【正文】 于能夠就糾正錯碼。 采用 FEC是，不需要反相信道傳送重發(fā)指令，也沒有因反復(fù)重發(fā)而產(chǎn)生的時延，故實時性好。但是為了能夠糾正錯碼，而不是僅僅檢測到有錯碼，和檢測重發(fā)相比，需要加入更多的差錯控制 碼元。故設(shè)備要比檢測重發(fā)設(shè)備復(fù)雜。 3 反饋校驗（ Feed Checkout）：這時不需要在發(fā)送序列中加入差錯控制碼元。接收端將接收到的碼元原封不動地轉(zhuǎn)發(fā)回發(fā)送端。在發(fā)送端將它和原發(fā)送碼元逐一比較。若發(fā)現(xiàn)有不同，就認(rèn)為接收端收到的序列中有錯碼，發(fā)送端立即重發(fā)。這種技術(shù)的原理和設(shè)備都很簡單。但是需要雙向信道，傳輸效率也比較低，因為每個碼元都需要占用兩次傳輸時間。 檢錯刪除（ deletion）：它和檢錯重發(fā)的區(qū)別在于，在接收端發(fā)現(xiàn)錯誤碼后，立即將其刪除，不要求重發(fā)。這種方法只適用在少數(shù)特定系統(tǒng)中，在那里發(fā)送碼元中有 大量多余度，刪除不分接收碼元不影響應(yīng)用。 循環(huán)碼是線性分組碼中最重要的一個子類 ,它的結(jié)構(gòu)完全建立在有限域的基礎(chǔ)上 ,可以用近似代數(shù)的方法精確描述 ,循環(huán)碼是 1957 年由普蘭奇 (Prange)提出的 ,此后幾十年中得到了充分的研究和發(fā)展。起初人們認(rèn)識到并感興趣的是循環(huán)碼的外在特點 ,即循環(huán)碼碼字的循環(huán)移位后仍然是碼字 ,這個特點給循環(huán)碼的編譯碼實現(xiàn)帶來了便利。在以后的實踐中，人們從循環(huán)群的角度，在代數(shù)機構(gòu)、糾錯性能控制等方面找到了循環(huán)碼更加吸引人的優(yōu)越之處。目前，使用查錯控制系統(tǒng)中使用的線性分組碼幾乎都是循環(huán)碼或循環(huán)碼 的子類。循環(huán)冗余校驗碼（ CRC）是一種系統(tǒng)的縮短循環(huán)碼，廣泛應(yīng)用于幀校驗。 內(nèi)容概要 本設(shè)計主要分析循環(huán)冗余碼理論，在理論基礎(chǔ)上探討其運用 VHDL 語言實現(xiàn)其算法 ,設(shè)計主要分為兩個模塊，即循環(huán)冗余碼編碼模塊和循環(huán)冗余解碼模塊，主要編程工具為 Max Plus II。 本設(shè)計主要內(nèi)容首先從了解循環(huán)冗余校驗碼的實際應(yīng)用入手，然后分析糾錯編碼的基本原理，研究程序設(shè)計中的基本運算規(guī)則（模 2 運算）入手，深入分析循環(huán)冗余碼的編解碼理論及其工程實現(xiàn)算法。提出編解碼方案并進(jìn)行比較分析，選出符合本設(shè)計要求的實現(xiàn)方案，進(jìn)行 硬件設(shè)計，最后進(jìn)行程序的模塊化設(shè)計，并進(jìn)行仿真驗證，模塊仿真驗證無誤進(jìn)行模塊組合調(diào)試仿真。分析仿真結(jié)果得出結(jié)論。 4 第 2 章 CRC 編解碼理論 糾錯編碼的基本原理 信道編碼是在被傳送的信息中附加一些監(jiān)督碼元，來檢錯和糾錯。下面以三位二進(jìn)制碼組為例，說明檢錯 糾錯 的基本原理。三位二進(jìn)制碼元共有 32 =8 種可能的組合； 000、 00 0 01 100、 10 1 111。下面分三種情況討論 （ l）如果這 8 種碼組都用于傳送消息，即每個碼組都是許用碼組 。在傳輸過程中若發(fā)生一個或多個誤碼，則一種碼組會錯誤地變成另一種碼組。這樣的編碼既不能檢錯，也不能糾 錯 ， 完全 沒有抗干擾能力； （ 2）若只選其中的 000、 01 10 110 四種碼組作為許用碼組 。 除上述 4種許用碼組以外的另外 4 種碼組 00 0 100、 111 稱為禁用碼組。 經(jīng)觀察我們可以發(fā)現(xiàn)，許用碼組中“ 1”的個數(shù)為偶數(shù)個，禁用碼組中“ 1”的個數(shù)為奇數(shù)個。如果在傳輸過程中發(fā)生了一位或三位的錯碼，則“ 1”的個數(shù)就變?yōu)槠鏀?shù)個，許用碼組就變?yōu)榻么a組；接收端 一旦發(fā)現(xiàn)這些禁用碼組，就表明傳輸過程中發(fā)生了錯誤 。用這種簡單的校驗關(guān)系可以發(fā)現(xiàn)一個和三個錯誤，但不能糾正錯誤。例如，當(dāng)接收到的碼組為 010 時，我們可以斷定這是禁用碼組，但無法判斷原來的正確碼組 是哪個 許用碼組 。雖然原發(fā)送碼組為 101 的可能性很小（因為發(fā)生三個誤碼的情況極少），但不能絕對排除 ； 即使傳輸過程中只發(fā)生一個誤碼，也有三種可能的發(fā)送碼組： 000、 011 和 110。 顯然，上述編碼無法發(fā)現(xiàn) 2 個錯碼。以上編碼方法 相當(dāng)于只傳遞 00、 0 11 四種信息，而第三位是附加的 監(jiān)督位 。這位附加的監(jiān)督碼 位 與前面兩位 信息 碼元 和在 一起，保證碼組中 “1”碼的個數(shù)為偶數(shù)。 下 表示出了這種情況： 表 2－ 1 信息位與監(jiān)督位的關(guān)系 信息位 監(jiān)督位 晴 00 0 云 01 1 陰 10 1 雨 11 0 （ 3）如果進(jìn)一步將許用碼組限制為二種： 000 和 111。則不難看出，用這種方法可以發(fā)現(xiàn)所有 不超過 2 個 的誤碼 ；或能 糾正一位錯碼。糾 正一位 錯 碼 的方法是：將 8 個碼組分成二個子集，其中｛ 000、 100、 0 001｝ 與許用碼組 000對應(yīng)， {11 01 10 110}與許用碼組 111 對應(yīng) ； 這樣， 在接收端如果認(rèn)為碼 5 組中僅有一個錯碼， 只要收到第一子集中的碼組即判為 000，收到第二子集中的碼組即判為 111。 例如，當(dāng)收到的碼組為禁用碼組 100 時，如果認(rèn)為該碼組中僅有 1 個錯碼，則可判斷此錯碼發(fā)生在“ 1”位，從而糾正為 000；若認(rèn)為上述接收碼組中的錯碼數(shù)不超過兩個，則存在兩種可能性： 000 錯一位和 111 錯兩位都可能變成 100，因而只能檢測出存在錯碼而無法糾正它。 分組碼一般用符號 (n,k)表示，其中 k 是每個碼組中二進(jìn)信息碼元的數(shù)目； n是每個碼組的總位數(shù)，又稱為碼組長度 (碼長 )； n－ k = r 為每碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。通常，將分組碼規(guī)定為具有如下圖所示的結(jié)構(gòu)。圖中 前面 k 位 (an1? ar)為信息位，后面附加個監(jiān)督位 (ar1? a0)。 1na? 2na? ra 1ra? 0a 圖 21 分組碼的結(jié)構(gòu) 在信道編碼中，碼組的重量 就是碼組中 非零碼元的數(shù)目，簡稱碼重，例如 0010 碼組的碼重為 1， 0011 碼組的碼重為 2。漢明（ Hamming）距離 就是 兩個碼組中對應(yīng)碼位上具有不同二進(jìn)制碼元的位數(shù)定義為兩碼組的距離，簡稱碼距。 我們把某種編碼中各個碼組間距離的最小值稱為最小碼距，可記為 mind 。 在上述三位 二進(jìn)制 碼組例子中， 8 種碼組均為許用碼組時，兩碼組間的最小距離為 1，常記作 min 1d ? 。在選四種碼組為許用碼組情況下，最小碼距式中 min 2d ? ；采用兩種許用碼組時， min 3d ? 。 由上例可知，一種編碼的最小碼距直接關(guān)系到這種碼的檢錯和糾錯能力，碼距實際上是由一種碼組變成另一種碼組必須變化的比特數(shù)。因此最小碼距是信道編碼的一個重要參數(shù)。在一般情況下，對于分組碼有以下結(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 時，則按檢錯方式工作。也 就是按“糾檢結(jié)合的方式”工作。 在簡要討論了編碼的糾（檢）錯能力后，再來分析一下差錯控制編碼的效用。 假設(shè)在信道中傳輸 “ 0” 和 “ l” 的錯誤概率 p 相等，且 p＜＜ 1，則在碼長為 n位的碼組中發(fā)生 r 位錯碼的概率（誤碼率）為 ? ? ? ? ? ?!1 !!nrr r rnn rP r C p p pr n r?? ? ? ? （ ） 例如，當(dāng)碼長 n＝ 7， 310p ?? 時 ，則有 ? ? 37 1 7 7 10pp ?? ? ? ? ? 257 2 31 2. 1 10pp ?? ? ? ? ? 387 3 35 3. 5 10pp ?? ? ? 可見，采用了差錯控制編碼，即使只能糾 正 （ 或檢測 ）碼組中的 l～ 2 個錯 0碼，也可以使誤碼率下降幾個數(shù)量級。這就表明，只能糾（檢） 1～ 2 個錯碼的簡單編碼也有很大實用價值。事實上，常用的差錯控制編碼大多數(shù)也只能糾 正 （ 或檢 測 ）碼組中的 l～ 2 個錯碼。 模 2 運算原理 模 2 運算是一種二進(jìn)制算法， CRC 校驗技術(shù)中的核心部分，因此，我們在分析 CRC 算法之前，必須掌握模 2 運算的規(guī)則。 與四則運算相同，模 2 運算也包括模 2 加、模 2 減、模 2 乘、模 2 除四種二進(jìn)制運算。而且，模 2 運算 也使用與四則運算相同的運算符，即“＋”表示模 2 加，“－”表示模 2 減，“”或“”表示模 2 乘，“247?！被颉?/”表示模 2 除。與四則運算不同的是模 2 運算不考慮進(jìn)位和借位，即模 2 加法是不帶進(jìn)位的二進(jìn)制加法運算，模 2 減法是不帶借位的二進(jìn)制減法運算。這樣，兩個二進(jìn)制位相運算時，這兩個位的值就能確定運算結(jié)果，不受前一次運算的影響，也不對下一次造成影響。 ① 模 2 加法運算定義為： 0＋ 0＝ 0； 0＋ 1＝ 1； 1＋ 0＝ 1； 1＋ 1＝ 0 ② 模 2 減法運算定義為 ： 0－ 0＝ 0； 0－ 1＝ 1； 1－ 0＝ 1； 1－ 1＝ 0 ③ 模 2 乘法運算定義為： 7 00＝ 0； 01＝ 0； 10＝ 0； 11＝ 1 多位二進(jìn)制模 2 乘法類似于普通意義上的多位二進(jìn)制乘法，不同之處在于后者累加中間結(jié)果（或稱部分積）時采用帶進(jìn)位的加法，而模 2 乘法對中間結(jié)果的處理方式采用的是模 2 加法。 ④ 模 2 除法運算定義為： 0247。1＝ 0 1247。1＝ 1 多位二進(jìn)制模 2 除法也類似于普通意義上的多位二進(jìn)制除法，但是在如何確定商的問題上兩者采用不同的規(guī)則。后者按帶借位的二進(jìn)制減法，根據(jù)余數(shù)減除數(shù)夠減與否確定商 1 還是商 0，若夠減則商 1，否則商 0。多位模 2 除法采用模 2 減法，不帶借位的二進(jìn)制減法，因此考慮余數(shù)夠減除數(shù)與否是沒有意義的。實際上，在 CRC 運算中，總能保證除數(shù)的首位為 1，則模 2 除法運算的商是由余數(shù)首位與除數(shù)首位的模 2 除法運算結(jié)果確定。因為除數(shù)首位總是 1，按照模 2 除法運算法則，那么余數(shù)首位是 1 就商 1，是 0 就商 0。 CRC 分類 在線性分組碼中 ,有一種重要的碼稱為循環(huán)碼 (cyclic code)。循環(huán)碼是建立在嚴(yán)密的代數(shù)學(xué)理論基礎(chǔ)上之上的。這種碼的檢（糾）錯能力較強 ,而且編碼和解碼設(shè)備都不太復(fù)雜。循環(huán)碼除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性。循環(huán)性是指任一碼組循環(huán)移位以后 ，仍是該碼中的一個碼組。作為數(shù)據(jù)傳輸中差錯控制的基本方法之一 ,循環(huán)冗余校驗（ Cyclic Redundant Check）已被廣泛用于通信應(yīng)用中。目前 CRC的應(yīng)用分為非標(biāo)準(zhǔn)和標(biāo)準(zhǔn)兩種，已被國際標(biāo)準(zhǔn)化組織規(guī)定的標(biāo)準(zhǔn)生成多項式為標(biāo)準(zhǔn) ,用戶自定義的生成多項式為非標(biāo)準(zhǔn)，這也是目前廣泛使用的幾種。 8 標(biāo)準(zhǔn)的 CRC 在通信協(xié)議中常見并被廣泛使用的標(biāo)準(zhǔn)列于表中。 表 2－ 2 標(biāo)準(zhǔn) CRC多項式 名稱 多項式 簡記 應(yīng)用 CRC－ 4 4 1xx?? 0x13 ITU CRC－ 16 1 6 1 5 2 1x x x? ? ? 0x8005 IBM SDLC CRC－ CCITT 1 6 1 2 5 1xxx? ? ? 0x1201 ISO HDLC,SDLC,42,PPPFCS CRC－ 32 3 2 2 6 2 3 2 2 1 6 1 2 1 08 7 5 4 2 1x x x x x x xx x x x x? ? ? ? ? ?? ? ? ? ? ? 0x104C11DB7 ZIP,RAR,IEEE802LAN/FDDI,IEEE 1394,PPPFCS CRC－ 32C 3 2 2 8 2 7 2 6 2 5 2 3 2 2 2 0 1 91 8 1 4 1 3 1 1 1 0 9 8 4 1x x x x x x x x xx x x x x x x x? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? 0x11EDC6F41 SCTP 非標(biāo)準(zhǔn)的 CRC 非標(biāo)準(zhǔn)的 CRC一般是為了某種用途而采用不同于標(biāo)準(zhǔn)的生成多項式，而實際的操作原理是相同的，主要用于需要 CRC 而需要低成本的應(yīng)用，或者為了減輕設(shè)計算機處理負(fù)擔(dān)而又能夠保證數(shù)據(jù)可靠性的折中辦法，此外，部分的加密算法也是采用 CRC 來生成。 循環(huán)碼理論基礎(chǔ) 循環(huán)碼屬于分組碼也記為 (n,k),可分為線性循環(huán)碼和非線性循環(huán)碼兩種。循環(huán)碼仍是線性分組碼，但另有循環(huán)移位不變特性。 循環(huán)碼的碼字和多項式： 設(shè)循 環(huán)碼的任一個碼字為： 1 2 1 0n n ia a a a a?? 在二元情況下， ia 只取 1 或 0，為了完整描述一個碼字，需要知道 ia 的取值及其在碼字中的位置。用多項式來描述碼字是很方便的，于是 1 2 1 0n n ia a a a a??表示的碼字用 1n? 次多項式來