Mixed kernels of polar codes are mapping functions having inputs of different alphabet sizes that are used to construct polar coding scheme. These schemes are constructed by incorporating several (homogeneous) kernels, each one over different alphabet size. In this paper, the idea of mixed-kernels construction is introduced and analyzed. An asymptotic analysis of the proposed scheme shows that its polarization properties are strongly related to the ones of the constituent kernels. Simulation of finite length instances of the scheme indicate their advantages both in error correction performance and complexity compared to the known polar coding structures.

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.

An algorithm for constructing Tanner graphs of non-binary irregular quasi-cyclic LDPC codes is introduced. It employs a new method for selection of edge labels allowing control over the code's non-binary ACE spectrum and resulting in low error-floor. The efficiency of the algorithm is demonstrated by generating good codes of short to moderate length over small fields, outperforming codes generated by the known methods.

Error vector magnitude (EVM) is an important figure of merit in many communication systems. In this work an analytical approach to the calculation of EVM in clipped multi- carrier signals is proposed. In contrast to previous work, the EVM in this work is calculated with no simplifying model (e.g. a Gaussian assumption). The expression is given in a form of a power series. Based on the derived expressions for EVM, bounds on the maximal achievable rate are derived.

For the recently proposed model of symbol-pair channels, we advance the pair-error coding theory with algebraic cyclic-code constructions and asymptotic bounds on code rates. Cyclic codes for pair-errors are constructed by a careful use of duals of known tools from cyclic-code theory. Asymptotic lower bounds on code rates show that codes for pair-errors provably exist for rates strictly higher than codes for the Hamming metric.

Along with PAPR and PMEPR, the error vector magnitude (EVM) measure for sequences is of importance for applications in OFDM communication systems with clipping. No analytical method for calculation of EVM is currently known. It is shown that EVM can be computed as a power series in the length of the sequence with coefficients depending on the alphabet and clipping level.

A generalization of the polar coding scheme is proposed. It exploits several homogeneous kernels over alphabets of different sizes. An analysis of the introduced scheme is undertaken. Specifically, asymptotic properties of the polarization are shown to be strongly related to the ones of the constituent kernels.

Code decompositions (a.k.a code nestings) are used to design good binary polar code kernels. The proposed kernels are in general non-linear and show a better rate of polarization under successive cancelation decoding, than the ones suggested by Korada et al., for the same kernel dimensions. In particular, we construct kernels of sizes 14, 15 and 16 providing polarization rates better than any binary kernel of such sizes.

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549–595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $\textsc{rej}(\epsilon)$ were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781–1795]. They used Fourier analysis to show that $\textsc{rej}(\epsilon)\geq\epsilon$ for every $0\leq\epsilon\leq1/2$. They also conjectured that this bound might not be tight for $\epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $\textsc{rej}(\epsilon)\geq\epsilon$ by an additive constant that depends only on $\epsilon$: $\textsc{rej}(\epsilon)\geq\epsilon+\min\{1376\epsilon^{3}(1-2\epsilon)^{12},\frac{1}{4}\epsilon(1-2\epsilon)^{4}\}$, for every $0\leq\epsilon\leq1/2$. Our analysis is based on a relationship between $\textsc{rej}(\epsilon)$ and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

For a binary sequenceSn= {si:i=1,2,...,n} ∈ {±1}n,n> 1, the peak sidelobe level (PSL) is defined as M(Sn)=maxk=1,2,...,n-1|∑i=1n-kSiSi+k|. It is shown that the distribution ofM(Sn) is strongly concentrated, and asymptotically almost surely γ(Sn) = (M(Sn))/√(n In n) ∈ [1-o(1),√2]. Explicit bounds for the number of sequences outside this range are provided. This improves on the best earlier known result due to Moon and Moser that the typical γ(Sn) ∈ [o([1/(√(ln n))]),2], and settles to the affirmative the conjecture of Dmitriev and Jedwab on the growth rate of the typical peak sidelobe. Finally, it is shown that modulo some natural conjecture, the typical γ(Sn) equals√2.

Using lower bounds on components of the distance spectrum of a code on the Euclidean sphere obtained by linear programming, we derive new, better than known, upper bounds on the size of multiple packings.

High error floors in optimized irregular LDPC codes limit their usage in applications that require low error rates. We introduce new methods for lowering the error floor of LDPC codes, based on enhancing the code's parity-check matrix with additional linearly dependent and independent parity-checks. We prove NP hardness of certain optimization problems related to proposed methods and provide upper bound on the number of parity-checks that need to be added. We show that the proposed methods can lower the error floor of the code significantly, by several orders of magnitude, at negligible or no rate penalty.

Schedule is the order of passing messages between vertices of the bipartite graph defining an LDPC code during decoding. Schedules may significantly differ in the rate of decoding convergence. New efficient generalized serial schedules are described and analyzed. They provide significant convergence rate speedup factors compared to previously known schedules. For the proposed schedules, combinatorial and probabilistic analysis is presented, explaining the fast convergence observed in simulations. Using it, LDPC ensembles for which significantly better convergence rates can be obtained are identified.

Schedule is the order of passing messages between vertices of the bipartite graph defining an LDPC code in the process of decoding. Schedules affect the rate of decoding convergence. New efficient generalized serial schedules are described and analyzed, exhibiting significantly faster convergence compared to previously known schedules. For the proposed schedules, combinatorial and probabilistic analysis is presented, explaining the fast convergence observed in simulations. Using it, LDPC ensembles for which significantly better convergence rates can be achieved are identified. Specific code constructions from lifted graphs are further proposed, efficiently supporting the schedules. Examples based on regular LDPC codes are provided, in which the schedules achieve convergence speedup factors of up to 6 in comparison with the flooding schedule. Higher speedup factors are predicted by the analysis for irregular codes.

For a binary sequence in given equation, the peak sidelobe level (PSL) is defined as by a certain equation. It is shown that the distribution of M(Sn) is strongly concentrated, and asymptotically almost surely, as per a derived equation. Explicit bounds for the number of sequences outside this range are provided. This improves on the best earlier known bounds due to Moon and Moser [1968] claiming that the typical value in equation 3 and settles to the affirmative a conjecture of Dmitriev and Jedwab [2007] on the growth rate of the typical peak sidelobe.

Efficient serial decoding schedules for LDPC codes are described. The schedules are based on dividing the Tanner graph to sub-graphs. This yields an improvement in complexity and performance over the standard schedules. An application of the introduced schedules to decoding codes based on lifted graphs is described. An analysis based on density evolution is presented and is used to predict the behavior of different schedules.

Nonlinearity is the number of bits which must change in the truth table of a Boolean function to reach the closest affine function. It may be expressed through the maximum of the absolute value of a component in the function's Walsh–Hadamard transform. Concentration of nonlinearity is proved. The derived bounds on the concentration point and tails of the distribution are tighter than the earlier known ones.

A novel approach to constructing Tanner graphs using progressive edge growth (PEG) is introduced. It yields LDPC codes providing minimized block error probability in Binary Erasure Channels (BEC). The constructed codes exhibit superior performance over codes generated by previously known algorithms, both for BEC and AWGN channels. Furthermore, an upper bound on the expected block error probability in the error floor region of the generated codes is derived. This allows analytical prediction of the codes' error floor performance. Finally, the method is generalized for generating simple in implementation LDPC codes based on lifted graphs.

Upper bounds are derived for codes in Stiefel and Grassmann manifolds with given minimum chordal distance. They stem from upper bounds for codes in the product of unit spheres and projective spaces. The new bounds are asymptotically better than the previously known ones.

A new lower bound on the distance distribution of spherical codes is derived. This yields two new upper bounds on the reliability function of the Gaussian channel. These bounds outperform previously known bounds, and imply a new range of rates for which the exact value of the reliability function is known.

Upper bounds are derived for codes in the Grassmann manifold with given minimum chordal distance. They stem from upper bounds for codes in the product of unit spheres and projective spaces. The new bounds are asymptotically better than the previously known ones.

A relation is established between the strength of a binary code over the alphabet {+1,-1}, and its ability to reduce peak-to-mean envelope power ratio (PMEPR) in n-subcarrier (OFDM) signals. Based on this relation, a method is proposed to deterministically bound PMEPR of such signals using coordinate-wise multiplication by a balancing vector (BV) chosen from a code of given strength. A practical probabilistic scheme considering a small number of candidate codewords is devised. For this scheme, estimates on the PMEPR reduction achievable with arbitrary high probability are derived. In particular, the scheme provides for large n PMEPR of lnn+2.01lnlnn with (ln2)middot(log2n)2+1 bits of redundancy, the failure probability at most e-n, and testing n/(lnlnn) candidate BVs. Finally, several practical settings are considered. For example, for quaternary phase-shift keying, n=128, the scheme with 36 bits of redundancy (18 redundant subcarriers), by testing only 4 BVs provides over 2 dB PMEPR reduction, for any failure rate below 10-2.5

The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved.

New bounds on the rate of non-binary codes and non-binary constant weight codes are derived. The asymptotic forms of these bounds outperform known bounds in a wide range of distances. The method is based on analysis of subsets in products of Hamming and Johnson association schemes

A new lower bound on the distance distribution of spherical codes is derived. This yields two new upper bounds on the reliability function of the Gaussian channel. These bounds outperform previously known bounds, and imply a new range of rates for which the exact value of the reliability function is known

The complexity of brute force encoding of LDPC codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

This paper describes a novel progressive edge growth (PEG) algorithm for constructing LDPC codes with minimized block error probability over the binary erasure channel (BEC). The constructed codes provide superior performance and lower error floor compared to codes generated by previously known algorithms. Furthermore, an upper bound on the expected block error probability in the error floor region of the generated code is derived

Use of extrinsic information transfer (EXIT) functions, characterizing the amplification of mutual information between the input and output of the maximum a posteriori (MAP) decoder, significantly facilitates analysis of iterative coding schemes. Previously, EXIT functions derived for binary erasure channels (BECs) were used as an approximation for other channels. Here, we improve on this approach by introducing more accurate methods to construct EXIT functions for binary-input memoryless symmetric (BMS) channels. By defining an alternative pseudo-MAP decoder coinciding with the MAP decoder over BEC, we provide an expression for the EXIT functions of block codes over BEC. Furthermore, we draw a connection between the EXIT function over BEC and the EXIT function over the BMS channel under certain conditions. This is used for deriving accurate or approximate expressions of EXIT functions over BMS channels in certain scenarios

We exploit extrinsic information tranfer functions of single parity-check and prepetition codes over the binay input additive white Gaussian noise (biAWGN) channel, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that our method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods.

We exploit extrinsic information transfer functions of single parity-check and repetition codes over the binary input additive white Gaussian noise (biAWGN) channel, derived by the authors, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that this method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.

Asymptotic nonexistence bounds for unequal error protecting codes with two protection levels are considered. We show that the improved estimates on the possible distance distributions for codes may sometimes yield sharper upper bounds than the previously known ones on the higher significance protection level of both nonlinear and linear codes having two protection levels.

In this paper generalized bounds on the crest-factor (CF) distribution in orthogonal frequency-division multiplexing (OFDM) transmission for both independent and dependent subcarriers are derived. Here, the latter situation represents the coded case. For independent subcarriers, a general path for bounding practical constellations is provided. Moreover, a complete characterization of their asymptotic behavior is devised and discussed. The results are shown to carry over to the spherical constellations improving on recent results. For dependent subcarriers, the focus is mainly on binary codes where bounds on the CF distribution are obtained in terms of the distance distributions and their duals. The asymptotic behavior of codes is analyzed and it is shown that the upper bound on the effective crest-factor of a large class of Bose-Chaudhuri-Hocquenghem (BCH) codes behaves asymptotically as radiclogN. Finally, two applications of the results to code design are presented: first, fixed phase shifts on the subcarriers for all codewords are used and an algorithm to calculate the phase shifts is designed. That way, it is proved that the effective CF of any binary code can be scaled to be of order radiclogN for large N without sacrificing on rate. Furthermore, the same approach is applied to calculation of the phases of redundant subcarriers for each codeword. It is shown by simulations that the values can be effectively chosen so that the CF is significantly reduced with nonexponential complexity

A code is said to be locally testable if an algorithm can distinguish between a codeword and a vector being essentially far from the code using a number of queries that is independent of the code's length. The question of characterizing codes that are locally testable is highly complex. In this work we provide a sufficient condition for linear codes to be locally testable. Our condition is based on the weight distribution (spectrum) of the code and of its dual. Codes of (large) length n and minimum distance n/2 - /spl Theta/(/spl radic/n) have size which is at most polynomial in n. We call such codes almost-orthogonal. We use our condition to show that almost-orthogonal codes are locally testable, and, moreover, their dual codes can be spanned by words of constant weights (weight of a codeword refers to the number of its non-zero coordinates). Dual-BCH(n, t) codes are generalizations of the well studied Hadamard codes (t = 1 is Hadamard). Alon et al. (2003) raised the question whether Dual-BCH(n, t) codes are locally testable for constant t. As these codes are known to be almost-orthogonal, we solve this question. We further show that BCH(n, t) code is spanned by its almost shortest words, that is by codewords of weight at most 2t + 2, while the minimum weight is 2t + 1. Our results can be straightforwardly extended to Goppa codes and trace subcodes of algebraic-geometric codes.

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. These bounds are based on combinatorial arguments and linear programming. They improve on the previous bounds due to Burshtein et al. It is proved that at least for high rate LDPC codes have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound

Asymptotic nonexistence bounds for unequal error protecting codes with two protection levels are considered. We show that the improved estimates, reported by Litsyn on the possible distance distributions for codes, may sometimes yield sharper upper bounds than the previously known ones, for both nonlinear and linear codes having two protection levels

Upper bounds on the maximum number of codewords in a binary code of a given length and minimum Hamming distance are considered. New bounds are derived by a combination of linear programming and counting arguments. Some of these bounds improve on the best known analytic bounds. Several new record bounds are obtained for codes with small lengths

An identifying code C is a subset of the vertices of the square grid ${\mathbb Z}^2$ with the property that for each element v of ${\mathbb Z}^2$, the collection of elements from C at a distance of at most one from v is nonempty and distinct from the collection of any other vertex. We prove that the minimum density of C within ${\mathbb Z}^2$ is $\frac{7}{20}$.

A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits. We show that the Reed-Muller codes of constant order are locally testable. Specifically, we describe an efficient randomized algorithm to test if a given vector of length n=2/sup m/ is a word in the rth-order Reed-Muller code R(r,m) of length n=2/sup m/. For a given integer r/spl ges/1, and real /spl epsi/>0, the algorithm queries the input vector /spl upsi/ at O(1//spl epsi/+r2/sup 2r/) positions. On the one hand, if /spl upsi/ is at distance at least /spl epsi/n from the closest codeword, then the algorithm discovers it with probability at least 2/3. On the other hand, if /spl upsi/ is a codeword, then it always passes the test. Our result is almost tight: any algorithm for testing R(r,m) must perform /spl Omega/(1//spl epsi/+2/sup r/) queries.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

We define an ensemble of lattices, and show that for asymptotically high dimension most of its members are simultaneously good as sphere packings, sphere coverings, additive white Gaussian noise (AWGN) channel codes and mean-squared error (MSE) quantization codes. These lattices are generated by applying Construction A to a random linear code over a prime field of growing size, i.e., by "lifting" the code to /spl Ropf//sup n/.

The ratio between the discrete and continuous maxima of signals used in multicarrier communications is analyzed. An exact expression, up to an additive term, is obtained for the considered ratio when the number of uniformly distributed samples is equal to the number of carriers. A more accurate upper estimate on the continuous maximum from discrete samples of the signal and its derivative is suggested. Finally, a tight upper bound is given for the value of the continuous maximum via discrete values of samples when the number of samples is greater than the number of carriers.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

This paper address the problem of classification of BPSK-modulated multicarrier signals with the peak-to-average power ratio (PAPR) exceeding 3/4 of the maximal possible value. By providing a simple characterization of such signals, an upper bound on their number are derived and propose a simple sufficient condition for the signals to have low PAPR. Based on this, a simple method for generation of signals with guaranteed PAPR gain of more than 2.5 dB using only two redundant tones are described.

In this paper bounds on the crest-factor (CF) distribution of OFDM signals are generalized as firstly, independent subcarriers a complete characterization of arbitrary complex constellations is derived; secondly, for dependent subcarriers bounds are derived in terms of the weight distribution and their duals of the underlying code. Implications on code design are also discussed. Generalizations to linear, binary codes are given in terms of the weight distribution

Use of extrinsic information transfer (EXIT) functions characterizing mutual information between the input and output of constituent decoders significantly facilitates performance analysis of iterative decoding schemes. Previously EXIT functions derived for binary erasure channel (BEC) were used as an approximation for other binary memoryless symmetric (BMS) Channels. Here we improve on this approach by introducing a more accurate method to compute EXIT functions of some block codes for BMS channels. A general expression is derived for the extrinsic mutual information at the output of MAP decoder. Using this expression we are able to compute EXIT functions for single parity-check codes over all BMS channels. Application of this result to analysis of convergence thresholds of LDPC codes is described. Using an alternative decoder coinciding with MAP decoder over BEC, we derive an expression for EXIT function over BEC, and based on it approximation to the EXIT function over AWGN channel for some block codes.

We address the problem of classification of binary phase-shift keying-modulated multicarrier signals with the peak-to-average power ratio (PAPR) exceeding 3/4 of the maximal possible value. By providing a simple characterization of such signals, we derive an upper bound on their number, and propose a simple sufficient condition for the signals to have low PAPR. Based on this, we describe a simple method for generation of signals with guaranteed PAPR gain of more than 2.5 dB using only two redundant tones.

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.

We present new MAP decoding algorithms for first order Reed-Muller and Hamming codes. The proposed algorithms have complexities proportional to n/spl times/log/sub 2/(n), where n is the code length.

Using random coding techniques, we show that, in high dimensions, there exist lattices which are simultaneously good as sphere packings, sphere coverings, AWGN channel and MSE quantization codes. These lattices are produced by a construction, similar to construction A (Conway, J.H. and Sloane, N.J.A., 1988), and a randomly chosen set of generating vectors.

The paper presents a new approach to the calculation of the crest-factor (CF) distribution in coded OFDM systems. The approach reveals an interesting connection between the weight distribution and the CF distribution of linear, binary codes that can be exploited to give an upper bound. The weight distribution of codes has attracted a great deal of attention in the past and many expressions and bounds are known. Thus we can expect to obtain a large number of bounds on the CF distribution. The upper bounds can serve as approximate curves for the CF distribution in the low probability region.

We derive asymptotic expressions for the average distance distributions in ensembles of irregular low-density parity-check (LDPC) codes. The ensembles are defined by matrices with given profiles of column and row sums.

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.

We derive expressions for the average distance distributions in several ensembles of regular low-density parity-check codes (LDPC). Among these ensembles are the standard one defined by matrices having given column and row sums, ensembles defined by matrices with given column sums or given row sums, and an ensemble defined by bipartite graphs.

Let A(n,d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as good as the Johnson bound for all values of n and d, and for each d there are infinitely many values of n for which the new bound is better than the Johnson bound. For small values of n and d, the best known method to obtain upper bounds on A(n,d) is linear programming. We give new inequalities for the linear programming and show that with these new inequalities some of the known bounds on A(n,d) for n/spl les/28 are improved.

We consider the problem of bounding the distance distribution for unrestricted block codes with known distance and/or dual distance. Applying the polynomial method, we provide a general framework for previously known results. We derive several upper and lower bounds both for finite length and for sequences of codes of growing length. Asymptotic results in the paper improve previously known estimates. In particular, we prove the best known bounds on the binomiality range of the distance spectrum of codes with a known dual distance.

We use a generalized Gray isometry in order to construct a previously unknown nonlinear (96,2/sup 36/,24) code as the image of a Z/sub 8/-linear Hensel lift of the binary Golay code. The union of this code with a relevant coset yields a (96,2/sup 37/,24) code. We show that this code and some of its shortenings are better than the best (non)linear binary codes known so far. For instance, the best earlier known code of length 96 and minimum distance 24 had 2/sup 88/ words.

This paper is devoted to the problem of error detection with quantum codes. We show that it is possible to give a consistent definition of the undetected error event. To prove this, we examine possible problem settings for quantum error detection. Our goal is to derive a functional that describes the probability of undetected error under natural physical assumptions concerning transmission with error detection with quantum codes. We discuss possible transmission protocols with stabilizer and unrestricted quantum codes. The set of results proved in the paper shows that in all the cases considered the average probability of undetected error for a given code is essentially given by one and the same function of its weight enumerators. We examine polynomial invariants of quantum codes and show that coefficients of Rains's (see ibid., vol44, p.1388-94, 1998) "unitary weight enumerators" are known for classical codes under the name of binomial moments of the distance distribution. As in the classical situation, these enumerators provide an alternative expression for the probability of undetected error.

In Part I of this paper we formulated the problem of error detection with quantum codes on the completely depolarized channel and gave an expression for the probability of undetected error via the weight enumerators of the code.In this part we show that there exist quantum codes whose probability of undetected error falls exponentially with the length of the code and derive bounds on this exponent.The lower (existence) bound is proved for stabilizer codes by the counting argument for classical self-orthogonal quaternary codes.Upper bounds are proved by linear programming.First we formulate two linear programming problems that are convenient for the analysis of specific short codes.Next we give a relaxed formulation of the problem in terms of optimization on the cone of polynomials in the Krawtchouk basis.We present two general solutions of the problem.Together they give an upper bound on the exponent of undetected error.The upper and lower asymptotic bounds coincide for a certain interval of code rates close to 1.

We derive a new upper bound on the exponent of error probability of decoding for the best possible codes in the Gaussian channel. This bound is tighter than the known upper bounds (the sphere-packing and minimum-distance bounds proved in Shannon's classical 1959 paper and their low-rate improvement by Kabatiansky and Levenshtein (1978)). The proof is accomplished by studying asymptotic properties of codes on the sphere S/sup n-1/(R). First we prove a general lower bound on the distance distribution of codes of large size. To derive specific estimates of the distance distribution, we study the asymptotic behavior of Jacobi polynomials P/sub k//sup ak, bk/ as k/spl rarr//spl infin/. Since on the average there are many code vectors in the vicinity of the transmitted vector x, one can show that the probability of confusing x and one of these vectors cannot be too small. This proves a lower bound on the error probability of decoding and the upper bound announced in the title.

We derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives lim/sub n/spl rarr//spl infin// sup d/n/spl les/(5-5/sup 3/4/)/10<0.165630, thus improving on the Mallows-Odlyzko-Sloane bound of 1/6 and our recent bound of 0.166315.

In this paper we estimate covering radius when dual distance is known. We derive new bounds on covering radii of linear codes. A bound for self-complementary codes is also presented. The improvements of these bounds on the known results are based on the knowledge of the cardinality of constant weight codes and on the behavior of Hahn polynomials and discrete Chebyshev polynomials.

We derive new asymptotic upper bounds on the generalized weights of a binary linear code of a given size. We also prove some asymptotic results on the distance distribution of binary codes.

The covering radius of a code tells us how far in the sense of Hamming distance an arbitrary word of the ambient space can be from the code. For a few decades this parameter has been widely studied. We estimate the covering ratios of a code when the dual distance is known. We derive a new bound on covering radii of linear codes. It improves essentially on the previously known estimates in a certain wide range. We also study asymptotic bounds on the cardinality of constant weight codes.

This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams (1972, 1977) identities, we generalize the linear programming approach from classical coding theory to the quantum case. Using this approach, we obtain Singleton-type, Hamming-type, and the first linear-programming-type bounds for quantum codes. Using the special structure of linear quantum codes, we derive an upper bound that is better than both Hamming and the first linear programming bounds on some subinterval of rates.

We improve estimates on the parameters of quantum codes obtained by Steane's (see ibid., vol.45, no.7, p.2492-5, 1999) construction from binary codes. This yields several new families of quantum codes.

The spectral-null code S(n, k) of kth order and length n is the union of n-tuples with /spl plusmn/1 components, having kth-order spectral-null at zero frequency. We determine the exact asymptotic in n behavior of the size of such codes. In particular, we prove that for n satisfying some divisibility conditions, log/sub 2/|S(n, k)|=n-k/sup 2//2log/sub 2/n+c/sub k/+o(1), where c/sub k/ is a constant depending only on k and o(1) tends to zero when n grows. This is an improvement on the earlier known bounds due to Roth, Siegel, and Vardy (see ibid., vol40, p.1826-40, 1994).

We derive a new estimate for the error term in the binomial approximation to the distance distribution of BCH codes. This is an improvement on the earlier bounds by Kasami-Fujiwara-Lin (1985), Vladuts-Skorobogatov (1991), and Krasikov-Litsyn (1995).

We derive upper bounds on the components of the distance distribution of duals of BCH codes. Roughly speaking, these bounds show that the distance distribution can be upper-bounded by the corresponding normal distribution. To derive the bounds we use the linear programming approach along with some estimates on the magnitude of Krawtchouk polynomials of fixed degree in a vicinity of q/2.

We derive new upper bounds on the error exponents for the maximum-likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the best earlier known bounds by Shannon-Gallager-Berlekamp (1967) and McEliece-Omura (1977). For the probability of undetected error the new bounds are better than the bounds by Levenshtein (1978, 1989) and the bound by Abdel-Ghaffar (see ibid., vol.43, p.1489-502, 1997). Moreover, we further extend the range of rates where the undetected error exponent is known to be exact. The new bounds are based on an analysis of possible distance distributions of the codes along with some inequalities relating the distance distributions to the error probabilities.

We derive several new lower bounds on the size of binary codes with covering radius one. In particular, we prove K

We introduce a family of binary array codes of size t/spl times/n, correcting multiple phased burst erasures of size t. The codes achieve maximal correcting capability, i.e., being considered as codes over GF(2/sup t/) they are MDS. The length of the codes is n=/spl Sigma//sub l=1//sup L/(/sub l//sup t/) where L is a constant or is slowly growing in t. The complexity of encoding and decoding is proportional to rnmL where r is the number of correctable erasures, and m is the smallest number such that 2/sup t/=1 modulo m. This compares favorably with the complexity of decoding codes obtained from the shortened Reed-Solomon codes having the same parameters.

We study geometrically the domain of linear binary codes and of unrestricted binary codes in the plane (normalized covering radius, normalized minimal distance).

A family of binary array codes of size (p-1)/spl times/n, with p a prime, correcting multiple column erasures is proposed. The codes coincide with a subclass of shortened Reed-Solomon codes and achieve the maximum possible correcting capability. Complexity of encoding and decoding is proportional to rnp, where r is the number of correctable erasures, i.e., is simpler than the Forney decoding algorithm. The length n of the codes is at most 2p-1, that is, twice as big as the length of the Blaum-Roth codes having comparable decoding complexity.

We derive new estimates for the range of binomiality in a code's spectra, where the distance distribution of a code is upperbounded by the corresponding normalized binomial distribution. The estimates depend on the code's dual distance.

Using a variant of the linear programming method we derive a new upper bound on the minimum distance d of doubly-even self-dual codes of length n. Asymptotically, for n growing, it gives d/n/spl les/0.166315/spl middot//spl middot//spl middot/+o(1), thus improving on the Mallows-Odlyzko-Sloane bound of 1/6. To establish this, we prove that in any doubly even-self-dual code the distance distribution is asymptotically upper-bounded by the corresponding normalized binomial distribution in a certain interval.

We discuss parameters of Goppa (1970) codes, such as minimum distance, covering radius, distance distribution, and generalized Hamming weights. By a variation on the exponential sums method and combinatorial arguments, we sharpen known bounds on these parameters.

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.

Given a subset X of vertices of the n-cube (i.e., the n-dimensional Hamming space), we are interested in the solution of the traveling salesman problem; namely, the minimal length of a cycle passing through all vertices of X. For a given number M, we estimate the maximum of these lengths when X ranges over all possible choices of sets of M vertices. Asymptotically, our estimates show that for a number M of vertices growing exponentially in n, the maximum is attained for a code with maximal possible minimum distance.

We study a wide class of problems in coding theory for which we consider two different formulations: in terms of incidence matrices and in terms of hypergraphs. These problems are dealt with using a greedy algorithm due to Stein (1974) and Lovasz (1975). Some examples, including constructing covering codes, codes for conflict resolution, separating systems, source encoding with distortion, etc., are given a unified treatment. Under certain conditions derandomization can be performed, leading to an essential reduction in the complexity of the constructions.

New lower bounds on the minimum length of t-error-correcting BCH codes with covering radius at most 2t are derived.

A binary code $C \subseteq \mathbb{F}_2^n$ with M codewords is called an $( n,M,r,u )$ multiple covering of the farthest-off points (MCF) if the Hamming spheres of radius r centered at the codewords cover the whole space $\mathbb{F}_2^n $ and every $x \in \mathbb{F}_2^n $ such that $d( x,C ) = r$ is covered by at least $\mu $ codewords. The minimum possible cardinality $F( n,r,\mu )$ of such a code is studied and tables of upper bounds on $F ( n,r,\mu )$ for $n \leq 16,r \leq 4,\mu \leq 4$ are given.

Introduces a generalization of the concepts of coverings and packings in Hamming space called weighted coverings and packings. This allows to formulate a number of well-known coding theoretical problems in a uniform manner. The authors study the existence of perfect weighted codes, discuss connections between weighted coverings and packings, and present many constructions for them.

Derives an estimate for the error term in the binomial approximation of spectra of BCH codes. This estimate asymptotically improves on the bounds by Sidelnikov (1971), Kasami et al. (1985), and Sole (1990).>

The binomial distribution is a well-known approximation to the distance spectra of many classes of codes. We derive a lower estimate for the deviation from the binomial approximation.>

We derive new asymptotic bounds for generalized distances. Our approach extends the classical Hamming, Plotkin, and Elias bounds. The latter bound involves extending the definition of generalized distances to nonlinear codes.>

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

A new approach for encoding any string of information bits into a sequence having bounded running digital sum is presented. The results improve previously known values of the running digital sum for the same rate. Also discussed are ways of incorporating an error-correcting capability into these codes. Some general constructions are given and tables are constructed for specific cases.>

The authors consider the construction of balanced error-correcting codes with distance close to half of the block length and bounded running digital sum. Use of these codes in cascade constructions allows derivation of a number of classes of DC-constrained codes of various lengths. The mathematical framework underlying the code construction is the theory of (incomplete) exponential sums. Essentially, the authors consider a class of codes formed by values of Legendre symbols of polynomials of bounded degree on the set of residues modulo a prime. In particular, taking linear polynomials, they obtain the Hadamard codes. Applying well-known estimates of the exponential sums, they compute the code parameters and prove that the proposed codes are in fact DC constrained.>

The authors investigate the problem of evaluating the possible size of error-correcting codes with code words taken from a subset of Hamming spaces. This is an example of the problem of constructing codes in irregular subsets of Hamming spaces. The authors examine the theoretical restrictions on the parameters of error-correcting codes in the asymptotic case (semi-finite sequence) when the recursive digital sum is upper-bounded by some small constant. The bounds allow demonstration of the existence of long codes that have good error-correcting properties and that satisfy some restrictions that are natural for optical and magnetic recording.>

Let Q be an alphabet of size q>or=2. The Hamming space Q/sup n/ that consists of all n-tuples of elements of Q is a metric space, provided with the Hamming distance function. A perfect multiple covering (PMC) is a code C in Q/sup n/ such that there exist fixed numbers r and mu with the property that every word in Q/sup n/ is within distance r from exactly mu codewords of C. The authors give a few constructions of PMCs and investigate in detail the problem of determining all possible parameters of PMCs with r=1.>

A new lower bound for the parameters of (nonlinear)q-ary codes is introduced. For some q this bound improves on the Varshamov-Gilbert bound, the "modular" algebraic-geometric bound, and the very recent Vl\breve{a}duts bound.