Brevet FR2673301A1 — publié le 19920828

CIRCUIT ET PROCEDÉ DE SÉL Er TION DES k PLUS GRANDES DONNEES D'UNE SUITE DE DONNEES La présente invention coexrne les circuits de tri de données selon un critère déterminé et en particulier un circuit permettant de sélectionner les k plus grandes données d'une suite de données arrivant séquentiellement. 5 Ces circuits de tri sont par exemple utiles dans le cadre de la compression d'image En effet, dans ce cadre, on cherche à transmettre un minimum de dones représentant le mieux possible une image On cherche en particulier à annuler des don- rnées selon un critère détermirné pour augmenter l'efficacité de10 compression en diminuant la complexité et le temps des traite- ments qui augmentent avec le nombre de données non nulles. Dans les systèmes de compression d'image, on déomrpose les images en blocs, de par exemple 8 x 8 pixels, auxquels on asso- cie des matrices dont chaque coefficient représente les informa-15 tions de luminance et de chrominanroe d'un pixel Ces matrices subissent, par exemple, une transformée cosinus discrète (DCT) à la suite de quoi on obtient des matrices transfornmées de même dimension qui présentent l'avantage d'avoir beaucoup de coeffi- cients pratiquement nuls. On a coistaté qu'en annulant un certain hombre des petits coefficients de la matrice transforme puis en lui faisant subir la transfornée cosinus inverse, on pouvait renstituer une image sans dégradaticn significative. Une première technique de l'art antérieur pour fournir les plus grands coefficients de la matrice transformée consiste à lire séquentiellement les coefficients et à les oemparer à une valeur de seuil pour annuler ceux qui scnt inférieurs au seuil. Cette technique présente 1 ' inconvénient d' annuler tous les coef- ficients d' une matrice s'ils sont tous petits; il en résulte une dégradation non nrgligeable de l'image reconstituée car les plus grands de ces petits coefficients correspcrxent à des informa- tions significatives Elle présente aussi 1 ' 'ir Kxvénient de n'annuler aucun des coefficients s'ils sont tous supérieurs au seuil et l'objectif de compression n'est alors pas atteint. Une deuxième technique consiste à ne garder qu'un hxo Libre détermir k des données les plus grandes Ainsi, on est sûr de ne pas annuler des valeurs petites qui sont quand mnne représentatives de l'image et de ne pas avoir à traiter plus de k donrées dans une étape ultérieure Jusqu'à présent les circuits de mise en oeuvre de cette deuxième technique présentent l' incn- vénient d'être oomplexes et relativement lents. La présente invention prévoit un procédé mettant en oeuvre cette deuxième technique d'uns façon particulièrament simple. Pour cela, la présente invention prévoit un procédé de sélection des k données de plus grande valeur dans uns suite de n données arrivant séquentiellaennt sous forme de signaux logiques bin& req, comprenant les étapes suivantes: a) écrire séquentiel- lement chacune des données dans l'une de N mémoires adaptées à recevoir chacue un mot oemprenant dans l'ordre des poids de bit décroissant: un premier bit d'inhibition, un deuxième bit de sélection, des troisièmes bits de la donnée, des quatrièmes bits correspondant à un rhombre représentatif du rarx d'arrivée de la donnée; b) mett Lre à 1 les premiers bits des N mots lors de l'arrivée du premier des signaux correspoxdant à la suite de données; c) lors de l'écriture de chacune des donées, mettre à zéro les premier et deuxième bits du mot correspoxnant; d) entre les arrivées des signaux cororespcdant à la (n- k)ème donnée et à la nrme donnée, détecter le plus petit des mots cxntenus dans les mémoires et mett Lre à 1 son deuxième bit; et e) dès l'arrivée des signaux correspoexxant à la né me donnée, lire séquentiel- lement les données mémorisées et traiter différemment celles dont le mot présente le deuxième bit à 1 et celles dont ce bit est à 0. Selon un mode de réalisation de la présente invention, à l'étape e) les données sont lues selon l'ordre de leur écriture à l'étape a). La présente invention prévoit aussi un circuit de sélection des k données de plus grande valeur dans une suite de n données présentées séquentiellement sur un bus d'entrée sous forme de signaux logiques binaires, comprenant: une matrice de points mémoire de N colonnes et m rangées, chaque colonne étant affectée à un mot correspcrdant à l'une des données et comprenant dans l'ordre des numéros de rangée croissants et des poids de bit décroissants: un premier point mémoire d'inhibition mis à un par un signal d'initialisation et mis à zéro par l'arrivée de la donnée, un deuxième point mémoire de sélection relié à une ligna d'un bus de sortie, mis à zéro par l'arrivée de la donnée, des troisièmes points mémoire reliés aux lignes du bus d'entrée de données et d'un bus de sortie de données, pour reoevoir et stocker la donnée, et des quatrièmes points mémoire contenant un rxnombre représentatif du rang d'arrivée de la donnée; un premier circuit pour adresser chacune des colonnes au rythme d'arrivée des données et y écrire la donnée présente sur les lignes du bus d' entrée; un deuxième circuit actif seulement entre l'arrivée de la (n-k)ême donnée et l'arrivée de la nrme donnée pour détecter le mot de plus petite valeur et mett Lre son deuxieme point mémoire à 1 dès l'arrivée de la donnée suivante; et un troisième circuit pour adresser chacune des coloonnes au rythme d'arrivée des données et écrire les bits contenus dans les deu- xième et troisièmes points mémoire sur les lignes du bus de 5 sortie de données dès l'écriture de la rme donném. Selon un mode de réalisation de la présente invention, le deuxième circuit est constitué de modules, chacun étant asso- cié à un point ménoire et oeoprenant: une liaison à la sortie Q du point mémoire associé, une sortie d'exclusion Xij, qui, si la rangée courante i est la dernière, est reliée à une entrée de mise à 1 du deuxième point mâéoire de la colcnne courante j, une sortie intermédiaire, une entrée d'exclusion reliée, ou bien à la sortie d'exclusion Xi -, j du module de la colonne courante j et de la rangée précédente i-l, ou bien à O si la rangée courante15 est la première, une entrée de détection reliée à la sortie Zi d'un moyen logique de détection Commun à tous les modules de la rangée courante j et reoevant en entrée les sorties interm-diai- res de oes modules; la sortie Xij prenant les valeurs résumées dans le tableau suivant o le symbole "#" désigne indifféremment20 O ou 1: zi Xi _,j xii # i 1 1 o o o i O Q la sortie intermédiaire prenant la valeur 1 si la sortie YX 1, est à 1 et/ou si la sortie Q est à 1. Selon un mode de réalisation de la présente invention, le moyen logique de détection fournit la valeur O à sa sortie Zi seulement quarnd toutes les sorties internméiai res des modules de la rangée courante j sont à 1. Selon un mode de réalisation de la présente invention, les circuits pour adresser chacuns des oelonnes sont constitués d'un registre à décalage. Selon un mode de réalisation de la présente invention, les deuxièmes points mnmoire sont autorisés à être mis à 1 par un signal de validation actif entre les arrivées de la (n-k)ième donnée et de la niame dcne. Un avantage de la présente invention est que la sélec- ticn des k plus grarndes dcnnées est terminée dès l'arrivée de la dernière doamée de la suite, alors que dans l'art antérieur on était obligé de trier et ranger les dontées par ordre décroissant dans une Mmsoire et de prendre ensuite les k premieres. Ces objets, caractéristiques et avantages ainsi que d'autres de la présente invention seront exposés plus en détail dans la description suivante de modes de réalisation particuliers faite en relation avec les figures jointes parmi lesquelles: les figures l A à 1 P illustrent des étapes successives du procédé selon la présente invention dans un cas concret; la figure 2 représente un schéma simplifié modulaire d'un mode de réalisation d'un circuit de sélection selon la présente invention; la figure 3 représente un schéma électrique d'un des modules de la figure 2; la figure 4 représente le chrcxgramfe des cycles de fon Dtioninnt des circuits des figures 2 et 3; et la figure 5 représente une modificaticn d'un des modules et du circuit de la figure 2 pour pallier un éventuel ir vent. Pour simplifier la compréhension, on va decrire le procédé selon l'invention à l'aide d'un exemple o Eoeret. Ccnsidérons la suite de 8 données suivantes: D = 1 1)= 5 D 3 = 7 D 4 = 8 D 5 = 5 DE = 4 D 7 = 8 D 8 = 2 et supposons qu'on veuille sélectionneor les k= 4 données plus grandes Il y a deux solutions: (D 4, D 7, D 3, D 2) ou (D 4, D 7, D 3, D 5); il faut donc supprimer 1 'une des données D 2 ou 15 On choisit ici de garder la donnée d'indice le plus petit, ici D 2- Pour oela, on forme de rnouvelles données D' à D'8 à partir des données Di à D 8 auxquelles on juxtapose à droite un coefficient15 de priorité n-j o N désigne le rxnombre de données de la suite (ici n= 8) et j le rang d'arrivée de la donnée considérée La suite de données modifiée est alors: D'l = 17 D'2 = 56 D'3 = 75 D'4 = 84 D'5 = 53 D'6 = 42 D'7 = 81 D'8 = 20 Ainsi on est sûr de n'avoir qu'une solution pour les quatre valeurs les plus grandes de la suite de données (D'2 = 56 est devenu plus grarnd que D'5 = 53) On notera qu'on a choisi ici des coefficients de priorité décroissants mais on aurait pu les30 choisir croissants pour garder les donnrées d'indioe le plus grand en cas d'ambiguïtés Ce point étant résolu, pour sélectionner les quatre plus grandes données, on procède comme expliqué ci- dessous. Dans toute la suite de la description, tout élément affecté de l'indice j correspxxd à la jième donée de la suite. Selon l'invention on associe à chaque donnée Dj en binaire un mot comprenant des bits supplémentaires à savoir, dans l'ordre décroissant de poids de bit, un bit d'inhibition Ij, un bit de sélection Sj, les bits de la donnée Dj, et des bits de priorité Pj Les bits Pl représentent en binaire un coefficient de priorité valant n-j (ici 8- j). Chacun des mots est placé dans une mémoire, par exemple selon une colonne Le contenu de la mémoire est illustré sous forme d'un tableau représenté aux figures l A à 1 P à différentes étapes de son remplissage, la première rangée représentant les états des bits I, la deuxième les états des bits S, la troisième les valeurs décimales des données D et la quatrième les valeurs décimales des coefficients de priorité P. La figure 1 A représente l'état de ce tableau dès l'arrivée de la première donée D 1 d'une suite de huit doenées. Le symbole "#" représente une valeur quelconque. Dès l'arrivée de la première doaée D 1, les bits I des 8 colonnes sont mis à 1 La première colonne est sélectionnée pour écriture, une colonne sélectionnée pour écriture étant indiquée par la lettre W en haut de la colonne La donnée Dl y est écrite et en même temps les bits I 1 et Si sont mis à zero. A l'arrivée de chacune des trois données suivantes D 2 à D 4 dans les figures l B à 1 D, les trois colonnes suivantes sont successivement sélectionnées pour écriture, les données y sont respectivement écrites, et les bits I et S correspcxnants sont mis à zéro. A la figure 1 E, la cinquième donnée D 5 est écrite dans le tableau de la même manière à la cinquième colonne A ce stade on détecte le plus petit mot dans les 8 colonnes, une détection étant représentée par une colonne encadrée Il s'agit forcment de l'un des mots des 5 premières colonnes puisque leurs prnemiers bits I sont à O alors que les premiers bits I des mots des autres colonnes sont à 1 Dans l'exemple choisi, c'est le mot de la première colonne, on met à 1 son bit de sélection Si dès l'arrivée de la donnee suivante Dr à la figure 1 F La mise à 1 est représentée par un 1 encadré Du fait de la mise à 1 du bit St du mot de la première colonne (le plus petit), celui-ci devient le plus grand parmi les cinq qui viennent d'être écrits et ne pourra plus être sélectionné comme le plus petit lors des comparaisons suivantes. Les données D 6 à D 8 sont écrites lors des étapes illustrées dans les figures i F à 1 H de la même manière aux colonnes 6 à 8 On détecte sucoessivement que les mots des colonnes 6, 5 et 8 sont les plus petits et on met à 1 leurs bits Sr, 55 et 58. Apres écriture de la dernière donnée Da, on ne détecte plus de plus petit mot dans les colonnes jusqu'à l'arrivée de la quatrième donnée d'une rxnouvelle suite de données. A la figure 1 H, en même temps qu'on écrit la donnée D 8, on commence la séquence de lecture des données Pendant l'écriture de la donnée D 8 et sept temps suivants, illustrés dans les figures l I à 10, on lit chacune des données dans l'ordre de leur arrivée avec le bit S correspondant Une colonne slectionnre pour lecture est indiquée par la lettre R en haut de la colonne Ainsi, le bit S marque par O les quatre données les plus grandes et par 1 les autres On peut ensuite, par exemple dans le cadre d'une application à de la compression d'image, annulrles données marquées par 1. Un insrxvénient peut résulter du fait que la première donrnée D soit la dernière donnée marquée par la mise à 1 du bit Si Dans ce cas, dans la figure 1 H, on lira la donnée Di avec son30 bit Si qui n'aura pas encore été mis à 1, car oe bit est mis à 1 au temps suivant dans la figure l I Dans les applications o le circuit de la présente invention est employé, ce cas ne se présente jamais car les premières données sont les plus grandes, notamment quand ce circuit traite des données provenant d'une transformée cosinus Toutefois, une solution à cet inconvénient sera proposé en figure 5. On remarquera qu'on peut conmer à écrire de nouvelles données dans les colonnes dès l'instant o on lit la deuxième donnée D 2 Ainsi, par exemple à la figure l I, on écrit la première donnée E 1 d'une suite de données F à Fe en même temps qu'on lit la donnée D 2 de la suite précédente et qu'on met à 1 le bit de sélection, ici 58, du dernier plus petit mot. L'arrivée de la donnée E force à 1 les bits I des 8 colonnes puis à O les bits I et S de la première colonne Aux figures 1 J à 1 P, on écrit les données E 2 à FE comme cela a été décrit pour les données D La donnée EF peut aussi arriver à n'importe quel instant ultérieur (voire après la lecture de la donnée D). Ce procédé est facilement généralisable pour sélectionner les k données les plus grandes dans une suite de n données Au lieu d'avoir huit mots et colonnes, on en aura N et la sélection des k plus petits de ces N mots est active après l'arrivée de la (n-k)ième donnée Apres l'arrivée de la nième donnée, la sélection est inactive et on aura marqué les n-k plus petites colonnes en mettant à 1 leurs bits S Ainsi il reste k colonnes marquées par un O dans leurs bits S orrespodlants, ce qui indique que les k plus grandes données y sont écrites. Pendant N temps suivants, les N données sont lues avec leurs bits S et on peut annuler celles marquées par un 1 dans les bits S. La figure 2 représente un nmode de réalisation parti- culier d'un circuit mettant en oeuvre le procédé décrit précédenenat Ce circuit comprend une matrice de modules de mémorisation et de traitement d'un bit Ainsi, dans le cas considéré précédemennt o l'on veut traiter des suites de n données, cette matrice comprendra N oolonnes, comme celles des tableaux des figures 1 A à l B En outre, cette matrice comprernd m rangées, le nombre m correspxdant au nombre de bits d'une colonne des tableaux précédannt décrits La première rangée comprernd des modules MI (MI 11 M Il j Mln) destinés aux bits d'inhibition I La deuxième rangée copnrend des modules MS (M 521 j M 52) destins aux bits de sélection S Les r rangées suivantes, r étant le nomnbre de bits d'une donnére à trai- ter, comprennent des modules MD (M 31 MD 3 j MD 3 N à MD 2 + r, 1 **M r+,r MD 2 +r,n) Les p dernières rangées compprennnt des modules de priorité MP (MP 3 + r, 1 - MP 3 + r MP 3 + r, N à M Pm 1M Pm j M Pm N) destins à conte- nir sous forme binaire les mots de priorité désignés par la lettre P dans les tableaux des figures 1 A à 1 P (p représente le nombre de bits nressaires au codage des nrmbres O à n-l). Dans la suite de la description, i est un indioe de rangée Chacun des modules comprend une entrée de bit (sauf les modules MP), une sortie de bit (sauf les modules MI et MP), une entrée d'exclusion, une sortie d'exclusion Xij, une entrée d'au- torisation de lecture (sauf les modules MP) et une entrée d'auto- risation d'écriture (sauf les modules MP) Les modules MI et MS conportent en plus une entrée SET de mise à 1 Les modules MP codent en binaire les coefficients de priorité de manière fixe. Pour chaque module d'une même rangée i, l'entrée de bit est reliée à une ligne I Ni d'un bus d'entrée, la sortie de bit est reliée à une ligne OU Ti d'un bus de sortie et la sortie d'exclusion Xi jest reliée à l'entrée d' exclusion du module de la rangée suivante i+l. Tous les modules d'une rangée i sont aussi reliés à une ligne commune Zi dont le rôle sera compris lors de l'explication de la figure 3. Pour chaque module d'une mnêe colonne j, l'entrée d'autorisation d'écriture est reliée à une ligne Wj d'un bus d'adresses d'écriture et l'entrée d'autorisation de lecture est30 reliée à une ligne Rj d'un bus d'adresses de lecture La première ligne de lecture Ri est reliée à la dernière ligne d'écriture Wn, oe qui entra înra la lecture de la première colonne et l'écriture de la dernière simultanément Les lignes W et R sont pilotées par un circuit d'adressage 11 de constitution classique, constitué par exemple d'un registre à décalage, Commanardé par une horloge CK et par un signal d'initialisatica INIT appliqué aussi sur la première ligne d'écriture W 1. Les entrées de bit des deux premières rangées sont reliées au niveau logique O (la masse) Les entrées d'exclusion des modules MI sont reliées au niveau logique O La sortie d'exclusion X j de chacun des modules M Pj de la dernière rangée est reliée à l'entrée D d'une bascule 10. Chacune des bascules 10 est du type D et oomporte une sortie inversée Q* reliée à l'entrée SET de mise à 1 du module MS de la olonne orrespndante, une entrée de validation reliée à une horloge CK et une entrée SET de mise à 1 reliée à une ligne de validation VAL o Aumunse à toutes les bascules 10. Ainsi, si l'on considère une colonne de la figure 2, chaque module MI, MS, MD et MP d'une colonne correspond notamment à un point mémoire propre à mnoriser un bit du mot contenu dans la colonns orrespoante des tableaux des figures l A à 1 P. Lors des phases d'écriture de données, telles qu'illus- trées dans les figures l A à 1 H, on écrit les donres successives dans les modules MD de colornes successives Les opérations de omparaison sont actives pour les k dernières dcnnées écrites. Chacun des modules MI, MS, MD et MP nopreanz, outre le point mémoire, une unité de traitemaient logique qui, en conbinai- son avec celle de tous les autres modules, effectue les opéra-25 tions expliquées précdemrnt, à savoir des opérations de compa- raison des valeurs des mots mnmorisés dans les colonnes et des opérations de sélection de colonne (Cette opération de sélection consistant à fixer le bit de sélection S du module MS de chacune des colonnes).30 Mais avant d'aborder le fonctionnement d'un module, décrit ultérieuramnt à l'aide de la figure 3, on va claircrir le fonctionnement de l'ensable de ces modules dans une opération de ooparaison et de sélection qui sera mieux comprise en reprenant l'exemaple oncret utilisé en relation avec les figures l A à 1 P. On a représenté ci- dessous le contenu des points mémoire des modules du circuit de la figure 2 correspoxdant à l'état de l'étape de la figure 1 G. 1 2 3 4 5 6 7 8 MI, 00000001 N 1021000010 o Mr O O 1 O O 1 MD 4 01 1 01 O O f MD _ 0 1 O O 1 O _ MD 6 111010 # MP 7 11110000 MP 8 1 1 O O 1 1 O MP 9 1 O 1 O 1 O 10 On supposera, pour simplifier les explications, qu'on analyse séquentiellement les modules rangée par rangée en partant de la première Pour cela, on regarde d'abord les modules dans la20 première rangée Les modules contenant un 1 (ci-dessus celui de la colonne 8) corresponrtont forcement aux mots les plus grands et chacun de oes modules fournira au module inférieur par sa sortie d'exclusion un bit d'exclusion (représenté ci-dessus par un chiffre souligné) qui se propagera vers le bas de module en25 module pour exclure la olone correspoixxnte des analyses suivantes On procède ainsi pour les rangées suivantes et l'on pourra dncc identifier le mot pour lequel aucun bit d'exclusion n'apparaît dans la rangée la plus basse comme le plus petit A la suite de oette identification on marquera d'un 1 le bit de30 sélection de oe mot. Bien entendu, ce circuit doit tenir compte de quelques combinaisons logiques supplémentaires à savoir qu'aucun bit d'exclusion ne doit être émis dans le cas o, pour toutes les colonnes non precdemmaent exclues, tous les modules d'une mêmne rangée contiennent un 1 (par exemple cidessus les modules MD 42, MD 43 et MD 45 puis les modules MD 62 et M 65 puis le module MP 85 et finalement le module MP 95). Toutes ces opérations sont effectuées grâce à la contribution de chacune des unités de traitement logique contenues dans les modules. La figure 3 représente un des modules sous la forme d'un schéma logique. Un point mémoire constitué d'une bascule 20 du type D comprend une entrée D de bit reliée à une des lignes IN; une entrée de validation reliée à une des lignes d'écriture Wj; une sortie Q reliée à une des lignes OU Ti par l'intermédiaire d'une porte trois états 21 activée par son entrée de comnnade reliée à une des lignes de lecture Rj; et une entrée SET de mise à 1 dans le cas des modules MI et MS Les modules MP ne comportent pas de bascule et les fils qui correspondraient aux sorties des bascules sont reliées soit à la masse (O logique), soit à la tension d'alimentation Vcc ( 1 logique) pour former en binaire les coefficients de priorité n-j. Une porte OU (OR) 22 reçoit la sortie Q de la bascule et la sortie d'exclusion Xi -1 du module de la ligne précé- dente La sortie de la porte OU 22 alimente la grille d'un tran- sistor MOS à canal P 23 dont la source est reliée à la tension d'alimentation Vcc et dont le drain est relié à la ligne Zi Un moyen résistif 24 (un seul par ligne) relie la ligne Zi à la masse L'ensemble des transistors MDS 23 d'une même rangée et le moyen résistif 24 constituent une porte NMN ET Cette porte NON ET a pour sortie la ligne Zi et chacune de ses entrées est reliée aux sorties des portes OU 22 de la mêmne rangée On peut oonsidé- rer la porte NON ET comme un détecteur de zéro qui fournit à sa sortie un 1 quand au moins une de ses entrées est à 0 Une porte ET (AND) 25 est connectée en entrée à la sortie Q de la bascule et à la ligne Zi Une porte OU (OR) 26 reçoit la sortie de la porte ET 25 et la sortie d'exclusion Xi,j du module précédent La sortie de la porte OU 26 constitue la sortie d'exclusion Xij. Un module fncxtionne de la manière suivante. Un 1 présent sur son entrée d'exclusion (Xil,j=l) indique que la colonne est à exclure des analyses, c'est-à-dire qu'un bit à 1 a été détecté dans au moins un des modules de la colonne dans les rangées précédentes Ce 1 est présent sur l'une des entrées de la porte OU 26 et est transmis à la sortie de cette porte, qui Xonstitue la sortie d'exclusion Xij Ainsi, chaque module satisfait à la fonction de transmission directe d'un bit d'exclusion produit par un module antérieur de la même colonne. Si un O est présent sur l'entrée d'exclusion (X.j,j = 0), ceci signifie que la colonne à laquelle appartient le module considéré n'a pas encore été identifiée coere comprenant un mot plus grand que celui ou ceux contenus dans au moins une autre colonne Le contenu Q de la bascule 20 est preésent sur l'une des entrées de la porte ET 25 et est transmis à la sortie de cette porte, et aussi à la sortie Xi j à travers la porte OU 26, seulement si la ligne Zi reliée à l'autre entrée de la porte ET 25 est à 1 Ceci veut dire que si le contenu Q de la bascule 20 est à 1, on détecte pour la première fois que la colonne à laquelle appartient le module considéré est à exclure des analyses, si toutes les autres bascules des modules de la même rangée ne recevant pas un bit d'exclusion ne sont pas également à 1. La ligne Zi est forcée à 1 par l'un quelconoque des modules d'une mome rangée dont le transistor MFS 23 est conduc- teur, c'est-à-dire dont la porte CU 22 a sa sortie à 0 Ceci se produit seulement si l'entrée d'exclusion et le contenu de la bascule sont à 0, ce qui signifie que la colonne à laquelle30 appartient le module considéré contient forcément un des plus petits mots. La ligne Z, est forcée à O par le moyen résistif 24 seulement si tous les transistors MDS 23 des modules d'une même rangée sont bloqués Ceci se produit quand chacun des modules de la rangée a son entrée d'exclusion à 1 ou le contenu de sa bascule 20 à 1 Ceci se présente dans le cas o tous les modules de la rangée et dans des colonnes non exclues contiennent un 1 dans leur bascule 20 Dans ce cas, toutes les sorties des portes5 E Tr 25 des modules de la rangée sont à O et oe O est transmis aux sorties d'exclusion de tous les nmdules de la rangée se trouvant dans des colonnes non exclues. Sachant que la ligne Zi d'une rangée i est à O seulement si chacun des modules de la rangée i a son entrée d'exclusion à 1 ou le contenu de sa bascule 20 à 1, on peut résumer les valeurs que prend la sortie d'exclusion Xij d'un module se trouvant à la rangée i et à la colonne j par le tableau suivant: Zi Xi-1,j xij 0 0 0 1 O Q Les trois colonnes représentent respectiverent les valeurs que prennent la ligne Zi, la sortie d'exclusion du module de la rangée précédente i-1 et de la même colonne j, et la sortie d'exclusion Xij du module cxonsidéré Le symbole "#" représente25 indifféremment O ou 1 et Q désigne le contenu de la bascule 20 du module considéré. Outre oes fonctions de calcul, chaque module effectue les opérations d'écriture et de lecture suivantes. Un 1 présent sur la ligne Wj qui est reliée à l'entrée de validation de la bascule 20 permet de charger dans la bascule le bit present à ce moment là sur la ligne I Ni reliée à l'entrée de bit D de la bascule Un 1 présent sur la ligne de lecture Rj qui est reliée à l'entrée de cammande de la porte trois états 21 permet la transmission du contenu Q de la bascule sur la ligne35 OU Ti reliée à la sortie de la porte trois états 21. On constate ici que de par leur constitution, tous les modules fonctionnent en continu et simultanément pour rechercher comme on l'a expliqué précésdaeent la colonne contenant le plus petit mot, leurs sorties d'exclusion oscillant puis se stabilisant à des valeurs fixes à uninstant ultérieur à l'arrivée d'une donnée et antérieur à l'arrivée de la donnée suivante. Certains points qui restent à éclaircir, notament la façon dont sont séquecees les opérations du circuit de sélection de la figure 2, seront expliqués dans la suite. La figure 4 représente un chrcngraime o CK désigne le signal d'horloge; INIT le signal d'initialisation appliqué à la ligne W 1 et en entrée du circuit d'adressage 11; VAL le signal de validation appliqué à la ligne de validation; Din les instants d'apparition de chacune des données Dj sur les lignes I Ni du bus d'entrée; et Dout les instants d'apparition de chacune des données Dj à la sortie du circuit sur les lignes OU Ti du bus de sortie. Initialement, le signal INIT est à O et le signal VAL est à 1, les signaux Din et Dout sont quelconques Dès l'arrivée de la première donnée DL d'une suite de données, le signal INIT passe à l'état haut perndant une période d'horloge en autorisant l'écriture de la donnée DE dans les modules MD de la première colonne; les bascules des modules MI de la première rangée sont mises à 1 et on initialise le circuit d'adressage 11 Au prochain front montant du signal d'horloge oerresprodant à l'arrivée de la donnée suivante D 2, le circuit d'adressage présente un 1 sur la ligne W 2 pendant une période d'horloge, ce qui autorise l'écri- ture de la donnée D 2 dans les modules MD de la deuxième colcnne et ainsi de suite jusqu'à l'écriture des N données successivement dans chacun des ensembles de modules MD 1 i à M Di, Dès l'arrivée d'une des données, tous les modules de la matrice se mettent à calculer la colonne contenant le plus petit mot et un O apparait à la sortie d'exclusion du dernier module de cette colonne. Entre temps, dès l'écriture de la (n-k)ième donn, le signal VAL passe à l'état bas jusqu'à l'écriture de la rnme donnée Pendant cet intervalle de temps, les bascules 10 sont actives, c'est-à-dire que leurs sorties Q* ne sont plus forcées à O par le signal VAL et qu'elles prennent en compte les bits présents sur leurs entrées; notamment au prochain front montant de l'horloge (dès l'arrivée de la donnée suivante), la bascule 10 de la colonne contenant le mot le plus petit transmet à sa sortie Q* un 1 mettant le module MS correspnxdant à 1. Dès l'écriture de la dernière donnée dans les modules MD de la dernière colonner, le circuit d'adressage 11 autorise le transfert de la première donnée D 1 ainsi que du bit de sélec- tion Si stockés respectivement dans les modules MP 31 à M 2 + rl et Mf E sur le bus de sortie de données, et ainsi de suite jusqu'à la15 lecture des modules MD et MS de la dernière colcnne. La figure 5 illustre une modification simple du circuit de la présente invention, permettant de pallier l'irxnvénient précédemment mentionnér selon lequel, lorsque la première donnée Di est la dernière donnée marquée, le bit de marquage 51 de cette donnée Di n'est pas encore forcé à 1 alors que ce bit de marquage et la donnée Dl sont lues A la figure 5 on a représenté partiel- lement le circuit d'un module FM 521 modifié, le dernier module M Pm 1 et la bascule 10 de mise à 1 du module Mi E Entre la porte trois états 21 et la sortie de la bascu- le 20 du module M 521, on a inséré une porte OU 50 recevant sur une entrée la sortie de la bascule 20, et sur une autre entrée le bit d'exclusion Xml provenant du module M Pml par l'intermédiaire d'un inverseur 51 Le foncrticonement sera mieux compris à l'aide des figures 1 H et 4.30 Dès que la dernière donnée D 8 est écrite, la cmparai- son débute et, peu de temps après, un bit d'exclusion Xml égal à O apparaitra à la sortie du module M Pml irndiquant que la donnée D 1 doit être marquée La mise à 1 de la bascule de marquage 20 n'aura lieu qu'au prochain front montant de l'horloge CK quand le bit d'exclusion XY= sera transféré à la sortie inversée Q* de la bascule 10 En même tesmps on effectue la lecture de la dorne DE et du module 21 La ligne de lecture Ri est mise à 1 et la porte 21 transmet sur la ligne OJT 2 la sortie de la porte UJ 50. Caome dans ce cas la bascule 20 n'est pas encore à 1, la sortie de la porte OU 50, et donc la ligne OUT 2, s'établira à 1 quand le bit X 1, s'établira à 0 Ainsi, le bit de marquage Sl présenté sur la ligne OUT 2 s' établit un certain temps après l' établissement des bits de la due D 1 sur les autres lignes CMT, mais, comme10 en général ces bits sont pris en ccmpte par le circuit qui les utilise au prochain front deserndant de l'horloge CK, ce retard, étant inférieur à la demi-période d'horloge, n'induira pas d' elrreur. Un circuit facile à réaliser par l'hcmmne du métier peut être placé après le circuit de la figure 2 pour annuler les données marquées par un 1 dans leurs bits de sélection S correspodants. On notera qu'on peut caenoerr à écrire la première donnée d'une rnouvelle suite de donées alors qu'on est en train de lire les données d'une ancienne suite de données. On notera aussi que le circuit du mode de réalisation de l'invention décrit en relation avec la figure 2 est un circuit du type systolique o chacun des modules constitue une systole. Ce genre de circuit est d'une intégration facile car son routage25 est simplifié. De plus, on peut monltrer que la durée de sélection de la plus petite des N colonnes est proportionnelle à Tz + (m-l)TM, o Tz désigne le temps d'établissaeent d'un bit sur une ligne Z, m désigne le nmnbre de modules dans une coloene et TM désigne le temps de calcul d'un module Cette durée est particulièrement brave. L'invention a été décrite dans le cadre d'un traitement d'image, mais elle s'applique partout o aon a besoin de sélectionner les k plus grandes ou plus petites données dans un ensemble de données.5 Le circuit logique représenté à la figure 3 est donné à titre d'exemple Bien entendu, on peut obtenir les mêmes fcrtions avec un grand nombre de circuits logiques différents. Les fnctions de ces circuits peuvent aussi être réalisées avec un micropro esseur convenablement prograxrm associé à des10 mémoires. Les modules de priorité MP aont été décrits un contenu fixe, mais celuici peut tout aussi modifiable comme le contenu des autres modules, pour ordres de priorité variables. comme ayant bien être obtenir des REVENDICATIONS 1 Procédé de sélection des k données de plus grande valeur dans une suite de N données arrivant séquentiellement sous forme de signaux logiques binaires, caractérisé en ce qu'il omeprend les étapes suivantes: 5 a) écrire suentiellemnt chacune des données dans l'une de N mémoires adaptées à recevoir chacune un mot comprenant dans l'ordre des poids de bit décroissant: un premier bit d'inhibition (Ij), un deuxième bit de sélection (Sj), des troisièmes bits (Dj) de la donnée, des quatrièmes bits (P) correspoxdant à un nombre représentatif du rang d'arrivée de la donnée; b) mettre à 1 les premiers bits (Ij) des N mots lors de l'arrivée du premier des signaux o Drrespcndant à la suite de données; c) lors de l'écriture de chacune des données (Dj), mettre à zéro les premier (Ij) et deuxième (Sj) bits du mot oorrespomdant; d) entre les arrivées des signaux correspoxdant à la (n-k)éme donnée et à la rÈme donnée, détecter le plus petit des mots contenus dans les mémoires et mettr Le à 1 son deuxième bit (Sj); et e) dès l'arrivée des signaux correspodant à la néme donnée, lire séquentiellement les données mémorisées et traiter différemment oelles dont le mot présente le deuxième bit (Sj) à 1 et celles dont oe bit est à 0. 2 Procédé selon la reverndication 1, caractérisé en e qu'à l'étape e) les données sont lues selon l'ordre de leur écriture à l'étape a). 3 Circuit de sélection des k données de plus grande valeur dans une suite de N données présentées séquentiellement sur un bus d'entrée sous forme de signaux logiques binaires, caractérisé en ce qu'il comprend: une matrice de points mémoire ( 20) de N colonnes et m rangrées, chaque colonnar étant affectée à un mot correspconant à l'une des données et omprenant dans l'ordre des numre os de rarnée croissants et des poids de bit décroissants: un premanier point mémoire d'inhibition (MI) mis à un par un signal d'initialisaticn (INIT) et mis à zéro par l'arrivée de la donnée,. un deuxième point mémoire de sélection (MS) relié à une ligne d'un bus de sortie, mis à zéro par l'arrivée de la donnée, des troisièmes points mémoire (MD) reliés aux lignes du bus d'entrée de données et d'un bus de sortie de données, pour reevoir et stocker la donnée, et des quatrièmes points mémoire (MP) contenant un nombre représentatif du rang d'arrivée de la donnée,; un premier circuit pour adresser chacune des colonnes au rythme d'arrivée des données et y écrire la donnée présente sur les lignes du bus d'entrée; un deuxième circuit actif seulement entre l'arrivée de la (n- k)ème donnée et l'arrivée de la rnéme donnée pour détecter le mot de plus petite valeur et mettre son deuxième point mémoire à 1 dès l' arrivée de la donnée suivante; et un troisième circuit pour adresser chacune des colonnes au rythme d'arrivée des données et écrire les bits contenus dans les deuxième et troisièmes points mémoire sur les lignes du bus de sortie de données dés l'écriture de la nérm e donnée. 4 Circuit selon la revendication 3, caractérisé en oe que le deuxième circuit est cnstitué de modules, chacun étant associé à un point mémoire et oomprenant: une liaison à la sortie Q du point mémoire associé, une sortie d'exclusion Xij, qui, si la rangée courante i est la dernière (m), est reliée à une entrée de mise à 1 du deuxième point mémoire de la colonne courante j, une sortie interédiaire, une entrée d'exclusion reliée, ou bien à la sortie d'exclusion Xi lj du module de la colonne courante j et de la rangée précédente i-l, ou bien à O si la rangée courante est la5 première, une entrée de détection reliée à la sortie Zi d'un moyen logique de détection ( 23, 24) commun à tous les nmodules de la rangée courante j et recevant en entrée les sorties intermé- diaires de ces modules;10 la sortie Xij prenant les valeurs résunées dacns le tableau suivant o le symbole "#" désigne indifférement O ou 1: zi X 1-,i Xi i # 1 1 0 0 0 1 O Q 1 O Q la sortie intermédiaire prenant la valeur 1 si la sortie X l j 1 est à 1 et/ou si la sortie Q est à 1. Circuit selon la revendication 4, caractérisé en ce que le moyen logique de détection fournit la valeur O à sa sortie Zi seulement quand toutes les sorties intermédiaires des modules de la rangée ourante j sont à 1. 6 Circuit selon la revendication 3, caractérisé en ce que les circuits pour adresser chacune des olonnes sont constitués d'un registre à décalage. 7 Circuit selon la revendication 3, caractérisé en ce que les deuxièmes points mémoire sont autorisés à être mis à 1 par un signal de validation actif entre les arrivées de la (n-k)ième donnée et de la rnièe donnée.