- 相關推薦
高速Viterbi譯碼器的優化和實現
摘要：大約束度卷積碼作為信道糾錯編碼在通信中得到了廣泛的應用，而其相應的Viterbi譯碼器硬件復雜度大，限制了譯碼速度。分析了Viterbi譯碼器的結構，優化了各模塊，合理地組織了存儲器結構，簡化了接口電路。用FPGA實現Viterbi譯碼器，提高了譯碼器速度。關鍵詞：卷積碼Viterbi譯碼ACS路徑度量存儲FPGA實現
Viterbi算法是一種基于最大后驗概率的卷積譯碼算法，應用廣泛。CDMA的IS-95標準和WCDMA3GPP標準將卷積碼作為高速實時數據傳輸的信道糾錯編碼，使Viterbi譯碼器成為移動通信系統的重要組成部分。
為保證糾錯性能，卷積碼結束度一般選擇比較大的，在3GPP中規定約束度K=9。出于實時性的考慮，移動通信系統中對譯碼時延的要求比較高，需要高速譯碼器的支持。可是Viterbi譯碼算法的復雜度、所需存儲器容量與結束長度成指數增長關系，成為限制譯碼器速度的瓶頸。Viterbi譯碼器每解碼一位信息位就需對2k-1個寄存器的狀態進行路徑度量，并對相應的存儲單元進行讀寫。這種情況下，可以采用狀態路徑存儲單元分塊的方法，以提高其譯碼性能，缺點是ACS單元與存儲器之間的接口電路十分復雜，不易實現。
本文分析和優化了Viterbi譯碼器的結構，提出了一種FPGA實現方案，簡化了接口電路，提高了速度。用這種結構實現的單片集成譯碼器譯碼速率達350kbps、時鐘頻率30MHz。以下先分析譯堿器總體結構，然后對各模塊設計和實現做詳細說明。
1算法簡述及譯碼器結構
本文采用3GPP標準規定的K=9，碼率r=1/2的(753,561)卷積碼，卷積編碼器送出的碼序列C，經過信道傳輸后送入譯碼器的序列為R。譯碼器根據接受序列R，按最大似然準則力圖找出正確的原始碼序列。
Viterbi譯碼過程可用狀態圖表示，圖1表示2個狀態的狀態轉移圖。Sj,t和Sj+N/2,t表示t時刻的兩個狀態。在t+1時刻，這兩個狀態值根據路徑為0或者1，轉移到狀態S2j+1和S2j+1,t+1。每一種可能的狀態轉移都根據接收到的有噪聲的序列R計算路徑度量，然后選擇出各個狀態的最小度量路徑（幸存路徑）。Viterbi算法就是通過在狀態圖中尋找最小度量路徑向前回溯L步，最后得到的即為譯碼輸出。
本設計采用XilinxVirtex600EFPGA芯片，在ALDEC公司的Active-HDL仿真環境下，用Verilog語言完成，并用Xilinx的ISE4綜合實現。Viterbi譯碼器系統框圖如圖2所示，主要由BMG(路徑計算模塊)、ACS(加比選模塊)、TB(路徑回溯模塊)、MMU（路徑存儲模塊）等部分組成。采用并行流水線結構，各個模塊在控制信號統一監控下工作，減少了讀取數據所需時間，充分發揮了FPGA高速計算的特性，提高了整個系統的效率。
2子模塊的優化和實現
2.1ACS模塊
由于采用的卷積碼約束度K=9，在譯碼過程中，每一時刻有2k-1=256個狀態，512個度量路徑值，為了獲得高速率，需采用盡可能多的ACS單元。但由于實際應用中需求電路面積小、功耗低，決定了ACS單元的數目不能太多。經過實驗證明，采用4個ACS單元并行處理，完成可以達到應用要求。
圖3度量路徑狀態分組圖
ACS單元用來計算選擇狀態的路徑度量。它需要不斷地讀出路徑度量作為操作數，然后將更新的度量寫回各個狀態。由于采用4個ACS單元并行處理，為不造成流水線堵塞，如何對RAM中的度量數據進行讀寫是關鍵。如前述，本文采用狀態路徑存儲單元分塊的方法。將所有狀態分成4組，分別對應于4個ACS。每次運算時，4個ACS同時從各組狀態值中讀取數據進行操作。
由圖1可知，狀態Sj和Sj+2/N在狀態轉移中同時得到兩個新狀態S2J和S2j+1。因此為了ACS能夠同時取出這兩個狀態值，Sj和Sj+2/N必須存儲在不同的RAM組中。同樣，兩個計算出來的新狀態S2j和S2j+1也應如此。遵循這種準則，則時也簡化接口電路，采用如下的分組算法：假設待分配狀態=Sj=Sk-2Sk-1…S1S0，所對應的RAM組為Rm，由于RAM共分成4組，則m=(Sk-2S1)S0（兩位二進制數表示）。狀態分組圖如圖3所示，從中可以看出，從狀態S128開始的后續狀態都有規律地交錯位置存儲。由此，ACS單元和狀態路徑存儲單元的接口電路只需采用兩個2×2交換器，如圖4所示。每一個交換器上連著兩個ACS單元和兩個RAM組。這兩個交換器由輸入狀態Sj的最高位Sk-2控制。當Sk-2=1時，交換器交叉互聯，如果Sk-2為0時，各ACS和RAM直接相連。這種接口設計十分容易實現。
在Viterbi譯碼算法中，譯碼狀態的轉移導致度量的讀出和寫入地址的不同，這樣用FPGA實現時就需要兩塊RAM采用乒乓模式實現。本文更新路徑存儲采用原位運算方法，也就是找出狀態轉移的規律性，建立轉移后的新狀態和轉移前的老狀態際址映射關系，使度量的更新在原位上進行，使存儲空間減小一半。
2.2幸存路徑管理模塊
幸存路徑的存回溯是Viterbi算法關鍵的一步，最終的譯碼輸出從對幸存的回溯中得到。由于采用基2的狀態轉移算法，當前時刻對應的前序時刻狀態只有2個，所以在路徑回溯中采用1bit指針算法。也就是說，在每個狀態路徑更新時，只需寫1bit路徑狀態轉移信息。幸存路徑存儲單元可看作一個存儲器陣列，每列對應一個狀態，一列中的每個單元都有一個1位的指針。在實際設計中，考慮到數據總線的帶寬有限，對于8位的幸存路徑數據總線，在幸存路徑存中將256個狀態分成32塊。對應幸存路徑時，先通過當前狀態地址尋址的方式來選擇所對應的幸存路徑塊。
在實際應用中，為了保證譯碼的準確度，幸存路徑的回溯長度通常取4～5倍約束長度，本文回溯長度定為64。如圖5所示，當一個解碼初始信號進來后，系統把當前所有狀態中的最小狀態，也就是最小狀態值作為當前狀態值，路徑回溯模塊把地址值送入MMU中，從32個分組塊中選取相應的幸存路徑存到幸存狀態值（8位），然后根據當前狀態的指針從這8位數據中得到1位幸存路徑比特，而下一個狀態值由當前狀態的低7位和這個幸存路徑比特決定。當回溯了64步后，控制信號給出一個輸出指示時，當前狀態值的最高位即是解碼輸出值。
圖5路徑回溯模塊框圖
本文重點從ACS的并行處理、度量路徑的存儲管理和路徑回溯上對Viterbi譯碼方法進行了討論。從實際應用出發，考慮到硬件功耗的面積的減小，采用了4個ACS并行，路徑的存儲和管理都采取了分組的模式，簡化了接口電路，譯碼達到了較高的速度，完全可以滿足3GPP標準的要求。用Xilinx的Virtex600EFPGA芯片實現了K=9、碼率為1/2、編碼速率為350kbps、時鐘頻率40MHz的Viterbi譯碼器。表1列出了XilinxISE對本設計綜合布線報告中提供的參數。
表1Viterbi譯碼器布線參數表
NumberofSlices:1,596outof6,19223%
SliceFlipFlops:620
4inputLUTs:1,320
NumberofSlicescontaining
unrelatedlogic:0outof1,5960%
NumberofbondedIOBs:30outof15319%
NumberofBlockRAMs:20outof7234%Totalequivalentgatecountfordesign:474,210
【高速Viterbi譯碼器的優化和實現】相關文章：
優化稅制，實現增值稅轉型08-07
優化稅制，實現增值稅轉型08-07
3-DES算法的FPGA高速實現08-06
高速紅外VFIR控制器的設計與實現08-06
換體DMA高速數據采集電路的CPLD實現08-06
高速公路視頻超速臨控系統的實現08-06
USB接口的高速數據采集卡的設計與實現08-06