LDPC 低密度奇偶校驗(yàn)碼的軟判決譯碼算法淺析(二)--降低運(yùn)算量
本系列文章列表：
LDPC低密度奇偶校驗(yàn)碼的比特翻轉(zhuǎn)譯碼淺析
LDPC 低密度奇偶校驗(yàn)碼的軟判決譯碼算法淺析(一)
LDPC 低密度奇偶校驗(yàn)碼的軟判決譯碼算法淺析(二)--降低運(yùn)算量
LDPC 低密度奇偶校驗(yàn)碼的軟判決譯碼算法淺析（三）--算法和代碼
LDPC 軟判決算法之似然比形式 (三) tanh-lambda 規(guī)則
-----------------------------------------------------
這篇文章以及對應(yīng)錄制的視頻，是對上面文章和視頻的進(jìn)一步完善。
在上面的文章和視頻中，對 LDPC 軟判決譯碼算法 的背后思想和數(shù)學(xué)公式做了一個(gè)初步的推導(dǎo)，大致明白了 LDPC 軟判決譯碼算法的流程，但是，其中還有一個(gè)細(xì)節(jié)需要進(jìn)一步優(yōu)化，這個(gè)優(yōu)化主要是為了降低運(yùn)算量的。
錄制了一個(gè)小視頻來講解這個(gè)文章：https://www.bilibili.com/video/BV1B24y1Z7BY/
本篇文章和對應(yīng)的視頻，屬于 “續(xù)集”，建議看完前面的文章和視頻后再看。
在前面的文章中，我們根據(jù)各個(gè)比特的概率，來估算各個(gè)校驗(yàn)方程成立的概率，得出如下的公式：
這個(gè)公式看起來很嚇人！
首先，這個(gè)公式的含義是計(jì)算校驗(yàn)方程成立的概率，即校驗(yàn)方程? $z_m=0$ 成立的概率，給定的條件是 第 n 個(gè) 比特的值已知，以及收到的數(shù)據(jù) r ，這里的 r 是一個(gè)向量。
其次，這個(gè)方程的右邊，涉及到的是這個(gè)校驗(yàn)方程中含有的比特取值 0 或者 1 的概率，把這些比特相關(guān)的概率做相乘及求和等動作，完成對校驗(yàn)方程成立的概率的估計(jì)。
下面還是用例子來說明比較好。
假設(shè) LDPC 用的校驗(yàn)矩陣如下，本篇文章都是以這個(gè)校驗(yàn)矩陣為例子（這個(gè)例子與前面文章的例子是相同的）。
我們譯碼出來的碼字表示成向量形式：
這個(gè)譯碼出來的碼字，不是指發(fā)送的正確的碼字，是表示我們待譯碼出來的，例如，我們可能想評估?? 的可能性（概率）。
我們把接收到的數(shù)據(jù)表示為一個(gè)向量：
?5 個(gè)校驗(yàn)方程為：
?假如我們在考慮比特 2 取值 為 1 的概率，那么上面公式 (1) 中的? 就是 n=2, x=1,?
，? 進(jìn)一步假如咱們考慮的是第一個(gè)校驗(yàn)方程，則公式 (1) 中的
，
就是一個(gè)下標(biāo)的集合，表示第 m個(gè)校驗(yàn)方程中，含有的比特的下標(biāo)，但是不包括下標(biāo) n 的。在這個(gè)具體的例子中，就是 m=1 個(gè)校驗(yàn)方程中，除了比特 n=2 之外的那些比特的下標(biāo)，
.
重寫公式(1)
求和的部分，是對所有能使第 m=1 個(gè)校驗(yàn)方程成立的那些比特，都要做一次求和，總共有以下這么多情況：
因?yàn)?了，所以，要使第 m=1 個(gè)校驗(yàn)方程成立，則其它 5 個(gè)比特，需要有奇數(shù)個(gè) 1，即?
這 5 個(gè)比特中應(yīng)該有奇數(shù)個(gè) 1.
則含有 1 個(gè) 1 的有 5 種情況：含有 3 個(gè) 1 的有 10 種情況：
含有 5 個(gè) 1 的就 1 種情況：
總計(jì) 16 種情況。
對這 16 種情況中的任何一種，都需要再做一個(gè)連乘。例如：， 需要做的連乘為：
所以，總的計(jì)算量就是 16x4=64個(gè)乘法（還有幾乎可以忽略的15個(gè)加法）：
其實(shí)，從上面的計(jì)算，我們也可以看到很多冗余的，例如上面第一個(gè)連乘和第二個(gè)連乘中，前三個(gè)元素相乘都是相同的，可以只計(jì)算一次。那么，我們?nèi)绾蝸韮?yōu)化掉這些冗余呢？牛人們推導(dǎo)出了一個(gè)簡潔的公式。
先引入一個(gè)臨時(shí)函數(shù)：
求和公式中下標(biāo)有點(diǎn)多，不容易看清楚，求和是對 x 求和，只是下標(biāo)不同，下標(biāo)為： ，以前面的例子看，這個(gè)
則：
所以，例如當(dāng) k = 3時(shí)：
其中， 表示的是?
的取值。
我們把? 中元素的個(gè)數(shù)記為 L.
那么，可以形成一個(gè)如下所示的圖：
若 (其中 x 是??
的取值)，則這種情況是被考慮到進(jìn)來的，否則，這種組合就不用考慮，不用展開連乘并參與到累加中。繼續(xù)上面的例子，因?yàn)?
， 所以 L=5.
要考慮的 ，所以，
的組合是我們需要考慮的，也就是凡是滿足?
的組合是我們需要考慮的，這就是前面 “不厭其煩” 列出來的那 16 種情況的公式表達(dá)。
下面開始推導(dǎo)關(guān)鍵的遞推公式，利用這個(gè)遞推公式，就可以簡化計(jì)算，消除計(jì)算過程中的冗余了(這里先用上面的例子來講解，最后再總結(jié)成通用的公式)
首先令
那么? ，就依賴于
的取值
然后 , 就依賴于
的取值
然后 , 就依賴于?
的取值
然后 , 就依賴于?
的取值
最后 , 就依賴于
的取值.
為了書寫方便，我們再引入一個(gè)記號? , 表示在上面圖形的第 k 步，或者說加到第 k 個(gè)數(shù)時(shí) 結(jié)果為 x 的概率。在例子中 x =1 ，那么
? 表示的是?
的概率
? 表示的是
的概率
? 表示的是?
的概率
?表示的是
的概率
? 表示的是
的概率
因?yàn)槭?從 0 開始的，所以，，即在? 0 節(jié)點(diǎn)上，等于 0 的概率是 1， 等于 1 的概率是 0.
我們來看一下：
節(jié)點(diǎn) 1 上 等于 0 的情況有兩種：
?? ??? ??? ?節(jié)點(diǎn) 0 上等于 0，且
?? ??? ??? ? 節(jié)點(diǎn) 0 上等于 1，且
則
同理：
那么：
依次類推，則：
用上面兩個(gè)式子相減：
同理可得：
其中：
把遞推公式逐級代回去，則有：
而
又有
則可以把? 都解出來。
為了書寫方便，我們令：
則解出來的結(jié)果可以表示為：
我們來看一下計(jì)算量，有 4 個(gè)乘法，6 個(gè)加減法，以及一個(gè)除以 2（可以右移實(shí)現(xiàn)），相比之前的 64 個(gè)乘法，運(yùn)算量小了很多。
前面，用具體的例子先做了一個(gè)推導(dǎo)。從具體例子的推導(dǎo)和分析中，我們可以得到更一般的遞推公式。
令：
遞推公式為：
兩式相減，則：
這個(gè)遞推公式一直推下去，則有：
那么，若 L 是? 中元素的個(gè)數(shù)，則：
前面咱們所有的推導(dǎo)，其實(shí)都隱含這一個(gè)背景條件：“就是在收到數(shù)據(jù) r 的條件下“。把這個(gè)條件加上變成條件概率，則：
另外，
則公式(2)遞推公式就推導(dǎo)為：
又因?yàn)?br>
所以，容易把? 和?
解出來。
所以，運(yùn)算量大致等于 L-1 次乘法.
這樣，我們就得到了公式 (1) 簡化算法。
