chap3.tex 7.63 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
\documentclass[main.tex]{subfiles}

\begin{document}

L'idée du codage prédictif est d'utiliser les corrélations (ressemblances) temporelles ou spatiales du signal à compresser.

\section{Rappels sur la corrélation}

On considère une source $X$ qui émet un signal constitué de $x_1,\dots,x_N$ considérés comme une réalisation d'une suite de variables aléatoires $X_1,\dots,X_N$ de moyenne nulle.

%\img{0.5}{3/1/1}

La fonction de corrélation permet de mesurer la ressemblance entre échantillons voisins :
\[ \gamma_x(n,k) = E(X_nX_{n+k}) \]

Pour un signal stationnaire (dont les caractéristiques statistiques n'évoluent pas au cours du temps :
\[ \gamma_x(n,k) = \gamma_x(k) = E(X_nX_{n+k}), \forall n\]

En pratique, on estime la corrélation à partir des échantillons du signal à compresser.

Estimateur biaisé :
\[ \hat{\gamma_x}(k) = \frac{1}{N}\sum_{i=1}^{N-k} x_i x_{i+k}, \forall k \geq 0 \]

\[ \gamma_x(k) = \frac{1}{N} \sum_{i=-k}^N x_i x_{i+k}, \forall k \leq 0 \]

Avec Matlab, on l'obtient avec :
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
27 28 29 30
% \begin{lstlisting}
% [c,k] = xcorr(x,'biased');
% plot(k,c); grid;
% \end{lstlisting}
31 32

$\gamma_x(k)$ est maximale en 0 et est égale à l'énergie $\sigma^2$ du signal.
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
\section{Codage prédictif en boucle ouverte}
Schéma en boucle ouverte:

\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    \sbEntree{E}
    \node[above] at (E) {$x_n$};
    \sbDecaleNoeudy[5]{E}{mem}
    \sbBloc{mem2}{Mémoire}{mem}
    \sbBlocL{pred}{Prédiction}{mem2}
    \sbRelieryx{E}{mem2}
    \sbDecaleNoeudy[-5]{pred}{comp2}
    \sbComp{comp}{comp2}
    \sbRelierxy{pred}{comp}
    \sbRelier{E}{comp}
    \sbBlocL{Q}{Quantif}{comp}
    \sbBlocL{C}{Codage entropique}{Q}
    \sbSortie[5]{S}{C}
    \sbRelier[0100..1]{C}{S}
  \end{tikzpicture}
  \caption{Emetteur en boucle ouverte}
\end{figure}
\begin{figure}[H]
  \centering
  \begin{tikzpicture}
    \sbEntree{E}
    \sbBlocL{Dc}{Décodeur entropique}{E}
    \sbBlocL{Di}{Desindexation}{Dc}
    \sbSumb[7]{comp}{Di}
    \sbRelier{Di}{comp}
    \sbDecaleNoeudy[5]{comp}{comp2}
    \sbBloc{pred}{Prédicteur}{comp2}
    \sbBlocL{mem}{Mémoire}{pred}
    \sbDecaleNoeudy[-5]{mem}{S}
    \sbSortie[5]{X}{S}
    \sbRelierxy{pred}{comp}
    \sbRelieryx{X}{mem}
    \sbRelier{comp}{X}
  \end{tikzpicture}
  \caption{Recepteur en boucle ouverte}
\end{figure}

Ca marche mais la quantification introduit des erreurs qui peuvent s'accumuler. On s'en sort en réinitialisant le codeur régulièrement.


\subsection{Prédicteur linéaire optimal à 1 pas}
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

On souhaite prédire la valeur de $X_n$ à partir de la valeur de $X_{n-1}$.

Le prédicteur sera linéaire :
\[\hat{X_n} = a_1 X_{n-1} \]

On cherche la valeur de $a_1$ qui minimise $e = E((X_n-\hat{X_n})^2)$

\begin{align*}
e & = E((X_n-a_1X_{n-1})^2) \\
& = E(X_n^2 -a_1^2 X_{n-1}^2 - 2a_1X_{n-1}X_n) \\
& = E(X_n^2) + a_1^2E(X_{n-1}^2) - 2a_1E(X_{n-1}X_n)\\
e & = \gamma_x(0) + a_1^2 \gamma_x(0) - 2a_1 \gamma_x(1)  \text{ par stationnarité}\\
\derivp[e]{a_1}|_{\hat{a_1}} = 0 & \Leftrightarrow 2 \hat{a_1} \gamma_x(0) - 2 \gamma_x(1) = 0\\
& \Rightarrow \hat{a_1} = \frac{\gamma_x(1)}{\gamma_x(0)}
\end{align*}

\begin{rem}
Lorsque le signal sera très corrélé, $\gamma_x(1) \approx \gamma_x(0)$ et $\hat{a_1} \approx 1$. Pour un signal peu corrélé, $\gamma_x(1) \approx 0$ et $\hat{a_1} \approx 0$.
\end{rem}

Pour la valeur de $\hat{a_1}$ obtenue, on a
\begin{align*}
\hat{e} & = \gamma_x(0) + (\frac{\gamma_x(1)}{\gamma_x(0)})^2 \gamma_x(0) - 2 \frac{\gamma_x(1)^2}{\gamma_x(0)} \\
& = \frac{\gamma_x(0)^2-\gamma_x(1)^2}{\gamma_x(0)} \leq \gamma_x(0)
\end{align*}

$\hat{e}$ est l'énergie de la partie qui n'a pas pu être prédite de $x_1,\dots,x_N$.\\

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
109 110
Lorsque le signal est fortement corrélé, $\gamma_x(1)\simeq \gamma_x(0)$ et  $\hat{a_1}\simeq 1$.

111 112 113 114 115 116
Le résidu de prédiction a une variance plus faible. Si on le quantifie, il permettra de reconstituer le signal initial avec une distorsion plus faible.

\newpage
\section{Prédiction à $p$ pas}


Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
117 118 119 120 121 122
On cherche à prédire $\vec{X_n}$ à partir des échantillons précédents $X_{n-1},\dots,X_{n-p}$.

\newcommand{\ap}{\vec{a}}
\newcommand{\Xn}{\vec{X_n}}
\newcommand{\cp}{\vec{c}}
\newcommand{\Rp}{\vec{R}}
123

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
124
\[ \hat{X_n} = a_1 X_{n-1} + \dots + a_pX_{n-p} = \ap^T \Xn \quad\text{avec}\quad \ap^T=(a_1\dots a_p) \text{ et } \Xn^T = (X_{n-1} \dots X_{n-p})\]
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153

On cherche $\ap$ minimisant
\begin{align*}
e & = E((X_n-\hat{X_n})^2) \\
& = E((X_n-\ap^T\Xn)^2) \\
& = E(X_n^2) + \ap^T E(\Xn\Xn^T) \ap -2\ap^t E(X_n\Xn) \\
\text{Or, } E(X_n\Xn)& =(E(X_nX_{n-1}),\dots,E(X_nX_{n-p}))^T \\
& = (\gamma_x(1), \gamma_x(2),\dots,\gamma_x(p))^T = \cp \\
\text{De plus, } E(\Xn\Xn^T) & =
\left[
\begin{array}{cccc}
E(X_{n-1}X_{n-1}) &E(X_{n-1}X_{n-2}) & \dots & E(X_{n-1}X_{n-p}) \\
E(X_{n-2}X_{n-1}) & \ddots & & \vdots \\
\vdots & & \ddots & \vdots \\
E(X_{n-p}X_{n-1}) & \dots & \dots & E(X_{n-p}X_{n-p})
\end{array}
\right] \\
& =
\left[
\begin{array}{cccc}
\gamma_x(0) & \gamma_x(1) & \dots & \gamma_x(p-1) \\
\gamma_x(1) & \gamma_x(0) & & \vdots \\
\vdots & & \ddots & \gamma_x(1) \\
\gamma_x(p-1) & \dots & \gamma_x(1) & \gamma_x(0)
\end{array}
\right] = \Rp\\
\text{ donc } e & = \gamma_x(0) + \ap^T \Rp \ap - 2 \ap^T \cp
\end{align*}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
154
\[ \left.\derivp[e]{\ap}\right|_{\hat{\ap}} =  0  \quad \Leftrightarrow \quad \vec{0} + 2 \Rp\hat{\ap} - 2\cp = 0  \quad \Rightarrow \quad \hat{\ap} = \Rp^{-1} \cp \]
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177

Pour cette valeur de $\hat{\ap}$, on a
\begin{align*}
\hat{e} & = \gamma_x(0) + \cp^T \Rp^{-1} \Rp \Rp^{-1} \cp -2\cp^T\Rp^{-1}\cp \\
& = \gamma_x(0) - \cp^T \Rp^{-1} \cp \leq \gamma_x(0)
\end{align*}

Ce prédicteur à $p$ pas est en général plus efficace que le prédicteur à 1 pas mais il est plus complexe.

\newpage
\section{Mise en oeuvre du prédicteur}

On considère le codeur prédictif de structure suivante à l'émetteur :
%\img{0.4}{3/2/1}

et de structure suivante au décodeur de récepteur:
%\img{0.4}{3/2/2}

On met en œuvre un dispositif de prédiction exploitant les échantillons disponibles au récepteur, de manière à éviter l'accumulation des erreurs de quantification. Il n'y a pas d'accumulation d'erreur de prédiction car le prédicteur est le même à l'émetteur et au récepteur.\\

Pour le réglage du prédicteur, on distingue plusieurs méthodes :

\begin{enumerate}\setlength{\itemsep}{5mm}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
178
\item On calcule $\hat{\gamma_x}$ sur tout le signal et on transmet $\vec{\hat{a}}_{opt}$.
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198

Avantage :
\begin{itemize}
\item sa simplicité de mise ne œuvre
\end{itemize}
Inconvénients :
\begin{itemize}
\item il ne permet pas de tenir compte des non stationnarités
\item on règle le prédicteur à partir de $x_n$ et non de $\hat{x_n}$.
\end{itemize}

\item On découpe le signal en blocs et on recalcule le prédicteur sur chaque bloc.

Avantages :
\begin{itemize}
\item sa simplicité de mise ne œuvre
\item permet de s'adapter aux non-stationnarités
\end{itemize}
Inconvénient :
\begin{itemize}
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
199
\item débit nécessaire à la transmission des $\vec{\hat{a}}_{opt}$.
200 201
\end{itemize}

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
202
\item Mettre en place un prédicteur adaptatif. On travaille sur une fenêtre glissante contenant les N échantillons décalés : $\vec{\hat{X}}_n = (\hat{x}_{n-1}, ..., \hat{x}_{n-N})^T$.
203

Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
204
On calcule $\vec{\hat{a}}_{opt}$ à partir de $\vec{\hat{X}}_n$ (au codeur et au décodeur). On applique $\vec{\hat{a}}_{opt}$ pour coder et décoder $x_n$ en $\hat{x}_n$. À l'itération suivante, on calcule $\vec{\hat{a}}_{opt}$ à partir de $\vec{\hat{X}}_{n+1} = (\hat{x}_{n}, ..., \hat{x}_{n-N+1})^T$.
205 206 207 208

Avantages :
\begin{itemize}
\item Il est très adaptatif.
Pierre-antoine Comby's avatar
Pierre-antoine Comby committed
209
\item On ne transmet plus $\vec{\hat{a}}_{opt}$
210 211 212 213 214 215 216 217 218 219 220 221
\end{itemize}

Inconvénient :
\begin{itemize}
\item et bien... c'est pas simple.
\end{itemize}


\end{enumerate}


\end{document}
222 223 224 225 226

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