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

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.
• 3: B. Becker , J. Hartmann, Optimal-time multipliers and C-testability, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.146-154, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97680]
• 4: Richard E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 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: Jyh-Huei Guo , Chin-Liang Wang, Systolic Array Implementation of Euclid's Algorithm for Inversion and Division in GF (2m), IEEE Transactions on Computers, v.47 n.10, p.1161-1167, October 1998 [doi>10.1109/12.729800]
• 7: C-T. Huang , C-W. Wu, High-Speed C-Testable Systolic Array Design for Galois-Field InversionChih-Tsun Huang and Cheng-Wen Wu, Proceedings of the 1997 European conference on Design and Test, p.342, March 17-20, 1997
• 8: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 9: F. Lombardi , D. Sciuto, Constant testability of combinational cellular tree structures, Journal of Electronic Testing: Theory and Applications, v.3 n.2, p.139-148, May 1992 [doi>10.1007/BF00137251]
• 10: Edoardo D. Mastrovito, VLSI Designs for Multiplication over Finite Fields GF (2m), Proceedings of the 6th International Conference, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.297-309, July 04-08, 1988
• 11: Mastrovito, E. D. 1991. VLSI architectures for computation in Galois fields. PhD thesis, Linkoping University, Sweden.
• 12: D. K. Pradhan, A Theory of Galois Switching Functions, IEEE Transactions on Computers, v.27 n.3, p.239-248, March 1978 [doi>10.1109/TC.1978.1675077]
• 13: Hafizur Rahaman , Debesh K. Das , Bhargab B. Bhattacharya, Easily Testable Realization of GRM and ESOP Networks for Detecting Stuck-at and Bridging Faults, Proceedings of the 17th International Conference on VLSI Design, p.487, January 05-09, 2004
• 14: Hafizur Rahaman , Debesh K. Das , Bhargab B. Bhattacharya, Testable design of GRM network with EXOR-tree for detecting stuck-at and bridging faults, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 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: Xuemin Chen , Irving S. Reed, Error-Control Coding for Data Networks, Kluwer Academic Publishers, Norwell, MA, 1999
• 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.
• 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.
• 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: Chien-Hsing Wu , Chien-Ming Wu , Ming-Der Shieh , Yin-Tsung Hwang, High-Speed, Low-Complexity Systolic Designs of Novel Iterative Division Algorithms in GF(2^m), IEEE Transactions on Computers, v.53 n.3, p.375-380, March 2004 [doi>10.1109/TC.2004.1261843]
• 21: Huapeng Wu , M. Anwarul Hasar, Efficient Exponentiation of a Primitive Root in GF(2m), IEEE Transactions on Computers, v.46 n.2, p.162-172, February 1997 [doi>10.1109/12.565591]
• 22: Wu, Y. and Adham, M. I. 1999. Scan-based BIST fault diagnosis. IEEE Trans. CAD 18, 2, 203--211.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.3 Reliability and Testing**

General Terms:
Reliability

Keywords:
C-testable, Galois field, TPG, VLSI design, built-in self-test, cryptography, digital signal processing, error control code, fault, multiplier, polynomials, stuck-at fault, testing