Multidimensional vector radix FHT algorithms

In this paper, efficient multidimensional (M-D) vector radix (VR) decimation-in-frequency and decimation-in-time fast Hartley transform (FHT) algorithms are derived for computing the discrete Hartley transform (DHT) of any dimension using an appropriate index mapping and the Kronecker product. The proposed algorithms are more effective and highly suitable for hardware and software implementations compared to all existing M-D FHT algorithms that are derived for the computation of the DHT of any dimension. The butterflies of the proposed algorithms are based on simple closed-form expressions that allow easy implementations of these algorithms for any dimension. In addition, the proposed algorithms possess properties such as high regularity, simplicity and in-place computation that are highly desirable for software and hardware implementations, especially for the M-D applications. A close relationship between the M-D VR complex-valued fast Fourier transform algorithms and the proposed M-D VR FHT algorithms is established. This type of relationship is of great significance for software and hardware implementations of the algorithms, since it is shown that because of this relationship and the fact that the DHT is an alternative to the discrete Fourier transform (DFT) for real data, a single module with a little or no modification can be used to carry out the forward and inverse M-D DFTs for real- or complex-valued data and M-D DHTs. Thus, the same module (with a little or no modification) can be used to cover all domains of applications that involve the DFTs or DHTs.     

New radix-(2/spl times/2/spl times/2)/(4/spl times/4/spl times/4) and radix-(2/spl times/2/spl times/2)/(8/spl times/8/spl times/8) DIF FFT algorithms for 3-D DFT

In this paper, new three-dimensional (3-D) radix-(2/spl times/2/spl times/2)/(4/spl times/4/spl times/4) and radix-(2/spl times/2/spl times/2)/(8/spl times/8/spl times/8) decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithms are developed and their implementation schemes discussed. The algorithms are developed by introducing the radix-2/4 and radix-2/8 approaches in the computation of the 3-D DFT using the Kronecker product and appropriate index mappings. The butterflies of the proposed algorithms are characterized by simple closed-form expressions facilitating easy software or hardware implementations of the algorithms. Comparisons between the proposed algorithms and the existing 3-D radix-(2/spl times/2/spl times/2) FFT algorithm are carried out showing that significant savings in terms of the number of arithmetic operations, data transfers, and twiddle factor evaluations or accesses to the lookup table can be achieved using the radix-(2/spl times/2/spl times/2)/(4/spl times/4/spl times/4) DIF FFT algorithm over the radix-(2/spl times/2/spl times/2) FFT algorithm. It is also established that further savings can be achieved by using the radix-(2/spl times/2/spl times/2)/(8/spl times/8/spl times/8) DIF FFT algorithm.     

A new radix-2/8 FFT algorithm for length-q/spl times/2/sup m/ DFTs

In this paper, a new radix-2/8 fast Fourier transform (FFT) algorithm is proposed for computing the discrete Fourier transform of an arbitrary length N=q/spl times/2/sup m/, where q is an odd integer. It reduces substantially the operations such as data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of FFT algorithms. It is shown that the arithmetic complexity (multiplications+additions) of the proposed algorithm is, in most cases, the same as that of the existing split-radix FFT algorithm. The basic idea behind the proposed algorithm is the use of a mixture of radix-2 and radix-8 index maps. The algorithm is expressed in a simple matrix form, thereby facilitating an easy implementation of the algorithm, and allowing for an extension to the multidimensional case. For the structural complexity, the important properties of the Cooley-Tukey approach such as the use of the butterfly scheme and in-place computation are preserved by the proposed algorithm.     

A new split-radix FHT algorithm for length-q*2/sup m/DHTs

In this paper, a new split-radix fast Hartley transform (FHT) algorithm is proposed for computing the discrete Hartley transform (DHT) of an arbitrary length N=q*2/sup m/, where q is an odd integer. The basic idea behind the proposed FHT algorithm is that a mixture of radix-2 and radix-8 index maps is used in the decomposition of the DHT. This idea and the use of an efficient indexing process lead to a new decomposition different from that of the existing split-radix FHT algorithms, since the existing ones are all based on the use of a mixture of radix-2 and radix-4 index maps. The proposed algorithm reduces substantially the operations such as data transfer, address generation, and twiddle factor evaluation or access to the lookup table, which contribute significantly to the execution time of FHT algorithms. It is shown that the arithmetic complexity (multiplications+additions) of the proposed algorithm is, in almost all cases, the same as that of the existing split-radix FHT algorithm for length- q*2/sup m/ DHTs. Since the proposed algorithm is expressed in a simple matrix form, it facilitates an easy implementation of the algorithm, and allows for an extension to the multidimensional case.