I have the following problem: Let $x$, $y$ be finite real valued sequences defined on $0, \ldots, N-1$ and let $g$ be a non negative integer.


$$z_n=\sum_{k=0}^n x_{n-k}y_k, \quad \text{also on $0, \ldots, N-1$.}$$

Note that the sum is from $0$ to $n$, not $N-1$. In addition, the DFT of $y$ is known in closed form.

  • Is there a way to write $z$ as some cyclic convolution, so that with the help of the convolution theorem $z$ can be calculated in $N \log N$ instead of $N^2$?

I tried following the convolution theorem proof but I get stuck:

\begin{align} z_n&=\sum_{k=0}^nx_{n-k}y_k= \sum_{k=0}^{N-1}x_{n-k}\cdot \theta (n-k)\cdot y_k\\ \Rightarrow \tilde{z_q}&=\sum_{n=0}^{N-1}\sum_{k=0}^{N-1} x_{n-k}\cdot \theta (n-k)\cdot y_k e^{-2\pi iqn/N}\\ &=\sum_{n=0}^{N-1}\sum_{k=0}^{N-1} x_{n-k}\cdot \theta (n-k)e^{-2\pi iq(n-k)/N}\cdot y_k e^{-2\pi iqk/N}\\ &=\sum_{k=0}^{N-1} y_k e^{-2\pi iqk/N} \sum_{n=0}^{N-1} x_{n-k}\cdot \theta (n-k)e^{-2\pi iq(n-k)/N}\\ &=\sum_{k=0}^{N-1} y_k e^{-2\pi iqk/N} \sum_{n'=-k}^{N-1-k} x_{n'}\cdot \theta (n')e^{-2\pi iqn'/N}\\ &=\sum_{k=0}^{N-1} y_k e^{-2\pi iqk/N} \sum_{n'=0}^{N-1-k} x_{n'}e^{-2\pi iqn'/N}=?????\\ \end{align}

The problem is that the second sum depends on $k$ so the double sum doesn't factor to the product of DFTs.

What am I missing?

  • 1
    $\begingroup$ Do you know what is meant by linear convolution (as opposed to the cyclic convolution that the DFT supports)? Do you know how to embed a linear convolution inside a cyclic convolution, or have you heard of the notion of zero-padding? $\endgroup$ – Dilip Sarwate Apr 4 '14 at 20:11
  • 1
    $\begingroup$ What you are trying to do is a linear convolution of two causal sequences. So, it is addressed directly by application of the (circular) convolution theorem to linear convolution. See my answer below. $\endgroup$ – hops Apr 19 '17 at 18:40

You might be looking for the convolution property of the DFT. If $z[n] = x[n] * y[n]$, where $*$ represents circular convolution, then $Z[k] = X[k] Y[k]$, where $Z[k]$ is the DFT of $z[n]$ and so on.

This property is used in fast convolution techniques like overlap-save to implement convolution in $O(N \log N)$ time instead of the $O(n^2)$ time required by direct implementation of the convolution sum.

| improve this answer | |

Let's consider your equation carefully. It is given by $$z[n]=\sum_{k=0}^n x[n-k]y[k], \quad \text{for $n = 0, 1, \cdots, N-1$}$$ where $x[n]$ has $N$ samples indexed from $0$ to $N-1$ and $y[n]$ has $N$ samples with the same indexing. To help us see what we are after, let's write down a list of the outputs that you want to obtain expanded over $n$. $$\begin{array}{rcl} z[0] & = & x[0] y[0] \\ z[1] & = & x[1] y[0] + x[0] y[1] \\ z[2] & = & x[2] y[0] + x[1] y[1] + x[0] y[2] \\ & \vdots & \\ z[N-1] & = & \displaystyle\sum_{k=0}^{N-1} x[N-1-k] y[k] \end{array}$$ To compute these $N$ samples naively requires $1 + 2 + 3 + \cdots + N = \frac{N(N+1)}{2}$ multiplications and $1 + 2 + 3 + \cdots N - 1 = \frac{(N-1)N}{2}$ additions. So, naive computation is on the order of $N^2$ as claimed. We don't want to do this.

Now, let's consider a circular convolution (since this is where the convolution theorem of the DFT applies). Let's consider two sequences of length $2 N$ each. We will call them $x'[n]$ and $y'[n]$. The circular convolution of these sequences is denoted $z'[n]$ and may be expressed as $$ z'[n] = \sum_{k=0}^{N-1} x'[(n-k)_{2N}] y'[k], \quad \text{for $n = 0, 1, \cdots, 2 N-1$} $$ where now $x'[n]$ and $y'[n]$ each contain $2 N$ samples indexed from $0$ to $2 N - 1$ and the notation $(\cdot)_{2N}$ means the result is to be reduced modulo $2N$ to the range $0, 1, \cdots, 2N-1$. Now, let's write down a list of the first $N$ outputs that we would obtain from this operation.

$$\begin{array}{rcl} z'[0] & = & x'[0] y'[0] + \displaystyle\sum_{k=1}^{2 N - 1} x'[(-k)_{2N}] y'[k]\\ z'[1] & = & x'[1] y'[0] + x'[0] y'[1] + \displaystyle\sum_{k=2}^{2 N - 1} x'[(1-k)_{2N}] y'[k]\\ z'[2] & = & x'[2] y'[0] + x'[1] y'[1] + x'[0] y'[2] + \displaystyle\sum_{k=3}^{2 N - 1} x'[(2-k)_{2N}] y'[k]\\ & \vdots & \\ z'[N-1] & = & \displaystyle\sum_{k=0}^{N-1} x'[n-k] y'[k] + \displaystyle\sum_{k=N}^{2 N - 1} x'[(N-1-k)_{2N}] y'[k] \end{array}$$ Notice the similarity of this with our previous list. If the first $N$ elements of the primed sequences matched the first $N$ elements of the unprimed sequences, then these results are the desired quantity plus some extra terms we don't want (represented by the additional summation). If only there were some way we could force that additional summation to be zero... Well you probably see where I am going with this. We can force those terms to zero. If we define our input signals as $$ x'[n] = \left\{\begin{array}{lr} x[n] & 0 \leq n < N \\ 0 & N \leq n < 2 N \end{array}\right.$$ and $$ y'[n] = \left\{\begin{array}{lr} y[n] & 0 \leq n < N \\ 0 & N \leq n < 2 N \end{array}\right.$$ or in other words zero pad $x[n]$ and $y[n]$ to fit into $x'[n]$ and $y'[n]$, then the summations drop off and we obtain the desired result.

In other words, we have resolved your issue, and it turns out that we used the standard textbook convolution theorem to do it. No need to derive anything else.

The process is as follows:

  1. Zero pad $x[n]$ and $y[n]$ to length $2N$.
  2. Compute the $2N$-DFT of these zero-padded sequences.
  3. Perform the $2N$ multiplications.
  4. Compute the $2N$-IDFT of the resulting product.
  5. The output you desire is the first $N$ terms.

This is described well in many introductory DSP textbooks, although it is cast as a framework for converting circular convolution to (the generally preferred) linear convolution. As you can see, this is exactly what you are after just not formulated the same way. For more information, I know that the book Digital Signal Processing by John G. Proakis and Dimitris K. Manolakis has a good treatment of this procedure (look for overlap-add and overlap-save algorithms).

| improve this answer | |

There is simpler way to get from your circular convolution to DFT terms.

  • Start of with your first equation summed from $p=0$ to $N-1$.
  • Now multiply both sides of equation by $e^{-2\pi j \cdot k n/N}$.
  • Then sum both sides from $n =0$ to $N-1$.
  • Use the DFT property $x(n-p) \Leftrightarrow e^{-2\pi i \cdot p k/N}\cdot X(k)$.
  • Replace the $x(n-p)$ with $x(n)*e^{-2\pi j \cdot pk/N}$.
  • Rearrange terms to get $Z(k) = X(k)\cdot Y(k)$.
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.