0 引言

    Viterbi譯碼是1967年由VITERBI A J提出的一種概率譯碼算法,，且是最大似然譯碼法,。后來發(fā)現(xiàn)，這種算法可用于多種數(shù)字估值問題,，如碼間干擾下的判決,、連續(xù)相位FSK信號(hào)的最佳接收、語詞識(shí)別,、序列跟蹤和源編碼等,。Viterbi算法的這些應(yīng)用都可以歸結(jié)為時(shí)間離散、狀態(tài)有限的馬氏過程的最佳估值問題,，因而它不僅是卷積碼的一種重要譯碼算法,，而且在理論上也有較大意義。

    由于卷積碼優(yōu)良的糾錯(cuò)性能和Viterbi硬件譯碼器簡單(容易實(shí)現(xiàn)高速譯碼),被廣泛應(yīng)用于深空通信,、衛(wèi)星通信,、IEEE 802.11、超寬帶(UWB)系統(tǒng),、DAB,、DVB、2G,、3G,、LTE、Wimax以及電力線通信中,。

    自1986年以來,，國際上發(fā)表了很多關(guān)于Viterbi譯碼器設(shè)計(jì)的文章，如文獻(xiàn)[1]～[6],。為追求譯碼速度,，大多采用全并行結(jié)構(gòu),，吞吐量可高達(dá)1.74 Gb/s^[3]、2.8 Gb/s^[4],，同時(shí)目前各大FPGA廠商都已經(jīng)提供了很多的IP核^[7],。

    由于內(nèi)部互連機(jī)制不同，基于FPGA的譯碼器與結(jié)構(gòu)化ASIC以及定制ASIC的工作速度不可同日而語,，在FPGA上實(shí)現(xiàn)的譯碼器工作頻率一般在140~510 MHz^[6,，7]之間，同樣的設(shè)計(jì)結(jié)構(gòu)若采取定制ASIC實(shí)現(xiàn),，應(yīng)能達(dá)到與文獻(xiàn)[3-4]相近的工作頻率（800 MHz~1.4 GHz）,。

    從工程應(yīng)用角度看，對Viterbi 譯碼器的性能評價(jià)指標(biāo)主要有譯碼速度,、處理時(shí)延和資源占用等,。傳統(tǒng)的Viterbi譯碼器結(jié)構(gòu)難以兼具資源消耗少和時(shí)延小的優(yōu)點(diǎn)。而在高速通信系統(tǒng)中,，很多時(shí)候?qū)ψg碼時(shí)延要求很高,。本文提出了一種采用部分寄存器交換的辦法可兼顧譯碼延時(shí)和消耗邏輯資源的性能。測試結(jié)果表明,，采用這種部分寄存器交換的回溯方式存儲(chǔ)幸存路徑,，具有寄存器交換時(shí)延小的優(yōu)點(diǎn)，而所需邏輯資源與普通回溯法相當(dāng),，所需存儲(chǔ)單元大大小于普通回溯法,。

1 部分寄存器交換方式的路徑存儲(chǔ)

1.1 傳統(tǒng)的路徑存儲(chǔ)

    幸存路徑存儲(chǔ)器的結(jié)構(gòu)主要有兩種：一種是寄存器交換結(jié)構(gòu)(RE),另一種是回溯結(jié)構(gòu)(TB)^[1-2]。

    前者采用專用寄存器作為存儲(chǔ)主體,，存儲(chǔ)的是路徑上的輸入信號(hào)信息,，利用數(shù)據(jù)在寄存器陣列中的不斷交換來實(shí)現(xiàn)譯碼。這種方法雖然具有存儲(chǔ)單元少,、譯碼延時(shí)短的優(yōu)點(diǎn),，但由于其內(nèi)連關(guān)系過于復(fù)雜, 功耗大(每個(gè)新判決比特輸入時(shí)寄存器都要翻轉(zhuǎn))，不適合大狀態(tài)Viterbi譯碼器的FPGA實(shí)現(xiàn),。

    回溯法利用通用的RAM作為存儲(chǔ)主體,，存儲(chǔ)的是幸存路徑的格狀連接關(guān)系,通過讀寫RAM來完成數(shù)據(jù)的寫入和回溯輸出。其優(yōu)點(diǎn)是內(nèi)連關(guān)系簡單,、規(guī)則,；缺點(diǎn)一是譯碼延時(shí)大——一般并行譯碼時(shí)回溯法的延時(shí)是寄存器交換法的4倍，缺點(diǎn)二是存儲(chǔ)單元要求多,。具體性能區(qū)別分析如下,。

    設(shè)卷積碼編碼約束長度為L，譯碼深度V=6×L,；對碼率R=1/2的譯碼器而言,，每系統(tǒng)時(shí)鐘輸入2 bit編碼傳輸信息,，輸出1 bit譯碼后信息。

    對于基2加比選的全并行RE方式：路徑存儲(chǔ)部分需鎖存交換2^L-1個(gè)狀態(tài)的長V路徑信息,，即需V×2^L-1個(gè)邏輯單元和寄存器,，譯碼時(shí)延為V個(gè)系統(tǒng)時(shí)鐘。

    對于全并行的傳統(tǒng)TB方式,，因每譯出1 bit,，至少回溯V bit，為實(shí)現(xiàn)連續(xù)譯碼,，一次回溯應(yīng)譯出多個(gè)比特,，設(shè)為x。則從譯碼輸入到準(zhǔn)備回溯需等待V+x個(gè)系統(tǒng)時(shí)鐘,，若每系統(tǒng)時(shí)鐘只回溯y=1 bit,，則一次譯碼輸出需回溯V+x個(gè)系統(tǒng)時(shí)鐘。采取多片輪讀(一片寫,，2至多片讀)的模式，在回溯期間又寫入V+x個(gè)符號(hào)的路徑信息,。

    流水線方式操作時(shí),，在(n+1)x系統(tǒng)時(shí)鐘內(nèi)至少完成n次回溯譯碼x bit。2片讀時(shí),，2x時(shí)鐘內(nèi)需完成(V+x)符號(hào)的回溯,，因而一般取x=V。

    這樣,，2x時(shí)鐘內(nèi)讀的2片RAM深度分別為2V,，寬度2^L-1個(gè)狀態(tài)的1 bit路徑信息，共計(jì)4V深度(按之前4V系統(tǒng)時(shí)鐘內(nèi)寫入順序標(biāo)記為1a,、1b,，之后啟動(dòng)寫2a、2b的深度為2V的2片RAM),，寫入2V深度之后啟動(dòng)回溯讀出1b,、1a；V深度后另一片讀出2a,、1b,，這樣回溯出1a、1b處的傳輸信息,，同時(shí)寫入2b,、1a路徑。

    在這段時(shí)間內(nèi)又寫入2V深度的路徑信息(1a,，1b),，與2片讀的RAM中的前一片2V深度RAM讀出信息(1b,，1a)交叉。當(dāng)路徑存儲(chǔ)RAM采用一讀一寫的雙端口RAM實(shí)現(xiàn)時(shí),，2片RAM即可實(shí)現(xiàn)1片寫,，2片讀的寫入及回溯功能。

    所以,，總存儲(chǔ)單元應(yīng)為深度為4V個(gè)符號(hào)的寬度2^L-1個(gè)狀態(tài)路徑信息,，即4V×2^L-1 bit存儲(chǔ)單元，實(shí)際深度取滿足(M=2N>4V)的最小正整數(shù)N對應(yīng)的M,。

    譯碼延時(shí)：從譯碼器開始接收到準(zhǔn)備回溯需2V個(gè)時(shí)鐘,，回溯(V+x)即2V深度需2V個(gè)系統(tǒng)時(shí)鐘，共計(jì)4V個(gè)系統(tǒng)時(shí)鐘,。

1.2 改進(jìn)的部分寄存器交換回溯方式

    從上述傳統(tǒng)TB方式可以看出,，為減小譯碼延時(shí)和存儲(chǔ)單元，可采取一次并行讀出多比特符號(hào)的路徑信息,。本文提出采用部分寄存器交換方法,，累積多符號(hào)(2~6)的路徑信息后,一次存儲(chǔ)寫入一個(gè)地址的存儲(chǔ)單元，從而加快之后的讀過程,。

    設(shè)部分RE的長度為y,。采取1片存儲(chǔ)單元1讀1寫方式，每次回溯譯出x比特,，則回溯延時(shí)為t=(V+x)/y,；在此回溯期間又寫入t比特路徑信息，為保證路徑信息存儲(chǔ)單元不發(fā)生有用信息覆蓋,，要求t≤x,，即x≥(V+x)/y，也即x≥V/(y-1),。一般x取滿足條件的最小整數(shù)值,。

    譯碼延時(shí)為等待時(shí)間加回溯時(shí)間。對每段譯碼信息而言從開始接收到回溯前的等待時(shí)間為：V+x比特的譯碼信息接收時(shí)間V+x個(gè)系統(tǒng)時(shí)鐘,。譯碼延時(shí)共計(jì)V+x+t≈V+2x,。

    路徑信息存儲(chǔ)單元為(V+2x)/y深(實(shí)際深度取滿足M=2^N>(V+2x)/y的最小正整數(shù)N對應(yīng)的M)，y×2^L-1寬,，總比特?cái)?shù)為(V+2x)×2^L-1,。

    另外，回溯時(shí)要多消耗y個(gè)2^L-1選一的邏輯資源,，即y×2^L-1的組合LUT,；由于采用部分寄存器交換，需要2^L-1個(gè)長為y的寄存器鎖存當(dāng)前路徑信息,。

2 其他優(yōu)化措施

    采用了文獻(xiàn)[5]中提到的分支度量線性變換3 bit量化解調(diào)信號(hào)時(shí),，分支度量仍為3 bit的非負(fù)數(shù),，簡化了之后的路徑度量溢出處理。

    分支度量一次計(jì)算多次查找——對于（2,，1,，n）碼即4選一。

    簡單的累積路徑度量溢出,，對于(2,，1，7)3 bit量化卷積碼,，路徑度量的最大最小范圍在3+log₂⁷位內(nèi),。因所有路徑度量及分支度量都是非負(fù)數(shù)，這樣再補(bǔ)充一位最高位溢出位,，確定了存儲(chǔ)路徑度量的寄存器位寬為3+log₂⁷+17,。

    由于采用全并行結(jié)構(gòu)，一個(gè)時(shí)鐘內(nèi)必須完成一次ACS（Add-Compare-Select,，加比選）,，因而ACS部分未采用文獻(xiàn)[7]中流水線結(jié)構(gòu)，ACS是制約全并行結(jié)構(gòu)Viterbi譯碼器最高工作頻率的因素之一,。但采取了緩解分支度量選擇的時(shí)延,，兩級(jí)計(jì)算鎖存的分支度量算法，較一級(jí)分支度量鎖存提高了約10 MHz的最高工作頻率,。

3 譯碼器設(shè)計(jì)

    譯碼器的結(jié)構(gòu)框圖如圖1所示。

4 資源占用實(shí)驗(yàn)性能

    按照圖1設(shè)計(jì)的基2全并行譯碼器在Quartus9.1下時(shí)序仿真正確后,，綜合適配結(jié)果如表1～表4所述,，其中：V=6×L，量化比特?cái)?shù)為3,。

5 譯碼器其他性能

5.1 譯碼器譯碼性能

    在MATLAB下3 bit量化定點(diǎn)仿真和Modelsim下3 bit量化前仿真：分別對(2,，1，3),、(2,，1，5),、(2,，1，7),、(2,，1，9)的50段(信噪比小于等于4.4 dB時(shí))或100段(信噪比大于4.4 dB時(shí))長度為40 000的已編碼序列經(jīng)信噪比(SNR=E_b/n_o)為3～5.4 dB(僅在MATLAB下,，而在Modelsim下每種卷積碼僅選擇譯碼BER=10^-3及10^-4兩種情況)的AGWN BPSK信道傳輸?shù)慕邮招盘?hào)進(jìn)行模擬,，誤碼性能如圖2所示,。后仿真[2，7]時(shí)對(2,，1,，3)、(2,，1,，5)、(2,，1,，7)、(2,，1,，9)4種卷積碼分別選取了5.2 dB、4.8 dB,、4.0 dB,、3.4 dB下長度為40 000的有噪已編碼接收序列進(jìn)行誤碼性能測試，與圖2完全一致,。

5.2 吞吐量

    當(dāng)吞吐量定義為譯碼器輸出信息速率時(shí)(而文獻(xiàn)[5]中吞吐量定義為譯碼器輸入速率,，與量化比特?zé)o關(guān))，對于本文中的基2全并行碼率R=1/2的Viterbi譯碼器,，吞吐量為2f_max,。即在CycloneIII上實(shí)現(xiàn)的(2，1,，7)全并行譯碼器吞吐量在290～350 Mb/s之間,。

    在結(jié)構(gòu)化ASIC器件如HardCopyIII上消耗邏輯資源與在CycloneIII上相當(dāng)時(shí)(2，1,，7)卷積碼的最高工作頻率340 Hz,，吞吐量680 Mb/s。

    若采用定制ASIC實(shí)現(xiàn),，吞吐量應(yīng)可滿足引言中提到的目前各種使用Viterbi譯碼的標(biāo)準(zhǔn)（500 Mb/s）的需求,。

5.3 與其他文獻(xiàn)的并行譯碼器性能對比

    與其他文獻(xiàn)的(2，1,，3)全并行譯碼器性能對比(EP3-C10F256C6)如表5所示,。

    由表中數(shù)據(jù)可以看出，本文設(shè)計(jì)的（2,，1,，3）卷積碼全并行譯碼器明顯優(yōu)于Altera公司提供的IP核，邏輯資源占用量僅其25%，譯碼時(shí)延也僅其25%,。與其他文獻(xiàn)的(2,，1，7)全并行譯碼器性能對比如表6所示,。

6 結(jié)論

    本文采用部分寄存器交換的譯碼器在交換長度為3時(shí)與簡單回溯模式相比消耗邏輯資源幾乎相近,，存儲(chǔ)單元減少25%~66%的條件下實(shí)現(xiàn)譯碼延時(shí)減半的效果。

    對于短約束長度的卷積碼,，如(2,，1，3),、(2,，1，5)采用全寄存器交換資源消耗不會(huì)增加太多,，但譯碼延時(shí)比交換長度為3時(shí)又減少50%,，更具實(shí)用價(jià)值。

    而對于長約束長度的卷積碼,，如(2,，1，7),、(2,，1，9)采用全寄存器交換資源消耗增加太多,，選用寄存器交換長度為4或6時(shí)較合適,，此時(shí)的時(shí)延與完全寄存器交換相近，但消耗的邏輯資源與簡單回溯模式相當(dāng),，存儲(chǔ)器單元比簡單回溯小很多(小50%或62.5%),，雖然在本文中的FPGA下實(shí)現(xiàn)時(shí)消耗的存儲(chǔ)塊數(shù)更多，但那是由于CycloneIII的每塊存儲(chǔ)塊比較大(深度大而寬度受限),，若采用最小深度為16的小存儲(chǔ)塊時(shí)(比如定制ASIC技術(shù))其優(yōu)勢將明顯顯現(xiàn)出來,。

參考文獻(xiàn)

[1] TRUONG T K, SHIH M T,，REED I S,，et al.A VLSI design for a trace-back Viterbi decoder[J].IEEE Transaction on Commuications，1992,，40(3)：616-624.

[2] FEYGIN G,，GULAK P G.Architectural tradeoffs for survivor sequence memory management in Viterbi decoders[J].IEEE Trans on Commun，1993,，41(3)：425–429.

[3] GOO Y J,，LEE H.Two bit-level pipelined viterbi decoder for high-performance UWB applications[C].IEEE International Symposium on Circuits and Systems，ISCAS 2008，2008：1012-1015.

[4] BRUELS N,，SICHENEDER E,，LOEW M，et al.A 2.8 Gb/s,，32-state, radix-4 Viterbi decoder add-compare-select unit[C].2004 Symposium on VLSI Circuits,，2004：170-173.

[5] Yang Min.Design optimization of FPGA based Viterbi decoder[C].2011 International Conference on Electric Information and Control Engineering，2001,，5：4129-4131.

[6] Tang Jiuling.Design and FPGA implementation of a Viterbi decoder：a case study using systemVerilog and co-simulation[C].2009 IEEE International Symposium on Signal Processing and Information Technology(ISSPIT),，2009：1-6.

[7] Altera Cooperation.Viterbi Compiler v9.1 User Guide[Z].2009.

[8] 夏宇聞.Verilog數(shù)字系統(tǒng)設(shè)計(jì)教程（第二版)[M].北京：北京航空航天大學(xué)出版社，2008.

作者信息:

楊  敏

(華中科技大學(xué) 電子信息與通信學(xué)院,，湖北 武漢430074)