摘要: 本文介紹了低密度奇偶校驗碼(LDPC)原理，并基于LDPC硬判決譯碼算法的思想提出了一種實用的實現(xiàn)步驟。

關(guān)鍵詞: LDPC碼;硬判決

1引言

在現(xiàn)代無線通信系統(tǒng)中，信道編碼技術(shù)是提高系統(tǒng)傳輸數(shù)據(jù)可靠性的有效方法，主要是其能降低信號傳播功率和解決信號在無線傳播環(huán)境中不可避免的衰落問題。低密度奇偶校驗碼(LDPC)最初是由Gallager[1]在1962年提出的，具有逼近香農(nóng)限的性能，幾乎適用于所有信道，因此成為近年來編碼界研究的熱點。

LDPC譯碼算法本質(zhì)上都是基于Tanner圖的消息傳遞迭代解碼算法(Message Passing)[2]。算法的性能隨量化階數(shù)的增加而提高，復雜度也隨之增加。最簡單的是量化為兩階，即成為硬判決算法;當量化階數(shù)趨向于無窮時，即成為BP[3] (Belief Propagation)算法，也叫做SPA算法(Sum Product Algorithm)。

在硬判決中，采用的方法是“位翻轉(zhuǎn)”(Bit Flipping)，因此通常稱為BF[1]算法。該算法只需計算模2校驗和，并用計算結(jié)果進行判決，因此計算復雜度相當?shù)?，并且主要采用異或門和比較器，所以易于硬件實現(xiàn)。每次迭代中翻轉(zhuǎn)的比特位數(shù)稱為門限(Threshold)，通常用δ表示。和BP算法相比，BF算法的性能較差，所以BF算法一般只適合用于光纖通信等信道條件較好的情況。另外，BF算法還可用于粗略的判斷校驗矩陣H對應的LDPC碼是否具有良好的糾錯性能等。

2 LDPC碼簡介

低密度奇偶校驗碼本質(zhì)上是一種線性分組碼，它通過一個生成矩陣G將信息序列映射成發(fā)送序列，也就是碼字序列。對于生成矩陣G，完全等效的存在一個奇偶校驗矩陣H，所有的碼字序列V構(gòu)成了H的零空間，即HVT=0。LDPC 碼的奇偶校驗矩陣H是一個稀疏矩陣，相對于行與列的長度(N， M)，校驗矩陣每行、列中非零元素的數(shù)目(我們習慣稱作行重、列重，分別用j、k或ρ、γ表示)非常小，這也是LDPC 碼之所以稱為低密度碼的原因。

根據(jù)行重列重是否固定值可以將碼分為正則碼(又叫規(guī)則碼)和非正則碼(又叫非規(guī)則碼)。校驗矩陣H的構(gòu)造方法有隨機化和系統(tǒng)化兩種方法。

Gallager給出的奇偶校驗矩陣實例[1]如圖1所示。由該矩陣構(gòu)造出的是隨機的正則碼。

3 硬判決算法的流程

3.1 硬判決算法的思想

假設(shè)信道是二進制對稱信道(BSC)，信道噪聲為加性高斯白噪聲(AWGN)，噪聲均值為0，功率普密度是No/2。用BPSK調(diào)制，能量為1，編碼后序列被映射成，這里映射公式是。接收匹配濾波器的輸出作為軟判決的輸入，，。序列作為硬判決的輸入，這里

。這里先給出幾個符號的定義 :假設(shè)H是一個J行n列的校驗矩陣，用h1，h2，……，hJ表示H的各行，其中hi(1當且僅當s=0時表示接收到的碼字z是正確的，否則，在z中存在可檢測的錯誤。也就是說，當接收到的碼字中存在錯誤時，則s中必至少有一位為1。因此在譯碼的一次迭代過程中，首先根據(jù)s翻轉(zhuǎn)z中的某些比特位，得到新的z后，可以得到更新后的s，由s是否為0判斷譯碼是否正確。BF正是根據(jù)上述思想來進行迭代譯碼。

3.2BF的步驟

第一步:由接收序列z根據(jù)式(1)計算校驗和s;若s為全零，表示接收正確，停止譯碼并退出;否則轉(zhuǎn)第二步。

第二步:計算每一位碼字所對應的不滿足校驗和的校驗方程的數(shù)目，記為fi，i=0，1，……，n-1。

第三步:根據(jù)門限值δ的大小對f0，f1，……，fn-1進行相應的從大到小的排序，將排在前面第1到第δ的fi的下標放入集合F中。

第四部:將下標在F中的碼字比特進行翻轉(zhuǎn)。

第五步:重復一至四步，直至所有的校驗方程都得到滿足(此時，譯碼正確并能在第一步退出)或超過了最大的迭代次數(shù)(此時沒有能夠正確譯碼，即譯碼失敗)。

4 結(jié)論

LDPC碼不僅具有逼近Shannon限的良好性能，而且譯碼復雜度較低， 結(jié)構(gòu)靈活，是近年信道編碼領(lǐng)域的研究熱點，目前已廣泛應用于深空通信、光纖通信、衛(wèi)星數(shù)字視頻和音頻廣播等領(lǐng)域，并已成為第四代通信系統(tǒng)(4G)中的首選。

參考文獻:

[1] R.G.Gallager .Low-Density Parity-Check Codes.IRE Trans Inform Theory. IT-8:21-28， January 1962

[2] RICHARDSONT， URBANKER.The capacity of low - density parity- check codes under message - passing decoding[J ].IEEE Trans on Inform Theory ，2000 ，47 :599～6181

[3] T.Richardson， A.Shokrollahi， and R.Urbanke. Design of capacity approaching irregular codes. IEEE Trans. Inform. Theory， vol. 47， pp. 619–637， Feb. 2001.