2.1第章信道編碼

4.1概述4.2能量擴散4.3RS編碼4.4交錯4.5卷積編碼第4章信道編碼4.1概述提高數(shù)據(jù)傳輸效率，降低誤碼率是信道編碼的任務(wù)。信道編碼的本質(zhì)是增加通信的可靠性。數(shù)字信號在傳輸中往往由于各種原因，使得在傳送的數(shù)據(jù)流中產(chǎn)生誤碼，從而使接收端產(chǎn)生圖象跳躍、不連續(xù)、出現(xiàn)馬賽克等現(xiàn)象。所以通過信道編碼這一環(huán)節(jié)，對數(shù)碼流進行相應(yīng)的處理，使系統(tǒng)具有一定的糾錯能力和抗干擾能力，可極大地避免碼流傳送中誤碼的發(fā)生。誤碼的處理技術(shù)有糾錯、交錯、線性內(nèi)插等。根本目的：提高信息傳輸?shù)目煽啃孕诺谰幋a是數(shù)字通信區(qū)別于模擬通信的顯著標(biāo)志。數(shù)字電視系統(tǒng)對信道編碼技術(shù)的要求編碼效率高，抗干擾能力強；對傳輸信號應(yīng)有良好的透明性；傳輸信號的頻譜特性與傳輸通道的通頻帶有最佳的匹配；編碼信號內(nèi)應(yīng)包含有數(shù)據(jù)定時信息與幀同步信息，以便接收端能夠準(zhǔn)確解碼；編碼的數(shù)字信號應(yīng)具有適當(dāng)?shù)碾娖椒秶话l(fā)生誤碼時，誤碼的擴散蔓延小。信道中的噪聲:加性噪聲乘性噪聲。4.1.1信道編碼基礎(chǔ)1)隨機差錯信道信道中，碼元出現(xiàn)差錯與其前、后碼元是否出現(xiàn)差錯無關(guān)，每個碼元獨立地按一定的概率產(chǎn)生差錯。從統(tǒng)計規(guī)律看，可以認(rèn)為這種隨機差錯是由加性高斯白噪聲AWGN(AdditiveWhiteGaussianNoise)引起的，主要的描述參數(shù)是誤碼率pe。1.隨機差錯和突發(fā)差錯2)突發(fā)差錯信道信道中差錯成片出現(xiàn)時，一片差錯稱為一個突發(fā)差錯。突發(fā)差錯總是以差錯碼元開頭，以差錯碼元結(jié)尾，頭尾之間并不是每個碼元都錯，而是碼元差錯概率大到超過了某個標(biāo)準(zhǔn)值。通信系統(tǒng)中的突發(fā)差錯是由突發(fā)噪聲(比如雷電、強脈沖、時變信道的衰落等)引起的。存儲系統(tǒng)中，磁帶、磁盤物理介質(zhì)的缺陷或讀寫頭的接觸不良等造成的差錯均為突發(fā)差錯。實際信道中往往既存在隨機差錯又存在突發(fā)差錯。信道編碼的基本知識

從信道編碼的構(gòu)造方法看，其基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼中加入一些人為多余的碼元，以保證傳輸過程可靠性。信道編碼的任務(wù)就是構(gòu)造出以最小多余度代價換取最大抗干擾性能的“好碼”。在分組碼中，編碼后的碼元序列每n位為一組，其中k位是信息碼元，r位是附加的監(jiān)督碼元，r=n-k，通常記為(n，k)。分組碼的監(jiān)督碼元只與本碼組的信息碼元有關(guān)。卷積碼的監(jiān)督碼元不僅與本碼組的信息碼元有關(guān)，還與前面幾個碼組有約束關(guān)系。2.分組碼和卷積碼3.線性碼和非線性碼若信息碼元與監(jiān)督碼元之間的關(guān)系是線性的，即滿足一組線性方程，則稱為線性碼；反之，兩者若不滿足線性關(guān)系，則稱為非線性碼。4.系統(tǒng)碼和非系統(tǒng)碼在編碼后的碼組中，信息碼元和監(jiān)督碼元通常都有確定的位置，一般信息碼元集中在碼組的前k位，而監(jiān)督碼元位于后r=n-k位。如果編碼后信息碼元保持原樣不變，則稱為系統(tǒng)碼；反之稱為非系統(tǒng)碼。碼組或碼字中編碼的總位數(shù)稱為碼組的長度，簡稱碼長；碼組中非零碼元的數(shù)目稱為碼組的重量，簡稱碼重。例如:“11010〞的碼長為5，碼重為3。5.碼長和碼重6.碼距和最小漢明距離兩個等長碼組中對應(yīng)碼位上具有不同碼元的位數(shù)稱為漢明(Hamming)間隔，簡稱碼距。例如，“11010〞和“01101〞有4個碼位上的碼元不同，它們之間的漢明距離是4。在由多個等長碼組構(gòu)成的碼組集合中，定義任意兩個碼組之間距離的最小值為最小碼距或最小漢明距離，通常記作dmin，它是衡量一種編碼方案糾錯和檢錯能力的重要依據(jù)。以3位二進制碼組為例，在由8種可能組合構(gòu)成的碼組集合中，兩碼組間的最小距離是1，例如“000〞和“001〞之間，因此dmin=1；如果只取“000〞和“111〞為準(zhǔn)用碼組，則這種編碼方式的最小碼距dmin=3。對于分組碼，最小碼距dmin與碼的糾錯和檢錯能力之間具有如下關(guān)系：在一個碼組集合中，如果碼組間的最小碼距滿足dmin≥e+1，則該碼集中的碼組可以檢測e位錯碼；如果滿足dmin≥2t+1,則可以糾正t位錯碼；如果滿足dmin≥t+e+1，則可以糾正t位錯碼，同時具有檢測e位錯碼的能力。它是指信息碼元和監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示的分組碼。其主要性質(zhì)有：(1)封閉性,即任意兩個準(zhǔn)用碼組之和(逐位模2加)仍為一個準(zhǔn)用碼組。(2)兩個碼組之間的距離必定是另一碼組的重量，因此碼的最小距離等于非零碼的最小重量。(3)線性碼中的單位元素是A=0，即全零碼組，因此全零碼組一定是線性碼中的一個元素。(4)線性碼中一個元素的逆元素就是該元素本身，因為A與它本身異或結(jié)果為0。7.線性分組碼1.定義循環(huán)碼是一種系統(tǒng)碼，通常前k位為信息碼元，后r位為監(jiān)督碼元。它除了具有線性分組碼的一般性質(zhì)以外，還具有循環(huán)性，也就是說當(dāng)循環(huán)碼中的任一碼組循環(huán)移動一位以后，所得碼組仍為該循環(huán)碼的一個準(zhǔn)用碼組。4.1.2循環(huán)碼2.多項式表示數(shù)碼用多項式來表示是一種比較直觀的方法，如5位二進制數(shù)字序列11010可表示為1×24＋1×23＋0×22＋1×21＋0×20=11010通常在編碼中，以x表示系數(shù)只取0、1的多項式的基，則上述５位二進制序列可表示為1×x4＋1×x3＋0×x2＋1×x1＋0×x0=x4＋x3＋x這種以多項式的系數(shù)表示二進制序列的方法給編碼處理帶來了方便,一個(n，k)循環(huán)碼的k位信息碼可以用x的k-1次多項式來表示，即A(x)=ak-1xk-1+ak-2xk-2+…+a2x2+a1x+a0（4-1）式中，ak-1～a0為多項式的0、1系數(shù)值；x表示多項式的基，x的次數(shù)k-1～0表示了該位在碼中的位置。3.編碼循環(huán)碼的編碼規(guī)則是：把k位信息碼左移r位后被規(guī)定的多項式除，將所得余數(shù)作校驗位加到信息碼后面。規(guī)定的多項式稱為生成多項式，用G〔x〕表示。要將A(x)左移r位，只要將A(x)乘上xr，得到xrA(x)。用生成多項式G〔x〕除xrA(x),便可得到余數(shù)R(x)，即xrA(x)=G〔x）×Q〔x）+R(x)兩邊加上R(x)，得xrA(x)+R(x)=G〔x）×Q〔x）+R(x)+R(x)因為R(x)+R(x)=0，所以有xrA(x)+R(x)=G〔x）×Q〔x）（4-3）上式表明xrA(x)+R(x)可被生成多項式G〔x〕除盡。用這種編碼方法能產(chǎn)生出有檢錯能力的循環(huán)碼〔n，k）。在發(fā)送端發(fā)出信號U〔x）=xrA(x)+R(x)，如果傳送未發(fā)生錯誤，則收到的信號必能被G〔x〕除盡，否則表明有錯。BCH碼是根據(jù)碼的3個發(fā)明人Bose、Chaudhuri和Hocquenghem命名的。BCH碼解決了生成多項式與最小碼距之間的關(guān)系問題。根據(jù)所要求的糾錯能力，可以很容易地構(gòu)造出BCH碼。它們的譯碼也比較簡單，因此是線性分組碼中應(yīng)用最為普遍的一類碼。BCH碼分為本原BCH碼和非本原BCH碼。4.1.3BCH碼4.1.4級聯(lián)編碼1.級聯(lián)碼信道中由噪聲引起的誤碼一般分為兩類，一類是由隨機噪聲引起的隨機性誤碼，一類是由沖擊噪聲引起的突發(fā)性誤碼。在實際通信信道中出現(xiàn)的誤碼是混合型誤碼，是隨機性誤碼和突發(fā)性誤碼的混合。糾正這類混合誤碼，要設(shè)計既能糾隨機性誤碼又能糾突發(fā)性誤碼的碼。交錯碼、乘積碼、級聯(lián)碼均屬于這類糾錯碼。而性能最好、最有效、最常采用的是級聯(lián)碼。級聯(lián)碼是一種由短碼構(gòu)造長碼的特殊的、有效的方法。通常由一個二進制的(n1，k1)碼c1〔為內(nèi)編碼〕和另一個非二進制的(n2，k2)碼c2(為外編碼)就能組成一個簡單的級聯(lián)碼。一般外編碼c2采用RS碼，內(nèi)編碼c1采用分組碼或卷積碼。圖4-1是級聯(lián)碼編、解碼方框圖。圖4-1級聯(lián)碼編、解碼方框圖在編碼時，首先將k1×k2個二進制信息元〔碼元〕劃分為k2個碼字，每個碼字有k1個碼元，把碼字看成是多進制碼中的一個符號。k2個碼字編碼成(n2，k2)RS碼(詳見4.3節(jié))的外碼c2，它有k2個信息符號，n2-k2個監(jiān)督符號。每一個碼字內(nèi)的k1個碼元按照二進制分組碼或卷積碼編成(n1，k1)的內(nèi)碼c1，它有k1個信息碼元，n1-k1個監(jiān)督碼元。這樣構(gòu)成總共有n1×n2個碼元的編碼(n1×n2，k1×k2)。若內(nèi)碼與外碼的最小距離分別為d1和d2，則它們級聯(lián)后的級聯(lián)碼最小距離至少為d1×d2。級聯(lián)碼編、譯碼也可分為兩步進行，其設(shè)備僅是c1與c2的直接組合，顯然它比直接采用一個長碼構(gòu)成時設(shè)備要簡單得多。以RS碼為外碼、卷積碼為內(nèi)碼的級聯(lián)編碼對隨機性誤碼和突發(fā)性誤碼有很強的糾錯能力，接收端經(jīng)糾錯譯碼后一般可達到10-10～10-11比特誤碼率。信道編碼常用的差錯控制方式:有前向糾錯FEC(ForwardErrorCorrection)檢錯重發(fā)ARQ(AutomaticRepeatRequest）反饋校驗〔IRQ）混合糾錯HEC(HybridErrorCorrection）。4.1.5前向糾錯數(shù)字電視中的差錯控制采用前向糾錯方式接收端能夠根據(jù)接收到的碼元自動檢出錯誤和糾正錯誤。糾錯編碼的基本思想：在所要傳輸?shù)男畔⑿蛄猩细郊右恍┐a元，附加的碼元與信息碼元之間以某種確定的規(guī)則相關(guān)聯(lián)。接收端按照這種規(guī)則對接收的碼元進行檢驗，一旦發(fā)現(xiàn)碼元之間的確定關(guān)系受到破壞，便可通過恢復(fù)原有確定關(guān)系的方法來糾正誤碼。數(shù)字電視的前向糾錯能量擴散(EnergyDispersal)RS編碼交錯(Interleaving)卷積編碼(ConvolutionalCoding)。4.2.1能量擴散的作用能量擴散也稱為隨機化、加擾或擾碼。在數(shù)字電視廣播過程中會出現(xiàn)碼流中斷或碼流格式不符合MPEG-2的TS流結(jié)構(gòu)的情況，導(dǎo)致調(diào)制器發(fā)射未經(jīng)調(diào)制的載波信號；當(dāng)數(shù)字基帶信號是周期不長的周期信號時，已調(diào)波的頻譜將集中在局部并含有相當(dāng)多的高電平離散譜。結(jié)果對處于同一頻段的其它業(yè)務(wù)的干擾超過了規(guī)定值。另外，信源碼流中可能會出現(xiàn)長串的連“0〞或連“1”，這將給接收端恢復(fù)位定時信息造成一定困難。4.2能量擴散為消除上述兩種情況，可將基帶信號在隨機化電路中進行能量擴散，信號擴散后具有偽隨機性質(zhì)，其已調(diào)波的頻譜將分散開來，從而降低對其它系統(tǒng)的干擾；同時，連“0〞碼或連“1〞碼的長度縮短，便于接收端提取比特定時信息。實現(xiàn)能量擴散功能的是隨機化電路，也稱為偽隨機碼發(fā)生器或M序列發(fā)生器，由帶有若干反饋線的m級移位寄存器組成。M序列有下列基本特性：(1)由m級移位寄存器產(chǎn)生的M序列，其周期為2m-1。(2)除全0狀態(tài)外，m級移位寄存器可能出現(xiàn)的各種不同狀態(tài)都在M序列的一個周期內(nèi)出現(xiàn)一次；M序列中“0”、“1〞碼的出現(xiàn)概率基本相同，在一個周期內(nèi)，“1〞碼只比“0〞碼多一個。4.2.2能量擴散的實現(xiàn)(3)若將連續(xù)出現(xiàn)的“0〞或“1〞稱為游程，則M序列一個周期中共有2m-1個游程，其中長度為1的游程占1／2，長度為2的游程占1／4，長度為3的游程占1／8，……還有一個長度為m的連“1〞碼游程和一個長度為m-1的連“0〞碼游程。DVB規(guī)定的偽隨機碼生成多項式為G(x)＝1+x14+x15圖4-4DVB隨機化和去隨機化電路4.3RS編碼RS碼是里德·索洛蒙(ReedSolomon)碼的簡稱，是一類糾錯能力很強的線性分組碼(n,k)，在所有的線性分組碼中，RS碼的漢明距離最大，因此糾錯能力最佳。RS碼以碼字〔組〕為基礎(chǔ)，碼字〔組〕又稱為符號，RS碼只處理符號。在(n，k)RS碼中，輸入信號每k·m比特為一碼字，每個碼元由m比特組成，因此一個碼字共包括k個碼元。K個信息符號，n-k個監(jiān)督符號。（n,k,t）一個能糾正t個碼元錯誤的RS碼主要參數(shù)如下：(1)字長n=2m-1碼元，或m(2m-1)比特。(2)監(jiān)督碼元數(shù)n-k=2t碼元，或m·2t比特。(3)最小碼距dmin=2t+1碼元，或m·(2t+1)比特。RS碼能夠糾正t個m位二進制錯誤碼組。至于一個m位二進制碼組中到底有1位錯誤，還是m位全錯了，并不會影響到它的糾錯能力。從這一點來說，RS碼特別適合于糾正突發(fā)錯誤，如果與交織技術(shù)相結(jié)合，它糾正突發(fā)錯誤的能力則會更強。因此RS碼廣泛應(yīng)用在既存在隨機錯誤又存在突發(fā)錯誤的信道上。在數(shù)字電視中，一個符號是一個8比特的字節(jié)，因此總共有28＝256種符號，這256種符號組成伽羅華域GF(28)。DVB系統(tǒng)中，外碼采用RS(204，188)，它是由RS(255，239)截短得到的。具體的做法是，以188字節(jié)的TS包為單位，每個TS數(shù)據(jù)包前加上51字節(jié)的填充位(全“0”)構(gòu)成一個239字節(jié)的包，進入RS(255，239)編碼器編碼，得到255字節(jié)的碼字(239字節(jié)的信息碼元+16字節(jié)的監(jiān)督碼元)，然后再去掉51字節(jié)的填充位，最終得到長度為204字節(jié)的碼字。

接收端糾錯解碼時，也要先在204字節(jié)的碼字前面加上51字節(jié)的全“0〞填充位，然后送入RS(255，239)解碼器解碼，最終恢復(fù)188字節(jié)的TS包。RS(204，188)碼的同步字使用TS包的同步字(47H和0B8H)，同步字也作為有效的信息碼元參加運算。4.4交織為了增強RS碼糾正突發(fā)錯誤的能力，常常使用交織(Interleaving)技術(shù)。交織的作用是減小信道中錯誤的相關(guān)性，把長突發(fā)錯誤離散成為短突發(fā)錯誤或隨機錯誤。交織深度越大，則離散程度越高。交織技術(shù)數(shù)據(jù)交織是指在不附加糾錯碼字的前提下，利用改變數(shù)據(jù)碼字傳輸順序的方法，來提高收端去交織解碼是的抗突發(fā)誤碼能力。交錯〔交錯）在實際應(yīng)用中，比特差錯經(jīng)常成串發(fā)生，這是由于持續(xù)時間較長的衰落谷點會影響到幾個連續(xù)的比特，而信道編碼僅在檢測和校正單個差錯和不太長的差錯串時才最有效。為了糾正這些成串發(fā)生的比特差錯及一些突發(fā)錯誤，可以運用交織技術(shù)來分散這些誤差。分組交織對一個(n，k)分組碼進行深度為m的分組交織時，把m個碼組按先行后列排列成一個m×n的碼陣。碼元aij的下標(biāo)i為行號，下標(biāo)j為列號，排列成a11,a12,…,a1n,a21,a22,…,a2n,am1,am2,…,amn的形式。規(guī)定以先列后行的次序自左至右的順序傳輸，即以a11,a21,…,am1,a12,a22,…,am2,…,a1n,a2n,…,amn的順序傳輸。接收端的去交織則執(zhí)行相反的操作，把收到的碼元仍排列成a11,a12,…,a1n,a21,a22,…,a2n,am1,am2,…,amn的形式，以行為單位，按(n，k)碼的方式進行譯碼。經(jīng)過交織以后，每個(n，k)碼組的相鄰碼元之間相隔m-1個碼元。因而，當(dāng)接收端收到交織的碼元后，若仍恢復(fù)成原來的碼陣形式，就把信道中的突發(fā)錯誤分散到了m個(n，k)碼中。如果一個(n，k)碼可以糾正t個錯誤(隨機或突發(fā))，交織深度為m時形成的m×n碼陣就能糾正長度不大于mt的單個突發(fā)錯誤。顯然交織方法是一種時間擴散技術(shù)，它把信道錯誤的相關(guān)性減??；當(dāng)m足夠大時就把突發(fā)錯誤離散成隨機錯誤。卷積交織DVB采用的是卷積交織，DVB的交織器和去交織器如下圖所示。交織器由I=12個分支組成，在第j(j＝0，1，…，I-1)分支上設(shè)有容量為jM個字節(jié)的先進先出〔FIFO〕移位寄存器。下圖M＝17，交織器的輸入與輸出開關(guān)同步工作，以1字節(jié)／位置的速度進行從分支0到分支I-1的周期性切換。接收端在去交織時，應(yīng)使各個字節(jié)的延時相同，因此采用與交織器結(jié)構(gòu)類似但分支排列次序相反的去交織器。為了使交織與去交織開關(guān)同步工作，在交織器中使數(shù)據(jù)幀的同步字節(jié)總是由分支0發(fā)送出去，這由下述關(guān)系可以得到保證：N＝IM＝12×17＝204即17個切換周期正好是糾錯編碼包的長度。去交織器的同步可以通過從分支0識別出同步字節(jié)來完成。DVB的卷積交織器和去交織器卷積交織器用參數(shù)(N，I)來描述，上圖所示的是(204，12)交織器。很容易證明，在交織器輸出的任何長度為N的數(shù)據(jù)串中，不包含交織前序列中距離小于I的任何兩個數(shù)據(jù)，I稱為交織深度。對于(204，188)RS碼，能糾正連續(xù)8個字節(jié)的錯誤，與交織深度I=12相結(jié)合，可具有最多糾正12×8＝96個字節(jié)長的突發(fā)錯誤的能力。I越大糾錯能力越強，但交織器與去交織器總的存儲容量S和數(shù)據(jù)延時D與I有關(guān)：S=D=I(I-1)M在DVB中，交織位于RS編碼與卷積編碼之間，這是因為維特比譯碼會出現(xiàn)差錯擴散，引起突發(fā)差錯。例：I=4,M=34.5卷積編碼分組碼編譯碼時要把整個碼組存儲起來，處理時會產(chǎn)生較長的延時。卷積碼的碼長n和信息碼元個數(shù)k通常較小，故延時小，特別適合于以串行形式傳輸信息的場合。卷積碼(ConvolutionalCoding)在任何一個碼組中的監(jiān)督碼元不僅與本組的k個信息碼元有關(guān)，而且與前面N段的信息碼元有關(guān)。隨著N的增加，卷積碼的糾錯能力增強，誤碼率則呈指數(shù)下降。編碼器卷積碼的編碼器由移位寄存器和加法器組成。輸入移位寄存器有N段，每段有k級，共Nk位寄存器，主要負責(zé)存儲每段的k個信息碼元；各信息碼元通過n個模2加法器相加，產(chǎn)生每個輸出碼組的n個碼元，并寄存在一個n級的移位寄存器中移位輸出。編碼過程是輸入信息序列與由移位寄存器和模2加法器之間連接所決定的另一個序列的卷積，因此稱為卷積碼。通常把N稱為卷積碼的約束長度，卷積碼則記為(n，k，N)，其中n為碼長，k為碼組中信息碼元的個數(shù)，即編碼器每輸入k比特，輸出n比特；編碼效率為R=k/n。(2，1，3)卷積編碼器(a)編碼器結(jié)構(gòu)(b)輸入輸出時序關(guān)系圖中沒有畫出延時為零的第一級移位寄存器〔約束長度為N，需要N-1個移位寄存器），并用轉(zhuǎn)換開關(guān)代替了輸出移位寄存器。它的編碼方法是：輸入序列依次送入一個兩級移位寄存器，編碼器每輸入一位信息bi，輸出端的開關(guān)就在c1、c2之間切換一次，輸出c1,i和c2,i，其中c1,i=bi+bi-1+bi-2c2,i=bi+bi-2設(shè)寄存器m1，m2的起始狀態(tài)為全零，則編碼器的輸入輸出時序關(guān)系見上圖。卷積碼研究方法樹狀圖網(wǎng)格圖狀態(tài)圖樹狀圖(2，1，3)卷積碼編碼電路的樹狀圖如下圖所示。這里用a，b，c和d表示寄存器m2、m1的4種可能狀態(tài)(00，01，10和11)，并作為樹狀圖中每條支路的節(jié)點。以全零狀態(tài)a為起點，當(dāng)?shù)?位信息b1=0時，輸出碼元c1c2=00，寄存器保持狀態(tài)a不變，對應(yīng)圖中從起點出發(fā)的上支路；當(dāng)b1=1時，輸出碼元c1c2=11，寄存器則轉(zhuǎn)移到狀態(tài)b，對應(yīng)圖中的下支路；然后再分別以這兩條支路的終節(jié)點a和b作為處理下一位輸入信息b2的起點，從而得到4條支路。c1,i=bi+bi-1+bi-2c2,i=bi+bi-2(2，1，3)卷積碼樹狀圖110111010100依此類推，可以得到整個樹狀圖。顯然，對于第i位輸入信息，圖中將會出現(xiàn)2i條支路。但從第4位信息開始，樹狀圖的上半部和下半部完全相同，這意味著此時的輸出碼元已和第1位信息無關(guān)，由此可以看出把卷積碼的約束長度定義為N的意義。圖中還用虛線標(biāo)出了輸入信息序列為“1101〞時的支路運動軌跡和狀態(tài)變化路徑，從中可以讀出對應(yīng)輸出碼元序列為“11010100”。網(wǎng)格圖利用樹狀圖中觀察到的重復(fù)性，把其中具有相同狀態(tài)的節(jié)點合并到一起，可以得到更為緊湊的網(wǎng)格圖〔格形圖）。這種圖仍由節(jié)點和支路組成，4行節(jié)點分別表示a，b，c，d四種狀態(tài)；支路則代表了狀態(tài)之間的轉(zhuǎn)移關(guān)系，其中實線支路表示輸入信息為“0”，虛線支路表示輸入信息為“1”，支路上標(biāo)注的碼元為當(dāng)前輸出。一般情況下，網(wǎng)格圖應(yīng)有2k(N-1)種狀態(tài)，從第N節(jié)開始圖形同樣會出現(xiàn)重復(fù)。利用網(wǎng)格圖同樣可以得到任意輸入信息序列下的輸出序列和狀態(tài)變化路徑。(2，1，3)卷積碼網(wǎng)格圖(2，1，3)卷積碼編碼過程和狀態(tài)變化假設(shè)起始狀態(tài)為0，輸入序列為“110111001000”，則對應(yīng)的輸出序列和狀態(tài)變化將如圖所示。110111001000(2，1，3)卷積碼狀態(tài)圖注意：狀態(tài)圖有2k(N-1)種可能狀態(tài)(節(jié)點)，每個節(jié)點會 引出2k條支路，同時也會有2k條來自其他節(jié)點或 本節(jié)點的支路到達。維特比譯碼(Viterbi)卷積譯碼方法：代數(shù)譯碼：硬件實現(xiàn)簡單，但性能較差；概率譯碼：利用了信道的統(tǒng)計特性，譯碼性能好，但硬 件復(fù)雜，常用的有維特比譯碼。維特比譯碼比較接收序列與所有可能的發(fā)送序列，選擇與接收序列漢明距離最小的發(fā)送序列作為譯碼輸出。通常把可能的發(fā)送序列與接收序列之間的漢明距離稱為量度。如果發(fā)送序列長度為L，就會有2L種可能序列，需要計算2L次量度并對其進行比較，從中選取量度最小的一個序列作為輸出。因而，譯碼過程的計算量將隨著L的增加而增長。維特比譯碼使用網(wǎng)格圖描述卷積碼，每個可能的發(fā)送序列都與網(wǎng)格圖中的一條路徑相對應(yīng)。如果發(fā)現(xiàn)某些路徑不可能具有最小量度，就放棄這些路徑,在剩下的幸存路徑中選擇。對于(n，k，N)卷積碼，網(wǎng)格圖中共有2k(N-1)種狀態(tài)，每個節(jié)點(狀態(tài))有2k條支路引入，也有2k條支路引出?，F(xiàn)以全零狀態(tài)為起點，由前N-1條支路構(gòu)成的2k(N-1)條路徑互不相交。從第N條支路開始，每條路徑都將有2k條支路延伸到下一級節(jié)點，而每個節(jié)點也將匯聚來自上一級不同節(jié)點的2k條支路。維特比譯碼算法的基本步驟為：

對于網(wǎng)格圖第i級的每個節(jié)點，計算到達該節(jié)點的所有