A guitar effects pedal processes sound live: when sample k arrives it must produce output sample k. A recording studio's software, working on a finished recording, can look ahead. Both run FIR filters (finite impulse response): each output sample is a weighted sum of a few input samples,
y[k] = sum of c * x[k - d] over the filter's taps (d, c).
A tap with offset d = 2 uses the input from 2 samples ago, d = 0 the present sample, and d = -1 the next sample, which has not arrived yet.
- The filter is causal if no tap uses a future input (no negative offset). Only causal filters can run live without delay.
- It is memoryless if every output uses only the present input (every tap has offset 0).
- It must store the largest positive offset's worth of past samples (0 if it uses no past samples).
- It must wait for the most negative offset's worth of future samples before it can answer (0 if it uses no future samples). A pedal can run any such filter if it delays its output by that many samples.
A tap whose coefficient is 0 does nothing and does not count.
Write filter_needs(taps) that returns the tuple (causal, memoryless, store, wait).
Examples
Input: taps = [(0, 0.5), (1, 0.3), (3, 0.2)]
Output: (True, False, 3, 0)
Explanation: y[k] = 0.5*x[k] + 0.3*x[k-1] + 0.2*x[k-3] needs the last 3 samples
and nothing from the future.
Input: taps = [(-1, 0.25), (0, 0.5), (1, 0.25)]
Output: (False, False, 1, 1)
Explanation: a centred smoother needs x[k+1]; live, it must answer one sample late.
Input: taps = [(0, 2), (4, 0)]
Output: (True, True, 0, 0)
Explanation: the tap at offset 4 has coefficient 0, so this is a plain amplifier.
Constraints
- the offsets in
tapsare distinct - a list
[causal, memoryless, store, wait]is accepted in place of a tuple
Goals
- Tell a causal filter (past and present only) from one that needs the future
- Tell a memoryless system from one that remembers past samples
- Work out how many samples a filter must remember, and how long it must wait