電子發燒友App
摘要：全部1-Wire?器件，包括iButton?器件，都具有唯一的8字節注冊碼，儲存在只讀存儲器(ROM)中。該注冊碼在1-Wire總線上用作唯一的網絡地址。為確保數據通信的完整性，每個注冊碼的一個字節是一個DOW CRC字節。本篇應用筆記說明了8位DOW CRC的計算方法以及用于驗證器件存儲器記錄的16位CRC的計算。DOW CRC和CRC-16還會在選擇1-Wire器件驗證數據的硬件中產生。
圖1. 采用DOW CRC的iButton系統配置
有些iButton器件除了8字節ROM外，還具有高達8kB的RAM，主機可以通過適當的命令進行訪問。即使iButton器件本身不帶CRC硬件電路，如果主機具有為ROM碼計算CRC值的能力，就可以采用CRC技術，開發一個訪問器件RAM部分的子程序。數據按正常模式寫入器件，主機將計算出的CRC結果附在數據后面，與數據一起保存。當從iButton器件讀入數據時，則執行相反的過程。主機將計算出的CRC值與存儲器中存儲的CRC進行比較，如果相同，則認為從iButton接收的數據有效。為了充分利用CRC來驗證1-Wire總線上進行的串行通信的有效性，用戶有必要了解一下CRC的概念和工作原理。此外，無論是基于硬件實現還是軟件實現，還需要掌握通過主機計算CRC的實用計算方法。
圖2. Maxim 1-Wire 8位CRC
例2所示是當所有數據都移入之后計算出的CRC碼。在計算開始時移位寄存器全置為‘0’，計算由64位ROM的LSB位開始，本例中家族碼為02。當56位數據(序列號加上家族碼)都移入后，移位寄存器的的值變為A2，這就是輸入數據流的DOW CRC碼。如果把計算得到的CRC碼(A2)的8個位接在數據流的后面繼續移入移位寄存器，那么當64位數據全部輸入后，移位寄存器的值就全部為0。在DOW CRC算法中，就是利用這樣一個特性來檢查是否發生了錯誤的。把任意的8位數據移入移位寄存器到得到的8位數字接在移入的數據的后面繼續移入移位寄存器，那么第8位數據位移入后的移位寄存器的結果總為00，通過觀察不難注意到，移位寄存器的第8階的值總是和輸入的數據位相等，這樣就使得用來控制反饋的異或門的輸出和移位寄存器第一階的下一個狀態總為邏輯0，這樣一來，當數據移入時，從左到右移入的每一位都是0，直到第8位后移位寄存器的每一位都被置0為止。Maxim 1-Wire 64位ROM就是利用上述特性來簡化64位ROM的硬件設計的。主機端的移位寄存器首先被清0，然后讀取包括CRC碼在內的64位ROM。如果讀取正確，則移位寄存器為零，易于檢測。如果移位寄存器的值不是全部為0，則(表示發生了錯誤)必須重新讀取數據。
到現在為止，我們一直圍繞CRC硬件實現方法進行討論，當然，與硬件方法等價的軟件解決方案，則是另一種計算DOW CRC碼的實現方法。如何編寫程序代碼如例1示例所示。需注意的是，寄存器A與常量18的異或運算是為了實現DOW CRC中第4、5階之后的的異或反饋門，如圖2所示。另一種軟件實現方案就是簡單地構建一個查詢表，可以根據CRC寄存器中的8位值和新的8位數據直接讀取。對于CRC寄存器為00的這種簡單情況，可以推出輸入數據的256種不同的組合，并將它們保存距陣中，該距陣索引值等于輸入數據(即索引值為：I = 0至255)。很明顯，如果CRC寄存器的當前值不是00，那么對于任一個當前CRC碼和輸入字來說，其查詢表的值與CRC寄存器為0的簡單情況相同，但表的索引值計算方式應改為：
新CRC = 表[I]，I = 0至255 ;
這里，I = (當前CRC) EXOR (輸入字)。
當CRC寄存器的當前值為00時，該等式就和上述簡單情況一樣。由于第二種方案是以字節為基礎進行操作，而不是上例中面向位的操作，因此可以節省計算時間。但該方法會占用存儲器的空間，因為查詢表是存儲在存儲器中的，占用256字節，而在第一種方案中除了程序代碼外，不再需要占用任何存儲空間。例3為第二種方案的程序代碼示例，表1給出了上例中查詢表實現方法。在生成CRC碼時，DOW CRC的兩個特性有助于其代碼的調試，其中的第一個特性在硬件實現時已介紹過，即：如果下一個輸入數據等于當前CRC寄存器值，則計算后的CRC碼肯定為00 (見前面的說明)。其第二個特性也能夠用于確認代碼是否正確，出現在輸入數據等于當前CRC寄存器的反碼時。對于DOW CRC算法來說，計算出的CRC碼將為35H，即十進制的53 。當輸入數據為CRC寄存器反碼時，通過觀察CRC寄存器工作方式，就可以解釋這種特性，如表2所示。
例3. DOW CRC查詢函數
注釋：Xi* = Xi的反碼
將導致后續部分的讀入數據為邏輯1，這是因為未連接iButton器件時，主機將解釋所有的接收數據為1。 CRC-16在大多數情況下可以檢測出這類錯誤。第三類錯誤是由讀寫頭短路引起的，這可能因為iButton器件沒有正確插入或iButton器件在閱讀器內大幅度翹起導致的。讀寫頭短路會使主機把數據全讀為0，此時采用CRC進行校驗時，就會出現問題。由于確認數據是否有效的方法是判斷主機在讀取數據和附加的CRC之后，計算出的CRC碼是否全為0000H (采用16位CRC)。當閱讀器短路時，讀到的數據和CRC值全部為0，此時讀操作已經出錯，但由主機計算出的CRC值將錯誤地指示該讀操作是有效的。為了避免這種情況的發生，Maxim推薦將CRC-16反碼(CRC-16*)隨同數據一起寫入RAM。當采用無補碼的CRC-16時，iButton的數據驗證過程與DOW CRC相似，即，主機把CRC寄存器初始化成0000H，然后從iButton讀取全部數據和存儲的CRC-16，則最終計算出來的結果應為0000H。如果采用CRC-16*，在iButton中保存的就是CRC-16的反碼和數據。進行CRC校驗時，主機同樣把CRC寄存器初始化成0H，然后從iButton讀取數據和CRC-16*，如果操作沒有錯誤的話，最后的結果應該是B001H。這樣大大地提高了系統可靠性，讀寫頭短路造成的錯誤就不會被漏檢。至于為什么CRC-16具有這些特性，可通過與之相似的DOW CRC的分析(見圖3和圖5)來解釋。在理論上16位CRC的操作與此前介紹的8位CRC完全相同，只是由于采用的是16的CRC，性能有所改善。對于CRC-16函數，可以檢測到以下幾類錯誤：
圖3. CRC-16硬件實現及其多項式表示
圖3給出了CRC-16函數的硬件實現圖，例4則列出了與其硬件相對應的軟件實現方案，采用位操作計算CRC-16值。之前很少有高效的查詢表軟件解決方案，8位DOW CRC查詢表的基礎概念也同樣適用于CRC-16，只需對8位的程序稍加改動即可。但是，如果仍然采用DOW CRC實現方法的話，要把CRC-16全部16位結果全部放進一個查詢表，則表中就會有216也就是65536個記錄(占用的空間將會很大)。與DOW CRC不同的實現方法如例5所示，圖中采用兩個256位表來計算和存儲16位CRC值，其中一個表包含CRC的高8位，另一個存放低8位。任何一個16位CRC都可以分為代表高8位的Current_CRC16_Hi和代表低8位的Current_CRC16_Lo兩部分。對于任何一個輸入字節，在高階字節表中決定新的CRC值高階字節(New_CRC16_Hi)的索引計算公式如下：
New_CRC16_Hi = CRC16_Tabhi[I], I = 0至255; 這里：I = (Current_CRC16_Lo) EXOR (輸入字)
在低階字節表中決定新的CRC值低階字節(New_CRC16_Lo)的索引計算公式如下：
New_CRC16_Lo = (CRC16_Tablo[I]) EXOR (Current_ CRC16_Hi) I = 0至255;
這里：I = (Current_CRC16_Lo) EXOR (輸入字)
圖4所示為如何實現該方法的一個實例。
圖4. CRC-16計算和查表方法的比較
例6描述了一種令人感興趣的的中間方案。該程序利用圖5所示的公式，通過對當前整個CRC的值和輸入字節進行運算來生成CRC-16。同時在圖中還給出了該等式的推導過程，用字母字符表示當前16位CRC值，用數字字符表示輸入字節的位。8次移位后就得到了所示的等式，這些等式隨后可以預計算出大部分的新CRC值。注意：例如ABCDEFGH01234567 (定義為所有位異或的結果)數字量等于輸入數據和當前CRC低字節的奇偶性。與前面的按位計算或查表方法相比較，這種方法可以減少計算時間，或減少存儲空間。最后，應說明的是，前面介紹的CRC-16函數的兩種特性在這里也用作調試準則。其第一個特性與DOW CRC的情況完全相同，即如果當前CRC寄存器的16位內容作為后續的16位輸入數據，則得到的CRC也總為0000H。CRC功能的第二個特性與DOW CRC相似，如果把當前CRC寄存器的16位反碼也作為后續的16位輸入數據，則CRC結果總為B0 01H。這兩個CRC-16特性的證明方法也與DOW CRC相似。
詳細圖片(GIF)
圖5. 高速CRC-16的計算方法
參考文獻
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.
引言
Maxim的iButton系列產品是通過單線按照1-Wire協議傳送特定命令序列，進行數據通信。該系列產品都有個很重要的特性，就是在出廠前每個器件都被寫入了唯一的8字節ROM碼。其ROM碼組成如圖1所示，最低有效字節為家族代碼，代表iButton器件的類型，如：DS1990A的家族碼為01，DS1991的家族碼為02。由于在同一條1-Wire總線上可同時掛接多個相同系列或不同系列的1-Wire器件，因此主機必須能夠決定如何正確地訪問位于1-Wire總線上的各個器件，這一點尤為重要。家族碼提供器件的類型，隨后的6個字節是器件的唯一序列號，用以區分同一個系列的不同器件。該序列號可作為1-Wire總線上器件的“地址”，這樣1-Wire總線上的所有器件連同主機就構成了一個微型局域網(MicroLAN)，它們之間通過一條公共線來進行通信。1-Wire器件ROM碼的最高有效字節是循環冗余校驗(CRC)碼，該值基于前面的7個字節數據。當系統主機開始與某個器件進行通信時，可以讀取8個ROM字節，低位在前。如果主機計算出的CRC碼與ROM數據本身所含的CRC碼相同，則通信有效；反之，則表明有錯誤發生，需重新讀取器件的ROM碼。圖1. 采用DOW CRC的iButton系統配置
有些iButton器件除了8字節ROM外，還具有高達8kB的RAM，主機可以通過適當的命令進行訪問。即使iButton器件本身不帶CRC硬件電路，如果主機具有為ROM碼計算CRC值的能力，就可以采用CRC技術，開發一個訪問器件RAM部分的子程序。數據按正常模式寫入器件，主機將計算出的CRC結果附在數據后面，與數據一起保存。當從iButton器件讀入數據時，則執行相反的過程。主機將計算出的CRC值與存儲器中存儲的CRC進行比較，如果相同，則認為從iButton接收的數據有效。為了充分利用CRC來驗證1-Wire總線上進行的串行通信的有效性，用戶有必要了解一下CRC的概念和工作原理。此外，無論是基于硬件實現還是軟件實現，還需要掌握通過主機計算CRC的實用計算方法。
背景知識
有多種串行數據的檢錯方法，一種常用的方法是在被檢測的數據包中包含一個附加位，用于指示是否出錯。如：對于8位ASCII字符來說，可在其ASCII字符串后添加一位用于檢錯。假設數據為11010001，可以附加第9位，使數據中"1"的位數為奇數個。這樣，應該附加1，數據包就變為：111010001，其中帶下劃線的字符為所要求的奇偶校驗位，使全部9位數據中1的位數為奇數。如果收到的數據為：111010001，則認為接收到的信息有效；但是，若收到的數據為：111010101，即左邊第七位接收錯誤，此時數據中"1"的個數就不再是奇數，則表明發生了錯誤，進而采取相應的措施，這種校驗方法稱作奇校驗。與之類似，如果要求數據中1的個數總為偶數，則稱為偶檢驗。但是這種檢驗方式有其局限性，它只能檢查出數據中的奇數個錯誤。在上例中，如果收到的數據為：111011101，其中從左邊數第6位和第7位都是錯的，但此時奇偶檢測結果卻是正確的。對于這類錯誤，因此無論采用奇校驗還是偶校驗，都不能夠檢測出來。詳述
Maxim 1-Wire器件的CRC
在串行數據流中發現錯誤的最有效檢錯方案是循環冗余校驗(CRC)，并且所要求的硬件最少。這里主要介紹Maxim器件的CRC校驗的工作及特性，暫不涉及詳細的數學定義和描述。包含在CRC特性之后的數學概念在參考資料中進行了詳細介紹。由于CRC實際上是由硬件實現，因此很容易理解CRC功能，通常CRC表示為帶反饋的移位寄存器，如圖2所示。另一種方式，也可將CRC看成是變量X的多項式，每一項的系數為二進制數，這些系數與移位寄存器的反饋通道直接對應。硬件方案中的移位寄存器的階數，或多項式中的最高冪次就是將要計算CRC的位數。通常數字通信中使用的CRC編碼方式有CRC-16和CRC-CCITT，它們產生的CRC碼都為16位。Maxim的1-Wire CRC (DOW CRC)的位數是8位，用于1-Wire器件的64位ROM碼的檢錯，該ROM碼包括：最低有效字部分的8位家族碼、與最低有效字節緊挨著的6字節48位唯一序列號、位于最高有效字節是前56位ROM碼所計算出的CRC校驗碼。圖2中，異或門構成的反饋路徑(多項式的系數)決定了CRC檢錯性能和錯誤定位性能。DOW CRC可檢測到以下幾種錯誤：- 任意64位數據中的奇數個錯誤。
- 所有64位數據中的雙位錯誤。
- 包含在8位"window" (1至8位錯誤)中的任何字符串的錯誤。
- 絕大多數長字符串的錯誤。
圖2. Maxim 1-Wire 8位CRC
例2所示是當所有數據都移入之后計算出的CRC碼。在計算開始時移位寄存器全置為‘0’，計算由64位ROM的LSB位開始，本例中家族碼為02。當56位數據(序列號加上家族碼)都移入后，移位寄存器的的值變為A2，這就是輸入數據流的DOW CRC碼。如果把計算得到的CRC碼(A2)的8個位接在數據流的后面繼續移入移位寄存器，那么當64位數據全部輸入后，移位寄存器的值就全部為0。在DOW CRC算法中，就是利用這樣一個特性來檢查是否發生了錯誤的。把任意的8位數據移入移位寄存器到得到的8位數字接在移入的數據的后面繼續移入移位寄存器，那么第8位數據位移入后的移位寄存器的結果總為00，通過觀察不難注意到，移位寄存器的第8階的值總是和輸入的數據位相等，這樣就使得用來控制反饋的異或門的輸出和移位寄存器第一階的下一個狀態總為邏輯0，這樣一來，當數據移入時，從左到右移入的每一位都是0，直到第8位后移位寄存器的每一位都被置0為止。Maxim 1-Wire 64位ROM就是利用上述特性來簡化64位ROM的硬件設計的。主機端的移位寄存器首先被清0，然后讀取包括CRC碼在內的64位ROM。如果讀取正確，則移位寄存器為零，易于檢測。如果移位寄存器的值不是全部為0，則(表示發生了錯誤)必須重新讀取數據。
到現在為止，我們一直圍繞CRC硬件實現方法進行討論，當然，與硬件方法等價的軟件解決方案，則是另一種計算DOW CRC碼的實現方法。如何編寫程序代碼如例1示例所示。需注意的是，寄存器A與常量18的異或運算是為了實現DOW CRC中第4、5階之后的的異或反饋門，如圖2所示。另一種軟件實現方案就是簡單地構建一個查詢表，可以根據CRC寄存器中的8位值和新的8位數據直接讀取。對于CRC寄存器為00的這種簡單情況，可以推出輸入數據的256種不同的組合，并將它們保存距陣中，該距陣索引值等于輸入數據(即索引值為：I = 0至255)。很明顯，如果CRC寄存器的當前值不是00，那么對于任一個當前CRC碼和輸入字來說，其查詢表的值與CRC寄存器為0的簡單情況相同，但表的索引值計算方式應改為：
新CRC = 表[I]，I = 0至255 ;
這里，I = (當前CRC) EXOR (輸入字)。
當CRC寄存器的當前值為00時，該等式就和上述簡單情況一樣。由于第二種方案是以字節為基礎進行操作，而不是上例中面向位的操作，因此可以節省計算時間。但該方法會占用存儲器的空間，因為查詢表是存儲在存儲器中的，占用256字節，而在第一種方案中除了程序代碼外，不再需要占用任何存儲空間。例3為第二種方案的程序代碼示例，表1給出了上例中查詢表實現方法。在生成CRC碼時，DOW CRC的兩個特性有助于其代碼的調試，其中的第一個特性在硬件實現時已介紹過，即：如果下一個輸入數據等于當前CRC寄存器值，則計算后的CRC碼肯定為00 (見前面的說明)。其第二個特性也能夠用于確認代碼是否正確，出現在輸入數據等于當前CRC寄存器的反碼時。對于DOW CRC算法來說，計算出的CRC碼將為35H，即十進制的53 。當輸入數據為CRC寄存器反碼時，通過觀察CRC寄存器工作方式，就可以解釋這種特性，如表2所示。
例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 ; 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查詢函數
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. 查表方式計算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的補碼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 |
iButton RAM中CRC-16的算法
如前所述，一些iButton器件除了內部唯一的8字節ROM碼，還有RAM存儲器。與內部的8字節ROM碼相比，RAM中存儲的數據量要大得多，因此Maxim推薦使用16位CRC碼而不是ROM所使用的8位DOW CRC，以確保數據的完整性。這種特殊的16位CRC通常稱為CRC-16。圖3給出了這種16位CRC的移位寄存器的硬件實現圖和相應的多項表達式，圖中的移位寄存器有16階，其表達式也有16次冪項。如前所述，iButton器件自身并不產生CRC碼，而是由主機生成16位CRC碼并將其附加在實際數據之后。由于iButton的“通信通道”，如兩個金屬接觸面，存在不確定性，數據傳輸可能會出現一些錯誤，分為三類：第一，短暫的連接中斷引起的數據傳輸中小部分數據位出錯，CRC-16可檢測出這類錯誤；第二類錯誤是完全脫離接觸引起的，如：當iButton器件快速移離讀寫頭時。將導致后續部分的讀入數據為邏輯1，這是因為未連接iButton器件時，主機將解釋所有的接收數據為1。 CRC-16在大多數情況下可以檢測出這類錯誤。第三類錯誤是由讀寫頭短路引起的，這可能因為iButton器件沒有正確插入或iButton器件在閱讀器內大幅度翹起導致的。讀寫頭短路會使主機把數據全讀為0，此時采用CRC進行校驗時，就會出現問題。由于確認數據是否有效的方法是判斷主機在讀取數據和附加的CRC之后，計算出的CRC碼是否全為0000H (采用16位CRC)。當閱讀器短路時，讀到的數據和CRC值全部為0，此時讀操作已經出錯，但由主機計算出的CRC值將錯誤地指示該讀操作是有效的。為了避免這種情況的發生，Maxim推薦將CRC-16反碼(CRC-16*)隨同數據一起寫入RAM。當采用無補碼的CRC-16時，iButton的數據驗證過程與DOW CRC相似，即，主機把CRC寄存器初始化成0000H，然后從iButton讀取全部數據和存儲的CRC-16，則最終計算出來的結果應為0000H。如果采用CRC-16*，在iButton中保存的就是CRC-16的反碼和數據。進行CRC校驗時，主機同樣把CRC寄存器初始化成0H，然后從iButton讀取數據和CRC-16*，如果操作沒有錯誤的話，最后的結果應該是B001H。這樣大大地提高了系統可靠性，讀寫頭短路造成的錯誤就不會被漏檢。至于為什么CRC-16具有這些特性，可通過與之相似的DOW CRC的分析(見圖3和圖5)來解釋。在理論上16位CRC的操作與此前介紹的8位CRC完全相同，只是由于采用的是16的CRC，性能有所改善。對于CRC-16函數，可以檢測到以下幾類錯誤：
- 任何數據記錄中的奇數個錯誤。
- 任何數據記錄中的雙位錯誤。
- 包含在16位"window" (1至16錯誤)中的任何字符串的錯誤。
- 絕大多數長字符串的錯誤。
圖3. CRC-16硬件實現及其多項式表示
圖3給出了CRC-16函數的硬件實現圖，例4則列出了與其硬件相對應的軟件實現方案，采用位操作計算CRC-16值。之前很少有高效的查詢表軟件解決方案，8位DOW CRC查詢表的基礎概念也同樣適用于CRC-16，只需對8位的程序稍加改動即可。但是，如果仍然采用DOW CRC實現方法的話，要把CRC-16全部16位結果全部放進一個查詢表，則表中就會有216也就是65536個記錄(占用的空間將會很大)。與DOW CRC不同的實現方法如例5所示，圖中采用兩個256位表來計算和存儲16位CRC值，其中一個表包含CRC的高8位，另一個存放低8位。任何一個16位CRC都可以分為代表高8位的Current_CRC16_Hi和代表低8位的Current_CRC16_Lo兩部分。對于任何一個輸入字節，在高階字節表中決定新的CRC值高階字節(New_CRC16_Hi)的索引計算公式如下：
New_CRC16_Hi = CRC16_Tabhi[I], I = 0至255; 這里：I = (Current_CRC16_Lo) EXOR (輸入字)
在低階字節表中決定新的CRC值低階字節(New_CRC16_Lo)的索引計算公式如下：
New_CRC16_Lo = (CRC16_Tablo[I]) EXOR (Current_ CRC16_Hi) I = 0至255;
這里：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 ; 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. 利用查找表進行CRC-16計算的匯編程序
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計算和查表方法的比較
例6描述了一種令人感興趣的的中間方案。該程序利用圖5所示的公式，通過對當前整個CRC的值和輸入字節進行運算來生成CRC-16。同時在圖中還給出了該等式的推導過程，用字母字符表示當前16位CRC值，用數字字符表示輸入字節的位。8次移位后就得到了所示的等式，這些等式隨后可以預計算出大部分的新CRC值。注意：例如ABCDEFGH01234567 (定義為所有位異或的結果)數字量等于輸入數據和當前CRC低字節的奇偶性。與前面的按位計算或查表方法相比較，這種方法可以減少計算時間，或減少存儲空間。最后，應說明的是，前面介紹的CRC-16函數的兩種特性在這里也用作調試準則。其第一個特性與DOW CRC的情況完全相同，即如果當前CRC寄存器的16位內容作為后續的16位輸入數據，則得到的CRC也總為0000H。CRC功能的第二個特性與DOW CRC相似，如果把當前CRC寄存器的16位反碼也作為后續的16位輸入數據，則CRC結果總為B0 01H。這兩個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
詳細圖片(GIF)
圖5. 高速CRC-16的計算方法
參考文獻
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.
工商網監
評論