Brief derivation of the Cooley–Tukey algorithm

In the development of digital information processing are distinguished the emergence of a fast algorithm for the implementation of the discrete Fourier transform (DFT), known as the Fast Fourier Transform (FFT). The description of this famous algorithm appeared in a paper by Cooley and Tukey, and is a flow of concepts from Good’s ideas for the discrete Walsh transform to DFT. The paper gives the final form of the matrix notation of the FFT algorithm for an arbitrary composite order. It is proposed that the algorithm should start with a reverse permutation rather than include a perfect reshuffle in each step of the algorithm. The inverse permutation matrix is presented as a $b$-product of unit matrices (the $b$-product is a new type of tensor product of matrices introduced earlier by the author). The complete derivation of the FFT algorithm is given. The methodical aspect of the article is that it can be used in the educational process, the practical significance is in that the results can be used for software development. The new in the matrix form of FFT is the representation of the $L$ permutation matrix as the $b$-product of the identity matrices. This allows the algorithm to start with a reverse rearrangement, without being distracted by subsequent permutations. In the algorithms which are presented in the Internet FFT permutation in the form of the perfect shuffle offer to do at every step. The program and algorithm of the composite order FFT is based on theorem 1 or its consequences, similar to theorem 2. The flowchart for $N = 16$ was represented earlier.