Test generation for combinational quantum cellular automata (QCA) circuits

ABSTRACT

In this paper, we present a test generation framework for testing of quantum cellular automata (QCA) circuits. QCA is a nanotechnology that has attracted significant recent attention and shows immense promise as a viable future technology. This work is motivated by the fact that the stuck-at fault test set of a circuit is not guaranteed to detect all defects that can occur in its QCA implementation. We show how to generate additional test vectors to supplement the stuck-at fault test set to guarantee that all simulated defects in the QCA gates get detected. Since nanotechnologies will be dominated by interconnects, we also target bridging faults on QCA interconnects. The efficacy of our framework is established through its application to QCA implementations of MCNC benchmarks that use majority gates as primitives.

REFERENCES

• 1: "International Technology Roadmap for Semiconductors." http://public.itrs.net
• 2: P. D. Tougaw and C. S. Lent, "Logical devices implemented using quantum cellular automata," J. Applied Physics, vol. 75, no. 3, pp. 1818--1825, Feb. 1994.
• 3: I. Amlani, A. O. Orlov, G. L. Snider, and C. S. Lent, "Demonstration of a six-dot quantum cellular automata system," Appl. Phys. Lett., vol. 72, no. 17, pp. 2179--2181, Apr. 1998.
• 4: I. Amlani, A. O. Orlov, G. Toth, C. S. Lent, G. Bernstein, and G. L. Snider, "Digital logic gate using quantum-dot cellular automata," Science, vol. 284, no. 5412, pp. 289--291, Apr. 1999.
• 5: M. Lieberman, S. Chellamma, B. Varughese, Y. Wang, C. S. Lent, G. Bernstein, G. L. Snider, and F. Peiris, "Quantum-dot cellular automata at a molecular scale," Ann. New York Acad. Sci., vol. 960, pp. 225--239, 2002.
• 6: K. Hennessy and C. S. Lent, "Clocking of molecular quantum-dot cellular automata," J. Vac. Sci. Technol., vol. 19, no. 5, pp. 1752--1755, Sept. 2001.
• 7: M. B. Tahoori, J. Huang, M. Momenzadeh, and F. Lombardi, "Testing of quantum cellular automata," IEEE Trans. Nanotechnol., vol. 3, no. 4, pp. 432--442, Dec. 2004.
• 8: Rui Zhang , Pallav Gupta , Niraj K. Jha, Synthesis of Majority and Minority Networks and Its Applications to QCA, TPL and SET Based Nanotechnologies, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.229-234, January 03-07, 2005 [doi>10.1109/ICVD.2005.157]
• 9: R. Zhang, K. Walus, W. Wang, and G. A. Jullien, "A method of majority logic reduction for quantum cellular automata," IEEE Trans. Nanotechnol., vol. 3, no. 4, pp. 443--450, Dec. 2004.
• 10: D. Berzon , T. J. Fountain, A Memory Design in QCAs using the SQUARES Formalism, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.166, March 04-06, 1999
• 11: Nadine Gergel , Shana Craft , John Lach, Modeling QCA for area minimization in logic synthesis, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764824]
• 12: K. Walus, T. Dysart, G. A. Jullien, and R. A. Budiman, "QCADesigner: A rapid design and simulation tool for quantum-dot cellular automata," IEEE Trans. Nanotechnol., vol. 3, no. 1, pp. 26--31, Mar. 2004.
• 13: Mehdi Baradaran Tahoori , Mariam Momenzadeh , Jing Huang , Fabrizio Lombardi, Defects and Faults in Quantum Cellular Automata at Nano Scale, Proceedings of the 22nd IEEE VLSI Test Symposium, p.291, April 25-29, 2004
• 14: Niraj K. Jha , Sandeep Gupta, Testing of Digital Systems, Cambridge University Press, New York, NY, 2002
• 15: M. Momenzadeh, M. B. Tahoori, J. Huang, and F. Lombardi, "Quantum cellular automata: New defects and faults for new devices," in Proc. Int. Parallel and Distributed Processing Symp., Apr. 2004, pp. 207--214.
• 16: K. Walus, G. Schulhof, and G. A. Jullien, "High level exploration of quantum-dot cellular automata," in Proc. Conf. Signals, Systems, and Computers, Nov. 2004, pp. 7--10.
• 17: T. Larrabee, "Test pattern generation using Boolean satisfiability," IEEE Trans. Computer-Aided Design, vol. 11, no. 1, pp. 4--15, Jan. 1992.
• 18: Hyung Ki Lee , Dong Sam Ha, An Efficient, Forward Fault Simulation Algorithm Based on the Parallel Pattern Single Fault Propagation, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.946-955, October 26-30, 1991
• 19: Paul Beckett , Andrew Jennings, Towards nanocomputer architecture, Proceedings of the seventh Asia-Pacific conference on Computer systems architecture, p.141-150, January 01, 2002, Melbourne, Victoria, Australia
• 20: R. Lisanke, "Logic synthesis and optimization benchmarks," Microelectronics Center of North Carolina, Tech. Rep., 1988.
• 21: Ellen Sentovich , Kanwar Jit Singh , Cho W. Moon , Hamid Savoj , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Sequential Circuit Design Using Synthesis and Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.328-333, October 11-14, 1992