해밍 코드 (Hamming Code)

I. 2계층 네트워크 오류 검출 기법

구분기법설명
전진오류수정(FEC)
(수신 측에서 수정)
해밍 코드– 중복 패리티를 추가
– 수신측 오류 검출/수정
상승 코드– 한계값, 순차적 디코딩
– 오류 비트 모두 수정
후진오류
수정(BEC)
(송신측에
재전송요청)
오류
검출
방식
패리티 (Parity)– 데이터 끝에 비트 추가
– 짝/홀수 패리티 비트
블록합 (Block sum)– 가로와 세로로 검사
– 2차원 패리티 검사
순환 중복검사 (CRC)– 이진 나눗셈 연산 기반
– 중복 검사로 오류 검출
체크섬 (Checksum)– 앞서 보낸 데이터 보수화 전송, 수신측 합산
재전송
요청
(ARQ)
Stop and Wait– 송신측 한 프레임 전송
– 수신측 에러 유무 판단
Go Back N– 오류 발생 프레임 이후 모두 재전송 요청
Selective Repeat– 오류가 발생한 프레임만 재전송 요청
Adaptive ARQ– 데이터 오류 발생 확률
– 프레임 길이 동적 변경
  • ARQ: Automatic Repeat Request, 자동 재전송 요구

 

II. 해밍 코드 도출 과정

  • 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

 

III. 해밍코드 오류 검출 및 정정 과정

  • 해밍코드: 10010100101

가. ‘10010100101’ 해밍코드 오류 검출 과정

과정설명
수신 데이터
배치
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번째 자리 비트 오류
  • 패리티 비트의 결과값이 오류 비트의 위치

나. 해밍 코드 오류 정정 과정

과정설명
오류 자리0111 → 7번째 자리 비트 오류
7번째 자리 수정7번째 자리 “0”을 그 보수인 “1”로 변경

1110987654321
10010100101
오류 수정 결과
1110987654321
10011100101

∴ 정상 비트는 10011100101

2 Comments

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^