Fast cosine transform of Toeplitz matrices, algorithm andapplications

A fast algorithm for the discrete cosine transform (DCT) of a Toeplitz matrix of order N is derived. Only O(N log N)+O(M) time is needed for the computation of M elements. The storage requirement is O(N). The method carries over to other transforms (DFT, DST) and to Hankel or circulant matrices. Some applications of the algorithm are discussed     

Algorithm for wavelet transform of Toeplitz matrices

An algorithm is presented for calculating the 2D wavelet transform of a Toeplitz matrix. The algorithm exploits the special form of the Toeplitz matrix in order to reduce the number of operations required. More specifically. It is shown that the number of 1D wavelet transformations that are necessary to carry out a sub-band decomposition can be reduced to eight     

Mixed-radix discrete cosine transform

Presents two new fast discrete cosine transform computation algorithms: a radix-3 and a radix-6 algorithm. These two new algorithms are superior to the conventional radix-3 algorithm as they (i) require less computational complexity in terms of the number of multiplications per point, (ii) provide a wider choice of the sequence length for which the DCT can be realized and, (iii) support the prime factor-decomposed computation algorithm to realize the 2^m3ⁿ-point DCT. Furthermore, a mixed-radix algorithm is also proposed such that an optimal performance can be achieved by applying the proposed radix-3 and radix-6 and the well-developed radix-2 decomposition techniques in a proper sequence     

Fast algorithm for computing discrete cosine transform

An efficient method for computing the discrete cosine transform (DCT) is proposed. Based on direct decomposition of the DCT, the recursive properties of the DCT for an even length input sequence is derived, which is a generalization of the radix 2 DCT algorithm. Based on the recursive property, a new DCT algorithm for an even length sequence is obtained. The proposed algorithm is very structural and requires fewer computations when compared with others. The regular structure of the proposed algorithm is suitable for fast parallel algorithm and VLSI implementation     

Simple systolic arrays for discrete cosine transform

in this paper, simple 1-D and 2-D systolic array for realizing the discrete cosine transform (DCT) based on the discrete Fourier transform (DFT) fo an input sequence are presented. The proposed arrays are obtained by a simple modified DFT (MDFT) and an inverse DFT (IDFT) version of the Goertzel algorithm combined with Kung's approach. The 1-D array requiresN cells, one multiplier and takesN clock cycles to produce a completeN-point DCT. The 2-D array takes N clock cycles, faster than the 1-D array, but the area complexity is larger. A continuous flow of input data is allowed and no idle time is required between the input sequences.     

Fast algorithms for the discrete cosine transform

Several fast algorithms for computing discrete cosine transforms (DCTs) and their inverses on multidimensional inputs of sizes which are powers of 2 are introduced. Because the 1-D 8-point DCT and the 2-D 8×8-point DCT are so widely used, they are discussed in detail. Algorithms for computing scaled DCTs and their inverses are also presented. These have applications in compression of continuous tone image data, where the DCT is generally followed by scaling and quantization     

A derivation for the discrete cosine transform

The purpose of this letter is to derive the discrete cosine transform (DCT) as a limiting case of the Karhunen-Loève transform (KLT) of a first-order Markov process, as the correlation coefficient approaches 1.     

The fractional discrete cosine transform

The extension of the Fourier transform operator to a fractional power has received much attention in signal theory and is finding attractive applications. The paper introduces and develops the fractional discrete cosine transform (DCT) on the same lines, discussing multiplicity and computational aspects. Similarities and differences with respect to the fractional Fourier transform are pointed out     

An algorithm for calculation of the discrete cosine transform by paired transform

A new algorithm for splitting the one-dimensional (1-D) 2/sup r/-point discrete cosine transform (DCT) into a set of short 2/sup k/-point type-IV DCTs [k=1:(r-1)] is introduced. The splitting is performed by means of paired transformation that is defined by the paired representation of signals with respect to the cosine transform. A proposed method of calculating the 2/sup r/-point cosine transform requires 2/sup r-1/r multiplications and 2/sup r-1/(3r-2)+1 additions when r/spl ges/2.     

Fast discrete cosine transform algorithm for systolic arrays

A fast algorithm for an N-point discrete cosine transform (DCT) is derived from a 4N-point Winograd Fourier transform algorithm (WFTA). This algorithm, which has the same form as Winograd's Fourier transform and convolution algorithms, is suitable for a high-speed implementation using one-bit systolic arrays.     

Efficient index mapping for computing discrete cosine transform

An efficient algorithm for computing the discrete cosine transform (DCT) is presented. It is based on an index mapping which converts an odd-length DCT to a real-valued DFT of the same length using permutations and sign changes only. The real-valued DFT can then be computed by efficient real-valued FFT algorithms such as the prime factor algorithm. The algorithm is more efficient than an earlier one because no postmultiplications are required.<>     

Fast recursive algorithms for short-time discrete cosine transform

Local adaptive signal processing can be carried out using the short-time discrete cosine transform (DCT). Two fast recursive algorithms for computing the short-time DCT are presented. The algorithms are based on a recursive relationship between three subsequent local DCT spectra. The computational complexity of the algorithms is compared with that of fast DCT algorithms     

Relationship between two algorithms for discrete cosine transform

Two contributions are made to the implementation of fast discrete cosine transform algorithms. The first uses Hadamard ordering to improve the regularity of the Lee fast cosine transform (FCT) algorithm for the discrete cosine transform (DCT). The second derives a close relationship between the Lee FCT and the recursive algorithm for the DCT.<>     

Pruning the fast discrete cosine transform

The matrix representation of the simple structured algorithm for the discrete cosine transform (DCT), which was first introduced by Y. Morikawa et al. (1985) based on the successive order reduction of the Tchebycheff polynomial, and retrieved by a simpler approach by Z. Wang (1988), is reviewed. A fast pruning algorithm for the DCT is then developed     

Fast odd discrete cosine transform algorithms

It is shown that an N point type I odd discrete cosine transform can be reformulated as a (2N-1) point DFT of a real-symmetric sequence efficiently computed by the real-symmetric PFA-FFT. Using simple index mappings, the type II and III ODCTs are efficiently computed from the ODCT-1 of the same length. The ODCT-IV are then computed from ODCT-II or III using simple recurrence formulas.<>     

An order-16 integer cosine transform

It is shown that it is possible to replace the real-numbered elements of a discrete cosine transform (DCT) matrix with integers and still maintain the structure, i.e., relative magnitudes and orthogonality, among the matrix elements. The result is an integer cosine transform (ICT). Thirteen ICTs have been found, and some of them have performance comparable to the DCT. The main advantage of the ICT lies in having only integer values, which in two cases can be represented perfectly by 6-bit numbers, thus providing a potential reduction in the computational complexity     

On the discrete cosine transform computation

A generalized signal flow graph for the forward and inverse discrete cosine transform (DCT) based on the Hou's recursive algorithm is described. The regular structure of the generalized signal flow graph enables to realize the DCT and inverse DCT computation for any given N = 2^m, m > 0, and is effectively implementable on a VLSI chip. Computer program for the DCT and inverse DCT computation is also presented.     

Signal reconstruction from cosine transform magnitude

In this letter, we prove that any real, causal, and finite-duration sequence can be reconstructed from samples of its cosine transform magnitude. In addition, a simple numerical algorithm is developed for the signal reconstruction.     

Fast computation of discrete cosine transform through fast Hartley transform

A relationship between the discrete cosine transform (DCT) and the discrete Hartley transform (DHT) is derived. It leads to a new fast and numerically stable algorithm for the DCT.     

Computationally efficient discrete cosine transform algorithm

An algorithm is developed for evaluating the discrete cosine transform using DFT and polynomial transforms. It is shown to be computationally more efficient than existing algorithms.