數(shù)字通信原理8差錯(cuò)控制編碼學(xué)習(xí)教案

1、數(shù)字通信原理數(shù)字通信原理(yunl)8差錯(cuò)控制編碼差錯(cuò)控制編碼第一頁，共101頁。1、差錯(cuò)控制編碼的基本原理 編碼：在信息(xnx)碼組上附加一定位數(shù)的監(jiān)督碼元，使其與信息(xnx)位按某種規(guī)則相互關(guān)聯(lián)； 檢錯(cuò)與糾錯(cuò)：若數(shù)據(jù)在傳輸過程中發(fā)生差錯(cuò)，關(guān)聯(lián)關(guān)系被破壞，從而可檢出和/或糾正錯(cuò)誤第1頁/共100頁第二頁，共101頁。 2、差錯(cuò)控制主要類型 檢錯(cuò)重發(fā)（ARQ） 設(shè)備較簡單；傳輸序列中冗余量較小； 需要有反向信道支持；出錯(cuò)后重傳造成延時(shí)較大。 前向糾錯(cuò)（FEC） 適用于包括沒有(mi yu)反向信道的場合； 出錯(cuò)時(shí)可糾正誤碼，無需重傳，延時(shí)?。?傳輸序列中冗余量較大。 混合系統(tǒng) 前向糾錯(cuò)（F

2、EC）檢錯(cuò)重發(fā)（ARQ） 出錯(cuò)較少時(shí)FEC起作用；出錯(cuò)較多時(shí)ARQ起作用第2頁/共100頁第三頁，共101頁。 3、差錯(cuò)控制編碼的分類 線性碼：信息(xnx)碼與監(jiān)督碼之間的關(guān)系為線性關(guān)系； 非線性碼：信息(xnx)碼與監(jiān)督碼之間的關(guān)系為非線性關(guān)系。 分組碼：信息(xnx)碼與監(jiān)督碼以組為單位建立關(guān)系； 卷積碼：監(jiān)督碼與本組和前面碼組中的信息(xnx)碼有關(guān)。 系統(tǒng)碼： 編碼后碼組中信息(xnx)碼保持原圖樣順序不變； 非系統(tǒng)碼：編碼后碼組中原信息(xnx)碼原圖樣發(fā)生變化。第3頁/共100頁第四頁，共101頁。第4頁/共100頁第五頁，共101頁。因任何一位誤碼，都會(huì)變成禁用碼組，所以可檢出

3、一位誤碼。 c. 若規(guī)定許用碼組：000，111禁用碼組：001，010，011，100，101，110每個(gè)碼組可攜帶1比特信息，碼組具有檢測出兩位及以下的誤碼，或糾正一位誤碼的能力。第5頁/共100頁第六頁，共101頁。第6頁/共100頁第七頁，共101頁。第7頁/共100頁第八頁，共101頁。8、幾種常用的檢錯(cuò)編碼 奇偶校驗(yàn)碼 在信息(xnx)碼組an-1,an-2,a1中加入監(jiān)督位a0，使編碼后碼組中 “1”的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。 偶校驗(yàn)：取a0，使下式成立 an-1an-2 a1 a0 0 a0 = an-1an-2 a1 奇校驗(yàn)：取a0，使下式成立 an-1an-2

4、 a1 a0 1 a0 = an-1an-2 a1 1第8頁/共100頁第九頁，共101頁。第9頁/共100頁第十頁，共101頁。第10頁/共100頁第十一頁，共101頁。第11頁/共100頁第十二頁，共101頁。第12頁/共100頁第十三頁，共101頁。第13頁/共100頁第十四頁，共101頁。第14頁/共100頁第十五頁，共101頁。 9、線性分組碼 基本定義(dngy) 碼重W：碼組/碼字中非零碼元的數(shù)目； 碼距d（漢明(Hamming)距）：兩碼組/碼字中對(duì)應(yīng)碼元位置上取值不同的個(gè)數(shù)稱為碼組/碼字間的距離，簡稱碼距； 最小碼距dmin：準(zhǔn)用碼組/碼字空間中任兩碼組間的最小距離。第15頁

5、/共100頁第十六頁，共101頁。9、線性分組碼 線性分組碼的檢錯(cuò)能力與碼距的關(guān)系(gun x)(1)要在一個(gè)碼組中檢出e個(gè)誤碼，要求 dmin e1 即任一碼組產(chǎn)生小于等于e個(gè)誤碼時(shí)，都不會(huì)變成另一準(zhǔn)用碼組。 圖中，Ci和Cj是 兩個(gè)準(zhǔn)用碼組第16頁/共100頁第十七頁，共101頁。9、線性分組碼 線性分組碼的糾錯(cuò)(ji cu)能力與碼距的關(guān)系(2)要在一個(gè)碼組中能糾正t個(gè)誤碼，要求 dmin 2t1 將以t為半徑的“球”內(nèi)所有的禁用碼組均判為球心中的準(zhǔn)用 碼組，可糾正t個(gè)以內(nèi)的錯(cuò)誤。 圖中，Ci和Cj是 兩個(gè)準(zhǔn)用碼組第17頁/共100頁第十八頁，共101頁。9、線性分組碼 線性分組碼的檢錯(cuò)

6、糾錯(cuò)能力與碼距的關(guān)系 (3)要在一個(gè)碼組中能糾正t個(gè)誤碼，同時(shí)(tngsh)檢出e (e t) 個(gè)誤碼，要求 dmin et1 當(dāng)誤碼數(shù)小于等于t時(shí)，可糾正； 當(dāng)誤碼數(shù)大于t小于等于e時(shí)，不會(huì)落入另一碼組的糾錯(cuò)范 圍內(nèi)第18頁/共100頁第十九頁，共101頁。9、線性分組碼 線性分組碼的基本性質(zhì)(定理) (1)兩許用碼組之和（逐位模2和）仍為一許用碼組（封閉性）； (2)碼組間的最小距離等于(dngy)非零碼的最小重量。第19頁/共100頁第二十頁，共101頁。9、線性分組碼 線性分組碼的數(shù)學(xué)(shxu)基礎(chǔ) (1)群的概念 若G是非空集合，在G中定義了一種代數(shù)運(yùn)算，滿足（a）封閉性，對(duì) a、

7、b G，恒有 ab G（b）結(jié)合律，對(duì) a、b、c G，恒有 （ab）c a（bc） （c）有恒等元e存在，對(duì) a G，有 e G，使 aeeaa（d）對(duì) a G，有逆元 a-1 G， 使 aa-1 a-1ae 則稱G構(gòu)成一個(gè)群。第20頁/共100頁第二十一頁，共101頁。9、線性分組碼 線性分組碼的數(shù)學(xué)基礎(chǔ)(jch) (2)矢量空間的概念 在群G中，若 a、b G，恒有 abba，則稱G為交換群或阿貝爾群。 在阿貝爾群G中定義F域上的數(shù)乘、且分配率成立， a、b G， A F，有 A（ab）AaAb則稱該群為矢量空間V。第21頁/共100頁第二十二頁，共101頁。9、線性分組碼 線性分組碼的

8、數(shù)學(xué)基礎(chǔ) (2)矢量空間的概念(續(xù)) 矢量子空間 矢量空間V中的一個(gè)子集(z j)S，若滿足： 全0矢量（恒等元e）在S中； S中的任意兩個(gè)矢量的和（運(yùn)算 “”）也在S中 （封閉性）； 則稱S為子空間。第22頁/共100頁第二十三頁，共101頁。9、線性分組碼 線性分組碼的數(shù)學(xué)基礎(chǔ) (3)n維線性空間 一個(gè)由2n個(gè)n維二進(jìn)制數(shù)組組成的集合，定義如下(rxi)的加乘運(yùn)算 則該集合構(gòu)成一n維線性空間Vn。 第23頁/共100頁第二十四頁，共101頁。9、線性分組碼 線性分組碼的數(shù)學(xué)基礎(chǔ) (4) 子空間(kngjin)與線性分組碼 在2n個(gè)n維二進(jìn)制數(shù)組中可選擇2k個(gè)數(shù)組構(gòu)成Vn上的子空間(kngj

9、in)，子空間(kngjin)上的元素構(gòu)成線性分組碼。第24頁/共100頁第二十五頁，共101頁。第25頁/共100頁第二十六頁，共101頁。9、線性分組碼 線性分組碼示例 例1：4維線性空間V4及其子空間S V4的所有元素 V4空間的一個(gè)(y )子空間 容易驗(yàn)證它包含“0”元素(0000), 且滿足按位求和運(yùn)算 的封閉性。第26頁/共100頁第二十七頁，共101頁。9、線性分組碼 線性分組碼示例 例2： （6，3）線性分組碼 可以(ky)驗(yàn)證：對(duì)3位的信息碼組采用如下6為的碼字集編碼，該碼字集構(gòu)成一線性子空間。第27頁/共100頁第二十八頁，共101頁。9、線性分組碼 生成矩陣G的概念 選擇

10、線性空間V中k個(gè)線性無關(guān)(wgun)(獨(dú)立)的n元組： V1,V2,V3,Vk 以此為基構(gòu)成所有2k個(gè)線性組合S可以表示為： 其中mi0或1。顯然，S是V的一個(gè)子空間。 記 則有 矩陣G稱為生成矩陣。第28頁/共100頁第二十九頁，共101頁。9、線性分組碼 生成矩陣G的概念(續(xù)) 例：利用矩陣G計(jì)算（許用）碼字，已知生成矩陣 編碼(bin m)前的信息碼組為110，生成的碼字為：第29頁/共100頁第三十頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式(校正(jiozhng)子) 例：具有糾正一位誤碼的分組碼 C6C5C4C3 C2C1C0 n = 7, k = 4, 信息位

11、 監(jiān)督位 r = nk3 傳輸過程中如果發(fā)生某一位錯(cuò)誤，如在C3位置出錯(cuò)， 則相當(dāng)于 C6C5C4C3C2C1C0000E3000 = C6C5C4(C3E3)C2C1C0 其中： E31 定義一組確定誤碼位置的參量:校正(jiozhng)子/伴隨式 S1S2S3 第30頁/共100頁第三十一頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式(續(xù)) 設(shè)建立1位誤碼與校正子的對(duì)應(yīng)關(guān)系如下(rxi)（亦可建立其它關(guān)系） 由表格關(guān)系，校正子與誤碼Ei的關(guān)系，如表中的S1，當(dāng) E2、E4、E5、E6中有一個(gè)為1時(shí)，S11； S1E6E5E4E2 同理可得， S2E6E5E3E1 S3E6

12、E4E3E0 S1S2S3誤碼位置S1S2S3誤碼位置0010000001101001000001000000101100100000100000010011110000000110001000000 0000000 無誤第31頁/共100頁第三十二頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式(續(xù)) 由此，當(dāng)出現(xiàn)一位誤碼時(shí)，校正子能夠確定誤碼的位置。 當(dāng)無誤碼時(shí)，顯然有 S1E6E5E4E20 S2 E6E5E3E10 S3E6E4E3E00 編碼(bin m)時(shí),通過選擇監(jiān)督位C0C1C2的取值來保證正常情況下： S1C6C5C4C20 S2C6C5C3C10 S3C6C

13、4C3C00 上述方程亦稱為監(jiān)督方程。 (*) 由監(jiān)督方程可以解得，監(jiān)督位C0C1C2的取值分別為： C0 C6C4C3 C1C6C5C3 C2C6C5C4 給出一組信息碼C6C5C4C3 ，可計(jì)算出監(jiān)督位C2C1C0。構(gòu)成碼： C6C5C4C3C2C1C0。 注意：信息位與監(jiān)督位間的關(guān)系為線性關(guān)系。第32頁/共100頁第三十三頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨(bn su)式(續(xù)) 例（續(xù)前）： 設(shè)信息碼組C6C5C4C30101 C2C6C5C4 0101 C1C6C5C3 0110 C0C6C4C3 0011 構(gòu)成發(fā)送碼字： C6C5C4C3 C2C1C0 0

14、101101 發(fā)送碼字01011101，若接收時(shí)有一位，如C5，出錯(cuò)： C6(C5E5)C4C3 C2C1C00001101 S1C6(C5E5)C4C200011(C6C5C4C2)E5 S2C6(C5E5)C3C100101(C6C5C3C1)E5 S3C6C4C3C0 00000(C6C4C3C0) 根據(jù)校正子 S1 S2 S3110，由表，可判斷誤碼發(fā)生在C5第33頁/共100頁第三十四頁，共101頁。 9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式 前述的監(jiān)督方程可用矩陣形式表示(biosh) 其一般形式為： un-1un-2u1u0是發(fā)送碼字/碼組，矩陣H稱為監(jiān)督矩陣。 第34頁

15、/共100頁第三十五頁，共101頁。9、線性分組碼 生成矩陣(j zhn)的構(gòu)建、監(jiān)督矩陣(j zhn)和伴隨式(續(xù)) 對(duì)上例，觀察P37（*）式（監(jiān)督方程），有：S1C6C5C4C20S2C6C5C3C10 S3C6C4C3C00 方程組的矩陣(j zhn)表示形式為：第35頁/共100頁第三十六頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式 其中，監(jiān)督矩陣H為： 校正子與誤碼的位置的關(guān)系 由H的列向量反映 監(jiān)督矩陣的性質(zhì)： （a）H由碼元間的監(jiān)督關(guān)系唯一確定； （b）H的行向量相互獨(dú)立，當(dāng)采用系統(tǒng)(xtng)碼結(jié)構(gòu)時(shí)，具有形式 ，其中Ir是rr（rn-k）單位陣。第36頁

16、/共100頁第三十七頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督(jind)矩陣和伴隨式 在上例中，監(jiān)督(jind)位的產(chǎn)生可表示為 一般地，對(duì)于線性分組碼(n，k)，上述關(guān)系可表示為 其中監(jiān)督(jind)位 rnk： 第37頁/共100頁第三十八頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式 監(jiān)督位矩陣的轉(zhuǎn)置表達(dá)式為： 若將信息位排列在碼組的前半部，監(jiān)督排列在碼組的后半部， 則有： 生成矩陣可定義為： 其中Ik是kk的單位陣。系統(tǒng)(xtng)碼形式的發(fā)送碼組可按下式產(chǎn)生第38頁/共100頁第三十九頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督(jind)矩陣和

17、伴隨式 生成矩陣G與監(jiān)督(jind)矩陣H之間的關(guān)系 監(jiān)督(jind)位矩陣可表示為： 生成矩陣可表示為： 其中Ik是kk的單位陣，In-k是(n-k)(n-k)的單位陣 由此得 上述關(guān)系說明：生成矩陣的每一行都是一個(gè)有效的碼字。PIGkknTIPH第39頁/共100頁第四十頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式 伴隨式(校正子)的定義 設(shè) 發(fā)送碼字為 接收碼字為 錯(cuò)誤(cuw)圖樣為 則一般地，有 接收碼字r的伴隨式(校正子)定義為第40頁/共100頁第四十一頁，共101頁。9、線性分組碼 生成矩陣的構(gòu)建、監(jiān)督矩陣和伴隨式 由前面分析，有 其中H的第i列對(duì)應(yīng)第i位單

18、個(gè)錯(cuò)誤時(shí)的伴隨式/校正子 伴隨式只與錯(cuò)誤圖樣和監(jiān)督矩陣有關(guān)，與發(fā)送的碼字無關(guān)。 上式中e是1n的矩陣，而H是rn的矩陣，所得結(jié)果 S是二進(jìn)制數(shù)的1r的矩陣（向量），所有可能組合的個(gè)數(shù)為 若用伴隨式的不同(b tn)組合表征不同(b tn)的錯(cuò)誤，則最多能夠表 征（糾正）2r2n-k個(gè)錯(cuò)誤。 第41頁/共100頁第四十二頁，共101頁。9、線性分組碼 線性分組碼的許用碼字與可糾正的錯(cuò)誤圖樣 對(duì)于線性分組碼（n，k）所有許用碼字和可糾正 的錯(cuò)誤圖樣及組合可表示為一標(biāo)準(zhǔn)陣： 其中U1是許用碼字集中的全0碼字。第一行為無誤碼的許用 碼字；第一列（除全零元素(yun s)的向量U1外）為所有可糾正的錯(cuò)

19、誤圖樣，稱為陪集首。每一行稱為一個(gè)陪集。第42頁/共100頁第四十三頁，共101頁。9、線性分組碼 陪集的伴隨式 陪集中的每一個(gè)(y )元素均有相同的伴隨式。任一陪集可表示為 相應(yīng)的伴隨式為： 陪集首中每一種錯(cuò)誤圖樣，對(duì)應(yīng)于一個(gè)(y )特定的伴隨式。 因此，可用伴隨式來進(jìn)行錯(cuò)誤定位。 第43頁/共100頁第四十四頁，共101頁。9、線性分組碼 糾錯(cuò)碼的譯碼步驟 根據(jù)收到的r和H計(jì)算接收碼字的伴隨式： 根據(jù)S定位錯(cuò)誤圖樣ej 由得到的錯(cuò)誤圖樣ej進(jìn)行糾錯(cuò)：注：如果出現(xiàn)的錯(cuò)誤圖樣不在陪集首內(nèi)，則不能正確地 定位錯(cuò)誤（超出(choch)該種編碼方法能夠糾錯(cuò)的范圍）。第44頁/共100頁第四十五頁，共

20、101頁。9、線性分組碼 線性分組碼的糾錯(cuò)示例：例 線性分組碼（6，3） 標(biāo)準(zhǔn)陣： 其伴隨(bn su)式為： 查詢表：第45頁/共100頁第四十六頁，共101頁。9、線性分組碼 線性分組碼的糾錯(cuò)示例：例 線性分組碼（6，3） 設(shè) 發(fā)送碼字為：101110 接收碼字為：001110 伴隨式： S001110HT100 根據(jù)查詢(chxn)表（或監(jiān)督矩陣），得 錯(cuò)誤圖樣為：100000 差錯(cuò)恢復(fù)計(jì)算： Ure001110+100000101110第46頁/共100頁第四十七頁，共101頁。9、線性分組碼 線性分組碼的糾錯(cuò)示例：例 線性分組碼（6，3） 譯碼器的實(shí)現(xiàn) 已知譯碼器的伴隨(bn su)

21、式為： 即有： 由此，結(jié)合伴隨(bn su)式查詢表，可構(gòu)建相應(yīng)的譯碼電路。第47頁/共100頁第四十八頁，共101頁。9、線性分組碼 線性分組碼的糾錯(cuò)(ji cu)示例：例 線性分組碼（6，3） 譯碼器的譯碼電路第48頁/共100頁第四十九頁，共101頁。9、線性分組碼 線性分組碼具有封閉性：任兩碼組按位之和仍是一個(gè)碼組。 設(shè)任 Ci，Cj C （許用碼組集合），G為生成矩陣，則 式中 是碼組中的信息(xnx)碼部分。 任兩碼組之和： 因?yàn)椋?所以 所以第49頁/共100頁第五十頁，共101頁。9、線性分組碼 線性分組碼的最小距離dmin等于非零碼組最小重量W 即若記 Wi為Ci的碼重，則

22、因?yàn)?yn wi)按定義 又因?yàn)?yn wi) 由線性分組碼的封閉性，有 所以顯然有：第50頁/共100頁第五十一頁，共101頁。9、線性分組碼 漢明界 線性分組碼（n, k）能糾正任意的t個(gè)錯(cuò)誤的必要條件： 陪集數(shù)/伴隨(bn su)式個(gè)數(shù)： 不等式的左邊為伴隨(bn su)式的總數(shù)； 不等式的右邊為所有可能的小于等于t的錯(cuò)誤的總的個(gè)數(shù)。 例 線性分組碼（127，106）所需的陪集數(shù)(由上式可得)第51頁/共100頁第五十二頁，共101頁。9、線性分組碼 完備碼 能糾正任意(rny)的t個(gè)錯(cuò)誤的線性分組碼（n,k）若滿足條件： 則稱該碼為完備碼(perfect code)第52頁/共100頁

23、第五十三頁，共101頁。9、線性分組碼 普洛特金界 線性分組碼（n,k）的最小碼距dmin小于某一上界： 該界稱為普洛特金界。 例 a.判斷線性分組碼（7,2）有無(yu w)糾正任意2個(gè)錯(cuò)誤的可能 因 所以不可能。 b.判斷線性分組碼（8,2）有無(yu w)糾正任意2個(gè)錯(cuò)誤的可能 因 所以有可能。第53頁/共100頁第五十四頁，共101頁。9、線性分組碼 漢明碼 能夠糾正1位誤碼，且滿足下列條件 的線性分組碼，稱為漢明碼。 例：可驗(yàn)證如下監(jiān)督(jind)矩陣對(duì)應(yīng)的線性分組碼是漢明碼 或100110101010110010111H第54頁/共100頁第五十五頁，共101頁。tnnnkn.21

24、12第55頁/共100頁第五十六頁，共101頁。9、線性分組碼 生成矩陣的變換 在線性分組碼(n,k)的碼字集(子空間)中，如果能夠找到k個(gè)線性無關(guān)的碼字，即可構(gòu)成生成矩陣； 簡單地由k個(gè)線性無關(guān)的碼字構(gòu)成的生成矩陣未必是系統(tǒng)碼生成矩陣； 通過矩陣變換可將非系統(tǒng)碼的生成矩陣變換成系統(tǒng)碼生成矩陣； 生成矩陣的變換并不改變碼字集中碼字的圖樣，僅僅(jnjn)改變碼字集中碼字與信息碼組的對(duì)應(yīng)關(guān)系。 第56頁/共100頁第五十七頁，共101頁。9、線性分組碼 生成矩陣的變換(binhun)(續(xù)) 例：已知線性分組(7,4)中4個(gè)線性無關(guān)的碼字： 1011000，0010110，0101100，0001

25、011 求關(guān)于該碼字集的系統(tǒng)碼生成矩陣和監(jiān)督矩陣。 解：該3碼字構(gòu)成的生成矩陣可表示為 非 或 形式，所以為非系統(tǒng)碼生成矩陣。 第57頁/共100頁第五十八頁，共101頁。9、線性分組碼 解(續(xù))：對(duì)生成矩陣做線性變化，使其左側(cè)成為標(biāo)準(zhǔn)(biozhn)陣， 得到新的生成矩陣 第58頁/共100頁第五十九頁，共101頁。9、線性分組碼 解(續(xù))： 該碼的生成矩陣具有系統(tǒng)(xtng)碼生成矩陣的形式 相應(yīng)地監(jiān)督矩陣為 PIGk1101000011010011100101010001第59頁/共100頁第六十頁，共101頁。第60頁/共100頁第六十一頁，共101頁。第61頁/共100頁第六十二頁，

26、共101頁。10、循環(huán)碼 同余類的概念 在整數(shù)除法中，取定除數(shù)n，可將所有整數(shù)按除以n所得(su d)余 數(shù)進(jìn)行分類，余數(shù)相同的數(shù)稱為關(guān)于n的同余類。 一般地，若 （Q為整數(shù)，p n） 則記為： 所有余數(shù)為p的整數(shù)屬于關(guān)于模n的一個(gè)同余類。第62頁/共100頁第六十三頁，共101頁。10、循環(huán)碼 同余類的概念（續(xù)前） 類似地，可以定義關(guān)于多項(xiàng)式N(x)的同余類，若 式中Q(x)為整式，余式R(x)的冪 N(x)的冪。 上式可寫成： 記為： 例：在系數(shù)(xsh)為二元域的多項(xiàng)式中，有 因?yàn)椋?從而有上述結(jié)論。第63頁/共100頁第六十四頁，共101頁。10、循環(huán)碼 循環(huán)碼的代數(shù)(dish)結(jié)構(gòu)

27、定理1 若U(X)是長度為n的循環(huán)碼中的一個(gè)碼多項(xiàng)式，則 XiU(X)（i為不等于0的整數(shù)）按模 Xn1運(yùn)算的余 式必為循環(huán)碼中的另一碼多項(xiàng)式。 證明：設(shè)i1，有第64頁/共100頁第六十五頁，共101頁。10、循環(huán)碼循環(huán)碼的代數(shù)結(jié)構(gòu)（續(xù)） 余式為 對(duì)應(yīng)碼組un-1 un-2 u1 u0左循環(huán)一位之后(zhhu)的得到的碼組： un-2 u1 u0 un-1。 若i2第65頁/共100頁第六十六頁，共101頁。10、循環(huán)碼 循環(huán)碼的代數(shù)結(jié)構(gòu)（續(xù)） 顯然，余式為對(duì)應(yīng)碼組un-1un-2u1u0左循環(huán)兩位之后的得到的 碼組。一般地，對(duì)任意i有： 余式對(duì)應(yīng)un-1un-2u1u0左循環(huán)i位之后的得到

28、的碼組。 證畢 (容易(rngy)用歸納法嚴(yán)格證明)第66頁/共100頁第六十七頁，共101頁。10、循環(huán)碼 循環(huán)碼的代數(shù)結(jié)構(gòu)(jigu)（續(xù)）例 已知碼組的長度為n4，其中一碼字：U1101(高位在右)， 求該碼字循環(huán)移位3位后得到的碼字。 a. 由1101直接(右)循環(huán)移3位得：U(3)1011 b. 根據(jù)多項(xiàng)式關(guān)系求解，當(dāng)i3時(shí)， 關(guān)于X4+1的余式U(3)(X) - 1011第67頁/共100頁第六十八頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成多項(xiàng)式g(x)及生成矩陣 一般地，線性分碼組可表示為矩陣G中每一行均為一許用碼組，如第i行對(duì)應(yīng)第i個(gè)信息位為1，其余為0時(shí)的信息碼生成的碼組。

29、由于G中包含一個(gè)Ik分塊，所以G為k個(gè)獨(dú)立的碼組組成(z chn)的矩陣。即： 任一線性分組碼碼組均可由k個(gè)線性無關(guān)的碼組組合而成。 第68頁/共100頁第六十九頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成多項(xiàng)式g(x)及生成矩陣(續(xù)) 利用上述線性分組碼任一線性分組碼碼組均可由k個(gè)線性無關(guān)的碼組組合而成 這一性質(zhì)，尋求循環(huán)碼生成矩陣的構(gòu)建方法。 設(shè)存在一個(gè)冪次數(shù)(csh)為nk，且常數(shù)項(xiàng)不為0的碼多項(xiàng)式g(X)， 則由循環(huán)碼的性質(zhì)（定理1） g(X)，Xg(X),，Xk-2g(X)，Xk-1g(X) (最高次冪等于n1) 也是碼多項(xiàng)式，這k個(gè)碼多項(xiàng)式對(duì)應(yīng)獨(dú)立的k個(gè)碼字，由此可構(gòu) 成循環(huán)碼生成矩

30、陣G(X)。第69頁/共100頁第七十頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成多項(xiàng)式g(X)及生成矩陣(續(xù)) 循環(huán)碼生成矩陣G(X)： 其中，g(X)稱為循環(huán)碼碼生成多項(xiàng)式。G(X)對(duì)應(yīng)的系數(shù)矩陣G 右側(cè)的子方陣具有主對(duì)角線元素均不為0的形式。該子陣行列 式不為0，因而子陣滿秩，因而行向量是線性無關(guān)(wgun)的。 利用碼生成矩陣G(X)，任一碼字多項(xiàng)式可以表示為： 或：第70頁/共100頁第七十一頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成(shn chn)多項(xiàng)式g(X)及生成(shn chn)矩陣(續(xù)) 例（7，3）生成(shn chn)多項(xiàng)式 g(X)X4+X3+X2+1 對(duì)應(yīng)生成(sh

31、n chn)矩陣GX 矩陣為： 因?yàn)榫仃嘒左側(cè)的子方陣滿秩，因此容易判斷該矩陣中的 行向量是線性無關(guān)的。第71頁/共100頁第七十二頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成多項(xiàng)式g(X)及生成矩陣(續(xù)) 定理 2 在循環(huán)碼中，nk次的碼多項(xiàng)式g(X)有一個(gè)且只有 一個(gè)。證明： （a）在含k個(gè)信息位的循環(huán)碼中，除全0碼外，其它碼 組最多只有k-1個(gè)連0。否則(fuz)，經(jīng)循環(huán)移位后前面k個(gè)信息碼 元為0，而監(jiān)督碼元不全為0的碼組，這在線性分組碼中是不 可能的。所以一定有一個(gè)nk次的多項(xiàng)式。 （b）nk次的碼多項(xiàng)式g(X)的常數(shù)項(xiàng)不能為0，否則(fuz) 該多項(xiàng)式右移一位就會(huì)出現(xiàn)k個(gè)連0的情況。

32、第72頁/共100頁第七十三頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成多項(xiàng)式g(X)及生成矩陣(續(xù)) （c） nk次的碼多項(xiàng)式g(X)只可能有一個(gè)(y )，若有兩個(gè)， 兩多項(xiàng)式相加后由線性分組碼的封閉性仍為碼多項(xiàng)式，但 由于nk次項(xiàng)和常數(shù)項(xiàng)相消，會(huì)產(chǎn)生k1連0的情況， 由（a）分析，這是不可能的。 綜上（a）、（b）和（c），證畢。第73頁/共100頁第七十四頁，共101頁。第74頁/共100頁第七十五頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成多項(xiàng)式g(X)及生成矩陣(續(xù)) 推論：次數(shù)不大于k1次的任何(rnh)多項(xiàng)式與g(X)的乘積都是 碼多項(xiàng)式。第75頁/共100頁第七十六頁，共101頁。

33、第76頁/共100頁第七十七頁，共101頁。第77頁/共100頁第七十八頁，共101頁。)()(.)()(21XgXXgXgXXgXXGkk第78頁/共100頁第七十九頁，共101頁。10、循環(huán)碼 循環(huán)碼的生成(shn chn)多項(xiàng)式g(x)及生成(shn chn)矩陣(續(xù)) 例：線性分組碼（7，4）生成(shn chn)多項(xiàng)式 g(x)x3+x2+1 對(duì)應(yīng) 生成(shn chn)矩陣Gx對(duì)應(yīng)的系數(shù)矩陣為： 為非系統(tǒng)碼結(jié)構(gòu)的生成(shn chn)矩陣。第79頁/共100頁第八十頁，共101頁。一定是循環(huán)碼的碼多項(xiàng)式，顯然（*）定義的U(X)為一種系統(tǒng)(xtng)碼結(jié)構(gòu)的循環(huán)碼。第80頁/共10

34、0頁第八十一頁，共101頁。10、循環(huán)碼 循環(huán)碼編碼器的電路實(shí)現(xiàn) 由系統(tǒng)(xtng)碼結(jié)構(gòu)循環(huán)碼的編碼方法可知 循環(huán)碼編碼器的實(shí)現(xiàn)需要用到以生成多項(xiàng)式g(x)為除式的 除法器計(jì)算余式p(x):第81頁/共100頁第八十二頁，共101頁。10、循環(huán)碼 循環(huán)碼編碼器的電路實(shí)現(xiàn)(續(xù)) 多項(xiàng)式除法 多項(xiàng)式除法可用帶反饋的移位寄存器實(shí)現(xiàn)。 例：除數(shù)為 g(X)X6X5X4X31 除法電路 如下圖，反饋的接入由g(X)確定 除法運(yùn)算的實(shí)現(xiàn) 先將移位寄存器清“0”； 進(jìn)行n次移位，將被除數(shù)全部(qunb)送入除法器后，在寄存 器內(nèi)即可得到相應(yīng)的余式。第82頁/共100頁第八十三頁，共101頁。10、循環(huán)碼

35、循環(huán)碼編碼器的電路實(shí)現(xiàn)(續(xù)) (接上例)計(jì)算C(X)/g(X)，其中C(X)=X13+X11+X10+X7+X4+X3+X+1 得余式： p(x)x4x2 （容易通過長除法(chf)驗(yàn)證） 移位序號(hào)輸入移位寄存器內(nèi)容輸出商反饋信號(hào)01234567891011121314010110010011011 L 000000 H100000010000101000110100011011001101000001100111110100111010111101111001011011001010余數(shù)00000011100111000000000000000000000000000000000000000

36、0000100111100111100111000000000000100111100111100111 第83頁/共100頁第八十四頁，共101頁。10、循環(huán)碼 循環(huán)碼編碼器的電路實(shí)現(xiàn)(續(xù)) 多項(xiàng)式除法電路的一般(ybn)形式 被除式： 除式： 相應(yīng)實(shí)現(xiàn)電路：第84頁/共100頁第八十五頁，共101頁。10、循環(huán)碼 循環(huán)碼編碼器的電路實(shí)現(xiàn)(續(xù)) 多項(xiàng)式除法(chf)電路的缺點(diǎn) 除法(chf)運(yùn)算在移位進(jìn)行了n-k-1位后才開始，運(yùn)算完成后， 要將余式移出，還要做n-k-1次移位。速度較慢。第85頁/共100頁第八十六頁，共101頁。10、循環(huán)碼 實(shí)際應(yīng)用的循環(huán)碼編碼電路(dinl)特點(diǎn)：采用

37、“預(yù)先乘Xn-k方案”（信號(hào)直接到達(dá)最后一級(jí)），邊移位邊做除法運(yùn)算，當(dāng)k個(gè)信息碼輸入后，同時(shí)完成了除法運(yùn)算。 g(X)=X4+X3+X2+1 （a）當(dāng)信息位輸入時(shí)，開關(guān)K1、K2合下，k個(gè)信息位經(jīng)K2逐位輸出，同時(shí)直接送到最高位做除法，其運(yùn)算等效為：第86頁/共100頁第八十七頁，共101頁。10、循環(huán)碼 實(shí)際應(yīng)用的循環(huán)碼編碼電路特點(diǎn)：采用“預(yù)先乘Xn-k方案”（信號(hào)直接到達(dá)最后一級(jí)），邊移位邊做除法運(yùn)算，當(dāng)k個(gè)信息(xnx)碼輸入后，同時(shí)完成了除法運(yùn)算。 g(X)=X4+X3+X2+1 （a）當(dāng)信息(xnx)位輸入時(shí)，開關(guān)K1、K2合下，k個(gè)信息(xnx)位經(jīng)K2逐位輸出，同時(shí)直接送到最高位做除法，其運(yùn)算等效為：DDDDx x4 4x x3 31 1x x2 2K K1 1K K2 2輸入輸入輸出輸出)(.)()()()(02211XgXmXgXmXgXmXgXmXknnknkkn第87頁/共100頁第八十八頁，共101頁。第88頁/共100頁第八十九頁，共101頁。10、循環(huán)碼 實(shí)際應(yīng)用的循環(huán)碼編碼電路 一般(ybn)形式的（nk）移位寄存器編碼電路，設(shè) 則： 總的所需的移位次數(shù)為n。第89頁/共100