[데이터 통신] Error Detection and Correction - 2

Cyclic codes

 

codeword가 회전하는 형태이다. 예를 들어, 1011000이라는 codeword가 있다면, left-shift 하여 0110001로 만드는 것이다.

 

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

 

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

 

 

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

 

이 비트를 계산하는 방법에 대해 알아보자.

 

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

그림에서 추가된 3개의비트는 다음과 같은 과정에 의해 만들어진다.

 

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이라고 가정하자.

 

 

 

나누려는 값에 존재하는 비트중 값이 1인 가장 왼쪽의 비트를 먼저 찾는다.

 

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

 

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

 

 

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

추가된 비트 110 = r2,r1,r0

 

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

 

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

 

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

 

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

 

 

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

 

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

 

 

Advantages of Cyclic Codes

single-bit error, double errors, an odd number of errors, burst errors를 detecting 하는데 좋은 성능을 보인다.

하드웨어 및 소프트웨어에서 쉽게 구현할 수 있음.
특히 하드웨어에서 구현될 때 빠르다.

 

 

Checksum

체크섬은 모든 길이의 메시지에 적용할 수 있는 error-detecting 기술이다.

 

 

우리가 보내려는 메시지를 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비트 범위를 넘어가는 비트를 다시 최하위 비트에 더해주는 방식이다.

100100은 아래 4비트 0100은 그대로 두고, 앞에 2비트 10은 4비트(0100)에 더해줘서 0110으로 만들어 10진수로 변환하면 6이므로 6을 붙여준다. 즉, [7, 11, 12, 0, 6, 6] 이 되는 것이다.

 

 

Tradtional Checksum

 

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

 

위에 예시에서 6에 1의 보수를 취하면 1001이 되고 이것이 체크섬이 된다는 말이다.

 

하지만 위와 같은 체크섬 방식에서의 문제점은 합은 똑같이 36이지만, 36의 조합이 다른 숫자라면 오류가 있지만 정상적으로 보내게 되는 문제가 생긴다.

 

 

 

Enhanced Checksum - Fletcher's

 

 

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

 

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

 

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

 

• 앞, 뒤를 연관시켜놓으면 순서 고려 가능
  -> 모든 것들이 서로에게 영향을 주기 때문에 순서가 바뀌면 값이 바뀜.

 

Forward Error Correction

앞에서의 오류 검출과 재전송에 대해 설명했는데, 손상되고 손실된 패킷의 재전송은 실시간 멀티미디어 전송에 유용하지 않아 패킷을 즉시 재생성하고 에러를 수정해야 할 방법이 필요하다.

 

* Backward Error Correction (ARQ)

- 수신기에서 송신기로 피드백 사용 : 수신기는 데이터 블록이 올바르게 수신되었는지 여부를 송신기로 신호를 보낸다. 수신이 잘못되면 전송이 반복된다.

 

Hamming Code

 

 

 

쉽게 이해하자면, s2,s1,s0순으로 001이다. 이 말은 s2와 s1에는 문제가 없지만 s0에만 에러가 있다고 말하는 것이다.

즉, 수식을 통해 q0가 문제임을 알 수 있다. 

또한 111은 s2, s1, s0에 동시에 존재하는 문제를 보면된다. 즉, b1이 문제임을 알 수 있다.

 

 

 

Interleaving

 

 

에러를 모든 패킷에 분산하는 방식이다.

 

Compound

 

redundancy의 복제를 만들어서 redundancy 버전을 다음 패킷과 결합하는 것이다. 다음과 같이 보낼 수 있다.

 

 

Reference

https://ideadummy.tistory.com/112

[데이터 통신] Error Detection 과 Correction