經(jīng)過前面多篇文章和視頻的講解，我們已經(jīng)清楚地了解了 LDPC 譯碼的流程和背后的邏輯思想。現(xiàn)在，我們可以引入 Tanner 圖，來為 LDPC 譯碼算法做一個(gè)圖形化的抽象和理解。我覺得，在理解了譯碼算法的流程之后，再引入 Tanner 圖，就比較容易理解 Tanner 圖的作用，有一個(gè)更清晰的圖形化的理解，方便我們記憶 LDPC 譯碼的流程。

（錄制的視頻：https://www.bilibili.com/video/BV1iY4y1u7Gi/）

我們知道，譯碼算法，不管是用 Log 形式的還是不用 Log 形式的，都有兩個(gè)主要的步驟和思想：



1）校驗(yàn)方程成立與否的概率或者某種度量

2）比特取值的概率或者某種度量



而相互迭代這兩個(gè)步驟，逐步逼近成功譯碼這個(gè)理想的目標(biāo)。所以，我們可以把步驟 1) 的結(jié)果，稱之為校驗(yàn)，則在 Tanner 圖中引入校驗(yàn)節(jié)點(diǎn)；步驟 2）的結(jié)果，稱之為數(shù)據(jù)或者比特，在 Tanner 圖中引入變量節(jié)點(diǎn)。

在這兩種節(jié)點(diǎn)之間，引入連線，規(guī)則是：某個(gè)比特參與某個(gè)校驗(yàn)方程，則在對(duì)應(yīng)的比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)之間引入連線，表示一種相互關(guān)系：比特參與校驗(yàn)方程，校驗(yàn)方程含有比特。

這個(gè)一般稱之為 Tanner 圖，也稱之為二分圖，這個(gè)圖本身，并不是算法的精確表達(dá)，而是對(duì)算法中各種角色之間關(guān)系的一種形象表達(dá)，至于這種表示的背后，還需要嚴(yán)格的數(shù)學(xué)推導(dǎo)作為支撐。即，角色之間的依賴關(guān)系是有什么樣的數(shù)學(xué)公式來描述的。



本篇文章都是以這個(gè)校驗(yàn)矩陣為例子。

我們譯碼出來的碼字表示成向量形式：

這個(gè)譯碼出來的碼字，不是指發(fā)送的正確的碼字，是表示我們待譯碼出來的，例如，我們可能想評(píng)估?? 的可能性（概率）。

我們把接收到的數(shù)據(jù)表示為一個(gè)向量：

根據(jù)線性分組碼相關(guān)的原理，我們知道有如下的校驗(yàn)方程：


計(jì)算后的結(jié)果 z，是一個(gè)含有5個(gè)元素的向量，記為：

為了易于理解，我們把上面這個(gè)矩陣形式的方程，展開成 5 個(gè)校驗(yàn)方程：

那么，用 Tanner 圖來表示這些依賴關(guān)系，可以表示成下圖：

兩種變量節(jié)點(diǎn)間的關(guān)系，可以用這個(gè)思想來描述：校驗(yàn)節(jié)點(diǎn)（校驗(yàn)方程）把自己的某種度量信息告知這個(gè)校驗(yàn)方程含有的比特對(duì)應(yīng)的變量節(jié)點(diǎn)，同理，變量節(jié)點(diǎn)也把自己取值的概率信息的某種度量也發(fā)給包含這個(gè)比特的校驗(yàn)方程對(duì)應(yīng)的校驗(yàn)節(jié)點(diǎn)。



我們之前推導(dǎo)的 LDPC 譯碼都是分兩個(gè)主要步驟在迭代：用比特的概率信息估計(jì)校驗(yàn)方程的概率信息，然后用校驗(yàn)方程的信息更新比特的概率信息。這個(gè)過程，在 Tanner 圖上來描述：變量節(jié)點(diǎn)的信息發(fā)送到與之相連的校驗(yàn)節(jié)點(diǎn)，校驗(yàn)節(jié)點(diǎn)據(jù)此計(jì)算出自己的信息，然后，校驗(yàn)節(jié)點(diǎn)把這個(gè)信息發(fā)送給與之相連的變量節(jié)點(diǎn)。

在 Tanner 圖的表示中，則問題就變成：

1）節(jié)點(diǎn)之間發(fā)送的信息，是什么樣的信息？

2）各個(gè)節(jié)點(diǎn)收到發(fā)來的信息后，如何計(jì)算自己的信息，或者說如何計(jì)算將要發(fā)出去的信息？



這兩個(gè)問題的回答，都依賴于具體的算法，所以，不同的算法，上面兩個(gè)問題的答案也不盡相同。我們之前講的兩種算法，就有兩種不同的答案。



1. 節(jié)點(diǎn)之間發(fā)送的信息，是什么樣的信息？



對(duì)于不用? log likelihood ratio 形式的算法：

?校驗(yàn)節(jié)點(diǎn) m 向變量節(jié)點(diǎn) n 發(fā)送的信息：

例如：

當(dāng)然，這個(gè)公式的計(jì)算，是有一個(gè)簡(jiǎn)化的快速算法的，這里就不講了，有興趣的朋友可以看專欄往期內(nèi)容。



?變量節(jié)點(diǎn) n 向 校驗(yàn)節(jié)點(diǎn) m 發(fā)送的信息：

例如:

?對(duì)于 log likelihood ratio 形式的算法：

校驗(yàn)節(jié)點(diǎn) m 向變量節(jié)點(diǎn) n 發(fā)送的信息：

例如：




變量節(jié)點(diǎn) n 向 校驗(yàn)節(jié)點(diǎn) m 發(fā)送的信息：

例如：

???? 變量節(jié)點(diǎn) 1 發(fā)給校驗(yàn)節(jié)點(diǎn) 2 的信息：

2. 對(duì)于第二個(gè)問題的回答，即各個(gè)節(jié)點(diǎn)收到發(fā)來的信息后，如何計(jì)算自己的信息，由于自己的消息，就是發(fā)給另外一種節(jié)點(diǎn)的信息，在回答第一個(gè)問題時(shí)，已經(jīng)隱含了這個(gè)問題的答案。

變量節(jié)點(diǎn)收到校驗(yàn)節(jié)點(diǎn)的消息之后，計(jì)算出變量節(jié)點(diǎn)的信息，在非 log likelihood ratio算法中用的公式為：

所以，變量節(jié)點(diǎn)是對(duì)收到的來自校驗(yàn)節(jié)點(diǎn)的信息，用連乘的方式來計(jì)算

而在 log likelihood ratio 算法中，因?yàn)槿×?log ，所以，變成了用連加來計(jì)算

校驗(yàn)節(jié)點(diǎn)收到變量節(jié)點(diǎn)的消息之后，計(jì)算出校驗(yàn)節(jié)點(diǎn)的信息，在非 log likelihood ratio算法中用的公式為：

則對(duì)收到的各種變量節(jié)點(diǎn)的信息的組合，先做連乘，然后再做連加。

而在 log likelihood ratio 算法中，用 tanh 函數(shù)來表示，更為復(fù)雜的一種計(jì)算公式。