0 引言

    糾錯(cuò)碼技術(shù)在數(shù)字通信中具有重要作用，其中卷積碼的編碼方式，由于優(yōu)良的糾錯(cuò)性能被廣泛應(yīng)用，而Viterbi譯碼方式作為卷積碼的一種最佳概率譯碼方法，對(duì)于卷積碼的廣泛應(yīng)用具有重要價(jià)值^[1-2]。近年來(lái)，FPGA作為一種半定制電路，廣泛應(yīng)用于數(shù)字信號(hào)處理系統(tǒng)中，為Viterbi譯碼器的實(shí)現(xiàn)提供了有利條件^[3]。

    評(píng)價(jià)Viterbi譯碼器性能的指標(biāo)主要是譯碼速度和資源消耗，因此如何減小譯碼時(shí)延、提高譯碼速度、降低資源消耗成為近年來(lái)研究的熱點(diǎn)^[4]。文獻(xiàn)[5-6]通過(guò)改進(jìn)文獻(xiàn)[7-8]網(wǎng)格圖的構(gòu)造來(lái)降低譯碼時(shí)延、提高譯碼速率，文獻(xiàn)[5]采用基二算法，文獻(xiàn)[6]采用基四算法。其中基二算法的資源消耗小，但基二算法的數(shù)據(jù)處理能力比基四算法弱；基四算法處理數(shù)據(jù)能力比基二算法強(qiáng)，但基四算法的主頻低，速度難以提升。文獻(xiàn)[9-10]通過(guò)改進(jìn)Viterbi的迭代方式提高譯碼速度，但是該方法復(fù)雜度高，資源消耗大。文獻(xiàn)[11]通過(guò)改進(jìn)回溯結(jié)構(gòu)來(lái)降低譯碼時(shí)延、提高譯碼速率，在文獻(xiàn)[6]的基礎(chǔ)上提出了基于滑窗流水的前向回溯基四算法，但該方法添加了冗余滑窗，資源消耗大，不適用于資源有限的場(chǎng)景。

    為了使Viterbi譯碼算法可以在XC6SLX16-2CSG-324型FPGA上實(shí)現(xiàn)，并針對(duì)目前大多數(shù)改進(jìn)算法在資源有限條件下難以兼顧時(shí)延與資源消耗，本文在基二算法的基礎(chǔ)上提出了一種改進(jìn)算法。該算法在基二算法的基礎(chǔ)上，對(duì)Viterbi譯碼器的度量控制和幸存路徑信息存儲(chǔ)模塊分別進(jìn)行了改進(jìn)，提高基二算法的數(shù)據(jù)處理能力，在資源有限條件下，能夠有效簡(jiǎn)化譯碼器的實(shí)現(xiàn)結(jié)構(gòu)，進(jìn)而兼顧時(shí)延與資源消耗，提高譯碼性能。

1 改進(jìn)Viterbi算法

1.1 算法原理

    Viterbi算法是一種用于解決有限狀態(tài)離散時(shí)間馬爾科夫鏈的狀態(tài)估計(jì)問(wèn)題的優(yōu)化算法^[12]。圖1^[1]所示的基二網(wǎng)格圖顯示了卷積碼的譯碼過(guò)程，具體描述可參見(jiàn)文獻(xiàn)[1]。時(shí)間節(jié)點(diǎn)t表示第t個(gè)信息碼元，Viterbi譯碼器從網(wǎng)格中找出最大似然路徑。

    Viterbi譯碼器的工作流程如圖2^[3]所示。將接收機(jī)^[13]每一時(shí)刻從信道接收到的信息序列與編碼網(wǎng)格中所有的信息序列進(jìn)行比較，根據(jù)軟判決原理計(jì)算各分支路徑度量值，并與該分支下一時(shí)刻進(jìn)入狀態(tài)的度量值進(jìn)行累加，保留進(jìn)入每個(gè)狀態(tài)的度量值最小的分支路徑和幸存路徑信息，當(dāng)達(dá)到回溯深度時(shí)，選出度量值最小的狀態(tài)作為開(kāi)始逆向回溯的初始狀態(tài)，根據(jù)幸存路徑信息找到回溯的最大似然路徑。

    記(n₀，k₀，m)為卷積碼編碼器，該編碼器共有2k₀×m個(gè)狀態(tài)，Viterbi譯碼器必須具備同樣的2k₀×m個(gè)狀態(tài)發(fā)生器，且每個(gè)狀態(tài)必須有一個(gè)存儲(chǔ)路徑度量值的存儲(chǔ)器和一個(gè)存儲(chǔ)幸存路徑信息的存儲(chǔ)器，所以Viterbi譯碼器的復(fù)雜度呈2k₀×m指數(shù)增長(zhǎng)^[1]。

1.2 算法改進(jìn)的具體描述

    基二Viterbi譯碼器主要由分支度量計(jì)算單元(BMU)、加比選單元(ACSU)、路徑度量存儲(chǔ)單元(PMU)、幸存路徑存儲(chǔ)單元(SMU)、回溯單元(TBU)構(gòu)成，系統(tǒng)框圖如圖3^[3]所示。

    改進(jìn)算法在基二算法的基礎(chǔ)上，主要對(duì)ACSU中度量控制結(jié)構(gòu)和SMU的存儲(chǔ)結(jié)構(gòu)進(jìn)行改進(jìn)。記S_i為狀態(tài)i，PMi為狀態(tài)Si的路徑度量累加值，τ為回溯深度(τ=L+m，L為信息碼元數(shù))，Sub_bit為幸存路徑信息，算法改進(jìn)的具體描述如下：

2 理論分析

2.1 離散無(wú)記憶信道(DMC)模型

    Viterbi譯碼算法的性能可由譯碼器輸出的誤碼率進(jìn)行分析。由于改進(jìn)算法采用軟判決，這里主要針對(duì)高斯白噪聲(AWGN)下，BPSK調(diào)制的DMC信道模型根據(jù)不同回溯深度τ，τ=(5～10)m做誤碼率分析。DMC信道模型如圖5^[1]所示，q為電平量化序列，左邊表示信道輸入為二進(jìn)制0、1，右邊表示信道輸出為0～(q-1)，p(q-1|0)表示輸入為0輸出為q-1的概率^[1]。

    根據(jù)信道編碼定理，二進(jìn)制對(duì)稱信道(BSC)下，對(duì)某一給定的(n₀，k₀，m)卷積碼，采用最大似然譯碼的Viterbi譯碼器產(chǎn)生錯(cuò)誤事件的概率P_E為^[1]：

2.2 改進(jìn)算法分析

    給定(2，1，4)卷積碼，對(duì)于Viterbi的截尾譯碼器，回溯深度τ滿足τ=(5～10)m即可^[1]，為節(jié)約度量寄存器資源，本文選擇τ=20。然后在τ=20的情況下改變Q值，如圖6所示?？梢钥闯鯭<8時(shí)判決增益增加比較明顯，當(dāng)Q>8后判決增益增加很慢。因此實(shí)際應(yīng)用中一般選用八電平和十六電平量化，譯碼器不會(huì)太復(fù)雜，且有2~3 dB軟判決增益^[1]。因此選擇τ=20，Q=8能有效保證譯碼器性能。

3 仿真分析

3.1 MATLAB仿真結(jié)果分析

    在MATLAB中，對(duì)Viterbi譯碼器分別在AWGN信道和平坦瑞利衰落信道中譯碼進(jìn)行建模，給定(2，1，4)卷積碼，當(dāng)τ=20，Q=8時(shí)，對(duì)傳統(tǒng)和改進(jìn)后的譯碼器分別在AWGN信道和平坦瑞利衰落信道中進(jìn)行仿真。該模型中，輸入信道的信號(hào)為二進(jìn)制相移鍵控(Binary Phase Shift Keying，BPSK)調(diào)制信號(hào)，信道的輸出量化成八進(jìn)制。誤比特率(Bit Error Rate，BER)統(tǒng)計(jì)性能如圖7所示。從BER性能來(lái)看，在AWGN信道中本文采用的Viterbi算法與傳統(tǒng)的Viterbi算法相比，增益提高了約0.5 dB；在平坦瑞利衰落信道中本文采用的Viterbi算法與傳統(tǒng)的Viterbi算法性能相比，在低信噪比時(shí)增益提高不明顯，在高信噪比時(shí)增益提高了約1 dB。

3.2 ISE仿真結(jié)果分析

    針對(duì)τ=20，Q=8的(2，1，4)譯碼器，本文基于Verilog硬件描述語(yǔ)言對(duì)各模塊進(jìn)行了RTL級(jí)描述，并用ISE Design Suite 14.7進(jìn)行了功能仿真。

    對(duì)改進(jìn)前與改進(jìn)后的Viterbi譯碼器進(jìn)行ISE仿真，資源消耗與時(shí)延如表1所示。表中可以看出，采用本文提出的度量控制方法和幸存路徑存儲(chǔ)結(jié)構(gòu)的Viterbi譯碼器達(dá)到回溯深度后只需15個(gè)CLK延遲便可以譯出第一個(gè)碼元，采用傳統(tǒng)的度量控制與RE幸存路徑存儲(chǔ)結(jié)構(gòu)的Viterbi譯碼器需要32個(gè)CLK延遲。改進(jìn)后的譯碼器在速度上有了很大的提高，同時(shí)資源消耗也有了一定的節(jié)約。

    Viterbi譯碼器的測(cè)試主要包括功能驗(yàn)證與譯碼器的糾錯(cuò)性能兩部分。

    首先進(jìn)行功能驗(yàn)證，所有數(shù)據(jù)都是理想的。因?yàn)棣?20，則譯碼器以20個(gè)數(shù)據(jù)為一組譯碼，本文的Viterbi譯碼器采用的是截尾譯碼，故利用MATLAB產(chǎn)生16個(gè)隨機(jī)序列加上4個(gè)0組成一組信息序列為C1：11111101101110110000，經(jīng)過(guò)編碼器后的輸出序列為C2：11_10_11_01_10_10_01_11_11_11_00_11_00_10_11_11_11_11_01_11，八電平量化后的序列為C3：111111_111000_111111_000111_111000_111000_000111_111111_111111_111111_000000_111111_000000_111000_111111_111111_111111_111111_000111_111111，將C3序列作為Viterbi譯碼器的輸入，ISE仿真結(jié)果如圖8所示。

    圖中Clk為碼元時(shí)鐘，code是C3序列，TB_flag為1表示達(dá)到回溯深度，code_in為譯碼輸出結(jié)果：11111101101110110000，與C1序列完全相同，故此譯碼器功能正確。

    其次是糾錯(cuò)性能測(cè)試，在理想數(shù)據(jù)中人為加入錯(cuò)誤的干擾信息。經(jīng)計(jì)算，(2，1，4)譯碼器的d_f=7，故理論上此譯碼器可在5段連續(xù)譯碼中糾正3個(gè)隨機(jī)錯(cuò)誤。經(jīng)測(cè)試，在20個(gè)連續(xù)碼元段中加入3個(gè)隨機(jī)錯(cuò)誤碼元，即誤比特率為2.5%的情況下，譯碼器可以將錯(cuò)誤完全糾正。在20個(gè)連續(xù)碼元段中加入4個(gè)隨機(jī)錯(cuò)誤碼元，即誤比特率為3.33%時(shí)不能將錯(cuò)誤完全糾正，但若錯(cuò)誤碼元之間間隔≥5段碼元時(shí)也可完全糾正。理論值的糾錯(cuò)性能是在譯碼深度無(wú)限長(zhǎng)時(shí)計(jì)算出來(lái)的，而無(wú)限長(zhǎng)的譯碼深度在硬件上是無(wú)法實(shí)現(xiàn)的，因此在實(shí)際應(yīng)用中的糾錯(cuò)性能會(huì)與理論值有一定的差距，但在實(shí)際通信系統(tǒng)中，調(diào)制后通過(guò)信道傳輸?shù)腻e(cuò)誤碼率遠(yuǎn)未達(dá)到10^-2這個(gè)數(shù)量級(jí)^[1]。如圖7所示，在AWGN信道中，只要信噪比大于4.5 dB，誤碼率就小于10^-2這個(gè)數(shù)量級(jí)；在平坦瑞利衰落信道中，只要信噪比大于14 dB，誤碼率就小于10-2這個(gè)數(shù)量級(jí)，而實(shí)際通信系統(tǒng)中信道的信噪比遠(yuǎn)遠(yuǎn)大于14 dB，因此本文改進(jìn)的Viterbi譯碼器能夠滿足實(shí)際應(yīng)用中的需求^[1]。

4 結(jié)論

    本設(shè)計(jì)主要針對(duì)ACS和SMU單元，簡(jiǎn)化譯碼器的結(jié)構(gòu)，降低硬件實(shí)現(xiàn)的復(fù)雜度，提高運(yùn)算速度。在加比選單元的控制度量部分，為了解決路徑度量數(shù)據(jù)溢出問(wèn)題，本文提出了預(yù)定義存儲(chǔ)度量值寄存器容量法，減小了運(yùn)算量，提高了譯碼速度。在幸存路徑存儲(chǔ)部分，優(yōu)化了存儲(chǔ)方式， 采用步進(jìn)式存儲(chǔ)方法，降低了譯碼器的功耗?；厮葑g碼時(shí)，采用奇偶回溯法譯碼方式，根據(jù)幸存狀態(tài)的奇偶性完成輸出，減小了RAM的存儲(chǔ)空間。仿真結(jié)果表明，本文的優(yōu)化設(shè)計(jì)能夠大大簡(jiǎn)化硬件電路的結(jié)構(gòu)，在譯碼器的設(shè)計(jì)中具有應(yīng)用價(jià)值。

參考文獻(xiàn)

[1] 王新梅，肖國(guó)鎮(zhèn).糾錯(cuò)碼—原理與方法(修訂版)[M].西安：西安電子科技大學(xué)出版社，2001.

[2] GAO Z，ZHU J，HAN R，et al.Design and implementation of configuration memory SEU-Tolerant Viterbi decoders in SRAM-based FPGAs[J].IEEE Transactions on Nanotechnology，2019，18：691-699.

[3] 張慎.卷積碼編碼器及Viterbi譯碼器的設(shè)計(jì)[D].成都：電子科技大學(xué)，2008.

[4] 平磊.面向5G通信的咬尾卷積碼和Turbo碼技術(shù)研究[D].西安：西安電子科技大學(xué)，2017.

[5] MAMARDE R，KHOJE S.Viterbi decoder using Zynq-7000 AP-SoC[C].2018 Second International Conference on Intelligent Computing and Control Systems(ICICCS).IEEE，2018：941-944.

[6] EL-GOHARY A，SAAD M，MAHMOUD O，et al.Low utilization FPGA implementation of OFDM transceiver based on IEEE 802.11 n standard[C].2019 8th International Conference on Modern Circuits and Systems Technologies(MOCAST).IEEE，2019：1-4.

[7] ZHOU L，TANG M，LIU D，et al.A flexible viterbi decoder for software defined radio[J].Journal of Theoretical and Applied Information Technology，2013，47(2)：702-706.

[8] SANTHI M，LAKSHMINARAYANAN G，SUNDARAM R，et al.Synchronous pipelined two-stage radix-4 200Mbps MB-OFDM UWB Viterbi decoder on FPGA[C].2009 International SoC Design Conference(ISOCC).IEEE，2009：468-471.

[9] 朱明哲，肖瑞，蘇小凡，等.混合噪聲下基于Viterbi同步壓縮S變換的FM信號(hào)分析[J].電子與信息學(xué)報(bào)，2018，40(12)：2913-2918.

[10] YOSHIKAWA H.Error performance analysis of the K-best viterbi decoding algorithm[C].2018 International Symposium on Information Theory and Its Applications(ISITA).IEEE，2018：257-260.

[11] AHMED S，SIDDIQUE F，WAQAS M，et al.Viterbi algorithm performance analysis for different constraint length[C].2019 16th International Bhurban Conference on Applied Sciences and Technology(IBCAST).IEEE，2019：930-932.

[12] 楊敏.高速率低延時(shí)Viterbi譯碼器的設(shè)計(jì)與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2018，44(9)：56-58，62.

[13] 辛淵博，侯宏.基于FPGA的數(shù)字信道化接收機(jī)的研究及實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2009，35(5)：163-165，170.

[14] 仇佩亮，陳惠芳，謝磊.數(shù)字通信基礎(chǔ)[M].北京：電子工業(yè)出版社，2007.

作者信息:

吳雪玲，江  虹

(西南科技大學(xué) 信息工程學(xué)院，四川 綿陽(yáng)621000)