Source-linked AI summary
Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring
Umberto Martínez-Peñas
TL;DR
The general linearized structure of skew Reed-Solomon codes was unknown. This paper introduces linearized Reed-Solomon codes and proves they have maximum sum-rank distance, a metric of interest in multishot and singleshot multi-network coding.
Problem
The general linearized structure of skew Reed-Solomon codes was unknown, despite the relevance of maximum sum-rank distance to multishot and singleshot multi-network coding.
Source: §1 · p. 2Method
The paper introduces linearized Reed-Solomon codes using linear operator polynomials to describe skew metrics and skew Reed-Solomon codes, developing the theory over any division ring.
Source: §1 · p. 2, §3 · p. 10Results
All linearized Reed-Solomon codes have maximum sum-rank distance, and are the first general linear block codes with this property apart from Reed-Solomon and Gabidulin codes.
Source: §1 · p. 2Takeaways & Limitations
The sum-rank metric provides a common theoretical framework for Hamming and rank metrics and is relevant to multishot and singleshot multi-network coding.
Source: §1 · p. 2Whether an MDS linear code whose projections are MRD codes necessarily has maximum sum-rank distance remains an open problem.
Source: §3.3 · p. 18
Abstract
from arXiv · showhide
Reed-Solomon codes and Gabidulin codes have maximum Hamming distance and maximum rank distance, respectively. A general construction using skew polynomials, called skew Reed-Solomon codes, has already been introduced in the literature. In this work, we introduce a linearized version of such codes, called linearized Reed-Solomon codes. We prove that they have maximum sum-rank distance. Such distance is of interest in multishot network coding or in singleshot multi-network coding. To prove our result, we introduce new metrics defined by skew polynomials, which we call skew metrics, we prove that skew Reed-Solomon codes have maximum skew distance, and then we translate this scenario to linearized Reed-Solomon codes and the sum-rank metric. The theories of Reed-Solomon codes and Gabidulin codes are particular cases of our theory, and the sum-rank metric extends both the Hamming and rank metrics. We develop our theory over any division ring (commutative or non-commutative field). We also consider non-zero derivations, which give new maximum rank distance codes over infinite fields not considered before.
1 Introduction
The paper introduces linearized Reed-Solomon codes as the general linearized form of skew Reed-Solomon codes, then proves they achieve maximum sum-rank distance. Its proof links skew metrics and skew Reed-Solomon codes to the sum-rank metric and linearized codes.
1 Introduction
- Linearized Reed-Solomon codes extend the known linearized connection between skew Reed-Solomon codes and Gabidulin codes to all cases.That general linearized structure was previously unknown.Source: §1 · p. 2
- All linearized Reed-Solomon codes have maximum sum-rank distance, a metric of interest in multishot and singleshot multi-network coding.The sum-rank metric provides a common framework for Hamming and rank metrics.Source: §1 · p. 2
- The proof introduces skew metrics, proves skew Reed-Solomon codes have maximum skew distance, then translates these results to linearized codes and the sum-rank metric.The authors note that a shorter proof would obscure the connection between skew and linearized Reed-Solomon codes.Source: §1 · p. 2
- The theory is developed over any division ring, and its field descriptions include a case where linearized Reed-Solomon codes require derivations rather than endomorphisms.The paper also treats non-zero derivations.Source: §1 · pp. 2–3
2 Skew metrics and skew Reed-Solomon codes
Section 2 defines skew metrics and establishes maximum skew distance for skew Reed-Solomon codes. It builds on skew-polynomial evaluation and interpolation over division rings.
2.1 Skew polynomials over division rings
- Skew polynomial rings use an endomorphism and a σ-derivation in their multiplication rule, and allow evaluation and interpolation over division rings.For a P-basis of size n, Lagrange interpolation gives a unique polynomial of degree less than n matching n prescribed values.Source: §2.1 · pp. 3, 5
2.2 Skew polynomial metrics
- Skew weights measure degree after accounting for polynomial zeros on Ω; their induced metrics are invariant under P-basis changes and connect to Hamming weight.The weight is expressed through the rank of the zero set in Ω.Source: §2.2 · pp. 6–8
2.3 Maximum skew distance codes and skew Reed-Solomon codes
- Skew Reed-Solomon codes of each dimension attain the Singleton bound for skew metrics, making them maximum skew-distance codes and MDS.The bound connects maximum skew distance to the Hamming-metric Singleton bound.Source: §2.3 · pp. 8–9
3 Linearizing skew metrics and skew Reed-Solomon codes
This section develops operator-polynomial linearizations of skew metrics and skew Reed–Solomon codes, relates the resulting metrics to sum-rank metrics, and introduces linearized Reed–Solomon codes. It establishes their maximum sum-rank distance, including existence for every dimension and a range of lengths under stated conditions, and treats Reed–Solomon and Gabidulin codes as special cases.
3.1 Linear operators and operator polynomials
- Operator-polynomial evaluations are right linear over the centralizer Ka, which is a division subring, and connect skew-polynomial evaluation with operator-polynomial evaluation.The section recalls operator polynomials from and describes their general connection to skew Reed-Solomon codes as new to the authors’ knowledge.Source: §3 · p. 10, §3.1 · p. 11
3.2 Sum-rank metrics from linearizing skew metrics
- For two P-bases of the same P-closed set, the theorem gives commuting coordinate maps that are left vector space isomorphisms, establishing a correspondence between skew-metric and sum-rank isometries.Source: §3.2 · pp. 13–14
- Under the coordinate map φA, the skew weight of f equals the sum-rank weight of its image, with lengths n1 through nℓ and division subrings Ki = Ka(i).Here c = φA(f), for f in FA.Source: §3.2 · p. 15
3.3 Linearized Reed-Solomon codes with maximum sum-rank distance
- Linearized Reed-Solomon codes are defined using conjugacy representatives, basis vectors, and operator evaluations, and the subsection states that they have maximum sum-rank distance.The code definition allows dimensions k from 0 to n.Source: §3.3 · p. 16
- Linearized Reed-Solomon codes are maximum sum-rank distance codes with their specified lengths and division subrings.This follows by combining the cited results and applies to the code defined in Definition 31.Source: §3.3 · p. 17
- If the division subrings are centralizers of pairwise non-conjugate elements and 1 ≤ n_i ≤ dim_Ki(F), such codes exist for every dimension k = 1, …, n.Here n = n_1 + … + n_ℓ, and the resulting code has lengths (n_1, …, n_ℓ) over the corresponding division subrings.Source: §3.3 · p. 17
- With σ = Id and δ = 0, the construction recovers conventional Reed-Solomon codes and the Hamming metric, with 1 ≤ k ≤ n ≤ #F.In this case skew and linearized skew Reed-Solomon codes coincide.Source: §3.3 · pp. 17–18
- With σ ≠ Id and δ = 0 on C(1), the construction recovers Gabidulin codes for finite F, with 1 ≤ k ≤ n ≤ dim_K(F).The corresponding sum-rank metric is the rank metric over the fixed subfield K; σ may have finite or infinite order.Source: §3.3 · p. 18
- The pasting MDS construction [18, Section III-C] has MDS and MRD projections, but whether these properties together imply maximum sum-rank distance remains open.The construction is also a linearized Reed-Solomon code over any field.Source: §3.3 · p. 18
4 Explicit descriptions over fields
The field treatment separates inner from non-inner derivations: inner cases reduce to zero derivations, while non-inner derivations over infinite fields yield codes unavailable from inner derivations. In finite fields, the framework also compares the maximum lengths of Gabidulin and linearized Reed-Solomon codes.
4.1 Inner derivations
- When σ ≠ Id over a field, every σ-derivation is inner, and the corresponding theory can be reduced to the zero-derivation case.The section notes that this reduction does not apply to all linearized Reed-Solomon codes over infinite fields.Source: §4.1 · p. 19
4.2 Finite fields
- Over finite fields, the new skew metrics and linearized Reed-Solomon codes are new even though skew Reed-Solomon constructions and decoding algorithms were already known.For an extension Fq ⊂ Fqm, the maximum lengths are nG = m for Gabidulin codes and nL = (q − 1)m for linearized Reed-Solomon codes.Source: §4.2 · pp. 20–21
- For a fixed length n in Fqm over Fq, the minimum extension degrees are mG = n for Gabidulin codes and mL = n/(q − 1) for linearized Reed-Solomon codes.The finite-field discussion treats derivations as inner and notes q − 1 non-trivial conjugacy classes.Source: §4.2 · pp. 20–21
4.3 Non-inner derivations
- For non-inner derivations over infinite fields, some linearized Reed-Solomon codes cannot be constructed using inner derivations, while the standard derivation yields Gabidulin-type maximum-rank-distance codes.The resulting codes can have all centralizers equal to Fp(z^p) over the extension Fp(z).Source: §4.3 · pp. 21–22
A Alternative proof of Lemma 24
The appendix gives an alternative short proof of Lemma 24 by reducing the claim to evaluations of monomials and expanding the relevant terms.
A Alternative proof of Lemma 24
- The alternative proof fixes a ∈ F, writes D = Da, and denotes evaluation of x^i at b by Ni(b).It uses these definitions to establish the claim for every i ∈ N.Source: A Alternative proof of Lemma 24 · p. 23
- By linearity, it suffices to prove the stated claim for all i ∈ N; the text also gives this same proof obligation by (7).Source: A Alternative proof of Lemma 24 · p. 23
- For fixed i, expanding D(b) and δ(Di(b)b−1) on the right-hand side of equation (8) completes the proof.Source: A Alternative proof of Lemma 24 · p. 23