(3.236.214.19) 您好!臺灣時間:2021/05/07 12:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:莊和昇
研究生(外文):Ho-Sheng Chuang
論文名稱:適用於802.11n之低密度同位檢查解碼器晶片設計
論文名稱(外文):Chip Design of a Low Density Parity Check Decoder for IEEE 802.11n
指導教授:陳少傑陳少傑引用關係
指導教授(外文):Sao-Jie Chen
口試委員:林茂昭顧孟愷
口試日期:2013-06-26
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:63
中文關鍵詞:低密度同位檢查碼收斂最小和演算法區塊式解碼器提早處理降低關鍵路徑
外文關鍵詞:Low Density Parity Check (LDPC)ConvergenceMin-Sum AlgorithmBlock-serial DecoderEarly ProcessShorting Critical Path
相關次數:
  • 被引用被引用:1
  • 點閱點閱:227
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
早期受限於當時電腦計算能力不夠,使得這個演算法未受到應有的重視。然隨著電腦運算能力大幅成長,以及製程技術越來越先進。低密度同位檢查碼再度引起熱烈的討論。解碼器架構大致可分兩種:全平行(Fully-parallel)和部分平行(Partial-parallel)。其中部分平行又會因為平行度和平行方式的不同,又有一些類別。
在本論文中,我們採用部分平行區塊式架構進行設計低密度同位元檢查解碼器。為了改善Xiang學者所提出的架構,我們提出三個改良的方法:首先我們藉由重組處理和儲存的順序,縮短了解碼器的關鍵路徑(Critical Path),執行速度提升約11%。第二,當解碼器在儲存事前對數概似比(Prior Log Likelihood Ratio)的同時,即運算第一個檢查點(Check Node),此舉可節省執行所需的周期數約3%。第三,我們改進了偵測收斂的方法,而省去儲存上個迴圈的解碼結果,故可以節省原儲存對數概似比記憶體需求的11%。最後我們將跟過去的文獻做比較,在802.11n的規範下,我們的解碼器面積比較小且節省功率消耗。

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.


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


[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.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔