Error Correction Code

Parity Bit·Checksum·CRC는 오류가 있다는 사실만 알릴 뿐, 어느 비트가 틀렸는지는 알려주지 않는다. ECC(Error Correction Code, 오류 정정 부호)는 여기서 한 걸음 더 나아가 오류의 위치까지 찾아 정정할 수 있도록 설계된 부호로, 재전송을 다시 요청하기 어렵거나 비싼 메모리·저장 장치 같은 곳에서 널리 쓰인다. 얼마나 많은 오류를 검출·정정할 수 있는지는 부호가 갖는 해밍 거리(Hamming distance)로 결정된다[1].

해밍 거리

해밍 거리는 길이가 같은 두 부호어(codeword)를 비교했을 때 값이 다른 비트의 개수다. 예컨대 1010과 1001은 뒤 두 비트가 다르므로 해밍 거리가 2다. 어떤 부호가 쓰는 모든 부호어 쌍 중 최솟값을 최소 해밍 거리($d_{min}$)라 하며, 이 값이 그 부호의 오류 검출·정정 능력을 결정한다[1].

• 검출만 하는 경우 최대 $d_{min}-1$개의 오류까지 검출할 수 있다.
• 정정까지 하는 경우 최대 $\lfloor (d_{min}-1)/2\rfloor$개의 오류까지 정정할 수 있다.

Hamming(7, 4) 코드

가장 널리 알려진 ECC는 4비트 데이터에 3비트 패리티를 더해 7비트 부호어를 만드는 Hamming(7, 4) 코드다. 데이터 비트를 $d_1,d_2,d_3,d_4$라 하면 패리티 비트는 각각 다음과 같이 계산되고, 부호어는 $(p_1,p_2,d_1,p_3,d_2,d_3,d_4)$ 순서로 배치된다[1].

$p_1=d_1\oplus d_2\oplus d_4,p_2=d_1\oplus d_3\oplus d_4,p_3=d_2\oplus d_3\oplus d_4$

Example

데이터 1101($d_1{d}_2{d}_3{d}_4$)을 부호화하면 $p_1=1,p_2=0,p_3=0$이 되어 부호어 1010101이 만들어진다. 수신 측은 세 패리티를 다시 계산해 비교하고, 그 결과(신드롬)를 이진수로 읽어 틀린 비트 위치를 바로 찾아낸다 — 예컨대 5번째 비트($d_2$)가 뒤집혀 1010001로 수신되면 신드롬은 5를 가리켜 그 비트를 정정할 수 있다.

Hamming(7, 4)의 최소 해밍 거리는 3이므로 위 공식을 그대로 적용하면 최대 2비트 오류를 검출하거나 최대 1비트 오류를 정정할 수 있지만, 이 둘을 동시에 하지는 못한다 — 위 예에서 5번째 비트 대신 5·6번째 두 비트가 함께 뒤집히면 신드롬은 엉뚱하게 3번째 비트를 가리켜, 정정을 시도하면 오히려 다른 유효한 부호어로 잘못 바뀐다[1].

자동차 분야의 활용

동시에 검출·정정하려면 더 큰 최소 해밍 거리가 필요하다. 전체 비트에 대한 패리티 비트를 하나 더 추가해 최소 해밍 거리를 4로 늘린 확장 Hamming 코드는 1비트 오류를 정정하면서 2비트 오류는 (정정 없이) 검출까지 할 수 있는데, 이를 SECDED(Single Error Correction, Double Error Detection)라 부른다[1]. Infineon의 AURIX TC3xx 계열 MCU는 이 SECDED 방식의 Hamming 코드로 SRAM을 보호하며, PFlash에는 최소 해밍 거리 6을 갖는 BCH 코드를 적용해 2비트 오류 정정과 3비트 오류 검출(DECTED)까지 지원한다[2]. CAN FD가 확장 CRC의 목표 해밍 거리를 6으로 설계하는 것도, 최소 해밍 거리가 Hamming 코드에 국한되지 않고 오류 검출·정정 부호 전반에 적용되는 척도임을 보여주는 예다.

참고문헌

[1]

R. W. Hamming, “Error Detecting and Error Correcting Codes”, The Bell System Technical Journal, vol 29, no. 2, pp 147–160, 1950.

[2]

Infineon Technologies, “AN0001 — AURIX TC3xx Functional Safety (FuSa) in a Nutshell”, 2023.