Research report · rs-codesign benchmark

Co-Designing MDS Erasure Codes Across GF(2³)–GF(2⁸)

Schedule-aware search over six binary fields · 117 machine-verified code shapes · C++ pipeline (~1,000 lines) · July 2026 · code & data: github.com/verma7/rs-codesign-cpp
117
code shapes co-designed — every (k, r) ∈ {4…200} × {2…11} that fits each field, n = 3…8
117 / 117
shapes where the smallest admissible field gave the cheapest encoder (per data bit)
3.824
XORs per data bit for RS(108+4) in GF(2⁷) — beating GF(2⁸) co-design (4.089) and certified permutation codes (4.030)

1 · Problem

A systematic MDS erasure code with generator [I | Pᵀ] protects k data symbols with r parity symbols such that any k of the k+r survive-and-decode. For XOR-engine encoders (bit-matrix software, FPGA/ASIC), each GF(2ⁿ) entry of the parity block P expands into an n×n binary matrix, and the encoder's true cost is the scheduled XOR count of that (n·r)×(n·k) bit-matrix after common-subexpression elimination — not the matrix's one-bit count, which earlier experiments showed is only a proxy. The question here: for each code shape (k, r), which field, which polynomial, which matrix — and how cheap can the encoder get?

2 · Background

P must be superregular (every square submatrix nonsingular) for the code to be MDS. Generalized Cauchy matrices Pij = uivj/(xi⊕yj) guarantee this by construction at any size, which matters because exhaustive verification explodes combinatorially (≈10¹⁵ minors at (108,11)). Within the Cauchy family, three levers change the bit-level cost without touching the MDS guarantee: the field polynomial, the evaluation points, and per-row/column scalars. Two further facts drive the design: scheduling (Paar CSE + a row-MST hybrid) recovers 30–65% of naive XORs, and — the headline of the earlier session — optimizing the matrix through the scheduler beats optimizing it for sparseness. This benchmark adds the last free variable: the field size n itself.

3 · Algorithm

  1. Field scan. Enumerate all irreducible degree-n polynomials (2, 3, 6, 9, 18, 30 for n = 3…8; a subfield-gcd test is required at n = 6, where the naive checkpoint test admits reducibles). Keep the polynomial whose scaled-Cauchy seed is lightest.
  2. Point optimization. Hill-climb the Cauchy x-points with column-optimal y-selection under the one-bit metric, then ones-greedy row/column scaling — a fast warm start.
  3. Scheduled sweeps. Coordinate descent over all r + k scalar knobs; each knob tests every field scalar, evaluated exactly as min(Paar-CSE, MST-hybrid) XORs on the expanded bit-matrix — a bucket-queue scheduler with native popcounts, batched over 16 threads — iterated to fixpoint.
  4. GA refinement. Leftover budget runs a genetic algorithm over (y-points, column scalars, row scalars) with column-gene crossover and duplicate repair; every individual stays inside the Cauchy family, hence MDS.
  5. Verification. Shapes with ≤ 500k minors get exhaustive superregularity checks (60 of 117 passed, zero failures); the rest are MDS by construction.

4 · Results

The smallest field that fits is always the right field. In all 117 runs, the minimum-n field admitting the shape (k + r ≤ 2ⁿ) produced the cheapest encoder per data bit — usually by 10–25% over GF(2⁸). Mechanism: halving the symbol width halves the bit-matrix rows per parity symbol, which densifies input-pair co-occurrence, which is precisely what CSE converts into shared temporaries. The loss of point-selection freedom in a crowded small field never outweighed it.

r = 2 is solved. Every RAID-6-shaped code landed exactly on its no-sharing floor r(k−1)/k — e.g. (4,2) at 1.500 XORs/bit in every field from GF(2³) up.

Small fields dive below the no-sharing floor. (4,11) in GF(2⁴) costs 6.56 XORs/bit against a floor of 8.25 — cross-output sharing at work; per-row lower-bound arguments do not bind scheduled encoders.

Three prior champions retired. RS(108+4): GF(2⁷) at 3.824 XORs/bit beats both the GF(2⁸) co-design (4.089) and the certified permutation-power code (4.030). RS(108+5): 4.813 vs 4.873 from the earlier Python pipeline. RS(10+4): GF(2⁴) at 3.100 beats even the free-search GF(2⁸) champion (3.613) — the field-size lever outweighs the matrix-family lever.

Scope note. These costs matter for XOR-engine encoders. SIMD table-lookup encoders (PSHUFB/GFNI) are insensitive to all of this. And 46 of the 48 GF(2⁸) grid shapes (including k = 200, which only GF(2⁸) can host) were not run before termination — reproducible via ./rs-codesign grid.

5 · Interactive explorer

Scheduled XORs per data bit, by parity count and field
Lower is better. Choose a data-symbol count k; each line is one field GF(2ⁿ). The dashed gray line is the no-sharing floor r(k−1)/k — the cost if every parity bit were computed independently; scheduled encoders can legitimately dip below it via cross-output sharing. Hover for exact values and distance to the floor.
k =
The same data as a field × parity heatmap
Sequential shading (darker = more XORs per data bit) for the selected k. The lightest row is consistently the smallest field that fits.
All 117 runs
Click a column header to sort. Bold rows are the best field for their (k, r). “ver” = exhaustive MDS verification (others are Cauchy-guaranteed).
field

6 · Reproduce

cd rs-codesign-cpp
make            # clang++ -O3, no dependencies
make test       # field self-tests + exhaustive MDS checks
./rs-codesign grid              # full matrix -> results.csv (this dataset)
./rs-codesign single 7 108 11 90   # one shape, 90 s budget

Data: results.csv (117 rows) · log: grid-run.log · source & full results: github.com/verma7/rs-codesign-cpp

← All research