4.2: Rader's Conversion of the DFT into Convolution

[ "article:topic" ]

In this section a method quite different from the index mapping or polynomial evaluation is developed. Rather than dealing with the DFT directly, it is converted into a cyclic convolution which must then be carried out by some efficient means. Those means will be covered later, but here the conversion will be explained. This method requires use of some number theory.

Definition

The DFT and cyclic convolution are defined by

$C(k)=\sum_{n=0}^{N-1}x(n)W^{nk}$

$y(k)=\sum_{n=0}^{N-1}x(n)h(k-n)$

For both, the indices are evaluated modulo $$N$$. In order to convert the DFT in Equation 4.2.1 into the cyclic convolution of Equation 4.2.2, the $$nk$$ product must be changed to the $$k-n$$ difference. With real numbers, this can be done with logarithms, but it is more complicated when working in a finite set of integers modulo $$N$$. From number theory it can be shown that if the modulus is a prime number, a base (called a primitive root) exists such that a form of integer logarithm can be defined. This is stated in the following way. If $$N$$ is a prime number, a number r called a primitive roots exists such that the integer equation

$n=((r^{m}))_{N}$

creates a unique, one-to-one map of the $$N-1$$ member set $$m={0,...,N-2}$$ and the $$N-1$$ member set $$n={1,...,N-1}$$. This is because the multiplicative group of integers modulo a prime, $$p$$, is isomorphic to the additive group of integers modulo ($$p-1$$) and is illustrated for $$N=5$$ below.

is an array of values of $$r^m$$ modulo $$N$$ and it is easy to see that there are two primitive roots, 2 and 3, and Equation 4.2.3 defines a permutation of the integers n from the integers m (except for zero). The equation and a primitive root (usually chosen to be the smallest of those that exist) can be used to convert the DFT in the Equation 4.2.1 to the convolution in the Equation 4.2.2. Since the equation cannot give a zero, a new length-($$N-1$$) data sequence is defined from $$x(n)$$ by removing the term with index zero. Let

$n=r^{-m}$

and

$k=r^{s}$

where the term with the negative exponent (the inverse) is defined as the integer that satisfies

$((r^{-m}r^{m}))_{N}=1$

If $$N$$ is a prime number, $$r^{-m}$$ always exists. For example

$((2^{-1}))_{5}=3$

The Equation 4.2.1 now becomes

$C(r^{s})=\sum_{m=0}^{N-2}x(r^{-m})W^{r^{-m}r^{s}}+x(0)$

for $$s=0,1,...,N-2$$ and

$C(0)=\sum_{n=0}^{N-1}x(n)$

New functions are defined, which are simply a permutation in the order of the original functions, as

$x'(m)=x(r^{-m}),\; \; C'(s)=C(r^{s}),\; \; W'(n)=W(r^{n})$

The above equation then becomes

$C'(s)=\sum_{m=0}^{N-2}x'(m)W'(s-m)+x(0)$

which is cyclic convolution of length $$N-1$$ (plus $$x(0)$$ and is denoted as

$C'(k)=x'(k)\ast W'(k)+x(0)$

Applying this change of variables (use of logarithms) to the DFT can best be illustrated from the matrix formulation of the DFT. The equation is written for a length-5 DFT as:

$\begin{bmatrix} C(0)\\ C(1)\\ C(2)\\ C(3)\\ C(4) \end{bmatrix}=\begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 4\\ 0 & 2 & 4 & 1 & 3\\ 0 & 3 & 1 & 4 & 2\\ 0 & 4 & 3 & 2 & 1 \end{bmatrix}\begin{bmatrix} x(0)\\ x(1)\\ x(2)\\ x(3)\\ x(4) \end{bmatrix}$

where the square matrix should contain the terms of $$W^{nk}$$ but for clarity, only the exponents $$nk$$are shown. Separating the $$x(0)$$ term, applying the mapping of the equation and using the primitive roots $$r=2$$ $$r^{-1}=3$$gives

$\begin{bmatrix} C(1)\\ C(2)\\ C(3)\\ C(4) \end{bmatrix}=\begin{bmatrix} 1 & 3 & 4 & 2 \\ 2 & 1 & 3 & 4 \\ 4 & 2 & 1 & 3 \\ 3 & 4 & 2 & 1 \\ \end{bmatrix}\begin{bmatrix} x(1)\\ x(2)\\ x(3)\\ x(4) \end{bmatrix}+\begin{bmatrix} x(0)\\ x(0)\\ x(0)\\ x(0) \end{bmatrix}$

and

$C(0)=x(0)+x(1)+x(2)+x(3)+x(4)$

which can be seen to be a reordering of the structure in the above equation. This is in the form of cyclic convolution as indicated in the above equation. Rader first showed this in 1968, stating that a prime length-$$N$$ DFT could be converted into a length-($$N-1$$) cyclic convolution of a permutation of the data with a permutation of the W's. He also stated that a slightly more complicated version of the same idea would work for a DFT with a length equal to an odd prime to a power.

Until 1976, this conversion approach received little attention since it seemed to offer few advantages. It has specialized applications in calculating the DFT if the cyclic convolution is done by distributed arithmetic table look-up or by use of number theoretic transforms. It and the Goertzel algorithm, are efficient when only a few DFT values need to be calculated. It may also have advantages when used with pipelined or vector hardware designed for fast inner products. One example is the TMS320 signal processing microprocessor which is pipelined for inner products. The general use of this scheme emerged when new fast cyclic convolution algorithms were developed by Winograd.

Contributor

• ContribEEBurrus