臺灣博碩士論文加值系統

在此論文中我們利用退火模擬演算法(Simulated Annealing Algorithm)提出無衝突演算法去解決平行渦輪碼中記憶體碰撞問題。再者，對於平行渦輪碼中的非本質記憶體，我們提出有效使記憶體面積減少的兩種架構；
其中一種架構是由平行單埠記憶體與一個緩衝暫存器所組成去取代原來須兩埠或雙埠記憶體所組成的架構。另外一個架構，我們基於前一個架構上再加上一個非本質函數的非線性映對器。在前兩種架構相較於傳統使用雙埠記憶體在 0.13 CMOS 聯電製程環境底下分別可以節省約 37 和 46 百分比記憶體使用量。

In this thesis, a contention free algorithm for solving memory collision problem of parallel Turbo decoder architecture using the simulated annealing algorithm is presented. Furthermore, we proposed two area-efficient extrinsic memory schemes based on the
parallel contention free Turbo decoder. One of the proposed schemes employs only multiple single port memories with one temporary buffer instead of the original dual port or two port memories. And the other scheme further employs an additional non-linear extrinsic mapping architecture. The proposed schemes lead to approximately 37% and 46% memory area reduction, respectively, for 16-parallel Turbo decoder in comparison to the conventional dual port memory scheme under the UMC 0.13-μm CMOS process.

口試委員會審定書 #
中文摘要 i
ABSTRACT ii
誌謝 iii
CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES x
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Thesis Organization 2
Chapter 2 Turbo Code 3
2.1 System Overview 3
2.2 Turbo Encoder 4
2.2.1 Turbo Encoder Process. 4
2.2.2 Recursive Systematic Convolution (RSC) 5
2.2.3 Trellis-Termination 7
2.2.4 Puncturing 9
2.3 Interleaver 10
2.3.1 Block Interleaver 10
2.3.2 Prime Interleaver 11
2.3.3 Random Interleaver 12
2.3.4 S - Interleaver 12
2.3.5 Characteristic of Interelaver 13
2.4 Channel Model 14
2.5 Turbo Decoder Process 15
2.6 SISO Decoding Algorithm 17
2.6.1 Log-MAP Algorithm 17
2.6.2 Max-Log-MAP Algorithm 19
2.6.3 Initialized Procedure for Both Log-
MAP and Max-Log-MAP Algorithm 19
2.7 Error Probability for Turbo Code 20
2.8 Turbo Code Application on Telemetry and Deep Space
Communications 21
2.9 Simulation and Results 24
Chapter 3 VLSI Architecture of Turbo Decoder 28
3.1 Sliding Window Approach 29
3.2 VLSI Architecture of SISO Decoder for CCSDS
Standard 31
3.2.1 Log-MAP Decoder 32
3.2.2 Interleaver Address Calculation Unit 38
3.2.3 Extrinsic Information Quantization 39
3.3 Serial SISO Structure 39
3.4 Parallel SISOs Strcture 40
Chapter 4 Solving Memory Collision Problem For
Parallel Turbo Decoder 43
4.1 Introduction 43
4.2 Memory Collision Problem for Parallel Turbo
Decoder 43
4.3 Solving Memory Collision Problem Using Temporal
Buffer Architecture 44
4.4 Proposed Memory Contention Free Scheme for
Parallel Turbo Decoder 45
4.4.1 Definition of Memory Collision Problem 46
4.4.2 Solution to Graph Coloring Problem
by Simulated Annealing Algorithm 48
4.4.3 The Extrinsic Memory Collision Free VLSI
Architecture Design 52
4.4.4 Simulation and Experiment Results 53
4.5 An Approach for Reducing Memory Area of Parallel
Turbo Decoder 63
4.5.1 Classical Extrinsic Memory Access for Single
Turbo Decoder 63
4.5.2 An Area-Efficient Extrinsic Memory Scheme
for Parallel Turbo Decoder 63
4.5.3 Analysis of the Required Memory Size 66
Chapter 5 Conclusion 69
Bibliography 70

[1]. C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes,” in Proc. ICC, Geneva,
Switzerland, May 1993, pp. 1064–1070.
[2]. Boutillon, E. Douillard, C. Montorsi, G. “Iterative Decoding of Concatenated Convolutional Codes: Implementation Issues,” Proceedings of the IEEE, June 2007, Issue: 6, pp. 1201-1227.
[3]. A. Nimbalker, T. K. Blankenship, B. Classon, T. E. Fuja, D. J. Costello, Jr, “Contention-free interleavers,” Int. Symp. on Inf. Theory, June 2004.
[4]. A. Tarable, G. Montorsi and S. Benedetto, “Mapping of interleaving laws to parallel turbo decoder architectures,”, in Proc. 3rd Int. Symp. Turbo Codes Related Topics, Brest, France, Sep. 2003, pp. 153-156.
[5]. Consultative Committee for Space Data Systems, CCSDS 131.0-B-1 Blue Book September 2003.
[6]. S. Dolinar and D. Divsalar, “Weight Distributions for Turbo Codes Using Random and Nonrandom Permutations” TDA Progress Report 42-122, Jet Propulsion Laboratory, Pasadena, California, pp. 56–65, August 15, 1995.
[7]. D. Divsalar and F. Pollara, “On the design of turbo codes”, TDA Progress Report 42-123, Jet Propulsion Laboratory, Pasadena, California, pp. 99–121, November
15, 1995.
[8]. P. Guinand and J. Lodge, “Trellis termination for turbo encoders,” in Proc. 17th Biennial Symp. Commun., pp. 389–392, May 30-June 1 1994.
[9]. J. Hokfelt, O. Edfors, and T. Maseng, “A survey on trellis termination alternatives for turbo codes,” in Proc. IEEE Vehicular Technology Conf. (VTC’99), pp2225–2229, May 1999.
[10]. S. Crozier, P. Guinand, and A. Hunt, “On designing turbo-codes with data puncturing,” in 9th Canadian Workshop on Inform. Theory (CWIT’05), pp. 32–35,
June 2005.
[11]. L. C. Perez, J. Seghers, and D. J. Costello, Jr., “A distance spectrum interpretation of turbo codes,” IEEE Trans. Inform. Theory, vol. 42, pp.1698–1709, Nov. 1996.
[12]. C. Berrou, "Turbo codes: some simple ideas for efficient communications", ESA-DSP 2001, Lisbon, Oct. 2001, and ESA-TTC 2001, Noordwijk, The Netherlands, Oct. 2001.
[13]. D. Divsalar and F.Pollara, “Multiple Turbo Codes” MIL-COM’95, pp. 279-285, November 6-8, 1995.
[14]. S. Benedetto and G. Montorsi, “Unveiling Turbo Codes: Some Results on Parallel Concatenated Coding Schemes”, IEEE Trans. on Inform. Theory, Vol. 42,
No. 2, pp.409-428, March 1996.
[15]. S. Crozier, J. Lodge, P. Guinand and A. Hunt, "Performance of turbo codes with relatively prime and golden interleaving strategies", Proc. of 6th Int. Mobile Satellite Conf., pp. 268-275, Ottawa, Canada, June 1999.
[16]. C. Berrou, Y. Saouter, C. Douillard, S. Kerouédan and M. Jézéquel, “Designing good permutations for turbo codes: towards a single model,” in Proc. IEEE Int. Conf. Communications, Paris, France, June 2004.
[17]. E. K. Hall, S. G. Wilson, “Stream-oriented turbo codes,” IEEE Trans. Inform. Theory, vol.47, pp.1813-1831, July 2001.
[18]. P. Robertson, E. Villebrun, and P. Hoeher, “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain,” in ZEEE Inc.
on Communications (Seattle, WA, June 1995). pp. 1009-1013.
[19]. A.Worm, P. Hoeher, and N. Wehn, “Turbo-Decoding without SNR Estimation,” IEEE Communications Letters, vol. 4, no. 6, June 2000.
[20]. M. J. Thul, F. Gilbert, and N. Wehn, “Concurrent Interleaving Architec-tures for High-Throughput Channel Coding,” in Proc. 2003 Conferenceon Acoustics,
Speech, and Signal Processing (ICASSP ’03), Hong Kong,P.R.China, Apr. 2003, pp. 613–616.
[21]. T. A. Summers and S. G. Wilson, “SNR mismatch and online estimation in turbo decoding,” IEEE Trans. Commun., vol. 46, no. 4, pp. 421-423, Apr. 1998.
[22]. Zhongfeng Wang, Zhipei Chi and K. K. Parhi, “Area-efficient high speed decoding schemes for Turbo Decoders” IEEE Transactions on very large scale integration (VLSI) 2002.
[23]. TH Tsai, CH Lin, AY Wu, “A memory-reduced log-MAP kernel for turbo decoder,” Circuits and Systems, 2005. ISCAS 2005. IEEE International
Symposium on Publication Date: 23-26 May 2005 On page(s): 1032- 1035 Vol. 2
[24]. J.Ertel, J.Vogt and A.Finger, “A high throughput Turbo Decoder for an OFDM-based WLAN demonstrator,” in proceedings of 5th International ITG Conference, Jan. 2004.
[25]. D. Garrett, B. Xu and C. Nicol, “Energy Efcient Turbo Decoding for 3G Mobile,” Proceedings of 2001 International Symposium on Low Power Electronic
Design,pp 328-333.
[26]. R. Dobkin, M. Peleg, and R. Ginosar, “Parallel interleaver design and VLSI
architecture for low-latency MAP turbo decoders,” IEEE Trans. on VLSI Systems, vol. 13, no. 4, pp. 427–438, Apr. 2005.
[27]. J. Sun and O. Y. Takeshita, “Interleavers for turbo codes using permutation polynomials over integer rings,” IEEE Trans. on Inform. Theory, vol. 51, no. 1, pp. 101–119, Jan. 2005
[28]. J.Y´a˜nez and J. Ram´ırez, “The robust coloring problem,” European J.Oper. Res., vol. 148, no. 3, pp. 546–558, 2003.
[29]. A.Lim and F.Wang, “Meta-heuristics for robust graph coloring problem,” in International Conference on Tools with Articial Intelligence. IEEE Computer
Society, 2004, pp. 514–518.
[30]. C.-H. Lin, and A.-Y. Wu, “Low-power traceback MAP decoding for double-binary convolutional turbo decoder,” accepted for publication in Proc. IEEE ISCAS 2008, Seattle, USA, May 18-21, 2008.
[31]. J.Ertel, J.Vogt, A.Finger, “A high throughput Turbo Decoder for an OFDM-based WLAN demonstrator,” in proceedings of 5th International ITG
Conference, Jan. 2004.
[32]. Bougard, A. Giulietti, C. Desset, L. Van der Perre, and F. Catthoor, “A low power high speed parallel concatenated turbo-decoding architecture,” in Proc. Int. Symp. Turbo Codes and Related Topics, Brest, France,Sep. 2003, pp. 511–514.