CH11差錯控制編碼課件

第11章差錯控制編碼又稱信道編碼，是提高數(shù)字傳輸可靠性的一種技術(shù)。其基本思想是通過對信息序列作某種變換，使原來彼此獨立、相關(guān)性極小的信息碼元產(chǎn)生某種相關(guān)性，在接收端就可以利用這種規(guī)律性來檢查并糾正信息碼元在信到傳輸中所造成的差錯。比如，考試填空題，改錯題……概述2023/3/141概述糾錯編碼的基本原理糾錯編碼的性能簡單的實用編碼線性分組碼循環(huán)碼卷積碼網(wǎng)格編碼調(diào)制TCM其它編碼第11章差錯控制編碼2023/3/142信電學(xué)院信息工程系——李世銀11.1概述

1.誤碼的主要形式

（1）隨機(jī)錯誤：誤碼的位置隨機(jī)（誤碼間無關(guān)聯(lián)），隨機(jī)誤碼主要由白噪聲引起。（2）突發(fā)錯誤：誤碼成串出現(xiàn)，主要由強(qiáng)脈沖及雷電等突發(fā)的強(qiáng)干擾引起。（3）混合錯誤：以上兩種誤碼及產(chǎn)生原因的組合。11.1差錯控制編碼的基本概念差錯控制的主要方式2023/3/143信電學(xué)院信息工程系——李世銀監(jiān)督碼元：在接收端識別有無錯碼，所以在發(fā)送端需要在信息碼元序列中增加一些除了信息碼元之外的差錯控制碼元，它們稱為監(jiān)督碼元。編碼效率(簡稱碼率)

：設(shè)編碼序列中信息碼元數(shù)量為k，總碼元數(shù)量為n，則比值k/n就是碼率。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的碼率為1/3。冗余度：監(jiān)督碼元數(shù)(n-k)和信息碼元數(shù)k之比。不同的編碼方法，有不同的檢錯或糾錯能力。理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。糾錯編碼又稱為差錯控制編碼差錯控制編碼的分類2023/3/145信電學(xué)院信息工程系——李世銀

3.差錯控制編碼的分類（1）線性碼：信息碼與監(jiān)督碼之間的關(guān)系為線性關(guān)系（信息位與監(jiān)督位之間是由一些線性方程聯(lián)系的）；

非線性碼：信息碼與監(jiān)督碼之間的關(guān)系為非線性關(guān)系。（2）分組碼：信息碼與監(jiān)督碼以組為單位建立關(guān)系（將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼）；

卷積碼：監(jiān)督碼與本組和前面碼組中的信息碼有關(guān)。（3）系統(tǒng)碼：編碼后碼組中信息碼保持原圖樣順序(形式)不變;

非系統(tǒng)碼：編碼后碼組中原信息碼原圖樣發(fā)生變化。（4）數(shù)學(xué)方法：

代數(shù)碼:建立在代數(shù)學(xué)基礎(chǔ)上的編碼

幾何碼；算術(shù)碼。分組碼結(jié)構(gòu)11.2差錯控制編碼的基本原理2023/3/146信電學(xué)院信息工程系——李世銀分組碼的結(jié)構(gòu)將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。分組碼的一般結(jié)構(gòu)分組碼的符號：(n,k)N－碼組的總位數(shù)，又稱為碼組的長度（碼長），k－碼組中信息碼元的數(shù)目，n–k＝r,碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。糾錯編碼基本原理2023/3/147信電學(xué)院信息工程系——李世銀3.檢錯與糾錯的基本概念11.2差錯控制編碼的基本原理例1，用1位二進(jìn)制碼的2種編碼組合，分別表示“月有陰晴圓缺”中“月”的四種狀態(tài)。0-圓，1-缺。

a.若任一位或一位以上的錯誤都會變成另一碼組，所以無法檢錯和糾錯。例如，發(fā)送“0”，錯誤收到“1”

b.若用2位二進(jìn)制（有4個碼組），表示“圓、缺”兩種信息。00-圓，11-缺用到的：00，11稱為“許用碼組”：其余不用的，稱為“禁用碼組”：10，01

因任一位誤碼，都會變成禁用碼組，所以可檢出1位誤碼。

續(xù)2023/3/149信電學(xué)院信息工程系——李世銀可見糾錯編碼之所以具有檢錯和糾錯能力，是因為在信息碼元外添加了冗余碼元（監(jiān)督碼元）；直觀地，冗余度越大，許（準(zhǔn)）用碼組間的區(qū)別越大，檢錯和糾錯能力越強(qiáng)。幾個術(shù)語

c.若用3位二進(jìn)制（有8個碼組），表示“圓、缺”兩種信息。000-圓，111-缺。其余為禁用碼。則可發(fā)現(xiàn)兩位及以下的誤碼，并糾正1位誤碼。11.2差錯控制編碼的基本原理2023/3/1410信電學(xué)院信息工程系——李世銀a.

碼重W：碼組中非零碼元的數(shù)目。如“011”碼字的碼重為2；b.碼距d：兩碼組中對應(yīng)碼元位置上取值不同的個數(shù)。如碼字“011”與“110”間碼距為2；c.最小碼距d0（Hamming距）：準(zhǔn)用碼組中任兩碼組間的最小碼距。

幾個術(shù)語

分組碼碼距和糾檢錯能力之間的關(guān)系11.2差錯控制編碼的基本原理2023/3/1411信電學(xué)院信息工程系——李世銀【證】圖中畫出碼組A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以A為圓心的圓上就判決收到的是碼組A，若落于以B為圓心的圓上就判決為碼組B。從而，就能夠糾正兩位錯碼。BtA漢明距離012345td02）為了糾正t個錯碼，要求最小碼距d0

2t+1續(xù)2023/3/1413信電學(xué)院信息工程系——李世銀圖中碼組A和B之間距離為5。按照檢錯能力公式，最多能檢測4個錯碼，即e=d0–1=5–1=4，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時做到兩者，因為當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組立即進(jìn)入另一碼組的圓內(nèi)而被錯誤地“糾正”了。例如，碼組A若錯了3位(超過2位)，就會被誤認(rèn)為碼組B錯了2位造成的結(jié)果，從而被錯“糾”為B。這就是說，檢錯和糾錯公式不能同時成立或同時運用。BtA漢明距離012345td03）為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距續(xù)2023/3/1414信電學(xué)院信息工程系——李世銀 這種糾錯和檢錯結(jié)合的工作方式簡稱糾檢結(jié)合。ABe1tt漢明距離所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組A）發(fā)生e個錯誤之后所處的位置，與其他碼組（譬如碼組B）的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發(fā)生錯誤地“糾正”。因此，由此圖可以直觀看出，要求最小碼距續(xù)2023/3/1415信電學(xué)院信息工程系——李世銀由上節(jié)所述的糾錯編碼原理可知，為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)。11.3糾錯編碼的性能系統(tǒng)帶寬和信噪比的矛盾：傳輸速率和信噪比關(guān)系2023/3/1417信電學(xué)院信息工程系——李世銀若希望提高傳輸速率，可看出勢必導(dǎo)致信噪比下降，誤碼率增大。假設(shè)系統(tǒng)原來工作在圖中C點，提高速率后由C點升到E點。但加用糾錯編碼后，仍可將誤碼率降到D點。這時付出的代價仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)傳輸速率和Eb/n0的關(guān)系對于給定的傳輸系統(tǒng)式中，RB為碼元速率。幾種簡單的常用編碼2023/3/1418信電學(xué)院信息工程系——李世銀11.4.1奇偶效驗碼

在信息碼組an-1,an-2,…,a1中加入監(jiān)督位a0，使編碼后碼組中“1”的個數(shù)為奇數(shù)（奇效驗）或偶數(shù)（偶效驗）。偶效驗：取校驗碼（監(jiān)督碼元）a0，使下式成立

an-1an-2…a1a0＝0

即，a0=an-1an-2…a1奇效驗：取校驗碼（監(jiān)督碼元）

a0，使下式成立an-1an-2…a1a0＝1即，

a0=an-1an-2…a11奇偶效驗碼碼組間最小距離d0＝2，至少可檢出一位誤碼。實際，可檢測所有奇數(shù)個誤碼。(用于計算機(jī)通信）水平奇偶校驗碼11.4幾種簡單的常用編碼2023/3/1419信電學(xué)院信息工程系——李世銀水平奇偶效驗碼特點：在上面的分析中，整個方陣作為一個“碼組”，長度為原來的m倍；可檢出不大于m個的突發(fā)錯誤；在未增加監(jiān)督位的條件下，檢錯能力為原來的m倍，這是香農(nóng)信道編碼定理應(yīng)用的一個例子。

該編解碼所付的代價：緩存空間和延時增大。水平垂直奇偶校驗碼2023/3/1421信電學(xué)院信息工程系——李世銀11.4.3水平垂直二維奇偶效驗碼（方陣碼）8.1差錯控制編碼的基本概念a1n-1a1n-2……a11

a10a2n-1a2n-2……a21a20

……………ann-1ann-2……an1an0

在水平奇偶監(jiān)督碼的基礎(chǔ)上增加列的奇偶效驗可檢出任一行和任一列的所有奇數(shù)個錯誤，及長度不大于行數(shù)（按列發(fā)）或不大于列數(shù)（按行發(fā)）的突發(fā)錯誤。其他校驗碼2023/3/1422信電學(xué)院信息工程系——李世銀11.4.4恒比碼每個碼組中含“1”和“0”的個數(shù)的比例恒定，又稱等重碼能檢測出所有奇數(shù)個錯誤，并能部分檢測出偶數(shù)個錯誤（成對交換錯則檢測不出）簡單，適應(yīng)于對字母或符號進(jìn)行編碼11.4.5群計數(shù)碼碼組中的監(jiān)督碼元是信息序列中“1”碼個數(shù)的二進(jìn)制表示；假設(shè)待編碼信息序列為，則編碼后碼組為101；較強(qiáng)的檢錯能力，能檢測出幾乎所有形式的差錯（除同時發(fā)生“0”變“1”和“1”變“0”的成對錯誤外）正反碼2023/3/1423信電學(xué)院信息工程系——李世銀先將接收碼組中信息位和監(jiān)督位按模2相加，得到一個合成碼組。然后，由此合成碼組產(chǎn)生一個校驗碼組：若接收碼組的信息位中有奇數(shù)個“1”，則合成碼組就是校驗碼組；若接收碼組的信息位中有偶數(shù)個“1”，則取合成碼組的反碼作為校驗碼組。最后，觀察校驗碼組中“1”的個數(shù)，按下表進(jìn)行判決及糾正可能發(fā)現(xiàn)的錯碼。

正反碼的解碼：校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0”信息碼中有1位錯碼，其位置對應(yīng)校驗碼組中“0”的位置3有4個“0”和1個“1”監(jiān)督碼中有1位錯碼，其位置對應(yīng)校驗碼組中“1”的位置4其他組成錯碼多于1個例2023/3/1425信電學(xué)院信息工程系——李世銀例，發(fā)送1100111001，無錯接收，則合成碼組應(yīng)為1100111001=00000。由于接收碼組信息位中有奇數(shù)個“1”，所以校驗碼組就是00000。按上表判決，結(jié)論是無錯碼。若傳輸中產(chǎn)生了差錯：接收碼組錯成1000111001，則合成碼組1000111001＝01000。由于接收碼組中信息位有偶數(shù)個“1”，所以校驗碼組應(yīng)取合成碼組的反碼，即10111。按上表判斷信息位中左邊第2位為錯碼。若接收碼組錯成1100101001，則合成碼組1100101001＝10000。由于接收碼組中信息位有奇數(shù)個“1”，故校驗碼組就是10000，按上表判斷，監(jiān)督位中第1位為錯碼。若接收碼組為1001111001，則合成碼組1001111001＝01010，校驗碼組與其相同，按上表判斷，這時錯碼多于1個。上述長度為10的正反碼具有糾正1位錯碼的能力，并能檢測全部2位以下的錯碼和大部分2位以上的錯碼。線性分組碼2023/3/1426信電學(xué)院信息工程系——李世銀例：具有糾正一位誤碼的分組碼（7，4）

a6a5a4a3a2a1a0

n=7,k=4,

信息位監(jiān)督位r=n－k＝311.5線性分組碼定義一組確定誤碼位置的參量：S1S2S3(校正子)

由上表可得：如何確定a2a1a0?監(jiān)督位確定當(dāng)出現(xiàn)一位誤碼時，校正子能夠確定誤碼的位置。S1S2

S3錯碼位置S1S2

S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯碼11.5.2校正子（續(xù)）2023/3/1429信電學(xué)院信息工程系——李世銀由此,編碼時監(jiān)督位的產(chǎn)生：給出一組信息碼a6a5a4a3，可計算出監(jiān)督位a2a1a0。例11.5線性分組碼11.5.3監(jiān)督方程當(dāng)無誤碼時，應(yīng)有上述方程亦稱為監(jiān)督方程。2023/3/1430信電學(xué)院信息工程系——李世銀例：

設(shè)信息碼組a6a5a4a3＝0101

則監(jiān)督位為：若接收時有一位(a5)碼出錯：

a6a5a4a3a2a1a0＝0001101則有：S1＝a6a5a4a2＝0001=1

S2＝a6a5a3a1＝0010=1

S3＝a6a4a3a0＝0011=0根據(jù)校正子S1S2S3＝110，可判斷誤碼發(fā)生在a5，并恢復(fù)。則發(fā)送碼組：

a6a5a4a3a2a1a0＝0101101

11.5線性分組碼監(jiān)督矩陣2023/3/1431信電學(xué)院信息工程系——李世銀

11.5.4監(jiān)督矩陣11.5線性分組碼監(jiān)督矩陣該監(jiān)督方程可用矩陣形式表示可用表示為前述的監(jiān)督方程2023/3/1432信電學(xué)院信息工程系——李世銀前述的監(jiān)督方程可用矩陣形式表示11.5線性分組碼矩陣H稱為監(jiān)督矩陣。監(jiān)督矩陣一般式及性質(zhì)

這里

11.5.4監(jiān)督矩陣2023/3/1433信電學(xué)院信息工程系——李世銀一般地，對于任意的監(jiān)督方程都可用矩陣形式表示11.5線性分組碼矩陣H稱為監(jiān)督矩陣。監(jiān)督矩陣的性質(zhì)：（1）H由碼元間的監(jiān)督關(guān)系[S]唯一確定；（2）H的行向量相互獨立，當(dāng)采用系統(tǒng)碼結(jié)構(gòu)時，具有形式H=[PIr]其中Ir是r×r單位陣。并稱之為典型監(jiān)督矩陣。（3）若發(fā)[A]，收到[B]，H[B]T≠[0]則有誤碼。

11.5.4監(jiān)督矩陣生成矩陣2023/3/1434信電學(xué)院信息工程系——李世銀11.5.5生成矩陣在上例中，根據(jù)監(jiān)督方程，監(jiān)督位的產(chǎn)生可表示為可用矩陣表示為一般式即其中，11.5線性分組碼2023/3/1435信電學(xué)院信息工程系——李世銀其轉(zhuǎn)置形式：式中例定義為生成矩陣。

其中Ik是k×k的單位陣，k為信息位數(shù)。發(fā)送碼組可按下式產(chǎn)生：直接得到整個碼組，而不是只有監(jiān)督位！11.5線性分組碼2023/3/1436信電學(xué)院信息工程系——李世銀如，在上例中可得生成矩陣發(fā)送碼組可按下式產(chǎn)生：11.5線性分組碼三個關(guān)系2023/3/1437信電學(xué)院信息工程系——李世銀11.5.6

校正[S]與[H]及誤碼碼組[E]的關(guān)系

11.5線性分組碼設(shè)發(fā)送碼組為[A]，接收碼組為[B]誤碼碼組為：[E]=[B]-[A]=[en-1en-2……e1e0]在接收端計算校正子為矩陣E常稱為錯誤樣圖。（實際中只知道B而并不知道A和E）[S]=[B]HT={[A]+[E]}HT

＝[A]HT+[E]HT

=0+[E]HT=[E]HT可見，[S]僅與[E]和HT有關(guān)，[S]與[E]之間存在確定關(guān)系，所以只需計算[S]，就可得到[E]，從而實現(xiàn)檢錯糾錯。H與G關(guān)系2023/3/1438信電學(xué)院信息工程系——李世銀可見，監(jiān)督矩陣和生成矩陣存在對應(yīng)關(guān)系，線性碼既可以由G確定，也可以直接由H生成。使用場合11.5.7H和G矩陣對應(yīng)關(guān)系2023/3/1439信電學(xué)院信息工程系——李世銀通常，編碼時使用生成矩陣，譯碼時使用監(jiān)督矩陣。[S]=[B]HT=[E]HT例E、S、監(jiān)督方程、P、H、G六者之間是相互關(guān)聯(lián)，一一對應(yīng)的。一個改變必然導(dǎo)致其它5者的相應(yīng)變化。2023/3/1440信電學(xué)院信息工程系——李世銀【例1】給定一個（7，4）線性分組碼的生成矩陣若信息碼為d=1101，求該信息碼的線性分組編碼。解：

采用生成矩陣進(jìn)行編碼11.5.8應(yīng)用舉例2023/3/1441信電學(xué)院信息工程系——李世銀例2所以，該信息碼的線性分組編碼為：2023/3/1442信電學(xué)院信息工程系——李世銀【例2】已知線性（6，3）碼的生成矩陣為求線性分組碼、各碼組的碼重、最小碼距和該碼的差錯控制能力。解：

因為k=3，所以信息碼碼組組成的矩陣為（3×8階）矩陣D：2023/3/1443信電學(xué)院信息工程系——李世銀續(xù)則由2023/3/1444信電學(xué)院信息工程系——李世銀可得出分組碼碼組矩陣為碼重2023/3/1445信電學(xué)院信息工程系——李世銀可見非零碼組的最小碼重為3，則分組碼的最小碼距dmin=3；因此，該分組碼能夠檢2位錯；或同時糾1位錯，檢1位錯。例三2023/3/1446信電學(xué)院信息工程系——李世銀

【例3】已知一線性(7，4)碼的生成矩陣為求當(dāng)接收端收到碼組R=［］時，所對應(yīng)的信息碼組D。分析：首先，需要由G推導(dǎo)出[H]；然后，通過[H]計算S；再，判斷糾錯。解2023/3/1447信電學(xué)院信息工程系——李世銀解：根據(jù)前面H與G的關(guān)系可得將接收碼組R=［］代入，可得S2023/3/1448信電學(xué)院信息工程系——李世銀第7位出錯。所以，接收端收到碼組R=1010110］時，所對應(yīng)的信息碼組D=0010。漢明碼？E、S、監(jiān)督方程、P、H、G六者之間是相互關(guān)聯(lián)，一一對應(yīng)的。一個改變必然導(dǎo)致其它5者相應(yīng)變化。本題S=111對應(yīng)的是a4出錯。所以信息碼應(yīng)為1000。請大家驗證一下！2023/3/1449信電學(xué)院信息工程系——李世銀S1S2

S3錯碼位置S1S2

S3錯碼位置001a0111a4010a1011a5100a2110a6101a3000無錯碼監(jiān)督矩陣錯誤圖樣監(jiān)督方程本題S=111對應(yīng)的是a4出錯。所以信息碼應(yīng)為1000。2023/3/1450信電學(xué)院信息工程系——李世銀11.5.9漢明碼11.5線性分組碼第四講具有下列特點的線性分組碼稱之為漢明碼：碼長：n＝2r－1，信息位k＝2r-r-1，監(jiān)督位：r＝n-k記為：（n，k）＝（2r－1，2r－1－r）最小碼距

dmin＝3，糾錯能力t＝1漢明碼的編碼效率：監(jiān)督矩陣2023/3/1451信電學(xué)院信息工程系——李世銀漢明碼的監(jiān)督矩陣有n列r行，它的n列是除全零以外的r位碼組構(gòu)成，且每一碼組只在某列中出現(xiàn)一次。以r=3為例，可構(gòu)造如下監(jiān)督矩陣其編譯碼可直接根據(jù)H、G使用數(shù)字電路實現(xiàn)。其中，譯碼方法采用計算校正子，然后確定錯誤圖樣并加以糾正。編碼器2023/3/1452信電學(xué)院信息工程系——李世銀編碼器譯碼器編碼器方法1：方法2：2023/3/1453信電學(xué)院信息工程系——李世銀[S]=[B]HT=[E]HT譯碼器擴(kuò)展?jié)h明碼譯碼器方法1：方法2：2023/3/1454信電學(xué)院信息工程系——李世銀*11.5.10擴(kuò)展?jié)h明碼11.5線性分組碼

在漢明碼中增加一位校驗碼（n，k）（n＋1，k），對所有的位作偶監(jiān)督。例：設(shè)原漢明碼（7，4）：

a7a6a5a4a3a2a1a7a6a5a4a3a2a1a0

信息位監(jiān)督位信息位原監(jiān)督位偶校驗位

監(jiān)督矩陣：HHe特點2023/3/1455信電學(xué)院信息工程系——李世銀擴(kuò)展?jié)h明碼特點：

11.5線性分組碼校正子[S’]的確定方法與原漢明碼校正子[S]的確定方法基本相同。只是新增了一個校正子最小碼距：

在糾正1位誤碼的同時可以檢測兩為誤碼。在某些情況下也可以將，漢明碼的碼長和信息位縮短，得到縮短漢明碼。如（5，2）交織碼2023/3/1456信電學(xué)院信息工程系——李世銀*11.5.11交織碼

目的：減小信道中錯誤的相關(guān)性，將長突發(fā)錯誤離散成短突發(fā)錯誤或隨機(jī)錯誤。措施：將m個（n,k）分組碼碼組按行排列成一個m×n的碼陣，從而得到一個（mn，mk）交織碼，并規(guī)定以列的順序自左至右傳送。性能：如果（n,k）可糾正t個誤碼，則（mn,mk）可糾正不大于mt的單個突發(fā)錯誤，或糾正t個長度不大于m的突發(fā)錯誤。循環(huán)碼2023/3/1457信電學(xué)院信息工程系——李世銀11.6.1循環(huán)碼的基本概念（1）定義

對線性分組碼T，如對任意Ti

T，Ti

循環(huán)左移或循環(huán)右移任意位后得到的碼組Ti’仍然有Ti’T，則稱T為循環(huán)碼。（2）碼多項式

為用代數(shù)理論研究循環(huán)碼，可將碼組用多項式表示，該多項式稱為碼多項式。

一般地，長為n的碼組an-1an-2…a1a0，對應(yīng)碼多項式T(x)11.6循環(huán)碼式中，xi的系數(shù)對應(yīng)碼字中ai的取值。例：（7,3）的一個碼字：1001110對應(yīng)x6＋x3＋x2＋x碼多項式的按模運算2023/3/1458信電學(xué)院信息工程系——李世銀所有，在模運算下，一整數(shù)m按模n運算等于其被n除所得之?dāng)?shù)余數(shù)。（3）碼多項式的按模運算在整數(shù)除法中，可進(jìn)行按n運算，若（Q為整數(shù)，p<n）（模n）碼多項式的除法2023/3/1459信電學(xué)院信息工程系——李世銀類似地，可以定義關(guān)于多項式N(x)的除法運算，若式中Q(x)為整式，余式R(x)的冪<N(x)的冪。上式可寫成：記為：此時，碼多項式系數(shù)仍按模2運算，即只取0和1值。例：有例22023/3/1460信電學(xué)院信息工程系——李世銀再如由于在模2運算中，用加法代替了減法，故余項定理12023/3/1461信電學(xué)院信息工程系——李世銀

證明：設(shè)，(1)i＝1時，有

定理1

若T(x)是長度為n的循環(huán)碼中的一個碼多項式，則xiT(x)按模xn＋1運算的余式T’(x)必為循環(huán)碼中的另一碼多項式。P343

可見余式是由碼組an-1an-2…a1a0左循環(huán)一位之后的得到的碼組：an-2…a1a0an-12023/3/1462信電學(xué)院信息工程系——李世銀（接定理1證明），若i＝2顯然，余式為對應(yīng)碼組an-1an-2…a1a0左循環(huán)兩位之后的得到的碼組。

一般地，對任意i有：余式an-i-1an-i-2…a1a0an-1an-2…an-i+1an-i對應(yīng)an-1an-2…a1a0左循環(huán)i位之后的得到的碼組。

證畢循環(huán)碼生成多項式2023/3/1463信電學(xué)院信息工程系——李世銀11.6.2循環(huán)碼的生成多項式g(x)及生成矩陣

定理2循環(huán)碼中，n－k次碼多項式g(x)有且只有一個。g(x)稱為循環(huán)碼碼生成多項式。

P343證明：（1）在含K個信息位的循環(huán)碼中，除全0碼外，其它碼組最多只有k-1個連0。否則，經(jīng)循環(huán)移位后前面k個信息碼元全為0，而監(jiān)督碼元不全為0的碼組，這在線性分組碼中是不可能的。（2）n－k次的碼多項式g(x)的常數(shù)項不能為0，否則該多項式右移一位就會出現(xiàn)k個連0的情況。(因該碼組前k-1位為0)（3）n－k次的碼多項式g(x)只可能有一個，若有兩個，兩多項式相加后由線性分組碼的封閉性仍為碼多項式，但由于n－k次項和常數(shù)項相消，會產(chǎn)生k＋1連0的情況，由（1）分析，這是不可能的。綜上（1）、（2）和（3），證畢。循環(huán)碼生成矩陣2023/3/1464信電學(xué)院信息工程系——李世銀循環(huán)碼生成矩陣G(x)例任一碼多項式都可由其信息碼元和生成矩陣G[x]確定：2023/3/1465信電學(xué)院信息工程系——李世銀例如表11-5的(7,3)循環(huán)碼，n=7,k=3,r=4,唯一的一個(n–k)=4次碼多項式代表的碼組是第二碼組，與它相對應(yīng)的碼多項式，即生成多項式定理3其生成矩陣分別為2023/3/1466信電學(xué)院信息工程系——李世銀11.6.2

循環(huán)碼的生成多項式g(x)及生成矩陣(續(xù))

g(x)為碼多項式A(x)的一個因式，所以T(x)可被g(x)整除。證畢循環(huán)碼生成多項式（續(xù)）定理4推論：次數(shù)不大于k－1次的任何多項式與g(x)的乘積都是碼多項式。定理3在循環(huán)碼中，所有的碼多項式T(x)都能夠被g(x)整除。

P344式11.6-18

證明：因為任一碼多項式都可由其信息碼元和生成矩陣G[x]確定：2023/3/1467信電學(xué)院信息工程系——李世銀11.6.2循環(huán)碼的生成多項式g(x)及生成矩陣(續(xù))

定理4循環(huán)碼（n，k）的生成多項式g(x)是xn＋1的一個因式。其中R(x)的冪小于n。由定理1，R(x)是碼多項式，又由定理3，有R(x)=h(x)g(x)，即有移項整理得：即g(x)是xn＋1的一個因式。證畢總結(jié)證明：因為g(x)冪為n－k，因而可得∵定理1若T(x)是長度為n的循環(huán)碼中的一個碼多項式，則xiT(x)按模xn＋1運算的余式T(i)(x)必為循環(huán)碼中的另一碼多項式。∵定理3在循環(huán)碼中，所有的碼多項式T(x)都能夠被g(x)整除。2023/3/1468信電學(xué)院信息工程系——李世銀11.6.2循環(huán)碼的生成多項式g(x)及生成矩陣(續(xù))

總結(jié)：監(jiān)督多項式定理1

若T(x)是長度為n的循環(huán)碼的一個碼多項式，則xiT(x)按模xn＋1運算的余式T(i)(x)必為循環(huán)碼中的另一碼多項式。定理2循環(huán)碼中，n－k次碼多項式g(x)有且只有一個。g(x)稱為循環(huán)碼碼生成多項式。定理3在循環(huán)碼中，所有的碼多項式T(x)都能夠被g(x)整除。推論：不大于k－1次的任何多項式與g(x)的乘積都是碼多項式。定理4循環(huán)碼（n，k）的生成多項式g(x)是xn＋1的一個因式。生成多項式g(x)的三個性質(zhì)（充要條件）：

（1）g(x)是n－k次多項式；

（2）g(x)的常數(shù)項不等于0；

（3）是xn＋1的一個因式。2023/3/1469信電學(xué)院信息工程系——李世銀

則，對任一碼多項式，T(x)＝I(x)g(x)，有

h(x)T(x)=h(x)[I(x)g(x)]=[h(x)g(x)]I(x)=(xn+1)I(x)

即若T(x)是許用碼組對應(yīng)的多項式，其與h(x)的乘積h(x)T(x)一定可被xn＋1整除。稱h(x)為循環(huán)碼的一致校驗多項式，即監(jiān)督多項式。h(x)是常數(shù)項為1的k次多項式由定理4”循環(huán)碼（n,k）的生成多項式g(x)是xn＋1的一個因式“可知*11.6.3監(jiān)督多項式監(jiān)督矩陣編譯碼2023/3/1470信電學(xué)院信息工程系——李世銀根據(jù)監(jiān)督多項式，可得監(jiān)督矩陣H

其中h*(x)是h(x)的逆多項式。

例*11.6.3監(jiān)督多項式及監(jiān)督矩陣2023/3/1471信電學(xué)院信息工程系——李世銀例如(7，3)循環(huán)碼，g(x)=x4+x3+x2+1，則循環(huán)碼的編譯碼2023/3/1472信電學(xué)院信息工程系——李世銀11.6.4循環(huán)碼的編碼和譯碼1.采用循環(huán)碼生成矩陣：例：若生成多項式g(x)＝x4+x3+x2+1，k=3，則其生成矩陣為：實際的編碼方法對應(yīng)的矩陣G一般不符合[Ik,Q]的形式。編碼輸出結(jié)果相當(dāng)于m(x)g(x)為非系統(tǒng)碼結(jié)構(gòu)。信息碼和監(jiān)督碼不容易區(qū)分。設(shè)數(shù)據(jù)101,則輸出為2023/3/1473信電學(xué)院信息工程系——李世銀

2.系統(tǒng)結(jié)構(gòu)循環(huán)碼的編碼方法11.6.4

循環(huán)碼的編碼和譯碼（續(xù)）（1）以xn-k乘信息多項式m(x)，得到xn-km(x)；（冪<n）

（2）用g(x)除xn-km(x)得余式r(x)(冪<n-k)即

xn-km(x)＝Q(x)g(x)+r(x)（3）編碼輸出的碼多項式

T(x)=xn-km(x)+r(x)（*）

上述編碼方式的合理性：

T(x)=xn-km(x)+r(x)＝[Q(x)g(x)+r(x)]+r(x)=Q(x)g(x)

因為Q(x)的冪次數(shù)小于k，所以Q(x)g(x)一定是循環(huán)碼的碼多項式，顯然（*）定義的T(x)為一種系統(tǒng)碼結(jié)構(gòu)的循環(huán)碼。編譯碼器2023/3/1474信電學(xué)院信息工程系——李世銀*3.循環(huán)碼編碼器的電路實現(xiàn)

8.3.4循環(huán)碼的編碼和譯碼（續(xù)）除法運算的實現(xiàn)過程：先將移位寄存器清“0”；進(jìn)行n次移位，將被除數(shù)全部送入除法器后，在寄存器內(nèi)，即可得到相應(yīng)的余式。例：除數(shù)為g(x)＝x6＋x5＋x4＋x3＋1除法電路，(即r=6)

如下圖，反饋的接入由g(x)確定x6x5x4＋＋＋DDDDD＋Dx31例（a）多項式除法多項式除法可用帶反饋的移位寄存器實現(xiàn)。2023/3/1475信電學(xué)院信息工程系——李世銀（接上例）計算m(x)/g(x)，設(shè)m(x)=x13+x11+x10+x7+x4+x3+x+1,即k=14010110010011011000000100000010000101000110100011010001101000001100111110100111010111101111001011011001010余數(shù)000000111001110x6x5x4＋＋＋DDDDD＋Dx3100000001000001001000000101000101101001001101000001101010000011110011101110100001110101011110111111001010110111100101010除法運算在移位進(jìn)行了r-1位后才開始，運算完成后，要將余式移出，還要做r-1次移位。速度較慢。實際電路2023/3/1476信電學(xué)院信息工程系——李世銀（b）實際應(yīng)用的循環(huán)碼編碼電路

特點：采用“預(yù)先乘xn-k方案”（信號直接到達(dá)最后一級），邊移位邊做除法運算，當(dāng)k個信息碼輸入后，同時也完成了除法運算。（1）當(dāng)信息位輸入時，開關(guān)K1、K2合向下，k個信息位經(jīng)K2逐位輸出，同時直接送到最高位做除法運算：（2）當(dāng)信息位全部輸入后，相應(yīng)除法運算完成，開關(guān)K1、K2合向上，將余數(shù)順序輸出。DD＋D＋D＋x4x31x2K1K2輸入輸出除法原理例2023/3/1477信電學(xué)院信息工程系——李世銀例：設(shè)m(x)=x2＋x＋1111，xn-k＝x7－3＝x4，xn-km(x)＝1110000，上述運算也可看作下列分別運算的結(jié)果：商為：110⊕11⊕1100余數(shù)：1110⊕0111⊕11010100商為：100，余數(shù)為：0100譯碼過程2023/3/1478信電學(xué)院信息工程系——李世銀4.循環(huán)碼的譯碼過程

用生成多項式g(x)除接收碼多項式R(x)，得到余式r(x);通過余式r(x)，計算校正子多項式S(x)；由S(x)確定誤碼的錯誤圖樣E(x)；將E(x)與R(x)相加，糾正錯誤（若在糾錯范圍內(nèi)）。

糾錯譯碼原理2023/3/1479信電學(xué)院信息工程系——李世銀（1）糾錯譯碼原理

a.計算S(x)＝R(x)/g(x)b.確定錯誤圖樣S(x)E(x)c.根據(jù)E(x)糾錯。123n-k......校正子計算電路:S(x)錯誤圖樣識別：E(x)緩沖移位寄存器＋R(x)C(x)例：糾正單個錯誤的電路完成除法運算2023/3/1480信電學(xué)院信息工程系——李世銀*（2）糾正單個錯誤的譯碼電路根據(jù)上節(jié)討論，當(dāng)用于糾正單個錯誤時，只需要記住一個錯誤圖樣。E(x)識別電路可用簡單的邏輯電路來實現(xiàn)。例：g(x)＝x4＋x2＋x＋1ab＋c＋dx4x31x2輸入輸出＋與門DDDDDDD＋設(shè)接收碼組為:1000101余數(shù)dcba:0100一碼組輸入完成后，輸入k個“0”，進(jìn)行信碼輸出和糾錯。本例，當(dāng)輸入第1個0時，輸出第一位信碼，并使dcba=1000，進(jìn)而使與門輸出1，輸入第二個0時，完成錯誤糾正，輸出。循環(huán)碼檢錯能力E(x)識別電路2023/3/1481信電學(xué)院信息工程系——李世銀11.6.5循環(huán)碼的檢錯能力能檢出全部的奇數(shù)個錯碼；能檢測所有與準(zhǔn)用碼距小于dmin的錯誤；能檢出所有長度L<n-k+1的突發(fā)錯誤在突發(fā)長度L大于(n-k)的錯誤中，若L=n-k+1，則(n，k)循環(huán)碼不能檢測的概率為2-(n-k-1)；

若L>n-k+1，則不能檢測的概率為2-(n-k）。BCH碼2023/3/1482信電學(xué)院信息工程系——李世銀截短目的：在設(shè)計糾錯編碼方案時，常常信息位數(shù)k、碼長n和糾錯能力都是預(yù)先給定的。但是，并不一定有恰好滿足這些條件的循環(huán)碼存在。這時，可以采用將碼長截短的方法，得出滿足要求的編碼。截短方法：設(shè)給定一個(n,k)循環(huán)碼，它共有2k種碼組，現(xiàn)使其前i(0<i<k)個信息位全為“0”，變成僅有2k-i種碼組。然后刪去這i位全“0”的信息位，得到一個(n–i,k–i)的線性碼。將這種碼稱為截短循環(huán)碼。截短循環(huán)碼性能：循環(huán)碼截短前后至少具有相同的糾錯能力，并且編解碼方法仍和截短前的方法一樣。

例：要求構(gòu)造一個能夠糾正1位錯碼的(13,9)碼。這時可以由(15,11)循環(huán)碼的11種碼組中選出前兩信息位均為“0”的碼組，構(gòu)成一個新的碼組集合。于是發(fā)送碼組成為(13,9)截短循環(huán)碼。

11.6.6截短循環(huán)碼2023/3/1483信電學(xué)院信息工程系——李世銀11.6.7BCH碼發(fā)現(xiàn)者：Hocguenghem，Bose和Chaudhuri特點：能糾正多個隨機(jī)錯誤，并有嚴(yán)密的數(shù)學(xué)結(jié)構(gòu)循環(huán)碼中一類重要子碼：g(x)與dmin關(guān)系密切BCH碼的碼長n與監(jiān)督位r、糾錯能力t間關(guān)系：

對于任一正整數(shù)m和t(t<m/2)，必定存在一個碼長n=2m-1，監(jiān)督位r=n-k≤mt，能糾正所有不大于t個隨機(jī)錯誤的BCH碼分兩類：本原BCH碼：g(x)中含有最高次數(shù)為m的本原多項式，且碼長n=2m-1非本原BCH碼：

g(x)中不含上述本原多項式，且碼長n是2m-1的一個因子BCH碼及對應(yīng)的生成多項式見P348，表11-6本原多項式2023/3/1484信電學(xué)院信息工程系——李世銀例如m=3時，本原多項式（次數(shù)為m)：（1）是既約的；（2）可以整除（3）不能整除則稱該多項式為最高次數(shù)為m的本原多項式。此時最高次數(shù)為3的本原多項式有兩個：(x3+x2+1)和(x3+x+1)，它們都能除得盡x7-+1，但除不盡x6+1和x5+1。

BCH碼的構(gòu)造見書p348RS碼2023/3/1485信電學(xué)院信息工程系——李世銀11.6.8RS碼多進(jìn)制BCH碼(m=2q進(jìn)制)；具有很強(qiáng)的糾錯能力，特別適合于糾正突發(fā)錯誤；糾t個符號錯誤的(n,k)RS碼：碼長：n=m-1=2q-1個符號bit信息碼元數(shù):k個符號監(jiān)督碼元數(shù)：n-k=2t個符號最小碼距：d0=2t+1個符號卷積碼若將每個m進(jìn)制碼元表示成相應(yīng)的q位二進(jìn)制碼元，則得到的二進(jìn)制碼的參數(shù)為：碼長：n=q(2q–1)（二進(jìn)制碼元）監(jiān)督碼：r=2qt（二進(jìn)制碼元）2023/3/1486信電學(xué)院信息工程系——李世銀11.7卷積碼幾點說明：又名連環(huán)碼，是一種非分組碼與分組碼相比，在同等碼率和相似的糾錯能力下，卷積碼的實現(xiàn)往往更簡單卷積碼主要應(yīng)用于FEC數(shù)據(jù)通信系統(tǒng)中11.7.1基本原理：在任何一段規(guī)定時間里編碼器產(chǎn)生的n個碼元，不僅取決于這段時間中的k個信息碼元,而且還取決于前（N-1）段規(guī)定時間內(nèi)的信息碼元，編碼過程中相互關(guān)聯(lián)的碼元為Nn個。N稱為編碼約束度，N段時間內(nèi)的碼元數(shù)目Nn稱為卷積碼的編碼約束長度。記作(n，k，N)，編碼效率R=k/n。例2023/3/1487信電學(xué)院信息工程系——李世銀1.一種簡單的（2,1,2）卷積碼編碼器編碼器：譯碼編碼過程：輸入一位信息，電子開關(guān)倒換2次，即前半拍（半個輸入碼元寬）接通b端，后半拍接通c端(監(jiān)督位)。監(jiān)督位ci除與本組信息碼元bi有關(guān)外，還跟上一組信息碼元bi-1有關(guān)。并且此監(jiān)督位緊跟此信息位之后發(fā)送出去。D+bcbici輸出信息碼輸入bi簡單(2,1,2)卷積碼編碼器bi-1監(jiān)督位編碼公式：ci=bi+bi-1

tb1b2b3b4b1c1b2c2b3c3b4c4輸入t輸出2023/3/1488信電學(xué)院信息工程系——李世銀解碼器工作過程解碼器輸入端的電子開關(guān)按節(jié)拍把信息碼元與監(jiān)督碼元分接到b'端與c'端；2個移位寄存器的節(jié)拍比碼序列節(jié)拍低一倍，其中移位寄存器D1，D2在信息碼元到達(dá)時移位，監(jiān)督碼元到達(dá)期間保持原狀；而移位寄存器D3在監(jiān)督碼元到達(dá)時移位，信息碼元到達(dá)期間保持原狀；移位寄存器D1、D2和模2加法器1構(gòu)成與發(fā)端一樣的編碼器，它從接收到的信息序列中計算出對應(yīng)的監(jiān)督序列來；模2加法器2把計算出的監(jiān)督序列與接收到的監(jiān)督序列進(jìn)行比較：兩者相同，輸出“0”；兩者不同，輸出“1”，顯然此時，必定出現(xiàn)了差錯。

如果有差錯，則通過大數(shù)邏輯判決門確定差錯位置并糾錯。判決準(zhǔn)則2.簡單(2,1,2)卷積碼的譯碼簡單(2,1,2)卷積碼譯碼器1D2信息碼輸出卷積碼輸入D3Sib'3c'2D1大數(shù)判決“1”的個數(shù)>1？Si-12023/3/1489信電學(xué)院信息工程系——李世銀具體判決如下：根據(jù)譯碼圖，校正子S的方程（即解碼方程）如下：可見每個信息碼元出現(xiàn)在兩個S方程中，即bi'與Si-1和Si有關(guān)，在判決bi'是否有錯時，應(yīng)根據(jù)Si-1和Si的值。決定Si-1和Si值的共有5個碼元，但其中只有bi'與Si-1、Si兩值都有關(guān)，而其他碼元只與一個值有關(guān)。判決準(zhǔn)則2023/3/1490信電學(xué)院信息工程系——李世銀在差錯不多于1個時，根據(jù)正交性得判決規(guī)則如下：①當(dāng)Si-1、Si都為“0”時，解碼方程與編碼方程一致，判決無錯；②當(dāng)Si-1、Si都為“1”時，必定是bi'有錯，給予糾正；③當(dāng)Si-1、Si中只有一個“1”時，必定是bi'以外四個碼元：bi-1'、bi+1'、ci'及ci+1'中的一個出錯，判決bi'無錯；完成上述判決規(guī)則的電路是譯碼器中的移位寄存器D3，與門及模2加法器3：從該例可以看到：該碼可以糾正連續(xù)3個碼組中的一位差錯。卷積碼的幾何描述2023/3/1491信電學(xué)院信息工程系——李世銀11.7.2卷積碼的幾何描述

編碼過程diciei

(3,1,3)卷積碼編碼器bi-2bi輸入bibi-1編碼輸出M2M3M1設(shè)輸入信息比特序列是bi-2

bi-1

bibi+1，則當(dāng)輸入bi時，此編碼器輸出3比特cidiei，輸入和輸出的關(guān)系為：2023/3/1492信電學(xué)院信息工程系——李世銀起始狀態(tài)，各級移位寄存器清零，即M1M2M3為000。M1等于當(dāng)前輸入數(shù)據(jù)(bi)，而移位寄存器狀態(tài)M2M3存儲以前的數(shù)據(jù)(bi-1bi-2)，輸出碼字由下式確定(3,1,3)編碼器的工作過程(狀態(tài))變化如下表狀態(tài)圖原狀態(tài)(M3M2)a(00)b(01)c(10)d(11)輸入(M1)01010101監(jiān)督位輸出(diei)0011011011001001新狀態(tài)(M3M2)a(00)b(01)c(10)d(11)a(00)b(01)c(10)d(11)dicieibi-2bi輸入bibi-1編碼輸出M2M3M12023/3/1493信電學(xué)院信息工程系——李世銀1.狀態(tài)圖

(3,1,3)碼的狀態(tài)圖上表也可以用狀態(tài)轉(zhuǎn)移圖表示，如下圖(a)所示。如果把相同的當(dāng)前狀態(tài)和其下一狀態(tài)重疊起來，就可以得到如圖(b)所示的狀態(tài)圖。cbad110010011111100001000101(b)其中實線代表輸入”0”，虛線代表輸入“1”。樹圖當(dāng)前狀態(tài)下一狀態(tài)abcdabcd00011101110001110010101(a)輸出2023/3/1494信電學(xué)院信息工程系——李世銀100110001cdc100011abd101010cd001110a111000abb110001cdc100011ab011上半部下半部2.樹圖a111000abb000a111ba000111d101010cd010c101db001110a(00)111000輸入信息碼起點01寄存器狀態(tài)a=M3M2＝00b=M3M2＝01c=M3M2＝10d=M3M2＝11輸入1101時，編碼輸出為：111110010100輸出diei網(wǎng)格圖2023/3/1495信電學(xué)院信息工程系——李世銀由節(jié)點和支路組成：節(jié)點表示4種狀態(tài)；支路代表狀態(tài)間的轉(zhuǎn)移關(guān)系(實線代表輸入”0”，虛線代表輸入“1”)；支路上的數(shù)字代表當(dāng)前輸出的監(jiān)督位。3.網(wǎng)格圖

利用樹狀圖中的重復(fù)性，將其中具有相同狀態(tài)的節(jié)點合并到一起，即可得到另一種表示方式：網(wǎng)格圖。起點利用本圖也可以方便得到任意輸入序列的輸出序列和狀態(tài)轉(zhuǎn)移路徑。例：輸入110111在網(wǎng)格圖中每一條路徑就意味著可能發(fā)送的某一個序列組合。概率譯碼輸出：111110010100110101a000aaaaaabbbccccbbcbddddd0000000000000001001001001001101101100100100100101011011011011111111111111111110010010010011101100010110110110112023/3/1496信電學(xué)院信息工程系——李世銀11.7.3卷積碼的概率譯碼（維特比解碼）

有兩種譯碼方法：一是大數(shù)邏輯譯碼，又稱門限譯碼。即，從線性碼的伴隨式出發(fā)，找到一組特殊的能夠檢查信息位置是否發(fā)生錯誤的方程組，從而實現(xiàn)糾錯譯碼。如11.7.1之2。二是概率譯碼。建立在最大似然準(zhǔn)則基礎(chǔ)上，其基本思想是：比較接收序列與所有可能的發(fā)送序列，從中選擇與接收序列漢明距最小的發(fā)送序列作為譯碼輸出。又分為：維持比特譯碼和序列譯碼兩種。

門限譯碼是以分組碼理論為基礎(chǔ)的，其譯碼設(shè)備簡單，速度快，但其誤碼性能比概率譯碼差。概率譯碼例2023/3/1497信電學(xué)院信息工程系——李世銀cbad1010111100010001設(shè)編碼輸入序列為：則編碼器輸出為：111110010100001011000設(shè)接收序列為：

111010010110001011000下面討論其譯碼方法和過程：例實線代表輸入”0”，虛線代表輸入“1”。2023/3/1498信電學(xué)院信息工程系——李世銀由于該卷積碼的約束長度=N*n=3*3=9，因此一般先取接收序列的前9位序列（111010010），同時到達(dá)第三時刻(節(jié)點)的所有可能的8個序列進(jìn)行比較，并保留到達(dá)各節(jié)點路徑中，與接收序列碼距最小的路徑，共4條。以此類推可以得到第4、5、6、7時刻的幸存路徑。到最后第7時刻幸存的路徑即為譯碼輸出。a00起點aaaaaabbbccccbbcbddddd000000000000000000011010101010101001010101111111111111010101011010abc01111111111100111010第一步00d012023/3/1499信電學(xué)院信息工程系——李世銀a00起點aaacbbcbdd000000011010100111111101123a:000000000

111001011b:000000111

111001100c:000111001

111110010d:000111110

11111010111d053647164設(shè)接收序列：111010010110001011000保留到達(dá)各節(jié)點路徑中，與接收序列碼距最小的路徑，共4條：即1110100102023/3/14100信電學(xué)院信息工程系——李世銀a起點aaacbbcbdd00011010011112311設(shè)接收序列：111010010110001011000保留到達(dá)各節(jié)點路徑中，與接收序列碼距最小的路徑，共4條。考查第4時刻1-3d0a1110010113b1110011004c1111100101d11111010142023/3/14101信電學(xué)院信息工程系——李世銀a起點aaacbbcbdd000110100111123411設(shè)接收序列：111010010110001011000保留到達(dá)各節(jié)點路徑中，與接收序列碼距最小的路徑，共4條：即abcd00001010011101111-34d0a11100101100051111100100113b11100101111141111100101002c11100110000171111101010105d111001100110411111010110162023/3/14102信電學(xué)院信息工程系——李世銀a起點aaacbbcbdd0001101001111234設(shè)接收序列：111010010110001011000保留到達(dá)各節(jié)點路徑中，與接收序列碼距最小的路徑，共4條。以此類推abcd001010111-34d0a1111100100113b1111100101002c1111101010105d11100110011042023/3/14103信電學(xué)院信息工程系——李世銀按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。譯碼輸出序列：1101000幸存路徑d0a1111100101000010110000b1111100101000010111113c1111100100110001110016d111110010011000111110710111001abcdabcd0011000011111101102023/3/14104信電學(xué)院信息工程系——李世銀 在上例中卷積碼的約束度N=3，需要存儲和計算8條路徑的參量。由此可見，維特比解碼算法的復(fù)雜度隨約束長度N按指數(shù)形式2N增長。故維特比解碼算法適合約束度較?。∟

10）的編碼。對于約束度大的卷積碼，可以采用其他解碼算法。Turbo碼2023/3/14105信電學(xué)院信息工程系——李世銀Turbo碼是一種特殊的鏈接碼。由于其性能接近信息理論上能達(dá)到的最好性能，所以在編碼理論上是帶有革命性的進(jìn)步。但是，特別是解碼運算，非常復(fù)雜，這里只對其基本概念作一簡明介紹。基本原理由于分組碼和卷積碼的復(fù)雜度隨碼組長度或約束度的增大按指數(shù)規(guī)律增長，所以為了提高糾錯能力，通常將兩種或多種簡單的編碼組合成復(fù)合編碼。

Turbo碼的編碼器在兩個并聯(lián)或串聯(lián)的分量碼編碼器之間增加一個交織器，使之具有很大的碼組長度，能在低信噪比條件下得到接近理想的性能。Turbo碼的譯碼器有兩個分量碼譯碼器，譯碼在兩個分量譯碼器之間進(jìn)行迭代譯碼，故整個譯碼過程類似渦輪（turbo）工作，所以又形象地稱為Turbo碼。11.8Turbo碼編碼器結(jié)構(gòu)2023/3/14106信電學(xué)院信息工程系——李世銀RSCC編碼器和卷積碼編碼器之間的主要區(qū)別是從移存器輸出端到信息位輸入端之間有反饋路徑。兩個RSCC編碼器是相同的。它們的輸入經(jīng)過一個交織器并聯(lián)。此Turbo碼的輸入信息位是bi，輸出是bic1ic2i，故碼率等于1/3。RSCC編碼器交織器RSCC編碼器bibic1ic2i編碼器的基本結(jié)構(gòu)：它由一對遞歸系統(tǒng)卷積碼(RSCC)編碼器和一個交織器組成。RSCC舉例2023/3/14107信電學(xué)院信息工程系——李世銀它是一個碼率等于1/2的卷積碼編碼器，輸入為bi，輸出為bici。因為輸出中第1位是信息位，所以它是系統(tǒng)碼。DDbibiciRSCC編碼器舉例矩陣交織器2023/3/14108信電學(xué)院信息工程系——李世銀若輸入碼元序列是：a11a12…a1m

a21a22…a2m…an1…anm，則輸出序列是：a11a21…an1a12a22…an2…a1m…anm。交織的目的是：將集中的突發(fā)錯碼分散到各個碼組中，變成隨機(jī)錯碼，從而有利于糾錯。這種交織器常用于分組碼。a11a12a1ma21a22a2man1an2anm矩陣交織器其基本形式是矩陣交織器，它由容量為(n-1)m比特的存儲器構(gòu)成。將信號碼元按行的方向輸入存儲器，再按列的方向輸出。卷積交織器2023/3/14109信電學(xué)院信息工程系——李世銀卷積交織器一般說來，由N個移存器和輸入輸出開關(guān)組成。第1個移存器的容量可以是k比特，第2個移存器的容量是2k比特，第3個移存器的容量是3k比特，…，直至第N個移存器的容量是Nk比特。卷積交織法和矩陣交織法相比，主要優(yōu)點是延遲時間短和需要的存儲容量小。卷積交織法端到端的總延遲時間和兩端所需的總存儲容量均為k(N+1)N個碼元，是矩陣交織法的一半。卷積交織器2023/3/14110信電學(xué)院信息工程系——李世銀xxx1234xxx1234xxx1xxx1xxxxxx(a)第1~4比特輸入時的狀態(tài)xx2567834x5678xx25x2x51xxxxx(b)第5~8比特輸入時的狀態(tài)x369362951xxxx9101112101112784x369(c)第9~12比特輸入時的狀態(tài)1013769543211415161112813141516471013471013(d)第13~16比特輸入時的狀態(tài)交織器解交織器卷積交織器卷積交織器2023/3/14111信電學(xué)院信息工程系——李世銀(a)第1~4比特輸入時的狀態(tài)xxx1234xxx1234xxx1交織器xxxxxxx1xx解交織器卷積交織器它是由3個移存器構(gòu)成。3個移存器的容量分別為1b、2b、3b。交織器的輸入碼元依次進(jìn)入各個移存器。第1個輸入碼元直接輸出；第2、3、4個輸入碼元分別存入第1、2、3個移存器中。在這4個碼元期間，交織器的輸出為“1xxx”。這里的“x”表示移存器的初始狀態(tài)值。卷積交織器2023/3/14112信電學(xué)院信息工程系——李世銀(b)第5~8比特輸入時的狀態(tài)xx2567834x5678xx25交織器xxxxx2x51x解交織器在圖(b)中的交織器則示出第5至8個碼元輸入時的工作狀態(tài)。(a)第1~4比特輸入時的狀態(tài)xxx1234xxx1234xxx1交織器xxxxxxx1xx解交織器卷積交織器2023/3/14113信電學(xué)院信息工程系——李世銀在圖(c)和(d)中示出的是第9至12個碼元以及第13至16個碼元輸入時的工作狀態(tài)。以此類推，交織器輸出碼元的次序?qū)⑹牵?xxx52xx963x131074

接收端解交織器的工作過程與此相反，如圖所示，解交織器的輸出碼元的次序?qū)⑹牵簒xxxxxxxxxxx1234其中，前面接收的12個碼元“x”無意義，從第13個碼元開始才是有效碼元。卷積交織器2023/3/14114信電學(xué)院信息工程系——李世銀解碼后的誤碼率信噪比(dB)

20交織器容量10010-110-210-310-410-510-610-7交織器容量大時誤碼率低，這是因為交織范圍大可以使交織器輸入碼元得到更好的隨機(jī)化。交織器容量和誤碼率關(guān)系2023/3/14115信電學(xué)院信息工程系——李世銀低密度奇偶校驗(LDPC)碼是一種線性分組碼，和Turbo碼同屬于復(fù)合碼類。兩者的性能相近，且譯碼延遲都相當(dāng)長，所以它們更適用于一些實時性要求不很高的通信。但是LDPC碼比Turbo碼的譯碼簡單，更易實現(xiàn)。LDPC碼的分類：規(guī)則LDPC碼：H矩陣每列具有相同個數(shù)的“1”。非規(guī)則LDPC碼：H矩陣每列中“1”的個數(shù)不一定相同。非規(guī)則LDPC碼是為改善解碼性能在規(guī)則LDPC碼基礎(chǔ)上發(fā)展出