8 Key excerpts on "Discrete Fourier Transform"

• 

  eBook - ePub

  Encyclopedia of Image Processing

  • Phillip A. Laplante, Phillip A. Laplante(Authors)
  • 2018(Publication Date)
  • CRC Press

    (Publisher)

  Discrete Fourier Transforms Dave K. Kythe

  Security Leader & Advisor, Los Angeles, California, U.S.A .

  Prem K. Kythe

  University of New Orleans, New Orleans, Louisiana, U.S.A .

  Abstract

  The Discrete Fourier Transform (DFT) is one of the most important algorithms for processing digital signals, including images. It has many other applications as well in virtually all important engineering domains. In this article the DFT is introduced and many of its important properties are examined.

  Keywords: Algorithm; DFT; Discrete Fourier Transform

  Discrete Fourier Transform

  The Discrete Fourier Transform (DFT) that transforms one function into another is called the frequency domain representation ; it requires a discrete input function whose nonzero real or complex values are finite. Unlike the discrete-time Fourier transform (DIFT), the DFT only evaluates enough frequency components to reconstruct the finite segment that was analyzed. The DFT is used in processing information (data) stored in computers, and in signal processing and related fields where the frequencies in a signal are analyzed. An efficient computation of the DFT is provided by a fast Fourier transform (FFT) algorithm. Although DFT refers to a mathematical transformation while FFT refers to a specific family of algorithms for computing DFTs, the FFT algorithms commonly used to compute DFTs often mean DFT in common terminology, which has now become confusing by taking FFT as synonymous with DFT. For more details, see Kythe and Schäferkotter

  [1 ]

  [2005: 299 ff]. The DFT is defined as follows: Let a sequence of n nonzero complex numbers

  {

  x 0

  , … ,  

  x

  n − 1

  }

  be transformed into a sequence of m complex numbers

  {

  X 0

  , … ,  

  X

  m − 1

  }

  by the formula

  X j

    =  

  ∑

  k = 0

  n − 1

  x k

  e

  − 2 π j k   i / m

     for    0     ≤     j     ≤     m − 1 ;   i     =  

  − 1

  ,

  ⁢ ( 1 )

  where

  x k

  =

  1 m

  ∑

  j = 0

  m − 1

  X j

  e

  2 π k j   i / m

  ⁢  

    for       0 ≤ k ≤ n − 1 .

  ⁢ ( 2 )

  Formula (1) is known as the DFT analysis equation and its inverse (2) the DFT synthesis equation, or the inverse Discrete Fourier Transform

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Signal Processing 101

  Everything You Need to Know to Get Started

  • Michael Parker(Author)
  • 2017(Publication Date)
  • Newnes

    (Publisher)

  Chapter 10

  Discrete and Fast Fourier Transforms (DFT, FFT)

  Abstract

  This chapter covers both Discrete Fourier Transform (DFT) and it's more efficient form, the fast Fourier transform (FFT). These transforms provide a means to convert time domain signals into frequency domain, and their inverse forms allow for the reversal. The DFT is covered in detail, as this is one of the most fundamental building blocks in digital signal processing. The FFT is a dramatically more efficient method to compute the DFT, and this is what is used in practice. Practical implementation issues such as bit growth as well as bit reversal addressing are also discussed.

  Keywords

  Butterfly; DFT; FFT; Frequency spectrum; IFFT; Twiddle factors

  Many of us have heard the term “FFT.” In this chapter, we are going to discuss the DFT (Discrete Fourier Transform) and its more popular cousin, the FFT (Fast Fourier Transform). We will again try to approach this intuitively, although a bit of math is unavoidable. This chapter will make liberal use of the complex exponential, so if you are not comfortable with this, you may want to review Chapter 4 .

  The key is to understand the DFT operation. The FFT is simply a highly optimized implementation of the DFT. They both produce identical results. While the implementation of the FFT is interesting, unless you are actually building it, you do not really need to know the details. As the FFT is such a basic building block in DSP, there are many implementations already available for implementation on CPUs, DSPs, FPGAs, and GPUs.

  So what is the DFT? To start with, the DFT is simply a transform. It takes a sequence of sampled data (a signal), and computes the frequency content of that sampled data sequence. This will give the representation of the signal in the frequency domain, as opposed to the familiar time domain representation. This is very similar to what we did when computing frequency response of FIR filters. This can be a very powerful tool in signal processing applications, because it allows one to examine any given signal (not just a filter) in the frequency domain, which provides the spectral content of a given signal.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Signal Processing

  Fundamentals and Applications

  • Li Tan(Author)
  • 2007(Publication Date)
  • Academic Press

    (Publisher)

  Discrete Fourier Transform , or DFT. The DFT also establishes a relationship between the time domain representation and the frequency domain representation. Therefore, we can apply the DFT to perform frequency analysis of a time domain sequence. In addition, the DFT is widely used in many other areas, including spectral analysis, acoustics, imaging/video, audio, instrumentation, and communications systems.

  To be able to develop the DFT and understand how to use it, we first study the spectrum of periodic digital signals using the Fourier series. (Detailed discussion of Fourier series is in Appendix B .)

  4.1.1 Fourier Series Coefficients of Periodic Digital Signals

  Let us look at a process in which we want to estimate the spectrum of a periodic digital signal x (n ) sampled at a rate of

  fs

  Hz with the fundamental period T 0 = NT , as shown in Figure 4.2 , where there are N samples within the duration of the fundamental period and T = 1/

  fs

  is the sampling period. For the time being, we assume that the periodic digital signal is band limited to have all harmonic frequencies less than the folding frequency

  fs

  /2 so that aliasing does not occur.

  FIGURE 4.2 Periodic digital signal.

  According to Fourier series analysis (Appendix B ), the coefficients of the Fourier series expansion of a periodic signal x (t ) in a complex form is

  (4.1)

  where k is the number of harmonics corresponding to the harmonic frequency of kf 0 and ω0 = 2π/T 0 and f 0 = 1/T 0 are the fundamental frequency in radians per second and the fundamental frequency in Hz, respectively. To apply Equation (4.1) , we substitute T 0 = NT , ω0 = 2π/T 0 and approximate the integration over one period using a summation by substituting dt = T and t = nT . We obtain

  (4.2)

  Since the coefficients

  ck

  are obtained from the Fourier series expansion in the complex form, the resultant spectrum

  ck

  will have two sides. There is an important feature of Equation (4.2) in which the Fourier series coefficient

  ck

  is periodic of N

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Audio Processes

  Musical Analysis, Modification, Synthesis, and Control

  • David Creasey(Author)
  • 2016(Publication Date)
  • Routledge

    (Publisher)

  Any periodic function can be expressed as a summation of harmonically-related sinusoids (sine and cosine terms) of appropriate frequencies and amplitudes. It is possible to use Fourier series mathematical techniques to establish this information. This can be used, for example, to calculate the frequency domain form of standard waveform shapes such as sawtooth, square, and triangle (§4.2.2, p.79).

  Rather than working with mathematical functions, a normal audio process will deal with time-varying discrete sample values. In those cases the Discrete Fourier Transform (DFT) is used, which is the class of methods most commonly associated with transforming between time and frequency domains. The type of DFT used most regularly is the Fast Fourier Transform (FFT), which (as its name suggests) is an efficient implementation of the DFT. There are two related mathematical forms; the FFT that transforms from the time to the frequency domain, and the Inverse FFT (IFFT) that achieves the opposite. Therefore the arrangement in figure 12.2 can be implemented as an FFT, followed by manipulation of the frequency domain data, followed by an IFFT.

  The mathematics of the FFT and IFFT is beyond this book. Suitable functions are often provided in libraries or as standard objects in programming languages, so it is not necessary for those creating frequency domain audio processes to have to implement them from scratch. It is important, however, to understand the configuration, limitations, and side effects of the FFT and IFFT in order to use them properly.

  Figure 12.3 illustrates how the FFT might typically be used. The time domain data is stored in a buffer (as described in Chapter 8 ). The reason for buffering is that the time domain data must be transformed in sections. The number of samples considered at once is called the window size (also known as the transform size, or FFT size, or number of FFT points). The FFT transforms the time domain data into an output spectral frame of the same size as the input window. This frame is composed of a set of bins

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Signal Processing for Neuroscientists

  An Introduction to the Analysis of Physiological Signals

  • Wim van Drongelen(Author)
  • 2006(Publication Date)
  • Academic Press

    (Publisher)

  6 Continuous, Discrete, and Fast Fourier Transform

  6.1 INTRODUCTION

  In this chapter, the Fourier transform is related to the complex Fourier series presented in the previous chapter (see overview, Fig. 5.3 ). The Fourier transform in continuous time (or space) is referred to as the continuous Fourier transform (CFT). In Section 6.3 , we develop a discrete version of the Fourier transform (DFT) and explore an efficient algorithm for calculating it this efficient algorithm is known as the fast Fourier transform (FFT). In Chapter 7 , we show an example of the use of the CFT in the reconstruction of images and an application of the DFT calculating the power spectra of simulated and recorded signals.

  6.2 THE FOURIER TRANSFORM

  The Fourier transform is an operation that transforms data from the time (or spatial) domain into the frequency domain. In this section we demonstrate that the transform can be considered as the limiting case of the complex Fourier series.

  Figure 6.1 illustrates how one can create an arbitrary function f (t ) from a periodic signal

  fTo

  (t ) by increasing its period T 0 to ∞. This thought process is the basis on which the continuous Fourier transform is derived from the complex Fourier series. For clarity, we reiterate the expressions for the complex series and its coefficients derived in Chapter 5 :

  Figure 6.1 (A) Periodic function

  fτ

  0 (t ) and (B) function f (t ) derived from one cycle.

  (6.1a)

  with the coefficients defined as

  (6.1b)

  The first step is to establish the coefficient

  cn

  for the series

  fT

  0 (t ) in Figure 6.1A . Hereby we integrate over one cycle of the function

  fT

  0 (t ), which equals f (t ) over the period from –T0 /2 to T0 /2:

  (6.2)

  In Equation (6.2) , we include the period T0 , and the fundamental angular frequency ω0 . The relationship between these parameters is given by (with f 0 the fundamental frequency in Hz). So far we are still simply applying the complex Fourier series to f (t ) as one cycle of

  fT

  0 (t ). The second step is to stretch the period parameter T 0 to ∞ (which also means that the fundamental angular frequency ω0 → 0) and to define

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Signal Processing

  A Primer With MATLAB®

  • Samir I. Abood(Author)
  • 2020(Publication Date)
  • CRC Press

    (Publisher)

  6 Discrete-Time Fourier Transform (DTFT)

  The Fourier representation of signals plays an essential part in both continuous and discrete-time signal processing. It delivers a method for mapping signals into another domain in which to operate them. The Fourier representation mainly useful is the property that the convolution operation mapped to multiplication. Also, the Fourier transform provides a different method to understand the systems and signals.

  Discrete-Time Fourier Transform (DTFT) is used to analyze the frequency spectrum of a discrete signal with a computer because computers can only handle a finite number of values. This chapter presents analysis a frequency response for a signal using MATLAB, and the Inverse Discrete-Time Fourier Transform(IDTFT), also chapter will submit the Applications of DTFT and analysis of LSI Systems and Solving Difference Equations using DTFT.

  6.1 Frequency Response

  Eigen functions of linear shift-invariant systems are sequences that, when input to the system, pass through with only a change in (complex) amplitude. If the input is x (n ), the output is y (n ) = λ x (n ), where λ , the eigenvalue, generally depends on the input x (n ).

  Signals of the form

  x ( n ) = e j n ω     − ∞ < n < ∞

  (6.1)

  where ω is a constant, are Eigen functions of LSI systems. Which is shown in the convolution sum:

  y ( n ) = h ( n ) * x ( n ) = ∑ k = − ∞ ∞ h ( k ) x ( n − k )

  (6.2)

  = ∑ k = − ∞ ∞ h ( k ) e j ω n − k = e j n ω ∑ k = − ∞ ∞ h ( k ) e − j k ω

  = H e j ω e j n ω

  (6.3)

  Thus, the eigenvalue, which we denote as

  H

  e

  j ω

  , is

  H e j ω = ∑ k = − ∞ ∞ h ( k ) e − j k ω

  (6.4)

  The function

  H

  e

  j ω

  is called the frequency response of the systems.

  Note that,

  H

  e

  j ω

  is, in general, a complex-valued quantity. Thus, it is written in terms of its real and imaginary

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Digital Signal Processing

  Concepts and Applications

  • Bernard Mulgrew, Peter Grant, John Thompson(Authors)
  • 2002(Publication Date)
  • Bloomsbury Academic

    (Publisher)

  9

  The Fourier transform and spectral analysis

  CHAPTER INTRODUCTION

  This chapter develops the mathematical relationship behind the Discrete Fourier Transform (DFT) operation and highlights the limitations of the finite data record on the DFT performance analysis. This is then developed into the classical and modern techniques which are widely used for estimation of the power spectrum from signal sample data records. The power spectral density of a signal was defined previously in section 7.3 via the autocorrelation sequence. Here we extend this to the case of a discretely sampled sequence, x (n), which, in most practical situations, is restricted to a finite and limited number of signal samples.

  The learning objectives of this chapter are to: •understand how the Discrete Fourier Transform is obtained from the continuous Four ier transfor m; •know how to apply the Discrete Fourier Transform to a finite sequence of signal samples; •recognise the importance of resolution and be able to use appropr iate windowing functions; •understand how modern spectral analysis techniques can be applied to autoregressive processes.

  9.1.Development of the Discrete Fourier Transform

  In this section, the Discrete Fourier Transform is developed, starting with the continuous Fourier transform.

  9.1.1.The continuous Fourier transform

  Consider first an analogue deterministic signal, x(t), with Fourier transform X(

  ω

  ), equation (1.16), i.e.:

  In the practical situation we observe x(t) and wish to calculate and estimate its Fourier transform. Usually we are supplied with a finite number of samples of the signal. The sampling of the signal may not cause loss of information provided we sample fast enough (see the sampling theorem, Chapter 4 ). However, the finite nature of the data record is such that we cannot perform the integration in equation (9.1) from the beginning of time (i.e. t = − ∞ ) to the end of time (i.e. t = ∞

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  An Introduction to Signal Processing for Non-Engineers

  • Afshin Samani(Author)
  • 2019(Publication Date)
  • CRC Press

    (Publisher)

  n and reduces the number of multiplication and addition steps required to implement the DFT algorithm.

  Particularly, the FFT algorithm is more efficient if the number of samples of the discrete signal N is a power of 2, for example, N = 64, 128, 256, … Therefore, even if the number of available samples is not a power of 2, the signal is padded by zeros (“zero padding”) to fill in the rest of the samples with zeros and create a sequence with a power of 2.

  5.3 Aliasing in the Time Domain

  As I mentioned earlier, DFT is equivalent to the sampling of the Fourier transform, and this sampling in the frequency domain would correspond to a periodic signal in time, which is composed of copies of the original signal shifted by N. In Chapter 4 , I discussed the overlapping of the shifted versions of the Fourier transform in the frequency domain and concluded that the extent of the shift should be such that the original Fourier transform can simply be reconstructed by isolating one of the shifted versions in one period. The same concept can be applied here, and the shifted versions of the signal in time should not overlap, and the original signal should be reconstructed by looking at the signal over one single period. The question here is that if the DFT algorithm is the sampling of the Fourier transform in the frequency domain, how many samples of the DFT are sufficient to be able to reconstruct the signal in time? It is straightforward to realize that the number of samples from the Fourier transfer should be greater than N

  Sign up to read

  Learn more about book