臺灣博碩士論文加值系統

本論文中利用了錯誤更正能力很接近雪農極限(Shannon-limit)理論的渦輪乘積碼(Turbo Product Code, TPC)，及被認為是目前最有效更正隨機錯誤(Random error)和叢集錯誤(Burst error)，可以更正8個符號(symbol)的里德所羅門碼(Reed-Solomon Code, RS)兩種錯誤更正碼的組合方式，且TPC使用軟式決策解碼(Soft-Decision Decoding)，使效能曲線大為提升。
本論文詳細探討與分析TPC及里德所羅門碼錯誤更正碼的編解碼機制，訊號流程及其實際開發於軟體定義無線電(Software Defined Radio, SDR)系統之設計過程，並完成Labview FPGA程式碼效能曲線之軟體驗證。
為解決硬體與軟體的要求不斷提升的問題，在開發錯誤更正碼時就必須要快速且準確的得到驗證，並測試是否可以依照硬體規格達到應有的效能。故將開發之錯誤更正碼實現於軟體定義無線電系統(Software Defined Radio, SDR)中的FPGA模組上，可以得到快速且準確的驗證。本文程式碼部分由Labview FPGA所撰寫而成，而錯誤更正碼編解碼系統則建置於NI PXIE-5641R FPGA模組平台。本論文使用之NI軟體定義無線電系統是由控制器(NI PXIE-8106)、收發器(NI PXIE-5641R)、降頻轉換器(NI PXI-5600)、升頻轉換器(NI PXI-5610)這些模組所組合而成。其中，5641R是一個具有20 MHz 頻寬的 IF 收發器 - 搭載 DSP - optimized Xilinx Virtex-5 SX95T FPGA (NI PXIe-5641R) 具備中頻 (IF) 輸入與輸出，包含A/D、D/A轉換器，可介接類比升/降轉換器，以擷取並產生 RF 訊號。此介面卡的 FPGA 亦可透過 LabVIEW FPGA進行程式設計，於硬體中執行複雜的調變與訊號處理作業；而其高傳輸率與低延遲，均為軟體定義的無線電系統所必備。
本論文實現於NI PXIE-5641R軟體定義無線電系統的Labview FPGA軟體驗證TPC解碼效能曲線結果，與相關參考文獻使用二維RS(31,15,17)的列、行編碼之TPC效能曲線比較，其錯誤機率同樣在10-3時，使用m =5二維的RS(31,15,17)之TPC碼，其Eb/No約在3.9 dB，而比較本文所使用m =8的RS(31,15,8)與RS(63,47,8)組合之TPC碼時約在 ﹣0.4 dB，表示本文使用m =8的RS可以減少功率的使用，達到約4.3 dB的編碼增益。
一般於FPGA上的開發必須先透過軟體模擬及驗證，根據其模擬結果才能撰寫實現於FPGA的程式碼，就實現的FPGA程式碼來說其延伸的使用性較低，而SDR系統的優點在於可以直接透過Labview FPGA撰寫FPGA程式碼，且完成的程式碼可以用於軟體上的模擬及驗證，也可直接使用於NI PXIE-5641R的FPGA模組平台，理想的情況下可以完全不需修改程式碼使用於硬體與軟體之間，視硬體規格限制而定才可能需要做優化的動作。本論文結果已於SDR系統上完成TPC與RS編碼結合的Labview FPGA開發，且程式碼經過軟體驗證及模擬，並與其他相關文獻研究比較其效能。至於程式碼優化與硬體驗證及模擬結果為下一步實現目標。

In this paper, the error correction capability we use is very close to the Shannon-limit theory of Turbo Product Code, TPC, and is considered to be the most effective way to correct random errors, and Burst error, we can correct 8 symbols of Reed Solomon code, and the TPC use soft decision decoding, it’s greatly enhance the performance curve.
In this paper, we explore and analysis TPC and Reed Solomon code error correction code about encoding and decoding mechanisms, signal flow and its development of software-defined radio system of the design process, also complete the LabView FPGA program code performance curve in the software.
To resolve ever-increasing problems of hardware and software requirements, we must be fast and accurate to get the verification when we develop error correction codes, and exam whether we can achieve the proper performance with the hardware specifications. Therefore, we implement the development of error correction code in software-defined radio system of the FPGA Module. The codes in this paper were written on LabView FPGA, and the error correction encoder and decoder system was built on the NI PXIE-5641R FPGA module platform. The SDR system is composed of modules including controller (NI PXIE-8106), transceiver(NI PXIe-5641R), down-converter(NI PXI-5600), and up-convertor(NI PXI-5610). 5641R is an IF transceiver of bandwidth at 20 MHz – equipped with DSP - optimized Xilinx Virtex-5 SX95T FPGA (NI PXIe- 5641R) with IF (intermediate frequency) input and output, also including the Analog to Digital converter and the Digital to Analog converter that can be interfaced with analog up/down converter to capture and generate RF signals. The FPGA of this interface card can be programmed through LabView to execute complex modulation and signal processing of the hardware. Its high transmission rate and low latency are necessary for software defined radio systems.
In this paper achieves the performance curve results of the LabView FPGA soft verifies by TPC decoding on NI PXIE-5641R software-defined radio software systems, comparing the TPC performance curve with row encoder and column decoder in the two-dimensional RS (31,15,17), when the error probability is the same in 10-3, using the TPC code in m equals 5 of two-dimensional RS (31,15,17), the Eb /No will approximately be 3.9 dB, comparing in this paper, using the TPC code in m equals 8 of RS (31,about -0.4 dB, 15.8)and RS (63,47,8) together, that the article uses m = 8 RS can reduce the power, and the coding gain can reach to 4.3 dB.
General in the development of the FPGA must be past the software simulations and verifications, according to the simulation results, we are able to write code in the FPGA, the utilization is lower to extend in FPGA code. The SDR system has the advantage that it can write directly to the FPGA pass on LabView FPGA code and the completed codes can be used from the NI PXIE-5641R FPGA module platform directly for simulating and verifying on the software, the ideal situation can be completely without modifying the code between the hardware and software, IP core optimization is based on the hardware specifications. In this paper, we were completed he results of which TPC and RS encoders combined with the LabView FPGA development on the SDR system , and the codes are past the software verification and simulation, and compare their performance with other relevant reference. As regards the IP core optimization and hardware verification and simulation results are the next targets.

key word: Reed-Solomon, Turbo Product Code, Labview PFGA, Soft Define Radio, Soft-Decision Decoding

第一章 緒論..........................................................................1
1.1 研究背景.........................................................................1
1.2 數位通訊系統與通道編碼..............................................................2
1.3 渦輪乘積碼及里德所羅門碼.............................................................3
1.4 研究動機..........................................................................5
第二章 里德所羅門碼.....................................................................6
2.1 伽羅瓦場元素的建立..................................................................6
2.2 里德所羅門碼定義與參數..............................................................10
2.3 里德所羅門碼之編碼.................................................................11
2.4 里德所羅門碼解碼...................................................................14
2.4.1 計算徵候值(Syndrome polynomial).................................15
2.4.2 求出錯誤位置多項式(error location polynomial).....................16
2.4.3 尋找錯誤位置之方法(Chien Search)..................................23
2.4.4 尋找錯誤值大小之方法(Forney Algorithm)............................24
第三章 渦輪乘積碼......................................................................28
3.1 渦輪乘積碼編碼.............................................................28
3.2 渦輪乘積碼解碼.............................................................29
3.2.1 軟式判斷........................................................30
3.2.2 Chase Algorithm................................................32
3.3 TPC與RS碼完整架構說明.......................................................43
第四章 NI Labview FPGA實作里德所羅門碼與渦輪乘積碼..........................................52
4.1 Labview FPGA簡介..........................................................52
4.2 里德所羅門編碼設計與實作......................................................55
4.2.1 g(x)程式碼設計...................................................56
4.2.2 編碼位元與g(x)相除取餘數設計........................................57
4.2.3 里德所羅門編碼....................................................60
4.3 里德所羅門解碼設計與實作......................................................61
4.3.1 syndrome, S(x)程式碼設計..........................................61
4.3.2 error location, s (x) 程式碼設計..................................63
4.3.3 chien search 程式碼設計...........................................65
4.3.4 Forney Algorithm程式碼設計........................................66
4.3.5 里德所羅門解碼.....................................................67
4.3.6 里德所羅門碼於Labview FPGA設計之附件.................................53
4.4 渦輪乘積碼設計與實作..........................................................81
4.4.1 渦輪乘積碼解碼設計與實作.............................................83
4.4.2 Chase子程式......................................................85
4.4.3 Correct子程式....................................................87
4.4.4 Union子程式......................................................87
4.4.5 Revision子程式...................................................89
4.4.6 TPC於Labview FPGA設計之附件.......................................91
4.5 程式碼驗證..................................................................98
第五章 結果與討論........................................................................100
第六章 結論與未來展望.....................................................................104
參考文獻................................................................................105

[1] C.Berrou , A. Glavieux and P. Thitmajshima “Near Shannon limiterror-correcting coding and decoding : Turbo-codes ”, presented at the IEEE. Int. Conf .Communications, Geneva, Switerland ,May 1993.

[2] R.M. Pydiah ,” Near-optimum decoding of product codes : block turbo codes,” IEEE Trans Commun. ,Vol. 46,pp.1003-1010,Aug. 1998.

[3] P. Elias, “Error-free coding,” IRE Trans. Inform Theory, vol. IT-4, pp.29–37, Sept. 1954.

[4] Irving S. Reed, Xuemin Chen, Error-Contorl Coding for data networks, Kluwer Academic Publishers, 1997.

[5] W.S. Huang, “High-Speed pipeline VLSI Architecture for Reed-SolomonDecoder”, Master Thesis, Institute of Electronics, National Chiao-Tung University, June, 1993.

[6]S. B. Wicker, "Error Control Systems for Digital Communication and Storage". Prentice Hall, 1995.

[7]Wicker and Bhargava," Reed-Solomon codes and applications", IEEE Press, 1994.

[8]S. Whitaker, J. Canaris, and K. Cameron, “Reed-Solomon VLSI codec for advanced television,” IEEE Trans. Circuits Syst. Video Technol., vol. 1, pp. 230-236, June 199 1.

[9] Kuang Yung Liu," Architecture for VLSI Design of Reed-Solomon Decoders", IEEE Trans. On computers, vol. C-33, no. 2, Feb 1984.

[10]L. Song and K. K. "Parhi, Low-Energy Software Reed-Solomon Codecs Using Specialized Finite Field Datapath and Division-Free Berlekamp-Massey Algorithm, IEEE Symp". On Circuits ans Systems, June 1999.

[11] J. C. Huang, C. M. Wu, M. D. Shieh, C. H. Wu, “An Area-Efficient Versatile Reed-Solomon Decoder for ADSL”, IEEE Symposium, 1999.

[12]S. Baudyopadhyay and A. Sengupta, “ Algorithm for Multiplication in Galois Field for Implementation Using systolic Array,” IEE Proc. vol. 135, no:6, Nov. 1988.

[13]Jin-Chuan Huang, Chien-Ming Wu, Ming-Der Shieh, Chien-Hsing Wu, “An area-efficient versatile Reed-Solomon decoder for ADSL,” Proceedings of the 1999 IEEE International Symposium on Circuits and Systems, ISCAS '99, vol:1, pp. 517-520, 1999.

[14]Stephen B. Wicker, Vijay K. Bhargava, “Reed-Solomon codes and their applications”, New York: IEEE Press, 1994.

[15] Bruno Pattan, “Modulation Methods & Smart Antennas in Wireless Communications,” Prentice Hall PTR, 2000.

[16]D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE Trans. Inform. Theory, vol. IT-18, pp.170–182, Jan. 1972.

[17] Michael B. Pursley and Jason S. Skinner, “Decoding Strategies for Turbo Product Codes in Frequency-Hop Wireless Communications”, 2003

[18] Jia Jan Ong and L.-M Ang and K.P.Seng, “Implementation of (255,223) Reed-Solomon Minimal Instruction Set Computing using Handel-C”, 2010

[19] Tiago C. Barbosa and Robson L. Moreno and Tales C. Pareira and Luis H.C. Ferreira, ”FPGA Implementation of a Reed-Solomon CODEC for OTN G.709 Standard with Reduced Decoder Area”, 2010

[20] Mohamed Sayed Hassan and Karine Amis, “Turbo Product Code Decoding for Concatenated Space-Time Error Correcting Codes”, 2009

[21] Jiayan Zhang and Wenbin Zhang and Jing Ma, “Turbo Product Code Method for Real-Time Video Radio Transmission”, 2011

[22] Gabriel Marchesan Almeida and Luis Vitorio Cargnini and Daniel Gomes Mesquita, “A Reed-Solomon Algorithm for FPGA Optimization in Space Applications”, 2007

[23] Zefu Tan and Hong Xie and Guangjie Wu and Mingxia Liao, “Design and Implementation of Reed-Solomon Encoder in CMMB System”, 2010

[24] Jiabin You and Shaochuan Wu, “Design and Realization of Reed-Solomon Codec Based on FPGA Technique”, 2011

[25] G.C. cardarilli and S. Pontarelli and M.Re and A. Salsano, ”Design of a Self Checking Reed Solomon Encoder”, 2005

[26] Y.S. Kavian and A. Falahati and A. Khayatzadeh and M. Naderi, “High Speed Reed-Solomon with Pipeline Architecture”, 2005

[27] Dong-Sun Kim and Jong-Chan Choi and Duck-Jin Chung, ”Implementation of High Speed Reed-Solomon Decoder”, 1999

[28] Xiu-zhi Yang and Bing Song and Lin-huang Wu, “Implementation of RS Decoder based on FPGA in CMMB System”, 2010

[29] Liu Tong and Zhang Chuan, “Optimization Design of Reed-Solomon Decoder Based on FPGA”, 2011

[30] Camille Leroux and Christophe Jego and Patrick Adde and Michel Jezequel and Deepak Gupta, “A HIGHLY PARALLEL TURBO PRODUCT CODE DECODER WITHOUT INTERLEAVING RESOURCE”, 2008

[31] Changlong Xu and Ying-Chang Liang and Wing Seng Leon, “Low Complexity Decoding Algorithm for Turbo Product Codes”, 2007

[32] Erl-Huei Lu and Pen-Yao Lu, “A Syndrome-Based Hybrid Decoder for Turbo Product Codes”, 2010

[33] Nan-Hsiung Yeh and Philip L. Steiner and Yan Li, “Enhanced Message Passing in Turbo Product Code”, 2008

[34] Yinggang Du and Kam Tai Chan, “Enhanced Space-Time Block Coded Systems by Concatenating Turbo Product Codes”, 2004

[35] Yanni Chen and Keshab K. Parhi, “PARALLRL DECODING OF INTERLEAVED SINGLE PARITY CHECK TURBO PRODUCT CODES”, 2002

[36] Yejun He and P.C. Ching, “Performance Evaluation of Adaptive Two-Dimensional Turbo Product Codes Composed of Hamming Codes”, 2007

[37] Esam A. Obiedat and Wei Xiang, John Leis and Lei Cao, “Soft Incremental Redundancy for Distributed Turbo Product Codes”, 2010

[38] Changlong Xu and Ying-Chang Liang and Wing Seng Leon, “THE DESIGN AND DECODING SCHEMES FOR SHORTENED TURBO PRODUCT CODES”, 2006

[39] Cathy Y. Liu, Member, IEEE, and Shu Lin, Life Fellow, IEEE,” Turbo Encoding and Decoding of Reed–Solomon Codes Through Binary Decomposition and Self-Concatenation”, VOL. 52, NO. 9, SEPTEMBER 2004

[40] Omar AIT.SAB and Ramesh PYNDIAH, “PERFORMANCE OF REED-SOLOMON BLOCK TURBO CODE”, IEEE,1996

[41] Suman Mamidi, Daniel Iancu, Andrei Iancu, Michael J. Schulte, and John Glossner "Instruction set extensions for Reed-Solomon encoding and decoding", ASAP, Samos, pp. 231-237, July 2005.

[42] E. Berlecamp, "Bounded distance+1 soft decision Reed-Solomon decoding", IEEE Trans. Inform. Theory. vol. 42, pp. 704-720, May 1996.

[43] G. D. Forney, "Generalized Minimum Distance Decoding", IEEE Trans. Inform Theory, vol. IT-12. pp. 125-131, Apr. 1996.

[44] D. J. Taipale and M.B.Pursley, "An improvement to generalized minimum distance decoding", IEEE Trans. Inform. Theory, vol. IT-37,pp. 167-172, Jan. 1991.

[45] M.Lamarca, J.Sala-Alvarez, and A.Martinez, "Iterative decoding algorithm for RS-convolutional concatenated codes", Proc. of 3rd Intl. Symposium on Turbo Codes and Related Topics, pp.543-546, Brest (France), Sept. 2003

[46] J. Glossner, D. Iancu, J. Lu, E. Hokenek, and M. Moudgill, "A Software Defined Communications Baseband Design", IEEE Communications Magazine, vol. 41, no. 1, pp. 120-128, January 2003.