劉曉健， 汪 烜

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

0 引言

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

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

1 背景知識(shí)介紹

1．1 QC－LDPC碼簡(jiǎn)介

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

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

1．2 PEXIT分析方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

本文討論了如何在給定的QC－LDPC碼的基矩陣上通過截短技術(shù)來(lái)獲得可變速率的QC－LDPC碼的構(gòu)造方法。這種方法可以在一定范圍內(nèi)，提高QC－LDPC碼在碼長(zhǎng)和碼率方面的靈活性，從而使之在實(shí)際應(yīng)用中能夠更加靈活地適應(yīng)各種場(chǎ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)低密度奇偶校驗(yàn)碼解碼器［P］．專利號(hào)ZL 2006100965359．

［6］ 單鳴．LDPC碼編解碼技術(shù)研究及實(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．