摘要
RS(Reed-Solomon)码因其具有优良的纠突发错误和随机错误的能力,而被广泛用于数据传输和存储系统中。本文在研究RS码的理论和分析DVD标准的基础上,对算法实现、电路结构、流程控制等进行了优化,给出了一种基于DVD应用的全程流水线纠错纠删RS-PC译码器芯片的VLSI设计。该RS-PC译码器芯片的特点是全程流水线实现,面积小,速度快,纠错能力强,可纠错和纠删,时序控制简单,电路实现简洁,并有较好的扩展能力。该芯片可对DVD数据在存储和读取中引入的错误进行纠错处理,也可作为IP核,用于DVD伺服控制芯片的设计和实现。
本文提出的流水线处理的纠错纠删RS-PC译码芯片主要模块包括行RS(182,172)译码器、列RS(208,192)译码器和数据块缓冲管理器。在译码器的设计中,采用修正的欧几里德(ME)算法,并将其优化,降低了设计的复杂度,实现了能够同时纠错和纠删;采用三级流水线结构,使RS译码处理速度达到每时钟一个符号;采用模块复用的设计思想实现关键方程的求解,达到面积优化和电路规整。在数据块缓冲管理器的设计中,采用一种基于二维数据重排的访问方式,实现高速高效的DRAM访问。在RS-PC译码器芯片的顶层,采用外接DRAM的缓冲管理器,实现全程流水线处理的RS-PC译码器,提高了译码的运算速度,达到RS-PC译码速度每时钟一个符号。
本文在DVD标准的基础上,定义了RS-PC译码器设计流程;为验证采用的算法和产生的测试数据,设计了RS-PC编译码器的Matlab模型;采用Verilog HDL实现译码器芯片的电路硬件描述,同时进行了功能仿真与时序验证,并进行了FPGA实现。功能仿真与时序验证的结果表明,该RS-PC译码芯片的设计满足预期的性能要求:处理速度达到每时钟译码一个接收符号;在纠错能力上:行纠错能力达到纠正5个错误或10个删除,列纠错能力达到纠正8个错误或16个删除;外接100MHz的SDR DRAM,可实现译码数据吞吐率40Mbytes/s,达到12×DVD的处理要求。
RS (Reed-Solomon) code has been widely employed in data transmission and storage systems owing to its excellent capability for correcting burst errors and random errors. Based on the research of RS code theory, analysis of DVD specification, and optimization improved from algorithm, this paper presents a full-process pipelined Errors-and-Erasures correcting Reed-Solomon Product-Code (RS-PC) decoders chip for DVD application. It features full-process pipelined, high-speed decoding, high performance correcting, simpleness of control timing, succinctness of circuit implementation, area efficient, and with good extend capacity. It can correct errors-and-erasures introduced in the process of storage and recovery of DVD data and also can be used as an IP core in the design of DVD servo chip.
The main module of the RS-PC decoder chip are two pipelined Errors-and-Erasures correcting RS decoders and a block buffer manager. The RS decoder features an area-efficient key equation solver using a modified Euclid algorithm, which reduced the complexity of the design. Based on the methods of modules reuse, the proposed RS decoder are very regular and area efficient. Using three stage pipelines, the RS decoder can operate at a rate of 1 byte/clk. Based on a method of 2 dimension data rearrange, a high speed and high efficiency implementation of DRAM access is proposed in the design of block buffer manager. Using the block buffer manager with off-chip DRAM, a (182,172) row RS decoder and a (208,182) column RS decoder can be pipelined, which double the speed of RS-PC decoder and get a rate of 1 byte/clk.
Based on the DVD specifications, the RS-PC decoder chip design is defined. The Matlab model of RS-PC encoders and decoder is presented for the verification of the algorithm. The hardware of RS-PC decoder chip is described in the Verilog HDL, function simulation and timing verification are processed, and then is implemented in a Altera FPGA. Through the function simulation and timing verification, the proposed RS-PC decoder meet the expected performance requirement, which gets the rates of one byte per clock, gets the max row error correcting of 5 errors of 10 erasures and the max column error correcting of 8 errors or 16 erasures, gets a data rate 40Mbytes/s interfaced with 100MHz SDR DRAM, which meet the 12×DVD performance requirement.
引文
[1] 王新梅,肖国镇.《纠错码-原理与方法》(修订版). 西安:西安电子科技大学出版社,2001.
[2] 王新梅. 纠错码浅说. 北京: 人民邮电出版社, 1976
[3] 王新梅. 纠错码与差错控制. 北京: 人民邮电出版社, 1989
[4] Rober J. McEliece 著, 李斗, 殷悦等译. 信息论与编码理论(第二版). 北京: 电子工业出版社, 2004
[5] Blaum Mario. A Cource on Error-Correction Codes. San Jose, CA 95120, USA: IBM Corp, 1997
[6] Wicker S B, Bhargava V K. Reed-Solomon Codes and Their Applicatins. New York: IEEE Press, 1994
[7] 王进祥. RS 码译码器综述. 微电子学, 1997, 27(2): 115-120
[8] 吴暇. RS 码的研究与应用. 西安电子科技大学毕业论文, 2001
[9] R.E. Blahut. A universal Reed-Solomon decoder. IBM J. Res. Develop., 1984, 28(3): 150-158
[10] Liu K Y. Architectures for VLSI design of Reed-Solomon decoders. IEEE Trans. Computers. 1984, 33(2) 81-84
[11] Maki, G K. VLSI Reed-Solomon decoder design. Military Communications Conference. MILCOM: IEEE. 1986: 47-51
[12] Colls K. ASIC synthesis of flexible 80Mbit/s Reed-Solomon codec. EDA&T, Beijing, China, 1994: 142-145
[13] Hanho Lee. An area-efficient Euclidean algorithm block for Reed-Solomon decoder. Computer Society Annual Symposium on VLSI. New York: IEEE, 2003
[14] 刘毓敏. CD、VCD 机伺服技术的发展. 电声技术, 1998, 7: 9-11
[15] 佳一. DVD 视盘系统的记录数据和恢复. 电声技术, 2000, 5: 9-15
[16] DVD Specifications for Read-Only Disc, part1: Physical Specification, Version 1.0, August 1996
[17] Jeng, Jyh-Hong Truong Trieu-Kien. On Decoding of Both Errors and Erasures of a Reed-Solomon Code Using an Inverse-Free Berlekamp-Massey Algorithm. IEEE Trans. Communications, 1999, 47(10). 1488-1494
[18] Sarwate Dilip V., Shanbhag Naresh R.. High-Speed Architectures for Reed-Solomon Decoders. IEEE Trans. On VLSI Systems. 2001, Oct., 9(5). 641-655
[19] Shao Howard M., Reed Irving S.. On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays. IEEE Trans. Computers. 1988, Oct, 37(9). 1273–1280
[20] Choomchuay S.. Time domain algorithms and architectures for Reed-Solomon decoding. IEEE Proceedings- I, 1993, 140(3). 189-196
[21] Burton H. Inversionless decoding of binary BCH code. IEEE Trans. Inform. Theory. July 1971. vol. IT-17. pp464-466
[22] Truong Trieu-Kien, Jeng J. H., Hung King-Chu. Inversionless decoding of both errors and erasures of Reed-Solomon code. IEEE Trans. Commun., Aug. 1998.vol. 46, NO. 8, pp.973–976
[23] Zhang Tong, Parhi Keshab K., On the High Speed VLSI Implementation of Errors and Erasures Correcting Reed Solomon Decoders. the 12th Great Lakes Symposium on VLSI, 2002.
[24] Reed I., Shih M., Truong T. VLSI design of inverse-free Berlekamp–Massey algorithm. IEEE Proceedings-E, 1991, 138(5). 295-298
[25] Lee Hanho, Yu Meng-Lin, Song Leilei. VLSI Design of Reed-Solomon Decoder Architectures. in Proc. of IEEE International Symposium on Circuit and Systems, Geneva, Switzerland. 2000:705-708
[26] 刘大海,孙辉先. RS(255,223)编码器的实现. 宇航学报,2000, 21(7): 118-126
[27] 朱海坤, 沈泊, 章倩苓. 一种改进控制逻辑的面积优化高速RS译码器. 微电子学, 2002, 32(1):41-45
[28] Y. S. Kavian, A. Falahati, A. Khayatzadeh, M. Naderi. High Speed Reed-Solomon Decoder with Pipeline Architecture. IEEE ISCAS, 2005, 9(5): 132-136
[29] M.H.Lee, et al. A high speed Reed-Solomon decoder. IEEE Trans. Consumer Electron, 1995, 41(4): 1142-1149.
[30] Y.R. Shayan, et al. A cellular structure for a versatile Reed-Solomon decoder. IEEE Trans. Computer, 1997, 46(1): 80-85.
[31] R.E. Blahut. A universal Reed-Solomon decoder. IBM J. Res. Develop., 1984, 28(3): 150-158.
[32] Y. S. Kavian, A. Falahati, A. Khayatzadeh, M. Naderi. High Speed Reed-Solomon Decoder with Pipeline Architecture. IEEE ISCAS, 2005, 9(5): 132-136.
[33] Jae H. Baek, Jin Y. Kang, and Myung H. Sunwoo. Design of A High-Speed Reed-Solomon Decoder. Proc. IEEE Int. Symp. Circuits Syst. (ISCAS’2002), 2002, 34(18): 793-796.
[34] Christof Paar. A New Architecture for a Parallel Finite field Multiplier with LowComplexity Based on Composite Field. IEEE Tran. On Computer, 1996, 45(7): 856-861.
[35] J. H. Jeng, J. M. Kuo and T. K. Truong. A high efficient multiplier for RS decoder. International Symposium on 1999 VLSI Technology, Systems and Applications, Taiwan, 1999: 116-118.
[36] H. Lee. High-speed VLSI architecture for Reed-Solomon decoder. IEEE Trans. Very Large Scale(VLSI)Integer. Syst., 2003, 11(2): 288-294.
[37] T. K. Truong. An area-efficient Euclidean architecture for parallel Reed-Solomon decoder. IEEE Computer Society Annu. Symp. VLSI, 2003: 209-210.
[38] D. V. Sarwate and N. R. Shanbhag. High-speed architecture for Reed-Solomon decoder. IEEE Trans. Very Large Scale (VLSI) Integr. Syst., 2003, 17(3): 288-294.
[39] L. Song, M.-L. Yu, and M. S. Shaffer. 10 and 40-Gb/s Forward error correction devices for optical communications. IEEE J, Solid-State Circuits, 2002, 37(11): 1565-1573
[40] A. G. M. Strollo, N. Petra, D. De Caro, E. Napoli. An Area-Efficient High-Speed Reed-Solomon Decoder in 0.25μm CMOS. IEEE Trans. On circuit and systems, 2004,36(8): 479-482
[41] 吴飞, 王小力. 一种改进的高速Reed-Solomon译码算法及其FPGA实现. 西安电子科技大学学报(自然科学版). 2006, 33(6): 995-999
[42] 孙富明, 李笑盈. 基于多种EDA工具的FPGA设计. 电子技术应用, 2002,1:54-76