2-4. 데이터 통신 : 순환 중복 검사 CRC

오류 검출과 교정 기법 

 

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

- 오류 검출에 주로 사용되며 매우 강력하면서도 쉽게 구현할 수 있는 기술

- 인터넷에서 사용

- CRC개념

* FCS(Frame Check Sequence) : CRC과정을 통하여 만들어진 코드값

-> 원래 송신측에서 보내려던 전송 메세지에 FCS값을 포함하여 전송

 

- 동작과정

송신측)

- n비트 프레임을 (k+1)비트 생성 다항식(Generator Polynominal)으로 나누어 k비트 FCS(Frame Check Sequence)를 생성한다. 

    - 프레임 다음에 k비트 FCS를 추가하기 위하여 나누기 연산 전에 프레임을 k비트 왼쪽으로 이동한다.

    - 나누기 연산으로 생긴 K비트 나머지 (Remainder)가 FCS

- 송신 호스트가 네트워크를 통해 실제 전송할 데이터는 프레임과 FCS이며 총 (n+k)비트이다.

 

수신측)

- 수신 호스트는 송신 호스트가 보낸 (n+k)비트 데이터를 받는다.

- 수신한 (n+k)비트 데이터를 생성 다항식으로 나눈다.

    - 나머지가 '0'이면 오류 발생이 없는 것으로 판단

    - 나머지가 '0'이 아니면 오류가 발생한 것으로 판단

 

CRC 동작원리

- 표기 

M(x) : 사용자가 전송하려고 하는 n비트 데이터

G(x) : 송수신측 간에 합의된 (k+1)비트 생성 다항식 (다항코드 100101 = 생성다항식 x^5 + x^2 + 1 -> 계수값)

R(x) : k비트 나머지(FCS)

Q(x) : 몫

 

- CRC는 모듈로-2(modulo-2) 연산사용 : exclusive-OR 연산

* modulo-2연산과 exclusive-OR연산은 동일

출처 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=seo0511&logNo=10131936944

-> 두 개의 인풋값이 다를 때 결과값은 0, 같을 때 1

 

 

- 다음과 같은 등식의 성립

     -> FCS값을 넣기 위해 데이터를 k비트만큼 왼쪽 이동을 시켜줘야하기 때문에 2^k를 곱해줌

 

- 송신측에서 실제로 전송되는 데이터 

 

- 데이터가 올바르게 수신되었다고 가정하고, 수신측에서 G(x)로 나누어 보면 다음과 같다.

    -> 최종적으로 Q(x)만 남는 이유는 모듈로-2 덧셈에서 같은 수를 더하면 0이 되기 때문

- 위의 식은 수신측에서 받은 데이터를 G(x)로 나누었을 때 나머지가 없으면(0) 데이터가 올바르게 수신되었다는 것을 의미

 

- FCS 계산법

-> 가장 왼쪽이 1이면 몫은 1, 나머지는 데이터101, 가장 왼쪽이 0이면 몫은 0, 나머지는 000-> FCS = 11 

 

- 국제 표준으로 사용되는 생성다항식 예

 

CRC 예시

- 송신측

*데이터100101 + 000 (FCS=생성다항식의 비트 -1만큼 0으로 채워놓음)

 

- 수신측