對低密度校驗矩陣之圖形解碼方法修改之探討

Abstract

在本篇論文裡, 我們根據設計目標的不同展示了兩種方法來修改低密度校驗碼所使用的和積演算法。

第一種提出的方法之設計目標是減緩迴圈對和積演算法造成的影響。 我們發現和積演算法之所以會因為迴圈的存在而導致判斷失準的原因, 是因為迴圈破壞了田納圖上校驗節點的滿足條件彼此獨立的假設。 因此, 既然這些校驗節點的滿足條件彼此相依, 則正確的解碼方式是要同時考慮這些校驗節點的滿足條件。 由上述的想法為起點, 我們利用籬笆解碼同時考慮迴圈上之邊的資訊解碼以得到更準確的判斷。 此外, 我們發現了一種具雙狀態的去尾籬笆結構可以用來解任何長度的單一迴圈上的資訊。 這個發現使我們不需紀錄各種不同的籬笆結構而讓此方法更具實用性。

第二種提出的方法之設計目的是當低密度校驗碼使用截取(Puncture)時可得到更佳的效能。 一般在設計低密度校驗碼的截取模式(Puncture Pattern)時, 最重要的設計概念之一就是盡可能讓所有截取節點能在最少解碼疊代次數內回復資訊。 然而, 當截取數量大到一定程度時, 即使使用最好的截取模式來作截取, 仍不可避免的會出現需要高疊代次數才能回復資訊的截取節點。 我們設計出了一種"一步回復解碼器"可以輔助和積演算法使所有截取節點在第一次疊代時就回復資訊。 此外, 為了讓截碼更準確我們在此解碼器中使用了多樣性結合(Diversity Combining)來解碼。 我們將WiMAX的802.16e標準裡長度為576、碼率為1/2之低密度校驗碼截取成碼率為2/3, 我們所提出的新的解碼方法對原始的和積演算有1.2dB左右的位元錯誤率的改善。 此外, 隨著我們加大截取數量, 位元錯誤率改善的程度也會不斷增加。

In this thesis, two modified Sum-Product algorithm (SPA) about low-density parity-check (LDPC) codes are present for different purposes.

The first proposed algorithm is designed to alleviate the cycle effect on SPA. We found that the existing of cycle degrades the performance of SPA since it breaks the independence of the satisfy condition of different check nodes within the cycles in the Tanner graph. It means that we should consider the satisfy conditions of check nodes within the cycle at the same time for decoding since they are dependent. Based on the above observation, we replace SPA with trellis-decoding to solve the information of edges in the cycles at the same time to get better estimation. Furthermore, we also found that we can utilize one special two-state tail-biting trellis structure to estimate the information of edges in a cycle with any length. This discovery helps us to save huge storage from different trellis structures and it makes the method be more practical.

The second proposed algorithm is specifically designed for the LDPC punctured code to improve the decoding performance. In previous studies, one of the most important criterions to design puncture pattern is to recover the message of punctured nodes in smallest iteration numbers in SPA. However, when the number of punctured nodes increases, it must happen that some of punctured nodes need large iteration numbers to recover in original SPA even under the optimal puncture pattern. We therefore design an auxiliary decoder based on the diversity combining, which called “One-Step Recover decoder”, can help all punctured nodes recover their message in first iteration of SPA. In the case we puncture the 802.16e standard LDPC code of length 576 from rate 1/2 to 2/3, the simulation results show about 1.2dB BER improvement than original SPA. The performance gain can be larger while the punctured number is increase.