We study a class of graph based codes with Reed-Solomon component codes as affine variety codes. We give a formulation of the exact dimension of graph codes in general. We give an algebraic description of these codes which makes the exact computation of the dimension of the graph codes easier.

Several modifications of product codes have been suggested as standards for optical networks. We show that the performance exhibits a threshold that can be estimated from a result about random graphs. For moderate input bit error probabilities, the output error rates for codes of finite length can be found by easy simulations. The analysis indicates that the performance curve can be extrapolated until the error floor is reached. The analysis allows us to calculate the error floors and avoid time-consuming simulations.

In Pickard random fields (PRF), the probabilities of finite configurations and the entropy of the field can be calculated explicitly, but only very simple structures can be incorporated into such a field. Given two Markov chains describing a boundary, an algorithm is presented which determines whether a PRF consistent with the distribution on the boundary and a 2-D constraint exists. Iterative scaling is used as part of the algorithm, which also determines the conditional probabilities yielding the maximum entropy for the given boundary description if a solution exists. A PRF is defined for the domino tiling constraint represented by a quaternary alphabet. PRF models are also presented for higher order constraints, including the no isolated bits (n.i.b.) constraint, and a minimum distance 3 constraint by defining super symbols on blocks of binary symbols.

By introducing a few simplifying assumptions we derive a simple condition for successful decoding using the Koetter-Vardy algorithm for soft-decision decoding of Reed-Solomon codes. We show that the algorithm has a significant advantage over hard decision decoding when the code rate is low, when two or more sets of received symbols have substantially different reliabilities, or when the number of alternative transmitted symbols is very small.

We present an iterative list decoding algorithm for low-density parity-check (LDPC) codes. In particular we apply this decoder to a class of LDPC codes from finite geometries and show that the (73,45,10) projective geometry code can be maximum-likelihood (ML) decoded with low complexity. Moreover, the list decoding approach enables us to give a theoretical analysis of the performance. We also consider list bit-flipping (BF) decoding of longer LDPC codes.

We treat a specific case of codes based on bipartite expander graphs coming from finite geometries. The code symbols are associated with the branches and the symbols connected to a given node are restricted to be codewords in a Reed-Solomon code. We give results on the parameters of the codes and methods for their encoding

We determine the number of minimum weight codewords in a class of Euclidean geometry codes and link the performance of bit-flipping decoding to the geometry of the error patterns.

By introducing a few simplifying assumptions we derive a simple condition for successful decoding using the Koetter-Vardy algorithm for soft-decision decoding of RS codes. We show that the algorithm has a significant advantage over hard decision decoding when the code rate is low, when two or more sets of received symbols have substantially different reliabilities, or when the number of alternative transmitted symbols is very small

We analyze the relation between iterative decoding and the properties of the extended parity check matrix. By considering a modified version of bit flipping, which produces a list of decoded words, we derive several relations between decodable error patterns and parameters of the code. By developing a tree of codewords at minimal distance form the received vector, we also obtain new information about the code.

A simple construction of two-dimensional (2-D) fields is presented. Rows and columns are outcomes of the same Markov chain. The entropy can be calculated explicitly

This paper considers a class of discrete finite alphabet 2D fields that can be characterized using tools front finite state machines and Markov chains. These fields have several properties that greatly simplify the analysis of 2D coding methods.

Recently Bleichenbacher et al. proposed a decoding algorithm for interleaved (N, K) Reed-Solomon codes, which allows close to N-K errors to be corrected in many cases. We discuss the application of this decoding algorithm to concatenated codes

We consider codes based on simple bipartite expander graphs. These codes may be seen as the first step leading from product type concatenated codes to more complex graph codes. We emphasize constructions of specific codes of realistic lengths, and study the details of decoding by message passing in trees.

We derive upper bounds on the weights of error patterns that can be corrected by a convolutional code with given parameters, or equivalently we give bounds on the code rate for a given set of error patterns. The bounds parallel the Hamming bound for block codes by relating the number of error patterns to the number of distinct syndromes.

We present some improvements in the procedure for calculating power spectra of signals based on finite state descriptions and constant block size. In addition to simplified calculations, our results provide some insight into the form of the closed expressions and to the relation between the spectra and other properties of the codes.

We derive lower bounds on the distance and error exponent of the coding scheme described in the title. The bounds are compared to the parameters and error performance of a concatenated code family with varying inner codes of equal rates and a fixed minimum-distance separable (MDS) code as the outer code, letting the inner and outer code lengths approach infinity.

We derive upper bounds on the number of errors that can be corrected by list decoding of maximum-distance separable (MDS) codes using small lists. We show that the performance of Reed-Solomon (RS) codes, for certain parameter values, is limited by worst case codeword configurations, but that with randomly chosen codes over large alphabets, more errors can be corrected.

Bounds on the capacity of constrained two-dimensional (2-D) codes are presented. The bounds of Calkin and Wilf (see SIAM J. Discr. Math., vol.11, no.1, p.54-60, 1998) apply to first-order symmetric constraints. The bounds are generalized in a weaker form to higher order and nonsymmetric constraints. Results are given for constraints specified by run-length limits or a minimum distance between pixels of a given value.

The maximum entropy and thereby the capacity of two-dimensional (2-D) fields given by certain constraints on configurations is considered. Upper and lower bounds are derived. A new class of 2-D processes yielding good lower bounds is introduced. Asymptotically, the process achieves capacity for constraints with limited long-range effects. The processes are general and may also be applied to, e.g., data compression of digital images. Results are given for the binary hard square model, which is a 2-D run-length-limited model and some other 2-D models with simple constraints.

If the calculation of the critical length is based on the expurgated exponent, the length becomes nonzero for low error probabilities. This result applies to typical long codes, but it may also be useful for modeling error events in specific codes.

We present a decoding algorithm for algebraic-geometric codes from regular plane curves, in particular the Hermitian curve, which corrects all error patterns of weight less than d*/2 with low complexity. The algorithm is based on the majority scheme of Feng and Rao (1993) and uses a modified version of Sakata's (1988) generalization of the Berlekamp-Massey algorithm.

An algorithm that, for codes from a regular plane curve, corrects up to (d*/2)-(m/sup 2//8)+(m/4)-(9/8) errors, where d* is the designed distance and m is the degree of the curve, was presented in an earlier work (see ibid., vol.35, p.811-21, 1989). It is now shown that this bound is the best possible for the algorithm considered.>

We discuss minimum distance decoding of convolutional codes. The relevant distance functions are defined, and the set of correctable error patterns is described by a sequence of weight constraints. Decoding methods for error patterns of bounded weight are described, and it is demonstrated that these methods offer a favorable combination of performance and complexity. Exact values and upper bounds on the error probability are calculated from finite state models of the decoding process.>

Improvement to an earlier decoding algorithm for codes from algebraic geometry is presented. For codes from an arbitrary regular plane curve the authors correct up to d*/2-m/sup 2//8+m/4-9/8 errors, where d* is the designed distance of the code and m is the degree of the curve. The complexity of finding the error locator is O(n/sup 7/3/), where n is the length of the code. For codes from Hermitian curves the complexity of finding the error values, given the error locator, is O(n/sup 2/), and the same complexity can be obtained in the general case if only d*/2-m/sup 2//2 errors are corrected.>

Unit memory convolutional codes with generator matrices, which are composed of circulant submatrices, are introduced. This structure facilitates the analysis of efficient search for good codes. Equivalences among such codes and some of the basic structural properties are discussed. In particular, catastrophic encoders and minimal encoders are characterized and dual codes treated. Further, various distance measures are discussed, and a number of good codes, some of which result from efficient computer search and some of which result from known block codes, are presented.>

A class of codes derived from algebraic plane curves is constructed. The concepts and results from algebraic geometry that were used are explained in detail; no further knowledge of algebraic geometry is needed. Parameters, generator and parity-check matrices are given. The main result is a decoding algorithm which turns out to be a generalization of the Peterson algorithm for decoding BCH decoder codes.>

Series representations of the form f(t) approximately Sigma /sub n=- infinity //sup infinity / Sigma /sub k=- infinity //sup infinity /a/sub n,k/ nu (t-n)/sub e//sup 2 pi /kts/ for bounded signals f(t) are studied, as are conditions on the unit function nu (t), such that coefficients a/sub n,k/ reveal the energy content of f(t) in the time interval n-(1/2)>

The minimum distance of concatenated codes with Reed-Solomon outer codes and convolutional inner codes is studied. For suitable combinations of parameters the minimum distance can be lower-bounded by the product of the minimum distances of the inner and outer codes. For a randomized ensemble of concatenated codes a lower bound of the Gilbert-Varshamov type is proved.>

A class of infinite\pm 1sequences is presented whose autocorrelation function is zero for all nonzero shifts.

A class of binary sequences of lengthN = 2^{m}is considered, and it is shown that their aperiodic autocorrelations can be calculated recursively in a simple way. Based on this, the merit factor of the sequences is calculated and it is shown that the asymptotic value is3. Finally, it is proved that the magnitude of the maximal aperiodic autocorrelation is bounded byN^{0.9}.

The Markov chain that has maximum entropy for given first and second moments is determined. The solution provides a discrete analog to the continuous Gauss-Markov process.

We construct0, \pm 1sequences of length(q^{2l+1}-l)/(q-1), whereq=2^{s}, with out-of-phase periodic autocorrelation0, and in-phase correlationq^{2l};SUch that the peak factor of radiation is(q^{2l+1}-1) /(q^{2+l}-q^{2l}), which is close to1asqbecomes large.

Binary unit memory codes, originally introduced by Lee, are investigated. A few examples of constant unit memory codes are given and bounds on the distance profile and the free distances are discussed. For time-varying codes asymptotic lower bounds on the distance profile and the free distance are given. The error probability for the codes, used on a memoryless binary-input, output-symmetric channel, is asymptotically upper bounded. The asymptotic results for the free distance and the error probability, which are in some respects better than for conventional convolutional codes, are interpreted by Forney's inverse concatenation construction.

The encoding of independent data symbols as a sequence of discrete amplitude, real variables with given power spectrum is considered. The maximum rate of such an encoding is determined by the achievable entropy of the discrete sequence with the given constraints. An upper bound to this entropy is expressed in terms of the rate distortion function for a memoryless finite alphabet source and mean-square error distortion measure. A class of simple dc-free power spectra is considered in detail, and a method for constructing Markov sources with such spectra is derived. It is found that these sequences have greater entropies than most codes with similar spectra that have been suggested earlier, and that they often come close to the upper bound. When the constraint on the power spectrum is replaced by a constraint On the variance of the sum of the encoded symbols, a stronger upper bound to the rate of dc-free codes is obtained. Finally, the optimality of the binary biphase code and of the ternary bipolar code is decided.

Certainq-ary Reed-Solomon codes can be decoded by an algorithm requiring onlyO(q \log^{2} q)additions and multiplications inGF(q).

If the constraint length of a convolutional code is defined suitably, it is an obvious upper bound on the free distance of the code, and it is sometimes possible to find codes that meet this bound. It is proved here that the length of a rate1/\nu q-ary code with this property is at mostq\nu, and we construct a class of such codes with lengths greater thanq\nu/3.

We show that when an inner linear cyclic binary code which has an irreducible check polynomial is concatenated with an appropriately chosen maximal-distance-separable outer code, then the overall code is cyclic OverGF(2). Using this theorem, we construct a number of linear cyclic binary codes which are better than any previously known. In particular, by taking the inner code to be a quadratic residue code, we obtain linear cyclic binary codes of lengthN, rateR, and distanceD \geq (1 - 2R)N/ \sqrt{2 \log N}, which compares favorably with the BCH distanceD \sim (2 \ln R^{-1})N/\log N, although it still fails to achieve the linear growth of distance with block length which is possible with noncyclic linear concatenated codes. While this construction yields many codes, including several with block lengths greater than10^{10^5}, we have not been able to prove that there are arbitrarily long codes of this type without invoking the Riemann hypothesis or the revised Artin conjecture, as the existence of long codes of our type is equivalent to the existence of large primespfor which the index of 2 is(p - 1)/2.

We define maximum-distance-separable convolutional codes as systematic codes with (feedback) minimum distance exceeding the number of check digits in a constraint length. The maximum length of such codes is determined for certain small fields when the rate is\frac{1}{2}.

We show that the generator polynomials of certain cyclic codes define noncatastrophic fixed convolutional codes whose free distances are lowerbounded by the minimum distances of the cyclic codes. This result is used to construct convolutioual codes with free distance equal to the constraint length and to derive convolutional codes with good free distances from the BCH codes. Finally, a class of time-varying codes is constructed for which the free distance increases linearly with the constraint length.

For any nonzero elementcof a general finite fieldGF(q), it is shown that the polynomials(x - c)^i, i = 0,1,2,\cdots, have the "weight-retaining" property that any linear combination of these polynomials with coefficients inGF(q)has Hamming weight at least as great as that of the minimum degree polynomial included. This fundamental property is then used as the key to a variety of code constructions including 1) a simplified derivation of the binary Reed-Muller codes and, for any primepgreater than 2, a new extensive class ofp-ary "Reed-Muller codes," 2) a new class of "repeated-root" cyclic codes that are subcodes of the binary Reed-Muller codes and can be very simply instrumented, 3) a new class of constacyclic codes that are subcodes of thep-ary "Reed-Muller codes," 4) two new classes of binary convolutional codes with large "free distance" derived from known binary cyclic codes, 5) two new classes of long constraint length binary convolutional codes derived from2^r-ary Reed-Solomon codes, and 6) a new class ofq-ary "repeated-root" constacyclic codes with an algebraic decoding algorithm.

For any rateR, 0 < R < 1, a sequence of specific(n,k)binary codes with rateR_n > Rand minimum distancedis constructed such that \begin{equation} \lim_{n \rightarrow \infty} \inf \frac{d}{n} \geq (1 - r ^{-1} R)H^{-1} (1 - r)> 0 \end{equation} (and hence the codes are asymptotically good), whereris the maximum of\frac{1}{2}and the solution of \begin{equation} R = \frac{r^2}{1 + \log_2 [1 - H^{-1}(1 - r)]}. \end{equation} The codes are extensions of the Reed-Solomon codes overGF(2^m)With a simple algebraic description of the added digits. Alternatively, the codes are the concatenation of a Reed-Solomon outer code of lengthN = 2^m - 1withNdistinct inner codes, namely all the codes in Wozeneraft's ensemble of randomly shifted codes. A decoding procedure is given that corrects all errors guaranteed correctable by the asymptotic lower bound ond. This procedure can be carried out by a simple decoder which performs approximatelyn^2 \log ncomputations.