利用雙重?cái)U(kuò)展RS碼及循環(huán)MDS碼構(gòu)造實(shí)用化的LDPC碼.doc

第6期張國華等：利用雙重?cái)U(kuò)展RS碼及循環(huán)MDS碼構(gòu)造實(shí)用化的LDPC碼105利用雙重?cái)U(kuò)展RS碼及循環(huán)MDS碼構(gòu)造實(shí)用化的LDPC碼張國華，王新梅（西安電子科技大學(xué) ISN國家重點(diǎn)實(shí)驗(yàn)室， 陜西 西安 710071）摘 要：提出了利用雙重?cái)U(kuò)展RS碼和循環(huán)MDS碼來構(gòu)造無4-環(huán)準(zhǔn)循環(huán)LDPC碼的兩類實(shí)用方法。第一類構(gòu)造法利用雙重?cái)U(kuò)展RS碼中的所有非零碼字來構(gòu)造校驗(yàn)矩陣，因此在LDPC碼的參數(shù)選擇上比基于單擴(kuò)展RS碼的構(gòu)造法更加靈活；推導(dǎo)出與雙重?cái)U(kuò)展RS碼構(gòu)造法完全等效的直接構(gòu)造法，利用RS碼的生成多項(xiàng)式可以直接生成LDPC碼的校驗(yàn)矩陣，從而避免了RS碼字雙重?cái)U(kuò)展、碼字分類等預(yù)處理步驟。第二類構(gòu)造法直接根據(jù)循環(huán)MDS碼的生成多項(xiàng)式構(gòu)造了一類無4-環(huán)的準(zhǔn)循環(huán)LDPC碼。仿真結(jié)果表明，基于雙重?cái)U(kuò)展RS碼和循環(huán)MDS碼的準(zhǔn)循環(huán)LDPC碼在AWGN信道下均可取得很好的誤比特性能。關(guān)鍵詞：LDPC碼；迭代譯碼；RS碼；MDS碼中圖分類號：TN911.22 文獻(xiàn)標(biāo)識碼：B 文章編號：1000-436X(2008)06-0100-06Applied quasi-cyclic LDPC codes from doubly-extended RS code and cyclic MDS codeZHANG Guo-hua, WANG Xin-mei（State Kay Lab. of Integrated Service Networks,Xidian Univ.,Xian 710071,China）Abstract: Based on doubly-extended RS codes and cyclic MDS codes, two construction schemes were proposed for applied quasi-cyclic LDPC codes whose Tanner graph is free of 4-cycles. In the first approach, all the nonzero codewords within a doubly-extended RS code were employed, and hence provided more flexible parameters than the original or singly-extended RS codes. Equivalent to the method from doubly-extended RS code, a straightforward procedure was derived, by which given generator polynomial of an RS code,LDPC codes could be constructed directly without pretreatment such as double extension and classification of codewords. In the second method, generator polynomials of cyclic MDS codes were utilized in a straightforward manner to build quasi-cyclic LDPC codes with its Tanner graph free of 4-cycles. Experimental results showed that the constructed codes from the two methods perform well over AWGN channels.Key words: LDPC code; iterative decoding; RS code; MDS code1 引言收稿日期：2007-01-15；修回日期：2008-02-20基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（U0635003，60572149）Foundation Item: The National Natural Science Foundation of China (U0635003, 60572149)低密度奇偶校驗(yàn)（LDPC）碼是一類線性分組碼，其特殊性在于LDPC碼的校驗(yàn)矩陣是稀疏矩陣，即矩陣中非零元素的數(shù)目遠(yuǎn)小于“0”的數(shù)目。在SPA等迭代譯碼算法下，LDPC碼可以獲得逼近Shannon極限的優(yōu)異性能；目前,LDPC碼的構(gòu)造、譯碼、分析和應(yīng)用等問題已經(jīng)成為編碼領(lǐng)域的研究熱點(diǎn)。在構(gòu)造方面，除了帶約束的偽隨機(jī)方法外，主要是數(shù)學(xué)氣息相當(dāng)濃厚的結(jié)構(gòu)化構(gòu)造方法，例如有限幾何13、平衡不完全區(qū)組設(shè)計(jì)46等。目前，多項(xiàng)通信標(biāo)準(zhǔn)已將LDPC碼作為下一代通信系統(tǒng)的信道編碼方式，LDPC碼正在逐步進(jìn)入實(shí)用化階段。而實(shí)用化的一個巨大障礙就是LDPC碼構(gòu)造方法的不確定性和復(fù)雜性。因此，如何構(gòu)造出既簡單實(shí)用，又性能優(yōu)異的LDPC碼是目前的一大研究熱點(diǎn)。利用雙重?cái)U(kuò)展RS碼和循環(huán)MDS碼，本文提出了2種簡單實(shí)用的LDPC碼構(gòu)造方法。使用RS碼來構(gòu)造LDPC的思想源于I.Djurdjevic7，這種方法得到的LDPC碼缺乏準(zhǔn)循環(huán)結(jié)構(gòu)，因而不便于編碼器的硬件設(shè)計(jì)；隨后，L.Chen僅利用RS碼中的最小重量碼字，以非/單擴(kuò)展RS碼為基礎(chǔ)構(gòu)造出兩類具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼8,9：non-extended RS-LDPC codes（N碼）和singly extended RS-LDPC codes（S碼）。本文從2種角度發(fā)展了這種構(gòu)造方法。一方面，本文將這種方法推廣到雙重?cái)U(kuò)展RS碼的情形，得到了一類更一般化的LDPC碼（D碼，doubly extended RS-LDPC code），N碼和S碼都是D碼的特殊情形，而D碼在參數(shù)選擇上更加靈活。另一方面，本文推導(dǎo)出與雙重?cái)U(kuò)展RS碼構(gòu)造法完全等效的直接構(gòu)造法，根據(jù)RS碼的生成多項(xiàng)式可以直接得到LDPC碼的校驗(yàn)矩陣，從而避免了RS碼字的擴(kuò)展與分類等預(yù)處理步驟，使這種構(gòu)造方法更加實(shí)用化。此外，利用循環(huán)MDS碼的生成多項(xiàng)式得到了另一種校驗(yàn)矩陣，不僅具有簡單實(shí)用的優(yōu)點(diǎn)而且具有緊湊的描述方式。2 雙重?cái)U(kuò)展RS碼設(shè)是GF(q)中的本原元，則 構(gòu)成GF(q)中的所有元素。(q1,k,d=qk) RS碼的生成多項(xiàng)式為其中，。與系統(tǒng)碼相對應(yīng)的H矩陣為根據(jù)矩陣H，可以得到雙重?cái)U(kuò)展RS碼的校驗(yàn)矩陣10因此，RS碼的任意碼字，添加一個全校驗(yàn)位將得到單擴(kuò)展碼字，再添加一個校驗(yàn)位，就得到了雙重?cái)U(kuò)展碼字。改變記號，則。因?yàn)殡p重?cái)U(kuò)展RS碼是MDS碼，所以由MDS碼的重量分布10可知(q+1,k=2,qk+2=q)雙重?cái)U(kuò)展RS碼中包含1個全零碼字和個重量為q的碼字。設(shè)是一個非零碼字，它在第個位置為0。集合中的所有碼字均在位置處為零；而且除此以外，不存在其他非零碼字在位置處為零。事實(shí)上，如果存在一個之外的碼字在位置處為零，則必與中某個碼字在兩個位置取相同元素，而這與最小碼距為相矛盾。因此，個重量為q的碼字可以劃分為q+1個不相交的集合。3 D碼及其等效構(gòu)造法3.1 D碼的構(gòu)造方法本節(jié)符號沿用文獻(xiàn)8中的記法。設(shè)是有限域GF(q)中的本原元。定義1 GF(q)中每個非零元素對應(yīng)于一個GF(2)上的q1重：，其中，其他為0；GF(q)中0元素對應(yīng)于分量全部為零的q1重。GF(q)中每個元素對應(yīng)的q1重稱為該元素的位置矢量。定義2 對于，將中碼字的所有符號用位置矢量表示，可以得到一個重。所對應(yīng)的重稱為的符號位置向量。對于，中全部碼字所對應(yīng)的符號位置向量按行的順序排成一個的矩陣；則可以看作是由q+1個的循環(huán)置換矩陣拼接而成的行，其中包括一個全零矩陣。將所有（）排成一列，可以得到一個的矩陣H；則H可以看作一個的陣列，陣列的每個元素都是一個的循環(huán)矩陣（或全零矩陣）。對于任意正整數(shù)（且），設(shè)是H的一個的子陣列。由于由循環(huán)矩陣構(gòu)成，因此與之對應(yīng)的LDPC碼為準(zhǔn)循環(huán)碼。對于GF(q)上的RS碼，任意2個非零碼字至多在一個位置取相同符號。因此，對應(yīng)的Tanner圖上不含4-環(huán)，即girth至少為6。由上述構(gòu)造方法容易知道，的零空間給出的LDPC碼具有如下參數(shù)：碼長；校驗(yàn)矩陣對應(yīng)Tanner圖的girth至少為6；校驗(yàn)矩陣的列重為或；校驗(yàn)矩陣的行重為或；稀疏性（即“1”占的比例）。除了girth，影響LDPC碼性能的另一個參數(shù)是碼字的最小距離：最小距離較小LDPC碼通常會在高信噪比區(qū)產(chǎn)生錯誤平層。使用與文獻(xiàn)9相同的討論，可以得到最小距離的下界：若不含全零矩陣則最小碼距至少為，若包含全零矩陣則最小碼距至少為。其中表示不大于的最大整數(shù)。N碼和S碼是D碼的2個特例。如果刪除D碼的最后一個符號，將得到S碼；如果進(jìn)一步刪除S碼的最后一個符號，將得到N碼。D碼利用了雙重?cái)U(kuò)展RS碼的所有非零碼字，因而在參數(shù)選擇上比另外2種碼更加靈活。這3種碼的參數(shù)如表1、2所示，其中列重，。表13種規(guī)則LDPC碼的參數(shù)比較碼類列重，行重設(shè)計(jì)碼率NSD表23種準(zhǔn)規(guī)則LDPC碼的參數(shù)比較碼類列重，行重設(shè)計(jì)碼率NSD原則上，雙信息符號的MDS碼都能構(gòu)造出Tanner圖不含4-環(huán)的LDPC碼；除了RS碼、縮短RS碼、單/雙重?cái)U(kuò)展RS碼，非RS碼的MDS碼也是存在的。但是，對于GF(q)上的雙信息符號MDS碼，碼長至多取q+1 10。對于雙信息符號的雙重?cái)U(kuò)展RS碼，其碼長為q+1，因而對碼長繼續(xù)擴(kuò)展是不可能的。因此，在所有基于MDS構(gòu)造無4-環(huán)LDPC碼的方法中，本文方法為參數(shù)選擇提供了最大可能的靈活性（見表1、表2所示）。3.2 D碼的等效構(gòu)造方法由第3.1節(jié)可知，通過對RS碼進(jìn)行雙重?cái)U(kuò)展、碼字分類等操作可以構(gòu)造出LDPC碼的校驗(yàn)矩陣。本節(jié)將推導(dǎo)一種D碼的等效構(gòu)造方法。使用該方法，不必列出雙重?cái)U(kuò)展RS碼的碼字就能直接構(gòu)造出D碼。首先證明3個性質(zhì)。性質(zhì)1 ， ，和 都是雙重?cái)U(kuò)展RS碼的碼字。證明 根據(jù)RS碼的校驗(yàn)矩陣H可知是(q1,2,q2) RS碼的一個碼字；根據(jù)全校驗(yàn)關(guān)系可知，是單重?cái)U(kuò)展(q,2,q1) RS碼中的一個碼字；根據(jù)，可知 是雙重?cái)U(kuò)展(q+1,2,q) RS碼中的一個碼字。同理可證是雙重?cái)U(kuò)展(q+1,2,q) RS碼中的一個碼字。對應(yīng)于(q1,2,q2) RS碼中一個重量為q2的碼字,，所以是雙重?cái)U(kuò)展(q+1,2,q) RS碼中的一個碼字。性質(zhì)2 設(shè)是循環(huán)右移m位算子。若對應(yīng)的雙重?cái)U(kuò)展碼是，則 對應(yīng)的雙重?cái)U(kuò)展碼是。證明 顯然保持不變。令，根據(jù)有根據(jù)性質(zhì)1和2可以得到共計(jì)1+1+(q1)=q+1個雙重?cái)U(kuò)展RS碼字，它們的零分量出現(xiàn)位置各不相同。用GF(q)中的(q1)個非零元素與每個碼字相乘，可得(q1)(q+1)個非零碼字，它們就是雙重?cái)U(kuò)展(q+1,2,q) RS碼的所有非零碼字。由于碼字和固定不變，因此為了構(gòu)造D碼，我們只需求出，然后計(jì)算出和；事實(shí)上，根據(jù)以下性質(zhì)只需求出，和可由直接得到。性質(zhì)3 。如果q為奇數(shù)，；如果q為偶數(shù)，。根據(jù)以上討論，D碼可根據(jù)以下步驟等價(jià)地構(gòu)造出來。1) 根據(jù)和構(gòu)造母矩陣M2) 對于非零元素，定義為一個 的置換矩陣：如果，；否則。對于零元素，定義一個的全零矩陣。3) 從矩陣M中選擇一個的子陣列，稱此子陣列為矩陣；將矩陣中的所有元素用相應(yīng)的置換矩陣（或全零矩陣）替代，將得到一個的矩陣，稱此矩陣為。4) 將作為校驗(yàn)矩陣，則其零空間對應(yīng)于一個準(zhǔn)循環(huán)LDPC碼。D碼的母矩陣M包含了S碼和N碼的母矩陣。母矩陣M的前q1行、前q1列對應(yīng)于N碼的校驗(yàn)矩陣；母矩陣M的前q行、前q列對應(yīng)于S碼的校驗(yàn)矩陣。根據(jù)母矩陣M的性質(zhì)，不必計(jì)算即可直接得到。性質(zhì)4 在母矩陣M中，除末行以外任意行的前q個元素兩兩不同，即這q個符號恰是GF(q)上的所有元素。 證明：第q行的前q個元素顯然兩兩不同。假設(shè)第行（）的前q個符號中存在2個相同的元素，該行與矩陣M末行對應(yīng)的2個雙重?cái)U(kuò)展RS碼字，可以線性組合出一個至少包括兩個零元素的非全零碼字。矛盾。4 利用循環(huán)MDS碼構(gòu)造LDPC碼為便于使用理論方法對最小距離、girth等重要參數(shù)作深入分析，校驗(yàn)矩陣一般希望具有較強(qiáng)的結(jié)構(gòu)特征。母矩陣M在形式上比較對稱，但其最后兩行和最后兩列影響了母矩陣M整體上的循環(huán)性質(zhì)。雖然雙重?cái)U(kuò)展RS碼的碼字之間一般不存在循環(huán)關(guān)系，但是存在與雙重?cái)U(kuò)展RS碼參數(shù)相同的循環(huán)MDS碼10。利用循環(huán)MDS碼，可以得到具有循環(huán)性質(zhì)的母矩陣。設(shè)，是上的本原元。令，則。根據(jù)的取值，可以分為兩種情況。（1）若，令 ，則是(q+1,2,q)循環(huán)MDS碼的生成多項(xiàng)式10。（2）若，令，可以驗(yàn)證是的連續(xù)q1個零點(diǎn)。因?yàn)椋陨梢粋€(q+1,2)循環(huán)碼；根據(jù)BCH限，該循環(huán)碼的最小距離為q，因此生成一個(q+1,2,q)循環(huán)MDS碼。令。則對應(yīng)的母矩陣可表示為由母矩陣構(gòu)造LDPC碼的方法同3.2節(jié)完全相同，這里不再重復(fù)。與直接利用組合數(shù)學(xué)（例如有限幾何、平衡不完全區(qū)組設(shè)計(jì)等）的方法相比，以上2種方法（等效構(gòu)造法和循環(huán)MDS碼構(gòu)造法）利用了通信領(lǐng)域的已有標(biāo)準(zhǔn)技術(shù)，可以方便直觀地作出LDPC碼的校驗(yàn)矩陣；惟一需要計(jì)算的是碼的生成多項(xiàng)式，而這是基本和簡單的。除本文方法外，還存在其他能夠簡潔構(gòu)造出校驗(yàn)矩陣的方法。例如，利用有限域和仿射變換（FFAM），文獻(xiàn)11,12提出了2種構(gòu)造LDPC碼的簡潔方法。它們與本文構(gòu)造法有以下異同之處。一方面，F(xiàn)FAM方法與本文方法都是基于MDS的構(gòu)造方法；根據(jù)文獻(xiàn)13中的定理2.3.3，利用FFAM的構(gòu)造方法在本質(zhì)上是基于線性MDS碼的構(gòu)造方法。另一方面，F(xiàn)FAM方法與本文方法得到的校驗(yàn)矩陣，在描述形式上存在較大差異。在FFAM方法中，有限域上一組相異的元素被施加仿射變換后得到母矩陣，母矩陣中每個元素被相應(yīng)的位置矢量替換后即得校驗(yàn)矩陣。這種方法得到的母矩陣采用元素之差的形式來描述，在實(shí)施位置矢量替換之前必須完成元素之差表示到指數(shù)表示的轉(zhuǎn)換，這對實(shí)用來說是不方便的。本文得到的母矩陣直接采用指數(shù)形式描述，不僅結(jié)構(gòu)緊湊而且便于實(shí)用。5 例子與仿真仿真條件：迭代譯碼算法采用BP算法14，最大迭代次數(shù)設(shè)定為100，信道模型為AWGN，采用BPSK調(diào)制。在下面2個例子中，誤碼率數(shù)據(jù)均仿真到了量級；量級以下的仿真超出了目前計(jì)算機(jī)的運(yùn)算速度。為了保證仿真數(shù)據(jù)的準(zhǔn)確性，仿真數(shù)據(jù)量至少比誤碼率高出2個量級。LDPC碼的誤比特性能可以與相應(yīng)參數(shù)的偽隨機(jī)LDPC碼比較，也可以直接與Shannon限相比較。為了保證比較的客觀性和可重復(fù)性，本文采用第二種方式。例1 使用有限域上的(129,2,128)雙重?cái)U(kuò)展RS碼構(gòu)造QC-LDPC碼。設(shè)是的本原元，滿足。(127,2,126) RS碼的生成多項(xiàng)式為；用本原元的冪次表示，對應(yīng)的碼字為 。根據(jù)等效構(gòu)造法，作出一個的母矩陣M。取。將矩陣的前8行和后32列作為子陣列，對應(yīng)的行重為32，列重為8。零空間可以給出一個碼率為0.783，最小距離至少為10的規(guī)則(4064,3181) QC-LDPC碼。在誤碼率為時(shí)，(4 064,3 181) QC-LDPC的性能距離Shannon限約1.7dB。取。將矩陣M的前4行和后8列作為子陣列，對應(yīng)的行重為8，列重為4。零空間可以給出一個碼率為0.517，最小距離的規(guī)則(1016,525) QC-LDPC碼。在誤碼率為時(shí)，(1016,525) QC-LDPC的性能距離Shannon限約2.4 dB，對于結(jié)構(gòu)化的短碼而言，這是比較好的性能。圖1 (129,2,128)雙重?cái)U(kuò)展RS碼構(gòu)造的2個QC-LDPC碼例2 使用有限域上的長度為33的循環(huán)MDS碼構(gòu)造QC-LDPC碼。設(shè)是上的本原元，滿足。令，則是的本原元。設(shè)，則(33,2,32) MDS碼的生成多項(xiàng)式為；用本原元的冪次表示，則對應(yīng)的碼字為。作出一個的母矩陣。設(shè)。將矩陣的前16行和前32列作為子陣列，對應(yīng)的行重為31，列重為15和16。零空間可以給出一個碼率為0.772、最小距離至少為16的準(zhǔn)規(guī)則(992,766) QC-LDPC碼。在誤碼率為時(shí)，準(zhǔn)規(guī)則(992,766) QC-LDPC的性能距離Shannon限約2.0dB。設(shè)。將矩陣的前6行和全部列作為子陣列，對應(yīng)的行重為32，列重為5和6。零空間可以給出一個碼率為0.857、最小距離至少為6的準(zhǔn)規(guī)則(1 023,877) QC-LDPC碼。在誤碼率為時(shí)，準(zhǔn)規(guī)則(1 023,877) QC-LDPC碼的性能距離Shannon極限約1.5dB。圖2 長度為33的循環(huán)MDS碼構(gòu)造的2個QC-LDPC碼6 結(jié)束語首先利用雙重?cái)U(kuò)展RS碼構(gòu)造出一類無4-環(huán)的準(zhǔn)循環(huán)LDPC碼。使用非擴(kuò)展RS碼和單擴(kuò)展的RS碼得到的LDPC碼是新方法的兩個特例。由于雙重?cái)U(kuò)展RS碼中所有非零碼字均被利用，因此構(gòu)造出的LDPC具有更加靈活的參數(shù)選擇范圍。給定RS碼的生成多項(xiàng)式，利用等效構(gòu)造法可以直接得到LDPC碼，它與通過雙重?cái)U(kuò)展RS碼得到的LDPC碼完全等價(jià)。在所有基于MDS構(gòu)造無4-環(huán)LDPC碼的方法中，本文方法為參數(shù)選擇提供了最大可能的靈活性。此外，利用循環(huán)MDS碼也可以簡便地構(gòu)造出準(zhǔn)循環(huán)LDPC碼，而且對應(yīng)的校驗(yàn)矩陣結(jié)構(gòu)非常緊湊。在LDPC碼的實(shí)用中，通常要求校驗(yàn)矩陣易于構(gòu)造、編碼器易于實(shí)現(xiàn)。本文提出的兩種實(shí)用化QC-LDPC碼構(gòu)造方法可以滿足這兩個要求。但是，目前絕大多數(shù)校驗(yàn)矩陣的結(jié)構(gòu)化構(gòu)造方法（包括本文方法）存在一個不足，即校驗(yàn)矩陣只有在構(gòu)造出來之后才可以確定LDPC碼的碼率。這對應(yīng)用來說是不方便的。給定碼長和碼率，如何構(gòu)造性能優(yōu)異的校驗(yàn)矩陣是LDPC碼實(shí)用中需要解決的一個問題，也是我們下一步的一個研究方向。參考文獻(xiàn)：1KOU Y, LIN S, FOSSORIER M P C. Low-density parity-check codes based on finite geometries: a rediscovery and new resultsJ. IEEE Trans Inform Theory, 2001,47(7):2711-2736.2WELLER S R, JOHNSON S J. Regular low-density parity-check codes from oval designsJ. Euro Trans Telecomms, 2003,14: 399-409.3JOHNSON S J, WELLER S R. High-rate LDPC codes from unital designsA. IEEE Globecom2003C. San Francisco, CA, 2003. 2036-2040.4WELLER S R, JOHNSON S J. Construction of low-density parity-check codes from Kirkman triple systemsA. Proceedings of IEEE Globecom conferenceC. San Antonio, TX, 2001.970-974.5AMMAR B, HONARY B, KOU Y, et al. Construction of low-density parity-check codes based on balanced incomplete block designsJ. IEEE Trans Inform Theory, 2004,50(6):1257-1268.6VASIC B, MILENKOVIC O. Combinatorial constructions of low-density parity-check codes for iterative decodingJ. IEEE Trans Inform Theory, 2004,50(6):1156-1176. 7DJURDJEVIC I, XU J, ABDEL-GHAFFAR K, et al. A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbolsJ. IEEE Commun Lett, 2003,7(7): 317-319.8CHEN L, DJURDJEVIC I, XU J, et al. Construction of QC-LDPC codes based on the minimum-weight codewords of RS codesA. Proc.IEEE Int.Symp.Inform.TheoryC. Chicago, 2004.239-239.9