A generalized fast algorithm for n-D discrete cosine transform andits application to motion picture coding

摘要

In this paper, a generalized fast computational algorithm for thenn-dimensional discrete cosine transform (DCT) of length N=2mn(m⩾2) is presented. The developed algorithm is proved and itsnefficiency is evaluated theoretically. The theoretical results show thatncompared with the conventional method of computing the one-dimensionalnalong n directions, the number of multiplications needed by ournalgorithm is only 1 of that required by the conventional method; fornthe total number of additions, the latter is a bit more when N⩽8 andnmuch fewer when N⩾16 than the former. To validate the proposednalgorithm, we take the case when n=3 as an example and apply it tonmotion-picture coding. The results show that our method is superior tonMPEG-2 in speed and coding performance. The algorithm is clearlyndescribed and it is easy to make a computer program for implementation