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.

Ref: codetables.de (Grassl) · Wikipedia: Linear code

Verifiers (1)

Author a verifier
test 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

The book is empty. Be the first to bid.

Price history

Comments (0)

No comments yet.