以的內(nèi)存占用進(jìn)行高效的 CRC 計算

    幾乎每種形式的數(shù)字信息交換都會引入通信錯誤。有時，這些錯誤可以被忽略（例如，高分辨率視頻中的錯誤像素根本無法察覺）。然而，大多數(shù)時候，它們是不能被忽視的，我們要確保接收者得到正確的信息流。
    為了克服信息傳輸固有的不準(zhǔn)確性，已經(jīng)開發(fā)了一些錯誤檢測和糾正的方法。一般來說，這些方法向?qū)嶋H消息引入了一些冗余，這反過來又可用于檢測錯誤，并在某些情況下恢復(fù)原始數(shù)據(jù)。
    常見的方法之一是使用CRC（循環(huán)冗余校驗）功能，這是 一組常用于通過檢測由于消息流中的噪聲或位丟失而導(dǎo)致的錯誤來確保數(shù)字?jǐn)?shù)據(jù)流中的數(shù)據(jù)完整性的代碼。CRC 計算附加到數(shù)據(jù)流并與消息一起傳輸?shù)囊幌盗形唬ㄍǔＲ卜Q為 CRC）。接收方對消息執(zhí)行 CRC 函數(shù)，并將結(jié)果與??接收到的 CRC 碼進(jìn)行比較，以驗證消息的完整性。CRC 通常用于許多應(yīng)用，例如數(shù)字通信和計算機(jī)數(shù)據(jù)存儲系統(tǒng)。
    CRC 通過所傳輸?shù)南⒑投囗検匠龜?shù)之間的二進(jìn)制多項式除法來執(zhí)行，并且通常使用線性反饋移位寄存器（LFSR）來實現(xiàn)。LFSR 是一個移位寄存器，其下一個狀態(tài)是其先前狀態(tài)和輸入位的線性組合。在我們的上下文中，線性運算符是邏輯異或和邏輯與。由于 LFSR 電路的操作是確定性的，并且 CRC 比消息短，因此通常很少有消息映射到每個 CRC 值。精心選擇的多項式可確保消息到 CRC 值的均勻分布映射（例如，如果所有消息都映射到相同的 CRC，則不可能檢測到消息位中的錯誤）。
    嵌入式系統(tǒng)設(shè)計的技巧是以盡可能有效的方式和盡可能小的占用空間來實現(xiàn)該技術(shù)。在本文中，我們討論了 LFSR 和 CRC 的理論和實現(xiàn)的各個方面，并使用 Analog Devices Blackfin 處理器上專門為解決高效 LFSR 實現(xiàn)任務(wù)而定義的一系列指令進(jìn)行說明。我們還提供了一種將實現(xiàn)從內(nèi)部 LFSR 形式轉(zhuǎn)換為外部 LFSR 形式的方法。
    基礎(chǔ)知識
    CRC 的開發(fā)是為了滿足錯誤檢測機(jī)制的要求。該代碼由一個位字段（具有一定的設(shè)定長度）組成，該位字段與消息（通常附加到消息中）一起通過通信介質(zhì)傳輸。在接收方，根據(jù)接收到的消息計算第二個 CRC，然后與接收到的 CRC 進(jìn)行比較。如果兩個字段不相同，則傳輸中發(fā)生錯誤（但不知道是消息錯誤、CRC 錯誤還是兩者都錯誤）。
    為了計算消息的 CRC 代碼，我們將問題視為伽羅瓦域 GF(2) 上的多項式代數(shù)練習(xí)。簡而言之，GF(2) 是一個由元素 0 和 1 組成的域，+ 和* 運算符定義為模 2；換句話說，+ 是邏輯異或，* 是邏輯與。
    方法對于長度為 k位 的
    消息串M和長度為n 位的CRC字段 ，我們定義以下多項式：
    M k-1 (x)是k-1 次多項式，其形式為：
    M k-1 (x) = m k -1 x k -1 + m k -2 x k -2 +…+ m 0 x 0
    G n (x)是n 次 CRC 生成多項式：
    G n ( x ) = x n + g n -1 x n -1 +…+ g 0 x 0
    C n-1 (x)是計算出的n-1 次 CRC 多項式：
    C n -1 ( x ) = c n -1 x n -1 + c n -2 x n -2 +…+ c 0 x 0
    CRC 是這樣確定的：
    C n -1 ( x ) = { M k -1 ( x ) ? x n } mod G n ( x )
    模除法 在 GF(2) 上進(jìn)行模 2。消息字符串的k 位附加了n 位零（這是 等式中的x n項）。這種劃分通常使用 LFSR 電路來實現(xiàn)。LFSR 實現(xiàn)恰好有兩種規(guī)范形式，它們是可以互換的，因為在給定相同的消息和除數(shù)多項式的情況下，它們將計算相同的結(jié)果。
    一種稱為外部、I 型 或斐波那契 LFSR 的 形式在反饋路徑中具有異或門，反饋項從相關(guān)抽頭中采樣、相加（模 2），然后反饋到有效位 (lsb) 。
    另一種形式稱為內(nèi)部 II 型 或伽羅瓦 LFSR， 采用階位 (msb) 作為反饋項，通過位于抽頭之間的異或門反饋到相關(guān)抽頭。這種形式更流行，因為用硬件邏輯門實現(xiàn)時它似乎更快。事實上，我們可以看到代數(shù)過程和這種 LFSR 除法之間的相似之處。然而，許多實施者并不知道這兩種形式的等效性。
    內(nèi)部 CRC LFSR 的實現(xiàn)如圖 1 所示。等效的外部 LFSR 的形式如圖 2 所示。
   

   

    如前所述，這兩種電路是等效的，從內(nèi)部形式轉(zhuǎn)換為外部形式的簡單規(guī)則是：
    1. 在保持LFSR流向相同的情況下，顛倒反饋抽頭的順序；
    2. 在前k個 時鐘之后，向個抽頭 ( S 0 )饋送n 個 零，并讀取n 個 輸出位（這是所需的 CRC）作為反饋和輸入的總和。
    在這兩種情況下，M 都是從位m k -1開始饋入的。例如，考慮生成多項式G 5 ( x )= x 5 + x 4 + x 2 +1 的兩個等效實現(xiàn)，如圖 3 和 4 所示。
       如果輸入端具有相同的位序列，則兩個電路生成的 CRC 將相同。