RS码编译码算法研究及其硬件实现
摘要
本文主要研究在二次雷达系统中进行数据传输时如何保证通信的可靠性，也即如何设计合理的纠错码方案以减少误码率。
纠错码技术是一种通过增加一定的冗余信息来提高信息传输可靠性的有效方法。RS码是一种典型的纠错码，在线性分组码中，它具有最强的纠错能力，既能纠正随机错误，也能纠正突发错误。同时，随着对RS码研究的深入、RS编译码算法的改进和相关技术的发展，RS码在实际中的应用也更加广泛。
在本文中，采用RS码作为二次雷达系统数据链中进行差错控制的主要纠错码，研究了RS码的编译码算法及其硬件实现。对编译码算法的改进有助于提高RS编译码器的性能，而利用FPGA来实现RS编译码器，并采用流水线、心缩式阵列等优化结构，更能提高编译码器的性能。此外，虽然本方案主要针对的是RS(31,15)码型，但在设计中也考虑到RS码的参数可配置性。
本文首先介绍相关背景和编码理论，接着提出纠错码的设计方案，介绍RS编译码算法，并对其性能进行仿真，最后设计出RS编译码器的硬件电路，后期的试验表明编译码器达到了预期的纠错性能。
This paper mainly discusses how to guarantee information's reliable transmission in a type of SSR system. Proper channel-coding scheme is designed to decrease error-rate in digital transmission.
Error-correcting codes work by adding extra information to original data. Among the linear block codes, RS code is an important one widely used in modern digital communications, which can correct both random and bursty errors with the most powerful error-correcting capability.
In this scheme, RS code is selected as the main error-correcting code. Its encoding/decoding algorithms and hardware implements are researched. Improve on algorithms can enhance encoding/decoding performance. With pipeline and systolic array architectures adopted in the hardware implements, encoder/decoder based on FPGA can work better. Although this scheme lays more emphasis on RS(31,15), it also considers the parameters' programmability of RS code, which can expand its applications.
In this paper, firstly, we introduce the relevant background and the coding theory. Subsequently, we present the error-correcting scheme in this SSR system and elaborate on RS encoding/decoding algorithms and then simulate the selected codes' error-correcting capability. Finally, we implement RS codec with FPGA technology and the experiments show that desired targets can be achieved.
纠错码技术是一种通过增加一定的冗余信息来提高信息传输可靠性的有效方法。RS码是一种典型的纠错码，在线性分组码中，它具有最强的纠错能力，既能纠正随机错误，也能纠正突发错误。同时，随着对RS码研究的深入、RS编译码算法的改进和相关技术的发展，RS码在实际中的应用也更加广泛。
在本文中，采用RS码作为二次雷达系统数据链中进行差错控制的主要纠错码，研究了RS码的编译码算法及其硬件实现。对编译码算法的改进有助于提高RS编译码器的性能，而利用FPGA来实现RS编译码器，并采用流水线、心缩式阵列等优化结构，更能提高编译码器的性能。此外，虽然本方案主要针对的是RS(31,15)码型，但在设计中也考虑到RS码的参数可配置性。
本文首先介绍相关背景和编码理论，接着提出纠错码的设计方案，介绍RS编译码算法，并对其性能进行仿真，最后设计出RS编译码器的硬件电路，后期的试验表明编译码器达到了预期的纠错性能。
This paper mainly discusses how to guarantee information's reliable transmission in a type of SSR system. Proper channel-coding scheme is designed to decrease error-rate in digital transmission.
Error-correcting codes work by adding extra information to original data. Among the linear block codes, RS code is an important one widely used in modern digital communications, which can correct both random and bursty errors with the most powerful error-correcting capability.
In this scheme, RS code is selected as the main error-correcting code. Its encoding/decoding algorithms and hardware implements are researched. Improve on algorithms can enhance encoding/decoding performance. With pipeline and systolic array architectures adopted in the hardware implements, encoder/decoder based on FPGA can work better. Although this scheme lays more emphasis on RS(31,15), it also considers the parameters' programmability of RS code, which can expand its applications.
In this paper, firstly, we introduce the relevant background and the coding theory. Subsequently, we present the error-correcting scheme in this SSR system and elaborate on RS encoding/decoding algorithms and then simulate the selected codes' error-correcting capability. Finally, we implement RS codec with FPGA technology and the experiments show that desired targets can be achieved.
引文
1. 韩作生,袁东风.RS码频域编译码的计算机模拟.通信学报,1994,Vol.15,No.6: pp.104~112.
2. 井洪,尹俊勋.移动信道中交错RS码纠错能力的计算机模拟.华南理工大学学报(自然科学版),1996,Vol.24,No.4: pp.63~69.
3. 曾晓洋,郝志航,魏仲慧.RS码时域编码算法及其计算机模拟.系统工程与电子技术, 2001,Vol.23,No.3: pp.16~18.
4. 朱起悦.RS码编码和译码的算法.电讯技术,1999,Vol.39,No.2: pp.63~67.
5. 罗开杰.RS码编译码及其快速实现:[硕士学位论文].成都:电子科技大学,2000.
6. 夏芳.ATSC-8VSB接收芯片中外码系统的设计与实现:[硕士学位论文].杭州:浙江大学,2002.
7. 曾晓洋.高性能Reed-Solomon码编译码方法及相关技术的研究:[博士学位论文].长春:中国科学院长春光学精密机械与物理研究所,2001.
8. 《中国大百科全书.电子学与计算机卷》（光盘1.2版）.北京:中国大百科全书出版社,2001.
9. 曹志刚,钱亚生.《现代通信原理》.北京:清华大学出版社,1992.
10. 丁鹭飞,耿富录.《雷达原理》.西安:西安电子科技大学出版社,1995.
11. 侯伯亨,顾新.《VHDL硬件描述语言与数字逻辑设计》.西安:西安电子科技大学出版社,1999.
12. 黎廷璋.《空中交通管制机载应答机》.北京:国防工业出版社,1992.
13. 李广军,孟宪元.《可编程ASIC设计及应用》.成都:电子科技大学出版社,2000.
14. 林苏,科斯特洛.《差错控制编码基础和应用》(王育民,王新梅 译).北京:人民邮电出版社,1986.
15. 梅文华,杨义先.《跳频通信地址编码理论》.北京:国防工业出版社,1996.
16. 申敏,邓矣兵,郑建宏等.《DSP原理及其在移动通信中的应用》.北京:人民邮电出版社,2001.
17. 王金龙,沈良,任国春等.《无线通信系统的DSP实现》.北京:人民邮电出版社,2002.
18. 王念旭.《DSP基础与应用系统设计》.北京:北京航空航天大学出版社.2001.
19. 王新梅,马文平,武传坤.《纠错密码理论》.北京:人民邮电出版社,2001.
王新梅,肖国镇.《纠错码——原理与方法》.西安:西安电子科技大学出版
20. 社,2000.
21. 徐志军,徐光辉.《CPLD/FPGA的开发与应用》.北京:电子工业出版社,2000.
22. 张鸣瑞,邹世开.《编码理论》.北京:北京航空航天大学出版社,1990.
23. G. C. Clark, Jr., J. B. Cain, Error-Correction Coding for Digital Communications, New York: Plenum Press, 1981.
24. J. G. Proakis, Digital Communications, New York: McGraw-Hill, 2001.
25. S. B. Wicker, Error Control Systems for Digital Communication and Storage, Englewood Cliffs: Prentice-Hall, Inc., 1995.
26. S. G. Wilson, Digital Modulation and Coding, Englewood Cliffs: Prentice-Hall, Inc., 1996.
27. C. E. Shannon, "A Mathematical Theory of Communications", Bell Syst. Tech. J., 1948, Vol. 27: pp. 379~423 & pp. 623~656.
28. D. J. Costello, Jr., J. Hagenauer & H. Imai, et al., "Applications of Error-Control Coding", IEEE Trans. on Information Theory, 1998, Vol. 44, No. 6: pp. 2531~2560.
29. E. Boutillon, A. Dehamel, "Architecture for a Smart Reed-Solomon Decoder", IEEE Trans. on Information Theory, 1991, Vol.37, No. 4: pp. 236~239.
30. E. Petre, G. Masera, "A Parametrical Architecture for Reed-Solomon Decoders", 1996 IEEE: pp. 81~84.
31. E. R. Berlekamp, "Bit-Serial Reed-Solomon Encoders", IEEE Trans. on Information Theory, 1982, Vol. IT-28, No. 6: pp. 869~874.
32. G. D. Forney, Jr., "Generalized Minimum Distance Decoding", IEEE Trans. on Information Theory, 1966, Vol. IT-12, No. 2: pp. 125~131.
33. G. D. Forney, Jr., "On Decoding BCH Codes", IEEE Trans. on Information Theory, 1965, Vol. IT-11, No. 4: pp. 549~557.
34. G. L. Feng, "A VLSI Architecture for Fast Inversion in ", IEEE Trans. on Computers, 1989, Vol. 38, No. 10: pp. 1383~1386.
35. H. Brunner, A. Curiger & M. Hofstetter, "On Computing Multiplicative Inverses in ", 1993, Vol. 42, No. 8, 1010~1015.
36. H. M. Shao, I. S. Reed, "A VLSI Design of a Pipeline Reed-Solomon Decoder", IEEE Trans. on Computers, 1985, Vol. C-34, No. 5: pp. 393~402.
37. H. M. Shao, I. S. Reed, "On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays", IEEE Trans. On Computers, 1988, Vol. 37, No. 10: pp. 1273~1280.
38. I. S. Reed, G. Solomon, "Polynomial Codes over Certain Finite Fields", J. Soc. Indust. Appl. Math., 1960: pp. 300~304.
39. J. L. Massey, "Shift-Register Synthesis and BCH Decoding", IEEE Trans. on Information Theory, 1969, Vol. IT-15, No. 1: pp. 122~127.
40. K. Y. Liu, "Architecture for VLSI Design of Reed-Solomon Decoders", IEEE Trans. on Computers, 1984, Vol. C-33, No. 2: pp. 178~189.
41. M. A. Hasan, A. G. Wassal, "VLSI Algorithms, Architectures and Implementation of a Versatile Processor", IEEE Trans. on Computers, 2000, Vol. 49, No.10: pp. 1064~1073.
42. N. Demassieux, F. Jutand & M. Muller, "A 10-MHz (255,223) Reed-Solomon Decoder", IEEE 1998 Custom Integrated Circuit Conference: pp. 17.6.1~17.6.4.
43. P. Tong, "A 40-MHz Encoder-Decoder Chip Generated by a Reed-Solomon Code Compiler", IEEE 1990 Custom Integrated Circuit Conference: pp. 13.5.1~13.5.4.
44. R. C. Bose, D. K. Ray-Chaudhuri, "On a Class of Error Correcting Binary Group Codes", IEEE Trans. on Information Theory, 1960, Vol. 3, No. 3, pp. 68~79.
45. R. E. Blahut, "A Universal Reed-Solomon Decoder", IBM J. Res. and Devel., 1984, Vol. 28, No. 3: pp. 150~158.
46. R. T. Chien, "Cyclic Decoding Procedures for Bose-Chaudhuri-Hocquenghem Codes", IEEE Trans. on Information Theory, 1964, Vol. 10, No. 10: pp. 357~363.
47. S. Choomchuay, B. Arambepola, "Time Domain Algorithms and Architectures for Reed-Solomon Decoding", IEE Proceedings-I, 1993, Vol. 140, No.3: pp. 189~196.
48. S. K. Jain, K. K. Parhi, "Efficient Standard Basis Reed-Solomon Encoder", 1996 IEEE: pp. 3287~3290.
49. S. Verdú, "Fifty Years of Shannon Theory", IEEE Trans. on Information Theory, 1998, Vol. 44, No. 6: pp. 2057~2078.
50. T. A. Gulliver, M. Jorgenson & W. K. Moreland, "Performance of Reed-Solomon Codes with Dependent Symbol Errors", IEE Proc.-Commun., 1996, Vol. 143, No. 3: pp. 117~121.
51. T. K. Matsushima, T. Matsushima, S. Hirasawa, "Parallel Architecture for High-Speed Reed-Solomon Codec", 1998 IEEE: pp. 468~473.
52. W. J. Ebel, W. H. Tranter, "The Performance of Reed-Solomon Codes on a Bursty-Noise Channel", IEEE Trans. on Communications, 1995, Vol. 43, No. 2/3/4: pp. 298~306.
53. W. W. Peterson, "Encoding and Error-Correcting Procedures for the Bose-Chaudhuri-Hocauenghem Codes", IRE Trans. on Information Theory, 1960, Vol. 6, No. 9: pp. 459~470.
54. W. Wilhelm, "A New Scalable VLSI Architecture for Reed-Solomon Decoders", IEEE Journal of Solid-State Circuits, 1999, Vol. 34, No. 3: pp. 388~396.
55. Y. R. Shayan, T. L. Ngoc & V. K. Bhargava, "A Versatile Time-Domain Reed-Solomon Decoder", IEEE Journal on Selected Areas in Communications, 1990, Vol. 8, No. 8: pp. 1535~1542.
56. AMD. AM28F512: 512 Kilobit (64K*8-Bit) CMOS 12.0 Volt, Bulk Erase Flash Memory. 1998.
57. Maxim. ±15kV ESD-Protected, +5V RS-232 Transceivers. 1996.
58. Texas Instruments. TMS320C54x DSP Reference Set. 1999.
59. Texas Instruments. TMS320VC5409 Fixed-Point Digital Signal Processor. 2000.
60. Texas Instruments. TPS73HD301, TPS73HD318, TPS73HD325 Dual-Output Low-Dropout Regulators. 1999.
61. Xilinx. VirtexTM 2.5V Field Programmable Gate Arrays. 2001.
62. Xilinx. XVC1800 Series of In-System Programmable Configuration PROMs. 2000.
2. 井洪,尹俊勋.移动信道中交错RS码纠错能力的计算机模拟.华南理工大学学报(自然科学版),1996,Vol.24,No.4: pp.63~69.
3. 曾晓洋,郝志航,魏仲慧.RS码时域编码算法及其计算机模拟.系统工程与电子技术, 2001,Vol.23,No.3: pp.16~18.
4. 朱起悦.RS码编码和译码的算法.电讯技术,1999,Vol.39,No.2: pp.63~67.
5. 罗开杰.RS码编译码及其快速实现:[硕士学位论文].成都:电子科技大学,2000.
6. 夏芳.ATSC-8VSB接收芯片中外码系统的设计与实现:[硕士学位论文].杭州:浙江大学,2002.
7. 曾晓洋.高性能Reed-Solomon码编译码方法及相关技术的研究:[博士学位论文].长春:中国科学院长春光学精密机械与物理研究所,2001.
8. 《中国大百科全书.电子学与计算机卷》（光盘1.2版）.北京:中国大百科全书出版社,2001.
9. 曹志刚,钱亚生.《现代通信原理》.北京:清华大学出版社,1992.
10. 丁鹭飞,耿富录.《雷达原理》.西安:西安电子科技大学出版社,1995.
11. 侯伯亨,顾新.《VHDL硬件描述语言与数字逻辑设计》.西安:西安电子科技大学出版社,1999.
12. 黎廷璋.《空中交通管制机载应答机》.北京:国防工业出版社,1992.
13. 李广军,孟宪元.《可编程ASIC设计及应用》.成都:电子科技大学出版社,2000.
14. 林苏,科斯特洛.《差错控制编码基础和应用》(王育民,王新梅 译).北京:人民邮电出版社,1986.
15. 梅文华,杨义先.《跳频通信地址编码理论》.北京:国防工业出版社,1996.
16. 申敏,邓矣兵,郑建宏等.《DSP原理及其在移动通信中的应用》.北京:人民邮电出版社,2001.
17. 王金龙,沈良,任国春等.《无线通信系统的DSP实现》.北京:人民邮电出版社,2002.
18. 王念旭.《DSP基础与应用系统设计》.北京:北京航空航天大学出版社.2001.
19. 王新梅,马文平,武传坤.《纠错密码理论》.北京:人民邮电出版社,2001.
王新梅,肖国镇.《纠错码——原理与方法》.西安:西安电子科技大学出版
20. 社,2000.
21. 徐志军,徐光辉.《CPLD/FPGA的开发与应用》.北京:电子工业出版社,2000.
22. 张鸣瑞,邹世开.《编码理论》.北京:北京航空航天大学出版社,1990.
23. G. C. Clark, Jr., J. B. Cain, Error-Correction Coding for Digital Communications, New York: Plenum Press, 1981.
24. J. G. Proakis, Digital Communications, New York: McGraw-Hill, 2001.
25. S. B. Wicker, Error Control Systems for Digital Communication and Storage, Englewood Cliffs: Prentice-Hall, Inc., 1995.
26. S. G. Wilson, Digital Modulation and Coding, Englewood Cliffs: Prentice-Hall, Inc., 1996.
27. C. E. Shannon, "A Mathematical Theory of Communications", Bell Syst. Tech. J., 1948, Vol. 27: pp. 379~423 & pp. 623~656.
28. D. J. Costello, Jr., J. Hagenauer & H. Imai, et al., "Applications of Error-Control Coding", IEEE Trans. on Information Theory, 1998, Vol. 44, No. 6: pp. 2531~2560.
29. E. Boutillon, A. Dehamel, "Architecture for a Smart Reed-Solomon Decoder", IEEE Trans. on Information Theory, 1991, Vol.37, No. 4: pp. 236~239.
30. E. Petre, G. Masera, "A Parametrical Architecture for Reed-Solomon Decoders", 1996 IEEE: pp. 81~84.
31. E. R. Berlekamp, "Bit-Serial Reed-Solomon Encoders", IEEE Trans. on Information Theory, 1982, Vol. IT-28, No. 6: pp. 869~874.
32. G. D. Forney, Jr., "Generalized Minimum Distance Decoding", IEEE Trans. on Information Theory, 1966, Vol. IT-12, No. 2: pp. 125~131.
33. G. D. Forney, Jr., "On Decoding BCH Codes", IEEE Trans. on Information Theory, 1965, Vol. IT-11, No. 4: pp. 549~557.
34. G. L. Feng, "A VLSI Architecture for Fast Inversion in ", IEEE Trans. on Computers, 1989, Vol. 38, No. 10: pp. 1383~1386.
35. H. Brunner, A. Curiger & M. Hofstetter, "On Computing Multiplicative Inverses in ", 1993, Vol. 42, No. 8, 1010~1015.
36. H. M. Shao, I. S. Reed, "A VLSI Design of a Pipeline Reed-Solomon Decoder", IEEE Trans. on Computers, 1985, Vol. C-34, No. 5: pp. 393~402.
37. H. M. Shao, I. S. Reed, "On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays", IEEE Trans. On Computers, 1988, Vol. 37, No. 10: pp. 1273~1280.
38. I. S. Reed, G. Solomon, "Polynomial Codes over Certain Finite Fields", J. Soc. Indust. Appl. Math., 1960: pp. 300~304.
39. J. L. Massey, "Shift-Register Synthesis and BCH Decoding", IEEE Trans. on Information Theory, 1969, Vol. IT-15, No. 1: pp. 122~127.
40. K. Y. Liu, "Architecture for VLSI Design of Reed-Solomon Decoders", IEEE Trans. on Computers, 1984, Vol. C-33, No. 2: pp. 178~189.
41. M. A. Hasan, A. G. Wassal, "VLSI Algorithms, Architectures and Implementation of a Versatile Processor", IEEE Trans. on Computers, 2000, Vol. 49, No.10: pp. 1064~1073.
42. N. Demassieux, F. Jutand & M. Muller, "A 10-MHz (255,223) Reed-Solomon Decoder", IEEE 1998 Custom Integrated Circuit Conference: pp. 17.6.1~17.6.4.
43. P. Tong, "A 40-MHz Encoder-Decoder Chip Generated by a Reed-Solomon Code Compiler", IEEE 1990 Custom Integrated Circuit Conference: pp. 13.5.1~13.5.4.
44. R. C. Bose, D. K. Ray-Chaudhuri, "On a Class of Error Correcting Binary Group Codes", IEEE Trans. on Information Theory, 1960, Vol. 3, No. 3, pp. 68~79.
45. R. E. Blahut, "A Universal Reed-Solomon Decoder", IBM J. Res. and Devel., 1984, Vol. 28, No. 3: pp. 150~158.
46. R. T. Chien, "Cyclic Decoding Procedures for Bose-Chaudhuri-Hocquenghem Codes", IEEE Trans. on Information Theory, 1964, Vol. 10, No. 10: pp. 357~363.
47. S. Choomchuay, B. Arambepola, "Time Domain Algorithms and Architectures for Reed-Solomon Decoding", IEE Proceedings-I, 1993, Vol. 140, No.3: pp. 189~196.
48. S. K. Jain, K. K. Parhi, "Efficient Standard Basis Reed-Solomon Encoder", 1996 IEEE: pp. 3287~3290.
49. S. Verdú, "Fifty Years of Shannon Theory", IEEE Trans. on Information Theory, 1998, Vol. 44, No. 6: pp. 2057~2078.
50. T. A. Gulliver, M. Jorgenson & W. K. Moreland, "Performance of Reed-Solomon Codes with Dependent Symbol Errors", IEE Proc.-Commun., 1996, Vol. 143, No. 3: pp. 117~121.
51. T. K. Matsushima, T. Matsushima, S. Hirasawa, "Parallel Architecture for High-Speed Reed-Solomon Codec", 1998 IEEE: pp. 468~473.
52. W. J. Ebel, W. H. Tranter, "The Performance of Reed-Solomon Codes on a Bursty-Noise Channel", IEEE Trans. on Communications, 1995, Vol. 43, No. 2/3/4: pp. 298~306.
53. W. W. Peterson, "Encoding and Error-Correcting Procedures for the Bose-Chaudhuri-Hocauenghem Codes", IRE Trans. on Information Theory, 1960, Vol. 6, No. 9: pp. 459~470.
54. W. Wilhelm, "A New Scalable VLSI Architecture for Reed-Solomon Decoders", IEEE Journal of Solid-State Circuits, 1999, Vol. 34, No. 3: pp. 388~396.
55. Y. R. Shayan, T. L. Ngoc & V. K. Bhargava, "A Versatile Time-Domain Reed-Solomon Decoder", IEEE Journal on Selected Areas in Communications, 1990, Vol. 8, No. 8: pp. 1535~1542.
56. AMD. AM28F512: 512 Kilobit (64K*8-Bit) CMOS 12.0 Volt, Bulk Erase Flash Memory. 1998.
57. Maxim. ±15kV ESD-Protected, +5V RS-232 Transceivers. 1996.
58. Texas Instruments. TMS320C54x DSP Reference Set. 1999.
59. Texas Instruments. TMS320VC5409 Fixed-Point Digital Signal Processor. 2000.
60. Texas Instruments. TPS73HD301, TPS73HD318, TPS73HD325 Dual-Output Low-Dropout Regulators. 1999.
61. Xilinx. VirtexTM 2.5V Field Programmable Gate Arrays. 2001.
62. Xilinx. XVC1800 Series of In-System Programmable Configuration PROMs. 2000.