用動態排程來改進低密度奇偶檢查碼系統的性能

Performance improvement of LDPC coded systems by dynamic scheduling and selective mapping

林琦祐(Chi-Yu Lin)

指導教授 ： 翁詠祿

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

摘要

近年來隨著硬體的進步, LDPC被廣泛的運用在通訊方面,而准迴旋式的低密度奇偶檢查碼(QC-LDPC)更是在新一代的無線通訊系統上被大量的使用且納入規格中. 在這篇論文中,我們提出一種動態排程的解碼方法,並且將這個方法使用在之前提出的類循環低密度奇偶檢查碼的解碼架構上, 用來縮短IEEE 802.16e標準的類循環低密度奇偶檢查碼 (QC-LDPC)的解碼時間. 我們基於適當的判斷標準對每個階層動態的省略, 重複或是執行其它的解碼運算.一種易於硬體上實現的提早停止策略也同時在這篇論文中被提出來, 其作用在於提早將部分的階層動態的跳過解碼, 如此一來可以大幅地減少遞迴解碼的數量, 以及較快速的達到收歛, 或是跳出解碼步驟.同時使用這兩種技術的修正型訊息傳遞解碼可以較沒有使用這兩種方法的解碼方式在相仿的錯誤表現上有效的減少計算複雜度. 我們同時的表現出了兩個獨自的方法, 並且將它們兩個合併於一起以顯示出它們的效果. 在這篇論文中, 我們不僅在相異的解碼方法中提供位元錯誤率的比較, 同時也提出了一種平均執行數目的數據來顯示出各種方法的差異. 最後我們將這兩種技術合併在一起,得到一種動態解碼並且快速提早收歛的方法, 同時用剛剛提出來的數據來表現出改進之後的優點.

關鍵字

動態排程 ； 低密度奇偶檢查碼

並列摘要

In this thesis, we propose a dynamic scheduling decoding
method, to accelerate the decoding of quasi-cyclic low-density
parity-check (QC-LDPC) codes used in the IEEE 802.16e standards
based on a previously proposed decoding architecture. We dynamically
skip, redo
or do other decoding operations for each layered based on appropriate
criteria. An early termination strategy which is efficient in
hardware implementation is also proposed in this thesis. The
modified message-passing decoding (MPD) using these two techniques
simultaneously can reduce the computational complexity with similar
error performance as compared to the case of not using these two
techniques.

並列關鍵字

LDPC ； dynamic scheduling

參考文獻

[1] R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: MIT

Press, 1963.

[3] G. A. Margulis, ”Explicit construction of graphs without short cycles and

[4] R. M. Tanner, ”A recursive approach to low complexity codes,” IEEE

[5] M. Sipser and D. A. Spielman, ”Expander codes,” IEEE Trans. Inform.