改善傳統圖形解碼演算法在低密度校驗迴旋碼上之研究

Abstract

在圖形解碼中，使用和積演算法解碼時，若田納圖中存在循環會導致位元節點和校驗節點之間的運算違反獨立的假設，進而讓和積演算法解碼對每一個位元的估計會有所偏差。而低密度校驗迴旋碼的田納圖是由一些校驗節點和一些位元節點所形成的基本結構所重複拼貼而成，所以一旦發現裡面出現一個循環，會導致該循環的結構之後一直重複出現。當低密度校驗迴旋碼的字碼長度越長，則循環的數量也因此增加；在使用和積演算法時，獨立的假設會嚴重被違反，解碼效能也因此不佳。而本篇論文提供了兩種作法，來降低循環對和積演算法的影響，以改善其解碼效能。 第一種作法，首先把那些會導致和積演算法解碼效能不好的循環所連之校驗節點確認出來，再將這些校驗節點與其所連之全部位元節點這兩者間形成的子圖用等效位元籬笆做取代，並使用位元籬笆為基礎的解碼方式進行解碼。修改過後的田納圖中去掉被位元籬笆所取代的部分，剩餘之位元節點及校驗節點一樣以和積演算法做解碼，且這兩種解碼方式在迭代時是同時運作的。在上面的方法中，那些被取代的校驗節點其對應的所有校驗方程式或是其連的所有位元節點之數量有可能太多，導致那些子圖所形成之位元籬笆的複雜度過高，因此我們提出了第二種作法來降低位元籬笆的複雜度。第二種作法與第一種作法最大的差別在於我們不會將導致和積演算法解碼效能不好的循環所連之校驗節點與其對應之全部位元節點組成的子圖用位元籬笆做取代，而是只將那些循環對應的子圖用等效位元籬笆替代，並使用位元籬笆為基礎的解碼方式進行解碼。修改過後的田納圖中去掉被位元籬笆所取代的部分，剩餘之位元節點及校驗節點一樣以和積演算法做解碼，且這兩種解碼方式在迭代時是同時運作的。由於用這兩種作法所修改過後的田納圖中那些被取代的循環之結構都不會出現，若修改過後的田納圖也都沒有其他循環之結構的話，則兩種作法的解碼方式都能達到最佳解碼。最後由理論推導及模擬結果顯示，本論文所提之方法確實對和積演算法的解碼效能有進一步改善。

If there exist cycle in tanner graph of error-correcting code, the messages for computation in the sum-product algorithm (SPA) are observed to be statistically dependent, thereby degrading the decoding performance from the optimal one. Such performance degradation is even severer for low‐density parity‐check convolutional codes due to the repetitive structure among check and variable nodes in their tanner graphs. In this thesis, we propose two modified methods of SPA for mitigation of the cycle effect. Both the methods are based on a simple idea that the harmful cycles are replaced by proper trellis-decoding modules such that the dependence among messages in the modified tanner graph can be alleviated. By the simulation results, the proposed methods are verified to achieve satisfactory performance enhancements compared with SPA.