EETimes

Embedded Systems September 2000 Vol13_10

Issue link: http://dc.ee.ubm-us.com/i/71837

Contents of this Issue

Navigation

Page 135 of 229

LISTING 1, continued Working implementation of FHT .. ·:. · To[1] = (c=From[QJ - From[1J) + (d=From[2J - From[3]); To[2J = a - b; To[3] = c - d; To ~ 4; From ~ 4; } II Start general butterfly calculations with round 3 ... FromArray = DataArray; ToArray = WorkArray; ButterflyWidth = 4; while( ButterflyBlocks ) { From = FromArray; To = ToArray; To_ArrayEnd = ToArray + dataN; while(To != To_ArrayEnd) { II This while loop does a single butterfly block DataType CSTerm; II Special 0 degrees case ..• To[OJ = From[OJ + From[ButterflyWidthJ; To[ButterflyWidthJ = From[OJ - From[ButterflyWidthJ; II .. then the rest of the first quadrant ... To_QuadrantEnd = To + ButterflyWidth12; SinPtr = TrigPtr; CosPtr = TrigPtr + TrigArraySize; II beyond end of trig array FromRetrograde = From + ButterflyWidth + ButterflyWidth; while(1) { From++; To++; FromRetrograde--; if( To == To_QuadrantEnd ) break; SinPtr ~ ButterflyBlocks; CosPtr -= ButterflyBlocks; CSTerm = *CosPtr * From[ButterflyWidthJ + *SinPtr * FromRetrograde[OJ; To[QJ = From[QJ + CSTerm; To[ButterflyWidthJ = From[OJ - CSTerm; } II Special 90 degrees case •.• To[OJ = From[OJ + FromRetrograde[OJ; To[ButterflyWidthJ = From[OJ - FromRetrograde[OJ; II .. then the rest of the second quadrant •.. To_QuadrantEnd = To + ButterflyWidthl2; Listing 1 continued on p. 138 134 SEPTEMBER 2000 Embedded Systems Programming · ··::, indexed values. As before, we will con- sider all indices to be interpreted modulo-N. But since Xo and X1 are defined in terms of 2t, they actually repeat modulo N/ 2. So consider Xo and X1 as sequences oflength N/ 2 and let H0 and H1 be their Hartley trans- forms. Let M tand for N/ 2. Then, by the definiti on of the Hartley transfom1 in Equation 1 we have: H0(f)= ~ %x0(r{cos( :)+sin( Zt)] 2 2 I I first two rounds are done ... ButterflyBlocks = dataNIB; II these parameters are set for round 3. H,(f) = ~ %x,(r{cos( :)+sin( 2 2 : )J I leave it as an exercise for the read- er to verify that: (3) (If you are reading the Byte article, note that this equation is incorrectly shown with N, instead of N.) It took me about half an hour to verify this equation with paper and pencil, using only ilie trig identities: sin(A)cos(B) = sin( A+ B)+ sin( A- B) 2 sin(A)sin(B) = cos( A - B) - cos( A + B) 2 cos(A)cos(B) = cos( A- B)+ cos( A+ B) 2 If you want to develop an appreciation of the basis of the Hartley transform, I recommend performing ilie exercise. Keeping in mind that ilie Hartley transforms on the righ t side of Equation 3 repeat modulo N/ 2, we can recognize the following symmeu-y: H ~) ~~H0(f)-H (! + = ,(f)cos(::)) - H,(N- f)sin( :) (4) Equations 3 and 4 taken together

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10