Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 145 of 229

FHT butterfl y. It is represented by FromRetrograde in the code. Bit reversal and special cases The transform code starts by permut- ing the input array according to the bit reversal pattern described earlier. This could take a lot of time if done in a brute-fo rce fashion, peeling off o ne bi t at a time. I have chosen to do it four bi ts at a time by using a pre-com- puted table of 16 bit-reversed nibbles. I generate all N bit-reversed pairs and, fo r each pair I interchange and trans- fe r the input array values to the other array if the pair of indices is increasing o r equal. Ifl did not check the relative magnitude of the paired indices, we would be transfe rring mo t values twice, which would not be bad but would waste some time. Note that the bit reversal could have been done in- place, but the other work array was availabl e so I used tha t instead. Because of the assumptions made in thi optimized bit reversal , the imple- mentatio n is limited to transforms of sequences whose length is at least 16. The fir t two rounds ofth e FHT are so simple that I do them all at once as a specia l case. They involve only degenerate oig values (0 or 1) . Also, the first computation of every set of butterflies is pecial because it has only two terms and no trig lookups. I have, therefore, structured the code to compute th e butterflies fo r ze ro degrees and 90 degrees as special cases. Interface details In order to use the FHT code, the call- ing program must first generate a o-ig table of th e appropriate size. The functio n Ini tTrigTableO is provided fo r just that purpose. The reafte r the clie nt code may call FastHartleyTransformO by providing the appropriate parameters. Notice that the client code is responsible for allocating all the arrays, and that the resulting transform may be in either the original input array or the work array. Also note that no static variables are used, so this implementation is re- e ntrant. The re turn value of FastHartleyTransformO is a pointer to the correct result array. As noted earlier, unlike the Fourier transform, the Hartley o-ansform has no natural inte rpretation as a frequen- cy specti-um. The most natural use for the Hartley transform is as a means to develop the Fo urier transform, as shown by Equation 2. The magnitude of the fi rs t half of the Fourier tran s- form is calculated PowerSpectrum() fun ction. Performance Classicall y, FFT performance has been evaluated by counting the number of multiplications, additions, and sub- tractions that are involved . In these terms, tl1e FHT does very well. If we disregard the simplicity of the first two rounds, we have each round requiring N multiplications and 2N additions o r subtractions. The number of rounds is log2N. By compa riso n, the FFT requires 2N multiplications and 7 N/ 2 additions o r subtractio ns in each round. In botl1 cases these numbers assume that no redundant operations are performed. But tl1is may not tell the whole sto ry. On mode rn processors with floating po in t capability, the tim e required to do arithmetic may not dominate the overall running time. Time spent in computing indices and other "overhead" operations may acnl- ally take mo re time than al l the multi- plications, especially in some of the demonstration programs th at are given as examples of a Hartley imple- mentation (as in O'Neilll ) . The implement.:'ltion in Listing 1 is meant as a real wo rking implementa- tion , not just a demo nso-ation. I admit that the cost-savings of performing the first two rounds as a special case does become a smaller percentage of the whole as tile number o r poin ts in the sequence increa es. But the savings gained by minimizing the number of function calls and parameters passed 144 SEPTEMBER 2000 Embedded Systems Programming by the in the inner-most loop is significant for transfonns of any length. If the Hartley transform is used o nly as a means to develop the Fourier transform, tl1e cost of converting to the Fourier o-ansform using Equation 2 should be taken in to accoun t in per- formance comparisons. This will add 2N additions to tl1e total number of operations if the FHT is used to gen- erate the FFT. However, if the goal is to develo p the power spectrum, which is the magnitude of th e complex Fourier transform values, tl1en there is no additional cost to the FHT. The operations in th e PowerSpectrumO function amount to no more than what would be required to perform tile magnitude calculations on the Fourier transform values. By tl1e use of a typedef, th e code in Listing 1 can be made to operate on either do ubles or fl oats. Table 1 con- tains some be nchma rks run on a 75MHz Pentium. Doing the job quickly Wheneve r real-valued sample sequences need to be transformed in to the frequency domain , the fast Hartley transform does the j ob in about half the time of tl1e fast Fourier transform. The FHT algorithm is sim- ple e nough to code that there is little reaso n to resort to thil-d-par ty librari es. With direct control over tl1e implement.:'ltion you can achieve opti- mizati ons that surpass the typi cal demo nstration implementation . esp l?.obert Scott is the fmsirlmt of l?.eal-Time Specialties, which pmvicles consulting ser- vices t)(lrticula· automotive industry. He can be macherl at rscott@wwnet. net. The code in this a-rticle is available at h un. References 1. O'Neill, Mark A, "Faster Than Fast Fourier," Byte, April1988, p. 293. 2. Bracewell , Ronald N., "The Fast Hartley Transform," Proceedings of the IEEE, vol. 72, no. 8, pp. 1010-1017, 1984. r to embedded systems in the

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10