Logique booléenne

Le fonctionnement des ordinateurs s’appuie sur quelques principes très simples, mais qui sont utilisés à une très grande échelle. Le premier principe est que toute l’information peut s’encoder sous une forme binaire, c’est-à-dire une suite de bits. Un bit est l’unité de représentation de l’information. Un bit peut prendre deux valeurs:

• 0

• 1

On peut associer une signification à ces bits. Il est par exemple courant de considérer que le bit 0 représente la valeur Faux tandis que le bit 1 représente la valeur Vrai. C’est une convention qui est utile dans certains cas, mais n’est pas toujours nécessaire et peut parfois porter à confusion.

Avec ces deux valeurs booléennes, il est intéressant de définir des opérations. Une opération booléenne est une fonction qui prend en entrée 0, 1 ou plusieurs bits et retourne un résultat.

Fonctions booléennes

La fonction la plus simple est la fonction identité. Elle prend comme entrée un bit et retourne la valeur de ce bit. On peut la définir en utilisant une table de vérité qui indique la valeur du résultat de la fonction pour chaque valeur possible de son entrée. Dans la table ci-dessous, la colonne x contient les différentes valeurs possibles de l’entrée x et la valeur du résultat pour chacune des valeurs possibles de x.

x	identité(x)
0	0
1	1

Cette fonction n’est pas très utile en pratique. Elle nous permet d’illustrer une table de vérité simple dans laquelle il y a une valeur binaire en entrée et une valeur binaire également en sortie.

Une fonction plus intéressante est l’inverseur, aussi dénommée NOT en anglais. Cette fonction prend comme entrée un bit. Si le bit d’entrée vaut 1, elle retourne 0. Tandis que si le bit d’entrée vaut 0, elle retourne 1. Cette fonction sera très fréquemment utilisée pour construire des circuits électroniques utilisés dans les ordinateurs.

x	NOT(x)
0	1
1	0

Il y a encore deux fonctions que l’on peut construire avec une seule entrée binaire. La première, baptisée Toujours0, retourne toujours la valeur 0, quelle que soit son entrée. La seconde, baptisée Toujours1 retourne toujours la valeur 1. Voici leurs tables de vérité.

x	Toujours0(x)
0	0
1	0

x	Toujours1(x)
0	1
1	1

La logique booléenne devient nettement plus intéressante lorsque l’on considère des fonctions qui prennent plus d’une entrée.

Fonctions booléennes à deux entrées

Plusieurs fonctions booléennes classiques existent. Les premières correspondent à la conjonction (et) et à la disjonction (ou) en logique. Commençons par la fonction AND. Celle-ci correspond à la table de vérité suivante:

x	y	AND(x,y)
0	0	0
0	1	0
1	0	0
1	1	1

Cette table comprend quatre lignes qui correspondent à toutes les combinaisons possibles des deux entrées de la fonction. On remarque aisément que la fonction AND(x,y) retourne la valeur 1 uniquement lorsque ses deux entrées ont la valeur 1. Si une des deux entrées de la fonction AND(x,y) a la valeur 0, alors sa sortie est nécessairement 0. Cette fonction est bien l’équivalent de la conjonction logique si l’on applique la convention que 0 représente la valeur Faux.

La fonction OR(x,y), quant à elle, est l’équivalent de la disjonction logique. Sa table de vérité est reprise ci-dessous.

x	y	OR(x,y)
0	0	0
0	1	1
1	0	1
1	1	1

On remarque aisément que la fonction OR(x,y) correspond bien à la disjonction logique lorsque 1 représente la valeur Vrai. Cette fonction OR(x,y) ne retourne la valeur 0 que si ses deux entrées valent 0. Dans tous les autres cas, elle retourne la valeur 1.

Ces fonctions peuvent être combinées entre elles. Un premier exemple est d’appliquer un inverseur (opération NOT au résultat de la fonction AND). Cette fonction booléenne s’appelle généralement NAND (NOT AND) et sa table de vérité est la suivante. On pourra dire que \(NAND(x,y) \iff NOT(AND(x,y))\).

x	y	NAND(x,y)
0	0	1
0	1	1
1	0	1
1	1	0

De même, la fonction NOR s’obtient en inversant le résultat de la fonction OR. On pourra dire que \(NOR(x,y) \iff NOT(OR(x,y))\).

x	y	NOR(x,y)
0	0	1
0	1	0
1	0	0
1	1	0

Il est important de noter que NOR(x,y) n’est pas équivalent à la fonction OR(NOT(x),NOT(y)). La table de vérité de cette dernière fonction est reprise ci-dessous.

x	y	NOT(x)	NOT(y)	OR(NOT(x),NOT(y))
0	0	1	1	1
0	1	1	0	1
1	0	0	1	1
1	1	0	0	0

Il existe d’autres fonctions booléennes à deux entrées qui sont utiles en pratique. Parmi celles-ci, on retrouve la fonction XOR(x,y) qui retourne la valeur 1 uniquement si une seule de ses entrées a la valeur 1. Sa table de vérité est reprise ci-dessous. On remarquera qu’elle diffère de celle des autres fonctions booléennes que nous avons déjà présenté.

x	y	XOR(x,y)
0	0	0
0	1	1
1	0	1
1	1	0

Algèbre booléenne

Ces fonctions booléennes ont des propriétés importantes que l’on peut facilement démontrer en utilisant des tables de vérité.

• \(AND(1,x) \iff x\)

• \(AND(0,x) \iff 0\)

• \(OR(1,x) \iff 1\)

• \(OR(0,x) \iff x\)

A titre d’exemple, regardons la table de vérité de la dernière propriété:

x	0	OR(0,x)
0	0	0
1	0	1

Dans certains cas, on peut être amené à appliquer une fonction booléenne à deux entrées identiques ou l’une inverse de l’autre. En utilisant les tables de vérité, on peut aisément démontrer que:

• \(AND(x,x) \iff x\)

• \(OR(x,x) \iff x\)

• \(AND(NOT(x),x) \iff 0\)

• \(OR(NOT(x),x) \iff 1\)

A titre d’exemple, regardons la table de vérité de la dernière propriété:

x	NOT(x)	OR(NOT(x),x)
0	1	1
1	0	1

Les opérations AND et OR sont commutatives et associatives comme les opérations arithmétiques d’addition et de multiplication.

• \(AND(x,y) \iff AND(y,x)\) (commutativité)

• \(OR(x,y) \iff OR(y,x)\) (commutativité)

• \(AND(x,AND(y,z)) \iff AND(AND(x,y),z)\) (associativité)

• \(OR(x,OR(y,z)) \iff OR(OR(x,y),z)\) (associativité)

Ces lois d’associativité sont importantes car elles vont nous permettre de facilement construire des fonctions booléennes qui prennent un nombre quelconque d’entrées en utilisant des fonctions à deux entrées comme briques de base.

La distributivité est une autre propriété qui relie les fonctions AND et OR.

• \(AND(x,OR(y,z)) \iff OR( AND(x,y), AND(x,z) )\) (distributivité)

• \(OR(x,AND(y,z)) \iff AND( OR(x,y), OR(x,z) )\) (distributivité)

Lorsque l’on ajoute la fonction NOT, on obtient deux autres propriétés utiles en pratique.

• \(AND(x,OR(NOT(x),y)) \iff AND(x,y)\)

• \(OR(x,AND(NOT(x),y)) \iff OR(x,y)\)

Enfin, les trois opérations AND, OR et NOT sont reliées entre elles par les lois de De Morgan. On peut facilement démontrer, par exemple en utilisant des tables de vérité, que:

• NOT( OR(x,y) ) = AND ( NOT(x), NOT(y) )

• NOT( AND(x,y) ) = OR ( NOT(x), NOT(y) )

Ce lois sont très utiles lorsque l’on doit manipuler des fonctions booléennes.

Fonctions booléennes à plus de deux entrées

En utilisant l’associativité, on peut facilement construire des fonctions à plus de deux entrées. Ainsi, la fonction AND à trois entrées \(AND(x,y,z) \iff AND(x,AND(y,z)) \iff AND(AND(x,y),z)\). Sa table de vérité est sans surprise la suivante.

x	y	z	AND(x,y,z)
0	0	0	0
0	1	0	0
1	0	0	0
1	1	0	0
0	0	1	0
0	1	1	0
1	0	1	0
1	1	1	1

De la même façon, on peut obtenir la fonction OR à plus de deux entrées: \(OR(x,y,z) \iff OR(x,OR(y,z)) \iff OR(OR(x,y),z)\).

En plus de ces fonctions booléennes classiques, il est possible de construire deux autres fonctions qui sont très utiles en pratique. La première est le multiplexeur qui permet de « sélectionner » une valeur d’entrée. La table de vérité du multiplexeur est reprise ci-dessous.

x	y	sel	out
0	0	0	0
0	1	0	0
1	0	0	1
1	1	0	1
0	0	1	0
0	1	1	1
1	0	1	0
1	1	1	1

On remarque aisément que la sortie du multiplexeur dépend de l’entrée marquée sel (pour sélecteur). Lorsque sel vaut 0, la sortie du multiplexeur est égale à sa première entrée (x). Lorsque sel vaut 1, sa sortie est égale à sa seconde entrée (y). On peut résumer ceci avec la table de vérité ci-dessous:

sel	out
0	x
1	y

La fonction duale du multiplexeur est le démultiplexeur. Un démultiplexeur a deux entrées, in et sel et deux sorties, x et y. Son comportement est le suivant:

• lorsque l’entrée sel vaut 0, alors la sortie x a la même valeur que l’entrée in tandis que la sortie y vaut 0

• lorsque l’entrée sel vaut 1, alors la sortie y a la même valeur que l’entrée in tandis que la sortie x vaut 0

La table de vérité correspondant au démultiplexeur est présentée ci-dessous.

in	sel	x	y
0	0	0	0
0	1	0	0
1	0	1	0
1	1	0	1

Tant le multiplexeur que le démultiplexeur peuvent s’implémenter en utilisant des portes AND, OR et des inverseurs. Prenons comme exemple le multiplexeur. Nous verrons dans la section suivante qu’il est possible de l’implémenter en utilisant une fonction OR à quatre entrées et des fonctions AND à trois entrées.

Synthèse de fonctions booléennes

L’intérêt des fonctions booléennes est qu’il est possible de concevoir des fonctions booléennes pour supporter n’importe quelle table de vérité. Prenons comme exemple la fonction XOR qui retourne 1 lorsque ses deux entrées sont différentes et 0 sinon. Sa table de vérité est reprise ci-dessous.

x	y	XOR(x,y)
0	0	0
0	1	1
1	0	1
1	1	0

Pour réaliser une telle fonction, il suffit de se trouver une combinaison de fonctions AND, OR et NOT qui produit la même table de vérité. Une façon mécanique de produire cette fonction est de remarquer que la sortie d’une fonction AND ne vaut 1 que lorsque ses deux entrées sont à 1. Examinons la deuxième ligne de la table de vérité de la fonction XOR. Celle-ci indique que cette fonction doit valoir 1 lorsque x vaut 0 et y vaut 1. Avec des fonctions AND et des inverseurs, on peut obtenir les tables de vérité suivantes:

x	y	AND(x,y)
0	0	0
0	1	0
1	0	0
1	1	1

x	y	AND(NOT(x),y)
0	0	0
0	1	1
1	0	0
1	1	0

x	y	AND(x,NOT(y))
0	0	0
0	1	0
1	0	1
1	1	0

x	y	AND(NOT(x),NOT(y))
0	0	1
0	1	0
1	0	0
1	1	0

Deux de ces fonctions AND peuvent être combinées avec une fonction OR. Un premier exemple est de combiner les deux premières fonctions, AND(x,y) et AND(NOT(x),y) pour construire la fonction OR(AND(x,y),AND(NOT(x),y). Sa table de vérité est la suivante.

x	y	OR(AND(x,y),AND(NOT(x),y)
0	0	0
0	1	1
1	0	0
1	1	1

On remarque aisément que la fonction combinée vaut 1 uniquement lorsque x vaut 1 et y vaut 1 ou lorsque x vaut 0 et y vaut 1.

En revenant à notre fonction XOR, on se rend aisément compte qu’elle doit valoir 1 dans uniquement deux cas :

• x vaut 1 et y vaut 0

• x vaut 0 et y vaut 1

Dans tous les autres cas, la fonction XOR doit retourner 0. Le premier cas peut s’implémenter en utilisant la fonction AND(x,NOT(y)) tandis que le second correspond à la fonction AND(NOT(x),y). Ces deux fonctions peuvent se combiner comme suit: OR(AND(x,NOT(y)), AND(NOT(x),y)). En construisant la table de vérité, on se convainc facilement que \(OR(AND(x,NOT(y)), AND(NOT(x),y)) \iff XOR(x,y)\).

En pratique, il est possible de construire n’importe quelle fonction booléenne en combinant avec la fonction OR, autant de fonctions AND qu’il y a de lignes de la table de vérité dont la sortie vaut 1.

A titre d’exemple, considérons la fonction F dont la table de vérité est reprise ci-dessous.

x	y	F(x,y)
0	0	1
0	1	1
1	0	1
1	1	0

Cette fonction peut s’implémenter comme étant la combinaison des trois fonctions AND suivantes:

• AND(NOT(x),NOT(y))

• AND(NOT(x),y)

• AND(x,NOT(y))

Et donc, \(OR(AND(NOT(x),NOT(y)), AND(NOT(x),y), AND(x,NOT(y)) \iff F(x,y)\). Cependant, cette implémentation n’est pas la plus efficace du point de vue du nombre de fonctions AND. Il y a d’autres réalisations possibles. Une première implémentation équivalente est de remarquer que lorsque x vaut 0, la fonction F(x,y) vaut toujours 1. On peut donc simplifier cette fonction comme étant OR(NOT(x), AND(x,NOT(y)). On peut aisément se rendre compte que cette fonction booléenne a la même table de vérité que la fonction F(x,y). Mathématiquement, on peut noter que \(OR(AND(NOT(x),NOT(y)), AND(NOT(x),y)) \iff NOT(x)\).

Cette implémentation de la fonction F(x,y) n’est pas la plus compacte. On remarque aisément que cette fonction vaut 0 uniquement lorsque ses deux entrées valent 1. Dans tous les autres cas, elle vaut 1. Cela nous rappelle la fonction NAND ou \(NOT(AND(x,y)) \iff F(x,y)\).

Dans le cadre de ce cours, nous nous focaliserons sur la synthèse de fonctions booléennes qui sont correctes, c’est-à-dire qui produisent une table de vérité donnée, mais qui n’utilisent pas nécessairement un nombre minimal de fonctions de base. Différentes techniques existent pour minimiser de telles fonctions booléennes, mais elles correspondent plus à un cours d’électronique digitale qu’à un cours d’introduction au fonctionnement des ordinateurs.

Représentations graphiques

Lorsque l’on travaille avec des fonctions booléennes, on peut soit utiliser les symboles comme AND, OR, NOT, soit utiliser des symboles graphiques. Ceux-ci sont très utilisés pour construire de petits circuits. La Fig. 49 représente l’inverseur ou la fonction NOT. La fonction OR est présentée schématiquement dans la Fig. 50 et la fonction AND dans la Fig. 51.

Fig. 49 Représentation graphique d’une fonction NOT

Fig. 50 Représentation graphique d’une fonction OR

Fig. 51 Représentation graphique d’une fonction AND

La fonction XOR a aussi sa représentation graphique. Celle-ci est présentée dans la Fig. 52.

Fig. 52 Représentation graphique d’une fonction XOR

Dans de nombreux circuits, on retrouve des inverseurs. Ainsi, la fonction NAND est finalement une fonction AND suivie d’un inverseur comme représenté sur la Fig. 53. Cette inversion est symbolisée par un petit rond. Il en va de même pour la fonction NOR (Fig. 54).

Fig. 53 Représentation graphique d’une fonction NAND

Fig. 54 Représentation graphique d’une fonction NOR

Les multiplexeurs et démultiplexeurs ont aussi leur représentation graphique. Le livre les représente en utilisant un triangle comme dans la Fig. 55.

Fig. 55 Un multiplexeur à deux entrées

De la même façon, on peut également représenter le démultiplexeur de façon graphique comme représenté dans la Fig. 56.

Fig. 56 Un démultiplexeur à deux sorties

Il est évidemment possible de combiner plusieurs fonctions booléennes pour supporter des fonctions plus avancées. A titre d’exemple, considérons la fonction d’égalité qui vaut 1 lorsque ses deux entrées sont égales et 0 sinon. Voici sa table de vérité.

x	y	EQ(x,y)
0	0	1
0	1	0
1	0	0
1	1	1

Cette fonction peut être réalisée en utilisant deux fonctions AND, une fonction OR et des inverseurs (Fig. 57).

Fig. 57 Représentation graphique d’un circuit qui réalise la fonction EQ

Un autre exemple est la fonction XOR dont nous avons déjà parlé précédemment. Celle-ci peut s’implémenter en utilisant deux inverseurs, deux fonctions AND et une fonction OR comme représenté dans la Fig. 58.

Fig. 58 Représentation graphique d’un circuit qui réalise la fonction XOR

Avec un multiplexeur, il est possible de construire un circuit « programmable » qui, en fonction de la valeur de son entrée sel, calcule soit la fonction AND, soit la fonction OR. Ce circuit est représenté dans la Fig. 59.

Fig. 59 Un circuit programmable

Un langage de description de circuits logiques

Les représentations graphiques sont très utiles pour permettre à des électroniciens de discuter de circuits électroniques, mais de nos jours ils travaillent généralement en utilisant des langages informatiques qui permettent de décrire ces circuits électroniques sous la forme de commandes. L’avantage de ces langages est qu’ils peuvent facilement être utilisés dans des logiciels de simulation ou d’analyse de circuits. C’est ce que nous ferons dans le cadre de ce cours avec le langage HDL proposé par les auteurs du livre Building a Modern Computer from First Principles.

Il existe de nombreux langages qui permettent de décrire de façon précise des fonctions booléennes et des circuits électroniques de façon générale 1 . Une description détaillée de ces langages sort du cadre de ce cours. Nous nous contenterons de voir celui qui est utilisé par les simulateurs du livre de référence.

Quatre types de fichiers sont utilisés par le simulateur :

• les fichiers de description de circuits (nom de fichier se terminant par .hdl)

• les fichiers qui définissent les tests à réaliser sur les circuits (nom de fichier se terminant par .tst)

• les fichiers contenant les sorties d’un circuit obtenues lors de l’exécution d’un fichier de test (nom de fichier se terminant par .out)

• les fichiers contenant les sorties attendues d’un circuit (nom de fichier se terminant par .cmp)

Le langage de description de circuits permet de construire des fonctions booléennes en réutilisant les fonctions de base. Ce langage s’utilise un peu comme un langage de programmation. Dans le langage HDL, un circuit est défini sous la forme d’une liste de commandes, avec généralement une commande par ligne.

Comme dans tout langage de programmation, HDL permet d’inclure des commentaires. HDL utilise une convention similaire à des langages de programmation tels que C ou Java. En HDL, il y a deux façons de définir un commentaire. La première est d’utiliser les caractères //. Tous les caractères qui suivent // sur une ligne sont un commentaire qui ne sera pas lu par le simulateur. Il est aussi possible d’écrire de longs commentaires qui couvrent plusieurs lignes. Dans ce cas, le commentaire débute par les caractères /* et couvre tout le texte jusqu’à */. Le texte ci-dessous présente ces deux types de commentaires.

// Un commentaire sur une seule ligne

 /*
  * un commentaire sur plusieurs lignes
  */

Le langage HDL comprend différents mots-clés que l’on retrouve dans toute description de circuits. Le premier est le mot clé CHIP qui permet donner un nom au circuit électronique que l’on décrit dans le fichier. Il est préférable d’utiliser comme nom du circuit le même nom que celui du fichier. Le livre recommande d’utiliser un nom commençant par une majuscule pour les circuits que l’on crée. La définition d’un circuit commence après l’accolade ouvrante ({) et se termine à l’accolade fermante (}).

/*
 * Commentaire expliquant ce que fait le circuit
 */
CHIP Nom {
  // définition complète du circuit
}

A l’intérieur de la définition d’un circuit, on peut utiliser différents mots-clés:

• IN permet de lister un ensemble d’entrées

• OUT permet de lister un ensemble de sorties

Ces deux mots-clés sont utilisés au début de la description d’un circuit. Chaque entrée et chaque sortie doit avoir un nom différent. Par convention, on utilisera un nom écrit en minuscules et commençant par une lettre pour les entrées et les sorties. Les noms des entrées/sorties doivent être séparés par des virgules et la liste des entrées/sorties doit se terminer par un point-virgule (;).

IN a,b,c;  // Trois entrées appelés a, b et c
OUT out1, out2; // Deux entrées baptisées out1 et out2

Après avoir spécifié les entrées/sorties, il faut indiquer les différentes fonctions qui sont utilisées par le circuit. Le mot-clé PARTS: marque le début de la définition des fonctions logiques. L’exemple ci-dessous présente un squelette de circuit en HDL.

// Un commentaire
CHIP Nom {   // Le nom du circuit doit être le même que le nom du fichier
   IN ...  // les entrées du circuit
   OUT ... // les sorties du circuit

   PARTS:   // les composantes du circuit
     // description des différentes parties du circuit
} // marque la fin de la définition du circuit Nom

HDL peut être utilisé pour construire de nombreuses fonctions booléennes en s’appuyant sur les fonctions existantes. Le simulateur supporte différentes fonctions de base dont :

• la fonction Nand qui est la fonction primitive pour de très nombreux circuits électroniques

• la fonction And

• la fonction Or

• la fonction Not ou l’inverseur

En utilisant l’inverseur, il est possible de construire un circuit électronique qui ne fait rien du tout avec deux inverseurs. Ce circuit prend une entrée nommée a et la connecte à un inverseur. La sortie de cet inverseur a comme nom nota. Elle est connecté à l’entrée du second inverseur.

// un circuit qui ne fait rien
CHIP Rien {
    IN a;     // Le circuit a une entrée que l'on nomme a dans ce fichier
    OUT out;  // Le circuit a une sortie que l'on nomme out dans ce fichier
    //
    PARTS:
    Not(in=a, out=nota);   // premier inverseur connecté à l'entrée a, sa sortie est appelée nota
    Not(in=nota, out=out); // second inverseur connecté à la sortie du premier, sa sortie est reliée à out
}

Graphiquement, ce circuit peut être représenté comme dans la Fig. 60.

Fig. 60 Représentation graphique du circuit qui ne fait rien

Un autre exemple est de construire un circuit qui implémente la fonction AND avec trois entrées en utilisant des fonctions AND à deux entrées.

/*
 * Une circuit AND à trois entrées
 */
CHIP And3 {
    IN a,b,c;   // Les trois entrées
    OUT out;    // La sortie du circuit
    //
    PARTS:
    And(a=a, b=b, out=and1);   // première fonction AND
    And(a=and1, b=c, out=out); // seconde fonction AND
}

Un exemple plus complexe est de construire une implémentation de la fonction XOR sur base des fonctions AND, OR et NOT.

/*
 * Une circuit XOR à deux entrées
 */
CHIP Xor {
    IN a,b;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=a, b=notb, out=w1);
    And(a=nota, b=b, out=w2);
    Or(a=w1, b=w2, out=out);
}

Les fichiers HDL contiennent la description du circuit électronique. Ils seront utilisés pour les différents projets de ce cours. Outre le langage HDL, le simulateur proposé dans le livre de référence supporte également un langage qui permet de définir les tests que chaque circuit doit supporter. Ces tests sont très importants car ils définissent de façon précise les sorties attendues de chaque circuit. Prenons comme exemple les tests pour la fonction NOT. Ceux-ci sont définis dans le fichier Not.tst du premier projet. La fonction Not a une entrée baptisée in et une sortie baptisée out.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Not.tst

load Not.hdl,                    // charge la description de l'inverseur
output-file Not.out,             // les valeurs de la sortie out sont sauvées dans le fichier Not.out
compare-to Not.cmp,              // les valeurs de la sortie out seront comparées au contenu du fichier Not.cmp
output-list in%B3.1.3 out%B3.1.3; // format des données dans le fichier de sortie

set in 0,      // pour ce test, on fixe la valeur de in à 0
eval,          // on exécute le simulateur
output;        // on sauvegarde le résultat

set in 1,      // pour ce test, on fixe la valeur de in à 0
eval,          // on exécute le simulateur
output;        // on sauvegarde le résultat

Ce test charge le fichier contenant la description du circuit (Not.hdl). Il définit ensuite le fichier de sortie comme étant Not.out. Le fichier référence auquel le résultat de la simulation devra être comparé est le fichier Not.cmp. La commande output-list indique qu’il faut créer une colonne avec la valeur de l’entrée in suivie d’une colonne avec la valeur de la sortie out dans le fichier Not.out.

Dans la deuxième partie de la suite de test, la commande set permet de fixer les valeurs des différentes entrées. Comme le circuit n’a qu’une entrée, il suffit de deux commandes set pour couvrir toutes les possibilités.

Le fichier Not.cmp reprend les résultats attendus lors de l’exécution du circuit qui implémente l’inverseur. Dans ce cas, il s’agit de la table de vérité complète de l’inverseur. Pour des circuits plus simples, ce fichier ne contiendra que les valeurs attendues pour les tests réalisés.

|  in   |  out  |
|   0   |   1   |
|   1   |   0   |

Vous trouverez de nombreux autres exemples de fichiers de test dans l’archive relative au premier projet : https://www.nand2tetris.org/project01 ainsi qu’une présentation détaillée du langage HDL sur le site du livre.

1

Voir par exemple https://en.wikipedia.org/wiki/Hardware_description_language

Les fonctions « multi-bits »

Maintenant que nous avons vu les fonctions logiques de base, nous pouvons nous préparer à construire les circuits qui seront les briques de base d’un microprocesseur. Avant cela, il nous reste deux concepts importants à discuter.

Durant la première semaine, nous avons vu comment une fonction booléenne pouvait traiter des entrées valant 0 ou 1. Souvent, les circuits électroniques sont amenés à traiter plusieurs données simultanément. Le livre appelle ces circuits les circuits « multi-bits ».

L’autre point que nous devons aborder sont les fonctions primitives. Durant la première semaine, nous avons travaillé avec AND, OR et NOT. Ces fonctions sont faciles à comprendre et utiliser. Pour des raisons technologiques, les circuits électroniques n’utilisent pas ces fonctions comme des fonctions primitives mais plutôt les fonctions NAND ou NOR dans certains cas. Nous verrons que la fonction NAND est une fonction primitive qui permet d’implémenter n’importe quelle fonction booléenne.

Les fonctions multi-bits sont simplement des fonctions qui sont appliquées de la même façon à plusieurs entrées. Le circuit de la Fig. 61 applique la fonction NOT à quatre entrées baptisées x[0], x[1], x[2] et x[3]. Les sorties sont out[0], out[1], out[2] et out[3].

Fig. 61 Représentation graphique d’un circuit NOT 4-bits

Il est aussi possible de construire des versions multi-bits des fonctions AND et OR. Ces deux circuits sont représentés dans les figures Fig. 62 et Fig. 63.

Fig. 62 Représentation graphique d’un circuit AND 2-bits

Fig. 63 Représentation graphique d’un circuit OR 2-bits

De la même façon, on peut construire des multiplexeurs et des démultiplexeurs à k-bits.

La fonction universelle NAND

La fonction NAND joue un rôle particulier dans de nombreux circuits électroniques car elle sert d’élément de base à la réalisation d’autres fonctions. Un point particulier est que la fonction NAND permet de facilement obtenir un inverseur. Ainsi, \(NAND(x,x) \iff NOT(x)\).

x	NAND(x,x)
0	1
1	0

Sur base de cette fonction NAND, on peut aussi facilement construire la fonction AND puisque \(AND(x,y) \iff NAND( NAND(x,y), NAND(x,y) )\). On peut s’en convaincre en construisant la table de vérité de cette fonction

x	y	NAND(x,y)	NAND(x,y)	NAND( NAND(x,y), NAND(x,y) )
0	0	1	1	0
0	1	1	1	0
1	0	1	1	0
1	1	0	0	1

Compléments sur les fonctions booléennes

Dans les chapitres précédents, nous avons couvert les bases de la construction des fonctions booléennes en utilisant les fonctions AND, OR et NOT. Il existe de nombreuses fonctions de ce type. La plupart de ces fonctions manipulent des séquences de bits. Certaines de ces séquences de bits servent à représenter de l’information d’un type particulier.

Représentation binaire de l’information

Dans un ordinateur, toutes les informations peuvent être stockées sous la forme d’une séquence de bits. La longueur de la séquence est fonction de la quantité d’information à stocker. Notre premier exemple concerne les caractères. Il est important de pouvoir représenter les différents caractères des langues écrites de façon compacte et non-ambiguë pour pouvoir stocker et manipuler du texte sur un ordinateur. Le principe est très simple. Il suffit de construire une table qui met en correspondance une séquence de bits et le caractère qu’elle représente.

Parmi les tables d’encodage des caractères les plus simples, la plus connue est certainement la table US-ASCII dont la définition est notamment reprise dans RFC 20. Cette table associe une séquence de 7 bits (b7 à b1) à un caractère particulier. Pour des raisons historiques, certains de ces caractères sont des caractères dits « de contrôle » qui ne sont pas imprimables. Ils permettaient de contrôler le fonctionnement de terminaux ou d’imprimantes. Par exemple, les caractères CR et/ou LF correspondent au retour de charriot et au passage à la ligne sur un écran ou une imprimante.

Code source 2 Table des caractères ASCII

|----------------------------------------------------------------------|
  B  \ b7 ------------>| 0   | 0   | 0   | 0   | 1   | 1   | 1   | 1   |
   I  \  b6 ---------->| 0   | 0   | 1   | 1   | 0   | 0   | 1   | 1   |
    T  \   b5 -------->| 0   | 1   | 0   | 1   | 0   | 1   | 0   | 1   |
     S                 |-----------------------------------------------|
               COLUMN->| 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   |
|b4 |b3 |b2 |b1 | ROW  |     |     |     |     |     |     |     |     |
+----------------------+-----------------------------------------------+
| 0 | 0 | 0 | 0 | 0    | NUL | DLE | SP  | 0   | @   | P   |   ` |   p |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 0 | 0 | 1 | 1    | SOH | DC1 | !   | 1   | A   | Q   |   a |   q |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 0 | 1 | 0 | 2    | STX | DC2 | "   | 2   | B   | R   |   b |   r |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 0 | 1 | 1 | 3    | ETX | DC3 | #   | 3   | C   | S   |   c |   s |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 1 | 0 | 0 | 4    | EOT | DC4 | $   | 4   | D   | T   |  d  |   t |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 1 | 0 | 1 | 5    | ENQ | NAK | %   | 5   | E   | U   |  e  |   u |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 1 | 1 | 0 | 6    | ACK | SYN | &   | 6   | F   | V   |  f  |   v |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 0 | 1 | 1 | 1 | 7    | BEL | ETB | '   | 7   | G   | W   |  g  |   w |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 0 | 0 | 0 | 8    | BS  | CAN | (   | 8   | H   | X   |  h  |   x |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 0 | 0 | 1 | 9    | HT  | EM  | )   | 9   | I   | Y   |  i  |   y |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 0 | 1 | 0 | 10   | LF  | SUB | *   | :   | J   | Z   |  j  |   z |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 0 | 1 | 1 | 11   | VT  | ESC | +   |  ;  | K   | [   |  k  |   { |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 1 | 0 | 0 | 12   | FF  | FS  | ,   | <   | L   | \   |  l  |   | |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 1 | 0 | 1 | 13   | CR  | GS  | -   | =   | M   | ]   |  m  |   } |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 1 | 1 | 0 | 14   | SO  | RS  | .   | >   | N   | ^   |  n  |   ~ |
|---|---|---|---|------|-----|-----|-----|-----|-----|-----|-----|-----|
| 1 | 1 | 1 | 1 | 15   | SI  | US  | /   | ?   | O   | _   |  o  | DEL |
+----------------------+-----------------------------------------------+

La table US-ASCII (Code source 1) définit les représentations binaires suivantes:

• 01100000 correspond au caractère représentant le chiffre 0

• 01101001 correspond au caractère représentant le chiffre 9

• 10000011 correspond au caractère représentant la lettre A (majuscule)

• 01000000 correspond au caractère représentant un espace

Cette table avait l’inconvénient majeur de ne contenir que les représentations des caractères non-accentués de l’alphabet latin. Elle permet d’écrire du texte en anglais et dans d’autres langues européennes qui utilisent peu d’accents, mais ne permet évidemment pas de représenter tous les caractères des langues écrites sur notre planète. Au fil des années, ce problème a été résolu avec d’autres tables de correspondance dont celles qui sont adaptées aux accents utilisés par les langues européennes. Aujourd’hui, l’encodage standard des caractères se fait en utilisant le format Unicode. Une description détaillée d’Unicode sort du cadre de ce cours d’introduction, mais sachez qu’en mars 2020, la version 13.0 d’Unicode permettait de représenter 143859 caractères différents correspondant à 154 formes d’écritures. Unicode permet de représenter quasiment toutes les langues écrites connues sur notre planète. Des chercheurs ont même proposé un format Unicode permettant de supporter le Klingon, c’est-à-dire la langue écrite inventée pour la série de films Star Trek.

Avoir une représentation binaire pour les caractères permet de les stocker en mémoire, sur disque ou de les transmettre à travers un réseau. C’est important, mais il faut aussi pouvoir permettre à un humain de lire des textes produits par un ordinateur, que ce soit sur papier ou écran. Il existe de très nombreuses solutions qui permettent d’afficher ou d’imprimer des caractères. Dans ce cours d’introduction, nous nous contentons d’une solution très simple qui fonctionne en noir et blanc. Nous pourrons ajouter les couleurs lorsque nous aurons vu comment représenter des nombres dans le chapitre suivant.

Un écran et une imprimante permettent d’afficher des points à n’importe quelle position. On peut aisément se représenter un écran comme un rectangle composé de pixels. Chacun des points de cet écran est identifié par une abscisse et une ordonnée qui sont toutes les deux entières. Ainsi, un écran 1024x768 peut afficher 1024 points selon l’axe des x et 768 points selon l’axe des y.

Sur un tel écran, on peut facilement afficher des caractères. Il suffit d’avoir pour chaque caractère une table qui contient la représentation graphique de chacun des caractère à afficher sous la forme de pixels. A titre d’exemple, supposons que l’on veut afficher chaque caractère dans un carré de 8x8 pixels. Dans ce cas, on peut stocker la représentation graphique d’un caractère en noir en blanc sous la forme d’une suite de 8 bytes. Par exemple, les huit octets ci-dessous contiennent une représentation graphique du caractère 1.

00001000
00011000
00101000
00001000
00001000
00001000
00001000
00111110

Une représentation graphique, fortement agrandie, de ce caractère est présentée dans la Fig. 1.

Fig. 64 Un caractère sous la forme de pixels

Fonctions booléennes sur les séquences de bits

De nombreuses fonctions manipulent des séquences de bits. Nous verrons dans le prochain chapitre comment représenter des nombres sous la forme d’une séquence de bits et comment réaliser différentes opérations arithmétiques sur ces séquences de bits. Ces fonctions sont dites combinatoires car ce sont des fonctions dont le résultat dépend uniquement des valeurs d’entrée. Dans cette section, nous abordons d’abord les fonctions combinatoires qui permettent de déplacer des bits dans une séquence. Nous considérons trois types de fonctions:

• les fonctions de décalage (à droite ou à gauche)

• les fonctions de rotation (à droite ou à gauche)

• les fonctions de masquage permettant de forcer certains bits à la valeur 0 ou 1

Chacune de ces fonctions travaille sur une séquence de n bits, \(b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}\). Dans une telle séquence, nous avons vu que \(b_{n-1}\) était le bit de poids fort tandis que \(b_{0}\) est le bit de poids faible. Ces opérations sont généralement appliquées à des séquences de 8, 16, 32 ou 64 bits

Plusieurs fonctions de décalage sont possibles. La plus simple est la fonction de décalage d’un bit vers la droite. Cette fonction prend comme entrée la séquence de bits \(b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}\) et retourne comme résultat la séquence \(0b_{n-1}b_{n-2}...b_{2}b_{1}\). Tous les bits sont décalés d’une place vers la droite. Il existe une variante de cette fonction de décalage qui retourne \(b_{n-1}b_{n-1}b_{n-2}...b_{2}b_{1}\) pour la séquence d’entrée \(b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}\). Elle est parfois utilisée pour certaines manipulations des nombres entiers.

De la même façon, la fonction de décalage d’une place vers la gauche prend comme entrée la séquence de bits \(b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}\) et retourne comme résultat \(b_{n-2}...b_{2}b_{1}b_{0}0\).

Ces deux fonctions peuvent se généraliser. Plutôt que de décaler la séquence de bits d’une place vers la gauche ou vers la droite, on peut la décaler de p places où p est aussi une entrée de la fonction. Ainsi, lorsque l’on décale de deux places vers la droite la séquence \(b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}\), on obtient la séquence \(00b_{n-1}b_{n-2}...b_{2}\). Il en va de même pour le décalage vers la gauche.

Dans certaines applications, il est utile de pouvoir forcer la valeur d’un bit particulier à 0 ou 1. Pour illustrer ces interactions, considérons deux exemples sur base de la représentation des caractères et l’utilisation de pixels. Dans la table US-ASCII, les lettres majuscules sont représentées par des chaînes de bits dont les deux bits de poids forts sont à 10 tandis que pour les minuscules, ces deux bits de poids forts sont à 11. Si on observe les séquences de bits pour chaque caractère, on remarque que les 4 bits de poids faible sont identiques pour la majuscule et la minuscule d’une lettre. Ainsi, pour la lettre E, on utilise les séquence 1000101 en majuscules et 1100101 en minuscules. Si une séquence de 7 bits représente une lettre majuscules, alors on peut facilement la convertir en minuscules en forçant le deuxième bit de poids fort à la valeur 1. Sachant que la fonction booléenne OR retourne toujours 1 lorsqu’au moins une de ses deux entrées vaut 1, on peut transformer une majuscule en minuscule en calculant OR avec la séquence 0100000. Si la représentation du caractère initiale est \(b_{6}b_{5}b_{4}b_{3}b_{2}b_{1}b_{0}\), alors la fonction OR 0100000 retournera \(b_{6}1b_{4}b_{3}b_{2}b_{1}b_{0}\). De la même façon, on peut forcer un bit à zéro en utilisant la fonction AND. Par exemple, pour transformer une minuscule en majuscule en utilisant le masque 1011111.

Lorsqu’un ordinateur doit transmettre ou stocker de l’information encodée sous la forme d’une séquence de bits, il doit parfois pouvoir s’assurer que l’information qui est reçue ou lue est bien identique à celle qui a été envoyée ou écrite.

Un exemple classique de l’utilisation de ces techniques concerne les sondes spatiales qui sont envoyées pour explorer les planètes du système solaire voire explorer au-delà de notre système solaire. Ces sondes collectent de nombreuses informations qu’elles doivent envoyer par radio vers la Terre. Différentes techniques, qui sortent du cadre de ce cours, permettent d’envoyer des séquences de bits par radio. Malheureusement, les transmissions radio peuvent être perturbées par différents phénomènes naturels dont les émissions du soleil par exemple. Suite à ces perturbations, une séquence de bits envoyée par une sonde spatiale peut être reçue de façon incorrecte par la station d’écoute se trouvant au sol. Vu les capacités de la sonde spatiale et les délais de transmission entre les confins du système solaire et la Terre, il est impossible de demander à la sonde spatiale de stocker de l’information pour pouvoir la retransmettre au cas où elle ne serait pas reçue correctement par la station d’écoute sur la Terre. A titre d’exemple, la distance entre Mercure et la Terre varie entre 77 millions de kilomètres et 222 millions de kilomètres. La lumière, qui est la façon la plus rapide de transmettre de l’information, se propage à une vitesse de 300.000 kilomètres par seconde. Cela signifie que lorsque Mercure est proche de la Terre, un signal émis par une sonde autour de Mercure met au moins 256 secondes pour atteindre la Terre. Pour les sondes Voyager 1 et Voyager 2 qui explorent les confins du système solaire, les délais sont encore plus grands. En octobre 2020, un signal radio émis par Voyager 1 mettait près de 21 heures pour atteindre la Terre.

Plusieurs techniques ont étés proposées pour faire face à des erreurs dans la transmission de séquences de bits. Certaines permettent de détecter des erreurs dans l’information reçue. D’autres, plus complexes, permettent de récupérer certaines erreurs de transmission.

Les techniques de détection les plus simples sont les techniques dite de parité. L’idée est très simple. Pour pouvoir détecter si une erreur de transmission a affecté une séquence de bits, il suffit d’encoder ces séquences de bits de façon à pouvoir facilement distinguer une séquence valide d’une séquence invalide. Les techniques de parité séparent les séquences de bits en deux moitiés. La première contient les séquences valides qui sont émises par l’émetteur. La seconde contient des séquences qui peuvent être obtenues des première après une erreur de transmission.

La technique de parité paire fonctionne comme suit. Une séquence de n+1 bits, \(b_{n-1}b_{n-2}...b_{2}b_{1}b_{0}p\) est valide si elle contient un nombre pair de bits ayant la valeur 1 et invalide sinon. Lorsqu’un émetteur veut envoyer n bits, il doit calculer la valeur du bit de poids faible de façon à ce que la séquence des n+1 bits contienne un nombre pair de bits à la valeur 1.

Il est utile de prendre quelques exemples pour bien comprendre comment cette technique fonctionne. Considérons les caractères représentés sur 7 bits. Une parité peut être associé à chacun de ces caractères.

• la parité paire de 01100000 sera 0

• la parité paire de 01101001 sera 0

• la parité paire de 10000011 sera 1

Considérons une sonde spatiale qui envoie la séquence de bits composée de ces trois caractères avec leur parité paire, c’est-à-dire : 011000000 011010010 100000111. La station d’écoute pourra recalculer le bit de parité qui est placé dans le bit de poids faible de chaque octet pour vérifier qu’il n’y a pas eu d’erreur de transmission. Si par contre la station d’écoute reçoit 011000001 111010010 100000111, elle pourra vérifier que les deux premiers octets sont incorrects tandis que le troisième est correct. Cette technique de parité permet de détecter les erreurs de transmission qui modifient la valeur de un (et un seul bit) dans la séquence de bits couverte par la parité. En pratique, l’émetteur envoie les bits et calcule la valeur du bit de parité pendant l’envoi de ces bits. Le receveur fait l’inverse pour vérifier que la parité de la séquence reçue est correcte.