0 引言

    糾錯碼技術在數字通信中具有重要作用，其中卷積碼的編碼方式，由于優良的糾錯性能被廣泛應用，而Viterbi譯碼方式作為卷積碼的一種最佳概率譯碼方法，對于卷積碼的廣泛應用具有重要價值^[1-2]。近年來，FPGA作為一種半定制電路，廣泛應用于數字信號處理系統中，為Viterbi譯碼器的實現提供了有利條件^[3]。

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

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

1 改進Viterbi算法

1.1 算法原理

    Viterbi算法是一種用于解決有限狀態離散時間馬爾科夫鏈的狀態估計問題的優化算法^[12]。圖1^[1]所示的基二網格圖顯示了卷積碼的譯碼過程，具體描述可參見文獻[1]。時間節點t表示第t個信息碼元，Viterbi譯碼器從網格中找出最大似然路徑。

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

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

1.2 算法改進的具體描述

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

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

2 理論分析

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

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

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

2.2 改進算法分析

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

3 仿真分析

3.1 MATLAB仿真結果分析

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

3.2 ISE仿真結果分析

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

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

    Viterbi譯碼器的測試主要包括功能驗證與譯碼器的糾錯性能兩部分。

    首先進行功能驗證，所有數據都是理想的。因為τ=20，則譯碼器以20個數據為一組譯碼，本文的Viterbi譯碼器采用的是截尾譯碼，故利用MATLAB產生16個隨機序列加上4個0組成一組信息序列為C1：11111101101110110000，經過編碼器后的輸出序列為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仿真結果如圖8所示。

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

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

4 結論

    本設計主要針對ACS和SMU單元，簡化譯碼器的結構，降低硬件實現的復雜度，提高運算速度。在加比選單元的控制度量部分，為了解決路徑度量數據溢出問題，本文提出了預定義存儲度量值寄存器容量法，減小了運算量，提高了譯碼速度。在幸存路徑存儲部分，優化了存儲方式， 采用步進式存儲方法，降低了譯碼器的功耗。回溯譯碼時，采用奇偶回溯法譯碼方式，根據幸存狀態的奇偶性完成輸出，減小了RAM的存儲空間。仿真結果表明，本文的優化設計能夠大大簡化硬件電路的結構，在譯碼器的設計中具有應用價值。

參考文獻

[1] 王新梅，肖國鎮.糾錯碼—原理與方法(修訂版)[M].西安：西安電子科技大學出版社，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譯碼器的設計[D].成都：電子科技大學，2008.

[4] 平磊.面向5G通信的咬尾卷積碼和Turbo碼技術研究[D].西安：西安電子科技大學，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信號分析[J].電子與信息學報，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] 楊敏.高速率低延時Viterbi譯碼器的設計與實現[J].電子技術應用，2018，44(9)：56-58，62.

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

[14] 仇佩亮，陳惠芳，謝磊.數字通信基礎[M].北京：電子工業出版社，2007.

作者信息:

吳雪玲，江  虹

(西南科技大學 信息工程學院，四川 綿陽621000)