MDS convolutional codes

Maximum distance separable (MDS) convolutional codes are defined as the row space overF(D)of totally nonsingular polynomial matrices in the indeterminateD. These codes may be used to transmit information onnparallel channels when a temporary or even an infinite break can occur in some of these channels. Their algebraic properties are emphasized, and the relevant parameters are introduced. On this basis two decoding procedures are described. Both procedures correct arbitrarily long error sequences that may occur at the same time in some of thenchannels. Some specific constructions of MDS convolutional codes are presented.     

Finite field construction for quasi-cyclic LDPC convolutional codes with cyclic 2-D MDS codes

The parity-check matrices for quasi-cyclic low-density parity-check convolutional (QC-LDPC-C) codes have different characteristics of time-varying periodicity and need to realize fast encoding. The finite field construction method for QC-LDPC-C codes with cyclic two-dimensional maximum distance separable (2-D MDS) codes is proposed using the base matrix framework and matrix unwrapping, thus the constructed parity-check matrices are free of length-4 cycles. The unwrapped matrices are constructed respectively based on different cyclic 2-D MDS codes for the case of matrix period less than or greater than constraint block length, and construction examples are given. LDPC-C codes with different periodicity characteristics are compared with QC-LDPC-C codes constructed with the proposed method. Experimental results show that QC-LDPC-C codes with the proposed method outperform the other codes and have lower encoding and decoding complexity.

     

On lowest density MDS codes

Let F_q denote the finite field GF(q) and let h be a positive integer. MDS (maximum distance separable) codes over the symbol alphabet F_q^b are considered that are linear over F _q and have sparse (“low-density”) parity-check and generator matrices over F_q that are systematic over F_q^b. Lower bounds are presented on the number of nonzero elements in any systematic parity-check or generator matrix of an F_q-linear MDS code over F_q^b, along with upper bounds on the length of any MDS code that attains those lower bounds. A construction is presented that achieves those bounds for certain redundancy values. The building block of the construction is a set of sparse nonsingular matrices over F_q whose pairwise differences are also nonsingular. Bounds and constructions are presented also for the case where the systematic condition on the parity-check and generator matrices is relaxed to be over F_q, rather than over F_q^b     

Efficient encoding of QC-LDPC codes related to cyclic MDS codes

In this paper, we present an efficient systematic encoding algorithm for quasi-cyclic (QC) low-density paritycheck (LDPC) codes that are related to cyclic maximum-distance separable (MDS) codes. The algorithm offers linear time complexity, and it can be easily implemented by using polynomial multiplication and division circuits. We show that the division polynomials can be completely characterized by their zeros and that the sum of the respective numbers of their zeros is equal to the parity-length of the codes.     

On MDS codes via Cauchy matrices

A special form of Cauchy matrix is used to obtain a tighter bound for the validity region of the maximum distance separable (MDS) conjecture and a new compact characterization of generalized Reed-Solomon codes. The latter is further used to obtain constructions and some existence results for long [2k, k] double-circulant MDS codes     

Lowest density MDS codes over extension alphabets

Let F be a finite field and b be a positive integer. A construction is presented of codes over the alphabet F/sup b/ with the following three properties: i) the codes are maximum-distance separable (MDS) over F/sup b/, ii) they are linear over F, and iii) they have systematic generator and parity-check matrices over F with the smallest possible number of nonzero entries. Furthermore, for the case F=GF(2), the construction is the longest possible among all codes that satisfy properties i)-iii).     

On MDS extensions of generalized Reed- Solomon codes

An(n, k, d)linear code overF=GF(q)is said to be {em maximum distance separable} (MDS) ifd = n - k + 1. It is shown that an(n, k, n - k + 1)generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} qis even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withkin the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1, and that generalized Reed-Solomon codes of lengthq + 1and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} qis even) do not have MDS extensions. Hence, in cases where the(q + 1, k)MDS code is essentially unique,(n, k)MDS codes withn > q + 1do not exist.     

A multicast hybrid ARQ scheme using MDS codes and GMD decoding

An efficient multicast hybrid ARQ scheme is proposed by incorporating the generalized minimum distance (GRID) decoding of maximum distance separable (MDS) codes with Metzner's (1984) scheme. Erroneous frames are stored in the receiver buffer and recovered after receiving one or more redundant frames. The throughput and the average transmission delay of the proposed scheme are analyzed on memoryless symmetric channels. The proposed scheme can circumvent the degradation of the throughput due to an increase of the number of receivers, which is the most serious defect in the conventional multicast ARQ schemes, at the expense of the transmission delay     

A systematic construction of self-dual codes

A new coding construction scheme of block codes using short base codes and permutations that enables the construction of binary self-dual codes is presented in Cadic et al. (2001) and Carlach et al. (1999, 2000). The scheme leads to doubly-even (resp,. singly-even) self-dual codes provided the base code is a doubly-even self-dual code and the number of permutations is even (resp., odd). We study the particular case where the base code is the [8, 4, 4] extended Hamming. In this special case, we construct a new [88, 44, 16] extremal doubly-even self-dual code and we give a new unified construction of the five [32, 16, 8] extremal doubly-even self-dual codes.     

A new construction of frequency-hopping codes

This article presents a new construction of frequency-hopping (FH) codes for multilevel frequency-shift-keying/frequency-hopping code-division multiple-access (MFSK/ FH-CDMA) systems. Exactly P³ -P FH patterns of length P³ and frequency slots P³ are constructed for every prime, P. These new FH patterns possess ideal autocorrelation and good cross-correlation properties. Furthermore, these new FH patterns can be partitioned into P(P+1) groups, of which the auto- and cross-correlation properties between any two FH patterns in the same group are both ideal     

X-code: MDS array codes with optimal encoding

We present a new class of MDS (maximum distance separable) array codes of size n×n (n a prime number) called X-code. The X-codes are of minimum column distance 3, namely, they can correct either one column error or two column erasures. The key novelty in X-code is that it has a simple geometrical construction which achieves encoding/update optimal complexity, i.e., a change of any single information bit affects exactly two parity bits. The key idea in our constructions is that all parity symbols are placed in rows rather than columns     

On the main conjecture on geometric MDS codes

A new way to attack the main conjecture on MDS codes for geometric codes is proposed. In particular, the conjecture for codes arising from curves of genus one or two when the cardinal of the ground field is large enough is proven     

Systematic MDS erasure codes based on Vandermonde matrices

An increasing number of applications in computer communications uses erasure codes to cope with packet losses. Systematic maximum-distance separable (MDS) codes are often the best adapted codes. This letter introduces new systematic MDS erasure codes constructed from two Vandermonde matrices. These codes have lower coding and decoding complexities than the others systematic MDS erasure codes.     

On generator matrices of MDS codes (Corresp.)

It is shown that the family ofq-ary generalized Reed-Solomon codes is identical to the family ofq-ary linear codes generated by matrices of the form[I|A], whereIis the identity matrix, andAis a generalized Cauchy matrix. Using Cauchy matrices, a construction is shown of maximal triangular arrays over GF(q), which are constant along diagonals in a Hankel matrix fashion, and with the property that every square subarray is a nonsingular matrix. By taking rectangular subarrays of the described triangles, it is possible to construct generator matrices[I|A]of maximum distance separable codes, whereAis a Hankel matrix. The parameters of the codes are(n,k,d), for1 leq n leq q+ 1, 1 leq k leq n, andd=n-k+1.     

A construction technique for random-error-correcting convolutional codes

A simple algorithm is presented for finding rate1/nrandom-error-correcting convolutional codes. Good codes considerably longer than any now known are obtained. A discussion of a new distance measure for convolutional codes, called the free distance, is included. Free distance is particularly useful when considering decoding schemes, such as sequential decoding, which are not restricted to a fixed constraint length. It is shown how the above algorithm can be modified slightly to produce codes with known free distance. A comparison of probability of error with sequential decoding is made among the best known constructive codes of constraint length36.     

Error-correcting capabilities of concatenated codes with MDS outer codes on memoryless channels with maximum- likelihood decoding

Error-correcting capabilities of concatenated codes with maximum distance separable (MDS) outer codes and time-varying inner codes, used on memoryless discrete channels with maximum-likelihood decoding, are investigated. It is proved that, asymptotically, the Gallager random coding theorem can be obtained for all rates by such codes. Further, the expurgated coding theorem, as well, is proved to be valid for all rates on regular channels. The latter result implies that the Gilbert-Varshamov bound for block codes over any finite field can be obtained asymptotically for all rates by linear concatenated codes.     

A geometric construction procedure for geometrically uniformtrellis codes

The problem of maximizing the minimum free squared Euclidean distance of a trellis code is developed from a geometric point of view. This approach provides a new way of constructing constellations for trellis coding. A decomposition of the trellis topology leads to a systematic construction of signal sets and generators for geometrically uniform trellis codes. An algorithm is proposed to construct geometrically uniform trellis codes, and examples show how to obtain large free distance trellis codes. This approach unifies the construction of convolutional codes over the binary field and trellis codes over the real field     

A note on type II convolutional codes

The result of a search for the world's second type II (doubly-even and self-dual) convolutional code is reported. A rate R=4/8, 16-state, time-invariant, convolutional code with free distance d_free=8 was found to be type II. The initial part of its weight spectrum is better than that of the Golay convolutional code (GCC). Generator matrices and path weight enumerators for some other type II convolutional codes are given. By the “wrap-around” technique tail-biting versions of (32, 18, 8) Type II block codes are constructed     

A lattice-based systematic recursive construction of quasi-cyclic LDPC codes

This paper presents a low-complexity recursive and systematic method to construct good well-structured low-density parity-check (LDPC) codes. The method is based on a recursive application of a partial Kronecker product operation on a given gamma x q, q ges 3 a prime, integer lattice L(gamma x q). The (n - 1)- fold product of L(gamma x q) by itself, denoted Lⁿ(gamma x q), represents a regular quasi-cyclic (QC) LDPC code, denoted (see PDF), of high rate and girth 6. The minimum distance of (see PDF) is equal to that of the core code (see PDF) introduced by L(gamma x q). The support of the minimum weight codewords in (see PDF) are characterized by the support of the same type of codewords in (see PDF). From performance perspective the constructed codes compete with the pseudorandom LDPC codes.