卷積碼編解碼規則
⑴ 卷積碼的過程
下面就讓我們來看看網格圖是如何描述卷積編碼過程的：仍以（2,1,2）為例，假定輸入序列為1011010100，起始狀態（零時刻）為狀態a（零狀態）。第一個有效時鍾沿來臨後，編碼器接收到輸入信息「1」，根據圖所示網格圖知該時刻（即時刻1）狀態為b，並輸出其對應的編碼結果「11」，同樣在下一個時刻（時刻2）接收到輸入信息「0」，狀態變為c並輸出「10」，接下來的輸入數據依次類推……，由此我們可以用網格圖作出該例子的卷積編碼過程，如圖5所示，其中兩個狀態連線之間的信息為輸出結果。
⑵ 卷積碼的表示方法
描述卷積碼編碼器過程的方法有很多，如矩陣法、多項式、碼樹和網格圖等，這里我們主要介紹和卷積碼編碼器結構密切相關的多項式法，以及與卷積碼解碼密切相關的網格圖法。
結構圖多項式法就是由卷積碼的生成多項式直接得出其編碼器的結構圖。如前面例子中的（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））就可以發現輸入信息已經隱含在轉移後的狀態中。在圖中還可以發現兩個網格圖不同主要集中在轉移後狀態位置不同。重新排序結構（即所謂蝶型結構）是為了優化運算而設計的，因為其中蝶型與蝶型之間是相互獨立的。
⑶ 卷積碼的原理
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
charinput[10]={0,0,1,1,1,0,1,1,1,1};
charoutput[5]={0};
intr1=0,r2=0;
inti;
for(i=0;i<5;i++)
{
output[i]=(input[2*i]+r1+r2)&1;
r2=r1;
r1=output[i];
}
for(i=0;i<5;i++)
printf("%d",output[i]);
printf("
");
⑸ 卷積碼的編碼原理
卷積碼編碼器
以二元碼為例，編碼器如圖。輸入信息序列為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)]，稱為碼的生成多項式矩陣。
⑹ 信息經卷積編碼器之後的信息速率如何求
卷積碼
卷積碼是一種差錯控制編碼，由P.Elias於1955年發明。因為數據與二進制多項式滑動相關故稱卷積碼。卷積碼在通信系統中應用廣泛，如IS-95，TD-SCDMA，WCDMA，IEEE 802.11及衛星等系統中均使用了卷積碼。
卷積碼使用（n，k，L）表示，碼率為R。
n為輸出碼字；
k為輸入的比特信息；
L為約束長度，也稱為記憶深度。
R表示為R = k/n。
卷積碼是一種有記憶的糾錯碼，編碼規則是將k個信息比特編碼形成n個比特，編碼後的n個碼元不但與當前輸入的k個信息有關，仍與之前的L-1組的信息有關，其結構如下圖1所示，圖1來自Goldsmith的著作。
圖中表示有L級信息比特，每次輸入k比特信息，共有k*L個比特，每次輸出n個比特信息，可以明顯地看出該n個比特信息不僅與當前輸入的k個比特信息有關，與之前L-1組信息比特也有關，所以卷積碼是有記憶的編碼，記憶深度為L。
註：此處與其他常見表示方法不同，此處將輸入的比特做了緩存，所以記憶深度不一樣，L看寄存器的個數確定。
2、卷積碼表示方法
圖2是輸出碼長n=2，記憶深度L為2，輸入比特k=1的，（2,1,2）卷積碼編碼器。用該例說明卷積碼的以下幾種表示方法。
2.1 生成多項式
生成多項式使用K-1階的多項式描述編碼器的移位寄存器和模二加法器的連接狀態。每個模二加法器的連接可表示成一個多項式。多項式的次數輸入的階次為0，其餘按寄存器數的移位次數依次遞增。如上圖
輸出1： g1(x) = 1 + x + x^2
輸出2： g2(x) = 1 + x^2
以下是IEEE 802.11標准中的卷積碼編碼器，生成多項式分別為：
輸出1： g1(x) = 1 + x^2 + x^3+ x^5 + x^6
輸出2： g2(x) = 1 + x + x^2 +x^3 + x^6
2.2 狀態圖
狀態圖是關於系統狀態變化的描述，它將由系統的輸入，根據當前的系統狀態，影響系統的輸出。卷積碼編碼器存儲的L-1段消息，既要因新的消息輸入而改變，又要影響當前的編碼輸出，把卷積碼編碼器的移位寄存器中任一時刻所存儲的信息稱為卷積碼編碼器的一個狀態。
（n,k,L）卷積碼共有2^(k*(L-1))個狀態，每次輸入k比特只有2^k種狀態變化，所以，每個狀態只能轉移到全部狀態的某個子集(2^k個狀態)中去，每個狀態也只能由全部狀態的某個子集（2^k個狀態）轉移而來。
（2,1,2）卷積碼編碼器包含2級移位寄存器和2個模2加法器。2級移位寄存器共有2^2=4種不同狀態，定義為S0(00)、S1(01)、S2(10)和S3(11)四種狀態。在每個時刻，輸入的1個比特信息，當前狀態將轉為4種狀態中的任何一種。
狀態表類似查找表，原理即根據當前的輸入和當前的狀態，可以從表中查得輸出信息。圖4為卷積碼的狀態轉移圖，圖中的狀態轉移表示「輸入/輸出1輸出2」。
卷積編碼碼率是什麼
為了支持高效、靈活的傳輸方式，信道編碼技術需要考慮到各種不同的傳輸碼率和調制方式，兼顧HARQ重傳技術以及鏈路自適應技術。為此，信道編碼技術常常使用打孔或者重復的方法，從編碼比特流中提取預定長度比特序列，這個過程稱為速率匹配。研究表明，均勻並且對稱的打孔或者重復模式能夠獲得最優的速率匹配性能。均勻的打孔或者重復模式是指打孔或者重復的比特位置的分布是均勻的，以避免連續的比特位置上的比特被打孔或者重復。
TD-LTE中卷積碼速率匹配的原理如圖3-31所示。卷積編碼器輸出的第一、二和三校驗比特流分別獨立地交織後，被比特收集單元依次收集，也就是交織後的第一、二和三校驗比特流依次輸入到緩沖器中。每次傳輸時，比特選擇單元從緩沖器頭部的比特開始逐位讀取，直至達到預定的比特數。當讀取到緩沖器的尾部，仍然沒有達到預定的比特數時，比特選擇單元自動跳至緩沖器的頭部繼續讀取。卷積碼的這種基於緩沖器的速率匹配的過程，被稱為循環緩沖器速率匹配（CBRM）。
TD-LTE採用的卷積編碼器是碼率為1/3的最優距離譜編碼器，內嵌碼率為1/2的最優距離譜編碼器，這種編碼編碼方法能夠保證獲得優異的糾錯性能。如圖3-31所示，卷積碼速率匹配時，比特收集單元在收集3個比特流時，3個比特流是依次被收集，這樣能夠保證卷積碼通過速率匹配得到碼率為1/2碼字時，其距離譜仍然是最優的。
TD-LTE卷積碼速率匹配採用的交織器是一個簡單的行列交織器，如圖3-32所示，交織器執行按行寫入、內部列交織、按列讀出的簡單操作。行列交織器的列數固定為32，交織前，需要根據每個比特流的長度，計算得到行列交織器的行數，並根據需要在行列交織器的第一行的頭部進行補零操作。在基於循環緩沖器進行速率匹配時，交織器的使用能夠保證卷積碼的打孔或者重復模式是均勻的，從而獲得優異的卷積碼速率匹配性能。另外，由於卷積碼和Turbo碼採用了一致的速率匹配方法，因此基站和終端能夠採用一致的演算法實現卷積碼和Turbo碼的速率匹配。
卷積編碼1/2碼率是什麼
（1）對輸入的數據進行卷積編碼，編碼速率為1/2，即每輸入1個比特編碼輸出2個比特。
（2）將每次編碼輸出的2個比特量化為相應的數值，通過每一組數值計算出該組4個狀態（s0，s1，s2，s3）的分支度量值，即BM值。
（3）進行加比選（ACS）運算，同時保存路徑信息。首先在0時刻給4個狀態（s0，s1，s2，s3）賦初始路徑向量值（PM）：假如起始點為狀態s0，則狀態s0的初始路徑向量值為PM0=100（該數值根據實際的情況來定，如回溯深度和分支度量值等，以便計算），狀態s1、狀態s2、狀態s3的初始路徑向量賦值為PM1=PM2=PM3=0。
（4）ACS過程。因為到達每一個狀態有兩條路徑（如圖3），例如到達狀態s0（00）的兩條路徑分別是s0（00）和s1（01），從中選出到達s0路徑度量值最大的一條路徑作為倖存路徑。如圖2，若從0時刻到1時刻：BM0=-8，BM1=0，max{PM0+BM0，PM1+BM1}=PM0+BM0=92，所以1時刻到達狀態s0的保留路徑為0時刻從狀態s0來的路徑，從而更新1時刻s0的PM0=92；同時由於1時刻到達s0的是「0」路徑，所以保存的該時刻s0的路徑信息是0（若是「1」路徑，則保存的該時刻s0的路徑信息為1）。以此類推，可求出該時刻到達狀態s1、s2、s3的倖存路徑，存儲該路徑信息，更新其路徑度量值PM。
（5）輸出判決（OD），即回溯過程，就是根據回溯深度以及ACS過程中所保存的PM值和倖存路徑信息進行相應的演算法回溯出解碼結果。