# Connexions

You are here: Home » Content » ECE 454 and ECE 554 Supplemental reading » INTRODUCTORY DISCRETE FOURIER TRANSFORM (DFT)

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• VOCW

This module is included inLens: Vietnam OpenCourseWare's Lens
By: Vietnam OpenCourseWare

Click the "VOCW" link to see all content affiliated with them.

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

Course by: Thad Welch. E-mail the author

# INTRODUCTORY DISCRETE FOURIER TRANSFORM (DFT)

Module by: Nguyen Huu Phuong. E-mail the author

## INTRODUCTORY DISCRETE FOURIER TRANSFORM (DFT)

In this chapter we have seen that the Continuous-Time Fourier Series (CTFS) relates the continuous periodic time to the discrete frequencies, and the Continuous-Time Fourier transform (CTFT) relates the continuous time to the continuous frequency, then the Discrete Time Fourier Series (DTFS) relates the discrete periodic time to the discrete frequencies, and, finally, the Discrete Time Fourier Transform (DTFT) relates the discrete time to the continuous frequency. The two latter representations differ from the two former in that they are size 12{2π} {} - periodic in the frequency domain due to the effect of the sampling in the time domain.

Although the DTFT is very useful for examing the frequency characteristic of discrete – time signals and systems, but there is a computational problem with it, i.e. its frequency representation is continuous. The Discrete Fourier Transform (DFT) fills up the time-frequency picture, it relates the discrete time to the discrete frequency. There is still the Fast Fourier Transform (FFT) which is the algorithm to compute the DFT. Both the DFT and FFT are really important tools to tackle many problems is DSP(DTSP). In this last section we present just a brief introduction to the DFT. They will be presented more fully in chapter 8.

## From the DTFT to the DFT

While the discrete sequence x(n) is discrete in time , its DTFT X(ω)X(ω) size 12{X $$ω$$ } {}is continuous and size 12{2π} {}-periodic in frequency ωω size 12{ω} {}, which is not convenient for computation on computers. So, the frequency variable ωω size 12{ω} {} must be discretized in one period [0,2π][0,2π] size 12{ $0,2π$ } {} and we then take the transform of these discrete frequencies.

First let’s repeat the DTFT pair here for comvenience (( Equation ) and ( Equation )):

(1)
(2)

For the sequence x(n) having N samples (time indices) we discretize at equal spaces the continuous frequency ωω size 12{ω} {} into the same N points in the interval [0,2π][0,2π] size 12{ $0,2π$ } {}:

ω k = 2π N k,k=0,1,2,...,N1 ω k = 2π N k,k=0,1,2,...,N1 MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabaGaciaacaqaaeaadaqaaqaaaOqaaiabeM8a3naaBaaaleaacaWGRbaabeaakiabg2da9maalaaabaGaaGOmaiabec8aWbqaaiaad6eaaaGaam4AaiaacYcacaaMc8UaaGjbVlaaywW7caWGRbGaeyypa0JaaGimaiaacYcacaaMe8UaaGymaiaacYcacaaMe8UaaGOmaiaacYcacaGGUaGaaiOlaiaac6cacaGGSaGaamOtaiabgkHiTiaaigdaaaa@520C@
(3)

These are the frequency samples .We take the summation from 0 to N-1 instead of from size 12{ - infinity } {}to size 12{ infinity } {} as in the DTFS, to get the DFT of x(n) :

(4)

This is the N- point DFT (analysis equation). X(k) is the spectral components. Notice that we write X(k) to mean X(ωk)X(ωk) size 12{X $$ω rSub { size 8{k} }$$ } {}, for short as many authors do . The exponent of the exponential is written as j(/N)knj(/N)kn size 12{ - j $$2π/N$$ ital "kn"} {}. Many authors write it as j2πkn/Nj2πkn/N size 12{ - j2π ital "kn"/N} {} for convenience, but our writing is more meaningful.

Since X(k) is discrete we don’t have to take the integral as in Equation 3 to recover the time sequence x(n), but rather a summation :

(5)

This is the inverse DFT (IDFT) (synthesis equation). X(k) and x(n) form the transform pair

The transform also applies to a systems represented by their impulse responses h(n):

(6)
(7)

It is interesting to compare the above N-point DFT with the DTFS of N samples ( Equation and Equation ). Besides the factor 1/N1/N size 12{ {1} slash {N} } {} appended to different equations , we see that they are just the same with the coefficients akak size 12{a rSub { size 8{k} } } {} in the place of the coefficients X(k)X(k) size 12{X $$k$$ } {}. The idea is that for a nonperiodic discrete sequence x(n) of N time samples , for which we must use the DTFT, we consider an infinitely long periodic sequence having the original x(n) as its period and then use the DTFS but with the new name DFT. If we compute the DFT equations outside the interval 0kN10kN1 size 12{0 <= k <= N - 1} {}and 0nN10nN1 size 12{0 <= n <= N - 1} {}we will have repeated values.

By reason of computational convenience the number N is usually taken as the integer power of 2 (i.e. N=2nN=2n size 12{N=2 rSup { size 8{n} } } {} with n integer). When the number of samples (data samples) is below such a number we use a technique called zero filling or zero padding , whereby we will fill up the vacant samples with zero so that the total samples will be equal to that integer power of 2.

Relating to the DFT we might wonder if the sampling of the frequency ωω size 12{ω} {} at N equal-distance points represents correctly the frequency variation . In parallel to the sampling theorem in time domain ( section ) , we have the sampling theorem in frequency domain which is stated as follows.

The continuous frequency spectrum of a signal existing in a finite time interval T0T0 size 12{T rSub { size 8{0} } } {} seconds can be represented completely by the frequency samples separated by a distance no more than 1/T01/T0 size 12{ {1} slash {T rSub { size 8{0} } } } {} Hertzs. The frequency sepectrum can then be recovered completely from the samples.

It can be checked that the previons sampling of N points does satisfy this theorem. Another way to check the legitimacy of the DFT pair is from the given transform X(k)X(k) size 12{X $$k$$ } {}we can recover x(n)x(n) size 12{x $$n$$ } {}. The problem is very similar to the case of CTFT ( section ), the difference is that in this case we use the orthogonality of discrete-time exponentials.

### Example 1

Find the N-point DFT of the following signal

(a) x(n)=δ(n)x(n)=δ(n) size 12{x $$n$$ =δ $$n$$ } {}

(b) x(n)=1x(n)=1 size 12{x $$n$$ =1} {}

(c) x(n)=anx(n)=an size 12{x $$n$$ =a rSup { size 8{n} } } {}

(d) x(n)=2cosω0nx(n)=2cosω0n size 12{x $$n$$ =2"cos"ω rSub { size 8{0} } n} {}

Solution

(a) X(k)=n=0N1δ(n)ejNkn=1ejNk0=1,k=0,1,2,...,N1X(k)=n=0N1δ(n)ejNkn=1ejNk0=1,k=0,1,2,...,N1 size 12{X $$k$$ = Sum cSub {n=0} cSup {N - 1} {δ $$n$$ e rSup { size 8{ - j { { size 6{2π} } over { size 6{N} } } ital "kn"} } } size 12{ {}=1e rSup { - j { { size 6{2π} } over { size 6{N} } } k rSub { size 6{0} } } } size 12{ {}=1, matrix { {} # {} } k=0,1,2, "." "." "." ,N - 1}} {}

(b) X(k)=n=0N11ejNknX(k)=n=0N11ejNkn size 12{X $$k$$ = Sum cSub {n=0} cSup {N - 1} {1e rSup { size 8{ - j { { size 6{2π} } over { size 6{N} } } ital "kn"} } } } {}

The summation has a value of N for k=0 and of zero for k0k0 size 12{k <> 0} {}, thus

X ( k ) = ( k ) X ( k ) = ( k ) size 12{X $$k$$ =Nδ $$k$$ } {}

(c) X(k)=n=0N1anejNkn=n=0N1(aejNk)nX(k)=n=0N1anejNkn=n=0N1(aejNk)n size 12{X $$k$$ = Sum cSub {n=0} cSup {N - 1} {a rSup { size 8{n} } e rSup { size 8{ - j { { size 6{2π} } over { size 6{N} } } ital "kn"} } } size 12{ {}= Sum cSub {n=0} cSup {N - 1} { $$ital "ae" rSup { - j { { size 6{2π} } over { size 6{N} } } k} size 12{$$ rSup {n} }} }} {}

Using the formula of finite geometric series ( Equation ) we obtain

X ( k ) = 1 b n 1 b , k = 0,1,2, . . . , N 1 X ( k ) = 1 b n 1 b , k = 0,1,2, . . . , N 1 size 12{X $$k$$ = { {1 - b rSup { size 8{n} } } over {1 - b} } , matrix { {} # {} } k=0,1,2, "." "." "." ,N - 1} {}

Where b stands for ejNkejNk size 12{e rSup { size 8{ - j { { size 6{2π} } over { size 6{N} } } k} } } {}.

(d) As usual, we express the cosinusoid in terms of exponentials:

x ( n ) = 2 cos ω 0 n = e 0 n + e ω 0 n x ( n ) = 2 cos ω 0 n = e 0 n + e ω 0 n size 12{x $$n$$ =2"cos"ω rSub { size 8{0} } n=e rSup { size 8{jω rSub { size 6{0} } n} } +e rSup { - ω rSub { size 6{0} } n} } {}

The DFT is

X ( k ) = n = 0 N 1 x ( n ) e j N kn = n = 0 N 1 e j ( N k ω 0 ) n + n = 0 N 1 e j ( k + ω 0 ) n X ( k ) = n = 0 N 1 x ( n ) e j N kn = n = 0 N 1 e j ( N k ω 0 ) n + n = 0 N 1 e j ( k + ω 0 ) n size 12{X $$k$$ = Sum cSub {n=0} cSup {N - 1} {x $$n$$ e rSup { size 8{ - j { { size 6{2π} } over { size 6{N} } } ital "kn"} } } size 12{ {}= Sum cSub {n=0} cSup {N - 1} {e rSup { - j $${ { size 6{2π} } over { size 6{N} } } k - ω rSub { size 6{0} }$$ n} } } size 12{+ Sum cSub {n=0} cSup {N - 1} {e rSup { - j $${ { size 6{2π} } over { size 6{k} } } +ω rSub { size 6{0} }$$ n} } }} {}

For convenience, let’s call a spectral coefficient k0k0 size 12{k rSub { size 8{0} } } {}corresponding to the given frequency ω0ω0 size 12{ω rSub { size 8{0} } } {}, satisfying :

N k 0 = ω 0 or k 0 = N N 0 N k 0 = ω 0 or k 0 = N N 0 size 12{ { {2π} over {N} } k rSub { size 8{0} } =ω rSub { size 8{0} } matrix { {} # {} # {} } ital "or" matrix { {} # {} # {} } k rSub { size 8{0} } = { {N} over {2π} } N rSub { size 8{0} } } {}

Rewrite the transform as

X ( k ) = n = 0 N 1 e j N ( k k 0 ) n + n = 0 N 1 e j N ( k + k 0 ) n X ( k ) = n = 0 N 1 e j N ( k k 0 ) n + n = 0 N 1 e j N ( k + k 0 ) n size 12{X $$k$$ = Sum cSub {n=0} cSup {N - 1} {e rSup { size 8{ - j { { size 6{2π} } over { size 6{N} } } $$k - k rSub { size 6{0} }$$ n} } } size 12{+ Sum cSub {n=0} cSup {N - 1} {e rSup { - j { { size 6{2π} } over { size 6{N} } } $$k+k rSub { size 6{0} }$$ n} } }} {}

The first summation equals to N when k=k0k=k0 size 12{k=k rSub { size 8{0} } } {}, and to zero when kk0kk0 size 12{k <> k rSub { size 8{0} } } {}. The second summation equals to N when k=Nk0k=Nk0 size 12{k=N - k rSub { size 8{0} } } {}, and to zero when kNk0kNk0 size 12{k <> N - k rSub { size 8{0} } } {}. Thus

For example with ω0=π/4ω0=π/4 size 12{ω rSub { size 8{0} } = {π} slash {4} } {} radians/sample then

k 0 = N π 4 = N 8 , N k 0 = 7N 8 k 0 = N π 4 = N 8 , N k 0 = 7N 8 size 12{k rSub { size 8{0} } = { {N} over {2π} } { {π} over {4} } = { {N} over {8} } , matrix { {} # {} # {} } N - k rSub { size 8{0} } = { {7N} over {8} } } {}

### Example 2

A causal filter has impulse response as

(a) Find the 4-point DFT of the impulse response.

(b) Taking the inverse DFT to see if we can recover the impulse response.

Solution

(a) The 4-point DFT of the impulse response is

H(k)= n=0 3 h(n) e j 2π 4 kn = n=0 3 h(n) e j π 2 kn ,k=0,1,2,3 H(k)= n=0 3 h(n) e j 2π 4 kn = n=0 3 h(n) e j π 2 kn ,k=0,1,2,3 MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaGaam4AaiaacMcacqGH9aqpdaaeWbqaaiaadIgacaGGOaGaamOBaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSqaaWqaaiaaikdacqaHapaCaeaacaaI0aaaaSGaam4Aaiaad6gaaaaabaGaamOBaiabg2da9iaaicdaaeaacaaIZaaaniabggHiLdGccqGH9aqpdaaeWbqaaiaadIgacaGGOaGaamOBaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSqaaWqaaiabec8aWbqaaiaaikdaaaWccaWGRbGaamOBaaaaaeaacaWGUbGaeyypa0JaaGimaaqaaiaaiodaa0GaeyyeIuoakiaacYcacaaMf8UaaGzbVlaadUgacqGH9aqpcaaIWaGaaiilaiaaigdacaGGSaGaaGOmaiaacYcacaaIZaaaaa@6744@

The computation is proceeded as follows.

H(1)= n=0 3 h(n) e j π 2 1n =h(0)+h(1) e j π 2 +h(2) e jπ +0=2j2 H(1)= n=0 3 h(n) e j π 2 1n =h(0)+h(1) e j π 2 +h(2) e jπ +0=2j2 MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaGaaGymaiaacMcacqGH9aqpdaaeWbqaaiaadIgacaGGOaGaamOBaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSaaaeaacqaHapaCaeaacaaIYaaaaiaaigdacaWGUbaaaaqaaiaad6gacqGH9aqpcaaIWaaabaGaaG4maaqdcqGHris5aOGaeyypa0JaamiAaiaacIcacaaIWaGaaiykaiabgUcaRiaadIgacaGGOaGaaGymaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSaaaeaacqaHapaCaeaacaaIYaaaaaaakiabgUcaRiaadIgacaGGOaGaaGOmaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbGaeqiWdahaaOGaey4kaSIaaGimaiabg2da9iaaikdacqGHsislcaWGQbGaaGOmaaaa@65E0@

H(3)= n=0 3 h(n) e j π 2 3n =h(0)+h(1) e j 3π 2 +h(2) e j 6π 2 +0=2+j2 H(3)= n=0 3 h(n) e j π 2 3n =h(0)+h(1) e j 3π 2 +h(2) e j 6π 2 +0=2+j2 MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaGaaG4maiaacMcacqGH9aqpdaaeWbqaaiaadIgacaGGOaGaamOBaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSaaaeaacqaHapaCaeaacaaIYaaaaiaaiodacaWGUbaaaaqaaiaad6gacqGH9aqpcaaIWaaabaGaaG4maaqdcqGHris5aOGaeyypa0JaamiAaiaacIcacaaIWaGaaiykaiabgUcaRiaadIgacaGGOaGaaGymaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSqaaWqaaiaaiodacqaHapaCaeaacaaIYaaaaaaakiabgUcaRiaadIgacaGGOaGaaGOmaiaacMcacaWGLbWaaWbaaSqabeaacqGHsislcaWGQbWaaSqaaWqaaiaaiAdacqaHapaCaeaacaaIYaaaaaaakiabgUcaRiaaicdacqGH9aqpcaaIYaGaey4kaSIaamOAaiaaikdaaaa@683C@

Remember H(k) is H( ω k ) H( ω k ) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaGaeqyYdC3aaSbaaSqaaiaadUgaaeqaaOGaaiykaaaa@3AFC@ with ω k = 2π N k ω k = 2π N k MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeM8a3naaBaaaleaacaWGRbaabeaakiabg2da9maalaaabaGaaGOmaiabec8aWbqaaiaad6eaaaGaam4Aaaaa@3E28@ hence H(0) is H(0) , H(1) is H( 2π 4 ) H( 2π 4 ) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaWaaSaaaeaacaaIYaGaeqiWdahabaGaaGinaaaacaGGPaaaaa@3B50@ or H( π 2 ) H( π 2 ) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaWaaSaaaeaacqaHapaCaeaacaaIYaaaaiaacMcaaaa@3A92@ , H(2) is H( 2π 4 2) H( 2π 4 2) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaWaaSaaaeaacaaIYaGaeqiWdahabaGaaGinaaaacaaIYaGaaiykaaaa@3C0C@ or H(π) H(π) MathType@MTEF@5@5@+=feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaGaeqiWdaNaaiykaaaa@39C5@ , H(3) is H( 2π 4 3) H( 2π 4 3) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaWaaSaaaeaacaaIYaGaeqiWdahabaGaaGinaaaacaaIZaGaaiykaaaa@3C0D@ or H( 3π 2 ) H( 3π 2 ) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaabIeacaGGOaWaaSaaaeaacaaIZaGaeqiWdahabaGaaGOmaaaacaGGPaaaaa@3B4D@ . The result is depicted in Figure 1. The four values of DFT are the samples of the corresponding continuous-frequency frequency response H(ω)H(ω) size 12{H $$ω$$ } {}given by the DTFT of the impulse response.

(b) Suppose now the continuous frequency response H(ω) H(ω) MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaadIeacaGGOaGaeqyYdCNaaiykaaaa@39D6@ is given and we sample it at 4 frequencies ω k =0,π/ 2,π, ω k =0,π/ 2,π, MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiabeM8a3naaBaaaleaacaWGRbaabeaakiabg2da9iaaicdacaGGSaGaaGjbVpaalyaabaGaeqiWdahabaGaaGOmaiaacYcacaaMe8UaeqiWdaNaaiilaaaaaaa@440C@ and 3π /2 3π /2 MathType@MTEF@5@5@+=feaagaart1ev2aqatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLnhiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVCI8FfYJH8YrFfeuY=Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfeaY=biLkVcLq=JHqpepeea0=as0Fb9pgeaYRXxe9vr0=vr0=vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaamaalyaabaGaaG4maiabec8aWbqaaiaaikdaaaaaaa@392F@ to get 4 values , respectively, 6, 2 – j2, 2 , and 2 + j2. From these values we take the inverse DFT to find the impluse response:

Thus

Continuing we will get back h(2) and h(3) as expected.

In part (a) if we evalue H(4) we will see it is equal to H(1), and in part (b) if we evaluate h(4) we will see it is equal to h(1). The reason is that H(k) is periodic and h(n) is assumed periodic. This example illustrates the frequency sampling method of FIR filter design ( sectionn ).

## Properties of the DFT

The discrete Fourier transform DFT has many properties similar to those of the discrete-time Fourier transform DTFT but with one basic difference as follows. Since the sequence x(n) is assumed to repeat itself indefinitely (this long sequence is periodic with x(n) its period) and the frequency sampling points in a frequency interval [0,2π][0,2π] size 12{ $0,2π$ } {} are repeated in other size 12{2π} {}-intervals, we will be concerned with circular shift instead of linear shift , and circular convolution instead of linear convolution. The properties and other aspects of the DFT , and the related FFT algorithm will be elaborated in chapter 8.

## Content actions

EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks