Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 137 of 229

I ! .. ID TABLE 1 Points N 256 2,048 16,384 131,072 float 0.48ms 7.0ms 0.10s 1.4s double 0.62m5 9.1ms 0.135 1.85 defin e the complete FHT butterfly computa tion , as diagrammed in Figure 1. These two equations express the Hartley transform of length N in terms of two smaller (half- length) Hartley transforms. This is the begin- ning of a recursive process. At each step in the recursion we recognize that all of the Hartley tran forms from the previous step can be furth er broken down into Hartley transforms of half the length. The process continues until we have only Hartley transforms of length 1, which can be trivially com- puted from Equation 1. At this point I wi ll abandon math e- In-Circuit Emulators matical rigor and proceed by example alone. Suppose N = 16. Figure 2 shows a data-flow diagram that illustra tes the recursive decomposition of a Hartley transform of length 16. Although the data-flow diagram is computed from left to right, we hall analyze it from right to left. On the far right, the num- bers 0 to 15 represent the values of /-1(0) through /-1(15) , which is the Ha rtley transform of the original sequence X(O) through X(15). If you let f run from 0 to 7 in Equations 3 and 4, you can see how the 16 values of H can be computed from the two smaller Hartley trans- Preserve your investment in time and capital with universal emulators from iSYSTEM. A complete line, from low-cost BDM/JTAG to high-end full-function ICEs. Support for over 400 micro- controllers with a simple swap of the POD or software setup. Driven with an intuitive development environment integrating all popular compilers. Thousands in use world-wide. Call for your free demo CD. America Europe Scandinavia Asia Pacific 1 (888) 543-5300 49 (8131) 70610 46 (40) 459571 82 (2) 2645-0386 t SYSTEM www. isystem .com Visit us at Embedded Systems Conference 2000, Booth #2709 136 SEPTEMBER 2000 Embedded Systems Programming form s, /-10 and /-11, each of length 8. The right-most column of data-flow lines in Figure 2 illustrates this process as the overlay of eight instances of the butterfly diagram from Figure 1. The lines have been omitted where the cor- responding trig factor is zero. In the column of numbers to the left of the final butterfly diagrams, the two sets of indices, 0 through 7, represent the value of /-10 and /-11 with /-10 on top. For example, the first three instances of Equations 3 and 4 in this column of butterflies i : H(O) = lf2{ H0(0) + H,(O)cos(O) + H,(O)sin(O)} H(8) = 1/2{ H0(0)- H,(O)cos(O)- H,(O)sin(O)} H(1) = 1/2{ H0 (1)+ H1(1) cos(Jt/8) + H1 H(9) = 1/2{ H0 (1)- H,(1)cos(Jt/8)- H1 H(2) = 1/2{H0(2) + H1 (7)sin(Jt/8)} (7)sin(Jt/8)} (2)cos(Jt/4) + H,(6) sin(Jt/4)} H(10) = lf2{H0(2)- H1(2)cos(Jt/4)- H1 (6)sin(~t/4)} Note that the indices of /-10 and /-11 have been reduced modulo 8, since tl1ey are Hartley transforms of length 8. The decomposition then continues with the next column to the left, show- ing how /-10 and /-11 are each repre-

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10