Embedded Systems September 2000 Vol13_10

Issue link:

Contents of this Issue


Page 130 of 229

What could be so magical about correlating against a sine function that was shifted by an arbitrary amount? Well, the answer is "nothing." that article again and decided to delve into it to see what the story was. I was so impressed with what I learned that I immediately wrote a little freeware u tili ty fo r gene• was shifted by an a•·bitrary amount? ·al aviation enthusi- asts-a PC program to measure tl1e RPM of an airplane engine based on the sound of tl1at engin e. The pro- gram (available a t - rscott/[) uses the Hartley transform to find tl1e peaks in the fre- quency spectrum. The pattern and location of the frequency peaks deter- min e the RPM. Hartley transform defined The Hartley transform was first pro- posed in 1942 by Ralph Hartl ey. This is the same fe llow, by the way, who inve nted the well-known Hartley oscil- lato• · circuit. just as in tl1e Fo urie r transform, the Hartley u·ansfo rm star ts with a seque nce of samples in the time domain. Let X(t) fo r t = 0 . .. N-1 be uch a sequence. The Hart.ley trans- form of thi s seque nce is a nothe r sequence, H(f) for f = 0 ... N-1 given by: H(f ) = ~ ~X(t{co{2 ~)+sin(2 ~)] (1) If, for some reason, you want to undo tl1is u·ansforn1 , the fommla is almost identical, except for the absence of the 1/ N facto r: X(t) =% H(f{ co{2 ~) + sin( 2 ~)] The first tl1ing that made me suspi- cious about these formulae was tlut the sum of tl1e cosine and the sine of an angle is just anot11er phase-shifted sine function (shifted by 45 degrees, to be exact). What could be so magical about correlating against a sine function tl1at Well , tl1e answer is "noth ing." In fact, it is possible to define a whole class of reversible transforms based on other phase-shifted sine functions. But the specific sine fun ction used in tl1e Hartley transform exh ibi ts a certain symmeu·y between the transform and its inverse. And when it comes to implementing tl1e u-ansform, we wi ll see that we end up taking pure sines and cosines any- way and not their sums. Comparisons with the FFT In a 1988 article in Byle, • Mark 0 ' eill gave form u- lae simi lar to the ones shown above; but note the typo in his Equation 5, FIGURE l FHT data flow A 16-point sequence, X, generates its Hartley transform, H. The lines represent instances of the single butterfly calculation from Figure 1. Lines have been ommited for null terms. HOOO H001 X 0 8 4 12 2 10 6 14 9 ::=::==:::::::: ::::::::::::><: :::::::::><:::: ::::::::::::><: :::::::><:: 11 7 1: ::::::::::::><: 3 :::::::>:<: 15 :::::::>:<: H111 HOO H01 H10 H11 which I have corrected. In addition to introducing the Hartley transform, O'Neill went on to develop the fast Hart.ley u·ansform, based on a 1984 articl e by Ronald Bracewell Proceedings of the IEEE. 2 in The results of recursion Equations 3 and 4 are combined in t his data-flow diagram. Blue represents terms with a cosine factor. Red represents terms with a sine factor. Black represents terms with no trig factors. HO H1 H 0 ...-------, 0 1 2 3 2 3 4 -M,~~'+flh4~ 4 5 6 7 0 ~~~~d 9 2 e611lrRt¥~~ 1 o 3 4 5 6 7 11 12 13 14 15 Embedded Systems Programming SEPTEMBER 2000 129 5 6 7 8

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems September 2000 Vol13_10