So I just started reading on FIR and IIR filters and am amazed by how "simple" the theory seems, so far.
But what confuses me is, why does filtering work by creating a weighted sum of previous samples?
What intuition makes one think this can produce desired filtering effects?
Consider a discrete-time input signal of the form: $$ x[n] = \cos(\omega_0 n) ~~~,~~~-\infty < n < \infty, ~~~~~ n\in \mathcal{Z}$$
where the radian frequency $\omega_0$ is set between 0 and $\pi$ radians per sample.
Now, consider two basic discrete-time (digital) filters which are defined through addition and subtraction of their input $x[n]$ for producing their outputs $y_1[n]$ and $y_2[n]$ as: $$y_1[n] = (x[n]+x[n-1])/2 ~~~,~~~ \text{sum filter}$$ and $$y_2[n] = (x[n]-x[n-1])/2 ~~~,~~~ \text{difference filter}$$
Lets make a qualitative analysis of these two filters by setting their input frequency $\omega_0$ to low (close to $0$), and high (close to $\pi$) values, and then observing the corresponding outputs respectively;
First, assume that $\omega_0$ is set to low frequencies: Then the consecutive input samples $x[n]$ and $x[n-1]$ will have highly similar values, as a low frequency sine wave will not change much from one sample to the other. When this is the case, their sum will add up, whereas their difference will cancel.
Therefore, $y_1[n]$ will be approximately equal to the input's value $x[n]$, while the output $y_2[n]$ will be close to zero, due to cancelling of $x[n]$ by $x[n-1]$ when subtracted. Then we conclude that the sum filter passes the low frequencies while the difference filter attenuates (blocks) them.
For the second part of the analysis, set $\omega_0$ to high frequencies: then the values of the input samples $x[n]$ and $x[n-1]$ will be of opposite polarities, as the cosine will be rapidly changing from sample to sample. Then, their sum will cancel, whereas their difference will add up.
Therefore, $y_1[n]$ will be approximately zero, while $y_2[n]$ will be following the input. Then we see that the sum filter blocks high frequencies while the difference filter passes them.
Combining these two analyses we conclude that the sum filter is a lowpass filter, which passes low frequencies and attenuates high frequencies, while the difference filter is a highpass filter, which attenuates low frequencies and passes high frequencies.
Following this basic basic setting, more complex filters are realized through using more samples at farther delays, and are weighted properly. Then the passband and stopband cutoff frequencies, the transition bandwidth and ripples are all determined by those delays and weights applied into the summing (or differencing) samples and the number of samples (length of filter) used in the sums (or differences).
Those weights are then called as the filter coefficients (or its impulse response $h[n]$ for the FIR filter) that characterize the filter.
You have probably used filtering a lot already. A moving average is a filter!
Think of general filtering as performing a fancy moving average where instead of averaging every component in a window equally, you weight the components.
If you just wanted to smooth the signal you could weight each value used in the average by a Gaussian (bell) curve for example. This is a low pass filter.
If you wanted to isolate a particular frequency you could weight each value alternatively positive and negative at the same frequency.
I think you're looking for intuition as to why you get a certain frequency domain behavior when computing a weighted sum of input samples. As you know, the output signal of a causal length $N$ FIR filter is given by
$$y[n]=\sum_{k=0}^{N-1}h[k]x[n-k]\tag{1}$$
where $h[n]$ are the filter coefficients (taps), or, equivalently, the filter's finite length impulse response, and $x[n]$ is the input signal.
Now let $x[n]=e^{j\omega_0n}$, i.e., a complex exponential at frequency $\omega_0$. The corresponding output signal is
$$y[n]=\sum_{k=0}^{N-1}h[k]e^{j\omega_0(n-k)}=e^{j\omega_0n}\sum_{k=0}^{N-1}h[k]e^{-j\omega_0k}=e^{j\omega_0n}H(\omega_0)\tag{2}$$
where
$$H(\omega)=\sum_{k=0}^{N-1}h[k]e^{-j\omega k}\tag{3}$$
is the frequency response of the filter, evaluated at $\omega=\omega_0$. It equals the discrete-time Fourier transform of the impulse response $h[n]$.
Eq. $(2)$ shows how an input frequency component at frequency $\omega_0$ appears at the output. Its amplitude is scaled by $|H(\omega_0)|$, and its phase is shifted by $\arg\{H(\omega_0)\}$. As an example, you could choose the coefficients $h[n]$ such that $H(\omega_0)=0$ for a certain frequency $\omega_0$. In this case, the corresponding frequency component in the input signal is completely suppressed by the filter. This is what notch filters do.
Eq. $(2)$ explains the frequency domain behavior of a discrete-time filter. You can approximate any desired frequency response $D(\omega)$ by $H(\omega)$ by choosing the coefficients $h[n]$ in an appropriate way. This is the topic of approximation theory, or, more specifically, (frequency-domain) design of digital filters. Have a look at this answer for a brief overview of digital filter design and for some references.
To the useful answers that have been added so far, I would like to add, on the point of intuition, that filtering works because it is based on Wave theory and specifically, the interaction of waves. This provides a huge array of intuitive examples.
But also, that there are basically two viewpoints. One is the abstract viewpoint, taken by modelling reality and then working with the models and the other one is the "physical" reality. That is, what is actually happening in nature.
For example, in reality, sound from a source bounces off of a wall and comes back at the ears of the listeners. This is reality. "Modelling" reality is to say that the wall is just a detail. What is happening is that there is another source, at a well defined location BEHIND the wall that is playing back the sound of the source. This simple model then allows reflections to be studied as the addition of waves...But there is nothing on the other side of the wall.
$y=a \times cos(\omega t + \phi)$ is an oscillator. If it was coming out of a function generator, on top of a bench, we could say that $y$ corresponds to the jack of the output, $a$ is the amplitude dial, $\omega$ is the frequency dial and $\phi$ is the phase dial. So, each one of our abstract symbols has a physical meaning. We can play with the frequency dial and it immediately becomes accessible to us, it becomes part of our experience.
Can we play with that $h$ that Matt. L is talking about in his response further above? What is the physical correspondence of $h$? What is actually happening in reality? What is $h$?
$h$ is many wonderful things. A room is an $h$. A long tunnel passage under a bridge is an $h$. The atmosphere is an $h$. A piano is an $h$ (generally, the resonators of instruments). The ocean is an $h$. A piece of wire is an $h$. A guitar amplifier is an $h$.
Imagine yourself in what we call free space. Free space is space so big that your voice falls flat, it doesn't resonate at all. It's a very strange feeling. To realise what "flat" really means, you have to find yourself in a shop that sells fabrics (or an unechoic chamber...the fabric shop is easier). All the merchandise absorbs sound so much that you get a sense of complete isolation and without any sense of direction.
But anyway, we are in free space and we have that function generator on a speaker somewhere in front of us. Turn it on. You hear the crystal clear sound of a whistle. The speaker sets the air in vibrating motion and eventually the waves reach our ears.
We now bring in a flat sheet of granite. It is a large sheet of granite on wheels and we can position it anywhere we like, we position it somewhere behind us and observe that when we move at a specific location between the speaker and the granite sheet, the sound reduces in amplitude, until it disappears completely. Why is this happening? Because the peaks of the waves that the speaker produces in front of us, combine (perfectly) with the troughs of the waves that are produced by the phantom speaker behind us (or actually, the fact that the same waves from the speaker, bounce off of the granite sheet and recombine. By the way, because of the physics of this bouncing, wherever you have a reflection, the phase of the reflected signal is flipped). Therefore, where the front speaker creates some pressure, the rear speaker (the reflection) creates some "suction" and the air effectively doesn't move.
What does this have to do with $h$?
Let's start with an "empty" $h$. No, it's not all zeros, it looks like this $h= [1,0,0,0,0,0,0,0]$. The signal that hits the ears is $z=y * h$. The $*$ here denotes the convolution from Matt. L's response above. With this $h$, $z$ is identical to $y$. This is us in free space. We now bring in the granite sheet detail. How does this change $h$?
Could be something like this $h=[1,0,0,0,0,1,0,0,0,0]$. Which represents 1 bounce some time later than the immediate forward wave reaching our ears. If the distance between the two $1$s corresponds to half a wavelength of the frequency of our generator, $z$ will be zero. Other wavelengths will be cancelling out proportionally.
So...We can carve the harmonic spectrum of $z$...by careful placement of echoes in $h$...
Now, forget about gravity. We float in free space (not outer space) and we bring in sheets of granite, sheets of plywood, sheets of plywood covered in fabric, sheets of really thick fabric, gypsum, glass, etc and we can position them in every way we like. Because of the different materials, the "echo profile" we are effectively sculpting will have different amplitudes. So your $h$ will end up being something like $h=[1.0,0,0,0,0,-0.6,0,0.1,-0.05,0,0,0,0,0]$.
Does this actually happen in reality? Yes! Every time that you experience sound in a beautiful concert hall, someone has sat there for hours trying to sculpt the room's $h$ so that its reflections don't give people a headache or you can actually hear what the speaker says. And you can see the sculpting tools all around you, there are bass traps, there are diffusers, there are simply panels hanging from the ceiling, there are curtains, each one of these corresponding to one or more coefficients in $h$. In fact, the $h$ was starting to be sculpted since the architect specified the shape of the space.
Can we "get" the $h$ of a room? Certainly, go to your living room, inflate a balloon and leave it somewhere close to your TV, put a microphone somewhere close to the couch and pinch the balloon so that it bursts. What happens? A sharp atmospheric disturbance (a unit pulse) travels through space, it hits the microphone but also bounces off walls and objects and hits the microphone later. There you have it, an $h$ that when convolved with the "flat" signal from your TV would simulate what you actually hear in your living room. Now, repeat the same experiment in the bathroom (covered in tiles, different signature), or a long bunker in Scotland.
Different rooms, different $h$, different hearing experience. Different hearing experience at the long cobble-stone underpass, different hearing experience in the fabric shop.
It's a thunderstorm. You see the bolt (that's your first $1$) and later on you hear rumble (subsequent echoes of the electric arc). That's the $h$ that carries information about the landscape and the atmosphere around us as the atmospheric disturbance caused by the lightning arc travels in space and bounces. It takes the bursting of more than a balloon to see it though. You hit the note of a piano, the wave travels along the string, bounces of its end and comes back, it also travels through the wooden body of the piano and returns. Different material for the strings and the body, different $h$, different piano.
Tie a light bulb to a brick, throw it overboard and record it bursting at depth (from this site). That's the $h$ of the ocean below the boat, it conveys information about how sound propagates.
What do all these phenomena have in common? Waves! Mechanical waves in fact, in the case of sound and the ways they interact. And actually, it's just a good enough approximation. There are many interesting non-linear phenomena (or this one) that take place in the sea and in the air and certainly in electronic circuits (reality, in general) that get lumped together in this simple model of interacting sinusoids and where this representation of reality would break.
Finally, please note that in the "modelling" reality, (from the mathematical point of view) the convolution integral is a a way of solving differential equations (models of systems) and has other applications too (please see the last three in this list).
An intuitive way to look a FIR filter is as a sort-of running match function. A weighted-sum-of-samples outputs how much the input looks similar to some "match" value inherent in the weights.
A bandpass filter looks sort of like a chunk of some waveform at the frequency that you want the filter to pass. A good match from a segment of about the same frequency of input signal outputs a high positive value. Shift that input 90 degrees, and the match is orthogonal, or nearly so, so the filter outputs a low value. Shift another 90 degrees, and the signal waveform now looks to be roughly the inverse of the FIR waveform, so the filter outputs a negative value. This alternation from positive to negative thus produces an output waveform that somewhat resembles the input waveform if it is a good match at some phase and an opposite match at other phases. Other input waveforms, such as DC, or a much higher frequency, won't match nearly as well, so will produce lower output values.
A moving average or low pass FIR filter has lots of weights the same or nearly the same, so will output at a higher level when the input does not oscillate both with positive and negative values around DC, which will cancel out, at least partially, when summed after nearly the same weighting.
Whereas a FIR filter kernel that alternates every weight, or nearly so, will cancel out given a DC input, but better match highest frequency inputs, and thus output more given input that looks less like DC, e.g. a high-pass filter.
Since FIR filtering in as LTI process, the "linear" in LTI means you can sum multiple "match types" together to create a linear combination of frequency responses, which is sort-of why the inverse FT of a frequency response produces a impulse response that can be used for FIR filtering with roughly that desired frequency response.
Some functions, such as sine and cosine, can be closely approximated by a short recursion. An IIR filter can be looked at as simply a combination of a short recursion function generator that generates some desired FIR filter-like "match" waveform, plus simultaneously doing the above match process at the same time.
