Shannon et le calcul par relais

dimanche 14 août 2022
par Alain BUSSER , Ariel FRECKHAUS , David THÉRINCOURT

L’atelier portait sur les circuits électroniques présentés par Claude Shannon dans sa thèse, publiée en 1938, et que voici :

partie 1	partie 2	partie 3	partie 4

Des lycéens découvraient le calcul binaire en montant et manipulant ces circuits.

Cet article est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 2.0 France.

Programmes

SNT

mise en activité des élèves, sous des formes variées (exposés, travaux en groupe, mini-projets, productions individuelles ou collectives, etc.)
...
coopérer au sein d’une équipe

(Capacités attendues en SNT)

(Internet) Caractériser les principes du routage et ses limites
(Internet) Caractériser quelques types de réseaux physiques (obsolètes ou non)
(le Web) Étudier et modifier une page html simple.
(Données) Identifier les principaux formats et représentations de données
(Données) Identifier les principales causes de la consommation énergétique des centres de données
(Objets connectés) Réaliser une IHM simple d’un objet connecté

NSI 1^re

Démarche de projet

Une part de l’horaire d’enseignement d’au moins un quart du total en classe de première doit être réservé à la conception et l’élaboration de projets conduits par des groupes de deux à quatre élèves.

(Capacités attendues en 1^re NSI)

Histoire de l’informatique

Situer dans le temps les principaux événements de l’histoire de l’informatique et leurs protagonistes.

Programme de NSI (1^re) :

Écriture d’un entier positif dans une base b ≥ 2
Représentation binaire d’un entier relatif
Valeurs booléennes :
- 0
- 1
Opérateurs booléens :
- and,
- or,
- not.

Commentaires

Le ou exclusif (xor) est évoqué.

Binaire	Capacités attendues	Commentaires
Expressions booléennes	Dresser la table d’une expression booléenne.	Quelques applications directes comme l’addition binaire sont présentées.

Architectures matérielles

Les circuits électroniques sont au cœur de toutes les machines informatiques.

Modèle d’architecture séquentielle (Von Neumann)

Des activités débranchées sont proposées.

Les circuits combinatoires réalisent des fonctions booléennes.

Périphériques d’entrée et de sortie

Identifier le rôle des capteurs et actionneurs.

BTS SIO

Comparaison entre le calcul binaire et le calcul booléen

Les booléens seront alors 1 et 0, interprétés comme signifiant « il y en a, ou pas ».

Calcul propositionnel

On dégagera les propriétés fondamentales des opérations ainsi introduites, de manière à déboucher ensuite sur un exemple d’algèbre de Boole.

Shannon

Claude Shannon a déjà été évoqué sur ce site, à propos d’un jeu qu’il a inventé et appelé switching game :

Ainsi que de sa machine qui joue à Hex.

Il est surtout célèbre pour sa théorie de la communication, dans laquelle la transmission d’une information est modélisée selon le schema suivant :

émetteur → canal → récepteur

et la qualité du transfert d’information dépend de manière cruciale de celle

de l’émetteur (le prof : faire des phrases courtes et claires, parler fort, créer de la redondance dans le discours...)
du canal (visuel, auditif, tactile ou kinesthésique ; le distanciel fonctionne mal, le bruit de fond gène la compréhension)
du récepteur (les élèves ; peu réceptifs s’ils ont un écran devant eux, plus réceptifs s’ils sont calmes).

C’est de la théorie de la communication par Shannon, que vient la célèbre définition de l’entropie de l’information (co-inventée par Turing pendant la guerre, et utile comme indicateur de biodiversité) et la notion de code correcteur d’erreur, décrite ici :

Turing

Pendant que Shannon travaillait sur sa thèse, Alan Turing effectuait un séjour à Princeton pour lui aussi travailler sur une thèse, sous la direction d’Alonzo Church. Durant ce séjour (écourté à cause de la menace de guerre : Turing voulait déjà participer à l’effort de guerre via la cryptographie), Turing a confié à des physiciens de Princeton un procédé cryptographique dont il était l’auteur :

from base64 import *

def codage(texte,clé):
    longadd = clé.bit_length()
    texte += '='*(-len(texte)%4)
    clair = b64decode(texte,'-_')
    entierclair = int.from_bytes(clair,byteorder='big')
    entiercodé = entierclair*clé
    codé = entiercodé.to_bytes(len(texte)+longadd,byteorder='big')
    s = b64encode(codé)
    return s
    
def décodage(texte,clé):
    longadd = clé.bit_length()
    codé = b64decode(texte,'-_')
    entiercodé = int.from_bytes(codé,byteorder='big')
    entierclair = entiercodé//clé
    clair = entierclair.to_bytes(len(texte)-longadd,byteorder='big')
    t = b64encode(clair)
    return t

Le principe est le suivant : pour coder un message, on le traduit en binaire (par exemple à l’aide du code Baudot que Turing connaissait). Puis on multiple par une clé (un entier secret et taille suffisamment importante pour que « 100 allemands travaillant 8 heures par jour pendant 100 ans ne puissent le trouver » selon Turing) pour coder le message et on envoie le produit. Le décodage ne nécessite alors qu’une division. En guise de preuve de concept, Turing avait besoin d’une machine à effectuer des multiplications (pour le codage) en binaire (ligne 8 du script Python ci-dessus). Celle-ci n’existant pas à l’époque (Shannon n’étant allé que jusqu’à l’addition, et rien ne prouve qu’à cette époque Turing ait connu la thèse de Shannon), Turing a alors entrepris de la fabriquer. Il a obtenu la clé de l’atelier de physique et y a construit et câblé des relais. D’après ses amis physiciens, la machine fonctionnait (mais on ne sait pas avec quelle précision).

Dès la fin de l’année universitaire 1937-1938, Turing est rentré en Angleterre pour rejoindre Bletchley Park, avec son multiplicateur binaire dans ses bagages. Cette machine ne semble pas avoir servi durant la guerre.

En 1943, une rencontre entre cryptographes alliés a été organisée à New York, et Turing faisait partie de la délégation britannique. À cette occasion il a rencontré Shannon mais apparemment leur conversation a surtout porté sur le cryptage de la voix.

Winston Churchill ayant demandé que « pas un morceau ne soit plus grand que l’ongle du pouce », tout ce qui était à Bletchley Park a été détruit, y compris le multiplicateur binaire de Turing. Celui que Konrad Zuse a fabriqué durant la guerre a d’ailleurs subi le même sort, dans les bombardements de Berlin.

À la fin de la guerre, le rapport de Von Neumann sur l’EDVAC décrit un multiplicateur binaire basé sur l’additionneur de Shannon : L’algorithme des égyptiens ramène la multiplication binaire à des additions et des multiplications par 2, lesquelles reviennent à des décalages. Von Neumann recommande l’usage de tubes électroniques en lieu et place de relais.

Transistors

Après les relais et les tubes électroniques, vint le transistor à effet de champ. Celui-ci diffère du relais sur les points suivants :

le fait que le courant passe ou non, ne dépend pas du courant d’entrée, mais de la tension d’entrée,
il n’y a pas de partie mécanique mais seulement l’accumulation de charges électriques dans un semiconducteur : le transistor est à la fois plus rapide et plus silencieux que le relais,
le transistor est nettement plus petit, et même de plusieurs ordres de grandeur, que le relais et le tube électronique,
le transistor à effet de champ est fragile, une faible charge électrostatique ou une température trop élevée suffit à le détruire.

Voici un cours d’ISN qui montre le principe sous forme d’animations :

Le logiciel Logisim permet de reproduire et simuler les circuits de la thèse de Shannon avec des transistors à effet de champ. Ici on a décidé (comme avec les vrais relais) de travailler en logique positive plutôt qu’en logique négative (choix de Shannon) soit

branchement en série pour la conjonction
branchement en parallèle pour la disjonction.

Les images ci-dessous sont cliquables et permettent de télécharger des fichiers .circ pour Logisim :

La figure 1 de Shannon :

La figure 2 de Shannon (disjonction chez lui, conjonction ici) :

La figure 3 de Shannon (conjonction chez lui, disjonction ici) :

La figure 5 de Shannon (un circuit à simplifier) :

La figure 6 de Shannon (version simplifiée de la figure 5) :

La figure 36 de Shannon (additionneur binaire selon lui) :

Un autre additionneur binaire, mettant à profit les macros de Logisim :

En reliant entre eux de tels additionneurs à un chiffre (avec retenue) on peut câbler un additionneur d’octets...

Matériel

Le circuit suivant a été fabriqué, en 6 exemplaires (3 relais inverseurs, 3 relais non inverseurs) :

Les dimensions permettent de relier les relais à d’autres composants, plus standards, pour étudier les montages :

Activité

L’activité la plus simple consiste à faire manipuler un seul relais (inverseur) dont le courant d’entrée dépend d’un interrupteur marqué 0-1, de ce genre :

et dont la sortie alimente une lampe à filament capable de supporter la tension plus élevée que requiert le relais dans son fonctionnement.

On constate alors que la lampe s’allume uniquement lorsque le courant d’entrée ne circule pas dans le relais : on a réalisé une porte non, dont voici la table de vérité :

courant d’entrée	allumage de la lampe
0	1
1	0

Conjonction

Pour la porte et, il faut deux interrupteurs (puisqu’il y a deux opérandes) :

(à gauche, les câbles alimentant les deux relais montés en série)

En faisant la table de vérité, on constate que la lampe ne s’allume que lorsque les deux interrupteurs sont sur « 1 » :

Ce qui donne cette table de vérité :

entrée 1	entrée 2	sortie
0	0	0
0	1	0
1	0	0
1	1	1

Ce résultat est logique, puisque comme les deux relais sont en série, le courant ne passe au travers du montage que s’il peut traverser le premier relais et le second relais.

Disjonction

Pour la disjonction, on monte les relais en parallèle, ce qui fait que le courant passe dès qu’il peut traverser le premier relais ou le second relais. Ce qui donne cette table de vérité :

entrée 1	entrée 2	sortie
0	0	0
0	1	1
1	0	1
1	1	1

Ou exclusif

Ce montage est plus complexe que les précédents :

Il est formé de deux parties, reliées en parallèle :

un relais normal commandé par la première entrée, en série avec un relais inverseur commandé par la seconde entrée,
un relais inverseur commandé par la première entrée, en série avec un relais normal commandé par la seconde entrée.

La figure 4

En effet, l’algorithme de Quine-McCluskey, que Shannon avait dessiné dans sa figure 4, dit que

si a=0 alors a xor b = b (0 si b=0, 1 sinon)
si a=1 alors a xor b = non b (1 si b=0, 0 sinon)

soit, algébriquement, a xor b = (a et non b) ou (non a et b).

L’objet de la thèse de Shannon est de prouver qu’avec cette méthode, on peut réaliser avec des relais toute fonction binaire calculable, quoique pas forcément de façon optimale (en nombre de relais, consommation de courant, fatigue des ressorts...)

On constate que la lampe ne s’allume que si les deux interrupteurs donnent des valeurs différentes :

La configuration ci-dessus a par exemple pour effet d’allumer la lampe :

En résumé, la table de vérité de cette opération est

entrée 1	entrée 2	sortie
0	0	0
0	1	1
1	0	1
1	1	0

Addition

On constate en regardant les montages précédents que

le chiffre des unités pour l’addition 1 bit est donné par xor (ou exclusif)
le chiffre des deuzaines (ou la retenue) est donné par une porte et.

Il est possible de réaliser un additionneur binaire avec 5 relais (dont deux inverseurs) :

On aperçoit à gauche la lampe des deuzaines et en bas à droite, celle des unités. La table de vérité correspond bien à une addition binaire :

0+0 = 00

0+1 = 01

1+0 = 01

1+1 = 10

On a donc, avec les circuits précédents, la base d’un additionneur :

on utilise un xor entre les deux entrées
on fait encore un xor mais entre la somme et le retenue d’entrée : en sortie on a le bit de la somme
on réalise une opération de majorité entre les 3 entrées (les deux bits d’entrée et la retenue entrée) pour avoir la retenue engendrée : il y a une retenue uniquement si parmi les 3 entrées, au moins deux d’entre elles étaient à 1.

Pour chercher une porte majorité parmi 3, on peut utiliser encore une fois la figure 4 de Shannon :

Si a=0, la majorité entre a, b et c est b et c (1 seulement si b=1 et c=1)
Si a=1, la majorité entre a, b et c est b ou c.

La construction a été donnée sous la forme d’un devoir maison à faire avec le logiciel Logisim. Voici des copies d’élèves de 1^re NSI (les images sont cliquables et permettent de télécharger leurs circuits) :

Pour le corrigé, on programme de façon modulaire, en commençant par remarquer qu’il est possible de relier trois relais en parallèle ou de faire ainsi :

On dispose alors d’une porte ou à trois entrées, dont la sortie est 1 dès qu’au moins une des trois entrées est 1. On peut s’en servir pour faire un additionneur 1 bit avec retenue :

Quartets

Dès la rentrée 2023, un élève de 1^re NSI a créé un circuit à 6 portes (à deux entrées chacune) réalisant l’addition binaire de trois nombres à un chiffre (dont l’un est la retenue) :

Le circuit obtenu alors est un additionneur, mais sur 1 bit :

Maintenant il suffit d’en relier 4 en cascade pour avoir un additionneur 4 bits :

Produire cet additionneur d’octets a été donné en devoir sur Moodle. Tout le monde n’a pas réussi. Par exemple il y a eu des tentatives de brancher plusieurs entrées binaires sur un même point du circuit, ce que Logisim affiche en rouge (et le circuit ne fonctionne pas). Mais le principal problème a été le placement des 8 bits d’entrée et des 5 bits de sortie de manière qu’on reconnaisse les nombres :