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

\newpage

%----------------------------------------------------------------
\section{Codage : repr\'esentation en machine}

Lorsque  l'on veut repr\'esenter des informations en machine,  nous
rencontrons  une difficult\'e suppl\'ementaire : non  seulement  nous
devons repr\'esenter toutes les informations sous forme de suite de
0  et  de  1, mais en plus le nombre de bits dont nous  disposons
pour  cette  repr\'esentation est limit\'e par la  taille  des  mots
m\'emoire qu'est capable de traiter l'unit\'e centrale. 
Ainsi, en pratique, nous ne pouvons pas repr\'esenter n'importe 
quel nombre. \\

On distingue deux types de donn\'ees : 
les donn\'ees num\'eriques pouvant faire l'objet d'une op\'eration 
arithm\'etique, et les donn\'ees non num\'eriques, par exemple les symboles
constituants un texte. 

\subsection{Repr\'esentation des entiers}
%--------------------------------------

\subsubsection{Entiers non sign\'es}
%---------------------------------

Dans un registre de $p$ positions, seuls les entiers positifs $N$ 
tels que $0 \leq N \leq 2^{p}-1$ peuvent \^etre repr\'esent\'es. 
On parle de registre de longueur $p$. 

En effet, en remarquant que le plus grand entier $N$ repr\'esentable sur  
$p$ bits correspond \`a la repr\'esentation constitu\'ee de $p$ bits valant $1$,
on a 
$$
N = \sum_{i=0}^{p-1} 2^{i} = 2^{p} - 1.
$$
Par suite, le nombre de valeurs distinctes repr\'esentables sur $p$ bits
est $2^{p}$.

\begin{exemple}
Avec $p=4$, 
le plus petit entier positif repr\'esentable est $0000_{2} = 0_{10}$ 
et le plus grand entier repr\'esentable est $1111_{2} = 15_{10}$.
Ce qui donne $16$ valeurs possibles. 
\end{exemple}

\subsubsection{Entiers sign\'es}
%-----------------------------

Nous devons repr\'esenter en plus de l'entier, son signe. 
De plus, la repr\'esentation doit, d'une part, 
permettre de tester facilement si le nombre est positif ou n\'egatif, 
et d'autre part, utiliser (de pr\'ef\'erence) les m\^emes circuits pour effectuer 
les op\'erations sur les entiers sign\'es ou non sign\'es.\\

Les entiers n\'egatifs peuvent \^etre cod\'es selon plusieurs m\'ethodes.
Nous citons par exemple :
\begin{itemize}
\item 
signe et valeur absolue,
\item
compl\'ement \`a 1 (compl\'ement logique),
\item
compl\'ement \`a 2 (compl\'ement arithm\'etique).
\end{itemize}

Nous nous int\'eresserons particuli\`erement au codage en compl\'ement \`a 2 
qui reste le plus utilis\'e aujourd'hui pour repr\'esenter 
l'oppos\'e d'un entier.

\subsubsection*{Technique}
Le calcul du compl\'ement \`a deux d'un entier en base deux, 
s'op\`ere en trois \'etapes : 
\begin{enumerate}
\item 
calculer sa repr\'esentation binaire sur $p$ bits,
\item 
compl\'ementer tous les bits ; c'est-\`a-dire remplacer chaque bit \`a $0$ par $1$, 
et vice-versa (\`a ce stade ci, on a obtenu le compl\'ement \`a $1$),
\item
ajouter $1$ au r\'esultat.
\end{enumerate}

Une autre technique couramment utilis\'ee est la suivante~:
\begin{itemize}
\item 
parcourir la chaine de bits de droite \`a gauche jusqu'au premier bit \`a $1$,
\item 
inverser tous les bits \`a gauche du bit trouv\'e 
(ce bit ne doit pas \^etre modifi\'e).
\end{itemize}

\begin{exemple}
Repr\'esenter $(-6)$ sur quatre bits (en compl\'ement \`a $2$)~:
\begin{enumerate}
\item
$+ 6 = 0110$
\item 
compl\'ement \`a $1$ : 1001
\item
compl\'ement \`a $2$ : $1001 + 1 = 1010$\\
$\Longrightarrow -6 = 1010$ (en compl\'ement \`a $2$).
\end{enumerate}
\end{exemple}

\begin{remarque}
Dans la repr\'esentation en compl\'ement \`a 2, le bit le plus \`a gauche 
indique le signe : $0$ pour $+$, et $1$ pour $-$ 
(l'entier 0 est consid\'er\'e comme un entier positf).
\end{remarque}

\begin{exemple}
Codage sur trois bits : 
$$
\begin{tabular}{|r||c|c|c|c|c|c|c|c|}
\hline
Code   & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\
\hline
Valeur &  +0 &  +1 &  +2 &  +3 &  -4 &  -3 &  -2 &  -1 \\
\hline 
\end{tabular}
$$
\end{exemple}

\subsubsection*{
Comment retrouver la valeur d'un entier sign\'e \`a partir de son codage~?}
\begin{itemize}
\item[$\bullet$] 
Si le bit le plus \`a gauche est $0$, il s'agit d'un entier positif. 
Il suffit d'effectuer une conversion binaire $\rightarrow$ d\'ecimal.
\item[$\bullet$] 
Si le bit le plus \`a gauche est $1$, il s'agit d'un entier n\'egatif. 
Sa valeur s'obtient en prenant son oppos\'e (compl\'ement \`a 2) 
puis en effectuant une conversion binaire $\rightarrow$ d\'ecimal 
et en mettant le signe $-$ devant la valeur obtenue.
\end{itemize}

\begin{remarque}
Le nombre de valeurs qu'on peut repr\'esenter (en base 2) sur $p$ bits 
\'etant $2^{p}$, le codage en compl\'ement \`a 2 obeit aux principes suivants :
\begin{itemize}
\item 
les entiers positifs sont repr\'esent\'es sur les $p-1$ bits de droite
et le bit le plus \`a gauche vaut $0$,
\item 
les entiers n\'egatifs $N$ sont cod\'es sous la forme $2^{p} - N$ 
(ce qui s'appelle prendre le compl\'ement \`a 2 de $N$).
\end{itemize}
\end{remarque}

\begin{remarque}
les entiers positifs \'etant repr\'esent\'es sur $p-1$ bits, donc 
\begin{itemize}
\item 
ils sont au nombre de $2^{p-1}$, et 
\item 
le plus grand entier positif repr\'esentable (en compl\'ement \`a 2) 
est $2^{p-1} - 1$.
\end{itemize}
\end{remarque}

\begin{remarque}
Le nombre de valeurs possibles sur $p$ bits \'etant $2^{p}$, 
il nous reste alors $2^{p-1}$ valeurs possibles pour les entiers 
n\'egatifs. D'o\`u le plus petit entier n\'egatif repr\'esentable 
(en compl\'ement \`a 2) est $-2^{p-1}$.
\end{remarque}

\subsubsection*{Additions sign\'ees}
%---------------------------------
Une des particularit\'es de la repr\'esentation en compl\'ement \`a 2 
est que les additions s'effectuent de la m\^eme mani\`ere que sur 
les entiers non sign\'es. 
De plus, nous obtenons un moyen simple d'effectuer les soustractions 
sans qu'il soit n\'ecessaire de passer par un circuit sp\'ecifique.

\begin{exemple}
Effectuer les op\'erations suivantes (sur 8 bits) :
\begin{enumerate}
\item
$ 
(+52)_{10} + (+41)_{10} = ? \\
\begin{tabular}{rccccccccc}
$52$ & $\longrightarrow$ & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\
$41$ & $\longrightarrow$ & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\
\hline 
$93$ & $\longrightarrow$ & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1
\end{tabular}
$
\item 
$ 
-36_{10} - 67_{10} = (-36)_{10} + (-67)_{10} = ? \\
36_{10} \rightarrow 100100_{2} \rightarrow 00100100 
\rightarrow 11011100 \rightarrow -36_{10} \\
67_{10} \rightarrow 1000011_{2} \rightarrow 01000011 
\rightarrow 10111101 \rightarrow -67_{10} \\
\begin{tabular}{rccccccccc}
$-36$  & $\longrightarrow$ & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\
$-67$  & $\longrightarrow$ & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\
\hline 
$-103$ & $\longrightarrow$ & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1
\end{tabular}
$
\item 
$ 
123_{10} - 87_{10} = (+123)_{10} + (-87)_{10} = ? \\
+123_{10} \rightarrow 1111011_{2} \rightarrow 01111011 \\
87_{10} \rightarrow 1010111_{2} \rightarrow 01010111 
\rightarrow 10101001 \rightarrow -87_{10} \\
\begin{tabular}{rccccccccc}
$123$  & $\longrightarrow$ & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \\
$-87$  & $\longrightarrow$ & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\
\hline 
$36$ & $\longrightarrow$ & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0
\end{tabular}
$
\end{enumerate}
\end{exemple}


Le dernier r\'esultat s'obtient en tronquant \`a $8$ bits le r\'esultat 
de l'addition. 
Cette troncature est normale et le r\'esultat est correct.
\\

Cependant, des erreurs de d\'epacement de capacit\'e peuvent survenir 
lorsque le r\'esultat de l'addition n'est pas repr\'esentable sur 
le m\^eme nombre de bits que les op\'erandes. 
\\

Dans le cas des entiers sign\'es repr\'esent\'es en compl\'ement \`a 2, 
il y a {\bf d\'epacement de capacit\'e} \underline{si et seulement si} 
l'addition de deux valeurs de {\bf m\^eme signe} produit un r\'esultat 
de {\bf signe diff\'erent}.

\begin{exemple} 
(sur 8 bits) \\
$(+105)_{10} + (+87)_{10} = ? $\\
\begin{tabular}{rcccccccccl}
$105$ & $\longrightarrow$ & 
$0$ & $1$ & $1$ & $0$ & $1$ & $0$ & $0$ & $1$ & $> 0$ \\
$ 87$ & $\longrightarrow$ & 
$0$ & $1$ & $0$ & $1$ & $0$ & $1$ & $1$ & $1$ & $> 0$ \\
\hline 
$192$ & $\longrightarrow$ & 
$1$ & $1$ & $0$ & $0$ & $0$ & $0$ & $0$ & $0$ & $< 0$ !!
\end{tabular}
\end{exemple}

Ce r\'esultat est manifestement faux puisque nous obtenons une valeur 
n\'egative (bit de signe \`a $1$) en additionnant deux nombres positifs.

\subsection{Repr\'esentation des caract\`eres}
%-----------------------------------------

Les donn\'es non num\'eriques correspondent aux caract\`eres 
\begin{itemize}
\item[$\bullet$]  alphanum\'eriques :
A, B, ..., Z, 0, 1, ..., 9 
\item[$\bullet$]  sp\'eciaux :
?, !, ``, \$, ;, etc.
\end{itemize}

La principale contrainte concernant les caract\`eres est l'ordre alphab\'etiques. 
Le caract\`ere A doit pr\'ec\'ed\'e le carct\`ere B, et le caract\'ere B doit pr\'ec\'ed\'e 
le caract\`ere C, etc.\\

Plusieurs codifications des carat\`eres ont \'et\'e propos\'ees :
\begin{itemize}
\item[$\bullet$] 
BCD [Binary Coded Decimal], 
un caract\`ere est cod\'e sur 6 bits~;
\item[$\bullet$]
EBCDIC [Extended Binary Coded Decimal Internal Code] 
(8 bits)~;
\item[$\bullet$]
ASCII [American Standard Code for Information Interchange]
(7 bits)~;
%employ\'e par les ordinateurs IBM ;
\item[$\bullet$]
ISO [International Standard Organisation] (8 bits), qui est un ASCII \'etendu~;
%utilis\'e dans les logiciels d'Internet~; 
\item[$\bullet$] 
UNICODE (16 bits), qui contient actuellement 38887 caract\`eres \`a travers le monde~;
\item[$\bullet$] 
ISO/IEC 10646 (32 bits), une extension de UNICODE.
\end{itemize}

Les deux derniers codes sont plus r\'ecents (d\'ebut des ann\'ees 90). 
En effet, $2^{7}=128$ ou $2^{8}=256$ valeurs ne suffisent pas pour repr\'esenter 
l'ensemble de tous les caract\`eres de toutes les langues de la plan\`ete. 
Ainsi, le code UNICODE permet de coder $2^{16}=65536$ caract\`eres diff\'erents.\\

Cependant, c'est le code ASCII qui est adopt\'e de fa\c{c}on 
quasi universelle (pour l'instant !). 
Ses principales caract\'eristiques sont :
\begin{itemize}
\item[$\bullet$] 
c'est un code sur $7$ bits permettant de coder $128$ $(=2^{7})$ symboles diff\'erents~;
\item[$\bullet$] 
les $32$ premiers~; entre $0$ et $31$ (en hexad\'ecimal entre $00$ et $1F$)~; 
repr\'esentent les caract\`eres de contrôle (ne sont pas affichables), (par exemple~:
\'emettre un bip sonore, passer \`a la ligne, ...)~;
\item[$\bullet$] 
Les lettre se suivent dans l'ordre alphab\'etiques 
(codes $65$ \`a $90$ pour les majuscules, $97$ \`a $122$ pour les minuscules) 
ce qui simplifie les comparaisons par exemple pour faire un tri par ordre 
alphab\'etique (on passe donc des majuscules aux minuscules en ajoutant $32$ 
au code ASCII d\'ecimal)~; 
\item[$\bullet$] 
les caract\`eres num\'eriques (chiffres) sont rang\'es dans l'ordre croissant 
(codes $48$ \`a $57$).
\end{itemize}

\begin{table}
{\footnotesize
\begin{tabular}{rrrc|rrrc}
D\'ecimal	& Hexa	& Binaire	& Caract\`ere	& D\'ecimal	& Hexa	& Binaire	& Caract\`ere	\\ \hline 
0 	& 0 	& 0		& NUL		& 64		& 40	& 1000000	& @		\\
1 	& 1	& 1		& SOH 		& 65		& 41	& 1000001	& A		\\
2	& 2 	& 10		& STX 		& 66		& 42	& 1000010	& B		\\
3	& 3	& 11		& ETX 		& 67		& 43	& 1000011	& C		\\ 
4	& 4	& 100		& EOT 		& 68		& 44	& 1000100	& D 		\\
5	& 5	& 101		& ENQ 		& 69		& 45	& 1000101	& E 		\\
6	& 6	& 110		& ACK 		& 70		& 46	& 1000110	& F 		\\
7	& 7	& 111		& BEL		& 71		& 47	& 1000111	& G 		\\
8	& 8	& 1000		& BS		& 72		& 48	& 1001000	& H 		\\
9	& 9	& 1001		& HT		& 73		& 49 	& 1001001	& I		\\
10	& A	& 1010		& NL		& 74		& 4A 	& 1001010	& J		\\
11	& B	& 1011		& VT		& 75		& 4B 	& 1001011	& K		\\
12	& C	& 1100		& NP		& 76		& 4C	& 1001100	& L 		\\
13	& D	& 1101		& CR 		& 77		& 4D 	& 1001101	& M 		\\
14	& E	& 1110		& SO 		& 78		& 4E 	& 1001110	& N		\\
15	& F	& 1111		& SI 		& 79		& 4F 	& 1001111	& O		\\
16	& 10 	& 10000		& DLE 		& 80		& 50	& 1010000	& P 		\\
17	& 11	& 10001		& DC1 		& 81		& 51 	& 1010001	& Q 		\\
18	& 12	& 10010		& DC2 		& 82		& 52	& 1010010	& R 		\\
19	& 13	& 10011		& DC3 		& 83		& 53 	& 1010011	& S 		\\
20	& 14 	& 10100		& DC4 		& 84		& 54	& 1010100	& T 		\\
21	& 15	& 10101		& NAK 		& 85		& 55	& 1010101	& U 		\\
22	& 16 	& 10110		& SYN 		& 86		& 56	& 1010110	& V 		\\
23	& 17	& 10111		& ETB		& 87		& 57	& 1010111	& W 		\\
24	& 18 	& 11000		& CAN 		& 88		& 58	& 1011000	& X 		\\
25	& 19	& 11001		& EM 		& 89		& 59	& 1011001	& Y		\\
26	& 1A	& 11010		& SUB 		& 90		& 5A	& 1011010	& Z 		\\
27	& 1B	& 11011		& ESC 		& 91		& 5B	& 1011011	& [ 		\\
28	& 1C 	& 11100		& FS 		& 92		& 5C	& 1011100	& $\backslash$	\\
29	& 1D	& 11101		& GS 		& 93		& 5D	& 1011101	& ] 		\\
30	& 1E	& 11110		& RS 		& 94		& 5E	& 1011110	& $_{\widehat{}}$		\\
31	& 1F	& 11111		& US 		& 95		& 5F 	& 1011111	& \_		\\
32	& 20	& 100000	& SP 		& 96		& 60	& 1100000	& ` 		\\
33	& 21	& 100001	& ! 		& 97		& 61 	& 1100001	& a 		\\
34	& 22 	& 100010	& " 		& 98		& 62 	& 1100010	& b 		\\
35	& 23 	& 100011	& \# 		& 99		& 63 	& 1100011	& c 		\\
36	& 24 	& 100100	& \$ 		& 100		& 64	& 1100100	& d 		\\
37	& 25 	& 100101	& \% 		& 101		& 65 	& 1100101	& e 		\\
38	& 26 	& 100110	& \& 		& 102		& 66 	& 1100110	& f 		\\
39	& 27 	& 100111	& ' 		& 103		& 67	& 1100111	& g 		\\
40	& 28	& 101000	& ( 		& 104		& 68	& 1101000	& h 		\\
41	& 29 	& 101001	& ) 		& 105		& 69 	& 1101001	& i 		\\
42	& 2A 	& 101010	& * 		& 106		& 6A 	& 1101010	& j 		\\
43	& 2B 	& 101011	& + 		& 107		& 6B	& 1101011	& k 		\\
44	& 2C	& 101100	& ,		& 108		& 6C	& 1101100	& l 		\\
45	& 2D 	& 101101	& -		& 109		& 6D 	& 1101101	& m 		\\
46	& 2E 	& 101110	& . 		& 110		& 6E 	& 1101110	& n 		\\
47	& 2F 	& 101111	& / 		& 111		& 6F 	& 1101111	& o 		\\
48	& 30	& 110000	& 0		& 112		& 70	& 1110000	& p 		\\
49	& 31 	& 110001	& 1		& 113		& 71 	& 1110001	& q 		\\
50	& 32	& 110010	& 2		& 114		& 72 	& 1110010	& r		\\
51	& 33	& 110011	& 3 		& 115		& 73 	& 1110011	& s		\\
52	& 34	& 110100	& 4		& 116		& 74	& 1110100	& t		\\
53	& 35 	& 110101	& 5		& 117		& 75 	& 1110101	& u		\\
54	& 36 	& 110110	& 6		& 118		& 76 	& 1110110	& v		\\
55	& 37 	& 110111	& 7		& 119		& 77 	& 1110111	& w		\\
56	& 38	& 111000	& 8 		& 120		& 78	& 1111000	& x 		\\
57	& 39 	& 111001	& 9		& 121		& 79 	& 1111001	& y 		\\
58	& 3A 	& 111010	& :		& 122		& 7A 	& 1111010	& z 		\\
59	& 3B 	& 111011	& ;		& 123		& 7B 	& 1111011	& \{ 		\\
60	& 3C	& 111100	& <		& 124		& 7C	& 1111100	& $|$ 		\\
61	& 3D 	& 111101	& =		& 125		& 7D	& 1111101	& \}		\\
62	& 3E 	& 111110	& > 		& 126		& 7E 	& 1111110	& $_{\widetilde{}}$ \\
63	& 3F	& 111111	& ?		& 127		& 7F	& 1111111	& DEL 		\\ \hline 
\end{tabular}
}
\caption{Code ASCII (d\'ecimal - Hexad\'ecimal - Binaire - Caract\`ere)}
\end{table}

\begin{remarque}
Ce code \'etant \`a l'origine fait pour les besoins de l'informatique 
en langue anglaise ne permet pas de coder les caract\`eres accentu\'es du fran\c{c}ais, 
de m\^eme que les caract\`eres sp\'eciaux d'autres langues (arabe, chinoix, ...).
\end{remarque}

La longueur standard minimale des mots trait\'es par les machines actuelles \'etant 
de $8$ bits, des extensions du code ASCII, utilisant le $8^{eme}$ bit,  
ont \'et\'e propos\'ees afin de pouvoir coder des caract\`eres sp\'ecifiques 
d'autres langues, mais ne sont pas universellement reconnues.


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