移动信道条件下RS码的应用及DSP实现相关问题研究
|
摘要
在数字通信中，纠错码技术得到了广泛的应用。作为一种性能优异的纠错码，RS码在实际应用中发挥着重要的作用。本论文的内容主要在于对RS码的算法、RS码在某些移动信道中的应用进行研究，并讨论RS码在DSP上编程实现的一些相关问题。
在本课题的研究中，选择了两个RS码作为研究对象，它们分别是RS(15，9，7)码和RS(255，223，33)码。这两个码的性能和参数存在着很大的差异，其应用背景也有所不同：RS(15，9，7)码用于允许较高编码冗余度的场合；其编译码速度较快。RS(255，223，33)码适用于低冗余度的场合；但其编译码速度较慢。本文的工作主要集中在以下几个方面：
1．对RS码的原理和常用编译码算法进行了简单的介绍；
2．基于错误图样重量分布的规律，提出了一种改进的RS码译码流程，并将其应用到RS(15，9，7)码的译码中。理论分析和实验都表明，改进译码流程比传统译码流程节省约30％～50％的计算量；
3．根据相关文献中提供的算法思想，推导出GF(2~8)有限域上的快速傅立叶变换公式和拉格朗日插值公式，并将它们应用到RS(255，223，33)码的快速编码和伴随式计算中，使这两步的计算量降低到原来的10％～30％；
4．讨论了RS码在TI TMS320C64x DSP上编程实现的相关问题(如用二表法实现有限域上的乘方运算)，并结合64xDSP的硬件结构和特点，对编译码过程中的某些算法进行了程序优化设计(如结合64x的有限域乘法器和流水线结构设计有限域上的求逆算法等)；
5．根据相关文献提供的信道参数，用隐Markov模型对不同调制方式、不同传信率及不同环境下的八个移动数字信道进行仿真。利用仿真的结果，分析RS(15，9，7)码和RS(255，223，33)码在这些信道中的纠错性能。实验表明，在结合适当的交织以后，两个RS码在这些信道中都能得到较好的纠错效果。
本文最后对全文的工作作了总结和展望，指出了以后的研究方向和工作重点。
The technology of error-correcting code has been widely used in the digital communication. As a good error-correcting code, RS code has been having a desired effect on many applications. So this thesis mainly researches on the algorithm of RS code and its application in some mobile channels, and discusses some issues about the implement on DSP of RS code.
During the research, two different types of RS code are selected as the studying objects. They are (15,9,7)RS code and (255,223,33)RS code.There are many differences between them concern their parameters and performances, so they have been used in different applications: RS(15,9,7) is suit for the application that allows high redundancy,but it has a high encoding-decoding speed; RS(255.223,33) is suit for the application of low redundancy,but it's slow when encoding-decoding. In this paper, several points are focused, which are listed below:
1. Principle and algorithm of RS code is introduced first;
2. An improved flow of RS decoding is proposed in this thesis. For (15,9,7)RS code, using this improved flow can reduce about 30%～50% of the computational complexity compare with the traditional one;
3. Basd on the idel of correlative thesis, we conclude the formula of DFT and Lagrange interpolation over GF(2~8) by program, and then use them to encoding the (255,223,33)RS code and computing its syndromes, and reduce 70%～80% of the computational complexity of these two steps;
4. Discuss some issues about the implement on TI TMS320C64x DSP of RS code(eg.algorithm for power operation over GF(2~8)). Optimize some steps of encoding and decoding combined with the characteristic of 64x DSP.
5. Based on the parameters provided by correlative thesis, eight digital mobile channels with different modulation,different data rata and different environment are simulated, using Markov model. Using the result of simulation, the performance of (15,9,7)RS code and (255,223,33)RS code in these channels are analysised. Experiment shows that combined with proper interlace, these two codes are both effective in these channels.
At last, conclusions and the direction of future improvement are summarized.
在本课题的研究中，选择了两个RS码作为研究对象，它们分别是RS(15，9，7)码和RS(255，223，33)码。这两个码的性能和参数存在着很大的差异，其应用背景也有所不同：RS(15，9，7)码用于允许较高编码冗余度的场合；其编译码速度较快。RS(255，223，33)码适用于低冗余度的场合；但其编译码速度较慢。本文的工作主要集中在以下几个方面：
1．对RS码的原理和常用编译码算法进行了简单的介绍；
2．基于错误图样重量分布的规律，提出了一种改进的RS码译码流程，并将其应用到RS(15，9，7)码的译码中。理论分析和实验都表明，改进译码流程比传统译码流程节省约30％～50％的计算量；
3．根据相关文献中提供的算法思想，推导出GF(2~8)有限域上的快速傅立叶变换公式和拉格朗日插值公式，并将它们应用到RS(255，223，33)码的快速编码和伴随式计算中，使这两步的计算量降低到原来的10％～30％；
4．讨论了RS码在TI TMS320C64x DSP上编程实现的相关问题(如用二表法实现有限域上的乘方运算)，并结合64xDSP的硬件结构和特点，对编译码过程中的某些算法进行了程序优化设计(如结合64x的有限域乘法器和流水线结构设计有限域上的求逆算法等)；
5．根据相关文献提供的信道参数，用隐Markov模型对不同调制方式、不同传信率及不同环境下的八个移动数字信道进行仿真。利用仿真的结果，分析RS(15，9，7)码和RS(255，223，33)码在这些信道中的纠错性能。实验表明，在结合适当的交织以后，两个RS码在这些信道中都能得到较好的纠错效果。
本文最后对全文的工作作了总结和展望，指出了以后的研究方向和工作重点。
The technology of error-correcting code has been widely used in the digital communication. As a good error-correcting code, RS code has been having a desired effect on many applications. So this thesis mainly researches on the algorithm of RS code and its application in some mobile channels, and discusses some issues about the implement on DSP of RS code.
During the research, two different types of RS code are selected as the studying objects. They are (15,9,7)RS code and (255,223,33)RS code.There are many differences between them concern their parameters and performances, so they have been used in different applications: RS(15,9,7) is suit for the application that allows high redundancy,but it has a high encoding-decoding speed; RS(255.223,33) is suit for the application of low redundancy,but it's slow when encoding-decoding. In this paper, several points are focused, which are listed below:
1. Principle and algorithm of RS code is introduced first;
2. An improved flow of RS decoding is proposed in this thesis. For (15,9,7)RS code, using this improved flow can reduce about 30%～50% of the computational complexity compare with the traditional one;
3. Basd on the idel of correlative thesis, we conclude the formula of DFT and Lagrange interpolation over GF(2~8) by program, and then use them to encoding the (255,223,33)RS code and computing its syndromes, and reduce 70%～80% of the computational complexity of these two steps;
4. Discuss some issues about the implement on TI TMS320C64x DSP of RS code(eg.algorithm for power operation over GF(2~8)). Optimize some steps of encoding and decoding combined with the characteristic of 64x DSP.
5. Based on the parameters provided by correlative thesis, eight digital mobile channels with different modulation,different data rata and different environment are simulated, using Markov model. Using the result of simulation, the performance of (15,9,7)RS code and (255,223,33)RS code in these channels are analysised. Experiment shows that combined with proper interlace, these two codes are both effective in these channels.
At last, conclusions and the direction of future improvement are summarized.
引文
[1]孙丽华．信息论与纠错编码[M]．北京：电子工业出版社，2005
[2]王新梅，肖国镇．纠错码原理与方法[M]．西安：西安电子科技大学出版社，2001
[3]Robert. H, Morelos-Zaragoza. The Art of Error Correctting Coding[M], John Wiley&Sons, 2002
[4]张宗橙．纠错编码原理和应用[M]．北京：电子工业出版社，2003
[5]杨家玮，盛敏，刘勤．移动通信基础[M]．北京：电子工业出版社，2005
[6]D.F.Yuan. The modelling for the mobile communication channel. IEEE TENCON90, Hong Kong, Sept. 1990
[1]王新梅，肖国镇．纠错码原理与方法[M]．西安：西安电子科技大学出版社．2001
[2]Robert.H, Morelos-Zaragoza. The Art of Error Correctting Coding[M], John Wiley&Sons, 2002
[3]吴瑕．RS码的研究与应用．西安．西安电子科技大学．2001
[4]孙军英．RS码的编译码算法及DSP实现．保定．华北电力大学．2003
[5]张玉良，陈晓敏．(255，223)RS码硬件译码器的实现[J]．计算机工程与应用，2005．27(103-104)
[6]蒋增荣，曾泳泓，余品能．快速算法[M]．长沙：国防科技大学出版社，1993
[7]张玉良．RS码硬件译码器的实现．北京．中国科学院空间科学与应用研究中心．2005
[8]林舒，科斯特洛．差错控制编码[M]．北京：人民邮电出版社，1986
[9]Massey J L. Step-by-step Decoding of the Bose-chaudhuri-hoequenghem Codes[J]. IEEE Trans, 1965, IT-11: 580-585
[10]T.C.Chen, C.H.Wei, S.W.Wei. Step-by-step decoding algorithm for Reed-Solomon code[J]. IEEE Proc-Commun, 2000.147(1): 8～12
[1]王新梅，肖国镇．纠错码原理与方法[M]．西安：西安电子科技大学出版社，2001
[2]C.L.CHEN. High-Speed Decoding of BCH Codes[J]. IEEE Trans.on Information Theory, 1981, IT-27(2): 254-256
[3]任友．RS码编译码算法研究及其硬件实现．成都：电子科技大学，2003
[4]PHIL K. Reed-Solomon coding/decoding package V1.0. http://www.pici-list.com/techref/method/error/rs-gp-pk-uoh-199609/index.htm, 1996.09
[5]袁东风．交错BCH码在移动信道中的性能估计[J]．山东大学学报(自然科学版)，1990，25(3)：329～335
[6]张宗橙．纠错编码原理和应用[M]．北京：电子工业出版社，2003
[7]蒋增荣，曾泳泓，余品能．快速算法[M]．长沙：国防科技大学出版社，1993
[8]C.S.Burrus, T.W.Parks. DFT/FFT and convolution algorithms[M]. New York: Wiley, c1985
[9]胡广书．数字信号处理[M]．北京：清华大学出版社，1993
[10]徐士良．计算机常用算法[M]．北京：清华大学出版社，1989
[11]Reed.I.S, Truong.T.K, Miller.R.L. Further Results on Fast Transforms for Decoding Reed-Solomon Codes Over GF(2^n) for n=4,5,6,8.Deep Space Network Progress Report 43～50, pp.132-154. Jet Propulsion Laboratory, Pasadena, Calif. Jan. 15,1979
[12]Reed.I.S, Truong.T.K, Miller.R.L. Fast Technique for Computing Syndro- mes of BCH and Reed-Solomon Codes. Deep Space Network Progress Report 42～52, pp.67-70. Jet Propulsion Laboratory, Pasadena, Calif.Aug.15,1979
[13]Miller.R.L, Truong.T.K, Reed.I.S. An Efficient Program for Decoding the (255,223) Reed-Solomon Code Over GF(2^8) With Both Errors and Erasures, Using Transform Decoding. Deep Space Network Progress Report 42-54, pp. 82-91, Sept. 1979
[14]Reed.I.S, Truong.T.K, Miller.R.L. Fast Algorithm for Encoding the (255,223) Reed-Solomon code over GF(2^8)[J]. Electronics Lett., 1980, 16(6): 222～223
[1]李方慧，王飞，何佩锟．TMS320C6000系列DSPs原理与应用[M]．北京：电子工业出版社，2003
[2]刘国华，刘钊．RS译码在C64系列DSP的实现[J]．实验科学与技术，2005，4：20～22
[3]姚志强，盛孟刚．宽带无线接入系统中长RS编解码的DSP设计与实现[J]．现代电子技术，2005，13：5～7
[4]孙军英．RS码的编译码算法及DSP实现．保定．华北电力大学．2003
[5]PHIL K. Reed-Solomon coding/decoding package V1.0. http://www.piclist.com/techref/techref/method/error/rs-gp-pk-uoh-199609/index.htm. 1996,09
[6]吴亚联，刘念，段斌．基于TMS320C64x系列DSPs的有限域乘法逆元算法的设计与实现[J]．电脑与信息技术，2004，3：23～26
[7]TMS320C6000 Programmerp's Guide. Texas Instruments. Inc.2000
[8]TMS320C6000 CPU and Instruction Set Reference Guide. Texas Instrume- nts. Inc.2000
[9]TMS320C6000 Optimizing Compiler User's Guide. Texas Instruments. Inc.2000
[1]F.Swarts, H.C.Ferreira. Markov Characterization of Digital Fading Mobile VHF Chmnnels[J]. IEEE Trans.Vehicular Technology, 1994, 43(4):977～985
[2]徐明远，邵玉．MATLAB仿真在通信与电子工程中的应用[M]．西安：西安电子科技大学出版社，2005
[3]William H．Tranter，K．Sam Shanmugan，Theodore S．Rappaport等．通信系统仿真原理与无线应用[M]．北京：机械工业出版社，2005
[4]L.Kittel. Radio signalling design and discrete channel modelling for mobile automatic telephone systems[J]. IEE International Mobile Radio Systems and Techniques, p86, 1984
[5]B.D.Fritchman. A Binary Channel Characterization Using Partitioned Markov Chains[J]. IEEE Trans.Inform Theory, 1967, IT-13: 221～227
[6]袁东风，吴开霞．移动信道三状态Markov模型建立及其差错序列的计算机软件产生[J]．山东大学学报(自然科学版)，1988,23(4)：34～42
[7]孙屹．MATLAB通信仿真开发手册[M]．北京：国防工业出版社，2004
[8]袁东风．移动信道误码性能分析及其纠错码选择[J]．移动通信，1990，1：32～37
[9]D.F.Yuan. The estimating on performance to interleaved BCH codes applied to the mobile communication channel. IEEE TENCON91 ,India, Aug. 1991
[10]D.F.Yuan, Z.G.Cao. On error-correcting performance of BCH codes in VHF mobile channel with different subcarrier modulation, different vehicle speed and different environment. IEEE 6th International Conference on Universal Personal Communications Record, 1997, p500～504
[2]王新梅，肖国镇．纠错码原理与方法[M]．西安：西安电子科技大学出版社，2001
[3]Robert. H, Morelos-Zaragoza. The Art of Error Correctting Coding[M], John Wiley&Sons, 2002
[4]张宗橙．纠错编码原理和应用[M]．北京：电子工业出版社，2003
[5]杨家玮，盛敏，刘勤．移动通信基础[M]．北京：电子工业出版社，2005
[6]D.F.Yuan. The modelling for the mobile communication channel. IEEE TENCON90, Hong Kong, Sept. 1990
[1]王新梅，肖国镇．纠错码原理与方法[M]．西安：西安电子科技大学出版社．2001
[2]Robert.H, Morelos-Zaragoza. The Art of Error Correctting Coding[M], John Wiley&Sons, 2002
[3]吴瑕．RS码的研究与应用．西安．西安电子科技大学．2001
[4]孙军英．RS码的编译码算法及DSP实现．保定．华北电力大学．2003
[5]张玉良，陈晓敏．(255，223)RS码硬件译码器的实现[J]．计算机工程与应用，2005．27(103-104)
[6]蒋增荣，曾泳泓，余品能．快速算法[M]．长沙：国防科技大学出版社，1993
[7]张玉良．RS码硬件译码器的实现．北京．中国科学院空间科学与应用研究中心．2005
[8]林舒，科斯特洛．差错控制编码[M]．北京：人民邮电出版社，1986
[9]Massey J L. Step-by-step Decoding of the Bose-chaudhuri-hoequenghem Codes[J]. IEEE Trans, 1965, IT-11: 580-585
[10]T.C.Chen, C.H.Wei, S.W.Wei. Step-by-step decoding algorithm for Reed-Solomon code[J]. IEEE Proc-Commun, 2000.147(1): 8～12
[1]王新梅，肖国镇．纠错码原理与方法[M]．西安：西安电子科技大学出版社，2001
[2]C.L.CHEN. High-Speed Decoding of BCH Codes[J]. IEEE Trans.on Information Theory, 1981, IT-27(2): 254-256
[3]任友．RS码编译码算法研究及其硬件实现．成都：电子科技大学，2003
[4]PHIL K. Reed-Solomon coding/decoding package V1.0. http://www.pici-list.com/techref/method/error/rs-gp-pk-uoh-199609/index.htm, 1996.09
[5]袁东风．交错BCH码在移动信道中的性能估计[J]．山东大学学报(自然科学版)，1990，25(3)：329～335
[6]张宗橙．纠错编码原理和应用[M]．北京：电子工业出版社，2003
[7]蒋增荣，曾泳泓，余品能．快速算法[M]．长沙：国防科技大学出版社，1993
[8]C.S.Burrus, T.W.Parks. DFT/FFT and convolution algorithms[M]. New York: Wiley, c1985
[9]胡广书．数字信号处理[M]．北京：清华大学出版社，1993
[10]徐士良．计算机常用算法[M]．北京：清华大学出版社，1989
[11]Reed.I.S, Truong.T.K, Miller.R.L. Further Results on Fast Transforms for Decoding Reed-Solomon Codes Over GF(2^n) for n=4,5,6,8.Deep Space Network Progress Report 43～50, pp.132-154. Jet Propulsion Laboratory, Pasadena, Calif. Jan. 15,1979
[12]Reed.I.S, Truong.T.K, Miller.R.L. Fast Technique for Computing Syndro- mes of BCH and Reed-Solomon Codes. Deep Space Network Progress Report 42～52, pp.67-70. Jet Propulsion Laboratory, Pasadena, Calif.Aug.15,1979
[13]Miller.R.L, Truong.T.K, Reed.I.S. An Efficient Program for Decoding the (255,223) Reed-Solomon Code Over GF(2^8) With Both Errors and Erasures, Using Transform Decoding. Deep Space Network Progress Report 42-54, pp. 82-91, Sept. 1979
[14]Reed.I.S, Truong.T.K, Miller.R.L. Fast Algorithm for Encoding the (255,223) Reed-Solomon code over GF(2^8)[J]. Electronics Lett., 1980, 16(6): 222～223
[1]李方慧，王飞，何佩锟．TMS320C6000系列DSPs原理与应用[M]．北京：电子工业出版社，2003
[2]刘国华，刘钊．RS译码在C64系列DSP的实现[J]．实验科学与技术，2005，4：20～22
[3]姚志强，盛孟刚．宽带无线接入系统中长RS编解码的DSP设计与实现[J]．现代电子技术，2005，13：5～7
[4]孙军英．RS码的编译码算法及DSP实现．保定．华北电力大学．2003
[5]PHIL K. Reed-Solomon coding/decoding package V1.0. http://www.piclist.com/techref/techref/method/error/rs-gp-pk-uoh-199609/index.htm. 1996,09
[6]吴亚联，刘念，段斌．基于TMS320C64x系列DSPs的有限域乘法逆元算法的设计与实现[J]．电脑与信息技术，2004，3：23～26
[7]TMS320C6000 Programmerp's Guide. Texas Instruments. Inc.2000
[8]TMS320C6000 CPU and Instruction Set Reference Guide. Texas Instrume- nts. Inc.2000
[9]TMS320C6000 Optimizing Compiler User's Guide. Texas Instruments. Inc.2000
[1]F.Swarts, H.C.Ferreira. Markov Characterization of Digital Fading Mobile VHF Chmnnels[J]. IEEE Trans.Vehicular Technology, 1994, 43(4):977～985
[2]徐明远，邵玉．MATLAB仿真在通信与电子工程中的应用[M]．西安：西安电子科技大学出版社，2005
[3]William H．Tranter，K．Sam Shanmugan，Theodore S．Rappaport等．通信系统仿真原理与无线应用[M]．北京：机械工业出版社，2005
[4]L.Kittel. Radio signalling design and discrete channel modelling for mobile automatic telephone systems[J]. IEE International Mobile Radio Systems and Techniques, p86, 1984
[5]B.D.Fritchman. A Binary Channel Characterization Using Partitioned Markov Chains[J]. IEEE Trans.Inform Theory, 1967, IT-13: 221～227
[6]袁东风，吴开霞．移动信道三状态Markov模型建立及其差错序列的计算机软件产生[J]．山东大学学报(自然科学版)，1988,23(4)：34～42
[7]孙屹．MATLAB通信仿真开发手册[M]．北京：国防工业出版社，2004
[8]袁东风．移动信道误码性能分析及其纠错码选择[J]．移动通信，1990，1：32～37
[9]D.F.Yuan. The estimating on performance to interleaved BCH codes applied to the mobile communication channel. IEEE TENCON91 ,India, Aug. 1991
[10]D.F.Yuan, Z.G.Cao. On error-correcting performance of BCH codes in VHF mobile channel with different subcarrier modulation, different vehicle speed and different environment. IEEE 6th International Conference on Universal Personal Communications Record, 1997, p500～504