LDPC硬判決譯碼算法

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

關鍵詞: LDPC碼;硬判決

1引言

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

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

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

2 LDPC碼簡介

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

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

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

3 硬判決算法的流程

3.1 硬判決算法的思想

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

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

3.2BF的步驟

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

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

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

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

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

4 結論

LDPC碼不僅具有逼近Shannon限的良好性能，而且譯碼復雜度較低， 結構靈活，是近年信道編碼領域的研究熱點，目前已廣泛應用于深空通信、光纖通信、衛星數字視頻和音頻廣播等領域，并已成為第四代通信系統(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.