# Convolution and DFT size

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}

• Are you writing $x(n)$ as $y(m)$? – Gilles Aug 3 '16 at 13:51
• @Gilles Sorry lapsus calami, I will correct it – Cali Aug 3 '16 at 14:00
• 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? – Matt L. Aug 3 '16 at 19:14
• @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. – 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]$.
• 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. – Cali Aug 4 '16 at 10:35 • @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. – Gilles Aug 4 '16 at 12:39 • @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. – Matt L. Aug 4 '16 at 19:22 • @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. – Matt L. Aug 4 '16 at 19:26 • @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} – Gilles Aug 6 '16 at 15:09 Taking theN$-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}