Examples of Discrete Transforms (779442), страница 2
Текст из файла (страница 2)
. ., - - 1.co(n)W;72,n=ODue to the periodicity of the DFT thevalues X ( L ) for Ic = $, .. . ,N - 1 aregiven byNNX ( k ) = U(Ic - -)2+ W&V(Ic- -),2Ic = -, . . . ,N - 1.2(4.54)Thus, we havedecomposed an N-point DFT into two $-point DFTs andsome extra operations for combining the two DFT outputs.Figure 4.1 illustrates the implementation of an N-point DFT via two $point DFTs. It is easily verified that the decomposition of the DFT results ina reduction of the number of multiplications: the two DFTs require 2 ( N / 2 ) 2multiplications, and the prefactors W& requireanother N multiplications.Thus, the overall complexity is $ N , instead of N 2 for the direct DFT.The prefactors W&,which are used for the combination of the two DFTs, arecalled twaddle factors.Since N is considered to be a power of two, the same decompositionprinciple can be used for the smaller DFTs and thecomplexity can be further+4.4.
The Fast Fourier Transform87reduced. To be explicit, we decompose the sequences u ( n ) and w(n) into theireven and odd numbered parts:a(n)=u(2n)=x(4n)+ 2)2(4n + 1)b ( n ) = u(2n+ 1) = x(4n= w(2n)).(C=(4.55)d(n) = v(2n+ 1) = 2(4n + 3 ) .Observing thatU ( L )={= W&kwe get for the $-point DFTs U ( k ) and V ( L )+A ( k ) W&kB ( k ) ,Nk = O , l , ...,-41,...,-N421A(L-T)+Wj$'"B(k-N4 )7 L = -(4.56)andV ( k )=I+...,-N4C(L) W;k D@),k=O,l,NNC(k-$+W&9(k--),4NNk = - ,.", - - l .41(4.57)2The decompositionprocedurecanbecontinueduntiltwo-pointDFTs arereached.It turns out that all stages of the FFT are composed of so-called butterflygraphs as shown in Figure 4.2.
The two structures in Figure 4.2 are equivalent,88Chapter 4. Examples of Discrete Transforms(401)Figure 4.2. Equivalent butterfly graphs.but theone in Figure 4.2(b) saves us one complexmultiplication. The completeflow graph for an 8-point FFT basedon the butterfly in Figure4.2(b) isdepicted in Figure 4.3.
As we see, the output values appear in their naturalorder, but the input values appear in permuted order. This is the case forall N . The order of the input values is known as the bit reversed order. Thisorder can bederived from the natural one as follows. First, one represents thenumbers 0 , 1 , . . .,N - 1in binary form. Then the orderof bits is reversed andthe decimal equivalent is taken. For example, n = 3 is represented by [011]when an 8-point FFT is considered.
This yields [l101 in reversed order, andthe decimal equivalent is 6. Thus, 4 6 ) has to be connected to input node 3.Since the butterfly operations within each stage of the FFT are independent of one another, the computationof the FFT can be carried out in place.This means that the pair of output values of a butterfly is written over theinput. After this has been done for all butterflies of a given processing stage,one can proceed to the next stage. Thus, only a memoryof size N1 isrequired for computing an N-point FFT.+Thecomputationalcomplexityof theFFT is as follows. Each stageof the FFT requires N/2 complex multiplications and N additions.Thenumber of stages is log, N . This yields a total number of i N log, N complexmultiplications and N log, N additions.
However, since the 2-point DFTs donot require multiplications, and since the 4-point DFTs involve multiplicationswith 1, -l,j, and - j only, the actual number of full complex multiplicationsis even lower than iNlog, N .4.4.2Radix-2Decimation-in-Frequency FFTA second variantof the radix-2 FFT is the decimation-in-frequency algorithm.In order to derive this algorithm, we split the input sequence into the firstFourier4.4. The Fast89Transform1-1-1Figure 4.3. Flow graph for an 8-point decimation-in-time FFT.and second halves and write the DFT asN-ln=ON/2-l(4.58)n=OcNf2-1=[U(.)+ (-l)”(.)] W$)n=OwhereU(.)= ).(X).(v= z(n+N/2)Nn = 0 , 1 ) . . . )- - l .2,In (4.58) we haveused the fact that W:’2numbered DFT points we getcN-lX(2k)=[U(.)(4.59)= -1.
For the even andodd+ v(.)]WZh(4.60)-v(.)]W; W Z k .(4.61)n=OandX(2k+ 1) =cN-l[U(.)n=OBecause of W F k = W$2, the even numbered DFT points X ( 2 k ) turn outto be the DFT of the half-length sequence U(.)W(.)The odd numbered+90Chapter 4. Examples o f Discrete Transforms40)41)42)d3)44)45)46)47)-1-1-1Figure 4.4. Flow graph for an 8-point decimation-in-frequency FFT.+DFT points X(2k 1) are the DFT of [u(n)- w(n)]W;. Thus, as with thedecimation-in-time algorithm, the N-point DFTis decomposed into two N/2point DFTs. Using the principle repeatedly resultsin an FFT algorithm wherethe input values appear in their natural order, but where the output valuesappear in bitreversed order. Thecomplexity is the same as for the decimationin-time FFT.
Figure 4.4 shows the complete flow graph of the decimation-infrequency FFT for the case N = 8. The comparison of Figures 4.3 and 4.4shows that thetwo graphs can beviewed as transposedversions of one another.4.4.3Radix-4 FFTThe radix-4 decimation-in-frequency FFT is derived by writing the DFT ascN-lX(k) =n=O.(n)w;k914.4. The FastFourier Transform+ m) yieldsSplitting X(k) into four subsequences X(4kNz ( n + .e-)WG"41w$4.(4.63)Thus, we have replaced the computation of an N-point DFT by four N/4point DFTs. One of these four DFTs requires no multiplication at all, and theothers require one complex multiplication per point.
Compared to the radix2 FFT this means 3 X (N/4) instead of N/2 multiplications for the twiddlefactors. However, the radix-4 algorithm requires only N/4-point DFTs, andit requires only half as many stages as a radix-2 one. Therefore, the overallnumber of multiplications is lower for the radix-4 case.4.4.4Split-Radix FFTThesplit-radix FFT [46], whichis amixture of the radix-2 and radix-4algorithm, requires the lowest number of operations of all currently knownFFT algorithms.
It is also easily programmed on a computer.The radix-2approach is used to compute the even numbered frequencies, and the radix4 approach isused to compute two length-(N/4) subsequences of the oddnumbered frequencies. For this, X(k) is split into the following three subsets:cc[N/2-1X(2k) =n7+z(n[X(.)+ ;)lW$,(4.64)n=OX(4k+ 1)N/4-1=[X(.)- z(n+ -)]N2[X(.)- z(n+ -)]N2n=OX(4k+ 3)c[N/4-1=n=ONN+ j [ z ( n+ -)+ 34)1] W$'W$,. (4.66)and [z(n+): - z ( n + y)]in (4.65) and (4.66)4+- z(n- z ( n $)]The terms [X(.)are the natural pairsto the terms in (4.64).Thus,asplit-radixbutterflycan be drawn as shown in Figure 4.5. As with the previous approaches, thedecomposition principle can be used repeatedly.
It turns out that the splitradix approach requires less multiplications than a pure radix-2 or radix4 FFT, because fewerfull complex multiplications occur. Thesplit-radix92Chapter 4. Examples o f Discrete Transforms0use for X(4k+l)0use for X(4k+3)Figure 4.5. Butterfly for a split-radix FFT.conceptcanbegeneralized to other radices [152], and special forms areavailable for real and real-symmetric data [45, 1381.4.4.5Further FFT AlgorithmsThere area number of algorithms available for the case where the DFT lengthis not necessarily a power of two. The best known one is the Cooley-Tukey F F T[31], which requires that the DFT-length is a composite number N = P&,where P and Q are integers.
The DFT can then be written asccP-1 Q-lX ( k P + m) =+z(iQ j ) W,(iQ+j)(kP+m)(4.67)j=Oi=Ofor k = 0, 1,.. .,P - 1 and m = 0, 1 , . . . , Q - 1. The inner sum in the secondline of (4.67) turns out to bea P-point DFT, and the outer sumis a Q-pointDFT.
Thus, the N-point DFT is decomposed into P Q-point and Q P-pointDFTs, plus the twiddle factors in the middle of the second line in (4.67). Ascan easily be verified, the complexity islower than for the direct N-pointDFT. If P and/or Q are composite themselves, the approach can be iterated,and the complexity can be further reduced. Note that the radix-2 approachoccurs as a special case where P = 2 and Q = N/2.If the DFT-length canbe factored into N = P Q where P and Q arerelatively prime (have no common divisor other than 1) a powerful algorithmknown as the Good-Thomas F F T can be used. The basic idea dates backto papers by Good [64] and Thomas [143].
The algorithm has been furtherdeveloped in [88, 164, 20,1421. The efficiency of the Good-Thomas FFTTransforms4.5. Discrete Cosine93results from the fact that for relatively prime P and Q the twiddle factors(they arealways present in the Cooley-Tukey FFT) can beavoided. The inputdata can be arranged in a two-dimensional array, and the transform can beimplemented as a true two-dimensional transform. The mapping is based onthe Chinese remainder theorem [g].FFTs where N is a prime number can be realized via circular convolution[120, 101. In order to give an idea of how this is done, we follow the approachin [l01 and write the DFT ascN-lX ( k )=x(n)W;k = W;;c[x(n)W&]W,,-(k-n)'(4.68)n=OThe sum on the right side can be identified as a circular convolution of thesequences x(n)Wp$, and W;;', that isX ( n ) = W;; [ x(n)W& * W'$].(4.69)Efficiency is achievedby implementing the circular convolution via fastconvolution based on the FFT, see e.g.
[117].Powerful FFT algorithms are most often associated with signal lengthsthat are powers of two. However, prime factor algorithms such as the Winograd FFT [l641 are often competitive, if not superior, to the power-of-twoapproaches.
Thus, when designing an algorithm where the DFT is involved,one should not be bound to certain block lengths, because for almost anylength an appropriate FFT algorithm can be found.4.5Discrete Cosine TransformsWe distinguish the following four types of discrete cosine transforms (DCTs)[122]:DCT-I:..., N .c o s ( k$ ,)n, = 0 , 1 ,c:(")=&%(4.70)DCT-11:c:'(.)= &yk(k ( n + ) ,+)TCOSk , n =0,1,..., N- 1.(4.71)94Chapter 4. Examples o f Discrete TransformsDCT-111:cL"(n) =6(yn cos (Ic'2)""),5,n = 0 , 1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
