개요: iButton®을 포함한 각 1-Wire® 소자는 ROM에 8바이트의 고유한 등록 번호를 가지고 있다. 이 등록 번호는 1-Wire 버스에서 고유한 네트워크 주소로 사용된다. 데이터 통신 무결성을 보장하기 위해 각 등록 번호의 1바이트가 DOW CRC 바이트이다. 애플리케이션 노트 27에서는 이러한 8비트 DOW CRC 바이트를 계산하는 방법을 설명한다. 또한 소자의 메모리에 저장된 레코드를 확인하는데 사용되는 16비트 CRC에 대한 설명이 제공된다. DOW CRC 및 CRC-16은 모두 선별된 1-Wire 소자의 하드웨어에서 생성되어 데이터를 검증한다.
개요
Maxim iButton은 1-Wire 프로토콜이라고 하는 특정 명령 시퀀스에 따라 단일 와이어 상에서 모든 통신을 수행하는 장치 제품군이다. 핵심적 특징으로 모든 개별적인 장치는 제조시에 각 부품에 쓰여진 고유한 8바이트 ROM 코드를 가지고 있다. 이 8바이트 코드의 구성은 그림 1에서 볼 수 있다. 최하위 바이트에는 iButton 제품 유형을 식별하는 패밀리 코드가 포함되어 있다. 예를 들면 DS1990A의 패밀리 코드는 01 Hex이고, DS1991의 패밀리 코드는 02 Hex이다. 동일한 또는 다른 패밀리 유형의 여러 장치가 동일한 1-Wire 버스에 동시에 상주할 수 있으므로, 호스트가 1-Wire 버스에 있는 각 장치에 적절히 액세스할 수 있는 방법을 결정하는 것이 중요하다. 패밀리 코드가 이러한 정보를 제공한다. 다음 6바이트에는 동일한 패밀리 코드를 가지고 있는 여러 장치들 중에 각각의 장치를 구별하는데 사용되는 고유한 일련 번호가 포함되어 있다. 이러한 고유한 일련 번호는 1-Wire 버스 상의 각 장치에 지정되는 "주소"로 생각할 수 있다. 이와 같은 장치의 전체 요소는 호스트와 함께 일종의 축소형 LAN인 MicroLAN을 형성하며, 단일의 공통 와이어를 통해 모든 통신을 수행한다. 각 장치의 ROM 코드의 최상위 바이트에는 CRC (Cyclic Redundancy Check) 값이 포함되어 있으며, 이 값은 해당 부분에 대한 이전 7바이트 데이터를 기초로 한다. 호스트 시스템이 장치와 통신을 시작하면, LSB부터 시작하여 8바이트 ROM이 읽혀진다. 호스트에 의해 계산되는 CRC가 ROM 데이터의 바이트 7에 포함된 CRC와 일치할 경우, 통신은 유효한 것으로 간주된다. 일치하지 않은 경우, 오류가 발생하며, ROM 코드를 다시 읽어야 한다.
그림 1. DOW CRC를 사용한 iButton 시스템 구성
일부 iButton 제품은 적절한 명령으로 호스트 시스템에서 액세스할 수 있는 8바이트 ROM 외에도 최대 8kB의 RAM을 포함할 수 있다. iButton에 CRC 하드웨어 온보드가 없는 경우에도, 호스트가 ROM 코드에 대한 CRC 값을 계산할 수 있는 기능을 갖추고 있는 경우, CRC를 사용하여 장치의 RAM 부분에 데이터를 저장하고 검색할 수 있는 프로시저를 개발할 수 있다. 정상적인 방법으로 데이터를 장치에 쓰고, 그런 다음 호스트에 의해 계산된 CRC 값을 부가하여 데이터와 함께 저장한다. iButton을 통해 이러한 데이터를 검색할 경우, 프로세스는 정반대의 순서로 진행된다. 호스트가 데이터 바이트에 대해 계산된 CRC 값을 해당 데이터에 대한 CRC로서 메모리에 저장된 값과 비교한다. 값이 일치하면, iButton으로부터 읽혀진 데이터는 유효한 것으로 간주된다. 1-Wire 버스에서 직렬 통신을 검증하는 CRC의 강력한 성능을 이용하기 위해서는 CRC란 무엇이며 그 동작 원리를 이해할 필요가 있다. 이 밖에도, 호스트에서 하드웨어 또는 소프트웨어 구현을 위해 CRC 값을 계산하는 실제적인 방법이 필요하다.
배경
직렬 데이터는 다양한 방식으로 오류를 체크할 수 있다. 공통적으로 사용되는 한 가지 방법은 체크되는 각 패킷에 여분의 비트를 부가하여 오류가 발생했는지를 표시한다. 예를 들어, 8비트 ASCII 문자로 구성된 패킷의 경우, 각 ASCII 문자에 별도의 비트를 부가하여 문자에 오류가 포함되어 있는지를 나타낼 수 있다. 비트 문자열 11010001로 구성된 데이터가 있다고 하자. 1의 전체 비트 수가 항상 홀수가 되게 하기 위해 9번째 비트를 부가한다. 따라서 1이 부가되고 데이터 패킷은 111010001이 된다. 밑줄친 문자는 완전한 9비트 패킷이 홀수의 비트 수를 갖게 하기 위해 필요한 패리티 비트 값을 나타낸다. 수신된 데이터가 111010001이라면, 정보가 정확하다고 간주된다. 그러나 만약 수신된 데이터가 111010101이고, 이때 왼쪽으로부터 7번째 비트가 부정확하게 수신되었다면, 1의 전체 비트 수는 더 이상 홀수가 아니므로 오류 조건이 검출되고 적절한 조치가 취해진다. 이러한 유형의 구조를 홀수 패리티라고 한다. 이와 마찬가지로 1의 전체 비트 수가 항상 짝수가 되게 하는 방법도 있으며, 이를 짝수 패리티라고 부른다. 그러나 이 구조는 비트 오류의 홀수를 검출하는 데 제한된다. 위의 예에서, 만약 데이터가 훼손되어 왼쪽에서부터 6번째와 7번째 비트가 잘못 수신되어 111011101이 되었다면, 패리티 체크는 정확한 것처럼 보인다. 그러나 짝수 또는 홀수 패리티가 사용되었건 오류가 탐지되지 못한 것이다.
설명
Maxim 1-Wire CRC
하드웨어의 최소 정보량으로 직렬 데이터 스트림에서 오류를 찾는 가장 효과적인 오류 검출 구조는 CRC(Cyclic Redundancy Check)이다. Maxim 제품에 사용되는 CRC 기능의 동작과 특성은 명령문과 설명에 대한 수학적인 세부사항 없이 제공된다. CRC 특성을 구성하는 수학적인 개념은 참고문헌에서 상세히 설명된다. CRC는 실제로 하드웨어에서 구현되는 기능으로 고려할 때 가장 쉽게 이해할 수 있다. 이 경우 언제나 그림 2와 같이 피드백을 갖는 시프트 레지스터 정렬로 표현된다. 또는 CRC는 각 항에 대한 2진 계수를 갖는 더미 변수 (dummy variable) X의 다항식으로 표현할 수 있다. 이 경우 계수는 시프트 레지스터 구현에서 표시되는 피드백 경로에 직접 대응된다. 하드웨어 설명에서 시프트 레지스터의 단계의 수 또는 다항식에서 표시되는 최상위 계수는 계산될 CRC 값의 크기를 나타낸다. 디지털 데이터 통신에 일반적으로 사용되는 CRC 코드는 CRC-16 및 CRC-CCITT를 포함하며, 각각 16비트 CRC 값을 계산한다. Maxim 1-Wire CRC (DOW CRC) 크기는 8비트이며, 이 CRC는 각 1-Wire 제품에 쓰여진 64비트 ROM 코드를 체크하는데 사용된다. 이 ROM 코드는 최하위 바이트에 쓰여진 8비트 패밀리 코드, 다음 6바이트에 쓰여진 고유한 48비트 일련 번호 및 ROM에 있는 앞의 56비트를 기초로 계산된 다음 최상위 바이트에 쓰여지는 CRC 값으로 구성된다. 그림 2의 배타적 논리합 (exclusive-or) 게이트에 의해 표현되는 피드백 경로의 위치 또는 다항식에서의 계수의 존재는 CRC의 특성과 데이터의 특정 오류 유형을 찾는 알고리즘의 능력을 결정한다. DOW CRC의 경우, 검출할 수 있는 오류 유형은 다음과 같다.
64비트 수에서 임의 위치의 모든 홀수 비트 오류
64비트 수에서 임의 위치의 모든 더블 비트 오류
8비트 "윈도우" 안에 포함될 수 있는 모든 집단 오류 (부정확한 1 ~ 8비트)
더 큰 크기의 집단 오류
그림 2에서 입력 데이터는 시프트 레지스터의 8번째 단계의 출력과 배타적 논리합(exclusive-or)이다. 시프트 레지스터는 수학적으로 분주 회로(dividing circuit)로 간주할 수 있다. 입력 데이터는 피제수(dividend)이며, 피드백을 갖는 시프트 레지스터는 제수(divisor)이다. 피제수를 제수로 나눈 결과인 몫은 폐기되며, 나머지가 마지막 데이터 비트가 시프트 인 된 후 시프트 레지스터에 상주하는 입력 데이터의 특정 스트림에 대한 CRC 값이다. 시프트 레지스터 구현에서는 최종 결과(CRC 값)가 매우 복잡한 방식으로, 제공된 비트의 이전 히스토리에 의존적이라는 점이 분명하다. 따라서, 이와 같은 방법에서는 극도로 드문 오류의 조합이 아니면 검출을 피할 수 없다.
그림 2. Maxim 1-Wire 8비트 CRC
그림 2의 예는 각 데이터 비트가 제공된 후 CRC 값을 계산한 것이다. 시프트 레지스터 회로는 계산이 시작될 때 언제나 0으로 리셋된다. 이 예에서 계산은 02 Hex 패밀리 코드인 64비트 ROM의 LSB부터 시작한다. 모든 56 데이터 비트(일련 번호 + 패밀리 코드)가 입력되면, 시프트 레지스터에 포함된 값이 A2 Hex가 되며, 이 값은 해당 입력 스트림에 대한 DOW CRC 값이다. 계산된 CRC 값(이 예에서 A2 Hex)이 이제 다음 8비트 데이터에 대한 시프트 레지스터에 대한 입력으로 사용되면, 전체 64비트 데이터가 입력된 후 시프트 레지스터의 최종 결과는 모두 0이어야 한다. 이러한 특성은 DOW CRC 알고리즘에 대해서는 언제나 참이다. 만약 시프트 레지스터에 표시되는 임의 8비트 값이 또한 입력 스트림의 다음 8비트로 사용된다면, 8번째 데이터 비트가 시프트 인 된 후 시프트 레지스터에 나타나는 결과는 언제나 00 Hex가 된다. 이것은 시프트 레지스터의 8번째 단계의 내용이 언제나 들어오는 데이터 비트와 동일하므로, 따라서 시프트 레지스터의 피드백과 시프트 레지스터의 첫 번째 단계의 다음 값을 제어하는 EXOR 게이트의 출력은 언제나 로직 0이 된다는 것을 관찰할 수 있다는 사실로 설명할 수 있다. 이에 따라, 시프트 레지스터는 8번째 비트 후 전체 레지스터가 0으로 채워질 때까지 각 데이터 비트가 제공될 때마다 왼쪽에서 오른쪽으로 0을 시프트 할 수 있다. Maxim 1-Wire 64비트 ROM의 구조는 이러한 특성을 사용하여 ROM을 읽는데 사용되는 장치의 하드웨어 설계를 단순화하고 있다. 호스트의 시프트 레지스터가 클리어 되고, 그런 다음 CRC 값을 포함하여 64 ROM 비트가 읽혀진다. 정확한 읽기가 발생한 경우, 시프트 레지스터는 다시 전부 0이 되며, 이것은 용이한 검출 상태이다. 그러나 만약 시프트 레지스터에 0 이외의 값이 남아있는 경우, 읽기 동작을 반복해야 한다.
지금까지 CRC 프로세스의 하드웨어 구현을 중심으로 살펴보았지만, 하드웨어 방법론과 유사한 소프트웨어 솔루션도 DOW CRC 값을 계산하는 또 다른 방법을 제공한다. 프로시저를 코딩하는 방법의 예는 예제 1에 제공된다. 상수 18 Hex를 갖는 A 레지스터의 XRL(EXOR)은 4번째 및 5번째 단계 후 DOW CRC에서 EXOR 피드백 게이트가 존재하기 때문이다(그림 2). 이에 대한 소프트웨어 구현은 간단히 CRC 레지스터에 현재 저장되어 있는 임의 8비트 값과 새로운 데이터의 8비트 패턴에 대해 직접 액세스할 수 있는 룩업 테이블을 만드는 것이다. RC 레지스터의 현재 값이 00 Hex와 같이 단순한 경우, 입력 바이트에 대한 256가지 다른 비트 조합을 계산하여 매트릭스에 저장할 수 있다. 이때 매트릭스에 대한 인덱스는 입력 바이트의 값과 동일하다(즉, 인덱스는 I = 0 ~ 255가 된다). CRC 레지스터의 현재 값이 00 Hex가 아닐 경우, 현재 CRC 값과 임의 입력 값에 대해, 룩업 테이블 값은 00 Hex의 경우와 마찬가지로 동일하게 표현할 수 있지만, 테이블 안의 인덱스 계산은 다음과 같은 형식을 취한다.
I = 0 ~ 255일 때 New CRC = Table [I]
여기서, I = (Current CRC) EXOR (입력 바이트)
현재 CRC 레지스터 값이 00 Hex인 경우, 방정식은 단순해진다. 이 두 번째 방법은 앞의 예와 같은 비트 지향 명령이 아닌 바이트 기준으로 연산을 수행하기 때문에 계산 시간을 줄일 수 있다. 그러나 이 경우 룩업 테이블을 저장해야 하고 256 바이트를 소비해야 하므로, 사용할 수 있는 메모리 용량이 감소된다. 첫 번째 예에서는 프로그램 코드를 제외하고 실제로 어떤 저장 공간도 필요로 하지 않는다. 이러한 유형의 코드 예는 예제 3에 제공된다. 표 1은 룩업 테이블 방법을 사용한 앞의 예를 다시 보여준다. DOW CRC의 두 가지 특성은 CRC 값을 계산하는데 사용되는 코드 디버깅을 용이하게 해준다. 첫 번째 특성은 이미 하드웨어 구현에서 설명했다. 즉, CRC 레지스터의 현재 값이 데이터의 다음 바이트에 사용될 경우, 그에 따른 CRC 값은 언제나 00 Hex가 된다(위 설명 참조). 코드의 적절한 연산을 확인하는데 사용할 수 있는 두 번째 특성은 CRC 레지스터의 현재 값에 대한 1의 보수를 입력하는 것이다. DOW CRC 알고리즘의 경우, 그에 따른 CRC 값은 언제나 35 Hex (십육진수) 또는 53 Decimal(십진수)이 된다. 그 이유는 표 2에서 볼 수 있듯이 1의 보수 데이터가 입력될 때 CRC 레지스터의 연산을 관찰한다면 알 수 있을 것이다.
예제 1. 어셈블리 언어 프로시저
DO_CRC:PUSH ACC;save accumulator
PUSH B;save the B register
PUSH ACC;save bits to be shifted
MOV B,#8;set shift = 8 bits ;
CRC_LOOP:XRL A,CRC;calculate CRC
RRC A;move it to the carry
MOV A,CRC;get the last CRC value
JNC ZERO;skip if data = 0
XRL A,#18H;update the CRC value
;
ZERO:RRC A;position the new CRC
MOV CRC,A;store the new CRC
POP ACC;get the remaining bits
RR A;position the next bit
PUSH ACC;save the remaining bits
DJNZ B,CRC_LOOP;repeat for eight bits
POP ACC;clean up the stack
POP B;restore the B register
POP ACC;restore the accumulator
RET
예제 2. DOW CRC 계산 예
CRC Value
Input Value
00000000
0
00000000
1
10001100
0 2
01000110
0
00100011
0
10011101
0
11000010
0 0
01100001
0
10111100
0
01011110
0
00101111
1 C
00010111
1
00001011
1
00000101
0
10001110
0 1
01000111
0
10101111
0
11011011
0
11100001
0 8
11111100
1
11110010
1
11110101
1
01111010
0 B
00111101
1
00011110
1
10000011
0
11001101
0 1
11101010
0
01110101
0
10110110
0
01011011
0 0
10100001
0
11011100
0
01101110
0
00110111
0 0
10010111
0
11000111
0
11101111
0
11111011
0 0
11110001
0
11110100
0
01111010
0
00111101
0 0
10010010
0
01001001
0
10101000
0
01010100
0 0
00101010
0
00010101
0
10000110
0
01000111
0 0
10101101
0
11011010
0
01101101
0
10111010
0 0
01011101
0
10100010 = A2 Hex = CRC Value for [00000001B81C (Serial Number) + 02 (Family Code)]
10100010
0
01010001
1
00101000
0 2
00010100
0
00001010
0
00000101
1
00000010
0 A
00000001
1
00000000 = 00 Hex = CRC Value for A2 [(CRC) + 00000001B81C (Serial Number) + 02 (Family Code)]
개요에서 언급했듯이 일부 iButton 장치는 모든 iButton에 포함된 고유한 8바이트 ROM 코드 외에 RAM을 가지고 있다. RAM에 저장되는 데이터 양은 8바이트 ROM 코드에 비해 크기 때문에, 데이터의 무결성을 보장하기 위해 Maxim은 ROM에 사용되는 8비트 DOW CRC가 아닌 16비트 CRC 값을 사용할 것을 권한다. 제안되는 특별한 CRC를 일반적으로 CRC-16이라고 한다. 시프트 레지스터 및 다항식은 그림 3에 제공된다. 그림에서는 16비트 CRC의 경우 시프트 레지스터에 16단계가 포함되며 다항식은 16번째 차수의 항을 갖는다는 것을 볼 수 있다. 앞에서 언급했듯이 iButton은 CRC 값을 계산하지 않는다. 호스트가 값을 생성한 다음 16비트 CRC 값을 실제 데이터 끝에 부가해야 한다. iButton의 "통신 채널" 즉, 두 개의 금속 접촉의 불확실성으로 인해, 데이터 전송은 오류가 발생할 수 있으며, 이러한 오류는 일반적으로 세 가지 범주로 분류된다. 첫째, 짧은 간헐적 연결이 데이터에 소수의 비트 오류를 발생시킬 수 있다. 이러한 오류는 일반적 CRC-16 기능으로 검출할 수 있다. 두 번째 유형의 오류는 가령, iButton이 리더에서 너무 빨리 제거되는 경우와 같이 접촉이 완전히 손실될 때 발생한다.
이러한 경우 데이터의 마지막 부분이 로직 1로 읽혀진다. iButton에 대한 연결이 없는 상태는 호스트에 의해 언제나 모두 1로 해석되기 때문이다. 일반적 CRC-16 기능은 대부분의 환경에서 이러한 조건을 검출할 수 있다. 세 번째 오류 유형은 리더의 단락 회로에 의해 발생한다. 단락 회로는 적절히 삽입되지 못하거나 또는 리더에 많이 기울어진 채 삽입된 iButton에 의해 발생할 수 있다. 리더의 단락은 데이터가 호스트에 의해 모두 0으로 읽혀지도록 한다. CRC를 사용할 경우, 이것은 문제를 일으킬 수 있다. 데이터의 유효성을 검증하는 방법이 데이터 및 저장된 CRC 값을 읽고, 호스트에서 계산된 CRC 값이 0000 Hex(16비트 CRC의 경우)인지를 확인하는 것이기 때문이다. 리더가 단락된 경우, 데이터 및 데이터와 함께 저장된 CRC 값은 모두 0으로 읽혀지고, 잘못된 읽기가 발생하지만, 호스트에 의해 계산된 CRC는 유효한 읽기라고 잘못된 결과를 표시할 것이다. Maxim은 이러한 상황을 피할 수 있도록 RAM에 쓰여진 데이터와 함께, 계산된 CRC-16 값의 보수(CRC-16*)를 저장하도록 권고하고 있다. 보수가 아닌 CRC-16 값을 사용할 경우, iButton의 데이터 검색은 DOW CRC 경우와 유사하다. 즉, 만약 호스트의 CRC 레지스터가 0000 Hex로 초기화되고 그런 다음 모든 데이터 및 데이터와 함께 저장된 CRC-16 값을 iButton으로부터 읽을 경우, 그에 따른 호스트에 의한 계산은 최종 결과로 0000 Hex를 가져야 한다. 만약 대신, CRC-16 값의 보수를 iButton에 데이터와 함께 저장하고, 그런 다음 호스트의 CRC 레지스터를 0000 Hex로 초기화한다면, 실제 데이터 및 저장된 CRC-16* 값이 읽혀진다. 계산된 CRC 값은 유효 읽기가 되려면 B001 Hex가 되어야 한다. 이것은 리더의 단락에 의해 잘못 판단되는 일이 더 이상 없기 때문에 시스템 동작을 현저히 향상시킨다. CRC-16 기능이 이러한 특성을 갖는 이유는 DOW CRC 경우와 유사한 방식에서 찾아볼 수 있다(그림 3 및 그림 5 참조). 16비트 CRC의 연산은 앞에서 설명한 8비트 버전과 이론적으로는 동일하지만, 이제 16비트 값을 오류 검출을 위해 사용할 수 있기 때문에 CRC의 특성은 달라진다. CRC-16 기능의 경우, 검출 가능한 오류 유형은 다음과 같다.
데이터 레코드 내에서 임의 위치의 모든 홀수 비트 오류
데이터 레코드 내에서 임의 위치의 모든 더블 비트 오류
16비트 "윈도우" 안에 포함될 수 있는 모든 집단 오류 (부정확한 1 ~ 16비트)
더 큰 크기의 집단 오류
그림 3. CRC-16 하드웨어 설명 및 다항식
CRC-16 기능의 하드웨어 구현은 3에 제공된 설명에서 쉽게 알 수 있다. 예제 4는 단일 비트 연산을 사용하여 CRC-16 값을 계산하는 하드웨어 연산과 유사한 소프트웨어 솔루션을 보여준다. 앞에서와 마찬가지로 룩업 테이블을 사용하여 보다 덜 계산 집약적인 (computation-intensive) 소프트웨어 솔루션을 개발할 수 있다. 8비트 DOW CRC 룩업 테이블의 기본 개념은 CRC-16의 경우에도 적용된다. 그러나 CRC-16 기능에 대한 전체 16비트 결과가 앞에서와 같이 하나의 테이블에 매핑될 경우 테이블은 216 또는 65536 엔트리를 갖기 때문에, 8비트 경우에서 프로시저를 약간 수정할 필요가 있다. 예제 5에는 16비트 CRC 값을 계산하여 2개의 256 엔트리 테이블에 저장하는 다른 방법을 볼 수 있다. 이 경우 한 테이블에는 계산된 CRC 값의 상위 바이트가 기록되고, 다른 테이블에는 CRC 값의 하위 바이트가 기록된다. 현재 16비트 CRC 값(현재 상위 바이트 Current_CRC16_Hi 및 현재 하위 바이트 Current _CRC16_Lo)과 새로운 입력 바이트의 경우, 새로운 상위 바이트 CRC 값(New_CRC16_Hi)을 찾기 위해 상위 바이트 테이블에 대한 인덱스를 결정하는 방정식은 다음과 같다.
I = 0 ~ 255일 때 New_CRC16_Hi = CRC16_Tabhi[I]
여기서, I = (Current CRC) EXOR (입력 바이트)
새로운 하위 바이트 CRC 값(New_CRC16_Lo)을 찾기 위한 하위 바이트 테이블에 대한 인덱스를 결정하는 방정식은 다음과 같다.
I = 0 ~ 255일 때 New_CRC16_Lo = (CRC16_Tablo[I]) EXOR (Current_ CRC16_Hi)
여기서, I = (Current_CRC16_Lo) EXOR (입력 바이트)
이러한 방법이 적용되는 예를 그림 그림 4에서 볼 수 있다.
예제 4. CRC-16 계산을 위한 어셈블리 언어
crc_lo data 20h ; lo byte of crc calculation (bit addressable)
crc_hi data 21h ; hi part of crc calculation
;---------------------------------------------------------------------------
;CRC16 subroutine.
;- accumulator is assumed to have byte to be crc'ed
;- two direct variables are used crc_hi and crc_lo
;- crc_hi and crc_lo contain the CRC16 result
;---------------------------------------------------------------------------
crc16:; calculate crc with accumulator
push b; save value of b
mov b, #08h; number of bits to crc.
crc_get_bit:
rrc a; get low order bit into carry
push acc; save a for later use
jc crc_in_1;got a 1 input to crc
mov c, crc_lo.0;xor with a 0 input bit is bit
sjmp crc_cont;continue
crc_in_1:
mov c, crc_lo.0;xor with a 1 input bit
cpl c;is not bit.
crc_cont:
jnc crc_shift; if carry set, just shift
cpl crc_hi.6;complement bit 15 of crc
cpl crc_lo.1;complement bit 2 of crc
crc_shift
mov a, crc_hi; carry is in appropriate setting
rrc a ; rotateit
mov crc_hi, a; and save it
mov a, crc_lo; again, carry is okay
rrc a ; rotateit
mov crc_lo, a; and save it
pop acc; get acc back
djnz b, crc_get_bit; go get the next bit
pop b; restore b
ret
end
예제 5. 룩업 테이블을 사용한 CRC를 위한 어셈블리 언어
crc_lo data 40h; any direct address is okay
crc_hi data 41h
tmp data 42h
;---------------------------------------------------------------------------
;CRC16 subroutine.
;- accumulator is assumed to have byte to be crc'ed
;- three direct variables are used, tmp, crc_hi and crc_lo
;- crc_hi and crc_lo contain the CRC16 result
;- this CRC16 algorithm uses a table lookup
;---------------------------------------------------------------------------
crc16:
xrl a, crc_lo; create index into tables
mov tmp, a; save index
push dph; save dptr
push dpl;
mov dptr, #crc16_tablo; low part of table address
movc a, @a+dptr; get low byte
xrl a, crc_hi;
mov crc_lo, a; save of low result
mov dptr, #crc16_tabhi; high part of table address
mov a, tmp; index
movc a, @a+dptr;
mov crc_hi, a; save high result
pop dpl; restore pointer
pop dph;
ret; all done with calculation
crc16_tablo:
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 000h, 0c1h, 081h, 040h, 001h, 0c0h, 080h, 041h
db 001h, 0c0h, 080h, 041h, 000h, 0c1h, 081h, 040h
crc16_tabhi:
db 000h, 0c0h, 0c1h, 001h, 0c3h, 003h, 002h, 0c2h
db 0c6h, 006h, 007h, 0c7h, 005h, 0c5h, 0c4h, 004h
db 0cch, 00ch, 00dh, 0cdh, 00fh, 0cfh, 0ceh, 00eh
db 00ah, 0cah, 0cbh, 00bh, 0c9h, 009h, 008h, 0c8h
db 0d8h, 018h, 019h, 0d9h, 01bh, 0dbh, 0dah, 01ah
db 01eh, 0deh, 0dfh, 01fh, 0ddh, 01dh, 01ch, 0dch
db 014h, 0d4h, 0d5h, 015h, 0d7h, 017h, 016h, 0d6h
db 0d2h, 012h, 013h, 0d3h, 011h, 0d1h, 0d0h, 010h
db 0f0h, 030h, 031h, 0f1h, 033h, 0f3h, 0f2h, 032h
db 036h, 0f6h, 0f7h, 037h, 0f5h, 035h, 034h, 0f4h
db 03ch, 0fch, 0fdh, 03dh, 0ffh, 03fh, 03eh, 0feh
db 0fah, 03ah, 03bh, 0fbh, 039h, 0f9h, 0f8h, 038h
db 028h, 0e8h, 0e9h, 029h, 0ebh, 02bh, 02ah, 0eah
db 0eeh, 02eh, 02fh, 0efh, 02dh, 0edh, 0ech, 02ch
db 0e4h, 024h, 025h, 0e5h, 027h, 0e7h, 0e6h, 026h
db 022h, 0e2h, 0e3h, 023h, 0e1h, 021h, 020h, 0e0h
db 0a0h, 060h, 061h, 0a1h, 063h, 0a3h, 0a2h, 062h
db 066h, 0a6h, 0a7h, 067h, 0a5h, 065h, 064h, 0a4h
db 06ch, 0ach, 0adh, 06dh, 0afh, 06fh, 06eh, 0aeh
db 0aah, 06ah, 06bh, 0abh, 069h, 0a9h, 0a8h, 068h
db 078h, 0b8h, 0b9h, 079h, 0bbh, 07bh, 07ah, 0bah
db 0beh, 07eh, 07fh, 0bfh, 07dh, 0bdh, 0bch, 07ch
db 0b4h, 074h, 075h, 0b5h, 077h, 0b7h, 0b6h, 076h
db 072h, 0b2h, 0b3h, 073h, 0b1h, 071h, 070h, 0b0h
db 050h, 090h, 091h, 051h, 093h, 053h, 052h, 092h
db 096h, 056h, 057h, 097h, 055h, 095h, 094h, 054h
db 09ch, 05ch, 05dh, 09dh, 05fh, 09fh, 09eh, 05eh
db 05ah, 09ah, 09bh, 05bh, 099h, 059h, 058h, 098h
db 088h, 048h, 049h, 089h, 04bh, 08bh, 08ah, 04ah
db 04eh, 08eh, 08fh, 04fh, 08dh, 04dh, 04ch, 08ch
db 044h, 084h, 085h, 045h, 087h, 047h, 046h, 086h
db 082h, 042h, 043h, 083h, 041h, 081h, 080h, 040h
그림 4. CRC-16에 대한 계산 및 테이블 룩업 방법 비교
흥미있는 중간 방법이 예제 6에 제공된다. 코드는 그림 5의 방정식을 사용하여 전체 현재 CRC 값 및 들어오는 바이트에서 연산을 수행함으로써 각 바이트 입력에 대한 CRC-16 값을 발생시킨다. 또한 현재 16비트 CRC 값을 표현하는 알파 문자 (alpha character) 및 들어오는 바이트의 비트를 표현하는 숫자를 사용하는 방정식에 대한 도출을 볼 수 있다. 8회 시프트 후, 그 결과 그림에서 보는 방정식이 생성된다. 그런 다음 이러한 방정식을 사용하여 새로운 CRC 값의 많은 부분을 미리 계산할 수 있다. 예를 들어, 수량 ABCDEFGH01234567(모든 해당 비트에 대한 EXOR로 정의)은 들어오는 데이터 바이트 및 현재 CRC의 하위 바이트의 패리티이다. 이 방법은 위에서 설명한 bit-by-bit 및 룩업 테이블에 비해 계산 시간과 메모리 공간을 감소시킨다. 마지막으로, 시험 사례로 사용할 수 있는 CRC-16 기능의 두 가지 특성은 앞의 모든 방법에서 코드 디버깅을 위한 유용한 도구가 될 수 있다. 첫 번째 특징은 DOW CRC 경우와 동일하다. CRC 레지스터의 현재 16비트 내용을 다음 16비트 입력에도 사용하는 경우, 계산된 CRC 값은 언제나 0000 Hex가 된다. CRC-16 기능의 두 번째 특징도 DOW CRC 경우와 유사한데, 만약 CRC 레지스터의 현재 16비트 내용의 1의 보수를 다음 16비트 입력에도 사용하는 경우, 계산된 CRC 값은 언제나 B0 01 Hex가 된다. 이들 두 가지 CRC-16 특징에 대한 증명은 유사한 방식으로 DOW CRC 경우에 대한 증명을 따른다.
예제 6. 고속 CRC-16 계산을 위한 어셈블리 언어 프로시저
lo equ 40h ; low byte of CRC
hi equ 41h ; high byte of CRC
crc16:
push acc; save the accumulator.
xrl a, lo
mov lo, hi; move the high byte of the CRC.
mov hi, a; save data xor low(crc) for later
mov c, p
jnc crc0
xrl lo, #01h; add the parity to CRC bit 0
crc0:
rrc a; get the low bit in c
jnc crc1
xrl lo, #40h; need to fix bit 6 of the result
crc1:
mov c, acc.7
xrl a, hi; compute the results for other bits.
rrc a; shift them into place
mov hi, a; and save them
jnc crc2
xrl lo, #80h; now clean up bit 7
crc2:
pop acc; restore everything and return
ret
다운로드, PDF 형식
