伍永鋒，馬思根

（貴州財(cái)經(jīng)大學(xué)信息學(xué)院，貴州 貴陽(yáng) 550004）

0 引 言

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

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

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

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

2 典型LDPC譯碼算法

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

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

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

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

3 譯碼算法性能分析

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

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

3.1 各種譯碼算法誤碼性能測(cè)試

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

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

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

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

3.3 歸一化因子的選擇

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

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

4 結(jié)束語(yǔ)

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