The Regularized Fast Hartley Transform
Optimal Formulation of Real-Data Fast Fourier Transform for Silicon-Based Implementation in Resource-Constrained Environments
Published on 19. March 2010
Book
Hardback
XVII, 200 pages
978-90-481-3916-3 (ISBN)
Description
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.
Reviews / Votes
From the reviews:
"The aim of the author is to present a design for a generic double-sized butterfly for use by the fast Hartley transform (FHT) of radix-4 length, which lends itself to parallelization and to mapping onto a regular computational structure for implementation with parallel computing technology. . The textbook is mainly written for students and researchers in engineering and computer science, who are interested in the design and implementation of parallel algorithms for real-data DFT and DHT." (Manfred Tasche, Zentralblatt MATH, Vol. 1191, 2010)More details
Series
Edition
2010
Language
English
Place of publication
Dordrecht
Netherlands
Target group
Professional and scholarly
Professional/practitioner
Illustrations
XVII, 200 p. With online files/update.
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
1150 gr
ISBN-13
978-90-481-3916-3 (9789048139163)
DOI
10.1007/978-90-481-3917-0
Schweitzer Classification
Other editions
New editions
Keith John Jones
The Regularized Fast Hartley Transform
Low-Complexity Parallel Computation of the FHT in One and Multiple Dimensions
Book
09/2021
2nd Edition
Springer
€123.04
Shipment within 7-9 days
Additional editions
Keith Jones
The Regularized Fast Hartley Transform
Optimal Formulation of Real-Data Fast Fourier Transform for Silicon-Based Implementation in Resource-Constrained Environments
Book
05/2012
Springer
€144.44
Shipment within 15-20 days
Keith Jones
The Regularized Fast Hartley Transform
Optimal Formulation of Real-Data Fast Fourier Transform for Silicon-Based Implementation in Resource-Constrained Environments
E-Book
03/2010
1st Edition
Springer
€139.09
Available for download
Content
Preface. Acknowledgements.
1 Background to Research. 1.1 Introduction. 1.2 The DFT and its Efficient Computation. 1.3 Twentieth Century Developments of the FFT. 1.4 The DHT and its Relation to the DFT. 1.5 Attractions of Computing the Real-Data DFT via the FHT. 1.6 Modern Hardware-Based Parallel Computing Technologies. 1.7 Hardware-Based Arithmetic Units. 1.8 Performance Metrics. 1.9 Basic Definitions. 1.10 Organization of the Monograph. 1.11 References.
2 Fast Solutions to Real-Data Discrete Fourier Transform. 2.1 Introduction. 2.2 Real-Data FFT Algorithms. 2.3 Real-From-Complex Strategies. 2.4 Data Re-Ordering. 2.5 Discussion. 2.6 References.
3 The Discrete Hartley Transform. 3.1 Introduction. 3.2 Normalization of DHT Outputs. 3.3 Decomposition into Even and Odd Components. 3.4 Connecting Relations between DFT and DHT. 3.5 Fundamental Theorems for DFT and DHT. 3.6 Fast Solutions to DHT. 3.7 Accuracy Considerations. 3.8 Discussion. 3.9 References.
4 Derivation of the Regularized Fast Hartley Transform. 4.1 Introduction. 4.2 Derivation of the Conventional Radix-4 Butterfly Equations. 4.3 Single-to-Double Conversion of the Radix-4 Butterfly Equations. 4.4 Radix-4 Factorization of the FHT. 4.5 Closed-Form Expression for Generic Radix-4 Double Butterfly. 4.6 Trigonometric Coefficient Storage, Accession and Generation. 4.7 Comparative Complexity Analysis with Existing FFT Designs. 4.8 Scaling Considerations for Fixed-Point Implementation. 4.9 Discussion. 4.10 References.
5 Algorithm Design for Hardware-Based Computing Technologies. 5.1 Introduction. 5.2 The Fundamental Properties of FPGA and ASIC Devices. 5.3 Low-Power Design Techniques. 5.4 Proposed Hardware Design Strategy. 5.5 Constraints on Available Resources. 5.6 Assessing the Resource Requirements. 5.7 Discussion. 5.8 References.
6 Derivation of Area-Efficient and Scalable Parallel Architecture. 6.1 Introduction. 6.2 Single-PE versus Multi-PE Architectures. 6.3 Conflict-Free Parallel Memory Addressing Schemes. 6.4 Design of Pipelined PE for Single-PE Architecture. 6.5 Performance and Requirements Analysis of FPGA Implementation. 6.6 Constraining Latency versus Minimizing Update-Time. 6.7 Discussion. 6.8 References.
7 Design of Arithmetic Unit for Resource-Constrained Solution. 7.1 Introduction. 7.2 Accuracy Considerations. 7.3 Fast Multiplier Approach. 7.4 CORDIC Approach. 7.5 Comparative Analysis of PE Designs. 7.6 Discussion. 7.7 References.
8 Computation of 2n-Point Real-Data Discrete Fourier Transform. 8.1 Introduction. 8.2 Computing One DFT via Two Half-Length Regularized FHTs. 8.3 Computing One DFT via One Double-Length Regularized FHT. 8.4 Discussion. 8.5 References.
9 Applications of Regularized Fast Hartley Transform. 9.1 Introduction. 9.2 Fast Transform-Space Convolution and Correlation. 9.3 Up-Sampling and Differentiation of Real-Valued Signal. 9.4 Correlation of Two Arbitrary Signals. 9.5 Channelization of Real-Valued Signal. 9.6 Discussion. 9.7 References.
10 Summary and Conclusions. 10.1 Outline of Problem Addressed. 10.2 Summary of Results. 10.3 Conclusions.
Appendix A - Computer Program for Regularized Fast Hartley Transform. A.1 Introduction. A.2 Description of Functions. A.3 Brief Guide to Running the Program. A.4 Available Scaling Strategies.
Appendix B - Source Code Listings for Regularized Fast Hartley Transform. B.1 Listings for Main Program and Signal Generation Routine. B.2 Listings for Pre-Processing Functions. B.3 Listings for Processing Functions.
Glossary. Index.