卷積碼編譯器狀態圖

❶ 卷積碼的解碼方法

若信道干擾序列為，其中。接收序列為
其中和。這里「+」為模 2 運算（q=p元碼按模p運算）。解碼就是根據編碼規則和信道干擾的統計特性，對信息序列u(x）作出估值的方法。常用的有三類解碼方法，即代數解碼、維特比解碼和序貫解碼。
⒈代數
代數解碼是將卷積碼的一個編碼約束長度的碼段看作是[n0(m+1），k0(m+1)]線性分組碼，每次根據（m+1）分支長接收數字，對相應的最早的那個分支上的信息數字進行估計，然後向前推進一個分支。上例中信息序列 =(10111），相應的碼序列 c=(11100001100111）。若接收 序列R=(10100001110111），先根據R的前三個分支（101000）和碼樹中前三個分支長的所有可能的 8條路徑(000000…）、（000011…）、（001110…）、（001101…）、（111011…）、（111000…）、（110101…）和（110110…）進行比較，可知（111001）與接收序列（101000）的距離最小，於是判定第 0分支的信息數字為 0。然後以R的第 1～3分支數字（100001）按同樣方法判決，依此類推下去，最後得到信息序列的估值為=(10111），遂實現了糾錯。這種解碼法，解碼時採用的接收數字長度或解碼約束長度為（m+1)n0，所以只能糾正不多於（dmin-1)/2個錯誤（n長上的）。實用中多採用反饋擇多邏輯解碼法實現。
⒉維特比
維特比解碼過程
維特比解碼是根據接收序列在碼的格圖上找出一條與接收序列距離（或其他量度）為最小的一種演算法。它和運籌學中求最短路徑的演算法相類似。若接收序列為R=(10100101100111），解碼器從某個狀態，例如從狀態ɑ出發，每次向右延伸一個分支（對於l<L，從每個節點出發都有 2=2種可能的延伸，其中L是信息序列段數，對l≥L，只有一種可能），並與接收數字相應分支進行比較，計算它們之間的距離，然後將計算所得距離加到被延伸路徑的累積距離值中。對到達每個狀態的各條路徑（有2=2條）的距離累積值進行比較，保留距離值最小的一條路徑，稱為倖存路徑（當有兩條以上取最小值時，可任取其中之一），解碼過程如圖。圖中標出到達各級節點的倖存路徑的距離累積值。對給定 R的估值序列為=(10111）。這種演算法所保留的路徑與接收序列之間的似然概率為最大，所以又稱為最大似然解碼。這種解碼的解碼 約束長度常為編碼約束長度的數倍，因而可以糾正不多於（df/2）個錯誤。
維特比解碼器的復雜性隨m呈指數增大。實用中m不大於10。它在衛星和深空通信中有廣泛的應用。在解決碼間串擾和數據壓縮中也可應用。
⒊ 序貫解碼
序貫解碼是根據接收序列和編碼規則，在整個碼樹中搜索（既可以前進，也可以後退）出一條與接收序列距離（或其他量度）最小的一種演算法。由於它的解碼器的復雜性隨m值增大而線性增長，在實用中可以選用較大的m值（如20～40）以保證更高的可靠性。許多深空和海事通信系統都採用序貫解碼。

❷ 卷積碼的原理

DMT和卷積編碼調制在DSL中的應用

鍾曉建 潘貴敦 馬親民 梁小宇

�

(華中師范大學物理系武漢430079)

【摘要】討論了離散多音頻調制和網格編碼相結合的調制方式在DSL中的應用,離散多音頻調制DMT〔1〕是一種多載波調制技術，將傳輸數據根據各子帶信噪比按位分配到子帶上，使每個子帶碼元寬度大於多徑延遲。如果把調制和糾錯編碼結合起來，則可使誤碼率大大降低，是一種帶寬利用率較高的調制方式。

�關鍵詞：ADSL離散多音頻網格編碼〔2〕歐氏距離〔3〕離散傅立葉變換／逆變換

1引 言

� 隨著Internet技術的不斷發展,人們對傳輸數據的速度、質量要求越來越高,在當前為了有效地利用現有的資源——電話線，提出了DSL〔1〕(數字用戶線)的概念，使用話音頻率以上的頻帶(4 k~1.1 MHz)來調制高速數字信號,按照Δf=4.3125 kHz分割成一個個的子帶,由於Δf剛好是音頻的寬度，故命名為離散多音頻,DMT調制是基於離散傅立葉變換對並行數據進行調制解調的。隨著超大規模集成電路(VL SI)和數字信號處理(DSP)技術的不斷進步，用FFT實現實時DMT調制已付諸使用。但以往的調制解調系統，糾錯編碼與調制是各自獨立設計並實現的，解碼和解調也是如此，這樣解調器在接收信號是對信號作獨立硬判決，硬判決結果再送給解碼器解碼，這種硬判決會導致接收端信息的不可恢復的丟失，解決這個問題的方法是在接收端採用軟判決解碼。DSL技術中就是將DMT和網格編碼綜合設計，在白雜訊環境下比傳統技術的誤碼性能有了很大的提高。這種最佳的編碼調制系統是按照編碼序列的歐氏距離為設計的量度，這就要求將編碼器和調制器當作一個統一的整體進行綜合設計，使得編碼器和調制器級聯後產生的編碼信號序列具有最大的歐氏自由距離。從信號空間的角度看，這種最佳編碼調制的設計實際上是一種對信號空間的最佳分割。經過實驗分析，DMT和卷積編碼結合後的編碼增益比傳統編碼的編碼增益增加了8 dB。�

2xDSL接入設備體系結構

� 在ADSL的應用當中,其硬體體系結構大致是由線路介面、接收濾波、線路驅動、模擬前端以及DMT收發器這幾個模塊組成。其中DMT收發器在發端對數據進行復用、循環冗餘校驗、前向糾錯、子帶排序、卷積編碼、星座映射以及IFFT變換，送到模擬前端變換成模擬信號發送出去，而在收端是將模擬信號經過FFT變換、解映射、維特比解碼等一系列反變換，提交給上層。根據T1.413〔4〕標准，採用韋氏16狀態4維網格碼作為內碼，採用Reed�Solomon編碼作為前向糾錯碼，另外由於網格編碼對成塊的雜訊抵抗能力較差，因此在進行網格編碼之前將數據進行交織使雜訊分散。ADSL的DMT收發器框圖大致如圖1所示。

3DMT與卷積編碼調制原理

� 在ADSL的發送端,將數據分配到不同的子帶上,這種分配可以根據各個子帶的信噪比來確定分配的bit數。而ADSL系統為各個子帶建立並維持了一個比特數和增益大小的表，是在ATU-R一端計算出來並返回給局端。為保證後一子帶所帶的位數不小於前一子帶的位數，先對子帶進行排序，即子帶按信噪比大小從小到大進行排序。為了使編碼獲得的碼字有較大的歐氏自由距離，採用了四維TCM網格編碼，這樣位抽取是基於一對子帶的,因為一個子帶在空間上是二維的,一對相互正交的子帶在空間上則是四維的 ，相應的在解碼的時候也是一對一對的作維特比解碼。歐氏自由距離是在四維空間上計算出來的，這樣四維的陪集可以由兩個二維的陪集的聯合構成，即這樣四維TCM網格碼的歐氏自由距離可以由兩個二維星座圖的距離的平方和算出， 在解碼系統中，最可能發生錯誤的情況是在具有最小的平方歐氏距離的兩個序列�{an}和{bn}�之間，(前者是發送序列，後者是解碼序列)，這一最小平方歐氏距離常又稱為平方自由距離，記做：

��編碼的目的是為了使這個平方自由距離最大。

�網格編碼調制的通過一種特殊的信號映射可變成卷積碼的形式。這種映射的原理是將調制信號集分

割成子集，是的子集內的信號間具有更大的空間距離，用編碼效率為k/(k 1)的卷積碼選擇子集，用其餘位選擇子集中的點。在DSL數字用戶環路中用16狀態的4維網格編碼的編碼器結構如圖2所示。

其中的卷積編碼部分如圖3所示。

圖2中每兩個子帶抽取的位數z′=x y-1(x為第一個子帶所帶的位數，y為第二個子帶所帶的位數)。{uz′-1,uz′-2，…u1}為原碼，輸出的是經過卷積以及異或以後的編碼，為兩個二進制碼字，即{vz-y�,vz′-y-1，…v1,v0}和{wy-1,wy-2,…w1,w0}，這兩個二進制碼字將映射成兩個星座點。編碼演算法使星座點的兩個最低位決定星座點的二維陪集{v1,v0}和{w1,w0}實際上是這個上標的二進製表示。對於一幀中最後兩個碼字，為了使卷積編碼狀態{s3,s2,s1,s0}回到零狀態。讓編碼前的碼字的{u1,u2}={0,0}，則最後兩對子帶抽取的位數z′＝x y-3。

�

這樣編碼得出的信號有兩個基本特徵：

� (1)星座圖中所用的信號點數大於未編碼同種調制所需的點數(擴大了一倍)，這些附加的信號點為糾錯編碼提供冗餘度。

�(2)採用卷積碼在相繼的信號點之間引入某種依賴性，因而只有某些信號點序列才是允許出現的，這些允許的信號序列可以模型化為網路結構。可用網格圖來表述。

� 在接收端對接收序列進行維特比解碼〔4〕，即最大似然解碼，可以用網格圖求最相似的路徑來描述這種演算法，它依賴於有限狀態的馬爾可夫系統的描述，包括狀態變遷以及狀態變遷的輸出碼字。在四維TCM�編碼的基礎上，解碼時要對一對一對的數據進行解碼，計算碼距時也是以四維空間的歐氏距離為標准，取最相似的一條路徑。對於長度為L m的網格路徑(L為信息序列的長度，m表示後綴為m個0向量)接收序列為所有的網格路徑在零時刻發散於同一個初始狀態、收斂於第j時刻(j＝L m)的同一個最後一狀態。在理想狀況下，對於一個存儲量無限度的通道，可以將所有可能的路徑都記錄下來，然後選擇其中對數似然函數值最大的作為解碼結果。

對數似然函數是將接收序列判定為某條路徑的序列的條件概率的對數

��這里的對數似然函數取最大值，實際上是接收的碼序列與估計路徑的碼之間的距離取最小值，是基於歐氏空間距離來計算的。在這里維特比解碼演算法的核心是回退的觀點，採用動態規劃法存儲數據，如果對每條可能的路徑進行存儲的話，隨著解碼深度的增加，存儲量將成4的指數增長，這在現實條件下是不可能的。因為每個節點都有四個分支(二輸入十六狀態的網格圖)，因此我們對於j時刻到達的某一狀態

δi(i=1,2…，S-1)，進行加—比—選操作，即將所有可能前一時刻的狀態的最大似然函數∧j-1(δp)與當前接收的序列和前一狀態到當前狀態的估計碼的似然度相加，選擇其中最大的作為j時刻i狀

態的最大似然函數值，並在倖存序列j(δi)在原來的基礎上加上這條最優的路徑u〔δp→δi〕。這樣給出的演算法可以表述為：

� 變數／存儲：

� S—狀態數(DSL為16)；

� T—每一狀態的分支數(4)；

� j—時刻編號，即第j時刻

�對於用卷積編碼完畢的序列可以直接送到數字信號處理器中作IDFT〔5〕變換成串列數據了。每個子帶i的二進制碼字可以映射成星座圖上的復數點(Zi=ai jbi)，為了使輸出信號為實信號，頻域上的子帶i的復數值(i≥N′,N′=N/2)為

��Zi=conj�(ZN-i),(i≥N′，N′=N/2)

即取共軛復數，這樣經過離散傅立葉逆變換，得到時域信號：

��此信號經過並／串變換，再通過A／D變換，變成模擬信號送到線路上進行傳輸。

4模擬結果

� 我們在應用Itex公司的ADSL解決方案中，用該公司提供的局端模擬工具IADT對ADSL鏈路性能進

行模擬，得到ADSL每個子帶(從0~255)的信噪比，再根據這個預測值來確定每個子帶的位數和增益值。

從而建立一個與子帶一一對應的表，其線路預測的信噪比曲線如圖4所示。

我們可以看到，測得的線路上行速率為544

kbps，網路速率(去掉ADSL鏈路開銷)為448 kbps，下行鏈路速率為8 160 kbps，網路速率為7 616 kbps。

5總 結

� 本文描述了在帶寬受限的信道採用DMT和卷積編碼相結合的技術，將調制與糾錯編碼結為一體，高效利用了現有的帶寬。隨著ADSL技術的逐漸成熟，該編碼技術也正在應用於其它領域，如無線通信，針對其信道的衰減特性可以獲得較高的帶寬利用率。在具體硬體實現上,由於超大規模集成電路的發展，硬體已不再是信號處理的瓶頸了,如以上分析的維特比解碼,其對硬體的需求是隨著N的增大而迅速增加,需要上十萬的門電路實現，現已有單片的維特比解碼器，或是在特殊的應用中集成在一塊數字晶元中，同時完成RS編碼、交織、FFT變換等等。

�參考文獻

�

1Asymmetrical Digital Subscriber Lines(ADSL)�ITU-T�Recommendation G.992,Geneva,June,1999

2曹志剛，錢亞生.現代通信原理.北京：清華大學出版社

3Stephen G Wilson.digital Molation and Coding,○C1996 byPrentice�Hall,Inc

4ANSI T1.413�1998,COMMITTEE T1—Telecommunications Working Group T1E1.4 T1E1.4/98�007R5，1998

5John G Proakis.Digital Communications,Third edition,McGraw�Hill 1998

❸ 卷積碼的表示方法

描述卷積碼編碼器過程的方法有很多，如矩陣法、多項式、碼樹和網格圖等，這里我們主要介紹和卷積碼編碼器結構密切相關的多項式法，以及與卷積碼解碼密切相關的網格圖法。
結構圖多項式法就是由卷積碼的生成多項式直接得出其編碼器的結構圖。如前面例子中的（2，1，2）卷積碼的生成多項式矩陣為：G(D)=[1 ,1 ]
其中，D是延遲運算元，生成多項式的第一項為1 D ，表示輸出編碼的第一個碼元等於輸入碼元x（n）與前兩個時刻輸入的碼元x（n-1）、x（n-2）的模2和，同理第二項類似。 將編碼器寄存器中的內容組合（x（n-1）、x（n-2））定義為編碼器狀態。如仍以前面所舉的例子（2，1，2）為例，則該編碼器的狀態有四種：00，10，01和11，下面分別用a，b，c，d來代替。編碼器在每一個時鍾沿打入一個輸入信息x（n），因此圖示寄存器組合內容就變為（x（n），x（n-1））即狀態發生了轉移，並同時輸出G0（n）、G1（n）。由此我們可以將圖所示編碼過程用右圖所示的狀態圖表示。
編碼器
由圖所示，隨著信息序列不斷輸入，編碼器就不斷從一個狀態轉移到另一個狀態並同時輸出相應的碼序列，所以圖3所示狀態圖可以簡單直觀的描述編碼器的編碼過程。因此通過狀態圖 很容易給出輸入信息序列的編碼結果，假定輸入序列為110100，首先從零狀態開始即圖示a狀態，由於輸入信息為「1」，所以下一狀態為b並輸出「11」，繼續輸入信息「1」，由圖知下一狀態為d、輸出「01」……其它輸入信息依次類推，按照狀態轉移路徑a->b->d->c->b->c->a輸出其對應的編碼結果「110101001011」。
網格圖
狀態圖可以完整的描述編碼器的工作過程，但是其只能顯示狀態轉移的過程而不能顯示狀態轉移發生的時刻，由此引出用來表示卷積碼的另一種常用方法——網格圖。網格圖就是時 間與對應狀態的轉移圖（如圖），在網格圖中每一個點表示該時刻的狀態，狀態之間的連線表示狀態轉移。通過觀察網格圖可以發現在網格圖中輸入信息x（n）並沒有標出，但如觀察到轉移後的狀態表示（x（n），x（n-1））就可以發現輸入信息已經隱含在轉移後的狀態中。在圖中還可以發現兩個網格圖不同主要集中在轉移後狀態位置不同。重新排序結構（即所謂蝶型結構）是為了優化運算而設計的，因為其中蝶型與蝶型之間是相互獨立的。

❹ 什麼是卷積編碼

卷積碼是將k個信息比特編成n個比特，但k和n通常很小，特別適合以串列形式進行傳輸，時延小。
卷積碼定義：

若以（n,k,m）來描述卷積碼，其中k為每次輸入到卷積編碼器的bit數，n為每個k元組碼字對應的卷積碼輸出n元組碼字，m為編碼存儲度，也就是卷積編碼器的k元組的級數，稱m+1= K為編碼約束度m稱為約束長度。卷積碼將k元組輸入碼元編成n元組輸出碼元，但k和n通常很小，特別適合以串列形式進
卷積碼的編碼器
行 傳輸，時延小。與分組碼不同，卷積碼編碼生成的n元組元不僅與當前輸入的k元組有關，還與前面m-1個輸入的k元組有關，編碼過程中互相關聯的碼元個數為n*m。卷積碼的糾錯性能隨m的增加而增大，而差錯率隨N的增加而指數下降。在編碼器復雜性相同的情況下，卷積碼的性能優於分組碼。
編碼原理：
卷積碼編碼器
以二元碼為例，編碼器如圖。輸入信息序列為u=(u0，u1，…），其多項式表示為u(x)=u0+u1x+…+ulxl+…。編碼器的連接可用多項式表示為g(1,1)(x)=1+x+x2和g(1,2)(x)=1+x2，稱為碼 的子生成多項式。它們的系數矢量g(1,1)=(111）和g(1,2)=(101）稱作碼的子生成元。以子生成多項式為陣元構成的多項式矩陣G(x)=[g(1,1)(x),g(1,2)(x)]，稱為碼的生成多項式矩陣。

❺ 求大神指導卷積碼網格圖的畫法

先畫出狀態圖，由狀態圖來推導網格圖就很簡單了

❻ 卷積碼的過程

下面就讓我們來看看網格圖是如何描述卷積編碼過程的：仍以（2,1,2）為例，假定輸入序列為1011010100，起始狀態（零時刻）為狀態a（零狀態）。第一個有效時鍾沿來臨後，編碼器接收到輸入信息「1」，根據圖所示網格圖知該時刻（即時刻1）狀態為b，並輸出其對應的編碼結果「11」，同樣在下一個時刻（時刻2）接收到輸入信息「0」，狀態變為c並輸出「10」，接下來的輸入數據依次類推……，由此我們可以用網格圖作出該例子的卷積編碼過程，如圖5所示，其中兩個狀態連線之間的信息為輸出結果。

❼ 卷積碼有哪些圖形可以表述

卷積碼的表述方法有碼樹圖、狀態圖、網格圖。

❽ tcm中的網路圖和卷積碼的網路圖有何不同,為什麼

由於未編碼比特有兩種取值，TCM網格圖每個狀態有兩根線

❾ 什麼是解碼

解碼是編碼的逆過程，同時去掉比特流在傳播過程中混入的雜訊。利用解碼表把文字譯成一組組數碼或用解碼表將代表某一項信息的一系列信號譯成文字的過程稱之為解碼。
解碼器是電子技術中的一種多輸入多輸出的組合邏輯電路，負責將二進制代碼翻譯為特定的對象（如邏輯電平等），功能與編碼器相反。解碼器一般分為通用解碼器和數字顯示解碼器兩大類。
數字電路中，解碼器（如n線－2n線BCD解碼器）可以擔任多輸入多輸出邏輯門的角色，能將已編碼的輸入轉換成已編碼的輸出，這里輸入和輸出的編碼是不同的。
輸入使能信號必須接在解碼器上使其正常工作，否則輸出將會是一個無效的碼字。解碼在多路復用、七段數碼管和內存地址解碼等應用中是必要的。

❿ 採用卷積編碼器當輸入信息位10110時輸出編碼位多少

參考資料：http://hi..com/wuruide/blog/item/33d28bbf1b34940818d81f26.html
在一個二進制分組碼（n,k）當中，包含k個信息位，碼組長度為n，每個碼組的（n-k）個校驗位僅與本碼組的k個信息位有關，而與其它碼組無關。為了達到一定的糾錯能力和編碼效率（＝k/n），分組碼的碼組長度n通常都比較大。編譯碼時必須把整個信息碼組存儲起來，由此產生的延時隨著n的增加而線性增加。
為了減少這個延遲，人們提出了各種解決方案，其中卷積碼就是一種較好的信道編碼方式。這種編碼方式同樣是把k個信息比特編成n個比特，但k和n通常很小，特別適宜於以串列形式傳輸信息，減小了編碼延時。
與分組碼不同，卷積碼中編碼後的n個碼元不僅與當前段的k個信息有關，而且也與前面（N-1）段的信息有關，編碼過程中相互關聯的碼元為nN個。因此，這N時間內的碼元數目nN通常被稱為這種碼的約束長度。卷積碼的糾錯能力隨著N的增加而增大，在編碼器復雜程度相同的情況下，卷段積碼的性能優於分組碼。另一點不同的是：分組碼有嚴格的代數結構，但卷積碼至今尚未找到如此嚴密的數學手段，把糾錯性能與碼的結構十分有規律地聯系起來，目前大都採用計算機來搜索好碼。
下面通過一個例子來簡要說明卷積碼的編碼工作原理。正如前面已經指出的那樣，卷積碼編碼器在一段時間內輸出的n位碼，不僅與本段時間內的k位信息位有關，而且還與前面m段規定時間內的信息位有關，這里的m＝N-1通常用（n，k，m）表示卷積碼（注意：有些文獻中也用（n，k，N）來表示卷積碼）。圖8-8就是一個卷積碼的編碼器，該卷積碼的n = 2，k = 1，m = 2，因此，它的約束長度nN = n×(m+1) = 2×3 = 6。
（2，1，2）卷集碼編碼器
在圖8-8中，與為移位寄存器，它們的起始狀態均為零。、與、、之間的關系如下：
（8-41）
假如輸入的信息為D = [11010]，為了使信息D全部通過移位寄存器，還必須在信息位後面加3個零。表8-9列出了對信息D進行卷積編碼時的狀態。
表8-9 信息D進行卷積編碼時的狀態 輸入信息D
1
1
0
1
0
0
0
0
b3b2
0 0
0 1
1 1
1 0
0 1
1 0
0 0
0 0
輸出C1C2
1 1
0 1
0 1
0 0
1 0
1 1
0 0
0 0
描述卷積碼的方法有兩類，也就是圖解表示和解析表示。解析表示較為抽象難懂，而用圖解表示法來描述卷積碼簡單明了。常用的圖解描述法包括樹狀圖、網格圖和狀態圖等。基於篇幅原因這里就不詳細介紹了。
卷積碼的解碼方法可分為代數解碼和概率解碼兩大類。代數解碼方法完全基於它的代數結構，也就是利用生成矩陣和監督矩陣來解碼，在代數解碼中最主要的方法就是大數邏輯解碼。概率解碼比較常用的有兩種，一種叫序列解碼，另一種叫維特比解碼法。雖然代數解碼所要求的設備簡單，運算量小，但其解碼性能（誤碼）要比概率解碼方法差許多。因此，目前在數字通信的前向糾錯中廣泛使用的是概率解碼方法。