臺灣博碩士論文加值系統

近年來，隨著無線網路通訊技術與應用的蓬勃發展，通訊技術也一直朝向高資料傳輸率與寬頻服務的目標趨勢來發展，但在現實的環境中，到處充滿著雜訊與干擾，因此要維持高資料傳輸率又要達到資料傳輸的高品質便是無線通訊技術的一大挑戰。錯誤更正碼技術一直是無線通訊系統中維持系統資料傳輸品質最重要且不可或缺的關鍵技術。渦輪碼導入疊代遞迴解碼的概念，使解碼效能接近了Shannon極限，確立渦輪碼在未來無線通訊系統中的地位。然而高解碼複雜度與解碼時間延遲(latency delay)的問題一直是值得去探討與改進的。
本論文基於步階式解碼演算法對於高碼率之里德-所羅門碼具有低解碼複雜度、低解碼時間延遲以及高解碼速度之特性，提出改良型高速步階式單一錯誤更正里德-所羅門解碼法以及改良型步階式Chase里德-所羅門方塊渦輪解碼法，並以電腦模擬驗證所提之改良型演解碼法的效能增益。
針對具高碼率特性之里德-所羅門方塊渦輪碼(Reed-Solomon Block Turbo Codes, RS BTC)解碼器，本論文也提出一個低解碼複雜度、低解碼時間延遲且高速之步階式里德-所羅門方塊渦輪碼之解碼器架構，並使用Verilog HDL來完成解碼器電路設計，實現於FPGA發展板上，其解碼速度可高達數個Giga bits/sec，以適用於未來之寬頻無線通訊系統之高傳輸速度與高頻寬效率的發展趨勢。

It is well known that the wireless communication technology has been developed towards broadband services. However, to keep the high quality and high throughput for wireless communication systems over wireless channel environment with noise and interferences is a real challenge. The forward error correction techniques can be employed to improve the performance and widely used in wireless communication systems. The concept of iterative decoding turbo code makes decoding performance close to the Shannon limit. Turbo code has established its future status in the wireless communication system. However, it has very high complexity and long latency delay.
In this paper, based on the step-by-step decoding algorithm in RS codes, it has the properties of low-complexity and high-speed. A modified step-by-step decoding procedure for single-error-correcting RS codes is proposed. Moreover, a modified decoding procedure for Chase RS-BTC decoding with step-by-step RS decoding algorithm has also been proposed. The simulation result shows that the modified decoding procedure we proposed is improved for RS-BTC.
This paper also proposed a high-speed step-by-step RS-BTC decoder architecture with low decoding complexity and short latency delay. The Verilog HDL is used here to construct RS-BTC decoder hardware and used to FPGA board to complete the decoder circuit design. This RS-BTC has a good balance between performance and complexity suitable to apply to the broadband wireless communication systems with high transmission speed and high bandwidth efficiency trends in the future.

目錄

中文摘要…i
英文摘要…ii
誌謝…iii
目錄…iv

第一章 緒論…1
1.1 前言…1
1.2 錯誤更正碼……2
1.3 研究動機…2
1.4 論文大綱…4
第二章 方塊渦輪碼…5
2.1 方塊渦輪碼之概述…5
2.2 方塊渦輪碼之編碼…5
2.3 Chase演算法…7
2.4 方塊渦輪碼之解碼…13
2.5 里德-所羅門方塊渦輪碼之編碼與解碼…19
第三章 步階式解碼演算法…22
3.1 步階式里德-所羅門解碼演算法…22
3.2 高速步階式單一錯誤更正里德-所羅門解碼法…25
3.3 步階式里德-所羅門方塊渦輪碼解碼法…27
3.4 模擬與分析…29
第四章 里德-所羅門方塊渦輪碼解碼器…34
4.1 高速步階式里德-所羅門解碼器…34
4.1.1 解碼器架構與HDL-Code設計…34
4.1.2 硬體測試與實現…41
4.2 軟式輸入軟式輸出里德-所羅門解碼器…43
4.2.1 解碼器架構與HDL-Code設計…43
4.2.2 硬體測試與實現…50
4.3 里德-所羅門方塊渦輪碼之Full-Parallel解碼器…52
4.3.1 解碼器架構與HDL-Code設計…52
4.3.2 硬體測試與實現…55
第五章 結論…59
參考文獻…60
作者簡歷…63

圖目錄
圖2-1 方塊渦輪碼之概念圖…6
圖2-2 方塊渦輪碼編碼示意圖…7
圖2-3 傳統代數解碼示意圖…8
圖2-4 Chase演算法解碼示意圖…8
圖2-5 BPSK硬式決策示意圖…11
圖2-6 Chase演算法解碼流程圖…13
圖2-7 軟式輸入軟式輸出解碼器…17
圖2-8 半次遞迴之方塊渦輪碼解碼架構圖…17
圖2-9 方塊渦輪碼模擬之系統架構圖…19
圖2-10 (128, 120)2BCH方塊渦輪碼之遞迴次數之效能模擬圖…19
圖2-11 RS-BTC編碼示意圖…20
圖2-12 方塊渦輪碼模擬之系統架構圖…21
圖2-13 RS-BTC之不同碼字長度之效能模擬圖…21
圖3-1 改良型之Chase演算法解碼流程圖…29
圖3-2 軟式輸入硬式輸出模擬之系統架構圖…30
圖3-3 (31, 29)里德-所羅門碼之效能模擬圖…31
圖3-4 軟式輸入軟式輸出RS-BTC模擬之系統架構圖…31
圖3-5 (31, 29)2里德-所羅門方塊渦輪碼之效能模擬圖…32
圖3-6 (15, 13)2里德-所羅門方塊渦輪碼之效能模擬圖…33
圖3-7 (63, 61)2里德-所羅門方塊渦輪碼之效能模擬圖…33
圖4-1 快速步階式里德-所羅門解碼流程圖…34
圖4-2 徵狀產生器運算架構圖…35
圖4-3 徵狀產生器設計方塊圖…36
圖4-4 錯誤個數運算器架構圖…37
圖4-5 錯誤個數運算器架構圖…37
圖4-6 運算器架構圖…38
圖4-7 運算器架構圖…39
圖4-8 判斷器架構圖…40
圖4-9 錯誤值輸出器架構圖…40
圖4-10 更正錯誤器架構圖…41
圖4-11 模擬結果…42
圖4-12 高速步階式(31, 29)里德-所羅門解碼器時脈示意圖…43
圖4-13 軟式輸入軟式輸出里德-所羅門解碼架構圖…44
圖4-14 低可靠度位元搜尋器(符元)架構圖…45
圖4-15 低可靠度位元搜尋器(碼字)架構圖…45
圖4-16 低可靠度位元搜尋器(碼字)之運作流程圖…46
圖4-17 符碼距離計算器架構圖…47
圖4-18 碼字距離計算器架構圖…47
圖4-19 位元偵測器架構圖…48
圖4-20 一般方案軟式輸出計算器架構圖…49
圖4-21 特殊方案軟式輸出計算器架構圖…50
圖4-22 額外資料產生器架構圖…50
圖4-23 模擬結果…51
圖4-24 軟式輸入軟式輸出(31, 29)里德-所羅門解碼器時脈示意圖…52
圖4-25 Full-parallel之方塊渦輪碼運作概念圖…53
圖4-26 里德-所羅門方塊渦輪碼之Full-parallel解碼器架構圖…53
圖4-27 方塊渦輪碼陣列記憶體運作架構圖…54
圖4-28 方塊渦輪碼轉置控制記憶體運作架構圖…55
圖4-29 模擬結果…56
圖4-30 高速步階式里德-所羅門方塊渦輪解碼器時脈示意圖…57
圖4-31 (31, 29)2RS-BTC之軟硬體共同模擬效能圖…58

表目錄
表1-1 RS-BTC與BCH-BTC之比較…4
表2-1 軟式輸入訊息範例表…12
表2-2 測試樣本範例表…12
表2-3 測試序列範例表…12
表3-1 徵狀矩陣行列式值分布情形…23
表3-2 單一錯誤更正之渦輪碼比較…25
表4-1 高速步階式(31, 29)里德-所羅門解碼器latency delay架構分析…42
表4-2 軟式輸入軟式輸出(31, 29)里德-所羅門解碼器latency delay架構分析…51
表4-3 高速步階式里德-所羅門方塊渦輪碼解碼器latency delay架構分析…56

[1] C. E. Shannon., “A Mathematical Theory of Communication,” Bell System Technical Journal, vol. 27, pp. 379-423 and 623-656, July 1948.
[2] P. Elias, “Coding for noisy channels,” IRE Convention Record, pt. 4, pp. 37-47, 1995.
[3] J. L. Massey, “Step-by-step decoding of the Bose-Chaudhuri-Hocquenghem codes,” IEEE Trans. Inform. Theory, vol. IT-11, pp. 580-585, Oct. 1965.
[4] I. Reed and G. Solomon, “Polynomial codes over certain finite fields,” Journal of the Society of Industrial and Applied Mathematics, vol. 8, pp. 300-304, June 1960.
[5] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes,” in Proceedings of the International Conference on Communications, Geneva, Switzerland, pp. 1064-1070, May 1993.
[6] R. Pyndiah, A. Glavieux, A. Picart, and S. Jacq, “Near optimum decoding of product codes,” in Proc. IEEE GLOBECOM’94 Conf., vol. 1/3, San Francisco, pp. 339-343, Nov.-Dec. 1994.
[7] O. Aitsab and R. Pyndiah, “Performance of Reed-Solomon block turbo code,” in Proc. IEEE Global Telecommun. Conf., vol. 1-3, London, U.K., pp. 121-125, Nov. 1996.
[8] Z. Chi and K. Parhi, “High speed VLSI architecture design for block turbo decoder,” in Circuits and Systems, ISCAS 2002. IEEE International Symposium, vol. 1, pp. I-901-I-904, May 2002.
[9] C. Jégo, P. Adde, and C. Leroux, “Full-parallel architecture for turbo decoding of product codes,” Electronics Letters, vol. 42, no. 18, pp. 1052–1054, 2006.
[10] P. Adde, R. Pyndiah, O. Raoul, and J. R. Inisan, “Block turbo decoder design,” in Proc. IEEE Int. Symp.Turbo Codes &; Related Topics, vol. 1/1, Brest, France, pp. 166-169 Sept. 1997.
[11] C. Leroux, C. Jego, P. Adde, and M. Jezequel, “On the higher efficiency of parallel Reed-Solomon turbo-decoding,” In ICECS’08 15th international conference on electronics, circuits and system, pp. 1308-1311, Sept. 2008.
[12] R. Le Bidan, C. Leroux, C. Jego, P. Adde, and R. Pyndiah, “Reed-Solomon Turbo Product Codes for Optical Communications: From Code Optimization to Decoder Design,” EURASIP Journal on Wireless Communicational and Networking, vol. 2008.
[13] E. Piriou, C. Jego, P. Adde, R. Le Bidan, and M. Jezequel, “Efficient architecture for Reed Solomon block turbo code,” ISCAS 2006 : International Symposium on Circuits and Systems, Kos, Greece, pp. 3682-3685, May 2006.
[14] R. Zhou, R. L. Bidan, R. Pyndiah, and A. Goalic, “Low-complexity high-rate Reed-Solomon block turbo codes,” IEEE Trans. on Communications, vol. 55, no. 9,pp. 1656-1660, Sept. 2007.
[15] J. Trubuil, A. Goalic, N. Beuzelin, C. Laot, “Check and validate Reed Solomon Block Turbo Codes in shallow underwater acoustic communication,” IEEE OCEANS, Sydney, pp. 1-6, May 2010.
[16] A. Goalic, J. Trubuil, C. Laot, N. Beuzelin, “Improvement of underwater acoustic communication using Reed Solomon Block Turbo Codes” in Proc. IEEE Global Telecommunications Conf., pp. 151-155, Sept. 2010.
[17] C. Leroux, G. Le Mestre, C. Jégo, P. Adde, and M. Jézéquel, “A 5-Gbps FPGA prototype of a (31, 29)2 Reed-Solomon Turbo Decoder,” 5th International Symposium on Turbo Codes and Related Topics, Lausanne, Suisse, pp. 67-72, Sept. 2008.
[18] L. Hanho, “A high-speed low-complexity Reed-Solomon decoder for optical communications,” IEEE Trans. Circuits and Syst. II, Express Briefs, vol. 52, Issue 8, pp. 461–465, Aug. 2005.
[19] BERNARD SKLAR, Digital Communications, Prentice-Hall International, Inc., second Edition, 2006.
[20] S. Haykin, Communication systems, John Wiley &; Sons, Inc., 5th edition, 2001.
[21] T. C. Chen and M. H. Tasi, “Hardware Implementation of a High-Speed (32, 24, 4) RS Decoder, “Chung Hua Journal of Science and Engineering,” vol. 5, no. 4, pp. 21-27, Dec. 2007.
[22] T. C. Chen, C. H. Wei, and S. W. Wei, “A Pipeline Structure for High-Speed Step-by-Step RS decoding,” IEICE Trans. Commun., vol. E86-B, no. 2, Feb. 2003.
[23] D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE trans. Inform. Theory, vol. 18, Jan. 1972.
[24] P. Elias, “Error-free coding,” IRE Trans. Inform. Theory, vol. IT-4, pp. 29-37, Sept. 1954.
[25] R. Pyndiah, “Near-optimum decoding of product codes: Block turbo codes,” IEEE Trans. Commun., vol. 46, no. 8, pp. 1003- 1010, Aug. 1988.
[26] R. Pyndiah, “Iterative decoding of product codes: Block turbo codes,” in Proc. IEEE Int. Symp. Turbo Codes &; Related Topics, vol. 1/1, Brest, France, pp. 71–79, Sept. 1997.
[27] J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes,” IEEE Trans. Inform. Theory, vol. 42, pp. 429–445, Mar. 1996.
[28] S. W. Wei and C. H. Wei, “High-speed decoder of Reed-Solomon codes,” IEEE trans. Commun., vol. 41, no. 11, pp. 1588-1593, Nov. 1993.
[29] T. C. Chen, C. H. Wei, and S. W. Wei, “Step-by-step decoding algorithm for Reed-Solomon codes,” IEE Proc. Commun., vol. 147, no. 1, pp. 8-12, Feb. 2000.