[發明專利]一種準循環低密度奇偶校驗碼的構造方法

無效

• 申請號: 200810239316.0
• 申請日: 2008-12-10
• 公開（公告）號: CN101753149A
• 公開（公告）日: 2010-06-23
• 發明（設計）人: 李繼龍;楊明;李錦文;高鵬;吳智勇;盛國芳;邸娜
• 申請（專利權）人: 國家廣播電影電視總局廣播科學研究院
• 主分類號: H03M13/11
• 分類號: H03M13/11
• 代理公司: 信息產業部電子專利中心 11010
• 代理人: 梁軍

技術領域

本發明涉及通信技術領域，特別涉及一種準循環低密度奇偶校驗碼的構造方法。

背景技術

低密度奇偶校驗(Low?Density?Parity?Check，LDPC)碼是由Gallager在1962年最先提出的，被證實是一種在高斯白噪聲(AWGN)下能夠很好的逼近香農限的編碼方式，因而得到廣泛的關注。LDPC碼優秀的性能不僅是學術界的研究熱點，也開始大量應用于工業界。目前在一些標準中，如DVB-S2、IEEE802.16e，以及中國的數字電視地面廣播、數字電視衛星廣播、移動多媒體廣播標準中，都采用了LDPC碼。

LDPC碼由其校驗矩陣H或其所對應的Tanner圖所唯一確定。LDPC碼的校驗矩陣是一個N×M的稀疏矩陣，如果矩陣的每一行和每一列都有相同的重量j，k，稱這種LDPC碼是規則的；否則這種LDPC碼是不規則的。其中，一行或一列中1的個數稱為重量。LDPC碼性能與該碼對應的Tanner圖中的最小環的長度有很大的關系，稱最小環長度為該LDPC碼的圍長g。Tanner證明了LDPC碼的最小距離d_min的下界隨著圍長g的增長指數增長。而且，當使用迭代解碼算法的時候，圍長大的碼一般比圍長小的碼收斂的快。因此，在涉及LDPC碼時，一般都優先考慮圍長g的大小。同時，在LDPC碼的設計中，平均最小環長也影響碼的性能。減少小環的數量就是增加了獨立迭代的次數，從而需要相對較少的迭代次數就能正確譯碼，較大程度上提升了碼子性能。因而在碼的設計中要減少小環的數目，從而最大化平均最小環。

LDPC碼具有稀疏的校驗結構，因此便于實現并行譯碼，但是一般來說，LDPC碼的編碼矩陣并不稀疏，尤其是計算機搜索出來的隨機LDPC碼，由于沒有足夠的結構特性，編碼復雜且消耗大量存儲單元。準循環LDPC(QC-LDPC)碼是一類具有一定結構的LDPC碼，可以以線性復雜度被編碼，近年來成為了研究的熱點。準循環碼在中短碼時具有相當強的糾錯能力，性能接近隨機構造的最優LDPC碼，又因其硬件實現極其簡單，只需用反饋移位寄存器連接就可實現，因此具有很好的應用前景。

QC-LDPC碼的奇偶校驗矩陣H可表示為下面的形式：

式中，P_i，j∈[-1，p-1]，p為一正整數，表示每個塊矩陣的大小。當P_i，j＝-1時，擴展矩陣表示一個p×p的全零矩陣；當P_i，j＝0到P-1之間的一個正整數時，擴展陣表示一個p×p的循環置換矩陣，它是由單位矩陣的每一行循環右移位P_i，j位得到的。n和m是兩個正整數。此時，H的維數是mp×np，碼的長度為np，矩陣H的秩最高是mp，所以碼率至少為(n-m)/n。

定義QC-LDPC碼奇偶校驗矩陣H的指數矩陣M(H)：

H矩陣可以由指數矩陣M(H)擴展得到。

在構造QC-LDPC碼奇偶校驗矩陣H時，一般先產生滿足要求的行列權重的指數矩陣M(H)，由M(H)指數擴展就得到H。

現有設計QC-LDPC碼的方法主要有以下幾種。基于有限域上的幾何的方法，這種方法的缺點是只能保證構造出g＞4的碼。參見M.Fossorier，Quasi-cycliclow-density?parity-check?codes?from?circulant?permutation?matrices，IEEE.Trans.Inform.Theory，Vol.50，no.8，pp.1788-1793，Aug.2004。Fossorier給出了使用循環置換矩陣構造的LDPC碼的圍長g和行列的重量j，k之間的關系，但是并沒有給出有效的構造方法。

Xiao-Yu?Hu提出了一種非代數的構造LDPC碼的方法，漸進邊增長(Progressive-Edge-Growth，PEG)的構造方法，該算法中在Tanner圖上一次添加一條邊來生成需要的LDPC碼，它可以使校驗矩陣具有較大的環長，從而降低了誤碼平層，具有較高的復雜度和較好的靈活性。PEG構造法的基本思想是由無環的二分圖開始，向二分圖里逐條增加連接比特節點與校驗節點的邊，每次增加邊時，都盡量使得由于新增邊而形成的環盡可能地長，增加的新邊可以使圖的girth達到最大，最終獲得具有較大圍長的碼字。該PEG算法被認為是目前性能最優的LDPC校驗矩陣構造方法。