The Regularized Fast Hartley Transform

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.