{'fraction_non_alphanumeric': 0.04811580139091056, 'fraction_numerical': 0.0074397541646449945, 'mean_word_length': 4.321428571428571, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Binary Rate Distortion With Side Information: The Asymmetric Correlation Channel Case

Advancing over up-to-date information theoretic results that assume symmetric correlation models, in this work we consider the problem of lossy binary source coding with side information, where the correlation is expressed by a generic binary asymmetric channel. Specifically, we present an in-depth analysis of rate distortion with side information available to both the encoder and decoder (conventional predictive), as well as the Wyner-Ziv problem for this particular setup. Prompted by our recent results for the Z-channel correlation case, we evaluate the rate loss between the Wyner-Ziv and the conventional predictive coding, as a function of the parameters of the binary asymmetric correlation channel.


I. INTRODUCTION
Using side information is fundamental in many source and channel coding problems and has recently been adopted in new fields, like compressed sensing and compressive classification [1]. The vast majority of results in discrete source coding with side information assume that correlation channel between the source and the side information to be symmetric. Side information is also a key factor in distributed source coding; e.g. recent results in distributed video coding [2], [3] have shown that using an asymmetric channel model to express the correlation between the source (frame to be encoded) and the side information (motion-compensated prediction) leads to substantial compression performance gains compared to the case where a conventional symmetric correlation channel model is used.
In this work, we focus on the theory of rate distortion with side information. Specifically, we consider the following setup: let (X, Y ) ∈ X × Y be correlated binary random variables, such that the source X ∽ Bernoulli(0.5) is to be encoded using the source Y as side information. The correlation between the two sources is described by a binary asymmetric channel: (a, b) ∈ 0, 1 2 . The reconstructed source is the binary variablê X ∈X , and the distortion metric considered is the Hamming distance: if (x,x) ∈ X ×X then d H (x,x) = 0 if x =x, and d H (x,x) = 1 if x =x. Our goal is to describe the rate distortion characteristics of this system in two cases, that is when the side information Y is available at (i) both the encoder and decoder, corresponding to the conventional predictive case, and (ii) available only at the decoder, i.e., the Wyner-Ziv (WZ) case.
For the binary symmetric correlation, the rate distortion functions were given by Berger in [4] for the predictive case, and respectively by Wyner and Ziv in [5], for the corresponding WZ case. Another binary correlation channel that has been recently studied is the Z-channel, for which Steinberg derived in [6] the rate distortion bound R Z X|Y (d) for the predictive case, while in [7] we derived the rate distortion bound R Z W Z (d) for the Wyner-Ziv case. In [5], it is established that, for the general case, a rate loss exists between the predictive and WZ bounds. Zamir showed in [8] that, for binary sources and the Hamming distortion metric, the rate loss is at most 0.22 bits/sample, and in [7] we show that this difference vanishes in the case of the Z-channel correlation.
To the best of our knowledge, the characterization of the binary rate distortion function in the general case of the asymmetric correlation is still an open problem. A straightforward option is to use a numerical algorithm to compute it, such as the Blahut-Arimoto [9] implementation in [10]. Unfortunately, such a numerical analysis does not provide an analytical characterization of the rate distortion function nor an understanding of its behaviour in various rate regions.
In this paper, we present the derivation of the conventional predictive R X|Y (d) function for the considered setup. Subsequently, by considering a binary auxiliary variable in the formulations of [5], we derive rate and distortion expressions that yield a bound for the WZ problem. Furthermore, through our analysis, we are able to evaluate the evolution of the rateloss, with respect to the crossover probabilities of the binary asymmetric correlation channel.

II. SOURCE CODING WITH ENCODER-DECODER SIDE INFORMATION
When the side information is available both at the encoder and the decoder, the rate-distortion function is given by where E · denotes the expectation operator and d is the targeted distortion.
The quantity to be minimized in (2) can be written as where H(·) denotes the binary entropy function and D = X ⊕X. With the X − Y correlation channel given by (1), the maximum distortion to be considered is the average crossover of the side information channel, i.e., ifX = Y : D max = a+b 2 . We consider the inverse channel Y − X: , and the maximum distortion can be written as (1). This implies a * ≥ b * . Given that the side information is known at the encoder, we can always describe the overall distortion as being where (3) with the above mentioned constraints gives the minimum for I(X;X|Y ). This is an optimization problem that can be expressed using the Karush-Kuhn-Tucker conditions: We formulate the Lagrangian optimization problem with the above inequality constraints, and the Lagrangian function is: Deriving with respect to the unknowns yields: This can be achieved by considering an auxiliary variable U given by a binary symmetric channel with input X and output U , with crossover probability p 0 as follows: The corresponding reconstruction function is:

III. SOURCE CODING WITH SIDE INFORMATION AT THE DECODER
When the side information is available only at the decoder, the R-D function is given by whereX = f (U, Y ) and U is an auxiliary random variable, satisfying the Markov chains: Let U ∈ U be the outcome obtained from a binary channel with input X and the transition matrix given by: with (p, q) ∈ 0, 1 2 .
We will express the resulting rate and distortion as functions of the crossover probabilities of the channels in (1) and (12).

A. Expression of the Rate
The quantity to be minimized in (11) is written as Given the Markovianity U ↔ X ↔ Y the channel between Y and U can be expressed as the concatenation of the channels X − U and X − Y . Knowing (4) and (12) the transition matrix is Therefore, based on (13), let us define R * W Z (p, q) to be:

B. Expression of the Distortion
The distortion expression can be determined by observing that for a fixed pair (u, y), x is given by the conditional distribution p(x|u, y). Since the decoder can only make a deterministic decision given u and y, the best choice is to output:x = f (u, y) = arg max x p(x|u, y).
We can write the error rate conditioned on (u, y) as 1 − p(f (u, y)|u, y) , so the average distortion is given by (1 − p(f (u, y)|u, y))p(u, y).
Knowing that, due to the Markov property U ↔ X ↔ Y , we can write p(x, y, u) as follows: and .
At this point, it is useful to make the following observations regarding the symmetries of the R * W Z (p, q) and d with respect to the crossover probabilities in (1) and (12): the functions R * W Z (p, q) and d do not change. • If in (12) we substitute the pair (p, q) by (1 − p, 1 − q), the functions R * W Z (p, q) and d do not change. Essentially, the substitutions are equivalent to a label swap at the output of the respective channels and do not affect the rate-distortion function. The consequence is that the domains of interest for the pairs (a, b) and (p, q) can be reduced from [0, 1] 2 to 0 ≤ a + b ≤ 1 and 0 ≤ p + q ≤ 1.
There can be four possible expressions for the above equation, each corresponding to a different reconstruction strategy at the decoder. Without loss of generality, let a < b, fixed by the initial setup. The crossover probabilities p and q can vary. In order to emphasize the decision taken by the reconstruction function given in (16) for every pair (y, u), we introduce the following function: x out (y, u) = arg max

C. Deriving a tight bound on the rate distortion function
Given R * W Z (p, q) as in (15) and the four expressions of the distortion function in (22), finding the bound can be formulated as a minimization problem with constraints. For every distortion level d ∈ 0, D max , the goal is to find the (p, q) pair that minimizes the rate, while satisfying the distortion constraint: The result of the above minimization is denoted R * W Z (d). In order to establish a characterization of the bound, we need to show how a certain distortion level can be achieved, i.e., what reconstruction function should be used. For example, if the required distortion level is d = 0, this can only be obtained usingX = U , since min(D 2 ) = a/2, min(D 3 ) = b/2, and D 4 is a constant.
As such, we consider all possible values for the expected distortion d, and we must find what pairs (p, q) can achieve it and the corresponding reconstruction strategy. As d grows from zero to D max , we can derive the following conclusions: We want our bound to be a convex function; R * W Z (d) on the other hand may not be convex, as it is the union of two convex curves: one corresponding toX = U , the other toX = U ∨Y . To this end, we must consider the lower convex envelope of the achievable points: R bound (d) = l.c.e.{R * W Z (d)}. This will include the common tangent of the two curves and the region is achievable through time sharing.
As an illustration, the rate distortion points in region Ri of Fig. 2 correspond to the p(q) values in region i of Fig.  1, for all i ∈ {I, II, III}. Fig. 2 also presents R * W Z (d), the common tangent which completes R bound (d), and the predictive R X|Y (d).
The solution to the minimization problem proposed has a complex form and the resulting equations cannot be solved analytically. We can therefore obtain the R bound (d) curve only by numerically solving a logarithmic equation.
An important aspect is to answer whether the obtained rate distortion bound is tight. From [5] we know that the cardinality of the auxiliary variable U is bounded by |X | + 1, so a ternary alphabet for U might be needed to achieve the rate distortion function. However, numerical experiments obtained with various probability input distributions π, and crossover probabilities of the correlation channel (a, b), indicate that the proposed rate distortion bound does overlap with the rate distortion function obtained with the Blahut-Arimoto algorithm in [10]. Hence, we conjecture that a binary auxiliary  variable U is sufficient to achieve the rate distortion function and the proposed rate distortion bound R bound (d) is tight. A thorough analysis of this aspect is left as topic of further investigation.

IV. OPTIMAL p(U |X) AND RATE-LOSS ASSESSMENT
Since our bound R bound (d) does not have an analytical form, we use a numerical approach to derive the optimal crossover values of the X − U channel, i.e., the (p, q) pairs, and also to find the time-sharing region.
The optimal crossover pairs (p, q) that achieve the R * W Z (d) bound, are plotted as p(q) in Fig. 1, while Fig. 3 presents the same (p, q) pairs as functions of the distortion. The cross markers in both figures show the values that delimit the time sharing region. For low distortions, when the reconstruction function isX = U , the optimal channels are close to binary symmetric channels. When the transition to the reconstruction functionX = U ∨ Y occurs, there is a discontinuity in the p(d) and q(d) functions. That can be noticed in Fig. 1 as well, where the two green curve segments are disjoint.
If we fix the average distortion of the correlation channel, the highest rate-loss is in the case of the binary symmetric correlation. Fig. 4 shows the variation of the rate-loss for different crossover probabilities of the binary symmetric correlation channel X − Y . The maximum value ∆R = 0.0765 is obtained for the crossover a = b = 0.227.

V. CONCLUSION
This paper analyzes the rate distortion problem for a binary uniform source in the presence of correlated side information, when the correlation is given by an asymmetric channel. We have derived the R X|Y (d) for the conventional predictive case, and also proposed a bound R bound (d) for the Wyner-Ziv case. Numerical algorithms allow us to describe the optimum p(U |X) achieving the bound, as well as to establish the maximum rate-loss in the case of binary uniform sources.