Brevet FR2660476A1 — publié le 19911004

DISPOSITIF DE STOCKAGE ET DE CLASSEMENT DE DONNEES NUMERIQUES La présente invention se rapporte à un dispositif de stockage et de classement de données numériques. Pour le stockage de données numériques, il est courant d'utiliser des mémoires comportant un plus ou moins grand nombre de cases de stockage, chacune de ces cases étant définie par son adresse dans la mémoire. Dans le cas où l'on souhaite ordonner les données numériques qui sont stockées dans la mémoire, c'est à dire par exemple les classer par ordre croissant ou décroissant (sur tout ou partie de l'ensemble de bits qui constitue chaque donnée numérique), il est nécessaire d'examiner les cases une par une et de procéder au classement méthodique de leur contenu, ce qui constitue une procédure particulièrement longue et, quoi qu'il en soit, de prix de revient global plutôt élevé. L'invention vise à remédier à ces inconvénients. Elle se rapporte à cet effet à un dispositif de stockage et de classement de données numériques, ce dispositif constituant une pile systolique composée d'une série de cellules identiques mises en cascade et synchronisées par un même signal d'horloge, chacune de ces cellules comprenant au moins un premier registre auquel est appliqué le signal d'horloge un deuxième registre auquel est également appliqué ce signal d'horloge un comparateur qui peut recevoir d'une part la donnée numérique d'entrée de la cellule; et donc soit provenant de la cellule supérieure, soit, s'il s'agit de la première cellule de la pile, étant la donnée appliquée de l'extérieur à l'entrée de la pile, et qui peut recevoir d'autre part la donnée contenue dans le premier registre ; et un multiplexeur qui peut recevoir ces deux données et qui est commandé par le signal de sortie de ce comparateur de manière à diriger la plus grande des deux vers le premier registre pour y remplacer celle qui s'y trouve, et à diriger la plus petite des deux vers le deuxième registre, pour y remplacer celle qui s'y trouve, tandis que cette dernière est transférée vers la cellule inférieure dont elle constitue la donnée numérique d'entrée. De toute façon, l'invention sera bien comprise, et ses avantages et autres caractéristiques ressortiront, lors de la description suivante de deux exemples de réalisation de cette pile systolique, en référence au dessin schématique annexé dans lequel - Figure 1 est une synoptique d'ensemble d'une forme élémentaire de réalisation de cette pile systolique - Figure 2 représente une des cellules de la pile systolique selon la figure 1 ; - Figure 3 est une synoptique d'ensemble d'une forme plus perfectionnée de réalisation d'une telle pile systolique; - Figure 4 représente de même une des cellules de cette dernière pile systolique. En se reportant à la figure 1, ce dispositif se compose d'une série descendante de modules ou cellules identiques Ml, M2, M3,..., MN qui sont branchés en cascade et qui sont synchronisés par une horloge commune H. Il s'agit donc d'une pile "systolique", c'est à dire d'une pile faite d'une série de modules identiques et travaillant tous en même temps. Chaque module de la pile comporte une entrée E1, E2, E3,...EN, de données provenant d'une manière générale d'un registre du module précédent. Bien entendu, l'entrée E1 du module supérieur Mi de la pile constitue l'entrée des données nouvelles introduites dans cette pile. Par ailleurs, chaque module de cette pile possède un registre de sortie, dont les données peuvent être extraites de la pile en S1, S2, S3,..., SN. La figure 2 représente le module Mn, n étant un nombre entier compris en 1 et N. Ce module comporte deux registres, tous deux synchronisés par l'horloge H, dont un premier registre Rmax dont la sortie de données 10 est la sortie Sn du module, et un deuxième registre Rmin dont la sortie de données 11 constitue l'entrée En+l du module inférieur Mn+l (non représenté) de la pile. L'entrée En de ce module provient du module supérieur Mn-l de la pile, et est appliquée à la fois à une première entrée 12 d'un comparateur numérique 14 et à une première entrée 13 d'un multiplexeur 15 dont la borne de commande 16 reçoit le signal de sortie du comparateur 14. L'autre entrée 17 du comparateur 14 ainsi que l'autre entrée 18 du multiplexeur 15 reçoivent les bits de sortie en 10 du registre Rmax, soit Sn, de sorte que le signal en 16, qui indique quel est le plus grand des deux nombres En et Sn, agit sur le multiplexeur 15 pour aiguiller le plus grand de ceux-ci vers le registre Rmax, et le plus petit vers le registre Rmin, tandis que simultanément ce qui se trouvait dans Rmin est transmis en En+l vers l'étage inférieur de la pile, soit Mn+i. Finalement, au coup d'horloge H, l'entrée En est transmise en Rmax Si le contenu Sn de celui-ci lui est inférieur, et alors ce contenu initial de Rmax est transféré en Rmin, tandis que cette entrée En est transmise en Rmin Si elle est inférieure au contenu de Rmax. Dans l'un et l'autre cas, le contenu initial de Rmin descend vers l'étage inférieur, qui travaille pour sa part de la même façon et en même temps. En d'autres termes, la valeur En entrant dans le module Mn est comparée à la valeur Sn stockée dans le registre Rmax de ce module. Le multiplexeur 15 assure l'aiguillage de la donnée, Sn ou En, la plus petite vers le registre Rmin, tandis que la plus grande est mémorisée dans le registre Rmax. La valeur En+l sortant du registre Rmin est adressée à l'étage inférieur Mn+l Où un traitement identique est simultanément effectué. Une valeur entrant en E1 par le haut de la pile transverse donc, progressivement et au rythme de l'horloge H, les différents étages M1, M2,..., en descendant le long de la pile, jusqu'à son stockage dans le registre Rmax du module qui mémorisait, avant l'entrée de cette valeur, une valeur plus faible que cette dernière. Cette valeur plus faible est, au coup d'horloge suivant, dirigée vers l'étage suivant, selon toujours le même processus : les plus grands nombres restent, tandis que les plus petits descendent, jusqu'à trouver leur place exacte et ordonnée dans la pile. La pile, formée de la succession des registres Rmax, s'ordonne ainsi automatiquement d'elle-même à chaque coup d'horloge. Lorsqu'une nouvelle donnée E1 est entrée dans cette pile, elle est aussitôt comparée à la valeur maximale de la pile, qui se trouve nécessairement en haut de pile. Si elle est plus grande, elle est mémorisée dans le registre Rmax en haut de pile. Sinon, elle aborde l'étage suivant et une nouvelle donnée E1 peut être appliquée à l'entrée. On décrira maintenant une version plus perfectionnée de cette même pile, dans laquelle les modules successifs sont légèrement modifiés pour pouvoir lire, en série et par ordre décroissant, les valeurs stockées dans la pile. Ceci est réalisé, comme on le verra ci-après, en ajoutant à chaque module deux multiplexeurs qui permettent le déplacement des données vers le haut de la pile. En se reportant à la figure 3, cette autre pile systolique se compose d'une cascade descendante de modules identiques M'i, M'2, M'3,..., MIN. Ces modules diffèrent légèrement (voir figure 4) des précédents, et la sortie Su,..., S3, S2 de chaque module est appliquée au module supérieur M'N-i,..., M'2, M'i, tandis que la sortie Si du module M'i en haut de pile constitue la sortie de données de cette pile, qui sortent donc, comme on le verra ciaprès, en série et par ordre décroissant (c'est à dire les plus grands d'abord). En figure 4 est représenté le module M'n, n étant w'ew'e le/nombre entier, compris entre 1 et N, que pour la figure 2. Outre les registres Rmin, Rmax, ainsi que le multiplexeur 15 et le comparateur 14 de la figure 2, ce module M'n comporte deux multiplexeurs 19 et 20, qui selon la valeur du niveau continu de commande U/D qu'ils reçoivent sur leur borne de commande 21, 22, commutent sur leur sortie, respectivement 23 et 24, soit leur entrée de droite, respectivement 25 et 26, pour le niveau D, soit leur entrée de gauche, respectivement 27 et 28, pour le niveau U. Les entréeS 25 et 26 reçoivent respectivement l'entrée En provenant du module supérieur (voir la figure 2) et la sortie Sn du registre Rmax, cette dernière étant également appliquée (voir la figure 3) à ce module supérieur. La sortie 11 du registre Rmin constitue comme auparavant l'entrée En+l du module inférieur, et elle constitue l'entrée sur la borne 27 du multiplexeur 19. la borne 28 du multiplexeur 20 reçoit quant à elle la sortie Sn+l du module inférieur. Le fonctionnement du dispositif selon les figures 3 et 4 est le suivant En position D, les bornes 26 et 24 d'une part et 25 et 23 d'autre part sont interconnectées de sorte que, les sorties 23 et 24 étant respectivement appliquées à 12, 13 et 17, 18, on retrouve exactement le schéma de la figure 2 : la pile classe les données en ordre décroissant comme précédemment. Pour sortir les données de la pile, le niveau de commande est basculé sur U. Les bornes 23 et 24 sont alors respectivement reliées aux bornes 27 et 26. A chaque coup d'horloge H, le contenu du registre Rmin est alors comparé avec la sortie Sn+l du module d'en dessous, et le plus grand de ces deux nombres est placé en Rmax tandis que simultanément le nombre Sn qui était en Rmax est transféré, pour un traitement identique, vers le module du dessus. On remonte ainsi à chaque coup d'horloge le nombre qui est le plus grand des deux nombres du module M'n vers le module supérieur M'n-i. En Si sort donc à chaque coup d'horloge le plus grand nombre de la pile, de sorte que les données de la pile en sortent bien en série et par ordre décroissant. Comme il va de soi, l'invention n'est pas limitée aux exemples de réalisation qui viennent d'être décrits. C'est ainsi que cette pile systolique peut aussi être utilisée pour classer en ordre décroissant, à condition d'utiliser les cellules en sens inverse : les nouvelles données sont alors rentrées par le dessous de la pile, les plus petites se classant alors dans chaque registre Rmin, etc... On retrouve alors finalement, en regardant cette fois-ci du haut en bas, les données ordonnées, mais cette fois-ci dans les registres Rmin et non pas dans les registres Rmax. Une utilisation pratique de l'invention est donc un classement rapide de données. Ainsi, lorsque l'on a une série de données à classer, on la rentre (D) séquentiellement dans la pile systolique. Lorsqu'on la ressort (U), elle est classée (en ordre décroissant si on a pris la pile dans le sens direct, en ordre croissant si on l'a prise en sens inverse) . A noter que la taille des registres Rmax et Rmin est variable et que le classement peut être effectué sur une partie seulement des mots mémorisés. Par exemple on peut stocker la donnée d'un numéro de département et sa population en les classant par ordre de population croissant ou décroissant. REVENDICATIONS 1 - Dispositif de stockage et de classement de données numériques, caractérisé en ce qu'il constitue une pile systolique composée d'une cascade de cellules identiques (M1, .2...., MN) synchronisées par un même signal d'horloge (H)1 chacune de ces cellules comportant au moins un premier registre (Rmax) auquel est appliqué ce signal d'horloge (H) un deuxième registre (Rmin) auquel est également appliqué ce signal d'horloge un comparateur (14) qui peut recevoir d'une part la donnée numérique d'entrée (En) de la cellule, qui provient soit de la cellule supérieure soit, s'il s'agit de la première cellule de la pile, qui est la donnée extérieure entrée dans la pile, et qui peut recevoir d'autre part la donnée (Sn) contenue dans le premier registre (Rmax) ; et un multiplexeur (15) qui peut recevoir ces deux données (En, Sn) et qui est commandé par le signal de sortie (16) de ce comparateur (14) de manière à diriger la plus grande des deux (En Ou Sn) vers le premier registre (Rmax) pour y remplacer celle (Sn) qui s'y trouve, et à diriger la plus petite des deux vers le deuxième registre (Rmin) pour y remplacer celle (En+i) qui s'y trouve, tandis que cette dernière est transférée vers l'étage inférieur dont elle constitue la donnée numérique d'entrée. 2 - Dispositif de stockage et de classement selon la revendication 1, caractérisé en ce qu'il comporte en outre deux multiplexeurs (19, 20), commandés par un même signal (U/D) et qui, dans une première position (D) sont aptes à diriger ladite entrée de données (En) et le contenu (Sn) du premier registre (Rmax) vers le comparateur (14) , pour stocker et ordonner les données comme précédemment, tandis que, dans une seconde position (U), ils sont aptes à diriger vers ce comparateur (14) le contenu (En+l) du deuxième registre (Rmin) d'une part et le contenu (S,n+l) du premier registre de la cellule d'c#~~~fre # > o#.r# inférieure/, de sorte qu'ainsi le plus grand nombre (Sn) de la cellule remonte, à chaque coup d'horloge (H), vers la cellule supérieure et que par suite les données sortant de la pile (en S1) en série et par ordre décroissant. 3 - Dispositif de stockage selon la revendication 2, caractérisé en ce que les nouvelles données sont rentrées par le dessous de la pile, et se classent alors dans chaque deuxième registre (Rmin).