臺灣博碩士論文加值系統

由於渦輪碼有著優異的錯誤更正能力，所以在近十年來已經被廣泛的運用在通訊系統上。然而由於渦輪碼複雜的結構使得其速度無法有效提升，本論文將改善解碼器的架構使渦輪解碼器速度有效提升。
由於渦輪碼的時脈是被遞迴結構所限制的，我們利用偏移加法-比較-選擇器和一級CSA的架構，來減少主要路徑延遲；除此之外，我們更進一步提出了hybrid 4-inputs addition/subtraction基數-4的遞迴結構使得此架構的吞吐量和傳統的遞迴結構相比有近80%的提升。另一方面，傳統渦輪解碼必須跑到固定次數的迭代以確保事前資訊已經收斂，但如此一來造成速度慢，高延遲和功率浪費。事實上，當通道狀況好的時候，渦輪解碼會提早收斂，因此，藉由分析，我們選用HDA2提早停止方法來降低迭代次數來達到高吞吐量的目的。
根據實驗分析，此渦輪解碼器在UMC90 nm製程下最高能達到的時脈頻率為357.14MHz，以及在單塊MAP解碼器之下，渦輪解碼器能達到77.62MS/s的傳輸速度，晶片面積為1.59mm2。另外，由於平行化的渦輪解碼會發生記憶體碰撞的問體，我們可以利用修正過的退火演算法將這問題解決，並且在十四塊MAP解碼器之下，渦輪解碼器能達到884.91MS/s的傳輸速度，晶片面積為17.64mm2。

Turbo codes have been applied widely in communication systems over the last decade due to its excellent error correction ability. However, because of complex structure, the data rate of turbo decoder could not improve more efficiently. Therefore, the thesis presents improved architectures to increase its data rate.
The operating frequency of turbo decoder is greatly limited by the recursion unit. In order to decrease the critical path delay, the OACS and one stage CSA structure is employed. Furthermore, the hybrid 4-inputs addition/subtraction radix-4 recursion architecture is presented for CCSDS turbo decoder and finally the relative throughput of proposed recursion unit is faster than traditional one around 80%. On the other hand, the decoding process has to run a certain number of iterations to ensure the extrinsic have converged. In fact, turbo decoder may converge earlier when the channel condition is good. Hence, an early stopping criterion could be employed to reduce the number of iterations.
After chip implementation in 90nm process, the maximum clock rate 357.14MHz can be achieved, and the 1.59mm2 core area can support the maximum data rate 77.62MS/s of turbo decoder with single MAP decoder. Besides, if the parallel MAP decoders are considered, the memory collision could be happened. We can introduce the modified annealing algorithm to solve the collision problems. The 17.64mm2 core area can support the maximum data rate 884.91MS/s of turbo decoder with fourteen MAP decoders.

口試委員會審定書 #
誌謝 iii
CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES x
Chapter 1 Introduction 1
1.1 Background of Turbo Codes 1
1.2 Motivation and Objective 1
1.3 Thesis Organization 2
Chapter 2 Overview of Turbo Codes System 3
2.1 The Structure of Turbo Code 3
2.1.1 Encoder of Turbo Code 3
2.1.2 CCSDS Encoder 4
2.1.3 Decoder of Turbo Code 8
2.2 The Turbo Decoder Algorithm 10
2.2.1 The MAP Algorithm 10
2.2.2 The Log-MAP Algorithm 16
2.2.3 The Maximum Log (ML) MAP Algorithm 17
2.3 Sliding Window Method for Turbo Decoding 20
Chapter 3 Turbo Decoder Design Consideration 24
3.1 The Proposed Structure of Parallel Turbo Decoder 24
3.2 The Parallel Turbo Decoder 25
3.2.1 Sliding Window Timing Diagram 25
3.2.2 Parallel Sliding Window Decoding 26
3.2.3 The Interleaver of Parallel Turbo Decoders 27
3.3 Early Stopping Criteria 33
Chapter 4 Soft-In-Soft-Out (SISO) Decoder Design Consideration 37
4.1 SISO Decoder Architecture 37
4.2 Radix-4 Log-MAP Algorithm 38
4.3 The Architecture of Recursion State Metric 40
4.3.1 OASC Structure 41
4.3.2 Proposed Radix-4 Log-MAP Recursion State Metric 43
4.3.3 The State Metric Normalization 47
4.4 The Structure of Branch Metric 49
4.5 The Structure of Log-Likelihood Ratios (LLR) 51
4.5.1 Traditional LLR Computation Unit (LCU) Based on Radix-2 Log-MAP Algorithm 51
4.5.2 LLR Computation Unit (LCU) Based on Radix-4 Log-MAP Algorithm 51
Chapter 5 System Simulation and Performance Analysis 53
5.1 The Bit-Width Estimation of Soft-Input Information 53
5.2 The Bit-Width Estimation of Lex 54
Chapter 6 Turbo Decoder Implementation in FPGA and ASIC 58
6.1 The FPGA Implementation Results 58
6.2 The ASIC Implementation Results 62
6.3 Comparison 66
Chapter 7 Conclusions 68
REFERENCE 69

[1]C. Berrou, A. Glavieux and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes,” in Proc. ICC `93, Geneva, Switzerland, May 1993, pp. 1064–1070.
[2]C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, pp. 379-427, 1948.
[3]IEEE Std 802.16e-2005, 802.16 TGe, Feb. 2006.
[4]3GPP Specifications. 3rd generation partnership project. [Online]. Available: http://www.3GPP.org
[5]Consulative Committee for Space Data Systems, Recommendation for Telemetry Channel Coding, CCSDS 101.0-B-6, Blue Book, October 2002.
[6]L. Bahl, J. Cocke, F. Jelinek and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. on Information Theory, vol. 20, pp. 284-287, May 1974.
[7]J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its applications,” in Proc. IEEE Globecom Conf., Nov. 1989, pp. 1680-1686.
[8]A. J. Viterbi, “An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes,” IEEE J. Select. Areas Communication, vol. 16, pp. 260-264, Feb. 1998.
[9]M. Bicherstaff, L. Davis, C. Thomas, D. Garrett, and C. Nicol, “A 24Mb/s Radix-4 LogMAP Turbo Decoder for 3GPP-HSDPA Mobile Wireless,” in IEEE ISSCC Dig. Tech. Papers, 2003, pp. 150 – 151.
[10]Z. Wang, “High-speed recursion architecture for MAP-based Turbo decoders”, in IEEE Trans. VLSI Syst, vol 14, No. 4, pp. 470-474, April 2007.
[11]C. Zhang, X. Wang, F. Ye and J. Ren, “A 400Mb/s radix-4 MAP decoder with fast recursion architecture” in IEEE ICACT 2008, vol. 2, 17-20 Feb. 2008 paper(s): 1339-1342.
[12]E. Boutillon,W.J. Gross and P.G. Gulak, “VLSI architectures for the MAP algorithm,” IEEE Transactions on Communications, vol. 51(2), pp. 175 - 185, Feb. 2003.
[13]J. Ertel, J. Vogt, A. Finger, “A high throughput Turbo Decoder for an OFDM-based WLAN demonstrator,” in proceedings of 5th International ITG Conference on Source and Channel Coding (SCC), Jan. 2004.
[14]A. Hekstra, “An alternative to metric rescaling in Viterbi decoders” IEEE Trans. on Communications, 37(11): 1220-1222, Nov 1989.
[15]C. B. Shung, G. Ungerboeck and H. K. Thapar, “VLSI architectures for metric normalization in the Viterbi algorithm,” in Proc. IEEE Int. Conference Communications (ICC `90), vol.4, Atlanta, GA, Apr. 16-19, 1990, pp.1723-1728.
[16]A. Worm, H. Michel, F. Gilbert, G. Kreiselmaier, M. Thul and N. When, “Advanced implementation issues of turbo-decoders” in Proc. 2nd Int. Symp. on Turbo Codes, Brest, France, Sept. 2000, pp. 351–354.
[17]T.-H. Tsai, C.-H. Lin, and A.-Y. Wu, “A memory-reduced log-MAP kernel for turbo decoder,” in Prof. IEEE ISCAS, 2005, pp. 1032-1035.
[18]Ahmed and T. Arslan, “VLSI Design of Multi Standard Turbo Decoder for 3G and Beyond,” 12th Asia and South Pacific Design Automation Conference (ASP-DAC 2007), pp. 589-594, Pacifico Yokohama, Yokohama, Japan, January 23-26, 2007.
[19]Engin. N, “Turbo decoder architecture with scalable parallelism,” in Proceedings of IEEE Workshop on Signal Processing Systems, 2004, pp. 298.303
[20]A. Giulietti, L. Van der Perre, and A. Strum, “Parallel turbo coding interleavers: Avoiding collisions in accesses to storage elements,” Electron. Lett., vol. 38, pp. 232–234, Feb. 2002.
[21]A. Tarable, S. Benedetto, G. Montorsi, “Mapping interleaving laws to parallel turbo and LDPC decoder architectures,” in IEEE Transaction on, vol 50, pp. 2002-2009, Sept. 2004.
[22]J. Vogt, J. Ertel, and A. Finger, “Reducing bit width of extrinsic memory in turbo decoder realizations,” Electron. Lett., pt. 20, pp. 1714–1716, Sept. 2000.
[23]Z. Wang, Y. Zhang and K. K. Parhi, “Study of early stopping criteria for turbo decoding and their applications in WCDMA systems” in Proc of ICASSP’06, pp. III-1016-1019, May. 2006.
[24]A. Matache, S. Dolinar, and F. Pollara, “Stopping rules for turbo decoders,” Tech. Rep., Jet Propulsion Laboratory, Pasadena, California, Aug. 2000.
[25]T. M. N. Ngatched and F. Takawira, “Simple stopping criterion for turbo decoding,” Electronics Letters, vol. 37, no. 22, pp. 1350 – 1351, Oct. 2001.
[26]Z. Wang, H. Suzuki, and K. K. Parhi, “Vlsi implementation issues of turbo decoder design for wireless applications,” in Proc. of 1999 IEEE Workshop on Signal Processing Systems (SIPS’99), Oct. 1999, pp. 503–512.
[27]Jeff B. Berner, Kenneth S. Andrews, “Deep Space Network Turbo Decoder Implementation” Aerospace Conference, 2001, IEEE Proceedings.
[28]http://www.sworld.com.au/pub/pcd04c.pdf, Small World Communications.
[29]Keshab K. Parhi, “VLSI Digital Signal Processing Systems: Desing and Implementation,” New York:Wiley, 1999.
[30]A. Worn, Peter. Hoeher, Norbert. Wehn,”Turbo-decoding without SNR estimation” IEEE Communications leter, vol 4, NO 6, June 2000.