一個使用縱向混合排程和提早終止解碼機制的低密度奇偶檢查碼解碼器

An LDPC decoder using vertical shuffled scheduling and early termination

陳春榮(Chun-Jung Chen)

指導教授 ： 翁詠祿

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2009年)

摘要

無線通訊技術正在改變人類的生活型態，幾乎可取代今日ADSL加Wi-Fi的網路接取模式。尤其在無線傳輸下，通道編碼為一必要之過程。在許多規格書版本中，低密度奇偶檢查碼(Low Density Parity Check Codes, 以下簡稱LDPC碼)即為其中的規範之一種類。由於LDPC碼有很好的抗衰落性，編碼增益很高，接收機在較低的信噪比情況下仍然可以擁有較低的誤碼率，可以使覆蓋範圍得到提升。

在最近幾年來，高碼率低密度奇偶檢查碼的應用已經廣泛的被討論。然而，對高碼率低密度奇偶檢查碼而言，要以較快的解碼收斂速度做到高吞吐量和較低面積複雜度仍然是很困難的。而 Shuffled MPD 和 LMPD 的解碼收斂速度都快過傳統的 TPMP。由於複雜的記憶體讀取和極大儲存空間的需求，傳統的Shuffled MPD 並不適合硬體實現，特別是高速率低密度奇偶檢查碼。但另一方面，LMPD 已經使用在各種解碼器。在這篇論文裡，我們提出一種修改自 Shuffled MPD 的演算法，相比於傳統的 Shuffled MPD，它有著相似的解碼收斂速度，但卻可以減少記憶體讀取的複雜度以及很大儲存空間的需求，並且能保有不輸 LMPD 的解碼收斂速度。最後，我們將提出的演算法和架構套用在歐幾里德幾何學的低密度奇偶檢查碼 (8176,7156) 的解碼器。

關鍵字

低密度奇偶檢查碼 ； 歐幾里德幾何學 ； 提早終止解碼機制

並列摘要

The applications involving high-rate LDPC codes have been widely discussed. However, it is hard for high-rate LDPC decoders to achieve high throughput, lower complexity, and fast decoding convergence speed. The convergence speed of shuffled message passing decoding (SMPD) and the layered message passing decoding (LMPD) are faster than that of standard two phase message passing (TPMP) decoding. Due to complex memory access and requirement of large storage space, the conventional shuffled MPD is not suitable for hardware implementation especially for high-rate LDPC codes. On the other hand, the LMPD decoding has been broadly used in all decoder field. In this thesis, we propose a modified shuffled MPD which can achieve a similar decoding convergence speed but with reduced complexity in memory access and storage space as compared to the conventional shuffled MPD and achieve a similar convergence speed as compared to the LMPD decoding. Finally, a suitable architecture of self-rotate structure is also provided to implement an EG-LDPC (8176,7156) decoder based on the proposed algorithm and structure.

並列關鍵字

LDPC code ； Euclidean Geometry ； Shuffled MPD ； Early Termination

參考文獻

[1] R. Gallager, “Low-density parity-check Codes,” IRE Trans. Inf. Theory, vol.IT-8, no.1, pp.21-28, Jan. 1962.

[2] D. J. C. Mackay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronics Letters, vol.32, no.18, pp.1645-1646, Aug. 1996.

[3] D. Mackay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol.45, no.2, pp.399-431, Mar. 1999.

[4] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inform. Theory, vol.IT-27, pp.533-547, Sep. 1981.

[5] M. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” IEEE Trans. Commun., vol. 47, pp. 673-680, May. 1999.