Fonctionnement de Fonctionnement de l’ordinateurl’ordinateur

Chapitre 2: Codage d’informations et algèbre de Boole

Hassen JEDIDI

PlanPlan

Objectifs:

Connaitre le système binaire: le bit et l’octet. Comprendre le codage des informations en

informatique. Etre capable de convertir des nombres entre les

différentes bases. Savoir effectuer des opération (addition,

multiplication,…) sur les nombres binaires.

Hassen JEDIDI

IntroductionIntroduction

Les grandeurs physiques que l’on mesure, ou que l’on désire modifier, sont des variables analogiques.

Elles prennent des nombreuses valeurs, en passant en général de l’une à l’autre de manière continue.

Exemple: signal sinusoïdal

Hassen JEDIDI

Système binaireSystème binaire

L’informatique utilise des courants électriques, des aimantations, des rayons de lumière ...

Chacun de ces phénomènes met en jeu deux états possibles:

◦tension nulle ou tension non nulle (5V par ex),◦aimantation dans un sens ou dans l’autre sens,◦lumière ou pas de lumière.

Hassen JEDIDI

Système binaire (2)Système binaire (2)

Il suffit donc de deux chiffres pour traduire ces deux états: c’est la numération binaire qui utilise les chiffres 0 et 1.

Un rayon de lumière peut parfaitement traduire ces deux valeurs:

0 = pas de lumière, 1 = lumière.

Hassen JEDIDI

Système binaire (3)Système binaire (3)

Le système binaire est un système de numération de position de base deux: les deux seuls chiffres qui le composent sont le 0 et le 1.

Le système binaire est le langage des ordinateurs. Toutes les machines numériques utilisent le système binaire pour coder des informations (textes, sons, images, vidéos ....).

Hassen JEDIDI

Notation positionnelleNotation positionnelle

La représentation d’un nombre est un codage

ne pas confondre un nombre avec sa représentation !

la quantité dix peut être représentée par:◦ dix, 10, **********, 1010, A, X, etc...

Hassen JEDIDI

Représentation d’un nombre dans Représentation d’un nombre dans la base 10la base 10

Les nombres décimaux sont représentés comme des sommes de multiples de chaque puissance de 10.

Exemple 1543(10)= (1* 103) + (5* 102) + (4* 101) + (3* 100).

Hassen JEDIDI

Représentation d’un nombre dans Représentation d’un nombre dans la base binaire la base binaire

alphabet de 2 caractères binaires (appelés bit) {0,1}

Exemple: 01101(2) = (0×24) + (1×23)

+ (1×22) + (0×21)+ (1×20) =8(10)+ 4(10)+ 1(10)

=13(10)

Hassen JEDIDI

Représentation d’un nombre dans Représentation d’un nombre dans la base 16 (hexadécimal)la base 16 (hexadécimal)alphabet de 16 caractères

hexadécimaux {0, . . . ,9,A,B,C,D,E,F }

01B16 = 0 × 162 + 1 × 161 + B × 160

= 16(10) + 11(10)

= 27 (10)

Hassen JEDIDI

Code binaire naturel /pureCode binaire naturel /pure

Basé sur la représentation des nombres en base 2 :

0: 000. 1: 001. 2: 010. 3: 011. 4: 100. 5: 101. 6: 110. 7: 111

Hassen JEDIDI

Code Décimal Codé Binaire Code Décimal Codé Binaire ( BCD/DCB)( BCD/DCB)chaque chiffre est codé sur 4 bits :

0: 0000. 1: 0001. 2: 0010. 3: 0011. … …10: 0001 0000.11: 0001 0001.

Hassen JEDIDI

Code De GrayCode De GrayDistance de 1 entre deux mots de code

consécutif.

0: 000. 1: 001. 2: 011. 3: 010. 4: 110. 5: 111. 6: 101. 7: 100

Hassen JEDIDI

Détection d’erreurDétection d’erreur

Un code peut être utiliser pour détecter une erreur.

Exemple: Ajout d’un bit pour maintenir la parité.

◦ 0110 devient 01100.◦ 1011 devient 10111

Hassen JEDIDI

Bit de paritéBit de parité

0110 à transmettrecalcul du bit de parité : 001100 transmiserreur de transmission01110 arrivérecalcule du bit de parité : 1comparaison avec le bit de parité

arrivé : erreur détectée

Hassen JEDIDI

Représentation des réels Représentation des réels ( virgule fixe)( virgule fixe)Même méthode pour la partie entière.On garde la virgule. La partie décimale se décompose en

puissance négatives de 2. Exemple: 0,75(10) = ? (2)

0.75 * 2 = 1,5 (on garde 1, reste 0,5) 0,5 * 2 = 1,0 (on garde 1, reste 0: terminé) 0,75(10) = 0,11(2) = 1*2-1 + 1* 2-2 = 0,25 + 0,5 = 0,75

Hassen JEDIDI

Codage des entiers relatifsCodage des entiers relatifs Problème = représenter le signe Première méthode: signe ( « + » = 0, « - » = 1) + valeur absolue Exemple: codage de -22(10) sur 8 bits (1 bit de signe

+ 7 bits) 22 = 10010110 signeAvantage: facile à lire pour l’utilisateur.Problèmes:

2 représentations possible pour 0 (+ 0 et -0) Comment additionner 2 nombres de signe différent?

Hassen JEDIDI

Codage des entiers relatifs (2)Codage des entiers relatifs (2) Seconde méthode: Complément à 2 Principe: Soit a représenter un nombre positif

1. On prend son opposé.2. On le représente en base 2.3. On complémente chaque bit.4. On ajoute 1.

Remarque: Si on ajoutant le nombre et son complément à deux on obtient 0.

Hassen JEDIDI

Codage des entiers relatifs (3)Codage des entiers relatifs (3) 1 + (-1) = ??

◦ « signe + valeur absolue » 00000001 + 10000001 = 10000010 ◦ « Complément à 2 » 00000001 + 11111111 = 00000000

Hassen JEDIDI

Codage des données alphanumériques Codage des données alphanumériques

Idée = associer un nombre à un caractère.

Code ASCII ( American Standard Code for Information Interchange)=

7 bits (127 possibilité), les caractères 0 (00) à 31 (1F) sont des caractères spéciaux.

les caractères 32 (20) à 127 (7F) représentent: les minuscules, Les majuscules, Les signes de ponctuation.

Hassen JEDIDI

Codage des données alphanumériques Codage des données alphanumériques

Hassen JEDIDI

Conversion décimal-BinaireConversion décimal-Binaire

Pour communiquer avec un ordinateur, il est donc nécessaire de savoir convertir des nombres décimaux en nombres binaires.

Pour obtenir l'expression binaire d'un nombre exprimé en décimal, il suffit de diviser successivement ce nombre par 2 jusqu'à ce que le quotient obtenu soit égal à 0.

Hassen JEDIDI

Conversion décimal-Binaire (2)Conversion décimal-Binaire (2)

Une méthode de conversion consiste à décomposer le nombre décimal en une somme de puissances de deux:

Exemple: 44(10) = 101100 (2)

Hassen JEDIDI

Conversion Binaire-DécimalConversion Binaire-Décimal

soit d un nombre décimal, alors on pourra écrire :

d= a0*20 + a1*21 + a2*22 + ...+ an*2n

Exemple : 1101=?

1.20+0.21+1.22+1.23 =1+4+8=13

Hassen JEDIDI

0000 0101 + 0000 0110 = ? 1

0000 0101 +

0000 0110 0000 1011 = 11(10)

Hassen JEDIDI

Addition de 2 nombres positifsAddition de 2 nombres positifs

Première solution

Dans la soustraction binaire, on procède comme en décimal. Quand la quantité à soustraire est supérieure à la quantité dont on soustrait, on emprunte 1 au voisin de gauche.

En binaire, ce 1 ajoute 2 à la quantité dont on soustrait.

Exemple: 1

10 - 101

01

Hassen JEDIDI

Soustraction de 2 nombres positifsSoustraction de 2 nombres positifs

Deuxième solution (complément à 2)

Le complément binaire: Changer les « 1 » par des «0 » et les « 0 » par des « 1 »

Exemple: le complément de 01101 est 10010

Principe :

Pour effectuer une soustraction binaire, il suffit de faire une addition avec le complément du nombre à soustraire auquel on a ajouté 1 et de ne pas tenir compte de la dernière retenue la plus à gauche.

Hassen JEDIDI

Soustraction de 2 nombres positifs(2)Soustraction de 2 nombres positifs(2)

Exemple: 28 – 22 = ?◦ 22 = 000 10110.◦ Complément de 22 = 00001001◦ On ajoute 1 au complément 00001001 + 1 = 00001010◦ La soustraction du nombre binaire suivant  00011100 (28)

-  00010110 (22) revient à faire de l'addition de 00011100 + 00001010 = 00100110

◦ On enlève la retenue et on aura 110 = 6.

28 – 22 = 6

Hassen JEDIDI

Soustraction de 2 nombres positifs (3)Soustraction de 2 nombres positifs (3)

le résultat de l’opération n’est pas représentable dans le système utilisé.

Exemple: Nombres codés sur 4 bits 1101 + 0011 10000 le débordement correspond à une retenue

sortante à 1.

Hassen JEDIDI

Débordement (overflow)Débordement (overflow)

Comme en décimal. N'utilise que du décalage de bits et additions. Exemple : 101 x 110 :

101 * 110 000 +

1010 + 10100 11110

Hassen JEDIDI

Multiplication binaireMultiplication binaire

Les opérations Les opérations logiques de baseslogiques de bases

Hassen JEDIDI

« ou » logique (OR)« ou » logique (OR)

L’opération est représentée par +.

X= A+B. Table de vérité:

Hassen JEDIDI

A B X = A+B

0 0 0

0 1 1

1 0 1

1 1 1

« ET » logique (AND)« ET » logique (AND)

L’opération est représentée par * ou .

X= A.B. Table de vérité:

Hassen JEDIDI

A B X = A+B

0 0 0

0 1 0

1 0 0

1 1 1

Inverseur logique (NOT)Inverseur logique (NOT)

L’opération est notée comme x = A

Table de vérité:

Hassen JEDIDI

A X

0 1

1 0

«NON ET » logique (NAND)«NON ET » logique (NAND)

Il s'agit d'un ET complémenté (inversé) X= A.B . Table de vérité:

Hassen JEDIDI

A B X

0 0 1

0 1 1

1 0 1

1 1 0

«NI » ou « NON OU » ou « NOR »«NI » ou « NON OU » ou « NOR » Il s'agit d'un ET complémenté (inversé) X= A+B . Table de vérité:

Hassen JEDIDI

A B X

0 0 1

0 1 0

1 0 0

1 1 0

«OU exclusif »«OU exclusif » a + b = 1 quand a=0 et b=1 ou a= 1 et b =0a + b = ab + ab

Hassen JEDIDI

A B X

0 0 0

0 1 1

1 0 1

1 1 0

Portes logiquesPortes logiques

Hassen JEDIDI

Algèbre de BooleAlgèbre de Boole

L’ algèbre de Boole est la donnée de:

Un ensemble E, Deux éléments particuliers de E : « 0 » et « 1 »,

Deux opérations binaires sur E :  « + » et  « . » ,

une opération unaire sur E : « - » .

Hassen JEDIDI

Axiome de l’ algèbre de BooleAxiome de l’ algèbre de Boole

Hassen JEDIDI

ThéorèmesThéorèmes• Idempotence

• a+a=a • aa=a

• Absorption • a+ab=a• a(a+b)=a

• De Morgan (dualité)• a + b=a.b • ab=a+b

éléments absorbants a+1=1 a0=0

Hassen JEDIDI

Circuits logiques combinatoiresCircuits logiques combinatoires

Circuits dont la fonction de sortie s’exprime par une expression logique des variables d’entrées.

Quelques circuits combinatoires intervenant dans la réalisation des composants d’un ordinateur

Décodeur,Multiplexeur.

Hassen JEDIDI

DécodeurDécodeur

Permet d’envoyer un signal à une sortie choisie.

n lignes d’entrées2n lignes de sortie

Hassen JEDIDI

Table de véritéTable de vérité

Décodeur 2 vers 4 (n = 2)

Hassen JEDIDI

e1 e0 S0 S1 S2 S3

0 0 1 0 0 0

0 1 0 1 0 0

1 0 0 0 1 0

1 1 0 0 0 1

Réalisation d’un décodeur 2 vers 1Réalisation d’un décodeur 2 vers 1

Hassen JEDIDI

Multiplexeur Multiplexeur

permet de sélectionner une entrée parmi plusieurs

2n entrées1 sortien lignes de sélection

Hassen JEDIDI

Table de véritéTable de vérité

multiplexeur 4 voies

Hassen JEDIDI

e3 e2 e1 e0 C1 C0 S

- - - X 0 0 X

- - X - 0 1 X

- X - - 1 0 X

x - - 1 1 x

multiplexeur “4 voies” (n = 2)multiplexeur “4 voies” (n = 2)

Hassen JEDIDI

Circuits arithmétiques Circuits arithmétiques

Quelques circuits typiques de mise en

œuvre de opérations arithmétiques

Hassen JEDIDI

Addition Addition

Demi additionneur◦ Somme de 2 bits◦Table de vérité

◦Sortie s= a + b◦Retenue R= ab

Hassen JEDIDI

a b S R

0 0 0

0 1 1

1 0 1

1 1 0 1

Addition (2) Addition (2)

Additionneur complet (full adder)

◦ Somme de 3 bits : A, B, Rin◦ Somme : S = A + B + Rin

◦Retenue : vient de l’une des deux sommes

Hassen JEDIDI

Addition (3) Addition (3)

Hassen JEDIDI

Additionneur à propagation Additionneur à propagation simple de retenuesimple de retenue

Hassen JEDIDI

ComparateurComparateur

Comparateur 1 bit a b

p e g

p: si a <b abe: si a =b ab + abg :si a>b ab

Hassen JEDIDI

Comparateur 1 bit

Comparateur 1 bit

a b p e g

0 0 0 1 0

0 1 1 0 0

1 0 0 0 1

1 1 0 1 0

Résumé des circuits Résumé des circuits combinatoirescombinatoires

Circuit combinatoire◦ Construit avec des portes logiques.◦ Définit par une des portes logiques.◦ Définit par une table de vérité.

Circuit « idéal » pas de temps de propagation dans le circuit, La sortie « existe dès que les entrées sont

présentées. Circuit « réel »: le passage de 0 à 1 n’est pas

immédiat.

Hassen JEDIDI

Circuits séquentielsCircuits séquentiels

Circuit séquentiel:

◦ prise en compte du temps.

◦ La sortie du circuit dépend: des valeurs d’entrée, des sorties précédentes.

◦ Utilisation de l’horloge, mémoire,… .

Hassen JEDIDI

Bascule D (bistable, flip-flop)Bascule D (bistable, flip-flop)

Q-: valeur précédente de la bascule. Q+: nouvelle valeur

◦ Si CK = 1; Q+ = Q- ;◦ Si CK = 0; Q+ = D

l’entrée D est validée par l’horloge.

Hassen JEDIDI

D

CK

Q

Q

CK D Q+

1 X Q-

0 0 0

0 1 1

Utilisation des basculesUtilisation des bascules

Mémorisation:◦ Si CK = 1, le registre continue de mémoriser Q7 …..Q0

◦ Si CK =0, mémorisation de la nouvelle valeur donnée par D7 …..D0

Hassen JEDIDI

D

CK

Q

Q

D

CK

Q

Q

D

CK

Q

Q

D7D6 D0

Q7 Q6Q0

CK

Unité Arithmétique et Logique (UAL)Unité Arithmétique et Logique (UAL)

Unité chargée:◦ des opérations arithmétiques:

ADD (+), SUB(-), MUL (*), DIV (/), INC (+1), DEC (-1).

◦ des opérations logiques: AND, OR, XOR, NOT, CMP LSL, LSR, ASR (décalage)

Hassen JEDIDI

C0C1

C2

C3UAL

OF: Overflow Flag

CF: Carry Flag

ZF: Zero Flag

SF: Sign Flag

R

A B

Flag = drapeauFlag = drapeau

Sélection de

l’opération

Sélection de

l’opération

Chemin de donnéesChemin de données

Rappel de l’architecture de Von Neumann

BA : Bus d’adresseBD: Bus de donnéesBC: Bus de commande

Hassen JEDIDI

Unité de commandeUnité de commande

MémoireMémoire

Unité de traitementBA

BD

BC EntréesEntrées

SortiesSorties

Bus internes

Bus internes

61

Chapitre prochain

Machine de Von Neumann