Brevet FR2776787A1 — publié le 19991001

COMPARATEUR NUMÉRIQUE La présente invention concerne le domaine des comparateurs numériques et plus particulièrement un comparateur numérique utilisant un additionneur à anticipation de retenue (carrylookahead). De nombreux circuits électroniques utilisent des circuits de calcul numérique permettant notamment de comparer deux nombres A et B ayant le même nombre de bits. La figure 1 représente de manière très schématique la structure d'un comparateur complet classique, fournissant une indication d'égalité, de supériorité A > B et d'infériorité A Un premier bloc 11 reçoit sur une première entrée un opérande A, sur une deuxième entrée un opérande B, et produit un signal de sortie indiquant si A = B. Un deuxième bloc 12 reçoit sur deux entrées les opérandes A et B, effectue l'opération A-B et produit deux sorties, l'une correspondant à A Si A = B ou Si A > B. L'opération A - B correspondant, en codage binaire, à l'opération A + B + 1, le bloc 11 est classiquement un additionneur faisant la somme de A, de B et d'une retenue entrante égale à 1. Dans la description suivante, on désignera par Ai et Bi, i étant compris entre 1 et n, les n bits des opérandes A et B. La figure 2 représente un exemple de structure du bloc 11 de la figure 1. Une porte OU EXCLUSIF 21 reçoit sur une première entrée le bit A1 du premier opérande A et sur une deuxième entrée le bit B1 du deuxième opérande B. La sortie de la porte OU EXCLUSIF 21 sera à un niveau logique haut "1" en cas d'égalité entre les bits A1 et B1. n portes OU EXCLUSIF 21 permettent de déterminer ainsi, rang par rang, l'égalité ou l'inégalité des bits de même rang des premier et deuxième opérandes. Les sorties de ces portes OU EXCLUSIF sont connectées aux n entrées d'une porte ET 22. La sortie de la porte ET 22 sera à un niveau logique haut "1" en cas d'égalité bit à bit du premier et du deuxième opérande. Un objet de la présente invention est de réaliser un comparateur complet utilisant un nombre réduit de portes logiques. Cet objet ainsi que d'autres est atteint par un comparateur numérique qui comprend un premier bloc recevant sur des premières entrées les bits d'un premier opérande A de n bits et sur des deuxièmes entrées les inverses logiques des bits d'un deuxième opérande B de n bits, produisant un signal de propagation où Pi = Ai + Bi, et un signal de génération où Gi = Alibi, g1 = G1, qui comprend un deuxième bloc recevant sur une première entrée le bit de poids fort An du premier opérande, sur une deuxième entrée l'inverse logique B n du bit de poids fort Bn du second opérande, sur une troisième entrée le signal de propagation Pnl sur une quatrième entrée le signal de génération gn, produisant des signaux Cn et Sn+1 tels que Cn = ph + gn et Sn+l = (Pn + gn) $ An $ Bn où le signe $ représente l'opération OU EXCLUSIF et qui comprend également un troisième bloc recevant sur une première entrée le signal ph et sur une seconde entrée le signal gn, et produisant un signal E tel que E = Pn gn, indiquant par un état prédéterminé que les opérandes A et B sont égaux. Selon un autre aspect de la présente invention, les premier et deuxième blocs appartiennent tous deux à un additionneur à anticipation de retenue, le premier bloc faisant partie d'un bloc de l'additionneur servant à calculer tous les signaux de propagation Pi et tous les signaux de génération gi, où i est compris entre 1 et n, et le deuxième bloc faisant partie d'un bloc de l'additionneur servant à calculer tous les signaux de somme Si, où i est compris entre 1 et n+l, et le signal Cn de retenue sortante, un signal de retenue entrante du deuxième bloc étant fixé à 1. Ces objets, caractéristiques et avantages, ainsi que d'autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles la figure 1 représente très schématiquement la structure d'un comparateur numérique complet la figure 2 représente très schématiquement la structure d'un comparateur fournissant une information d'égalité la figure 3 représente très schématiquement la structure d'un additionneur à anticipation de retenue la figure 4 représente une première partie d'un additionneur à anticipation de retenue la figure 5 représente une deuxième partie d'un additionneur à anticipation de retenue la figure 6 représente schématiquement un comparateur selon la présente invention ; et la figure 7 représente schématiquement un comparateur selon la présente invention. Un comparateur est, comme on l'a vu, classiquement réalisé au moyen d'un additionneur calculant A + B + 1. La présente invention prévoit d'utiliser un additionneur à anticipation de retenue pour réaliser un comparateur fournissant une indication d'égalité de structure particulièrement simple. Un additionneur à anticipation de retenue présente de nombreux avantages, en particulier en ce qui concerne la rapidité de fonctionnement. La figure 3 représente une vue très schématique d'un additionneur à anticipation de retenue. L'additionneur 31 reçoit ici les signaux lui permettant de calculer A + B + 1 = S. L'additionneur 31 reçoit sur une première entrée de n bits les n bits du premier opérande A et sur une deuxième entrée de n bits les inverses logiques des n bits du deuxième opérande B. Un premier bloc 32 calcule selon la méthode d'anticipation de retenue, n signaux de génération g1 à gn tels que où Gi = AiBi k étant compris entre 2 et n, avec g1 = G1 ; et n signaux de propagation ph tels que où Pi = Ai + B i k étant compris entre 1 et n. Un deuxième bloc 33, selon la méthode d'anticipation de retenue, reçoit sur une première entrée les n signaux de propagation, sur une deuxième entrée les n signaux de génération, sur une troisième entrée le premier opérande A, sur une quatrième entrée l'inverse logique du deuxième opérande B et sur une cinquième entrée un bit de retenue entrante que l'on fixe ici à 1 afin d'effectuer l'opération A + B + 1. Les quatre premières entrées du bloc 33 sont des entrées à n bits. Les sorties S et Cn correspondent respectivement au résultat sur n bits et à la retenue sortante de cette opération. I1 existe plusieurs architectures différentes des blocs 32 et 33. La figure 4 représente schématiquement une architecture classique du bloc 32. Une porte ET 41 reçoit sur une première entrée un signal A1 correspondant au bit de poids faible du premier opérande A et sur une seconde entrée un signal B1 correspondant à l'inverse logique du bit de poids faible du deuxième opérande B. La porte ET 41 produit un signal G1 qui est aussi égal au signal de génération de poids faible g1. Une porte OU 42 reçoit sur une première entrée le signal A1 et sur une seconde entrée le signal B1. La porte OU 42 produit un signal P1 qui est aussi égal au bit de poids faible du signal de propagation pi. Un bloc 43 comprend une porte ET 44 et une porte OU 45 qui reçoivent toutes deux un signal A2 correspondant au deuxième bit de poids faible A2 du premier opérande A et un signal B 2 correspondant à l'inverse logique du deuxième bit de poids faible du deuxième opérande B, et produisent respectivement des signaux intermédiaires G2 et P2. Le bloc 43 comprend également une porte ET 46 recevant sur une première entrée le signal intermédiaire P2 et sur une deuxième entrée le signal de génération de rang inférieur g1, et une porte OU 47 recevant sur une première entrée la sortie de la porte ET 46 et sur une deuxième entrée le signal intermédiaire G2. La sortie de la porte OU 47 correspond au signal de génération g2. Le bloc 43 comprend enfin une porte ET 48 dont une première entrée reçoit le signal intermédiaire P2 et une deuxième entrée reçoit le signal de propagation de rang inférieur Pi La sortie de la porte ET 48 correspond au signal de propagation P2. Les signaux de génération g de rangs 3 à n, ainsi que les signaux de propagation p de rangs 3 à n sont produits par des blocs 43 correspondants. On a représenté en figure 5 une architecture classique du bloc 33 de la figure 3. Une porte OU EXCLUSIF 51 reçoit sur une première entrée le signal de retenue entrante C0, sur une deuxième entrée le bit A1 de rang 1 de l'opérande A et sur une deuxième entrée l'inverse logique B1 du bit de rang 1 de l'opérande B. La porte OU EXCLUSIF 51 produit le bit S1 de rang 1 de la somme S. Une porte ET 52 reçoit sur une première entrée le signal de retenue entrante C0 et sur une deuxième entrée le signal de propagation de rang 1, pl. La sortie de la porte ET 52 est connectée à une première entrée d'une porte OU 53. Une deuxième entrée de la porte OU 53 reçoit le signal de génération gl, et la sortie de la porte OU 53 correspond au signal de retenue C1. Le bit S2 de la somme S est produit par une porte OU EXCLUSIF recevant sur une première entrée le signal de retenue de rang inférieur C1, sur une deuxième entrée le bit A2 du premier opérande et sur une troisième entrée l'inverse logique B2 du bit de rang 2 de l'opérande B. Les signaux C de rangs 2 à n et les bits S de rangs 3 à n sont obtenus de façon similaire par des portes 51, 52 et 53 correspondantes. On a de manière générale Ck = PkCO + gk avec Cg = 1, soit Ck = pk + gk et Sk = Ck-l $ Ak + Bk, ou k est compris entre 1 et n. On a vu précédemment que le bloc 12 de la figure 1 permet de déterminer si le premier opérande A est inférieur ou supérieur-ou-égal au deuxième opérande B. L'additionneur 31 représenté en figure 3 réalise l'opération A - B mais seul le signe du résultat S de cette opération est nécessaire pour déterminer si le premier opérande A est inférieur ou supérieur-ou-égal au deuxième opérande B. Ce résultat est déterminé de deux manières différentes selon que les opérandes A et B sont des nombres binaires signés ou non signés. S'ils sont signés, le résultat est négatif (A est inférieur à B) si le bit 5n de rang n de S est à "1" (Sn est le bit de signe du résultat). On remarquera que pour obtenir un résultat signé sur n bits, on doit additionner deux opérandes de n-l bits maximum. De manière classique, les bits An et Bn seront alors par extension de signe les mêmes que An~1 et Bn~1 respectivement. On a 5n = Con 1 $ An + Bn, mais on peut aussi dans ce cas écrire que 5n = Cn-1 + An-1 + B n-1 Si A et B sont des opérandes de n bits, on devra calculer Sn+1 = Cn + An O Bn. Si les opérandes A et B sont des nombres binaires de n bits non signés, le résultat est négatif (A est inférieur à B) si la retenue sortante Cn est à "O". Ainsi, pour des opérandes de n bits signés ou non, la structure de l'additionneur peut être réduite uniquement aux éléments qui permettent de calculer les signaux Sn+1 et Cn. La présente invention permet de fournir, à partir de cette structure réduite, une indication d'égalité avec peu d'éléments supplémentaires. La figure 6 représente de manière très schématique un comparateur selon la présente invention. Le bloc 32 correspond à celui de la figure 3 mais seules les sorties ph et gn, correspondant aux signaux de propagation et de génération de rang n, sont utilisées. Le bloc 32 reçoit sur une première entrée à n bits le premier opérande A et sur une deuxième entrée à n bits l'inverse logique du deuxième opérande B. Un bloc 63 reçoit sur une première entrée le signal An de rang n du premier opérande A, sur une deuxième entrée l'in- verse logique B n du signal de rang n du deuxième opérande B, sur une troisième entrée le signal de propagation de rang n, ph, et sur une quatrième entrée le signal de génération de rang n, gn. Le bloc 63 comprend la porte OU 55 du bloc 33 de la figure 5 permettant de générer la retenue Cn = pn + gn, et une porte OU EXCLUSIF 64 permettant de générer le signal 5n+l dans le cas décrit précédemment où Sn+1 = Cn An $ Bn. On a vu que les signaux Sn+1 et Cn produits par le bloc 63 suffisent à déterminer si l'opérande A est inférieur ou supérieur-ou-égal à l'opérande B, selon que A et B sont signés ou non. On se reporte maintenant aux équations permettant de calculer le signal de propagation ph, soit avec Pi = Ai + Bi. On remarque que si l'opérande A est égal à l'opérande B, c'est-à-dire que, quel que soit i compris entre 1 et n, Ai = Bi, alors le signal Pi sera toujours égal à 1. En effet, si Ai = 0, alors Bi sera égal à 1 et inversement. Ainsi, si le premier opérande est égal au deuxième opérande, le signal ph est égal à 1. Cependant, il existe des cas de figures dans lesquels le signal ph est égal à 1 sans que l'opérande A soit égal à l'opérande B. Par exemple, si Ai = 1 et Bi = 0, alors Pi = 1 et Pn = 1. De même, on a où Gi = Alibi On remarque que si Ai = Bi quel que soit i, alors le signal Gi est nul. En effet, si Ai = 1 alors Bi = O et Gi = O et inversement. Ainsi, le signal gn est nul si les deux opérandes A et B sont égaux bit à bit. Là encore, on peut trouver des cas de figures dans lesquels gn est nul sans que les opérandes soient égaux bit à bit. Par exemple, si Ai = O et Bi = 1, alors Gi = 0 et gn = 0. Cependant il n'existe pas de cas de figure dans lequel Pn est égal à 1, gn est nul, et les deux opérandes ne sont pas égaux bit à bit. Ainsi, il suffit de vérifier que pn.gn = 1 pour garantir que A est égal bit à bit à B. On a représenté en figure 6 deux éléments logiques permettant d'effectuer ce calcul. Un inverseur 61 reçoit en entrée gn La sortie de l'inverseur 61 est connectée à une première entrée d'une porte ET 62 dont une deuxième entrée reçoit le signal ph. La sortie E de la porte ET 62 sera à 1 si le premier opérande A est égal au premier opérande B, et à 0 dans le cas contraire. Les composants 61 et 62 forment un bloc 64. Le bloc 64 a la même fonction que le bloc 21 de la figure 2 et utilise un nombre extrêmement réduit de composants. La présente invention est bien sûr susceptible de nombreuses variantes et modifications qui apparaîtront à l'homme de l'art. En particulier il existe de nombreuses structures permettant le calcul du signal de génération de rang n, gn, et du signal de propagation de rang n, ph, et toutes pourront être utilisées selon la présente invention. De même, on a décrit en figure 6 la présente invention adaptée à un bloc 63 spécialement optimisé pour comparer les opérandes A et B, mais on comprendra aisément que l'on peut adapter la présente invention à un additionneur à anticipation de retenue classique carme en figure 7. La figure 7 représente une adaptation de l'additionneur 31 de la figure 3, qui peut à la fois effectuer des opérations classiques d'addition et de soustraction, mais aussi des opérations de comparaison telles que celle décrite en relation avec la figure 6. Un bloc 72 a la même fonction que le bloc 32 des figures 3 et 6, un bloc 73 correspond au bloc 33 de la figure 3 auquel on a intégré le bloc 63 de la figure 6, et le bloc 64 a la même fonction en figures 7 et 6. Le dispositif représenté en figure 7 permet de réaliser les mêmes fonctions que les blocs 11 et 12 de la figure 1, tout en occupant une surface très inférieure. REVENDICATIONS 1. Comparateur numerique comprenant un premier bloc (32) recevant sur des premières entrées les bits d'un premier opérande A de n bits et sur des deuxièmes entrées les inverses logiques des bits d'un deuxième opérande B de n bits, et produisant un signal de propagation où Pi = Ai + Bi, et un signal de génération où Gi = Ai Bi, g1 = G1 et un deuxième bloc (63) recevant sur une première entrée le bit de poids fort An du premier opérande, sur une deuxième entrée l'inverse logique B n du bit de poids fort Bn du second opérande, sur une troisième entrée le signal de propagation P,, sur une quatrième entrée le signal de génération gn, et produisant des signaux Cn et Sn+i tels que Cn = Ph + gn et Sn+l = (Pn + gn) $ An + Bn où le signe $ représente l'opération OU EXCLUSIF caractérisé en ce qu'il comprend un troisième bloc (65) recevant sur une première entrée le signal ph et sur une seconde entrée le signal gn, et produisant un signal E tel que E = pn g n, indiquant par un état prédéterminé que les opérandes A et B sont égaux. 2. Comparateur numérique selon la revendication 1, caractérisé en ce que les premier et deuxième blocs appartiennent tous deux à un additionneur à anticipation de retenue (71), le premier bloc faisant partie d'un bloc (72) de l'additionneur servant à calculer tous les signaux de propagation Pi et tous les signaux de génération gi, où i est compris entre 1 et n, et le deuxième bloc (63) faisant partie d'un bloc (73) de l'additionneur servant à calculer tous les signaux de somme Si, où i est compris entre 1 et n+l, et le signal Cn de retenue sortante, un signal de retenue entrante du deuxième bloc étant fixé à 1.