2
$\begingroup$

Let $y$ be the inverse (in the sense of convolution) of $x$, i.e.

$$x \star y = \delta$$

Context: $x[n]$ is a discrete signal defined for $n = 0,\ldots, N$. We can assume $x[n] = 0$ if $n \not\in [0,\ldots, N]$.

How to compute the inverse of $x$ (for the convolution)?


\begin{align}(x\star y)[0]&=x[0] y[0] = 1\implies y[0] = \frac{1}{x[0]}\\ (x\star y)[1]&=x[1] y[0] + x[0] y[1] = 0\implies y[1] = -\frac{x[1]}{x[0]^2}\\ (x\star y)[2]&=x[2] y[0] + x[1] y[1] + x[0] y[2] = 0\implies y[2] = -\frac{x[2]}{x[0]^2} + \frac{x[1]^2}{x[0]^3} \end{align}

I tried to find $y[3]$ manually, but I don't see a general formula appearing...

$\endgroup$
2
$\begingroup$

(I would post this as a comment, but I don't have enough rep)

If I understand your question correctly, the operation you want to do is called Deconvolution. Considering the more general problem $x \star y = z $, we can find a solution according to wikipedia as $ x = IFT(Z/Y) = IFT(FT(Z)/FT(Y))$, (where $FT$ is the Fourier Transform and $IFT=FT^{-1}$ the inverse FT).

| improve this answer | |
$\endgroup$
1
$\begingroup$

Consider a signal $x[n]$ of a finite length $N$. We are interested in a signal $y[n]$ where $$y[n]\star x[n]=\delta[n]\tag{1}$$ Assume $x[n]$ is the impulse response of an FIR filter and the transfer function is $X(z)$. The inverse filter is an IIR filter whose transfer function is $\frac{1}{X(z)}$. The impulse response of the inverse filter is $$y[n]=\mathcal{Z}^{-1}\left\{\frac{1}{X(z)}\right\}$$

The other way to see it: Convolution becomes product in the $z$-domain, where $\mathcal{Z}\left\{\delta[n]\right\}=1$.

It should be noted that depending on the zeros of $X(z)$ we can have different regions of convergence (ROC) for $\frac{1}{X(z)}$, and consequently different $y[n]$. This means that solutions of $(1)$ may not be unique.

Since the length of the $y[n]$ is theoretically infinite, for implementation you should use a truncated signal which results in an approximated $\delta$. You can use long-division algorithm to find $y$ with desired length.

| improve this answer | |
$\endgroup$
  • $\begingroup$ to do this practically, the OP will likely set $$ z=e^{j2\pi \tfrac{k}{N}} $$ and will have to worry a little about what to do in the occasion of $|X(z)|$ being too close to zero. $\endgroup$ – robert bristow-johnson Dec 29 '16 at 1:25
  • $\begingroup$ @robertbristow-johnson this would be interesting as an answer! $\endgroup$ – Basj Jan 2 '17 at 19:58
1
$\begingroup$

Since Convolution is a Linear Operation the easiest way to derive the coefficients is using a Matrix Representation of the problem.

Take the kernel $ y $ and build from it the Convolution Matrix.
Then write the vector representation of the Delta Funciton $ d $ and solve:

$$ Y x = d $$

In case the problem is solvable (Namely there is an inverse operator of $ Y $) you'll get you answer.
Of course you can always use Least Squares Solution.

Full code for building Convolution Matrix was given in Estimating a Signal Given a Noisy Measurement of the Signal and Its Derivative (Denoising) and Deconvolution of Synthetic 1D Signals - How To?

| improve this answer | |
$\endgroup$
  • $\begingroup$ Could you show an example? $\endgroup$ – David Aug 19 '18 at 16:28

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.