FR 2072117 A1 19710924 FR 7044226 A 19701119 70 44226 1 2072117 La présente invention concerne la réalisation de fonctions logiques de N variables, et plus particulièrement un système matriciel généralisé permet» tant de réaliser diverses fonctions logiques à l'aide d'un minimum de portes logiques. 5 Les matrices logiques sont connues dans l'art antérieur. Une matrice généralisée permet de générer diverses fonctions logiques à N variables tout en utilisant la mSme configuration de portes logiques et présente de ce fait une très grande souplesse. Une telle matrice se compose fondamentalement de portes logiques disposées en colonnes et en rangées, d'un système permettant 10 d'accepter les N variables en tant qu'entrées des portes logiques, et d'un système permettant d'emmagasiner de façon semi-permanente les entrées fixes des portes logiques et, de ce fait, de déterminer leurs fonctions de sortie. Diverses fonctions logiques sont obtenues en sortie en faisant varier les signaux d'entrée emmagasinés. L'un des principaux inconvénientsdes matrices 15 généralisées de l'art antérieur est le fait qu'un grand nombre de portes logiques est nécessaire pour réaliser une fonction désirée. Un autre inconvénient de certaines de ces matrices est qu'un grand nombre de niveaux logiques est nécessaire pour réaliser une fonction désirée. Ces inconvénients sont d'autant plus graves que le nombre de variables d'entrée augmente, car le nombre résul-20 tant de portes logiques nécessaires augmente lui aussi et dans, certains cas de façon exponentielle. .L'un des objets de la présente invention est par conséquent de fournir un système matriciel généralisé permettant de diminuer le nombre de portes logiques et de niveaux logiques nécessaires pour produire une fonction varia-25 ble de N et maintenir le nombre de niveaux logiques à une valeur constante, indépendamment de la fonction que l'on génère. On utilise à cette fin un certain nombre de matrices généralisées, chacune desquelles se compose d'un décodeur d'entrée, de portes logiques disposées en colonnes et en rangées, et d'un registre d'emmagasinage. Le décodeur accepte 30 les variables d'entrée et fournit une sortie qui indique la valeur des variables d'entréei il existe un signal de sortie indépendant pour chaque combinaison de variables d'entrée. Par exemple, s'il y a deux variables d'entrée, il y aura quatre sorties possibles du décodeur indiquant les combinaisons possibles ci-après des variables d'entrée: Xgfy XgX^. Il y a dans chaque 35 matrice autant de rangées qu'il y a de sorties possibles du décodeur. Le nombre de colonnes dépend du nombre de fonctions de sortie désirées puisque les sorties de chaque porte logique dans chaque colonne sont reliées de façon à produire une fonction de sortie désirée pour chaque colonne. Le registre d'emmagasinage est variable et fournit une seconde entrée pour chacune des portas 40 logiques. Les valeurs emmagasinées dans ce registre déterminent la fonction bad oftfginat1 70 44226 2 2072117 produite dans chaque colonne de la matrice puisque la sortie de chaque porte logique est fonction de cette valeur d'entrée. Si une fonction de N variables est désirée, les N variables sont les entrées du système matriciel. Conformément à la présente invention, un nombre 5 L) de variables inférieur au nombre total N de ces variables est décodé de façon indépendante dans une première matrice logique généralisée. De mSrne, un nombre V de ces variables inférieur à N est décodé de façon indépendante dans une seconde matrice généralisée. Les sorties des colonnes de ces deux matrices sont combinées de façon logique pour fournir des fonctions de U + 10 V variables. Cette technique peut être répétée dans une troisième matrice et dans d'autres matrices généralisées jusqu'à ce que la fonction de l\l variables soit générée. L'invention permet ainsi de réaliser un système de matrices logiques généralisées comprenant des matrices généralisées individuelles qui sont montées en parallèle de façon à générer la fonction désirée de N variables. 15 Etant donné que le fonctionnement de chaque matrice individuelle requiert moins du nombre total de variables, les différentes matrices individuelles permettent d'obtenir une partition des opérations logiques effectuées par le système matriciel» D'autres objets, caractéristiques et avantages de la,présente invention 20 ressortiront mieux de l'exposé qui suit, fait en référence aux dessins annexés à ce texte, qui représentent un mode de réalisation préféré de celle-ci. La figure 1 représente une matrice logique généralisée utilisée aux fins de la présente invention. La figure 2 représente la technique permettant d'obtenir une partition 25 des opérations logiques selon la présente invention. La figure 3 représente la technique permettant d'obtenir une partition des opérations logiques selon la présente invention dans laquelle les variables sont traitées de façon indépendante. On a représenté sur la figure 1 une réalisation spécifique d'un type 30 de matrice logique généralisée pouvant être employée dans la présente invention. Elle se compose essentiellement d'un décodeur 10, de portes logiques 12 disposées en colonnes et en rangées, et d'un registre d'emmagasinage 14. La disposition des portes représentée sur la figure 1 a simplement pour but d'illustrer un cas particuler de groupage-topologique dense de portes logiques. 35 Les portes logiques 12 représentées sont des partes ET, mais la matrice peut utiliser n'importe quel type de portes logiques classiques y compris des portes □U, NON ET3 ou NI. Le circuit de décodage 10 est classique et ses sorties constituent las entrées des portes ET, Il accepte les variables d'entrée X^» X2 et X3 et fournit un signal de sortie sur l'une des lignes 16-30 en 40 fonction de la combinaison des variables d'entrée. Par exemple, si X1 et BAD ORIGINAL 70 44226 3 2072117 sont des "1" et est un "0", le décodeur fournit une sortie seulement sur la ligne 28. Cette sortie est ensuite utilisée comme entrée de toutes les portes ET 12 associées à la mSme rangée que la ligne 28. Le registre d'emmagasinage représenté est un registre à décalage 14 possédant huit positions 5 de bit pour chaque colonne, chaque bit étant associé à une entrée de chaque porte ET. D'autres systèmes de mémoire ou d'emmagasinage peuvent être utilisés à la place de ce registre à décalage, par exemple un registre d'emmagasinage constant tel qu'une mémoire inaltérable dite mémoire morte. Des techniques classiques peuvent 6tre employées pour faire varier les signaux emmagasinés 10 dans chaque position ou cellule de bit. Chaque porte ET a donc deux entrées: l'une d'elles provient de la sortie du décodeur, et l'autre est emmagasinée dans une position de bit associée dans le registre d'emmagasinage. Comme le montre la figure, les sorties des portes ET figurant dans chaque colonne sont respectivement reliées par les lignes 32, 34 et 36. Il existe donc une fonction 15 (de colonne) de sortie pour chaque colonne. Il convient de préciser ici que le terme "colonne" est dérivé de la configuration particulière représentée sur la figure 1. Dans le cas d'une autre configuration, telle qu'un groupe concentrique de portes logiques, l'équivalent fonctionnel de la "colonne" peut être réalisé en couplant les portes le long de rayons choisis des groupes 20 concentriques» ou encore le long d'anneaux choisis. Dans un autre groupage topologique dense de portes logiques, l'équivalent fonctionnel d'une "colonne" peut être une coupe à travers un groupage tridimensionnel, Une configuration planaire de portes logiques comprend alors l'équivalent fonctionnel d'une "colonne". 25 C'est donc dans son sens le plus large que le mot "colonne" est employé ici pour désigner un groupage de portes logiques permettant de réaliser une fonction ou une salis-fonction logique dans les conditions indiquées dans le présent document. Trois fonctions seulement, f^, f2 et fg, des trois variables X^, X2 et Xg 30 sont représentées sur la figure, une fonction étant associée à chaque colonnej il existe 25B fonctions possibles. La fonction générée à la sortie de chaque colonne est déterminée par les signaux emmagasinés dans le registre. Comme indiqué sur la -figure, les fonctions générées sont F1 = X^-W^-VX^, F2 = X2VCXi . X3), F3 = Fi. En fonctionnement, chaque cellule du registre d'emmaga-35 sinage fournit une entrée à sa porte ET correspondante selon les valeurs de bit emmagasinées dans cette cellule. L'autre entrée de la porte ET est fournie par la ligne de sortie correspondante du décodeur. De la sorte, pour une combinaison donnée de variables d'entrée, une, et une seulement, des lignes de sortie du décodeur a une sortie positive ou au niveau logique 1, et si la 40 porte ET associée reçoit également un signal positif de son bit d'emmagasinage 70 44226 4 2072117 10 35 correspondant, la sortie de la porte ET est positive. Etant donné que toutes les portes ET d'une colonne sont interconnectées, ce signal positif apparaît sous la forme d'une sortie de colonne. Bien que la figure 1 représente une matrice pour N = 3, il est évident que la mSme méthode peut Stre employée pour un nombre arbitraire de N variables. Toutefois, le nombre de fonctions à N variables composant cet univers est de 22^, dont seulement un nombre relativement faible se compose^fonctions utilesdans le sens qu'elles sont employées comme équations d'étude ou descriptions d'états dans un ordinateur réel. De plus, le nombre de lignes de sortie N du décodeur est de 2 , ce qui est également le nombre de portes logiques par colonne et le nombre dB bits dans le registre d'emmagasinage commandant chaque colonne. De la sorte, pour N = 8, un décodeur à 256 lignes de sortie doit Être utilisé pour commander 256 portes logiques par colonne, chaque colonne étant commandée par 256 bits dans son registre d'emmagasinage. Il est souhai-15 table d'employer des matrices comportant un nombre inférieur de variables et de procéder à une partition des fonctions de commutation de telle sorte qu'une fonction du nombre requis de variables puisse Être construite, sans perte de possibilités, à partir de fonctions de sous-ensembles de ces variables. Considérons à présent la fonction F de N variables: f(XQ, X^... X^). 20 Cette fonction peut être développée sous sa forme disjonctive normale de la façon suivante: fIV X1* xn-15 K, . Xn.~% ....T .V 0 _0_ 1 _ n-1 Kv„. x„x„ ... x nx „x y ... m 1 0 1 n-2 n-1 n-1 25 ,. XnX, ... X . 2n»1 0 1 n-1 dans laquelle chaque est le coefficient de l'une des combinaisons ET de XQ, X,j ..., et a une valeur de "zéro" ou de "un". Cette forme disjonctive normale de la fonction F (Xg, X^, .... Xn-^3 peut être groupée en mettant en facteur tous les termes en X . et tous les termes en X , comme suit: n-1 n-i 30 ^Xo' Xn-1^ |x" |X° o U • • • "Xn-2 V A1 XQ X(| . • • Xn-2 v A^p-1^ xo x1 • • • X ,] X . n-2 n-1 + ^0 X0 X1 * • • Xn-2 v B1 XQ 71 . • • Xn-2 v B (2° ~1) xo X, ... 1 x„ o 3 x , n-2 n-1 Les termes entre parenthèses sont des fonctions des n-1 variables restantes (Xn, X.., ... x exprimées sous la forme normale disjonctive. Les A et u i les B sont définis de façon similaire à la définition de K ci-dessus. Il est donc évident que l'équation initiale peut Stre écrite sous la 70 44226 5 2072117 X n-1 X 10 forme suivante: F (Xq, X^, ... Xn„1) = fQ (XQ, ... Xn-2) v ^ cx0> ... xn-2i ..n-1 De plus, fQ et f peuvent tous deux être mis en facteur de façon similaire, de sorte que la fonction F peut Être développée davantage encore. Pour, illustrer en détail ce qui précède, considérons.le cas d'une fonction F de huit variables: FtXg, X^, .X^J. En développant cette fonction de la façon indiquée ci-dessus, on obtient : *— B var. FCX , ... X } 15 20 25 30 « 7 var • ■ f0 -cx0. • • 9 V X7 - V f1 iX0, • • » V X7 « B var • = g0 £X0' • • ) V X6 X7 V Ê1 ex , * * ) XJ X„ X, 0 5 _6 _7 V Ê2 cx0. • • » X5) X6 X7 V s3 CXq. .. 5 x5} XB X7 — 5 var k = h0 CXq, • • » X4) X5 X6 X7 V h1 CXq, X4) X5 xB X7 V h2 CXD, •M X4) x5 XB X7 V h3 CX0, •M X4) x5 X6 X7 V h4 CXq, • • J X4) x5 XB X7 V h5 CXq, • • » X4) X5 Xb x7 V hg CXq, X4) X5 X6 x7 = Jo £Xq, • • * X3) X4 X5 X6 V 1 1 J1 cx0. • • * X31 x4 X5 XB 1 V jl5£xo. • • * x3î x4 x5 Xb X? X7 = f1 v f2 v v f15 Cette séquence finale peut être extrapolée de façon logique pour retrouver 35 la fonction originale en inversant simplement les étapes mathématiques de la réalisation logique. Si des matrices logiques généralisées sont utilisées de la façon représentée par la figure 1, cette réalisation peut être effectuée à l'aide de deux matrices de ce type, de quatre variables d'entrée et de seize colonnes chacune. La première matrice permet alors de générer les fonctions 70 44226 6 2072117 15 J et a ainsi comme entrée les variables Xg à Xg. La seconde, matrice génère les fonctions de X^ à X^. Les sous fonctions f^ à f peuvent alors être dé-* duites en faisant simplement passer les colonnes de sortie appropriées des deux matrices généralisées à travers ilin circuit ET. La fonction OU de ces 5 seize sous fonctions permet alors de déduire la fonction F de huit variables. Toutefois, la fonction peut également être développée en réunissant les N variables par paires de telle sorte que chaque matrice logique généralisée n'emploie que deux variables comme entrées. Pour illustrer ce point, la fonction de huit variables mentionnée ci-dessus peut également être développée 10 comme suit: f (Xq' = ^ é=1X6X7 ^ ®2* X6tX7 ^ ®3X6*X7 où : gQ = hQ (X0,X1,X2, Xg.3 . X^.Xg v hg.X^.Xg v h^.X^.Xg v hQ. X^.X^ S1 = h° CX0,X1.X2, X3.) . X4.X5 v h2.X4.X5 v h2.X4.X5 v h^. X^ g2 = h°.X4.X5 v h2.X4.X5 v h2.X4.X5 v h2.X4.X5 g3 = h°.X4.X5 v h3.X4.X5 v hg.X4.X5 v hg.X4.X5 Les termes H peuvent Stre développés de façon similaire en deux fonctions de deux variables. Il suffit d'en donner ci-après un seul exemple: h0(X0' X1' X2' X33 " ^00 (X0* X13 *X2"X3 V ^00 X2,X3 V J0D oX2"X3 20 . • y &-V3 Ce développement de la fonction FCXg, X^, »<>., peut §tre résuma de la façon suivante: 4 fonctions g, f(X^, X^) = gQ.Xg.X^ v ... 4 X 4 = 1E fonctions h 25 hg»v hg.T^.Xç- v hQ.X4.Yg v hg.X4.X^ 4 X 4 X 4 = 64 fonctions J feV J00 X2 5r3a 3SO"V3V J00X2X3 Il est évident qus la fonction de huit variables peut également être 30 réalisée à l'aide de quatre matrices logiques généralisées à deux entrées chacune, ainsi qu'à l'aide de deux matrices à quatre entrées chacune. La première de ces matrices générerait les fonctions J avec des variables X^ et 70 44226 7 2072117 comme entrées. La seconde matrice générerait les fonctions de X2 et Xg avec ces variables comme entrées. La fonction-ET des sorties des colonnes de ces matrices, et la fonction OU des colonnes appropriées permettraient d'obtenir les fonctions H. La troisième matrice logique générerait les fonctions de 5 X^ et X5 avec ces variables comme entrées. La fonction ET des sorties de colonnes de cette troisième matrice et des fonctions h déjà obtenues et la fonction OU des sorties appropriées des portes ET permettraient d'obtenir les fonctions G. La quatrième matrice généralisée générerait les fonctions désirées de X„ et Xt avec ces variables comme entrées. La fonction ET des sorties des b / 10 colonnes de cette quatrième matrice et dLes fonctions G, et la fonction OU des sorties de ces portes ET permettraient d'obtenir la fonction désirée F de huit variables. La figure 2 représente une configuration permettant de réaliser une fonction de quatre variables à l'aide des techniques décrites ci-dessus. La confi-15 guration se compose de deux matrices logiques généralisées 50 et 52 dont le fonctionnement est identique à celui de la matrice décrite dans la figure 1, à l'exception du fait que chaque matrice n'accepte que deux variables d'entrée au lieu de trois. Etant donné que chaque décodeur 54 et 56 n'a que deux entrées, chaque décodeur n'a que quatre lignes de sortie, respectivement réfé- 30 rencées 56-64 et 66-72, au lieu de huit comme dans le cas du décodeur à trois entrées représenté sur la figure 1. -Avant de décrire le fonctionnement de la matrice représentée sur la figure 2, il est intéressant de développer la fonction F de quatre variables F(X„,X ,X„,X„) conformément à la description ci-dessus dans laquelle les varia-0 1 2 3 25 bles sont réunies par paire. Par conséquent: F CXq,X^,X2,Xg] = gg."X2«Xj v g^.X2«Xg v g2.X2.Xg v gg.X2.Xg où : g0 = h!rV*1 v hJ'VX1 v h0-X0-X1 v h0-X0-X1 30 g g2 = h^.Xg.X^ v I^.Xg.X^ v h2«Xg.X^ v h^*Xq•X^ g3 = h3,X0*X1 V h3*X0*X1 V h3'X0'X1 V h3*X0'X1 Une fonction désirée de quatre variables peut de la sorte être réalisée à 35 partir des quatre sous-fonctions suivantes: 3 f0 B0 .X 2X . f1 = g1 •*2"X3 f2 = g2 •X2'^3 f3 = ' S3 .x2.x3 70 44226 2072117 □n peut voir sur la figure 2 la façon dont ces sous-fonctions sont générées. La matrice 50 génère les fonctions G à partir des variables d'entrée XQ et X^. Ces variables sont les entrées du décodeur 54 qui fournit une sortie sur l'une de ses lignes de sortie 58-64 en fonction des valeurs de ces entrées. 5 Par exemple, si XQ et X^ sont toutes deux des "zéros," un signal positif apparaît sur la ligne de sortie 58j de même, si XQ est un "zéro" et si X^ est un "un", une sortie apparaît sur la ligne 60. Les valeurs H nécessaires pour obtenir la fonction G désirée sont emmagasinées dans les registres 74 à B0. Il s'ensuit que, si la fonction désirée gQ est X0X1, hg est un "un" 10 et les valeurs restantes hQ sont des "zéros"; par conséquent, une valeur de "un" est emmagasinée dans le premier bit du registre 74 et des "zéros" dans les bits restants. En fonctionnement, cela signifie que dans la première colonne de la matrice 50, seule la porte ET 82 reçoit une entrée du registre positive 74. En conséquence, une sortie de colonne positive apparaît sur la 15 ligne d'interconnexion 90, seulement lorsqu'un signal positif apparaît sur la ligne de sortie 58 du décodeur, c'est-à-dire seulement lorsque XQ et X^ ^ont toutes deux des "zéros". La fonction désiree g^ = X^X^apparaît donc en tant que sortie de colonne de la li^ne d'interconnexion 90. De même, si la — — 12 fonction désirée g_ est égale a X„X. v X„X., les valeurs de h„ et h„ sont 43 0" w 0101 00 20 des "uns" et les valeurs restantes sont des "zéros." Les second et troisième bits dans le registre 74 sont donc positifs et les bits restants négatifs. Les portes ET 84 et 86 produisent une sortie de colonne positive sur la ligne d'interconnexion 90 chaque fois que X^ ou X^ est égale à "un," mais non lorsque XQ et X^ sont toutes deux égales à "un". Les colonnes restantes dans la 25 matrice 50 fonctionnent de façon similaire et produisent les fonctions g^, g2 Bn tarvfe clUB sortiBe de colonnes sur les lignes d'interconnexion 92. à 96, respectivement. La matrice 52 génère les seconds termes des fonctions fQ, f^ , f et f^ s'est-à-dire, les fonctions X2X3, X2X3, X2X3, et X2X3 . Il est souhaitable 30 que la fonction X2Xg soit générée dans la prerriière colonne de la matrice 52 afin de pouvoir Stre facilement combinée avec la fonction gQ produite dans la première colonne de la matrice 50. Afin de produire la fonction X2X3 40 d'interconnexion 108 seulement lorsqu'un signal positif apparaît sur la ligne ■û 44226 9 2072117 dé sortie SB du décodeur, ce qui sg produit seulement lorsque les variables d'entrée X_^X sont toutes deux négatives. Les colonnes restantes de la matrice 52-génùrsnt dans les mêmes conditions les fonctions XX, X 3 «J A O J Ds la sorte, les fonctions g,,. g.,, ç.. et g., ont été générées dans la i ^ o 5 matrice 5J, et les fonctions X_.X, et X„X„- dans la matrice 52. La fonction 2 j £ 3 ET, obtenus à l'aide des portes ET 110-116, des sorties des colonnes appropriées ae ces matrices permet de générer les fonctions fn, f., f_, et f„. La fonction «j » j OU de ces ^onctions individuelles sans la porte OU "11S permet d'obtenir une fonctior aésirée de quatre variables f (Xn,X.,X.„X_J. ' U » ^ O 10 II est possible d'améliorer davantage encore la technique de partition décrite ci-dessus en traitant chaque sous-ensemble de variables ae façon indépendante. Les fonctions de cas variacles peuvent ensuite être combinées de façon logique en une fonction composite désirée de toutes les variables, avec un nombre réduit de portes logiques et sans perte de DossiDilités. Par exemple, 15 la fonction de quatre variacles décrits ci-dessus prendrait la forme suivants • si les sous-ensemblss da'variables rroucées car paires étaient traités indépendamment: fixc,x1,x2,x3) - tgG(xQ,x1) h, cx2,x3J } v fj^fX^X.,} CX.,,X3) ) v 20 ' "3 [X2'X3] ^ v Le nombre ds colonnes requis dans le système matriciel est fonction du nombre de termes du cStâ droit de l'cTj^tijn ci-dessus car la génération de chaque terme nécessite une colonne. Cette diminution du nombre ds colonnes dépend de deux conditions. La première est que certaines des fonctions logiques possi- 25 Dles disponibles à partir de N variables soient redondantes. La seconde est nue, en traitant les variables de façon indépendante, on puisse procéder à une nouvelle répartition'ae celles-ci, :je tslle sorte que, au lieu aue X_ u et X. soient décodées dans la première matrice et X_, et X dans une seconde 1 i. o matrice, X„ 0_ „ puissent, par exemple, être décodées dans la première matrice u X 30 et XQ et X_ dans la seconde matrics. A^in a'illustrer la redondance- de certaines fonctions logiques, considérons la fonction suivante de quatre variacles qui a été disposée dans une table sous sa forme disjonctive normale. Comme il s'agit d'une fonction à auatre variables, il existe seize combinaisons possibles de variacles d'entrée. 35 La table comporte donc seize rangées, chacune desquelles est associée à une combinaison particulière des quatre variables d'entrée. La cinquième colonne représente les coefficients nisjonctifs normaux de ces combinaisons possibles: t bad origlnal» 70 44226 2072117 1D 15 20 xc X1 X2 X3 0 0 0 0 1 G G 0 1 G Q 0 1 0 1 0 1 1 1 0 1 0 D 1 G 1 c 1 1 Û 1- A l 0 0 0' 1 1 1 1 1 û G 0 D 1 0 G 1 G "1 0 1 0 . 1 1 0 1 1 0 1 1 Û 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 En conséquence, la fonction représentée par la .table ci-dessus est: F = v x0.xrx .X v X .X .X .X3-v 25 X .X .X .X v VX1-V*3 v ■X0*VX2**3V XQ.X1,X2.X3 v X0"X1*; Xq°XI*X2,X3 V Si l'on suppose que la fonction ci-dessus doit être réalisée à l'aide d'un système matriciel à partition du type représenté par la figure 2, dans leauel les variables XQ et X^ sont les entrées du décodeur 54 et les variables 35 X et X_ les entrées du décodeur 56, les sous-fonctions seraient réalisées C U comme indiqué ci«après! BAD ORIGINAL 70 44226 2072117 cxqx^ v X0X1 v XQX1) . cx2x3j v ( w . Tx2x3) v cx0j X0X1 v X0Xn3 * CX2V v (Y0*1 v Vi v X^ï . cx2x33 = g0CX2X3 ) V g-) cx2x3) v g2 Dans cette équation, le premier terme est généré dans la première colonne de la matrice 50, c'est-à-dire la fonction gQ, le second terme est généré dans la première colonne de la matrice 52, le troisième terme dans la seconde colonne de la matrice 50, c'est-à-dire, la fonction g^, le Quatrième terme 10 dans la seconde colonne de la matrice 52, et ainsi de suite. Il convient toutefois de noter que le premier et le septième terme de l'équation ci-dessus sont égaux, c'est-à-dire gQ = g^. Une fois cela admis, l'équation peut être réalisée avec trois colonnes seulement puisque la première et la dernière colonne peuvent être combinées, la fonction pouvant être écrite de nouveau 15 avec seulement trois termes de la façon suivante: F = gQ CX2X3 v X2X3) v g □ans cette dernière équation, les deux premiers termes peuvent etre générés dans une seule colonne de logique en emmagasinant une valeur de "un" supplémen-20 taire dans la quatrième cellule du registre 3&, de sorte que la fonction générée a partir de la ligne 108 de sortie de colonne est : X2X^ + *2*3" sorte, Dour générer cette fonction particulière, le système matriciel représenté sur la figure 2 peut Stre réduit d'une colonne et devenir une matrice à trois colonnes seulement. Cette réduction n'est possible qu'à cause de la 25 redondance qui existe dans la fonction ci-dessus. De telles redondances peuvent facilement être détectées grâce à la méthode suivante. La table décrite ci-dessus peut être transformée en une autre table dans laquelle les combinaisons possibles des variables XQ et X^ sont placées à gauche et les combinaisons oossibles des variables X2 et Xg au sommet 30 de la table, les coefficients de ces combinaisons étant placés au centre» soit: 35 X0X1 0 0 0 1 1 0 1 1 GQ 1 0 1 1 01 A \ 1 0 1 10 n 0 1 0 11 1 c 1 1 bad original1 70 44226 072117 10 15 Les redondances peuvent ainsi Être facilement détectées chaque fois au'une" colonne est identique à une autre colonne ou qu'une rangée est identique à une autre rangée. Dans la table reproduite ci-dessus, la première colonne est identique à la quatrième et il existe par conséquent une redondance. Cette dernière peut être supprimée de la façon.décrite ci-dessus et la fonction peut en conséquence être générée en n'employant que trois colonnes dans chaque matrice au lieu de quatre. Une autre raison pour laquelle le fait de traiter les variables de façon indépendante peut aboutir à une diminution du nombre requis de colonnes, est que les variables sont interchangeables» Par exemple, la variable X^ peut constituer une paire avec la variable X2 ou X3 x2x3 X0X1 0 0 0 1 CD 1 1 00 1 0 0 0 01 0 1 0 0 10 0 0 1 0 11 " 0 0 0 1 20 25 30 Lorsqu'on réunit les variables par paires dans la table ci-dessus, et par conséquent dans un système matriciel du type représenté par la figure 2, quatre colonnes sont nécessaires puisqu'il nexiste aucune redondance dans les colonnes ou dans les rangées. Toutefois, si les variables peuvent être réunies par paires de façon différente, c'est-à-dire X^ avec X2 et X^ avec X^comme dans la table ci-après, on peut voir que le nombre de colonnes contenant des valeurs de "un" peut être ramené à deux: X1*3 X0X2 0 0 0 1 1 0 1 1 00 1 0 0 1 01 0 0 0 0 10 0 0 0 0 11 1 0 0 1 . t. BAD ORIGINAL 13 70 44226 2072117 Il convient ds noter que dans les deux dernières tables ci-dessus les fonctions sont identiques, et que seule la façon de réunir les variables par paires a été modifiée. Il convient de noter également qu'il existe une redondance dans la table immédiatement ci-dessus et que, par conséquent, le nombre 5 de colonnes peut Stre ramené à une seule. Ainsi donc, en traitant les variables de façon indépendante, on a ramené le nombre de colonnes de quatre à seulement une. La figure 3 montre "l'amélioration obtenue en traitant les variables de façons indépendantes. Elle représente un additionneur binaire à deux bits 10 dont les entrées sont les opérandes A^ et Ë^, l'indice 2 représentant la position du bit d'ordre supérieur. Les deux sorties de données S,,. et S2» et la sortie de report C £ sont formées avec seulement cinq colonnes de portes logiques. Son fonctionnement d'ensemble est semblable à celui des matrices à partition représentées par la figure 2. Comme dans la figure 2, les quatre 15 variables sont décodées de façon indépendante en tant que paires de variables dans les décodeurs 120 et 122. Les matrices composites 123 et 130 comportent respectivement les registres à décalage 124 et 126. Chaque matrice composite se compose de portes ET disposées en colonnes ez en rangées, chaque colonne comportant quatre portes ET. Par conséquent, chaque registre d'emmagasinage? 20 quatre cellules associées à une colonne. Les fonctions de sortie de colonnes générées dans chaque matrice passent à travers les portes ET 132-140. Les serties des portes ET 134-13E et 136-14C traversent respectivement les portes CU 142 et 144. La somme ainaire du bit d'ordre inférieur est un "un" chaque fois que 25 l'une des entrées de bit d'ordre inférieur est un "un", c'est-à-dire chaque fois que A ou 6„ est un "un" mais non lorsque A.et' B. sont tous deux un "un" Il 11 Ceci est sifflement le OU exclusif de ces fonctions. En utilisant les techniques décrites ci-dessus, cette fonction peut être produite dans une colonne, mais seulement si les variables sont réunies par paires de la façon indiquée, c'est- 30 à-dire A avec B et A„ avec B„. 3n peut le constater en réunissant d'abord 1 12 2 par paires les variables de façon différente, par exemple de la façon indiquée dans la table ci-dessous: B.B2 1 0 0 0 1 1 0 1 1 00 0 0 1 1 01 0 0 1 1 10 1 1 0 0 11 1 1 0 0 bad original 70 44226 072117 10 15 Si l'on ne tient pas compte de la redondance qui existe entre la première et la seconde colonne,, et entre la troisième et la quatrième colonne, il faudrait quatre colonnes pour réaliser cette fonction OU exclusif.-Si l'on tient compte de cette redondance, la fonction peut Stre. réalisée en deux colonnes en mettant en facteur les termes comme indiqué.ci-après: .. v v - f - (BiB2 1A1A2 v 'CB1B2 ' v Dans cette équation, le premier et le second terme peuvent être générés dans -la première colonne, et le second et le troisième terme dans la seconde colonne. Toutefois, si les variables sont réunies par paires de façon différente, comme indiqué dans la table ci-dessous, la fonction OU exclusif peut être générée dans une seule colonne: . . ' a2b2 .. A.B. 1 1 : - 00 0 1 - - 1 0 - 1 1 - 00 0 0 0 0 01 1 1 1 1 10 1 1 1 1 11 0 0 0 0 20 25 30 La fonction OU exclusif peut maintenant être réalisée dans une seule colonne comme indiqué par l'équation suivante: F = tA1B1 v A1B1J CA2B2 V A2B2 v A2B2 v A2B2) Il s'agit en fait ici de la réalisation représentée dans la première colonne de la figure 3. Le premier terme de l'équation est généré par la première colonne de la matrice 128, A^ et B^ étant les variables d'entrée, et le second terme par la première colonne de la matrice 130, A2 et B2 étant les variables d'entrée. Ce résultat est obtenu en emmagasinant un "un" dans les première et troisième cellules du registre 124 et en emmagasinant un "un" dans chaque cellule du registre 126. Le nombre de colonnes nécessaire pour générer la somme binaire du second bit S2 et le report binaire de sortie CQU£ a de façon similaire été ramené de quatre colonne chaque à deux colonnes chaque. Bien que l'on ait décrit dans ce qui précède et représenté sur les dessins, les caractéristiques essentielles de l'invention"appliquées à un mode de réalisation préféré de celle-ci, il est évident que l'homme de l'art peut y ap-porter toutes modifications de forme où de détail cu'il juge utiles, sans pour autant sortir du cadre de ladite invention. BAD ORIGINAL 70 44226 15 2072117 REVENDICATIONS 1.- Procédé pour la partition d'opérations logiques effectuées à l'aide de matrices logiques généralisées produisant des fonctions logiques F.-F de 1 K N variables, lesdites N variables étant utilisées comme entrées auxdites ma-5 trices logiques, comprenant chacune plusieurs portes logiques ayant au moins deux bornes d'entrée et au moins une borne de sai'tie, un registre permettant d'emmagasiner le signal d'entrée prédéterminé pour chacune desdites portes, un décodeur d'entrée acceptant en entrée un nombre prédéterminé des N variables et produisant au moins un signal indépendant pour chacune des combinaisons 10 possibles dudit nombre prédéterminé de variables d'entrée, des moyens de connexion des entrées desdites portes logiques aux sorties dudit registre et dudit décodeur, des moyens d'interconnexion des sorties des portes d'une même colonne, le système ainsi réalisé permettant d'engendrer une fonction logique • de colonnes combinant des signaux du registre et du décodeur sur chaque colonne 15 de sorties de portes de chacune desdites matrices généralisées, ledit procédé comprenant les opérations suivantes: a. décodage indépendant d'un nombre U de variables dans une première matrice généralisée, U étant inférieur à M, b. emmagasinage de signaux adéquats dans le registre de la première 20 matrice généralisée de sorte que les sorties de colonnes correspondantes con~ tiennent des fonctions désirées desdites U variables, c. décodage indépendant d'un nombre V de variables dans une seconde matrice généralisée, V étant inférieur à N, d. emmagasinage de signaux adéquats dans le registre de la seconde ma-25 trice généralisée de manière telle que les sorties de colonnes correspondantes contiennent des fonctions desdites V variables, e. combinaison logique des sorties de colonnes desdites premières et secondes matrices généralisées pour engendrer les fonctions désirées de U + V variables, 30 f. décodage indépendant d'un nombre X de variables dans une troisième matrice généralisée, X étant inférieur à N, g. emmagasinage de signaux adéquats dans le registre de la troisième matrice généralisée de manière telle que les sorties de colonnes correspondantes contiennent des fonctions desdites X variables, 35 h. combinaison logique des fonctions de II + V variables enregistrées, avec les sorties des colonnes de ladite troisième matrice généralisée pour engendrer des fonctions désirées de U + V + X variables,. i. répétition des opérations ci-dessus, jusqu'à obtention de la fonction F de N variables désirées* 70 44226 '6 20721 17 2.- Procédé selon la revendication 1 caractérisé en ce que les groupes de variables tels que U, V et X sont égaux. 3.- Procédé pour partition d'opérations logiques effectuées avec un ensemble de matrices logiques généralisées, permettant de produire une fonction logique 5 F de N variables, lesdites N variables étant utilisées comme entrées desdites matrices logiques, comprenant chacune plusieurs portes logiques disposées en colonnes et rangées, chaque porte ayant deux bornes d'entrée, une borne de sortie, un registre à contenu variable permettant d'emmagasiner le signal d'entrée prédéterminé pour chacune desdites portes, un décodeur d'entrée ac-10 ceptant en entrée un nombre prédéterminé de N variables et produisant un signal de sortie indépendant pour chacune des combinaisons possibles des variables d'entrée, des moyens de connexion des entrées desdites portes logiques auxdites sorties dudit registre et dudit décodeur, des moyens d'interconnexion des sorties des portes d'une même colonne, le système ainsi réalisé permettant 15 d'engendrer une fonction logique de colonnes combinant les signaux du registre et du décodeur sur chaque colonne de sortie de portes de chacune desdites matrices généralisées, ledit procédé comprenant les opérations suivantes: a. décodage indépendant d'un nombre'U de variables dans une première matrice généralisée, U étant inférieur à N, 20 b. emmagasinage de signaux adéquats dans le registre d'une première matrice généralisée de sorte que les sorties des colonnes correspondantes contiennent une fonction désirée desdites U variables, c. décodage indépendant d'un nombre V de variables dans une seconde matrice généralisée, V étant inférieur à N, 25 d. emmagasinage de signaux adéquats dans le registre de la seconde ma trice généralisée de manière telle que les sorties de colonnes correspondantes contiennent des fonctions recherchées desdites V variables, e. répétition des opérations ci-dessus, jusqu'à ce que le nombre de variables décodées soit égal à M, 30 f. combinaison logique des sorties de colonnes desdites matrices logiques généralisées pour engendrer la fonction F de N variables recherchée.