This correspondence develops efficient fast Fourier transform (FFT) programs to transform arrays of dimension N, where N can be written as a power of two possibly multiplied by arbitrary factors. Two programs were developed which use radix-2 and radix-4 transformations for the binary factors. These programs call another subprogram to transform with respect to the arbitrary factors, if any. Since the sequential transformation is well known, the emphasis is on developing an efficient unscrambling procedure to follow the transformation.

Radix—2 fast Fourier transform programs of the Gentleman-Sande type leave the transformed array in a scrambled order of frequencies. Unscrambling is accomplished by moving each element from its present location into a new location obtained by bit reversal. Bit reversal can be interpreted as an exchange of groups of bits symmetric with respect to a pivot. Two formulas are developed for simultaneous and sequential exchanging in place, with negligible auxiliary storage. Programs for one-step and sequential unscrambling were implemented. Binary unscrambling is useful to unscramble large arrays in peripheral storage. The one-step unscrambling program presented is more efficient than other programs available in the literature.

This paper describes a general systematic procedure for the convolution of functions that are piecewise polynomial. The procedure can be implemented by hand using a simple table format or programmed for execution on a digital computer. An algebraic convolution law is dermed to replace integration; this provides an efficient digital computation algorithm. Thus, convolution operations of any complexity can be transformed into the algebraic manipulation of numbers by a digital computer.

The output of a system is often expressed as a sequence of unary and/or binary operations on the input. Analysis or design considerations may require manipulation of the sequence of operators to obtain an equivalent sequence either mathematically simpler or easier to design. For this purpose, available operator algebra must be considerably expanded. Several new operators are introduced: the multiple operator which is a combination of unary operators, and the zero-convolution and zero-correlation operators. Three commutation tables are developed, one for unary and transform operators, one for binary operators, and one for binary operators operating on two functions already transformed by unary or transform operators. The commutation tables can be used to manipulate and simplify a sequence of operators. They should be useful in the analysis and design of complex systems. This becomes quite clear when one tries to repeat the examples of this paper without using the commutation tables. The simplification of sequence of operators procedure not only permits a faster simplification of multiple integral transformations, but it also provides such a clear picture of the operations to perform that the manipulations become obvious. This contrasts with the conventional technique of rearranging the integrals and performing changes of variables somewhat blindly. Since the purpose of this paper is to make available a practical tool, most of the derivations of the formulas were left out for conciseness.