0
$\begingroup$

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}

$\endgroup$
4
  • 1
    $\begingroup$ Are you writing $x(n)$ as $y(m)$? $\endgroup$
    – Gilles
    Aug 3, 2016 at 13:51
  • $\begingroup$ @Gilles Sorry lapsus calami, I will correct it $\endgroup$
    – Cali
    Aug 3, 2016 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, 2016 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, 2016 at 20:46

2 Answers 2

2
$\begingroup$

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

$\endgroup$
7
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 15:09
1
$\begingroup$

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}

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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