Search

This paper considers the natural extension of locally recoverable codes (LRC) to the case of ${t} > 1$ erased symbols. While several approaches have been proposed for the handling of multiple erasures, in the approach considered here, the t erased symbols are recovered in succession, each time contacting at most r other symbols for assistance. Under the local-recovery constraint, this sequential approach is the most general and hence offers the maximum possible code rate. We characterize the rate of an LRC with sequential recovery for any ${r} \geq 3$ and any t, by first deriving an upper bound on the code rate and then constructing a binary code achieving this optimal rate. The upper bound derived here proves an earlier conjecture. Our approach permits us to deduce the structure of the parity-check matrix of a rate-optimal LRC with sequential recovery. The derived structure of parity-check matrix leads to a graphical description of the code used in code construction. A subclass of binary codes that are both rate and block-length optimal, are shown to correspond to certain regular graphs known as Moore graphs, that have the smallest number of vertices for a given girth. A connection with Tornado codes is also made. [ABSTRACT FROM AUTHOR]

The Z2s-additive codes are subgroups of Zn2s, and can be seen as a generalization of linear codes over Z2 and Z4. A Z2s-linear Hadamard code is a binary Hadamard code which is the Gray map image of a Z2s-additive code. It is known that either the rank or the dimension of the kernel can be used to give a complete classification for the Z4-linear Hadamard codes. However, when s > 2, the dimension of the kernel of Z2s-linear Hadamard codes of length 2t only provides a complete classification for some values of t and s. In this paper, the rank of these codes is computed for s = 3. Moreover, it is proved that this invariant, along with the dimension of the kernel, provides a complete classification, once t ≥ 3 is fixed. In this case, the number of nonequivalent such codes is also established. [ABSTRACT FROM AUTHOR]

We provide polylog sparse quantum codes for correcting the Erasure channel arbitrarily close to the capacity. Specifically, we provide the $[[n, k, d]]$ quantum stabilizer codes that correct for the erasure channel arbitrarily close to the capacity if the erasure probability is at least 0.33 and with a generating set $\langle S_{1}, S_{2}, \cdots {} S_{n-k} \rangle $ such that $|S_{i}|\leq {\mathrm{ log}} ^{2+\zeta }(n)$ for all $i$ and for any $\zeta > 0$ with high probability. In this paper, we show that the result of Delfosse et al. is tight: one can construct capacity approaching codes with weight almost $O(1)$. [ABSTRACT FROM AUTHOR]

Bent functions, or equivalently, Hadamard difference sets in the elementary Abelian group (${\mathrm {GF}}(2^{2m}), $ +), have been employed to construct symmetric and quasi-symmetric designs having the symmetric difference property. The main objective of this paper is to use bent vectorial functions for a construction of a two-parameter family of binary linear codes that do not satisfy the conditions of the Assmus–Mattson theorem, but nevertheless hold 2-designs. A new coding-theoretic characterization of bent vectorial functions is presented. [ABSTRACT FROM AUTHOR]

For any prime power $q$ , Mori and Tanaka introduced a family of $q$ -ary polar codes based on the $q\,\,\times \,\,q$ Reed–Solomon polarization kernels. For transmission over a $q$ -ary erasure channel, they also derived a closed-form recursion for the erasure probability of each effective channel. In this paper, we use that expression to analyze the finite-length scaling of these codes on the $q$ -ary erasure channel with erasure probability $\epsilon \in (0,1)$. Our primary result is that for any $\gamma >0$ and $\delta >0$ , there is a $q_{0}$ , such that for all $q\geq q_{0}$ , the fraction of effective channels with erasure rate at most $N^{-\gamma }$ is at least $1-\epsilon -O(N^{-1/2+\delta })$ , where $N=q^{n}$ is the blocklength. Since this fraction cannot be larger than $1-\epsilon -O(N^{-1/2})$ , this establishes near-optimal finite-length scaling for this family of codes. Our approach can be seen as an extension of a similar analysis for binary polar codes by Hassani, Alishahi, and Urbanke. A similar analysis is also considered for $q$ -ary polar codes with $m \times m$ polarizing matrices. This separates the effect of the alphabet size from the effect of the matrix size. If the polarizing matrix at each stage is drawn independently and uniformly from the set of invertible $m \times m$ matrices, then the linear operator associated with the Lyapunov function analysis can be written in the closed form. To prove near-optimal scaling for polar codes with fixed $q$ as $m$ increases, however, two technical obstacles remain. Thus, we conclude by stating two concrete mathematical conjectures that, if proven, would imply near-optimal scaling for fixed $q$. [ABSTRACT FROM AUTHOR]

In this paper, we mainly study quaternary linear codes and their binary subfield codes. First we obtain a general explicit relationship between quaternary linear codes and their binary subfield codes in terms of generator matrices and defining sets. Second, we construct quaternary linear codes via simplicial complexes and determine the weight distributions of these codes. Third, the weight distributions of the binary subfield codes of these quaternary codes are also computed by employing the general characterization. Furthermore, we present two infinite families of optimal linear codes with respect to the Griesmer Bound, and a class of binary almost optimal codes with respect to the Sphere Packing Bound. We also need to emphasize that we obtain at least 9 new quaternary linear codes. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the combinatorial error model of Mazumdar et al. that models errors in high-density magnetic recording caused by lack of knowledge of grain boundaries in the recording medium. We present new upper bounds on the cardinality/rate of binary block codes that correct errors within this model. All our bounds, except for one, are obtained using combinatorial arguments based on hypergraph fractional coverings. The exception is a bound derived via an information-theoretic argument. Our bounds significantly improve upon existing bounds from the prior literature. [ABSTRACT FROM PUBLISHER]

Binary almost instantaneous fixed-to-variable length (AIFV) codes are lossless codes that generalize the class of instantaneous fixed-to-variable length codes. The code uses two code trees and assigns source symbols to incomplete internal nodes as well as to leaves. AIFV codes are empirically shown to attain better compression ratio than Huffman codes. Nevertheless, an upper bound on the redundancy of optimal binary AIFV codes is only known to be 1, which is the same as the bound of Huffman codes. In this paper, the upper bound is improved to 1/2, which is shown to coincide with the worst-case redundancy of the codes. Along with this, the worst-case redundancy is derived for sources with p\max \geq 1 /2, where p\max is the probability of the most likely source symbol. In addition, we propose an extension of binary AIFV codes, which use $m$ code trees and allow at most $m$ -bit decoding delay. We show that the worst-case redundancy of the extended binary AIFV codes is $1/m$ for $m \leq 4$ . [ABSTRACT FROM AUTHOR]

Following the very recent studies on \mathbb Z2\mathbb Z4 -additive codes, \mathbb Z2\mathbb Z2[u] -linear codes have been introduced by Aydogdu et al. In this paper, we introduce and study the algebraic structure of cyclic, constacyclic codes and their duals over the R -module \mathbb {Z}_{2}^\alpha R^\beta where R=\mathbb {Z}_{2}+u\mathbb {Z}_{2}=\left \{{0,1,u,u+1}\right \} is the ring with four elements and u^2=0 . We determine the generating independent sets and the types and sizes of both such codes and their duals. Finally, we present a bound and an optimal family of codes attaining this bound and also give some illustrative examples of binary codes that have good parameters which are obtained from the cyclic codes in \mathbb Z_2^\alpha R^\beta . [ABSTRACT FROM AUTHOR]

The noise model of deletions poses significant challenges in coding theory, with basic questions like the capacity of the binary deletion channel still being open. In this paper, we study the harder model of worst case deletions, with a focus on constructing efficiently decodable codes for the two extreme regimes of high-noise and high-rate. Specifically, we construct polynomial-time decodable codes with the following tradeoffs (for any \varepsilon > 0 ): 1) codes that can correct a fraction 1- \varepsilon of deletions with rate \mathop \mathrm poly\nolimits ( \varepsilon ) over an alphabet of size \mathop \mathrm poly\nolimits (1/ \varepsilon ) ; 2) binary codes of rate 1-\tilde O(\sqrt \varepsilon ) that can correct a fraction $ \varepsilon $ of deletions; and 3) Binary codes that can be list-decoded from a fraction (1/2- \varepsilon )$ of deletions with rate \mathop {\mathrm {poly}}\nolimits ( \varepsilon ) . This paper gives the first efficient constructions which meet the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate approaching 1 over a fixed alphabet. The above-mentioned results bring our understanding of deletion code constructions in these regimes to a similar level as worst case errors. [ABSTRACT FROM PUBLISHER]

Given n items with at most d of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called d -disjunct if the Boolean sum of arbitrary d columns does not contain another column not in this collection. Let T(d) denote the minimal t , such that there exists a t\times n\,\,d -disjunct matrix with n>t and was conjectured that T(d)\ge (d+1)^{2} . In this paper, we narrow the gap by proving T(d)/d^{2}\ge (15+\sqrt {33})/24$ , a quantity in [6/7,7/8]. [ABSTRACT FROM PUBLISHER]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some $t$ -intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed. [ABSTRACT FROM AUTHOR]

Let $n (>3)$ be a prime number and ${\mathbb {F}}_{2^{n}}$ a finite field of $2^{n}$ elements. Let $L ={\mathbb {F}}_{2^{n}}\cup \{\infty \}$ be the support set and $g(x)$ an irreducible polynomial of degree 6 over ${\mathbb {F}}_{2^{n}}$. In this paper, we obtain an upper bound on the number of extended irreducible binary Goppa codes $\Gamma (L, g)$ of degree 6 and length $2^{n}+1$. [ABSTRACT FROM AUTHOR]

For locally repairable codes (LRCs), Cadambe and Mazumdar derived the first field-dependent parameter bound, known as the C-M bound. However, the C-M bound depends on an undetermined parameter $ {k}^{({q})}_{{\textbf {opt}}}({n}, {d})$. In this paper, a sphere-packing approach is developed for upper bounding the parameter $ {k}$ for $[ {n}, {k}, {d}]$ linear LRCs with locality $ {r}$. When restricted to the binary field, three upper bounds (i.e., Bound A, Bound B, and Bound C) are derived in an explicit form. More specifically, Bound A holds under the hypothesis that the local repair groups are disjoint and of equal size. Comparing with previous bounds obtained under the same hypothesis, Bound A either covers them as special cases or has an advantage due to its explicit form. Then, the hypothesis is removed in Bound B and Bound C. As the price for explicit form, Bound B specially holds for $ {d}\geq \text {5}$ and Bound C for $ {r}=\textbf {2}$. Through specific comparisons, we show that Bound B and Bound C both tend to outperform the C-M bound, as $ {n}$ goes large. Moreover, a family of binary linear LRCs with $ {d}\geq \textbf {6}$ attaining Bound B are constructed and later extended to a wider range of parameters by a shortening technique. Lastly, most of the bounds and constructions are extended to $ {q}$ -ary LRCs. [ABSTRACT FROM AUTHOR]

Marton’s inner bound is the best known achievable rate region for a general two-receiver discrete memoryless broadcast channel. In this paper, we establish improved bounds on the cardinalities of the auxiliary random variables appearing in this inner bound to the true rate region. We combine a perturbation technique, along with a representation using concave envelopes of information-theoretic functions that involve the use of auxiliary random variables, to achieve this improvement. The new cardinality bounds lead to a proof that a randomized-time-division strategy achieves every rate triple in Marton’s region for binary input broadcast channels. This extends the result by Hajek and Pursley which showed that the Cover-van der Muelen region was exhausted by the randomized-time-division strategy. [ABSTRACT FROM AUTHOR]

The square $C^{*2}$ of a linear error correcting code $C$ is the linear code spanned by the component-wise products of every pair of (non-necessarily distinct) words in $C$. Squares of codes have gained attention for several applications mainly in the area of cryptography, and typically in those applications, one is concerned about some of the parameters (dimension and minimum distance) of both $C^{*2}$ and $C$. In this paper, motivated mostly by the study of this problem in the case of linear codes defined over the binary field, squares of cyclic codes are considered. General results on the minimum distance of the squares of cyclic codes are obtained, and constructions of cyclic codes $C$ with a relatively large dimension of $C$ and minimum distance of the square $C^{*2}$ are discussed. In some cases, the constructions lead to codes $C$ such that both $C$ and $C^{*2}$ simultaneously have the largest possible minimum distances for their length and dimensions. [ABSTRACT FROM AUTHOR]

Linear complementary dual (LCD) cyclic codes were referred historically to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In particular, it has been shown that binary LCD codes play an important role in implementations against side-channel attacks and fault injection attacks. In this paper, we first present a new characterization of binary LCD codes in terms of their orthogonal or symplectic basis. Using such a characterization, we solve a conjecture proposed by Galvez et al. on the minimum distance of binary LCD codes. Next, we consider the action of the orthogonal group on the set of all LCD codes, determine all possible orbits of this action, derive simple closed formulas of the size of the orbits, and present some asymptotic results on the size of the corresponding orbits. Our results show that almost all binary LCD codes are odd-like codes with odd-like duals, and about half of $q$ -ary LCD codes have orthonormal basis, where $q$ is a power of an odd prime. [ABSTRACT FROM AUTHOR]

The study of regenerating codes has advanced tremendously in recent years. However, most known constructions require large field size and, hence, may be hard to implement in practice. By restructuring a code construction by Rashmi et al., we obtain two explicit families regenerating codes. These codes approach the cut-set bound as the reconstruction degree increases and may be realized over any given finite field if the file size is large enough. Essentially, these codes constitute a constructive proof that the cut-set bound does not imply a field size restriction, unlike some known bounds for ordinary linear codes. The first construction attains the cut-set bound at the MBR point asymptotically for all parameters, whereas the second one attains the cut-set bound at the MSR point asymptotically for low-rate parameters. Even though these codes require a large file size, this restriction is trivially satisfied in most conceivable distributed storage scenarios, that are the prominent motivation for regenerating codes. [ABSTRACT FROM AUTHOR]

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. [ABSTRACT FROM AUTHOR]

The most common decision criteria for decoding are maximum likelihood decoding and nearest neighbor decoding. It is well known that maximum likelihood decoding coincides with nearest neighbor decoding with respect to the Hamming metric on the binary symmetric channel. In this paper, we study channels and metrics for which those two criteria do and do not coincide for general codes. [ABSTRACT FROM AUTHOR]

In this paper, a generic construction of codebooks based on binary codes is introduced. With this generic construction, a few previous constructions of optimal codebooks are extended, and a new class of codebooks almost meeting the Levenshtein bound is presented. Exponentially many codebooks meeting or almost meeting the Levenshtein bound from binary codes are obtained in this paper. The codebooks constructed in this paper have alphabet size 4. As a byproduct, three bounds on the parameters of binary codes are derived. [ABSTRACT FROM PUBLISHER]

Bazzi and Mitter showed that binary dihedral group codes are asymptotically good. In this paper we prove that the dihedral group codes over any finite field with strong duality property are asymptotically good. If the characteristic of the field is even, self-dual dihedral group codes are asymptotically good. If the characteristic of the field is odd, maximal self-orthogonal dihedral group codes and LCD dihedral group codes are asymptotically good. [ABSTRACT FROM AUTHOR]

The parameters of a q-ary MDS Euclidean self-dual codes are completely determined by its length and the construction of MDS Euclidean self-dual codes with new length has been widely investigated in recent years. In this paper, we give a further study on the construction of MDS Euclidean self-dual codes via generalized Reed-Solomon (GRS) codes and their extended codes. The main idea of our construction is to choose suitable evaluation points such that the corresponding (extended) GRS codes are Euclidean self-dual. Firstly, we consider the evaluation set consists of two disjoint subsets, one of which is based on the trace function, the other one is a union of a subspace and its cosets. Then four new families of MDS Euclidean self-dual codes are constructed. Secondly, we give a simple but useful lemma to ensure that the symmetric difference of two intersecting subsets of finite fields can be taken as the desired evaluation set. Based on this lemma, we generalize our first construction and provide two new families of MDS Euclidean self-dual codes. Finally, by using two multiplicative subgroups and their cosets which have nonempty intersection, we present three generic constructions of MDS Euclidean self-dual codes with flexible parameters. Several new families of MDS Euclidean self-dual codes are explicitly constructed. [ABSTRACT FROM AUTHOR]

Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite significant efforts, progress on designing such codes has been lagging until recently, particularly compared to the detailed understanding of error-correcting codes for symbol substitution or erasure errors. This paper surveys the recent progress in designing efficient error-correcting codes over finite alphabets that can correct a constant fraction of worst-case insertions and deletions. Most state-of-the-art results for such codes rely on synchronization strings, simple yet powerful pseudo-random objects that have proven to be very effective solutions for coping with synchronization errors in various settings. This survey also includes an overview of what is known about synchronization strings and discusses communication settings related to error-correcting codes in which synchronization strings have been applied. [ABSTRACT FROM AUTHOR]

Guyon (Guyon J. Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging. Ann Appl Probab, 2007, 17: 1538-1569) introduced an important model for homogeneous bifurcating Markov chains indexed by a binary tree taking values in general state space and studied their limit theorems. The results were applied to detect cellular aging. In this paper, we define a discrete form of nonhomogeneous bifurcating Markov chains indexed by a binary tree and discuss the equivalent properties for them. The strong law of large numbers and the entropy ergodic theorem are studied for these Markov chains with finite state space. In contrast to previous work, we use a new approach to prove the main results of this paper. [ABSTRACT FROM AUTHOR]

The goal of this paper is to present constructions of high-rate nonbinary write-once memory (WOM) codes for multilevel flash memories. The constructions provided here are all based on the basic idea of mapping high-rate binary codebooks to nonbinary codebooks. The proposed codes maintain the same length and encoding complexity as their underlying binary constituents. We begin by presenting some elementary, yet rate-efficient constructions. Afterward, we consider a high-rate two-write WOM-code defined over an alphabet of size four. In addition, we consider the application of our constructions to the creation of fixed-rate WOM codes. The constructions presented in this paper improve upon the best-known code constructions for certain code lengths. [ABSTRACT FROM AUTHOR]

In this paper, we present an algebraic construction of binary codes through rational function fields. We make use of certain multiplicative group of rational functions for our construction. In particular, the point at infinity can be employed in our construction to get codes of length up to $q+1$ , where $q$ is the ground field size. As a result, several new binary constant-weight codes are found and many new binary nonlinear codes are presented. [ABSTRACT FROM PUBLISHER]

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate $R$ and minimum distance $\delta $ of a binary code. The best known tradeoff is the Gilbert–Varshamov bound, and says that for every $\delta \in (0, 1/2)$ , there are codes with minimum distance $\delta $ and rate $R = {R_{\mathsf {GV}}}(\delta) > 0$ (for a certain simple function ${R_{\mathsf {GV}}}(\cdot)$ ). In this paper, we show that the Gilbert–Varshamov bound can be achieved by codes, which support local error-detection and error-correction algorithms. Specifically, we show the following results. 1) Local testing: for all $\delta \in (0,1/2)$ and all $R < {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally testable with $\mathsf {quasipolylog}(n)$ query complexity. 2) Local correction: for all $\epsilon > 0$ , for all $\delta < 1/2$ sufficiently large, and all $R < (1-\epsilon) {R_{\mathsf {GV}}}(\delta)$ , there exist codes with length $n$ , rate $R$ , and minimum distance $\delta $ that are locally correctable from $({\delta }/{2}) - o(1)$ fraction errors with $O(n^{\epsilon })$ query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen’s random concatenation technique and the best known locally testable codes by Kopparty et al. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami–Sudan–Indyk list decoding strategy for concatenated codes, Alon–Edmonds–Luby distance amplification, and the local list-decodability, local list-recoverability, and local testability of Reed–Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code. [ABSTRACT FROM AUTHOR]

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write $n$ incoming packets and read $k$ outgoing packets while using $m$ memory banks, each able to write and read one packet per time unit. Each set of $n$ packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of $k$ packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case $n=k$ . [ABSTRACT FROM AUTHOR]

The Johnson-type upper bound on the maximum size of a code of length n , distance d=2w-1 , and constant composition \overline w is \lfloor \dfrac \vphantom R^.nw1\rfloor , where w is the total weight and w_{1} is the largest component of {\overline {w}} . Recently, Chee et al. proved that this upper bound can be achieved for all constant-composition codes of sufficiently large lengths. Let Nccc({\overline {w}}) be the smallest such length. The determination of Nccc({\overline {w}}) is trivial for binary codes. This paper provides a lower bound on Nccc({\overline {w}}) , which is shown to be tight for all ternary and quaternary codes by giving new combinatorial constructions. Consequently, by the refining method, we determine the values of Nccc({\overline {w}}) , for all $q$ -ary constant-composition codes, provided that 3w_{1}\geq w with finite possible exceptions. [ABSTRACT FROM AUTHOR]

Codes over Galois rings have been studied extensively during the last three decades. Negacyclic codes over \mathop \mathrm GR\nolimits (2^a,m) of length 2^s have been characterized: the ring \mathcal R2(a,m,-1)= {\mathrm{ GR}}(2^{a},m)[x]/\langle x^{2^{s}}+1\rangle is a chain ring. Furthermore, these results have been generalized to \lambda -constacyclic codes for any unit \lambda of the form 4z-1 , . In this paper, we study more general cases and investigate all cases, where {\mathcal{ R}}_{p}(a,m,\gamma) = {\mathrm{ GR}}(p^{a},m)[x]/\langle x^{p^{s}}-\gamma \rangle is a chain ring. In particular, the necessary and sufficient conditions for the ring {\mathcal{ R}}_{p}(a,m,\gamma) to be a chain ring are obtained. In addition, by using this structure we investigate all \gamma -constacyclic codes over \mathop {\mathrm {GR}}\nolimits (p^{a},m) when {\mathcal{ R}}_{p}(a,m,\gamma)$ is a chain ring. The necessary and sufficient conditions for the existence of self-orthogonal and self-dual \gamma$ -constacyclic codes are also provided. Among others, for any prime p$ , the structure of is used to establish the Hamming and homogeneous distances of $\gamma$ -constacyclic codes. [ABSTRACT FROM PUBLISHER]

Historically, LCD cyclic codes were referred to as reversible cyclic codes, which had applications in data storage. Due to a newly discovered application in cryptography, there has been renewed interest in LCD codes. In this paper, we explore two special families of LCD cyclic codes, which are both BCH codes. The dimensions and the minimum distances of these LCD BCH codes are investigated. [ABSTRACT FROM AUTHOR]

Binary codes over 2D arrays are very useful in data storage, where each array column represents a storage device or unit that may suffer failure. In this paper, we propose a new framework for probabilistic construction of codes on 2D arrays. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, and assuming a binary erasure channel in each failing column. For this model, we give code constructions and detailed analysis that allow sustaining a large number of column failures with graceful degradation in the fraction of erasures correctable in failing columns. Another advantage of the new framework is that it uses low-complexity iterative decoding. The key component in the analysis of the new codes is to analyze the decoding graphs induced by the failed columns, and infer the decoding performance as a function of the code design parameters, as well as the array size and failure parameters. A particularly interesting class of codes, called probabilistically maximum distance separable (MDS) array codes, gives fault-tolerance that is equivalent to traditional MDS array codes. The results also include a proof that the 2D codes outperform standard 1D low-density parity-check codes. [ABSTRACT FROM PUBLISHER]

A locally repairable code (LRC) is a linear code such that every code symbol can be recovered by accessing a small number of other code symbols. In this paper, we study bounds and constructions of LRCs from the viewpoint of parity-check matrices. Firstly, a simple and unified framework based on parity-check matrix to analyze the bounds of LRCs is proposed, and several new explicit bounds on the minimum distance of LRCs in terms of the field size are presented. In particular, we give an alternate proof of the Singleton-like bound for LRCs first proved by Gopalan et al. Some structural properties on optimal LRCs that achieve the Singleton-like bound are given. Then, we focus on constructions of optimal LRCs over the binary field. It is proved that there are only five classes of possible parameters with which optimal binary LRCs exist. Moreover, by employing the proposed parity-check matrix approach, we completely enumerate all these five classes of optimal binary LRCs attaining the Singleton-like bound in the sense of equivalence of linear codes. [ABSTRACT FROM AUTHOR]

The binary Hamming codes with parameters $[{2^{m}-1, 2^{m}-1-m, 3}]$ are perfect. Their extended codes have parameters $[{2^{m}, 2^{m}-1-m, 4}]$ and are distance-optimal. The first objective of this paper is to construct a class of binary linear codes with parameters $[{2^{m+s}+2^{s}-2^{m},2^{m+s}+2^{s}-2^{m}-2m-2,4}]$ , which have better information rates than the class of extended binary Hamming codes, and are also distance-optimal. The second objective is to construct a class of distance-optimal binary codes with parameters $[{2^{m}+2, 2^{m}-2m, 6}]$. Both classes of binary linear codes have new parameters. [ABSTRACT FROM AUTHOR]

In this paper, we solve the open problems raised in [8] and present some examples to illustrate the obtained results. Moreover, we work out the diophantine problem by Shi and Wang and then give the sufficient conditions for the nonexistence of two-Lee weight projective codes over \mathbb Z4 with type 4^k12^{k2} . [ABSTRACT FROM PUBLISHER]

In this paper, let n=2k and d=3\cdot 2^{k}-2 with k\geq 3 and \gcd (d,2^n-1)=1 . Based on some analysis of certain equations over finite fields and the number of codewords with Hamming weight five in Zetterberg code, the correlation distribution between a binary m -sequence of period 2^n-1 and its $d$ -decimation sequence is completely determined. This solves a ten-year-old open problem proposed by Dobbertin et al. [ABSTRACT FROM PUBLISHER]

Projective Reed–Muller codes were introduced by Lachaud in 1988 and their dimension and minimum distance were determined by Serre and Sørensen in 1991. In coding theory, one is also interested in the higher Hamming weights, to study the code performance. Yet, not many values of the higher Hamming weights are known for these codes, not even the second lowest weight (also known as the next-to-minimal weight) is completely determined. In this paper, we determine all the values of the next-to-minimal weight for the binary projective Reed–Muller codes, which we show to be equal to the next-to-minimal weight of Reed–Muller codes in most, but not all, cases. [ABSTRACT FROM PUBLISHER]

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size $q$ , i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance $d$ of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length $n$ , dimension $k$ , locality $r$ , availability $t$ , and field size $q$ . Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed–Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code. [ABSTRACT FROM PUBLISHER]

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called $\rho $ -node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any $\rho $ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in $\mathbb {Z}_{n}$. These codes are at most a single bit away from optimality. [ABSTRACT FROM AUTHOR]

MDS codes and self-dual codes are important families of classical codes in coding theory. Therefore, it is of interest to investigate MDS self-dual codes. The existence of MDS self-dual codes over finite field ${\mathbb F}_{q}$ is competely solved for $q$ is even. In the literature, there are many known constructions of MDS self-dual codes for $q$ is odd. In this paper, we present a unified approach on the existence of MDS self-dual codes with concise statements and simplified proof. It is illustrated that some of known results can also be stated in this framework. Furthermore, we can obtain some new MDS self-dual codes, especially for the case when $q$ is not a square. [ABSTRACT FROM AUTHOR]

In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length $ {n} > {q}+1$ are also obtained. [ABSTRACT FROM AUTHOR]

Line codes make it possible to mitigate interference, to prevent short pulses, and to generate streams of bipolar signals with no direct-current (DC) power content through balancing. They find application in magnetic recording (MR) devices, in Flash devices, in optical recording devices, and in some computer standards. This paper introduces a new family of fixed-length, binary constrained codes, named lexicographically-ordered constrained codes (LOCO codes), for bipolar non-return-to-zero signaling. LOCO codes are capacity-achieving, the lexicographic indexing enables simple, practical encoding and decoding, and this simplicity is demonstrated through analysis of circuit complexity. LOCO codes are easy to balance, and their inherent symmetry minimizes the rate loss with respect to unbalanced codes having the same constraints. Furthermore, LOCO codes that forbid certain patterns can be used to alleviate inter-symbol interference in MR systems and inter-cell interference in Flash systems. Numerical results demonstrate a gain of up to 10% in rate achieved by LOCO codes with respect to other practical constrained codes, including run-length-limited codes, designed for the same purpose. Simulation results suggest that it is possible to achieve a channel density gain of about 20% in MR systems by using a LOCO code to encode only the parity bits, limiting the rate loss, of a low-density parity-check code before writing. [ABSTRACT FROM AUTHOR]

We construct error-correcting write-once memory (WOM) codes that guarantee correction of any specified number of errors in $q$ -level memories. The constructions use suitably designed short $q$ -ary WOM codes and concatenate them with outer error-correcting codes over different alphabets using suitably designed mappings. With a new storage-efficiency measure, we call EC-rate and show that for common error types the codes save redundancy and implementation complexity over straightforward concatenation. In addition to constructions for guaranteed error correction, we extend the error-correcting WOM scheme to binary multi-level coding for random errors, and toward soft-decision decoding provide an efficient way to extract reliability information without using higher-precision readout. [ABSTRACT FROM AUTHOR]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

In this paper, we study the close relationship between Reed–Muller codes and single-qubit phase gates from the perspective of $T$ -count optimization. We prove that minimizing the number of $T$ gates in an $n$ -qubit quantum circuit over CNOT and $T$ , together with the Clifford group powers of $T$ , corresponds to finding a minimum distance decoding of a length $2^{n}-1$ binary vector in the order $n-4$ punctured Reed–Muller code. Moreover, we show that the problems are polynomially equivalent in the length of the code. As a consequence, we derive an algorithm for the optimization of $T$ -count in quantum circuits based on Reed–Muller decoders, along with a new upper bound of $O(n^{2})$ on the number of $T$ gates required to implement an $n$ -qubit unitary over CNOT and $T$ gates. We further generalize this result to show that minimizing small angle rotations corresponds to decoding lower order binary Reed–Muller codes. In particular, we show that minimizing the number of $R_{Z}(2\pi /m)$ gates for any integer $m$ is equivalent to minimum distance decoding in $\mathcal {RM}(n-k-1, n)^{*}$ , where $k$ is the highest power of 2 dividing $m$. [ABSTRACT FROM AUTHOR]

A ${\mathbb {Z}}_{2}{\mathbb {Z}}_{4}$ -additive code ${\mathcal{ C}}\subseteq {\mathbb {Z}}_{2}^\alpha \times {\mathbb {Z}}_{4}^\beta $ is called cyclic if the set of coordinates can be partitioned into two subsets, the set of ${\mathbb {Z}}_{2}$ coordinates and the set of ${\mathbb {Z}}_{4}$ coordinates, such that any cyclic shift of the coordinates of both subsets leaves the code invariant. Let $\Phi ({\mathcal{ C}})$ be the binary Gray map image of ${\mathcal{ C}}$. We study the rank and the dimension of the kernel of a ${\mathbb {Z}}_{2} {\mathbb {Z}}_{4} $ -additive cyclic code ${\mathcal{ C}}$ , that is, the dimensions of the binary linear codes $\langle \Phi ({\mathcal{ C}}) \rangle $ and $\ker (\Phi ({\mathcal{ C}}))$. We give upper and lower bounds for these parameters. It is known that the codes $\langle \Phi ({\mathcal{ C}}) \rangle $ and $\ker (\Phi ({\mathcal{ C}}))$ are binary images of ${\mathbb {Z}}_{2} {\mathbb {Z}}_{4}$ -additive codes that we denote by ${\mathcal{ R}}({\mathcal{ C}})$ and ${\mathcal{ K}}({\mathcal{ C}})$ , respectively. Moreover, we show that ${\mathcal{ R}}({\mathcal{ C}})$ and ${\mathcal{ K}}({\mathcal{ C}})$ are also cyclic and determine the generator polynomials of these codes in terms of the generator polynomials of the code ${\mathcal{ C}}$. [ABSTRACT FROM AUTHOR]

Motivated by the study of deletion channels, this paper presents improved bounds on the number of subsequences obtained from a binary string $X$ of length $n$ under $t$ deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string $X$ ; where a run is a maximal substring of the same character. Our improved bounds are obtained by a structural analysis of the family of $r$ -run strings $X$ , an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every $r$ , we present $r$ -run strings with the minimum (respectively maximum) number of subsequences under any $t$ deletions; we perform an exact analysis of the number of subsequences of these extremal strings; and show that this number can be calculated in polynomial time. [ABSTRACT FROM AUTHOR]

A Z2Z4 -linear Hadamard code of length \alpha +2\beta =2^t is a binary Hadamard code, which is the Gray map image of a Z2Z4 -additive code with \alpha binary coordinates and \beta quaternary coordinates. It is known that there are exactly \lfloor \frac t-12 \rfloor and \lfloor \frac t2 \rfloor nonequivalent Z2Z4 -linear Hadamard codes of length 2^t , with $\alpha =0$ and \alpha \not =0$ , respectively, for all t\geq 3$ . In this paper, it is shown that each \alpha =0$ is equivalent to a Z2Z4 -linear Hadamard code with \alpha \not =0 nonequivalent Z2Z4 -linear Hadamard codes of length 2^t . Moreover, the order of the monomial automorphism group for the Z2Z4 -additive Hadamard codes and the permutation automorphism group of the corresponding Z2Z4 -linear Hadamard codes are given. [ABSTRACT FROM AUTHOR]