2
$\begingroup$

I've read about the discrete convolution and how it applies to filters, but is convolution the only way to apply filters (to input signals)?

$\endgroup$
  • 1
    $\begingroup$ The answer is "kind of". Covolution in the time domain leads to FIR and IIR filters. There also is the multiplication in the frequency domain, but that equals convolution in the time domain: $$ x(t)*y(t) => X(f)\cdot Y(F) $$ In the end, everything can be traced back to one form of convolution or another. $\endgroup$ – Jan Krüger Jul 2 '16 at 9:44
  • $\begingroup$ @JanKrüger Is then for example the direct evaluation of direct forms also convolution? Such as what Matlab's filter() claims to do. $\endgroup$ – mavavilj Jul 2 '16 at 9:46
  • $\begingroup$ @mavavilj what else should it be? Have you read the mathematical expression that filter computes? It's a discrete convolution! $\endgroup$ – Marcus Müller Jul 2 '16 at 10:10
  • $\begingroup$ @mavavilj Yes, it is. Convolution is nothing else than a mathematical operation, constructed from an integral (which, in essence, is a sum), one signal (the filter kernel for example) turned around ($0..k => k..0$) and a multiplication. This is also what Matlabs filter() does. This is also what hardware filters do, no matter how they are arranges (one MAC cycling over the whole signal, FIR/IIR transversal, etc). $\endgroup$ – Jan Krüger Jul 2 '16 at 11:03
  • $\begingroup$ by the way, we're only considering digital, linear filters, right? because there are other types of filters, but they are kind of rarely used, and especially Matlab's filter has nothing to do with them. $\endgroup$ – Marcus Müller Jul 2 '16 at 11:04
4
$\begingroup$

For this discussion it's important to restrict the class of filters to linear time-invariant (LTI) filters. Their input-output relation is described by the standard convolution sum (or, in continuous-time, convolution integral) that you've probably come across. So the operation of any LTI system can be described by a convolution. In discrete time you have

$$y[n]=\sum_{k=-\infty}^{\infty}h[k]x[n-k]\tag{1}$$

where $x[n]$ is the input signal, $h[n]$ is the system's impulse response, and $y[n]$ is the output signal. An example where $(1)$ is implemented directly is the transversal filter, which has a finite impulse response (FIR).

However, this doesn't mean that an LTI system can only be implemented by directly implementing the convolution sum ($1$). Any infinite impulse response (IIR) must be implemented recursively, because the convolution sum $(1)$ can't be computed exactly in finite time (since it's an infinite sum). But mathematically, any recursive implementation of an IIR filter computes the same thing as the convolution sum.

The convolution sum can also be implemented in the frequency domain, where blocks of data are transformed using the DFT, these frequency domain data are modified according to the desired impulse response, and after applying an IDFT, the data blocks are combined to give the desired output signal. Two such methods are the overlap add and the overlap save methods.

In sum, all LTI systems are described by a convolution sum (or integral), but there are many ways to implement that sum, and more often than not, the convolution sum is not evaluated directly.

$\endgroup$
  • $\begingroup$ So is there something else than LTI systems, in digital filters? $\endgroup$ – mavavilj Jul 3 '16 at 10:16
  • $\begingroup$ @mavavilj: Sure, why not? $\endgroup$ – Matt L. Jul 3 '16 at 10:18
  • $\begingroup$ @mavavilj: E.g., adaptive filters, non-linear filters, etc. $\endgroup$ – Matt L. Jul 3 '16 at 10:22
  • $\begingroup$ So then the answer to my question should be "yes, but only for LTI systems"? $\endgroup$ – mavavilj Jul 3 '16 at 10:30
  • $\begingroup$ @mavavilj: Well, the problem is that your formulation "the only way to apply filters" is a bit unclear. Does "apply" mean implement? My answer should clarify all those details, please read it (again), and ask questions if necessary. Especially the last sentence of the answer should actually make things clear. $\endgroup$ – Matt L. Jul 3 '16 at 10:37
1
$\begingroup$

What is a filter anyway? In every-day life:

a device that is used to remove something unwanted from a (generally) fluid substance

In computer programming?

a program or section of code that is designed to examine each input or output request for certain qualifying criteria

In data processing, we are somehow inbetween. The fluid substance (signal) should be removed from something unwanted not satisfying some qualifying criteria (noise).

Depending on the criteria, you have many choices, depending on assmptions. For instance median, min-max filtering, all depending on certain qualifying criteria.

If you trust in filtering that does not depend on the actual time, and that is linear (the sum of two filtered signals is the filtering of the sum of two signals), you get "linear time_invariant filtering" (LTI). Then, one quickly understands this is strongly related to Fourier basis and convolution. Many other sources can provide you with insights:

Then, you can apply linear filters the convolutive way. But thanks to the above Fourier relation, you can apply them in the Fourier domain, using recursive filters, with lattice formulations, etc. All of them ultimately yield linear filters, but the different implementations vary in efficiency, complexity, economy, robusness to errors, etc.

$\endgroup$

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.