The Study And Realization Of Finite Field Multiplication And Division

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.