伍永鋒，馬思根

（貴州財經(jīng)大學信息學院，貴州 貴陽 550004）

0 引 言

信道編碼技術歷經(jīng)幾十年的發(fā)展歷程，從早期的線性分組碼、BCH碼、卷積碼，到后來的RS碼、級聯(lián)碼、代數(shù)幾何碼、Turbo碼和LDPC碼；從原來的代數(shù)譯碼方法，到后面的門限譯碼、Viterbi譯碼、迭代譯碼、軟判決譯碼等概率譯碼以及軟輸入輸出譯碼。Gallager[1]于1962年提出低密度奇偶校驗碼（low density parity check code，LDPC），并證明 LDPC 碼是一種性能接近香農(nóng)極限的編碼方案。然而由于受到當時計算機發(fā)展水平的限制，要實現(xiàn)這種迭代算法十分的困難。1981年，Tanner生成出了LDPC碼，并且用圖論的方式將碼字表示出來，現(xiàn)在這種圖示的方式叫做Tanner[2]圖。采用Tanner圖構(gòu)造的LDPC碼，通過并行譯碼可以顯著地降低譯碼復雜度。本文首先介紹下一代無線局域網(wǎng)IEEE802.11ac中LDPC的編碼參數(shù)，隨后分析了典型的LDPC譯碼算法，并利用Matlab搭建IEEE802.11ac仿真系統(tǒng)，最終得到適合ASIC實現(xiàn)的譯碼算法與參數(shù)。

1 IEEE802.11ac協(xié)議中的LDPC碼

802.11 ac中，LDPC支持的編碼速率、信息塊的長度以及編碼塊的長度如表1所示。

該協(xié)議規(guī)定的LDPC碼為系統(tǒng)碼，一個長度為n的碼字，包括了k個信息比特，另外加上n-k個校驗比特，以使碼字滿足：H×CT=0，H 為一個（n-k）×n的校驗矩陣。每個校驗矩陣可以分為大小為Z×Z的子矩陣，這些子矩陣為單位矩陣的循環(huán)矩陣或者零矩陣。

2 典型LDPC譯碼算法

對于LDPC碼而言，譯碼算法是決定該碼字性能和應用前景的一個重要因素，而對于譯碼算法的評價一般包括性能和復雜度兩個方面。Gallager在1962年提出LDPC碼的同時給出了兩種譯碼算法：基于硬判決的譯碼算法（bit flipping，BF）和基于軟判決的譯碼算法（probabilistic decoding）。BF譯碼算法運算量小，復雜度低，適合校驗集比較小的情況，但是沒有充分發(fā)揮LDPC碼的性能；Gallager首先在譯碼領域引入了軟輸入、軟輸出的譯碼思想，但是在當時計算機水平發(fā)展相對較低，基于軟判決的譯碼算法難以實現(xiàn)。隨著計算機水平的不斷提高，在1992年由 Mackay 和 Neal[3]提出的 BP（belief-propagation）迭代譯碼算法正是基于該思想，BP算法也就成為一種兼顧性能和復雜度的譯碼算法，在沒有環(huán)的情況下，BP算法等價于最大似然譯碼。雖然現(xiàn)在的計算機技術可以實現(xiàn)BP算法，但是BP算法仍然是一種復雜度相當高的算法。在隨后的研究中，如何盡量保持BP算法的糾錯性能的同時如何降低譯碼的復雜度，成為20世紀90年代LDPC碼的一個重要研究熱點，從而產(chǎn)生了最小和（MS）算法。

由于BP算法中有大量的乘法運算，在實現(xiàn)時會有相當大的復雜度，而且在大量的乘法下會損失精度?；趯?shù)域的BP譯碼算法，將乘法運算變?yōu)楹唵蔚募訙p法運算，簡化了硬件實現(xiàn)的難度。但是在其校驗信息比特的更新中設計大量的雙曲函數(shù)和反雙曲函數(shù)，需要消耗大量的存儲器資源，且會帶來量化精度的損失，同樣不利用硬件實現(xiàn)。由此出現(xiàn)了對校驗信息比特表達式的進一步簡化，提出了MS算法，以及修正的MS[4-5]算法，在MS算法上僅僅增加很少的復雜度來達到與BP算法十分接近的性能。

在對降低BP算法復雜度研究的同時，在BP算法基礎上尋找更好的譯碼算法也是大家努力的方向。特別是考慮到譯碼器硬件實現(xiàn)時迭代次數(shù)是有限的，加快BP算法的譯碼收斂速度將會提升譯碼吞吐量。一種分層的BP算法[6-7]應運而生，通過對LDPC碼校驗矩陣進行分層，相應的對BP算法的比特節(jié)點更新公式進行修改，使得信息在比特節(jié)點和校驗節(jié)點之間的傳播速度加快，從而可以減少迭代次數(shù)而達到和BP算法性能相同。

改進的MS算法是對BP算法的校驗節(jié)點計算公式進行的修改，而分層的BP算法則是對BP算法的比特節(jié)點計算公式進行的修改；因此，將這兩種改進算法的思想結(jié)合起來，能夠得到一種性能好、復雜度低和收斂速度快的分層修正MS譯碼算法，目前已經(jīng)成為LDPC碼譯碼器設計采用最多的譯碼算法。

3 譯碼算法性能分析

用于仿真的系統(tǒng)模型如圖1所示。本文將對不同的譯碼算法、不同的譯碼迭代次數(shù)、不同的歸一化因子，在圖示仿真系統(tǒng)中進行性能分析，確定ASIC實現(xiàn)方案。

圖1 LDPC編譯碼系統(tǒng)仿真環(huán)境

3.1 各種譯碼算法誤碼性能測試

由于802.11ac協(xié)議中的LDPC碼校驗矩陣具有近似下三角矩陣的結(jié)構(gòu)，故在編碼過程使用RU編碼方法，迭代次數(shù)為20次。仿真中采用蒙特卡洛方法進行誤碼率統(tǒng)計，圖中BP代表BP算法，Log-BP代表對數(shù)BP算法，Min-sum代表最小和譯碼算法，Layer-modify-MS代表修正的MS分層算法。

通過仿真圖2可以看出，最小和譯碼算法譯碼性能最差；修正的MS分層算法譯碼性能接近BP譯碼算法，但收斂時間更少，其復雜度高于最小和譯碼算法；從性能和復雜度綜合來看，分層修正MS譯碼算法最適于ASIC實現(xiàn)。故將采用分層修正的MS譯碼算法作為LDPC實現(xiàn)的譯碼算法。

3.2 譯碼迭代次數(shù)的選擇

譯碼迭代次數(shù)是影響LDPC碼譯碼性能的重要指標，圖3是不同迭代次數(shù)下的譯碼性能仿真圖。譯碼的迭代次數(shù)影響著系統(tǒng)的吞吐量和解碼延遲等系統(tǒng)的關鍵指標。如果譯碼迭代次數(shù)太小，會嚴重影響譯碼性能。但是譯碼性能也并不是隨著迭代次數(shù)成正比增加的，在迭代次數(shù)達到一個值時，譯碼次數(shù)增加所換來的性能增加并不明顯。相比增加迭代次數(shù)所帶來的實現(xiàn)復雜度，譯碼性能的提高是微不足道的。所以在保證譯碼性能的情況下，應盡量減少迭代次數(shù)，減少硬件實現(xiàn)的復雜度。為了確定適合802.11ac系統(tǒng)中的LDPC碼硬件實現(xiàn)的譯碼迭代次數(shù)，選取碼長為1944，碼率為1/2，歸一化因子為0.8進行仿真。由圖3可知，在相同信噪比下，迭代次數(shù)越大譯碼性能越好。當?shù)螖?shù)為20，30，40次時的譯碼性能非常接近，考慮到較大的迭代次數(shù)會帶來較大的解碼延遲，硬件設計中建議采用20次為最大迭代次數(shù)。

3.3 歸一化因子的選擇

圖4 LDPC碼在不同歸一化因子下的性能仿真

本文選用了分層修正的MS譯碼算法，在計算比特節(jié)點時，引入了歸一化因子，加快其收斂。為了找到合適的歸一化因子，本文對不同的歸一化因子進行了仿真。圖4是不同歸一化系數(shù)下的譯碼性能仿真圖，碼長為1944，最大迭代次數(shù)為20，在加性高斯白噪聲信道下（信噪比為1dB）的仿真?？梢钥闯觯敋w一化因子在0.8時，表現(xiàn)出了很好的性能，當歸一化因子為0.75時也接近0.8的性能，為了方便硬件實現(xiàn)以0.75作為歸一化因子。

4 結(jié)束語

本文分析了IEEE802.11ac系統(tǒng)中的LDPC譯碼算法，通過Matlab仿真平臺測試了BP算法、對數(shù)BP算法、最小和譯碼算法、分層修正MS譯碼算法的性能，結(jié)果表明分層修正譯碼算法適合硬件實現(xiàn)，同時給出了硬件實現(xiàn)時的譯碼參數(shù)。

[1]Gallager R G.Low-density parity-check codes[J].IEEE Transactions on Information Theory，1962：21-28.

[2]Tanner R M.A recursive approach to low complexity codes[J].IEEE Trans Inform Theory，1981，27（5）：533-547.

[3]Mackay D J C，Neal R M.Near shannon limit performance of low density parity check codes[J].IEEE Electronic Letters，1996，32（18）：1645-1646.

[4]Zarkeshvari F，Banihashemi A H.On implementation of min-sum algorithm for decoding low-density paritycheck （LDPC）codes[C]∥ Global Telecommunications Conference.Taipei，Taiwan：2002（2）：17-21.

[5]Howard S L，Gaudet V C，Schlegel C.Soft-bit decoding of regular low-density parity-check codes[J].IEEE Transactions on Circuits and Systems II，2005（99）：1-2.

[6]Li Z W，Chen L，Zeng L G，et al.Efficient encoding of quasi-cyclic low-density parity-check codes[J].IEEE Trans Commun，2006，51（1）：71-81.

[7]Kang S H，Park I C.Loosely coupled memory-based decoding architecture for low density parity check codes[J].IEEE Teans Circuits Syst I，2006，53（5）：1045-1056.