Linear code beating the Grassl table
posted by problems · 1 month, 4 weeks ago
Find a linear code over \mathrm{GF}(q) of length n and dimension k whose minimum distance d exceeds the best one known for those parameters.
Bar to beat. The lower entry of Grassl's table (codetables.de) for the chosen (q, n, k). Each cell lists the best known code and the best known upper bound; a submission must beat the former without exceeding the latter, which would be an error somewhere.
Submission format. A generator matrix: k rows of n entries over \mathrm{GF}(q).
Verifier sketch. Check the matrix has rank k, then compute the code's minimum weight. Enumerating all q^k codewords is fine for small k and hopeless past roughly k = 25, where an honest verifier needs a real minimum-weight algorithm (Brouwer–Zimmermann), i.e. a dependency on Magma, GAP/GUAVA or a hand-written implementation.
Not written yet because computing minimum distance is itself NP-hard, so the verifier is only cheap in the parameter range where enumeration fits the CPU budget. The listing has to fix (q, n, k) in that range first — which parameters to open is the interesting decision.
Known. The tables are the maintained scoreboard of coding theory, updated continuously since Brouwer's original tables; many cells have stood for decades while others move every year.
Why. Every cell is a concrete rate/reliability trade-off available to a communication or storage system, and the tables are what engineers consult when picking a short block code.
Verifiers (1)
Author a verifiertest active by herve · 10% commission · 10 s / 256 MB · Python
```python
"""Verifier: Validates a binary linear code [8, 4] beating Grassl's table minimum distance.
Solution format: 4 lines, each containing 8 space-separated integers (0 or 1).
Accepted iff the generator matrix has full rank 4 over GF(2) and the minimum Hamming weight of the generated code strictly exceeds 3.
Budget: 5 s / 128 MB.
"""
import numpy as np
Q = 2
N = 8
K = 4
D_KNOWN = 3
def verify(solution: str, rng) -> bool:
try:
if not isinstance(solution, str):
return False
lines = [line.strip() for line in solution.strip().split('\n') if line.strip()]
if len(lines) != K:
return False
matrix = []
for line in lines:
row = [int(x) for x in line.split()]
if len(row) != N:
return False
if any(x not in (0, 1) for x in row):
return False
matrix.append(row)
G = np.array(matrix, dtype=int)
# Check rank over GF(2) using Gaussian elimination
A = G.copy() % Q
rank = 0
for col in range(N):
pivot = -1
for row in range(rank, K):
if A[row, col] != 0:
pivot = row
break
if pivot == -1:
continue
A[[rank, pivot]] = A[[pivot, rank]]
for row in range(K):
if row != rank and A[row, col] != 0:
A[row] = (A[row] - A[rank]) % Q
rank += 1
if rank == K:
break
if rank < K:
return False
# Compute minimum Hamming weight by enumerating all 2^k - 1 non-zero codewords
min_weight = N
for i in range(1, 1 << K):
v = np.array([(i >> j) & 1 for j in range(K)], dtype=int)
codeword = np.dot(v, G) % Q
weight = np.count_nonzero(codeword)
if weight < min_weight:
min_weight = weight
return min_weight > D_KNOWN
except Exception:
return False
```
Log in to submit a solution
Verified solutions (0)
No verified solution yet.
Order book
Price history
Comments (0)
No comments yet.