Brevet FR2568034A1 — publié le 19860124

L'invention concerne des multiplicateurs numériques, et en particulier des multiplicateurs qui sont particulièrement adaptés pour l'intégration à grande échelle en circuits intégrés. Beaucoup d'opérations nécessaires au traite- ment du signal ou de l'image, telles que corrélation, convoi ution et filtrage, ne sont pas réalisées au -mieux sur un ordinateur d'architecture conventionnelle. L'exigence de base pour ces opérations est l'aptitude à multiplier ensemble des flux de paires de nombres et à accumuler un total. En représentation binaire,-des nombres ayant une longueur de mot de 32 bits ont une précision suffisante pour les opérations de traite- ment du signal présentes et futures, tandis que l'usage des produits à 64 bits minimisera les erreurs d'arrondi dans le processus cumulatif. La raison de l'inefficacité dans l'exécution des algorithmes des opérations de traitement du'signal mentionnées ci-dessus provient des allers et retours répétés d'un même élément de données entre une mémoire et un processeur. Une approche très intéressante pour le traitement de flux continus de données est l'utili- sation d'une matrice contractée d'éléments de traite- ment. Une telle matrice contractée est utilisée comme processeur particulier annexé à un ordinateur hôte d'usage-général, laissant ainsi l'ordinateur hâte disponible pour exécuter ses fonctions plus générales. Il est évident qu'un tel processeur particu- lier doit être capable de fournir les résultats de ses opérations de traitement à son ordinateur hôte à une vitesse compatible avec le flux entrant de données. Ceci est accompli par l'approche à matrice contractée en faisant l'usage maximum de combinaisons séries/ parallèles, et en faisant plein usage de chaque élé- ment de données à son passage dans une certaine configuration d'éléments processeurs relativement sim- ples et connectés localement. Dans le cas des opérations de traitement du signal mentionnées ci-dessus, la fonction de base de chaque élément processeur identique est de multiplier ensemble des paires de nombres (dont la longueur de mot est suffisamment grande pour donner un niveau acceptable de précision), et de cumuler les sommes des produits. Les matrices contractées connues demandent un réseau de cellules multiplicatrices identiques, chacune d'entre elles multipliant un bit de chacun des nombres à multiplier ensemble. La demande de brevet britannique 2 106 278 A, par exemple, décrit une dis- position impliquant une matrice rectangulaire de cellules, chacune d'entre elles étant connectée à chaque cellule adjacente dans le réseau. Cependant, dans une telle matrice, le nombre de cellules du réseau augmente comme le carré du nombre de bits dans chaque nombre à multiplier. Par conséquent, pour les longueurs de mots habituelles, le nombre de cellules peut devenir très grand. Ceci est d'importance en particulier parce que l'opération la plus rapide serait obtenue avec un multiplicateur contenu sur une seule puce de silicium, car les connexions entre puces introduisent des retards. C'est donc- l'un des objets de l'invention, que de proposer un multiplicateur numérique du type "série" dans lequel le nombre de cellules multiplica- trices n'augmente qu'en fonction linéaire de la taille des nombres N multiplier. Selon l'invention, on propose un multiplicateur numérique pour multiplier ensemble deux nombres binai- res, comprenant un réseau linéaire de cellules de traitement au niveau du bit, chacune incluant deux connexions d'entrée auxquelles sont appliqués respec- tivement les bits successifs de chacun des deux nombres binaires, deux connexions de sortie connectées 'à la cellule adjacente suivante et auxquelles sont appliqués les bits successifs, des moyens de multiplication qui agissent pour multiplier ensemble un bit de chacun des nombres, et des moyens d'addition qui agissent pour ajouter ensemble et mettre en mémoire les résultats des multiplications successives exécutées dans la cellule. Le nombre de cellules dans le réseau linéaire est de préférence égal à la somme des nombres de bits dans les deux nombres à multiplier. On va maintenant décrire l'invention en fai- sant référence aux dessins joints, dans lesquels: la figure 1 est un diagramme logique d'une cellule de traitement de bit selon un premier mode de réalisation de l'invention; la figure 2 est un diagramme schématique montrant l'interconnexion d'une matrice simple de cellules de traitement de bit de la figure 1 pour former un multiplicateur numérique; la figure 3 illustre le fonctionnement du multiplicateur numérique de la figure 2; 25. la figure 4 est un diagramme logique d'une cellule de traitement de bit selon un second mode de réalisation de l'invention; la figure 5 illustre le fonctionnement d'un multiplicateur comprenant un réseau de cellules de traitement de bit de la figure 4; la figure 6 montre un exemple du fonction- nement du multiplicateur de la figure 4; et la figure 7 montre un organigramme d'un appareil de traitement de signal comprenant un certain nombre de multiplicateurs numériques. En se référant à la figure 1, on voit une forme de cellule de traitement de bit selon l'inven- tion. La cellule représentée doit être utilisée pour multiplier ensemble deux nombres "a" et "b", et les flux de données des deux nombres arrivent en direc- tions opposées. La cellule représentée possède trois entrées de données marquées Ia, lb et Ic, cette der- nière étant faite pour les bits de "retenue" engendrés par la cellule précédente du réseau. Chacune de ces entrées est connectée à une bascule bistable à transi- tion déclenchée, séparée, marquée L1, L2 ou L3. Sur chaque bascule arrive aussi un signal impulsionnel d'horloge CK. La sortie de la bascule L1 constitue la sortie des données "a" vers la cellule suivante la plus proche à droite par l'intermédiaire de la connexion de sortie Oa, et est aussi connectée à une entrée d'une porte ET à double entrée, G. La sortie de la bascule L2 est connectée à l'autre entrée de la porte G, et constitue aussi la sortie des données "b" vers la cellule suivante la plus proche à gauche par l'intermédiaire de la connexion de sortie Ob. La sortie de la porte ET G est reliée à un circuit additionneur AD, ainsi que la sortie de la bascule L3. Une sortie "retenue" du circuit addition- neur AD constitue la sortie "retenue" c' vers la cellule suivante la plus proche à droite par l'inter- médiaire de la connexion de sortie Oc. Un signal de "lecture" RD peut être appliqué au circuit addition- neur AD pour provoquer le déversement de son contenu vers une sortie de données DO. En fonctionnement, un bit de chacun des nombres "a" et "b" est appliqué à la porte ET G lorsqu'une impulsion d'horloge ou "top" est appliqué à chacune des bascules L1 et L2. La multiplication de deux nombres binaires à un seul bit consiste à faire simplement l'opération ET, puisque lorsque l'un ou les deux nombres sont nuls le produit est également nul. La sortie de la porte ET G est stockée dans le circuit additionneur AD. Tout bit de "retenue" de la cellule précédente est aussi appliqué au circuit additionneur, et toute retenue résultante est appli- quée immédiatementà la cellule suivante la plus proche. Lorsque l'opération entière de multiplication à effectuer par le réseau a été accomplie, le signal "lecture" RD est appliqué en séquence à chaque circuit additionneur du réseau, provoquant l'écoulement des bits successifs du résultat de l'opération de multi- plication vers un bus de données. D'autres circuits peuvent être ajoutés pour extraire les signes et remettre à zéro les mémoires avant de démarrer une nouvelle opération de multiplication. La figure 2 montre comment un certain nombre de cellules de traitement de bit du modèle décrit peuvent être connectées entre elles pour former un multiplicateur. Le nombre de cellules de traitement de bit doit être au moins égal à la somme des nombres de bits dans chacun des deux nombres. Par exemple, la multiplication de deux nombres à trois bits demande six cellules, marquées sur la figure 2 de C1 à C6. Les connexions "lecture" et sortie sont aussi représentées et repérées RD1 à RD6 et RO1 à RO6 respectivement. La figure 3 illustre le fonctionnement du multiplicateur quand il multiplie entre eux deux nombres à trois bits. Le dessin montre le fonctionnement du multiplicateur pour chacun de neuf tops successifs, le multiplicateur étant représenté pour chaque top avec les positions des bits des deux nombres repérées respectivement a1, a2, a3 et b1, b2 et b3, les bits a3 et b3 étant les bits de plus grands poids des nombres respectifs. La multiplication de deux nombres de trois bits est représentée ci-dessous: b3 b2 b1 x a3 a2 a1 = i h g f e d o d = a1b1 e= a1b2 + a2b1 + retenue éventuelle de d f = a1b3 + a2b2 + a3b1 + retenue éventuelle de e g = a2b3 + a3b2 + retenue éventuelle de f h = a3b3 + retenue éventuelle de g i = retenue éventuelle de h. Il s'ensuit que chaque bit de l'un des nombres est multiplié à son tour par chacue bit de l'autre nombre. Les deux nombres seront généralement obtenus sur deux bus de données séparés, en même temps, et il faut que les bits de l'un des nombres, en l'occurence "b", soient appliqués en ordre inverse. On verra que la pre- mitre cellule représentée, Cl, est une cellule "fictive" qui n'effectue aucune multiplication. En se référant maintenant à la figure 3, le bit de moindre poids a1 du nombre "a" est appliqué à l'entrée "a" de la cellule Ci. Au deuxième top, a1 passe dans la cellule C2 mais il n'y a pas encore d'entrée "b". Au troisième top, a1 passe dans la cellule C3, le bit a2 est appliqué à la cellule C1 et au deuxième top le bit de plus grands poids b3 du nombre "b" est appliqué à la cellule C6. Au quatrième top, a1 passe dans la cellule C4, ainsi que b3, et par conséquent le produit a1b3 est mis en mémoire dans le circuit additionneur de la cellule C4. Egalement au quatrième top b2 est appliqué à la cellule C6, et a2 passe dans la cellule C1. Les bits des nombres "a" et "b" continuent de passer dans le réseau de cellules, et chaque fois qu'un bit de chacun des nombres apparalt dans la même cellule, un produit est effectué et mis en mémoire dans le cir- cuit additionneur de cette cellule. Lors de chaque opération de mise en mémoire, les retenues effectuées sont passées à la cellule suivante la plus proche à droite. Le processus continue jusqu'à ce que chaque bit de l'un des nombres ait été multiplié par chaque bit de l'autre nombre. On verra qu'après le top 8, le circuit additionneur de chacune des cellules contient l'un des nombres d à i mentionnés ci-dessus, sauf pour la cellule Cl. Le résultat de l'opération de multiplication est obtenu en lisant en séquence les contenus des cir- cuits additionneurs de chaque cellule, en commençant par la cellule C6. Dans le mode de réalisation qu'on vient de décrire, les bits des deux nombres passaient en direc- tions opposées à travers le réseau de cellules de traitement de bit, les bits étant appliques alternati- vement aux tops. Ceci exige naturellement que les deux nombres soient présents en même temps, et probablement, que l'un d'entre eux soit mis en mémoire dans un regis- tre jusqu'à ce que l'autre soit disponible. Un second mode de réalisation comporte une disposition convenant au cas o les nombres apparais- sent à des moments différents sur un bus. La figure 4 montre la disposition d'une cellule de traitement de bit pour un tel mode de réalisation. Celle-ci est semblable à la cellule de la figure 1, à part l'addition d'une bascule supplémentaire L4 entre la sortie de la bascule L2 et la connexion Ob de la sortie "b". De plus, on voit que les nombres entrent dans la cellule dans la même direction. L'effet de la bascule L4 est de retarder l'application de chaque bit du nombre "b" d'une impulsion d'horloge, ou d'un top par rapport aux bits du nombre "a", comme on va le décrire ci-dessous. Le figure 5 illustre le fonctionnement d'un réseau de cellules de la figure 4, lors de la multi- plication l'un par l'autre de deux nombres à trois bits. Le retard supplémentaire donné à chaque bit du nombre "b" est représenté par un carré dans un coin du symbole représentant la cellule. En se référant maintenant a la figure 5, le bit de plus grand poids b3 du nombre "b" est appliqué à l'entrée de la cellule CD à laquelle le retard additionnel d'un top est appliqué. Au second top, le bit b3 est retenu par ce circuit de retard, cependant que le bit b2 est appliqué à la cellule CD. Au troisième top, le bit b3 passe à la cellule Cl, le bit b2 est retenu dans le circuit de retard de la cellule CD, et le bit de moindre poids b! est appliqué à la cellule CD. Les bits du nombre "b" continuent de passer dans la matrice de cellules à la cadence d'une cellule tous les deux tops. Au quatrième top, le bit de moindre poids a1 du nombre "a" est appliqué à la cellule CD, et passe à la cellule C1 au top suivant, lorsque le bit a2 est appli- qué à la cellule CD. Le bit a1 se trouve dans la cellule Cl en même temps que le bit b1 et par suite le produit a1b1 est effectué et mis en mémoire dans le circuit additionneur de la cellule C1. Au sixième top, le bit a1 passe dans la cellule C2 en même temps que le bit b2, et par suite le produit a1b2 est effectué et mis en mémoire dans la cellule C2. Au septième top, les bits a1 et b3 sont multipliés dans la cellule C3, cependant que les bits a2 et b1 sont multipliés dans la cellule C2, le produit étant ajouté à celui des bits a1 et b2 déjà contenus dans le circuit additionneur. La retenue éventuelle est passée à la cellule C2. Le processus continue comme indiqué figure 5 jusqu'à ce que chaque bit de l'un des nombres ait été multiplié par chaque bit de l'autre nombre. On verra qu'après le top 11 les circuits additionneurs de chacune des cellules C1 à C6 contiennent les sommes des produits mentionnés ci-dessus, à l'exception de la cellule C6 qui ne contiendra qu'un produit éventuel venant de la cellule C5. Le résultat de l'opération de multiplication est obtenu en lisant en séquence les contenus des cir- cuits additionneurs de chaque cellule, en commençant par le bit de plus grand poids dans la cellule C6. La figure 6 montre un exemple de l'opération qu'on vient de décrire, à savoir la mumtiplication des nombres 111 et 101. Les chiffres réels de chaque nombre ont été écrits dans les rectangles, et les résultats des multiplications sont indiqués au-dessous des rec- tangles concernés. La sortie finale 100011, est indi- quée au bas du diagramme, avec les flèches indiquant une "retenue" reportée du circuit additionneur d'une cellule à celui de la cellule suivante. Comme on l'a déjà indiqué, la technique décrite ci-dessus n'exige qu'un nombre de cellules de traitement de bit au moins égal à la somme des nombres de bits dans les deux nombres, et les multiplicateurs ayant l'une des deux formes décrites conviennent pour la multiplication de grands nombres. Les multiplicateurs numériques du type décrit ci-dessus peuvent servir à de nombreux usages. Par exemple, la multiplication de deux matrices est une exigence commune dans le traitement des signaux numéri- ques. Considérons, par exemple, la multiplication suivante de matrices: a a a b11 b12 bl r 013 Iil 12 1ilb3 2 13. ilC11 201 3 a21 a22 a23 X b21 b22 b23 [21 22 23 la31 a32 a 33 b31 b32 b33 e31 c32 e33l o chaque nombre est lui-même composé de plusieurs bits. Alors: Cll =allb1 + al2b21 + al3b31 e12 = allb12 + a12b22 + a13b32 et ainsi de suite. Un tel calcul peut être facilement exécuté en utilisant un réseau de multiplicateurs du type déjà décrit. Pour la multiplicaiton de matrices indiquée ci-dessus, il faut un réseau de neuf multiplicateurs numériques,comme indiqué figure 7. Les neuf multiplicateurs numériques DM1 à DM9 comprennent chacun un réseau linéaire de cellu- les de traitement de bit, comme on l'a déjà décrit. Les neuf multiplicateurs sont disposées en un réseau de trois par trois, de sorte que quand un nombre passe dans un multiplicateur, il est passé bit par bit au multiplicateur suivant de la même ligne ou colonne. Le dessin montre aussi l'ordre dans lequel les nombres sont appliqués à la matrice de multiplicateurs. Dans chaque rectangle repré- sentant un multiplicateur, on a indiqué le résultat du calcuI effectué par ce multiplicateur, par exemple le multiplicateur DM3 calcule le résultat C13 de la matrice finale. On verra sur la figure 7 que les nombres ail et b1l sont d'abord appliqués au multiplicateur DM1, qui effectue le produit de ces deux nombres. Quand ceci a été fait, le nombre a11 passe au multiplicateur DM2, o il est multiplié par b12, cependant que b11 passe au multiplicateur DM4, o il est multiplié par a22. Au même moment, a12 et b21 sont appliques au multiplicateur DM1. Le produit a12b21 est effectué dans le multiplica- teur DM1 et ajouté au produit a11b11 qui y est déjà en mémoire. La multiplication continue pas à pas jusqu'à ce que chacun des nombres "a" ait été multiplié par chacun des nombres "b". Les résultats finals sont lus dans les neuf multiplicateurs suivant la séquence voulue. Du fait que les multiplicateurs numériques non seulement multiplient l'un par l'autre deux nombres à n bits, mais aussi ajoutent ensemble les résultats de trois telles multiplications, chaque multiplicateur devra comprendre plus de 2n cellules, puisqu'il peut y avoir des bits de "retenue". En fait, s'il y a "m" produits à ajouter les uns aux autres, le nombre N de cellules dans chaque multiplicateur est donné par N = 2n + (m-1). Dans le cas de la multiplication de matrices mentionné ci-dessus, o chaque résultat est l'addition de trois multiplications (m = 3), et o chaque nombre est un nombre à 32 bits (n = 32), on a alors pour cha- cun des neuf multiplicateurs numériques, N = 66. Ceci signifie que chaque multiplicateur comprend un réseau linéaire de 66 cellules, et non les 64 qui sont suffi- santes pour la multiplication de deux nombres de 32 bits. La multiplication de matrices n'est qu'un exem- ple des utilisations nombreuses qu'on peut faire d'un multiplicateur numérique selon l'invention. REVENDICATIONS 1. Un multiplicateur numérique pour multiplier l'un par l'autre deux nombres binaires, caractérisé par une matrice linéaire de cellules de traitement au niveau du bit, chacune comprenant deux connexions d'entrée à chacune desquelles sont appliqués respectivement les bits successifs de chacun des deux nombres binaires, deux connexions de sortie connectées à la cellule adjacente suivante, et auxquelles sont appliqués les- bits successifs déjà mentionnés, des moyens de multipli- cation agissant pour multiplier ensemble un bit de chacun des nombres, et des moyens d'addition agissant pour ajouter ensemble et mettre en mémoire les résul- tats des multiplications successives exécutées dans la cellule. 2. Un multiplicateur selon la revendication 1, caractérisé-par le fait que les premier et second cir- cuits à bascules bistables sont connectés entre chacune des connexions d'entrée et la connexion correspondante de sortie. 3. Un multiplicateur selon la revendication 2, caractérisé par le fait que les moyens de multiplication comprennent une-porte ET ayant deux entrées connectées aux sorties du premier et du second circuits à bascules. 4. Un multiplicateur selon l'une quelconque des revendications 1 à 3, caractérisé par le fait que les moyens d'addition de chaque cellule de traitement de bit, à l'exception de la première cellule du réseau, possèdent une entrée de retenues connectée à la cellule précédente par l'intermédiaire d'un circuit à bascules bistable. 5. Un multiplicateur selon l'une quelconque des revendications 1 à 4, caractérisé par le fait que les moyens d'addition de chaque-cellule de traitement de bit, à l'exception de la dernière cellule du réseau, possèdent une sortie de retenues connectée à la cellule suivante la plus proche. 6. Un multiplicateur selon l'une quelconque des précédentes revendications, caractérisé par des moyens de retard agissant pour retarder l'application des bits successifs de l'un des nombres à la connexion de sortie appropriée, d'un intervalle de temps prédé- terminé, par rapport à chacun des bits successifs de l'autre nombre. 7. Un multiplicateur selon la revendication 6, caractérisé par le fait que les moyens de retard comprennent un troisième circuit bistable à bascules, connecté entre la sortie du second circuit à bascules et la connexion de sortie correspondante. 8. Un multiplicateur selon l'une quelconque des précédentes revendications, caractérisé par le fait que le nombre de cellules dans le réseau est au moins égal à la somme des nombres de bits dans chacun des nombres binaires à multiplier l'un par l'autre. 9. Un multiplicateur selon l'une quelconque des revendications 1 à 8, caractérisé par des moyens de lecture agissant pour extraire des circuits addi- tionneurs de chaque cellule de traitement de bit le nombre qui y est mémorisé lorsque la multiplication des deux nombres binaires est terminée.