A generalized fast algorithm for n-d discrete cosine transform and its application to motion picture coding

In this paper, a generalized fast computational algorithm for the n-dimensional discrete cosine transform (DCT) of length N = 2(m) (m greater than or equal to 2) is presented. The developed algorithm is proved and its efficiency is evaluated theoretically, The theoretical results show that compared with the conventional method of computing the one-dimensional along n directions, the number of multiplications needed by our algorithm is only 1/n of that required by the conventional method; for the total number of additions, the latter is a bit more when N less than or equal to 8 and much fewer when N greater than or equal to 16 than the former. To validate the proposed algorithm, me take the case when n = 3 as an example and apply it to motion-picture coding. The results show that our method is superior to MPEG-2 in speed and coding performance. The algorithm is clearly described and it is easy to make a computer program for implementation.