差錯控制編碼

差錯控制編碼第一頁，共八十八頁，2022年，8月28日第九章差錯控制編碼這章講述的內容差錯控制編碼的概念漢明碼線性分組碼循環(huán)碼卷積碼第二頁，共八十八頁，2022年，8月28日9.1引言數(shù)字信號在傳輸中，遇噪聲和干擾，在收端判決時可能會判錯。減小誤碼率的措施有:

合理選擇調制方式{信號正交,合適的系統(tǒng)帶寬,信道因素}；增大發(fā)送信號功率；改善傳輸特性；合理選擇接收方式｛相干、非相干、最佳｝

差錯控制編碼優(yōu)良的同步系統(tǒng)(準確的同步)第三頁，共八十八頁，2022年，8月28日差錯控制編碼方式(有針對性)漢明碼、循環(huán)碼加性高斯白噪聲。誤碼的出現(xiàn)是分散的。卷積碼、循環(huán)碼脈沖噪聲；衰落。誤碼的出現(xiàn)是集中的。差錯控制方法反饋檢驗法：收端收到碼組后，反饋回發(fā)端，與原發(fā)碼組比較確認。傳輸效率低；雙向信道；設備技術簡單。檢錯重發(fā)法:收端收到碼組后，檢查出錯誤后，要求重法。只需很少的監(jiān)督元；檢錯編碼對信道適應能強；雙向信道；不能用于實時傳輸；信道噪聲大時，出現(xiàn)“重發(fā)循環(huán)”。例如：第四頁，共八十八頁，2022年，8月28日信源信道編碼及緩沖存儲器雙向信道信道譯碼指令發(fā)生器發(fā)送控制輸出緩沖存儲器NYN“重發(fā)”N自動請求重發(fā)系統(tǒng)ARQ(AutomaticRepeatreQuest)第五頁，共八十八頁，2022年，8月28日3.前向糾錯法：收端收到碼組后，能檢查出錯碼的位置，自動糾錯。單向信道；實時傳輸；監(jiān)督元位數(shù)多,影響傳輸效率；設備技術復雜。4.混合法：檢糾結合。噪聲大錯碼多按檢錯重發(fā)工作，噪聲小錯碼少按前向糾錯工作。后三種方法，需接收端自動檢查錯誤或自動糾正錯誤。怎樣的編碼(算法)，能實現(xiàn)這些功能？第六頁，共八十八頁，2022年，8月28日9.2基本原理1.例如：用“0”、“1”傳輸天氣預報信號。晴“0”陰“1”因噪聲傳輸出錯“1/0”陰“0/1”晴如用2位二進碼“00”、“11”傳輸以上天氣預報信號一般把“00”,“11”稱為許用碼組，而“01”、“10”稱為禁用碼組。把原信息位后附加的碼元稱為監(jiān)督位。晴“00”陰“11”因噪聲傳輸出錯“10/00”“10/11”“01/11”“01/00”可檢錯，但不知哪位錯“11/00”“00/11”不可檢錯誤(超出檢錯范圍)第七頁，共八十八頁，2022年，8月28日如用3位二進碼“000”、“111”傳輸以上天氣預報信號晴“000”(陰“111”)出錯“100/000”；“010/000”；“001/000”僅錯2位可檢錯，但不知哪位錯?！?11/000”不可檢錯誤(超出檢錯范圍)“101/000”；“011/000”；“110/000”僅錯1位的概率最大，自動糾1位錯碼。差錯控制編碼碼組(系統(tǒng)碼)構成信息位監(jiān)督位監(jiān)督元與信息元滿足線性方程稱為線性碼。監(jiān)督元只監(jiān)督本碼組的信息元稱為線性分組碼(漢明碼;循環(huán)碼)。監(jiān)督元除監(jiān)督本碼組的信息元還監(jiān)督前(N-1)個碼組的信息元，稱為線性非分組碼(卷積碼)。第八頁，共八十八頁，2022年，8月28日2.分組碼(1).線性分組碼定義k位信息元r位監(jiān)督元碼組長度n＝k+rr/n稱為多余度（冗余度）。越大糾、檢能力越強。k/n稱為編碼效率。越大糾、檢能力越弱。用（n，k）表示線性分組碼。第九頁，共八十八頁，2022年，8月28日(2).碼重W、碼距d、以及最小碼距d0碼重W：分組碼中“1”碼的位數(shù)。

(11010100),W=4。碼距d：分組碼中兩個碼組對應位取不同值的位數(shù)。即兩碼組模2加所得碼組的碼重。(11110110)(11010100)(00100010)d=6最小碼距d0:

某種編碼生成的碼組集合中，各個碼組間距離的最小值。第十頁，共八十八頁，2022年，8月28日線性分組碼具有封閉性(碼組集合中任意兩個碼組模2和所得碼組仍為該集合中的碼組)。所以碼組集合中，碼組的最小重量就等于最小碼距。全零碼除外。最小碼距d0，直接關系到檢錯、糾錯的能力。d0越大檢錯、糾錯的能力越強。(3).最小碼距d0與糾檢能力的關系：當許用碼組集合M一定，d0

一定，只檢個以下(含個)的錯碼,要求或或只糾個以下(含個)的錯碼,要求既檢個又糾個錯碼，要求第十一頁，共八十八頁，2022年，8月28日A、B碼組為許用碼集合中碼距為d0的(但不唯一)。禁用碼組都落在檢錯圓上。許用碼組都落在檢錯圓外。但碼距大于等于d0。只檢方式ABd0檢錯圓0123第十二頁，共八十八頁，2022年，8月28日A、B碼組為許用碼集合中碼距為d0的，(但不唯一)。禁用碼組都落在糾錯圓上。許用碼組都落在糾錯圓外。但碼距大于等于d0。糾錯園上的碼組都糾為圓心上的碼組。Ad0B012345糾錯圓只糾方式第十三頁，共八十八頁，2022年，8月28日AB1t檢、糾結合方式糾錯圓檢錯圓d0第十四頁，共八十八頁，2022年，8月28日如前例晴陰d0＝2只檢一位錯不能糾錯晴陰d0＝3只檢方式，能檢2位錯只糾方式，能糾1位錯不能檢糾結合晴陰多云雨d0＝1無檢糾能力第十五頁，共八十八頁，2022年，8月28日3.差錯控制編碼的效果如果誤碼率為P＝10－3，在碼長為n＝7的碼組中，恰好發(fā)生r個錯碼的概率為能糾1位錯，出錯的概率由10－3降為10－5

。能糾2位錯，出錯的概率由10－3降為10－9

。第十六頁，共八十八頁，2022年，8月28日9.3常用的簡單編碼an-1＋an-2＋＋a2＋a1＋a0＝01.偶監(jiān)督碼(an-1,an-2a2,a1,a0)奇數(shù)個1a0

＝1偶數(shù)個1a0

＝0信息位監(jiān)督位接收校驗:an-1＋an-2＋＋a2＋a1＋a0＝01碼組中1碼個數(shù)為偶數(shù)“無錯或無奇數(shù)個錯”“有奇數(shù)個錯”模2加檢錯能力：能檢奇數(shù)個錯碼。第十七頁，共八十八頁，2022年，8月28日an-1＋an-2＋＋a2＋a1＋a0＝12.奇監(jiān)督碼(an-1,an-2a2,a1,a0)奇數(shù)個1a0

＝0偶數(shù)個1a0

＝1信息位監(jiān)督位接收校驗:an-1＋an-2＋＋a2＋a1＋a0＝10碼組中1碼個數(shù)為奇數(shù)“無錯或無奇數(shù)個錯”“有奇數(shù)個錯”檢錯能力：能檢奇數(shù)個錯碼。第十八頁，共八十八頁，2022年，8月28日2維奇偶監(jiān)督碼(塊奇偶監(jiān)督碼）多個碼組構成方陣對方陣的行、列方向都進行奇或偶監(jiān)督碼的編碼。能檢奇數(shù)個錯；可能檢偶數(shù)個錯(但錯碼構成矩形形狀錯不可檢);適合檢突發(fā)錯誤。第十九頁，共八十八頁，2022年，8月28日9.4線性分組碼an-1an-2a0k位信息元r位監(jiān)督元線性方程組一.漢明碼糾一個分組中的1位錯碼t＝1，d0=3偶監(jiān)督碼是最簡單的線性分組（n,n-1）,一個監(jiān)督元。如偶監(jiān)督碼an-1＋an-2＋＋a1＋a0=S＝01無錯(極大的概率)有錯S稱為校正子(伴隨式)。一個校正子只有兩個狀態(tài)，可表示有錯與無錯兩個信息，而不能指出錯碼的位置。監(jiān)督關系式第二十頁，共八十八頁，2022年，8月28日如果增加一位監(jiān)督元，a1

、a0

，增加一個監(jiān)督關系式監(jiān)督關系為a1與an-1,an-2a2中部分碼元構成監(jiān)督關系a0與an-1,an-2a2中部分碼元構成監(jiān)督關系an-1＋an-2＋＋a1=S1an-1＋an-2＋＋a0=S2兩個校正子，能表示4種信息。設想r個監(jiān)督元，r個監(jiān)督式，r個校正子，(S1S2Sr)2r種狀態(tài)全零無錯2r

－1＝n表示n位碼組中1位錯碼的n個位置。線性無關第二十一頁，共八十八頁，2022年，8月28日所以，一般碼長為n，信息位數(shù)為k，監(jiān)督位數(shù)r＝n－k。如果希望用r個監(jiān)督位構造出r個監(jiān)督關系式來指示一位錯碼的n種可能位置，則要求(S1S2Sr)000100100011

1111an-1,an-2a2,a1,a0第二十二頁，共八十八頁，2022年，8月28日對于（7,4）漢明碼，r＝3，滿足23－1＝7。能糾7位中的1位錯碼。3個監(jiān)督位構造出3個監(jiān)督關系a2與a6a5a4構成偶監(jiān)督關系a1與a6a5a3構成偶監(jiān)督關系a0與a6a4a3構成偶監(jiān)督關系a6+

a5+

a4+a2=0或S1a6+

a5+

a3+a1=0或S2a6+

a4+

a3+a0=0或S3S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000僅無1位錯得出關系(線性無關)第二十三頁，共八十八頁，2022年，8月28日a6+

a5+

a4+a2=0a6+

a5+

a3+a1=0a6+

a4+

a3+a0=04比特信息元a6、a5、a4、a3確定后，根據(jù)監(jiān)督關系式求出3比特監(jiān)督元a2、a1、a0。a2=a6+

a5+

a4a1=a6+

a5+

a3a0=a6+

a4+

a3監(jiān)督關系式也可以表示成1a2=1a6+

1a5+

1a4+

0a31a1=

1a6+

1a5+

0a4+

1a31a0=

1a6+

0a5+

1a4+

1a3碼元系數(shù)為1的表示碼元之間存在監(jiān)督關系，0則沒有(7,4)漢明碼編碼用矩陣表示第二十四頁，共八十八頁，2022年，8月28日監(jiān)督關系式還可以用矩陣表示或a2a1a0=a6a5a4a3111110101011==P111011011011a6a5a4a3a2a1a0a6a5a4a3=a6a5a4a3QPT13×13×44×14×11×31×44×31×4監(jiān)督序列生成矩陣第二十五頁，共八十八頁，2022年，8月28日a2a1a0=a6a5a4a31111101010111000010000100001a6a5a4a3=I421×31×44×3a6a5a4a3a2a1a01000010000100001111110101011a6a5a4a3＝1×44×71×7G4×7第二十六頁，共八十八頁，2022年，8月28日a6a5a4a3a2a1a01000010000100001111110101011a6a5a4a3＝I4Q信息元矩陣G典型生成矩陣A漢明碼(系統(tǒng)碼)矩陣＝1×44×71×7∴

Aa6a5a4a31×4G4×7＝G4×7將信息元a6a5a4a3，共2k個不同的信息序列，分別代入方程組，得到a6a5a4a3a2a1a0共2k個許用碼組。見下表。第二十七頁，共八十八頁，2022年，8月28日(7,4)漢明碼，d0=3，許用碼組集合。為生成矩陣。A許用碼組A許用碼組信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111112341234第二十八頁，共八十八頁，2022年，8月28日結論1：

(7,4)漢明碼屬(n,k)線性分組碼之一。編碼方法為A許用碼組系統(tǒng)碼＝a6a5a4a3K位信息位×IkQk×rG典型生成陣典型生成矩陣G，左半部分為k階單位陣Ik，右半部分為監(jiān)督序列生成矩陣Q。k×r

G的各行線性無關。

G的各行也在許用碼組集合中。監(jiān)督關系Q不同時，構成的(n,k)線性分組碼不同。第二十九頁，共八十八頁，2022年，8月28日(7,4)漢明碼譯碼1a2=1a6+

1a5+

1a4+

0a31a1=

1a6+

1a5+

0a4+

1a31a0=

1a6+

0a5+

1a4+

1a31a6+1a5+1a4+0a3+1a2+0a1+0a0=01a6+

1a5+

0a4+

1a3+0a1+1a1+0a0=01a6+

0a5+

1a4+

1a3+0a2+0a1+1a0=0a6a5a4a3a2a1a01110100110101010110013×7=0007×13×1IrPH一致監(jiān)督矩陣AT0T全零校正子監(jiān)督關系式第三十頁，共八十八頁，2022年，8月28日a6a5a4a3a2a1a01110100110101010110013×7=0007×13×1IrPH0TATH＝×或0AHT＝×3×77×13×11×37×31×7一致監(jiān)督矩陣H。左邊部分為監(jiān)督序列生成矩陣P，右邊部分為r階單位陣Ir。r×nr×n

H各行線性無關。各行也在許用碼組集合中。

H給定后信息位和監(jiān)督位的關系就完全確定?！?”碼的位置表示相應碼元之間存在著監(jiān)督關系。第三十一頁，共八十八頁，2022年，8月28日結論2:一致監(jiān)督矩陣H。左邊部分為監(jiān)督序列生成矩陣P，右邊部分為r階單位陣Ir。r×kr×n

H各行線性無關。

H給定后信息位和監(jiān)督位的關系就完全確定?！?”碼的位置表示相應碼元之間存在著監(jiān)督關系。如果接收碼組B等于發(fā)送碼組A，全零校正子表示無錯。此種信道譯碼方式稱為校正子檢驗。0AHT＝1×rn×r1×n?BHT1×n?＝伴隨式檢驗第三十二頁，共八十八頁，2022年，8月28日校正子檢驗檢錯原理：如果接收碼組為B(用矩陣表示)，有B=A，無錯，則B×HT

=0，校正子S＝0檢驗無錯碼。B≠A，有錯，則B×HT≠0，校正子S≠0檢驗有錯碼。糾錯原理：如果B≠A，而B－A＝E，或B＝A+EE

＝en-1en-2…e1e01×n稱為錯誤圖樣行矩陣。ei＝0bi=ai

bi

≠ai無錯有錯∴E中1元素(1碼)的位置就是錯碼的位置。第三十三頁，共八十八頁，2022年，8月28日根據(jù)校正子檢驗BHT=(A+E)HT=AHT+EHT＝EHT＝S1×nn×r1×nn×rn×r1×n1×n1×nn×rn×r∴

校正子矩陣S1×r=1×nn×rEHT=HT或ST=HE=Hr×1r×nn×1如果糾n位碼組中的1位錯碼，校正子S有n種狀態(tài)(2r-1≥n)，錯誤圖樣E也有n種狀態(tài)。即Sn×r=n×nn×rEHT=HTn×r或ST=HEr×nr×nn×n=Hr×n1×r1×rr×1第三十四頁，共八十八頁，2022年，8月28日(7，4）漢明碼糾1位錯S7×3=7×77×3EHT=HT7×31000000010000000100000001000000010000000100000001111110101011100010001∴S7×3=111110101011100010001a6錯a5錯a4錯a3錯a2錯a1錯a0錯漢明碼的哪一位有錯，校正子S就等于H矩陣相應順序的列校正子S等于H矩陣某一列，將指示漢明碼相應順序的那位錯。第三十五頁，共八十八頁，2022年，8月28日或ST=HEr×nr×nn×n=Hr×nST=HE3×73×77×7=H3×71000000010000000100000001000000010000000100000001111010011010101011001a6錯a5錯a0錯…第三十六頁，共八十八頁，2022年，8月28日例：A=0110011B=01110111110100110101010110010111011=011011a3錯H0010011111110101011100010001=110B=0010011a5錯第三十七頁，共八十八頁，2022年，8月28日三.線性分組碼的一般原理(n,k)線性分組碼，可寫出r個線性無關的監(jiān)督關系式構成方程組。有r個校正子的2r－1個校正子碼：指示出t個錯碼的位置。只糾方式?？蓹z出e個錯碼。只檢方式。指示出t個錯碼的位置，同時檢出e個錯碼。檢、糾結合。由r個監(jiān)督關系得到監(jiān)督位生成矩陣Pr×k，Qk×r,

G＝H＝k×nIkQPIrr×n典型生成陣為一致監(jiān)督陣為(1).(2).Q=PT;第三十八頁，共八十八頁，2022年，8月28日(3).漢明界（確定線性分組碼n、k與d0的關系）當給定糾錯位數(shù)t時，不加證明的給出“線性分組碼最小碼距下界”n－k≧log2t∑i＝0Cnit＝(d0－1)/2或2

n－k≧t∑i＝0Cnit＝(d0－1)/2例1，t＝1，d0

＝3由上式可計算出2

n－k≧t∑i＝0Cni＝Cn0＋Cn1第三十九頁，共八十八頁，2022年，8月28日2

7－k≧1∑i＝0Cni確定n、k，欲得到確保t＝1，d0＝3的n與k各確定值，必首先選定n與k中之一。2

7－k≧8k＝4，r＝7－4＝3max=8n＝6，r＝6－3＝3mix如已選定n＝7如已選定k＝3＝C70＋C712

n－3≧1∑i＝0Cni=1+n＝Cn0＋Cn1第四十頁，共八十八頁，2022年，8月28日例2，t＝2，d0

＝5，2n－k≧t∑i＝0Cni＝Cn0＋Cn1＋Cn22

7－k≧292

7－k≧29k＝2，r＝7－2＝5max如已選定n＝72

n－5≧n＝11，r＝6mix如已選定k＝5t∑i＝0Cni＝C70＋C71＋C72＝1+7+21＝2n－5≧2∑i＝0Cni＝Cn0＋Cn1＋Cn2＝1＋(n2+n)/21＋(n2+n)/2第四十一頁，共八十八頁，2022年，8月28日9.6循環(huán)碼特點*

屬線性分組碼。具有線性分組碼的所有特性。*

循環(huán)性許用碼集合中，任意碼組(字)循環(huán)左移(或右移)一位之后，仍是集合中的碼，全零碼除外。序號信息位監(jiān)督位序號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000041001011100101115101110020101110611001013011100171110010例1:(7,3)循環(huán)碼，W=4，d0

＝41253764第四十二頁，共八十八頁，2022年，8月28日*一個長為n的循環(huán)碼，它必是按模(xn+1)運算的余式。碼多項式一個長為n的循環(huán)碼(an-1an-2…a1a0)用碼多項式T(x)表示T(x)＝

an-1

xn-1+an-2xn-2+

…+a1x1+a0(an-1an-2…a1a0)例2：1110010T(x)＝x6+

x5+

x4+x其中：碼元是多項式各項的系數(shù)；

x僅起占位符的作用第四十三頁，共八十八頁，2022年，8月28日按模運算整數(shù)按模運算：整數(shù)m按模n運算等于被n除所得余數(shù)；m/n=Q+p/nm≡p記為也稱按n模運算m與p同余例3：5≡1模2、模4，2≡0模2。碼多項式F(x)按模N(x)運算：F(x)/N(x)=Q(x)+R(x)/N(x)F(x)≡R(x)例4：x4+x+1≡x2+x+1

（模x3+1）

xx3+1x4+0+x2+0＋1x4+xx2+x+1余式(次數(shù)小于除式的次數(shù))第四十四頁，共八十八頁，2022年，8月28日T(x)＝an-1

xn-1+an-2xn-2+

…+a1x1+a0T(x)是長為n的許用碼組的碼多項式而xi

T(x)＝an-1

xn-1+i+an-2xn-2+i+

…+a1x1+i+a0xixiT(x)按模(xn+1)運算余式T’(x)是T(x)左移循環(huán)i位后的碼組，仍是許用碼組。所以*一個長為n的循環(huán)碼，它必是按模(xn+1)運算的余式。xiT(x)≡T’(x)an-1

xn-1+i+an-2xn-2+i+

…+a1x1+i+a0xixn+1an-1

xi-1+an-2xi-2+

…+an-ian-1

xn-1+i＋an-1

xi-1an-2xn-2+i+

…+a1x1+i+a0xi＋an-1

xi-1an-i-1

xn-1+an-i-2xn-2+

…+a1x1+an-i第四十五頁，共八十八頁，2022年，8月28日二.循環(huán)碼的生成多項式g(x)典型生成矩陣G為了產(chǎn)生許用碼組，要找到循環(huán)碼的生成多項式g(x)或G。分析1：g(x)的特征已知G可以由k個許用碼組求出。在（n，k）循環(huán)碼中，全零碼除外有2k－1個許用碼組。設g(x)是a0≠0，前k-1位全為零(an-k≠0)

的碼組對應的n-k次多項式，且唯一。（如果有兩個，根據(jù)封閉性，相加an-k

=0出現(xiàn)k連0，不是許用碼組。）an-1an-2…

an-k

an-k-1…a1a0krg(x)＝an-kxn-k＋

an-k-1xn-k-1＋

…＋a1x＋

a0第四十六頁，共八十八頁，2022年，8月28日g(x)＝an-kxn-k＋

an-k-1xn-k-1＋

…＋a1x＋

a0xg(x)＝?xk-1g(x)＝an-kxn-1＋

an-k-1xn-2＋

…＋a1x＋

a0＋

…補(k-1)位零00…0

an-k

an-k-1…a1a0k-1r+1而g(x)、xg(x)、…

xk-1k個碼多項式線性無關。將它們按行排好，作為生成矩陣G(x)左移循環(huán)1位對應的碼多項式第四十七頁，共八十八頁，2022年，8月28日xk-1g(x)xk-2g(x)?xg(x)g(x)G(x)＝如例1，(7，3)循環(huán)碼，

許用碼中唯一的一個前2位全零的碼組是0010111a6a5a4a3a2a1a0g(x)＝x4+x2+

x+1xg(x)＝x5+x3+x2+

xx2g(x)＝x6+x4+x3+x2G(x)＝x6+x4+x3+x2x5+x3+x2+

xx4+x2+

x+1g(x)xg(x)x2g(x)＝第四十八頁，共八十八頁，2022年，8月28日G(x)＝x6+x4+x3+x2x5+x3+x2+

xx4+x2+

x+1Gx＝101110001011100010111初等行變換①＋③

①

100101101011100010111典型生成矩陣G所以信息序列乘以G(x)，得循環(huán)碼多項式。所以信息序列乘以G，得循環(huán)碼組(系統(tǒng)碼)。第四十九頁，共八十八頁，2022年，8月28日所以信息序列乘以G(x)，得循環(huán)碼多項式T(x)

，即T(x)＝如(7,3)循環(huán)碼的信息元a6a5a4，a6a5a4G(x)＝a6a5a4g(x)xg(x)x2g(x)＝a6x2g(x)＋a5xg(x)＋a4g(x)＝（a6x2＋a5x＋a4）g(x)＝m(x)g(x)信息碼多項式所以所有循環(huán)碼多項式T(x)，都可以被g(x)整除?；蛉我庋h(huán)碼多項式T(x)，都是g(x)的倍式。

第五十頁，共八十八頁，2022年，8月28日分析2：尋找（n，k）循環(huán)碼的生成多項式假設T(x)＝h(x)g(x)T’(x)＝g(x)xkT’(x)n次多項式xkT’(x)xn+1=

Q(x)+T(x)xn+1=1xkT’(x)＝xn+1+T(x)xkg(x)＝xkT’(x)＝xn+1+T(x)xn+1＝[xk+h(x)]g(x)h(x)次數(shù)不大于(k-1)g(x)是(n-k)次T(x)次數(shù)不大于(n-1)多項式g(x)，應該是(xn+1)的一個(n-k)次因式。所以(n，k)循環(huán)碼的生成第五十一頁，共八十八頁，2022年，8月28日所以只要知道n、k值。從(xn+1)的分解因式中找出(n-k)次因式，即可作為（n，k）循環(huán)碼的g(x)。例5:g(x)應該是4次因式，即x7+1＝(x+1)(x3+x2+1)(x3+x+1)作為（7，3）循環(huán)碼的g(x),有g(x)＝(x+1)(x3+x2+1)＝x4+x2+x+1

g(x)＝(x+1)(x3+x+1)＝x4+x3+x2+1或第五十二頁，共八十八頁，2022年，8月28日三編、譯碼方法根據(jù)糾、檢要求，按漢明界確定n、k值。從(xn+1)的分解因式中選出(n-k)次因式，作為g(x)。根據(jù)所有循環(huán)碼多項式T(x)

，都可以被g(x)整除的原則編碼。如果信息碼多項式為m(x),xn-km(x)g(x)=

Q(x)+r(x)g(x)所編碼組為T(x)＝xn-km(x)+r(x)信息位在前監(jiān)督位在后第五十三頁，共八十八頁，2022年，8月28日譯碼：檢錯接收碼組是否能被g(x)整除。余式為零，無錯。余式為非零，有錯。糾錯方法2：校正子檢驗方法1：將余式用查表法求出錯誤圖樣接收碼組＋錯誤圖樣＝正確碼組第五十四頁，共八十八頁，2022年，8月28日9.6卷積碼一般描述（參量的定義）卷積碼的圖形描述（樹狀圖、網(wǎng)格圖、狀態(tài)圖）卷積碼的解析描述（生成矩陣、生成多項式、沖激響應、基本生成矩陣）卷積碼的譯碼（維特比譯碼）第五十五頁，共八十八頁，2022年，8月28日1.一般描述（參量的定義）卷積碼屬線性非分組碼。卷積碼表示為（n，k，N），通常n，k都很小。其中的參量定義為：

n：子碼長（子碼位數(shù)）。

k：子碼中信息段長（信息段位數(shù)）。

N：以子碼為單位的卷積碼約束度。卷積編碼器把k比特信息段編成n比特的子碼，所編n比特的子碼不僅與當前信息段有關，而且還與前(N－1)個信息段有關聯(lián)。約束長度為Nn比特。編碼效率為k/n。第五十六頁，共八十八頁，2022年，8月28日2.一般結構(n,k,N)卷積碼編碼器一般包括:Nk級的輸入移位寄存器;一組n個模2相加器;n級輸出移位寄存器。12...k12...k…………12...k＋＋＋＋12…n-1n………Nk輸入輸出mX(m)第五十七頁，共八十八頁，2022年，8月28日3.卷積編碼器的工作過程M3M2M1＋＋例1.

（3,1,3）卷積編碼器y1,jy2,jy3,jmj－1y2,j=mj－2+mjmj－2mjy3,j=mj－2＋mj－1+mjmjy1,jy2,jy3,jy1,j=mj（n，k，N）tM2M1起記憶作用的移存器第五十八頁，共八十八頁，2022年，8月28日9.6.1卷積碼的圖形描述1.樹狀圖卷積編碼器的工作過程可用圖形描述由樹杈、節(jié)點、子碼組成。如例1，編碼器的樹狀圖。寄存器初始狀態(tài)為00。對于第j個輸入信息段，相應有2(j-1)個節(jié)點、2(j-1＋k)個樹杈。當j＝N時，樹狀圖表示出節(jié)點的所有可能的狀態(tài)和所有可能的樹杈以及所有可能的子碼。當j>N,樹狀圖出現(xiàn)節(jié)點自上而下重復取j＝N時的這段結構。cd000111aba001110cda011100ab010101cdb000111ab001110cdc011100ab010101cdd000000baab111001110011100010101111001110000111j＝Nabcd第五十九頁，共八十八頁，2022年，8月28日樹杈(支路、路徑)表示編碼器的工作過程(路徑)。每個節(jié)點可引出2k個樹杈。對于例1，k＝1，每個節(jié)點可引出2個樹杈。上支杈表示輸入“0”時編碼器的輸出路徑，下支杈表示輸入“1”時編碼器的輸出路徑?！皹滂旧系拇a是輸出子碼”。節(jié)點表示(起記憶作用的)移存器的狀態(tài)。一般共有k(N-1)個這樣的寄存器，共有2k(N-1)種不同的狀態(tài)。如例1，起記憶作用的移存器是M1M2，有4種狀態(tài)(4個不同的節(jié)點)。a=00；b=01；c=10；d=11。M1M2：第六十頁，共八十八頁，2022年，8月28日cd000111aba001110cda011100ab010101cdb000111ab001110cdc011100ab010101cdd000000baab111001110011100010101111001110000111輸入1，移存器輸出的卷積碼為111。再輸入1，移存器輸出的卷積碼為110。例2.當初始狀態(tài)為M1M2＝00＝aM3M2M1110M3M2M1100…所以輸入1101…編碼路徑和輸出的卷積碼為111,110,010,100…第六十一頁，共八十八頁，2022年，8月28日2.網(wǎng)格圖樹狀圖的優(yōu)點是對編碼器工作過程描述很清晰。缺點是縱向尺寸大。網(wǎng)格圖：把碼樹中具有相同狀態(tài)的節(jié)點合并在一起；碼樹中的下支路用虛線表示，虛線上的碼為輸出子碼；碼樹中的上支路用實線表示，實線上的碼為輸出子碼；輸入為“0”走實線輸入為“1”走虛線共有2k(N-1)種不同的狀態(tài)（a=00；b=01；c=10；d=11）M1M2＝第六十二頁，共八十八頁，2022年，8月28日000000000000000000000000001010011101101101101101101111111110100abcd000101如例1:(3,1,3)編碼器的網(wǎng)格圖第六十三頁，共八十八頁，2022年，8月28日

11010101

111110010100001100100001輸入紅線是編碼路徑abcd000001011101100例3.

輸出

111110010100001100001100第六十四頁，共八十八頁，2022年，8月28日3.狀態(tài)圖當網(wǎng)格圖達到穩(wěn)定狀態(tài)后，取兩個節(jié)點間的一段網(wǎng)格圖得到狀態(tài)圖。（編碼器工作的狀態(tài)轉移圖）abcd010000101011110111100001第六十五頁，共八十八頁，2022年，8月28日結論：對于(n,k,N)卷積碼(1).對應于每k個輸入信息段，編碼后產(chǎn)生n個輸出比特(子碼）。(2).樹狀圖中每個節(jié)點引出2k條樹杈。當?shù)趈個信息信息段輸入時，相應有2(j-1)個節(jié)點(狀態(tài))、2(j-1＋k)個樹杈。當j較大時，樹狀圖縱向尺寸太大。當輸入序列確定后，必有一條編碼路徑對應。(3).網(wǎng)格圖和狀態(tài)圖都有2k(N-1)種可能的狀態(tài)。每個狀態(tài)引出

2k條支路，同時也有2k條支路從其它狀態(tài)或本狀態(tài)引入。網(wǎng)格圖周期重復時，周期內有2kN條路徑。第六十六頁，共八十八頁，2022年，8月28日9.6.2卷積碼的解析表示1.生成矩陣m1+0+0

=y1,1

m1+0+0

=y2,1

m1+0+0

=y3,1

0+m2+

0=y1,2

0+m2+

0=y2,2

m1+m2+

0=y3,2

0+0+m3=y1,3m1+0+m3=y2,3m1+m2+m3=y3,3

0+mj-2+mj-1+mj=y3,j

0+mj-2+0+mj=y2,j

0+0+0+mj=y1,j…100100100010010110001101111…0…001…0…101…0…111……=m1m2m3…mj…y1,1y2,1y3,1y1,2y2,2y3,2y1,3y2,3y3,3…y1,jy2,jy3,j……GTMTYT＝×第六十七頁，共八十八頁，2022年，8月28日

G＝G∞Y＝M?Gy1,1y2,1y3,1y1,2y2,2y3,2y1,3y2,3y3,3…y1,jy2,jy3,j…m1m2m3m4m5…mj…編碼輸出其中M=Y=100100100010010110001101111…0…001…0…101…0…111……0T＝G＝生成矩陣111001011000111001011000000111001011111001…

011111001

111…

……00第六十八頁，共八十八頁，2022年，8月28日G＝G∞生成矩陣：是半無限矩陣，是基本生成矩陣逐行按子碼長延遲。其中包含沖激響應(基本生成矩陣)；子碼生成矩陣A。G＝G∞＝111001011000111001011000000111001011111001…111

011

001

111

……00第六十九頁，共八十八頁，2022年，8月28日2.沖激響應（編碼器對輸入單個“1”比特的響應）輸入…001000…輸出…000000111001011000…沖激響應輸入序列m＝101它對應的輸出序列可以是時移“脈沖”的線性疊加卷積和。M3M2M1＋＋y1,jy2,jy3,jmj所以稱為卷積碼。第七十頁，共八十八頁，2022年，8月28日輸入m輸出1101111001011111001011000000000111001011

111110010100001011編碼輸出＝卷積和例4：第七十一頁，共八十八頁，2022年，8月28日3.卷積編碼器的生成多項式M3M2M1＋＋y1,jy2,jy3,jmj編碼器的生成多項式表示移存器各級與模2加的連接關系。生成多項式與輸入序列多項式相乘產(chǎn)生輸出序列多項式。將編碼器的1個輸入對應的3個輸出分解成3個支路。得到3個子生成多項式。移存器及它的移位用延遲算子(啞變量)及相應的冪次表示，移存器輸出與模2加有連接延遲算子系數(shù)為1，反之系數(shù)為0。第七十二頁，共八十八頁，2022年，8月28日M3M3M2M1y2,jM3M2M1y3,jy1,j生成多項式＋＋＋M3M2M1＋＋y1,jy2,jy3,jmjg1(x)=1g2(x)=1+x2g3(x)=1+x+x211x2x2x1g1=(100)g2=(101)g3=(111)第七十三頁，共八十八頁，2022年，8月28日如例3，輸入序列多項式為M(x)=1+x+x3+x5+x7…(11010101

輸入序列11010101…

Y1=M(x)g1(x)=

1+x+x3+x5+x7

…(11010101…)Y2=M(x)g2(x)=(1+x+x3+x5+x7…)(1+x2)=1+x+x2+x9

…

(11100000…)Y3=M(x)g3(x)=(1+x+x3+x5+x7…)(1+x+x2)

=1+x4+x6+x8+x9

…(10001010…)

輸出序列多項式(Y1子碼第1位,Y2子碼第2位,Y3子碼第3位,)輸出序列111110

010100001100001100第七十四頁，共八十八頁，2022年，8月28日4.生成多項式與基本生成矩陣的關系G基＝

g1213g11gg21g22g23g31g32g33g1=(100)11gg21g31g22

g12g3213gg23g33g2=(101)g3=(111)其中第七十五頁，共八十八頁，2022年，8月28日9.6.3卷積碼譯碼卷積碼譯碼方法大數(shù)邏輯譯碼（門限譯碼）概率譯碼維特比譯碼（性能最好）序列譯碼最大似然譯碼第七十六頁，共八十八頁，2022年，8月28日1.最大似然譯碼卷積編碼信道卷積譯碼信息序列m發(fā)送序列X譯碼序列R’接收序列R譯碼器對接收序列R進行觀察，P[R/X(mi)]>P[R/X(mj)]譯為Ri’i≠j,j=1,2,…pP[R/X(m1)]、P[R/X(m2)]、…P[R/X(mp)]如果信息序列m等概，譯碼器通過比較P[R/X(mi)]稱為似然函數(shù)。與fsi(y)是等價的。則稱為最大似然譯碼。第七十七頁，共八十八頁，2022年，8月28日2.維特比(VB)譯碼最大似然譯碼的方法是：把已接收序列R與所有可能的發(fā)送序列X(編碼路徑)做比較，選擇其中與它具有最小碼距的一個發(fā)送序列作為譯碼序列R’。這個序列具有最大似然值。VB算法的特點是：不是在網(wǎng)格圖上一次比較所有可能的發(fā)送路徑與接收序列R的碼距(計算所有的似然函數(shù))，而是接收一段，計算比較一段。選擇出幸存路徑，累計得到最大似然路徑。計算路徑與R的最小碼距等效于計算似然函數(shù)。選擇最小碼距等效于選擇最大似然值第七十八頁，共八十八頁，2022年，8月28日例5.（2,1,3）卷積編碼器M3M2M1＋＋y1,jy2,jmj0000000000000000100111101010101010110100abcd0010

01234567800011011M1M2第七十九頁，共八十八頁，2022年，8月28日維特比譯碼過程設：信息序列為(11011000)編碼序列為(1101010001011100)接收序列為(0101011001011100)因該卷積碼約束長度為Nn＝3×2＝6，先選擇接收序列前6位010101同到達第3時刻的可能的8個發(fā)送碼序列(8條路徑)比較。第八十頁，共八十八頁，2022年，8月28日0000000000000000100111