2The Discrete Fourier Transform

The discrete Fourier transform (DFT) is introduced when the Fourier transform of a function is to be calculated using a digital computer. This type of processor can handle only numbers and, in a quantity limited by the size of its memory. It follows that the Fourier transform:

upper S left-parenthesis f right-parenthesis equals integral Subscript minus infinity Superscript infinity Baseline s left-parenthesis t right-parenthesis e Superscript minus normal j Baseline 2 pi italic f t Baseline normal d t

must be adapted, by replacing the signal s(t) with the numbers s(nT) which represent a sample of the signal, and by limiting to a finite value N the set of numbers on which the calculations are carried out. The calculation then provides numbers S*(f) defined by

upper S asterisk left-parenthesis f right-parenthesis equals sigma-summation Underscript n equals 0 Overscript upper N minus 1 Endscripts s left-parenthesis italic n upper T right-parenthesis e Superscript minus normal j Baseline 2 italic pi fnT

As the computer has limited processing power, it can only provide results for a limited number of values of the frequency f, and it is natural to choose multiples of a certain frequency step Δf. Thus,

upper S asterisk left-parenthesis k normal upper Delta f right-parenthesis equals sigma-summation Underscript n equals 0 Overscript upper N minus 1 Endscripts s left-parenthesis italic n upper T right-parenthesis e Superscript minus normal j Baseline 2 pi italic n k normal upper Delta italic fT

The conditions under which the calculated values form a good approximation to the required values are examined below. An interesting simplifying choice is to take Δf = 1/NT. Then there are only N different values of S*(k/NT), which is a periodic set of period N since:

upper S asterisk left-bracket left-parenthesis k plus upper N right-parenthesis slash italic upper N upper T right-bracket equals upper S asterisk left-parenthesis k slash italic upper N upper T right-parenthesis

On the other hand, the transform thus calculated ...

Get Digital Signal Processing, 10th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial