X

해밍 코드 (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 자리를 제외한 자리에 데이터 배치
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 1 0 1
짝수 패리티 기반
체크 비트 도출
R1 = 1 (1, 3, 5, 7, 9, 11 자리의 1의 개수가 짝수 유지)
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 1 0 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의 개수가 짝수 유지)

패리티 비트
배치한 해밍코드
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 1 1 0 0 1 0 1

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

  • 해밍코드: 10010100101

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

과정 설명
수신 데이터
배치
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1
체크 비트 확인 R = 1 (1, 3, 5, 7, 9, 11번째 값과 짝수 패리티 유지)
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1

∴ 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”로 변경
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 0 1 0 0 1 0 1
오류 수정 결과
11 10 9 8 7 6 5 4 3 2 1
1 0 0 1 1 1 0 0 1 0 1

∴ 정상 비트는 10011100101

Categories: 네트워크
도리:

View Comments (2)