NOTE: THIS DOCUMENT IS OBSOLETE, PLEASE CHECK THE NEW VERSION: "Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications --- Second Edition", by Julius O. Smith III, W3K Publishing, 2007, ISBN 978-0-9745607-4-8. - Copyright © 2017-09-28 by Julius O. Smith III - Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

<< Previous page  TOC  INDEX  Next page >>

Music 320 Background Reader
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

---

• Preface
  • Outline
• Introduction to the DFT
  • The DFT
  • Mathematics of the DFT
  • DFT Math Outline
• Introduction to Complex Numbers
  • Factoring a Polynomial with Real Roots
  • The Quadratic Formula
  • Complex Roots
  • The Fundamental Theorem of Algebra
  • Complex Numbers
    • The Complex Plane
    • More Notation and Terminology
    • Elementary Relationships
    • Euler’s Formula
    • De Moivre’s Theorem
  • Numerical Tools in Matlab
  • Numerical Tools in Mathematica
• Proof of Euler’s Identity
  • Euler’s Theorem
    • Positive Integer Exponents
    • Properties of Exponents
    • The Exponent Zero
    • Negative Exponents
    • Rational Exponents
      • Special Case: The Mth Roots of Unity
    • Real Exponents
    • A First Look at Taylor Series
    • Imaginary Exponents
    • Derivatives of f(x)=a^x
    • Back to e
    • Sidebar on Mathematica
    • Back to e^(j theta)
  • Informal Derivation of Taylor Series Expansion
  • Derivation of Taylor Series Expansion with Remainder
  • Formal Statement of Taylor’s Theorem
  • The Weierstrass (Polynomial) Approximation Theorem
  • Further Notes on Differentiability of Audio Signals
• Logarithms, Decibels, and Number Systems
  • Logarithms
    • Changing the Base
    • Logarithms of Negative and Imaginary Numbers
  • Decibels
    • Properties of DB Scales
    • Specific DB Scales
      • DBm Scale
      • DBV Scale
      • DB SPL
      • DB for Display
    • Dynamic Range
  • Linear Number Systems for Digital Audio
    • Pulse Code Modulation (PCM)
    • Binary Integer Fixed-Point Numbers
      • One’s Complement Fixed-Point Format
      • Two’s Complement Fixed-Point Format
      • General Formula for Two’s-Complement, Integer Fixed-Point Numbers
      • ‘‘Little Endian’’ Formula for Two’s-Complement, Integer Fixed-Point Numbers
    • Fractional Binary Fixed-Point Numbers
    • How Many Bits are Enough for Digital Audio?
    • When Do We Have to Swap Bytes When Changing Computers?
  • Logarithmic Number Systems for Digital Audio
    • Floating-Point Numbers
    • Logarithmic Fixed-Point Numbers
    • -Law Companding
  • Appendix A: Round-Off Error Variance
  • Appendix B: Electrical Engineering 101
• Sinusoids and Exponentials
  • Sinusoids
    • Example Sinusoids
    • Why Sinusoids are Important
    • In-Phase and Quadrature Sinusoidal Components
    • Sinusoids at the Same Frequency
    • Constructive and Destructive Interference of Sinusoids
  • Exponentials
    • Why Exponentials are Important
    • Audio Decay Time ()
  • Complex Sinusoids
    • Circular Motion
    • Projection of Circular Motion
    • Positive and Negative Frequencies
    • The Analytic Signal and Hilbert Transform Filters
    • Generalized Complex Sinusoids
    • Sampled Sinusoids
    • Powers of
    • Why (Generalized) Complex Sinusoids are Important
    • Comparing Analog and Digital Complex Planes
  • Mathematica for Selected Plots
  • Acknowledgement
• Geometric Signal Theory
  • The DFT
  • Signals as Vectors
    • An Example Vector View:
  • Vector Addition
  • Vector Subtraction
  • Signal Metrics
    • Other Norms
  • The Inner Product
    • Linearity of the Inner Product
    • Norm Induced by the Inner Product
    • Cauchy-Schwarz Inequality
    • Triangle Inequality
    • Triangle Difference Inequality
    • Vector Cosine
    • Orthogonality
    • The Pythagorean Theorem in N-Space
    • Projection
  • Signal Reconstruction from Projections
    • An Example of Changing Coordinates in 2D
    • General Conditions
    • Gram-Schmidt Orthogonalization
  • Appendix: Matlab Examples
• The Discrete Fourier Transform (DFT) Derived
  • The DFT Derived
    • Geometric Series
    • Orthogonality of Sinusoids
    • Orthogonality of the DFT Sinusoids
    • Norm of the DFT Sinusoids
    • An Orthonormal Sinusoidal Set
    • The Discrete Fourier Transform (DFT)
    • Frequencies in the ‘‘Cracks’’
    • Normalized DFT
  • The Length 2 DFT
  • Matrix Formulation of the DFT
    • Matrices
    • Matrix Multiplication
    • The DFT Matrix
  • Matlab Examples
    • Figure 7.2
    • Figure 7.3
    • DFT Matrix
• Fourier Theorems for the DFT
  • The DFT and its Inverse
    • Notation and Terminology
    • Modulo Indexing, Periodic Extension
  • Signal Operators
    • Flip Operator
    • Shift Operator
    • Convolution
      • Graphical Convolution
      • Polynomial Multiplication
      • Multiplication of Decimal Numbers
    • Correlation
    • Stretch Operator
    • Zero Padding
    • Repeat Operator
    • Decimation Operator
    • Alias Operator
  • Even and Odd Functions
  • The Fourier Theorems
    • Linearity
    • Conjugation and Reversal
    • Symmetry
    • Shift Theorem
      • Linear Phase Terms
      • Application of the Shift Theorem to FFT Windows
    • Convolution Theorem
    • Dual of the Convolution Theorem
    • Correlation Theorem
    • Power Theorem
    • Rayleigh Energy Theorem (Parseval’s Theorem)
    • Stretch Theorem (Repeat Theorem)
    • Decimation Theorem (Aliasing Theorem)
    • Zero Padding Theorem
    • Bandlimited Interpolation in Time
  • Conclusions
  • Acknowledgement
  • Appendix A: Linear Time-Invariant Filters and Convolution
    • LTI Filters and the Convolution Theorem
  • Appendix B: Introductory Statistical Signal Processing
    • Cross-Correlation
    • Applications of Cross-Correlation
    • Autocorrelation
    • Coherence
  • Appendix C: Mathematica/Matlab Examples
  • Appendix D: The Similarity Theorem
• Example Applications of the DFT
  • Spectrum Analysis of a Sinusoid: Windowing, Zero-Padding, and the FFT
    • Example 1: FFT of a Simple Sinusoid
    • Example 2: FFT of a Not-So-Simple Sinusoid
    • Example 3: FFT of a Zero-Padded Sinusoid
    • Example 4: Blackman Window
    • Example 5: Use of the Blackman Window
    • Example 6: Hanning-Windowed Complex Sinusoid
      • Spectral Phase
• A Basic Tutorial on Sampling Theory
  • Introduction
    • Reconstruction from Samples–Pictorial Version
    • Reconstruction from Samples–The Math
  • Aliasing of Sampled Continuous-Time Signals
  • Shannon’s Sampling Theorem
  • Figuring Out Sampling Theory by Playing Around with Complex Sinusoids
    • What frequencies are representable by a geometric sequence?
    • Recovering a Continuous-Time Signal from its Samples
      • Method 1: Additive Synthesis
      • Does it Work?
• Introduction to Digital Filter Analysis
  • Motivating Example and Overview
  • FIR Filters
    • Convolution Representation
    • Finiteness
    • Causal FIR Filters
    • Transfer Function
    • Order
  • The BiQuad Section
  • Digital Filter Theory Summary
    • Linearity and Time-Invariance
    • Difference Equation
    • Convolution Representation of LTI Filters
    • Frequency Response
    • Phase Delay and Group Delay
• Bibliography
• Index
• About this document …

<< Previous page  TOC  INDEX  Next page >>