低密度奇偶校驗碼構(gòu)造及編譯碼研究進展

張用宇,吳東偉,左麗芬,劉 冰

(解放軍91469 部隊,北京100841)

1 引 言

回顧60 多年來編碼領(lǐng)域的發(fā)展,低密度奇偶校驗(Low-Density Parity-Check,LDPC)碼和Turbo 碼是到目前為止在糾錯編碼領(lǐng)域中最具代表性的成果。LDPC 碼是繼Turbo 碼之后的又一重大進展,也是目前距離Shannon 限最近的糾錯碼,是當今信道編碼領(lǐng)域的研究熱點之一。

1962 年,Gallager 在其博士論文中首次提出了LDPC 碼[1],并在論文中提出了兩種遞歸概率譯碼算法,但是由于當時計算機運算能力水平的限制,未能證明其具有接近Shannon 限的能力。Gallager 提出了兩個具有創(chuàng)造性的觀點[1]:一是用簡單稀疏校驗矩陣的隨機置換和級聯(lián)來模擬隨機碼;二是采用迭代譯碼的方法逼近最大似然譯碼。由于當時RS 碼和卷積碼的級聯(lián)被認為非常適于實際的差錯控制系統(tǒng),致使Gallager 的工作被忽視了近30 年,在此期間,Zyablov、Pinsker、Margulis 以及Tanner 仍然還致力于LDPC 碼的研究。直到Turbo 碼提出以后,人們才發(fā)現(xiàn)Turbo 碼實質(zhì)上就是LDPC 碼的一個特例,LDPC 碼又重新燃起了人們的興趣。1996 年,Mackay 等人的研究使LDPC 碼的研究跨入了一個新階段[2],他指出LDPC 碼可以像Turbo 碼一樣接近Shannon限。2001 年,Sae -Young Chung 將密度演化算法進行簡化,提出一種高斯近似(Gaussian Approximation,GA)的近似算法[3],將原來無限維的密度迭代計算轉(zhuǎn)化為一維的高斯期望計算,提高了求取LDPC 碼門限值的速度,在AWGN 信道下進行二進制傳輸,碼率為1/2 的最好不規(guī)則LDPC 碼的門限值距離Shannon 限僅僅0.004 5 dB, 仿真結(jié)果顯示, 碼長為107時,在誤比特率(Bit Error Rate,BER)為10-6的情況下,離Shannon 限的距離低于0.04 dB,這一結(jié)果超過了Turbo 碼。在近十幾年里,對LDPC 碼的研究主要集中于以下4 個方面[4]:校驗矩陣的構(gòu)造、編譯碼算法的優(yōu)化、性能分析和優(yōu)化設(shè)計以及LDPC 碼在實際系統(tǒng)中的應(yīng)用。本文對二進制和多進制LDPC碼的關(guān)鍵技術(shù)從構(gòu)造、編碼和譯碼3 個方面進行了系統(tǒng)歸納和詳細探討,總結(jié)了目前已取得的最新成果,為進一步研究提供了思路。

2 校驗矩陣的構(gòu)造

2.1 二進制校驗矩陣構(gòu)造方法

LDPC 碼的結(jié)構(gòu)決定了碼的性能,同時也決定了編譯碼方案的選擇和復(fù)雜度。LDPC 碼的校驗矩陣具有兩種形式:隨機化結(jié)構(gòu)和結(jié)構(gòu)化結(jié)構(gòu)。到目前為止,有關(guān)LDPC 碼的構(gòu)造方法數(shù)不勝數(shù)。二進制LDPC 碼校驗矩陣的構(gòu)造方法主要可以分為兩大類:隨機化構(gòu)造法和結(jié)構(gòu)化構(gòu)造法。隨機化構(gòu)造法主要是按照特定的設(shè)計準則和Tanner 圖結(jié)構(gòu)、度分布、停止集等條件來搜尋滿足要求校驗矩陣。典型方法主要有1962 年Gallger 提出的Gallager 構(gòu)造法[1],其基本思想是第一個子矩陣采用滿足要求的固定設(shè)置,其余矩陣是第一個子矩陣的隨機列重排。1997年,Mackay 在Gallager 的基礎(chǔ)上給出了幾種校驗矩陣的隨機構(gòu)造方法,使Tanner 圖中短環(huán)的數(shù)量最少,為了保證線性時間編碼復(fù)雜度,將校驗矩陣的構(gòu)造強制為下三角陣的形式[2],但是這種約束太強,必然破壞校驗矩陣的girth 約束和變量節(jié)點及校驗節(jié)點的度數(shù)約束,從而導(dǎo)致性能下降。2001 年,Yongyi Mao 和Amir Banihashemi 提出一種通過girth 分布在碼字集合中尋求好碼的啟發(fā)式方法,Jorge Campello提出了具有啟發(fā)式的比特填充(Bit-Filling)算法,Xiaoyu Wu 提出了一種漸進邊增長(Progressive Edge Growth,PEG)方法[5],其在變量節(jié)點和校驗節(jié)點邊逐漸增加的過程,使Tanner 圖具有最大的girth,該方法可以產(chǎn)生具有線性編碼復(fù)雜度的下三角形式校驗矩陣,也可擴展到多進制LDPC 碼的構(gòu)造上。結(jié)構(gòu)化構(gòu)造方法則是利用抽象代數(shù)、有限幾何和組合數(shù)學等數(shù)學理論構(gòu)造出具有規(guī)律可循結(jié)構(gòu)的校驗矩陣。在中、短碼長LDPC 碼的構(gòu)造上,好的結(jié)構(gòu)化構(gòu)造可能會優(yōu)于隨機化構(gòu)造;在長碼長LDPC 碼的構(gòu)造上,采用Thomas Richardson 的密度進化理論可以構(gòu)造出誤碼性能很好的校驗矩陣,結(jié)構(gòu)化構(gòu)造校驗矩陣的性能很難與隨機構(gòu)造的相媲美。但從實際角度來看,隨機化校驗矩陣缺少有規(guī)律的結(jié)構(gòu),致使LDPC碼編碼和譯碼過程變得復(fù)雜,且需要較大的存儲空間來存儲校驗矩陣,在中短碼長上隨著碼率的升高,隨機化構(gòu)造法很難保證校驗矩陣的稀疏性,也難以避免Tanner 圖中的短環(huán),構(gòu)造出好LDPC 碼也就相對更難,這些缺陷都阻礙了隨機化構(gòu)造的發(fā)展和應(yīng)用。而結(jié)構(gòu)化碼的優(yōu)勢在于矩陣存儲空間小,編譯碼時延短,具有良好的最小距離和girth 特性,易于實現(xiàn)。2001 年,Yu Kou 提出了基于有限幾何(Finite Geometries)的LDPC 碼構(gòu)造方法[6],該方法主要是利用歐氏和射影幾何中的點、線和超平面的關(guān)系,這種方法構(gòu)造出的碼已經(jīng)被美國國家航空航天局推薦在深空衛(wèi)星通信中使用。2004 年,Bassem Ammar 提出了基于平衡不完全區(qū)組設(shè)計(Balanced Incomplete Block Design,BIBD)的LDPC 碼,BIBD 設(shè)計是組合數(shù)學中組合設(shè)計的一種方法,除此之處,相關(guān)的設(shè)計還有Steiner 和Kirkman 三 重系 統(tǒng)[7]、Bose 設(shè)計、反Pasch 技術(shù)等。同年,Fossorier 提出了基于循環(huán)置換矩陣的LDPC 碼構(gòu)造方法,并給出了girth 為12 以下的充分必要條件或必要條件。2006 年,Lan Lan 提出了基于有限域(Finite Field)的LDPC 構(gòu)造方法[8],這種方法奠定了準循環(huán)LDPC 碼構(gòu)造的一種基調(diào),后續(xù)一些學者深入研究采用不同的數(shù)學方法構(gòu)造出滿足RD 約束的基矩陣。2007 年,Jun Xu 提出對LDPC碼的分解(Decomposition)和掩蔽(Masking)技術(shù)。2010 年,Jingyu Kang 提出了一種滿足RD 約束更大類構(gòu)造LDPC 碼校驗矩陣的方法,其涵蓋了Lan Lan提出的有限域的第一類方法,同年,Li Zhang 對準循環(huán)校驗矩陣進行了秩分析,并給出了基于Latin 方格校驗矩陣具體秩表達式[9]。從上述的發(fā)展可以看出,Shu Lin 課題研究小組在二進制準循環(huán)LDPC 碼上的研究做出了開創(chuàng)和突出性的貢獻,并且其研究仍在繼續(xù)。2005 年到2008 年間,華中科技大學的彭立、朱光喜等人提出了基于等差數(shù)列、斐波那契數(shù)列、二次同余序列、Q 矩陣等LDPC 碼構(gòu)造方法。2007 年,Norifumi Kamiya 提出了基于有限域仿射平面的高碼率QC LDPC 碼,并且給出了碼字的循環(huán)置換矩陣明確的秩公式,Li Zhang 對秩的分析正是來源于Kamiya 的啟示。QC LDPC 碼的構(gòu)造方法層出不窮,如中國剩余定理、二次同余序列、量子理論、整數(shù)網(wǎng)格等,但是這些方法都是采用不同的數(shù)學方式來構(gòu)造滿足RD 約束的基矩陣或是與之相關(guān)的擴展研究。

2.2 多進制校驗矩陣構(gòu)造方法

二進制LDPC 碼的構(gòu)造只需確定校驗矩陣中1(非零)的位置,多進制LDPC 碼的構(gòu)造與二進制不同,除了位置的確定,還有數(shù)值的選取。近些年來,許多學者把目光從二進制投向到多進制上。多進制LDPC 碼的構(gòu)造方法與二進制是一樣的,但為了更為明確,我們將多進制LDPC 碼的構(gòu)造方法分為3 類:隨機化構(gòu)造法、結(jié)構(gòu)化構(gòu)造法和混合構(gòu)造法。這3種構(gòu)造方法構(gòu)造出的校驗矩陣只會具有兩種形式:隨機化結(jié)構(gòu)和結(jié)構(gòu)化結(jié)構(gòu),形成隨機碼和結(jié)構(gòu)化碼。只有非零值的位置和取值兩個參數(shù)同時具有結(jié)構(gòu)化的特性時,才認為矩陣是結(jié)構(gòu)化的。多進制隨機化和結(jié)構(gòu)化構(gòu)造法的主要思路與二進制相同,混合構(gòu)造法的主要思路是在結(jié)構(gòu)化構(gòu)造的基礎(chǔ)上融入隨機化方法,比如非零值位置的選擇采用結(jié)構(gòu)化方法,數(shù)值的選取采用隨機方法,或是在結(jié)構(gòu)化構(gòu)造的基礎(chǔ)上采用隨機化方法進行處理,由此構(gòu)造的碼可能是隨機碼,也可能是結(jié)構(gòu)化碼。多進制LDPC 碼的構(gòu)造吸取了二進制發(fā)展的經(jīng)驗,大部分研究放在了結(jié)構(gòu)化構(gòu)造法上。2008 年,Lingqi Zeng 在二進制的基礎(chǔ)上提出了有限域和有限幾何的多進制QC LDPC碼構(gòu)造方法[10-11]。2009 年,Bo Zhou 提出了基于有限歐氏幾何平面和陣列掩蔽(Array Masking)技術(shù)的多進制QC LDPC 碼的構(gòu)造,其中采用的陣列掩蔽技術(shù)是在Jun Xu 基礎(chǔ)上的擴展,還提出了通過陣列分散(Array Dispersion)技術(shù)構(gòu)造的多進制QC LDPC 碼,具有很好糾正突發(fā)錯誤的能力,實驗結(jié)果表明在AWGN 信道和衰落信道下,多進制QC LDPC 碼的性能明顯優(yōu)于同碼長碼率的RS 碼。2010 年, Jingyu Kang 提出的滿足行距離(Row -Distance,RD)約束更大類QC LDPC 碼構(gòu)造方法[12],其中包括了多進制的情況。上述方法是Shu Lin 課題研究小組在多進制LDPC 碼構(gòu)造方面做出的主要工作,這些方法在繼承二進制LDPC 碼構(gòu)造方法的同時,也繼承了其優(yōu)缺點,有限幾何由于幾何結(jié)構(gòu)的固定化,構(gòu)造出的碼字數(shù)量有限,碼長碼率受限,但存在的好處在于校驗矩陣存在較多的冗余行,碼字在迭代譯碼過程中能更快地收斂;有限域法構(gòu)造的具有多進制循環(huán)置換陣列結(jié)構(gòu)的校驗矩陣具有較大的靈活性,輔以上述相關(guān)技術(shù)可以得到不同碼長、不同碼率、不同最小距離的規(guī)則和非規(guī)則多進制LDPC 碼。2008 年,北京理工大學劉珂珂、匡鏡明等人在滿足RD 約束要求基矩陣的框架下構(gòu)造了6 種多進制QC LDPC 碼。2010年,西安電子科技大學的陳超、白寶明、王新梅等人提出了基于Singer 完備差分集構(gòu)造的多進制QC LDPC 循 環(huán)碼[13],其Tanner 圖的girth 為12,最小符號Hamming 距離為6,同時也提出了基于循環(huán)最大距離可分碼的多進制QC LDPC 碼等。到目前為止,縱觀多進制QC LDPC 碼的發(fā)展,其基本思想還是停留在構(gòu)造滿足RD 約束的基矩陣上,至于如何滿足,研究學者可謂各顯神通,從數(shù)學理論的各個角度設(shè)法進行挖掘研究。

2.3 girth 對校驗矩陣構(gòu)造的影響

Tanner 圖中最短環(huán)的長度定義為girth。由于短環(huán)的存在會破壞變量節(jié)點和校驗節(jié)點信息傳遞的獨立性假設(shè),使相關(guān)信息在兩類節(jié)點之間傳遞,影響碼字的迭代收斂過程。上述消除4 環(huán)的研究成果已經(jīng)非常豐富,但是也有特例存在,Heng Tang 給出了存在4 環(huán)且性能優(yōu)良的有限幾何LDPC 碼,定性地說明了產(chǎn)生的結(jié)果與多種因素有關(guān),具體還不明確之間存在的關(guān)系。小girth 對低碼率、長度較短(103以下)的碼影響較大,消除這類碼的短環(huán)或減少其分布可以帶來明顯的性能改善,但是一味地增大girth 并不能一直提高碼字的性能。2007 年,電子科技大學的敬龍江提出了一大類基于圖形理論的無小環(huán)高度結(jié)構(gòu)化的QC LDPC 碼構(gòu)造方法,該方法通過設(shè)計一個有幾類特殊路徑的連接圖,來保證由此連接圖映射而得的校驗矩陣對應(yīng)的Tanner 圖無小環(huán)。2009年,Xueqin Jiang 和Moon Ho Lee 提出了基于歐氏幾何兩個不同維超平面的大girth 多進制LDPC 碼構(gòu)造方法,同年,也提出了基于中國剩余定理的大girth二進制QC LDPC 碼構(gòu)造方法。2010 年,Morteza Esmaeili 分別提出了采用兩配置之積girth 為8 和基于兩個循環(huán)置矩陣的斜率和斜率矩陣girth 為18 的二進制QC LDPC 的構(gòu)造[14]。

3 編碼設(shè)計

雖然LDPC 碼的校驗矩陣是非常稀疏的,但是其對應(yīng)的生成矩陣卻并不稀疏,這使得LDPC 碼面臨著一個主要瓶頸——較高的編碼復(fù)雜度和編碼時延。目前,大部分編碼算法主要是集中在二進制LDPC 碼上,專門針對多進制LDPC 碼編碼方面的研究相對較少,對于多進制LDPC 碼編碼來說,主要思想與二進制LDPC 碼相同,只是數(shù)域和運算規(guī)則有所不同。一般來說,設(shè)計LDPC 碼編碼器存在以下4種方法。

(1)傳統(tǒng)的直接編碼方法

一種直接編碼方法是從生成矩陣出發(fā),將信息位與生成矩陣相乘得到發(fā)送的碼字,其編碼的復(fù)雜度與LDPC 碼碼長的二次方成正比,而且直接編碼產(chǎn)生的生成矩陣過于稠密,存儲需要大量的空間;另一種是從校驗矩陣的角度出發(fā),采用高斯消去法(加減消元法)將校驗矩陣變?yōu)橄氯蔷仃?進而采用遞推的方式獲得校驗位。這兩種直接方法從復(fù)雜度、時延和存儲量角度來看,完全不利于工程實現(xiàn)。

(2)Richardson-Urbanke(RU)方法

2001 年,由Richardson 和Urbanke 提出的基于近似下三角矩陣的編碼復(fù)雜度接近線性[15],其基本思想是利用LDPC 碼校驗矩陣的稀疏性去減小產(chǎn)生稠密矩陣逆矩陣的尺寸,很大程度上減輕了在編碼上巨大運算量和存儲量需求。RU 方法從校驗矩陣出發(fā),只進行行列置換,不破壞校驗矩陣的結(jié)構(gòu),同時避開了采用非稀疏的生成矩陣對LDPC 碼進行編碼,充分利用了校驗矩陣稀疏的特點,是LDPC 碼一種通用的編碼方式,可應(yīng)用于任何LDPC 碼。整體計算復(fù)雜度從O(n2)降低到了O(n +g2),其中g(shù)為校驗矩陣與近似下三角矩陣之間的“距離”。然而,RU 方法的缺點也是比較明顯的。首先,RU 方法的流水線安排不合理[16],每一級流水線復(fù)雜度不同會導(dǎo)致消耗的時鐘數(shù)相差比較大,降低了硬件資源的利用效率。其次,后向遞推方法在解決了下三角非稀疏矩陣與向量乘法的同時,也引入了串行的計算結(jié)構(gòu),使得目標向量中下一個分量的求解依賴于該向量之前求得的所有分量,因此后向遞推必須逐符號串行進行,大大限制了吞吐量的提升。最后,在-1沒有被強制設(shè)計為某些特殊簡單矩陣的情況下,它與向量的乘法沒有辦法做任何簡化,這使RU算法在支持自適應(yīng)編碼時顯得力不從心。綜上所述,RU 算法只適合應(yīng)用在碼長不太長、吞吐量要求不太高、不要求自適應(yīng)編碼的場合。RU 方法只要求矩陣為非奇異稀疏矩陣,這一寬松的條件使其具有普適性,但同時也導(dǎo)致了該方法不會“隨機應(yīng)變”,對一些特殊結(jié)構(gòu)的校驗矩陣不會加以利用,可能會通過行列置換將其打亂。引入一些特殊矩陣結(jié)構(gòu)可改進RU 方法,得到更為實用的編碼算法,復(fù)雜度可達到完全線性化程度,這種改進與下述構(gòu)造特定的校驗矩陣實現(xiàn)線性化編碼的方法有交叉之處。2005年,Seho Myung 提出了一種二進制QC LDPC 碼的快速編碼方法,其校驗矩陣具有QC 形式,而且RU 算法中的 取的是單位陣,將計算校驗位的復(fù)雜度降至線性。2007 年,Sung -Eun Park 在Seho Myung 的基礎(chǔ)上提出了多進制QC LDPC 碼的有效編碼方法,其只是將 設(shè)計為GF(q)域下的單位陣,無需計算-1。2009 年,陳超、白寶明、王新梅提出了基于RU算法線性復(fù)雜度的多進制QC LDPC 碼有效編碼方法。RU 算法的改進是LDPC 編碼發(fā)展的一個分支方向,其編碼的方法及復(fù)雜度與碼的構(gòu)造密切相關(guān),比如塊LDPC 碼,分層近似規(guī)則LDPC 碼等都是采用RU 方法進行編碼。

(3)構(gòu)造特定代數(shù)結(jié)構(gòu)的校驗矩陣實現(xiàn)線性化編碼

特定結(jié)構(gòu)中一類最重要的結(jié)構(gòu)是循環(huán)或準循環(huán)結(jié)構(gòu),具有循環(huán)或準循環(huán)結(jié)構(gòu)的校驗矩陣可以得到系統(tǒng)循環(huán)陣形式的生成矩陣,僅采用簡單的移位寄存器就可以實現(xiàn)線性編碼,是QC LDPC 編碼的一種有效實現(xiàn)方式。隨著QC 結(jié)構(gòu)的流行,人們開始重新審視基于生成矩陣的編碼方法。此時的生成矩陣雖然仍是非稀疏矩陣,但是卻賦予了QC 結(jié)構(gòu)的特點,只需存儲矩陣的第一行元素即可。這種QC LDPC 碼的有效編碼方法是由Zongwang Li 于2006 年提出的[17],對于串行編碼,復(fù)雜度與校驗比特的位數(shù)成正比;對于高速的并行編碼,復(fù)雜度與碼字的長度成正比。同年,Lingqi Zeng 在其博士論文中將上述二進制編碼方法擴展到多進制,實現(xiàn)了多進制QC LDPC 碼的高效編碼?；赒C 結(jié)構(gòu)的編碼算法從系統(tǒng)型生成矩陣出發(fā),計算步驟比從校驗矩陣角度出發(fā)的RU 算法顯得簡單明了。這種編碼方式可以根據(jù)實際需求控制吞吐量的大小,從串行結(jié)構(gòu)到并行乃至全并行結(jié)構(gòu)。由于通用的循環(huán)移位寄存器結(jié)構(gòu)可以為不同的LDPC 碼所共用,因此很容易就能實現(xiàn)可變碼長、可變碼率的自適應(yīng)LDPC 碼編碼。其不足之處在于,提升吞吐量所需要的代價是增加寄存器數(shù)量,兩者幾乎是呈線性關(guān)系的,難以滿足在有限資源下追求最大吞吐量的設(shè)計要求。除了重要的QC 結(jié)構(gòu),下面對其他一些用于有效編碼的典型校驗矩陣構(gòu)造方法簡要地給予介紹。2003 年,Jin Lu提出了列重為2 的LDPC 循環(huán)碼的線性編碼方法。同年,Sarah Johnson 提出了一種采用循環(huán)碼編碼方式的準規(guī)則LDPC 碼構(gòu)造方法。2006 年,Zhiyong He設(shè)計了一種具有下三角加雙對角線形式的校驗矩陣來實現(xiàn)線性遞推的編碼方式。2009 年,Norifumi Kamiya 提出了與循環(huán)最大距離可分碼相關(guān)的有效系統(tǒng)編碼方法[18],這種編碼方式的實現(xiàn)主要采用的循環(huán)碼的多項式乘除法電路。總之,基于特定結(jié)構(gòu)校驗矩陣的LDPC 碼編碼,一類方法是從校驗矩陣的角度切入,采用遞推等方式得到校驗位;一類方法則是從生成矩陣或生成多項式的角度切入,采用反饋移位寄存器或多項式乘除法電路實現(xiàn)。

(4)基于迭代譯碼的編碼方法

基于迭代譯碼的編碼方法的主要原理是,把編碼過程看成是一個編碼后碼字經(jīng)過二進制刪余信道(Binary Erasure Channel,BEC)后的置信傳播譯碼的恢復(fù)過程。具體來說,可認為編碼后碼字經(jīng)過BEC后,所有信息位均得到保留,所有校驗位均被刪除,可以采用信度傳播譯碼算法來恢復(fù)未知的校驗位。這種迭代譯碼方式簡單,主要是由于變量節(jié)點和校驗節(jié)點之間傳遞的信息只有兩種:要么知道(概率為1)要么不知道(概率為0.5)。這種方法屬于校驗矩陣的編碼方式,不足之處在于不能保證迭代編碼能夠成功得到碼字,如果所有校驗位的節(jié)點組成的子集中存在停止集,迭代編碼很容易陷入其中。2002年,David Haley 受譯碼方式的影響,提出了LDPC 碼的迭代編碼方法,在有限的迭代次數(shù)下,采用Jacobi方法實現(xiàn)低復(fù)雜度編碼,而且可以與譯碼共用同一電路結(jié)構(gòu)。2007 年,Mohamed Shaqfeh 和Norbert Goertz 提出了一種基于迭代譯碼的改進編碼算法,這種算法對校驗矩陣刪除相關(guān)行并添加很少的新行,以使得迭代算法不會陷入到停止集中,這種編碼復(fù)雜度是近似線性的,因為引入的新行是非稀疏的。目前,該類LDPC 碼編碼方法只應(yīng)用于二進制,多進制上還未有發(fā)展。

從上述編碼方法來看,通用的方法適用范圍廣,可用于所有的LDPC 碼編碼,與碼的具體構(gòu)造基本上沒有關(guān)系,其復(fù)雜度較高;而校驗矩陣具有特定結(jié)構(gòu)的LDPC 碼則會充分利用其結(jié)構(gòu)特性,把編碼過程的復(fù)雜度盡量降至最低,但是其可擴展性不強。

4 譯碼算法

衡量LDPC 碼譯碼方法的指標主要有:誤碼性能、計算復(fù)雜度、譯碼延遲、存儲容量,其中誤碼性能和計算復(fù)雜度是衡量的兩個最重要指標。根據(jù)實際需求的不同會有不同的LDPC 碼迭代方法,但是基本原理是相通的:在表示Tanner 圖中的變量(符號或比特)節(jié)點和校驗節(jié)點之間反復(fù)交換和更新信息。如圖1 所示,無論是二進制,還是多進制,對于LDPC碼的譯碼方法,大體可分為4 類:軟判決譯碼,該算法主要是處理接收到的符號軟信息,直接利用信道輸出的信息進行迭代譯碼;硬判決譯碼,該算法是處理接收到的符號硬判決信息,譯碼端處理的接收符號集合與發(fā)送符號集合相同,都為GF(q)(q ≥2)域中的元素,不需要信道的先驗信息;基于可靠性度量的譯碼,該算法是處理接收到符號的硬判決值,而且還要利用未作硬判決的軟信息作為可靠性度量,其目的是在少量增加硬判決算法的復(fù)雜度的前提下來提高糾錯性能,是軟判決和硬判決譯碼的折衷;混合譯碼,采用上述3 類算法中的兩種及兩種以上組合而成的譯碼算法,目的是為了在誤碼性能和計算復(fù)雜度上找到不同的權(quán)衡點。

圖1 LDPC 碼的譯碼方法的分類Fig.1 Classification of decoding algorithms for LDPC codes

譯碼的任務(wù)是在已知接收碼字的條件下找出可能性最大的發(fā)送碼字作為譯碼碼字。最大似然譯碼(Maximum Likelihood Decoding,MLD)算法是在已知實際接收碼字序列的條件下使先驗概率最大的譯碼算法,該算法被認為是最好的譯碼方法,但對于LDPC碼來說,由于碼長較長,MLD 算法隨碼長呈現(xiàn)指數(shù)級增長導(dǎo)致復(fù)雜度極高而不利于實現(xiàn)。如圖1 所示,MLD 算法處于最高復(fù)雜度和最好性能的左端點上;軟判決譯碼是一種次最優(yōu)譯碼,復(fù)雜度偏高,雖取得的性能與MLD 算法有一定差距,但卻是可實現(xiàn)譯碼中性能最好的譯碼方法;硬判決譯碼主要是處理接收到碼字的硬判決值,只需簡單的實數(shù)運算和邏輯運算,以犧牲性能為代價而具有很低的復(fù)雜度,適合于信道條件較好的高速通信系統(tǒng);而介于軟、硬判決兩者之間的便是基于可靠性度量的譯碼。為了不同的目的而產(chǎn)生了兩種不同的思想,一個是從軟判決算法向下簡化,另一個是從硬判決向上優(yōu)化,這兩種思想形成了兩種截然不同的發(fā)展方向,也提供了糾錯性能和算法復(fù)雜度兩者權(quán)衡的一系列滿足于不同需求的算法;而混合譯碼算法實際上是一種組合算法,其目的和基于可靠性度量譯碼一樣,而方式卻完全不同,為了得到性能和復(fù)雜度的折衷而采用兩種或兩種以上的算法,獲取兩者的優(yōu)勢,削弱其劣勢,是算法的一種擴展手段。

4.1 二進制LDPC碼譯碼算法

二進制LDPC 碼可采用上述各種方式譯碼,第一個軟判決譯碼算法——概率譯碼方法是1962 年由Gallager 提出來的[1],從本質(zhì)上來說,與1988 年P(guān)earl 給出的信度傳播(Belief Propagation,BP)算法是一致的,只是兩者問題切入角度和應(yīng)用環(huán)境不同罷了,前者是在LDPC 譯碼時充分利用了其他比特的相關(guān)性得到最佳后驗概率,后者是在人工智能領(lǐng)域用于Bayesian 網(wǎng)絡(luò)的消息傳遞。在Mackay、Neal、McEliece、Frey 和Kschischang 等人將信度傳播算法引入到Turbo 碼和LDPC 碼之前,廣泛應(yīng)用于人工智能領(lǐng)域的信度傳播算法是不為信息理論學家所熟知的,其中Kschischang 證明了在因子圖上概率BP 算法或消息傳遞(Message Passing,MP)算法是和積算法(Sum-Product Algorithm,SPA)的特例,而這3 個概念在LDPC 碼譯碼中是等同的。由于概率BP 算法計算復(fù)雜,需耗費較多運算時間和硬件資源,表達形式也不夠簡潔,采用對數(shù)似然比(Log-Likelihood Ratio,LLR)后得到的LLR BP 算法誤碼性能不變,但具有更低的復(fù)雜度。從LLR BP 角度出發(fā),多數(shù)研究學者都致力于降低復(fù)雜度而形成從LLR BP 向下簡化的軟判決算法。在LLR BP 的簡化上,Fossorier 做了大量且系統(tǒng)的工作,1999 年,Fossorier 提出了比特節(jié)點簡化處理的APP 譯碼算法、校驗節(jié)點簡化處理的BP-Based 譯碼算法、比特節(jié)點和校驗節(jié)點同時簡化的APP-Based 譯碼算法,這類算法有屬于軟判決譯碼的簡化算法,也有屬于基于可靠性度量的譯碼算法,但都是從LLR BP 信息的近似處理著手取得性能和復(fù)雜度的權(quán)衡,其中BP-Based 軟判決譯碼算法與Wiberg 提出的最小和算法(Min -Sum Algorithm,MSA)是同一概念。2002 年,Fossorier 研究小組中的Jinghu Chen 提出了Normalized BP-Based(或記為NMS,Normalized Min -Sum)算法和Offset BP -Based(或記為OMS,Offset M in -Sum)算法, 在原有BP-Based 譯碼算法的基礎(chǔ)上引入了校正因子和偏移因子,這兩種修正的譯碼算法以少量復(fù)雜度的增加取得了接近BP 譯碼算法的性能,而兩個因子參數(shù)的選取既可以通過數(shù)值仿真手段獲得,也可以通過理論推導(dǎo)得出。總的來說,Fossorier 的貢獻主要是對LLR BP 算法的簡化,其在校驗節(jié)點、變量節(jié)點或兩者的計算上做簡化近似或修正處理形成了一系列低復(fù)雜度的軟判決譯碼算法和基于可靠性度量的譯碼算法。譯碼算法的節(jié)點消息更新策略也是譯碼中的研究熱點之一,采用串行的方式可以比并行的方式獲得更好的性能,其主要思想是改變了變量節(jié)點和校驗節(jié)點之間全并行的消息傳遞方式,采用本次迭代中已更新的節(jié)點消息及時代替前次迭代中的節(jié)點消息參與本次更新。

第一個二進制LDPC 碼硬判決譯碼算法也是由Gallager 于1962 年提出[1]并命名為比特翻轉(zhuǎn)(Bit-Flipping,BF)譯碼算法,這種硬判決譯碼算法之后被Yu Kou 進行了改進,于2001 年提出了加權(quán)比特翻轉(zhuǎn)譯碼(Weighted Bit-Flipping,WBF)算法[6],該算法加入了比特度量信息,但卻仍保持了BF 譯碼算法低復(fù)雜度的優(yōu)勢,屬基于可靠性度量譯碼。之后,許多通信學者對WBF 算法的誤碼率性能和計算復(fù)雜度加以改進。2002 年,Ahmed Nouh 提出了LDPC 碼的引導(dǎo)加權(quán)比特翻轉(zhuǎn)(Bootstrap WBF, BWBF)譯碼算法,在引導(dǎo)部分首先通過預(yù)設(shè)閾值來劃分可靠比特和不可靠比特,通過來自可靠比特的可靠校驗方程的信度傳播來重新對不可靠比特進行賦值,之后采用WBF 算法處理信息,屬混合譯碼算法,該算法在性能和復(fù)雜度上都取得了提升。2004 年, Juntan Zhang 提出了修正的加權(quán)比特翻轉(zhuǎn)(Modified WBF,MWBF)算法,該算法在WBF 的基礎(chǔ)上同時考慮了伴隨式的信息和每一比特自身包含的信息。F.Guo和L.Hanzo 提出了基于可靠率的加權(quán)比特翻轉(zhuǎn)(Re-liability Ratio based WBF,RRWBF)算法,其翻轉(zhuǎn)函數(shù)不需要任何的離線處理。次年,M ing Jiang 提出了改進的修正加權(quán)比特翻轉(zhuǎn)(Improved MWBF,IMWBF)算法。2005 年,Zhenyu Liu 提出了有限幾何碼的一種譯碼算法,在該算法中定義了一種新的翻轉(zhuǎn)函數(shù),其比特選取準則綜合考慮了不滿足校驗方程的個數(shù)和接收比特的可靠性度量,并首次提出了環(huán)路檢測和規(guī)避方法,記為LP-WBF。2006 年,Inaba 和Ohtsuki提出的引導(dǎo)的修正加權(quán)比特翻轉(zhuǎn)(Bootstrap MWBF,BMWBF)算法不僅具有低的譯碼復(fù)雜度,而且其性能都優(yōu)于WBF、MWBF 和BWBF 算法。2007 年, 吳曉富提出了并行加權(quán)比特翻轉(zhuǎn)(Parallel WBF,PWBF)算法, 在不損失性能的情況下加快了收斂速度。2009 年,吳曉富給出了不同WBF 算法和BP 算法的對偶映射關(guān)系,建立了基于可靠性度量譯碼算法和軟判決譯碼算法之間的橋梁[19]。李廣文、酆廣增提出了改進的并行加權(quán)比特翻轉(zhuǎn)算法(Improved PWBF,IPWBF),算法中融入了延遲處理方法, 將比特按照可靠性度量分為延遲處理集合和非延遲處理集合,在延遲處理集合中,只有比特輔助計數(shù)器達到某一預(yù)設(shè)閾值,才進行翻轉(zhuǎn);而在非延遲集合中,則不需延遲直接翻轉(zhuǎn)。另一種經(jīng)典的二進制LDPC 碼硬判決譯碼算法是一步大數(shù)邏輯譯碼(One -Step Majority -Logic -Decoding,OSMLD)。2009 年, Shu Lin 課題研究小組的Qin Huang 提出了基于軟可靠性度量和硬可靠性度量的兩種迭代大數(shù)邏輯譯碼算法,只需要低復(fù)雜度的邏輯運算和整數(shù)加法,其思路是從大數(shù)邏輯譯碼算法演變?yōu)榛诳煽啃远攘康淖g碼算法。

綜上所述,1962 年Gallager 給出了兩個譯碼算法發(fā)展的根節(jié)點——軟判決譯碼算法和硬判決譯碼算法。此后,Fossorier 研究小組在軟譯碼算法SPA上做了大量的簡化工作以及向下延拓了得到一些基于可靠性譯碼的算法;而Kou 則開啟了硬判決譯碼向基于可靠性譯碼算法發(fā)展的道路,引出了吳曉富、李廣文、Zhenyu Liu 和Ngatched 等人為代表在WBF算法所出的成果。如圖1 所示,二進制LDPC 碼的譯碼在各方面得到了全局性的發(fā)展,可以適用于不同通信系統(tǒng)LDPC 碼譯碼器的需求。

4.2 多進制LDPC碼譯碼算法

而多進制LDPC 碼譯碼器的發(fā)展不像二進制LDPC 碼發(fā)展那樣均衡,對于多進制LDPC 譯碼算法目前還處于發(fā)展研究階段,基本集中在軟判決譯碼算法方向。1998 年,Davey 和Mackay 在二進制SPA譯碼的基礎(chǔ)上提出了基于GF(q)(q >2)域的多進制LDPC 碼譯碼算法——QSPA,被稱為多進制經(jīng)典譯碼算法,仿真表明相比于二進制LDPC 碼,Mackay法構(gòu)造的列重不大于3 的多進制LDPC 碼可以在二進制對稱信道(Binary Symmetric Channel,BSC)和二進制高斯信道上取得更好的性能,這種算法導(dǎo)致校驗節(jié)點的計算復(fù)雜度為O(q2),正是由于這種高復(fù)雜度制約了多進制LDPC 碼的發(fā)展,因此如何降低譯碼復(fù)雜度成為多進制LDPC 碼發(fā)展的大勢所趨。在軟判決譯碼中,為減少其譯碼復(fù)雜度,對QSPA 的簡化主要從兩個分支上來進行研究:一是頻域,二是對數(shù)似然比(Log-Likelihood Ratio,LLR)域。在頻域中,2000 年,Mackay 提出了在GF(q)域上采用快速傅里葉變換(Fast Fourier Transform,FFT)的多進制譯碼算法FFT-QSPA,該算法通過FFT 轉(zhuǎn)換到頻域,從而使在校驗節(jié)點的卷積運算變成乘法運算,將計算的復(fù)雜度降低為O(q lb q),但是在FFT 和歸一化時仍需要大量的實數(shù)乘法和除法運算。2003 年,Barnault 和Declercq 采用張量表示法給出了快速譯碼算法FFT -QSPA 的實現(xiàn)步驟[20]。同年,Hongxin Song對FFT-QSPA 中變量節(jié)點和校驗節(jié)點的概率取對數(shù),變乘法運算為加法運算,提出了Log -FFT-QSPA 譯碼算法,這種算法結(jié)合了傅里葉變換和對數(shù)計算的優(yōu)勢,但其需要大量的對數(shù)和指數(shù)運算,不利于實用化,為了克服這個問題,可將對數(shù)和指數(shù)運算采用查找表(Look-Up Table, LUT)方式進行,但LUT的數(shù)量會隨著伽羅華域值以q lb q 的速度增長,只適合于伽羅華域元素較少的情況,同時LUT 的近似也會帶來誤碼性能的損失。在LLR 域中,2004 年,Henk Wymeersch 在二進制MS 譯碼算法的基礎(chǔ)上,提出了采用對數(shù)似然比的多進制LLR-QSPA,具有實現(xiàn)容易、復(fù)雜度低和數(shù)值穩(wěn)定等特點,乘法和加法運算被加法和Jacobi 對數(shù)運算所取代,但其復(fù)雜度仍為O(q2)。2007 年,David Declercq 提出了擴展最小和(Extended Min-Sum,EMS)算法[21],為減少迭代中的復(fù)雜運算,采用LLR 域的對數(shù)似然比值作為傳遞的消息,在信度傳播校驗節(jié)點上只選取一部分(nmq)有用值來計算度量值,算法具有與FFT -QSPA近似的復(fù)雜度O(nmq),而且只有實數(shù)加法運算,沒有乘法和除法運算,復(fù)雜度大大降低, 但是相對于QSPA 譯碼而言,誤碼性能有一定的損失。受二進制BP-Based 和APP -Based 譯碼算法思想的啟發(fā),加入校正因子和偏移因子給出了相應(yīng)的修正算法。之后David Declercq 在EMS 算法的基礎(chǔ)上,將上述原理同時應(yīng)用于校驗節(jié)點和變量節(jié)點,提出了低復(fù)雜度、低存儲容量的EMS 算法,具有O(nmlb nm)的復(fù)雜度。2008 年,北京郵電大學的周偉、全子一等人在FFT-QSPA 基礎(chǔ)上,提出了減小振蕩的改進算法,使每個發(fā)生振蕩的變量節(jié)點處輸出的信息包含上次信息和當前迭代后得到的信息。同年,陳昕、全子一等人提出了部分更新策略的低復(fù)雜度譯碼算法,對高可靠性的變量節(jié)點停止更新,并利用高可靠性信息進行更新的同時防止低可靠性變量節(jié)點錯誤信息的傳遞。

多進制硬判決譯碼算法2010 年才出現(xiàn),其發(fā)展思路延續(xù)了二進制LDPC 碼硬判決譯碼的思路。西安電子科技大學陳超、白寶明、王新梅等人提出了多進制廣義比特翻轉(zhuǎn)(Generalized Bit Flipping,GBF)算法和修正的GBF(Modified GBF ,MGBF)算法[22],兩種算法的每一個符號都有一個整數(shù)度量值, 不同于QSPA 中傳播的實數(shù)概率值,每次迭代中對可靠的符號度量加1,最后做大數(shù)判決(或多數(shù)投票)來確定譯碼符號。GBF 和MGBF 算法的區(qū)別在于前者初始化條件直接采用了硬判決信息,而后者利用了信道軟信息值,算法都只需要有限域運算、整數(shù)加法和整數(shù)比較,屬基于可靠性度量的譯碼算法,其不足在于只針對校驗矩陣列重較大的情況。同年底,中山大學趙大源、馬嘯提出了大數(shù)邏輯可譯多進制LDPC碼的低復(fù)雜度譯碼算法[23],該算法的譯碼過程與文獻[22]提出算法一致,不同之處在于初始化選取,其采用星座圖上的歐氏距離作為初始化度量值,算法的不足之處在于只適用于大數(shù)邏輯可譯碼。Shu Lin課題研究小組的Chao-Yu Chen 提出了多進制LDPC 碼基于軟可靠性度量和硬可靠性度量的譯碼算法[24],兩種算法不同之處在于初始化信息不同,不足之處在于只適用于二進制相移鍵控(Binary Phase Shift Keying,BPSK)調(diào)制,不適用于高階調(diào)制,算法對列重很大的規(guī)則校驗矩陣更為有效。

5 結(jié)束語

本文綜述了LDPC 碼在構(gòu)造、編碼和譯碼三方面的研究情況。在構(gòu)造方面,主要存在隨機化和結(jié)構(gòu)化兩種構(gòu)造方法,目前的研究主要集中于結(jié)合代數(shù)或幾何方法的結(jié)構(gòu)化構(gòu)造方法;在編碼方面,考慮到編碼的復(fù)雜度,研究多集中于基于特定LDPC 碼結(jié)構(gòu)的線性化編碼;在譯碼方面,衍生出了軟判決、硬判決、基于可靠性度量和混合的4 類主要算法,為減小譯碼復(fù)雜度,目前多在基于可靠性度量和混合算法上進行研究。LDPC 碼作為一種先進的編譯碼技術(shù),是現(xiàn)代通信領(lǐng)域的研究熱點,雖然經(jīng)歷了十幾年的發(fā)展歷程,但仍有很多技術(shù)有待研究,特別是多進制LDPC 碼還處在發(fā)展研究階段,有更多的未知領(lǐng)域亟待探索。隨著LDPC 碼的研究不斷深入下去,將為數(shù)據(jù)傳輸質(zhì)量的提高提供可靠保證。

[1] Gallager R G.Low -density parity-check codes[ J] .IRE Transactions on Information Theory,1962,8(1):21-28.

[2] MacKay D J C.Good error-correcting codes based on very sparse matrices[ J] .IEEE Transactions on Information Theory,1999,45(2):399-431.

[3] Chung S, Jr Forney G D,Richardson T J,et al.On the design of low-density parity-check codes within 0.0045 dB of the Shannon lim it[ J] .IEEE Communications Letters, 2001, 5(2):58-60.

[4] Bonello N, Chen S, Hanzo L.Low -density parity-check codes and their rateless relatives[ J] .IEEE Communications Surveys &Tutorials,2011,13(1):3-26.

[5] Hu X,Eleftheriou E,Arnold D M.Regular and irregu lar p rogressive edge-grow th tanner graphs[ J] .IEEE Transactions on Information Theory,2005,51(1):386-398.

[6] Kou Y, Lin S,Fossorier M P C.Low-density parity-check codes based on finite geometries:A rediscovery and new results[ J] .IEEE Transactions on Information Theory,2001,47(7):2711-2736.

[7] Falsafain H, Esmaeili M.A new construction of structured binary regu lar LDPC codes based on Steiner systems with parameter t>2[ J] .IEEE Transactions on Communications,2012,60(1):74-80.

[8] Lan L,Zeng L,Tai Y Y, et al.Construction of quasi-cyclic LDPC codes for AWGN and binary erasure channels:A finite field approach[ J] .IEEE Transactions on Information Theory,2007, 53(7):2429-2458.

[9] Zhang L,Huang Q,Lin S, 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.

[10] Zeng L,Lan L,Tai Y Y,et al.Constructions of nonbinary quasi-cyclic LDPC codes:A finite field approach[J] .IEEE Transactions on Communications,2008,56(4):545-554.

[11] Zeng L, Lan L, Tai Y Y, et al.Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes:a finite geom-etry approach[ J] .IEEE Transactions on Communications,2008,56(3):378-387.

[12] Kang J, Huang Q, Zhang L, et al.Quasi-cyclic LDPC codes:An algebraic construction[ J] .IEEE Transactions on Communications,2010, 58(5):1383-1396.

[ 13] Chen C, Bai B, Wang X.Construction of nonbinary quasicyclic LDPC cycle codes based on singer perfect difference set[ J] .IEEE Communications Letters,2010,14(2):181-183.

[ 14] Esmaeili M, Gholami M.Structured quasi-cyclic LDPC codes with girth 18 and column-weight J ≥3[ J] .International Journal of Electronics and Communications,2010, 64(3):202-217.

[ 15] Richardson T J,Urbanke R L.Efficient encoding of lowdensity parity-check codes[ J] .IEEE Transactions on Information Theory,2001, 47(2):638-656.

[ 16] Zhang H,Zhu J, Shi H,et al.Layered approx-regu lar LDPC:code construction and encoder/decoder design[ J] .IEEE Transactions on Circuits and Systems I,2008,55(2):572-585.

[ 17] Li Z, Chen L, Zeng L,et al.Efficient encoding of quasicyclic low-density parity-check codes[ J] .IEEE Transactions on Communications, 2006,54(1):71-81.

[ 18] Kam iya N,Sasaki E.Efficient encoding of QC-LDPC codes related to cyclic MDS codes[ J] .IEEE Journal on Selected Areas in Communications,2009,27(6):846-854.

[ 19] Wu X, Ling C, Jiang M, et al.New insights into weighted bit-flipping decoding[ J] .IEEE Transactions on Communications, 2009, 57(8):2177-2180.

[ 20] Barnau lt L,Declercq D.Fast decoding algorithm for LDPC over GF(2q)[ C]//Proceedings of IEEE Information Theory Workshop.Paris,France:IEEE,2003:70-73.

[ 21] Declercq D,Fossorier M.Decoding algorithms for nonbinary LDPC codes over GF(q)[ J] .IEEE Transactions on Communications,2007,55(4):633-643.

[ 22] 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.

[ 23] Zhao D,Ma X,Chen C,et al.A low complexity decoding algorithm for majority-logic decodable nonbinary LDPC codes[J] .IEEE Communications Letters,2010,14(11):1062-1064.

[24] Chen C,Huang Q,Chao C, et al.Two low-complexity reliability-based message -passing algorithms for decoding non-binary LDPC codes[J] .IEEE Transactions on Communications,2010,58(11):3140-3147.