Fast Fourier Transforms (6x9 Version) by C. Sidney Burrus - HTML preview

/ Home / Engineering / Fast Fourier Transforms (6x9 Version)

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub for a complete version.

262

APPENDIX

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲●❊◆❊❘❆▲ ❇❯❚❚❊❘❋▲❨✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❉❖ ✷✵ ❏ ❂ ✷✱ ◆✷

■❆✶ ❂ ■❆✶ ✰ ■❊

■❋ ✭❏✳❊◗✳❏❚✮ ●❖❚❖ ✺✵

■❆✷ ❂ ■❆✶ ✰ ■❆✶ ✲ ✶

■❆✸ ❂ ■❆✷ ✰ ■❆✶ ✲ ✶

❈❖✶ ❂ ❲❘✭■❆✶✮

❈❖✷ ❂ ❲❘✭■❆✷✮

❈❖✸ ❂ ❲❘✭■❆✸✮

❙■✶ ❂ ❲■✭■❆✶✮

❙■✷ ❂ ❲■✭■❆✷✮

❙■✸ ❂ ❲■✭■❆✸✮

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲❇❯❚❚❊❘❋▲■❊❙ ❲■❚❍ ❙❆▼❊ ❲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❉❖ ✸✵ ■ ❂ ❏✱ ◆✱ ◆✶

■✶ ❂ ■ ✰ ◆✷

■✷ ❂ ■✶ ✰ ◆✷

■✸ ❂ ■✷ ✰ ◆✷

❘✶ ❂ ❳✭■ ✮ ✰ ❳✭■✷✮

❘✸ ❂ ❳✭■ ✮ ✲ ❳✭■✷✮

❙✶ ❂ ❨✭■ ✮ ✰ ❨✭■✷✮

❙✸ ❂ ❨✭■ ✮ ✲ ❨✭■✷✮

❘✷ ❂ ❳✭■✶✮ ✰ ❳✭■✸✮

❘✹ ❂ ❳✭■✶✮ ✲ ❳✭■✸✮

❙✷ ❂ ❨✭■✶✮ ✰ ❨✭■✸✮

❙✹ ❂ ❨✭■✶✮ ✲ ❨✭■✸✮

❈

❳✭■✮ ❂ ❘✶ ✰ ❘✷

❘✷

❂ ❘✶ ✲ ❘✷

❘✶

❂ ❘✸ ✲ ❙✹

❘✸

❂ ❘✸ ✰ ❙✹

❈

❨✭■✮ ❂ ❙✶ ✰ ❙✷

❙✷

❂ ❙✶ ✲ ❙✷

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

APPENDIX

263

❙✶

❂ ❙✸ ✰ ❘✹

❙✸

❂ ❙✸ ✲ ❘✹

❈

❳✭■✶✮ ❂ ❈❖✶✯❘✸ ✰ ❙■✶✯❙✸

❨✭■✶✮ ❂ ❈❖✶✯❙✸ ✲ ❙■✶✯❘✸

❳✭■✷✮ ❂ ❈❖✷✯❘✷ ✰ ❙■✷✯❙✷

❨✭■✷✮ ❂ ❈❖✷✯❙✷ ✲ ❙■✷✯❘✷

❳✭■✸✮ ❂ ❈❖✸✯❘✶ ✰ ❙■✸✯❙✶

❨✭■✸✮ ❂ ❈❖✸✯❙✶ ✲ ❙■✸✯❘✶

✸✵

❈❖◆❚■◆❯❊

●❖❚❖ ✷✵

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲❙P❊❈■❆▲ ❇❯❚❚❊❘❋▲❨ ❋❖❘ ❲ ❂ ❏✲✲✲✲✲✲✲✲✲✲✲

✺✵

❉❖ ✹✵ ■ ❂ ❏✱ ◆✱ ◆✶

■✶ ❂ ■ ✰ ◆✷

■✷ ❂ ■✶ ✰ ◆✷

■✸ ❂ ■✷ ✰ ◆✷

❘✶ ❂ ❳✭■ ✮ ✰ ❳✭■✷✮

❘✸ ❂ ❳✭■ ✮ ✲ ❳✭■✷✮

❙✶ ❂ ❨✭■ ✮ ✰ ❨✭■✷✮

❙✸ ❂ ❨✭■ ✮ ✲ ❨✭■✷✮

❘✷ ❂ ❳✭■✶✮ ✰ ❳✭■✸✮

❘✹ ❂ ❳✭■✶✮ ✲ ❳✭■✸✮

❙✷ ❂ ❨✭■✶✮ ✰ ❨✭■✸✮

❙✹ ❂ ❨✭■✶✮ ✲ ❨✭■✸✮

❈

❳✭■✮ ❂ ❘✶ ✰ ❘✷

❨✭■✷✮❂✲❘✶ ✰ ❘✷

❘✶

❂ ❘✸ ✲ ❙✹

❘✸

❂ ❘✸ ✰ ❙✹

❈

❨✭■✮ ❂ ❙✶ ✰ ❙✷

❳✭■✷✮❂ ❙✶ ✲ ❙✷

❙✶

❂ ❙✸ ✰ ❘✹

❙✸

❂ ❙✸ ✲ ❘✹

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

264

APPENDIX

❈

❳✭■✶✮ ❂ ✭❙✸ ✰ ❘✸✮✯❈✷✶

❨✭■✶✮ ❂ ✭❙✸ ✲ ❘✸✮✯❈✷✶

❳✭■✸✮ ❂ ✭❙✶ ✲ ❘✶✮✯❈✷✶

❨✭■✸✮ ❂✲✭❙✶ ✰ ❘✶✮✯❈✷✶

✹✵

❈❖◆❚■◆❯❊

✷✵

❈❖◆❚■◆❯❊

✶✵

❈❖◆❚■◆❯❊

❈✲✲✲✲✲✲✲✲✲✲✲❉■●■❚ ❘❊❱❊❘❙❊ ❈❖❯◆❚❊❘✲✲✲✲✲✲✲✲✲✲

✶✵✵

❏ ❂ ✶

◆✶ ❂ ◆ ✲ ✶

❉❖ ✶✵✹ ■ ❂ ✶✱ ◆✶

■❋ ✭■✳●❊✳❏✮ ●❖❚❖ ✶✵✶

❘✶

❂ ❳✭❏✮

❳✭❏✮ ❂ ❳✭■✮

❳✭■✮ ❂ ❘✶

❘✶

❂ ❨✭❏✮

❨✭❏✮ ❂ ❨✭■✮

❨✭■✮ ❂ ❘✶

✶✵✶

❑ ❂ ◆✴✹

✶✵✷

■❋ ✭❑✯✸✳●❊✳❏✮ ●❖❚❖ ✶✵✸

❏ ❂ ❏ ✲ ❑✯✸

❑ ❂ ❑✴✹

●❖❚❖ ✶✵✷

✶✵✸

❏ ❂ ❏ ✰ ❑

✶✵✹

❈❖◆❚■◆❯❊

❘❊❚❯❘◆

❊◆❉

18.10 Basic DIF Split Radix FFT Algorithm

Below is the Fortran code for a simple Decimation-in-Frequency,

Split-Radix, one butterfly FFT to be followed by a bit-reversing

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

APPENDIX

265

unscrambler.

❈

❆ ❉❯❍❆▼❊▲✲❍❖▲▲▼❆◆◆ ❙P▲■❚ ❘❆❉■❳ ❋❋❚ P❘❖●❘❆▼

❈

❋❘❖▼✿ ❊▲❊❈❚❘❖◆■❈❙ ▲❊❚❚❊❘❙✱ ❏❆◆✳ ✺✱ ✶✾✽✹

❈

❈❖▼P▲❊❳ ■◆P❯❚ ❉❆❚❆ ■◆ ❆❘❘❆❨❙ ❳ ❆◆❉ ❨

❈

▲❊◆●❚❍ ■❙ ◆ ❂ ✷ ✯✯ ▼

❈

❈✳ ❙✳ ❇❯❘❘❯❙✱ ❘■❈❊ ❯◆■❱❊❘❙■❚❨✱ ▼❆❘❈❍ ✶✾✽✹

❈❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❙❯❇❘❖❯❚■◆❊ ❋❋❚ ✭❳✱❨✱◆✱▼✮

❘❊❆▲ ❳✭✶✮✱ ❨✭✶✮

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲▼❆■◆ ❋❋❚ ▲❖❖P❙✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❈

◆✶ ❂ ◆

◆✷ ❂ ◆✴✷

■P ❂ ✵

■❙ ❂ ✶

❆ ❂ ✻✳✷✽✸✶✽✺✸✵✼✶✼✾✺✽✻✴◆

❉❖ ✶✵ ❑ ❂ ✶✱ ▼✲✶

❏❉ ❂ ◆✶ ✰ ◆✷

◆✶ ❂ ◆✷

◆✷ ❂ ◆✷✴✷

❏✵ ❂ ◆✶✯■P ✰ ✶

■P ❂ ✶ ✲ ■P

❉❖ ✷✵ ❏ ❂ ❏✵✱ ◆✱ ❏❉

❏❙ ❂ ✵

❏❚ ❂ ❏ ✰ ◆✷ ✲ ✶

❉❖ ✸✵ ■ ❂ ❏✱ ❏❚

❏❙❙❂ ❏❙✯■❙

❏❙ ❂ ❏❙ ✰ ✶

❈✶ ❂ ❈❖❙✭❆✯❏❙❙✮

❈✸ ❂ ❈❖❙✭✸✯❆✯❏❙❙✮

❙✶ ❂ ✲❙■◆✭❆✯❏❙❙✮

❙✸ ❂ ✲❙■◆✭✸✯❆✯❏❙❙✮

■✶ ❂ ■ ✰ ◆✷

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

266

APPENDIX

■✷ ❂ ■✶ ✰ ◆✷

■✸ ❂ ■✷ ✰ ◆✷

❘✶

❂ ❳✭■ ✮ ✰ ❳✭■✷✮

❘✷

❂ ❳✭■ ✮ ✲ ❳✭■✷✮

❘✸

❂ ❳✭■✶✮ ✲ ❳✭■✸✮

❳✭■✷✮ ❂ ❳✭■✶✮ ✰ ❳✭■✸✮

❳✭■✶✮ ❂ ❘✶

❈

❘✶

❂ ❨✭■ ✮ ✰ ❨✭■✷✮

❘✹

❂ ❨✭■ ✮ ✲ ❨✭■✷✮

❘✺

❂ ❨✭■✶✮ ✲ ❨✭■✸✮

❨✭■✷✮ ❂ ❨✭■✶✮ ✰ ❨✭■✸✮

❨✭■✶✮ ❂ ❘✶

❈

❘✶

❂ ❘✷ ✲ ❘✺

❘✷

❂ ❘✷ ✰ ❘✺

❘✺

❂ ❘✹ ✰ ❘✸

❘✹

❂ ❘✹ ✲ ❘✸

❈

❳✭■✮ ❂ ❈✶✯❘✶ ✰ ❙✶✯❘✺

❨✭■✮ ❂ ❈✶✯❘✺ ✲ ❙✶✯❘✶

❳✭■✸✮ ❂ ❈✸✯❘✷ ✰ ❙✸✯❘✹

❨✭■✸✮ ❂ ❈✸✯❘✹ ✲ ❙✸✯❘✷

✸✵

❈❖◆❚■◆❯❊

✷✵

❈❖◆❚■◆❯❊

■❙ ❂ ■❙ ✰ ■❙

✶✵

❈❖◆❚■◆❯❊

■P ❂ ✶ ✲ ■P

❏✵ ❂ ✷ ✲ ■P

❉❖ ✺ ■ ❂ ❏✵✱ ◆✲✶✱ ✸

■✶ ❂ ■ ✰ ✶

❘✶

❂ ❳✭■✮ ✰ ❳✭■✶✮

❳✭■✶✮ ❂ ❳✭■✮ ✲ ❳✭■✶✮

❳✭■✮ ❂ ❘✶

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

APPENDIX

267

❘✶

❂ ❨✭■✮ ✰ ❨✭■✶✮

❨✭■✶✮ ❂ ❨✭■✮ ✲ ❨✭■✶✮

❨✭■✮ ❂ ❘✶

✺

❈❖◆❚■◆❯❊

❘❊❚❯❘◆

❊◆❉

18.11 DIF Split Radix FFT Algorithm

Below is the Fortran code for a simple Decimation-in-Frequency,

Split-Radix, two butterfly FFT to be followed by a bit-reversing

unscrambler. Twiddle factors are precalculated and stored in arrays

WR and WI.

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲❈

❈

❆ ❉❯❍❆▼❊▲✲❍❖▲▲▼❆◆ ❙P▲■❚ ❘❆❉■❳ ❋❋❚

❈

❘❊❋✿ ❊▲❊❈❚❘❖◆■❈❙ ▲❊❚❚❊❘❙✱ ❏❆◆✳ ✺✱ ✶✾✽✹

❈

❈❖▼P▲❊❳ ■◆P❯❚ ❆◆❉ ❖❯❚P❯❚ ❉❆❚❆ ■◆ ❆❘❘❆❨❙ ❳ ❆◆❉ ❨

❈

▲❊◆●❚❍ ■❙ ◆ ❂ ✷ ✯✯ ▼✱ ❖❯❚P❯❚ ■◆ ❇■❚✲❘❊❱❊❘❙❊❉ ❖❘❉❊❘

❈

❚❲❖ ❇❯❚❚❊❘❋▲■❊❙ ❚❖ ❘❊▼❖❱❊ ▼❯▲❚❙ ❇❨ ❯◆■❚❨

❈

❙P❊❈■❆▲ ▲❆❙❚ ❚❲❖ ❙❚❆●❊❙

❈

❚❆❇▲❊ ▲❖❖❑✲❯P ❖❋ ❙■◆❊ ❆◆❉ ❈❖❙■◆❊ ❱❆▲❯❊❙

❈

❈✳❙✳ ❇❯❘❘❯❙✱

❘■❈❊ ❯◆■❱✳

❆P❘■▲ ✶✾✽✺

❈

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲❈

❈

❙❯❇❘❖❯❚■◆❊ ❋❋❚✭❳✱❨✱◆✱▼✱❲❘✱❲■✮

❘❊❆▲ ❳✭✶✮✱❨✭✶✮✱❲❘✭✶✮✱❲■✭✶✮

❈✽✶❂ ✵✳✼✵✼✶✵✻✼✼✽

◆✷ ❂ ✷✯◆

❉❖ ✶✵ ❑ ❂ ✶✱ ▼✲✸

■❙ ❂ ✶

■❉ ❂ ◆✷

◆✷ ❂ ◆✷✴✷

◆✹ ❂ ◆✷✴✹

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

268

APPENDIX

✷

❉❖ ✶ ■✵ ❂ ■❙✱ ◆✲✶✱ ■❉

■✶ ❂ ■✵ ✰ ◆✹

■✷ ❂ ■✶ ✰ ◆✹

■✸ ❂ ■✷ ✰ ◆✹

❘✶

❂ ❳✭■✵✮ ✲ ❳✭■✷✮

❳✭■✵✮ ❂ ❳✭■✵✮ ✰ ❳✭■✷✮

❘✷

❂ ❨✭■✶✮ ✲ ❨✭■✸✮

❨✭■✶✮ ❂ ❨✭■✶✮ ✰ ❨✭■✸✮

❳✭■✷✮ ❂ ❘✶ ✰ ❘✷

❘✷

❂ ❘✶ ✲ ❘✷

❘✶

❂ ❳✭■✶✮ ✲ ❳✭■✸✮

❳✭■✶✮ ❂ ❳✭■✶✮ ✰ ❳✭■✸✮

❳✭■✸✮ ❂ ❘✷

❘✷

❂ ❨✭■✵✮ ✲ ❨✭■✷✮

❨✭■✵✮ ❂ ❨✭■✵✮ ✰ ❨✭■✷✮

❨✭■✷✮ ❂✲❘✶ ✰ ❘✷

❨✭■✸✮ ❂ ❘✶ ✰ ❘✷

✶

❈❖◆❚■◆❯❊

■❙ ❂ ✷✯■❉ ✲ ◆✷ ✰ ✶

■❉ ❂ ✹✯■❉

■❋ ✭■❙✳▲❚✳◆✮ ●❖❚❖ ✷

■❊ ❂ ◆✴◆✷

■❆✶ ❂ ✶

❉❖ ✷✵ ❏ ❂ ✷✱ ◆✹

■❆✶ ❂ ■❆✶ ✰ ■❊

■❆✸ ❂ ✸✯■❆✶ ✲ ✷

❈❈✶ ❂ ❲❘✭■❆✶✮

❙❙✶ ❂ ❲■✭■❆✶✮

❈❈✸ ❂ ❲❘✭■❆✸✮

❙❙✸ ❂ ❲■✭■❆✸✮

■❙ ❂ ❏

■❉ ❂ ✷✯◆✷

✹✵

❉❖ ✸✵ ■✵ ❂ ■❙✱ ◆✲✶✱ ■❉

■✶ ❂ ■✵ ✰ ◆✹

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

APPENDIX

269

■✷ ❂ ■✶ ✰ ◆✹

■✸ ❂ ■✷ ✰ ◆✹

❈

❘✶

❂ ❳✭■✵✮ ✲ ❳✭■✷✮

❳✭■✵✮ ❂ ❳✭■✵✮ ✰ ❳✭■✷✮

❘✷

❂ ❳✭■✶✮ ✲ ❳✭■✸✮

❳✭■✶✮ ❂ ❳✭■✶✮ ✰ ❳✭■✸✮

❙✶

❂ ❨✭■✵✮ ✲ ❨✭■✷✮

❨✭■✵✮ ❂ ❨✭■✵✮ ✰ ❨✭■✷✮

❙✷

❂ ❨✭■✶✮ ✲ ❨✭■✸✮

❨✭■✶✮ ❂ ❨✭■✶✮ ✰ ❨✭■✸✮

❈

❙✸

❂ ❘✶ ✲ ❙✷

❘✶

❂ ❘✶ ✰ ❙✷

❙✷

❂ ❘✷ ✲ ❙✶

❘✷

❂ ❘✷ ✰ ❙✶

❳✭■✷✮ ❂ ❘✶✯❈❈✶ ✲ ❙✷✯❙❙✶

❨✭■✷✮ ❂✲❙✷✯❈❈✶ ✲ ❘✶✯❙❙✶

❳✭■✸✮ ❂ ❙✸✯❈❈✸ ✰ ❘✷✯❙❙✸

❨✭■✸✮ ❂ ❘✷✯❈❈✸ ✲ ❙✸✯❙❙✸

✸✵

❈❖◆❚■◆❯❊

■❙ ❂ ✷✯■❉ ✲ ◆✷ ✰ ❏

■❉ ❂ ✹✯■❉

■❋ ✭■❙✳▲❚✳◆✮ ●❖❚❖ ✹✵

✷✵

❈❖◆❚■◆❯❊

✶✵

❈❖◆❚■◆❯❊

❈

■❙ ❂ ✶

■❉ ❂ ✸✷

✺✵

❉❖ ✻✵ ■ ❂ ■❙✱ ◆✱ ■❉

■✵

❂ ■ ✰ ✽

❉❖ ✶✺ ❏ ❂ ✶✱ ✷

❘✶ ❂ ❳✭■✵✮

✰ ❳✭■✵✰✷✮

❘✸ ❂ ❳✭■✵✮

✲ ❳✭■✵✰✷✮

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

270

APPENDIX

❘✷ ❂ ❳✭■✵✰✶✮ ✰ ❳✭■✵✰✸✮

❘✹ ❂ ❳✭■✵✰✶✮ ✲ ❳✭■✵✰✸✮

❳✭■✵✮

❂ ❘✶ ✰ ❘✷

❳✭■✵✰✶✮ ❂ ❘✶ ✲ ❘✷

❘✶ ❂ ❨✭■✵✮

✰ ❨✭■✵✰✷✮

❙✸ ❂ ❨✭■✵✮

✲ ❨✭■✵✰✷✮

❘✷ ❂ ❨✭■✵✰✶✮ ✰ ❨✭■✵✰✸✮

❙✹ ❂ ❨✭■✵✰✶✮ ✲ ❨✭■✵✰✸✮

❨✭■✵✮

❂ ❘✶ ✰ ❘✷

❨✭■✵✰✶✮ ❂ ❘✶ ✲ ❘✷

❨✭■✵✰✷✮ ❂ ❙✸ ✲ ❘✹

❨✭■✵✰✸✮ ❂ ❙✸ ✰ ❘✹

❳✭■✵✰✷✮ ❂ ❘✸ ✰ ❙✹

❳✭■✵✰✸✮ ❂ ❘✸ ✲ ❙✹

■✵ ❂ ■✵ ✰ ✹

✶✺

❈❖◆❚■◆❯❊

✻✵

❈❖◆❚■◆❯❊

■❙ ❂ ✷✯■❉ ✲ ✶✺

■❉ ❂ ✹✯■❉

■❋ ✭■❙✳▲❚✳◆✮ ●❖❚❖ ✺✵

❈

■❙ ❂ ✶

■❉ ❂ ✶✻

✺✺

❉❖ ✻✺ ■✵ ❂ ■❙✱ ◆✱ ■❉

❘✶ ❂ ❳✭■✵✮

✰ ❳✭■✵✰✹✮

❘✺ ❂ ❳✭■✵✮

✲ ❳✭■✵✰✹✮

❘✷ ❂ ❳✭■✵✰✶✮ ✰ ❳✭■✵✰✺✮

❘✻ ❂ ❳✭■✵✰✶✮ ✲ ❳✭■✵✰✺✮

❘✸ ❂ ❳✭■✵✰✷✮ ✰ ❳✭■✵✰✻✮

❘✼ ❂ ❳✭■✵✰✷✮ ✲ ❳✭■✵✰✻✮

❘✹ ❂ ❳✭■✵✰✸✮ ✰ ❳✭■✵✰✼✮

❘✽ ❂ ❳✭■✵✰✸✮ ✲ ❳✭■✵✰✼✮

❚✶ ❂ ❘✶ ✲ ❘✸

❘✶ ❂ ❘✶ ✰ ❘✸

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

APPENDIX

271

❘✸ ❂ ❘✷ ✲ ❘✹

❘✷ ❂ ❘✷ ✰ ❘✹

❳✭■✵✮

❂ ❘✶ ✰ ❘✷

❳✭■✵✰✶✮ ❂ ❘✶ ✲ ❘✷

❈

❘✶ ❂ ❨✭■✵✮

✰ ❨✭■✵✰✹✮

❙✺ ❂ ❨✭■✵✮

✲ ❨✭■✵✰✹✮

❘✷ ❂ ❨✭■✵✰✶✮ ✰ ❨✭■✵✰✺✮

❙✻ ❂ ❨✭■✵✰✶✮ ✲ ❨✭■✵✰✺✮

❙✸ ❂ ❨✭■✵✰✷✮ ✰ ❨✭■✵✰✻✮

❙✼ ❂ ❨✭■✵✰✷✮ ✲ ❨✭■✵✰✻✮

❘✹ ❂ ❨✭■✵✰✸✮ ✰ ❨✭■✵✰✼✮

❙✽ ❂ ❨✭■✵✰✸✮ ✲ ❨✭■✵✰✼✮

❚✷ ❂ ❘✶ ✲ ❙✸

❘✶ ❂ ❘✶ ✰ ❙✸

❙✸ ❂ ❘✷ ✲ ❘✹

❘✷ ❂ ❘✷ ✰ ❘✹

❨✭■✵✮

❂ ❘✶ ✰ ❘✷

❨✭■✵✰✶✮ ❂ ❘✶ ✲ ❘✷

❳✭■✵✰✷✮ ❂ ❚✶ ✰ ❙✸

❳✭■✵✰✸✮ ❂ ❚✶ ✲ ❙✸

❨✭■✵✰✷✮ ❂ ❚✷ ✲ ❘✸

❨✭■✵✰✸✮ ❂ ❚✷ ✰ ❘✸

❈

❘✶ ❂ ✭❘✻ ✲ ❘✽✮✯❈✽✶

❘✻ ❂ ✭❘✻ ✰ ❘✽✮✯❈✽✶

❘✷ ❂ ✭❙✻ ✲ ❙✽✮✯❈✽✶

❙✻ ❂ ✭❙✻ ✰ ❙✽✮✯❈✽✶

❈

❚✶ ❂ ❘✺ ✲ ❘✶

❘✺ ❂ ❘✺ ✰ ❘✶

❘✽ ❂ ❘✼ ✲ ❘✻

❘✼ ❂ ❘✼ ✰ ❘✻

❚✷ ❂ ❙✺ ✲ ❘✷

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

272

APPENDIX

❙✺ ❂ ❙✺ ✰ ❘✷

❙✽ ❂ ❙✼ ✲ ❙✻

❙✼ ❂ ❙✼ ✰ ❙✻

❳✭■✵✰✹✮ ❂ ❘✺ ✰ ❙✼

❳✭■✵✰✼✮ ❂ ❘✺ ✲ ❙✼

❳✭■✵✰✺✮ ❂ ❚✶ ✰ ❙✽

❳✭■✵✰✻✮ ❂ ❚✶ ✲ ❙✽

❨✭■✵✰✹✮ ❂ ❙✺ ✲ ❘✼

❨✭■✵✰✼✮ ❂ ❙✺ ✰ ❘✼

❨✭■✵✰✺✮ ❂ ❚✷ ✲ ❘✽

❨✭■✵✰✻✮ ❂ ❚✷ ✰ ❘✽

✻✺

❈❖◆❚■◆❯❊

■❙ ❂ ✷✯■❉ ✲ ✼

■❉ ❂ ✹✯■❉

■❋ ✭■❙✳▲❚✳◆✮ ●❖❚❖ ✺✺

❈❈✲✲✲✲✲✲✲✲✲✲✲✲❇■❚ ❘❊❱❊❘❙❊ ❈❖❯◆❚❊❘✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❈ ✶✵✵ ❏ ❂ ✶

◆✶ ❂ ◆ ✲ ✶

❉❖ ✶✵✹ ■❂✶✱ ◆✶

■❋ ✭■✳●❊✳❏✮ ●❖❚❖ ✶✵✶

❳❚ ❂ ❳✭❏✮

❳✭❏✮ ❂ ❳✭■✮

❳✭■✮ ❂ ❳❚

❳❚

❂ ❨✭❏✮

❨✭❏✮ ❂ ❨✭■✮

❨✭■✮ ❂ ❳❚

✶✵✶

❑ ❂ ◆✴✷

✶✵✷

■❋ ✭❑✳●❊✳❏✮ ●❖❚❖ ✶✵✸

❏ ❂ ❏ ✲ ❑

❑ ❂ ❑✴✷

●❖❚❖ ✶✵✷

✶✵✸

❏ ❂ ❏ ✰ ❑

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

APPENDIX

273

✶✵✹

❈❖◆❚■◆❯❊

❘❊❚❯❘◆

❊◆❉

18.12 Prime Factor FFT Algorithm

Below is the Fortran code for a Prime-Factor Algorithm (PFA) FFT

allowing factors of the length of 2, 3, 4, 5, and 7. It is followed by

an unscrambler.

❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❈❈ ❆ P❘■▼❊ ❋❆❈❚❖❘ ❋❋❚ P❘❖●❘❆▼ ❲■❚❍ ●❊◆❊❘❆▲ ▼❖❉❯▲❊❙

❈

❈❖▼P▲❊❳ ■◆P❯❚ ❉❆❚❆ ■◆ ❆❘❘❆❨❙ ❳ ❆◆❉ ❨

❈

❈❖▼P▲❊❳ ❖❯❚P❯❚ ■◆ ❆ ❆◆❉ ❇

❈

▲❊◆●❚❍ ◆ ❲■❚❍ ▼ ❋❆❈❚❖❘❙ ■◆ ❆❘❘❆❨ ◆■

❈

◆ ❂ ◆■✭✶✮✯◆■✭✷✮✯ ✳✳✳ ✯◆■✭▼✮

❈

❯◆❙❈❘❆▼❇▲■◆● ❈❖◆❙❚❆◆❚ ❯◆❙❈

❈

❯◆❙❈ ❂ ◆✴◆■✭✶✮ ✰ ◆✴◆■✭✷✮ ✰✳✳✳✰ ◆✴◆■✭▼✮✱ ▼❖❉ ◆

❈

❈✳ ❙✳ ❇❯❘❘❯❙✱ ❘■❈❊ ❯◆■❱❊❘❙■❚❨✱ ❏❆◆ ✶✾✽✼

❈❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❈

❙❯❇❘❖❯❚■◆❊ P❋❆✭❳✱❨✱◆✱▼✱◆■✱❆✱❇✱❯◆❙❈✮

❈

■◆❚❊●❊❘ ◆■✭✹✮✱ ■✭✶✻✮✱ ❯◆❙❈

❘❊❆▲ ❳✭✶✮✱ ❨✭✶✮✱ ❆✭✶✮✱ ❇✭✶✮

❈

❉❆❚❆ ❈✸✶✱ ❈✸✷ ✴ ✲✵✳✽✻✻✵✷✺✹✵✱✲✶✳✺✵✵✵✵✵✵✵ ✴

❉❆❚❆ ❈✺✶✱ ❈✺✷ ✴ ✵✳✾✺✶✵✺✻✺✷✱✲✶✳✺✸✽✽✹✶✽✵ ✴

❉❆❚❆ ❈✺✸✱ ❈✺✹ ✴ ✲✵✳✸✻✸✷✼✶✷✻✱ ✵✳✺✺✾✵✶✻✾✾ ✴

❉❆❚❆ ❈✺✺

✴ ✲✶✳✷✺ ✴

❉❆❚❆ ❈✼✶✱ ❈✼✷ ✴ ✲✶✳✶✻✻✻✻✻✻✼✱✲✵✳✼✾✵✶✺✻✹✼ ✴

❉❆❚❆ ❈✼✸✱ ❈✼✹ ✴ ✵✳✵✺✺✽✺✹✷✻✼✱ ✵✳✼✸✹✸✵✷✷ ✴

Available for free at Connexions

<http://cnx.org/content/col10683/1.5>

274

APPENDIX

❉❆❚❆ ❈✼✺✱ ❈✼✻ ✴ ✵✳✹✹✵✾✺✽✺✺✱✲✵✳✸✹✵✽✼✷✾✸ ✴

❉❆❚❆ ❈✼✼✱ ❈✼✽ ✴ ✵✳✺✸✸✾✻✾✸✻✱ ✵✳✽✼✹✽✹✷✷✾ ✴

❈❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲◆❊❙❚❊❉ ▲❖❖P❙✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲

❈

❉❖ ✶✵ ❑❂✶✱ ▼

◆✶ ❂ ◆■✭❑✮