通信工程系移動通信教研室信道編碼第五章 卷積碼9/21/20232信道編碼卷積碼的基本概念卷積碼的矩陣描述與編碼卷積碼的狀態(tài)圖與格圖描述卷積碼的概率譯碼第五章 卷積碼9/21/20233信道編碼重點掌握：卷積碼的基本概念與編碼方法卷積碼的格圖描述重點理解：卷積碼的維特比譯碼算法第五章 卷積碼9/23/20234信道編碼卷積碼的基本概念卷積碼的矩陣描述與編碼卷積碼的狀態(tài)圖與格圖描述卷積碼的概率譯碼5.1卷積碼的基本概念9/23/20235信道編碼卷積碼的提出與發(fā)展1954年，埃里斯（Elias）提出卷積碼的概念，它是完全不同于線性分組碼的一個碼類。1961年，提出卷積碼的序列譯碼方法。1963年，梅西（Massey）提出了卷積碼的代數(shù)譯碼方法—門限譯碼。1967年，維特比（Vitebi）提出了卷積碼的最大似然譯碼方法，稱為維特比算法。直到現(xiàn)在，仍是應用最為廣泛的譯碼算法。5.1卷積碼的基本概念一個簡單的卷積碼編碼例子初始狀態(tài)：00設輸入m=101100……則輸出與輸入的關系為：列9/23/20236信道編碼輸入：1011000…碼序狀態(tài)碼：分0組0100110110100…輸出：11010010101100…編碼碼序存列儲信息分組5.1卷積碼的基本概念9/23/20237信道編碼說明：可以將卷積碼的編碼器看作一個由k0個輸入端和n0個輸出端組成的時序網(wǎng)絡，即每輸入k0個信息元，輸出n0個碼元組成的碼分組(子碼)。例子中k0=1,n0=2；編碼器某個時刻的輸出不僅與該時刻編碼器的輸入有關，而且與以前若干時刻(由編碼存儲單元的個數(shù)決定)的輸

入編碼器的信息有關。卷積碼的碼字（碼序列）可以看作是由無限多個碼分組組成的碼向量，即碼字是一個無限維向量。5.1卷積碼的基本概念9/23/20238信道編碼幾個基本概念信息分組與碼分組(子碼)：k0，n0k0:每個時刻輸入編碼器信息組中的信息元個數(shù)；n0

:每個時刻編碼器輸出一個子碼中碼元的個數(shù)。系統(tǒng)碼與非系統(tǒng)碼：如果在n0位長的碼分組中，前k0位是原輸入的信息元，則該卷積碼為系統(tǒng)碼，否則稱為非系統(tǒng)碼。編碼效率：R=k0/n05.1卷積碼的基本概念9/23/20239信道編碼幾個基本概念編碼存儲m

：表示編碼過程中，輸入的信息組在編碼器中需要存貯的單位時間。前面例子中，m=2編碼約束度N=m+1

：表示編碼過程中相互約束的碼分組個數(shù)。編碼約束長度n0N：表示編碼過程中相互約束的碼元數(shù)目。參數(shù)m,N,k0,n0反映了編碼器的復雜度卷積碼通常記為：(n0,k0,m)卷積碼或N(n0,k0)5.1卷積碼的基本概念9/23/202310信道編碼卷積碼的特點：當前碼分組輸出不僅與當前信息分組輸入有關，還與前面m個信息分組有關。在相同碼率、相同譯碼復雜性條件下，卷積碼的性能要好于分組碼。卷積碼仍是線性碼，滿足線性疊加關系。通常情況下，非系統(tǒng)碼的性能好于系統(tǒng)碼。尚沒有完善的數(shù)學工具有效地分析其結構和性能，須借助計算機搜索來尋找好碼。第五章 卷積碼9/23/202311信道編碼卷積碼的基本概念卷積碼的矩陣描述與編碼卷積碼的狀態(tài)圖與格圖描述卷積碼的概率譯碼5.2卷積碼的矩陣描述與編碼9/23/202312信道編碼卷積碼的特點：當前碼分組輸出不僅與當前信息分組輸入有關，還與前面m個信息分組有關。在相同碼率、相同譯碼復雜性條件下，卷積碼的性能要好于分組碼。卷積碼仍是線性碼，滿足線性疊加關系。通常情況下，非系統(tǒng)碼的性能好于系統(tǒng)碼。尚沒有完善的數(shù)學工具有效地分析其結構和性能，須借助計算機搜索來尋找好碼。5.2卷積碼的矩陣描述與編碼9/23/202313信道編碼卷積碼的生成矩陣與編碼系統(tǒng)卷積碼的校驗矩陣初始截短碼卷積碼的距離特性5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣為便于理解，仍以(2,1,2)卷積碼為例設：m=(m0,m1,m2,…)C=(C0,C1,C2,…)，其中Ci=(ci

,ci

)(1)

(2)若輸入信息序列和編碼器相應輸出序列為：m’

=(100…)m’’=(0100..)m’’’=(0010...)C’

=(11

01

11…)C’’=(00

11

01

11…)C’’’=(00

00

11

01

11…)9/23/202314信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣為便于理解，仍以(2,1,2)卷積碼為例設：m=(m0,m1,m2,…)C=(C0,C1,C2,…)，其中Ci=(ci

,ci

)(1)

(2)若輸入信息序列分別為m=m’+m’’+m’’’

=(100…)+(0100..)+(0010...)=(1110…)編碼器相應輸出的碼序列為：C=C’+C’’+C’’=(11

01

11…)+(00

11

01

11…)+(00

00

11

01

11…)=(11

10

01

10

11…)9/23/202315信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣為便于理解，仍以(2,1,2)卷積碼為例設：m=(m0,m1,m2,…)C=(C0,C1,C2,…)，其中Ci=(ci

,ci

)(1)

(2)若輸入信息序列分別為m=m’+m’’+m’’’

=(100…)+(0100..)+(0010...)=(1110…)編碼器相應輸出的碼序列為：C=mG∞=(1110…) 11

01

11…00

11

01

11…00

00

11

01

11…169/23/2023

信道編碼

…

…

…5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣為便于理解，仍以(2,1,2)卷積碼為例設：m=(m0,m1,m2,…)0

1

2C=(C

,C

,C

,…)，其中C

=(ci

i(1)

(2),c

)ig∞g9/23/202317信道編碼(2,10,2)卷積碼的生成矩陣為：11

01

11

00

00

…G∞=

00

11

01

11

00

00

…00

00

11

01

11

00

00

……

…g1g25.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣為便于理解，仍以(2,1,2)卷積碼為例g∞=[11011100…]=[g0

g1

g2

0…]稱為(2,1,2)卷積碼的基本生成矩陣。其中：g0=[11],g1=[01],g2=[11]均為1x2

(k0xn0)階矩陣，稱為該碼的子生成矩陣。子生成矩陣的行構成的向量,稱為該碼的生成元。g(1)=11

01

11生成元g(1)=11

01

11中每一段對應位構成的子向量

g(1,1)=101,g(1,2)=111稱為該碼的子生成元。9/23/202318信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣為便于理解，仍以(2,1,2)卷積碼為例子生成元的物理含義：子生成元g(1,

j)表示了碼分組中第j個碼元與參與運算的共m+1個信息元之間的校驗關系，它對應于編碼器的抽頭系數(shù)。生成元的物理含義：生成元g(1)表示了碼分組與m+1個信息元之間的校驗關系。9/23/202319信道編碼5.2卷積碼的矩陣描述與編碼9/23/202320信道編碼(n0,1,m)卷積碼的生成矩陣

對于一般的(n0,1,m)卷積碼：子生成元一共有n0個，每個子生成元都是一個m+1重向量，記為：g(1,1)=[g0

,1)

g1

,1)

…

gm(1,1)](1

(1g(1,2)=[g0

,2)

g1

,2)

…

gm(1,2)](1

(1……g(1,n0)=[g0

,n0)

g1

,n0)

…

gm(1,n0)](1

(1g0,g1,…,gm為子生成矩陣5.2卷積碼的矩陣描述與編碼9/23/202321信道編碼(n0,1,m)卷積碼的生成矩陣它們對應編碼器的n0組抽頭系數(shù)特別地：對于系統(tǒng)卷積碼，其第一個子生成元為g(1,1)=[1

0

0…0]。對于一般的(n0,1,m)卷積碼：生成元僅有一個，可以由子生成元得到：g(1)=[g0

g0

…g0

g1

g1

…(1,1)

(1,2)

(1,n0)

(1,1)

(1,2)0(1,n

)g …

g1

mm

m(1,1)g

(1,2)…g

(1,n0)]子生成矩陣gi為：i

ig

=

[g

gi(1,1)

(1,2)i0(1,n

)…g

]5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣因此可得到(n0,1,m)卷積碼的基本生成矩陣：g∞=[g0

g1

…

gm

0

…](n0,1,m)卷積碼的生成矩陣為：9/23/202322信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的編碼原理對于線性碼均有C=mG，因此對卷積碼有：C∞=m∞G∞(n0,1,m)卷積碼的編碼可由如下電路實現(xiàn)：9/23/202323信道編碼5.2卷積碼的矩陣描述與編碼9/23/202324信道編碼(n0,1,m)卷積碼的生成矩陣(n0,1,m)卷積碼舉例：給定一卷積碼的子生成元為：g(1,1)=10011，g(1,2)=11101判斷該碼的參數(shù)，寫出生成矩陣，給出編碼電路；假設信息序列m=110110000…，試求出編碼序列C∞5.2卷積碼的矩陣描述與編碼9/23/202325信道編碼(n0,1,m)卷積碼的生成矩陣由子生成元g(1,1)=10011，g(1,2)=11101可得：m=4，n0=2，k0=1該碼為(2,1,4)非系統(tǒng)卷積碼其生成元為：g(1)=11

01

01

10

11子生成矩陣為：g0=[11],g1=[01],g2=[01],g3=[10],g4=[11]5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣于是該碼的生成矩陣為：11

01

01

10

11

00

…00

11

01

01

10

11

00

…00

00

11

01

01

10

11

00

…G∞=……00

11

01

01

10

11

00

…00

11

01

01

10

11

00

……9/23/202326信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣根據(jù)子生成元可畫出(2,1,4)碼的編碼電路：g(1,1)=10011，g(1,2)=111019/23/202327信道編碼5.2卷積碼的矩陣描述與編碼(n0,1,m)卷積碼的生成矩陣已知m=110110000…由C∞=m∞G∞可得碼序列為：C∞

=11

10

00

00

11

11

11

01

11

00

…11

01

01

10

11

00

…00

11

01

01

10

11

00

…00

00

11

01

01

10

11

00

…G∞=……00

11

01

01

10

11

00

…00

11

01

01

10

11

00

……9/23/202328信道編碼5.2卷積碼的矩陣描述與編碼9/23/202329信道編碼(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

)5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣每個子生成元均為m+1重向量：g(i,

j)=

g0

,

j)

g1

,

j)

…

gm(i,

j)(i

(i特別地：對于系統(tǒng)卷積碼，其子生成元有如下特點：9/23/202330信道編碼5.2卷積碼的矩陣描述與編碼9/23/202331信道編碼(n0,k0,m)卷積碼的生成矩陣生成元：一共有k0個，記為：g(1),g(2),…,g(k0)每個生成元均為n0x(m+1)重向量：g(i)=g0

,1)g0

,2)…g0

,n0)…gm(i,1)…gm(i,n0)(i

(i

(i其中：gt

：子生成元g

的第t位(i,j)

(i,j)子生成矩陣：一共有m+1個，g0,g1,…,gm每個子生成矩陣均為k0xn0階矩陣：5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣特別地：對于系統(tǒng)卷積碼，其子生成矩陣有如下特點：其中，P0,P1,…,Pm為k0xr0階矩陣9/23/202332信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼的生成矩陣9/23/202333信道編碼5.2卷積碼的矩陣描述與編碼信道編碼9/23/202334(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼的編碼原理根據(jù)子生成元可構造(n0,k0,m)卷積碼的編碼電路。參見教材(Page

198)5.2卷積碼的矩陣描述與編碼信道編碼9/23/202335(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：給定一卷積碼的子生成元為：

g(1,1)=100，g(1,2)=000，g(1,3)=101g(2,1)=000，g(2,2)=100，g(2,3)=110判斷該碼的參數(shù)，寫出生成矩陣，給出編碼電路；假設信息序列m=10110000…，試求出編碼序列C∞5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：由子生成元可得：m=2，n0=3，k0=2其生成元為：g(1)

=101000001g(2)

=011001000該碼為(3,2,2)系統(tǒng)卷積碼g(1,1)=100

g(1,2)=000

g(1,3)=101g(2,1)=000

g(2,2)=100

g(2,3)=110信道編碼9/23/2023365.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：其子生成矩陣為:該碼的生成矩陣為：101

000

001

000

…011

001

000

000

…000

101

000

001

000

…G∞= 000

011

001

000

000

…000

000

101

000

001

000

…000

000

011

001

000

000

………9/23/202337信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：根據(jù)子生成元可畫出(3,2,2)碼的編碼電路：g(1,1)=100

g(1,2)=000

g(1,3)=101g(2,1)=000

g(2,2)=100

g(2,3)=1109/23/202338信道編碼5.2卷積碼的矩陣描述與編碼(n0,k0,m)卷積碼的生成矩陣(n0,k0,m)卷積碼舉例：已知m=10

11

00

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

C=101

110

000

001

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

0

…h(huán)1

h0

0

…h(huán)2

h1

h0

0

…H∞= …

…h(huán)m

hm-1

…

h1

h0

0

…0 hm

… h2

h1

h0

0

……

…0

1

mh,h,…,h

均為0

0

0

0

0r

xn

階矩陣(r=n-k)，稱為子校驗矩陣1

0h∞

=

[hm

hm-1

…

h

h

0

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

g(1,1)=100，g(1,2)=000，g(1,3)=101g(2,1)=000，g(2,2)=100，g(2,3)=110則：子校驗矩陣為：h0=[111] h1=[01

0] h2=[10

0]9/23/202343信道編碼系統(tǒng)卷積碼的校驗矩陣所以可得(3,2,2)系統(tǒng)卷積碼的校驗矩陣為：111

000

…010

111

000

…H∞

=

100

010

111

000

…000

100

010

111

000

……

…h(huán)0=[11

1]h1=[01

0]h2=[10

0]5.2卷積碼的矩陣描述與編碼h0

0

…h(huán)1

h0

0

…h(huán)2

h1

h0

0

…H∞= …

…h(huán)m

hm-1

…

h1

h0

0

…m

2

1

00

h

…

h

h

h

0

……

…9/23/202344信道編碼5.2卷積碼的矩陣描述與編碼9/23/202345信道編碼初始截短碼卷積碼的生成矩陣和校驗矩陣都是半無限長矩陣，但在任何(m+1)個碼分組的約束長度內(nèi)，碼元之間的校驗關系都是相同的。在卷積碼的代數(shù)譯碼中，通常只考慮一個編碼約束長度內(nèi)的碼序列。因此我們有必要定義卷積碼的初始截短碼，研究一個約束長度內(nèi)的碼元校驗關系。5.2卷積碼的矩陣描述與編碼9/23/202346信道編碼初始截短碼[定義1]：卷積碼的編碼器初始狀態(tài)為全0時，編碼器輸出碼序列的首m+1段碼分組所構成的碼字，稱為卷積碼的初始截短碼字。[定義2]：一卷積碼的所有初始截短碼字的集合，構成一個((m+1)n0,(m+1)k0)線性碼，稱其為(n0,k0,m)卷積碼的初始截短碼。初始截短碼具有線性分組碼的所有性質(zhì)。初始截短碼與(n,k)分組碼的主要區(qū)別在于前者的信息位不是連在一起的，而是間隔地分布在每一段碼分組內(nèi)。5.2卷積碼的矩陣描述與編碼初始截短碼根據(jù)定義，(n0,k0,m)系統(tǒng)卷積碼初始截短碼的生成矩陣為：9/23/202347信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼初始截短碼的校驗矩陣為：9/23/202348信道編碼5.2卷積碼的矩陣描述與編碼初始截短碼[舉例]：(3,2,2)系統(tǒng)卷積碼的子生成元為：g(1,3)=101

g(2,3)=110則初始截短碼的生成矩陣和校驗矩陣為：G=10

1 00