# Codage optimal zéro-erreur pour le calcul de fonction avec information adjacente partagée deux à deux

Nicolas Charpenay, Maël Le Treust, Aline Roumy

## ► To cite this version:

Nicolas Charpenay, Maël Le Treust, Aline Roumy. Codage optimal zéro-erreur pour le calcul de fonction avec information adjacente partagée deux à deux. GRETSI 2023 - XXIXème Colloque Francophone de Traitement du Signal et des Images, Aug 2023, GRENOBLE, France. pp.1-4. hal-04251973

HAL Id: hal-04251973

https://hal.science/hal-04251973v1

Submitted on 20 Oct 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Codage optimal zéro-erreur pour le calcul de fonction avec information adjacente partagée deux à deux

Nicolas CHARPENAY<fnref n="1" /> Maël LE TREUST<fnref n="1" /> Aline ROUMY<fnref n="2" />

**Résumé** – Nous étudions un problème de codage de source zéro-erreur pour le calcul de fonction, avec information adjacente à l'encodeur. Dans ce problème, $(X, Y)$ est tirée avec une loi jointe $P_{X,Y}$ ; l'encodeur connaît $X$ et $g(Y)$, et communique à travers un canal parfait à un certain débit avec un décodeur. Ce dernier connaît $Y$ et doit retrouver $f(X, Y)$ avec probabilité d'erreur 0, où $f, g$ sont des fonctions déterministes. Dans notre travail précédent, nous avons proposé une condition suffisante sur $P_{X,Y}$ et $g$ pour que le débit optimal de ce problème admette une expression à une seule lettre. Nous donnons dans ce papier une nouvelle interprétation de ces résultats en termes de graphes caractéristiques et de débit optimal dans le problème Slepian-Wolf zéro-erreur associé.

**Abstract** – We study a zero-error source coding for computing problem, with side-information at the encoder. In this problem, $(X, Y)$ is drawn with a distribution $P_{X,Y}$; the encoder knows $X$ and $g(Y)$, and communicates with the decoder at a certain rate through a noiseless channel. The decoder knows $Y$ and must retrieve $f(X, Y)$, where $f, g$ are deterministic functions. In our previous work, we exhibited a sufficient condition on $P_{X,Y}$ and $g$ such that the optimal rate in this problem has a single-letter expression. In this paper, we give a new interpretation of these results in terms of characteristic graphs and optimal rate in the associated zero-error Slepian-Wolf problem.

## 1 Introduction

Considérons le scénario de codage de source de la Figure 1, où deux suites corrélées $(X^n, Y^n) = ((X_1, ..., X_n), (Y_1, ..., Y_n))$ de variables aléatoires discrètes sont tirées de manière i.i.d. avec la distribution $P_{X,Y}$. L'encodeur connaît $X^n$, a $(g(Y_t))_{t \le n} = (g(Y_1), ..., g(Y_n))$ comme information adjacente, et transmet de l'information au décodeur à travers un canal parfait de capacité $R$. Le décodeur a l'information adjacente $Y^n$, et désire reconstruire $(f(X_t, Y_t))_{t \le n}$, où $f, g$ sont des fonctions déterministes. Quel est le plus petit $R$ tel que le décodeur retrouve $(f(X_t, Y_t))_{t \le n}$ avec probabilité d'erreur 0 ?

Le schéma de la Figure 1 a été étudié avec d'autres contraintes que la probabilité d'erreur zéro ; et le débit optimal a été caractérisé dans chacun de ces cas : le cas sans pertes et probabilité d'erreur asymptotiquement nulle par OR-litsky et Roche dans [8], et le cas avec pertes par Yamamoto dans [12]. Toutefois, ces résultats peuvent seulement servir de bornes ici et ne coïncident pas en général avec le débit optimal zéro-erreur, en particulier quand la distribution de source $P_{X,Y}$ est à support plein.

Ce problème de codage apparaît en compression vidéo [4,5], où $X^n$ modélise un ensemble d'images connues à l'encodeur. Le décodeur ne doit pas nécessairement retrouver chaque image en entier, mais a une suite de requêtes particulières $Y^n$ pour chaque image, par exemple la détection d'un chat, chien, voiture, vélo, etc...; ou reconnaissance de scène : rue, ville, montagne etc... L'encodeur ne connaît pas la requête exacte du décodeur, mais il possède une information partielle (par exemple le type de la requête), ce qui est modélisé par la suite de variables aléatoires $(g(Y_t))_{t \le n}$.

En considérant le cas $f(X, Y) = X$, on obtient un cas particulier du problème de la Figure 1 : le problème ouvert

<figure><img src="image_2.png" /><figcaption>FIGURE 1 : Codage de source zéro-erreur pour le calcul de fonction, avec information adjacente à l'encodeur.</figcaption></figure>

Slepian-Wolf zéro-erreur [1] représenté en Figure 2. Dans ce dernier problème, à chaque distribution $P_{X,Y}$ est associé un graphe caractéristique, et le débit optimal s'exprime comme un invariant de ce graphe : il s'agit de l'entropie complémentaire de graphe [1, 6, 10], dont la définition fait intervenir une limite et des coloriages de produits de graphes. Or, l'entropie complémentaire a une formule à une seule lettre (i.e. sans utiliser de limite) seulement pour certains graphes particuliers, les graphes parfaits notamment [3]. Obtenir des formules à une seule lettre présente un intérêt, car elles permettent d'exprimer le débit optimal du problème en Figure 2 à l'aide d'un coloriage de graphe de petite taille.

Avec le paramètre supplémentaire de la fonction $f$, le problème de la Figure 1 n'a donc pas de formule à une seule lettre pour son débit optimal en général. Dans notre travail

<figure><img src="image_3.png" /><figcaption>FIGURE 2 : Problème de Slepian-Wolf zéro-erreur avec information adjacente à l'encodeur.</figcaption></figure>

<footnote n="1">¹Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), 263 Av. Général Leclerc, 35000 Rennes, France</footnote>

<footnote n="2">²Institut National de Recherche en Informatique et en Automatique (INRIA), 263 Av. Général Leclerc, 35000 Rennes, France</footnote>
précédent [2], nous avons proposé une condition sur $P_{X,Y}$ et $g$ appelée "information adjacente partagée deux à deux". Lorsqu'elle est vérifiée, le débit optimal de la Figure 1 s'écrit pour tout $f$ comme combinaison convexe d'entropies de Körner [7], qui ont une expression à une seule lettre [1].

Dans ce papier, nous donnons une nouvelle interprétation de cette condition en termes de débit optimal du problème Slepian-Wolf zéro-erreur : les $P_{X,Y}$ et $g$ qui vérifient la condition "information adjacente partagée deux à deux" sont ceux qui induisent le pire débit possible $H(X|g(Y))$ dans le problème Slepian-Wolf zéro-erreur en Figure 2. Dans le cas où la condition est vérifiée, le graphe caractéristique du problème Slepian-Wolf zéro-erreur correspondant s'écrit comme une union disjointe de graphes complets.

Ce papier est organisé comme suit. En Section 2, nous posons formellement le problème de la Figure 1 et ses notations. Dans la Section 3, nous présentons la condition "information adjacente partagée deux à deux" et la nouvelle interprétation que nous en donnons; ainsi que les formules pour le débit optimal de la Figure 1 qu'elles permettent d'obtenir. Dans la Section 4, nous développons la preuve pour cette nouvelle interprétation.

## 2 Présentation formelle

On note les suites $x^n = (x_1, ..., x_n)$. L'ensemble des distributions de probabilité sur un ensemble fini $\mathcal{X}$ est noté $\Delta(\mathcal{X})$. La loi d'une variable aléatoire $X$ est notée $P_X \in \Delta(\mathcal{X})$, son support est noté supp $P_X$. Pour une longueur de suite donnée $n \in \mathbb{N}^*$, on note $\Delta_n(\mathcal{X}) \subset \Delta(\mathcal{X})$ l'ensemble des distributions empiriques des suites de $\mathcal{X}^n$.

On note $\{0, 1\}^*$ l'ensemble des mots binaires. Un ensemble de mots $\mathcal{W} \subset \{0, 1\}^*$ est sans préfixe si pour tout $w, w' \in \mathcal{W}$, $w$ n'est pas un préfixe de $w'$ et vice-versa.

Le schéma de la Figure 1 est caractérisé par :

- Quatre ensembles finis $\mathcal{X}, \mathcal{Y}, \mathcal{U}, \mathcal{Z}$, un couple de variables aléatoires $(X, Y) \in \mathcal{X} \times \mathcal{Y}$ suivant la loi $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$ (avec $P_X$ et $P_Y$ à support plein), et deux fonctions déterministes

$$f: \mathcal{X} \times \mathcal{Y} \to \mathcal{U}, \qquad (1)$$

$$g: \mathcal{Y} \to \mathcal{Z}. \qquad (2)$$

On suppose sans perte de généralité que $g$ est surjective afin d'avoir des marginales à support plein : si elle ne l'est pas, on peut simplement considérer sa corestriction à son ensemble image. Pour $n$ utilisations successives de la source, on note $(X^n, Y^n)$ la suite de $n$ copies de $(X, Y)$ tirées de manière i.i.d. avec la loi $P_{X,Y}$.

- L'encodeur observe les réalisations de $X^n, (g(Y_t))_{t \le n}$ et envoie de l'information au décodeur sur un canal parfait de capacité $R \ge 0$.

- Le décodeur reconstruit $(f(X_t, Y_t))_{t \le n}$ à l'aide du message de l'encodeur et de l'information adjacente $Y^n$.

**Définition 2.1 (Code de source zéro-erreur, débit réalisable)**
Pour tout $n \in \mathbb{N}^*$, un $(n, R_n)$-code de source zéro-erreur est composé d'une fonction d'encodage $\phi_e: \mathcal{X}^n \times \mathcal{Z}^n \to \{0, 1\}^*$ et d'une fonction de décodage $\phi_d: \mathcal{Y}^n \times \{0, 1\}^* \to \mathcal{U}^n \text{ telles que :}$

1. l'ensemble $\phi_e(\mathcal{X}^n \times \mathcal{Z}^n)$ est sans préfixe,

2. $R_n = \frac{1}{n}\mathbb{E}[l \circ \phi_e(X^n, (g(Y_t))_{t \le n})]$, où $l(\cdot)$ est la longueur d'un mot binaire,

3. la propriété zéro-erreur est satisfaite :

$$\begin{gathered} \forall (x^n, y^n) \in \text{supp } P_{X,Y}^n, \\ \phi_d(y^n, \phi_e(x^n, (g(y_t))_{t \le n})) = (f(x_t, y_t))_{t \le n}. \quad (3) \end{gathered}$$

Un débit $R$ est réalisable s'il existe une suite de $(n, R_n)$-code de source zéro-erreur tels que $\lim_n R_n = R$. Le débit optimal est noté $R^* = \inf\{R \ge 0 \mid R \text{ est atteignable}\}$.

L'hypothèse que l'image de $\phi_e$ soit sans préfixe garantit que le décodeur pourra toujours déterminer quand le message de l'encodeur s'arrête. Une hypothèse plus faible que l'impossible sans préfixe est étudiée dans [1, Théorème 3], sans influence sur le débit optimal. Si les trois conditions ci-dessus sont satisfaites, on aura un décodage correct avec probabilité 1.

## 3 Information adjacente partagée deux à deux

**Définition 3.1 La distribution $P_{X,Y}$ et la fonction $g$ vérifient la condition "information adjacente partagée deux à deux" si**

$$\begin{gathered} \forall z \in \mathcal{Z}, \forall x, x' \in \mathcal{X}, \exists y \in g^{-1}(z), \\ P_{XY}(x, y)P_{XY}(x', y) > 0. \quad (4) \end{gathered}$$

Cela signifie que pour tout $z$ dans l'image de $g$, chaque paire $(x, x')$ "partage" au moins un symbole d'information adjacente $y \in g^{-1}(z)$.

Nous donnons dans le Théorème 3.2 une interprétation de cette condition. Les couples $(P_{X,Y}, g)$ qui vérifient la condition "information adjacente partagée deux à deux" (4) sont exactement ceux qui induisent le plus mauvais débit optimal possible $H(X|g(Y))$ dans le cas $f(X, Y) = X$.

Dans la preuve du Théorème 3.2 en Section 4, nous illustrons que dans le cas $f(X, Y) = X$ (problème Slepian-Wolf zéro-erreur en Figure 2), si (4) est vérifiée, le graphe caractéristique du problème s'écrit comme une union disjointe de graphes complets. Pour rappel, le débit optimal du problème Slepian-Wolf zéro-erreur est connu quand le graphe caractéristique est parfait. Comme une union disjointe de graphes complets est un cas particulier de graphes parfaits, on peut alors caractériser le débit optimal dans le cas où $f(X, Y) = X$ et (4) est vérifiée : $H(X|g(Y))$.

Toutefois, il est important de remarquer la portée de la condition "information adjacente partagée deux à deux" (4), car elle ne dépend pas de la fonction $f$ et est donc plus générale que le cas $f(X, Y) = X$. Une conséquence de l'indépendance de la condition à la fonction $f$ est que, dans l'expression du débit optimal au Théorème 3.7, la fonction $f$ contribue uniquement pour le calcul de l'entropie d'un graphe auxiliaire. Une interprétation de l'effet de $f$ dans la construction du graphe auxiliaire est d'enlever des arêtes à l'union de graphes complets qu'on aurait obtenue dans le cas $f(X, Y) = X$.
**Théorème 3.2** Le couple $(P_{X,Y}, g)$ satisfait la condition “information adjacente partagée deux à deux” (4)

$\iff R^* = H(X|g(Y))$ dans le cas $f(X, Y) = X$ et pour tout $z$, $P_{X|g(Y)=z}$ est à support plein.

La condition (4) présente un grand intérêt. En effet, dans notre travail précédent [2] nous avons montré que, si $P_{X,Y}$ et $g$ vérifient cette condition, le débit optimal $R^*$ s'écrit comme combinaison convexe d'entropies de Körner qui sont des formules à une seule lettre, comme illustré dans les Théorèmes 3.7 et 3.8. Puisque la condition “information adjacente partagée deux à deux” (4) ne dépend pas de la fonction $f$ : le Théorème 3.7 donne une formule à une seule lettre pour toutes les instances correspondantes.

Le cas où $P_{X,Y}$ est à support plein est suffisant (mais non nécessaire) pour que (4) soit vérifiée avec n'importe quelle fonction $g$. Le débit optimal trouvé au Théorème 3.7 peut alors être évalué pour une distribution à support plein, ce qui donne l'expression du Théorème 3.8.

**Définition 3.3 (Graphe probabiliste)** Un graphe probabiliste $G$ est un tuple $(\mathcal{V}, \mathcal{E}, P_V)$, où $\mathcal{V}$ est l'ensemble des sommets, $\mathcal{E}$ est l'ensemble des arêtes, et $P_V \in \Delta(\mathcal{V})$ est une distribution de probabilité sur les sommets.

**Définition 3.4 (Ensemble indépendant)** Soit $G = (\mathcal{V}, \mathcal{E}, P_V)$ un graphe probabiliste. Un sous-ensemble de sommets $S \subseteq \mathcal{V}$ est indépendant si $xx' \notin \mathcal{E}$ pour tout $x, x' \in S$.

**Définition 3.5 (Entropie de Körner d'un graphe $H_\kappa$)**

Pour tout graphe probabiliste $G = (\mathcal{V}, \mathcal{E}, P_V)$, soit $\Gamma(G)$ la collection des ensembles indépendants dans $G$. L'entropie de Körner de $G$ est définie par

$$H_{\kappa}(G) = \min_{V \in W \in \Gamma(G)} I(W; V), \quad (5)$$

où le minimum est pris sur les distributions conditionnelles $P_{W|V} \in \Delta(W)^n$, avec $W = \Gamma(G)$ et avec la contrainte que le sommet aléatoire $V$ appartient à l'ensemble aléatoire $W$ avec probabilité 1.

**Définition 3.6 (Graphe auxiliaire $G_z^f$)** Pour tout $z \in \mathcal{Z}$, nous définisons le graphe auxiliaire $G_z^f$ par

- $\mathcal{X}$ comme ensemble de sommets, avec $P_{X|g(Y)=z}$ comme distribution sur les sommets,

- $xx'$ sont adjacents si $f(x, y) \neq f(x', y)$ pour au moins un $y \in g^{-1}(z) \cap \text{supp } P_{Y|X=x} \cap \text{supp } P_{Y|X=x'}$.

**Théorème 3.7 (de [2])** Si $P_{X,Y}$ et $g$ satisfont la condition “information adjacente partagée deux à deux” (4), le débit optimal est :

$$R^* = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f). \quad (6)$$

**Théorème 3.8 (de [2])** Si $P_{X,Y}$ est à support plein, le débit optimal est :

$$R^* = H(j(X, g(Y))|g(Y)), \quad (7)$$

où la fonction $j$ renvoie un mot de $U^*$, défini par

$$\begin{gathered} j : \mathcal{X} \times \mathcal{Z} \to U^* \\ (x, z) \mapsto (f(x, y'))_{y' \in g^{-1}(z)}. \end{gathered} \quad (8)$$

# 4 Preuve du Théorème 3.2

## 4.1 Préliminaires

**Définition 4.1 (Coloriage)** Soit $G = (\mathcal{V}, \mathcal{E}, P_V)$ un graphe probabiliste et $C$ un ensemble fini (l'ensemble des couleurs). Une application $c : \mathcal{V} \to C$ est un coloriage si $c^{-1}(i)$ est indépendant pour tout $i \in C$.

**Définition 4.2 (Entropie chromatique $H_\chi$)** L'entropie chromatique d'un graphe probabiliste $G = (\mathcal{V}, \mathcal{E}, P_V)$ est définie par

$$H_{\chi}(G) = \inf \{ H(c(V)) \mid c \text{ est un coloriage } G \}. \quad (9)$$

**Définition 4.3 (produit ET)** Soit $G_1 = (\mathcal{V}_1, \mathcal{E}_1, P_{V_1})$, et $G_2 = (\mathcal{V}_2, \mathcal{E}_2, P_{V_2})$ deux graphes probabilistes, leur produit ET est noté $G_1 \wedge G_2$ et défini par : $\mathcal{V}_1 \times \mathcal{V}_2$ comme sommets avec distribution $P_{V_1} P_{V_2}$, et $(v_1 v_2), (v'_1 v'_2)$ sont adjacents si

$$v_1 v'_1 \in \mathcal{E}_1 \text{ ET } v_2 v'_2 \in \mathcal{E}_2, \quad (10)$$

avec la convention d'auto-adjacence pour tous les sommets. On note $G_1^{\wedge n}$ la n-ième puissance pour le produit ET.

**Définition 4.4 (Entropie complémentaire de graphe $\overline{H}$)** L'entropie complémentaire d'un graphe probabiliste $G$ est définie par $\overline{H}(G) = \lim_{n \to \infty} \frac{1}{n} H_\chi(G^{\wedge n})$.

L'entropie complémentaire $\overline{H}$ caractérise le débit optimal du problème Slepian-Wolf zéro-erreur en Figure 2; elle est égale à $H_\kappa$ dans le cas des graphes parfaits, comme exposé au Théorème 4.6. Notamment, les graphes complets sont parfaits.

**Définition 4.5 (Graphe parfait)** Un graphe probabiliste $G = (\mathcal{V}, \mathcal{E}, P_V)$ est parfait si pour tout $S \subset \mathcal{V}$, $\omega(G[S]) = \chi(G[S])$; où $G[S]$ est le sous-graphe de $G$ induit par $S$, $\omega$ est la taille de la plus grande clique et $\chi$ est le nombre chromatique.

**Théorème 4.6 (de [3], Corollaire 12)** Si $G$ est parfait alors $\overline{H}(G) = H_\kappa(G)$.

**Définition 4.7 (Union disjointe $\sqcup$ de graphes probabilistes)** Soit $A$ un ensemble fini, et soit $P_A \in \Delta(A)$. Pour tout $a \in A$, soit $G_a = (\mathcal{V}_a, \mathcal{E}_a, P_{V_a})$ un graphe probabiliste, l'union disjointe de ces graphes par rapport à $P_A$ est un graphe probabiliste $(\mathcal{V}, \mathcal{E}, P_V)$ noté $\bigsqcup_{a \in A}^{P_A} G_a$ et défini par :

- $\mathcal{V}$ est l'union disjointe des ensembles $(\mathcal{V}_a)_{a \in A}$, i.e. $\mathcal{V} = \bigcup_a \mathcal{V}_a$ et $\mathcal{V}_a \cap \mathcal{V}_{a'} = \emptyset$ pour tout $a \neq a'$;

- Pour tout $v, v' \in \mathcal{V}$, $vv' \in \mathcal{E}$ ssi ils appartiennent au même $\mathcal{V}_a$ et $vv' \in \mathcal{E}_a$;

- $P_V = \sum_{a \in A} P_A(a) P_{V_a}$; notons que les $(P_{V_a})_{a \in A}$ ont des supports disjoints dans $\mathcal{V}$.

$$X^n, (g(Y_t))_{t \le n} \to \boxed{\text{Encoder}} \leftarrow R \leftarrow \boxed{\text{Decoder}} \to X^n, (g(Y_t))_{t \le n}$$

FIGURE 3 : Un problème auxiliaire de codage de source zéro-erreur.
## 4.2 Preuve principale

Considérons le cas particulier où $f(X, Y) = X$ de la Figure 1, qui est représenté en Figure 2. Le débit optimal $R^*$ dans ce cas particulier est égal à celui du problème auxiliaire suivant, illustré dans la Figure 3 : $(X, g(Y))$ comme source disponible à l'encodeur et à retrouver par le décodeur, ce dernier connaît $Y$ (demander que le décodeur retrouve $g(Y)$ en plus de $X$ ne change rien au débit optimal).

Le problème de la Figure 3 est une instance particulière du problème "entrées restreintes" d'Alon et Orlitsky [1], son débit optimal s'écrit alors $\overline{H}(G)$, où $G$ est le graphe de Witsenhausen [11] pour la paire $((X, g(Y)), Y)$; ce graphe a $\mathcal{X} \times \mathcal{Z}$ comme sommets et $(x, z)$ adjacent à $(x', z')$ s'il existe un $Y$ tel que $P_{X,Y,g(Y)}(x, y, z)P_{X,Y,g(Y)}(x', y, z') > 0$.

On remarque la structure particulière de ce graphe : les sommets $(x, z)$ et $(x', z')$ avec $z \neq z'$ ne sont pas adjacents. Le graphe $G$ est donc une union disjointe indexée par $\mathcal{Z}$ :

$$G = \bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z; \qquad (11)$$

$$R^* = \overline{H}(G) = \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z \right); \qquad (12)$$

où pour tout $z \in \mathcal{Z}$, $G_z$ est le graphe de Witsenhausen pour la paire $(X'_z, Y'_z) \sim P_{X,Y|g(Y)=z}$.

(⇒) Supposons que $g$ et $P_{X,Y}$ satisfont la condition "information adjacente partagée deux à deux". On a alors directement que $P_{X|g(Y)=z}$ est à support plein pour tout $z$. Soit $z \in \mathcal{Z}$, et $(x, z)$, $(x', z)$ deux sommets de $G_z$. Par hypothèse, il existe un $y \in g^{-1}(z)$ tel que $P_{X,Y}(x, y)P_{X,Y}(x', y) > 0$; d'où $P_{X,Y,g(Y)}(x, y, z)P_{X,Y,g(Y)}(x', y, z) > 0$, et donc $(x, z)$, $(x', z)$ sont adjacents dans $G_z$. Chaque graphe $G_z$ est alors complet, et donc parfait; le graphe $G = \bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z$ est alors aussi parfait. On a :

$$R^* = \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z \right) \qquad (13)$$

$$= H_{\kappa} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z \right) \qquad (14)$$

$$= \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z) \qquad (15)$$

$$= \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H(P_{X|g(Y)=z}) \qquad (16)$$

$$= H(X|g(Y)); \qquad (17)$$

où (13) vient de (12); (14) résulte du Théorème 4.6 appliqué au graphe parfait $\bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z$; (15) vient de [9, Corollaire 3.4]; et (16) est vraie car les ensembles indépendants du graphe complet $G_z$ sont les singleton contenant chacun de ses sommets.

(←) Réciproquement, supposons $R^* = H(X|g(Y))$ et $P_{X|g(Y)=z}$ est à support plein pour tout $z$. Supposons par l'absurde qu'un des $G_z$ n'est pas complet, il existe alors un coloriage de ce graphe assignant la même couleur à au moins deux sommets. On a alors l'existence d'un $z$ tel que

$$\overline{H}(G_z) < H(P_{X|g(Y)=z}), \qquad (18)$$

car $P_{X|g(Y)=z}$ est à support plein. On a

$$H(X|g(Y)) = R^* \qquad (19)$$

$$= \overline{H} \left( \bigsqcup_{z \in \mathcal{Z}}^{P_g(Y)} G_z \right) \qquad (20)$$

$$\leq \sum_z P_{g(Y)}(z) \overline{H}(G_z) \qquad (21)$$

$$< H(X|g(Y)); \qquad (22)$$

où (20) vient de (12), (21) résulte de [10, Théorème 2], et (22) vient de (18). On arrive à une contradiction, d'où tous les $G_z$ sont complets : pour tout $z \in \mathcal{Z}$ et $x, x' \in \mathcal{X}$, il existe un $y$ tel que $P_{X,Y,g(Y)}(x, y, z)P_{X,Y,g(Y)}(x', y, z) > 0$. Un tel $y$ appartient à $g^{-1}(z)$, et satisfait $P_{X,Y}(x, y)P_{X,Y}(x', y) > 0$. La condition "information adjacente partagée deux à deux" est donc satisfaite par $P_{X,Y}, g$.

# 5 Conclusion

Nous avons étudié un problème de codage de source zéro-erreur pour le calcul de fonction. Lorsqu'elle est satisfaite, la condition "information adjacente partagée deux à deux" sur $P_{X,Y}$ et $g$ permet d'obtenir une expression à une seule lettre pour le débit optimal. Nous avons montré dans ce dernier que cette condition est équivalente à un débit optimal de $H(X|g(Y))$ dans le problème Slepian-Wolf zéro-erreur, avec la même distribution de source $P_{X,Y}$ et avec information adjacente $g(Y)$ à l'encodeur.

# Références

[1] Noga ALON et Alon ORLITSKY : Source coding and graph entropies. *IEEE Transactions on Information Theory*, 1996.

[2] Nicolas CHARPENAY, Maël le TREUST et Aline ROUMY : Zero-error coding for computing with encoder side-information. *arXiv preprint : 2211.03649*, 2022.

[3] Imre CSISZÁR, János KÖRNER, László LOVÁSZ, Katalin MARTON et Gábor SIMONYI : Entropy splitting for antiblocking corners and perfect graphs. *Combinatorica*, 10:27-40, 1990.

[4] Lingyu DUAN, Jiaying LIU, Wenhan YANG, Tiejun HUANG et Wen GAO : Video coding for machines : A paradigm of collaborative compression and intelligent analytics. *IEEE Transactions on Image Processing*, 29:8680-8695, 2020.

[5] Wen GAO, Shan LIU, Xiaozhong XU, Manouchehr RAFIE, Yuan ZHANG et Igor CURCIO : Recent standard development activities on video coding for machines. *arXiv preprint : 2105.12653*, 2021.

[6] J KORNER et Giuseppe LONGO : Two-step encoding for finite sources. *IEEE Transactions on Information Theory*, 1973.

[7] János KÖRNER : Coding of an information source having ambiguous alphabet and the entropy of graphs. *In 6th Prague conference on information theory*, 1973.

[8] Alon ORLITSKY et James R ROCHE : Coding for computing. *In Proceedings of IEEE 36th Annual Foundations of Computer Science*, 1995.

[9] Gábor SIMONYI : Graph entropy : a survey. *Combinatorial Optimization*, 20:399-441, 1995.

[10] Ertem TUNCEL, Jayanth NAYAK, Prashant KOULGI et Kenneth ROSE : On complementary graph entropy. *IEEE Transactions on Information theory*, 55(6), 2009.

[11] Hans WITSENHAUSEN : The zero-error side information problem and chromatic numbers (corresp.). *IEEE Transactions on Information Theory*, 22(5):592-593, 1976.

[12] Hirosuke YAMAMOTO : Wyner-ziv theory for a general function of the correlated sources (corresp.). *IEEE Transactions on Information Theory*, 28(5):803-807, 1982.