FA-91546 / Digital signal filters / Open access
Polyphase decimator drops the last partial output · case 01
For a length not divisible by D the final output sample is missing.
ROOT CAUSE
The output count is floor(len / D) instead of ceil(len / D).
VERIFIED REPAIR
Use (len + D - 1) // D outputs.
Unsuccessful approach: The attempted repair uses len // D + 1, producing an extra sample when the length is divisible.
Case contract
Input [h, D, samples] (integers). Output y[m] = sum_k h[k] x[mD - k] for m = 0 .. ceil(len/D) - 1 with x = 0 outside the signal, computed through the polyphase split E_p[j] = h[jD + p].
Why this case matters
Polyphase decimators avoid computing discarded outputs; commutator and phase-split slips alias the output.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
h, D, xs = x
L = len(xs)
M = L // D
phases = [h[p::D] for p in range(D)]
out = []
for m in range(M):
acc = 0
for p in range(D):
for j, c in enumerate(phases[p]):
idx = (m - j) * D - p
if 0 <= idx < L:
acc += c * xs[idx]
out.append(acc)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression: impulse through D=2', [[1, 2, 3], 2, [1, 0, 0, 0, 0]], [1, 3, 0]], ['regression: first sample matters', [[1], 3, [7, 1, 1, 1]], [7, 1]], ['repair check: length divisible', [[1, 1], 2, [1, 2, 3, 4]], [1, 5]], ['regression: long filter D=3', [[1, 2, 3, 4, 5], 3, [1, 0, 0, 2, 0, 0, 3]], [1, 6, 11]], ['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]]], [['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['repair check: random polyphase 5', [[3, 1, -1, 0, -1], 2, [-3, 5, 4, 1]], [-9, 20]], ['regression: long filter D=3', [[1, 2, 3, 4, 5], 3, [1, 0, 0, 2, 0, 0, 3]], [1, 6, 11]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]]], [['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]], ['repair check: random polyphase 13', [[1, 4], 2, [-4, 3, -1, 4]], [-4, 11]], ['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 7', [[1, -1, 0], 4, [4, 5, -2, -1, 0]], [4, 1]]], [['regression: random polyphase 8', [[-3, 0, 2, 1, 2], 4, [-2, 0, -1, -1, -4, -2, 1]], [6, 6]], ['regression: random polyphase 9', [[1, -2, 2, 3, 1, 0], 3, [5, 2, 1, -3, 4, 0, 0, 1]], [5, 14, 0]], ['repair check: random polyphase 15', [[4, -2, -3, 1, 1, 3, 1], 4, [2, -2, -3, 5]], [8]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]]], [['regression: random polyphase 11', [[-2, 1, 4, -2, -3], 4, [-1, -4, -2, 5, 4, 5, 3, 1, 0]], [2, 0, -9]], ['regression: random polyphase 16', [[-2, -1, -1, -1, 2, 0, -3], 4, [5, 5, 4, 1, 1, 2, 0, 1, -1]], [-10, -2, -11]], ['repair check: random polyphase 21', [[1, 1, -3], 4, [2, 2, -1, -1]], [2]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]], ['regression: random polyphase 7', [[1, -1, 0], 4, [4, 5, -2, -1, 0]], [4, 1]]]]
for label, args, expected in fixtures[N-1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: impulse through D=2 | [1, 3] | [1, 3, 0] | Failed |
| regression: first sample matters | [7] | [7, 1] | Failed |
| repair check: length divisible | [1, 5] | [1, 5] | Passed |
| regression: long filter D=3 | [1, 6] | [1, 6, 11] | Failed |
| regression: random polyphase 0 | [6, 11, -4] | [6, 11, -4, -3] | Failed |
| regression: random polyphase 1 | [-6] | [-6, 4] | Failed |
| regression: random polyphase 3 | [-15] | [-15, 6] | Failed |
SHA-256 / cdd69b4cbcf5b9aa8cd70bb74992f5a8fd2f33a3655a4f28d6619a2cdf93f0aa
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
h, D, xs = x
L = len(xs)
M = L // D + 1
phases = [h[p::D] for p in range(D)]
out = []
for m in range(M):
acc = 0
for p in range(D):
for j, c in enumerate(phases[p]):
idx = (m - j) * D - p
if 0 <= idx < L:
acc += c * xs[idx]
out.append(acc)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression: impulse through D=2', [[1, 2, 3], 2, [1, 0, 0, 0, 0]], [1, 3, 0]], ['regression: first sample matters', [[1], 3, [7, 1, 1, 1]], [7, 1]], ['repair check: length divisible', [[1, 1], 2, [1, 2, 3, 4]], [1, 5]], ['regression: long filter D=3', [[1, 2, 3, 4, 5], 3, [1, 0, 0, 2, 0, 0, 3]], [1, 6, 11]], ['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]]], [['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['repair check: random polyphase 5', [[3, 1, -1, 0, -1], 2, [-3, 5, 4, 1]], [-9, 20]], ['regression: long filter D=3', [[1, 2, 3, 4, 5], 3, [1, 0, 0, 2, 0, 0, 3]], [1, 6, 11]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]]], [['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]], ['repair check: random polyphase 13', [[1, 4], 2, [-4, 3, -1, 4]], [-4, 11]], ['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 7', [[1, -1, 0], 4, [4, 5, -2, -1, 0]], [4, 1]]], [['regression: random polyphase 8', [[-3, 0, 2, 1, 2], 4, [-2, 0, -1, -1, -4, -2, 1]], [6, 6]], ['regression: random polyphase 9', [[1, -2, 2, 3, 1, 0], 3, [5, 2, 1, -3, 4, 0, 0, 1]], [5, 14, 0]], ['repair check: random polyphase 15', [[4, -2, -3, 1, 1, 3, 1], 4, [2, -2, -3, 5]], [8]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]]], [['regression: random polyphase 11', [[-2, 1, 4, -2, -3], 4, [-1, -4, -2, 5, 4, 5, 3, 1, 0]], [2, 0, -9]], ['regression: random polyphase 16', [[-2, -1, -1, -1, 2, 0, -3], 4, [5, 5, 4, 1, 1, 2, 0, 1, -1]], [-10, -2, -11]], ['repair check: random polyphase 21', [[1, 1, -3], 4, [2, 2, -1, -1]], [2]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]], ['regression: random polyphase 7', [[1, -1, 0], 4, [4, 5, -2, -1, 0]], [4, 1]]]]
for label, args, expected in fixtures[N-1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: impulse through D=2 | [1, 3, 0] | [1, 3, 0] | Passed |
| regression: first sample matters | [7, 1] | [7, 1] | Passed |
| repair check: length divisible | [1, 5, 4] | [1, 5] | Failed |
| regression: long filter D=3 | [1, 6, 11] | [1, 6, 11] | Passed |
| regression: random polyphase 0 | [6, 11, -4, -3] | [6, 11, -4, -3] | Passed |
| regression: random polyphase 1 | [-6, 4] | [-6, 4] | Passed |
| regression: random polyphase 3 | [-15, 6] | [-15, 6] | Passed |
SHA-256 / 95c0027d973488dfb0622ec74e240bd7358a59b0d2b957c02fdca2976cc5757e
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
h, D, xs = x
L = len(xs)
M = (L + D - 1) // D
phases = [h[p::D] for p in range(D)]
out = []
for m in range(M):
acc = 0
for p in range(D):
for j, c in enumerate(phases[p]):
idx = (m - j) * D - p
if 0 <= idx < L:
acc += c * xs[idx]
out.append(acc)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression: impulse through D=2', [[1, 2, 3], 2, [1, 0, 0, 0, 0]], [1, 3, 0]], ['regression: first sample matters', [[1], 3, [7, 1, 1, 1]], [7, 1]], ['repair check: length divisible', [[1, 1], 2, [1, 2, 3, 4]], [1, 5]], ['regression: long filter D=3', [[1, 2, 3, 4, 5], 3, [1, 0, 0, 2, 0, 0, 3]], [1, 6, 11]], ['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]]], [['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['repair check: random polyphase 5', [[3, 1, -1, 0, -1], 2, [-3, 5, 4, 1]], [-9, 20]], ['regression: long filter D=3', [[1, 2, 3, 4, 5], 3, [1, 0, 0, 2, 0, 0, 3]], [1, 6, 11]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]]], [['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]], ['repair check: random polyphase 13', [[1, 4], 2, [-4, 3, -1, 4]], [-4, 11]], ['regression: random polyphase 0', [[2, -1], 2, [3, -3, 4, -2, -3, 5, 1]], [6, 11, -4, -3]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 7', [[1, -1, 0], 4, [4, 5, -2, -1, 0]], [4, 1]]], [['regression: random polyphase 8', [[-3, 0, 2, 1, 2], 4, [-2, 0, -1, -1, -4, -2, 1]], [6, 6]], ['regression: random polyphase 9', [[1, -2, 2, 3, 1, 0], 3, [5, 2, 1, -3, 4, 0, 0, 1]], [5, 14, 0]], ['repair check: random polyphase 15', [[4, -2, -3, 1, 1, 3, 1], 4, [2, -2, -3, 5]], [8]], ['regression: random polyphase 1', [[-2, 4, -1, -1, 1, -3], 4, [3, 0, 1, 0, -1, -2]], [-6, 4]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]]], [['regression: random polyphase 11', [[-2, 1, 4, -2, -3], 4, [-1, -4, -2, 5, 4, 5, 3, 1, 0]], [2, 0, -9]], ['regression: random polyphase 16', [[-2, -1, -1, -1, 2, 0, -3], 4, [5, 5, 4, 1, 1, 2, 0, 1, -1]], [-10, -2, -11]], ['repair check: random polyphase 21', [[1, 1, -3], 4, [2, 2, -1, -1]], [2]], ['regression: random polyphase 3', [[-3], 4, [5, -1, 2, 1, -2]], [-15, 6]], ['regression: random polyphase 4', [[0, -1, 1, -1, 4], 3, [3, 2, 5, 3, -1, 0, -3, 2, -1, -2]], [0, -6, 16, 6]], ['regression: random polyphase 6', [[1, -2, 3, 2, -1], 4, [4, 3, 5, -3, -4, -2]], [4, 19]], ['regression: random polyphase 7', [[1, -1, 0], 4, [4, 5, -2, -1, 0]], [4, 1]]]]
for label, args, expected in fixtures[N-1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: impulse through D=2 | [1, 3, 0] | [1, 3, 0] | Passed |
| regression: first sample matters | [7, 1] | [7, 1] | Passed |
| repair check: length divisible | [1, 5] | [1, 5] | Passed |
| regression: long filter D=3 | [1, 6, 11] | [1, 6, 11] | Passed |
| regression: random polyphase 0 | [6, 11, -4, -3] | [6, 11, -4, -3] | Passed |
| regression: random polyphase 1 | [-6, 4] | [-6, 4] | Passed |
| regression: random polyphase 3 | [-15, 6] | [-15, 6] | Passed |
SHA-256 / 1ba1deb561d794a6e663ec08e4399e0a46a6ec1f59b8802e716e45b4e37b82fb
Verification & scope
A deterministic bounded teaching model with a stipulated toy contract; exact rational arithmetic or fixed-decimal rounding keeps outputs strict JSON. It is not a production DSP library and claims no standards conformance. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:36.930245+00:00.
Case digest / 0463b500b6d112066a972ca427e8f501aa97ba05025967ae7699bfa1bea8942e