改進的多進制LDPC碼的EBF算法

佟寧寧，趙旦峰，吳宇平

1)哈爾濱工程大學信息與通信工程學院，哈爾濱150001;2)黑龍江工程學院電氣與信息工程學院，哈爾濱150050

低密度奇偶校驗碼 (low-density parity-check codes，LDPC)碼與Turbo碼［1］是迄今為止糾錯性能最好的信道編碼技術(shù).多進制LDPC碼具有高可靠性、快速收斂性及較強抗突發(fā)錯誤能力［2-7］，并可提高通信系統(tǒng)的有效性［8-14］，因此成為近年的研究熱點.LDPC碼的校驗矩陣構(gòu)造方法可以分為結(jié)構(gòu)構(gòu)造方法［15-20］和隨機構(gòu)造方法.結(jié)構(gòu)構(gòu)造的LDPC碼的優(yōu)勢在于它具有低復(fù)雜度的編譯碼器結(jié)構(gòu)，從而可降低編譯碼器的硬件實現(xiàn)復(fù)雜度，但選擇碼長和碼率等參數(shù)不夠靈活，兼容性較差.而在碼長趨于無窮時，隨機構(gòu)造的LDPC碼與結(jié)構(gòu)構(gòu)造的LDPC碼相比更接近Shannon限，碼長、碼率等參數(shù)選擇靈活，但其優(yōu)越性能是以高編譯碼復(fù)雜度為代價的，阻礙了其實際應(yīng)用.因此，降低隨機構(gòu)造多進制LDPC碼的編碼復(fù)雜度，使其進一步實用化具有重大意義.本研究針對隨機構(gòu)造多進制LDPC碼編碼復(fù)雜度高的缺陷，基于具有線性編碼復(fù)雜度的多進制LDPC碼迭代編碼方法，提出一種改進多進制LDPC碼隨機構(gòu)造算法——改進的擴展比特填充(extended bit-filling，EBF)構(gòu)造算法.與原EBF算法相比，本研究提出的算法可在不損失編碼增益的情況下，降低系統(tǒng)的編碼復(fù)雜度.

1 多進制LDPC碼的迭代編碼算法

王鵬［21］提出的基于二元LDPC碼的迭代編碼算法，很容易被轉(zhuǎn)變成適用于多進制的LDPC編碼方法.若多進制LDPC碼的校驗矩陣具有如圖1的下三角結(jié)構(gòu)，其中對角線的位置上全為有限域GF(q)上的非0元素，而其余的非0元素均在對角線的左邊，則可直接采用迭代編碼算法進行編碼.設(shè)碼字符號向量為c∈Fn，將其分為信息位符號向量s∈Fn－m和校驗位符號向量p∈Fm兩部分，即c∈(s，p)，則該編碼算法為

其中，l∈［0，n － k －1］;Hi，j表示校驗矩陣H的第i行，第j列上的元素，且k=n－m.由式(1)可見，該編碼過程就是利用校驗矩陣H各行的約束關(guān)系，采用后向迭代的方法，依次計算每個校驗位符號值.

圖1 具有下三角結(jié)構(gòu)的校驗矩陣Fig.1 The parity check matrix with lower triangle structure

多進制迭代編碼方法與二進制迭代編碼方法的原理基本相同，區(qū)別在于:在二進制迭代編碼運算過程中，采用的是二進制的與以及異或運算，而用多進制迭代編碼方法運算時，采用的是GF(q)域上的乘加運算;多進制迭代編碼運算過程中引入了GF(q)域上除法運算，與二進制迭代編碼算法相比，增加了編碼復(fù)雜度.為簡化運算量，可令對角線上的元素全為1，此時，式 (1)可寫為

2 改進的擴展比特填充構(gòu)造算法

針對隨機構(gòu)造多進制LDPC碼的高編碼復(fù)雜度，基于線性編碼復(fù)雜度的迭代編碼算法，本研究提出一種直接構(gòu)造具有下三角結(jié)構(gòu)的非規(guī)則多進制LDPC碼的方法——改進的多進制EBF算法，從改進編碼方案和構(gòu)造校驗矩陣方面降低算法復(fù)雜度.

EBF算法的基本原理，是在保持給定的girth約束條件下，將GF(q)域上的非0元素依次填充到校驗矩陣 H中［22］.在整個算法的執(zhí)行過程中，girth約束一直都是變化的.在算法最初執(zhí)行時保持girth約束的最大值g，直到不降低girth約束就不能給校驗矩陣中填充非0元素時為止.這時girth約束可降低 (以2遞減)，算法在保證新的girth約束條件下繼續(xù).如此循環(huán)，當所有的非0元素都成功填充到校驗矩陣中，或girth約束低于給定的最小值g時，算法停止.本研究提出的改進多進制LDPC碼的EBF算法與無改進的EBF算法流程基本相同，改進點包括:

改進1 按列號由大到小依次排序，將GF(q)域上的非0元素添加到校驗矩陣H的每一列.

校驗矩陣的環(huán)分布是決定LDPC碼糾錯性能好壞的關(guān)鍵，因此構(gòu)造校驗矩陣H時，如何消除短環(huán)(4環(huán)和6環(huán))就顯得十分重要［23］.由于EBF是隨機構(gòu)造方法，每次填充GF(q)域上非0元素時，填充位置具有隨機性.為使校驗矩陣構(gòu)造算法具有低編碼復(fù)雜度，所構(gòu)造的校驗矩陣需具有圖1的下三角結(jié)構(gòu)，即與EBF構(gòu)造算法相比，改進的EBF算法構(gòu)造的校驗矩陣具有一定的結(jié)構(gòu)約束.在下三角區(qū)域，隨著列號的增大，非0元素可填充的位置數(shù)量逐漸減少.若填充是沿著列號由小到大依次進行，則填充下三角區(qū)域時，隨著列號的增大，可填充非0元素的位置數(shù)量越來越少，構(gòu)成4環(huán)和6環(huán)等小環(huán)的可能性越來越大，從而影響構(gòu)造算法性能.該點算法的改進主要是克服上述問題，隨著列號的減小，構(gòu)造非下三角區(qū)域時，對于每列來講，非0元素可填充的位置因無結(jié)構(gòu)束縛而有更多選擇，從而降低4環(huán)和6環(huán)等短環(huán)的形成，從而提高了改進的EBF算法的糾錯性能.

改進2 構(gòu)造校驗矩陣H的下三角部分的列時，每一列的首個GF(q)域上的非0元素必須添加在對角線的位置上，其余非0元素需添加在對角線下方.

該點對EBF算法的改進可保證所構(gòu)造的矩陣具有如圖1的下三角結(jié)構(gòu)，矩陣中的GF(q)域上非0元素或分布在對角線上，或分布在對角線下方的區(qū)域，從而可采用具有線性編碼復(fù)雜度的迭代編碼方法進行編碼，是改進EBF構(gòu)造算法較EBF算法具有更低編碼復(fù)雜度的關(guān)鍵.

改進3 按列重 (每列非0元素個數(shù))遞減的順序依次將GF(q)域上的非0元素添加到校驗矩陣H的非下三角部分的列中.

該點算法主要是保證改進的EBF算法構(gòu)造的校驗矩陣H具有更大的圍長，從而提升糾錯性能.對于校驗矩陣來說，變量節(jié)點的度反映校驗矩陣中每列非0元素的數(shù)量.對于非規(guī)則LDPC碼，每列(行)中的非0元素數(shù)不同，即列重不同.列重越大，非0元素數(shù)量越多.由于該矩陣構(gòu)造算法是逐次按列隨機構(gòu)造矩陣算法，若按照列重由小到大的順序填充非下三角區(qū)域，隨著列號的減小，每列中要填充的非0元素數(shù)量越來越多，又要保證填充的位置要滿足girth約束條件，則等價于可填充非0元素的位置數(shù)量越來越少，構(gòu)成4環(huán)和6環(huán)等小環(huán)的可能性越來越大，從而影響所構(gòu)造算法的性能.該點算法的改進主要是為了克服上述問題，構(gòu)造非下三角區(qū)域時，按照列重遞減順序添加H的每列，與列重由小到大的順序相比，隨著列號的減小，每列中非0元素的數(shù)量越來越少，在滿足girth約束條件下，每列中可選擇填充非0的位置數(shù)量要更多，從而避免4環(huán)和6環(huán)等短環(huán)的形成，因此可提高改進的EBF算法的糾錯性能.

由于隨機校驗矩陣構(gòu)造方法所構(gòu)造的校驗矩陣沒有一定的結(jié)構(gòu)性，因此本研究以式 (3)的64進制校驗矩陣H8×16為例，說明所提出的改進的EBF算法構(gòu)造出的校驗矩陣的結(jié)構(gòu)為

其中，比特節(jié)點的度分布序列為

由于構(gòu)造的矩陣具有下三角結(jié)構(gòu)，構(gòu)造時在滿足式 (4)度分布的基礎(chǔ)上，需將矩陣中最后一個比特節(jié)點的列重設(shè)為1.由式 (3)可見，最終構(gòu)造的校驗矩陣具有如圖1的下三角結(jié)構(gòu)，校驗部分對角線上的元素均為1，對角線以上的元素均為0.因此可直接利用式 (1)進行迭代編碼.

3 仿真結(jié)果及分析

圖2是BEF構(gòu)造算法中提出的改進1和改進3對改進的EBF算法的誤碼率性能的影響，即糾錯性能的影響.其中，碼率r=1/2;進制數(shù)q=64;信息位長為768 bit，即符號長為128，譯碼采用置信傳播 (belief propagation，BP)譯碼算法，為給硬件實現(xiàn)提供參考，最大譯碼迭代次數(shù)取為32，調(diào)制方式為二進制移相鍵控 (binary phase shift keying，BPSK)調(diào)制，信道為高斯白噪聲信道，比特節(jié)點服從式 (4)的度分布.圖2中的4條仿真曲線分別為采用無改進的EBF、采用改進1、采用改進3及采用本研究提出的混合改進EBF算法 (改進1和改進3同時進行)的誤碼率曲線，3種改進EBF算法構(gòu)造的校驗矩陣均滿足具有下三角結(jié)構(gòu) (滿足改進2).由圖2可見，在低信噪比(Eb/N0)的情況下，4條誤碼率曲線基本重合，表明糾錯性能基本一致，但隨著信噪比的增加，誤碼率出現(xiàn)明顯差異.改進1、改進3和混合改進的EBF算法與未改進的EBF構(gòu)造算法相比，對信噪比增益都有一定程度改善.其中，混合改進的EBF算法的編碼增益提高最顯著.當誤碼率為10－5時，有約為0.75 dB的編碼增益.

圖2 改進的EBF算法的誤碼率性能Fig.2 The bit error rate performance of improved EBF algorithm

上述4種LDPC碼編碼性能的差異是直接由構(gòu)造的校驗矩陣中短環(huán)的數(shù)量決定的.表1分別列出了4種矩陣中長度為4環(huán)和6環(huán)的數(shù)量.從表1可見，本研究提出的混合改進的EBF算法構(gòu)造的矩陣的4環(huán)和6環(huán)平均數(shù)量最小，無任何改進構(gòu)造的校驗矩陣中4環(huán)和6環(huán)的平均數(shù)量最大.從圖2可見，矩陣中的4環(huán)和6環(huán)的平均數(shù)量越少，所構(gòu)造的LDPC碼性能越佳.

表1 矩陣中的短環(huán)分布Table 1 Short loop distribution in the matrix

圖3和圖4分別顯示了EBF及改進的EBF構(gòu)造算法構(gòu)造的多進制LDPC誤碼率和誤幀率性能仿真曲線.其中，碼率r=1/2;q分別為16和64;LDPC碼的信息位長均為768 bit，即信息位的符號長度分別為192和128，譯碼采用BP譯碼算法，為給硬件實現(xiàn)提供參考，最大譯碼迭代次數(shù)取32，調(diào)制方式為BPSK調(diào)制，信道為高斯白噪聲信道，比特節(jié)點服從式 (4)的度分布.EBF構(gòu)造算法采用基于高斯消去的編碼算法，而改進的EBF構(gòu)造算法采用迭代編碼算法.從圖3和圖4可見，采用改進EBF構(gòu)造方法與直接應(yīng)用EBF構(gòu)造方法構(gòu)造出的LDPC碼的誤碼率、誤幀率曲線基本重合，表明兩個LDPC碼編碼增益基本一致，即本研究提出的改進的EBF算法與EBF算法構(gòu)造的碼字具有相同的糾錯性能.

圖3 改進的EBF與EBF構(gòu)造方法構(gòu)造的LDPC碼的誤碼率性能Fig.3 The bit error rate performance of improved EBF and EBF algorithm

圖4 改進的EBF與EBF構(gòu)造方法構(gòu)造的LDPC碼的誤幀率性能Fig.4 The frame error rate performance of improved EBF and EBF algorithm

4 編碼復(fù)雜度分析

由對EBF算法的第2點改進可知，改進的EBF算法所構(gòu)造的校驗矩陣具有下三角結(jié)構(gòu)，因而具有線性的編碼復(fù)雜度，致使改進后的EBF算法在硬件實現(xiàn)上較原EBF算法更容易.EBF算法和改進的EBF算法的編碼復(fù)雜度如表2.

表2 編碼復(fù)雜度分析Table 2 Analysis of coding complexity

其中，n為碼長;w為生成矩陣平均列重;k為信息位長.EBF算法構(gòu)造的LDPC碼的碼字可采用基于高斯消去的編碼算法，編碼復(fù)雜度由兩個部分構(gòu)成，預(yù)處理的運算復(fù)雜度為o(n3)，編碼復(fù)雜度為o(n2).而本研究提出的改進的多進制EBF構(gòu)造算法可采用具有線性編碼復(fù)雜度的迭代編碼，當w相對于n可看作很小的常數(shù)時，該編碼算法就具有線性復(fù)雜度.綜上可知，由于兩種算法的校驗矩陣結(jié)構(gòu)和采用的編碼算法不同，系統(tǒng)的復(fù)雜度也不同.我們認為，這是由于高斯消去編碼算法的復(fù)雜度取決于生成矩陣的稀疏性，雖然EBF算法構(gòu)造的LDPC碼校驗矩陣非常稀疏，但其生成矩陣的非0元素密度大，因而編碼復(fù)雜度正比于碼長的平方.本研究提出的改進多進制LDPC碼的EBF算法所構(gòu)造的校驗矩陣具有下三角結(jié)構(gòu)，因而可以使用具有線性編碼復(fù)雜度的迭代編碼算法編碼.

因此，本研究提出的改進EBF算法可在不損失LDPC碼糾錯性能的前提下，使系統(tǒng)的編碼復(fù)雜度降低至線性.

結(jié) 語

本研究基于LDPC碼的具有線性編碼復(fù)雜度的迭代編碼算法，提出了一種多進制LDPC碼的EBF構(gòu)造算法，通過改進編碼方案和校驗矩陣的構(gòu)造來降低復(fù)雜度，并分別對改進的EBF和無改進的EBF算法所構(gòu)造的多進制LDPC碼進行了計算機仿真.結(jié)果表明，該改進EBF構(gòu)造算法構(gòu)造的LDPC碼字與EBF構(gòu)造算法構(gòu)造的碼字相比，可在不損失糾錯性能的前提下，大幅降低系統(tǒng)的編碼復(fù)雜度，從而為進一步的硬件實現(xiàn)提供了理論參考.但EBF算法屬于隨機構(gòu)造LDPC碼校驗矩陣的構(gòu)造算法，雖然具有糾錯性能強于結(jié)構(gòu)構(gòu)造算法構(gòu)造的碼字的優(yōu)點，但由于構(gòu)造的矩陣具有隨機性，因此硬件實現(xiàn)復(fù)雜度高于結(jié)構(gòu)構(gòu)造算法.雖然本研究提出的改進的EBF算法結(jié)合迭代編碼算法可大大降低LDPC碼的編碼復(fù)雜度，但更適合于LDPC中短碼的硬件實現(xiàn).而對長碼的硬件實現(xiàn)，復(fù)雜度仍然較高，此時可通過犧牲LDPC碼一定的糾錯能力，采用LDPC碼校驗矩陣的結(jié)構(gòu)構(gòu)造算法結(jié)合迭代編碼算法來降低硬件實現(xiàn)復(fù)雜度.

/References:

［1］ Xue Rui，Zhao Danfeng，Xiao Chunli.Design of a receiver for LDPCC-CPM system based on Turbo principle［J］.Journal of Shenzhen University Science and Engineering，2010，27(3):301-305.(in Chinese)薛 瑞，趙旦峰，肖春麗.基于Turbo迭代算法的LDPCC-CPM系統(tǒng)接收機設(shè)計 ［J］.深圳大學學報理工版，2010，27(3):301-305.

［2］ Bennatan A，Burshtein D.Design and analysis of non binary LDPC codes for arbitrary discrete-memoryless channels ［J］.IEEE Transactions on Information Theory，2006，52(2):549-583.

［3］ Chen Chaoyu，Huang Qin，Chao Chichao，et al.Two low complexity reliability based message passing algorithms for decoding non-binary LDPC codes［J］.IEEE Transaction on Communications，2010，58(11):3140-3147.

［4］ Yu Y，Chen W.Design of low complexity non-binary LDPC codes with an approximated performance-complexity tradeoff［J］.IEEE Communications Letters，2012，16(4):514-517.

［5］ García-Herrero F，Canet M J，Valls J，et al.Serial symbol-reliability based algorithm for decoding non-binary LD-PC codes［J］.IEEE Communications Letters，2012，16(6):909-912.

［6］ Chen Xiaoheng，Lin Shu，Akella V.Efficient configurable decoder architecture for nonbinary quasi-cyclic LDPC codes［J］.IEEE Transactions on Circuits and Systems，2012，59(1):188-197.

［7］ He Kai，Sha Jin，Wang Zhongfeng.Nonbinary LDPC code decoder architecture with efficient check node processing［J］.IEEE Transactions on Circuits and Systems，2012，59(6):381-385.

［8］ Bennatan A，Burshtein D.On the application of LDPC Codes to arbitrary discrete-memoryless channels ［J］.IEEE Transactions on Information Theory，2004，50(3):417-438.

［9］ Li G，F(xiàn)air I J，Krzymien W A.Low-density parity-check codes for space-time wireless transmission［J］.IEEE transactions on wireless communications，2006，5(2):312-322.

［10］ Wang Xuepeng，Bai Baoming，Ma Xiao.A low-complexity joint detection-decoding algorithm for nonbinary LDPC-coded modulation systems［C］//Proceedings on IEEE International Symposium on Information Theory.Austin(USA):Institute of Electrical and Electronics Engineers，2010:794-798.

［11］ Guo F，Hanzo L.Low complexity non-binary LDPC and modulation schemes communicating over MIMO channel［C］//The 60th Vehicular Technology Conference.Los Angeles(USA):Institute of Electrical and Electronics Engineers，2004，60(2):1294-1298.

［12］ Arabaci M，Djordjevic I B，Xu Lei，et al.Nonbinary LDPC-coded modulation for high-speed optical fiber communication without bandwidth expansion ［J］.IEEE Photonics Journal，2012，4(3):728-734.

［13］ Arabaci M，Djordjevic I B，XU Lei，et al.Nonbinary LDPC-coded modulation for rate-adaptive optical fiber communication Without bandwidth expansion［J］.IEEE Photonics Technology Letters，2012，24(16):1402-1406.

［14］ Lin Changyu，Djordjevic I B，Zou Ding，et al.Nonbinary LDPC-coded mode-multiplexed coherent optical OFDM 1.28-Tbit/s 16-QAM signal transmission over 2000 km of few-mode fibers with mode-dependent loss［J］.IEEE Photonics Journal，2012，4(5):1922-1929.

［15］ Zhou Bo，Kang Jingyu，Lin Shu，et al.High performance non-binary quasi-cyclic LDPC codes on euclidean geometries ［J］. IEEE Transactions on Communications，2009，57(5):1298-1311.

［16］ Arabaci M，Djordjevic I B，Saunders R，et al.Nonbinary quasi-cyclic LDPC-based coded modulation for beyond 100 Gb/s transmission ［J］.IEEE Photonics Technology Letters，2010，22(6):434-436.

［17］ Chen Chao，Bai Baoming，Wang Xinmei.Construction of nonbinary quasi-cyclic LDPC cycle codes based on singer perfect difference set［J］.IEEE Communications Letters，2010，14(2):181-183.

［18］ Zhang Li，Huang Qin，Lin Shu，et al.Quasi-cyclic LDPC codes:an algebraic construction，rank analysis，and codes on Latin squares［J］.IEEE Transactions on Communications，2010，58(11):3126-3139.

［19］ Zeng Linqi，Lan Lan，Tai Yingyu，et al.Constructions of nonbinary quasi-cyclic LDPC codes a finite field approach ［J］. IEEE Transactions on Communications，2008，56(4):545-554.

［20］ Kang Jingyu，Huang Qin，Zhang Li，et al.Quasi-cyclic LDPC codes:analgebraicconstruction［J］.IEEE Transactions on Communications，2010，58(5):1383-1396.

［21］ Wang Peng，Wang Xinmei.Study of efficient encoding of LDPC codes［J］.Journal of Xidian University Natural Science，2004，31(6):934-938.(in Chinese)王 鵬，王新梅.LDPC碼的快速編碼研究 ［J］.西安電子科技大學學報自然科學版，2004，31(6):934-938.

［22］ Campello J，Modha D S.Extended bit-filling and LDPC code design［C］//IEEE Global Telecommunications Conference.San Jose(USA):IBM Almaden Research Center，2001，2:985-989.

［23］ Tarokh V，Jafarkhani H，Calderbank A R.Space-time block coding for wireless communications:performance result［J］.IEEE Journal on Selected Areas in Communications，1999，17(3):451-460.