This guide omits a fair amount of detail in order to provide a fairly quick guide.
1) Design in the s-domain
Butterworth filters have their poles evenly spaced on a circlular arc in the left hand plane of the [s/Laplace/analogue]-domain.
For a low-pass filter of order , the complex valued pole locations are:
Where and is the cutoff frequency in radians.
The transfer function in the s domain is:
Because the poles always occur in conjugate pairs for this kind of filter, it can always be expanded out into a polynomial with real-valued coefficients :
2) Convert the s-domain transfer function to the z-domain.
There are a few methods to convert an s-domain transfer function this into a [z/digital/discrete]-domain transfer function. The most common is the bilinear transform which makes the substitution:
Or if you’re performing “frequency warping”:
I won’t go into verbose details here, but you probably want frequency warping. The bilinear transform is a linear approximation to the function which maps the s-domain to the digital z-domain. This linear mapping is analogous to the first term of a series expansion of which is most accurate around z=1 (i.e. DC). The frequency warping operation moves the point where most accuracy is preserved to . For higher frequency cutoffs, this becomes important. can be set to the cutoff frequency of the filter to improve the frequency response near the transition.
For a 3-rd order system, the conversion yields (see notes at the end of this page about risks):
Which can be expanded into a rational polynomial transfer function in .
3) Convert from the z-domain to a difference equation.
First, you must make your z-domain expression causal. Positive powers of must be removed otherwise your filter would need to know the future! This is simple, just modify the numerator and denominator of the transfer function by the inverse of the highest power of . For example:
Multiply the numerator and denominator by .
Get as a function of .
The difference equation can be found by substituting z-powers as offsets to the data they are using. i.e. for the above case:
That is what you want to implement in your code.
Things to keep in mind
High-order systems can start behaving very poorly when designed in this way. Even on floating point, once a system reaches 4-th order or higher, if there are poles close to the real axis in the z-domain, the output can become severely degraded. There are ways to mitigate this: the simplest of which is to break the implementation into separate 2nd order filters (biquads).