====== Circuit additionneur ======

Dans ce travail, nous voulons réaliser un circuit logique n'utilisant que des circuits élémentaires ET, OU et NON, et permettant de réaliser la somme de deux nombres. Ainsi vous verrez de simples circuits logiques -- qui ne sont eux-mêmes que des assemblages de transistors fonctionnant comme des interrupteurs -- permettent de faire des calculs.

<WRAP tip>Il pourra être avantageux d'utiliser des circuits OU-EXCLUSIF, XOR qui permettent de grandement réduire la complexité de l'ensemble du circuit. La règle est simple : **a XOR b est vrai si et seulement si les booléens a et b ont une valeur différente**.</WRAP>

===== Mise en place =====

Les deux nombres que nous allons additionner sont A et B. Dans la machines ils sont stockés sous forme de mots binaires. Ainsi, A, dans un cas réel, sera typiquement un entier sous forme binaire de 32 bits.

Pour ne pas trop surcharger le circuit que nous voulons réaliser, nous nous contenterons de **mots binaires de 4 bits**.

On pourra alors noter $A_3A_2A_1A_0$ ce mot binaire. $A_3$ est le MSB -- //Most Significant Bit// = Bit de poids fort -- et $A_0$ est le LSB -- //Less Significant Bit// = Bit de poids faible. De la même façon on pourra noter $B_3B_2B_1B_0$.

Le résultat S = A + B sera aussi un mot 4 bits $S_3S_2S_1S_0$.

<WRAP tip>Si A et B sont tous les deux assez grands, la somme A + B sera trop grande pour être contenus sur les 4 bits de S. On peut prévoir un booléen //Overflow// qui passe à 1 si A + B est trop grand. Par exemple si $A = 14 = 1110_b$ et $B = 7 = 0111_b$, alors $S = A + B = 21 = 10101_b$ ce qui dépasse les 4 bits disponibles pour S.</WRAP>

===== Approche naïve =====

Pour réaliser un circuit logique, on peut toujours remplir un tableau de vérité : Il suffit de lister toutes les configurations possibles de A et B et pour chacune de déterminer la valeur de S. Voici ce que cela donnerait :

^ A3 ^ A2 ^ A1 ^ A0 ^ B3 ^ B2 ^ B1 ^ B0 ^ S3 ^ S2 ^ S1 ^ S0 ^ Ov ^
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
| 0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  | 1  | 0  |
| 0  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0  | 0  | 1  | 0  | 0  |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 0  | 1  | 1  | 0  | 0  | 0  | 1  | 1  | 1  | 0  | 0  | 1  | 0  |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 1  | 1  | 1  | 0  | 0  | 1  | 1  | 1  | 0  | 1  | 0  | 1  | 1 |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 0  | 1 |

Réaliser ce tableau et en déduire le circuit logique adapté est possible, mais :

  * Le tableau aura $2^8 = 256$ lignes, c'est beaucoup...
  * Le circuit serait inutilement compliqué, bien qu'il soit possible de faire des simplifications automatiquement.
  * Si on voulait passer à des entiers un peu plus grand, par exemple 5 bits ou 6 bits, il faudrait refaire totalement un nouveau tableau.

On préfère une autre méthode.

===== Additionneurs 1 bit =====

On réalise des circuits permettant d'additionner 1 bit à 1 bit et de propager l'éventuelle retenue :

  * un premier de ces circuits calcule $A_0 + B_0 = S_0$ et produit également une retenue $r_0$,
  * un deuxième de ces circuits calcule $r_0 + A_1 + B_1 = S_1$ et produit également une retenue $r_1$,
  * etc jusqu'à $S_3$

Cette approche a de grands avantages :
  * chacun des petits additionneurs 1 bits sera simple à concevoir et à réaliser,
  * il suffira d'assembler autant de ces circuits que nécessaire pour réaliser l'additionneur complet,
  * passer d'un additionneur 4 bits à un additionneur 6 bits ou plus ne pose aucune difficulté.

<WRAP tip>Cette méthode correspond à ce que l'on fait quand on pose une addition en colonnes et que l'on propage les retenues depuis la droite vers la gauche.</WRAP>

==== Table de vérité de l'additionneur 1 bit ====

Comme dans une addition en colonne, on considère une certaine colonne $i$. On additionne le bit de A pour cette colonne, $A_i$, et le bit de B, $B_i$. Il faut aussi ajouter la retenue de la colonne précédente : $r_{i-1}$.

Cette addition permet de déterminer le bit de S pour cette colonne, $S_i$, ainsi que la retenue à propager, $r_i$.

| $A_i$ | $B_i$ | $r_{i-1}$ ^ $S_i$ ^ $r_i$ ^
| 0     | 0     | 0         |       |       |
| 0     | 0     | 1         |       |       |
| 0     | 1     | 0         |       |       |
| 0     | 1     | 1         |       |       |
| 1     | 0     | 0         |       |       |
| 1     | 0     | 1         |       |       |
| 1     | 1     | 0         |       |       |
| 1     | 1     | 1         |       |       |


==== À faire ====

Dans logisim,

  - Menu //Window//, commande //Combitional Analysis//
  - Dans la fenêtre qui s'ouvre,
    - Dans //Inputs//, ajoutez Ai, Bi, rp  -- //rp pour retenue précédente//
    - Dans //Outputs//, ajoutez Si, Ri
    - Dans //Table//, complétez la table de vérité en cliquant sur les croix de façon à faire apparaître les valeurs voulues
    - Cliquez //Build Circuit//
    - Choisissez le nom //ADD1//
    - Fermez la fenêtre //Combitional Analysis//

Vous découvrez un circuit généré automatiquement et réalisant la table de vérité demandée.

<WRAP tip>Ce circuit est un peu volumineux mais ce n'est pas grand chose au regard de ce qui est possible aujourd'hui. On préfère le réaliser en utilisant des circuits XOR qui simplifient grandement la structure.</WRAP>

Vous avez réaliser un nouveau circuit élémentaire ADD1 possédant 3 entrées et 2 sorties. Pour l'instant vous êtes à l'intérieur de ce circuit. Sortez-en en double-cliquant sur //main// en haut à gauche de la fenêtre.

===== Additionneur 4 bits =====

ADD1 est un nouveau circuit que vous pouvez ajouter dans le circuit principal. Vous pouvez même l'ajouter en plusieurs exemplaires.

<WRAP info>Quand on ajoute ADD1, on voit clairement 3 entrées et 2 sorties mais on ne sait pas qui est qui. Vous pouvez passer le curseur au-dessus de ces entrées / sorties, vous verrez apparaître le nom. Elles sont normalement dans l'ordre où vous les avez ajoutées dans les onglets //Inputs// et //Outputs// de la partie précédente.</WRAP>

==== À faire ====

Vous êtes dans //main//, restez-y.

  - Ajoutez 4 entrées -- //bouton vert carré à côté du A tout en haut à gauche de la fenêtre//. À chaque fois, changez le //label// pour les nommer : A3, A2, A1, A0.
  - Faites de même pour B.
  - Ajoutez 4 sorties -- // bouton vert rond//. Nommez-les S3, S2...
  - Ajoutez encore 1 sortie pour //Overflow//
  - Ajoutez 4 circuits additionneurs //ADD1//

Avant de vous lancer dans le branchement du tout, il reste une petite chose à ajouter : Dans le calcul $S_0 = A_0 + B_0$ il n'y a pas de retenue $r_{-1}$. Il faut donc mettre à 0 l'entrée //rp// du tout premier //ADD1//. Pour cela, dans la bibliothèque de composants : //Wiring// -> //Constant//. Réglez sa valeur à 0 et branchez cette constante comme entrée //rp// du premier //ADD1//

**À vous de terminer le branchement !**

==== Tester ====

Quand vous avez terminé, n'oubliez pas de tester. Pour cela :

  - Utilisez l'outil en forme de main -- //en haut à gauche//
  - Choisissez des valeurs pour A et B,
  - En cliquant sur les boutons A3, A2... réglez les valeurs de A et B en binaire,
  - Vérifiez que la valeur binaire de S -- écrite en binaire sur S3, S2, S1, S0 -- est bien égale à A + B
  - Vérifiez que dans le cas où S est trop grand -- les cas ou S > 15 -- Overflow est à 1.