%----------------------------------------------------------------
%	DEUG STPI 1\`ere ann\'ee \\
%	D\'ecouverte : Informatique \\
%	Cours~3 \\
%	semaine du 11 octobre 1999 \\

\newpage

%----------------------------------------------------------------
\section{Codage : changement de base}
Les informations traît\'ees par l'ordinateur sont de diff\'erents types 
(nombres, instructions, images, s\'equences d'images anim\'ees, son, ...)
mais elles sont toujours repr\'esent\'ees et manipul\'ees par l'ordinateur 
sous forme binaire. \\

Une information \'el\'ementaire correspond donc \`a un chiffre binaire 
($0$ ou $1$) appel\'e {\bf bit}. 
Une information plus complexe, telle qu'un caract\`ere ou un nombre 
se ram\`ene \`a un ensemble de bits (suite de $0$ et de $1$). 
Le codage d'une information consiste \`a trouver une correspondance 
entre la repr\'esentation externe de l'information 
(le caract\`ere A, le nombre 1986, ...) et sa repr\'esentation interne
qui est une suite de bits.\\

L'avantage de la repr\'esentation binaire est qu'elle est facile \`a r\'ealiser 
techniquement, \`a l'aide de bistables (syst\`emes \`a deux \'etats d'\'equilibre). 
\\

%\subsection{Changement de base}
%------------------------------

Pour la repr\'esentation des nombres, on doit d'abord effectuer 
un changement de base pour les repr\'esenter en base $2$ 
(repr\'esentation binaire) dans la m\'emoire de la machine. 

\subsection{Syst\`eme de num\'eration}

Un syst\`eme de num\'eration fait correspondre \`a un nombre $N$ un certain 
symbole d'un ensemble $B$ donn\'e. 
Dans un syst\`eme de base $b>1$ ($B=\{0, 1, ..., b-1\}$), les nombres 
$0, 1, ..., b-1$ sont appel\'es {\em chiffres}.\\

Un nombre entier positif peut-\^etre repr\'esent\'e par une expression 
de la forme~:
$$
N = a_{n} \cdot b^{n} + a_{n-1} \cdot b^{n-1} 
+ ... + a_{1} \cdot b^{1} + a_{0} \cdot b^{0}
= \sum_{i=0}^{n} a_{i} \cdot b^{i}
$$
avec $a_{i} \in \{0, ..., b-1\}$ et $a_{n} \neq 0$.\\

En notation condens\'ee, le nombre $N$ s'\'ecrit d'une fa\c{c}on \'equivalente 
sous la forme :
$$
N = a_{n}a_{n-1}...a_{1}a_{0}.
$$

\begin{tabular}{lll}
En d\'ecimal,     & $b = 10$, & $a_{i} \in \{0, ..., 9\}$ \\
En binaire,     & $b = 2$,  & $a_{i} \in \{0, 1\}$ \\
En octal,       & $b = 8$,  & $a_{i} \in \{0, ..., 7\}$ \\
En hexad\'ecimal, & $b = 16$, & $a_{i} \in \{0, ..., 9, A, ..., F\}$ \\
\end{tabular}

\begin{exemple}
Le nombre d\'ecimal $20 \; (b=10, \; 20 = 2 \cdot 10^{1} + 0 \cdot 10^{0})$ 
est repr\'esent\'e en binaire $(b=2)$ par $10100$, soit 
$1 \cdot 2^{4} + 0 \cdot 2{3} + 1 \cdot 2^{2} + 0 \cdot 2^{1} + 0 \cdot 2^{0}$. 
Ce qui s'\'ecrit : $20_{10} = 10100_{2}$. \\
En base $16$ :  $20_{10} = 14_{16}$. \\
\end{exemple}

Une table de conversion pour simplifier les calculs~:
$$
\begin{tabular}{|r|r|r|r|}
\hline
d\'ecimal & binaire & octal & hexad\'ecimal \\ \hline \hline
 0 &     0 &  0 &  0 \\ \hline 
 1 &     1 &  1 &  1 \\ \hline 
 2 &    10 &  2 &  2 \\ \hline 
 3 &    11 &  3 &  3 \\ \hline 
 4 &   100 &  4 &  4 \\ \hline 
 5 &   101 &  5 &  5 \\ \hline 
 6 &   110 &  6 &  6 \\ \hline 
 7 &   111 &  7 &  7 \\ \hline 
 8 &  1000 & 10 &  8 \\ \hline 
 9 &  1001 & 11 &  9 \\ \hline 
10 &  1010 & 12 &  A \\ \hline 
11 &  1011 & 13 &  B \\ \hline 
12 &  1100 & 14 &  C \\ \hline 
13 &  1101 & 15 &  D \\ \hline 
14 &  1110 & 16 &  E \\ \hline 
15 &  1111 & 17 &  F \\ \hline 
16 & 10000 & 20 & 10 \\ \hline 
\end{tabular}
$$

\subsection{Conversion binaire - d\'ecimal}
%-------------------------------------------------------

\subsection*{binaire $\rightarrow$ d\'ecimal~:}
%---------------------------------------------

La conversion se fait simplement en additionnant les puissances de $2$
correspondant aux bits de valeur $1$ (voir exemple ci-dessus).

\begin{remarque}
Cette m\'ethode peut-\^etre utilis\'e pour passer d'une base quelconque 
\`a la base $10$.
\end{remarque}

\subsection*{d\'ecimal $\rightarrow$ binaire~:}
%---------------------------------------------

La convesrion s'effectue par divisions enti\`eres successives par $2$. 
On s'arr\^ete d\`es qu'on obtient un quotient nul. 
Le nombre binaire est obtenu en lisant les restes du dernier vers 
le premier.
\begin{exemple}.\\
\begin{tabular}{cccccc}
25 &  2 &    &    &    &    \\ \cline{2-2}
\entourer{1} & 12 &  2 &    &    &    \\ \cline{3-3}
   &  \entourer{0} &  6 &  2 &    &    \\ \cline{4-4}
   &    &  \entourer{0} &  3 &  2 &    \\ \cline{5-5}
   &    &    &  \entourer{1} &  1 &  2 \\ \cline{6-6}
   &    &    &    &  \entourer{1} &  0 \\
\end{tabular}

$\Longrightarrow 25_{10} = 11001_{2}.$
\end{exemple}

%\epsfig{file=ex-dec-bin.eps}

\begin{remarque}
Le premier reste obtenu est le chiffre de poids faible (le plus \`a droite) 
de la repr\'esentation en base $2$. 
Le dernier reste obtenu est le chiffre de poids fort (le plus \`a gauche).
\end{remarque}

\subsection{Codages hexad\'ecimal et octal}
%-------------------------------------------

Les codages hexad\'ecimal (base $16$) et octal (base $8$) sont aussi 
des codages tr\`es utilis\'es en informatique pour deux raisons~:
\begin{itemize}
\item[$\bullet$] 
les conversions entre les bases $16$ (ou $8$) et $2$ sont tr\`es simples  
(plus simple qu'entre $10$ et $2$)~;
\item[$\bullet$] 
le codage est beaucoup plus compact (plus court).
\end{itemize}

Les conversions de la base $10$ en base $16$ ($8$) se font en utilisant 
le m\^eme principe que pour les conversions de la base $10$ vers la base $2$, 
c'est-\`a-dire en effectuant des divisions successives par $16$ ($8$), 
dont les restes forment la repr\'esentation en base $16$ ($8$).

\subsection*{Conversion hexad\'ecimal (octal) $\rightarrow$ binaire~:}
%--------------------------------------------------------------------

La conversion correspond \`a un ``\'eclatement'' de chaque chiffre hexad\'ecimal 
(octal) en son \'equivalent binaire sur $4$ ($3$) bits. 
\begin{exemple}
$2A_{16} = 0010 \; 1010_{2}$ 
car $2_{16} = 0010_{2}$ et $A_{16} = 1010_{2}$. \\
$17_{8} = 001 \; 111_{2}$ 
car $1{8} = 001_{2}$ et $7_{8} = 111_{2}$. 
\end{exemple}

\subsection*{Conversion binaire $\rightarrow$ hexad\'ecimal (octal)~:}
%--------------------------------------------------------------------

On effectue un remplacement, de droite \`a gauche, de $4$ ($3$) bits 
par le chiffre hexad\'ecimal (octal) correspondant. 
Si le nombre de bits n'est pas multiple de $4$ ($3$), 
on compl\`ete \`a gauche avec des z\'eros. 
\begin{exemple}
$101101_{2} = 2D_{16} = 55_{8}$.
\end{exemple}

\subsection{Arithm\'etique en base $2$}
%---------------------------------------

On peut effectuer des calculs dans une base autre que la base $10$. 
Il suffit d'avoir la table d'op\'eration des op\'erateurs arithm\'etiques 
dans cette base. 
Par exemple en binaire : 
\begin{center}
\begin{tabular}{c|c|r}
$+$ & $0$ &  $1$ \\ \hline
$0$ & $0$ &  $1$ \\ \hline
$1$ & $1$ & $10$ 
\end{tabular}
\hs \hs \hs
\begin{tabular}{c|c|r}
$\times$ & $0$ & $1$ \\ \hline
$0 $     & $0$ & $0$ \\ \hline
$1$      & $0$ & $1$ 
\end{tabular}
\end{center}

\begin{exemple}
En binaire~: 
\begin{center}
\begin{tabular}{rccccc}
    &     & $1$ & $0$ & $1$ & $1$ \\
$+$ &     &     & $1$ & $0$ & $1$ \\ \hline
    & $1$ & $0$ & $0$ & $0$ & $0$ 
\end{tabular}
\hs \hs \hs
\begin{tabular}{rccccc}
         &     &     & $1$ & $0$     & $1$     \\
$\times$ &     &     & $1$ & $1$     & $0$     \\ \hline
         &     &     & $0$ & $0$     & $0$     \\
$+$      &     & $1$ & $0$ & $1$     & $\cdot$ \\
         & $1$ & $0$ & $1$ & $\cdot$ & $\cdot$ \\ \hline
         & $1$ & $1$ & $1$ & $1$     & $0$ 
\end{tabular} 
\end{center}
De m\^eme, en hexad\'ecimal~: 
\begin{center}
\begin{tabular}{rcccc}
    & $1$ & $3$ & $B$ & $9$ \\
$+$ &     & $A$ & $3$ & $4$ \\ \hline
    & $1$ & $D$ & $E$ & $D$ 
\end{tabular}
\end{center}
\end{exemple}

%======================================================================