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

   

   

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

   

    如果輸入端具有相同的位序列，則兩個(gè)電路生成的 CRC 將相同。