Finite Field Polynomial Multiplier with Linear Feedback Shift Register

Che-Wun Chiou This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Chiou-Yng Lee² and Jim-Min Lin³ 

¹Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan 320, R.O.C.
²Department of Computer Information and Network Engineering, Lung Hwa University of Science & Technology, Taoyuan, Taiwan 333, R.O.C.
³Department of Information Engineering and Computer Science, Feng Chia University, Taichung, Taiwan 407, R.O.C.

REFERENCES

1. [1] MacWilliams, F. J. and Sloane, N. J. A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland (1977).
2. [2] Lidl, R. and Niederreiter, H., Introduction to Finite Fields and Their Applications, New York: Cambridge Univ. Press, U.S.A. (1994).
3. [3] Blahut, R. E., Fast Algorithms for Digital Signal Processing, Reading, Mass.: Addison-Wesley (1985).
4. [4] Reed, I. S. and Truong, T. K., “The Use of Finite Fields to Compute Convolutions,” IEEE Trans. Information Theory, Vol. IT-21, pp. 208
   213 (1975).
5. [5] Wang, C. C. and Pei, D., “A VLSI Design for Computing Exponentiation in GF(2m) and its Application to Generate Pseudorandom Number Sequences,” IEEE Trans. Computers, Vol. 39, pp. 258
   262 (1990).
6. [6] Omura, J. and Massey, J., “Computational Method and Apparatus for Finite Field Arithmetic,” U.S. Patent Number 4,587,627 (1986).
7. [7] Wang, C. C., Truong, T. K., Shao, H. M., Deutsch, L. J., Omura, J. K. and Reed, I. S., “VLSI Architectures for Computing Multiplications and Inverses in GF(2m),” IEEE Trans. Computers, Vol. C-34, pp. 709
   717 (1985).
8. [8] Reyhani-Masoleh, A. and Hasan, M. A., “A New Construction of Massey-Omura Parallel Multiplier Over GF(2m),” IEEE Trans. Computers, Vol. 51, pp. 511
   520 (2002).
9. [9] Berlekamp, E. R., “Bit-Serial Reed-Solomon Encoder,” IEEE Trans. Inform. Theory, Vol. IT-28, pp. 869
   874 (1982).
10. [10] Wu, H., Hasan, M. A. and Blake, I. F., “New LowComplexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases,” IEEE Trans. Computers, Vol. 47, pp. 1223
    1234 (1998).
11. [11] Wu, H. and Hasan, M. A., “Low Complexity BitParallel Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 883
    887 (1998).
12. [12] Lee, C. Y., Chiou, C. W. and Lin, J. M., “LowComplexity Bit-Parallel Dual Basis Multipliers Using the Modified Booth’s Algorithm,” Computers & Electrical Engineering, Vol. 31, pp. 444
    459 (2005).
13. [13] Lee, C. Y. and Chiou, C. W., “Efficient Design of Low-Complexity Bit-Parallel Systolic Hankel Multipliers to Implement Multiplication in Normal and Dual Bases of GF(2m),” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Science, Vol. E88-A, pp. 3169
    3179 (2005).
14. [14] Bartee, T. C. and Schneider, D. J., “Computation with Finite Fields,” Information and Computing, Vol. 6, pp. 79
    98 (1963).
15. [15] Mastrovito, E. D., “VLSI Architectures for Multiplication Over Finite Field GF(2m),” Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Proc. Sixth Int’l Conf., AAECC-6, T. Mora, ed., Rome, pp. 297
    309 (1988).
16. [16] Mastrovito, E. D., “VLSI Architectures for Computations in Galois Fields,” Ph.D. thesis, Linköping Univ., Dept. of Electrical Eng., Linköping, Sweden (1991).
17. [17] Koç, Ç. K. and Sunar, B., “Low-Complexity BitParallel Canonical and Normal Basis Multipliers for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 47, pp. 353
    356 (1998).
18. [18] Sunar, B. and Koç, Ç. K., “Mastrovito Multiplier for All Trinomials,” IEEE Trans. Computers, Vol. 48, pp. 522
    527 (1999).
19. [19] Wu, H., “Bit-Parallel Finite Field Multiplier and Square Using Polynomial Basis,” IEEE Trans. Computers, Vol. 51, pp. 750
    758 (2002).
20. [20] Elia, M., Leone, M. and Visentin, C., “Low Complexity Bit-Parallel Multipliers for GF(2m) with Generator Polynomial xm+xk +1,” Electronics Letters, Vol. 35, pp. 551
    552 (1999).
21. [21] Wu, H., “Montgomery Multiplier and Squarer for a Class of Finite Fields,” IEEE Trans. Computers, Vol. 51, pp. 521
    529 (2002).
22. [22] Lee, C. Y., “Low Complexity Bit-Parallel Systolic Multiplier Over GF(2m) Using Irreducible Trinomials,” IEE Proc.-Comput. Digit. Tech., Vol. 150, pp. 39
    42 (2003).
23. [23] Chiou, C. W., Lin, L. C., Chou, F. H. and Shu, S. F., “Low Complexity Finite Field Multiplier Using Irreducible Trinomials,” IEE Electronics Letters, Vol. 39, pp. 1709
    1711 (2003).
24. [24] Itoh, T. and Tsujii, S., “Structure of Parallel Multipliers for a Class of Fields GF(2m),” Information and Computation, Vol. 83, pp. 21
    40 (1989).
25. [25] Hasan, M. A., Wang, M. and Bhargava, V. K., “Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields GF(2m),” IEEE Trans. Computers, Vol. 41, pp. 962
    971 (1992).
26. [26] Lee, C. Y., Lu, E. H. and Lee, J. Y., “Bit-Parallel Systolic Multipliers for GF(2m) Fields Defined by All-One and Equally-Spaced Polynomials,” IEEE Trans. Computers, Vol. 50, pp. 385
    393 (2001).
27. [27] Paar, C., “A New Architecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Fields,” IEEE Trans. Computers, Vol. 45, pp. 856
    861 (1996).
28. [28] Paar, C., Fleischmann, P. and Roelse, P., “Efficient Multiplier Architectures for Galois Fields GF(24n),” IEEE Trans. Computers, Vol. 47, pp. 162
    170 (1998).
29. [29] Kim, N.-Y., Kim, H.-S. and Yoo, K.-Y., “Computation of AB2 Multiplication in GF(2m) Using Low-Complexity Systolic Architecture,” IEE Proc.-Circuits, Devices and Systems, Vol. 150, pp. 119
    123 (2003).
30. [30] Drolet, G., “A New Representation of Elements of Finite Fields GF(2m) Yielding Small Complexity Arithmetic Circuits,” IEEE Trans. Computers, Vol. 47, pp. 938
    946 (1998).
31. [31] Wang, C.-L. and Lin, J.-L., “Systolic Array Implementation of Multipliers for Finite Fields GF(2m),” IEEE Trans. Circuits and Systems, Vol. 38, pp. 796
    800 (1991).
32. [32] Wei, S.-W., “A Systolic Power-Sum Circuit for GF(2m),” IEEE Trans. Computers, Vol. 43, pp. 226
    229 (1994).
33. [33] Wei, S.-W., “VLSI Architectures for Computing Exponentiations, Multiplicative Inverses, and Divisions in GF(2m),” IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 44, pp. 847
    855 (1997).
34. [34] Yeh, C.-S., Reed, I. S. and Truong, T. K., “Systolic Multipliers for Finite Fields GF(2m),” IEEE Trans. Computers, Vol. C-33, pp. 357
    360 (1984).
35. [35] Wang, C. L. and Guo, J. H., “New Systolic Arrays for C+AB2 , Inversion, and Division in GF(2m),” IEEE Trans. Computers, Vol. 49, pp. 1120
    1125 (2000).
36. [36] Hsu, I. S., Truong, T. K., Deutsch, L. J. and Reed, I. S., “A Comparison of VLSI Architecture of Finite Field Multipliers Using Dual, Normal, or Standard Bases,” IEEE Trans. Computers, Vol. 37, pp. 735
    739 (1988).
37. [37] Weste, N. and Eshraghian, K., Principles of CMOS VLSI Design: A System Perspective, Reading, Mass.: Addison-Wesley (1985).
38. [38] http://www.st.com/stonline/books/pdf/docs/2006.pdf
39. [39] http://www.st.com/stonline/books/pdf/docs/1885.pdf
40. [40] Http://www.stm.com/stonline/products/literature/ ds/1937/m74hc279.pdf