Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Systematic Design of Original and Modified Mastrovito Multipliers for General Irreducible Polynomials
Zhang T., Parhi K. IEEE Transactions on Computers50 (7):734-749,2001.Type:Article
Date Reviewed: Jun 13 2002

Finite field multiplication is a key operation in such areas as cryptography and error correction coding by block codes. The operation is far from trivial, since it involves a modulo operation with a primitive polynomial. This paper provides insight into the structure and design of finite field multipliers.

The paper introduces relevant concepts from field theory using vector-matrix notation and corresponding operations. A decomposition theorem and a corresponding algorithm are then presented that permit building a Mastrovito multiplier in the general case. An example is given to show how to perform every step in the algorithm. This could for example be used to build constant multiplier Galois field multipliers. Such multipliers are of great value in particular applications of Reed-Solomon codecs, such as xDSL.

Next it is shown that an efficient multiplier architecture can be obtained even for high Hamming weight irreducible polynomials, a valuable development, since it is traditionally known that complexity grows with such polynomials. The last section is concerned with building efficient multipliers for some special irreducible polynomials: specific types of trinomials and pentanomials, as well as the so-called equally-spaced polynomials. Proofs of the decomposition theorem that permits the building of modular general purpose Mastrovito multipliers is given in the appendix. In a subsequent appendix the theorem for building the matrix needed to compute the Galois field multiplication in the case of high Hamming weight irreducible polynomials is proved. This is one of the few papers available that, besides its theoretical value, also has a direct implementational value.

Reviewer:  Vladimir Botchev Review #: CR126166 (0207-0372)
Bookmark and Share
 
Arithmetic And Logic Units (B.5.1 ... )
 
 
Computer Arithmetic (G.1.0 ... )
 
 
VLSI (Very Large Scale Integration) (B.7.1 ... )
 
 
General (G.1.0 )
 
 
Numerical Linear Algebra (G.1.3 )
 
 
Types And Design Styles (B.7.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Arithmetic And Logic Units": Date
Square-rooting algorithms for high-speed digital circuits
Majerski S. IEEE Transactions on Computers 34(9): 724-733, 1985. Type: Article
Aug 1 1986
Synthesis of integer multipliers in sum of pseudoproducts form
Ciriani V., Luccio F., Pagli L. Integration, the VLSI Journal 36(3): 103-119, 2003. Type: Article
Mar 9 2004
A General Proof for Overlapped Multiple-Bit Scanning Multiplications
Vassiliadis S., Schwarz E., Hanrahan D. IEEE Transactions on Computers 38(2): 172-183, 1989. Type: Article
Jun 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy