第五章-卷積碼碼2

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

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

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

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

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

給出該碼節(jié)拍數(shù)為6的格圖。 設(shè)m=101100…，結(jié)合格圖給出碼序列3/2/202311信道編碼第五章卷積碼5.1卷積碼的基本概念5.2卷積碼的矩陣描述與編碼5.3卷積碼的狀態(tài)圖與格圖描述5.4卷積碼的概率譯碼3/2/202312信道編碼5.4卷積碼的概率譯碼概率譯碼概述Vitebi譯碼的基本原理3/2/202313信道編碼5.4卷積碼的概率譯碼概率譯碼概述概率譯碼概述 概率譯碼不僅基于碼的代數(shù)結(jié)構(gòu)，還充分利用了信道的統(tǒng)計(jì)特性，因此，通常能獲得最佳或準(zhǔn)最佳的譯碼性能（最大似然譯碼性能）。 概率譯碼由于利用足夠長序列的統(tǒng)計(jì)特性，其性能不再以糾錯(cuò)實(shí)力來衡量，而接受統(tǒng)計(jì)參數(shù)--編碼增益來衡量。3/2/202314信道編碼5.4卷積碼的概率譯碼概率譯碼概述概率譯碼最早始于1961年提出的序列譯碼，1963年費(fèi)諾（Fano）改進(jìn)后得以實(shí)際應(yīng)用，稱為Fano算法。1967年維特比（Vitebi）提出一種卷積碼譯碼方法，稱為維特比算法。1973年Forney證明維特比譯碼是最大似然譯碼。維特比算法具有效率較高、速度快、實(shí)現(xiàn)簡潔等特點(diǎn)，使得維特比算法得到了極為廣泛的應(yīng)用。3/2/202315信道編碼5.4卷積碼的概率譯碼概率譯碼概述維特比譯碼基于卷積碼的格圖實(shí)現(xiàn)，其基本思想是在格圖上找尋一條最大似然路徑，該條路經(jīng)所對(duì)應(yīng)的信息序列即為譯碼輸出。對(duì)于(n0,k0,m)卷積碼，從某一個(gè)狀態(tài)動(dòng)身，長為L的格圖上一共有2Lk0條不同的路徑，可見當(dāng)L足夠大時(shí)找尋最大似然路徑是極其困難的。維特比算法解決了這一問題，可利用較為簡潔的方法找到足夠長的最大似然路徑。3/2/202316信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理最大似然譯碼： P(C|R)=Max[P(Cj|R)]?Max[P(R|Cj)]卷積碼的最大似然譯碼與分組碼原理相同，實(shí)現(xiàn)上的區(qū)分在于：分組碼的最大似然譯碼是計(jì)算單個(gè)碼字的相像度，而卷積碼是計(jì)算整個(gè)碼序列的相像度。在BSC上，最大似然譯碼和最小漢明距離譯碼是等價(jià)的。3/2/202317信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理維特比算法的中心思想是：將求解格圖上整條路經(jīng)的似然度轉(zhuǎn)化為利用分支似然度逐步求解路徑似然度。大大簡化了譯碼的困難性。思路：在格圖上，逐節(jié)拍（逐分支）、逐狀態(tài)比較候選序列的似然度，在每個(gè)節(jié)拍上發(fā)覺和解除不行能路徑，從而將候選路徑保持在與狀態(tài)數(shù)相同的數(shù)量上。將困難度系數(shù)從2Lk0降為Lx2mk0(通常L>>m)。3/2/202318信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理結(jié)尾卷積碼序列： 設(shè)一個(gè)(n0,k0,m)編碼器輸入是一個(gè)k0L位信息和后面跟著k0m位全0的序列 m=(m0,m1,m2,…,mL-1,0,0,…,0) 其中，最終m段全0序列是使編碼器復(fù)原到初始狀態(tài)所必需的。由編碼器輸出的碼序列C=(C0,C1,…,Cm+L-1)是一個(gè)長為n0(L+m)的二元序列。 由于編碼器輸出的碼序列C確定復(fù)原到初始全0狀態(tài)，因此稱這種碼序列為結(jié)尾卷積碼序列。 由于信息序列共有2k0L個(gè)，因此對(duì)應(yīng)的碼序列也有2k0L個(gè)，即格圖上共有2k0L條路徑。3/2/202319信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：

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

該碼的格圖為：

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

C=111000010111…

設(shè)：R=011001010111…3/2/202320信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001130011323/2/202321信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131121130023/2/202322信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120021040133/2/202323信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130121053/2/202324信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031143/2/202325信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031130043/2/202326信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031131040123/2/202327信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010121043/2/202328信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010120041133/2/202329信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123105012113/2/202330信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123201005112113/2/202331信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理[例]：(2,1,2)卷積碼：S000S110S201S311011001010111R=0011110021121001131120020130120031132010123201112113/2/202332信道編碼5.4卷積碼的概率譯碼Vitebi譯碼算法步驟：結(jié)合例子，說明過程：1.從時(shí)間單位j＝m(2)起先，計(jì)算進(jìn)入每一狀態(tài)的單個(gè)路徑的部重量度，存儲(chǔ)每一狀態(tài)下的路徑及其部重量度。2.j增加1，分別計(jì)算進(jìn)入每一狀態(tài)的全部分枝量度，并分別將其與前一單位時(shí)間有關(guān)的部重量度相加得到新的部重量度；對(duì)每一狀態(tài)，比較進(jìn)入它的全部路徑的部重量度，選出其中具有最佳量度的路徑（幸存路徑）及其量度進(jìn)行存儲(chǔ)，刪除其它路徑?！炯?、比、選】3.若j<6，重復(fù)以上步驟，否則停止。3/2/202333信道編碼5.4卷積碼的概率譯碼Vitebi譯碼的基本原理留意：從時(shí)間單位2(m)到4(L)中，每個(gè)狀態(tài)都有一個(gè)幸存路徑。時(shí)間單位4(L)之后，幸存路徑削減，最終在時(shí)間單位2+4時(shí)，只有一個(gè)狀態(tài)，即全0狀態(tài)?；厮荩河晒乐敌蛄幸罁?jù)網(wǎng)格圖得出信息序列的過程。經(jīng)回溯，得到信息序列m’＝（101100），去掉補(bǔ)的m＝2個(gè)0得譯碼信息序列m＝（1011）。以上過程是針對(duì)結(jié)尾卷積碼序列的譯碼操作。3/2/202334信道編碼5.4卷積碼的概率譯碼Vitebi最大似然路徑算法步驟： 1.從時(shí)間單位j＝m起先，計(jì)算進(jìn)入每一狀態(tài)的單個(gè)路徑的部重量度，存儲(chǔ)每一狀態(tài)下的路徑及其部重量度。2.j增加1，分別計(jì)算進(jìn)入每一狀態(tài)的全部分枝量度，并分別將其與前一單位時(shí)間有關(guān)的部重量度相加得到新的部重量度，然后對(duì)每一狀態(tài)比較進(jìn)入它的全部路徑的部重量度，選出其中具有最佳量度的路徑（幸存路徑）及其量度進(jìn)行存儲(chǔ)，刪除其它路徑?！炯?、比、選】3.若j<L＋m，重復(fù)以上步驟，否則停止。3/2/20233