2.6 When the output list has a fixed length

Full multiplication needs extra space

Two length-N lists can produce positions as high as (N−1)+(N−1)=2N−2. Full linear convolution therefore needs up to 2N−1 output positions. But some systems deliberately keep only N storage positions.

Once output storage is fixed, the system needs an explicit boundary rule. There is no single default.

Truncatediscard positions ≥ N

Information beyond the boundary is lost.

Cyclicposition N+k → k

Wrap to the start with the same sign.

Negacyclicposition N+k → k, negate

Wrap to the start and flip the sign.

A circular-buffer picture

Let N=8. Imagine positions 0 through 7 around a ring. Position 8 lands back at 0, position 9 at 1, and so on. Negacyclic wrap attaches a minus sign to every value that crosses the boundary once.

01234567boundary8 → − at 09 → − at 1

Animated visual · ManimCross once, flip once

A destination beyond N returns to the fixed list with its sign reversed. Unmute for narration.

Worked example

Route one over-the-edge product

With N=8, multiply a value 3 at position 6 by value 5 at position 4. The ordinary destination is 6+4=10 and the product is 15. Since 10=8+2, negacyclic wrap sends it to position 2 as −15.

Check your understanding

With N=8, where does a product destined for position 13 go under negacyclic wrap?

Work a complete fixed-length example

Let N=4, A=[1,2,0,1], and B=[3,−1,1,0]. First compute the ordinary length-7 convolution:

A∗B = [3, 5, −1, 5, −1, 1, 0]

Positions 0 through 3 stay in place. Position 4 wraps to 0 and changes sign; position 5 wraps to 1 and changes sign; position 6 wraps to 2 and changes sign:

fixed 0ordinary c₀ − c₄3−(−1)=4

fixed 1ordinary c₁ − c₅5−1=4

fixed 2ordinary c₂ − c₆−1−0=−1

fixed 3ordinary c₃5

A(x)B(x) with x⁴ = −1 ↔ [4, 4, −1, 5]

Writing the ordinary convolution first is intentionally inefficient on paper. It exposes where every sign came from and gives us an independent oracle for the direct wrapped implementation.

Coefficient formula with one possible wrap

When both inputs have length N, their largest product destination is below 2N. Each fixed output bucket t can therefore receive direct terms at destination t and wrapped terms from destination t+N:

fixed bucket t = (ordinary bucket t) − (ordinary bucket t+N)

The minus sign is the entire “nega” part. This plain bucket statement is equivalent to more formal quotient-ring notation, but it requires no number theory.

Express the boundary rule as a branch

Code can make the definition less mysterious. The direct case adds into the ordinary destination. The wrapped case subtracts the product at destination−N. Walk through the branch using i=3, k=2, and N=4.

Runnable Python · explicit lists and loopsComplete source

01destination = i + k02product = left_value * right_value03 04if destination < size:05    output[destination] += product06else:07    output[destination - size] -= product

Compare the rules in executable form

Return to the reactive convolution notebook and switch its boundary policy. Use the same inputs for linear, cyclic, and negacyclic outputs. The pair products do not change; only the destination and sign policy changes. This isolates the boundary rule as a design choice rather than a mysterious new multiplication.

Reactive Python laboratory · marimo + PyodideBuild convolution one loop at a time

Construct every pair, route it to a bucket, and change only the boundary rule to obtain negacyclic multiplication.

Open full-screen lab ↗

Runs entirely in this browser. Python executes in Pyodide WebAssembly with no remote kernel. The construction code stays visible while reactive dependents recompute whenever you change an input.

Optional formal notation

Polynomials are calculated modulo xᴺ+1, written ℤ[x]/(xᴺ+1). “Modulo” means two polynomials are treated as equivalent after repeatedly replacing xᴺ with −1. The concrete routing rule above is all later sections require.

Check your understanding

For length-N inputs, why is one subtraction of N enough for every ordinary destination?

Section summary

Linear convolution grows to 2N−1 positions.
Fixed-length multiplication needs a boundary rule.
Negacyclic wrap subtracts N from the destination and flips the sign.
Bucket t may contain direct contributions minus wrapped contributions from t+N.

Repository layer · second pass

What changes when storage permits only N output positions?

A fixed-degree ring does not merely throw high coefficients away. It supplies a boundary equation that tells us how to rewrite them. Under xᴺ=1, xᴺ⁺ʳ returns to r unchanged. Under xᴺ=−1, it returns to r with its sign flipped. This second rule is negacyclic reduction.

Separate ordinary multiplication from boundary reduction. First compute the destination degree d. Then write d=qN+r. Each crossing of the boundary contributes a factor of −1 in the negacyclic ring, so the final sign is (−1)^q.

Reasoning chain

1
Compute the ordinary degree d=i+k.
2
Divide d by N into quotient q and remainder r.
3
Use r as the stored destination.
4
Flip the sign when q is odd.
5
Accumulate with any products already at r.

Worked trace

Reduce a degree beyond one boundary

Let N=8 and consider 5x¹⁹.
Write 19=2×8+3.
The stored position is 3.
Two boundary crossings give (−1)²=+1.

Result. 5x¹⁹ reduces to +5x³; one-crossing intuition would be wrong here.

Executable lens · Python

Make the hidden state visible

def negacyclic_destination(degree, size):
    crossings, position = divmod(degree, size)
    sign = -1 if crossings % 2 else 1
    return position, sign
assert negacyclic_destination(19, 8) == (3, 1)

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

Always subtracting once; larger degrees can cross several boundaries.
Calling truncation, cyclic reduction, and negacyclic reduction interchangeable.

Retrieval and transfer

Close the book first

Reduce −3x²⁶ when N=8.
Compare x¹³ under x⁸=1 and x⁸=−1.
Explain why products of two degree-bounded inputs cross at most once.