**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 *F***x** where *F* is the
frame operator associated with a frame
*O _{F}={o_{i}}_{i in I}* ,

Frames in finite-dimensional Hilbert spaces such as
**R**^{K} and **C**^{K}, 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.,
*l*_{2}(**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.

**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
*l*_{2}(**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.

**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

*a _{i} --> b_{1}...b_{n}*,

where

with

where (

**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.

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.

**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
*n _{t}* transmitting antennas and

- Is this system better than the system with a space-time code in the sense of lower bit error rate or lower reconstruction error for the same SNR?;
- Are the encoding and decoding algorithms less complex than those with a space-time code?;
- What are the criteria for finding the optimal frame expansion?;
- What are the characteristics of the frame operator which leads to the optimal performance?;
- Is the optimal frame expansion related to the optimal space-time code for a given bit rate, and if so, how?

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