Chapter10 Error Detection And Correction

Types of Errors

bit들이 다른 포인트로 이동할 때, interference에 의한 예측할 수 없는 변화에 노출된다.

interference는 신호의 모양을 바꾼다.

single-bit error는 주어진 bits에서 한 개의 bit만 바뀐 것을 의미한다.

burst error는 2개 이상의 bits들이 변화한 것을 의미한다.

---

Redundancy

Error를 detecting 하거나 correcting 하는 것의 central concept은 redundancy(중복)이다. 에러들을 감지하거나 바로 고치기 위해서는 추가적인 bits나 data를 보내야 한다.

이런 redundants들은 sender에게서 만들어지고 remover에게서 제거된다.

redundants들은 잘못된 bit들을 recevier가 감지하거나 바로 고칠 수 있게 해 준다.

---

Detection VS Correction

Correction은 Detection보다 훨씬 어렵다.

Error detection에서, 우리는 그저 error가 발생했는지만 보면 된다. bit 몇 개가 손상되었는지 조차 상관없다. 즉, single-bit error와 burst error를 같은 취급 한다.

Error correction에서, 우리는 정확히 망가진 bit의 개수와 그들의 위치까지 알아야 한다.

---

Coding

Redundancy는 다양한 coding schemes에 의해 이루어진다. Sender는 redundant bits와 actual data bits사이의 relationship를 통해 redundant bits를 만든다.

Receiver는 redundant bits와 actual data bits를 비교하여 error를 detect 한다. Data bits에 대한 redundant bits의 ratio과  robustness of the process는 coding scheme에서 매우 중요한 요소들이다.

---

Block Coding

Block Coding에서 우리는 메시지들을 각각 k개의 bits들로 이루어진 blocks로 나누고 datawords라고 부른다. 우리는 r개의 redundant bits를 각각의 block에 더하고 길이가 n=k+r인 block을 만든다.

Block coding을 통해 만들어진 n개의 bit를 가진 blocks를 codewords라고 부른다.

---

Hamming Distance

Hamming distance는 두 개의 binary data strings를 비교하는 측정법이다.  Hamming distance는 같은 곳에 위치한 bit들이 몇 개가 다른지를 알려준다.

 

각각의 같은 길이의 strings들이 존재한다고 할 때, Minimum Hamming distance는 가능한 모든 경우에서 가장 작은 distance를 의미한다.

010,011,101,111이 존재하는 경우 Minimum Hamming Distance는 1이다.

d single bit errors를 detect 하기 위해, codewords들의 minimum Hamming distance는 d+1 또는 그 이상이어야 한다.

d single bit errors를 correct 하기 위해, codewords들의 minimum Hamming distance는 2d+1가 요구된다.

---

Error Detection

패리티 비트(Parity bit)는 전체 데이터 워드 중 1의 개수가 짝수가 되도록 붙는다. 예를 들어 데이터워드가 1101001이면 1의 개수가 4이므로, 추가되는 패리티 비트는 0이다. (홀수가 되도록 구현할 수도 있다)

데이터워드 a0 ~ a3에 대해 송신 측에서는 이들의 1 개수에 따라 패리티 비트 r0을 추가해 수신 측에 전송한다.

수신 측에서는 전송받은 코드워드를 복호기의 검사기(Checker)에 넣어 오류를 검출한다. 이 때 검출의 결과는 신드롬(Syndrome, s0)을 통해 나타난다. 이 신드롬 값이 0이면 오류가 발생하지 않은 것으로, 코드 워드는 수락되어 데이터 워드를 추출한다. 만약 신드롬 값이 1이라면 이는 손상된(유효하지 않은) 코드워드로, 폐기된다.

만약 1011의 데이터 워드를 전송하는 상황을 가정해 보자. 데이터워드 1011의 1은 3개이므로, 패리티 비트 1이 추가되고 10111이란 코드 워드가 생성되어 보내진다.

만약 비트 하나가 손상되어 10011이라는 코드워드가 보내진 다면, 코드 워드의1 개수가 홀수이므로 검사기는 이 코드 워드가 손상된 것임을 알 수 있다. 즉, 신드롬 값이 1이다. 패리티 비트는 1이 짝수 개가 되도록 붙기 때문이다.

하지만 만약 두 비트가 손상되어 00101이라는 코드워드가 보내진 다면, 코드 워드의 1 개수가 짝수이므로 검사기는 이 코드 워드를유효한 것으로 판단한다. 즉, 신드롬 값이 0이다. 이를 통해 단순 패리티 검사 코드는 짝수 개의 오류를 검출할 수 없음을 알 수 있다.

---

Cyclic Codes

Cyclic codes는 extra property를 가지고 있는 special linear block codes이다. Cyclic code에서, 만약 codeword가 cyclically shifted 되었다면, 그 결과는 또 다른 codeword가 된다.

예를 들어서, 1011000이 우리가 cyclically left-shifted 해서 011001을 만들었다면 이것 또한  codeword가 된다.

---

Cyclic Redundancy Check

우리는 error들을 바로 고치기 위해 cyclic codes를 만들 수 있다.

LANs와 WANs에서는 cyclic redundancy check(CRC)를 사용한다.

CRC는 Divisor라는 요소를 통해 구현하는데, 데이터 워드를 Divisor로 나눈 나머지(Remainder)를 데이터 워드에 추가해 코드 워드를 생성한다. 그림은 데이터워드 1001에 대한 코드워드를 생성하는 과정이다.

Dataword가 1001이고 Divisor가 1011일 때, 위와 같이 계산이 된다. 알아둬야 할 것은 나눠져야 할 것의 leftmost가 1이면 Divisor에 1을 곱해주고 0이면 0을 곱해준 값을 나눠줘야 한다는 것이다. 또, 곱셈과 뺄셈이 기존에 우리가 알고 있는 방식이 아니라 곱은 And연산 뺄셈은 XOR을 이용하여 계산한다.

Uncorrupted 라면 Syndrome은 Zero가 나오지만 Corrupted 라면 Non-Zero값이 나온다.

Cyclic Codes를 이용하면 single-bit error, double error, odd number of error, 그리고 burst error들을 모두 detect 할 수 있다.

Software와 hardware, 특히 hardware에서 쉽게 구현할 수 있다.

---

Checksum

Checksum은 길이와 상관없이 error를 detecting 하는 기술이다.

인터넷에서, checksum 기술은 data-link layer보다는 주로 network 그리고 transport layer에서 사용된다.

calculate check sum using 1's complement

---

Forward Error Correction

corrupted and lost data의 retransmission은 매우 비효율적이기 때문에, 우리는 error를 correct 하고 packet을 즉시 재생산할 필요가 있다.

---

Chunk Interleaving

FEC(Forward Error Correction)은 receiver가 몇몇의 작은 chunks들을 잃는 것을 허락한다.

위와 같이 paket들을 정렬후 보내고 receiver가 다시 역순으로 정렬하면 송신 중에 packet 하나가 없어지더라도 receiver 입장에서는 각각의 paket에서 한개의 chunk만 없어진 것이기 때문에 큰 문제가 발생하는 것을 막을 수 있다. 예를 들어서 음성 데이터가 전송 될 때, 한글자의 소리가 없어지는 것은 문제가 되지만 그 이하의 소리가 없어지는 것은 큰 문제가 되지 않는다.

---

Compounding

Compounding은 현재 packet에 이전 packet의 Low-resolution packet을 추가하여 보내는 것이다. 이렇게 하면 packet하나가 손실 되더라도 다음 packet에 손실된 packet의 Low-resolution이 있기 때문에 완벽하진 않지만 어느정도 복구가 가능하다.