Search

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction $\tau \ge 1/4$ vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with $n$ transmissions that achieves a positive rate for any fraction of errors $\tau < 1$ and $n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

$\mathbb {Z}_{2^{s}}$ -additive codes are subgroups of $\mathbb {Z}^{n}_{2^{s}}$ , and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{2^{s}}$ -linear code is a binary code (not necessarily linear) which is the Gray map image of a $\mathbb {Z}_{2^{s}}$ -additive code. We consider $\mathbb {Z}_{2^{s}}$ -additive simplex codes of type $\alpha $ and $\beta $ , which are a generalization over $\mathbb {Z}_{2^{s}}$ of the binary simplex codes. These codes are related to the $\mathbb {Z}_{2^{s}}$ -additive Hadamard codes. In this paper, we use this relationship to find a linear subcode of the corresponding $\mathbb {Z}_{2^{s}}$ -linear codes, called kernel, and a representation of these codes as cosets of this kernel. In particular, this also gives the linearity of these codes. Similarly, $\mathbb {Z}_{2^{s}}$ -additive MacDonald codes are defined for $s>2$ , and equivalent results are obtained. [ABSTRACT FROM AUTHOR]

Linear codes over $\mathbb {Z}_{p^{s}}$ of length $n$ are subgroups of $\mathbb {Z}_{p^{s}}^{n}$. These codes are also called $\mathbb {Z}_{p^{s}}$ -additive codes and can be seen as a generalization of linear codes over $\mathbb {Z}_{2}$ and $\mathbb {Z}_{4}$. A $\mathbb {Z}_{p^{s}}$ -linear code is a code over $\mathbb {Z}_{p}$ , not necessarily linear, which is the generalized Gray map image of a $\mathbb {Z}_{p^{s}}$ -additive code. In 2015, a systematic encoding was found for $\mathbb {Z}_{4}$ -linear codes. Moreover, an alternative permutation decoding method, which is suitable for any binary code (not necessarily linear) with a systematic encoding, was established. In this paper, we generalize these results by presenting a systematic encoding for any $\mathbb {Z}_{p^{s}}$ -linear code with $s\geq 2$ and $p$ prime. We also describe a permutation decoding method for any systematic code over $\mathbb {Z}_{p}$ , not necessarily linear, and show some examples of how to use this systematic encoding in this decoding method. [ABSTRACT FROM AUTHOR]

A new family of codes, called clustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of the data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also called strands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost. Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, their data fields have large distance. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single symbol of redundancy. The results are first presented for the Hamming metric and are then extended for the edit distance. [ABSTRACT FROM AUTHOR]

Due to its high data density and longevity, DNA is considered a promising medium for satisfying ever-increasing data storage needs. However, the diversity of errors that occur in DNA sequences makes efficient error-correction a challenging task. This paper aims to address simultaneously correcting two types of errors, namely, short tandem duplication and edit errors, where an edit error may be a substitution, deletion, or insertion. We focus on tandem repeats of length at most 3 and design codes for correcting an arbitrary number of duplication errors and one edit error. Because an edited symbol can be duplicated many times (as part of substrings of various lengths), a single edit can affect an unbounded substring of the retrieved word. However, we show that with appropriate preprocessing, the effect may be limited to a substring of finite length, thus making efficient error-correction possible. We construct a code for correcting the aforementioned errors and provide lower bounds for its rate. Compared to optimal codes correcting only duplication errors, numerical results show that the asymptotic cost of protecting against an additional edit is only 0.003 bits/symbol when the alphabet has size 4, an important case corresponding to data storage in DNA. [ABSTRACT FROM AUTHOR]

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear codes have been studied since decades but their tight connection with cutting blocking sets of finite projective spaces was unfolded only in the past few years, and it has not been fully exploited yet. In this paper we apply finite geometric and probabilistic arguments to contribute to the field of minimal codes. We prove an upper bound on the minimal length of minimal codes of dimension $k$ over the $q$ -element Galois field which is linear in both $q$ and $k$ , hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well. [ABSTRACT FROM AUTHOR]

Quantum error-correcting codes play the role of suppressing noise and decoherence in quantum systems by introducing redundancy. Some strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error-correcting codes to achieve higher rates than the one obtained by means of the traditional stabilizer formalism. Such codes are called entanglement-assisted quantum error-correcting (EAQEC) codes. In this paper, we utilize algebraic geometry codes to construct several families of EAQEC codes derived from the Euclidean and the Hermitian construction. Three families constructed here consist of codes whose quantum Singleton defect is equal to zero, one, or two. We also construct families of EAQEC codes with an encoding rate exceeding the quantum Gilbert-Varshamov bound. Additionally, asymptotically good towers of linear complementary dual codes are used to obtain asymptotically good families of EAQEC codes consuming maximal entanglement. Furthermore, a simple comparison with the quantum Gilbert-Varshamov bound demonstrates that, by utilizing the proposed construction, it is possible to generate an asymptotically family of EAQEC codes that exceeds this bound. [ABSTRACT FROM AUTHOR]

A new method to construct q-ary complementary sequence sets (CSSs) and complete complementary codes (CCCs) of size N is proposed by using desired para-unitary (PU) matrices. The concept of seed PU matrices is introduced and a systematic approach on how to compute the explicit forms of the functions in constructed CSSs and CCCs from the seed PU matrices is given. A general form of these functions only depends on a basis of the functions from ZN to Zq and representatives in the equivalent class of Butson-type Hadamard (BH) matrices. Especially, the realization of Golay pairs from our general form exactly coincides with the standard Golay pairs. The realization of ternary complementary sequences of size 3 is first reported here. For the realization of the quaternary complementary sequences of size 4, almost all the sequences derived here are never reported before. Generalized seed PU matrices and the recursive constructions of the desired PU matrices are also studied, and a large number of new constructions of CSSs and CCCs are given accordingly. From the perspective of this paper, all the known results of CSSs and CCCs with explicit GBF form in the literature (except non-standard Golay pairs) are constructed from the WHT matrices. This suggests that the proposed method with other BH matrices will yield a large number of new CSSs and CCCs with the significantly increasing number of the sequences of low peak-to-mean envelope power ratio. [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]

In the $q$ -ary online (or “causal”) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf {x} =(x_{1},\ldots,x_{n}) \in \{0,1,\ldots,q-1\}^{n}$ symbol-by-symbol via a channel limited to at most $pn$ errors and $p^{*} n$ erasures. The channel is “online” in the sense that at the $i$ th step of communication the channel decides whether to corrupt the $i$ th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols $(x_{1},\ldots,x_{i})$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword $\mathbf {x}$. In this paper, we study the capacity of $q$ -ary online channels for a combined corruption model, in which the channel may impose at most $pn$ errors and at most $p^{*} n$ erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of $q,p$ , and $p^{*}$. [ABSTRACT FROM AUTHOR]

Constacyclic codes are well-known generalizations of cyclic and negacyclic codes. Due to their rich algebraic structure, constacyclic codes are used to construct quantum codes and symbol-pair codes. Let ${\mathbb {F}}_{q}$ be a finite field with order $q$ , where $q$ is a positive power of a prime $p$. Suppose that $n$ is a positive integer and the product of distinct prime factors of $n$ divides $q-1$ , i.e., $rad(n)\mid (q-1)$. In this paper, we explicitly factorize the polynomial $x^{n}-\lambda $ for each $\lambda \in {\mathbb {F}}_{q}^{*}$. As applications, first, we obtain all repeated-root $\lambda $ -constacyclic codes and their dual codes of length $np^{s}$ over ${\mathbb {F}}_{q}$ ; second, we determine all simple-root LCD cyclic codes and LCD negacyclic codes of length $n$ over ${\mathbb {F}}_{q}$ ; third, we list all self-dual repeated-root negacyclic codes of length $np^{s}$ over ${\mathbb {F}}_{q}$. In contrast to known results, the lengths of constacyclic codes in this paper have more flexible parameters. [ABSTRACT FROM AUTHOR]

Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]

In an interesting paper, Prof. C. Ding provided three constructions of cyclic codes of length being a product of two primes. Numerical data shows that many codes from these constructions are best cyclic codes of the same length and dimension over the same finite field. However, not much is known about these codes. In this paper, we explain some of the numerical data by developing a general method on cyclic codes of composite length and on estimating the minimum distance. We also provide a general construction of cyclic codes of composite length which are related to Ding’s constructions. Numerical data shows that it produces many best cyclic codes as well. Finally, we point out how these cyclic codes can be used to construct convolutional codes with large free distance. [ABSTRACT FROM AUTHOR]

In distributed computing systems slow working nodes, known as stragglers, can greatly extend finishing times. Coded computing is a technique that enables straggler-resistant computation. Most coded computing techniques presented to date provide robustness by ensuring that the time to finish depends only on a set of the fastest nodes. However, while stragglers do compute less work than non-stragglers, in real-world commercial cloud computing systems (e.g., Amazon’s Elastic Compute Cloud (EC2)) the distinction is often a soft one. In this paper, we develop hierarchical coded computing that exploits the work completed by all nodes, both fast and slow, automatically integrating the potential contribution of each. We first present a conceptual framework to represent the division of work amongst nodes in coded matrix multiplication as a cuboid partitioning problem. This framework allows us to unify existing methods and motivates new techniques. We then develop three methods of hierarchical coded computing that we term bit-interleaved coded computation (BICC), multilevel coded computation (MLCC), and hybrid hierarchical coded computation (HHCC). In this paradigm, each worker is tasked with completing a sequence (a hierarchy) of ordered subtasks. The sequence of subtasks, and the complexity of each, is designed so that partial work completed by stragglers can be used, rather than ignored. We note that our methods can be used in conjunction with any coded computing method. We illustrate this by showing how we can use our methods to accelerate all previously developed coded computing techniques by enabling them to exploit stragglers. Under a widely studied statistical model of completion time, our approach realizes a 66% improvement in the expected finishing time. On Amazon EC2, the gain was 27% when stragglers are simulated. [ABSTRACT FROM AUTHOR]

This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords $\mathsf {M}$ , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the $r$ -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized $r$ -wise Plotkin bound. The $r$ -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < $\delta$ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords $\mathsf {M}$ satisfying $\mathsf {M}\le 4$ and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For $\mathsf {M}$ = 5 or $\mathsf {M}$ = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger $\mathsf {M}$ , observations regarding the optimal design are presented, e.g., that good codes have a large $r$ -wise Hamming distance structure for all $r$. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes. [ABSTRACT FROM AUTHOR]

Shannon in his 1956 seminal paper introduced the concept of the zero error capacity, C0 , of a noisy channel. This is defined as the least upper bound of rates, at which, it is possible to transmit information with zero probability of error. At present not many codes are known to achieve the zero error capacity. In this paper, some codes which achieve zero error capacities in limited magnitude error channels are described. The code lengths of these zero error capacity achieving codes can be of any finite length $n=1,2,\ldots$ , in contrast to the long lengths required for the known regular capacity achieving codes, such as turbo codes, LDPC codes, and polar codes. Both wrap around and non-wrap around limited magnitude error models are considered in this paper. For non-wrap around error model, the exact value of zero error capacities is derived, and optimal non-systematic and systematic codes are designed. The non-systematic codes achieve the zero error capacity with any finite length. The optimal systematic codes achieve the systematic zero error capacity of the channel, which is defined as the zero error capacity with the additional requirements that the communication must be carried out with a systematic code. It is also shown that the rates of the proposed systematic codes are equal to or approximately equal to the zero error capacity of the channel. For the wrap around model bounds are derived for the zero error capacity and in many cases the bounds give the exact value. In addition, optimal wrap around non-systematic and systematic codes are developed which either achieve or are close to achieving the zero error capacity with finite length. [ABSTRACT FROM PUBLISHER]

$\epsilon $ -Minimum Storage Regenerating ($\epsilon $ -MSR) codes form a special class of Maximum Distance Separable (MDS) codes, providing mechanisms for exact regeneration of a single code block in their codewords by downloading slightly sub-optimal amount of information from the remaining code blocks. The key advantage of these codes is a significantly lower sub-packetization that grows only logarithmically with the code length, while providing optimality in storage and error-correcting capacity. However, existing constructions of $\epsilon $ -MSR codes require each remaining code block to be available for the repair of any failed code block. In this paper, we construct $\epsilon $ -MSR codes that can repair any failed code block by contacting fewer number of available code blocks. When a code block fails, our repair procedure needs to contact a few compulsory code blocks and is free to choose any subset of available code blocks for the remaining choices. Our construction requires a field size linear in code length and ensures load balancing (in terms of information downloaded) among the contacted code blocks for repairing a failed code block. [ABSTRACT FROM AUTHOR]

Constant dimension codes (CDCs), as special subspace codes, have received a lot of attention due to their application in random network coding. This paper introduces a family of new codes, called rank metric codes with given ranks (GRMCs), to generalize the parallel construction in [Xu and Chen, IEEE Trans. Inf. Theory, 64 (2018), 6315–6319] and the classic multilevel construction. A Singleton-like upper bound and a lower bound for GRMCs derived from Gabidulin codes are given. Via GRMCs, two effective constructions for CDCs are presented by combining the parallel construction and the multilevel construction. Many CDCs with larger size than the previously best known codes are given. The ratio between the new lower bound and the known upper bound for $(4\delta,2\delta,2\delta)_{q}$ -CDCs is calculated. It is greater than 0.99926 for any prime power $q$ and any $\delta \geq 3$. [ABSTRACT FROM AUTHOR]

Limited magnitude asymmetric error model is well suited for flash memory. In this paper, we consider the construction of asymmetric codes correcting single error over $\mathbb {Z}_{2^{k}r}$ which is based on so called $B_{1}[{4}](2^{k}r)$ set. In fact, we reduce the construction of a maximal size $B_{1}[{4}](2^{k}r)$ set for $k\geq 3$ to the construction of a maximal size $B_{1}[{4}](2^{k-3}r)$ set. Finally, we give an explicit formula of a maximal size $B_{1}[{4}](4r)$ set and some lower bounds of a maximal size $B_{1}[{4}](2r)$ set. By computer searching up to $q\leq 106$ , we conjecture that those lower bounds are tight. [ABSTRACT FROM AUTHOR]

Regenerating code is a class of distributed storage codes that can optimally trade the bandwidth with the amount of data stored per node to repair a failed node. There are two extreme points in the optimal regenerating trade-off curve, which correspond to minimum-storage regenerating (MSR) and minimum-bandwidth regenerating (MBR). Recently, Reed-Solomon (RS) code based regenerating codes (RS-RC) were constructed under the product-matrix framework. It can also achieve the maximum distance separable (MDS) property in code regeneration and reconstruction. However, in case that the network is hostile and the storage nodes could be compromised or packets be modified, the storage capacity and the bandwidth required to regenerate or reconstruct the original file can be significantly affected. In this paper, we propose Hermitian code based regenerating codes (H-RC) by developing constructions under the product-matrix framework for minimum storage regenerating (H-MSR) and the minimum bandwidth regenerating (H-MBR). We also propose data regeneration and reconstruction algorithms for both H-MSR and H-MBR codes under both error-free and hostile networks. We demonstrate that the proposed algorithms can also successfully determine the erroneous decodings in hostile networks. Theoretical evaluation shows that our proposed H-RC can detect and correct more errors in hostile networks well beyond the RS-RC with the same code rate. Our analysis shows that the proposed H-RC have lower computational complexity than the RS-RC for both code regeneration and code reconstruction. [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]

The increasing interest in using quantum error correcting codes in practical devices has heightened the need for designing quantum error correcting codes that can correct against specialized errors, such as that of amplitude damping errors which model photon loss. Although considerable research has been devoted to quantum error correcting codes for amplitude damping, not so much attention has been paid to having these codes simultaneously lie within the decoherence free subspace of their underlying physical system. One common physical system comprises of quantum harmonic oscillators, and constant-excitation quantum codes can be naturally stabilized within them. The purpose of this paper is to give constant-excitation quantum codes that not only correct amplitude damping errors, but are also immune against permutations of their underlying modes. To construct such quantum codes, we use the nullspace of a specially constructed matrix based on integer partitions. [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]

Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation ball sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing upper and lower bounds on multipermutation Ulam ball sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric. [ABSTRACT FROM AUTHOR]

We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems à la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms -notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC code-based cryptosystem) in a rank metric context, due to the similar form of the public keys. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to $\frac {2}{3}(n-k)$ when the previous decoding algorithm only decodes up to $\frac {n-k}{2}$ errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to $\frac {n-k}{2}$. This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 5893 bits for public key encryption, both for 128 bits of security. [ABSTRACT FROM AUTHOR]

Let $q$ be a prime power and $m\geq 3$ be odd. Suppose that $n=\frac {q^{2m}-1}{a}$ with $a|(q^{m}+1)$ and $3\leq a \leq 2(q^{2}-q+1)$. This paper mainly determines the actual maximum designed distance of Hermitian dual-containing Bose-Chaudhuri-Hocquenghem (BCH) codes over $\mathbb {F}_{q^{2}}$ of length $n$. Firstly, we give the maximum designed distance $\delta _{m,a}^{R}$ of narrow-sense Hermitian dual-containing BCH codes. Secondly, we show that there are also non-narrow-sense ones of designed distance up to $\delta _{m,a}^{R}$. It is worth mentioning that our maximum designed distance $\delta _{m,a}^{R}>\lceil \frac {a}{2}\rceil \delta _{m}^{A}$ , where $\delta _{m}^{A}$ is given by Aly et al. (IEEE Trans. Inf. Theory, vol. 53, no. 3, pp. 1183-1188, 2007). Thus, many families of Hermitian dual-containing BCH codes with relatively large designed distance are obtained. Using the Hermitian construction to them, we can subsequently construct different classes of nonprimitive quantum codes, which are new in the sense that their parameters are not covered in the literature. [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]

In this paper, we first study deviations of the complete weight distribution of a linear code from that of a random code. Then, we consider a large family of subfield subcodes of algebraic-geometric codes over prime fields which include BCH codes and Goppa codes and prove that the complete weight distribution is close to that of a random code if the code length is large compared with the genus of the curve and the degree of the divisor defining the code. [ABSTRACT FROM AUTHOR]

A common way to protect data stored in DRAM and related memory systems is through the use of an error-correcting code such as the extended Hamming code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In this paper, we focus on unequal message protection (UMP), in which a subset of messages is deemed as special, and is afforded additional error-correction protection while maintaining the same number of redundancy bits as the baseline code. UMP is a powerful approach when the special messages are chosen based on the knowledge of data patterns in context. Our objective is to construct deterministic, algebraic codes with guaranteed UMP properties, derive their cardinality bounds using novel combinatorial techniques, and to demonstrate their efficacy for realistic memory benchmarks. We first introduce a UMP alternative to the single-bit parity-check code, and then we generalize to a broader UMP code family, including a UMP alternative to the extended Hamming code, offering full double-error correction protection to special messages. Our UMP constructions, applied to main memory in high-performance computing applications, could lead to significant system-level benefits such as less frequent checkpoints in supercomputers and decreased risk of catastrophic failure from erroneous special messages. [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]

In this paper, we reinterpret the $(k+2,k)$ zigzag code in coding matrix and then propose an optimal exact repair strategy for its parity nodes, whose repair disk I/O approaches a lower bound derived in this paper. [ABSTRACT FROM PUBLISHER]

Recently, Etzion et al. introduced metrics on ${\mathbb{F}}_{2}^{n}$ based on directed graphs on $n$ vertices and developed some basic coding theory on directed graph metric spaces. In this paper, we consider the problem of classifying directed graphs, which admit the extended Hamming codes to be a perfect code. We first consider weighted poset metrics as a natural generalization of poset metrics and investigate interrelation between the weighted poset metrics and the directed graph-based metrics. In the next, we classify weighted posets on a set with eight elements and directed graphs on eight vertices, which admit the extended Hamming code $\tilde {\mathcal {H }}_{3}$ to be a two-perfect code. We also construct some families of such structures for any $k \geq 3$ , which can be viewed as generalizations of some results presented by Etzion et al. and Hyun and Kim. Those families enable us to construct packing or covering codes of radius 2 under certain maps. [ABSTRACT FROM AUTHOR]

Gaussian thermal loss channels are of particular importance to quantum communication theory since they model realistic optical communication channels. Except for special cases, the quantum capacity of Gaussian thermal loss channels is not yet quantified completely. In this paper, we provide improved upper bounds of the Gaussian thermal loss channel capacity, both in energy-constrained and unconstrained scenarios. We briefly review Gottesman-Kitaev-Preskill (GKP) codes and discuss their experimental implementation. We then prove, in the energy-unconstrained case, that a family of GKP codes achieves the quantum capacity of Gaussian thermal loss channels up to at most a constant gap from the improved upper bound. In the energy-constrained case, we formulate a biconvex encoding and decoding optimization problem to maximize entanglement fidelity. Then, we solve the biconvex optimization heuristically by an alternating semi-definite programming method and report that, starting from Haar random initial codes, our numerical optimization yields a hexagonal GKP code as an optimal encoding in a practically relevant regime. [ABSTRACT FROM AUTHOR]

We consider list decoding in the zero-rate regime for two cases—the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal $\tau \in [{0,1}]$ for which there exists an arrangement of $M$ balls of relative Hamming radius $\tau $ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by $L$ or more of them. As $M\to \infty $ the maximal $\tau $ decreases to a well-known critical value $\tau _{L}$. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is $\Theta (M^{-1})$ when $L$ is even, thus extending the classical results of Plotkin and Levenshtein for $L=2$. For $L=3$ , the rate is shown to be $\Theta (M^{-({2}/{3})})$. For the similar question about spherical codes, we prove the rate is $\Omega (M^{-1})$ and $O(M^{-({2L}/{L^{2}-L+2})})$. [ABSTRACT FROM AUTHOR]

Communication in integrated circuits faces two major impediments: inter-wire capacitive coupling and noise. Coding can be used to address both these problems. So-called crosstalk-avoidance codes mitigate capacitive coupling, and traditional error-correction codes introduce resilience against channel errors. Unfortunately, crosstalk-avoidance and error-correction codes cannot be combined in a straightforward manner. On the one hand, crosstalk-avoidance encoding followed by error-correction encoding destroys the crosstalk-avoidance property. On the other hand, error-correction encoding followed by crosstalk-avoidance encoding causes the crosstalk-avoidance decoder to fail in the presence of errors. Existing approaches circumvent this difficulty by using additional bus wires to protect the parities generated from the output of the error-correction encoder, and are therefore inefficient. In this paper, we propose a novel joint crosstalk-avoidance and error-correction coding and decoding scheme that provides higher bus transmission rates compared with existing approaches. Our joint approach carefully embeds the parities such that the crosstalk-avoidance property is preserved. We analyze the rate and minimum distance of the proposed scheme. We also provide a density evolution analysis and predict iterative decoding thresholds for reliable communication under random bus erasures. This density evolution analysis is nonstandard, since the crosstalk-avoidance constraints are inherently nonlinear. [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]

Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed–Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size $q$. Recently, it was proved through the extension of construction by Tamo and Barg that the length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al. Surprisingly, Barg et al. 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 the work of Li et al. that there exist $q$ -ary optimal locally repairable codes with the length bigger than $q+1$ and the distance proportional 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 distances 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. [ABSTRACT FROM AUTHOR]

We study the problem of constructing balanced generator matrices for Reed–Solomon and Tamo–Barg codes. More specifically, we are interested in realizing generator matrices, for the full-length cyclic versions of these codes, where all rows have the same weight and the difference in weight between any columns is at most one. The results presented in this paper translate to computationally balanced encoding schemes, which can be appealing in distributed storage applications. Indeed, the balancedness of these generator matrices guarantees that the computation effort exerted by any storage node is essentially the same. In general, the framework presented can accommodate various values for the required row weight. We emphasize the possibility of constructing sparsest and balanced generator matrices for Reed–Solomon codes, i.e., each row is a minimum distance codeword. The number of storage nodes contacted once a message symbol is updated decreases with the row weight, so sparse constructions are appealing in that context. Results of similar flavor are presented for cyclic Tamo–Barg codes. In particular, we show that for a code with minimum distance $d$ and locality $r$ , a construction in which every row is of weight $d + r - 1$ is possible. The constructions presented are deterministic and operate over the codes’ original underlying finite field. As a result, efficient decoding from both errors and erasures is possible thanks to the plethora of efficient decoders available for the codes considered. [ABSTRACT FROM AUTHOR]

A combinatorial framework for adversarial network coding is presented. Channels are described by specifying the possible actions that one or more (possibly coordinated) adversaries may take. Upper bounds on three notions of capacity—the one-shot capacity, the zero-error capacity, and the compound zero-error capacity—are obtained for point-to-point channels, and generalized to corresponding capacity regions appropriate for multi-source networks. A key result of this paper is a general method by which bounds on these capacities in point-to-point channels may be ported to networks. This technique is illustrated in detail for Hamming-type channels with multiple adversaries operating on specific coordinates, which correspond, in the context of networks, to multiple adversaries acting on specific network edges. Capacity-achieving coding schemes are described for some of the considered adversarial models. [ABSTRACT FROM AUTHOR]

An error-erasure channel is a simple noise model that introduces both errors and erasures. While the two types of errors can be corrected simultaneously with error-correcting codes, it is also known that any linear code allows for first correcting errors and then erasures in two-step decoding. In particular, a carefully designed parity-check matrix not only allows for separating erasures from errors but also makes it possible to efficiently correct erasures. The separating redundancy of a linear code is the number of parity-check equations in a smallest parity-check matrix that has the required property for this error-erasure separation. In a sense, it is a parameter of a linear code that represents the minimum overhead for efficiently separating erasures from errors. While several bounds on separating redundancy are known, there still remains a wide gap between upper and lower bounds except for a few limited cases. In this paper, using probabilistic combinatorics and design theory, we improve both upper and lower bounds on separating redundancy. We also show a relation between parity-check matrices for error-erasure separation and special matrices, called X-codes, for data compaction circuits in VLSI testing. This leads to an exponentially improved bound on the size of an optimal X-code. [ABSTRACT FROM AUTHOR]

When transmitting information over a noisy channel, two approaches, dating back to Shannon’s work, are common: assuming the channel errors are independent of the transmitted content and devising an error-correcting code or assuming the errors are data dependent and devising a constrained-coding scheme that eliminates all offending data patterns. In this paper, we analyze a middle road, which we call a semiconstrained system. In such a system, which is an extension of the channel with the cost constraints model, we do not eliminate the error-causing sequences entirely, but rather restrict the frequency in which they appear. We address several key issues in this paper. The first is proving closed-form bounds on the capacity, which allow us to bound the asymptotics of the capacity. In particular, we bound the rate at which the capacity of the semiconstrained $(0,k)$ -RLL tends to 1 as $k$ grows. The second key issue is devising efficient encoding and decoding procedures that asymptotically achieve capacity with vanishing error. Finally, we consider delicate issues involving the continuity of the capacity and a relaxation of the definition of semiconstrained systems. [ABSTRACT FROM AUTHOR]

The rank modulation scheme has been proposed for efficient writing and storing data in nonvolatile memory storage. Error correction in the rank modulation scheme is done by considering permutation codes. In this paper, we consider codes in the set of all permutations on n elements, S_{n} , using the Kendall \tau -metric. The main goal of this paper is to derive new bounds on the size of such codes. For this purpose, we also consider perfect codes, diameter perfect codes, and the size of optimal anticodes in the Kendall \tau -metric, structures which have their own considerable interest. We prove that there are no perfect single-error-correcting codes in S_{n} , where n>4 is a prime or 4\leq n\leq 10 . We present lower bounds on the size of optimal anticodes with odd diameter. As a consequence, we obtain a new upper bound on the size of codes in S_{n} with even minimum Kendall \tau -distance. We present larger single-error-correcting codes than the known ones in S5 and S7 . [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]

This paper deals with Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes, which are binary codes after a Gray map from a subgroup of direct products of \mathbb Z2 , \mathbb Z4 , and Q8 , where Q8 is the quaternionic group. In a previous work, these codes were classified in five shapes. In this paper, we analyze the allowable range of values for the rank and dimension of the kernel, which depends on the particular shape of the code. We show that all these codes can be represented in a standard form, from a set of generators, which can help in understanding the characteristics of each shape. The main results we present are the characterization of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes as a quotient of a semidirect product of \mathbb Z2 \mathbb Z4 -linear codes and the construction of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes with each allowable pair of values for the rank and dimension of the kernel. [ABSTRACT FROM AUTHOR]

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes like Reed–Solomon or Reed–Muller codes. Fix a finite field \mathbb F . The Reed–Muller code \text RM {\mathbb {F}}(n,d) is defined by n -variate degree- d polynomials over \mathbb F . In this paper, we study the list decoding radius of Reed–Muller codes over a constant prime field \mathbb F= \mathbb Fp , constant degree d , and large n . We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by {\delta }(d) the normalized minimal distance of \text RM {\mathbb {F}}(n,d) , then the number of codewords in any ball of radius {\delta }(d)- {\varepsilon } is bounded by c=c(p,d, \varepsilon ) independent of n . This resolves a conjecture of Gopalan et al., who among other results proved it in the special case of \mathbb F= \mathbb F2 ; and extends the work of Gopalan who proved the conjecture in the case of d=2 . We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For e \leq d , we show that the number of codewords of \text RM \mathbb F(n,d) in a ball of radius \delta (e) - \varepsilon is bounded by \exp (c \cdot n^d-e) , where c=c(p,d, \varepsilon ) is independent of $n$ . The dependence on n$ is tight. This extends the work of Kaufman et al. who proved similar bounds over {\mathbb {F}}_{2} . The proof relies on several new ingredients: an extension of the Frieze–Kannan weak regularity to general function spaces, higher order Fourier analysis, and an extension of the Schwartz–Zippel lemma to the compositions of polynomials. [ABSTRACT FROM PUBLISHER]

This paper reduces multiple-unicast network coding to single-unicast secure network coding and single-unicast network error correction. Specifically, we present reductions that map an arbitrary multiple-unicast network coding instance to a unicast secure network coding instance in which at most one link is eavesdropped, or a unicast network error correction instance in which at most one link is erroneous, such that a rate tuple is achievable in the multiple-unicast network coding instance if and only if a corresponding rate is achievable in the unicast secure network coding instance, or in the unicast network error correction instance. Conversely, we show that an arbitrary unicast secure network coding instance in which at most one link is eavesdropped can be reduced back to a multiple-unicast network coding instance. In addition, we show that the capacity of a unicast network error correction instance in general is not (exactly) achievable. [ABSTRACT FROM AUTHOR]

Random (dv,dc) -regular low-density parity-check (LDPC) codes, where each variable is involved in dv parity checks and each parity check involves dc variables are well-known to achieve the Shannon capacity of the binary symmetric channel, for sufficiently large dv and dc , under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the linear programming (LP) decoding algorithm of Feldman et al., which is known to correct an \Omega (1/dc) fraction of errors. In this paper, we show that fairly powerful extensions of LP decoding, based on the Sherali–Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that: 1) for any values of dv and dc , a linear number of rounds of the Sherali–Adams LP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc) -regular LDPC code; and 2) for any value of dv and infinitely many values of dc , a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc) -regular LDPC code. Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali–Adams and special cosets of balanced pairwise independent subgroups for Lasserre. Our (algebraic) construction for the Lasserre hierarchy is based on designing sets of points in \mathbb Fq^{d} (for $q$ any power of 2 and $d = 2,3$ ) with special hyperplane-incidence properties—constructions that may be of independent interest. An intriguing consequence of our work is that expansion seems to be both the strength and the weakness of random regular LDPC codes. Some of our techniques are more generally applicable to a large class of Boolean CSPs called Min-Ones. In particular, for $k$ -Hypergraph Vertex Cover, we obtain an improved integrality gap of $k-1-\epsilon $ that holds after a linear number of rounds of the Lasserre hierarchy, for any $k = q+1$ with $q$ an arbitrary prime power. The best previous gap for a linear number of rounds was equal to $2-\epsilon $ and due to Schoenebeck. [ABSTRACT FROM PUBLISHER]

In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel, the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP superposition coding is introduced, whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme, where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection. [ABSTRACT FROM AUTHOR]

Reducible codes for the rank metric were introduced for cryptographic purposes. They have fast encoding and decoding algorithms, include maximum rank distance (MRD) codes, and can correct many rank errors beyond half of their minimum rank distance, which makes them suitable for error correction in network coding. In this paper, we study their security behavior against information leakage on networks when applied as coset coding schemes, giving the following main results: 1) we give lower and upper bounds on their generalized rank weights (GRWs), which measure worst case information leakage to the wire tapper; 2) we find new parameters for which these codes are MRD (meaning that their first GRW is optimal) and use the previous bounds to estimate their higher GRWs; 3) we show that all linear (over the extension field) codes, whose GRWs are all optimal for fixed packet and code sizes but varying length are reducible codes up to rank equivalence; and 4) we show that the information leaked to a wire tapper when using reducible codes is often much less than the worst case given by their (optimal in some cases) GRWs. We conclude with some secondary related properties: conditions to be rank equivalent to Cartesian products of linear codes and conditions to be rank degenerate, duality properties, and MRD ranks. [ABSTRACT FROM PUBLISHER]