卷積碼碼 課件

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

為便于理解，仍以(2,1,2)卷積碼為例g∞=[11011100…]=[g0g1g2

0…]稱為(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稱為該碼的子生成元。11/19/202218信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

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

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

(n0,1,m)卷積碼舉例：給定一卷積碼的子生成元為： g(1,1)=10011，g(1,2)=11101判斷該碼的參數(shù)，寫出生成矩陣，給出編碼電路；假設(shè)信息序列m=110110000…，試求出編碼序列C∞11/19/202224信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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]

11/19/202225信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

于是該碼的生成矩陣為： 110101101100… 00110101101100… 0000110101101100… G∞= …00110101101100… …00110101101100… …11/19/202226信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

根據(jù)子生成元可畫出(2,1,4)碼的編碼電路：g(1,1)=10011，g(1,2)=1110111/19/202227信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣已知m=110110000… 由C∞=m∞G∞可得碼序列為： C∞=11100000111111011100… 110101101100… 00110101101100… 0000110101101100… G∞= …00110101101100… …00110101101100… …11/19/202228信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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)11/19/202229信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣每個子生成元均為m+1重向量： g(i,j)=g0(i,j)g1(i,j)…gm(i,j)特別地：對于系統(tǒng)卷積碼，其子生成元有如下特點：11/19/202230信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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階矩陣：11/19/202231信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣特別地：對于系統(tǒng)卷積碼，其子生成矩陣有如下特點： 其中，P0,P1,…,Pm為k0xr0階矩陣

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

參見教材(Page198)11/19/202234信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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∞11/19/202235信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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)=11011/19/202236信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：

其子生成矩陣為:

該碼的生成矩陣為： 101000001000… 011001000000… 000101000001000… G∞= 000011001000000… 000000101000001000… 000000011001000000… ……11/19/202237信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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)=11011/19/202238信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：已知m=10110000… 由C∞=m∞G∞可得碼序列為： C=101110000001000…

11/19/202239信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣(n0,k0,m)系統(tǒng)卷積碼的校驗矩陣 卷積碼是線性碼，生成矩陣和校驗矩陣之間滿足：GHT=0 根據(jù)上述關(guān)系式可由生成矩陣G∞求得H∞ 對于系統(tǒng)卷積碼，G∞和H∞之間有簡單的轉(zhuǎn)換關(guān)系。

11/19/202240信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣11/115.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣(n0,k0,m)卷積碼的校驗矩陣具有如下形式： h0

0… h1h0

0… h2h1h0

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

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

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

0…]

稱為基本校驗矩陣。11/19/202241信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣h0,h15.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣對于(n0,k0,m)系統(tǒng)卷積碼，子生成矩陣gi與子校驗矩陣hi之間有如下關(guān)系： 由上述關(guān)系可容易地得到(n0,k0,m)系統(tǒng)卷積碼的校驗矩陣。11/19/202242信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣11/115.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣[舉例]：對前例中的(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 則： 子校驗矩陣為： h0=[111]h1=[010]h2=[100]

11/19/202243信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣11/11系統(tǒng)卷積碼的校驗矩陣所以可得(3,2,2)系統(tǒng)卷積碼的校驗矩陣為：

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… ……11/19/202244信道編碼系統(tǒng)卷積碼的校驗矩陣5.2卷積碼的矩陣描述與編碼 h05.2卷積碼的矩陣描述與編碼初始截短碼

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

11/19/202245信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼11/11/20225.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)。11/19/202246信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼11/11/20225.2卷積碼的矩陣描述與編碼初始截短碼根據(jù)定義，(n0,k0,m)系統(tǒng)卷積碼初始截短碼的生成矩陣為：

11/19/202247信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼11/11/20225.2卷積碼的矩陣描述與編碼初始截短碼初始截短碼的校驗矩陣為：

11/19/202248信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼11/11/20225.2卷積碼的矩陣描述與編碼初始截短碼[舉例]：(3,2,2)系統(tǒng)卷積碼的子生成元為： g(1,3)=101g(2,3)=110則初始截短碼的生成矩陣和校驗矩陣為： 101000001 011001000 G=000101000 000011001 000000101 000000011 111000000H=

010111000 10001011111/19/202249信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼 11105.2卷積碼的矩陣描述與編碼卷積碼的距離特性卷積碼不同于分組碼，有多種距離定義。最小漢明距離[定義]：(n0,k0,m)卷積碼的最小漢明距離定義為所有第0碼分組不同的初始截短碼字之間的最小距離，記為dm。[定理1]：(n0,k0,m)卷積碼的最小漢明距離等于第0碼分組為非全0的初始截短碼字的最小重量。[定理2]：在(n0,k0,m)卷積碼的校驗矩陣中，若任意小于等于d-1列線性無關(guān)（其中至少有一列在首n0列），且有d列線性相關(guān)，則碼的最小漢明距離為d。11/19/202250信道編碼5.2卷積碼的矩陣描述與編碼卷積碼的距離特性11/11/25.2卷積碼的矩陣描述與編碼卷積碼的距離特性自由距離[定義]：(n0,k0,m)卷積碼的自由距離定義為所有非0半無限長碼序列之間的最小距離。[定理1]：(n0,k0,m)卷積碼的自由距離等于第0碼分組為非全0的半無限長碼序列的最小漢明重量。

卷積碼的自由距離df大于等于最小漢明距離dm通常情況下：非系統(tǒng)碼的df大于系統(tǒng)碼的df。11/19/202251信道編碼5.2卷積碼的矩陣描述與編碼卷積碼的距離特性11/11/25.2卷積碼的矩陣描述與編碼小結(jié)：卷積碼的當前碼分組不僅與當前信息分組有關(guān)，還與前m個信息分組有關(guān)卷積碼由子生成元定義（編碼電路）類似于分組碼，卷積碼也可采用生成矩陣和校驗矩陣描述初始截短碼定義在卷積碼的一個約束長度內(nèi)卷積碼最小漢明距離定義為初始截短碼的最小距離卷積碼的自由距離大于等于其最小漢明距離11/19/202252信道編碼5.2卷積碼的矩陣描述與編碼小結(jié)：11/11/2022525.2卷積碼的矩陣描述與編碼作業(yè)：1、已知一卷積碼的子生成元為： g(1,1)=100,g(1,2)=110,g(1,3)=101

判斷該碼的參數(shù)，寫出其生成矩陣、校驗矩陣，給出編碼電路； 假設(shè)信息序列m=1011000…，試求出編碼序列C∞； 給出該碼的初始截短碼的生成矩陣與校驗矩陣。11/19/202253信道編碼5.2卷積碼的矩陣描述與編碼作業(yè)：11/11/202253通信工程系移動通信教研室信道編碼信道編碼第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼11/19/202255信道編碼第五章卷積碼5.1卷積碼的基本概念11/11/202第五章卷積碼重點掌握：卷積碼的基本概念與編碼方法卷積碼的格圖描述重點理解：卷積碼的維特比譯碼算法11/19/202256信道編碼第五章卷積碼重點掌握：11/11/20223信道編碼第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼11/19/202257信道編碼第五章卷積碼5.1卷積碼的基本概念11/11/2025.1卷積碼的基本概念卷積碼的提出與發(fā)展1954年，埃里斯（Elias）提出卷積碼的概念，它是完全不同于線性分組碼的一個碼類。1961年，提出卷積碼的序列譯碼方法。1963年，梅西（Massey）提出了卷積碼的代數(shù)譯碼方法—門限譯碼。1967年，維特比（Vitebi）提出了卷積碼的最大似然譯碼方法，稱為維特比算法。直到現(xiàn)在，仍是應(yīng)用最為廣泛的譯碼算法。11/19/202258信道編碼5.1卷積碼的基本概念卷積碼的提出與發(fā)展11/11/2025.1卷積碼的基本概念一個簡單的卷積碼編碼例子初始狀態(tài)：00設(shè)輸入m=101100……則輸出與輸入的關(guān)系為：輸入：1狀態(tài)：00輸出：11010011010011010011100011100000………碼序列碼分組碼序列編碼存儲信息分組11/19/202259信道編碼5.1卷積碼的基本概念一個簡單的卷積碼編碼例子輸入：1015.1卷積碼的基本概念說明：可以將卷積碼的編碼器看作一個由k0個輸入端和n0個輸出端組成的時序網(wǎng)絡(luò)，即每輸入k0個信息元，輸出n0個碼元組成的碼分組(子碼)。例子中k0=1,n0=2；編碼器某個時刻的輸出不僅與該時刻編碼器的輸入有關(guān)，而且與以前若干時刻(由編碼存儲單元的個數(shù)決定)的輸入編碼器的信息有關(guān)。卷積碼的碼字（碼序列）可以看作是由無限多個碼分組組成的碼向量，即碼字是一個無限維向量。11/19/202260信道編碼5.1卷積碼的基本概念說明：11/11/20227信道編碼5.1卷積碼的基本概念幾個基本概念信息分組與碼分組(子碼)：k0，n0k0:每個時刻輸入編碼器信息組中的信息元個數(shù)；n0:每個時刻編碼器輸出一個子碼中碼元的個數(shù)。系統(tǒng)碼與非系統(tǒng)碼： 如果在n0位長的碼分組中，前k0位是原輸入的信息元，則該卷積碼為系統(tǒng)碼，否則稱為非系統(tǒng)碼。編碼效率：R=k0/n011/19/202261信道編碼5.1卷積碼的基本概念幾個基本概念11/11/20228信5.1卷積碼的基本概念幾個基本概念編碼存儲m：表示編碼過程中，輸入的信息組在編碼器中需要存貯的單位時間。前面例子中，m=2編碼約束度N=m+1：表示編碼過程中相互約束的碼分組個數(shù)。編碼約束長度n0N：表示編碼過程中相互約束的碼元數(shù)目。 參數(shù)m,N,k0,n0反映了編碼器的復雜度 卷積碼通常記為：(n0,k0,m)卷積碼或N(n0,k0)11/19/202262信道編碼5.1卷積碼的基本概念幾個基本概念11/11/20229信5.1卷積碼的基本概念卷積碼的特點：當前碼分組輸出不僅與當前信息分組輸入有關(guān)，還與前面m個信息分組有關(guān)。在相同碼率、相同譯碼復雜性條件下，卷積碼的性能要好于分組碼。卷積碼仍是線性碼，滿足線性疊加關(guān)系。通常情況下，非系統(tǒng)碼的性能好于系統(tǒng)碼。尚沒有完善的數(shù)學工具有效地分析其結(jié)構(gòu)和性能，須借助計算機搜索來尋找好碼。11/19/202263信道編碼5.1卷積碼的基本概念卷積碼的特點：11/11/20221第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼11/19/202264信道編碼第五章卷積碼5.1卷積碼的基本概念11/11/2025.2卷積碼的矩陣描述與編碼卷積碼的特點：當前碼分組輸出不僅與當前信息分組輸入有關(guān)，還與前面m個信息分組有關(guān)。在相同碼率、相同譯碼復雜性條件下，卷積碼的性能要好于分組碼。卷積碼仍是線性碼，滿足線性疊加關(guān)系。通常情況下，非系統(tǒng)碼的性能好于系統(tǒng)碼。尚沒有完善的數(shù)學工具有效地分析其結(jié)構(gòu)和性能，須借助計算機搜索來尋找好碼。11/19/202265信道編碼5.2卷積碼的矩陣描述與編碼卷積碼的特點：11/11/205.2卷積碼的矩陣描述與編碼卷積碼的生成矩陣與編碼系統(tǒng)卷積碼的校驗矩陣初始截短碼卷積碼的距離特性11/19/202266信道編碼5.2卷積碼的矩陣描述與編碼卷積碼的生成矩陣與編碼11/15.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…)11/19/202267信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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…)11/19/202268信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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… ………11/19/202269信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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∞g0g1g211/19/202270信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

為便于理解，仍以(2,1,2)卷積碼為例g∞=[11011100…]=[g0g1g2

0…]稱為(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稱為該碼的子生成元。11/19/202271信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

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

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

(n0,1,m)卷積碼舉例：給定一卷積碼的子生成元為： g(1,1)=10011，g(1,2)=11101判斷該碼的參數(shù)，寫出生成矩陣，給出編碼電路；假設(shè)信息序列m=110110000…，試求出編碼序列C∞11/19/202277信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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]

11/19/202278信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

于是該碼的生成矩陣為： 110101101100… 00110101101100… 0000110101101100… G∞= …00110101101100… …00110101101100… …11/19/202279信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣

根據(jù)子生成元可畫出(2,1,4)碼的編碼電路：g(1,1)=10011，g(1,2)=1110111/19/202280信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣已知m=110110000… 由C∞=m∞G∞可得碼序列為： C∞=11100000111111011100… 110101101100… 00110101101100… 0000110101101100… G∞= …00110101101100… …00110101101100… …11/19/202281信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩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)11/19/202282信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣每個子生成元均為m+1重向量： g(i,j)=g0(i,j)g1(i,j)…gm(i,j)特別地：對于系統(tǒng)卷積碼，其子生成元有如下特點：11/19/202283信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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階矩陣：11/19/202284信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣特別地：對于系統(tǒng)卷積碼，其子生成矩陣有如下特點： 其中，P0,P1,…,Pm為k0xr0階矩陣

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

參見教材(Page198)11/19/202287信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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∞11/19/202288信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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)=11011/19/202289信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：

其子生成矩陣為:

該碼的生成矩陣為： 101000001000… 011001000000… 000101000001000… G∞= 000011001000000… 000000101000001000… 000000011001000000… ……11/19/202290信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成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)=11011/19/202291信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：已知m=10110000… 由C∞=m∞G∞可得碼序列為： C=101110000001000…

11/19/202292信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣(n0,k0,m)系統(tǒng)卷積碼的校驗矩陣 卷積碼是線性碼，生成矩陣和校驗矩陣之間滿足：GHT=0 根據(jù)上述關(guān)系式可由生成矩陣G∞求得H∞ 對于系統(tǒng)卷積碼，G∞和H∞之間有簡單的轉(zhuǎn)換關(guān)系。

11/19/202293信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣11/115.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣(n0,k0,m)卷積碼的校驗矩陣具有如下形式： h0

0… h1h0

0… h2h1h0

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

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

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

0…]

稱為基本校驗矩陣。11/19/202294信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣h0,h15.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣對于(n0,k0,m)系統(tǒng)卷積碼，子生成矩陣gi與子校驗矩陣hi之間有如下關(guān)系： 由上述關(guān)系可容易地得到(n0,k0,m)系統(tǒng)卷積碼的校驗矩陣。11/19/202295信道編碼5.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣11/115.2卷積碼的矩陣描述與編碼系統(tǒng)卷積碼的校驗矩陣[舉例]：對前例中的(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 則： 子校驗矩陣為： h0=[111]h1=[010]h2=[100]

11/19/202296信道編碼5.2卷積碼