Theory

Part1

Properties of Discrete Fourier Transform

In this experiment, we consider some of the properties of DFT for finite-duration sequence and rest will be tabulated in table. Mainly, we are going to explain linearity and circular shift properties of DFT.

Linearity Property

If x₁(n) and x₂(n) have N-point DFTs X₁(k)and X₂(k), respectively,

$$ ax_1(n) + bx_2(n) \stackrel{\text{DFT}}{\Longleftrightarrow} ax_1(k) + bx_2(k) $$

In using this property, it is important to ensure that the DFTs are the same length. If x₁(n)and x₂(n) have different lengths, the shorter sequence must be padded with zeros in order to make it the same length as the longer sequence. For an example, if x₁(n) is of length N1 and x₂(n) is of length N2 with N2 > N1. x₁(n) may be considered to be a sequence of length N2 with the last N2-N1 values equal to zero, and DFTs of length N2 may be taken for both sequences.

Circular time and frequency shift

If X(k) is the N-point DFT of x(n), then if we apply N-point DFT on time shifted (circular) sequence i.e. x(n-m), where m is a positive integer, then the according to circular time shift property:

$$DFT[X((n-m))N]=X(k)e^-{(\frac{j2\pi km}{N})}$$

Similarly,

$$DFT[X((n))^\frac{ei2\pi mn}{N}]=X((K-M))N|$$

It means, if we multiply a complex exponential sequence e^(i2Πmn/N) with the sequence x(n) in time domain is equivalent to the circular shift of the DFT by m units in frequency domain. This property is called circular frequency shift property of DFT

Periodicity property

If x(n) and X(k) are an N-point DFT pair, then

x(n+N)=x(N) for all n

x(K+N)=X(K) for all k

These periodicities in x(n) and X(k) follow immediatly for the DFT and IDFT, respectively

We previously illustrated the periodicity property in the sequence x(n) for a given DFT. However, we had not previously viewed the DFT X(k) as a periodic sequence. In some applications it is advantageous to do this.

Time reversal of a sequence

If x(n) and X(k) are an N-point DFT pair, then

DFT[x((-n))N]=DFT[X(N-n)]=x((-k))N=X(N-K)

Hence reversing the N-point sequence in time is equivalent to reversing the DFT values

Circular convolution

The multiplication of DFTs of two sequences is equivalent to the circular convolution of the two sequences in the time domain

If

$$DFT[X_1(N)]=X_1(K)$$

$$DFT[X_2(N)=X_2(K)]$$

$$x_1(n)(N)x_2(n)=x_1(k)x_2(k)$$

(N) is the symbol for circular convolution of two sequences i.e. x₁(n) and x₂(n)

Parseval's Theorem

For complex-valued sequences x(n) and y(n), in general, if

DFT[x(n)]=X(k)

DFT[y(n)]=x(k)

Then

$$\sum_{n=0}^{N-1}x(n)y*(n)=\frac{1}{N} \sum_{k=0}^{N-1}x(k)Y*(k)$$

This expression is the general form of Parseval's theorem. In the special where y(n) = x(n), reduced to

$$\sum_{n=0}^{N-1}|x(n)|^2=\frac{1}{N} \sum_{k=0}^{N-1}|x(k)|^2$$

which expresses the energy in the finite-duration sequence x(n) in term of the frequency components {X(k)}.