Unified Parallel Systolic Multiplier Over GF(2^m)

Chiou-Yng Lee; Yung-Hui Chen; Che-Wun Chiou; Jim-Min Lin

Volume 22 Issue 1

January 2007

Turn off MathJax

Article Contents

Abstract

References

Journal of Computer Science and Technology > 2007 > 22(1): 28-38.

Chiou-Yng Lee, Yung-Hui Chen, Che-Wun Chiou, Jim-Min Lin. Unified Parallel Systolic Multiplier Over GF(2^m)[J]. Journal of Computer Science and Technology, 2007, 22(1): 28-38.

Citation:

Chiou-Yng Lee, Yung-Hui Chen, Che-Wun Chiou, Jim-Min Lin. Unified Parallel Systolic Multiplier Over GF(2^m)[J]. Journal of Computer Science and Technology, 2007, 22(1): 28-38.

Citation:

Chiou-Yng Lee, Yung-Hui Chen, Che-Wun Chiou, Jim-Min Lin. Unified Parallel Systolic Multiplier Over GF(2^m)[J]. Journal of Computer Science and Technology, 2007, 22(1): 28-38.

Previous Article Next Article

Unified Parallel Systolic Multiplier Over GF(2^m)

^{1} Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology Taoyuan County 333, Taiwan, China^{2}Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li 320, Taiwan, China^{3}Department of Information Engineering and Computer Science, Feng Chia University, Taichung City 407, Taiwan, China

More Information

Received Date: January 05, 2006
Revised Date: May 19, 2006
Published Date: January 14, 2007

Abstract

Abstract

In general, there are three popular basisrepresentations, standard (canonical, polynomial) basis, normal basis,and dual basis, for representing elements in ${\it GF}(2^{m}$ ). Variousbasis representations have their distinct advantages and have theirdifferent associated multiplication architectures. In this paper, wewill present a unified systolic multiplication architecture, byemploying Hankel matrix-vector multiplication, for various basisrepresentations. For various element representation in ${\it GF}(2^{m}$ ),we will show that various basis multiplications can be performed byHankel matrix-vector multiplications. A comparison with existing andsimilar structures has shown that the proposed architectures performwell both in space and time complexities.
- Hankel matrix-vector multiplication,
- bit-parallel systolic multiplier,
- Galois field GF2^m

FullText(HTML)

References (30)

References

[1]	Denning D E R. Cryptography and Data Security. Reading, MA: Addison-Wesley, 1983.
[2]	Rhee M Y. Cryptography and Secure Communications. Singapore: McGraw-Hill, 1994.
[3]	Menezes A, Oorschot P V, Vanstone S. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press, 1997.
[4]	Massey J L, Omura J K. Computational method and apparatus for finite field arithmetic. U.S. Patent Number 4.587.627, May 1986.
[5]	Itoh T, Tsujii S. Structure of parallel multipliers for a class of fields $-\it GF}(2-m}$ ). \it Information and Computation, \rm 1989, 83: 21--40.
[6]	Wu H, Hasan M A. Low complexity bit-parallel multipliers for a class of finite fields. \it IEEE Trans. Computers, \rm 1998, 47(8): 883--887.
[7]	Koc C K, Sunar B. Low complexity bit-parallel canonical and normal basis multipliers for a class of finite fields. \it IEEE Trans. Computers, \rm 1998, 47(3): 353--356.
[8]	Hasan M A, Wang M Z, Bhargava V K. A modified Massey-Omura parallel multiplier for a class of finite fields. \it IEEE Trans. Computers, \rm 1993, 42(10): 1278--1280.
[9]	Sunar B, Koc C K. An efficient optimal normal basis type II multiplier. \it IEEE Trans. Computers, \rm 2001, 50(1): 83--87.
[10]	Yeh C S, Reed S, Truong T K. Systolic multipliers for finite fields $-\it GF}(2-m}$ ). \it IEEE Trans. Computers, \rm 1984, C-33(4): 357--360.
[11]	Wang C L, Lin J L. Systolic array implementation of multipliers for finite fields $-\it GF}(2-m}$ ). \it IEEE Trans. Circuits and Systems, \rm 1991, 38(7): 796--800.
[12]	Wei S W. A systolic power-sum circuit for $-\it GF}(2-m}$ ). \it IEEE Trans. Computers, \rm 1994, 43(2): 226--229.
[13]	Wang C L. Bit-level systolic array for fast exponentiation in $-\it GF}(2-m}$ ). \it IEEE Trans. Computers, \rm 1994, 43(7): 838--841.
[14]	Lee C Y. Low-latency bit-parallel systolic multiplier for irreducible $x-m}+x-n}+1$ with $gcd(m,n)=1$ . \it IEICE Trans. Fundamentals, \rm 2003, E86-A(11): 2844--2852.
[15]	Lee C Y, Lu E H, Lee J Y. Bit-parallel systolic multipliers for $-\it GF}(2-m}$ ) fields defined by all-one and equally-spaced polynomials. \it IEEE Trans. Computers, \rm 2001, 50(5): 385--393.
[16]	Kwon S. A low complexity and a low latency bit parallel systolic multiplier over $-\it GF} (2-m}$ ) using an optimal normal basis of type II. In \it Proc. 16th IEEE Symp. Computer Arithmetic, \rm Santiago de Compostela, Spain, 2003, 16: 196--202.
[17]	Belekamp E R. Bit-serial Reed-Solomon encoders. \it IEEE Information Theory, \rm 1982, 28: 869--974.
[18]	Morii M, Kasahara K, Whiting D L. Efficient bit-serial multiplication and discrete-time Wiener-Hoph equation over finite fields. \it IEEE Trans. Information Theory, \rm 1989, 35: 1177--1184.
[19]	Wang M, Blake I F. Bit serial multiplication in finite fields. \it SIAM Discrete Math., \rm 1990, 3(1): 140--148.
[20]	Wang C C. An algorithm to design finite field multipliers using a self-dual normal basis. \it IEEE Trans. Computers, \rm 1989, 38(10): 1457--1459.
[21]	Wu H, Hasan M A, Blake L F. New low-complexity bit-parallel finite field multipliers using weakly dual bases. \it IEEE Trans. Computers, \rm 1998, 47(11): 1223--1234.
[22]	Fenn S T J, Benaissa M, Taylor D. $-\it GF}(2-m}$ ) Multiplication and division over the dual basis. \it IEEE Trans. Computers, \rm 1996, 45(3): 319--327.
[23]	Fenn S T J, Benaissa M, Taylor D. A dual basis systolic multipliers for $-\it GF}(2-m}$ ). \it IEE Proc-Comp. Digit. Tech., \rm 1997, 144(1): 43--46.
[24]	Weisstein E W. Hankel Matrix. Mathworld --A wolfram web resource, http://mathworld.com/HankelMatrix.html.
[25]	Parhi K. VLSI Signal Processing Systems: Design and Implementation. John Wiley \& Sons, 1999.
[26]	Seroussi G. Table of low-weight binary irreducible polynomials. Visual Computing Dept., Hewlett Packard Laboratories, Aug. 1998, Available at: http://www.hpl.hp.com/techre\-po\-rts/98/HPL-98-135.html.
[27]	Perlis S. Normal bases of cyclic fields of prime power degree. \it Duke Math. J., \rm 1942, 9: 507--517.
[28]	Mullin R C, Onyszchuk I M, Vanstone S A, Wilson R M. Optimal normal bases in $-\it GF}(p-n}$ ). \it Discrete Applied Math., \rm 1988/1989, 22: 149--161.
[29]	Brent R P, Zimmermann P. Algorithms for finding almost irreducible and almost primitive trinomials. In \it Primes and Misdemeeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams, \rm Fields Institute Communication FIC/41, The Fields Institute, Toronto, 2004, pp.91--102.
[30]	Lee C Y. Low complexity bit-parallel systolic multiplier over $-\it GF}(2-m}$ ) using irreducible trinomials. \it IEE Proc.-Comput. and Digit. Tech., \rm 2003, 150(1): 39--42.

Relative Articles

[1]	Dong-Yu Zheng, Yan Sun, Shao-Qing Li, Liang Fang. A 485ps 64-Bit Parallel Adder in 0.18 $\mu$ m CMOS[J]. Journal of Computer Science and Technology, 2007, 22(1): 25-27.
[2]	Chiou-Yng Lee, Jenn-Shyong Horng, I-Chang Jou. Low-Complexity Bit-Parallel Multiplier over GF(2 $^m$ ) Using Dual Basis Representation[J]. Journal of Computer Science and Technology, 2006, 21(6): 887-892.
[3]	Ye-Kui Wang. AVS-M: From Standards to Applications[J]. Journal of Computer Science and Technology, 2006, 21(3): 332-344.
[4]	ZHANG Zaiyue, SUI Yuefei. The Contiguity in R/M[J]. Journal of Computer Science and Technology, 2002, 17(4).
[5]	Gao Wen, Chen Xilin. A Stochastic Approach for Blurred Image Restoration and Optical Flow Computation on Field Image Sequence[J]. Journal of Computer Science and Technology, 1997, 12(5): 385-399.
[6]	Liang Xundong, Li Bin, Liu Shenquan. Three-Dimensional Vector Field Visualization Based on Tensor Decomposition[J]. Journal of Computer Science and Technology, 1996, 11(5): 452-460.
[7]	Luo Yinfang. Algorithm and Implementation of Parallel Multiplication in a Mixed Number System[J]. Journal of Computer Science and Technology, 1988, 3(3): 203-213.
[8]	Sun Yongqiang. Verification of Systolic Array:An FP Functional Approach[J]. Journal of Computer Science and Technology, 1988, 3(2): 81-101.
[9]	Qi Yulu. A Systolic Approach for an Improvement of a Finite Field Multiplier[J]. Journal of Computer Science and Technology, 1987, 2(4): 303-309.
[10]	Chen Shihua. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. Journal of Computer Science and Technology, 1986, 1(2): 54-59.

Supplements (0)

Cited By

Get Citation

XML

Article views (17) PDF downloads (5894)

Indexed in:

Unified Parallel Systolic Multiplier Over GF(2^m)

Abstract

References

Related Articles

Catalog

Related

Home

Overview

Resources

Contents

Indexed in:

Unified Parallel Systolic Multiplier Over GF(2^m)

Abstract

References

Related Articles

Catalog

Related

Home

Overview

Resources

Contents

Export File

Citation

Format

Content