We consider codes for channels with extreme noise that emerge in various low-power applications. Simple LDPC codes with parity checks of weight 3 are first studied for any code dimension m → ∞. These codes form modulation schemes: they improve the original channel outputs for any SNR > -6 dB (per information bit) and gain 3 dB over uncoded modulation as SNR grows. However, they also have a floor on the output bit error rate (BER) irrespective of their length. Tight lower and upper bounds, which are virtually identical to simulation results, are then obtained for BER at any SNR. We also study a combined scheme that splits$m$information bits into$b$blocks and protects each with some polar code. Decoding moves back and forth between polar and LDPC codes, every time using a polar code of a higher rate. For m → ∞and a sufficiently large parameter b, this design yields a vanishing BER at any SNR above the Shannon limit of -1.59 dB and has complexity order of m log m per information bit.

We combine polar and LDPC codes to address data correction for various low-power applications. We first use long low-rate LDPC codes that have parity checks of a low weight. Decoding performs several iterations of the belief propagation (BP) algorithm that recalculates the information bits only. Partially corrected bits are then passed to a short polar code that uses successive cancellation list (SCL) decoder. The newly corrected bits then serve as the new inputs for an LDPC decoder. For codes of rate less than 0.1, the algorithm performs on par with a CA-SCL decoder, while substantially reducing its latency.

We design polar codes of blocklength n→∞ and code rate R →1 that achieve the vanishing output error rates on the binary symmetric channels with transition error probability p → 0. These codes have a substantially smaller redundancy order (1 - R)n than do other known high-rate codes, such as Reed-Muller (RM) or BCH codes. The construction is explicit and has complexity of order nlog n. We also design asymptotically optimal low-rate codes that achieve the vanishing output error rates if p → 1/2.

Consider a binary Reed-Muller code RM(r, m) defined on the m-dimensional hypercube F2m. In this paper, we study punctured Reed-Muller codes Pr(m, b), whose positions are restricted to the m-tuples of a given Hamming weight b. In combinatorial terms, this paper concerns m-variate Boolean polynomials of any degree r, which are evaluated on a Hamming sphere of some radius b in F2m. Codes Pr(m, b) inherit some recursive properties of RM codes. In particular, they can be built from the shorter codes, by decomposing a spherical b-layer into sub-layers of smaller dimensions. However, these sub-layers have different sizes and do not form the classical Plotkin construction. We analyze recursive properties of the spherically punctured codes Pr(m, b) and find their distances for the arbitrary values of parameters r, m, and b. Finally, we describe recursive (successive cancellation) decoding of these codes.

The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer LDPC codes.

The problem of finding code distance has been long studied for the generic ensembles of linear codes and led to several algorithms that substantially reduce exponential complexity of this task. However, no asymptotic complexity bounds are known for distance verification in other ensembles of linear codes. Our goal is to re-design the existing generic algorithms of distance verification and derive their complexity for LDPC codes. We obtain new complexity bounds with provable performance expressed in terms of the erasure-correcting thresholds of long LDPC codes. These bounds exponentially reduce complexity estimates known for linear codes.

We survey the existing techniques for calculating code distances of classical codes and apply these techniques to generic quantum codes. For classical and quantum LDPC codes, we also present a new linked-cluster technique. It reduces complexity exponent of all existing deterministic techniques designed for codes with small relative distances (which include all known families of quantum LDPC codes), and also surpasses the probabilistic technique for sufficiently high code rates.

Consider a binary Reed-Muller code RM(r, m) defined on the m-dimensional hypercube Fm2. In this paper, we study punctured Reed-Muller codes Pr(m, b) whose positions form a spherical b-layer and include all m-tuples of a given Hamming weight b. These punctured codes inherit some recursive properties of the original RM codes and can be built from the shorter codes, by decomposing a spherical b-layer into sub-layers of smaller dimensions. However, codes Pr(m, b) cannot be formed by the recursive Plotkin construction. We analyze recursive properties of these codes and find their code distances for arbitrary values of parameters r, m, and b.

Consider a binary Reed-Muller code RM(r,m) defined on the hypercube \BB F2mand let all code positions be restricted to the m-tuples of a given Hamming weight b. In this paper, we specify this single-layer construction obtained from the biorthogonal codes RM(1,m) and the Hadamard codes H(m). Both punctured codes inherit some recursive properties of the original RM codes; however, they cannot be formed by the recursive Plotkin construction. We first observe that any code vector in these codes has Hamming weight defined by the weight w of its information block. More specifically, this weight depends on the absolute values of the Krawtchouk polynomials Kbm(w). We then study the properties of the Krawtchouk polynomials and show that the minimum code weight of a single-layer code RM(1,m,b) is achieved at the minimum input weight w = 1 for any . We further refine our codes by limiting the possible weights w of the input information blocks. As a result, some of the designed code sequences meet or closely approach the Griesmer bound. Finally, we consider more general punctured codes whose positions form several spherical layers.

Consider a binary Reed-Muller code RM(r, m) defined on the full set of binary m-tuples and let this code be punctured to the spherical layer S(b) that includes only m-tuples of a given Hamming weight b. More generally, we can consider punctured RM codes RM(r, m, B) restricted to some set B of several spherical layers S(b), b ϵ B. In this paper we specify this construction for the biorthogonal codes RM(1, m) and the Hadamard codes H(m). It is shown that the overall weight of any code vector in a punctured code H(m, B) is determined by the weight w of its information block. More specifically, this weight depends only on the values of the Krawtchouk polynomials Kbm(w) for all b ϵ B. We further refine our codes by limiting the possible weights w of the input information blocks. As a result, we obtain sequences of codes that meet or closely approach the Griesmer bound.

Let a binary Reed-Muller code RM(s;m) of length n be used on a memoryless channel with an input alphabet ±1 and a real-valued output ℝ. Given a received vector y in ℝn; we define its generalized distance T to any codeword c as the sum Σ|yj|taken over all positions j, in which vectors y, c have opposite signs. We then consider the list ℒTof codewords located within distance T from the received vector y and estimate the size LTof this list using the generalized Johnson bound. For any RM code RM(s,m) of fixed order s, the algorithm is proposed that performs list decoding beyond the error-correcting radius with linear complexity in length n and retrieves the code list ℒTwith complexity of order nsLTfor any decoding radius T within the generalized Johnson bound.

Codeword stabilized (CWS) codes form a general class of quantum codes that includes stabilizer codes and many families of nonadditive codes with good parameters. Similar to classical nonlinear codes, a CWS code can be decoded by screening all possible errors. For an n-qubit quantum code correcting up to t errors, this brute-force approach consecutively tests different errors of weight t or less, and employs a separate n-qubit measurement in each test. To simplify decoding, we propose an algorithm that employs a single measurement to process all errors located on a given cluster of t qubits. Compared to an exhaustive error screening, this reduces the total number of measurements required for error correction about 3ttimes.

Error exponents are studied for recursive and majority decoding of general Reed-Muller (RM) codesRM(r,m) used on the additive white Gaussian noise (AWGN) channels. Both algorithms have low complexity and correct many error patterns whose weight exceeds half the code distance. Decoding consists of multiple consecutive steps, which repeatedly recalculate the input symbols and determine different information symbols using soft-decision majority voting. For any codeRM(r,m), we estimate the probabilities of the information symbols obtained in these recalculations and derive the analytical upper bounds for the block error rates of the recursive and majority decoding. In the case of a low noise, we also obtain the lower bounds and show that the upper bounds are tight. For a higher noise, these bounds closely approach our simulation results.

Error exponents are studied for the recursive and majority decoding algorithms of general Reed-Muller codes RM(r, m) used on the AWGN channels. Both algorithms have low decoding complexity and substantially outperform bounded distance decoding in their error-correcting capabilities. We obtain asymptotically tight upper bounds on the output error rate that hold for both algorithms and can be used for any RM-code.

We address the maximum attainable rate of fingerprinting codes under the marking assumption, studying lower and upper bounds on the value of the rate for various sizes of the attacker coalition. Lower bounds are obtained by considering typical coalitions, which represents a new idea in the area of fingerprinting and enables us to improve the previously known lower bounds for coalitions of size two and three. For upper bounds, the fingerprinting problem is modeled as a communications problem. It is shown that the maximum code rate is bounded above by the capacity of a certain class of channels, which are similar to the multiple-access channel (MAC). Converse coding theorems proved in the paper provide new upper bounds on fingerprinting capacity.

Let a biorthogonal Reed-Muller code RM (1,m) of length n = 2mbe used on a memoryless channel with an input alphabet plusmn1 and a real-valued output R. Given any nonzero received vector y in the Euclidean space Rnand some parameter epsiisin(0,1), our goal is to perform list decoding of the code RM (1, m) and retrieve all codewords located within the angle arccos e from y. For an arbitrarily small epsi, we design an algorithm that outputs this list of codewords with the linear complexity order of n [ln2isin] bit operations. Without loss of generality, let vector y be also scaled to the Euclidean length radic(n) of the transmitted vectors. Then an equivalent task is to retrieve all coefficients of the Hadamard transform of vector y whose absolute values exceed nisin. Thus, this decoding algorithm retrieves all ne-significant coefficients of the Hadamard transform with the linear complexity n [ln2isin] instead of the complexity n In2n of the full Hadamard transform.

We study the maximum attainable rate or capacity of fingerprinting codes under the marking assumption. It is proved that capacity for fingerprinting against coalitions of size two and three over the binary alphabet satisfies 0.25 ≤ C2,2≤ 0.322 and 0.083 ≤ C3,2≤ 0.199 respectively. For coalitions of an arbitrary fixed size, we derive a closed-form upper bound on fingerprinting capacity in the binary case. Finally, for general alphabets, we establish upper bounds on the fingerprinting capacity involving only single-letter mutual information quantities.

Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.

Recursive decoding is studied for Reed-Muller (RM) codes used on a binary symmetric channel. Decoding is performed beyond the bounded distance radius d/2 and corrects most error patterns of weight up to (dlnd)/2. In our analysis, decoding is decomposed into consecutive steps, with one information bit derived in each step. Then the error probability of each step is defined by the recursive recalculations of the Bernoulli random variables. We derive the exponential moments of the recalculated random variables. As a result, tight exponential bounds on the output error probability are obtained for the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results

Given a sphere or a ball of radius r > 1 in an Euclidean space of dimension n, we study their thinnest coverings with unit balls. Our goal is to design a covering with the lowest covering density, which is defined by an average number of unit balls needed to cover any point within a sphere. For growing n, we obtain a new upper bound on the covering density that has the order of (n ln n)/2, which is half the order established in the classic Rogers bound

A new deterministic list decoding algorithm is proposed for general Reed-Muller codes RM(s,m) of length n = 2mand distance d = 2m-epsi. Given n and d, the algorithm performs beyond the bounded distance threshold of d/2 and has a low complexity order of nmepsi-1for any decoding radius T that is less than the Johnson bound

Error exponents are studied for recursive decoding of Reed-Muller (RM) codes and their subcodes used on a binary-symmetric channel. The decoding process is first decomposed into similar steps, with one new information bit derived in each step. Multiple recursive additions and multiplications of the randomly corrupted channel outputs plusmn1 are performed using a specific order of these two operations in each step. Recalculated random outputs are compared in terms of their exponential moments. As a result, tight analytical bounds are obtained for decoding error probability of the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results. Comparison of these bounds with similar bounds for bounded distance decoding and majority decoding shows that recursive decoding can reduce the output error probability of the latter two algorithms by five or more orders of magnitude even on the short block length of 256. It is also proven that the error probability of recursive decoding can be exponentially reduced by eliminating one or a few information bits from the original RM code

Soft-decision decoding is considered for general Reed-Muller (RM) codes of length n and distance d used over a memoryless channel. A recursive decoding algorithm is designed and its decoding threshold is derived for long RM codes. The algorithm has complexity of order nlnn and corrects most error patterns of the Euclidean weight of order radicn/lnn, instead of the decoding threshold radicd/2 of the bounded distance decoding. Also, for long RM codes of fixed rate R, the new algorithm increases 4/pi times the decoding threshold of its hard-decision counterpart

Recursive list decoding is considered for Reed-Muller (RM) codes. The algorithm repeatedly relegates itself to the shorter RM codes by recalculating the posterior probabilities of their symbols. Intermediate decodings are only performed when these recalculations reach the trivial RM codes. In turn, the updated lists of most plausible codewords are used in subsequent decodings. The algorithm is further improved by using permutation techniques on code positions and by eliminating the most error-prone information bits. Simulation results show that for all RM codes of length 256 and many subcodes of length 512, these algorithms approach maximum-likelihood (ML) performance within a margin of 0.1 dB. As a result, we present tight experimental bounds on ML performance for these codes

For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2

The thinnest coverings of ellipsoids are studied in the Euclidean spaces of an arbitrary dimension n. Given any ellipsoid, we obtain a tight asymptotic bound on the minimum size of its covering by the balls of radius /spl epsi/. This bound holds for all but the most oblong ellipsoids. The results can be applied to vector quantization when different data streams are bundled together in one block.

Recursive decoding techniques are considered for Reed-Muller (RM) codes of growing length n and fixed order r. An algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight up to n(1/2-/spl epsiv/) given that /spl epsiv/ exceeds n/sup -1/2r/. This improves the asymptotic bounds known for decoding RM codes with nonexponential complexity. To evaluate decoding capability, we develop a probabilistic technique that disintegrates decoding into a sequence of recursive steps. Although dependent, subsequent outputs can be tightly evaluated under the assumption that all preceding decodings are correct. In turn, this allows us to employ second-order analysis and find the error weights for which the decoding error probability vanishes on the entire sequence of decoding steps as the code length n grows.

The thinnest coverings of ellipsoids are studied in the Euclidean spaces of an arbitrary dimension n. Given any ellipsoid, the main goal is to find its /spl epsiv/-entropy, which is the logarithm of the minimum number of the balls of radius /spl epsiv/ needed to cover this ellipsoid. A tight asymptotic bound on the /spl epsiv/-entropy is obtained for all but the most oblong ellipsoids, which have very high eccentricity. This bound depends only on the volume of the sub-ellipsoid spanned over all the axes of the original ellipsoid, whose length (diameter) exceeds 2/spl epsiv/. The results can be applied to vector quantization performed when data streams from different sources are bundled together in one block.

Let A(q,n,d) denote the maximum size of a q-ary code of length n and distance d. We study the minimum asymptotic redundancy as n grows while q and d are fixed. For any d and q/spl ges/d-1, long algebraic codes are designed that improve on the Bose-Chaudhuri-Hocquenghem (BCH) codes and have the lowest asymptotic redundancy known to date. Prior to this work, codes of fixed distance that asymptotically surpass BCH codes and the Gilbert-Varshamov bound were designed only for distances 4,5, and 6.

Reed-Muller (RM) codes (m, r) of length 2/sup m/ are considered on a binary symmetric (BS) channel with high crossover error probability 1/2 -/spl epsiv/. For an arbitrarily small /spl epsiv/>0, new recursive decoding algorithms are designed that retrieve all information bits of RM codes of fixed order r with a vanishing error probability and sublinear complexity of order O(m/sup r+1/). The algorithms utilize a vanishing fraction of the received symbols for both hard- and soft-decision decoding.

We show that the minimum distance d of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless nondeterministic polynomial time (NP) equals RP. We also show that the minimum distance is not approximable to within an additive error that is linear in the block length n of the code. Under the stronger assumption that NP is not contained in random quasi-polynomial time (RQP), we show that the minimum distance is not approximable to within the factor 2/sup log1-/spl epsi//(n), for any /spl epsi/>0. Our results hold for codes over any finite field, including binary codes. In the process, we show that it is hard to find approximately nearest codewords even if the number of errors exceeds the unique decoding radius d/2 by only an arbitrarily small fraction /spl epsi/d. We also prove the hardness of the nearest codeword problem for asymptotically good codes, provided the number of errors exceeds (2/3)d. Our results for the minimum distance problem strengthen (though using stronger assumptions) a previous result of Vardy (1997) who showed that the minimum distance cannot be computed exactly in deterministic polynomial time (P), unless P = NP. Our results are obtained by adapting proofs of analogous results for integer lattices due to Ajtai (1998) and Micciancio (see SIAM J. Computing, vol.30, no.6, p.2008-2035, 2001). A critical component in the adaptation is our use of linear codes that perform better than random (linear) codes.

Let a q-ary linear (n,k)-code be used over a memoryless channel. We design a soft-decision decoding algorithm that tries to locate a few most probable error patterns on a shorter length s /spl isin/ [k,n]. First, we take s cyclically consecutive positions starting from any initial point. Then we cut the subinterval of length s into two parts and examine T most plausible error patterns on either part. To obtain codewords of a punctured (s,k)-code, we try to match the syndromes of both parts. Finally, the designed codewords of an (s,k)-code are re-encoded to find the most probable codeword on the full length n. For any long linear code, the decoding error probability of this algorithm can be made arbitrarily close to the probability of its maximum-likelihood (ML) decoding given sufficiently large T. By optimizing s, we prove that this near-ML decoding can be achieved by using only T/spl ap/q/sup (n-k)k/(n+k)/ error patterns. For most long linear codes, this optimization also gives about T re-encoded codewords. As a result, we obtain the lowest complexity order of q/sup (n-k)k/(n+k)/ known to date for near-ML decoding. For codes of rate 1/2, the new bound grows as a cubic root of the general trellis complexity q/sup min{n-k,k}/. For short blocks of length 63, the algorithm reduces the complexity of the trellis design by a few decimal orders.

We study an interrelation between the coverings generated by linear (n,k)-codes and complexity of their maximum-likelihood (ML) decoding. First , discrete ellipsoids in the Hamming spaces E/sub 1//sup n/ are introduced. These ellipsoids represent the sets of most probable error patterns that need to be tested in soft-decision ML decoding. We show that long linear (n,k)-codes surrounded by ellipsoids of exponential size 2/sup n-k/ can cover the whole space E/sub 2//sup n/. Then it is proven that ML decoding of most long (n,k)-codes needs only about 2/sup n-k/ most probable error patterns to be tested on any quantized memoryless channel. Finally, ML decoding complexity is bounded from above by 2/sup k(n-k)/n/. This substantially reduces the general trellis complexity 2/sup min{n-k,k}/.

We present a new soft-decision majority decoding algorithm for Reed-Muller codes RM(r,m). First, the reliabilities of 2/sup m/ transmitted symbols are recalculated into the reliabilities of 2/sup m-r/ parity checks that represent each information bit. In turn, information bits are obtained by the weighted majority that gives more weight to more reliable parity checks. It is proven that for long low-rate codes RM(r,m), our soft-decision algorithm outperforms its conventional hard-decision counterpart by 10 log/sub 10/(/spl pi//2)/spl ap/2 dB at any given output error probability. For fixed code rate R and m/spl rarr//spl infin/, our algorithm increases almost 2/sup r/2/ times the correcting capability of soft-decision bounded distance decoding.

We show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random quasi-polynomial time), we show that the minimum distance is not approximable to within the factor 2/sup log(1-/spl epsiv/)n/, for any /spl epsiv/>0, where n denotes the block length of the code. Our results hold for codes over every finite field, including the special case of binary codes. In the process we show that the nearest codeword problem is hard to solve even under the promise that the number of errors is (a constant factor) smaller than the distance of the code. This is a particularly meaningful version of the nearest codeword problem. Our results strengthen (though using stronger assumptions) a previous result of A. Vardy (1997) who showed that the minimum distance is NP-hard to compute exactly. Our results are obtained by adapting proofs of analogous results for integer lattices due to M. Ajtai (1998) and D. Micciancio (1998). A critical component in the adaptation is our use of linear codes that perform better than random (linear) codes.

Let a q-ary linear (n, k) code C be used over a memoryless channel. We design a decoding algorithm /spl Psi//sub N/ that splits the received block into two halves in n different ways. First, about /spl radic/N error patterns are found on either half. Then the left- and right-hand lists are sorted out and matched to form codewords. Finally, the most probable codeword is chosen among at most n/spl radic/N codewords obtained in all n trials. The algorithm can be applied to any linear code C and has complexity order of n/sup 3//spl radic/N. For any N/spl ges/q/sup n-k/, the decoding error probability P/sub N/ exceeds at most 1+q/sup n-k//N times the probability P/sub /spl Psi//(C) of maximum-likelihood decoding. For code rates R/spl ges/1/2, the complexity order q/sup n-k/2/ grows as square root of general trellis complexity q/sup min{n-k,k}/. When used on quantized additive white Gaussian noise (AWGN) channels, the algorithm /spl Psi//sub N/ can provide maximum-likelihood decoding for most binary linear codes even when N has an exponential order of q/sup n-k/.

General symmetric channels are introduced, and near-maximum-likelihood decoding in these channels is studied. First, we define a class of suboptimal decoding algorithms based on an incomplete search through the code trellis. It is proved that the decoding error probability of suboptimal decoding is bounded above for any q-ary code of length n and code rate r by twice the error probability of its maximum-likelihood decoding and tends to the latter as n grows. Second, we design a suboptimal trellis-like algorithm, which reduces the known decoding complexity of the order of q/sup n min (r,1-r)/ operations to that of q/sup nr(i-r)/ operations for all cyclic codes and virtually all long linear codes. We also consider the corresponding bounds for concatenated codes. An important corollary is that this suboptimal decoding can provide complexity below the lower bounds on trellis complexity at a negligible expense in terms of decoding error probability.

Linear q-ary codes of growing length n/spl rarr//spl infin/ and designed distance /spl delta/ are studied. At first, we examine cyclic codes defined by the sets of code zeros {g/sup i/|i=q/sup s/+1, q/sup s+1/+1, /spl middot//spl middot//spl middot/, q/sup s+/spl delta/-2/+1} over a primitive element g of GF(q/sup m/). Then special cubic varieties are designed and employed in order to attain distances /spl delta/=5, 6. The resulting double-error-correcting codes of length n=q/sup m/ have r/spl les/2m+[m/3]+1 parity check symbols, and reduce the best known redundancy by [2m/3] symbols. A decoding procedure of complexity O(rn) operations is also considered.

Two deterministic algorithms of computing the weight spectra of binary cyclic codes are presented. These algorithms have the lowest known complexity for cyclic codes. For BCH codes of lengths 63 and 127, several first coefficients of the weight spectrum in number sufficient to evaluate the bounded distance decoding error probability are computed.>