LDPC 低密度奇偶校驗碼的軟判決譯碼算法淺析(一)
本系列文章列表：
LDPC 低密度奇偶校驗碼的軟判決譯碼算法淺析(二)--降低運算量
LDPC 低密度奇偶校驗碼的軟判決譯碼算法淺析（三）--算法和代碼
LDPC 軟判決算法之似然比形式 (三) tanh-lambda 規(guī)則
-----------------------------------------------------
本篇文章目的是簡單易懂地介紹 LDPC 碼的軟判決譯碼。本人在開始學習 LDPC碼時遇到最大的困惑是軟判決譯碼中 “消息傳播”? ，很多書一上來就給出 “消息傳播” 算法的具體描述，可為什么 “消息傳播” 算法是那個流程，為什么能起作用？其背后有原理（數(shù)學原理）支撐嗎？鮮有耐心詳細的說明的，幸好，我挖掘到一本書 [1]，介紹得比較好，本文就是以這本書的內容為藍本寫就的.
本人在嗶站上錄制了一個視頻，做了簡單講解：
https://www.bilibili.com/video/BV1AT411u7WJ/
在讀者已經了解線性分組碼的基本概念，以及校驗矩陣的基礎上，有概率方面的基本知識，就可以讀懂本篇文章。建議讀者在閱讀本篇文章前，閱讀一下本人寫的關于比特翻轉譯碼算法，可以領會一下背后的思想，對理解本篇文章有幫助。當然，不閱讀比特翻轉譯碼算法的文章，也完全可以理解本篇文章。
假設 LDPC 用的校驗矩陣如下，本篇文章都是以這個校驗矩陣為例子。
我們譯碼出來的碼字表示成向量形式：
這個譯碼出來的碼字，不是指發(fā)送的正確的碼字，是表示我們待譯碼出來的，例如，我們可能想評估?? 的可能性（概率）。
我們把接收到的數(shù)據(jù)表示為一個向量：
特別說明一下，這里講的接收的數(shù)據(jù)，并不是已經硬判決出來的 0 或者 1 ，而是通過信道傳輸過來后的小數(shù)。發(fā)送端發(fā)送的是 0 或者 1 ，但是，由于信道噪聲的干擾，收到的數(shù)據(jù)是各種可能，從負無窮到正無窮都是有可能的，只是越偏離原始發(fā)送的數(shù)據(jù)則可能性越小而已，假如發(fā)送的是 1，則收到是 105.7 的可能性要比收到 1.1 的可能性要小得多。例如，可能收到的數(shù)據(jù)如下：
根據(jù)信道的特點，例如是高斯白噪聲信道，我們根據(jù)接收到的上面的那些小數(shù)，可以計算出一個后驗概率，例如，可以計算出：在收到? 的條件下，
的概率，寫成概率公式為：
用? 表示這種后驗概率。
如果我們直接用這個后驗概率來判決? 還是
，則沒有利用碼字內部各個比特之間是有關聯(lián)的，那就沒有使用編碼帶來的好處。
那么，有哪些關聯(lián)的性質呢？即有哪些約束條件的？
根據(jù)線性分組碼相關的原理，我們知道有如下的校驗方程：
計算后的結果 z ，是一個含有5個元素的向量，記為：
為了易于理解，我們把上面這個矩陣形式的方程，展開成 5 個校驗方程：
如果譯碼正確，則所有的方程都是等于 0 的。如果不是正確的碼字，則上面的校驗方程中至少有一個是不等于 0 的。
由于軟判決沒有直接判決出碼字，然后來檢驗校驗方程是否滿足。使用軟信息，咱們來判斷各個校驗方程成立的概率，然后有了各個方程是否成立的概率，來計算碼字中各個比特? 等于 0 或者等于 1 的概率。
咱們一點點來推導。
咱們知道，最佳譯碼是找下面這個概率最大的：
說明：? 是 所有的校驗方程都成立的意思。
例如：在滿足校驗方程和收到的數(shù)據(jù)為 r 的條件下
則可以計算概率
注意：上面公式中 r 是含有 10 個元素的向量，是接收到的數(shù)據(jù)。
那么，把所有滿足校驗方程的 c 都計算一遍上式的概率，在這些概率中選擇最大的那個作為譯碼結果。
缺點：如果分組碼中每個組中數(shù)據(jù)比特數(shù)量是 k, 編碼后的長度為 n (例如上面例子中 k= 5, n = 10)，則需要計算? 個概率出來，對于分組碼長度為幾百這種量級的，則這個計算量非常非常大，完全不可行。因此，需要一種折中的快速算法。
第一種折中，咱們先按照單個比特最優(yōu)的角度來開始，咱們求解下面的概率：
對于二進制的傳輸數(shù)據(jù)，上面公式中的 x 要么取 0，要么取 1.
咱們對上面的公式進行一些推導，推導成這個概率是用? 的概率來表示，即用校驗方程成立的概率來表達對這個比特等于 0 或者 1 的概率。
上面的公式中，分母的部分是與 無關的項，可以認為是一個常數(shù)。
?對分子中的兩項，做進一步的簡化（其實是一種近似）
第一:? 令 即假設接收到的其它的數(shù)據(jù)(除了?
以外的)不影響?
的判決，這當然是一種簡化，因為考慮校驗方程的約束，其它數(shù)據(jù)的取值，對當前
的判斷是可以給出更多信息的。這個概率，已經與 LDPC 碼無關了，只由信道的特點決定。（有網友認為這里不是近似，因為校驗方程的條件，在公式推導過程中已經被拿掉了，好像也有道理，我寫在這里，大家自己來多思考一下吧）
第二：假設 參與的校驗方程，在?
以及收到 r 的條件下，各個校驗方程是獨立的，統(tǒng)計上獨立的。這個只有在這些校驗方程中，除了
以外，沒有其它共同參與的比特 的情況下才成立。在實際的 LDPC 碼的校驗矩陣中，是無法保證的。因此，這個也是一種簡化。 在這個假設的條件下，分子中的項可以展開為：
那么：
至此，我們已經走到了一個比較重要的步驟，或者說得到了一個比較重要的思想：
用校驗方程成立的概率，來表達或者說來計算? 的概率。這個與比特翻轉算法的思想有點類似，再比特翻轉算法中，校驗方程不成立的個數(shù)，決定了參與這些校驗方程的比特的出錯的可能性。參與到錯誤校驗方程的個數(shù)越多，這個比特出錯的可能性越大。在上面的公式中，也可以看到這個思想的影子。校驗方程成立的可能性越大，則可以看出來
的可能性就越大。
咱們舉個例子來理解上面這個公式，在前面的 LDPC 碼校驗方程中，咱們考慮正在估計? 的概率，
參與的校驗方程有?
? 這三個。
則估計 的概率可以表示成：
而上面式子中分子部分的左邊第一個概率，在假設? 相互獨立的假設下，又可以展開為三個概率的乘積：
????????????????????????????????????????????????????????-------- 例子公式(1)
=========================================================
如果至此都理解了，咱們可以開始往下推導了?，F(xiàn)在來看如何判斷校驗方程成立的概率呢？即
這個怎么計算呢？或者說如何估計呢？
咱們來解讀一下上面這個公式，這個公式是估計 成立的概率，也就是這個第 m 個校驗方程成立的可能性。我們可以很自然地理解，這個概率肯定與?
檢驗方程中包含的比特有關，又由于前面的公式是一個條件概率，其中一個條件是?
，這個是確定的。因此，評估上面這個概率，就只需要考慮這個校驗方程含有的比特，除了?
以外的那些比特。
下面，咱們做一些公式的推導，把其它參與的比特考慮進來：
首先用全概率公式：
對上面? "例子公式(1)"? 右邊的三個概率，分別都使用全概率公式展開?，F(xiàn)在對第一個( ) 展開作為例子來說明。
這個校驗方程，除了?
參與了之外，還有?
? 這 5 個比特參與，現(xiàn)在對這 5 個比特的取值進行全排列，每個取 0 或者 1，則有
種情況：
從上面舉的例子容易看出來，在? 的條件下，要求
，則可以看到上面的?
中情況中并不是都成立，只有?
? 這 5 個比特中有偶數(shù)個 1 才成立。
另外，公式(1) 中的 ，在所有?
確定的情況下，
已經與 r 無關，因此：
因此公式(1)可以寫成：
補充說明一下上面這個公式：其中的? 是取?
這個校驗方程中參與的比特，除了
。 如在例子中第一個校驗方程
，參與的比特有?
，假如?
是
，且 x=0，即
，那么?
的取值就是
. 則上面公式的右邊，需要考慮的就是?
然后，這 5 個比特的取值，就是要滿足
. 那么，上面的公式就可以展開為：
為了進一步簡化，對公式 (2) 又做了一個假設，即?? 相互獨立，則公式(2) 就可以變?yōu)椋?br>
對上面例子中的? ，假設?
相互獨立，則：
至此，公式(3) 中的??? 可以用?
來代替，顯然這里也是用了一個近似，則公式(3) 就可以計算出來，然后代入公式 (0) ，就可以計算出?
? 此時就可以對比特?
進行判決：
那么對所有的 ，都做一遍上面的流程，則?
就都判決出來了。因為，上面的計算中用了幾個假設和簡化，這次判決出來的結果代入校驗方程，可能不是所有的校驗方程都成立。那么，我們要采取一些辦法，來再做一次嘗試。如果還是按照上面的流程做一遍，那還是會得到相同的結果，我們自然可以想：能否利用上一輪估計出來的某些參數(shù)，來做這一輪的嘗試？利用上一輪的結果，把某些估計的概率能更準確一些？
咱們來看公式 (3)，對于公式 (3) 中右邊乘法的部分 ,? 在第一輪中，是用?
來近似的，這里沒有考慮?
參與的校驗方程成立的可能性，如果把這個因素考慮進去，我們可以想到，應該能提高對??
估計的準確性。因此，我們可以用下面的公式，來進一步提高估計的準確性：
因為在公式 (3) 中等號的左邊，已經是假設 ，因此上面公式中的?
要排除?
這個校驗方程。上面公式的右邊，利用公式(0) 的推導方式，又可以轉化為由
計算出來，這樣，利用第一輪計算出來的關于校驗方程成立的概率
，來遞歸循環(huán)第提高
? 的準確率。
[1]? Error Correction Coding--Mathematical Methods and Algorithms , Todd K. Moon, Wiley, 2005 ，主要參考第 15.5 章節(jié)。
