DFT properties

Screencast video [⯈]

In this section we will discuss the main DFT properties. We will see that most of these properties look similar to the properties of other Fourier transforms however there are some important differences which are caused by the fact that the DFT is a periodic, or circular, operation.

Circular shift

As one of the first consequences of the periodic behavior we need to pay special attention to the shift operation.

The two figures at the left hand side of Fig. 1 show a signals $x [n]$ and its shifted version $x [n - 1]$ which has been shifted over one sample to the right. More specifically the red sample at index $n = 0$ moves to index $n = 1$ and the blue sample at index $n = 3$ moves to index $n = 4$ . The two figures at the right hand side of Fig. 1 shows the Periodic Extended signal $x_{p} [n]$ , with period $N = 4$ samples, and its shifted version $x_{p} [n - 1]$ . From these figures it is clear that $x_{p} [n - 1]$ and $x [n - 1]$ are not the same. More specifically for $x_{p} [n - 1]$ the blue sample at index $n = 3$ is moved out the FP at the right hand side while it enters again at the left hand side at index $n = 0$ . This circular, or periodic, behavior can be represented by using modulo counting as follows: The samples denoted by $x_{p} [(n - 1) mod N]$ represent the samples in the FP of $x_{p} [n]$ which has been shifted over one sample.

For the proof of the circular shift property, we need an explicit expression for this modulo representation, which can be derived as follows:

Fig. 2 represents the time index axis $n$ which ranges from $- \infty$ until $+ \infty$ . One interval of the periodic extended signal $x_{p} [n]$ consists of $N$ samples and the indices of the FP range from $0$ until $N - 1$ . Now we shift $x_{p} [n]$ over $n_{0}$ samples, in which we assume for simplicity $n_{0} \leq 0$ .

An explicit expression for the indices of the samples of $x_{p} [n - n_{0}]$ within the FP can be found as follows:

As a first step we can represent the shifted sample at index $- n_{0}$ within the FP by adding $λ$ times $N$ , with $λ \in N$ . Then we must try to map $N$ consecutive samples into the FP. The samples in the red area map into the red area at the right hand side of the FP. In this range the samples are indexed by $n - n_{0} + λ N$ , as denoted in the following equation: $x_{p} [(n - n_{0}) mod (N)] = {\begin{cases} x_{p} [n - n_{0} + λ N] & index \in - \\ x_{p} [n - n_{0} + λ N - N] & index \in - \end{cases}$ In order to map the other samples, indicated in the blue area, inside the FP, an extra $N$ samples must be subtract, as denoted in the equation above.

The circular shift property states that a circular shift in time domain results in a multiplication with a complex exponent in frequency domain: $x_{p} [n - n_{0}] \circ - \circ e^{- j \frac{2 π}{N} k n_{0}} \cdot X_{p} [k]$

Proof of circular shift property

The DFT of the shifted samples

x_{p} [n - n_{0}]

is denoted as:

Y [k] = \sum_{n = 0}^{N - 1} x_{p} [n - n_{0}] e^{- j \frac{2 π}{N} k n} .

Now we can use the indexing as discussed above: Split the indices in a red and blue part. The red part contains the samples which are at the right end side of the FP and the blue part contains samples that are shifted outside the FP at the right end side and entering the FP again at the left end side:

\begin{array}{rcl} Y [k] & = & \sum_{\in -} x_{p} [n - n_{0} + λ N] e^{- j \frac{2 π}{N} k n} + \sum_{\in -} x_{p} [n - n_{0} + λ N - N] e^{- j \frac{2 π}{N} k n} \end{array}

Substitute a new index

m

and replace the index

n

with this new index in the complex exponent of both summations:

Y [k] = \sum_{m \in -} x_{p} [m] e^{- j \frac{2 π}{N} k (m + n_{0} - λ N)} + \sum_{m \in -} x_{p} [m] e^{- j \frac{2 π}{N} k (m + n_{0} - λ N + N)}

The complex exponent with index

n_{0}

can be taken outside brackets:

\begin{array}{rcl} Y [k] & = & (\sum_{m \in -} x_{p} [m] e^{- j \frac{2 π}{N} k m} e^{j \frac{2 π}{N} k λ N} + \sum_{m \in -} x_{p} [m] e^{- j \frac{2 π}{N} k m} e^{j \frac{2 π}{N} k (λ - 1) N}) e^{- j \frac{2 π}{N} k n_{0}} \\ = & (\sum_{m \in -} x_{p} [m] e^{- j \frac{2 π}{N} k m} + \sum_{m \in -} x_{p} [m] e^{- j \frac{2 π}{N} k m}) \cdot e^{- j \frac{2 π}{N} k n_{0}} \end{array}

The resulting two summations are the same but each of the indices run over a different part of the FP. When concatenating these two summations the result between brackets writes as the DFT result

X_{p} [k]

, which end the proof:

Y [k] = (\sum_{m \in FP} x_{p} [m] e^{- j \frac{2 π}{N} k m}) \cdot e^{- j \frac{2 π}{N} k n_{0}} = X_{p} [k] \cdot e^{- j \frac{2 π}{N} k n_{0}}

Try to prove yourself that, in a similar way, it can be shown that a circular shift in frequency domain results in a multiplication with a complex exponent in time domain:

e^{j \frac{2 π}{N} n k_{0}} \cdot x_{p} [n] \circ - \circ X_{p} [k - k_{0}]

Example

The values within the FI of the 5-point DFT of

x_{p} [n]

are:

X_{p} [k] = {\begin{cases} 5 & for k = 0 \\ 6 & for k = 1 \\ 1 & for k = 2 \\ 2 & for k = 3 \\ 9 & for k = 4 \end{cases}

A new signal is defined as

y_{p} [n] = W_{5}^{- 2 n} x_{p} [n]

, with twiddle factor

W_{5} = e^{j \frac{2 π}{5}}

. Calculate within the Fundamental Interval the values of

Y_{p} [k]

which is the 5-point DFT of this new signal

y_{p} [n]

According to the shift property we obtain:

\begin{array}{rcl} y_{p} [n] = e^{- j \frac{2 π}{5} 2 n} \cdot x_{p} [n] & \circ - \circ & Y_{p} [k] = X_{p} [k + 2]] \end{array}

resulting into the following values with the FI:

Y_{p} [k] = {\begin{cases} X_{p} [2] = 1 & for k = 0 \\ X_{p} [3] = 2 & for k = 1 \\ X_{p} [4] = 9 & for k = 2 \\ X_{p} [0] = 5 & for k = 3 \\ X_{p} [1] = 6 & for k = 4 \end{cases}

Circular convolution

The circular convolution, indicated by the symbol $⊛$ , between the two periodic extended signals $x_{p} [n]$ and $h_{p} [n]$ , both with an FP of $N$ samples, is defined as follows: $x_{p} [n] ⊛ h_{p} [n] = \sum_{i = 0}^{N - 1} x_{p} [i] h_{p} [n - i] = \sum_{i = 0}^{N - 1} x_{p} [n - i] h_{p} [i]$ The different steps of the circular procedure are as follows:

Eventually pad zeros in order to make the period of both periodic extended signals $x_{p} [n]$ and $h_{p} [n]$ the same.
Plot one of the signals, e.g. $h_{p} [n]$ , as function of another index, e.g. $h_{p} [i]$ .
Flip $h_{p} [i]$ to obtain $h_{p} [- i]$ .
For $n = 0, 1, \dots, N - 1$ : Calculate $y_p [n] = \sum_{i = 0}^{N - 1} x_{p} [i] h_{p} [n - i]$ .

As an example the circular convolution result

y_{p} [n] = x_{p} [n] ⊛ h_{p} [n]

is depicted in Fig. 3.

Within the FP these Periodic Extended signals are defined as: $\begin{array}{rcl} x_{p} [n] & = & δ [n] + δ [n - 1] + δ [n - 2] + \frac{1}{2} δ [n - 3] \\ h_{p} [n] & = & δ [n] + \frac{3}{4} δ [n - 1] + \frac{1}{2} δ [n - 2] + \frac{1}{4} δ [n - 3] \end{array}$ resulting in: $y_{p} [n] = x_{p} [n] ⊛ h_{p} [n] = \frac{17}{8} δ [n] + \frac{18}{8} δ [n - 1] + \frac{19}{8} δ [n - 2] + \frac{16}{8} δ [n - 3]$

Example

Compute

y_{p} [n] = x_{p} [n] ⊛ h_{p} [n]

with

\begin{array}{rcl} x_{p} [n] & = & δ [n mod (4)] + 2 δ [(n - 1) mod (4)] + δ [(n - 2) mod (4)] - δ [(n - 3) mod (4)] \\ h_{p} [n] & = & \frac{1}{3} δ [(n - 1) mod (4)] - \frac{1}{3} δ [(n - 2) mod (4)] + \frac{1}{3} δ [(n - 3) mod (4)] \end{array}

A matlab animation is to be added.

As in the FTD case it can be shown that for the DFT a circular convolution in time domain is equivalent to a circular multiplication in frequency domain: $x_{p} [n] ⊛ h_{p} [n] \circ - \circ X_{p} [k] \cdot H_{p} [k]$

Proof of circular convolution property

For the proof of this property we first apply the DFT operation to the circular convolution and then switch the order of the two summations:

\begin{array}{rcl} Y [k] & = & DFT {x_{p} [n] ⊛ h_{p} [n]} = \sum_{n = 0}^{N - 1} (\sum_{i = 0}^{N - 1} x_{p} [i] h_{p} [n - i]) e^{- j (2 π / N) k n} \\ = & \sum_{i = 0}^{N - 1} x_{p} [i] \cdot {\sum_{n = 0}^{N - 1} h_{p} [n - i] e^{- j (2 π / N) k n}} \end{array}

In between brackets we recognize the DFT of

h_{p} [n]

which has been shifted in time domain. As shown in the previous subsection the time domain shift results in a multiplication with a complex exponent in frequency domain:

Y [k] = \sum_{i = 0}^{N - 1} x_{p} [i] \cdot {H_{p} [k] \cdot e^{- j (2 π / N) k i}}

Moving the complex exponent forward finalizes the proof:

Y [k] = (\sum_{i = 0}^{N - 1} x_{p} [i] e^{- j (2 π / N) k i}) \cdot H_{p} [k] = X_{p} [k] \cdot H_{p} [k]

Try to prove yourself that, in a similar way, that a circular convolution in frequency domain is equivalent to a multiplication in time domain:

x_{p} [n] \cdot h_{p} [n] \circ - \circ X_{p} [k] ⊛ H_{p} [k]

Example

Given the same 4-point periodic extended signals as in the previous example:

\begin{array}{rcl} x_{p} [n] & = & δ [n mod (4)] + 2 δ [(n - 1) mod (4)] + δ [(n - 2) mod (4)] - δ [(n - 3) mod (4)] \\ h_{p} [n] & = & \frac{1}{3} δ [(n - 1) mod (4)] - \frac{1}{3} δ [(n - 2) mod (4)] + \frac{1}{3} δ [(n - 3) mod (4)] \end{array}

Furthermore we have the following 4-point DFT's:

X_{p} [k] \circ - \circ x_{p} [n]

and

H_{p} [k] \circ - \circ h_{p} [n]

. Calculate

Y_{p} [k] = X_{p} [k] \cdot H_{p} [k]

From the circular convolution property it follows that

Y_{p} [k] = X_{p} [k] \cdot H_{p} [k] \circ - \circ y_{p} [n] = x_{p} [n] ⊛ h_{p} [n]

From the previous example we have

y_{p} [n] = x_{p} [n] ⊛ h_{p} [n] = δ [(n - 1) mod (4)]

. Thus the answer equals the 4-point DFT of

y_{p} [n]

Y_{p} [k] = DFT {δ [(n - 1) mod (4)]} = e^{- j \frac{2 π}{4} k} .

Another way to find the solution is to write out the product of the two 4-point DFT's:

\begin{array}{rcl} X_{p} [k] & = & 1 + 2 e^{- j \frac{2 π}{4} k} + e^{- j \frac{2 π}{4} 2 k} - e^{- j \frac{2 π}{4} 3 k} \\ H_{p} [k] & = & \frac{1}{3} {e^{- j \frac{2 π}{4} k} - e^{- j \frac{2 π}{4} 2 k} + e^{- j \frac{2 π}{4} 3 k}} \end{array}

resulting in

Y_{p} [k] = X_{p} [k] \cdot H_{p} [k] = e^{- j \frac{2 π}{4} k}

Complex conjugation

The periodic behavior of the DFT operation leads to a special result of the complex conjugation operation: $x_{p}^{*} [n] \circ - \circ X_{p}^{*} [N - k]$

Proof of complex conjugation property

In the first step of the proof we apply the DFT operation to the complex conjugated samples and take the complex operation outside the brackets and multiply with 1:

Y [k] = \sum_{n = 0}^{N - 1} x_{p}^{*} [n] e^{- j \frac{2 π}{N} k n} = {(\sum_{n = 0}^{N - 1} x_{p} [n] e^{j \frac{2 π}{N} k n})}^{*} = {(\sum_{n = 0}^{N - 1} x_{p} [n] e^{j \frac{2 π}{N} k n} \cdot 1)}^{*}

The number 1 can be expressed as complex exponent

e^{- j \frac{2 π}{N} N n}

Y [k] = {(\sum_{n = 0}^{N - 1} x_{p} [n] e^{j \frac{2 π}{N} k n} \cdot e^{- j \frac{2 π}{N} N n})}^{*}

Combining the two exponents finalizes the proof:

{(\sum_{n = 0}^{N - 1} x_{p} [n] e^{- j \frac{2 π}{N} (N - k) n})}^{*} = X_{p}^{*} [N - k]

As a result of this property we can derive the following property when signal

x [n]

is real:

x [n] real \Rightarrow X_{p} [k] = X_{p}^{*} [N - k] .

Thus when

x [n]

is real we only need to calculate half of the DFT components, the other half can by obtained from the resulting symmetry property. More specifically the range of DFT coefficients that we need to calculate for a real signal is as follows:

$0 \leq k \leq (N - 1) / 2$ , for $N$ odd
$0 \leq k \leq N / 2$ , for $N$ even

Note that for $N$ even the coefficient $X_{p} [N / 2] = X_{p}^{*} [N / 2]$ . In other words $X_{p} [N / 2]$ is a real number.

Example

The even samples of the 9-point DFT

X_{p} [k]

of a real signal

x_{p} [n]

are given as follows:

X_{p} [0] = 1; X_{p} [2] = 5 - 2 j; X_{p} [4] = - 3 e^{- j \frac{π}{10}}; X_{p} [6] = 7; X_{p} [8] = 2 + 5 j

Calculate the odd values of

X_{p} [k]

Signal

x_{p} [n]

is real thus we have

X_{p} [k] = X^{*} [N - k]

which results in this case, with

N = 9

, in:

X_{p} [1] = X_{p}^{*} [8] = 2 - 5 j; X_{p} [3] = X_{p}^{*} [6] = 7; X_{p} [5] = X_{p}^{*} [4] = - 3 e^{j \frac{π}{10}}; X_{p} [7] = X_{p}^{*} [2] = 5 + 2 j

Example

Given the

N

-point DFT

X_{p} [k] = e^{j θ_{0}} δ [(k - 1) mod (N)] + e^{- j θ_{0}} δ [(k - (N - 1)) mod (N)]

in which

θ_{0}

is some fixed value. Calculate

x_{p} [n]

the

N

-point IDFT. The answer should be a formula for

x_{p} [n]

in terms of

n

and

N

. Is

x_{p} [n]

a real valued signal? If so simplify the resulting formula in such a way that it does not contain

j = \sqrt{- 1}

The resulting signal

x_{p} [n]

will be real since

X_{p} [k] = X_{p}^{*} [N - k]

and can be expressed as follows:

\begin{array}{rcl} x_{p} [n] & = & e^{j θ_{0}} \cdot e^{j \frac{2 π}{N} n} + e^{- j θ_{0}} \cdot e^{j \frac{2 π}{N} (N - 1) n} \\ = & e^{j θ_{0}} \cdot e^{j \frac{2 π}{N} n} + e^{- j θ_{0}} \cdot e^{- j \frac{2 π}{N} n} = 2 \cos (\frac{2 π}{N} n + θ_{0}) \end{array}

Preserve energy (Parceval)

$\sum_{n = 0}^{N - 1} | x_{p} [n] |^{2} = \frac{1}{N} \sum_{k = 0}^{N - 1} | X_{p} [k] |^{2}$

Proof of Parceval property

Parceval has shown that the Fourier transform preserves energy. Here we will show that this property also holds for the DFT. First we write out according to the DFT definition the term

X_{p}^{*} [k]

Y [k] = \frac{1}{N} \sum_{k = 0}^{N - 1} X_{p} [k] \cdot X_{p}^{*} [k] = \frac{1}{N} \sum_{k = 0}^{N - 1} X_{p} [k] \cdot {(\sum_{n = 0}^{N - 1} x_{p} [n] e^{- j \frac{2 π}{N} k n})}^{*}

Then bring the complex conjugation operation inside the brackets, change the order of the summations and combine the factor

\frac{1}{N}

before the second summation:

Y [k] = \frac{1}{N} \sum_{k = 0}^{N - 1} X_{p} [k] \cdot (\sum_{n = 0}^{N - 1} x_{p}^{*} [n] e^{j \frac{2 π}{N} k n}) = \sum_{n = 0}^{N - 1} x_{p}^{*} [n] \cdot {\frac{1}{N} \sum_{k = 0}^{N - 1} X_{p} [k] e^{j \frac{2 π}{N} k n}}

The second summation represents the Inverse DFT operation resulting in

x_{p} [n]

which finalizes the proof:

Y [k] = \sum_{n = 0}^{N - 1} x_{p}^{*} [n] \cdot {x_{p} [n]} = \sum_{n = 0}^{N - 1} | x_{p} [n] |^{2}

Note that it seems as if there is a difference of a factor

\frac{1}{N}

between the energy in time- and frequency domain. However this is the result of the way that the DFT and Inverse DFT operations have been defined.

Example

Show the Parceval relation for the 4-point Periodic Extended signal

x_{p} [n] = δ [n mod (4)] + δ [(n - 1) mod (4)] + δ [(n - 2) mod (4)] + δ [(n - 3) mod (4)] .

First we calculate the 4-point DFT:

X_{p} [k] = \sum_{n = 0}^{3} x_{p} [n] e^{- j \frac{2 π}{4} k n} = \sum_{n = 0}^{3} e^{- j \frac{2 π}{4} k n} = 4 δ [k mod (4)]

The energy in time- and frequency domain can be calculated as follows:

\begin{array}{rcl} Time & : & \sum_{n = 0}^{3} | x_{p} [n] |^{2} = (1^{2} + 1^{2} + 1^{2} + 1^{2}) = 4 \\ Frequency & : & \frac{1}{4} \sum_{k = 0}^{3} | X_{p} [k] |^{2} = \frac{1}{4} (4^{2}) = 4 \end{array}

which proves that the Parceval relation is indeed correct.

Last updated on May 30, 2020