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.     

Fast computation of discrete Hartley transform via Walsh?Hadamard transform

A new fast algorithm is proposed to compute the discrete Hartley transform (DHT) via the Walsh?Hadamard transform (WHT). The processing is carried out on an interframe basis in (N × N) data blocks, where N is an integer power of two. The WHT coefficients are obtained directly, and then used to obtain the DHT coefficients. This is achieved by a transform matrix, the H-transform matrix, which is ortho-normal and has a block-diagonal structure. A complete derivation of the block-diagonal structure for the H-transform matrix is given.     

Fast radix-3/9 discrete Hartley transform

An efficient algorithm for computing radix-3/9 discrete Hartley transforms (DHTs) is presented. It is shown that the radix-3/9 fast Hartley transform (FHT) algorithm reduces the number of multiplications required by a radix-3 FHT algorithm for nearly 50%. For the computation of real-valued discrete Fourier transforms (DFTs) with sequence lengths that are powers of 3, it is shown that the radix-3/9 FHT algorithm reduces the number of multiplications by 16.2% over the fastest real-valued radix-3/9 fast Fourier transform (FFT) algorithm     

Fast algorithm for pseudodiscrete Wigner-Ville distribution usingmoving discrete Hartley transform

A new fast algorithm is proposed to compute pseudodiscrete Wigner-Ville distribution (PDWVD) in real-time applications. The proposed algorithm uses the moving discrete Hartley transform to compute the Hilbert transform and thereby implements the PDWVD in real domain. The computational complexity of the proposed algorithm is derived and compared with the existing algorithm to compute the PDWVD     

Fast Hartley transform algorithm

The discrete Hartley transform is a new tool for the analysis, design and implementation of digital signal processing algorithms and systems. It is strictly symmetrical concerning the transformation and its inverse. A new fast Hartley transform algorithm has been developed. Applied to real signals, it is faster than a real fast Fourier transform, especially in the case of the inverse transformation. The speed of operation for a fast convolution can thus be increased.     

Fast two-dimensional Hartley transform

The fast Hartley transform algorithm introduced in 1984 offers an alternative to the fast Fourier transform, with the advantages of not requiring complex arithmetic or a sign change of i to distinguish inverse transformation from direct. A two-dimensional extension is described that speeds up Fourier transformation of real digital images.     

Fast computation of the discrete Fourier transform of real data

Fast algorithms for the computation of the discrete Fourier transform (DFT) of real signals are important since the signals in practical situations are mostly real. The more efficient algorithms for real data are those that are derived from the algorithms for complex data. So far, all such algorithms use a real array to store the data. However, as the data values are real and their transform values are mostly complex, two possible data structures can be used for these algorithms: real or complex. DFT algorithms for real data that use a complex array for storing both the real data and their transform values are derived from the Cooley-Tukey radix-2 algorithm for complex data. This approach reduces the number of bit-reversal and array-index updating operations, eliminates independent data-swapping operations, and yields a computational structure that is almost as regular as that of the algorithms for complex data. Detailed derivations of the proposed algorithms for the computation of both the DFT of real data and the inverse DFT of the transform of real data, as well as their computational complexities, are presented. A C-language program of one of the proposed algorithms is given, illustrating the use of all the features of the new approach in software implementation. Comparison results are included to show that the proposed algorithms are faster and simpler than the real-valued split-radix and other algorithms     

Computation of 2D discrete Hartley transform

Based on a decimation-in-time decomposition, a fast split-radix algorithm for the 2D discrete Hartley transform is presented. Compared to other reported algorithms, the proposed algorithm achieves substantial savings on the number of operations and provides a wider choice of transform sizes     

基于离散Hartley变换的OFDM实现模型

本文研究离散Hartley变换在OFDM系统中的应用,提出一种基于离散Hartley变换的OFDM实现模型.分析了新模型在加性高斯白噪声信道下的传输性能和算法复杂度.新模型与基于离散傅立叶变换(DFT)的OFDM系统具有相同的传输性能,但计算复杂度降低,时效性提高,且调制与解调算法一致.     

Systolic arrays for the discrete Hartley transform

Recently, R.N. Bracewell (1983) introduced the discrete Hartley transform (DHT) as an alternative to the discrete Fourier transform (DFT). Two linear systolic array models for the (DHT) are derived. One model requires O(2N-1) in the computational phase and O(N) in the preloading phase. The other model requires O(2N-1) in the computational phase and O(N) in the output phase. A square systolic array for two-dimensional DHT is also constructed by combining the individual advantages of each model. The CORDIC algorithm is proposed as an alternative to conventional multipliers. To speed up the systolic array, two-level pipelining with CORDIC is also possible     

Prime-factor algorithms for generalised discrete Hartley transform

A prime factor fast algorithm for the type-II generalised discrete Hartley transform is presented. In addition to reducing the number of arithmetic operations and achieving a regular computational structure, a simple index mapping method is proposed to minimise the overall implementation complexity     

Fast interpolation algorithm using fast Hartley transform

The use of fast Hartley transform for fast discrete interpolation is considered. The computational method uses the sprit-radix algorithm which requires the least number of operations compared with other Hartley algorithms. Results from this method are compared with those using the fast Fourier transform.     

Design and parallel computation of regularised fast Hartley transform

The paper describes the design and parallel computation of a regularised fast Hartley transform (FHT), to be used for computation of the discrete Fourier transform (DFT) of real-valued data. For the processing of such data, the FHT has attractions over the fast Fourier transform (FFT) in terms of reduced arithmetic operation counts and reduced memory requirement, whilst its bilateral property means it may be straightforwardly applied to both forward and inverse DFTs. A drawback, however, of conventional FHT algorithms lies in the loss of regularity arising from the need for two sizes of 'butterfly' for efficient fixed-radix implementations. A generic double butterfly is therefore developed for the radix-4 FHT which overcomes the problem in an elegant fashion. The result is a recursive single-butterfly solution, referred to as the regularised FHT, which lends itself naturally to parallelisation and to mapping onto a regular computational structure for implementation with algorithmically specialised hardware.     

New split-radix algorithm for the discrete Hartley transform

This paper presents a split-radix algorithm that can flexibly compute the discrete Hartley transforms of various sequence lengths. Comparisons with previously reported algorithms are made in terms of the required number of additions and multiplications. It shows that the length-3*2^m DHTs need a smaller number of multiplications than the length-2^m DHTs. However, they both require about the same computational complexity in terms of the total number of additions and multiplications. Optimized computation of length-12, -16 and -24 DFTs are also provided     

Comments on "Generalized discrete Hartley transform"

The author comments on the paper by Hu et al. (IEEE Trans. Signal Processing, vol.40, no.12, p.2951-60, 1992). Information is provided about prior published work that precedes the transforms and convolution procedures defined in the above paper.<>     

Split radix algorithm for the discrete Hartley transform

A new split radix fast algorithm for the discrete Hartley transform is presented. Comparisons with other reported algorithms are made in terms of the number of additions and multiplications. The algorithm is also simple and straightforward and can be easily implemented     

New fast algorithm to compute two-dimensional discrete Hartley transform

A new fast algorithm for computing the two-dimensional discrete Hartley transform is presented. This algorithm requires the lowest number of multiplications compared with other related algorithms.<>     

On prime factor mapping for the discrete Hartley transform

The authors propose a new prime factor mapping scheme, which requires no extra arithmetic operations for the realization of prime factor mapping, for the computation of the discrete Hartley transform (DHT). It is achieved by embedding all the extra arithmetic operations into the subsequent short-length computations, with the computational complexities of these embedded short lengths remaining unchanged. Consequently, the present approach significantly eliminates the burden which is introduced by the extra arithmetic operations. With this mapping scheme, it is further demonstrated that a prime-factor-mapped DHT would have superb performance compared with other fast DHT algorithms     

Vector-radix algorithm for a 2-D discrete Hartley transform

A new multidimensional Hartley transform is defined and a vector-radix algorithm for fast computation of the transform is developed. The algorithm is shown to be faster (in terms of multiplication and addition count) compared to other related algorithms.     

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.