FFT Butterfly Network Design for Easy Testing

We consider off-line testing and easily testable design of butterfly networks for fast Fourier transform. The butterfly networks are shown to be testable with 32 patterns using a design-for-testability technique based on the M-testability conditions. The functional-level cell-fault model is assumed, and the fault coverage for combinational single cell faults is 100%. A higher-level fault model-the module-fault model-is also discussed. We present a novel input-assignment technique based on the functional byectivity property of the butterfly modules to discover faults other than the cell faults (e.g., interconnection faults).