低記憶體需求及效能改善的低密度同位元檢查碼解碼器架構

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：18.191.62.68

姓名

張競升(Jing-sheng Jhang) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

低記憶體需求及效能改善的低密度同位元檢查碼解碼器架構
(A Low Memory Demand and Performance Enhancement Architecture of LDPC Decoder)

相關論文

★ 用於類比/混和訊號積體電路可靠度增強的加壓測試	★ 應用於電容陣列區塊之維持比值良率的通道繞線法
★ 高速無進位除法器設計	★ 以正交分頻多工系統之同步的高效能內插法技術
★ 增強CMOS鎖相迴路可靠度	★ 適用於地面式數位電視廣播系統之平行架構記憶體式快速傅立葉轉換處理器設計
★ 對於長解碼長度可降低其記憶體使用的低密度同位檢查碼解碼器設計	★ 單級降壓式功因修正轉換器之探索
★ 設計具誤差消除機制之串疊式三角積分調變器	★ 交換電容式類比電路良率提升之設計方法
★ 使用分級時序記憶實作視角無關手勢辨識問題	★ 部分平行低密度同為元檢查碼解碼器設計
★ 應用於無線通訊系統之同質性可組態記憶體式快速傅立葉處理器	★ 混合式加法器設計
★ 非線性鋰電池之充放電模型	★ 降壓型轉換器之控制在市電併聯型光伏系統

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

低密度同位元檢查(low density parity check, LDPC)解碼演算法是使用訊息傳遞(message passing)的方式進行疊代運算。在解碼效能與硬體複雜度的取捨之下，大多採用部分平行(partially parallel)架構，在此架構中記憶體(memory)被用來儲存交換的訊息。換言之，儲存元件在此架構中是不可或缺的。而記憶體的大小與檢查矩陣(parity check matrix, PCM)中 ”1” 的數目成正比。
部分平行架構的兩種記憶體使用方法，共享記憶體架構與獨立型記憶體架構已普遍實現於LDPC解碼器。因為儲存單元佔據了大部分的面積，如何減少儲存單元的面積成為LDPC解碼器上一個熱門的研究課題。運用移位暫存器來做資料的取回，可減少記憶體使用量，使得整體電路面積可以下降；而運用環型位移暫存器來取代記憶體以及資料取回電路，可以提升解碼速度。本論文提出改良型架構融合兩者的優點以提高吞吐量(throughput)及減低硬體需求。實驗結果顯示，所提出來的方法實現在(3,6)規則同位元檢查矩陣，編碼長度(code length)為 1536位元(bit)，編碼率(code rate) 1/2，所提出的解碼器在操作頻率為400Mhz時，其吞吐量可達到438Mb/s。

摘要(英)

LDPC code is one of error correction codes (ECC) and widely used in digital communication systems because it has good error correcting performance for large code length. There exists a trade-off between hardware complexity and decoding efficiency on LDPC decoder. In general, partially parallel architecture is adopted for reducing the complexity of hardware implementation. Because of LDPC code decodes iteratively, storage element is necessary when designing a LDPC decoder in finite hardware cost. Since that storage element dominates the area of LDPC decoders. Reducing the area cost of memory becomes an important issue.
Previous studies provided methods to lower the memory requirement and to reduce the processing unit. Lowering the memory requirement can be achieved by using registers; on the other hand, the throughput can be enhanced by using the circular shift registers. This thesis proposes an alternative architecture which takes the advantages of both approaches. The proposed architecture attempts to achieve higher throughout at moderate hardware cost. Results show that, for a (3,6)-regular parity check matrix (PCM) with code length 1536, the proposed LDPC decoder achieves a throughput of 438Mb/s at operating frequency of 400MHz.

關鍵字(中)

★ 部分平行
★ 低密度同位元碼
★ 低密度同位元解碼器

關鍵字(英)

★ LDPC code
★ LDPC decoder
★ paritally parallel

論文目次

一、緒論..................................................1
1.1數位通訊與錯誤更.......................................1
1.2研究動機...............................................2
二、研究背景..............................................4
2.1同位元檢查矩陣.........................................4
2.2類循環(quasi-cyclic)矩陣...............................6
2.3 LDPC編碼原理..........................................7
2.4 LDPC 解碼.............................................8
2.4.1 訊息傳遞演算法(Message Passing Algorithm, MPA)......8
2.4.2 積和演算法(Sum Product Algorithm, SPA)[3]..........13
2.2.2對數型積和演算法(Log-Likelihood Ratio for SPA)......16
2.2.3最小和演算法與改良型最小和演算法....................18
2.2.4位元錯誤率與疊代關係模擬............................19
三、解碼器硬體架構.......................................20
3.1 LDPC解碼架構.........................................20
3.1.1完全平行架構(Fully parallel Architecture)...........20
3.1.2序列架構(Serial Architecture).......................21
3.1.3部分平行架構(Partially Parallel Architecture).......22
3.1.4探討與比較..........................................24
3.2CNFU與BNFU架構........................................25
3.2.1對數型積和演算法硬體架構............................25
3.2.2最小和演算法與改良型最小和演算法硬體架構............27
3.3以記憶體為基礎所實現的部分平行架構[19]................28
3.3.1修正型最小和演算法..................................28
3.3.2硬體架構............................................31
3.3.3記憶體排列方式......................................32
3.3.4資料取回結構問題....................................34
3.3.5吞吐量估計..........................................37
3.4以環型移位暫存器為基礎的部分平行架構[20]..............38
3.4.1資料取回與儲存架構..................................38
3.4.2硬體架構............................................39
3.4.3 CSR演算法..........................................40
3.4.4 吞吐量估計.........................................42
3.5 討論與比較...........................................42
四、提出的架構設計與電路實現.............................44
4.1 改良型架構...........................................44
4.1.1原型架構............................................44
4.1.2所提出的解碼架構....................................46
4.2 解碼流程與改良型CSR演算法............................49
4.2.1解碼流程............................................49
4.2.2改良型CSR演算法.....................................50
4.3整體架構與功能單元....................................57
4.3.1整體解碼架構(Overall decoding architecture).........57
4.3.2處理單元(Process Unit, PU)..........................58
4.3.3數值產生器(value generator, VG).....................61
4.3.4提出的記憶體排列方式................................61
4.3.5環型位移暫存器(Circular Shift Register, CSR)........63
4.4實驗結果(Experimental Results)........................63
五、結論與未來工作.......................................68
5.1結論..................................................68
5.2未來工作..............................................69
參考文獻.................................................70

參考文獻

[1]C. Berrou, A. Glavieux, and P. Thitimajshima, “ Near Shannon limit error- correcting coding and decoding: Turbo codes,” IEEE International Conference on Communication,
pp. 1064-1070, May 1993.
[2]R. G. Gallager, “ Low density parity check codes,” IEEE Transactions on Information Theory, pp. 21–28, January 1962.
[3]D. J. MacKay, and R. M. Neal, “Good codes based on very sparse matrices,” IEEE Transactions on Information Theory, pp.399-431, March 1999.
[4]R. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, pp.533-547, September 1981.
[5]L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Transactions on Information Theory, pp.284-287, March 1974.
[6]G. D. Forney, “ Codes on graphs: normal realizations,” IEEE Transactions on Information Theory, pp. 520-548, Feb. 2001
[7]F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, pp. 498- 519, February 2001.
[8]D. Vukobratovic and V. Senk, “On the optimized patent-free LDPC code design for content distribution systems,” IEEE International Symposium on Wireless Communication, pp. 365 - 369, October 2007.
[9]H. Saeedi and A. Banihashemi, “Design of irregular LDPC codes for BIAWGN channels with SNR mismatch,” IEEE Transactions on Communications, pp.6-11, January 2009.
[10]Z. W. Li, L. Chen, L. Q. Zeng, S. Lin, and W. H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” IEEE Transactions on Communications, pp.1973 – 1973, November 2005.
[11]J. Rosenthal and P. O. Vontobel, “Constructions of regular and irregular LDPC codes using Ramanujan graphs and ideas from Margulis,” IEEE International Symposium on Information Theory, pp. 4, June 2001.
[12]C. J. Howland and A. Blanksby, “A 220mW 1-Gbit/s 1024-bit rate-1/2 low density parity check code decoder,” IEEE Conference on Custom Integrated Circuits, pp. 293-296, May 2001.
[13]A. Blanksby and C. J. Howland, “A 690mW 1-Gbit/s 1024-b rate-1/2 low –density parity-check code decoder,” IEEE Journal of Solid-State Circuits, pp. 404-412, March 2002.
[14]M. Karkooti and J. R. Cavallaro, “Semi-parallel reconfigurable architectures for real-time LDPC decoding,” IEEE International Conference on Information Technology: Coding and Computing, pp.579 – 585, April 2004.
[15]X. Y. Shih, C. Z. Zhan, and A. Y. Wu “A real time programmable LDPC decoder chip for arbitrary QC-LDPC Partially check matrix,” IEEE Asian Solid-State Circuits Conference, pp.369-372, November 2009.
[16]T. Ishikawa, K. Shimizu, T. Ikenaga, and S. Goto, “High-throughput LDPC decoder for long code-length,” International Symposium on VLSI Design, Automation and Test, pp.1-4, April 2006.
[17]Z. F. Wang and Z. Q. Cui, “A Memory Efficient partially parallel decoder architecture for QC-LDPC codes,” Asilomar Conference on Signals, pp.729-733, November 2005.
[18]C. L. Wey, M. D. Shieh, and S. Y. Lin, “Algorithms of finding the first two minimum values and their hardware implementation,” IEEE Transactions on Circuits and Systems, pp.3430 – 3437, December 2008.
[19]C. K. Liau and C. L. Wey, “A partially parallel low-density parity check code decoder with reduced memory for long code-length,” VLSI Design/CAD Symposium, August 2007.
[20]J. J. Wu and C. L. Wey, “A partially parallel low-density parity check code decoder,” Electronic Technology Symposium, June 2009.
[21]J. Heo, “Analysis of scaling soft information on low density parity check codes,” Electronics Letters, pp. 219-221, January 2003.
[22]M. M. Mansour and N. R. Shanbhag, “High-throughput LDPC decoders,” IEEE Transactions on VLSI Systems, pp. 976-996, December 2003.
[23]Y. L. Ueng and C. C. Cheng, “A fast-convergence decoding method and memory efficient VLSI decoder architecture for irregular LDPC code in the IEEE802.16e Standards,” IEEE Semiannual Vehicular Technology Conference, pp.1125-1129, October 2007.
[24]C. Z. Zhan, X. Y. Shih, and A. Y. Wu, “High-performance scheduling algorithm for partially parallel LDPC decoder,” IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3177-3180, March 2008.
[25]X. Y. Shih, C. Z. Zhan, C. H. Lin, and A. Y. Wu, “An 8.29mm2 52mWmulti-mode LDPC decoder design for mobile WiMAX system in 0.13um CMOS process ,” IEEE Journal of Solid-State Circuits, pp. 672-683, March 2008.
[26]Y. Sun , M. Karkooti, and J. R. Cavallaro, “VLSI decoder architecture for high throughput, variable block-size and multi-rate LDPC codes,” IEEE International Symposium on Circuits and Systems, pp.2104-2107 ,May 2007.
[27]M. Karkooti, P. Radosavljevic, and J. R. Cavallaro, “Configurable, High Throughput, Irregular LDPC Decoder Architecture: Trade off Analysis and Implementation,” IEEE International Conference on Application-specific Systems, pp.73-88, November 2008.
[28]Y. L. Ueng, Y. L. Wang, C. Y. Lin, J. Y. Hsu, and P. Ting, “Modified layered message passing decoding with dynamic scheduling and early termination for QC-LDPC code,” IEEE International Symposium on Circuits and Systems, May 2009.

指導教授

魏慶隆(Chin-long Wey)

審核日期

2010-8-24

推文