Assuming that filtered signal $y(n)$ is given as

$$ y(n)=x(n)\star h(n)=\sum_{m=0}^{2N-1}x(m)h(n-m), \quad n \in[0,1,\ldots, 2N] $$

where $\star$ is convolution parameter. $x(n)$ is discrete signal of lenght $2N$ and $h(n)$ is filter of the same lenght as $x(n)$. If I want to take for example $N$-point FFT of $y(n)$ how it would look like

\begin{align} DFT_{N}(y(n))=\sum_{n=0}^{N-1}(x(n)\star h(n))&e^{-j\frac{2\pi nk}{N}}=\sum_{n=0}^{N-1}\sum_{m=0}^{\mathbf{2N-1}}(x(m)h(n-m))e^{-j\frac{2\pi nk}{N}}\\ &\textrm{or}\\ DFT_{N}(y(n))=\sum_{n=0}^{N-1}(x(n)\star h(n))&e^{-j\frac{2\pi nk}{N}}=\sum_{n=0}^{N-1}\sum_{m=0}^{\mathbf{N-1}}(x(m)h(n-m))e^{-j\frac{2\pi nk}{N}}\quad ? \end{align}

  • 1
    $\begingroup$ Are you writing $x(n)$ as $y(m)$? $\endgroup$ – Gilles Aug 3 '16 at 13:51
  • $\begingroup$ @Gilles Sorry lapsus calami, I will correct it $\endgroup$ – Cali Aug 3 '16 at 14:00
  • 1
    $\begingroup$ You'll have to explain why your first sum goes from $0$ to $2N-1$. What are the lengths of $x[n]$ and $h[n]$? Are they both causal? $\endgroup$ – Matt L. Aug 3 '16 at 19:14
  • $\begingroup$ @MattL. I have edite the question.shortly: I am filtering 2N lenght signal (convoluition in time domain) and then taking N point DFT of the filtered signal. $\endgroup$ – Cali Aug 3 '16 at 20:46

Note that if $x[n]$ and $y[n]$ are non-zero in the interval $n\in [0,2N-1]$ (and, for convenience, they are defined as being zero outside that interval), the (linear) convolution sum can be written as

$$y[n]=(x\star h)[n]=\sum_{m=0}^nx[m]h[n-m],\qquad 0\le n<4N-1\tag{1}$$

Note that the upper limit is $n$ because the argument of the term $h[n-m]$ becomes negative for $m>n$.

So if, for whatever reason, you're only interested in $y[n]$ in the interval $n\in [0,N-1]$, you can set the upper limit in the convolution sum $(1)$ to $N-1$ (assuming that $x[n]$ and $h[n]$ are defined as zero outside the interval $n\in [0,2N-1]$). However, the result wouldn't change if you chose the upper summation interval as $2N-1$, because you would just add zeros to the result.

In short, both formulas in your question give the same result, under the given assumptions on the definitions of $x[n]$ and $y[n]$.

  • $\begingroup$ Thank you for your answer. This helps a lot! Just to clarify your answer once more- summation over $m$ can be changed in accordance with summation over $n$ because $h[n-m]$=0 for $m>n$? Under assumption that $x[n]$ and &h[n]$ are zero outside defined interval. $\endgroup$ – Cali Aug 4 '16 at 10:35
  • $\begingroup$ @Matt. L., I think in the second formula, one fails to see that you have to get all the $y(n)$'s first (which involves convolving with $m$ going up to $2N-1$ for some terms. $\endgroup$ – Gilles Aug 4 '16 at 12:39
  • $\begingroup$ @Cali: It's not a summation over $n$; $m$ is the summation index, and the upper limit is $n$. So for each $y[n]$ the sum involves a different number of elements. $\endgroup$ – Matt L. Aug 4 '16 at 19:22
  • $\begingroup$ @Gilles: Not sure what you mean by "get all the y(n)'s first". The formula is only about computing $y[n]$, nothing else. For each index $n$, the upper limit of the sum is the current $n$ (or, if $n\ge 2N$, it can be replaced by $2N-1$). So for each $y[n]$ the number of (non-zero) elements in the sum is different. E.g., for the computation of $y[0]$ you just have $1$ element in the sum, for $y[1]$ you have two, etc. $\endgroup$ – Matt L. Aug 4 '16 at 19:26
  • $\begingroup$ @MattL. , I mean from the OP's $y(n)$ definition $$ y(n)=x(n)\star h(n)=\sum_{m=0}^{2N-1}x(m)h(n-m), \quad n \in[0,1,\ldots, 2N], $$ the equality from RHS gives the LHS ($\textrm{DFT}_{N}\left\{y(n)\right\}$) only for the first equation as \begin{align} \sum_{n=0}^{N-1}\left(\sum_{m=0}^{2N-1}x(m)h(n-m)\right)e^{-j\frac{2\pi nk}{N}} &=\sum_{n=0}^{N-1}y(n)e^{-j\frac{2\pi nk}{N}}\\ \textrm{while}\\ \sum_{n=0}^{N-1}\left(\sum_{m=0}^{N-1}x(m)h(n-m)\right)e^{-j\frac{2\pi nk}{N}} &\neq\sum_{n=0}^{N-1}y(n)e^{-j\frac{2\pi nk}{N}} \end{align} $\endgroup$ – Gilles Aug 6 '16 at 15:09

Taking the $N$-point FFT of $y(n)$, strictly speaking you should get the first equation as in your DFT the $n$ goes from $0$ to $N-1$, and in your signal from convolution $y(n)$, $n$ and $m$ go from $0$ to $2N-1$. Notice that here you're taking less points in your DFT than you have your signal $y(n)$, you'll have a bad visual resolution.

Using the DFT definition and the defined $y(n)$, \begin{align} \textrm{DFT}_{N}\left\{y(n)\right\}&=\sum_{n=0}^{N-1}y(n)e^{-j\frac{2\pi nk}{N}}\\ &=\sum_{n=0}^{N-1}\underbrace{(x(n)\star h(n))}_{y(n)}e^{-j\frac{2\pi nk}{N}}\\ &=\sum_{n=0}^{N-1}\underbrace{\left(\sum_{m=0}^{2N-1}x(m)h(n-m)\right)}_{y(n)}e^{-j\frac{2\pi nk}{N}}\\ \end{align}


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.