research-article

C-testable bit parallel multipliers over GF(2^m)

Authors:

A. M. JabirAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 13, Issue 1

Article No.: 5, Pages 1 - 18

https://doi.org/10.1145/1297666.1297671

Published: 06 February 2008 Publication History

Abstract

We present a C-testable design of polynomial basis (PB) bit-parallel (BP) multipliers over GF(2^m) for 100% coverage of stuck-at faults. Our design method also includes the method for test vector generation, which is simple and efficient. C-testability is achieved with three control inputs and approximately 6% additional hardware. Only 8 constant vectors are required irrespective of the sizes of the fields and primitive polynomial. We also present a Built-In Self-Test (BIST) architecture for generating the test vectors efficiently, which eliminates the need for the extra control inputs. Since these circuits have critical applications as parts of cryptography (e.g., Elliptic Curve Crypto (ECC) systems) hardware, the BIST architecture may provide with added level of security, as the tests would be done internally and without the requirement of probing by external testing equipment. Finally we present experimental results comprising the area, delay and power of the testable multipliers of various sizes with the help of the Synopsys® tools using UMC 0.18 micron CMOS technology library.

References

[1]

Abramovici, M., Breuer, M., and Friedman, A. 1994. Digital Systems Testing and Testable Design. IEEE Publications.

[2]

Agnew, G. B., Beth, T., Mullin, R. C., and Vanstone, S. A. 1993. Arithmetic operations in GF(2^m). J. Cryptol. 6, 3--13.

Digital Library

[3]

Becker, B. and Hartmann, J. 1990. Optimal-time multiplier and C-testability. ACM Symposium on Paralletism in Algorithms and Architectures (SPAA). 146--154.

Digital Library

[4]

Blahut, R. E. 1985. Fast Algorithms for Digital Signal Processing. Addison-Wesley.

Digital Library

[5]

Gulliver, T. A., Serra, M., and Bhargava, V. K. 1991. The generation of primitive polynomials in GF(2^m) with independent roots and their application for power residue codes, VLSI testing and finite field multipliers using normal bases. Int. J. Electr. 71, 4, 559--576.

[6]

Guo, J. H. and Wang, C. L. 1998. Systolic array implementation of Euclid's algorithm for inversion and division in GF(2^m). IEEE Trans. Comput. 47, 10, 1161--1167.

Digital Library

[7]

Haung, C. and Wu, C. 1997. High-speed C-testable systolic array design for Galois-field inversion. European Design and Test Conference (ED&TC 97). 342--346.

Digital Library

[8]

Lidl, R. and Niederreiter, H. 1994. Introduction to Finite Fields and Their Applications. Cambridge University Press.

Digital Library

[9]

Lombardi, F. and Sciuto, D. 1992. Constant testability of combinational cellular tree structure. J. Electr. Test.: Theor. Appl. 3, 139--148.

Digital Library

[10]

Mastrovito, E. D. 1988. VLSI designs for multiplication over finite fields GF(2^m). Proceedings of the International Joint Conference (AAECC88). 297--309.

Digital Library

[11]

Mastrovito, E. D. 1991. VLSI architectures for computation in Galois fields. PhD thesis, Linkoping University, Sweden.

[12]

Pradhan, D. K. 1978. A theory of Galois switching functions. IEEE Trans. Comput. 27, 3, 239--248.

Digital Library

[13]

Rahaman, H., Das, D. K., and Bhattacharya, B. B. 2004a. Easily testable realization of GRM and ESOP networks for detecting stuck-at and bridging faults. Proceedings of the IEEE Conference on VLSI Design India.

Digital Library

[14]

Rahaman, H., Das, D. K., and Bhattacharya, B. B. 2004b. Testable design of GRM network with EXOR--tree for detecting stuck-at and bridging faults. Proceedings of the Asia and South Pacific Design Automation Conference. 224--229.

Digital Library

[15]

Rahaman, H., Mathew, J., Jabir, A. M., and Pradhan, D. K. 2006. Easily testable implementation for bit parallel multipliers in GF(2^m). Proceedings of the IEEE International High Level Design Validation and Test Workshop. 48--54.

[16]

Reed, I. S. and Chen, X. 1999. Error-Control Coding for Data Networks. Kluwer Academic Publishing.

Digital Library

[17]

Reyhani--Masoleh, A. and Hasan, M. A. 2004. Low complexity bit parallel architectures for polynomial basis multiplication over GF(2^m). IEEE Trans. Comput. 53, 8, 945--959.

Digital Library

[18]

Scott, P. A., Simmons, S. J., Tavares, S. E., and Peppard, L. E. 1988. Architectures for exponentiation in GF(2^m). IEEE J. Selec. Areas Comm. 6, 3, 578--586.

Digital Library

[19]

Sridhar, T. and Hayes, J. P. 1981. Design of easily testable bit-sliced systems. Comput.-Aid.-Des. Integr. Circ. Syst. 28, 11, 1046--1058.

[20]

Wu, C. H., Wu, C. M., Sheih, M. D., and Hwang, Y. T. 2004. High-speed, low-complexity systolic design of novel iterative division algorithm in GF(2^m). IEEE Trans. Comput. 53, 375--380.

Digital Library

[21]

Wu, H., and Hasan, M. A. 1997. Efficient exponentiation of a primitive root in GF(2^m). IEEE Trans. Comput. 46, 2, 162--172.

Digital Library

[22]

Wu, Y. and Adham, M. I. 1999. Scan-based BIST fault diagnosis. IEEE Trans. CAD 18, 2, 203--211.

Digital Library

Cited By

Rahaman HMathew JJabir APradhan D(2012)VLSI architecture for bit parallel systolic multipliers for special class of GF(2m) using dual basesProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_30(258-269)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31494-0_30
Mathew JBanerjee SMahesh PPradhan DJabir AMohanty S(2010)Multiple Bit Error Detection and Correction in GF Arithmetic CircuitsProceedings of the 2010 International Symposium on Electronic System Design10.1109/ISED.2010.28(101-106)Online publication date: 20-Dec-2010
https://dl.acm.org/doi/10.1109/ISED.2010.28
Rahaman HMathew JJabir APradhan D(2009)C-testable S-box implementation for secure advanced encryption standard2009 15th IEEE International On-Line Testing Symposium10.1109/IOLTS.2009.5196017(210-211)Online publication date: Jun-2009
https://doi.org/10.1109/IOLTS.2009.5196017
Show More Cited By

Index Terms

C-testable bit parallel multipliers over GF(2^m)
1. Hardware
  1. Hardware test
  2. Robustness
    1. Hardware reliability

Recommendations

Transition faults detection in bit parallel multipliers over GF(2^m)

In this article, a C-testable design for detecting transition faults in the polynomial basis (PB) bit parallel (BP) multiplier circuits over GF(2^m) is discussed. For 100 percent transition fault coverage, the proposed technique requires only 10 vectors, ...
Transition Fault Testability in Bit Parallel Multipliers over GF(2^{m})
VTS '07: Proceedings of the 25th IEEE VLSI Test Symmposium

This paper presents a C-testable technique for detecting transition faults with 100% fault coverage in the polynomial basis (PB) bit parallel (BP) multiplier circuits over GF(2^{m}). The proposed technique requires only 10 vectors, which is independent ...
Test generation in systolic architecture for multiplication over GF(2^m)

This paper presents a test generation technique for detecting stuck-at (SAF) and transition delay fault (TDF) at gate level in the finite-field systolic multiplier over GF(2^m) based on polynomial basis. The proposed technique derives test vectors from ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 13, Issue 1

January 2008

496 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1297666

Issue’s Table of Contents

Copyright © 2008 ACM.

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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 06 February 2008

Accepted: 01 June 2007

Revised: 01 June 2007

Received: 01 June 2006

Published in TODAES Volume 13, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Engineering and Physical Sciences Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rahaman HMathew JJabir APradhan D(2012)VLSI architecture for bit parallel systolic multipliers for special class of GF(2m) using dual basesProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_30(258-269)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31494-0_30
Mathew JBanerjee SMahesh PPradhan DJabir AMohanty S(2010)Multiple Bit Error Detection and Correction in GF Arithmetic CircuitsProceedings of the 2010 International Symposium on Electronic System Design10.1109/ISED.2010.28(101-106)Online publication date: 20-Dec-2010
https://dl.acm.org/doi/10.1109/ISED.2010.28
Rahaman HMathew JJabir APradhan D(2009)C-testable S-box implementation for secure advanced encryption standard2009 15th IEEE International On-Line Testing Symposium10.1109/IOLTS.2009.5196017(210-211)Online publication date: Jun-2009
https://doi.org/10.1109/IOLTS.2009.5196017
Singh ABera ARahaman HMathew JPradhan D(2009)Error Detecting Dual Basis Bit Parallel Systolic Multiplication Architecture over GF(2m)2009 IEEE Circuits and Systems International Conference on Testing and Diagnosis10.1109/CAS-ICTD.2009.4960812(1-4)Online publication date: Apr-2009
https://doi.org/10.1109/CAS-ICTD.2009.4960812
Mathew JJabir ARahaman HPradhan D(2009)Single error correctable bit parallel multipliers over GF(2m)IET Computers & Digital Techniques10.1049/iet-cdt.2008.00153:3(281)Online publication date: 2009
https://doi.org/10.1049/iet-cdt.2008.0015
Chen IKuo SYeh PYe B(2009)Scalable and bijective cells for C-testable iterative logic array architecturesIET Circuits, Devices & Systems10.1049/iet-cds.2008.02963:4(172-181)Online publication date: 1-Aug-2009
https://doi.org/10.1049/iet-cds.2008.0296
Rahaman HDas DBhattacharya B(2009)Testable design of AND-EXOR logic networks with universal test setsComputers and Electrical Engineering10.1016/j.compeleceng.2009.01.00635:5(644-658)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.compeleceng.2009.01.006
Mathew JSingh JJabir AHosseinabady MPradhan D(2008)Fault tolerant bit parallel finite field multipliers using LDPC codes2008 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2008.4541760(1684-1687)Online publication date: May-2008
https://doi.org/10.1109/ISCAS.2008.4541760

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents