第五章-卷積碼碼1課件

第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼6/7/20231信道編碼第五章卷積碼重點(diǎn)掌握：卷積碼的基本概念與編碼方法卷積碼的格圖描述重點(diǎn)理解：卷積碼的維特比譯碼算法6/7/20232信道編碼第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼6/7/20233信道編碼5.1卷積碼的基本概念卷積碼的提出與發(fā)展1954年，埃里斯（Elias）提出卷積碼的概念，它是完全不同于線性分組碼的一個碼類。1961年，提出卷積碼的序列譯碼方法。1963年，梅西（Massey）提出了卷積碼的代數(shù)譯碼方法—門限譯碼。1967年，維特比（Vitebi）提出了卷積碼的最大似然譯碼方法，稱為維特比算法。直到現(xiàn)在，仍是應(yīng)用最為廣泛的譯碼算法。6/7/20234信道編碼5.1卷積碼的基本概念一個簡單的卷積碼編碼例子初始狀態(tài)：00設(shè)輸入m=101100……則輸出與輸入的關(guān)系為：輸入：1狀態(tài)：00輸出：11010011010011010011100011100000………碼序列碼分組碼序列編碼存儲信息分組6/7/20235信道編碼5.1卷積碼的基本概念說明：可以將卷積碼的編碼器看作一個由k0個輸入端和n0個輸出端組成的時序網(wǎng)絡(luò)，即每輸入k0個信息元，輸出n0個碼元組成的碼分組(子碼)。例子中k0=1,n0=2；編碼器某個時刻的輸出不僅與該時刻編碼器的輸入有關(guān)，而且與以前若干時刻(由編碼存儲單元的個數(shù)決定)的輸入編碼器的信息有關(guān)。卷積碼的碼字（碼序列）可以看作是由無限多個碼分組組成的碼向量，即碼字是一個無限維向量。6/7/20236信道編碼5.1卷積碼的基本概念幾個基本概念信息分組與碼分組(子碼)：k0，n0k0:每個時刻輸入編碼器信息組中的信息元個數(shù)；n0:每個時刻編碼器輸出一個子碼中碼元的個數(shù)。系統(tǒng)碼與非系統(tǒng)碼： 如果在n0位長的碼分組中，前k0位是原輸入的信息元，則該卷積碼為系統(tǒng)碼，否則稱為非系統(tǒng)碼。編碼效率：R=k0/n06/7/20237信道編碼5.1卷積碼的基本概念幾個基本概念編碼存儲m：表示編碼過程中，輸入的信息組在編碼器中需要存貯的單位時間。前面例子中，m=2編碼約束度N=m+1：表示編碼過程中相互約束的碼分組個數(shù)。編碼約束長度n0N：表示編碼過程中相互約束的碼元數(shù)目。 參數(shù)m,N,k0,n0反映了編碼器的復(fù)雜度 卷積碼通常記為：(n0,k0,m)卷積碼或N(n0,k0)6/7/20238信道編碼5.1卷積碼的基本概念卷積碼的特點(diǎn)：當(dāng)前碼分組輸出不僅與當(dāng)前信息分組輸入有關(guān)，還與前面m個信息分組有關(guān)。在相同碼率、相同譯碼復(fù)雜性條件下，卷積碼的性能要好于分組碼。卷積碼仍是線性碼，滿足線性疊加關(guān)系。通常情況下，非系統(tǒng)碼的性能好于系統(tǒng)碼。尚沒有完善的數(shù)學(xué)工具有效地分析其結(jié)構(gòu)和性能，須借助計算機(jī)搜索來尋找好碼。6/7/20239信道編碼第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼6/7/202310信道編碼5.2卷積碼的矩陣描述與編碼卷積碼的特點(diǎn)：當(dāng)前碼分組輸出不僅與當(dāng)前信息分組輸入有關(guān)，還與前面m個信息分組有關(guān)。在相同碼率、相同譯碼復(fù)雜性條件下，卷積碼的性能要好于分組碼。卷積碼仍是線性碼，滿足線性疊加關(guān)系。通常情況下，非系統(tǒng)碼的性能好于系統(tǒng)碼。尚沒有完善的數(shù)學(xué)工具有效地分析其結(jié)構(gòu)和性能，須借助計算機(jī)搜索來尋找好碼。6/7/202311信道編碼5.2卷積碼的矩陣描述與編碼卷積碼的生成矩陣與編碼系統(tǒng)卷積碼的校驗(yàn)矩陣初始截短碼卷積碼的距離特性6/7/202312信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例 設(shè)：m=(m0,m1,m2,…)

C=(C0,C1,C2,…)，其中Ci=(ci(1),ci(2))若輸入信息序列和編碼器相應(yīng)輸出序列為：m’=(100…)C’=(110111…)m’’=(0100..) C’’=(00110111…)m’’’=(0010...) C’’’=(0000110111…)6/7/202313信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例 設(shè)：m=(m0,m1,m2,…)

C=(C0,C1,C2,…)，其中Ci=(ci(1),ci(2))若輸入信息序列分別為m=m’+m’’+m’’’=(100…)+(0100..)+(0010...)=(1110…)編碼器相應(yīng)輸出的碼序列為：C=C’+C’’+C’’=(110111…) +(00110111…) +(0000110111…)=(1110011011…)6/7/202314信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例 設(shè)：m=(m0,m1,m2,…)

C=(C0,C1,C2,…)，其中Ci=(ci(1),ci(2))若輸入信息序列分別為m=m’+m’’+m’’’=(100…)+(0100..)+(0010...)=(1110…)編碼器相應(yīng)輸出的碼序列為：

C=mG∞=(1110…)110111… 00110111… 0000110111… ………6/7/202315信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例 設(shè)：m=(m0,m1,m2,…)

C=(C0,C1,C2,…)，其中Ci=(ci(1),ci(2))(2,1,2)卷積碼的生成矩陣為：

1101110000… G∞=001101110000… 00001101110000… ……

g∞g0g1g26/7/202316信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例g∞=[11011100…]=[g0g1g20…]稱為(2,1,2)卷積碼的基本生成矩陣。

其中：g0=[11],g1=[01],g2=[11]均為1x2(k0xn0)階矩陣，稱為該碼的子生成矩陣。子生成矩陣的行構(gòu)成的向量,稱為該碼的生成元。

g(1)=110111生成元g(1)=110111中每一段對應(yīng)位構(gòu)成的子向量g(1,1)=101,g(1,2)=111稱為該碼的子生成元。6/7/202317信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例子生成元的物理含義： 子生成元g(1,j)表示了碼分組中第j個碼元與參與運(yùn)算的共m+1個信息元之間的校驗(yàn)關(guān)系，它對應(yīng)于編碼器的抽頭系數(shù)。生成元的物理含義： 生成元g(1)表示了碼分組與m+1個信息元之間的校驗(yàn)關(guān)系。6/7/202318信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

對于一般的(n0,1,m)卷積碼：

子生成元一共有n0個，每個子生成元都是一個m+1重向量，記為：

g(1,1)=[g0(1,1)g1(1,1)…gm(1,1)] g(1,2)=[g0(1,2)g1(1,2)…gm(1,2)] …… g(1,n0)=[g0(1,n0)g1(1,n0)…gm(1,n0)] g0,g1,…,gm為子生成矩陣6/7/202319信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

它們對應(yīng)編碼器的n0組抽頭系數(shù)特別地：對于系統(tǒng)卷積碼，其第一個子生成元為

g(1,1)=[100…0]。對于一般的(n0,1,m)卷積碼：

生成元僅有一個，可以由子生成元得到：

g(1)=[g0(1,1)g0(1,2)…g0(1,n0)g1(1,1)g1(1,2)… g1(1,n0)…gm(1,1)gm(1,2)…gm(1,n0)]

子生成矩陣gi為：

gi=[gi(1,1)gi(1,2)…gi(1,n0)]6/7/202320信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

因此可得到(n0,1,m)卷積碼的基本生成矩陣：

g∞=[g0g1…gm0…](n0,1,m)卷積碼的生成矩陣為：6/7/202321信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的編碼原理對于線性碼均有C=mG，因此對卷積碼有：C∞=m∞G∞(n0,1,m)卷積碼的編碼可由如下電路實(shí)現(xiàn)：6/7/202322信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

(n0,1,m)卷積碼舉例：給定一卷積碼的子生成元為：

g(1,1)=10011，g(1,2)=11101判斷該碼的參數(shù)，寫出生成矩陣，給出編碼電路；假設(shè)信息序列m=110110000…，試求出編碼序列C∞6/7/202323信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

由子生成元g(1,1)=10011，g(1,2)=11101

可得：m=4，n0=2，k0=1

該碼為(2,1,4)非系統(tǒng)卷積碼

其生成元為：g(1)=1101011011

子生成矩陣為：

g0=[11],g1=[01],g2=[01],g3=[10],g4=[11]

6/7/202324信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

于是該碼的生成矩陣為：

110101101100… 00110101101100… 0000110101101100… G∞= …00110101101100… …00110101101100… …6/7/202325信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

根據(jù)子生成元可畫出(2,1,4)碼的編碼電路：g(1,1)=10011，g(1,2)=111016/7/202326信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣已知m=110110000…

由C∞=m∞G∞可得碼序列為：

C∞=11100000111111011100… 110101101100… 00110101101100… 0000110101101100… G∞= …00110101101100… …00110101101100… …6/7/202327信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣一般地，對于(n0,k0,m)卷積碼： 子生成元：一共有k0xn0個，記為：

g(1,1),g(1,2),…,g(1,n0) g(2,1),g(2,2),…,g(2,n0) …… g(k0,1),g(k0,2),…,g(k0,n0)6/7/202328信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣每個子生成元均為m+1重向量：

g(i,j)=g0(i,j)g1(i,j)…gm(i,j)特別地：對于系統(tǒng)卷積碼，其子生成元有如下特點(diǎn)：6/7/202329信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣生成元：一共有k0個，記為：

g(1),g(2),…,g(k0)

每個生成元均為n0x(m+1)重向量：

g(i)=g0(i,1)g0(i,2)…g0(i,n0)…gm(i,1)…gm(i,n0)

其中：gt(i,j)：子生成元g(i,j)的第t位

子生成矩陣：一共有m+1個，g0,g1,…,gm

每個子生成矩陣均為k0xn0階矩陣：6/7/202330信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣特別地：對于系統(tǒng)卷積碼，其子生成矩陣有如下特點(diǎn)： 其中，P0,P1,…,Pm為k0xr0階矩陣

6/7/202331信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼的生成矩陣6/7/202332信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼的編碼原理 根據(jù)子生成元可構(gòu)造(n0,k0,m)卷積碼的編碼電路。

參見教材(Page198)6/7/202333信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例： 給定一卷積碼的子生成元為：

g(1,1)=100，g(1,2)=000，g(1,3)=101 g(2,1)=000，g(2,2)=100，g(2,3)=110

判斷該碼的參數(shù)，寫出生成矩陣，給出編碼電路；假設(shè)信息序列m=10110000…，試求出編碼序列C∞6/7/202334信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：

由子生成元可得：

m=2，n0=3，k0=2其生成元為：

g(1)=101000001 g(2)=011001000該碼為(3,2,2)系統(tǒng)卷積碼g(1,1)=100g(1,2)=000g(1,3)=101g(2,1)=000g(2,2)=100g(2,3)=1106/7/202335信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：

其子生成矩陣為:

該碼的生成矩陣為：

101000001000… 011001000000… 000101000001000… G∞= 000011001000000… 000000101000001000… 000000011001000000… ……6/7/202336信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：根據(jù)子生成元可畫出(3,2,2)碼的編碼電路：

g(1,1)=100g(1,2)=000g(1,3)=101g(2,1)=000g(2,2)=100g(2,3)=1106/7/202337信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：已知m=10110000…

由C∞=m∞G∞可得碼序列為：

C=101110000001000…

6/7/202338信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗(yàn)矩陣(n0,k0,m)系統(tǒng)卷積碼的校驗(yàn)矩陣 卷積碼是線性碼，生成矩陣和校驗(yàn)矩陣之間滿足：GHT=0

根據(jù)上述關(guān)系式可由生成矩陣G∞求得H∞

對于系統(tǒng)卷積碼，G∞和H∞之間有簡單的轉(zhuǎn)換關(guān)系。

6/7/202339信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗(yàn)矩陣(n0,k0,m)卷積碼的校驗(yàn)矩陣具有如下形式：

h00… h1h00… h2h1h00… H∞= …… hmhm-1…h(huán)1h00… 0hm…h(huán)2h1h00… ……h(huán)0,h1,…,hm

均為r0xn0階矩陣(r0=n0-k0)，稱為子校驗(yàn)矩陣h∞=[hmhm-1…h(huán)1h0

0…]

稱為基本校驗(yàn)矩陣。6/7/202340信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗(yàn)矩陣對于(n0,k0,m)系統(tǒng)卷積碼，子生成矩陣gi與子校驗(yàn)矩陣hi之間有如下關(guān)系： 由上述關(guān)系可容易地得到(n0,k0,m)系統(tǒng)卷積碼的校驗(yàn)矩陣。6/7/202341信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗(yàn)矩陣[舉例]：對前例中的(3,2,2)系統(tǒng)卷積碼，子生成元為：

g(1,1)=100，g(1,2)=000，g(1,3)=101 g(2,1)=000，g(2,2)=100，g(2,3)=110

則： 子校驗(yàn)矩陣為：

h0=[111]h1=[010]h2=[100]

6/7/202342信道編碼系統(tǒng)卷積碼的校驗(yàn)矩陣所以可得(3,2,2)系統(tǒng)卷積碼的校驗(yàn)矩陣為：

111000… 010111000…H∞=100010111000… 000100010111000… ……h(huán)0=[111]h1=[010]h2=[100]5.2卷積碼的矩陣描述與編碼

h0

0… h1h0

0… h2h1h0

0…H∞= …… hmhm-1…h(huán)1h0

0… 0hm…h(huán)2h1h0

0… ……6/7/202343信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼

卷積碼的生成矩陣和校驗(yàn)矩陣都是半無限長矩陣，但在任何(m+1)個碼分組的約束長度內(nèi)，碼元之間的校驗(yàn)關(guān)系都是相同的。 在卷積碼的代數(shù)譯碼中，通常只考慮一個編碼約束長度內(nèi)的碼序列。 因此我們有必要定義卷積碼的初始截短碼，研究一個約束長度內(nèi)的碼元校驗(yàn)關(guān)系。

6/7/202344信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼[定義1]：卷積碼的編碼器初始狀態(tài)為全0時，編碼器輸出碼序列的首m+1段碼分組所構(gòu)成的碼字，稱為卷積碼的初始截短碼字。[定義2]：一卷積碼的所有初始截短碼字的集合，構(gòu)成一個((m+1)n0,(m+1)k0)線性碼，稱其為(n0,k0,m)卷積碼的初始截短碼。初始截短碼具有線性分組碼的所有性質(zhì)。初始截短碼與(n,k)分組碼的主要區(qū)別在于前者的信息位不是連在一起的，而是間隔地分布在每一段碼分組內(nèi)。6/7/202345信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼根據(jù)定義，(n0,k0,m)系統(tǒng)卷積碼初始截短碼的生成矩陣為：

6/7/202346信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼初始截短碼的校驗(yàn)矩陣為：

6/7/202347信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼[舉例]：(3,2,2)系統(tǒng)卷積碼的子生成元為：

g(1,3)=101g(2,3)=110則初始截短碼的生成矩陣和校驗(yàn)矩陣為：

101000001