Trellis codes based on linear congruential recursions have recently been introduced as powerful source codes. For a modest computational complexity they offer excellent rate distortion performance at low to moderate quantization rates. In this work the bit error sensitivity of these codes is explored. The theoretical analysis shows that for a given number of trellis states the deviation from the correct trellis path, caused by bit errors on the transmission channel, can be described by two code parameters alone. The theoretic approach is compared to Monte-Carlo simulations and show that the particular trellis source codes under consideration offer robust transmission for bit error ratios up to the order of 10-3without the aid of any explicit correcting channel code.

Rate-distortion trellis source codes are developed for quantizing memoryless independent and identically distributed (i.i.d.) sources. The codes are generated by simple linear congruential recursions. The method generates codes at a variety of rates including fractional ones; reproducer sets can be large, a crucial advantage with certain sources. Axioms for good code construction are developed that are based on recursion properties and certain trellis symmetries. These axioms are justified by the outcome of random searches for good codes. It is found that the trellis code design breaks into two problems: the trellis labels should have certain properties regardless of the source distribution; and the reproducer values depend on the source. Encoders are simulated for a number of continuous amplitude sources. For the same computational complexity, the new codes, in most cases, perform better than the best codes in the literature, including trellis-coded quantization and fake process approaches.

The Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm is an important channel decoding method. We extend it to trellis rate-distortion data compression. Beginning from source coding principles, the derivation of the algorithm avoids channel coding or soft output ideas. The encoder does not use entropy coding; equiprobable reproducer letters are emphasized since these maximize entropy. The BCJR method is demonstrated by tests of a tail-biting variant. It performs much better than the ordinary Viterbi algorithm for short and medium blocks. However, the improvement stems from tail biting; the role of the BCJR is to achieve tail biting in a relatively simple way. Some issues that arise with tail biting are explored. It is shown that there is an optimal trellis state size for each block length.

We consider the lossy image compression problem and propose a model-residual approach. Polynomial basis images encode the model image and powerful new trellis codes quantize the residual part. A simple bit allocation scheme determines the residual bit rates and a variety of rates are attainable without entropy coding. The trellis structure is also used to form a joint source and channel coding scheme for the residual components. Results are shown for the 0.4-1.6 bits per pixel region. Comparisons are made to several state-of-the-art techniques and show that the proposed scheme is very competitive.

We consider the lossy image compression problem and propose a model-residual approach. Polynomial basis images encode the model image and powerful new trellis codes quantize the residual part. A simple bit allocation scheme determines the residual bit rates. Results are shown for the 0.4-1.6 bits per pixel region. Comparisons are made to several state-of-the-art techniques and show that the proposed scheme is very competitive

We motivate and discuss the logarithmic bit-significance ratio (S-value) which is a universal measure to quantify the significance of each bit in a digital communication system. Calculation rules for the S-values are given which, for instance, allow for the computation of the significances of parity bits when the significances of the data bits are given. The introduction of the S-value allows for the processing of soft-information, e.g., in encoding and modulation and can, hence, be interpreted as the transmitter-based counterpart of the well-established log-likelihood ratio (L-value) at the receiving end

Summary form only given. In this paper, we examine the effect of block size on the performance of trellis based quantization. In particular, the Viterbi and tailbiting BCJR algorithms are compared. It is shown that for short blocks of data, the T-BCJR algorithm achieves a superior performance over the Viterbi algorithm (VA). One approach is to use the maximum a posteriori probability (MAP) heuristic and the T-BCJR algorithm. If the MAP-encoder does not produce a tailbiting state sequence, the path is modified for a number of stages at the beginning and end of the block such that it tailbites. The enclosed figure shows MSE as a function of block size and sample position, respectively, for a rate R=1 bit per sample, 32-state trellis quantizer and an IID Gaussian source. The effects of start-up are clearly visible. For the T-BCJR algorithm, the distortion is evenly distributed across the whole block. The performance decrease for short blocks stems from the increase in the number of tailbiting violations for short blocks and the suboptimal modification to ensure tailbiting. The results presented here hold for a large class of trellis constructions, such as TCQ.

We present two methods for variable-rate trellis quantization. Both methods utilize trellis codes based on linear congruential (LC) recursions. LC code trellises have good pseudo-random properties and are easily adapted to serve reconstruction alphabets of different sizes. The first method finds an entropy-constrained code only by optimizing over a scale factor. The scale factor modifies an initial reproducer alphabet in order to skew the associated set of codeword lengths. Using a Lagrangian formulation and the maximum a posteriori (MAP) heuristic, we also develop an entropy-constrained trellis quantizer suitable for short blocks of data. Here the tailbiting BCJR algorithm is used to find the MAP path in the trellis. Simulation results for the Gaussian and Laplacian distributions show that the proposed method is competitive with the best in the literature.

The BCJR algorithm is an important method of channel decoding. We extend it here to rate-distortion encoding. The arguments begin from source coding principles and make no use of channel coding or soft output ideas. An important role is played by codeword ensembles with equiprobable reproducer letters. The BCJR method is demonstrated by tests of a tailbiting BCJR with the Gaussian source. The outcome improves Viterbi algorithm performance at short and medium blocklengths

This paper presents new methods trellis source coding at rates above and below one. The new schemes have in common a code design based on branch correlation, a large reproducer alphabet, and an encoder based on either the Viterbi algorithm or a tailbiting MAP technique. The methods are easily adapted to various bit rates, but here only the results for R = 2 and R = 1/2 bits per source sample are presented. Results, demonstrated for the memoryless Gaussian source, show similar or better performances than previous methods with similar coding complexity.

Two new kinds of fractional-rate trellis source codes based on linear congruential recursions are evaluated. Properties of good codes are given. Square error distortion is similar to or better than competing schemes.

New trellis constructions for compression of short data sequences are presented. Traditional low rate trellis source coding suffer from having a too small reproduction alphabet. Governed by alphabet-constrained rate-distortion theory a simple method was proposed for a source coding rate of 1 bit per sample that allows 2/sup m/ reconstruction values for a trellis with 2/sup m/ states. The proposed method is based on the maximum a posteriori probability criterion distortion measure and it employs tailbiting. Tailbiting makes the method suitable also for short data sequences. Simulation results are compared to TCQ-like methods.

Summary form only given. BCJR based source coding of image residuals is investigated. From a trellis representation of the residual, a joint source-channel coding system is formed. Then the BCJR algorithm is applied to find the MAP encoding. MAP and minimized squared error encoding are compared. The novelty of this work is the use of the BCJR algorithm and the MAP criterion in the source coding procedure. The source encoding system described preserves more features than an MSE based encoder. Also, blocking artifacts are reduced. Comparisons may be found in the full paper version (see http://www.it.lth.se/tomas/eriksson/spl I.bar/novak/spl I.bar/anderson/spl I.bar/dcc02.ps, 2001).