# Fonctionnement d'un ordinateur/Les encodages spécifiques aux bus

Avant de passer aux liaisons point à point et aux bus, nous allons voir comment un bit est codé sur un bus. Vous pensez certainement que l'encodage des bits est le même sur un bus que dans un processeur ou une mémoire. Mais ce n'est pas le cas. Il existe des encodages spécifiques pour les bus.

## Les codes en ligne : le codage des bits sur une ligne de transmission

Il existe des méthodes relativement nombreuses pour coder un bit de données pour le transmettre sur un bus : ces méthodes sont appelées des codages en ligne. Toutes codent celui-ci avec une tension, qui peut prendre un état haut (tension forte) ou un état bas (tension faible, le plus souvent proche de 0 volts). Outre le codage des données, il faut prendre aussi en compte le codage des commandes. En effet, certains bus série utilisent des fils dédiés pour la transmission des bits de données et de commande. Cela permet d'éviter d'utiliser trop de fils pour un même procédé.

### Les codages non-différentiels

Pour commencer, nous allons voir les codages qui permettent de transférer un bit sur un seul fil (nous verrons que d'autres font autrement, mais laissons cela à plus tard). Il en existe de toutes sortes, qui se distinguent par des caractéristiques électriques qui sont à l’avantage ou au désavantage de l'un ou l'autre suivant la situation : meilleur spectre de bande passante, composante continue nulle/non-nulle, etc. Les plus courants sont les suivants :
* Le codage NRZ-L utilise l'état haut pour coder un 1 et l'état bas pour le zéro (ou l'inverse).
* Le codage RZ est similaire au codage NRZ, si ce n'est que la tension retourne systématiquement à l'état bas après la moitié d'un cycle d'horloge. Celui-ci permet une meilleure synchronisation avec le signal d'horloge, notamment dans les environnements bruités.
* Le codage NRZ-M fonctionne différemment : un état haut signifie que le bit envoyé est l'inverse du précédent, tandis que l'état bas indique que le bit envoyé est identique au précédent.
* Le codage NRZ-S est identique au codage NRZ-M si ce n'est que l'état haut et bas sont inversés.
* Avec le codage Manchester, aussi appelé codage biphasé, un 1 est codé par un front descendant, alors qu'un 0 est codé par un front montant (ou l'inverse, dans certaines variantes).
Faisons une petite remarque sur le codage de Manchester : il s'obtient en faisant un XOR entre l'horloge et le flux de bits à envoyer (codé en NRZ-L). Les bits y sont donc codés par des fronts montants ou descendants, et l'absence de front est censé être une valeur invalide. Si je dis censé, c'est que de telles valeurs invalides peuvent avoir leur utilité, comme nous le verrons dans le chapitre sur la couche liaison. Elles peuvent en effet servir pour coder autre chose que des bits, comme des bits de synchronisation entre émetteur et récepteur, qui ne doivent pas être confondus avec des bits de données. Mais laissons cela à plus tard.

### Les codages différentiels

Pour plus de fiabilité, il est possible d'utiliser deux fils pour envoyer un bit (sur un bus série). Ces deux fils ont un contenu qui est inversé électriquement : le premier utilise une tension positive pour l'état haut et le second une tension négative. Ce faisant, on utilise la différence de tension pour coder le bit. Un tel codage est appelé un codage différentiel.
Ce codage permet une meilleure résistance aux perturbations électromagnétiques, aux parasites et autres formes de bruits qui peuvent modifier les bits transmis. L'intérêt d'un tel montage est que les perturbations électromagnétiques vont modifier la tension dans les deux fils, la variation induite étant identique dans chaque fil. La différence de tension entre les deux fils ne sera donc pas influencée par la perturbation.
    Évidemment, chaque codage a son propre version différentielle, à savoir avec deux fils de transmission.
Ce type de codage est, par exemple, utilisé sur le protocole USB. Sur ce protocole, deux fils sont utilisés pour transmettre un bit, via codage différentiel. Dans chaque fil, le bit est codé par un codage NRZ-I.

### Les codes redondants

D'autres bus encodent un bit sur plusieurs fils, mais sans pour autant utiliser de codage différentiel. Il s'agit des codes redondants, dans le sens où ils dupliquent de l'information, ils dupliquent des bits. L'intérêt est là encore de rendre le bus plus fiable, d'éliminer les erreurs de transmission.
La méthode la plus simple est la suivante : le bit est envoyé à l'identique sur deux fils. Si jamais les deux bits sont différents à l'arrivée, alors il y a un problème. Une autre méthode encode un 1 avec deux bits identiques, et un 0 avec deux bits différents, comme illustré ci-dessous. Mais ce genre de redondance est rarement utilisé, vu qu'on lui préfère des systèmes de détection/correction d'erreur comme un bit de parité.
Les codes redondants sont aussi utilisés pour faire communiquer entre eux des composants asynchrones, à savoir deux composants qui ne ne sont pas synchronisés par l'intermédiaire d'une horloge. Il s'agit d'ailleurs de leur utilisation principale. Vu que les composants ne sont pas synchronisés par une horloge, il se peut que certains bits arrivent avant les autres lors de la transmission d'une donnée sur une liaison parallèle. L'usage d'un code redondant permet de savoir quels bits sont valides et ceux pas encore transmis. Nous détaillerons cela à la fin de ce chapitre.

## L'ordre d'envoi des bits sur une liaison série

Sur une liaison ou un bus série, les bits sont envoyés uns par uns. L'intuition nous dit que l'on peut procéder de deux manières : soit on envoie la donnée en commençant par le bit de poids faible, soit on commence par le bit de poids fort. Les deux méthodes sont valables et tout n'est au final qu'une question de convention. Les deux méthodes sont appelées LSB0 et MSB0. Avec la convention LSB0, le bit de poids faible est envoyé en premier, puis on parcourt la donnée de gauche à droite, jusqu’à atteindre le bit de poids fort. Avec la convention MSB0, c'est l'inverse ; on commence par le bit de poids fort, on parcours la donnée de gauche à droite, jusqu'à arriver au bit de poids faible.
Exemple sur un octet (groupe de 8 bits) :
* Convention de numérotation LSB0 : Le premier bit transmis (bit 0) est celui de poids faible (LSB)
* (bit numéro 7) Le bit de poids fort (MSB), celui le plus à gauche, vaut 1 (poids 2$^7$).
* (bit numéro 0) Le bit de poids faible (LSB), celui le plus à droite, vaut 0 (poids 2$^0$).
* Convention de numérotation MSB0 : Le premier bit transmis (bit 0) est celui de poids fort (MSB)
* (bit numéro 0) Le bit de poids fort (MSB), celui le plus à gauche, vaut 1 (poids 2$^7$).
* (bit numéro 7) Le bit de poids faible (LSB), celui le plus à droite, vaut 0 (poids 2$^0$).

## Les encodages de bus

Les encodages de bus encodent des données pour les envoyer sur un bus. Ils s'appliquent aux bus parallèles, à savoir ceux qui transmettent plusieurs bits en même temps sur des fils séparés. Un de leurs nombreux objectifs est de réduire la consommation d'énergie des bus parallèles. La consommation d'énergie dépend en effet de deux choses : de l'énergie utilisée pour faire passer un fil de 0 à 1 (ou de 1 à 0), et du nombre de fois qu'il faut inverser un bit par secondes. Le premier paramètre est fixé une fois pour toute, mais le second ne l'est pas et peut être modifié par des encodages spécifiques.

### Le retour du code Gray

Une première idée serait d'utiliser des encodages qui minimisent le passage d'un 0 à un 1 et inversement. Dans les premiers chapitres du cours, nous avions parlé du code Gray, qui est spécifiquement conçu dans cet optique. Rappelons qu'avec des entiers codés en code de Gray, deux entiers consécutifs ne différent que d'un seul bit. Ainsi, quand on passe d'un entier au suivant, seul un bit change de valeur. Une telle propriété est très utile pour les compteurs, mais pas vraiment pour les bus : on envoie rarement des données consécutives sur un bus.
Il y a cependant un contre-exemple assez flagrant : le bus mémoire ! En effet, les processeurs ont tendance à accéder à des données consécutives quand ils font des lectures/écritures successives. Nous verrons pourquoi dans les chapitres sur le processeurs, mais sachez que c'est lié au fait que les programmeurs utilisent beaucoup les tableaux, une structure de données qui regroupe des données dans des adresses consécutives. Les programmeurs parcourent ces tableaux dans le sens croissant/décroissant des adresses, c'est une opération très fréquente. Une autre raison est que les transferts entre RAM et mémoire cache se font par paquets de grande taille, environ 64 octets, voire plus, qui sont composés d'adresses consécutives. De ce fait, utiliser le code Gray pour encoder les adresses sur un bus mémoire est l'idéal.
Maintenant, cela demande d'ajouter des circuits pour convertir un nombre du binaire vers le code Gray et inversement. Et il faut que l'économie d'énergie liée au code Gray ne soit pas supprimée par l'énergie consommée par ces circuits. Heureusement, de tels circuits sont basés sur des portes XOR. Jugez plutôt. On voit que pour convertir un nombre du binaire vers le code Gray, il suffit de faire un XOR entre chaque bit et le suivant. Pour faire la conversion inverse, c'est la même chose, sauf qu'on fait un XOR entre le bit à convertir et le précédent.
| Circuit de conversion du binaire vers le code Gray. | Circuit de conversion du code Gray vers le binaire. |

### L'encodage à adressage séquentiel

Plus haut, on a dit que l'on peut profiter du fait que des accès mémoire consécutifs se font à des adresses consécutives. L'utilisation du code Gray est une première solution, mais il y a une autre solution équivalente. L'idée est d'ajouter un fil sur le bus mémoire, qui indique si l'adresse envoyée est la suivante. Le fil, nommé INC, indique qu'il faut incrémenter l'adresse envoyée juste avant sur le bus. Si on envoie l'adresse suivante, alors on met ce fil à 1, mais on n'envoie pas l'adresse suivante sur le bus mémoire. Si l'adresse envoyée est totalement différente, ce fil reste à 0 et l'adresse est effectivemen envoyée sur le bus mémoire. On parle de Sequential addressing ou encore de T0 codes.
La mémoire de l'autre côté du bus doit incorporer quelques circuits pour gérer un tel encodage. Premièrement, il faut stocker l'adresse reçue dans un registre à chaque accès mémoire. De plus, il faut aussi ajouter un circuit incrémenteur qui incrémente l'adresse si le fil INC est mis à 1. Le registre et l'incrémenteur sont placés juste entre le bus et le reste de la mémoire, il ne faut rien de plus, si ce n'est quelques multiplexeurs.

### Le codage à inversion de bus

Le codage à inversion de bus (bus inversion encoding, BIE) est un codage généraliste qui s'applique à tous les bus, pas seulement au bus mémoire. L'idée est que pour transmettre une donnée, on peut transmettre soit la donnée telle quelle, soit son complément obtenu en inversant tous les bits. Pour minimiser le nombre de bits qui changent entre deux données consécutives envoyées sur le bus, l'idée est de comparer quelle est le cas qui change le plus de bits.
Par exemple, imaginons que j'envoie la donnée 0000 1111 suivie de la donnée 1110 1000. Les deux données n'ont que deux bits de commun, 6 de différents. Par contre, si je prends le complément de 1110 1000, j'obtiens 0001 0111. Il y a maintenant 6 bits de commun et 2 de différents. Envoyer la donnée inversée est donc plus efficace : moins de bits sont à changer. Mais cela ne marche pas toujours : parfois, ne pas inverser la donnée est une meilleure idée. Par exemple, si j'envoie la donnée 0000 1111 suivie de la donnée 0001 1110, inverse les bits donnera un plus mauvais résultat.
Pour implémenter cette technique, le récepteur doit savoir si la donnée a été inversée avant d'être envoyée. Pour cela, on rajoute un fil/bit sur le bus qui indique si la donnée a été inversée ou non. Le bit associé, appelé le bit INV, vaut 1 pour une donnée inversée, 0 sinon.
L'implémentation de ce code est assez simple, du côté du récepteur : il suffit d'ajouter un inverseur commandable dans le récepteur, qui est commandé par le bit INV du bus. Et pour rappel, un inverseur commandable est un circuit qui fait un XOR avec le bit reçu.
Du côté de l'émetteur, il faut ajouter là aussi un inverseur commandable, mais sa commande est plus compliquée. Le circuit doit détecter s'il est rentable ou non d'inverser la donnée. Pour cela, il faut ajouter un registre pour contenir la donnée envoyé juste avant. La donnée à envoyer est comparé à ce registre, pour déterminer quels sont les bits différents, en faisant un XOR entre les deux. Le résultat passe ensuite dans un circuit qui détermine s'il vaut mieux inverser ou non, qui commande un inverseur commandable.
Déterminer s'il faut inverser ou non la donnée est assez simple. On détermine les bits différents avec une porte XOR. Puis, on les compte avec un circuit de population count. Si le résultat est supérieur à la moitié des bits, alors il est bénéfique d'inverser. En effet prenons deux entiers de taille N. S'il y a X bits de différence entre eux, alors si l'on inverse l'un des deux, on aura N-X bits de différents. Il est possible de remplacer le circuit de population count par un circuit de vote à majorité, qui détermine quel est le bit majoritaire. S'il y a plus de 1 dans le résultat du XOR, cela signifie que l'on a plus de bits différents que de bits identiques, on dépasse la moitié (et inversement si on a plus de 0).
Le cout en circuits de cette technique est relativement faible, mais elle est assez efficace. Elle permet des économies qui sont au maximum de 50%, soit une division par deux de la consommation électrique du bus. Elle est plus proche de 10% dans des cas réalistes, pour un cout en circuit proche de plusieurs centaines de portes logiques pour des entiers 32/64 bits. De plus, la technique réduit la consommation dynamique du bus, celle liée aux changements d'état du bus, il reste une consommation statique qui a lieu en permanence, même si les bits du bus restent identiques.
Des calculs théoriques, couplés à des observations empiriques, montrent que la technique marche assez bien pour les petits bus, de 8/16 bits. Mis pour des bus de 32/64 bits, la technique n'offre que peu d'avantages. Une solution est alors d'appliquer la méthode sur chaque octet du bus indépendamment des autres. Par exemple, pour un bus de 64 bits, on peut utiliser 8 signaux INV, un par octet. Ou encore, on peut l'utiliser pour des blocs de 16 bits, ce qui donne 4 signaux INV pour 64 bits, un par bloc de 16 bits. On parle alors de Partitioned inversion encoding. La technique marche bien pour les bus mémoire, car c'est surtout les octets de poids faible qui changent souvent.

## Les encodages sur les liaisons point à point asynchrones

Avant de passer à la suite, nous allons voir comment sont encodées les données sur les bus asynchrones. Les liaisons point à point asynchrones permettent à deux circuits/composants de se communiquer sans utiliser de signal d'horloge. L'absence de signal d'horloge fait qu'il faut trouver d'autres méthodes de synchronisation entre composants. Et les méthodes en question se basent sur l'ajout de plusieurs bits ACK et REQ sur le bus.
Dans ce qui suit, on se concentrera sur les liaisons point à point asynchrones unidirectionnelles, on avec un composant émetteur qui envoie des données/commandes à un récepteur. Pour se synchroniser, l’émetteur indique au récepteur qu'il lui a envoyé une donnée. Le récepteur réceptionne alors la donnée et indique qu'il a pris en compte les données envoyées. Cette synchronisation se fait grâce à des fils spécialisés du bus de commande, qui transmettent des bits particuliers.
Les liaisons asynchrones doivent résoudre deux problèmes : comment synchroniser émetteur et récepteur, comment transmettre les données. Les deux problèmes sont résolus de manière différentes. Le premier problème implique d'ajouter des fils au bus de commande, qui remplacent le signal d'horloge. Le second problème est résolu en jouant sur l'encodage des données. Voyons les deux problèmes séparément.

### La synchronisation des composants sur une liaison asynchrone

La synchronisation entre deux composants asynchrones utilise deux fils : REQ et ACK (des mots anglais request =demande et acknowledg(e)ment =accusé de réception). Le fil REQ indique au récepteur que l'émetteur lui a envoyé une donnée, tandis que le fil ACK indique que le récepteur a fini son travail et a accepté la donnée entrante.
Plus rarement, un seul fil est utilisé à la fois pour la requête et l'acquittement, ce qui limite le nombre de fils. Un 1 sur ce fil signifie qu'une requête est en attente (le second composant est occupé), tandis qu'un 0 indique que le second composant est libre. Ce fil est manipulé aussi bien par l'émetteur que par le récepteur. L'émetteur met ce fil à 1 pour envoyer une donnée, le récepteur le remet à 0 une fois qu'il est libre.
Si l'on utilise deux fils séparés, le codage des requêtes et acquittements peut se faire de plusieurs manières. Deux d'entre elles sont très utilisées et sont souvent introduites dans les cours sur les circuits asynchrones. Elles portent les noms de protocole à 4 phases et protocole à 2 phases. Elles ne sont cependant pas les seules et beaucoup de protocoles asynchrones utilisent des méthodes alternatives, mais ces deux méthodes sont très pédagogiques, d'où le fait qu'on les introduise ici.
Avec le protocole à 4 phases, les requêtes d'acquittement sont codées par un bit et/ou un front montant. Les signaux REQ/ACK sont mis à 1 en cas de requête/acquittement et repassent 0 s'il n'y en a pas. Le protocole assure que les deux signaux sont remis à zéro à la fin d'une transmission, ce qui est très important pour le fonctionnement du protocole. Lorsque l'émetteur envoie une donnée au récepteur, il fait passer le fil REQ de 0 à 1. Cela dit au récepteur : « attention, j'ai besoin que tu me fasses quelque chose ». Le récepteur réagit au front montant et/ou au bit REQ et fait ce qu'on lui a demandé. Une fois qu'il a terminé, il positionne le fil ACK à 1 histoire de dire : j'ai terminé ! les deux signaux reviennent ensuite à 0, avant de pouvoir démarrer une nouvelle transaction.
Avec le protocole à deux phases, tout changement des signaux REQ et ACK indique une nouvelle transmission, peu importe que le signal passe de 0 à 1 ou de 1 à 0. En clair, les signaux sont codés par des fronts montants et descendants, et non par le niveau des bits ou par un front unique. Il n'y a donc pas de retour à 0 des signaux REQ et ACK à la fin d'une transmission. Une transmission a lieu entre deux fronts de même nature, deux fronts montants ou deux fronts descendants.
Le tout est illustré ci-contre. On voit que le protocole à 4 phases demande 4 fronts pour une transmission : un front montant sur REQ pour le mettre à 1, un autre sur ACk pour indiquer l'acquittement, et deux fronts descendants pour remettre les deux signaux à 0. Avec le protocole à 2 phases, on n'a que deux fronts : deux fronts montants pour la première transmission, deux fronts descendants pour la suivante. D'où le nom des deux protocoles : 4 et 2 phases.

### La transmission des données sur une liaison asynchrone

La transmission des données/requêtes peut se faire de deux manières différentes, qui portent les noms de Bundled Encoding et de Multi-Rail Encoding. La première est la plus intuitive, car elle correspond à l'encodage des bits que nous utilisons depuis le début de ce cours, alors que la seconde est inédite à ce point du cours.
Le Bundled Encoding utilise un fil par bit de données à transmettre. De telles liaisons sont souvent utilisées dans les composants asynchrones, à savoir les processeurs, mémoires et autres circuits asynchrones. Les circuits asynchrones sont composés de sous-circuits séparés, qui communiquent avec des liaisons asynchrones, qui utilisent le Bundled Encoding. Les circuits construits ainsi sont souvent appelés des micro-pipelines.
Le Bundled Encoding a quelques défauts, le principal étant la sensibilité aux délais. Pour faire simple, la conception du circuit doit prendre en compte le temps de propagation dans les fils : il faut garantir que le signal REQ arrive au second circuit après les données, ce qui est loin d'être trivial. Pour éviter cela, d'autres circuits utilisent plusieurs fils pour coder un seul bit, ce qui donne un codage multiple-rails.
Le cas le plus simple utilise deux fils par bit, ce qui lui vaut le nom de codage dual-rail.
Il en existe plusieurs sous-types, qui différent selon ce qu'on envoie sur les deux fils qui codent un bit.
* Certains circuits asynchrones utilisent un signal REQ par bit, d'où la présence de deux fils par bit : un pour le bit de données, et l'autre pour le signal REQ.
* D'autres codent un bit de données sur deux bits, certaines valeurs indiquant un bit invalide.