無線通信系統(tǒng)-FFT與信道譯碼VLSI設(shè)計 課件 第6章 卷積碼并行列表譯碼算法與硬件結(jié)構(gòu)設(shè)計

第6章卷積碼并行列表譯碼算法與硬件結(jié)構(gòu)設(shè)計6.1卷積碼并行列表譯碼方法6.2基于路徑標(biāo)識的非咬尾卷積碼并行列表譯碼算法6.3并行列表譯碼器的硬件結(jié)構(gòu)設(shè)計6.4理論分析與硬件測試本章小結(jié)

6.1卷積碼并行列表譯碼方法

考慮一個表示為(c,1,u)的卷積碼，其編碼器中包含一個u級移位寄存器，并對每一個輸入比特相應(yīng)產(chǎn)生c個輸出比特，因此編碼碼率為1/c。圖6.1以(2,1,2)卷積碼為例，對卷積碼編碼器結(jié)構(gòu)以及譯碼網(wǎng)格圖進(jìn)行了說明。

圖6.1卷積碼編碼器結(jié)構(gòu)與相應(yīng)的譯碼網(wǎng)格圖

圖6.1卷積碼編碼器結(jié)構(gòu)與相應(yīng)的譯碼網(wǎng)格圖

6.1.1非咬尾卷積碼的列表譯碼

為了在路徑回溯階段并行輸出多條信息序列，并行列表譯碼在前向遞推過程中需要保留到達(dá)每網(wǎng)格每一級每個狀態(tài)的L條最優(yōu)路徑，這里L(fēng)為列表長度。用

表示連結(jié)網(wǎng)格第n-1級狀態(tài)sk與第n級狀態(tài)s的分支度量，其中

；定義

表示連結(jié)初始狀態(tài)與網(wǎng)格第n級狀態(tài)s的第l+1條最優(yōu)路徑的路徑度量。在非咬尾卷積碼對應(yīng)的網(wǎng)格中，初始狀態(tài)確定為0狀態(tài)，因此路徑度量在網(wǎng)格第

級初始化為：

完成初始化操作后，對于

路徑度量

在前向遞推過程中按照如下方式進(jìn)行計算：

其中

表示第n級網(wǎng)格狀態(tài)s的M個前序狀態(tài)索引，

表示到達(dá)每個狀態(tài)的L條路徑的路徑次序。當(dāng)l>0時，參數(shù)k,j進(jìn)一步滿足

在(6.3)中，

作為狀態(tài)序號，表示到達(dá)網(wǎng)格第n級狀態(tài)s的第l+1條最優(yōu)路徑在網(wǎng)格第n-1級經(jīng)過s的前序狀態(tài)

，而

作為路徑次序序號，對應(yīng)于路徑在該前序狀態(tài)的路徑次序。上述前向遞推過程可以用圖示的方式進(jìn)行描述，如圖6.2(a)所示。定義2u×L維矩陣Kn和Rn，它們分別為網(wǎng)格第

級的狀態(tài)索引矩陣和路徑次序矩陣，用于存儲前向遞推過程中計算得到的參數(shù)

：

圖6.2并行列表譯碼算法的前向遞推與路徑回溯操作

6.1.2咬尾卷積碼的列表譯碼

咬尾卷積碼只滿足網(wǎng)格起始狀態(tài)與結(jié)束狀態(tài)相同，但具體的起始或終止?fàn)顟B(tài)是未知的。因此在咬尾卷積碼網(wǎng)格中，連結(jié)未知初始狀態(tài)與終止?fàn)顟B(tài)的最優(yōu)路徑需要從2u個子網(wǎng)格包含的所有路徑中選出。根據(jù)這一定義，對咬尾卷積碼執(zhí)行列表長度為L的列表譯碼，首先應(yīng)當(dāng)搜索出每個子網(wǎng)格中的

條最優(yōu)路徑，然后再從所得的全部2uL條候選路徑中選出最優(yōu)的L條，并輸出其對應(yīng)的信息序列。為了降低譯碼復(fù)雜度，單次與多次狀態(tài)估計方案通過給出初始狀態(tài)的一個或一組估計值來使譯碼操作只涉及到少數(shù)子網(wǎng)格，以此來減小信息序列的搜索空間。

這樣一來，咬尾卷積碼列表譯碼器可以在非咬尾卷積碼列表譯碼器的基礎(chǔ)上通過添加初始狀態(tài)估計單元來實(shí)現(xiàn)。用

表示未知初始狀態(tài)的第l=1個最優(yōu)估計，這里的“第l+1個最優(yōu)”表示以

為初始l狀態(tài)的咬尾路徑是全部2u條咬尾路徑中的第l+1條最優(yōu)路徑。進(jìn)一步令

表示在以s為初始狀態(tài)的子網(wǎng)格中通過列表譯碼確定的L條最優(yōu)路徑，用

表示咬尾卷積碼網(wǎng)格中的第l+1條全局最優(yōu)路徑，則

6.2基于路徑標(biāo)識的非咬尾卷積碼并行列表譯碼算法

在遞歸執(zhí)行(6.6)來完成對pl的路徑回溯過程中，我們可以得到路徑次序序列

，它描述了pl在網(wǎng)格每一級的路徑次序。對路徑次序序列進(jìn)行進(jìn)一步研究，可以發(fā)現(xiàn)其具有非遞減的數(shù)學(xué)性質(zhì)，總結(jié)在下面的定理中：

路徑次序序列能夠用于揭示卷積碼網(wǎng)格中非最大似然路徑之間的關(guān)系。具體而言，利用路徑次序序列，可以將非最大似然路徑pl與前l(fā)條路徑p0,...,pl-1

中的一條相關(guān)聯(lián)。這樣在得到前l(fā)條路徑之后，不必回溯整個網(wǎng)格即可確定pl，有利于降低列表譯碼器并行路徑回溯的復(fù)雜度。下面的定理對兩條路徑之間的關(guān)系進(jìn)行了描述：

圖6.3對定理6.2描述的路徑間關(guān)聯(lián)性進(jìn)行了更為具體的說明。對于路徑pl?同樣能得到與之相對應(yīng)的路徑次序序列

。特別地當(dāng)l?時，定理6.1表明存在參數(shù)n?*使得pl?在網(wǎng)格的第n?*級出現(xiàn)首個非零路徑次序。注意到路徑pl的非零路徑次序出現(xiàn)于網(wǎng)格的第n*級，我們有

這是由于pl?滿足

，根據(jù)定理6.1對于

均有

。上面的分析使我們

能夠通過少量參數(shù)來唯一確定每一條非最大似然路徑，這些參數(shù)構(gòu)成了該條路徑的路徑標(biāo)識。

圖6.3列表譯碼算法確定出的多條最優(yōu)路徑之間的關(guān)聯(lián)性

6.2.1基于路徑標(biāo)識的前向遞推運(yùn)算

對于網(wǎng)格第n級的狀態(tài)

，如果將其看作網(wǎng)格的終止?fàn)顟B(tài)，那么定理6.2也可以用來描述到達(dá)s的L條最優(yōu)路徑之間的關(guān)聯(lián)性。具體而言，對于到達(dá)s的第l+1條最優(yōu)路徑，當(dāng)l>1時定義與之相對應(yīng)的路徑標(biāo)識為

，其中

?表示與第l+1條最優(yōu)路徑相關(guān)聯(lián)的路徑在狀態(tài)s的路徑次序；

?表示第l+1條最優(yōu)路徑的路徑次序變?yōu)榉橇銜r所在的網(wǎng)格級數(shù)；

?表示第l+1條最優(yōu)路徑在網(wǎng)格第

級所經(jīng)歷狀態(tài)的前序狀態(tài)索引。

6.2.2基于路徑標(biāo)識的路徑回溯

圖6.4基于路徑標(biāo)識的并行列表譯碼算法執(zhí)行過程

6.2.3基于網(wǎng)格循環(huán)性的咬尾卷積碼初始狀態(tài)估計器

在前面我們提到，列表長度為L的咬尾卷積碼列表譯碼需要基于網(wǎng)格未知初始狀態(tài)的L個最優(yōu)估計

來達(dá)到最優(yōu)糾錯性能。在已有的研究工作中，有的方案通過窮盡搜索全部子網(wǎng)格來確定

條咬尾路徑的路徑度量，再對路徑度量排序來得到

，該方案具有極高的計算復(fù)雜度。本節(jié)我們將從咬尾卷積碼網(wǎng)格的循環(huán)性入手，以低運(yùn)算復(fù)雜度來實(shí)現(xiàn)對初始狀態(tài)的有效估計。

圖6.5基于網(wǎng)格循環(huán)性的初始狀態(tài)估計算法流程圖

圖6.6不同初始狀態(tài)估計方法下咬尾卷積碼列表譯碼器BLER性能隨Eb/N0變化曲線

圖6.6不同初始狀態(tài)估計方法下咬尾卷積碼列表譯碼器BLER性能隨Eb/N0變化曲線

6.3并行列表譯碼器的硬件結(jié)構(gòu)設(shè)計

在硬件實(shí)現(xiàn)方面，基于路徑標(biāo)識的非咬尾卷積碼并行列表譯碼器具有圖6.7所示的頂層結(jié)構(gòu)。

圖6.7并行列表譯碼器頂層結(jié)構(gòu)框圖

了實(shí)現(xiàn)對咬尾卷積碼的列表譯碼，需要在上述非咬尾卷積碼列表譯碼器的基礎(chǔ)上進(jìn)一步配置初始狀態(tài)估計器。這里的估計器利用6.2節(jié)所設(shè)計的算法依次確定并輸出狀態(tài)

。譯碼器所要執(zhí)行的各類操作的先后次序以時序圖的方式表示在了圖6.8中。

圖6.8咬尾卷積碼并行列表譯碼器工作時序圖

6.3.1并行列表譯碼器的ACS單元

在列表長度為L的并行列表譯碼器中，執(zhí)行radix-M算法的ACS單元需要從LM個來自前序狀態(tài)的路徑度量中確定出L個最優(yōu)的路徑度量。故如圖6.9所示，電路中需要消耗LM個加法器來實(shí)現(xiàn)路徑度量與相應(yīng)的分支度量的累積。隨后，路徑標(biāo)識與相應(yīng)的路徑度量合并后通過由log2M級樹形連接的比較器所組成的選擇網(wǎng)絡(luò)，而選擇網(wǎng)絡(luò)輸出的路徑標(biāo)識進(jìn)一步通過L-1個路徑標(biāo)識計算單元進(jìn)行更新。最后將更新后的路徑度量和路徑標(biāo)識送至寄存器進(jìn)行緩存，用于網(wǎng)格下一級的ACS計算。

圖6.9并行列表譯碼器中執(zhí)行radix-M運(yùn)算的ACS單元結(jié)構(gòu)（M=2）

不同于Viterbi譯碼器的ACS單元所使用的2輸入1輸出比較器，并行列表譯碼器中用于構(gòu)建ACS單元選擇網(wǎng)絡(luò)的比較器為2L

輸入L輸出模式：所接收的2組輸入各包含L個按大小次序排列的路徑度量，比較器選擇其中L個最優(yōu)度量并排序后作為輸出。由于輸入比較器的路徑度量形成了分段有序序列，我們可以采用歸并排序的策略來設(shè)計低復(fù)雜度的比較器結(jié)構(gòu)。圖6.10以L=4的情形為例給出了比較器的數(shù)據(jù)流圖與電路結(jié)構(gòu)。具體而言，首先利用歸并網(wǎng)絡(luò)從輸入中選出L個最優(yōu)路徑度量，它們構(gòu)成一個雙調(diào)序列；然后利用雙調(diào)排序器完成對輸出路徑度量的排序。在硬件實(shí)現(xiàn)上，2L輸入L輸出的比較器需要消耗L個最大值選擇器和L/2?log2L個換向器，通過log2L+1輪比較操作來完成計算任務(wù)。

圖6.102L輸入L輸出比較器的信號流圖與電路結(jié)構(gòu)（L=2）

圖6.11以

的計算為例說明了路徑標(biāo)識計算單元的電路結(jié)構(gòu)。一般地，

與

的計算只用到2個數(shù)據(jù)選擇器和1個相等判斷單元，這里相等判斷單元通過按位異或的方式來判別兩個輸入數(shù)據(jù)是否相同；另一方面，基于(6.11)計算

要用到2l+1個相等判斷單元和1個l輸入的二進(jìn)制編碼器，其中二進(jìn)制編碼器的輸入在任一時刻有且僅有一路信號維持高電平，編碼器的輸出為該路高電平信號的次序。

圖6.11路徑標(biāo)識計算單元的電路結(jié)構(gòu)

6.3.2并行列表譯碼器的路徑回溯單元

為了并行恢復(fù)路徑

及相應(yīng)信息序列

，如圖6.12(a)所示，電路中部署了L個路徑回溯模塊。路徑回溯模塊l一方面利用存儲的前序狀態(tài)索引遞歸計算路徑p1的狀態(tài)并將結(jié)果傳遞給之后的L-l-1個路徑回溯模塊，另一方面接收前l(fā)-1個模塊所傳遞的狀態(tài)值。如圖6.12(b)所示，路徑回溯模塊0用于完成路徑p0的恢復(fù)，它從網(wǎng)格第N級開始執(zhí)行回溯操作，通過相鄰兩個狀態(tài)值可以得到該狀態(tài)轉(zhuǎn)移所對應(yīng)的信息符號，并將其緩存在先入后出（LastInputFirstOutput,LIFO）單元中。

路徑p1

，l>0對應(yīng)的路徑回溯模塊

具有圖6.12(c)所示的電路結(jié)構(gòu)，它從網(wǎng)格第

級開始執(zhí)行回溯操作，并在這一級利用參數(shù)

從l-1個傳遞來的狀態(tài)值中選出狀態(tài)

作為回溯起始狀態(tài)。由于回溯操作涉及到網(wǎng)格的第0級至第

級，故在理論上，用于緩存路徑回溯模塊l所產(chǎn)生的信息符號的LIFO單元深度應(yīng)達(dá)到

。然而注意到路徑p1所對應(yīng)的路徑次序滿足

，即p1在網(wǎng)格的第0級至第

級是一條最大似然路徑，因此如果卷積碼的判決深度為D且D<

，路徑p1在網(wǎng)格第

級會以很高概率與路徑p0重合。利用這一性質(zhì)，可以將路徑回溯模塊l所對應(yīng)的LIFO單元深度進(jìn)一步減小至

。

圖6.12并行路徑回溯單元的硬件結(jié)構(gòu)設(shè)計

圖6.12并行路徑回溯單元的硬件結(jié)構(gòu)設(shè)計

6.3.3初始狀態(tài)估計器

圖6.13給出了初始狀態(tài)估計器的硬件設(shè)計方案。圖6.13初始狀態(tài)估計器的頂層結(jié)構(gòu)圖

圖6.14給出了ACS單元的底層硬件結(jié)構(gòu)圖，可以看到ACS單元選用減法器來實(shí)現(xiàn)分支度量的累積，相應(yīng)地比較單元選取兩個路徑度量中的最小值輸出。這些設(shè)計旨在使ACS單元包含的計算資源能夠同時承擔(dān)其他計算任務(wù)，即當(dāng)ACS單元完成Viterbi算法在網(wǎng)格中的前向遞推運(yùn)算后，再次復(fù)用其中的計算資源來計算咬尾路徑度量估計值

，搜索狀態(tài)

與

以及確定集合

。ACS單元內(nèi)計算資源的不同使用方式在圖6.15中進(jìn)行了總結(jié)。

圖6.14初始狀態(tài)估計器中ACS單元的硬件結(jié)構(gòu)設(shè)計

圖6.15ACS單元中計算資源在不同階段的執(zhí)行的操作

圖6.15ACS單元中計算資源在不同階段的執(zhí)行的操作

6.4理論分析與硬件測試

6.4.1非咬尾卷積碼列表譯碼器存儲資源分析

對于非咬尾卷積碼的列表譯碼，表6.2總結(jié)了基于列表擴(kuò)展算法和樹形網(wǎng)格算法算法的兩種串行列表譯碼方案、傳統(tǒng)并行列表譯碼方案、文獻(xiàn)[39]改進(jìn)的并行列表譯碼方案以及本章提出的基于路徑標(biāo)識的并行列表譯碼方案所對應(yīng)的存儲資源消耗。

其中(c,1,u)卷積碼的判決深度為D，M進(jìn)制信息符號序列長度為N，譯碼器列表長度為L，輸入軟信息和路徑度量分別量化為wc和ws

比特。譯碼器中輸入軟信息的緩存、前向遞推中路徑度量及相關(guān)參數(shù)的存儲、路徑回溯所需的輔助參數(shù)存儲及LIFO構(gòu)建均在表中進(jìn)行了統(tǒng)計。進(jìn)一步，圖6.17選用EC-GSM系統(tǒng)的卷積碼碼型G0=133，G1=171，G2=145并固定信息序列長度為512比特，即Nlog2M

，在這些前提條件下研究了D=64，M分別取2和4的情況下譯碼器資源消耗與列表長度L的關(guān)系。

圖6.17不同列表長度下非咬尾卷積碼列表譯碼算法的存儲資源需求

6.4.2基于FPGA的列表譯碼器硬件實(shí)現(xiàn)與性能測試

我們在FPGA上對不同的列表譯碼器設(shè)計方案進(jìn)行了硬件實(shí)現(xiàn)與性能測試。所用的FPGA型號為具有-3速度等級的XilinxKintex7XC7K325T，編譯器版本為ISE14.2。對于非咬尾卷積碼的譯碼，我們選用Viterbi譯碼器作為基準(zhǔn)方案來衡量不同列表譯碼器的硬件復(fù)雜度與性能，實(shí)驗(yàn)中測試了基于樹形網(wǎng)格算法的串行列表譯碼方案、傳統(tǒng)并行列表譯碼及其改進(jìn)設(shè)計、以及本章提出的基于路徑標(biāo)識的并行列表譯碼。

對于非咬尾卷積碼的譯碼，表6.3與表6.4的上半部分分別統(tǒng)計了不同譯碼器的FPGA資源消耗情況與譯碼時延、最大吞吐量以及編碼增益提升量等性能指標(biāo)。

6.4.3列表譯碼器的VLSI實(shí)現(xiàn)

利用130nmCMOS工藝，我們對前面在FPGA上測試的基于路徑標(biāo)識的并行列表譯碼進(jìn)行了綜合與布局布線操作，實(shí)驗(yàn)所用的編譯器為Synopsys。圖6.18(a)統(tǒng)計了不同列表長度下基于路徑標(biāo)識的并行列表譯碼在布局布線后的電路面積，作為對比，圖6.18(b)同時