A teaching lab has a cupboard of sealed signal boxes. Each box takes a list of numbers (the input samples) and returns a list of the same length (the output samples), always starting from rest. The lab wants each box labelled with two properties.
Linear: for any two inputs x1, x2 of the same length and any numbers a, b,
box(a*x1 + b*x2) == a*box(x1) + b*box(x2), sample by sample.
(This includes scaling, box(a*x) == a*box(x), and additivity, box(x1 + x2) == box(x1) + box(x2), where + means adding sample by sample. With a = 0 it also says that silence must give silence.)
Time-invariant: delaying the input only delays the output. Feed d samples of silence, then x; after the silence, the box must answer exactly what it answers to x alone:
box([0] * d + x)[d:] == box(x), for every input x and every delay d >= 1.
Write classify(system) that is given one box (a function) and returns the pair (linear, time_invariant) of booleans. You can only learn about the box by calling it. Compare outputs with a tolerance: two numbers count as equal when they differ by at most 1e-6 * max(1, |u|, |v|).
The tests call classify(box(i)) for the cupboard's boxes i = 0, ..., 20 (the box function is provided; try print(box(3)([1, 0, 0, 0])) with Run). Every box shows its nature on tests with inputs of 20 samples, values between -10 and 10, and delays from 1 to 5; behaviour that only shows for some inputs (large values, a positive first sample, the longest delay) does count, and a box whose answers differ from the definition by rounding dust alone still has the property. A single property may hold for some inputs and fail for others, so try several different inputs.
Examples
Input: system = box(0) (it multiplies every sample by 2.5)
Output: (True, True)
Input: system = box(9) (it adds 1 to every sample)
Output: (False, True)
Explanation: box([0, 0]) is [1, 1], not silence, so it is not linear;
it does the same thing at every moment, so it is time-invariant.
Constraints
- a list
[linear, time_invariant]is accepted in place of a tuple - your function may call the box as often as it likes (a few hundred calls is plenty)
Goals
- Test linearity by comparing the answer to a mix of inputs with the same mix of answers
- Test time invariance by feeding silence first and comparing the delayed answer
- Choose test inputs (random, large, negative, non-zero at the start) that expose a system that only looks linear