Cited By
View all- Barford L(2006)Diagnosis and Design for Diagnosability for Internet RoutersProceedings of the 7th International Symposium on Quality Electronic Design10.1109/ISQED.2006.51(761-768)Online publication date: 27-Mar-2006
Efficient FFT network testing and diagnosis schemes
Authors: 
Jin-Fu Li, Cheng-Wen WuAuthors Info & Claims
Pages 267 - 278
Abstract
We consider offline testing, design-for-testability, and diagnosis for fast Fourier transform (FFT) networks. A practical FFT chip can contain millions of gates, so effective testing and fault-tolerance techniques usualiy are required in order to guarantee high-quality products. We propose M-testability conditions for FFT butterfly, omega, and flip networks at the double-multiply-subtract-add (DMSA) module level. A novel design-for-testability technique based on the functional bijectivity property of the specified modules to detect faults other than the cell faults is presented. It guarantees 100% Combinational fault coverage with negligible hardware overhead--about 0.17% for an FFT network with 16-bit operand words, independent of the network size. Our design requires fewer test vectors compared with previous ones--a factor of up to 1/(6 × 25n), where n is the word length. We also propose C-diagnosability conditions and a C-diagnosable FFT network design. By properly exchanging and blocking certain fault propagation paths, a faulty DMSA module can be located using a two-phase deterministic algorithm. The blocking mechanism can be implemented with no additional hardware. Compared with previous schemes, our design reduces the diagnosis complexity from O(N) to O(1). For both testing and diagnosis, the hardware overhead for our approach is only about 0.43% for 16-bit numbers regardless of the FFT network size.
References
[1]
{1} A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing . Englewood Cliffs, NJ: Prentice-Hall, 1989.
[2]
{2} A. E. Cetin, O. N. Gerek, and Y. Yardimci, "Equiripple FIR filter design by FFT algorithm," IEEE Signal Processing Mag., vol. 14, pp. 60-64, Mar. 1997.
[3]
{3} P. Noll, "MPEG digital audio coding," IEEE Signal Processing Mag., vol. 14, pp. 59-81, Sept. 1997.
[4]
{4} J. O'Brien, J. Mather, and B. Holl, "A 200 MIPS single-chip 1K FFT processor," in Proc. IEEE Int. Solid-State Circuit Conf. (ISSCC), Feb. 1989, pp. 166-167, 327.
[5]
{5} E. Bidet, D. Castelain, C. Joanblanq, and P. Senn, "A fast single-chip implementation of 8192 complex point FFT," IEEE J. Solid-State Circuits, vol. 30, pp. 300-305, Mar. 1995.
[6]
{6} C. C. W. Hui, T. J. Ding, J. V. McCanny, and R. E Woods, "A 64-point Fourier transform chip for video motion compensation using phase correlation," IEEE J. Solid-State Circuits, vol. 31, pp. 1751-1761, Nov. 1996.
[7]
{7} M. Wosnitza, M. Cavadini, M. Thaler, and G. Troster, "A high precision 1024-point FFT processor for 2D convolution," in Proc. IEEE Int. Solid-State Circuit Conf. (ISSCC), Feb. 1998, pp. 118-119, 424.
[8]
{8} B. M. Bass, "A low-power, high-performance, 1024-point FFT processor," IEEE J. Solid-State Circuits, vol. 34, pp. 380-387, Mar. 1999.
[9]
{9} T. Chen, G. Sunada, and J. Jin, "COBRA: A 100-MOPS single-chip programmable and expandable FFT," IEEE Trans. VLSI Syst., vol. 7, pp. 174-182, June 1999.
[10]
{10} J.-Y. Jou and J. A. Abraham, "Fault-tolerant FFT networks," IEEE Trans. Comput., vol. 37, pp. 548-561, May 1988.
[11]
{11} y.-H. Choi and M. Malek, "A fault-tolerant FFT processor," IEEE Trans. Comput., vol. 37, pp. 617-621, May 1988.
[12]
{12} V. K. Jain, S. A. Al-Arian, D. L. Landis, and H. A. Nienhans, "Fully parallel and testable WSI architecture for an FFT processor," Int. J. Computer-Aided VLSI Design, vol. 3, pp. 113-135, 1991.
[13]
{13} A. Antola and M. G. Sami, "Testing and diagnosis of FFT arrays," J. VLSI Signal Processing, pp. 225-236, 1991.
[14]
{14} F. Lombardi and J. Muzio, "Concurrent error detection and fault location in an FFT architecture," IEEE J. Solid-State Circuits, vol. 27, pp. 728-736, May 1992.
[15]
{15} C. Feng, J. C. Muzio, and F. Lombardi, "On the testability of the array structures for FFT computation," J. Electron. Testing: Theory Applicat., vol. 4, pp. 215-224, Aug. 1993.
[16]
{16} D.L. Tao and C. R. P. Hartmann, "A novel concurrent error detection scheme for FFT networks," IEEE Trans. Parallel Distrib. Syst., vol. 4, pp. 198-221, Feb. 1993.
[17]
{17} C.-W. Wu and C.-T. Chang, "FFT butterfly network design for easy testing," IEEE Trans. Circuits Syst., vol. 40, pp. 110-115, Feb. 1993.
[18]
{18} S.-K. Lu, C.-W. Wu, and S.-Y. Kuo, "Enhancing testability of VLSI arrays for fast Fourier transform," Inst. Elect. Eng. Proc. Pt. E, vol. 140, pp. 161-166, May 1993.
[19]
{19} S. J. Wang and N. K. Jha, "Algorithm-based fault tolerance for FFT networks," IEEE Trans. Comput., vol. 43, pp. 849-854, July 1994.
[20]
{20} C.G. Oh and H. Y. Youn, "On concurrent error location and correction of FFT networks," IEEE Trans. VLSI Syst., vol. 2, pp. 257-260, June 1994.
[21]
{21} C.G. Oh, H. Y. Youn, and V. K. Raj, "An efficient algorithm-based concurrent error detection for FFT network," IEEE Trans. Comput., vol. 44, pp. 1157-1162, Sept. 1995.
[22]
{22} S.-K. Lu, C.-W. Wu, and S.-Y. Kuo, "On fault-tolerant FFT butterfly network design," in Proc. IEEE Int. Symp. Circuits Syst. (ISCAS), Atlanta, May 1996, pp. 69-72.
[23]
{23} M. Tsunoyama, M. Uenoyama, and T. Kabasawa, "A concurrent fault-detection scheme for FFT processors," in Proc. 6th IEEE Asian Test Symp. (ATS), Akita, Nov. 1997, pp. 94-99.
[24]
{24} K. Yamashita, A. Kanasugi, S. Hijiya, G. Goto, N. Matsumura, and T. Shirato, "A wafer-scale 170000-gate FFT processor with built-in test circuits," IEEE J. Solid-State Circuits, vol. 23, pp. 336-342, April 1988.
[25]
{25} C.-W. Wu and P. R. Cappello, "Easily testable iterative logic arrays," IEEE Trans. Comput., vol. 39, pp. 640-652, May 1990.
[26]
{26} A. D. Friedman, "Easily testable iterative systems," IEEE Trans. Comput., vol. 22, pp. 1061-1064, Dec. 1973.
[27]
{27} C.-W. Wu and S.-K. Lu, "Designing self-testable cellular arrays," in Proc. IEEE Int. Conf. Comput. Design (ICCD), Cambridge, MA, Oct. 1991, pp. 110-113.
[28]
{28} P. R. Menon and A. D. Friedman, "Fault detection in iterative arrays," IEEE Trans. Comput., vol. 20, pp. 524-535, May 1971.
[29]
{29} S.-K. Lu, J.-C. Wang, and C.-W. Wu, "C-testable design techniques for iterative logic arrays," IEEE Trans. VLSI Syst., vol. 3, pp. 146-152, Mar. 1995.
[30]
{30} N. Weste and K. Eshraghian, Principles of CMOS VLSI Design: A Systems Perspective, 2nd ed. Reading, MA: Addison-Wesley, 1993.
Index Terms
- Efficient FFT network testing and diagnosis schemes
Recommendations
Design-for-testability and fault-tolerant techniques for FFT processors
In this paper, we first propose a novel design-for-testability approach based on M-testability conditions for module-level systolic fast Fourier transform (FFT) arrays. Our M-testability conditions guarantee 100% single-module-fault testability with a ...
Quantum Boolean Circuits are 1-Testable
Recently, a systematic procedure was proposed to derive a minimum input quantum circuit for any given classical logic with the generalized quantum Toffoli gate, which is universal in Boolean logic. Since quantum Boolean circuits are reversible, we can ...
Multi-Layer Test and Diagnosis for Dependable NoCs
NOCS '15: Proceedings of the 9th International Symposium on Networks-on-ChipNetworks-on-chip are inherently fault tolerant or at least gracefully degradable as both, connectivity and amount of resources, provide some useful redundancy. These properties can only be exploited extensively if test and diagnosis techniques support ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2002.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 01 June 2002
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View all- Barford L(2006)Diagnosis and Design for Diagnosability for Internet RoutersProceedings of the 7th International Symposium on Quality Electronic Design10.1109/ISQED.2006.51(761-768)Online publication date: 27-Mar-2006
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in