The Regularized Fast Hartley Transform: Optimal Formulation of Real-Data Fast Fourier Transform for Silicon-Based Implementation in Resourc by Keith JonesThe Regularized Fast Hartley Transform: Optimal Formulation of Real-Data Fast Fourier Transform for Silicon-Based Implementation in Resourc by Keith Jones

The Regularized Fast Hartley Transform: Optimal Formulation of Real-Data Fast Fourier Transform for…

byKeith Jones

Paperback | May 5, 2012

Pricing and Purchase Info

$218.22 online 
$260.95 list price save 16%
Earn 1,091 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


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.
Title:The Regularized Fast Hartley Transform: Optimal Formulation of Real-Data Fast Fourier Transform for…Format:PaperbackDimensions:200 pagesPublished:May 5, 2012Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:9400731787

ISBN - 13:9789400731783


Table of Contents

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.

Editorial Reviews

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)