0

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}

Cali
  • 181
  • 2
  • 12
  • 1
    Are you writing $x(n)$ as $y(m)$? – Gilles Aug 03 '16 at 13:51
  • @Gilles Sorry lapsus calami, I will correct it – Cali Aug 03 '16 at 14:00
  • 1
    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 03 '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 03 '16 at 20:46

2 Answers2

2

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]$.

Matt L.
  • 89,963
  • 9
  • 79
  • 179
  • 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 04 '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 04 '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 04 '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 04 '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 06 '16 at 15:09
  • @Gilles: Since $x[n]$ and $h[n]$ are both zero outside the interval $n\in [0,2N-1]$, both equations are indeed equivalent. This is the case because the OP only seems to care about the first $N$ samples of $y[n]$, and they can be computed from Eq. $(1)$ in my answer (note the upper summation index). So the $\neq$ in your comment should actually be a $=$. – Matt L. Aug 06 '16 at 16:54
  • Ah now I see, causality with that upper limit in $\displaystyle\sum_{m=0}^n$ makes all this clear now. And the $N$-point DFT end results are the same indeed. Thanks @MattL. ! – Gilles Aug 06 '16 at 17:19
1

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}

Gilles
  • 3,386
  • 3
  • 21
  • 28