差錯(cuò)控制編碼

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

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

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

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

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

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

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

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

＝1偶數(shù)個(gè)1a0

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

＝0偶數(shù)個(gè)1a0

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

、a0

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

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

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

a5+

a4+a2=0或S1a6+

a5+

a3+a1=0或S2a6+

a4+

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

a5+

a4+a2=0a6+

a5+

a3+a1=0a6+

a4+

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

a5+

a4a1=a6+

a5+

a3a0=a6+

a4+

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

1a5+

1a4+

0a31a1=

1a6+

1a5+

0a4+

1a31a0=

1a6+

0a5+

1a4+

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

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

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

G的各行線性無關(guān)。

G的各行也在許用碼組集合中。監(jiān)督關(guān)系Q不同時(shí)，構(gòu)成的(n,k)線性分組碼不同。第二十九頁(yè)，共八十八頁(yè)，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)督關(guān)系式第三十頁(yè)，共八十八頁(yè)，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各行線性無關(guān)。各行也在許用碼組集合中。

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

H各行線性無關(guān)。

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

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

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

bi

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

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

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

＝3由上式可計(jì)算出2

n－k≧t∑i＝0Cni＝Cn0＋Cn1第三十九頁(yè)，共八十八頁(yè)，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第四十頁(yè)，共八十八頁(yè)，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第四十一頁(yè)，共八十八頁(yè)，2022年，8月28日9.6循環(huán)碼特點(diǎn)*

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

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

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

an-1

xn-1+an-2xn-2+

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

x5+

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

x僅起占位符的作用第四十三頁(yè)，共八十八頁(yè)，2022年，8月28日按模運(yùn)算整數(shù)按模運(yùn)算：整數(shù)m按模n運(yùn)算等于被n除所得余數(shù)；m/n=Q+p/nm≡p記為也稱按n模運(yùn)算m與p同余例3：5≡1模2、模4，2≡0模2。碼多項(xiàng)式F(x)按模N(x)運(yùn)算：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ù))第四十四頁(yè)，共八十八頁(yè)，2022年，8月28日T(x)＝an-1

xn-1+an-2xn-2+

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

T(x)＝an-1

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

…+a1x1+i+a0xixiT(x)按模(xn+1)運(yùn)算余式T’(x)是T(x)左移循環(huán)i位后的碼組，仍是許用碼組。所以*一個(gè)長(zhǎng)為n的循環(huán)碼，它必是按模(xn+1)運(yùn)算的余式。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第四十五頁(yè)，共八十八頁(yè)，2022年，8月28日二.循環(huán)碼的生成多項(xiàng)式g(x)典型生成矩陣G為了產(chǎn)生許用碼組，要找到循環(huán)碼的生成多項(xiàng)式g(x)或G。分析1：g(x)的特征已知G可以由k個(gè)許用碼組求出。在（n，k）循環(huán)碼中，全零碼除外有2k－1個(gè)許用碼組。設(shè)g(x)是a0≠0，前k-1位全為零(an-k≠0)

的碼組對(duì)應(yīng)的n-k次多項(xiàng)式，且唯一。（如果有兩個(gè)，根據(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第四十六頁(yè)，共八十八頁(yè)，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＋

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

an-k

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

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

許用碼中唯一的一個(gè)前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)＝第四十八頁(yè)，共八十八頁(yè)，2022年，8月28日G(x)＝x6+x4+x3+x2x5+x3+x2+

xx4+x2+

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

①

100101101011100010111典型生成矩陣G所以信息序列乘以G(x)，得循環(huán)碼多項(xiàng)式。所以信息序列乘以G，得循環(huán)碼組(系統(tǒng)碼)。第四十九頁(yè)，共八十八頁(yè)，2022年，8月28日所以信息序列乘以G(x)，得循環(huán)碼多項(xiàng)式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)信息碼多項(xiàng)式所以所有循環(huán)碼多項(xiàng)式T(x)，都可以被g(x)整除?；蛉我庋h(huán)碼多項(xiàng)式T(x)，都是g(x)的倍式。

第五十頁(yè)，共八十八頁(yè)，2022年，8月28日分析2：尋找（n，k）循環(huán)碼的生成多項(xiàng)式假設(shè)T(x)＝h(x)g(x)T’(x)＝g(x)xkT’(x)n次多項(xiàng)式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)多項(xiàng)式g(x)，應(yīng)該是(xn+1)的一個(gè)(n-k)次因式。所以(n，k)循環(huán)碼的生成第五十一頁(yè)，共八十八頁(yè)，2022年，8月28日所以只要知道n、k值。從(xn+1)的分解因式中找出(n-k)次因式，即可作為（n，k）循環(huán)碼的g(x)。例5:g(x)應(yīng)該是4次因式，即x7+1＝(x+1)(x3+x2+1)(x3+x+1)作為（7，3）循環(huán)碼的g(x),有g(shù)(x)＝(x+1)(x3+x2+1)＝x4+x2+x+1

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

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

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

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

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

N：以子碼為單位的卷積碼約束度。卷積編碼器把k比特信息段編成n比特的子碼，所編n比特的子碼不僅與當(dāng)前信息段有關(guān)，而且還與前(N－1)個(gè)信息段有關(guān)聯(lián)。約束長(zhǎng)度為Nn比特。編碼效率為k/n。第五十六頁(yè)，共八十八頁(yè)，2022年，8月28日2.一般結(jié)構(gòu)(n,k,N)卷積碼編碼器一般包括:Nk級(jí)的輸入移位寄存器;一組n個(gè)模2相加器;n級(jí)輸出移位寄存器。12...k12...k…………12...k＋＋＋＋12…n-1n………Nk輸入輸出mX(m)第五十七頁(yè)，共八十八頁(yè)，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起記憶作用的移存器第五十八頁(yè)，共八十八頁(yè)，2022年，8月28日9.6.1卷積碼的圖形描述1.樹狀圖卷積編碼器的工作過程可用圖形描述由樹杈、節(jié)點(diǎn)、子碼組成。如例1，編碼器的樹狀圖。寄存器初始狀態(tài)為00。對(duì)于第j個(gè)輸入信息段，相應(yīng)有2(j-1)個(gè)節(jié)點(diǎn)、2(j-1＋k)個(gè)樹杈。當(dāng)j＝N時(shí)，樹狀圖表示出節(jié)點(diǎn)的所有可能的狀態(tài)和所有可能的樹杈以及所有可能的子碼。當(dāng)j>N,樹狀圖出現(xiàn)節(jié)點(diǎn)自上而下重復(fù)取j＝N時(shí)的這段結(jié)構(gòu)。cd000111aba001110cda011100ab010101cdb000111ab001110cdc011100ab010101cdd000000baab111001110011100010101111001110000111j＝Nabcd第五十九頁(yè)，共八十八頁(yè)，2022年，8月28日樹杈(支路、路徑)表示編碼器的工作過程(路徑)。每個(gè)節(jié)點(diǎn)可引出2k個(gè)樹杈。對(duì)于例1，k＝1，每個(gè)節(jié)點(diǎn)可引出2個(gè)樹杈。上支杈表示輸入“0”時(shí)編碼器的輸出路徑，下支杈表示輸入“1”時(shí)編碼器的輸出路徑?！皹滂旧系拇a是輸出子碼”。節(jié)點(diǎn)表示(起記憶作用的)移存器的狀態(tài)。一般共有k(N-1)個(gè)這樣的寄存器，共有2k(N-1)種不同的狀態(tài)。如例1，起記憶作用的移存器是M1M2，有4種狀態(tài)(4個(gè)不同的節(jié)點(diǎn))。a=00；b=01；c=10；d=11。M1M2：第六十頁(yè)，共八十八頁(yè)，2022年，8月28日cd000111aba001110cda011100ab010101cdb000111ab001110cdc011100ab010101cdd000000baab111001110011100010101111001110000111輸入1，移存器輸出的卷積碼為111。再輸入1，移存器輸出的卷積碼為110。例2.當(dāng)初始狀態(tài)為M1M2＝00＝aM3M2M1110M3M2M1100…所以輸入1101…編碼路徑和輸出的卷積碼為111,110,010,100…第六十一頁(yè)，共八十八頁(yè)，2022年，8月28日2.網(wǎng)格圖樹狀圖的優(yōu)點(diǎn)是對(duì)編碼器工作過程描述很清晰。缺點(diǎn)是縱向尺寸大。網(wǎng)格圖：把碼樹中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起；碼樹中的下支路用虛線表示，虛線上的碼為輸出子碼；碼樹中的上支路用實(shí)線表示，實(shí)線上的碼為輸出子碼；輸入為“0”走實(shí)線輸入為“1”走虛線共有2k(N-1)種不同的狀態(tài)（a=00；b=01；c=10；d=11）M1M2＝第六十二頁(yè)，共八十八頁(yè)，2022年，8月28日000000000000000000000000001010011101101101101101101111111110100abcd000101如例1:(3,1,3)編碼器的網(wǎng)格圖第六十三頁(yè)，共八十八頁(yè)，2022年，8月28日

11010101

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

輸出

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

2k條支路，同時(shí)也有2k條支路從其它狀態(tài)或本狀態(tài)引入。網(wǎng)格圖周期重復(fù)時(shí)，周期內(nèi)有2kN條路徑。第六十六頁(yè)，共八十八頁(yè)，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＝×第六十七頁(yè)，共八十八頁(yè)，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第六十八頁(yè)，共八十八頁(yè)，2022年，8月28日G＝G∞生成矩陣：是半無限矩陣，是基本生成矩陣逐行按子碼長(zhǎng)延遲。其中包含沖激響應(yīng)(基本生成矩陣)；子碼生成矩陣A。G＝G∞＝111001011000111001011000000111001011111001…111

011

001

111

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

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

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

010100001100001100第七十四頁(yè)，共八十八頁(yè)，2022年，8月28日4.生成多項(xiàng)式與基本生成矩陣的關(guān)系G基＝

g1213g11gg21g22g23g31g32g33g1=(100)11gg21g31g22

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

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