Home  |   방명록 2019-03-19 (화) 
Untitled Document
  S e a r c h
M e n u
프로그램
개발자료
고전음악실
대청마루
집주인
비망록
갤러리
  B o a r d
게시판
Untitled Document
개발자료 Software / Hardware 개발 관련 정보

CRC : CRC-16, CRC-32에 대한 설명과 구현


CRC-16/32

 

CRC(Cyclic Redundancy Check)는 시리얼 전송에서 데이타의 신뢰성을 검증하기 위한 에러 검출 방법의 일종이다.

간단한 에러 검출방법으로는 parity 비트에 의한 방법과 check-sum에 의한 에러 검출 방법이 있지만 parity 비트에 의한 방법은 데이타 중에 한꺼번에 2비트나 4비트가 변하게 되면 검출을 할 수 없고, check-sum에 의한 방법은 한 바이트에서 +1, 다른 바이트에서는 -1로 에러가 생기는 경우만 해도 에러는 검출 되지 않는다. 즉, 이들 방법으로는 에러를 검출해 낼 수 있는 확률이 대단히 낮다.

CRC에 의한 방법은 높은 신뢰도를 확보하며 에러 검출을 위한 오버헤드가 적고, 랜덤 에러나 버스트 에러를 포함한 에러 검출에 매우 좋은 성능을 갖는 것을 특징으로 한다.

이러한 CRC 방법으로 보통 2가지 종류가 사용 되는데, 원칩 마이크로 프로세서와 같이 간단한 용도에서는 CRC-16 이 사용되고, 이보다 더욱 정확한 에러 검출이 필요한 경우에는 CRC-32를 사용한다.

ZIP,ARJ,RAR 과 같은 압축 프로그램이나 플로피 디스크 등의 데이터 검증 용도에 널리 사용되고 있다.

* CRC 검증의 에러 확률 p = 2-k (여기서 k는 CRC 비트수)
예를들어 CRC16의 경우 에러 확율은 p = 2-16 = 1 / 65536 = 0.0000152587890625 = 0.0015%
반대로 데이터의 신뢰성은 1 - p = 0.9999847412109375 = 99.9984 %

 

기본 원리

n 비트의 주어진 정보가 있을때, 이를 k 비트 만큼 자리를 올리고 미리 약속한 k 비트의 키 값으로 나누면 r 비트의 나머지가 남게 된다. 송신측에서는 원래의 정보 비트를 k 비트 자리 올린 것에 r 비트의 나머지를 더해서 n+r 비트의 데이타를 만들어 보낸다.
수신측에서는 수신된 n+r 비트의 데이타를 키 값으로 나누어 보고 나머지가 정확히 0 이 되는지를 검사하면 된다.

이 때 k 가 16 비트이면 CRC-16, 32비트이면 CRC-32 가 되고 키 값으로는 수학자 들에 의해 정해진 값을 주로 사용한다.
CRC-16 에는 0x8005, CRC-32 에는 0x04c11db7 이 많이 사용된다. 그리고 r 비트의 나머지를 Frame Check Sequence(FCS)라고 부른다.

여기서 CRC 계산에 사용되는 modulo-2 연산의 세계를 살펴보자.

CRC 계산시의 사칙연산은 carry를 고려하지 않는다.
1 + 1 = 0 (carry는 생각하지 않음)
0 - 1 = 1
덧셈 연산은 뺄셈 연산과 결과가 같으며 XOR 연산과도 같다.

다항식 표현 방법을 통해 CRC 계산 방법을 살펴보자.

(1) 2진 다항식으로 표시

예) 비트열 101 --> 다항식 x2 + 1

정보 다항식: 데이터 비트열의 다항식으로 P(x) = pn xn-1 + ... + p3x2 + p2x1 + p1
CRC 다항식: CRC 생성을 위한 다항식으로 G(x) (미리 정해진 키 값)
몫: Q(x)
나머지: R(x)
전송 데이타: T(x)

(2) CRC 계산 방법

P(x)를 k 비트 만큼 자리를 올리고( P(x)에 xk를 곱하는 것과 동일) G(x)로 나누면

xk P(x) = Q(x)*G(x) +/- R(x) 이다.

(k는 CRC 다항식의 최고 차수)

R(x) = dk xk-1 + .. + d2x1 + d1 ( R(x)의 최고 차수는 k-1)

비트열 dk ... d2 d1 을 FCS(Frame Check Sequence) 라 함

위 식에서 xk P(x) + R(x) 는 Q(x)*G(x) 와 같다.

즉, xk P(x) + R(x) 는 G(x)의 배수이므로 G(x) 로 나누면 나머지가 0 임을 알 수 있다.

결과적으로 전송되는 데이터 비트열 : pn ... p3 p2 p1 dk ... d2 d1

즉, 전송 T(x) = xk P(x) + R(x)

 

예) 데이터 비트열 110011 즉 P(x) =x5+x4+x1+x0, CRC 다항식G(x) = x4+x3+1, 즉 11001일 경우 FCS와 전송되는 비트열은?

xkP(x) = x4 (x5 + x4 + x1 + 1) = x9 + x8 + x5 + x4, 비트열로 표시하면 1100110000

                   100001
          ____________
11001 | 1100110000
            11001
          ____________
                     10000
                     11001
          ____________
                       1001    

xkP(x) = Q(x)G(x) - R(x)에서

Q(x) = x5 + x0 이므로,

R(x) = x3 + x0, ---> FCS는1001

따라서 전송되는 비트열 1100111001

 

연산의 최적화

CRC의 계산은 일반 나눗셈 명령을 이용해 구현할 수 없다. 1비씩 shift 하면서 XOR 연산을 통해 나머지를 구해야 한다.
하지만 정보 비트에 대해 하나하나씩 연산을 하는 것에는 분명 속도 개선의 여지가 있다.
실제 계산 시에는 모든 바이트에 대해 CRC 다항식에 대한 CRC값을 계산해 표로 만들어 두고 들어오는 데이타를 인덱스로 삼아 계산값을 바로 얻는 방법을 사용 한다.

CRC-16 C소스 : crc16h.c
CRC-32 C소스 : crc32h.c

8051 어셈블리 CRC-8 소스 : 8051crc8.zip
8051 어셈블리 CRC-16 소스 : 8051crc16.zip

2004-06-14 [조회: 32767]

이전글: TWAIN : 스캐너등 이미지장치 인터페이스 API 규약
다음글: I2C : Inter IC Bus

목록보기
궁금...
CRC16의 경우 에러 확율은 p = 2-16 = 1 / 65536 = 0.0000152587890625 = 0.0015%
반대로 데이터의 신뢰성은 1 - p = 0.9999847412109375 = 99.9984 %
--------------------------------------
이 부분의 말이 이해가 가질 않네요.
저런 계산은. 16비트가 잇고. 각 비트당 에러 확률이 0.5이며. 이 비트열 모두가 에러날 확률이 0.0015%라는 말 아닌가요? 어째서 저렇게 되는건지..
차라리. 전송단계에서 한 개의 비트가 에러날 확률이 0.1이며 CRC-16이 에러날 확률은

한 개의 비트가 정상일 확률 0.9.
16비트 모두가 정상일 경우는 (0.9)^16이며
CRC-16가 에러날 경우는 1 - (0.9)^16라는게 말이 되어보여서요.

그냥 예를 간단히 든거라서 의미가 크지 않는 말인가요? 2018-11-25 13:11
×
 
이름 암호
(스팸 방지용)오늘의 날짜를 숫자만으로 입력하세요.(예: 12)

비밀번호
목록보기
 
Copyright ⓒ 2019 All Rights Reserved.