CCITT 16 Bit CRC

CRC 在程式設計中是相當重要的功能，他提供了錯誤偵測的能力（沒有修正，要有修正能力，要使用 ECC），確保我們傳送的數據是正確無誤的，這不管是在寫軟體、韌體都是經常會使用的方法。



數據在傳輸線上很可能受外來的干擾而發生錯誤，因此由通訊設備所
接收的資料還須再通過一層查核，在確定所接收的資料與傳送端所發出的
原始數據完全相同時，該資料才可做進一步的利用，否則錯誤的部份必須
重傳，但如何檢查所接收資料的正確性呢? 通常欲傳送的資料先被依序
劃分成固定長度的區段，稱為區塊 (block) ，每次在傳送一個區塊之後
，雙方即進行核對。傳統較常採用的方式即是一種稱為 checksum 的方法，這是一個數值
，它的算法是取區塊內所有位元組總合的最低的一、兩個位元組，
每個區塊皆有自己的 checksum，此種方式所能偵測到的錯誤機會並不高
，例如: 若在某個區塊內某兩個位元組的原值分別是 A 與 B，若 A、B 分別
被干擾成 A+C 與 B-C，則這些干擾對整個區塊的 checksum 的影響
是 (A+C)+(B-C)=A+B ，沒有任何影響，並且，區塊中被干擾的位元組其
所在位置也不影響該區塊的 checksum。
這種情形若僅對數個區塊的傳輸而言，偵測不到的機會也許不高，但
就今日數據的傳輸量來看，checksum 的檢查方式顯然已不足以應付，
當然，這類問題的細節須要較深的統計與機率等數學作進一步探討，本書
僅是介紹性質，有興趣的讀者可參考相關的書籍。
另一種較先進的錯誤偵測方式即是所謂的循環冗餘檢查碼 (Cyclic
Redundancy Check Code) ，簡稱 CRC 碼，它也是由待傳輸的資料區塊
計算出的，所不同的是，CRC 的計算方式可避免上述 checksum 所遭遇的
問題，意即，在整個區塊中任意一個位元的值發生變動，其對於整個區塊
之 CRC 值的影響將視該位元在區塊中的相對位置而定，簡言之，CRC 值有
牽一髮而動全身的作用，而 checksum 則沒有。
CRC 的計算方式是將待傳輸的區塊視為一堆連續位元所構成的一整個
數值，並將此數值除以一特定的除數，通常以二進位表示，此除數又稱為
衍生多項式 (Generation Polynomial) ，該除數一般皆由設計硬體或
軟體的廠商所提供，而除數值位元數目則視欲得到的 CRC 位元數目而定
，目前較常使用的 CRC 位元數目有 8、16 或 32，一般縮寫為 CRC-8、
CRC-16、CRC-32，通常，CRC 碼越長，則數據發生干擾卻不反應在 CRC 值
的機率也就越低，不過得多花些時間傳送較長的 CRC 碼。
根據理論統計，CRC-16 可完全偵測資料區塊內單一或兩個位元的錯誤
、奇數個位元的錯誤、連續 16 個位元或少於此數的錯誤，超過 17 個
連續位元的錯誤偵測率則有 99.9969% ，其它位元長度的錯誤偵測率則可
達 99.9984% ，但對於 checksum，兩個位元同時出錯，或連續九位元或
更多的錯誤即非常可能不被偵測到。
底下是一些數學符號所表示的 CRC 碼運算過程。
吾人可將待傳送的區塊資料位元串表示成一個很大的二進位數字，並
令此數字等於 F，例如，底下是某個區塊的位元串所連成的二進位數字:

F = 1011010111110111101110100100101110101... (區塊資料)

假設目前欲求 F 的 16 位元 CRC 值，並且，廠商所提供的衍生多項
式是:
16 12 5
G(x) = x + x + x + 1 (衍生多項式)

其中，x 是所採的進制，在二進位系統，x = 2，則 G 的值為:

G = 1,0001,0000,0010,0001 (二進位數字)

底下的式子中的餘數 C 即是 F 的 16 位元 CRC 值:

16
F ‧ 2 = A ‧ G + C

由於 C 是此式中的餘式，故稱此值為 Redundancy。

例如，底下即是透過上述的 G(x) 求得 11010101 (D5H) 的 CRC 值:

A
┌─────────────────
1,0001,0000,0010,0001│1101,0101 ‧ 1,0000,0000,0000,0000
╯......
──────────────────
(二進位長除法) 16 位元 CRC 值 → 1001,1011,1101,1000

讀者應可注意到，衍生多項式的數值將影響到所產生的 CRC 值，
根據理論計算，當衍生多項式的數值恰為某些特定值時，所產生的 CRC 值
最 "亂" ，換句話說，它偵測資料受雜訊干擾的能力越高，在上個範例
中所採用的多項式也是 PC/XT 控制卡上 μPD765A 所採用，該多項式
也是 CRC-CCITT v.41 所制定的標準，而目前在許多通訊上的應用亦採用
此值。
理論上，在計算 CRC 時非常簡單，只要一個除法運算即可，運算之後
的餘數即是 CRC 值，但實際上所被除數 F 的位元數目可能以萬為單位，
如何利用程式以最簡易、最快的方式求得該餘數也是技術關鍵所在。
事實上，各式的檢查碼也不僅應用在網路通訊上，和數據的存取、
儲存、傳輸等類似的範疇也會用到，例如磁碟片或磁帶機上資料的儲存即是
，在 Apple 個人電腦的磁碟機即是利用 checksum 驗證所存取資料的正確
性，而 PC 的磁碟機則使用 CRC。



-------------------------------------------------------------------------------
// Update the CRC for transmitted and received data using
// the CCITT 16bit algorithm (X^16 + X^12 + X^5 + 1).

unsigned char ser_data;
static unsigned int crc;

crc = (unsigned char)(crc >> 8) | (crc << 8);
crc ^= ser_data;
crc ^= (unsigned char)(crc & 0xff) >> 4;
crc ^= (crc << 8) << 4;
crc ^= ((crc & 0xff) << 4) << 1;