# Connexions

You are here: Home » Content » Discrete Fourier Transform

### Recently Viewed

This feature requires Javascript to be enabled.

# Discrete Fourier Transform

Module by: CHARAN MYSORE SRINIVAS. E-mail the author

Summary: This module introduces you to the concept of Discrete fourier transform

## Introduction

The discrete Fourier transform (DFT) is a fundamental transform in digital signal processing, with applications in frequency analysis, fast convolution, image processing, etc. Moreover, fast algorithms exist that make it possible to compute theDFTvery efficiently. The algorithms for the efficient computation of the DFT are collectively called fast Fourier transforms (FFTs). The historic paper by Cooley and Tukey [15] made well known an FFT of complexity N log2 N, where N is the length of the data vector. A sequence of early papers [3, 11, 13, 14, 15] still serves as a good reference for the DFT and FFT. In addition to texts on digital signal processing, a number of books devote special attention to the DFT and FFT [4, 7, 10, 20, 28, 33, 36, 39, 48].

The importance of Fourier analysis in general is put forth very well by Leon Cohen [12]:

. . . Bunsen and Kirchhoff, observed (around 1865) that light spectra can be used for recognition, detection, and classification of substances because they are unique to each substance.

The kth DFT coefficient of a length N sequence {x(n)} is defined as

## The DFT Matrix

The DFT of a length N sequence {x(n)} can be represented as a matrix-vector product. For example, a length 5 DFT can be represented as

X0X1X2X3X4=( 11111 1WWDid not convert matrixrow/degreeWW )x0x1x2x3X4 X 0 X 1 X 2 X 3 X 4 1 1 1 1 1 1 W W 2 W W x 0 x 1 x 2 x 3 X 4

It is very useful to illustrate the entries of the matrix FN as in Fig. 2.1, where each complex value is shown as a vector. In Fig. 2.1, it can be seen that in the kth row of the matrix the elements consist of a vector rotating clockwise with a constant increment of 2πk/N. In the first row k = 0 and the vector rotates in increments of 0. In the second row k = 1 and the vector rotates in increments of 2π/N.

## DFT Frequency Analysis

To formalize the type of frequency analysis accomplished by the DFT, it is useful to view each DFT value {X(k)} as the output of a length N FIR filter hk(n). The output of the filter is given by the convolution sum

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

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

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