해밍 거리 (Hamming Distance)

1. 해밍 거리(Hamming Distance)의 개념

  • 송/수신 데이터 오류 검출 및 오류 정정 등을 위해 두 데이터 간의 유사도를 수치화하는 함수

 

2. 해밍 거리 도출 메커니즘 및 오류 검출/정정 능력

(1) 해밍 거리 도출 사례 기반 메커니즘

  • 같은 길이를 가진 두 부호열 또는 비트열에 대해 같은 위치에서 서로 다른 기호의 개 수(Hamming Weight)로 산출 
해밍 거리 도출 사례 기반 메커니즘사례 설명
– Data1, Data2를 XOR 한 결과(00100110)의 Hamming Weight는 3이므로, Hamming Distance는 3으로 판단
– Hamming Weight: 부호열 중 ‘0’이 아닌 부호의 개 수

(2) 해밍 거리를 이용한 오류 검출/정정 능력

구분산출식설명
오류 검출 능력(td)td ≤ dmin – 1검출 가능한 최대 오류의 개 수
오류 정정 능력(tc)tc = {(dmin – 1) / 2}정정 가능한 최대 오류의 개 수
  • dmin: 최소 해밍 거리(Minimum Hamming Distance), 두 개 이상의 데이터 간 해밍 거리 중 가장 작은 거리.
  • 해밍 거리는 인공지능 분야의 유사도 측정을 위한 협업 필터링 등 추천시스템 Data 분석 및 네트워크 분야 전진오류수정(FEC)을 위한 해밍 코드 구현 시 활용

 

3. 오류 검출 및 정정을 위한 최소 해밍 거리

(1) 오류 검출을 위한 최소 해밍 거리

산출식사례 기반 설명
dmin  = m + 1– 송신측이 보낸 신호 1bit{해밍 코드 2bit}: 0{00} 혹은 1{11}
– 수신측에서 받을 수 있는 신호: {00, 01, 10, 11}
– 수신측에서 신호 수신 시:
00 : 0 (오류 없음)
01 : 오류 (오류 검출)
10 : 오류 (오류 검출)
11 : 1 (오류 없음)

(2) 오류 정정을 위한 최소 해밍 거리

산출식사례 기반 설명
dmin  = 2m + 1– 송신측이 보낸 신호 1bit{해밍 코드 3bit}: 0{000} 혹은 1{111}
– 수신측에서 받을 수 있는 신호: {000, 001, 010, 011, 100, 101, 110, 111}
– 수신측에서 신호 수신 시:
000 : 0 (오류 없음)
001 : 0 (3번째 bit 0으로 정정)
010 : 0 (2번째 bit 0으로 정정)
011 : 1 (1번째 bit 1로 정정)
100 : 0 (1번째 bit 0으로 정정)
101 : 1 (2번째 bit 1로 정정)
110 : 1 (3번째 bit 1로 정정)
111 : 1 (오류 없음)
  • 수신측에서 오류 정정을 위해 7 bit의 데이터를 송신할 때 2 x 7 + 1 = 15이므로 최소 해밍 거리인 15 bit의 해밍 코드가 필요하지만, 실제 해밍 코드 기반 오류 검출/정정 시 최소한의 Parity bit를 이용하여 11bit의 해밍 코드 만으로도 오류 정정 가능

 

4. 해밍 코드 도출 및 오류 검출/정정 과정 사례

(1) Parity bit 기반 해밍 코드 도출

  • 전송 데이터: 1001101, 짝수 패리티 비트로 추가
과정설명
패리티
비트 계산
2p – 1 ≥ d + p (p: 패리티 자리 수, d: 데이터 자리 수)
d = 7이므로, 2p – 1 ≥ 7 + p
∴ p = 4, 패리티 자리 수는 4
데이터 배치

2n 자리를 제외한 자리에 데이터 배치

1110987654321
100 110 1  
짝수 패리티 기반
체크 비트 도출

R1 = 1 (1, 3, 5, 7, 9, 11 자리의 1의 개수가 짝수 유지)

1110987654321
100 110 1 R1

(1, 0, 1, 0, 1, R1) → 짝수, ∴ R1 = 1
마찬가지로,
R2 = 0 (2, 3, 6, 7, 10, 11 자리의 1의 개수가 짝수 유지)
R3 = 0 (4, 5, 6, 7 자리의 1의 개수가 짝수 유지)
R4 = 1 (8, 9, 10, 11 자리의 1의 개수가 짝수 유지)

패리티 비트
배치한 해밍코드
1110987654321
10011100101

(2) 해밍코드 오류 검출 과정

과정설명
수신 데이터
배치
1110987654321
10010100101
체크 비트 확인

R = 1 (1, 3, 5, 7, 9, 11번째 값과 짝수 패리티 유지)

1110987654321
10010100101

∴ 1이 3개, R1 = 1
R2 = 1 (2, 3, 6, 7, 10, 11번째 값과 짝수 패리티 유지)
R3 = 1 (4, 5, 6, 7번째 값과 짝수 패리티 유지)
R4 = 0 (8, 9, 10, 11번째 값과 짝수 패리티 유지)

오류 자리 확인0111 → 7번째 자리 비트 오류
  • 패리티 비트의 결과값이 오류 비트의 위치

(3) 해밍 코드 오류 정정 과정

과정설명
오류 자리0111 → 7번째 자리 비트 오류
7번째 자리 수정

7번째 자리 “0”을 그 보수인 “1”로 변경

1110987654321
10010100101
오류 수정 결과
1110987654321
10011100101

∴ 정상 비트는 10011100101

 

콘텐츠 사용 시 출처 표기 부탁 드리고, 궁금한 점이나 의견은 댓글 남겨주세요^^

도리의 디지털라이프에서 더 알아보기

지금 구독하여 계속 읽고 전체 아카이브에 액세스하세요.

Continue reading