《信息處理與編碼》課件編碼理論 4.4-4.5

1、4.4 (n,k)循環(huán)碼的譯碼線性碼的譯碼線性碼的譯碼是根據(jù)接收多項(xiàng)式的伴隨式和可糾的錯(cuò)誤圖樣間的一一對應(yīng)關(guān)系，由伴隨式得到錯(cuò)誤圖樣。循環(huán)碼的譯碼循環(huán)碼是線性碼的一個(gè)特殊子類，循環(huán)碼的譯碼與線性碼的譯碼基本一致，不過由于循環(huán)碼的循環(huán)特性，它的譯碼更加簡單。譯碼過程1. 接收多項(xiàng)式的伴隨式計(jì)算。2. 求伴隨式對應(yīng)的錯(cuò)誤圖樣。3. 用錯(cuò)誤圖樣糾錯(cuò)。根據(jù)伴隨式定義計(jì)算伴隨式S設(shè) ，其中表示H的行矢量；于是得到伴隨式各分量的表示式：用k級(jí)移存器的伴隨式計(jì)算電路定理 4.4.1定理 4.4.1 二元線性系統(tǒng)中，接收矢量R的伴隨式S等于對R的信息部分所計(jì)算的監(jiān)督數(shù)字（相當(dāng)于對R的信息部分重新編碼）與接收的

2、監(jiān)督數(shù)字的矢量和。證明： 設(shè)接收矢量 ， 是R的信息部分，它是長度為k的矢量， 是R的監(jiān)督數(shù)字部分，它是長度為 的矢量，監(jiān)督矩陣為 ，Q為 階子陣， 為 階單位子陣。由伴隨式的定義得：注意到Q是H中除單位子陣外的 階子陣，所以 是把 作信息元重新編碼計(jì)算的監(jiān)督元。而 為接收的監(jiān)督元。因此，定理可證。k級(jí)移存器實(shí)現(xiàn)的伴隨式計(jì)算電路電路工作步驟 （1）門1通，門2、3、4關(guān)，接收字R的k位信息部分輸入編碼器。（2）門1關(guān)，門2、3、4通，接收信息編碼所得的監(jiān)督數(shù)字與接收監(jiān)督數(shù)字逐位模2和，得到伴隨式。這里的伴隨式計(jì)算方法只適用于線性系統(tǒng)碼。n-k級(jí)移存器的伴隨式計(jì)算電路設(shè)接收多項(xiàng)式為 ，它的信息部

3、分表示為 ，監(jiān)督部分表示為 ，由定理4.4.1經(jīng)推倒可得：上式表明循環(huán)碼接收多項(xiàng)式的伴隨式是接收多項(xiàng)式 除以 的余式，則可得到n-k級(jí)移存器的伴隨式計(jì)算電路如下：n-k級(jí)移存器的伴隨式計(jì)算電路定理4.4.2定理4.4.2 設(shè) 為接收矢量 的伴隨式，則 的循環(huán)移位 （模 ）的伴隨式 等于伴隨式 的循環(huán)移位 （模 ）。即：證明1證明：由伴隨式計(jì)算式： 可知： 對上式兩邊作同余運(yùn)算得 令 模 ，即用 表示 移位一次 模 的碼多項(xiàng)式。證明2對式 進(jìn)行模 運(yùn)算，則得到 循環(huán)移位 的伴隨式：由 可得： 證畢。定理4.4.2說明，接收矢量的循環(huán)移位（模 運(yùn)算下）與伴隨式在模 運(yùn)算下（或在除以 的伴隨式計(jì)算電

4、路中）的循環(huán)移位是一一對應(yīng)的。循環(huán)碼的通用譯碼法梅吉特譯碼法譯碼電路工作過程整個(gè)譯碼電路的工作過程如下：（1）將接收矢量移入伴隨式計(jì)算電路，計(jì)算出伴隨式。同時(shí)將接收矢量移入緩存器。（2）伴隨式寫入錯(cuò)誤圖樣檢測器，并在檢測器中循環(huán)移位（模），同時(shí)將接收矢量移出緩存器，當(dāng)監(jiān)測器輸出“1”時(shí)，表示緩存器此時(shí)刻的輸出符號(hào)是錯(cuò)誤的，并將錯(cuò)誤糾正。同時(shí)檢測器輸出反饋到伴隨式計(jì)算電路的輸入端，去修改伴隨式，從而消除該錯(cuò)誤對伴隨式所產(chǎn)生的影響。直到接收矢量全部移出緩存器，該接收矢量糾錯(cuò)完畢。若隨后伴隨式寄存器中為全零，則表示錯(cuò)誤全部被糾正，否則檢出了不可久的錯(cuò)誤圖樣。4.5循環(huán)漢明碼定義4.5.1 ：以r次本

5、原多項(xiàng)式為生成多項(xiàng)式的循環(huán)碼稱為循環(huán)漢明碼。參數(shù)碼長： 監(jiān)督位數(shù)： 信息元數(shù)目： 碼的最小距離為： 特點(diǎn)漢明碼是完備碼，而且是高效碼，這是漢明碼的特點(diǎn)。因此，在構(gòu)造循環(huán)漢明碼時(shí)，只要選擇不同的本原多項(xiàng)式作為生成多項(xiàng)式，就可以得到不同的（n, k）循環(huán)漢明碼。例4.5.1例4.5.1應(yīng)用梅吉特譯碼法實(shí)現(xiàn)（7，4）循環(huán)碼的譯碼。 （7，4）循環(huán)碼是糾一個(gè)錯(cuò)誤的循環(huán)漢明碼。該循環(huán)碼只需一個(gè)簡單的組合邏輯電路對這一確定的伴隨式進(jìn)行檢測就可以完成糾錯(cuò)。譯碼電路如圖：（7，4）循環(huán)碼譯碼電路譯碼電路的工作過程如下：（1）接受矢量送入伴隨式計(jì)算電路，經(jīng)七次移位得到伴隨式。同時(shí)接收矢量移入緩存器。（2）將前一

6、步所計(jì)算的伴隨式轉(zhuǎn)入伴隨式自發(fā)運(yùn)算電路。計(jì)算并糾正錯(cuò)誤。（3）當(dāng)接收矢量全部移出緩存器后，完成一個(gè)碼組的譯碼。當(dāng)接收矢量開始移出緩存器時(shí)下一個(gè)接收矢量緊跟著移入伴隨式計(jì)算電路和緩存器，重復(fù)第二步的過程，可實(shí)現(xiàn)連續(xù)對接收矢量糾錯(cuò)。例4.5.2例4.5.2 設(shè)計(jì)由生成的（15，11）循環(huán)漢明碼的譯碼電路，如下圖：（15，11）循環(huán)碼譯碼電路（15，11）循環(huán)漢明碼與（7，4）循環(huán)漢明碼姨媽電路的工作原理是相同的。但（15，11）循環(huán)漢明碼譯碼器未加伴隨式自發(fā)運(yùn)算電路，在接收完一個(gè)接收矢量后，伴隨式還需要在伴隨式計(jì)算電路循環(huán)一周以糾正所有碼位上可能的錯(cuò)誤。所以這種電路所需譯碼時(shí)間較長，不能進(jìn)行連續(xù)譯碼。采