低密度奇偶校驗碼之新動態解碼排程

Abstract

動態解碼排程 (informed dynamic scheduling)，亦即差值信任傳播(residual belief propagation, RBP)，是一種依LDPC 碼圖中的訊息現況進行動態解碼排程的連續解碼排程 (sequential scheduling)。相較於標準的連續解碼排程，動態解碼排程可快速降低錯誤率以提供更快的收斂速度。然而，動態解碼排程在收斂時的錯誤率較高，其原因在碼圖中的貪婪群集(greedy group)於訊息迭代解碼後佔用大量解碼資源所致。為解決上述問題，我們提出兩種新的動態解碼排程。根據我們的觀察，貪婪群集通常由高對數概似強度的變數節點(variable node)以及與其相連之檢查節點(check node)所組成。上述節點產生的高強度訊息差值，將導致大部分訊息更新與傳遞的解碼資源為貪婪群集所佔據。為此，我們提出propagation-guaranteed RBP (PG-RBP)。在此排程中，被更新的檢查節點到變數節點的訊息將立即被傳送到相鄰的檢查節點，並確保訊息在相鄰的檢查節點間更新及傳遞。因此，解碼資源將不為少數檢查節點或變數節點所佔據。為強化動態解碼排程的訊息可靠度，我們另外提出enhanced-reliability RBP (E-RBP)。當一檢查 節點到變數節點的訊息被選定傳遞後，另一與此變數節點相連的檢查節點到此變數節點訊息亦將被更新與傳遞，以提高變數節點到檢查節點訊息的可靠度。模擬結果顯示，上述兩種動態解碼排程在錯誤率效能及收斂速度上，相較於現有的動態排程都有更優秀的表現。此外，同時採用上述兩種動態排程策略可獲得更加優異的效能。

為了獲得訊息差值，動態解碼排程需要大量的運算以取得檢查節點到變數節點的事前預算(pre-computing) 訊息。雖然傳統的最小和近似(min-sum approximation)演算法可簡化運算複雜度，但此演算法只能用於更新事前預算訊息，而無法用於檢查節點到變數節點的訊息更新。在本篇論文中，我們提出以最小和近似為基礎的檢查節點訊息更新演算法。相較於傳統的最小和演算法，我們提出的演算法除了提供較低的複雜度外，亦可同時用於訊息的事前預算及更新。模擬數據顯示，使用以最小和為基礎的近似演算法用作訊息事前預算與更新，可使解碼器在錯誤率效能和運算複雜度兩者間取得良好的平衡。

Informed dynamic scheduling (IDS), also known as residual belief propagation (RBP) based decoding, is a class of sequential belief-propagation (BP) decoding strategies for LDPC codes which dynamically updates the decoding schedule based on the current state of the messages in the code graph. Compared with the standard sequential scheduling, IDS is able to provide faster decrease of error rate and rapid convergence. However, IDS may have much worse converged error-rate performance due to the decoding greedy groups, which are the sub-graphs that can occupy most of the message updating resources after few decoding iterations. In this work, we propose two novel IDS strategies. We observed that a greedy group usually consists of several check nodes (CNs) connected to the variable nodes (VNs) with large log-likelihood magnitudes, and then the messages associated with these nodes will have larger residuals and occupy most decoding resources for message updating and passing. As a result, we propose propagation-guaranteed RBP (PG-RBP). In this schedule, the updated CN-to-VN message will be immediately forwarded to the other linked CNs by the CN so that the decoding resource will not be occupied by some certain VNs/CNs for updating messages. To enhance the reliability of the propagated messages in IDS decoding, enhanced reliability RBP (E-RBP) is also proposed. While a CN-to-VN message is selected to be updated, one of the other CN-to-VN messages related to this VN will also be selected to be renewed and propagated so that the new VN-to-CN messages can be more accurate. Simulation results indicate that either of the proposed two schedules is able to outperform the existing IDS strategies in both error-rate performance and convergence speed, and by applying these two schedules simultaneously we would have further performance improvement. To have the message residuals, IDS strategies require huge computation effort for pre-computing the CN-to-VN messages. Although the conventional min-sum (MS) approximation has been considered for complexity reduction, it can only be utilized in message pre-computations but cannot simultaneously be used for calculating the propagated CN-to-VN messages. In our work, we also suggest a new CN message updating formula based on the MS approximation. Compared with the conventional MS formula, the new one requires higher computational complexity but can be used for CN-to-VN message updating. Numerical results show that the IDS strategies with the MS-based pre-computations and proposed CN message updating rule can yield satisfactory error-rate performance and provide good trade-off between complexity and performance.