Theoretical Development of Fast Fourier Transform 11.06.15
Chapter 11.06
Theoretical Development of FFT
Introduction
The informal development of FFT (presented in the previous chapter 11.05) has captured all the essential features and characteristics about FFT. In this chapter, however, FFT [1–5] will first be presented in a more general fashion (for the case where the number of sampled data points can be expressed as, with is an integer number) so that it will facilitate further refined FFT formulation to the cases where the restriction on can be removed.
FFT Algorithms for
Recall Equation (5) from Chapter 11.05
(5, Ch. 11.05)
where
(4, Ch 11.05)
Considered the case
In this case, we can express and as 2-bit binary numbers
(1)
(2)
Equations (1, 2) can also be expressed in compact forms, as following:
(3)
(4)
where
or 1
In the new notations, Equation (5) from chapter 11.05 becomes
(5)
Consider
(6)
Notice that:
Hence Equation (5) can be simplified to:
(7)
Define the inner summation as (notice: the index is repeated, hence will be disappeared, and replaced by the index ):
(8)
or
(9)
Hence
(10)
In matrix notation, Equation (10) can be written as:
(11)
Thus, Equation (11) plays the same role as Equation (11) in chapter 11.05.
Now, define the outer summation as (notice: the index is repeated, hence will be disappeared and replaced by the index .
(12)
(13)
Hence
(14)
(15)
Equation (15) plays the same role as Equation (13) in chapter 11.05.
Also, comparing Equation (5) and Equation (13), one gets
(16)
Thus, Equation (16) implies that unscrambling (or bit-reversed operations) the results of will give us the desired results for.
The set of Equations (8, 12, 16) represents the original Cooley-Turkey [1–4] formulation of the FFT.
Consider the Case
In this case, and can be expressed in compact forms (using 3-bit binary numbers) as
(17)
(18)
where
or 1
Using Equation (17), any value of integer (between 0 and 7), say , can be expressed in terms of appropriated binary numbers of and . In this specific example, the values for and should be and 1 respectively.
In the new notations, Equation (5) from chapter 11.05 becomes (19)
Consider
(20)
Due to the definitions of (shown in Equation (4) from chapter 11.05), each of the 3 terms inside the square bracket is equal to 1. Thus, Equation (19) can be simplified to:
(21)
Define (see Figure 1)
(22)
(23)
(24)
Hence,
(25)
Remarks about Equation (22):
(22a)
(Companion Nodes) (22b)
skip computation
In the above example (where ), computation of the first vector (see Equation 22) will require calculation of the above 8 equations (see Equation 22b). However, in actual computer implementation, the above last 4 equations will be skipped, since the first 4 equations are the “companion nodes” of the last 4 equations. The 1st and the 5th equations, the 2nd and the 6th equations, the 3rd and the 7th equations, and the 4th and the 8th equations are companion pair of nodes. Thus, once the product of had been computed, the 1st equation can be computed for and in the 5th equation can be obtained with nearly free efforts (with the “plus” sign in the 1st equation to become “minus” sign in the 5th equation).
Figure 1 Graphical Form of FFT (for the case ).Consider the general case ( any integer number)
Equations (17, 18) can be generalized to, where can be any integer number, as following
(26)
(27)
Equation (5) from chapter 11.05 becomes
(28)
where
(29)
The first term of Equation (29) can be computed as:
Since
Hence all terms inside the above brackets are equal to 1. Thus
(30)
Similarly, the second term of Equation (29) can be computed as
(31)
(32)
Equation (28) will eventually become
(33)
Let
(34)
(35)
…..
…..
(36)
(37)
Remarks:
When the number of data size can’t be expressed as , then additional (zero values) data can be artificially created to satisfy this requirement [9]. For example, if then 6 additional data points can be created so that can be expressed as
FFT Algorithms for (where are integers)
In the previous section, FFT algorithms have been developed for the case where the sample size can be expressed as . The objective of this section is to develop FFT algorithms for handling a more general case where can be expressed as where and can be any positive integers.
Let us first define
(38)
(39)
where
(40)
(41)
(42)
(43)
Remarks:
The smallest value for (when .
The largest value for “” will occur when and Hence,
Equation (38) gives:
Thus, if then
Using the above notations, Equation (5) from chapter 11.05 can be expressed as
(44)
Consider
(45)
(46)
Due to the fact that
(47)
Substituting Equation (46) into (44), one gets:
(48)
Define:
(49)
(50)
Hence:
(51)
Example 1
For Equations (49) and (50) give (also refer to Figure 2)
(52)
(53)
Expanding Equation (52), one obtains
(52a)
Similarly, expanding Equation (53), one gets:
(53a)
For a typical term corresponding to, Equation (52A) gives:
(52b)
(52c)
For a typical term, such as , Equation (53A) gives:
(53b)
A partial/incomplete graph of FFT (based on Equations 52b, 52c and 53b), for the case is presented in Figure 2, for which it is noted that
a) Since , there are 2 computational arrays and which need to be computed.
b) Computation for arrays (or should be proceeded in “top-down” fashion. Each computed term for array (or will have contributions of 4 terms from the “previous” array.
Figure 2 An “incomplete” FFT for .Example
(For the case
In this case, utilizing Equations (40-43) into Equations (38) and (39), one obtains (11)
(54)
(55)
where
(56)
(57)
(58)
(59)
Then, Equation (5) in chapter 11.05 becomes
(60)
Consider
(61)
Substituting Equation (61) into Equation (60), one obtains
(62)
Define:
(63)
(64)
Hence:
(65)
Expanding (the summation) of Equations (63) and (64), one gets
(66)
Assuming then the above equation becomes
(67)
Similarly, one has
(68)
Assuming and then
(69)
Thus, computation of each term for arrays and (see Equations 67) and (69)) will require the “previous” 4 terms and 2 terms, respectively. The partial (or incomplete) graphical display for FFT (with based on Equations (67) and (69), is shown in Figure 3.
Figure 3 An “incomplete” FFT for .General FFT Algorithms and Relationships Between FFT Algorithms for versus
FFT algorithms for the case where the sample size can be expressed as has already been discussed in the previous section.
For the more general case, such as
(70)
where are any ‘integer” numbers.
Define
(71)
(72)
with
(for (73)
(for (74)
In order to simplify the “arithmetic efforts”, and to easily identify the “patterns” of the general FFT algorithms/formulas, we assume , and therefore the following case will be considered
(75)
Hence, Equations (71) to (74) will be simplified to
(76)
(77)
(78)
(79)
Equation (5) in chapter 11.05 can be expressed as
(80)
Let’s define
(81)
(82)
(83)
where
(84)
(85)
since
(see Equation 4 in chapter 11.05)
(86)
(87)
(88)
Substituting Equations (85), (87) and (88) into Equation (83), and using Equation (81), then Equation (80) will become
(89)
Define
(90)
(91)
(92)
Then
(93)
In order to see the “connections” between the general FFT algorithms (such as and the base 2 FFT algorithms (such as we now consider the special case where (hence In this case, Equations (90 to 92) can be simplified to
(94)
(95)
(96)
In fact, Equations (94) to (96) are “identical” to the earlier derived Equations (22) to (24).
Twiddle Factor FFT Algorithms for
To facilitate the discussions for better understanding about the “improved FFT” algorithms by using the “twiddle factor” [1–5], a specific case for will be explained in the following paragraphs.
Equation (48) can be re-written as:
(97)
The factor can be included either in the “inner summation” or in the ”outer summation” (as shown in Equation 50). In this section, however, the factor is included in the “inner summation”. Thus, one defines
(98)
(99)
(100)
Remarks:
Consider the following term in Equation (98)
(101)
Table 1 Consider the following few possibilities for , such as:
0 / 11 /
2 / -1
3 /
4 / +1
.
. / .
.
Thus, depending on the numerical (integer) value of , the value of can only be or . Hence, there is “no multiplication” involved in computing . The twiddle factor can be done outside the inner summation (on the index ).
a) Since the twiddle factor is included in the first vector , as shown in Equation (98), the remaining factor can also be either . Thus, there is also “no multiplication” involved in calculating the second vector as shown in Equation (99).
b) The twiddle factor can also be applied for the case or for the more general case
c) It has been concluded in [1-4] that, using the twiddle factor, the number of operation counts (based on the number of required multiplications) for FFT with base 16 is less than with base 8, which in turns is less (or better) than with base 4, etc.
References
[1] E.Oran Brigham, The Fast Fourier Transform, Prentice-Hall, Inc. (1974).
[2] S.C. Chapra, and R.P. Canale, Numerical Methods for Engineers, 4th Edition, Mc-Graw Hill (2002).
[3] W.H . Press, B.P. Flannery, S.A. Tenkolsky, and W.T. Vetterling, Numerical Recipies, Cambridge University Press (1989), Chapter 12.
[4] M.T. Heath, Scientific Computing, Mc-Graw Hill (1997).
[5] H. Joseph Weaver, Applications of Discrete and Continuous Fourier Analysis, John Wiley & Sons, Inc. (1983).
FAST FOURIER TRANSFORMTopic / Theoretical Development of Fast Fourier Transform
Summary / Textbook notes on theoretical development of fast Fourier transform.
Major / General Engineering
Authors / Duc Nguyen
Date / July 8, 2010
Web Site / http://numericalmethods.eng.usf.edu