【正文】 通過某種算法 ,得到一個新的數(shù)據(jù) ,而這個新的數(shù)據(jù)與原數(shù)據(jù)有著固定的內(nèi)在關(guān)系，通過把原數(shù)據(jù)和新數(shù)據(jù)組合在一起，形成新的數(shù)據(jù)，因此這個新數(shù)據(jù)高位為 1 嗎 ? 1． 左移 1 位 2． 下一字節(jié)最高位移入 異或運算 最后異或運算 結(jié)束 運算結(jié)束嗎？ 初始化 CRC 寄存器 設(shè)定下一個字節(jié) 開始 3． 左移 1 位 4． 下一字節(jié)最高位移入 16 具有自 我檢驗的能力。 8位數(shù)據(jù)的 CRC查表法實現(xiàn)流程圖如下： 14 圖 31 查表法流程圖 逐位運算法，直接根據(jù)表 23的原理實現(xiàn)的。以一個 8 位的數(shù)據(jù)為例，作一次異或操作就能夠完成著一個字節(jié)。 查表法實現(xiàn)方案分析 查表法，就是預(yù)先算好基本的 CRC 值，并存儲于存儲器中，需要時直接查詢存儲器中的 CRC 數(shù)據(jù)表，它是以字或字節(jié)為單位進(jìn)行操作的，而不進(jìn)行耗時的位運算。但隨著通信速度的不斷提高 ,高的數(shù)據(jù)傳輸帶寬要求 CRC 的計算速度越來越快 ,串行計算的方法已經(jīng)不適應(yīng)要求 ,所以越來越多的使用并行計算方法 。故次設(shè)計中采用基于 CPLD 的軟件實現(xiàn)方法來完成 CRC 的編解碼校驗。 四川理工學(xué)院本科生畢業(yè)（論文）設(shè)計 13 第 3 章 方案設(shè)計 實現(xiàn)方案分析 CRC 算法可以用 硬件 實現(xiàn) ,也可以用 軟 件實現(xiàn) ,硬件實現(xiàn)的方式電路結(jié)構(gòu)復(fù)雜 ,使得應(yīng)用系統(tǒng)功能模塊增多 ,增大系統(tǒng)體積降低了集成度，批量生產(chǎn)的產(chǎn)品中提高了產(chǎn)品成本；使用 軟件 實現(xiàn)的方法 計算的速度受限于系統(tǒng) CPU 的速度 ,但是隨著 CPU 的集成度和運行速度的提高，這樣的影響顯得微不足道，所以采用 軟件實現(xiàn)的方法增加了系統(tǒng)集成度， 從而提升系統(tǒng)的通信效率 ，在進(jìn)行批量生產(chǎn)時可以極大的降低成本 。不可檢錯誤中的誤碼數(shù)必定超過了這種編碼的檢錯能力。這時的錯碼就不能檢出了。當(dāng)傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即? ? ? ?R x T x? ，故接收碼組 ??Rx必定能被 ??Gx整除；若碼組在傳輸中發(fā)生錯誤，則 ? ? ? ?R x T x? ， ??Rx被 ??Gx除時可能除不盡而有余項，即有 ? ? ? ? ? ? ? ? ? ?R x R xQxG x G x?? 因此，我們就以余項是否為零來判別接收碼組中有無錯碼。 循環(huán)碼解碼方法 接收端解碼的要求 有兩個 :檢錯和糾錯。如果為 1，那么就要與 0x8005 作模 2（異或）運算。在運算過程中，第 17位總是被舍去（圖中紅色的位）。 ??2 用 ? ?Gx 除 ? ? ? ?nkx M x? ，得到商 ? ?Qx 和余式 ? ?Rx ，即 ? ? ? ?? ? ? ? ? ?? ?nkx M x R xQxG x G x? ?? ??3 編出的碼組 ??Tx為 ? ? ? ? ()nkT x x M x R x??? 11 CRC 產(chǎn)生操作過程 以下是一個 8位的數(shù) 據(jù) 0x02 產(chǎn)生一個 16 位的 CRC的過程。因為它必定能夠被 ??Gx整除，且商的次數(shù)不大于 ? ?1k? 。用 ??Gx除 ? ? ? ?nkx M x? ，得到余式 ??Rx， ??Rx的次數(shù)必定小于 ??Gx的次數(shù)，即小于 ? ?nk? 。根據(jù)這條原則，就可以對給定的信息位進(jìn)行編碼：設(shè) ? ?Mx為信息碼多項式，其次數(shù)小于 k。如果將余式加到被除式 ??1Cx即： ? ? ? ?* 2 7 2 2 711 11C x C x x x x x x x x x? ? ? ? ? ? ? ? ? ? ? 4237754545 3 2432423311111110xxxx x xx x xxxx x xx x xxxxxxxx? ? ?? ? ???????? ? ??????? 循環(huán)碼編碼方法 在編碼時 ,首先要根據(jù)給定的 (n,k)值選定生成多項式 ??Gx,即從（ 1nx? ）的因子中選一個（ nk）次多項式作為 ??Gx。 多項式另一個常用的運算是除法，可排豎式長除法。同理左移 i 位相對于乘 ix 。可見多項式僅是碼字的一個數(shù)學(xué)描述工具，但不是碼字本身，但兩者有一一對應(yīng)的關(guān)系。 循環(huán)碼的碼字和多項式： 設(shè)循 環(huán)碼的任一個碼字為： 1 2 1 0n n ia a a a a?? 在二元情況下， ia 只取 1 或 0，為了完整描述一個碼字，需要知道 ia 的取值及其在碼字中的位置。 循環(huán)碼理論基礎(chǔ) 循環(huán)碼屬于分組碼也記為 (n,k),可分為線性循環(huán)碼和非線性循環(huán)碼兩種。 8 標(biāo)準(zhǔn)的 CRC 在通信協(xié)議中常見并被廣泛使用的標(biāo)準(zhǔn)列于表中。作為數(shù)據(jù)傳輸中差錯控制的基本方法之一 ,循環(huán)冗余校驗（ Cyclic Redundant Check）已被廣泛用于通信應(yīng)用中。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性。循環(huán)碼是建立在嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)上之上的。因為除數(shù)首位總是 1，按照模 2 除法運算法則，那么余數(shù)首位是 1 就商 1，是 0 就商 0。多位模 2 除法采用模 2 減法，不帶借位的二進(jìn)制減法，因此考慮余數(shù)夠減除數(shù)與否是沒有意義的。1＝ 1 多位二進(jìn)制模 2 除法也類似于普通意義上的多位二進(jìn)制除法，但是在如何確定商的問題上兩者采用不同的規(guī)則。 ④ 模 2 除法運算定義為： 0247。這樣，兩個二進(jìn)制位相運算時，這兩個位的值就能確定運算結(jié)果，不受前一次運算的影響，也不對下一次造成影響?！被颉?/”表示模 2 除。而且，模 2 運算 也使用與四則運算相同的運算符，即“＋”表示模 2 加，“－”表示模 2 減，“”或“ 模 2 運算原理 模 2 運算是一種二進(jìn)制算法， CRC 校驗技術(shù)中的核心部分，因此，我們在分析 CRC 算法之前，必須掌握模 2 運算的規(guī)則。這就表明，只能糾（檢） 1～ 2 個錯碼的簡單編碼也有很大實用價值。 在簡要討論了編碼的糾（檢）錯能力后，再來分析一下差錯控制編碼的效用。在一般情況下，對于分組碼有以下結(jié)論： ① 為 檢測 e 個誤碼，要求 該編碼的 最小碼距 min 1de?? （ ） ② 為 糾正 t 個誤碼，要求 該編碼的 最小碼距 m in 21dt?? （ ） ③ 為 糾正 t 個誤碼，同時檢測 e（ e＞ t）個誤碼，要求最小碼距 m in 1d t e? ? ? （ ） 所謂 “ 糾正 t 個誤碼 ,同時檢測 e 個誤碼 ” ，是指 若接收碼組與某一許用碼組K 個信息位 碼長 n=k+r r 個監(jiān)督位 6 間的距離在糾錯能力范圍 t 內(nèi)，則按前向糾錯方式工作 ，自動 將誤碼予以糾正；而當(dāng) 與任何許用碼組間的距離都超過 t 時，則按檢錯方式工作。 由上例可知，一種編碼的最小碼距直接關(guān)系到這種碼的檢錯和糾錯能力，碼距實際上是由一種碼組變成另一種碼組必須變化的比特數(shù)。 在上述三位 二進(jìn)制 碼組例子中， 8 種碼組均為許用碼組時，兩碼組間的最小距離為 1，常記作 min 1d ? 。漢明（ Hamming）距離 就是 兩個碼組中對應(yīng)碼位上具有不同二進(jìn)制碼元的位數(shù)定義為兩碼組的距離，簡稱碼距。圖中 前面 k 位 (an1? ar)為信息位，后面附加個監(jiān)督位 (ar1? a0)。 分組碼一般用符號 (n,k)表示，其中 k 是每個碼組中二進(jìn)信息碼元的數(shù)目； n是每個碼組的總位數(shù)，又稱為碼組長度 (碼長 )； n－ k = r 為每碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。糾 正一位 錯 碼 的方法是：將 8 個碼組分成二個子集，其中｛ 000、 100、 0 001｝ 與許用碼組 000對應(yīng)， {11 01 10 110}與許用碼組 111 對應(yīng) ； 這樣， 在接收端如果認(rèn)為碼 5 組中僅有一個錯碼， 只要收到第一子集中的碼組即判為 000，收到第二子集中的碼組即判為 111。 下 表示出了這種情況： 表 2－ 1 信息位與監(jiān)督位的關(guān)系 信息位 監(jiān)督位 晴 00 0 云 01 1 陰 10 1 雨 11 0 （ 3）如果進(jìn)一步將許用碼組限制為二種： 000 和 111。以上編碼方法 相當(dāng)于只傳遞 00、 0 11 四種信息，而第三位是附加的 監(jiān)督位 。雖然原發(fā)送碼組為 101 的可能性很?。ㄒ驗榘l(fā)生三個誤碼的情況極少），但不能絕對排除 ； 即使傳輸過程中只發(fā)生一個誤碼，也有三種可能的發(fā)送碼組： 000、 011 和 110。用這種簡單的校驗關(guān)系可以發(fā)現(xiàn)一個和三個錯誤，但不能糾正錯誤。 經(jīng)觀察我們可以發(fā)現(xiàn)，許用碼組中“ 1”的個數(shù)為偶數(shù)個，禁用碼組中“ 1”的個數(shù)為奇數(shù)個。這樣的編碼既不能檢錯，也不能糾 錯 ， 完全 沒有抗干擾能力； （ 2）若只選其中的 000、 01 10 110 四種碼組作為許用碼組 。下面分三種情況討論 （ l）如果這 8 種碼組都用于傳送消息，即每個碼組都是許用碼組 。下面以三位二進(jìn)制碼組為例，說明檢錯 糾錯 的基本原理。分析仿真結(jié)果得出結(jié)論。 本設(shè)計主要內(nèi)容首先從了解循環(huán)冗余校驗碼的實際應(yīng)用入手，然后分析糾錯編碼的基本原理，研究程序設(shè)計中的基本運算規(guī)則（模 2 運算）入手，深入分析循環(huán)冗余碼的編解碼理論及其工程實現(xiàn)算法。循環(huán)冗余校驗碼（ CRC）是一種系統(tǒng)的縮短循環(huán)碼，廣泛應(yīng)用于幀校驗。在以后的實踐中，人們從循環(huán)群的角度，在代數(shù)機(jī)構(gòu)、糾錯性能控制等方面找到了循環(huán)碼更加吸引人的優(yōu)越之處。 循環(huán)碼是線性分組碼中最重要的一個子類 ,它的結(jié)構(gòu)完全建立在有限域的基礎(chǔ)上 ,可以用近似代數(shù)的方法精確描述 ,循環(huán)碼是 1957 年由普蘭奇 (Prange)提出的 ,此后幾十年中得到了充分的研究和發(fā)展。 檢錯刪除（ deletion）：它和檢錯重發(fā)的區(qū)別在于，在接收端發(fā)現(xiàn)錯誤碼后，立即將其刪除，不要求重發(fā)。這種技術(shù)的原理和設(shè)備都很簡單。在發(fā)送端將它和原發(fā)送碼元逐一比較。 3 反饋校驗（ Feed Checkout）：這時不需要在發(fā)送序列中加入差錯控制碼元。但是為了能夠糾正錯碼，而不是僅僅檢測到有錯碼，和檢測重發(fā)相比，需要加入更多的差錯控制 碼元。在二進(jìn)制碼元的情況下，能夠確定錯碼的位置，就相當(dāng)于能夠就糾正錯碼。 前向糾錯：前向糾錯一般簡稱 FEC（ Forward Error Correction）。所謂檢測到有碼錯 ,是指在一組接收碼元中知道有一個或一些錯 碼 ,但是不知道該錯碼該如何糾正。在突發(fā)信道中 ,錯碼是成串集中出現(xiàn)的 ,即在一些短促的時間段內(nèi)會出現(xiàn)大量錯碼 ,而在這些短促的時間段之間存在較長的無錯碼區(qū)間。即隨機(jī)信道、突發(fā)信道和混合信道。一些通用的系統(tǒng) ,其誤碼率要求因用途而異 ,也可以把查錯控制作為附加手段 ,在需要時加用。由于乘性干擾引起的碼間串?dāng)_，可以采用均衡的辦法糾正 .而加性的影響則需要用其他的辦法解決。數(shù)字信號在傳輸過程中 ,由于受到干擾的影響，碼元波形變壞。 圖 12數(shù)字通信系統(tǒng)模型 與模擬數(shù)據(jù)通信相比較，數(shù)字?jǐn)?shù)據(jù)通信具有下列優(yōu)點： ? 數(shù)字技術(shù) 的發(fā)展較 模擬技術(shù)更快，數(shù)字設(shè)備 通過集成電路很容易 實現(xiàn)，并與計算機(jī)相結(jié)合，而由于超大規(guī)模集成電路技術(shù)的迅速發(fā)展，數(shù)字設(shè)備的體積與成本的下降速度大大超過模擬設(shè)備，性能價格比高； ? 來自 視頻 、 聲音 和其他 信息 源的各 類數(shù)據(jù)均可統(tǒng)一為數(shù)字信號的形式，并通過數(shù)字通信系統(tǒng)傳輸； ? 在長距離數(shù)字通信中可以通過中繼器放大和整形來保證數(shù)字信號的完整性而不累積噪音； 模擬信息源 調(diào)制器 信道 解調(diào)器 受信者 噪聲源 信息源 信源編碼 加密 信道編碼 數(shù)字調(diào)制 信道 數(shù)字解調(diào) 信道譯碼 解密 信源譯碼 受信者 2 ? 以數(shù)據(jù)幀為單位傳輸數(shù)據(jù)，并通過檢錯編碼和重發(fā)數(shù)據(jù)幀來發(fā)現(xiàn)與糾正通信錯誤，從而有效保證通信的可靠性； ? 使用加密技術(shù)可有效增強(qiáng)通信的安全性； ? 多路光纖技術(shù)的發(fā)展大大提高了數(shù)字通信的效率。 圖 11模擬通信系統(tǒng)模型 數(shù)字通信是用 數(shù)字信號作為載體來傳輸消息，或用數(shù)字信號對載波進(jìn)行數(shù)字調(diào)制后再傳輸?shù)耐ㄐ欧绞?。Error detection 3 目錄 摘 要 .............................................................. I ABSTRACT .......................................................... II 第 1章 引 言 ........................................................ 1 概述 .