改進的多進制QC—LDPC碼構造算法

佟寧寧+++佟偉松+++姜坤+++張海龍

摘 要：針對隨機構造多進制LDPC碼編碼復雜度高的問題，基于具有線性編碼復雜度的多進制LDPC碼的編碼方法，提出了一種改進的QC-LDPC碼校驗矩陣構造算法。仿真結果表明，該算法構造的多進制LDPC碼不僅可以獲得較高的編碼增益，而且具有低編碼復雜度、校驗矩陣存儲簡單等優點。

關鍵詞：準循環低密度奇偶校驗碼；多進制低密度奇偶校驗碼；高編碼增益；低編碼復雜度

1 引言

由于多進制低密奇偶校驗碼（Low-Density Parity-Check Codes，LDPC）[1]與二進制LDPC碼相比，具有更高的編碼增益、較強的抗突發錯誤能力以及更適合應用于高頻帶利用率的通信系統等優勢，因此近年來得到了信道編碼領域研究者的高度重視。雖然多進制LDPC碼具有顯著的優勢，但其高編譯碼復雜度阻礙了其實用化進程，導致多進制LDPC碼沒有得到廣泛的應用。根據不同的校驗矩陣結構，LDPC碼的構造方法主要可以分為兩大類：隨機構造方法及結構構造方法。隨機構造方法[2]具有糾錯性能好、碼長及碼率構造靈活等優點，但校驗矩陣構造算法及相應的編譯碼算法復雜度較高，尤其對于多進制LDPC碼，其編譯碼運算均是基于伽羅華域上的運算，復雜度更高，硬件難以實現；而結構構造算法[3]雖然碼長及碼率的取值受限，靈活性較差，但具有構造簡單、編譯碼算法復雜度低等優點，因此成為了主流的多進制LDPC碼校驗矩陣構造算法。由于LDPC碼的校驗矩陣構造方式直接影響其糾錯性能，并且一定程度上決定了編譯碼算法復雜度，因此文章提出了一種具有低編碼復雜度的多進制準循環LDPC碼（Quasi-Cyclic-LDPC，QC-LDPC）的構造算法，該算法不僅可以獲得較高的編碼增益，而且具有線性編碼運算復雜度、矩陣存儲簡單等優勢。

2 改進的多進制QC-LDPC碼構造算法

令 表示QC-LDPC碼的校驗矩陣，

（1）

其中， 0表示p×p維的零陣，I表示p×p維的單位陣，編碼長度為n=p×L，編碼碼率為r=（1-J/L）。

子矩陣 ，其中gcj，l為有限域系數， 表示

GF（q）域上的有限域元素gcj，l構成的矩陣，0？燮gcj，l？燮q-1。如果有限域系數gcj，l=0，則子矩陣Hj，l為零陣；如果gci，j≠0，則子矩陣Hj，l為矩陣

向右循環移位Sj，l次構成的矩陣，即 ， ，1？燮l？燮L，其中，Sj，l為循環移位系數， 表示移位系數構成的矩陣，0？燮sj，l？燮p-1。根據式（2）所示的避免長度為2i短環的充分必要條件，隨機選擇移位系數sj，l。

（2）

其中，2？燮m？燮i，1？燮jk？燮J，1？燮jk+1？燮J，1？燮lk？燮L，j0=jm。

算法具體步驟如下：

2.1 對于給定的LDPC碼度分布，具有下三角結構的二進制基矩陣WJ×L如式（1）所示，大小為J×L維，基矩陣可由如PEG算法、EBF算法等校驗矩陣的隨機構造算法生成。如果矩陣中的元素為“0”，則由一個p×p維的零陣替代該位置；如果矩陣中的元素為“1”，則首先隨機的從集合{1，…， q-1}中選取一個元素作為有限域系數gcj，l的值，然后由一個p×p維的單位陣I或者 的循環移位矩陣替代該位置。

2.2 基于式（2）選取移位系數的原則，可通過連續的試探法確定移位系數矩陣SJ×L中的移位系數Sj，l。

（1）如果基矩陣WJ×L第j列和第l行的元素wj，l的值為“0”，即，wj，l=0，1？燮j？燮J，1？燮l？燮L，則sj，l=0；

（2）如果基矩陣WJ×L第j列和第l行的元素wj，l的值為“1”，即，wj，l=1，1？燮j？燮J，1？燮l？燮L，則隨機的從集合{0，1，…，p-1}中選取一個移位系數Sj，l的值，對于給定的圍長，根據式（2）判斷是否滿足約束條件。如果滿足約束條件，則可以確定移位系數sj，l的值；如果不滿足約束條件，則重新執行步驟B。

（3）根據基矩陣WJ×L、循環移位矩陣SJ×L及有限域系數矩陣GcJ×L，則可以確定校驗矩陣H。如果wj，l=0，則子矩陣Hj，l=0p×p，即H（（j-1）*p+1：j*p），（l-1）*p+1：j*p）=0p×p；如果wj，l=1，則Hj，l=gcj，lIp×p（Sj，l），即H（（j-1）*p+1：j*p），（（l-1）*p+1：j*p）=gcj，lIp×p（Sj，l）。

3 仿真結果及分析

（a）誤碼率 （b）誤幀率

圖1 改進QC-LDPC與PEG算法的性能（q=16）

圖1顯示了PEG及改進的QC-LDPC碼構造算法構造的LDPC碼字誤碼率和誤幀率性能仿真曲線。其中，碼率r=1/2、2/3、3/4，q為16，LDPC碼的信息位長均為768比特，即信息位的符號長度分別為192和92，譯碼采用BP譯碼算法，為給硬件實現提供參考，最大譯碼迭代次數取25，調制方式為BPSK調制，信道為高斯白噪聲信道，兩種構造算法構造碼字的比特節點服從相同的度分布。由圖1可見，雖然采用改進的QC-LDPC構造方法構造出的具有下三角結構的LDPC碼誤碼率、誤幀率的性能略差于應用PEG構造方法構造出的LDPC碼，但性能差距非常小，表明兩個LDPC碼編碼增益基本一致。

4 編碼復雜度分析

雖然提出的QC-LDPC碼的性能不能超越PEG-LDPC碼，但其優勢在于具有更低的編碼復雜度及存儲復雜度。

從編碼復雜度的角度看，提出的QC-LDPC碼既可以采用迭代的編碼方法，也可以采用QC-LDPC碼的編碼方法，無論是哪種編碼方法，均具有線性的編碼復雜度。

同時，QC-LDPC碼的構造方法屬于結構化構造方法，所構造的LDPC碼具有準循環結構，存儲矩陣時只需存儲一個p×p的單位陣I、一個J×L的多進制系數矩陣GcJ×L及一個J×L的循環移位系數矩陣SJ×L即可。而隨機構造的同樣大小的校驗矩陣，則需要存儲一個p×J×p×L大小的校驗矩陣?？梢娫摲椒嬙斓腖DPC碼與隨機構造方法相比具有更簡單的矩陣存儲結構。

此外，因其該構造方法有一定的碼結構，克服了隨機構造算法（如PEG）構造中長碼時搜索時間過長的缺陷。

5 結束語

文章提出的多進制QC-LDPC碼構造算法所構造出的LDPC碼不僅具有線性的編碼復雜度及矩陣構造和存儲簡單的優點，同時具有較強的糾錯能力。

參考文獻

[1]楊民，張文彥，鐘杰，等.準循環多進制LDPC碼構造[J].電子信息學報，2013，35（2）：297-302.

[2]黎勇，王琳，陳俊斌.基于PEG算法的多進制LDPC碼的設計與仿真[J].重慶郵電學院學報，2006，18（2）：175-177.

[3]Zhao S， Ma X， Zhang X， et al. A Class of Non-binary LDPC Codes with Fast Encoding and Decoding Algorithms. IEEE Transactions on Communications. 2013， 61（1）：1-6.endprint

摘 要：針對隨機構造多進制LDPC碼編碼復雜度高的問題，基于具有線性編碼復雜度的多進制LDPC碼的編碼方法，提出了一種改進的QC-LDPC碼校驗矩陣構造算法。仿真結果表明，該算法構造的多進制LDPC碼不僅可以獲得較高的編碼增益，而且具有低編碼復雜度、校驗矩陣存儲簡單等優點。

關鍵詞：準循環低密度奇偶校驗碼；多進制低密度奇偶校驗碼；高編碼增益；低編碼復雜度

1 引言

由于多進制低密奇偶校驗碼（Low-Density Parity-Check Codes，LDPC）[1]與二進制LDPC碼相比，具有更高的編碼增益、較強的抗突發錯誤能力以及更適合應用于高頻帶利用率的通信系統等優勢，因此近年來得到了信道編碼領域研究者的高度重視。雖然多進制LDPC碼具有顯著的優勢，但其高編譯碼復雜度阻礙了其實用化進程，導致多進制LDPC碼沒有得到廣泛的應用。根據不同的校驗矩陣結構，LDPC碼的構造方法主要可以分為兩大類：隨機構造方法及結構構造方法。隨機構造方法[2]具有糾錯性能好、碼長及碼率構造靈活等優點，但校驗矩陣構造算法及相應的編譯碼算法復雜度較高，尤其對于多進制LDPC碼，其編譯碼運算均是基于伽羅華域上的運算，復雜度更高，硬件難以實現；而結構構造算法[3]雖然碼長及碼率的取值受限，靈活性較差，但具有構造簡單、編譯碼算法復雜度低等優點，因此成為了主流的多進制LDPC碼校驗矩陣構造算法。由于LDPC碼的校驗矩陣構造方式直接影響其糾錯性能，并且一定程度上決定了編譯碼算法復雜度，因此文章提出了一種具有低編碼復雜度的多進制準循環LDPC碼（Quasi-Cyclic-LDPC，QC-LDPC）的構造算法，該算法不僅可以獲得較高的編碼增益，而且具有線性編碼運算復雜度、矩陣存儲簡單等優勢。

2 改進的多進制QC-LDPC碼構造算法

令 表示QC-LDPC碼的校驗矩陣，

（1）

其中， 0表示p×p維的零陣，I表示p×p維的單位陣，編碼長度為n=p×L，編碼碼率為r=（1-J/L）。

子矩陣 ，其中gcj，l為有限域系數， 表示

GF（q）域上的有限域元素gcj，l構成的矩陣，0？燮gcj，l？燮q-1。如果有限域系數gcj，l=0，則子矩陣Hj，l為零陣；如果gci，j≠0，則子矩陣Hj，l為矩陣

向右循環移位Sj，l次構成的矩陣，即 ， ，1？燮l？燮L，其中，Sj，l為循環移位系數， 表示移位系數構成的矩陣，0？燮sj，l？燮p-1。根據式（2）所示的避免長度為2i短環的充分必要條件，隨機選擇移位系數sj，l。

（2）

其中，2？燮m？燮i，1？燮jk？燮J，1？燮jk+1？燮J，1？燮lk？燮L，j0=jm。

算法具體步驟如下：

2.1 對于給定的LDPC碼度分布，具有下三角結構的二進制基矩陣WJ×L如式（1）所示，大小為J×L維，基矩陣可由如PEG算法、EBF算法等校驗矩陣的隨機構造算法生成。如果矩陣中的元素為“0”，則由一個p×p維的零陣替代該位置；如果矩陣中的元素為“1”，則首先隨機的從集合{1，…， q-1}中選取一個元素作為有限域系數gcj，l的值，然后由一個p×p維的單位陣I或者 的循環移位矩陣替代該位置。

2.2 基于式（2）選取移位系數的原則，可通過連續的試探法確定移位系數矩陣SJ×L中的移位系數Sj，l。

（1）如果基矩陣WJ×L第j列和第l行的元素wj，l的值為“0”，即，wj，l=0，1？燮j？燮J，1？燮l？燮L，則sj，l=0；

（2）如果基矩陣WJ×L第j列和第l行的元素wj，l的值為“1”，即，wj，l=1，1？燮j？燮J，1？燮l？燮L，則隨機的從集合{0，1，…，p-1}中選取一個移位系數Sj，l的值，對于給定的圍長，根據式（2）判斷是否滿足約束條件。如果滿足約束條件，則可以確定移位系數sj，l的值；如果不滿足約束條件，則重新執行步驟B。

（3）根據基矩陣WJ×L、循環移位矩陣SJ×L及有限域系數矩陣GcJ×L，則可以確定校驗矩陣H。如果wj，l=0，則子矩陣Hj，l=0p×p，即H（（j-1）*p+1：j*p），（l-1）*p+1：j*p）=0p×p；如果wj，l=1，則Hj，l=gcj，lIp×p（Sj，l），即H（（j-1）*p+1：j*p），（（l-1）*p+1：j*p）=gcj，lIp×p（Sj，l）。

3 仿真結果及分析

（a）誤碼率 （b）誤幀率

圖1 改進QC-LDPC與PEG算法的性能（q=16）

圖1顯示了PEG及改進的QC-LDPC碼構造算法構造的LDPC碼字誤碼率和誤幀率性能仿真曲線。其中，碼率r=1/2、2/3、3/4，q為16，LDPC碼的信息位長均為768比特，即信息位的符號長度分別為192和92，譯碼采用BP譯碼算法，為給硬件實現提供參考，最大譯碼迭代次數取25，調制方式為BPSK調制，信道為高斯白噪聲信道，兩種構造算法構造碼字的比特節點服從相同的度分布。由圖1可見，雖然采用改進的QC-LDPC構造方法構造出的具有下三角結構的LDPC碼誤碼率、誤幀率的性能略差于應用PEG構造方法構造出的LDPC碼，但性能差距非常小，表明兩個LDPC碼編碼增益基本一致。

4 編碼復雜度分析

雖然提出的QC-LDPC碼的性能不能超越PEG-LDPC碼，但其優勢在于具有更低的編碼復雜度及存儲復雜度。

從編碼復雜度的角度看，提出的QC-LDPC碼既可以采用迭代的編碼方法，也可以采用QC-LDPC碼的編碼方法，無論是哪種編碼方法，均具有線性的編碼復雜度。

同時，QC-LDPC碼的構造方法屬于結構化構造方法，所構造的LDPC碼具有準循環結構，存儲矩陣時只需存儲一個p×p的單位陣I、一個J×L的多進制系數矩陣GcJ×L及一個J×L的循環移位系數矩陣SJ×L即可。而隨機構造的同樣大小的校驗矩陣，則需要存儲一個p×J×p×L大小的校驗矩陣?？梢娫摲椒嬙斓腖DPC碼與隨機構造方法相比具有更簡單的矩陣存儲結構。

此外，因其該構造方法有一定的碼結構，克服了隨機構造算法（如PEG）構造中長碼時搜索時間過長的缺陷。

5 結束語

文章提出的多進制QC-LDPC碼構造算法所構造出的LDPC碼不僅具有線性的編碼復雜度及矩陣構造和存儲簡單的優點，同時具有較強的糾錯能力。

參考文獻

[1]楊民，張文彥，鐘杰，等.準循環多進制LDPC碼構造[J].電子信息學報，2013，35（2）：297-302.

[2]黎勇，王琳，陳俊斌.基于PEG算法的多進制LDPC碼的設計與仿真[J].重慶郵電學院學報，2006，18（2）：175-177.

[3]Zhao S， Ma X， Zhang X， et al. A Class of Non-binary LDPC Codes with Fast Encoding and Decoding Algorithms. IEEE Transactions on Communications. 2013， 61（1）：1-6.endprint

摘 要：針對隨機構造多進制LDPC碼編碼復雜度高的問題，基于具有線性編碼復雜度的多進制LDPC碼的編碼方法，提出了一種改進的QC-LDPC碼校驗矩陣構造算法。仿真結果表明，該算法構造的多進制LDPC碼不僅可以獲得較高的編碼增益，而且具有低編碼復雜度、校驗矩陣存儲簡單等優點。

關鍵詞：準循環低密度奇偶校驗碼；多進制低密度奇偶校驗碼；高編碼增益；低編碼復雜度

1 引言

由于多進制低密奇偶校驗碼（Low-Density Parity-Check Codes，LDPC）[1]與二進制LDPC碼相比，具有更高的編碼增益、較強的抗突發錯誤能力以及更適合應用于高頻帶利用率的通信系統等優勢，因此近年來得到了信道編碼領域研究者的高度重視。雖然多進制LDPC碼具有顯著的優勢，但其高編譯碼復雜度阻礙了其實用化進程，導致多進制LDPC碼沒有得到廣泛的應用。根據不同的校驗矩陣結構，LDPC碼的構造方法主要可以分為兩大類：隨機構造方法及結構構造方法。隨機構造方法[2]具有糾錯性能好、碼長及碼率構造靈活等優點，但校驗矩陣構造算法及相應的編譯碼算法復雜度較高，尤其對于多進制LDPC碼，其編譯碼運算均是基于伽羅華域上的運算，復雜度更高，硬件難以實現；而結構構造算法[3]雖然碼長及碼率的取值受限，靈活性較差，但具有構造簡單、編譯碼算法復雜度低等優點，因此成為了主流的多進制LDPC碼校驗矩陣構造算法。由于LDPC碼的校驗矩陣構造方式直接影響其糾錯性能，并且一定程度上決定了編譯碼算法復雜度，因此文章提出了一種具有低編碼復雜度的多進制準循環LDPC碼（Quasi-Cyclic-LDPC，QC-LDPC）的構造算法，該算法不僅可以獲得較高的編碼增益，而且具有線性編碼運算復雜度、矩陣存儲簡單等優勢。

2 改進的多進制QC-LDPC碼構造算法

令 表示QC-LDPC碼的校驗矩陣，

（1）

其中， 0表示p×p維的零陣，I表示p×p維的單位陣，編碼長度為n=p×L，編碼碼率為r=（1-J/L）。

子矩陣 ，其中gcj，l為有限域系數， 表示

GF（q）域上的有限域元素gcj，l構成的矩陣，0？燮gcj，l？燮q-1。如果有限域系數gcj，l=0，則子矩陣Hj，l為零陣；如果gci，j≠0，則子矩陣Hj，l為矩陣

向右循環移位Sj，l次構成的矩陣，即 ， ，1？燮l？燮L，其中，Sj，l為循環移位系數， 表示移位系數構成的矩陣，0？燮sj，l？燮p-1。根據式（2）所示的避免長度為2i短環的充分必要條件，隨機選擇移位系數sj，l。

（2）

其中，2？燮m？燮i，1？燮jk？燮J，1？燮jk+1？燮J，1？燮lk？燮L，j0=jm。

算法具體步驟如下：

2.1 對于給定的LDPC碼度分布，具有下三角結構的二進制基矩陣WJ×L如式（1）所示，大小為J×L維，基矩陣可由如PEG算法、EBF算法等校驗矩陣的隨機構造算法生成。如果矩陣中的元素為“0”，則由一個p×p維的零陣替代該位置；如果矩陣中的元素為“1”，則首先隨機的從集合{1，…， q-1}中選取一個元素作為有限域系數gcj，l的值，然后由一個p×p維的單位陣I或者 的循環移位矩陣替代該位置。

2.2 基于式（2）選取移位系數的原則，可通過連續的試探法確定移位系數矩陣SJ×L中的移位系數Sj，l。

（1）如果基矩陣WJ×L第j列和第l行的元素wj，l的值為“0”，即，wj，l=0，1？燮j？燮J，1？燮l？燮L，則sj，l=0；

（2）如果基矩陣WJ×L第j列和第l行的元素wj，l的值為“1”，即，wj，l=1，1？燮j？燮J，1？燮l？燮L，則隨機的從集合{0，1，…，p-1}中選取一個移位系數Sj，l的值，對于給定的圍長，根據式（2）判斷是否滿足約束條件。如果滿足約束條件，則可以確定移位系數sj，l的值；如果不滿足約束條件，則重新執行步驟B。

（3）根據基矩陣WJ×L、循環移位矩陣SJ×L及有限域系數矩陣GcJ×L，則可以確定校驗矩陣H。如果wj，l=0，則子矩陣Hj，l=0p×p，即H（（j-1）*p+1：j*p），（l-1）*p+1：j*p）=0p×p；如果wj，l=1，則Hj，l=gcj，lIp×p（Sj，l），即H（（j-1）*p+1：j*p），（（l-1）*p+1：j*p）=gcj，lIp×p（Sj，l）。

3 仿真結果及分析

（a）誤碼率 （b）誤幀率

圖1 改進QC-LDPC與PEG算法的性能（q=16）

圖1顯示了PEG及改進的QC-LDPC碼構造算法構造的LDPC碼字誤碼率和誤幀率性能仿真曲線。其中，碼率r=1/2、2/3、3/4，q為16，LDPC碼的信息位長均為768比特，即信息位的符號長度分別為192和92，譯碼采用BP譯碼算法，為給硬件實現提供參考，最大譯碼迭代次數取25，調制方式為BPSK調制，信道為高斯白噪聲信道，兩種構造算法構造碼字的比特節點服從相同的度分布。由圖1可見，雖然采用改進的QC-LDPC構造方法構造出的具有下三角結構的LDPC碼誤碼率、誤幀率的性能略差于應用PEG構造方法構造出的LDPC碼，但性能差距非常小，表明兩個LDPC碼編碼增益基本一致。

4 編碼復雜度分析

雖然提出的QC-LDPC碼的性能不能超越PEG-LDPC碼，但其優勢在于具有更低的編碼復雜度及存儲復雜度。

從編碼復雜度的角度看，提出的QC-LDPC碼既可以采用迭代的編碼方法，也可以采用QC-LDPC碼的編碼方法，無論是哪種編碼方法，均具有線性的編碼復雜度。

同時，QC-LDPC碼的構造方法屬于結構化構造方法，所構造的LDPC碼具有準循環結構，存儲矩陣時只需存儲一個p×p的單位陣I、一個J×L的多進制系數矩陣GcJ×L及一個J×L的循環移位系數矩陣SJ×L即可。而隨機構造的同樣大小的校驗矩陣，則需要存儲一個p×J×p×L大小的校驗矩陣。可見該方法構造的LDPC碼與隨機構造方法相比具有更簡單的矩陣存儲結構。

此外，因其該構造方法有一定的碼結構，克服了隨機構造算法（如PEG）構造中長碼時搜索時間過長的缺陷。

5 結束語

文章提出的多進制QC-LDPC碼構造算法所構造出的LDPC碼不僅具有線性的編碼復雜度及矩陣構造和存儲簡單的優點，同時具有較強的糾錯能力。

參考文獻

[1]楊民，張文彥，鐘杰，等.準循環多進制LDPC碼構造[J].電子信息學報，2013，35（2）：297-302.

[2]黎勇，王琳，陳俊斌.基于PEG算法的多進制LDPC碼的設計與仿真[J].重慶郵電學院學報，2006，18（2）：175-177.

[3]Zhao S， Ma X， Zhang X， et al. A Class of Non-binary LDPC Codes with Fast Encoding and Decoding Algorithms. IEEE Transactions on Communications. 2013， 61（1）：1-6.endprint