Problem 598168 · easy · Level 05 Advanced Algorithms & Graphs

A Low-Pass Filter from the Sinc Recipe

FIR filter design · windowed sinc · window functions · low-pass filter · normalisation

A digital stethoscope samples its microphone fs times per second. Heart sounds lie below a few hundred hertz, but the microphone also picks up hiss and the rustle of clothing at higher frequencies. The firmware needs an FIR low-pass filter: a list of taps weights that keeps frequencies below cutoff hertz and removes those above.

The ideal low-pass has weights shaped like a sinc, centred in the middle of the list. With M = taps - 1 and t = k - M / 2 (the distance of weight k from the centre, in samples):

ideal[k] = 2 * cutoff / fs                                   if t == 0
ideal[k] = sin(2 * pi * cutoff * t / fs) / (pi * t)          otherwise

The ideal sinc goes on for ever; cutting it to taps weights leaves ripples in the response, so the weights are tapered towards the ends by a window w[k], chosen by name:

"rectangular":  w[k] = 1
"hann":         w[k] = 0.5 - 0.5 * cos(2 * pi * k / M)
"hamming":      w[k] = 0.54 - 0.46 * cos(2 * pi * k / M)
"blackman":     w[k] = 0.42 - 0.5 * cos(2 * pi * k / M) + 0.08 * cos(4 * pi * k / M)

Finally the weights ideal[k] * w[k] are divided by their sum, so that they add up to exactly 1: a constant signal (0 Hz) then passes through unchanged.

Write sinc_lowpass(taps, cutoff, fs, window) that returns the list of taps weights. Press Run with plot(sinc_lowpass(51, 200, 4000, "hamming"), kind="stem") to see the tapered sinc.

Examples

Input:  taps = 3, cutoff = 1000, fs = 4000, window = "rectangular"
Output: [0.2800495952130599, 0.43990080957388, 0.2800495952130599]
Explanation: M = 2. The middle weight is 2 * 1000 / 4000 = 0.5; the outer ones are
sin(-pi / 2) / (-pi) = 1 / pi = 0.3183. Dividing by their sum 1.1366 gives the output.

Input:  taps = 3, cutoff = 1000, fs = 4000, window = "hann"
Output: [0.0, 1.0, 0.0]
Explanation: the Hann window is 0 at both ends and 1 in the middle, so only the centre is left.

Values like 1.4e-17 where the exact answer is 0 count as correct.

Constraints

  • 3 <= taps <= 101 (an even taps puts the centre between two weights, so no t is 0)
  • 0 < cutoff < fs / 2; answers are compared with a tolerance of 1e-6

Goals

  • Build the weights of a low-pass FIR filter from the sinc formula
  • Taper the weights with a window (rectangular, Hann, Hamming or Blackman)
  • Scale the weights so the filter passes a constant signal unchanged
Starting Python…