卷積碼編碼及譯碼實(shí)驗(yàn) 淺談卷積編碼下的FPGA實(shí)現(xiàn)

卷積編碼是現(xiàn)代數(shù)字通信系統(tǒng)中常見(jiàn)的一種前向糾錯(cuò)碼，區(qū)別于常規(guī)的線性分組碼，卷積編碼的碼字輸出不僅與當(dāng)前時(shí)刻的信息符號(hào)輸入有關(guān)，還與之前輸入的信息符號(hào)有關(guān)。

本文主要是關(guān)于卷積碼編碼及譯碼實(shí)驗(yàn)的相關(guān)介紹，并著重分析闡述了基于卷積編碼下的FPGA實(shí)現(xiàn)。

卷積編碼

卷積碼的編碼分為兩類(lèi)：前饋和反饋，在每類(lèi)中又可分為系統(tǒng)和非系統(tǒng)形式。我們這里只考慮非系統(tǒng)形式的前饋編碼器?！?/p>

上圖是WLAN 802.11a協(xié)議中采用的卷積編碼器結(jié)構(gòu)，輸入比特k=1，輸出n=2，存儲(chǔ)器長(zhǎng)度m=6，編碼輸出不僅與當(dāng)前輸入有關(guān)，還與存儲(chǔ)器存儲(chǔ)的之前的輸入數(shù)據(jù)有關(guān)，具體由之前的哪些數(shù)據(jù)得到編碼輸出呢，由生成多項(xiàng)式確定其連接關(guān)系。這里，生成多項(xiàng)式為g0=133（八進(jìn)制）和g1=171（八進(jìn)制）（右邊是最高位），輸出數(shù)據(jù)A的生成多項(xiàng)式為：

輸出數(shù)據(jù)B的生成多項(xiàng)式為：

生成多項(xiàng)式確定了卷積編碼器輸出的連接關(guān)系。根據(jù)多項(xiàng)式的系數(shù)，在相應(yīng)項(xiàng)進(jìn)行連接。生成多項(xiàng)式寫(xiě)成二進(jìn)制序列的形式分別為：g0 = ［1 0 1 1 0 1 1］和g1 = ［1 1 1 1 0 0 1］（右邊是最高位）。我們假設(shè)信息序列u，兩個(gè)編碼器輸出序列分別為v（0）和v（1），編碼器可以看成一個(gè)線性系統(tǒng)，系統(tǒng)的信道響應(yīng)脈沖最多持續(xù)m+1個(gè)時(shí)間單元，編碼輸出可以寫(xiě)成編碼輸入與信道脈沖響應(yīng)的卷積（即生成多項(xiàng)式），即

其中需要注意的是，所有的加法都是模2加運(yùn)算。

卷積碼編碼及譯碼實(shí)驗(yàn)

基本原理

1、卷積碼編碼

卷積碼是一種糾錯(cuò)編碼，它將輸入的k個(gè)信息比特編成n個(gè)比特輸出，特別適合以串行形式進(jìn)行傳輸，時(shí)延小。卷積碼編碼器的形式如圖17-1所示，它包括：一個(gè)由N段組成的輸入移位寄存器，每段有k段，共Nk個(gè)寄存器;一組n個(gè)模2和相加器;一個(gè)由n級(jí)組成的輸出移位寄存器，對(duì)應(yīng)于每段k個(gè)比特的輸入序列，輸出n個(gè)比特。

由圖17-1可以看到，n個(gè)輸出比特不僅與當(dāng)前的k個(gè)輸入信息有關(guān)，還與前（N-1）k個(gè)信息有關(guān)。通常將N稱(chēng)為約束長(zhǎng)度（有的書(shū)中也把約束長(zhǎng)度定為nN或N-1）。常把卷積碼

記為：（n 、k 、N ），當(dāng)k =1時(shí)，N -1就是寄存器的個(gè)數(shù)。編碼效率定義為：

/c R k n = （17-1） 卷積碼的表示方法有圖解表示法和解析表示法兩種：解析法，它可以用數(shù)學(xué)公式直接表達(dá)，包括離散卷積法、生成矩陣法、碼生成多項(xiàng)式法;圖解表示法，包括樹(shù)狀圖、網(wǎng)絡(luò)圖和狀態(tài)圖（最的圖形表達(dá)形式）三種。一般情況下，解析表示法比較適合于描述編碼過(guò)程，而圖形法比較適合于描述譯碼。

（1）圖解表示法

（2）解析法

下面以（2，1，3）卷積編碼器為例詳細(xì)講述卷積碼的產(chǎn)生原理和表示方法。（2，1，3）卷積碼的約束長(zhǎng)度為3，編碼速率為1/2，編碼器的結(jié)構(gòu)如圖17-2所示。

j

j

圖17-2 （2，1，3）卷積編碼器

這里我們主要介紹碼多項(xiàng)式法。我們可以用多項(xiàng)式來(lái)表示輸入序列、輸出序列、編碼器中移位寄存器與模2和的連接關(guān)系。

為了簡(jiǎn)化，仍以上述（2，1，3）卷積碼為例，例如輸入序列1011100…可表示為 （）2341M x x x x =++++ （17-2） 在一般情況下，輸入序列可表示為

（）231234M x m m x m x m x =++++ （17-3） 這里m 1，m 2，m 3，m 4…為二進(jìn)制表示（1或0）的輸入序列。x 稱(chēng)為移位算子或延遲算子，它標(biāo)志著位置狀況。

我們可以用多項(xiàng)式表示移位寄存器各級(jí)與模2加的連接關(guān)系。若某級(jí)寄存器與模2加相連接，則相應(yīng)多項(xiàng)式項(xiàng)的系數(shù)為1;反之，無(wú)連接線時(shí)的相應(yīng)多項(xiàng)式項(xiàng)系數(shù)為0，以圖17-2編碼器為例，相應(yīng)的生成多項(xiàng)式為

（）（）212211g x x x g x x =++???=+?? （17-4）

利用生成多項(xiàng)式與輸入序列多項(xiàng)式相乘，可以產(chǎn)生輸出序列多項(xiàng)式，即得到輸出序列。

（）（）（）（）（）

234211234345245646

1111P x M x g x x x x x x x x x x x x x x x x x x x x ==+++++=+++++++++++=+++

（17-5）

（）（）（）

（）（）2234211P x M x g x x x x x ==++++ （17-6）

對(duì)應(yīng)的碼組為

（）（）

（）（）（）（）461135622121110010111001011，11，10，00，01，10，01，11P x x x x p P x x x x p P p p =+++?==+++?===

（17-7）

2、卷積碼譯碼

卷積碼的譯碼方法有兩類(lèi)：一類(lèi)是大數(shù)邏輯譯碼，又稱(chēng)門(mén)限譯碼;另一類(lèi)是概率譯碼，概率譯碼又能分為維特比譯碼和序列譯碼兩種。門(mén)限譯碼方法是以分組理論為基礎(chǔ)的，其譯碼設(shè)備簡(jiǎn)單，速度快，但其誤碼性能要比概率譯碼法差。這里我們主要介紹維特比譯碼。

維特比（Viterbi ）譯碼和序列譯碼都屬于概率譯碼。當(dāng)卷積碼的約束長(zhǎng)度不太大時(shí)，與序列譯碼相比，維特比譯碼器比較簡(jiǎn)單，計(jì)算速度更快。維特比譯碼算法，以后簡(jiǎn)稱(chēng)VB 算法。

采用概率譯碼的一種基本想法是：把已接收序列與所有可能的發(fā)送序列做比較，選擇其中碼距最小的一個(gè)序列做為發(fā)送序列。如果發(fā)送L 組信息比特對(duì)于（，）n k 卷積碼來(lái)說(shuō)，可能發(fā)送的序列有2kL 個(gè)，計(jì)算機(jī)或譯碼器需存儲(chǔ)這些序列并進(jìn)行比較，以找到碼距最小的那個(gè)序列。當(dāng)傳信率和信息組數(shù)L 較大時(shí)，使得譯碼器難以實(shí)現(xiàn)。VB 算法則對(duì)上述概率譯碼（又稱(chēng)最大似然解碼）做了簡(jiǎn)化，以至成為了一種實(shí)用化的概率算法。它并不是在網(wǎng)格圖上一次比較所有可能的2kL 條路徑（序列），而是接收一段，計(jì)算和比較一段，選擇一段有最大似然可能的碼段，從而達(dá)到整個(gè)碼序列是一個(gè)有最大似然值的序列。

下面將用圖17-2的（2，1，3）卷積碼編碼器所編出的碼為例，來(lái)說(shuō)明維特比解碼的方法和運(yùn)作過(guò)程。為了能說(shuō)明解碼過(guò)程，這里給出該碼的狀態(tài)圖，如圖17-5所示。維特比譯碼需要利用圖來(lái)說(shuō)明譯碼過(guò)程。根據(jù)前面的畫(huà)網(wǎng)格的例子，讀者可檢驗(yàn)和畫(huà)個(gè)該碼網(wǎng)格圖如圖17-4所示。該圖設(shè)輸入信息數(shù)目L=5，所以畫(huà)有L+N=8個(gè)時(shí)間單位（節(jié)點(diǎn)）。這里設(shè)編碼器從a 狀態(tài)開(kāi)始運(yùn)作。該網(wǎng)格圖的每一條路徑都對(duì)應(yīng)著不同的輸入信息序列。由于所有的可能輸入信息序列共有2kL 個(gè)，因而網(wǎng)格圖中所有可能路徑也有2kL 條。這里節(jié)

a=00，b=01，c=10，d=11。

設(shè)輸入編碼器的信息序列為（1 1 0 1 1 0 0 0 ），則由編碼器輸出的序列Y=（1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 ），編碼器的狀態(tài)轉(zhuǎn)移路線為abcdbdca。若收到的序列R=（0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 ），對(duì)照網(wǎng)格圖來(lái)說(shuō)明維特比譯碼的方法。

由于該卷積碼的約束長(zhǎng)度為6位，因此先選擇接收序列的前6位序列

R=（0 1 0 1 0 1）

1

同到達(dá)第3時(shí)刻可能的8個(gè)碼序列（即8條路徑）進(jìn)行比較，并計(jì)算出碼距。該例中到達(dá)第3時(shí)刻a點(diǎn)的路徑序列是（0 0 0 0 0 0）和（1 1 1 0 1 1 ），它們與

R的距離分別是3和4;到

1

達(dá)第3時(shí)刻b點(diǎn)的路徑序列是（0 0 0 0 1 1）和（1 1 1 0 0 0），它們與

R的距離分別是3和4，

1

到達(dá)第3時(shí)刻c點(diǎn)的路徑序列是（0 0 1 1 1 0）和（1 1 0 1 1 0），與

R的距離分別是4和1;

1

到達(dá)第3時(shí)刻d點(diǎn)的路徑序列是（0 0 1 1 0 1）和（1 1 0 1 1 0），與

R的距離分別是2和3。

1

上述每個(gè)節(jié)點(diǎn)都保留碼距較小的路徑為幸存路徑，所以幸存路徑碼序列是（0 0 0 0 0 0）、（0 0 0 0 1 1）、（1 1 0 1 0 1）和（0 0 1 1 0 1），如圖17-6（a）所示。用與上面類(lèi)同的方法可以得到第4、5、6、7時(shí)刻的幸存路徑。需指出對(duì)于某一個(gè)節(jié)點(diǎn)而言比較兩條路徑與接收序列的累計(jì)碼距時(shí)，若發(fā)生兩個(gè)碼距值相等，則可以任選一路徑作為幸存路徑，此時(shí)不會(huì)影響最終的譯碼結(jié)果。圖17-6（b）給出了第5時(shí)刻的幸存路徑，讀者可自行驗(yàn)證。在碼的終了時(shí)刻a狀態(tài)，得到一根幸存路徑，如圖17-6（c）所示。由此看到譯碼器輸出是‘R=（1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0），即可變換成序列（1 1 0 1 1 0 0 0），恢復(fù)了發(fā)端原始信息。比較’R和R序列，可以看到在譯碼過(guò)程中己糾正了在碼序列第1和第7位上的差錯(cuò)。當(dāng)然，差錯(cuò)出現(xiàn)太頻繁，以至超出卷積碼的糾錯(cuò)能力，則會(huì)發(fā)生誤糾，這是不希望的。

FPGA實(shí)現(xiàn)

這里，采用verilog語(yǔ)言對(duì)編碼過(guò)程進(jìn)行描述。通過(guò)狀態(tài)機(jī)控制編碼的過(guò)程，設(shè)置有三種狀態(tài)：IDLE，ENCODING，CLEAR。通常卷積編碼以數(shù)據(jù)塊為單元，逐塊進(jìn)行編碼的。當(dāng)待編碼的數(shù)據(jù)塊未到達(dá)編碼單元時(shí)，狀態(tài)機(jī)處于IDLE態(tài)，即空閑狀態(tài)，不做任何處理。當(dāng)數(shù)據(jù)塊到來(lái)時(shí)，存在一個(gè)觸發(fā)信號(hào)，讓狀態(tài)機(jī)開(kāi)始進(jìn)入ENCODING狀態(tài)，即編碼狀態(tài)，編碼狀態(tài)持續(xù)的時(shí)間為輸入的數(shù)據(jù)塊的長(zhǎng)度。此外，狀態(tài)機(jī)還設(shè)置有CLEAR態(tài)，因?yàn)樵诰矸e編碼中，還有尾比特需要輸出，這時(shí)輸入看做全0輸入，存儲(chǔ)器逐漸清空，持續(xù)時(shí)間為尾比特的長(zhǎng)度。這一步完成后，狀態(tài)機(jī)重新回到IDLE態(tài)，等待下一個(gè)數(shù)據(jù)塊的到來(lái)。代碼如下：

conv_encoder（

input clk，

input rst_n，

input e_start_i， //數(shù)據(jù)起始信號(hào)，比數(shù)據(jù)uncoded_bits第一個(gè)符號(hào)早一個(gè)時(shí)鐘，作為編碼狀態(tài)機(jī)的啟動(dòng)信號(hào)

input uncoded_bits，

output reg e_start_o，

output reg ［1:0］ coded_bits

）;

% 常量定義

parameter UNCODED_BLOCK_LEN = 100; //未編碼的數(shù)據(jù)塊長(zhǎng)度

parameter CODED_BLOCK_LEN = 106; //編碼后的單路數(shù)據(jù)塊長(zhǎng)度

% 狀態(tài)機(jī)定義

parameter IDLE = 3‘b001;

parameter ENCODING = 3’b010;

parameter CLEAR = 3‘b100;

reg ［2:0］ state;

//

reg ［7:0］ datain_cnt;

reg ［5:0］ shift_reg;

//

wire encoder_clear_start;

wire encoder_end;

wire encoder_enable;

assign encoder_clear_start = （datain_cnt == UNCODED_BLOCK_LEN -1）;

assign encoder_end = （datain_cnt == CODED_BLOCK_LEN -1）;

assign encoder_enable = （state ！= IDLE）;

/*********************************************************************/

// 卷積編碼狀態(tài)機(jī)

/*********************************************************************/

always @（posedge clk）

begin

if（！rst_n）

state 《= IDLE;

else begin

case（state）

IDLE： state 《= e_start_i ？ ENCODING ： IDLE;

ENCODING： state 《= encoder_clear_start ？ CLEAR ： ENCODING;

CLEAR： state 《= encoder_end ？ IDLE ： CLEAR;

default： state 《= IDLE;

endcase

end

end

/*********************************************************************/

// 符號(hào)計(jì)數(shù)器

/*********************************************************************/

always @（posedge clk）

begin

if（！rst_n）

datain_cnt 《= 8’d0;

else

datain_cnt 《= encoder_enable ？ （datain_cnt + 1‘b1） ： 8’d0;

end

/*********************************************************************/

// 移位寄存器更新

/*********************************************************************/

always @（posedge clk）

begin

if（！rst_n）

shift_reg 《= 6‘d0;

else

shift_reg 《= encoder_enable ？ {shift_reg［4:0］， uncoded_bits} ： 6’d0;

end

/*********************************************************************/

// 編碼結(jié)果輸出

/*********************************************************************/

always @（posedge clk）

begin

if（！rst_n）

coded_bits 《= 2‘d0;

else begin

case（state）

IDLE：

coded_bits 《= 2’d0;

CODING：

begin

coded_bits［0］ 《= shift_reg［5］ ^ shift_reg［4］ ^ shift_reg［2］ ^ shift_reg［1］ ^ uncoded_bits;

coded_bits［1］ 《= shift_reg［5］ ^ shift_reg［2］ ^ shift_reg［1］ ^ shift_reg［0］ ^uncoded_bits;

end

CLEAR：

begin

coded_bits［0］ 《= shift_reg［5］ ^ shift_reg［4］ ^ shift_reg［2］ ^ shift_reg［1］;

coded_bits［1］ 《= shift_reg［5］ ^ shift_reg［2］ ^ shift_reg［1］ ^ shift_reg［0］;

end

default：

coded_bits 《= 2‘d0;

endcase

end

end

/*********************************************************************/

// 啟動(dòng)信號(hào)輸出

/*********************************************************************/

always @（posedge clk_fpga）

begin

if（！rst_n）

e_start_o 《= 1’b0;

else begin

e_start_o 《= e_start_i;

end

end

結(jié)語(yǔ)

關(guān)于卷積碼編碼及譯碼實(shí)驗(yàn)的相關(guān)介紹就到這了，如有不足之處歡迎指正。

相關(guān)閱讀推薦：什么是卷積碼

相關(guān)閱讀推薦：卷積編碼是什么