有限域乘除法研究与实现
|
摘要
有限域上的算术运算是许多差错控制/密码应用系统中的基本运算和重要模块,具有强大纠错能力的Reed-Solomon码就是依赖于有限域上的运算来完成编解码功能的。在有限域运算中,加法非常简单,而有限域乘法、求逆/除法等运算则很复杂且需要很长的计算时间,它们的计算效率在很大程度上决定了整个系统的性能。
随着应用系统中数据传输速率的不断增长,要求RS编解码器应有很高的吞吐率和纠错能力,使得有不同RS码型的通用RS编解码器在当前和将来的应用中都变得日益重要,因此研究通用的有限域运算特别是其中的可编程乘法模块的设计具有重要的理论意义和应用价值。本文主要目的就是面向RS编解码等差错控制应用的GF(2~m)上有限域乘法、求逆/除法运算的研究设计与VLSI实现。
本文在研究传统有限域乘法算法和结构的基础上,设计实现了高性能的并行有限域乘法器和除法器,主要工作如下:
1详细分析了传统的有限域乘法算法和结构;
2针对编解码中大量使用的常数乘法器,专门设计了基于贪婪算法的优化的常数乘法器,显著减少了电路规模,同时设计了适于做平方运算的专用的正规基乘法器;
3为使有限域乘法器应用到通用的RS编解码器中,设计实现了对本原多项式可编程的脉动和半脉动阵列乘法器,提出了一种对多项式相乘后做取模化简运算的电路实现结构,在此基础上设计实现了全并行的阵列乘法器,该乘法器在速度和面积等指标上有很好的性能;
4设计了低实现复杂度的有限域上的求逆器和除法器;
5采用基于标准单元的设计方法对本文设计的有限域运算器进行了逻辑综合和布局布线,并对设计进行了模拟验证和形式验证。
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.
随着应用系统中数据传输速率的不断增长,要求RS编解码器应有很高的吞吐率和纠错能力,使得有不同RS码型的通用RS编解码器在当前和将来的应用中都变得日益重要,因此研究通用的有限域运算特别是其中的可编程乘法模块的设计具有重要的理论意义和应用价值。本文主要目的就是面向RS编解码等差错控制应用的GF(2~m)上有限域乘法、求逆/除法运算的研究设计与VLSI实现。
本文在研究传统有限域乘法算法和结构的基础上,设计实现了高性能的并行有限域乘法器和除法器,主要工作如下:
1详细分析了传统的有限域乘法算法和结构;
2针对编解码中大量使用的常数乘法器,专门设计了基于贪婪算法的优化的常数乘法器,显著减少了电路规模,同时设计了适于做平方运算的专用的正规基乘法器;
3为使有限域乘法器应用到通用的RS编解码器中,设计实现了对本原多项式可编程的脉动和半脉动阵列乘法器,提出了一种对多项式相乘后做取模化简运算的电路实现结构,在此基础上设计实现了全并行的阵列乘法器,该乘法器在速度和面积等指标上有很好的性能;
4设计了低实现复杂度的有限域上的求逆器和除法器;
5采用基于标准单元的设计方法对本文设计的有限域运算器进行了逻辑综合和布局布线,并对设计进行了模拟验证和形式验证。
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.
引文
[1]Wenbo Mao著,王继林等译,现代密码学:理论与实践 电子工业出版2004.
[2]王新梅,肖国镇.纠错码-原理与方法.西安电子科技大学出版社,2001.
[3]S.Lin and D.J.Costello,Error Control Coding:Fundamentals and Applications,Prentice Hall,1983.
[4]Peter Sweeney,Error Control Coding:From Theory to Practice.John Wiley & Sons,2002.
[5]Stephen B.Wicker,Error Control Systems for Digital Communication and Storage,Prentice-Hall,1995.
[6]Texas Instruments,TMS320C64x Technical Overview.
[7]Texas Instruments.Reed Solomon Decoder:TMS320C64x Implementation.2000.12.
[8]S.T.J.Fenn,M.Benaissa,D.Taylor,"GF(2~m)Multiplication and division over the dual field",IEEE Transaction on computers,Vol.45,No.3,pp.319-327,1996.
[9]I.S.Hsu,T.K.Truong,L.J.Deutsch,I.S.Reed,"A comparison of VLSI architectures of finite field multipliers using dual,normal or standard basis",IEEE Transactions on Computers,Vol.37,pp.738-739,June 1988.
[10]T.K.Truong and L.J Deutsch,I.S.Reed,I.S.Hsu,K.Wang and C-S Yeh,"The VLSI Design of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithrn",TDA Progress Report 42-70,May and June 1982.
[11]C.L.Wang,J.L.Lin,"Systolic array implementation of multipliers for finite field GF(2~m)",IEEE Trans on Circuits and Systems,Vol.38.No.7.pp.796-800,Jul.1991.
[12]Surendra K.Jain,Leilei Song,Keshab K.Parhi."Efficient semisystolic architectures for finite-field arithmetic",IEEE Transactions on VLSI Systems,Vol6,Nol,pp.101-113,1998.
[13]Leilei song.Keshab K.Parhi,Ichiro Kuroda,Takao Nishitani."Hardware/software codesign of finite field datapath for low-energy Reed-Solomon codecs".IEEE Transactions on VLSI Systems,Vol8,No2,pp.160-172.2000.
[14]E.D.Mastrovito,VLSI,Architectures for Computation in Galois Fields,PhD thesis.Linkoping Univ.,Linkoping,Sweden,1991.
[15]D.V.Sarwate and N.R.Shanbhag."Very high speed Reed-Solomon decoders," IEEE international Symposium on Information Theory.JunE.2000.
[16]M.A.Hasan.V.K.Bhargava,".Architecture for a low complexity rate-adapative Reed-Solomon encoder",IEEE Trans.On Computers Vol.44.pp938-942,July 1995.
[17]Wolfgang Wilhelm,"A New Scalable VLSI Architecture for Reed Solomon Decoders" IEEE Journal of Solid-State Circuits.Vol.34.pp.388-396.Mar.1999.
[18]H.Shao,I S Reed,"On the VLSI design of a Pipeline Reed-Solomon Decoder using systolic arrays",IEEE transactions on computers,Vol 37,pp1273-1280,1988.
[19]K.Y.Liu,"Architecture for VLSI design of Reed-Solomon decoders" IEEE Transactions on Computers,Vol33,pp178-189,Feb.1984.
[20]E.R.Berlekamp,"Bit-serial Reed-SoIomon encoders",IEEE Trans.Information Theory,vol.28.pp.120-126,Nov.1982.
[21]Hanho Lee,"High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder",IEEE Transactions on VLSI Systems,Vol.11,No.2,pp288-294,2003.
[22]游余新,王进祥、高速流水(204,188)译码器的VLSI设计与实现,2004中国通信集成电路技术与应用研讨会论文集,杭州,2004
[23]C.C.Wang,Y.K.Truong,H.M.Shao,L.J.Deutsch,J.K.Omura,I.S.Reed,"VLSI architecture for computing multiplications and inverses in GF(2m)",IEEE Transactions on Computers,vol.34,no.6,pp.709-716,Aug,1985.
[24]Tong zhang,Keshab K.Parhi,"Systematic Design of Original and Modified Mastrovito Multipliers for General Irreducible Polynomials",IEEE Transactions on Computers,Vol.50,no.7,pp.734-749,July 2001.
[25]C.K.Koc,B.sunnar,"Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields",IEEE Transactions on Computers,47(3):353-356,March 1998.
[26]Christof Paar,"a new architecture for parallel finite field multiplier with low complexity based on composite fields",IEEE Transactions on Computers,Vol.45,No.7,pp 856-861,1996.
[27]Lijun Gao and Keshab K.Parhi."'Custom VLSI Design of Efficient Low Latency and Low Power Finite Field Multiplier for Reed-Solomon Codec".IEEE,2001,9(3)pp.574-577.2001.
[28]李玉山,来新泉,电子系统集或设计技术 电子工业出版社2002.
[29]S.Y.Kung,VLSI Array Processors.Englewood Cliffs.Prentice Hall,1988.
[30]K.K Parhi著.陈弘毅等译,VLSI数字信号处理系统设计与实现 机械工业出版社 2004.
[31]李芳慧.王飞.何佩琨.TMS320C6000系列DSPs原理与应用,电子工业出版社2003.
[32]沈晓强.Yuan Jiang.郭阳.一种通用的有限域乘法器的设计与实现.中国集成电路2005.8
[33]王进祥,毛志刚.叶以正 “GF(2~8)上快速乘法器及求逆器的设计”微电子学第28卷第5期 1998.10
[34]陈桂明,应用MATLAB语言处理数字信号与数字图像.科学出版社2000.
[35]Himanshu Bhatnagar,Advanced ASIC Chip Synthesis Using Synopsys Design Compiler Physical Compiler and Primetime,Kluwer Academic Publishers,2002
[36]Shivakumar Chornnad Needamangalam Balachander,Verilog:Frequently Asked Questions:Language,Applications and Extensions,Springer 2004.
[37]James M.Lee,VERILOG QUICKSTART:A Practical Guide to Simulation and Synthesis in Verilog,Third Edition,Kluwer Academic Publishers,2002
[38]William K.Lam,Hardware Design Verification Simulation and Formal Method Based Approaches,Prentice Hall Publisher,2005.
[39]Shuvra S.Bhattacharyya,ED F.Deprettere,Jurgen Teich,Domain-Specific Processors Systems,Architectures,Modeling,and Simulation,Marcel Dekker,2004
[40]Keshab K.Parhi and Taka Nishitani,Digital Signal Processing for Multimedia Systems,Marcel Dekker 1999.
[41]Wai-Kai Chen,The VLSI handbook,CRC Press 2000.
[42]Jan M,Rabaey,Massoud Pedram,Low Power Design Methodologies,Kluwer Academic,1996.
[43]N.rakagi,J.Yoshiki,and K.Yakagi,"A fast algorithm for multiplicative inversion in GF(2~m)using normal basis",IEEE Trans.Comput.,vol.50,pp.394-398,May 2001.
[44]J.H.Guo and C.L.Wang,"New systolic arrays for C+AB~2,inversion,and division in GF(2~m)," IEEE Trans.Comput.,vol.49,pp.1120-1125,Oct.2000.
[45]C.L.Wang and J.L.Lin,"A systolic architecture for computing inverses and divisions in finite fields GF(2~m)," IEEE Trans.Comput.,vol.42,pp.1141-1146,Sept.1993.
[46]H.Brunner,A.Curiger,and M.Hofstetter,"On computing multiplicative inverses in GF(2~m),IEEE Trans.Comput.,vol.42,pp.1010-1015,Aug.1993.
[47]J.H Guo and C.L Wang,"Systolic array implementation of Euclid's algorithm for inversion and division in GF(2~m)",IEEE Transactions on Computers,Vol.47,No.10,pp 1161-1167,1998.
[48]N.Takagi,"A VLSI algorithm for modular division based on the binary GCD algorithm," IEICE Trans.Fundamentals,vol.E81-A,pp.724-728,May 1998.
[49]Y.Watanabe,N.Takagi,and K.Takagi,"A VLSI algorithm for division in GF(2~m)based on extended binary GCD algorithm," IEICE Trans.Fundamentals,vol.E85-A,pp.994-999,May 2002.
[50]J.Goodman and A.P.Chandrakasan."An energy-efficient reconfigurable public-key cryptography processor," IEEE J.Solid-State Circuits,vol.36,pp.1808-1820.Nov.2001.
[51]牛风举.刘元成,朱明程.基于IP复用的数字IC设计技术,电子工业出版社2003.
[2]王新梅,肖国镇.纠错码-原理与方法.西安电子科技大学出版社,2001.
[3]S.Lin and D.J.Costello,Error Control Coding:Fundamentals and Applications,Prentice Hall,1983.
[4]Peter Sweeney,Error Control Coding:From Theory to Practice.John Wiley & Sons,2002.
[5]Stephen B.Wicker,Error Control Systems for Digital Communication and Storage,Prentice-Hall,1995.
[6]Texas Instruments,TMS320C64x Technical Overview.
[7]Texas Instruments.Reed Solomon Decoder:TMS320C64x Implementation.2000.12.
[8]S.T.J.Fenn,M.Benaissa,D.Taylor,"GF(2~m)Multiplication and division over the dual field",IEEE Transaction on computers,Vol.45,No.3,pp.319-327,1996.
[9]I.S.Hsu,T.K.Truong,L.J.Deutsch,I.S.Reed,"A comparison of VLSI architectures of finite field multipliers using dual,normal or standard basis",IEEE Transactions on Computers,Vol.37,pp.738-739,June 1988.
[10]T.K.Truong and L.J Deutsch,I.S.Reed,I.S.Hsu,K.Wang and C-S Yeh,"The VLSI Design of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithrn",TDA Progress Report 42-70,May and June 1982.
[11]C.L.Wang,J.L.Lin,"Systolic array implementation of multipliers for finite field GF(2~m)",IEEE Trans on Circuits and Systems,Vol.38.No.7.pp.796-800,Jul.1991.
[12]Surendra K.Jain,Leilei Song,Keshab K.Parhi."Efficient semisystolic architectures for finite-field arithmetic",IEEE Transactions on VLSI Systems,Vol6,Nol,pp.101-113,1998.
[13]Leilei song.Keshab K.Parhi,Ichiro Kuroda,Takao Nishitani."Hardware/software codesign of finite field datapath for low-energy Reed-Solomon codecs".IEEE Transactions on VLSI Systems,Vol8,No2,pp.160-172.2000.
[14]E.D.Mastrovito,VLSI,Architectures for Computation in Galois Fields,PhD thesis.Linkoping Univ.,Linkoping,Sweden,1991.
[15]D.V.Sarwate and N.R.Shanbhag."Very high speed Reed-Solomon decoders," IEEE international Symposium on Information Theory.JunE.2000.
[16]M.A.Hasan.V.K.Bhargava,".Architecture for a low complexity rate-adapative Reed-Solomon encoder",IEEE Trans.On Computers Vol.44.pp938-942,July 1995.
[17]Wolfgang Wilhelm,"A New Scalable VLSI Architecture for Reed Solomon Decoders" IEEE Journal of Solid-State Circuits.Vol.34.pp.388-396.Mar.1999.
[18]H.Shao,I S Reed,"On the VLSI design of a Pipeline Reed-Solomon Decoder using systolic arrays",IEEE transactions on computers,Vol 37,pp1273-1280,1988.
[19]K.Y.Liu,"Architecture for VLSI design of Reed-Solomon decoders" IEEE Transactions on Computers,Vol33,pp178-189,Feb.1984.
[20]E.R.Berlekamp,"Bit-serial Reed-SoIomon encoders",IEEE Trans.Information Theory,vol.28.pp.120-126,Nov.1982.
[21]Hanho Lee,"High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder",IEEE Transactions on VLSI Systems,Vol.11,No.2,pp288-294,2003.
[22]游余新,王进祥、高速流水(204,188)译码器的VLSI设计与实现,2004中国通信集成电路技术与应用研讨会论文集,杭州,2004
[23]C.C.Wang,Y.K.Truong,H.M.Shao,L.J.Deutsch,J.K.Omura,I.S.Reed,"VLSI architecture for computing multiplications and inverses in GF(2m)",IEEE Transactions on Computers,vol.34,no.6,pp.709-716,Aug,1985.
[24]Tong zhang,Keshab K.Parhi,"Systematic Design of Original and Modified Mastrovito Multipliers for General Irreducible Polynomials",IEEE Transactions on Computers,Vol.50,no.7,pp.734-749,July 2001.
[25]C.K.Koc,B.sunnar,"Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields",IEEE Transactions on Computers,47(3):353-356,March 1998.
[26]Christof Paar,"a new architecture for parallel finite field multiplier with low complexity based on composite fields",IEEE Transactions on Computers,Vol.45,No.7,pp 856-861,1996.
[27]Lijun Gao and Keshab K.Parhi."'Custom VLSI Design of Efficient Low Latency and Low Power Finite Field Multiplier for Reed-Solomon Codec".IEEE,2001,9(3)pp.574-577.2001.
[28]李玉山,来新泉,电子系统集或设计技术 电子工业出版社2002.
[29]S.Y.Kung,VLSI Array Processors.Englewood Cliffs.Prentice Hall,1988.
[30]K.K Parhi著.陈弘毅等译,VLSI数字信号处理系统设计与实现 机械工业出版社 2004.
[31]李芳慧.王飞.何佩琨.TMS320C6000系列DSPs原理与应用,电子工业出版社2003.
[32]沈晓强.Yuan Jiang.郭阳.一种通用的有限域乘法器的设计与实现.中国集成电路2005.8
[33]王进祥,毛志刚.叶以正 “GF(2~8)上快速乘法器及求逆器的设计”微电子学第28卷第5期 1998.10
[34]陈桂明,应用MATLAB语言处理数字信号与数字图像.科学出版社2000.
[35]Himanshu Bhatnagar,Advanced ASIC Chip Synthesis Using Synopsys Design Compiler Physical Compiler and Primetime,Kluwer Academic Publishers,2002
[36]Shivakumar Chornnad Needamangalam Balachander,Verilog:Frequently Asked Questions:Language,Applications and Extensions,Springer 2004.
[37]James M.Lee,VERILOG QUICKSTART:A Practical Guide to Simulation and Synthesis in Verilog,Third Edition,Kluwer Academic Publishers,2002
[38]William K.Lam,Hardware Design Verification Simulation and Formal Method Based Approaches,Prentice Hall Publisher,2005.
[39]Shuvra S.Bhattacharyya,ED F.Deprettere,Jurgen Teich,Domain-Specific Processors Systems,Architectures,Modeling,and Simulation,Marcel Dekker,2004
[40]Keshab K.Parhi and Taka Nishitani,Digital Signal Processing for Multimedia Systems,Marcel Dekker 1999.
[41]Wai-Kai Chen,The VLSI handbook,CRC Press 2000.
[42]Jan M,Rabaey,Massoud Pedram,Low Power Design Methodologies,Kluwer Academic,1996.
[43]N.rakagi,J.Yoshiki,and K.Yakagi,"A fast algorithm for multiplicative inversion in GF(2~m)using normal basis",IEEE Trans.Comput.,vol.50,pp.394-398,May 2001.
[44]J.H.Guo and C.L.Wang,"New systolic arrays for C+AB~2,inversion,and division in GF(2~m)," IEEE Trans.Comput.,vol.49,pp.1120-1125,Oct.2000.
[45]C.L.Wang and J.L.Lin,"A systolic architecture for computing inverses and divisions in finite fields GF(2~m)," IEEE Trans.Comput.,vol.42,pp.1141-1146,Sept.1993.
[46]H.Brunner,A.Curiger,and M.Hofstetter,"On computing multiplicative inverses in GF(2~m),IEEE Trans.Comput.,vol.42,pp.1010-1015,Aug.1993.
[47]J.H Guo and C.L Wang,"Systolic array implementation of Euclid's algorithm for inversion and division in GF(2~m)",IEEE Transactions on Computers,Vol.47,No.10,pp 1161-1167,1998.
[48]N.Takagi,"A VLSI algorithm for modular division based on the binary GCD algorithm," IEICE Trans.Fundamentals,vol.E81-A,pp.724-728,May 1998.
[49]Y.Watanabe,N.Takagi,and K.Takagi,"A VLSI algorithm for division in GF(2~m)based on extended binary GCD algorithm," IEICE Trans.Fundamentals,vol.E85-A,pp.994-999,May 2002.
[50]J.Goodman and A.P.Chandrakasan."An energy-efficient reconfigurable public-key cryptography processor," IEEE J.Solid-State Circuits,vol.36,pp.1808-1820.Nov.2001.
[51]牛风举.刘元成,朱明程.基于IP复用的数字IC设计技术,电子工业出版社2003.