The Regularized Fast Hartley Transform : Low-Complexity Parallel Computation of the FHT in One and Multiple Dimensions

• Autore: Jones Keith John
• Pubblicazione: Cham : , : Springer International Publishing AG, , 2021; ©2022
• Edizione: 2nd ed.
• Descrizione fisica: 1 online resource (325 pages)
• Soggetto genere / forma: Electronic books.
• Nota di contenuto: Intro -- Preface -- Audience -- Acknowledgements -- Contents -- About the Author -- Part I: The Discrete Fourier and Hartley Transforms -- Chapter 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 and Constraints -- 1.9 Key Parameters, Definitions and Notation -- 1.10 Organization of Monograph -- References -- Chapter 2: The Real-Data Discrete Fourier Transform -- 2.1 Introduction -- 2.2 Real-Data FFT Algorithms -- 2.2.1 The Bergland Algorithm -- 2.2.2 The Bruun Algorithm -- 2.3 Real-From-Complex Strategies -- 2.3.1 Computation of Real-Data DFT via Complex-Data FFT -- 2.3.2 Computation of Two Real-Data DFTs via Complex-Data FFT -- 2.3.3 Computation of Real-Data DFT via Half-Length Complex-Data FFT -- 2.4 Data Reordering -- 2.5 Discussion -- References -- Chapter 3: The Discrete Hartley Transform -- 3.1 Introduction -- 3.2 Orthogonality of DHT -- 3.3 Decomposition into Even and Odd Components -- 3.4 Connecting Relations Between DFT and DHT -- 3.4.1 Real-Data DFT -- 3.4.2 Complex-Data DFT -- 3.5 Fundamental Theorems for DFT and DHT -- 3.5.1 Reversal Theorem -- 3.5.2 Addition Theorem -- 3.5.3 Shift Theorem -- 3.5.4 Convolution Theorem -- 3.5.5 Product Theorem -- 3.5.6 Autocorrelation Theorem -- 3.5.7 First Derivative Theorem -- 3.5.8 Second Derivative Theorem -- 3.5.9 Summary of Theorems and Related Properties -- 3.6 Fast Solutions to DHT - The FHT Algorithm -- 3.7 Accuracy Considerations -- 3.8 Discussion -- References -- Part II: The Regularized Fast Hartley Transform. ; Chapter 4: Derivation of Regularized Formulation of Fast Hartley Transform -- 4.1 Introduction -- 4.2 Derivation of the Conventional Radix-4 Butterfly Equations -- 4.3 Single-to-Double Conversion of Radix-4 Butterfly Equations -- 4.4 Radix-4 Factorization of the FHT -- 4.5 Closed-Form Expression for Generic Radix-4 Double Butterfly -- 4.5.1 Twelve-Multiplier Version of Generic Double Butterfly -- 4.5.2 Nine-Multiplier Version of Generic Double Butterfly -- 4.6 Trigonometric Coefficient Storage, Retrieval and Generation -- 4.6.1 Minimum-Arithmetic Addressing Scheme -- 4.6.2 Minimum-Memory Addressing Scheme -- 4.6.3 Trigonometric Coefficient Generation via Trigonometric Identities -- 4.7 Comparative Complexity Analysis with Existing FFT Designs -- 4.8 Scaling Considerations for Fixed-Point Implementation -- 4.9 Discussion -- References -- Chapter 5: Design Strategy for Silicon-Based Implementation of Regularized Fast Hartley Transform -- 5.1 Introduction -- 5.2 The Fundamental Properties of FPGA and ASIC Devices -- 5.3 Low-Power Design Techniques -- 5.3.1 Clock Frequency -- 5.3.2 Silicon Area -- 5.3.3 Switching Frequency -- 5.4 Proposed Hardware Design Strategy -- 5.4.1 Scalability of Design -- 5.4.2 Partitioned-Memory Processing -- 5.4.3 Flexibility of Design -- 5.5 Constraints on Available Resources -- 5.6 Assessing the Resource Requirements -- 5.7 Discussion -- References -- Chapter 6: Architecture for Silicon-Based Implementation of Regularized Fast Hartley Transform -- 6.1 Introduction -- 6.2 Single-PE Versus Multi-PE Architectures -- 6.3 Conflict-Free Parallel Memory Addressing Schemes -- 6.3.1 Parallel Storage and Retrieval of Data -- 6.3.2 Parallel Storage, Retrieval and Generation of Trigonometric Coefficients -- 6.3.2.1 Minimum-Arithmetic Addressing Scheme -- 6.3.2.2 Minimum-Memory Addressing Scheme. ; 6.3.2.3 Comparative Analysis of Addressing Schemes -- 6.4 Design of Pipelined PE for Single-PE Recursive Architecture -- 6.4.1 Parallel Computation of Generic Double Butterfly -- 6.4.2 Space-Complexity Considerations -- 6.4.3 Time-Complexity Considerations -- 6.5 Performance and Requirements Analysis of FPGA Implementation -- 6.6 Derivation of Range of Validity for Regularized FHT -- 6.7 Discussion -- References -- Chapter 7: Design of CORDIC-Based Processing Element for Regularized Fast Hartley Transform -- 7.1 Introduction -- 7.2 Accuracy Considerations -- 7.3 Fast Multiplier Approach -- 7.4 CORDIC Arithmetic Approach -- 7.4.1 CORDIC Formulation of Complex Multiplier -- 7.4.2 Parallel Formulation of CORDIC-Based PE -- 7.4.3 Discussion of CORDIC-Based Solution -- 7.4.4 Logic Requirement of CORDIC-Based PE -- 7.5 Comparative Analysis of PE Designs -- 7.6 Discussion -- References -- Part III: Applications of Regularized Fast Hartley Transform -- Chapter 8: Derivation of Radix-2 Real-Data Fast Fourier Transform Algorithms Using Regularized Fast Hartley Transform -- 8.1 Introduction -- 8.2 Computation of Real-Data DFT via Two Half-Length Regularized FHTs -- 8.2.1 Derivation of Radix-2 Algorithm via Double-Resolution Approach -- 8.2.2 Implementation of Double-Resolution Algorithm -- 8.2.2.1 Single-FHT Solution for Computation of Regularized FHTs -- 8.2.2.2 Two-FHT Solution for Computation of Regularized FHTs -- 8.2.2.3 Comparative Analysis of Solutions -- 8.3 Computation of Real-Data DFT via One Double-Length Regularized FHT -- 8.3.1 Derivation of Radix-2 Algorithm via Half-Resolution Approach -- 8.3.2 Implementation of Half-Resolution Algorithm -- 8.4 Comparative Complexity Analysis with Standard Radix-2 FFT -- 8.5 Discussion -- References -- Chapter 9: Computation of Common DSP-Based Functions Using 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.3.1 Up-Sampling via Hartley-Space -- 9.3.2 Differentiation via Hartley-Space -- 9.3.3 Combined Up-Sampling and Differentiation -- 9.4 Correlation of Two Arbitrary Signals -- 9.4.1 Computation of Complex-Data Correlation via Real-Data Correlation -- 9.4.2 Cross-Correlation of Two Finite-Length Data Sets -- 9.4.3 Auto-Correlation: Finite-Length Against Infinite-Length Data Sets -- 9.4.4 Cross-Correlation: Infinite-Length Against Infinite-Length Data Sets -- 9.4.5 Combining Functions in Hartley-Space -- 9.5 Channelization of Real-Valued Signal -- 9.5.1 Single Channel: Fast Hartley-Space Convolution -- 9.5.2 Multiple Channels: Conventional Polyphase DFT Filter Bank -- 9.5.2.1 Alias-Free Formulation -- 9.5.2.2 Implementation Issues -- 9.6 Distortion-Free Multi-Carrier Communications -- 9.7 Discussion -- References -- Part IV: The Multi-dimensional Discrete Hartley Transform -- Chapter 10: Parallel Reordering and Transfer of Data Between Partitioned Memories of Discrete Hartley Transform for 1-D and m-... -- 10.1 Introduction -- 10.2 Memory Mappings of Regularized FHT -- 10.3 Requirements for Parallel Reordering and Transfer of Data -- 10.4 Sequential Construction of Reordered Data Sets -- 10.5 Parallelization of Data Set Construction Process -- 10.6 Parallel Transfer of Reordered Data Sets -- 10.7 Discussion -- References -- Chapter 11: Architectures for Silicon-Based Implementation of m-D Discrete Hartley Transform Using Regularized Fast Hartley Tr... -- 11.1 Introduction -- 11.2 Separable Version of 2-D DHT -- 11.2.1 Two-Stage Formulation of 2-D SDHT -- 11.2.2 Hartley-Space Filtering of 2-D Data Sets -- 11.2.3 Relationship Between 2-D SDHT and 2-D DFT -- 11.3 Architectures for 2-D SDHT. ; 11.3.1 Single-FHT Recursive Architecture -- 11.3.2 Two-FHT Pipelined Architecture -- 11.3.3 Relative Merits of Proposed Architectures -- 11.4 Complexity Analysis of 2-D SDHT -- 11.4.1 Complexity Summary for Regularized FHT -- 11.4.2 Space-Complexity of 2-D Solutions -- 11.4.3 Time-Complexity of 2-D Solutions -- 11.4.4 Computational Density of 2-D Solutions -- 11.4.5 Comparative Complexity of 2-D Solutions -- 11.4.6 Relative Start-up Delays and Update Times of 2-D Solutions -- 11.4.7 Application of 2-D SDHT to Filtering of 2-D Data Sets -- 11.4.8 Application of 2-D SDHT to Computation of 2-D Real-Data DFT -- 11.5 Generalization of 2-D Solutions to Processing of m-D Data Sets -- 11.5.1 Space and Time Complexities of m-D Solutions -- 11.5.2 Comparative Complexity of M-D Solutions -- 11.5.3 Relative Start-up Delays and Update Times of m-D Solutions -- 11.6 Constraints on Achieving and Maintaining Real-Time Operation -- 11.7 Discussion -- References -- Part V: Results of Research -- Chapter 12: Summary and Conclusions -- 12.1 Outline of Problems Addressed -- 12.2 Summary of Results -- 12.3 Conclusions -- References -- Appendix A: Computer Programme for Regularized Fast Hartley Transform -- A.1 Introduction -- A.2 Description of Functions -- A.2.1 Control Routine -- A.2.2 Generic Double Butterfly Routines -- A.2.3 Address Generation and Data Reordering Routines -- A.2.4 Data Memory Retrieval and Updating Routine -- A.2.5 Trigonometric Coefficient Generation Routines -- A.2.6 Look-Up Table Generation Routines -- A.2.7 FHT-to-FFT Conversion Routine -- A.3 Brief Guide to Running the Programme -- A.4 Available Scaling Strategies -- Appendix B: Source Code for Regularized Fast Hartley Transform -- B.1 Listings for Main Programme and Signal Generation Routine -- B.2 Listings for Preprocessing Functions -- B.3 Listings for Processing Functions. ; Appendix C: MATLAB Code for Parallel Reordering of Data via Dibit-Reversal Mapping.
• Altri titoli varianti: Regularized Fast Hartley Transform
• Titolo autorizzato: The Regularized Fast Hartley Transform
• ISBN: 3-030-68245-5
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910497086503321
• Lo trovi qui: Univ. Federico II