An extension of one of the fastest existing algorithms for the computation of the two-dimensional (2D) discrete cosine transform (DCT) is presented and a 2D fast cosine transform (FCT) pruning algorithm is derived. The proposed vector-radix FCT algorithm has the same computational complexity as the fastest existing 2D algorithms, but outperforms them in speed of computation, in facilitating VLSI implementation and pruning properties. For the computation of N x N DCT points, the proposed algorithm requires N-2 fewer memory locations and 4N(2) fewer data transfers. For the computation of N-0 x N-0 out of N x N points (N-0 = 2(m0)) by means of the proposed vector-radix FCT pruning algorithm, 3m(0)N(2)/4 multiplications and (2m(0) + 1)N-2 + (m(0) - 3)N-0(2) + 2N(0) additions are required, while the number of memory accesses for the computation of the butterflies is 2m(0)N(2) + 5(N-2 - N-0(2))/3. This reduced total complexity of the proposed algorithm makes it a useful tool for many image coding applications on general and special purpose computer platforms.
展开▼
