버텍스-5 FPGA에서 CRC 하드 블록 사용하기 - Technology

자일링스 FPGA에서 CRC 블록을 제공함으로써 디자이너들이 다양한 설계에서 오류 검출 매커니즘을 보다 쉽고 간단하게 구현할 수 있게 되었다. 여러분은 CORE GeneratorTM 소프트웨어에서 이용할 수 있는 CRC Wizard IP를 사용하여, Aurora 및 PCI Express와 같은 다양한 프로토콜 상의 오류 검출 기능을 통합할 수 있다.

버텍스-5 FPGA에서 CRC 하드 블록 사용하기

글│수니타 자인(Sunita Jain), 구루 프라산나(Guru Prasanna), 자일링스

데이터 손실은 데이터 전송 및 스토리지와 관련된 가장 주요한 문제이다. 데이터가 채널을 통해 전송될 때마다 오류가 발생할 가능성이 항상 존재한다.

수신 모듈은 반드시 수신 메시지의 오류 유무를 판단할 수 있어야 한다. 여기에는 다양한 오류 검출 방법이 존재하는데, 대부분의 오류 점검 방법은 리던던트 bit를 사용한다. 데이터 통신에서 오류 검출을 위해 일반적으로 사용되고 있는 방법으로는 패러티 코드(Parity Code), Hamming 코드, CRC(Cyclic Redund-ancy Check) 등이 있다. 이 가운데 CRC가 가장 폭넓게 사용되고 있다.

CRC는 주어진 데이터 bit의 세트를 기반으로 연산이 이뤄지며, 전송이나 스토리지를 실행하기 전에 데이터 프레임 끝단에서 삽입된다. 프레임이 수신되거나 검출될 때, 이에 대한 유효성은 데이터에 오류가 없다는 것을 보장하기 위해 프레임 컨텐츠에 적합한 CRC를 재계산함으로써 확보된다.

이 글에서, 우리는 리니어 피드백 쉬프트 레지스터를 이용해 CRC 계산의 기본적인 이론과 하드웨어 구현을 살펴 보고, 자일링스 버텍스-5(VirtexTM-5) LXT/SXT 디바이스에서 제공되는 CRC 하드 블록에 대해 논의하고자 한다.

개요

덧셈 및 뺄셈 연산은 모듈로 2 수학적 계산을 사용해 → 2진수 연산을 통해 수행된다. 즉, 이 연산들은 독자적인 OR(XOR) 연산과 동일하다. 다항식 계산에서 2개의 숫자를 덧셈하는 것은 올림 수가 없다는 것을 제외하고는 정상적인 2진법 계산에서 숫자를 덧셈하는 것과 동일하다.

예를 들어, 2진법 메시지 스트림 11001011은 x7 x6 x3 x 1로 나타난다. 이 전송 및 수신 포인트는 제너레이터 다항식으로 불리는 고정 다항식과 상응하며, 이것은 CRC 계산의 핵심 요소이다.

데이터는 다항식의 계수로 해석되며, 이것은 주어진 제너레이터 다항식으로 나누어진다. 이 나눗셈의 나머지가 CRC이다. 주어진 m-bit 메시지 시퀀스 및 r degree의 제너레이터 다항식에서 트랜스미터는 FCS(Frame Check Sequence)로 불리는 n-bit(n = m r) 시퀀스를 생성하며, 결과인 (m r)-bit 프레임은 미리 계산된 시퀀스에 따라 나누어질 수 있다.

트랜스미터는 m-bit 메시지에 r 개의 0-bit를 부가하고, 제너레이터 다항식으로 m r-1 degree의 결과 다항식을 나눈다. 이것은 (r-1) degree 미만의 잔여 다항식을 생성한다. 나머지 다항식은 r 계수를 가지며, 이것은 체크섬을 형성한다. 지수는 버려진다. 전송된 데이터는 r-bit 체크섬에 따라 이루어진 원래의 m-bit 메시지이다.

리시버에서 수신된 데이터의 유효성 여부를 평가하기 위해 2가지의 표준 접근방식 중 하나를 선택할 수 있다.

¶ 최초로 수신된 m-bit를 위해 체크섬을 다시 계산하고 수신된 체크섬(최종 수신된 r-bit)과 비교한다.
¶ 모든 수신된 (m r) bit에 대한 체크섬을 계산하고 나머지 0과 비교한다.

0의 나머지에서 두 번째 방법이 어떠한 결과를 가져오는지 확인하기 위해 다음 사항을 사용해 보자.
   M = 메시지의 다항식 표현
   R = 트랜스미터에서 연산된 나머지의 다항식 표현
   G = 제너레이터 다항식
   Q = M을 G로 나눗셈함으로써 획득되는 지수

전송된 데이터는 다항식 Mxr-R에 대응한다. 가변 xr은 체크섬을 수용하기 위해 메시지의 r-bit 쉬프트를 나타낸다. 알다시피 Mxr = QG R이다.

트랜스미터에서 메시지에 체크섬 R을 추가하는 것은 메시지에서 나머지를 빼는 것과 동일하다. 그 다음 전송된 데이터는 Mxr-R = QG가 되며, 이것은 G의 배수가 된다. 이것이 바로 두 번째 사례에서 0의 나머지를 어떻게 얻는지에 대한 방법이다.

그러나 이 절차는 전송된 데이터의 앞쪽의 수나 트레일링 0-bit에는 민감하지 않다. 즉, 메시지에 트레일링 0-bit가 삽입되어 있거나 지워질 경우, 나머지는 여전히 0으로 남고, 오류는 발견되지 않을 것이며, 이로 인해 동일한 비트 시퀀스는 다시 재생되지 않을 것이다. 이러한 결함을 극복할 수 있는 전술적 해결 방법은 무엇일까?

그 밖의 접근방법

실제 상황에서 체크섬은 부가되기 전에 보완되어진다. 이것은 리시버의 non-0단에서 나머지가 계산(m r bit에서)되도록 한다. 이러한 경우에 리시버에서 획득되는 나머지는 다항식의 나머지 값으로 알려진 고정 값이다.
약간의 수학적 계산만으로 이 아이디어를 더욱 분명하게 설명할 수 있다.

아래에 나타낸 % 심볼은 모듈로 동작을 나타낸다.

인버전 없이 부가된 체크섬의 경우:
(Mxr-R) xr % G = 0

여기서 리시버는 다시 트랜스미터와 동일한 변환 동작을 수행한다.

이제 체크섬이 트랜스미터에서 메시지 스트림으로 인버트되고 부가되는 사례를 살펴보자:

(Mxr-Rc) xr % G

여기서, Rc는 보완된 체크섬을 나타낸다.

이것은 다음과 같이 기술될 수도 있다:
(Mxr-R (xr-1 ... x 1)) xr % G

비트 컴플리먼트는 1 XOR과 동일하다. 여기서 사인은 모듈로 2 산술적 계산에 추가되어 나타난다.(덧셈과 뺄셈은 모듈 2 산술적 계산에서 동일하다는 것을 명심하자)

여기서, 나머지는 다음과 같다:
(xr-1 ... x 1) xr % G

이것은 주어진 제너레이터 다항식을 위한 상수로 작용한다.

가장 흔하게 사용되는 CRC-32 제너레이터 다항식은 다음과 같다
G(x) = x32 x26 x23 x22 x16 x12 x11 x10 x8 x7 x5 x4 x2 x 1

이것은 16진수로 04C11DB7이다.

CRC-32에 대응하는 상수의 나머지 값은 16진수로 C704DD7B이다. 주어진 제너레이터 다항식 G의 경우, 나머지 값은 입력에서 제공되는 데이터 패턴을 위한 상수로 남는다.

하드웨어 구현

CRC 체크섬의 연산은 다항식 나눗셈 과정이다. 하드웨어에서 이것을 구현하는 것은 쉬프트 레지스터를 사용할 수 있다.(CRC 레지스터로도 불린다). 쉬프트 레지스터의 길이는 제너레이터 다항식의 degree와 동일하다.

CRC 연산 절차는 다음과 같다:

1. CRC 레지스터를 초기화 한다.
2. 메시지 비트가 가능한 길게 존재하는 동안 메시지 비트를 획득하고 지속시킨다. CRC 레지스터에서 더 높은 차수 bit가 1일 경우, 왼쪽으로 한 bit 쉬프트하여 G와 XOR을 취한다. 그렇지 않을 경우, 왼쪽으로 한 bit만 쉬프트 한다.
주어진 메시지에 대해 이러한 모든 단계가 완성되었을 때, CRC 레지스터는 나머지를 갖게 된다.

이러한 단계는 LFSR(Linear Feed-back Shift Register)로 알려진 회로를 통해 구현될 수 있다. 그림 1은 CRC32 다항식을 이용해 CRC를 계산하기 위한 LFSR 구현을 보여준다. XOR 게이트는 제너레이터 다항식의 계수가 1인 경우에 배치하게 된다. 이 그림에 나타난 각각의 숫자로 명시된 블록은 메모리 성분(플립 플롭)이다.

그림 1.

CRC 블록

CRC 하드웨어 구현은 간단한 LFSR을 사용한다. 이러한 회로 구현이 간단하다고 해도, n-bit 데이터 스트림을 위해 CRC 값을 계산하는데 n클럭 사이클이 소요된다. 이 레이턴시는 데이터 프레임이 고속으로 처리되어야 하는 고속 데이터 네트워킹 애플리케이션에서는 주요한 문제가 된다. 병렬 스트림 상에서의 CRC 생성과 확인 절차의 구현은 이러한 고속 네트워킹 애플리케이션에서 요구되고 있다.

CRC 블록을 버텍스-5 LXT/SXT 디바이스에 구현하면 체크섬 계산 속도를 높일 수 있다. 버텍스-5 LXT/SXT 디바이스의 CRC 하드 블록은 CRC32 다항식에 기반한다. 버텍스-5 FPGA는 4-byte와 8-byte 입력에 대한 CRC를 생성하는데 한 클럭 사이클의 레이턴시를 갖는 CRC32 및 CRC64 하드 블록을 포함하고 있다. 인터페이스는 사용하기 쉽고 간단하다. 하드 블록은 입력으로서 일부 CRC-특정 파라미터와 함께 주어진 메시지 스트림에서 CRC 계산기로 동작한다. CRC 비교 기능은 하드 블록 내에서 처리될 수 없으며, FPGA 패브릭에 구현되어야 한다.

FPGA 각각의 CRC 하드 블록은 비동기적으로 32-bit 체크섬을 연산한다. 그림 2는 하드 블록의 아키텍처를 보여주는 블록-레벨 다이어그램이다. CRC 하드 블록은 bit-인버터되고, 바이트-리버스된 출력을 제공한다.

그림 2.

그림 3은 CRC 하드 블록의 애플리케이션 개요를 나타내고 있다. CRC는 트랜스미터에서 주어진 데이터 패킷의 끝단에서 부가되고 연산된다. 리시버에서 CRC는 트랜스미터에서 추가된 CRC와 함께 수신된 전체 패킷에 대해 재계산이 이루어진다.

그림 3.

그림 4.

수신된 패킷의 유효성 확인은 나머지 방법을 통해 이뤄진다. 이 경우, CRC32 다항식의 나머지는 16진수로 1CDF4421이 되도록 동작되며, 이는 C704DDB7 에 대한 bit-인버트되고 byte-리버스 된 값이다. 바이트 로테이션 및 비트 인버전에 대한 개념은 그림 4에 제시되어 있다. 그림 5는 표준 CRC 동작에 대한 파형을 보여주고 있다.

한편 우리는 버텍스-5 디바이스의 CRC 하드 매크로를 위해 LocalLink를 포함하고 있는 LogiCORETM CRC 위저드를 제공하고 있으며, 또한 이 코어는 CRC 하드 블록을 사용한 실제 디자인 사례를 제공한다.

이와 함께 이 코어는 파이프라인, 컴플리멘팅, 트랜스포팅과 같은 다양한 옵션을 제공한다. 보다 자세한 정보는 www. xilinx.com/crcwizard 에서 제공된다.

그림 5.

결론

Notes:
참고: 1. Prev = 기존 사이클에서 CRCINTREG 값
2. f(x) = 비트 인버트 및 바이트 리버스 x.