View Course Path

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 a1x1(n)+a2x2(n) \underleftrightarrow { \quad DFT\quad } a1X1(k) + a2X2(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 convolution property of DFT
Circular correlation For x(n) and y(n), circular correlation rxy(l) is

rxy(l) \underleftrightarrow { \quad DFT\quad } Rxy(k) = X(k).Y*(k)

Circular frequency shift x(n)e2π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)WklN where 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 multiplication property of dft
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:

a1x1(n)+a2x2(n) \underleftrightarrow { \quad DFT\quad }  a1X1(k) + a2X2(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) \underleftrightarrow { \quad DFT\quad }  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) \underleftrightarrow { \quad DFT\quad }  Nx[((-k))N]

Assume that xp(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 Xp(k)

Thus we can write

xpn \underleftrightarrow { \quad DFT\quad } Xp(k)

Let’s define periodic sequence x1p(n) = Xp(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 x1(n), X1(k) is

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

Here Nxp(-k) is the discrete fourier series coefficients of x1p(n). Basically, Nxp(-k) = X1p(k).

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

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

Since X1(k) is a DFT of x1(n) and since x1(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

circular convolution property of DFT

 

 

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 rxy(l) is

rxy(l) \underleftrightarrow { \quad DFT\quad } Rxy(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)e2πjln/N \underleftrightarrow { \quad DFT\quad }  X(k+l)
x(n)e-2πjln/N \underleftrightarrow { \quad DFT\quad }  X(k-l)

We can generalize the above two and alternatively state that

x(n)e2πjln/N \underleftrightarrow { \quad DFT\quad }  X((k-l))N = X(N+k-l)

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

=  \sum_{ n=0 }^{ N-1 }x(n)e2π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)\underleftrightarrow { \quad DFT\quad }  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: 

multiplication property of dft

 

 

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) \underleftrightarrow { \quad DFT\quad }  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) = \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)

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

X(ω) = XR(ω) + jXI(ω)

where XR(ω) and XI(ω) 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:

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

and

XI(ω) = – \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

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

Thus

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

Similaryly for the imaginary part we get:

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

Thus

XI(-ω) = XI(ω) (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.

 

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.