# Deconvolution by Convolution

This is now a second time I am attempting to ask this very important but simple question here. What I want to know is can you do deconvolution by convolving a signal. It is often stated that, for example by cutting and boosting the same frequency on an equalizer the result is the original signal. Is that the case? Can convolution be removed by convolving? That would certainly brake the identity that the convolved signal must be n+m-1 in length. I tried this with an equalizer and the results seem to be close to perfect, just some quantization distortion.

If the above can be done, I can not arrive at this conclusion. For example If I convolve (1) with (1, 1) the result is (1, 1). I can not find any impulse response that if convolved with (1, 1) would result in (1).

So what is the truth here?

Since convolution describes the operation of a linear time-invariant (LTI) system, the question is if the effect of an LTI system can be compensated by another LTI system. In the discrete-time domain you can use the $\mathcal{Z}$-transform to analyze LTI systems. If a signal $x(n)$ (with $\mathcal{Z}$-transform $X(z)$) is filtered by a system with impulse response $h(n)$ (with $\mathcal{Z}$-transform $H(z)$), then the $\mathcal{Z}$-transform of the resulting output signal $y(n)$ is given by

$$Y(z)=X(z)H(z)$$

Recovering $X(z)$ from $Y(z)$ can theoretically be done by

$$X(z)=\frac{Y(z)}{H(z)}$$

except at points $z$ where $H(z)=0$. The above equation corresponds to convolution with an impulse response $g(n)$ with $\mathcal{Z}$-transform

$$G(z)=\frac{1}{H(z)}\tag{1}$$

The question is if this system can be realized by a causal and stable filter. This is indeed the case if $H(z)$ is a minimum-phase system. Assuming rational transfer functions (which we always get when discrete-time systems consist of adders, multipliers, and delay elements), this means that $H(z)$ is a causal and stable system with all its zeros inside the unit circle of the complex plane (its poles are of course also inside the unit circle because of stability). Due the inversion in (1), the zeros of $H(z)$ are the poles of $G(z)$ and vice versa, i.e. if the zeros of $H(z)$ are inside the unit circle, then $G(z)$ is stable. One more thing that can be seen from (1) is that if $H(z)$ is an FIR system, then $G(z)$ is IIR. Nevertheless, in practice equalization if often done by FIR filters, which approximate the inverse filter in some optimal sense.

Let's look at a simple example. Assume an FIR system

$$h(n)=\delta(n)-a\delta(n-1),\quad |a|<1$$

Then we have

$$H(z)=1-az^{-1}$$

$H(z)$ is a minimum-phase system because it has one pole at $z=0$ and a zero at $z=a$, which is inside the unit circle if $|a|<1$. The inverse system is given by

$$G(z)=\frac{1}{1-az^{-1}}=\sum_{n=0}^{\infty}a^nz^{-n}$$

the impulse response of which is

$$g(n)=a^n,\quad n\ge 0$$

which is of course IIR.

So in this case the convolution

$$y(n)=(x*h)(n)=x(n)-ax(n-1)$$

can be perfectly compensated for by the convolution

$$x(n)=(y*g)(n)=\sum_{k=0}^{\infty}g(k)y(n-k)=\sum_{k=0}^{\infty}a^ky(n-k)$$

Note that exact deconvolution of a minimum-phase FIR system can only be achieved by an IIR system. The only systems that can be inverted (exactly) by FIR systems are all-pole IIR systems, i.e. systems with all their zeros at the origin of the complex plane (like $g(n)$ in the example above). Note however that in practice exact compensation is usually not the goal. E.g., in digital communications, almost all (linear) equalizers are implemented by transversal (FIR) filters, because they can be adapted more easily and because they are always stable.

• @Matt L. With "FIR filters are unable deconvolve" I meant that FIR is unable deconvolve it's own FIR impulses. It seems like IIR filters are able to produce responses that settle to 0(audio) quickly and deconvolve their own impulses. By the way, in circular convolution it seems FIR can be deconvolved by FIR, as long as multiplication/division by 0 does not take place in the non0 frequency domain. That would also indicate that by aliasing the time domain FIR can be deconvolved by FIR. True? DC offset only proof: (1,1)*(1,1)=(2, 2); (2, 2)*(0.25, 0.25)=(1,1), where * = Circular Conv. – Tony Jun 5 '14 at 16:47
• @MattL. Here is a better proof with a DC offset and a sin component in both functions. The first term is linear convolution to show that the circular convolution can deconvolve linear FIR convolution with a finite impulse: (1, 0) * (2, 1) = (2, 1); (2,1) circular (0.66,-0.33) = (1, 0). 0.66 and -.0.33 are rounded. However, this does not work in the (1,1) * (1.0) "diracDC" case, which makes sense since we are multiplying a filled frequency bin by 0. I don't yet fully grasp why this kind of function can be deconvolved in any form. – Tony Jun 5 '14 at 18:00
• @Tony: Circular deconvolution is a different matter. With circular (de)convolution it does not make sense to make the distinction FIR vs. IIR because by definition all involved sequences are of length $N$. So if (circular) deconvolution is possible, it is naturally always possible by a finite length sequence. And it is possible if the DFT of the impulse response does not introduce any zeros in the DFT of the original sequence. – Matt L. Jun 7 '14 at 11:48
• @Tony: If the two sinc functions have the same zero crossings, convolution changes nothing. This is of course much easier to see in the frequency domain than in the time domain. – Matt L. Jun 8 '14 at 7:37
• @Tony: Linear convolution IS multiplication in the frequency domain. Of course not of the DFTs but the the DTFTs. A sinc function extends infinitely, so I'm not sure what you mean by 'zero padding' in this context. And two sincs convolved with each other cannot get any steeper because each of them is already in ideal lowpass filter. – Matt L. Jun 8 '14 at 20:50

What you want is $$x(t) = (x(t)\otimes h(t))\otimes h'(t)$$ where $\otimes$ denotes convolution. Taking $Z$ transform, $$X(z) = X(z) \times H(z) \times H'(z)$$ or $$H'(z) = \frac{1}{H(z)} \tag{1}$$

So you can deconvolve a convolution sum if you you have inverse transfer function as expressed in (1).

For causal and stable system, the ROC of $H'(z)$ must extend to infinity and ROC should contain the unit circle.

Another approach (Though the same).

Let's assume we're in Finite Dimension Space and the convolution operator is the Circular Convolution (Namely, the same we would do using the DFT).

Then $y = h \ast x$ can be written as:

$$y = H x$$

Where $H$ is a circulant matrix.
Now, the Deconvolution Operator is basically the Inverse of $H$.
Yet, since $H$ is a circulant matrix it can be diagonalized by the DFT Matrix:

$$H = {D}^{T} \mathcal{{H}_{f}} D \Rightarrow {H}^{-1} = {D}^{T} \mathcal{{H}_{f}}^{-1} D$$

Where $\mathcal{{H}_{f}}$ is a diagonal matrix (Baiscally the DFT of the $h$ filter).
The above implies ${H}^{-1}$ is also a circulant matrix and since:

$$x = {H}^{-1} y$$

The operation can be carried out as a convolution.

Pay attention, we assumed the there are no vanishing elements in the diagonal matrix (Otherwise it can be inverted).
This is a valid assumption to any deconvolution problem.
In any case information it lost (Vanished) there is no way to return it using direct convolution (Some priors might do, but this is not what the question is all about).

If you deconvolve the output signal with the system response, then you will obtain the (almost) input signal.

(sig_noisy = sig_clean * h + noise)

Alternatively, if you don't know the h function, but know the input and output, this time why not deconvolve the input signal with the output which will give the h^-1 function. Then you can use it as a filter to filter the noisy signal.

(sig_clean = sig_noisy * h^-1)

So, it is possible. I believe I have answered it in more detail in other related question.