해밍 거리와 ECC

해밍 거리(Hamming Distance)와 ECC(Error Correction Code) — 부호어 간 차이를 수치화하는 지표(해밍 거리)와, 이 지표를 기반으로 오류를 검출·정정할 수 있는 코드(ECC). 자동차 프로토콜 CRC 성능 평가(HD 기준)와 MCU 메모리 보호(ECC)가 이 개념 위에서 정의된다.

해밍 거리

Hamming Distance (HD) — 같은 길이를 가진 두 데이터 간 다른 값을 가지는 비트의 수.

예시

• Data A: 1100010
• Data B: 1101001
• 차이 비트: 3번째·5번째·7번째 → HD = 3.

계산 방식: A ⊕ B의 1 개수.

최소 해밍 거리

Minimum Hamming Distance ($d_{min}$) — 부호어 집합 $C$에서 모든 부호어 쌍의 HD 중 최솟값.

$d_{min}=\min \{d(x,y)\mid x,y\in C,x\ne y\}$

예시 — $C=\{010,011,111,101\}$

${}_4{C}_2=6$ 개 조합:

쌍	XOR	HD
d(c1, c2)	001	1
d(c1, c3)	101	2
d(c1, c4)	111	3
d(c2, c3)	100	1
d(c2, c4)	110	2
d(c3, c4)	010	1

$d_{min}=1$.

조합 공식

${}_n{C}_r=\frac{n!}{r!(n-r)!}$

검출·정정 능력

$d_{min}$으로부터 다음 두 능력이 정해진다.

능력	공식
오류 검출 $t_d$	$t_d=d_{min}-1$
오류 정정 $t_c$	$t_c=\lfloor (d_{min}-1)/2\rfloor$

예시 — $C=\{000,111\}$

• $d(c_0,c_1)=3\Rightarrow d_{min}=3$.
• $t_d=3-1=2$ → 2비트 에러까지 100% 검출.
• $t_c=\lfloor 2/2\rfloor =1$ → 1비트 에러 정정 가능.
• 단, 001을 수신한 경우: 000에서 1비트 오류인지 111에서 2비트 오류인지 구분할 추가 정보가 필요.

ECC (Error Correction Code)

ECC (오류 정정 코드) — 데이터 전송·저장 시 발생할 수 있는 오류를 검출하고 수정할 수 있는 코드.

• 데이터 무결성 보장 목적.
• 신뢰성이 중요한 통신 시스템, 컴퓨터 메모리, 디지털 저장 장치 등에 사용.
• 가장 기본 형태가 Hamming Code.

자동차 분야의 ECC

• ISO 26262 만족을 위한 MCU 메모리 에러 정정 기능.
• MCU 내의 RAM, Flash, Register 메모리는 낮은 확률로 저장된 값이 변경될 수 있음 (SEU, alpha particle 등).
• 대다수 주요 차량용 MCU는 ECC 기능 지원 → 1비트 에러 자동 정정, 2비트 에러 검출·알람.

Hamming Code

Hamming Code — 1비트 오류 정정이 가능한 대표 ECC.

Hamming (7, 4) 부호

• 7비트 코드 워드 = 데이터 4비트 $(m_1,m_2,m_3,m_4)$ + 패리티 3비트 $(p_1,p_2,p_3)$.
• 데이터 4비트의 조합 $2^4=16$ 가지 → 유효 부호어 16개.

패리티 계산 규칙:

$p_1=m_1\oplus m_2\oplus m_4$ $p_2=m_1\oplus m_3\oplus m_4$ $p_3=m_2\oplus m_3\oplus m_4$

부호 순서: $c=(p_1,p_2,m_1,p_3,m_2,m_3,m_4)$.

부호화 예시

메시지 $(1,0,1,1)$:

• $p_1=1\oplus 0\oplus 1=0$.
• $p_2=1\oplus 1\oplus 1=1$.
• $p_3=0\oplus 1\oplus 1=0$.
• 부호 = $(0,1,1,0,0,1,1)$.

성능

• $d_{min}=3$.
• $t_d=2$ — 2비트 에러까지 검출.
• $t_c=1$ — 1비트 에러 정정.

오류 위치 식별

수신된 7비트로 각 패리티를 재계산 후 수신 패리티와 비교. 일치/불일치 패턴이 3비트 신드롬 $(e_3,e_2,e_1)$을 형성:

신드롬 $(e_3,e_2,e_1)$	에러 위치
000	에러 없음
010	2번 비트
110	6번 비트
111	7번 비트

예시 — 데이터 0001 전송 → 정상 부호 1101001

• 전송 중 에러 → 수신 1101011.
• $p_2,p_3$ 불일치, $p_1$ 일치 → 신드롬 110 → 6번 비트 에러.

CRC 성능과의 관계

CRC의 성능 지표 중 하나는 해당 프로토콜이 보장하는 $d_{min}$. CRC 섹션 참조:

• CAN 15bit CRC: 목표 HD = 6 → 실제 스터프 비트 영향으로 HD = 2.
• 차량 Ethernet 32bit CRC: HD = 4(일반) / HD = 5 (3,006 bit 이하).

같이 보기

• Parity / Checksum