6.2 Error - detection and -correction techniques

Parity checks

• One bit parity scheme

- Even : 송신자는 하나의 추가 비트를 포함하고 parity를 포함한 1의 개수가 짝수가 되도록 하는 값을 고른다.

- Odd : 송신자는 하나의 추가 비트를 포함하고 parity를 포함한 1의 개수가 홀수가 되도록 하는 값을 고른다.

=> 실제로 one-bit patiry scheme는 오류가 종종 burst형태로 함께 clustering되기 때문에 잘 작동하지 않을 수 있다.

• Two dimensional parity scheme

- one-bit parity scheme의 간단한 일반화

- 단일 비트 오류를 감지하고 수정 가능

- 두 오류의 조합은 탐색은 가능하지만 수정은 할 수 없음(위치를 알 수 없으니께,,)

Checksumming methods

• Internet checksum

1) transmitter(송신기)

- 16비트 정수의 1s complement의 합를 계산

- 1s complement의 합을 얻음

 

2) Receicer(수신기)

- 수신된 데이터(체크섬 포함)의 값의 1s complement의 합을 취하고 결과가 모두 1 bit인지 확인 => checksum 확인

 

+ TCP와 UDP 프로토콜에서 인터넷 체크섬은 모든 필드(헤더+데이터)에 대해 계산됨

+ IP에서 체크섬은 IP 헤더를 통해 계산됨

+ SW로 구현

Cyclic redundancy check(CRC)

• modulo-2 arithmetic

- 모든 연산은 modulo-2 연산을 취한다

- 모든 CRC계산은 carries와 borrows 없이 수행

- 덧셈과 뺄셈은 동일하며 피연산자의 XOR과 동일 => 같으면 0, 다르면 1

 

• Generator G

- 송신자 및 수신자에서 합의된 r+1 비트 패턴

- 가장 중요한(가장 왼쪽) 비트는 1

• Sender

- 추가 비트를 선택하고 D에 추가하여 결과 d+r 비트 패턴이 modulo-2 연산을 사용하여 generator G에 의해 정확히 분할될 수 있도록 한다.

• Receiver(수신기)

- d+r 수신 비트를 G로 나눈다

- 나머지가 0이 아닌 경우, 수신자는 오류가 발생했음을 알 수 있다.