The split-radix algorithm has the lowest
M+A
M
A
operations of any known power-of-two algorithm. Most
FFT experts believe it to be optimum in this respect.
Split-radix algorith muses part radix-2 decomposition and part
radix-4 decomposition.
Xk=∑
n
=0N2−1x2ne−(i2π×(2n)kN)+∑
n
=0N2−1x4n+1e−(i2π(4n+1)kN)+∑
n
=0N2−1x4n+3e−(i2π(4n+3)kN)=
DFT
N
2
x2n+
W
N
k
DFTx4n+1+
W
N
3
k
DFTx4n+3
X
k
n
N
2
1
0
x
2
n
2
2
n
k
N
n
N
2
1
0
x
4
n
1
2
4
n
1
k
N
n
N
2
1
0
x
4
n
3
2
4
n
3
k
N
DFT
N
2
x
2
n
W
N
k
DFT
x
4
n
1
W
N
3
k
DFT
x
4
n
3
(1)Table 1: Operation Counts
| Complex M/As |
Real M/As (4/2) |
Real M/As (3/3) |
|
ON3log
2
N
O
N
3
2
N
|
43Nlog
2
N−389N+6+29−1M
4
3
N
2
N
38
9
N
6
2
9
1
M
|
Nlog
2
N−3N+4
N
2
N
3
N
4
|
|
ONlog
2
N
O
N
2
N
|
83Nlog
2
N−169N+2+29−1M
8
3
N
2
N
16
9
N
2
2
9
1
M
|
3Nlog
2
N−3N+4
3
N
2
N
3
N
4
|
-
Split-radix algorithm has an irregular structure. Successful
progams have been written (Sorensen) for uni-processor machines,
but its not good for multi processors.
-
D. Braun's algorithm has split-radix counts
N−2
N
2
, has a regular structure, and is thus appealing
for multiprocessors or special-purpose hardware. (Contact me
if you ever need the references)
-
H.V. Sorensen, M.T. Heideman, and C.S. Burrus. (1986). On computing the split-radix FFT. ASSP, 34(1), 152-156.
-
P. Duhamel and H. Hollman. (1984, Jan 5). Split-radix FFT algorithms. Electronics Letters, 20, 14-16.
