2.2.5 LDPC碼構(gòu)造

如前文所述，LDPC碼的性能由其Tanner圖結(jié)構(gòu)決定。理論上，只要碼長充分長（例如N=107），隨機構(gòu)造的LDPC碼都是好碼。但考慮到實用化，一般編碼的碼長小于104，此時需要考慮Tanner圖與編碼結(jié)構(gòu)對性能的影響。

通常，較小的環(huán)長會導(dǎo)致變量節(jié)點、校驗節(jié)點交互的消息很快出現(xiàn)相關(guān)性，從而限制糾錯性能。一般而言，LDPC碼的構(gòu)造要求消除長度為2與4的環(huán)，也就是說，Tanner圖的圍長至少為6。但從另一方面來看，Tanner圖上的環(huán)長、圍長的值也并非越大越好。理論上，只有無環(huán)圖才是嚴(yán)格的 MAP 譯碼，如果圖上存在環(huán)，則和積算法是APP譯碼算法，只是MAP譯碼的近似。由于受到最小漢明距離的限制，嚴(yán)格無環(huán)圖的性能很差。因此，增大環(huán)長或圍長并非LDPC碼設(shè)計的唯一優(yōu)化目標(biāo)，需要綜合考慮Tanner圖結(jié)構(gòu)與編碼結(jié)構(gòu)參數(shù)進(jìn)行優(yōu)選。

LDPC碼主流的構(gòu)造與編碼方法如圖2-10所示。LDPC碼的編碼方法根據(jù)結(jié)構(gòu)特點可分為5類，分別簡述如下。

1．偽隨機構(gòu)造

從實際應(yīng)用來看，這一類LDPC碼構(gòu)造大多是考慮去除某些限制條件的偽隨機編碼，例如去掉長度為4的環(huán)。在Gallager[4]的原始研究中，(3,6)規(guī)則LDPC碼的構(gòu)造就是一種偽隨機構(gòu)造。他將校驗矩陣的行等分為多段，通過在不同段中隨機排列1的位置實現(xiàn)偽隨機構(gòu)造。MacKay與Neal[6]構(gòu)造的基本思路是按列重隨機選擇列進(jìn)行疊加，觀察行重是否滿足度分布要求，通過反復(fù)迭代操作最終實現(xiàn)構(gòu)造，這種構(gòu)造能夠消除長度為4的環(huán)。

比特填充構(gòu)造[12]是指在Tanner圖每次添加變量節(jié)點時，要檢查新增連邊是否構(gòu)成特定長度（例如4）的環(huán)，通過避免短環(huán)出現(xiàn)，得到增大圍長的Tanner圖結(jié)構(gòu)。

漸近邊增長（progressive edge growth,PEG）算法[13]是比特填充構(gòu)造的對偶方法。其基本思想是每次在Tanner圖上添加新邊時，都選擇最大化本地圍長的變量節(jié)點，這樣能夠保證圍長充分大。

上述方法都是從不同角度隨機構(gòu)造Tanner圖或相應(yīng)的校驗矩陣H。但是LDPC碼的編碼需要使用生成矩陣G。我們可以采用高斯消元法得到生成矩陣G，但由于這種結(jié)構(gòu)的生成矩陣往往不稀疏，因此LDPC碼的編碼復(fù)雜度是O(N 2)。為了降低編碼復(fù)雜度，Richardson與Urbanke[14]證明了如果校驗矩陣為近似下三角矩陣形式，則編碼復(fù)雜度為O(N+g2)，其中，g是校驗矩陣與下三角矩陣之間的歸一化距離，對于很多編碼g?1。

2．結(jié)構(gòu)化編碼

偽隨機構(gòu)造編碼能達(dá)到較好的糾錯性能，但一般編譯碼復(fù)雜度較高。與之相反，結(jié)構(gòu)化編碼也稱確定性編碼，編譯碼復(fù)雜度更具有優(yōu)勢。結(jié)構(gòu)化編碼的一類主要思路是采用幾何設(shè)計或組合設(shè)計。其中，幾何設(shè)計的代表性方法是文獻(xiàn)[15]提出的有限幾何構(gòu)造；組合設(shè)計有很多方法，包括平衡不完全區(qū)組方法[16]、Kirkman 系統(tǒng)設(shè)計[17]以及正交拉丁方設(shè)計[18]等。這些方法都需要用到幾何或組合理論，具有良好的數(shù)學(xué)分析基礎(chǔ)。

結(jié)構(gòu)化編碼的另一類思路是采用線性結(jié)構(gòu)設(shè)計，代表性方法包括 Lu 等[19]提出的 Turbo 結(jié)構(gòu)設(shè)計與 Fossorier[20]提出的準(zhǔn)循環(huán)（QC）-LDPC 碼。由于利用了線性編碼特征，這兩種方法的編碼比較簡單規(guī)整。

3．嵌套構(gòu)造

偽隨機構(gòu)造是在整個Tanner圖上進(jìn)行設(shè)計，另一種設(shè)計思路是將Tanner圖上的邊分類，首先優(yōu)化子圖，然后擴展到全圖。由于全圖與子圖具有嵌套結(jié)構(gòu)，因此被稱為嵌套構(gòu)造。

這種構(gòu)造的代表是Richardson等[21]提出的多邊類型LDPC碼，其中一個重要的子類就是原模圖（protograph）LDPC 碼。Thorpe[22]提出了原模圖的概念。Divsalar等[23]設(shè)計的AR3A與AR4JA碼是兩種代表性的原模圖碼，它們具有線性編碼復(fù)雜度與快速譯碼算法，能夠逼近信道容量極限，被應(yīng)用在美國深空探測標(biāo)準(zhǔn)中。5G NR移動通信標(biāo)準(zhǔn)中也采用了基于原模圖的LDPC碼編碼方案。

圖2-11給出了原模圖構(gòu)造示例。圖2-11（a）所示為一個原模圖，與普通的Tanner圖不同，原模圖中允許存在重邊。該原模圖有4個變量節(jié)點、3個校驗節(jié)點和9條邊，由于有重邊，因此圖2-11（a）所示的原模圖對應(yīng)8種不同類型的邊。其對應(yīng)的基礎(chǔ)矩陣如下。

圖2-11（b）給出了兩次拷貝示意，經(jīng)過同類型邊之間的重排，可以得到圖2-11（c）所示的導(dǎo)出圖。

一般地，假設(shè)原模圖有MP個校驗節(jié)點、NP個變量節(jié)點，經(jīng)過z次拷貝與邊重排操作得到的全圖稱為導(dǎo)出圖，其規(guī)模為M × N=zM P× zNP。這種“拷貝重排”操作稱為自舉，操作次數(shù)z稱為自舉因子。原模圖的性能不能直接應(yīng)用外部信息傳遞（extrinsic information transfer,EXIT）圖分析，需要采用修正的原模圖外部信息傳遞（protograph extrinsic information transfer,PEXIT）圖分析[24]。導(dǎo)出圖中的邊連接優(yōu)化可以用PEG算法得到。

4．多進(jìn)制編碼

上述討論的LDPC碼都是二進(jìn)制編碼。Davey與MacKay[25]提出了基于有限域的多進(jìn)制LDPC碼，稱為Q-LDPC碼。由于引入了有限域的額外編碼約束，相對于二進(jìn)制編碼而言，Q-LDPC 碼能夠獲得更好的糾錯能力。但這種編碼的最大問題是譯碼復(fù)雜度較高，限制了其工程應(yīng)用。

另外一類多進(jìn)制編碼是廣義構(gòu)造，稱為 G-LDPC 碼，由 Lentmaier 與Zigangirov[26]提出。G-LDPC碼將傳統(tǒng)LDPC碼中簡單校驗的校驗節(jié)點替換為經(jīng)典的線性分組碼校驗，例如，采用Hamming碼、BCH碼或RS碼作為校驗節(jié)點。進(jìn)一步，Liva等[27]考慮了不規(guī)則G-LDPC碼，由于Tanner圖上存在強糾錯節(jié)點，其被稱為摻雜LDPC碼。

5．?dāng)U展構(gòu)造

近年來，人們擴展LDPC碼設(shè)計思想，針對具體應(yīng)用構(gòu)造新型編碼。其中，代表性的編碼是低密度生成矩陣（low density generative matrix,LDGM）碼、無速率（rateless）碼與空間耦合LDPC（spatial coupling-LDPC,SC-LDPC）碼，下面分別介紹其基本思想與性質(zhì)。

（1）LDGM碼

Cheng與McEliece[28]提出了LDGM碼的設(shè)計思想。一般而言，LDPC碼的校驗矩陣是低密度的，生成矩陣是高密度的，而LDGM碼的設(shè)計利用了對偶性，它是一種系統(tǒng)碼，生成矩陣是稀疏的，校驗矩陣是稠密的。因此，LDGM碼主要應(yīng)用于高碼率場景，它具有線性的編譯碼復(fù)雜度。

早期研究表明，由于最小漢明距離較小，LDGM碼是漸近壞碼，有顯著的錯誤平臺現(xiàn)象。但如果將兩個LDGM碼進(jìn)行串行級聯(lián)，或者將LDGM碼與其他LDPC碼級聯(lián)，則可以顯著降低錯誤平臺。

由于LDGM碼編碼簡單，可以應(yīng)用于信源壓縮與編碼，也可以與星座調(diào)制聯(lián)合設(shè)計，或者應(yīng)用于多輸入多輸出（multiple-input multiple-output,MIMO）傳輸，逼近高頻譜效率下的信道容量極限。

（2）無速率碼

無速率碼最早來源于糾刪應(yīng)用。在固定/無線互聯(lián)網(wǎng)中，由于某種原因（擁塞或差錯），介質(zhì)訪問控制（medium access control,MAC）層會產(chǎn)生丟包，但丟包數(shù)量并不固定。固定編碼碼率進(jìn)行糾刪時，如果碼率高于刪余率，則糾刪能力較差；如果碼率低于刪余率，則冗余較大。總之，由于實際系統(tǒng)中刪余率無法先驗確知或者存在動態(tài)變化，因此固定的碼率無法匹配。

Luby[29]提出的Luby變換（Luby transform,LT）碼是一種是實用化的無速率碼。它是一種數(shù)據(jù)包編碼，主要用于 MAC 層或應(yīng)用層數(shù)據(jù)傳輸。也有人稱其為噴泉（fountain）碼，即將每個編碼數(shù)據(jù)包比喻為一滴水，根據(jù)傳輸條件動態(tài)變化，接收機收到不同的水量（數(shù)據(jù)包），就可以開始糾刪譯碼，因此其碼率不固定。

理論上可以證明，當(dāng)碼長趨于無限長時，LT碼能夠達(dá)到BEC的信道容量，它是一種容量可達(dá)的構(gòu)造性編碼。但已有研究表明，碼長有限時，LT 碼具有顯著的錯誤平臺現(xiàn)象。為了降低錯誤平臺，Shokrollahi[30]提出了Raptor碼，這種編碼使用一個高碼率的LDPC碼作為外碼，級聯(lián)LT碼，獲得了顯著的性能提升。Raptor碼已經(jīng)應(yīng)用于3G的應(yīng)用層編碼標(biāo)準(zhǔn)中。

（3）空間耦合LDPC碼

空間耦合LDPC碼借鑒卷積編碼結(jié)構(gòu)。Jimenez與Zigangirov[31]最早提出了卷積LDPC 碼。它的基本思想是將基本校驗矩陣作為移位寄存器的抽頭系數(shù)，設(shè)計卷積型的編碼結(jié)構(gòu)，從而獲得周期性時變的編碼序列。

Kudekar 等[32]認(rèn)識到卷積在各個碼段之間引入了編碼約束關(guān)系，產(chǎn)生了“空間耦合”效應(yīng)。他們證明，即使采用規(guī)則的(3,6)碼約束，只要引入適當(dāng)?shù)目臻g耦合關(guān)系，當(dāng)編碼長度趨于無窮時，密度進(jìn)化的譯碼門限將趨于BEC的信道容量的門限值。這意味著，空間耦合LDPC碼也是一種能夠達(dá)到BEC的信道容量的構(gòu)造性編碼。研究者發(fā)現(xiàn)，空間耦合LDPC碼對于一般的B-DMC都是漸近容量可達(dá)的，這是一個LDPC 編碼理論的重大突破，經(jīng)過多年的研究，人們終于發(fā)現(xiàn)了可以達(dá)到信道容量極限的LDPC碼。空間耦合LDPC碼掀起了LDPC碼新的研究熱潮，尤其是有限碼長下的高性能編譯碼算法是學(xué)術(shù)界關(guān)注的重點。