Search

The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources. [ABSTRACT FROM AUTHOR]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $r\geq 3$ be a positive integer satisfying $\gcd (r,n)=1$ and $\gcd \big (r,q(q^{2}-1)\big)=1$. We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$. [ABSTRACT FROM AUTHOR]

Consider a channel with a given input alphabet size and input distribution. Our aim is to degrade or upgrade it to a channel with at most L output letters. Channel Q is degraded with respect to a channel W if Q can be obtained from W by processing the output of W. Upgrading is the inverse relation. This paper contains four main results. The first result, from which the paper title is derived, deals with the so called “greedy–merge” algorithm. We derive an upper bound on the reduction in mutual information between input and output, as a function of L. This upper bound is within a constant factor of an algorithm-independent lower bound. Thus, we establish that greedy–merge is optimal in the power-law sense (i.e. the power of L). The other main results deal with upgrading. The second result shows that a certain sequence of channels, which was previously shown to be “hard” for degrading, displays the same hardness in the context of upgrading. That is, suppose we are given such a channel and a corresponding input distribution. If we upgrade (degrade) to a new channel with L output letters, we incur an increase (decrease) in mutual information between input and output. We show that a previously derived bound on the decrease in mutual information for the degrading case is also a lower bound on the increase for the upgrading case. The third result is an efficient algorithm for optimal upgrading, in the binary-input case. That is, we are given a channel and an input distribution. We must find an upgraded channel with L output letters, for which the increase in mutual information is minimal. We give a simple characterization of such a channel, which implies an efficient algorithm. The fourth result is an analog of the first result for the upgrading case when the input is binary. That is, we first present a sub-optimal algorithm for the setting considered in the third result. The main advantage of the sub-optimal algorithm is that it is amenable to analysis. We carry out the analysis and show that the increase incurred in mutual information is within a constant factor of the lower bound derived in the second result. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

A pair of sequences is called a Z-complementary pair (ZCP) if it has zero aperiodic autocorrelation sums at each of the non-zero time-shifts within a certain region, called the zero correlation zone (ZCZ). ZCPs are categorised into two types: Type-I ZCPs and Type-II ZCPs. Type-I ZCPs have the ZCZ around the in-phase position and Type-II ZCPs have the ZCZ around the end-shift position. Till now only a few constructions of Type-II ZCPs are reported in the literature, and all have lengths of the form 2m ± 1 or N + 1 where N = 2a 10b 26c and a, b, c are non-negative integers. In this paper, we propose a recursive construction of ZCPs based on concatenation of sequences. Inspired by Turyn’s construction of Golay complementary pairs, we also propose a construction of Type-II ZCPs from known ones. The proposed constructions can generate optimal Type-II ZCPs with new flexible parameters and Z-optimal Type-II ZCPs with any odd length. In addition, we give upper bounds for the PMEPR of the proposed ZCPs. It turns out that our constructions lead to ZCPs with low PMEPR. [ABSTRACT FROM AUTHOR]

The well-known Huffman algorithm is an elegant approach to solve the basic problem of finding the optimal code among those with Kraft sums smaller than or equal to 1. In this paper, an extended problem is investigated, where the Kraft sum of the usable codes is limited to a given real number $\gamma $ , $0<\gamma <1$ . Unlike the case $\gamma =1$ (i.e., Huffman coding), for $\gamma <1$ , the Kraft sum of the optimal code is not necessarily equal to $\gamma $ . However, we show that the Kraft sum of the optimal code lies in a finite set of rational numbers which depend on the value of $\gamma $ . This motivates us to first devise a recursive algorithm to obtain the optimal codelengths with Kraft sum equal to $\gamma '$ , where $\gamma '$ has a finite binary representation and $0<\gamma '<1$ . To do so, the set of $N$ -tuple codelength vectors with a specific Kraft sum $\gamma '$ is characterized. The binary representation of $\gamma $ plays a fundamental role in all problems that arise for $\gamma <1$ . [ABSTRACT FROM PUBLISHER]

In a locally recoverable or repairable code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds. [ABSTRACT FROM PUBLISHER]

A primitive $k$ -batch code encodes a string $\boldsymbol {x}$ of length $n$ into a string $\boldsymbol {y}$ of length $N$ , such that each multiset of $k$ symbols from $\boldsymbol {x}$ has $k$ mutually disjoint recovering sets from $\boldsymbol {y}$. In this paper, we discuss new constructions of binary primitive batch codes. First, we develop novel explicit and random coding constructions of linear primitive batch codes based on finite geometries. Second, a new explicit coding construction of binary primitive batch codes based on bivariate lifted multiplicity codes is provided. For any $k=n^ \varepsilon $ with $\varepsilon \in (0,0.47)\setminus \{1/5,1/4\}$ , our proposed codes have a better trade-off between the redundancy and the parameters $k,n$ than previously known batch codes. [ABSTRACT FROM AUTHOR]

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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 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]

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]

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]

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]

We introduce two notions of discrepancy between binary vectors, which are not metric functions in general but nonetheless capture the mathematical structure of the binary asymmetric channel. These lead to two new fundamental parameters of binary error-correcting codes, both of which measure the probability that the maximum likelihood decoder fails. We then derive various bounds for the cardinality and weight distribution of a binary code in terms of these new parameters, giving examples of codes meeting the bounds with equality. [ABSTRACT FROM AUTHOR]

Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most $L$ . For odd $L\ge 3$ , an asymptotic upper bound on the rate of any such packing is proved. The resulting bound improves the best known bound (due to Blinovsky’1986) for rates below a certain threshold. The method is a superposition of the linear-programming idea of Ashikhmin, Barg, and Litsyn (that was previously used to improve the estimates of Blinovsky for $L=2$ ) and a Ramsey-theoretic technique of Blinovsky. As an application, it is shown that for all odd $L$ , the slope of the rate-radius tradeoff is zero at zero rate. [ABSTRACT FROM AUTHOR]

We say that a $q$ -ary length n$ code is non-overlapping if the set of non-trivial prefixes of codewords and the set of non-trivial suffices of codewords are disjoint. These codes were first studied by Levenshtein in 1964, motivated by applications in synchronization. More recently these codes were independently invented (under the name cross-bifix-free codes) by Bajić and Stojanović. We provide a simple construction for a class of non-overlapping codes which has optimal cardinality whenever n$ divides q$ . Moreover, for all parameters n$ and q$ , we show that a code from this class is close to optimal, in the sense that it has cardinality within a constant factor of an upper bound due to Levenshtein from 1970. Previous constructions have cardinality within a constant factor of the upper bound only when q$ is fixed. Chee, Kiah, Purkayastha, and Wang showed that a codewords; this bound is weaker than the Levenshtein bound. Their proof appealed to the application in synchronization: we provide a direct combinatorial argument to establish the bound of Chee et al. We also consider codes of short length, finding the leading term of the maximal cardinality of a non-overlapping code when $n$ is fixed and $q\rightarrow \infty $ . The largest cardinality of non-overlapping codes of lengths 3 or less is determined exactly. [ABSTRACT FROM AUTHOR]

Let ${T}_{ \epsilon }$ , $0 \le \epsilon \le 1/2$ , be the noise operator acting on functions on the boolean cube $\{0,1\}^{n}$. Let $f$ be a nonnegative function on $\{0,1\}^{n}$ and let ${q} \ge 1$. We upper bound the $\ell _{{q}}$ norm of ${T}_{ \epsilon } {f}$ by the average $\ell _{{q}}$ norm of conditional expectations of f, given sets of roughly $(1-2 \epsilon)^{{r}({q})} \cdot {n}$ variables, where r is an explicitly defined function of q. We describe some applications for error-correcting codes and for matroids. In particular, we derive an upper bound on the weight distribution of BEC-capacity achieving binary linear codes and their duals. This improves the known bounds on the linear-weight components of the weight distribution of constant rate binary Reed-Muller codes for all (constant) rates. [ABSTRACT FROM AUTHOR]

The study of subblock-constrained codes has recently gained attention due to their application in diverse fields. We present bounds on the size and asymptotic rate for two classes of subblock-constrained codes. The first class is binary constant subblock-composition codes (CSCCs), where each codeword is partitioned into equal sized subblocks, and every subblock has the same fixed weight. The second class is binary subblock energy-constrained codes (SECCs), where the weight of every subblock exceeds a given threshold. We present novel upper and lower bounds on the code sizes and asymptotic rates for the binary CSCCs and SECCs. For a fixed subblock length and small relative distance, we show that the asymptotic rate for CSCCs (respectively SECCs) is strictly lower than the corresponding rate for constant weight codes (CWCs) [respectively heavy weight codes (HWCs)]. Furthermore, for codes with high weight and low relative distance, we show that the asymptotic rate for CSCCs is strictly lower than that of SECCs, which contrasts with the fact that the asymptotic rate for the CWCs is equal to that of the HWCs. We also provide a correction to an earlier result by Chee et al. (2014) on the asymptotic CSCC rate. In addition, we present several numerical examples comparing the rates for the CSCCs and SECCs with those for the CWCs and HWCs. [ABSTRACT FROM AUTHOR]

We propose a new coded caching scheme where linear combinations of the file segments are cached at the users, for the cases where the number of files is no greater than the number of users. When a user requests a certain file in the delivery phase, the other file segments in the cached linear combinations can be viewed as interference. The proposed scheme combines rank-metric codes and maximum distance-separable codes to facilitate the decoding and elimination of the interference and also to simultaneously deliver useful contents to the intended users. The performance of the proposed scheme can be explicitly evaluated, and we show that it can achieve improvement over known memory-rate tradeoff achievable results in the literature in some regime; for certain special cases, the new memory-rate tradeoff points can be shown to be optimal. [ABSTRACT FROM PUBLISHER]

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs. [ABSTRACT FROM AUTHOR]

We study codes with parameters of $q$ -ary shortened Hamming codes, i.e., $(n=(q^{m}-q)/(q-1), q^{n-m}, 3)_{q}$. Firstly, we prove the fact mentioned in 1998 by Brouwer et al. that such codes are optimal, generalizing it to a bound for multifold packings of radius-1 balls, with a corollary for multiple coverings. In particular, we show that the punctured Hamming code is an optimal $q$ -fold packing with minimum distance 2. Secondly, for every admissible length starting from $n=20$ , we show the existence of 4-ary codes with parameters of shortened 1-perfect codes that cannot be obtained by shortening a 1-perfect code. [ABSTRACT FROM AUTHOR]

Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert–Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval [0,0.0668] . One of the two newly presented upper bounds improves on the best known upper bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval \tau \in (0,{1}/{8}] and meets the lower bound of {1}/{2} for \tau \geq 1/8 . Moreover, in a nonasymptotic regime, both upper bounds improve on the previously best known results on the largest size of t -grain-correcting codes of length $n$ , for certain values of n$ and t$ . Constructions of 1-grain-correcting codes based on a partitioning technique are presented for lengths up to 18. Finally, a lower bound of on the minimum redundancy of $\infty $ -grain-detecting codes of length $n$ is presented. [ABSTRACT FROM PUBLISHER]

We determine the exact value of the optimal symmetric rate point $(r, r)$ in the Dueck zero-error capacity region of the binary adder channel with complete feedback. We proved that the average zero-error capacity $r = h(1/2-\delta) \approx 0.78974$ , where $h(\cdot)$ is the binary entropy function and $\delta = 1/(2\log _{2}(2 + \sqrt {3}))$. Our motivation is a problem in quantitative group testing. Given a set of $n$ elements two of which are defective, the quantitative group testing problem asks for the identification of these two defectives through a series of tests. Each test gives the number of defectives contained in the tested subset, and the outcomes of previous tests are assumed known at the time of designing the current test. We establish that the minimum number of tests is asymptotic to $(\log _{2} n) / r$ as $n \to \infty $. [ABSTRACT FROM AUTHOR]

A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$. It is said to be list-recoverable for input list size $\ell $ if for every sufficiently large subset of at least $L$ codewords, there is a coordinate where the codewords take more than $\ell $ values. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below $q$ is the alphabet size, and $ \varepsilon > 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log _{q}(\ell) - \varepsilon $ requires list size $L \ge \ell ^{\Omega (1/ \varepsilon)}$ for list-recovery from input list size $\ell $. (2) A random linear code of rate $1 - h_{q}(p) - \varepsilon $ requires list size $L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $ for list-decoding from error fraction $p$. (3) A random binary linear code of rate $1 - h_{2}(p) - \varepsilon $ is list-decodable from average error fraction $p$ with list size with $L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018). [ABSTRACT FROM AUTHOR]

We give an explicit construction of length- $n$ binary codes capable of correcting the deletion of two bits that have size $2^{n}/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $\Omega (2^{n}/n^{4})$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $\Omega (2^{n}/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear. [ABSTRACT FROM AUTHOR]

Let p ≥ 2. We improve the bound ||ƒ||p/||ƒ||2 ≤ (p−1)s/2 for a polynomial ƒ of degree s on the boolean cube {0,1}n, which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of p and s, which is smaller than (p−1)s/2 for any p > 2 and s > 0. We show the new bound to be tight, within a smaller order factor, for the Krawchouk polynomial of degree s. This implies several nearly-extremal properties of Krawchouk polynomials and Hamming spheres (equivalently, Hamming balls). In particular, Krawchouk polynomials have (almost) the heaviest tails among all polynomials of the same degree and ℓ2 norm. The Hamming spheres have the following approximate edge-isoperimetric property: For all 1 ≤ s ≤ n/2, and for all even distances 0 ≤ i ≤ 2s(n-s)/n, the Hamming sphere of radius s contains, up to a multiplicative factor of O(i), as many pairs of points at distance i as possible, among sets of the same size (there is a similar, but slightly weaker and somewhat more complicated claim for all distances). This also implies that Hamming spheres are (almost) stablest with respect to noise among sets of the same size. In coding theory terms this means that a Hamming sphere (equivalently a Hamming ball) has the maximal probability of undetected error, among all binary codes of the same rate. We also describe a family of hypercontractive inequalities for functions on {0,1}n, which improve on the ‘usual’ “q → 2” inequality by taking into account the concentration of a function (expressed as the ratio between its ℓr norms), and which are nearly tight for characteristic functions of Hamming spheres. 1 This has to be interpreted with some care. [ABSTRACT FROM AUTHOR]

This article studies the cardinality of perfect multi deletion binary codes. The lower bound for any perfect deletion code with fixed code length and number of deletions, and the asymptotic achievability of Levenshtein’s upper bound are shown. [ABSTRACT FROM AUTHOR]

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate $1 - {H}(\text {p}) - \epsilon $ is $({p},\text {O}(1/\epsilon))$ -list-decodable with high probability. In this work, we show that such codes are $({p}, {H}({p})/\epsilon + 2)$ -list-decodable with high probability, for any $ {p} \in (0, 1/2)$ and $\epsilon > 0$. In addition to improving the constant in known list-size bounds, our argument—which is quite simple—works simultaneously for all values of p, while previous works obtaining $ {L} = \text {O}(1/\epsilon)$ patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain an essentially tight lower bound of $1/\epsilon $ on the list size of uniformly random codes; this implies that random linear codes are in fact more list-decodable than uniformly random codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear codes and (b) to prove a similar result for random linear rank-metric codes. [ABSTRACT FROM AUTHOR]

In this work, we study the problem of list decoding of insertions and deletions. We present a Johnson-type upper bound on the maximum list size. The bound is meaningful only when insertions occur. Our bound implies that there are binary codes of rate $\Omega (1)$ that are list-decodable from a 0.707-fraction of insertions. For any $\tau _{\mathsf {I}} \geq 0$ and $\tau _{\mathsf {D}} \in [0,1)$ , there exist $q$ -ary codes of rate $\Omega (1)$ that are list-decodable from a $\tau _{\mathsf {I}}$ -fraction of insertions and $\tau _{\mathsf {D}}$ -fraction of deletions, where $q$ depends only on $\tau _{\mathsf {I}}$ and $\tau _{\mathsf {D}}$. We also provide efficient encoding and decoding algorithms for list-decoding from $\tau _{\mathsf {I}}$ -fraction of insertions and $\tau _{\mathsf {D}}$ -fraction of deletions for any $\tau _{\mathsf {I}} \geq 0$ and $\tau _{\mathsf {D}} \in [0,1)$. Based on the Johnson-type bound, we derive a Plotkin-type upper bound on the code size in the Levenshtein metric. [ABSTRACT FROM AUTHOR]

Erasure codes play an important role in storage systems to prevent data loss. In this work, we study a class of erasure codes called Multi-Erasure Locally Recoverable Codes (ME-LRCs) for storage arrays. Compared to previous related works, we focus on the construction of ME-LRCs over small fields. Our main contribution is a general construction of ME-LRCs based on generalized tensor product codes, and an analysis of their erasure-correcting properties. A decoding algorithm tailored for erasure recovery is given, and correctable erasure patterns are identified. We then prove that our construction yields optimal ME-LRCs with a wide range of code parameters, and present some explicit ME-LRCs over small fields. Next, we show that generalized integrated interleaving (GII) codes can be treated as a subclass of generalized tensor product codes, thus defining the exact relation between these codes. Finally, ME-LRCs are investigated in a probabilistic setting. We prove that ME-LRCs based upon a generalized tensor product construction can achieve the capacity of a compound erasure channel consisting of a family of erasure product channels. [ABSTRACT FROM AUTHOR]

It is shown that there does not exist a projective triply-even binary code of length 59. This settles the last open length for projective triply-even binary codes, which therefore exist precisely for the lengths 15, 16, 30, 31, 32, 45–51, and ≥ 60. [ABSTRACT FROM AUTHOR]

In the random deletion channel, each bit is deleted independently with probability $p$. For the random deletion channel, the existence of codes of rate $(1-p)/9$ , and thus bounded away from 0 for any $p < 1$ , has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate $c_{0} (1-p)$ for an absolute constant $c_{0} > 0$. [ABSTRACT FROM AUTHOR]

It is known that, for large user word lengths, the auxiliary data can be used to recover most of the redundancy losses of Knuth’s simple balancing method compared with the optimal redundancy of balanced codes for the binary case. Here, this important result is extended in a number of ways. First, an upper bound for the amount of auxiliary data is derived that is valid for all codeword lengths. This result is primarily of theoretical interest, as it defines the probability distribution of the number of balancing indices that results in optimal redundancy. This result is equally valid for particular non-binary generalizations of Knuth’s balancing method. Second, an asymptotically exact expression for the amount of auxiliary data for the ternary case of a variable length realization of the modified balanced code construction is derived, that, in all respects, is the analogue of the result obtained for the binary case. The derivation is based on a generalization of the binary random walk to the ternary case and a simple modification of an existing generalization of Knuth’s method for the non-binary balanced codes. Finally, a conjecture is proposed regarding the probability distribution of the number of balancing indices for any alphabet size. [ABSTRACT FROM AUTHOR]

We consider the locally repairable codes (LRCs), aiming at sequentially recovering multiple erasures; in particular, we propose and study the so-called $(n, k, r, t)$ -sequential LRCs (SLRC) as an [n,k]$ linear code, where any t'~(\leq t)$ erasures can be sequentially recovered, each by r~(2\leq r

We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k \ge 2 , we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1-(2/(k+\sqrt k)) . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414 . Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1-\Theta (1/\sqrt k) , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for $k$ -ary codes as 1-\Theta (1/k)$ , since 1-1/k$ is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question. [ABSTRACT FROM PUBLISHER]

For a class \mathcal C of binary linear codes, we write \theta \mathcal {C}\colon (0,1) \to [0,({1}/{2})] for the maximum-likelihood decoding threshold function of \mathcal C , the function whose value at R \in (0,1) is the largest bit-error rate p that the codes in \mathcal C can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if \mathcal C is the class of cycle codes of graphs, then \theta \mathcal {C}(R) \le ({(1-\sqrt {R})^{2}}/{2(1+R)}) for each R , and show that equality holds only when $R$ is asymptotically achieved by the cycle codes of regular graphs. [ABSTRACT FROM AUTHOR]

We study certain combinatorial aspects of list-decoding, motivated by the exponential gap between the known upper bound (of \(O(1/\gamma )\) ) and lower bound (of \(\Omega _{p} (\log (1/\gamma ))\) ) for the list size needed to list decode up to error fraction \(p\) with rate \(\gamma \) away from capacity, i.e., \(1- h(p)-\gamma \) [here \(p\in (0, {1}/{2})\) and \(\gamma > 0\) ]. Our main result is that we prove that in any binary code \(C \subseteq \{ 0, 1 \} ^{n}\) of rate \(1- h(p) - \gamma \) , there must exist a set \( \mathcal {L}\subset C\) of \(\Omega _{p} (1/\sqrt {\gamma })\) codewords such that the average distance of the points in \( \mathcal {L}\) from their centroid is at most \(pn\) . In other words, there must exist \(\Omega _{p}(1/\sqrt {\gamma })\) codewords with low average radius. The standard notion of list decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average radius form is in itself quite natural; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding as follows. First, we give a short simple proof, over all fixed alphabets, of the above-mentioned \(\Omega _{p}(\log (1/\gamma ))\) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. Second, we show that one cannot improve the \(\Omega _{p}(\log (1/\gamma ))\) lower bound via techniques based on identifying the zero-rate regime for list-decoding of constant-weight codes [this is a typical approach for negative results in coding theory, including the \(\Omega _{p} (\log (1/\gamma ))\) list-size lower bound]. On a positive note, our \(\Omega _{p}(1/\sqrt {\gamma })\) lower bound for average-radius list-decoding circumvents this barrier. Third, we exhibit a reverse connection between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap \(\gamma \) of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (with weight bounded away from \(p\) ) and general codes. Fourth, we give simple second moment-based proofs that w.h.p. a list-size of \(\Omega _{p} (1/\gamma )\) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are \(\Omega _{p} (1/\gamma )\) for errors and \(\exp (\Omega _{p}(1/\gamma ))\) for erasures. [ABSTRACT FROM AUTHOR]