Digital Signal Processing, 10th Edition

3Other Fast Algorithms for the FFT

Algorithms for the fast calculation of a discrete Fourier transform (DFT) are based on factorization of the matrix of the transform. We have already seen such factorization in the sections on decimation-in-time and decimation-in-frequency algorithms, in the preceding chapter, which are particular examples of a large group of algorithms.

In order to use these fast algorithms and thus to exploit to the full both the characteristics of the signals to be processed and the various technological possibilities, one must use a suitable mathematical tool – the Kronecker product of matrices. By combining this product with the conventional product, it is possible to factorize the matrix of the DFT in a simple way.

3.1 Kronecker Product of Matrices

The Kronecker product is a tensor operation which is a generalization of the multiplication of a matrix by a scalar [1]. Knowing two matrices A and B with m and p rows and n and q columns respectively, the Kronecker product of A by B (written A × B) is a new matrix with mp rows and nq columns, which is obtained by replacing each element b_ij of the matrix B by the following array b_ijA:

This product is generally not commutative:

As an example of the product, if the matrix B is

the Kronecker product of the ...