信息論與編碼-第17講-信道編碼-卷積碼

第1頁(yè)2024/4/14第10章卷積碼10.1卷積碼的基本概念10.2卷積碼的編碼10.3卷積碼的譯碼10.4卷積碼的圖描述10.5維特比譯碼的基本原理10.6軟判決維特比譯碼10.7維特比譯碼的應(yīng)用ElectronicsEngineeringDepartment,XXXXXxxXxxx第2頁(yè)2024/4/1410.1卷積碼的基本概念

卷積碼（連環(huán)碼）首先由麻省理工學(xué)院于1955年提出。卷積碼與分組碼的不同之處：在任意給定單元時(shí)刻，編碼器輸出的

n

個(gè)碼元中，每一個(gè)碼元不僅和此時(shí)刻輸入的k

個(gè)信息元有關(guān)，還與前連續(xù)m

個(gè)時(shí)刻輸入的信息元有關(guān)。卷積碼常用(n,k,m)表示。

n—子碼，k—信息位，m—編碼存儲(chǔ)在同樣的編碼效率R下，卷積碼的性能優(yōu)于分組碼，至少不低于分組碼。第3頁(yè)2024/4/1410.1卷積碼的基本概念

卷積碼的譯碼方法

代數(shù)譯碼：門限譯碼。譯碼延時(shí)是固定的。概率譯碼：序列譯碼：譯碼延時(shí)是隨機(jī)的。

維特比譯碼：譯碼延時(shí)是固定的。第4頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度(2)系統(tǒng)碼形式的卷積碼第5頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼第6頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼待編碼的信息序列m：在對(duì)m

進(jìn)行編碼之前，先將它每k個(gè)碼元分成一組，在每單元時(shí)刻內(nèi)，k個(gè)碼元串行輸入到編碼器；移位寄存器組：

(m+1)個(gè)，每個(gè)移位寄存器組內(nèi)有k級(jí)寄存器；常數(shù)乘法器g(i,j)：i=1,2,…,k；j=1,2,…,n，共有(m+1)?n

個(gè)，當(dāng)g(i,j)=1時(shí)，常數(shù)乘法器為一條直通的連接線；當(dāng)g(i,j)=0時(shí)，連接線斷開。每一個(gè)碼元都是k?(m+1)個(gè)數(shù)據(jù)組合，每一個(gè)碼字需用n?k?(m+1)

個(gè)系數(shù)才能描述；第7頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼開關(guān)K在每一節(jié)拍中移動(dòng)n次，每一節(jié)拍輸入k個(gè)信息元而輸出n個(gè)碼元。信息序列m=[m0(1)m1(1)m2(1)…]；

ml(1)表示第l個(gè)時(shí)刻的第k=1個(gè)信息元；第8頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼卷積碼的生成序列g(shù)(1,1)=[g0(1,1)g1(1,1)g2(1,1)g3(1,1)]=[1011]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)g3(1,2)]=[1111]

g(1,1)表明：任一時(shí)刻l時(shí)，輸出端1的碼元Cl(1)是由此時(shí)刻l輸入的信息元ml(1)與前兩個(gè)時(shí)刻輸入的信息元ml－2(1)以及前三個(gè)時(shí)刻

ml－3(1)輸入的信息元模2加后的和；

g(1,2)表明：Cl(2)是由ml(1)、ml－1(1)、ml－2(1)和ml－3(1)的模2和。第9頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼卷積碼的生成序列

生成序列：給定g(i,j)后，就可以生成編碼器輸出的碼元。稱g(1,1)和g(1,2)為(2,1,3)卷積碼的生成序列。第l個(gè)時(shí)刻的編碼器輸出為：第10頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼卷積碼的生成序列

卷積碼名稱的由來(lái)：任一時(shí)刻編碼器的輸出可以由信息元與生成序列的離散卷積運(yùn)算求出。第11頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼設(shè)m

=[m0(1)m1(1)m2(1)m3(1)]=[1011]，則編碼器兩個(gè)輸出端的序列分別是：

子碼：在任一單元時(shí)刻，送入編碼器一個(gè)信息元（k=1），編碼器輸出由2個(gè)(n=2)碼元組成的一個(gè)碼組，稱之為子碼。第12頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-1]：(2,1,3)碼每個(gè)子碼中的碼元不僅與此時(shí)此刻的信息元有關(guān)，而且還與前m個(gè)(m=3)時(shí)刻的信息元有關(guān)。

編碼存儲(chǔ)：m（本例

m=3）

約束度：N=m+1，編碼過(guò)程中相互約束的子碼數(shù)。（本例N=4）

編碼約束長(zhǎng)度：N

n，編碼過(guò)程中相互約束的碼元數(shù)。（本例N

n=8）

非系統(tǒng)碼：在碼序列C

中的每個(gè)子碼不是系統(tǒng)碼字結(jié)構(gòu)。（本例是非系統(tǒng)碼）第13頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-2]：(3,2,1)碼

n=3,k=2,m=1；它的任一子碼有3個(gè)碼元。每個(gè)碼元由此時(shí)此刻的2個(gè)信息元和前一個(gè)時(shí)刻進(jìn)入編碼器的2個(gè)信息元模2運(yùn)算和求出。這些信息元參加模2運(yùn)算的規(guī)則由[n

k]=3×2=6

個(gè)生成序列{[n

k

(m+1)]=3×2×2=12個(gè)系數(shù)}所確定，每個(gè)生成序列含有2個(gè)元素。第14頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-2]：(3,2,1)碼這6個(gè)輸出序列是：g(1,1)=[g0(1,1)

g1(1,1)]=[11]g(1,2)=[g0(1,2)

g1(1,2)]=[01]g(1,3)=[g0(1,3)

g1(1,3)]=[11]g(2,1)=[g0(2,1)

g1(2,1)]=[01]g(2,2)=[g0(2,2)

g1(2,2)]=[10]

g(2,3)=[g0(2,3)

g1(2,3)]=[10](10-3)第15頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-2]：(3,2,1)碼若待編碼的信息序列：m=[m0(1)m0(2)m1(1)m1(2)…

ml(1)ml(2)…]

則碼序列C中的任一子碼為：第16頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-2]：(3,2,1)碼

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

g1(1,1)]=[11]g(2,1)=[g0(2,1)

g1(2,1)]=[01]

g(1,2)=[g0(1,2)

g1(1,2)]=[01]g(2,2)=[g0(2,2)

g1(2,2)]=[10]

g(1,3)=[g0(1,3)

g1(1,3)]=[11]

g(2,3)=[g0(2,3)

g1(2,3)]=[10]第17頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度[例10-2]：(3,2,1)碼每個(gè)時(shí)刻單元輸入編碼器k=2個(gè)信息元，它們與前一個(gè)時(shí)刻進(jìn)入編碼器的2個(gè)信息元按式(10-4)所確定的卷積關(guān)系進(jìn)行運(yùn)算后，在輸出端1、2、3分別得到該時(shí)刻子碼中的3個(gè)碼元。編碼器由N=2個(gè)移位寄存器組和模2加法器構(gòu)成，每個(gè)移位寄存器組含有k=2級(jí)移位寄存器，每級(jí)移位寄存器的輸出按式(10-3)的規(guī)則引出后進(jìn)行模2加的運(yùn)算。本例也是非系統(tǒng)碼形式的卷積碼。第18頁(yè)2024/4/1410.1卷積碼的基本概念(1)卷積碼的生成序列、約束度和約束長(zhǎng)度推論：(n,k,m)碼完全由(n

k)個(gè)生成序列所生成，每個(gè)生成序列中含有(N=m+1)

個(gè)元素。

碼序列：C=[C0(1)C0(2)…C0(n)C1(1)C1(2)…C1(n)…Cl(1)Cl(2)…Cl(n)…]

待編碼的信息序列：m=[m0(1)m0(2)…m0(k)m1(1)m1(2)…m1(k)…ml(1)ml(2)…ml(k)…]

任一子碼：可按如下卷積關(guān)系求出：第19頁(yè)2024/4/1410.1卷積碼的基本概念(2)系統(tǒng)碼形式的卷積碼系統(tǒng)卷積碼：是卷積碼的一類。它的碼序列中任一子碼Cl，也是有n個(gè)碼元，其前k位與待編碼信息序列中的第l信息組ml(i)相同，而后(n－k)

位監(jiān)督元由生成序列生成；每個(gè)碼中的前k位就是此時(shí)刻待編碼的k位信息元，所以在生成序列g(shù)(i,j)中有(k

k)

個(gè)生成序列是固定的，即：第20頁(yè)2024/4/1410.1卷積碼的基本概念(2)系統(tǒng)碼形式的卷積碼只有k

(n－k)個(gè)生成序列需要給定，以便確定每個(gè)子碼中(n－k)個(gè)監(jiān)督元。第21頁(yè)2024/4/1410.1卷積碼的基本概念(2)系統(tǒng)碼形式的卷積碼任一子碼由下式計(jì)算：上式表明：在約束長(zhǎng)度N內(nèi)，每個(gè)子碼中的(n－k)個(gè)監(jiān)督元與信息元的卷積關(guān)系。第22頁(yè)2024/4/1410.1卷積碼的基本概念(2)系統(tǒng)碼形式的卷積碼[例10-3]：(3,1,2)系統(tǒng)卷積碼g(1,1)=[g0(1,1)

g1(1,1)

g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)

g2(1,2)]=[110]g(1,3)=[g0(1,3)

g1(1,3)

g2(1,3)]=[101]第23頁(yè)2024/4/1410.1卷積碼的基本概念(2)系統(tǒng)碼形式的卷積碼[例10-3]：(3,1,2)系統(tǒng)卷積碼g(1,1)=[g0(1,1)

g1(1,1)

g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)

g2(1,2)]=[110]g(1,3)=[g0(1,3)

g1(1,3)

g2(1,3)]=[101]

任一時(shí)刻子碼為：第24頁(yè)2024/4/14(2)系統(tǒng)碼形式的卷積碼[例10-4]：(3,2,2)系統(tǒng)卷積碼g(1,1)=[g0(1,1)

g1(1,1)

g2(1,1)]=[100]g(1,2)=[g0(1,2)

g1(1,2)

g2(1,2)]=[000]g(1,3)=[g0(1,3)

g1(1,3)

g2(1,3)]=[101]g(2,1)=[g0(2,1)

g1(2,1)

g2(2,1)]=[000]g(2,2)=[g0(2,2)

g1(2,2)

g2(2,2)]=[100]g(2,3)=[g0(2,3)

g1(2,3)

g2(2,3)]=[110]10.1卷積碼的基本概念第25頁(yè)2024/4/14(2)系統(tǒng)碼形式的卷積碼[例10-4]：(3,2,2)系統(tǒng)卷積碼該碼的任一子碼Cl中前兩位與ml(1)、ml(2)相同，后一位的監(jiān)督元由式(10-6)確定，即：10.1卷積碼的基本概念第26頁(yè)2024/4/14(2)系統(tǒng)碼形式的卷積碼[例10.1.4]：(3,2,2)系統(tǒng)卷積碼g(1,1)=[g0(1,1)

g1(1,1)

g2(1,1)]=[100]g(2,1)=[g0(2,1)

g1(2,1)

g2(2,1)]=[000]g(1,2)=[g0(1,2)

g1(1,2)

g2(1,2)]=[000]g(2,2)=[g0(2,2)

g1(2,2)

g2(2,2)]=[100]g(1,3)=[g0(1,3)

g1(1,3)

g2(1,3)]=[101]g(2,3)=[g0(2,3)

g1(2,3)

g2(2,3)]=[110]10.1卷積碼的基本概念第27頁(yè)2024/4/14(1)串行輸入、串行輸出的編碼電路(2)(n－k)

m級(jí)移位寄存器構(gòu)成的并行編碼電路（Ⅰ型編碼電路）(3)k

m級(jí)移位寄存器編碼電路（Ⅱ型編碼電路）(4)結(jié)論10.2卷積碼的編碼第28頁(yè)2024/4/14(1)串行輸入、串行輸出的編碼電路非系統(tǒng)碼編碼器：根據(jù)式(10-5)構(gòu)造的是非系統(tǒng)編碼器。圖10-5是(n,k,m)非系統(tǒng)卷積碼串行編碼電路。10.2卷積碼的編碼第29頁(yè)2024/4/14(1)串行輸入、串行輸出的編碼電路10.2卷積碼的編碼第30頁(yè)2024/4/14(1)串行輸入、串行輸出的編碼電路系統(tǒng)碼編碼器：根據(jù)式(10-6)構(gòu)造的是系統(tǒng)編碼器；圖10-6是(n,k,m)系統(tǒng)卷積碼串行編碼電路。10.2卷積碼的編碼第31頁(yè)2024/4/14(1)串行輸入、串行輸出的編碼電路10.2卷積碼的編碼第32頁(yè)2024/4/14(4)結(jié)論：以上三種形式電路各有不同的特點(diǎn)在一般的串行通信方式下，用串行編碼電路比較方便，雖然它所需的電路級(jí)數(shù)較多；在并行通信時(shí)，若(n－k)<k，采用Ⅰ型編碼電路較Ⅱ型更為簡(jiǎn)單；否則，應(yīng)采用Ⅱ型編碼電路。10.2卷積碼的編碼第33頁(yè)2024/4/1410.3卷積碼的譯碼(1)卷積碼譯碼的種類：卷積碼的譯碼可分為代數(shù)譯碼和概率譯碼。(2)代數(shù)譯碼：從碼的代數(shù)結(jié)構(gòu)出發(fā)，以一個(gè)約束度的接收序列為單位，對(duì)該接收序列的信息碼組進(jìn)行譯碼。大數(shù)邏輯譯碼是代數(shù)譯碼的主要方法。代數(shù)譯碼中，用矩陣描述比較方便。(3)概率譯碼：從信道的統(tǒng)計(jì)特性出發(fā)，以遠(yuǎn)大于約束度的接收序列為單位，對(duì)信息碼組進(jìn)行最大似然的判決。維特比譯碼和序列譯碼是其最主要的方法。在維特比譯碼中，用網(wǎng)格圖來(lái)描述碼的譯碼更為方便。第34頁(yè)2024/4/1410.4卷積碼的圖描述(1)卷積碼的狀態(tài)(2)卷積碼的狀態(tài)轉(zhuǎn)移圖(3)卷積碼的網(wǎng)格圖第35頁(yè)2024/4/1410.4卷積碼的圖描述(1)卷積碼的狀態(tài)定義：卷積碼編碼器要存儲(chǔ)m段消息，這些消息數(shù)據(jù)既要因新的輸入而改變，又要影響當(dāng)前的編碼輸出，因此稱存儲(chǔ)表達(dá)這些數(shù)據(jù)的參量為卷積編碼器的內(nèi)部狀態(tài)，簡(jiǎn)稱狀態(tài)。第36頁(yè)2024/4/1410.4卷積碼的圖描述(1)卷積碼的狀態(tài)[例]：(2,1,2)碼的狀態(tài)向量為D=(D2,D1)，共有4種狀態(tài)S0,S1,S2,S3，如圖所示。

g(1,1)=[g0(1,1)g1(1,1)g2(1,1)]=[111]

g(1,2)=[g0(1,2)g1(1,2)g2(1,2)]=[101]第37頁(yè)2024/4/1410.4卷積碼的圖描述(1)卷積碼的狀態(tài)[例]：其狀態(tài)轉(zhuǎn)移圖如圖

10-14和圖10-17所示。第38頁(yè)2024/4/1410.4卷積碼的圖描述(1)卷積碼的狀態(tài)[例]：其狀態(tài)轉(zhuǎn)移圖如圖

10-14和圖10-17所示。第39頁(yè)2024/4/1410.4卷積碼的圖描述(2)卷積碼的狀態(tài)轉(zhuǎn)移圖閉合型的狀轉(zhuǎn)移態(tài)圖：直接地描述了卷積編碼器在任一時(shí)刻的工作狀況；開放型的狀態(tài)轉(zhuǎn)移圖：更適合去描述一個(gè)特定輸入序列的編碼過(guò)程。第40頁(yè)2024/4/1410.4卷積碼的圖描述(2)卷積碼的狀態(tài)轉(zhuǎn)移圖[例10-13]：(3,2,1)碼的狀態(tài)向量為D=(D2,

D1)，共有4種狀態(tài)S0,S1,S2,S3，如圖10-15所示。

g(1,1)=[g0(1,1)g1(1,1)]=[11]g(1,2)=[g0(1,2)g1(1,2)]=[01]g(1,3)=[g0(1,3)g1(1,3)]=[11]g(2,1)=[g0(2,1)g1(2,1)]=[01]g(2,2)=[g0(2,2)g1(2,2)]=[10]g(2,3)=[g0(2,3)g1(2,3)]=[10]第41頁(yè)2024/4/1410.4卷積碼的圖描述(2)卷積碼的狀態(tài)轉(zhuǎn)移圖[例10-13]：第42頁(yè)2024/4/1410.4卷積碼的圖描述(2)卷積碼的狀態(tài)轉(zhuǎn)移圖[例10-13]：第43頁(yè)2024/4/1410.4卷積碼的圖描述(3)卷積碼的網(wǎng)格圖狀態(tài)圖不能反映出狀態(tài)轉(zhuǎn)移與時(shí)間的關(guān)系網(wǎng)格圖：將開放型的狀態(tài)轉(zhuǎn)移圖按時(shí)間順序級(jí)聯(lián)形成一個(gè)網(wǎng)格圖。編碼路徑：狀態(tài)序列D在網(wǎng)格圖中形成的一條有向路徑。當(dāng)有向路徑始于全“0”狀態(tài)S0，又終于S0時(shí)，表明此時(shí)編碼器又回到全“0”狀態(tài)，這條始于S0又首次終于S0的路徑是一個(gè)卷積碼碼字。第44頁(yè)2024/4/1410.4卷積碼的圖描述(3)卷積碼的網(wǎng)格圖紅實(shí)線表示m=0時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支；蘭虛線表示m=1時(shí)輸入產(chǎn)生的轉(zhuǎn)移分支。第45頁(yè)2024/4/1410.4卷積碼的圖描述(3)卷積碼的網(wǎng)格圖第46頁(yè)2024/4/1410.5維特比譯碼的基本原理(1)維特比譯碼的度量(2)維特比譯碼和網(wǎng)格圖(3)最大似然譯碼／最小距離譯碼(4)舉例說(shuō)明維特比譯碼工作原理(5)總結(jié)維特比算法的步驟第47頁(yè)2024/4/1410.5維特比譯碼的基本原理(1)維特比譯碼的度量待編碼的信息序列m：m=[m0,m1,…,mL－1]；編碼器輸入序列的總長(zhǎng)度：k(L+m)；編碼器輸出的碼序列C：C=[C0,C1,…,CL+m－1]，其中每個(gè)子碼Ci含有n個(gè)碼元；經(jīng)離散無(wú)記憶信道（DMC）傳輸后，譯碼器接收的序列R：R=[R0,R1,…,RL+m－1]；第48頁(yè)2024/4/1410.5維特比譯碼的基本原理(1)維特比譯碼的度量對(duì)于DMC信道：

碼序列C的路徑度量

M(R/C)：計(jì)算第l時(shí)刻到達(dá)狀態(tài)i的最大似然路徑的相似度—logp(R/C)；

子碼Ci的度量（分支度量）M(Ri/Ci)

：計(jì)算第l時(shí)刻接收子碼Ri相對(duì)于各子碼的相似度—logp(Ri/Ci)。第49頁(yè)2024/4/1410.5維特比譯碼的基本原理(2)維特比譯碼和網(wǎng)格圖在維特比譯碼中，用狀態(tài)圖和網(wǎng)格圖描述碼的譯碼比較方便。

[例]：(2,1,2)碼

g(1,1)=[g0(1,1)g1(1,1)g2(1,1)]=[111]g(1,2)=[g0(1,2)g1(1,2)g2(1,2)]=[101]

圖10-20是(2,1,2)碼的網(wǎng)格圖：它由結(jié)點(diǎn)和分支構(gòu)成。共有8個(gè)結(jié)點(diǎn)（單元時(shí)刻），在圖中的上方以0,1,2,…,7標(biāo)號(hào)，0結(jié)點(diǎn)表示第0個(gè)時(shí)刻。第50頁(yè)2024/4/1410.5維特比譯碼的基本原理(2)維特比譯碼和網(wǎng)格圖編碼器的工作過(guò)程：第51頁(yè)2024/4/1410.5維特比譯碼的基本原理(2)維特比譯碼和網(wǎng)格圖

編碼器的工作過(guò)程：在起始的第0個(gè)到第2個(gè)時(shí)刻內(nèi)，編碼器根據(jù)輸入的信息元不同從S0狀態(tài)向四個(gè)可能的狀態(tài)之一行進(jìn)；本例假定信息序列長(zhǎng)為L(zhǎng)=5個(gè)信息組，最后m個(gè)信息組是全0，所以在網(wǎng)格圖上的最后兩個(gè)時(shí)刻向S0狀態(tài)返回；網(wǎng)格圖上各連續(xù)分支組成了可能的路徑，它們代表了各種可能的碼序列；

由于可能的輸入信息序列有2kL=25=32個(gè)，可能的路徑有32條；每個(gè)分支上的數(shù)字表示輸出的子碼。第52頁(yè)2024/4/1410.5維特比譯碼的基本原理(3)最大似然譯碼/最小距離譯碼譯碼器接收到R

序列后，按最大似然法則力圖尋找編碼器在網(wǎng)格圖上原來(lái)走過(guò)的路徑，也就是尋找具有最大度量的路徑；因此，譯碼器必須計(jì)算max[M(R/Cj)]，j=1,2,…,2kL，對(duì)BSC信道，就是尋找與R

有最小距離的路徑，即計(jì)算和尋找min[d(R,Cj)]。第53頁(yè)2024/4/1410.5維特比譯碼的基本原理(3)最大似然譯碼/最小距離譯碼譯碼的實(shí)現(xiàn)：最大似然譯碼方法只是提供了一個(gè)譯碼準(zhǔn)則，實(shí)現(xiàn)起來(lái)尚有一定困難。因?yàn)樗强紤]了長(zhǎng)度為(L+m)n的接收序列來(lái)譯碼的，這樣的序列可能有2kL條；若實(shí)際接收序列中，L=50，k=2，則可能的路徑有2100條。譯碼器每接收一個(gè)序列R，就要計(jì)算1030個(gè)似然函數(shù)才能做出譯碼判決。若kL再大一些，譯碼器按最大似然譯碼準(zhǔn)則譯碼將是很困難的。第54頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理維特比提出了一種算法：譯碼器不是在網(wǎng)格圖上一次就計(jì)算和比較2kL條路徑，而是接收一段，就計(jì)算、比較一段，從而在每個(gè)狀態(tài)時(shí)，選擇進(jìn)入該狀態(tài)的最可能的分支。維特比譯碼的基本思想：將接收序列R

與網(wǎng)格圖上的路徑逐分支地比較，比較的長(zhǎng)度一般取(5～6)mn，然后留下與R

距離最小的路徑，稱為幸存路徑，而去掉其余可能的路徑，并將這些幸存路徑逐分支地延長(zhǎng)并存儲(chǔ)起來(lái)。幸存路徑的數(shù)目：等于狀態(tài)數(shù)

2km第55頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理以(2,1,2)非系統(tǒng)碼為例說(shuō)明維特比譯碼的基本思想：設(shè)發(fā)送序列為全零序列。維特比譯碼的一次運(yùn)算計(jì)算每個(gè)輸入分支的度量值（分支距離、累加距離）；比較各部分路徑的度量值，選擇一條作為幸存路徑。網(wǎng)格圖中共有2km個(gè)狀態(tài)，因此，維特比譯碼的計(jì)算量與編碼存儲(chǔ)m成指數(shù)關(guān)系變化，所以采用維特比算法譯碼的卷積碼，其m不能選的太大。第56頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理累積路徑值累積路徑值累積路徑值第57頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第58頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第59頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第60頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第61頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第62頁(yè)2024/4/149.6維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第63頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第64頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理第65頁(yè)2024/4/1410.5維特比譯碼的基本原理(4)舉例說(shuō)明維特比譯碼工作原理對(duì)本例，按上述算法進(jìn)行到第11個(gè)分支后，四條路徑的前面分支都合并在一起。所以，只要譯碼深度足夠，就可達(dá)到較低的錯(cuò)誤概率。一般，約為(