臺灣博碩士論文加值系統

自九零年代初渦輪碼被發現以來，由於出色的錯誤更正能力一直以來廣泛的引起研究者的注意，在近期寬頻無線通訊以及第四代行動通訊等協定中，對於高速渦輪碼的資料流量的要求，也分別訂定了每秒70Mb以及每秒20Mb到100Mb的高速傳輸量，因此，對於高速渦輪碼的需求也與日俱增。而在渦輪碼的解碼中，由於尋找最大事後機率的解碼方式中，含有遞迴式的計算方式，也因此造成了在渦輪碼的解碼中，產生了很可觀的時間延遲。在這篇論文當中，針對高速的渦輪碼解碼，我們提出了一個完整的解決方案，其中，包含一個資料讀寫平順無誤的打散器設計，一個多級高階的渦輪解碼器，以及提出ㄧ種能夠運用在兩個維度的平行解碼器架構，由於這些因素，使得我們在本論文中所提出的設計，與現今科技之水準比較下，達到最高的能源效率以及每秒的資料解碼量，達到最高的水準。

Turbo codes have received a lot of interest since 90’s because of their excellent performance. To apply turbo codes in high-speed digital communications, such as in broadband wireless access based on the IEEE 802.16 standard supporting data rates of up to 70 Mb/s, and in fourth generation cellular systems, which are expected to provide a data rate from 20 to 100 Mb/s for high mobility, high throughput of turbo codes is a critical issue. The recursive computations in the MAP-based decoding of turbo codes usually introduce a significant amount of decoding delay. In this thesis, we present a total solution for a high throughput application, including a contention-free interleaver design, a high radix turbo decoder design, and the two-dimension parallel decoding architecture. The chip proposed in this thesis is the most power efficient and the fastest design in the state of the art.

ABSTRACT IV
CONTENTS VI
LIST OF FIGURES IX
LIST OF TABLES XII
CHAPTER 1 INTRODUCTION 1
1.1 MOTIVATION 1
1.2 THESIS ORGANIZATION 3
CHAPTER 2 TURBO CODE 4
2.1 PRINCIPLE OF TURBO CODE 4
2.1.1 Turbo Encoding 4
2.1.2 Turbo Interleaver 6
2.1.3 Turbo Decoding 6
2.1.4 Error floor effect 7
2.2 DECODING ALGORITHMS FOR TURBO CODE 8
2.2.1 The MAP algorithm 8
2.2.2 The Log-MAP algorithm 12
2.2.3 The Max-Log-MAP algorithm 13
2.2.4 SNR sensitivity of Max-Log-MAP and Log-MAP algorithm 15
2.3 SLIDING WINDOW APPROACH 15
2.4 TAIL-BITING APPROACH 18
2.4.1 Encoding tail-biting codes using feedback encoders 19
CHAPTER 3 THE HIGH SPEED TURBO DECODER DESIGN I 21
3.1 INTRODUCTION 21
3.2 DECODER STRUCTURE 22
3.3 INTERLEAVER DESIGN FOR HIGH SPEED TURBO CODE 23
3.3.1 Contention-free Interleaver 23
3.3.2 IBP Interleaver 25
3.3.3 Butterfly network 25
3.3.4 Double prime interleaver 26
3.4 HIGH-THROUGHPUT MAP DECODERS 27
3.4.1 Retimed radix-2x2 ACS unit 27
3.4.2 The circuit for log-likelihood ratio calculation 29
3.5 SIMULATION RESULT AND CHIP IMPLEMENTATION 29
3.6 SUMMARY 34
CHAPTER 4 THE HIGH SPEED TURBO DECODER DESIGN II 35
4.1 INTRODUCTION 35
4.1.1 Data Hazards 35
4.1.2 A dummy sub-block 36
4.2 DECODING SCHEDULE 37
4.2.1 Decoding with two codewords 37
4.3 MAP DECODERS 39
4.3.1 The structure of each processing element. 39
4.3.2 The memory units 41
4.3.3 Retime or not retime 41
4.4 INTERLEAVER DESIGN 43
4.4.1 Multiple block lengths support 44
4.5 CHIP IMPLEMENTATION 44
4.6 SUMMARY 47
CHAPTER 5 HIGHLY PARALLEL DECODING OF TURBO CODE 48
5.1 A SECTIONALIZED METHOD FOR PARALLEL DECODING 49
5.1.1 A sectionalized method 49
5.1.2 Parallel decoding with the sectionalized method 51
5.2 PROPOSED ARCHITECTURES 51
5.2.1 A two-dimension parallel architecture 52
5.2.2 A intra-codeword parallel architecture 52
5.2.3 Data hazards 53
5.3 PERFORMANCE ANALYSIS 54
5.4 PROPOSED METHOD TO IMPROVE PERFORMANCE 57
5.5 DECODING SCHEDULE 59
5.6 HARDWARE COMPARISON 61
5.7 SUMMARY 63
CHAPTER 6 CONCLUSION AND FUTURE WORK 64
6.1 CONCLUSION 64
6.2 FUTURE WORK 65
BIBLIOGRAPHY 66

[1] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error- correcting coding and decoding: Turbo-codes (1),” in Proc. IEEE Int. Conf. on Commun., Geneva, Switzerland, May 1993, pp. 1064–1070.
[2] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol,” IEEE Trans. Inform. Theory, no. IT-20, pp. 284–287, Mar. 1974.
[3] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inform. Theory, vol. 42, no. 2, pp. 429-445, Mar. 1996.
[4] J. Hagenauer and P. Hoeher, “A Viterbi Algorithm with Soft-decision Outputs and its Applications,” in IEEE GLOBE-COM, Dallas, TX, pp. 47.1.1-47.1.7, Nov. 1989.
[5] G. Solomon and H. C. A. van Tilborg, “A connection between block and convolutional codes,” SIAM J. Appl. Math., vol. 37, pp. 358–369, Oct. 1979.
[6] H. H. Ma and J. K. Wolf, “On tail biting convolutional codes,” IEEE Trans. Commun., vol. COM-34, pp. 104–111, Feb. 1986.
[7] C. Weiss, C. Bettstetter, S. Riedel, and D. J. Costello, “Turbo decoding with tailbiting trellises,” in Proc. URSI Int. Symp. Signals, Systems, Electronics, 1998, pp. 343–348.
[8] C. Weiss, C. Bettstetter, and S. Riedel, “Code construction and decoding of parallel concatenated tail-biting codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 366-386, Jan. 2001.
[9] J. Sun and O. Y. Takeshita, ”Interleavers for Turbo codes using permutation polynomials over integer rings,” IEEE Trans. Inform. Theory, vol. 51, no. 1, pp. 101-119, Jan. 2005.
[10] P. Robertson, E.Villebrun and P. Hoeher, “A Comparison of Optimal and Sub-optimal MAP Decoding Algorithms operating in the Log Domain,” Proc. ICC’95, Seattle, June 1995.
[11] M. Bickerstaff, L. Davis, C. Thomas, D. Garrett, and C. Nicol, “A 24Mb/s radix-4 logMAP turbo decoder for 3GPP-HSDPA mobile wireless,” in ISSCC Dig. Tech. Papers, 2003, pp. 151–484.
[12] B. Bougard, A. Giulietti, V. Derudder, J. Willem, S. Dupont, L. Hollevoet, F. Catthoor, L. V. der Perre, H. D. Man, and R. Lauwereins, “A scalable 8.7nj/bit 75.6Mb/s parallel concatenated convolutional (turbo-)codec,” in ISSCC Dig. Tech. Papers, 2003, pp. 152–484.
[13] Y. Zheng, “Network for permutation or de-permutation utilized by channel coding algorithm,” U.S. Patent Pending.
[14] C. H. Tang, C. C. Wong, C. L. Chen, C. C. Lin, and H. C. Chang, “A 952Mb/s Max-Log MAP decoder chip using radix-4×4 ACS architecture,” in IEEE A-SSCC, 2006, pp. 79–82.
[15] C. B. Shung, P. H. Siegel, G. Ungerboeck, and H. K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm,” in Int. Conf. Communications, vol. 4, Atlanta, CA, Apr. 1990, pp. 1723–1728.
[16] P. Urard, L. Paumier, M. Viollet, E. Lantreibecq, H. Michel, S. Muroor, and B. Gupta, “A generic 350Mb/s turbo-codec based on a 16-states SISO decoder,” in ISSCC Dig. Tech. Papers, 2004, pp. 424–536.
[17] Z. He, P. Fortier, and S. Roy, “Highly parallel decoding architectures for convolutional turbo codes,” IEEE Trans. VLSI Syst., vol. 14, no. 10, Oct. 2006.
[18] S. Yoon, and Y. Bar-Ness, “A Parallel MAP Algorithm for Low Latency Turbo Decoding,” IEEE Commun. Lett., vol. 6, no. 7, pp.288-290, Jul. 2002.
[19] J. H. Andersen, “‘Turbo’ Coding for Deep Space Application,” in IEEE International Symposium on Inform. Theory, 17-22, pp.36, Sep. 1995.
[20] D.Divsalar, S. Dolinar, R. J. McEliece, and F. Pollara, “Performance Analysis of Turbo Codes,” in IEEE Military Communication conf., vol. 1, 5-8, pp. 91-96, Nov. 1995.
[21] J. Hagenauer and P. Hoeher, “A Viterbi Algorithm with Soft-decision Outputs and its Applications,” in IEEE GLOBE-COM, Dallas, TX, pp. 47.1.1-47.1.7, Nov. 1989.
[22] J. H. Andersen, “‘Turbo’ Coding for Deep Space Application,” in IEEE International Symposium on Inform. Theory, 17-22, pp.36, Sep. 1995.
[23] J. H. Andersen, “Turbo codes extended with outer BCH code,” in Electronics Letters, vol. 32, no. 22, 24, pp.2059-2060, Oct. 1996.
[24] J. A. Erfanian, S. Pasupathy, and G.Gulak, “Reduced Complexity Symbol Detectors with Parallel Structures for ISI Channels,” IEEE Trans. Commun., vol. 42, no. 2/3/4, pp.1261-1271, Feb./Mar./Apr. 1994.
[25] T. A. Summers and S. G. Wilson, “SNR Mismatch and Online Estimation in Turbo Decoding,” IEEE Trans. Commun., vol. 46, pp.421-423, Apr. 1998.
[26] A. Worm, P. Hoeher, N. Wehn, “Turbo-Decoding Without SNR Estimation,” IEEE Commun. Letters, vol. 4, no. 6, pp.193-195, June 2000.
[27] S. A. Barbulescu, “Iterative decoding of turbo codes and other concatenated codes,” University of South Australia, PhD Dissertation, Aug. 1995.
[28] S. A. Barbulescu, “On Sliding Window and Interleaver Design,” Electronics Letters, vol. 37, no. 21, pp.1299-1300, Oct. 2001.
[29] A. J. Viterbi, “Error bounds for convolutional codes and asymptotically optimum decoding algorithm,” IEEE Trans. Inform. Theory, vol. IT-13, no. 2, pp.260-269, Mar. 1973.
[30] Y. Wu and B. D. Woerner, “Internal data width in SISO decoding module with modular renormalization,” in IEEE Vehic. Tech. Conf., vol. 1, pp. 675-679, May 2000.
[31] Y. Wu, B. D. Woerner, and T. K. Blankenship, “Data Width Requirements in SISO Decoding With Module Normalization,” in IEEE Trans. On Commun., vol. 49, no. 11, pp. 1861-1868, Nov. 2001.
[32] T. K. Blankenship and B. Classon, “Fixed-Point Performance of Low-Complexity Turbo Decoding Algorithms,” in IEEE Vehic. Tech. Conf., vol. 2 pp. 1483-1487, May 2001.
[33] C. B. Shung, P. H. Siegel, G. Ungerboeck and H. K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm,” IEEE International Conference on Communications, vol. 4, pp.1723-1728, Apr. 1990.
[34] A. P. Hekstra, “An Alternative to Metric Rescaling in Viterbi Decoders,” IEEE Trans. Commun., vol. 37, no. 11, pp. 1220-1222, Nov. 1989.
[35] G. Feygin and P. G. Gulak, “Architectural Tradeoffs for Survivor Sequence Memory Management in Viterbi Decoder,” IEEE Trans. On Commun., vol. 41, no. 3, pp. 425-429, Mar. 1993.
[36] M. A. Bickerstaff, D. Garrate, T. Prokop, C. Thomas, B. Widdup, G. Zhou, L. M. Davis, G. Woodward, C. Nicol, R. H. Yan, “ A Unified Turbo/Viterbi Channel Decoder for 3GPP Mobile Wireless in 0.18-μm CMOS”, in IEEE Journal of Solid-State Circuits, vol.37, no.11, Nov. 2002
[37] M. Moher, “Decoding via Cross Entropy Minimization,” in Proc. IEEE Globecom Conf., Houston, TX, Dec. 1993, pp.809-813.
[38] R. Y. Shao, S. Lin, and M. P. C. Fossorier, “Two Simple Stopping Criteria for Turbo Decoding,” IEEE Trans. On Commun., vol. 47, no. 8, pp.1117-1120, Aug. 1999.
[39] Y Wu, D. Woerner, and J. Ebel, "A simple stopping criteria for turbo decoding," IEEE Commun. Letters, vol. 4, pp. 258-260, Aug. 2000.