4. Discrete Fourier Transform

Question 1

What is the discrete-time Fourier transform?

Answer 1

The discrete-time Fourier transform is a dedicated signal transform that is suited to calculate the frequency spectrum of aperiodic discrete-time signals.

Question 2

What is the physical meaning of |Xd(f)| and ∠Xd(f), and hence, of |Xd(φ)| and of ∠Xd(φ)?

Answer 2

The magnitude of the discrete-time Fourier transform |Xd(f)| tells how much of frequency f there is in the signal x[k] relative to other frequencies (cf. page 22) and ∠Xd(f) indicates the phase of frequency components of frequency f.

(p. 60)

Question 3

What does the discrete-time Fourier spectrum look like?

Answer 3

Remember that the discrete-time Fourier spectrum Xd(f) is periodic with period fs.

(p. 61)

Question 4

What is the fundamental interval? How is it defined?

Answer 4

As Xd(f) is periodic, all frequency information is contained in one period of the spectrum, e.g. between −fs/2 and fs/2. In other words, knowledge of Xd(f) over the interval [−fs/2, fs/2] is sufficient to characterize the entire frequency spectrum from −∞ to +∞. The interval [−fs/2, fs/2] is therefore called the fundamental interval. Sometimes, alternatively, [0, fs] is used as the fundamental interval.

(p. 61)

Question 5

What is normalized frequency φ? 
How is it defined? 
In which unit is it expressed?
Why is φ used? 
How do you convert φ into a frequency f expressed in hertz?

Answer 5

Normalized frequency is defined,

                 φ = f/fs

which linearly maps f onto φ in such a way that fs corresponds to φ = 1. Normalized frequencies, also called digital frequencies, are dimensionless (Hz/Hz). Sometimes they are said to be expressed in cycles (or periods) per sample as f has units of cycles per second and fs is in samples per second.

Note that thanks to the normalization the fundamental interval becomes [−1/2, 1/2]. Normalized frequencies can be easily converted into real frequencies in hertz by multiplying φ by the sampling frequency :

                 f = φfs

Using the normalized form of the discrete-time Fourier transform and the concept of digital frequency has the advantage of making abstraction of the sampling frequency. If one analyzes a discrete-time signal on a computer or microprocessor the actual sampling frequency is often not of primary importance, unless a concrete physical interpretation is required. Furthermore, if one looks into the frequency properties of a digital filter, which are standardly visualized using the discrete-time Fourier transform (see section 6.5.1), the actual sampling frequency is often unknown as it depends on the signal that will eventually be input into the filter. It is therefore more appropriate in that case to use the normalized version of the discrete-time Fourier transform, which expresses the frequency relative to the (still unknown) sampling frequency.

(p. 62)

Question 6

Make sure you understand formulas 4.12 and 4.13. Interpret. How is the fundamental interval defined in this case?

The formulas can be found in the formulary.

Answer 6

Note that thanks to the normalization the fundamental interval becomes [−1/2, 1/2]. Normalized frequencies can be easily converted into real frequencies in hertz by multiplying φ by the sampling frequency :

                 f = φfs

(p. 62)

Question 7

What do the magnitude and the phase of the discrete-time Fourier transform of a real-valued signal look like?

Which symmetry is observed?

Answer 7

The magnitude spectrum |Xd(phi)| is even and that the phase spectrum ∠Xd(phi) is odd.

Het frequentie spectrum is periodisch en continu.

(p. 63)

Question 8

What is the time-shifting property of the discrete-time Fourier transform? Explain in a few words.

The formula can be found in the formulary.

Answer 8

If x[k] ←→ Xd(φ) is a discrete-time Fourier transform pair, then also

                   formula 4.18

is a discrete-time Fourier transform pair, where K is an integer. Hence, time shifting leaves the magnitude spectrum unchanged, but adds an extra term −2πφK to the phase spectrum ∠Xd(φ). Notice that the extra phase term is linear in φ.

(p. 63)

Question 9

What is a discrete(-time) convolution? The formula can be found in the formulary.

Explain in words how it can be calculated (figure 4.1). Make sure you can calculate the convolution of two signals as in equation 4.30.

Answer 9

Expression 4.27 is called the discrete(-time) convolution of x[k] and y[k]. Remark that equation 4.27 comes down to a set of multiplications and additions, which can be easily calculated on a microprocessor. Contrary to equation 2.41, no integral operations are involved.

A discrete convolution of x[k] and y[k] comes down to time reversing one of the signals, time shifting the reversed signal by a distance k to the right6 with respect to the other signal, and then multiplying the corresponding samples and summing them together.

(p. 65)

Question 10

What is the importance of discrete convolution?

Answer 10

If one or both signals are of finite duration, the sum in equation 4.27 (or equation 4.28) runs over a finite set of integers only.

It is easily seen that if signal x[k] has length N, i.e. if x[k] has N consecutive nonzero samples, and signal y[k] has length M, the convolution result z[k] = x[k] ⋆ y[k] has length N + M − 1.

(gokje p. 66)

Question 11

What does the convolution theorem state?
What is the importance of the convolution theorem?

The formulas can be found in the formulary.

Answer 11

It can be proven that if x[k] ←→ Xd(φ) and y[k] ←→ Yd(φ) are discrete-time Fourier transform pairs, then it holds that

                     formulas 4.33 and 4.34

It follows that similar to the continuous-time case, a convolution operation in one domain corresponds to a multiplication in the other domain. The convolution theorem is useful in some applications where it is more convenient to compute a convolution (filtering) operation as a multiplication in the frequency domain rather than as a computation-intensive convolution in the time domain.

(p. 66 - 67)

Question 12

What is discrete correlation? Explain in words how it can be calculated.

The formula can be found in the formulary.

Answer 12

A discrete correlation comes down to time shifting the second signal by a distance k to the left (or to the right, if the alternative definition11 is used) with respect to the first signal, and then multiplying the corresponding samples and summing them together. Unlike convolution the second signal is not reversed in time.

(p. 68)

Question 13

What does the correlation theorem say?

The formula can be found in the formulary

Answer 13

It can be proven that if x[k] ←→ Xd(φ) and y[k] ←→ Yd(φ) are discrete-time Fourier transform pairs, it holds that

             formula 4.38

(p. 68)

Question 14

What is a discrete Dirac impulse?

Answer 14

The discrete Dirac impulse is the discrete-time equivalent of the Dirac impulse in continuous time. It is defined as:

                   δ[k] = 1              if k = 0
                   δ[k] = 0             if k != 0

(p. 68)

Question 15

What is the discrete-time Fourier transform of a Dirac impulse?

Answer 15

The discrete-time Fourier transform of a Dirac impulse is a constant: the Dirac impulse contains all frequencies in equal amounts.

(p. 69)

Question 16

Give the graphical representation of the discrete-time Fourier transform of a discrete rectangular pulse

Answer 16

Make sure you can reproduce figure 4.4. You are not supposed to be able to replicate the values on the vertical axes.

(p. 71)

Question 17

What is a periodic discrete-time signal? How is period N defined?

Answer 17

A periodic discrete-time signal xN [k] is. a signal for which the following property is fulfilled:

                   xN [k] = xN [k + N]             ∀k ∈ Z

where N is an integer that is different from 0. Period N is the smallest integer larger than 0 for which the equation holds.

(p. 72)

Question 18

Give the graphical derivation of the Frequency spectrum of a periodic discrete-time signal of period N = 6.

Answer 18

Make sure you can reproduce figure 4.5. You are not supposed to be able to replicate the values on the vertical axes.

Recall that throughout the textbook signals are commonly represented in the time and in the frequency domain as continuous Fourier transform pairs, indicated as two figures with a two-sided arrow in between with the acronym ’CFT’ on top. By representing (discrete-time) signals in the continuous time and frequency domain (as sets of Dirac impulses) (properties of) the continuous Fourier transform can be applied, which is well established from a mathematical point of view (see chapter 2 and course on Signals and Systems). One could alternatively represent discrete-time signals as DTFT or DFT transform pair plots. However, in that case, one has to use a different type of convolution (discrete, linear or circular), for which slightly different properties hold compared to the standard convolution operation defined by equation 2.41. Recall for instance that if you opt for DTFT or DFT transform pair plots, a rectangular pulse in the (discrete) time domain, no longer corresponds to a perfect sinc in the frequency domain (see e.g. formula 4.46).

(p. 73)

Question 19

What is the frequency spectrum of a periodic discrete-time signal?

Answer 19

The frequency spectrum of a periodic discrete-time signal is discrete and periodic with period fs.

(p. 74)

Question 20

What is the discrete Fourier transform?

Answer 20

The discrete Fourier transform is a dedicated signal transform to calculate the frequency spectrum of periodic discrete-time signals.

Question 21

Interpret the DFT formula and the IDFT formula.

Answer 21

Make sure you understand formulas 4.58 and 4.59. Interpret. Observe that both the forward and the inverse transform can be easily implemented on a microprocessor.

(p. 74)

Question 22

What do the time-domain signal xN [k] and the DFT transform XN [n] have in common?

Answer 22

Keep in mind that both the time-domain signal xN [k] and the DFT transform XN [n] are discrete and periodic with period N.

Question 23

What is the fundamental interval? How is it defined?

Answer 23

Both the time-domain signal xN [k] and the DFT spectrum XN [n] are discrete and periodic with period N. This means that not only xN [k], but also XN [n] is completely characterized by a finite set of N coefficients that are infinitely repeated. It therefore suffices to consider only one period of XN [n] to describe the complete signal (in the frequency domain). This single period is called the fundamental interval. The exact location of the fundamental interval is arbitrary, however. It can be located between n = − N/2 and N/2 − 1, between −N + 1 and 0, or between 0 and N − 1. Most often, the last option is preferred.

(p. 75)

Question 24

What is an N-point (I)DFT?

Answer 24

In practice, only the finite set {xN [0], xN [1], . . . , xN [N − 1]} of N samples (a single period of xN [k]) is input into the DFT, and as a result, a corresponding finite set of N frequencydomain coefficients {XN [0], XN [1], . . . , XN [N − 1]} (a single period of XN [n]) is output. Keep in mind that in reality, both xN [k] and XN [n] are infinitely long periodic signals.

In this respect, one often refers to equation 4.58 as an N-point DFT, suggesting that the DFT is to be performed on a signal of length N. In reality, however, parameter N does not refer to the length of the signal, but rather to the signal period.

(p. 75)

Question 25

What is a frequency bin?

Answer 25

In practice, only the finite set {xN [0], xN [1], . . . , xN [N − 1]} of N samples (a single period of xN [k]) is input into the DFT, and as a result, a corresponding finite set of N frequencydomain coefficients {XN [0], XN [1], . . . , XN [N − 1]} (a single period of XN [n]) is output. Keep in mind that in reality, both xN [k] and XN [n] are infinitely long periodic signals.

In this respect, one often refers to equation 4.58 as an N-point DFT, suggesting that the DFT is to be performed on a signal of length N. In reality, however, parameter N does not refer to the length of the signal, but rather to the signal period.

The N outputs of the DFT are commonly referred to as frequency bins.

(p. 75)

Question 26

What does periodicity in the one domain lead to in the other domain?

Answer 26

Note that a periodic repetition in one domain leads to discretization in the other domain.

(p. 75)

Question 27

What is the physical meaning of the magnitude spectrum |XN [n]| and the phase spectrum ∠XN [n]? (Discrete Fourier Transform)

Answer 27

The magnitude spectrum |XN [n]| and the phase spectrum ∠XN [n] indicate the strength and the phase of the n-th frequency component in the signal (cf. page 22), which corresponds to frequency.

(p. 76)

Question 28

To which frequency in hertz does the n-th frequency bin correspond?

Answer 28

The fundamental interval is divided into N frequency bins of equal size, the n-th bin corresponds to nfs/N.

See formula 4.61.

(p. 76)

Question 29

What is the resolution of the DFT spectrum? How can the resolution be improved?

Answer 29

Parameter fs/N is called the resolution of the DFT spectrum. Observe that a longer signal period N leads to a better frequency resolution, i.e. a finer sampling of Xd^(c) (f).

(p. 76)

Question 30

What do the magnitude and the phase of the discrete Fourier transform of a real-valued signal look like?
Which symmetry is observed?
Which of the DFT coefficients XN [n] are real-valued?

Answer 30

In the most general case both the time-domain signal xN[k] and the frequency spectrum XN[n] are complex valued and there is no structure neither in xN[k] nor in XN[n].

Mostly in practice, however, xN[k] is a real-valued sequence. Then, the complex-valued frequency spectrum will show some symmetry. In case period N is even:

It follows that XN[n] = XN[N−n], or equivalently, that XN[N/2+n] = XN[N/2−n]. Hence, the magnitude spectrum |XN[n]| is even and the phase spectrum ∠XN[n] is odd wrt. n=N/2.

The magnitude spectrum |XN[n]| is even and that the phase spectrum ∠XN[n] is odd wrt. n=N/2. Also observe that as XN[0] and XN[N/2] are real valued, the phase is 0° or ±180°.

Zie ook plots op de dia.

(ppt. dia 6 - 7)

Zie ook figure 4.6

(p. 78)

Question 31

What is the time-shifting property of the discrete Fourier transform? Explain in a few words.

The formula can be found in the formulary

Answer 31

If xN [k] ←→ XN [n] is a discrete Fourier transform pair, then also

                formula 4.68

is a discrete Fourier transform pair, where K is an integer. Hence, time shifting leaves the magnitude spectrum unchanged, but adds an extra term − 2πnK/N to the phase spectrum ∠XN [n]. Notice that the extra phase term changes linearly with frequency n.

(p. 78)

Question 32

What is a discrete circular convolution? The formula can be found in the formulary.
What is the difference with discrete linear convolution?
Explain in words how a discrete circular convolution can be computed (figure 4.7).

Answer 32

formula 4.77

This variant of equation 4.27 is called (discrete) circular convolution, which is an alternative convolution operation especially suited for periodic signals.

Take a single period out of one of the signals and reverse in time. Shift the time-reversed signal period by a distance k to the right with respect to a periodically repeated extension of the other signal17, and multiply corresponding samples and add them together. Repeat this operation for N consecutive time shifts, where N is the period of the signals.

Make sure you can calculate the discrete circular convolution of two signals as in equation 4.82.

(p. 79 - 81)

Question 33

What does the circular convolution theorem state? The formulas can be found in the formulary.
What is the importance of the convolution theorem?

Answer 33

If xN [k] ←→ XN [n] and yN [k] ←→ YN [n] are discrete Fourier transform pairs of period N, then also

                 formula 4.84
                 formula 4.85

are discrete Fourier transform pairs. Hence, a (discrete) circular convolution in one domain can be equivalently computed as a multiplication in the other domain.

Property 4.84 forms the basis of so-called fast convolution techniques, which offer a lowcost alternative for digital filtering. It is typically more advantageous to apply the convolution theorem (equation 4.84) and to perform the filtering operation ˜x7[k]⊙⋆ y˜7[k] in the frequency domain as X˜7[n]·Y˜7[n].

(p. 81)

Question 34

How can the discrete linear convolution of two signals of finite length be computed using a discrete circular convolution?

Answer 34

It is easily verified that the linear convolution result z[k] = {4, −2, 1, 3} ⋆ {−1, −3, 1, 4} can be alternatively obtained from the discrete circular convolution of two zero-padded sequences that are related to equations 4.80 and 4.81 :

                      x˜7[k] = {4, − 2, 1, 3, 0, 0, 0}
                      y˜7[k] = {−1, − 3, 1, 4, 0, 0, 0}

Zero padding means that the sequences {4, −2, 1, 3} and {−1, −3, 1, 4} are extended with 3 zeros so that they have the length of the linear convolution result of equation 4.83. Verify that the circular convolution of the zero-padded sequences x˜7[k] and ˜y7[k] gives

                     x˜7[k]⊙⋆ y˜7[k] = {−4, − 10, 9, 8, − 16, 7, 12}

which is identical to z[k].

(p. 81)

Question 35

What is zero padding?

Answer 35

Zero padding means that the sequences {4, −2, 1, 3} and {−1, −3, 1, 4} are extended with 3 zeros so that they have a particular length.

(p. 81)

Question 36

What is a discrete circular cross-correlation? The formula can be found in the formulary.
Explain in words how it can be calculated.
What is a circular autocorrelation?

Answer 36

The discrete circular (cross-)correlation of two real-valued periodic discrete-time signals xN [k] and yN [k] of period N is defined as:

                formula 4.89

It can be calculated by selecting a single period of the second signal, by shifting it by a distance k to the left (or to the right if the alternative definition is used) with respect to a periodically repeated extension of the first signal, and by multiplying corresponding samples and adding them together. This operation is repeated for N consecutive time shifts, where N is the period of the signals.

If xN [k] = yN [k]

                 formula 4.90

is obtained, which is called the discrete circular autocorrelation of xN [k].

(p. 82)

Question 37

What does the circular correlation theorem say?

The formula can be found in the formulary

Answer 37

It is easily shown that if xN [k] ←→ XN [n] and yN [k] ←→ YN [n] are discrete Fourier transform pairs all having period N, the circular correlation theorem

            formula 4.91

holds. Hence, a discrete circular correlation operation can be alternatively computed in the frequency domain as a multiplication (plus complex conjugation).

(p. 82)
.

Question 38

How many arithmetic operations are needed for an N-point discrete Fourier transform of a complex-valued signal?

Do not try to memorize the formula, but make sure you can calculate it yourself.

Answer 38

Actually, in total N DFT coefficients XN [0], . . . , XN [N − 1] need to be computed (one period of the spectrum). For the computation of each of these coefficients a sum of N products must be calculated (see equation 4.58), requiring N multiplications and N − 1 additions to sum the products together.

As there are N DFT coefficients in total, N^2 multiplications and N(N −1) additions are needed for one N-point DFT. In the most general case, when signal xN [k] is complex valued, all the multiplications and additions are performed on complex numbers.

Recall that a complex multiplication (a + jb) · (c + jd) = (a · c − b · d) + j(a · d + b · c) comes down to 4 real multiplications and 2 real additions. A complex addition (a + jb) + (c + jd) = (a + c) + j(b + d) on the other hand, amounts to 2 real additions. Hence, the N^2 complex multiplications and N(N − 1) complex additions needed for a complex N-point DFT, require 4N^2 real multiplications and 2N^2 real additions, plus 2N(N − 1) real additions, offering a total cost of 4N^2 real multiplications and 2N(N −1) + 2N^2 real additions.

Leading to the following formula:

   cost_complex DFT = (4N^2 + 2N(N − 1) + 2N^2) op. = (8N^2 − 2N) op.

(p. 85)

Question 39

How many arithmetic operations are needed for an N-point discrete Fourier transform of a real-valued signal?

Do not try to memorize the formula, but make sure you can calculate it yourself.

Answer 39

Thanks to equation 4.66 the spectrum is symmetrical. So, it suffices to calculate XN [1] till XN [N/2 −1] (on top of XN [0] and XN [N/2]) and obtain XN [N/2 +1] till XN [N −1] as a mere complex conjugation of XN [1], …, XN [N/2 − 1]. Hence, for even N the number of arithmetic operations reduces to

cost_real-input DFT, even N = (2N^2 − 3N) op.

(p. 85 - 86)

Question 40

For a real-valued signal, roughly only half of the coefficients XN [n] need to be computed. Why?

Answer 40

Thanks to equation 4.66 the spectrum is symmetrical. So, it suffices to calculate XN [1] till XN [N/2 −1] (on top of XN [0] and XN [N/2]) and obtain XN [N/2 +1] till XN [N −1] as a mere complex conjugation of XN [1], …, XN [N/2 − 1].

(p. 85 - 86)

Question 41

What is the relationship between the cost of a discrete Fourier transform and the signal period N?

Answer 41

The implementation cost of a discrete Fourier transform rises quadratically with the signal period N.

(p. 86)

Question 42

What does the acronym FFT stand for?

Answer 42

Fast Fourier Transform

p. 85

Question 43

Briefly explain in words the divide-and-conquer strategy that is behind the class of FFT algorithms.

Answer 43

The idea behind these fast implementation schemes is a divide-and-conquer strategy that writes the N-point DFT in terms of N/2-point DFTs. Recursively, the N/2-point DFTs can be replaced with sets of N/4-point DFTs, and so on. In this way, the original N-point DFT is computed in a total of log2 N steps. As for each step a number of calculations is required that is proportional to N, an overall complexity results that rises with N log2 N. Given that the complexity of a standard implementation of the DFT is proportional to N^2, a significant reduction in the number of calculations is expected for large values of N.

(p. 86 - 87)

Question 44

What is the relationship between the implementation cost of an (I)FFT algorithm to the signal period N?

Answer 44

The implementation cost of an (I)FFT algorithm is proportional to N log2 N, where N is the signal period.

(p. 86)

Question 45

Explain figure 4.10.

Answer 45

Make sure that you understand and can explain figure 4.10 (in broad outlines). You are not expected to reproduce the figure yourself at the exam.

(p. 87)

Question 46

Explain figure 4.11.

Answer 46

Make sure that you understand and can explain figure 4.11 (in broad outlines). You are not expected to reproduce the figure yourself at the exam.

(p. 88)

Question 47

Explain figure 4.12.

Answer 47

Make sure that you understand and can explain figure 4.12 (in broad outlines). You are not expected to reproduce the figure yourself at the exam.

(p. 89)

Question 48

What is a radix-2 FFT algorithm?

Answer 48

Combination of figures 4.10, 4.11 and 4.12 leads to figure 4.13, showing the structure of the so-called decimation-in-time (DIT) radix-2 fast Fourier transform algorithm for N = 8. It is called a radix-2 algorithm because the original N-point DFT is decomposed into two N/2-point DFTs, and so on.

(p. 90)

Question 49

Explain figure 4.13.

Answer 49

Make sure that you understand and can explain figure 4.13 (in broad outlines). You are not expected to reproduce the figure yourself at the exam

(p. 90)

Question 50

What is a butterfly operation? See also figure 4.14. You are not expected to reproduce the figure yourself at the exam.

Answer 50

Recursive decomposition leads to a signal flow graph consisting of log2 N layers. In all of these layers N/2 so-called butterfly operations are performed, which each operate on two input samples and produce
two output samples. This type of operation, shown in more detail in figure 4.14, is called this way, because the cross by which it is represented is reminiscent of a butterfly.

(p. 90 - 91)

Question 51

Explain figure 4.15.

Answer 51

Make sure that you understand and can explain figure 4.15 (in broad outlines). You are not expected to reproduce the figure yourself at the exam.

(p. 91)

Question 52

Make sure you can make a cost estimate (do not simply memorize the formulas) for the different implementation schemes in the textbook, such as equations 4.95, 4.99 and 4.114 (and many other examples in the following chapters). You also have to be able to perform a memory requirement analysis: how much memory does the equation or the scheme (for instance figure 4.15) require? While studying also think about a practical application for the different implementation schemes/formulas that are considered in the course.

Answer 52

p. 85 - p. 86 - p. 91

Question 53

What is bit-reversed ordering/addressing? Explain table 4.1.

Answer 53

Owing to the recursive splitting of the data the time-domain samples xN [k] need to be input into the FFT in a non-sequential order, called bit-reversed ordering. The name comes from the fact that this somewhat unnatural ordering can be retrieved by first writing the time index k in xN [k] as a binary number, and then swapping the order of the bits. In this way, the most significant bit is put in the last position and the least significant bit in the first position, and so on.

(p. 91 - 92)

Question 54

What is an in-place algorithm?

Which advantages does it have?

Answer 54

The original sample values a and b of the butterfly operation can be overwritten and replaced with a + Wr^N · b and a − Wr^N · b upon completion. In this way, the algorithm can operate on one array of N (complexvalued) data elements only. The array initially contains the input (time-domain) data, is continuously overwritten, and will finally contain the output (frequency-domain) data.

The radix-2 algorithm is therefore efficient, not only in terms of number of computations, but also as far as memory consumption is concerned. As the input data is continuously overwritten the implementation scheme is called an in-place computation algorithm.

(p. 92)

Question 55

How can de IDFT of XN[n] be computed from the DFT?

Answer 55

Owing to the similarity between the DFT and the IDFT, the IDFT of XN [n] can be computed by first calculating the DFT (or FFT) of the complex conjugate of XN [n], then performing a complex conjugation on the result, and finally dividing all the sample values by N.

(p. 93 - 94)

Question 56

What is a real-input FFT?

What are the advantages and disadvantages with respect to an equivalent complex FFT?

Answer 56

In most practical applications, the input data is real valued. Hence, the imaginary part of xN [k] is zero, making half of the 2N inputs, being the real and the imaginary parts of one period of xN [k], zero. As a consequence, roughly half of the calculations that are performed in the left-most layer of the implementation scheme are redundant and can be omitted. Similarly, given the symmetry XN [N − n] = X∗N [n] in the spectrum, about half of the frequency data XN [n] can be obtained through complex conjugation of the other half and do not need to be explicitly computed, as explained below equation 4.95. An optimized implementation scheme (30% faster/less calculations) for realvalued input signals results, called real-input FFT.

(p. 94)

The real-input FFT, however, has two disadvantages with respect to the standard complex FFT. It is less symmetric, hence the inverse transform cannot be directly derived from the forward transform. Secondly, the code is typically about twice as long as that of the corresponding complex FFT. This may pose problems if the scheme needs to be run on hardware with limited memory capabilities.

(p. 95)

Question 57

What is a real-output IFFT?

Answer 57

They compute the inverse DFT of a sequence XN [n] that has the symmetry of equation 4.66, i.e. XN [N−n] = X∗N [n], leading to a purely real-valued time-domain signal xN [k]. Just like with the real-input FFT, efficient implementation schemes can be derived that input XN [n] into the algorithm using the half-complex format shown in equation 4.118. In this way, data buffers can be used of N rather than of 2N real coefficients.

(p. 95)

Question 58

Why do most frequency transforms encountered in practical implementations operate on data buffers of N = 2^m samples, where m is a positive integer?

Answer 58

Because most FFT implementations follow the divide-and-conquer strategy. This idea can be extended to the case where N = N1 · N2 · · · Nq. In general, the more (prime) factors can be identified in N, the faster the overall implementation becomes. As a result, the complexity of an FFT implementation scheme with N != 2^m, m = 1, 2, 3, … is typically higher than the complexity of an FFT with N′ = 2^m ≈ N.

(p. 96)

Question 59

What needs to be taken into account in a detailed cost analysis?

Answer 59

Just counting the number of additions and multiplications does not reliably reflect the required execution time of the code. In a detailed cost analysis also data transfer and pointer update operations need to be taken into account.

(p. 96)

Question 60

Complexity analyses as in equation 4.114 are used to highlight the main dependencies of the computation cost on some parameters, such as the FFT size N, and can
furthermore serve as a means to compare and benchmark different algorithm implementations.

Answer 60

(p. 96)