Chapitre 2

Systèmes de nombres et codes

Ce chapitre présente la base des systèmes de notation utilisés dans les systèmes
numériques, tel que le codage binaire, ou hexadécimal. On y verra aussi différentes
méthodes pour coder les systèmes.

2.1 Système positionnel

Le système positionnel est le système de base utilisé pour coder des chiffres. Le système
le mieux connu est le système décimal. Dans ces systèmes, la position d’un chiffre est
associée à un poids (ou valeur) spécifique.

2.1.1 Système décimal

Le système décimal comporte dix symboles : 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9. Chaque position

d’un chiffre représente une puissance de 10. Ex :
• 1734 = 1 · 1000 + 7 · 100 + 3 · 10 + 4 · 1
• 51.68 = 5 · 10 + 1 · 1 + 6 · 0.1 + 8 · 0.01
Donc, sous le système décimal, un nombre D = d1 d0 .d−1 d−2 a la valeur

D = . . . d1 · 101 + d0 · 100 . + d−1 · 10−1 + d−2 10−2 + . . .

On appelle 10 la base ou la racine (en anglais radix).

1
 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

Pour tous les systèmes de nombre, la racine r ≥ 2 et le chiffre à la position i a un poids

ri. La forme générale est :
dp−1 dp−2 · · · d1 d0 . d−1 d−2 · · · d−n (2.1)
où on a p chiffres à gauche du point et n chiffres à droite. La valeur du nombre est :
p
X
D= di · r i (2.2)
i=−n

2.1.2 Système binaire

C’est le système le mieux connu après le système décimal. C’est aussi la base de tous les
systèmes numériques (ordinateurs, microcontrôleurs, etc). Dans ce système, à base 2, r = 2,
et les deux symboles sont 0 et 1.

Exemple 1

Quelle est la valeur décimale des chiffres binaires suivants : 100112 et 101.0012 ?

100112 = 1 · 24 + 0 · 23 + 0 · 22 + 1 · 21 + 1 · 20
= 1 · 16 + 0 · 8 + 0 · 4 + 1 · 2 + 1 · 1 = 1910

101.0012 = 1 · 4 + 0 · 2 + 1 · 1 + 0 · 0.5 + 0 · 0.25 + 0 · 0.125

= 5.12510

On utilise un indice pour indiquer la base avec laquelle le chiffre est écrit. Le chiffre le
plus à gauche est le chiffre le plus important : c’est lui qui a le plus de poids sur la valeur du
chiffre. Ce chiffre est nommé le bit le plus significatif (MSB : most significant bit). Le bit le
plus à droite est le chiffre le moins significatif, nommé le LSB. Par exemple, pour le chiffre
100112 , s’il y a erreur dans le MSB, la valeur du chiffre est 3 au lieu de 19. Par contre, s’il y
a erreur dans le LSB, le chiffre est 18 au lieu de 19 ; l’erreur est moins significative dans ce
cas.

2.1.3 Système octal

Dans ce système, la base est 8 : r = 8, avec huit symboles : 0, 1, 2, 3, 4, 5, 6 et 7. Un

exemple :
178 = 1 · 81 + 7 · 80 = 1510

Gabriel Cormier 2 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

2.1.4 Système hexadécimal

Ce système est souvent utilisé dans la programmation, pour raccourcir l’écriture de

chiffres binaires. La base est 16 : r = 16, avec seize symboles : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,
C, D, E et F. Exemple :
B65F16 = 11 · 163 + 6 · 162 + 5 · 161 + 15 · 160 = 4668710

2.2 Conversions de base

Il existe quelques méthodes pour convertir d’une base à une autre. Certaines conversions
sont plus faciles que d’autre, comme la conversion de binaire à hexadécimal.

2.2.1 Conversions binaire-octal-hexadécimal

La conversion de binaire à octal est assez simple, puisque dans la base octal, 8 = 23 . On
doit donc grouper les termes binaires en groupes de trois, puis convertir. Exemple :
1000110011102 = 100 011 001 110 = 43168
4 3 1 6
Le même principe peut être appliqué pour convertir de binaire à hexadécimal ; cette fois,
on fait des groupes de 4 (16 = 24 ).
1000110011102 = 1000 1100 1110 = 8CE16
8 C E

Pour convertir de octal (ou hexadécimal) à binaire, on fait le processus inverse. Pour
la conversion octal-binaire, chaque chiffre octal est écrit comme 3 bits binaires, et pour
la conversion hexadécimale, chaque chiffre hexadécimal est écrit comme 4 bits binaires.
Exemples :
13578 = 001 011 101 1112
9F.46C16 = 1001 1111. 0100 0110 11002

2.2.2 Conversion de décimal à une autre base

Pour convertir de décimal à une autre base, on fait la division par la base à laquelle on
veut convertir. On fait la division jusqu’à ce que le chiffre à diviser soit plus petit que la
base.

Gabriel Cormier 3 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

Exemple 2

Convertir 17910 en binaire.

179 ÷ 2 = 89 reste 1 (LSB)

89 ÷ 2 = 44 reste 1
44 ÷ 2 = 22 reste 0
22 ÷ 2 = 11 reste 0
11 ÷ 2 = 5 reste 1
5 ÷ 2 = 2 reste 1
2 ÷ 2 = 1 reste 0
1 ÷ 2 = 0 reste 1 (MSB)
17910 = 101100112

Exemple 3

Convertir 46710 en octal.

467 ÷ 8 = 58 reste 3 (LSB)

58 ÷ 8 = 7 reste 2
7 ÷ 8 = 0 reste 7 (MSB)
46710 = 7238

Pour convertir les fractions, on multiplie par la base au lieu de diviser.

Exemple 4

Convertir 0.687510 en binaire.

0.6875 × 2 = 1.3750 → d−1 = 1 (MSB)

0.3750 × 2 = 0.75 → d−2 = 0
0.75 × 2 = 1.5 → d−3 = 1
0.5 × 2 = 1 → d−4 = 1 (LSB)
0.687510 = 0.10112

Gabriel Cormier 4 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

Avec des fractions, il est possible d’avoir des erreurs de conversions. Il faut tronquer la
séquence selon le nombre de bits voulus.

Exemple 5

Convertir 0.310 en binaire.

0.3 × 2 = 0.6 → d−1 = 0 (MSB)

0.6 × 2 = 1.2 → d−2 = 1
0.2 × 2 = 0.4 → d−3 = 0
0.4 × 2 = 0.8 → d−4 = 0
0.6 × 2 = 1.6 → d−5 = 1
0.6 × 2 = 1.2 → d−6 = 1 (LSB)
0.310 = 0.0100112

Ici, la séquence se répète à partir de d−6 . Il faut donc décider du nombre de bits à utiliser
dans la conversion. Avec 3 bits, la réponse est 0102 , ce qui est 0.25 si on reconvertit en
décimal. On a donc une erreur de 0.05.

Précision Réponse Reconversion Erreur

4 bits 0.01002 0.25 0.05
5 bits 0.010012 0.28125 0.01875
6 bits 0.0100112 0.296875 0.003125

Avec plus de bits, l’erreur diminue.

2.3 Addition et soustraction binaire

L’addition et la soustraction binaires suivent les même règles que le décimal, sauf qu’il
n’y a que deux valeurs possibles.

2.3.1 Addition binaire

Le tableau 2.1 montre les combinaisons possibles d’entrées et leurs sorties correspon-
dantes pour l’addition binaire. Le Cin est le report d’entrée : c’est le surplus de l’addition à
la position précédente. Le Cout est le report de sortie : le surplus qui sera ajouté à l’addition
des bits de la position suivante.

Gabriel Cormier 5 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

Tableau 2.1 – Addition binaire

X Y Cin S Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Un exemple d’addition binaire est montré à la figure 2.1. Il y a débordement dans cet
exemple : le report de sortie est 1 à la fin de l’addition, mais il n’y a pas de bit de réservé
pour ce report. Dans l’exemple, on est dans un système à 8 bits : le report de sortie irait à
la place du 9e bit, mais cette position n’existe pas.

Débordement
1 1 1 1 1
X 1 0 1 1 1 1 1 0 190
Y + 1 0 0 0 1 1 0 1 + 141
0 1 0 0 1 0 1 1 S 331
1 0 1 1 1 1 0 0 Cout

Figure 2.1 – Exemple d’addition binaire

2.3.2 Soustraction binaire

Le tableau 2.2 montre les combinaisons possibles d’entrées et leurs sorties correspon-
dantes pour la soustraction binaire. Le Bin est l’emprunt d’entrée : c’est la valeur qu’il
faut aller chercher à la position plus importante pour effectuer la soustraction. Le Bout est
l’emprunt de sortie : valeur qu’on doit aller chercher à la position précédente.

Un exemple d’addition binaire est montré à la figure 2.2. Le processus est un peu
plus complexe que l’addition : lorsqu’on doit emprunter un bit pour faire la soustraction,
l’emprunt se propage à travers les colonnes jusqu’à ce qu’on trouve un 1. Dans l’exemple,
lorsqu’il faut faire un emprunt à la colonne 3, on doit chercher jusqu’à la colonne 6 pour
trouver un 1. Le 100 devient donc 011 + 1 : le 011 sont les bits modifiés, et le +1 est
l’emprunt.

Gabriel Cormier 6 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

Tableau 2.2 – Soustraction binaire

X Y Bin D Bout
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1

0 10 1 1 10 10
X 1 1 1 0 0 1 0 1 229
Y − 0 0 1 0 1 1 1 0 − 46
1 0 1 1 0 1 1 1 D 183

Figure 2.2 – Exemple d’addition binaire

2.4 Représentation des nombres négatifs

Il existe quelques façons de représenter des nombres négatifs. En représentation

décimale, on utilise l’amplitude et un signe : +49, −53. En représentation binaire, on
peut utiliser le MSB, ou utiliser des méthodes dites à complément.

2.4.1 Représentation avec le MSB

Dans la représentation avec MSB, le MSB représente le signe : un 0 veut dire un chiffre
positif, et un 1 veut dire un chiffre négatif. Par exemple, le chiffre 010101012 = +8510 , et
110101012 = −8510 . Le bit de signe est celui le plus à gauche (le MSB). On perd donc 1 bit
pour représenter l’amplitude des chiffres. Dans un système à n bits, les valeurs possible
sont de :
−(2n−1 − 1) à (2n − 1)
Pour n = 4, les valeurs possibles sont de −7 à 7. La valeur zéro a deux possibilités : 1000 ou
0000.

Dans cette méthode, il y a cependant quelques désavantages : on a beaucoup de

décisions à prendre lorsqu’on fait l’addition (ou la soustraction) et on perd un bit pour le
signe. Pour l’addition :
• Si on a deux nombres de même signe :

Gabriel Cormier 7 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

– On additionne les amplitudes

– Le résultat est de même signe
• Si on a deux nombres de signe différent :
– Il faut vérifier le nombre avec la plus grande amplitude
– Soustraire le plus petit du plus grand
– Le résultat aura le signe du plus grand

2.4.2 Méthode de compléments

Les systèmes à compléments ont été introduits pour simplifier l’opération de soustrac-
tion. On a deux types de complément : complément à R, et complément à R − 1.

De façon générale, le complément à R peut être décrit selon :

r n − D = [(r n − 1) − D] + 1 (2.3)

où D = dn−1 dn−2 · · · d1 d0 , et le MSB indique le signe.

Exemple 6

Quel est le complément à 10 de 184910 ?

Dans ce cas-ci, la base est 10 (r = 10), on utilise 4 chiffres (n = 4), et le chiffre est
D = 1849. Le complément à 10 est :
h i
C = (104 − 1) − 1849 + 1 = 8151

Une autre méthode de faire le calcul est de prendre le complément de chaque chiffre,
individuellement, puis additionner 1 au total. Le complément de chaque chiffre (à la
position x) est (r − 1) − dx .

Exemple 7

Quel est le complément à 10 de 184910 ?

Dans ce cas-ci, la base est 10 (r = 10), et le complément par chiffre est (10 − 1) −
dx .

Gabriel Cormier 8 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

9 9 9 9
− 1 8 4 9
8 1 5 0 + 1 = 8151

2.4.3 Complément à 2

Le complément à 2 (two’s complement) est très utilisé : c’est le système utilisé dans les
ordinateurs. C’est un système de représentation pour les chiffres binaires. Dans ce cas-ci,
la plage de valeurs possible est de −(2n−1 ) à +(2n−1 − 1), pour un nombre à n bits.

Exemple 8

Quel est le complément à 2 de 000100012 ?

1710 = 00010001
⇓
11101110
+1
11101111 = −1710

2.4.4 Complément à 1

Le complément à un est un autre système de représentation des nombres négatifs.

Comme le complément à 2, le MSB indique le signe (1 veut dire un nombre négatif, 0 pour
un nombre positif). On a deux représentations pour le zéro : 00000000 et 111111111. La
plage de valeurs possibles est : −(2n−1 − 1) à +(2n−1 − 1), pour un nombre à n bits.

Exemple 9

Quel est le complément à 1 de 000100012 ?

1710 = 00010001
⇓
11101110 = −1710

Gabriel Cormier 9 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

2.5 Addition et soustraction en complément à 2

Pour faire l’addition et la soustraction dans le système de complément à 2, on néglige

le report au-delà du MSB tant que la somme n’excède pas la limite de n bits. Quelques
exemples sont montrés à la figure 2.3.

+3 0011 −2 1110
+ +4 0100 + −6 1010
+7 0111 −8 1 1000

+6 0110 +4 0100
+ −3 1101 + −7 1001
+3 1 0011 −3 1101

Figure 2.3 – Exemples d’addition binaire en complément à 2

Il y a risque de débordement (overflow) lorsque la somme d’une addition dépasse le

nombre maximal permis. Pour un système à n bits, il y a débordement si la somme est plus
grande que +(2n−1 − 1), ou si la somme est plus petite que −(2n−1 ). Si on additionne deux
nombres de signe différent, il n’y a jamais de débordement. Cependant, si on additionne
deux nombres de même signe, il y a possibilité de débordement. Il y a débordement si
le résultat est de signe différent du signe des nombres additionnés. Deux exemples sont
montrés à la figure 2.4. Le débordement est montré en rouge.

−3 1101 +5 0101
+ −6 1010 + +6 0110
−9 1 0 1 1 1 = +7 +11 1 1 0 1 1 = −5

Figure 2.4 – Exemples de débordement

2.6 Codes binaires

Les codes binaires sont l’ensemble des règles ou conventions qui permettent de représenter
les chiffres décimaux en en code binaire.

Gabriel Cormier 10 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

2.6.1 Décimal codé binaire

Le décimal codé binaire (DCB, ou BCD, binary coded decimal en anglais) est un code
communément utilisé. La représentation est montrée à la figure 2.5.

Décimal Code
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001

Figure 2.5 – Décimal codé binaire

Le décimal codé binaire n’est pas la même chose que la conversion décimale à binaire.
Par exemple, en code binaire le nombre 13 est 1101, mais en DCB c’est 00010011 (chaque
chiffre est convertit séparément). Dans les ordinateurs (ou microcontrôleurs), les opérations
sont effectuées sur le code binaire et non sur le DCB.

2.6.2 Code Gray

Le code Gray est une autre méthode pour coder des nombres en format binaire. C’est
un code où seulement 1 bit change entre chaque nombre successif. La figure 2.6 montre le
code Gray pour un système à 3 bits.

Décimal Binaire Gray

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

Figure 2.6 – Code Gray à 3 bits

Gabriel Cormier 11 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

2.6.3 Code Hamming

Le code Hamming permet de détecter et corriger des erreurs dans des séquences de
bits. On calcul k bits de parité à partir de n bits de données (k < n). Les bits de parité sont
placés à des positions qui sont des puissances de 2. Les n bits de données sont placés dans
les positions restantes. La figure 2.7 montre un exemple de position des bits de parité et
des bits de données, pour un mot de 8 bits.
Position 1 2 3 4 5 6 7 8 9 10 11 12
Valeur P1 P2 d1 P4 d2 d3 d4 P8 d5 d6 d7 d8

Figure 2.7 – Code Hamming pour un mot de 8 bits

Le j e bit de parité (où j = 1, 2, 3, ...k) est calculé en faisant des opérations xor (ou
exclusifs) avec les bits de données dont les positions, lorsque présentées en binaire, sont
des 1. La figure 2.8 montre le calcul des bits de parité pour un mot de 8 bits.
Colonne
Position 4321
P1 ← 0001
P2 ← 0010
0011
P4 ← 0100
0101
0110
0111
P8 ← 1000
1001
1010
1011
1100

Figure 2.8 – Code Hamming et calcul des bits de parité pour un mot de 8 bits

Le calcul des bits de parité est comme suit :

P1 = XOR(3, 5, 7, 9, 11) = XOR(d1 , d2 , d4 , d5 , d7 ) (2.4)
P2 = XOR(3, 6, 7, 10, 11) = XOR(d1 , d3 , d4 , d6 , d7 ) (2.5)
P4 = XOR(5, 6, 7, 12) = XOR(d2 , d3 , d4 , d8 ) (2.6)
P8 = XOR(9, 10, 11, 12) = XOR(d5 , d6 , d7 , d8 ) (2.7)
Exemple : Dans la colonne 1 (pour calculer P1 ), il y a un 1 aux rangées 3, 5, 7, 9, et 11, si on
ignore les rangées qui correspondent aux bits de parité (on saute les rangées 1, 2, 4 et 8).
Dans la colonne 2, pour calculer P2 , il y a des 1 aux rangées 3, 6, 7, 10 et 11.

Gabriel Cormier 12 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

Pour vérifier si le message a été transmit correctement, on fait un processus semblable

à celui du calcul des bits de parité, sauf que les termes utilisés dans le calcul inclus ceux
des bits de parité :

C1 = XOR(1, 3, 5, 7, 9, 11) (2.8)

C2 = XOR(2, 3, 6, 7, 10, 11) (2.9)
C4 = XOR(4, 5, 6, 7, 12) (2.10)
C8 = XOR(8, 9, 10, 11, 12) (2.11)

On forme ensuite un nombre C = C1 C2 C4 C8 .

• Si C = 0, il n’y a pas d’erreur.
• Si C = X, il y a erreur à la position X : on doit prendre le complément du bit à
la position X pour corriger l’erreur. Exemple : pour un mot à 8 bits, si on trouve
C = 0101, le bit à la position 5 contient une erreur.

Exemple 10

Calculer le code de Hamming pour le mot suivant : 11000100.

On calcule les bits de parité :

P1 = XOR(d1 , d2 , d4 , d5 , d7 ) = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 = 0
P2 = XOR(d1 , d3 , d4 , d6 , d7 ) = 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 0 = 0
P4 = XOR(d2 , d3 , d4 , d8 ) = 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1
P8 = XOR(d5 , d6 , d7 , d8 ) = 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1

On transmet le message : 001110010100.

On peut augmenter l’efficacité de la détection d’erreur en ajoutant un bit de parité à la

fin de la séquence. Ceci permet de détecter 2 erreurs. À la réception, on calcule C, comme
le code de Hamming normal, et on vérifie la parité P .
• Si C = 0 et P = 0, il n’y a pas d’erreur.
• Si C , 0 et P = 1, il y a une erreur qu’on peut corriger.
• Si C , 0 et P = 0, il y a deux erreurs (mais on ne peut pas les corriger).
• Si C = 0 et P = 1, alors P est une erreur.

2.6.4 Code ASCII

Les systèmes numériques (ordinateurs) ne manipulent pas seulement des nombres,

mais aussi des lettres et des signes ou caractères spéciaux (comme !, $, etc). Il faut donc

Gabriel Cormier 13 GELE2442

 CHAPITRE 2. SYSTÈMES DE NOMBRES ET CODES

avoir un code spécial pour représenter ces caractères alphanumériques. Le système ASCII
(American Standard Code for Information Interchange) est un code très utilisé. C’est un code
à 7 bits. Cependant, il ne permet pas de représenter les caractères spéciaux de plusieurs
langages du monde ; de plus en plus, on préfère le format UTF-8 (Unicode), qui permet de
représenter beaucoup plus de caractères spéciaux. Le tableau 2.3 présente le code ASCII.

Tableau 2.3 – Tableau ASCII

b7 b6 b5
b4 b3 b2 b1 000 001 010 011 100 101 110 111
0000 NUL DLE SP 0 @ P ‘ p
0001 SOH DC1 ! 1 A Q a q
0010 STX DC2 ” 2 B R b r
0011 ETX DC3 # 3 C S c s
0100 EOT DC4 $ 4 D T d t
0101 ENQ NAK % 5 E U e u
0110 ACK SYN & 6 F V f v
0111 BEL ETB ’ 7 G W g w
1000 BS CAN ( 8 H X h x
1001 HT EM ) 9 I Y i y
1010 LF SUB * : J Z j z
1011 VT ESC + ; K [ k {
1100 FF FS , < L \ l |
1101 CR GS − = M ] m }
1110 SO RS . > N ˆ n ˜
1111 SI US / ? O o DEL

Gabriel Cormier 14 GELE2442

Chapitre 3
Principes de la logique combinatoire

La logique combinatoire est la logique où la sortie dépend seulement des entrées. L’autre
type de logique, la logique séquentielle, est celle où la sortie dépend des entrées actuelles et
de la sortie précédente. Ce type de logique sera présenté plus tard. La logique combinatoire
est la base du design de circuits logiques.

3.1 Algèbre booléenne

L’algèbre booléenne est l’algèbre utilisée pour les systèmes binaires ; il y a seulement
deux valeurs : 0 ou 1. On y verra certaines propriétés. Le tableau 3.1 présente les postulats
les plus importants de l’algèbre booléenne. Note : Il n’y a pas de soustraction ou de division
dans l’algèbre booléenne.

Tableau 3.1 – Postulats importants de l’algèbre booléenne

(A1) X = 0 si X , 1 (A1’) X = 1 si X , 0
(A2) Si X = 0 ⇒ X 0 = 1 (A2’) Si X = 1 ⇒ X 0 = 0
(A3) 0·0 = 0 (A3’) 1+1 = 1
(A4) 1·1 = 1 (A4’) 0+0 = 0
(A5) 0·1 = 1·0 = 0 (A5’) 1+0 = 0+1 = 1

Le tableau présente certains théorèmes importants.

1
 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

Tableau 3.2 – Théorèmes importants de l’algèbre booléenne

Numéro Nom Théorème

T5 Complément X + X 0 = 1, ou X · X 0 = 0
T6 Idempotence X + X = X, ou X · X = X
T8 Distributivité X + (Y · Z) = (X + Y ) · (X + Z)
T9 Absorption X + (X · Y ) = X
T10 Combinaison X ·Y +X ·Y0 = X

Dualité

Le principe de dualité peut être exprimé ainsi : si dans une expression on interchange
l’opérateur et l’élément d’identité, l’égalité demeure (0 ↔ 1, · ↔ +). La figure 3.1 montre
quelques exemples de cette propriété.

Dualité
X +0 = X X ·1 = X
X + X0 = 1 X · X0 = 0

Figure 3.1 – Exemples de la dualité

Théorème de Demorgan

Le théorème de Demorgan permet d’interchanger l’opérateur + et ·, et l’opérateur de

complément :

(X + Y + Z)0 = X 0 · Y 0 · Z 0
(X · Y · Z)0 = X 0 + Y 0 + Z 0

Figure 3.2 – Exemples du théorème de Demorgan

3.1.1 Fonction booléenne

Une fonction booléenne est une expression formée de variables binaires, comme F =
X · Y + Z 0 . Le symbole · représente ET (AND), et le symbole + représente OU (OR). On
représente souvent une fonction booléenne par une table de vérité : c’est un tableau qui
représente toutes les combinaisons possibles d’entrées et de sortie(s). Pour n variables
d’entrée, il y a 2n possibilités. La figure 3.3 montre un exemple de table de vérité.

Gabriel Cormier 2 GELE2442

 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

X Y Z F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

Figure 3.3 – Exemple de table de vérité pour F = X · Y + Z 0

3.1.2 Complément d’une fonction

Le complément d’une fonction F s’écrit F 0 . On l’obtient en changeant les 0 pour des 1

(et vice-versa) dans la table de vérité. On peut aussi l’obtenir en utilisant le théorème de
Demorgan.

Exemple 1

Calculer le complément de la fonction F = X 0 Y Z 0 + X 0 Y 0 Z

F 0 = (X 0 Y Z 0 + X 0 Y 0 Z)0 = (X 0 Y Z 0 )0 · (X 0 Y 0 Z) = (X + Y 0 + Z) · (X + Y + Z 0 )

3.1.3 Mintermes et maxtermes

Une fonction booléenne peut être exprimée de l’une de deux façons : une somme de
produits, ou un produit de sommes. Les termes multipliés sont des mintermes, et les termes
de somme sont nommés maxtermes. La figure 3.4 montre les mintermes et maxtermes d’une
fonction à 3 bits.

Pour générer les mintermes, on utilise le complément de la variable aux endroits où
on a un 0 dans la table de vérité. Pour générer les maxtermes, on utilise le complément
lorsqu’il y a un 1 dans la table de vérité. Une fonction peut ensuite être exprimée comme
une somme de mintermes, ou un produit de maxtermes. Par la suite, on peut simplifier
la fonction en utilisant les théorèmes appropriés. Une fonction est créée en à l’aide de
mintermes en utilisant les termes où la fonction est 1. Pour créer une fonction à l’aide de
maxtermes, on utilise les termes où la fonction est 0.

Gabriel Cormier 3 GELE2442

 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

X Y Z Minterme Maxterme
0 0 0 0 X0 · Y 0 · Z0 X +Y +Z
1 0 0 1 X0 · Y 0 · Z X + Y + Z0
2 0 1 0 X0 · Y · Z0 X +Y0 +Z
3 0 1 1 X0 · Y · Z X + Y 0 + Z0
4 1 0 0 X · Y 0 · Z0 X0 + Y + Z
5 1 0 1 X ·Y0 ·Z X0 + Y + Z0
6 1 1 0 X · Y · Z0 X0 + Y 0 + Z
7 1 1 1 X ·Y ·Z X0 + Y 0 + Z0

Figure 3.4 – Mintermes et maxtermes à 3 bits

Exemple 2

Exprimer la fonction ayant la table de vérité de la figure 3.5 à l’aide de mintermes et

maxtermes.

X Y Z F
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

Figure 3.5 – Table de vérité pour une fonction

Les mintermes sont exprimés avec des m minuscules ; les termes où la fonction est 1
sont : 0, 3, 4, 6 et 7.
X
F= m0 , m 3 , m 4 , m 6 , m 7
= X0 · Y 0 · Z0 + X0 · Y · Z + X · Y 0 · Z0 + X · Y · Z0 + X · Y · Z

Les maxtermes sont exprimés avec des M majuscules ; les termes où la fonction est 0 sont :
1, 2 et 5.
Y
F= M1 , M 2 , M 5
= (X + Y + Z 0 ) · (X + Y 0 + Z) · (X 0 + Y + Z 0 )

Gabriel Cormier 4 GELE2442

 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

3.2 Portes logiques

Il y a trois fonctions logiques de base présentées dans la section précédente : ET (AND),

représenté par le symbole · ; OU (OR), représenté par + ; et NON (NOT ; complément),
représenté par 0 . Ces trois fonctions permettent la création de n’importe quelle fonction
complexe. Ces trois fonctions de base, et leur symboles (circuits) correspondants sont
montrés à la figure 3.6. Le cercle à la sortie de la porte NON indique que la porte logique a
un comportement d’inversion. La porte NON s’appelle aussi un inverseur.

X X
X·Y X+Y X X0
Y Y

X Y X·Y X Y X+Y X X0
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1

ET OU NON

Figure 3.6 – Trois fonctions logiques de base

Trois autres portes logiques sont fréquemment utilisées : la porte NAND (NON-ET),
la porte NOR (NON-OU) et la porte XOR (Exclusivement-OU). Ces portes, ainsi que leur
table de vérité, sont montrées à la figure 3.7.

X X X
X ·Y X +Y X⊕Y
Y Y Y

X Y X ·Y X Y X +Y X Y X⊕Y
0 0 1 0 0 1 0 0 0
0 1 1 0 1 0 0 1 1
1 0 1 1 0 0 1 0 1
1 1 0 1 1 0 1 1 0

NAND NOR XOR

Figure 3.7 – Trois fonctions logiques communes

Gabriel Cormier 5 GELE2442

 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

3.3 Création des circuits logiques

Pour créer des circuits logiques à partir de fonctions complexes, on combine les min-
termes (ou maxtermes) avec les fonctions logiques de base. Chaque minterme est créé à
partir des portes logiques de base. Soit la fonction logique suivante :

F1 = X + Y 0 Z (3.1)

Le circuit créé est montré à la figure 3.8. L’inverseur est utilisé pour créer Y 0 , puis la porte
AND pour créer Y 0 Z, et finalement la porte OR permet de créer la fonction F1 .

X
F1

Y
Y 0Z
Z

Figure 3.8 – Circuit logique de la fonction F1

Exemple 3

On a trois juges qui contrôlent le départ d’une course. La course a lieu si au moins deux
des trois juges sont prêts. Créer le circuit logique qui représente le départ d’une course.

Les trois juges forment les trois entrées : A, B et C. Le départ de la course représente la
sortie F. On peut ensuite créer manuellement la table de vérité de cette fonction.

A B C F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

Figure 3.9 – Table de vérité de la fonction de l’exemple 3

P On peut ensuite exprimer cette fonction comme une somme de mintermes : F =

(3, 5, 6, 7). Puis on va simplifier la fonction.

Gabriel Cormier 6 GELE2442

 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

X
F= (3, 5, 6, 7) = ABC + ABC + ABC + ABC
= ABC + ABC + ABC + ABC + ABC + ABC Th.6
= BC(A + A) + AC(B + B) + AB(C + C)
= AB + BC + AC Th.5

À partir de la fonction simplifiée, on peut créer le circuit.

A
B

B
F
C

A
C

Figure 3.10 – Circuit logique de l’exemple 3

3.4 Implémentation NAND

Les circuits logiques sont souvent implantés avec des portes NAND et NOR plutôt que
des portes AND et OR. Les portes NAND et NOR nécessitent moins de transistors pour
l’implémentation, donc prennent moins de superficie sur les circuits intégrés, et donc sont
moins chers. Comme exemple, une porte NAND à 2 entrés nécessite 4 transistors, tandis
qu’une porte OR créée avec la même technologie nécessite 6 transistors. Puisque les portes
NAND et NOR sont très communes, des méthodes ont été développées pour faire le design
de circuits logiques avec ces portes.

3.4.1 Création des portes NAND

Une porte NAND peut être créée de deux façons : à partir d’une porte AND, en ajoutant
une bulle d’inversion à la sortie, et à partir d’une porte OR, en ajoutant des bulles d’inver-
sion aux entrées. La conversion d’une porte OR est montrée à la figure 3.11. Des bulles
d’inversion sont ajoutées à l’entrée de la porte OR ; à l’aide du théorème de Demorgan, on
obtient la même équation de sortie qu’une porte NAND.

Gabriel Cormier 7 GELE2442

 CHAPITRE 3. PRINCIPES DE LA LOGIQUE COMBINATOIRE

X (X + Y + Z)0 X
X0 · Y 0 · Z0
Y Y
= (X + Y + Z)0
Z Z

Figure 3.11 – Porte OR transformée en porte NAND

3.4.2 Transformation AND-OR à NAND

Pour effectuer une transformation AND-OR à NAND, il faut que le circuit (ou la
fonction logique) soit de la forme d’une somme de produits, et donc exprimée par des
mintermes. Comme exemple, on prend la fonction suivante :

F = AB + CD (3.2)

Le circuit correspondant à cette fonction est montré à la figure 3.12, sous la forme d’un
circuit AND-OR.

A
B
F
C
D

Figure 3.12 – Fonction F = AB + CD implantée en logique AND-OR

Pour transformer les portes à des portes NAND, on ajoute des bulles d’inversion à la
sortie des portes AND et à l’entrée de la porte OR. La logique reste la même puisqu’il y a
deux inversions consécutives ((X 0 )0 = X). La figure 3.13 montre cette transformation. Le
circuit est maintenant constitué de portes NAND seulement.

A A
B B
F F
C C
D D

Figure 3.13 – Portes AND-OR transformées en portes NAND

Gabriel Cormier 8 GELE2442

Chapitre 4
Minimisation

La minimisation est une partie importante du design de circuits logiques. On doit

simplifier le plus possible la fonction logique avant d’essayer d’implanter le circuit logique.
Deux types de minimisation sont possibles : minimisation au niveau logique, et la minimi-
sation au niveau électronique. Dans le premier cas, on manipule les équations pour obtenir
une fonction logique plus simple. Dans le deuxième cas, on réarrange le circuit logique
pour réduire sa complexité, et son coût.

4.1 Diagrammes de Karnaugh

La complexité des circuits logiques est directement reliée à la complexité de la fonction

logique qu’elle implémente. On peut utiliser les théorèmes pour simplifier la fonction
logique, mais ce peut être long et difficile pour des fonctions de plusieurs variables. Une
méthode très utilisée pour simplifier des fonctions logiques est la méthode des diagrammes
de Karnaugh.

Les équations produites par les diagrammes de Karnaugh sont toujours sous l’une de
deux formes : somme de produits ou produits de sommes. L’équation résultante minimise
le nombre de termes, et donc la complexité du circuit logique correspondant.

4.1.1 Diagramme à deux variables

Le plus simple diagramme de Karnaugh est celui à deux variables, montré à la figure
4.1. Une fonction à deux variables possède un maximum de quatre mintermes, et donc

1
 CHAPITRE 4. MINIMISATION

le diagramme de Karnaugh est un carré divisé en quatre. La première figure montre

l’emplacement des mintermes, et la seconde figure montre l’équation qui correspond à
chaque minterme.

Y Y
Y Y
0 1 0 1
X X
0 m0 m1 0 X0Y 0 X0Y

X 1 m2 m3 X 1 XY 0 XY

Figure 4.1 – Diagramme de Karnaugh pour une fonction à 2 variables

Le diagramme de Karnaugh (ou table de Karnaugh) est rempli à partir de la table de

vérité. On ajoute les 1 et 0 aux endroits appropriés, selon l’emplacement du minterme.
Pour simplifier la fonction, on essaie de créer des rectangles les plus gros possibles en
regroupant des 1, pour obtenir des mintermes, ou des 0, pour obtenir des maxtermes. Deux
exemples sont montrés à la figure 4.2.

Y Y
Y Y
0 1 0 1
X X
0 0 0 0 0 1

X 1 0 1 X 1 1 1

X ·Y X +Y
Figure 4.2 – Exemples de diagrammes de Karnaugh pour une fonction à 2 variables

4.1.2 Diagramme à trois variables

Le diagramme de Karnaugh pour trois variables est montré à la figure 4.3. Noter que
les mintermes sont organisés comme un code Gray : un seul bit change en passant d’une
case à une autre. Le processus de simplification est le même que celui de deux variables :
on essaie de créer des carrés ou rectangles qui englobent le plus de 1. Dans tous les cas,
que ce soit à 2, 3, 4 variables ou plus, il faut minimiser le nombre de regroupements, et
maximiser la taille des regroupements.

Gabriel Cormier 2 GELE2442

 CHAPITRE 4. MINIMISATION

Y
YZ
00 01 11 10
X
0 m0 m1 m3 m2

X 1 m4 m5 m7 m6

Figure 4.3 – Diagramme de Karnaugh pour une fonction à 3 variables

Exemple 1
P
Simplifier la fonction suivante : F = (2, 3, 4, 5).

Pour chaque minterme de la fonction, on place un 1 à l’endroit correspondant dans le

diagramme de Karnaugh.

Y
YZ
00 01 11 10
X
0 0 0 1 1

X 1 1 1 0 0

Figure 4.4 – Diagramme de Karnaugh pour l’exemple 1

La fonction simplifiée donne : F = XY 0 + X 0 Y .

Exemple 2
P
Simplifier la fonction suivante : F = (3, 4, 6, 7).

La fonction simplifiée donne F = Y Z + XZ 0 .

Pour un diagramme de Karnaugh à trois variables, le nombre de carrés encerclés doit

toujours être une puissance de 2. Plus on encercle de carrés, moins il y aura de variables
dans le produit créé :

Gabriel Cormier 3 GELE2442

 CHAPITRE 4. MINIMISATION

Y
YZ
00 01 11 10
X
0 0 0 1 0

X 1 1 0 1 1

Figure 4.5 – Diagramme de Karnaugh pour l’exemple 2

• Un carré de un minterme représente un terme à trois variables,

• Un groupe de deux mintermes représente un terme à deux variables,
• Un groupe de quatre mintermes représente un terme à une variable,
• Un groupe de huit mintermes englobe tout le diagramme, et est toujours égal à 1.

4.1.3 Diagramme à quatre variables

Le diagramme de Karnaugh à quatre variables est construit de la même façon que

ceux de deux et trois variables. Dans ce cas-ci, on a un carré de 4×4 cases. Le diagramme
est montré à la figure 4.6. Tout comme les diagrammes à trois variables, pour simplifier
une fonction, il faut minimiser le nombre de regroupements, et maximiser la taille des
regroupements.

Y
YZ
00 01 11 10
WX
00 m0 m1 m3 m2

01 m4 m5 m7 m6
X
11 m12 m13 m15 m14
W
10 m8 m9 m11 m10

Figure 4.6 – Diagramme de Karnaugh pour une fonction à 4 variables

Gabriel Cormier 4 GELE2442

 CHAPITRE 4. MINIMISATION

Exemple 3
P
Simplifier la fonction suivante : F = (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

Y
YZ
00 01 11 10
WX
00 1 1 0 1

01 1 1 0 1
X
11 1 1 0 1
W
10 1 1 0 0

Figure 4.7 – Diagramme de Karnaugh pour l’exemple 3

La fonction simplifiée donne F = Y 0 + XZ 0 + W 0 Z 0 .

4.2 Impliquants premiers

En choisissant des carrés adjacents dans un diagramme de Karnaugh, il faut :

1. S’assurer que tous les mintermes sont couverts
2. Minimiser le nombre de termes
3. Maximiser le nombre de carrés recouverts par un groupement
Il y a parfois plus d’une solution possible, ou plus d’une option pour couvrir tous les
termes. On peut simplifier un peu le choix des regroupements si on définit deux types de
regroupements :
1. Impliquant premier : c’est un regroupement obtenu en groupant le maximum de
cases adjacentes dans le diagramme de Karnaugh.
2. Impliquant premier essentiel : si une case est couverte par un seul impliquant
premier, alors cet impliquant est essentiel.
Les impliquants premiers d’une fonction sont obtenus en groupant le maximum de cases.
Ceci veut dire, par exemple, qu’un 1 seul sur le diagramme représente un impliquant
primaire s’il n’est pas adjacent à aucun autre 1. Les impliquants premiers essentiels sont
ceux qui recouvrent seulement une case.

Gabriel Cormier 5 GELE2442

 CHAPITRE 4. MINIMISATION

Exemple 4

Identifier les impliquants premiers essentiels de la fonction suivante à 3 entrées :

X
F= (1, 3, 4, 5, 6)

Le diagramme de Karnaugh est :

Y
YZ
00 01 11 10
X
0 0 1 1 0

X 1 1 1 0 1

Figure 4.8 – Diagramme de Karnaugh pour l’exemple 4

Il y a quelques possibilités d’impliquants. Les mintermes 3 et 6 sont seulement couverts

par un impliquant. Ceux-ci sont donc des impliquants premiers essentiels. Les termes
XY 0 et Y 0 Z ne sont pas des impliquants premiers essentiels. Pour couvrir tous les 1 du
diagramme, on doit choisir l’un ou l’autre :

Y Y
YZ YZ
00 01 11 10 00 01 11 10
X X
0 0 1 1 0 0 0 1 1 0

X 1 1 1 0 1 X 1 1 1 0 1

Z Z

Figure 4.9 – Deux choix d’impliquants pour l’exemple 4

La fonction est :
F = X 0 Z + XZ 0 + Y 0 Z = X 0 Z + XZ 0 + XY 0

Gabriel Cormier 6 GELE2442

 CHAPITRE 4. MINIMISATION

Exemple 5

Identifier les impliquants premiers essentiels de la fonction suivante à 4 entrées :

X
F= (0, 2, 3, 5, 7, 8, 9, 10, 11, 13, 15)

Le diagramme de Karnaugh de cette fonction est montré à la figure 4.10. Il y a plusieurs

possibilités pour créer des regroupements.

Y
YZ
00 01 11 10
WX
00 1 0 1 1

01 0 1 1 0
X
11 0 1 1 0
W
10 1 1 1 1

Figure 4.10 – Diagramme de Karnaugh pour l’exemple 5

Les impliquants premiers essentiels sont montrés à la figure 4.11a. Ce sont des impli-
quants essentiels, parce que les deux 1 encerclés en bleu peuvent seulement être groupés
par les impliquants montrés. En groupant ces 1, il faut maximiser le nombre de termes
groupés, et donc on obtient les impliquants de la figure 4.11a. Les impliquants premiers
sont montrés à la figure 4.11b. Il y a plusieurs possibilités pour regrouper les mintermes
qui ne sont pas groupés par les impliquants essentiels. On a quatre possibilités pour la
fonction simplifiée :

F = BD + BD 0 + CD + AD
= BD + BD 0 + CD + AB0
= BD + BD 0 + B0 C + AD
= BD + BD 0 + B0 C + AB0

Gabriel Cormier 7 GELE2442

 CHAPITRE 4. MINIMISATION

Y Y
YZ YZ
00 01 11 10 00 01 11 10
WX WX
00 1 0 1 1 00 1 0 1 1

01 0 1 1 0 01 0 1 1 0
X X
11 0 1 1 0 11 0 1 1 0
W W
10 1 1 1 1 10 1 1 1 1

Z Z
a) Impliquants premiers essentiels b) Impliquants premiers
Figure 4.11 – Diagramme de Karnaugh pour l’exemple 5

4.3 Conditions indifférentes

Jusqu’à maintenant, lorsqu’on crée une table de vérité pour une fonction, on place les 1
aux endroits où la fonction est vrai, puis on rempli le reste des combinaisons de 0. Dans
certains cas, il y a des combinaisons d’entrées qui ne sont pas possibles lorsqu’on crée
des tables de vérité. Par exemple, en DCB, il y a 6 combinaisons qui ne sont pas utilisées
(de 10 à 15). La plupart du temps, lorsque des combinaisons ne sont pas utilisées, on est
indifférent à la valeur de sortie. On utilise alors un X (au lieu d’un 0 ou 1) dans la table de
vérité. En anglais, cette condition est appelée un don’t care. Les mintermes ou maxtermes
qui ont des conditions indifférentes sont exprimées avec un d.

Les conditions indifférentes peuvent être utilisées dans les diagrammes de Karnaugh
pour créer des regroupements plus gros. Par contre, il n’est pas nécessaire d’utiliser ces
conditions ; on les utilise seulement pour faire des regroupements plus gros, pas pour créer
plus de regroupements.

Exemple 6

Simplifier la fonction suivante :

X
F(W , X, Y , Z) = (1, 2, 3, 7, 11, 15) + d(0, 5)

Le diagramme de Karnaugh est montré à la figure 4.12. On a deux groupes de 4

mintermes : a utilisé un des X pour faire un groupe plus gros. L’autre X n’est pas utilisé.
La fonction est :
F = W 0 X 0 + ZY

Gabriel Cormier 8 GELE2442

 CHAPITRE 4. MINIMISATION

Y
YZ
00 01 11 10
WX
00 X 1 1 1

01 0 X 1 0
X
11 0 0 1 0
W
10 0 0 1 0

Figure 4.12 – Diagramme de Karnaugh pour l’exemple 6

Exemple 7

Simplifier la fonction suivante :

X
F(A, B, C, D) = (0, 4, 10, 14) + d(1, 2, 3, 5, 6, 11, 15)

Le diagramme de Karnaugh est montré à la figure 4.13. On a deux groupes de 4

mintermes qui utilisent des X. Les autres X ne sont pas utilisés.

C
CD
00 01 11 10
AB
00 1 X X X

01 1 X 0 X
B
11 0 0 X 1
A
10 0 0 X 1

Figure 4.13 – Diagramme de Karnaugh pour l’exemple 7

La fonction est :
F = A0 C 0 + CD 0

Gabriel Cormier 9 GELE2442

 CHAPITRE 4. MINIMISATION

4.4 Simplification par produit de sommes

On peut aussi utiliser les diagrammes de Karnaugh pour simplifier des fonctions
représentées par un produit de sommes. Dans ce cas-ci, on modifie un peu la procédure.
Au lieu de faire des regroupements de 1, on fait les regroupements avec des zéros ; ceci
nous donne le complément de la fonction. On applique ensuite le théorème de Demorgan
à la fonction simplifiée. Cette méthode fonctionne aussi avec les conditions indifférentes.

Exemple 8

Simplifier la fonction suivante sous un produit de sommes.

X
F(A, B, C, D) = (0, 1, 2, 5, 8, 9, 10)

Le diagramme de Karnaugh est montré à la figure 4.14. On regroupe les 0 au lieu des 1.

C
CD
00 01 11 10
AB
00 1 1 0 1

01 0 1 0 0
B
11 0 0 0 0
A
10 1 1 0 1

Figure 4.14 – Diagramme de Karnaugh pour l’exemple 8

La fonction sous forme de somme de produit est :

F 0 = AB + CD + BD 0

Puis on applique le théorème de Demorgan, pour obtenir un produit de sommes :

F = (A0 + B0 ) · (C 0 + D 0 ) · (B0 + D)

Gabriel Cormier 10 GELE2442