請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/59004
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳少傑(Sao-Jie Chen) | |
dc.contributor.author | Ho-Sheng Chuang | en |
dc.contributor.author | 莊和昇 | zh_TW |
dc.date.accessioned | 2021-06-16T08:43:57Z | - |
dc.date.available | 2013-09-02 | |
dc.date.copyright | 2013-09-02 | |
dc.date.issued | 2013 | |
dc.date.submitted | 2013-08-22 | |
dc.identifier.citation | [1]R. G. Gallager, “Low Density Parity Check Codes,” IRE Trans. Information 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]S. Y. Chung, G. D. Forney, T. J. Richardson, and R. L. Urbanke “On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit” IEEE Communication Letters, vol. 5, no. 2, p58-60, Feb. 2001. [4]A. J. Blanksby and C. J. Howland, “A 690-mW-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. [5]R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Information Theory, vol. IT-27, no. 5, pp. 533–547, Sep. 1981. [6]T. J. Richardson and R. L. Urbanke,” Efficient Encoding of Low-Density Parity-Check Codes”, IEEE Trans. on Information Theory, vol. 47, no. 2, pp. 638-656, Feb. 2001. [7]M. P. C. Fossorier, M. Mihaljevi’c, and H. Imai, ” Reduced Complexity Iterative Decoding of Low-Density Parity Check Codes Based on Belief Propagation”, IEEE Trans. Communications, vol. 47, no. 5, pp.673-680, May 1999. [8]Y. Kou, S. Lin, and M. P. C. Fossorier, “Low Density Parity-Check Codes based on Finite Geometries: a Rediscovery and New Results,” IEEE Trans. on Information Theory, vol. 47, no. 7, pp. 2711–2736, Nov. 2001. [9]J. C. Moreira and P. G. Farrell, Essentials of error-control coding, Wiley 2006, pp. 277-324. [10]S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Pearson Prentice Hall, 2004, p.66-98. [11]B. Xiang, D. Bao, S. Huang, and X. Y. Zeng, “An 847–955 Mb/s 342–397 mW Dual-Path Fully-Overlapped QC-LDPC Decoder for WiMAX System in 0.13μm CMOS,” IEEE Journal of Solid-State Circuits, vol. 46, no. 6, pp. 1416-1432, Jun. 2011. [12]T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,” IEEE Trans. on Information Theory, vol. 47, no. 2, pp. 619-637, Feb. 2001. [13]J. Heo, K. Chung, and K.M. Chugg, “Simple Stopping Criterion for Min-Sum Iterative Decoding Algorithm,” IEE Electronics Letters, vol. 37, No. 25, pp.1530-1531, Dec. 2001. [14]F. Kienle and N. Wehn, “Low Complexity Stopping Criterion for LDPC Codes Decoders,” in Proc. IEEE on Vehicular Technology Conference, vol. 1, pp.606-609, June 2005. [15]P. Radosavljevic, A. Baynast, de, and J. R. Cavallaro, “Optimized Message Passing Schedules for LDPC Decoding,” Asilomar Conf. on Signals, Systems and Computers (IEEE), pp. 591–595, Oct. 2005. [16]X. Y. Shih, C. Z. Zhan, and A.Y. (Andy) Wu, “A Real-Time Programmable LDPC Decoder Chip for Arbitrary QC-LDPC Parity Check Matrices,” IEEE Asian Solid-State Circuits Conference, pp.369-372, Nov. 16-18, 2009. [17]I. Park and S. Kang, 'Scheduling Algorithm for Partially Parallel Architecture of LDPC Decoder by Matrix Permutation,' IEEE Int. Symp. on Circuits and Systems (ISCAS), vol. 6, pp. 5778-5781, May 2005. [18]B. Xiang, R. Shen, A. Pan, D. Bao, and X. Y. Zeng, “An Area-Efficient and Low-Power Multirate Decoder for Quasi-Cyclic Low-Density Parity-Check Codes,” IEEE Trans. on VLSI Systems, vol. 18, no. 10, pp.1447-1460, Oct. 2010. [19]J. Jin and C.Y. Tsui, “An Energy Efficient Layered Decoding Architecture for LDPC Decoder,” IEEE Trans. on VLSI Systems, vol. 18, no. 8, pp. 1185-1195, Aug. 2010. [20]A. Darabiha, A. C. Carusone, and F. R. Kschischang,” Power Reduction Techniques for LDPC Decoders,” IEEE Journal of Solid-State Circuits, vol. 43, no. 8, pp.1835-1845, Aug 2008. [21]X. Y. Shih, C. Z. Zhan, C. H. Lin, and A. Y. (Andy) Wu, “An 8.29 mm^2 52 mW Multi-Mode LDPC Decoder Design for Mobile WiMAX System in 0.13 μm CMOS Process,” IEEE Journal of Solid-State Circuits, vol. 43, no. 3. pp.672- 683, Mar. 2008. [22]S. Timakut, I. Tanyanont, and S. Choomchuayft, “An Overlapping Min-Sum LDPC Decoder for IEEE 802.11n,” International Symposium on Intelligent Signal Processing and Communication Systems (lSPACS 2010), pp. 1-4, Dec, 6-8, 2010. [23]C. L. Wey, M. D. Shieh, and S. Y. Lin “Algorithms of Finding the First Two Minimum Values and their Hardware Implementation,” IEEE Trans. on Circuits and Systems—I: Regular Papers, vol. 55, no. 11, pp. 3430-3437, Dec. 2008. [24]S. Kim, G. E. Sobelman, and H. Lee “A Reduced-Complexity Architecture for LDPC Layered Decoding Schemes' IEEE Trans. on VLSI Systems, vol. 19, no. 6, pp. 1099-1103, Jun. 2011. [25]D. Bao, B. Xiang, R. Shen, A. Pan, Y. Chen, and X. Y. Zeng, “Programmable Architecture for Flexi-mode QC-LDPC Decoder Supporting Wireless LAN/MAN Applications and Beyond,” IEEE Trans. Circuits Syst. I, vol. 57, no. 1, pp. 125-138, Jan. 2010. [26]C. H. Liu, C. C. Lin, S. W. Yen, C. L. Chen, H. C. Chang, C. Y. Lee, Y. S. Hsu, and S. J. Jou, “Design of a Multimode QC-LDPC Decoder based on Shift-Routing Network,” IEEE Trans. on Circuits and Systems-II, vol. 56, no. 9, pp. 734-738, Sep. 2009. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/59004 | - |
dc.description.abstract | 早期受限於當時電腦計算能力不夠,使得這個演算法未受到應有的重視。然隨著電腦運算能力大幅成長,以及製程技術越來越先進。低密度同位檢查碼再度引起熱烈的討論。解碼器架構大致可分兩種:全平行(Fully-parallel)和部分平行(Partial-parallel)。其中部分平行又會因為平行度和平行方式的不同,又有一些類別。
在本論文中,我們採用部分平行區塊式架構進行設計低密度同位元檢查解碼器。為了改善Xiang學者所提出的架構,我們提出三個改良的方法:首先我們藉由重組處理和儲存的順序,縮短了解碼器的關鍵路徑(Critical Path),執行速度提升約11%。第二,當解碼器在儲存事前對數概似比(Prior Log Likelihood Ratio)的同時,即運算第一個檢查點(Check Node),此舉可節省執行所需的周期數約3%。第三,我們改進了偵測收斂的方法,而省去儲存上個迴圈的解碼結果,故可以節省原儲存對數概似比記憶體需求的11%。最後我們將跟過去的文獻做比較,在802.11n的規範下,我們的解碼器面積比較小且節省功率消耗。 | zh_TW |
dc.description.abstract | Gallager published Low Density Parity Check (LDPC) code in 1963. Since the computation power is so weak at that time, LDPC has not been paid much attention. However, LDPC has become an important technique because of advanced semiconductor technology that increases gradually the computation power. The architecture of LDPC decoder can be simply divided into two kinds: fully-parallel and partial-parallel schemes. There are some variations on the partial-parallel schemes depending on their parallelization methods.
In this Thesis, we used a block-serial architecture for the implementation of an LDPC decoder, which has three improvements compared with previous work proposed by Xiang. The first is to shorten the critical path by reordering the process step and the storing step, which can facilitate an 11% improvement in the clock rate. The second is that the decoder updates the first check node message while it is storing the Log-Likelihood Ratio (LLR) data. As a result, the proposed design saves 3% clock cycles than the previous work. The third is that this work improves the algorithm of detecting convergence, which can avoid saving the last iteration result. Therefore, the storage space required to save the LLR can be reduced to 11% of the original size. Finally, the performance evaluation with other previous works was made to validate that the proposed design is having smaller chip area and less power dissipation. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T08:43:57Z (GMT). No. of bitstreams: 1 ntu-102-R99943166-1.pdf: 5375332 bytes, checksum: 41f0c8057aae613cc68d75c91702b4aa (MD5) Previous issue date: 2013 | en |
dc.description.tableofcontents | ABSTRACT i
LIST OF FIGURES vii LIST OF TABLES ix CHAPTER 1 INTRODUCTION 1 1.1 Overview of Digital Communication System 1 1.2 Overview of Channel Coding 2 1.3 History of LDPC Codes 2 1.4 Motivation 3 1.5 Thesis Organization 3 CHAPTER 2 REVIEW OF LDPC 5 2.1 Definition 5 2.2 Graph Representation 6 2.3 Richardson-Urbanke Encoding Algorithm 7 2.4 Decoding Algorithms 8 2.4.1 Bit-Flipping Algorithm 9 2.4.2 Sum-Product Algorithm 10 2.4.3 Log-domain Sum-Product Algorithm 14 2.4.4 Minimum-Sum Algorithm 16 2.5 Stopping Criterion 17 2.5.1 Parity-Check 17 2.5.2 Hard-Decision Comparison 17 2.5.3 Variable Node Reliability 17 2.6 Decoding Scheduling 18 2.6.1 Two-phase Decoding Scheduling 19 2.6.2 Turbo Decoding Message Passing Scheduling 19 2.6.2.1 Horizontal Scheduling 20 2.6.2.2 Vertical Scheduling 22 CHAPTER 3 ARCHITECTURE OF LDPC DECODER 23 3.1 Fully-parallel Architecture 23 3.2 Partial-parallel Architecture 24 3.3 Overlapping the Process 26 3.4 Parallel Strategy 29 3.4.1 Correlation is Zero 29 3.4.2 Correlation is not Zero 31 3.4 Summary 32 CHAPTER 4 IMPLEMENTATION OF LDPC DECODER 35 4.1 Review of LDPC Decoder 35 4.2 Proposed Architecture 35 4.3 Symmetrical Pipelining 37 4.4 Matrix Interleaving and Reordering 38 4.4.1 Data Dependency 38 4.4.2 Access Conflict 39 4.4.3 Summary of Matrix Interleaving and Reordering 40 4.5 Architecture of LLR Memory 43 4.6 Architecture of Recovery Unit 44 4.7 Architecture of CNU 45 4.8 Architecture of VNU 46 4.9 Early Termination 48 4.10 Early Process 49 CHAPTER 5 EXPERIMENTAL RESULTS 51 5.1 LDPC Simulation 51 5.1.1 BER of SPA and MSA 51 5.1.2 BER of TPMP and TDMP 51 5.1.3 Number of Max Iterations 53 5.1.4 Early Termination 53 5.2 Synthesis of VNU and CNU 54 5.3 Implementation Results 54 5.3.1 Verilog Simulation Results 55 5.3.2 TSMC 90nm 55 5.3.3 TSMC 180nm 56 5.4 Comparison 57 CHAPTER 6 CONCLUSION 59 REFERENCE 61 | |
dc.language.iso | en | |
dc.title | 適用於802.11n之低密度同位檢查解碼器晶片設計 | zh_TW |
dc.title | Chip Design of a Low Density Parity Check Decoder for IEEE 802.11n | en |
dc.type | Thesis | |
dc.date.schoolyear | 101-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 游竹(Chu Yu) | |
dc.contributor.oralexamcommittee | 林茂昭,顧孟愷 | |
dc.subject.keyword | 低密度同位檢查碼,收斂,最小和演算法,區塊式解碼器,提早處理,降低關鍵路徑, | zh_TW |
dc.subject.keyword | Low Density Parity Check (LDPC),Convergence,Min-Sum Algorithm,Block-serial Decoder,Early Process,Shorting Critical Path, | en |
dc.relation.page | 63 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2013-08-22 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf 目前未授權公開取用 | 5.25 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。