Low latency systolic multipliers for finite field GF (2^m) based on irreducible polynomials

Abstract

Systolic implementation of multiplication over GF(2^m) is usually very efficient in area-time complexity, but its latency is usually very large. Thus, two low latency systolic multipliers over GF(2^m) based on general irreducible polynomials and irreducible pentanomials are presented. First, a signal flow graph (SFG) is used to represent the algorithm for multiplication over GF(2^m). Then, the two low latency systolic structures for multiplications over GF(2^m) based on general irreducible polynomials and pentanomials are presented from the SFG by suitable cut-set retiming, respectively. Analysis indicates that the proposed two low latency designs involve at least one-third less area-delay product when compared with the existing designs. To the authors’ knowledge, the time-complexity of the structures is the lowest found in literature for systolic GF(2^m) multipliers based on general irreducible polynomials and pentanomials. The proposed low latency designs are regular and modular, and therefore they are suitable for many time critical applications.

Keywords

finite field / finite field multiplication / systolic structure / low latency / polynomials

References

[1] DeschampsJ. P., ImanaJ. L., SutterG. D.Hardware implementation of finite field arithmetic [M], 2009New YorkMcGraw-Hill45-49

[2] BlakeI., SeroussiG., SmartN. P.. Elliptic curves in cryptography, ser [M]. London Mathematical Society Lecture Note Series, 1999Cambridge, UKCambridge Univ Press75-78

[3] ChenS. H., YanH. Z., MingX. Z.. Analysis and modeling of error of spiral bevel gear grinder based on multi-body system theory [J]. Journal of Central South University of Technology, 2008, 15(5): 706-711

[4] JiangA. H., MeiC. E. J. Q.. Nonlinear combined forecasting model based on fuzzy adaptive variable weight and its application [J]. Journal of Central South University of Technology, 2010, 17(4): 863-867

[5] LeeS. H., WangY. Q., SongJ. I.. Fourier and wavelet transformations application to fault diction of induction motor with stator current [J]. Journal of Central South University of Technology, 2010, 17(1): 93-101

[6] WuJ. S., ShuH. Z., WangL., SenhadjiL.. Fast algorithms for the computation of sliding sequency-ordered complex hadamard transform [J]. IEEE Trans Signal Process, 2010, 58(11): 5901-5909

[7] YehC. S., ReedI. S., TruongT. K.. Systolic multipliers for finite fields GF(2^m) [J]. IEEE Trans. Computers, 1984, 33(4): 357-360

[8] WangC. L., LinJ. L.. Systolic array implementation of multipliers for finite fields GF(2^m) [J]. IEEE Trans Circuits Syst, 1991, 38(7): 796-800

[9] SunarB., KocC. K.. Mastrovito multiplier for all trinomials[J]. IEEE Trans Comput, 1999, 48(5): 522-527

[10] SongL., ParhiK. K., KurodaI., NishitaniT.. Hardware/software code sign of finite field data path for low-energy Reed-Solomn codes [J]. IEEE Trans Very Large Scale Integr (VLSI) Syst, 2000, 8(2): 160-172

[11] LeeC. Y., LuE. H., LeeJ. Y.. Bit-parallel systolic multipliers for GF(2^m) fields defined by all-one and equally spaced polynomials [J]. IEEE Trans Comput, 2001, 50(6): 385-393

[12] LeeC. Y.. Low complexity bit-parallel systolic multiplier over GF(2^m) using irreducible trinomials [J]. IEE Proc Comput Digit Tech, 2003, 150(1): 39-42

[13] LeeC. Y., ChiouC. W., LinJ. M., ChangC. C.. Scalable and systolic Montgomery multiplier over GF(2^m) generated by trinomials [J]. IET Circuits Devices Syst, 2007, 1(6): 477-484

[14] LeeC. Y., HorngJ. S., JouI. C., LuE. H.. Low-complexity bit-parallel systolic Montgomery multipliers for special classes of GF(2^m) [J]. IEEE Trans Comput, 2005, 54(9): 1061-1070

[15] JainS. K., SongL., ParhiK. K.. Efficient semisystolic architectures for finite field arithmetic [J]. IEEE Trans Very Large Scale Integr (VLSI) Syst, 1998, 6(1): 734-749

[16] SarmadiS. B., Hasan AnwarM.. Concurrent error detection in finite-field arithmetic operations using pipelined and systolic architectures [J]. IEEE Trans Comput, 2009, 58(11): 1553-1567

[17] MeherP. K.. Systolic and non-systolic scalable modular designs of finite field multipliers for Reed-Solomon codes [J]. IEEE Trans Very Large Scale Integr (VLSI) Syst, 2009, 17(6): 747-757

[18] MaoZ., ShouG., HuY., GuoZ.. Design of multipliers for GF(2^m) [J]. Electron Lett, 2010, 46(6): 419-420

[19] FanH. N., HasanM. A.. Alternative to the Karatsuba algorithm for software implementations of GF(2ⁿ) multiplications [J]. IET Information Security, 2009, 3(2): 60-65

[20] ParhiK. K.VLSI digital signal processing systems: Design and implementation [M], 1999New YorkWiley189-223