Probabilistic construction of large constraint length trellis codesfor sequential decoding

Probabilistic algorithms are given for constructing good large constraint length trellis codes for use with sequential decoding that can achieve the channel cutoff rate bound at a bit error rate (BER) of 10^-5-10^-6. The algorithms are motivated by the random coding principle that an arbitrary selection of code symbols will produce a good code with high probability. One algorithm begins by choosing a relatively small set of codes randomly. The error performance of each of these codes is evaluated using sequential decoding and the code with the best performance among the chosen set is retained. Another algorithm treats the code construction as a combinatorial optimization problem and uses simulated annealing to direct the code search. Trellis codes for 8 PSK and 16 QAM constellations with constraint lengths v up to 20 are obtained. Simulation results with sequential decoding show that these codes reach the channel cutoff rate bound at a BER of 10^-5-10^-6 and achieve 5.0-6.35 dB real coding gains over uncoded systems with the same spectral efficiency and up to 2.0 dB real coding gains over 64 state trellis codes using Viterbi decoding     

Optimal sectionalization of a trellis

While the complexity of trellis decoding for a given block code is essentially a function of the number of states and branches in its trellis, the decoding complexity may be often reduced by means of an appropriate sectionalization of the trellis. Notwithstanding the many examples of such sectionalizations for particular codes that appeared in the literature, no systematic method for finding the best sectionalization of a given trellis is presently known. We present a polynomial-time algorithm which produces the optimal sectionalization of a given trellis T in time O(n²), where n is the length of the code generated by T. The algorithm is developed in a general setting of certain operations and functions defined on the set of trellises; it therefore applies to both linear and nonlinear codes, and easily accommodates a broad range of optimality criteria. The particular optimality criterion based on minimizing the total number of additions and comparisons required for maximum-likelihood trellis decoding is investigated in detail: several different methods for decoding a given trellis are discussed and compared in a number of examples. Finally, analysis of the dynamical properties of certain optimal sectionalizations is presented     

Performance of Reduced State S–T Trellis Coded MC-CDMA Systems

In this paper, performance of reduced state space-time trellis coded multi carrier code division multiple access (STTC-MC-CDMA) system is evaluated and compared with the performance of original state STTC-MC-CDMA system. The optimum decoding scheme, i.e., maximum likelihood sequence estimation is employed which uses Viterbi algorithm for decoding STTC code. To simplify the implementation of the STTC decoder, the number of states is reduced by reducing the constraint length of the STTC encoder using generating function technique. In this technique, the generator matrix of STTC code is minimized to reduce the number of states of S–T trellis decoder. It is observed that the performance loss in terms of frame error rate of the reduced state STTC-MC-CDMA system is negligible compared to the original state STTC-MC-CDMA system. It is also noted that by using the reduced state technique the STTC decoder can be made faster since it is having lower computational complexity.     

Codes on graphs: constraint complexity of cycle-free realizations of linear codes

Cycle-free graphical realizations of linear codes generalize trellis realizations. Given a linear code C and a cycle-free graph topology, there exists a well-defined minimal realization for C on that graph in which each constraint is a linear code with a well-defined length and dimension. The constraint complexity of the realization is defined as maximum dimension of any constraint code. There exists a graph that minimizes constraint complexity in which all internal nodes have degree 3 and all interface nodes have degree 2, and which moreover can be put in the form of a "tree-structured trellis realization." The constraint complexity of a general cycle-free graph realization can be less than that of any conventional trellis realization, but not by very much. Such realizations can yield reductions in decoding complexity even when they do not reduce constraint complexity.     

Trellis Encoding of memoryless discrete-time sources with a fidelity criterion

For memoryless discrete-time sources and bounded single-letter distortion measures, we derive a bound on the average per-letter distortion achievable by a trellis source code of fixed constraint length. For any fixed code rate greater thanR(D^{ast}), the rate-distortion function atD^{ast}, this bound decreases towardD^{ast}exponentially with constraint length.     

Soft-decision decoding using punctured codes

Let a q-ary linear (n,k)-code be used over a memoryless channel. We design a soft-decision decoding algorithm that tries to locate a few most probable error patterns on a shorter length s ∈ [k,n]. First, we take s cyclically consecutive positions starting from any initial point. Then we cut the subinterval of length s into two parts and examine T most plausible error patterns on either part. To obtain codewords of a punctured (s,k)-code, we try to match the syndromes of both parts. Finally, the designed codewords of an (s,k)-code are re-encoded to find the most probable codeword on the full length n. For any long linear code, the decoding error probability of this algorithm can be made arbitrarily close to the probability of its maximum-likelihood (ML) decoding given sufficiently large T. By optimizing s, we prove that this near-ML decoding can be achieved by using only T≈q^(n-k)k(n+k)/ error patterns. For most long linear codes, this optimization also gives about T re-encoded codewords. As a result, we obtain the lowest complexity order of q^(n-k)k(n+k)/ known to date for near-ML decoding. For codes of rate 1/2, the new bound grows as a cubic root of the general trellis complexity q^min{n-k,k}. For short blocks of length 63, the algorithm reduces the complexity of the trellis design by a few decimal orders     

Two trellis coding schemes for large free distances

A trellis code encoded by using the encoder of a convolutional code C with a short constraint length followed by an additional processing unit is equivalent to a trellis code with a large constraint-length. In 1993, Hellstern proposed a trellis coding scheme for which the processing unit consists of a delay processor and a signal mapper. With Hellstern's scheme, trellis codes with large free distances can be constructed. In this paper, we propose two trellis coding schemes. For the first scheme, the processing unit is composed of multiple pairs of delay processors and signal mappers. For the second scheme, the processing unit is composed of a convolutional processor and a signal mapper, where a convolutional processor is a rate 1 convolutional code. The trellis code constructed from each of the proposed schemes can be suboptimally decoded by using the trellis of the convolutional code C with some feedback information. Either of the proposed schemes can produce a trellis code that has a larger bound on free distance and better error performance as compared to the trellis code constructed from Hellstern's scheme based on the same convolutional code C     

Optimization of Trellis Codes with Multilevel Amplitude Modulation with Respect to an Error Probability Criterion

An easily computed upper bound on the error probability of a data communications system with combined trellis coding and multilevel/phase modulation is derived, assuming an additive white Gaussian noise channel and maximum-likelihood decoding. This bound is used to search for codes obtained by set-partitioning that minimize the bound for a fixed number of trellis states. Only amplitude modulated signals typically used in voiceband modem applications are considered. The signal levels that minimize the error probability bound subject to an average power constraint are presented for some specific codes.     

Truncation Error Probability in Viterbi Decoding

An upper bound on the bit error probability due to truncation of the path length in Viterbi decoding is obtained for any given convolutional code. This bound is then used to determine the path length at which the additional error probability due to truncation becomes negligible compared to the maximum likelihood decoding error probability. These results are tested by simulation using several short constraint length codes.     

Coherent detection of interleaved trellis encoded CPFSK on shadowedmobile satellite channels

A receiver that utilizes trellis coded continuous phase frequency shift keying (CPFSK) with coherent detection and convolutional interleaving of the coded symbols for data transmission is presented. An earlier study considered decoding based solely on the code trellis. A new decoding algorithm that copes with the interleaving is presented and uses information from both the modulation trellis and the code trellis. The performance results are obtained by Monte Carlo simulation and are partially verified through analysis. The fading model is Rician, but the line-of-sight (LOS) component is subjected to a log-normal transformation that represents attenuations due to foliage which is referred to as shadowing. The system studied is not suitable for digital speech applications as the required interleaving depths lad to an unacceptable time delay     

A Gilbert bound for periodic binary convolutional codes

A Gilbert bound for periodic binary convolutional (PBC) codes is established. This bound shows that regardless of previous decoding decisions any fraction of errors less thanalpha/2can be corrected in a constraint length by some PBC code if the constraint length is sufficiently large andR, the code rate, is less than[1 - H(alpha)]/2, 0 leq alpha < frac{1}{2}.     

Constraint Complexity of Realizations of Linear Codes on Arbitrary Graphs

A graphical realization of a linear code C consists of an assignment of the coordinates of C to the vertices of a graph, along with a specification of linear state spaces and linear "local constraint" codes to be associated with the edges and vertices, respectively, of the graph. The kappa-complexity of a graphical realization is defined to be the largest dimension of any of its local constraint codes, kappa -complexity is a reasonable measure of the computational complexity of a sum-product decoding algorithm specified by a graphical realization. The main focus of this paper is on the following problem: given a linear code C and a graph G, how small can the kappa-complexity of a realization of C on G be? As useful tools for attacking this problem, we introduce the vertex-cut bound, and the notion of "vc-treewidth" for a graph, which is closely related to the well-known graph-theoretic notion of treewidth. Using these tools, we derive tight lower bounds on the kappa-complexity of any realization of C on G. Our bounds enable us to conclude that good error-correcting codes can have low-complexity realizations only on graphs with large vc-treewidth. Along the way, we also prove the interesting result that the ratio of the kappa-complexity of the best conventional trellis realization of a length-n code C to the kappa-complexity of the best cycle-free realization of C grows at most logarithmically with code length n. Such a logarithmic growth rate is, in fact, achievable.     

On Minimal Tree Realizations of Linear Codes

A tree decomposition of the coordinates of a code is a mapping from the coordinate set to the set of vertices of a tree. A tree decomposition can be extended to a tree realization, i.e., a cycle-free realization of the code on the underlying tree, by specifying a state space at each edge of the tree, and a local constraint code at each vertex of the tree. The constraint complexity of a tree realization is the maximum dimension of any of its local constraint codes. A measure of the complexity of maximum-likelihood (ML) decoding for a code is its treewidth, which is the least constraint complexity of any of its tree realizations.It is known that among all tree realizations of a linear code that extends a given tree decomposition, there exists a unique minimal realization that minimizes the state-space dimension at each vertex of the underlying tree. In this paper, we give two new constructions of these minimal realizations. As a by-product of the first construction, a generalization of the state-merging procedure for trellis realizations, we obtain the fact that the minimal tree realization also minimizes the local constraint code dimension at each vertex of the underlying tree. The second construction relies on certain code decomposition techniques that we develop. We further observe that the treewidth of a code is related to a measure of graph complexity, also called treewidth. We exploit this connection to resolve a conjecture of Forney's regarding the gap between the minimum trellis constraint complexity and the treewidth of a code. We present a family of codes for which this gap can be arbitrarily large.     

Graph-based iterative decoding algorithms for parity-concatenatedtrellis codes

We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10^-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit     

Low-latency architectures for high-throughput rate Viterbi decoders

In this paper, a novel K-nested layered look-ahead method and its corresponding architecture, which combine K-trellis steps into one trellis step (where K is the encoder constraint length), are proposed for implementing low-latency high-throughput rate Viterbi decoders. The proposed method guarantees parallel paths between any two-trellis states in the look-ahead trellises and distributes the add-compare-select (ACS) computations to all trellis layers. It leads to regular and simple architecture for the Viterbi decoding algorithm. The look-ahead ACS computation latency of the proposed method increases logarithmically with respect to the look-ahead step (M) divided by the encoder constraint length (K) as opposed to linearly as in prior work. For a 4-state (i.e., K=3) convolutional code, the decoding latency of the Viterbi decoder using proposed method is reduced by 84%, at the expense of about 22% increase in hardware complexity, compared with conventional M-step look-ahead method with M=48 (where M is also the level of parallelism). The main advantage of our proposed design is that it has the least latency among all known look-ahead Viterbi decoders for a given level of parallelism.     

On the structure of rate1/nconvolutional codes

We show what choice there is in assigning output digits to transitions of a binary rate1/ncode trellis so that the latter will correspond to a convolutional code. We then prove that in any ratefrac{1}{2}noncatastrophic code of constraint lengthupsiloneach binary sequence of length2j(1 leq j leq upsilon - 1)is associated with exactly2^{upsilon -j -1}distinct pathsjbranches long. As a consequence of the above properties nondegenerate codes with branch complementarity are fully determined by the topological relationship of the trellis transitions associated with output pairs 00. Finally, we derive a new upper bound on free distance of rate1/nconvolutional codes and use our results to determine the length of the largest input sequence that can conceivably result in an output whose weight is     

Coset codes viewed as terminated convolutional codes

Coset codes are considered as terminated convolutional codes. Based on this approach, three new general results are presented. First, it is shown that the iterative squaring construction can equivalently be defined from a convolutional code whose trellis terminates. This convolutional code determines a simple encoder for the coset code considered, and the state and branch labelings of the associated trellis diagram become straightforward. Also, from the generator matrix of the code in its convolutional code form, much information about the trade-off between the state connectivity and complexity at each section, and the parallel structure of the trellis, is directly available. Based on this generator matrix, it is shown that the parallel branches in the trellis diagram of the convolutional code represent the same coset code C₁ of smaller dimension and shorter length. Utilizing this fact, a two-stage optimum trellis decoding method is devised. The first stage decodes C₁ while the second stage decodes the associated convolutional code, using the branch metrics delivered by stage 1. Finally, a bidirectional decoding of each received block starting at both ends is presented. If about the same number of computations is required, this approach remains very attractive from a practical point of view as it roughly doubles the decoding speed. This fact is particularly interesting whenever the second half of the trellis is the mirror image of the first half, since the same decoder can be implemented for both parts     

Codes based on a trellis cut-set transformation. I. Rotationallyinvariant codes

Let a trellis section 𝒯 generate a trellis code 𝒞. We study two trellis sections based on 𝒯, a “cut-set” trellis section 𝒯_cs and a “differential encoder” trellis section 𝒯_de. We show that 𝒯 can be transformed to a cut-set trellis section 𝒯_cs, which is equivalent to 𝒯 in the sense that both 𝒯 and 𝒯 _cs generate 𝒞 and both 𝒯 and 𝒯_cs have the same decoding complexity. A differential encoder trellis section is equivalent to the trellis section obtained by following 𝒯 with a differential encoder. It is shown that both 𝒯_cs and 𝒯_de have inverse transform trellis sections. A differential encoder trellis section generates a rotationally invariant (RI) code in a particularly simple and straightforward way. But an RI code need not have a differential encoder trellis section. However, for all of the RI codes examined here, we show that the cut-set trellis section can be arranged into a differential encoder trellis section. This means that these codes can be decomposed into an encoder followed by a differential encoder. Further we show that when 𝒯 is formed using a linear binary convolutional encoder and a mapping by set partitioning, then 𝒯 followed by a differential encoder gives an RI code which in some cases is as good as the best previously known codes, after applying the inverse transform to 𝒯_de     

On dualizing trellis-based APP decoding algorithms

The trellis of a finite Abelian group code is locally (i.e., trellis section by trellis section) related to the trellis of the corresponding dual group code which allows one to express the basic operations of the a posteriori probability (APP) decoding algorithm (defined on a single trellis section of the primal trellis) in terms of the corresponding dual trellis section. Using this local approach, any algorithm employing the same type of operations as the APP algorithm can, thus, be dualized, even if the global dual code does not exist (e.g., nongroup codes represented by a group trellis). Given this, the complexity advantage of the dual approach for high-rate codes can be generalized to a broader class of APP decoding algorithms, including suboptimum algorithms approximating the true APP, which may be more attractive in practical applications due to their reduced complexity. Moreover, the local approach opens the way for mixed approaches where the operations of the APP algorithm are not exclusively performed on the primal or dual trellis. This is inevitable if the code does not possess a trellis consisting solely of group trellis sections as, e.g., for certain terminated group or ring codes. The complexity reduction offered by applying dualization is evaluated. As examples, we give a dual implementation of a suboptimum APP decoding algorithm for tailbiting convolutional codes, as well as dual implementations of APP algorithms of the sliding-window type. Moreover, we evaluate their performance for decoding usual tailbiting codes or convolutional codes, respectively, as well as their performance as component decoders in iteratively decoded parallel concatenated schemes.     

Iterative maximum-likelihood trellis decoding for block codes

An iterative trellis search technique is described for the maximum-likelihood (ML) soft decision decoding of block codes. The proposed technique derives its motivation from the fact that a given block code may be a subcode for a parent code whose associated trellis has substantially fewer edges. Through the use of list-Viterbi (1967) decoding and an iterative algorithm, the proposed technique allows for the use of a trellis for the parent code in the ML decoding of the desired subcode. Complexity and performance analyses, as well as details of potential implementations, indicate a substantial reduction in decoding complexity for linear block codes of practical length while achieving ML or near-ML soft decision performance