0 引言

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

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

    自1986年以來(lái)，國(guó)際上發(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的工作速度不可同日而語(yǔ)，在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)用角度看，對(duì)Viterbi 譯碼器的性能評(píng)價(jià)指標(biāo)主要有譯碼速度、處理時(shí)延和資源占用等。傳統(tǒng)的Viterbi譯碼器結(jié)構(gòu)難以兼具資源消耗少和時(shí)延小的優(yōu)點(diǎn)。而在高速通信系統(tǒng)中，很多時(shí)候?qū)ψg碼時(shí)延要求很高。本文提出了一種采用部分寄存器交換的辦法可兼顧譯碼延時(shí)和消耗邏輯資源的性能。測(cè)試結(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ù)在寄存器陣列中的不斷交換來(lái)實(shí)現(xiàn)譯碼。這種方法雖然具有存儲(chǔ)單元少、譯碼延時(shí)短的優(yōu)點(diǎn)，但由于其內(nèi)連關(guān)系過(guò)于復(fù)雜, 功耗大(每個(gè)新判決比特輸入時(shí)寄存器都要翻轉(zhuǎn))，不適合大狀態(tài)Viterbi譯碼器的FPGA實(shí)現(xiàn)。

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

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

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

    對(duì)于全并行的傳統(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對(duì)應(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ǔ)單元，從而加快之后的讀過(guò)程。

    設(shè)部分RE的長(zhǎng)度為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í)間。對(duì)每段譯碼信息而言從開始接收到回溯前的等待時(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對(duì)應(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è)長(zhǎng)為y的寄存器鎖存當(dāng)前路徑信息。

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

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

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

    簡(jiǎn)單的累積路徑度量溢出，對(duì)于(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)性能

    按照?qǐng)D1設(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量化前仿真：分別對(duì)(2，1，3)、(2，1，5)、(2，1，7)、(2，1，9)的50段(信噪比小于等于4.4 dB時(shí))或100段(信噪比大于4.4 dB時(shí))長(zhǎng)度為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í)對(duì)(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下長(zhǎng)度為40 000的有噪已編碼接收序列進(jìn)行誤碼性能測(cè)試，與圖2完全一致。

5.2 吞吐量

    當(dāng)吞吐量定義為譯碼器輸出信息速率時(shí)(而文獻(xiàn)[5]中吞吐量定義為譯碼器輸入速率，與量化比特?zé)o關(guān))，對(duì)于本文中的基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)的并行譯碼器性能對(duì)比

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

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

6 結(jié)論

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

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

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

參考文獻(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)