Extracteurs de racine rapides

Extracteur de racine carrée rapide

On cherche à s'affranchir de la propagation de retenue en utilisant la notation "BS", les mêmes cellules "head" et "tail" et une architecture similaire à celle de la division rapide SRT. On se heurte à trois difficultés en cherchant à utiliser ce diviseur pour extraire des racines.

Convertisseur de racine

La première difficulté est le rebouclage de la racine. Comme le diviseur, l'extracteur de racine carrée rapide fourni des racines partielles Qj en notation "BS". Utiliser les cellules "head" et "tail" du diviseur rapide exige une racine partielle en notation binaire conventionnelle. On pourrait utiliser un soustracteur pour la conversion de "BS" à binaire de chaque Qj mais ce serait coûteux en temps et en circuit et ne tirerait pas partie du fait que les qj en "BS" sont calculés séquentiellement. Le convertisseur ci-dessous utilise une cellule "trc" à 4 entrées et 2 sorties dérivées de la cellule "BK". Pour n entrées, il donne n(n+1)/2 bits à reboucler.

Ce circuit a un autre intérêt : il fourni l'entrée Q (la racine) convertie de "BS" en binaire. Il fourni en plus une sortie Qm = Q0  1. Si le reste final R de l'extraction de racine sans propagation de retenue est négatif, c'est que le Q calculé est trop grand (de 1) et Qm est la bonne valeur de la racine. Dans le cas contraire, Q0 donne la valeur de la racine.

Cellule du convertisseur de racine

Vérifiez que vous maîtrisez les fonctions logiques de la cellule "trc" de conversion "à la volée" de notation "BS" vers notation binaire conventionnelle.
L'entrée "si" est un bit du Qj+1, la sortie "so" est le bit de même poids de Qj, l'entrée "ci" indique que la retenue se propage jusqu'à la position de cette cellule dans Qj+1 et naturellement la sortie "co" que la retenue se propage jusqu'à la position de cette cellule dans Qj . La propagation est utilisée pour la soustraction de 1. Elle correspond au 'P' de la cellule"BK".

  • si q = '-1' alors { so = si Å ci ; co = 0} //soustraction (somme retenue), retenue tuée
  • si q = '0' alors { so = si ; co = ci } //somme inchangée, retenue propagée
  • si q = '1' alors { so = si ; co = 0 } //somme inchangée, retenue tuée

Extracteur de racine carrée sans propagation de retenue

L'extracteur rapide utilise les mêmes cellules que le diviseur rapide pour effectuer à chaque itération une des opérations arithmétiques :

  • si qj-1 = '-1' alors R2j-2 = R2j + 2j * Qj 22j-1 // addition
  • si qj-1 = '0' alors R2j-2 = R2j // identité
  • si qj-1 = '1' alors R2j-2 = R2j 2j * Qj 22j-1 //soustraction

La deuxième difficulté par rapport à la division est dans la soustraction de 22j-1 quand qj = '-1' ou qj = '1'. Ce cas est détecté par une porte "ou" dont la sortie est relié à l'entrée négative de la cellule "tail" en poids faible de chaque ligne.
Ramené à des entiers, une ligne calcule S = 4 * R + A qj-1 * ( 4 * Qj + qj-1 )
ou encore S = ( R & a1 & a0 ) qj-1* ( Qj & '0' & qj-1 ), "&" désignant la concaténation.

  Chaque "head" détermine un qj grâce au signe d'un approximant 2j du reste courant R2j.
La troisième difficulté limite en fait le domaine d'utilisation. En effet tous les Qj doivent commencer par un '1' en poids fort (implicite). Cette condition n'est pas réalisée si les deux premiers bits du radicande A sont nuls tous les deux, en d'autres termes A doit être "normalisé" pour que l'extracteur fonctionne. On soustrait ce '1' de A à la première ligne grâce à une entrée négative de "head".
  La racine Q sort à gauche en notation "BS" et sort en bas convertie en binaire conventionnel.

Diviseur et extracteur de racine carrée

Le même circuit peut exécuter soit la division soit l'extraction de racine carrée grâce à des multiplexeurs "2 Þ 1" insérés sur les entrées de certaines cellules "tail". Les deux flèches marquées "vue" recadrent les poids des bits pour normaliser ou bien permutent les connexions des entrées d'environ la moitié des cellules "tail" et permutent ainsi la fonction réalisée.
Pour clarifier le dessin le convertisseur n'est pas dessiné pour la division. Il est cependant toujours connecté à Q et fourni en sortie un quotient ou une racine en binaire conventionnel.