skip to main content
research-article

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

Published: 06 February 2008 Publication History

Abstract

We present a C-testable design of polynomial basis (PB) bit-parallel (BP) multipliers over GF(2m) 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(2m). J. Cryptol. 6, 3--13.
[3]
Becker, B. and Hartmann, J. 1990. Optimal-time multiplier and C-testability. ACM Symposium on Paralletism in Algorithms and Architectures (SPAA). 146--154.
[4]
Blahut, R. E. 1985. Fast Algorithms for Digital Signal Processing. Addison-Wesley.
[5]
Gulliver, T. A., Serra, M., and Bhargava, V. K. 1991. The generation of primitive polynomials in GF(2m) 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(2m). IEEE Trans. Comput. 47, 10, 1161--1167.
[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.
[8]
Lidl, R. and Niederreiter, H. 1994. Introduction to Finite Fields and Their Applications. Cambridge University Press.
[9]
Lombardi, F. and Sciuto, D. 1992. Constant testability of combinational cellular tree structure. J. Electr. Test.: Theor. Appl. 3, 139--148.
[10]
Mastrovito, E. D. 1988. VLSI designs for multiplication over finite fields GF(2m). Proceedings of the International Joint Conference (AAECC88). 297--309.
[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.
[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.
[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.
[15]
Rahaman, H., Mathew, J., Jabir, A. M., and Pradhan, D. K. 2006. Easily testable implementation for bit parallel multipliers in GF(2m). 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.
[17]
Reyhani--Masoleh, A. and Hasan, M. A. 2004. Low complexity bit parallel architectures for polynomial basis multiplication over GF(2m). IEEE Trans. Comput. 53, 8, 945--959.
[18]
Scott, P. A., Simmons, S. J., Tavares, S. E., and Peppard, L. E. 1988. Architectures for exponentiation in GF(2m). IEEE J. Selec. Areas Comm. 6, 3, 578--586.
[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(2m). IEEE Trans. Comput. 53, 375--380.
[21]
Wu, H., and Hasan, M. A. 1997. Efficient exponentiation of a primitive root in GF(2m). IEEE Trans. Comput. 46, 2, 162--172.
[22]
Wu, Y. and Adham, M. I. 1999. Scan-based BIST fault diagnosis. IEEE Trans. CAD 18, 2, 203--211.

Cited By

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Index Terms

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

      Recommendations

      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
      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

      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.

      Check for updates

      Author Tags

      1. C-testable
      2. Galois field
      3. TPG
      4. VLSI design
      5. built-in self-test
      6. cryptography
      7. digital signal processing
      8. error control code
      9. fault
      10. multiplier
      11. polynomials
      12. stuck-at fault
      13. testing

      Qualifiers

      • Research-article
      • Research
      • Refereed

      Funding Sources

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)1
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (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
      • (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
      • (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
      • (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
      • (2009) Single error correctable bit parallel multipliers over GF(2 m ) IET Computers & Digital Techniques10.1049/iet-cdt.2008.00153:3(281-288)Online publication date: 5-May-2009
      • (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: 13-Aug-2009
      • (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
      • (2008)Fault tolerant bit parallel finite field multipliers using LDPC codes2008 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2008.4541760(1684-1687)Online publication date: May-2008

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media