MATHEMATICS OF THE
DISCRETE FOURIER TRANSFORM (DFT)
WITH AUDIO APPLICATIONS
SECOND EDITION

JULIUS O. SMITH III

Center for Computer Research in Music and Acoustics (CCRMA)
Department of Music, Stanford University, Stanford, California 94305 USA

• Preface
  • Chapter Outline
  • Acknowledgments
  • Errata
  
  
• Introduction to the DFT
  • DFT Definition
  • Inverse DFT
  • Mathematics of the DFT
  • DFT Math Outline
  
  
• Complex Numbers
  • Factoring a Polynomial
  • The Quadratic Formula
  • Complex Roots
  • Fundamental Theorem of Algebra
  • Complex Basics
  • The Complex Plane
  • More Notation and Terminology
  • Elementary Relationships
  • Euler's Identity
  • De Moivre's Theorem
  • Conclusion
  • Complex_Number Problems
  
  
• Proof of Euler's Identity
  • Euler's Identity
  • Positive Integer Exponents
  • Properties of Exponents
  • The Exponent Zero
  • Negative Exponents
  • Rational Exponents
  • Real Exponents
  • A First Look at Taylor Series
  • Imaginary Exponents
  • Derivatives of f(x)=a^x
  • Back to e
  • e^(j theta)
  • Back to Mth Roots
  • Roots of Unity
  • Direct Proof of De Moivre's Theorem
  • Euler_Identity Problems
  
  
• Sinusoids and Exponentials
  • Sinusoids
    • Example Sinusoids
    • Why Sinusoids are Important
    • In-Phase & Quadrature Sinusoidal Components
    • Sinusoids at the Same Frequency
    • Constructive and Destructive Interference
    • Sinusoid Magnitude Spectra
  • Exponentials
    • Why Exponentials are Important
    • Audio Decay Time (T60)
  • Complex Sinusoids
    • Circular Motion
    • Projection of Circular Motion
    • Positive and Negative Frequencies
    • Plotting Complex Sinusoids versus Frequency
    • Sinusoidal Amplitude Modulation (AM)
      • Example AM Spectra
    • Sinusoidal Frequency Modulation (FM)
      • Bessel Functions
      • FM Spectra
    • Analytic Signals and Hilbert Transform Filters
    • Generalized Complex Sinusoids
    • Sampled Sinusoids
    • Powers of z
    • Phasors and Carriers
      • Phasor
      • Why Phasors are Important
    • Importance of Generalized Complex Sinusoids
    • Comparing Analog and Digital Complex Planes
  • Sinusoid Problems
  
  
• Geometric Signal Theory
  • The DFT
  • Signals as Vectors
    • An Example Vector View:
  • Vector Addition
  • Vector Subtraction
  • Scalar Multiplication
  • Linear Combination of Vectors
  • Linear Vector Space
  • Signal Metrics
    • Other Lp Norms
    • Norm Properties
    • Banach Spaces
  • 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
    • Changing Coordinates
      • An Example of Changing Coordinates in 2D
    • Projection onto Linearly Dependent Vectors
    • Projection onto Non-Orthogonal Vectors
    • General Conditions
    • Signal/Vector Reconstruction from Projections
    • Gram-Schmidt Orthogonalization
  • Signal Projection Problems
  
  
• The DFT Derived
  • Geometric Series
  • Orthogonality of Sinusoids
    • Nth Roots of Unity
    • DFT Sinusoids
  • Orthogonality of the DFT Sinusoids
  • Norm of the DFT Sinusoids
  • An Orthonormal Sinusoidal Set
  • The Discrete Fourier Transform (DFT)
  • Frequencies in the ``Cracks''
  • Spectral Bin Numbers
  • Fourier Series Special Case
  • Normalized DFT
  • The Length 2 DFT
  • Matrix Formulation of the DFT
  • DFT Problems
  
  
• Fourier Theorems for the DFT
  • The DFT and its Inverse Restated
    • Notation and Terminology
    • Modulo Indexing, Periodic Extension
  • Signal Operators
    • Operator Notation
    • Flip Operator
    • Shift Operator
      • Examples
    • Convolution
      • Commutativity of Convolution
      • Convolution as a Filtering Operation
      • Convolution Example 1: Smoothing a Rectangular Pulse
      • Convolution Example 2: ADSR Envelope
      • Convolution Example 3: Matched Filtering
      • Graphical Convolution
      • Polynomial Multiplication
      • Multiplication of Decimal Numbers
    • Correlation
    • Stretch Operator
    • Zero Padding
    • Causal (Periodic) Signals
    • Causal Zero Padding
    • Zero Padding Applications
    • Ideal Spectral Interpolation
    • Interpolation Operator
    • Repeat Operator
    • Downsampling Operator
    • Alias Operator
  • Even and Odd Functions
  • Fourier Theorems
    • Linearity
    • Conjugation and Reversal
    • Symmetry
    • Shift Theorem
      • Linear Phase Terms
      • Linear Phase Signals
      • Zero Phase Signals
      • Application of the Shift Theorem to FFT Windows
    • Convolution Theorem
    • Dual of the Convolution Theorem
    • Correlation Theorem
    • Power Theorem
      • Normalized DFT Power Theorem
    • Rayleigh Energy Theorem (Parseval's Theorem)
    • Stretch Theorem (Repeat Theorem)
    • Downsampling Theorem (Aliasing Theorem)
      • Illustration of the Downsampling/Aliasing Theorem in Matlab
    • Zero Padding Theorem (Spectral Interpolation)
    • Interpolation Theorems
      • Relation to Stretch Theorem
      • Bandlimited Interpolation of Time-Limited Signals
  • DFT Theorems Problems
  
  
• DFT Applications
  • Why a DFT is usually called an FFT in practice
  • Spectrum Analysis of a Sinusoid
    • FFT of a Simple Sinusoid
    • FFT of a Not-So-Simple Sinusoid
    • FFT of a Zero-Padded Sinusoid
    • Use of a Blackman Window
      • Applying the Blackman Window
    • Hann-Windowed Complex Sinusoid
      • Hann Window Spectrum Analysis Results
      • Spectral Phase
  • Spectrograms
    • Spectrogram of Speech
  • Filters and Convolution
    • Frequency Response
    • Amplitude Response
    • Phase Response
  • Correlation Analysis
    • Cross-Correlation
    • Unbiased Cross-Correlation
    • Autocorrelation
    • Matched Filtering
    • FIR System Identification
  • Power Spectral Density
  • Coherence Function
    • Coherence Function in Matlab
  • Recommended Further Reading
  
  
• Fast Fourier Transforms (FFT)
  • Mixed-Radix Cooley-Tukey FFT
    • Decimation in Time
    • Radix 2 FFT
      • Radix 2 FFT Complexity is N Log N
    • Fixed-Point FFTs and NFFTs
  • Prime Factor Algorithm (PFA)
  • Rader's FFT Algorithm for Prime Lengths
  • Bluestein's FFT Algorithm
  • Fast Transforms in Audio DSP
  • Related Transforms
    • The Discrete Cosine Transform (DCT)
    • Number Theoretic Transform
  • FFT Software
  
  
• Continuous/Discrete Transforms
  • Discrete Time Fourier Transform (DTFT)
  • Fourier Transform (FT) and Inverse
    • Existence of the Fourier Transform
    • The Continuous-Time Impulse
  • Fourier Series (FS)
    • Relation of the DFT to Fourier Series
  
  
• Continuous Fourier Theorems
  • Differentiation Theorem
  • Scaling Theorem
  • The Uncertainty Principle
    • Second Moments
    • Time-Limited Signals
    • Time-Bandwidth Products are Unbounded Above
  
  
• Sampling Theory
  • Introduction to Sampling
    • Reconstruction from Samples--Pictorial Version
    • The Sinc Function
    • Reconstruction from Samples--The Math
  • Aliasing of Sampled Signals
    • Continuous-Time Aliasing Theorem
  • Sampling Theorem
  • Geometric Sequence Frequencies
  
  
• Taylor Series Expansions
  • Informal Derivation of Taylor Series
  • Taylor Series with Remainder
  • Formal Statement of Taylor's Theorem
  • Weierstrass Approximation Theorem
  • Points of Infinite Flatness
  • Differentiability of Audio Signals
  
  
• Logarithms and Decibels
  • Logarithms
    • Changing the Base
    • Logarithms of Negative and Imaginary Numbers
  • Decibels
    • Properties of DB Scales
    • Specific DB Scales
      • DBm Scale
      • DBV Scale
      • DB SPL
      • DBA (A-Weighted DB)
      • DB for Display
    • Dynamic Range
  • Voltage, Current, and Resistance
  • Exercises
  
  
• Digital Audio Number Systems
  • Linear Number Systems
    • Pulse Code Modulation (PCM)
    • Binary Integer Fixed-Point Numbers
      • One's Complement Fixed-Point Format
      • Two's Complement Fixed-Point Format
      • 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?
  • Logarithmic Number Systems for Audio
    • Floating-Point Numbers
    • Logarithmic Fixed-Point Numbers
    • Mu-Law Coding
  • Round-Off Error Variance
  
  
• Matrices
  • Matrix Multiplication
  • Solving Linear Equations Using Matrices
  
  
• Matlab/Octave Examples
  • Complex Numbers in Matlab and Octave
    • Complex Number Manipulation
  • Factoring Polynomials in Matlab
  • Geometric Signal Theory
    • Vector Interpretation of Complex Numbers
    • Signal Metrics
      • Signal Energy and Power
    • Inner Product
    • Vector Cosine
    • Projection
      • Projection Example 1
      • Projection Example 2
    • Orthogonal Basis Computation
  • The DFT
    • DFT Sinusoids for
    • DFT Bin Response
    • DFT Matrix
  • Spectrogram Computation
  
  
• Bibliography
• Index for this Document
• About this document ...

Sign in