【作者】 沈晓强；

【导师】 郭阳；

【作者基本信息】 国防科学技术大学 ， 软件工程， 2006， 硕士

【摘要】 有限域上的算术运算是许多差错控制/密码应用系统中的基本运算和重要模块,具有强大纠错能力的Reed-Solomon码就是依赖于有限域上的运算来完成编解码功能的。在有限域运算中,加法非常简单,而有限域乘法、求逆/除法等运算则很复杂且需要很长的计算时间,它们的计算效率在很大程度上决定了整个系统的性能。随着应用系统中数据传输速率的不断增长,要求RS编解码器应有很高的吞吐率和纠错能力,使得有不同RS码型的通用RS编解码器在当前和将来的应用中都变得日益重要,因此研究通用的有限域运算特别是其中的可编程乘法模块的设计具有重要的理论意义和应用价值。本文主要目的就是面向RS编解码等差错控制应用的GF(2~m)上有限域乘法、求逆/除法运算的研究设计与VLSI实现。本文在研究传统有限域乘法算法和结构的基础上,设计实现了高性能的并行有限域乘法器和除法器,主要工作如下:1详细分析了传统的有限域乘法算法和结构;2针对编解码中大量使用的常数乘法器,专门设计了基于贪婪算法的优化的常数乘法器,显著减少了电路规模,同时设计了适于做平方运算的专用的正规基乘法器;3为使有限域乘法器应用到通用的RS编解码器中,设计实现了对本原多项式可编程的脉动和半脉动阵列乘法器,提出了一种对多项式相乘后做取模化简运算的电路实现结构,在此基础上设计实现了全并行的阵列乘法器,该乘法器在速度和面积等指标上有很好的性能;4设计了低实现复杂度的有限域上的求逆器和除法器;5采用基于标准单元的设计方法对本文设计的有限域运算器进行了逻辑综合和布局布线,并对设计进行了模拟验证和形式验证。更多还原

【Abstract】 Arithmetic operations in finite field are the fundamental operations and building blocks of many error-control codes and cryptography systems.Sophisticated Reed-Solomon code relies on finite field arithmetic to perform encoding and decoding. In finite field arithmetic,addition is trivial,however,multiplication,inversion and division requires a significant amount of computation.While increasing data rates in many applications demand higher throughput from RS codec’s,universal RS codec’s that work for different RS codes are becoming increasingly important for present and future applications.Therefore,the universal architectures and implementations for finite field arithmetic,especially the universal finite field multiplication is becoming valuable both in theory and applications.This thesis focuses on the design and VLSI realization of finite field multiplication and inversion/division over GF(2~m)for Reed-Solomon codec applications.We design and realize high performance parallel finite field multiplier and divider based on the analyzing of the traditional multiplication algorithms and architectures,the main works are as follows:1.Classical and traditional finite field multiplication algorithms and architectures are analyzed.2.Due to the large amount of multiplications by a constant in RS codec,we design numbers of optimized constant multipliers based greedy algorithm,thus the implementation scale is reduced substantially.Then we design dedicated normal basis multiplier which is suitable for square operation.3.In order to satisfy the requirements of universal RS codec,we design systolic and semi-systolic parallel finite field multiplier,which are programmable with respect to primitive/irreducible polynomial.We proposed a new architecture to perform modular reduction operation which was done after ordinary polynomial multiplication.A full-parallel multiplier example is also given, results shows that it outperforms its systolic type counterparts.4.Design a low-complexity finite field inverter and divider which have low latency.5.Standard cell based semi-custom design flow and methodology was adopted in this thesis.Logic synthesis tool was used to synthesize&optimize the design and layout tool was used to do P&R at SMIC’s 0.18μm CMOS process. Simulation and formal verification were also done to verify the design.更多还原