دانلود کتاب The Regularized Fast Hartley Transform: Low-Complexity Parallel Computation of the FHT in One and Multiple Dimensions

فهرست مطالب :

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
C.1 Listing for MATLAB Data Reordering Program
C.2 Discussion
Glossary
Index