A unified approach to search for and optimize codes determined by their sparse parity-check matrices is presented. Replacing the nonzero elements of a binary parity-check matrix (the base or parent matrix) either by circulants or by companion matrices of elements from a finite field GF(2m), we obtain quasi-cyclic low-density parity-check (LDPC) block codes and binary images of nonbinary LDPC block codes, respectively. By substituting monomials of a formal variable D, we obtain the polynomial description of an LDPC convolutional code. A set of performance measures applicable to different classes of LDPC codes is considered, and a greedy algorithm for code performance optimization is presented. The heart of the new optimization algorithm is a fast procedure for searching for LDPC codes with large girth of their Tanner graphs. For a few classes of LDPC codes, examples of codes combining good error-correcting performance with compact representation are obtained. In particular, we present optimized convolutional LDPC codes and conclude that the LDPC block codes are still superior to their convolutional counterparts if both decoding complexity and coding delay are considered. Moreover, a specific channel model can easily be embedded into the optimization loop. Thereby, the code can be optimized for a specific channel. The efficiency of such an optimization is demonstrated via an example of faster than Nyquist (FTN) signaling using LDPC codes. The FTN strategy combined with a rate R = 1/2 LDPC code of length 64800 optimized for effective data rate R = 3/4 gains more than 0.5 dB compared with the standard LDPC codes of the same rate and length. The obtained gain corresponds to transmission at the capacity of the binary input additive white Gaussian noise channel. In most numerical examples, we consider codes with bidiagonal structure of the parity-check matrix. This restriction preserves low encoding complexity and allows fair comparison with codes selected for communication standards.

Outstanding asymptotical performance demonstrated by low-density parity-check (LDPC) convolutional codes (CC) makes them strong competitors with respect to quasi-cyclic (QC) LDPC block codes (BC) currently used in a variety of communication standards. However, typically communication standards, for example, DVB-S2 or WIMax standards impose rather serious restrictions on the structure of the employed codes. These restrictions are related to different implementation issues such as existence of low-complexity encoding and decoding, short decoding delay etc. Two scenarios are considered. In one scenario, short-delay and low-complexity constraints are taken into account. In the other scenario, the complexity requirement is relaxed. Both LDPC CCs and QC LDPC BCs with optimized degree distribution and girth profile, which enable low-complexity encoding, are constructed for these scenarios. Having both delay and complexity constraints yields QC LDPC BCs that outperform the LDPC CCs. In this scenario LDPC CCs play an important role mostly for constructing tailbiting QC LDPC BCs. On the other hand, assuming only a decoding delay constraint the LDPC CCs can be superior compared to the QC LDPC BCs at the relatively low signal-to-noise ratio region. Moreover, under practically acceptable decoding delays also the LDPC CCs with low-complexity encoding structure beat records in approaching the Shannon limit. A new LDPC CC is presented achieving the BER 10-7with decoding delay 96000 bits at 0.62 dB, that is, performing only about 0.43 dB from the Shannon limit.

Techniques for searching for good quasi-cyclic (QC) LDPC block codes of short and moderate lengths which are suitable for practical purposes are studied. To facilitate implementations only codes whose parity-check matrices having bidiagonal structure of their submatrices and consequently having low encoding complexity are considered. The problem of finding QC LDPC codes with the near-optimum frame or bit error rate performance is split into two independent steps: searching for the near-optimum column degree distribution of the parity-check matrix together with the best base matrix for this degree distribution and searching for the near-optimum labeling of the chosen base matrix. Sets of parameters and criteria for both steps are introduced and discussed. They allow further reduction of the search complexity without significant loss of the search optimality. New QC LDPC block codes of various code rates are obtained and their BER and FER performances are compared with those of the LDPC block codes as well as the turbo codes defined in the IEEE 802.16 WiMAX standard.

Relations between Generalized LDPC codes, nonbinary LDPC codes, and woven graph codes are considered. Focus is on rather short codes suitable, for example, for coding control signaling information in mobile communications. In particular, codes of lengths less than 200 bits are studied. Low-complexity near maximum-likelihood (ML) decoding for these classes of codes is introduced and analyzed. Frame error rate (FER) performance of the new decoding procedure is compared with the same performance of ML and belief propagation (BP) decoding. It is shown that unlike BP decoding whose performances are mainly governed by the girth of the Tanner graph the new decoding procedure has performances which significantly depend on the minimum distance and spectrum of the woven code. Short woven graph codes with large minimum distances are tabulated.

The girth profile is introduced and search algorithms for regular and irregular quasi-cyclic LDPC block codes with both good girth profile and good degree distribution are presented. New QC LDPC block codes of various code rates are obtained and their bit error rate performance is compared with that of the corresponding LDPC block codes defined in the IEEE 802.16 WiMAX standard of the same block length and code rate.

In 1995, Bestpublished a formula for the exact bit error probability for Viterbi decoding of the rate$R=1/2$, memory$m=1$(two-state) convolutional encoder with generator matrix$G(D)=(1 \quad 1+D)$when used to communicate over the binary symmetric channel. Their formula was later extended to the rate$R=1/2$, memory$m=2$(four-state) convolutional encoder with generator matrix$G(D)=(1+D^{2} \quad 1+D+D^{2})$by LentmaierIn this paper, a different approach to derive the exact bit error probability is described. A general recurrent matrix equation, connecting the average information weight at the current and previous states of a trellis section of the Viterbi decoder, is derived and solved. The general solution of this matrix equation yields a closed-form expression for the exact bit error probability. As special cases, the expressions obtained by Bestfor the two-state encoder and by Lentmaierfor a four-state encoder are used. The closed-form expression derived in this paper is evaluated for various realizations of encoders, including rate$R=1/2$and$R=2/3$encoders, of as many as 16 states. Moreover, it is shown that it is straightforward to extend the approach to communication over the quantized additive white Gaussian noise channel.

The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.

A new method using Hamming codes to construct base matrices of (J,K)-regular LDPC convolutional codes with large free distance is presented. By proper labeling the corresponding base matrices and tailbiting these parent convolutional codes to given lengths, a large set of quasi-cyclic (QC) (J,K)-regular LDPC block codes with large minimum distance is obtained. The corresponding Tanner graphs have girth up to 14. This new construction is compared with two previously known constructions of QC (J,K)-regular LDPC block codes with large minimum distance exceeding (J + 1)!. Applying all three constructions, new QC (J,K)-regular block LDPC codes with J = 3 or 4, shorter codeword lengths and/or better distance properties than those of previously known codes are presented.

The relation between the parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and the biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Algorithms for searching iteratively for LDPC block codes with large girth are presented and constructions based on Steiner Triple Systems and short QC block codes are introduced, leading to new QC regular LDPC block codes with girth up to 24.

The relation between low-density parity-check (LDPC) codes and hypergraphs supports searching for powerful LDPC codes based on hypergraphs. On the other hand, coding theory methods can be used in searching for hypergraphs with large girth. Moreover, compact representations of hypergraphs based on convolutional codes can be found. Algorithms for iteratively constructing LDPC codes with large girth and for determining their minimum distance are introduced. New quasi-cyclic (QC) LDPC codes are presented, some having both optimal girth and optimal minimum distance.

Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensembles of such codes based on$s$-partite,$s$-uniform hypergraphs, where$s$depends only on the code rate, there exist codes satisfying the Gilbert—Varshamov (GV) and the Costello lower bound on the minimum distance and the free distance, respectively. A connection between regular bipartite graphs and tailbiting (TB) codes is shown. Some examples of woven graph codes are presented. Among them, an example of a rate$R_{\rm wg}=1/3$woven graph code with$d_{\rm free}=32$based on Heawood's bipartite graph, containing$n=7$constituent rate$R^{\rm c}=2/3$convolutional codes with overall constraint lengths$\nu^{\rm c}=5$, is given.

A rate R=5/20 hypergraph-based woven convolutional code with overall constraint length 67 and constituent convolutional codes is presented. It is based on a 3-partite, 3-uniform, 4-regular hypergraph and contains rate Rc=3/4 constituent convolutional codes with overall constraint length 5. Although the code construction is based on low-complexity codes, the free distance of this construction, computed with the BEAST algorithm, is dfree=120, which is remarkably large.

Rate R = (c-1)/c convolutional codes of constraint length ν can be represented by conventional syndrome trellises with a state complexity of s = ν or by binary syndrome trellises with a state complexity of s = ν or s = ν + 1, which corresponds to at most 2sstates at each trellis level. It is shown that if the parity-check polynomials fulfill certain conditions, there exist binary syndrome trellises with optimum state complexity s = ν. The BEAST is modified to handle parity-check matrices and used to generate code tables for optimum free distance rate R = (c - 1)=c, c = 3; 4; 5, convolutional codes for conventional syndrome trellises and binary syndrome trellises with optimum state complexity. These results show that the loss in distance properties due to the optimum state complexity restriction for binary trellises is typically negligible.

Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensemble of such codes based on s-partite, s-uniform hypergraphs, where s depends only on the code rate, there exist codes satisfying the Varshamov-Gilbert (VG) and the Costello lower bound on the minimum distance and the free distance, respectively.

List decoding of binary block codes for the additive white Gaussian noise (AWGN) channel is considered. The output of a list decoder is a list of the$L$most likely codewords, that is, the$L$signal points closest to the received signal in the Euclidean-metric sense. A decoding error occurs when the transmitted codeword is not on this list. It is shown that the list error probability is fully described by the so-called list configuration matrix, which is the Gram matrix obtained from the signal vectors forming the list. The worst case list configuration matrix determines the minimum list distance of the code, which is a generalization of the minimum distance to the case of list decoding. Some properties of the list configuration matrix are studied and their connections to the list distance are established. These results are further exploited to obtain a new upper bound on the list error probability, which is tighter than the previously known bounds. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability for a given list. The results are illustrated by examples.

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximatea posterioriprobabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.

A construction of woven graph codes based on constituent convolutional codes is studied. It is shown that within the random ensemble of such codes there exist asymptotically good codes with short fixed constituent codes. An example of a rate R = 1/3 woven graph code with free distance equal to 32 based on rate Rc= 2/3 constituent convolutional codes with overall constraint length 5 is given.

This paper reviews soft-input soft-output (SISO) algorithms that have been recently proposed as reduced-complexity alternatives to maximumaposteriori(MAP) trellis-based decoding or equalization. The M*-BCJR, LISS, and BEAST algorithms are chosen as representatives of reduced-state trellis- and tree- search procedures. The former two algorithms have been initially developed for intersymbol interference (ISI) equalization, while BEAST is tailored for decoding. All three algorithms are modified for either application and their advantages and shortcomings are studied for each case. Comparisons in terms of performance and complexity are presented.

An extended table of Shuurman's bounds on the state complexity of short binary linear codes is presented. Some new lower and upper bounds are obtained. Most of the newly found codes are based on the so-called double zero-tail termination (DZT) construction.

A new upper bound on the list error probability is presented. This bound is derived by combining the techniques for obtaining the tangential union bound with an improved bound on the error probability with respect to a given list. Connections between the list distance and the eigenvalues of the covariance matrix of the code are studied.

The performance and convergence behavior of the iterative schemes for decoding two-dimensional product codes are investigated. The decoding trajectories of the extrinsic and the a posteriori information are used as a main tool for predicting and explaining the behavior of the iterative decoding process. The component-wise optimal BCJR decoder is compared to the suboptimal max-log-MAP decoder and the list-based BEAST-APP decoder in terms of convergence and bit-error-rate performance. The results are illustrated by examples, which show that the BEAST-APP decoder achieves near-BCJR performance with significantly lower complexity.

In this correspondence, unequal error-correcting capabilities of convolutional codes are studied. For errors in the information symbols and code symbols, the free input- and output-distances, respectively, serve as "unequal" counterparts to the free distance. When communication takes place close to or above the channel capacity the error bursts tend to be long and the free distance is not any longer useful as the measure of the error correcting capability. Thus, the active burst distance for a given output and the active burst distance for a given input are introduced as "unequal" counterparts to the active burst distance and improved estimates of the unequal error-correcting capabilities of convolutional codes are obtained and illustrated by examples. Finally, it is shown how to obtain unequal error protection for both information and code symbols using woven convolutional codes.

The BEAST-APP decoding algorithm is a low-complexity bidirectional algorithm that searches code trees to find the list of the most likely codewords, which are used to compute approximate a posteriori probabilities (APPs) of the transmitted symbols. It can be applied to APP-decoding of any linear block code, as well as in iterative structures for decoding concatenated block codes. Previous work has shown that the list size sufficient to achieve the performance of true-APP decoding is very small. This paper aims at providing a theoretical justification for this result. The sufficient list size is estimated first via the minimum list distance - a parameter that is defined and analyzed as a key factor that governs the performance of list-based algorithms. Additionally, statistical properties of the codeword likelihoods are investigated and the typical list structure is presented. Preliminary simulation results for iterative BEAST decoding confirm the list-size estimates obtained from both approaches.

In this paper unequal error-correcting capabilities of convolutional codes are studied. State-transition graphs are used for investigating the error-correcting capabilities for specific inputs or outputs of given convolutional encoding matrices. Active burst input- and output-distances are defined and shown to be generalizations of the active burst distance. These new distances provide better estimates of the error-correction capability, especially when we communicate close to or above the channel capacity and they are connected to the corresponding free input- and output-distances via lower bounds

BEAST is a bidirectional efficient algorithm for searching trees that performs soft-decision maximum-likelihood (ML) decoding of block codes. The decoding complexity of BEAST is significantly reduced compared to the Viterbi algorithm. An analysis of the asymptotic BEAST decoding complexity verifies BEAST's high efficiency compared to other algorithms. The best of the obtained asymptotic upper bounds on the BEAST decoding complexity is better than previously known bounds for ML decoding in a wide range of code rates.

BEAST is a bidirectional efficient algorithm for searching trees. In this correspondence, BEAST is extended to maximum-likelihood (ML) decoding of block codes obtained via convolutional codes. First it is shown by simulations that the decoding complexity of BEAST is significantly less than that of the Viterbi algorithm. Then asymptotic upper bounds on the BEAST decoding complexity for three important ensembles of codes are derived. They verify BEAST's high efficiency compared to other algorithms. For high rates, the new asymptotic bound for the best ensemble is in fact better than previously known bounds.

Good approximations of code-symbol a-posteriori probabilities (APPs) are obtained using a list of the most likely codewords, instead of the whole code-book. This list is found by Bidirectional Efficient Algorithm for Searching code Trees (BEAST), whose complexity is shown to be lower than of the known trellis-based algorithms.

This paper describes the error-correcting capability of a convolutional code when transmitting close to capacity. We show that it is the combination of average burst length and first event error probability that allows us to better describe the error-correcting capability of a code.

This paper describes the active burst distance for convolutional codes. The unequal error protection for information sequences are used to formulate a theorem on the error-correcting capability of the generator matrix and set state paths in the encoder state-transition diagram correspond to code sequences. Therefore the active-distance concepts are used to characterize the error patterns.

When searching for convolutional codes and tailbiting codes of high complexity it is of vital importance to use fast algorithms for computing their weight spectra, which corresponds to finding low-weight paths in their code trellises. This can be efficiently done by a combined search in both forward and backward code trees. A bidirectional efficient algorithm for searching such code trees (BEAST) is presented. For large encoder memories, it is shown that BEAST is significantly more efficient than comparable algorithms. BEAST made it possible to find new convolutional and tailbiting codes that have larger free (minimum) distances than the previously best known codes with the same parameters. Tables of such codes are presented.

A new class of block codes with low state complexity of their conventional trellis representations called double zero-tail terminated convolutional codes (DZT codes) is introduced. It is shown that there exist DZT-codes meeting the Varshamov-Gilbert bound on the minimum distance and having asymptotically optimal state complexity. Two ways of constructing DZT-codes are considered. Examples of DZT-codes meeting a lower bound on the state complexity are given.

An error exponent for woven convolutional codes (WCC) with one tailbiting component code is derived. This error exponent is compared with that of the original WCC. It is shown that for WCC with outer warp, a better error exponent is obtained if the inner code is terminated with the tailbiting method. Furthermore, it is shown that the decoding error probability decreases exponentially with the square of the memory of the constituent convolutional encoders, while the decoding complexity grows exponentially only with the memory.

An iterative decoding scheme for woven convolutional codes is presented. It operates in a window sliding over the received sequence. This exploits the nature of convolutional codewords as infinite sequences and reflects the concept of considering convolutional encoding and decoding as a continuous process. The decoder is analyzed in terms of decoding delay and decoding complexity. Its basic building block is a symbol-by-symbol a posteriori probability (APP) decoder for convolutional codes, which is a windowed variant of the well-known Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. Additional interleaving for the woven constructions is introduced by employing convolutional scramblers. It is shown that row-wise random interleaving preserves the lower bound on the free distance of the original woven constructions. Based on the properties of the interleavers, new lower bounds on the free distance of woven constructions with both outer warp and inner warp are derived. Simulation results for woven convolutional codes with and without additional interleaving are presented.

Nested convolutional codes are a set of convolutional codes that is derived from a given generator matrix. The structural properties of nested convolutional codes and nested generator matrices are studied. A method to construct the set of all minimal (rational) generator matrices of a given convolutional code is presented. As an example, two different sets of nested convolutional codes are derived from two equivalent minimal generator matrices. The significant difference in their free-distance profiles emphasizes the importance of being careful when selecting the generator matrices that determine the nested convolutional codes. As an application of nested convolutional codes, woven codes with outer warp, and inner nested convolutional codes are considered. The free-distance profile of the inner generator matrix is shown to be an important design tool.

Tailbiting is an attractive method to terminate convolutional codes without reducing the code rate. Maximum-likelihood and exact a posteriori probability decoding of tailbiting codes implies, however, a large computational complexity. Therefore, suboptimal decoding methods are often used in practical coding schemes. It is shown that suboptimal decoding methods work better when the slope of the active distances of the generating convolutional encoder is large. Moreover, it is shown that considering quasi-cyclic shifts of the received channel output can increase the performance of suboptimal tailbiting decoders. The findings are most relevant to tailbiting codes where the number of states is not small relative to the block length.

The slope of the active distances is an important parameter when investigating the error-correcting capability of convolutional codes and the distance behavior of concatenated convolutional codes. The slope of the active distances is equal to the minimum average weight cycle in the state-transition diagram of the encoder. A general upper bound on the slope depending on the free distance of the convolutional code and new upper bounds on the slope of special classes of binary convolutional codes are derived. Moreover, a search technique, resulting in new tables of rate R=1/2 and rate R=1/3 convolutional encoders with high memories and large active distance-slopes is presented. Furthermore, we show that convolutional codes with large slopes can be used to obtain new tailbiting block codes with large minimum distances. Tables of rate R=1/2 and rate R=1/3 tailbiting codes with larger minimum distances than the best previously known quasi-cyclic codes are given. Two new tailbiting codes also have larger minimum distances than the best previously known binary linear block codes with same size and length. One of them is also superior in terms of minimum distance to any previously known binary nonlinear block code with the same set of parameters.

Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes.

Encoders for convolutional codes with large free distances can be constructed by combining several less powerful convolutional encoders. This paper is devoted to constructions in which the constituent convolutional codes are woven together in a manner that resembles the structure of a fabric. The general construction is called twill and it is described together with two special cases, viz., woven convolutional encoders with outer warp and with inner warp. The woven convolutional encoders inherit many of their structural properties, such as minimality and catastrophicity, from their constituent encoders. For all three types of woven convolutional codes upper and lower bounds on their free distances as well as lower bounds on the active distances of their encoders are derived.

Tailbiting codes encoded by feedback convolutional encoders are studied. A condition for when tailbiting will work is given and it is described how the encoder starting state can be obtained for feedback encoders in both controller and observer canonical forms. Finally, results from a search for systematic feedback encoders that encode tailbiting codes with good decoding bit error probabilities are presented.

In this correspondence, the error exponents and decoding complexity of binary woven convolutional codes with outer and inner warp are studied. It is shown that for both constructions an error probability that is exponentially decreasing with the memory of the woven convolutional codes can be achieved with a nonexponentially increasing decoding complexity. Furthermore, the error exponent for woven convolutional codes with inner warp is larger than the one for woven convolutional codes with outer warp.

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/sub 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 family of active distance measures for general convolutional codes is defined. These distances are generalizations of the extended distances introduced by Thommesen and Justesen (1983) for unit memory convolutional codes. It is shown that the error correcting capability of a convolutional code is determined by the active distances. The ensemble of periodically time-varying convolutional codes is defined and lower bounds on the active distances are derived for this ensemble. The active distances are very useful in the analysis of concatenated convolutional encoders.

Tabulations of binary systematic and nonsystematic polynomial convolutional encoders with an optimum distance profile for rate 1/2, 1/3, and 1/4 are given. The reported encoders are found by computer searches that optimize over the weight spectra. The free distances for rate 1/3 and 1/4 are compared with Heller's (1968) and Griesmer's (1960) upper bounds.

The results of an extensive search for short and moderate length polynomial convolutional encoders for time-invariant tail-biting representations of block codes at rates R=1/4, 1/3, 1/2, and 2/3 are reported. The tail-biting representations found are typically as good as the best known block codes.

In this correspondence the error exponent and the decoding complexity of binary woven convolutional codes with outer warp and with binary convolutional codes as outer and inner codes are studied. It is shown that an error probability that is exponentially decreasing with the product of the outer and inner code memories can be achieved with a nonexponentially increasing decoding complexity.

For rate R=1/2 convolutional codes with 16 states there exists a gap between Heller's (1968) upper bound on the free distance and its optimal value. This article reports on the construction of 16-state, binary, rate R=2/4 nonlinear trellis and convolutional codes having d/sub free/=8; a free distance that meets the Heller upper bound. The nonlinear trellis code is constructed from a 16-state, rate R=1/2 convolutional code over Z/sub 4/ using the Gray map to obtain a binary code. Both convolutional codes are obtained by computer search. Systematic feedback encoders for both codes are potential candidates for use in combination with iterative decoding. Regarded as modulation codes for 4-PSK, these codes have free squared Euclidean distance d/sub E, free//sup 2/=16.

Convolutional codes over rings have been motivated by phase-modulated signals. Some structural properties of the generator matrices of such codes are presented. Successively stronger notions of the invertibility of generator matrices are studied, and a new condition for a convolutional code over a ring to be systematic is given and shown to be equivalent to a condition given by Massey and Mittelholzer (1990). It is shown that a generator matrix that can be decomposed into a direct sum is basic, minimal, and noncatastrophic if and only if all generator matrices for the constituent codes are basic, minimal, and noncatastrophic, respectively. It is also shown that if a systematic generator matrix can be decomposed into a direct sum, then all generator matrices of the constituent codes are systematic, but that the converse does not hold. Some results on convolutional codes over Z(p/sup e/) are obtained.

Consider nonbacktracking convolutional decoders that keep a fixed number of trellis survivors. It is shown that the error performance of these depends on the early part of the distance profile and on the number of survivors kept, and not on the free distance or the details of the code generators. Particularly, the encoder may be feedforward systematic without loss. Furthermore, this kind of encoder solves the correct path loss problem in reduced-search decoders. Other kinds do not. Therefore, with almost any other decoding method than the Viterbi algorithm, systematic feed-forward encoders should be used. The conclusions in this correspondence run counter to much accepted wisdom about convolutional codes.

A full-rank K/spl times/n matrix G(D) over the rational functions F(D) generates a rate R=k/n convolutional code C. G(D) is minimal if it can be realized with as few memory elements as any encoder for C, and G(D) is canonical if it has a minimal realization in controller canonical form. We show that G(D) is minimal if and only if for all rational input sequences u(D), the span of u(D)G(D) covers the span of u(D). Alternatively, G(D) is minimal if and only if G(D) is globally zero-free, or globally invertible. We show that G(D) is canonical if and only if G(D) is minimal and also globally orthogonal, in the valuation-theoretic sense of Monna (1970).

The authors review the work of G.D. Forney, Jr., on the algebraic structure of convolutional encoders upon which some new results regarding minimal convolutional encoders rest. An example is given of a basic convolutional encoding matrix whose number of abstract states is minimal over all equivalent encoding matrices. However, this encoding matrix can be realized with a minimal number of memory elements neither in controller canonical form nor in observer canonical form. Thus, this encoding matrix is not minimal according to Forney's definition of a minimal encoder. To resolve this difficulty, the following three minimality criteria are introduced: minimal-basic encoding matrix, minimal encoding matrix, and minimal encoder. It is shown that all minimal-basic encoding matrices are minimal and that there exist minimal encoding matrices that are not minimal-basic. Several equivalent conditions are given for an encoding matrix to be minimal. It is proven that the constraint lengths of two equivalent minimal-basic encoding matrices are equal one by one up to a rearrangement. All results are proven using only elementary linear algebra.>

Simmons' lower bound on impersonation P/sub 1/>or=2/sup -I(M;E)/ where M and E denote the message and the encoding rule, respectively, is strengthened by maximizing over the source statistics and by allowing dependence between the message and the encoding rule. The authors show that a refinement of their argument, which removes the assumption of independence between E and the source state S, leads to an even stronger bound.>

A fast algorithm for searching a tree (FAST) is presented for computing the distance spectrum of convolutional codes. The distance profile of a code is used to limit substantially the error patterns that have to be searched. The algorithm can easily be modified to determine the number of nonzero information bits of an incorrect path as well as the length of an error event. For testing systematic codes, a faster version of the algorithm is given. FAST is much faster than the standard bidirectional search. On a microVAX, d/sub infinity /=27 was verified for a rate R=1/2, memory M=25 code in 37 s of CPU time. Extensive tables of rate R=1/2 encoders are given. Several of the listed encoders have distance spectra superior to those of any previously known codes of the same rate and memory. A conjecture than an R=1/2 systematic convolutional code of memory 2M will perform as well as a nonsystematic convolutional code of memory M is given strong support.>

It is well known that the computational performance of sequential decoding deteriorates greatly when channel errors occur in clusters, as in Gilbert channels. A way of using sequential decoding to exploit the memory of a Gilbert channel that alleviates this problem is presented. A Fano-like metric matched to this channel is used. The method is investigated by simulating sequential decoding utilizing the stack algorithm. The simulations confirm the feasibility of the technique.< >

Multitype branching processes have been employed to determine the stack algorithm computational distribution for one subtree. These results are extended here to the distribution of the number of computations in any finite number of subtrees. Starting from the computational distribution forK-1subsequent subtrees, a recurrent equation for the distribution forKsubsequent subtrees is determined.

An upper bound on the first-event error probability for maximum-likelihood decoding of fixed binary convolutional codes on the binary symmetric channel is derived. The bound is evaluated for rate1/2codes, and comparisons are made with simulations and with the bounds of Viterbi, Van de Meeberg, and Post. In particular, the new bound is significantly better than Van de Meeberg's bound for rates aboveR_{\comp}.

An analytical procedure is presented for generating the computational distribution for the Zigangirov-Jelinek stack algorithm. Multitype branching processes are employed to develop a procedure for estimating sequential decoding computation, without the need for simulation, but with sufficient accuracy to be a valid design tool. At information rates about the cutoff rateR_{o}the calculated computational performance is virtually Identical to that obtained by time consuming simulations.

Fixed binary convolutional codes are considered which are simultaneously optimal or near-optimal according to three criteria: namely, distance profiled, free distanced_{ \infty}, and minimum number of weightd_{\infty}paths. It is shown how the optimum distance profile criterion can be used to limit the search for codes with a large value ofd_{\infty}. We present extensive lists of such robustly optimal codes containing rateR = l/2nonsystematic codes, several withd_{\infty}superior to that of any previously known code of the same rate and memory; rateR = 2/3systematic codes; and rateR = 2/3nonsystematic codes. As a counterpart to quick-look-in (QLI) codes which are not "transparent," we introduce rateR = 1/2easy-look-in-transparent (ELIT) codes with a feedforward inverse(1 + D,D). In general, ELIT codes haved_{\infty}superior to that of QLI codes.

A tabulation of binary systematic convolutional codes with an optimum distance profile for rates1/3and1/4is given. A number of short rate1/3binary nonsystematic convolutional codes are listed. These latter codes are simultaneously optimal for the following distance measures: distance profile, minimum distance, and free distance; they appear attractive for use with Viterbi decoders. Comparisons with previously known codes are made.

An upper bound on the average error probability for maximum-likelihood decoding of the ensemble of randomL-branch binary trellis codes of rateR = 1/nis given which separates the effects of the tail lengthTand the memory lengthMof the code. It is shown that the bound is independent of the lengthLof the information Sequence whenM \geq T + [nE_{VU}(R)]^{-1} \log_{2} L. The implication that the actual error probability behaves similarly is investigated by computer simulations of sequential decoding utilizing the stack algorithm. These simulations confirm the implication which can thus be taken as a design rule for choosingMso that the error probability is reduced to its minimum value for a givenT.

This correspondence gives a tabulation of long systematic, and long quick-look-in (QLI) nonsystematic, rateR = 1/2binary convolutional codes with an optimum distance profile (ODP). These codes appear attractive for use with sequential decoders.

Three optimality criteria for convolutional codes are considered in this correspondence: namely, free distance, minimum distance, and distance profile. Here we report the results of computer searches for rate one-half binary convolutional codes that are "robustly optimal" in the sense of being optimal for one criterion and optimal or near-optimal for the other two criteria. Comparisons with previously known codes are made. The results of a computer simulation are reported to show the importance of the distance profile to computational performance with sequential decoding.