Circuits et nombre 2-adiques, une nouvelle vision de l'échange temps-espace

Les circuits synchrones permettent de travailler à la fois dans le temps et dans l’espace. L’exemple le plus simple est l’additionneur sériel SerialAdder de la figure 3. Les nombres d’entrée y sont présentés poids faibles d’abord, donc un 0 puis un 1 puis des 0 pour le nombre 2. Le FullAdder combinatoire fait une addition à chaque cycle, le registre propageant la retenue d’un cycle vers le suivant. Une paire de bits d’entrée produit un bit de somme à chaque cycle sur le fil de sortie du circuit. L’addition se fait dans le temps et non plus dans l’espace comme dans le cours précédent.

Trois autres circuits d’addition sérielle sont présentés dans la figure 4. Celui de gauche imbrique le temps et l’espace en traitant 2 bits à chaque cycle : la retenue des bits de rang pair est passée dans l’espace, celle des bits impairs dans le temps. Celui du milieu est plus subtil, car le doublement du registre entrelace dans le temps deux additions indépendantes, celle des nombres composés des bits d’ordre pair aux cycles pairs et celle des nombres composés des bits d’ordre impair aux cycles impairs. Nous l’appelons additionneur stéréo en référence au traitement entrelacé du canal droit et du canal gauche d’un enregistrement stéréophonique. Son principe se généralise à tout circuit séquentiel. Celui de droite utilise une technique fondamentale d’optimisation fondée sur l’échange espace-temps, le pipeline. Les opérations combinatoires y sont coupées par des rangées de registres, ce qui accroît la vitesse d’horloge au prix d’une augmentation de la surface et de la latence, qui est le délai entre la fourniture des entrées aux circuits et celle des sorties par le circuit. C’est l’analogue de la méthode introduite par Henry Ford pour l’industrie automobile, les registres assurant le déplacement des objets dans la chaîne de montage.

Les nombres 2-adiques comme modèle des circuits séquentiels

Contrairement à l’additionneur combinatoire, l’additionneur sériel traite sans problème des chaînes de bits infinies, car la propagation de la retenue se fait dans le sens du temps. Or, les nombres écrits en base p avec une infinité de décimales mais poids faibles d’abord sont fondamentaux en mathématiques, où ils sont appelés entiers p-adiques. Nos suites infinies de bits sont donc des nombres 2-adiques. Les 2-adiques ont l’avantage d’unifier logique et arithmétique, car ils codent aussi les fonctions caractéristiques d’ensembles d’entiers en prenant comme éléments d’un ensemble les rangs des 1 dans la suite de bits du nombre 2-adique. Les extensions point à point des opérations booléennes ~ (négation), ∧ et ∨ calculent la complémentation, l’intersection et l’union des ensembles.

Notons les nombres 2-adiques en gras et leur développement binaire infini avec un indice 2 initial, le premier bit étant de rang 0. Le nombre 0, qui dénote aussi l’ensemble vide, s’écrit ₂000… Comme il est périodique, on l’écrit aussi avec la période entre parenthèse : 0 = ₂(0) = ∅. On a ensuite 1 = ₂10000… = ₂1(0) = {0}, 2 = ₂01000… = ₂01(0) = {1}, 3 = ₂11000… = ₂11(0)= {0,1}, etc. L’addition se fait de gauche à droite en propageant la retenue à l’infini, donc dans le sens de l’écriture. Elle est réalisée par le circuit SerialAdder de la figure 3. La multiplication se fait aussi par prolongation à l’infini de la multiplication classique. Ces deux opérations donnent aux nombres 2-adiques une structure d’anneau (nous n’utiliserons pas ici la structure de corps 2-adique).

Les opposés se calculent par « complémentation à 2 infinie » : -1 = ₂11111… = ₂(1) = {0,1,2,…}, puisque 1+(-1) = 0, puis -2 = ₂01111… = ₂0(1) = {1,2,3,…}, etc. Les nombres périodiques correspondent aux rationnels à dénominateur impair. Par exemple, pour x = ₂101010… = ₂(10) = {i | i pair}, on peut écrire x = ₂100000…+ ₂001010, donc x = 1 + 4x puisque ajouter 00 en tête d’un 2-adique revient à le multiplier par 4, d’où x = -1/3.

Une relation 2-adique fondamentale est la relation arithmético-logique∀x. x + ~x = -1, évidente car l’addition de x et ~x se fait sans retenue. Si on pose y = ~(-1/3)= ₂010101… = ₂(01) = {i | i impair}, il est facile de voir qu’on a y = -2/3 puisque -1/3 + y= -1 d’après l’identité arithmético-logique. Je laisse le soin au lecteur de vérifier que tout nombre rationnel –p/q possède bien un développement 2-adique, ce qui n’est pas vrai pour les rationnels à dénominateur pair : 1/2 n’est pas représentable car son premier bit b devrait vérifier b+b = 1, ce qui est impossible.

Le remarquable travail de Jean Vuillemin [2] établit les rapports entre les 2-adiques et les circuits. Les points essentiels sont résumés dans la figure 5. D’abord, le circuit FullAdder trouve en 2-adiques une définition bien plus intéressante que sa définition purement combinatoire de la figure 1. Si on note a, b, c, s,r, les suites d’entrées et sorties de l’additionneur au cours du temps vues comme 2-adiques, alors FullAdder vérifie l’invariant 2-adique a + b + c = s + 2r, qui remplace avantageusement le calcul booléen par le calcul numérique. Le second point est qu’un registre est un multiplieur par 2 pour les 2-adiques, puisqu’il sort un 0 initial puis les bits d’entrée retardés. Si on rajoute une négation booléenne de chaque côté du registre, représentée par un cercle, le « registre à oreilles » obtenu calcule 1+2x pour l’entrée x.

Cette formalisation rend triviales des preuves qui seraient difficiles en suivant les bits un par un. Par exemple, il est trivial que le circuit de gauche dans la figure 6 calcule z = x-y : l’invariant de FullAdder donne x + ~y + c = z + 2r, et celui du registre à oreilles donne c = 1+2r. Donc x + ~y + 1 = z en simplifiant par 2r, et x-y = z puisque~y + 1 = -y d’après l’identité arithmético-logique. La preuve est triviale, mais elle ne dit vraiment rien de ce qui se passe au niveau des bits !

Le cours a présenté de superbes circuits pour calculer 3x et x/3, généralisables à tout p impair, la quasi-division 1/1-2x, et, en point d’orgue la quasi-racine carrée √(1-8x), dont la preuve de 5 lignes est étourdissante. Je renvoie aux vidéos et transparents pour les détails.

Les entiers 2-adiques forment également un espace topologique compact avec la norme 2-adique║x║ = 2^-n si n = min{i | x_i = 1}. La distance associée est définie par d(x,y) = ║x-y║. Autrement dit, deux entiers 2-adiques x et y sont à distance 2^-n si et seulement si le segment initial commun de leur développement est de longueur n. J. Vuillemin a démontré le théorème fondamental suivant :

Théorème : une fonction f : 2z → 2z est calculable par un circuit synchrone (éventuellement de mémoire infinie) si et seulement si elle est contractante pour la distance 2-adique : ∀x, y. d(f(x),f(y)) ≤ d(x,y).

Toute fonction calculée par un circuit synchrone est trivialement contractante, car l’inégalité exprime que les sorties sont égales sur les n premiers bits si les entrées sont égales sur les n premiers bits. La réciproque, bien plus subtile, construit une forme normale dite Sequential Decision Diagram (SDD), fondée sur une représentation dans le temps et dans l’espace de la table de vérité de la fonction.

Un résultat constamment utilisé mais rarement prouvé est qu’on peut toujours reboucler toute sortie sur toute entrée si tout chemin d’une entrée vers une sortie est coupé par un registre. Ce n’est en fait qu’une conséquence du théorème de Banach disant que toute fonction Lipschitzienne sur un compact a un point fixe unique : dire que tout chemin est coupé revient à dire d(f(x),f(y)) < d(x,y), équivalent à d(f(x),f(y)) < 0,6 d(x,y) d’après la définition de la distance, CQFD.

Le cours a présenté d’autres propriétés fondamentales de l’interprétation 2-adique : le fait qu’on puisse implémenter les fonctions continues et pas seulement synchrones en travaillant avec des pairs de fils validité-valeur, donc en rendant le temps élastique comme expliqué plus loin ; le fait qu’on puisse linéariser la forme normale SDD de Vuillemin en un nombre 2-adique qui représente la table de vérité dans le temps et l’espace de la fonction ; le résultat consistant à voir ce nombre comme définissant une série formelle, qui est algébrique si et seulement si la fonction peut être implémentée par un circuit de mémoire finie ; le fait extraordinaire que, vu comme un nombre réel en le préfixant par « 0, », ce nombre est soit rationnel, soit transcendant, etc. Beaucoup de travail reste à faire dans ce domaine magnifique mais trop peu connu à mon goût.