Error Detection and Correction

에러의 종류

에러는 전송과 수신 사이에서 하나의 비트가 바뀌면 발생한다. 

• binary 1 → binary 0
• binary 0 → binary 1

Single Bit Errors

• 한 비트만 영향을 받아 주변 비트에는 영향을 미치지 않는 독립적인 오류
• white noise가 있는 환경에서 발생할 수 있음.

Burst Errors

• 길이 B의 연속적인 비트 시퀀스에서 발생하는 오류이다. 첫 번째와 마지막 비트뿐만 아니라 중간의 여러 비트들이 오류가 발생할 수 있
• 충격 소음이나 모바일 무선 환경에서의 fading으로 인해 발생할 수 있음.
• 데이터 전송 속도가 높을수록 더 커짐.(높은 속도에서 짧은 시간 안에 더 많은 데이터가 전송되기에 오류율도 증가)

예시 그림

 

 

Error Detection

 

frame: 데이터는 하나 이상의 연속적인 비트 시퀀스로 전송됨

 

Pb​: 비트 오류율(Bit Error Rate, BER)로, 비트가 오류로 도착할 확률.

P1​: frame이 오류가 없는 상태로 도착할 확률.

P2​: 오류 탐지 알고리즘을 사용할 때, frame이 하나 이상의 탐지되지 않은 비트 오류와 함께  도착할 확률.

P3: 오류 탐지 알고리즘을 사용할 때, frame이 하나 이상의 탐지된 비트 오류가 있지만 탐지되지 않은 비트 오류가 없는 상태로  도착할 확률.

 

single bit error의 확률이 증가하면, 프레임이 오류 없이 도착할 확률은 감소

프레임 길이가 길어질수록 포함된 비트 수도 증가하기 때문에, 오류가 발생할 확률 또한 높아짐

 

즉, 프레임의 길이가 길어질수록 오류 가능성도 증가하며, 오류 탐지 알고리즘의 사용 여부에 따라 프레임에서 오류가 탐지될 확률이 달라질 수 있다.

 

Error detection 과정

transmitter에서 n비트의 프레임을 보낸다고 해보자.

transmitter에서 내가 보내려는 데이터는 k비트가 된다. 거기에 추가적으로 함수를 사용해서 오류검출 코드 n-k비트가 추가되고 총 n비트가 receiver 쪽으로 보내진다. 총 n비트의 프레임을 받은 receiver는 다시 이 코드를 k비트와 n-k비트로 나누고 오류검출 코드를 만들 때 사용한 함수와 동일한 함수로 계산하여 값을 비교한다. 동일한 값이 나오면 에러가 아닌 것이다.

 

 

Parity check

가장 간단한 오류 검출 방법으로 데이터 블록의 끝에 패리티 비트를 추가하는 방식이다.

 

Even Parity

 

• 데이터의 1의 개수가 짝수가 되도록 패리티 비트를 추가
• synchronous transmission에서 사용

Odd Parity 

• 데이터의 1의 개수가 홀수가 되도록 패리티 비트를 추가
• asynchronous transmission에서 사용

짝수개의 비트가 오류로 바뀔 경우 패리티 체크가 오류를 탐지하지 못할 수 있음.(두 비트가 바뀌면 1의 개수가 여전히 짝수로 유지되어 탐지를 못할 수 있기 때문)

1이 홀수면 1 짝수면 0

c번은 초록색 부분에서 single bit error가 발생한다. 

d번처럼 동그라미 친 4개의 부분에서 에러가 발생하더라도 짝수개의 비트가 오류가 발생하는 상황이라 parity bit에서는 오류 탐지를 못할 수 있다. 

 

The internet checksum : IP, TCP, UDP 등에서 사용하는 오류 검출 코드

 

Ones-complement operation(1의 보수 연산) : 0을 1로, 1을 0으로 변환

Ones-complement addition(1의 보수 덧셈) : 두 숫자를 부호가 없는 binary 정수로 취급하여 서로 더함, 왼쪽 끝 비트에서 자릿수 올림이 발생할 경우, 이것을 합산해서 더함(end-around carry방식)

더했을 때 왼쪽 끝에서 자릿수 올림이 발생할 경우 end-around carry 방식으로 합산해서 더한다. receiver에서는 checksum값을 포함한 데이터 블록을 받고 동일한 계산을 한다. 모든 결과가 FFFF(비트가 1인값)가 된다면 오류가 없다.

checksum은 패리티 비트보다 뛰어나지만 CRC보다는 효과적이지 않다. 

 

CRC(Cyclic Redundancy Check, 순환 중복 검사) : 가장 흔하고 강력한 오류 검출 코드

 

transmitter는 k비트의 블록을 기반으로 n-k의 FCS(Frame Check Frame)를 생성함. 즉 k비트 블록에 n-k의 FCS를 더해서 프레임 n으로 만든다. 이 프레임은 3가지 방식으로 정확히 나눠지도록 만들어진다. 

• Modulo 2 Arithmetic : 2로 나누는 방식으로 XOR연산(같으면 0 다르면 1) 처리(나누려고하는 애의 차수만큼 0을 추가)
• Polynomials : 모든 값을 더미 변수 X와 이진 계수를 사용하여 다항식으로 표현, 나누기(나누려고 하는애의 차수만큼 곱하기)
• Digital Logic : CRC는 XOR gate와 shift register로 구성된 나눗셈 회로로 구현, shift register는 1비트가 저장된 장치의 연속이다. 일정한 시간마다 shift register의 모든 값이 동시에 이동하며, 전체 레지스터가 1비트씩 오른쪽으로 이동함. 그래서 고속의 실시간 오류검출 가능

쉽게 생각하면 FCS는 나머지 값이고, Polynomial은 나누는 값이다. 

차수가 있으면 데이터프레임은 1이고 없으면 0이다.

D(x) = 1010001101, P(x) = 110101, Q(x)  = 1101010110이다. R(x)가 0이 아니므로 에러가 발생

CRC는 error detecting에 focus 하고 있기에 어디서 에러가 발생했는지는 모름

 

Forward Error Correction : 오류를 검출하고 재전송 없이 데이터를 수정하는 방법

• 재전송이 필요 없음 - 전송 지연 최소화
• wireless application에는 부적합 - wireless link에서는 BER(Bit Error Rate)이 높기 때문에 재전송을 많이 해야 해서
• 비트 단위의 오류 수정 - 수신된 비트를 기반으로 찾고 수정
• 전송할 때 k비트 데이터 브록을 n비트 codeword와 매핑함(n > k) 추가된 비트들은 오류검출, 수정을 위한 정보를 가짐

FEC는 주로 신뢰성 있는 전송이 중요한 곳에서 사용하고 재전송이 어려운 무선 통신, 위성통신에서 사용

 

error detection에서는 보낼 때 n-k의 checksum을 붙여서 보냈지만 error correction에서는 새로운 codeword를 만들어서 보낸다. error detection에서는 수정불가능이지만 correction에서는 탐지하고 수정도 가능

 

Block code Principles

 

Hamming distance : 두 비트 사이에서 서로 다른 비트의 개수를 의미함. (ex. 1011과 1001의 해밍 거리는 1)

Redundancy of the code : (n-k)/k비트에 대한 중복된 비트의 비율(중복이 많으면 오류 검출과 수정 능력은 좋지만, 전송효율이 감소)

Code Rate : 데이터 비트와 전체 비트의 비율을 나타냄(k/n), 전송속도를 유지하기 위해 얼마나 많은 대역폭이 필요한지 알려줌(ex. 코드율이 1/2라면 2배의 전송용량 필요) 코드율이 낮으면 대역폭이 많이 필요하고 코드율이 높으면 효율은 높아지지만 오류 탐지와 검출은 저하됨