91 lines
3.3 KiB
TeX
91 lines
3.3 KiB
TeX
|
\documentclass{article}
|
||
|
|
\input{../../preambule/preambule}
|
||
|
|
|
||
|
|
\newcommand{\nom}{TD2 : Random TD}
|
||
|
|
\renewcommand{\nomentete}{UE455 - \nom}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
\begin{document}
|
||
|
|
|
||
|
|
\titre{\nom}
|
||
|
|
|
||
|
|
\cacededi{Tu vois E.? Il a renversé sa bière sur le Mac Book de B. Alors B. était vénère. Du coup il lui a sucé la bite.}{Cédric Colonna}
|
||
|
|
|
||
|
|
\section*{Exercice 3 : Code préfixe pour les entiers}
|
||
|
|
|
||
|
|
\begin{enumerate}\setlength{\itemsep}{1cm}
|
||
|
|
\item Si $\forall k,k \leq m$, alors il faut $\lceil \log_2 k \rceil$ ($\log_2 k$ arrondi au supérieur). Les codes sont ici tous de la même longueur, donc ce codage est préfixe.
|
||
|
|
|
||
|
|
\item $\lceil \log_2 k \rceil$ donne la taille du nombre $k$ codé.
|
||
|
|
|
||
|
|
\begin{center}
|
||
|
|
\begin{tabular}{|c|c|c|}
|
||
|
|
\hline
|
||
|
|
$k$ & $\lceil \log_2 k \rceil$ & $C(k)$ \\
|
||
|
|
\hline
|
||
|
|
0 & 0 & 10 \\
|
||
|
|
\hline
|
||
|
|
1 & 0 & 11 \\
|
||
|
|
\hline
|
||
|
|
2 & 1 & 0110 \\
|
||
|
|
\hline
|
||
|
|
\end{tabular}
|
||
|
|
\end{center}
|
||
|
|
|
||
|
|
\item $ C_1(k)$ est-il préfixe ?
|
||
|
|
|
||
|
|
On prend $k_1 \neq k_2$
|
||
|
|
|
||
|
|
\begin{itemize}
|
||
|
|
\item si $\lceil \log_2 k_1 \rceil = \lceil \log_2 k_2 \rceil$, alors la 2e partie du code est différente. Les deux codes font la même longueur mais sont différents, donc c'est préfixe.
|
||
|
|
\item si $\lceil \log_2 k_1 \rceil < \lceil \log_2 k_2 \rceil$, alors la 1e partie du code est différente, donc c'est préfixe.
|
||
|
|
\end{itemize}
|
||
|
|
|
||
|
|
\item $l_1(k) = \lceil \log_2 k \rceil + 1 + \lceil \log_2 k \rceil = 2\lceil \log_2 k \rceil + 1 = 2 \log_2 k + \mathcal{O}(1)$
|
||
|
|
|
||
|
|
\item On code $\lceil \log_2 k \rceil$ avec $C_1$ : $C_2(k) = C_1(\lceil \log_2 k \rceil)x...x$ où $x...x$ est $k$ en binaire.
|
||
|
|
|
||
|
|
On a alors $l_2(k) = 2 \lceil \log_2 ( \lceil \log_2 k \rceil ) \rceil + \lceil\log_2 k \rceil = 2 \log_2 (\log_2 k) + \log_2 k + \mathcal{O}(1)$
|
||
|
|
\end{enumerate}
|
||
|
|
|
||
|
|
\section*{Exercice 5 : Distribution de redondance minimale}
|
||
|
|
|
||
|
|
On considère un code préfixe : $C=\{C_1,C_J\}$ dont la longueur de chaque mot de code est $l_i, i = 1 \dots J$.
|
||
|
|
|
||
|
|
On considère une source $X$ dont l'alphabet est $A=\{a_1,...a_J\}$ et le vecteur de probabilités $\underline{p}=[p_1, \dots p_J]$.
|
||
|
|
|
||
|
|
\newcommand{\p}{\underline{p}}
|
||
|
|
|
||
|
|
\begin{enumerate}\setlength{\itemsep}{1cm}
|
||
|
|
\item Donner l'entropie de la source .
|
||
|
|
|
||
|
|
\[H(\p) = - \sum_{i=1}^J p_i \log_2 p_i\]
|
||
|
|
|
||
|
|
\item Donner la longueur moyenne du code.
|
||
|
|
|
||
|
|
\[l(C,\p) = \sum_{i=1}^J p_i l_i \]
|
||
|
|
|
||
|
|
\item Donner la redondance du code
|
||
|
|
\[ R(C,\p) = l(c,\p) - H(\p) = \sum_{i=1}^J p_i (l_i + \log_2 p_i) \]
|
||
|
|
|
||
|
|
On veut chercher $\p$ qui va minimiser $R(c,\p)$
|
||
|
|
|
||
|
|
\item Quelles sont les contraintes que doivent satisfaire les composantes de $\p$ ?
|
||
|
|
\[ \sum_{i=1}^J p_i=1 \quad \et \quad \forall i=1,\dots J, \quad 0 \leq p_i \leq 1\]
|
||
|
|
|
||
|
|
\item Un problème d'optimisation sous contraintes. Minimiser $R=\sum_{i=1}^J p_i (l_i + \log_2 p_i)$
|
||
|
|
|
||
|
|
\item On utilise le lagrangien :
|
||
|
|
\[ L(\p,\ld) = \sum_{i=1}^J p_i(l_i+\log_2 p_i) + \ld(\sum_{i=1}^J p_i-1) \]
|
||
|
|
|
||
|
|
\item Condition d'optimalité :
|
||
|
|
\begin{align*}
|
||
|
|
\acc{\drond{L}{p_i}(\p^*,\ld^*)&=0, \quad \forall i = 1,\dots J}{\drond{L}{\ld}(\p^*,\ld^*)&=0} & \Leftrightarrow \acc{l_i + \log_2p_i^* + \log_2 e + \ld^* & = 0}{\sum_{i=1}^J p_i^*-1 & =0}\\
|
||
|
|
& \Leftrightarrow \acc{p_i^* & = 2^{-l_i - \ld^* - \log_2 e} }{1 & = \sum_{i=1}^J 2^{-l_i}2^{-\ld^*-\log_2 e}} \\
|
||
|
|
& \Leftrightarrow \acc{p_i^* & = 2^{-l_i}2^{- \ld^* - \log_2 e} }{2^{-\ld^*-\log_2 e} & = \frac{1}{\sum_{i=1}^J 2^{-l_i}}}
|
||
|
|
\end{align*}
|
||
|
|
\[ \boxed{ p_i^*= \frac{2^{-l_i}}{\sum_{i=1}^J 2^{-l_i}}} \]
|
||
|
|
\end{enumerate}
|
||
|
|
|
||
|
|
\end{document}
|