chap1.tex 21.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
\documentclass[main.tex]{subfiles}

% Corrigé jusqu'à II.2 inclus. A 03/03/15
% Corrigé en entier. A 22/04/15

\begin{document}
\newcommand{\X}{\mathcal{X}}
\section{Modèles de sources}

On s'intéresse à la compression sans perte d'un message constitué de symboles appartenant à un alphabet fini $\X$.\\

Ces symboles sont:
\begin{itemize}
\item les caractères d'un texte
\item la sortie du quantificateur d'un codeur vidéo.
\item ...
\end{itemize}
\bigbreak
On fait l'hypothèse que le message est une réalisation d'une suite de variables aléatoires $X_1$,...,$X_n$.\\

\subsection{Modèle stationnaire sans mémoire}

C'est le modèle le plus simple, on suppose que:
\begin{itemize}
\item les VA $x_i$ sont distribuées de la même manière, quelque soit $n$ (stationnarité).
\item les VA sont indépendantes entre elles.
\end{itemize}
\smallbreak
C'est un mauvais modèle, mais il est simple.

Pour décrire ce modèle, il suffit de disposer de $p_i = Pr(X_n=i), \quad \forall i \in \X$.\\

\begin{exemple}
On considère une source binaire $X$, à valeurs dans $\X = \{0,1\}$, et

\[p_0 = Pr(X=0),\quad p_1 = Pr(X=1) = 1 - p_0\]
\end{exemple}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
39 40
\begin{defin}
\emph{L'information} associée à chaque symbole de la VA X est \[I(i) = -log_2 p_i \text{ (en bits/symbole)} \]
41 42 43 44 45 46
\end{defin}

\begin{rem}
C'est une fonction décroissante sur ]0,1] qui s'annule en 1. En effet, l'information associée à quelque chose de certain ($p_i=1$) est nulle, alors que celle associée à quelque chose de peu probable ($p_i\rightarrow 0$) est très grande $(\rightarrow \infty)$.
\end{rem}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
47 48
\begin{defin}
L'information moyenne associé aux symboles de $X$ ou à $X$ est appelée \emph{entropie} de la source $X$.
49 50 51 52 53 54
 \[H(X) = -\sum_{i\in\X}p_i log_2(p_i) = \sum_{i\in\X}p_i log_2(\frac{1}{p_i})\]
\end{defin}


On rappelle que $log_2(2^n)=n$.

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
55
\begin{example}
56 57 58 59 60
 Pour la source binaire:

 si $p_0 = 0.5$ et $p_1 = 0.5$ alors $H(X) = 1$ bit/symbole.

 si $p_0 = 0.01$ et $p_1 = 0.99$ alors $H(X) = 0.08$ bit/symbole.
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
61
\end{example}
62

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
63
\begin{prop}[Propriété de l'entropie]
64

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
65
On considère deux VA $X_1$ et $X_2$
66 67
\begin{align*}
H(X_1,X_2) &= - \sum_{i\in \X, j \in \X} Pr(X_1=i,X_2=j)log_2(Pr(X_1=i,X_2=j))\\
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
68 69
&= H(X_2|X_1)+H(X_1)\\
           &= H(X_1)+H(X_2) \iff X_1 \perp X_2
70
\end{align*}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
71 72 73
Plus généralement, si on a N VA iid alors $H(X_1,...,X_N) = N H(X_1)$.\\
Et on a
\[\boxed{H(X) \leq log_2|\X|}\text{ (nombre d'élément de $\X$).}\]
74 75 76 77 78 79
\end{prop}

\subsection{Modèle de Markov d'ordre 1}

\noindent Dans ce modèle, la probabilité d'apparition du symbole $n$ ne dépend que de la réalisation du symbole $n-1$. \\

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
80
Les probabilités de transition vérifient donc pour une source stationnaire :
81 82 83 84
\[Pr(X_n=a_n|X_{n-1} = a_{n-1},X_{n-2} = a_{n-2},...,X_{1} = a_{1}) = Pr(X_n = a_n |X_{n-1} = a_{n-1})\]

On considère des sources de Markov d'ordre 1 stationnaires, donc:
\[Pr(X_n=a_n|X_{n-1} = a_{n-1}) = Pr(X_{n-1} = a_n | X_{n-2} = a_{n-1}), \forall n\]
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
85 86
\begin{defin}
Pour décrire une source de Markov d'ordre 1 stationnaire, il suffit de décrire ses \emph{probabilités de transition :}
87
\[Pr(X_{n}=i|X_{n-1}=j) = p_{i|j},\quad \forall i \in \X, \forall j \in \X\]
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
88
\end{defin}
89 90 91 92 93 94 95 96 97 98 99 100 101 102
\begin{exemple}
Comment estimer les probabilités de transition ?
on a la séquence : a a b b a c a b b a\\
\paragraph{Modèle sans mémoire} on estime $\hat{p_a} = \frac{5}{10}$, $\hat{p_b} = \frac{4}{10}$ et $\hat{p_c} = \frac{1}{10}$\\

\paragraph{Modèle de Markov d'ordre 1}
\begin{align*}
Pr(X_{n}=i,X_{n-1}=j) &= Pr(X_{n}=i|X_{n-2}=j)Pr(X_{n-1}=j)\\
&= \frac{Pr(X_{n}=i,X_{n-2}=j)}{Pr(X_{n-1}=j)}
\end{align*}
Avec $j=a$, si $i=a$ alors \[Pr(X_n=a|X_{n-1}=a) = \frac{\text{nombre de paires aa}}{\text{nombre de paires débutant par a}}=\frac{1}{4}\]
si $i = b$ alors \[Pr(X_n=b|X_{n-1}=a) = \frac{\text{nombre de paires ab}}{\text{nombre de paires débutant par a}}=\frac{2}{4}\]

\end{exemple}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
103 104
\begin{defin}
On défini la matrice de transition :
105

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
106
\[\Pi = (p_{a_j|a_i})_{(i,j)} = \begin{pmatrix}
107 108 109 110
p_{a_1|a_1} & p_{a_2|a_1} & \dots & p_{a_j|a_1}\\
p_{a_1|a_2} & p_{a_2|a_2} & \dots & p_{a_j|a_2}\\
\vdots & & & \\
p_{a_1|a_J} & p_{a_2|a_j} & \dots & p_{a_J|a_J}\\
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
111 112 113 114
\end{pmatrix}\]
avec $J = |\X|$ nombre d'éléments de $\X$.\\
La somme de chaque ligne de $\Pi$ vaut 1.
\end{defin}
115 116 117 118
\begin{exemple}
On considère une source de Markov binaire:
\[p_{0|0} = 0.9, \quad p_{1|0} = 0.1, \quad p_{0|1} = 0.3, \quad p_{1|1} = 0.7\]
On a donc :
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
119
\[\vec{\Pi} = \begin{pmatrix}
120 121 122
0.9&0.1\\0.3&0.7
\end{pmatrix}\]
\end{exemple}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
123 124
\begin{defin}
Pour cette source de Markov, on peut être intéressé par les\emph{ probabilités stationnaires $Pr(x_n=i)$} et on note :
125
\begin{align*}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
126 127
\vec{p}^T &= [Pr(X_n=a_1), \dots, Pr(X_n = a_J)]\\
&= [p_{a_1},...,p_{a_J}]
128 129
\end{align*}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
130 131 132 133
\end{defin}
On peut montrer que $\vec{p}$ satisfait :
\[\boxed{\vec{p}^T = \vec{p}^T\vec{\Pi}}\]
\begin{prop}[Entropie d'une source de Markov d'ordre 1]
134 135 136 137 138 139

\begin{align*}
H(X) &= -\sum_{i \in \X}p_i\sum_{j \in \X}p_{i|j}log_2(p_{i|j})\\
&= -\sum_{i \in \X}\sum_{j \in \X}p_{i,j}log_2(p_{i|j})
\end{align*}
$p_{i,j} = Pr(X_n = i, X_{n-1} = j)$\\
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
\end{prop}
\begin{proof}
  On considère une source de markov d'ordre 1 à valeur dans $\X$ et unvecteur de longueur $n$ de VA de cette source $(X_1 \dots X_n) \in \X^n$:
  \begin{align*}
    H(X_1\dots \X_n) &= - \sum_{x_1,\dots x_n \in \X^n} P((X_1 ... X_n )=(x_1 ..x_n))\log_2(P((X_1 ... X_n )=(x_1 ..x_n)))\\
\intertext{On a modèle d'ordre 1 donc: }
                     &= \sum_{x_1...x_n\in\X^n}P((X_1 ... X_n )=(x_1 ..x_n))\left(\sum_{i=2}^{n}\log_2(P(X_i=x_i|X_{i-1}=x_{i-1}))+\log_2(P_rX_1=x_1)\right)\\
                     &=-\sum_{i=2}^{n}\sum_{x_i,x_{i-1}\in\X^2}P(X_i=x_i,X_{i-1}=x_{i-1})\log_2(P(X_{i}=x_i|X_{i-1}=x_{i-1}))
\intertext{Pour une chaine stationnaire}
                     &= (n-1)\sum_{x_1,x_2\in\X^2}P(X_1=x_1,X_2=x_2)\log_2(P(X_1=x_1|X_2=x_2))+H(X_1)\\
    \intertext{L'entropie par symbole (débit d'entropie) de cette source est alors}
    \lim_{n\to+\infty}\frac{1}{n}H(X_1...X_n) &= -\sum_{x_1,x_2\in\X^2}P(X_1=x_1,X_2=x_2)\log_2(P(X_1=x_1|X_2=x_2))
  \end{align*}
\end{proof}

155

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
156 157 158 159


\begin{rem}
Avec un modèle de Markov, si on essaie de "créer" des mots lettre par lettre, plus on monte dans les ordres, plus la structure de la langue commence à apparaître. À partir de l'ordre 3, il apparaît des mots qui seraient potentiellement de la langue considérée. Ce modèle peut être adapté, comme par exemple pour le correcteur orthographique des téléphones.\\
160 161 162

L'idée générale de la compression d'une source de Markov est d'effectuer des prédictions pour avoir accès aux informations, de sorte qu'il ne reste à transmettre que ce que l'on ne peut pas prédire.\\

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
163 164
\end{rem}

165 166 167 168 169
\section{Codes}

\subsection{Définitions et propriétés}
On considère une source $X$ à valeurs dans $\X = \{a_1,..a_J\}$.

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
170 171
\begin{defin}
Un \emph{code} est un ensemble binaire de $\{0,1\}^*$  (union de tous les ensembles $\{0,1\}^2 = \{00,11,01,10\}$ , $\{0,1\}^3 = ...$ ...). Un code est donc un sous-ensemble de $\{0,1\}^*$.\\
172 173
\end{defin}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
174 175
\begin{defin}
\emph{Une fonction de codage} $c : \X \rightarrow C$ associe à chaque élément de $\X$, un élément de C.\\
176 177
\end{defin}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
178 179
\begin{defin}
La \emph{longueur d'un mot de code} associé à $x \in \X$ est notée \[l(x) = l(c(x)) = \text{ nombre de bits de } c(x)\]
180 181 182 183 184 185 186 187
Pour une source sans mémoire avec $p_j = Pr(X=a_j)$. La longueur moyenne du code C associé à $\X$ est:
\[\overline{l} = \sum_{j=1}^J p_jl(a_j)\]
\end{defin}

L'objectif du codage sans perte est de minimiser $\overline{l}$ tout en étant capable de décoder le code sans ambiguïté.


\begin{defin}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
188
Un code $C$ (et sa fonction de codage associée $c$) est dit \emph{non singulier} si:
189 190 191 192
\[x_1 \neq x_2 \Rightarrow c(x_1) \neq c(x_2) \]
\end{defin}

\begin{defin}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
193 194
\emph{L'extension} $C^*$ d'un code $C$ est l'ensemble de toutes les suites, finies et infinies, de mots provenant du code $C$.
\end{defin}
195 196 197 198 199 200 201 202 203 204 205
\begin{exemple}
Si C $=\{0,10\}$ alors $\{C^*=\{0,10,00,010,100,000,1010,...\}$
\end{exemple}
\begin{prop}
Un code C est décodable de façon unique si son extension $C^*$ est non singulière.\\
Si on prend deux successions de symboles dans $\X$:
\[x_1x_2...x_N \neq x_1'x_2'...x_{N'} \Rightarrow c(x_1,...x_N)=c(x_1)c(x_2)...c(x_N) \neq c(x_1')...c(x_N')\]
\end{prop}

\begin{defin}
Un code C est un code préfixe si aucun mot de code n'est le début d'un autre mot de code.\\
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
206
\end{defin}
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
\begin{exemple}
$\X = \{1,2,3,4\}$\\

\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
X & Singulier & Non singulier & Décodable de manière unique & Préfixe \\
\hline
\hline
1 & 0 & 0 & 10 & 0 \\
\hline
2 & 0 & 010 & 00 & 10 \\
\hline
3 & 0 & 01 & 11 & 110 \\
\hline
4 & 0 & 10 & 110 & 111 \\
\hline
\end{tabular}
\end{center}

\end{exemple}

\begin{rem}
"Décodable de manière unique" implique "Non singulier".
\end{rem}

\subsection{Inégalités}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
235
\begin{prop}[Inégalité de Kraft]
236 237 238 239
Un code binaire préfixe peut exister à condition que ses longueurs de mot de code $l_1,...l_J$ satisfassent:
\[\sum_{j=1}^J2^{-l_j} \leq 1 \]


Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
240
\end{prop}
241 242 243 244 245 246 247 248 249 250 251 252
\begin{proof} Condition nécessaire : \\
Soit $l_{max}$ la plus grande des longueurs.
Le nombre de feuilles à la profondeur $l_{max}$ que peut porter un arbre dont la racine est à la profondeur $l_j$ est $2^{l_{max}-l_j}$.\\

Le nombre maximum de feuilles d'un arbre de profondeur $l_{max}$ est $2^{l_{max}}$.\\

On a $\sum_{j=1}^J2^{l_{max}-l_j} \leq 2^{l_{max}}$ d'où le résultat.\\

Condition suffisante : ?
\end{proof}


Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
253
\begin{prop}[Inégalité de Kraft-McMillan]
254

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
255 256 257 258 259 260
Un code binaire décodable de manière unique peut exister à condition que ses longueurs de mot de code $l_1,...l_J$ satisfassent:
 \[\sum_{j=1}^J2^{-l_j} \leq 1 \]
\end{prop}
\begin{proof}
  Par l'absurde
\end{proof}
261 262 263 264 265 266 267 268 269 270 271 272
\begin{rem}
Attention, ce sont des théorèmes d'existence : ils ne peuvent pas servir à vérifier qu'un code est préfixe ou décodable de manière unique.

\begin{exemple}
Le code $\{1,00,10\}$ n'est pas préfixe, pourtant on a $\sum 2^{-l_i} = 2^{-1} + 2^{-2} + 2^{-2} = 1$. On sait seulement qu'il existe un code préfixe dont les mots de code ont ces longueurs.
\end{exemple}
\end{rem}

\begin{rem}
On sait que "préfixe" implique "décodable de manière unique". En revanche, si un code est décodable de manière unique, on peut seulement dire qu'il existe un code préfixe équivalent, sans qu'il soit le même.
\end{rem}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
273 274
\begin{corol}
Pour qu'un code binaire soit préfixe (ou décodable de manière uniquer), \emph{il faut} que ses longueurs de mot de code $l_1,...l_J$ satisfassent:
275
\[\sum_{j=1}^J2^{-l_j} \leq 1 \]
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
276
\end{corol}
277

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
278
\section{Code de longueur minimale}
279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
On considère une source $X$ sans mémoire d'alphabet $\X = \{a_1,...,a_J\}$ et de probabilités $p_j = Pr(X=a_j)$.
On souhaite construire un code préfixe de longueur moyenne minimale associé à $X$.\\

Si on note $l_1,...,l_J$ les longueurs des mots de codes associés à $a_1,...a_J$ la longueur moyenne sera:
\[\overline{l}=\sum_{j=1}^Jp_jl_j\]

On cherche à minimiser $\overline{l}$ en s'assurant que le code reste préfixe, c'est à dire que:
 \[\sum_{j=1}^J2^{-l_j} \leq 1 \text{ ou } \sum_{j=1}^J2^{-l_j} - 1 \leq 0\]

C'est un problème d'optimisation sans contrainte que l'on résout en introduisant le Lagrangien:
 \[L(l_1,...l_J,\mu) = \sum_{j=1}^Jp_jl_j + \mu\times (\sum_{j=1}^J2^{-l_j} - 1) \text{  avec $\mu$ le multiplicateur de Lagrange}\]

Une condition nécessaire d'optimisation est que:
 \[\left\{ \begin{matrix}
 \frac{\partial L}{\partial l_j}=0 & \forall j=1,...,J\\
 \frac{\partial L}{\partial \mu} = 0
 \end{matrix}\right.\]

 On a donc:
 \[
   \begin{cases}
     \frac{\partial L}{\partial \mu} & = \sum_{j=1}^J2^{-l_j} - 1 = 0 \\
     \frac{\partial L}{\partial l_j} & = p_j-\mu. 2^{-l_j}.\ln2 = 0 \text{	, }\forall j=1,...,J
   \end{cases}
\]

 En sommant ces égalités et en injectant l'égalité précédente de Kraft, on obtient:
 \[\mu = \frac{1}{ln2}\]

 En remplaçant dans $p_j-\mu. \ln2. 2^{-l_j} = 0$, et en passant au log en base 2:
 \[\boxed{l_j = -log_2p_j}\]
 \bigbreak
 \bigbreak
 Pour ce choix de longueurs de mots de code, on obtient:
313 314
 \begin{prop}
    Le meilleur code préfixe a une longueur moyenne au minimum égale à l'entropie de la source.
315
 \[ \boxed{ \overline{l} = \sum_{j=1}^J p_j(-log_2p_j) = H(x)}\]
316
\end{prop}
317 318 319 320
 \begin{rem}
 L'entropie (avec une source sans mémoire) donne une borne supérieure de la quantité d'information réelle contenue dans un message. Dans le cas d'un texte, l'entropie au sens d'une source de Makorv diminue quand on augmente l'ordre, jusqu'à se stabiliser au bout d'un certain ordre.
 \end{rem}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
321 322 323 324 325 326 327 328
 \begin{prop}[Code préfixe à longueur minimale]
   \begin{itemize}
    \item Si $p_i\ge p_j$, $l_i\le l_j$
    \item Les noms de codes associé aux deux symboles les moins probables sont de même longueur
    \item Les noms de codes associé aux deux symboles les moins probables ne diffère que d'un seul bit à la fin.
   \end{itemize}
 \end{prop}

329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
\subsection{Codage de Huffmann}

On considère une source $X$ à valeurs dans $\X$, de probabilités associées $p_i=Pr(X=a_i)$, pour $a_i\in\X$.

\paragraph{Code préfixe à longueur minimale}
Pour qu'un code à longueur variable préfixe $C$ de longueurs de mots de code $l_1,...,l_j$ soit un code de Huffmann, il faut que :
\begin{itemize}
\item $p_i \leq p_j \Rightarrow l_i \geq l_j, \forall i,j$
\item les deux mots de codes associés aux symboles les moins probables aient la même longueur
\item parmi tous les mots de code de longueur maximale, deux d'entre eux ne diffèrent que par le dernier bit.
\end{itemize}

\paragraph{Principe d'un code de Huffmann}
À partir de ces propriétés, on peut fabriquer un code de Huffmann.

Initialement, on considère une source $X^{(0)}$ à $J$ symboles $\X=\{a_1,\dots a_J\}$

\begin{enumerate}
\item On identifie les deux symboles $a_i^{(0)}$ et $a_j^{(0)}$ les moins probables, avec les probabilités associées $p_i^{(0)}$ et $p_j^{(0)}$
\item On fabrique une source fictive $X^{(1)}$ émettant tous les symboles de $\X$ sauf $a_i^{(0)}$ et $a_j^{(0)}$, remplacé par le symbole fictif $a_{ij}^{(0)}$ de probabilité $p_i^{(0)}+p_j^{(0)}$.

$\X^{(1)}$ comporte $J-1$ éléments.

\item On répète 1 et 2 jusqu'à ce qu'il n'y ait plus que deux symboles.
\end{enumerate}

Au bout de $J-2$ itérations, il reste deux symboles $\X^{(J-2)} = \{a_1^{(J-2)},a_2^{(J-1)}\}$. Le premier est identifié avec un 0, le second avec un 1.\\

Si $a_1^{(J-2)}$ est un symbole fictif résultant du regroupement de deux symboles $a_1^{(J-3)}$ et $a_2^{(J-3)}$ alors le code associé à ces deux symboles est obtenu en rajoutant 0 ou 1 au code associé à $a_1^{(J-2)}$.\\

Plus généralement, si $\underline{C}$ est le code associé au symbole fictif $a_i^{k)}$ résultant du regroupement de $a_i^{(k-1)}$ et $a_j^{(k-1)}$, alors le code de $a_i^{(k-1)}$ sera $\underline{C} 0$ et le code de $a_j^{(k-1)}$ sera $\underline{C} 1$.\\

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
361 362 363
\begin{prop}

On montre que la longueur moyenne $\overline{l}$ d'un code de Huffmann associé à une source satisfait \[ H(x) \leq \overline{l} \leq H(X) +1 \]
364 365 366 367

On peut obtenir des codes plus performants en codant des paires de symboles, des triplets... des N-uplets de symboles. Avec ce type de technique, la longueur moyenne $\overline{l}$ par symbole de la source initiale satisfait : \[H(X) \leq \overline{l} \leq H(X)+1 \]

L'inconvénient est la taille de la table de Huffmann à gérer.
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
368
\end{prop}
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443
\newpage
\subsection{Codage arithmétique}

On considère une source binaire $X$ avec $p_0=Pr(X=0)$ et $p_i=Pr(X=i)$.

Cette source génère un message $x_{1:N}$ de longueur $N$.


On va associer un code $\underline{c}(x_{1:N})$ à $x_{1:N}$ qui sera un nombre dans l'intervalle $[0,1[$.

On essaie de représenter $\c(x_{1:N})$ avec peu de bits si $x_{1:N}$ est très probable et avec plus de bits si $x_{1:N}$ est moins probable.

\subsubsection{Algorithme de codage arithmétique (codage d'Elias)}

\paragraph{Initialisation} $l_0=0, \quad h_1 = 1,\quad n=1$

\paragraph{Étapes}
\begin{enumerate}
\item Si $x_n=0$ alors $l_n=l_{n-1}$ et $h_n=l_{n-1}+(h_{n-1}-l_{n-1})p_0$
\item Si $x_n=1$ alors $l_n=l_{n-1}+(h_{n-1}-l_{n-1})p_0$ et $h_n=h_{n-1}$
\item $n = n+1$
\item Si $n\leq N$, aller en 1.
\item On a $h_N-l_N=p(x_{1:N})$
\end{enumerate}

On pose $\mu(x_{1:N}) = \frac{l_N+h_N}{2} \text{ et } \lambda(x_{1:N}) = \lceil - \log_2(p(x_{1:N})) \rceil + 1$

\[ \overline{c}(x_{1:N}) = \lfloor \mu(x_{1:N}) \rfloor _{\lambda(x_{1:N})} \]

$\lfloor a \rfloor _{\lambda}$ est la représentation binaire de $a$ tronquée à $\lambda$ bits. (Exemple : $\lfloor 0,1011 \rfloor _2 = 0,10$)\\

Il faut montrer que $c(x_{1:N}) \in [l_N,h_N[$ (et qu'alors on pourra décoder), et que cette procédure de codage est efficace. \\



\begin{itemize}
\item On sait que $c(x_{1:N}) \leq \mu(x_{1:N})$ et on veut montrer que $\mu(x_{1:N})-c(x_{1:N}) \leq \frac{h_N-l_N}{2}$.\\

Avec par exemple
$\mu(x_{1:N}) = 0,101xxx$ et $c(x_{1:N})=0,101$, alors
\[ \mu(x_{1:N}) - c(x_{1:N}) = 0,000xxx \leq \sum_{i=4}^6 2^{-i} \]


Ainsi dans le cas général,
\[ \mu(x_{1:N}) - c(x_{1:N}) \leq \sum_{i=\lambda(x_{1:N})+1}^{+\infty} 2 ^{-i} = 2^{-\lambda(x_{1:N})} \]

Or, on a $\lambda(x_{1:N}) = -\lceil \log_2(p(x_{1:N})) \rceil + 1$
\[
\begin{array}{ccccc}
- \log_2(p(x_{1:N})) + 1 & \leq & \lambda(x_{1:N}) & < & -\log_2(p(x_{1:N})) + 2 \\
\log_2(p(x_{1:N})) - 1 & \geq & -\lambda(x_{1:N}) & > & \log_2(p(x_{1:N})) - 2 \\
2^{\log_2(p(x_{1:N})) - 1} & \geq & 2^{-\lambda(x_{1:N})} & > & 2^{\log_2(p(x_{1:N})) - 2} \\
\end{array}
\]
\[ \frac{p(x_{1:N})}{2} \geq 2^{-l(x_{1:N})} \]

Ainsi, $\mu(x_{1:N}) - c(x_{1:N}) \leq 2^{-\lambda(x_{1:N})} \leq \frac{p(x_{1:N})}{2} = \frac{h_N-l_N}{2}$ donc  $c(x_{1:N}) \in [l_N,h_N[$ (donc on pourra décoder).

\newpage
\item L'efficacité du codage est montrée en calculant la longueur moyenne du code obtenu :
\[ \overline{l} = \sum_{x_{1:N}\in\X^N} p(x_{1:N}) \lambda(x_{1:N}) \]

En utilisant le premier encadrement de $\lambda(x_{1:N})$, alors
\[ \begin{array}{ccccc}
- \sum_{x_{1:N}} p(x_{1:N})( \log_2(p(x_{1:N}))-1) & \leq & \overline{l} & < & -\sum_{x_{1:N}} p(x_{1:N})(\log_2(p(x_{1:N}))-2) \\
NH(X) + 1 & \leq & \overline{l} & < & NH(X) + 2
\end{array}
\]

Cette procédure est efficace pour $N\to +\infty$, avec l'$\infty$ petit. Par exemple, pour $N=100$, alors la longueur moyenne sera proche à $1\%$ de l'entropie.
\end{itemize}

\paragraph{Décodage}
On part de $c(x_{1:N})$, on réalise le découpage de $[0,1[$ suivant les probabilités d'apparition de 0 et de 1. À chaque étape, l'intervalle auquel appartient $c(x_{1:N})$ permet de déterminer le bit codé.\\

444
\subsubsection{Réalisation pratique}
445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
En pratique, le codage utilise l'intervalle $[0,2^p[$$p$ désigne la précision du codeur arithmétique. (pour le codage H264/AVC, on a $p=9$).
On réalise des homothéties de centre 0, de rapport $2^p$ ou $2^{p-1}$ avec ou sans émission de bits.
On estime les probabilités d'apparition des bits en parallèle du codage au codeur et au décodeur, et on modifie la façon de découper les intervalles en fonction de ces probabilités d'apparition estimées.
On obtient alors un CABAC : Context Adaptative Binary Arithmetic Coder.

\begin{rem}
Si on a plusieurs symboles à coder (A,B,C), on pourrait faire un codeur arithmétique ternaire, mais on préfaire binariser les données (A=00,B=01,C=10) et utiliser un codeur arithmétique binaire, qui est plus pratique pour les remises à l'échelle.
\end{rem}

\newpage
\subsection{Code de Lempel-Ziv-Welch}

\paragraph{Idée}
Avant l'algorithme arithmétique adaptatif, il fallait avoir les probabilités d'apparition des symboles (Huffmann, codage arithmétique,...). Le code LZW permet de faire une compression sans passer par la phase d'estimation des probabilités des symboles. Par exemple pour un texte, l'alphabet est gros, et le codeur arithmétique ne fonctionne pas très bien pour les gros alphabets, car il utilise d'abord une phase de binarisation.\\

\subsubsection{Codage}
Le codage de LZW est une variante des codes LZ77 et LZ78 qui utilise un dictionnaire et n'a pas besoin des probabilités de la source. C'est un cde universel.\\

On considère une source $X$ à valeurs dans $\X=\{a,b,c\}$.

\begin{enumerate}
\item On initialise le dictionnaire de codage à l'aide des symboles de l'alphabet $\X$.
\item On cherche la plus longue suite de symboles restant à coder et appartenant au dictionnaire et on la code.
\item On rajoute cette suite suivi du premier symbole non codé $\omega$ au dictionnaire.
\item Aller en 2 tant qu'il existe des symboles à coder.
\end{enumerate}

\begin{exemple}
On a à coder la séquence $aabababca$.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$a$ & $b$ & $c$ & $aa$ & $ab$ & $ba$ & $aba$ & $abac$ \\
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
\end{tabular}
\end{center}

On code $a$, on émet 0 et on ajoute $aa$ au dictionnaire.

On code $a$, on émet 0 et on ajoute $ab$ au dictionnaire.

On code $b$, on émet 1 et on ajoute $ba$ au dictionnaire.

On code $ab$, on émet 4 et on ajoute $aba$ au dictionnaire.

On code $aba$, on émet 6 et on ajoute $abac$ au dictionnaire.

On code $c$, on émet 2.

\end{exemple}

\subsubsection{Décodage}
Le décodage se fait
\begin{enumerate}
\item à partir du dictionnaire initial
\item à chaque décodage d'un mot, on rajoute ce mot suivi de $\omega$ au dictionnaire
\item $\omega$ n'est déterminé que si on a décodé le mot suivant
\end{enumerate}

\begin{exemple}
On a à décoder 001462.\\

On décode $a$, on ajoute $a\omega$ (3) au dictionnaire.

On décode $a$, donc le (3) est $aa$ et on ajoute $a\omega$ (4) au dictionnaire.

On décode $b$, donc le (4) était $ab$ et on ajoute $b\omega$ (5) au dictionnaire.

On décode $ab$, donc le (5) était $ba$ et on ajoute $ab\omega$ (6) au dictionnaire.

On décode $ab\omega$, qui était en fait un $aba$ et on ajoute $aba\omega$ (7) au dictionnaire.

On décode $c$ donc le (7) était $abac$.
\end{exemple}

En pratique :
\begin{itemize}
\item les codes générés sont à nouveau codés à l'aide d'un code de Huffmann
\item la taille du dictionnaire est limitée, les mots les moins utilisés sont effacés.
\end{itemize}

\end{document}
530 531 532 533 534

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: