Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 139 of 229

Working implementation of FHT whi le(1) { From++; To++; FromRetrograde--; if( To == To_QuadrantEnd ) break; CSTenn = •Sinptr * FromRetrograde[OJ - •Cosptr * From[ButterflyWidthJ; To[OJ = Frani:OJ + CSTenn; To[ButterflyWidthJ = From[OJ - CSTenn; Sinptr -= ButterflyBlocks; Cosptr += ButterflyBlocks; } From += ButterflyWidth; To += ButterflyWidth; } ButterflyWidth <<= 1; ButterflyBlocks >>= 1; SwapTE!fl1l = FrcrnArray; I I Swap "from" and "to" arrays FrcrnArray = ToArray; ToArray = SwapTE!fl1l; } } void PowerSpectrum(DataType *PQWer, DataType *dht, int nBits) II converts Hartley transfonn dht[O .•. N-1] into power spectrum 11 power[O ... NI2J. The power spectrum array is one entry longer than 11 half as long as the DHT because it is symmetrical after the 11 mid-frequency anyway. It is OK to call with power=dht and use II only the first Nl2+1 elements of dht on return. { unsigned int N, i,r.ninusl; N = 1 « nBits; for(i=O; i <= Nl2; i++) { r.ninusl = (i==O)? 0 : ; } } void ScaleHartleyTransfonn(DataType *data, int nBits) { unsigned int i,N; DataType Nrecip; N = 1«rBits; Nrecip = 1 I (DataType)N; for loop return FrcrnArray; · · . ," · · · :. · ··· ,. sented in terms of Hartley transforms oflength 4. H0 is decomposed into Hoo and H01, H10 while H1 and H11. is decomposed into The numbers 0 through 3 are indice into these smaller Hartley transforms. The recursion process continues all the way back to the first column, where we would have 16 Hartley trans- forms of length l. Equation 1 shows that a Hartley transform of a time sequence of length 1 is just the origi- nal time sequence itself. So the first column represents values from the original time sequence X(t) . The num- bers in that column are the indices into the original time sequence, X( t). But how did tl1ey get into that strange order? To answer tl1is question we must de termine exactly which time sequence is transformed into each of the Hartley transforms in Figure 2. Starting again at the right, we know that the fu ll Hartley transform is derived from the original time sequence X(O) through X(15) in nor- mal order. Going back one step in the recursion and recalling how the small- er Hartley transforms in Equations 3 and 4 were defined, we see that H1 the Hartley transform of the sequence i X(O), X(2), ... , X(14) and H1 is the Hartley transform of the sequence X(1 ), X(3), .. . , X(15) . Purely as a com- putational convenience, we place the time sequence for H1 after the time sequence for H0. We have effectively sorted the sequence, X, according to the least-significant bit of its indices. In going from Hartley transf01·ms of length 8 to Hartley transforms of length 4, we further refine tl1e sort on X ba ed on the next-least-significant bit of its indices. That is: H00 is based on {X(O) , X(4), X(8) , X(l2)} H01 is based on {X(2) , X(6) , X(l O) , X(l4)} H10 is based on {X( l ) , X(5) , X(9), X(l 3)} H11 i based on {X(3) , X(7) , X(ll ), X(l5)} At each stage in this progressive sort, the results of th e previous sort are preserved. Therefore when we

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10