QC－LDPC碼的截短技術(shù)研究

劉曉健， 汪 烜

（上海無線電設(shè)備研究所，上海200090）

0 引言

LDPC（low－density parity check code）碼屬于傳統(tǒng)的線性分組碼，在使用軟判決迭代譯碼算法時可以達到了漸進香農(nóng)限的譯碼性能，此外它還具有較靈活的編譯碼方案和誤碼率基底較低的特點。其中一類校驗矩陣具有準循環(huán)結(jié)構(gòu)的LDPC（QC－LDPC）碼，由于其編碼器設(shè)計方便，并且利于解碼器的并行化設(shè)計，目前已被IEEE 802．16e，IEEE 802．11n和數(shù)字電視廣播DVB2－S20等標準采納［1－3］。

QC－LDPC碼雖然有以上優(yōu)點，然而在碼長和碼率上的靈活性比較有限。在無線通信傳輸系統(tǒng)中，如果只采用幾個固定碼率的碼字進行傳輸，會影響系統(tǒng)的整體傳輸吞吐率。因此需要根據(jù)實際的信道狀況，動態(tài)地配置傳輸碼率。在目前的一些通信標準中，往往通過給出一系列不同碼長和碼率的QC－LDPC碼來滿足以上需求，然而要更加靈活地對碼長和碼率進行調(diào)整，就需要求助于其他的一些方法。本文結(jié)合PEXIT分析方法［4］，給出了一種優(yōu)化地選取截短比特的方法。

1 背景知識介紹

1．1 QC－LDPC碼簡介

QC－LDPC碼的校驗矩陣H是由一系列尺寸相同的循環(huán)置換矩陣（CPM）和零矩陣（ZM）構(gòu)成的。通常H可以由如下所示的基矩陣擴展得到：

式中：Ai，j，1≤i≤m，1≤j≤n，表示一個CPM或ZM。Ai，j的取值由具體的構(gòu)造方法確定。以IEEE 802．16 e中給出的1／2碼率的 QC－LDPC碼為例，該碼的校驗矩陣的基矩陣尺寸為12×24。當(dāng)Ai，j＝－1時，它代表一個24×24的ZM；當(dāng)Ai，j＝ω，－1＜ω＜24時，它對應(yīng)的CPM 具有如下形式：第一行的唯一一個非零單元位置在第ω列，第二行的唯一一個非零單元在第（ω＋1）mod 24行，其他各行依次類推。為了避免在Tanner圖上出現(xiàn)圈四的情況，Hb中任意兩行和任意兩列中不能包含超過兩個相同的非零元素。QC－LDPC碼的高速的譯碼器設(shè)計方便。采用BP或者MS算法時，將各個CPM中非零元素對應(yīng)的變量節(jié)點（校驗節(jié)點）信息存儲在獨立的RAM中，通過一定的時序安排便可以實現(xiàn)半并行的譯碼方式?；赒C－LDPC碼的高速譯碼算法研究及硬件設(shè)計，有興趣的讀者可以參考文獻等［5－7］。

1．2 PEXIT分析方法

QC－LDPC碼是一類特殊的基于原型圖（prototype）方法構(gòu)造的LDPC碼，通過把（1）式中的非負元素替換成“1”，并畫出對應(yīng)的Tanner圖即可得到它們的原型圖。用PEXIT來分析QCLDPC碼的收斂門限相比直接用EXIT來分析主要具有兩大優(yōu)點：運算量少和通用性高。

運算量的減少主要源于原型圖的尺寸遠遠小于校驗矩陣H；通用性高，是由于在IEEE 802．16 e等標準中，同一種碼率條件下，不同長度的QCLDPC碼具有相同的原型圖，因此對一個原型圖進行分析得到的結(jié)果可以適用于該原型圖對應(yīng)的所有碼長的QC－LDPC碼。PEXIT的原理及相關(guān)步驟可以參考相關(guān)文獻［4］。

2 非規(guī)則QC－LDPC碼的截短技術(shù)

所謂截短，指的是發(fā)送端在編碼時在信息序列的某些特定位置插入預(yù)設(shè)的比特（比如都插入比特“1”），且這些特定的位置是發(fā)送端和接收端預(yù)先約定的。在發(fā)送端輸出的序列中，這些預(yù)設(shè)的比特可以不用發(fā)送，因而縮短了碼長，同時由于這些比特占用了一部分信息比特的位置，并且它們不包含有效信息，所以截短后的碼字碼率更低。在接收端譯碼時，譯碼器可以將預(yù)設(shè)的比特的置信度設(shè)為無限大?？紤]到置信度無限大的比特在迭代譯碼過程中作用不大，為了減少運算量，通?？梢詫⑦@些比特對應(yīng)的校驗矩陣中的列刪除，用于對截短的碼字序列進行譯碼。

截短技術(shù)對于規(guī)則QC－LDPC碼的作用在文獻［8］中已經(jīng)有較為詳細的分析，這種技術(shù)可以增加給定的規(guī)則QC－LDPC碼的girth，即Tanner圖上最短圈的長度。由于girth是影響規(guī)則QCLDPC碼譯碼性能的主要因素之一，較大的girth通?？梢允勾a字在瀑布區(qū)取得更好的性能。對于目前無線通信系統(tǒng)中常用的非規(guī)則QC－LDPC碼，通常設(shè)計人員更關(guān)心的是碼字在瀑布區(qū)的性能，即譯碼算法能否在較低的信噪比條件下收斂。決定譯碼器收斂門限的主要因素是校驗矩陣的行列重量分布，因此對于非規(guī)則QC－LDPC碼，用于規(guī)則碼的截短比特選擇方法不再適用，因而在選擇合適的截短位置時必須將校驗矩陣的重量分布考慮在內(nèi)。下面本文以非規(guī)則QC－LDPC碼為對象，給出一種優(yōu)化選擇截短位置的算法。

在軟判決迭代譯碼的過程中，變量節(jié)點vj輸出信息的可靠度與它的度數(shù)λ（j）成正比，而校驗節(jié)點ci在低信噪比區(qū)域輸出信息的可靠度與它的度數(shù)ρ（i）成正反比，因此在截短后的Tanner圖中，應(yīng)該盡量保留那些度數(shù)比較大的變量節(jié)點，同時減少與這些變量節(jié)點相連的校驗節(jié)點的度數(shù)。這樣，這些變量節(jié)點便可以得到更加可靠的外信息，同時由于它們的度數(shù)比較大，因而能夠使得相對更多的校驗節(jié)點收到可靠的外信息，從而加快算法的收斂。變量節(jié)點vj收到的外信息來自與它相連的各個校驗節(jié)點ci，i∈A（j）。這些校驗節(jié)點輸出給該變量節(jié)點的信息則來自于除vj以外與它們相連的變量節(jié)點。因此可以用下面的式子來近似計算與變量節(jié)點vj的外信息相關(guān)的變量節(jié)點數(shù)量：

式中：ρ（i）表示校驗節(jié)點ci的度數(shù)。由上式可以看到，SE（j）受到兩個因素的影響：該變量節(jié)點vj的度數(shù)λ（j）；與該變量節(jié)點相連的校驗節(jié)點的度數(shù)。

利用式（2）提供的信息作為輔助，可以按照如下方法來選擇截短的非規(guī)則QC－LDPC碼的變量節(jié)點：首先，選擇原型圖上度數(shù)最小的變量節(jié)點構(gòu)成候選節(jié)點集合，接著用式（2）計算這些候選節(jié)點的SE（j），最后選取SE（j）最大的變量節(jié)點作為被截短的節(jié)點。選擇度數(shù)最小的變量節(jié)點是為了盡量保留度數(shù)較大的變量節(jié)點，而在這些節(jié)點中選擇SE（j）最大的節(jié)點截短可以盡可能地減少截短后得到的校驗矩陣中度數(shù)比較大的校驗節(jié)點的度數(shù)。根據(jù)這樣的選擇方式，截短后的碼字在譯碼時能夠更快地收斂，從而得到更好的瀑布區(qū)性能。有時候會遇到不止一個候選變量節(jié)點都具有最大的SE（j），這時候應(yīng)用上一節(jié)中介紹的PEXIT分析方法，對于將這些候選節(jié)點截短后的原型圖逐個進行分析，從中選取能夠得到最低門限的候選節(jié)點。

根據(jù)以上敘述，具體的搜索算法如下所示：

a）初始化：令λ＝［λ（1），λ（2），…，λ（K）］表示信息位對應(yīng)的原型圖上變量節(jié)點的度數(shù)分布，G∞＝｛1，2，…，K｝表示可用的變量節(jié)點集合，T表示需要被截短的變量節(jié)點總數(shù)；

b）尋找候選節(jié)點：從所有可用的變量節(jié)點中找出最小的度數(shù)cdmin＝min｛λ（j），j∈G∞｝，如果λ（j）＝cdmin，則將變量節(jié)點vj設(shè)為候選節(jié)點；

c）用式（2）計算所有候選節(jié)點的SE（j）；

d）選擇候選節(jié)點中SE（j）最大的節(jié)點作為進一步的候選節(jié)點，如果這些候選節(jié)點不止一個，則用PEXIT分析方法分別求將它們截短后的原型圖的收斂門限，從中選取門限最低的作為該次迭代的輸出；

e）如果節(jié)點vJ最終被選中，則G∞＝G∞＼｛J｝，對于所有的i∈A（J），ρ（i）＝ρ（i）－1。

f）T＝T－1，如果T＝0，中止迭代，否則回到步驟2繼續(xù)執(zhí)行。

以上給出的截短節(jié)點選擇算法也適用于普通的非規(guī)則LDPC碼，這時只要將以上在原型圖上進行的操作移植到Tanner圖上，同時把PEXIT分析方法更換為普通的EXIT分析方法或密度演變算法即可。

3 仿真結(jié)果與分析

這一節(jié)以IEEE 802．16 e和IEEE 802．11 n中給出的QC－LDPC碼為對象，分析比較截短算法的效果。仿真環(huán)境為AWGN信道，信號采用BPSK調(diào)制，譯碼算法為BP算法，最大迭代次數(shù)設(shè)為100。本文用A－X的字母對基矩陣的列從左到右進行編號，表1截短圖案中的字母分別表示被截短的變量節(jié)點對應(yīng)的基矩陣中列的位置。

本文分別選取IEEE 802．16 e中碼率為1／2，碼長為2 304的 QC－LDPC碼和IEEE 802．11 n中碼率為1／2，碼長為1 944的QC－LDPC碼作為對象，原型圖上的截短節(jié)點數(shù)設(shè)為4，截短后的碼率為0．4。下表中給出了采用不同的截短圖案時用PEXIT分析方法計算出的收斂門限，并分析了截短以后校驗矩陣的girth。表中第一欄的截短圖案（A，B，E K）和（C，D，F(xiàn)，G）是用上一節(jié)介紹的方法得到的，其他兩欄的圖案是窮舉搜索得到的，旨在提高校驗矩陣的girth。與規(guī)則QC－LDPC碼的截短不同，girth的增加并不會改善碼字的收斂門限，而通過本文給出的方法尋找的截短圖案則能給出更好的結(jié)果。

表1 不同截短方案用PEXIT分析方法計算得到的收斂門限

在下面兩張仿真曲線圖中，分別對應(yīng)表1中的各種截短方案，給出了對應(yīng)的仿真曲線，由這兩張圖可以看到，通過優(yōu)化得到的截短圖案相比表1中的其他截短圖案都取得了更好的性能。其中圖1中，優(yōu)化選取的圖案1相比圖案2和3，在誤幀率為10－3時，分別取得了約0．2 dB和0．35 dB的增益；圖2中，優(yōu)化選取的圖案1相比圖案2和3，在誤幀率為10－3時，分別取得了約0．25 dB和0．5 d B的增益。

圖1 （2 304，1152）QC－LDPC碼各種截短方案的誤幀率比較

4 結(jié)論

本文討論了如何在給定的QC－LDPC碼的基矩陣上通過截短技術(shù)來獲得可變速率的QC－LDPC碼的構(gòu)造方法。這種方法可以在一定范圍內(nèi)，提高QC－LDPC碼在碼長和碼率方面的靈活性，從而使之在實際應(yīng)用中能夠更加靈活地適應(yīng)各種場景。結(jié)合PEXIT分析方法，本文分別給出了如何優(yōu)化地選擇截短位置的方法。數(shù)據(jù)分析和仿真結(jié)果顯示，本文的選擇方法能夠給出較為理想的解決方案。

圖2 （1 944，972）QC－LDPC碼各種截短方案的誤幀率比較

［1］ IEEE Standard for Local and Metropolitan Area Networks Part 16．Air Interface for Fixed Broadband Wireless Access Systems［J］．IEEE Std 802，16TM－2004，2004．

［2］ IEEE 802．11－Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）Specifications［J］．IEEE，2007．

［3］ ETSI EN302 307 V1．1．1－2005 DVB．Second Generation Framing Structure，Channel Coding and Modulation System for Broadcasting，Interactive Service，News Gathering and Other Broadband Satellite Applications［S］．2005．

［4］ Liva G andChiani M．Protograph LDPC Codes Design Based on Exit Analysis［C］．GLOBECOM′07．IEEE，2007，（11）：3250－3254．

［5］ 趙春明，許恩楊，姜明，黃鶴．雙渦輪結(jié)構(gòu)低密度奇偶校驗碼解碼器［P］．專利號ZL 2006100965359．

［6］ 單鳴．LDPC碼編解碼技術(shù)研究及實現(xiàn) ［D］．碩士論文，東南大學(xué)，2004．

［7］ Yongmei Dai；Zhiyuan Yan and Ning Chen．Optimal Overlapped Message Passing Decoding of Quasi－Cyclic LDPC Codes［J］．IEEE Transactions on VLSI Systems，2008，16（5）：1063－8210．

［8］ M．P．C．Fossorier．Quasi－cyclic Low－density Parity－check Codes from Circulant Permutation Matrices［J］．IEEE Trans．Inform．Theory，Aug．2004，50（8）：1788－1794．