Skip to main content
Engineering LibreTexts

4.2: Rader's Conversion of the DFT into Convolution

  • Page ID
    1980
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    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} \nonumber \]

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

    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} \nonumber \]

    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.

    n={1,...,N-1}n={1,...,N-1}" role="presentation" style="position:relative;" tabindex="0">


    This page titled 4.2: Rader's Conversion of the DFT into Convolution is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?