PROPERTIES OF THE DFT

1. PRELIMINARIES (a) Denition (b) The Mod Notation (c) Periodicity of WN (d) A Useful Identity (e) Inverse DFT Proof (f) Circular Shifting (g) Circular Convolution (h) Time-reversal (i) Circular Symmetry 2. PROPERTIES (a) Perodicity property (b) Circular shift property (c) Modulation property (d) Circular convolution property (e) Parsevals theorem (f) Time-reversal property (g) Complex-conjugation property (h) Real x[n] property (i) Real and circularly symmetric x[n]

I. Selesnick

EL 713 Lecture Notes

DFT DEFINITION
The DFT of an N -point signal {x[n], 0 n N 1} is dened as
N 1

X [k ] =
n=0

kn x[n] WN ,

0k N 1

(1)

where WN = ej N = cos
2

2 N

+ j sin

2 N

is the principal N -th root of unity. The original sequence x[n] can be retrieved by the inverse discrete Fourier transform (IDFT) 1 x[n] = N
N 1 kn X [k ] WN , k=0

0 n N 1.

I. Selesnick

EL 713 Lecture Notes

THE MOD NOTATION

The notation k N denotes the remainder r when k is divided by N . This is also denoted as k mod N . For example 3
4

=3
4

and

= 2.

The following table shows k

for values of k from 0 to 7. k 0 1 2 3 4 5 6 7 . . . k 4 0 1 2 3 0 1 2 3 . . .

The notation k N is also dened for negative integers k . We choose the remainder r so that it is between 0 and N 1. 0 k For example, 3 = (1)(4) + 1 and 6 = (2)(4) + 2 so 6
4 N

N 1

so

=1

=2

I. Selesnick

EL 713 Lecture Notes

The following table shows k

for values of k from -8 to 7. k . . . 8 7 7 5 4 3 2 1 0 1 2 3 4 5 6 7 . . . k . . . 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 . . .

4

In MATLAB, we can generate k the code fragment: >> k=-8:7; >> [k, mod(k,4)] ans = -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5
I. Selesnick

using the command mod, as illustrated by

0 1 2 3 0 1 2 3 0 1 2 3 0 1
EL 713 Lecture Notes

6 7 Evidently k

2 3
N

is a periodic function of k with period N : k+N

N

= k

I. Selesnick

EL 713 Lecture Notes

PERIODICITY OF WN
Our denition of WN is WN := ej N . If we write k as k = l N + r with 0 r N 1 then we have k
k WN = ej N (lN +r)
2 2

= r and

= ej N (lN ) ej N r r = 1 WN = WN
k
N

k is a periodic function of k with a period of N . The identity Therefore WN k WN = WN k

N

is useful when working with the DFT. A related identity is

mk WN = WN m k
N

which is derived as
mk WN = ej N (m)(lN +r)
2 2

= ej N (mlN ) ej N mr mr = 1 WN = WN
m k
N

I. Selesnick

EL 713 Lecture Notes

A USEFUL IDENTITY
First, recall the geometric summation formula:
N 1

a =
n=0 k If a = WN , then we get: N 1 nk WN n=0 Nk = 1, this simplies to Because WN N 1 nk = WN n=0

aN 1 a1

a=1 a = 1.

N k 1 WN k 1 WN

k WN =1 k WN = 1.

0 N

k =1 WN k WN = 1.

k k Note that WN = 1 if k = 0, N, 2N, . . . . In other words WN = 1 if k N = 0. k Similarly WN = 1 if k N = 0. Therefore we can simplify the summation further to obtain: N 1 nk WN = n=0

0 N

k k

N N

=0 = 0.

Using the discrete-time delta function [n], dened as [n] = 0 1 n=0 n = 0,

we nally get the sought identity in the simple form:

N 1 nk WN = N [ k n=0 N ].

I. Selesnick

EL 713 Lecture Notes

INVERSE DFT PROOF

With the formula
N 1 nk WN = N [ k n=0 N]

we are ready to verify the the inverse DFT formula. To verify the inversion formula, we substitute the DFT into the inverse DFT formula: x[n] = 1 N
N 1 kn X [k ] WN k=0 N 1 N 1 kl x[l] WN k=0 N 1 l=0 N 1 kn , WN

1 x[n] = N 1 = N = 1 N

x[l]
l=0 N 1 k=0

WN

k(nl)

,
N ],

x[l] N [ n l
l=0

= x[n].

I. Selesnick

EL 713 Lecture Notes

CIRCULAR SHIFTING
Given an N -point signal {x[n], 0 n N 1}, the signal g [n] := x[ n m
N]

represents a circular shift of x[n] by m samples to the right. For example, if g [n] := x[ n 1 then g [0] = x[ g [1] = x[ g [2] = x[ . . . g [N 1] = x[ 1 N ] = x[N 1] 0 N ] = x[0] 1 N ] = x[1] N 2
N] N]

= x[N 2]

For example, if x[n] is the 4-point signal x[n] = (1, 3, 5, 2) then x[ n 1 x[ n m

N] N]

= (2, 1, 3, 5).

represents a circular shift by m samples.

The following MATLAB code fragment illustrates the circular shift. >> g = [1 3 5 2] g = 1 3 5 >> n = 0:3 n = 0 1 >> mod(n-1,4) 3 0

2 % Add 1 to account for MATLAB indexing 5

>> g(mod(n-1,4)+1) 2 1 3

Because indexing in MATLAB begins with 1 rather than with 0, it is necessary to add 1 to the index vector.
I. Selesnick EL 713 Lecture Notes

CIRCULAR CONVOLUTION
The usual convolution (or linear convolution) is dened as
N 1

x[n] g [n] :=
m=0

x[m]g [n m].

But when x[n] and g [n] are dened as N -point signals {x[n], 0 n N 1} and {g [n], 0 n N 1},

then the term g [n m] will fall outside the range. The denition of circular convolution evaluates the index modulo N :
N 1

x[n] g [n] :=
m=0

x[m]g [ n m

N ].

The following MATLAB function illustrates how the circular convolution can be computed.
function y = cconv(x,g) % y = cconv(x,g) N = length(x); n = 0:N-1; y = zeros(size(x)); for m = 0:N-1 y = y + x(m+1)*g(mod(n-m,N)+1); end

For example:
>> x = [2 4 3 1 5]; >> g = [7 3 5 2 4]; >> y = cconv(x,g) y = 56 73 57 60 69

I. Selesnick

EL 713 Lecture Notes

10

TIME-REVERSAL
Given an N -point signal {x[n], 0 n N 1}, the signal g [n] := x[ n is given by g [n] = as shown by: g [0] = x[ g [1] = x[ g [2] = x[ . . . g [N 1] = x[ 0 N ] = x[0] 1 N ] = x[N 1] 2 N ] = x[N 2] 1N
N] N]

x[0] x[N n]

n=0 1 n N 1.

= x[1].

For example, if x[n] is the 4-point signal x[n] = (1, 3, 5, 2) then x[ n

N]

= (1, 2, 5, 3).

The following MATLAB code fragment illustrates time-reversal for a 4-point signal.
>> g = [1 3 5 2] g = 1 3 5 2

>> N = 4; >> n = 0:N-1; >> g(mod(-n,N)+1) ans = 1 2 5 3

I. Selesnick

EL 713 Lecture Notes

11

CIRCULAR SYMMETRY
A discrete-time signal x[n] is symmetric if x[n] = x[n]. But if x[n] is an N -point signal {x[n], 0 n N 1}, then the sample x[n] falls outside the range. The denition of circular symmetry evaluates the index modulo N . An N -point signal x[n] is circularly symmetric if x[n] = x[ n For example, the sequences x[n] = (5, 3, 4, 2, 2, 4, 3) v [n] = (5, 3, 4, 2, 7, 2, 4, 3) are both circularly symmetric.
N ].

I. Selesnick

EL 713 Lecture Notes

12

PERIODICITY PROPERTY
Given the N -point signal {x[n], 0 n N 1}, we dened the DFT coecients X [k ] for 0 k N 1. But if k lies outside the range 0, . . . , N 1, then X [k ] = X [ k
N ].

To derive this equation, write k as k = l N + r with 0 r N 1. Then k N = r, and

N 1

X [k ] =
n=0 N 1

x[n] WN

n(lN +r)

=
n=0 N 1

n l N nr x[n] WN WN

=
n=0

nr x[n] WN

= X [r] = X[ k

N ].

If the DFT formula is evaluated for k outside the range 0 k N 1, then one nds that X [k ] is periodic with period N . Likewise, given the N -point DFT vector {X [k ], 0 k N 1}, we dened the Inverse DFT samples x[n] for 0 n N 1. But if n lies outside the range 0, . . . , N 1, then x[n] = x[ n
N ].

To derive this equation, write n as n = l N + r with 0 r N 1. Then k N = r, and 1 x[n] = N = = 1 N 1 N

N 1

X [k ] WN
k=0 N 1

k(lN +r)

kr klN X [k ] WN WN k=0 N 1 kr X [k ] WN k=0

= x[r] = x[ n

N ].

If the Inverse DFT formula is evaluated for n outside the range 0 n N 1, then one nds that x[n] is periodic with period N .
I. Selesnick EL 713 Lecture Notes

13

CIRCULAR SHIFT PROPERTY

If
mk G[k ] := WN X [k ]

then g [n] = x[ n m Derivation: Begin with the Inverse DFT. 1 g [n] = N = = 1 N 1 N

N 1 nk G[k ] WN k=0 N 1 mk nk WN X [k ] WN k=0 N 1 N ].

X [k ] WN
k=0

k(nm)

= x[n m] = x[ n m

N ].

The following MATLAB code fragment illustrates the circular shift property with a shift of 2 samples. property.
>> >> >> >> >> >> >> >> >> g = 2.0000 4.0000 3.0000 1.0000 5.0000 + 0.0000i 0.0000i 0.0000i 0.0000i 0.0000i x = [3 1 5 2 4]; N W X k m G g = = = = = = = length(x); % N: data length exp(2*pi/N*sqrt(-1)); fft(x); [0:N-1]; % frequency index 2; % shift W.^(-m*k) .* X; ifft(G)

I. Selesnick

EL 713 Lecture Notes

14

MODULATION PROPERTY (circular shift in frequency)

If
mn g [n] := WN x[n]

then G[k ] = X [ k m Derivation: Begin with the DFT.

N 1 N ].

G[k ] =
n=0 N 1

nk g [n] WN

=
n=0 N 1

nk mn WN x[n] WN

=
n=0

x[n] WN

n(km)

= X [k m] = X[ k m

N ].

I. Selesnick

EL 713 Lecture Notes

15

CIRCULAR CONVOLUTION PROPERTY

If
N 1

y [n] :=
m=0

x[m]g [ n m

N]

then Y [k ] = X [k ] G[k ]. Derivation:

N 1

Y [k ] = = =
m=0 N 1

nk y [n]WN n=0 N 1 N 1

n=0 m=0 N 1

x[m]g [ n m
N 1

nk N ]WN

x[m]
n=0

g[ n m

nk N ]WN

=
m=0

mk x[m]WN G[k ] N 1

= G[k ]
m=0

mk x[m]WN

= G[k ] X [k ] The following MATLAB code fragment illustrates the DFT convolution theorem.
>> x = [2 4 3 1 5]; >> g = [7 3 5 2 4]; >> cconv(x,g) ans = [ 56 73 57 60 69 ] >> ifft(fft(x).*fft(g)) ans = 56.0000 73.0000 57.0000 60.0000 69.0000
I. Selesnick

+ + -

0.0000i 0.0000i 0.0000i 0.0000i 0.0000i

EL 713 Lecture Notes

16

PARSEVALS THEOREM

N 1

x[n] g [n] =
n=0

1 N

N 1

X [k ] G [k ]
k=0

Derivation:
N 1 N 1

x[n] g [n] =
n=0 n=0

x[n] 1 N 1 N 1 N
N 1

1 N

N 1 nk G[k ]WN

k=0 N 1 nk G [k ]WN k=0 N 1

= = =

x[n]
n=0 N 1

G [k ]
k=0 N 1 n=0

nk x[n]WN

X [k ] G [k ]
k=0

The following MATLAB code fragment illustrates Parsevals theorem.

>> N = 4; >> x = randn(1,N) + i*randn(1,N) x = 0.7812 - 1.1878i

0.5690 - 2.2023i

-0.8217 + 0.9863i

-0.2656 - 0.5186i

>> g = randn(1,N) + i*randn(1,N) g = 0.3274 - 0.9471i >> X = fft(x); >> G = fft(g); >> sum(x.*conj(g)) ans = 1.9655 - 0.6644i >> sum(X.*conj(G))/N ans = 1.9655 - 0.6644i

0.2341 - 0.3744i

0.0215 - 1.1859i

-1.0039 - 1.0559i

I. Selesnick

EL 713 Lecture Notes

17

TIME-REVERSAL PROPERTY
If g [n] := x[ n then G[k ] = X [ k Derivation:
N 1 N ]. N]

G[k ] =
n=0 N 1

x[ n

nk N ]WN

=
m=0 N 1

x[m]WN

Nk

=
m=0

mk x[m]WN

= X [k ] = X [ k

N] N

where we used the change of variables m = n N (in which case n = m for 0 n N 1). The following MATLAB code fragment illustrates the time-reversal property.
>> >> >> >> >> >> g = 3.0000 7.0000 4.0000 2.0000 6.0000 - 0.0000i + 0.0000i + 0.0000i - 0.0000i N n x X G g = = = = = = 5; 0:N-1; [3 6 2 4 7]; fft(x); X(mod(-n,N)+1); ifft(G)

I. Selesnick

EL 713 Lecture Notes

18

COMPLEX CONJUGATION PROPERTY

If g [n] := x [n] then G[k ] := X [ k Derivation:
N 1 N]

G[k ] =
n=0

nk x [n]WN N 1 nk x[n]WN n=0

= X [k ] = X [ k

N]

The following MATLAB code fragment illustrates the complex conjugation property.
>> >> >> >> x = 3.0000 5.0000 6.0000 4.0000 8.0000 + + + 2.0000i 3.0000i 1.0000i 7.0000i 9.0000i N n i x = = = = 5; 0:N-1; sqrt(-1); [3+2*i 5-3*i 6+i 4-7*i 8+9*i].

>> X = fft(x); >> G = conj(X(mod(-n,N)+1)); >> g = ifft(G) g = 3.0000 5.0000 6.0000 4.0000 8.0000
I. Selesnick

+ + -

2.0000i 3.0000i 1.0000i 7.0000i 9.0000i

EL 713 Lecture Notes

19

REAL x[n] PROPERTY

x[n] real Equivalently, x[n] real =

X [k ] = X [ k

N ].

Xr [k ] = Xr [ k

N]

and Xi [k ] = Xi [ k

N ].

where Xr [k ] and Xi [k ] are the real and imaginary parts of X [k ]. Derivation:

x[n] real

= = =

x[n] = x [n] DFT{x[n]} = DFT{x [n]} X [k ] = X [ k N ].

The following MATLAB code fragment illustrates the circular symmetries present in the DFT of a real signal. In this case, the signal is of odd length. Notice that Xi (0) must be 0 because when k is 0, the relation X [k ] = X [ k N ] gives Xi [0] = Xi [0] .
>> x = [3 7 5 2 4 1 5] x = 3 7 5 2 4 1 5 >> X = fft(x) X = 27.0000 3.7409 -1.3351 -5.4058 -5.4058 -1.3351 3.7409
I. Selesnick

+ + +

4.5956i 1.7780i 4.2094i 4.2094i 1.7780i 4.5956i

EL 713 Lecture Notes

20

>> [real(X) imag(X)] ans = 27.0000 3.7409 -1.3351 -5.4058 -5.4058 -1.3351 3.7409 0 -4.5956 -1.7780 4.2094 -4.2094 1.7780 4.5956

In the following example, the signal is of even length. Notice that Xi (N/2) = 0 in this case.
>> x = [3 7 5 2 4 1 3 2] x = 3 7 5 2 4 1 3 2 >> X = fft(x) X = 27.0000 3.2426 -1.0000 -5.2426 3.0000 -5.2426 -1.0000 3.2426

- 6.2426i - 4.0000i - 2.2426i + 2.2426i + 4.0000i + 6.2426i

>> [real(X) imag(X)] ans =

I. Selesnick

EL 713 Lecture Notes

21

27.0000 3.2426 -1.0000 -5.2426 3.0000 -5.2426 -1.0000 3.2426

0 -6.2426 -4.0000 -2.2426 0 2.2426 4.0000 6.2426

I. Selesnick

EL 713 Lecture Notes

22

Real and Circularly Symmetric x[n]

When x[n] is real and circularly symmetric, then so is the DFT. {x[n] real and x[n] = x[ n Derivation: x[n] real and x[n] = x[ n Therefore {x[n] real and x[n] = x[ n
N ]} N] N ]}

{X [k ] real and X [k ] = X [ k

N ]}

X [k ] = X [ k

N]

= =

DFT{x[n]} = DFT{x[ n X [k ] = X [ k N ].

N ]}

= =

X [k ] = X [ k N ] = X [ k N ] X [k ] real and X [k ] = X [ k N ].

The following example illustrates the DFT of a real circularly symmetric signal.
>> x = [3 1 5 4 6 4 5 1] x = 3 1 5 4 6 4 5 1 >> X = fft(x) X = 29.0000 -7.2426 -1.0000 1.2426 9.0000 1.2426 -1.0000 -7.2426

- 0.0000i - 0.0000i + 0.0000i + 0.0000i

Note that both x[n] and X [k ] are real and circularly symmetric.
I. Selesnick EL 713 Lecture Notes

23

Summary of DFT Properties

Periodicity Circular Shift Modulation Circular Convolution Time-Reversal Complex Conjugation Parsevals Theorem X [k ] = X [ k N ] x[ n m N ] mn WN x[n] x[n] g [n] x[ n N ] x [n] N 1 n=0 x[n] g [n] = x[n] = x[ n N ] mk WN X [k ] X[ k m N ] X [k ] G[k ] X [ k N ] X [ k N ] N 1 k =0 X [k ] G [k ]

1 N

I. Selesnick

EL 713 Lecture Notes

24