Skip to main content
Engineering LibreTexts

12.5: Number Theoretic Transforms for Convolution

  • Page ID
    2039
  • \( \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}}\)

    Here we look at the conditions placed on a general linear transform in order for it to support cyclic convolution. The form of a linear transformation of a length-N sequence of number is given by

    \[X(k)=\sum_{n=0}^{N-1}t(n,k)x(n) \nonumber \]

    for \(k=0,1,...,(N-1)\). The definition of cyclic convolution of two sequences is given by

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

    for \(n=0,1,...,(N-1)\) and all indices evaluated modulo \(N\). We would like to find the properties of the transformation such that it will support the cyclic convolution. This means that if \(X(k),\; H(k),\; Y(k)\) are the transforms of \(x(n),\; h(n),\; y(n)\) respectively,

    \[Y(k)=X(k)H(k) \nonumber \]

    The conditions are derived by taking the transform defined in the above equations of both sides of the equation which gives

    \[Y(k)=\sum_{n=0}^{N-1}t(n,k)\sum_{m=0}^{N-1}x(m)h(n-m) \nonumber \]

    \[Y(k)=\sum_{m=0}^{N-1}\sum_{n=0}^{N-1}x(m)h(n-m)t(n,k) \nonumber \]

    Making the change of index variables, \(l=n-m\) gives

    \[Y(k)=\sum_{m=0}^{N-1}\sum_{l=0}^{N-1}x(m)h(l)t(l+m,k) \nonumber \]

    But from the equation, this must be

    \[Y(k)=\sum_{n=0}^{N-1}x(n)t(n,k)\sum_{m=0}^{N-1}x(m)t(m,k) \nonumber \]

    \[Y(k)=\sum_{m=0}^{N-1}\sum_{l=0}^{N-1}x(m)h(l)t(n,k)t(l,k) \nonumber \]

    This must be true for all \(\(x(n),\; h(n)\) and \(k\), therefore from the above equations we have

    \[t(m+l,k)=t(m,k)t(l,k) \nonumber \]

    For \(l=0\) we have

    \[t(m,k)=t(m,k)t(0,k) \nonumber \]

    Therefore, \(t(0,k)=1\). For \(l=m\) we have

    \[t(2m,k)=t(m,k)t(m,k)=t^2(m,k) \nonumber \]

    For \(l=pm\) we likewise have

    \[t(pm,k)=t^p(m,k) \nonumber \]

    Therefore,

    \[t^N(m,k)=t(Nm,k)=t(0,k)=1 \nonumber \]

    But

    \[t(m,k)=t^m(1,k)=t^k(m,1) \nonumber \]

    Therefore,

    \[t(m,k)=t^{mk}(1,1) \nonumber \]

    Defining \(t(1,1)=\alpha\) gives the form for our general linear transform equation as

    \[X(k)=\sum_{n=0}^{N-1}\alpha ^{nk}x(n) \nonumber \]

    where \(\alpha\) is a root of order \(N\)NN" role="presentation" style="position:relative;" tabindex="0">


    This page titled 12.5: Number Theoretic Transforms for Convolution is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.

    • Was this article helpful?