[데이터 통신] Error Detection 과 Correction

Node and Link

데이터 링크 계층에서의 통신은 node-to-node라고 한다.

 

데이터는 한 지점에서 다른 한 지점까지 많은 네트워크 (LANs and WANs)를 통하여 도달한다.

또한 이 네트워크들은 라우터에의해 연결되어 있다.

 

 

 

 

데이터는 node를 연결해주는 link를 통해 전송된다.

 

 

 

데이터 링크 계층은 Physical Layer(물리 계층)와 Network Layer(네트워크 계층)사이에 껴있다.

 

데이터 링크 계층은 물리 계층으로 부터 데이터를 받아 네트워크 계층에게 service를 제공한다.

 

Error Control

 

 

먼저 오류의 종류에는 크기에 따라 두가지로 나뉜다.

 

- Single-bit error

데이터 중 하나의 비트가 값이 바뀐 것

 

 

바뀐 비트를 Corrupted bit라 부른다.

 

- Burst error 

2개 이상의 비트가 바뀐 것

 

 

첫번째 corrupted bit부터 마지막 corrupted bit까지 총 8비트가 에러라고 보고있다.

 

 

 

 

 

Corrupted bit를 찾아서 다시 정상적인 비트로 바꾸는 것(Correction) 보다

 

데이터 자체에 오류가 포함되는걸 감지(Detection) 하는 것이 훨씬 쉽다.

 

 

Error Detection

먼저 보내려는 데이터를 k개의 비트로 먼저 쪼개야한다.

 

그리고 r개의 추가적인(redundant) 비트를 넣어서 n개의 비트를 갖는 블록으로 만든다.

 

*n = k + r

 

기존 데이터의 일부인 k개의 비트를 dataword라 부르고, 최종적으로 만들어지는 n비트의 블록은 codeword라 부른다.

 

 

 

전에 봤듯이 추가적인(redundant) 비트를 넣어서 새로운 블록으로 만드는걸 block coding이라고 한다.

 

추가한 비트를 통해 어떻게 오류를 감지하는지 알아보자.

 

 

 

 

보내는 쪽(Sender)는 dataword를 generator를 통해 codeword로 만들어서 보낸다.

하지만 신뢰할수 없는 전송(Unreliable transmission)이 있기 때문에 받는 쪽(Receiver)에서는 codeword가 맞는건지 확인할 필요가 있다.

 

따라서 checker가 codeword를 확인한 후, 맞게 왔다면 dataword만 추출(Extract)하고, 이상한 것은 버린다.

 

 

 

Example

 

 

 

알고리즘은 맨 오른쪽에 있는 parity bit는 dataword에 있는 비트들을 모두 더한 값을 2와 modulor연산을 한 값이다.

 

2로 나눈 나머지를 뒤에 붙였기 때문에 codeword를 모두 더한 값은 항상 짝수가 된다.

 

 

 

만약 1011이라는 dataword를 보내게 되었다면, 위 표에서 찾았을때 codeword는 10111이다.

 

이걸 전송했을 때, 받는 쪽에서는 4가지 상황이 발생할 수 있다.

 

1. 오류가 없다. (Codeword : 10111)

    -> Syndrome이 0이 되므로 dataword가 받아들여진다.

 

 

2. Dataword에 있는 비트중 하나가 corrupted bit가 된 경우 (Codeword : 10011)

    -> Syndrome은 1이되므로 dataword는 버려진다.

 

 

3. Parity bit가 corrupted bit 가 된 경우 (Codeword : 10110)

    -> Dataword는 문제가 없는데도 불구하고 syndrome이 1이므로 버려진다.

 

 

4. Parity bit와 dataword의 비트 하나가 corrupted bit가 된 경우 (Codeword : 00110)

    -> Dataword가 문제가 있음에도 불구하고 syndrome이 0이므로 받아들여진다.

 

 

5. Dataword에 있는 비트중 3개가 corrupted bit가 된 경우 (Codeword : 01011)

    -> Syndrome이 1이므로 dataword는 버려진다.