Ⅰ crc電路原理
CRC(Cyclic Rendancy Check)被廣泛用於數據通信過程中的差錯檢測，具有很強的
檢錯能力。本文詳細介紹了CRC的基本原理，並且按照解釋通行的查表演算法的由來的思路介紹
了各種具體的實現方法。
1.差錯檢測
數據通信中，接收端需要檢測在傳輸過程中是否發生差錯，常用的技術有奇偶校驗(Parity
Check)，校驗和(Checksum)和CRC(Cyclic Rendancy Check)。它們都是發送端對消息按照
某種演算法計算出校驗碼，然後將校驗碼和消息一起發送到接收端。接收端對接收到的消息按
照相同演算法得出校驗碼，再與接收到的校驗碼比較，以判斷接收到消息是否正確。
奇偶校驗只需要1位校驗碼，其計算方法也很簡單。以奇檢驗為例，發送端只需要對所有消息
位進行異或運算，得出的值如果是0，則校驗碼為1，否則為0。接收端可以對消息進行相同計
算，然後比較校驗碼。也可以對消息連同校驗碼一起計算，若值是0則有差錯，否則校驗通過。
通常說奇偶校驗可以檢測出1位差錯，實際上它可以檢測出任何奇數位差錯。
校驗和的思想也很簡單，將傳輸的消息當成8位(或16/32位)整數的序列，將這些整數加起來
而得出校驗碼，該校驗碼也叫校驗和。校驗和被用在IP協議中，按照16位整數運算，而且其
MSB(Most Significant Bit)的進位被加到結果中。
顯然，奇偶校驗和校驗和都有明顯的不足。奇偶校驗不能檢測出偶數位差錯。對於校驗和，
如果整數序列中有兩個整數出錯，一個增加了一定的值，另一個減小了相同的值，這種差錯
就檢測不出來。
2.CRC演算法的基本原理
-------------------
CRC演算法的是以GF(2)(2元素伽羅瓦域)多項式算術為數學基礎的，聽起來很恐怖，但實際上它
的主要特點和運算規則是很好理解的。
GF(2)多項式中只有一個變數x，其系數也只有0和1，如：
1*x^7 + 0*x^6 + 1*x^5 + 0*x^4 + 0*x^3 + 1*x^2 +1*x^1 + 1*x^0
即：
x^7 + x^5 + x^2 + x + 1
(x^n表示x的n次冪)
GF(2)多項式中的加減用模2算術執行對應項上系數的加減，模2就是加減時不考慮進位和借位，
即：
0 + 0 = 0 0 - 0 = 0
0 + 1 = 1 0 - 1 = 1
1 + 0 = 1 1 - 0 = 1
1 + 1 = 0 1 - 1 = 0
顯然，加和減是一樣的效果(故在GF(2)多項式中一般不出現"-"號)，都等同於異或運算。例
如P1 = x^3 + x^2 + 1，P2 = x^3 + x^1 + 1，P1 + P2為：
x^3 + x^2 + 1
+x^3 + x + 1
------------------------------
x^2 + x
GF(2)多項式乘法和一般多項式乘法基本一樣，只是在各項相加的時候按模2算術進行，例如
P1 * P2為：
(x^3 + x^2 + 1)(x^3 + x^1 + 1)
= (x^6 + x^4 + x^3
+ x^5 + x^3 + x^2
+ x^3 + x + 1)
= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
GF(2)多項式除法也和一般多項式除法基本一樣，只是在各項相減的時候按模2算術進行，例
如P3 = x^7 + x^6 + x^5 + x^2 + x，P3 / P2為：
x^4 + x^3 + 1
--------------------------------------------------------------
x^3 + x + 1 )x^7 + x^6 + x^5 + x^2 + x
x^7 + x^5 + x^4
-----------------------------------