Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 143 of 229

Equations 3 and 4. Each such evalua- tion involves a sine, a cosine, two mul- tiplications, and two additio ns. To make things quick, the trig values can be in pre-computed lookup tables. Additionally, we recognize that in each butterfly calculation , the terms in Equation 3 are the same as the terms in Equation 4, except for a difference in signs. Referring to the example of N=16, this allows us to calculate terms H(O) through H(7) and get H(8) through H(15) almost fo r free. This also means that we only need values of sine and cosine for angles from zero to just under 180 degrees. In fact, I choose to implement the smallest pos- sible trig lookup table, namely, the val- ues of sin(x) in the first quadrant (zero to 90 degrees). The values of sine in the second quadrant as well as the values of cosine in both quadrants will come from this table using the uig identities: CSTerm = *CosPtr * sin(x + tr/2) = sin(x) cos(x) = sin(rr/2- x) cos(x + tr/2) = -cos(x) Thus to perform a Hartley trans- form of length N, we only need to pre- compute the N/ 4 values of sin (x) in the first quadrant. In order to simplify accessing this table, I have separate code for the first and second quad- rants. The tl1i rd and fourtl1 quadrants are done as a byproduct using the sym- metry noted in Equation 4. Let's jump right to the heart of tl1e implementation. The inner-most loop is essentially: while(in first quadrant) { From++; To++; FromRetrograde--; SinPtr += ButterflyBLocks; CosPtr -= ButterflyBLocks; } This has been exu·acted and simpli- fied from Listing 1. The actual imple- mentation of Equation 3 is in the cal- culation for To[QJ. The calculation for To[ButterflyWidthJ shows tl1e use of the symmeU}' of Equation 4. As you can see, CSTerm only needs to be calcu- lated once for each pair of Hartley transform values. Both Si nPtr and CosPtr point into the pre-computed sine lookup table, but tl1ey run in opposite directions to give the sine and cosine. T he for values each for ButterflyWidth and ButterflyBLocks change round. ButterflyWi dth is the index offset between tl1e two outputs of the butter- fly. It starts at four for round three and doubles in each ro und. Attention Engineers ... Keil Software C51 is the leading C compiler development suite for the 8051 family of microcontrollers. The features in Version 6 help you write and test your embedded applications faster. Call us to get the latest CD-ROM and FREE evaluation tools . Keil CSl Benefits • t.Nision2 IDE & debugger speed software development and application testing • Web-based updates keep your tools current • Training at our facility or yours shortens the learning curve • Answers to over 1,000 questions are available around the clock on our web site Keil Software, Inc. 1501 1Oth Street. Suite 110 Plano, TX 75074 Toll-Free .......... 800-348-8051 Phone... 142 SEPTEMBER 2000 Embedded Systems Programming .. .. 972-312-11 07 FAX .................. 972-312-1159 Upgrade Today ... New Features in V6 • 32-bit programs work with Windows 95/98/NT/2000 and support long file names • Three new optimizer levels help shrink program size up to 25% • Integrated source browser • Complete device database sets all compiler, assembler, and linker options for you • Kernel-aware debugging Butterf LyBLocks is the number of Hartley transforms on the output side of each round. It is cut in half after each round, ending up at one for the last round. I should point out he re tl1at the code actually computes double the Hartley transform at each row because we ignore the facto r of 1/ 2 in Equations 3 and 4. This makes our final result too large by a factor of N In many applications this error is irrel- evant since only relative values are used. But if correct scaling is required, a separate scaling function, ScaleHartleyTransformO, is provided in the code. Without calling this func- tion you actually get the reverse Hartley transform. You will notice that two of the three terms in Equation 3 involve indices that increment as the target index increments. But the third term in tl1at equation uses a backwards-running index. This has been called tl1e "reu·o- grade index" in the literature. It is what I call the ugly third wing of the From[ButterflyWidthJ + *SinPtr * FrarRetrograde[OJ; To[OJ = From[OJ + CSTerm; To[ButterflyWidthJ = From[OJ - CSTerm;

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10