URL originale : https://books.openedition.org/ugaeditions/42653
Chapitre 5
Les retombées mathématiques et techniques du code de Baudot-Gros-Gray
p. 93-108
Texte intégral
1Après avoir présenté les propriétés mathématiques du code binaire réfléchi et ses applications immédiates dans le cadre de la résolution du casse-tête du baguenodier, nous souhaitons nous intéresser ici davantage aux retombées mathématiques et techniques de ce code, afin de donner des éléments de contextualisation permettant de montrer comment la solution à une situation ludique (résoudre un casse-tête vendu comme jouet pour enfant dans le commerce) peut amener à des considérations utiles dans les applications des sciences et des techniques, tout en restant ancrée dans le domaine ludique.
Le code de Baudot-Gros-Gray dans les télécommunications
2Malgré le fait que le nom de Gray soit resté d’usage pour désigner le code binaire réfléchi, l’utilisation la plus ancienne du code en question fut celle développée par Émile Baudot (1845-1903) alors remplaçant dans l’administration des télégraphes à Chaumont, passionné par le côté scientifique de son environnement. Ses recherches remontent à 1872, il dépose sa première demande de brevet concernant un « Système de télégraphie rapide » le 17 juin 1874. Un crédit accordé par l’administration des Postes et Télégraphes permet de l’expérimenter en ligne en décembre 1875 sur un fil de 550 kilomètres. Les résultats obtenus sont satisfaisants et poussent Baudot à améliorer son système qu’il brevette à nouveau en 1876 sous le titre « Système d’appareil télégraphique multiple imprimeur » (Lesaffre 1932 : 41). Le premier spécimen qui a été construit a permis de desservir la ligne Paris-Bordeaux pendant plusieurs mois. Cet appareil, permettant à cinq employés de travailler simultanément sur le même fil, pouvait transmettre ou recevoir en une heure 36 000 à 40 000 lettres ou chiffres imprimés en caractères topographiques (Anon 1879 : 354)1.
L’invention de Baudot concerne, d’une part, le système téléimprimeur et, d’autre part, le code avec lequel il fonctionne, qui n’est autre qu’un code binaire. Baudot fut le premier à introduire un tel code dans des signaux, composés de cinq moments successifs d’égale durée2, contrairement au code Morse qui alterne des impulsions longues et courtes. Le clavier émetteur (figure 38) composé de deux touches pour le majeur et l’index de la main gauche et de trois touches pour l’index, le majeur et l’annulaire de la main droite permettait d’encoder 32 caractères (25), ce qui est insuffisant pour encoder les 26 lettres de l’alphabet, les 10 chiffres, les signes de ponctuation, les signes opératoires et les autres symboles (comme %, &). Le code Baudot utilise donc deux jeux de caractères, un pour les lettres, et un pour les chiffres et symboles, comme le montre la figure 39.
Figure 38 : Disposition des doigts de l’opérateur sur le clavier du télégraphe Baudot.

(Pendry 1919 : 41)
Figure 39 : Codage des lettres (à gauche) et des chiffres et symboles (à droite) selon les touches (IV, V pour gauche et I, II, III pour droite) du clavier de l’appareil de Baudot. Un point noir signifie qu’il faut enfoncer la touche correspondante sur le clavier. Par exemple, pour obtenir la lettre L, il faut enfoncer les touches IV et V de la main gauche (avec l’index et le majeur) et les touches I et II de la main droite (avec l’index et le majeur), soit 11 110.

(La Lumière Électrique 1882 : 80)
Bien que les claviers et les alphabets apparaissaient toujours en deux groupes (IV, V et I, II, III) du côté des émetteurs, le récepteur recevait le code dans l’ordre I, II, III, IV, V (figure 40), grâce notamment aux électro-aimants recevant l’information qui étaient arrangés dans cet ordre.
Figure 40 : Illustration du clavier émetteur (à gauche) et de l’ordre de réception du code (à droite). Le codage en langue française se lit à gauche (les deux premières colonnes).

Reproduit par www.circuitousroot.com à partir de (Pendry 1919 : 43-44)
Dans le combiné récepteur, le code binaire à cinq chiffres était stocké dans une roue codée qui était directement connectée au disque imprimeur (figure 41). Quand le disque tournait, il finissait par atteindre un angle où le motif en dessous de la tête de lecture était identique à celui reçu par le combiné récepteur, après quoi la tête de lecture était activée et imprimait la lettre, le nombre ou le symbole transmis3.
Figure 41 : Illustration de la roue codée qui reçoit l’information et imprime la lettre, le chiffre ou le symbole correspondant au code envoyé.

(La Lumière Électrique 1882 : 178)
Le disque récepteur est composé de parties en métal (conductrices) représentant le 1, et de parties dans un matériau isolant, représentant le 0, ainsi que de frotteurs qui lisent les informations reçues. Le problème avec un simple code binaire (à gauche dans la figure 42), c’est que des erreurs de lectures peuvent survenir au niveau de certaines frontières, comme à la ligne A-A par exemple, où le frotteur peut lire 0000, 0001, 0010 ou 0011 (on lit de l’intérieur de la roue vers l’extérieur, une case blanche vaut 0 et une noire vaut 1). Avec le code binaire réfléchi (représenté à droite dans la figure 42), seul un chiffre change à une position donnée au niveau des frontières, réduisant considérablement les erreurs de lecture. Certes, le code de Baudot n’est en soit pas complètement nouveau, mais il consiste en une réorganisation dans un certain ordre de nombres écrits en binaire, de manière à simplifier la lecture de la tête de lecture de la roue codée.
Figure 42 : À gauche est représenté le code binaire classique, à droite le code binaire réfléchi (et cyclique). Une case blanche représente un 0 et une case noire représente un 1. Le distributeur circulaire de gauche incrémente le code binaire de façon classique (dans le sens horaire) : 0000, 0001, 0010, 0011, 0100, etc. alors que le distributeur circulaire de droite incrémente le code de Gray : 0000, 0001, 0011, 0010, 0110, etc. réduisant ainsi considérablement les erreurs de lecture des informations envoyées.

© L. R.
Les talents de Baudot furent immédiatement reconnus, et après avoir exhibé son équipement à l’Exposition universelle de Paris en 18784, il reçut la médaille d’or et fut nommé chevalier de la Légion d’honneur. Son télégraphe devint alors un objet standard. Vers 1882, il y retravaille (partie codage) pour qu’il puisse opérer sur une chaîne de caractères complète (et non plus sur une lettre à la fois). Ce codage mécanisé de caractères fut mis en forme en 1887 sous le nom d’Alphabet international télégraphique (reconnu par l’Union internationale des télécommunications), et Baudot en fit la première démonstration en 1899 par une communication entre Marseille et Alger. Le code Baudot est standardisé en 1932 par le Comité consultatif international télégraphique et téléphonique, et il est maintenant connu comme l’alphabet international télégraphique no 2.
3Le télégraphe imprimeur de Baudot a fonctionné jusque dans les années 1950 et était considéré comme le meilleur des appareils télégraphiques de l’époque, avant d’être remplacé par le téléphone.
Il ne fait aucun doute que Baudot était un personnage précurseur. En effet, il peut être considéré comme l’inventeur à la fois du code cyclique permuté et du code à chaîne5.
Par la suite, le code de Baudot-Gros-Gray fut breveté par le physicien et chercheur aux laboratoires Bell, Frank Gray (1887-1969), le 17 mars 1953 sous le nom « Pulse Code Communication » (« communication par impulsion codée »). Le brevet présente le code en question avec pour utilisation principale de réduire les erreurs de codes dans la transmission des informations. Gray souligne que plusieurs inventions ont tenté de remédier à ce problème, mais qu’elles impliquaient une complexification des appareils à plusieurs niveaux. Son idée est alors de réduire les erreurs de codage en modifiant le code en lui-même ; c’est ainsi qu’il introduit le code binaire réfléchi qui portera plus tard son nom.
Quelques années auparavant, en 1943, George Stibitz (1904-1995), également chercheur aux laboratoires Bell – il sera reconnu internationalement comme l’un des pères du premier ordinateur numérique – dépose un brevet pour un « Binary Counter » (« compteur binaire ») ayant pour objectif de mesurer des intervalles de temps de différentes durées de façon précise et économique dans le domaine des communications. Le dispositif était constitué de balles élastiques et d’aimants, et des impulsions électriques déplaçaient les balles d’avant en arrière, faisant varier leur position selon le code binaire réfléchi. La deuxième page du brevet explique clairement la construction du code avec une liste faisant correspondre au nombre de pulsations (0, 1, 2, 3, etc. jusqu’à 16) leur équivalent dans le code binaire réfléchi6. Selon Martin Garder, qui se serait entretenu avec Stibitz à ce sujet, la mention de ce brevet aurait poussé ce dernier à écrire ce poème :
An ingenious fellow one day
Wrote numbers a new-fangled way.
As earlier had Stibitz,
But that name inhibits,
Historians who call the code “Gray”7.
Ces quelques lignes pourraient aussi bien s’appliquer aux personnages de Louis Gros ou d’Émile Baudot et conduiraient sans nul doute à d’autres belles rimes, mais elles permettent avant tout – de par leur légère poésie – de nous rappeler à des propos plus ludiques, et de revenir à des considérations baguenodières concernant l’application du code de Baudot-Gros-Gray aux casse-têtes.
Les retombées mathématiques et techniques du code de Baudot-Gros-Gray : du futile à l’utile, et vice-versa
4Aujourd’hui, le code de Baudot-Gros-Gray trouve des applications variées, essentiellement dans le domaine du numérique ; son utilisation première consiste à prévenir des états parasites, c’est-à-dire des erreurs susceptibles d’intervenir dans les communications (la transmission du signal TV par exemple) ou dans la lecture de séquences. On le trouve notamment dans l’exploitation des ordinateurs parallèles (optimisation des communications entre les ordinateurs branchés en réseau8), dans la minimisation des circuits logiques (table de Karnaugh9, expressions booléennes) dans les architectures en hypercubes, et dans la création de fonctions de hachage. En optique, le code de Baudot-Gros-Gray est fréquemment utilisé dans les capteurs angulaires ou de positionnement. D’autres codes continus – c’est-à-dire ayant la propriété que le passage d’un nombre au nombre suivant ne change qu’un seul chiffre – existent, mais ils conduisent à des chemins plus longs. Le code de Baudot-Gros-Gray est donc parmi les codes les plus utilisés en informatique et est « le plus élégant de tous les codes continus » (Delahaye 1997 : 101).
5En mathématiques, des recherches sur le code de Baudot-Gros-Gray ont été menées à partir des années 1970, notamment pour essayer de compter le nombre de codes binaires de Gray qu’il est possible de générer avec cinq chiffres (pour quatre chiffres et moins, les résultats étaient connus). Ronald Read (1924-2019), mathématicien britannique et professeur émérite en théorie des graphes, avait conçu un algorithme pour répondre à la question, mais ce dernier aurait mis 10 ans à faire les calculs… Le projet fut donc abandonné, puis résolu dans les années 1980. En 1986, le nombre de codes binaires de Gray à six chiffres était encore inconnu, mais estimé autour de 2,4 × 1025. De manière générale, trouver une formule pour le nombre de codes de Gray à n chiffres (en fonction de n) reste un problème combinatoire difficile à résoudre (Gardner 1986 : 22). Gardner (1986) mentionne également un article de 1984 de E. N. Gilbert qui montre comment le code binaire de Gray à trois chiffres peut être utilisé pour commencer une séquence qui génère une courbe de Hilbert qui remplira par passage à la limite un cube de dimension n.
Le code binaire réfléchi constitue également un moyen élégant pour cheminer et compter le nombre de termes présents dans les diagrammes de Veitch-Karnaugh, utiles pour représenter des ensembles lorsque le diagramme de Venn devient illisible, en général à partir de quatre ou cinq ensembles (Lefort 1974).
Enfin, on peut remarquer qu’avec un baguenodier à 6 anneaux, le ratio entre le nombre de changements à effectuer dans la marche ordinaire et le nombre de changements à effectuer dans la marche accélérée est de 42/31, pour 7 anneaux il est de 85/64. Le ratio progresse de la sorte : 1,338 ; 1,332 ; 1,334… Le mathématicien américain Nathan Mendelsohn (1917-2006) a montré que cette série convergeait rapidement vers 4/3 (Gardner 1986 : 16). Les liens entre le code de Baudot-Gros-Gray et les chemins hamiltoniens sur des hypercubes de dimensions supérieures à 3 s’inscrivent plus généralement dans le domaine de la théorie des treillis en algèbre ainsi que dans la théorie des réseaux. Plus récemment, l’informaticien et mathématicien américain Donald Knuth (né en 1938) – connu pour ses travaux pionniers en algorithmique – a entrepris l’écriture d’une série de livres en plusieurs volumes10 sur la programmation informatique : The Art of Computer Programming. Dans le volume 4A consacré à l’algorithmique combinatoire, Knuth dédie un chapitre à l’étude des n-uplets et des algorithmes intéressants qu’on peut mobiliser pour, dans un premier temps, générer tous les objets combinatoires qu’on souhaite observer et, dans un second temps, pour examiner individuellement chaque permutation d’un objet combinatoire à un autre. Il commence par regarder les n-uplets de nombres binaires (a1, a2, …, an), où aj = 0 ou aj = 1. Générer l’ensemble des n-uplets possibles revient en fait à trouver tous les sous-ensembles de l’ensemble {x1, x2, …, xn} en considérant que xj appartient au sous-ensemble en question si et seulement si aj = 1. Knuth précise qu’« […] un tel problème possède une solution ridiculement simple11 », mais que néanmoins, « […] ce problème tout à fait trivial présente des points d’intérêt étonnants lorsque nous l’examinons plus en profondeur12 ». Cette considération l’amène à présenter le code de Gray comme alternative la plus connue à l’ordre lexicographique pour visiter les n-uplets (Knuth 2004 : 2) et à faire le lien avec le baguenodier et sa résolution donnée par Louis Gros en 1972, et affirme que « Gros est le véritable inventeur du code binaire de Gray13 ». Dans la suite du chapitre, Knuth étend l’analyse aux cycles de Gray puis aux codes de Gray non binaires, puis propose une liste de 112 problèmes (plus ou moins ouverts) à résoudre, en lien avec ce qui a été présenté précédemment. La richesse de ces considérations et des questionnements qui en découlent montrent comment des problèmes récréatifs peuvent être à l’origine de développements plus poussés en mathématiques, dans divers domaines.
6Revenons à présent à des considérations plus légères, mais non dépourvues d’intérêt, au sujet d’autres casse-têtes qui ont été inventés au cours du xxe siècle et dont la solution est également basée sur le code de Baudot-Gros-Gray. Le premier en date est très certainement le jeu de réflexion inventé par Édouard Lucas dans les années 1880, pour lequel il reçoit une médaille à l’Exposition universelle de Paris de 1889 : la Tour d’Hanoï.
Figure 43 : La Tour d’Hanoï, boîte de jeu, plateau et disques originaux de la fin du xixe siècle.

© Michel Boutin
Le but de la Tour d’Hanoï (figure 43) est de déplacer les disques de la tour de départ à la tour d’arrivée en passant par une tour intermédiaire, en un minimum de coups et en respectant les règles suivantes : on ne peut déplacer qu’un seul disque à la fois, et l’on ne peut placer un disque sur un autre disque que si celui-ci est plus grand (ou sur un emplacement vide). L’enchaînement des déplacements des disques est donné par le code de Baudot-Gros-Gray, et le nombre minimum de coups est de 2 n − 1 pour un jeu composé de n disques. Dans sa version classique, la Tour d’Hanoï est constituée d’une planchette sur laquelle sont fixées 3 tiges (disposées en triangle comme le montre la figure 43 ou alignées – version plus répandue actuellement dans le commerce) ; sur l’une d’elles sont enfilés 8 disques de diamètres différents, du plus grand en bas au plus petit en haut. Le Conservatoire national des arts et métiers possède deux jeux de ce type donnés par Lucas en personne : le jeu classique (figure 43) et un jeu particulier avec 6 tiges et 8 disques (Boutin 2019 : 30). Dans le fascicule d’accompagnement de 1889, intitulé « Jeux scientifiques no 3 : la Tour d’Hanoï » et édité par Chambon & Baye, on trouve un paragraphe dédié aux variantes de la Tour d’Hanoï classique ; Lucas suggère de prendre une tour à 5 tiges et 16 disques, répartis en quatre couleurs différentes. Le problème consiste alors à enfiler les disques de même couleur sur les 4 autres tiges que la centrale. Malheureusement, le Conservatoire ne possède pas cette variante de la Tour (Boutin 2019 : 29-30).
7Dans les années 1970, plusieurs casse-têtes mécaniques ont également été commercialisés en utilisant le code de Baudot-Gros-Gray comme solution. Un exemple notable est The Brain, inventé par l’informaticien Marvin H. Allison Jr. et commercialisé par l’entreprise Mag-Nif (Gardner 1986 : 20). Le casse-tête consiste en une tour composée de disques transparents qui tournent horizontalement (rotation) par rapport à leur centre (figure 44).
Figure 44 : The Brain, inventé en 1973 par Marvin H. Allison et toujours commercialisé.

© Jake Olefsky (puzzlesolver.com)
Les disques transparents sont fendus, avec huit tiges verticales passant à travers les fentes. Les tiges peuvent être déplacées selon deux positions : vers le centre du casse-tête ou vers l’extérieur, et le but est de faire tourner les disques dans des positions qui permettent de positionner toutes les tiges vers l’extérieur. Le code de Baudot-Gros-Gray fournit la solution à ce casse-tête en 170 coups (tel un baguenodier à 8 anneaux qu’on démonte par la marche ordinaire).
Notons que les casse-têtes présentés jusqu’à présent sont constitués de matériaux solides : bois, plastique, métal avec certaines parties mobiles, mais néanmoins rigides. Il existe également d’autres casse-têtes présentant d’autres matériaux – ce qui implique une préhension de l’objet et des mécanismes de manipulation différents – par exemple avec une corde. Ces derniers, malgré le fait que l’analyse mathématique soit identique à celle du baguenodier, paraissent beaucoup plus difficiles à résoudre, à cause de la mobilité excessive de la corde qu’il n’est pas toujours possible de contrôler. C’est le cas par exemple du casse-tête figure 45, pour lequel la navette, qui se trouve être rigide dans le « vrai » baguenodier, est ici remplacée par une cordelette fermée en boucle, passant par un anneau libre à l’une des extrémités du casse-tête (anneau qui par ailleurs, est tout à fait inutile et qui a pour but de compliquer le démontage de l’objet !).
Figure 45 : Variante d’un baguenodier à 8 anneaux, dont la navette rigide est remplacée par une cordelette en boucle contenant elle-même un anneau (à gauche de la photographie).

© L. R.
Un autre casse-tête dont la solution repose sur un code de Gray est le Loony Loop : l’objet est constitué de quatre boucles en acier (rigides) entrelacées d’une façon particulière et d’une corde de nylon qui d’apparence semble capturée dans les boucles de façon permanente. Le but est de libérer la corde en nylon. Le casse-tête est également référencé sous le nom de Nœud Gordien dans l’ouvrage 1000 casse-tête du monde entier de Van Delft et Botermans14, car selon la mythologie grecque, le nœud gordien vient de Gordius, roi de Phrygie qui, à l’aide d’un nœud extrêmement compliqué, attacha le timon d’une charrette à un pieu. L’oracle aurait alors prédit que quiconque déferait le nœud deviendrait roi de toute l’Asie. Mais tous ceux qui essayèrent – et apparemment ils furent nombreux – échouèrent (Van Delft & Botermans 1977 : 146). Ce casse-tête se généralise à n boucles, et se résout en appliquant un code de Gray, mais ternaire (c’est-à-dire en base 3, utilisant les symboles 0, 1 et 2) à la séquence de mouvements. Selon Gardner, ce casse-tête curieux aurait une histoire qui mériterait de s’y attarder un peu (peut-être cela sera l’objet d’un prochain livre ?). En tout cas, les auteurs du conséquent ouvrage sur les jeux et casse-têtes mathématiques Winning Ways for Your Mathematical Plays (Berlekamp, Conway & Guy 2004) y consacrent un chapitre entier dans lequel on trouve d’autres variantes de ce type de casse-tête, notamment une qu’ils appellent The Chinese Strings, nom dérivé de l’appellation anglophone du baguenodier Chinese Rings. Cette variation originale – et facile à fabriquer – du baguenodier fut brevetée en 1914 par William Rutledge (on trouve plus tard d’autres brevets du même type, par exemple celui de Davies, Fay, P. Puzzle. Brevet US 2 324 566. 20 juillet 1943) et se présente sous la forme de la figure 46 :
Figure 46 : Le casse-tête de Rutledge, ici avec 4 anneaux. La navette est matérialisée par la cordelette blanche et les anneaux sont fixes.

© L. R.
Le but du casse-tête est de réussir à sortir la cordelette du mécanisme. Là encore, le fait que les anneaux soient fixes et la navette très (voire trop) souple rend la manipulation complètement différente d’un baguenodier classique. En revanche, il se trouve que ce type de casse-têtes assez populaires, pour lequel il faut libérer une corde enchevêtrée dans une partie plus rigide avec des anneaux fixes, aboutit à d’intéressants problèmes dans le domaine mathématique de la topologie en basses dimensions. Par exemple, en 2002, les mathématiciens Józef Przytycki (Université George Washington) et Adam Sikora (Université de Buffalo) publient un article dans les Proceedings of the American Mathematical Society dans lequel ils prouvent une conjecture émise quelques années auparavant par Louis H. Kauffman (1996) de l’Université de l’Illinois concernant la solution la plus simple possible15 pour résoudre un tel casse-tête à n anneaux fixes : « Théorème 1.1. La complexité minimale de la solution pour le Baguenodier à n colonnes […] est 2 n− 1.16 » Ils expliquent que la preuve apportée à cette conjecture implique la découverte de nouvelles techniques de compréhension concernant la topologie des graphes en dimension trois et qu’il est particulièrement amusant de s’intéresser à un casse-tête classique aussi fascinant que le baguenodier et d’y trouver dans sa résolution un problème majeur en topologie (Przytycki & Sikora 2002 : 895). La preuve repose sur une correspondance entre des résultats développés en théorie des nœuds (invariant de nœuds) par Kazuo Habiro (Université de Kyoto) en 2000 et la séquence de mouvements nécessaire pour libérer la corde du casse-tête. La dernière section de l’article est consacrée à présenter les problèmes étudiés en théorie des groupes qui sont impliqués dans la preuve de la conjecture de Kauffman, illustrant une nouvelle fois comment les mathématiques récréatives peuvent être à la source de recherches fondamentales en mathématiques, parfois également en lien avec des applications en physique ou en biologie moléculaire (Kauffman 1996).
8En 1972, William Keister, ingénieur au laboratoire Bell et ancien collègue de Gray, fait breveter un casse-tête intitulé Pattern-Machine Puzzle, plus connu maintenant sous le nom de Spin Out.
Figure 47 : Le Spin Out, avec 7 boutons pivotants.

© Jake Olefsky (puzzlesolver.com)
L’instrument se présente sous la forme d’une règle avec une partie coulissante qu’il faut désolidariser, mais que les boutons pivotants bloquent. Dans la position initiale, tous les boutons sont placés à la verticale, et il faut réussir à tous les placer à l’horizontale pour faire sortir la partie coulissante. Seulement, il n’y a qu’un emplacement – fixe – où les boutons peuvent être pivotés (sur la droite de la figure 47, en bas, se trouve une petite encoche circulaire), en plus du bouton le plus à droite qui peut tout le temps être pivoté. Inutile d’entrer dans les détails de la résolution de ce casse-tête, l’analogie avec le baguenodier est assez évidente. Dans son brevet, Keister précise que le mécanisme peut être adapté pour créer d’autres casse-têtes qui demanderaient chacun une série de mouvements différents à effectuer (Keister 1972). Là encore, le Spin Out – en tant que variante du baguenodier classique – trouve sa place aux côtés d’autres casse-têtes du même genre dans un article récemment publié dans The Mathematical Gazette (Cooper 2019), notamment pour présenter leurs résolutions en lien avec le code de Baudot-Gros-Gray en base 2, mais aussi en base 3 (pour le casse-tête intitulé Crazy Elephant Dance par exemple), puis en base b quelconque17.
9Tous ces casse-têtes purement mécaniques peuvent également se décliner sous d’autres versions nécessitant des composants électroniques ou programmées sur ordinateur. Cette situation est assez fréquente dans l’histoire des jeux mathématiques qui font appel au binaire dans leur résolution. Nous avons pu le voir dans le chapitre 3 par l’exemple du jeu de Nim qui s’est rapidement – dès que la technique l’a permis – retrouvé sous forme électromécanique dans les années 1940, puis a été programmé sur ordinateur. Une version électronique du baguenodier fut proposée en 1938 par Joseph Rosenbaum dans le journal américain American Mathematical Monthly sous la forme d’un problème posé de la sorte : une ampoule électrique est connectée à n interrupteurs de sorte que la lumière est allumée quand tous les interrupteurs sont fermés. Chaque interrupteur est contrôlé par un bouton-poussoir, mais il n’est pas possible de savoir si l’interrupteur est ouvert ou fermé. Quel est l’ordre dans lequel il faut pousser les boutons pour allumer l’ampoule ? Et quel est alors le nombre minimal de pressions d’interrupteurs nécessaire pour être certain d’allumer l’ampoule sans connaître la position des interrupteurs à l’état initial ? La solution est donnée à la suite de l’énoncé du problème par Rosenbaum qui généralise au cas où chaque interrupteur s’éteint après avoir enclenché le bouton poussoir p fois. Selon Gardner (1986), ce système n’a pas été breveté et l’inventeur est inconnu, mais il était disponible à la vente dans des magasins de magie avec trois interrupteurs et une ampoule. En 1971, le magazine Popular Electronics à destination des amateurs et expérimentateurs d’électronique propose au lecteur de fabriquer sa propre version – nommée Princeps Puzzle (Cuccia 1971) – avec huit ampoules et huit boutons-poussoirs, selon un modèle déjà décrit en 1944 par Albert Beiler dans un article intitulé An Electrical Chinese Ring Puzzle (Beiler 1944). Dans cette contribution, il y a initialement sept ampoules de couleur rouge, toutes éteintes, ainsi qu’une grosse ampoule verte également éteinte (celle-ci ne s’allume que quand toutes les ampoules rouges sont allumées). Chaque ampoule est dotée de deux boutons-poussoirs : un pour allumer l’ampoule, l’autre pour l’éteindre. Seulement, appuyer sur le bouton ON (ou le bouton OFF) d’une ampoule n’allume (ou n’éteint) pas nécessairement l’ampoule en question… Il faut effectuer le bon enchaînement sur les différents boutons-poussoirs pour que les ampoules s’allument au moment voulu. Une ampoule allumée correspond ainsi à un anneau de baguenodier abaissé (et une ampoule éteinte à un anneau élevé), et quand toutes les ampoules rouges sont allumées (c’est-à-dire quand la navette est libérée de tous les anneaux du baguenodier), la grosse ampoule verte s’allume signifiant que la position finale est atteinte. La condition pour allumer une ampoule est ainsi formulée par Beiler :
Une ampoule peut être allumée ou éteinte seulement si la séquence qui a précédé a été suivie correctement et ensuite seulement par son propre bouton-poussoir18.
Beiler présente ensuite un schéma de la construction du circuit électrique et détaille un exemple en retraçant le chemin emprunté par l’électricité pour allumer telle ou telle ampoule selon la séquence de boutons-poussoirs enclenchés. Il conclut en précisant que ce système peut être construit à prix raisonnable avec des matériaux de récupération et qu’il est du meilleur effet lors de soirées mondaines :
[…] de nombreuses soirées de bridge ont été interrompues par une dame qui refusait de jouer tant qu’elle n’avait pas réussi à allumer la lampe verte19.
10Enfin, en digressant légèrement vers des mondes plus imaginaires, les amateurs de Lewis Carroll (1832-1898) pourront apprécier certaines similitudes entre les codes de Gray et les jeux de mots inventés par l’auteur britannique appelés doublets ou échelles de mots. Les doublets consistent à relier deux mots par une série de mots semblables en un minimum de modifications. Les modifications possibles à chaque étape sont : ajouter une lettre ou enlever une lettre ou changer une lettre ou réordonner les mêmes lettres pour obtenir une anagramme du mot. Le joueur qui parvient à créer les doublets avec le moins de modifications possible est gagnant. Par exemple, pour obtenir « misez » à partir de « rime », il est possible de passer par les étapes suivantes :
- rime
- mire (réordonner)
- mise (changement d’une seule lettre)
- misez (ajout d’une lettre).
Le code de Baudot-Gros-Gray intervient si l’on assigne un 0 à toutes les lettres du mot initial et un 1 à toutes les lettres du mot final. Le problème revient alors à construire un code de Baudot-Gros-Gray (en ne modifiant qu’un seul chiffre à la fois) qui permette de passer de 0000 à 11 111 dans l’exemple ci-dessus. Nous renvoyons aux travaux de Martin Gardner à ce sujet (un chapitre de son New Mathematical Diversions from Scientific American, 1966) et à un article de Rudolph Castown (1968) intitulé : The Arithmetic of Word Ladders.
Notes de bas de page
1Pour une description générale du télégraphe multiple imprimeur de Baudot et de son fonctionnement, voir (Anon 1879), ainsi que les articles publiés dans le journal La Lumière Électrique entre septembre 1881 et mars 1882. Ces derniers s’attachent à expliquer en détail les organes de transmission, de réception, de traduction et d’impression du télégraphe de Baudot.
2La transmission était rythmée par métronome. Pour un résumé historique des principales transformations et applications de l’appareil télégraphique de Baudot, de ses origines à 1931, voir (Lesaffre 1932).
3Au cours de la révolution des frotteurs sur le disque et à un moment, un seul, déterminé par les positions de travail ou de repos imposé, sous l’action du signal reçu, un circuit local se fermait par l’intermédiaire desdits frotteurs, contacts et butoirs, et provoquait le déclenchement du système imprimeur pour la traduction de ce système en un caractère typographique (Lesaffre 1932 : 41).
4Notons qu’à cette date, Louis Gros est toujours en vie, il a 64 ans, et il n’est pas impossible qu’il soit allé visiter l’Exposition universelle de Paris. Nous savons en effet qu’il a visité celle de Lyon en 1872, car il dit avoir été déçu de ne pas y voir de jeux exposés (Gros 1872a : 205).
5(Heath 1972 : 83) : « There is no doubt, however, that Baudot was the dominant figure. Indeed, he can be regarded as the inventor or both cyclic-permuted code and the chain code. », ma traduction.
6Voir le brevet (Stibitz, George, Binary Counter, US. 2.307.868, 12 janvier 1843).
7(Gardner 1986 : 20). Nous avons laissé le texte en anglais pour garder les rimes de ce petit poème, dont une traduction serait : « Un type ingénieux un jour/A écrit les nombres d’une façon ultramoderne./Comme Stibitz l’avait fait plus tôt,/Mais ce nom n’attire pas/Les historiens qui l’appellent le code “Gray”. »
8Les unités de calculs de la machine sont placées sur un réseau correspondant à un hypercube, et le code de Baudot-Gros-Gray fournit une numérotation des sommets de cet hypercube permettant le contrôle et l’optimisation des communications (Delahaye 1997 : 101).
9Une table de Karnaugh est une méthode graphique (qui passe par la création d’un tableau) pour trouver ou simplifier une fonction logique à partir de sa table de vérité (table utilisée pour représenter les expressions logiques et mesurer la valeur : VRAIE ou FAUSSE).
10Pour l’instant, seuls les premiers volumes (1 à 4) ont été publiés sur les sept volumes prévus (soit plus de 2 000 pages).
11(Knuth 2004 : 1) : « Of course such a problem has an absurdly simple solution. », ma traduction.
12(Knuth 2004 : 1) : « We will see, however, that even this utterly trivial problem has astonishing points of interest when we look into it more deeply. », ma traduction.
13(Knuth 2004 : 5) : « Thus Gros is the true inventor of Gray binary code. », ma traduction.
14Il peut être consulté à cette adresse : http://collection.cassetete.free.fr/8_divers/1000_casse_tete/scans_van_delft/page_146.jpg [consulté le 09/09/2022].
15La complexité d’une solution donnée pour résoudre le casse-tête est définie par les auteurs de l’article comme étant le nombre minimal de fois où la corde passe par l’arc imaginaire connectant l’anneau le plus haut à la base du casse-tête (Przytycki & Sikora 2002 : 895).
16(Przytycki & Sikora 2002 : 895) : « Theorem 1.1. The minimal complexity of a solution for the Chinese Rings with n columns […] is 2n−1. », ma traduction.
17Voir (Cooper 2019) pour davantage de détails.
18(Beiler 1944 : 134) : « A lamp can be lit or extinguished only if the correct sequence has been followed previously and then only by its own push-buttons. », ma traduction, partie en italique dans le texte original.
19(Beiler 1944 : 136) : « […] many a bridge party has been disrupted by a lady who would refuse to play until she could get the green lamp to light. », ma traduction.
Le texte seul est utilisable sous licence Licence OpenEdition Books. Les autres éléments (illustrations, fichiers annexes importés) sont « Tous droits réservés », sauf mention contraire.
Le binaire au bout des doigts
Ce livre est diffusé en accès ouvert freemium. L’accès à la lecture en ligne est disponible. L’accès aux versions PDF et ePub est réservé aux bibliothèques l’ayant acquis. Vous pouvez vous connecter à votre bibliothèque à l’adresse suivante : https://freemium.openedition.org/oebooks
Si vous avez des questions, vous pouvez nous écrire à access[at]openedition.org
Le binaire au bout des doigts
Vérifiez si votre bibliothèque a déjà acquis ce livre : authentifiez-vous à OpenEdition Freemium for Books.
Vous pouvez suggérer à votre bibliothèque d’acquérir un ou plusieurs livres publiés sur OpenEdition Books. N’hésitez pas à lui indiquer nos coordonnées : access[at]openedition.org
Vous pouvez également nous indiquer, à l’aide du formulaire suivant, les coordonnées de votre bibliothèque afin que nous la contactions pour lui suggérer l’achat de ce livre. Les champs suivis de (*) sont obligatoires.
Veuillez, s’il vous plaît, remplir tous les champs.
La syntaxe de l’email est incorrecte.
Référence numérique du chapitre
Format
Référence numérique du livre
Format
1 / 3