https://ccrma.stanford.edu/~jos/mdft/ Next | Index | JOS Index | JOS Pubs | JOS Home | Search --------------------------------------------------------------------- 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) --------------------------------------------------------------------- --------------------------------------------------------------------- * 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 to the power 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 o Example Sinusoids o Why Sinusoids are Important o In-Phase & Quadrature Sinusoidal Components o Sinusoids at the Same Frequency o Constructive and Destructive Interference o Sinusoid Magnitude Spectra + Exponentials o Why Exponentials are Important o Audio Decay Time (T60) + Complex Sinusoids o Circular Motion o Projection of Circular Motion o Positive and Negative Frequencies o Plotting Complex Sinusoids versus Frequency o Sinusoidal Amplitude Modulation (AM) # Example AM Spectra o Sinusoidal Frequency Modulation (FM) # Bessel Functions # FM Spectra o Analytic Signals and Hilbert Transform Filters o Generalized Complex Sinusoids o Sampled Sinusoids o Powers of z o Phasors and Carriers # Phasor # Why Phasors are Important o Importance of Generalized Complex Sinusoids o Comparing Analog and Digital Complex Planes + Sinusoid Problems * Geometric Signal Theory + The DFT + Signals as Vectors o An Example Vector View: $ N=2$ + Vector Addition + Vector Subtraction + Scalar Multiplication + Linear Combination of Vectors + Linear Vector Space + Signal Metrics o Other Lp Norms o Norm Properties o Summary and Related Mathematical Topics + The Inner Product o Linearity of the Inner Product o Norm Induced by the Inner Product o Cauchy-Schwarz Inequality o Triangle Inequality o Triangle Difference Inequality o Vector Cosine o Orthogonality o The Pythagorean Theorem in N-Space o Projection + Signal Reconstruction from Projections o Changing Coordinates # An Example of Changing Coordinates in 2D o Projection onto Linearly Dependent Vectors o Projection onto Non-Orthogonal Vectors o General Conditions o Signal/Vector Reconstruction from Projections o Gram-Schmidt Orthogonalization + Signal Projection Problems * The DFT Derived + Geometric Series + Orthogonality of Sinusoids o Nth Roots of Unity o 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 o Notation and Terminology o Modulo Indexing, Periodic Extension + Signal Operators o Operator Notation o Flip Operator o Shift Operator # Examples o 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 o Correlation o Stretch Operator o Zero Padding o Causal (Periodic) Signals o Causal Zero Padding o Zero Padding Applications o Ideal Spectral Interpolation o Interpolation Operator o Repeat Operator o Downsampling Operator o Alias Operator + Even and Odd Functions + Fourier Theorems o Linearity o Conjugation and Reversal o Symmetry o Shift Theorem # Linear Phase Terms # Linear Phase Signals # Zero Phase Signals # Application of the Shift Theorem to FFT Windows o Convolution Theorem o Dual of the Convolution Theorem o Correlation Theorem o Power Theorem # Normalized DFT Power Theorem o Rayleigh Energy Theorem (Parseval's Theorem) o Stretch Theorem (Repeat Theorem) o Downsampling Theorem (Aliasing Theorem) # Illustration of the Downsampling/Aliasing Theorem in Matlab o Zero Padding Theorem (Spectral Interpolation) o 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 o FFT of a Simple Sinusoid o FFT of a Not-So-Simple Sinusoid o FFT of a Zero-Padded Sinusoid o Use of a Blackman Window # Applying the Blackman Window o Hann-Windowed Complex Sinusoid # Hann Window Spectrum Analysis Results # Spectral Phase + Spectrograms o Spectrogram of Speech + Filters and Convolution o Frequency Response o Amplitude Response o Phase Response + Correlation Analysis o Cross-Correlation o Unbiased Cross-Correlation o Autocorrelation o Matched Filtering o FIR System Identification + Power Spectral Density + Coherence Function o Coherence Function in Matlab + Recommended Further Reading * Fast Fourier Transforms (FFT) + Mixed-Radix Cooley-Tukey FFT o Decimation in Time o Radix 2 FFT # Radix 2 FFT Complexity is N Log N o 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 o The Discrete Cosine Transform (DCT) o Number Theoretic Transform + FFT Software * Continuous/Discrete Transforms + Discrete Time Fourier Transform (DTFT) + Fourier Transform (FT) and Inverse o Existence of the Fourier Transform o The Continuous-Time Impulse + Fourier Series (FS) o Relation of the DFT to Fourier Series * Continuous Fourier Theorems + Differentiation Theorem + Scaling Theorem + The Uncertainty Principle o Second Moments o Time-Limited Signals o Time-Bandwidth Products are Unbounded Above * Sampling Theory + Introduction to Sampling o Reconstruction from Samples--Pictorial Version o The Sinc Function o Reconstruction from Samples--The Math + Aliasing of Sampled Signals o 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 o Changing the Base o Logarithms of Negative and Imaginary Numbers + Decibels o Properties of DB Scales o Specific DB Scales # DBm Scale # VU Meters and the DBu Scale^F.4 # DBV Scale # DB SPL # DBA (A-Weighted DB) # DB for Display o Dynamic Range + Voltage, Current, and Resistance + Exercises * Digital Audio Number Systems + Linear Number Systems o Pulse Code Modulation (PCM) o Binary Integer Fixed-Point Numbers # One's Complement Fixed-Point Format # Two's Complement Fixed-Point Format # Two's-Complement, Integer Fixed-Point Numbers o Fractional Binary Fixed-Point Numbers o How Many Bits are Enough for Digital Audio? o When Do We Have to Swap Bytes? + Logarithmic Number Systems for Audio o Floating-Point Numbers o Logarithmic Fixed-Point Numbers o Mu-Law Coding + Round-Off Error Variance * Matrices + Matrix Multiplication + Solving Linear Equations Using Matrices * Matlab/Octave Examples + Complex Numbers in Matlab and Octave o Complex Number Manipulation + Factoring Polynomials in Matlab + Geometric Signal Theory o Vector Interpretation of Complex Numbers o Signal Metrics # Signal Energy and Power o Inner Product o Vector Cosine o Projection # Projection Example 1 # Projection Example 2 o Orthogonal Basis Computation + The DFT o DFT Sinusoids for $ N=8$ o DFT Bin Response o DFT Matrix + Spectrogram Computation * Bibliography * Index for this Document * About this document ... --------------------------------------------------------------------- Next | Index | JOS Index | JOS Pubs | JOS Home | Search --------------------------------------------------------------------- [How to cite this work] [Order a printed hardcopy] [Comment on this page via email] --------------------------------------------------------------------- ``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 (c) 2022-09-05 by Julius O. Smith III Center for Computer Research in Music and Acoustics (CCRMA), Stanford University CCRMA