Joint source channel coding

Scientific foundations: Frame expansions

Key words: Wavelet transforms, filter banks, oversampled frame expansions, error correcting codes, multiple description coding.

Signal representation using orthogonal basis functions (e.g., DCT, wavelet transforms) is at the heart of source coding. The key to signal compression lies in selecting a set of basis functions that compacts the signal energy over a few coefficients. Frames are generalizations of a basis for an overcomplete system, or in other words, frames represent sets of vectors that span a Hilbert space but contain more numbers of vectors than a basis. Therefore signal representations using frames are known as overcomplete frame expansions. Because of their inbuilt redundancies, such representations can be useful for providing robustness to signal transmission over error-prone communication media.

Consider a signal x. An overcomplete frame expansion of x can be given as Fx where F is the frame operator associated with a frame OF={oi}i in I , oi's are the frame vectors and I is the index set. The i-th frame expansion coefficient of x is defined as (Fx)i= < oi,x>, for all i in I. Given the frame expansion of x, it can be reconstructed using the dual frame of OF which is given as OF={(FhF)-1oi}i in I. Tight frame expansions, where the frames are self-dual, are analogous to orthogonal expansions with basis functions.

Frames in finite-dimensional Hilbert spaces such as RK and CK, known as discrete frames, can be used to expand signal vectors of finite lengths. In this case, the frame operators can be looked upon as redundant block transforms whose rows are conjugate transposes of frame vectors. For a K-dimensional vector space, any set of N, N > K, vectors that spans the space constitutes a frame. Discrete tight frames can be obtained from existing orthogonal transforms such as DFT, DCT, DST, etc by selecting a subset of columns from the respective transform matrices. Oversampled filter banks can provide frame expansions in the Hilbert space of square summable sequences, i.e., l2(Z). In this case, the time-reversed and shifted versions of the impulse responses of the analysis and synthesis filter banks constitute the frame and its dual.

Since overcomplete frame expansions provide redundant information, they can be used as joint source-channel codes to fight against channel degradations. In this context, the recovery of a message signal from the corrupted frame expansion coefficients can be linked to the error correction in infinite fields. For example, for discrete frame expansions, the frame operator can be looked upon as the generator matrix of a block code in the real or complex field. A parity check matrix for this code can be obtained from the singular value decomposition of the frame operator, and therefore the standard syndrome decoding algorithms can be utilized to correct coefficient errors. The structure of the parity check matrix, for example the BCH structure, can be used to characterize discrete frames. In the case of oversampled filter banks, the frame expansions can be looked upon as convolutional codes.

New results

Overcomplete frame expansions for joint source-channel coding

Contributed by: Christine Guillemot, Slavica Marinkovic, Gagan Rath.

Overcomplete frame expansions have been introduced recently as signal representations that would be resilient to erasures in communication networks. Unlike the traditional signal representations with orthogonal bases, here a signal is represented by an overcomplete set of vectors that has some desirable reconstruction properties. The redundancy inherent in the representation is exploited to protect the signal against unwanted channel degradations. Therefore the frame expansions can be looked upon as joint source-channel codes. Redundant block transforms such as those obtained from DFT, DCT, and DST matrices can be seen as producing discrete frame expansions in finite dimensional real or complex vector spaces whereas oversampled filter banks can be seen as providing frame expansions in l2(Z).

Oversampled filter bank (OFB) frame expansions can be viewed as a generalization of the overcomplete signal expansions by redundant block transforms. That is, block transforms can be seen as filter banks with a zero order polyphase description. Increasing the polyphase filter order adds memory to the code and an OFB can be interpreted as a convolutional code over the real or complex field. With discrete frame expansions, the associated redundant transforms or, equivalently, the frame operators, can be interpreted as the generator matrices of some real or complex block codes. Therefore such frame expansions can be characterized based on the properties of the parity check matrices of the associated codes, such as the BCH structure. We observed that the frame expansions associated with low-pass DFT, DCT and DST codes possess this structure and thus can be utilized to correct coefficient errors and erasures.

The traditional BCH decoding or syndrome decoding approach is based on the concept of an error locator polynomial to localize the errors. However, the analogy between the DOA estimation in array signal processing and the error localization with quantized discrete frame expansions gives rise to newer decoding schemes. We have derived some subspace based approaches to error localization that are applicable to the discrete frame expansions characterized by the BCH structure. The algorithms follow the eigendecomposition of syndrome covariance matrices, estimate the eigenvectors which span the error and the noise subspaces, and then estimate the error locations from the noise subspace eigenvectors. We observed that these decoding approaches improve the error localization efficiency over the syndrome decoding depending on the number of coefficient errors.

The above approaches apply to block transforms with a BCH structure, however cannot be easily applied to oversampled filter bank (OFB) based frame expansions. The problem of decoding OFB codes can be viewed as a problem of decoding real-number convolutional codes in presence of impulse noise errors and background noise. In addition, in contrast to finite-field convolutional codes, real numbered convolutional codes have infinite state-space size and therefore Viterbi algorithm can not be applied. We have thus developed an error localization procedure relying on hypothesis testing. The syndrome decoding algorithm consists of two steps: error localization and error correction. The error localization problem is treated as an $M$-ary hypothesis testing problem. The tests are derived from the joint probability density function of the syndromes under various hypothesis of impulse noise positions and in a number of consecutive windows of the received samples (to account for the encoding memory of the convolutional code). The error amplitudes are then estimated from the syndrome equations by solving them in the least square sense. The message signal is reconstructed from the corrected received signal by a pseudoinverse receiver. The performance of this algorithm has been first tested for a Bernoulli Gaussian impulse noise model. We have then considered an image compression system with a complete encoding chain consisting of an OFB based signal decomposition, scalar quantization and a variable length entropy code (VLC) or a fixed length code (FLC). The noise due to errors at the output of the VLC/FLC decoder (input of the OFB syndrome decoder) has been modelled as a Bernoulli-Gaussian or a quantizer-dependent impulse noise. The error localization procedure for the quantizer-dependent impulse noise model has been developed. We have further shown how the soft information at the output of the soft-input-soft-output (SISO) VLC/FLC decoder can be used in the localization procedure of the OFB syndrome decoder. The localization procedure has been further improved by introducing in the localization procedure of the OFB decoder per symbol reliability information produced by the SISO VLC/FLC decoder. The a posteriori probabilities of the source symbols produced by y the SISO VLC/FLC decoders are used in the calculation of the hypothesis a priori probabilities. The performance of these algorithms has been tested in the system with a tree structured subband decomposition by a wavelet filter bank and a Huffman or an FLC. The results show that introducing the soft information in the localization procedure of the syndrome decoding algorithm significantly improves the probability of detection and decreases the mean square error. We have further proposed an algorithm for the iterative decoding of the OFB-FLC chain. In this algorithm, the trellis for the decoding of the FLC encoded source coefficients modeled by the first order Markov source is iteratively pruned with the help of the hypothesis a posteriori probabilities. This is done based on the information on the symbols for which errors have been detected in the OFB syndrome decoder. The performance of these algorithms has been tested in the image compression system based on the subband decomposition by a wavelet filter bank.

Error-resilient source codes

Contributed by: Christine Guillemot, Herve Jegou

Entropy coding, producing Variable Length Codes (VLCs), is a core component of any multimedia compression system (image, video, audio). The main drawback of VLCs is their high sensitivy to channel noise: bit errors may lead to dramatic decoder desynchronization problems. Most of the solutions known so far to address this problem consists in re-augmenting the redundancy of the compressed stream, e.g. using redundant source codes, synchronization markers, or channel codes. In 2002, we have designed a new family of codes, that we called multiplexed codes, which have the property of avoiding the dramatic desynchronization problem while still allowing to reach the entropy of the source. The idea underlying multiplexed codes builds upon the observation that most media compression systems generate sources of different priority. The design principle consists in creating fixed length codes (FLCs) for high priority information and in using the inherent redundancy to describe low priority data, hence the name ``multiplexed codes''. The redundant set of FLCs is partitioned into equivalence classes according to high priority source statistics. The cardinality of each class, according to the high priority source statistics, is a key element so that the code leads to a description length as close as possible to the source entropy. This class of codes has been extended so that higher-order source statistics are exploited. The error-resilience, for the high priority source, is expressed analytically as a function of the indexes assigned to the different codewords. The formulation is in turn used as a criterion in index assignment algorithms based on the binary switching algorithm or making use of simulated annealing.

Strategies for error resilient and progressive transmission of classical VLCs (in particular of Huffman codes) have also been designed. These bitstream construction (BC) approaches allow to improve the error-resilience of the code, even when using simple hard decoding techniques. The performance can be further improved by using MAP, MPM or MMSE estimators. In contrast with solutions proposed so far in the litterature, the solutions designed have a linear complexity. The resulting bitstream structure is amenable to progressive decoding. The design of a progressive expectation-based decoding approach led to the introduction of code properties and design criteria for increased resilient and progressive decoding criteria. The VLC code has to be designed so that the symbol energy is mainly concentrated on the first bits of the symbol representation (i.e. on the first transitions of the corresponding codetree). This energy distribution criterion is used in the design of codes and in the corresponding index assignment.

Finally, another family of codes, called self-multiplexed codes and introduced in 2003, has been generalized. The generalization is based on the fact that a VLC based on a binary codetree can be seen as a set of re-writing rules of the form

ai --> b1...bn,

where ai in A is a symbol of the source alphabet A and b1...bn in {0,1}*. Using this formalism, self-multiplexed codes can be regarded as the set of codes defined by a set of re-writing rules of the form

ai b1...bm --> b1...bn,

with m < n. Self-multiplexed codes can be further generalized to the set of codes defined by a set of re-writing rules of the form

ai s1...sm --> b1...bn,

where (s1...sm) in {0,1}*. This class of codes naturally extends codes based on binary codetrees and encompass codes which can be regarded as finite state automata including quasi-arithmetic codes. This extension introduces additional degrees of freedom in the index assignment, allowing to improve the decoder resynchronization properties and the code performance in a context of soft decoding.

Joint source-channel decoding of variable length codes

Contributed by: Christine Guillemot, Thomas Guionnet, Marion Jeanne, Pierre Siohan.

Arithmetic codes are now widely introduced in practical compressions systems (e.g. JPEG-2000, MPEG-4 and H.264 standards). When coupled with higher-order source statistical models, they allow to reach high compression factors. However, they are very sensitive to the presence of noise (transmission errors). It is then essential to design algorihms that would allow robust decoding of such codes, even in presence of bit errors. Two algorithms have been designed: the first algorithm follows sequential decoding principles, in the spirit of the Fano algorithm used for decoding channel codes, with an extra difficulty here residing in the fact that transitions on the coding decision tree are associated to a varying number of bits. In order to control the decoder complexity, different pruning techniques have been designed. A validation of the approach in a JPEG-2000 decoder revealed a very significant gain with respect to standard decoding solutions (see Fig.7). The algorithm allows in addition to flexibly control the trade-off between the complexity represented by the parameter W in Fig.7 and the reliability of the estimation. This parameter corresponds to the maximum number of surviving paths: a higher value of surviving paths corresponds to a higher decoding complexity and a higher estimation reliability.

Figure 1. Impact of transmission errors on the visual quality (0.5 bpp). (a)JPEG-2000 coded; PSNR = 37.41 dB; no channel error.
(b)JPEG-2000 coded; AWGN channel (Eb/N0 = 5 dB), PSNR = 16.43 dB.
(c)JPEG-2000 coded, AWGN channel (Eb/N0 = 5 dB), W = 10, PSNR = 25.15 dB.
(d)JPEG-2000 with sequential decoding, AWGN channel (Eb/N0 = 5 dB), W = 20, PSNR = 31.91 dB.

Lena1 Lena2 Lena3 Lena4

A second decoding algorithm has been developed considering quasi-arithmetic codes. A quasi-arithmetic coder/decoder can be modelled as finite-state automata. MAP estimation algorithms (e.g. the BCJR or the soft output Viterbi algorithm) hence apply. The dimension of the state-space can be traded against some approximation of the source distribution. The approach turns out to be well suited for extra soft-synchronization and to be used in a source-channel iterative structure in the spirit of serial turbo codes. In 2003, the approach has been first validated in a JPEG-2000 decoder. The integrated solution revealed a very significant gain with respect to standard decoding solutions. The approach (patented) has been promoted within the JPEG-2000 standardization group and adopted within the part 11 of the standard dealing with JPEG wireless (JWL).

In 2004, effort has been dedicated to the validation of the solution in the context of context-based adaptive arithmetic coding used in the H.264 video coding standard and very likely to be used in the emerging MPEG-21 SVC (Scalable Video Coding) standard. The extra difficulty comes from the fact that both the encoder and the decoder learn the source statistics as long as the sequence of symbols is being encoded or decoded. A method for estimating the source HMM parameters from the noisy sequence of bits that is received in a robust manner needs to be designed. This is still under progress. The next step will be to promote the solution in the context of a core experiment on error resilience defined by the MPEG-21/SVC standardization group.

Joint source-channel coding for MIMO-based wireless systems

Contributed by: Robin Chatterjee, Christine Guillemot, Gagan Rath.

Theoretical studies show that the capacity of a wireless channel can be increased by using multiple antennas at both the transmitter and the receiver. Using such a multiple-input multiple-output (MIMO) antenna system with multiplexing of data however may not result in high reliability. One of the ways to improve the reliability is to use diversity in space and time where redundant data is transmitted from multiple antennas over time. The design of redundant data streams to be transmitted from different transmitting antennas over time is the subject of so-called space-time coding. Space-time coding as such is applied over the symbol stream where the symbols are signal constellation points for a given modulation scheme. The design of a space-time code is primarily based on the minimization of the probability of transmitting a codeword and decoding a different codeword at the receiver.

A space-time block codeword typically consists of original symbols and their complex conjugates. Such a block of symbols can be generated by incorporating redundancy at the higher levels of the communication system as well. For example, one could use a multiple description coding where different descriptions of the source signal can be transmitted from different transmitting antennas which would promise similar or better performance as using a space-time code. This problem thus can be looked upon as a joint source-channel coding problem aimed for MIMO-based communication system. Consider a MIMO wireless communication system with nt transmitting antennas and nr receiving antennas. In order to achieve high reliability, the source signal needs to be separated into nt redundant streams. Consider a source vector x consisting of K real-valued components. It can be expanded to Knt components using an overcomplete frame expansion as y=Fx, where F is a frame operator associated with a frame having Knt frame vectors in the K-dimensional space. The components of y can be split into nt vectors each having K components, and these vectors can be transmitted from nt transmitting antennas after being quantized and modulated. In this case, frame expansion builds redundancy into the system which is exploited as spatial diversity. It is known that certain frame expansions provide error correcting capabilities as well. Therefore, such a frame expansion can increase the reconstruction reliability further by correcting residual errors in the decoded coefficients. This design however brings up several questions:

To answer these questions, we need to investigate the proposed system both in theory and in simulation which is presently underway.

Webmaster: Valid CSS! Valid XHTML IRISA
Last time modified: 2006-02-20