2019년 3월 22일
해밍 코드 (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 자리를 제외한 자리에 데이터 배치
| ||||||||||||||||||||||
| 짝수 패리티 기반 체크 비트 도출 | R1 = 1 (1, 3, 5, 7, 9, 11 자리의 1의 개수가 짝수 유지)
(1, 0, 1, 0, 1, R1) → 짝수, ∴ R1 = 1 | ||||||||||||||||||||||
| 패리티 비트 배치한 해밍코드 |
|
III. 해밍코드 오류 검출 및 정정 과정
- 해밍코드: 10010100101
가. ‘10010100101’ 해밍코드 오류 검출 과정
| 과정 | 설명 | ||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 수신 데이터 배치 |
| ||||||||||||||||||||||
| 체크 비트 확인 | R = 1 (1, 3, 5, 7, 9, 11번째 값과 짝수 패리티 유지)
∴ 1이 3개, R1 = 1 | ||||||||||||||||||||||
| 오류 자리 확인 | 0111 → 7번째 자리 비트 오류 |
- 패리티 비트의 결과값이 오류 비트의 위치
나. 해밍 코드 오류 정정 과정
| 과정 | 설명 | ||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 오류 자리 | 0111 → 7번째 자리 비트 오류 | ||||||||||||||||||||||
| 7번째 자리 수정 | 7번째 자리 “0”을 그 보수인 “1”로 변경
| ||||||||||||||||||||||
| 오류 수정 결과 |
∴ 정상 비트는 10011100101 |
About The Author
도리
2 Comments
기모링
잘보고감