The Regularized Fast Hartley Transform

Direct solution to real-data DFT methods are presented in this volume, which are targeted at real-world applications, like mobile communications. The methods discussed offer simple design variations that optimize resources for the best results.

Most real-world spectrum analysis problems involve the computation of the real-data discrete Fourier transform (DFT), a unitary transform that maps elements N of the linear space of real-valued N-tuples, R , to elements of its complex-valued N counterpart, C , and when carried out in hardware it is conventionally achieved via a real-from-complex strategy using a complex-data version of the fast Fourier transform (FFT), the generic name given to the class of fast algorithms used for the ef?cient computation of the DFT. Such algorithms are typically derived by explo- ing the property of symmetry, whether it exists just in the transform kernel or, in certain circumstances, in the input data and/or output data as well. In order to make effective use of a complex-data FFT, however, via the chosen real-from-complex N strategy, the input data to the DFT must ?rst be converted from elements of R to N elements of C . The reason for choosing the computational domain of real-data problems such N N as this to be C , rather than R , is due in part to the fact that computing equ- ment manufacturers have invested so heavily in producing digital signal processing (DSP) devices built around the design of the complex-data fast multiplier and accumulator (MAC), an arithmetic unit ideally suited to the implementation of the complex-data radix-2 butter?y, the computational unit used by the familiar class of recursive radix-2 FFT algorithms.

Describes direct solution to real-data DFT targeted at those real-world applications, such as mobile communications, where resources are limited Achieving computational density of most advanced commercially-available solutions for greatly reduced silicon resources Yielding simple design variations that enable one to optimize use of available silicon resources with resulting designs being: scalable and device-independent Area-efficient with memory requirement reducible to theoretical minimum Includes supplementary material: sn.pub/extras

Klappentext

When designing high-performance DSP systems for implementation with silicon-based computing technology, the oft-encountered problem of the real-data DFT is typically addressed by exploiting an existing complex-data FFT, which can easily result in an overly complex and resource-hungry solution. The research described in The Regularized Fast Hartley Transform: Optimal Formulation of Real-Data Fast Fourier Transform for Silicon-Based Implementation in Resource-Constrained Environments deals with the problem by exploiting directly the real-valued nature of the data and is targeted at those real-world applications, such as mobile communications, where size and power constraints play key roles in the design and implementation of an optimal solution. The Regularized Fast Hartley Transform provides the reader with the tools necessary to both understand the proposed new formulation and to implement simple design variations that offer clear implementational advantages, both practical and theoretical, over more conventional complex-data solutions to the problem. The highly-parallel formulation described is shown to lead to scalable and device-independent solutions to the latency-constrained version of the problem which are able to optimize the use of the available silicon resources, and thus to maximize the achievable computational density, thereby making the solution a genuine advance in the design and implementation of high-performance parallel FFT algorithms.

Inhalt
Background to Research.- Fast Solutions to Real-Data Discrete Fourier Transform.- The Discrete Hartley Transform.- Derivation of the Regularized Fast Hartley Transform.- Algorithm Design for Hardware-Based Computing Technologies.- Derivation of Area-Efficient and Scalable Parallel Architecture.- Design of Arithmetic Unit for Resource-Constrained Solution.- Computation of 2n-Point Real-Data Discrete Fourier Transform.- Applications of Regularized Fast Hartley Transform.- Summary and Conclusions.