해밍코드와 crc코드 레포트

본문내용

터가 10001101이라 할 때 번호를 부여하여 다항식으로 표현하면 (그림 4)와 같다.
그림 4을 보면 알 수 있듯이 각 자리에 1이 들어있는 자릿수를 X의 지수로 정한다.
그림 4
3. CRC 비트를 만드는 방법
우선 알아 두어야 할 것이 있다. CRC에 서 사용하는 모든 연산은 캐리(Carry)가 없는 Modulo-2 연산이다. 즉 윗자리로 올리거나 빌리지 않는다는 것이다. 이러한 연산방법을 아래에 보였다
1111 1111
-1001 +1001
0110 0110
위와 같이 두 연산의 결과는 같게 나온다. CRC의 제수로 나누는데 있어 사용되는 연산이 바로 이러한 연산이다. 그럼 이를 염두에 두고 그림 5를 보자
그림 5
그림5에 대한 설명을 하자면,
- 연산과정에서 산출되는 CRC 비트의 길이를 n이라 했을 때 제수는 n+1이 된다.
- 제수는 송신측과 수신측의 합의하에 정의된다.
- 전송하고자 하는 데이터 뒤쪽에 n개의 0을 붙인다.
이제 연산과정과 CRC의 추가에 대하여 그 과정을 살펴보자.
I 그림4와 같이 제수와 원시데이터에 n개의 0을 삽입한 값을 나눈다.
II. 이렇게 나눈 나머지 R을 n개의 0을 삽입한 자리에 각각 대체시킨다.
III. 그렇게 나온 값 10001101110이 최종 데이터가 되는 것이다.
IV. 그럼 이 값을 프레임에 실어서 전송한다.
4. 에러 검출 방법
송신측이 제수를 이용해 CRC를 산출해 내는 방법과 유사하게 연산함으로써 수신측은 데이터의 에러 유무를 판단할 수 있다. 그림 6는 그 연산과정을 보여준다.
그림 6
이제 연산과정에 대하여 살펴보자.
I. 우선 수신측은 전송받은 데이터를 송신측과 합의된 제수로 나눈다. 역시 Modulo-2연산으로 이루어진다.
II. 연산결과 나머지가 0이 된다면 정확한 값을 전송받은 것이 된다. 즉 그림 5는 나머지가 0이 되었으므로 정확한 값을 전송받은 것이다.
III. 그렇지 않다면 에러가 있으므로 재전송 요청을 하는 것이다.
이렇게 계산한 값을 삽입한다 해도 생성다항식의 n배의 에러가 발생하는 경우 는 나머지가 역시 0이 나오기 때문에 에러 검출이 불가능 하다.
5. 하드웨어로 구성된 CRC
전형적인 데이터 통신 하드웨어 구성에서 계산된 BCC는 쉬프트레지스터에 축적된다. 그리고 이 레지스터의 구성은 CRC 코드를 생성하게 되어있다. 레지스터 중에 있는 각 구분은 생성다항식의 등급과 같으며 따라서 Exclusive-OR 요소들의 수도 또한 그 다항식과 관계되는 수이다. 다음의 예제를 보자.
CRC-12
동기방식에서 사용하는 CRC-12는 6비트 캐릭터에 사용하며 이때의 BCC는 12비트가 된다. 생성다항식은 X12+X11+X3+X2+X+1 = (X+1)(X11+X2+1)이다. 이 생성다항식은 앞서 보았던 제수인데, 이것을 제수로 표현하면 생성다항식의 각각의 차수의 값이 1인 비트열이 된다. 즉 제수는 1100001000111(2)로 표현된다. 이것은 12비트 길이까지의 집단 에러를 검출할 수 있으며 또한 12비트보다 큰 집단에러의 경우는 99%이상의 확률로 에러를 검출할 수 있다. 그림7 을 보자
그림 7
- 최초의 레지스터는 모두 제로(‘0’)로 해둔다.
- 12비트 데이터위드(‘1’에 연속하여 11개의 ‘0’이 온다)가 레지스터의 입력이 된다.
- 쉬프트를 행하기 전에 최초의 데이터 비트(1)를 레지스터의 LSB(0)와 Exclusive-OR 회로와 연산이 되어 각 레지스터에 삽입된다.
- 이러한 과정이 12비트의 데이터 비트에 대하여 반복된다.
앞서 살펴본 계산방식과 달리 하드웨어를 이용한 CRC의 구현은 컴퓨터가 가장 빨리 할 수 있는 연산인 쉬프트 연산을 이용하고 있다. 이는 상당한 성능향상을 기대할 수 있다.
CRC-CCITT
CRC-CCITT는 유럽 시스템들의 표준 BCC로서 널리 이용되고 있는 방식이다.
이것을 8비트 캐릭터로 조작하는 경우는 BCC 축적은 16비트이다. 생성다항식은 X16+X12+X5+1이다. 이 방식에 의하면 집단 에러의 검출은 최대 16비트 길이까지 된다. 그림 7은 16비트의 데이터워드(‘1’에 연속하여 15개의 ‘0’이 온다.)를 사용한 BCC 축적을 표시하고 있다.
그림 8
CRC-16
CRC-16은 8비트 캐릭터용의 동기방식에 응용되고 이 BCC 축적은 16비트가 된다. 또한 생성다항식은 X16+X15+X2+1이다. 집단에러검출은 최대 16비트길이까지 행하여진다. 또한 에러의 집단이 16비트보다 큰 경우는 99%이상의 확률로 에러검출이 가능하다. 그림8에 16비트 데이터워드를 사용한 BCC 축적을 보였다.
그림 9
이상에 서술한 CRC의 예는 송신순서로 이용될 BCC 축적을 보여주고 있다. 그림9는 BCC와 함께 수신된 데이터를 수신측에서 처리하는 경우의 BCC 축적을 보이고 있다.
그림 10
여기에서 데이터 및 BCC 처리는 그림 8과 동일하다. 즉 CRC-16을 이용한 축적이다. 그림 9에 있어서 축적처리는 쉬프트번호 16까지 그림8에 효시한 경우와 같다. 그림9에서 쉬프트 번호 17부터는 BCC가 데이터 입력에 LSB를 선두로 보내는 것으로부터 개신된다. 바르게 전송된 BCC의 결과는 처리 후에 모두 ‘0’으로 되어 BCC 레지스터에 나타난다. 실제로는 송신 BCC와 수신측에서 처리한 것을 비교한 것이 된다. 비교결과가 올바FMS 경우의 나머지는 ‘0’, 즉 BCC 레지스터의 내용은 모두 ‘0’이 된다.
CRC는 전체 블록검사를 할 수 있으며 이진 나눗셈을 기반으로 하므로 패리티 검사보다 효울적이고 에러 검출 능력이 뛰어난 방법이다.
CRC(Cyclic Redundancy Check)
우리가 배우는 CRC는 통신 용어라 인식되지만 실생활에서 CRC는 상당히 많은 부분에서 사용되고 있다. 통신을 제외한 다른 분야 중 가장 두드러지는 곳은 압축 프로그램에서의 사용이다. 압축된 데이터를 압축 해제할 때 CRC 검사를 수행함을 우리는 자주 경험훌 수 있다. 압축 프로그램에서의 CRC 사용은 압축 데이터가 디스크 내에서 손상됨을 인식할 수 있도록 도와준다.
출처 - 디지털 공학 김학수 저
데이터 통신 정진욱, 한정수 지음
네이버 백과사전

키워드

해밍,   crc,   코드,   에러검출,   패리티코드,   패리티,   리처드 웨슬리 해밍,   Richard Wesley Hamming