Regularized Fast Hartley Transform (eBook)
XVII, 200 Seiten
Springer Netherlands (Verlag)
978-90-481-3917-0 (ISBN)
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.
Preface 5
Contents 9
1 Background to Research 15
1.1 Introduction 15
1.2 The DFT and Its Efficient Computation 16
1.3 Twentieth Century Developments of the FFT 18
1.4 The DHT and Its Relation to the DFT 20
1.5 Attractions of Computing the Real-Data DFT via the FHT 21
1.6 Modern Hardware-Based Parallel Computing Technologies 22
1.7 Hardware-Based Arithmetic Units 23
1.8 Performance Metrics 24
1.9 Basic Definitions 25
1.10 Organization of the Monograph 26
References 27
2 Fast Solutions to Real-Data Discrete Fourier Transform 29
2.1 Introduction 29
2.2 Real-Data FFT Algorithms 30
2.2.1 The Bergland Algorithm 30
2.2.2 The Brunn Algorithm 32
2.3 Real-From-Complex Strategies 33
2.3.1 Computing One Real-Data DFT via One Full-Length Complex-Data FFT 34
2.3.2 Computing Two Real-Data DFTs via One Full-Length Complex-Data FFT 34
2.3.3 Computing One Real-Data DFT via One Half-Length Complex-Data FFT 36
2.4 Data Re-ordering 37
2.5 Discussion 38
References 39
3 The Discrete Hartley Transform 40
3.1 Introduction 40
3.2 Normalization of DHT Outputs 41
3.3 Decomposition into Even and Odd Components 42
3.4 Connecting Relations Between DFT and DHT 42
3.4.1 Real-Data DFT 43
3.4.2 Complex-Data DFT 43
3.5 Fundamental Theorems for DFT and DHT 44
3.5.1 Reversal Theorem 45
3.5.2 Addition Theorem 46
3.5.3 Shift Theorem 47
3.5.4 Convolution Theorem 47
3.5.5 Product Theorem 48
3.5.6 Autocorrelation Theorem 48
3.5.7 First Derivative Theorem 48
3.5.8 Second Derivative Theorem 49
3.5.9 Summary of Theorems 49
3.6 Fast Solutions to DHT 50
3.7 Accuracy Considerations 52
3.8 Discussion 52
References 53
4 Derivation of the Regularized Fast Hartley Transform 54
4.1 Introduction 54
4.2 Derivation of the Conventional Radix-4 Butterfly Equations 55
4.3 Single-to-Double Conversion of the Radix-4 Butterfly Equations 58
4.4 Radix-4 Factorization of the FHT 59
4.5 Closed-Form Expression for Generic Radix-4 Double Butterfly 61
4.5.1 Twelve-Multiplier Version of Generic Double Butterfly 67
4.5.2 Nine-Multiplier Version of Generic Double Butterfly 67
4.6 Trigonometric Coefficient Storage, Accession and Generation 69
4.6.1 Minimum-Arithmetic Addressing Scheme 70
4.6.2 Minimum-Memory Addressing Scheme 70
4.6.3 Trigonometric Coefficient Generation via Trigonometric Identities 71
4.7 Comparative Complexity Analysis with Existing FFT Designs 72
4.8 Scaling Considerations for Fixed-Point Implementation 74
4.9 Discussion 75
References 76
5 Algorithm Design for Hardware-Based Computing Technologies 77
5.1 Introduction 77
5.2 The Fundamental Properties of FPGA and ASIC Devices 78
5.3 Low-Power Design Techniques 79
5.3.1 Clock Frequency 80
5.3.2 Silicon Area 80
5.3.3 Switching Frequency 82
5.4 Proposed Hardware Design Strategy 82
5.4.1 Scalability of Design 83
5.4.2 Partitioned-Memory Processing 83
5.4.3 Flexibility of Design 84
5.5 Constraints on Available Resources 85
5.6 Assessing the Resource Requirements 85
5.7 Discussion 86
References 87
6 Derivation of Area-Efficient and Scalable Parallel Architecture 88
6.1 Introduction 88
6.2 Single-PE Versus Multi-PE Architectures 89
6.3 Conflict-Free Parallel Memory Addressing Schemes 91
6.3.1 Data Storage and Accession 91
6.3.2 Trigonometric Coefficient Storage, Accession and Generation 95
6.3.2.1 Minimum-Arithmetic Addressing Scheme 96
6.3.2.2 Minimum-Memory Addressing Scheme 96
6.3.2.3 Summary of Addressing Schemes 97
6.4 Design of Pipelined PE for Single-PE Architecture 100
6.4.1 Internal Pipelining of Generic Double Butterfly 101
6.4.2 Space Complexity Considerations 102
6.4.3 Time Complexity Considerations 103
6.5 Performance and Requirements Analysis of FPGAImplementation 104
6.6 Constraining Latency Versus Minimizing Update-Time 106
6.7 Discussion 108
References 109
7 Design of Arithmetic Unit for Resource-Constrained Solution 111
7.1 Introduction 111
7.2 Accuracy Considerations 112
7.3 Fast Multiplier Approach 113
7.4 CORDIC Approach 114
7.4.1 CORDIC Formulation of Complex Multiplier 114
7.4.2 Parallel Formulation of CORDIC-Based PE 115
7.4.3 Discussion of CORDIC-Based Solution 116
7.4.4 Logic Requirement of CORDIC-Based PE 119
7.5 Comparative Analysis of PE Designs 120
7.6 Discussion 122
References 125
8 Computation of 2n-Point Real-Data Discrete Fourier Transform 126
8.1 Introduction 126
8.2 Computing One DFT via Two Half-Length Regularized FHTs 127
8.2.1 Derivation of 2n-Point Real-Data FFT Algorithm 128
8.2.2 Implementational Considerations 131
8.2.2.1 Solution Exploiting One PE for Computation of Regularized FHTs 133
8.2.2.2 Solution Exploiting Two PEs for Computation of Regularized FHTs 134
8.2.2.3 Summary of Latency-Constrained Solutions 136
8.2.2.4 Reduced-Complexity Solution for Increasing Throughput Rate 136
8.3 Computing One DFT via One Double-Length Regularized FHT 138
8.3.1 Derivation of 2n-Point Real-Data FFT Algorithm 138
8.3.2 Implementational Considerations 139
8.4 Discussion 141
References 143
9 Applications of Regularized Fast Hartley Transform 144
9.1 Introduction 144
9.2 Fast Transform-Space Convolution and Correlation 145
9.3 Up-Sampling and Differentiation of Real-Valued Signal 146
9.3.1 Up-Sampling via Hartley Space 147
9.3.2 Differentiation via Hartley Space 148
9.3.3 Combined Up-Sampling and Differentiation 148
9.4 Correlation of Two Arbitrary Signals 149
9.4.1 Computation of Complex-Data Correlation via Real-Data Correlation 150
9.4.2 Cross-Correlation of Two Finite-Length Data Sets 151
9.4.3 Auto-Correlation: Finite-Length Against Infinite-Length Data Sets 152
9.4.4 Cross-Correlation: Infinite-Length Against Infinite-Length Data Sets 154
9.4.5 Combining Functions in Hartley Space 156
9.5 Channelization of Real-Valued Signal 158
9.5.1 Single Channel: Fast Hartley-Space Convolution 158
9.5.2 Multiple Channels: Conventional Polyphase DFT Filter Bank 160
9.5.2.1 Alias-Free Formulation 163
9.5.2.2 Implementational Considerations 164
9.6 Discussion 164
References 165
10 Summary and Conclusions 167
10.1 Outline of Problem Addressed 167
10.2 Summary of Results 168
10.3 Conclusions 170
Appendix A Computer Program for Regularized Fast Hartley Transform 171
A.1 Introduction 171
A.2 Description of Functions 172
A.2.1 Control Routine 172
A.2.2 Generic Double Butterfly Routines 172
A.2.3 Address Generation and Data Re-ordering Routines 173
A.2.4 Data Memory Accession and Updating Routines 173
A.2.5 Trigonometric Coefficient Generation Routines 174
A.2.6 Look-Up-Table Generation Routines 175
A.2.7 FHT-to-FFT Conversion Routines 175
A.3 Brief Guide to Running the Program 175
A.4 Available Scaling Strategies 177
Appendix B Source Code Listings for Regularized Fast Hartley Transform 180
B.1 Listings for Main Program and Signal Generation Routine 180
B.2 Listings for Pre-processing Functions 192
B.3 Listings for Processing Functions 196
Glossary 228
Index 230
| Erscheint lt. Verlag | 10.3.2010 |
|---|---|
| Reihe/Serie | Signals and Communication Technology |
| Zusatzinfo | XVII, 200 p. |
| Verlagsort | Dordrecht |
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Informatik ► Netzwerke |
| Mathematik / Informatik ► Mathematik ► Analysis | |
| Mathematik / Informatik ► Mathematik ► Angewandte Mathematik | |
| Mathematik / Informatik ► Mathematik ► Statistik | |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Naturwissenschaften ► Physik / Astronomie | |
| Technik ► Elektrotechnik / Energietechnik | |
| Technik ► Nachrichtentechnik | |
| Schlagworte | algorithm • Analysis • Code • Communication • Complexity • discrete Fourier transform • Fast Fourier transform • fast Fourier transform (FFT) • FFT • FHT • Fourier transform • FPGA • metrics • Parallel • Signal |
| ISBN-10 | 90-481-3917-1 / 9048139171 |
| ISBN-13 | 978-90-481-3917-0 / 9789048139170 |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)Größe: 2,6 MB
DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
