CRC 연산 방법 CRC-8 CRC-16

CRC연산방법

안녕하세요.
오늘은 DATA 신뢰성을 보장하기 위한 에러 검출방법 중 한 가지인 CRC 연산에 대해 소개해드립니다.

 

 

◈CRC (순환중복검사) vs ECC(오류정정코드)

 

CRC의 약자는 Cyclic Redundancy Check 입니다. Redundabcy는 여유 또는 과잉이라는 뜻인데 CRC 연산은 원래의 DATA에 추가되는 BIT을 전송하여 다항식(Polynomial)을 통해 오류를 검출하는 방식입니다.

 

DATA는 항상 송신자와 수신자가 있으며 신뢰성이 매우 중요합니다. DATA신뢰도는 단순 송수신단계의 무결성과 저장된 DATA의 무결성 두 가지 측면에서 접근할 수 있습니다.

먼저 저장된 DATA의 무결성은 메모리 업체에서 보증하게 되어있습니다. 메모리 업체인 삼성전자,하이닉스,마이크론 등은 개별적인 Test Process를 통해 초기 Cell Error를 검출하지만 서버와 같은 고도의 신뢰성이 요구되는 System에서는 메모리 저장장치의 신뢰성 보증을 위한 보조장치로 ECC(Error Correction Code)가 활용되고 있습니다.

ECC 동작원리는 위키피디아 사이트를 통해 참조하실 수 있습니다.

 

※ECC 원리 위키피디아

Error correction code - Wikipedia

 

데이터의 신뢰도 유지가 필요한 두 번째 케이스는 송신자를 떠난 데이터가 수신자에게 도달하기까지 과정입니다. Data 전송 속도를 높이기 위해서는  동작 주파수를 높여 빠르게 데이터를 전송하거나 전송선로를 증가시켜 많은 양의 데이터를 동시에 전송해야 합니다. 동작주파수 증가는 기술적 한계로 난이도가 매우 높지만 전송선로 확대는 비용과 스페이스만 확보된다면 비교적 쉽게 적용할 수 있습니다.

 

전송선로가 많아지면 송신자를 떠난 데이터가 수 많은 전송선로를 통해 이동되는 동안 간섭과 노이즈로부터 발생될 수 있는 여러 가지 돌발 에러 가능성에 노출됩니다. 이러한 다중 전송선로에서 발생하는 에러에 대해 추가 데이터(Redundancy)와 다항식(Polinomial) 연산을 통해 검출하는 방법이 CRC입니다.

 

 

◈CRC 원리

 

CRC는 n개의 비트로 구성되어 있습니다. 1에서 64비트까지 다양한 CRC 연산법은 패리티 비트로 사용되는 1비트, ATM이나 메모리, 정보통신망에 사용되는 8비트, CDMA에 사용되는 30비트, ECMA-182에 사용되는 64비트가 대표적입니다. 고사양의 높은 신뢰도와 빠른 속도를 원하면서 추가 전송선로 활용이  용이하다면 높은 비트의 CRC 비트를 사용하게 됩니다.

 

CRC 연산은 CRC 생성 비트수(n)와 준비된 다항식을 통해 얻어지는 Divisor(n+1)을 활용하여 원본 데이터와 XOR 연산(나누기)을 통해 진행됩니다.

 

ATM과 ISDN에 적용 중인 CRC-8 CCITT(Consultative Committe on International Telegraphy and Telephony 국제전신전화 자문위원회 -ITU-T International Telecommunication Union)를 예로 CRC 연산의 원리를 알아보겠습니다.

 

※CRC-8 CCITT
①CRC 비트수 = 8
②다항식 = 0x83, X^8 + X^2 + X^1 + 1
③Divisor = 100000111

 

CRC-8 CCITT 방식의 CRC는 8비트의 CRC 비트를 가집니다. 사전에 준비된 다항식은 Hexa Code로 0x83, X^8 + X^2 + X^1 + 1로 표현되는데 이 숫자의 의미는 16진수 Hexa 0x83을 2진수 Binary 1000 0011로 변경한 후 각각의 자릿수를 제곱한 형태로 표현한 후 Binary Code와 곱해서 만들어집니다.

 

HEX	8				3				+ 1
BIN	1	0	0	0	0	0	1	1	1
다항식	X^8	X^7	X^6	X^5	X^4	X^3	X^2	X^1	1
곱셈결과 BINx다항식	X^8						X^2	X^1	1
최종결과	X^8 + X^2 + X^1 + 1

 

 

반응형

 

◈CRC 연산 방법과 실제 송수신 방법

 

지금부터는 CRC-8 CCITT 방식을 활용하여 실제 CRC 연산 방법과 데이터 송수신하는 과정을 살펴보겠습니다.

 

◆데이터 전송 위치의 CRC 연산
 - 원본 데이터 문자 "A"를 ASCII CODE로 전송할 경우
    "A" ASCII CODE = 0x41 = Binary 1000001

 

※데이터 전송자(송신자) 기준 CRC-8 CCITT 연산과정

 

①CRC 전송을 위해서는 원본데이터 뒷부분에 8개의 Redundancy 0을 추가합니다.

②Divisor와 Redundancy 0이 추가된 가공 데이터를 앞부분부터 XOR 연산합니다.

③XOR 연산 결과에서 앞자리 0을 제외한 후 Divisor와 동일한 자릿수만큼 XOR 연산을 반복합니다.

④최종 Data가 Divisor 자릿수보다 작아지게 되면 최종 8비트가 CRC Code가 됩니다.

⑤데이터 전송자는 원본데이터와 계산된 CRC CODE를 함께 전송합니다.

CRC전송연산

 

 

 

※데이터 수신자 기준 CRC-8 CCITT 연산과정 (에러 없는 경우)

 

①수신된 원본 데이터의 뒷부분에 같이 전송된 CRC CODE를 추가합니다.

②Divisor와 Redundancy 0이 추가된 가공 데이터를 앞부분부터 XOR 연산합니다.

③XOR 연산 결과에서 앞자리 0을 제외한 후 Divisor와 동일한 자릿수만큼 XOR 연산을 반복합니다.

④최종 Data가 Divisor 자릿수보다 작아지게 되는 순간 0을 가지면 에러가 없는 Data입니다.

 

CRC수신연산

 

동일한 방법으로 CRC-16, CRC-32, CRC-64까지 모두 연산할 수 있습니다. 그렇다면 만약 수신된 데이터에 오류가 있을 경우 CRC CODE은 어떻게 발생될까요?

 

※데이터 수신자 기준 CRC-8 CCITT 연산과정 (에러 발생 경우)

 

전송된 데이터에 오류가 있을 경우는 어떻게 되는지 동일하게 수신자 기준으로 CRC 연산을 진행해 본 결과 CRC Code가 0이 아닌 0xD로 정상적으로 오류 검출이 가능했습니다. 오류가 검출되면 수신자는 송신자에게 재전송을 요청하는 과정을 통해 에러를 수정할 수 있습니다.

 

CRC수신에러

 

지금까지 데이터 전송선로의 신뢰성 보증을 위한 CRC 연산에 대해 알아보았습니다. 다음 시간에는 위와 같은 CRC 연산을 실제 회로로 구성하는 방법에 대해 소개해 드리겠습니다. CRC 연산 관련 조금 더 많은 사례를 살펴보고 싶다면 아래 위키백과 링크를 통해 학습하시길 추천드립니다.

 

※위키백과 CRC 연산바로가기

순환 중복 검사 - 위키백과, 우리 모두의 백과사전