CH11差錯(cuò)控制編碼課件

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

1.誤碼的主要形式

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

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

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

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

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

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

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

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

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

幾個(gè)術(shù)語(yǔ)

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

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

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

an-1an-2…a1a0＝0

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

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

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

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

a10a2n-1a2n-2……a21a20

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

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

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

S3錯(cuò)碼位置S1S2

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

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

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

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稱(chēng)為監(jiān)督矩陣。監(jiān)督矩陣一般式及性質(zhì)

這里

11.5.4監(jiān)督矩陣2023/3/1433信電學(xué)院信息工程系——李世銀一般地，對(duì)于任意的監(jiān)督方程都可用矩陣形式表示11.5線性分組碼矩陣H稱(chēng)為監(jiān)督矩陣。監(jiān)督矩陣的性質(zhì)：（1）H由碼元間的監(jiān)督關(guān)系[S]唯一確定；（2）H的行向量相互獨(dú)立，當(dāng)采用系統(tǒng)碼結(jié)構(gòu)時(shí)，具有形式H=[PIr]其中Ir是r×r單位陣。并稱(chēng)之為典型監(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)生：直接得到整個(gè)碼組，而不是只有監(jiān)督位！11.5線性分組碼2023/3/1436信電學(xué)院信息工程系——李世銀如，在上例中可得生成矩陣發(fā)送碼組可按下式產(chǎn)生：11.5線性分組碼三個(gè)關(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]在接收端計(jì)算校正子為矩陣E常稱(chēng)為錯(cuò)誤樣圖。（實(shí)際中只知道B而并不知道A和E）[S]=[B]HT={[A]+[E]}HT

＝[A]HT+[E]HT

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

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

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

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

S3錯(cuò)碼位置S1S2

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

dmin＝3，糾錯(cuò)能力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ù)字電路實(shí)現(xiàn)。其中，譯碼方法采用計(jì)算校正子，然后確定錯(cuò)誤圖樣并加以糾正。編碼器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線性分組碼

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

a7a6a5a4a3a2a1a7a6a5a4a3a2a1a0

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

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

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

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

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

對(duì)線性分組碼T，如對(duì)任意Ti

T，Ti

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

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

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

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

定理1

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

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

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

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

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

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

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

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

P344式11.6-18

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

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

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

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

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

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

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

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

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

例*11.6.3監(jiān)督多項(xiàng)式及監(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)碼生成矩陣：例：若生成多項(xiàng)式g(x)＝x4+x3+x2+1，k=3，則其生成矩陣為：實(shí)際的編碼方法對(duì)應(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乘信息多項(xiàng)式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）編碼輸出的碼多項(xiàng)式

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)

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

8.3.4循環(huán)碼的編碼和譯碼（續(xù)）除法運(yùn)算的實(shí)現(xiàn)過(guò)程：先將移位寄存器清“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àng)式除法多項(xiàng)式除法可用帶反饋的移位寄存器實(shí)現(xiàn)。2023/3/1475信電學(xué)院信息工程系——李世銀（接上例）計(jì)算m(x)/g(x)，設(shè)m(x)=x13+x11+x10+x7+x4+x3+x+1,即k=14010110010011011000000100000010000101000110100011010001101000001100111110100111010111101111001011011001010余數(shù)000000111001110x6x5x4＋＋＋DDDDD＋Dx3100000001000001001000000101000101101001001101000001101010000011110011101110100001110101011110111111001010110111100101010除法運(yùn)算在移位進(jìn)行了r-1位后才開(kāi)始，運(yùn)算完成后，要將余式移出，還要做r-1次移位。速度較慢。實(shí)際電路2023/3/1476信電學(xué)院信息工程系——李世銀（b）實(shí)際應(yīng)用的循環(huán)碼編碼電路

特點(diǎn)：采用“預(yù)先乘xn-k方案”（信號(hào)直接到達(dá)最后一級(jí)），邊移位邊做除法運(yùn)算，當(dāng)k個(gè)信息碼輸入后，同時(shí)也完成了除法運(yùn)算。（1）當(dāng)信息位輸入時(shí)，開(kāi)關(guān)K1、K2合向下，k個(gè)信息位經(jīng)K2逐位輸出，同時(shí)直接送到最高位做除法運(yùn)算：（2）當(dāng)信息位全部輸入后，相應(yīng)除法運(yùn)算完成，開(kāi)關(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，上述運(yùn)算也可看作下列分別運(yùn)算的結(jié)果：商為：110⊕11⊕1100余數(shù)：1110⊕0111⊕11010100商為：100，余數(shù)為：0100譯碼過(guò)程2023/3/1478信電學(xué)院信息工程系——李世銀4.循環(huán)碼的譯碼過(guò)程

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

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

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

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

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

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

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

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

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

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

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

編碼過(guò)程diciei

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

bi-1

bibi+1，則當(dāng)輸入bi時(shí)，此編碼器輸出3比特cidiei，輸入和輸出的關(guān)系為：2023/3/1492信電學(xué)院信息工程系——李世銀起始狀態(tài)，各級(jí)移位寄存器清零，即M1M2M3為000。M1等于當(dāng)前輸入數(shù)據(jù)(bi)，而移位寄存器狀態(tài)M2M3存儲(chǔ)以前的數(shù)據(jù)(bi-1bi-2)，輸出碼字由下式確定(3,1,3)編碼器的工作過(guò)程(狀態(tài))變化如下表狀態(tài)圖原狀態(tài)(M3M2)a(00)b(01)c(10)d(11)輸入(M1)01010101監(jiān)督位輸出(diei)0011011011001001新?tīng)顟B(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)重疊起來(lái)，就可以得到如圖(b)所示的狀態(tài)圖。cbad110010011111100001000101(b)其中實(shí)線代表輸入”0”，虛線代表輸入“1”。樹(shù)圖當(dāng)前狀態(tài)下一狀態(tài)abcdabcd00011101110001110010101(a)輸出2023/3/1494信電學(xué)院信息工程系——李世銀100110001cdc100011abd101010cd001110a111000abb110001cdc100011ab011上半部下半部2.樹(shù)圖a111000abb000a111ba000111d101010cd010c101db001110a(00)111000輸入信息碼起點(diǎn)01寄存器狀態(tài)a=M3M2＝00b=M3M2＝01c=M3M2＝10d=M3M2＝11輸入1101時(shí)，編碼輸出為：111110010100輸出diei網(wǎng)格圖2023/3/1495信電學(xué)院信息工程系——李世銀由節(jié)點(diǎn)和支路組成：節(jié)點(diǎn)表示4種狀態(tài)；支路代表狀態(tài)間的轉(zhuǎn)移關(guān)系(實(shí)線代表輸入”0”，虛線代表輸入“1”)；支路上的數(shù)字代表當(dāng)前輸出的監(jiān)督位。3.網(wǎng)格圖

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

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

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

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

111001011b:000000111

111001100c:000111001

111110010d:000111110

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

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

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

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

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

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