chap3.tex 6.31 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 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 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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 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 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
\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 :
\begin{lstlisting}
[c,k] = xcorr(x,'biased');
plot(k,c); grid;
\end{lstlisting}

$\gamma_x(k)$ est maximale en 0 et est égale à l'énergie $\sigma^2$ du signal.

\newpage
\section{Prédicteur optimal à 1 pas}

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$.\\

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}

On cherche à prédire $X_n$ à partir des échantillons précédents $X_{n-1},\dots,X_{n-p}$.

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

\[ \hat{X_n} = a_1 X_{n-1} + \dots + a_pX_{n-p} = \ap^T \Xn \quad \text{ avec} \ap^T=(a_1\dots a_p) \text{ et } \Xn^T = (X_{n-1} \dots X_{n-p})\]

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*}

\[ \left.\derivp[e]{\ap}\right|_{\hat{\ap}} =  0  \quad \Leftrightarrow \quad \underline{0} + 2 \Rp\hat{\ap} - 2\cp = 0  \quad \Rightarrow \quad \hat{\ap} = \Rp^{-1} \cp \]

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}
\item On calcule $\hat{\gamma_x}$ sur tout le signal et on transmet $\underline{\hat{a}}_{opt}$.

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}
\item débit nécessaire à la transmission des $\underline{\hat{a}}_{opt}$.
\end{itemize}

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

On calcule $\underline{\hat{a}}_{opt}$ à partir de $\underline{\hat{X}}_n$ (au codeur et au décodeur). On applique $\underline{\hat{a}}_{opt}$ pour coder et décoder $x_n$ en $\hat{x}_n$. À l'itération suivante, on calcule $\underline{\hat{a}}_{opt}$ à partir de $\underline{\hat{X}}_{n+1} = (\hat{x}_{n}, ..., \hat{x}_{n-N+1})^T$.

Avantages :
\begin{itemize}
\item Il est très adaptatif.
\item On ne transmet plus $\underline{\hat{a}}_{opt}$
\end{itemize}

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


\end{enumerate}


\end{document}