5_Error Detection/Correction Code

Error in Computer Network

1.Binary Symmetric Channel(다른 값으로 error) 

2.Binary Erasure Channel (값이 사라지는 error)

 

 

Error Detection& Recovery

네트워크 상에서 에러를 예방하는 건 거의 불가능함, 에러를 발견하고 수정하는게 최선.

 

Error Detection

-Bit Level Error

Bit 단위로 에러가 남 (ex : 0 -> 1, 1->0) ,link 나 channel 단위

 

-Packet Level Error

패킷이 소실됨, 네트워크 계칭에서 혼잡(congestion)으로 손실이 발생하기도 함(Buffer Full)

 

Error Recovery (2 Approaches)

-Retransmission : 재전송, latency 상승

-FEC(Forward Error Correction) : 에러 수정, 추가의 헤더를 보내서 에러가 나면 어디서 수정본을 찾아야할지 알려줌

 

Type of Errors

-Single Bit Error : White noise, one bit

-Burst Error : impulse noise(외부 잡음)

 

Error Detection

n bit codeword = k bit data + (n-k)bit codebits

Code Rate = data/ codeword = k/n

A : No Error

B : Illegal Codewords (잘못 보냄)

C : Legal Codewords 지만 원래 보내려던 코드와는 다름

 

 

Parity Code(중요)

Even parity code 와 odd parity code

비트에서 1의 개수를 짝수로, 홀수로

 

ex) 

101 에 Even parity code 는 0, Odd parity code 는 1

 

Hamming Distance (중요)

-n bits binary sequence W1 and W2의 다른 비트, 즉 XOR =1 의 개수

dmin = min d(Wi,Wj) 가장 작은 HD

 

-Parity Code의 Hamming Distance??

1 bits? 아님 

ex)

0000 1

0000 0 

->even,odd 로 맞춰서 비트가 나오기 때문에 불가능

 

내가 물어봤던 질문

0010 1

0100 1

두 비트가 다른

 

즉, 아무리 거리가 작아도 2 bits 다. 가장 작은 HD이다.

 

 

 

 

파란색이 비트가 있는 부분이다. 흰색으로 bit error 가 났을 때 수정을 할 수 있는가?

위에 있는 선에선 2bit 이상의 에러가 나면 A,B중에 어느 곳에서 에러가 났는지 알 수 없다. 

밑에 선에선 3 bit 이상의 에러가 나면 B,C 중에 어느 곳에서 에러가 났는지 알 수 없다.

 

d min >= ( 홀 수 -> 2t +1 짝수 -> 2t ) 

t bits error can be detected , but not corrected generally 

 :일단 error 가 나면 detected는 할 수 있다. correction 할 수 있는 가에 문제.