CCITT CRC-16

디지탈 데이터를 송수신하는 과정에서 데이터가 오류없이 정상적으로 수신되었는지 확인하기 위해 흔히 CRC(Cyclic Redundancy Code)를 사용한다.

CRC에는 다양한 종류가 있는데, 대표적인 것이 CCITT CRC-16이다. 이것은 전송데이터를 특정 다항식을 이용하여 나눗셈을 수행하고 남은 나머지 16비트를 전송데이터의 뒷부분에 추가적으로 전송하는 것을 의미한다. 수신측에서는 동일한 다항식으로 나눗셈을 수행하여 나머지가 특정값이면 수신데이터에 오류가 없다고 추정하는 것이다.

CCITT CRC-16의 다항식은 다음과 같다.

 또는 0x1021

위 다항식의 좌측을 이진수로 표시하면 b’10001000000100001로 표기할 수 있으며, 우측은 이를 16진수로 표기한 것으로 MSB는 항상 1이기 때문에 이를 생략하고 16비트만 표기한 것이다. CRC의 계산은 전송하고자 하는 2진 데이터에 을 곱하고, 즉 b’10000000000000000을 곱하고 이를 위의 다항식으로 나누어서 나머지를 데이터에 이어서 전송하는 것이다. 수신측에서는 수신한 데이터를 위의 다항식으로 나누어 나머지가 0이면 수신데이터에 오류가 없는 것이고 0이 아니면 데이터에 오류가 발생하였다는 것을 의미한다. 나누는 과정에서는 일반적인 산술 나누기와 달리 각 비트 간에 xor을 수행한다. 이 과정을 간단하게 설명하기 위해 3비트의 CRC를 계산하는 과정을 살펴보면 다음과 같다. 우선 다항식을 b’011로 하고 전송하고자 하는 데이터를 b’11010011101100 라고 한다면 송수신부의 CRC 계산 과정은 다음과 같다.
- 송신부


- 수신부(오류가 없는 경우)



- 수신부(오류 포함)
그런데, 위의 CRC를 계산하는 과정은 shift register를 이용하여 다음과 같이 쉽게 구현할 수 있다. 여기서 + 는 modulo 2 더하기를 의미한다. 즉 2 비트를 xor을 취하면 된다.


이제 다시 CCITT CRC-16 다항식을 적용하여 보면 회로는 다음과 같이 구성할 수 있다.

 


그리고 인터넷에서 CCITT CRC-16을 찾아보면 규격이 다음과 같이 정의 되어 있다고 나온다. 

Width = 16 bits
Truncated polynomial = 0x1021
Initial value = 0xFFFF
Input data is NOT reflected
Output CRC is NOT reflected
No XOR is performed on the output CRC

위의 글을 보면 레지스터의 초기 값을 모두 1로 해야 한다는 것을 알 수 있고, CRC 계산 결과를 그대로 전송해야 된다. 그런데 또 인터넷에서 그냥 CRC-16 계산기를 찾아보면 다음과 같은 다양한 CRC-16 표를 볼 수 있다. 이 표에서 Poly는 다항식, Init는 레지스터 초기값, RefIn은 입력 비트의 순서를 반대로 한다는 것이고, RefOut 출력 비트의 순서를 반대로 한다는 뜻이다. 그리고 XorOut은 계산된 CRC 값에 대해 표에 나와 있는 값과 xor을 취해서 전송한다는 뜻이다. 즉 0xFFFF라고 표시 되어 있으면 계산된 CRC 비트 모두 not을 취해서 전송하여야 한다.

 

Algorithm

Result

Check

Poly

Init

RefIn

RefOut

XorOut

1

CRC-16/CCITT-FALSE

0x29B1

0x29B1

0x1021

0xFFFF

false

false

0x0000

2

CRC-16/ARC

0xBB3D

0xBB3D

0x8005

0x0000

true

true

0x0000

3

CRC-16/AUG-CCITT

0xE5CC

0xE5CC

0x1021

0x1D0F

false

false

0x0000

4

CRC-16/BUYPASS

0xFEE8

0xFEE8

0x8005

0x0000

false

false

0x0000

5

CRC-16/CDMA2000

0x4C06

0x4C06

0xC867

0xFFFF

false

false

0x0000

6

CRC-16/DDS-110

0x9ECF

0x9ECF

0x8005

0x800D

false

false

0x0000

7

CRC-16/DECT-R

0x007E

0x007E

0x0589

0x0000

false

false

0x0001

8

CRC-16/DECT-X

0x007F

0x007F

0x0589

0x0000

false

false

0x0000

9

CRC-16/DNP

0xEA82

0xEA82

0x3D65

0x0000

true

true

0xFFFF

10

CRC-16/EN-13757

0xC2B7

0xC2B7

0x3D65

0x0000

false

false

0xFFFF

11

CRC-16/GENIBUS

0xD64E

0xD64E

0x1021

0xFFFF

false

false

0xFFFF

12

CRC-16/MAXIM

0x44C2

0x44C2

0x8005

0x0000

true

true

0xFFFF

13

CRC-16/MCRF4XX

0x6F91

0x6F91

0x1021

0xFFFF

true

true

0x0000

14

CRC-16/RIELLO

0x63D0

0x63D0

0x1021

0xB2AA

true

true

0x0000

15

CRC-16/T10-DIF

0xD0DB

0xD0DB

0x8BB7

0x0000

false

false

0x0000

16

CRC-16/TELEDISK

0x0FB3

0x0FB3

0xA097

0x0000

false

false

0x0000

17

CRC-16/TMS37157

0x26B1

0x26B1

0x1021

0x89EC

true

true

0x0000

18

CRC-16/USB

0xB4C8

0xB4C8

0x8005

0xFFFF

true

true

0xFFFF

19

CRC-A

0xBF05

0xBF05

0x1021

0xC6C6

true

true

0x0000

20

CRC-16/KERMIT

0x2189

0x2189

0x1021

0x0000

true

true

0x0000

21

CRC-16/MODBUS

0x4B37

0x4B37

0x8005

0xFFFF

true

true

0x0000

22

CRC-16/X-25

0x906E

0x906E

0x1021

0xFFFF

true

true

0xFFFF

23

CRC-16/XMODEM

0x31C3

0x31C3

0x1021

0x0000

false

false

0x0000


앞에서 설명한 규격과 위의 표를 보면 일반적인 CCITT CRC-16은 표에서 1번에 해당한다. 그런데 어떤 시스템에서는 위 표에서 11번을 따른 다는 것을 CRC 계산 결과를 통해 알 수 있다. 그리고 11번에 따른 데이터 스트림을 수신부에서 CRC 부분까지 CRC를 계산하여 보면 오류가 발생하지 않았을 때 x’1d0f가 레지스터 값이다. 따라서 수신부에서 CRC 계산을 수행하여 레지스터에 x’1d0f가 남아 있다고 하면 전송이 정상적으로 이루어 진 것이다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

이미지
 FPGA 실습(5) 5. Manchester Code  맨체스터 코드는 앞절에서 설명한 SDLC의 NRZ 모드에서 별도의 클럭을 사용하지 않고 데이터에서 클럭을 추출하기 위해 사용하며, 멘체스터 코드의 코딩 방식은 다음 그림과 같다. 5.1. 송신부(Encoder) 송신부는 앞의 그림에서 살펴본 바와 같이 CLK과 NRZ를 XOR을 취해서 출력하면 된다. 그런데 CLK과 NRZ를 XOR을 취하면 서로의 위상차로 인해 glitch가 발생할 수 있으므로 전송 속도보다 아주 빠른 클럭으로 래치해서 출력하는 것이 좋다. 5.2. 수신부(Decoder) 수신부는 입력되는 맨체스터 코드로부터 데이터와 클럭을 추출하여 출력하여야 한다. 먼저 전송속도보다 아주 빠른 클럭을 이용하여 전송속도에 맞는 클럭을 생성하기 위한 카운터를 구동하여 기본적인 클럭을 생성한다. 예를 들어 전송 속도가 1Mbps인데 회로에서 사용하는 클럭이 128MHz 클럭이라고 한다면 카운터 값이 63이 된뒤 다시 0으로 돌아가도록 구성하여 카운 터값이 0일 때 반전이 일어나도록 하여 1MHz의 클럭을 생성한다. 그리고 입력되는 데이터를 전송속도 보다 아주 빠른 클럭(예: 128MHz)으로 래치를 해서 rising edge와 falling edge를 검출하고 rinsing edge나 falling edge에서 앞에서 언급한 카운터를 0으로 셋팅하여 주기를 맞춘다. 그리고 클럭 주기의 1/2되는 지점에서 sample 클럭을 생성하여 sample 클럭에서 입력되는 데이터를 래치하여 이전데이터와 비교한다. sample 데이터가 b’01이면 1로 디코딩하고 데이터가 b’10이면 0으로 디코딩하며 출력 클럭을 반전시킨다. 만일 데이터가 b’00이거나 b’11이면 디코딩하지 않으며 출력 클럭을 그대로 유지 한다. 이렇게 하면 입력되는 데이터로부터 데이터와 클럭을 추출하여 NRZ 데이터를 출력할 수 있다. 다음 그림은 Loopback되는 맨체스터코드로부터 NRZ 데이터와 출력 클럭을 시험 한 결과이다...
자세한 내용 보기
이미지
 FPGA 실습(4) 4. SDLC 구현 SDLC(Synchronous Data Link Control)를 구현하여 본다 SDLC를 구현하기 위해 SDLC의 프레임의 구조를 먼저 살펴보고 SDLC 프로토콜을 구현하기 위한 IP를 제작하는 과정과 통합하여 시험하는 과정을 기술한다. 4.1 SDLC 프로토콜 개요 4.1.1 SDLC 프레임 - Flag : b’0111110의 값으로 구성되면 프레임의 시작과 끝을 나타낸다. 데이터가 없는 구간은 All High로 구성되거나 b’01111111이 반복될 수 있다. - 규격 확인이 필요한 부분임. HW 구현 관점에서는 b’01111111이 반복되는 구조가 구현을 간단히 할 수 있다. 또한 Flag이외에 필드에 b’01111110 값이 들어가면 프레임 오류가 발생할 수 있기 때문에 송신측에서는 1이 5번 반복되면 ‘0’을 하나 삽입한다. 이를 bit stuffing이라고 하며, 수신측에서는 Flag이외의 필드에서 1이 5번 반복되는 것을 발견하면 뒤에 따라오는 ‘0’을 제거하고 데이터를 처리하여야 한다. - Address/Control 부분은 당초 SDLC 규격을 만들 때 각종 토폴로지와 통신 프로토콜을 정의하기 위해 삽입된 부분으로 생각되며 우리가 흔히 사용하는 Point-to-point의 토폴로지에서는 Source Address(1byte), Destination Address(1 byte), Message ID(1byte), Data Length(2 byte)등으로 흔히 구성되며, 이는 프로토콜 정의할 때 결정하면 된다. - Data : 데이터는 사용자가 전송하고자 하는 데이터를 바이트 크기단위로 전송하는 구간이다. 데이터의 크기는 control 필드에 송수신 프로토콜을 정의하는 부분에서 정의하여야 한다.(Link 계층의 SW에서 필요한 정보 임) - FCS : Foward Control Sequence는 전송된 프레임의 오류 여부를 판별하기 위한 것으로 흔히 CCITT CRC-16을 사용하는 것으로 표시한다...
자세한 내용 보기
이미지
 FPGA실습(2) 2. UART 구현 이전 글에 이어서 이번에는 UART를 구현하여 DMA를 통해 데이터를 전송하고 수신하는 부분에 대해 다룬다. 2.1 요구사항 - AXIS Stream FIFO와 연동되는 UART 구성 - UART 회로에 공급되는 클럭에 따라 BAUD Rate 결정 2.2 UART 개요 위키백과에 나오는 UART의 소개자료는 다음과 같다. UART(범용 비동기화 송수신기: Universal asynchronous receiver/transmitter)는 병렬 데이터의 형태를 직렬 방식으로 전환하여 데이터를 전송하는 컴퓨터 하드웨어의 일종이다. UART는 일반적으로 EIA RS-232, RS-422, RS-485와 같은 통신 표준과 함께 사용한다. UART의 U는 범용을 가리키는데 이는 자료 형태나 전송 속도를 직접 구성할 수 있고 실제 전기 신호 수준과 방식(이를테면 차분 신호)이 일반적으로 UART 바깥의 특정한 드라이버 회로를 통해 관리를 받는다는 뜻이다. 즉 동기 신호는 전달하지 않고 약정된 통신 속도로 8비트의 데이터를 직렬로 전송한다는 뜻이고 실제 PC 등과 통신을 수행하기 위해서는 선로 인터페이스 소자가 따로 있어야 한다. 여기서 설계한 것은 Zynq에서 선로 인터페이스 소자로 출력하는 송신신호, 선로 인터페이스 소자로부터 수신하는 수신 신호를 생성하거나 수신하여 데이터를 처리하는 과정을 설계하고 시험하는 것이다. UART의 코딩 규격은 다음과 같다. STOP 앞에 패리티 비트를 추가하기도 하는데 여기서는 패리티 비트를 사용하지 않는 UART를 사용한다. 2.3 AXI4 Stream Bus AXI4 Stream Bus의 프로토콜은 다음 그림과 같다. 즉 VALID 신호를 송신측에서 전달하면 수신 측에서 READY 신호를 출력하여 데이터를 수신하는 방식으로 데이터를 전달 받는다. 그리고 데이터의 마지막임을 알리는 TLAST 신호는 마지막 워드(32 bit의 데이터)일 때 HIGH가 되고 그 외에는 LOW를 유지한다. 또한 ...
자세한 내용 보기