loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
GF(2m) Multiplication and Division Over the Dual Basis
March 1996 (vol. 45 no. 3)
pp. 319-327
ASCII Text
x 
 
Sebastian T.J. Fenn, Mohammed Benaissa, David Taylor, "GF(2m) Multiplication and Division Over the Dual Basis," IEEE Transactions on Computers, vol. 45, no. 3, pp. 319-327, March, 1996.
 
 
BibTex
x
 
@article{ 10.1109/12.485570,
author = {Sebastian T.J. Fenn and Mohammed Benaissa and David Taylor},
title = {GF(2m) Multiplication and Division Over the Dual Basis},
journal ={IEEE Transactions on Computers},
volume = {45},
number = {3},
issn = {0018-9340},
year = {1996},
pages = {319-327},
doi = {http://doi.ieeecomputersociety.org/10.1109/12.485570},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - GF(2m) Multiplication and Division Over the Dual Basis
IS - 3
SN - 0018-9340
SP319
EP327
EPD - 319-327
A1 - Sebastian T.J. Fenn,
A1 - Mohammed Benaissa,
A1 - David Taylor,
PY - 1996
KW - Dual basis
KW - finite field division
KW - finite field multiplication
KW - irreducible polynomials
KW - Reed-Solomon codecs
KW - systolic arrays
KW - VLSI.
VL - 45
JA - IEEE Transactions on Computers
ER -
 

Abstract—In this paper an algorithm for GF(2m) multiplication/division is presented and a new, more generalized definition of duality is proposed. From these the bit-serial Berlekamp multiplier is derived and shown to be a specific case of a more general class of multipliers. Furthermore, it is shown that hardware efficient, bit-parallel dual basis multipliers can also be designed. These multipliers have a regular structure, are easily extended to different GF(2m) and hence suitable for VLSI implementations. As in the bit-serial case these bit-parallel multipliers can also be hardwired to carry out constant multiplication. These constant multipliers have reduced hardware requirements and are also simple to design. In addition, the multiplication/division algorithm also allows a bit-serial systolic finite field divider to be designed. This divider is modular, independent of the defining irreducible polynomial for the field, easily expanded to different GF(2m) and its longest delay path is independent of m.

[1] F.J. MacWilliams and N.J.A. Sloane,The Theory of Error-Correcting Codes.New York: North-Holland, 1977.[2] R.L. Rivest,A. Shamir, and L.A. Adleman,"A Method for Obtaining Digital Signatures and Public Key Cryptosystems," Comm. ACM, vol. 21, pp. 120-126, 1978.[3] E.R. Berlekamp,"Bit-Serial Reed-Solomon Encoders," IEEE Trans. Information Theory, vol. 28, pp. 869-874, Nov. 1982.[4] M.A. Hasan and V.K. Bhargava,"Division and Bit-Serial Multiplication overGF(qm)," IEE Proc. E., vol. 139, pp. 230-236, May 1992.[5] M.A. Hasan and V.K. Bhargava,"Bit-Serial Systolic Divider and Multiplier for Finite FieldsGF(2m)," IEEE Trans. Computers, vol. 41, no. 8, pp. 972-980, Aug. 1992.[6] E.D. Mastrovito,"VLSI Design for Multiplication over Finite Fields," LNCS-357, Proc. AAECC-6, pp. 297-309,Rome, July 1988, Springer-Verlag. [7] E.D. Mastrovito,"VLSI Architectures for Computations in Galois Fields," PhD thesis, Linkoping Univ., Linkoping, Sweden, 1991.[8] I.S. Hsu,T.K. Truong,L.J. Deutsch, and I.S. Reed,"A Comparison of VLSI Architectures of Finite Field Multipliers Using Dual, Normal or Standard Bases," IEEE Trans. Computers, vol. 37, no. 6, pp. 735-737, June 1988.[9] J.L. Massey and J.K. Omura,"Computational Method and Apparatus for Finite Field Arithmetic," U.S. Patent Application, Submitted 1981.[10] M. Morii,M. Kasahara, and D.L. Whiting,"Efficient Bit-Serial Multiplication and the Discrete-Time Wiener-Hopft Equation over Finite Fields," IEEE Trans. Information Theory, vol. 35, pp. 1,177-1,183, Nov. 1989.[11] P.A. Scott,S.E. Tavares, and L.E. Peppard,"A Fast VLSI Multiplier forGF(2m)," IEEE J. Selected Areas of Comm., vol. 4, pp. 62-66, Jan. 1986.[12] M. Wang and I.F. Blake,"Bit-Serial Multiplication in Finite Fields," SIAM J. Discrete Maths., vol. 3, pp. 140-148, Feb. 1990.[13] R.C. Mullin,I.M. Onyszchuk,S.A. Vanstone, and R.M. Wilson,"Optimal Normal Bases inGF(pn)," Discrete Applied Maths., pp. 142-169, 1988/89.[14] M. Kovac,N. Ranganathan, and M. Varanasi,"SIGMA: A VLSI Systolic Array Implementation of a Galois FieldGF(2m) Based Multiplication and Division Algorithm," IEEE Trans. VLSI Systems, vol. 1, pp. 22-30, Mar. 1993.[15] I.S. Hsu,I.S. Reed,T.K. Truong,K. Wang,C.S. Yeh, and L.J. Deutsch,"The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm," IEEE Trans. Computers, vol. 33, no. 10, pp. 906-911, Oct. 1984.[16] R.E. Blahut,Theory and Practice of Error Control Codes.Reading, Mass.: Addison-Wesley, 1983.[17] E.R. Berlekamp,Algebraic Coding Theory.New York: McGraw-Hill, 1968.[18] K. Araki,I. Fujita, and M. Morisue,"Fast Inverter over Finite Field Based on Euclid's Algorithm," Trans. IEICE E-72, pp. 1,230-1,234, 1989.[19] G-L. Feng,"A VLSI Architecture for Fast Iinversion inGF(2m)," IEEE Trans. Computers, vol. 38, no. 10, pp. 1,383-1,386, Oct. 1989.[20] C.C. Wang,T.K. Truong,H.M. Shao,L.J. Deutsch,J.K. Omura, and I.S. Reed,"VLSI Architectures for Computing Multiplications and Inverses inGF(2m)," IEEE Trans. Computers, vol. 34, no. 8, pp. 709-716, Aug. 1985.[21] R. Lidl and H. Niederreiter,An Introduction to Finite Fields and Their Applications.Cambridge: Cambridge Univ. Press, 1986.[22] S.T.J. Fenn,"Optimised Algorithms and Circuit Architectures for Performing Finite Field Arithmetic in Reed-Solomon Codecs," PhD thesis, Univ. of Huddersfield, 1993.[23] S.T.J. Fenn,M. Benaissa, and D. Taylor,"Division inGF(2m)," Electonic Letters, vol. 28, pp. 2,259-2,261, Nov.19, 1992.[24] G.K. Maki and P.A. Owlsey,"Parallel Berlekamp vs. Conventional VLSI Architecture," Gov. Microcircuit Applics. Conf. Rec., pp. 5-7, Nov. 1986.[25] B. Hochet,P. Quinton, and Y. Robert,"Systolic Gaussian Elimination overGF(p) with Partial Pivoting," IEEE Trans. Computers, vol. 38, no. 9, pp. 1,321-1,324, Sept. 1989.[26] S.T.J. Fenn,M. Benaissa, and D. Taylor,"Improved Algorithm for Division overGF(2m)," Electronic Letters, vol. 29, pp. 469-470, Mar.4, 1993.

Index Terms:
Dual basis, finite field division, finite field multiplication, irreducible polynomials, Reed-Solomon codecs, systolic arrays, VLSI.
Citation:
Sebastian T.J. Fenn, Mohammed Benaissa, David Taylor, "GF(2m) Multiplication and Division Over the Dual Basis," IEEE Transactions on Computers, vol. 45, no. 3, pp. 319-327, Mar. 1996, doi:10.1109/12.485570
Usage of this product signifies your acceptance of the Terms of Use.