Error Detection

Types of Errors

- single-bit error: 주어진 데이터 유닛 중 1bit만 바뀐다.

- burst error: multiple error (2 or more bits)

 

Error Detection vs Correction

- 공통점: extra/redundant/check bit 수행

- 차이점: correction을 하려면 detection이 선행되어야 한다. correction을 위해선 정확한 비트 넘버와 위치를 알아야 하므로 더 어렵다.

 

Error Detection

- Redundancy개념을 이용 - 에러를 감지하기 위해 끝에 extra bits를 더한다.

- sender가 redundant bit를 붙이면 receiver는 두 비트 세트 사이의 관계를 체크하고 오류를 감지한다.

- ratio of redundant bits = (Original Data) / (Codeword).   (codeword = original+redundant)

 

Block Coding

- 메시지를 datawords라 불리는 k비트 block 단위로 나눈다.

- 각 block에 r redundant 비트를 붙인 길이 n = k+r

- 결과로 나오는 n비트 block을 codewords라고 한다.

- 다음 두 조건을 만족할 때, receiver가 오류를 감지한다.

1. receiver has a list of valid codewords.

2. The original codeword has changed to an invalid one.

 

- XORing

- Hamming Distance: 두 codeword의 다른 비트 수. XOR로 1 되는 지점 수를 세면 된다.

- codeword들의 hamming distance 최솟값이 2라면, 그 코드는 한 비트 에러만 감지 가능하다.

  이유: 두 비트가 바뀔 경우 다른 codeword와 동일해지므로 구분할 수 없게 됨.

  ex) codeword 000, 101, 011, 110 이 있을 때, 각각의 hamming distance는 2이므로 최솟값은 2. 000이 100, 010, 001로 한 비트만 바뀌면 다른 codeword와 겹치지 않기 때문에 에러를 감지할 수 있지만, 011로 두 비트 바뀔 경우 겹치기 때문에 에러를 감지할 수 없다.

 

Error Detection Techniques

1. Parity check

2. Cyclic redundancy check

3. Checksum

 

1. Parity Check

- Even parity check / Odd parity check 두 가지가 있다.

- Even parity check: 데이터에 포함된 1의 개수가 짝수가 되도록 redundant bit를 붙인다.

  ex) 0110110은 1의 개수가 4이므로 0을 붙여 01101100을 만듦-> 1 개수가 짝수(4)

     0011111은 1의 개수가 5이므로 1을 붙여 00111111을 만듦-> 1 개수가 짝수(6)

- Odd parity check: 데이터에 포함된 1의 개수가 홀수가 되도록 redundant bit를 붙인다.

- 홀수 개 오류만 감지 가능하다. (1, 3, 5, ... 개)

 

2. Cyclic Redundancy Check (CRC)

- Cyclic Codes: codeword를 순환적으로 shift한 결과가 다른 codeword가 되는 linear block code.
  ex) 예를 들어, 1011000을 left-shift한 결과 0110001 또한 codeword가 된다.

- CRC는 cyclic code의 예이다. LAN, WAN과 같은 network에 사용된다.

- binary division 기반의 가장 강력한 redundancy checking 테크닉.

- CRC에 사용되는 redundancy bits는 데이터 유닛을 predetermined divisor로 나눠 얻는다. 그 나머지가 CRC.

- CRC는 divisor보다 한 비트 적어야 하며, data string에 CRC를 붙인 resulting bit sequence는 divisor에 의해 나눌 수 있어야 한다. 나눠지지 않으면 에러 감지.

 

3. Checksum

- 어느 길이의 메세지에도 적용될 수 있는 error-detecting technique.

- network, transport layer 프로토콜에 사용된다.

- check generator (sending side): 메시지를 일정 비트 단위로 끊어서 모두 더한 뒤 보수를 취함

- checker (receiving side): 메시지를 일정 비트 단위로 끊어서 모두 더하고 보수 값을 취한 값(checksum)이 0이면 오류가 없다고 판단.