For pt. I see ibid. vol.46, p.1592-1601 (1998). Soft-decision maximum-likelihood decoding of convolutional codes over GF(q) can be accomplished via searching through an error-trellis for the least weighing error sequence. The error-trellis is obtained by a syndrome-based construction. Its structure lends itself particularly well to the application of expedited search procedures. The method to carry out such error-trellis-based decoding is formulated by four algorithms. Three of these algorithms are aimed at reducing the worst case computational complexity, whereas by applying the fourth algorithm, the average computational complexity is reduced under low to moderate channel wise level. The syndrome decoder achieves substantial worst case and average computational gains in comparison with the conventional maximum-likelihood decoder, namely the Viterbi decoder, which searches for the most likely codeword directly within the code.

An error-trellis is a directed graph that represents all the sequences belonging to the coset which contains the symbol-by-symbol detected version of a given received sequence. A modular construction of error-trellises for an (n,k) convolutional code over GF(q) is presented. The trellis is designed on the basis of partitioning the scalar check matrix of the code into submatrices of l rows, accompanied with a corresponding segmentation of the syndrome. The value of the design parameter l is an essentially unconstrained multiple of n-k. For all the cosets of the code, the sections of the error-trellis are drawn from a collection of only q/sup l/ modules; the module for each section is determined by the value of the associated syndrome segment. In case the construction is based on a basic polynomial check matrix, either canonical or noncanonical, then the error-trellis is minimal in the sense that /spl sigma//spl les//spl mu/, where /spl sigma/ is the dimension of the state space of the trellis and /spl mu/ is the constraint length of a canonical generator matrix for the code. For basic check matrices with delay-free columns, the inequality reduces to /spl sigma/=/spl mu/.

We present an efficient recursive algorithm for accomplishing maximum likelihood (ML) soft syndrome decoding of binary convolutional codes. The algorithm consists of signal-by-signal hard decoding followed by a search for the most likely error sequence. The number of error sequences to be considered is substantially larger than in hard decoding, since the metric applied to the error bits is the magnitude of the log likelihood ratio rather than the Hamming weight. An error-trellis (alternatively, a decoding table) is employed for describing the recursion equations of the decoding procedure. The number of its states is determined by the states indicator, which is a modified version of the constraint length of the check matrix. Methods devised for eliminating error patterns and degenerating error-trellis sections enable accelerated ML decoding. In comparison with the Viterbi algorithm, the syndrome decoding algorithm achieves substantial reduction in the average computational complexity, particularly for moderately noisy channels.>