PaperlayerView exact revision on arXiv

Source-linked AI summary

Twisted Reed-Solomon Codes

Peter Beelen, Sven Puchinger, Johan Rosenkilde né Nielsen

arXiv:1701.01295v2cs.ITmath.IT

TL;DR

Because generalized Reed–Solomon codes are well studied, the paper asks whether new MDS codes outside the Reed–Solomon class can be constructed. It introduces twisted Reed–Solomon codes by adding a higher-degree monomial to the evaluated polynomials, and identifies explicit subclasses containing MDS codes of length at least q/2.

  • Problem

    Because generalized Reed–Solomon codes are well studied, the paper examines whether new MDS codes outside the Reed–Solomon class can be constructed.

    Source: §V · p. 4

  • Method

    The construction evaluates polynomials with freely chosen first k coefficients and an additional monomial of degree greater than k−1.

    Source: I . I N T RO D U C T I O N · pp. 1–2

  • Results

    The two explicit subclasses yield MDS codes of length at least q/2 for any field size, and for most field sizes most of these codes are non-GRS.

    Source: I . I N T RO D U C T I O N · p. 1, §VIII · p. 5

  • Takeaways & Limitations

    Twisted Reed–Solomon codes form a new class of Fq-linear codes containing many new non-GRS MDS codes.

    Source: §VIII · p. 5

Abstract

from arXiv · show

We present a new general construction of MDS codes over a finite field $\mathbb{F}_q$. We describe two explicit subclasses which contain new MDS codes of length at least $q/2$ for all values of $q \ge 11$. Moreover, we show that most of the new codes are not equivalent to a Reed-Solomon code.

I . I N T RO D U C T I O N

The paper introduces a Hamming-metric MDS-code construction using polynomials with an extra high-degree term. Two explicit subclasses yield non-GRS MDS codes, including codes of length at least q/2 for odd q ≥ 11.

Introduction

  • The paper defines MDS codes by equality in the Singleton bound, d = n−k +1, and identifies generalized Reed–Solomon codes as prominent examples.Other known constructions use n-arcs, circulant matrices, Hankel matrices, or extensions of GRS codes, [4], [5].Source: I . I N T RO D U C T I O N · p. 1
  • The construction is inspired by Twisted Gabidulin codes, while its relation to non-GRS codes from is distinct and extends to odd q ≥ 11.The paper reports computer verification of inequivalence to the codes in for small q.Source: I . I N T RO D U C T I O N · p. 1
  • For q ≥ 11, the two explicit subclasses contain non-GRS MDS codes, and for odd q they provide a simple construction of length at least q/2.The subclasses contain codes of length up to roughly q/2 for any q; for small q, computer checks found the construction’s codes inequivalent to those in.Source: I . I N T RO D U C T I O N · p. 1
  • The authors identify code-based cryptography as a possible application and leave the suitability of the codes and their subfield subcodes for future study.Source: I . I N T RO D U C T I O N · p. 1

Preliminaries

  • The code framework evaluates a k-dimensional polynomial space at distinct points; injectivity gives a length-n, dimension-k linear code, while twisted spaces may include polynomials of degree at least k.Choosing all polynomials of degree less than k gives a Reed–Solomon code.Source: I . I N T RO D U C T I O N · p. 1

Twisted Reed–Solomon Codes

  • The construction evaluates polynomials with freely chosen first k coefficients and an extra term ηa_h x^(k−1+t), where h is the hook and t is the twist.Choosing t, h, and η so each polynomial has at most k−1 zeros among the evaluation points ensures the resulting code is MDS.Source: I . I N T RO D U C T I O N · pp. 1–2

IV. MDS TWISTED CODES

Twisted codes are not MDS for all parameter choices, but this section describes several classes that are always MDS.

  • Several classes of twisted codes are always MDS, although twisted codes are not MDS for all parameter choices.Source: §IV · p. 2

A. (∗)-twisted Codes

For (t,h)=(1,0), the MDS property is characterized by a condition on products of k evaluation points. Restricting the evaluation points to a proper multiplicative subgroup and choosing η appropriately gives an explicit MDS subclass, with length bounds and limitations described below.

A. (∗)-twisted Codes

  • C_k(α,1,0,η) is MDS exactly when no k-element index set I has η(−1)^k∏_{i∈I}α_i=1.Source: A. (∗)-twisted Codes · p. 2
  • Every (∗)-twisted code is MDS when its evaluation points lie in a proper subgroup G ∪ {0} and (−1)^kη^-1 lies outside G.The definition sets C∗_k(α,η) := C_k(α,1,0,η).Source: A. (∗)-twisted Codes · p. 2
  • For odd q, (∗)-twisted codes can have length n=(q+1)/2, using a proper subgroup of size (q−1)/2 and adjoining 0.More generally, for a prime divisor p of q−1, the construction uses a subgroup of size (q−1)/p and adjoining 0.Source: A. (∗)-twisted Codes · p. 2
  • If the selected evaluation points form a k-sum generator of F_q*, then C_k(α,1,0,η) is not MDS.The proof invokes the product criterion to show that some k-point product equals (−1)^kη^-1.Source: A. (∗)-twisted Codes · pp. 2–3
  • For odd q and η ≠ 0, an MDS code C_k(α,1,0,η) with 3 ≤ k ≤ (q−1)/2−2 must have length n ≤ (q+1)/2.Source: A. (∗)-twisted Codes · p. 3
  • For even q>4, (∗)-twisted codes cannot reach length ⌊(q+1)/2⌋, though for q=16 computer search found many [9,k] twisted codes for k=3,4,5 with other α and η.Source: A. (∗)-twisted Codes · p. 3

B. (+)-twisted Codes

The section defines (+)-twisted codes using proper additive subgroups and proves that every such code is MDS. It also gives attainable lengths and constraints on other twisted codes built from additive structure.

B. (+)-twisted Codes

  • Lemma 10 characterizes when Ck(α, 1, k−1, η) is MDS by a condition that must hold for every k-element subset of evaluation points.This is the additive-group analogue of the earlier multiplicative-group criterion.Source: B. (+)-twisted Codes · p. 3
  • Every (+)-twisted code is MDS when its evaluation points lie in a proper additive subgroup together with infinity, with η^-1 outside that subgroup.The definition requires the evaluation elements to be a subset of V ∪ {∞}, where V is a proper subgroup of (Fq, +).Source: B. (+)-twisted Codes · p. 3
  • q/p + 1 is an attainable (+)-twisted code length, and when q is even the length can be q/2 + 1.Here p is the characteristic of Fq.Source: B. (+)-twisted Codes · p. 3
  • For even q and 3 ≤ k ≤ q/2 − 2, MDS twisted codes have length at most q/2 + 1 when 3 < k < q/2 − 3, and q/2 + 2 at k = 3 or q/2 − 2.A k-sum generator S also makes Ck(α, 1, k−1, η) non-MDS when η ≠ 0.Source: B. (+)-twisted Codes · p. 3

C. General Theory of Twisted Codes

The section gives a matrix criterion for twisted codes to be MDS and proves a subfield-based construction is MDS when evaluation points lie in a proper subfield and the twist parameter lies outside it.

C. General Theory of Twisted Codes

  • Ck(α, t, h, η) is MDS exactly when the specified matrix is regular for every index set I of size k.The matrix is defined using the coefficients σ_i of the polynomial ∏_{i∈I}(x − α_i).Source: C. General Theory of Twisted Codes · p. 3
  • The criterion follows because MDS status requires that no nonzero polynomial in Vk,t,h,η have at least k evaluation roots, equivalently that each associated homogeneous system has only the zero solution.Factoring a polynomial with k selected roots and imposing its coefficient constraints yields a system in t variables.Source: C. General Theory of Twisted Codes · pp. 3–4
  • When h = k − 1 and ∞ is an evaluation point, the criterion remains valid using index sets I that exclude ∞.A polynomial vanishing at ∞ has degree less than k − 1, so this case does not affect the MDS property.Source: C. General Theory of Twisted Codes · p. 4
  • For general h and t, the upper bounds in Theorems 8 and 14 do not hold, although explicit constructions of long MDS codes seem harder to find.The section points to later constructions of long MDS codes for particular q values.Source: C. General Theory of Twisted Codes · p. 4
  • If the evaluation points lie in a proper subfield Fs of Fq and η lies outside Fs, then Ck(α, t, h, η) is MDS.The proof reduces the matrix from Lemma 15 to lower triangular form with diagonal entries η^-1 + T, 1, …, 1, where T ∈ Fs.Source: C. General Theory of Twisted Codes · p. 4

V. NON-GRS MDS TWISTED CODES

The section bounds how many MDS twisted codes in a parameterized family can be equivalent to Reed–Solomon codes. It derives conditions yielding non-GRS MDS twisted codes from subgroup and subfield constructions, including length guarantees for specified field sizes.

V. NON-GRS MDS TWISTED CODES

  • At most 6 choices of η yield a Reed–Solomon-equivalent code when every code in the family indexed by H is MDS and 2 < k < n − 2.Theorem 18 assumes α1, …, αn ∈ Fq.Source: §V · p. 4
  • The proof makes generator-matrix entries affine in η and uses a 3×3 minor whose degree-at-most-6 polynomial must vanish for Reed–Solomon equivalence.A nonzero minor rules out equivalence, so it can vanish for at most six η values.Source: §V · p. 4
  • A multiplicative subgroup G with |Fq* \ G| > 6 yields non-GRS (*)-twisted codes, while an additive subgroup V with |Fq \ V| > 6 yields (+)-twisted codes, for n ≤ |G| or n ≤ |V|.Both conclusions require 2 < k < n − 2.Source: §V · p. 4
  • If Fs is a proper subfield with |Fq \ Fs| > 6 and n ≤ s, some η outside Fs gives an MDS code not equivalent to a GRS code.The parameters also require 2 < k < n − 2.Source: §V · p. 4
  • For q ≥ 13, Corollary 19 guarantees non-GRS twisted codes of length ⌈(q + 1)/2⌉; Corollary 20’s size condition holds when q = p^m with p > 3 and m > 1.The latter condition applies to every proper subfield Fs ⊊ Fq.Source: §V · p. 4

VI. COMPUTER SEARCHES

The section reports exhaustive computer searches for twisted codes over small fields, restricted to nonzero η and min{k, n−k} > 2 to focus on non-GRS codes.

VI. COMPUTER SEARCHES

  • The searches used SageMath v7.4, and the full results and source code are available for download.The search scope was η ≠ 0 and min{k, n−k} > 2.Source: §VI · p. 4

A. Number of (∗)-Twisted Codes

The enumeration finds that, for odd q, (∗)-twisted codes can have length up to (q+1)/2 for arbitrary k, and that almost all such codes are non-GRS. It also identifies exactly one non-GRS (∗)-twisted code, a case not guaranteed by Corollary 2.

A. Number of (∗)-Twisted Codes

B. Comparison with Roth–Lempel Codes

The section compares Roth–Lempel codes with twisted-code families, reporting computational evidence that the families are largely independent and noting a parity-dependent difference in construction range.

B. Comparison with Roth–Lempel Codes

C. Length ≈q/2 Codes with “Exotic Twists”

Exhaustive search finds length ⌊q/2⌋ twisted MDS codes for nearly all choices of (t, h) when q ≤ 19, with stated exceptions for (1, k − 1). The section contrasts these findings with the known odd- and even-q subclasses that permit lengths ≈q/2.

C. Length ≈q/2 Codes with “Exotic Twists”

  • The (∗)-twisted and (+)-twisted subclasses allow codes of length ≈q/2 for odd and even q, respectively.They correspond to (t, h) = (1, 0) and (t, h) = (1, k − 1), respectively.Source: C. Length ≈q/2 Codes with “Exotic… · p. 5
  • For every q ≤ 19, exhaustive search verified length-⌊q/2⌋ twisted MDS codes for almost every (t, h), except (1, k − 1) at (q, k) = (17, 4) and at q = 19 for any k.The search covered 3 ≤ k ≤ n − 3 and did not provide an explicit construction.Source: C. Length ≈q/2 Codes with “Exotic… · p. 5
  • The failure of (t, h) = (1, k − 1) is expected for sufficiently high k from Lemma 13 and the asymptotic upper bounds on M(k, Fq) in, while long codes for other pairs are described as surprising.Source: C. Length ≈q/2 Codes with “Exotic… · p. 5

D. Counting Twisted MDS Codes · VIII. CONCLUSION

Twisted Reed–Solomon codes form a new class of Fq-linear codes containing many non-GRS MDS codes. The paper presents explicit subclasses, counts small-field examples, and describes decoding methods.

D. Counting Twisted MDS Codes

  • Table II enumerates MDS twisted codes and their equivalence classes for q ≤13; for (q, n, k) = (13, 7, 4), each class arises from ≈1200 parameter choices on average.The passage suggests algebraic symmetries may explain the multiplicity, leaving this as a question to investigate.Source: D. Counting Twisted MDS Codes · p. 5
  • Most MDS twisted codes are non-GRS, and in most cases codes of length q −1 can be constructed for k ∈{3, n −3}.Source: D. Counting Twisted MDS Codes · p. 5
  • Apart from Glynn’s code and its dual, the passage identifies one new code of length q: (q, n, k) = (8, 8, 5), equivalent to a Roth–Lempel code.It can be constructed as C5(α, 1, 4, 1) with α = F8 ∪{∞} \ {1}.Source: D. Counting Twisted MDS Codes · p. 5
  • Guessing the hook coefficient ah and applying an [n, k]-RS decoder to the adjusted received word requires q RS-decoder runs over Fq.The approach also supports errors, erasures, soft-decision, and list decoding.Source: D. Counting Twisted MDS Codes · p. 5
  • An [n, k] twisted code over Fq decodes up to half its minimum distance in complexity O∼(qn).Source: D. Counting Twisted MDS Codes · p. 5
  • Even when a twisted code is not MDS, collecting outputs across guesses of ah gives a list decoder up to (n −k + 1)/2, containing the correct codeword within the RS decoding radius.Source: D. Counting Twisted MDS Codes · p. 5

VIII. CONCLUSION

  • The (∗)-twisted and (+)-twisted subclasses construct MDS codes of length at least q/2 for any field size; for most field sizes, most are non-GRS.Computer searches also suggest many other, longer MDS non-GRS twisted RS codes.Source: §VIII · p. 5

Related papers

Loading 1701.01295v2…