Engineering topics

Mcclellan, J. H.

Publications and source records attributed to Mcclellan, J. H..

3 records

NASA NTRS1979

Bounds on the minimum number of data transfers in WFTA and FFT programs

Bounds on the minimum number of data transfers (i.e., loads, stores, copies) required by WFTA and FFT programs are presented. The analysis is applicable to those general-purpose computers with M general processor registers, where M is equal to or greater than 4 but much less than the transform length. It is shown that the 1008-point WFTA requires about 21 percent more data transfers than the 1024-point radix-4 FFT; on the other hand, the 120-point WFTA has about the same number of data transfers as the mixed radix (4 x 4 x 4 x 2) version of the 128-point FFT and 22 percent fewer than the radix-2 version. Finally, comparisons of the 'total' program execution times (multiplications, additions, and data transfers, but not indexing or permutations) are presented.

Nawab, H.↗

NASA NTRS1979

A comparison of WFTA and FFT programs

Bounds on the minimum number of data transfers (i.e., loads and stores) required by WFTA (Winograd Fourier Transform Algorithm) and FFT programs are presented. The analysis is applicable to those general-purpose computers with a small number of general processor registers (e.g., the IBM370, PDP-11, etc.). It is shown that the 1008-point WFTA requires about 21% more data transfers than the 1024-point radix-4 FFT; on the other hand, the 120-point WFTA has about 22% fewer data transfers than the 128-point radix-2 FFT. Finally, comparisons of the 'total' program execution times (multiplications, additions, and data transfers, but not indexing or permutations) are presented.

Nawab, H.↗

NASA NTRS1978

Fixed-point error analysis of Winograd Fourier transform algorithms

The quantization error introduced by the Winograd Fourier transform algorithm (WFTA) when implemented in fixed-point arithmetic is studied and compared with that of the fast Fourier transform (FFT). The effect of ordering the computational modules and the relative contributions of data quantization error and coefficient quantization error are determined. In addition, the quantization error introduced by the Good-Winograd (GW) algorithm, which uses Good's prime-factor decomposition for the discrete Fourier transform (DFT) together with Winograd's short length DFT algorithms, is studied. Error introduced by the WFTA is, in all cases, worse than that of the FFT. In general, the WFTA requires one or two more bits for data representation to give an error similar to that of the FFT. Error introduced by the GW algorithm is approximately the same as that of the FFT.

Patterson, R. W.↗