fft.ps

Data Structure Ebook

Fh(12.8)55 b(The)19 b(Butter\015y)262 1655 y Fn(T)m(o)g(sa)o(v)o(e)h
(the)h(o)o(v)o(erhead)f(of)g(recursiv)o(e)h(calls,)g(e\016cien)o(t)g
(FFT)f(routines)h(are)f(iterativ)o(e,)262 1704 y(replacing)e(the)h
Fm(n)f Fn(v)n(alues)g(input)h(to)f(eac)o(h)h(of)f(the)h(log)6
b Fm(n)19 b Fn(stages)g(with)f(the)h(new)g(v)n(alues)262
1754 y(calculated)14 b(in)f(that)h(stage.)262 1804 y(The)f(com)o
(bination)e(stage)i(in)g(the)h(recursiv)o(e)h(algorithm)10
b(ma)o(y)h(b)q(e)j(represen)o(ted)i(diagram-)262 1854
y(matically:)505 2262 y @beginspecial 0 @llx 0 @lly 179
@urx 68 @ury 2267 @rwi @setspecial
%%BeginDocument: butterfly.eps
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {} def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
-59.0 97.0 translate
1 -1 scale

/clp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/l {lineto} bind def
/m {moveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
 /DrawEllipse {
	/endangle exch def
	/startangle exch def
	/yrad exch def
	/xrad exch def
	/y exch def
	/x exch def
	/savematrix mtrx currentmatrix def
	x y tr xrad yrad sc 0 0 1 startangle endangle arc
	closepath
	savematrix setmatrix
	} def

/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
10 setmiterlimit
 0.04200 0.04200 sc
45.000 slw
% Polyline
n 2700 2100 m 3300 900 l  gs col-1 s gr 
n 3210.56 967.08 m 3300.00 900.00 l 3300.00 1011.80 l gs col-1 s gr
% Polyline
n 1800 2100 m 4200 2100 l  gs col-1 s gr 
% Polyline
n 1950 1575 m 2100 1575 l  2325 2025 l  gs col-1 s gr 
% Polyline
n 1800 900 m 4200 900 l  gs col-1 s gr 
% Polyline
n 2670 915 m 3270 2115 l  gs col-1 s gr 
n 3270.00 2003.20 m 3270.00 2115.00 l 3180.56 2047.92 l gs col-1 s gr
% Ellipse
n 3750 2100 168 168 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col-1 s gr

% Ellipse
n 2382 2082 168 168 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col-1 s gr

% Ellipse
n 3750 900 168 168 0 360 DrawEllipse gs col7 1.00 shd ef gr gs col-1 s gr

/Times-Roman findfont 240.00 scalefont setfont
1800 1725 m
gs 1 -1 sc (n) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1800 1575 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
3750 975 m
gs 1 -1 sc (+) dup stringwidth pop 2 div neg 0 rmoveto  col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4500 900 m
gs 1 -1 sc (y) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4650 825 m
gs 1 -1 sc (e) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4650 1050 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5400 900 m
gs 1 -1 sc (y) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5550 825 m
gs 1 -1 sc (o) col-1 show gr
/Symbol findfont 240.00 scalefont setfont
1650 1650 m
gs 1 -1 sc (w) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1575 2250 m
gs 1 -1 sc (k) col-1 show gr
/Symbol findfont 240.00 scalefont setfont
5025 900 m
gs 1 -1 sc (w) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5175 825 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1575 2025 m
gs 1 -1 sc (o) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4500 2100 m
gs 1 -1 sc (y) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4650 2025 m
gs 1 -1 sc (e) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4650 2250 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5400 2100 m
gs 1 -1 sc (y) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5550 2025 m
gs 1 -1 sc (o) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5550 2250 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4875 900 m
gs 1 -1 sc (+) dup stringwidth pop 2 div neg 0 rmoveto  col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5550 1050 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1425 2100 m
gs 1 -1 sc (y) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1575 1050 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1575 825 m
gs 1 -1 sc (e) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
1425 900 m
gs 1 -1 sc (y) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5175 1050 m
gs 1 -1 sc (n) col-1 show gr
/Helvetica findfont 240.00 scalefont setfont
2400 2175 m
gs 1 -1 sc (x) dup stringwidth pop 2 div neg 0 rmoveto  col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
3750 2175 m
gs 1 -1 sc (-) dup stringwidth pop 2 div neg 0 rmoveto  col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
4875 2100 m
gs 1 -1 sc (-) dup stringwidth pop 2 div neg 0 rmoveto  col-1 show gr
/Symbol findfont 240.00 scalefont setfont
5025 2100 m
gs 1 -1 sc (w) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5175 2025 m
gs 1 -1 sc (k) col-1 show gr
/Times-Roman findfont 240.00 scalefont setfont
5175 2250 m
gs 1 -1 sc (n) col-1 show gr
$F2psEnd
restore
%%EndDocument
 @endspecial 262 2350 a(Standard)k(iterativ)o(e)h(algorithms)d(simply)h
(stac)o(k)i Fm(n)f Fn(of)g(these)j(`butter\015ies')e(\(so-called)262
2399 y(b)q(ecause)e(of)e(the)i(shap)q(e)g(of)e(the)h(diagram\))e(v)o
(ertically)h(and)h(then)h(replicate)f(this)g(stac)o(k)262
2449 y(for)13 b(log)7 b Fm(n)14 b Fn(stages.)20 b(The)14
b(results)i(from)c(eac)o(h)j(stage)f(o)o(v)o(erwrite)h(those)g(from)d
(the)j(previous)967 2574 y(4)p eop
%%Page: 5 5
5 4 bop 262 307 a Fn(one.)27 b(A)17 b(`bit-t)o(widdling')d(function)i
(determines)h(whic)o(h)g(butter\015y)h(in)e(the)i(stage)f
Fm(k)12 b Fn(+)g(1)262 357 y(the)i(outputs)g(of)g(the)g(butter\015y)h
(in)f(stage)g Fm(k)h Fn(are)f(sen)o(t.)p 262 407 1418
6 v 272 456 a Fb(c)262 457 y Fa(\015)p Fb(John)f(Morris,)h(1996)967
2574 y Fn(5)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF