一種搜索低碼重LDPC碼的快速算法*

張曙霞　陳海洋　蔣宇中

(海軍工程大學(xué)電子工程學(xué)院　武漢　430033)

?

一種搜索低碼重LDPC碼的快速算法*

張曙霞陳海洋蔣宇中

(海軍工程大學(xué)電子工程學(xué)院武漢430033)

摘要LDPC碼是目前已知性能與香農(nóng)限最接近的線性分組碼,其中構(gòu)造性能優(yōu)越的LDPC碼是主要的技術(shù)難點之一。構(gòu)造LDPC碼有多種方法,無論采用哪種方法,碼構(gòu)造完成以后,都需要評判構(gòu)造碼的性能。論文提出一種搜索低碼重LDPC碼的快速算法。該算法充分利用譯碼反饋信息對隨機噪聲進行控制,并配合和積算法譯碼器估計LDPC碼方案的最小碼重,可以快速判別性能較差的低碼重“劣碼”。實驗仿真表明,性能越差的低重碼所用搜索時間越少,驗證了該算法的準確性和實用性,對評判和優(yōu)化LDPC碼的設(shè)計具有重要參考價值。

關(guān)鍵詞LDPC碼; 構(gòu)造方法; 性能評判; 最小碼重

A Fast Algorithm for Searching Low Weight Code of LDPC Codes

ZHANG ShuxiaCHEN HaiyangJIANG Yuzhong

(College of Electronic Engineering, Naval University of Engineering, Wuhan430033)

AbstractLDPC code is a linear error correcting code, of which performance is closest to Shannon limit currently. Construction of LDPC code with superior performance is one of the major technical difficulties during those current research focuses. There are a variety of methods to construct LDPC code. Whichever method is used, the performance evaluation is required when the code is completed. This paper presents a fast algorithm for searching the low weight codewords of LDPC codes. The algorithm makes full use of decoding feedback information to control the random noise, and the sum-product decoder is used to estimate the minimum Hamming weight of LDPC code scheme. It can rapidly identify the low weight codewords of "bad code" with poor performance. Experimental simulation show that, the worse performance of the low weight code needs less time to be searched. The result verifies the accuracy and practicability of the algorithm which is of great reference value to the evaluation and optimization of LDPC code design.

Key WordsLDPC code, construction method, performance evaluation, minimum Hamming weight

Class NumberTN911

1引言

LDPC碼是Gallager在其博士論文[1]中第一次提出,但由于受當時電子元件計算能力和存儲設(shè)備的限制,沒有得到具體的應(yīng)用。隨著Turbo碼的研究和應(yīng)用的開展,基于網(wǎng)格和圖形的編碼逐漸受到人們的重視。MacKay和Neal在研究中發(fā)現(xiàn)LDPC碼具有逼近香農(nóng)極限的優(yōu)異性能[2],引發(fā)了對其研究的熱潮。由于具有較低的地板效應(yīng)和在高碼率時的良好性能,LDPC碼被各種通信標準選作信道編碼的碼型。

低碼率的LDPC長碼有著優(yōu)異的性能,目前越來越多的學(xué)者轉(zhuǎn)而研究中短碼的性能[3～4]。通常是對構(gòu)造出的碼組進行仿真,計算出在不同性噪比的情況下傳送碼字的誤碼率,然后根據(jù)誤碼率和性噪比的關(guān)系曲線評判碼的性能。這種方法比較精確,但是在低誤碼率區(qū)域需要計算很長時間,也不夠直觀、方便。最小距離是線性分組碼性能優(yōu)劣的重要因素,利用該信息可以有效地預(yù)測LDPC碼的性能。然而,計算線性分組碼的最小距離是一個NP完全問題[5]。針對這一問題,C. Berrou提出了錯誤脈沖法(EI)用于估計Turbo碼最小距離[6～7],其它的研究者改進該方法以適應(yīng)于LDPC碼[8]。這種方法可以有效地計算出最小距離,但很難保證估計值能最大程度逼近實際值。而且,由于使用的是突發(fā)錯誤噪聲和信息位反轉(zhuǎn)噪聲,干擾位置單一固定,并不能很好地模擬實際情況,導(dǎo)致應(yīng)用性較差。其他的研究者利用校驗矩陣的性質(zhì)[9～10]來計算最小距離,但存在方法復(fù)雜、耗時太長等缺陷。

在此基礎(chǔ)上,本文提出一種搜索低碼重LDPC碼的快速算法。該算法充分利用譯碼反饋信息對隨機噪聲進行控制,并配合和積算法譯碼器估計LDPC碼方案的最小碼重,可以快速判別性能較差的“劣碼”。

2LDPC碼的構(gòu)造方法和糾錯性能

GF(2)域上的LDPC碼是一種線性分組碼。根據(jù)線性分組碼的基本原理,校驗矩陣H決定著LDPC碼的構(gòu)造,并且在譯碼中起著重要作用。對于具有同等碼參數(shù)的LDPC碼集合,不同結(jié)構(gòu)的LDPC碼有著不同的檢錯和糾錯性能,編譯碼的復(fù)雜度也有巨大差異。因此,構(gòu)造性能優(yōu)異、編譯碼簡便的LDPC碼一直是信道編碼領(lǐng)域的研究熱點之一。

2.1LDPC碼的構(gòu)造方法

目前,LDPC碼有許多種構(gòu)造方法,可以根據(jù)校驗矩陣構(gòu)造方法的不同,將其分為兩大類:隨機構(gòu)造法和結(jié)構(gòu)化構(gòu)造法。運用代數(shù)構(gòu)造方法和組合方法等方式可以生成結(jié)構(gòu)化校驗矩陣,其生成的LDPC碼是循環(huán)碼或類循環(huán)碼,具有確定的數(shù)學(xué)結(jié)構(gòu),可以實現(xiàn)線性時間編碼和簡單譯碼。而隨機校驗矩陣基本都是通過限定條件由計算機搜索得到,沒有確定的編碼結(jié)構(gòu)。Gallager、Mackay以及Richardson等都是運用隨機方法生成稀疏矩陣,可以靈活地選擇碼字的參數(shù),具有較好的糾錯性能。但對于高碼率、中短長度的LDPC碼,運用隨機構(gòu)造法難以避免生成具有較短環(huán)長、低碼重的碼字,從而影響該碼的糾錯性能。

2.2LDPC碼的糾錯性能

差錯控制編碼的糾錯性能受多種因素的影響,其中最小環(huán)長和最小距離對碼的性能有著決定性的作用。在AWGN信道下,傳輸?shù)拇a序列經(jīng)過BPSK調(diào)制后的序列為Xn=(x1,x2,…,xn),接收序列為Rn=(r1,r2,…,rn),均值為0方差為σ2的高斯噪聲序列為Nn=(n1,n2,…,nn),則有:

ri=xi+ni

(1)

譯碼器采用ML譯碼,則成對錯誤率為

(2)

(3)

其中,Eb/N0為單位比特能量與噪聲能量之比,R=k/n為碼率。由聯(lián)合界可得誤碼字錯誤概率上界:

(4)

式中,dmin為最小漢明距離,Ad是漢明距離為d的碼字錯誤事件個數(shù)。為了通過線性碼的重量分布來表示性能界,引入重量枚舉函數(shù):

(5)

Ai為漢明距離為i的碼字數(shù)量。則誤字率上界可以表示為

(6)

3搜索低碼重LDPC碼的快速算法

3.1不可檢的差錯與最小重量

差錯控制編碼的檢錯和糾錯能力與其最小距離直接相關(guān)。為了簡化模型,假設(shè)在二進制對稱信道(BSC)中,接收端的接收序列表示為

ri=xi+e

(7)

式中,e為二進制差錯矢量。差錯圖案的伴隨式s可以表示為

s=yHT=xiHT+eHT=eHT

(8)

在使用最大似然譯碼時,所有可能的差錯圖案中,碼重最小的差錯圖案所對應(yīng)的陪首級與接收序列的和即為所譯碼字。但是,當一個具有最小碼重的差錯圖案可能把一個碼字轉(zhuǎn)變?yōu)榱硪粋€碼字,即為不可檢的差錯。當這種情況發(fā)生時,兩個碼字之間的距離為最小距離。

對于(n,k)的LDPC碼,將每個碼字映射到n維空間的點,共有2k個。在以碼字對應(yīng)的點為中心,漢明距離R為半徑的球里內(nèi),包含了所有與該碼字距離小于漢明距離的可能接收序列。對于任何落在球內(nèi)的接收碼字都會被譯為中心點對應(yīng)的碼字。當2R≥dmin時,接收碼字將譯為另一個碼字,即出現(xiàn)不可檢的差錯。

3.2搜索低碼重LDPC碼的快速算法

根據(jù)線性分組碼的特性,LDPC碼碼字的最小距離等于非零碼字的最小重量。為了便于實現(xiàn),可以通過計算最小重量來獲得碼的最小距離。對于短碼,可以使用窮盡搜索的方法。但對于長碼,暴力搜索顯然不行。根據(jù)以上原理,利用譯碼中出現(xiàn)的不可檢的差錯與LDPC碼的最小重量之間的關(guān)系,設(shè)計出一種搜索低重碼的快速算法,如圖1所示。

圖1　搜索低碼重LDPC碼的快速算法流程圖

在發(fā)送端發(fā)送全零碼字0,根據(jù)譯碼反饋信息調(diào)整噪聲,當出現(xiàn)譯碼碼字為非零碼字時,即出現(xiàn)不可檢的差錯。此時的該非零碼字的重量與該類碼的最小重量近似。最小重量在該非零碼重量附近波動,在此方向一定范圍內(nèi)控制噪聲激勵的大小和方向,找出發(fā)生不可檢差錯的碼字重量的最大值和最小值,二者的均值可以近似為該碼型的最小重量。

4仿真結(jié)果與分析

為了評估上文提出的低碼重LDPC碼字快速搜索算法的性能,進行了仿真實驗。這里采用經(jīng)典的MacKay隨機構(gòu)造碼作為實驗測試碼型,碼率為1/2。為了排除具有較小最小環(huán)長碼型的干擾,在構(gòu)造校驗矩陣之后,對其進行檢驗并剔除4環(huán)。實驗中,運用Box-Muller方法產(chǎn)生隨機數(shù),進而將根據(jù)譯碼反饋信息變化的高斯白噪聲作為激勵噪聲。實驗仿真程序在計算機上(雙核:2.30GHz、2.29GHz,內(nèi)存:4G)運行,并記錄仿真結(jié)果。

表1　不同參數(shù)構(gòu)造的LDPC碼仿真結(jié)果

表1中的運行時間為從程序開始運行到成功譯出非0碼字的總時間。根據(jù)這一結(jié)果,最小重量越小的LDPC碼,搜索算法用時越短。仿真結(jié)果中的誤碼率是成功譯出非0碼字時的幀錯誤率。當最小重量較小時,在低誤碼率的情況下就出現(xiàn)不可檢的差錯。隨著最小重量的增加,出現(xiàn)不可檢的差錯的概率越來越小,不可檢的差錯出現(xiàn)時的誤碼率越來越大。因此,具有低重碼的LDPC碼出現(xiàn)不可檢的差錯的概率較大,糾錯性能比較差。值得注意的是,用本文提出的搜索算法計算經(jīng)典的Mackay(504,252)碼,得到最小重量為20,用時1676.676s。這同X.Y.Hu和B.Keha等的實驗結(jié)果[8,11]相吻合,也驗證了本文算法在估計LDPC碼性能方面的準確性。

圖2　不同參數(shù)構(gòu)造的LDPC碼在AWGN信道下誤碼率性能對比

為了更好地比較不同最小重量LDPC碼的性能,同時記錄了幀錯誤率和信噪比的關(guān)系曲線,如圖2所示。當性噪比達到一定值時,最小碼重較大的LDPC碼的誤碼率曲線出現(xiàn)瀑布區(qū),誤碼率迅速下降。而最小碼重較小的LDPC碼的誤碼率曲線始終變化緩慢,并且在信噪比很低的時候就出現(xiàn)錯誤平臺現(xiàn)象。在不同性噪比情況下,最小碼重大的碼型的編碼增益始終大于最小碼重小的碼型。即LDPC碼的最小重量越小,糾錯性能越差,這與表1中的實驗結(jié)果完全吻合。

實驗結(jié)果表明,本文算法的運行時間、LDPC

碼的性能和最小重量呈現(xiàn)一致性的關(guān)系。即LDPC碼的最小重量越小,其性能越差,搜索算法運行時間越短。因此,在構(gòu)造完LDPC碼后,可以運用本文的算法搜索低重碼,以剔除劣碼,提高編碼的性能。在通常情況下,具有同等參數(shù)的長碼比短碼糾錯性能更好。由于實驗采用的是隨機碼,有的長碼性能比短碼還要差,例如(128,64)碼。因而,檢驗并搜索出低重碼對LDPC碼的構(gòu)造有重要意義,特別是對隨機構(gòu)造法而言顯得尤為重要。

5結(jié)語

本文提出一種搜索低碼重LDPC碼的快速算法,該算法利用噪聲激勵的方法配合和積算法譯碼器估計LDPC碼方案的最小碼重。根據(jù)程序運行時間或最小碼重的估計值,可以快速判別性能較差的“劣碼”。實驗仿真表明,該方法可以有效地估計出LDPC碼的最小漢明距離,性能越差的低重碼所用搜索時間越少,這對分析和優(yōu)化LDPC碼設(shè)計具有重要意義。

參 考 文 獻

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

[2] MacKay D J C, Neal R M. Near Shannon limit performance of low density parity check codes[J]. Electronics Letters,1996,32(18):1645-1646.

[3] Di C, Proietti D, Telatar I E, et al. Finite-length analysis of low-density parity-check codes on the binary erasure channel[J]. Information Theory, IEEE Transactions on,2002,48(6):1570-1579.

[4] Ashrafi R A, Sariduman A, Pusane A E. Asymptotic and finite-length performance of irregular spatially-coupled codes[C]//Communications and Networking(BlackSeaCom), 2014 IEEE International Black Sea Conference on. IEEE,2014:116-120.

[5] Vardy A. The intractability of computing the minimum distance of a code[J]. IEEE Transactions on Information Theory,1997,43(6):1757-1766.

[6] Berrou C. Some clinical aspects of turbo codes[C]//International Symposium on Turbo Codes,(Brest, France),1997:26-31.

[7] Berrou C, Vaton S, Jezequel M, et al. Computing the minimum distance of linear codes by the error impulse method[C]//Global Telecommunications Conference, 2002. GLOBECOM’02. IEEE. IEEE,2002,2:1017-1020.

[8] Hu X Y, Fossorier M P C, Eleftheriou E. On the computation of the minimum distance of low-density parity-check codes[C]//Communications, 2004 IEEE International Conference on. IEEE,2004,2:767-771.

[9] 李韻姣,葉凡,任俊彥.準循環(huán)LDPC碼最小漢明距離的計算與校驗矩陣的改善[J].微電子學(xué)與計算機,2010(6):118-121.

[10] 林燈生,李少謙.幾種LDPC碼的最小漢明距離的計算[J].電子學(xué)報,2007,35(S1):69-73.

[11] Keha A, Duman T M. Minimum distance computation of LDPC codes using a branch and cut algorithm[J]. Communications, IEEE Transactions on,2010,58(4):1072-1079.

中圖分類號TN911

DOI:10.3969/j.issn.1672-9730.2016.02.012

作者簡介:張曙霞,女,副教授,碩士生導(dǎo)師,研究方向:通信技術(shù)。陳海洋,男,碩士研究生,研究方向:通信理論與技術(shù)。蔣宇中,男,教授,博士生導(dǎo)師,研究方向:通信信號處理、低頻大氣噪聲。

*收稿日期:2015年8月3日,修回日期:2015年9月25日