Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 141 of 229

If you are familiar with the structure of the Fn; you will recognize similarities in the FHT. get back to th e beginning of th e data-flow diagram, we have the orig- inal sequence, X, listed in an order where the signifi cance of th e bits in the indices has bee n reversed. This is called bit-reve rsed order, and it is just as applicable to the FFT as it is to the FHT. Thus, to pe rform the FHT, we mus t firs t reord er th e sequence, X, into bit-reversed ord er. Then we pe r fo rm the butte rfly com- putations as they are diagramed in Figure 2. U S Software Knows Why CAD-UL is #1. U S Software knows who to count on when they need a partner for x86 embedded development tools. And it looks like they're not alone. According to VDC, CAD-UL is the number one revenue generator of x86 embedded development tools worldwide. Implementation If you are fa miliar wi th the structure of the FFT, you will recognize similarities in the FHT. One important diffe rence is that you cannot do the FHT "in place." Computing the transform "in place" means that your initial array of time domain values is used to hold all the intermediate calculations and the resulting transform ends up in the same array. This i possible with the FFT because the butte rfly operations all have two inputs and two outputs which are in the same array location as the inputs. You can load your time domain equence into an array and then perform butterfly calculations two elements at a time. The reason this is not possible with the FHT is that the butterfly operation takes three inputs to produce two outputs. If the outputs are immediately stored in the original array, then an input to some other butte rfly operation will get over- written before it is used. When we calculate the FHT, we CAD-UL U S SCFTWAAE. • EMB E DD E D EKC ~ LL E NC£ • Real-Time Operating System • Embedded TCP/IP Protocol Suite • Embedded File System • Distributed Computing (800) 356-7097 • CIC++ x86 Compiler Systems • Symbolic Debugging Systems • IDE: CAD-UL Workbench • Code Coverage Tools (877) GO CAD-UL must have two arrays. Each round of calculations uses one array fo r input (the FromArray in the code) and the other array for output (the ToArray in the code). Which array the fin al trans- form ends up in depends on whether you had to do an even or an odd num- ber of butte rfly calculation rounds. In any case, this inability to do a trans- form in place contradicts the opening claim of O'Neill 's article that only half the memory is needed for the FHT. It is true that the FHT uses only real-val- ued arrays instead of the complex-val- ued arrays needed by the FFT, and so the arrays use half as much memory. But you need two of those arrays wi th the FHT and only one array with the FFT, therefore the memory usage i a wash. In general, each round of calcula- tions requires N/ 2 evaluations of 140 SEPTEMBER 2000 Embedded Systems Programming

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10