這個文章講解一下多元 LDPC 碼的一種譯碼算法：基于 FFT 的譯碼算法。

所謂的多元，是指參與運算的數(shù)據(jù)不是比特，而是有更多的取值，例如取值0，1，2，3，或者例如取值01,2,3,4,5 等等。 校驗矩陣的系數(shù)也是可以取值不只是 0 和 1 ，例如下面這個校驗矩陣，是以模 4 運算為基礎(chǔ)的校驗矩陣，也就是很多教科書中稱之為有限域 , 當然涉及到很多高等代數(shù)的知識，但是，在這里，就都理解為模 4 的運算即可，無論加減乘，最后的結(jié)果都模 4 運算即可。

所以，這里面有三個校驗方程，收到 6 個數(shù)（記為 ），LDPC 編碼后的數(shù)據(jù)有六個，記為 ， 三個校驗方程可以寫為：

特別提醒，上面的運算都是在模 4 的規(guī)則下的，計算的結(jié)果都需要做模 4 運算。

本來最優(yōu)的譯碼方法是找? 中概率最大的，把概率最大時對應(yīng)的? 作為我們的譯碼結(jié)果。但是，這個運算量大，當碼長較長時，運算量大到不可行。我們退而求其次，計算單個 的概率來做判決：

我們把上面的公式做一些進一步的推導(dǎo)：

其中，（因為這個條件中沒有約束方程的要求，因此，其他的? 就不影響 .

?公式 (1) 中，我們?yōu)榱撕喕\算，我們假設(shè)各個校驗方程的成立與否，是相互獨立的，當然，實際上由于每個發(fā)送的數(shù)據(jù)，都參與多個校驗方程，因此，校驗方程之間是有相互關(guān)聯(lián)的，這里的假設(shè)，導(dǎo)致了一個約等于：

我們舉個例子，例如 在開頭的校驗方程中，我們考慮譯碼 則

現(xiàn)在，我們已經(jīng)用校驗方程成立與否的概率，來表示了發(fā)送數(shù)據(jù)的概率。

接著對公式 (2) 中的? 進行一些推導(dǎo)：

其中 ，可以認為是一個常數(shù)，我們來分析分子的部分, 因為? 給定，那么? 的話，就意味著校驗方程中其他項要取各種情況

其中

則公式 (4) 變成：

我們舉個例子，例如校驗方程 ， 以? 為例子

則有下列一些情況：

針對上面任何一種情況，例如


從上面的舉例中也可以看出，計算公式 (4) 是非常復(fù)雜的，運算量非常大。而且，我們還需要計算? 等于其他三種值(0,1,2)的情況，可見，公式(4) 和公式 (5)? 的計算量之大。

這里，引入一種在模 4 這種操作下的傅里葉變換，這里我們不做嚴格的證明，只是把這個思想和過程梳理一下，理解了這是在干啥，后面可以查閱更專業(yè)的書籍和文獻，來看嚴格的證明。

我們舉一個二元碼的例子，即取值只有 0 和 1， 有兩個隨機變量，，令：

如果我們要計算：

和

那么公式 (6) 可以展開為：

公式(7) 可以展開為：

對于這種二元的情況，我們引入一種變換：

因為是二元的情況，所以，這個變換是對某個隨機變量的兩種取值的概率的變換，對?? 做變換：

對?? 做變換

對上面兩種變換之后的結(jié)果，即兩個列向量，做對應(yīng)元素相乘：

對上面的結(jié)果，我們再引入一個變換：

則：

可以看到，上面這個結(jié)果，剛好就是公式(7)(8) 的結(jié)果，上面結(jié)果的向量中，元素1是公式(7)的結(jié)果，元素2是公式(8) 的結(jié)果。

這里，我們得到了一個新的方法：

先對

和

做? 變換，分別得到一個向量，然后再對兩個向量中對應(yīng)元素相乘，得到一個向量，最后對這個向量做? 的變換。

對公式 (5) 中，我們需要 考慮? ，我們把? 的結(jié)果，記為??? 其中上標 p 表示 permutation（置換） 的意思，實際上就是 取了一個值? ，通過乘以 ， 就可以計算出一個? , 然后，公式（5） 中求和項的下標，就可以表示為：

?則，公式(5) 可以寫成：

我們暫時先忽略上標 p ，假如 公式 (5) 是如：


那么，我們可以用類似于二元 情況的，引入變換域算法。

我們來看一下公式 (5)，其中

有四種情況（以模 4 為例子）：

假如看? 這個校驗方程，則 , 那么? 有四種取值，根據(jù)公式(5), 我們需要計算的概率有：
可以寫成一個向量：

我們另外三個向量：

對上面三個向量分別做 變換, 由? 計算得來：

則：


同理：


然后，把三個向量 做對應(yīng)的元素相乘

再對上式的結(jié)果做?? 變換，其中：

那么：

就是公式(10) 的結(jié)果，也就是公式 (5) 的結(jié)果，因為? 這個變換，是模 4 域里面的變換，可以用快速傅里葉變換的算法，降低運算量。

公式(11)(12)(13) 都是一種變換，從一個域變換到另外一個域，這里應(yīng)該理解為在模 4 運算下的傅里葉變換，然后可以用快速傅里葉變換，快速傅里葉變換的算法如下：

對公式（11）

如果是 元的 LDPC 碼，則這個變換就是

其中

則一個 s 維向量? , 則

?按照如下公式計算：

我們舉個例子來說明，假如我們要分析的是 8 元 LDPC 碼，則每個數(shù)據(jù)有 3 個比特，我們把一個數(shù)據(jù)記為 c , 是由 3 個比特組成的數(shù)據(jù)，取值范圍從 0 到 7.? 這八種取值，都對應(yīng)一個概率，8 個概率組成一個向量：

?那么 的結(jié)果還是一個 8 維的向量，其結(jié)果為：

然后

最后

則? 就是變換后的最終結(jié)果。

參考文獻： 《多元 LDPC 碼及其應(yīng)用》 趙山程? 馬嘯? 白寶明著