成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	唐興中 Tang, Shing-Chung
論文名稱：	一種針對低複雜度低密度同位元檢查碼解碼器設計之創新記憶體配置技術 A Novel Memory Arrangement Scheme for Low-Complexity LDPC Decoder Design
指導教授：	謝明得 Shieh, Ming-Der
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2009
畢業學年度：	97
語文別：	中文
論文頁數：	99
中文關鍵詞：	記憶體編組、半平行、解碼器、低密度同位元檢查碼、錯誤更正碼
外文關鍵詞：	Error control coding, decoder, low-density parity-check(LDPC) code, memory arrangement, partially-parallel
相關次數：	點閱：125 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

低密度奇偶檢查(Low-Density Parity-Check, LDPC)碼解碼器的架構設計上，記憶體佔了解碼器大半的面積，因此若能有效的降低解碼器中的記憶體的面積，則能夠大幅改善低密度奇偶檢查解碼器的設計。為了提高解碼器之運算之平行度，傳統部分平行架構使用了許多小容量記憶體區塊，但根據一般的記憶體設計原則，在組成相同容量記憶體情況下，利用小容量記憶體區塊來組成其所佔的面積會比利用大容量記憶體區塊來的大。此外，小容量記憶體區塊功率消耗上亦會較大。基於此概念，本論文中首先提出了如何合併小容量記憶體區塊，並且提出了一套記憶體資料存取機制來解決此架構下資料存取的問題。隨後，我們提出了記憶體區塊選擇演算法，透過此演算法我們可減少記憶體群組個數及額外所付出的硬體成本。最後從實驗結果可得知，我們所提出的架構具有低複雜度與低功率消耗之優點。

Memory management plays an important role in system/component designs and it is not surprised that memory occupies a large portion of the chip area in pervasive electronic products now. In this work, we propose an efficient memory management scheme for low-density parity-check (LDPC) decoders. The aim is to reduce the total area of memory requirement in conventional partially-parallel architectures of LDPC decoders, in which a plenty of small memory blocks employed to increase the parallelism of memory access. The basic principle behind our development is from the observation that the chip area of a
memory size constructed from a set of smaller memory blocks is larger than that of the same capacity but built from a set of larger memory blocks. In addition, the former also
consumes more power than the latter according to our experiments.

This thesis explores techniques to efficiently combine small memory blocks into larger ones and proposes a FIFO-based access scheme to solve the problem of concurrent memory access in the developed architecture. Moreover, a memory blocks selection algorithm is presented to reduce the number of memory groups so that the number of additional delay elements can be minimized. Experimental results show that the proposed architecture reveals the advantages of low complexity and low power dissipation compared with the related studies.

第一章 緒論.............................................................................................................1
1 數位通訊系統上的錯誤控制碼................................................................1
2 動機..........................................................................................................3
3 論文大綱...................................................................................................4
第二章 研究背景......................................................................................................6
1 同位元檢查矩陣.......................................................................................6
2 LDPC編碼.................................................................................................8
3 LDPC解碼.................................................................................................9
3.1 機率域的積和演算法.......................................................................9
3.2 對數域的積和演算法.....................................................................17
4 類循環LDPC碼.....................................................................................20
5 部分平行的LDPC解碼器架構..............................................................23
5.1 檢查點運算單元.............................................................................25
5.2 變數點運算單元.............................................................................27
5.3 部分平行架構的資料運算流程.....................................................27
第三章 記憶體的組合架構與方法.........................................................................31
1 記憶體合併的定義.................................................................................31
2 記憶體儲存方式的定義..........................................................................32
3 檢查點運算和變數點運算階段的資料存取...........................................34
3.1 記憶體資料存取架構與方法.........................................................36
3.2 記憶體資料讀取順序.....................................................................38
3.3 記憶體資料寫入順序.....................................................................43
3.4 一般數學算式表示.........................................................................49
4 LDPC碼範例...........................................................................................52
第四章 記憶體單元組合方法................................................................................55
1 縮小相對延遲dR(Mj,k) ...........................................................................55
2 非列區塊合併的資料存取問題..............................................................57
3 記憶體編組演算法.................................................................................62
4 取捨分析.................................................................................................66
第五章 運算階段重疊架構....................................................................................68
1 運算階段重疊分析.................................................................................68
1.1 起始索引選取策略.........................................................................68
1.2 潛在的冗餘等待.............................................................................70
1.3 起始索引偏移方法.........................................................................71
2 運算階段重疊的運算單元架構..............................................................75
2.1 資料存取頻寬之瓶頸.....................................................................75
2.2 提出的運算單元架構.....................................................................75
2.3 運算單元之包裝介面設計.............................................................77
第六章 硬體實現與驗證........................................................................................79
1 硬體設計架構.........................................................................................79
1.1 記憶體架構....................................................................................80
1.2 運算單元設計................................................................................80
1.3 內部連線單元及資料暫存單元.....................................................82
1.4 終止條件檢查方法與裝置.............................................................83
1.5 記憶體位址產生與控制單元.........................................................84
2 電路驗證方法.........................................................................................85
第七章 實驗結果與比較........................................................................................87
1 電路實現數據.........................................................................................87
1.1 挑選過的欄 / 列起始索引............................................................87
1.2 運算階段重疊(運算單元減半).......................................................89
2 實現結果數據與比較..............................................................................91
第八章 結論與未來方向........................................................................................94
1 結論........................................................................................................94
2 未來方向.................................................................................................95
參考文獻.................................................................................................................97
                                    

[1] R.G. Gallager, “Low-density parity check codes,” IRE Transactions on Information Theory, Volume IT-8, pp.21-28, 1962.
[2] S.Y. Chung, G. D. Forney, Jr., T. J. Richardson, and R. Urbanke, “On the design of low density parity check codes within 0.0045 dB of the shannon limit,” IEEE Commun. vol. 5, no. 2, pp. 58-60, Feb, 2001.
[3] IEEE 802.11 Wireless LANs WWiSE Proposal: High Throughput extension to the 802.11, IEEE Std. 11-04-0866-00-000n.
[4] Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems-Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1, IEEE Std 802.16e-2005 Std.
[5] F. Kienle, T. Brack, and N. Wehn, “A synthesizable IP core for DVB-S2 LDPC code decoding,” in Proc. IEEE Conference of Design, Automation and Test in Europe, vol. 3, pp. 100–105, Mar. 2005.
[6] Z.W. Li, L. Chen, L. Zeng, S. Lin, and W. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” in Proc. IEEE Globecom, vol. 3, pp.6, 28, Nov.-2 Dec. 2005.
[7] Z.W. Li, L. Chen, L. Zeng, S. Lin, and W.H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” IEEE Transactions on Communications, vol. 54, no. 1, pp.71-81, Jan. 2006.
[8] D.E. Hocevar, “Efficient encoding for a family of quasi-cyclic LDPC codes,” in Proc. IEEE Globecom, vol. 7, 1-5, pp.3996-4000, Dec. 2003.
[9] D. J. C. MacKay and R. M. Neal, “Near shannon limit performance of low-density parity check codes,” Electron. Lett., vol. 32, p. 1645, 1996.
[10] S. Lin and D. J. Costello, Error Control Coding Fundamentals and Applications Second Edition, 2004.
[11] L. Chen, J. Xu, I. Djurdjevic, and S. Lin, “Near-shannon-limit quasi-cyclic low-density parity-check codes,” IEEE Trans. Commun, vol. 52, no. 7, pp. 1038–1042, July 2004.
[12] Z. Li, L. Chen, L. Zeng, S. Lin, and W. H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes,” IEEE Trans. Commun., vol. 54, no. 1, pp. 71–81, Jan. 2006.
[13] R. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory, vol. 27, no. 5, pp. 533–547, Sep 1981.
[14] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399–431, Mar. 1999.
[15] M. P. C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low density parity check codes based on belief propagation,” IEEE Trans. Commun. Lett., vol. 47, no. 5, pp. 673–680, May 1999.
[16] J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Y. Hu, “Reduced-complexity decoding of LDPC codes,” IEEE Trans. Commun., vol. 53, no. 8, pp. 1288-1299, Aug. 2005.
[17] A. J. Blanksby and C. J. Howland, “A 690-mW 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder,” IEEE J. Solid-State Circuits, vol. 37, no. 3, pp. 404–412, Mar. 2002.
[18] Y. Cheng and K. K. Parhi, “Overlapped message passing for quasi-cyclic low-density parity check codes,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 51, no. 6, pp. 1106–1113, Jun. 2004.
[19] Y. Dai, Z. Yan, and N. Chen, “Optimal overlapped message passing decoding of quasi-cyclic LDPC codes,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 16, no. 5, pp. 565–578, May 2008.
[20] Z. Wang and Z. Cui, “Low-complexity high-speed decoder design for quasi-cyclic LDPC codes,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 15, no. 1, pp. 104–114, Jan. 2007.
[21] S.-H. Kang and I.-C. Park, “Loosely coupled memory-based decoding architecture for low density parity check codes,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 53, no. 5, pp. 1045–1056, May 2006.
[22] H. Zhong, W. Xu, N. Xie, and T. Zhang, “Area-efficient min-sum decoder design for high-rate quasi-cyclic low-density parity-check codes in magnetic recording,” IEEE Trans. Magnetics, vol. 43, no. 12, pp. 4117–4122, Dec. 2007.
[23] X.-Y. Shih, C.-Z. Zhan, and A.-Y. Wu, “An 8.29 mm2 52 mW multi-mode LDPC decoder design for mobile WiMAX system in 0.13μm CMOS process,” IEEE J. Solid-State Circuits, vol. 43, no. 3, pp. 672–683, Mar. 2008.
[24] L. Yang, H. Liu, and C.-J. R. Shi, “Code construction and FPGA implementation of a low-error-floor multi-rate low-density parity-check code decoder,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 53, no. 4, pp. 892–904, Apr. 2006.
[25] M. M. Mansour and N. R. Shanbhag, “A 640-Mb/s 2048-bit programmable LDPC decoder chip,” IEEE J. Solid-State Circuits, vol. 41, no. 3, pp. 684–698, Mar. 2006.
[26] L. Zhang, L. Gui, Y. Xu, and W. Zhang, “Configurable multi-rate decoder architecture for QC-LDPC codes based broadband broadcasting system,” IEEE Trans. Broadcast., vol. 54, no. 2, pp. 226–235, June 2008.
[27] C.-H. Liu, S.-W. Yen, C.-L. Chen, H.-C. Chang, C.Y. Lee, Y.-S. Hsu, and S.J. Jou, “An LDPC decoder chip based on self-routing network for IEEE 802.16e applications,” IEEE J. Solid-State Circuits, vol. 43, no. 3, pp. 684–694, Mar. 2008.
[28] Artisan Components, Sunnyvale, CA, Artisan standard library register file generator user manual, 2004.

校內：2014-08-27公開
校外：2014-08-27公開

簡易檢索 / 詳目顯示

相關論文