DIRECTORY Basics, Complex, FFT, IO, Random, RealFns, Rope; FFTImpl: CEDAR PROGRAM IMPORTS Basics, Complex, IO, Random, RealFns EXPORTS FFT = BEGIN OPEN FFT; pi: REAL = 3.14159276; radiansPerDeg: REAL _ pi/180.; TimeToFreq: PUBLIC PROC [ v: CVecRef ] = BEGIN p: NAT _ 1; exp: NAT _ 2; -- 2**p WHILE exp0 THEN s.PutRope[", "]; s.PutF[format: "%d: %g+j%g", v1: IO.int[i], v2: IO.real[v[i].x], v3: IO.real[v[i].y]]; ENDLOOP; RETURN[IO.RopeFromROS[s]]; END; -- of Print END. FFTImpl.mesa Routines to implement the Cooley-Tukey Fast Fourier Transform, etc. last modified by McCreight, November 14, 1984 10:59:51 am PST In-place bit-reversing shuffle the data Do butterfly stages dist is the number of points in this stage of DFT ... 1,2,3,..,v.size/2 ʨ˜Jšœ ™ J˜JšœC™CJ˜Jšœ=™=J˜šÏk ˜ Jšœ˜Jšœ˜Jšœ˜Jšœ˜J˜J˜J˜J˜—š œ œœœœœœ˜QJš˜J˜Jšœœ˜Jšœœ ˜J˜šÏn œœœ˜(Jš˜Jšœœ˜ JšœœÏc˜šœ ˜J˜ J˜Jšœ˜—Jšœ œœŸ˜-Jšœ'™'šœœœ ˜Jšœœ˜šœ˜ Jšœ.œ˜7—Jšœ˜—Jšœ™šœœ œ ˜.JšœH™HJ˜=J˜"šœœœ ˜J˜šœœœ ˜*Jšœœ ˜J˜&J˜J˜Jšœ˜—J˜JšœŸ8˜@Jšœ˜—Jšœ˜—JšœŸ˜J˜—šž œœœ˜'Jš˜Jšœœ˜šœœœ ˜Jšœ˜Jšœ˜—Jšœ˜šœœœ ˜J˜?Jšœ˜—JšœŸ˜J˜—š žœœœœœ˜HJšœŸ(˜.Jšœ˜ šœœœœ˜J˜—J˜Jšœœ˜ šœ œ˜šœœœœ˜.Jšœœ˜%—J˜Jšœ˜—Jšœœ˜JšœŸ ˜J˜J˜—š žœ œ œ1œœ˜oJš˜Jšœœœ0˜@Jšœœ ˜Jšœ˜Jš œœœ œœ˜9Jšœ˜J˜—J˜šžœ œœ˜@Jš˜Jšœœ˜Jšœ˜Jš œœœ œœ˜4Jšœ˜J˜J˜—šž œ œH˜_Jš˜šœœœ ˜JšœP˜PJšœ˜—Jšœ˜J˜J˜—š žœœœœœ ˜OJš˜Jšœ"˜"Jšœ+˜+JšœL˜Lšœœœ˜ Jšœ^˜^Jšœ˜—Jšœ˜šœœœ ˜Jšœ˜Jšœ˜—Jšœ˜J˜—J˜šž œ œœœ˜?Jšœœ6˜=J˜—šž œ œœœ˜?Jšœœ1˜8J˜J˜—š žœœœœœ˜9Jš˜Jš œœœœœ˜šœœœ ˜Jšœœ˜Jšœ!œ œœ˜VJšœ˜—Jšœœ˜JšœŸ ˜J˜—šœ˜J˜J˜—J˜——…— h*