Periodic, Circular, and Modulo-N Operations

Properties of The Discrete Fourier Transform

Digital Signal Processing

The Discrete Fourier Transform (DFT)

Michael Ibrahim

Spring 2019

Michael Ibrahim Digital Signal Processing 1/26

 Periodic, Circular, and Modulo-N Operations
Properties of The Discrete Fourier Transform

Periodic, Circular, and Modulo-N Operations

The DFT treats the N-point signal x[n] and its DFT
coefficients X [k] as primary periods of periodic sequences x̃[n]
and X̃ [k], respectively.
Another way to visualize this inherent periodicity is to wrap
the N-point sequence x[n] around a cylinder with a
circumference equal to the sequence length as illustrated in
the next figure.
Traveling around the circle once, starting at n = 0, yields the
N-point sequence x[n].

Michael Ibrahim Digital Signal Processing 2/26

 Periodic, Circular, and Modulo-N Operations
Properties of The Discrete Fourier Transform

Periodic, Circular, and Modulo-N Operations

If we keep repeatedly going around the circle, we obtain the

periodic extension x̃[n] of x[n].
Geometrically, the finite-duration sequence x[n] is recovered
by unwrapping the cylinder and laying it flat so that the
circular time-axis is mapped on the linear time-axis.
The relation between the linear time-index (n) and the circular
time-index (r ), known as modulo-N operation, is defined by

n = `N + r , 0 ≤ r ≤ (N − 1)

⇒
hniN , n modulo N = r

Michael Ibrahim Digital Signal Processing 3/26

 Periodic, Circular, and Modulo-N Operations
Properties of The Discrete Fourier Transform

Periodic, Circular, and Modulo-N Operations

Michael Ibrahim Digital Signal Processing 4/26

 Periodic, Circular, and Modulo-N Operations
Properties of The Discrete Fourier Transform

Periodic, Circular, and Modulo-N Operations

n = `N + r ⇒ (n modulo N): choose ` such that r is always a

positive integer in the range 0 ≤ r ≤ (N − 1)
For instance, if N = 4 ..
n -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
hni4 0 1 2 3 0 1 2 3 0 1 2 3 0
That is hniN is periodic with period N ...

hn + NiN = hniN ∀n

Michael Ibrahim Digital Signal Processing 5/26

 Periodic, Circular, and Modulo-N Operations
Properties of The Discrete Fourier Transform

Periodic, Circular, and Modulo-N Operations

This allows us to express the periodic extension x̃[n] of a

finite-length N-point sequence x[n], 0 ≤ n ≤ (N − 1), as
follows
x̃[n] = x [hniN ] ∀n

x̃[−n] = x [h−niN ] ∀n

Also ..
X̃ [k] = X [hkiN ] ∀k

X̃ [−k] = X [h−kiN ] ∀k

Michael Ibrahim Digital Signal Processing 6/26

 Periodic, Circular, and Modulo-N Operations
Properties of The Discrete Fourier Transform

Periodic, Circular, and Modulo-N Operations

In Matlab: r = mod(n,N)
The inherent periodicity imposed by the N-point DFT X [k] of
a finite-length N-point sequence x[n] can be dealt with using
one of the following techniques:
1 The periodic extension (x̃[n], X̃ [k]).
2 The circular mapping (x [hniN ] , X [hkiN ]) operations.

Michael Ibrahim Digital Signal Processing 7/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Linearity

Let x1 [n] and x2 [n] be finite-duration sequences having lengths

N1 and N2 respectively.
The linear combination

y [n] = a1 x1 [n] + a2 x2 [n]

has a maximum length Ny = max(N1 , N2 )

The N-point DFT of y [n], where N ≥ Ny is given by

1 −1
NX 2 −1
NX
Y [k] = a1 x1 [n]WNkn + a2 x2 [n]WNkn
n=0 n=0

Michael Ibrahim Digital Signal Processing 8/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Linearity

The first summation is the N-point DFT of x1 [n], that is x1 [n]

is padded by (N − N1 ) zeros and then the DFT is computed.
The second summation is the N-point DFT of x2 [n], that is
x2 [n] is padded by (N − N2 ) zeros and then the DFT is
computed.
Thus we can write

Y [k] = a1 X1 [k] + a2 X2 [k], 0 ≤ k ≤ (N − 1)

where
X1 [k] is the N-point DFT of x1 [n],
X2 [k] is the N-point DFT of x2 [n],
and N must satisfy the condition N ≥ max(N1 , N2 )

Michael Ibrahim Digital Signal Processing 9/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Folding

The operation z[n] = x[−n] of time-reversal (or time-folding)

is not defined when x[n] is unavailable outside the range
0 ≤ n ≤ (N − 1).
However, based on the inherent periodicity of the DFT, we
can define this operation in a mathematically consistent way
using the periodic extension x̃[n].

Michael Ibrahim Digital Signal Processing 10/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Folding

Michael Ibrahim Digital Signal Processing 11/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Folding

x[n] x [h−ni8 ]

Michael Ibrahim Digital Signal Processing 12/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Folding

The circular folding can be performed in three steps:

1 Generation of the periodic extension x̃[n]
2 Time-reversal about n = 0 to obtain z̃[n] = x̃[−n]
3 Extraction of a single period of z̃[n] to obtain the desired
sequence z[n] = z̃[n]pN [n].
The same result is obtained, in a single step, by wrapping the
sequence x[n] around a cylinder clockwise, and reading the
sequence (as usual) counterclockwise.

Michael Ibrahim Digital Signal Processing 13/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Folding

This operation, which is known as circular folding, is defined

by
(
x[0] n=0
z[n] = x [h−niN ] ,
x[N − n] 1 ≤ n ≤ (N − 1)

Please note that, the time-reversed sequence z[n] is also

defined for 0 ≤ n ≤ (N − 1)
The sample x[0] remains at its position and the remaining
samples are arranged in reverse order, that is, we have
x[0], x[N − 1], ..., x[2], x[1].

Michael Ibrahim Digital Signal Processing 14/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Folding

The circular time-reversal property of the DFT is

N-DFT
x [h−niN ] ←−−−−→ X [h−kiN ]

which also results in a circular folding (or frequency-reversal)

of X [k] and is defined in a similar manner as follows
(
X [0] k=0
X [h−kiN ] ,
X [N − k] 1 ≤ k ≤ (N − 1)

Michael Ibrahim Digital Signal Processing 15/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Symmetry

Circular Even Symmetry

x[n] = x [h−niN ]
(
x[0] n=0
=
x[N − n] 1 ≤ n ≤ (N − 1)

Circular Odd Symmetry

x[n] = −x [h−niN ]
(
0 n=0
=
−x[N − n] 1 ≤ n ≤ (N − 1)

Michael Ibrahim Digital Signal Processing 16/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Symmetry Properties of the DFT

N-DFT
x ∗ [n] ←−−−−−−→ X ∗ [h−kiN ]

N-DFT
x ∗ [h−niN ] ←−−−−−−→ X ∗ [k]

If x[n] is real-valued

X [k] = X ∗ [h−kiN ]

That is
X [k] = X [h−kiN ]

and
X [k] = − X [h−kiN ]
Michael Ibrahim Digital Signal Processing 17/26
 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Symmetry Properties of the DFT

Using these symmetry properties we can calculate the DFT of two

real-valued sequences using only one DFT operation. How ?
Let x1 [n], and x2 [n] be two real-valued N-point sequences
with DFTs X1 [k] and X2 [k].
If we form a complex-valued sequence x[n] as

x[n] = x1 [n] + jx2 [n]

and let’s compute its DFT X [k].

Michael Ibrahim Digital Signal Processing 18/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Symmetry Properties of the DFT

Then we can use the following DFT property

N-DFT
x ∗ [n] ←−−−−−−→ X ∗ [h−kiN ]

⇒
1
x1 [n] = [x[n] + x ∗ [n]]
2
Using the linearity property
1
X1 [k] = [X [k] + X ∗ [h−kiN ]]
2

Michael Ibrahim Digital Signal Processing 19/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Symmetry Properties of the DFT

Similarly for x2 [n] ...

1
x2 [n] = [x[n] − x ∗ [n]]
2j
Using the linearity property
1
X2 [k] = [X [k] − X ∗ [h−kiN ]]
2j

Thus, using only one DFT computation,we get the DFTs of

two real-valued sequences.

Michael Ibrahim Digital Signal Processing 20/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Shift

Michael Ibrahim Digital Signal Processing 21/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Shift

The circular shift can be expressed mathematically using the

periodic extension of x[n] as follows

x̃[n − m], −∞ < n < ∞

Or, equivalently, the circular shift can be expressed

mathematically using the modulo-N operation as follows

x [hn − miN ] , 0 ≤ n ≤ (N − 1)

Michael Ibrahim Digital Signal Processing 22/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Shift

The circular time shift property is given as follows ...

N-DFT
x [hn − miN ] ←−−−−−−→ WNkm X [k]

If m > 0 ⇒ counterclockwise rotation by m steps ⇒ x̃[n] is

shifted to the right by m steps.
If m < 0 ⇒ clockwise rotation by m steps ⇒ x̃[n] is shifted to
the left by m steps.

Michael Ibrahim Digital Signal Processing 23/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Shift

Michael Ibrahim Digital Signal Processing 24/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Circular Shift

Similarly, the circular frequency shift property is given as

follows ...

N-DFT
WN−mn x[n] ←−−−−−−→ X [hk − miN ]

In Matlab / GNU-Octave
s h i f t ( x n , m) ;

Please use fft and ifft in Matlab/ GNU-Octave to verify these

properties.

Michael Ibrahim Digital Signal Processing 25/26

 Linearity
Circular Folding
Periodic, Circular, and Modulo-N Operations
Symmetry Properties of the DFT
Properties of The Discrete Fourier Transform
Circular Shift
Other Properties

Other Properties

Duality
N-DFT
X [n] ←−−−−−−→ N · x [h−kiN ]

Parseval’s theorem

N−1 N−1
X 1 X
x[n]y ∗ [n] = X [k]Y ∗ [k]
N
n=0 k=0

Michael Ibrahim Digital Signal Processing 26/26