Theory and Performance of ML Decoding for LDPC Codes Using Genetic Algorithm

低密度奇偶校驗碼近幾年來吸引廣大研究者的關注，許多人先後投入這個領域，其中，最主要的原因在於優越的解碼能力。傳統的解碼器主要運用訊息傳遞的原理，藉由眾人的力量更正因雜訊干擾而錯誤的資訊。最大概度解碼則是編碼理論中公認最佳的解碼器。雖然前者的方法有不錯的更正效果，但是始終無法達到最大概度解碼的能力，而後者卻又因為複雜度太高無法實行。因此，如何求出低密度奇偶校驗碼中最佳解碼器的更錯效果就是本篇論文研究的重點。 相關研究指出，此種編碼方法整體效果可能達到通道容量，但我們還是想知道某些特定編碼的極限值。此外，渦輪碼的最大概度解碼研究也在某些論文中提出，他們成功找出錯誤率1.5*10^(-4)以下的解碼表現，這些成就也成為本篇論文參考及學習方向。 我們發現在錯誤率10^(-5)以下的地方，干擾解碼演算法可以有效達到出最大概度解碼的能力，但是當錯誤率較高時，這樣的方法就不太有效，因此我們提出加入額外資訊的概念及可行性研究。這些資訊稱做gift，主要協助解碼器產生其他高度可能的答案。為了更有效率找到這些額外資訊，本篇論文根據基因演算法的概念，設計出兩種新的解碼演算法。 基因解碼演算法中的染色體由一群已知的0、1或未知的基因組成，傳統的遞迴解碼器用來評斷這些染色體的好壞，運用「物競天擇、適者生存」的原理，留下最優良的基因，多代演化後，能夠幫忙解出真正傳送編碼的染色體就會出現。同時我們也提出平行基因解碼演算法，每個初始染色體獨自演化，最終解回真正的傳送資訊。 對我們而言，基因解碼演算法最重要的地方是任何人用模擬的方式求出特定低密度奇偶校驗碼的最大概度解碼能力。根據我們的模擬結果，此種解碼方法比傳統方法好上0.1dB以上，並且成功在錯誤率10^(-5)以下的地方找到解碼能力的極限值。此外，此法也比先前提到的干擾解碼演算法好上0.02~0.03dB，並擁有和球體裝填極限一樣的型式。只要複雜度允許，本文提出的方法就可以用來改善傳統解碼方法的能力。Low-density parity-check (LDPC) codes drawn large attention lately due to their exceptional performance. Typical decoders operate based on the belief-propagation principle. Although these decoding algorithms work remarkably well, it is generally suspected that they do not achieve the performance of ML decoding. The ML performance of LDPC codesemains unknown because efficient ML decoders have not been discovered.lthough it has been proved that for various appropriately chosen ensembles of LDPC codes, low error probability and reliable communication is possible up to channel capacity, we still want to know the actual limit for one specificode. Thus, in this thesis, our goal is to establish the ML performance. t a word error probability (WEP) of 10^{-5} or lower, we find that perturbed decoding can effectively achieve the ML performance at reasonable complexity. In higher error probability regime, the complexity of PD becomes prohibitive. In light of this, we propose the use of gifts. Proper gifts can induce high likelihood decoded codewords.e investigate the feasibility of using gifts in detail and discover that the complexity is dominated by the effort to identify small gifts that can pass the trigger criterion. A greedy concept is proposed to maximize the probability for a receiver to produce such a gift. Here we also apply the concept of gift into the genetic algorithm to find the ML bounds of LDPC codes. n genetic decoding algorithm (GDA), chromosomes are amount of gift sequence with some known gift bits. A conventional SPA decoder is used to assign fitness values for the chromosomes in the population. After evolution in many enerations, chromosomes that correspond to decoded codewords of very high likelihood emerge. We also propose aarallel genetic decoding algorithm (P-GDA) based on the greedy concept and feasibility research of gifts. The most important aspect of GDA, in our opinion, is that one can utilize the ML bounding technique and GDA to empirically determine an effective lower bound on the error probability with ML decoding. ur results show that GDA and P-GDA outperform conventional decoder by 0.1 ~ 0.13 dB and the two bounds converge at a WEP of $10^{-5}$. Our results also indicate that, for a practical block size of thousands of bits, the SNR-error probability relationship of LDPC codes trends smoothly in the same fashion as the sphere packing bound. The abrupt cliff-like error probability curve is actually an artifact due to the ineffectiveness of iterative decoding. If additional complexity is allowed, our methods can be applied to improve on the typical decoders.1 Introduction 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Contribution and organization . . . . . . . . . . . . . . . . . . . . . . 5 Background 7.1 Low-density parity-check code . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Sparse parity matrix . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Regular LDPC codes . . . . . . . . . . . . . . . . . . . . . . . 8.1.3 Irregular LDPC Codes . . . . . . . . . . . . . . . . . . . . . . 8.2 Tanner graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Decoding of LDPC codes . . . . . . . . . . . . . . . . . . . . . . . . . 10.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3.2 Concept of belief propagation . . . . . . . . . . . . . . . . . . 10.3.3 Sum-product algorithm . . . . . . . . . . . . . . . . . . . . . . 11.3.4 Iterative decoding . . . . . . . . . . . . . . . . . . . . . . . . . 13.4 ML bounding technique . . . . . . . . . . . . . . . . . . . . . . . . . 16.4.1 Bounding ML WEP through simulation . . . . . . . . . . . . 16.4.2 Multiple-output decoding . . . . . . . . . . . . . . . . . . . . 18.5 Genetic decoding algorithm . . . . . . . . . . . . . . . . . . . . . . . 19.6 Sphere packing bound(SPB) . . . . . . . . . . . . . . . . . . . . . . . 22 Bounding ML performance using perturbation noises 25.1 Perturbed decoding for LDPC codes . . . . . . . . . . . . . . . . . . 25.2 Genetic decoding with additive noise as chromosomes . . . . . . . . . 29 Feasibility of gifts in facilitating ML performance bounding 33.1 Gift-assisted decoding for LDPC codes . . . . . . . . . . . . . . . . . 34.2 Complexity analysis of randomly selected gifts . . . . . . . . . . . . . 37.3 Gift selection based on a priori bit probability . . . . . . . . . . . . . 39.4 Feasibility of evolutionary algorithm . . . . . . . . . . . . . . . . . . . 42.5 Concentration of useful gift bits . . . . . . . . . . . . . . . . . . . . . 44 Genetic decoding algorithm 49.1 Gift-assisted genetic decoding algorithm for LDPC codes . . . . . . . 49.2 ML bound using genetic decoding algorithm . . . . . . . . . . . . . . 52.3 Parameters and procedures for genetic decoding algorithm . . . . . . 53.4 Simulation results of genetic decoding algorithm . . . . . . . . . . . . 54 Parallel genetic decoding algorithm 57.1 Parallel genetic decoding algorithm for LDPC codes . . . . . . . . . . 57.2 Parameter and procedure for parallel genetic decoding algorithm . . . 60.3 Simulation results of parallel genetic decoding algorithm . . . . . . . 63 Summary 65 Conclusions and future works 67.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68ibliography 7