In this paper, a new algorithm for the fast computation of a 2-D discrete cosine transform (DCT) is presented. It is shown that the N×N DCT, where N = 2m, can be computed using only N 1-D DCT’s and additions, in...In this paper, a new algorithm for the fast computation of a 2-D discrete cosine transform (DCT) is presented. It is shown that the N×N DCT, where N = 2m, can be computed using only N 1-D DCT’s and additions, instead of using 2N 1-D DCT’s as in the conventional row-column approach. Hence the total number of multiplications for the proposed algorithm is only half of that required for the row-column approach, and is also less than that of most of other fast algorithms, while the number of additions is almost comparable to that of others.展开更多
The Fourier transform is very important to numerous applications in science and engineering. However, its usefulness is hampered by its computational expense. In this paper, in an attempt to develop a faster method fo...The Fourier transform is very important to numerous applications in science and engineering. However, its usefulness is hampered by its computational expense. In this paper, in an attempt to develop a faster method for computing Fourier transforms, the authors present parallel implementations of two new algorithms developed for the type IV Discrete Cosine Transform （DCT-IV） which support the new interleaved fast Fourier transform method. The authors discuss the realizations of their implementations using two paradigms. The first involved commodity equipment and the Message-Passing Interface （MPI） library. The second utilized the RapidMind development platform and the Cell Broadband Engine （BE） processor. These experiments indicate that the authors＇ rotation-based algorithm is preferable to their lifting-based algorithm on the platforms tested, with increased efficiency demonstrated by their MPI implementation for large data sets. Finally, the authors outline future work by discussing an architecture-oriented method for computing DCT-IVs which promises further optimization. The results indicate a promising fresh direction in the search for efficient ways to compute Fourier transforms.展开更多
A generalized fast computational algorithm for the n -dimensional discrete cosine transform ( n- D DCT) of length N=2 m(m≥2) is presented. The developed algorithm is theoretically proved and its efficiency is evaluat...A generalized fast computational algorithm for the n -dimensional discrete cosine transform ( n- D DCT) of length N=2 m(m≥2) is presented. The developed algorithm is theoretically proved and its efficiency is evaluated. The theoretical results show that compared with the conventional method to compute the 1-D DCTs in n directions, the number of multiplications needed by this algorithm is only 1/n of that required by the conventional method; for the total number of additions, it is a bit more when N≤8 and much less when N≥16 than the coventional one. To validate the proposed algorithm, the case when n=3 is taken as an example and applied to the motion picture compression. The results show that the proposed method is superior to MPEG-2.展开更多
文摘In this paper, a new algorithm for the fast computation of a 2-D discrete cosine transform (DCT) is presented. It is shown that the N×N DCT, where N = 2m, can be computed using only N 1-D DCT’s and additions, instead of using 2N 1-D DCT’s as in the conventional row-column approach. Hence the total number of multiplications for the proposed algorithm is only half of that required for the row-column approach, and is also less than that of most of other fast algorithms, while the number of additions is almost comparable to that of others.
文摘The Fourier transform is very important to numerous applications in science and engineering. However, its usefulness is hampered by its computational expense. In this paper, in an attempt to develop a faster method for computing Fourier transforms, the authors present parallel implementations of two new algorithms developed for the type IV Discrete Cosine Transform （DCT-IV） which support the new interleaved fast Fourier transform method. The authors discuss the realizations of their implementations using two paradigms. The first involved commodity equipment and the Message-Passing Interface （MPI） library. The second utilized the RapidMind development platform and the Cell Broadband Engine （BE） processor. These experiments indicate that the authors＇ rotation-based algorithm is preferable to their lifting-based algorithm on the platforms tested, with increased efficiency demonstrated by their MPI implementation for large data sets. Finally, the authors outline future work by discussing an architecture-oriented method for computing DCT-IVs which promises further optimization. The results indicate a promising fresh direction in the search for efficient ways to compute Fourier transforms.
文摘A generalized fast computational algorithm for the n -dimensional discrete cosine transform ( n- D DCT) of length N=2 m(m≥2) is presented. The developed algorithm is theoretically proved and its efficiency is evaluated. The theoretical results show that compared with the conventional method to compute the 1-D DCTs in n directions, the number of multiplications needed by this algorithm is only 1/n of that required by the conventional method; for the total number of additions, it is a bit more when N≤8 and much less when N≥16 than the coventional one. To validate the proposed algorithm, the case when n=3 is taken as an example and applied to the motion picture compression. The results show that the proposed method is superior to MPEG-2.
