Source-linked AI summary
Optimal locally repairable codes of distance $3$ and $4$ via cyclic codes
Yuan Luo, Chaoping Xing, Chen Yuan
TL;DR
Optimal locally repairable codes have faced length constraints in prior constructions, motivating the search for codes longer than q + 1. This paper uses cyclic codes with carefully chosen generator and parity-check polynomials to construct optimal codes of distances 3 and 4 with unbounded length independent of alphabet size.
Problem
Prior constructions imposed length restrictions, and the paper asks whether optimal codes can exceed q + 1 in length or have unbounded length at constant distance.
Source: §1.3 · p. 2Method
The paper constructs cyclic locally repairable codes by carefully choosing generator and parity-check polynomials.
Source: §1.2 · p. 2Results
The paper establishes optimal locally repairable codes of distances 3 and 4 with unbounded lengths independent of alphabet size.
Source: §1.2 · p. 2Takeaways & Limitations
The construction gives unbounded-length optimal codes for distances 3 and 4, addressing the open question for those distances.
Source: §1.2 · p. 2
Abstract
from arXiv · showhide
Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code {\it optimal} if it achieves the Singleton-type bound). In the breakthrough work of \cite{TB14}, several classes of optimal locally repairable codes were constructed via subcodes of Reed-Solomon codes. Thus, the lengths of the codes given in \cite{TB14} are upper bounded by the code alphabet size $q$. Recently, it was proved through extension of construction in \cite{TB14} that length of $q$-ary optimal locally repairable codes can be $q+1$ in \cite{JMX17}. Surprisingly, \cite{BHHMV16} presented a few examples of $q$-ary optimal locally repairable codes of small distance and locality with code length achieving roughly $q^2$. Very recently, it was further shown in \cite{LMX17} that there exist $q$-ary optimal locally repairable codes with length bigger than $q+1$ and distance propositional to $n$. Thus, it becomes an interesting and challenging problem to construct new families of $q$-ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we construct a class of optimal locally repairable codes of distance $3$ and $4$ with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen.
1 Introduction
Optimal locally repairable codes meet a Singleton-type bound, but prior constructions had restrictions on length or alphabet size. This paper uses cyclic codes to construct optimal codes of distances 3 and 4 with unbounded length.
1.1 Known results
- Earlier constructions reached length at most q or q + 1, while later examples included lengths exceeding q + 1 and distances proportional to length.The cited work gave a few examples with specific parameters; [8] used elliptic curves.Source: §1.1 · p. 2
1.2 Our result
- The paper constructs optimal cyclic locally repairable codes of distances 3 and 4 whose lengths are unbounded and independent of alphabet size.The authors state that the theorem’s conditions are easy to satisfy.Source: §1.2 · p. 2
1.3 Open problems
- The introduction asks whether optimal codes can combine length much greater than q with distance proportional to length, or have unbounded length for every constant distance.It presents these as two open problems.Source: §1.3 · pp. 2–3
1.4 Organization of the paper
- The paper reviews locally repairable codes and cyclic codes in Section 2, then proves its main theorem and gives a length-2(q − 1), distance-4 construction in Section 3.Source: §1.4 · p. 3
2 Preliminaries
The preliminaries define locality through coordinate recovery and set the parameters used for locally repairable codes. They introduce cyclic codes and properties used later, including their dimension, automorphisms, duals, and a root-based distance bound.
2.1 Locally repairable codes
- Locality r requires each coordinate to be recoverable from at most r other coordinates, and the paper considers linear [n, k, d]q codes with that locality.The formal definition requires a recovery set of size at most r that distinguishes every possible value of the coordinate.Source: §2.1 · p. 3
2.2 Cyclic codes
- A q-ary cyclic code is an ideal in Fq[x]/(x^n −1), generated by a divisor g(x), with dimension n − deg(g(x)).A polynomial is a codeword exactly when it is divisible by g(x), equivalently when it vanishes at every root of g(x).Source: §2.2 · p. 3
- The dual of a cyclic code generated by g(x) is generated by the reciprocal of h(x), where h(x)=(x^n−1)/g(x); the two codes in Lemma 2.1(i) are equivalent.These are stated as standard cyclic-code facts, without proof.Source: §2.2 · p. 3
- If consecutive powers β^t through β^(t+δ−2) are roots of a cyclic code's generator polynomial, its minimum distance is at least δ.Here β is an nth primitive root of unity; the passage states this as Lemma 2.1(iii).Source: §2.2 · p. 4
- For a cyclic code, the cyclic shift is an automorphism, making the code transitive across coordinate positions.Transitivity means an automorphism can map any coordinate position to any other.Source: §2.2 · p. 4
3 Constructions
The section develops cyclic locally repairable codes using a general locality criterion and carefully selected generator polynomials. It establishes distance-3 and distance-4 constructions, including a family of length 2(q−1).
3.1 A general result
- Under n|(q−1) and (r+1)|n, Example 3.2 gives optimal cyclic q-ary locally repairable codes for every 1≤d≤n.Lemma 3.1 supplies the locality criterion: a q-ary transitive linear code with dual distance at most r+1 has locality r; the construction uses generator roots to ensure distance.Source: §3.1 · pp. 4–5
3.2 Proof of part (i) of Theorem 1.1
- For part (i), the constructed cyclic code has locality r and minimum distance exactly 3, meeting the Singleton-type bound.The proof establishes locality through a dual-codeword of weight r+1 and distance through the generator polynomial's roots.Source: §3.2 · pp. 6–7
3.3 Proof of part (ii) of Theorem 1.1
- The minimum distance of C is at most 4 by bound (1); locality r is established by showing C⊥ has Hamming distance at most r+1, using a word of weight r+1.Source: §3.3 · pp. 7–8
3.4 A locally reparable codes of length 2(q −1) and distance 4
- If r+1 divides 2(q−1), an optimal q-ary locally repairable code exists with length 2(q−1), distance 4, and locality r+1.The proof verifies that C meets the Singleton-type bound (1).Source: §3.4 · p. 8