ch08.Error Detection and Correction

Error를 contorl 한다 -> Detection한다.

만약 에러가 있으면, 두 가지 방법으로 해결을 할 수 있다.

1. Retransmission

2. Forward error correction(순방향 에러 정정)

 

Types of Errors

- 에러는 transmission사이에 bit반전으로 인해 발생한다.

2가지로 나눌 수 있다.

Single bit errors vs. Burst errors

one bit에러 발생은 정확하게 찾을 수 있지만, 여러 개가 동시에 에러가 발생하면 detection이 힘들다.

단일 에러 , 여러개 비트 에러

에러 탐지 과정

Error Detection 함수를 실행한다. -> processing, 

Error detection code가 있고, 이를 f(data) = f(data')과 비교한다

 

Parity check 

1의 개수를 센다.

1의 개수를 짝수로 맞추는 경우 혹은 홀수로 맞추는 경우

위의 그림처럼 매트릭스 형태로 맞춘다고해도, 2개 이상의 오류를 찾지 못 한다.

 

Cyclic Redundancy Check(CRC) - 순환 중복 검사

에러 탐지 코드에 강력한 기술 중 하나이다.

비트를 다항식으로 나타내기도 한다.

eg. P(x) = x^3 + x^2 + 1 -> 1101

전송할 데이터가 110010이라고 하면, P(x)의 최고차항의 계수대로 0을 붙인다. 여기선 3차항이므로, 

110010+000을 해서 110010000을 한다. 

그 후, 110010000/1101을 해서 나머지가 0이면 에러가 없는것이고, 나머지가 있으면 에러가 있는 것이다.

하지만 에러 여부만 알고 어디서 에러가 났는지는 못 찾는다.

 

 

 

 

Circuit with Shift Registers for Dividing by the Polynomial

Forward Error Crrection

감지된 오류를 수정하려면 일반적으로 데이터 블록을 재전송해야한다.
무선 애플리케이션에는 적합하지 않다.
무선 링크의 BER(비트 오류율)이 상당히 높을 수 있으며 이로 인해 재전송 횟수가 많아질 수 있다.
단일 프레임의 전송 시간에 비해 전파 지연이 매우 길다. 따라서,  수신된 비트를 기준으로 오류를 수정해야 한다.

보내는 사람의 데이터의 각 k-bit블록은 FEC를 사요해서 n-bit block(n>k)로 맵핑한다.

DataBlock에 유효한 비트는 Codeword로 맵핑된다. 이 맵핑되지 않는 bits들이 오면 유효하지 않다고 판단한다.

메시지를 데이터워드(Dataword)라는 k비트 단위 블록으로 쪼개어, 각 블록마다 중복 비트 r비트를 추가한다. 따라서 각 블록의 길이 n은 k + r이 된다. 결과적으로 생성되는 길이 n의 비트 블록을 코드워드(Codeword)라 한다.

 

Block code Principles

• Hamming Distance
  • 서로 다른 두 워드 비트에서 같은 자리에서 다른 비트가 있는 것의 개수
  • 예를 들어 v1 = 010101 , v2 = 111111 이면 해밍턴 거리는 3
• Redundancy of the code
  • 오류를 검출하거나 수정하기 위해 데이터에 추가적인 비트를 보내는 것 , 이를 중복 비트 라고 한다.
• Code rate
  • 총 비트에 대한 데이터 비트의 비율 k/n
  • 코드가 없을 때와 동일한 데이터 속도로 데이터를 전송하는 데 필요한 추가 대역폭의 양을 측정한 것이다.

 

Using XOR

연속으로 데이터를 받았을 때, 중간에 에러가 있거나 빠진 값이 있는 경우, 다른 나머지 값들과 XOR연산을 해서, 누락되거나 잘못된 정보를 판단할 수 있다.

 

Chunk Interleaving

 

Combining

먼저 t비트 오류를 수정할 수 있는 n비트 패킷을 만들 수 있다.

그런 다음 m개의 행을 인터리브하고 비트를 열별로 보냅니다. 이러한 방식으로 최대 m × t 비트의 오류까지 버스트 오류를 자동으로 수정할 수 있다.

 

Compounding

저화질 data를 끼어서 보낸다.

만약 전송 도중 손실이 생기면 위에서 끼어서 보낸 data를 재생한다.

 

D1, D2의 reg상태가 다르다.

State Diagram

Trellis