DIRECTORY Basics, Complex, FFT, IO, Random, RealFns, Rope; FFTImpl: CEDAR PROGRAM IMPORTS Basics, Complex, IO, Random, RealFns EXPORTS FFT = { OPEN FFT; pi: REAL = 3.14159276; radiansPerDeg: REAL _ pi/180.; TimeToFreq: PUBLIC PROC [ v: CVecRef ] = { 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]]; }; rs: Random.RandomStream _ Random.Create[]; }. `FFTImpl.mesa McCreight, November 14, 1984 10:59:51 am PST Russ Atkinson (RRA) May 24, 1985 5:54:01 pm PDT Routines to implement the Cooley-Tukey Fast Fourier Transform, etc. 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 reverse the low-order width bits of i Κ°˜codešœ ™ Kšœ,™,K™/K˜—KšœC™CK˜šΟk ˜ Kšœ˜Kšœ˜Kšœ˜Kšœ˜K˜K˜K˜K˜—šœ œ˜Kšœœ˜,Kšœœ˜Kšœœ˜ K˜Kšœœ˜Kšœœ ˜K˜šΟn œœœ˜*Kšœœ˜ KšœœΟc˜šœ ˜K˜ K˜Kšœ˜—Kšœ œœŸ˜-Kšœ'™'šœœœ ˜Kšœœ˜šœ˜ Kšœ œ!˜1—Kšœ˜—Kšœ™šœœ œ ˜.KšœH™HKšœ œ/˜=Kšœ œ˜"šœœœ ˜Kšœ œ˜šœœœ ˜*Kšœœ ˜Kšœ œ˜&K˜K˜Kšœ˜—K˜KšœŸ8˜@Kšœ˜—Kšœ˜—Kšœ˜K˜—šž œœœ˜)Kšœœ˜šœœœ ˜Kšœ˜Kšœ˜—Kšœ˜šœœœ ˜K˜?Kšœ˜—Kšœ˜K˜—š žœœœœœ˜JKšœ%™%Kšœ˜ šœœœœ˜K˜—K˜Kšœœ˜ šœ œ˜šœœœœ˜.Kšœœ˜%—K˜Kšœ˜—Kšœœ˜Kšœ˜K˜—š žœœœ œ1œœ˜qKšœœœ0˜@Kšœœ ˜Kšœ˜Kš œœœ œœ˜9Kšœ˜—K˜šžœœœœ˜BKšœœ˜Kšœ˜Kš œœœ œœ˜4Kšœ˜K˜K˜—šž œœœJ˜ašœœœ ˜KšœP˜PKšœ˜—Kšœ˜K˜—š žœœœœœ ˜QKšœ"˜"Kšœ+˜+KšœL˜Lšœœœ˜ šœ˜Kšœ˜Kšœ5˜5—Kšœ˜—Kšœ˜šœœœ ˜Kšœ˜Kšœ˜—Kšœ˜—K˜š ž œœœœœ˜AKšœ5˜;Kšœ˜K˜—š ž œœœœœ˜AKšœ0˜6Kšœ˜K˜—š žœœœœœ˜;Kš œœœœœ˜šœœœ ˜Kšœœ˜Kšœ!œ œœ˜VKšœ˜—Kšœœ˜Kšœ˜K˜—˜*K˜—šœ˜K˜K˜—K˜——…— ό