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]

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to construct pliable fractional repetition (FR) codes that are locally recoverable for distributed storage systems (DSSs). FR codes are integral in constructing a class of distributed storage codes with exact repair by transfer. Pliable FR codes are a new type of FR codes in which both the per-node storage and repetition degree can easily be adjusted simultaneously; thus, pliable FR codes are vital for DSSs in which parameters can dynamically change over time. However, the constructions of pliable FR codes with repair locality remain unknown. In addition, the tradeoffs between the code minimum distance of an FR code and its repair locality are not fully understood. To address these problems, this paper first presents general results regarding FR codes. Subsequently, this paper presents an improved Singleton-like bound for locally recoverable FR codes under an additional requirement that each node must be part of a local structure that, upon failure, allows it to be exactly recovered by a simple download process. Moreover, this paper proposes a construction of locally recoverable FR codes that can achieve the proposed Singleton-like bound; this construction is based on bipartite graphs with a given girth. In particular, this paper also proposes a general bipartite-graph-based approach to constructing optimal pliable FR codes with and without repair localities; in this approach, a new family of bipartite graphs, called matching-feasible graphs, is introduced. Finally, this paper proposes the explicit constructions of optimal pliable FR codes by using a family of matching-feasible graphs with arbitrary large girth. Notably, in addition to attaining a Singleton-like bound for FR codes, the explicit pliable FR codes are optimal locally recoverable FR codes from two perspectives of repair locality. The explicit pliable FR codes can also be used as FR batch codes to provide load balancing in DSSs. [ABSTRACT FROM AUTHOR]

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [ABSTRACT FROM AUTHOR]

The Euclidean hull of a linear code $C$ is the intersection of $C$ with its Euclidean dual $C^\perp $. The hull with low dimensions gets much interest due to its crucial role in determining the complexity of algorithms for computing the automorphism group of a linear code and for checking permutation equivalence of two linear codes. The Euclidean hull of a linear code has been applied to the so-called entanglement-assisted quantum error-correcting codes (EAQECCs) via classical error-correcting codes. In this paper, we firstly consider linear codes with one-dimensional Euclidean hull from algebraic geometry codes, and then present a general method to construct linear codes with arbitrary dimensional Euclidean hull. Some new EAQECCs are presented. [ABSTRACT FROM AUTHOR]

Maximum distance profile codes over finite non-binary fields have been introduced and thoroughly studied in the last decade. These codes have the property that their column distances are maximal among all codes of the same rate and degree. In this paper, we aim at studying this fundamental concept in the context of convolutional codes over a finite ring. We extensively use the concept of $p$ -encoder to establish the theoretical framework and derive several bounds on the column distances. In particular, a method for constructing (not necessarily free) maximum distance profile convolutional codes over ${\mathbb Z}_{p^{r}}$ is presented. [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]

Information retrieval in associative memories was studied in a recent paper by Yaakobi and Bruck (2012). Associations between memory entries give us the t -neighbourhood of an entry. In their model, an information unit is retrieved from the memory with the aid of input clues, which are chosen from a reference set. In this paper, we consider the situation where the information unit is found unambiguously using the associated t -neighbourhoods of the input clues. A varying number of input clues are allowed, but a limit mu on the maximum number of them is imposed. Of course, we would like mu to be as small as possible. We consider the problem over the binary Hamming space \mathbb F^n and focus on the minimum of mu , denoted by $\nu (n;t)$ . Using linear reference sets, we show that $\nu (n;2) \leq 5$ for any $n \geq 9$ . We also give infinite families of reference sets, which provide good bounds on $\nu (n;t)$ for $t=3$ . In addition, efficient methods are given to obtain bounds on $\nu (n;t)$ for any $t$ from known reference sets. We also discuss the applications of this model to the Levenshtein’s sequence reconstruction problem and the sensor network monitoring. [ABSTRACT FROM AUTHOR]

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the $q^\ell $ -incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the $q^\ell $ -incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all $[n,k]$ linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all $[n,nR]$ linear codes. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes a novel concatenated coding scheme for enabling error resilience in two distributed storage settings: one being storage using existing regenerating codes and the second being storage using locally repairable codes. The concatenated coding scheme brings together a maximum rank distance code as an outer code and either a globally regenerating or a locally repairable code as an inner code. In addition, error resilience for combination of locally repairable codes with regenerating codes is considered. This concatenated coding system is designed to handle two different types of adversarial errors: the first type includes an adversary that can replace the content of an affected node only once; while the second type studies an adversary that is capable of polluting data an unbounded number of times. The paper establishes an upper bound on the resilience capacity for a locally repairable code. This paper also proves that the proposed concatenated coding approach attains the upper bound on the resilience capacity in the presence of the first type of adversary for both minimum storage regenerating codes and locally repairable codes. Further, this paper presents mechanisms that combine the presented concatenated coding scheme with subspace signatures to achieve error resilience for the second type of errors. [ABSTRACT FROM PUBLISHER]

In this paper, we study the decoding of dual-containing codes from Hermitian tower and applications to quantum codes. The contribution of this paper is threefold. First, we construct the quantum stabilizer codes from the Hermitian tower. Second, we provide a deterministic decoding algorithm with decoding radius that almost achieves the optimal decoding radius, i.e., $(1-R)/4$ , where $R$ is the rate. Last and most importantly, we present a Monte Carlo algorithm with decoding radius roughly equal to $(1-R)/3$ , which is beyond the optimal decoding radius $(1-R)/4$ . There are several features in this paper. First of all, we employ a differential for the Hermitian tower. This differential plays a crucial role for decoding. We also extend our decoding by passing to the constant field extension. This constant field extension makes the decoding work perfectly. [ABSTRACT FROM PUBLISHER]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [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]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

In this paper, the basic function field of an asymptotically optimal tower of function fields by Garcia and Stichtenoth is studied, where bases of one-point linear systems can be explicitly constructed. A representation of finite GF(q^2) -rational points on the associated plane curve is derived in this paper. This representation is exploited to extend the use of Horner’s loops and the mechanism of Chien search in the decoding of Reed–Solomon codes for syndrome generation and error-location search, respectively, to algebraic-geometry codes built on the plane Garcia–Stichtenoth curve. [ABSTRACT FROM AUTHOR]

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance. [ABSTRACT FROM PUBLISHER]

Golay complementary sequences and complementary sets have been proposed to deal with the high peak-to-average power ratio (PAPR) problem in orthogonal frequency division multiplexing (OFDM) system. The existing constructions of complementary sets based on generalized Boolean functions are limited to lengths, which are powers of two. In this paper, we propose novel constructions of binary and nonbinary complementary sets of non-power-of-two length. Regardless of whether or not the length of the complementary set is a power of two, its PAPR is still upper bounded by the size of the complementary set. Therefore, the constructed complementary sets can be applied in practical OFDM systems where the number of used subcarriers is not a power of two. In addition, while the binary Golay complementary pairs exist only for limited lengths, the constructed binary complementary sets of size 4 exist for more lengths with PAPR at most 4. [ABSTRACT FROM PUBLISHER]

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $\sigma $ complementary dual ($\sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $\sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q > 2$ , all $q$ -ary linear codes are $\sigma $ -LCD, and for every binary linear code $\mathcal C$ , the code $\{0\}\times \mathcal C$ is $\sigma $ -LCD. Furthermore, we study deeply $\sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $\sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $\sigma $ -LCD GQC codes. Finally, we focus on $\sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $\sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $\sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. [ABSTRACT FROM AUTHOR]

Let $p$ be a prime, $s$ be a positive integer, and $\mathcal {R}$ be a finite commutative chain ring with the characteristic as a power of $p$. For a unit $\lambda \in \mathcal {R},~\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are ideals of the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $. In this paper, we derive necessary and sufficient conditions under which the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring. When $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring, all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are known. In this paper, we establish the algebraic structures of all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ when $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a non-chain ring. We also determine the number of codewords in each of these codes. Using their algebraic structures, we obtain symbol-pair distances, Rosenbloom–Tsfasman (RT) distances, and RT weight distributions of all constacyclic codes of length $p^{s}$ over $\mathcal {R}$. Apart from this, we derive necessary and sufficient conditions under which a constacyclic code of length $p^{s}$ over $\mathcal {R}$ is maximum-distance separable with respect to the: 1) Hamming metric; 2) symbol-pair metric; and 3) RT metric. We also provide an algorithm to decode the constacyclic codes of length $p^{s}$ over $\mathcal {R}$ using the known decoding algorithms of linear codes over finite fields with respect to the Hamming, symbol-pair, and RT metrics. [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]

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]

In this paper, we introduce a model of a distributed storage system that is locally recoverable from any single server failure. Unlike the usual local recovery model of codes for distributed storage, this model accounts for the fact that each server or storage node in a network is connectable to only some, and not all other, nodes. This may happen for reasons such as physical separation, inhomogeneity in storage platforms, and so forth. We estimate the storage capacity of both undirected and directed networks under this model and propose some constructive schemes. From a coding theory point of view, we show that this model is approximately dual of the well-studied index coding problem. Furthermore, in this paper, we extend the above model to handle multiple server failures. Among other results, we provide an upper bound on the minimum pairwise distance of a set of words that can be stored in a graph with the local repair guarantee. The well-known impossibility bounds on the distance of locally recoverable codes follow from our result. [ABSTRACT FROM PUBLISHER]

In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a \delta s -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the \delta s -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the concept of spatially coupled turbo-like codes (SC-TCs) as the spatial coupling of a number of turbo-like code ensembles. In particular, we consider the spatial coupling of parallel concatenated codes, introduced by Berrou et al., and that of serially concatenated codes (SCCs), introduced by Benedetto et al. Furthermore, we propose two extensions of braided convolutional codes (BCCs), and a class of turbo-like codes which have an inherent spatially coupled structure, to higher coupling memories, and show that these yield improved belief propagation (BP) thresholds as compared with the original BCC ensemble. We derive the exact density evolution (DE) equations for SC-TCs and analyze their asymptotic behavior on the binary erasure channel. We also consider the construction of families of rate-compatible SC-TC ensembles. Our numerical results show that the threshold saturation of the BP decoding threshold to the maximum a posteriori threshold of the underlying uncoupled ensembles occurs for large enough coupling memory. The improvement of the BP threshold is especially significant for SCCs and BCCs, whose uncoupled ensembles suffer from a poor BP threshold. For a wide range of code rates, SC-TCs show close-to-capacity performance as the coupling memory increases. We further give a proof of threshold saturation for SC-TC ensembles with identical component encoders. In particular, we show that the DE of SC-TC ensembles with identical component encoders can be properly rewritten as a scalar recursion. This allows us to define potential functions and prove threshold saturation using the proof technique recently introduced by Yedla et al. [ABSTRACT FROM PUBLISHER]

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by ${t}$ -criss-cross deletions defined as any combination of ${t_{\mathrm {r}}}$ row and ${t_{\mathrm {c}}}$ column deletions such that ${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$ for a given $t$. We show an equivalence between correcting ${t}$ -criss-cross deletions and ${t}$ -criss-cross insertions and show that a code correcting ${t}$ -criss-cross insertions/deletions has redundancy at least ${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a ${t}$ -criss-cross insertion/deletion correcting code with redundancy bounded from above by ${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary ${t}$ -deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient. [ABSTRACT FROM AUTHOR]

Since discovery of Goppa geometric codes, people have been asking the question: are there different constructions of block codes from algebraic curves that give the same parameters as Goppa geometric codes. Despite of great effort by researchers, no such constructions have been found so far. Although in literature, there are many constructions of block code from algebraic curves, most of them are quite different from the one by Goppa in nature and thus they have different parameters. Some of these constructions have the same parameters as Goppa geometric codes, however it was proved that these are essentially the same codes defined by Goppa. In this paper, we solve this question for the case where the characteristic of the ground field is 2, namely, we present a different construction of block codes from algebraic curves that give the same parameters as Goppa geometric codes for the characteristic 2 case. [ABSTRACT FROM PUBLISHER]

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded $k$ data symbols using an $(n,k)$ code with code length $n$ and dimension $k$. During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmission bandwidth, namely, we can only download an $\alpha $ proportion of the corrupted codeword. For a given $\alpha $ , our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read $\alpha n$ coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any $\lfloor (\alpha n-k)/2\rfloor $ errors. In this paper we show that we can instead download an $\alpha $ proportion from each of the codeword’s coordinates. For a well-designed MDS code, this method can guarantee recovery from $\lfloor (n-k/\alpha)/2 \rfloor $ errors, which is $1/\alpha $ times more than the naive method, and is also the maximum number of errors that an $(n,k)$ code can correct by downloading only an $\alpha $ proportion of the codeword. We present two families of such optimal constructions and decoding schemes of which one is based on Interleaved Reed-Solomon codes and the other on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an $\alpha $ proportion of the corrupted codeword. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size. [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]

For the recently developed quasi-reversible BCH codes with long lengths and high error-correcting capability, this paper is aimed at proposing a new and faster decoding procedure. It consists of four steps: 1) compute the consecutive syndromes; 2) calculate the syndrome functions by the forward and backward recursions; 3) solve a linear subsystem together with one matrix multiplication in order to find an error-locator polynomial; 4) determine the errors from the obtained polynomial by using the root-finding algorithm. This procedure, especially in Steps 2 and 3, differs greatly from the conventional procedures, which determine an error-locator polynomial directly from solving a linear system with the aid of the consecutive syndromes. The key idea behind this decoding technique is that the computational complexity of such a small subsystem instead of an originally large linear system can be significantly reduced, although there are additional forward and backward syndrome calculations with low complexity increasing. Finally, the illustrative examples and numerical simulations can be helpful to demonstrate the accuracy and efficacy of the presented decoding technique at different error-correcting capabilities. [ABSTRACT FROM AUTHOR]

Transmissions across asynchronous communication channels are subject to delay injection attacks, which can cause an arbitrary number of skews. That is, such attacks can cause an arbitrary number of transmitted signals to arrive after the first signal of the next transmission has arrived. The (common) assumption that despite the delays, all signals from the $i$ th transmission arrive at the decoder before any signal from the (i+2){\text{nd}} transmission arrives is called a no switch assumption. This paper presents a self-synchronizing, zero-latency, zero-error coding scheme that requires no acknowledge and can decode transmissions distorted by an arbitrary number of skews that obey this no switch assumption. The rate associated with the coding scheme provides a lower bound of 0.6942 for the (zero-error) capacity of such a channel. It is further shown that zero-error channel capacity of the channel is upper bounded by 0.7248. Finally, this paper presents bounds on the (zero-error) capacity of a channel for which the number of transmissions that can mix with one another is large. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with $r$ redundancy nodes can correct any $r$ node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, $e$ erasures are a more likely failure event, for some $1 \le e < r$ . Hence, a natural question is how much information do we need to access in order to rebuild $e$ storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of $e$ erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of $1/r$ for the rebuilding of any systematic node when $e=1$ ; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any $r$ erasures can be corrected by accessing some of the remaining information, and any $e=1$ erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of $e/r$ for systematic nodes of MDS codes, for any $1 \le e \le r$ ; 2) we construct systematic codes that achieve optimal rebuilding ratio of $1/r$ , for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances. [ABSTRACT FROM AUTHOR]

In this paper, list decoding of crisscross errors in arrays over finite fields is considered. For this purpose, the so-called cover metric is used, where the cover of a matrix is a set of rows and columns which contains all non-zero elements of the matrix. A Johnson-like upper bound on the maximum list size in the cover metric is derived, showing that the list of codewords has polynomial size up to a certain radius. Furthermore, a simple list decoding algorithm for a known optimal code construction is presented, which decodes errors in the cover metric up to our upper bound. These results reveal significant differences between the cover metric and the rank metric and show that the cover metric is more suitable for correcting crisscross errors. [ABSTRACT FROM PUBLISHER]

In this paper, we obtain an improved lower bound on the error exponent of the memoryless multiple-access channel via the use of linear codes, thus demonstrating that structure can be beneficial even when capacity may be achieved via random codes. We show that if the multiple-access channel is additive over a finite field, then any error probability, and hence any error exponent, achievable by a linear code for the associated single-user channel, is also achievable for the multiple-access channel. In particular, linear codes allow to attain joint expurgation, and hence, attain the single-user expurgated exponent of the single-user channel, whenever the latter is achieved by a uniform distribution. Thus, for additive channels, at low rates, where expurgation is needed, our approach strictly improves performance over previous results, where expurgation was used for at most one of the users. Even when the multiple-access channel is not additive, it may be transformed into such a channel. While the transformation is information-lossy, we show that the distributed structure gain in some “nearly additive” cases outweighs the loss. Finally, we apply a similar approach to the Gaussian multiple-access channel. While we believe that due to the power constraints, it is impossible to attain the single-user error exponent, we do obtain an improvement over the best known achievable error exponent, given by Gallager, for certain parameters. This is accomplished using a nested lattice triplet with judiciously chosen parameters. [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]

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]

Let $q=p^{e}$ be a prime power and $\ell $ be an integer with $0\leq \ell \leq e-1$. The $\ell $ -Galois hull of classical linear codes is a generalization of the Euclidean hull and Hermitian hull. We provide a necessary and sufficient condition under which a codeword of a GRS code or an extended GRS code belongs to its $\ell $ -Galois dual code, generalizing both the Euclidean case and Hermitian case in the literature. By using four different tools: 1) the norm mapping from $\mathbb {F}_{q}^{\ast }$ to $\mathbb {F}_{p^{\ell }}^{\ast }$ ; 2) the direct product of two cyclic subgroups; 3) the coset decomposition of a cyclic group; 4) an additive subgroup of $\mathbb {F}_{q}$ and its cosets, we construct eleven families of $q$ -ary MDS codes with $\ell $ -Galois hulls of arbitrary dimensions, and give the related eleven families of $[[n,k,d;c]]_{q}$ entanglement-assisted quantum error-correcting codes (EAQECCs) with relatively large minimum distance in the sense that $2d=n-k+2+c$. We show that developing the theory on $\ell $ -Galois hulls of $q$ -ary MDS codes in this paper enables us to obtain new $q$ -ary EAQECCs with different kinds of length sets via different $\ell $ , where $2\ell \mid e$. [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]

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]

In this paper, we propose a characterization for non-elementary trapping sets (NETSs) of low-density parity-check (LDPC) codes. The characterization is based on viewing an NETS as a hierarchy of embedded graphs starting from an ETS. The characterization corresponds to an efficient search algorithm that under certain conditions is exhaustive. As an application of the proposed characterization/search, we obtain lower and upper bounds on the stopping distance $s_{\min }$ of LDPC codes. We examine a large number of regular and irregular LDPC codes and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, $s_{\min }$. Finding $s_{\min }$ , or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm. For a constant degree distribution and range of search, the worst case computational complexity of the proposed search algorithms for finding NETSs and stopping sets is linear in the code’s block length $n$. The average search complexity for stopping sets, however, is constant in $n$ , if the simple cycles required as input to the search algorithm are available. [ABSTRACT FROM AUTHOR]

The study of constant-weight codes in $\ell _{1}$ -metric was motivated by the duplication-correcting problem for data storage in live DNA. It is interesting to determine the maximum size of a code given the length ${n}$ , weight ${w}$ , minimum distance ${d}$ and the alphabet size ${q}$. In this paper, based on graph decompositions, we determine the maximum size of ternary codes with constant weight w and distance $2{w}-2$ for all sufficiently large length ${n}$. Previously, this was known only for a very sparse family ${n}$ of density $4/{w}({w}-1)$. [ABSTRACT FROM AUTHOR]

A Goppa code over $\Bbb F_{q^{m}}$ is a well-known subclass of algebraic error-correcting code. If $m=1$ , then it is a generalized Reed-Solomon(GRS) code and its dual code is called a GRS code via a Goppa code. In this paper, we give a necessary and sufficient condition that the dual codes of GRS codes via (expurgated) Goppa codes are also GRS codes via Goppa codes. Under the above condition, we show that the hulls of GRS codes via Goppa codes are still GRS codes via Goppa codes. As an application, we characterize LCD GRS codes and self-dual GRS codes under the above condition. Some numerical examples are also presented to illustrate our main results. Moreover, we also apply our result to entanglement-assisted quantum error correcting codes (EAQECCs) and obtain two new families of MDS EAQECCs with arbitrary parameters. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

Multi-permutations and in particular permutations appear in various applications in an information theory. New applications, such as rank modulation for flash memories, have suggested the need to consider error-correcting codes for multi-permutations. In this paper, we study systematic error-correcting codes for multi-permutations in general and for permutations in particular. For a given number of information symbols k , and for any integer t , we present a construction of (k+r,k) systematic t -error-correcting codes, for permutations of length $k+r$ , where the number of redundancy symbols $r$ is relatively small. In particular, for a given $t$ and for sufficiently large $k$ , we obtain $r=t+1$ , while a lower bound on the number of redundancy symbols is shown to be $t$ . The same construction is also applied to obtain related systematic error-correcting codes for any types of multi-permutations. [ABSTRACT FROM AUTHOR]

This paper is devoted to studying two main problems: 1) computing the apparent distance of an Abelian code and 2) giving a notion of Bose, Ray-Chaudhuri, Hocquenghem (BCH) multivariate code. To do this, we first strengthen the notion of an apparent distance by introducing the notion of a strong apparent distance; then, we present an algorithm to compute the strong apparent distance of an Abelian code, based on some manipulations of hypermatrices associated with its generating idempotent. Our method uses less computations than those given by Camion and Sabin; furthermore, in the bivariate case, the order of computation complexity is reduced from exponential to linear. Then, we use our techniques to develop a notion of a BCH code in the multivariate case, and we extend most of the classical results on cyclic BCH codes. Finally, we apply our method to the design of Abelian codes with maximum dimension with respect to a fixed apparent distance and a fixed length. [ABSTRACT FROM AUTHOR]

An error model with asymmetric single error with magnitude four is considered. In this paper, the constructions of codes correcting single error of magnitude four over $\mathbb {Z}_{2^{{a}}3^{{b}}{r}}$ are studied which is equivalent to construct $B_{1}[{4}](2^{{a}}3^{{b}}{r})$ sets. Firstly, we reduce the construction of a maximal size ${B}_{1}[{4}](2^{{a}}3^{{b}}{r})$ set for ${a}\geq 4$ and $ \gcd ({r},6)=1$ to the construction of a maximal size ${B}_{1}[{4}](2^{{a}-3}3^{{b}}{r})$ set. Furthermore, we will show that maximal size ${B}_{1}[{4}](8\cdot 3^{{b}}{r})$ sets can be reduced to maximal size ${B}_{1}[{4}](3^{{b}}{r})$ sets and also give lower bounds of maximal size ${B}_{1}[{4}](12{r})$ and ${B}_{1}[{4}](2\cdot 3^{{b}}{r})$ sets. Finally, we give a necessary and sufficient condition on the existence of perfect ${B}_{1}[{4}]({p})$ set for prime $p$. [ABSTRACT FROM AUTHOR]

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with m > 2 strings (where a previous paper considered m = 2) in asymptotic terms, where code-words are taken from an error-correcting code. Thus, we find the trade-off between the design minimum distance, the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease coding redundancy, or the required number of reads, or both. [ABSTRACT FROM AUTHOR]

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder’s sequence X differs from the decoder’s sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size. [ABSTRACT FROM AUTHOR]

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem: the problem of finding fractional transversals. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This paper studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then the upper bound by this method coincides with the well-known sphere packing bound and thus is called here the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. The art of finding the exact upper bound (or slightly weaker ones) is the assignment of weights to the hypergraph’s vertices in a way that they satisfy the constraints in the linear programming problem. In order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases significantly reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the $Z$ channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the nonbinary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion channel, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for single-deletion-correcting codes. Since the deletion and grain-error channels have a similar structure for a single error, we also improve upon the existing upper bounds on single-grain error-correcting codes. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case. [ABSTRACT FROM AUTHOR]