LDPC碼之SPA解碼演算法

好久好久沒有更新部落格啦!
應該是說!只發過一篇而已啦!!哈~
很快的!第二篇，是一年後!!
終於完成研討會的論文了!!
難得有空!就把研討會資料整理貼上來啦~

LDPC碼SPA解碼演算法
這次我所完成的LDPC解碼器設計方法，都是參考胡大湘老師上課的講義啦~
胡老師也有將講義公開在網路上~
有興趣的人可以上胡老師的"老胡小舖"下載來看喔~


而為什麼要用SPA(Sum-Product Algorithm)解碼演算法來當這次的主題呢??
因為書上說SPA是LDPC碼擁有最好效能的解碼演算法~
至於是不是真的~
我也不知道啦!
還有另一個原因就是~
在上課的時候~
胡老師就已經叫我們用matlab實現這個decoder啦~
所以~
matlab轉C~
OK的~
由於這次完成的程式只是在於驗證用，
因此所用的檢測矩陣是一個5X10的規則矩陣，
如下面的圖片~



所謂的規則矩陣就是說矩陣中每行每列含 1 的個數都相同。
接下來就是這個矩陣的Tanner Graph 圖啦~



Tanner Graph 圖真是LDPC碼的關鍵~
Tanner Graph 就是將檢測矩陣之行以檢查點(Check Node)表示，列以位元點(Bit Node)表示~
而SPA decoder 就是要計算出各檢查點與位元點之間為0與1的機率比值(比值大於等於0代表訊號接近0，比值小於0代表訊號接近1)，以達到解碼效果。

我是把步驟分成四個~
第一步驟~
即計算出所有檢查點到位元點間為0與1的機率比值，以上面圖中上半部顏色線條為例~
檢查點m1到位元點l1之關係，計算m1到l1之間的機率比值必須計算出所有位元點到m1(除了l1到m1)的機率比值，在做第一次解碼時所有位元點到檢查點的機率比值為初始輸入的訊號為 0 與 1 的機率比值，之後的遞迴則運用步驟二得到的結果。

第二步驟~
計算出所有位元點到檢查點間為0與1的機率比值，以上圖下半部顏色線條為例~
位元點l10到檢查點m5之關係，計算l10 到m5之間的機率比值必須計算出所有檢查點到l10(除了m5到l10)的機率比值(由第一步驟求得)，再加上初始收到的訊息為0與1的機率比值(圖中沒有畫出初始訊號)。

第三步驟~
求出所有檢查點與位元點之間為0與1的機率比值，經過公式的推導與簡化，其實就是將第一步驟求得之結果加上與第二步驟求得之結果。

第四步驟~
將機率的比值做判斷(大於等於0判斷為0，小於0判斷為1)，再將其乘上檢測矩陣的轉置矩陣，若結果為全零則代表此判斷後的結果為解碼後得到的訊號，反之則遞迴至第一步驟。

一般書上跟胡老師講義是只分成三步驟啦(第一步跟第二步合在一起)!
但是我想說這樣比較好解釋，所以我自己拆成四步驟啦~