→☾

International Standard Book Number  —  Click for https://mathworld.wolfram.com/ISBN.html

Search JOS Website

JOS Home Page

JOS Online Publications

Index of terms in JOS Website

Index: Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications -- Second Edition

Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications -- Second Edition

Fourier Theorems for the DFT

Alias Operator

Fourier Theorems

Click for https://ccrma.stanford.edu/~jos/mdft/Orthogonality.html

Click for https://ccrma.stanford.edu/~jos/mdft/Inner_Product.html

A sinusoid is any function of the form A sin(ω t+φ), where t is the independent variable, and A, ω, φ are fixed parameters of the sinusoid called the amplitude, (radian) frequency, and phase, respectively. Sinusoidal motion is produced by any 'pure' vibration, such as that of an ideal tuning fork or mass-spring system.  —  Click for https://ccrma.stanford.edu/~jos/mdft/Sinusoids.html

The Discrete Fourier Transform (DFT) computes a discrete-frequency spectrum from a discrete-time signal of finite length.  —  Click for https://ccrma.stanford.edu/~jos/mdft/

A signal is typically a real-valued function of time. A discrete-time signal is typically a real-valued function of discrete time, and is therefore a time-ordered sequence of real numbers.  —  Click for http://ccrma.stanford.edu/~jos/filters/Definition_Signal.html

Click for http://archives.math.utk.edu/visual.calculus/0/functions.14/index.html

Click for http://archives.math.utk.edu/visual.calculus/0/functions.14/index.html

Click for http://archives.math.utk.edu/visual.calculus/0/functions.14/index.html

The Fourier theorems establish important, elementary time-frequency relationships. The theorems are largely the same whether stated for the case of the Fourier Transform (FT), Discrete Fourier Transform (DFT), Discrete Time Fourier Transform (DTFT), or Fourier Series (FS).  —  Click for https://ccrma.stanford.edu/~jos/mdft/Fourier_Theorems.html

Click for http://archives.math.utk.edu/visual.calculus/0/functions.14/index.html

Search JOS Website

JOS Home Page

JOS Online Publications

Index of terms in JOS Website

Index: Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications -- Second Edition

Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications -- Second Edition

Fourier Theorems for the DFT

Alias Operator

Fourier Theorems

Even and Odd Functions

Some of the Fourier theorems can be succinctly expressed in terms of even and odd symmetries.

Definition: A function $f(n)$ is said to be even if $f(-n)=f(n)$.

An even function is also symmetric, but the term symmetric applies also to functions symmetric about a point other than $0$.

Definition: A function $f(n)$ is said to be odd if $f(-n)=-f(n)$.

An odd function is also called antisymmetric.

Note that every finite odd function $f(n)$ must satisfy $f(0)=0$.^7.12 Moreover, for any odd $x\in {\mathbb{C}}^N$ with $N$ even, we also have $x(N/2)=0$ since $x(N/2)=-x(-N/2)=-x(-N/2+N)=-x(N/2)$; that is, $N/2$ and $-N/2$ index the same point when $N$ is even (since all indexing in ${\mathbb{C}}^N$ is modulo $N$).

Theorem: Every function $f(n)$ can be uniquely decomposed into a sum of its even part $f_e(n)$ and odd part $f_o(n)$, where

$$\begin{array}{rcl}{f}_e(n)& \stackrel{\mathrm{\Delta }}{=}& \frac{f(n)+f(-n)}{2}\\ f_o(n)& \stackrel{\mathrm{\Delta }}{=}& \frac{f(n)-f(-n)}{2}.\end{array}$$

Proof: In the above definitions, $f_e$ is even and $f_o$ is odd by construction. Summing, we have

$$f_e(n)+f_o(n)=\frac{f(n)+f(-n)}{2}+\frac{f(n)-f(-n)}{2}=f(n).$$

To show uniqueness, let $f(n)=f_e^{\prime }(n)+f_o^{\prime }(n)$ denote some other even-odd decomposition. Then $f(n)+f(-n)=2f_e(n)=2f_e^{\prime }(n)\Rightarrow f_e(n)=f_e^{\prime }(n)$, and $f(n)-f(-n)=2f_o(n)=2f_o^{\prime }(n)\Rightarrow f_o(n)=f_o^{\prime }(n)$.

Theorem: The product of even functions is even, the product of odd functions is even, and the product of an even times an odd function is odd.

Proof: Readily shown.

Since even times even is even, odd times odd is even, and even times odd is odd, we can think of even as $(+)$ and odd as $(-)$:

$$\begin{array}{rcl}(+)\cdot (+)& =& (+)\\ (-)\cdot (-)& =& (+)\\ (+)\cdot (-)& =& (-)\\ (-)\cdot (+)& =& (-)\end{array}$$

Example: $\cos ({\omega }_{k}n)$, $n\in \mathbb{Z}$, is an even signal since $\cos (-\theta )=\cos (\theta )$.

Example: $\sin ({\omega }_{k}n)$ is an odd signal since $\sin (-\theta )=-\sin (\theta )$.

Example: $\cos ({\omega }_{k}n)\cdot \sin ({\omega }_{l}n)$ is an odd signal (even times odd).

Example: $\sin ({\omega }_{k}n)\cdot \sin ({\omega }_{l}n)$ is an even signal (odd times odd).

Theorem: The sum of all the samples of an odd signal $x_o$ in ${\mathbb{C}}^N$ is zero.

Proof: This is readily shown by writing the sum as $x_o(0)+[x_o(1)+x_o(-1)]+\cdots +x(N/2)$, where the last term only occurs when $N$ is even. Each term so written is zero for an odd signal $x_o$.

Example: For all DFT sinusoidal frequencies ${\omega }_k=2\pi k/N$,

$$\sum _{n=0}^{N-1}\sin ({\omega }_{k}n)\cos ({\omega }_{k}n)=0,k=0,1,2,\dots ,N-1.$$

More generally,

$$\sum _{n=0}^{N-1}{x}_e(n)x_o(n)=0,$$

for any even signal $x_e$ and odd signal $x_o$ in ${\mathbb{C}}^N$. In terms of inner products (§5.9), we may say that the even part of every real signal is orthogonal to its odd part:

$$⟨x_e,x_o⟩=0$$

Check Your Understanding

Exercise 1 Multiple Choice

Any function x(t) can be decomposed into even and odd parts. What is the even part x_e(t)?

[x(t) + x(-t)] / 2

[x(t) - x(-t)] / 2

x(t) + x(-t)

x(t) · x(-t)

Check Answer Show Hint

An even function satisfies f(-t) = f(t)

Adding x(t) and x(-t) cancels the odd part

Exercise 2 Multiple Choice

For N = 4, the sequence x = [0, 1, 2, 1] has the property that x[−n] = x[N−n]. What are the even and odd parts of x?

x_e = [0, 1, 2, 1],  x_o = [0, 0, 0, 0]

x_e = [0, 0, 0, 0],  x_o = [0, 1, 2, 1]

x_e = [0, 1, 2, 1],  x_o = [0, 1, 2, 1]

x_e = [0, 0.5, 1, 0.5],  x_o = [0, 0.5, 1, 0.5]

Check Answer Show Hint

Compute x[−n] mod 4: x[0]=0, x[−1]=x[3]=1, x[−2]=x[2]=2, x[−3]=x[1]=1.

Even part = (x[n] + x[−n])/2. If x[n] = x[−n], the odd part vanishes.

Exercise 3 Multiple Choice

For N = 4, the sequence x = [0, 1, 0, −1]. Compute its even part x_e and odd part x_o (indices modulo 4).

x_e = [0, 0.5, 0, −0.5],  x_o = [0, 0.5, 0, −0.5]

x_e = [0, 1, 0, −1],  x_o = [0, 0, 0, 0]

x_e = [0, 0, 0, 0],  x_o = [0, 1, 0, −1]

x_e = [0, −1, 0, 1],  x_o = [0, 1, 0, −1]

Check Answer Show Hint

Compute x[−n] mod 4: position 1 maps to position 3, and vice versa.

If x[−n] = −x[n] for all n, the sequence is purely odd and its even part is zero.

Exercise 4 Multiple Choice

For N = 4, find the even part of x = [0, 1, 2, 3] (indices modulo 4).

[0, 2, 2, 2]

[0, 1, 2, 3]

[0, 2, 4, 6]

[0, −1, 0, 1]

Check Answer Show Hint

x[−n] mod 4: reverse positions 1 and 3, keep 0 and 2 fixed.

Even part = (x[n] + x[−n])/2 element-by-element.

Exercise 5 Multiple Choice

For N = 4 (indexing modulo N), what is the odd part x_o of the sequence x = [0, 1, 2, 3]?

[0, −1, 0, 1]

[0, 1, 0, −1]

[0, 2, 2, 2]

[0, 1, 2, 3]

Check Answer Show Hint

x_o[n] = (x[n] − x[−n])/2, where −n is taken modulo N.

Reverse [0,1,2,3] modulo 4 to get [0,3,2,1], then subtract and halve.

MDFT Course

Progress Outline Exercises Help

0 of 18 chapters started

0 of 301 pages visited · ~7h total content

Current Page

§7.3Even and Odd Functions

Chapter: Fourier Theorems for the DFT

~2 min read

Exercises Completed

0 exercises

Reset Progress

PrefaceChapter OutlineAcknowledgmentsErrata§1Introduction to the DFT§1.1DFT Definition§1.2Inverse DFT§1.3Mathematics of the DFT§1.4DFT Math Outline§2Complex Numbers§2.1Factoring a Polynomial§2.2The Quadratic Formula§2.3Complex Roots§2.4Fundamental Theorem of Algebra§2Complex Basics§2.6The Complex Plane§2.7More Notation and Terminology§2Elementary Relationships§2.9Euler's Identity§2.10De Moivre's Theorem§2Conclusion§3Proof of Euler's Identity§3Euler's Identity§3Positive Integer Exponents§3.3Properties of Exponents§3The Exponent Zero§3Negative Exponents§3.4Rational Exponents§3Real Exponents§3.6A First Look at Taylor Series§3.7Imaginary Exponents§3Derivatives of f(x) = a to the power x§3Back to e§3.10e^(j theta)§3.11Back to Mth Roots§3.12Roots of Unity§3.13Direct Proof of De Moivre's Theorem§4Sinusoids and Exponentials§4.1Sinusoids§4.1Example Sinusoids§4.1.2Why Sinusoids are Important§4.1In-Phase & Quadrature Sinusoidal Components§4.1.4Sinusoids at the Same Frequency§4.1Constructive and Destructive Interference§4.1.6Sinusoid Magnitude Spectra§4.2Exponentials§4.2Why Exponentials are Important§4.2Audio Decay Time (T60)§4.3Complex Sinusoids§4.3Circular Motion§4.3Projection of Circular Motion§4.3.3Positive and Negative Frequencies§4.3.4Plotting Complex Sinusoids versus Frequency§4.3.5Sinusoidal Amplitude Modulation (AM)§4.3.5Example AM Spectra§4.3.6Sinusoidal Frequency Modulation (FM)§4.3.6Bessel Functions§4.3.6FM Spectra§4.3.7Analytic Signals and Hilbert Transform Filters§4.3Generalized Complex Sinusoids§4.3Sampled Sinusoids§4.3Powers of z§4.3.11Phasors and Carriers§4.3.11Phasor§4.3.11Why Phasors are Important§4.3Importance of Generalized Complex Sinusoids§4.3Comparing Analog and Digital Complex Planes§5Geometric Signal Theory§5The DFT§5.2Signals as Vectors§5.2An Example Vector View: \(N=2\)§5.3Vector Addition§5.4Vector Subtraction§5.5Scalar Multiplication§5.6Linear Combination of Vectors§5.7Linear Vector Space§5.8Signal Metrics§5.8.1Other Lp Norms§5.8.2Norm Properties§5.8Summary and Related Mathematical Topics§5.9The Inner Product§5.9Linearity of the Inner Product§5.9Norm Induced by the Inner Product§5.9.3Cauchy-Schwarz Inequality§5.9Triangle Inequality§5.9Triangle Difference Inequality§5.9.6Vector Cosine§5.9.7Orthogonality§5.9.8The Pythagorean Theorem in N-Space§5.9.9Projection§5.9Least Squares Approximation§5.10Signal Reconstruction from Projections§5.10Changing Coordinates§5.10An Example of Changing Coordinates in 2D§5.10Projection onto Linearly Dependent Vectors§5.10Projection onto Non-Orthogonal Vectors§5.10General Conditions§5.10Signal/Vector Reconstruction from Projections§5.10.4Gram-Schmidt Orthogonalization§6The DFT Derived§6.1Geometric Series§6.2Orthogonality of Sinusoids§6.2.1Nth Roots of Unity§6.2.2DFT Sinusoids§6.3Orthogonality of the DFT Sinusoids§6.4Norm of the DFT Sinusoids§6.5An Orthonormal Sinusoidal Set§6The Discrete Fourier Transform (DFT)§6.7Frequencies in the ``Cracks''§6.8Spectral Bin Numbers§6.9Fourier Series Special Case§6.10Normalized DFT§6The Length 2 DFT§6.12Matrix Formulation of the DFT§7Fourier Theorems for the DFT§7.1The DFT and its Inverse Restated§7.1.1Notation and Terminology§7.1.2Modulo Indexing, Periodic Extension§7.2Signal Operators§7.2.1Operator Notation§7.2.2Flip Operator§7.2.3Shift Operator§7.2.3Examples§7.2.4Convolution§7.2.4Commutativity of Convolution§7.2.4Convolution as a Filtering Operation§7.2.4Convolution Example 1: Smoothing a Rectangular Pulse§7.2.4Convolution Example 2: ADSR Envelope§7.2.4Convolution Example 3: Matched Filtering§7.2.4Graphical Convolution§7.2.4Polynomial Multiplication§7.2.4Multiplication of Decimal Numbers§7.2.5Correlation§7.2.6Stretch Operator§7.2.7Zero Padding§7.2Causal (Periodic) Signals§7.2.8Causal Zero Padding§7.2Zero Padding Applications§7.2.10Ideal Spectral Interpolation§7.2.11Interpolation Operator§7.2.12Repeat Operator§7.2.13Downsampling Operator§7.2.14Alias Operator§7.3Even and Odd Functions§7.4Fourier Theorems§7.4.1Linearity§7.4.2Conjugation and Reversal§7.4.3Symmetry§7.4.4Shift Theorem§7.4.4Linear Phase Terms§7.4.4Linear Phase Signals§7.4.4Zero Phase Signals§7.4.4Application of the Shift Theorem to FFT Windows§7.4.5Convolution Theorem§7.4.6Dual of the Convolution Theorem§7.4.7Correlation Theorem§7.4.8Power Theorem§7.4.8Normalized DFT Power Theorem§7.4.9Rayleigh Energy Theorem (Parseval's Theorem)§7.4.10Stretch Theorem (Repeat Theorem)§7.4.11Downsampling Theorem (Aliasing Theorem)§7.4.11Illustration of the Downsampling/Aliasing Theorem in Matlab§7.4.12Zero Padding Theorem (Spectral Interpolation)§7.4.13Interpolation Theorems§7.4.13Relation to Stretch Theorem§7.4.13Bandlimited Interpolation of Time-Limited Signals§8DFT Applications§8Why a DFT is usually called an FFT in practice§8.1Spectrum Analysis of a Sinusoid§8.1FFT of a Simple Sinusoid§8.1FFT of a Not-So-Simple Sinusoid§8.1.3FFT of a Zero-Padded Sinusoid§8.1.4Use of a Blackman Window§8.1.4Applying the Blackman Window§8.1Hann-Windowed Complex Sinusoid§8.1Hann Window Spectrum Analysis Results§8.1Spectral Phase§8.2Spectrograms§8.2Spectrogram of Speech§8.3Filters and Convolution§8.3Frequency Response§8.3Amplitude Response§8.3Phase Response§8.4Correlation Analysis§8.4.1Cross-Correlation§8.4.2Unbiased Cross-Correlation§8.4.3Autocorrelation§8.4Matched Filtering§8.4FIR System Identification§8.5Power Spectral Density§8.6Coherence Function§8.6Coherence Function in Matlab§8Recommended Further Reading§AFast Fourier Transforms (FFT)§A.1Mixed-Radix Cooley-Tukey FFT§A.1.1Decimation in Time§A.1.2Radix 2 FFT§A.1.2Radix 2 FFT Complexity is N Log N§A.1.3Fixed-Point FFTs and NFFTs§A.2Prime Factor Algorithm (PFA)§A.3Rader's FFT Algorithm for Prime Lengths§A.4Bluestein's FFT Algorithm§AFast Transforms in Audio DSP§A.6Related Transforms§A.6.1The Discrete Cosine Transform (DCT)§A.6.2Number Theoretic Transform§A.7FFT Software§BContinuous/Discrete Transforms§B.1Discrete Time Fourier Transform (DTFT)§B.2Fourier Transform (FT) and Inverse§B.2.1Existence of the Fourier Transform§B.2.2The Continuous-Time Impulse§B.3Fourier Series (FS)§B.3Relation of the DFT to Fourier Series§CContinuous Fourier Theorems§C.1Differentiation Theorem§C.2Scaling Theorem§C.3The Uncertainty Principle§C.3.1Second Moments§C.3.2Time-Limited Signals§C.3.3Time-Bandwidth Products are Unbounded Above§DSampling Theory§D.1Introduction to Sampling§D.1Reconstruction from Samples--Pictorial Version§D.1.2The Sinc Function§D.1Reconstruction from Samples--The Math§D.2Aliasing of Sampled Signals§D.2Continuous-Time Aliasing Theorem§D.3Sampling Theorem§D.4Geometric Sequence Frequencies§ETaylor Series Expansions§E.1Informal Derivation of Taylor Series§E.2Taylor Series with Remainder§E.3Formal Statement of Taylor's Theorem§E.4Weierstrass Approximation Theorem§EPoints of Infinite Flatness§E.6Differentiability of Audio Signals§FLogarithms and Decibels§F.1Logarithms§F.1.1Changing the Base§F.1.2Logarithms of Negative and Imaginary Numbers§F.2Decibels§F.2.1Properties of DB Scales§F.2.2Specific DB Scales§F.2.2DBm Scale§F.2.2VU Meters and the DBu ScaleF.4§F.2.2DBV Scale§F.2.2DB SPL§F.2.2DBA (A-Weighted DB)§F.2.2DB Full Scale (dBFS) for Spectrum Display§F.2.3Dynamic Range§F.3Voltage, Current, and Resistance§FExercises§GDigital Audio Number Systems§G.1Linear Number Systems§G.1Pulse Code Modulation (PCM)§G.1Binary Integer Fixed-Point Numbers§G.1One's Complement Fixed-Point Format§G.1Two's Complement Fixed-Point Format§G.1Two's-Complement, Integer Fixed-Point Numbers§G.1Fractional Binary Fixed-Point Numbers§G.1How Many Bits are Enough for Digital Audio?§G.1When Do We Have to Swap Bytes?G.5§G.2Logarithmic Number Systems for Audio§G.2Floating-Point Numbers§G.2Logarithmic Fixed-Point Numbers§G.2.3Mu-Law Coding§G.3Round-Off Error Variance§HMatrices§HMatrix Multiplication§HSolving Linear Equations Using Matrices§IMatlab/Octave Examples§I.1Complex Numbers in Matlab and Octave§I.1Complex Number Manipulation§IFactoring Polynomials in Matlab§I.3Geometric Signal Theory§I.3Vector Interpretation of Complex Numbers§I.3Signal Metrics§I.3Signal Energy and Power§I.3.1Inner Product§I.3.2Vector Cosine§I.3.3Projection§I.3.3Projection Example 1§I.3.3Projection Example 2§I.3.4Orthogonal Basis Computation§I.4The DFT§I.4.1DFT Sinusoids for \(N=8\)§I.4.2DFT Bin Response§I.4.3DFT Matrix§I.5Spectrogram ComputationBibliographyIndex for this DocumentAbout this document ...

5 exercise(s) for this page. Scroll down to try them!

even-odd-2

hw4a-even-odd-seq-a

hw4a-even-odd-seq-b

hw4a-even-odd-seq-c

mdftp-odd-part-0123

Get AI help understanding this page:

Ask Claude Ask ChatGPT Ask Gemini Ask Perplexity Ask Grok

Copies page context to clipboard, then opens AI in new tab. Just paste!