PaperlayerView exact revision on arXiv

Source-linked AI summary

New MDS Self-Dual Codes from Generalized Reed-Solomon Codes

Lingfei Jin, Chaoping Xing

arXiv:1601.04467v2cs.ITmath.IT

TL;DR

Existence of q-ary MDS self-dual codes at different lengths is a central question, and the even-q case is solved; this paper studies odd q. It constructs self-dual generalized Reed-Solomon codes and establishes existence for even lengths under several conditions on q and n.

  • Problem

    Determining which lengths admit q-ary MDS self-dual codes is a central problem; the even-q case is solved, while this paper focuses on odd q.

    Source: §I · p. 1

  • Method

    The paper constructs self-dual generalized Reed-Solomon codes using square-valued products of evaluation-point differences or a sufficient condition for a homogeneous system over F_q to have a nonzero solution over F_r when q=r².

    Source: Our techniques · p. 2

  • Results

    For even n, codes exist when q≡1 mod 4 is sufficiently large, when q=r² and n−1 divides q−1, or when q=r², r≡3 mod 4, and n=2tr with t≤(r−1)/2.

    Source: B. Our results · p. 2

  • Takeaways & Limitations

    The n−1 divisor condition extends, which required the stricter condition n−1 | r−1.

    Source: B. Our results · p. 2

Abstract

from arXiv · show

Both MDS and Euclidean self-dual codes have theoretical and practical importance and the study of MDS self-dual codes has attracted lots of attention in recent years. In particular, determining existence of $q$-ary MDS self-dual codes for various lengths has been investigated extensively. The problem is completely solved for the case where $q$ is even. The current paper focuses on the case where $q$ is odd. We construct a few classes of new MDS self-dual code through generalized Reed-Solomon codes. More precisely, we show that for any given even length $n$ we have a $q$-ary MDS code as long as $q\equiv1\bmod{4}$ and $q$ is sufficiently large (say $q\ge 2^n\times n^2)$. Furthermore, we prove that there exists a $q$-ary MDS self-dual code of length $n$ if $q=r^2$ and $n$ satisfies one of the three conditions: (i) $n\le r$ and $n$ is even; (ii) $q$ is odd and $n-1$ is an odd divisor of $q-1$; (iii) $r\equiv3\mod{4}$ and $n=2tr$ for any $t\le (r-1)/2$.

I. INTRODUCTION

The paper studies the existence of MDS self-dual codes, whose two component code classes have practical and theoretical relevance. It focuses on the unresolved odd-q case and constructs self-dual generalized Reed-Solomon codes.

I. INTRODUCTION

  • MDS codes achieve optimal parameters for correcting the maximal number of errors at a given code rate.They are also connected to combinatorial design and finite geometry.Source: §I · p. 1
  • Self-dual codes have applications in cryptography, including secret sharing, and in combinatorics.Generalized Reed-Solomon codes are MDS codes with wide practical applications.Source: §I · p. 1
  • The paper addresses existence of MDS self-dual codes for various lengths when q is odd, after the problem was solved for even q.The parameters of an MDS self-dual code are completely determined by its length.Source: §I · p. 1

A. Known results

Prior constructions of MDS self-dual codes use several approaches, but known existence results cover only sparse lengths beyond those summarized in Table I.

A. Known results

  • Existing constructions use constacyclic codes, orthogonal designs, and generalized Reed-Solomon codes.The paper notes that constacyclic duals can be determined from the code's generator polynomial.Source: A. Known results · p. 2
  • Beyond the results summarized in Table I, known MDS self-dual codes cover only some sparse lengths n.The cited passage refers to prior work –,,.Source: A. Known results · p. 2

B. Our results

The paper constructs MDS self-dual codes through generalized Reed-Solomon codes using two methods. It gives existence conditions for odd q, including square-field cases and a sufficiently large q condition for each even length.

B. Our results

  • For odd prime-power q and even positive n, the theorem asserts existence of a q-ary MDS self-dual code of length n when q and n satisfy any of its stated conditions.The supplied cases are (i) q ≡ 1 mod 4 and q ≥ 4n × n2; (iii) q = r2 and n − 1 divides q − 1; and (iv) q = r2, r ≡ 3 mod 4, and n = 2tr for any t ≤ (r − 1)/2.Source: B. Our results · p. 2
  • For any given even length n, the paper states that q ≡ 1 mod 4 suffices when q is sufficiently large.The remark gives the bound q ≥ 4n × n2 as printed in the passage.Source: B. Our results · p. 2
  • The square-field divisor condition extends prior work that required the stricter condition (n − 1) | (r − 1).The paper also contrasts its generalized Reed-Solomon construction with the orthogonal-design approach in.Source: B. Our results · p. 2
  • The first construction method chooses distinct field elements so that each product of pairwise differences is a square in Fq.The second seeks a sufficient condition for a homogeneous system over Fq to have a nonzero solution over Fr when q = r^2.Source: Our techniques · p. 2
  • The paper's organization describes studying generalized Reed-Solomon codes, their duals, and homogeneous systems before deriving several classes of MDS self-dual codes.Source: Organization of the paper · p. 2

II. PRELIMINARIES

The preliminaries define generalized Reed–Solomon codes and establish their MDS and dual-code properties. They give self-duality criteria based on evaluation-point products and, over square fields, on solutions of a homogeneous system.

II. PRELIMINARIES

  • GRS codes evaluate degree-at-most-k−1 polynomials at distinct field elements with nonzero multipliers, and have parameters [n,k,n−k+1] as MDS codes.Their duals are also GRS codes.Source: §II · p. 3
  • The dual of GRS_k(a,1) is GRS_{n−k}(a,u), while the extended code GRS_{(q+1)/2}(a,1,∞) is self-dual for odd q.The dual-code result follows by orthogonality and complementary dimensions.Source: §II · pp. 3–4
  • For even n, GRS_{n/2}(a,v) is MDS self-dual when each inverse product of evaluation-point differences is a square multiplier.The stated condition is that the inverse product for each α_i equals v_i².Source: §II · p. 4
  • When q=r², a nonzero solution of A_a x^T=0 over F_r yields an MDS self-dual GRS code, and solution existence is characterized by Frobenius invariance or row equivalence of A and A^(r).The system has an (n−1)×n coefficient matrix over F_{r²}; its nonzero F_r solution supplies square multipliers.Source: §II · pp. 4–5

III. MDS SELF-DUAL CODES

Section III establishes existence conditions for MDS self-dual codes and gives a construction based on sets with pairwise square differences. The results include odd-q length conditions and constructions over square-size fields.

III. MDS SELF-DUAL CODES

Loading 1601.04467v2…