Mastering the Discrete Fourier Transform in One, Two or Several Dimensions: Pitfalls and Artifacts
by
Isaac Amidror

Table of Contents:

Preface

xi

1. Introduction

1

1.1 The discrete Fourier transform	1
1.2 A brief historical background	2
1.3 The scope of the present book	4
1.4 Overview of the following chapters	5
1.5 About the graphic presentation of sampled signals and discrete data	7
1.5.1 Graphic presentations in the 1D case	7
1.5.2 Graphic presentations in the 2D case	8
1.5.3 Graphic presentations in the MD case	13
1.6 About the exercises and the internet site	13

2. Background and basic notions

15

2.1 Introduction	15
2.2 The continuous Fourier transform: definitions and notations	15
2.3 The discrete Fourier transform: definitions and notations	17
2.4 Rules for deriving new Fourier transforms from already known ones	21
2.4.1 Rules for the 1D continuous Fourier transform	22
2.4.2 Rules for the 2D continuous Fourier transform	23
2.4.3 Rules for the MD continuous Fourier transform	25
2.4.4 Rules for the 1D discrete Fourier transform	26
2.4.5 Rules for the 2D discrete Fourier transform	28
2.4.6 Rules for the MD discrete Fourier transform	29
2.5 Graphical development of the DFT — a three-stage process	31
2.6 DFT as an approximation to the continuous Fourier transform	36
2.7 The use of DFT in the case of periodic or almost-periodic functions	41
Problems	42

3. Data reorganizations for the DFT and the IDFT

45

3.1 Introduction	45
3.2 Reorganization of the output data of the DFT	45
3.3 Reorganization of the input data of the DFT	47
3.4 Data reorganizations in the case of IDFT	51
3.5 Examples	54
3.6 Discussion	60
Problems	66

4. True units along the axes when plotting the DFT

69

4.1 Introduction	69
4.2 True units for the input array	72
4.3 True units for the output array	72
4.3.1 The particular case of periodic functions	74
4.4 True units for the DFT element values (heights along the vertical axis)	78
4.5 Examples	79
Problems	84

5. Issues related to aliasing

89

5.1 Introduction	89
5.2 Aliasing in the one dimensional case	89
5.3 Examples of aliasing in the one dimensional case	95
5.4 Aliasing in two or more dimensions	113
5.5 Examples of aliasing in the multidimensional case	114
5.6 Discussion	132
5.7 Signal-domain aliasing	133
Problems	136

6. Issues related to leakage

143

6.1 Introduction	143
6.2 Leakage in the one dimensional case	143
6.3 Examples of leakage in the one dimensional case	148
6.4 Errors due to signal-domain truncation	158
6.5 Spectral impulses that fall between output array elements	162
6.6 Leakage in two or more dimensions	165
6.6.1 The case of 2D 1-fold periodic functions	170
6.6.2 The case of 2D 2-fold periodic functions	172
6.6.3 The general MD case	173
6.7 Signal-domain leakage	174
Problems	179

7. Issues related to resolution and range

185

7.1 Introduction	185
7.2 The choice of the array size	185
7.3 The choice of the sampling interval	186
7.4 The choice of the sampling range	187
7.5 The choice of the frequency step and of the frequency range	189
Problems	192

8. Miscellaneous issues

195

8.1 Introduction	195
8.2 Representation of discontinuities	195
8.3 Phase related issues	202
8.4 Symmetry related issues	203
8.5 Jaggies on sharp edges as aliasing or reconstruction phenomena	210
8.6 Sub-Nyquist artifacts	223
8.7 Displaying considerations	241
8.8 Numeric precision considerations	241
Problems	242

Appendices

A. Impulses in the continuous and discrete worlds

247

A.1 Introduction	247
A.2 Continuous-world impulses vs. discrete-world impulses	247
A.3 Impulses in the spectral domain	248
A.4 Impulses in the signal domain	259

B. Data extensions and their effects on the DFT results

265

B.1 Introduction	265
B.2 Method 1: Extending the input data by adding new values beyond the original range	265
B.3 Method 2: Extending the input data by denser sampling within the original range	266
B.4 Method 3: Extending the input data by adding zeroes after each value                                         (zero packing)	268
B.5 Method 4: Extending the input data by replicating it	269
B.6 Method 5: Extending the input data by replicating each of its elements	269
B.7 Method 6: Extending the input data by adding zeroes beyond its original range                                         (zero padding)	270
B.8 Conclusions	272

C. The roles of p and q and their interconnections

273

C.1 Introduction	273
C.2 The one dimensional case	273
C.3 Generalization of p and q to the multidimensional case	280
C.3.1 Multidimensional generalization in the continuous world	281
C.3.2 Multidimensional generalization in the discrete world	285

D. Miscellaneous remarks and derivations

299

D.1 The periodicity of the input and output arrays of the DFT	299
D.2 Explanation of the element order in the DFT output array	300
D.3 The beating effect in a sum of cosines with similar frequencies	302
D.4 Convolutions with a sinc function which have no effect	306
D.5 The convolution of a square pulse with a sinc function	307
D.6 A more detailed discussion on Remark A.2 of Sec. A.3	310
D.7 The effect of the sinc lobes on its convolution with a sharp-edged function	314
D.8 On the order of applying the sampling and truncation operations	315
D.9 Relation of the DFT to the CFT and to Fourier series	317
D.9.1 Examples illustrating the relation of the DFT to the CFT and                                         to Fourier series	325
D.10 The 2D spectrum of a rotated bar passing through the origin	332

E. Glossary of the main terms

335

E.1 About the glossary	335
E.2 Terms in the signal domain	336
E.3 Terms in the spectral domain	341
E.4 Miscellaneous terms	345

List of the main relations

353

List of notations and symbols

359

List of abbreviations

359

References

361

Index

367

Back to the DFT book homepage