Smith (III) J. O. - Mathematics of the Discrete Fourier Transform.pdf

(1483 KB) Pobierz
mdft.dvi
Mathematics of the Discrete Fourier Transform
(DFT)
Julius O. Smith III (jos@ccrma.stanford.edu)
Center for Computer Research in Music and Acoustics (CCRMA)
Department of Music, Stanford University
Stanford, California 94305
March 15, 2002
Page ii
DRAFT of “Mathematics of the Discrete Fourier Transform (DFT),” by J.O.
Smith, CCRMA, Stanford, Winter 2002. The latest draft and linked HTML
version are available on-line at http://www-ccrma.stanford.edu/~jos/mdft/ .
134149313.001.png
Contents
1 Introduction to the DFT 1
1.1 DFT Definition . . . ..................... 1
1.2 Mathematics of the DFT . . . . .............. 3
1.3 DFT Math Outline . ..................... 6
2 Complex Numbers 7
2.1 Factoring a Polynomial . . . . . . .............. 7
2.2 The Quadratic Formula . . . . . .............. 8
2.3 Complex Roots . . . ..................... 9
2.4 Fundamental Theorem of Algebra .............. 11
2.5 Complex Basics . . . ..................... 11
2.5.1 The Complex Plane . . . .............. 13
2.5.2 More Notation and Terminology . . . . . . .... 14
2.5.3 Elementary Relationships .............. 15
2.5.4 Euler’s Formula . . . . . . .............. 15
2.5.5 De Moivre’s Theorem . . .............. 17
2.6 Numerical Tools in Matlab . . . .............. 17
2.7 Numerical Tools in Mathematica .............. 23
3 Proof of Euler’s Identity 27
3.1 Euler’s Theorem . . ..................... 27
3.1.1 Positive Integer Exponents . . . . . . . . . .... 27
3.1.2 Properties of Exponents . .............. 28
3.1.3 The Exponent Zero . . . . .............. 28
3.1.4 Negative Exponents . . . .............. 28
3.1.5 Rational Exponents . . . .............. 29
3.1.6 Real Exponents . . . . . . .............. 30
3.1.7 A First Look at Taylor Series . . . . . . . . .... 31
3.1.8 Imaginary Exponents . . .............. 32
iii
Page iv
CONTENTS
3.1.9 Derivatives of f ( x )= a x ............... 32
3.1.10 Back to e ....................... 33
3.1.11 Sidebar on Mathematica . . . . . . . . . ...... 34
3.1.12 Back to e jθ ...................... 34
3.2 Informal Derivation of Taylor Series . . . . . . ...... 36
3.3 Taylor Series with Remainder ................ 37
3.4 Formal Statement of Taylor’s Theorem . . . . . ...... 39
3.5 Weierstrass Approximation Theorem . . . . . . ...... 40
3.6 Differentiability of Audio Signals . . . . . . . . ...... 40
4 Logarithms, Decibels, and Number Systems 41
4.1 Logarithms . . . ....................... 41
4.1.1 Changing the Base . . ................ 43
4.1.2 Logarithms of Negative and Imaginary Numbers . 43
4.2 Decibels . . . . . ....................... 44
4.2.1 Properties of DB Scales . . . . . . . . . ...... 45
4.2.2 Specific DB Scales . . ................ 46
4.2.3 Dynamic Range . . . . ................ 52
4.3 Linear Number Systems for Digital Audio . . . ...... 53
4.3.1 Pulse Code Modulation (PCM) . . . . . ...... 53
4.3.2 Binary Integer Fixed-Point Numbers . . ...... 53
4.3.3 Fractional Binary Fixed-Point Numbers ...... 58
4.3.4 How Many Bits are Enough for Digital Audio? . . 58
4.3.5 When Do We Have to Swap Bytes? . . . ...... 59
4.4 Logarithmic Number Systems for Audio . . . . ...... 61
4.4.1 Floating-Point Numbers . . . . . . . . . ...... 61
4.4.2 Logarithmic Fixed-Point Numbers . . . ...... 63
4.4.3 Mu-Law Companding ................ 64
4.5 Appendix A: Round-Off Error Variance . . . . ...... 65
4.6 Appendix B: Electrical Engineering 101 . . . . ...... 66
5 Sinusoids and Exponentials 69
5.1 Sinusoids . . . . ....................... 69
5.1.1 Example Sinusoids . . ................ 70
5.1.2 Why Sinusoids are Important . . . . . . ...... 71
5.1.3 In-Phase and Quadrature Sinusoidal Components . 72
5.1.4 Sinusoids at the Same Frequency . . . . ...... 73
5.1.5 Constructive and Destructive Interference . . . . . 74
5.2 Exponentials . . ....................... 76
DRAFT of “Mathematics of the Discrete Fourier Transform (DFT),” by J.O.
Smith, CCRMA, Stanford, Winter 2002. The latest draft and linked HTML
version are available on-line at http://www-ccrma.stanford.edu/~jos/mdft/ .
134149313.002.png
CONTENTS
Page v
5.2.1 Why Exponentials are Important . . . . . . .... 77
5.2.2 Audio Decay Time (T60) .............. 78
5.3 Complex Sinusoids . ..................... 78
5.3.1 Circular Motion . . . . . .............. 79
5.3.2 Projection of Circular Motion . . . . . . . . .... 79
5.3.3 Positive and Negative Frequencies . . . . . .... 80
5.3.4 The Analytic Signal and Hilbert Transform Filters 81
5.3.5 Generalized Complex Sinusoids . . . . . . . .... 85
5.3.6 Sampled Sinusoids . . . . .............. 86
5.3.7 Powers of z ...................... 86
5.3.8 Phasor & Carrier Components of Complex Sinusoids 87
5.3.9 Why Generalized Complex Sinusoids are Important 89
5.3.10 Comparing Analog and Digital Complex Planes . . 91
5.4 Mathematica for Selected Plots . .............. 94
5.5 Acknowledgement . . ..................... 95
6 Geometric Signal Theory 97
6.1 TheDFT ........................... 97
6.2 Signals as Vectors . . ..................... 98
6.3 Vector Addition . . . ..................... 99
6.4 Vector Subtraction . ..................... 100
6.5 Signal Metrics . . . . ..................... 100
6.6 The Inner Product . ..................... 105
6.6.1 Linearity of the Inner Product . . . . . . . .... 106
6.6.2 Norm Induced by the Inner Product . . . . .... 107
6.6.3 Cauchy-Schwarz Inequality . . . . . . . . . .... 107
6.6.4 Triangle Inequality . . . . .............. 108
6.6.5 Triangle Difference Inequality . . . . . . . . .... 109
6.6.6 Vector Cosine ..................... 109
6.6.7 Orthogonality ..................... 109
6.6.8 The Pythagorean Theorem in N-Space . . . .... 110
6.6.9 Projection . . ..................... 111
6.7 Signal Reconstruction from Projections . . . . . . .... 111
6.7.1 An Example of Changing Coordinates in 2D . . . 113
6.7.2 General Conditions . . . . .............. 115
6.7.3 Gram-Schmidt Orthogonalization . . . . . . .... 119
6.8 Appendix: Matlab Examples . . .............. 120
DRAFT of “Mathematics of the Discrete Fourier Transform (DFT),” by J.O.
Smith, CCRMA, Stanford, Winter 2002. The latest draft and linked HTML
version are available on-line at http://www-ccrma.stanford.edu/~jos/mdft/ .
134149313.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin