Notion de chemin critique : unité arithmétique et logique (ALU)

On appelle chemin critique, tout chemin qui va d'une entrée à une sortie et qui traverse le plus grand nombre possible de portes logiques. La longueur d'un tel chemin détermine le temps de calcul du circuit dans le pire des cas. La longueur d'un chemin critique est aussi appelée épaisseur.

On appelle semi additioneur un circuit qui prend deux entrées $X$ et $Y$ et dont les sorties nommées somme ($S$) et retenue ($R$) codent la somme des deux entiers binaires $X$ et $Y$.

• Donner les expressions de $S$ et $R$ ainsi que le circuit logique d'un semi additionneur.
On appelle additioneur complet un circuit qui prend trois entrées $X$, $Y$ et $Z$ dont les sorties nommées somme $S$ et retenue $R$ codent la somme des trois entiers binaires $X$, $Y$ et $Z$.
• Donner les expressions de $S$ et $R$ ainsi que le circuit logique d'un additionneur.
• Expliquer comment à l'aide de $n$ additionneurs on peut réaliser un additioneur $n$ bits, c'est à dire un circuit ayant en entrée
  • $n$ entrées $A_{n-1},$...$,A_{0}$ (représentant un nombre binaire $A$);
  • $n$ entrées $B_{n-1},$...$,B_{0}$ (représentant un nombre binaire $B$);
  • une entrée $R_0$.
Les sorties $R_n,S_{n-1},$...$,S_{0}$ codent la somme binaire des nombres $A$, $B$ et $R_0$.
• Calculer la longueur d'un chemin critique de l'additionneur.
• Peut-on réaliser simplemenent un circuit qui fasse à la fois additionneur et soustracteur ?

Le cicuit obtenu précédemment est lent. Pour comprendre comment faire mieux, nous allons d'abord travailler sur un circuit plus simple, l'incrémenteur. Ce circuit comporte $n$ entrées $A_{n-1},\ldots,A_{0}$ qui représente un nombre $A$ en binaire et donne en sortie $S_{n-1}\ldots,S_{0}$ représente le nombre $S=A+1$.

• Réaliser un incrémenteur $1$ bit.
• Construire un incrémenteur $n$ bits à l'aide d'un incrémenteur $1$ bit et de semi additionneurs.
• Est-il possible de calculer la valeur de $S_i$ sans avoir calculé celle de $S_{i-1}$ ? Ecrire le circuit correspondant.
• Comparer les longueurs des chemins critiques pour les deux incrémenteurs.

On applique à l'additionneur la même optimisation que celle de l'incrémenteur. On distingue deux cas, selon les valeurs de $A_i$ et $B_i$:

1. s'ils sont tous deux à $1$, une retenue est générée;
2. si l'un des deux est à $1$, la retenue $R_i$ est propagée vers $R_{i+1}$.
Ces deux possibilités sont codées par des valeurs, appelées respectivement $G_i$ et $P_i$. Ces valeurs ainsi que $S_i$ sont les sorties d'un circuit nommé additionneur partiel.
3. Donner le diagramme logique d'un additioneur partiel.
4. Donner en fonction de $R_0$, des $G_i$ et des $P_i$, la valeur de $S_i$ et de $R_i$.
5. Construire un additionneur complet $n$ bits avec des additioneurs partiels.
6. Quelle est la longueur d'un chemin critique ?
7. Comparer avec l'additionneur à propagation de retenue.
8. Commenter la structure du circuit logique sous-jacent.

$G_{i,k}$ est la retenue éventuelle générée par les bits $i,\ldots,k$.
$P_{i,k}$ indique qu'une retenue se propage ou non à travers les bits $i,\ldots,k$.

• Exprimer $P_{0,3}$ et $G_{0,3}$ en fonction des $P_i$ et des $G_i$.
• Trouver les relations entre $S_{k+1}$, $R_{k+1}$, les $G_{i,k}$ et les $P_{i,k}$.
• En déduire un circuit de forme \emph{régulière} réalisant l'anticipation de retenue.

• Construire un circuit utilisant seulement le calcul des $P_{i,k}$.
• Calculer le nombre d'unités de temps nécessaires pour calculer une addition de 20 bits si l'additionneur se compose de cinq blocs de 4 bits.
• Peut-on améliorer ce résultat avec d'autres tailles de blocs ?

On construit un additionneur 16 bits à l'aide de quatre additionneurs 4 bits à propagation de retenue en dédoublant chaque bloc (à part le premier) de sorte que l'un des blocs calcule avec une retenue $1$ en entrée et l'autre avec une retenue $0$.

• Construire le circuit utilisant ce principe.
• Commenter les avantages et inconvénients de cet additionneur par rapport aux additionneurs décrits précédemment.