[데이터 통신] Error Detection 과 Correction

오류의 종류

오류(Error)는 크기에 따라 두가지로 나뉜다.

 

보낼때의 데이터와 받을때의 데이터는 정확하게 일치해야하나, 전송 과정에서 의도치않게 값이 바뀔 수가 있다.

 

Single-bit error는 데이터중 하나의 비트가 값이 바뀐것을 말한다.

 

Burst error는 2개 이상의 비트가 바뀐것을 발한다.

 

Single-bit error는 위와같이 하나의 비트만 바뀐것을 말하며, 이 바뀐 비트는 Corrupted bit 라고 불린다.

 

Burst error는 2개 이상의 비트가 corrupted bit가 된것을 말하며, 위 사진은 첫번째 corrupted bit 부터 마지막 corrupted bit까지 총 8비트가 에러라고 보고있다.

 

 

 

 

생각해보자.

 

Corrupted bit를 찾아서 다시 정상적인 비트로 바꾸는것(Correction)이 쉬울까?

 

아니면, 그냥 데이터 자체에 오류가 포함되는걸 감지(Detection)하는게 쉬울까?

 

 

당연히 그냥 감지하는게 쉽다.

 

 

따라서 감지하는 관점에서는 single-bit error던 burst error던 상관없이 평등하게 감지해야할 오류다.

 

 

 

 

Error Detection

우선 우리가 보내려는 데이터를 k개의 비트씩 먼저 쪼개려고 한다.

 

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

 

 

 

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

 

 

 

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

 

 

 

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

 

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

 

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

 

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

 

오류 검출의 흐름을 표현한 것이 위 사진이다.

 

 

 

 

우리가 위와같은 규칙을 정했다고 해보자.

 

2비트로 이루어진 dataword에 1개의 추가적인 비트를 넣어서 3비트의 codeword를 만든다.

 

 

 

받는 쪽에 있는 checker는 위 표를 보면서 들어온 데이터를 검사한다.

 

만약 표에 존재하지 않는 codeword가 들어왔다면, 오류가 있다는 말이기 때문에 버릴것이다.

 

 

 

 

위 표는 잘 설계된 표일까?

 

 

 

 

Codeword의 비트가 하나만 바뀐다면 상관이 없다.

 

하지만 2개 이상의 비트가 corrupted bit가 된다면, 위 표에는 있지만 오류가 존재하는 codeword이기 때문에 checker는 잘못된 dataword를 추출하게 된다.

 

 

 

 

 

 

 

Simple Parity Bit

먼저 아래와 같은 dataword와 그에 대응되는 codeword가 적힌 표를 준비하자.

 

위 표에서 codeword의 맨 오른쪽에 있는 parity bit는 dataword에 있는 비트들을 모두 더한 값을 2와 modulor 연산(2로 나눈 나머지를 구하는 연산)한 값이다. 

 

 

 

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

 

만약 모두 더했을때 홀수가 된다면.. 그 codeword는 오류가 포함되었다는 말이 된다.

 

 

 

예시로 0111은 다 더했을때 값이 3이고, 2와 modulor 연산하면 1이므로 01111이다.

 

 

 

 

Simple Parity Bit는 dataword의 비트들을 generator에 넣고, generator는 하나의 Parity bit를 생성한다.

 

그리고 이를 dataword의 맨 오른쪽에 붙여서 보낸다.

 

 

 

받는 쪽은 codword의 모든 비트에 대해 checker가 하나의 Syndrome 으로 만든다.

 

Syndrome은 오류를 검출할때 쓰이는 값으로 codeword의 모든 비트들을 더한 후, 2와 modulor 연산한 값이다.

 

위에서 말했듯 codeword의 모든 비트들을 더했을때, 홀수인지 짝수인지 판별하는 값이 되겠다.

 

 

 

 

codeword에서 parity bit를 제외한 나머지 비트들(dataword)과 Syndrome을 사용하여 Decision Logic에 입력으로 준다.

 

Decision Logic은 syndrome이 0이라면(짝수라면) dataword를 받아들이고, 1이라면(홀수라면) 버린다.

 

 

 

 

 

이제 상황을 들어보자.

 

만약 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는 버려진다.

 

 

 

이 parity-check 코드는 홀수개의 오류만 검출 가능하다.

 

 

 

 

 

 

 

 

Cyclic codes

이름에서도 살짝 유추할 수 있듯, cylic code는 codeword가 회전하는 형태이다.

 

이게 무슨 말이냐면, 예를들어 1011000이라는 codeword가 있다면, left-shift 하여 011001로 만드는 것과 같다.

 

최상위 비트가 다시 최하위 비트로 들어간것을 확인할 수 있다.

 

 

 

Cyclic code는 CRC(Cyclic Redundancy Check)라고도 불린다.

 

 

 

 

위의 표는 4개의 비트를 가진 dataword에 대한 7개의 비트를 가지는 codeword의 대응을 보인다.

 

Codeword의 오른쪽 3 비트가 추가됐음을 알 수 있다.

 

이제 저 비트가 어쩌다 나왔는지 알아보자.

 

 

 

 

 

 

 

 

Codeword의 길이는 7이기때문에 3개의 비트를 추가해야하며

 

그림에서 추가된 3개의 비트($r_0 \cdots r_2$)는 다음과 같은 과정에 의해 만들어진다.

 

보내려는 dataword가 1001이라고 가정하자.

 

1. 먼저 어떤 값(Divisor)으로 나눌것인지를 정한다.

Divisor의 길이는 만들고자 하는 codeword의 길이($n$)에서 기존 dataword의 길이($k$)를 빼고 1을 더한 값이다.

 

즉 $n-k+1$이 divisor의 길이이고, 이번 예시에서는 divisor의 길이가 4임을 알 수 있다.

 

 

 

2. 기존 dataword 오른쪽에 값이 0인 비트 3개를 추가한다. (1001000)

 

 

 

 

3. 0이 추가된 dataword(1001000)를 divisor로 나눈다.

Divisor는 1011이라고 가정하자.

 

위 나눗셈은 그냥 나눗셈이 아니라 modulo-2 에 대한 나눗셈이다.

 

 

 

어떻게 나누게 되냐면, 나누려는 값에 존재하는 비트중 값이 1인 가장 왼쪽의 비트를 먼저 찾는다.

 

 

 

위에서는 1001000 가장 왼쪽의 1이 대상이 된다.

 

이때 뺄때는 XOR연산(서로 다를때만 1, 같으면 0)을 진행한다. 위에서는 1001과 1011을 XOR연산하므로 0010이 나온다.

 

이제 값이 1인 가장 왼쪽 비트는 XOR연산하고 나온 0010에서 오른쪽에서 2번째 1이다.

 

따라서 위 그림의 파란색 박스 부분까지 내려온 후, 다시 XOR연산을 진행한다.

 

그럼 1000과 1011을 XOR연산하므로 0011이 나온다.

 

 

다시 가장 왼쪽에 있는 1을 찾았지만, 더이상 Divisor로 나눌 수 없으므로 110이 나머지가 된다.

 

 

혼란스럽겠지만, modulo-2 연산을 깊이 이해하기 보다 방법만 알고 넘어가자.

 

 

 

 

4. 나머지(Remainder)가 추가될 3개의 비트가 되며, 몫은 버린다. (1001110)

추가된 비트 110 = $r_2r_1r_0$

 

 

 

이쯤에서 살짝 예상을 해보자.

 

나머지를 그대로 000을 추가했던 위치에 넣었다.

 

 

즉, 1001000에 1011로 나눈 나머지를 더했다.

 

따라서 나중에 체크할때, 다시 divisor로 나눠서 나머지가 0이 아니면 오류가 있다고 판단됨을 알 수 있다.

 

 

 

 

 

이후 전송된 codeword는 checker에서 예상한대로 위에서 가정한 divisor(1011)으로 나눈다.

 

 

이때 나눈 나머지를 Syndrome이라고 부르고, 만약 syndrome의 값이 0이 아니면 전송된 데이터는 버려진다.

 

 

 

위처럼 dataword의 특정 부분이 corrupted bit가 되면, 나머지가 0이 되지 않아 dataword가 버려짐을 알 수 있다.

 

 

 

 

비트 하나하나에 나머지 값은 민감하게 변화하므로 Cyclic codes는 전송된 codeword가 어디서 몇개나 변경됐든 오류를 감지할 수 있다.

 

 

 

 

 

 

 

 

Checksum

우리가 보내려는 메시지를 4비트 크기를 갖는 숫자 5개가 들어있는 리스트라고 하자.

 

만약 [7, 11, 12, 0, 6] 이라고 하면, 우리는 리스트의 원소들을 모두 합한 36이라는 숫자를 맨 오른쪽에 끼워서 같이 보낸다.

 

[7, 11, 12, 0, 6, 36]을 보냈는데, 나중에 리스트의 앞 5개의 숫자를 다 더했는데 36이 아니라면 오류가 존재한다는 말이 된다.

 

 

 

 

36은 이진수로 100100이고, 이는 6비트이다.

 

우리가 만든 리스트의 원소들은 공통적으로 4비트를 가진다고 가정했으므로 36도 4비트로 만들어줘야한다.

 

 

 

이때 사용되는게 1의 보수로 더하는 것(One's Complement Addition)이다.

 

별게 아니고 더하면서 4비트 범위를 넘어가는 비트는 다시 최하위 비트에 더해준다(wrap-around).

 

[7, 11, 12, 0, 6]에 대해 진행해보자.

 

 

 

 

7은 이진수로 0111이고, 11은 이진수로 1011이다.

 

둘을 더하면 10010 이고, 맨 오른쪽 1은 최대 크기(4비트)를 넘었으므로 다시 최하위 비트에 더해준다.

 

따라서 0011 이 된다.

 

 

 

이제 이 값과 12를 더해보자.

 

12는 이진수로 1100 이다.

 

따라서 둘이 더하면 1111이 된다.

 

 

 

0은 더해도 똑같으니까 넘어가고, 6은 이진수로 0110이므로 1111과 더하면 10101 이다.

또 다시 범위를 넘어가는 비트가 있으므로 최하위 비트에 더해주면 0110(십진수로 6)이 나온다.

 

 

 

 

 

이렇게 하나하나 더해서 만들기보다, 그냥 십진수로 모두 더한 후 정해진 범위를 넘어가는 비트들을 다시 더해주는 방식도 있다.

 

예를들어 36은 이진수로 100100 인데, 4비트를 넘어간 10을 다시 최하위에 더해서 0110 으로 해도 된다.

 

이는 최하위에 더할 값들이 4비트 다음 범위에 한번에 쌓여있다가, 맨 마지막에 다 더해주는 방식이므로 문제가 없다.

 

 

예를들어 다 더해서 45였다면, 이는 이진수로 101101 이고 4비트 범위에 맞게 더해주면 1111이 된다.

 

 

 

전통적인 체크섬 계산 방식

체크섬은 보내는 데이터를 모두 1의 보수로 더한 값에 1의 보수를 취한 값이다.

 

뭔말이냐면 위의 예시에서 보낼 데이터를 모두 1의 보수로 더했을때 6인데 이는 이진수로 0110이다.

 

여기에 1의 보수를 취하면 1001(십진수로 9)가 되고 이게 체크섬이 된다는 말이다.

 

 

 

 

어떻게 쓰이냐면, 보낸 리스트의 앞 5개를 먼저 1의 보수로 더하고

 

다 더한값과 체크섬을 더했을때, 1111이 나온다.

 

 

 

 

1의 보수 연산에 있어서 0(Positive Zero)의 보수는 -0(Negative Zero)이다.

 

이때 -0은 이진수로 1111로 표기한다.

 

 

따라서 특정 값과 그 값의 보수를 더하면 항상 negative zero가 나온다.

 

 

 

체크섬은 이런 성질을 이용했다고 볼 수 있다.

 

 

 

따라서 데이터를 받는 쪽에서 받은 데이터를 1의 보수 연산으로 모두 더했을때, negative zero가 나오지 않았다면 오류가 포함된다고 판단한다.

 

 

지금까지 했던 것들을 그림으로 보이면 위와같다.

 

보내려는 리스트를 1의 보수로 더하면 6이고, 이에 대한 체크섬은 9가 된다.

 

따라서 Packet에 이를 같이 담아서 보낸 후, 받는 쪽에서 모든 값을 1의 보수로 더하면 negative zero가 나오게 된다.

 

이 값을 한번 더 1의 보수로 계산하면 0이고, 이게 위 그림에서 Calculated Checksum이 된다.

 

 

 

 

발전된 체크섬 방식 - Fletcher's Checksum

위 흐름도를 보면, 먼저 체크섬은 16비트로 왼쪽(L) 8비트, 오른쪽(R) 8비트가 있다.

 

여기서 데이터가 추가될때마다 256으로 나눈 나머지를 R에 넣고, L은 계산된 R과 더한 후 256으로 나눈 나머지가 된다.

 

이를 보낼 데이터가 없을때까지 계속 진행하고, 최종적으로 체크섬은 L에 256을 곱하고(왼쪽으로 8번 shift) R을 더한 값이 된다.