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

張曙霞　陳海洋　蔣宇中

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

?

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

張曙霞陳海洋蔣宇中

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

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

關鍵詞LDPC碼; 構造方法; 性能評判; 最小碼重

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]中第一次提出,但由于受當時電子元件計算能力和存儲設備的限制,沒有得到具體的應用。隨著Turbo碼的研究和應用的開展,基于網格和圖形的編碼逐漸受到人們的重視。MacKay和Neal在研究中發現LDPC碼具有逼近香農極限的優異性能[2],引發了對其研究的熱潮。由于具有較低的地板效應和在高碼率時的良好性能,LDPC碼被各種通信標準選作信道編碼的碼型。

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

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

2LDPC碼的構造方法和糾錯性能

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

2.1LDPC碼的構造方法

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

2.2LDPC碼的糾錯性能

差錯控制編碼的糾錯性能受多種因素的影響,其中最小環長和最小距離對碼的性能有著決定性的作用。在AWGN信道下,傳輸的碼序列經過BPSK調制后的序列為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為碼率。由聯合界可得誤碼字錯誤概率上界:

(4)

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

(5)

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

(6)

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

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

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

ri=xi+e

(7)

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

s=yHT=xiHT+eHT=eHT

(8)

在使用最大似然譯碼時,所有可能的差錯圖案中,碼重最小的差錯圖案所對應的陪首級與接收序列的和即為所譯碼字。但是,當一個具有最小碼重的差錯圖案可能把一個碼字轉變為另一個碼字,即為不可檢的差錯。當這種情況發生時,兩個碼字之間的距離為最小距離。

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

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

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

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

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

4仿真結果與分析

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

表1　不同參數構造的LDPC碼仿真結果

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

圖2　不同參數構造的LDPC碼在AWGN信道下誤碼率性能對比

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

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

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

5結語

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

參 考 文 獻

[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] 李韻姣,葉凡,任俊彥.準循環LDPC碼最小漢明距離的計算與校驗矩陣的改善[J].微電子學與計算機,2010(6):118-121.

[10] 林燈生,李少謙.幾種LDPC碼的最小漢明距離的計算[J].電子學報,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

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

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