To explain Rader's conversion of a prime pp point DFT into a p-1p-1 point circular convolution [1] we recall the definition of the DFT

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

for l=0,⋯,p-2l=0,⋯,p-2. The `DC' term fis given by y(0)=∑n=0p-1x(n).y(0)=∑n=0p-1x(n). By defining new functions

which are simply permuted versions of the original sequences, the DFT becomes

for l=0,⋯,p-2l=0,⋯,p-2. 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

for 0≤k≤p-20≤k≤p-2 where ekek is the kthkth standard basis vector. Let the w˜w˜ be a p-1p-1 point vector of the roots of unity:

If ss is the inverse of rr modulo pp (that is, rs=1rs=1 modulo pp) and x˜=(x(1),⋯,x(p-1))tx˜=(x(1),⋯,x(p-1))t, then the circular convolution of Equation 4 can be computed with the bilinear form of (Reference):

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(p-1)y(1),⋯,y(p-1).

The computation of y(0)y(0) turns out to be very simple when the bilinear form Equation 7 is used to compute the circular convolution in Equation 4. The first element of ARPQrx˜ARPQrx˜ in Equation 7 is the residue modulo the polynomial s-1s-1, that is, the first element of this vector is the sum of the elements of x˜x˜. (The first row of the matrix, RR, representing the reduction operation is a row of 1's, and the matrices PP and QrQr are permutation matrices.) Therefore, the DC term can be computed by adding the first element of ARPQrx˜ARPQrx˜ to x(0)x(0). Hence, when the Winograd or split nesting algorithm is used to perform the circular convolution of Equation 7, the computation of the DC term requires only one extra complex addition for complex data.

The addition x(0)x(0) to each of the elements of Equation 7 also requires only one complex addition. By adding x(0)x(0) to the first element of CtR-tPJQsw˜*ARPQrx˜CtR-tPJQsw˜*ARPQrx˜ in Equation 7 and applying QstJPtRtQstJPtRt to the result, x(0)x(0) is added to each element. (Again, this is because the first column of RtRt is a column of 1's, and the matrices QstQst, JJ and PtPt are permutation matrices.)

Although the DFT can be computed by making these two extra additions, this organization of additions does not yield a bilinear form. However, by making a minor modification, a bilinear form can be retrieved. The method described above can be illustrated in Figure 1 with u=CtR-tPJQsw˜u=CtR-tPJQsw˜.

Figure 1: The flow graph for the computation of the DFT.

Clearly, the structure highlighted in the dashed box can be replaced by the structure in Figure 2.

Figure 2: The flow graph for the bilinear form.

By substituting the second structure for the first, a bilinear form is obtained. The resulting bilinear form for a prime length DFT is

where w=(W0,⋯,Wp-1)tw=(W0,⋯,Wp-1)t, x=(x(0),⋯,x(p-1))tx=(x(0),⋯,x(p-1))t, and where UpUp is the matrix with the form

and VpVp is the matrix with the form