The 1-D Radix-2 FFT Algorithms

=

=

First we consider fast algorithms for the one-dimensional DFT, com- monly abbreviated as FFT algorithms for fast Fourier transform. We assume that the dimension of the vector is a power of two, N 2l. As the direct solution according to Eq. (2.29) is O(N2) it seems useful to use the divide-and-conquer strategy. If we can split the transformation into two parts with vectors the size of N/2, we reduce the number of operations from N2 to 2(N/2)2 N2/2. This procedure can be applied recursively ld N times, until we obtain a vector of size 1, whose DFT is trivial because nothing at all has to be done. Of course, this procedure only works if the partitioning is possible and the number of additional operations to put the split transforms together is not of a higher order than O(N).

=   =

The result of the recursive partitioning is interesting. We do not have to perform a DFT at all. The whole algorithm to compute the DFT has been shifted over to the recursive composition stages. If these com- positions are of the order O(N), the computation of the DFT totals to O(N ld N) since ld N compositions have to be performed. In comparison to the direct solution of the order O(N2), this is a tremendous saving in the number of operations. For N 210 1024, the number is reduced by a factor of about 100.

We part the vector into two vectors by choosing the even and odd elements separately (Fig. 2.21):

N

N− 1

gˆ _v =

. gn exp .−  2 π i nv Σ

n=0

N

N/2− 1

N/2− 1

N

=  n.=0

g2n exp .−  2 π i 2 nv Σ  +

n.=0

g2n+1 exp .−  2 π i ( 2 n + 1 )v Σ

(2.85)

N/2− 1                                                                                         N/2− 1

=  .  g_2n exp.− 2 π i nv Σ  + exp.− 2 π i v Σ  .  g_2n+1 exp.− 2 π i nv Σ  .

n=0

N/2

N

n=0

N/2

=

Both sums constitute a DFT with N'               N/2. The second sum is multi- plied by a phase factor which depends only on the wave number v. This

2.5 Fast Algorithms for Unitary Transforms                                      67

All sampling points                       Even sampling points

Odd sampling points

 

 

Figure 2.21: Decomposition of a vector into two vectors containing the even and odd sampling points.

 

phase factor results from the shift theorem, since the odd elements are shifted one place to the left.

=             =

As an example, we take the base vector with v                   1 and N      8

(Fig. 2.21). Taking the odd sampling points, the function shows a phase shift of π /4. This phase shift is exactly compensated by the phase factor in Eq. (2.85):

exp(− 2π iv/N) = exp(− π i/4).

−                       −

= +

N

N

N

N

The operations necessary to combine the partial Fourier transforms are just one complex multiplication and addition, i. e., O(N1). Some more detailed considerations are necessary, however, since the DFT over the half-sized vectors only yields N/2 values. In order to see how the composition of the N values works, we study the values for v from 0 to N/2         1 and N/2 to N      1 separately. The partial transformations over the even and odd sampling points are abbreviated by egˆ _v and ogˆ _v, respectively. For the fi rst part, we can just take the partitioning as ex- pressed in Eq. (2.85). For the second part, v' v          N/2, only the phase factor changes. The addition of N/2 results in a change of sign: exp.− 2π i(v +  N/2) Σ  = − exp.− 2π iv Σ    or  w^{− (v+N/2)} = − w^{− v}.

Making use of this symmetry we can write

gˆ _v  =

egˆ v + w− v  o e          v o

gˆ _v   

0 ≤ v < N/2.              (2.86)

N

gˆ v+N/2  =

gˆ _v − w⁻ N

gˆ _v.  

+

The Fourier transforms for the indices v and v N/2 only diff er by the sign of the second term. Thus for the composition of two terms we only need one complex multiplication. The partitioning is now ap- plied recursively. The two transformations of the N/2-dimensional vec- tors are parted again into two transformations each. We obtain simi- lar expressions as in Eq. (2.85) with the only diff erence being that the phase factor has doubled to exp[− (2π iv)/(N/2)]. The even and odd parts of the even vector contain the points {0, 4, 8, ···, N/2 − 4} and

{2, 6, 10, ···, N/2 − 2}, respectively.

68                                                                                        2 Image Representation

 

g0 000 g1 001 g2 010 g3 011 g4 100 g5 101 g6 110 g7 111

g0 g2 g4 g6 g1 g3 g5 g7

g0                                            +

+                           + W g^

000

g4 100

 

-1        +

0

0

W

-1

g

^

-i  +                         +     1

g2 010

-2

W g

^

+                 -1  +                         +     2

3

-3

g6 110

-1        +                 i   +

+ W  ^g

g1                                            +                          +

-W0

+

g

^

-1

4

001

g5

-1        +

-i  +

+ -W  g^

101

g3 011

 

+                 -1  +

5

g

-2

+ -W  ^

^

-3 6

g7

111

-1        +                  i +

+ -W g7

 

Figure 2.22: Signal fl ow diagram of the radix-2 decimation-in-time Fourier trans- form algorithm for N = 8; for further explanation, see text.

 

In the last step, we decompose a vector with two elements into two vectors with one element. As the DFT of a single-element vector is an identical operation Eq. (2.29), no further calculations are necessary.

=

After the decomposition is complete, we can use Eq. (2.86) recursively with appropriate phase factors to compose the original vector step by step in the inverse order. In the fi rst step, we compose vectors with just two elements. Thus we only need the phase factor for v 0 which is equal to one. Consequently, the fi rst composition step has a very simple form:

gˆ ₀                     =  g₀ + g₁

gˆ _0+N/2 = gˆ ₁  =  g₀ − g₁.

(2.87)

=

The algorithm we have discussed is called a decimation-in-time FFT algorithm, as the signal is decimated in the space domain. All steps of the FFT algorithm are shown in the signal fl ow diagram in Fig. 2.22 for N 8. The left half of the diagram shows the decimation steps. The fi rst column contains the original vector, the second the result of the fi rst decomposition step into two vectors. The vectors with the even and odd elements are put in the lower and upper halves, respectively. This decomposition is continued until we obtain vectors with one element.

As a result of the decomposition, the elements of the vectors are arranged in a new order. That is all that is performed in the decomposi- tion steps. No computations are required. We can easily understand the new ordering scheme if we represent the indices of the vector with dual numbers. In the fi rst decomposition step we order the elements accord- ing to the least signifi cant bit, fi rst the even elements (least signifi cant bit is zero), then the odd elements (least signifi cant bit is one). With each further decomposition step, the bit that governs the sorting is shifted one place to the left. In the end, we obtain a sorting in which the ordering of the bits is completely reversed. The element with the index 1 = 001₂,

2.5 Fast Algorithms for Unitary Transforms                                      69

 

 

g

g0 000 g1 001 g2 010 g3 011 g4 100 g5 101 g6 110 g7 111

g0 g2 g4 g6

^

0

 

 

g1

g3

g5

g7

 

 

g0

g2

g4

g6

 

g

g0 000 g1 001 g2 010 g3 011 g4 100 g5 101 g6 110 g7 111

g1 g3 g5 g7

^

4

 

 

Figure 2.23: Signal fl ow path for the calculation of gˆ ₀ and gˆ ₄ with the decimation- in-time FFT algorithm for an 8-dimensional vector.

 

=

for example, will be at the position 4 100₂, and vice versa. Conse- quently, the chain of decomposition steps can be performed with one operation by interchanging the elements at the normal and bit-reversed positions. This reordering is known as bit reversal.

Further steps on the right side of the signal fl ow diagram show the stepwise composition to vectors of double the size. The composition to the 2-dimensional vectors is given by Eq. (2.87). The operations are pictured with arrows and points having the following meaning: points represent a fi gure, an element of the vector. These points are called the nodes of the signal fl ow graph. The arrows transfer the fi gure from one point to another. During the transfer the fi gure is multiplied by the factor written close to the arrow. If the associated factor is missing, no multiplication takes place. A value of a knot is the sum of the values transferred from the previous level.

The elementary operation of the FFT algorithm involves only two knots. The lower knot is multiplied with a phase factor. The sum and diff erence of the two values are then transferred to the upper and lower

70                                                                                        2 Image Representation

 

knot, respectively. Because of the crossover of the signal paths, this operation is denoted as a butterfl y operation.

We gain further insight into the FFT algorithm if we trace back the calculation of a single element. Figure 2.23 shows the signal paths for gˆ ₀ and gˆ ₄.  For each level we go back the number of knots contributing to the calculation doubles. In the last stage all the elements are involved. The signal path for gˆ ₀ and gˆ ₄ are identical but for the last stage, thus nicely demonstrating the effi ciency of the FFT algorithm.

All phase factors in the signal path for gˆ ₀ are one. As expected from Eq. (2.29), gˆ ₀ contains the sum of all the elements of the vector g,

gˆ ₀ = [(g₀ + g₄) + (g₂ + g₆)] + [(g₁ + g₅) + (g₃ + g₇)],

while in the last stage for gˆ ₄ the addition is replaced by a subtraction

gˆ ₄ = [(g₀ + g₄) + (g₂ + g₆)] − [(g₁ + g₅) + (g₃ + g₇)].

=

In Section 2.4, we learnt that the DFT is an example of a unitary trans- form which is generally performed by multiplying a unitary matrix with the vector. What does the FFT algorithm mean in this context? The signal fl ow graph in Fig. 2.22 shows that the vector is transformed in several steps. Consequently, the unitary transformation matrix is broken up into several partial transformation matrices that are applied one after the other. If we take the algorithm for N 8 as shown in Fig. 2.22, the unitary matrix is split up into three simpler transformations with sparse unitary transformations:

 

















gˆ 0 gˆ 1 gˆ 2 gˆ 3





1 0 0 0 1 0 0 0 0 1 0 0 0 w− 1 0 0

0 0 1 0 0 0 0 0 0 1 0 0

w− 2         0



0        w− 3



gˆ 4

= 1  0  0  0  –1  0            0        0

 

                                       − 0  1  0  0  0                                                                                                                − w     0        0



  gˆ 5  

   ˆ g6



                                                       − 0  0  10  0                     0        − w     0

gˆ 7  

1

0  0  0  1  0     0        0        − w− 3   



 

 



1  0  1   0 0  0  0   0

0  1  0   i 0  0  0   0



 1 0  –1  0  0  0  0   0

 



0  0  0   0 1  0  1   0



 

0  0  0   0 0  1  0   i

0  0  0   0 1 0 –1  0

0  0  0   0 0  1  0     i

1 0 0  0  1     0  0 0

1  0  0  0  –1  0      0 0

 

  0 0 1  0  0    0  1 0

 

 

0 1 0  0  0     1  0 0

 

    

0 1 0  0  0     –1  0  0

0 0 0  1  0     0  0 1

0 0 0  1  0     0  0 –1

g0 g1

  g2 

g3

 



  g4 

  g5 

g6

 



  g7 

The reader can verify that these transformation matrices refl ect all the properties of a single level of the FFT algorithm. The matrix decom- position emphasizes that the FFT algorithm can also be considered as a clever method to decompose the unitary transformation matrix into sparse partial unitary transforms.

2.5 Fast Algorithms for Unitary Transforms                                      71

 

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться: