差錯(cuò)控制編碼

差錯(cuò)控制編碼第一頁，共五十六頁，2022年，8月28日本章要點(diǎn)第11章差錯(cuò)控制編碼差錯(cuò)控制編碼，又稱為信道編碼，是提高數(shù)字傳輸可靠性的一種技術(shù)，在數(shù)字信號傳輸中，由于噪聲的存在及信道特性不理想，都可使信號波形變壞，從而在接收端就不可避免的產(chǎn)生錯(cuò)誤判決。差錯(cuò)控制編碼技術(shù)充分利用信道多余度，來減小信息傳輸差錯(cuò)概率。本章主要介紹差錯(cuò)控制編碼的基本概念；常用的幾種檢錯(cuò)編碼；線性分組碼；循環(huán)碼；卷積碼等。教學(xué)重點(diǎn)：糾錯(cuò)編碼的基本概念、定理和方法，常用的幾種檢錯(cuò)編碼。教學(xué)難點(diǎn)：線性分組碼；循環(huán)碼；卷積碼。第二頁，共五十六頁，2022年，8月28日差錯(cuò)控制編碼目的：降低誤碼率信道分類：隨機(jī)信道，突發(fā)信道，混合信道差錯(cuò)控制技術(shù)的種類：檢錯(cuò)重發(fā)，前向糾錯(cuò)，反饋校驗(yàn)，檢錯(cuò)刪除差錯(cuò)控制編碼的基本方法：發(fā)送端：信息序列附加監(jiān)督碼元；接收端：檢驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系.發(fā)收檢錯(cuò)碼應(yīng)答信號發(fā)收糾錯(cuò)碼發(fā)收糾檢錯(cuò)應(yīng)答信號檢錯(cuò)重發(fā)前向糾錯(cuò)混合糾錯(cuò)常用差錯(cuò)控制方法11.1概述第三頁，共五十六頁，2022年，8月28日接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組921436575981011131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK9ARQ系統(tǒng):停發(fā)等候重發(fā)返回重發(fā)選擇重發(fā)接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯(cuò)碼組有錯(cuò)碼組接收數(shù)據(jù)有錯(cuò)碼組有錯(cuò)碼組91011101112214365798576ACK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)57695214367981011101112重發(fā)碼組重發(fā)碼組第四頁，共五十六頁，2022年，8月28日例：3位二進(jìn)制數(shù)構(gòu)成的碼組表示天氣000001010011100101110111全用晴云陰雨雪霜霧雹用4種000晴011云101陰110雨用2種晴000雨111不能檢錯(cuò)、不能糾錯(cuò)能檢1位錯(cuò)、不能糾錯(cuò)能檢測2個(gè)錯(cuò)，可糾1位錯(cuò)。11.2糾錯(cuò)編碼的基本原理分組碼每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。如不用檢錯(cuò)，傳輸4種信息，用兩位碼就夠了，這兩位碼稱為信息位，多增加的稱為監(jiān)督位。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。第五頁，共五十六頁，2022年，8月28日分組碼的一般結(jié)構(gòu)分組碼的符號：(n,k)n－碼組的總位數(shù)，又稱為碼組的長度（碼長），k－碼組中信息碼元的數(shù)目，n–k＝r－碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)信息位監(jiān)督位晴000云011陰101雨110第六頁，共五十六頁，2022年，8月28日分組碼的碼重：碼組中“1”的個(gè)數(shù)；

碼距：兩個(gè)碼組中對應(yīng)位上數(shù)字不同的位數(shù)；或稱漢明距離最小碼距：某種編碼中各個(gè)碼組間距離的最小值?！?00”＝晴，“011”＝云，“101”＝陰，“110”＝雨(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1第七頁，共五十六頁，2022年，8月28日碼距和檢糾錯(cuò)能力的關(guān)系編碼的最小碼距d0

的大小直接關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力，為檢測e個(gè)錯(cuò)碼，要求最小碼距d0

e+10123BA漢明距離ed01.若碼組A中發(fā)生兩位錯(cuò)碼，則其位置不會超出以O(shè)點(diǎn)為圓心，以e為半徑的圓。因此，只要最小碼距不小于e+12.為糾正

t個(gè)錯(cuò)碼，要求最小碼距d0

2t+1設(shè)A和B的距離為5。碼組A或B若發(fā)生不多于兩位錯(cuò)碼，則其位置均不會超出半徑為2以原位置為圓心的圓。這兩個(gè)圓是不重疊的。第八頁，共五十六頁，2022年，8月28日BtA漢明距離012345td03.為糾正t個(gè)錯(cuò)碼，同時(shí)檢測e個(gè)錯(cuò)碼，要求最小碼距檢錯(cuò)

e=d0–1=5–1=4，糾

2個(gè)錯(cuò)碼，不能同時(shí)滿足ABe1tt漢明距離這種糾錯(cuò)和檢錯(cuò)結(jié)合的工作方式簡稱糾檢結(jié)合。第九頁，共五十六頁，2022年，8月28日系統(tǒng)帶寬和信噪比的矛盾：舉例：未編碼，誤碼率A點(diǎn)，編碼后，誤碼率B點(diǎn)。保持誤碼率10-5，C點(diǎn)，未編碼時(shí)，D點(diǎn)，編碼后。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)傳輸速率和Eb/n0

關(guān)系若提高傳輸速率，誤碼率增大。信噪比下降C點(diǎn)E點(diǎn)D點(diǎn)付出的代價(jià)仍是帶寬增大。第十頁，共五十六頁，2022年，8月28日11.4.1奇偶監(jiān)督碼奇偶監(jiān)督碼：奇數(shù)監(jiān)督碼和偶數(shù)監(jiān)督碼。偶監(jiān)督碼中，1位監(jiān)督位，使碼組中“1”為偶數(shù)。11.4簡單的實(shí)用編碼這種編碼能夠檢測奇數(shù)個(gè)錯(cuò)碼。在接收端，按照上式求“模2和

”。結(jié)果為“1”就說明有錯(cuò)碼，結(jié)果為“0”認(rèn)為無錯(cuò)碼。第十一頁，共五十六頁，2022年，8月28日a01

a02

a0m

為m行奇偶監(jiān)督碼中的m個(gè)監(jiān)督位。cn-1

cn-2

c1

c0為按列進(jìn)行第二次編碼所增加的監(jiān)督位，它們構(gòu)成了一監(jiān)督位行。可能檢測偶數(shù)個(gè)錯(cuò)碼構(gòu)成矩形四角的錯(cuò)碼無法檢測

還可以用來糾正一些錯(cuò)碼11.4.2二維奇偶監(jiān)督碼（方陣碼）第十二頁，共五十六頁，2022年，8月28日11.4.3恒比碼“1”的數(shù)目與“0”的數(shù)目之比保持恒定。這種碼在檢測時(shí)，只要計(jì)算接收碼組中“1”的數(shù)目是否對，就知道有無錯(cuò)碼。11.4.4正反碼能夠糾正錯(cuò)碼的編碼。其中的監(jiān)督位數(shù)目與信息位數(shù)目相同編碼規(guī)則：信息位有奇數(shù)個(gè)“1”，監(jiān)督位是信息位的重復(fù)；信息位有偶數(shù)個(gè)“1”，監(jiān)督位是信息位的反碼。正反碼的解碼在接收碼組中

信息位

監(jiān)督位=

合成碼組0000100001=00000校驗(yàn)碼組第十三頁，共五十六頁，2022年，8月28日接收碼組信息位有奇數(shù)個(gè)“1”，合成碼組就是校驗(yàn)碼組；接收碼組信息位有偶數(shù)個(gè)“1”，取合成碼組的反碼作為校驗(yàn)碼組。校驗(yàn)碼組和錯(cuò)碼的關(guān)系校驗(yàn)碼組的組成錯(cuò)碼情況1全為“0”無錯(cuò)碼2有4個(gè)“1”和1個(gè)“0”信息碼中有1位錯(cuò)碼，其位置對應(yīng)校驗(yàn)碼組中“0”的位置3有4個(gè)“0”和1個(gè)“1”監(jiān)督碼中有1位錯(cuò)碼，其位置對應(yīng)校驗(yàn)碼組中“1”的位置4其他組成錯(cuò)碼多于1個(gè)若發(fā)送碼組1100111001，接收碼組1000111001則合成碼組應(yīng)為1000111001=01000。校驗(yàn)碼組就是10111。若發(fā)送碼組1100111001，接收碼組1100101001則合成碼組應(yīng)為1100101001=10000。校驗(yàn)碼組就是10000。第十四頁，共五十六頁，2022年，8月28日11.5線性分組碼基本概念代數(shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼。線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。線性分組碼：按照一組線性方程構(gòu)成的分組碼。本節(jié)將以漢明碼為例引入線性分組碼一般原理。構(gòu)造原理在偶數(shù)監(jiān)督碼中，一位監(jiān)督位a0，和信息位構(gòu)成代數(shù)式：第十五頁，共五十六頁，2022年，8月28日在接收端解碼時(shí)，實(shí)際上就是在計(jì)算監(jiān)督關(guān)系式校正子S=0，認(rèn)為無錯(cuò)碼；

S=1，就認(rèn)為有錯(cuò)碼。若監(jiān)督位增加一位，兩個(gè)校正子的可能值有4中組合：00，01，10，11，故能表示4種不同信息。

1種表示無錯(cuò)其余3種能指示1位錯(cuò)碼(2r–1)個(gè)可能位置。碼長為n，信息位數(shù)為k，則監(jiān)督位r＝n－k。指示1位錯(cuò)碼的n種可能位置，要求第十六頁，共五十六頁，2022年，8月28日設(shè)分組碼(n,k)中k=4，為了糾正1位錯(cuò)碼，要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7S1S2

S3錯(cuò)碼位置S1S2

S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)碼僅當(dāng)一位錯(cuò)碼在a2

、a4、a5或a6時(shí)，校正子S1為1,偶數(shù)監(jiān)督關(guān)系a1、a3、a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：a0、a3、a4和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：第十七頁，共五十六頁，2022年，8月28日監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來確定，即監(jiān)督位應(yīng)使S1、S2和S3的值為0:上式經(jīng)過移項(xiàng)運(yùn)算，解出監(jiān)督位第十八頁，共五十六頁，2022年，8月28日信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111給定信息位后，可以直接按上式算出監(jiān)督位第十九頁，共五十六頁，2022年，8月28日接收端收到每個(gè)碼組后，先計(jì)算出S1、S2和S3，再查表判斷錯(cuò)碼情況。例如：若接收碼組為1101100按監(jiān)督式計(jì)算可得：S1=1，S2=1，S3=0。查表可知在a5位有1錯(cuò)碼。碼效率：k/n=(n-r)/n=1–r/n，當(dāng)n很大和r很小時(shí)，碼率接近1。漢明碼是一種高效碼。按照上述方法構(gòu)造的碼稱為漢明碼。表中所列的(7,4)漢明碼的最小碼距d0=3。

這種碼能夠糾正1個(gè)錯(cuò)碼或檢測2個(gè)錯(cuò)碼。S1S2

S3錯(cuò)碼位置S1S2

S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無錯(cuò)碼信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第二十頁，共五十六頁，2022年，8月28日線性分組碼的一般原理線性分組碼的構(gòu)造H矩陣上面(7,4)漢明碼的例子有改寫為上式中已經(jīng)將“”簡寫成“+”。第二十一頁，共五十六頁，2022年，8月28日矩陣形式簡記為HAT

=0T

或A

HT=

0H稱為監(jiān)督矩陣。只要監(jiān)督矩陣H給定，編碼時(shí)監(jiān)督位和信息位的關(guān)系就完全確定了。H矩陣的性質(zhì)：

1)H的行數(shù)就是監(jiān)督關(guān)系式數(shù)，等于監(jiān)督位數(shù)r。每行中“1”的位置表示監(jiān)督關(guān)系。H矩陣可以分成兩部分P為r

k階矩陣，Ir為r

r階單位方陣。我們將具有[PIr]形式的H矩陣稱為典型陣。第二十二頁，共五十六頁，2022年，8月28日2)H矩陣各行線性無關(guān)，才有r個(gè)獨(dú)立監(jiān)督位。若矩陣能寫成形式[PIr]，各行一定線性無關(guān)G矩陣：漢明碼例子中的監(jiān)督位公式為可以改寫成或Q=PT信息位的行矩陣乘矩陣Q就產(chǎn)生出監(jiān)督位第二十三頁，共五十六頁，2022年，8月28日生成矩陣G由它可以產(chǎn)生整個(gè)碼組具有[IkQ]形式的生成矩陣稱為典型生成矩陣。

由典型生成矩陣得出的碼組A中，信息位的位置不變，監(jiān)督位附加于其后。這種形式的碼稱系統(tǒng)碼。G矩陣的性質(zhì)：1)G矩陣的各行是線性無關(guān)的。任一碼組A都是G的各行的線性組合。

2)實(shí)際上，G的各行本身就是一個(gè)碼組。如果已有k個(gè)線性無關(guān)的碼組，則可以用其作為生成矩陣G，并由它生成其余碼組。G的k行線性無關(guān)2k

種不同的碼組A恰是有k位信息位的全部碼組。第二十四頁，共五十六頁，2022年，8月28日錯(cuò)碼矩陣和錯(cuò)誤圖樣A為一個(gè)n列的行矩陣，發(fā)送的碼組就是A。設(shè)接收碼組為n列的行矩陣B，即發(fā)送碼組和接收碼組之差為B–A=E(模2)E—傳輸中產(chǎn)生的錯(cuò)碼行矩陣錯(cuò)碼矩陣有時(shí)也稱為錯(cuò)誤圖樣校正子S當(dāng)接收碼組有錯(cuò)時(shí)，E

0，將B代入(AHT=0)，不一定成立。即BHT=S，將B=A+E代入S=(A+E)HT=A

HT+E

HT=EHT

S稱為校正子。它能用來指示錯(cuò)碼的位置。S和E之間有確定的線性變換關(guān)系。第二十五頁，共五十六頁，2022年，8月28日線性分組碼的性質(zhì)封閉性：是指一種線性碼中的任意兩個(gè)碼組之和仍為這種碼中的一個(gè)碼組。若A1和A2是一種線性碼中的兩個(gè)許用碼組，則(A1+A2)仍為其中的一個(gè)碼組。

A1

和A2之間的距離=(A1+A2)的重量。碼的最小距離就是碼的最小重量（除全“0”碼組外）第二十六頁，共五十六頁，2022年，8月28日(7,3)循環(huán)碼的全部碼組碼組編號信息位監(jiān)督位碼組編號信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010循環(huán)碼原理循環(huán)性：任一碼組循環(huán)一位以后，仍為該碼中的碼組。11.6循環(huán)碼第二十七頁，共五十六頁，2022年，8月28日碼多項(xiàng)式碼組的多項(xiàng)式表示法一個(gè)長度為n的碼組表示成（7，3）循環(huán)碼第7個(gè)碼組1100101可以表示為x僅是碼元位置的標(biāo)記碼多項(xiàng)式的按模運(yùn)算若一個(gè)整數(shù)m可以表示為則在模n運(yùn)算下，有m

p(模n)在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。Q

－整數(shù)第二十八頁，共五十六頁，2022年，8月28日碼多項(xiàng)式運(yùn)算多項(xiàng)式F(x)被n次多項(xiàng)式N(x)除=商式Q(x)+余式R(x)按模2運(yùn)算，即系數(shù)只取0和1。

xx3+1x4+x2+1

x4

+x

x2+x+1應(yīng)當(dāng)注意，由于在模2運(yùn)算中，用加法代替了減法，故余項(xiàng)不是x2–x+1，而是x2+x+1。循環(huán)碼的生成矩陣G碼組生成公式G是k行n列的矩陣，若能找到k個(gè)已知碼組，就能構(gòu)成矩陣且這k個(gè)已知碼組必須是線性的。第二十九頁，共五十六頁，2022年，8月28日在循環(huán)碼中，一個(gè)(n,k)碼有2k

個(gè)不同的碼組。若用g(x)表示其中前(k–1)位皆為“0”的碼組，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個(gè)碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。在循環(huán)碼中除全“0”碼組外，再沒有連續(xù)k位均為“0”的碼組，即連“0”的長度最多只能有(k-1)位。g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，且此g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一多項(xiàng)式。我們稱這唯一的(n–k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。循環(huán)碼的生成矩陣G可以寫成第三十頁，共五十六頁，2022年，8月28日(7,3)循環(huán)碼中，n=7,k=3,n–k=4。不符合G=[IkQ]的形式，所以它不是典型陣。不過，將它作線性變換，不難化成典型陣。寫出此循環(huán)碼組，即唯一(n–k)=4次碼多項(xiàng)式代表的碼組是第二碼組0010111，對應(yīng)碼多項(xiàng)式

g(x)=x4+x2+x+1。將g(x)代入上式，得第三十一頁，共五十六頁，2022年，8月28日所有碼多項(xiàng)式T(x)都可被g(x)整除，而且任意一個(gè)次數(shù)不大于(k–1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。兩個(gè)矩陣相乘的結(jié)果應(yīng)該仍是一個(gè)矩陣。上式中兩個(gè)矩陣相乘的乘積是只有一個(gè)元素的一階矩陣，這個(gè)元素就是T(x)。尋找(n,k)循環(huán)碼的生成多項(xiàng)式任一循環(huán)碼多項(xiàng)式T(x)都是g(x)的倍式，可以寫成T(x)=h(x)g(x)，而生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有T

(x)=g(x)，碼組T

(x)是一個(gè)(n–k)次多項(xiàng)式，xkT

(x)是一個(gè)n次多項(xiàng)式。xkT

(x)在模(xn+1)運(yùn)算下也是一個(gè)碼組上式左端分子和分母都是n次多項(xiàng)式，故商式Q(x)=1。第三十二頁，共五十六頁，2022年，8月28日可以化成將T(x)和T(x)代入得g(x)是(xn+1)的一個(gè)因子，且為(n–k)次因式。【例】(x7+1)可以分解成(7,3)循環(huán)碼的生成多項(xiàng)式g(x)需要從上式中找到一個(gè)(n–k)=4次的因子都可作為生成多項(xiàng)式第三十三頁，共五十六頁，2022年，8月28日循環(huán)碼的編碼方法選定生成多項(xiàng)式g(x)-----從(xn+1)的因子中選一個(gè)(n-k)次多項(xiàng)式作為g(x)。用xn

-k乘m(x)，得到xn-km(x)，其次數(shù)小于n。xn

-km(x)/g(x)，得余式r(x)，其次數(shù)必小于g(x)，即小于(n–k)。r(x)加于信息位之后作為監(jiān)督位將r(x)和xn

-km(x)相加得到碼多項(xiàng)式。編碼步驟：用xn

-k乘m(x)。在信息碼后附加上(n–k)個(gè)“0”。信息碼為110，它相當(dāng)于m(x)=x2+x用g(x)除xn

-km(x)，得到商Q(x)和余式r(x)，即第三十四頁，共五十六頁，2022年，8月28日例如，若選定g(x)=x4+x2+x+1，則上式相當(dāng)于編出的碼組T(x)為T(x)=xn

-km(x)+r(x)T(x)=1100000+101=1100101，是表中的第7碼組。循環(huán)碼的解碼方法解碼要求：檢錯(cuò)和糾錯(cuò)。檢錯(cuò)解碼原理：在接收端將接收R(x)用g(x)去除。若碼組在傳輸中發(fā)生錯(cuò)誤，則R(x)

T(x)，

R(x)被g(x)除時(shí)可能除不盡而有余項(xiàng)，即有第三十五頁，共五十六頁，2022年，8月28日糾錯(cuò)解碼原理：要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一個(gè)特定余式有一一對應(yīng)關(guān)系。糾錯(cuò)可按下述步驟進(jìn)行：用生成多項(xiàng)式g(x)除接收碼組R(x)，得出余式r(x)。按余式r(x)，用查表或計(jì)算得到錯(cuò)誤圖樣E(x)；例如，通過計(jì)算校正子S和查表，可以確定錯(cuò)碼的位置。R(x)-E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組T(x)。一種編碼可以有幾種糾錯(cuò)解碼方法，上述解碼方法為捕錯(cuò)解碼目前多采用軟件運(yùn)算實(shí)現(xiàn)上述編解碼運(yùn)算。第三十六頁，共五十六頁，2022年，8月28日截短循環(huán)碼截短目的：在設(shè)計(jì)糾錯(cuò)編碼時(shí)，糾錯(cuò)能力預(yù)先給定的。 不一定有恰好滿足這些條件的循環(huán)碼存在。截短方法：一個(gè)(n,k)循環(huán)碼，使前i(0<i<k)個(gè)信息位全為“0”，于是它變成僅有2k-i

種碼組。刪去這i位全“0”的信息位，得到(n–i,k–i)的線性碼。將這種碼稱為截短循環(huán)碼。截短循環(huán)碼性能：循環(huán)碼截短前后至少具有相同的糾錯(cuò)能力，并且編解碼方法仍和截短前的方法一樣?！纠恳髽?gòu)造一個(gè)能夠糾正1位錯(cuò)碼的(13,9)碼。由(15,11)循環(huán)碼的11種碼組中選出前兩信息位均為“0”的碼組，構(gòu)成一個(gè)新的碼組集合。然后在發(fā)送時(shí)不發(fā)送這兩位“0”。于是發(fā)送碼組成為(13,9)截短循環(huán)碼。第三十七頁，共五十六頁，2022年，8月28日11.7卷積碼卷積碼是一種非分組碼。更適用于前向糾錯(cuò)，性能優(yōu)于分組碼，運(yùn)算簡單。一個(gè)碼組中的監(jiān)督碼元監(jiān)督著N個(gè)信息段本碼組kbit信息段，前m=(N–1)個(gè)碼組的信息段。N稱為編碼約束度，

nN稱為編碼約束長度。卷積碼記作(n,k,N)

碼率則仍定義為k/n第三十八頁，共五十六頁，2022年，8月28日卷積碼的基本原理編碼器原理方框圖編碼輸出每次輸入k比特1k…1k…1k…1k……

…

…

1…k…2k3kNk……

…

…

…

…

…

…

…

12nNk級移存器n個(gè)模2加法器每輸入k比特旋轉(zhuǎn)1周第三十九頁，共五十六頁，2022年，8月28日【例】(n,k,N)=(3,1,3)卷積碼編碼器bi-2bi輸入bibi-1編碼輸出dicieiM2M3M1設(shè)輸入信息比特序列是bi-2

bi-1

bibi+1，則當(dāng)輸入bi時(shí)，此編碼器輸出3比特cidiei，輸入和輸出第四十頁，共五十六頁，2022年，8月28日c1d1e1c2d2e2c3d3e3b1b2b3tt輸入輸出虛線示出了信息位bi

的監(jiān)督位和各信息位之間的約束關(guān)系。約束度N=3約束長度nN=9第四十一頁，共五十六頁，2022年，8月28日第4級支路開始，碼樹上半部和下半部相同。從第4個(gè)輸入信息位開始，輸出碼元與第1位輸入信息位無關(guān)，此編碼器約束度N=3卷積碼的幾何表述:(3,1,3)碼樹圖起點(diǎn)信息位狀態(tài)M3M2a00b01c10d11信息位 1 1 0 1000111000111001110011100010101000111001110011100010101111000001110c2d2e2000100111011001101110010abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab↑0↓1↓1↑0↑0↓1c4d4e4c3d3e3c1d1e1第四十二頁，共五十六頁，2022年，8月28日移存器前一狀態(tài)M3

M2當(dāng)前輸入信息位bi輸出碼元cidiei移存器下一狀態(tài)M3

M2a(00)01000111a(00)b(01)b(01)01001110c(10)d(11)c(10)01011100a(00)b(01)d(11)01010101c(10)d(11)狀態(tài)圖由編碼器結(jié)構(gòu)可知，輸出碼元ci

di

ei決定于當(dāng)前輸入信息位bi和前兩位信息位bi-1和bi-2（即移存器M2和M3的狀態(tài)）。第四十三頁，共五十六頁，2022年，8月28日abcd111000110101100001011010虛線表示輸入信息位為“0”時(shí)狀態(tài)轉(zhuǎn)變的路線；實(shí)線表示輸入信息位為“1”時(shí)狀態(tài)轉(zhuǎn)變的路線。

----------線條旁的3位數(shù)字是編碼輸出比特。第四十四頁，共五十六頁，2022年，8月28日110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100網(wǎng)格圖將狀態(tài)圖在時(shí)間上展開，網(wǎng)格圖：圖中畫出了5個(gè)時(shí)隙。在第4時(shí)隙以后的網(wǎng)格圖形完全是重復(fù)第3時(shí)隙的圖形。這也反映了此(3,1,3)卷積碼的約束長度為3。第四十五頁，共五十六頁，2022年，8月28日abcdabcd110010001111100輸入信息位為11010時(shí)，在網(wǎng)格圖中的編碼路徑。有了上面的狀態(tài)圖和網(wǎng)格圖，就可以討論維特比解碼算法了。卷積碼的解碼代數(shù)解碼：利用代數(shù)結(jié)構(gòu)進(jìn)行解碼，不考慮信道的統(tǒng)計(jì)特性。大數(shù)邏輯解碼，又稱門限解碼，對于約束長度較短的卷積碼最為有效，而且設(shè)備較簡單。概率解碼：又稱最大似然解碼。它基于信道的統(tǒng)計(jì)特性和卷積碼的特點(diǎn)進(jìn)行計(jì)算。另一種概率解碼方法是維特比算法。第四十六頁，共五十六頁，2022年，8月28日維特比解碼算法基本原理：將接收到的序列和所有可能的發(fā)送序列比較，選擇其中漢明距離最小的序列認(rèn)為是當(dāng)前發(fā)送信號序列。若發(fā)送一個(gè)k位序列，則有2k種可能的發(fā)送序列。當(dāng)k較大時(shí)，存儲量太大，使實(shí)用受到限制。維特比算法對此作了簡化，使之能夠?qū)嵱?。第四十七頁，共五十六頁?022年，8月28日(3,1,3)卷積碼設(shè)現(xiàn)在的發(fā)送信息位為1101，為使移存器的信息位全部移出，在信息位后面加入3個(gè)“0”，故編碼后的發(fā)送序列為111110010100001011000。并且假設(shè)接收序列為111010010110001011000

由于這是一個(gè)(n,k,N)=(3,1,3)卷積碼，發(fā)送序列的約束度N=3，所以首先需考察nN＝9比特。第1步考察接收序列前9位“111010010”。由此碼的網(wǎng)格圖可見，沿路徑每一級有4種狀態(tài)a,b,c和d。每種狀態(tài)只有兩條路徑可以到達(dá)。故4種狀態(tài)共有8條到達(dá)路徑。第四十八頁，共五十六頁，2022年，8月28日110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100由出發(fā)點(diǎn)狀態(tài)a經(jīng)過3級路徑后到達(dá)狀態(tài)a的兩條路徑中上面一條為“000000000”。和接收序列“111010010”的漢明距離等于5；下面一條為“111001011”,它和接收序列的漢明距離等于3。同樣，由出發(fā)點(diǎn)a經(jīng)過3級到達(dá)狀態(tài)b、c和d的路徑分別都有兩條，故總共有8條路徑。第四十九頁，共五十六頁，2022年，8月28日序號路徑對應(yīng)序列漢明距離幸存否1aaaa0000000005否2abca1110010113是3aaab0000001116否4abcb1110011004是5aabc0001110017否6abdc1111100101是7aabd0001111106否8abdd1111101014是將到達(dá)每個(gè)狀態(tài)的兩條路徑比較，將距離小的路徑保留，稱為幸存路徑。這樣就剩下4條路徑了，即表中第2,4,6和8條路徑。第五十頁，共五十六頁，2022年，8月28日110110110110011011011010010010