### Notes of Digital Signal Analysis and Processing [CT 704]

#### Discrete Fourier Transform

DFT representation and properties

Discrete Fourier Transform

- It provides a frequency domain representation of a discrete time signal x[n].
- It converts sequence of numbers in time domain to another sequence of numbers in frequency domain.
- Mathematically, N point DFT of a sequence x[n] is given by:
X[k] = ∑k=0to N-1 {x[n] e-jkn.2π/N}
- The inverse fourier transform is given by:
x[n] = ∑k=0to N-1 {X[k] ejkn.2π/N}

Comparison of DFT and DTFT

- Discrete time fourier transform is given by:
X[w] = ∑k=-∞to∞ {x[n] e-jwn}

- Discrete fourier transform is given by:
X[k] = ∑k=0to N-1 {x[n] e-jkn.2π/N}

- This clearly shows that DFT is obtained from the samples of DTFT.

- DFT is better than DTFT because DTFT is a continuous function of frequency while DFT is frequency domain sample.

Frequency Domain Sampling

- According to definition of DTFT:
X[w] = ∑k=-∞to∞ {x[n] e-jwn}

- The range of w is from 0 to 2π or -π to π.

- It is not possible to compute X[w] on digital computer because of infinite range summation.

- X(w) is a continuous signal.

- A discrete signal is obtained by sampling X(w).

DFT as Linear Transformation

The DFT can be represented as a linear combination as shown below:

Properties of DFT

1. Periodicity
- If a discrete time signal is periodic then its DFT will also be periodic.
- If x[n] -------------> X[k], then:
x(n + N) = x(n) ; for all values of n
X(k + N) = X(k) ; for all values of k

2. Linearity
- DFT of linear combination of two or more signals is equal to the sum of linear combination of DFT of individual signals.
- If x1[n] ----> X1[k] and x2[n] ----> X2[k] ; then :
a x1[n] + b x2[n] -----------------> a X1[k] + b X2[k]

Circular Convolution

- The multiplication of two DFT's is equivalent to their circular convolution of their sequences in time domain.
- If x1[n] -----> X1[k] and x2[n] -----> X2[k], then:
x1[n] ⊗ x2[n] ----------> X1[k] . X2[k]
where,
⊗ indicates circular convolution.

Proof of Circular Convolution

```Let X3[k] = X1[k] . X2[k]
Then, by definition:
x3[m] = 1/N . ∑k=0to N-1 {X3[k] ejkm.2π/N}
= 1/N . ∑k=0to N-1 {{X1[k] . X2[k]} ejkm.2π/N}
= 1/N . ∑k=0to N-1 {{(∑n=0to N-1 {{x1[n] e-jkn.2π/N}) . (∑l=0to N-1 {x2[l] e-jkl.2π/N})} ejkm.2π/N}
= 1/N . ∑n=0to N-1 x1[n] . ∑n=0to N-1 x2[l] {∑k=0to N-1 ejk(m-n-l).2π/N}```

Let a = ej(m-n-l).2π/N :
We get,
∑k= 0 to N-1 ak = N ; for a = 1
= 0 ; for a != 1

For a = 1, (m-n-l) must be integer multiple of N.
m-n-l = pN
or, l = m-n-pN
or, l = ((m-n))N

So,
∑k=0to N-1 ejk(m-n-l).2π/N = N ; for l = ((m-n))N
= 0 ; elsewhere

Using this:
x3[m] = 1/N . ∑n= 0 to N-1 {N x1[n] x2((m-n))N}
= ∑n= 0 to N-1 {x1[n] x2((m-n))N}
= x1[n] ⊗ x2[n]

Fast Fourier Transform - Decimation in time and frequency algorithm

- Fast fourier transform (FFT) is an algorithm that allows computation of DFT of Discrete time signals faster.
- It makes use of symmetry of DFT calculation.

- In radix 2, N = 2v
where,
N = no of points
v = no of stages

- It can be computed by:
1. Radix-2 Decimation in time (DIT) Algorithm
2. Radix-2 Decimation in frequency (DIF) Algorithm

Computational Complexity of FFT

- For DFT,
N2 = complex multiplications
N2 - N = complex additions

- For FFT,
For one butterfly, one complex multiplication and 2 complex additions
No of butterfly in each stage = N/2
No of stages = log2N
So,
No of complex multiplications = N/2 . log2N
No of complex additions = N . log2N

- Complexity of DFT is of order O(N2).

- Complexity of FFT is of order O(N log2N).
{"ft_lang_label":"__label__en","ft_lang_prob":0.8052675,"math_prob":0.99883145,"size":3816,"snap":"2023-40-2023-50","text_gpt3_token_len":1346,"char_repetition_ratio":0.1156873,"word_repetition_ratio":0.045714285,"special_character_ratio":0.35455975,"punctuation_ratio":0.10320285,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99990654,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-06T23:49:48Z\",\"WARC-Record-ID\":\"<urn:uuid:bfbaab4f-2f8d-4e0d-8788-240b90138e41>\",\"Content-Length\":\"19383\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f3b1d5f3-1bfa-4820-9f17-e384aeee8b82>\",\"WARC-Concurrent-To\":\"<urn:uuid:259324e4-32ca-4153-934a-327c443ba99d>\",\"WARC-IP-Address\":\"104.21.91.181\",\"WARC-Target-URI\":\"https://ioesolutions.esign.com.np/notes/text-notes-show/Discrete-Fourier-Transform\",\"WARC-Payload-Digest\":\"sha1:WR7HFYBS6MZ7SSUBRWF6H2QKHKIAECQ7\",\"WARC-Block-Digest\":\"sha1:B7KFVBPHIMLWZMXODQPQX42FM3RGJV67\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100626.1_warc_CC-MAIN-20231206230347-20231207020347-00860.warc.gz\"}"}