馬 慧，吳彥鴻，王宏艷

(1.航天工程大學(xué) 電子與光學(xué)工程系，北京 101416；2.航天工程大學(xué) 航天信息學(xué)院，北京 101416)

0 引言

20世紀60年代以來，前向糾錯(Forward Error Correction，F(xiàn)EC)一直是空間通信的重要組成部分。隨著超大規(guī)模集成電路技術(shù)的發(fā)展，相比于現(xiàn)有Turbo編碼，LDPC編碼能夠更好地實現(xiàn)譯碼復(fù)雜度和誤碼平層之間的性能折衷，這無疑更適合下一代高速數(shù)據(jù)通信中的FEC[1-2]。盡管LDPC編碼性能逼近香農(nóng)極限，但香農(nóng)編碼只能給出理論結(jié)構(gòu)，未能提出具體構(gòu)造方法。校驗矩陣的結(jié)構(gòu)是LDPC編碼過程的構(gòu)造基礎(chǔ)，不僅直接關(guān)系到編碼性能的優(yōu)異程度，還會對系統(tǒng)的編譯碼復(fù)雜度產(chǎn)生影響[3]。

現(xiàn)有LDPC編碼主要通過幾何、代數(shù)和圖論等構(gòu)造方式構(gòu)造[4-5]，例如基于歐拉圖結(jié)構(gòu)的圖論構(gòu)造法[6]、基于雙對角矩陣的序列構(gòu)造法[7]和基于停止集優(yōu)化的原模圖構(gòu)造法[8]等，其中原模圖構(gòu)造的LDPC編碼在目前的通信衛(wèi)星、遙感衛(wèi)星、導(dǎo)航衛(wèi)星和星際探測等一系列航天活動中發(fā)揮重要的作用[9-10]。根據(jù)構(gòu)造主體的不同可將原模圖構(gòu)造編碼的研究分為2類:原模圖模板矩陣的構(gòu)造和原模圖循環(huán)移位子陣的構(gòu)造。模板矩陣的構(gòu)建對于不規(guī)則LDPC編碼來說至關(guān)重要，文獻[11]提出的啟發(fā)式漸進增加邊(Progressive Edge-Growth Graphs，PEG)算法改善了Tanner圖圍長分布特性，近年來被廣泛應(yīng)用于矩陣構(gòu)建過程。文獻[12]構(gòu)造了一種具有優(yōu)異性能的低碼率通用LDPC編碼，但對于模板矩陣準循環(huán)結(jié)構(gòu)的利用仍不充分，并且為有效解決基于原模圖編碼的秩虧現(xiàn)象，占用了特殊編碼結(jié)構(gòu)，這無疑增加了編碼的復(fù)雜度。文獻[13]通過歐式幾何優(yōu)化方法對準循環(huán)結(jié)構(gòu)中的最小重碼字進行優(yōu)化。文獻[14]設(shè)計多邊原模圖消除QC結(jié)構(gòu)中無法避免的小環(huán)，文獻[15-16]通過改善多對角線奇偶校驗結(jié)構(gòu)及準循環(huán)雙對角線擴展等方法得到較好性能的碼字。文獻[17]通過擴展的ACE算法對原模圖信息節(jié)點進行重新排序，在不損壞準循環(huán)結(jié)構(gòu)的同時，克服了秩缺失問題。但是該方法在構(gòu)造時需要對環(huán)進行搜索和結(jié)構(gòu)分析，仍舊存在一定的復(fù)雜性。文獻[18]對原模圖結(jié)構(gòu)進行優(yōu)化設(shè)計，克服了AR4JA編碼誤碼平底現(xiàn)象。文獻[19]提出采用PEG-ACE兩步擴展法對原模圖擴展后的循環(huán)子陣進行環(huán)結(jié)構(gòu)優(yōu)化，雖然經(jīng)PEG-ACE算法擴展后得到的AR4JA編碼的復(fù)雜度明顯降低，但是該算法中PEG擴展過程忽略了備選節(jié)點的考慮，節(jié)點度分布距離最佳分布仍舊存在差距；ACE擴展過程缺少對嵌套原模圖中塊環(huán)結(jié)構(gòu)分析，算法性能存在一定的誤差和誤碼平層現(xiàn)象，因此需要對其加以改進。本文提出了一種基于原模圖擴展的AR4JA碼優(yōu)化構(gòu)造方法。針對原模圖結(jié)構(gòu)對應(yīng)的基矩陣，提出改進的PEG擴展和QC-ACE優(yōu)化搜索循環(huán)置換子矩陣偏移量，聯(lián)合優(yōu)化與改善編碼碼字的圍長及環(huán)分布關(guān)系，使其適用于原模圖的擴展，提高碼字的誤碼率性能。

1 AR4JA編碼的原模圖構(gòu)造

1.1 原模圖構(gòu)造基本原理

目前由原模圖構(gòu)造的LDPC編碼在通信衛(wèi)星、遙感衛(wèi)星和星際探測等一系列航天活動中廣泛應(yīng)用，將原模圖用變量G=(V，C，E)表示，其中V表示變量節(jié)點集，C表示校驗節(jié)點集，E表示連接邊集合。將變量節(jié)點ve∈V和校驗節(jié)點ce∈C之間存在的連接邊定義為e∈E，由于原模圖允許平行邊的存在，連接邊映射e→(ve，ce)并非是一一對應(yīng)的。

本文針對原模圖LDPC編碼的原模圖構(gòu)造展開分析，原模圖與Tanner圖的不同之處在于原模圖可允許并行邊的存在，因此其結(jié)構(gòu)中一般具有少量的節(jié)點[20-21]。原模圖的復(fù)制模板圖G如圖1所示。

圖1 原模圖的復(fù)制模板圖G

該原模圖可被視為在(n=4，k=1)LDPC編碼Tanner圖的基礎(chǔ)上添加并行邊得到的。G是由|V|=4個變量節(jié)點和|C|=3個校驗節(jié)點組成，其中變量節(jié)點包括節(jié)點1～4，校驗節(jié)點包括節(jié)點A～C，共有|E|=9條連接邊。G中節(jié)點對應(yīng)的校驗矩陣HG的表達式為：

需要強調(diào)的是，不同于Tanner圖中的映射暗含著每個變量節(jié)點必然對應(yīng)傳輸信道中的一個編碼符號的假設(shè)，原模圖中的變量節(jié)點集V可以包含未發(fā)送節(jié)點，未發(fā)送變量節(jié)點的采用可改善原模圖編碼的性能。因此變量節(jié)點vi∈V可被指定為發(fā)送節(jié)點或未發(fā)送節(jié)點，定義變量節(jié)點中發(fā)送節(jié)點的個數(shù)為n，未發(fā)送節(jié)點的個數(shù)為u，則

n+u=|V|。

再定義校驗節(jié)點個數(shù)為c=|C|，則原模圖編碼后的碼率為：

將原模圖模板中的校驗節(jié)點和變量節(jié)點進行L倍復(fù)制，可得到由L份相互重疊的副本構(gòu)成的子圖。再按照一定的規(guī)則，將各個副本中對應(yīng)相同位置的連接邊進行置換重排，得到的交織圖稱為擴展衍生圖，由此構(gòu)造的LDPC編碼稱為原模圖LDPC碼。以圖1為例，對模板G進行3次復(fù)制并置換后得到的衍生圖G′，如圖2所示?？煽闯鲅苌鷪DG′繼承了原模圖的特性，具有與G相同的碼率、節(jié)點度分布以及鄰域特性，因此二者的譯碼門限相同。

圖2 原模圖置換后的擴展衍生圖G′

將原模圖LDPC碼對應(yīng)一致校驗矩陣一般通過基矩陣和循環(huán)置換矩陣聯(lián)合表述，當設(shè)定置換矩陣的維數(shù)p時，H與基矩陣和循環(huán)移位矩陣的對應(yīng)關(guān)系為：

-1≤hi，j≤p-1。

式中，矩陣I(hij) (1≤i≤m，1≤j≤n)為p×p維循環(huán)置換矩陣；hi，j為單位矩陣I的循環(huán)移位位數(shù)，其中當hi，j=-1時，I(hij)為零矩陣；當hi，j=0時，I(hij)為單位矩陣I；其他情況下，I(hij)表示單位矩陣循環(huán)右移hi，j位后的矩陣。由于H中循環(huán)矩陣和零矩陣的位置取決于基矩陣的設(shè)置，而置換矩陣決定著單位矩陣的循環(huán)移位位數(shù)。由于原模圖構(gòu)造的校驗矩陣在本質(zhì)上決定了碼的性能，因此對AR4JA碼性能的優(yōu)化離不開原模圖的構(gòu)造。

1.2 AR4JA編碼原模圖的模型構(gòu)建

AR4JA編碼的原模圖構(gòu)造流程表述如下：

① 結(jié)合模擬退火算法及密度進化理論進行原模圖譯碼搜索的門限預(yù)測，所設(shè)計的AR4JA對應(yīng)的原模圖構(gòu)造原理圖如圖3所示[18]。圖中代表信息比特的圓形節(jié)點分為2種，其中灰色實心圓表示待傳輸?shù)淖兞炕蛘咝ｒ灡忍?，白色空心圓表示非傳輸?shù)膭h除比特；內(nèi)含加號的方框表示校驗節(jié)點。以矩形框內(nèi)1/2碼率AR4JA編碼原模圖模板為基礎(chǔ)，在矩形框外部擴展校驗節(jié)點關(guān)聯(lián)復(fù)合變量節(jié)點可實現(xiàn)編碼的碼率擴展，得到的AR4JA系列碼率表達式為：

(5)

圖3 AR4JA編碼原模圖構(gòu)造原理

② 圖3所示的AR4JA編碼原模圖模板允許多重邊的存在，因此需要對其進行平行邊的消除使其轉(zhuǎn)變?yōu)門anner圖結(jié)構(gòu)。首先將該原模圖作為QC-LDPC結(jié)構(gòu)中的基本Tanner圖模板，對其進行矩陣復(fù)制操作以得到L個副本，然后對復(fù)制后原模圖中各對應(yīng)邊重排擾亂，使不同副本間節(jié)點互連，從而得到所需規(guī)模的Tanner圖。在此需要注意的是，在對不同副本中相同位置的連接邊隨機擾亂的過程中，連接邊對應(yīng)兩個模板間的節(jié)點序號需要保持不變。

③ 將構(gòu)造的Tanner圖映射為校驗矩陣H的形式，圖中的方框節(jié)點對應(yīng)H的行，圓形節(jié)點對應(yīng)H的列。當節(jié)點之間存在連接邊時，對應(yīng)H相應(yīng)位置為“1”；反之則為“0”。然后將H的基矩陣進行擴展得到所需的循環(huán)移位矩陣，也就是將“0”、“1”分別映射為一定維數(shù)的全零陣或者單位循環(huán)方陣。矩陣擴展結(jié)構(gòu)的物理實現(xiàn)過程可通過圖4所示的立體Tanner圖模型表示。

圖4 AR4JA編碼原模圖立體Tanner圖模型

由圖4可知，經(jīng)過空間擴展后的Tanner圖既繼承了基本原模圖的性質(zhì)，具有和初始原模圖模板相同的連接關(guān)系和度分布，還存在一定的空間交織結(jié)構(gòu)使其具有增大碼距的效果。復(fù)制擴展后的原模圖既繼承了原模圖模板的基本性質(zhì)，又增加了編碼隨機度，因此可將其作為構(gòu)建高效能不規(guī)則LDPC編碼的有效方法。通過對模板基矩陣進行循環(huán)擴展再分裂，可進一步消除停止集及狀態(tài)惡化的陷阱集，環(huán)分布的自由度也得以改善。

2 兩步擴展原模圖編碼的優(yōu)化構(gòu)造

要想得到性能優(yōu)越的AR4JA碼，僅僅設(shè)計出原模圖是不夠的，還需要對校驗矩陣的環(huán)結(jié)構(gòu)進行分析。基矩陣中的“塊環(huán)”作為擴展矩陣不同環(huán)之間的連接基礎(chǔ)，是決定譯碼性能的關(guān)鍵因素之一。當基矩陣對應(yīng)的塊環(huán)長度相同時，矩陣擴展后的環(huán)長與循環(huán)移位值和移位子陣維度p有關(guān)。因此在準循環(huán)編碼的構(gòu)造過程中，原模圖的既要考慮基矩陣的設(shè)計，又要兼顧循環(huán)置換矩陣的設(shè)置。文獻[11]將原模圖的構(gòu)造分成兩步擴展進行，先采用PEG算法尋找具有最佳圍長參數(shù)；然后通過QC-ACE算法搜索子矩陣循環(huán)偏移量，以最大限度延長矩陣中的環(huán)長，所構(gòu)造的碼字具有復(fù)雜度低、結(jié)構(gòu)性好的特點。但是在運用PEG算法時，未對備選節(jié)點的選擇分情況討論，因此度分布距離最佳分布有一定差距；QC-ACE算法中未考慮嵌套環(huán)條件下的算法誤差性能，兩步擴展算法仍舊存在優(yōu)化空間需要進一步對編碼性能進行優(yōu)化。

2.1 改進的PEG擴展算法

傳統(tǒng)PEG算法構(gòu)造基矩陣時，僅局限于圍長最大化，未對備選節(jié)點的選擇分情況討論，因此度分布距離最佳分布有一定差距。因此為了進一步優(yōu)化基矩陣的環(huán)連通性，需要考慮多個備選節(jié)點情況并加以討論。文獻[22]將節(jié)點的ACE值作為環(huán)連通性的測度，并引入了ACE選擇準則：當中至少包含2個元素時，選擇使得引入的環(huán)具有較大ACE校驗節(jié)點與vi連接。受該準則的啟發(fā)，本文對PEG擴展算法進行改進。

表1 改進的PEG基矩陣擴展算法原理

上述PEG算法中，滿足原模圖擴展約束的校驗節(jié)點隨著每一條邊的擴展變化，由于在Tanner圖不允許出現(xiàn)重邊的出現(xiàn)，所以在擴展原模圖時要保證擴展層數(shù)不低于最大重邊數(shù)。

2.2 改進的QC-ACE算法

在搜索原模圖構(gòu)造矩陣中的循環(huán)偏移量時，QC-ACE算法忽略了嵌套環(huán)中公共節(jié)點的存在，使得到的實際變量信息的ACE值產(chǎn)生偏差。采用改進的QC-ACE算法時，針對Tanner圖中的環(huán)間關(guān)系分情況討論，對于不存在重邊的原模圖直接采用原環(huán)間ACE值進行準循環(huán)擴展，對于嵌套環(huán)情況時，采用改進的復(fù)合環(huán)系統(tǒng)的ACE值進行計算。該ACE值的本質(zhì)是指嵌套環(huán)的外部獨立有效連接邊，因此在累積計算各環(huán)路節(jié)點ACE值之后，需要減去公共環(huán)中的重復(fù)ACE值，以避免外消息傳遞自反饋導(dǎo)致譯碼性能變差。

首先對算法中的專業(yè)名詞及符號進行說明，分別定義當前層根節(jié)點及與其相鄰的子節(jié)點為ws和Z(ws)，節(jié)點vi和cj分別表示AR4JA編碼矩陣中的變量節(jié)點和校驗節(jié)點。函數(shù)p(μt)表示根節(jié)點與任意變量或校驗節(jié)點之間所有節(jié)點ACE值總和。設(shè)編碼的門限參數(shù)為(dACE，hACE)，即所有環(huán)長不大于2dACE的環(huán)的EMD值至少為hACE。在LDPC編碼對應(yīng)的子循環(huán)陣中，設(shè)橫向及縱向最大非零矩陣塊數(shù)分別為n，m。改進的QC-ACE算法步驟如下：

① 初始化。根據(jù)置換子矩陣的分布，按照從右至左、自上而下的方向搜索非零循環(huán)子陣，并在對應(yīng)位置隨機產(chǎn)生變量節(jié)點vi，即隨機產(chǎn)生所在行“1”的循環(huán)右移位數(shù)；預(yù)設(shè)所有節(jié)點為活躍節(jié)點。

② ACE檢測。在進行ACE檢測之前，分別對單環(huán)和復(fù)合環(huán)對應(yīng)的ACE表達式進行定義。其中變量節(jié)點vi對應(yīng)的ACE為：

ACE(vi)=di-2，

(6)

式中，di為環(huán)中變量節(jié)點vi的度。則變量節(jié)點vi所在的單環(huán)ACE的表達式為：

(7)

但該表達式不適合公共邊的復(fù)合環(huán)，因此針對而復(fù)合環(huán)需要重新定義ACE計算式。用C(vi)表示復(fù)合環(huán)中變量節(jié)點相連的校驗節(jié)點集合，其中元素數(shù)量記為n(C(vi))，設(shè)a表示復(fù)合環(huán)中的公共節(jié)點取值范圍，則復(fù)合環(huán)ACE計算表達式為：

(8)

設(shè)定變量節(jié)點vi為根節(jié)點ws，尋找ws鄰接子集Z(ws)中的校驗節(jié)點cj，則該節(jié)點當前的ACE路徑為：

ptemp=p(ws)+ACE(cj)。

(9)

該節(jié)點的環(huán)長可通過節(jié)點先前最小ACE路徑及當前到該節(jié)點ACE減去根節(jié)點及子節(jié)點的2倍計算，則當前構(gòu)造環(huán)長為：

ACEtemp=ptemp+p(μt)-ACE(vi)-ACE(cj)。

(10)

③ 若滿足約束條件環(huán)長L≤2dACE時繼續(xù)進行ACEtemp≥ηACE；反之，說明本次搜索失敗，需要重設(shè)初始化參數(shù)，再次進行搜索。

④ 重復(fù)步驟②，對基矩陣中非零元素進行遍歷，當所有非零元素都滿足ACE約束時，循環(huán)矩陣的構(gòu)造完成，原模圖的第二步擴展結(jié)束。反之，則返回步驟①。

在搜索過程中，由于初始化參數(shù)設(shè)置帶有隨機性，需要搜索多組碼字進行驗證，以最終確定循環(huán)偏移參數(shù)。

3 仿真實驗與性能分析

為驗證基于PEG-ACE優(yōu)化的AR4JA構(gòu)造算法性能，將本文提出的優(yōu)化算法構(gòu)造得到的AR4JA編碼分別與隨機構(gòu)造算法以及現(xiàn)有AR4JA編碼性能進行對比。假設(shè)信道為AWGN信道且噪聲功率密度為N0，調(diào)制方式采用BPSK。譯碼采用標準BP譯碼，對于每幀LDPC譯碼中最大迭代次數(shù)設(shè)置為80次，在每個信噪比條件下將實驗運行到指定的誤幀數(shù)或者實驗次數(shù)達到107量級。

3.1 與隨機構(gòu)造編碼比較

首先用PEG-ACE優(yōu)化算法構(gòu)造1/2碼率的(2 048，1 024)AR4JA編碼，再用PEG經(jīng)典構(gòu)造法構(gòu)造的相近碼長的(2 016，1 008)全隨機LDPC編碼作為對照[23]，對比結(jié)果如圖5所示。

圖5 隨機構(gòu)造編碼與本文構(gòu)造編碼性能對比

可看出全隨機LDPC編碼隨著信噪比的增加存在著一定的誤碼平層現(xiàn)象，而本文中采用兩步擴展優(yōu)化搜索算法構(gòu)造的編碼，最短圍長和環(huán)連通特性得到改善，有效克服準循環(huán)LDPC編碼中存在的誤碼平底現(xiàn)象，編碼的綜合性能得到改善。

3.2 與現(xiàn)有AR4JA編碼比較

首先用PEG-ACE優(yōu)化算法構(gòu)造4/5碼率的(1 280，1 024)AR4JA編碼，再用現(xiàn)有PEG-ACE算法構(gòu)造法AR4JA編碼作為對照[19]，對比結(jié)果如圖6所示。

圖6 現(xiàn)有AR4JA編碼與優(yōu)化構(gòu)造編碼性能對比

圖6的仿真結(jié)果表明，在類似仿真參數(shù)及誤比特率條件下，優(yōu)化構(gòu)造的AR4JA編碼略優(yōu)于現(xiàn)有的AR4JA編碼。現(xiàn)有AR4JA編碼采用PEG算法時未考慮備選節(jié)點，且對應(yīng)的Tanner圖中存在部分嵌套環(huán)，易引起環(huán)間信息傳遞自反饋導(dǎo)致的誤碼。經(jīng)過PEG-ACE優(yōu)化算法可改善環(huán)間獨立節(jié)點信息，從而改進譯碼性能。同時在復(fù)雜度相似的前提下，采用兩步擴展優(yōu)化算法可獲得微小性能的改進，具有較好的工程實踐意義。

4 結(jié)束語

本文提出了擴展原模圖的AR4JA編碼優(yōu)化構(gòu)造算法，根據(jù)AR4JA編碼原模圖模板，對校驗節(jié)點及其關(guān)聯(lián)的變量節(jié)點進行擴展，增加矩陣維度。在擴展過程中，以環(huán)長和環(huán)路ACE測度最大化為目標，提出了PEG-ACE優(yōu)化算法，在譯碼門限和誤碼平層方面都具有良好表現(xiàn)，適合空間衛(wèi)星通信應(yīng)用。同時，所構(gòu)造的LDPC編碼具有準循環(huán)結(jié)構(gòu)，易于工程實現(xiàn)。