9강 Error Detection and Correction (Block Coding, Hamming Distance, Error Detection 기법, Checksum,CRC)

개요

• Block coding : DVD나 CD등에서 이용하는데 실제로 스크레치가 나도 데이터가 손상되지 않도록 도와줌.
• Cyclic coding : 1,2계층에서 에러가 났는지 확인하는 방법으로 주로 wifi나 일반적으로 사용하는 방법입니다.
• Checksum : TCP/IP에서 헤더가 에러가 났는지 안 났는지 확인 → 오래된 시스템에서 주로 사용되고 성능이 Cyclic coding기법이 더 성능이 뛰어나지만, TCP기법은 과거에 나온 프토토콜이기 때문에 checksum을 사용하고 있음.
• Forward error correction

Error들의 타입

에러란 보낸 값에 대해서 예상치 못한 변화가 있는 것을 말한다. 쉽게 말하면 1을 보냈을 때 0이 감지되거나 0을 보냈을 때 1이 감지되는 상황을 말한다.

• Single-bit error : 한 비트만 에러가 나는 경우
• Burst error : 인접한 여러 개의 비트에 에러가 나는 경우. (대부분 에러는 이것)
• 블록마다 한비트만 에러가 나면 에러를 찾기가 쉽지만 블록에 여러개가 에러가 나면 찾는 것이 쉽지 않다.

Redundancy

에러를 감지하기 위해서 더 드는 비용 및 크기를 말합니다.

• to detect or correct errors, we need to send some extra bits

Detection vs Correction

• correction of errors is more difficult
• detection: 에러가 발생하는지 보기만 한다.
• correction : 실제로 에러가 발생하던 안 하던 무조건 과정을 다 거치는 식으로 동작 시킨다.

Coding

실제로 들어온 데이터를 dataword라고 부르는데, 거기에 redundancy를 더해서, 최종적으로 codeword가 나옵니다.

당연하게 효율을 위해서는 redundancy가 적은 것이 효율이 좋다.

• Redundancy는 다양한 coding schemes을 만듭니다.
• coding scheme에서 중요한 요소는

coding schemes의 두가지 종류

• Block coding → 쉽게 생각하면 블록의 모양은 유지되고, 뒤에 Redundancy를 붙히는 경우
• Convolution coding → 데이터가 들어오면 이전 정보에 기반해서 비트를 만들어 냅니다.지금까지 히스토리 기반인 것이다.

Block Coding

위에서 설명했듯, datawords에 redundant bit를 붙혀서 codewords를 만들어낸다.

따라서 codeword는 늘 dataword보다 크다.

• one-to-one coding process이다.
• 만약 수신자가 잘못된 codeword를 받게되면, 전송중에 문제가 발생했다고 볼 수 있다.
• 만약 dataword bit 가 k , redundant bit가 r, codeword가 n이라면 n=k+r
• invalid codeword = 2^n - 2^k

Error Detection

• valid codewords가 들어오면 에러가 발생하지 않았다고 판단.
• 만약 에러가 정교하게 나서 둘 다 통과한다면, undetected 상태가 된다. (추후 다른 계층에서 detection 할 것이다.)

example

• k = 2 and n = 3
• 00가 01을 보내는데 01 은 011로 바껴서 보내진다.
• 여기서 사용하는 기법 : prarity check → 1의 갯수를 항상 짝수개로 유지시켜주는 기법

1. 만약 수신자가 011릘 받으면 01을 받았음을 안다.
2. 만약 에러가 나서 111을 받는 경우 잘못된 codeword이므로 버려진다.
3. 만약 에러가 나서 000이 받아지면 이것은 valid라고 되어버린다. 따라서 감지가 불가하다.

• invalid code word

Hamming Distance

Hamming Distance : 얼마나 에러 detection을 잘하는지 보는 성능 척도

얼마나 비트가 다른지를 세주는 것입니다. (상당히 단순) (same size)

• d(00000, 01101) = 3
• received codeword and the sent codeword로 보면 됩니다.
• 이 값은 transmission 동안 corrupted 된 비트의 갯수 입니다.
• XOR operation을 해주고 1의 갯수를 세주면 쉽게 찾을 수 있다.

1. The Hamming distance d(000, 011) is 2 because (000 ">

s bit에러를 detection할 수 있다.

즉 d min은 sbit에러를 반드시 dectetion할 수 있다고 보장하는 것이다.

Error Detection 기법

Linear Block Codes

 이것은 X1이 vaild이고 X2가 vaild이라면 X1 + X2 도 vaild 이라는 것을 의미한다.

 Parity-Check Code방식

 k-bit dataword is changed to an n-bit codeword where n = k + 1

 

 101 + 110 = 011로 vaild 하다는 것을 볼 수 있다.

 minimum Hamming distance is dmin= 2

 minimum Hamming distance for this category is dmin = 2

 The code is a single-bit error-detecting code

 A parity-check code can detect an odd number of errors

 → 쉽게 찾는 법은 모두 0인 것을 제외하고 1의 갯수가 최솟값인 것이 minimum hamming distance 라고 해도 된다.

 

 이것은 보낼 때

 

 이 공식을 따르고, 1이 남으면 1이 나오고 0이 남으면 0을 parity code에 넣어주는 것입니다.

 받을 때는

 

 아래 공식으로 0이 남으면 에러가 발견되지 않는 것이고 1이면 에러가 발생했다고 detect된다.

 에러가 짝수개가 나면 detection할 수 없다는 것을 기억하자.

Cyclic Codes

wifi LTE 유무선랜 전부 사용이 된다.

1. • cyclic shift 해도 값이 같다. (아래거는 오른쪽으로 shift 시킨것)

   

   

Cyclic Redundancy Check

1. • Cyclic redundancy check (CRC) : LAN과 WAN에서 사용된다.
   • 사이클릭 코드를 이용해서 error를 dectection 하는 code word입니다.
   • 인코딩
   • Decoding

예시

1. • C(7, 4)

   

   

1001 이 들어오면 Divisior 1011 즉 이것은 generater라고 부른다.

divisior 가 4비트이면 나머지는 최대 3비트인 것을 알 수가 있다.

따라서 시작할 때 1001에서 3비트 나머지가 있으니까 처음에

1001000으로 시작한다.

그러면 1011로 나눠본다. 여기서 나누기에서 뺴기는 XOR로 하는 것을 잘 보자.

divisior는 표준별로 약속되어있다. 즉 이더넷이면 이더넷 만의 divisor가 있고 wifi면 wifi만의 divisior가 약속되어있다.

수신측에서

 

아래와 같이 볼 수 있는데 0이면 에러가 발생하지 않는 것이고 0이 아니면 에러가 발생했다고 볼 수 있다.

Polynomials(다항식)

divisior를 만드는 방식을 볼 수 있다.

• Degree of a Polynomial : 6
• Adding and Subtracting 도 당연히 다항식으로 표현이 가능하다.
• Multiplying or Dividing Terms

 

앞서서 했던 방법을 다항식을 이용해서 다시 해보기

1. 

Cyclic Code Analysis

 

Generator : divisior,

syndrome : 수신기 측에서 새로 구한 나머지

Error : syncdrome이 0이 아니라면 에러가 발생했다고 보는 것이다.

 

여기서 e(x)가 g(x)로 나누어 떨어지지 않게 설계하면 된다.

1. • Single-Bit Error같은 경우 e(x) = x^i로 표현이 가능하다.
   • 예시 싱글 비트 에러같은 경우 어떤걸 사용해야 더 좋은 dection이 가능할까?

   

   • x^2같은 경우 x+1로 divisior를 설계 하면 나누어 떨어지지 않으니까, 잘 설계했다고 볼 수 있다.

이 부분은 PPT 한번 봅시다.(예시)

CRC-32 가 현재 WIFI 이더넷 등이 사용하고 있는 generater라고 보면 됩니다.

CRC 는 설계가 쉽고 구현이 쉬워서 상당한 장점이 있다.

Reed-Solomon code

Reed-Solomon code라는 방법이 있다.

이것은 CD에서 사용하는 기법입니다. (block coding이다. error corection이 가능하다.

Checksum

CRC가 나오기 전에 사용하던 방법(TCP에서 사용)

CRC는 나머지 연산을 기반으로 동작하지만 Checksum같은 경우 덧셈이 기반이다.

데이터와 체크섬을 더해서 0이 된다.

호환성때문에 계속 체크섬을 쓰고 있다.

메세지 비트를 m개의 비트로 쪼개줍니다.

이후 generator는 extra m-bit unit c를 만들고 그것이 checksum이라고 불린다.

예시

4 비트를 5개를 보내는 예시

(7, 11, 12, 0, 6)을 보내야 하면 실제로 보내는 것을 (7, 11, 12, 0, 6, 36) 이다. 36은 원래 값들의 합이다.

둘이 같으면 에러 없음, 둘이 다르면 에러가 있는 것이다.

여기서 숫자를 그대로 보내기 어려우니까 압축하는 방법을 사용합니다.

36 in binary is (100100)2 입니다.

이건 4비트만 살려야 하니까 0100 만 살려주고 그 위의 숫자는 더해주는 방식으로 압축을 해준다.

즉 0100 + 10 = (0110)2가 됩니다.

1의 보수 표현과 2의 보수 표현에 대한 이야기가 나오는데 1의 보수 표현은 0을 1111로 표현해서 두개를 더하면 1111이 되면 된다.

그래서 둘의 비트를 반전만 해주면 음수와 양수를 쉽게 왔다갔다 할 수 있다.

2의 보수는 0000이 0으로 정의 됩니다.

2의 보수표현은 1의 보수로 표현하고 1을 더해주기만 하면 됩니다.

 

Forward Error Correction

FEC라고 부르고 Error correction이다. 이게 대부분 무선 시스템에 다 들어가 있다고 보면 된다.

Hamming Distance사용

dmin = s + 1 → 디텍션에서는

correction에서는 dmin = 2t + 1 이다.

 

Using XOR

실제로 데이터를 보낼 때 4개를 보낸다고 하면 1개 더해서 5개를 보내고 1개에는 4개를 XOR한 값이 들어가게 됩니다.

다만 2개가 깨지면 안된다. 오직 1개만 깨졌을 때 감지가 가능하다

만약 깨졌다면 그것을 빼고 Redundant를 XOR 하면 이전 값을 복구 할 수 있다.

Chunk Interleaving

이 기술은 bust에러를 sigle 에러로 바꾸는 것을 말합니다

쉽게 말하면 패킷을 한줄로 세워서 순서대로 보내는 게 아니라 행을 바꿔서 보내버려서 버스트하게 에러가 나도 한줄에 하나씩 에러가 난 것으로 생각할 수 있다.