A probabilistic algorithm is used to construct large constraint length trellis codes at high spectral efficiencies for use with sequential decoding. Linear trellis codes for two- and four-dimensional constellations with constraint lengths up to 19 are obtained. These codes can achieve 180/spl deg/ rotational invariance. To achieve full 90/spl deg/ rotational invariance, nonlinear trellis codes for four-dimensional constellations with constraint lengths up to 19 are obtained. In both cases it is shown that the channel cutoff rate bound can be achieved using constraint lengths between 16 and 19 with sequential decoding at a bit-error rate of 10/sup -5/-10/sup -6/ and that 4.9-5.8 dB real coding gains can be achieved over uncoded systems with the same spectral efficiency.

The relationship between the distance properties of trellis codes and the computational effort and error performance of sequential decoding is studied and optimum distance profile (ODP) and optimum free distance (OFD) trellis codes are constructed for 8-PSK and 16 QAM modulation. A comparison of the performance of both the ODP and the OFD trellis codes reveals that neither class of codes results in the best trade-off between error performance and computational effort when sequential decoding is used. A new algorithm is then proposed to construct robustly good trellis codes for use with sequential decoding. New trellis codes with asymptotic coding gains up to 6.66 dB are obtained using this algorithm, and the new codes achieve nearly the same free distances as the OFD codes and nearly the same distance profiles as the ODP codes.

Two new classes of rotationally invariant trellis codes are constructed. A simple method is used to check the rotational invariance of a given code in the process of searching for optimum trellis codes. A class of linear trellis codes with constraint lengths 2-9 using four-dimensional constellations is presented. Simulation results show that a 180/spl deg/ rotationally invariant, constraint length 8, linear trellis code achieves about 0.4-dB real coding gain compared to the best constraint length 6 code, while the trellis complexity is only four times that of the constraint length 6 code. On the other hand, the constraint length 6 code that has been adopted for use in the V.34 28.8-kbit/s modem standard has the same 0.4-dB real coding gain compared to a constraint length 4 code which has also been adopted for the standard, but it requires sixteen times the trellis complexity. A class of fully rotationally invariant nonlinear trellis codes with constraint lengths 6-11 is also presented. Simulation results show that a 90/spl deg/ rotationally invariant, constraint length 8, nonlinear trellis code performs almost as well as the best linear code.

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/sup -5/-10/sup -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/sup -5/-10/sup -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.>

Sequential decoding of the channel code in a trellis-coded modulation system with trellis shaping can be used to reduce the system complexity and to achieve high coding gain with large constraint-length codes. It is shown that almost all the shaping gain that can be achieved when Viterbi decoding is used for the channel code can also be achieved when sequential decoding is used for the channel code. It is also shown that the real shaping gain is a function of both the SNR and the spectral efficiency.

Systematic feedforward trellis codes for 8-PSK and 16-QAM modulation are constructed using a nested step by step algorithm which guarantees a good distance profile. This makes the codes suitable for use with sequential decoding, where a rapidly growing distance profile is needed to reduce the average number of computations. In addition to having a good distance profile, the new codes achieve asymptotic coding gains of up to 6.53 dB. A procedure based upon the Fano (1963) algorithm (FA) is used to calculate the free distance of the new codes. This procedure is very effective for finding the free distances of long trellis codes because of the computational and storage efficiency of the FA. From a comparison of the new systematic feedforward codes with Ungerboeck's (1982, 1987) systematic feedback codes, the authors conjecture that a systematic feedforward code of constraint length 2/spl nu/ can achieve the same free distance as a systematic feedback code of constraint length /spl nu/.>

An erasure-free sequential decoding algorithm for trellis codes, called the buffer looking algorithm (BLA), is introduced. Several versions of the algorithm can be obtained by choosing certain parameters and selecting a resynchronization scheme. These can be categorized as block decoding or continuous decoding, depending on the resynchronization scheme. Block decoding is guaranteed to resynchronize at the beginning of each block, but suffers some rate loss when the block length is relatively short. The performance of a typical block decoding scheme is analyzed, and we show that significant coding gains over Viterbi decoding can be achieved with much less computational effort. A resynchronization scheme is proposed for continuous sequential decoding. It is shown by analysis and simulation that continuous sequential decoding using this scheme has a high probability of resynchronizing successfully. This new resynchronization scheme solves the rate loss problem resulting from block decoding. The channel cutoff rate, demodulator quantization, and the tail's influence on performance are also discussed. Although this paper considers only the decoding of trellis codes, the algorithm can also be applied to the decoding of convolutional codes.>