n=
K
1
n
1
+
K
2
n
2
modN
n
K
1
n
1
K
2
n
2
N
n=
K
3
k
1
+
K
4
k
2
modN
n
K
3
k
1
K
4
k
2
N
n
1
=01…
N
1
−1
n
1
0
1
…
N
1
1
k
1
=01…
N
1
−1
k
1
0
1
…
N
1
1
n
2
=01…
N
2
−1
n
2
0
1
…
N
2
1
k
2
=01…
N
2
−1
k
2
0
1
…
N
2
1
The basic ideas is to simply reorder the
DFT computation to expose the redundancies in the DFT, and
exploit these to reduce computation!
Three conditions must be satisfied to make this map serve our purposes
- Each map must be one-to-one from
00 to
N−1
N
1
, because we want to do the
same computation, just in a different
order.
- The map must be cleverly chosen so that computation is
reduced
- The map should be chosen to make the short-length
transforms be DFTs. (Not essential, since fast algorithms for
short-length DFT-like computations could be developed, but it
makes our work easier.)
N
1
N
1
,
N
2
N
2
relatively prime (greatest common denominator
=1
1
) i.e.
gcd
N
1
N
2
=1
N
1
N
2
1
K
1
=a
N
2
K
1
a
N
2
and/or
K
2
=b
N
1
K
2
b
N
1
and
gcd
K
1
N
1
=1
K
1
N
1
1
,
gcd
K
2
N
2
=1
K
2
N
2
1
N
1
N
1
,
N
2
N
2
not relatively prime:
gcd
N
1
N
2
>1
N
1
N
2
1
K
1
=a
N
2
K
1
a
N
2
and
K
2
≠b
N
1
K
2
b
N
1
and
gcda
N
1
=1
a
N
1
1
,
gcd
K
2
N
2
=1
K
2
N
2
1
or
K
1
≠a
N
2
K
1
a
N
2
and
K
2
=b
N
1
K
2
b
N
1
and
gcd
K
1
N
1
=1
K
1
N
1
1
,
gcdb
N
2
=1
b
N
2
1
where
K
1
K
1
,
K
2
K
2
,
K
3
K
3
,
K
4
K
4
,
N
1
N
1
,
N
2
N
2
,
a
a,
b
b integers
Requires number-theory/abstract-algebra concepts. Reference:
C.S. Burrus
Conditions of one-to-oneness must apply to both
kk and
nn
X
k
1
k
2
=∑
n
1
=0
N
1
−1∑
n
2
=0
N
2
−1x
n
1
n
2
W
N
(
K
1
n
1
+
K
2
n
2
)
(
K
3
k
1
+
K
4
k
2
=∑
n
1
=0
N
1
−1∑
n
2
=0
N
2
−1x
n
1
n
2
W
N
K
1
K
3
n
1
k
1
W
N
K
1
K
4
n
1
k
2
W
N
K
2
K
3
n
2
k
1
W
N
K
2
K
4
n
2
k
2
X
k
1
k
2
n
1
N
1
1
0
n
2
N
2
1
0
x
n
1
n
2
W
N
(
K
1
n
1
+
K
2
n
2
)
(
K
3
k
1
+
K
4
k
2
n
1
N
1
1
0
n
2
N
2
1
0
x
n
1
n
2
W
N
K
1
K
3
n
1
k
1
W
N
K
1
K
4
n
1
k
2
W
N
K
2
K
3
n
2
k
1
W
N
K
2
K
4
n
2
k
2
(1)
-
K
1
K
4
modN=0
K
1
K
4
N
0
exclusive or
K
2
K
3
modN=0
K
2
K
3
N
0
⇒ Common Factor Algorithm (CFA). Then
Xk=
DFT
N
i
twiddle factors
DFT
N
j
x
n
1
n
2
X
k
DFT
N
i
twiddle factors
DFT
N
j
x
n
1
n
2
-
K
1
K
4
modN
K
1
K
4
N
and
K
2
K
3
modN=0
K
2
K
3
N
0
⇒ Prime Factor Algorithm (PFA).
Xk=
DFT
N
i
DFT
N
j
X
k
DFT
N
i
DFT
N
j
No twiddle factors!
A PFA exists only and always for relatively prime
N
1
N
1
,
N
2
N
2
K
1
K
3
modN=
N
2
K
1
K
3
N
N
2
and
K
2
K
4
modN=
N
1
K
2
K
4
N
N
1
Convenient choice giving a PFA
K
1
=
N
2
K
1
N
2
,
K
2
=
N
1
K
2
N
1
,
K
3
=
N
2
N
2
-1mod
N
1
mod
N
1
K
3
N
2
N
2
1
N
1
N
1
,
K
4
=
N
1
N
1
-1mod
N
2
mod
N
2
K
4
N
1
N
1
1
N
2
N
2
where
N
1
-1mod
N
2
N
1
1
N
2
is an integer such that
N
1
N
1
-1mod=1
N
1
N
1
1
1
N
1
=3
N
1
3
,
N
2
=5
N
2
5
N=15
N
15
n=5
n
1
+3
n
2
mod15
n
5
n
1
3
n
2
15
k=10
k
1
+6
k
2
mod15
k
10
k
1
6
k
2
15
-
Checking Conditions for one-to-oneness:
5=
K
1
=a
N
2
=5a
5
K
1
a
N
2
5
a
3=
K
2
=b
N
1
=3b
3
K
2
b
N
1
3
b
gcd53=1
5
3
1
gcd35=1
3
5
1
10=
K
3
=a
N
2
=5a
10
K
3
a
N
2
5
a
6=
K
4
=b
N
1
=3b
6
K
4
b
N
1
3
b
gcd103=1
10
3
1
gcd65=1
6
5
1
-
Checking conditions for reduced computation:
K
1
K
4
mod15=5×6mod15=0
K
1
K
4
15
5
6
15
0
K
2
K
3
mod15=3×10mod15=0
K
2
K
3
15
3
10
15
0
-
Checking Conditions for making the short-length
transforms be DFTS:
K
1
K
3
mod15=5×10mod15=5=
N
2
K
1
K
3
15
5
10
15
5
N
2
K
2
K
4
mod15=3×6mod15=3=
N
1
K
2
K
4
15
3
6
15
3
N
1
Therefore, this is a prime factor map.
-
N
2
N
2
length-
N
1
N
1
DFTs
+
N
1
N
1
length-
N
2
N
2
DFTs
N
2
N
1
2+
N
1
N
2
2=N
N
1
+
N
2
N
2
N
1
2
N
1
N
2
2
N
N
1
N
2
complex multiplies
-
Suppose
N=
N
1
N
2
N
3
…
N
M
N
N
1
N
2
N
3
…
N
M
N
N
1
+
N
2
+…+
N
M
N
N
1
N
2
…
N
M
Complex multiplies
radix-2,
radix-4 eliminate all multiplies in short-length
DFTs, but have twiddle factors: PFA eliminates all twiddle
factors, but ends up with multiplies in short-length
DFTs.
Surprisingly, total operation counts end up being very similar
for similar lengths.
-
C.S. Burrus. (1977, June). Index Mappings for Multidimensional Formulation of the DFT and Convolution. ASSP, 25, 239-242.