[Computer Networks] Error Detection - Parity bit, Checksum, CRC

Error Detection

bit Parity

Checksum

CRC

 

---

EDC

error detection and correction bits (Data-link layer Trailer)

D

data protected by error checking, may include header fields

 

- Frame 은 Transmission Media 를 통해 전달됨\

 

---

Single bit parity (패리티 비트)

- detect single bit erros

- Even parity : set parity bit so there is an even number of 1's (1의 개수가 짝수가 되도록 맞추는 것)

-> count # of 1 even = ok / odd = error

 

XOR operation

- Sender : 보내려는 D에 어떤 parity bit 를 추가해야할지 알 수 있음

- Receiver : Parity bit 를 포함한 모든 비트에 대해 XOR operation을 수행해서 결과가 0이면 ok 1이면 error

 

Two-dimensional bit parity (2차원 비트에 대한 error detection)

- detect and correct single bit erros

- Even parity : set parity bit so there is an even number of 1's

- 송수신 데이터를 2차원 데이터인 것 처럼 간주

- 각각의 행과 열에 대한 패리티 비트를 모두 계산

 

---

Checksum

- sending data with the sum of the data

 

Sender

- addition (one's complement sum) of content

- checksum value put into checksum field

 

Receiver

- compute checksum of received segment

- check if computed checksum equals checksum field value

> not equal - error detected

> equal - no error detected. But may be erros nonetheless?

 

---

CRC

- Cyclic Rebundancy Check

- more powerful error-detection coding

- D : data bits (given, think of these as binary number) 

- G : bit pattern (generator), of r+1 bits (given)

- Sender 와 Receiver 간에 공유하는 bit 패턴이 존재 (G)

 

- Goal : choose r CRC bits, R, such that <D,R> exactly divisible by G

- Sender와 Receiver 둘 다 알고 있는 G를 통해 에러 발생 여부 판단

- receiver knows G, divides <D,R> by G. If non-zero remainder : error detected!

- can detect all burst erros less than r+1 bits

- widely used in practice (Ethernet, 802.11 WiFi)

 

Sender

- 보내려고 하는 데이터 D 에 R 비트를 추가해서 보냄

- R 비트 : G를 통해 계산. D를 G로 나눈 나머지

- <D,R> = D*2^r XOR R

 

Receiver

- D'과 R'을 G로 나눔 -> 나누어 떨어지면 ok / 나누어 떨어지지 않으면 error

 

- Set a divisor between the sender and the receiver (G)

- Calcualte the remainder of a dataword divided by the divisor (D%G)

- Combine the remainder into the data word (R)

 

- R (r bit)

- G (r+1 bit)

- r 0's bit

 

---