一種高圍長低復(fù)雜度LDPC碼構(gòu)造方法

覃遠(yuǎn)年，鄒 川，滕召宇，江 琪

（桂林電子科技大學(xué)信息與通信學(xué)院，廣西桂林 541004）

一種高圍長低復(fù)雜度LDPC碼構(gòu)造方法

覃遠(yuǎn)年，鄒 川，滕召宇，江 琪

（桂林電子科技大學(xué)信息與通信學(xué)院，廣西桂林 541004）

LDPC（低密度奇偶校驗(yàn)）碼常見的編碼方法常常無法將校驗(yàn)矩陣的圍長和線性無關(guān)相統(tǒng)一，對編譯碼復(fù)雜度和譯碼性能有一定影響。文章提出了一種低復(fù)雜度LDPC的構(gòu)造方法，通過構(gòu)造分塊矩陣A和B，獲得一個(gè)圍長為10、列重為2、具有近似下三角形式的校驗(yàn)矩陣，且矩陣各行之間線性無關(guān)。該碼具有以下優(yōu)點(diǎn)：較高的圍長能提升譯碼性能；較低的列重使該碼適合在部分響應(yīng)信道傳播；近似下三角形式和線性無關(guān)的特性，較好地降低了編譯碼的復(fù)雜度。采用Matlab軟件的仿真結(jié)果表明，在高斯白噪聲信道、BP（置信傳播）譯碼算法下，該碼比普通的10圍長LDPC碼具有更低的復(fù)雜度，比普通的6圍長LDPC碼具有更好的譯碼性能。

低密度奇偶校驗(yàn)碼；高圍長；低復(fù)雜度；近似下三角；線性無關(guān)

0 引 言

LDPC（低密度奇偶校驗(yàn)）碼已被證明是目前最接近香農(nóng)極限的編碼，廣泛應(yīng)用在3G、4G移動(dòng)通信領(lǐng)域，在未來的5G移動(dòng)通信中，LDPC碼仍將在信道編碼中擔(dān)當(dāng)重任［1］。影響LDPC碼性能的主要因素有最小碼距、圍長、碼率和碼長。當(dāng)列重j≥3時(shí)，其最小碼距dmin與碼長N成正比；當(dāng)j=2時(shí)，dmin與N成對數(shù)關(guān)系［2］。j為2的LDPC碼具有更低的計(jì)算復(fù)雜度，更適合在部分響應(yīng)信道中傳播［3］。當(dāng)列重一定時(shí)，最小碼距隨圍長的增加呈指數(shù)規(guī)律增加［4］。

LDPC碼的構(gòu)造方法很多，性能也各有利弊，大體上可分為兩類:隨機(jī)構(gòu)造法和結(jié)構(gòu)化構(gòu)造法。隨機(jī)構(gòu)造法通過計(jì)算機(jī)按照一定的規(guī)則搜索，其性能更容易接近香濃極限，但由于“1”元素分布沒有規(guī)律，實(shí)際應(yīng)用時(shí)其算法復(fù)雜度和邏輯資源的消耗都比較大。結(jié)構(gòu)化構(gòu)造法具有清晰的數(shù)學(xué)模型，校驗(yàn)矩陣H中“1”元素排布有序，在降低編碼復(fù)雜度的同時(shí)，也能控制圍長的大小，以QC-LDPC（準(zhǔn)循環(huán)低密度奇偶校驗(yàn)）碼最為常見。

常見的編碼方法通常無法將圍長和H的線性無關(guān)相統(tǒng)一，或一味追求高圍長的H而使其部分行向量出現(xiàn)相關(guān)的情況。雖然奇異的校驗(yàn)矩陣H能回避生成矩陣G實(shí)現(xiàn)編碼，但也必須通過行列變換，從H中分離出一個(gè)含M個(gè)行向量的可逆子矩陣（假設(shè)H的大小為M×N），且譯碼時(shí)還需對譯碼結(jié)果按編碼的逆順序做列交換，才能得到最終的譯碼結(jié)果［5］，這無疑加重了計(jì)算復(fù)雜度，帶來了一定的譯碼延遲，而通過H求G的過程也并不簡單。

本文提出使用結(jié)構(gòu)化構(gòu)造法，在構(gòu)造LDPC碼之初，先確定H的每個(gè)行向量都線性無關(guān)，在此基礎(chǔ)上保證其具有較大的圍長，就能兼顧H的大圍長和線性無關(guān)，在保證譯碼性能的同時(shí)，在一定程度上簡化了編譯碼步驟，降低了復(fù)雜度。

1 LDPC碼的構(gòu)造

本文所提LDPC碼的構(gòu)造過程可以概括為兩步:（1）通過循環(huán)移位法擴(kuò)展近似下三角矩陣Abasic，獲得滿秩分塊矩陣A；（2）使用織籠法［6］構(gòu)造高圍長矩陣Bbasic，得到分塊矩陣B，最后校驗(yàn)矩陣表示為H=［B|A］，其大小為M×N，M為H的行數(shù)，N為H的列數(shù)。

1.1 分塊矩陣A的構(gòu)造

構(gòu)造一個(gè)大小為M×M的分塊矩陣A，具體方法如下:創(chuàng)建一個(gè)上三角矩陣，使得主對角線和次對角線上的元素為“1”，其余元素為“0”；創(chuàng)建一個(gè)5× 6的上三角矩陣A1，如圖1所示，為了確保A1的列重為2，將最后一列的“1”元素移到第一列對應(yīng)的位置，并刪除最后一列，得到Abasic，大小為5×5。

圖1 分塊矩陣Abasic的構(gòu)造示意圖

對Abasic進(jìn)行擴(kuò)展，使其大小為M×M，擴(kuò)展方法如下:創(chuàng)建一個(gè)k×k的單位陣E和一個(gè)k×k的零矩陣Z，使得M=5×k，式中，M為Abasic行向量的個(gè)數(shù)；k為矩陣E和Z行向量的個(gè)數(shù)。用E的循環(huán)移位陣取代Abasic中所有“1”元素，用Z取代Abasic中所有“0”元素，最終得到分塊矩陣A。設(shè)（i，j）代表Abasic中各元素的位置，循環(huán)移位的規(guī)則為EQij=j-1。若（i，j）對應(yīng)為“1”，則EQij表示E向右循環(huán)移位的次數(shù)。經(jīng)過驗(yàn)證，所得的A是一個(gè)滿秩矩陣，且圍長為10，確保了校驗(yàn)矩陣H具有圍長不低于10的條件。

1.2 分塊矩陣B的構(gòu)造

將Bbasic的每一行看做一個(gè)點(diǎn)，如果第j列上的某兩個(gè)元素（i1，j）和（i2，j）為“1”，則將i1、i2兩行對應(yīng)的點(diǎn)用一條直線連接起來，這種將矩陣元素用點(diǎn)和線表示的方法叫做“織籠法”。它與常用的“Tanner圖”（也叫“二分圖”或“二部圖”）有明顯的區(qū)別。圖2所示為織籠法示意圖。在圖2（a）中，（i1=1，j=1）和（i2=3，j=1）兩個(gè)位置的元素為“1”，將（1，1）和（3，1）兩點(diǎn)用直線相連，對應(yīng)圖2（b）即為序號①和③以及連接①、③的直線。

圖2（b）是圖2（a）根據(jù)織籠法畫出的織籠圖，根據(jù)織籠法定理，圖2（b）中存在最小多邊形的邊數(shù)dmin，對應(yīng)圖2（a）矩陣Bbasic的圍長為2d。由圖2（b）可知，dmin=3，那么矩陣Bbasic的圍長為6。據(jù)此原理，當(dāng)我們增加Bbasic的行列數(shù)，取dmin=5織一個(gè)最小為五邊形的籠子時(shí)，就可以得到圍長為10的矩陣。按照循環(huán)移位擴(kuò)展法，可以擴(kuò)展Bbasic至大小為M×P（P由Bbasic的列數(shù)和擴(kuò)展矩陣的大小決定）的分塊矩陣B，而圍長保持不變，甚至大于10［6］。圖3所示為擴(kuò)展前圍長為10的矩陣塊Bbasic。

圖2 織籠法示意圖

圖3 圍長為10的矩陣塊Bbasic

2 性能仿真

我們創(chuàng)建了分塊矩陣A和B，得到新型校驗(yàn)矩陣H=［B|A］，其為大小為M×（M+P）、列重j為2、圍長為10的滿秩矩陣。利用Matlab軟件分別對大小均為850×2 550的新型10圍長校驗(yàn)矩陣、普通10圍長校驗(yàn)矩陣，以及普通6圍長的校驗(yàn)矩陣，按式（1）和式（2）進(jìn)行編碼，對編碼進(jìn)行2PSK（二進(jìn)制相移鍵控）調(diào)制，在高斯白噪聲信道下，采用BP（置信傳播）譯碼算法仿真其性能，并比較各自的算法復(fù)雜度。假設(shè)編碼后的編碼序列U由信源序列S和校驗(yàn)位C組成，且S在前，C在后，則有

進(jìn)而可得C=A-1·BT·S。

圖4所示為性能仿真結(jié)果圖。由圖可知，本文所提10圍長編碼與普通10圍長編碼性能相當(dāng)，且優(yōu)于普通6圍長編碼，符合預(yù)期。

圖4 性能仿真結(jié)果

在算法復(fù)雜度方面，由于本文所提編碼在構(gòu)造之初就確保了其具有線性無關(guān)和稀疏性，編碼時(shí)不需要對H進(jìn)行LU分解（矩陣分解的一種）來獲得可逆的矩陣塊A，譯碼時(shí)也不需要按照分解的順序進(jìn)行反交換，在一定程度上降低了編譯碼的復(fù)雜度。表1為上述3種編碼的算法復(fù)雜度統(tǒng)計(jì)。可見，本文所提編碼具有較低的算法復(fù)雜度。

表1 3種編碼的算法復(fù)雜度統(tǒng)計(jì)

3 結(jié)束語

本文介紹了一種LDPC碼的編碼方法，分別構(gòu)造分塊矩陣A和B，使H兼具非奇異和高圍長特性，與普通的10圍長和6圍長編碼相比，該方法在降低編譯碼復(fù)雜度的同時(shí)，還具有較好的譯碼性能。仿真結(jié)果表明，該編碼在信噪比2.2 dB附近誤碼率達(dá)到10-6，編碼復(fù)雜度為O（n2），具有一定的實(shí)用價(jià)值。

［1］本刊訊.IMT-2020（5G）推進(jìn)組發(fā)布5G技術(shù)白皮書［J］.中國無線電，2015，（05）:6.

［2］Gallager R G.Low-density parity-check codes［C］.IRE TRANSACTIONS ON INFORMATION THEORY，IEEE INC.NEW YORK，US:IEEE，1962，8（1）:21-28.

［3］Malema G，Liebelt M.High Girth Column-Weight-Two LDPC Codes Based on Distance Graphs［J］.Eurasip Journal on Wireless Communications&Networking，2007，2007（1）:211-216.

［4］張國華，劉智娟，王鳴濤.一類girth-8QC-LDPC碼構(gòu)造方法的簡化和擴(kuò)展［J］.空間電子技術(shù)，2015，12（4）:30-34.

［5］史治平.多元LDPC碼及其在無線通信中的應(yīng)用［M］.北京:國防工業(yè)出版社，2012.

［6］Kumari M，Bhutto J K.LDPC Codes Based On Fullerene Graphs［J］.Ijecce，2013，1（4）:203-206.

LDPC Codes Construction with High Girth Low Complexity

QIN Yuan-nian，ZOU Chuan，TENG Zhao-yu，JIANG Qi
（School of Information and Communication，Guilin University of Electronic Technology，Guilin 541004，China）

The conventional encoding method of Low Density Parity Check（LDPC）Code often cannot put the girth and nonsingularity of check matrices into consideration at the same time，which has negative effects on the performances of encoding and decoding，and increases the decoding complexity.A low complexity method to construct check matrices is presented.A matrix with properties of girth of 10，column weight of 2，nonsingularity，and approximate lower triangular is generated by constructing the sub-matrix A and sub-matrix B step by step.Due to these features，some advantages such as better decoding performance，more suitable for partial response channels，lower encoding and decoding complexity are shown.The simulation result shows that the proposed coding scheme has lower complexity than the code with girth of 10.It also presents better decoding performance than common code with girth of 6 in AWGN channels after Belief Propagation（BP）decoding algorithm.

LDPC code；high girth；low complexity；approximate lower triangular；nonsingularity

TN92

A

1005-8788（2016）05-0027-02

10.13756/j.gtxyj.2016.05.008

2016-06-03

國家自然科學(xué)基金資助項(xiàng)目（61162008）；廣西科學(xué)研究與技術(shù)開發(fā)項(xiàng)目（12118017-5）

覃遠(yuǎn)年（1971-），男，廣西賀州人。副教授，主要研究方向?yàn)橹悄苄畔z測與智能通信。

鄒川，碩士研究生。E-mail:372179946@qq.com