Search

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters $[n,k,d]$ and the list size $L$. $L$ -MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed–Solomon (GRS) codes. [ABSTRACT FROM AUTHOR]

An $(n,r,h,a,q)$ -Local Reconstruction Code (LRC) is a linear code over $\mathbb {F}_{q}$ of length $n$ , whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies ‘ $a$ ’ local parity checks to recover from ‘ $a$ ’ erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience—namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to ‘ $a$ ’ erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$ -MR LRCs with field size $q$ bounded by $\left ({O\left ({\max \{r,n/r\}}\right)}\right)^{\min \{h,r-a\}}$. This significantly improves upon known constructions in many practically relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=\Theta (\sqrt {n})$ , $r-a=\Theta (\sqrt {n})$ and $h$ is a fixed constant with $h \leqslant a+2$ , achieving the optimal field size of $\Theta _{h}(n^{h/2})$. Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory. [ABSTRACT FROM AUTHOR]

A large class of MDS linear codes is constructed. These codes are endowed with an efficient decoding algorithm. Both the definition of the codes and the design of their decoding algorithm only require from Linear Algebra methods, making them fully accessible for everyone. Thus, the first part of the paper develops a direct presentation of the codes by means of parity-check matrices, and the decoding algorithm rests upon matrix and linear maps manipulations. The somewhat more sophisticated mathematical context (non-commutative rings) needed for the proof of the correctness of the decoding algorithm is postponed to the second part. A final section locates the Reed-Solomon skew-differential codes introduced here within the general context of codes defined by means of skew polynomial rings. [ABSTRACT FROM AUTHOR]

It is well known that constructing codes with good parameters is one of the most important and fundamental problems in coding theory. Though a great many of good codes have been produced, most of them are defined over alphabets of sizes equal to prime powers. In this article, we provide a new explicit construction of $(q+1)$ -ary nonlinear codes via rational function fields, where $q$ is a prime power. Our codes are constructed by evaluations of rational functions at all rational places (including the place of “infinity”) of the rational function field. Compared to the rational algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes with length $q+1$ over the alphabet $\mathbb {F}_{q}\cup \{\infty \}$. As a result, our codes have reasonable parameters as they are rather close to the Singleton bound. Furthermore, our codes have better parameters than those obtained from MDS codes via code alphabet restriction or extension. Amazingly, an efficient decoding algorithm can be provided for our codes. [ABSTRACT FROM AUTHOR]

Multishot network coding is considered in a worst-case adversarial setting in which an omniscient adversary with unbounded computational resources may inject erroneous packets in up to $t$ links, erase up to $\rho $ packets, and wire-tap up to $\mu $ links, all throughout $\ell $ shots of a linearly-coded network. Assuming no knowledge of the underlying linear network code (in particular, the network topology and underlying linear code may be random and change with time), a coding scheme achieving zero-error communication and perfect secrecy is obtained based on linearized Reed-Solomon codes. The scheme achieves the maximum possible secret message size of $\ell n^\prime - 2t - \rho - \mu $ packets for coherent communication, where $n^\prime $ is the number of outgoing links at the source, for any packet length $m \geq n^\prime $ (largest possible range). By lifting this construction, coding schemes for non-coherent communication are obtained with information rates close to optimal for practical instances. The required field size is $q^{m} $ , where $q > \ell $ , thus $q^{m} \approx \ell ^{n^\prime } $ , which is always smaller than that of a Gabidulin code tailored for $\ell $ shots, which would be at least $2^{\ell n^\prime } $. A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length $n = \ell n^\prime $ , and which can be adapted to handle not only errors but also erasures, wire-tap observations and non-coherent communication. Combined with the obtained field size, the given decoding complexity is of $\mathcal {O}(n^{\prime 4} \ell ^{2} \log (\ell)^{2}) $ operations in $\mathbb {F}_{2} $ , whereas the most efficient known decoding algorithm for a Gabidulin code has a complexity of $\mathcal {O}(n^{\prime 3.69} \ell ^{3.69} \log (\ell)^{2}) $ operations in $\mathbb {F}_{2} $ , assuming a multiplication in a finite field $\mathbb {F} $ costs about $\log (|\mathbb {F}|)^{2} $ operations in $\mathbb {F}_{2} $. [ABSTRACT FROM AUTHOR]

An [ n , k , d ] linear code is said to be maximum distance separable (MDS) or almost maximum distance separable (AMDS) if d = n − k + 1 or d = n − k , respectively. If a code and its dual code are both AMDS, then the linear code is called a near maximum distance separable (NMDS) code. NMDS codes correspond to some interesting objects in finite geometry and have nice applications in cryptography. The NMDS codes constructed from elliptic curves are referred as elliptic curve NMDS codes. In this paper, by adding two suitable columns to the generator matrices of famous Reed-Solomon codes, we can obtain two families of NMDS codes with parameters [ q + 3 , 4 , q − 1 ] q (q is a prime power with gcd ⁡ (q − 1 , 3) = 1) and [ 2 m + 3 , 5 , 2 m − 2 ] 2 m respectively. These NMDS codes are shown to be linearly inequivalent to elliptic curve NMDS codes. Besides, the weight enumerators and locality of these NMDS codes are completely determined. It turns out that the resultant NMDS codes and their dual codes are mostly distance-optimal and dimension-optimal locally recoverable codes. [ABSTRACT FROM AUTHOR]

Twisted generalized Reed-Solomon codes are the generalization of generalized Reed-Solomon codes, due to their good algebraic structure and applications in cryptography, which have been widely studied in recent years. As a general algebraic decoding method for linear codes, the error-correcting pair exists in many classical linear codes. In this paper, we extend the error-correcting pair to twisted generalized Reed-Solomon codes. For twisted generalized Reed-Solomon codes with twist 1 or 2, we constructively show that the existence of the error-correcting pair. Moreover, we introduce the corresponding decoding procedure of twisted generalized Reed-Solomon codes by ℓ -error-correcting pairs and give several examples. [ABSTRACT FROM AUTHOR]

Combinatorial structures called stopping sets are useful in analyzing the performance of a linear code when coupled with an iterative decoding algorithm over an erasure channel. In this paper, we consider stopping sets of Hermitian codes. [ABSTRACT FROM PUBLISHER]

Burst errors are a type of distortion in many data communications and data storage channels. In this paper, we consider the list decodability of codes for single burst error case and phased-burst error case independently. Firstly, we analyze the list decodability of random codes, and we show that the burst list decoding radius and the rate of random codes achieve the Singleton bound and the Gilbert-Varshamov bound for single case and phased case, respectively. Second, we illustrate that cyclic codes and algebraic geometry codes are good burst list-decodable codes for single case and phased case, respectively. [ABSTRACT FROM AUTHOR]

It is shown that interleaved Reed–Solomon codes can be list-decoded for burst errors while attaining the generalized Reiger bound for list decoding. A respective decoding algorithm is presented that is (significantly) more efficient than a burst list decoder for a noninterleaved Reed–Solomon code with comparable parameters. Finally, it is shown through counterexamples that unlike the special case of Reed–Solomon codes, interleaving does not always preserve the list decoding properties of the constituent code. [ABSTRACT FROM PUBLISHER]

Assuming that we have a soft-decision list decoding algorithm of a linear code, a new hard-decision list decoding algorithm of its repeated code is proposed in this article. Although repeated codes are not used for encoding data, due to their parameters, we show that they have a good performance with this algorithm. We compare, by computer simulations, our algorithm for the repeated code of a Reed-Solomon code against a decoding algorithm of a Reed-Solomon code. Finally, we estimate the decoding capability of the algorithm for Reed-Solomon codes and show that performance is somewhat better than our estimates. [ABSTRACT FROM AUTHOR]

Practically good error-correcting codes should have good parameters and efficient decoding algorithms. Some algebraically defined good codes, such as cyclic codes, Reed–Solomon codes, and Reed–Muller codes, have nice decoding algorithms. However, many optimal linear codes do not have an efficient decoding algorithm except for the general syndrome decoding which requires a lot of memory. Therefore, a natural question to ask is which optimal linear codes have an efficient decoding. We show that two binary optimal [ 36 , 19 , 8 ] linear codes and two binary optimal [ 40 , 22 , 8 ] codes have an efficient decoding algorithm. There was no known efficient decoding algorithm for the binary optimal [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes. We project them onto the much shorter length linear [ 9 , 5 , 4 ] and [ 10 , 6 , 4 ] codes over G F (4) , respectively. This decoding algorithm, called projection decoding, can correct errors of weight up to 3. These [ 36 , 19 , 8 ] and [ 40 , 22 , 8 ] codes respectively have more codewords than any optimal self-dual [ 36 , 18 , 8 ] and [ 40 , 20 , 8 ] codes for given length and minimum weight, implying that these codes are more practical. [ABSTRACT FROM AUTHOR]