Article

High-speed systolic architectures for finite field inversion and division

Authors:

Zhiyuan Yan,

Dilip V. SarwateAuthors Info & Claims

GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI

Pages 462 - 465

https://doi.org/10.1145/988952.989064

Published: 26 April 2004 Publication History

Get Access

Abstract

Based on a new reformulation of the extended Euclidean algorithm, systolic architectures suitable for VLSI implementations are proposed for finite field inversion and division in this paper. The architectures proposed in this paper can achieve O(m²) area-time complexity, O(m) latency, and critical path delays of two logic gates. These architectures show improved performances when compared with previously proposed architectures.

References

[1]

K. Araki, I. Fujita, and M.Morisue, "Fast Inverters over Finite Field Based on Euclid 's Algorithm," Trans. of IEICE, vol.72E, no.11, pp.1230--1234, November 1989.

Google Scholar

[2]

J.-H.Guo and C.-L.Wang, "Hardware-efficient Systolic Architecture for Inversion and Division in GF(2m),"in IEEE Proceedings on Comp ters and Digital Techniques, 1998, pp.272--278.

Crossref

Google Scholar

[3]

K.K.Parhi, VLSI Digital Signal Processing Systems, John Wiley and Sons, New York, 1999.

Google Scholar

[4]

Y.Watanabe, N.Takagi, and K.Takagi, "A VLSI Algorithm for Division in GF(2m)Based on Extended Binary GCD Algorithm,"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E85-A, no.5, pp.994--999, May 2002.

Google Scholar

[5]

C.H.Wu, C.M.Wu, M.D.Shieh, and Y.T.Wang, "Systolic VLSI Realization of a Nove Iterative Division Algorithm over GF(2m): a High-Speed, Low-Complexity Design," in Proceedings of ISCAS '01, Re-2001, pp.33--36.

Google Scholar

[6]

Z.Yan and D.V. Sarwate, "New systolic architectures for inversion and division in GF(2m),"IEEE Transactions on Computers, vol.42, pp.1515--1520, architec-November 2003.

Digital Library

Google Scholar

[7]

Z.Yan and D.V.Sarwate, "Systolic Architectures for Finite Field Inversion and Division," in Proceedings of ISCAS '02, 2002, pp.789--792.

Digital Library

Google Scholar

Cited By

View all

Yi H(2023)Parallel Finite Field Algorithms for Communications and Sensor NetworksACM Transactions on Sensor Networks10.1145/3572774Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1145/3572774
Yan ZSarwate DLiu Z(2006)Erratum toIntegration, the VLSI Journal10.1016/j.vlsi.2005.04.00239:4(474-476)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1016/j.vlsi.2005.04.002
Yan ZSarwate DLiu Z(2005)High-speed systolic architectures for finite field inversionIntegration, the VLSI Journal10.5555/1062115.171208738:3(383-398)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/1062115.1712087
Show More Cited By

Index Terms

High-speed systolic architectures for finite field inversion and division
1. Hardware
  1. Integrated circuits
    1. Logic circuits
      1. Arithmetic and datapath circuits

Recommendations

High-speed systolic architectures for finite field inversion
Special issue: ACM great lakes symposium on VLSI

Using a new reformulation of the extended Euclidean algorithm, we propose new two-dimensional systolic architectures for inversion in GF ( 2 m ) . Our new architectures require considerably less hardware in comparison to the architectures we proposed ...
Systolic and non-systolic scalable modular designs of finite field multipliers for reed-solomon codec

In this paper, we present efficient algorithms for modular reduction to derive novel systolic and nonsystolic architectures for polynomial basis finite field multipliers over GF(2_m) to be used in Reed-Solomon (RS) codec. Using the proposed algorithm for ...
Systolic architectures for inversion/division using AB² circuits in GF(2^m)

The current paper presents a new AB² algorithm based on the MSB-first scheme using a standard basis representation of Galois fields, GF(2^m). Thereafter, parallel-in parallel-out and serial-in serial-out systolic realizations for computing AB² and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI

April 2004

479 pages

ISBN:1581138539

DOI:10.1145/988952

General Chair:
David Garrett
Bell Labs Research, Lucent Technologies
,
Program Chairs:
John Lach
University of Virginia
,
Charles Zukowski
Columbia University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 April 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GLSVLSI04

Sponsor:

GLSVLSI04: Great Lakes Symposium on VLSI 2004

April 26 - 28, 2004

MA, Boston, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
292
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yi H(2023)Parallel Finite Field Algorithms for Communications and Sensor NetworksACM Transactions on Sensor Networks10.1145/3572774Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1145/3572774
Yan ZSarwate DLiu Z(2006)Erratum toIntegration, the VLSI Journal10.1016/j.vlsi.2005.04.00239:4(474-476)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1016/j.vlsi.2005.04.002
Yan ZSarwate DLiu Z(2005)High-speed systolic architectures for finite field inversionIntegration, the VLSI Journal10.5555/1062115.171208738:3(383-398)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.5555/1062115.1712087
Yan ZSarwate DLach JQu GIsmail Y(2005)Area-efficient two-dimensional architectures for finite field inversion and divisionProceedings of the 15th ACM Great Lakes symposium on VLSI10.1145/1057661.1057690(116-121)Online publication date: 17-Apr-2005
https://dl.acm.org/doi/10.1145/1057661.1057690
Jachimiec NIliev NStine J(2005)Strategies for VLSI implementations of finite field inversion algorithms48th Midwest Symposium on Circuits and Systems, 2005.10.1109/MWSCAS.2005.1594419(1589-1592 Vol. 2)Online publication date: 2005
https://doi.org/10.1109/MWSCAS.2005.1594419
Yan ZSarwate D(2003)New Systolic Architectures for Inversion and Division in GF(2^m)IEEE Transactions on Computers10.1109/TC.2003.124495052:11(1514-1519)Online publication date: 1-Nov-2003
https://dl.acm.org/doi/10.1109/TC.2003.1244950

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

High-speed systolic architectures for finite field inversion

Systolic and non-systolic scalable modular designs of finite field multipliers for reed-solomon codec

Systolic architectures for inversion/division using AB² circuits in GF(2^m)