순환 중복 검사 (CRC)

jino630·2021년 6월 16일
0

hash

목록 보기
5/6

출처 - 위키


순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.

데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.

CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.

순환 중복 검사를 계산하는 과정은 하드웨어적 방식과 소프트웨어적 방식을 생각할 수 있다. 하드웨어적 방식을 말할 때, 직렬데이터를 계산하는 것이 단순하다. 통신시스템에서 프로토콜 계층에서 물리층에 가까울수록 하드웨어 접근을 그리고 상위계층에 가까울 수록 소프트웨어적인 방식이 적용된다.

통신시스템에서 물리계층에 가까울수록 직렬데이터를 사용하는 경향이 있다. 따라서 하드웨어적 계산방식을 사용한다. 전송라인은 거의 직렬 데이터이기 때문이다. 이런 경우 순환 중복 검사는 비트단위의 입력에 대한 출력을 얻는다. 논리 회로를 만들면 간단해진다. 그러나 높은 계층으로 갈수록 병렬데이터(octet 단위, 8비트)를 사용한다. 이런경우는 소프트웨어적 접근으로 주로 바이트 단위로 계산한다. 순환 중복 검사는 결국 비트단위 입력에 대한 각 비트별 XOR 연산이므로 한 바이트 계산도 소프트웨어적 고속계산에 한계가 있다. 이런 경우 주로 미리계산을 한 테이블 형태를 사용한다.


CRC 계산 예
(출처 - 위키)

다항식 : x^3 + x + 1 => 1011 (4비트)
원본 데이터 : 11010011101100

1단계 데이터 준비

원본 데이터에 (다항식 비트수 -1) 만큼의 0을 추가한다.

원본 데이터 + (다항식 비트수 - 1)개의 0 : 11010011101100000

2단계 검증값 계산

데이터의 젤 앞자리 가 1비트인 곳에 다항식 비트 1011을 맞춰두고 xor 연산을 계속한다.

1 1010 0111 0110 0000
1 011

0 1100 0111 0110 0000

1100 0111 0110 0000
1011

0111 0111 0110 0000

0111 0111 0110 0000
 101 1
 

0010 1111 0110 0000

0010 1111 0110 0000
  10 11

0000 0011 0110 0000

0011 0110 0000
  10 11

0001 1010 0000

0001 1010 0000
0001 011

0000 1100 0000

1100 0000
1011 0000

0111 0000

0111 0000
 101 1

0010 1000

0010 1000
0010 11

0000 0100

드디어 결과값인 100을 얻었다!

해당 100 비트값이 검증값이 된다!

3단계 검증

원본 데이터인 11010011101100 값에 100 비트를 더해서 11010011101100100을 만든 후, 다항식 비트였던 1011 을 2단계와 같은방식으로 XOR 해가면 된다. 결과 값이 0이되면 CRC 체크 통과!

0개의 댓글