To explain Rader's conversion of a prime pp point DFT
into a p1p1 point circular convolution [1] we
recall the definition of the DFT
y
(
k
)
=
∑
n
=
0
p

1
x
(
n
)
W
k
n
y
(
k
)
=
∑
n
=
0
p

1
x
(
n
)
W
k
n
(1)with
W
=
exp

j
2
π
/
p
W
=
exp

j
2
π
/
p
.
Also recall that a primitive root of
p
p
is an integer
r
r
such that
〈
r
m
〉
p
〈
r
m
〉
p
maps the integers
m
=
0
,
⋯
,
p

2
m
=
0
,
⋯
,
p

2
to the integers
1
,
⋯
,
p

1
1
,
⋯
,
p

1
.
Letting
n
=
r

m
n
=
r

m
and
k
=
r
l
k
=
r
l
,
where
r

m
r

m
is the
inverse of
r
m
r
m
modulo
p
p,
the DFT becomes
y
(
r
l
)
=
x
(
0
)
+
∑
m
=
0
p

2
x
(
r

m
)
W
r
l
r

m
y
(
r
l
)
=
x
(
0
)
+
∑
m
=
0
p

2
x
(
r

m
)
W
r
l
r

m
(2)for l=0,⋯,p2l=0,⋯,p2.
The `DC' term fis given by
y(0)=∑n=0p1x(n).y(0)=∑n=0p1x(n).
By defining new functions
x
′
(
m
)
=
x
(
r

m
)
,
y
′
(
m
)
=
y
(
r
m
)
,
W
′
(
m
)
=
W
r
m
x
′
(
m
)
=
x
(
r

m
)
,
y
′
(
m
)
=
y
(
r
m
)
,
W
′
(
m
)
=
W
r
m
(3)which are simply permuted versions of the original sequences,
the DFT becomes
y
′
(
l
)
=
x
(
0
)
+
∑
m
=
0
p

2
x
′
(
m
)
W
′
(
l

m
)
y
′
(
l
)
=
x
(
0
)
+
∑
m
=
0
p

2
x
′
(
m
)
W
′
(
l

m
)
(4)for l=0,⋯,p2l=0,⋯,p2.
This equation describes circular convolution and therefore
any circular convolution algorithm can be used to compute
a prime length DFT.
It is only necessary to
(i) permute the input, the roots of unity
and the output,
(ii) add x(0)x(0) to each term in Equation 4
and
(iii) compute the DC term.
To describe a bilinear form for the DFT we first define a
permutation matrix QQ for the permutation above.
If pp is a prime and rr is a primitive root of pp, then
let QrQr be the permutation matrix defined by
Q
e
〈
r
k
〉
p

1
=
e
k
Q
e
〈
r
k
〉
p

1
=
e
k
(5)for 0≤k≤p20≤k≤p2 where ekek is the kthkth standard basis vector.
Let the w˜w˜ be a p1p1 point vector of the roots of unity:
w
˜
=
(
W
1
,
⋯
,
W
p

1
)
t
.
w
˜
=
(
W
1
,
⋯
,
W
p

1
)
t
.
(6)If ss is the inverse of rr modulo pp (that is, rs=1rs=1 modulo pp)
and x˜=(x(1),⋯,x(p1))tx˜=(x(1),⋯,x(p1))t, then
the circular convolution of Equation 4 can be computed with the
bilinear form of (Reference):
Q
s
t
J
P
t
R
t
B
t
C
t
R

t
P
J
Q
s
w
˜
*
A
R
P
Q
r
x
˜
.
Q
s
t
J
P
t
R
t
B
t
C
t
R

t
P
J
Q
s
w
˜
*
A
R
P
Q
r
x
˜
.
(7)This bilinear form does not compute y(0)y(0), the DC term.
Furthermore, it is still necessary to add the x(0)x(0) term
to each of the elements of Equation 7 to
obtain y(1),⋯,y(p1)y(1),⋯,y(p1).