第五章-卷積碼碼2課件

第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼8/14/20231信道編碼第五章卷積碼5.1卷積碼的基本概念8/2/202315.3卷積碼的狀態(tài)圖與格圖描述卷積碼的狀態(tài)圖描述用編碼器狀態(tài)及其轉(zhuǎn)移描述卷積碼。[例]：(2,1,2)卷積碼的子生成元為：

g(1,1)=111 g(1,2)=101

其編碼器如圖所示編碼器一共有4個狀態(tài)：00,10,01,11

分別記為：S0,S1,S2,S38/14/20232信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的狀態(tài)圖描述8/2/25.3卷積碼的狀態(tài)圖與格圖描述卷積碼的狀態(tài)圖描述(2,1,2)卷積碼的狀態(tài)轉(zhuǎn)移圖為：一般地：(n0,k0,m)卷積碼共有2mk0個狀態(tài)每個狀態(tài)有2k0個輸入和2k0個輸出8/14/20233信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的狀態(tài)圖描述一般地：(5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的狀態(tài)圖描述卷積碼的狀態(tài)圖只表示編碼狀態(tài)之間的轉(zhuǎn)移關(guān)系，無法表示狀態(tài)轉(zhuǎn)移與時間節(jié)拍的關(guān)系。為了表示狀態(tài)轉(zhuǎn)移與時間節(jié)拍的關(guān)系，我們引入卷積碼的格圖(TrellisDiagram)表示。8/14/20234信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的狀態(tài)圖描述8/2/25.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述[例]：(2,1,2)卷積碼，將狀態(tài)轉(zhuǎn)移圖按時間節(jié)拍展開，如圖所示。8/14/20235信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述8/2/205.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述卷積碼的格圖也稱為籬笆圖。從初始狀態(tài)出發(fā)，格圖上的每一條路經(jīng)都對應(yīng)著一個輸入信息序列所對應(yīng)的編碼序列。給定信息序列，可在格圖上找到一條路經(jīng)，進(jìn)而得到所對應(yīng)的編碼序列。反過來，給定編碼序列，也可在格圖上找到一條路經(jīng)，進(jìn)而得到所對應(yīng)的信息序列。8/14/20236信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述8/2/205.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述例如：(2,1,2)卷積碼，m=101100…8/14/20237信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述8/2/205.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述例如：(2,1,2)碼，C=110101001011…8/14/20238信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述8/2/205.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述對于(n0,k0,m)卷積碼： 格圖一共有2mk0個狀態(tài) 每個狀態(tài)有2k0個輸入分支和2k0個輸出分支 格圖從第m個節(jié)拍以后開始重復(fù) 長為L的格圖一共有2Lk0條路經(jīng) 每條路經(jīng)對應(yīng)一個長為L段的編碼序列8/14/20239信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述8/2/205.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述由于(n0,k0,m)卷積碼的格圖從第m個節(jié)拍以后開始重復(fù)，因此，通常情況下只需研究一個節(jié)拍的格圖即可；格圖是卷積碼維特比譯碼的基本依據(jù)。利用格圖也可以構(gòu)造卷積碼，是研究卷積碼的重要工具。8/14/202310信道編碼5.3卷積碼的狀態(tài)圖與格圖描述卷積碼的格圖描述8/2/205.3卷積碼的狀態(tài)圖與格圖描述課下作業(yè)：1、已知一卷積碼的子生成元為：

g(1,1)=110，g(1,2)=101

給出該碼節(jié)拍數(shù)為6的格圖。 設(shè)m=101100…，結(jié)合格圖給出碼序列8/14/202311信道編碼5.3卷積碼的狀態(tài)圖與格圖描述課下作業(yè)：8/2/20231第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼8/14/202312信道編碼第五章卷積碼5.1卷積碼的基本概念8/2/202315.4卷積碼的概率譯碼概率譯碼概述Vitebi譯碼的基本原理8/14/202313信道編碼5.4卷積碼的概率譯碼概率譯碼概述8/2/202313信5.4卷積碼的概率譯碼概率譯碼概述概率譯碼概述 概率譯碼不僅基于碼的代數(shù)結(jié)構(gòu)，還充分利用了信道的統(tǒng)計特性，因此，通常能獲得最佳或準(zhǔn)最佳的譯碼性能（最大似然譯碼性能）。 概率譯碼由于利用足夠長序列的統(tǒng)計特性，其性能不再以糾錯能力來衡量，而采用統(tǒng)計參數(shù)--編碼增益來衡量。8/14/202314信道編碼5.4卷積碼的概率譯碼概率譯碼概述8/2/202314信5.4卷積碼的概率譯碼概率譯碼概述概率譯碼最早始于1961年提出的序列譯碼，1963年費諾（Fano）改進(jìn)后得以實際應(yīng)用，稱為Fano算法。1967年維特比（Vitebi）提出一種卷積碼譯碼方法，稱為維特比算法。1973年Forney證明維特比譯碼是最大似然譯碼。維特比算法具有效率較高、速度快、實現(xiàn)簡單等特點，使得維特比算法得到了極為廣泛的應(yīng)用。8/14/202315信道編碼5.4卷積碼的概率譯碼概率譯碼概述8/2/202315信5.4卷積碼的概率譯碼概率譯碼概述維特比譯碼基于卷積碼的格圖實現(xiàn)，其基本思想是在格圖上尋找一條最大似然路徑，該條路經(jīng)所對應(yīng)的信息序列即為譯碼輸出。對于(n0,k0,m)卷積碼，從某一個狀態(tài)出發(fā)，長為L的格圖上一共有2Lk0條不同的路徑，可見當(dāng)L足夠大時尋找最大似然路徑是極其困難的。維特比算法解決了這一問題，可利用較為簡單的方法找到足夠長的最大似然路徑。8/14/202316信道編碼5.4卷積碼的概率譯碼概率譯碼概述8/2/202316信5.4卷積碼的概率譯碼Vitebi譯碼的基本原理最大似然譯碼：

P(C|R)=Max[P(Cj|R)]?Max[P(R|Cj)]卷積碼的最大似然譯碼與分組碼原理相同，實現(xiàn)上的區(qū)別在于：分組碼的最大似然譯碼是計算單個碼字的相似度，而卷積碼是計算整個碼序列的相似度。在BSC上，最大似然譯碼和最小漢明距離譯碼是等價的。8/14/202317信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理8/2/5.4卷積碼的概率譯碼Vitebi譯碼的基本原理維特比算法的中心思想是：將求解格圖上整條路經(jīng)的似然度轉(zhuǎn)化為利用分支似然度逐步求解路徑似然度。大大簡化了譯碼的復(fù)雜性。思路：在格圖上，逐節(jié)拍（逐分支）、逐狀態(tài)比較候選序列的似然度，在每個節(jié)拍上發(fā)現(xiàn)和排除不可能路徑，從而將候選路徑保持在與狀態(tài)數(shù)相同的數(shù)量上。將復(fù)雜度系數(shù)從2Lk0降為Lx2mk0(通常L>>m)。8/14/202318信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理8/2/5.4卷積碼的概率譯碼Vitebi譯碼的基本原理結(jié)尾卷積碼序列： 設(shè)一個(n0,k0,m)編碼器輸入是一個k0L位信息和后面跟著k0m位全0的序列 m=(m0,m1,m2,…,mL-1,0,0,…,0)

其中，最后m段全0序列是使編碼器恢復(fù)到初始狀態(tài)所必需的。由編碼器輸出的碼序列C=(C0,C1,…,Cm+L-1)是一個長為n0(L+m)的二元序列。 由于編碼器輸出的碼序列C一定恢復(fù)到初始全0狀態(tài)，因此稱這種碼序列為結(jié)尾卷積碼序列。 由于信息序列共有2k0L個，因此對應(yīng)的碼序列也有2k0L個，即格圖上共有2k0L條路徑。8/14/202319信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理8/2/5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：

g(1,1)=111，g(1,2)=101

該碼的格圖為：

m=101100…對應(yīng)的碼序列為：

C=111000010111…

設(shè)：R=011001010111…8/14/202320信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理8/2/5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001130011328/14/202321信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131121130028/14/202322信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120021040138/14/202323信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130121058/14/202324信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031148/14/202325信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031130048/14/202326信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031131040128/14/202327信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010121048/14/202328信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010120041138/14/202329信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123105012118/14/202330信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123201005112118/14/202331信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123201112118/14/202332信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理S0S15.4卷積碼的概率譯碼Vitebi譯碼算法步驟：結(jié)合例子，說明過程：1.從時間單位j＝m(2)開始，計算進(jìn)入每一狀態(tài)的單個路徑的部分量度，存儲每一狀態(tài)下的路徑及其部分量度。2.j增加1，分別計算進(jìn)入每一狀態(tài)的所有分枝量度，并分別將其與前一單位時間有關(guān)的部分量度相加得到新的部分量度；對每一狀態(tài)，比較進(jìn)入它的所有路徑的部分量度，選出其中具有最佳量度的路徑（幸存路徑）及其量度進(jìn)行存儲，刪除其它路徑。【加、比、選】3.若j<6，重復(fù)以上步驟，否則停止。8/14/202333信道編碼5.4卷積碼的概率譯碼Vitebi譯碼算法步驟：8/2/5.4卷積碼的概率譯碼Vitebi譯碼的基本原理注意：從時間單位2(m)到4(L)中，每個狀態(tài)都有一個幸存路徑。時間單位4(L)之后，幸存路徑減少，最后在時間單位2+4時，只有一個狀態(tài)，即全0狀態(tài)?；厮荩河晒乐敌蛄懈鶕?jù)網(wǎng)格圖得出信息序列的過程。經(jīng)回溯，得到信息序列m’＝（101100），去掉補的m＝2個0得譯碼信息序列m＝（1011）。以上過程是針對結(jié)尾卷積碼序列的譯碼操作。8/14/202334信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理8/2/5.4卷積碼的概率譯碼Vitebi最大似然路徑算法步驟：

1.從時間單位j＝m開始，計算進(jìn)入每一狀態(tài)的單個路徑的部分量度，存儲每一狀態(tài)下的路徑及其部分量度。2.j增加1，分別計算進(jìn)入每一狀態(tài)的所有分枝量度，并分別將其與前一單位時間有關(guān)的部分量度相加得到新的部分量度，然后對每一狀態(tài)比較進(jìn)入它的所有路徑的部分量度，選出其中具有最佳量度的路徑（幸存路徑）及其量度進(jìn)行存儲，刪除其它路徑?！炯?、比、選】3.若j<L＋m，重復(fù)以上步驟，否則停止。8/14/202335信道編碼5.4卷積碼的概率譯碼Vitebi最大似然路徑算法步驟：5.4卷積碼的概率譯碼軟判決Vitebi譯碼軟判決譯碼