循環診斷演算法

❶ CRC循環冗餘校驗演算法

CRC循環冗餘校驗演算法

CRC，全稱Cyclic Rendancy Check，即循環冗餘校驗，是一種用於檢查通信內容是否發生錯誤的演算法。它通過除法運算得到的余數來檢測數據的完整性。如果數據在傳輸過程中被干擾，使用相同的除數計算出來的余數會不同，從而可以判斷數據是否發生了變化。

一、CRC校驗的基本原理

CRC校驗的原理與余數檢查法類似。在CRC校驗中：

• 被除數對應於需要CRC校驗的數據。
• 除數對應於CRC演算法的多項式。
• 余數對應於最後算出來的CRC校驗碼。

但是，CRC演算法中的除法和普通的算術除法有所不同，它採用的是模2除法，得到的余數為模2餘數。模2除法是一種不帶借位和進位的二進制除法，其加減運算等同於異或運算。

二、有限域內的運算

為了理解模2除法和模2餘數，需要了解有限域（Finite Field）內的加減乘除運算。在計算機中，數據以二進制形式表示，因此可以定義在0-1有限域內的運算。

• 加法（不帶進位）：0+0=0，0+1=1，1+0=1，1+1=0（等同於異或運算）。
• 減法（不帶借位）：與加法相同，因為不帶借位的二進制減法也等同於異或運算。
• 乘法：0×0=0，0×1=0，1×0=0，1×1=1。
• 除法：在有限域內，除法可以簡化為通過乘法逆元來計算，但通常我們更關注模2除法下的余數計算。

三、CRC演算法參數

CRC演算法包含五個主要參數：

1. Poly（Polynomial）：生成多項式，即模2除法的除數。這個多項式不是隨意選擇的，而是根據數據的位數、CRC長度和數據錯誤類型來設計的，以盡可能提高錯誤檢測的概率。
2. Init（Initialization）：初始值，用於被檢查數據減去（異或）的值。這個值可以在計算CRC之前對數據進行預處理。
3. RefIn（Reflect the bits in each byte of input）：輸入翻轉，指將被檢查數據的輸入方向翻轉過來。
4. RefOut（Reflect the bits in each byte of output）：輸出翻轉，指將算出的CRC校驗值翻轉過來。
5. XorOut：異或輸出，用於與最後算出的CRC校驗值進行異或的值。這個值可以在輸出CRC之前對校驗值進行後處理。

四、CRC計算過程

1. 數據預處理：根據Init參數對數據進行異或運算，得到預處理後的數據。
2. 數據左移：將預處理後的數據左移與CRC長度相同的位數，為CRC校驗碼的放置留出空間。
3. 模2除法：使用生成多項式（Poly）對左移後的數據進行模2除法運算，得到余數作為CRC校驗碼。
4. CRC校驗碼處理：根據RefOut和XorOut參數對CRC校驗碼進行翻轉和異或運算，得到最終的CRC校驗碼。

五、CRC校驗過程

接收方收到數據後，將數據和CRC校驗碼整體作為被除數，再次使用相同的生成多項式進行模2除法運算。如果計算出的余數為0，則說明數據傳輸沒有錯誤；如果余數不為0，則說明數據傳輸存在錯誤。

六、示例

以CRC-8演算法為例，假設數據為0xAABB（1010 1010 1011 1011），生成多項式為0x07（對應x^8+x^2+x+1的省略形式），其他參數為默認值。

1. 數據預處理：由於Init為0x00，所以不進行預處理。
2. 數據左移：將0xAABB左移8位，得到0xAABB00。
3. 模2除法：使用0x07對0xAABB00進行模2除法運算，得到余數0xB2作為CRC校驗碼。
4. CRC校驗碼處理：由於RefOut和XorOut均為默認值False和0x00，所以不進行翻轉和異或運算。

最終，發送方發送的數據為0xAABBB2（0xAABB00+0x0000B2），接收方對收到的0xAABBB2進行CRC-8計算，如果余數為0，則說明數據傳輸沒有錯誤。

以上即為CRC循環冗餘校驗演算法的基本介紹和計算過程。通過CRC校驗，可以有效地檢測數據傳輸過程中的錯誤，提高通信的可靠性。