Search

We propose a successive cancellation list (SCL) encoding and decoding scheme for the Gelfand Pinsker (GP) problem based on the known nested polar coding scheme. It applies SCL encoding for the source coding part, and SCL decoding with a properly defined CRC for the channel coding part. The scheme shows improved performance compared to the existing method. A known issue with nested polar codes for binary dirty paper is the existence of frozen channel code bits that are not frozen in the source code. These bits need to be retransmitted in a second phase of the scheme, thus reducing the rate and increasing the required blocklength. We provide an improved bound on the size of this set, and on its scaling with respect to the blocklength, when the Bhattacharyya parameter of the test channel used for source coding is sufficiently large, or the Bhattacharyya parameter of the channel seen at the decoder is sufficiently small. The result is formulated for an arbitrary binary-input memoryless GP problem, since unlike the previous results, it does not require degradedness of the two channels mentioned above. Finally, we present simulation results for binary dirty paper and noisy write once memory codes. [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]

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

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [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, 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]

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

We consider the problem of constructing binary codes for correcting deletions that are localized within certain parts of the codeword that are unknown a priori. The model that we study is when $\delta \leq w$ deletions are localized in a window of size $w$ bits. These $\delta $ deletions do not necessarily occur in consecutive positions, but are restricted to the window of size $w$. The localized deletions model is a generalization of the bursty model, in which all the deleted bits are consecutive. In this paper, we construct new explicit codes for the localized model, based on the family of Guess & Check codes which was previously introduced by the authors. The codes that we construct can correct, with high probability, $\delta \leq w$ deletions that are localized in a single window of size $w$ , where $w$ grows with the block length. Moreover, these codes are systematic; have low redundancy; and have efficient deterministic encoding and decoding algorithms. We also generalize these codes to deletions that are localized within multiple windows in the codeword. [ABSTRACT FROM AUTHOR]

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

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

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

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]

Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction $\text{D}'$ whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction $\text{D}'$ is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel. [ABSTRACT FROM AUTHOR]

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

This paper studies the parameters for which binary Reed–Muller (RM) codes can be decoded successfully on the binary erasure channel and binary symmetry channel, and, in particular, when can they achieve capacity for these two classical channels. Necessarily, this paper also studies the properties of evaluations of multivariate $GF(2)$ polynomials on the random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about the square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about $E(m,r)$ , the matrix whose rows are the truth tables of all the monomials of degree $\leq r$ in $m$ variables. What is the most (resp. least) number of random columns in $E(m,r)$ that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees $r$ , which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code $C$ of sufficiently high rate, we construct a new code $C'$ obtained by tensorizing $C$ , such that for every subset $S$ of coordinates, if $C$ can recover from erasures in $S$ , then $C'$ can recover from errors in $S$ . Specializing this to the RM codes and using our results for erasures imply our result on the unique decoding of the RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent bounds from constant degree to linear degree polynomials. [ABSTRACT FROM PUBLISHER]

In this paper, code decompositions (a.k.a. code nestings) are used to design binary polarization kernels. The proposed kernels are in general nonlinear. They provide a better polarization exponent than the previously known kernels of the same dimensions. In particular, nonlinear kernels of dimensions 14, 15, and 16 are constructed and are shown to have optimal asymptotic error-correction performance. The optimality is proved by showing that the exponents of these kernels achieve a new upper bound that is developed in this paper. [ABSTRACT FROM AUTHOR]

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

In this paper, a general binary-input binary-output channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are calculated for the case of an $(1,\infty )$ -RLL input constraint, that is, the input sequence contains no consecutive ones. These results are obtained via explicit solution of an equivalent dynamic programming optimization problem. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: history bits, which captures the memory embedded in our setting, and message-interval splitting, which eases the analysis of the scheme. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that is shown to achieve capacity. For the input-constrained binary symmetric channel, we show using our capacity formula that feedback increases capacity when the cross-over probability is small. [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]

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

In this paper, we present a fast Fourier transform algorithm over extension binary fields, where the polynomial is represented in a non-standard basis. The proposed Fourier-like transform requires \mathcal O(h\lg (h)) field operations, where h is the number of evaluation points. Based on the proposed Fourier-like algorithm, we then develop the encoding/decoding algorithms for (n=2^{m},k) Reed–Solomon erasure codes. The proposed encoding/erasure decoding algorithm requires \mathcal {O}(n\lg (n))$ , in both additive and multiplicative complexities. As the complexity leading factor is small, the proposed algorithms are advantageous in practical applications. Finally, the approaches to convert the basis between the monomial basis and the new basis are proposed. [ABSTRACT FROM AUTHOR]

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