해밍코드 원리와 패리티 연산을 활용한 ECC 에러 검출 원리

해밍코드

 

안녕하세요.

오늘은 네트워크 통신 과정에서 발생하는 데이터 유실 또는 오류에 대한 검출방법 중 지난 CRC 연산 포스팅에 이어 해밍 코드의 원리를 활용한 ECC 에러 검출 원리에 대해 알아보겠습니다.

 

반응형

 

◈ECC(Error Correction Code) 란?

 

ECC의 약자는 Error Correction Code입니다. 약자의 의미 그대로 데이터의 에러 발생여부를 감지하여 수정까지 하는 장치로 고도의 데이터 신뢰성을 요구하는 서버 시스템에서 메모리 반도체의 에러를 감지하고 수정하여 시스템을 보호하는 기능입니다. 최근 메모리 공정의 집적도 향상으로 Cell Cap용량이 줄어들고 고속 동작시 발생하는 발열은 지속적으로 데이터 신뢰도의 하락을 유발하기 때문에 에러를 검출하고 수정하는 기술은 앞으로 더욱 중요한 기술이 될 것입니다.

 

AI, GPT 등 인공지능의 발달로 데이터의 고속화(Frequency)와 대역폭(Input/Output) 증가는 필수 불가결한 요소가 되었습니다. 지난 CXL 메모리 인터페이스 포스팅을 통해 빠른 데이터 처리를 위해서는 고속으로 동작하는 메모리와 GPU, CPU 등 각각의 장치 간의 터페이스의 중요성에 대해 소개드렸습니다.

 

2023.04.17 - [유용한 생활 정보] - CXL 메모리 반도체 인터페이스

CXL 메모리 반도체 인터페이스

 

또한 엄청나게 증가한 데이터의 양과 함께 데이터의 무결성 또한 중요한 기술이 되었고 데이터 통신의 에러를 검출할 수 있는 가장 기본적인 방법 CRC 연산에 대해 원리와 구현 방법까지 아래 포스팅을 통해 자세히 확인하실 수 있습니다. 

 

 

2023.02.07 - [유용한 생활 정보] - CRC 연산 방법 CRC-8 CRC-16

CRC 연산 방법 CRC-8 CRC-16

 

이번 포스팅에서는 메모리 반도체가 늘어난 데이터 전송선로에서 데이터 정확도를 높이면서 한개의 에러를 감지해 수정까지 해줄 수 있는 ECC 동작 원리인 해밍코드에 대해 알아보겠습니다.

 

◈해밍코드 (Hamming Code)

 

오류 검출 구조는 반복 부호, 패리티 비트, 체크섬, CRC, 해시함수, 전방 오류 정정 등이 있으며 이 중 ECC는 패리티 비트를 활용한 해밍코드 연산으로 수행됩니다. 1950년 벨 연구소에서 리처드 해밍에 의해 되입된 해밍코드는 초기의 컴퓨터의 데이터 입력을 천공카드를 활용하면서 발생하는 오류에 대한 극복에서 시작되었습니다. 해밍코드를 사용하기위해서는 전송자와 수신자 간 짝수, 홀수 패리티 중 어느 것을 사용할지가 먼저 약속되어야 합니다.

 

◈패리티 비트(Parity Bit)란?

 

패리티비트는 데이터 전송 과정에서 발생할 수 있는 오류를 검출하기 위한 추가 데이터(비트)입니다. 짝수와 홀수로 구성된 패리티는 전체 데이터 중 1의 개수가 짝수가 되게 하거나 홀수가 되게 비트를 추가하는 방법입니다. 아래 예시를 보면 더욱 쉽게 패리티 비트에 대해 이해하실 수 있습니다.

 

※패리티 비트 예시 (출처 : 위키백과)

7 Bit Data	Parity Bit + Data (8Bit)
	Even(짝수) 데이터의 1의 갯수가 짝수일 경우 0 데이터의 1의 갯수가 홀수일 경우 1	Odd(홀수) 데이터의 1의 갯수가 짝수일 경우 1 데이터의 1의 갯수가 홀수일 경우 0
0000000	0 0000000	1 0000000
0101100	1 0101100	0 0101100

 

 

◈패리티 비트(Parity Bit)수의 결정

 해밍코드에 사용될 패리티 비트의 홀,짝을 결정했다면 몇 개의 비트로 패리티를 구성할지 정의해야 합니다. 패리티 비트수는 데이터의 비트수와 연동되어 반드시 아래 부등식을 만족하는 최소한의 수여야만 합니다.

★패리티 비트 결정 부등식
   2^p >= p + m + 1
※p:추가할 패리티 비트 개수, m(데이터 비트 개수)

예를 들어, 한개의 비트로 이루어진 데이터의 경우, 패리티 한 개는 부동식을 완성할 수 없고 두 개 이상의 패리티부터 부등식을 만족하는 최소의 패리티로 사용가능합니다.

 

※한 개의 비트를 가진 데이터의 오류를 검출하기 위한 패리티 비트 개수 산출하기
※부등식 : 2^p >= p + m + 1
①한 개의 패리티 개수 사용할 경우(p=1)
     2^1=2  < 1+1+1=3  (부등식 만족하지 않음)
②두 개의 패리티 개수 사용할 경우(p=2)
     2^2=4 = 2+1+1=4 (부등식을 만족하는 최소의 수)
③세 개의 패리티 개수 사용할 경우(p=3)
     2^3=8 > 3+1+1=5 (부등식을 만족하는 수)

 

위 예시에서 두 개의 패리티를 선택할 경우 Hamming(데이터 비트 수+패리티비트 수,데이터개수)으로 표현하여 Hamming(3,1)이라고 표현합니다. 이 경우 한개의 데이터 비트의 오류를 검출하기 위해서는 최소 두 개 이상의 패리티 비트를 사용해야 하기 때문에 실질적으로 세 개의 데이터를 전송하지만 실제 데이터는 한 개이므로 전송 효율이 1/3입니다. 더 많은 비트를 가진 데이터의 경우에도 동일한 방식으로 패리티 비트와 전체 비트를 산출할 수 있습니다.

 

◈해밍코드의 에러검출 원리

 

해밍코드 연산을 통해 한 개의 에러를 검출하고 수정할 수 있습니다. 메모리 반도체에서는 이러한 원리를 이용해 128b+8b의 ECC를 재공하고 있다고 마이크론 반도체 홈페이지를 통해 공개하고 있습니다. 이는 128비트의 데이터 중 한 개의 에러에 대해 검출 및 수정이 가능하다는 의미이며, 이를 위해 8개의 패리티 비트를 사용하고 있다는 의미입니다. 마이크론 메모리 반도체에서 사용하는 ECC 연산의 패리티가 부등식을 만족하는지 확인해 보았더니 128비트의 데이터를 처리하기 위한 최소의 패리티 비트는 8개였습니다.

 

※128 개의 비트를 가진 데이터의 오류를 검출하기 위한 패리티 비트 개수 산출하기
※부등식 : 2^p >= p + m + 1

①7개의 패리티 개수 사용할 경우(p=7)
   2^7=128 < 7+128+1=136 (부등식 불만족)

①8개의 패리티 개수 사용할 경우(p=8)
  2^8=256 >= 8+128+1=137 (부등식을 만족하는 최소의 패리티 비트 수)

 

 

▶패리티 비트의 위치

 

해밍코드 연산시 사용하는 패리티 비트는 2^(n-1) 자리에 배치되어 최종 전송할 데이터와 조합하여 전송됩니다. 아래 예시를 통해 실제 데이터에서 패리티 비트의 위치를 쉽게 알 수 있습니다.

 

※전송할 데이터 내의 패리티 비트의 위치
p1=2^(1-1)=1
p2=2^(2-1)=2
p3=2^(3-1)=4
p4=2^(4-1)=8
pn=2^(p-1)=

 

※패리티 비트와 데이터의 위치

  - d(데이터), p(패리티)

10	9	8	7	6	5	4	3	2	1
d6	d5	p4	d4	d3	d2	p3	d1	p2	p1

 

▶패리티 비트 연산

 

패리티 비트의 개수와 위치를 알았다면 실제 에러 검출을 위해 사용할 패리티 코드를 구해내야 합니다. 이때 해당 코드의 위치로부터 2^(n-1) 개 단위로 모든 데이터를 xor 연산 처리 합니다. 짝수 패리티를 사용하는 경우 1의 개수가 홀수이면 1, 짝수이면 0이 됩니다.

 

※패리티비트 실제 연산
p1=xor(1,3,5,7,9,...)
p2=xor(2,3,6,7,...)
p3=xor(4,5,6,7,12,13,14,15,...)
p4=xor(8-15,24-31,...)
...

	9	8	7	6	5	4	3	2	1
p1	v		v		v		v		v
p2			v	v			v	v
p3			v	v	v	v
p4	v	v

 

지금까지 해밍코드와 패리티 연산 방법을 알아보았습니다. 이제 실제 데이터를 통해 해밍코드 연산을 통해 어떻게 에러가 검출되고 수정되는지 알아보겠습니다.

 

 

 

▶해밍코드 실제 연산

 

데이터 "1010"을 기준으로 해밍코드 연산을 수행하여 에러를 검출하고 수정하는 과정을 알아보겠습니다. 4개의 비트로 이루어진 데이터의 에러를 검출하기 위해서는 최소 3개의 패리티 비트가 필요합니다.

 

※2^3=8 = 3+4+1=8  (부등식 만족, 2^p >= p + m + 1)

 

3 개의 패리티 비트의 위치는 아래와 같고, 

 

※p1=2^(1-1)=1, p2=2^(2-1)=2, p3=2^(3-1)=4

 

이를 데이터로 표현하면 아래와 같이 7비트의 코드가 됩니다.

 

7	6	5	4	3	2	1
1	0	1	p3	0	p2	p1

 

다음 순서로 실제 패리티 비트의 값을 연산을 통해 산출해 보겠습니다.

 

※데이터 1010의 패리티 비트 연산 과정

p1=xor(1,3,5,7,9,...)=(0,1,1)=1의 개수가 짝수이므로 0
p2=xor(2,3,6,7,...)=(0,0,1)=1의 개수가 홀수이므로 1
p3=xor(4,5,6,7,12,13,14,15,...)=(1,0,1)=1의 개수가 짝수이므로 0

 

이렇게 산출된 패리티 비트는 원래의 데이터와 패리티 비트의 자리에 맞추어 "1010010" 의 데이터로 새롭게 전송됩니다.

 

7	6	5	4	3	2	1
1	0	1	0 p3	0	1 p2	0 p1

 

이렇게 데이터와 패리티 비트로 조합된 데이터를 수신하면, 코드를 풀이하는 디코딩 과정을 수행하게 됩니다. 위에서 인코딩한 과정과 동일하게 패리티 비트 연산을 수행합니다.

 

※패리티 비트의 디코딩 과정

1=xor(1,3,5,7,9,...)=(0,0,1,1)=1의 개수가 짝수이므로 0
p2=xor(2,3,6,7,...)=(1,0,0,1)=1의 개수가 짝수이므로 0
p3=xor(4,5,6,7,12,13,14,15,...)=(0,1,0,1)=1의 개수가 짝수이므로 0

 

위와 같이 모든 연산과정의 결과 모든 패리티가 0이되면 에러 없이 정상적으로 데이터 전송이 완료된 것입니다.

 

만약 전송한 데이터 중 한개의 오류가 있었다면 어떻게 검출하는 지도 확인해 보겠습니다.

 

 

전송 당시 "1010010"의 정상적인 데이터가 "1110010"로 한 개의 비트에 오류가 발생하여 수신되었다면 수신자가 해밍코드를 디코딩하는 과정은 아래와 같습니다.

 

p1=xor(1,3,5,7,9,...)=(0,0,1,1)=1의 개수가 짝수이므로 0
p2=xor(2,3,6,7,...)=(1,0,1,1)=1의 개수가 홀수이므로 1
p3=xor(4,5,6,7,12,13,14,15,...)=(0,1,1,1)=1의 개수가 홀수이므로 1

 

위의 디코딩 과정에서 0이 아닌 패리티 비트들은 전송된 데이터에 에러가 발생했음을 의미함과 동시에 110은 10진수로 6을 의미하며 6번째 데이터의 오류를 표현하여 시스템이 해당 에러를 수정할 수 있게 합니다. 이렇게 해밍코드의 인코딩, 디코딩 과정을 통해 한 개의 에러를 검출하고 수정하는 과정을 SEC(Single Error Correction)하고 합니다.

 

하지만 해밍코드는 한 개의 비트만 검출할 수 있고, 두 개 이상의 에러는 정확한 동작을 기대할 수 없습니다. 이러한 단점을 보완한 것이 SECDED이며 Single Error Correction Double Error Detection)입니다.

 

▶SECDED (Single Error Correction Double Error Detection) 

 

SECDED는 기존에 만들어진 패리티(SEC)가 포함된 모든 데이터를 xor연산하여 추가로 한 개의 패리티(DED)를 생성합니다. SEC 과정에서 진행한 데이터 "1010"의 해밍코드 연산 데이터를 기반으로 SECDED 연산을 추가해 보겠습니다. DED를 위한 마지막 비트는 SEC를 통해 만들어진 데이터의 모든 비트의 xor 연산의 결과입니다.

 

xor(1,0,1,0,0,1,0) = 1의 개수가 홀수이므로 DED 비트는 1이 됩니다.

7	6	5	4	3	2	1	DED
1	0	1	0 p3	0	1 p2	0 p1	1

 

만약 정상적으로 데이터가 송, 수신되었을 경우 아래와 같은 SEC / DED 연산과정을 통해 에러가 없음을 확인할 수 있습니다. SECDED 연산을 위한 패리티 디코딩 진행 시에는 패리티 비트는 제외하고 연산을 수행합니다.

 

	SEC			DED
수신 패리티	0 p3	1 p2	0 p1	1
연산 패리티	0 xor(5,6,7)=(1,0,1)	1 xor(3,6,7)=(0,0,1)	0 xor(3,5,7)=(0,1,1)	1
xor	0	0	0	0

 

전송 당시 "1010010"의 정상적인 데이터가 "1110010" "1110010"로 한 개의 비트에 오류가 발생한 경우, SECDED 연산 과정을 통해 아래와 같이 DED가 1일 경우, SEC가 0이 아닌 경우에는 한 개의 에러의 발생과 위치를 정확히 알 수 있습니다.

 

	SEC			DED
수신 패리티	0 p3	1 p2	0 p1	1
연산 패리티	1 xor(5,6,7)=(1,1,1)	0 xor(3,6,7)=(0,1,1)	0 xor(3,5,7)=(0,1,1)	0
xor	1	1	0	1

 

 

그렇다면 두 개 이상의 에러가 발생한 경우는 어떨까요? 전송 당시 "1010010"의 정상적인 데이터가 "1111010" "1111010"로 두 개의 비트에 오류가 발생한 경우, SECDED 연산 과정을 통해 아래와 같이 DED가 0일 되고, 동시에 SEC가 0이 아닌 경우에는 두 개 이상의 오류가 발생하여 수정할 수 없음을 의미합니다.

	SEC			DED
수신 패리티	0 p3	1 p2	0 p1	1
연산 패리티	1 xor(5,6,7)=(1,1,1)	0 xor(3,6,7)=(0,1,1)	0 xor(3,5,7)=(0,1,1)	1
xor	1	1	0	0

 

지금까지 해밍코드와 패리티 비트를 활용한 ECC 연산에 대해 살펴보았습니다. 해밍코드는 세 개 이상의 에러를 검출하거나 수정할 수 없는 단점을 가지고 있으며 이를 해결하기 위해 CRC 연산을 추가하여 데이터의 무결성을 보완하고 있습니다.