MDS codes characterized by fixed smaller codes over field extensions
MDS codes containing a fixed subcode over finite field extensions
Information Theory
Summary
This work studies special error-correcting codes called MDS codes that contain a smaller fixed code inside them. The authors find a key condition that tells when such a larger MDS code can exist over extensions of a finite field. They also give a formula that counts how many of these big codes exist based on mathematical objects called matroids. The paper shows how these counts can tell apart different code structures even if they look similar in other ways.
What this means in practice
- •For coding theorists: Determine existence and count of MDS codes containing given subcodes over field extensions to guide code construction efforts.
- •For error correction engineers: Inform choice of code parameters and field sizes when extending codes while preserving error correction guarantees.
A theory result. No direct application yet.
Authors
Yangcheng Li, Pingzhi Yuan
Abstract
Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from \(U\). Its full-weight words characterize the desired MDS completions. We prove that \(U\) admits an \([n,k]\) MDS completion over some finite extension of \(\mathbb{F}_q\) if and only if \(d(U)\ge n-k+1\). When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is \[\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{χ_{δ_GM(G)}(q^m)}{q^m-1},\] where $G$ is a generator matrix of $U$, $δ_GM(G)$ is its represented derived matroid, and $χ_{δ_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.