Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 133 of 229

Working implementation of FHT unsigned int Regular,Reversed; int BitsToMove,nibble; static const unsigned char bitrev16[J {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}; ReversedBase = 0; RemainingRegularBase = RegularBase; BitsToMove = nBits - 4; while(BitsToMove) { if(BitsToMove >= 4) { ReversedBase = >= 4; BitsToMove -= 4; } else //(Less than 4 bits to move ... ) { ReversedBase = (Reversed8ase<<1) + (RemainingRegularBase & 1); RemainingRegularBase >>= 1; Bi tsToMove--; } } ReversedBase <<= 4; Regular = RegularBase; for(nibble=O; nibble<16; nibble++) { Reversed = ReversedBase + bitrev16[nibbleJ; if(Regular <= Reversed) { To[ Regular J = From[ Reversed J; To[ Reversed J = From[ Regular J; } Regular += baseN; } } II Perform the first two rounds of FHT at once From = WorkArray; To = DataArray; To_ArrayEnd = To + dataN; while(To != To_ArrayEnd) { DataType a,b,c,d; To[QJ = (a=FromCOJ + From[1J) + (b=From[2J + From[3J); Listing 1 continued on p. 134 ably stuffed your real-valued sequence in to the real parts of an array of com- plex numbers and zeroed out the imag- inary parts. Having all those zeroes using up space but providing no infor- mation always bothered me. Then, when tl1e Fourier transform was done, the resulting array of complex numbers had a lot of redundancy. In particular, you never had to look past the mid- point of the array (the so-called yquist frequency) because th e frequency domain data in the second half of tl1e array was a kind of mirror image of the first half. The complex-valued F(N-j) is just the complex conjugate of F(j). (This is only true for tl1e Fourier trans- form of real-valued sequences. In gen- eral, the Fourier tnmsform has no such redundancy.) When I saw how the power of t11e FolllĀ·ier transfonn was being "wasted" on real-valued sequences, I finally understood how something like the Hartley transform could be more effi cient. Butterflies Now let's get down to business and see how the Hartley transform can be implemented effi ciently as the FHT. The development is similar to that of t11e FFT, which is not presented here but can be found in any textbook on digital signal processing. The heart of the algorithm is a computation whose data-fl ow diagram looks like a butte rfly. But unlike the symmetric butterfly of tl1e FFT, tl1e FHT butterfly, as shown in Figure l , is a bit ugly. lt has a vestigial t11ird \ving. From now o n we will be assuming that N is a power of two. Since N is even, the time sequence, X(t), which appears in th e de finiti o n of th e Hartley transform (Equation 1), can be divided into two intertwin ed sequences, X0 and X1, given by: X0 (t) = X(2t) x,(t) = x(2t + t) That is, sequence Xo consists of t11e even-indexed values from sequence X and sequence X1 132 SEPTEMBER 2000 Embedded Systems Programming consists of the odd-

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10