跳到主要內容

臺灣博碩士論文加值系統

(35.172.136.29) 您好!臺灣時間:2021/07/26 20:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王太平
研究生(外文):Tai-PingWang
論文名稱:迴旋碼及渦輪碼解碼器架構之研究與實現
論文名稱(外文):Exploration and Development of Decoder Architecture for Convolutional Codes and Turbo Codes
指導教授:謝明得謝明得引用關係
指導教授(外文):Ming-Der Shieh
學位類別:博士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:117
中文關鍵詞:腓特比解碼器渦輪碼解碼器路徑計量值記憶體存活路徑儲存單元暫存器交換平行交錯器
外文關鍵詞:Viterbi decoderturbo decoderpath metric memorysurvivor memoryregister exchangeparallel interleaver
相關次數:
  • 被引用被引用:1
  • 點閱點閱:135
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
迴旋碼及渦輪碼被廣泛的應用於各種通訊標準中,用來更正經過傳送通道時被干擾的接收信號。在這些標準之中,關於迴旋碼及渦輪碼解碼器的實現需求都有所不同,因此須針對不同的需求來對迴旋碼及渦輪碼解碼器進行架構的改善。本論文提出不同的方法分別來符合面積或低消耗功率應用上的需求,並且基於這些技術,我們提出相應之迴旋碼及渦輪碼解碼器的架構。
在迴旋碼解碼器的實現上,腓特比演算法是最常被使用的,但是腓特比解碼器在計算複雜度上與迴旋碼的記憶深度成指數的關係,進而使得在以腓特比演算法實現迴旋碼解碼器時硬體複雜度會提高。因此,我們在路徑計量值記憶體的管理架構上推導出一有系統的計量值記憶體管理方法,所提出的架構具有因應不同腓特比解碼器規格需求而降低記憶體連接複雜度以降低硬體面積的優點。我們也研究如何降低迴旋碼解碼器的存活路徑儲存單元的功率消耗問題,存活路徑儲存單元是腓特比解碼器的一個重要單元,也是消耗功率很大的單元,我們提出一個區塊化的暫存器交換(Register Exchange)架構,有效的減少了電路中的switching activity,進而架構出此低消耗功率之存活路徑儲存單元。
最後,我們發展出符合HomePlug GP標準的平行渦輪碼解碼器之平行交錯器。在平行交錯器的實現上,其複雜度來自於多個記憶體區塊及競爭性的記憶體資料讀取,因此我們推導出HomePlug GP的交錯器是無競爭性的記憶體資料讀取,另外以單一記憶體區塊來取代多記憶區塊設計出低硬體面積與低消耗功率的架構。研究結果證明我們所實現之符合HomePlug GP標準的平行渦輪碼解碼器之平行交錯器有低消耗功率、高硬體使用率的優異效能。
The convolutional codes and turbo codes are widely applied in wireless communication systems to correct received noisy signals. Various communication standards have distinguishing requirements, thus imposing different constraints on the designs of convolutional and turbo decoders. This dissertation presents techniques to reach demands for area-efficienct and/or low-power applications. Several convolutional and turbo decoder architectures are developed for demonstrating the effectiveness of the proposed techniques.
The Viterbi algorithm is frequently adopted in realizing convolutional decoders but the computational complexity of Viterbi decoder is exponentially dependent on the memory order of the convolutional code. This increases the hardware complexity as we implement a convolutional decoder by the Viterbi algorithm. This work has successfully developed a systematic method for path metric memory management. The derived architecture can be effectively applied to reduce the interconnection complexity of the path metric memory to save area in various specifications. This dissertation also studies how to diminish the power consumption of survivor memory unit which is a critical part of the Viterbi decoder and consumes large power. A segmented register exchange architecture is proposed to effectively reduce the switching activity of circuit; thus construct a low power survivor memory unit.
Finally, an efficient parallel interleaver design method for parallel turbo decoders of HomePlug GP is proposed. The complexity of parallel interleavers depends on the adopted structure of multiple memory blocks and the way of solving memory access contention. This dissertation has successfully derived a contention-free HomePlug GP interleaver and its corresponding architecture with low hardware cost and low power consumption by using the proposed single-memory-block structure. Experimental results show that the proposed parallel interleaver for parallel HomePlug GP turbo decoder design has low power consumption and high hardware efficiency.
LIST OF FIGURES...........................................ix
LIST OF TABLES............................................xi
1. INTRODUCTION............................................1
1.1 COMMUNICATION SYSTEM AND CHANNEL CODING................1
1.2 MOTIVATION.............................................5
1.2.1 Motivation for Efficient Path Metric Memory Management for Viterbi Decoders............................6
1.2.2 Motivation for Survivor Memory Architecture for Low-power Viterbi Decoders.....................................7
1.2.3 Motivation for Low-Complexity Interleaver Design for Parallel Turbo Decoders....................................7
1.3 ORGANIZATION OF THE DISSERTATION.......................9
2. DECODER ARCHITECTURES FOR CONVOLUTIONAL CODES AND TURBO CODES.....................................................10
2.1 INTRODUCTION OF ENCODING..............................10
2.1.1 Convolutional Code Encoding.........................10
2.1.2 Turbo Coding........................................12
2.2 DECODER ARCHITECTURES.................................15
2.2.1 Viterbi Decoders....................................15
2.2.2 Turbo Code Decoders.................................22
2.3 IMPLEMENTATION ISSUES FOR VITERBI DECODERS AND TURBO CODE DECODERS.............................................27
2.4 SUMMARY...............................................30
3. AREA EFFICIENCY DESIGN METHOD ON PATH METRIC MEMORY MANAGEMENT FOR VITERBI DECODERS...........................31
3.1 INTRODUCTION..........................................31
3.1.1 Fundamentals and Definitions........................33
3.1.2 Definition of notations.............................35
3.2 CONFLICT-FREE MEMORY ACCESS...........................38
3.2.1 Formulas for Memory Partition.......................38
3.2.2 Architectures without Transposed ACSs...............41
3.2.3 Architectures with Transposed ACSs..................43
3.3 ARCHITECTURE WITH LOCAL MEMORY AND FIXED INTERCONNECT.49
3.3.1 Basic Concept of Extended In-Place Scheduling.......49
3.3.2 The Bank Mapping Relationship.......................50
3.3.3 Pseudo-Bank Design..................................54
3.3.4 Address Generation..................................56
3.3.5 Conflict-Free Architecture with Local Memory and Pseudo-Bank...............................................57
3.4 COMPARISON AND DISCUSSION.............................59
3.4.1 Complexity of the Developed Architecture............60
3.4.2 Implementation Results..............................63
3.5 SUMMARY...............................................65
4. LOW POWER DESIGN METHOD ON SURVIVOR MEMORY ARCHITECTURE FOR VITERBI DECODERS......................................66
4.1 INTRODUCTION..........................................66
4.2 BACKGROUND FOR SURVIVOR MEMORY MANAGEMENT SCHEMES.....68
4.2.1 Register Exchange (RE) Method.......................68
4.2.2 Scarce State Transition (SST) Algorithm.............69
4.2.3 Trace-Forward Unit (TFU)............................70
4.3 SEGMENTED RE STRUCTURES...............................72
4.3.1 Segmented RE Structures Using TFU_m’s...............73
4.3.2 Segmented RE Structures Using TFU_1’s...............76
4.3.3 Switching Activity Reduction........................78
4.3.4 SST Viterbi Decoders Using Segmented RE.............79
4.3.5 Examples............................................79
4.4 COMPARISON AND DISCUSSION.............................82
4.5 SUMMARY...............................................86
5. LOW-COMPLEXITY PARALLEL INTERLEAVER METHOD FOR HOMEPLUG GP TURBO DECODERS.........................................87
5.1 INTRODUCTION..........................................87
5.2 PARALLEL INTERLEAVERS.................................91
5.2.1 HomePlug GP Interleaver.............................91
5.2.2 Contention-Free HomePlug GP Interleaver.............92
5.3 PARALLEL INTERLEAVER STRUCTURES.......................95
5.3.1 M-Memory-Block Conventional Interleaver.............95
5.3.2 M-Memory-Block Contention-Free HomePlug GP Interleaver...............................................96
5.3.3 Single-Memory-Block Contention-Free HomePlug GP Interleaver...............................................98
5.3.4 Single-Memory-Block Contention-Free HomePlug GP Interleaver with Processed Seed Table....................100
5.4 COMPARISON AND DISCUSSION............................103
5.5 SUMMARY..............................................108
6. CONCLUSIONS AND FUTURE WORK...........................109
6.1 CONCLUSIONS..........................................109
6.2 FUTURE WORK..........................................112
BIBLIOGRAPHY.............................................113
[1] S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Pearson Prentice Hall, 2004.
[2] B. Sklar, Digital Communications Fundamentals and Application, 2nd ed. Prentice Hall, 2002.
[3] P. Elias, “Coding for noisy channels, IRE Conv. Rec., pp. 4:37-47, 1955.
[4] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo codes, in Proc. IEEE Int. Conf. Commun. (ICC 93), Geneva, Switzerland, May 1993, pp. 1064-70.
[5] C. Berrou and A. Glavieux, “Near optimum error correcting coding and decoding: Turbo codes, IEEE Trans. Commun., vol. 44, no. 10, pp. 1261-1271, Oct. 1996.
[6] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, IEEE Trans. Inform. Theory, IT-13: 260-69, Apr. 1967.
[7] J. K. Omura, “On the Viterbi decoding algorithm, IEEE Trans. Inform. Theory, IT-15: 177-79, Jan. 1969.
[8] G. D. Forney, Jr., “The Viterbi algorithm, in Proc. IEEE, 61: 268-78, Mar. 1973.
[9] G. D. Forney, Jr., “Convolutional codes II: Maximum likelihood decoding, Inform. Control, 25: 222-66, Jul. 1974.
[10] H. L. Lou, “Implementing the Viterbi algorithm, IEEE Signal Processing Magazine, vol. 12, pp. 42-52, Sep. 1995.
[11] I. Habib, Ö. Paker, and S. Sawitzki, “Design space exploration of hard-decision Viterbi decoding: algorithm and VLSI implementation, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 18, no. 5, pp. 794-807, May. 2010.
[12] C. Y. Tsui, R. S-K. Cheng, and C. Ling, “Low power ACS unit design for the Viterbi decoder, in Proc. IEEE Int. Symp. ISCAS'99, pp. 137-140, 1999.
[13] Z. Wang, Z. Chi, and K. K. Parhi, “Area-efficient high speed decoding schemes for turbo/MAP decoders, in Proc. 2001 IEEE Int. Conf. Acoustics, Speech and Signal Processing, Salt Lake City, UT, May 2001, pp. 2633-2636.
[14] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate, IEEE Trans. Inform. Theory, IT-20: 284-87, Mar. 1974.
[15] C. C. Wong, M. W. Lai, C. C. Lin, H. C. Chang, and C. Y. Lee, “Turbo decoder using contention-free interleaver and parallel architecture, IEEE J. Solid-State Circuits, vol. 45, no. 2, pp. 422-432, Feb. 2010.
[16] E. Boutillion, C. Douillard, and G. Montorsi, “Iterative decoding of concatenated convolutional codes: Implementation issues, Proc. IEEE, vol. 95, no. 6, pp. 1201-1227, Jun. 2007.
[17] R. Y. Shao, S. Lin, and P. C. Fossorier, “Two simple stopping criteria for turbo decoding, IEEE Trans. Commun., vol. 47, no. 8, pp. 1117-1120, Aug. 1999.
[18] G. Fettweis and H. Meyr, “Parallel Viterbi algorithm implementation: breaking the ACS-bottleneck, IEEE Trans. Commun., vol. 37, pp. 785-790, Aug. 1989.
[19] C. Y. Chang and K. Yao, “Systolic array processing of the Viterbi algorithm, IEEE Trans. Inform. Theory, vol. 35, pp. 76-86, Jan. 1989.
[20] S. C. Glinski, T. M. Lalumia, D. R. Cassiday, T. Koh, C. M. Gerveshi, A. Wilson, and J. Kumar, “A processor for graph search algorithms, in Proc. ISSCC, pp. 162-163, 1987.
[21] P. G. Gulak and E. Shwedyk, “VLSI structures for Viterbi receivers: Part I–General theory and application, IEEE J. Select. Areas Commun., vol. SAC-4, pp. 142-154, Jan. 1986.
[22] P. G. Gulak and T. Kailath, “Locally connected VLSI architectures for the Viterbi algorithm, IEEE J. Select. Areas Commun. vol. 6, pp. 527-537, Apr. 1988.
[23] G. Feygin, P. G. Gulak, and P. Chow, “A multiprocessor architecture for Viterbi decoders with linear speedup, IEEE Trans. Signal Processing, vol. 41, pp. 2907-2917, Sep. 1993.
[24] C. B. Shung, H. D. Lin, R. Cypher, P. H. Siegel, and H. K. Thapar, “Area-efficient architectures for the Viterbi algorithm–Part I: Theory, IEEE Trans. Commun., vol. 41, pp. 636-543, Apr. 1993.
[25] C. B. Shung, H. D. Lin, R. Cypher, P. H. Siegel, and H. K. Thapar, “Area-efficient architectures for the Viterbi algorithm–Part II: Applications, IEEE Trans. Commun., vol. 41, pp. 802-807, May 1993.
[26] M. Boo, F. Arguello, J. D. Bruguera, R. Doallo, and E. L. Zapata, “High-performance VLSI architecture for the Viterbi algorithm, IEEE Trans.Commun., vol. 45, pp. 168-176, Feb. 1997.
[27] D. Akopian, J. Takala, J. Saarinen, and J. Astola, “Multistage interconnection networks for parallel Viterbi decoders, IEEE Trans. Commun., vol. 51, pp. 1536-1545, Step. 2003.
[28] S. Y. Kim, H. Kim, and I. C. Park, “Path metric memory management for minimising interconnections in Viterbi decoders, Electronics Letters, vol. 37, pp. 925-926, July 2001.
[29] M. D. Shieh, M. H. Sheu, C. M. Wu, and W. S. Ju, “Efficient management of in-place path metric update and its implementation for Viterbi decoders, in Proc. ISCAS, pp. IV449-452, 1998.
[30] C. M. Rader, “Memory management in a Viterbi decoder, IEEE Trans. Commun. vol. 29, pp. 1399-1401, Sept. 1981.
[31] M. Biver, H. Kaeslin, and C. Tommasini, “In-place updating of path metrics in Viterbi decoders, IEEE J. Solid-State Circuits, vol. 24, pp. 1158-1159, Aug. 1989.
[32] F. Daneshgaran and K. Yao, “The iterative collapse algorithm: a novel approach for the design of long constraint length Viterbi decoders—Part I, IEEE Trans. Commun., vol. 43, no. 2/3/4, pp. 1409-1418, Feb./Mar./Apr. 1995.
[33] T. Järvinen, P. Salmela, T. Sipilä, and J. Takala, “Systematic approach for path metric access in Viterbi decoders, IEEE Trans. Commun., vol. 53, no. 5, pp. 755-759, May 2005.
[34] S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice-Hall, 1995.
[35] G. Feygin and P. G. Gulak, “Architectural tradoffs for survivor sequence memory management in Viterbi decoders, IEEE Trans. Commun., vol. 41, no. 3, pp. 425-429, Mar. 1993.
[36] D. J. Lin, C. C. Lin, C. L. Chen, H. C. Chanh, and C. Y. Lee, “A low-power Viterbi decoder based on scarce state transition and variable truncation length, in Proc. IEEE Int. Symp. Design Automat. Test, pp. 1-4, 2007.
[37] C. C. Lin, Y. H. Shih, H. C. Chang, and C. Y. Lee, “Design of a power-reduction Viterbi decoder for WLAN applications, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 52, no. 6, pp. 1148-1156, Jun. 2005.
[38] Y. Gang, A. T. Erdogan, and T. Arslan, “An efficient pre-traceback architecture for the Viterbi decoder targeting wireless communication applications, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 53, no. 9, pp. 1918-1927, Sep. 2006.
[39] T. Ishitani, K. Tansho, N. Miyahara, S. Kubota, and S. Kato, “A scarce-state-transition Viterbi-decoder VLSI for bit error correction, IEEE J. Solid-State Circuits, vol. 22, no. 4, pp. 575-582, Aug. 1987.
[40] F. Sun and T. Zhang, “Low-power state-parallel relaxed adaptive Viterbi decoder, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 54, no. 5, pp. 1060-1068, May 2007.
[41] S. Kubota and S. Kato, “Novel Viterbi decoder VLSI implementation and its performance, IEEE Trans. Commun., vol. 41, no. 8, pp. 1170-1178, Aug. 1993.
[42] M. Kamuf, V. Öwall, and J. B. Aderson, “Survivor path processing in Viterbi decoders using register exchange and traceforward, IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 54, no. 6, pp. 537-541, Jun. 2007.
[43] J. Jin and C. Y. Tsui, “Low-power limited-search parallel state Viterbi decoder implementation based on scarce state transition, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 15, no. 10, pp. 1172-1176, Oct. 2007.
[44] P. J. Black and T. H. -Y. Meng, “Hybrid survivor path architectures for Viterbi decoders, in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process, pp. 433-436, 1993.
[45] HomePlug Green PHY, homeplug powerline alliance. Available: http://www.homeplug.org.
[46] Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE Std 802.16, Oct. 2004.
[47] Technical Specification Group Radio Access Network, the 3rd generation partnership project (3GPP). Available: http://www.3gpp.org.
[48] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error correcting coding and decoding: turbo codes, in Proc. IEEE Int. Conf. on Commun., Geneva, Switzerland, May 1993, pp. 1064-1070.
[49] Y. Sun, Y. Zhu, M. Goel, and J. Cavallaro, “Configurable and scalable high throughput turbo decoder architecture for Multiple 4G wireless standards, in Proc. 19th IEEE Int. Conf. on Application-specific Systems, Architectures, and Processors., Leuven, Belgium, Jul. 2008, pp. 209-214.
[50] Z. Wang, and Q. Li, “Very low-complexity hardware interleaver for turbo decoding, IEEE Trans. Circuits Sys. II, Exp. Briefs, vol. 54, no. 7, pp. 636-640, Jul. 2007.
[51] R. Dobkin, M. Peleg, and R. Ginosar, “Parallel interleaver design and VLSI architecture for low-latency MAP turbo decoders, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 13, no. 4, pp. 427-438, Apr. 2005.
[52] O. Y. Takeshita, and D. J. Costello, Jr., “New deterministic interleaver designs for turbo codes, IEEE Trans. Inf. Theory, vol. 46, no. 6, pp. 1988-2006, Sep. 2000.
[53] A. Nimbalker, T. K. Blankenship, B. Classon, T. E. Fuja, and D. J. Costello, Jr., “Contention-free interleavers for high-throughput turbo decoding, IEEE Trans. Commun., vol. 56, no. 8, pp. 1258-1267, Aug. 2008.
[54] S. G. Lee, C. H. Wang, and W. H. Sheen, “Architecture design of QPP interleaver for parallel turbo decoding, in Proc. IEEE Vehic. Tech. Conf., Taipei, May 2010, pp. 1-5.
[55] T. K. Blankenship, B. Classon, and V. Desai, “High-throughput turbo decoding techniques for 4G, in Proc. Int. Conf. Third Generation Wireless and Beyond, San Francisco, CA, USA, May 2002, pp. 137-142.
[56] Artisan Components, TSMC 0.18-μm Process 1.8-Volt SAGE-XTM Standard Cell Library Databook, Sunnyvale, CA, 2003.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top