THE FAST M-TRANSFORM - A FAST COMPUTATION OF CROSS-CORRELATIONS WITH BINARY M-SEQUENCES

An algorithm is presented for the fast computation of the m-transform, a Hadamard transform intimately related to cross-correlation of analog signals with binary m-sequences. It is shown that m-transforms are in the same Hadamard equivalence class as Walsh-Hadmard transforms and can, thus, be computed by means of the Fast Walsh Transform (FWT) algorithm, preceded and followed by a permutation. The FWT is performed in place in the original data array, while the permutations are executed during loading and reading of this array. Real-time generation of the array addresses for loading and reading adds little to execution time of the FWT. The implementation described here lends itself particularly well to applications in linear and nonlinear systems analysis.