摘要：全部1-Wire?器件，包括iButton?器件，都具有唯一的8字節(jié)注冊(cè)碼，儲(chǔ)存在只讀存儲(chǔ)器(ROM)中。該注冊(cè)碼在1-Wire總線上用作唯一的網(wǎng)絡(luò)地址。為確保數(shù)據(jù)通信的完整性，每個(gè)注冊(cè)碼的一個(gè)字節(jié)是一個(gè)DOW CRC字節(jié)。本篇應(yīng)用筆記說(shuō)明了8位DOW CRC的計(jì)算方法以及用于驗(yàn)證器件存儲(chǔ)器記錄的16位CRC的計(jì)算。DOW CRC和CRC-16還會(huì)在選擇1-Wire器件驗(yàn)證數(shù)據(jù)的硬件中產(chǎn)生。

引言

Maxim的iButton系列產(chǎn)品是通過(guò)單線按照1-Wire協(xié)議傳送特定命令序列，進(jìn)行數(shù)據(jù)通信。該系列產(chǎn)品都有個(gè)很重要的特性，就是在出廠前每個(gè)器件都被寫入了唯一的8字節(jié)ROM碼。其ROM碼組成如圖1所示，最低有效字節(jié)為家族代碼，代表iButton器件的類型，如：DS1990A的家族碼為01，DS1991的家族碼為02。由于在同一條1-Wire總線上可同時(shí)掛接多個(gè)相同系列或不同系列的1-Wire器件，因此主機(jī)必須能夠決定如何正確地訪問(wèn)位于1-Wire總線上的各個(gè)器件，這一點(diǎn)尤為重要。家族碼提供器件的類型，隨后的6個(gè)字節(jié)是器件的唯一序列號(hào)，用以區(qū)分同一個(gè)系列的不同器件。該序列號(hào)可作為1-Wire總線上器件的“地址”，這樣1-Wire總線上的所有器件連同主機(jī)就構(gòu)成了一個(gè)微型局域網(wǎng)(MicroLAN)，它們之間通過(guò)一條公共線來(lái)進(jìn)行通信。1-Wire器件ROM碼的最高有效字節(jié)是循環(huán)冗余校驗(yàn)(CRC)碼，該值基于前面的7個(gè)字節(jié)數(shù)據(jù)。當(dāng)系統(tǒng)主機(jī)開(kāi)始與某個(gè)器件進(jìn)行通信時(shí)，可以讀取8個(gè)ROM字節(jié)，低位在前。如果主機(jī)計(jì)算出的CRC碼與ROM數(shù)據(jù)本身所含的CRC碼相同，則通信有效；反之，則表明有錯(cuò)誤發(fā)生，需重新讀取器件的ROM碼。


圖1. 采用DOW CRC的iButton系統(tǒng)配置

有些iButton器件除了8字節(jié)ROM外，還具有高達(dá)8kB的RAM，主機(jī)可以通過(guò)適當(dāng)?shù)拿钸M(jìn)行訪問(wèn)。即使iButton器件本身不帶CRC硬件電路，如果主機(jī)具有為ROM碼計(jì)算CRC值的能力，就可以采用CRC技術(shù)，開(kāi)發(fā)一個(gè)訪問(wèn)器件RAM部分的子程序。數(shù)據(jù)按正常模式寫入器件，主機(jī)將計(jì)算出的CRC結(jié)果附在數(shù)據(jù)后面，與數(shù)據(jù)一起保存。當(dāng)從iButton器件讀入數(shù)據(jù)時(shí)，則執(zhí)行相反的過(guò)程。主機(jī)將計(jì)算出的CRC值與存儲(chǔ)器中存儲(chǔ)的CRC進(jìn)行比較，如果相同，則認(rèn)為從iButton接收的數(shù)據(jù)有效。為了充分利用CRC來(lái)驗(yàn)證1-Wire總線上進(jìn)行的串行通信的有效性，用戶有必要了解一下CRC的概念和工作原理。此外，無(wú)論是基于硬件實(shí)現(xiàn)還是軟件實(shí)現(xiàn)，還需要掌握通過(guò)主機(jī)計(jì)算CRC的實(shí)用計(jì)算方法。

背景知識(shí)

有多種串行數(shù)據(jù)的檢錯(cuò)方法，一種常用的方法是在被檢測(cè)的數(shù)據(jù)包中包含一個(gè)附加位，用于指示是否出錯(cuò)。如：對(duì)于8位ASCII字符來(lái)說(shuō)，可在其ASCII字符串后添加一位用于檢錯(cuò)。假設(shè)數(shù)據(jù)為11010001，可以附加第9位，使數(shù)據(jù)中"1"的位數(shù)為奇數(shù)個(gè)。這樣，應(yīng)該附加1，數(shù)據(jù)包就變?yōu)椋?11010001，其中帶下劃線的字符為所要求的奇偶校驗(yàn)位，使全部9位數(shù)據(jù)中1的位數(shù)為奇數(shù)。如果收到的數(shù)據(jù)為：111010001，則認(rèn)為接收到的信息有效；但是，若收到的數(shù)據(jù)為：111010101，即左邊第七位接收錯(cuò)誤，此時(shí)數(shù)據(jù)中"1"的個(gè)數(shù)就不再是奇數(shù)，則表明發(fā)生了錯(cuò)誤，進(jìn)而采取相應(yīng)的措施，這種校驗(yàn)方法稱作奇校驗(yàn)。與之類似，如果要求數(shù)據(jù)中1的個(gè)數(shù)總為偶數(shù)，則稱為偶檢驗(yàn)。但是這種檢驗(yàn)方式有其局限性，它只能檢查出數(shù)據(jù)中的奇數(shù)個(gè)錯(cuò)誤。在上例中，如果收到的數(shù)據(jù)為：111011101，其中從左邊數(shù)第6位和第7位都是錯(cuò)的，但此時(shí)奇偶檢測(cè)結(jié)果卻是正確的。對(duì)于這類錯(cuò)誤，因此無(wú)論采用奇校驗(yàn)還是偶校驗(yàn)，都不能夠檢測(cè)出來(lái)。

詳述

Maxim 1-Wire器件的CRC

在串行數(shù)據(jù)流中發(fā)現(xiàn)錯(cuò)誤的最有效檢錯(cuò)方案是循環(huán)冗余校驗(yàn)(CRC)，并且所要求的硬件最少。這里主要介紹Maxim器件的CRC校驗(yàn)的工作及特性，暫不涉及詳細(xì)的數(shù)學(xué)定義和描述。包含在CRC特性之后的數(shù)學(xué)概念在參考資料中進(jìn)行了詳細(xì)介紹。由于CRC實(shí)際上是由硬件實(shí)現(xiàn)，因此很容易理解CRC功能，通常CRC表示為帶反饋的移位寄存器，如圖2所示。另一種方式，也可將CRC看成是變量X的多項(xiàng)式，每一項(xiàng)的系數(shù)為二進(jìn)制數(shù)，這些系數(shù)與移位寄存器的反饋通道直接對(duì)應(yīng)。硬件方案中的移位寄存器的階數(shù)，或多項(xiàng)式中的最高冪次就是將要計(jì)算CRC的位數(shù)。通常數(shù)字通信中使用的CRC編碼方式有CRC-16和CRC-CCITT，它們產(chǎn)生的CRC碼都為16位。Maxim的1-Wire CRC (DOW CRC)的位數(shù)是8位，用于1-Wire器件的64位ROM碼的檢錯(cuò)，該ROM碼包括：最低有效字部分的8位家族碼、與最低有效字節(jié)緊挨著的6字節(jié)48位唯一序列號(hào)、位于最高有效字節(jié)是前56位ROM碼所計(jì)算出的CRC校驗(yàn)碼。圖2中，異或門構(gòu)成的反饋路徑(多項(xiàng)式的系數(shù))決定了CRC檢錯(cuò)性能和錯(cuò)誤定位性能。DOW CRC可檢測(cè)到以下幾種錯(cuò)誤：

1. 任意64位數(shù)據(jù)中的奇數(shù)個(gè)錯(cuò)誤。
2. 所有64位數(shù)據(jù)中的雙位錯(cuò)誤。
3. 包含在8位"window" (1至8位錯(cuò)誤)中的任何字符串的錯(cuò)誤。
4. 絕大多數(shù)長(zhǎng)字符串的錯(cuò)誤。

如圖2所示，輸入數(shù)據(jù)是與移位寄存器的第8階輸出進(jìn)行異或，移位寄存器在數(shù)學(xué)上可被視為除法電路，其中輸入數(shù)據(jù)為被除數(shù)，反饋移位寄存器為除數(shù)，計(jì)算所得的商數(shù)在這里沒(méi)有價(jià)值，計(jì)算后的余數(shù)就是指定數(shù)據(jù)流的CRC碼。當(dāng)最后一位數(shù)據(jù)移入之后，移位寄存器的值就是最后的余數(shù)。通過(guò)用移位寄存器來(lái)實(shí)現(xiàn)CRC的方案不難看出，最后得到的結(jié)果(CRC碼)是根據(jù)要發(fā)送的所有數(shù)據(jù)，通過(guò)一種非常復(fù)雜的過(guò)程獲得的，故此，這種校驗(yàn)算法基本上可以檢測(cè)出數(shù)據(jù)中大多數(shù)的錯(cuò)誤，只有極少數(shù)特別極端情況的差錯(cuò)無(wú)法檢測(cè)到。


圖2. Maxim 1-Wire 8位CRC

例2所示是當(dāng)所有數(shù)據(jù)都移入之后計(jì)算出的CRC碼。在計(jì)算開(kāi)始時(shí)移位寄存器全置為‘0’，計(jì)算由64位ROM的LSB位開(kāi)始，本例中家族碼為02。當(dāng)56位數(shù)據(jù)(序列號(hào)加上家族碼)都移入后，移位寄存器的的值變?yōu)锳2，這就是輸入數(shù)據(jù)流的DOW CRC碼。如果把計(jì)算得到的CRC碼(A2)的8個(gè)位接在數(shù)據(jù)流的后面繼續(xù)移入移位寄存器，那么當(dāng)64位數(shù)據(jù)全部輸入后，移位寄存器的值就全部為0。在DOW CRC算法中，就是利用這樣一個(gè)特性來(lái)檢查是否發(fā)生了錯(cuò)誤的。把任意的8位數(shù)據(jù)移入移位寄存器到得到的8位數(shù)字接在移入的數(shù)據(jù)的后面繼續(xù)移入移位寄存器，那么第8位數(shù)據(jù)位移入后的移位寄存器的結(jié)果總為00，通過(guò)觀察不難注意到，移位寄存器的第8階的值總是和輸入的數(shù)據(jù)位相等，這樣就使得用來(lái)控制反饋的異或門的輸出和移位寄存器第一階的下一個(gè)狀態(tài)總為邏輯0，這樣一來(lái)，當(dāng)數(shù)據(jù)移入時(shí)，從左到右移入的每一位都是0，直到第8位后移位寄存器的每一位都被置0為止。Maxim 1-Wire 64位ROM就是利用上述特性來(lái)簡(jiǎn)化64位ROM的硬件設(shè)計(jì)的。主機(jī)端的移位寄存器首先被清0，然后讀取包括CRC碼在內(nèi)的64位ROM。如果讀取正確，則移位寄存器為零，易于檢測(cè)。如果移位寄存器的值不是全部為0，則(表示發(fā)生了錯(cuò)誤)必須重新讀取數(shù)據(jù)。

到現(xiàn)在為止，我們一直圍繞CRC硬件實(shí)現(xiàn)方法進(jìn)行討論，當(dāng)然，與硬件方法等價(jià)的軟件解決方案，則是另一種計(jì)算DOW CRC碼的實(shí)現(xiàn)方法。如何編寫程序代碼如例1示例所示。需注意的是，寄存器A與常量18的異或運(yùn)算是為了實(shí)現(xiàn)DOW CRC中第4、5階之后的的異或反饋門，如圖2所示。另一種軟件實(shí)現(xiàn)方案就是簡(jiǎn)單地構(gòu)建一個(gè)查詢表，可以根據(jù)CRC寄存器中的8位值和新的8位數(shù)據(jù)直接讀取。對(duì)于CRC寄存器為00的這種簡(jiǎn)單情況，可以推出輸入數(shù)據(jù)的256種不同的組合，并將它們保存距陣中，該距陣索引值等于輸入數(shù)據(jù)(即索引值為：I = 0至255)。很明顯，如果CRC寄存器的當(dāng)前值不是00，那么對(duì)于任一個(gè)當(dāng)前CRC碼和輸入字來(lái)說(shuō)，其查詢表的值與CRC寄存器為0的簡(jiǎn)單情況相同，但表的索引值計(jì)算方式應(yīng)改為：

新CRC = 表[I]，I = 0至255 ;
這里，I = (當(dāng)前CRC) EXOR (輸入字)。

當(dāng)CRC寄存器的當(dāng)前值為00時(shí)，該等式就和上述簡(jiǎn)單情況一樣。由于第二種方案是以字節(jié)為基礎(chǔ)進(jìn)行操作，而不是上例中面向位的操作，因此可以節(jié)省計(jì)算時(shí)間。但該方法會(huì)占用存儲(chǔ)器的空間，因?yàn)椴樵儽硎谴鎯?chǔ)在存儲(chǔ)器中的，占用256字節(jié)，而在第一種方案中除了程序代碼外，不再需要占用任何存儲(chǔ)空間。例3為第二種方案的程序代碼示例，表1給出了上例中查詢表實(shí)現(xiàn)方法。在生成CRC碼時(shí)，DOW CRC的兩個(gè)特性有助于其代碼的調(diào)試，其中的第一個(gè)特性在硬件實(shí)現(xiàn)時(shí)已介紹過(guò)，即：如果下一個(gè)輸入數(shù)據(jù)等于當(dāng)前CRC寄存器值，則計(jì)算后的CRC碼肯定為00 (見(jiàn)前面的說(shuō)明)。其第二個(gè)特性也能夠用于確認(rèn)代碼是否正確，出現(xiàn)在輸入數(shù)據(jù)等于當(dāng)前CRC寄存器的反碼時(shí)。對(duì)于DOW CRC算法來(lái)說(shuō)，計(jì)算出的CRC碼將為35H，即十進(jìn)制的53 。當(dāng)輸入數(shù)據(jù)為CRC寄存器反碼時(shí)，通過(guò)觀察CRC寄存器工作方式，就可以解釋這種特性，如表2所示。

例1. 匯編語(yǔ)言程序

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
;
ZER	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)]

例3. DOW CRC查詢函數(shù)

Var
	CRC : Byte;
Procedure Do_CRC(X: Byte);
{
	This procedure calculates the cumulative Maxim 1-Wire CRC of all bytes passed to it.
The result accumulates in the global variable CRC.
}
Const
	Table : Array[0..255] of Byte = (

	0, 94, 188, 226, 97, 63, 221, 131, 194, 156, 126, 32, 163, 253, 31, 65,
	157, 195, 33, 127, 252, 162, 64, 30, 95, 1, 227, 189, 62, 96, 130, 220,
	35, 125, 159, 193, 66, 28, 254, 160, 225, 191, 93, 3, 128, 222, 60, 98,
	190, 224, 2, 92, 223, 129, 99, 61, 124, 34, 192, 158, 29, 67, 161, 255,
	70, 24, 250, 164, 39, 121, 155, 197, 132, 218, 56, 102, 229, 187, 89, 7,
	219, 133, 103, 57, 186, 228, 6, 88, 25, 71, 165, 251, 120, 38, 196, 154,
	101, 59, 217, 135, 4, 90, 184, 230, 167, 249, 27, 69, 198, 152, 122, 36,
	248, 166, 68, 26, 153, 199, 37, 123, 58, 100, 134, 216, 91, 5, 231, 185,
	140, 210, 48, 110, 237, 179, 81, 15, 78, 16, 242, 172, 47, 113, 147, 205,
	17, 79, 173, 243, 112, 46, 204, 146, 211, 141, 111, 49, 178, 236, 14, 80,
	175, 241, 19, 77, 206, 144, 114, 44, 109, 51, 209, 143, 12, 82, 176, 238,
	50, 108, 142, 208, 83, 13, 239, 177, 240, 174, 76, 18, 145, 207, 45, 115,
	202, 148, 118, 40, 171, 245, 23, 73, 8, 86, 180, 234, 105, 55, 213, 139,
	87, 9, 235, 181, 54, 104, 138, 212, 149, 203, 41, 119, 244, 170, 72, 22,
	233, 183, 85, 11, 136, 214, 52, 106, 43, 117, 151, 201, 74, 20, 246, 168,
	116, 42, 200, 150, 21, 75, 169, 247, 182, 232, 10, 84, 215, 137, 107, 53);

Begin
	CRC := Table[CRC xor X];
End;

表1. 查表方式計(jì)算DOW CRC

Current CRC Value (= Current Table Index)	Input Data	New Index (= Current CRC xor Input Data)	Table (New Index) (= New CRC Value)
0000 0000 = 00 Hex	0000 0010 = 02 Hex	(00 H xor 02 H) = 02 Hex = 2 Dec	Table[2]= 1011 1100 = BC Hex = 188 Dec
1011 1100 = BC Hex	0001 1100 = 1C Hex	(BC H xor 1C H) = A0 Hex = 160 Dec	Table[160]= 1010 1111 = AF Hex = 175 Dec
1010 1111 = AF Hex	1011 1000 = B8 Hex	(AF H xor B8 H) = 17 Hex = 23 Dec	Table[23]= 0001 1110 = 1E Hex = 30 Dec
0001 1110 = 1E Hex	0000 0001 = 01 Hex	(1E H xor 01 H) = 1 F Hex = 31 Dec	Table[31]= 1101 110 = DC Hex = 220 Dec
1101 1100 = DC Hex	0000 0000 = 00 Hex	(DC H xor 00 H) = DC Hex = 220 Dec	Table[220]= 1111 0100 = F4 Hex = 244 Dec
11110100 = F4 Hex	0000 0000 = 00 Hex	(F4 H xor 00 H) = F4 Hex = 244 Dec	Table [244]= 0001 0101 = 15 Hex = 21 Dec
0001 0101 = 15 Hex	0000 0000 = 00 Hex	(15 H xor 00 H) = 15 Hex = 21 Dec	Table[21]= 1010 0010 = A2 Hex = 162 Dec
1010 0010 = A2 Hex	10100010 = A2 Hex	(A2 H xor A2 H) = Hex = 0 Dec	Table[0]=0000 0000 = 00 Hex = 0 Dec

帶有CRC寄存器1的補(bǔ)碼CRC寄存器

表2. CRC寄存器值輸入

X0	X1	X2	X3	X4	X5	X6	X7	X7*
1	X0	X1	X2	X3*	X4*	X5	X6	X6*
1	1	X0	X1	X2*	X3	X4*	X5	X5*
1	1	1	X0	X1*	X2*	X3	X4*	X4*
0	1	1	1	X0	X1*	X2	X3	X3*
1	0	1	1	0	X0*	X1*	X2	X2*
1	1	0	1	0	1	X0*	X1*	X1*
0	1	1	0	1	0	1	X0*	X0*
0	0	1	1	0	1	0	1	Final CRC Value = 35 Hex, 53 Decimal

注釋：Xi* = Xi的反碼

iButton RAM中CRC-16的算法

如前所述，一些iButton器件除了內(nèi)部唯一的8字節(jié)ROM碼，還有RAM存儲(chǔ)器。與內(nèi)部的8字節(jié)ROM碼相比，RAM中存儲(chǔ)的數(shù)據(jù)量要大得多，因此Maxim推薦使用16位CRC碼而不是ROM所使用的8位DOW CRC，以確保數(shù)據(jù)的完整性。這種特殊的16位CRC通常稱為CRC-16。圖3給出了這種16位CRC的移位寄存器的硬件實(shí)現(xiàn)圖和相應(yīng)的多項(xiàng)表達(dá)式，圖中的移位寄存器有16階，其表達(dá)式也有16次冪項(xiàng)。如前所述，iButton器件自身并不產(chǎn)生CRC碼，而是由主機(jī)生成16位CRC碼并將其附加在實(shí)際數(shù)據(jù)之后。由于iButton的“通信通道”，如兩個(gè)金屬接觸面，存在不確定性，數(shù)據(jù)傳輸可能會(huì)出現(xiàn)一些錯(cuò)誤，分為三類：第一，短暫的連接中斷引起的數(shù)據(jù)傳輸中小部分?jǐn)?shù)據(jù)位出錯(cuò)，CRC-16可檢測(cè)出這類錯(cuò)誤；第二類錯(cuò)誤是完全脫離接觸引起的，如：當(dāng)iButton器件快速移離讀寫頭時(shí)。

將導(dǎo)致后續(xù)部分的讀入數(shù)據(jù)為邏輯1，這是因?yàn)槲催B接iButton器件時(shí)，主機(jī)將解釋所有的接收數(shù)據(jù)為1。 CRC-16在大多數(shù)情況下可以檢測(cè)出這類錯(cuò)誤。第三類錯(cuò)誤是由讀寫頭短路引起的，這可能因?yàn)閕Button器件沒(méi)有正確插入或iButton器件在閱讀器內(nèi)大幅度翹起導(dǎo)致的。讀寫頭短路會(huì)使主機(jī)把數(shù)據(jù)全讀為0，此時(shí)采用CRC進(jìn)行校驗(yàn)時(shí)，就會(huì)出現(xiàn)問(wèn)題。由于確認(rèn)數(shù)據(jù)是否有效的方法是判斷主機(jī)在讀取數(shù)據(jù)和附加的CRC之后，計(jì)算出的CRC碼是否全為0000H (采用16位CRC)。當(dāng)閱讀器短路時(shí)，讀到的數(shù)據(jù)和CRC值全部為0，此時(shí)讀操作已經(jīng)出錯(cuò)，但由主機(jī)計(jì)算出的CRC值將錯(cuò)誤地指示該讀操作是有效的。為了避免這種情況的發(fā)生，Maxim推薦將CRC-16反碼(CRC-16*)隨同數(shù)據(jù)一起寫入RAM。當(dāng)采用無(wú)補(bǔ)碼的CRC-16時(shí)，iButton的數(shù)據(jù)驗(yàn)證過(guò)程與DOW CRC相似，即，主機(jī)把CRC寄存器初始化成0000H，然后從iButton讀取全部數(shù)據(jù)和存儲(chǔ)的CRC-16，則最終計(jì)算出來(lái)的結(jié)果應(yīng)為0000H。如果采用CRC-16*，在iButton中保存的就是CRC-16的反碼和數(shù)據(jù)。進(jìn)行CRC校驗(yàn)時(shí)，主機(jī)同樣把CRC寄存器初始化成0H，然后從iButton讀取數(shù)據(jù)和CRC-16*，如果操作沒(méi)有錯(cuò)誤的話，最后的結(jié)果應(yīng)該是B001H。這樣大大地提高了系統(tǒng)可靠性，讀寫頭短路造成的錯(cuò)誤就不會(huì)被漏檢。至于為什么CRC-16具有這些特性，可通過(guò)與之相似的DOW CRC的分析(見(jiàn)圖3和圖5)來(lái)解釋。在理論上16位CRC的操作與此前介紹的8位CRC完全相同，只是由于采用的是16的CRC，性能有所改善。對(duì)于CRC-16函數(shù)，可以檢測(cè)到以下幾類錯(cuò)誤：

1. 任何數(shù)據(jù)記錄中的奇數(shù)個(gè)錯(cuò)誤。
2. 任何數(shù)據(jù)記錄中的雙位錯(cuò)誤。
3. 包含在16位"window" (1至16錯(cuò)誤)中的任何字符串的錯(cuò)誤。
4. 絕大多數(shù)長(zhǎng)字符串的錯(cuò)誤。

圖3. CRC-16硬件實(shí)現(xiàn)及其多項(xiàng)式表示

圖3給出了CRC-16函數(shù)的硬件實(shí)現(xiàn)圖，例4則列出了與其硬件相對(duì)應(yīng)的軟件實(shí)現(xiàn)方案，采用位操作計(jì)算CRC-16值。之前很少有高效的查詢表軟件解決方案，8位DOW CRC查詢表的基礎(chǔ)概念也同樣適用于CRC-16，只需對(duì)8位的程序稍加改動(dòng)即可。但是，如果仍然采用DOW CRC實(shí)現(xiàn)方法的話，要把CRC-16全部16位結(jié)果全部放進(jìn)一個(gè)查詢表，則表中就會(huì)有216也就是65536個(gè)記錄(占用的空間將會(huì)很大)。與DOW CRC不同的實(shí)現(xiàn)方法如例5所示，圖中采用兩個(gè)256位表來(lái)計(jì)算和存儲(chǔ)16位CRC值，其中一個(gè)表包含CRC的高8位，另一個(gè)存放低8位。任何一個(gè)16位CRC都可以分為代表高8位的Current_CRC16_Hi和代表低8位的Current_CRC16_Lo兩部分。對(duì)于任何一個(gè)輸入字節(jié)，在高階字節(jié)表中決定新的CRC值高階字節(jié)(New_CRC16_Hi)的索引計(jì)算公式如下：

New_CRC16_Hi = CRC16_Tabhi[I], I = 0至255; 這里：I = (Current_CRC16_Lo) EXOR (輸入字)

在低階字節(jié)表中決定新的CRC值低階字節(jié)(New_CRC16_Lo)的索引計(jì)算公式如下：

New_CRC16_Lo = (CRC16_Tablo[I]) EXOR (Current_ CRC16_Hi) I = 0至255;
這里：I = (Current_CRC16_Lo) EXOR (輸入字)

圖4所示為如何實(shí)現(xiàn)該方法的一個(gè)實(shí)例。

例4. 計(jì)算CRC-16的匯編語(yǔ)言程序

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 ; rotate	it
	mov crc_hi, a	; and save it
	mov a, crc_lo	; again, carry is okay
	rrc a ; rotate	it
	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. 利用查找表進(jìn)行CRC-16計(jì)算的匯編程序

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_tabl
	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計(jì)算和查表方法的比較

例6描述了一種令人感興趣的的中間方案。該程序利用圖5所示的公式，通過(guò)對(duì)當(dāng)前整個(gè)CRC的值和輸入字節(jié)進(jìn)行運(yùn)算來(lái)生成CRC-16。同時(shí)在圖中還給出了該等式的推導(dǎo)過(guò)程，用字母字符表示當(dāng)前16位CRC值，用數(shù)字字符表示輸入字節(jié)的位。8次移位后就得到了所示的等式，這些等式隨后可以預(yù)計(jì)算出大部分的新CRC值。注意：例如ABCDEFGH01234567 (定義為所有位異或的結(jié)果)數(shù)字量等于輸入數(shù)據(jù)和當(dāng)前CRC低字節(jié)的奇偶性。與前面的按位計(jì)算或查表方法相比較，這種方法可以減少計(jì)算時(shí)間，或減少存儲(chǔ)空間。最后，應(yīng)說(shuō)明的是，前面介紹的CRC-16函數(shù)的兩種特性在這里也用作調(diào)試準(zhǔn)則。其第一個(gè)特性與DOW CRC的情況完全相同，即如果當(dāng)前CRC寄存器的16位內(nèi)容作為后續(xù)的16位輸入數(shù)據(jù)，則得到的CRC也總為0000H。CRC功能的第二個(gè)特性與DOW CRC相似，如果把當(dāng)前CRC寄存器的16位反碼也作為后續(xù)的16位輸入數(shù)據(jù)，則CRC結(jié)果總為B0 01H。這兩個(gè)CRC-16特性的證明方法也與DOW CRC相似。

例6. 高速CRC-16算法的匯編語(yǔ)言程序

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

詳細(xì)圖片(GIF)
圖5. 高速CRC-16的計(jì)算方法

參考文獻(xiàn)
Stallings, William, Ph.D., Data and Computer Communications. 2nd ed., New York: Macmillan Publishing. pp. 107-112.
Buller, Jon, "High Speed Software CRC Generation", EDN, Volume 36, #25, p. 210.