❘✺ ❂ ❘✶ ✰ ❘✸ ✰ ❘✼
❨✭■✭✶✮✮ ❂ ❚✵ ✰ ❘✺
❘✺ ❂ ❚✵ ✰ ❘✺ ✯ ❈✾✺
❚✵ ❂ ✭❘✸ ✲ ❘✼✮ ✯ ❈✾✷
❘✼ ❂ ✭❘✶ ✲ ❘✼✮ ✯ ❈✾✸
❘✸ ❂ ✭❘✶ ✲ ❘✸✮ ✯ ❈✾✹
❘✶ ❂ ❚✾ ✰ ❚✵ ✰ ❘✸
❚✵ ❂ ❚✾ ✲ ❚✵ ✲ ❘✼
❘✼ ❂ ❚✾ ✰ ❘✼ ✲ ❘✸
❘✾ ❂ ✭❘✷ ✲ ❘✹ ✰ ❘✽✮ ✯ ❈✸✶
❘✸ ❂ ✭❘✹ ✰ ❘✽✮ ✯ ❈✾✻
❘✽ ❂ ✭❘✷ ✲ ❘✽✮ ✯ ❈✾✼
❘✹ ❂ ✭❘✷ ✰ ❘✹✮ ✯ ❈✾✽
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
290
APPENDIX
❘✷ ❂ ❘✻ ✰ ❘✸ ✰ ❘✹
❘✸ ❂ ❘✻ ✲ ❘✽ ✲ ❘✸
❘✽ ❂ ❘✻ ✰ ❘✽ ✲ ❘✹
❈
❳✭■P✭✷✮✮ ❂ ❚✶ ✲ ❘✷
❳✭■P✭✾✮✮ ❂ ❚✶ ✰ ❘✷
❨✭■P✭✷✮✮ ❂ ❘✶ ✰ ❚✷
❨✭■P✭✾✮✮ ❂ ❘✶ ✲ ❚✷
❳✭■P✭✸✮✮ ❂ ❚✸ ✰ ❘✸
❳✭■P✭✽✮✮ ❂ ❚✸ ✲ ❘✸
❨✭■P✭✸✮✮ ❂ ❚✵ ✲ ❚✹
❨✭■P✭✽✮✮ ❂ ❚✵ ✰ ❚✹
❳✭■P✭✹✮✮ ❂ ❚✺ ✲ ❘✾
❳✭■P✭✼✮✮ ❂ ❚✺ ✰ ❘✾
❨✭■P✭✹✮✮ ❂ ❘✺ ✰ ❚✻
❨✭■P✭✼✮✮ ❂ ❘✺ ✲ ❚✻
❳✭■P✭✺✮✮ ❂ ❚✼ ✲ ❘✽
❳✭■P✭✻✮✮ ❂ ❚✼ ✰ ❘✽
❨✭■P✭✺✮✮ ❂ ❘✼ ✰ ❚✽
❨✭■P✭✻✮✮ ❂ ❘✼ ✲ ❚✽
❈
●❖❚❖ ✷✵
❈✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲❲❋❚❆ ◆❂✶✻✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲✲
❈ ✶✶✻ ❘✶ ❂ ❳✭■✭✶✮✮ ✰ ❳✭■✭✾✮✮
❘✷ ❂ ❳✭■✭✶✮✮ ✲ ❳✭■✭✾✮✮
❘✸ ❂ ❳✭■✭✷✮✮ ✰ ❳✭■✭✶✵✮✮
❘✹ ❂ ❳✭■✭✷✮✮ ✲ ❳✭■✭✶✵✮✮
❘✺ ❂ ❳✭■✭✸✮✮ ✰ ❳✭■✭✶✶✮✮
❘✻ ❂ ❳✭■✭✸✮✮ ✲ ❳✭■✭✶✶✮✮
❘✼ ❂ ❳✭■✭✹✮✮ ✰ ❳✭■✭✶✷✮✮
❘✽ ❂ ❳✭■✭✹✮✮ ✲ ❳✭■✭✶✷✮✮
❘✾ ❂ ❳✭■✭✺✮✮ ✰ ❳✭■✭✶✸✮✮
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
APPENDIX
291
❘✶✵❂ ❳✭■✭✺✮✮ ✲ ❳✭■✭✶✸✮✮
❘✶✶ ❂ ❳✭■✭✻✮✮ ✰ ❳✭■✭✶✹✮✮
❘✶✷ ❂ ❳✭■✭✻✮✮ ✲ ❳✭■✭✶✹✮✮
❘✶✸ ❂ ❳✭■✭✼✮✮ ✰ ❳✭■✭✶✺✮✮
❘✶✹ ❂ ❳✭■✭✼✮✮ ✲ ❳✭■✭✶✺✮✮
❘✶✺ ❂ ❳✭■✭✽✮✮ ✰ ❳✭■✭✶✻✮✮
❘✶✻ ❂ ❳✭■✭✽✮✮ ✲ ❳✭■✭✶✻✮✮
❚✶ ❂ ❘✶ ✰ ❘✾
❚✷ ❂ ❘✶ ✲ ❘✾
❚✸ ❂ ❘✸ ✰ ❘✶✶
❚✹ ❂ ❘✸ ✲ ❘✶✶
❚✺ ❂ ❘✺ ✰ ❘✶✸
❚✻ ❂ ❘✺ ✲ ❘✶✸
❚✼ ❂ ❘✼ ✰ ❘✶✺
❚✽ ❂ ❘✼ ✲ ❘✶✺
❘✶ ❂ ❚✶ ✰ ❚✺
❘✸ ❂ ❚✶ ✲ ❚✺
❘✺ ❂ ❚✸ ✰ ❚✼
❘✼ ❂ ❚✸ ✲ ❚✼
❳✭■P✭ ✶✮✮ ❂ ❘✶ ✰ ❘✺
❳✭■P✭ ✾✮✮ ❂ ❘✶ ✲ ❘✺
❚✶ ❂ ❈✽✶ ✯ ✭❚✹ ✰ ❚✽✮
❚✺ ❂ ❈✽✶ ✯ ✭❚✹ ✲ ❚✽✮
❘✾ ❂ ❚✷ ✰ ❚✺
❘✶✶❂ ❚✷ ✲ ❚✺
❘✶✸ ❂ ❚✻ ✰ ❚✶
❘✶✺ ❂ ❚✻ ✲ ❚✶
❚✶ ❂ ❘✹ ✰ ❘✶✻
❚✷ ❂ ❘✹ ✲ ❘✶✻
❚✸ ❂ ❈✽✶ ✯ ✭❘✻ ✰ ❘✶✹✮
❚✹ ❂ ❈✽✶ ✯ ✭❘✻ ✲ ❘✶✹✮
❚✺ ❂ ❘✽ ✰ ❘✶✷
❚✻ ❂ ❘✽ ✲ ❘✶✷
❚✼ ❂ ❈✶✻✷ ✯ ✭❚✷ ✲ ❚✻✮
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
292
APPENDIX
❚✷ ❂ ❈✶✻✸ ✯ ❚✷ ✲ ❚✼
❚✻ ❂ ❈✶✻✹ ✯ ❚✻ ✲ ❚✼
❚✼ ❂ ❘✷ ✰ ❚✹
❚✽ ❂ ❘✷ ✲ ❚✹
❘✷ ❂ ❚✼ ✰ ❚✷
❘✹ ❂ ❚✼ ✲ ❚✷
❘✻ ❂ ❚✽ ✰ ❚✻
❘✽ ❂ ❚✽ ✲ ❚✻
❚✼ ❂ ❈✶✻✺ ✯ ✭❚✶ ✰ ❚✺✮
❚✷ ❂ ❚✼ ✲ ❈✶✻✹ ✯ ❚✶
❚✹ ❂ ❚✼ ✲ ❈✶✻✸ ✯ ❚✺
❚✻ ❂ ❘✶✵ ✰ ❚✸
❚✽ ❂ ❘✶✵ ✲ ❚✸
❘✶✵ ❂ ❚✻ ✰ ❚✷
❘✶✷ ❂ ❚✻ ✲ ❚✷
❘✶✹ ❂ ❚✽ ✰ ❚✹
❘✶✻ ❂ ❚✽ ✲ ❚✹
❘✶ ❂ ❨✭■✭✶✮✮ ✰ ❨✭■✭✾✮✮
❙✷ ❂ ❨✭■✭✶✮✮ ✲ ❨✭■✭✾✮✮
❙✸ ❂ ❨✭■✭✷✮✮ ✰ ❨✭■✭✶✵✮✮
❙✹ ❂ ❨✭■✭✷✮✮ ✲ ❨✭■✭✶✵✮✮
❘✺ ❂ ❨✭■✭✸✮✮ ✰ ❨✭■✭✶✶✮✮
❙✻ ❂ ❨✭■✭✸✮✮ ✲ ❨✭■✭✶✶✮✮
❙✼ ❂ ❨✭■✭✹✮✮ ✰ ❨✭■✭✶✷✮✮
❙✽ ❂ ❨✭■✭✹✮✮ ✲ ❨✭■✭✶✷✮✮
❙✾ ❂ ❨✭■✭✺✮✮ ✰ ❨✭■✭✶✸✮✮
❙✶✵❂ ❨✭■✭✺✮✮ ✲ ❨✭■✭✶✸✮✮
❙✶✶ ❂ ❨✭■✭✻✮✮ ✰ ❨✭■✭✶✹✮✮
❙✶✷ ❂ ❨✭■✭✻✮✮ ✲ ❨✭■✭✶✹✮✮
❙✶✸ ❂ ❨✭■✭✼✮✮ ✰ ❨✭■✭✶✺✮✮
❙✶✹ ❂ ❨✭■✭✼✮✮ ✲ ❨✭■✭✶✺✮✮
❙✶✺ ❂ ❨✭■✭✽✮✮ ✰ ❨✭■✭✶✻✮✮
❙✶✻ ❂ ❨✭■✭✽✮✮ ✲ ❨✭■✭✶✻✮✮
❚✶ ❂ ❘✶ ✰ ❙✾
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
APPENDIX
293
❚✷ ❂ ❘✶ ✲ ❙✾
❚✸ ❂ ❙✸ ✰ ❙✶✶
❚✹ ❂ ❙✸ ✲ ❙✶✶
❚✺ ❂ ❘✺ ✰ ❙✶✸
❚✻ ❂ ❘✺ ✲ ❙✶✸
❚✼ ❂ ❙✼ ✰ ❙✶✺
❚✽ ❂ ❙✼ ✲ ❙✶✺
❘✶ ❂ ❚✶ ✰ ❚✺
❙✸ ❂ ❚✶ ✲ ❚✺
❘✺ ❂ ❚✸ ✰ ❚✼
❙✼ ❂ ❚✸ ✲ ❚✼
❨✭■P✭ ✶✮✮ ❂ ❘✶ ✰ ❘✺
❨✭■P✭ ✾✮✮ ❂ ❘✶ ✲ ❘✺
❳✭■P✭ ✺✮✮ ❂ ❘✸ ✰ ❙✼
❳✭■P✭✶✸✮✮ ❂ ❘✸ ✲ ❙✼
❨✭■P✭ ✺✮✮ ❂ ❙✸ ✲ ❘✼
❨✭■P✭✶✸✮✮ ❂ ❙✸ ✰ ❘✼
❚✶ ❂ ❈✽✶ ✯ ✭❚✹ ✰ ❚✽✮
❚✺ ❂ ❈✽✶ ✯ ✭❚✹ ✲ ❚✽✮
❙✾ ❂ ❚✷ ✰ ❚✺
❙✶✶❂ ❚✷ ✲ ❚✺
❙✶✸ ❂ ❚✻ ✰ ❚✶
❙✶✺ ❂ ❚✻ ✲ ❚✶
❚✶ ❂ ❙✹ ✰ ❙✶✻
❚✷ ❂ ❙✹ ✲ ❙✶✻
❚✸ ❂ ❈✽✶ ✯ ✭❙✻ ✰ ❙✶✹✮
❚✹ ❂ ❈✽✶ ✯ ✭❙✻ ✲ ❙✶✹✮
❚✺ ❂ ❙✽ ✰ ❙✶✷
❚✻ ❂ ❙✽ ✲ ❙✶✷
❚✼ ❂ ❈✶✻✷ ✯ ✭❚✷ ✲ ❚✻✮
❚✷ ❂ ❈✶✻✸ ✯ ❚✷ ✲ ❚✼
❚✻ ❂ ❈✶✻✹ ✯ ❚✻ ✲ ❚✼
❚✼ ❂ ❙✷ ✰ ❚✹
❚✽ ❂ ❙✷ ✲ ❚✹
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
294
APPENDIX
❙✷ ❂ ❚✼ ✰ ❚✷
❙✹ ❂ ❚✼ ✲ ❚✷
❙✻ ❂ ❚✽ ✰ ❚✻
❙✽ ❂ ❚✽ ✲ ❚✻
❚✼ ❂ ❈✶✻✺ ✯ ✭❚✶ ✰ ❚✺✮
❚✷ ❂ ❚✼ ✲ ❈✶✻✹ ✯ ❚✶
❚✹ ❂ ❚✼ ✲ ❈✶✻✸ ✯ ❚✺
❚✻ ❂ ❙✶✵ ✰ ❚✸
❚✽ ❂ ❙✶✵ ✲ ❚✸
❙✶✵ ❂ ❚✻ ✰ ❚✷
❙✶✷ ❂ ❚✻ ✲ ❚✷
❙✶✹ ❂ ❚✽ ✰ ❚✹
❙✶✻ ❂ ❚✽ ✲ ❚✹
❳✭■P✭ ✷✮✮ ❂ ❘✷ ✰ ❙✶✵
❳✭■P✭✶✻✮✮ ❂ ❘✷ ✲ ❙✶✵
❨✭■P✭ ✷✮✮ ❂ ❙✷ ✲ ❘✶✵
❨✭■P✭✶✻✮✮ ❂ ❙✷ ✰ ❘✶✵
❳✭■P✭ ✸✮✮ ❂ ❘✾ ✰ ❙✶✸
❳✭■P✭✶✺✮✮ ❂ ❘✾ ✲ ❙✶✸
❨✭■P✭ ✸✮✮ ❂ ❙✾ ✲ ❘✶✸
❨✭■P✭✶✺✮✮ ❂ ❙✾ ✰ ❘✶✸
❳✭■P✭ ✹✮✮ ❂ ❘✽ ✲ ❙✶✻
❳✭■P✭✶✹✮✮ ❂ ❘✽ ✰ ❙✶✻
❨✭■P✭ ✹✮✮ ❂ ❙✽ ✰ ❘✶✻
❨✭■P✭✶✹✮✮ ❂ ❙✽ ✲ ❘✶✻
❳✭■P✭ ✻✮✮ ❂ ❘✻ ✰ ❙✶✹
❳✭■P✭✶✷✮✮ ❂ ❘✻ ✲ ❙✶✹
❨✭■P✭ ✻✮✮ ❂ ❙✻ ✲ ❘✶✹
❨✭■P✭✶✷✮✮ ❂ ❙✻ ✰ ❘✶✹
❳✭■P✭ ✼✮✮ ❂ ❘✶✶ ✲ ❙✶✺
❳✭■P✭✶✶✮✮ ❂ ❘✶✶ ✰ ❙✶✺
❨✭■P✭ ✼✮✮ ❂ ❙✶✶ ✰ ❘✶✺
❨✭■P✭✶✶✮✮ ❂ ❙✶✶ ✲ ❘✶✺
❳✭■P✭ ✽✮✮ ❂ ❘✹ ✲ ❙✶✷
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
APPENDIX
295
❳✭■P✭✶✵✮✮ ❂ ❘✹ ✰ ❙✶✷
❨✭■P✭ ✽✮✮ ❂ ❙✹ ✰ ❘✶✷
❨✭■P✭✶✵✮✮ ❂ ❙✹ ✲ ❘✶✷
❈
●❖❚❖ ✷✵
❈ ✷✵
❈❖◆❚■◆❯❊
✶✵
❈❖◆❚■◆❯❊
❘❊❚❯❘◆
❊◆❉
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
296
APPENDIX
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
Appendix 4: Programs for
Short FFTs1
This appendix will discuss efficient short FFT programs that can
be used in both the Cooley-Tukey (Chapter 9) and the Prime Fac-
tor FFT algorithms (Chapter 10). Links and references are given to
Fortran listings that can be used "as is" or put into the indexed loops of existing programs to give greater efficiency and/or a greater variety of allowed lengths. Special programs have been written for
lengths: N = 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 25, etc.
In the early days of the FFT, multiplication was done in software
and was, therefore, much slower than an addition. With modem
hardware, a floating point multiplication can be done in one clock
cycle of the computer, microprocessor, or DSP chip, requiring the
same time as an addition. Indeed, in some computers and many
DSP chips, both a multiplication and an addition (or accumulation)
can be done in one cycle while the indexing and memory access is
done in parallel. Most of the algorithms described here are not
hardware architecture specific but are designed to minimize both
multiplications and additions.
The most basic and often used length FFT (or DFT) is for N = 2.
In the Cooley Tukey FFT, it is called a "butterfly" and its reason for fame is requiring no multiplications at all, only one complex addi-1This content is available online at <http://cnx.org/content/m17646/1.4/>.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
297
298
APPENDIX
tion and one complex subtraction and needing only one complex
temporary storage location. This is illustrated in Figure 1: The
Prime Factor and Winograd Transform Algorithms (Figure 10.1)
and code is shown in Figure 2: The Prime Factor and Winograd
Transform Algorithms (Figure 10.2). The second most used length
is N = 4 because it is the only other short length requiring no multi-
plications and a minimum of additions. All other short FFT require
some multiplication but for powers of two, N = 8 and N = 16 re-
quire few enough to be worth special coding for some situations.
Code for other short lengths such as the primes N =
3, 5, 7, 11, 13, 17, and 19 and the composites N = 9 and 25
are included in the programs for the prime factor algorithm or the
WFTA. They are derived using the theory in Chapters 5, 6, and 9.
They can also be found in references ... and
If these short FFTs are used as modules in the basic prime factor
algorithm (PFA), then the straight forward development used for
the modules in Figure 17.12 are used. However if the more com-
plicated indexing use to achieve in-order, in-place calculation used
in {xxxxx} require different code.
For each of the indicated lengths, the computer code is given in a
Connexions module.
They are not in the collection Fast Fourier Transforms2 as the
printed version would be too long. However, one can link to them
on-line from the following buttons:
◆❂✷3
◆❂✸4
◆❂✹5
2Fast Fourier Transforms <http://cnx.org/content/col10550/latest/>
3"N=2" <http://cnx.org/content/m17625/latest/>
4"N=3" <http://cnx.org/content/m17626/latest/>
5"N=4" <http://cnx.org/content/m17627/latest/>
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
APPENDIX
299
◆❂✺6
◆❂✼7
◆❂ ✽
◆❂ ✾
◆❂ ❧✶
◆❂ ✶✸
◆❂ ✶✻
◆❂ ✶✼
◆❂ ✶✾
◆❂ ✷✺
Versions for the in-place, in-order prime factor algorithm {pfa} can
be obtained from:
◆❂✷8
◆❂✸9
◆❂✹10
◆❂✺11
◆❂✼12
◆❂✽13
◆❂✾14
◆❂❧✶15
◆❂✶✸16
◆❂✶✻17
6"N=5" <http://cnx.org/content/m17628/latest/>
7"N=7" <http://cnx.org/content/m17629/latest/>
8"pN=2" <http://cnx.org/content/m17631/latest/>
9"pN=3" <http://cnx.org/content/m17632/latest/>
10"pN=4" <http://cnx.org/content/m17633/latest/>
11"pN=5" <http://cnx.org/content/m17634/latest/>
12"pN=7" <http://cnx.org/content/m17635/latest/>
13"pN=8" <http://cnx.org/content/m17636/latest/>
14"pN=9" <http://cnx.org/content/m17637/latest/>
15"N = 11 Winograd FFT module" <http://cnx.org/content/m17377/latest/> 16"N = 13 Winograd FFT module" <http://cnx.org/content/m17378/latest/> 17"N = 16 FFT module" <http://cnx.org/content/m17382/latest/> Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
300
APPENDIX
◆❂✶✼18
◆❂✶✾19
◆❂✷✺20
A technical report that describes the length 11, 13, 17, and 19 is
in {report 8105} and another technical report that describes a pro-
gram that will automatically generate a prime length FFT and its
flow graph si in {report xxx}.
18"N = 17 Winograd FFT module" <http://cnx.org/content/m17380/latest/> 19"N = 19 Winograd FFT module" <http://cnx.org/content/m17381/latest/> 20"N = 25 FFT module" <http://cnx.org/content/m17383/latest/> Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
Bibliography
[1] R. C. Agarwal and C. S. Burrus. Fast digital convolution us-
ing fermat transforms. In Proceedings of the IEEE 25th An-
nual Southwestern Conference, page 5388211;543, Hous-
ton, April 1973.
[2] R. C. Agarwal and C. S. Burrus. Fast convolution using
fermat number transforms with applications to digital filter-
ing. IEEE Transactions on Acoustics, Speech, and Signal
Processing, ASSP-22(2):87–97, April 1974. Reprinted in
Number Theory in DSP, by McClellan and Rader, Prentice-
Hall, 1979.
[3] R. C. Agarwal and C. S. Burrus.
Fast one-dimensional
digital convolution by multi-dimensional techniques. IEEE
Transactions on Acoustics, Speech, and Signal Processing,
ASSP-22(1):18211;10, February 1974. also in IEEE Press
DSP Reprints II, 1979; and Number Theory in DSP, by Mc-
Clellan and Rader, Prentice-Hall, 1979.
[4] R. C. Agarwal and C. S. Burrus. Number theoretic trans-
forms to implement fast digital convolution. Proceedings
of the IEEE, 63(4):5508211;560, April 1975. also in IEEE
Press DSP Reprints II, 1979.
[5] R. C. Agarwal and C. S. Burrus. Number theoretic trans-
forms to implement fast digital convolution. Proceedings
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
301
302
BIBLIOGRAPHY
of the IEEE, 63(4):5508211;560, April 1975. also in IEEE
Press DSP Reprints II, 1979.
[6] R. C. Agarwal and J. W. Cooley. New algorithms for digi-
tal convolution. IEEE Trans. on ASSP, 25(2):3928211;410,
October 1977.
[7] R. C. Agarwal and J. W. Cooley. New algorithms for digi-
tal convolution. IEEE Trans. on ASSP, 25(2):3928211;410,
October 1977.
[8] R. C. Agarwal and J. W. Cooley. New algorithms for digi-
tal convolution. IEEE Trans. on ASSP, 25(2):3928211;410,
October 1977.
[9] R. C. Agarwal and J. W. Cooley. New algorithms for digi-
tal convolution. IEEE Trans. on ASSP, 25(2):3928211;410,
October 1977.
[10] E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel,
J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling,
A. McKenney, and D. Sorensen. LAPACK Users’ Guide.
Society for Industrial and Applied Mathematics, Philadel-
phia, PA, 3rd edition, 1999.
[11] Jrg Arndt. Algorithms for Programmers: Ideas and Source
Code.
http://www.jjj.de/fxt/, Bayreuth, Germany, 2008.
FFT book available on-line, 1000 pages, continually up-
dated.
[12] L. Auslander, E. Feig, and S. Winograd.
Abelian semi-
simple algebras and algorithms for the discrete fourier trans-
form.
Advances in Applied Mathematics, 5:318211;55,
1984.
[13] S. Bagchi and S. Mitra.
The Nonuniform Discrete
Fourier Transform and Its Applications in Signal Process-
ing. Kluwer Academic, Boston, 1999.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
BIBLIOGRAPHY
303
[14] D. H. Bailey. Ffts in external or hierarchical memory. J.
Supercomputing, 4(1):238211;35, May 1990.
[15] C. W. Barnes. Roundoff8211;noise and overflow in normal
digital filters. IEEE Transactions on Circuit and Systems,
CAS-26:1548211;155, March 1979.
[16] C. W. Barnes and S. Shinnaka. Block shift invariance and
block implementation of discrete-time filters. IEEE Trans-
actions on Circuit and Systems, CAS-27(4):6678211;672,
August 1980.
[17] James K. Beard. An in-place, self-reordering fft. In Pro-
ceedings of the ICASSP-78, pages 632–633, Tulsa, April
1978.
[18] James K. Beard. The FFT in the 21st Century: Eigenspace
Processing. Kluwer, Boston, 2003.
[19] James K. Beard. The FFT in the 21st Century: Eigenspace
Processing. Kluwer, Boston, 2003.
[20] Laszlo A. Belady. A study of replacement algorithms for
virtual storage computers. IBM Systems Journal, 5(2):78–
101, 1966.
[21] G. D. Bergland. A fast fourier transform algorithm for real-
valued series. Comm. ACM, 11(10):703–710, October 1968.
[22] G. D. Bergland. A radix-8 fast fourier transform subroutine
for real-valued series. IEEE Trans. on Audio an Electro-
coustics, 17:138–144, June 1969.
[23] Th. Beth. Verfahren der Schnellen Fouriertransformation
[Fast Fourier Transform Methods]. Teubner, 1984.
[24] Guoan Bi and Yan Qiu Chen.
Fast dft algorithms for
length. IEEE Transactions on Circuits and Systems 8211;
II, 45(6):6858211;690, June 1998.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
304
BIBLIOGRAPHY
[25] R. E. Blahut. Fast Algorithms for Digital Signal Processing.
Addison-Wesley, Inc., Reading, MA, 1984.
[26] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[27] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[28] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[29] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[30] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[31] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[32] Richard E. Blahut. Fast Algorithms for Digital Signal Pro-
cessing. Addison-Wesley, Reading, Mass., 1985.
[33] Richard E. Blahut. Algebraic Methods for Signal Processing
and Communications Coding. Springer-Verlag, New York,
1992.
[34] L. I. Bluestein. A linear filtering approach to the computa-
tion of discrete fourier transform. IEEE Transactions on Au-
dio Electroacoustics, AU-18:4518211;455, December 1970.
[35] Leo I. Bluestein. A linear filtering approach to the computa-
tion of the discrete fourier transform. Northeast Electronics
Research and Eng. Meeting Record, 10:2188211;219, 1968.
[36] R. N. Bracewell. The Hartley Transform. Oxford Press,
1986.
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>
BIBLIOGRAPHY
305
[37] William L. Briggs and Van Emden Henson. The DFT: An
Owner’s Manual for the Discrete Fourier Transform. SIAM,
Philadelphia, 1995.
[38] E. Oran Brigham. The Fast Fourier Transform and Its Ap-
plications. Prentice-Hall, Englewood Cliffs, NJ, 1988. Ex-
pansion of the 1974 book.
[39] E. Oran Brigham. The Fast Fourier Transform and Its Ap-
plications. Prentice-Hall, Englewood Cliffs, NJ, 1988. Ex-
pansion of the 1974 book.
[40] V. Britanak and K. R. Rao.
The fast generalized dis-
crete fourier transforms: A unified approach to the dis-
crete sinusoidal transforms computation. Signal Processing,
79:1358211;150, 1999.
[41] G. Bruun. z-transform dft filters and ffts. IEEE Transactions
on ASSP, 26(1):568211;63, February 1978.
[42] O. Buneman.
Stable online creation of sines or cosines
of successive angles. Proc. IEEE, 75(10):14348211;1435,
1987.
[43] C. S. Burrus. Block implementation of digital filters. IEEE
Transactions on Circuit Theory, CT-18(6):6978211;701,
November 1971.
[44] C. S. Burrus.
Block realization of digital filters.
IEEE Transactions on Audio and Electroacoustics, AU-
20(4):2308211;235, October 1972.
[45] C. S. Burrus.
Digital filter structures described by dis-
tribut