Bootstrap trellis decoding

A new hybrid coding scheme is introduced that bears the same relation to Viterbi decoding as bootstrap hybrid decoding [3] bears to sequential decoding. Bounds on the probability of error are developed and evaluated for some examples. In high-rate regions of interest, the computed exponents are more than three times as large as those for Viterbi decoding. Results of simulations are also presented.     

Permutation trellis codes

We introduce the new concept of permutation trellis codes and present a generalized construction procedure, applying our technique of distance-preserving mappings. Minimum-distance decoding follows naturally, using the Viterbi algorithm. We furthermore investigate the performance of these codes when combined with multitone frequency-shift keying modulation and noncoherent detection in a diversity scheme, to make transmissions robust against narrowband, broadband, and background noise disturbances, such as those encountered in power-line communications.     

Complexity-constrained trellis quantizers

A reasonable measure of quantizer complexity is the expected number of quanta per input sample for which distortion is computed. Given this measure, a rate-distortion-complexity theory is obtained by extending earlier work in alphabet-constrained rate-distortion theory. Numerical results show that operation on the alphabet-constrained rate-distortion bound can be obtained with a complexity of two. Furthermore, Lloyd-Max conditions are shown to describe the minimum of a slightly constrained version of the rate-distortion-complexity problem. Complexity-constrained design methods are applied first to trellis-coded quantizers, where they are shown to reduce arithmetic operations by at least 25%. They are then used to develop model-based trellis quantizers, the trellises of which are derived from a Markov model of the source. Simulation results confirm that excellent performance can be obtained with modest complexity     

Simplified trellis decoder

A new simplified trellis decoder (STD) Viterbi-type algorithm is proposed for fast trellis decoding of rate K/K+1 binary convolutional codes. Viterbi algorithm (VA) computation is dominated by add-compare-select (ACS) operations when k⩾2. The STD can substantially reduce the number of ACS operations and allow for a trade-off between the computational load and the performance of the decoder, The STD is analyzed and simulated for a four-dimensional (4-D) rate 4/5 64-state convolutional encoder specified by the ITU-T V.34 modem recommendation     

8-PSK trellis codes for a Rayleigh channel

A suboptimal trellis coding approach based on the concept of combining a good convolutional code and bit interleavers is presented. The aim is to improve the reliability of digital radio communication over a fading channel. It is shown that over a Rayleigh channel and for a fixed code complexity the proposed system is superior to the baseline system. Its performance is analyzed using the generalized R_o and the upper bound on the bit error rate. The results suggest that on a Rayleigh channel, the standard trellis codes may not be the correct approach for improving the reliability of the communication channel. The discussion is restricted to a rate 2/3 coded system with 8-PSK modulation     

Designing lexicographic codes with a given trellis complexity

We generalize constructions of lexicographic codes to produce locally optimal codes with a desired trellis decoding complexity. These constructions are efficient for high-rate codes and provide a means for automated code design. As a byproduct, we improve known bounds on the parameters of lexicodes     

Variable-rate trellis source encoding

The fixed slope lossy algorithm derived from the kth-order adaptive arithmetic codeword length function is extended to finite-state decoders or trellis-structured decoders. When this algorithm is used to encode a stationary, ergodic source with a continuous alphabet, the Lagrangian performance converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of auxiliary random variables and reproduction levels, where λ>0 and -λ are designated to be the slope of the rate distortion function R(D) of the source at some D; the quantity is close to R(D)+λD when the order k used in the arithmetic coding or the number of states in the decoders is large enough, An alternating minimization algorithm for computing the quantity is presented; this algorithm is based on a training sequence and in turn gives rise to a design algorithm for variable-rate trellis source codes. The resulting variable-rate trellis source codes are very efficient in low-rate regions. With k=8, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Gaussian sources is comparable to that afforded by trellis-coded quantizers; with k=8 and the number of states in the decoder=32, the mean-squared error encoding performance at the rate 1/2 bits/sample for memoryless Laplacian sources is about 1 dB better than that afforded by the trellis-coded quantizers with 256 states, with k=8 and the number of states in the decoder=256, the mean-squared error encoding performance at the rates of a fraction of 1 bit/sample for highly dependent Gauss-Markov sources with correlation coefficient 0.9 is within about 0.6 dB of the distortion rate function     

Universal trellis coded quantization

A new form of trellis coded quantization based on uniform quantization thresholds and "on-the-fly" quantizer training is presented. The universal trellis coded quantization (UTCQ) technique requires neither stored codebooks nor a computationally intense codebook design algorithm. Its performance is comparable with that of fully optimized entropy-constrained trellis coded quantization (ECTCQ) for most encoding rates. The codebook and trellis geometry of UTCQ are symmetric with respect to the trellis superset. This allows sources with a symmetric probability density to be encoded with a single variable-rate code. Rate allocation and quantizer modeling procedures are given for UTCQ which allow access to continuous quantization rates. An image coding application based on adaptive wavelet coefficient subblock classification, arithmetic coding, and UTCQ is presented. The excellent performance of this coder demonstrates the efficacy of UTCQ. We also present a simple scheme to improve the perceptual performance of UTCQ for certain imagery at low bit rates. This scheme has the added advantage of being applied during image decoding, without the need to reencode the original image.     

Robustly good trellis codes

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     

Super-orthogonal space-time trellis codes

We introduce a new class of space-time codes called super-orthogonal space-time trellis codes. These codes combine set partitioning and a super set of orthogonal space-time block codes in a systematic way to provide full diversity and improved coding gain over earlier space-time trellis code constructions. We also study the optimality of our set partitioning and provide coding gain analysis. Codes operating at different rates, up to the highest theoretically possible rate, for different number of states can be designed by using our optimal set partitioning. Super-orthogonal space-time trellis codes can provide a tradeoff between rate and coding gain. Simulation results show more than 2-dB improvements over the codes presented in the literature while providing a systematic design methodology.     

An eight-dimensional trellis code

An 8-state trellis code is described that uses a signal constellation from the 8-dimensional Gosset lattice E8. It can be used for example to transmit data at 9.6, 14.4, and 19.2 kbits/s with a nominal coding gain of close to 6 dB.     

Finite-state trellis representation of CPM

In most of the literature it is claimed that the number of phase states in CPM is equal to q if p is even, and 2q if p is odd, where the modulation index h=p/q. It is shown that a simple assumption due to Fornery (1973) leads to a simplified finite-state representation and also that CPM has q phase states.<>     

Algorithmic construction of trellis codes

An algorithmic approach is proposed whereby long convolutional codes of rate r_c=k/n can easily be constructed for any chosen signal constellation in signal space. These algorithms are iterative, and in each step a number of candidate codes are found which locally maximize the distance (Hamming or Euclidean) between the codewords. The result is not necessarily a free-distance-optimizing code. However, since the construction complexity can be chosen, optimal codes are quite frequently found. The codes ae constructed such that a rapid growth of the column distance is achieved. A method of combining two codes into a single code of twice the constraint length is also presented     

On trellis codes with a delay processor and a signal mapper

It is already known that a trellis code T, which is constructed by using the encoder of a convolutional code C with short constraint length followed by a delay processor and a signal mapper, is equivalent to a trellis code with large constraint length. In this paper, we derive a new lower bound on the free distance of T, which, in some cases, is better than the previously derived bound. Moreover, instead of the decoding used in earlier publications, we apply iterative decoding on both tailbiting and zero-tail representations of T to take advantage of the new lower bound and, in the meantime, to decrease the associated error coefficient caused by the decoding used in earlier publications. Comparisons among various designs of such a trellis code and some well-known coding methods are also provided.     

Channel-optimized soft trellis waveform coding

We provide a new fuzzy relaxation trellis codebook search algorithm over noisy channels. The new algorithm solves the problems associated with the LBG algorithm in the sense of delivering relatively lower distortion configurations using short training sequences. Furthermore, the new approach is significantly less sensitive to the initialization process. The algorithm minimizes a weighted distortion measure averaged over both the source and the channel statistics. The weights are soft distortion-related reliability information, which are delivered by a soft trellis vector quantization algorithm (STVQ). The concept of soft compression is introduced by Haddad and Yongacoglu (see Proc. GLOBECOM, Rio de Janeiro, Brazil, Dec. 1999) in another paper, using the forward-backward symbol-MAP algorithm. The work introduced in this paper is an extension of the work established for the noiseless channel case by Haddad and Yongacoglu (see Proc. IEEE ICASSP, Istanbul, Turkey, June 2000) in yet another paper. Testing is performed using first- and second-order Gauss-Markov sources over several trellis structures, vector dimensions, and compression rates. Moreover, the robustness of the optimal configurations is tested under channel-mismatch conditions and compared with tandem coding systems.     

Efficient maximum likelihood decoding of linear block codes using a trellis

It is shown that soft decision maximum likelihood decoding of any(n,k)linear block code overGF(q)can be accomplished using the Viterbi algorithm applied to a trellis with no more thanq^{(n-k)}states. For cyclic codes, the trellis is periodic. When this technique is applied to the decoding of product codes, the number of states in the trellis can be much fewer thanq^{n-k}. For a binary(n,n - 1)single parity check code, the Viterbi algorithm is equivalent to the Wagner decoding algorithm.     

Assembled space-time turbo trellis codes

A novel full rate space-time turbo trellis code, referred to as an assembled space-time turbo trellis code (ASTTTC), is presented in this paper. For this scheme, input information binary sequences are first encoded using two parallel concatenated convolutional encoders. The encoder outputs are split into four parallel streams and each of them is modulated by a QPSK modulator. The modulated symbols are assembled by a predefined linear function rather than punctured as in the standard schemes. This results in a lower code rate and a higher coding gain over time-varying fading channels. An extended two-dimensional (2-D) log-MAP (maximum a posteriori probability) decoding algorithm, which simultaneously calculates two a posteriori probabilities (APP), is developed to decode the proposed scheme. Simulation results show that, under the same conditions, the proposed code considerably outperforms the conventional space-time turbo codes over time-varying fading channels.     

On entropy-constrained trellis coded quantization

An entropy-constrained trellis coded quantization (TCQ) scheme is presented for encoding memoryless sources. A simple 8-state trellis is used to encode the memoryless Gaussian source with mean-squared-error (MSE) performance within about 0.5 dB of the rate-distortion function. This performance is achieved at all non-negative encoding rates     

Performance of trellis codes for a class of equalized ISI channels

The performance of trellis codes is examined for a class of intersymbol interference (ISI) channels that occur in high-frequency radio systems. The channels considered are characterized by in-band spectral nulls and by a rapid time variation. The baseline modulation technique is 4QAM (four-point quadrature amplitude modulation). When spectral nulls are absent, performance of fractionally spaced linear equalizers and trellis decoders is found to be near ideal and to be better than using symbol-spacing in the equalizer. However, error propagation in the feedback path, resulting from equalizer-based decisions, ruins the performance of the combination of decision-feedback equalizers and trellis decoders when spectral nulls are present. Their performance can be improved by using fractionally spaced feedforward equalizer sections and by designing the decoder to compensate for ISI. Rate 2/3 codes are found to outperform rate 1/2 codes in error performance