Discrete Fourier Transform Properties

Contents

Introduction

Earlier equations for the direct and inverse Discrete Fourier Transform were got. Give them once again:

$$
S(k) = \text{DFT} \big[ s(n) \big] = \sum_{n=0}^{N-1} s(n) \cdot \exp \left( -j \cdot \frac{2 \pi}{N} \cdot n \cdot k \right) = \sum_{n=0}^{N-1} s(n) \cdot W_{N}^{n \cdot k} \text{;}
$$
$$
s(n) = \text{IDFT} \big[S(k) \big] = \frac{1}{N} \cdot \sum_{k=0}^{N-1} S(k) \cdot \exp \left( j \cdot \frac{2 \pi}{N} \cdot n \cdot k \right) = \sum_{k=0}^{N-1} S(k) \cdot W_{N}^{-n \cdot k} \text{;}
$$
$$
W_{N}^{n \cdot k} = \exp \left( -j \cdot \frac{2 \pi}{N} \cdot n \cdot k
\right) \text{; } n = 0 \ldots N-1 \text{; } k = 0 \ldots N-1 \text{,}
$$

(1)

where $\text{DFT}\big[ \bullet \big]$ is a DFT operator, and $\text{IDFT}\big[\bullet \big]$ is an inverse DFT operator, and $W_N^{n \cdot k}$ bear the name of DFT twiddle factors. Here and elsewhere in this section it is considered that $n = 0 \ldots N-1$ and $k = 0 \ldots N-1$ index temporal and spectrum samples respectively.

In this section some DFT properties will be considered.

DFT Linearity

DFT of the signals sum is equal to the DFT sum of these signals. If $s(n)=x(n) + y(n),$ then:

$$
S(k) = \text{DFT} \big[ s(n) \big] = \text{DFT} \big[ x(n) + y(n) \big] =
$$
$$
= \sum_{n = 0}^{N-1} \big(x(n) + y(n) \big) \cdot W_N^{n \cdot k} = \sum_{n = 0}^{N-1} x(n) \cdot W_N^{n \cdot k} + \sum_{n = 0}^{N-1} y(n) \cdot W_N^{n \cdot k} =
$$
$$
= X(k) + Y(k) \textrm{, } k = 0\ldots N-1,
$$

(2)

where $X(k)$ and $Y(k)$ are the DFT of signals $x(n)$ and $y(n)$ respectively.

Upon multiplying the signal by the constant $a$, the signal DFT is also multiplied by the constant:

$$
S(k) = \text{DFT} \big[ a \cdot x(n) \big] = a \cdot X(k).
$$

(3)

DFT of Signal with Circular Shifting in Time

Let $S(k)$ be the DFT signal $s(n)$.
If we shift the pickup signal $s(n)$ cyclically to $m$ samples, i.e. $x(n) = s(n-m),$
then the DFT of the shifted signal is equal to:

$$
X(k) = \text{DFT} \big[s(n-m) \big] = \sum_{n=0}^{N-1}s(n-m) \cdot W_N^{n\cdot k},
\text{ } k=0 \ldots N-1.
$$

(4)

Introduce the variable change $n-m=r$, then $n = m+r$ and (4) can be written as follows:

$$
X(k) = \sum_{r = 0}^{N-1} s(r) \cdot W_N^{(r+m)\cdot k} =
\sum_{r = 0}^{N-1} s(r) \cdot W_N^{r\cdot k} \cdot W_N^{m\cdot k} =
$$
$$
=S(k) \cdot \exp \left(-j \cdot \frac{2 \pi}{N} \cdot m \cdot k \right) = S(k) \cdot W_N^{m \cdot k}.
$$

(5)

Thus, the circular signal shifting to $m$ samples leads to the phase spectrum rotating while the amplitude spectrum does not change.

Equation (5) is correct only for circular shifting which example is shown in Figure 1.

Figure 1. Example of Circular Signal Shifting

The red color in the upper chart is for the pickup signal $s(n)$, in the average one there is $s(n)$ with circular shifting $m=-3$ samples (with advancing), and in the lower chart there is $s(n)$,
shifted to $m=3$ samples (with delay). It is obvious that in case of circular shifting with advancing the first $m$ samples are transferred from the beginning to the end of the capture. In case of delay the last $m$ samples are transferred from the end of the capture to the beginning.

DFT of Signals Circular Convolution

Let the signal $s(n)$ be the result of circular convolution of signals $a(n)$ and $b(n)$:

$$
s(n)=\sum_{m=0}^{N-1}a(m) \cdot b(n-m).
$$

(6)

Calculate the DFT signal $s(n)$:

$$
S(k)= \text{DFT} \big[s(n) \big] = \sum_{n=0}^{N-1} \left(\sum_{m=0}^{N-1}a(m) \cdot b(n-m) \right) \cdot W_N^{n \cdot k}.
$$

(7)

Change the positions of summing operations:

$$
S(k)= \sum_{m=0}^{N-1} a(m) \cdot \underbrace{\sum_{n=0}^{N-1} b(n-m) \cdot W_N^{n \cdot k}}_{B(k) \cdot W_N^{m \cdot k}}=
$$
$$
=\sum_{m=0}^{N-1} a(m) \cdot B(k) \cdot W_N^{m \cdot k} = B(k) \cdot \sum_{m=0}^{N-1} a(m)\cdot W_N^{m \cdot k} = B(k) \cdot A(k).
$$

(8)

Upon deriving (8) the circular temporal shifting property was used.

Thus, the circular convolution DFT of two signals is equal to the DFT cut product of these signals. This property allows to use algorithms of fast Fourier transform to calculate convolutions of signals.

DFT of Signals Circular Convolution

Let the signal $s(n)$ be equal to the cut product of signals $a(n)$ and $b(n)$,
i.e. $s(n)= a(n) \cdot b(n)$, at that $A(k)$ and $B(k)$ are the DFT of signals $a(n)$ and $b(n)$ respectively.
Then the signal DFT $s(n)$ is equal to:

$$
S(k) = \sum_{n=0}^{N-1} s(n) \cdot W_N^{n \cdot k} = \sum_{n=0}^{N-1} a(n) \cdot b(n) \cdot W_N^{n \cdot k}.
$$

(9)

Substitute $a(n)$ in (9) in the form of the IDFT of the spectrum $A(k)$:

$$
S(k) = \sum_{n=0}^{N-1} a(n) \cdot b(n) \cdot W_N^{n \cdot k}
= \sum_{n=0}^{N-1} \left( \frac{1}{N} \sum_{m=0}^{N-1} A(m) \cdot W_N^{-m \cdot n} \right) \cdot b(n) \cdot W_N^{n \cdot k}.
$$

(10)

Change the positions of summing operations in (10) and get:

$$
S(k) = \frac{1}{N} \sum_{m=0}^{N-1} A(m) \cdot \underbrace{ \sum_{n=0}^{N-1} b(n) \cdot W_N^{(k-m) \cdot n} }_{B(k-m)}= \frac{1}{N} \sum_{m=0}^{N-1} A(m) \cdot B(k-m).
$$

(11)

Thus, the DFT of the signals cut product represents the DFT circular convolution of these signals.

Property of the DFT Circular Shifting in Frequency

Let $S(k)$ be the signal DFT $s(n)$.
Perform the spectrum circular shifting $S(k-m)$
and consider the IDFT, then:

$$
x(n) = \dfrac{1}{N} \cdot \sum_{k=0}^{N-1} S(k-m) \cdot W_N^{-k \cdot n}= \left| {{r = k-m} \atop {k = r+m}} \right| = \frac{1}{N} \cdot \sum_{r =0}^{N-1}S(r) \cdot W_N^{-(r+m) \cdot n} =
$$
$$
= \underbrace{\frac{1}{N} \cdot \sum_{r =0}^{N-1}S(r) \cdot W_N^{-r \cdot n}}_{s(n)} \cdot W_N^{-m \cdot n} =
s(n) \cdot \exp \left( j \cdot \frac{2\pi}{N} \cdot m \cdot n \right).
$$

(12)

Thus, the DFT circular shifting in frequency is carried out by multiplying the signal by the complex exponent. It is important to note that after multiplying by the complex exponent of a real-valued signal, the resulting signal will be complex, and its spectrum will stop being symmetric.

DFT Symmetry of a Real-Valued Signal

If the pickup signal is real, i.e. $\Im[s(n)] = 0$ is for $n = 0 \ldots N-1$,
then for even $N$ it is:

$$
S\left(\frac{N}{2}\right) = \sum_{n=0}^{N-1} s(n) \cdot
\exp\left( - j\cdot\frac{2\pi}{N}\cdot n\cdot \frac{N}{2} \right) =
$$

$$ = \sum_{n=0}^{N-1} s(n)\cdot \exp\left( - j \cdot n \cdot \pi \right) = \sum_{n=0}^{N-1} \left(-1\right)^n \cdot s(n) . $$

$$ = \sum_{n=0}^{N-1} s(n)\cdot \exp\left( - j \cdot n \cdot \pi \right) = \sum_{n=0}^{N-1} \left(-1\right)^n \cdot s(n) . $$

(13)

The spectrum sample $S\left( \frac{N}{2} \right)$ has also no imaginary component.

Now consider $S(m),$ $m=1 \ldots \frac{N}{2} - 1$ and $S(N-m)$:

$$
S\left(N-m\right) = \sum_{n=0}^{N-1} s(n) \cdot
\exp\left( - j\cdot\frac{2\pi}{N}\cdot n\cdot (N-m) \right)
=
$$
$$
= \sum_{n=0}^{N-1} s(n)\cdot \exp\left( - j\cdot 2 \pi \cdot n \right) \cdot
\exp\left( j\cdot \frac{2 \pi}{N} \cdot n \cdot m \right).
$$

(14)

Take into account that $\exp(-j \cdot 2 \pi \cdot n) = 1$ is for any integer $n$.
In this case:

$$
S(N-m) = S^{*}(m),\text{ } m=1 \ldots {\frac{N}{2}} - 1, \textrm{ For even }N;
$$

$$ S(N-m) = S^{*}(m),\text{ } m=1 \ldots {\frac{N-1}{2}} - 1, \textrm{ For odd }N; $$

$$ S(N-m) = S^{*}(m),\text{ } m=1 \ldots {\frac{N-1}{2}} - 1, \textrm{ For odd }N; $$

(15)

i.e. the second half of spectrum samples is conjugated with the first one in a complex way.

The form of the real and imaginary components of the real signal complex spectrum under even $N$ are presented in Figure 2a.
Just real-valued $S(0)$ and $S \left(\frac{N}{2} \right)$ spectrum components are marked as red.

Figure 2. Real and imaginary components of the real DFT signal

The real and imaginary components of the real signal complex spectrum under odd $N$ are presented in Figure 2b.
Under odd $N$ only the first DFT spectrum sample of the real-valued signal is real-valued. In the general case other spectrum samples are complex.

Spectrum Frequency Inversion of a Real-Valued Signal for Even $N$

Frequency signal spectrum inversion is shown in Figure 3 for even $N$.

If $S(k)$ is a signal spectrum $s(n)$, then the inverse spectrum $S_{\rm{inv}}(k)$ is equal to:

$$
S_{\rm{inv}}(k) = \begin{cases}
S\left(k + \frac{N}{2} \right), &\text{if $k = 0 \ldots \frac{N}{2}-1$;}\\
S\left(k - \frac{N}{2} \right), &\text{if $k = \frac{N}{2} \ldots N-1.$}
\end{cases}
$$

(16)

Due to the DFT symmetry of the real-valued signal we can perform the frequency signal spectrum inversion by shifting spectrum components.

Consider the inverse spectrum $S_{\rm{inv}}(k)$ for $k = 0 \ldots \frac{N}{2}-1$:

Figure 3. DFT Frequency Inversion

of the Real-Valued Signal for Even $N$

of the Real-Valued Signal for Even $N$

$$
S_{\rm{inv}}(k) = S \left( k + \frac{N}{2}\right) =
$$
$$
=\sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{\left( k+ \frac{N}{2}\right) \cdot n}
= \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{k \cdot n} \cdot W_{N}^{\frac{N}{2} \cdot n} =
$$
$$
= \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{k \cdot n} \cdot \exp \left( -j \cdot \frac{2\pi}{N} \cdot \frac{N}{2} \cdot n \right) =
$$
$$
= \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{k \cdot n} \cdot \exp \left( -j \cdot \pi \cdot n \right) =
$$
$$
= \sum_{n = 0}^{N-1}(-1)^n \cdot s(n) \cdot W_{N}^{k \cdot n}, \text{ } k = 0 \ldots \frac{N}{2}-1.
$$

(17)

Likewise $S_{\rm{inv}}(k)$ for $k = \frac{N}{2} \ldots N-1$ is equal to:

$$
S_{\rm{inv}}(k) = S \left( k - \frac{N}{2}\right) = \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{\left( k- \frac{N}{2}\right) \cdot n}
= \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{k \cdot n} \cdot W_{N}^{-\frac{N}{2} \cdot n} =
$$
$$
= \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{k \cdot n} \cdot \exp \left( j \cdot \frac{2\pi}{N} \cdot \frac{N}{2} \cdot n \right)
= \sum_{n = 0}^{N-1}s(n) \cdot W_{N}^{k \cdot n} \cdot \exp \left( j \cdot \pi \cdot n \right) =
$$
$$
= \sum_{n = 0}^{N-1}(-1)^n \cdot s(n) \cdot W_{N}^{k \cdot n}, \text{ } k = \frac{N}{2} \ldots N-1.
$$

(18)

Thus, for frequency inversion of the real-valued spectrum signal it is necessary to multiply every second sample by $-1$ according to (16). At the same time it is important to note that it is necessary to multiply samples beginning with the second, i.e. for $n = 1,3,5,7, \dots$, because indexation of samples begins with $n = 0$.
If we multiply every second sample beginning with the first by $-1$, we will get the inverse spectrum with a negative sign $-S_{\rm{inv}}(k)$.

Note that (18) is correct only for even $N$.

It is shown in Figure 4 that frequency spectrum inversion corresponds to the circular spectrum shifting in frequency to $\frac{N}{2}$ spectrum samples by advancing or delay.

Figure 4. Frequency Spectrum Signal Inversion due to the DFT Shifting in Frequency

Then according to the frequency spectrum shifting property (12) the signal with the inverse spectrum is equal to:

$$
s_{\rm{inv}}(n) = s(n) \cdot \exp \left( j \cdot \frac{2\pi}{N} \cdot \frac{N}{2} \cdot n\right) = s(n) \cdot \exp \big( j\cdot \pi\cdot n\big) = \left(-1\right)^n \cdot s(n).
$$

(19)

The zero DFT sample

The zero DFT sample is the sum of signal samples.

$$
S(0) = \sum_{n-0}^{N-1}s(n).
$$

(20)

Duality Property

We have considered the main DFT properties. The DFT have one more remarkably property: the duality property the essence of which is that all DFT properties are correct either for temporal or for frequency signal representation.

For example, it is possible to consider the DFT property of circular convolution which says: the DFT of signal circular convolution is the DFT cut product of convolved signals. At the same time it can be formulated invertedly: the DFT cut product of signals is DFT circular convolution of these signals.

It is also possible to reformulate the frequency shifting property. So, the shifting in time leads to multiplying the spectrum by the complex exponent while multiplying the signal by the complex exponent leads to the circular spectrum shifting in the frequency area.

Conclusions

In this section we considered the main DFT properties: linearity, properties of temporal and frequency shiftings, convolution spectrum and cut product of signals, and we analyzed spectrum and signal inversion. There is also shown the DFT duality allowing to formulate properties simultaneously for frequency and for temporary signal representation.

You can provide your any feedbacks, questions and wishes in the message board or guestbook.

Reference

[1]
Bracewell R.N.
The Fourier Transform and its Applications.
McGraw Hill, Singapor, 2000.

[2]
Oppenheim Alan V. and Schafer Ronald W.
Discrete-Time Signal Processing
Second Edition.
Prentice-Hall, New Jersey, 1999.

[3]
Robert J. Marks II
The Joy of Fourier:
Analysis, Sampling Theory, Systems, Multidimensions, Stochastic
Processes, Random Variables, Signal Recovery, Pocs, Time
Scales, & Applications.
Baylor University, 2006.

[4]
Nussbaumer Henri J.
Fast Fourier Transform and Convolution Algorithms.
Second Corrected and Updated Edition.
Springer-Verlag, 1982.

Select spelling error with your mouse and press |