一種多進(jìn)制LDPC碼加權(quán)符號翻轉(zhuǎn)譯碼算法*

張用宇

(中國人民解放軍91469部隊，北京 100841)

一種多進(jìn)制LDPC碼加權(quán)符號翻轉(zhuǎn)譯碼算法*

張用宇

(中國人民解放軍91469部隊，北京 100841)

提出了一種低復(fù)雜度基于翻轉(zhuǎn)規(guī)則的多進(jìn)制低密度奇偶校驗(yàn)(Low-Density Parity-Check ，LDPC)碼符號翻轉(zhuǎn)譯碼算法。為尋求有效碼字，該算法在符號向量空間迭代地更新硬判決的接收符號向量。每一次迭代只改變一個符號，其符號翻轉(zhuǎn)函數(shù)綜合考慮了不滿足校驗(yàn)式的個數(shù)和接收比特和計算出符號的可靠性度量。在高階伽羅華域中采用一種無限環(huán)路規(guī)避和翻轉(zhuǎn)符號選取方法，同時提出了翻轉(zhuǎn)規(guī)則設(shè)計方法，該設(shè)計決定了計算復(fù)雜度和差錯性能。仿真結(jié)果表明，該符號翻轉(zhuǎn)算法在幀長為150符號的16進(jìn)制LDPC碼中取得了糾錯性能和計算復(fù)雜度的有效權(quán)衡。

多進(jìn)制；低密度奇偶校驗(yàn)碼；迭代譯碼；翻轉(zhuǎn)規(guī)則

0 引 言

低密度奇偶校驗(yàn)(Low-Density Parity-Check，LDPC)碼由Gallager于1962年提出的一種基于稀疏校驗(yàn)矩陣的線性分組碼[1]，在20世紀(jì)90年代被重新發(fā)現(xiàn)并認(rèn)為是一類接近Shannon限容量的好碼[2]。自從LDPC碼的重新發(fā)現(xiàn)，其在數(shù)字通信系統(tǒng)中的構(gòu)造、編譯碼、性能分析和應(yīng)用成為了研究的熱點(diǎn)。目前，許多學(xué)者都致力于二進(jìn)制LDPC碼的研究，而對多進(jìn)制LDPC碼的研究正處在發(fā)展階段。

多進(jìn)制LDPC碼的譯碼[3]根據(jù)譯碼原理可分為四類：硬判決譯碼、軟判決譯碼、基于可靠性度量的譯碼和混合譯碼。1998年，Davey和Mackay在二進(jìn)制和積算法(Sum-Product Algorithm，SPA)譯碼的基礎(chǔ)上提出了基于GF(q)(q>2)域的多進(jìn)制LDPC碼譯碼算法QSPA[4]，被稱為多進(jìn)制經(jīng)典譯碼算法。2000年，Mackay在GF(q)域上提出了FFT-QSPA多進(jìn)制譯碼算法[5]，將計算的復(fù)雜度降低為O(qlog2q)，2007年，David Declercq提出了擴(kuò)展最小和(Extended Min-Sum，EMS)算法[6-7]，采用對數(shù)似然比值作為傳遞的信息，在信度傳播校驗(yàn)節(jié)點(diǎn)上只有一部分(nm?q)有用值參與度量值的計算，算法復(fù)雜度為O(nmq)。2010年，陳超提出了多進(jìn)制廣義比特翻轉(zhuǎn)(Generalized Bit-Flipping，GBF)算法和修正的GBF(MGBF，Modified GBF)算法[8]，分別采用信道的硬判決和軟判決信息來初始化，算法中每一個符號都采用整數(shù)度量，循環(huán)迭代中每次對可靠的符號度量值加1，最后采用大數(shù)判決的方法來確定譯碼符號，其屬可靠性度量的譯碼算法。同年，趙大源提出了大數(shù)邏輯可譯多進(jìn)制LDPC碼的低復(fù)雜度譯碼算法[9]，該算法采用星座圖上的歐氏距離作為初始化度量值，其只適用于大數(shù)邏輯可譯碼。Chao-Yu Chen提出了多進(jìn)制LDPC碼基于軟可靠性度量和硬可靠性度量的譯碼算法[10]，兩者采用不同的初始化信息，不適用于高階調(diào)制，只適用于二進(jìn)制相移鍵控(Binary Phase Shift Keying，BPSK)調(diào)制。

本文提出了一種新的具備翻轉(zhuǎn)規(guī)則的多進(jìn)制LDPC碼符號翻轉(zhuǎn)譯碼算法，當(dāng)決定某一符號需要翻轉(zhuǎn)時，可以根據(jù)翻轉(zhuǎn)規(guī)則中的翻轉(zhuǎn)順序進(jìn)行翻轉(zhuǎn)。采用具備翻轉(zhuǎn)規(guī)則的加權(quán)符號翻轉(zhuǎn)算法雖犧牲了一定的性能，但卻降低了譯碼復(fù)雜度，在誤碼性能和復(fù)雜度上找到了權(quán)衡點(diǎn)，使多進(jìn)制LDPC碼在更低的復(fù)雜度上實(shí)現(xiàn)了較好的性能。

1 一種符號翻轉(zhuǎn)譯碼算法

1.1 基本定義

考慮多進(jìn)制(N，K)LDPC碼，其中N為碼字長度，K為信息位長度。LDPC碼可以完全由稀疏的多進(jìn)制奇偶校驗(yàn)矩陣H來決定，其校驗(yàn)矩陣H有N列和M≥N-K行。對其任意嘗試的符號硬判決向量y，其伴隨式向量為s=yHT，其中所涉及的乘法和加法運(yùn)算都是在GF(q)下進(jìn)行的。校驗(yàn)矩陣H的行重為dc，列重為dv。定義N(m)表示參與第m個校驗(yàn)方程的dc個符號集合，M(n)表示參與符號n的dv個校驗(yàn)集合：

N(m)={n:hm,n≠0}，M(n)={m:hm,n≠0}

(1)

選取任一碼字c=[c1,c2,…,cN]∈{GF(q)}N，其中q=2b，在發(fā)送之前將碼字按發(fā)送信號星座圖Ω映射成雙極性向量t=[t1,t2,…,tN-1]，其中tn=[tnb,…,t(n+1)b-1]，0≤n

對于0≤i

定義GF(q)域非零元素a的對數(shù)似然比：

Ln(a)=[Ln(a=α1),…,Ln(a=αq-1)],

(2)

式中：

(3)

式中，P(a=αi)表示a取值為αi的概率。

定義GF0(q)={α1,…,αq-1}為不含零元的伽羅華域。為了便于表示，第n個符號取值為a的概率向量為Ln=[Ln,α1,…,Ln,a,…,Ln,αq-1]，其中Ln,a=∑j:ψ(a)j=+1rnb+j，a∈GF0(q)。可以看出，Ln,a是除去常數(shù)項2/σ2的Ln(a=αi)的一種表達(dá)形式。

1.2 算法描述

(4)

利用式(4)迭代可計算出E(k-1),E(k-2),…,E(0)，如果其中任意一個向量為全零，檢測到環(huán)路，則當(dāng)前選擇要翻轉(zhuǎn)的符號值就剔除。

算法開始于接收的硬判決向量y(0)，在k(k≥1)次迭代之前，符號向量為y(k-1)，對應(yīng)的伴隨式向量為s(k-1)=y(k-1)HT≠0。先計算GF0(q)上的決定翻轉(zhuǎn)符號位置的符號度量值，對于每一個符號和每一個GF0(q)的元素，

(5)

為估計出符號的可靠性度量，計算出每一個符號的度量值：

(6)

根據(jù)翻轉(zhuǎn)規(guī)則翻轉(zhuǎn)y(k-1)中的符號：

y(k)=y(k-1)⊕en(k)

(8)

表1 GF(16)下兩種不同翻轉(zhuǎn)規(guī)則

翻轉(zhuǎn)深度定義為翻轉(zhuǎn)集合中前若干個GF(q)域中的元素。當(dāng)翻轉(zhuǎn)規(guī)則確定之后，其翻轉(zhuǎn)深度可取的范圍是1到q。翻轉(zhuǎn)的深度越小，其復(fù)雜度就越低，該復(fù)雜度的降低是以翻轉(zhuǎn)深度所決定的或大或小的糾錯性能損失為代價的。綜上所述，在翻轉(zhuǎn)規(guī)則中，變量Q是以1為初始值的位置信息，翻轉(zhuǎn)深度為q′≤q，其地址范圍為一個模q′計數(shù)器。

綜上所述，提出的具有翻轉(zhuǎn)規(guī)則的譯碼算法FRWSF如下：

步驟(1) 初始化：設(shè)置迭代計數(shù)器k=0；計算y(0)，Ln和wn,m,a；排除符號列表B←?；翻轉(zhuǎn)計數(shù)器Q=1。

步驟(3)k←k+1；如果k>kmax(kmax為設(shè)定的最大迭代次數(shù))，譯碼失敗并停止譯碼。

步驟(6) 對于選出的翻轉(zhuǎn)符號，根據(jù)由Q得到的翻轉(zhuǎn)規(guī)則翻轉(zhuǎn)成另一個符號。

步驟(7) 根據(jù)式(4)計算E(l)，l=k-1,k-2,…,0；如果對于任意l=k-1,…,0，E(l)=0，則如果Q≠q，Q←Q+1，返回到步驟(6)；如果Q=q，B←B∪{n(k)}并且Q=1，返回到步驟(5)。

步驟8 根據(jù)式(7)計算y(k)；B←?；返回步驟(2)。

2 仿真結(jié)果

以SNR作為變量來衡量LDPC碼的譯碼性能，我們將研究以下譯碼算法的誤比特率(Bit-ErrorRate，BER)、誤符號率(Symbol-ErrorRate，SER)和誤幀率(Frame-ErrorRate，F(xiàn)ER)：(1)FRWSF算法；(2)FFT-QSPA；(3)RSBM算法。

如圖1所示，對(150, 76) 16進(jìn)制的有限域(FiniteField，F(xiàn)F)LDPC碼[11]進(jìn)行了研究，其碼率為0.506 7，校驗(yàn)矩陣H是一個行重列重都為9的150×150循環(huán)陣，α=1。該碼采用順序和移位翻轉(zhuǎn)規(guī)則譯碼算法(200次迭代)的糾錯性能如圖1所示。為了便于比較，也給出了LDPC碼的FFT-QSPA(200次迭代)和RS碼的BM算法的誤碼性能。

為更好地理解和表述譯碼算法，以16-ary(150,76)FFLDPC碼為例，并選擇發(fā)送全零的信息符號向量。一個長度為76的全零信息符號經(jīng)過編碼器后得到長度為150的全零碼字，碼字經(jīng)BPSK調(diào)制并經(jīng)AWGN信道，經(jīng)過硬判決，接收到由150個符號組成的碼字向量為c=[0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 4 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 8 0 1 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 8 1 0 0 0 0 4 0 0 0 0 6 0 0 0 0 0 1 0 0 2 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 5 0 0 6 0 0 0]。從接收到的硬判決向量來看，由于已知發(fā)送序列，我們知道錯誤出現(xiàn)的位置和數(shù)值，但是對于譯碼程序來說，這些信息都是未知的。表2給出了存在錯誤的符號位置以及符號中對應(yīng)發(fā)生錯誤的比特和度量值大小的排序。以第67個錯誤符號(向量c中粗體符號位置)為例，[3 1x0x2]中的0、1、2、3表示符號中比特的可靠性程度，0表示的是4個比特當(dāng)中最不可靠的比特，3表示的是最可靠的比特，符號“x”表示導(dǎo)致符號發(fā)生錯誤的比特，但這對于譯碼來說是未知的。當(dāng)傳輸符號0(0000)時，該位置接收到的硬判決值為6(0110)。FRWSF譯碼中每次迭代只翻轉(zhuǎn)一個符號，翻轉(zhuǎn)的值是由翻轉(zhuǎn)函數(shù)、接收比特軟信息和翻轉(zhuǎn)規(guī)則等共同決定，表3給出了譯碼過程中的部分迭代符號翻轉(zhuǎn)過程，其中粗體表示的是每次迭代確定出的翻轉(zhuǎn)符號位置和取值。

表2 錯誤符號位置及相應(yīng)比特狀態(tài)

表3 符號翻轉(zhuǎn)譯碼的部分迭代過程

如圖1所示，順序翻轉(zhuǎn)規(guī)則和移位翻轉(zhuǎn)規(guī)則的FRWSF算法的誤碼性能相差無幾，這是因?yàn)榇a字都是在AWGN這一類型的信道條件下傳輸?shù)摹２煌D(zhuǎn)規(guī)則的譯碼算法可以應(yīng)用到不同類型的信道上，可以獲取不同的誤碼性能。特別是在突發(fā)信道條件下，翻轉(zhuǎn)規(guī)則可以根據(jù)突發(fā)噪聲的特性進(jìn)行合理設(shè)計。在FER為10-5處，與GF(27)域上采用BM算法同比特長度的(86,44) RS碼進(jìn)行比較，F(xiàn)RWSF取得了1.07 dB左右的編碼增益。在FER為10-5處，與FFT-QSPA譯碼進(jìn)行比較，F(xiàn)RWSF距離FFT-QSPA譯碼大約1.56 dB。在5.5 dB時采用兩種不同的翻轉(zhuǎn)規(guī)則對該碼進(jìn)行譯碼的計算復(fù)雜度如表4所示，從表3可以看出，F(xiàn)FT-QSPA實(shí)數(shù)加法的計算量大約是FRWSF算法實(shí)數(shù)加法的7倍，并且FRWSF算法不需要實(shí)數(shù)乘法和實(shí)數(shù)除法，所以，F(xiàn)RWSF算法的整體計算復(fù)雜度比FFT-QSPA低很多。

圖1 16-ary (150,76) FF LDPC碼和GF(27)域

譯碼算法實(shí)數(shù)加法實(shí)數(shù)乘法實(shí)數(shù)除法順序FPWSF3336100移位FPWSF3298700FFT-QSPA22737027872725758

如圖2所示，考慮對上述碼字采用不同翻轉(zhuǎn)深度的譯碼算法。從圖2中可以看出，具有全翻轉(zhuǎn)深度和深度為10的譯碼算法誤碼性能相差不多，但是深度為10的算法復(fù)雜度略比全翻轉(zhuǎn)深度的低一些。相對于高深度(如深度為10)而言，翻轉(zhuǎn)深度為5的譯碼算法以誤碼性能為代價降低了計算復(fù)雜度。因此，在實(shí)際應(yīng)用中翻轉(zhuǎn)深度可以選擇略低于伽羅華域階數(shù)q的一個數(shù)值來取得一定的權(quán)衡。

圖2 不同翻轉(zhuǎn)深度的16-ary (150,76) LDPC碼的誤碼性能

3 結(jié) 語

本文提出了一種翻轉(zhuǎn)規(guī)則的多進(jìn)制LDPC碼加權(quán)符號翻轉(zhuǎn)譯碼算法，在譯碼過程中，根據(jù)每次迭代的翻轉(zhuǎn)函數(shù)和翻轉(zhuǎn)深度來選擇和翻轉(zhuǎn)碼字中的一個符號。算法中具有最小計算開銷的環(huán)路檢測方法不僅有利于翻轉(zhuǎn)符號的選取，也有利于防止在正確碼字搜尋過程中陷入到無限環(huán)路之中。算法不需要信號的幅度和噪聲功率等先驗(yàn)知識，翻轉(zhuǎn)的順序和深度的選擇也帶來了較大的靈活性。通過仿真結(jié)果和復(fù)雜度分析，在相對低伽羅華域下相比于RS碼，該算法在中長幀LDPC碼上取得了明顯的編碼增益，而其計算復(fù)雜度也較低。所以，提出的譯碼算法取得了很好的糾錯性能和復(fù)雜程度上的權(quán)衡。

[1] Gallager R G. Low-Density Parity-Check Codes[J]. IRE Transactions on Information Theory, 1962, 8(1): 21-28.

[2] Chung S Y, Forney G D, Richardson T J, et al. On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit[J]. IEEE Communications Letters, 2001, 5(2): 58-60.

[3] 張譽(yù)，雷菁，文磊. 多進(jìn)制LDPC譯碼算法的研究[J]. 通信技術(shù)，2011, 44(05): 21-23. ZHANG Yu, LEI Jing, WEN Lei. Research on Nonbinary LDPC Decoding Algorithm[J]. Communications Technology, 2011, 44(05): 21-23.

[4] Davey M C, Mackay D. Low-Density Parity Check Codes over GF(q)[J]. IEEE Communications Letters, 1998, 2(6): 165-167.

[5] Mackay D, Davey M. Evaluation of Gallager Codes for Short Block Length and High Rate Applications[C]. Proc. IMA International Conf. Mathematics its Application: Codes, Systems and Graphical Models. New York, 2000: 113-130.

[6] Declercq D, Fossorier M. Decoding Algorithms for Nonbinary LDPC Codes over GF(q)[J]. IEEE Transcations on Communications, 2007, 55(4): 633-643.

[7] ZHAO S, LU Z, MA X, et al. A Variant of the EMS Decoding Algorithm for Nonbinary LDPC Codes[J]. IEEE Communications Letters, 2013, 17(8): 1640-1643.

[8] CHEN C, BAI B, WANG X, et al. Nonbinary LDPC Codes Constructed based on a Cyclic MDS Code and a Low-Complexity Nonbinary Message-Passing Decoding Algorithm[J]. IEEE Communications Letters, 2010, 14(3): 239-241.

[9] ZHAO D, MA X, CHEN C, et al. A Low Complexity Decoding Agorithm for Majority-Logic Decodable Nonbinary LDPC Codes[J]. IEEE Communications Letters, 2010, 14(11): 1062-1064.

[10] CHEN C, HUANG Q, CHAO C, et al. Two Low-Complexity Reliability-based Message-Passing Algorithms for Decoding Non-Binary LDPC Codes[J]. IEEE Transcations on Communications, 2010,58(11):3140-3147.

[11] SONG S, ZHOU B, LIN S, et al. A Unified Approach to the Construction of Binary and Nonbinary Quasi-Cyclic LDPC Codes based on Finite Fields[J]. IEEE Transcations on Communications,2009,57(1):84-93.

Weighted Symbol-Flipping Decoding Algorithm for Nonbinary LDPC Codes

ZHANG Yong-yu

(Unit 91469 of PLA, Beijing 100841, China)

A low-complexity symbol-flipping algorithm for nonbinary LDPC (Low-Density Parity-Check) codes based on flipping rules is proposed. In searching of valid codeword, the proposed algorithm iteratively updates the received symbol vector of hard-decision in symbol vector space. Only one symbol is flipped in each iteration, and symbol flipping function comprehensively considers the number of failed checks and the reliability of the received bits and calculated symbols. A scheme to avoid infinite loops and select flipping symbol in high-order Galois field is adopted and meanwhile, the design of flipping rules is also proposed, which determines the computational complexity and error performance. Simulation results indicate that this algorithm could achieve an effective tradeoff of between error-correcting performance and computational complexity for the 16-ary (150,76) LDPC code.

nonbinary; LDPC codes; iterative decoding; flipping rule

10.3969/j.issn.1002-0802.2015.11.004

2015-06-08；

2015-09-28 Received date:2015-06-08；Revised date：2015-09-28

TN911.22

A

1002-0802(2015)11-1222-06

張用宇(1977—)，男，碩士，高級工程師，主要研究方向?yàn)闊o線通信系統(tǒng)。