Search

The extrinsic information transfer (EXIT) functions of Hadamard codes in the context of repeat-zigzag-Hadamard (RZH) codes with parallel decoding are investigated. EXIT functions over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise (BIAWGN) channel are derived. The application of these EXIT functions in the design of low-rate capacity-approaching irregular RZH (IRZH) codes is also considered. Using the EXIT functions, the bit error rate (BER) for a given code profile can be easily estimated and the differential evolution (DE) technique can be employed to find the optimal degree profile for given design parameters. The EXIT functions derived in this communication can serve as an effective tool for designing low-rate IRZH codes with parallel decoding in both BEC and BIAWGN channels. Index Terms--Extrinsic information transfer (EXIT) functions, Hadamard codes, irregular code design, low-rate codes.

In this paper, we study moments of soft bits of binary-input symmetric-output channels and solve some extremal problems of the moments. We use these results to solve the extremal information combining problem. Further, we extend the information combining problem by adding a constraint on the second moment of soft bits, and find the extremal distributions for this new problem. The results for this extension problem are used to improve the prediction of convergence of the belief propagation decoding of low-density parity-check (LDPC) codes, provided that another extremal problem related to the variable nodes is solved. Index Terms--Extrinsic information transfer (EXIT) functions, information combining, low-density parity-check (LDPC) codes.

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R = (1 - [epsilon]) C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and l/[epsilon], then the decoding time complexity of the presented family is linear in N and polynomial in 1/[epsilon]. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes" IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel," IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/[epsilon]. Index Terms--Concatenated codes, decoding complexity, decoding error probability, error exponent, expander codes, irregular repeat accumulative (IRA) codes, iterative decoding, linear-time decoding, low-density parity-check (LDPC) codes.

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. Index Terms--Covering radius, distance distributions in codes, error probability threshold, undetected error probability.

Extrinsic information transfer (EXIT) charts are a tool for predicting the convergence behavior of iterative processors for a variety of communication problems. A model is introduced that applies to decoding problems, including the iterative decoding of parallel concatenated (turbo) codes, serially concatenated codes, low-density parity-check (LDPC) codes, and repent-accumulate (RA) codes. EXIT functions are defined using the model, and several properties of such functions are proved for erasure channels. One property expresses the area under an EXIT function in terms of a conditional entropy. A useful consequence of this result is that the design of capacity-approaching codes reduces to a curve-fitting problem for all the aforementioned codes. A second property relates the EXIT function of a code to its Helleseth-Klove--Levenshtein information functions, and thereby to the support weights of its subcodes. The relation is via a refinement of information functions called split information functions, and via a refinement of support weights called split support weights. Split information functions are used to prove a third property that relates the EXIT function of a linear code to the EXIT function of its dual. Index Terms--Concatenated codes, duality, error-correction coding, iterative decoding, mutual information.

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. Index Terms--Hamming codes, maximum a posteriori (MAP) decoding, Reed-Muller 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. In this paper we estimate the covering radius 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. Index Terms - Constant weight codes, covering radius, dual distance, Krawtchouk polynomial.

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. Index Terms - Constant-weight codes, distance distribution, generalized weights, linear programming.

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. Index Terms--Binomial spectrum, constant weight codes, distance distribution, Krawtchouk polynomials, polynomial method.

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). 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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as K [direction] [infinity]. Since on the average there are many code vectors in the vicinity of the transmitted vector [Chi] one can show that the probability of confusing [Chi] 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. Index Terms--Distance distribution, error probability of decoding, Jacobi polynomials, spherical codes.

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. In the final section of the paper we examine polynomial invariants of quantum codes and show that coefficients of Rains's "unitary weight enumerators" [17] 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 a companion paper (part II) we use the relation of the probability of undetected error and weight enumerators to derive bounds on this probability for quantum codes. Index Terms--Measurement, quantum code, Shor-Laflamme enumerators, undetected error.

In Part I of this paper we formulated the problem of error detection with quantum codes on the depolarizing 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 a 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. Index Terms--Polynomial method, probability of undetected error, quantum code, self-orthogonal codes.

We define and show how to construct nonbinary quantum stabilizer codes. Our approach is based on nonbinary error bases. It generalizes the relationship between self-orthogonal codes over [F.sub.4] and binary quantum codes to one between self-orthogonal codes over [F.sub.q]2 and q-ary quantum codes for any prime power q. Index Terms--Nonbinary quantum codes, quantum stabilizer codes, self-orthogonal codes.

This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams 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. Index Terms - Linear programming, quantum codes, upper bounds.

The extrinsic information transfer (EXIT) functions of Hadamard codes in the context of repeat-zigzag-Hadamard (RZH) codes with parallel decoding are investigated. EXIT functions over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise (BIAWGN) channel are derived. The application of these EXIT functions in the design of low-rate capacity-approaching irregular RZH (IRZH) codes is also considered. Using the EXIT functions, the bit error rate (BER) for a given code profile can be easily estimated and the differential evolution (DE) technique can be employed to find the optimal degree profile for given design parameters. The EXIT functions derived in this communication can serve as an effective tool for designing low-rate IRZH codes with parallel decoding in both BEC and BIAWGN channels. [ABSTRACT FROM AUTHOR]