A fast algorithm for 2-D DCT

Recently, a novel fast algorithm for 2-D N×N DCT (discrete cosine transform), where N=2^m, was proposed. Only half the number of multiplications required for the conventional row-column approach are needed. However, the relationship between the input-output indices for the postaddition stage in the algorithm is seemingly very irregular. In the present work, the authors derive general and systematic expressions for the relation of the postaddition stage in the 2-D DCT algorithm by representing it in matrix form and developing a method for partitioning the matrices. The results show that the signal flow graph from input to output has a recursive structure where the structure for smaller N appears recursively for larger N. Hence, one can obtain an organized and regular structure for the input-output relation in the postaddition stage