應用雙向信度差值與訊息暫停傳遞機制於低密度奇偶檢查碼動態解碼排程之研究

Abstract

由於低密度奇偶檢查碼具備強大的錯誤更正能力，故在眾多通訊標準中目前皆有採用此碼做為保護傳輸資料之用。在接收端解碼部分，通常會用和積演算法搭配田納圖並使用泛洪排程機制來解碼，但是因為田納圖可能具有短循環結構，所以當使用不同排程機制可得到不同的收斂速度與錯誤率效能。在序列動態排程研究中，一類是依據單向訊息變化差值動態調整的排程，如檢查節點至變數節點的訊息差值或變數節點至檢查節點的訊息差值，這類動態排程機制已被證明較泛洪排程優異。所以此類排程被視為替代泛洪排程的一個很好的選擇，雖然在此類排程亦被發現可能會出現貪婪群集這種不好的解碼現象，導致最後解碼失敗。

在此論文中，我們首先發現貪婪群集的發生原因之一可能來自訊息的連續傳遞現象，因此我們提出訊息暫停傳遞機制來避免貪婪群集現象的發生。此外，我們也擷取不同面向的單向差值之基本精神與優點，發展出一新式參考雙向差值的動態排程機制。此新式機制能同時準確地更新尚未收斂的節點並保有高可靠度的訊息傳遞，因此能同時改善錯誤率效能與收斂速度。根據實驗模擬結果顯示，訊息的暫停傳遞機制應用於傳統的動態排程解碼演算法中能有不錯的錯誤率改善，而參考雙向差值的動態排程機制則比傳統單向差值動態排程皆優異。

Since Low-Density Parity-Check Codes ( LDPC Codes ) have the powerful capability of error correction, they have been widely adopted for data protection in many communication standards. The sum-product algorithm based on Tanner graph of LDPC Codes with flooding scheduling is often used for decoding. However, due to the possible cycles on Tanner graph, different ways of scheduling for propagating message can produce different amounts of convergence speed and error-rate performance. The sequential dynamic scheduling based on the unidirectional residual of message, e.g., the residual of check-to-variable node message or the residual of variable-to-check node message, has been shown to provide better performance than the flooding scheduling. Such scheduling could be viewed as a good alternative, although it may sometimes result in a so-called greedy group decoding failure.

In this thesis, we first discover the circulative message-passing phenomenon that causes the greedy group. The message deactivation strategy is proposed here to avoid this phenomenon so as to reduce the occurrence of greedy group. Besides, we further take the advantages from the different forms of unidirectional residual in several designs of dynamic scheduling to develop a new dynamic scheduling with bidirectional residual. Our new scheduling can not only boost the convergence speed for the unstable nodes but also keep the propagation of high reliable messages on Tanner graph. Simulation results show that the conventional designs of dynamic scheduling with message deactivation strategy can obtain a significant improvement on the error-rate performance. The bidirectional residual based dynamic scheduling also outperforms the conventional designs.