0.3 A bilinear form for the dft

A bilinear form for the dft

A bilinear form for a prime length DFT can be obtained by making minor changes to a bilinear form for circular convolution.This relies on Rader's observation that a prime $p$ point DFT can be computed by computing a $p-1$ point circular convolution and by performing some extra additions [link] . It turns out that when the Winograd or the split nestingconvolution algorithm is used, only two extra additions are required.After briefly reviewing Rader's conversion of a prime length DFT in to a circular convolution,we will discuss a bilinear form for the DFT.

Rader's permutation

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

with $W=exp-j2\pi /p$ . Also recall that a primitive root of $p$ is an integer $r$ such that $⟨r^m{⟩}_p$ maps the integers $m=0,\cdots ,p-2$ to the integers $1,\cdots ,p-1$ . Letting $n=r^{-m}$ and $k=r^l$ , where $r^{-m}$ is theinverse of $r^m$ modulo $p$ , the DFT becomes

for $l=0,\cdots ,p-2$ . The `DC' term fis given by $y\left(0\right)={\sum }_{n=0}^{p-1}x\left(n\right).$ By defining new functions

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

for $l=0,\cdots ,p-2$ . This equation describes circular convolution and thereforeany circular convolution algorithm can be used to compute a prime length DFT.It is only necessary to (i) permute the input, the roots of unityand the output, (ii) add $x\left(0\right)$ to each term in [link] and (iii) compute the DC term.

To describe a bilinear form for the DFT we first define a permutation matrix $Q$ for the permutation above. If $p$ is a prime and $r$ is a primitive root of $p$ , then let $Q_r$ be the permutation matrix defined by

for $0\le k\le p-2$ where $e_k$ is the $k^{th}$ standard basis vector. Let the $\tilde{w}$ be a $p-1$ point vector of the roots of unity:

If $s$ is the inverse of $r$ modulo $p$ (that is, $rs=1$ modulo $p$ ) and $\tilde{x}={(x\left(1\right),\cdots ,x(p-1))}^t$ , then the circular convolution of [link] can be computed with the bilinear form of [link] :

This bilinear form does not compute $y\left(0\right)$ , the DC term. Furthermore, it is still necessary to add the $x\left(0\right)$ term to each of the elements of [link] to obtain $y\left(1\right),\cdots ,y(p-1)$ .

Calculation of the dc term

The computation of $y\left(0\right)$ turns out to be very simple when the bilinear form [link] is used to compute the circular convolution in [link] . The first element of $ARP{Q}_r\tilde{x}$ in [link] is the residue modulo the polynomial $s-1$ , that is, the first element of this vector is the sum of the elements of $\tilde{x}$ . (The first row of the matrix, $R$ , representing the reduction operation is a row of 1's, and the matrices $P$ and $Q_r$ are permutation matrices.) Therefore, the DC term can be computed by adding the first element of $ARP{Q}_r\tilde{x}$ to $x\left(0\right)$ . Hence, when the Winograd or split nesting algorithm is used to perform thecircular convolution of [link] , the computation of the DC term requires only one extra complex addition for complex data.

The addition $x\left(0\right)$ to each of the elements of [link] also requires only one complex addition. By adding $x\left(0\right)$ to the first element of $\left\{C^t,R^{-t},P,J,Q_s,\tilde{w},*,A,R,P,Q_r,\tilde{x}\right\}$ in [link] and applying $Q_s^{t}J{P}^t{R}^t$ to the result, $x\left(0\right)$ is added to each element. (Again, this is because the first column of $R^t$ is a column of 1's, and the matrices $Q_s^t$ , $J$ and $P^t$ 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 [link] with $u=C^t{R}^{-t}PJ{Q}_s\tilde{w}$ .

Clearly, the structure highlighted in the dashed box can be replaced by the structure in [link] .

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={(W^0,\cdots ,W^{p-1})}^t$ , $x={(x\left(0\right),\cdots ,x(p-1))}^t$ , and where $U_p$ is the matrix with the form

and $V_p$ is the matrix with the form