Tdm cours: septembre 2011

Représentation à "virgule fixe"

A l'instar de la définition des nombres binaires naturels,
nous pourrions définir un réel positif par une convention du même type :

Exemple : le nombre 1010,101 peut représenter la somme suivante :

Soit, en écriture décimale : 8 + 2+ 0,5 + 0,125 = 10,625
Sous une autre forme :

On peut rigoureusement démonter que tout nombre réel positif pourrait ainsi écrit de cette manière.
Resterait à décrire le signe, ce qui peut être fait par un bit particulier (bit de signe)
ou par une convention de type complément à deux.
Beaucoup de ces variantes ont été utilisées dans les calculateurs.

1010 est la partie entière du nombre,
101 sa partie fractionnaire.

Exemple du calcul inverse : traduire en binaire le nombre 78,347

Partie entière : 78

Nous opérons une suite de divisions par 2 et retenons les divers restes.
Ces restes sont repris à l'envers

Partie fractionnaire : 0,347

En réalité, 2^-10 = 0,0009765625 est la valeur de 0,000 000 000 1, le dernier chiffre binaire à droite du nombre ci-dessus.
L'erreur dûe au fait de négliger les résultats à droite de ce chiffre est inférieure à 2

10^-11 = 0,00048828125.

Résultat final :
78,347 écrit en décimal
représente 1001110,0101100011 écrit en binaire à moins de 2 ^-11 près

Reste cependant que cette représentation à virgule fixe est souvent dispendieuse en nombre de bits !

Imaginons que l'on veuille écrire tous les réels de 0 à 65 635.
Le sous-ensemble d'entiers de cet intervale s'écrit sous 16 bits : 2¹⁶ = 65 536.
Si la précision maximale que nous voulons atteindre est seulement de 1/2¹⁶-1 = 1/65 535
Nous devrons écrire seize chiffres après la virgule ;exemple 1010 0101 1100 1111,0110 1110 1101 0111

Pour de petits nombres, il y gaspillage de bits à gauche de la virgule : 101,001001100
Pour des nombres à peu de décimales, il y aura gaspillage de bits après la virgule : 1100 1111,01

Néanmoins ce système a été réellement employé dans certains types de calculateurs.

Représentation "à virgule flottante"

Rappelons ce qu'est la notation scientifique des nombres réels :

En "notation scientifique" dite "à virgule flottante"
- 0,006234 s'écrit - 6.234 e- 3 ou - 6.234 E- 3
Cette notation est l'équivalent de :
- 6,234 . 10^{- 3}

Observons bien la manière dont on construit ce format à partir d'une expression quelconque d'un nombre.
Prenons deux exemples de nombres écrits en base décimale :
- 0,007123456789 et +54321,123456

On retient le signe du nombre.
Et on ne s'interesse d'abord qu'à la valeur absolue.
On met le nombre sous forme de deux facteurs.
1. Un nombre de l'intervalle [1,9]
  7,123456789 pour le premier
  5,4321123456 pour le second
2. Une puissance de 10 ramenant le produit à sa valeur initiale.
  7,123456789 ×10^-3 pour le premier.
  5,4321123456 ×10⁺⁴ pour le second.
On rétablit le signe.
-7,123456789 ×10^-3 pour le premier
+5,4321123456 ×10⁺⁴ pour le second.
On remplace, 10 par E (ou e) suivis de la caractéristique.
-7,123456789 E-3 pour le premier
+5,4321123456 E+4 pour le second.

Le nombre intermédiaire de l'intervalle [1,9]s'appelle la mantisse

.L'exposant de la puissance de 10 est appelé la caractéristique.
Ce dernier mot tombe actuellement en déssuétude.

Exemple en binaire.

Nb = -1010 1101,1011 0110
Mantisse de |Nb| = 1,010 1101 1011 0110
Caractéristique : + 7
Nb = - 1,010 1101 1011 0110 × 2⁺⁷

Notons que la mantisse comporte une partie entière et une partie fractionnaire.

Exemple : -7,123456789 E-3
7 est la partie entière de la mantisse,
123456789 est sa partie fractionnaire.

Nombre zéro en virgule flottante.

Rien n'interdit de représenter le nombre zéro
par un flottant dont la parties entière et fractionnaire sont nulles
ainsi que la caractéristique.
n = 0 x 10⁰ = 0 x 1 = 0Mais cette forme du zéro pose des problèmes dans les standards de représentation binaire
des nombres dans les mémoires des machines informatiques.
Notamment dans les formats 32 et 64 bits du standard IEEE.

Nous allons maintenant voir comment on implémente ce format
de notation dans un ordinateur.

Quelques exemples de formats binaires à virgule flottante
à 32, 64 et 80 bits
Respectivement 4, 8 et 10 octets

Utilisé pour le type "float" (simple précision)

Utilisé pour le type "double" (double précision)

Les formats à 32 et 64 bits ignorent la partie entière de la mantisse.
Le format à 80 bits mémorise la mantisse avec sa partie entière

Schéma de représentation des nombres en virgule flottante et en représentation binaire

Détails d'implémentation des nombres en virgule flottante
au niveau de leur représentation binaire.Normes IEEE

Partie fractionnaire

La partie fractionnaire
du nombre obtenu après avoir déplacé la virgule du nombre initial,
de manière à ne laisser subsister qu'un seul chiffre à gauche, différent de zéro.
Pour un nombre écrit en binaire, ce chiffre est invariablement "1"
Exemple :
Si le nombre écrit en binaire est : 0000 1010,0110
Après déplacement de la virgule de 3 rangs à gauche : 1,0100110
La partie fractionnaire est : 0100110
Le "1" à gauche du zéro est omis de la représentation IEEE.
Il est "implicite" car en binaire ce chiffre est toujours le même : "1" pour tous les nombres.
Sauf, me direz-vous le zéro, cas particulier sur lequel nous reviendrons plus loin.

Exposant
Attention ! la valeur de l'exposant dans l'écriture du nombre en virgule flottante
et celle de l'exposant dans le format IEEE,
ne sont pas les mêmes !
L'exposant permet de déterminer de combien de rangs
il faut déplacer la virgule se trouvant à gauche de la partie fractionnaire
et dans quel sens (droite ou gauche) après rétablissement du "1" implicite,
pour obtenir le nombre à représenter.

Pour mesurer ce déplacement, tantôt positif tantôt négatif, on aurait pu penser à écrire l'exposant
dans la "convention du complément à 2"

Ce n'est pas le cas. Les structures internes des machines numériques
s'accomodent mieux de la convention suivante.

Soit D le nombre entier algébrique mesurant le déplacement de la virgule
Soite E la valeur de l'exposant, par définition on pose :

E = D + B

E = valeur de l'exposant considéré comme entier positif
D = déplacement algébrique de la virgule B = une constante appelée décalage (Bias en anglais)

D = E - B

B (le décalage ou bias) est une constante de valeur :

Décalage (ou Bias)
B = 2^n-1 - 1

Calcul de B

Pour éclairer cette définition.
nous vous proposons deux exemples.

Traduisons en binaire format flottant simple précision 32 bits ( float )le nombre : - 1039,0 (écrit ici en décimal)

Occupons-nous d''abord de sa valeur absolue 1039,0.
Pour traduire ce nombre (il est entier dans ce premier exemple) en binaire
nous passons par son écriture hexadécimale :

1039 _décimal = 40F _{héxadécimal} = 0000 0100 0000 1111_binaire

Nous constituons la partie fractionnaire : 1, partie fractionnaire

0000 0100 0000 1111 = 1,00 0000 1111 . 2¹⁰
( 2¹⁰ décale la virgule de dix chiffres vers la droite )

Nous étendons la partie fractionnaire à 23 bits

1,00 0000 1111 =1,00 0000 1111 0000 0000 0000 0
Rangé autrement :1,000 0001 1110 0000 0000 0000
Partie fractionnaire sur 23 bits = 000 0001 1110 0000 0000 0000(on ne mémorise pas le 1 implicite d'avant la virgule)

Nous constituons le décalage IEEE en simple précision 8 bits : 2^{8 - 1} - 1 = 127

Nous constituons l'exposant : exposant = 10 + décalage = 137

137 _décimal = 1000 1001 _binaire

Voici le résultat : bit de signe - exposant - partie fractionnaire

Bits	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	1	1	0	0	0	1	0	0	1	0	0	0	0	0	0	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0

En héxadécimal C4 81 E0 00

Le bit de signe (bit b31) positionné à 1 indique un nombre réel négatif !

L'opposé de -1039,0, soit 1039,0, s'obtient en mettant le bit de signe b31 à 0

+ 1039,0 se code 44 81 E0 00 en héxadécimal

Second exemple

Traduisons en binaire format flottant simple précision 32 bits ( float )le nombre : x = - 6,625 (écrit ici en décimal)

Occupons-nous d''abord de sa valeur absolue 6,625
Traduisons ce nombre en binaire :
6,625 _décimal = 110,1010 _{binaire

c.f. " Virgule fixe" :}

Nous mettons ce nombre sous la forme : 1, partie fractionnaire

110,1010 = 1,101010 . 2²
( 2² décale la virgule de 2 chiffres vers la droite)

Nous étendons la partie fractionnaire à 23 bits

1,101010 = 1,1010 1000 0000 0000 0000 000
partie fractionnaire sur 23 bits = 101 0100 0000 0000 0000 0000
(on ne mémorise pas le 1 implicite d'avant la virgule)

Nous rappelons le décalage IEEE en simple précision 8 bits : 2^{8 - 1} - 1 = 127

Nous constituons l'exposant : exposant = 2+ décalage = 129

129 _décimal = 1000 0001 _binaire

Voici le résultat : bit de signe - exposant - partie fractionnaire

Bits	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	1	1	0	0	0	0	0	0	1	1	0	1	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

En héxadécimal C0 D4 00 00

Le bit de signe (bit b31) positionné à 1 indique un nombre réel négatif !

L'opposé de - 6,625, soit + 6,625, s'obtient en mettant le bit de signe b31 à 0

+ 6,625 se code 40 D4 00 00 en héxadécimal

Correspondance Exposant - Décalage - Déplacement

E = valeur de l'exposant dans l'implémentation IEEE
D = déplacement de la virgule pour rétablir le nombre.
B = 2^n-1-1 = Décalage (bias)

En rouge les diverses valeurs numériques décimales pour n = 8 bits
valeur pour laquelle le décalage (bias) est B = 2^8-1-1=127 .
Seules quelques valeurs sont affichées.

E	0	1	...	B	B+1	...	2ⁿ-2	2ⁿ-1
E	0	1	...	127	128	...	254	255
D	- B	-B+1	...	0	1	...	2^n-1-1	2^n-1
D	-127	-126	...	0	1	...	127	128
2^D	2^-B	2^-(B-1)	...	0	2	...	2 ^ (2^n-1-1)	2 ^ (2^n-1)
	128 valeurs D <= 0				128 valeurs D > 0

Comme nous allons le voir, les colonnes extrêmes grisées de ce taleau
correspondent à des nombres d'exception.

Exceptions

Représentation du zéro.
La règle de formation de la partie fractionnaire dans le format IEEE
impose que l'on déplace la virgule à droite du bit à "1" le plus signifiant (de plus grand poids)
dans le nombre binaire initial.
Exemple : 0,001 0000 1110 sera transformé en:1, 0000 1110 x 2^-3

Cette méthode est inopérante pour un nombre nul.

C'est la raison pour laquelle on est convenu d'attribuer aux positions extrêmes du tableau précédent
des interprétations particulières.

Le zéro sera représenté
par un exposant E nul et une partie fractionnaire F nulle.
E = 0 ; F = 0

L'ennui est que si on en reste là, ces valeurs représentent déjà un autre nombre.
En effet, suivant notre règle de formation du format IEEE, on rétablit le "1" implicite
et le tableau précédent vous indique un déplacement de - B.
Ce n'est autre que : 1,000...x 2^-B

D'où la règle : ( F étant la partie fractionnaire)

E = 0
F = 0	représente les deux zéros ± 0 (n'oubliez pas le bit de signe)
F # 0	sont déclarés nombres hors norme, dénormalisés

C'est la raison pour laquelle nous avons grisé la colonne la plus à gauche du précédent tableau.

Autres réattributions

Il est indispensable que le format d'enregistrement d'un nombre
puisse mémoriser une impossibilité de calcul ou un résultat infini
survenus lors de son calcul..

On se sert pour cela des nombres correspondant à la colonne la plus à droite du tableau précédent.C'est-à-dire pour : E = 2ⁿ-1

E = 2ⁿ-1 (Max de E)
F = 0	Nombres infinis (±) Nommés INFINITY en informatique.
F # 0	Non-Nombres, notés NaN (Not a Number, voir ci-dessous)

Remarquez que les NaN et les INFINITY n'ont que des "1" dans leur exposant.

N'oublions pas que ces représentations binaires
sont directement traitées par des ordinateurs qui n'éprouvent aucune difficulté à déceler
et traiter ces exceptions.

Le format NaN est souvent utilsé pour les programmes
pour enregistrer une mauvaise saisie d'un nombre comme par exemple : 12,45U.
Le format INFINITY est souvent utilisé pour enregistrer le résultat d'une opération
telle qu'une division par zéro.

Les nombres ne faisant pas exception
(normalisés IEEE)

1 < E < 2ⁿ -2

Partie fractionnaire F quelconque.

Tableau des nombres normalisés IEEE
(le précédent sans les colonnes extrêmes)Seules quelques valeurs sont affichées.

E	1	2	...	B	B+1	...	2ⁿ-3	2ⁿ-2
E	1	2	...	127	128	...	253	254
D	-B+1	-B+2	...	0	1	...	2^n-1-2	2^n-1-1
D	-126	-125	...	0	1	...	+126	+127
2^D	2^-(B-1)	2^-(B-2)	...	0	2	...	2 ^(2^n-1-2)	2 ^(2^n-1-1)

Les nombres normalisés les plus proches de zéroEn valeur absolue :
Obtenus pour E = 1

D = 2 -2^n-1 et F = 0nombres = ± 1,0 x 2^D

Les nombres normalisés ayant la plus grande valeur absolueObtenus pour E = 254

D = 2^n-1-1 et F = 1111....1111nombres = ± 1,1111...1111 x 2^D

Les nombres dénormalisés
Comme lindique un tableau précédent, ils correspondent à

E = 0 et F # 0
On doit interpréter ces nombres comme ayant une partie entière égale à zéro
et une partie fractionnaire F non nulle.

Même le déplacement D est réattribué.
On ne prendra pas la valeur D = - B = - ( 2^n-1-1 )comme on aurait pu l'induire de l'observation du tableau,
mais la valeur D = -B+1 = -2^n-1 +2 par mesure de continuité avec les nombres normalisés.:

± 0,F × 2^-D

avec F#0 et D = -2^n-1+2 = 2-2^n-1

Exemple du format IEEE 32 bits
L'exposant a n = 8 bits, et D = -126
---
Valeur absolue maxima d'un nombre dénormalisé :
Val. abs. max. = 0,1× 2 ^-126 = 2 ^-127 =
5,8774717541114375398436826861112e-39
---
Valeur absolue minima d'un nombre dénormalisé :
Val. abs. min. = 0,000...001 × 2 ^-126
La partie fractionnaire ayant 23 bits dans ce format,
0,000...001 = 2 ^-23
Val. abs. min. = 2 ^-23 × 2 ^-126 = 2 ^-149 =
1,4012984643248170709237295832899e-45
J'arrête là pour aujourd'hui

1. Simplification algébrique

On considère qu'une équation booléenne est simplifiée si le nombre d'apparition des variables dans l'équation est le plus petit possible.

Q.1 En utilisant les propriétés et théorèmes de l'algèbre de Boole, simplifiez l'expression ci-dessous :

                                 _____ 
                 _   _           _      _
S = (a + b + c).(a + d.e + f) + (d + e).a.c + a.b

En développant l'équation en termes produits, nous obtenons :

_     _           _       _           _       _           _     _
S = a.a + a.d.e + a.f + a.b + b.d.e + b.f + a.c + c.d.e + c.f + a.c.d.e + a.b

en éliminant a.a (propiété de complémentarité) et comme a.b + a.b = b, il est possible d'éliminer les termes contenant la variable b (théorème d'absoption). Il en résulte :

_           _       _           _     _ 
S = b + a.d.e + a.f + a.c + c.d.e + c.f + a.c.d.e

De même le théorème d'absorption s'applique pour a.c + a.c.d.e , faisant disparaître le 2ème terme

_           _       _       
S = b + a.d.e + a.f + a.c + c.d.e + c.f

En mettant d.e et f en facteur, il résulte :

_                         _
S = b + d.e.(a + c) + f.(a + c) + a.c

Et finalement le terme (a + c) se met en facteur. Une des solutions mettant en oeuvre le moins de varaiables logiques est donc :

_         _
S = b + (a + c).(d.e +f) + a.c

2. Simplification par tableau de Karnaugh

La méthode de Karnaugh permet de simplifier les fonctions logiques ayant peu de variables, à partir de la table de vérité de la fonction.

Q.2 Simplifiez les 2 fonctions F et G suivantes après avoir transformé leur table de vérité (respectivement Table 2.1 et Table 2.2) en tableau de Karnaugh.

Table 2.1 : fonction F
e	d	c	b	a	F
0	X	X	X	X	0
1	0	0	X	X	0
1	0	1	0	X	1
1	0	1	1	X	0
1	1	0	0	0	0
1	1	0	0	1	1
1	1	0	1	X	1
1	1	1	0	0	1
1	1	1	0	1	0
1	1	1	1	X	0

Les entrées sont a b c d e
Une variable d'entrée à "X" indique qu'elle peut être à 0 ou 1.

En remarquant que la variable e sert à valider l'action des autres entrées, F s'exprime alors : F = e.f(a,b,c,d)
Il suffit dans ce cas de simplifier la fonction à 4 entrées f(a,b,c,d) et le report de la table de vérité nous donne la table de Karnaugh de la figure ci-dessous.

En effectuant par la suite la mise en facteur des termes d.c et c.b une expression simplifiée de F est donc :

_  _   _      _   
F = e. [c.b.(d + a) + d.c.(a + b)]

i	d	c	b	a	G
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	-
3	0	0	1	1	0
4	0	1	0	0	-
5	0	1	0	1	-
6	0	1	1	0	-
7	0	1	1	1	1
8	1	0	0	0	-
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

Les entrées sont a b c d
i indique la valeur de la combinaison (ou minterme) en décimal
Le "-" indique que G peut prendre indifféremment 0 ou 1

Le report de la table de vérité nous donne la table de Karnaugh de la figure ci-dessous :

Il serait possible d'effectuer une simplification supplémentaire si on dispose de la fonction OU exclusif et dans ce cas, G = c.b + (c ⊕ a)
En utilisant la fonction inverse, l'expression est un peu plus simple car il y a moins de combinaisons où la fonction G est fausse (Figure 2.3).

Figure 2.3

Pages

Tdm cours

Ads 468x60px

Popular Posts

Followers

vendredi 30 septembre 2011

Représentation binaire des Nombres Réels

Représentation "à virgule flottante"

Représentation à "virgule fixe"

Multiplication And Division of Octal Numbers Calculator

jeudi 29 septembre 2011

Simplification algébrique d'équations

1. Simplification algébrique

2. Simplification par tableau de Karnaugh

Share

Poser ta question!!

Blog Archive

Sample text

e	d	c	b	a	F
0	X	X	X	X	0
1	0	0	X	X	0
1	0	1	0	X	1
1	0	1	1	X	0
1	1	0	0	0	0
1	1	0	0	1	1
1	1	0	1	X	1
1	1	1	0	0	1
1	1	1	0	1	0
1	1	1	1	X	0

i	d	c	b	a	G
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	-
3	0	0	1	1	0
4	0	1	0	0	-
5	0	1	0	1	-
6	0	1	1	0	-
7	0	1	1	1	1
8	1	0	0	0	-
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

e	d	c	b	a	F
0	X	X	X	X	0
1	0	0	X	X	0
1	0	1	0	X	1
1	0	1	1	X	0
1	1	0	0	0	0
1	1	0	0	1	1
1	1	0	1	X	1
1	1	1	0	0	1
1	1	1	0	1	0
1	1	1	1	X	0

i	d	c	b	a	G
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	-
3	0	0	1	1	0
4	0	1	0	0	-
5	0	1	0	1	-
6	0	1	1	0	-
7	0	1	1	1	1
8	1	0	0	0	-
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

e	d	c	b	a	F
0	X	X	X	X	0
1	0	0	X	X	0
1	0	1	0	X	1
1	0	1	1	X	0
1	1	0	0	0	0
1	1	0	0	1	1
1	1	0	1	X	1
1	1	1	0	0	1
1	1	1	0	1	0
1	1	1	1	X	0

i	d	c	b	a	G
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	-
3	0	0	1	1	0
4	0	1	0	0	-
5	0	1	0	1	-
6	0	1	1	0	-
7	0	1	1	1	1
8	1	0	0	0	-
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1