臺灣博碩士論文加值系統

訊息由發送端傳遞至接收端的內容與品質，須運用適當方法，使其盡可能相同。因此，吾人對高效率且可靠通訊系統之需求，日益迫切；其中最重要的是，在有效運用功率與頻寬資源、而系統複雜度又易於實現的前提下，如何將接收訊息之錯誤機率降至最低。
1993年，布勞(Berro)等三位學者所提出改錯能力趨近夏農(Shannon)極限之渦輪碼，堪稱是錯誤控制碼領域一大突破。渦輪碼之編碼架構，主要由2個回授對稱式迴旋碼(RSC code)與1個交錯器(interleaver)組成；而其解碼步驟，則採用最大化事後機率(MAP)與軟式輸入軟式輸出(SISO)之反覆解碼程序。然渦輪碼解碼之複雜運算與延遲，使得渦輪碼不論在硬體實現或實際應用均有所限制。
本論文旨在探討新式反覆解碼技術於渦輪碼之應用，期能降低解碼複雜度與延遲。在對錯誤控制碼與渦輪碼作簡單回顧及說明後，我們提出三種低延遲之解碼架構。首先，心臟收縮式滑動視窗解碼器可將傳統MAP解碼器之解碼延遲從2N縮短至2L(N、L分別為碼框及視窗長度)。其次，協力式渦輪解碼器(Concurrent Turbo Decoder, CTD)，可將一般渦輪解碼器(GTD)之反覆解碼延遲從4N縮短至2N；而採用CTD設計之平行解碼架構，其解碼延遲更可降低1/2K倍(K為CTD之個數)。最後，為增進傳統渦輪碼之改錯效能，吾人提出改良式MAP演算法及2階式(Two-Tier)渦輪碼之編/解碼器架構，由模擬結果顯示，在N=8192、BER=10-6時，可增加約1.0dB之編碼增益。
本論文所提出之渦輪碼編/解碼演算法及硬體架構設計，其解碼延遲均低於其他解碼器，且不論是BER效能、電路複雜度與模組化，均優於或至少等於其他解碼器，因此適合應用於VLSI電路之設計。

The transmission of information from the source to its destination has to be done in a way that the content and quality of the received information should be as close as possible to that of the transmitted information. Thus, there has been an increasing demand for efficient and reliable communication systems. The major concern of communication system is to minimize the error probability at the receiver end by making efficient use of the power and bandwidth resources, while keeping the system complexity reasonable to implement.
In 1993, a breakthrough in error control coding was the invention of turbo codes proposed by Berrou et al., which facilitate the operation of communication systems close to the Shannon limit. Turbo coding is based on the combinations of two recursive systematic convolutional (RSC) codes, an interleaver and the soft-input soft-output (SISO) iterative decoding using MAP algorithm. However, the complex computation and long latency of turbo decoding make turbo codes impractical not only in hardware implementation but also in some applications.
This dissertation investigates new iterative decoding techniques applied to turbo coding schemes. These techniques are used to approach channel capacity with lower complexity and latency. After briefing the fundamentals of coding for error control in communication systems and the important concepts of turbo coding, we submitted three low-latency decoding architectures. First, we proposed a systolic sliding window (SSW) scheme and VLSI architecture based on Log-MAP algorithm. The proposed low-latency SSW scheme reduced the decoding delay of a MAP decoder from 2N to 2L (N and L are the length of frame and sliding window, respectively). Simulation results and further issues on implementation, such as metric normalization and data length, are also explained.
Second, we proposed a concurrent decoding algorithm which reduces the decoding delay of iteration from 4N to 2N. Based on the concurrent algorithm, we designed the architecture of the concurrent turbo decoder (CTD) using only one single MAP decoder. The CTD approximately reduces the decoding latency by half while offers a comparable BER performance.
Furthermore, we proposed two parallel turbo decoder (PTD) schemes based on the concurrent algorithm, which can perform decoding computations for all component codes concurrently. Additionally, because decoding processes corresponding to different component codes perform concurrently, the (de)interleaving delay is eliminated. Thus, with a K-level parallel scheme (K is the number of CTD), the PTD obtained an iterative delay reduction by a factor of 1/2K, while that of other existed parallel turbo decoding architectures is only 1/K.
Finally, to improve the BER performance of a general turbo codes, we proposed a two-tier turbo coding scheme and a modified MAP algorithm. According to the simulation results, the new coding scheme achieves about 1.0 dB additional coding gain, compared to the general turbo decoding scheme at a BER = 10-6, with a frame length of 8192.
Compared with other related approaches, the proposed architectures of turbo coding are lower complexity, lower latency and more regular. Therefore, it is adequate for VLSI implementation.

Table of Contents
誌 謝 v
摘 要 vi
Abstract vii
Table of Contents ix
List of Figures xii
List of Tables xiv
List of Abbreviations xv
Glossary xvii
Chapter 1 Introduction 1
1.1 Introduction 1
1.2 Development of Channel Coding Technique 3
1.3 Organization of the Dissertation 6
Chapter 2 Turbo Codes and MAP Algorithm 8
2.1 Introduction 8
2.2 Turbo Encoder 9
2.3 Turbo Decoder 13
2.4 The Maximum A-Posteriori Algorithm 15
2.4.1 Description of the MAP algorithm 15
2.4.2 Mathematical preliminaries 15
2.4.3 Derivation of forward recursive calculation 19
2.4.4 Derivation of backward recursive calculation 20
2.4.5 Derivation of branch metric calculation 21
2.5 Application of the MAP Algorithm in Iterative Decoding 24
2.5.1 Preliminaries of turbo decoding 24
2.5.2 Iterative turbo decoding 26
2.6 Modifications of the MAP Algorithm in Log Arithmetic Domain 27
2.6.1 The Max-Log-MAP algorithm 28
2.6.2 The Log-MAP algorithm 30
2.7 Conclusions 32
Chapter 3 VLSI Architecture Design of Proposed Systolic Sliding Window Scheme for Log-MAP Decoder 34
3.1 Introduction 34
3.2 Literature Review 35
3.3 Classical Sliding Window Scheme for the Log-MAP Algorithm 37
3.4 Computation Units of the Proposed Systolic Sliding Window Scheme 39
3.4.1 Branch-metric unit 41
3.4.2 Forward-metric unit 42
3.4.3 Backward-metric unit 44
3.5 VLSI Architecture of Proposed Systolic Sliding Window Scheme 45
3.5.1 Systolic sliding window scheme 46
3.5.2 VLSI architecture of SSW Log-MAP decoder 47
3.5.3 Decoding process 48
3.6 Simulation Results for Turbo Decoding 49
3.7 Several Issues on Implementation 51
3.7.1 Modulo normalization with two’s complement arithmetic 51
3.7.2 Bounds of metrics and determination of data length 52
3.7.3 Normalization of the proposed SSW scheme 53
3.8 Evaluations and Comparisons 53
3.8.1 Evaluations of system architecture 54
3.8.2 Time-area-power analysis and comparison 55
3.9 Conclusions 57
Chapter 4 A Concurrent Algorithm for Low-Latency Turbo Decoder Using a Single MAP Decoder 58
4.1 Introduction 58
4.2 Literature Survey 60
4.3 Review of General Turbo Decoders 61
4.4 Concurrent Turbo Decoding Algorithm 64
4.4.1 Concurrent turbo decoding procedure 65
4.4.2 Updating of the priori information 69
4.5 Hardware Implementation 72
4.5.1 Hardware architecture 72
4.5.2 Iterative decoding schedule 74
4.5.3 Bit-by-bit (de)interleaving 81
4.6 Simulation Results and Comparisons 82
4.7 Conclusions and Remarks 85
Chapter 5 Low-Latency Parallel Turbo Decoders Based on Concurrent Decoding of Component Codes 87
5.1 Introduction 87
5.2 Basics of Parallel Turbo Decoding 89
5.3 Concurrent Decoding of Component Codes for Parallel Turbo Decoder 89
5.3.1 Parallel turbo decoding scheme I 90
5.3.2 Parallel turbo decoding scheme II 93
5.3.3 Updating the priori information 95
5.4 Simulation Results and Remarks 96
5.5 Conclusions 97
Chapter 6 Two-Tier Turbo Coding Scheme and Modified Log-MAP Algorithm 101
6.1 Introduction 101
6.2 Turbo Coding and Hybrid Concatenated Convolutional Codes 102
6.3 Modified Log-MAP Algorithm 103
6.4 Applications in Turbo Coding 105
6.4.1 Encoder of the two-tier scheme 105
6.4.2 Decoder of the two-tier scheme 106
6.5 Simulation Results 109
6.5.1 BER performance of the two-tier scheme with code rate 1/3 111
6.5.2 BER performance of the two-tier with code rate 1/4 112
6.6 Conclusions and Remarks 114
Chapter 7 Conclusion and Future Research 115
7.1 Conclusion 115
7.2 Future Research 118
Appendix 120
A.1 Log Likelihood Ratios (LLRs) 120
A.2 Conditional LLRs 121
A.3 Bayes’ Rule 122
References 123

[1] C. E. Shannon, “A mathematical theory of communication,” in Bell Sys. Tech. J., vol. 27, pp. 379–423, July and pp. 623–656, Oct. 1948.
[2] S. Lin and Daniel J. Costello, Error Control Coding, second edition, Prentice Hall, 2004.
[3] G. Ungerboeck, “Trellis-coded modulation with redundant signal sets, Part I: introduction and Part II: state of the art,” IEEE Communications Magazine, vol. 25, pp. 5-11 and pp. 12-21, Feb. 1987.
[4] R. W. Hamming, “Error detecting and error correcting codes,” in Bell Sys. Tech. J., vol. 29, pp. 147–160, April 1950.
[5] A. Hocquenghem, “Codes correcteurs d’erreurs,” in Chiffres (Paris), vol. 2, pp. 147–156, Sep. 1959.
[6] R. C. Bose and D. K. Ray-CHaudhuri, “On a class of error correcting binary group codes,” in Information and Control, vol. 3, pp. 68-79, March 1960.
[7] W. W. Peterson, “Encoding and error correction procedures for the Bose-CHaudhuri codes,” in IEEE Trans. on Information Theory, vol. 6, pp. 459-470, Sep. 1960.
[8] J. K. Wolf, “Efficient maximum-likelihood decoding of linear block codes using a trellis,” in IEEE Trans. on Information Theory, vol. 24, pp. 76-80, Jan. 1978.
[9] G. D. Forney Jr., “Coset codes-Part II: binary lattices and related codes,” in IEEE Trans. on Information Theory, vol. 34, pp. 1152-1187, Sep. 1988.
[10] S. Lin, T. Kasami, T. Fujiwara and M. P. C. Fossorier, Trellises and Trellis-based decoding algorithms for linear block codes, Kluwer Academic, Boston, MA, USA, 1998.
[11] D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” in IEEE Trans. on Information Theory, vol. 18, pp. 170-182, Jan. 1972.
[12] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” in Journal of the Society of Industrial and Applied Mathematics, vol. 8, pp. 300-304, June 1960.
[13] J. Massey, “Step-by-step decoding of the Bose-CHaudhuri- Hocquenghem codes,” in IEEE Trans. on Information Theory, vol. 11, pp. 580-585, Oct. 1965.
[14] E. R. Berlekamp, Algebraic coding theory, WcGraw-Hill, New York, USA, 1968.
[15] P. Elias, Coding for noisy channels, in IRE Convention Record, vol. 4, pp. 37-47, 1955.
[16] J. M. Wozwncraft and B. Reiffen, Sequential decoding, MIT press, Cambridge, MA, USA, 1961.
[17] J. L. Massey, Threshold decoding, MIT press, Cambridge, MA, USA, 1963.
[18] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. on Information Theory, vol. 13, no. 2, pp. 260-269, April 1967.
[19] L. R. 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, no. 2, pp. 284–287, March 1974.
[20] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit error-correcting coding and decoding: turbo codes (1),” in Proc. IEEE Int. Conf. Communications, pp. 1064–1070 Geneva, Switzerland, May 1993.
[21] G. D. Forney, Jr., Concatenated Codes, MIT press, Cambridge, MA, USA, 1966.
[22] J. Hagenauer, E. Offer and L. Papke, “Matching Viterbi decoders and Reed-Solomon decoders in concatenated systems,” in Reed-Solomon codes and their applications, pp. 242-271, Piscataway, NJ: IEEE press, 1994.
[23] J. A. Erfanian, S. Pasupathy and G.Gulak “Reduced complexity symbol detectors with parallel structures for ISI channels,” IEEE Trans. on Communications, vol. 42, pp. 1661-1671, 1994.
[24] P. Robertson, E. Villeburn, and P. Hoeher, “A comparison of optimal and suboptimal MAP decoding algorithms operating in the log domain,” in Proc. IEEE Int. Conf. Comm., vol. 2, pp. 1009–1013, June 1995.
[25] J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its applications,” in Proc. IEEE Global Telecommunications Conf., vol. 3, pp. 1680–1686, Nov. 1989.
[26] H. Dawid and H. Meyr, “Real-time algorithms and VLSI architectures for soft output MAP convolutional decoding,” Proc. of IEEE Personal, Indoor, and Mobile Radio Comm., PIMRC’95.Wireless: Merging onto the Information Superhighway, vol. 1, pp. 193–197, 1995.
[27] A. J. Viterbi, “An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes,” IEEE J. Select. Areas Communi., vol. 16, pp. 260–264, Feb. 1998.
[28] S. Yoon and Y. Bar-Ness, “A parallel MAP algorithm for low latency turbo decoding,” IEEE Comm. Lett., vol. 6, no. 7, pp. 288–290, July 2002.
[29] E. Boutillon, W. J. Gross and P. G. Gulak, “VLSI architectures for the MAP algorithm,” IEEE Trans. on Communi., vol. 51, no. 2, pp. 175–185, Feb. 2003.
[30] S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Serial concatenation of interleaved codes: performance analysis, design and iterative decoding,” IEEE Trans. Info. Theory, vol. 44, no. 3, pp. 909–926, May 1998.
[31] D. Divsalar and F. Pollara, “Hybrid concatenated codes and iterative decoding,” JPL TDA Progress Rep. 42-130, pp. 1-23, Aug. 15 1997.
[32] D. Divsalar and F. Pollara, “Serial and hybrid concatenated codes with applications,” in Proc. Int. Symp. on turbo codes and related topics, pp. 80-87, Sep. 1997.
[33] C. Argon and S. W. McLaughlin, “A parallel decoder for low latency decoding of turbo product codes,” IEEE Comm. Lett., vol. 6, no. 2, pp. 70–72, Feb. 2002.
[34] S. Benedetto and G. Montorsi, “Iterative decoding of serially concatenated convolutional codes,” Electronic Letter, vol. 32, pp. 1186-1188, July 1996.
[35] P. Robertson, P. Hoeher and E. Villebrun, “Optimal and sub-optimal Maximum a Posteriori algorithms suitable for turbo decoding,” European Transactions on Telecommunications (ETT), vol. 8, no. 2, pp.119-125, 1997.
[36] J. Hagenauer, E.Offer and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. on Information Theory, Vol. 42, No. 2, pp. 429-445, March 1996.
[37] M. Mansour and N. R. Shanbhag, “VLSI architectures for SISO-APP decoders,” IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 2, pp. 627–650, April 2003.
[38] C. Schurgers, F. Catthoor, and M. Engels, “Memory optimization of MAP turbo decoder algorithms,” IEEE Trans. on VLSI Systems, vol. 10, pp. 305–312, April 2001.
[39] S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Serial concatenation of interleaved codes: performance analysis, design and iterative decoding,” JPL TDA Progress Rep. 42-126, pp. 1-26, Aug. 15, 1996.
[40] W. Koch and A. Baier, “Optimum and sub-optimum detection of coded data disturbed by time-varying intersymbol interference,’ IEEE Proc. Globecom’90, pp.1679-1684, Dec. 1990.
[41] S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “A soft-input soft-output maximum a posterior (MAP) module to decode parallel and serial concatenated codes,” JPL TDA Progress Rep. 42-127, pp. 1-20, Nov. 15, 1996.
[42] S. Benedetto, G. Montorsi, D. Divsalar, and F. Pollara, “Soft-Output Decoding Algorithms in Iterative Decoding of Turbo Codes,” JPL, TDA Progress Report 42-124, pp. 63-87, Feb. 1996.
[43] G. Masera, G. Piccinini, M. R. Roch, and M. Zamboni, “VLSI architectures for turbo codes,” IEEE Trans. on VLSI Systems, vol. 7, no. 3, pp. 369–379, Sep. 1999.
[44] S. A. Barbulescu, “Sliding window and interleaver design,” Electron. Lett., vol. 37, no. 21, pp. 1299–1300, Oct. 2001.
[45] A. Hekstra, “An alternative to metric rescaling in Viterbi decoders,” IEEE Trans. on Comm., vol. 37, pp. 1220–1222, Nov. 1989.
[46] Y. Wu, B. D. Woerner and T. K. Blankenship, “Data width requirements in SISO decoding with modulo normalization,” IEEE Trans. on Comm., vol. 49, no. 11, pp. 1861-1868, Nov. 2000.
[47] Z. Wang, H. Suzuki, and K. K. Parhi, “VLSI implementation issues of turbo decoder design for wireless applications,” in Proc. IEEE Workshop Signal Processing Systems, : Design and Implementation, Taipei, Taiwan, R.O.C. , pp. 503–512, Oct. 1999.
[48] J.Dielissen and J.Huisken, "State vector reduction for initialization of sliding windows MAP", 2nd International Symposium in Turbo Codes and Related Topics, Brest, France, pp.387-390, Sep. 2000.
[49] A. Raghupathy and K. J. R. Liu, “VLSI implementation considerations for turbo decoding using a low-latency log-MAP,” Proc. IEEE Int. Conf. Consumer Electronics, ICCE, pp.182-183, June 1999.
[50] C.Berrou and A.Glavieux, “Near optimum error correcting coding and decoding: Turbo codes,” IEEE Trans. on Comm., Vol. 44, No. 10, pp. 1261-1271, Oct.1996.
[51] R. Dobkin, M. Peleg and R. Ginosar, “Parallel interleaver design and VLSI architecture for low-latency MAP turbo decoders,” IEEE Trans. on Very Large Scale Integ. (VLSI) Sys., vol. 13, no. 4, pp. 427–438, April 2005.
[52] A. Worm, H. Lamm and N. Wehn, “VLSI architectures for high-speed MAP decoders,” in Proc. 14th Int. Conf. VLSI Design, pp.446-453, 2001.
[53] J. Hsu and C. Wang, “A parallel decoding scheme for turbo codes,” in Proc. ISCAS’98, vol. 4, pp. 445–448, June 1998.
[54] S. Gounai, T. Ohtsuki and T. Kaneko “Performance of concatenated code with LDPC code and RSC code,” in Proc. of IEEE ICC’06, pp. 1195–1199, 2006.
[55] J. Zhang and Marc P. C. Fossorier, “Shuffled iterative decoding,” IEEE Trans. on Communi., vol. 53, no. 2, pp. 209–213, Feb. 2005.
[56] D. H. Kim and S. W. Kim, “ Bit-level stopping of turbo decoding,” IEEE Comm. Lett., vol. 10, pp. 183–185, March 2006.
[57] J. P. Woodard and L. Hanzo, “Comparative Study of turbo decoding techniques: an overview,” IEEE Trans. On Veh. Technol., vol. 49, pp. 2208–2233, Nov. 2000.
[58] L. Hanzo, T. H. Liew and B. L. Yeap, Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels, John Wiley &; Sons Ltd, 2002.
[59] B. J. Frey, F.R. Kschischang, and P. G. Gulak “Concurrent Turbo- Decoding,” in Proc. International Sym. on I. T., ISIT’97, pp. 431, 1997.
[60] Third Generation Partnership Project, 3GPP homepage, www.3gpp.org.
[61] S. Le Goff, A. Glavieux and C. Berror, “Turbo codes and high spectral efficiency modulation,” in Proc. IEEE Int. Conf. Communications, pp. 645–645, 1994.
[62] P. D. Alexander, A. J. Grant, M. M. Miller, L. K. Rasmussen, L. Wei and P. Whitiing, “Multiuser mobile communications ,” invited paper presented at ISITA’94, Sydney, Nov. 1994.