信息理論與編碼第六章信道編碼

信息理論與編碼第六章信道編碼第一頁，共一百五十一頁，2022年，8月28日§6.1信道編碼的概念§6.2線形分組碼§6.3循環(huán)碼§6.4卷積碼第二頁，共一百五十一頁，2022年，8月28日§6.1.1信道編碼的作用和分類§：編碼信道§：檢錯和糾錯原理§：檢錯和糾錯方式和能力第三頁，共一百五十一頁，2022年，8月28日信道編碼是以信息在信道上的正確傳輸為目標(biāo)的編碼，可分為兩個層次上的問題：如何正確接收載有信息的信號 －－線路編碼如何避免少量差錯信號對信息內(nèi)容的影響 －－糾錯編碼廣義信道編碼=特定信道上傳輸信息而進(jìn)行的傳輸信號或信號格式的設(shè)計與實現(xiàn)

第四頁，共一百五十一頁，2022年，8月28日

描述編碼

用于對特定數(shù)據(jù)信號的描述約束編碼用于對特定信號特性的約束擴(kuò)頻編碼用于擴(kuò)展信號頻譜為近似白噪聲譜并滿足某些相關(guān)特性糾錯編碼用于檢測與糾正信號傳輸過程中因噪聲干擾導(dǎo)致的差錯1234第五頁，共一百五十一頁，2022年，8月28日：信道編碼的作用和分類§6.1.3編碼信道：檢錯和糾錯原理：檢錯和糾錯方式和能力第六頁，共一百五十一頁，2022年，8月28日消息信道編碼

編碼信道

信道譯碼

碼字接收向量消息編碼信道模型第七頁，共一百五十一頁，2022年，8月28日n-1

當(dāng)碼字C和接受向量R均由二元序列表時，稱編碼信道為二進(jìn)制信道

C=(c0,c1,…cn-1)如果對于任意的n都有：

P(r/c)=∏p(ri/ci)則稱此二進(jìn)制信道為無記憶二進(jìn)制信道。

p(0/1)=p(1/0)=p0則稱此信道為無記憶二進(jìn)制對稱信道BSCi=0第八頁，共一百五十一頁，2022年，8月28日BSC轉(zhuǎn)移概率BSC編碼信道BSC輸入輸出關(guān)系等效為第九頁，共一百五十一頁，2022年，8月28日差錯圖案：隨機(jī)序列

或，

第位上的一個隨機(jī)錯誤：

長的突發(fā)錯誤：第至第

位之間有很多錯誤

對于一個BSC信道總有轉(zhuǎn)移概率1/2，比特傳輸中發(fā)生差錯數(shù)目越少，概率越大，即

從而總認(rèn)為發(fā)生差錯的圖案是差錯數(shù)目較少的圖案

第十頁，共一百五十一頁，2022年，8月28日二元軟判決信道

用多個比特（理想情況下為實數(shù)）表示每一個無記憶編碼信道的二元符號輸出

信道干擾z為零均值正態(tài)分布的隨機(jī)變量，噪聲干擾功率為均方差，z的概率分布為。對于BPSK調(diào)制，二元輸入符號為二元符號取值為+1或-1第十一頁，共一百五十一頁，2022年，8月28日第十二頁，共一百五十一頁，2022年，8月28日：信道編碼的作用和分類：編碼信道§6.1.3檢錯和糾錯原理：檢錯和糾錯方式和能力第十三頁，共一百五十一頁，2022年，8月28日檢糾錯是根據(jù)信道輸出序列自身判斷是否可能是發(fā)送的，或糾正導(dǎo)致不等于的錯誤。冗余編碼：碼字的長度一定大于消息的長度

糾錯編碼編碼碼率：每個碼字的序列符號（或碼元）平均傳送的消息比特數(shù)

第十四頁，共一百五十一頁，2022年，8月28日偶（或奇）校驗方法：實現(xiàn)檢糾錯目的的一個基本方法。

一個偶校驗位是對消息使得如下校驗方程成立的二進(jìn)制符號，即

一個偶校驗碼碼字

一個碼率為的偶校驗碼，所有可能的的全體校驗方程為1表明一定有奇數(shù)個差錯，校驗方程為0表明可能有偶數(shù)個差錯

第十五頁，共一百五十一頁，2022年，8月28日

m0+m1+m2+…+mk－1+p=0（mod2）

稱c=(m0,m1,m2…mk-1,p)為一個偶校驗字

確定校驗位P的編碼方程為：

P=m0+m1+…+mk-1第十六頁，共一百五十一頁，2022年，8月28日編碼可以產(chǎn)生多個奇偶校驗位，即一個校驗位可以由消息位的部分或全部按某種校驗方程產(chǎn)生，例如對陣列消息進(jìn)行垂直與水平校驗以及總校驗的碼字和其碼率分別為

第十七頁，共一百五十一頁，2022年，8月28日第十八頁，共一百五十一頁，2022年，8月28日重復(fù)消息位：實現(xiàn)檢糾錯目的第二個基本方法

一個重復(fù)碼是一個碼率為的碼，僅有兩個碼字和，傳送1比特（）消息。

重復(fù)碼可以檢測出任意小于個差錯的錯誤圖案，糾正任意小于個差錯的錯誤圖案。糾1位差錯的3重復(fù)碼

第十九頁，共一百五十一頁，2022年，8月28日等重碼或定比碼：實現(xiàn)檢糾錯的第三個方法。

設(shè)計碼字重量恒為常數(shù)，即

例如一種用于表示0至9數(shù)字的5中取3等重碼如表（6.1.1）所示，其碼率為

5中取3等重碼

1234567890010111100110110110100011110101111000111010011011015中取3等重碼可以檢測出全部奇數(shù)位差錯，對某些碼字的傳輸則可以檢測出部分偶數(shù)位差錯第二十頁，共一百五十一頁，2022年，8月28日§：信道編碼的作用和分類§：編碼信道§：檢錯和糾錯原理§6.1.4檢錯和糾錯方式和能力第二十一頁，共一百五十一頁，2022年，8月28日糾錯碼的應(yīng)用方式：前向糾錯方式（FEC），自動請求重發(fā)（ARQ）方式，混合糾錯（HEC）方式以及信息反饋（IRQ方式）

FEC與ARQ糾錯應(yīng)用方式

第二十二頁，共一百五十一頁，2022年，8月28日

常用漢明距離來描述檢糾差錯的數(shù)目，對于兩 n長向量u，v漢明距離為：

最小漢明距離（最小碼距d）：任意兩碼字之間的漢明距離的最小值

第二十三頁，共一百五十一頁，2022年，8月28日定理

對一個最小距離為糾錯碼，如下三個結(jié)論僅有其中任意一個結(jié)論成立，

（1）

可以檢測出任意小于等于個差錯；（2）

可以糾正任意小于等于個差錯；（3）可以檢測出任意小于等于l同時糾正小于等于t個差錯，其中l(wèi)和t滿足第二十四頁，共一百五十一頁，2022年，8月28日最小碼距與檢糾錯能力

第二十五頁，共一百五十一頁，2022年，8月28日差錯概率：通信作為一個統(tǒng)計過程時，糾檢錯能力的統(tǒng)計特性。FEC方式糾錯碼的碼字差錯概率：發(fā)送碼字的先驗概率

：碼字?jǐn)?shù)，對于充分隨機(jī)的消息源

第二十六頁，共一百五十一頁，2022年，8月28日對BSC信道

最大化等價于最小化，最小差錯概率譯碼等價為使接收向量與輸出碼字距離最小的最小距離譯碼，即

第二十七頁，共一百五十一頁，2022年，8月28日信息比特信噪比：傳輸一個比特信息所需的最小信噪比

比特差錯概率（又稱誤碼率）與信噪比的關(guān)系如下圖所示，采用糾錯碼后，達(dá)到同樣比特差錯概率實際需要的信噪比減小量稱為編碼增益。

編碼增益

第二十八頁，共一百五十一頁，2022年，8月28日§6.2線性碼

§6.2.1線性分組碼的描述§6.2.2線性分組碼的譯碼§6.2.3碼例與碼的重構(gòu)第二十九頁，共一百五十一頁，2022年，8月28日§6.2.1線性分組碼的描述§6.2.2線性分組碼的譯碼§6.2.3碼例與碼的重構(gòu)第三十頁，共一百五十一頁，2022年，8月28日一個（n,k）線形分組碼C是稱為碼字c的n維向量的集合

C={c|c=mG}其中m為任意的k維向量并稱為消息向量。G是k行n行列秩為k（n≥k）的矩陣并稱為生成矩陣，第三十一頁，共一百五十一頁，2022年，8月28日對于二元編碼，和是二元向量，是一個二元矩陣，，向量與矩陣，矩陣與矩陣之間的基本運(yùn)算是模二加和模二乘運(yùn)算。

表6.2.1模二加/乘法表

第三十二頁，共一百五十一頁，2022年，8月28日例6.2.13重復(fù)碼是一個（3，1）線性分組碼

第三十三頁，共一百五十一頁，2022年，8月28日例（4，3）偶校驗碼是一個（4，3）線性分組碼第三十四頁，共一百五十一頁，2022年，8月28日當(dāng)生成矩陣給定時線性分組碼有如下性質(zhì)：（1）零向量一定是一個碼字，稱為零碼字；（2）任意兩碼字的和仍是一個碼字；（3）任意碼字是的行向量的線性組合；（4）線性分組碼的最小距離等于最小非零碼字重量。

第三十五頁，共一百五十一頁，2022年，8月28日由偶校驗碼的檢錯概念，可以通過計算接收向量的所有校驗方程值是否為0來判斷傳輸是否可能有錯，那么必有一個矩陣滿足

顯然的每一列或的每一行確定了一個可能的分組碼的校驗方程，的線性不相關(guān)行數(shù)最少要等于該碼的所有可能的校驗方程數(shù)，稱這樣的矩陣為線性分組碼的一致校驗矩陣。

第三十六頁，共一百五十一頁，2022年，8月28日由的每一行都是一個碼字有

由現(xiàn)行空間的理論，當(dāng)H的行秩為r時，H作為一個(n,k)線性分組碼的生成矩陣所生成的碼是與G對應(yīng)空間正交的r維線性子空間，稱為(n,k)線性分組碼的對偶碼或?qū)ε伎臻g，并且有如下的維數(shù)關(guān)系成立第三十七頁，共一百五十一頁，2022年，8月28日T定理：任何滿足下式的n維向量a均是一（n,k）線形分組碼的碼字

aH=?其中滿足公式的H矩陣形式不唯一，但一個碼的對偶碼是惟一的。T第三十八頁，共一百五十一頁，2022年，8月28日系統(tǒng)碼：生成矩陣具有如下形式

在碼字集合不變的情況下，任何一個線性分組碼都可以一對一的去對應(yīng)一個系統(tǒng)碼。對于系統(tǒng)碼相應(yīng)的一致校驗矩陣注意與仍然滿足。

以線性分組碼的一致校驗矩陣為生成產(chǎn)生的線性分組碼稱為原線性分組碼的對偶碼。第三十九頁，共一百五十一頁，2022年，8月28日例6.2.3一個（5，3）線性分組碼的

其中到的行初等變換過程為（表示第i行），

第四十頁，共一百五十一頁，2022年，8月28日（5，3）線性分組碼碼例

消息mG生成碼字Gs生成碼字對偶碼碼字00000101001110010111011100000110100101110001101100110011101001110000000111010110110010001101101101011101

00000111010111010011第四十一頁，共一百五十一頁，2022年，8月28日由一致校驗矩陣可以比較容易確定線性分組碼的最小碼距

定理

線性分組碼的最小碼距為，當(dāng)且僅當(dāng)其一致校驗矩陣H中任意列線性無關(guān)，某列線性相關(guān)。

該定理實際給出了計算線性分組碼最小碼距的一種方法。

第四十二頁，共一百五十一頁，2022年，8月28日§6.2.1線性分組碼的描述§6.2.2線性分組碼的譯碼§6.2.3碼例與碼的重構(gòu)第四十三頁，共一百五十一頁，2022年，8月28日譯碼的概念檢錯譯碼：譯碼器輸出為當(dāng)前接收向量r和r是否有差錯的標(biāo)志s，即。第四十四頁，共一百五十一頁，2022年，8月28日糾錯譯碼的譯碼成功狀態(tài)：譯碼器能夠在達(dá)到譯碼碼字差錯概率最小條件下輸出一個確切的碼字，即。第四十五頁，共一百五十一頁，2022年，8月28日糾錯譯碼的譯碼成功狀態(tài)：譯碼器能夠在達(dá)到譯碼碼字差錯概率最小條件下輸出一個確切的碼字，即。糾錯譯碼的譯碼失敗狀態(tài)：譯碼器不能輸出一個確切的碼字，通常此時的輸出y與檢錯譯碼輸出相同。

第四十六頁，共一百五十一頁，2022年，8月28日定義：(n,k）線形分組碼的伴隨式是一個r(r=n-k)維向量s

，則傳輸中一定有錯誤發(fā)生，則傳輸中要么無差錯發(fā)生，要么差錯圖案恰好為一個碼字。

第四十七頁，共一百五十一頁，2022年，8月28日定理

可糾t錯的q元線性分組碼滿足

第四十八頁，共一百五十一頁，2022年，8月28日伴隨式糾錯譯碼的通用譯碼方法

（1）按最可能出現(xiàn)的個差錯圖案，計算相應(yīng)的伴隨式，并構(gòu)造伴隨式—差錯圖案表；（2）對接收向量計算伴隨式；（3）查表得；（4）糾錯計算。第四十九頁，共一百五十一頁，2022年，8月28日§6.2.1線性分組碼的描述§6.2.2線性分組碼的譯碼§6.2.3碼例與碼的重構(gòu)第五十頁，共一百五十一頁，2022年，8月28日常見的線形分組碼有重復(fù)碼，漢明碼，里德-穆勒碼，戈雷碼（1）漢明碼：二元Hamming碼是一種的完備碼，滿足

其中列向量為全部可能的非零元組。

第五十一頁，共一百五十一頁，2022年，8月28日Hamming碼的對偶碼是一個線性分組碼，稱為最大長度碼，由于所有非零碼字的重量均為，又稱為等距碼或單形（simplex）碼。第五十二頁，共一百五十一頁，2022年，8月28日例6.2.4一個二元（7，4）Hamming碼的系統(tǒng)碼形式的矩陣和校驗矩陣分別為

等價的編碼方程為

第五十三頁，共一百五十一頁，2022年，8月28日伴隨式計算方程

第五十四頁，共一百五十一頁，2022年，8月28日（2）Hadamard碼

Hadamard碼是由Hadamard矩陣派生出的一種糾錯碼。

階實Hadamard矩陣由元素為+1，-1的矩陣遞歸定義為

例如

第五十五頁，共一百五十一頁，2022年，8月28日第五十六頁，共一百五十一頁，2022年，8月28日Hadamard矩陣為正交矩陣，即中的任意不同兩行（列）的點積為0，即

超正交矩陣：Hadamard矩陣中的第1列（全+1列）去掉后由于任兩行的點積為-1。

將Hadamard矩陣元素+1/-1映射為0/1，則Hadamard矩陣映射后的行向量為一個二元向量，以這些二元向量的部份或全體就構(gòu)成標(biāo)準(zhǔn)0/1二元意義上的分組碼，并稱為Hadamard碼。具體的Hadamard碼的選擇構(gòu)成有正交碼、雙正交碼和超正交碼三種形式。

第五十七頁，共一百五十一頁，2022年，8月28日（A）正交碼：以的全部行向量的0/1映射向量為碼字。（B）雙正交碼：以和-的全部行向量的0/1映射向量為碼字。

第五十八頁，共一百五十一頁，2022年，8月28日（C）超正交碼：以的全部行向量的0/1映射向量為碼字。

可以證明正交碼、雙正交碼和超正交碼均是線性分組碼。

第五十九頁，共一百五十一頁，2022年，8月28日例6.2.5（7，3）超正交碼的超正交矩陣和生成矩陣G分別為

第六十頁，共一百五十一頁，2022年，8月28日(3)里德-穆勒（Reed-Muller）階碼是一種 線性分組碼，滿足第六十一頁，共一百五十一頁，2022年，8月28日其中各個子矩陣的定義為

1）為矩陣，由全1向量構(gòu)成。2）為矩陣，由所有可能的m元組組成矩陣的列向量。3）為的所有兩不同行向量的叉積構(gòu)成其全部行向量的矩陣。兩向量的叉積為4）為的所有三不同行向量的叉積構(gòu)成其全部行向量的矩陣。5）為的所有個不同行向量的叉積構(gòu)成其全部行向量的矩陣。

r第六十二頁，共一百五十一頁，2022年，8月28日例6.2.6

的階RM碼的各個子矩陣有

第六十三頁，共一百五十一頁，2022年，8月28日

碼的對偶碼仍是一個Reed-Muller碼，為碼。

第六十四頁，共一百五十一頁，2022年，8月28日（4）戈雷碼二元戈雷碼是一種就糾3個錯的完備線形分組碼，滿足：

n=23k=12{第六十五頁，共一百五十一頁，2022年，8月28日由于

因此某種二元（23,12）碼一定可以糾正任意小于等于3個差錯，所以

第六十六頁，共一百五十一頁，2022年，8月28日§6.3循環(huán)碼循環(huán)碼的多項式描述循環(huán)碼的生成矩陣多項式運(yùn)算電路系統(tǒng)循環(huán)碼循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測碼與RS碼第六十七頁，共一百五十一頁，2022年，8月28日§6.3.1循環(huán)碼的多項式描述循環(huán)碼的生成矩陣系統(tǒng)循環(huán)碼多項式運(yùn)算電路循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測碼與RS碼第六十八頁，共一百五十一頁，2022年，8月28日

更好的設(shè)計和實現(xiàn)線性分組碼的方法是引入特定的數(shù)學(xué)結(jié)構(gòu)來界定某一類線性分組碼。循環(huán)碼即是采用循環(huán)移位特性界定的一類線性分組碼。

6.3.1循環(huán)碼的多項式描述第六十九頁，共一百五十一頁，2022年，8月28日第七十頁，共一百五十一頁，2022年，8月28日第七十一頁，共一百五十一頁，2022年，8月28日定義如果一個線性分組碼的任意一個碼字c(n元組)都是另外一個碼字c’的循環(huán)移位,稱此線性分組碼為一個循環(huán)碼.

將循環(huán)碼的碼字用多項式c(x)，稱為碼多項式（簡稱碼式）表示后，循環(huán)碼集合表示C(x),

第七十二頁，共一百五十一頁，2022年，8月28日例6.3.2如下確定的CA是線性循環(huán)碼，CB是非循環(huán)的線性分組碼，CC是非線性的循環(huán)碼。

，

，

第七十三頁，共一百五十一頁，2022年，8月28日定理：

（n,k）循環(huán)碼C(x)中存在唯一的一個非零的，首一的和最低次為r（r<n）的碼

多項式g(x)滿足：

g(x)=xr+gr-1xr-1+….+g1X+g0

g0≠0

r=n-k并且c(x)是碼式當(dāng)且僅當(dāng)c(x)是g(x)的倍式第七十四頁，共一百五十一頁，2022年，8月28日定義由上述定理確定的碼式g(x)稱為循環(huán)碼(n,k)的生成多項式.

因此(n,k)循環(huán)碼的構(gòu)造是如何構(gòu)造生成多項式g(x)。

循環(huán)碼由生成多項式的倍式組成第七十五頁，共一百五十一頁，2022年，8月28日定理：

g(x)是（n,k）循環(huán)碼的生成多項式，當(dāng)且僅當(dāng)g(x)是xn-1的r=n-k次因式。第七十六頁，共一百五十一頁，2022年，8月28日第七十七頁，共一百五十一頁，2022年，8月28日第七十八頁，共一百五十一頁，2022年，8月28日第七十九頁，共一百五十一頁，2022年，8月28日循環(huán)碼的多項式描述§6.3.2循環(huán)碼的生成矩陣系統(tǒng)循環(huán)碼多項式運(yùn)算電路循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測碼與RS碼第八十頁，共一百五十一頁，2022年，8月28日循環(huán)碼的生成矩陣和校驗矩陣(n,k)循環(huán)碼的生成矩陣為第八十一頁，共一百五十一頁，2022年，8月28日(n,k)循環(huán)碼的校驗矩陣為第八十二頁，共一百五十一頁，2022年，8月28日循環(huán)碼的多項式描述循環(huán)碼的生成矩陣§6.3.3系統(tǒng)循環(huán)碼多項式運(yùn)算電路循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測碼與RS碼第八十三頁，共一百五十一頁，2022年，8月28日6.3.3系統(tǒng)循環(huán)碼循環(huán)碼的系統(tǒng)碼碼式為第八十四頁，共一百五十一頁，2022年，8月28日第八十五頁，共一百五十一頁，2022年，8月28日循環(huán)碼的多項式描述循環(huán)碼的生成矩陣系統(tǒng)循環(huán)碼§6.3.4多項式運(yùn)算電路循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測碼與RS碼第八十六頁，共一百五十一頁，2022年，8月28日6.3.4多項式運(yùn)算電路因為多項式表示時間序列所以多項式的計算表現(xiàn)為對時間序列的操作.第八十七頁，共一百五十一頁，2022年，8月28日多項式a(x)與b(x相加電路第八十八頁，共一百五十一頁，2022年，8月28日

a(x)與g(x)的一般乘法電路第八十九頁，共一百五十一頁，2022年，8月28日第九十頁，共一百五十一頁，2022年，8月28日循環(huán)碼的多項式描述循環(huán)碼的生成矩陣系統(tǒng)循環(huán)碼多項式運(yùn)算電路§6.3.5循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測碼與RS碼第九十一頁，共一百五十一頁，2022年，8月28日非循環(huán)碼編碼器

根據(jù)多項式乘法電路和循環(huán)碼碼式是生多項式倍式原理，多項式乘法電路(圖6.3.4)是循環(huán)碼的非系統(tǒng)碼電路，又稱為循環(huán)碼乘法編碼電路圖6.3.4第九十二頁，共一百五十一頁，2022年，8月28日2.系統(tǒng)編碼電路

循環(huán)碼系統(tǒng)編碼電路由乘法電路，求余式電路以及加法開關(guān)電路組成,如圖所示,電路工作過程如表所示.圖6.3.14第九十三頁，共一百五十一頁，2022年，8月28日表6.3.2循環(huán)碼系統(tǒng)碼編碼電路工作過程第九十四頁，共一百五十一頁，2022年，8月28日§6.3.1循環(huán)碼的多項式描述§6.3.2循環(huán)碼的生成矩陣§6.3.3系統(tǒng)循環(huán)碼§6.3.4多項式運(yùn)算電路§6.3.5循環(huán)碼的編碼電路§6.3.6循環(huán)碼的伴隨多項式與檢測§6.3.7BCH碼與RS碼第九十五頁，共一百五十一頁，2022年，8月28日循環(huán)碼的譯碼分成檢錯譯碼與糾錯譯碼兩類.1.檢錯譯碼原理第九十六頁，共一百五十一頁，2022年，8月28日2.糾錯譯碼循環(huán)碼的糾錯譯碼要達(dá)到碼的最小距離依賴于具體的循環(huán)碼的結(jié)構(gòu).第九十七頁，共一百五十一頁，2022年，8月28日循環(huán)碼的多項式描述循環(huán)碼的生成矩陣系統(tǒng)循環(huán)碼多項式運(yùn)算電路循環(huán)碼的編碼電路循環(huán)碼的伴隨多項式與檢測§6.3.7BCH碼與RS碼第九十八頁，共一百五十一頁，2022年，8月28日BCH碼是一類能夠先確定糾錯能力t，然后設(shè)計碼長和生成多項式的碼。對于任意的整數(shù)m和可達(dá)到糾錯數(shù)t，都可以構(gòu)造出一個設(shè)計距離為d0的二元本原BCH碼滿足：

n=2m-1,r=n-k≤mt,dmin≥d0=2t+1第九十九頁，共一百五十一頁，2022年，8月28日RS碼是多元BCH碼的一個子類，碼字向量的每個分量可以表示`為m比特，其基本參數(shù)為：碼長：n=2m-1(符號)=m(2m-1)（比特）

校驗位長：r=n-k=2t(符號)=m·2t其中t為RS碼可以糾正的差錯符號數(shù).第一百頁，共一百五十一頁，2022年，8月28日§6.4卷積碼卷積碼的多項式描述

卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述維特比（Viterbi）譯碼算法卷積碼的矩陣描述第一百零一頁，共一百五十一頁，2022年，8月28日§6.4.1卷積碼的矩陣描述卷積碼的多項式描述卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述維特比（Viterbi）譯碼算法第一百零二頁，共一百五十一頁，2022年，8月28日卷積碼編碼：當(dāng)前輸出

不僅與當(dāng)前輸入消息

相關(guān)，還與此前輸入的

個消息

相關(guān)，

二元線性卷積碼：是僅由模二加運(yùn)算組成的布爾函數(shù)

第一百零三頁，共一百五十一頁，2022年，8月28日的長度恒為

比特，

的長度恒為

n比特，均稱為一段

第一百零四頁，共一百五十一頁，2022年，8月28日任意一輸入段

與輸出段

的關(guān)系都是一個特殊的

線性分組碼的編碼

第一百零五頁，共一百五十一頁，2022年，8月28日卷積編碼的離散卷積表達(dá)式卷積碼的記憶長度（段）：

約束長度（段）：

或

第一百零六頁，共一百五十一頁，2022年，8月28日結(jié)尾處理：額外輸入

段無效的0數(shù)據(jù)

比特，保證編碼器回到全0的初態(tài)

有限

段長消息的編碼速率為：

漸近編碼速率：

第一百零七頁，共一百五十一頁，2022年，8月28日卷積碼的生成矩陣

二元線性

卷積碼

定義第一百零八頁，共一百五十一頁，2022年，8月28日基本生成矩陣

：生成矩陣

的前

行，

列組成的子矩陣

第

個生成元

：

的第

行，描述

了所有各段輸入中的第

位輸入比特

對所有輸出比特的影響

第一百零九頁，共一百五十一頁，2022年，8月28日將的元素

的列下標(biāo)

表示為

則輸入移位寄存器中的第

段的第

位輸入比特

參與第

位輸出比特的編碼

<-->

不參與第

位輸出比特的編碼<-->

第一百一十頁，共一百五十一頁，2022年，8月28日卷積碼的子生成元或生成序列：

元組

第一百一十一頁，共一百五十一頁，2022年，8月28日線性卷積碼的矩陣（或向量）描述：

第一百一十二頁，共一百五十一頁，2022年，8月28日生成矩陣

，基本生成矩陣

，生成序列（生成元）

系統(tǒng)卷積碼：卷積碼每段輸出的

位中有

位（如當(dāng)前

位）恒等于每段輸入的

位

第一百一十三頁，共一百五十一頁，2022年，8月28日其中

均為

矩陣。

第一百一十四頁，共一百五十一頁，2022年，8月28日由于對每個獨(dú)立的輸入段（每段

比特，共3段）分別有

基本生成矩陣

為

，生成矩陣為

，生成元為

，生成

第一百一十五頁，共一百五十一頁，2022年，8月28日序列為

第一百一十六頁，共一百五十一頁，2022年，8月28日卷積碼的矩陣描述§6.4.2卷積碼的多項式描述卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述維特比（Viterbi）譯碼算法第一百一十七頁，共一百五十一頁，2022年，8月28日6.4.2卷積碼的多項式描述消息段序列的多項式表示第一百一十八頁，共一百五十一頁，2022年，8月28日多項式描述更直接的描述了（二元）

卷積碼作為一個

（比特）入，

（比特）

出的編碼關(guān)系

編碼輸出段序列的多項式表示第一百一十九頁，共一百五十一頁，2022年，8月28日線性

卷積碼的多項式表達(dá)式為

線性

卷積碼的多項式矩陣

：為

的多項式矩陣

又稱

為卷積碼的延遲算子生成矩陣。第一百二十頁，共一百五十一頁，2022年，8月28日定理

線性

卷積碼的多項式生成矩陣

對

滿足

的

冪次項系數(shù)等于

生成序列

的第

個分量，

1第一百二十一頁，共一百五十一頁，2022年，8月28日即

的最大次數(shù)等于卷積碼的記

憶長度

，即

2第一百二十二頁，共一百五十一頁，2022年，8月28日例

前述例（2,1,2）卷積碼重畫如圖

第一百二十三頁，共一百五十一頁，2022年，8月28日卷積碼的矩陣描述卷積碼的多項式描述§6.4.3卷積碼的狀態(tài)轉(zhuǎn)移圖與格描述維特比（Viterbi）譯碼算法第一百二十四頁，共一百五十一頁，2022年，8月28日卷積碼與分組碼的明顯區(qū)別是卷積碼編碼器要存儲m段信息，這些信息數(shù)據(jù)既要因新的輸入而改變，又要影響當(dāng)前的編碼輸出，因此稱存儲表達(dá)這些數(shù)據(jù)的參量為卷積編碼器的內(nèi)部狀態(tài)，簡稱狀態(tài)。第一百二十五頁，共一百五十一頁，2022年，8月28日狀態(tài)：既要因新的輸入而改變，又要

影響當(dāng)前的編碼輸出的數(shù)據(jù)。

卷積編碼器有效的存貯單元數(shù)為

第一百二十六頁，共一百五十一頁，2022年，8月28日其中

為每個輸入移位寄存器的

有效級數(shù)（寄存單元數(shù)）。因此二元卷積

碼的狀態(tài)變量記為狀態(tài)向量

或簡記為

第一百二十七頁，共一百五十一頁，2022年，8月28日狀態(tài)數(shù)：二元

卷積碼共有

個不同的狀態(tài)，記為

狀態(tài)轉(zhuǎn)移：當(dāng)狀態(tài)為

（或

）時，

輸入段

（或

）產(chǎn)生編碼輸出段

（或

），并使該

狀態(tài)改變（稱為

轉(zhuǎn)移）到新的狀態(tài)

（或

）。

第一百二十八頁，共一百五十一頁，2022年，8月28日轉(zhuǎn)移分支：到

的轉(zhuǎn)移過程，記為

（

，

）或（

，

），并標(biāo)

記為

或

分支為有向邊描述卷積碼的所有不同狀態(tài)

轉(zhuǎn)移的有向圖

狀態(tài)轉(zhuǎn)移圖：以狀態(tài)為結(jié)點，轉(zhuǎn)移

第一百二十九頁，共一百五十一頁，2022年，8月28日狀態(tài)轉(zhuǎn)移方程：

與

的關(guān)系

輸出方程：

與

的關(guān)系

第一百三十頁，共一百五十一頁，2022年，8月28日盡管卷積碼有

個狀態(tài)，但是由于每段

的輸入為

比特只有

種狀態(tài)的變

化，每個狀態(tài)只轉(zhuǎn)移到

個狀態(tài)的某個

子集（個狀態(tài)）中去，每個狀態(tài)

也只能由某

個狀態(tài)的狀態(tài)子集轉(zhuǎn)移

而來。

第一百三十一頁，共一百五十一頁，2022年，8月28日例第一百三十二頁，共一百五十一頁，2022年，8月28日狀態(tài)轉(zhuǎn)移圖（閉合形）

第一百三十三頁，共一百五十一頁，2022年，8月28日狀態(tài)轉(zhuǎn)移圖（開放形）

狀態(tài)轉(zhuǎn)移方程和輸出方程分別為

第一百三十四頁，共一百五十一頁，2022年，8月28日卷積編碼器工作過程：

*卷積編碼器工作初態(tài)為（全0狀態(tài)）

*消息段序列產(chǎn)生輸出段序列

*消息段序列產(chǎn)生狀態(tài)序列

第一百三十五頁，共一百五十一頁，2022年，8月28日柵格圖或籬笆圖：開放形的狀態(tài)轉(zhuǎn)移圖按時間順序級聯(lián)

編碼路徑：狀態(tài)序列在柵格圖中形成一條有向路徑

一個卷積碼碼字：有向路徑始于全0狀態(tài)，又終于時的一條有向路徑

對于的卷積碼，常用實線表示 時輸入產(chǎn)生的轉(zhuǎn)移分支，用虛線表示 時輸入產(chǎn)生的轉(zhuǎn)移分支

第一百三十六頁，共一百五十一頁，2022年，8月28日例

前述例（2，1，2）碼的柵格圖及幾條路徑例

第一百三十七頁，共一百五十一頁，2022年，8月28日路徑A消息A（100）輸出A（111011）路徑B消息B（10110）輸出B（1110000101）路徑