低密度同位檢查碼系統設計

Abstract

低密度同位檢查碼 (low-density parity-check code, LDPC code) 具有接近Shannon理論極限的錯誤更正效能。但相較於其他錯誤更正碼，LDPC碼的編碼與解碼通常需要更多的耗電與處理時間，使得它的實際應用受到限制。在本論文中，我們針對設計有效率的LDPC碼系統提出了以下技術：一、低時間延遲的編碼方式；二、數種用於解碼的技巧，如減少節點運算的方法、智慧型的排程、提早停止解碼的條件等；三、具有實作考量的碼結構。 首先，我們針對許多最新通訊標準採用的雙對角 (dual-diagonal) LDPC碼，提出有效率的編碼演算法。我們提出的編碼方式採用雙向的同位位元 (parity bit) 更正，可分離編碼過程中的資料相依性，以達到更高的產量、更低的時間延遲與更好的硬體利用率。 其次，為了減少LDPC解碼器的耗電量與計算時間延遲，我們提出了減少節點運算的方法與智慧型動態排程策略。我們提出的運算減少方法包含了一自動調整的停止條件與一節點停用機制。此節點停用機制可以更準確地判斷節點的可靠度。在另一方面，我們提出了兩種動態解碼排程策略。相較於傳統排程方法，第一種策略以較不貪婪的演算法來選擇下一個要更新的訊息 (message)。此作法用更少的訊息運算量有效地降低了error floor。第二種策略在排序與選擇下一待更新的訊息時，使用了不同的衡量標準，兼具了訊息差值 (residual) 以外的考量。此種排程策略在可達到的錯誤率與所需訊息運算量上，都優於傳統排程方法。 接著，我們設計了數種低複雜度的解碼提早停止條件。利用雙對角碼的結構特性，我們提出的提早偵測解碼成功的機制，可以排除非必要的解碼迴圈 (iteration)。此機制減少了可解碼區塊的平均解碼迴圈數，而不會損失錯更正效能。此外，我們也提出了兩種解碼失敗的提早終止機制。第一種機制利用解碼器中的syndrome檢查功能來偵測無法解碼的區塊。第二種機制利用相鄰解碼迴圈產生的hard decision來追蹤解碼狀況並偵測解碼失敗的收斂。這些機制均可在損失很少或不損失錯誤更正效能的情況下，有效地節省解碼迴圈數。 最後，我們針對較長碼長的應用，提出了一種有利於實作的結構化LDPC碼。我們修改漸進式邊增長 (progressive edge-growth) 演算法來建構所提出之多層次類循環 (hierarchical quasi-cyclic) 碼。藉由在同位檢查矩陣中加入有利於實作的兩層結構，只需要少量的第二層子矩陣，就可以改善類循環碼的錯誤更正效能。此外，類循環碼的解碼器架構經修改後可用於解碼所提出之結構化碼，以達到更好的錯誤率與更快的解碼速度。

For error correction in communication systems, low-density parity-check (LDPC) codes have been shown to have near-Shannon-limit performance. However compared with other error correction codes, encoding and decoding LDPC codes always require considerable power and processing time which would limit their practical use. In this thesis, the following techniques are proposed for efficient LDPC coding systems: 1) low-latency encoding, 2) decoding with node operation reduction, intelligent scheduling, and early stopping criteria, and 3) code structure with implementation benefits. First, an efficient encoding algorithm is proposed for dual-diagonal LDPC codes, which are adopted by many next generation communication standards. The proposed two-way parity bit correction encoding scheme breaks up the data dependency within the encoding process to achieve higher throughput, lower latency, and better hardware utilization. Next, to reduce the power consumption and computation latency of LDPC decoders, a node operation reduction scheme and intelligent dynamic scheduling strategies are presented. The proposed operation reduction scheme consists of an adaptive stopping criterion and a node deactivation mechanism. The node deactivation mechanism improves the accuracy of node reliability estimation. On the other hand, two dynamic scheduling strategies for LDPC decoders are proposed. The first strategy improves the conventional scheduling algorithms by selecting the next message to update less greedily. The less-greedy scheduling effectively lowers the error floor with fewer message updates. The second strategy orders and selects the next message to update using a different metric with considerations beyond the residuals of messages. This farsighted scheduling strategy outperforms the conventional scheduling algorithms in terms of achievable error rate and required number of message updates. Furthermore, several low-complexity early stopping criteria for LDPC decoders are presented. An early detection mechanism for successful decoding is proposed to eliminate unnecessary iterations by exploiting the structure of dual-diagonal codes. Average number of decoding iterations for decodable blocks can be reduced without error performance degradation. On the other hand, two types of early termination mechanisms are proposed for unsuccessful decoding. In the first mechanism, the syndrome-check block in the decoder is utilized to detect undecodable blocks. In the second mechanism, the hard decisions made during consecutive iterations are used to monitor the decoding status and detect the convergence of unsuccessful decoding. These mechanisms can achieve significant iteration saving with less or no error performance loss. Finally, we propose a class of implementation-friendly structured LDPC codes for long code length applications. A modified progressive edge-growth algorithm is used to construct the proposed hierarchical quasi-cyclic (H-QC) codes. By adding implementation-friendly two-level hierarchy with limited types of second-level submatrices in the parity check matrix, error performance is improved substantially over QC codes. We also show that QC-based decoder architecture can be easily applied to H-QC decoders to achieve better coding gain and higher throughput performance.