LDPC低密度奇偶校驗碼的比特翻轉(zhuǎn)譯碼淺析
本系列文章列表：
LDPC 低密度奇偶校驗碼的軟判決譯碼算法淺析(二)--降低運算量
LDPC 低密度奇偶校驗碼的軟判決譯碼算法淺析（三）--算法和代碼
LDPC 軟判決算法之似然比形式 (三) tanh-lambda 規(guī)則
-----------------------------------------------------
LDPC碼（low-density parity-check）實際上就是一種線性分組碼，但是，由于LDPC碼的 low-density? 特性，可以用比較高效的算法來實現(xiàn)譯碼。這篇小文不是探討 LDPC 碼的方方面面，而是在讀者已經(jīng)了解線性分組碼的基本概念，以及校驗矩陣的基礎(chǔ)上，試圖對 LDPC碼中一個簡單的譯碼算法進行一個描述。在 Gallager 博士論文 [1] 中非常簡要描述了一種稱之為 Bit-Flipping 的 hard decoder 方法來譯碼。下面這段英文摘自 Gallager 博士論文 [1] :
（在嗶站本人錄制了一個小視頻，做簡單講解：
https://www.bilibili.com/video/BV1C24y1Z7Uf/ ）
......, the decoder computes all the parity checks and then changes any digit that is contained in more than some fixed number of unsatisfied parity-check equations. Using these new values, the parity checks are recomputed, and the process is repeated until the parity checks are all satisfied.?
下面舉個例子來具體說明這個過程。
假設(shè)校驗矩陣是：
把接收到的碼字表示為一個向量：
則根據(jù)收到的碼字 ，可以計算出伴隨式 syndrome（這個詞在醫(yī)學里面是癥狀的意思，在這里，可以理解為用來“診斷”接收到的碼字是否有錯誤，以及診斷哪些校驗方程是沒有被滿足的）：
計算后的結(jié)果 ，是一個含有5個元素的向量，記為：
為了易于理解，我們把上面這個矩陣形式的方程，展開成 5 個校驗方程：
現(xiàn)在，我們舉一個具體的例子，發(fā)送一個碼子，接收到的碼字有一個錯誤，用 bit-flipping 算法做一個譯碼。
發(fā)送的碼字為：
接收到的碼字有錯誤：
可以看到? 是有錯誤的。下面，用 bit-flipping 算法，嘗試做一個譯碼：
第一步，計算出伴隨式：
?? ??? ??? ?
???????????????? 注：上面是模 2 加法， 1+1=0
第二步，看伴隨式是否都為 0 ，若都為 0 ，則結(jié)束譯碼，此時的? 就是正確的碼字；如果伴隨式不為0，跳到第三步。
第三步，看? 到
分別在哪幾個校驗方程中出現(xiàn)，在出現(xiàn)的校驗方程中，有幾個校驗方程是不滿足的，即不等于0.
?????? 出現(xiàn)在
中，其中
，因此，出現(xiàn)
的校驗方程中有 1 個方程不滿足；
????? 出現(xiàn)在
中，其中
，因此，出現(xiàn)
的校驗方程中有 1 個方程不滿足；
?? 以此類推，可以列出如下這個表格：
在 "不滿足的校驗方程的個數(shù)" 中選擇最大的，上表中最大的是 3 ，對應(yīng)的是? 所在的那一列，因此，把
從 1 翻轉(zhuǎn)（Flipping）成 0，接收到的碼字被翻轉(zhuǎn)后，記為新的
. 跳轉(zhuǎn)到第一步繼續(xù)執(zhí)行。
?此時的 為：
再來計算伴隨式 ，得出的結(jié)果為
譯碼結(jié)束。
正確的碼字為：
可見，與最初的發(fā)送碼字相同：
通俗來理解，這種迭代算法，就是考慮收到的碼字中的比特，如果參與的校驗方程中，越多的方程不滿足，則越說明這個比特出錯的可能性比較大，優(yōu)先對這個比特進行翻轉(zhuǎn)來嘗試。
以前一直不太理解的 sum-product 方法的思想，現(xiàn)在似乎有所領(lǐng)悟。上面是一種硬判決，如果換成軟判決，則考慮的是每個校驗方程不滿足的 “概率”，從絕對的滿足與不滿足，換成了滿足或不滿足的概率。進而來計算每個參與的比特，在各個校驗方程中，不滿足的概率，找出概率最大的那個進行某種修改。
[1]? R.G.Gallager, Low-Density Parity-Check Codes, *IRE Trans.Info.Theory*? IT-8:21-28. 1962.
