Francesca Bassi

Michel Kieffer

Claudio Weidmann

WYNER-ZIV CODING WITH UNCERTAIN SIDE INFORMATION QUALITY

The robustness of the coding scheme against variations of the side information quality is determinant to the performance of distributed source coding applications. Relatively few works, however, investigate this issue by an information theoretic perspective. Wyner-Ziv coding with uncertain side information quality is defined here introducing a Gaussian-mixture model for the correlation noise. The analysis of the theoretical rate-distortion performance is presented, along with a coding solution not relying on the presence of a feedback channel. The attainable performance of the coding scheme is derived, and a brief discussion on implementation issues concludes the paper.

INTRODUCTION

The major interest Wyner-Ziv coding has raised in recent years is due to its suitability to emerging applications such as wireless sensor networks [START_REF] Xiong | Distributed source coding for sensor networks[END_REF] and distributed video coding [START_REF] Girod | Distributed video coding[END_REF]. Investigation on practical solutions began with the contribution of DISCUS [START_REF] Pradhan | Distributed source coding using syndromes (DISCUS): design and construction[END_REF], and spread in the last decade producing innumerable works (see [START_REF] Dragotti | Distributed Source Coding, Theory, Algorithms and Applications[END_REF] for a survey). The main issue in practical design is, as emphasized in [START_REF] Westerlaken | The role of the virtual channel in distributed source coding of video[END_REF], the robustness of the scheme against the variations in time of the side information quality, which are usually not captured by the underlying theoretical model, but strongly affect the performance. The classical approach to the problem is the attempt to track the instantaneous quality of the correlation channel: either introducing a feed-back link, thus enabling rate adaptation [START_REF] Aaron | Wyner-Ziv video coding with hash-based motion compensation at the receiver[END_REF], or allowing the encoder to access previously transmitted data to facilitate the estimation of the correlation noise level [START_REF] Puri | PRISM: a video coding paradigm with motion estimation at the decoder[END_REF].

Relatively few works investigate the information theoretical consequences of distributed compression with uncertain side information quality. Heegard and Berger [START_REF] Heegard | Rate distortion when side information may be absent[END_REF] and Kaspi [START_REF] Kaspi | Rate-distortion function when side-information may be present at the decoder[END_REF] considered the event that the side information might be absent at the decoder, without the encoder being aware. Recent works by Verdú and Weissman [START_REF] Verdú | The information lost in erasures[END_REF] and Perron et al. [START_REF] Perron | Lossy source coding with Gaussian or erased side-information[END_REF] address the evaluation of the Wyner-Ziv rate-distortion function when the side information either is a noiseless copy of the source or is erased. The authors in [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF][START_REF] Weidmann | Practical distributed source coding with impulse-noise degraded side information at the decoder[END_REF] introduced a different correlation model, where the side information is a copy of the source affected by background noise and, occasionally, by additive noise impulses. The decoder is uninformed of the state of the correlation channel, whereas in the Wyner-Ziv setup for possibly erased side information [START_REF] Verdú | The information lost in erasures[END_REF][START_REF] Perron | Lossy source coding with Gaussian or erased side-information[END_REF][START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF] the receiver is assumed capable of detecting the occurred erasure.

This work generalizes the correlation model presented in [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF][START_REF] Weidmann | Practical distributed source coding with impulse-noise degraded side information at the decoder[END_REF] and outlines a theoretical framework for the analysis of Wyner-Ziv coding with uncertain side information quality. The instantaneous state of the correlation channel is described by means of a hidden random variable; the probability density function of the correlation noise results in a Gaussian mixture, with weighting coefficients determined by the state probability distribution.

After derivation of lower and upper bounds to the Wyner-Ziv rate-distortion function a coding architecture not relying on the F. Bassi is also with DEIS, Università di Bologna, Italy. This work was partly supported by the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM++.

presence of a feedback channel is proposed. Its attainable performance is characterized, and implementation details are discussed in the concluding section.

MODEL AND THEORETICAL BOUNDS

The standard Gaussian Wyner-Ziv setup [START_REF] Wyner | The rate-distortion function for source coding with side information at the decoder[END_REF] considers the compression of a memoryless source X ∼ N (0, σ 2 X ), when the side information Y ∼ N (0, σ 2 Y ) is available at the decoder. The correlation of the jointly Gaussian pair (X, Y ) is modeled by a virtual channel Y = X + Z, where Z ∼ N (0, σ 2 Z ) is independent additive noise. The model can be generalized by assuming the variance σ 2

Z as varying with time. The instantaneous state of the correlation channel is described by a random variable S, taking values in the alphabet

S = {0, 1, . . . , T -1}. The set S is mapped one-to-one onto R = {σ 2 0 , σ 2 1 , . . . , σ 2 T -1 }, where σ 2 s < σ 2 s+1
, so that the realization S = s represents the event of correlation noise with variance σ 2 s . Let ps = Pr(S = s). The probability density function fZ(z) of the correlation noise Z is the Gaussian mixture

fZ(z) = T -1 s=0 ps fZ|S=s(z) = T -1 s=0 ps √ 2πσ 2 s exp - z 2 2σ 2 s . (1)
Gaussian-mixture models are a widely deployed technique for the estimation of the probability density function of real random signals [START_REF] Escobar | Bayesian density estimation and inference using mixtures[END_REF]. A wide range of correlation channels can be approximated by a suitable choice of the number of components, of their variances, and of their mixing weights ps. Without loss of generality examples and coding schemes will be discussed in detail only for a twocomponent mixture, introduced in [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF] as the Gaussian-Bernoulli-Gaussian (GBG) model, given by S = {0, 1}, R = {σ 2 0 , σ 2 1 }, p1 = p and p0 = (1p). Section 2.1 explores quantization with decoder side information; a limit-achieving quantizer is derived, for future use in Section 2.2.

High-rate quantization with decoder side information

Wyner-Ziv coding can be understood as a quantization problem. The decoder side information helps in the reconstruction of the source, and allows to compress the quantization alphabet through Slepian-Wolf coding, which plays the same role as entropy coding in the standard quantization problem. Necessary conditions for the existence of limit-achieving Wyner-Ziv quantizers are derived in [START_REF] Dragotti | Distributed Source Coding, Theory, Algorithms and Applications[END_REF][START_REF] Rebollo-Monedero | High-rate quantization and transform coding with side information at the decoder[END_REF]. We provide here the following result, along with a brief sketch of the proof. A system composed by a dithered lattice quantizer [START_REF] Zamir | On universal quantization by randomized uniform/lattice quantizers[END_REF] followed by an ideal Slepian-Wolf chain satisfies the conditions in [START_REF] Dragotti | Distributed Source Coding, Theory, Algorithms and Applications[END_REF][START_REF] Rebollo-Monedero | High-rate quantization and transform coding with side information at the decoder[END_REF], and hence is Wyner-Ziv optimal, as the length n of the source sequence X grows towards infinity. The rate of the dithered lattice quantizer with side information at the decoder is derived mirroring the proof for standard quantization in [START_REF] Zamir | On universal quantization by randomized uniform/lattice quantizers[END_REF], and is expressed, in bits per sample, as

Rq = 1 n h(X |Y ) - 1 n log 2 V (Λ) , (2)
where V (Λ) is the volume of the fundamental Voronoi cell of Λ.

As n → ∞ the shape of the best tessellation associated with Λ approaches an Euclidean ball, and the second moment approaches σ 2 (Λ) = V (Λ)

2 n /2πe. Substitution into (2) yields

Rq = Rq σ 2 (Λ) = h(X|Y ) - 1 2 log 2 2πeσ 2 (Λ) . (3)
The second moment σ 2 (Λ) represents the quantization noise variance per sample. Under high-hate assumption σ 2 (Λ)/σ 2 s → 0, so that the optimal source reconstruction X is the quantized value of the source. Under the Mean Square Error (MSE) distortion constraint D ≤ E (X -X) 2 the scheme yields per sample distortion D = σ 2 (Λ). Substitution in (3) completes the proof.

Rate-distortion bounds

The Wyner-Ziv rate-distortion function is defined as

R WZ X|Y (D) = min (f U |X ,F D )∈M(D) I(X; U ) -I(Y ; U ) ( 4
)
where U is the auxiliary random variable, and M(D) is the set of all probability density functions fU|X and matched reconstruction functions

FD : U × Y → X satisfying the distortion constraint E[(X -X) 2 ] ≤ D.
The Wyner-Ziv rate-distortion function is known in closed form only in very few cases: for binary source with binary symmetric correlation channel and for Gaussian source with Gaussian additive correlation channel [START_REF] Wyner | The rate-distortion function for source coding with side information at the decoder[END_REF], and for discrete sources with erasure correlation channel [START_REF] Verdú | The information lost in erasures[END_REF][START_REF] Perron | Lossy source coding with Gaussian or erased side-information[END_REF]. In order to characterize the analytical form of (4) for uncertain side information quality we introduce the bounds

R WZ X|Y (D) ≤ R WZ X|Y (D) ≤ R WZ X|Y (D). (5)
The lower bound R WZ X|Y (D) is determined as the best performance achievable by a genie-aided system, where the genie informs both the encoder and the decoder of the realization of S. The genie-aided system works in time-division regime, matching the best achievable performance associated with the event S = s, given by the Gaussian Wyner-Ziv rate-distortion function for correlation noise of variance σ 2

s . Like for the compression of parallel Gaussian sources [START_REF] Cover | Elements of Information Theory[END_REF], the system has to satisfy the same distortion constraint D for each transmission instant, under the high-rate assumption

D < σ 2 x σ 2 0 (σ 2 x + σ 2 0 ) . (6)
If [START_REF] Aaron | Wyner-Ziv video coding with hash-based motion compensation at the receiver[END_REF] holds it is

R WZ X|Y (D) = T -1 s=0 ps 1 2 log 2 σ 2 x σ 2 s (σ 2 x + σ 2 s )D . ( 7
)
The upper bound R WZ X|Y (D) under the assumption ( 6) is determined as the achievable performance of a system composed by a lattice dithered quantizer Λ followed by an ideal Slepian-Wolf coding chain. Under the hypothesis n → ∞ the rate Rq of the lattice quantizer with side information at the decoder is obtained from (3)

Rq = h(X|Y ) - 1 n log 2 2πeσ 2 (Λ) ≤ h(X|Y, S) - 1 2 log 2 2πeσ 2 (Λ) + H(S), (8)
where ( 8) is obtained developing I(X; S|Y ). Expressing the differential entropy in (8) as h(X|Y, S) =

T -1 s=0 ps h(X|Y, S = s) and replacing σ 2 (Λ) with D finally yields the upper bound

R WZ X|Y (D) = T -1 s=0 ps 1 2 log 2 σ 2 x σ 2 s (σ 2 x + σ 2 s )D + H(S). (9)

THEORETICAL CODING SCHEME

The blindness of both the encoder and the decoder to the realization of S prevents, in the uncertain side information quality setup, any attempt to perform rate-adaptation: the system is forced to operate at constant rate. The simplest solution is obtained employing a standard Gaussian Wyner-Ziv coding scheme, dimensioned for the worst-case quality over the correlation channel, i.e. S = T -1.

The system is clearly suboptimal, since rate loss is experienced for any event S = T -1. The loss becomes smaller as the variances of the components in (1) tend to be similar, vanishing as σ 2 s → σ 2 s+1 , ∀s ∈ S, while it dramatically impacts the performance when the correlation noise presents occasional high-variance impulses, so that σ 2

T -1 ≫ σ 2 s and pT-1 < ps, ∀s ∈ S. The alternative coding solution proposed here still relies on fundamental coding blocks optimized for the Gaussian correlation model, but allows to restrain the rate loss also in the most penalizing case. The coding architecture is based on two layers, where suboptimality is confined on Layer 1. The Layer 1 coding chain is exploited to produce a first, rough estimate of the source, regarded as Gaussian side information for the optimal (in the Wyner-Ziv sense) transmission on Layer 2. The two-layer coding approach has been first proposed in [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF] for the case of possibly erased side information. In [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF] Layer 1 conveys the syndrome of a real-field code, used to correct the degraded side information sequence; the decoding process relies on the availability of the erasure pattern at the receiver side. The same solution cannot be employed here, due to the blindness of the decoder to S: an alternative coding scheme (depicted in Figure 1) needs to be designed. The remainder of this section derives its asymptotically achievable rate-distortion performance.

Encoding

The coding scheme works on the sequence X of n source symbols. Let L be an [n × n] orthonormal matrix. The rank m matrix Φ consists of a selection of m ≤ n rows of L; similarly, the rank (nm) matrix Φ is obtained from the remaining (nm) rows, so that

L = P Φ Φ (10)
with P a permutation matrix. The source X is multiplied at the encoder side by Φ and Φ, generating the Layer 1 sequence ΦX and the Layer 2 sequence ΦX . Since X is i.i.d. Gaussian, it has a spherically symmetric distribution, which is not affected by the rotation through L. The sequences ΦX and ΦX are selections of m and (n-m) components of LX respectively, hence the distribution of their symbols can be modeled as Gaussian with variance σ 2

x . The encoder performs vector quantization of the Layer 1 and Layer 2 sequences by means of the dithered lattice quantizers Λ1 ∈ R m and Λ2 ∈ R (n-m) , generating ΦX + N 1 and ΦX + N 2. The quantization indexes are ideally Slepian-Wolf compressed and sent to the receiver. The per source sample rates R1 and R2 are evaluated, using (2), as

R1 = 1 n h(ΦX |ΦY ) - 1 n log 2 V (Λ1) (11)
R2 = 1 n h(ΦX |Φ X ) - 1 n log 2 V (Λ2) , ( 12
)
where X is the output of the Layer 1 decoder, and ΦY and Φ X are the Slepian-Wolf side information sequences for Layer 1 and Layer 2, respectively. Since the sequences ΦX and ΦX have correlated components, in general it is h(ΦX |Y ) ≤ h(ΦX |ΦY ) and h(ΦX | X ) ≤ h(ΦX |Φ X ). It can be proved, however, that equality holds if the pair (X , X ) is jointly Gaussian, hence no loss is introduced on Layer 2 employing Φ X as Slepian-Wolf side information (see [START_REF] Bassi | Wyner-ziv coding with uncertain side information quality[END_REF]). Assuming Layer 1 decoder output X as composed by identically distributed Gaussian symbols of variance σ 2 X -D ′ , Figure 1: Two-layer coding scheme for Wyner-Ziv coding with uncertain side information quality.

and (X , X ) a jointly Gaussian pair, (12) yields the Layer 2 transmission rate as

R2 = (n -m) 2n log 2 σ 2 X D ′ (σ 2 X + D ′ )σ 2 (Λ2) . ( 13
)
In order to determine R1 characterization of the noise ΦZ = ΦY -ΦX is needed. The sequence ζ = ΦZ is composed of m statistically dependent symbols where the convolution product is possible because the random variables (φj,izi|si) are independent. Since (φj,izi|si) is normally distributed, (15) results in

ζj = φj Z = n i=1 φj,i zi, ∀j ∈ {1, 2, . . . , m}. (14)
fj(ζj) = s πs 1 √ 2πσ 2 s exp - ζ 2 j 2σ 2 s , (16)
where the variance σ 2 s is given by

σ 2 s = n i=1 φ 2 ji σ 2 Z i |s . ( 17
)
The j-th element of the noise sequence ΦZ is marginally distributed as a Gaussian mixture, where the variances of the components depend on the associated rows φ j of Φ. This implies that some rate loss is induced by the use of ΦY as the Slepian-Wolf side information at the Layer 1 decoder. Assuming the linear transform matrix L in [START_REF] Verdú | The information lost in erasures[END_REF] to be a Discrete Cosine Transform (DCT) matrix, it is

φi,j = 2 n cos (2j -1)(i -1) n π 2 ≤ 2 n , ∀(j, i). ( 18
) Define σ 2 z = T -1 s=0 ps σ 2 s .
As n → ∞ the properties of typical sequences assure that S contains close to n ps elements S = s, ∀s ∈ {0, 1, . . . , T -1}. Using [START_REF] Cover | Elements of Information Theory[END_REF] in [START_REF] Zamir | On universal quantization by randomized uniform/lattice quantizers[END_REF]

allows to bound σ 2 s with σ 2 s ≤ 2 n n i=1 σ 2 Z i |s = 2 n T -1 s=0 n ps σ 2 s = 2σ 2 Z . (19)
The ideal Slepian-Wolf chain in Layer 1 is designed to guarantee vanishing probability of error in the worst-case scenario, that is when the variance of the correlation noise between ΦX and ΦY equals 2σ 2 Z . Thus [START_REF] Perron | Lossy source coding with Gaussian or erased side-information[END_REF] becomes

R1 = m 2n log 2 σ 2 X 2σ 2 Z (σ 2 X + 2σ 2 Z ) σ 2 (Λ1) . (20)
The rate loss induced on Layer 1 transmission chain is thus due to the worst-case policy in protection against Slepian-Wolf decoding errors, and to the choice of ΦY as Slepian-Wolf side information sequence. The penalty ascribable to the former, however, is restrained by the effect of the linear transformation Φ, which determines similar probability density function [START_REF] Rebollo-Monedero | High-rate quantization and transform coding with side information at the decoder[END_REF] for each ζj, with mixtures made of components with comparable variances.

Decoding

The decoder operates in two steps. The Layer 1 Slepian-Wolf index is decoded to recover the quantized sequence ΦX +N 1, where N 1 is the quantization noise composed, under the assumption n → ∞, by independent Gaussian symbols with variance σ 2 (Λ1). The Layer 1 decoder outputs the estimate X of the source, to be employed in the second step to decode the Layer 2 Slepian-Wolf index. The estimate X output of the overall system is derived from the joint observation of ΦX + N 1, ΦX + N 2 and Y .

The Layer 1 estimator operates on the observed sequences ΦX + N 1 and Y . The system is described as

Ω = Φ In X + N 1 Z = AX + W . (21)
The MMSE estimator of X from the observation Ω = ω is

x(ω) = E X |ω = R n x fX|ω(x) dx, (22)
where the conditional density f X |ω can be developed as

fX|ω = s Pr(S = s|ω) fX|s,ω. (23)
Using ( 23) in ( 22) yields the expression of the estimate as

x(ω) = s Pr(S = s|ω) xs(ω, s), ( 24
)
where xs(ω, s) is, by definition, the MMSE estimate of the source sequence obtained from the observation vector Ω = ω, when the realization of the state sequence S = s is available at the decoder. Since (X , Ω|S = s) are, by construction, jointly Gaussian, the MMSE estimate xs(ω, s) has linear form

xs(ω, s) = K -1 X + A T K -1 W |s A -1 A T K -1 W |s ω, (25)
where KW |s is the covariance matrix of the observation noise when s is available. The estimate x(ω), although expressed as a combination of the linear estimates xs(ω, s), is not linear with ω, since the weighting coefficients in (24) have expression

Pr (S = s|ω) = fΩ|s(Ω = ω|s) Pr(S = s)

s fΩ|s(Ω = ω|s) Pr(S = s) . ( 26
)
The MSE vector M at the output of Layer 1 estimator is defined by

M = diag Cov X -x(Ω) = diag KX -EΩ x(Ω) x(Ω) T , (27)
whose analytical expression cannot be evaluated. The performance of the Layer 1 estimator is upper bounded by the performance of the suboptimal LMMSE estimator, whose expression is

M L = diag K X -K X Ω K -1 Ω K ΩX = diag σ 2 x σ 2 z σ 2 x + σ 2 z In - σ 2 x σ 2 z ∆1 Φ T Φ , (28)
with ∆1 = σ 2 x σ 2 z + σ 2 (Λ1) + σ 2 z σ 2 (Λ1).
Consider, as before, the linear transform matrix L to be a DCT matrix, and assume n odd; the rows (n -1)/2j and (n + 1)/2 + 1 + j of L are symmetric. Proper choice of the pairs of rows for the construction of Φ guarantees that Φ T Φ has equal diagonal elements, of value m/n. The expression of the per sample distortion D ′ on the output of the Layer 1 decoder is, from (28),

D ′ = σ 2 x σ 2 z σ 2 x + σ 2 z 1 - m n σ 2 x σ 2 z ∆1 , (29)
and depends on the length n only through the ratio m/n. The Layer 2 estimator operates on the observed sequences ΦX + N 1, ΦX + N 2 and Y . The system is described as

Ω ′ = Φ Φ In X + N 1 N 2 Z = A ′ X + W ′ . (30)
As for the Layer 1 estimator the optimal reconstruction is the weighted sum of the MMSE estimates xs(ω ′ , s), obtained from the observation Ω ′ = ω ′ when the realization S = s is available at the decoder side

x(ω ′ ) = s Pr(S = s|ω ′ ) xs(ω ′ , s), (31)
with xs(ω ′ , s) linear function of ω ′ , since (X , Ω ′ |S = s) are jointly Gaussian. The MSE vector M ′ is obtained as

M ′ = diag Cov X -x(Ω ′ ) (32)
and can be upper bounded by the performance of the suboptimal LMMSE estimator

M L ′ = diag K X -K X Ω ′ K -1 Ω ′ K Ω ′ X = diag σ 2 x σ 2 z σ 2 x + σ 2 z In - σ 2 x σ 2 z ∆1 Φ T Φ - σ 2 x σ 2 z ∆2 Φ T Φ , (33)
-GBG correlation model, σ 2 X = 1, p = 0.1, σ 2 0 = 0.04, σ 2 1 = 1.
where

∆2 = σ 2 x σ 2 z + σ 2 (Λ2) + σ 2 z σ 2 (Λ2).
The per sample distortion D at the output of the system is evaluated as

D = σ 2 x σ 2 z σ 2 x + σ 2 z 1 - m n σ 2 x σ 2 z ∆1 - (n -m) n σ 2 x σ 2 z ∆2 , (34)
and depends only on the ratio m/n. Remark that (29) and (34) express only upper bounds to the minimum distortions D ′ and D achievable by the scheme. They allow, however, to describe the operational rate-distortion performance (R1 + R2, D) as a function of the design parameters m/n, σ 2 (Λ1) and σ 2 (Λ2), thus enabling design parameter optimization. The key feature of the two-layer architecture is the shift of (nearly) all suboptimality arising from the uncertainty of the side information quality over Layer 1. Transmission over the Layer 1 is expensive, so that it is convenient to restrain the ratio m/n. On the other hand the quality of the Layer 1 estimate, which provides consistent rate savings on Layer 2, increases with m/n as well: a trade off between the two conflicting requirements exists, which determines the optimum performance. Figure 2 shows, in red, the asymptotic (for n → ∞) achievable performance of the coding scheme, evaluated for the GBG correlation model of parameters σ 2 X = 1, p = 0.1, σ 2 0 = 0.04, σ 2 1 = 1. The optimum value of the ratio m/n is, in high rate regime, constant, and equals m/n = 0.216. The achievable performance is compared with the lower (solid line) and upper (dashed line) bounds to R WZ X|Y (D), and with the performance of the standard Wyner-Ziv coding scheme, dimensioned for the worst correlation noise (yellow line).

TOWARDS PRACTICAL IMPLEMENTATION

The two-layer coding architecture here proposed can be understood as a theoretical tool for the design of Wyner-Ziv coding schemes for uncertain side information quality. Remark that the fundamental components of the coding scheme are represented by quantizers, and Slepian-Wolf coding chains for constant side information quality. Highly efficient Slepian-Wolf coding implementations are by now available, as the result of the extensive research effort of the last decade (a state-of-the-art survey can be found in [START_REF] Dragotti | Distributed Source Coding, Theory, Algorithms and Applications[END_REF]). The purpose of this section is to focus on the implementation issues related to Layer 1 and Layer 2 estimators only.

The optimum Layer 1 (24) and Layer 2 (31) estimators are defined, as detailed in the previous section, as weighted sums of the marginal (with respect to the realization of S) estimates. This clearly represents an obstacle to implementation, since the number of marginal estimates xs and xs to be evaluated grows exponentially with the size n of the source block. The weighting coefficients Pr(S = s|ω) and Pr(S = s|ω ′ ) associated with each marginal estimate pair xs and xs represent the likelihoods of the state sequence realization s, given the observation vectors ω and ω ′ : among them, only a small fraction have a significant value, and concentrates (almost) the totality of the a posteriori probability. A and performing the sums in ( 24) and (31) over the subspace W * , instead that over the entire vector space where S lives.

The solution adopted to evaluate the set W * is derived adapting the Bayesian Matching Pursuit algorithm [START_REF] Schniter | Fast Bayesian matching pursuit: model uncertainty and parameter estimation for sparse linear models[END_REF], originally proposed to solve the problem of compressed sensing of sparse sources. The algorithm performs a tree search in order to identify the elements s * ∈ W * ; on each exploration level the surviving leaves (the state sequences s * ) are selected as the ones maximizing Pr(S = s|ω). The root of the tree is represented by the sequence s composed by all zero elements. The descent to the following level of the tree is performed activating one impulse position at a time. The M (d) elements surviving at depth d and are employed to generate the following level.

The algorithm has been implemented and tested for the GBG correlation model, for the same mixture parameters considered before. Figure 3 presents the simulation results obtained on Layer 1 estimator, where the choice of the design parameters m/n, σ 2 (Λ1) and σ 2 (Λ2) results from the performance optimization procedure for n → ∞. The black line in Figure 3 represents the value of the distortion D ′ at the output of Layer 1 estimator obtained with the optimization procedure. The light-blue and blue lines depict the distortions obtained using the Bayesian Matching Pursuit algorithm, for block lengths (n = 14, m = 3) and (n = 28, m = 6) respectively: they consistently improve the theoretical distortion value D ′ . This should not surprise: the analytical expression (29), in fact, represent the attainable, but non minimum, distortion D ′ . The simulation results enable the conclusion that the optimization of the design parameters obtained for n → ∞ is to be considered effective for finite-length design as well.

CONCLUSIONS

This paper outlines a theoretical framework for Wyner-Ziv coding with uncertain side information quality. The proposed coding scheme inherits the two-layer approach presented in [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF] for the case of possibly erased side information. The blindness of the decoder to the actual state over the correlation channel, however, makes impossible to adopt the coding strategy devised in [START_REF] Bassi | Source coding with intermittent and degraded side information at the decoder[END_REF]. The Bayesian approach proposed here allows to account for all the possible realizations of the hidden state variable, thus overcoming the problem. The attainable performance of the scheme can be analytically characterized and compared to the theoretical bounds, showing that the coding solution is effective.

Denote

  πs = Pr(S = s) = n i=1 ps i . The marginal probability density function fj(ζj) is given by fj(ζj) = s πs f (ζj|s) (15) = s πs f (φj,1z1|s1) * . . . * f (φj,nzn|sn) ,

Figure 2 :

 2 Figure 2: Performance of the coding scheme -GBG correlation model, σ 2 X = 1, p = 0.1, σ 2 0 = 0.04, σ 2 1 = 1.

Figure 3 :

 3 Figure 3: Layer 1 estimator, BMP implementation -GBG correlation model, σ 2 X = 1, p = 0.1, σ 2 0 = 0.04, σ 2 1 = 1. reliable approximation of the estimates x (24) and x (31) can thus be obtained by identifying the set W * of the sequences S|ω such as

Acknowledgments

The authors would like to thank Phil Schniter for the fruitful discussions on the Fast Bayesian Matching Pursuit algorithm and its application to Wyner-Ziv coding with uncertain side information quality.


J B Leger

M Kieffer
email: kieffer@lss.supelec.fr

GUARANTEED ROBUST DISTRIBUTED ESTIMATION IN A NETWORK OF SENSORS

Keywords: Bounded-error estimation, distributed estimation, interval analysis, network of sensors, outliers, robust estimation

This paper proposes a guaranteed robust bounded-error distributed estimation algorithm. It may be employed to perform parameter estimation from data collected in a network of wireless sensors. The algorithm is robust to an arbitrary number of outliers. Using interval analysis, one is able, provided that the network is connected, to evaluate at each sensor, an outer approximation of the set of all parameter values which are consistent with a given number of measurements, and with noise bounds. An application to a robust distributed source localization problem is considered.

INTRODUCTION

A network of wireless sensors (NWS) is a set of autonomous devices, with limited computing capability and autonomy, exchanging information via a wireless channel. Various types of sensors may be considered, e.g., for measuring pressure, temperature, sound, vibration, motion... Many applications (environment monitoring, home automation, traffic control) may take advantage of NWS, see, e.g., [START_REF] Kay | The design space of wireless sensor networks[END_REF][START_REF] Haenselmann | GFDL Wireless Sensor Network textbook[END_REF].

Challenging problems arise when considering parameter or state estimation using measurements provided by a NWS. Two main types of estimation techniques may be considered. In centralized approaches, all measurements obtained by the sensors are transmitted to a central processing unit (CPU), see, e.g., [START_REF] Sheng | Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks[END_REF]. Many data have then to be send to a given point of the network. Moreover, this solution is not robust to a failure of the CPU, since the estimate is only available at that point of the network. Alternative distributed estimation techniques for constant [START_REF] Degroot | Reaching a consensus[END_REF] and time varying parameters [START_REF] Cattivelli | Diffusion recursive least-squares for distributed estimation over adaptative networks[END_REF][START_REF] Cattivelli | Diffusion strategies for distributed kalman filtering: Formulation and performance analysis[END_REF] have been provided. In this case, each sensor is responsible for the processing of its measurement and of data provided by neighboring sensors. An increased robustness to failure of the CPU is thus obtained.

Nevertheless, distributed solutions may not be very robust against erroneous measurements provided by some defective sensors. Albeit robust estimators have been proposed in a centralized context, using bounded-error estimation [START_REF] Jaulin | Guaranteed robust nonlinear parameter bounding[END_REF] or linear programming [START_REF] Picard | Accurate geolocalization in the presence of outliers using linear programming[END_REF], the extension of these techniques to a distributed context is far from being trivial.

This paper considers distributed bounded-error estimation in a NWS [START_REF] Kieffer | Centralized and distributed source localization by a network of sensors using guaranteed set estimation[END_REF]. Measurement noise is assumed to be bounded with known This work has been partly supported by the NEWCOM++ Network of Excellence.

bounds, and one aims at evaluating the set of all values of the parameter vector which is consistent with the measurements and the bounds on the measurement noise. It provides a guaranteed and robust estimator in a distributed context using interval analysis [START_REF] Jaulin | Applied Interval Analysis[END_REF]. By guaranteed, it is meant that no parameter value consistent with a fixed number of measurements is missed.

Section 2 recalls the robust bounded-error parameter estimation problem in a NWS. The centralized approach is described in Section 3 to provide a reference to the distributed approach presented in Section 4. Implementation issues are considered in Section 5 before providing simulation results in Section 6.

PROBLEM FORMULATION

Consider a network of N sensors spread in an environment. The aim is to provide the estimation of an unknown parameter vector p * ∈ P using measurements yi, i ∈ 1, N provided by each sensor of the network. The measurement yi is assumed to be linked to p * via the measurement model

yi = fi(p * ) + ei i ∈ 1, N (1)
where ei is assumed to remain in some known interval vector (box) [e, e]. Introducing [yi] = yi -[e, e], one has

fi(p * ) ∈ [yi] i ∈ 1, N . (2)
Bounded-error parameter estimation [START_REF] Walter | Special Issue on Parameter Identification with Error Bounds[END_REF][START_REF]Bounding Approaches to System Identification[END_REF] aims at characterizing the set S0 of all parameter values which are consistent with the measurements, the measurement model, and the bounds on the measurement noise, i.e.,

S0 = {p ∈ P|∀i ∈ 1, N , fi(p) ∈ [yi]} . (3)
When they are some outliers, e.g., in the case of a defective sensors, for some measurements, the noise may not remain in its bounds, S0 may be then empty. In such situations, one may define a set estimator for p robust to q outliers as follows

Sq = {p ∈ P|λ(p) ≥ N -q} (4)
where

λ(p) = N i=1 I [y i ] (fi(p)) (5)
and

IA(x) = 1 if x ∈ A 0 else (6)
Guaranteed inner and outer approximations S q and Sq of Sq may be obtained for any value of q using interval analysis [START_REF] Jaulin | Applied Interval Analysis[END_REF], provided that all measurements are collected at a CPU, to which all measurements yi and models fi have been transmitted. By guaranteed, it is meant that one is able to numerically prove that in P \ Sq, all values of the parameter vector are inconsistent with at least q + 1 measurements, and that in S q , all values of the parameter vector are consistent with at least N -q measurements. The aims of this paper is to propose a distributed robust bounded-error estimator, i.e., to provide an estimation algorithm which is able to evaluate at each sensor i of the network an outer approximation Sq,i of Sq using only a subset of the measurements available in the network. The aim is to be robust to a failure of the CPU, to compute at each sensor of the network partial estimates with a only subset of the measurements, and if possible, to reduce the amount of data exchanged within the network. In what follows, the network is assumed to be entirely connected, i.e., any sensor of the NWS is able to exchange information with any other sensor, in one or several hops.

ROBUST CENTRALIZED APPROACH

In this approach, all sensors send their measurements and measurement functions to a central processing unit. The robust boundederror approach presented in [START_REF] Jaulin | Guaranteed robust nonlinear parameter bounding[END_REF] is briefly recalled here to serve as reference of the distributed approach detailed in Section 4.

The robust estimator is based on the notion of inclusion function, introduced by interval analysis [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF][START_REF] Jaulin | Applied Interval Analysis[END_REF]. Consider a function f :

D ⊂ R α -→ R β , an inclusion function [f ] for f has to be such that ∀[x] ⊂ D [f ] ([x]) ⊃ f ([x]) . (7)
The natural inclusion function is a inclusion function obtained by replacing all occurrences of the variable x in the formal expression of f (x) by the interval counterpart [x]. It allows to compute an outerapproximation of the range of f over any interval [x] ⊂ D. For more details, see [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF][START_REF] Jaulin | Applied Interval Analysis[END_REF].

Assuming that an inclusion function [λ] for λ in ( 5) is available, one may use the SIVIA algorithm [START_REF] Jaulin | Set inversion via interval analysis for nonlinear bounded-error estimation[END_REF] to evaluate an inner approximation S q and an outer approximation Sq of Sq consisting of unions of non-overlapping boxes of P. S q and Sq are initialized as ∅.

Starting with a working LIFO list W of boxes to be processed, initially containing the box [p]0 = P, SIVIA extracts a box [p] from W and applies the following tests.

-

If [λ]([p]) ⊂ [N -q, N
], then all parameters in [p] are consistent with at least N -q measurements or more and [p] is stored in S q and Sq.

-

If [λ]([p]) ⊂ [0, N -q[,
then all parameters in [p] are not consistent with q + 1 measurement or more, and

[p] is dropped. -If the size of [p] is larger than some parameter ε, [p] is bisected into two subboxes [p] and [p] , which are stored in W. -If the size of [p] is smaller than ε, it is stored into Sq.
One of the interesting feature of this approach is that it is not necessary to specify a priori the sensors which are defective. Only the number q of erroneous data the estimator has to be robust to has to be specified. The approach considered by GOMNE [START_REF] Jaulin | Guaranteed robust nonlinear parameter bounding[END_REF] consists in starting with q = 0 and increasing q until a non-empty solution set S q is obtained. Note that with this approach, the solution set S q is only guaranteed to contain the true parameter value p * if the number of outliers is actually less than q. In what follows, the NWS is assumed to be entirely connected, i.e., each sensor is able to exchange information with any other sensor of the network, in one or several hops.

IDEALIZED ROBUST DISTRIBUTED APPROACH

In this context, each sensor has to process its own measurement and information transmitted by neighboring sensors. One aims at characterizing Sq in a guaranteed way, as in the centralized approach.

Consider the subset of measurement indexes J ⊂ 1, N , and define the set

S J q = I⊂J,card(I)=card(J)-q i∈I Pi , (8)
of all parameters consistent with card(J) -q or more measurements provided by sensors with index in J, with where Pi = {p ∈ P|fi(p) ∈ [yi]}, the set of parameters consistent with the measurement provided the sensor i and card(A), the cardinal number of the set A. One may easily verify that Sq = S 1,N q and

∀J1 ⊂ J2 ⊂ 1, N S J 1 q ⊃ S J 2 q ⊃ Sq (9)
Assume that a sensor has evaluated S J 1 q and that S J 2 q has been provided by one of its neighbors. According to 9, to obtain a better outer-approximation of Sq, the sensor has to compute S J 1 ∪J 2 q . If J1 ∩ J2 = ∅, there is no simple relation between S J 1 q ∩ S J 2 q and S J 1 ∪J 2 q . Now, if J1 ∩ J2 = ∅, one may easily prove that S J 1 q ∩ S J 2 q ⊃ S J 1 ∪J 2 q , but both sets are not equal in general. In fact, to compute S J 1 ∪J 2 q , all S J 1 0 , . . . , S J 1 q and S J 2 0 , . . . , S J 2 q are needed, see Appendix A.1. Thus, each sensor has to transmit S J 0 , . . . , S J q in place of only S J q . For any subset of indexes J ⊂ 1, N , consider the set Γ J q = S J 0 , S J 1 , • • • , S J q , see Figure 1. In what follows, sensors send and receive such sets, and try to compute Γ 1,N q to obtain S 1,N q = Sq. The number of tolerated outliers q is assumed to be fixed a priori.

S J 0 S J 1 S J 2 Fig. 1. Representation some set Γ J 2 = S J 0 , S J 1 , S J 2
Initially, each sensor i processes its own measurement, to get Pi and Γ {i} q = (Pi, P, • • • , P). Then, it broadcasts this first estimate to its neighboring sensors and receives similar structures. After a first round of communication, the i-th sensor is able to improve its estimates as follows. If J1 ∩ J2 = ∅ (combination constraint), then Γ J 1 q and Γ J 2 q can be used to get Γ J 1 ∪J 2 q by computing each S J 1 ∪J 2 q as ∀q ∈ 0, q

S J 1 ∪J 2 q = q 1 +q 2 =q S J 1 q 1 ∩ S J 2 q 2 , (10)
see Appendix A.1.

For the next round of communication, each sensor broadcasts the best Γ J q (with the largest card(J). Once all sensors have exchanged improved estimates, new improvements are possible. The two phases (estimation and communication) may be performed until convergence, i.e., until all sensors have obtained S 1,N q = Sq, which occurs in finite time the proof is not provided here due to lack of space). Computations may also be stopped at any time, each sensor of the network having an outer-approximation of Sq, which improves when more data are exchanged.

IMPLEMENTATION ISSUES

In Section 4, sets such as S J q are assumed to be transmitted. This is not possible in general, since the shape of such sets may be quite complex. Here, external approximations S J q are considered, in order to be able to determine a guaranteed outer approximation of the solution Sq. Such outer-approximation may consists of any simple geometric shape, such as ellipsoids, polytopes, or unions of nonoverlapping boxes or subpavings [START_REF] Jaulin | Applied Interval Analysis[END_REF], which are considered here.

A single subpaving of P can be used to represent Γ J q . A subpaving may be easily described by a binary tree. Each leaf of the tree has to be labeled with to indicate that the corresponding box is a subset of S J . This subpaving implementation of Γ as labeled binary trees, allows computation for each sensor to becomes only unions and intersections of subpavings.

Each node stores intermediate results with

Γ J q = S J 0 , S J 1 , • • • , S J q
in place of Γ J q and transmitted to neighboring nodes. Efficient routing protocols, such as Optimized Link State Routing Protocol [START_REF] Clausen | Optimized link state routing protocol for ad hoc networks[END_REF], may be used to satisfy the recombination constraint more easily. The node of the network use multipoint distribution relays (MPR) for transmission. For a given node, only a subset of its neighbors relay its message. The selection of MPRs is adaptive and done in real time. For more details, see [START_REF] Clausen | Optimized link state routing protocol for ad hoc networks[END_REF]. We impose here a dynamic hierarchical structure where a sensor selects his MPRs and sends his sets Γ only to its MPRs.

EXPERIMENTAL PART

A simple single source localization in a 2D-environment with a NWS is considered, see Figure 2. A network of 9 regularly-spaced nodes is considered. Each sensor measures the power it receives from the source. All measurement errors are bounded: for a received power yi by the i-th sensor, the noise-free measurement is assumed to belong to the interval [y] = [ y w , yw] with w = 1.7. Two outliers are introduced by hand, concerning Sensors 4 and 6. The

where (θ1 i , θ2 i ) is the location of the sensor i, and where d(P1, P2) is the distance between P1 and P2. Moreover, P0 = 1 and η = 2 are assumed to be known. For a number of outliers q ∈ {0, 1, 2}, the centralized robust bounded-error estimator for (θ1, θ2) provides the results represented in Figure 2. In distributed approach, Figure 3 describes the estimates obtained by the 4-th sensor. The sets of Γq are outer approximation of sets of Γq.

Increasing the number of nodes of the network, one may evaluate the evaluation of the number of iterations required until convergence, see Figure 4. The complexity seems to be linear with the number of sensors.

CONCLUSION

This paper introduces a guaranteed robust bounded-error distributed estimation algorithm. This algorithm is robust to any number q of outliers. It is able to provide at each sensor of the NWS an outerapproximation of the set of all values of the parameter vector which are consistent with all except q measurements, or more, the model structure and the noise bounds. It is not ,necessary to specify a priori the measurements which are deemed as outliers.

The number of outliers the estimator has to be robust to has to be specified a priori. If labeled trees are used to represent subpavings, themselves used to describe Γ, exchanged between sensors, the complexity of these structures is not affected by the value of q. The complexity of the algorithm has to be evaluated more carefully. The sets Γ are quite complex, and their transmission may require some resources. One could imagine an alternative way to provide a robust estimator by exchanging measurements within clusters, and

A. PROOFS

For a node i of a WSN of N nodes, consider L1(i) ⊂ 1, N , the set of all indexes of sensors which are directly connected to i. One chooses

L0(i) = {i}. Then, for any k ∈ 1, N the set L k (i) = L k-1 (i)∪( s∈L k-1 (i) L1(s)
) contains all indexes of sensors which can communicate i with k communication or less. Assuming that the network is fully connected translates into

∀i ∈ 1, N ∃d ∈ N L d (i) = 1, N . (12)

A.1. Computation rule

Considering J1 ⊂ 1, N and J2 ⊂ 1, N , with J1 ∩ J2 = ∅, one aims at proving [START_REF] Jaulin | Applied Interval Analysis[END_REF]. For that purpose, take some q ∈ 0, N . First consider p ∈ q 1 +q 2 =q S J 1 q 1 ∩S J 2 q 2 . There exists (q1, q2) ∈ 1, N 2 with q1 + q2 = q , and with p ∈ S J 1 q 1 ∩ S J 2 q 2 . Then p ∈ S J 1 q 1 and p ∈ S J 2 q 2 . One may also find I1 ⊂ J1 and I2 ⊂ J2, with card(I1) = card(J1) -q1, card(I2) = card(J2) -q2, and with p ∈ ∩i∈I 1 Pi and p ∈ ∩i∈I 2 Pi. Since J1∩J2 = ∅, then I1∩I2 = ∅, and card(I1 ∪ I2) = card(J1) -q1 + card(J2) -q2 = card(J1 ∪ J2) -q . Now, take I = I1 ∪ I2 ⊂ J1 ∪ J2, then p ∈ i∈I Pi with card(I) = card(J1 ∪ J2) -q , and one has

p ∈ I ⊂ J1 ∪ J2 card(I) = card(J1 ∪ J2) -q i∈I Pi (13)
Finally, p ∈ S J 1 ∪J 2 q and q 1 +q 2 =q S J 1 q 1 ∩ S J 2 q 2 ⊂ S J 1 ∪J 2 q . Second, take p ∈ S J 1 ∪J 2 q . There exists I ∈ J1 ∪ J2 such that p ∈ i∈I Pi, and card(I) = card(J1 ∪ J2) -q . Consequently, there exists I1 ⊂ J1 and I2 ⊂ J2 with I1 ∪ I2 = I.

One has then p ∈ S J 1 q 1 and p ∈ S J 2 q 2 and q1 + q2 = q . Finally, p ∈ q 1 +q 2 =q S J 1 q 1 ∩ S J 2 q 2 .

Fig. 2 .

 2 Fig. 2. Considered network of 9 sensors (blue) and one source (red) (a); Solution obtained using a centralized estimation technique for q = 0 (b), q = 1 (c), and q = 2 (d); all plots are in [-2, 2] 2

Fig. 3 . 2 ( 2 =

 322 Fig. 3. Estimates Γ J 2 available at the 4-th sensor using the proposed distributed estimator, with S J 0 in dark-red, S J 1 in red, and S J 2 in lightred, all represented in the box [-2, 2] 2 ; initial estimate Γ {4} 2 (a), Γ {4,5} 2 (b), Γ {2,4,5,6,8} 2 (c) , and final estimate Γ 1,N 2 = Γ2 (d)

Fig. 4 .

 4 Fig. 4. Evolution of convergence time with number of sensor

2

 2 Since J1 ∩ J2 = ∅, then I1 ∩ I2 = ∅. Let q1 = card(J1) -card(I1) and q2 = card(J2) -card I2. One has then q1 + q2 = card(J1) + card(J2) -(card(I1) + card(I2)) = card(J1 ∪ J2) -card(I1 ∪ I2) = card(J1 ∪ J2) -card(I) = q . So Pi card(I2) = card(J2) -q2


François Mériaux

Michel Kieffer

ROBUST IP AND UDP-LITE HEADER RECOVERY FOR PACKETIZED MULTIMEDIA TRANSMISSION

Keywords: Codes, Communication systems, Transport protocols, Redundancy, MAP estimation

Recently, Joint Source-Channel Decoding (JSCD) techniques have been proposed to improve the reception of multimedia contents transmitted over error-prone channels. These techniques take advantage of the redundancy left by the source coder and of bit reliability measures (soft information) provided by channel decoders to correct transmission errors. To be put at work, protocol stacks have to be made permeable to transmission errors in order to allow soft information to reach the upper protocol layers. For that purpose, headers have to be reliably estimated at each protocol layer. First results have been obtained for lower protocol layers (PHY and MAC) protected by CRCs. The aim of this paper is to extend these results to upper protocol layers (IP and UDP-lite) protected by checksums. As for CRCs, trellis-based decoding techniques may be employed for data protected by checksums. Nevertheless, specific tools have been proposed in this paper to reach a complexity-efficiency trade-off 1 .

INTRODUCTION

The delivery of multimedia contents over a bandlimited network requires the use of compression schemes to reduce the amount of data to transmit. Nevertheless, compressed data are highly sensitive to transmission errors: a single bit corrupted during its transmission may have heavy consequences on the full encoded content. To avoid such issue, contents which have to be transmitted through a network are packetized and protected with various error-correction and detection mechanisms. The basic protection is channel coding [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF], which adds redundancy to the information as it is sent over the physical channel. Another protection mechanism is included in the network architecture and its different layers protocols. For some of those layers, an error-detection code is added to the message to protect the header of the packet. These errordetection codes can be CRCs or checksums [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF][START_REF] Kurose | Computer Networking: A Top-Down Approach Featuring the Internet[END_REF]. At the receiver, these codes are used to decide whether the message is corrupted and if it is, the sender is asked to send again the packet, if possible.

Nevertheless, there are many live applications where packets cannot be sent again: broadcasting, voice over IP, etc. For the last few years, Joint Source-Channel Decoding techniques [START_REF] Duhamel | Joint Source-channel Decoding: A Cross-layer Perspective With Applications in Video Broadcasting[END_REF] have been proposed to deal with corrupted packets by correcting them using various sources of redundancy present in the whole coding and transmission chain. These techniques improve the decoding but as they treat the corrupted packets at the application layer, they require the network to be permeable to such erroneous packets. The current network architecture does not allow packets with corrupted headers to reach the application layer because of the error-detection codes.

In [?], a mechanism is proposed to allow the lower protocol layers (PHY and MAC) to be permeable to corrupted packets by using the CRCs in conjunction with inter-and intra-layer redundancy to correct the erroneous headers.

The main contribution of this paper is to extend the ideas in [?] to the IP and UDP-lite protocol layers. The headers of these layers are protected by checksums. As for CRCs, trellisbased decoding techniques [START_REF] Wolf | Efficient maximum-likelihood decoding of linear block codes using a trellis[END_REF] may be employed for data protected by checksums. Nevertheless, we propose specific tools have been proposed in this paper to reach a complexityefficiency trade-off.

The paper is organized as follow. We first explain the header correction mechanism, then we introduce an efficient way to reduce its complexity. Finally, we present the simulation context and the results of our method.

ROBUST RECOVERY HEADERS AT THE HIGHER LAYERS USING THE CHECKSUMS

MAP estimator for robust header recovery

By keeping the same formalism than in [?], consider a packet forwarded from a layer to layer + 1. This packet is composed of a payload and a header and in this header, some fields are protected by a checksum. We note r the vector containing the protected fields. Mny of these fields are unknown but as there are many sources of redundancy inter and intra-layer, some of them can ben known or predictable. We respectively note those vectors u, k and p and we have r = [k, p, u].

We also define the checksum vector c = (r), with being the -bit checksum evaluation function and we consider , the implicit information at the receiver which enables us to limit the search range of unknown fields. The soft information coming from are regrouped in the vector y = [y , y , y , y ], y ,y ,y and y respectively being the noisy values of the known, predictable, unknown and checksum fields.

Since the fields k and p are known or exactly predictable, the only remaining field to be estimated is u. This problem can be solved with a MAP estimator

ûMAP = arg max u (u | k, p, R, y , y ) (1)
After some derivations detailed in [?], one gets If we consider (u), the length in bits of the unknown vector u, 2 (u) possible combinations for u have to be considered. But, as (u) can be quite long, we cannot afford such a calculation complexity. That is why we use a trellis structure similar to the one described in [START_REF] Wolf | Efficient maximum-likelihood decoding of linear block codes using a trellis[END_REF] to compute (y | u). In our case, the rows of the trellis correspond to the different possible checksum values and each column of the trellis corresponds to one bit of the unknown sequence. Each bit of the unknown sequence offers two new possible checksum values to the existing ways. At the end of the trellis, we have the likelihood metrics of 2 (c) different possible sequences and their associated checksums.

ûMAP = arg max u (y | u) (y | (k, p, u)) (u | R) (2)
To compute (y | (k, p, u)), we just have to compare those checksums with y by the mean of a likelihood metric.

COMPLEXITY REDUCTION

Both IP and UDP checksums are coded over 16 bits, which means we have to work with a 2 16 rows trellis. But such a trellis requires a huge amount of calculation and we need to reduce its complexity. The solution proposed in [?] cannot be applied in our case as we cannot divide the checksum into several independent pieces.

From a 2 -bit checksum to a -bit checksum

As detailed in [START_REF] Braden | RFC 1071: Computing the Internet checksum[END_REF], for a given sequence it is possible to obtain its -bit checksum from its 2 -bit checksum. Let us consider 2 -bit words , ∈ [1, ]. One can divide each word into two -bit words such as the first one is made of the most significant bits from and the second one is made of the least significant bits from . We respectively note those words and and = × 2 + . One can write

( 2 ( 1 , ..., )) = ( 1 , 1 , ..., , ) (3)
Practically, once we have the 2 -bit checksum c 2 of a given sequence, we just do the 1's complement sum of of the most significant bits of c 2 with the least significant bits of c 2 to obtain the -bit checksum c of the same sequence. This property enables us to work with a -bit checksum rather than a 2 -bit one so the complexity of the sequence estimation is highly reduced. But the counterpart is that a -bit checksum is a worse protection than a 2 -bit one. The results of errors correction with this method are not as good as with the 2 -bits checksum, but we will see this in detail in section 4.2.

Computing the likelihood of the -bit checksum

When a data packet with 2 -bit checksum arrives at the receiver, we cannot directly compute the -bit checksum c associated to the sequence since we do not know the exact values of the 2 -bit checksum c 2 . Instead, we know the probability for each bit of c 2 to be a 1 or a 0, that is what is called the likelihood of c 2 and it is known due to the soft information. So what we can do is to calculate the likelihood ratio of c . The problem is : knowing the likelihood ratio of a 2 -bit checksum computed over a given sequence, what is the likelihood ratio of the -bit checksum computed over the same sequence?

To answer this question, we have to take a closer look at the relations between the bits of c and the bits of c 2 and for this, we introduce the following notations

•

, the probability for the ℎ bit of c 2 to be a 1, ∈ [0, 2 -1]. Reciprocally, we note , the probability for the ℎ bit of c 2 to be a 0.

• , ∈ [0, -1], the probability for the ℎ bit of c to be a 1 and the probability for the same bit to be a 0.

• , ∈ [0, -1], the probability to have a carry at the ℎ position of the 1's complement sum between the two mid-parts of c 2 . Reciprocally, is the probability not to have a carry at the same position.

Considering the i-th bit of c , we have two possibilities depending on whether there is a carry. If there is a carry, the bit is a 1 if both i-th and i+n-th bits of c 2 are 1 or both bits are 0. In the other case, if there is no carry from the precedent step, the i-th bit of c is a 1 if one of the i-th and i+n-th bits of c 2 is a 1 and the other is a 0. This gives us the following equations

⎧  ⎨  ⎩ 0 = -1 .( 0 + 0 ) + ¯ -1 ( 0 + 0 ) = -1 ( + + + ) +¯ -1 ( + + + ), ∀ ∈ [1, -1] (4
) In (4), the (and thus the ) terms are known since they are contained in the soft information, but the and remain unknown for the moment. To determine the value of the i-th carry, we have to consider two possibilities: either both i-th and i+n-th bits of c 2 are 1, or one of those bits is a 1 and the other a 0. In the first case, there is always a carry. In the second case, the i-th carry is only a 1 if the i-1-th carry is a 1 too. This enables us to write the following system of equations

{ 0 = -1 ( 0 + 0 ) + 0 = -1 ( + + + ) + + , ∀ ∈ [1, -1]
(5) The system ( 5) is made of equations and has unknown parameters , ∈ [0, -1]. It can be written as

Aq = b (6)
with

⎧              ⎨              ⎩ q = ( 0 , 1 , ..., -1 ) b = ( 0 . , 1 . +1 , ..., -1 . 2 -1 ) A = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 0 ⋅ ⋅ ⋅ 0 -0 -1 1 . . . . . . 0 0 -2 . . . . . . . . . . . . . . . . . . . . . 0 0 ⋅ ⋅ ⋅ 0 --1 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ and = + + + , ∀ ∈ [0, - 1
] from which q is easily obtained as

q = A -1 b (7)
Once q is known, we can use the values , ∈ [0, -1] in (4) in order to obtain , ∈ [0, -1].

A simplified trellis

Once the likelihood of the -bit checksum is known, we have to estimate the unknown sequence. As in Section 2.2, we use a trellis structure to do that. The only difference is that the trellis now has 2 rows instead of 2 2 . The number of calculations we have to make with the trellis is almost reduced by a factor 2 , the complexity is highly reduced. The only calculations we add with this process is the solving of ( 6) and have a complexity in 3 , which remains negligible compared to the factor 2 .

SIMULATION AND RESULTS

Context

Our simulation consists in sending packets through an AWGN channel and applying our algorithm to the packets with erroneous headers at the reception. We assume that a soft protocol stack is used at the lower layers, so that we deal with soft information at the IP and UDP-lite layers. The transparent network architecture presented in [START_REF] Lamy-Bergot | Content adaptive network aware joint optimization of wireless video transmission[END_REF] gives some insights on the way to transmit soft information between protocol layers. Moreover, the UDP-lite layer is set to only protect the header and in both IP and UDP-lite headers, some fields may be known or predictable. Here are the assumptions we made for those fields

• In UDP-lite, the Length field is considered as known since we know the way we use UDP-lite. The Terminal Port field is unknown but one can assume that a limited number of ports are used at the same time. In our case, it can only take 8 different values.

• In IP, The Version field is known since we assume we use IPv4. The Header Size field is considered as known.

The Type of Service field is also assumed to be known.

The Length field is considered as predictable as it can be obtained from the MAC layer. The first bit of the Flags field is reserved and set to 0, so it is known. The Protocol field is known as UDP is known to be the upper layer.

The remaining fields are all considered as unknown.

Results

At the receiver, we compare the HER (Header Error Rate) of the received packets for different values of the SNR. We compare three different decoders: the standard one which decodes the bits of the header sequence according to their likelihood ratio, our header-correcter decoder based on the redundancy included in the 16-bit checksum and the same decoder with reduced complexity as we explain in Section 3.2.

IP header correction

Figure 1 shows this comparison for the IP header. As expected, both proposed decoders show better results than the standard one. The one which bases its header correction on the 16-bit checksum always have the fewer HER, whereas the one with reduced complexity is always between the two other decoders in term of results. We explain this by the fact that when we work with the reduced complexity version, we turn the likelihood ratio of the real 16-bit checksum into a likelihood ratio of a corresponding 8-bit checksum. But this operation is not reversible, when we do this, we lose redundancy about the unknown sequence.

If we have a closer look at the uncorrected error patterns that remain after we tried to correct them, we clearly notice UDP-lite standard decoder UDP-lite 16-bit checksum correction Fig. 2. HER vs SNR for the standard and 16-bit header correcter decoders of the UDP-lite layer that there is no single bit error in the corrected sequence. This due to the checksum property of always detecting single bit error. The most common type of error appears when two bits separated by 15 (or 7 for the reduced complexity version) bits are both wrong but when added to each other, they do not change the checksum value. This kind of error is not detectable by our algorithm.

UDP-lite header correction

Figure 2 compares the performance of the standard decoder and the basic header-correcter decoder for the UDP-lite layer. Once again, our decoder has better results than the standard one and if we compare it with the same decoder at the IP layer, we notice that the results are even better. For a HER of 10 -2 , our UDP decoder needs 3.33 dB whereas the IP decoder needs 4.75 dB. We explain this observation by two facts. First, the length of the unknown sequence in the UDPlite header is smaller that the unknown sequence of the IP header. It is 32 bits instead of 39, there are fewer chances for errors to occur. Second, in the UDP-lite header, the Terminal Port field can only take a given number of values which correspond to the opened ports of the Terminal, which highly reduces the possible values for this field.

CONCLUSION AND PERSPECTIVE

By using the redundancy present in the checksum, the solution we propose enables us to make the upper protocol layers permeable to corrupted packets.

Currently, the main drawback of this method is its calculation complexity. If it is longer to estimate the correct header of a corrupted packet rather than waiting for it to be correctly sent, our contribution is useless. The solution we propose is fine as it highly reduces the number of calculations needed for the method but it is not as efficient in term of errors correction. To continue this project, the main purpose is to keep on working about complexity reduction. Instead of replacing the 16-bit checksum by the corresponding 8-bit checksum, it would be interesting to keep the 16-bit checksum and try to estimate the unknown sequence with two trellis of 2 8 rows, one corresponding to the 8 most significant bits of the 16-bit checksum and the other corresponding to 8 least significant bits. Of course, they would not be independent trellis, they should share information about their respective carries. This way, we would still have a reduced complexity but our sequence estimation should be better.

2. 2 .

 2 Practical evaluation of the MAP estimator In (2), the first term (y | u) represents the likelihood of the sequence u when having the soft information y . The second term (y | (k, p, u)) represents the likelihood of the checksum of the sequence r = [k, p, u]. The last term (u | R) may limits the range of possible values for u.

Fig. 1 .

 1 Fig. 1. HER vs SNR for the standard, 16-bit header correcter and 8-bit header correcter decoders of the IP layer.

This work has been partly supported by the ANR DITEMOI project.


N Changuel

B Sayadi

M Kieffer

H.264/AVC INTER-FRAME RATE-DISTORTION DEPENDENCY ANALYSIS BASED ON INDEPENDENT REGIME-SWITCHING AR MODELS

Keywords: Rate distortion theory, Autoregressive processes, Video codecs

The control of the trade-off between encoding rate and quality of compressed video is a challenging task. This control requires efrate and distortion (R-D) models, able to describe accurately the behavior of the compressed video. R-D models should account for the dependencies induced by the choice of frame-varying quantization parameters (QP). This paper proposes a dependent R-D model involving two independent regime-switching autoregressive (IRSmodels. Experimental results show that the proposed model is able to represent accurately the distortion dependency between frames. For the part of the rate due to the texture, the model fits experimental curves reasonably well. The model has to be completed to account also for the part of the rate due to motion vectors and signalization.

INTRODUCTION

Among the various problems raised by the efficient delivery of realtime video contents via a wireless channel, the control of the encoding rate is a challenging task. This control has to cope (i) with a time-varying quality of the channel which results in variations in the channel capacity and (ii) with changing complexity of the scenes to be encoded. Buffers are usually present at several places of the communication chain, e.g., at the output of the source coder, at intermediate nodes of the network, and at the receiver. They smooth variations of capacity and complexity, but their size has to remain small when a strict delivery delay has to be satisfied, for example in the case of visiophony. In such situations, the rate has to be controlled with a time scale of very few frames. Quality constraints on the compressed video (limited distortion, smooth variations of quality) increase the difficulty of the rate control [START_REF] Ying | Contentaware distortion-fair video streaming in networks[END_REF].

Obtaining models for the rate and distortion (R-D) characteristics of the video sequence to be encoded is thus instrumental to build an efficient control of the source coder. Among the wide variety of available models, one may identify the independent and dependent R-D models. In the first family of models, the R-D characteristics of each frame, or group of frames (GOF), are assumed to be independent of those of the other frames, or GOFs. One gets then simple parametric model with few tuning parameters, in which the rate and distortion are the logarithmic [START_REF] Kamaci | Frame bit allocation for the H.264/AVC video coder via cauchy-densitybased rate and distortion models[END_REF], the power [START_REF] Shen | Rate-distortion optimization for fast hierarchical b-picture transcoding[END_REF], or the exponential [START_REF] Changuel | Predictive control for efficient statistical multiplexing of digital video programs[END_REF] of some input parameter. Such models are quite efficient to represent the R-D characteristics of INTRA-encoded frames, i.e., frames encoded without reference to any other frame, or of a GOF which frames are encoded independently of the frames not belonging to the GOF. Nevertheless, it is well known that the quality at which a first frame is encoded impacts significantly that of the next frames when they are encoded with the first one as reference, as is done in most video coding standards based on the predictive coding principle [START_REF] Sayood | Introduction to Data Compression[END_REF], such as H.26X or MPEG X video coders [START_REF] Hanzo | Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels[END_REF].

In [START_REF] Kamaci | Frame bit allocation for the H.264/AVC video coder via cauchy-densitybased rate and distortion models[END_REF] a Cauchy density based R-D models for quantized DCT coefficients are proposed and analyzed in a frame bit allocation application for H.264 video coding, while in [START_REF] Tao | Adaptive modeldriven bit allocation for MPEG video coding[END_REF] a Gaussian distribution for the DCT coefficients is considered with an adaptive model-driven bit allocation method based on a parametric R-D model for MPEG2 video coding. In [START_REF] Bai | Hybrid models of the ratedistortion characteristics for MPEG video coding[END_REF] a rate model is proposed for intra frames by considering Laplacian distribution for the DCT coefficients and controlled by the quantization parameter value for MPEG2 video coding.

Dependent R-D models take the dependency between frames into account, but involve usually much more tuning parameters. In [START_REF] Lin | Bit-rate control using piecewise approximated rate-distortion characteristics[END_REF] a dependent R-D model is proposed handling texture and motion information. This model involves the previous and current quantization parameters but requires a large number of R-D measurements to fit its parameters. In [START_REF] Minghui | Ratedistortion optimized bit allocation for error resilient video transcoding[END_REF], different R-D models for Intra and Inter-coded frames are proposed. R-D models for the Inter-coded frames captures the quantization error propagation effect caused by motion compensation in the reference frame. Nevertheless, these models do not involve the coder quantization parameters, which are the actual control input. Moreover, the dependent R-D models proposed in [START_REF] Lin | Bit-rate control using piecewise approximated rate-distortion characteristics[END_REF] and [START_REF] Minghui | Ratedistortion optimized bit allocation for error resilient video transcoding[END_REF] are based on experimental analysis. In [START_REF] Wang | Theoretic analysis of inter frame dependency in video coding[END_REF] a theoretic analysis of optimal bit allocation in predictionbased video coders is presented. A Laplacian model is used to describe the distribution of DCT coefficients of residual frames and to analyze the dependency between reference frames and predicted frames at different bit rates. This paper focuses on the construction of an efficient dependent R-D model for video coders involving motion compensation and texture encoding such as H.264/AVC. The dependency between a transform coefficient of the frame to be encoded and that of its prediction obtained from past (uncoded) frames is described by an independent regime-switching autoregressive (IRS-AR) model [START_REF] Baum | Statistical inference for probabilistic functions of finite state Markov chains[END_REF]. This model, introduced in Section 2 allows to represent coefficients linked to parts of the frame where motion compensation performs well (via the AR part), and coefficients related to parts not well predicted (with the regime switching part). The R-D characteristics of such IRS-AR model are then studied in Section 2. To evaluate the R-D characteristics of a video sequence encoded with a video coder such as H.264/AVC, many IRS-AR models would be necessary. A compound model consisting of two IRS-AR models (one for the all DC coefficients, and one for all AC coefficients) is introduced in Section 3. Experimental results, detailed in Section 4, show that this simple compound model is able to accurately represent the distortion dependency between frames. For the rate, additional adjustments have to be performed to account for the cost of motion vectors and signalization.

IRS-AR MODEL

In a video coder involving block-based motion compensation such as H.264/AVC, to encode the j-th frame Fj of a video sequence, previously encoded frames F k , k = j, belonging to the same GOF are used to build a prediction Fj of Fj via motion estimation and compensation [START_REF] Sayood | Introduction to Data Compression[END_REF][START_REF] Hanzo | Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels[END_REF]. The prediction residual Fj is then transformed, quantized, and entropy-coded. The reconstructed frame is then Fj.

Neglecting the quantization noise, when the motion estimation and compensation is efficient, many collocated pixels in Fj and in Fj are very similar. For some parts of the picture, however, the motion estimation may be less efficient, due, e.g., to scene change, to appearing objects, or to motion of the camera. Collocated pixels in such areas may be quite differing. Similar observations may be done when considering transformed coefficients (TC). Collocated TC (DC and AC) may be similar or different depending on the quality of the motion estimation/compensation.

The effect of quantization noise is usually to decrease the efficiency of motion compensation. A prediction Fj based on F k , k = j is usually much less efficient than a prediction based on F k , k = j. One aim of this paper is precisely to study the impact of the quantization noise of one frame on the next ones.

Definition

The dependency between collocated TC (or collocated pixels) is modeled here using an IRS-AR

Yj = aX j Yj-1 + bX j Uj, (1)
where Yj and Yj-1 represent some collocated TC of a given block in frames j and j -1, Xj is a sequence of independent and identically distributed (iid) binary-valued random variables with Pr (Xj = 0) = 1 -ρ and Pr (Xj = 1) = ρ, and Uj is a sequence of iid zero-mean and unit variance Gaussian variables. The sequences Xj and Uj are assumed to be independent. This model allows to take into account the fact that in most cases (when Xj = 0), collocated TC are quite similar, in which case a0 is close to one, and that sometimes (when Xj = 1), there is fewer correlation, in which case a1 is closer to zero (a1 = 0 in what follows). Yj is assumed wide-sense stationary. This imposes some constraints on the parameters a0, b0, and b1. With Xj = 0, one gets

σ 2 y = a 2 0 σ 2 y + b 2 0 σ 2 u = b 2 0 σ 2 u /(1 -a 2 0 ) (2)
and if Xj = 1, one obtains

σ 2 y = b 2 1 σ 2 u . (3)
Combining (2) and (3), one gets

b 2 1 = b 2 0 /(1 -a 2 0 ). (4)
The R-D characteristics of the proposed model when scalar quantized with two different steps for Yj-1 and Yj is studied in the following section.

Rate and distortion characteristics

Assume that Yj-1 is quantized with a scalar uniform midtread quantizer qj-1 with step size ∆j-1 (to mimic intra coding). For Yj a predictive coding is performed with

Yj = aX j qj-1(Yj-1) (5)
as prediction for Yj (the value of Xj is assumed to be known). The prediction residual

E X j j = Yj -Yj = aX j (Yj-1 -qj-1 (Yj-1)) + bX j Uj (6)
then quantized with a stepsize ∆j. Depending on Xj, (6) may become E 0 j = a0 (Yj-1 -qj-1 (Yj-1)) + b0Uj when Xj = 0 corresponding to inter-coding and

E 1 j = b1Uj
when Xj = 1 corresponding to intra-coding. The aim of the remainder of this section is to provide R-D curves for the model (1) a function of ∆j-1 and ∆j. In the H.264/AVC standard [START_REF]Advanced video coding for generic audiovisual services[END_REF], characteristics of the quantizers depend on a quantization parameter Q. The relation between the quantization stepsize ∆ and Q may be approximated as

∆ (Q) = 2 Q-4 6 /PF, (7)
where PF is a constant which value depends of the subband, see [START_REF] Ma | Rate-distortion analysis for h.264/avc video coding and its application to rate control[END_REF].

The distortion for Yj may be written as

D X j j (∆j-1, ∆j) = +∞ -∞ (x -qj(x)) 2 f E X j j (x) dx, (8)
where f E X j j (x) is the probability density function of E X j j . The rate required to represent the quantized Yj is evaluated as the entropy of the output of the quantizer fed with E X j j R X j j (∆j-1, ∆j) = -+∞ k=-∞ P k (∆j-1, ∆j) log(P k (∆j-1, ∆j)) [START_REF] Lin | Bit-rate control using piecewise approximated rate-distortion characteristics[END_REF] where

P k (∆j-1, ∆j) = (k+ 1 2 )∆ j (k-1 2 )∆ j f E X j j (x) dx. (10)
When Xj = 1, E 1 j is zero-mean Gaussian with variance σ 2 y = b 2 1 σ 2 u and does not depend on ∆j-1,

f E 1 j (x) = 1 2πσ 2 y exp - x 2 2σ 2 y . (11)
High-rate approximations for (8) and (9) are easily obtained. At medium to low rates (large values of ∆j compared to σu), such highrate approximation becomes coarse, but (8) and (9) contain only few significant terms. When Xj = 0, f E 0 j (x) is the convolution of the pdfs of a0 (Yj-1 -qj-1 (Yj-1)) and of Uj. One may show that

f E 0 j (x) = 1 8πσ 2 y +∞ k=-∞ exp - (x + k∆j-1a0) 2 2σ 2 y G(x, ∆j-1, k), (12)
where

G(x, ∆j-1, k) = erf 2a0x + ∆j-1 1 -2k 1 -a 2 0 2 √ 2σy 1 -a 2 0 -erf 2a0x -∆j-1 1 + 2k 1 -a 2 0 2 √ 2σy 1 -a 2 0 . ( 13
)
Since f E 0 j (x) and f E 1 j (x) known, one may evaluate numerically D X j j (∆j-1, ∆j) and R X j j (∆j-1, ∆j) using ( 8) and [START_REF] Lin | Bit-rate control using piecewise approximated rate-distortion characteristics[END_REF]. The expectation of the rate and the distortion for a TC with respect to Xj is then

Dj(∆j-1, ∆j) = (1 -ρ) D 0 j (∆j-1, ∆j) + ρD 1 j (∆j) (14
)

Rj(∆j-1, ∆j) = (1 -ρ) R 0 j (∆j-1, ∆j) + ρR 1 j (∆j), (15)
since D 1 j and R 1 j do not depend on ∆j-1.

COMPOUND MODEL

Assuming that the size of the transform is the same for the whole frame, NDC blocks of TC have to be considered, each of which containing a single DC coefficient and NAC AC coefficients. Assume that each of these coefficients is represented by IRS-AR models, and that the quantization steps do not change within a frame, one gets a total distortion and rate for the j-th frame expressed as follows

D(∆j-1, ∆j) = 1 NDC(1 + NAC) N DC n=1 D DC,n j + N AC ℓ=1 D AC,n,ℓ j , (16) R(∆j-1, ∆j) = N DC n=1 R DC,n j + N AC ℓ=1 R AC,n,ℓ j , (17)
The number of parameters of the resulting compound model would be prohibitively large. Several simplifications have thus to be considered. First, it is assumed that when for a given TC block, the model for the DC and AC coefficients are switching simultaneously. This is reasonable, since when for a block, a motion compensation is not efficient, there is energy at all frequencies. Second, all IRS-AR models for the DC coefficients are aggregated within a single average IRS-AR model. Similarly, NAC averaged IRS-AR models for the AC coefficients may be considered (one per frequency). This would lead to 1 + NAC models, which still leads to a large number of parameters. Usually, most of the energy is gathered in the lowfrequency AC coefficients. One thus represents the R-D behavior of the AC coefficients by a single IRS-AR model which is quite coarse approximation.

As a result, one obtains a compound model consisting of two IRS-AR models (one for the DC coefficients and one for all AC coefficients)

Y DC j = a DC X j Y DC j-1 + b DC X j Uj, (18)
and

Y AC j = a AC X j Y AC j-1 + b AC X j Uj. ( 19
)
The expression of the rate and distortion becomes then

Rj = κ(δR DC j + (1 -δ)R AC j ) (20)
end

Dj = δD DC j + (1 -δ)D AC j . (21)
A multiplicative constant δ is introduced to weight the contributions of DC and AC coefficients to the total rate and distortion. An additional parameter κ is introduced in the rate to take into account the number of blocks of the frame. One may take κ NDC, but introducing an additional degree of freedom in the model of the rate helps to mitigate all approximations which were previously considered. The parameter vector p = (a DC , a

AC , b DC 1 , b AC 1 , δ, ρ) is esti- mated as follows p = arg min N k=1 (Dj(∆ k j-1 , ∆ k j ) -D exp j (∆ k j-1 , ∆ k j )) 2 (22)
here Dj is the distortion calculated using ( 8), [START_REF] Ma | Rate-distortion analysis for h.264/avc video coding and its application to rate control[END_REF], and (21) at frame j, whereas D exp j is the experimental distortion using H.264/AVC at the same frame j with N values of the pair of quantization steps (∆ k j-1 , ∆ k j ) or equivalently of the quantization parameters

(Q k j-1 , Q k j ), k = 1, .
. . , N . The parameter is then adjusted using the same experimental points on the rate curve, but with p fixed at p.

EXPERIMENTAL PART

The rate and distortion characteristics for several consecutive frames of various video sequences (Soccer, Foreman, News, Container) have been considered. Here the results for two first frames of Soccer Container are reported. Similar behaviors are observed for the other sequences.

Experimental characteristics are obtained with the H.264/AVC encoder. A subset of N = 20 measurements are considered to fit the of the proposed compound model and its rate and distortion characteristics are compared to the experimental ones. A fit with N = 9 is also considered and presented a comparable performance compared to those with 20 measurements. Figures 2 and1 represent the evolution of the rate and distortion for the second frame (Intercoded) of the Soccer and Container sequences in CIF format while varying the QP of the first reference (Intra-coded) frame.

Figure 1 shows the compound model is able to describe quite accurately the evolution of the distortion (for the luminance) and its various regimes, see [START_REF] Changuel | Statistical multiplexing of video programs[END_REF]. Figure 2 illustrates the evolution of the rate. For the experimental part (obtained with H264/AVC), the total rate (solid) and the rate due to the texture (dotted) are both represented. Dots on the solid curves correspond to the experimental values used for the parameter estimation as defined in equation ( 22) Here the fit with the texture part of the rate is satisfying, except for large values of the quantization parameter. This is mainly due to the fact that the dependency between DC coefficients has not been taken into account in the proposed compound model. When large values of QP are considered, DC values get closer, and are mode efficiently entropy-coded. This is why the rate is overestimated.

CONCLUSION

In this paper, we proposed an analytical model that describes the inter-frame rate-distortion dependency between two successively encoded frames. For that purpose, a compound IRS-AR model is constructed and analyzed. By comparing the R-D performance between the analytical model and the real H.264/AVC curves, we have shown the accuracy of the proposed model to describe the H264 encoder behavior. The resulting distortion curves using IRS-AR fits quite well the distortion behavior of the video encoder. The rate is less accurately described. One of the reasons for this is that the parameters of the IRS-AR model focuses mainly on the distortion. In addition, the rate due to signaling and transmission of motion vectors is not taken into account. Additional adjustments have to be performed on the rate model to improve its R-D modeling efficiency, allowing an improved rate and quality control.

Q j =20 Q j =25 Q j =30 Q j =35 Q j =40
Fig. 2. Rate as a function of Qj-1, parameterized with Qj (Soccer -left, Container -right); compound model (dashed), total rate using H.264/AVC (solid), texture rate using H.264/AVC (dotted)

Fig. 1 .

 1 Fig. 1. Log of the distortion as a function of Qj-1, parameterized with Qj (Soccer -left, Container -right); compound model (dashed), H.264/AVC (solid)


Ruijing Hu

Xucen Huang

Michel Kieffer

Olivier Derrien

Pierre Duhamel

ROBUST CRITICAL DATA RECOVERY FOR MPEG-4 AAC ENCODED BITSTREAMS

Keywords: Audio coding, Cyclic codes, Decoding, MAP estimation, Mobile communication, Robustness

This paper presents a bandwidth-efficient method for improved decoding of critical data generated by the MPEG-4 AAC audio coder when encoded bitstreams are transmitted over noisy channels. The critical data of each encoded frame is estimated using the redundancy due to the correlation between successive frame headers and using an optional CRC as an error-correcting code. Simulation results for an AWGN channel show a substantial link budget improvement (more than 5 dB) compared to a classical hard-decoding method. Once critical data are efficiently estimated, the work of previously proposed joint source-channel decoding techniques to recover the remaining parts of the MPEG4 AAC frames is significantly facilitated.

INTRODUCTION

High-quality audio codecs, such as the MPEG-4 AAC [START_REF] Iso/Iec | MPEG-4 information technology -very low bitrate audio-visual coding -part3: Audio)[END_REF], provide high compression efficiency. Nevertheless, since they were designed for data transmission over reliable channels, such codecs are very sensitive to transmission errors. A single bit in error in a packet of compressed data may lead to the loss of the whole packet. Such errors are unavoidable when streaming audio over wireless networks in last generation mobile communication systems, characterized by unreliable transmission channels which introduce noise at bit level and frame losses.

Packetisation of data and protection of the packets with error-detection codes (CRC or checksum) [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF][START_REF] Kurose | Computer Networking: A Top-Down Approach Featuring the Internet[END_REF] is a first solution to alleviate this problem. Erroneous packets are identified and retransmitted, if possible. Nevertheless, in scenarii with strong delay constraints, e.g., in visiophony, retransmission is difficult and may even become impossible when broadcasting data, e.g., in digital audio broadcasting. In addition to packetization, strong error-correcting codes, e.g., turbocodes, LDPC, at Physical (PHY) layer may be combined with packet-erasure codes at intermediate protocol layers [START_REF] Richardson | Modern Coding Theory[END_REF][START_REF] Mackay | Information Theory, Inference, and Learning Algorithms[END_REF]. The redundancy introduced by these codes reduces the bandwidth allocated for the data and may be over-sized in good This work has been partly funded by the NEWCOM++ NoE. channel conditions. In bad conditions, some corrupted packets may still not be recovered and are assumed lost. Errorconcealment techniques [START_REF] Kung | Spatial and temporal error concealment techniques for video transmission over noisy channels[END_REF][START_REF] Hong | Error concealment algorithms for compressed video[END_REF] can then be used by the source decoders at Application (APL) layer. They exploit the redundancy (temporal and/or spatial) found in the multimedia data for estimating the missing information.

Joint source/channel decoding (JSCD) techniques have been proposed to recover corrupted packets [START_REF] Duhamel | Joint Source-channel Decoding: A Cross-layer Perspective With Applications in Video Broadcasting[END_REF]. JSCD takes advantage of various sources of redundancy present in the coding and transmission chain. Residual redundancy may come from to the syntax of variable-length source codes [START_REF] Buttigieg | On variable-length errorcorrecting codes[END_REF][START_REF] Hagenauer | Source-controlled channel decoding[END_REF][START_REF] Kaiser | Soft decoding of variablelength codes[END_REF][START_REF] Perros-Meilhac | Huffman tree based metric derivation for a low-complexity soft VLC decoding[END_REF][START_REF] Thobaben | On iterative sourcechannel decoding for variable-length encoded markov sources using a bit-level trellis[END_REF], from the semantic of the source coders [START_REF] Tillo | A flexible error resilient scheme for jpeg 2000[END_REF][START_REF] Nguyen | Robust vlc sequence decoding exploiting additional video stream properties with reduced complexity[END_REF][START_REF] Bergeron | Soft-input decoding of variable-length codes applied to the H.264 standard[END_REF][START_REF] Sabeva | Robust decoding of h.264 encoded video transmitted over wireless channels[END_REF], from the packetization of compressed data [START_REF] Lee | Soft decoding of VLC encoded data for robust transmission of packetized video[END_REF], and from the protocol stack itself [START_REF] Marin | Robust header recovery based enhanced permeable protocol layer mechanism[END_REF], see [START_REF] Duhamel | Joint Source-channel Decoding: A Cross-layer Perspective With Applications in Video Broadcasting[END_REF] for more details. Altogether, the various redundancies can attain an unexpected amount, and have the potential of avoiding many packet retransmissions.

In [START_REF] Derrien | Joint source/channel decoding of scalefactors in mpeg-aac encoded bitstreams[END_REF], the JSCD of scalefactors in MPEG-AAC coded bitstream provides a significant improvement in perceptual signal quality compared to classical decoding method. Nevertheless, this result assumes that critical data (mainly packet headers) in every packet are correctly received. This assumption requires that critical data are better protected against transmission errors. This paper introduces an alternative approach to recover efficiently critical data in each MPEG4-AAC frame, which are assumed to be only protected by the optional CRC of MPEG4-AAC. A JSCD technique is again used to exploit the correlation between the headers of successive packets, in conjunction with soft information provided by the channel decoders at PHY layer and forwarded to the APL layer using a permeable protocol stack [START_REF] Jenkac | Permeablelayer receiver for reliable multicast transmission in wireless systems[END_REF][START_REF] Marin | Robust header recovery based enhanced permeable protocol layer mechanism[END_REF] involving joint protocol channel decoding techniques to recover the various headers of the protocol stack. The proposed decoding technique is an adaptation of that proposed in [START_REF] Marin | Robust header recovery based enhanced permeable protocol layer mechanism[END_REF], designed for the recovery of header at various levels of the protocol stack.

Section 2 gives an overview of MPEG-4 AAC decoding and identifies the critical data in the MPEG4-AAC bitstreams. Section 3 introduces the JSCD of MPEG4-AAC critical data. Finally, Section 4 presents simulation results before drawing some conclusions.

CRITICAL DATA OF THE MPEG4-AAC FRAMES

In this study, unreliable transmission channels which generate bit-level noise are considered. Data are segmented in transport-level frames, according to the network protocol [START_REF] Kurose | Computer Networking: A Top-Down Approach Featuring the Internet[END_REF]. It is assumed that, at the receiver side, reliability information at the output of the PHY layer reaches the APL layer and may be used by the source decoder [START_REF] Marin | Robust header recovery based enhanced permeable protocol layer mechanism[END_REF][START_REF] Marin | Robust mac-lite and soft header recovery for packetized multimedia transmission[END_REF]. This assumption is reasonable because all processing is performed inside the receiver terminal.

The MPEG-4 AAC standard specifies a bitstream format for encoded audio data. The bitstream is segmented in frames, of fixed length in the case of fixed bit-rate encoding, or variable length in the case of variable bit-rate (VBR) encoding. These are source level frames, and one frame does not necessarily correspond to a unique transport level frame.

The simplest AAC bitstream is considered: A monophonic audio signal encoded with the Low Complexity profile. A frame is made up of a fixed header, a variable header, a data block, and a marker indicating the end of the frame. The data block comprises a global gain (Gg) field, an individual channel stream (ICS) field, a section field, a scalefactor field, a spectral data field, and an optional field, called data stream element (DSE). The most critical parts of the frame are the headers, the ICS, and the section fields [START_REF] Korhonen | Schemes for error resilient streaming of perceptually coded audio[END_REF]. When these data are corrupted, decoding is almost impossible. Thus, errors on critical data are usually considered equivalent to a frame loss. The MPEG4-AAC standard provides an optional CRC covering the 192 first bits of the frame, allowing to detect a corruption of most critical data.

In what follows, this CRC is used as an error-correcting code, in conjunction with the residual redundancy left by the MPEG4-AAC coder in the headers it generates and the redundancy due to the correlation between successive headers.

MAP ESTIMATOR FOR THE CRITICAL DATA

Consider the -th incoming MPEG-4 AAC packet. Since the 192 first bits are protected by the CRC c of ℓ bits of MPEG-4 AAC, only some parts of the long frames are protected. Fields protected by the CRC may have various properties, which will be used in a different way as far as the corresponding redundancy is concerned.

Four types of fields protected by CRC may be identified.

• The constant fields, represented by the vector k , are assumed to be known.

• The predictable fields are embedded in the vector p .

In contrast with the known fields, the predictable fields are estimated by exploiting the correlation between successive packets, and, if available, information provided by the lower layers of the protocol stack. The provided information is represented by , which will be defined formally in what follows. The predictable fields are assumed to be entirely determined if the preceding packets and if the header of the lower layers have been correctly decoded.

• The important unknown fields are collected in the vector u . These parameters are either completely unknown or limited to a configuration set Ω (k , p , ) whose content is determined by the values of k , p , and .

• Finally, the vector o contains the other fields covered by the CRC. This last part contains less critical data, which may be robustly decoded using specific techniques [START_REF] Derrien | Joint source/channel decoding of scalefactors in mpeg-aac encoded bitstreams[END_REF].

The first three fields k, p, and u are the critical data of the AAC frame, and gathers the critical data of the -1-th frame

= {k -1 , p -1 , u -1 }.
To lighten notations, when there is no ambiguity, the packet number is omitted in what follows.

Assume that some soft information y = [y , y , y , y , y ] on k, p, u, o, and c is received from the lower protocol layer. Since k and p are known or may be exactly predicted from the already received data, only u remains to be estimated. Taking into account the observations y, the knowledge of k, p, and , as well as the CRC properties, one may obtain the maximum a posteriori estimate û = arg max u∈Ω (u|k, p, , y , y , y ) for u. After some derivations detailed in [START_REF] Marin | Robust mac-lite and soft header recovery for packetized multimedia transmission[END_REF], one obtains

û = arg max u∈Ω (y |u)Ψ(•). (1)
with

Ψ(•) = ∑ o (o) (y |o) (y |ℱ([k, p, u, o])), (2)
and where ℱ is the CRC encoding function.

The evaluation of (2) requires summing 2 ℓ terms for each u ∈ Ω . This results in many cases to an unmanageable computational complexity. A trellis decoding inspired from [START_REF] Wolf | Efficient maximum-likelihood decoding of linear block codes using a trellis[END_REF] has been proposed in [START_REF] Marin | Robust mac-lite and soft header recovery for packetized multimedia transmission[END_REF]. This techniques allows to reduce the evaluation of (2) to (2 ℓ ) operations. Splitting the CRC into several parts assumed to be independent allows to further reduce the complexity to (2 ℓ / ) operations, where is the number of parts in which the CRC is divided. Further simplification introduces some suboptimality in the estimation algorithm. Fig. 1. Fields of an MPEG-4 AAC monophonic audio frame

APPLICATION

The JSCD of critical data in a monophonic audio signal is performed using the algorithm described in Section 3. Figure 1 recalls the structure of an MPEG4-AAC encoded frame. Examples of the four types of fields are provided in what follows. Synchronisation is a 12-bit known field, since it contains only ones. Frame length is a predictable field, since the length of the frame may be obtained from lower protocol layers. Fs, the sampling frequency is a field of 4 bits, which may take any value between 0000 and 1011, it is thus a unknown field with a limited set of values. Gg, the global gain is an 8-bit field which may take any value, it is thus fully unknown. Finally, Section and Sf are examples of other fields, which may be more efficiently decoded with other JSCD techniques than those presented here.

The 5 first seconds of "Tom's dinner" by Suzanne Vega (first 5 seconds, sample rate 48 kHz) have been encoded with an MPEG-4 AAC in a Low Complexity profile at 64 kbits/s. The 192 first bits of each frame are encoded with the CRC specified by the MPEG-4 AAC standard. To simplify simulation, each packet is BPSK modulated and transmitted over an AWGN channel, modeling the actual transmission channel and the various layers of a permeable protocol stack.

Several decoders have been employed to estimate the critical data of each frame. The non-informed hard decoder is a standard hard-input decoder. The informed hard decoder takes into account the knowledge of the known and predictable fields to only estimate the unknown fields via a hard decision on the received bits. In other words, it makes use of the same information as used by our robust decoder. The robust decoder corresponds to an implementation of the estimator (1) using a trellis, as proposed in [START_REF] Marin | Robust mac-lite and soft header recovery for packetized multimedia transmission[END_REF]. The performance of the three decoders is evaluated in terms of frame error rate (FER), evaluated only on the known, predictable, and unknown fields. Figure 2 shows the frame error rate for different values of SNR. For a FER of 10 -3 , compared with the hard decoders, from 4 to 5 dB in SNR are gained with the proposed robust decoder, depending on whether the known and predictable fields are exploited by the hard decoder.

In [START_REF] Derrien | Joint source/channel decoding of scalefactors in mpeg-aac encoded bitstreams[END_REF], a JSCD of the Scalefactor field has been proposed, assuming that the headers were correctly decoded. The JSCD starts to provide satisfying results at 11 dB. One notices that at such values of the SNR, the robust decoder allows to get a vanishing FER. Assuming that headers may be correctly decoded, as done in [START_REF] Derrien | Joint source/channel decoding of scalefactors in mpeg-aac encoded bitstreams[END_REF] is thus reasonable.

CONCLUSIONS

In this paper, a robust MPEG4-AAC critical data estimator has been presented. This JSCD technique takes advantage of the presence of an optional CRC and of the correlation between successive packet headers. This redundancy allows large parts of the critical data to be known in advance, and to reduce the search set for the unknown parts.

Compared to a classical hard-decoding scheme, the frame error rate (measured on the critical data) is significantly reduced. A gain from 4 to 5 dB is obtained in terms of SNR. If additional JSCD techniques are employed to decode other parts of the MPEG4-AAC frames, the critical data estimator allows these data to be error-free in the SNR region for which, e.g., robust scalefactor decoders work fine, see [START_REF] Derrien | Joint source/channel decoding of scalefactors in mpeg-aac encoded bitstreams[END_REF].

The robust decoder presented in this work and that in [START_REF] Derrien | Joint source/channel decoding of scalefactors in mpeg-aac encoded bitstreams[END_REF] have now to be combined in order to study the performance of JSCD techniques on whole MPEG4-AAC frames.

Fig. 2 .

 2 Fig. 2. Frame Error Rate as a function of the SNR for three decoders