05 에러 검출 코드
[1] 패리티 비트
; 에러 검출 코드로 가장 간단하게 사용되고, 주로 컴퓨터 내부의 주기억 장치에서 사용함
메모리에 저장하거나 전달할 데이터에 패리티를 붙여서 전송
- 여러 비트에서 에러가 발생하면 검출이 되지 않음
- 에러가 난 곳이 어디인지 모름
짝수 패리티
; 데이터에서 1의 개수를 짝수로 맞춰줌
홀수 패리티
; 데이터에서 1의 개수를 홀수로 맞춰줌
[2] 해밍 코드
; 패리티 비트를 응용하여 에러를 정정할 수 있도록 고안된 것으로 한 비트에 에러가 발생했을 때 위치를 찾을 수 있음
- 원본 데이터 외에 추가적으로 많은 비트가 필요
- 추가되는 패리티 비트의 수는 2^p ≥ d+p+1에 의해서 계산 가능 (p: 패리티 비트 수, d: 데이터 비트 수)
- 짝수 패리티를 사용
원본 데이터가 00101110일 때 해밍 코드를 생성하는 과정
D3, D5, D7, D9, D11 ⇒ 1이 2개이므로 P1은 0
D3, D6, D7, D10, D11 ⇒ 1이 3개이므로 P2는 1
D5, D6, D7, D12 ⇒ 1이 1개이므로 P4는 1
D9, D10, D11, D12 ⇒ 1이 3개이므로 P8은 1
해밍 코드가 010111011110일 경우 에러가 있는 지 검사해라
색칠 된 부분을 기준으로 검사해보면
P1 = 1
P2 = 0
P4 = 1
P8 = 0
이고, 모든 패리티 비트 값이 0이 아니기 때문에 에러가 있다.
에러가 있는 자리는 0101(2)로 5번째 자리다.
[3] 순환 중복 검사(CRC)
; 데이터 전송에서 에러를 검사하는 순환 중복 검사
- 높은 신뢰도
- 에러 검출을 위한 오버헤드가 적음
- 랜덤 에러(집단 에러)나 비스트 에러를 포함한 에러 검출에 좋은 성능
송신측
- 데이터에 (키 길이-1)만큼 0을 붙인다.
- 0을 붙인 데이터를 key로 나눈다.
- (키 길이-1)만큼의 나머지를 FCS로 잡는다.
- 데이터에 FCS를 붙여서 전송한다.
수신측
- 데이터에 FCS가 붙은 비트를 key로 나눈다.
- XOR 연산을 사용한다.
- 연산 결과는 1번째 비트가 0으로 소거되도록 몫 비트를 정한다(1일 경우 key값과 동일, 0일 경우 0000)
- 비트 단위로 CRC를 계산하면 처리 속도에 문제가 있어서 CRC 테이블 기법을 사용한다.
생성 다항식
x^7+x^5+x^2+x+1은 10100111과 동일하다.
Uploaded by Notion2Tistory v1.1.0