Properties of DFT (Summary and Proofs)

All of these properties of the discrete Fourier transform (DFT) are applicable for discrete-time signals that have a DFT. Meaning these properties of DFT apply to any generic signal x(n) for which an X(k) exists. (x(n) $\underleftrightarrow { \quad DFT\quad }$ X(k)) where $X(k)=\sum _{ n=0 }^{ N-1 }{ x(n){ e }^{ \frac { -j2\pi kn }{ N } } }$ .

Property	Mathematical Representation
Linearity	a₁x₁(n)+a₂x₂(n) $\underleftrightarrow { \quad DFT\quad }$ a₁X₁(k) + a₂X₂(k)
Periodicity	if x(n+N) = x(n) for all n then x(k+N) = X(k) for all k
Time reversal	x(N-n) $\underleftrightarrow { \quad DFT\quad }$ X(N-k)
Duality	x(n) $\underleftrightarrow { \quad DFT\quad }$ Nx[((-k))_N]
Circular convolution
Circular correlation	For x(n) and y(n), circular correlation r_xy(l) is r_xy(l) $\underleftrightarrow { \quad DFT\quad }$ R_xy(k) = X(k).Y*(k)
Circular frequency shift	x(n)e^2πjln/N $\underleftrightarrow { \quad DFT\quad }$ X(k+l) x(n)e^-2πjln/N $\underleftrightarrow { \quad DFT\quad }$ X(k-l)
Circular time shift	x((n-l))N = x(n-l) $\underleftrightarrow { \quad DFT\quad }$ X(k)e^-2πjlk/N or X(k)W^kl_Nwhere W is the twiddle factor.
Circular symmetries of a sequence	If the circular shift is in anti-clockwise direction (positive): Delayed discrete-time signal clockwise direction (negative): Advanced discrete-time signal Time reversal: Obtained by reversing samples of the discrete-time sequence about zero axis/locating x(n) in a clockwise direction.
Multiplication
Complex conjugate	x(n) $\underleftrightarrow { \quad DFT\quad }$ X(N-k)
Symmetry	For even sequences: X(k) = $\sum _{ n=0 }^{ N-1 }{ }$ x(n)Cos(2πnk/N) For odd sequences: X(k) = $\sum _{ n=0 }^{ N-1 }{ }$ x(n)Sin(2πnk/N)
Parseval’s theorem	$\sum _{ n=0 }^{ N-1 }{ }$ x(n).y(n) = $\frac { 1 }{ N } \sum _{ k=0 }^{ N-1 }{ }$ X(k).Y(k)

Proofs of the properties of the discrete Fourier transform

Linearity

Statements: The DFT of the linear combination of two or more signals is the sum of the linear combination of DFT of individual signals.

Proof: We will be proving the property:

a₁x₁(n)+a₂x₂(n)  a₁X₁(k) + a₂X₂(k)

We have the formula to calculate DFT:

X(k) = $\sum _{ n=0 }^{ N-1 }{ x(n){ { W }_{ N }^{ nk } } }$ where k = 0, 1, 2, … N-1.

Here x(n) = a1x1(n)+a2x2(n)

Therefore,

X(k) = $\sum _{ n=0 }^{ N-1 }{ [a1x1(n)+a2x2(n)]{ { W }_{ N }^{ nk } } }$

= $\sum _{ n=0 }^{ N-1 }{ a1x1(n){ { W }_{ N }^{ nk } } }$ + $\sum _{ n=0 }^{ N-1 }{ a2x2(n){ { W }_{ N }^{ nk } } }$

a1 and a2 are constants and can be separated, therefore,

= a1 $\sum _{ n=0 }^{ N-1 }{ x1(n){ { W }_{ N }^{ nk } } }$ + a2 $\sum _{ n=0 }^{ N-1 }{ x2(n){ { W }_{ N }^{ nk } } }$

= a1X1(k) + a2X2(k)

Hence, proved.

Periodicity

Statement: For a given DFT and IDFT pair, if the discreet sequence x(n) is periodic with a period N, then the N-point DFT of the sequence (i.e X(k)) is also periodic with the period of N samples.

Proof: We will be proving the property

if x(n+N) = x(n) for all n
then x(k+N) = X(k) for all k

According to the definition of DFT, we have,

X(k) = $\sum _{ n=0 }^{ N-1 }{ x(n){ { W }_{ N }^{ nk } } }$ where k = 0, 1, 2, … N-1.

To prove periodicity, put k = k+N

X(k+N) = $\sum _{ n=0 }^{ N-1 }{ x(n){ { W }_{ N }^{ n(k+N) } } }$

Rewriting,

$\sum _{ n=0 }^{ N-1 }{ x(n){ { W }_{ N }^{ n(k) } }{ { W }_{ N }^{ n(N) } } }$

Let’s calculate the twiddle factor

${ W }_{ N }^{ nN }$ = ${ e }^{ -j\frac { 2\pi nN }{ N } }=\quad { e }^{ -j2\pi n }$ = 1

Thus,

X(k+N) = X(k)

Hence, proved.

Time reversal

Statement: This property basically points to the circular folding of a sequence in a clockwise direction. When this is done, the DFT of the sequence will also get circularly folded.

Proof: We will be proving the property

x(N-n)  X(N-k)

x(N-n) = $\sum _{ p=0 }^{ N-1 }{ x(N-n){ e }^{ \frac { -j2\pi nk }{ N } } }$

Put N-n=p, that gives us n=N-p; substituting in the above equation we get,

DFT[x(N-n)] = $\sum _{ p=0 }^{ N-1 }{ x(p){ e }^{ \frac { -j2\pi (N-p)k }{ N } } }$

The lower limit will be the same since a DFT is periodic.

DFT [x(N-n)] = $\sum _{ p=0 }^{ N-1 }{ x(p){ e }^{ \frac { j2\pi pk }{ N } } { e }^{ \frac { -j2\pi Nk }{ N } }}$ ${ e }^{ j2\pi pk }$ = 1 for all k, thus,

DFT[x(N-n)] = $\sum _{ p=0 }^{ N-1 }{ x(p){ e }^{ \frac { j2\pi pk }{ N } } }$

= $\sum _{ p=0 }^{ N-1 }{ x(p){ e }^{ \frac { j2\pi pk }{ N } } { e }^{ \frac { -j2\pi N }{ N } }}$

where ${ e }^{ \frac { -j2\pi N }{ N } }$ = 1

Therefore,

DFT[x(N-n)] = $\sum _{ p=0 }^{ N-1 }{ x(p){ e }^{ \frac { -j2\pi p(N-k) }{ N } } }$

= X(N-k)

Hence, proved.

Duality

Statement: The DFT of a sequence can be used to find its finite duration sequence.

Proof: We will be proving the property

x(n)  Nx[((-k))_N]

Assume that x_p(n) is the periodic extension of a discrete-time sequence x(n). If the DFT of x(n) is X(k), we can say that the periodic extension of X(k) is X_p(k)

Thus we can write

x_pn $\underleftrightarrow { \quad DFT\quad }$ X_p(k)

Let’s define periodic sequence x₁_p(n) = X_p(n). Any random single period of this sequence (say x1(n)) will be a finite duration sequence that will be equal to x(n).

The DFT of x₁(n), X₁(k) is

Nx_p(-k) for 0<= k <= N-1; and 0 elsewhere

Here Nx_p(-k) is the discrete fourier series coefficients of x₁_p(n). Basically, Nx_p(-k) = X₁_p(k).

X₁(k) from the equation above can also be written as

X₁(k) = Nx[((-k))]_N for 0<= k <= N-1; and 0 elsewhere

Since X₁(k) is a DFT of x₁(n) and since x₁(n) is a finite duration sequence denoted by X(n), we can say that:

x(n) $\underleftrightarrow { \quad DFT\quad }$ Nx[((-k))_N]

Hence, proved.

Circular convolution

Statement: The multiplication of two DFT sequences is equivalent to the circular convolution of their sequences in the time domain. (Note that this is NOT the same as the convolution property.)

Proof: We will be proving the property

Consider x(n) and h(n) are two discrete time signals. Their N-point DFTs can be given as:

X(k) = $\sum _{ n=0 }^{ N-1 }{ x(n){ { W }_{ N }^{ nk } } }$ where k = 0, 1, 2, … N-1.

H(k) = $\sum _{ n=0 }^{ N-1 }{ h(n){ { W }_{ N }^{ nk } } }$ where k = 0, 1, 2, … N-1.

If we multiply them together we will get Y(k)

Y(k) = H(k).X(k) …. 1

If we find the IDFT of this:

y(m) = $\frac { 1 }{ N } \sum _{ k=0 }^{ N-1 }{ Y(k){ e }^{ \frac { j2\pi mk }{ N } } }$

Similarly, the convolution of the two DFTs will give us y(n)

y(n) = $\sum _{ m=0 }^{ N-1 }$ x(m)h(n-m)

Let’s put the DFT expansion of X(k) into equation 1

y(m) = $\frac { 1 }{ N } \sum _{ k=0 }^{ N-1 }{ X(k)H(k){ e }^{ \frac { j2\pi mk }{ N } } }$

Replacing X(k) with its expansion

y(m) = $\frac { 1 }{ N } \sum _{ k=0 }^{ N-1 }{ H(k)}$ $\sum _{ n=0 }^{ N-1 }$ $x(n)e^{ \frac { -j2\pi kn }{ N } }{ e }^{ \frac { j2\pi km }{ N } }$

y(m) = $\frac { 1 }{ N } \sum _{ k=0 }^{ N-1 }{ H(k)}{ e }^{ \frac { j2\pi (m-n)k }{ N } }$ $\sum _{ n=0 }^{ N-1 }{ x(n).N}$

which is equal to y(n) = $\sum _{ m=0 }^{ N-1 }$ x(m)h(n-m)

Hence, proved.

Circular correlation

Statement: The circular cross-correlation of two sequences in the time domain is equivalent to the multiplication of DFT of one sequence with the complex conjugate DFT of the other sequence.

Mathematical representation: For x(n) and y(n), circular correlation r_xy(l) is

r_xy(l) $\underleftrightarrow { \quad DFT\quad }$ R_xy(k) = X(k).Y*(k)

Circular frequency shift

Statement: Multiplication of a sequence by the twiddle factor or the inverse twiddle factor is equivalent to the circular shift of the DFT in the time domain by ‘l’ samples.

Proof: We will be proving the property

x(n)e^2πjln/N  X(k+l)
x(n)e^-2πjln/N  X(k-l)

We can generalize the above two and alternatively state that

x(n)e^2πjln/N  X((k-l))N = X(N+k-l)

DFT of x(n)e^2πjln/N = $\sum _{ n=0 }^{ N-1 }$ x(n)e^2πjln/N x e^-2πjkn/N

= $\sum_{ n=0 }^{ N-1 }$ x(n)e^2πjn(k-l)/N

= X((k-l))N

Hence, proved.

Circular time shift

Statement: Shifting the sequence in time domain by ‘l’ samples is equivalent to multiplying the sequence in frequency domain by the twiddle factor.

Proof: We will be proving the property

x(n-l) X(k)e^-2πjlk/N

According to DFT,

DFT [x(n)] = $\sum _{ n=0 }^{ N-1 }$ x(n) e^-2πjkn/N

DFT [x(n-l)] = $\sum _{ n=0 }^{ N-1 }$ x(n-l) e^-2πjkn/N

Let n-l=p

n=p+l

DFT [x(p)] = $\sum _{ p=0 }^{ N-1 }$ x(p) e^{-2πjk(p+l)/N}

= e^-2πjkl/N $\sum _{ p=0 }^{ N-1 }$ x(p) e^-2πjkp/N

= X(k)e^-2πjlk/N

Hence, proved.

Multiplication of two sequences

Statement: The multiplication of two sequences in the time domain is equivalent to their circular convolution in the frequency domain.

Mathematical representation:

Complex conjugate property

Statement: The DFT of a complex conjugate of any sequence is equal to the complex conjugate of the DFT of that sequence; with the sequence delayed by k samples in the frequency domain.

Proof: We will be proving the property

x*(n)  X*(N-k)

DFT [x*(n)] = $\sum _{ n=0 }^{ N-1 }$ x*(n) e^-2πjkn/N

= [ $\sum _{ n=0 }^{ N-1 }$ x*(n) e^-2πjkn/N]*

= [ $\sum _{ n=0 }^{ N-1 }$ x*(n) e^{-2πjn(N-k)/N}]*

= X*(N-k)

Hence, proved.

Symmetry

Statement: The DFT of an even sequence is purely real and even. DFT of an odd sequence is purely imaginary and odd.

Proof: We will be proving the properties:

For even sequences:

X(k) =  x(n)Cos(2πnk/N)

For odd sequences:

X(k) =  x(n)Sin(2πnk/N)

X(k) or X(ω) (depending on the expansion notation) is a complex quantity and can be written as:

X(ω) = X_R(ω) + jX_I(ω)

where X_R(ω) and X_I(ω) are the real and imaginary parts of X(ω) respectively.

X(ω) = $\sum _{ n= - \infty }^{ \infty }{ }$ x(n) ${ e }^{ -j\omega n }$

= $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)cosωn – j $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)sinωn

Comparing the above two equations we have:

X_R(ω) = $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)cosωn

and

X_I(ω) = – $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)sinωn

We know that cos(-ω)n = cosωn and sin(-ω)n=-sinωn

Putting -ω to check for even and odd signals

X_R(-ω) = $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)cos(-ω)n = $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)cosωn = X_R(ω)

Thus

X_R(-ω) = X_R(ω) (Even and real)

Similaryly for the imaginary part we get:

X_I(-ω) = $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)sin(-ω)n = – $\sum _{ n= - \infty }^{ \infty }{ }$ x(n)cosωn = -X_I(ω)

Thus

X_I(-ω) = X_I(ω) (Odd and imaginary)

Thus we can say

For even sequences:

X(k) = $\sum _{ n=0 }^{ N-1 }{ }$ x(n)Cos(2πnk/N)

For odd sequences:

X(k) = $\sum _{ n=0 }^{ N-1 }{ }$ x(n)Sin(2πnk/N)

Hence, proved.

3 thoughts on “Properties of DFT (Summary and Proofs)”

APC says:

May 9, 2023 at 10:28 PM

why are all images in black? Is it just for me the images are not loading?

1. Asem Syed says:
  
  September 7, 2023 at 11:29 AM
  
  I don’t see any images in black here
  
John Ladbury says:

October 16, 2021 at 2:18 AM

under periodicity, I think you have a lower case x when you should have a capitol X…you have “then x(k+N) = X(k) for all k” which doesn’t make sense. I think both should have a capitol X

Proofs of the properties of the discrete Fourier transform

Optical Fiber Comm. Course

Satellite Communication Course

Wireless & Mobile Communication Course