Brevet FR2621144A1 — publié le 19890331

MULTIPLIEUR PIPELINE SERIE L'invention concerne un multiplieur pipeline série à structure cellulaire destiné à multiplier deux flux de données numériques synchrones A de n bits [an... ak a1] et B de p bits [bp...bk... bl], n, k et p étant des entiers, en opérant dans chaque cellule de la structure, en mode pipeline, la formation des produits partiels du multi- plicande A par chaque bit du multiplicateur B puis leurs addi- tions successives à une fréquence F d'horloge, chaque cellule d'ordre k comprenant: - un additionneur élémentaire à un bit qui reçoit respective- ment des données xk, Yk et des retenues ck, et qui dé- livre à un instant donné un résultat vk et une retenue Cok, tel que vk = (xk & Yk & Ck) modulo 2 Cok = (Xk & Yk & Ck) div 2 o ck à un instant donné est égal à la donnée cok déter- minée dans la même cellule au temps d'horloge précédent puis retardée soit ck = cok(d), - des moyens de retard pour synchroniser les données issues de deux cellules successives, -et des moyens de stockage temporaire d'un bit de donnée et de la retenue Cok. Pour opérer la multiplication série de deux don- nées numériques on stocke chaque bit d'une des données dans des cellules d'un multiplieur et on multiplie ces bits par les bits de la seconde donnée pour fournir des produits partiels qui sont additionnés selon leurs poids binaires. Un multiplieur de ce genre est connu du document GB 2 166 272A qui décrit un multiplieur série qui opère sur des données signées et qui permet à l'aide d'un drapeau exter- ne de rendre le multiplieur cascadable lorsque l'on désire étendre le nombre de bits des données d'entrée. Mais dans ce document il n'est décrit que la réa- lisation de multiplications tronquées, seule la partie poids fort du résultat est délivrée. Le résultat déterminé est alors approché. Or un premier problème posé, et qu'il est nécessaire de résoudre pour certaines applications, est de disposer du résultat exact de l'opération mais sans accroître le temps de calcul. Ce problème est résolu par l'invention qui est remarquable en ce que le multiplieur comprend des moyens pour délivrer le résultat exact de l'opération en deux tranches consécutives de bits sous le contrôle d'un signal R, tout d'abord, avec n > p, une tranche L formée des p bits de poids binaires les plus faibles puis une tranche H formée des n bits de poids binaires les plus élevés, le multiplieur ayant un débit F/n, ces moyens comprenant: - des moyens de génération, puis de stockage temporaire, d'une donnée clk tel que: clk = (Xk & Yk & Cok) modulo 2 la donnée clk étant délivrée au cours du même temps d'hor- loge que la donnée Cok, - et des moyens pour déterminer les tranches partielles Lk et Hk délivrées par chaque cellule d'ordre k tel que: Lk = Lkl(d).Rk-l(d) + Vk.Rk-l(d) et Hk = vk.Rk_1(d) + Clk(d). Rk-l(d) o Rkl(d) est le signal Rk_1 transmis à la cellule k à travers les cellules précédentes, retardé d'un temps d'hor- loge dans la cellule k, la réintroduction de la retenue ck dans l'additionneur d'ordre k étant contrôlée par le signal Rkl(d) selon ck = cok(d).Rk1-l(d) pour les p-1ième cellules et cp = bp.Rpl(d)+Rpl1(d).cop(d) pour la pième cellule, clk(d) étant la donnée Clk retardée d'un temps d'horloge dans la kième cellule, les p-1ième cellules effectuant sur les données A et B des opérations de type A.bk et la pilme celllule effectuant une opération de type A.bp, les symboles utilisés étant: (.): ET logique; (+): OU logique; (x): multiplication; (&): addition. os05 Un problème technique secondaire est de pouvoir cascader deux multiplieurs. Pour cela la pième cellule est modifiée et comprend des moyens pour déterminer la retenue cp qui entre dans le pième additionneur selon: cp = F.bp.Rp_1(d)+Rpl(d).cop(d) et pour effectuer l'opération du type: (A * F).bp, avec (*) représentant la fonction OU-exclusif; et o F est un signal qui permet de contrôler la pième cellule afin d'obte- nir un multiplieur cascadable. On peut ainsi réaliser une chaîne de plusieurs multiplieurs pour former une structure multiplicatrice. Un autre problème technique secondaire consiste à pouvoir mettre en parallèle plusieurs multiplieurs afin de faire une opération telle que l'addition des résultats de deux multiplications: (AxB) & (CxD) tout en délivrant le résultat exact. Pour cela l'invention permet de réaliser une structure multiplicatrice qui comprend en parallèle deux multiplieurs ou deux chaînes de multiplieurs délivrant simultanément leurs deux tranches L1 et L2 ainsi que leurs deux tranches H1 et H2, les tranches L1 et L2 étant additionnées dans un premier addi- tionneur, et les tranches H1 et H2 et la retenue du premier additionneur étant additionnées dans un second additionneur, chaque additionneur délivrant l'un la partie correspondant aux bits de poids binaires les plus faibles et l'autre la partie correspondant aux bits de poids binaires les plus forts du résultat global. Il est possible de traiter des données A de n bits et B de p bits. Avantageusement avec n>p le multiplieur aura un nombre de cellules égal au nombre p de bits le plus petit de l'une ou l'autre des données d'entrées afin de dispo- ser d'un multiplieur compact. Dans les équations qui suivent les symboles habi- tuels de la notation algébrique sont repris, à savoir: (.): multiplication; (+): addition; (-): soustraction. Soient deux nombres binaires A et B constitués des suites de bits: A = [an... ak... ai] et B = [bp... bk... bl]. Si ces nombres binaires sont négatifs ils sont représentés en complément à 2 selon la méthode habituelle. La multiplication de A par B est un nombre codé sur (n+p) bits: p-i Pnp = A.B = kE A.bk.2k-1-A.bp.2P-1. k=1i On définit les produits partiels: P(o) = o (1) P(k) = P(k-1)+A.bk.2k1 pour 1 (2) P(k) = [Pn+k... Pk... P1]. On peut décomposer cette suite en deux termes pour chaque cellule d'ordre k: (3) L(k) = [Pk - Pl] (4) et H(k) = [Pn+k... Pk+1], o Lk correspond à un terme non signé et Hk correspond à un terme signé. On écrit le terme P(k) tel que: (5) P(k) = H(k).2k+L(k). De même le terme P(k) s'écrit à partir du terme précédent P(k-1) tel que: (6) P(k) = P(k-1)+A.bk.2k-1 c'est-à-dire: (7) P(k) = (H(k-1)+A.bk).2k-l+L(k-1). Le terme H(k-1)+A.bk est une suite binaire S = [Sn+1... sj] qui peut être exprimée par n (8) S = H(k-1)+A.bk = i s i.2ilsn+12n soit: n (9)P()( s (9) P(k)=(i si.2i-1-sn+l.2n).2k-l+L(k-1). Par comparaison avec (5) on déduit que H(k) = [sn+1.. - s2] et L(k) = L(k-1)+s1.2k-1. Donc la détermination du terme H(k-1)+A.bk va permettre de déterminer la suite S, dont les bits de poids forts constituent le terme H(k) de la cellule d'ordre k, le terme L(k) se déduisant du terme L(k-1) en ajoutant le bit de poids faible sl pondéré par le coefficient 2k-1. Ce proces- sus est mis en oeuvre dans chaque cellule d'ordre k. Pour la première cellule les termes H(O) et L(O) sont nuls. Les termes L1, L2,... Lp sont déterminés successivement dans les cel- lules d'ordre 1, 2,... p et apparaissent dans cet ordre à la sortie de la pième cellule sur la connexion propre à L. En même temps que s'effectue la détermination des termes L1... Lp, le multiplieur détermine les termes H1... Hp qui ap- paraissent sur la connexion propre à H en sortie du multi- plieur lorsque la sortie des termes L1 à Lp est terminée. Les deux tranches L et H du résultat final apparaissent donc consécutivement en sortie. L'invention sera mieux comprise à l'aide des fi- gures suivantes données à titre d'exemple non limitatif qui représentent: - figure 1A: un schéma de la structure cellulaire du multi- plieur pipeline série selon l'invention avec p cellules pour une multiplication n x p avec n > p. - figure lB: un diagramme des temps relatif à une multiplica- tion n x n bits. - figure 1C: un diagramme des temps relatif à la structure de la figure 1A. - figure 2: un schéma logique représentant une cellule d'or- dre k avec 1 les tranches L et H selon l'invention. - figure 4: un schéma modifié de la dernière cellule pour obtenir un multiplieur cascadable. - figure 5: un schéma représentant la mise en parallèle de deux multiplieurs selon l'invention afin de réaliser l'opé- ration (AxB) & (CxD). Les symboles suivants sont à nouveau utilisés: (.): ET logique; (+): OU logique; (x): multiplication; (&): addition; (*): OU-exclusif; (-): inversion. La figure 1A représente un schéma de la structure cellulaire du multiplieur pipeline série selon l'invention. Le multiplieur comprend des cellulles 101,... 1Ok... lop. Elles présentent 5 entrées plus une entrée d'horloge h pour assurer le synchronisme des opérations. L'horloge est distri- buée sur toutes les cellules. Les entrées A et B sont destinées à recevoir res- pectivement les données [an... ai] et [bp... b1] à mul- tiplier. Ces données entrent toutes deux avec le bit le moins significatif en tête. Un signal de contrôle R permet de con- trôler les échanges entre les différentes cellules et à l'in- térieur des cellules elles-mêmes. Les entrées L et H reçoivent les valeurs de l'étage précédent. Dans le cas de la première cellule celles- ci sont mises à la valeur zéro. Mais l'entrée H peut recevoir des valeurs non nulles lorsqu'une constante est à ajouter. La cellule 1 transmet à la cellule 2 les données introduites sur A, B et R en les retardant. Elle transmet éga- lement les valeurs L1 et H1 qu'elle a calculées. Ce processus se poursuit jusqu'à la pième cellule qui délivre le résultat final d'abord Lp puis Hp. La figure lB donne le diagramme des temps du dé- roulement des opérations pour n cellules, dans le cas o les données A et B ont toutes deux une longueur de n bits. Toutes les cellules vont opérer durant un tempe égal à n fois l'hor- loge de base de durée h. La première cellule opère dès l'ins- tant initial, la kième cellule commence à opérer avec un re- tard de kxh et la nième cellule commence à opérer avec un retard de nxh. La cellule k délivre à l'instant k le premier bit de son terme Lk, et à l'instant 2k délivre le premier bit de son terme Hk. De même la cellule n délivre à l'instant n le premier bit de son terme Ln et délivre à l'instant 2n le premier bit de son terme Hn. La figure 1C donne le diagramme des temps du dé- roulement des opérations avec p cellules pour des données A de n bits et B de p bits. Cela correspond au cas de la figure lB avec k=p. La cellule p délivre à l'instant p le premier bit de son terme Lp et à l'instant 2p délivre le premier bit de son terme Hp. La figure 2 est un schéma logique représentant la cellule 10k d'ordre k (1 Rk_1 le kième bit de la donnée Bk_1 c'est-à-dire bk. Celui-ci est stocké pendant une durée nxh dans la bascule 23k pour être utilisé par la cellule k. La sortie de la bascule 23k et celle de la bascule 21k entrent dans une porte ET 35k pour effectuer la multiplication du bit bk par [an... ai]. Toutes les bascules sont contrôlées par l'horloge h. Chaque cellule 10k comprend un additionneur 37k. C'est un additionneur à 1 bit à 3 entrées et 3 sorties. En appelant x, y, r le bit présent respectivement sur chaque entrée et en appelant v, co, ci le bit présent respectivement sur chaque sortie, le résultat délivré par l'additionneur s'exprime d'une manière générale par les équations logiques suivantes: si x * y = 1 alors v = r, co = r et cl =r si x * y = O alors v= r, co = x et cl = x o le symbole (*) représente le OU-exclusif et le symbole (-) représente l'opération d'inversion. La sortie de la porte ET 35k est additionnée dans l'additionneur 37k avec la sortie de la bascule 24k et avec une retenue ck pour fournir le résultat partiel vk. L'additionneur 37k délivre également une retenu Cok qui est retardée dans une bascule 29k. Un sélecteur 32k délivre la retenue ck tel que: ck = Cok(d).Rk-1(d). L'additionneur 37k délivre également la donnée clk définie par C1k = [xk & Yk & cok] modulo 2 dans le même temps d'horloge que la donnée cok. Un sélecteur 33k délivre les données Hk tel que: Hk = vk.Rk-l(d)+clk(d).Rk-l(d). De même un sélecteur 34k délivre les données Lk tel que: Lk = vk.Rk-1(d)+Lk-1(d).Rk-l(d). La cellule 10p est analogue à la cellule 10k à l'exception des points suivants. Le sélecteur 32p sélec- tionne la retenue cp tel que: Cp = Rp_l(d).bp+Rpl(d).cop(d) - la sortie de la bascule 21p entre dans un inverseur 36p dont la sortie entre dans une porte ET 35p, - les bascules 27p et 22p peuvent être supprimées sauf lorsque deux multiplieurs sont mis en série et que les données A et B doivent être transmises (voir figure 4). Le mécanisme de fonctionnement est le suivant donné à titre d'exemple avec 4 bits pour les données A et B. Le multiplieur présente alors 4 cellules. Au début du premier temps Ro = O. A l'issue du 1er temps: La bascule 211 stocke ai La bascule 221 stocke bi La bascule 231 stocke b1 La bascule 241 stocke H(O)=O ' La bascule 251 stocke L(O)=0 La bascule 261 passe à l'état logique O Au cours du 2ème temps: l'additionneur 371 commence à opérer en calculant al.bl A l'issue du 2ème temps: le bit al a progressé jusqu'à la sortie de la bascule 271 le bit bl a progressé jusqu'à la sortie de la bascule 222 la bascule 231 conserve le bit b, la bascule 232 est toujours à zéro. A l'issue du 3ème temps: le bit al a progressé jusqu'à la sortie de la bascule 211 le bit b2 a progressé jusqu'à la sortie de la bascule 222 la bascule 231 conserve le bit b1 la bascule 232 stocke le bit b2. Au cours du 4ème temps: l'additionneur 372 commence à opérer en calculant al.b2. Les calculs effectués dans chaque cellule se dé- roulent de la manière suivante: 1ère cellule 2ème cellule 1er temps O O 2ème temps albi 0 3ème temps a2b1 aibi & O 4ème temps a3bl a2bl & alb2 Sème temps a4bj a3bl & a2b2 6ème temps O a4bl & a3bz 7ème temps O O & a4b2 8ème temps O O 9ème temps O O ème temps O O 11ème temps O O 3ème cellule 4ème cellule 1er temps 0 0 2ème temps 0 0 3ème temps 0 0 4ème temps a1b1 & 0 0 ème temps a2b1 & alb2 & 0 albi 6ème temps a3b1 & a2b2 & a1b3 a2bl & alb2 7ème temps a4b1 & a3b2 & a2b3 a3b1 & a2b2 & a1b3 8ème temps a4b2 & a3b3 a4b1 & a3b2 & a2b3 & alb4 9ème temps a4b3 a4b2 & a3b3 & a2b4 ème temps 0 a4b3 & a3b4 11ème temps 0 a4b4 A partir de ces opérations élémentaires effec- tuées dans chaque cellule du multiplieur, la construction des signaux Lk et Hk va se faire dans chaque cellule de la ma- nière suivante. La situation est représentée sur la figure 3. En A sont représentées les données sur la connexion 73k, en B sont représentées les données sur la connexion 72k, en C sont représentées les données sur la connexion 71k, c'est-à-dire avant les sélecteurs 34k et 33k. Ceux-ci vont être actionnés par le signal Rkl(d) de la connexion 76k, la position représentée sur la figure 2 étant celle correspon- dant à Rk_1=1. A la fin d'un cycle de calcul Rk_1 passe à zéro pendant une durée d'horloge. Ceci permet d'insérer cer- tains bits et d'obtenir les configurations représentées en D et E. Pour une cellule d'ordre k seuls les k premiers bits de Lk ont été déterminés, le reste des k-p (ou k-n) bits sont des zéros. Selon l'invention le bit de poids le plus faible h1k du terme vk calculé est inséré dans la donnée Lk_1 pour former Lk. Cette insertion contrôlée par le si- gnal R se fait de sorte que le bit h1k devienne le bit le plus significatif de la tranche Lk. Sur le même principe la donnée clk qui a été calculée par la cellule k est tout d'abord retardée par la cellule 30k et insérée dans la donnée vk pour former Hk. La donnée Clk devient le bit le plus significatif de Hk. Cette situation est représentée en E sur la figure 3. Ces opérations se renouvellent dans chaque cellu- le et on obtient en sortie du multiplieur la tranche Lp sui- vie de la tranche Hp constituant le résultat exact de la multiplication de A (n bits) par B (p bits). L'opération ne nécessite que p durées d'horloge pour délivrer Lp et n du- rées d'horloges pour délivrer Hp pour un résultat exact sur n+p bits. Avec n > p on peut initialiser une nouvelle opéra- tion tous les n cycles. Le débit est donc F/n o F,est la fré- quence d'horloge. Le temps de latence qui est la durée entre l'introduction du premier bit d'une donnée et la sortie du premier bit du résultat, est de p cycles si p est le nombre de cellules. Les données A et B peuvent être deux entiers. Il est également possible que B par exemple soit un coefficient inférieur à l'unité. Dans ce cas la tranche Hp contient la partie entière du résultat et Lp contient la partie frac- tionnaire. Il est possible de mettre en série deux multi- plieurs tels que ceux décrits par exemple pour effectuer une extension de la donnée B de p à 2p bits. Selon le schéma de la figure 5 il est possible de faire opérer les 2 multiplieurs 41, 42 en parallèle pour opé- rer une première multiplication AxB et une seconde CxD afin d'obtenir le résultat (AxB) & (CxD). Les tranches L des bits les moins significatifs étant délivrées en premier, elles sont additionnées dans l'ad- ditionneur 43. De même les tranches H des bits les plus signi- ficatifs sont additionnées dans l'additionneur 44 avec la re- tenue issue de l'additionneur 43. Le résultat final est de la même façon délivré sur deux tranches de bits. 262 1 1 4 4 Le schéma de la dernière cellule représenté sur la figure 2 concerne un multiplieur qui ne peut être cascadé avec l'entrée d'un multiplieur identique. Pour obtenir cette possibilité il est nécessaire de modifier la dernière cellule selon le schéma de la figure 4. Les bascules 27p et 28p retardent les données Ap et Rp de la même façon que sur les cellules précédentes et les transmettent vers l'extérieur. Un signal F contrôle de l'extérieur le mode de fonctionnement afin de permettre que dans une chaîne de plusieurs multiplieurs seule la dernière cellule du dernier multiplieur ait un mode de fonctionnement particulier. Les autres dernières cellules des multiplieurs précédents sont alors contrôlées par F pour opérer comme tou- tes les autres cellules. Pour cela une porte ET 51 reçoit F et le bit bp, et une porte OU-exclusif 52 reçoit F et la sortie de la bascule 21p. Lorsque le signal F est à l'état logique zéro la dernière cellule a un mode de fonctionnement particu- lier. Lorsque le signal F est à l'état logique 1 la cellule a le même comportement que toutes les autres cellules. Ceci permet de cascader plusieurs multiplieurs pour étendre le nombre de bits de l'une au moins des données A ou B. Ainsi la pième cellule comprend des moyens pour déterminer la retenue cp, qui entre dans le dernier addi- tionneur, selon: cp = F.bp.Rpl(d)+Rpl(d).cop(d) et pour effectuer l'opération du type: (A * F).bp, avec (*) représentant la fonction OU-exclusif, et o F est un si- gnal qui permet de contrôler la pième cellule afin d'obtenir un multiplieur cascadable. REVENDICATIONS: 1. Multiplieur pipeline série à structure cellu- laire destiné à multiplier deux flux de données numériques synchrones A de n bits [an... ak... al] et B de p bits [bp.bk.. bi], n, k et p étant des entiers, en opérant dans chaque cellule de la structure, en mode pipeline, la formation des produits partiels du multiplicande A par chaque bit du multiplicateur B puis leurs additions successives à une fréquence F d'horloge, chaque cellule d'ordre k comprenant: - un additionneur élémentaire à un bit qui reçoit respective- ment des données xk, Yk et des retenues Ck, et qui dé- livre à un instant donné un résultat vk et une retenue Cok, tel que vk = (xk & Yk & Ck) modulo 2 Cok = (xk & Yk & ck) div 2 o ck à un instant donné est égal à la donnée Cok déter- minée dans la même cellule au temps d'horloge précédent puis retardée soit ck = Cok(d), -des moyens de retard pour synchroniser les données issues de deux cellules successives, - et des moyens de stockage temporaire d'un bit de donnée et de la retenue Cok, caractérisé en ce que le multiplieur comprend des moyens pour délivrer le résultat exact de l'opération en deux tranches consécutives de bits sous le contrôle d'un signal R, tout d'abord, avec n > p, une tranche L formée des p bits de poids binaires les plus faibles puis une tranche H formée des n bits de poids binaires les plus élevés, le multiplieur ayant un dé- bit F/n, ces moyens comprenant: - des moyens de génération, puis de stockage temporaire, d'une donnée clk tel que: Clk = (xk & Yk & Cok) modulo 2 la donnée clk étant délivrée au cours du même temps d'hor- loge que la donnée Cok, - et des moyens pour déterminer les tranches partielles Lk et Hk délivrées par chaque cellule d'ordre k tel que: Lk = Lk_1(d).Rk-l(d) + Vk.Rk-1(d) et Hk = vk.Rkl(d) + Clk(d). Rk-1(d) o Rkl(d) est le signal Rk_1 transmis à la cellule k à travers les cellules précédentes, retardé d'un temps d'hor- loge dans la cellule k, la réintroduction de la retenue ck dans l'additionneur d'ordre k étant contrôlée par le signal Rkl(d) selon ck = cok(d).Rkl(d) pour les p-1ième cellules et cp = bp.Rpl(d)+Rpl(d).cop(d) pour la pième cellule, c1k(d) étant la donnée Clk retardée d'un temps d'horloge dans la kième cellule, les p-1ième cellules effectuant sur les données A et B des opérations de type A.bk et la pième cellule effectuant une opération de type A.bp, les symboles utilisés étant: (.): ET logique; (+): OU logique; (x): multiplication; (&): addition. 2. Multiplieur selon la revendication 1, caractéri- sé en ce qu'il comprend n cellules, les moyens de stockage temporaire retardant dans chaque cellule les bits du multipli- cateur B. 3. Multiplieur selon la revendication 1, caractéri- sé en ce qu'il comprend p cellules, les moyens de stockage temporaire retardant dans chaque cellule les bits du multipli- cande A. 4. Multiplieur pipeline série selon une des revendi- cations 1 à 3 modifiées en ce que la pième cellule comprend des moyens pour déterminer la retenue cp selon: cp = F.bp.Rpl(d)+Rpl(d).cop(d) et pour effectuer l'opération du type: (A * F).bp, avec (*) représentant la fonction OU-exclusif, et o F est un si- gnal qui permet de contrôler la pième cellule afin d'obtenir un multiplieur cascadable. 5. Structure multiplicatrice caractérisée en ce qu'elle comprend une chaîne de plusieurs multiplieurs selon la revendication 4, qui sont cascadés pour étendre le nombre de bits de l'une au moins des données A ou B. 6. Structure multiplicatrice caractérisée en ce qu'elle comprend en parallèle deux multiplieurs ou deux chaî- nes de multiplieurs selon l'une des revendications 1 à 5, les OS deux multiplieurs ou les deux chaines de multiplieurs déli- vrant simultanément leurs deux tranches L1 et L2 ainsi que leurs deux tranches H1 et H2, les tranches L1 et L2 étant additionnées dans un premier additionneur, et les tranches H1 et H2 et la retenue du premier additionneur étant additionnées dans un second additionneur, chaque additionneur délivrant l'un la partie correspondant aux bits de poids binaires les plus faibles et l'autre la partie correspondant aux bits de poids binaires les plus forts du résultat global.