In this work, we present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distribution that arises in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, at code lengthn, we can compute the weight distribution of anypolar cosetsin timeO(n2). We show that any polar code can be represented as a disjoint union of such polar cosets; moreover, this representation extends to polar codes with dynamically frozen bits. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call themixing factor. To upper bound the complexity of our algorithm for polar codes being decreasing monomial codes, we study the range of their mixing factors. We prove that among all decreasing monomial codes with rates at most 1/2, self-dual Reed-Muller codes have the largest mixing factors. To further reduce the complexity of our algorithm, we make use of the fact that, as decreasing monomial codes, polar codes have a large automorphism group. That automorphism group includes the block lower-triangular affine group (BLTA), which in turn contains the lower-triangular affine group (LTA). We prove that a subgroup of LTA acts transitively on certain subsets of decreasing monomial codes, thereby drastically reducing the number of polar cosets that we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of polar codes at lengthn= 128.

Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. PCR amplifies the virus DNA 40 times to produce measurements of viral loads that span seven orders of magnitude. Unfortunately, the outputs of these tests are imprecise and therefore quantitative group testing methods, which rely on precise measurements, are not applicable. Motivated by the ever-increasing demand to identify individuals infected with SARS-CoV-19, we propose a new model that leverages tropical arithmetic to characterize the PCR testing process. Our proposed framework, termed tropical group testing, overcomes existing limitations of quantitative group testing by allowing for imprecise test measurements. In many cases, some of which are highlighted in this work, tropical group testing is provably more powerful than traditional binary group testing in that it requires fewer tests than classical approaches, while additionally providing a mechanism to identify the viral load of each infected individual. It is also empirically stronger than related works that have attempted to combine PCR, quantitative group testing, and compressed sensing.

Polar codes approach channel capacity provably and empirically and are thereby a constituent code of the 5G standard. Compared to low-density parity-check codes, however, the performance of short-length polar codes have rooms for improvement that could hinder its adoption by a wider class of applications. As part of the program that addresses the performance issue at short length, it is crucial to understand how fast binary memoryless symmetric channels polarize. A number, called scaling exponent, was defined to measure the speed of polarization and several estimates of the scaling exponent were given in literature. As of 2022, the tightest overestimate is 4.714 made by Mondelli, Hassani, and Urbanke in 2015. We lower the overestimate to 4.63. The idea behind this improvement is that, instead of describing the relation between a channel${W}$and its children${W}^ {\scriptscriptstyle {\boxed {\star}}}$and${W}^ {\bigcirc \!\!\! \star}$, we describe the relation between${W}$and its grandchildren$ {W}^{\scriptscriptstyle {\boxed {\star}} \, {\scriptscriptstyle {\boxed {\star}}} }$,${W}^{\scriptscriptstyle {\boxed {\star}}\, {{\bigcirc \!\! \star} }}$,${W}^{{\bigcirc \!\!\! \star}\,\,{\scriptscriptstyle {\boxed {\star}}} }$, and$ {W}^{{\bigcirc \!\!\! \star}\,{\bigcirc \!\!\! \star} }$. By doing so, the evolution of channels becomes “less Markovian” and hence more tighter inequalities can be obtained.

Motivated by DNA-based applications, we generalize the bee identification problem proposed by Tandon et al. (2019). In this setup, we transmit all M codewords from a codebook over some channel and each codeword results in N noisy outputs. Then our task is to identify each codeword from the MN noisy outputs.First, via a reduction to a minimum-cost flow problem on a related flow network ${\mathcal{G}_N}$, we show that the problem can be solved in O(M3) time in the worst case. Next, we consider the deletion channel and study the expected number of edges in the network ${\mathcal{G}_N}$. Specifically, we obtain closed expressions for this quantity for certain codebooks and when the codebook comprises all binary words, we show that this quantity is sub-quadratic when the deletion probability is less than 1/2. This then implies that the expected running time for this codebook is o(M3). For other codebooks, we develop methods to compute the expected number of edges efficiently. Finally, we adapt classical peeling-decoding techniques to reduce the number of nodes and edges in ${\mathcal{G}_N}$.

An error correcting code exhibits the t-Disjoint Repair Group Property (t-DRGP) (for message symbols) if it is possible to recover a single symbol of a codeword (message) in t ways, each from a disjoint set of symbols of the codeword. Codes with the DRGP have found applications in private information retrieval (PIR) and distributed storage, and are related to several notions of locality in coding theory. In this work we prove an impossibility result for codes with the DRGP. We show that the redundancy of any code with the t-DRGP is ${{\Omega }}(\sqrt n )$ for all t ≥ 2. Our bound is tight, even including the leading constant, for t = 2, and is tight up to a constant factor for t = O(1). We also show an analogous result for binary codes with the t-DRGP for message symbols, which has applications to PIR.These results first appeared in 2016 and were never published. As our results have not yet been improved upon, and have been referenced by multiple works over the years, we are prompted to publish them now. We hope that publishing these results now will spur more work in the area, and in particular will lead to improved bounds.

Polymerase chain reaction (PCR) testing is the gold standard for diagnosing COVID-19. Unfortunately, the outputs of these tests are imprecise and therefore quantitative group testing methods, which rely on precise measurements, are not applicable. Motivated by the ever-increasing demand to identify individuals infected with SARS-CoV-19, we propose a new model that leverages tropical arithmetic to characterize the PCR testing process. In many cases, some of which are highlighted in this work, tropical group testing is provably more powerful than traditional binary group testing in that it requires fewer tests than classical approaches, while additionally providing a mechanism to identify the viral load of each infected individual.

Bit-interleaved coded modulation (BICM) and multilevel coded modulation (MLC) are commonly used to combine polar codes with high order modulation. While BICM benefits from simple design and the separation of coding and modulation, MLC shows better performance under successive-cancellation de-coding. In this paper we propose a hybrid polar coded modulation scheme that lies between BICM and MLC, wherein a fraction of bits are assigned to set-partition (SP) labeling and the remaining bits are assigned for Gray labeling. The SP labeled bits undergo sequential demodulation, using iterative demodulation and polar decoding similar to MLC, whereas the Gray labeled bits are first demodulated in parallel and then sent for decoding similar to BICM. Either polar codes or other channel codes (such as LDPC codes) can be used for the Gray labeled bits. For length 2048 rate 1/2 polar code on 256-QAM, the performance gap be-tween BICM (Gray labeling only) and MLC (SP labeling only) can be almost fully closed by the hybrid scheme. Notably, the hybrid scheme has a significant latency advantage over MLC. These performance gains make the proposed scheme attractive for future communication systems such as 6G.

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems. In this work, in order to reduce the wear out of the cells, we propose a new coding scheme, called endurance-limited memories (ELM) codes, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an$\ell $-change$t$-write ELM code is a coding scheme that allows to write$t$messages into some$n$binary cells while guaranteeing that each cell is programmed at most$\ell $times. In case$\ell =1$, these codes coincide with the well-studied write-once memory (WOM) codes. We study some models of these codes which depend upon whether the encoder knows on each write the number of times each cell was programmed, knows only the memory state, or even does not know anything. For the decoder, we consider these similar three cases. We fully characterize the capacity regions and the maximum sum-rates of three models where the encoder knows on each write the number of times each cell was programmed. In particular, it is shown that in these models the maximum sum-rate is$\log \sum _{i=0}^{\ell } {\binom{t }{ i}}$. We also study and expose the capacity regions of the models where the decoder is informed with the number of times each cell was programmed. Finally we present the most practical model where the encoder read the memory before encoding new data and the decoder has no information about the previous states of the memory.

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on that trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. This gives a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length. We conclude by showing that this scheme can achieve capacity on the deletion channel by proving that the capacity of the deletion channel can be achieved by a sequence of regular hidden-Markov input distributions.

Transverse-read is a novel technique to detect the number of ‘1's stored in domain wall memory, also known as racetrack memory, without shifting any domains. Motivated by this technique, we propose a novel scheme to combine transverse-read and shift-operations such that the number of shift-operations can be reduced while still achieving high capacity. We also show that this scheme is helpful to correct errors in domain wall memory. A set of valid words in this transverse-read channel is called a transverse-read code. We first present several properties of transverse-read codes and show that they are equivalent to constrained codes. Then, we compute the maximal asymptotic rate of transverse-read codes for several parameters. Next, we construct achieving capacity codes with efficient encoding/decoding algorithms. Finally, we discuss transverse-read codes which correct shift-errors in domain wall memory.

Successive-cancellation list (SCL) decoding is a widely used and studied decoding algorithm for polar codes. For short blocklengths, empirical evidence shows that SCL decoding with moderate list sizes (say,$L \leq 32$) closely matches the performance of maximum-likelihood (ML) decoding. Hashemi et al. proved that on the binary erasure channel (BEC), SCL decoding actually coincides with ML decoding for list sizes$L \geq 2^{\gamma}$, where$\gamma$is a new parameter we call the mixing factor. Loosely speaking, the mixing factor counts the number of information bits mixed-in among the frozen bits; more precisely$\gamma=\vert\{i\in \mathcal{F}^{c}:i\leq \max\{\mathcal{F}\}\}\vert$, where$\mathcal{F}\subset [n]$denotes the set of frozen indices. Herein, we extend the aforementioned result of Hashemi et al. from the BEC to arbitrary binary-input memoryless symmetric channels. Our proof is based on capturing all$2^{\gamma}$decoding paths that correspond to the$\gamma$information bits appearing before the last frozen bit, and then finding the most-likely extension for each of these paths efficiently using a nearest coset decoding algorithm introduced herein. Furthermore, we present a hybrid successive-cancellation list (H -SCL) decoding algorithm, which is a hybrid between conventional SCL decoding and nearest coset decoding. We believe that the hybrid algorithm can outperform the conventional SCL decoder with lower decoding complexity.

This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements$P$that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is$O\left(N^{1-1/\mu}+ \frac{N}{P}\log_{2}\log_{2}\frac{N}{P}\right)$, where$N$is the block length of the code and$\mu$is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where$P=\frac{N}{2}$, the latency of SSC decoding is$O\left(N^{1-1/\mu}\right)$, which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where$P=1$, the latency of SSC decoding scales as$O(N\, \log_{2}\log_{2}N)$. The multiplicative constant is also calculated: we show that the latency of SSC decoding when$P=1$is given by$(2+o(1))N\, \log_{2}\log_{2}N$. Third, in a semi-parallel implementation, the smallest$P$that gives the same latency as that of the fully-parallel implementation is$P=N^{1/\mu}$. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.

The bee-identification problem, formally defined by Tandon, Tan and Varshney (2019), requires the receiver to identify “bees” using a set of unordered noisy measurements. In this previous work, Tandon, Tan and Varshney studied error exponents and showed that decoding the measurements jointly results in a significantly smaller error exponent. Here, we study efficient ways of performing joint decoding. First, by reducing to the problem of finding perfect matching and minimum-cost matchings, we obtain joint decoders that run in time quadratic and cubic in the number of “bees” for the binary erasure (BEC) and binary symmetric channels (BSC), respectively. Next, by studying the matching algorithms in the context of channel coding, we further reduce the running times by using classical tools like peeling decoders and list-decoders. In particular, we show that our identifier algorithms when used with Reed-Muller codes terminates in almost linear and quadratic time for BEC and BSC, respectively.

We present a deterministic algorithm for computing the entire weight distribution of polar codes. As the first step, we derive an efficient recursive procedure to compute the weight distributions that arise in successive cancellation decoding of polar codes along any decoding path. This solves the open problem recently posed by Polyanskaya, Davletshin, and Polyanskii. Using this recursive procedure, we can compute the entire weight distribution of certain polar cosets in time$O(n^{2})$. Any polar code can be represented as a disjoint union of such cosets; moreover, this representation extends to polar codes with dynamically frozen bits. This implies that our methods can be also used to compute the weight distribution of polar codes with CRC precoding, of pol-arization-adjusted convolutional (PAC) codes and, in fact, general linear codes. However, the number of polar cosets in such representation scales exponentially with a parameter introduced herein, which we call the mixing factor. To reduce the exponential complexity of our algorithm, we make use of the fact that polar codes have a large automorphism group, which includes the lower-triangular affine group LTA$(m,2)$. We prove that LTA$(m,2)$acts transitively on certain subsets of polar codes, thereby drastically reducing the number of polar cosets we need to evaluate. This complexity reduction makes it possible to compute the weight distribution of any polar code of length up to$n=128$.

The problem of channel polarization for an arbitrary sequence$\{W_{i}\}_{i=0}^{n-1}$of$n$independent channels, referred to as a nonstationary sequence of channels, is considered. Also, each of the channels is used only once for communication. We consider a general framework for polarization of non-stationary channels and aim at optimizing the framework toward obtaining the best polarization. This framework includes permuting channels before Arıkan's pairwise channel combining operations are applied at each polarization level and skipping certain combining operations. We define an explicit optimization problem with the objective of finding the best permutation and indices of skipped operations in order to minimize a certain measure of polarization in one-level polarization. We then provide a complete solution to this optimization problem in the case of non-stationary binary erasure channels (BECs). We also propose a greedy method for polarizing non-stationary BECs, based on our solution for one-level polarization. Numerical results confirm the superiority of our method, in terms of various performance metrics, for constructing polar codes in certain non-stationary settings compared to prior work.

Thede Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be calledlocally-constrained de Bruijn sequencesand a set of such sequences will be called alocally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the$\ell $-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes.

We prove that, for the binary erasure channel (BEC), the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Our proof is based on the construction and analysis of binary polar codes with large kernels. When communicating reliably at rates within ε > 0 of capacity, the code length n often scales as O(1/εμ), where the constant μ is called the scaling exponent. It is known that the optimal scaling exponent is μ = 2, and it is achieved by random linear codes. The scaling exponent of conventional polar codes (based on the 2×2 kernel) on the BEC is μ = 3.63. This falls far short of the optimal scaling guaranteed by random codes. Our main contribution is a rigorous proof of the following result: for the BEC, there existl×lbinary kernels, such that polar codes constructed from these kernels achieve scaling exponent μ(l) that tends to the optimal value of 2 aslgrows. We furthermore characterize precisely how largelneeds to be as a function of the gap between μ(l) and 2. The resulting binary codes maintain the recursive structure of conventional polar codes, and thereby achieve construction complexity O(n) and encoding/decoding complexity O(nlogn).

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 correctingonly twodeletion 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.

Successive-cancellation decoding has gained much renewed interest since the advent of polar coding a decade ago. For polar codes, successive-cancellation decoding can be accomplished in time O(n log n). However, the complexity of successive-cancellation decoding for other families of codes remains largely unexplored. Herein, we prove that successive-cancellation decoding of general binary linear codes is NP-hard. In order to establish this result, we reduce from maximum-likelihood decoding of linear codes, a well-known NP-complete problem. Unlike maximum-likelihood decoding, however, the successive-cancellation decoding problem depends on the choice of a generator matrix. Thus we further strengthen our result by showing that there exist codes for which successive-cancellation decoding remains hard for every possible choice of the generator matrix. On the other hand, we also observe that polynomial-time successive-cancellation decoding can be extended from polar codes to many other linear codes. Finally, we show that every binary linear code can be encoded as a polar code with dynamically frozen bits. This approach makes it possible to use list-decoding of polar codes to approximate the maximum-likelihood decoding performance of arbitrary codes.

Three new constraints are introduced in this paper. These constraints are characterized by limitations on the Hamming weight of every subword of some fixed even length ℓ. In the (ℓ, δ)-locally-balanced constraint, the Hamming weight of every length-ℓ subword is bounded between ℓ/2 - δ and ℓ/2 + δ. The strong-(ℓ,δ)-locally-balanced constraint imposes the locally-balanced constraint for any subword whose length is at least ℓ. Lastly, the Hamming weight of every length-ℓ subword which satisfies the (ℓ, δ)-locally-bounded constraint is at most ℓ/2 - δ. It is shown that the capacity of the strong-(ℓ, δ)-locally-balanced constraint does not depend on the value of ℓ and is identical to the capacity of the (2δ + 1)-RDS constraint. The latter constraint limits the difference between the number of zeros and ones in every prefix of the word to be at most 2δ + 1. This value is also a lower bound on the capacity of the (ℓ, δ)-locally-balanced constraint, while a corresponding upper bound is given as well. Lastly, it is shown that if δ is not large enough, namely for δ <; √ℓ/2, then the capacity of the (ℓ, δ)-locally-bounded constraint approaches 1 as ℓ increases.

The imbalance of a binary word refers to the absolute difference between the number of ones and zeros in the word. Motivated by applications in DNA-based data storage and the success of polar codes, we study the problem of reducing imbalance in the codewords of a polar code. To this end, we adapt the technique of Mazumdar, Roth, and Vontobel by considering balancing sets that correspond to low-order Reed-Muller (RM) codes. Such balancing sets are likely to be included as subcodes in polar codes.Specifically, using the first-order RM code, we show that any message can be encoded into a length-n polar codeword with imbalance at most o(n) in O(nlogn)-time. We then reduce the imbalance even further using two methods. First, we constrain the ambient space $\mathbb{X}$ and analyze the imbalance that the first-order RM code can achieve for words in $\mathbb{X}$. We demonstrate that for codelengths up to 128, the first-order RM code achieves zero imbalance for appropriate choices of $\mathbb{X}$ that sacrifice only a few message bits. Second, we augment the balancing set by considering higher order RM codes. We give a simple recursive upper bound for the guaranteed imbalance of RM codes. We also prove that the second-order RM code $\mathbb{R}\mathbb{M}\left( {2,m} \right)$ balances all even-weight words for m ⩽ 5, while the RM code of order m − 3 balances all even-weight words for m ⩾ 5.

Polar coding gives rise to the first explicit family of codes that provably achieve capacity with efficient encoding and decoding for a wide range of channels. However, its performance at short block lengths under standard successive cancellation decoding is far from optimal. A well-known way to improve the performance of polar codes at short block lengths is CRC precoding followed by successive-cancellation list decoding. This approach, along with various refinements thereof, has remained the state of the art in polar coding since it was first introduced in 2011. Last year, Arıkan presented a new polar coding scheme, which he called polarization-adjusted convolutional (PAC) codes. Such PAC codes provide another dramatic improvement in performance as compared to CRC-aided list decoding. These codes are based primarily upon the following main ideas: replacing CRC precoding with convolutional precoding (under appropriate rate profiling) and replacing list decoding by sequential decoding. Arıkan's simulation results show that PAC codes, resulting from the combination of these ideas, are quite close to finite-length lower bounds on the performance of any code under ML decoding.One of our main goals in this paper is to answer the following question: is sequential decoding essential for the superior performance of PAC codes? We show that similar performance can be achieved using list decoding when the list size L is moderately large (say, L ≥ 128). List decoding has distinct advantages over sequential decoding in certain scenarios such as low-SNR regimes or situations where the worst-case complexity/latency is the primary constraint. Another objective is to provide some insights into the remarkable performance of PAC codes. We first observe that both sequential decoding and list decoding of PAC codes closely match ML decoding thereof. We then estimate the number of low weight codewords in PAC codes, and use these estimates to approximate the union bound on their performance under ML decoding. These results indicate that PAC codes are superior to polar codes and Reed-Muller codes, and suggest that the goal of rate-profiling may be to optimize the weight distribution at low weights.

In a bus with n wires, each wire has two states, `0' or `1', representing one bit of information. Whenever the state transitions from `0' to `1', or `1' to `0', joule heating causes the temperature to rise, and high temperatures have adverse effects on on-chip bus performance. Recently, the class of low-power cooling (LPC) codes was proposed to control such state transitions during each transmission. As suggested in earlier work, LPC codes may be used to control simultaneously both the peak temperature and the average power consumption of on-chip buses. Specifically, an (n, t, w)-LPC code is a coding scheme over n wires that (i) avoids state transitions on the t hottest wires (thus preventing the peak temperature from rising); and (ii) allows at most w state transitions in each transmission (thus reducing average power consumption). In this paper, for any fixed value of w, several constructions are presented for large LPC codes that can be encoded and decoded in time O(n log2(n/w)) along with the corresponding encoding/decoding schemes. In particular, we construct LPC codes of size (n/w)w-1, which are asymptotically optimal. We then modify these LPC codes to also correct errors in time O(n3). For the case where w is proportional to n, we further present a different construction of large LPC codes, based on a mapping from cooling codes to LPC codes. Using this construction, we obtain two families of LPC codes whose encoding and decoding complexities are O(n3).

Write-once memory (WOM) is a storage device consisting of binary cells that can only increase their levels. A t-write WOM code is a coding scheme that makes it possible to write t times to a WOM without decreasing the levels of any of the cells. The sum-rate of a WOM code is the ratio between the total number of bits written to the memory during the t writes and the number of cells. It is known that the maximum possible sum-rate of a t-write WOM code is log(t + 1). This is also an achievable upper bound, both by information-theoretic arguments and through explicit constructions. While existing constructions of WOM codes are targeted at the sum-rate, we consider here two more figures of merit. The first one is the complexity of the encoding and decoding maps. The second figure of merit is the convergence rate, defined as the minimum code length n(δ) required to reach a point that is δ-close to the capacity region. One of our main results in this paper is a capacity-achieving construction of two-write WOM codes which has polynomial encoding/decoding complexity while the block length n(δ) required to be δ-close to capacity is significantly smaller than existing constructions. Using these two-write WOM codes, we then obtain three-write WOM codes that approach a sum-rate of 1.809 at relatively short block lengths. We also provide several explicit constructions of finite length three-write WOM codes; in particular, we achieve a sum-rate of 1.716 by using only 93 cells. Finally, we modify our two-write WOM codes to construct ε-error WOM codes of high rates and small probability of failure.

This paper provides a reduced-complexity approach to maximum likelihood (ML) decoding of cyclic codes. A cyclic code with generator polynomial gcyclic(x) may be considered a terminated convolutional code with a nominal rate of 1. The trellis termination redundancy lowers the rate from 1 to the actual rate of the cyclic code. The proposed decoder represents gcyclic(x) as the product of two polynomials, a convolutional code (CC) polynomial gcc(x) and a cyclic redundancy check (CRC) polynomial gcrc(x), i.e., gcyclic(x) = gcc(x)gcrc(x). This representation facilitates serial list Viterbi algorithm (S-LVA) decoding. Viterbi decoding is performed on the natural trellis for gcc(x), and gcrc(x) is used as a CRC to determine when the S-LVA should conclude. At typical target frame error rates, the expected list size of S-LVA is small, and the average decoding complexity is dominated by the trellis complexity of gcc(x) rather than gcyclic(x). Some high-rate binary Bose-Chaudhuri- Hocquenghem (BCH) examples show that the proposed use of S-LVA via factorization significantly lowers complexity as compared to using the minimum-complexity trellis representation of gcyclic(x) for soft ML decoding.

Polar coding has found its way into many realms in communications and information theory. In most implementation setups, they are accompanied with the list successive cancellation (LSC) decoding algorithm which is shown to provide a superior error performance compared to the original successive cancellation (SC) decoding method. While the SC decoding is fairly well-studied, the exact math behind LSC's superior performance still remains to be of mystery. Multiple techniques have been proposed to further improve the LSC's error performance or to reduce its computational complexity, which are usually motivated by heuristic reasons and shown through numerical simulations. Most notable example is the CRC-aided LSC, which drastically improves the LSC's performance by concatenating the polar code with some high-rate cyclic redundancy check (CRC) codes.In this paper, we present polar codes that are concatenated with an underlying high-rate convolutional code, which are shown to have superior performances over CRC-aided LSC. We also present a computationally-efficient decoding algorithm for these codes which resembles the techniques used in the Viterbi algorithm, and hence is called the convolutional decoding algorithm. To do this, we revisit the error analysis of the original SC decoding along with the concept of Arıkan's helper genie. We address some shortcomings of the CRC-aided LSC and discuss how to turn around them by emulating a convolutional code instead of a CRC code. Contrary to CRC codes, most of the convolutional codes are not a proper choice for concatenation with polar codes. We introduce the bucketing algorithm to construct suitable punctured convolutional codes for this purpose. The proposed framework can accommodate any such underlying convolutional code, which allows one to search for the optimal convolutional code based on their design parameters.

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on this trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. Using this approach, we obtain a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length.

Polar coding gives rise to the first explicit family of codes that provably achieve capacity for a wide range of channels with efficient encoding and decoding. But how fast can polar coding approach capacity as a function of the code length? In finite-length analysis, the scaling between code length and the gap to capacity is usually measured in terms of the scaling exponent μ. It is well known that the optimal scaling exponent, achieved by random binary codes, is μ = 2. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is μ = 3.627, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from ℓ × ℓ binary polarization kernels approach the optimal scaling exponent μ = 2 on the BEC as ℓ→∞, with high probability over a random choice of the kernel. Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ ≤ 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent μℓtransforms an underlying BEC into ℓ bit-channels W1, W2>,..., Wℓ. The erasure probabilities of W1, W2>,..., Wℓ, known as the polarization behavior of Kℓ, determine the resulting scaling exponent μ(Kℓ). We first introduce a class of self-dual binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing Kℓto that of producing a certain nested chain of only ℓ/2 self-orthogonal codes. We use nested cyclic codes, whose distance is as high as possible subject to the orthogonality constraint, to construct the kernels K32and K64. In order to evaluate the polarization behavior of K32and K64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that μ(K32) = 3.122 and explicitly compute over half of the polarization-behavior coefficients for K64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate μ(K64) ≃ 2.87. We augment this estimate with a rigorous proof that μ(K64) <; 2.97.

Non-volatile resistive memories, such as phase change memories and resistive random access memories, have attracted significant attention recently due to their scalability, speed, and rewritability. However, in order to use these memories in large-scale memory and storage systems, the limited endurance deficiency of these memories must be addressed. In a recent paper, we proposed a new coding scheme, called endurance-limited memories (ELM) codes, which increases the endurance of these memories by limiting the number of cell programming operations. Namely, an l-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that the number of times each cell is programmed is at most l. There are several models of these codes which depend upon the information that is available to the encoder and the decoder before each write. This information can be one of the following three options: 1. the number of times each cell has been programmed, 2. only the memory state before programming, or 3. no information is available on the cells' state or previous writes. In this paper, we study the models in which the decoder knows on each write the number of times each cell has been programmed before the last write, while for the encoder we consider the aforementioned three possibilities.

The problem of list decoding algebraic subspace codes and rank-metric codes is considered. We develop two separate methods, via two different approaches, for list decoding subspace codes and rank-metric codes. These methods provide, for certain code parameters, improved tradeoffs between rate and error-correction capability than that of the Koetter-Kschischang codes, in the domain of subspace codes, and than that of the Gabidulin codes, in the domain of rank-metric codes, and several other extensions thereof. In the first approach, we introduce the notion of root multiplicities for a certain sub-ring of the ring of linearized polynomials. In the list-decoding algorithm, multiple roots are enforced for the interpolation polynomial in order to achieve an improved error-correction radius for an extended family of Koetter-Kschischang subspace codes. The normalized error-correction radius for this approach is τA=2(L+1)/(r+1)-1-L(L+1)(L+n)/r(r+1)R, where L is the maximum list size, n is the subspace code dimension, R is the rate of the code, and r is the multiplicity parameter. In the second approach, we construct a folded version of Koetter-Kschischang codes. A linear-algebraic list-decoding algorithm is proposed for these codes that achieves the error-correction radius τB=s(1-sR), where s is the folding parameter. As opposed to the first approach, the size of output list in the second approach depends on the underlying field size and is at most qm(s-1), where qmis the size of the field that message symbols are chosen from. It is also shown that the output list size is 1, with high probability, in a probabilistic setting. We utilize the techniques of the second approach in the domain of rank-metric codes to construct folded Gabidulin codes to enable a linear-algebraic list-decoding algorithm for such codes. Our algorithm makes it possible to recover.

A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, were introduced recently. An (n,t,w)-LPC code is a coding scheme over n wires that (A) avoids state transitions on the t hottest wires (cooling), and (B) limit the number of transitions to w in each transmission (low-power). A few constructions for large LPC codes that have efficient encoding and decoding schemes, are given. In particular, when w is fixed, we construct LPC codes of size (n/w)w-1and show that these LPC codes can be modified to correct errors efficiently. We further present a construction for large LPC codes based on a mapping from cooling codes to LPC codes.

In this work, we study limited-shift errors in racetrack memories and propose several schemes to combat these errors. There are two kinds of shift errors, namely under-shift errors, that can be modeled as sticky-insertions and limited-over-shift errors, that can be modeled as bursts of deletions of limited length. One approach to tackle the problem is to use deletion/sticky-insertion-correcting codes. Using this approach, we present a new family of asymptotically optimal codes that correct multiple bursts of deletions of limited length and any number of sticky insertions. We then study another approach that takes advantage of the special features of racetrack memories and the ability to add extra heads for redundancy. Here, we propose how to place the extra heads and construct codes to correct these shift errors.

An (n,k, l) MDS code of length n, dimension k, and sub-packetization l over a finite field F is a set of n column vectors of length l over F with the property that any k vectors can recover the entire data of kl symbols. If one of the n nodes fails, we can recover it by downloading symbols from the surviving nodes, and the total number of symbols downloaded in the worst case is the repair bandwidth of the code. By the cut-set bound, the repair bandwidth of an (n,k, l) MDS code is at least (n-1)l/(n-k). There are several constructions of (n,k, l) MDS codes whose repair bandwidths meet or asymptotically meet the cut-set bound. For example, letting r=n-k denote the number of parities, Ye and Barg constructed (n,k,rn) Reed-Solomon codes that asymptotically meet the cut-set bound. Ye and Barg also constructed optimal bandwidth and optimal update (n, k, rn) MDS codes. Wang, Tamo, and Bruck constructed optimal bandwidth (n,k,rn/(r+1)) MDS codes, and these codes have the smallest known sub-packetization for optimal bandwidth MDS codes. A key idea in all these constructions is to expand integers in base r. When r is an integral power, we demonstrated in a previous paper how this technique can be refined to improve the sub-packetization of the two (n,k, l) MDS code constructions by Ye and Barg while achieving asymptotically optimal repair bandwidth. Herein, we present an extension of this idea that leads to a significant reduction in the sub-packetization of the Wang-Tamo-Bruck construction while achieving a repair-by-transfer scheme that has asymptotically optimal repair bandwidth. Specifically, when r=sm, we obtain an (n,k,sk/r+m-1) MDS code which has a repair-by-transfer scheme with asymptotically optimal repair bandwidth. If r=2m, for example, we achieve the sub-packetization of 2k/r+m-1, which improves upon the sub-packetization of 2mn/(r+1)in the Wang- Tamo-Bruck construction. Having demonstrated how to improve the sub-packetizations of three quite different (n,k, l) MDS code constructions, we believe that our approach will be generally useful in reducing the sub-packetizations of (n,k, l) MDS code constructions that utilize r-ary expansion.

In this paper, we propose a polar coding scheme for binary deletion channels. We also present an implementation of low-complexity polar SC decoder for deletion channels. The modified decoding algorithm requires only O(d2nlogn) computational complexity, where d and n respectively denote the number of deletions and the code-length. This is a huge improvement over naive implementation of the SC decoder for channels with deletion with O(nd+1logn) computation complexity that was recently proposed by Thomas et al. in [21], and is based on running individual instances of SC decoder for every deletion pattern while treating the deleted symbols as erasures. We also prove polarization theorems for the polar bit-channels in presence of deletions when d = o(n), which implies that our coding scheme is capable of achieving the symmetric information rate for this concatenated scheme with diminishing error probabilities as n becomes large. The same framework, in both theory and implementation, is also applicable to channels formed as a concatenation between binary discrete memoryless channels and the d-deletion channel, which marks our coding scheme as the first family of practical codes that is capable of decoding noisy channels with deletions at the optimal code rate.

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems.In this work, in order to reduce the wearout of the cells, we propose a new coding scheme, called Endurance-Limited Memories (ELM) code, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an ℓ-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that each cell is programmed at most ℓ times. In case ℓ = 1 then these codes coincide with the well-studied write-once memory (WOM) codes. We study four models of these codes which depend upon whether the encoder knows, on each write, the number of times each cell was programmed or only knows its state. For the decoder, we consider two cases which depend upon whether the decoder knows the previous state of the memory or not. For two of these models we fully characterize the capacity regions and present partial results for another model. Although only one of the four models is suitable for resistive memories, we consider all four in order to carry out a complete information-theory study of endurance-limited codes.

In this work, we study a special case of the reconstruction problem in order to combat position errors in racetrack memories. In these memories, the information is stored in magnetic cells that can be sensed by shifting them under read heads. However, since this shifting operation is not error free, recent work has been dedicated towards correcting these so-called position errors, which manifest themselves as deletions and sticky insertions. A deletion is the event where the cells are over-shifted, and a sticky insertion occurs when the cells are not shifted.We first present a code construction that uses two heads to correct two deletions with at most log2(log2n) +4 redundant bits. This result improves upon a recent one that requires roughly log2n redundant bits. We then extend this construction to correct d deletions using d heads with at most log2(log2n) +c redundant bits. Lastly, we extend our results and derive codes for the classical reconstruction problem by Levenshtein over the insertion/deletion channel.

We prove that, at least for the binary erasure channel, the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but, in fact, do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure reliable communication at rates within ε > 0 of capacity with block length n = O(1/ε2+δ), construction complexity Θ(n), and encoding/decoding complexity Θ(n log n).

High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. We also reduce the average power consumption by making sure that the total number of state transitions on all the wires is below a prescribed threshold. We show how each of these two features can be coded for separately or, alternatively, how both can be achieved at the same time. In addition, error-correction for the transmitted information can be provided while controlling the peak temperature and/or the average power consumption. In general, our cooling codes use n > k wires to encode a given k-bit bus. One of our goals herein is to determine the minimum possible number of wires n needed to encode k bits while satisfying any combination of the three desired properties. We provide full theoretical analysis in each case. In particular, we show that n = k+t +1 suffices to cool the t hottest wires, and this is the best possibility. Moreover, although the proposed coding schemes make use of sophisticated tools from combinatorics, discrete geometry, linear algebra, and coding theory, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

Racetrack memory is a new technology, which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape, which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this paper, we design codes, which combat shift errors in racetrack memory, called position errors, namely, shifting the domains is not an error-free operation and the domains may be over shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. This setup is a special case of the reconstruction problem studied by Levenshtein, however, in our case, the position errors from different heads are correlated. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions. In particular, under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d+1 heads if the heads are well separated. Similar results are provided for burst of deletions, sticky insertions, and combinations of both deletions and sticky insertions.

Polar codes provably achieve the capacity of memoryless symmetric channels with low encoding and decoding complexity. Nonetheless, for short and moderate blocklengths, polar codes fail to deliver competitive performance under successive cancellation decoding. Consequently, much effort has been devoted to improving the performance of polar codes, either through enhanced decoding algorithms or by modifying the code structure, or both. CRC-aided list decoding of polar codes is the most successful approach along this line of research. However, list decoding requires following L decoding paths, which leads to a significant increase in decoding complexity if L is large. As noted by Arikan shortly after the invention of polar codes, their performance could be improved dramatically if we had a genie that intervenes in the successive cancellation decoding process only a few times to reverse incorrect decisions on information bits. In fact, the Tal-Vardy list-decoding algorithm for polar codes can be regarded as an attempt to implement such a genie. Herein, we introduce an alternative implementation of Arikan's genie, which has much lower complexity than list decoding. Our approach is based on precoding some of the information bits with a short convolutional code that provides local error- correction capability at the expense of a small rate loss. This structure allows the successive cancellation polar decoder to verify its output by running it through a Viterbi decoder for the convolutional code. In contrast to conventional CRC-aided list decoding, wherein incorrect decoding paths are rejected detected only after reaching the last information bit, the Viterbi decoder detects incorrect decisions "on the fly'' after a short delay. Whenever an incorrect decision is detected, the successive cancellation decoder is set back to the corresponding bit-channel, and then restarts its computation using the correct bit value provided by the Viterbi decoder.

Combining the polar coded hybrid automatic repeat request (HARQ) with higher-order modulation has been proposed recently. To further improve the throughput of HARQ, a novel polar coded HARQ cheme with higher-order modulation is proposed. Wherein the proposed HARQ scheme, the unequal rror protection (UEP), caused by bit-mapping, in bit- interleaved polar coded modulation (BIPCM) is considered. Based on UEP, a non-linear integer programming (NLIP) problem is constructed to determine the optimal retransmitted sequence. Furthermore, a low-complexity suboptimal algorithm is proposed to solve the resulting NLIP problem. Simulation results show that the throughput of the proposed HARQ scheme outperforms the existing polar coded HARQ for higher-order modulation; in particular, our scheme easily accommodates arbitrarily puncturing methods. This makes it possible to use recently proposed puncturing methods for polar codes to further improve the performance of our HARQ scheme.

Defined through a certain 2 × 2 matrix called Arikan's kernel, polar codes are known to achieve the symmetric capacity of binary-input discrete memoryless channels under the successive cancellation (SC) decoder. Yet, for short block-lengths, polar codes fail to deliver a compelling performance under the low complexity SC decoding scheme. Recent studies provide evidence for improved performance when Arikan's kernel is replaced with larger kernels that have smaller scaling exponents. However, for ℓ×ℓ kernels the time complexity of the SC decoding increases by a factor of 2ℓ. In this paper we study a special type of kernels called permuted kernels. The advantage of these kernels is that the SC decoder for the corresponding polar codes can be viewed as a permuted version of the SC decoder for the conventional polar codes that are defined through Arikan's kernel. This permuted successive cancellation (PSC) decoder outputs its decisions on the input bits according to a permuted order of their indices. We introduce an efficient PSC decoding algorithm and show simulations for two 16 × 16 permuted kernels that have better scaling exponents than Arikan's kernel.

High temperatures have dramatic negative effects on interconnect performance. Numerous techniques have been proposed to reduce the power dissipation of on-chip buses but they fall short of fully addressing the thermal challenges posed by high-performance interconnects. We introduce new efficient coding schemes that directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. At the same time, we reduce the average power consumption by ensuring that the total number of state transitions on all the wires is bounded. Our solutions call for redundancy: we use n > k wires to encode a given k-bit bus. Therefore, it is important to determine the minimum possible number of wires n needed to encode k bits while satisfying the desired properties. We provide full analysis in each case, and show that the number of additional wires required to cool the t hottest wires is negligible when k is large. Moreover, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory has a tape-like structure which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. Under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d + 1 heads if the heads are well-separated. Similar results are provided for burst of deletions, sticky insertions and combinations of both deletions and sticky insertions.

Write-once memory (WOM) is a storage device consisting of binary cells which can only increase their levels. A t-write WOM code is a coding scheme which allows to write t times to the WOM without decreasing the levels of the cells. The sum-rate of a WOM code is the ratio between the total number of bits written to the memory and the number of cells. It is known that the maximum sum-rate of a t-write WOM code is log(t + 1). This is also an achievable upper bound both by information theory arguments and explicit WOM code constructions. While existing constructions of WOM codes were targeted to increase the sum-rate, we consider here two more figures of merit in evaluating the constructions. The first one is the complexity of the encoding and decoding maps of the code. The second one is called the convergence rate, and is defined to be the minimum code length n(ε) in order to reach e close to a point in the capacity region. One of our main results in the paper is a specific capacity achieving construction for two-write WOM codes which has polynomial complexity and relatively short block length to be ε close to the capacity. Using these two-write WOM codes, we obtain three-write WOM codes that approach sum-rate 1.809 with relatively short block lengths. Finally, we provide another construction of three-write WOM that achieves sum-rate 1.71 by using only 100 cells.

The problem of constructing sticky-insertion-correcting codes with efficient encoding and decoding is considered. An {n, M, r) sticky-insertion-correcting code consists of M codewords of length n such that any pattern of up to r sticky insertions can be corrected. We utilize BCH codes and their analogous in the Lee space to construct explicit and systematic codes that are immune to up to r sticky insertions. It is shown that the ratio of the number of constructed redundancy bits in the construction to a certain upper bound approaches one as the block length grows large, which implies asymptotic optimality of the construction.

Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we continue our recent study and design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions.

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n, k, d]-(α) MSR code C over Fqstores a file F consisting of αk symbols over Fqamong n nodes, each storing α symbols, in such a way that: 1) the file F can be recovered by downloading the content of any k of then nodes and 2) the content of any failed node can be reconstructed by accessing any d of the remaining n - 1 nodes and downloading α/(d-k+1) symbols from each of these nodes. In practice, the file F is typically available in uncoded form on some k of the n nodes, known as systematic nodes, and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only. Such codes are called systematic-repair MSR codes. Unfortunately, finite-α constructions of [n, k, d] MSR codes are known only for certain special cases: either low rate, namely k/n ≤ 0.5, or high repair connectivity, namely d = n - 1. Our main result in this paper is a finite-α construction of systematic-repair [n, k, d] MSR codes for all possible values of parameters n, k, d. We also introduce a generalized construction for [n, k] MSR codes to achieve the optimal repair bandwidth for all values of d simultaneously.

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n, k, d]-(α) MSR code C over Fqis defined as follows. Using such a code C, a file F consisting of αk symbols over Fq can be distributed among n nodes, each storing α symbols, in such a way that: . the file F can be recovered by downloading the content of any k of the n nodes; and . the content of any failed node can be reconstructed by accessing any d of the remaining n -1 nodes and downloading α/(d-k+1) symbols from each of these nodes. A common practical requirement for regenerating codes is to have the original file F available in uncoded form on some k of the n nodes, known as systematic nodes. In this case, several authors relax the defining node-repair condition above, requiring the optimal repair bandwidth of dα/(d-k+1) symbols for systematic nodes only. We shall call such codes systematic-repair MSR codes. Unfortunately, explicit constructions of [n, k, d] MSR codes are known only for certain special cases: either low rate, namely k/n ≤ 0.5, or high repair connectivity, namely d = n -1. Although setting d = n - 1 minimizes the repair bandwidth, it may be impractical to connect to all the remaining nodes in order to repair a single failed node. Our main result in this paper is an explicit construction of systematic-repair [n, k, d] MSR codes for all possible values of parameters n, k, d. In particular, we construct systematic-repair MSR codes of high rate k/n > 0.5 and low repair connectivity k ≤ d ≤ n - 1. Such codes were not previously known to exist. In order to construct these codes, we solve simultaneously several repair scenarios, each of which is expressible as an interference alignment problem. Extension of our results beyond systematic repair remains an open problem.

Batch codes, first studied by Ishai et al., are a coding scheme to encode n information bits into m buckets, in a way that every batch request of k bits can be decoded while at most one bit is read from each bucket. In this work we study the class of multiset primitive batch codes, in which every bucket stores a single bit and bits can be requested multiple times. We simply refer to these codes as batch codes. The main problem under this paradigm is to optimize the number of encoded bits, which is the number of buckets, for given n and k, and we denote this value by B(n, k). Since there are several asymptotically optimal constructions of these codes, we are motivated to evaluate their optimality by their redundancy. Thus we define the optimal redundancy of batch codes to be rB(n, k) ??? B(n, k) - n. Our main result in this paper claims that for any fixed k, rB(n, k) = O(√n log(n)).

Polar codes asymptotically achieve the symmetric capacity of memoryless channels, yet their error-correcting performance under successive-cancellation (SC) decoding for short and moderate length codes is worse than that of other modern codes such as low-density parity-check (LDPC) codes. Of the many methods to improve the error-correction performance of polar codes, list decoding yields the best results, especially when the polar code is concatenated with a cyclic redundancy check (CRC). List decoding involves exploring several decoding paths with SC decoding, and therefore tends to be slower than SC decoding itself, by an order of magnitude in practical implementations. In this paper, we present a new algorithm based on unrolling the decoding tree of the code that improves the speed of list decoding by an order of magnitude when implemented in software. Furthermore, we show that for software-defined radio applications, our proposed algorithm is faster than the fastest software implementations of LDPC decoders in the literature while offering comparable error-correction performance at similar or shorter code lengths.

In this paper, we present hardware and software implementations of flexible polar systematic encoders and decoders. The proposed implementations operate on polar codes of any length less than a maximum and of any rate. We describe the low-complexity, highly parallel, and flexible systematic-encoding algorithm that we use and prove its correctness. Our hardware implementation results show that the overhead of adding code rate and length flexibility is little, and the impact on operation latency minor compared with code-specific versions. Finally, the flexible software encoder and decoder implementations are also shown to be able to maintain high throughput and low latency.

Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic k-server PIR, the database is replicated among k non-communicating servers, and each server learns nothing about the item retrieved by the user. The cost of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers. However, another important cost parameter is the storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least 2 (or k, in the case of k-server PIR). In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of 1, without sacrificing the communication complexity. Specifically, we prove that all known k-server PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the n bits of the database among s + r servers, each storing n/s coded bits (rather than replicas). Notably, our coding scheme remains the same, regardless of the specific k-server PIR protocol being emulated. For every fixed k, the resulting storage overhead (s +r)/s approaches 1 as s grows; explicitly we have equation. Moreover, in the special case k = 2, the storage overhead is only 1 + 1/s. In order to achieve these results, we introduce and study a new kind of binary linear codes, called here k-server PIR codes. Finally, we show how such codes can be constructed from multidimensional cubic, from Steiner systems, and from one-step majority-logic decodable codes.

The problem of constructing error correcting codes for defective memories, where some of the cells are defected and unable to switch their states, is considered. This is a classical problem in coding theory which has recently received renewed attention due to application to new technologies for non-volatile memories such as phase change memories. We show how the state of the art capacity achieving codes, in combination with a coset coding and another error correcting code, can be used in order to asymptotically achieve the capacity of the binary defective memory. The resulting schemes are explicit, have polynomial time encoder and quasilinear time decoder. The model is further generalized by considering erasures on top of the defective cells. We propose the partitioned polar codes for this model and prove that they achieve the capacity.

One of the prominent properties of flash memories is their asymmetry between writing and erasing. When pages, which are the smallest write unit, are updated, they are written in a new copy rather than in place. As a result, every page can have more than one copy in the memory, its current version as well as some of its old invalid copies. Each invalid copy can be cleaned only when the block in which it resides is erased (blocks are the smallest erase unit and are typically in the order of hundreds of pages). This write property introduces redundancy in the memory, given by the invalid copies of the pages, and as a result can also affect the memory lifetime. In this paper we show how this inherent redundancy of invalid pages can be taken advantage of for the purpose of improving RAID solutions which are based upon Solid State Drives (SSDs). Our main contribution in the paper is a construction which shows how to improve the repair bandwidth of codes which are implemented on SSDs. We first show that with a single parity it is possible to transmit on the average roughly half of the data for rebuilding a single drive failure. We then show how these ideas can be extended for Zigzag codes with two parities and again improve their repair bandwidth.

The information-theoretic approach to security entails harnessing the correlated randomness available in nature to establish security. It uses tools from information theory and coding and yields provable security, even against an adversary with unbounded computational power. However, the feasibility of this approach in practice depends on the development of efficiently implementable schemes. In this paper, we review a special class of practical schemes for information-theoretic security that are based on 2-universal hash families. Specific cases of secret key agreement and wiretap coding are considered, and general themes are identified. The scheme presented for wiretap coding is modular and can be implemented easily by including an extra preprocessing layer over the existing transmission codes.

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 transversal. 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.

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.

We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arıkan. In the proposed list decoder, L decoding paths are considered concurrently at each decoding stage, where L is an integer parameter. At the end of the decoding process, the most likely among the L paths is selected as the single codeword at the decoder output. Simulations show that the resulting performance is very close to that of maximum-likelihood decoding, even for moderate values of L. Alternatively, if a genie is allowed to pick the transmitted codeword from the list, the results are comparable with the performance of current state-of-the-art LDPC codes. We show that such a genie can be easily implemented using simple CRC precoding. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths for each information bit, and then uses a pruning procedure to discard all but the L most likely paths. However, straightforward implementation of this algorithm requires Ω(Ln2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. In this paper, we utilize the structure of polar codes along with certain algorithmic transformations in order to overcome this problem: we devise an efficient, numerically stable, implementation of the proposed list decoder that takes only O(Ln logn) time and O(Ln) space.

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 channels, and in particular for those where the error spheres sizes are not all the same. This paper studies this method in its most general setup. We first show 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 the satisfy the constraints in the linear programming problem. Every valid assignment yields an upper bound and the goal is to find assignments that provide strong upper bounds. We show that for graphs which satisfy a monotonicity property it is possible to find a general formula for such an assignment. Lastly, in order to simplify the complexity of the linear programming, we present a technique based upon graph automorphisms that in many cases can significantly reduce the number of variables and constraints in the linear programming problem. All of our results will be demonstrated and calculated for the Z channel which will be a case study in our work.

In this paper we study a generalization of the sphere packing bound for channels that are not regular (the size of balls with a fixed radius is not necessarily the same). Our motivation to tackle this problem is originated by a recent work by Kulkarni and Kiyavash who introduced a method, based upon tools from hypergraph theory, to calculate explicit upper bounds on the cardinalities of deletion-correcting codes. Under their setup, the deletion channel is represented by a hypergraph such that every deletion ball is a hyperedge. Since every code is a matching in the hypergraph, an upper bound on the codes is given by an upper bound on the largest matching in a hypergraph. This bound, called here the generalized sphere packing bound, can be found by the solution of a linear programming problem. We similarly study and analyze 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 non-binary limited magnitude channel both for symmetric and asymmetric errors. We focus on the case of single error and derive upper bounds on the generalized sphere packing bound in this channel. We follow up on the deletion case, which was the original motivation of the work by Kulkarni and Kiyavash, and show how to improve upon their upper bounds for the single deletion case. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.

We extend the Bellare-Tessaro coding scheme for a discrete, degraded, symmetric wiretap channel to a Gaussian wiretap channel. Denoting by SNR the signal-to-noise ratio of the eavesdropper's channel, the proposed scheme converts a transmission code of rate R for the channel of the legitimate receiver into a code of rate R-0.5 log(1+SNR) for the Gaussian wiretap channel. The conversion has a polynomial complexity in the codeword length and the proposed scheme achieves strong security. In particular, when the underlying transmission code is capacity achieving, this scheme achieves the secrecy capacity of the Gaussian wiretap channel.

Polar codes provably achieve the symmetric capacity of a memoryless channel while having an explicit construction. The adoption of polar codes however, has been hampered by the low throughput of their decoding algorithm. This work aims to increase the throughput of polar decoding hardware by an order of magnitude relative to successive-cancellation decoders and is more than 8 times faster than the current fastest polar decoder. We present an algorithm, architecture, and FPGA implementation of a flexible, gigabit-per-second polar decoder.

Flash memory is a nonvolatile computer memory comprising blocks of cells, wherein each cell can take on$q$different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes—known as floating codes (or flash codes) and buffer codes—have been designed in order to maximize the number of times that information stored in a flash memory can be written (and rewritten) prior to incurring a block erasure. An$(n,k,t)_{q}$flash code$\BBC$is a coding scheme for storing$k$information bits in$n$cells in such a way that any sequence of up to$t$writes can be accommodated without a block erasure. The total number of available level transitions in$n$cells is$n(q{-}1)$, and the write deficiency of$\BBC$, defined as$\delta (\BBC)=n(q{-}1)-t$, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency$O(qk\log k)$if$q\geqslant\log_{2}k$, and at most$O(k\log^{2}k)$otherwise. An$(n,r,\ell,t)_{q}$buffer code is a coding scheme for storing a buffer of$r~\ell$-ary symbols such that for any sequence of$t$symbols, it is possible to successfully decode the last$r$symbols that were written. We improve upon a previous upper bound on the maximum number of writes$t$in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiangthat uses multiple cells, where$n\geqslant 2r$.

This paper has two goals. The first one is to discuss good codes for packing problems in the Lee and Manhattan metrics. The second one is to consider weighing matrices for some of these coding problems. Weighing matrices were considered as building blocks for codes in the Hamming metric in various constructions. In this paper we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics. Two related packing problems will be considered. The first one is to find good codes for error-correction (i.e. dense packings of Lee spheres). The second one is to transform the space in a way that volumes are preserved and each Lee sphere (or conscribed cross-polytope), in the space, will be transformed into a shape inscribed in a small cube.

The problem of achieving the secrecy capacity of wiretap channels explicitly and with low complexity has been open since the work of Wyner in 1975. Recently, Mahdavifar and Vardy presented a solution to this problem, based on polar codes, for the class of symmetric and degraded wiretap channels. Their polar coding scheme achieves both security and reliability under the weak security criterion, but does not guarantee reliability under the strong security criterion. The main difficulty in providing both strong security and reliability using polar codes is the existence of a small number of bit-channels that are both unreliable and unsecure. In this paper, a multi-block polar coding scheme that resolves this difficulty is presented. It is shown that this coding scheme achieves the secrecy capacity of symmetric degraded wiretap channels while guaranteeing both reliability and strong security.

Bellare and Tessaro recently introduced a new coding scheme, based on cryptographic principles, that guarantees strong security for a wide range of symmetric wiretap channels. This scheme has numerous advantages over alternative constructions, including constructions based on polar codes. However, it achieves secrecy capacity only under a certain restrictive condition. Specifically, let V be the main channel (from Alice to Bob) and let W be wiretap channel (from Alice to Eve). Suppose that W has a finite output alphabet y, and let X and Y denote the input and output of W, respectively. Then the rate of the Bellare-Tessaro coding scheme is at most I(V) - Ψ(W), where I(V) is the capacity of V and Ψ(W) is given by Ψ(W) = log2|y|-H(Y|X). For symmetric channels, it is clear that Ψ(ΨW) ≥ I(W) with equality if and only if uniform input to W produces uniform output. Unfortunately, few symmetric DMCs satisfy this condition. In this paper, we show how the Bellare-Tessaro coding scheme can be extended to achieve secrecy capacity in the case where W is an arbitrary symmetric DMC. To this end, we solve the following problem. Given W and ε > 0, we construct another channel Q such that W is degraded with respect to Q while the difference between Ψ(<;3) and I(W) is at most ε. We also solve a closely related problem, where the output alphabet of Q is required to be of a given size M. In this case, we construct a channel Q that is equivalent to W, such that Ψ(<;3) is a small as possible. We furthermore extend these results, and thereby the applicability of the Bellare-Tessaro coding scheme, to channels with binary input and continuous output.

This paper has two goals. The first one is to discuss two related packing problems in the Lee and Manhattan metrics. One is to find good codes for error-correction (i.e., packings of Lee spheres) and the other is to transform the space in a way that volumes are preserved and each Lee sphere (or scaled cross-polytope) will be transformed into a shape inscribed in a small cube. The second goal is to consider weighing matrices for some of these coding problems. Weighing matrices have been used as building blocks for codes in the Hamming metric in various constructions. In this paper, we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics.

Subspace codes are collections of subspaces of a cer- tain ambient vector space over a finite field. Koetter and Kschi- schang introduced subspace codes in order to correct errors and erasures in noncoherent (random) linear network coding. They have also studied a remarkable family of subspace codes obtained by evaluating certain linearized polynomials. The Koetter–Kschi- schang subspace codes are widely regarded as the counterpart of Reed–Solomoncodes in the domain of network error-correction. Koetter and Kschischang have furthermore devised an algebraic decoding algorithm for these codes, analogous to the Berlekamp– Welch decoding algorithm for Reed–Solomon codes.

A method for efficiently constructing polar codes is presented and analyzed. Although polar codes are explicitly defined, straightforward construction is intractable since the resulting polar bit-channels have an output alphabet that grows exponentially with the code length. Thus, the core problem that needs to be solved is that of faithfully approximating a bit-channel with an intractably large alphabet by another channel having a manageable alphabet size. We devise two approximation methods which “sandwich” the original bit-channel between a degraded and an upgraded version thereof. Both approximations can be efficiently computed and turn out to be extremely close in practice. We also provide theoretical analysis of our construction algorithms, proving that for any fixed ε > 0 and all sufficiently large code lengths n, polar codes whose rate is within ε of channel capacity can be constructed in time and space that are both linear in n.

Subspace codes and rank-metric codes can be used to correct errors and erasures in network, with linear network coding. Both types of codes have been extensively studied in the past five years. Subspace codes were introduced by Koetter and Kschischang to correct errors and erasures in networks where topology is unknown (the non-coherent case). In this model, the codewords are vector subspaces of a fixed ambient space; thus codes for this model are collections of such subspaces. In a previous work, we have developed a family of subspace codes, based upon the Koetter-Kschichang construction, which are efficiently list decodable. Using these codes, we achieved a better decoding radius than Koetter-Kschischang codes at low rates. Herein, we introduce a new family of subspace codes based upon a different approach which leads to a linear-algebraic list-decoding algorithm. The resulting error-correction radius can be expressed as follows: for any integer s, our list-decoder using s + 1-variate interpolation polynomials guarantees successful recovery of the message sub-space provided the normalized dimension of errors is at most s(1 - sR). The same list-decoding algorithm can be used to correct erasures as well as errors. The size of output list is at most Qs - 1, where Q is the size of the field that message symbols are chosen from. Rank-metric codes are suitable for error correction in the case where the network topology and the underlying network code are known (the coherent case). Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank-distance of a code. In this paper, we introduce a folded version of Gabidulin codes analogous to the folded Reed-Solomon codes of Guruswami and Rudra along with a list-decoding algorithm for such codes. Our list-decoding algorithm makes it possible to recover the message provided that the normalized rank of error is at most 1 - R - ϵ, for any ϵ >; 0. Notably this achieves the information theoretic bound on the decoding radius of a rank-metric code.

Consider a channel with an input alphabet that is finite but not necessarily binary. A method for approximating such a channel having a large output alphabet size by a degraded version of it having a smaller output alphabet size is presented and analyzed. The approximation method is used to construct polar codes for both single-user and multiple-access channels with prime input alphabet sizes.

A write-once memory (WOM) is a storage device that consists of cells that can take on$q$values, with the added constraint that rewrites can only increase a cell's value. A length-$n$,$t$-write WOM-code is a coding scheme that allows$t$messages to be stored in$n$cells. If on the$i$th write we write one of$M_{i}$messages, then the rate of this write is the ratio of the number of written bits to the total number of cells, i.e.,$\log_{2}M_{i}/n$. The sum-rate of the WOM-code is the sum of all individual rates on all writes. A WOM-code is called a fixed-rate WOM-code if the rates on all writes are the same, and otherwise, it is called a variable-rate WOM-code. We address two different problems when analyzing the sum-rate of WOM-codes. In the first one, called the fixed-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate WOM-codes, and in the second problem, called the unrestricted-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate and variable-rate WOM-codes. In this paper, we first present a family of two-write WOM-codes. The construction is inspired by the coset coding scheme, which was used to construct multiple-write WOM-codes by Cohenand recently by Wu, in order to construct from each linear code a two-write WOM-code. This construction improves the best known sum-rates for the fixed- and unrestricted-rate WOM-code problems. We also show how to take advantage of two-write WOM-codes in order to construct codes for the Blackwell channel. The two-write construction is generalized for two-write WOM-codes with$q$levels per cell, which is used with ternary cells to construct three- and four-write binary WOM-codes. This construction is used recursively in order to generate a family of$t$-write WOM-codes for all$t$. A further generalization of these$t$-write WOM-codes yields additional families of efficient WOM-codes. Finally, we show a recursive method that uses the previously constructed WOM-codes in order to construct fixed-rate WOM-codes. We conclude and show that the WOM-codes constructed here outperform all previously known WOM-codes for$2\leqslant t\leqslant 10$for both the fixed- and unrestricted-rate WOM-code problems.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of C, defined by R(C) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zemor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors.

The recently-discovered polar codes are widely seen as a major breakthrough in coding theory. These codes achieve the capacity of many important channels under successive cancellation decoding. Motivated by the rapid progress in the theory of polar codes, we pro pose a family of architectures for efficient hardware implementation of successive cancellation decoders. We show that such decoders can be implemented with O(n) processing elements and O(n) memory elements, while providing constant throughput. We also pro pose a technique for overlapping the decoding of several consecutive codewords, thereby achieving a significant speed-up factor. We furthermore show that successive cancellation decoding can be implemented in the logarithmic domain, thereby eliminating the multiplication and division operations and greatly reducing the complexity of each processing element.

We describe a successive-cancellation list decoder for polar codes, which is a generalization of the classic successive-cancellation decoder of Arikan. In the proposed list decoder, up to L decoding paths are considered concurrently at each decoding stage. Simulation results show that the resulting performance is very close to that of a maximum-likelihood decoder, even for moderate values of L. Thus it appears that the proposed list decoder bridges the gap between successive-cancellation and maximum-likelihood decoding of polar codes. The specific list-decoding algorithm that achieves this performance doubles the number of decoding paths at each decoding step, and then uses a pruning procedure to discard all but the L “best” paths. In order to implement this algorithm, we introduce a natural pruning criterion that can be easily evaluated. Nevertheless, straightforward implementation still requires O(L · n2) time, which is in stark contrast with the O(n log n) complexity of the original successive-cancellation decoder. We utilize the structure of polar codes to overcome this problem. Specifically, we devise an efficient, numerically stable, implementation taking only O(L · n log n) time and O(L · n) space.

In multi-level flash memories, the dominant cell errors are asymmetric with limited-magnitude. With such an error model in mind, Cassuto et al. recently developed bounds and constructions for codes correcting t asymmetric errors with magnitude no more than ℓ. However, a more refined model of these memory devices reflects the fact that typically only a small number of errors have large magnitude while the remainder are of smaller magnitude. In this work, we study such an error model, in which at most t1errors of maximum magnitude ℓ1and at most t2errors of maximum magnitude ℓ2, with ℓ12, can occur. We adapt the analysis and code construction of Cassuto, et al. for the refined error model and assess the relative efficiency of the new codes. We then consider in more detail specific constructions for the case where t1= t2= 1, ℓ1= 1, and ℓ2>; 1.

A Write-Once Memory (WOM)-code is a coding scheme that allows information to be written in a memory block multiple times, but in a way that the stored values are not decreased across writes. This work studies non-binary WOM-codes with applications to flash memory. We present two constructions of non-binary WOM-codes that leverage existing high sum-rate WOM-codes defined over smaller alphabets. In many instances, these constructions provide the highest known sum-rates of the non-binary WOM-codes. In addition, we introduce a new class of codes, called level distance WOM-codes, which mitigate the difficulty of programming a flash memory cell by eliminating all small-magnitude level increases. We show how to construct such codes and state an upper bound on their sum-rate.

The projective space of ordernover the finite field \BBFq, denoted here asPq(n), is the set of all subspaces of the vector space \BBFqn. The projective space can be endowed with the distance functiond(U,V) = dimU+ dimV-2 dim(U∩V) which turnsPq(n) into a metric space. With this, an (n,M,d) code \BBC in projective space is a subset ofPq(n) of sizeMsuch that the distance between any two codewords (subspaces) is at leastd. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an (n,M,d) code can correcttpacket errors and ρ packet erasures introduced (adversarially) anywhere in the network as long as 2t+ 2ρd. This motivates our interest in such codes. In this paper, we investigate certain basic aspects of “coding theory in projective space.” First, we present several new bounds on the size of codes inPq(n), which may be thought of as counterparts of the classical bounds in coding theory due to Johnson, Delsarte, and Gilbert-Varshamov. Some of these are stronger than all the previously known bounds, at least for certain code parameters. We also present several specific constructions of codes and code families inPq(n). Finally, we prove that nontrivial perfect codes inPq(n) do not exist.

The main computational steps in algebraic soft-decoding, as well as Sudan-type list-decoding, of Reed–Solomon codes are bivariate polynomial interpolation and factorization. We introduce a computational technique, based upon re-encoding and coordinate transformation, that significantly reduces the complexity of the bivariate interpolation procedure. This re-encoding and coordinate transformation converts the original interpolation problem into another reduced interpolation problem, which is orders of magnitude smaller than the original one. A formal proof is presented to show that the two interpolation problems are indeed equivalent. An efficient factorization procedure that applies directly to the reduced interpolation problem is also given.

Suppose that Alice wishes to send messages to Bob through a communication channel$C_{1}$, but her transmissions also reach an eavesdropper Eve through another channel$C_{2}$. This is the wiretap channel model introduced by Wyner in 1975. The goal is to design a coding scheme that makes it possible for Alice to communicate both reliably and securely. Reliability is measured in terms of Bob's probability of error in recovering the message, while security is measured in terms of the mutual information between the message and Eve's observations. Wyner showed that the situation is characterized by a single constant${\cal C}_{s}$, called the secrecy capacity, which has the following meaning: for all$\varepsilon \!\! > \!\! 0$, there exist coding schemes of rate$R\! \geqslant {\cal C}_{s} \! \! - \! \varepsilon$that asymptotically achieve the reliability and security objectives. However, his proof of this result is based upon a random-coding argument. To date, despite considerable research effort, the only case where we know how to construct coding schemes that achieve secrecy capacity is when Eve's channel$C_{2}$is an erasure channel, or a combinatorial variation thereof.

We examine the well-known problem of determining the capacity of multidimensional run-length-limited constrained systems. By recasting the problem, which is essentially a combinatorial counting problem, into a probabilistic setting, we are able to derive new lower and upper bounds on the capacity of (0,k)-RLL systems. These bounds are better than all previously-known analytical bounds fork≥ 2, and are tight asymptotically. Thus, we settle the open question: what is the rate at which the capacity of (0,k)-RLL systems converges to 1 ask→ ∞? We also provide the first nontrivial upper bound on the capacity of general (d,k)-RLL systems.

Suppose that Alice wishes to send messages to Bob through a communication channel C1, but her transmissions also reach an eavesdropper Eve through another channel C2. This is the wiretap channel model introduced by Wyner in 1975. The goal is to design a coding scheme that makes it possible for Alice to communicate both reliably and securely. Reliability is measured in terms of Bob's probability of error in recovering the message, while security is measured in terms of the ratio of Eve's equivocation about the message to its a priori entropy. Wyner showed that the situation is characterized by a single constant Cs, called the secrecy capacity, which has the following meaning: for all ε > 0, there exist coding schemes of rate R ≥ Cs- ε that asymptotically achieve both the reliability and the security objectives. However, his proof of this result is based upon a nonconstructive random-coding argument. To date, despite a considerable research effort, the only case where we know how to construct codes that achieve secrecy capacity is when Eve's channel C2is an erasure channel, or a combinatorial variation thereof. Polar codes were recently introduced by Arikan. They achieve the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. In this paper, we use polar codes to construct a coding scheme that achieves the secrecy capacity of general wiretap channels. Our construction works for any instantiation of the wiretap channel model, as originally defined by Wyner, as long as both C1and C2are symmetric and binary-input.

The operator channel was introduced by Koetter and Kschischang as a model of errors and erasures for randomized network coding, in the case where network topology is unknown (the noncoherent case). The input and output of the operator channel are vector subspaces of the ambient space; thus error-correcting codes for this channel are collections of such subspaces. Koetter and Kschischang also constructed a remarkable family of codes for the operator channel. The Koetter-Kschischang codes are similar to Reed-Solomon codes in that codewords are obtained by evaluating certain (linearized) polynomials. In this paper, we consider the problem of list-decoding the Koetter-Kschischang codes on the operator channel. In a sense, we are able to achieve for these codes what Sudan was able to achieve for Reed-Solomon codes. In order to do so, we have to modify and generalize the original Koetter-Kschischang construction in many important respects. The end result is this: for any integer L, our list-L decoder guarantess successful recovery of the message subspace provided the normalized dimension of the error is at most L - L2(L + 1)/2-R where R is the normalized rate of the code. Just as in the case of Sudan's list-decoding algorithm, this exceeds the previously best-known error-correction radius 1 - R, demonstrated by Koetter and Kschischang, for low rates R.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. WOM-codes were first presented by Rivest and Shamir and are designed for efficiently storing and updating data in the WOM. A WC[n, k, t] WOM-Code CWis a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The WOM-Rate of CW, defined to be Rt(CW) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions that can correct a single cell-error were presented by Zémor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-codes with a better WOM-rate. Our construction can be adjusted also for single-error-detection, double-error-correction, and triple-error-correction. For the latter case, we use triple-error-correcting BCH-like codes, which were showed by Kasami and more recently described again by Bracken and Helleseth.

Several new applications and a number of new mathematical techniques have increased the research on error-correcting codes in the Lee metric in the last decade. In this work we consider several coding problems and constructions of error-correcting codes in the Lee metric. First, we consider constructions of dense error-correcting codes in relatively small dimensions over small alphabets. The second problem we solve is construction of diametric perfect codes with minimum distance four. We will construct such codes over various lengths and alphabet sizes. The third problem is to transfer an n-dimensional Lee sphere with large radius into a shape, with the same volume, located in a relatively small box. Hadamard matrices play an essential role in the solutions for all three problems. A construction of codes based on Hadamard matrices will start our discussion. These codes approach the sphere packing bound for very high rate range and appear to be the best known codes over some sets of parameters.

Parallel programming is an important tool used in flash memories to achieve high write speed. In parallel programming, a common programm voltage is applied to many cells for simultaneous charge injection. This property significantly simplifies the complexity of the memory hardware, and is a constraint that limits the storage capacity of flash memories. Another important property is that cells have different hardness for charge injection. It makes the charge injected into cells differ even when the same program voltage is applied to them. In this paper, we study the parallel programming of flash memory cells, focusing on the above two properties. We present algorithms for parallel programming when there is information on the cells' hardness for charge injection, but there is no feedback information on cell levels during programming. We then proceed to the programming model with feedback information on cell levels, and study how well the information on the cells' hardness for charge injection can be obtained. The results can be useful for understanding the storage capacity of flash memories with parallel programming.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. A t-write WOM-code is a coding scheme for storing t messages in n cells in such a way that each cell can change its value only from the zero state to the one state. The WOM-rate of a t-write WOM-code is the ratio of the total amount of information written to the WOM in t writes to the number of cells. In this paper we present a family of 2-write WOM-codes. It is shown how to construct from each linear code C a 2-write WOM-code. Then, we find 2-write WOM-codes that improve the best known WOM-rate with two writes. This scheme is proved to be capacity achieving when the parity check matrix of the linear code C is chosen uniformly at random. Finally, we show how to take advantage of 2-write WOM-codes in order to construct codes for the Blackwell channel.

Flash memory is a nonvolatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine both the longevity and the efficiency of a flash memory. Therefore, when data in a NAND flash memory are reorganized, minimizing the total number of block erasures required to achieve the desired data movement is an important goal. This leads to the flash data movement problem studied in this paper. We show that coding can significantly reduce the number of block erasures required for data movement, and present several optimal or nearly optimal data-movement algorithms based upon ideas from coding theory and combinatorics. In particular, we show that the sorting-based (noncoding) schemes require$O(n\log n)$erasures to move data among$n$blocks, whereas coding-based schemes require only$O(n)$erasures. Furthermore, coding-based schemes use only one auxiliary block, which is the best possible and achieve a good balance between the number of erasures in each of the$n+1$blocks.

NAND flash memories are currently the most widely used flash memories. In a NAND flash memory, although a cell block consists of many pages, to rewrite one page, the whole block needs to be erased and reprogrammed. Block erasures determine the longevity and efficiency of flash memories. So when data is frequently reorganized, which can be characterized as a data movement process, how to minimize block erasures becomes an important challenge. In this paper, we show that coding can significantly reduce block erasures for data movement, and present several optimal or nearly optimal algorithms. While the sorting-based non-coding schemes require O(n log n) erasures to move data among n blocks, coding-based schemes use only O(n) erasures and also optimize the utilization of storage space.

The probability of error in the Koetter-Vardy algebraic soft-decoding algorithm for Reed-Solomon codes is determined by the multiplicity assignment scheme used. A multiplicity assignment scheme converts the reliability matrix Pi, consisting of the probabilities observed at the channel output, into a multiplicity matrix M that specifies the algebraic interpolation conditions. Using the method of types, Sanov's theorem in particular, we obtain tight exponential bounds on the probability of decoding error for a given multiplicity matrix. These bounds turn out to be essentially the same as the Chernoff bound. We establish several interesting properties of the multiplicity matrix Mdaggerwhich minimizes the exponent of the probability of error. Based on these observations, we develop a low-complexity multiplicity assignment scheme which uses nested bisection to solve for Mdagger. This scheme provides the same probability of error as a known scheme based upon the Chernoff bound, but with much lower complexity. We also derive a simple condition on the reliability matrix Pi which guarantees an exponentially small probability of error. This condition is akin to an error-correction radius, and can be used to study the performance of algebraic soft-decoding.

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n, k, t)qflash code ¿ is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 ¿ 1 or 1 ¿ 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of ¿, defined as ¿(¿) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write defficiency of O(qk2). On the other hand, the best known lower bound on write deficiency is ¿(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called ¿indexed¿ flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write defficiency of the resulting flash codes is O(qk log k) if q ¿ log2k, and at most O(k log2k) otherwise.

The projective space of order n over the finite field Fq, denoted Pq(n), is the set of all subspaces of the vector space Fnq. The distance function d(U,V) = dim U + dim V - 2 dim(UcapV) turns Pq(n) into a metric space. With this, an (n, M, d) code C in projective space is a subset of Pq(n) of size M such that the distance between any two codewords (subspaces) is at least d. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an (n, M, d) code can correct t packet errors and rho packet erasures introduced (adversarially) anywhere in the network as long as 2t + 2pq(n), which may be thought of as counterparts of the classical bounds in coding theory due to Johnson, Delsarte, and Gilbert-Varshamov. Some of these are stronger than all the previously known bounds, at least for certain code parameters. Next, we examine the fundamental concepts of "linear codes" and "complements" in the context of Pq(n). These turn out to be considerably more involved than their classical counterparts. In particular, we construct linear codes of size 2nand conjecture that larger linear codes do not exist. We also present several specific constructions of codes and code families in Pq(n). Finally, we prove that nontrivial perfect codes in Pq(n) do not exist.

For a linear code C, the stopping redundancy of C is defined as the minimum number of check nodes in a Tanner graph T for C such that the size of the smallest stopping set in T is equal to the minimum distance of C. Han and Siegel recently proved an upper bound on the stopping redundancy of general linear codes, using probabilistic analysis. For most code parameters, this bound is the best currently known. In this correspondence, we present several improvements upon this bound.

Algebraic soft-decision decoding is a recent break-through in decoding of Reed-Solomon codes and significant decoding gain can be achieved over conventional hard-decision decoding. Bivariate polynomial factorization is an important step of the new decoding algorithm and contributes to a significant portion of the overall decoding latency. In this paper, a novel architecture based on direct root computation is proposed to greatly reduce the factorization latency. Direct root computation is feasible because in most practical applications of algebraic soft-decision decoding of RS codes, sufficient decoding gain can be achieved with a relatively low interpolation cost, which results in bivariate polynomial of small Y-degree. Compared with existing works, not only does our new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient.

Algebraic soft-decision decoding (Koetter and Vardy, 2003) is a recent breakthrough in decoding of Reed-Solomon codes and it achieves significant decoding gain over conventional hard-decision decoding. In the bivariate polynomial factorization step of the new decoding algorithm, solving polynomial equations is required and it may contribute to a significant portion of the overall decoding latency. This paper presents a low-latency direct root computation architecture, which should lead to a factorization architecture that is of lower latency and more area efficient

Recently, Lee and O'Sullivan proposed a new interpolation algorithm for algebraic soft-decision decoding of Reed- Solomon codes. In some cases, the Lee-O'Sullivan algorithm turns out to be substantially more efficient than alternative interpolation approaches, such as Koetter's algorithm. Herein, we combine the re-encoding coordinate transformation, originally developed in the context of Koetter's algorithm, with the recent interpolation technique of Lee and O'Sullivan. To this end, we develop a new basis construction algorithm, which takes into account the additional constraints imposed by the reduced interpolation problem that results upon the re-encoding transformation. This reduces the computational and storage complexity of the Lee-O'Sullivan algorithm by orders of magnitude, and makes it directly comparable to Koetter's algorithm in situations of practical importance.

Bivariate polynomial factorization is an important stage of algebraic soft-decision decoding of Reed-Solomon (RS) codes and contributes to a significant portion of the overall decoding latency. With the exhaustive search-based root computation method, factorization latency is dominated by the root computation step, especially for RS codes defined over very large finite fields. The root-order prediction method proposed by Zhang and Parhi only improves average latency, but does not have any effect on the worst-case latency of the factorization procedure. Thus, neither approach is well-suited for delay-sensitive applications. In this paper, a novel architecture based on direct root computation is proposed to greatly reduce the factorization latency. Direct root computation is feasible because in most practical applications of algebraic soft-decision decoding of RS codes, enough decoding gain can be achieved with a relatively low interpolation cost, which results in a bivariate polynomial with low Y-degree. Compared with existing works, not only does the new architecture have a significantly smaller worst-case decoding latency, but it is also more area efficient since the corresponding hardware for routing polynomial coefficients is eliminated.

The most computationally demanding step in soft-decision decoding of RS codes is bivariate polynomial interpolation. The reencoding and coordinate transformation based technique can significantly reduce the computation complexity of the original interpolation problem, thus making the algebraic soft-decision decoder practically feasible. In this paper, an implementation of the reencoding and coordinate transformation procedure is presented. The novelties of our design include a fast algorithm to determine the reencoding points, an area efficient erasure-only RS decoding architecture, and an overlapped scheduling of the various procedures required for the reencoding process to reduce the overall latency. The synthesis result shows that the proposed design is sufficiently fast for any existing or developing interpolation architecture.

Algebraic soft-decision decoding of Reed-Solomon (RS) codes delivers promising coding gains over conventional hard-decision decoding. The most computationally demanding step in the soft-decision decoding is bivariate polynomial interpolation. In this paper, we present a very efficient high speed interpolation architecture based on hybrid data representation. It is shown that the proposed architecture is inherently scalable and can be extensively pipelined to achieve very high clock speed. By further incorporating the maximum overlapping for computations at adjacent iterations, the proposed architecture demonstrates significant advantages over conventional designs. It is estimated that over 1 Gbps data rate can be achieved using the presented work with moderate complexity.

The multivariate interpolation decoding (MID) algorithm for certain Reed-Solomon codes was recently introduced by Parvaresh and Vardy. The MID algorithm attempts to list-decode up to ntauMID= n (1 -RM(M+1)/) errors, in a Reed-Solomon code of length n and rate R, using (M+1)-variate polynomial interpolation. This improves on the Guruswami-Sudan decoding radius of tauGS= 1 - radicR by a large margin, especially for high-rate codes. The problem is that successful decoding is not guaranteed: there are certain patterns of less than ntauMIDerrors which the MID algorithm fails to decode. Nevertheless, simulations show that the actual performance of the MID decoder is very close to what one would expect if all patterns of up to ntauMIDerrors were corrected. On the other hand, analysis of the failure probability for the MID algorithm is extremely difficult, and there were no analytic results so far to confirm this empirically observed behavior. In this work, we provide such analytic results: we present a detailed analysis of the probability of failure in the MID algorithm for the special case where M = 2 and the interpolation multiplicity is m = 1. In this case, the MID algorithm attempts to correct up to ntau2,1errors, where tau2,1= 1 -3radic6R2. We consider the situation where symbol values received from the channel at the erroneous positions are distributed uniformly at random (a version of the q-ary symmetric channel). We show that, with high probability, the performance of the MID algorithm is very close to the optimum in this case. Specifically, we prove that if the fraction of positions in error is at most tau2,1-O(R5/3), then the probability of failure in the MID algorithm is at most n-Omega(n). Thus the probability of failure is, indeed, negligible for large n in this case

The branching program is a fundamental model of (nonuniform) computation, which conveniently captures both time and space restrictions. Recently, an interesting connection between the minimum distance of a code and the branching program complexity of its encoder was established by Bazzi and Mitter. Here, we establish a relationship between the minimum distance of a linear code C and the branching program complexity of computing the syndrome function for C and/or its dual code Cperp. Specifically, let C be an (n, k, d) linear code over Fq, and suppose that there is a branching program B that computes the syndrome vector with respect to the dual code Cperpin time T and space S. We prove that the minimum distance of C is then bounded by d les 2T(S+log2T)/klog2q + 1. We also consider the average-case complexity in the branching program model: we show that if B computes the syndrome with respect to Cperpin expected time T and expected space S, then d les 12T(S+log2T + 6)/klog2q + 1. Since there are trivial branching programs that compute the syndrome vector with time-space complexity ST = O(n2log q), the bound in (2) is asymptotically tight. Furthermore, with the help of the bounds in (1) and (2), we prove the conjecture of Bazzi and Mitter that a sequence of codes whose encoder function is computable by a branching program with time-space complexity ST = o(n2) cannot be asymptotically good, for the special case of self-dual codes. Our proof of these results is based on the probabilistic method developed by Borodin-Cook and Abrahamson

Summary form only given, as follows. We will survey the fi eld of algebraic and combinatorial coding theory, in an attempt to answer the question in the title. In particular, we shall revisit classical problems that are yet unsolved, review promising advances in the past decade, elaborate upon recent connections to other areas, and speculate what may lie ahead for the fi eld.

We consider a number of constrained coding techniques that can be used to mitigate a nonlinear effect in the optical fiber channel that causes the formation of spurious pulses, called "ghost pulses". Specifically, if b/sub 1/b/sub 2/...b/sub n/ is a sequence of bits sent across an optical channel, such that b/sub k/=b/sub l/=b/sub m/=1 for some k,l,m (not necessarily all distinct) but b/sub k+l-m/=0, then the ghost-pulse effect causes b/sub k+l-m/ to change to 1, thereby creating an error. Such errors do not occur if the sequence of bits satisfies the following constraint: for all integers k,l,m such that b/sub k/=b/sub l/=b/sub m/=1, we have b/sub k+l-m/=1. We call this the binary ghost-pulse (BGP) constraint. We will show, however, that the BGP constraint has zero capacity, implying that sequences satisfying this constraint cannot carry much information. Consequently, we consider a more sophisticated coding scheme, which uses ternary sequences satisfying a certain ternary ghost-pulse (TGP) constraint. We further relax these constraints by ignoring interactions between symbols that are more than a certain distance t apart in the transmitted sequence. Analysis of the resulting BGP(t) and TGP(t) constraints shows that these have nonzero capacities, and furthermore, the TGP(t)-constrained codes can achieve rates that are significantly higher than those for the corresponding BGP(t) codes. We also discuss the design of encoders and decoders for coding into the BGP, BGP(t), and TGP(t) constraints.

Iterative decoding algorithms may be viewed as high-dimensional nonlinear dynamical systems, depending on a large number of parameters. In this work, we introduce a simplified description of several iterative decoding algorithms in terms of the a posteriori average entropy, and study them as a function of a single parameter that closely approximates the signal-to-noise ratio (SNR). Using this approach, we show that virtually all the iterative decoding schemes in use today exhibit similar qualitative dynamics. In particular, a whole range of phenomena known to occur in nonlinear systems, such as existence of multiple fixed points, oscillatory behavior, bifurcations, chaos, and transient chaos are found in iterative decoding algorithms. As an application, we develop an adaptive technique to control transient chaos in the turbo-decoding algorithm, leading to a substantial improvement in performance. We also propose a new stopping criterion for turbo codes that achieves the same performance with considerably fewer iterations.

It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of Copf, defined as the minimum number of rows in a parity- check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely, s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes

We introduce a new family of error-correcting codes that have a polynomial-time encoder and a polynomial-time list-decoder, correcting a fraction of adversarial errors up to /spl tau//sub M/ = 1 - /sup M+1//spl radic/(M/sup M/R/sup M/) where R is the rate of the code and M /spl ges/ 1 is an arbitrary integer parameter. This makes it possible to decode beyond the Guruswami-Sudan radius of 1 /spl radic/R for all rates less than 1/16. Stated another way, for any /spl epsiv/ > 0, we can list-decode in polynomial time a fraction of errors up to 1 - /spl epsiv/ with a code of length n and rate /spl Omega/(/spl epsiv//log(1//spl epsiv/)), defined over an alphabet of size n/sup M/ = n/sup O(log(1//spl epsiv/))/. Notably, this error-correction is achieved in the worst-case against adversarial errors: a probabilistic model for the error distribution is neither needed nor assumed. The best results so far for polynomial-time list-decoding of adversarial errors required a rate of O(/spl epsiv//sup 2/) to achieve the correction radius of 1 - /spl epsiv/. Our codes and list-decoders are based on two key ideas. The first is the transition from bivariate polynomial interpolation, pioneered by Sudan and Guruswami-Sudan [1999], to multivariate interpolation decoding. The second idea is to part ways with Reed-Solomon codes, for which numerous prior attempts at breaking the O(/spl epsiv//sup 2/) rate barrier in the worst-case were unsuccessful. Rather than devising a better list-decoder for Reed-Solomon codes, we devise better codes. Standard Reed-Solomon encoders view a message as a polynomial f(X) over a field F/sub q/, and produce the corresponding codeword by evaluating f(X) at n distinct elements of F/sub q/. Herein, given f(X), we first compute one or more related polynomials g/sub 1/(X), g/sub 2/(X), ..., g/sub M-1/(X) and produce the corresponding codeword by evaluating all these polynomials. Correlation between f(X) and g/sub i/(X), carefully designed into our encoder, then provides the additional information we need to recover the encoded message from the output of the multivariate interpolation process.

We consider hard-decision iterative decoders for product codes over the erasure channel, which employ repeated rounds of decoding rows and columns alternatingly. We derive the exact asymptotic probability of decoding failure as a function of the error-correction capabilities of the row and column codes, the number of decoding rounds, and the channel erasure probability. We examine both the case of codes capable of correcting a constant amount of errors, and the case of codes capable of correcting a constant fraction of their length

It is now well known that the performance of a linear code Copf under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for Copf. Several recent papers refer to this parameter as the stopping distance s of Copf. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for Copf depends on the corresponding choice of a parity-check matrix. It is easy to see that s les d, where d is the minimum Hamming distance of Copf, and we show that it is always possible to choose a parity-check matrix for Copf (with sufficiently many dependent rows) such that s = d. We thus introduce a new parameter, termed the stopping redundancy of Copf, defined as the minimum number of rows in a parity-check matrix H for Copf such that the corresponding stopping distance s(H) attains its largest possible value, namely s(H) = d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes

We investigate the packing and covering densities of linear and nonlinear binary codes, and establish a number of duality relationships between the packing and covering problems. Specifically, we prove that if almost all codes are good packings, then only a vanishing fraction of codes are good coverings, and vice versa: if almost all codes are good coverings, then at most a vanishing fraction of codes are good packings. We also show that any specific maximal binary code is either a good packing or a good covering, in a certain well-defined sense.

In this paper, we analyze bi-infinite sequences over the alphabet $\{0,1,\ldots,q-1\}$, for an arbitrary $q \geq 2$, that satisfy the q-ary ghost pulse (qGP) constraint. A sequence $\x = {(x_k)}_{k \in \Z} \in \{0,1,\ldots,q-1\}^{\Z}$ satisfies the qGP constraint if for all $k,l,m \in \Z$ such that $x_k$, $x_l$ and $x_m$ are nonzero and equal, $x_{k+l-m}$ is also nonzero. This constraint arises in the context of coding for communication over a fiber optic medium. We show, using techniques from Ramsey theory, that if $\x$ satisfies the qGP constraint, then the set $\supp(\x) = \{l \in \Z:\ x_l \neq 0\}$ is the disjoint union of cosets of some subgroup, $k\Z$, of $\Z$, and a set of zero density. We provide much sharper results in the special cases of $q = 2$ and $q=3$. In the former case, we show that the corresponding binary ghost pulse constraint has zero capacity, and based on our results for the latter case, we conjecture that the capacity of the ternary ghost pulse constraint is also zero.

Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum-likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.

The most computationally demanding step in algebraic soft-decision decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes is bivariate polynomial interpolation. The interpolation problem consists of computing a polynomial Q(X,Y) that passes through a given set of points P with prescribed multiplicities M. We propose a new divide-and-conquer method that can potentially reduce the complexity of interpolation. Specifically, we split the interpolation problem {P,M} into two problems {P1,M1} and {P2,M2}, and then show that the intersection of the corresponding polynomial ideals I(P1,M1)capI(P2,M2) is equal to their product. Our divide-and-conquer approach differs from the one suggested by Feng-Giraud [G.L.Feng, (2002)] in that the interpolation subproblems {P2,M2} and {P2,M2} are solved independently and only afterwards their solutions are merged. This makes it possible to solve these problems in parallel

Biinfinite sequences X=(x/sub k/)/sub k/spl isin//spl Zopf// over the alphabet {0,1,...,q-1}, for an arbitrary q/spl ges/2, that satisfy the following q-ary ghost pulse (qGP) constraint: for all k,l,m/spl isin//spl Zopf/ such that x/sub k/,x/sub l/,x/sub m/ are nonzero and equal, x/sub k+l-m/ is also nonzero is studied in this paper. This constraint arises in the context of coding to combat the formation of spurious "ghost" pulses in high data-rate communication over an optical fiber. We show using techniques from Ramsey theory that if x satisfies the /sub q/GP constraint, then the support of x is a disjoint union of cosets of a subgroup k/spl Zopf/ of /spl Zopf/ and a set of zero density.

The main computational steps in algebraic soft-decoding and/or Sudan-type list-decoding of Reed-Solomon codes are interpolation and factorization. The interpolation consists of computing a bivariate polynomial Q(X,Y) that passes through a prescribed set of points with prescribed multiplicities. Using the iterative algorithm of Koetter (1996), this computation can be accomplished in time O(N2), where N is the number of linear equations satisfied by the coefficients of Q(X,Y). Here, we recast the iterative interpolation procedure of (R. Koetter, 1996) as a computation of the product of a certain chain of polynomial matrices. We then derive a dynamic-programming algorithm which optimizes the multiplication order in computing this matrix chain. The resulting optimization reduces the number of finite-field operations required to compute Q(X,Y) by a factor of about two

It is well-established "folk knowledge" that in order to be iteratively decodable, a code should have a sparse parity-check matrix, as it has some qualitative and quantitative properties for finite-length codes.

A tiling of $\F^n$ is a pair (V,A) of subsets of $\F^n$ such that every $x \in \F^n$ can be written in exactly one way as x = v + a with $v \in V$ and $a \in A$. A tiling (V,A) of $\F^n$ is said to be full-rank if $\rank(V)=\rank(A)=n$ and $\zero \in (V\! \cap A)$. It is known that every tiling (V,A)$ decomposes into smaller tilings that are either trivial or full rank. It is furthermore known that full-rank tilings of $\F^n$ exist for all $n \geq 10$ and do not exist for $n \leq 8$. The last case n= 9 is resolved in this paper, thereby proving that full-rank tilings of $\F^n$ exist if and only if $n \ge 10$. To establish this result, we use two different methods. The first method employs group characters to show that the sets V and A in a full-rank tiling (V,A) of $\F^9$ must have a certain structure. The second method is based on the classification of [14,5,3] binary linear codes and uses a fast algorithm for the exact cover problem. Both methods rely on a carefully designed exhaustive computer search to complete the proof.

Given positive integers n and d, let A/sub 2/(n,d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A/sub 2/(n,d)/spl ges/2/sup n//V(n,d-l), where V(n,d) = /spl sigma//sub i=0//sup d/(/sub i//sup n/) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A/sub 2/(n, d)/spl ges/c2/sup n//V(n,d-1)log/sub 2/V(n, d-1) whenever d/n/spl les/0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.

The main computational steps in algebraic soft decoding, as well as Sudan-type list decoding, of Reed-Solomon codes are interpolation and factorization. A series of transformations is given for the interpolation problem that arises in these decoding algorithms. These transformations reduce the space and time complexity to a small fraction of the complexity of the original interpolation problem. A factorization procedure that applies directly to the reduced interpolation problem is also presented.

We show that there are no full-rank tilings of $\mathbb{F}^8_{\kern -1pt 2}$, using a carefully designed exhaustive search. This solves an open problem posed in [T. Etzion and A. Vardy, SIAM J. Discrete Math., 11 (1998), pp. 205--233]. This also implies that a full-rank perfect binary code of length 15 with a kernel of dimension 7 does not exist.

Basic structural properties of tail-biting trellises are investigated. We start with rigorous definitions of various types of minimality for tail-biting trellises. We then show that biproper and/or nonmergeable tail-biting trellises are not necessarily minimal, even though every minimal tail-biting trellis is biproper. Next, we introduce the notion of linear (or group) trellises and prove, by example, that a minimal tail-biting trellis for a binary linear code need not have any linearity properties whatsoever. We observe that a trellis - either tail-biting or conventional - is linear if and only if it factors into a product of elementary trellises. Using this result, we show how to construct, for any given linear code /spl Copf/, a tail-biting trellis that minimizes the product of state-space sizes among all possible linear tail-biting trellises. We also prove that every minimal linear tail-biting trellis for /spl Copf/ arises from a certain n/spl times/n characteristic matrix, and show how to compute this matrix in time O(n/sup 2/) from any basis for /spl Copf/. Furthermore, we devise a linear-programming algorithm that starts with the characteristic matrix and produces a linear tail-biting trellis for /spl Copf/; which minimizes the maximum state-space size. Finally, we consider a generalized product construction for tail-biting trellises, and use it to prove that a linear code /spl Copf/ and its dual /spl Copf//sup /spl perp///spl Copf//sup /spl perp///spl Copf//sup /spl perp///spl Copf//sup /spl perp// have the same state-complexity profiles.

A polynomial-time soft-decision decoding algorithm for Reed-Solomon codes is developed. This list-decoding algorithm is algebraic in nature and builds upon the interpolation procedure proposed by Guruswami and Sudan(see ibid., vol.45, p.1757-67, Sept. 1999) for hard-decision decoding. Algebraic soft-decision decoding is achieved by means of converting the probabilistic reliability information into a set of interpolation points, along with their multiplicities. The proposed conversion procedure is shown to be asymptotically optimal for a certain probabilistic model. The resulting soft-decoding algorithm significantly outperforms both the Guruswami-Sudan decoding and the generalized minimum distance (GMD) decoding of Reed-Solomon codes, while maintaining a complexity that is polynomial in the length of the code. Asymptotic analysis for alarge number of interpolation points is presented, leading to a geo- metric characterization of the decoding regions of the proposed algorithm. It is then shown that the asymptotic performance can be approached as closely as desired with a list size that does not depend on the length of the code.

In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner (1995) variation of the Pohst (1981) method, is implemented. Given an arbitrary point x /spl isin/ /spl Ropf//sup m/ and a generator matrix for a lattice /spl Lambda/, the algorithm computes the point of /spl Lambda/ that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan (1983, 1987) algorithm and an experimental comparison with the Pohst (1981) algorithm and its variants, such as the Viterbo-Boutros (see ibid. vol.45, p.1639-42, 1999) decoder. Modifications of the algorithm are developed to solve a number of related search problems for lattices, such as finding a shortest vector, determining the kissing number, computing the Voronoi (1908)-relevant vectors, and finding a Korkine-Zolotareff (1873) reduced basis.

Two-dimensional interleaving schemes with repetitions are considered. These schemes are required for the correction of two-dimensional bursts (or clusters) of errors in applications such as optical recording and holographic storage. We assume that a cluster of errors may have an arbitrary shape, and is characterized solely by its area t. Thus, an interleaving scheme A(t,r) of strength t with r repetitions is an (infinite) array of integers defined by the property that every integer appears no more than r times in any connected component of area t. The problem is to minimize, for a given t and r, the interleaving degree deg A(t,r), which is the total number of distinct integers contained in the array. Optimal interleaving schemes for r=1 (no repetitions) have been devised in earlier work. Here, we consider interleaving schemes for r/spl ges/2. Such schemes reduce the overall redundancy, yet are considerably more difficult to construct and analyze. To this end, we generalize the concept of L/sub 1/-distance and introduce the notions of tristance, quadristance, and more generally r-dispersion. We focus on the special class of interleaving schemes, called lattice interleavers, that is akin to the class of linear codes in coding theory. We construct efficient lattice interleavers for r=2,3,4 and some higher values of r. For r=2,3 we show that these lattice interleavers are either optimal for all t or asymptotically optimal for t/spl rarr//spl infin/. We present the results of an extensive computer search that yields the optimal lattice interleavers for r=2,3,4,5,6 and t up to about 1000. Finally, we consider an alternative connectivity model for clusters, where two elements in an array are connected if they are adjacent horizontally, vertically, or diagonally. We establish relations between interleavers for this model and interleavers for the standard horizontal/vertical connectivity model, and show that these models become equivalent for t/spl rarr//spl infin/. We conclude with some conjectures and open problems.

This paper analyzes phase trajectories and fixed points of the turbo decoding algorithm as a function of the signal-to-noise ratio (SNR). By exploiting the large length of turbo codes, the turbo decoding algorithm is treated as a single-parameter dynamical system, parameterized (approximately) by the SNR. This parameterization, along "with" extensive simulations at practical SNRs and asymptotic analysis as SNR goes to zero and infinity, is used to subdivide the entire SNR range into three regions with the "waterfall region" in the middle. The turbo decoding algorithm has distinctive phase trajectories and convergence properties in these three SNR regions. This paper also investigates existence and properties of fixed points in these SNR regions. The main fixed points of the turbo decoding algorithm are classified into two categories. In a wide range of SNRs (corresponding to bit-error rates less than 10/sup -1/), the decoding algorithm has "unequivocal" fixed points which correspond to mostly correct decisions on the information bits. Within this range, toward the lower values of SNR, there is another fixed point which corresponds to many erroneous decision on the information bits. Fixed points of this type are referred to as "indecisive" fixed points. It turns out that the indecisive fixed points bifurcate and disappear for SNRs in the waterfall region. This paper associates the qualitative transition of phase trajectories in the waterfall region to the bifurcation of indecisive fixed points. These bifurcations also explain empirically observed quasi-periodic and periodic phase trajectories of the turbo decoding algorithm.

Let A(n, d) denote the maximum possible number of codewords in an (n, d) binary code. We establish four new bounds on A(n, d), namely, A(21, 4)/spl les/43689, A(22, 4)/spl les/87378, A(22, 6)/spl les/6941, and A(23, 4)/spl les/173491. Furthermore, using previous upper bounds on the size of constant-weight binary codes, we reapply known methods to generate a table of bounds on A(n, d) for all n/spl les/28. This table extends the range of parameters compared with previously known tables.

By tracing the flow of computations in the iterative decoders for low-density parity-check codes, we formulate a signal-space view for a finite number of iterations in a finite-length code. On a Gaussian channel, maximum a posteriori (MAP) codeword decoding (or "maximum-likelihood decoding") decodes to the codeword signal that is closest to the channel output in Euclidean distance. In contrast, we show that iterative decoding decodes to the "pseudosignal" that has highest correlation with the channel output. The set of pseudosignals corresponds to "pseudocodewords", only a vanishingly small number of which correspond to codewords. We show that some pseudocodewords cause decoding errors, but that there are also pseudocodewords that frequently correct the deleterious effects of other pseudocodewords.

We present a detailed analysis of generalized minimum distance (GMD) decoding algorithms for Euclidean space codes. In particular, we completely characterize GMD decoding regions in terms of receiver front-end properties. This characterization is used to show that GMD decoding regions have intricate geometry. We prove that although these decoding regions are polyhedral, they are essentially always nonconvex. We furthermore show that conventional performance parameters, such as error-correction radius and effective error coefficient, do not capture the essential geometric features of a GMD decoding region, and thus do not provide a meaningful measure of performance. As an alternative, probabilistic estimates of, and upper bounds upon, the performance of GMD decoding are developed. Furthermore, extensive simulation results, for both low-dimensional and high-dimensional sphere-packings, are presented. These simulations show that multilevel codes in conjunction with multistage GMD decoding provide significant coding gains at a very low complexity. Simulated performance, in both cases, is in remarkably close agreement with our probabilistic approximations.

Let A(n,d,w) denote the maximum possible number of codewords in an (n,d,w) constant-weight binary code. We improve upon the best known upper bounds on A(n,d,w) in numerous instances for n/spl les/24 and d/spl les/12, which is the parameter range of existing tables. Most improvements occur for d=8, 10, where we reduce the upper bounds in more than half of the unresolved cases. We also extend the existing tables up to n/spl les/28 and d/spl les/14. To obtain these results, we develop new techniques and introduce new classes of codes. We derive a number of general bounds on A(n,d,w) by means of mapping constant-weight codes into Euclidean space. This approach produces, among other results, a bound on A(n,d,w) that is tighter than the Johnson bound. A similar improvement over the best known bounds for doubly-constant-weight codes, studied by Johnson and Levenshtein, is obtained in the same way. Furthermore, we introduce the concept of doubly-bounded-weight codes, which may be thought of as a generalization of the doubly-constant-weight codes. Subsequently, a class of Euclidean-space codes, called zonal codes, is introduced, and a bound on the size of such codes is established. This is used to derive bounds for doubly-bounded-weight codes, which are in turn used to derive bounds on A(n,d,w). We also develop a universal method to establish constraints that augment the Delsarte inequalities for constant-weight codes, used in the linear programming bound. In addition, we present a detailed survey of known upper bounds for constant-weight codes, and sharpen these bounds in several cases. All these bounds, along with all known dependencies among them, are then combined in a coherent framework that is amenable to analysis by computer. This improves the bounds on A(n,d,w) even further for a large number of instances of n, d, and w.

The parametrized complexity of a number of fundamental problems in the theory of linear codes and integer lattices is explored. Concerning codes, the main results are that MAXIMUM-LIKELIHOOD DECODING and WEIGHT DISTRUBUTION are hard for the parametrized complexity class W[1]. The NP-completeness of these two problems was established by Berlekamp, McEliece, and van Tilborg in 1978 using by means of a reduction from THREE-DIMENSIONAL MATCHING. On the other hand, our proof of hardness for W[1] is based on a parametric polynomial-time transformation from PERFECT CODE in graphs. An immediate consequence of our results is that bounded-distance decoding is likely to be hard for binary linear codes. Concerning lattices, we address the THETA SERIES problem of determining for an integer lattice $\L$ %given by a set of generators, and a positive integer k whether there is a vector $x \in \L$ of Euclidean norm k. We prove here for the first time that THETA SERIES is NP-complete and show that it is also hard for W[1]. Furthermore, we prove that the NEAREST VECTOR problem for integer lattices is hard for W[1]. These problems are the counterparts of WEIGHT DISTRUBUTION and MAXIMUM-LIKELIHOOD DECODING for lattices. Relations between all these problems and combinatorial problems in graphs are discussed.

Ordered binary decision diagrams (OBDDs) are graph-based data structures for representing Boolean functions. They have found widespread use in computer-aided design and in formal verification of digital circuits. Minimal trellises are graphical representations of error-correcting codes that play a prominent role in coding theory. This paper establishes a close connection between these two graphical models, as follows. Let /spl Cscr/ be a binary code of length n, and let f/sub c/(x/sub 1/, ..., x/sub n/) be the Boolean function that takes the value 0 at x/sub 1/, ..., x/sub n/ if and only if (x/sub 1/, ..., x/sub n/)/spl isin//spl Cscr/. Given this natural one-to-one correspondence between Boolean functions and binary codes, we prove that the minimal proper trellis for a code /spl Cscr/ with minimum distance d>1 is isomorphic to the single-terminal OBDD for its Boolean indicator function f/sub c/(x/sub 1/, ..., x/sub n/). Prior to this result, the extensive research during the past decade on binary decision diagrams (in computer engineering) and on minimal trellises (in coding theory) has been carried out independently. As outlined in this work, the realization that binary decision diagrams and minimal trellises are essentially the same data structure opens up a range of promising possibilities for transfer of ideas between these disciplines.

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 "convolutional Golay code" with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F/sub 4/. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F/sub 4/, and the Z/sub 4/-linear (8. 4, 4) octacode.

If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R/spl ges/0.5 then d/spl les/2, while if R<0.5 then C is obtained from a code of rate /spl ges/0.5 and distance /spl les/2 by simply repeating certain symbols. In the latter case, we prove that d/spl les/[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.

We present a lower bound on the probability of symbol error for maximum-likelihood decoding of lattices and lattice codes on a Gaussian channel. The bound is tight for error probabilities and signal-to-noise ratios of practical interest, as opposed to most existing bounds that become tight asymptotically for high signal-to-noise ratios. The bound is also universal; it provides a limit on the highest possible coding gain that may be achieved, at specific symbol error probabilities, using any lattice or lattice code in n dimensions. In particular, it is shown that the effective coding gains of the densest known lattices are much lower than their nominal coding gains. The asymptotic (as n/spl rarr//spl infin/) behavior of the new bound is shown to coincide with the Shannon (1948) limit for Gaussian channels.

Although nontrivial perfect binary codes exist only for length n = 2 m -1 with $m \ge 3$ and for length n=23, many interesting problems concerning these codes remain unsolved. Herein, we present solutions to some of these problems. In particular, we show that the smallest nonempty intersection of two perfect codes of length 2 m -1 consists of two codewords, for all $m \ge 3$. We also provide a complete solution to the intersection number problem for Hamming codes. Furthermore, we prove that for $m \ge 3$, a perfect code of length 2 m-1 -1 is embedded in a perfect code $\Bbb{C}$ of length 2 m -1 if and only if ${\Bbb C}$ is not of full rank. This result implies the existence of distinct generalized Hamming weights for perfect codes, and we determine completely the generalized Hamming weights of all perfect codes that do not contain embedded full-rank perfect codes. We further explore the close ties between perfect codes and tilings: we prove that full-rank tilings of ${\Bbb F}_{2}^n$ exist for all $n \geq 14$ and show that the existence of full-rank tilings for other n is closely related to the existence of full-rank perfect codes with kernels of high dimension. We briefly survey the present state of knowledge on perfect binary codes and list several interesting and important open problems concerning perfect codes and tilings.

We present two-dimensional and three-dimensional interleaving techniques for correcting two- and three-dimensional bursts (or clusters) of errors, where a cluster of errors is characterized by its area or volume. Correction of multidimensional error clusters is required in holographic storage, an emerging application of considerable importance. Our main contribution is the construction of efficient two-dimensional and three-dimensional interleaving schemes. The proposed schemes are based on t-interleaved arrays of integers, defined by the property that every connected component of area or volume t consists of distinct integers. In the two-dimensional case, our constructions are optimal: they have the lowest possible interleaving degree. That is, the resulting t-interleaved arrays contain the smallest possible number of distinct integers, hence minimizing the number of codewords required in an interleaving scheme. In general, we observe that the interleaving problem can be interpreted as a graph-coloring problem, and introduce the useful special class of lattice interleavers. We employ a result of Minkowski, dating back to 1904, to establish both upper and lower bounds on the interleaving degree of lattice interleavers in three dimensions. For the case t/spl equiv/0 mod 6, the upper and lower bounds coincide, and the Minkowski lattice directly yields an optimal lattice interleaver. For t/spl ne/0 mod 6, we construct efficient lattice interleavers using approximations of the Minkowski lattice.

We start with an overview of algorithmiccomplexity problems in coding theory We then show that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This constitutes a proof of the conjecture Bedekamp, McEliece, van Tilborg, dating back to 1978. Extensions and applications of this result to other problems in coding theory are discussed.

Unlike block codes, n-dimensional lattices can have minimal trellis diagrams with an arbitrarily large number of states, branches, and paths. In particular, we show by a counterexample that there is no f(n), a function of n, such that all rational lattices of dimension n have a trellis with less than f(n) states. Nevertheless, using a theorem due to Hermite, we prove that every integral lattice /spl Lambda/ of dimension n has a trellis T, such that the total number of paths in T is upper-bounded by P(T)/spl les/n!(2//spl radic/3)/sup n2(n-1/2)/V(/spl Lambda/)/sup n-1/ where V(n) is the volume of /spl Lambda/. Furthermore, the number of states at time i in T is upper-bounded by |S/sub i/|/spl les/(2//spl radic/3)/sup i2(n-1)/V(/spl Lambda/)/sup 2i2/n/. Although these bounds are seldom tight, these are the first known general upper bounds on trellis complexity of lattices.

It is shown that the problem of computing the minimum distance of a binary linear code is NP-hard, and the corresponding decision problem is NP-complete. This result constitutes a proof of the conjecture of Berlekamp, McEliece, and van Tilborg (1978). Extensions and applications of this result to other problems in coding theory are discussed.

We present a novel scheme that combines decision feedback equalization (DFE) with high-rate error-detection coding in an efficient manner. The proposed scheme is shown to considerably outperform the conventional practice on channels with high SNR, such as those encountered in twisted-pair telephony systems. In order to analyze the performance of our method, we introduce an approximate mathematical model taking into account the error propagation phenomenon. Based on this model, upper and lower bounds on the overall probability of error are developed. These show that a simple low-redundancy error-detecting code, when properly integrated with the equalizer, can make the overall probability of error several orders of magnitude lower than that obtained with the conventional DFE, or with a DFE followed by an error-correcting code. Computer simulations of the proposed method have been performed for several channels, including the so-called high-bit-rate digital subscriber line (HDSL) test-loop 4, which is known to have a considerable amount of intersymbol interference. For all these channels, our results show that a reduction in the probability of error by more than three orders of magnitude can be obtained using codes of rate 0.96 and above. This, in turn, translates into power savings (coding gain) of 2.5 to 3 dB.

We study partitions of the space $\mathbb{F}_2^n $ of all the binary n-tuples into disjoint sets, where each set is an additive cosec of a given set V. Such a partition is called a tiling of $\mathbb{F}_2^n $ and denoted $(V,A)$, where A is the set of cosec representatives. We give a sufficient condition for a set V to be a tile in terms of the cardinality of $V + V$. We then employ this condition to classify all tilings with sets of small cardinality. Further, periodicity of tilings in $\mathbb{F}_2^n $ is discussed, and a simple construction of nonperiodic tilings of $\mathbb{F}_2^n $ is presented for all $n \geq 6$. It is also shown that the nonperiodic tiling of $\mathbb{F}_2^6 $ is unique. A tiling $(V,A)$ is said to be proper if V generates $\mathbb{F}_2^n $; it is said to be full rank if both V and A generate $\mathbb{F}_2^n $. We show that, in general, the classification of tilings can be reduced to the study of proper tilings. We then prove that any tiling may be decomposed into smaller tilings that are either trivial or have full rank. Existence of full-rank tilings is exhibited by showing that each tiling is uniquely associated with a perfect binary code. Moreover, it is shown that periodic full-rank tilings may be further decomposed into smaller tilings, and then the existence of nonperiodic full-rank tilings is deduced. Finally, we generalize the well-known Lloyd theorem, originally stated for tilings by spheres, for the case of arbitrary tilings.

A new family of maximum distance separable (MDS) array codes is presented. The code arrays contain p information columns and r independent parity columns, each column consisting of p-1 bits, where p is a prime. We extend a previously known construction for the case r=2 to three and more parity columns. It is shown that when r=3 such extension is possible for any prime p. For larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain class of primes these conditions are satisfied up to r/spl les/8. One of the advantages of the new codes is that encoding and decoding may be accomplished using simple cyclic shifts and XOR operations on the columns of the code array. We develop efficient decoding procedures for the case of two- and three-column errors. This again extends the previously known results for the case of a single-column error. Another primary advantage of our codes is related to the problem of efficient information updates. We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2/sup m/), following an update in a single information bit. This average number is of importance in many storage applications which require frequent updates of information. We show that the upper bound obtained from our codes is close to the lower bound and, most importantly, does not depend on the size of the code symbols.

It is shown that multistage generalized minimum-distance (GMD) decoding of Euclidean-space codes and lattices can provide an excellent tradeoff between performance and complexity. We introduce a reliability metric for Gaussian channels that is easily computed from an inner product, and prove that a multistage GMD decoder using this metric is a bounded-distance decoder up to the true packing radius. The effective error coefficient of multistage GMD decoding is determined. Two simple modifications in the GMD decoding algorithm that drastically reduce this error coefficient are proposed. It is shown that with these modifications GMD decoding achieves the error coefficient of maximum-likelihood decoding for block codes and for generalized construction A lattices. Multistage GMD decoding of the lattices D/sub 4/, E/sub 8/, K/sub 12/, BW/sub 16/, and /spl Lambda//sub 24/ is investigated in detail. For K/sub 12/BW/sub 16/, and /spl Lambda//sub 24/, the GMD decoders have considerably lower complexity than the best known maximum-likelihood or bounded-distance decoding algorithms, and appear to be the most practically attractive decoders available. For high-dimensional codes and lattices (/spl ges/64 dimensions) maximum-likelihood decoding becomes infeasible, while GMD decoding algorithms remain quite practical. As an example, we devise a multistage GMD decoder for a 128-dimensional sphere packing with a nominal coding gain of 8.98 dB that attains an effective error coefficient of 1365760. This decoder requires only about 400 real operations, in addition to algebraic errors-and-erasures decoding of certain BCH and Hamming codes. It therefore appears to be practically feasible to implement algebraic multistage GMD decoders for high-dimensional sphere packings, and thus achieve high effective coding gains.

While the complexity of trellis decoding for a given block code is essentially a function of the number of states and branches in its trellis, the decoding complexity may be often reduced by means of an appropriate sectionalization of the trellis. Notwithstanding the many examples of such sectionalizations for particular codes that appeared in the literature, no systematic method for finding the best sectionalization of a given trellis is presently known. We present a polynomial-time algorithm which produces the optimal sectionalization of a given trellis T in time O(n/sup 2/), where n is the length of the code generated by T. The algorithm is developed in a general setting of certain operations and functions defined on the set of trellises; it therefore applies to both linear and nonlinear codes, and easily accommodates a broad range of optimality criteria. The particular optimality criterion based on minimizing the total number of additions and comparisons required for maximum-likelihood trellis decoding is investigated in detail: several different methods for decoding a given trellis are discussed and compared in a number of examples. Finally, analysis of the dynamical properties of certain optimal sectionalizations is presented.

In holographic storage, two-dimensional arrays of binary data is optically recorded in a medium via an interference process. To ensure optimum operation of a holographic recording system, it is desirable that the patterns of 1s (light) and 0s (no light) in the recorded array satisfy the following modulation constraint: in each row and column of the array there are at least t transitions of the type 1/spl rarr/0 or 0/spl rarr/1, for a prescribed integer t. A two-dimensional array with this property is said to be a conservative array of strength t. In general, an n-dimensional conservative array of strength t is a binary array having at least t transitions in each column, extending in any of the n dimensions of the array. We present an algorithm for encoding unconstrained binary data into an n-dimensional conservative array of strength t. The algorithm employs differential coding and error-correcting codes. Using n binary codes-one per dimension-with minimum Hamming distance d/spl ges/2t-3, we apply a certain transformation to an arbitrary information array which ensures that the number of transitions in each dimension is determined by the minimum distance of the corresponding code.

We prove a conjecture of McEliece, establishing that for each fixed order of positions of a linear code C, the minimal trellis minimizes the quantity |E|-|V|+1, where |E| and |V| stand for the number of edges and vertices in the trellis, respectively. As a consequence, it follows that the minimal trellis uniquely minimizes the total number of operations required for Viterbi decoding of a given code. Moreover, we show that these results extend to the general class of rectangular codes (namely, the class of codes that admit a biproper trellis presentation), which includes all group codes and many other useful nonlinear codes.

The trellis complexity s(C) of a block code C is defined as the logarithm of the maximum number of states in the minimal trellis realization of the code. The parameter s(C) governs the complexity of maximum-likelihood decoding, and is considered a fundamental descriptive characteristic of the code in a number of recent works. We derive a new lower bound on s(C) which implies that asymptotically good codes have infinite trellis complexity. More precisely, for i/spl ges/1 let C/sub i/ be a code over an alphabet of size q, of length n/sub i/, rate R/sub i/, and minimum distance d/sub i/. The infinite sequence of codes C/sub ,/ C/sub 2spl middotspl middotspl middot/ such that n/sub ispl rarrspl infin/ when i/spl rarrspl infin/ is said to be asymptotically good if both R/sub i/ and d/sub in/sub i/ are bounded away from zero as i/spl rarrspl infin/. We prove that the complexity s(C/sub i/) increases linearly with n/sub i/ in any asymptotically good sequence of codes.>

The trellis state-complexity s of a linear block code is defined as the logarithm of the maximum number of states in its minimal trellis. We present a new lower bound on the state complexity of linear codes, which includes most of the existing bounds as special cases. The new bound is obtained by dividing the time axis for the code into several sections of varying lengths, as opposed to the division into two sections-the past and the future-employed in the well-known DLP bounds. For a large number of codes this results in a considerable improvement upon the DLP bound. Moreover, we generalize the new bound to nonlinear codes, and introduce several alternative techniques for lower-bounding the trellis complexity, based on the distance spectrum and other combinatorial properties of the code. We also show how the general ideas developed in this paper may be employed to lower-bound the maximum and the total number of branches in the trellis, leading to considerably tighter bounds on these quantities. Furthermore, the asymptotic behavior of the new bounds is investigated, and shown to improve upon the previously known asymptotic estimates of trellis state-complexity.

We present a new bounded-distance decoding algorithm for the hexacode, which requires at most 34 real operations in the worst case, as compared to 57 such operations in the best previously known decoder. The new algorithm is then employed for bounded-distance decoding of the Leech lattice and the Golay code. The error-correction radius of the resulting decoders is equal to that of a maximum-likelihood decoder. The resulting decoding complexity is at most 331 real operations for the Leech lattice and at most 121 operations for the Golay code. For all the three codes-the hexacode, the Golay code, and the Leech lattice-the proposed decoders are considerably more efficient than any decoder presently known.>

Multilevel constructions of the binary Golay code and the Leech lattice are described. Both constructions are based upon the projection of the Golay code and the Leech lattice onto the (6,3,4) hexacode over GF(4). However, unlike the previously reported constructions, the new multilevel constructions make the three levels independent by way of using a different set of coset representatives for one of the quaternary coordinates. Based upon the multilevel structure of the Golay code and the Leech lattice, efficient bounded-distance decoding algorithms are devised. The bounded-distance decoder for the binary Golay code requires at most 431 operations. As compared to 651 operations for the best known maximum-likelihood decoder. Efficient bounded-distance decoding of the Leech lattice is achieved by means of partitioning it into four cosets of Q/sub 24/, beyond the conventional partition into two H/sub 24/ cosets. The complexity of the resulting decoder is only 953 real operations on the average and 1007 operations in the worst case, as compared to about 3600 operations for the best known in maximum-likelihood decoder. It is shown that the proposed algorithms decode correctly at least up to the guaranteed error-correction radius of the maximum-likelihood decoder. Thus, the loss in coding-gain is due primarily to an increase in the effective error-coefficient, which is calculated exactly for both algorithms. Furthermore, the performance of the Leech lattice decoder on the AWGN channel is evaluated experimentally by means of a comprehensive computer simulation. The results show a loss in coding-gain of less than 0.1 dB relative to the maximum-likelihood decoder for BER ranging from 10/sup -1/ to 10/sup -7/.>

Properties of nonlinear perfect binary codes are investigated and several new constructions of perfect codes are derived from these properties. An upper bound on the cardinality of the intersection of two perfect codes of length n is presented, and perfect codes whose intersection attains the upper bound are constructed for all n. As an immediate consequence of the proof of the upper bound the authors obtain a simple closed-form expression for the weight distribution of a perfect code. Furthermore, they prove that the characters of a perfect code satisfy certain constraints, and provide a sufficient condition for a binary code to be perfect. The latter result is employed to derive a generalization of the construction of Phelps (1983), which is shown to give rise to some perfect codes that are nonequivalent to the perfect codes obtained from the known constructions. Moreover, for any m/spl ges/4 the authors construct full-rank perfect binary codes of length 2/sup m/-1. These codes are obviously nonequivalent to any of the previously known perfect codes. Furthermore the latter construction exhibits the existence of full-rank perfect tilings. Finally, they construct a set of 2(2/sup cn/) nonequivalent perfect codes of length n, for sufficiently large n and a constant c=0.5-/spl epsiv/. Precise enumeration of the number of codes in this set provides a slight improvement over the results reported by Phelps.>

Proves that the (10,40,4) code found by Best (1980) is unique. The authors then employ this fact to show that A(10,3)=A(11,4)/spl les/78 and A(11,3)=A(12,4)/spl les/156.>

Let /spl Sscr/(n.k) denote the set of all words of length n over the alphabet {+1,-1}, having a k th order spectral-null at zero frequency. A subset of /spl Sscr/(n,k) is a spectral-null code of length n and order k. Upper and lower bounds on the cardinality of /spl Sscr/(n,k) are derived. In particular we prove that (k-1) log/sub 2/ (n/k)/spl les/n-log/sub 2/|/spl Sscr/(n,k)|/spl les/O(2/sup k/log/sub 2/n) for infinitely many values of n. On the other hand, we show that /spl Sscr/(n.k) is empty unless n is divisible by 2/sup m/, where m=[log/sub 2/k]+1. Furthermore, bounds on the minimum Hamming distance d of /spl Sscr/(n,k) are provided, showing that 2k/spl les/d/spl les/k(k-1)+2 for infinitely many n. We also investigate the minimum number of sign changes in a word x/spl isin//spl Sscr/(n,k) and provide an equivalent definition of /spl Sscr/(n,k) in terms of the positions of these sign changes. An efficient algorithm for encoding arbitrary information sequences into a second-order spectral-null code of redundancy 3 log/sub 2/n+O(log log n) is presented. Furthermore, we prove that the first nonzero moment of any word in /spl Sscr/(n,k) is divisible by k!. This leads to an encoding scheme for spectral-null codes of length n and any fixed order k, with rate approaching unity as n/spl rarr//spl infin/.>

We show that the Nordstrom-Robinson (1968) code may be represented as the union of binary images of two isomorphic linear (4,2,3) codes over GF(4). Certain symmetries of the unique quaternary (4,2,3) quadracode are discussed. It is shown how the properties of the Nordstrom-Robinson code itself, such as weight distribution, distance invariance, and the well-known representation as the union of eight cosets of the (16,5,8) Reed-Muller code, may be easily rederived from these symmetries. In addition we introduce a decoding algorithm for the Nordstrom-Robinson code which involves projecting its codewords onto the codewords of the quadracode. The algorithm is simple enough to enable hard-decision decoding of the Nordstrom-Robinson code by hand. Furthermore we present an algorithm for maximum-likelihood soft-decision decoding of the Nordstrom-Robinson code based on its representation over GF(4). The complexity of the proposed algorithm is at most 205 real operations. This is, to the best of our knowledge, less than the complexity of any existing decoder, and twice as efficient as the fast maximum-likelihood decoder of Adoul (1987). We also investigate several related topics, such as bounded-distance decoding, sphere-packings, and the (20,2048,6) code.>

The problem of efficient maximum-likelihood soft decision decoding of binary BCH codes is considered. It is known that those primitive BCH codes whose designed distance is one less than a power of two, contain subcodes of high dimension which consist of a direct-sum of several identical codes. The authors show that the same kind of direct-sum structure exists in all the primitive BCH codes, as well as in the BCH codes of composite block length. They also introduce a related structure termed the "concurring-sum", and then establish its existence in the primitive binary BCH codes. Both structures are employed to upper bound the number of states in the minimal trellis of BCH codes, and develop efficient algorithms for maximum-likelihood soft decision decoding of these codes.>

An algorithm for maximum likelihood decoding of the Leech lattice is presented. The algorithm involves projecting the points of the Leech lattice directly onto the codewords of the (6,3,4) quaternary code-the hexacode. Projection on the hexacode induces a partition of the Leech lattice into four cosets of a certain sublattice 24. Such a partition into cosets enables maximum likelihood decoding of the Leech lattice with 3595 real operations in the worst case and only 2955 operations on the average. This is about half the worst case and the average complexity of the best previously known algorithm.>

A Reed-Solomon decoder that makes use of bit-level soft-decision information is presented. A Reed-Solomon generator matrix that possesses a certain inherent structure in GF(2) is derived. This structure allows the code to be represented as a union of cosets, each coset being an interleaver of several binary BCH codes. Such partition into cosets provides a clue for efficient bit-level soft-decision decoding. Two decoding algorithms are derived. In the development of the first algorithm a memoryless channel is assumed, making the value of this algorithm more conceptual than practical. The second algorithm, which is obtained as a modification of the first, does account for channel memory and thus accommodates a bursty channel. Both decoding algorithms are, in many cases, orders of magnitude more efficient than conventional techniques.>

Zero-concurring codewords disclose a certain structure of the code that may be used for efficient soft-decision decoding and for designing DC-free codes. Methods for constructing sets of zero-concurring codewords are presented for several families of codes. For the general case an algorithm solution of the problem is offered. A table of results obtained using the proposed techniques is supplied for all the primitive narrow-sense binary BCH codes of length up to 127.>

An algorithm for maximum-likelihood soft-decision decoding of the binary (24,12,8) Golay code is presented. The algorithm involves projecting the codewords of the binary Golay code onto the codewords of the (6,3,4) code over GF(4)-the hexacode. The complexity of the proposed algorithm is at most 651 real operations. Along similar lines, the tetracode may be employed for decoding the ternary (12,6,6) Golay code with only 530 real operations. The proposed algorithm also implies a reduction in the number of computations required for decoding the Leech lattice.>