FR 2027737 A1 19701002 FR 6945786 A 19691230 69 45786 1 2027737 La présente invention concerne la recherche d'information et plus particulièrement une technique nouvelle à commande électronique pour effectuer des recherches dans des index lisibles à la machine. Actuellement les informations de toute sorte sont recherchées a une vi-5 tesse toujours croissante. Il y a souvent un ralentissement du traitement par le fait que l'on ne peut rechercher rapidement un bloc d'information dans la masse d'information dans laquelle il est enterré. Bien que beaucoup de recherches aient été faites sur la recherche d'informatiorr on n'a pas trouvé jusqu'à présent de solution globale bien que de nombreuses techniques de recherche 10 d'information compliquée aient été conçues pour accéder à l'information impliquant un grand nombre de documents ou enregistrements. Dans le domaine de la recherche d'information, l'invention concerne un moyen permettant de commander une machine pour localiser l'information indexée par clés. Tous types de clés disposées dans une séquence ordonnée peuvent être 15 converties en une forme de clés comprimées et ces clés comprimées peuvent être recherchées par la présente invention. A chaque clé comprimée peut être associée une indication de l'emplacement d'un ou plusieurs blocs d'information qu'elle représente. L'information d'emplacement peut être une adresse, un indicateur, ou une autre forme obtenue à partir de la clé par un moyen qui ne 20 fait pas partie de l'invention. La présente invention concerne un algorithme qui permet d'améliorer la vitesse de recherche dans un index ordonné en effectuant cette recherche dans une forme comprimée de l'index. De nombreux procédés différents et des moyens pour effectuer une recher-25 che dans un index non comprimé, sont connus et ont été décrits par le passé. La recherche dans un index non comprimé, est réalisée électroniquement avec des ordinateurs en utilisant des procédés d'accès spéciaux, des moyens de commande et des catalogues. On pourra se référer aux brevets américains n° 3 409 631, 3 366 926, 3 242 470 et 3 030 609 et au brevet français n° 1 412 027 30 déposé par la demanderesse en FRANCE le 24 septembre 1364. La recherche d'information par ordinateur est limitée d'un certain nombre de manières,parmi lesquelles on peut citer la capacité très grande de la mémoire nécessaire. Il résulte du format de clé non comprimée que l'on a à balayer un grand nombre de multiplets pour chaque introduction de clé en re-35 cherchant un argument de recherche. C'est une opération qui prend du temps et qui est coûteuse lorsqu'on recherche dans un index long ou lorsqu'on recherche plusieurs fois dans un index court. C'est ce problème qui est résolu dans la présente invention, qui permet de réduire le nombre de multiplets balayés par entrée de clés dans un index recherché. Il en résulte une réduction de la 40 capacité de la mémoire et une recherche plus rapide à cause de la réduction 69 45786 2 2027737 du nossbre de multiplets qui doivent êt;c& détectés par la maahlne.. Il en résulte aîiàsî uns augmentation importants qs la ViïSa&a cîs la r&cfrercfie sans changement de la vitesse de l'ordinateur. Las techniques de recherche: dans les ©.rdïi'îaieurs. électroniques telles que 5 celîôà décrites dans, les brevets cités utilisai des clés non comprimées qui accompagnent les enregistrements sur un diéqu* au ïambour pour indexer l'information contenue dans un enregistraient astaelà. Une recherche pour.2'enregistrement associé peut être réalisée* sait par la clé, soit par l'adresse de î ' enregistrement « Par exemple dans les. brevets américains-n° 3 350 693, 1t, 3 34d 134, 3 344 402, 3 344-403 et dana 2* français n° 1 450 6S4 dêposâ par le demanderesse en FRANCE le 23 sep*esiiîrâ (9SS, une clé: non esfnprisaée peut être indexée sur un disque d'enregistrement magnétique.. Une clé peut être balayée électroniquement par un argument de recherche pour trouver une condition égalité-différence. Après avoir trouve la condition différence-égalité, un 15 indicateur d'adresse associé à la clé non comprimée est obtenu et utilisé pour rechercher l'enregistrement représenté par la clé qui peut se trouver n'importe ou sur le disque. Cet indicateur d'adresse peut par exemple comprendre l'emplacement sur le disque ou autre dispositif ou est enregistré l'enregistrement. L'ordinateur accède alors automatiquement à l'enregistrement adressé. Après 20 avoir été localisé l'enregistrement peut être utilisé pour n'importe quelle fonction. L'invention concerne la recherche dans un index ordonné de forme comprimât* » La forme comprimée supprime l'information redondante attribuabls à la nature de l'index. 2b Les recherches de l'art antérieur pour- la suppression de la redondance ne se sont pas intéressées à la suppression oe la redondance résultant de la mise en ordre. On trouve des exemples de diverses techniques de compression dans les brevets américains n° 2 9 78 535 et j ^2S 333 concernant les signaur. de télévision convertis en digits, dans le brevsi français n° 1 146 32? déposé 30 par îa demanderesse en FRANCE le 24 octobre 't3'ùn ai dens le brevet américain 1 237 327 concernant le comptage du i«asun'-a -às i/â^siCiasrds. entre les parties successives d'un signal de communication digital dans le brevet 3 237 170 pour coder des configurations de bits répétitifs dans le brevet américain 3 275 968 qui concerne des commandes qui ne contiennent que 1a partie qui est changée par 35 rapport à la commande restante, dans le brevet américain n° 3 223 962 qui concerne l'utilisation de la partie modifiée d'une adresse par rapport à l'adresse précédente, dans le brevet américain n5 3 278 907, qui concerne la compression dans le temps de signaux radars doppier et dans le brevet français n3 1 460 924 déposé par la demanderesse en FRANCE le 26 octobre 1965 qui coa-40 cerne une technique pour réduire les données de test. BÂD ORIGINAL 69 45786 3 2027737 La plupart des brevets précédents concernent des techniques de compression de données qui sont réversibles. C'est-à-dire, elles permettent de comprimer les données, de les transmettre et de reconstruire les données non comprimées initiales à partir des 5 données comprimées reçues, La réversibilité n'est pas une condition nécessaire dans la présente invention, car la compression d'index a comme, objectif principal d'augmenter la vitesse de recherche avec une mémoire de capacité inférieure. Par conséquent un objet de cette invention est de réaliser un procédé 10 et un système qi permettent de rechercher rapidement un index comprimé dans lequel est supprimée une partie ou toute la redondance due à la mise en ordre. Un autre objet de cette invention est de trouver un procédé de recherche de clés et un système qui permette d'explorer un index comprimé pour réduire le nombre de multiplets nécessaires à balayer par la machine pendant une 15 recherche, comparé au nombre de multiplets, balayés dans une recherche analogue avec l'index non comprimé correspondant. Ceci augmente la vitesse de " recherche de la machine par rapport à la vitesse de recherche de l'index d'origine non comprimé ordonné, pour la même fréquence de multiplets dans la machine. 20 Un autre objet de cette invention est de rechercher un index comprimé dans lequel la dimension de chaque entrée de clé est indépendante de la longueur de la clé non comprimée correspondante. Par exemple, une clé non comprimée qui contient 100 ou 1000 multiplets peut être représentée par une clé comprimée ayant un seul multiplet dans l'index comprimé. La valeur de la 25 compression dépend principalement du "resserrement" de l'index c'est-à-dire de l'importance des variations dans la relation oddonnée parmi l,es clés non comprimées de l'index. L'invention utilise un format de clé comprimée qui identifie les emplacements limites des multiplets qu'il peut comprendre par rapport aux positions 3Q des multiplets dans la clé non comprimée à partir de laquelle il est obtenu. Le nombre des multiplets de la clé dans une clé comprimée peut aussi être obtenu à partir du format de la clé comprimée. Une réalisation particulière de ce format utilise un champ dans chaque clé comprimée qui détermine le nom-- bre des multiplets de la clé et la position de son multiplet d'ordre supérieur 35 dans la clé non comprimée correspondante. Des adresses indicatrices et des données peuvent être associées à leurs clés comprimées respectives en étant positionnées à cBté de'leurs clés respectives. Un autre objet de cette invention.est de rechercher un index comprimé ayant un tel- format. un autre objet de l'invention est de rechercher un index comprimé indé 69 45786 4 2027737 pendamment du fait que le nombre de multiplets de la clé, est minimum ou non. L'invention utilise un dispositif de comparaison électronique pour comparer des multiplets de clés comprimées particulièrement sélectionnées par 5 l'invention. Un compteur d'égalité est aussi utilisé dans cette invention pour commander le processus de recherche. Au commencement de la recherche, le compteur d'égalité est mis aux conditions initiales par exemple à zéro. Sa valeur est comparée à un champ "facteur" dans le format particulier de chaque clé comprimée de la réalisation décrite ici.Le champ "facteur" concerne le 10 nombre de multiplets égaux dans un couple de clés non comprimées à partir duquel la clé actuelle ou la clé antérieure est obtenue. Avec un indice de compression maximum, certaines clés comprimées peuvent ne contenir aucun multiplet de clé mais elles ont néanmoins un champ "facteur" identifiant un nombre de multiplets égaux qui est obtenue à partir du couple de clés non com-15 primées correspondant. La comparaison entre les valeur dans le compteur d'égalité et le champ "facteur" détermine si la valeur dans le compteur est soit inférieure, soit égale, soit supérieure au champ "facteur". Si la valeur dans le compteur est inférieure la recherche se poursuit et elle peut passer immédiatement à la clé 20 comprimée suivante. Si la valeur dans le compteur est supérieure, la recherche est terminée avec la clé comprimée en cours. Si la valeur dans le compteur est égale chaque multiplet de la clé dans la clé comprimée en cours est comparé à un multiplet de recherche pris dans l'argument de recherche en cours à une position représentée par l'état actuel du compteur. 25 Une comparaison entre le multiplet de recherche et le multiplet de la clé détermine que le multiplet de recherche est supérieur, inférieur ou égal au multiplet de la clé. S'il est supérieur, la clé comprimée suivante peut être introduite immédiatement pour continuer la recherche. S'il est inférieur la recherche est terminée avec la clé comprimée en cours. S'il est égal le multi-30 plet de la clé suivant d'ordre inférieur et le multiplet de recherche suivant d'ordre inférieur sont comparés jusqu'à ce que tous les multiplets de la clé dans la clé comprimée en cours soient égaux ou jusqu'à ce que l'un d'eux soit différent. Chaque fois qu'un nouveau multiplet de la clé est obtenu le compteur d'égalité est incrémenté et on accède au multiplet de recherche suivant d'ordre 35 inférieur pour faire une comparaison. S'il y a une inégalité les multiplets de la clé restants peuvent être ignorés et la clé comprimée suivante immédiate-ment^iptroduite pour continuer la recherche. Si le dernier multiplet de l'argument de recherche est égal au dernier multiplet de la clé, la recherche est terminée par la clé comprimée en cours 40 mais.la çlé comprimée suivante sera la première clé "haute" par rapport à l'ar 69 45786 s 2027737 gument de recherche. Mais si certains des multiplets de la clé n'ont pas été comparés après que le dernier multiplet de recherche ait été comparé, la clé comprimée en cours est la première clé "haute" par rapport à l'argument de recherche. La clé non comprimée représentée par la première clé "haute" 5 sera égale à l'argument de recherche si l'argument de recherche est représenté par l'index comprimé. Dans chaque cas où la recherche est terminée elle se termine à la première clé . Lorsque l'argument de recherche est supérieur à toutes les clés de l'indsx» la recherche se termine lorsqu'on atteint la fin d'index qui peut être iden-10 tifiée par un caractère spécial ou lorsqu'il n'ya que des zéros dans des champs de limite des multiplets K d'identification de longueur dans la dernière clé comprimée de l'index. D'autres objets, caractéristiques et avantages de la présente inventions ressortiront mieux de l'exposé qui suit fait en référence aux dessins annexés 15 à ce texte, qui représentent un mode de réalisation préférée de celle-ci : La figure 1 représente une première réalisation de l'invention montrant la circulation des données. La figure 2 représente un circuit NON OU et sa table de vérité qui peut être utilisée comme un bloc fondamental pour le système de la figure 1. 20 La figure 3 représente un montage pour la réalisation d'une commande de branchement et de mise en séquence qui peut être utilisée sur la figure 1. Les figures 4,5,BA et 6B représentent une réalisation des circuits utilisés dans les commandes de mise en séquence et de branchement représentées sur la figure 3. 25 La figure ? représente une horloge qui peut être utilisée sur la figure 3. Les figures 8A à 8C constituent un tableau de la séquence des signaux de commande représentant la chronologie de cycle pour une forme de signaux de commande engendrés pour le transfert des données dans la figure 1 avec le 3Q procédé représenté sur la figure 17B. Les figures 9A et 9B représentent la succession des cycles dans l'horloge de la figure ?„ La figure 10 représente le format sur un support de communication ou d'enregistrement po-.-r une séquence ordonnée de clés non comprimées UK. 35 La figure 11A représente un format sur un suupport de communication ou d'enregistrement oo»ir la séquence de clé comprimée engendrée» Les figures "HB-11E représentent différents formats d'enregistrement pour 1.95 fiacres 12 et 13 permettent de définir certaines caractéristiques 40 fondamentales d'un couple de clés non comprimées utilisé pour engendrer les 69 45786 6 2027737 ciës non comprimées recherchées par le présente invention. Les figures 14A, B et C représentent ciexi séqasnces or&snnées de clés non comprimées à partir desquelles sont engendrées ass clés comprimées de type à décalage à gauche» décalage à droite et sans décalage. 5 Les figures ISA représentent uns siqusocE- d& clés non comprimées et une séquence de clés comprimées engendrée à pareil .is la première avsc une compression de multiplets maximum. La figure 15B représente uns séqut»ic& dû clé «ion comprimées triée et un© sêquei.ce de clé comprimées engendrée à par-Èir ut 1& première dans laquelle 10 chaque clé (sans décalage] comporte an K. ta figure 18 représente un argaaigrar^isi geitéral d'une réalisation du procédé ?Qndarnerttàl ds 1" invention. La figure 'i7P représente une réalisation du procédé de l'invention modifiée . 15 La figure 17B représente une réalisation da procédé utilisé par le cir cuit des données de la figure 1. La figure 16 représente une autre réalisation du procédé de l'invention. La figure 19 représente une réalisation détaillée du procédé de l'invention utilisée par les circuits de donnée ds la figure 20. 20 La figure 20 représente une seconde réalisation du circuit de données pour l'invention. La figure 22 représente un tableau de la séquence des signaux de commande représentant les signaux de commande engendrés pour commander les aiguillages des circuits de données représentés sur la figure 20 avec le procédé représenté 23 sur îe figure 13. Les figures 21, 23 et 24 représentent osa circuits particuliers identifiés dans la seconde réalisation représentée sur la figure 20. Ls figure 25 représente un circuit d'iJoricge particulier qui peut être utilisé avec le système de la figure 21. 30 Les figures 26A-D représentent qôuk fu*.r«éiia d'enregistrement pour des eiss comprimées. tes figures 16-, 17A, 178, 16 et 1S riïprè^s-.isit; des. réalisations ds procédés pour1 rechercher ur index csmprimô e^'igandré par un des procédés ou moyens décrits ici. 35 Un va décrire deux réalisations différentes avec des circuits de commande différents pour exécuter la méthode décrite ici, La première réalisation est représentée sur les figures 1 - 9B. Elle est uiiliaée pour rechercher un index comprimé avec le format CK (clé comprimée) fondamental représenté sur la figure 11B dans lequel le champ L et le champ F 40 occupent chacun des positions de multiplets différentes dans une mémoire et 45786 7 2027737 sont transférés sous forme de signaux distincts représentant un multiplet dans le circuit des données. Par suite, avec un multiplet de huit bits, à l'exclusion de la redondance pour chacun des champs L et F sur le format de la figure 11B, les champs L et F peuvent représenter chacun une valeur allant jusqu'à 256 suivis par jusqu'à 256 multiplets, K. Une seconde réalisation est représentée sur les figures 20 - 27A et B. Elle permet de rechercher un index ayant un des formats représentés sur les figures 11A - 11E, dans lesquels les champs L et F occupent ensemble un seul multiplet de sorte qu'ils peuvent être transférés en parallèle à un bus de transfert ds signaux d'un multiplet. Dans la seconde réalisation les champs L et F ayant ls format de la figure 11B peuvent occuper chacun des demi-multiplets de quatre bits et chaque multiplet E peut occuper un seul multiplet. Chaque multiplet étendu pour L ou pour F sur la figure 11C, D ou E peut occuper un multiplet complet. Tous les procédés décrits sur les figures 16, 17A, 17B, 18 et 19 permet- fi tent ds rschsrcher un index comprimé en utilisant une valeur maximum ou minimum Fg, ou une valeur quelconque comprise entre la valeur maximum et la valeur minimum. Ils permettent aussi de rechercher un argument de recherche non comprimé CSA) qui est représenté dans l'index non comprimé à partir duquel est engendré l'index comprimé. Ds plus, css procédés permettent de rechercher un argument non comprimé qui n'est pas représenté dans l'index non comprimé à partir duquel sst engendré l'index comprimé et qui peut indiquer que l'argument de recherche ne sera pas trouvé ici. Tous ces procédés permettent de trouver l'emplacement d'insertion approché dans l'index comprimé d'un argument de recherche si il doit être inséré ultérieurement comme une clé dans l'index comprimé. Tous ces procédés, tels que dans la figure 16, peuvent commencer la recherche dans un index comprimé à une clé comprimée quelconque ayant un champ facteur F nulle. La première clé comprimée dans l'index comprimé a un champ F nul et un champ L non nul. Un champ F nul se rencontre aussi dans l'index comprimé pour chaque clé comprimée engendrée à partir d'une paire de clés non comprimées dans laquelle la position de différence se trouve à la position de multiplet la plus significative. La recherche d'un index comprimé se fait essentiellement dans les clés comprimées ordonnées jusqu'à ce que la recherche se termine ce qui se produit lorsque l'argument de recherche est trouvé, lorsque l'argument de recherche n'est pas indiqué dans l'index comprimé ou lorsque la fin de l'index ou la fin de l'enregistrement est atteinte. Lorsque la fin de l'enregistrement est indiqué sans que l'argument de recherche ait été trouvé ou sans qu'il y ait eu de fin d'index la rechërche se poursuit avec l'Enregistrement suivant. 69 45786 B 2027737 D'autres procédés, tels que celui décrit sur la figure 16, comparent les multiplets SA'aux multiplets K amenés" séquentiellement cjepuis le débutd'une recherche. Un seul multiplet A de l'argument de recherche peut être traité à un instant quelconque. Les multiplets A sont traités dans l'ordre dans lequel 5 ils se trouvent dans l'argument de recherche, le multiplet A le plus significatif étant traité en premier lieu. Un registre A'ou autre emplacement d'emmagasinage est utilisé pour emmagasiner chaque multiplet A reçu pendant qu'il est recherché. On utilise un compteur d'égalité E dans chacun de ces procédés tels que L 10 celui représenté sur la figure 16. Le compteur d'égalité EC, est un registre ou un emplacement d'emmagasinage physique adressable et disponible. Le compteur Eç est d'abord mis aux conditions initiales et contient une Valeur nulle avant de faire une recherche dans un index comprimé. Le contenu du compteur Eç est incrémenté de un pour chaque multiplet A que l'on trouve égal au 15 multiplet CK. pendant une recherche. Le contenu du compteur d'égalité E à un instant quelconque désigne la * u position des multiplets dans l'argument de recherche pour les multiplets A entrain d'être traités. C'est-à-dire le multiplet A en co'urs est placé à la position de multiplet (Ec+ 1) dans l'argument de refcherche à partir-de la po-20 sition de multiplet la plus significative. Les conditions pour terminer une recherche avec un de ces procédés sont représentées sur la figure 16 par les circuits respectifs [4), (5), (6), (9), (10), (11) et (12) allant à l'étape 226 qui lit l'adresse indicatrice et fait passer à l'étape 227 qui termine l'opération. 25 L'argument de recherche peut ou non avoir été représenté comme une clé non comprimée dans l'index non comprimé d'origine à partir duquel l'index comprimé objet est engendré. L'index comprimé objet est réalisé dans le but de pouvoir être exploré de façon efficace, que l'argument de recherche soit connu ou non préalablement pour avoir été dans l'index non comprimé d'origine. Un autre 30 objectif est de permettre à la recherche de se terminer aussitôt que possible avant que la fin de l'index soit atteinte, que l'argument de recherché soit trouvé ou non dans l'index. Ces objectifs sont atteints en terminant la recherche à la détection de la première clé comprimée qui est supérieure à l'argument de recherche. Autrement dit, la "recherche se termine, la première fois 35 que la comparaison de l'argument de recherche et d'une clé comprimée indique que l'argument de recherche est inférieur à la clé.Avant que la comparaison indique que l'argument de recherche est inférieur, la comparaison indique que l'argument de recherche est supérieur ouégal, à chaque clé comprimée antérieure dans l'index comprimé d'objet à moins que l'argument de recherche soit 4g tout de suite déclaré inférieur à la première clé dans l'index. Lorsque I 69 45786 9 2027737 l'argument de recherche est inférieur à la première clé comprimée, son indicateur associé est lu. Des programmes classiques permettent de rechercher l'information lorsqu'il lui est attribué un indicateur. La recherche d'information peut aussi être réalisée manuellement en utilisant l'indicateur ou bien 5 en utilisant un ordinateur programmé. L'information retrouvée est utilisée pour reconstruire la clé non comprimée qu'elle représente dans l'index non comprimé d'origine puisque les positions des multiplets de la clé non comprimée sont connues dans l'information retrouvée. 10 L'argument de recherche est comparé à la clé non comprimée reconstruite. Si 1'argument de recherche est égal à la clé non comprimée reconstruite une vé- > rification est alors faite que l'argument de recherche a trouvé que les données recherchées ne sont pas représentées dans l'index comprimé. Les procédés de recherche de donnée classiques réalisent des opérations analogues de comparaison 15 avec les clés non comprimées pour vérifier l'exactitude d'une recherche. Cette comparaison permet de vérifier par conséquent si l'argument de recherche se trouve ou non dans l'index. Si nécessaire, l'index doit ensuite être mis à jour pour inclure un tel argument de recherche qui ne se trouve pas en réalité dans l'index. 20 Si l'argument de recherche n'est pas représenté comme une clé non compri mée dans l'index non comprimé d'origine, la première comparaison indiquant la supériorité termine néanmoins correctement la recherche. Elle indique le plus tôt possible que l'argument de recherche ne peut plus être trouvé dans l'index par suite elle économise du temps qui autrement serait perdu en poursuivant 25 le balayage de l'index comprimé. La fin de la recherche identifie aussi précisément la place dans l'index comprimé où une clé doit être insérée à un instant ultérieur si l'index doit être mis à jour avec l'argument de recherche. Une égalité entre l'argument de recherche et une clé comprimée n'a pas en soi une signification de recherche. Une clé comprimée à décalage à droite 30 ou une clé comprimée sans décalage (L = 1) peuvent être égales ou inférieures à l'argument de recherche avant de trouver la première clé comprimée qui est supérieure. La condition d'égalité est représentée sur la figure 16 par la sortie (14) qui provoque l'introduction de la clé comprimée suivante lorsqu'une clé comprimée quelconque est égale à l'argument de recherche, et que 35 plusieurs multiplets de l'argument de recherche restent à traiter. Si la comparaison de SA et CK se poursuivait après la détection de la première clé comprimée qui est supérieure à SA d'autres cas d'égalité, d'infériorité ou de supériorité avec des clés comprimées passibles* ils seraient sans signification. Ces comparaisons ultérieures seraient réalisées avec la 40 partie "bruit" de l'argument de recherche c'est-à-dire avec les positions de t 69 45786 10 2027737 multiplets d'importance inférieure à la position D dans la première clé comprimée supérieure à l'argument de recherche. Là désignation trouvée dans l'index comprimé objet est exécutée lorsqu'elle est engendrée à partir de l'index non comprimé d'origine. 5 La désignation "d'indicateur" relie chaque indicateur de clé non comprimée avec la clé comprimée obtenue à partir de la clé non comprimée suivante. C'est-à-dire chaque clé comprimée a un indicateur qui accède à l'information représentée par sa clé non comprimée antérieure adjacente. Ainsi, si l'argument de recherche est égal à la clé non comprimée, antérieure, la clé comprimée avec 10 l'indicateur de cette clé non comprimée antérieure est la première clé comprimée supérieure à l'argument de recherche. Aussi si un argument de recherche n'est pas égal à une clé non comprimée initialement dans la liste mais est inférieur à sa clé comprimée logiquement suivant l'argument de recherche sera supérieur à cette clé comprimée pour terminer la recherche. Par suite ce type 15 d'indicateur fait que la première clé comprimée qui est supérieure à l'argument de recherche a l'indicateur correct pour terminer une recherche et toute clé comprimée qui est égale à l'argument de recherche ne peut avoir d'indicateur correct. En conséquence, le seul indicateur qui doit être lu pendant une recherche est l'indicateur ayant la première clé comprimée supérieure. Tous 20 les autres indicateurs peuvent être sautés. La "désignation d'indicateur" est décrite avec plus de détail par le déplacement de l'indicateur représenté par les flèches sur les figures 14A, 14C, 15A et 15B. Ce déplacement peut être expliqué par la génération de chaque clé comprimée à partir d'un couple de clés non comprimées adjacentes UK- Y et 25 UK. - Z dans un index ordonné de clés non comprimées telles'"qu'on les trouve sur la figure 15A. La figure 13 représente un couple quelconque UK-Y et UK-Z utilisé comme j ième clé non comprimée et comme J+1 ème clé non comprimée respectivement. La clé comprimée est obtenue à partir de UK-Z tandis que son indicateur associé est obtenu à partir de UK-Y. En se référant à la figure 13," 30 on peut dire que l'indicateur avec Jième clé non comprimée est associé à la clé comprimée obtenue à partir de la j+1 ième clé non comprimée en comparant les jième et j+1 ième clés non comprimées j+1. Il en résulte que la clé comprimée dérivée est supérieure aux positions de multiplets correspondantes dans la jième clé non comprimée de sorte qu'une recherche se terminera avec la pre-35 mière clé comprimée supérieure à l'argument de recherche lorsque cet argument de recherche SA est égal à la clé non comprimée j ou inférieure à la clé non comprimée j+1. Ensuite toute recherche peut se terminer correctement à la détection du premier argument de recherche qui est supérieur à une clé comprimée (qui est la forme comprimée de UK - Z) et en liaant son indicateur. 40 C'est l'indicateur correct puisque c'est le seul qui peut obtenir l'informa 69 45786 11 2027737 tion indexée par l'argument de recherche. Par suite l'indicateur associé à la première clé comprimée supérieur à l'argument de recherche, est lu et disponible à la fin de la recherche. En conséquence, avec cette "désignation d'indicateur", la première clé 5 . comprimée supérieure ne peut représenter par elle-même 1'information recherchée car elle a été trouvée supérieure à l'argument de recherche. Puisque cette clé comprimée suivante est la première dans la séquence des index qui est supérieur . à SA, la clé non comprimée représentée par la clé comprimée immédiatement précédente est la seule clé non comprimée qui représente 1'information recher-10 chée. Par suite l'indicateur associé à la première clé comprimée supérieure est le seul indicateur qui peut retrouver l'information représentée par la clé non comprimée immédiatement antérieure qui est la seule qui peut être égale à l'argument de recherche SA. Ainsi, si l'argument de recherche est représenté dans l'index d'origine 15 par une clé non comprimée, une clé comprimée égale à l'argument de recherche peut exister immédiatement avant la première clé comprimée supérieure. Cette double condition à savoir qu'une clé comprimée est égale à.l'argument de recherche et est immédiatement suivie par une clé comprimée qui est supérieure à l'argument de recherche peut être utilisée pour signaler que l'argument de 20 recherche se trouve dans l'index d'origine sans rechercher l'information avec un indicateur quelconque mais on ne peut détecter par ce procédé toutes les possibilités d'argument de recherche se trouvant dans l'index. Par suite, la détection de la première clé comprimée supérieure à l'argument de recherche est le but du procédé représenté sur la figure 16. 25 C'est-à-dire cette première clé comprimée supérieure représente la première clé non comprimée supérieure dans l'index initial. La détection de la relation de l'argument de recherche à la clé comprimée ne consiste pas simplement à comparer les multiplets K de la clé aux multi- A plets de l'argument pour définir la première condition de supériorité comme 30 cela-serait fait si l'argument de recherche était comparé avec l'index de la clé non comprimée initiale dans une recherche classique d'argument de recherche. Le champ F d'une clé comprimée peut dans certains cas, seul et sans multiplet K déterminer la première condition de supériorité pour une clé comprimée. Dans l'étape 203 de la figure 16 on compare le champ F au contenu du 35 compteur E^ pour déterminer si une clé. comprimée est supérieure ou inférieure à l'argument de recherche. L'étape 203 ne peut faire une. détermination finale, d'une condition d'égalité entre la clé comprimée et l'argument de recherche mais sa branche de sortie (3) peut amorcer le processus d'une telle détermination. " r 4Q Le procédé de la figure 16,. ainsi que la plupart des( autres procédés n $ . 2027737 commencent avec l'étape 201 pendant laquelle on restaure le contenu du compteur d'égalité Ec pour qu'il ne contienne que des zéros et on introduit le multiplet A le plus significatif de l'argument de recherche SA dans un registre de multiplets A. Ensuite on passe à l'étape 202 dans laquelle les champs F et L de la 5 clé comprimée suivante sont lus. Initialement la clé comprimée suivante est la première clé comprimée dans l'index comprimé. Le champ L peut être transféré à un registre appelé L. On peut faire un test de zéro sur le contenu du registre L et le résultat du test peut être emmagasiné dans une bascule (ou position de bit) sous forme d'un un ou d'un zéro. Les résultats du test peuvent ensuite 10 être déterminés au cours des étapes 202a, b et c. Dans l'étape 203 on exécute une comparaison entre le contenu du compteur Eç et le champ F. La première clé comprimée a un champ F nul. Puisque le compteur Eç est initialement à zéro dans l'étape 203 on trouve une égalité à la première comparaison et on passe à l'étape 202c, au cours de laquelle est 15 détecté l'état zéro ou non zéro de L, et ensuite l'opération se poursuit en suivant la branche (G) ou (3). Il ne résultera pas nécessairement la détection d'une égalité de l'exécution de l'étape 203 pour les clés comprimées suivant la première, auquel cas on peut passer à une quelconque des étapes 202a, 202b ou 202c pour faire la 20 sélection parmi les branches (1), (2), (3), (4), (5), ou (6) sur la figure 16. Une seule de ces branches (1) - (6) est pris pendant que l'on traite une clé comprimée uniqueCK. Les branches (1) et (2) permettent de passer à une autre itération des étapes 202, 203 et 204 pour traiter la clé comprimée suivante sans traiter 25 un multiplet K. Les étapes (4), (5) et (6) terminent l'opération pour un argument de. recherche donné en provoquant la lecture d'un indicateur. Seul le circuit (3) est utilisé pour traiter les multiplets K et il fait passer à l'étape 208 pour faire une comparaison entre les multiplets A et K. La branche (3) utilise aussi l'étape 206 pour diminuer la valeur L afin de maintenir une 30 valeur du nombre restant de multiplets K non traités dans la clé comprimée en cours après le multiplet K suivant. La relation de supériorité ou d'inforiorité entre SA et CK qui n'a pas de multiplet K. (clé comprimée avec décalage à gauche ou sans décalage L = 0) est complètement déterminée par l'étape 203. On peut aussi déterminer dans certains cas qu'un argument de recherche est supérieur 35 à une clé comprimée avec décalage à droite sans traiter tous les multiplets K. La relation d'égalité entre E^ et F déterminée par l'étape 203 se poursuit avec des clés comprimées sans décalage (L=1) et avec décalage à droite qu'il existe ou non une première détection de supériorité et avec des clés comprimées sans décalage L = 0 et des clés comprimées avec décalage à gauche lorsqu'une 4D de ces clés est une première clé comprimée supérieure. 69 45786 69 45786 13 2027737 Si Eç est inférieur à F, le mutliplet A en cours doit être supérieur au multiplet dans la position de multiplet [E + 1) dans la clé non comprimée b à partir de laquelle la clé comprimée actuelle est obtenue. Dans ce cas aucun traitement ultérieur de cette clé comprimée nrest nécessaire quîil y ait un 5 décalage à droite, pas de décalage ou un décalage à gauche et la recherche se poursuit à la clé comprimée suivante. En passant à la clé comprimée suivante, tous les multiplets intermédiaires tels que les multiplets L, K ou indicateur peuvent être sautés pour accélérer le processus de recherche. Le saut est réalisé en introduisant l'état 202a pour déterminer quel branche (U ou C2) 1Q sur la figure 16 doit être suivi. S'il n'existe pas de multiplet K (L=0) on utilise la branche (1) pour aller à l'étape 211a, qui permet de sauter les multiplets indicateurs associés à la clé comprimée rejetée de sorte que la clé comprimée suivante peut être introduite par l'étape 202. Si les multiplets K existent dans l'étape 202a (L non nul) la branche £2) est utilisé pour 15 passer à l'étape 209a pour sauter les multiplets K et l'étape 211a est introduite pour sauter les multiplets indicateurs comme avec la branche (1). A partir de l'étape 203 on trouve la condition de la branche (4) à savoir EçSupérieur à F lorsque la clé comprimée CK à décalage à gauche est la première clé supérieure à l'argument de recherche SA. La clé comprimée avec déca-2Q lage à gauche peut suivre tout type de clé comprimé. La condition de la branche [5) termine une recherche dans certaines conditions pour une condition de décalage à gauche même si les multiplets K redondants sont inclus dans la clé comprimée. La sortie de l'étape 203 représentant l'égalité fait passer à l'étape 25 202C. Si on prend la branche (6) L = 0 l'indicateur est lu et la recherche se termine. La branche (6) est prise lorsque la première clé comprimée inférieure à l'argument de recherche présente un décalage à gauche ou pas de décalage sans multiplet K. Cependant une clé comprimée avec décalage à droite ou une clé comprimée 3Q sans décalage avec un multiplet K est déterminée par l'étape 202c trouvant un multiplet L non nul. Ensuite la branche (3) est sélectionnée pour traiter chaque multiplet K par rapport au multiplet A en cours. Les multiplets K sont traités un à la fois dans la séquence des clés comprimées, le multiplet K. le plus significatif Cle plus à gauche) étant traité en premier. Une étape 35 initiale de mise en ordre 206 est introduite par la branche C3) pour déterminer lorsque tous les multiplets K. pour la clé comprimée en cours ont été recherchés. Ceci est réalisé en diminuant le contenu du registre L en cours de un et en emmagasinant la valeur obtenue dans le registre L. La valeur L diminuée subit un test de zéro et elle est emmagasinée pour être détectée par 4Q l'une des étapes 206a, b, c et d. Les résultats du test peuvent être emmaga 69 5 10 15 20 25 30 35 40 2027737 sinés à l'emplacement utilisé pour emmagasiner le résultat des étapes 202a, b, c. Les branches C4] ou (B) sont aussi utilisées pour terminer une recherche à l'apparition de la dernière clé comprimée c'est-à-dire L 5 0 et F = 0 tel que représenté sur la figure 11A. Ainsi, si F = 0 et E^ n'est pas égal à zéro, la branche (4) sera prise. Mais si le contenu de E^ est nul et que les champs L et F sont nuls la branche (6) sera prise. Si Un index comprimé comprend des blocs multiples la clé comprimée de fin d'index peut être distinguée de la clé comprimée de fin de chaque bloc, sauf la dernière par le fait qu'il y a un multiplet de longueur d'indicateur ne contenant que des zéros avec L=0 et F=0 à la fin du dernier bloc, la clé comprimée de fin normale d'index avec un indicateur exact est utilisée. Ensuite au cours de l'étape 207 le premier multiplet K de la clé comprimée est lu et l'étape 208 est réalisée en comparant le multiplet K avec le contenu actuel du registre A. Après l'étape 208 on a le choix entre une des neuf branches (7) - (15). Quatre de ces branches [13) (7), (10) et C121 sont.choisies en fonctiqn de la relation de supériorité ou d'infériorité entre A et K. Les cinq autres branches (8) [9) C113 [14) (15) ne sont introduites que si A et K sont égaux. Les branches C8) (14) et (15) dépendent de l'existence de plusieurs multiplets A après le multiplet A en cours. Cependant, on utilise les branches (9) et (11) si il n'existe pas plusieurs multiplets A après le multiplet A en cours, auquel cas l'indicateur est lu après la clé comprimée en cours ou suivante, suivant quelle branche (11) ou (9) est prise respectivement. Chaque fois que l'indicateur est lu l'opération pour l'argument de recherche en cours se termine par l'étape 227. Si au cours de l'étape 208 on trouve que le multiplet A est supérieur au multiplet K. la recherche se poursuit en passant à la clé comprimée suivante par l'intermédiaire de l'étape 206a car l'argument de recherche doit être supérieur dans l'index supprimé à la clé comprimée en cours. Si l'étape 206a indique qu'il reste à lire plusieurs multiplets K à partir de la clé comprimée en cours la branche (7) est prise pour arriver à l'étape 209a pour ignorer les multiplets K. restants.-Ensuite l'étape 211a est introduite pour ignorer les multiplets de l'indicateur associé en vue d'introduire la clé continue suivante. Mais si l'étape 206a trouve qu'aucun multiplet K. ne suivra, la branche (13) est prise pour conduire à l'étape 211a au cours de laquelle les multiplets indicateurs associés sont sautés en vue d'introduire la clé comprimée suivante. L'exécution de l'une ou l'autre ou des deux étapes 209a ou 211a peut être réalisée premièrement en détectant et ignorant le nombre nécessaire 45786 45786 15 2027737 de multiplets dans une chaine de multiplets d'index comprimés fournis en série, ou deuxièmement en indexant le nombre nécessaire de multiplets emmagasinés dans une mémoire à accès aléatoire. Si l'étape 208 détermine que le multiplet A est égal au multiplet K reçu l'étape 216 est introduite pour tester si il y a encore plusieurs multiplets A. Une décision de recherche est faite dans l'étape 216 uniquement si l'argument de recherche a été complètement reçu. L'étape 216 peut être exécutée d'un certain nombre de façons. Par exemple, si une valeur du multiplet SA est disponible elle peut être diminuée avec chaque multiplet A reçu, et plusieurs multiplets A resteront tant que la valeur diminuée n'est pas nulle. Ou bien une demande pour un multiplet A suivant peut être réalisée à partir d'une source de multiplets A tel qu'un canal dans un ordinateur et la réponse excitera une ligne si il existe plusieurs multipletsA. Si on n'a pas plusieurs multiplets A pour l'argument de recherche le cycle de décision de recherche dépend du fait qu'il existe plusieurs multiplets K. L'étape 206c teste si il y a plusieurs multiplets K en faisant un test de zéro comme expliqué précédemment pour la valeur L diminuée dans le registre L. Si il existe plusieurs multiplets K la clé comprimée en cours doit être supérieure à l'argument de recherche et la branche (11) est prise pour lire l'indicateur en cours comme décision de recherche. Par suite les multiplets L restants sont sautés par la branche 11 introduisant l'étape 209c et ensuite l'étape 226 emmagasine l'indicateur associé à la clé comprimée en cours. Si il n'y a pas plusieurs multiplets K. indiqués par l'étape 206c, la branche (9) est prise indiquant que l'argument de recherche est égal à la clé comprimée. Mais l'argument de recherche n'est pas nécessairement égal à la clé non comprimée représentée par cette clé comprimée. La clé non comprimée à partir de laquelle est obtenue la clé comprimée peut être plus longue que l'argument de recherche à cause des multiplets de bruit qui sont chutes. De même il est possible que cette clé non comprimée n'ait pas de multiplets de bruit auquel cas l'argument de recherche est égal à la clé non comprimée représentée par cette clé comprimée. Cependant comme on l'a dit précédemment, une clé comprimée obtenue à partir d'une clé non comprimée égale à l'argument de recherche ne peut avoir l'indicateur correct mais la clé comprimée suivante aura l'indicateur correct. Par suite la branche (9) lit l'indicateur avec la clé comprimée suivante puisque la clé comprimée suivante est la première qui sera détectée supérieure à l'argument de recherche. En conséquence, la branche (9) fait passer à l'étape 211b pour sauter l'indicateur en cours avec la clé comprimée en cours, ensuite l'étape 223 saute les multiplets F et L suivants suivis par l'étape 209c saute tous les multiplets K de sorte que l'indicateur suivant est lu (associé à la clé comprimée suivante) comme 69 45786 16 2027737 indicateur trouvé terminant la recherche dans ce cas. Cependant la branche [S) est prise si l'étape 216 qu'il y a plusieurs multiplets A. Dans ce cas l'étape 217 est introduite pour que le multiplet A suivant soit traité. Le contenu du compteur d'égalité E est augmenté de un L 5 en introduisant et exécutant l'étape 218. Lorsque plusieurs multiplets K sont indiqués dans l'étape 206d le multiplet K suivant est recherché et l'étape 206 est introduite de nouveau pour diminuer L de un. Les nouveaux multiplets K et A sont alors comparés par l'intermédiaire de l'étape 208, et si il y a plusieurs multiplets K et A la même itération par 1'intermédiai-10 re des étapes 216, 217, 21B, 206d et 208 se poursuit jusqu'à ce qu'il n'y ait plus de multiplets K ni de multiplets A. Le compteur d'égalité E^ est augmenté dans l'étape 218 uniquement si l'on trouve qu'un multiplet K est égal à un multiplet A dans l'étape 208 et que l'étape 216 trouve que plusieurs multiplets A existent pour sortir le long 15 de la branche 18) pour faire passer à l'étape 217 afin d'obtenir le multiplet A suivant. Seules les clés comprimées à décalage à droite et sans décalage (L = 1) peuvent augmenter le contenu du compteur d'égalité car^seules ces clés comprimées peuvent prendre la branche (3) qui est la seule façon de faire passer à l'étape 208, 216, 217, 218. 20 Si l'étape 206d indique que La été augmenté l'étape 211a est introduite pour sauter l'indicateur associé à la clé comprimée en cours et introduire l'étape 202. Le tableau suivant représente en résumé les branches de sortie décrites précédemment pour les différents types de clés comprimées. La légende utilisée 25' dans le tableau est la suivante : LEGENDE L : CK avec décalage à gauche R : CK avec décalage à droite 30 Nq: CK saris décalage L = 0 : CK sans décalage L = 1 (B): CK est inférieur à SA c'est-à-dire tSA (E): CK est égal à SA c'est-à-dire (SA«CK). (H) :CK est supérieur à SA c'est-à-dire (SA>CK). 35 annotation : pour distinguer différentes conditions de sortie pour le même type de clé comprimée . Par exemple, (B) L représente une clé comprimée avec décalage à gauche qui est inférieure à l'argument de recherche et suit la branche (1). Un autre exemple (B)R-1, (B)R-2 et (B)R-3 représente différentes conditions de sortie pour une 40 clé comprimée avec,décalage à droite lorsqu'elle est inférieure à l'argument 69 45786 17 2027737 de recherche SA. TABLEAU DE SORTIE BRANCHE DE SORTIE SORTIE A CK SUIVANTE LORSQUE : (1) (2) (7) . C131 (14) (B)L, (B)N , (BIR-3, (E)L ou £E)N . o o {B) M -1. (B) R-2. (BIR-2. (BJN -2. 1 [BJR-1, (E)R, ou [E}N^. et plusieurs multiplets A à traiter 10 BRANCHE DE SORTIE SORTIE POUR LIRE INDICATEUR LORSQUE £4) (6) (9) (H)L (min F). CRÎL Cmax F), ou (HJ N . o CE)R, ou (E)N. et Ec = nombre de multiplets dans SA 15 (10) (H)R avec détermination au dernier multiplet K (12) (H)R avec détermination avant derniers multiplets K Les représentations des clés comprimées orientées vers les sorties dans le tableau précédent sont représentées sur la figure 16. 20 Le procédé décrit précédemment en se référant à la figure 16 se poursuit jusqu'à ce qu'un indicateur soit lu au cours de l'étape 226 en réponse à chaque argument de recherche ou jusqu'à ce que la fin d'index soit atteinte pour indiquer que l'argument de recherche est supérieur à une clé comprimée dans l'index. L'indicateur trouvé pour un argument de recherche donné peut 25 obtenir l'enregistrement ayant l'index de l'argument de recherche SA uniquement si cet argument est dans l'index d'origine non comprimé. Si l'argument de recherche n'est pas représenté dans l'index objet non comprimé recherché l'indicateur lu ne représentera pas l'argument de recherche. Comme expliqué précédemment, la détermination du fait que l'indicateur représente ou non l'argument 30 de recherche nécessite que l'indicateur soit utilisé pour retrouver son bloc de données représenté à partir duquel la clé non comprimée initiale est obtenue, et qui était utilisée pendant la formation de l'index comprimé. La clé non comprimée recherchée est alors comparée avec l'argument de recherche. Si * 69 45786 18 2027737 ils sont égaux, l'indicateur venu est l'indicateur exact et l'argument de recherche est représenté dans l'index comprimé. Cependant si la clé non comprimée et l'argument de recherche ne sont pas égaux, l'argument de recherche n'est pas représenté dans l'index comprimé et l'indicateur lu représente une 5 condition limite et non l'argument. Différentes réalisations peuvent mettre en oeuvre le procédé représenté sur la figure 16 telles que les réalisations sur les figures 17A et 17B. La figure 17B représente un exemple d'une adaptation du procédé de la figure 16 au bloc diagramme représenté sur la figure 1. 10 Sur la figure 16 est représentée une séquence particulière en bloc diagramme. Néanmoins l'ordre des événements pour une variable particulière est sans importance dans une sous séquence du bloc diagramme tant que la variable ne change pas dans la sous-séquence. Ainsi, les organigrammes des figures 17A et 17B modifient l'ordre de la séquence ou réalisent certaines fonction 15 en parallèle, dans certaines de sous séquences représentées sur la figure 16, dans lequelles la variable ne change pas. On utilise les mêmes numéros de référence pour les étapes communes dans les figures 16 et 17A, bien que des indications de référence soient portées sur la figure 17A lorsque l'étape de la figure 16 a plusieurs représentations. 20 Les organigrammes des figures 17A et 17B, représentent par conséquent d'autres réalisations permettant d'obtenir des opérations analogues à l'organigramme de la figure 16. La figure 17B obtient un degré maximum d'uniformité dans les blocs de l'organigramme afin de rendre optimum la construction d'une autre réalisation de la figure 1. 25 Les résultats obtenus par l'organigramme de la figure 16 peuvent aussi être obtenus en changeant l'ordre illustré de certaines étapes de la figure 16. La figure 17A permet d'obtenir les mêmes résultats que la figure 16 mais avec un ordre différent de certaines des étapes. Ainsi sur la figure 17A les mêmes numéros de référence sont utilisés sur la figure 16 sauf lorsqu'une étape 30 particulière de la figure 16 est divisée en plusieurs étapes sur la figure 17A, auquel cas il y a des annotations ajoutées à la fin du même numéro de référence que celui utilisé sur la figure 16. Les étapes 207 et 206 peuvent être interchangées sans modifier le fonctionnement de l'invention. Sur la figure 17A, la valeur L est diminuée dans l'étape 206-1, subit un 35 test de zéro dans l'étape 206-2 et ensuite le multiplet K. suivant est lu dans l'étape 207, un 1 lui étant ajouté afin de réaliser son complément à deux pour exécuter la comparaison suivant immédiatement l'étape 208. Le choix de l'addition du complément à deux pour l'étape de comparaison est préféré à cause du choix du type additionneur 276 dans un circuit de donnée choisi. _La figure 40 17B fait également de même avec les étapes correspondantes 306, 307 et 308. 69 45786 19 2027737 Sur la figure 17A, l'étape 202 est divisée en deux étapes 202-1 et 202-2, et l'étape 204 est intercalée entre les deux. Ceci est possible car l'étape 204 dépend de la lecture de L dans l'étape 202-1 mais est indépendante de la lecture de F dans l'étape 202-2. De même l'étape 203 est indépendante de 5 l'étape 204 par suite l'ordre des étapes 203 et 204 est sans importance. On retrouve ce type de raisonnement pour les autres différences entre les figures 16, 17A et 17B. Ainsi, sur la figure 17A, l'étape 204 de test zéro pour L suit immédiatement la lecture de L dans l'étape 202-1 et ces deux opérations peuvent 10 être réalisées dans un seul cycle d'horloge. Ensuite le multiplet F est lu dans l'étape 202-2 et il peut être comparé immédiatement avec le contenu de E^ dans l'étape 203 ce qui peut aussi être réalisé en un seul cycle d'horloge. Le circuit logique de la figure 16 nécessite que la comparaison du contenu de E^ et de F dans l'étape 203 et le test L=0 dans l'étape 204 soient 15 réalisés avant de déterminer laquelle branche (1) et (6) peut être prise. Cette même logique s'applique à la figure 17A où le résultat du test 0 dans l'étape 204 est emmagasiné pendant la détermination de la comparaison : F. Le test peut être emmagasiné dans une seule position de bit sous forme d'un 0 ou d'un 1 et par exemple le zéro peut représenter le fait que L est différent de 0 et 20 le un représenter que L est égal à 0. Lorsque l'étape de comparaison 203 est terminée la valeur emmagasinée pour le test de 0 de L est détecté dans l'une des étapes 202a1, 202a2, 202b1, 202b2, 202d1 ou 202d2 pour choisir une des branches (1] - (6J. Le procédé de la figure 17B adapte le procédé de la figure 17A au circuit 25 particulier représenté sur la figure 1. Certains des choix arbitraires mentionnés précédemment dans la séquences des étapes pour les procédés des figures 16 et 17A peuvent être choisis d'une manière particulière afin de diminuer les circuits nécessaires pour une adapta ion particulière. Ceci a été réalisé dans la figure 17B. Certaines des étapes représentées sur les figures 30 16 et 17A ont été séparées en plusieurs sous étapes. Par conséquent la figure 17B traite la lecture de la longueur de l'indicateur avant que l'on ignore ou lise les multiplets indicateurs. Sur la figure 16 on peut observer l'identité parmi certaines des étapes telles que 209, 224 et 225. Cette identité permet à ces étapes d'être réalisées par une opération commune dans l'organigramme 35 de la figure 17B. Chaque rectangle dans la figure 17B est suivi par une opération de test ou de comparaison pour organiser les opérations de 1'organigramme pour un minimum de cycles d'horloge. Ces cycles sont identifiés respectivement par C0 à C12 sur la figure 17B. Les cycles d'horloge respectifs sont séparés en phaseB 40 d'horloge qui peuvent être réalisés par un micro ordre qui est un transfert 69 45786 20 2027737 entre une porte de sortie et une porte d'entrée. Chaque micro-ordre réalise généralement une des expressions représentées dans, un rectangle de la figure 17B au moyen du dispositif représenté sur la figure 1. Les deux derniers chiffres dans les numéros de référence de la figure 5 17B correspondent aux deux derniers chiffres dans la figure 16 pour des éléments ayant des étapes analogues. Ainsi sur la figure 17B, l'étape 3D1 réalise la même fonction que l'étape 201 sur la figure 16. L'étape 301 réalise la même fonction que l'étape 201 sur la figure 16. La figure 17B est une adaptation de l'organigramme de la figure 16 au circuit représenté sur la figure 1. 10 En résumé, le circuit du système de recherche de la figure 1 a un index comprimé emmagasiné dans un dispositif I/O 350. L'argument de recherche SA peut être emmagasiné par exemple, dans une mémoire à accès aléatoire, d'un ordinateur 351. L'argument de recherche peut être fourni par une unité centrale de traitement de l'ordinateur 351 par l'intermédiaire d'un canal 351a à un dispositif 15 de commande qui comprend des commandes pour exécuter la présente invention. Un interface de commande I/O 353 connecte ls dispositif I/O 350 au dispositif de commande de la figure 1. Les multiplets de circulation de donnée X de l'index comprimé sont extraits d'un dispositif I/O 350 et envoyés à un interface de commande I/O 353. La chaine des multiplets X provenant du dis-20 positif I/O 350 est inversée à la sortie d'un registre d'interface X pour obtenir son complément à 1 X qui est amené à un bus de sortie 361. Chaque multiplet X est transféré à partir du bus 351a en réponse à un signal d'introduction IG(1 Un interface commande-unité centrale de traitement d'entrée reçoit les multiplets à une porte Y qui comprennent les multiplets de l'argument de recherche SA. Chaque multiplet A est amené à partir de la porte Y en réponse à un signal d'introduction IGCY) arrivant sur. une ligne de commande 357 qui 35 demande chaque multiplet A. Un signal d'existence e est amené au conducteur 358 pour indiquer qu'un multiplet A suivra à partir de la source Y. Le signal e peut être représenté par un niveau qui devient bas lorsque les multiplets vont suivre et reste bas tant que les multiplets sont transmis à partir de la source Y. La sortie valeur exacte de la porte Y est amenée à un bus.356. Le 40 signal de départ S est amené sur le conducteur 359 à partir de l'interface 69 45786 21 2027737 354a pour commencer une opération de"recherche. Le signal S peut être engendré en réponse à une instruction de l'unité centrale de traitement, une commande du canal ou une interruption de l'unité centrale de traitement. Un interface CPU-commande de sortie 354b est utilisé pour la transmis-5 sion des multiplets indicateurs R à partir d'un registre d'interface R à l'unité centrale de traitement 351. Un circuit de transfert W_ reçoit un signal d'introduction IGCR) sur un conducteur 367 chaque fois qu'un multiplet sur le bus de sortie de l'additionneur 377 doit être emmagasiné dans le registre d'interface R pour être transmis à l'unité centrale de traitement 351. Un 10 signal FIN sur la ligne de commande 368 indique qu'il ne suivra plus de multiplets sur le bus 377 pour terminer la recherche en cours. Le circuit de donnée de commande de recherche sur la figure 1 nécessite que les champs L et F de chaque clé comprimée soit transmis à des instants différents de sorte que le champ L est transmis sous forme d'un multiplet 15 suivi par un multiplet contenant le champ L. Trois registres de multiplets sont utilisés, ce sont un registre Ec 371, un registre L 372 et un registre A 373. Le contenu du registre 371 représente, la valeur binaire exacte du registre Eç, le contenu du registre 372 représente le complément à deux du nombre de multiplets K restants dans la clé comprimée en cours et le contenu 20 du registre 373 représente la valeur binaire exacte de A. Chaque multiplet A transmis à partir d'une source Y est introduit dans un registre A 373 par un signal d'introduction IGCY). Le complément à deux du multiplet L dans chaque clé comprimée reçue à partir de la source X est amené au registre L 372 en faisant passer le multi-25 plet dans un additionneur 376 en lui ajoutant un un actif CIGC+1) et dans une bascule d'additionneur H en utilisant le signal d'introduction IG(HQ) et en- n suite au registre L 372 en utilisant le signal d'introduction IGCL) alors qu'il n'y a pas de signal amené à l'autre entrée de l'additionneur. L'additionneur et son bus de sortie transmettent des signaux d'un mul-30 tiplet de longueur. Ainsi l'additionneur 376 permet d'ajouter deux entrées ayant chacune un multiplet de large et il fournit leur somme dans sa bascule H. Le signe de la somme est fourni par une position G d'un registre de dépassement de capacité dans laquelle un zéro indique un résultat positif dans la bascule H et un un indique un résultat négatif dans la bascule H. La valeur 35 négative est fournie par un dépassement de capacité lorsqu'on utilise une addition de complément binaire pour obtenir une opération de soustraction ou de comparaison. Un signal un actif IGC+1) est utilisé pour convertir un signal de complément à un en un signal de complément binaire pour une opération de soustraction ou de comparaison. Le signal complémentaire est amené 40 à l'entrée droite de l'additionneur tandis que la forme exacte du signal est 69 45786 22 2027737 reçue sur l'entrée droite de l'additionneur. Un signal de sortie OGCH) est reçu par la bascule H pour qu'elle contienne la somme des signaux d'entrée à l'additionneur laquelle somme est envoyée au bus de sortie de l'additionneur 377. 5 La position de signe G est connectée comme entrée à un circuit de commande d'horloge 382 ainsi que le signal complémentaire G obtenu à partir d'un inverseur.I. Un dispositif de test de zéro 378 est connecté au bus de sortie de l'additionneur 377 et il teste chaque multiplet de sortie ds l'additionneur 10 pour trouver un état zéro. Ce circuit est un circuit OU qui fournit un signal de sortie nul si un seul bit 1 est amené à son entrée. Ls signal de sortie du dispositif de test E et son complément E sont amenés à un basculeur 381 par l'intermédiaire d'une porte qui peut être excitée par le signal IGCT). Le basculeur fournit les signaux de sortie valeur exacte, valeur complémentai-15 re T et T. Le basculeur T conserve une indication de test de zéro jusqu'à ce qu'il reçoive le signal suivant IG(T). Le dispositif de test 378 ne teste que l'état zéro du résultat dans la bascule H sans tester la position de signe G qui n'est pas amenée au bus 377. Les signaux E, E, T et T sont amenés aux entrées d'un circuit de commande d'horloge 382. 28 Le compteur d'égalité (E) 371 emmagasine le nombre total de multiplets u égaux envoyés pendant les comparaisons des multiplets A et desmultiplets K pendant une recherche de l'argument de recherche SA. Le tableau des figures 8A, B et C représente les transferts de données pendant les différents cycles d'horloge du mode de recherche. Ils représentent 25 la chronologie pour les transferts de données nécessaires dans l'organigramme représenté sur la figure 1. Dans le tableau, la chronologie est représentée par un cycle d'horloge et une phase d'horloge dans chaque cycle. Les symboles de référence des signaux de transfert dans les tableaux sont OG pour la sortie des données, et IG pour l'entrée des données et BM pour les opérations de 30 branchement dans la matrice qui se produisent dans les commandes d'horloge 382. A chaque opérateur est ajoutée une annotation (représentant un registre auquel le préfixe IG, OG ou BFl s'applique. Par exemple OG (A) représente le registre de sortie A. Chaque porte de registres sur la figure 1 a une ligne de commande représentée dans le tableau. Par exemple le registre A 373 35 a une porte de sortie à laquelle est connectée une ligne de commande OG (A), qui lorsqu'elle est excitée provoque le passage du contenu du registre 373 au bus 374. De mime le registre E^ 371 comporte une porte d'entrée st une porte de sortie. Une ligne de commande IG CEq) 371 comporte une porte d'entrée et une porte de sortie. Une ligne de commande IG(E^) est connectée à sa 40 porte d'entrée et l'excitation du signal IG(EC) provoque le chargement 69 45786 23 2027737 dans le registre 371 des états électriques et bus de sortie de l'additionneur 377 qui sont déterminés par la sortie de la bascule H. Ainsi chacune des opérations dans le tableau s'appliquent à une ligne correspondante de la figure 1. Chaque opérateur BM dans le tableau comporte entre parenthèse un symbole 5 logique réalisé par l'introduction BM, an symbole ( La séquence d'horloge globale pour la figure 17B est représentée sur la figure 9A. Cette séquence est obtenue avec le circuit d'horloge représenté 25 sur la figure 7. La figure 2 représente une bascule NON-OU et sa table de vérité cette bascule est un circuit classique. Cette bascule peut être utilisée pour construire chaque position de bit à l'intérieur de chaque registre et bascule sur la figure 1. 30 La disposition du circuit de commande est représentée sur la figure 3 qui porte les identifications des autres figures 4-7, dans lesquelles les parties détaillées du circuit de commande sont représentées. Ainsi, la figure 5 représente les circuits de branchement pour commander les états des bascules S0 et S1. Les sorties des bascules sont amenées aux commandés de mise en route 35 de l'horloge dans les figures 6À et 6B pour commander les sorties provenant des cycles d'horloge communs C 2/10, C 2/7/11 et C/4/8/12. Lorsqu'on quitte un de ces cycles d'horloge commun, le choix du cycle d'horloge suivant dépend de l'état des bascules S0 et/ou S1. Les circuits d'horloge représentés sur la figure 7 sont mis etï route par 40 les sorties des figures 6A et 6B. Chaque circuit d'horloge 400-4Û7 comprend 45786 24 2027737 un registre à décalage ou anneau classique qui est ouvert-fermé et dont le nombre d'étages est égal au nombre d'étages de sortie représenté sur la figure 7. L'entrée de mise en route est reliée au premier étage du registre à décalage et met un "un" dans ce registre en réponse à la réception d'un signal 5 de mise en route provenant de la figure 6Â ou 6B. Le bit un est décalé par les impulsions de décalage reçues à partir d'un oscillateur 411 par l'intermédiaire d'une porte 410. Les impulsions de décalage sont constituées par les demi-cycles positifs des cycles de l'oscillateur 0^. 10 Un basculeur d'horloge 412 commande le moment où les impulsions de décala ge peuvent passer dans la porte 410. Lorsqu'il est enclenché le signal de sortie valeur exacte (T) du basculeur 412 conditionne la porte 410. Il est enclenché en réponse à une impulsion C^ provenant de l'interface I/O commande 353 sur la figure 18A. Une impulsion C^ précède ou se produit au début de chaque 15 multiplet fourni à partir de la source 1/0 350. L'opération de déclenchement de l'impulsion est commandée en phase par une porte ET 414 qui reçoit chaque impulsion C^ et une impulsion engendrée par un différentiateur 413 au début du cycle CL qui se produit à la fin d'une im- ^ Hp pulsion de decalage fournie à la porte 410. Ainsi un demi-cycle l'oscillateur 20 Oy est au niveau bas (tandis :que le cycle Dp est au niveau haut) avant que l'impulsion de décalage suivante (le demi-cycle positif de l'oscillateur) soit amené à la porte 410. Par suite, les fonctions de commande des circuits 413, 414, 412, 422 et 410 peuvent répondre en réalisant la commutation pendant la période de niveau bas de 0 avant que l'impulsion de décalage suivante soit 25 fournie. Les différentiateurs 413 reçoivent le signal de sSrtie de phase opposée (Dp) provenant de l'oscillateur 411, phase opposée à la phase de 0^ exacte fournie comme impulsions de décalage. La fréquence des impulsions de l'oscillateur est de préférence six fois supérieure ou plus à la fréquence des multiplets du dispositif 1/0 350 qui est 30 la fréquence des impulsions C^. Par suite tout cycle d'horloge peut être décalé suivant cinq phases (C 4/8/12 a un minimum de cinq phases) avant que l'impulsion suivante puisse être fournie. Il est nécessaire de pouvoir retarder les opérations de l'horloge à divers instants pour attendre l'impulsion suivante pour synchroniser le cycle 35 d'horloge suivant. Ce retard se produit après chaque phase d'horloge qui demande le multiplet I/O suivant en fournissant un signal IG(X) sur le conducteur 421 à partir de la figure 4 à la porte 422 sur la figure 7. Ce retard commence lorsque la fin de la phase d'horloge IG(X) est détectée par le différentiateur 413 fournissant une impulsion à cet instant pour exciter la porte 422 pour 40 restaurer le basculeur d'horloge 412. Un signal d'entrée de restauration du 69 45786 25 2027737 basculeur 12 chevauche un signal d'entrée d'enclenchement simultané et enclenche le basculeur 412. Chaque impulsion C^ a une durée supérieure à un cycle O.J. et demi. Le signal IG(X) n'est actif que pendant les demi-cycles positifs 0^. 5 Le signal IGCX) est aussi amené par l'intermédiaire du circuit à retard 416 à une porte ET 417 conditionnée par un signal de sortie F provenant du basculeur 412. Par suite le circuit 416 doit avoir un retard dépassant la période de restauration du basculeur 412 pour que l'impulsion passe dans la porte 417. Cette impulsion engendré le signal IG(X) - 1 sur le conducteur 362 qui est connecté 10 à l'interface sur la figure 1 pour introduire le multiplet CK suivant dans le registre X. Les multiplets A de l'argument de recherche sont amenés en réponse à un signal IG[Y) engendré sur la figure 4 dans les phases d'horloge C0.2 ou C6.2. Le signal IGCY) excite un circuit de commande d'interface R qui signale un A 15 ordinateur 351 d'envoyer le multiplet A suivant. Le multiplet A doit être reçu par la porte Y dans l'interface 354a et transféré dans le registre A 373 avant la phase d'horloge 5.3 lorsque le signal 0G(A) extrait ces multiplets du registre A pour le traitement. Ensuite la demande C0.2 par IG(Y) est suivie par cinq cycles d'horloge avant que le multiplet A soit demandé par le signal 0G(AJ. Ce-20 pendant la demande de la phase d'horloge C6.2 de IG(Y) est suivie par un intervalle égal à un cycle d'horloge avant que le multiplet A soit demandé par le signal OG(A) ét ceci représente le cas limite de la réponse de l'ordinateur au circuit R . A Les signaux de commande provenant de la figure 4 sont appliqués aux portes ne. de la figure 1 suivant la chronologie representee sur les figures 8A,B et C. La figure 9A représente la séquence générale des cycles d'horloge, la figure 9B représente la séquence des cycles d'horloge restreinte disponible pendant un état donné des bascules d'état S0 et S1. On va maintenant décrire une seconde réalisation du mode de recherche. En 30 pratique il a été observé que le nombre moyen des multiplets K dans les clés comprimées est faible et indépendant de la longueur des multiplets des clés non comprimées correspondantes. De plus, dans de nombreuses applications, le nombre moyen des multiplets facteur est aussi faible. La seconde réalisation utilise ces remarques en traitant les clés comprimées dans lesquelles le nombre 35 F des multiplets facteurs et le nombre L des multiplets K peuvent être représentés par un seul multiplet ce qui réduit la longueur des clés comprimées. On utilise une représentation à plusieurs multiplets pour F et L chaque fois que F t L ou les deux ne peuvent être représentés par des parties égales à un seul multiplet. Ainsi quatre représentations de F et L sont possibles qui sont re-40 présentées sur les figures 26A- D. Dans chacune de ces figures le premier mul- 69 45786 26 2027737 tiplet CK. est divisé en deux parties d'un demi-multiplet de quatre bits chacun. Le champ de quatre bits représente le nombre décimal maximum égal à 14, et 15 est utilisé comme code de champ étendu afin d'indiquer que le champ sera trouvé dans un multiplet suivant de 8 bits qui peut représenter des va-5 leurs allant jusqu'à 256 la valeur 256 n'étant pas comprise. La figure 26A représente on format CK avec F et L inférieur à 15 F,L sont représentés dans les demi-multiplets supérieur et inférieur respectivement, du premier multiplet de la clé comprimée. La figure 26B représente un format CK avec F inférieur à 15 mais L supé-10 rieur ou égal à 15, F est représenté dans la moitié d'ordre supérieur du -premier multiplet et L est représenté dans le second multiplet de la clé comprimée CK. La moitié d'ordre inférieur du premier multiplet (normalement le champ L) ne contient que des uns ce qui représente l'existence du multiplet L suivant. 15 La figure 26C représente un format CK avec F supérieur ou égal à 15 mais L inférieur à 15, F est représenté comme second multiplet de la clé comprimée tandis que L est représenté dans la moitié d'ordre inférieur du premier multiplet. Le premier demi-multiplet! et la clé comprimée (normalement le champ F) ne contiennent que des uns (151 représentant l'existence du multi-20 plet F suivant. La figure 26D représente un cas où on peut avoir à la fois F supérieur ou égal à 15 et L supérieur ou égal à 15, tout le premier multiplet contient des uns (normalement les champs F et L) indiquant l'existence des multiplets étendus L et F suivants dans cet ordre. 25 La seconde réalisation est décrite comme modification de la première. Les figures 18"et 19 représentent la modification. La figure 18 remplace la séquence de la figure 17A entre le point 701 et les points 722-724 tandis que la figure 19 remplace la séquence de la figure 17B entre les points 801 et 802, 807 (concernant le traitement de F et L). 30 La seconde réalisation est exécutée par les circuits représentés sur la figure 20. Les changements par rapport à la figure 1 sont : des circuits de transfert d'un demi multiplet entre l'interface des dispositifs I/O 353 et l'additionneur 376A, le registre G) decapacité un demi-multiplet et son entrée de conditionnement IG(HH ) à l'additionneur, les deux dispositifs de test de . R 35 zéro 395 et 396 et le transfert de IG(11113 comportant quatre bits un aux positions de bits d'ordre supérieur de l'additionneur 376A. La figure 21 représente le circuit pour les commandes et horloges spéciaux 840 représentées sur la figure 20 et mentionne les numéros des figures dans lesquelles sont représentées en détail certaines parties du circuit. 40 Sur la figure 21 un circuit d'horloge spécial 855 et les commandes de trans 69 45786 27 2027737 fert spéciales 851 sont combinés avéc des circuits d'horloge et de commande 852, 853, 854 parmi lesquels le dernier est aussi utilisé par la réalisation représentée sur les figures 1 et 3. Ainsi les figures mentionnées par des blocs sur la figure 3 sont aussi référencées par des blocs sur la figure 21, qui 5 comprend la matrice de branchement et les commandes de bascule d'état de la figure 5, les commandes de mise en route de l'horloge, des figures 6A et 6B, les circuits d'horloge de la figure 7 et les commandes de circulation de donnée de la figure 4. Cependant les connexions des circuits 852, 853 et 854 de la figure 21 sont différentes des connexions de la figure 3. 10 L'horloge 855 de la figure 25 engendre un cycle d'horloge C1A et est combinée avec les circuits d'horloge représentés sur la figure 7. La fonction de l'horloge C1 de la figure 7 est remplacée entièrement par l'horloge C1A sur la figure 25, la fonctionâes autres horloges 0 et 2-9 étant la même. L'horloge C1A est représentée en détail sur la figure 22 qui remplace simplement les fonc-15 tions décrites en détail pour l'horloge 1 sur'les figures 8A, B et C. La figure 19 représente en détail les étapes réalisées dans le circuit de la figure 20 par les six phases du cycle d'horloge C1A. Les deux circuits de transfert d'un demi-multiplet 390 et 391 sur la figure 20 entre l'interface 353 et l'additionneur 376A sont utilisés ensemble au 20 lieu du circuit de transfert d'un multiplet complet 361 sur la figure 1. Les autres séquences d'horloge C0 et C2-C9 de la figure 8A, B et C sont utilisées pour commander le circuit de la figure 20. Pendant la première phase du cycle d'horloge C1A (c'est-à-dire C1A.1) sur la figure 22, le premier multiplet d'une clé comprimée est demandé en augmentant 25 le niveau de XGCX) les deux demi-multiplets et XR présentés à l'interface 353 sont traités séparément pour loger les champs F et L d'un demi-multiplet normaux sur la figure 26A-D. Par suite le demi-multiplet gauche XL peut contenir le champ F d'un demi-multiplet tandis que le demi-multiplet de droite XR peut contenir le champ L. Le demi-multiplet de droite XR pendant la phase 30 d'horloge C1A.1 est transféré par l'additionneur 376 A sn même temps que les quatre uns d'ordre supérieur c'est-à-dire IG(1111] pour fournir 1'enchainement de X et des uns d'ordre supérieur qui sont ajoutés au un actif IG(+1) pour R obtenir le complément binaire de huit de XR qui est transmis au registre L. Ainsi, le demi-multiplet L est placé dans le registre L sous forme de son 35 complément à deux. Si la valeur exacte de L est nulle le complément à deux . sera nul ignorant ainsi^l/état de la bascule de dépassement de capacité G qui n'est pas amené au dispositif de test 378. De même pendant la phase C1A.1 deux tests de zéro sont réalisés sur L. Un dispositif de test de zéro 378 permet de déterminer l'état zéro ou non.zéro 40 du signal de sortie de l'additionneur qui est introduit par IG(T) dans la 69 45786 28 2027737 bascule T, fournissant un moyen pour tester l'état de L. Si T est un un, L est un zéro et si T est un zéro, L n'est pas zéro. L'état nul de X est aussi testé R dans le dispositif de test 396 et le résultat emmagasiné dans la bascule SO qui autrement n'est pas utilisé pendant l'opération de l'horloge 1A. Puisque 5 est le complément à un du demi-multiplet L, > 10 Le registre de demi-multiplet Q reçoit le demi-multiplet gauche d'ordre supérieur X^. Si il est non nul X^ représente F. Ainsi, le registre 0 contient soit F soit une indication qu'une représentation étendue à un multiplet entier de F suivra. La phase d'horloge C1A.2 assure simplement que IG(X) chute pendant une phase 15 d'horloge de sorte que son niveau augmente pendant que la phase suivante est reconnue par l'interface du dispositif I/O. Tandis que si le niveau de IG(X) ne chute que pendant une courte période, l'interface ne peut pas reconnaître qu'un autre multiplet de la clé comprimée est nécessaire. La phase d'horloge C1A.3 commande l'acquisition de la représentation éten-20 due à un multilplet entier de L s'il y en a. Si SO n'est pas nul il ne se produit pas de transfert. Si SO est égal à un, IG(X) est augmenté pour demander le multiplet suivant de CK. Les deux moitiés X , X du multiplet L éten- L R du sont acheminées sous forme d'une chaine à l'additionneur au moyen des signaux de commande IGCHH J et IGCHH ). La chaine est ajoutée à un "un" actif L R 25 et acheminée par la bascule H au registre L. L'état nul de'"la somme est détecté par le dispositif de test 378 et conservé en déclenchant la bascule T. La phase d'horloge C1A.4 assure que IGCXJ chute pendant une phase d'horloge dans le cas où le niveau de IGCX) est augmenté pendant la phase C1A.3. Ceci assure l'identification du multiplet CK suivant à l'interface 353 pendant la 30 phase C1A.5. La phase d'horloge C1A.5 compare le contenu du registre Ec soit avec la représentation d'un demi-multiplet, soit avec la représentation d'un multiplet complet de F. Le registre a son contenu transféré au côté gauche de l'additionneur 376A. Si le dispositif de test de zéro 395 indique un état non nul 35 dans le registre 0, quatre uns d'ordre élevé sont transférés par un signal de commande IG C11113 au côté droit de l'additionneur 376A. Le un actif IGC+1 ] est aussi présenté à l'additionneur. La triple somme est conservée dans la bascule H pour représenter la comparaison entre E^ et le demi-multiplet F, Mais si un dispositif de test de zéro 395 indique un état zéro dans le 40 registre G), la représentation en multiplet complet de F est demandée en éle- 69 45786 29 2027737 vant les niveaux des signaux de commande IG(X) . Les deux demi-multiplets CX^, XR)représentant les multiplets F étendus sont reçus et acheminés au côté droit de l'additionneur par IGCWR), ainsi qu'un un actif qui est acheminé par IGC+1], La source est conservée dans la bascule H pour représenter le résul-5 tat de la comparaison entre et le multiplet F étendu. La phase d'horloge C1A.6 effectue le branchement à six voies résultant de la comparaison de E^ et F, et le test de zéro sur L emmagasiné dans la bascule T comme cela était réalisé dans les réalisations décrites antérieurement. 10 Les circuits de commande de transfert spéciaux représentés sur la figure 23 permettent d'engendrer les signaux de commande de transfert nécessaires pendant le cycle d'horloge C1A. La figure 21 représente comment les commandes 851 reçoivent les phases C1A.1, C1A.3, C1A.15. Les commandes 851 reçoivent aussi les signaux de sortie -J5 IGCH ) provenant des commandes 854 pour actionner les portes IGCHH ) et R R IGCHHjJ en accord pendant les cycles d'horloge CD et C2, C9. Les commandes 854 ne reçoivent que les phases d'horloge C0.1 à C0.3 et C2.1 à C9.2. Les phases C2.1 à C9.2 sont amenées aux commandes d'horloge 852, qui reçoivent aussi à l'entrée C1.4 le signal de phase C1A.6 provenant du circuit d'horloge 20 spécial 855. Le signal de mise en route C1 provenant des commandes 852 est amené à l'entrée C1A au circuit d'horloge spécial 855 pour amorcer le cycle d'horloge C1A au lieu de C1. Les sorties des commandes 851 et 854 sont amenées aux entrées des commandes spéciales 856, représentées en détail sur la figure 24. Les circuits 25 856 font une sélection parmi les deux séries de commande 851 et 854 pour la fonction de transfert nécessaire dans le circuit de la figure 20 afin d'obtenir un fonctionnement maximum pendant tous les cycles d'horloge conformément à la seconde réalisation de l'invention. Bien que l'on ait décrit dans ce qui précède et représenté sur les 3Q dessins les caractéristiques essentielles de l'invention appliquées à un mode de réalisation préférée de celle-ci, il est évident que l'homme de l'art peut y apporter toute modification de forme et de détail qu'il juge utiles sans pour autant sortir du cadre de ladite invention. 69 45786 30 2027737 REVE N. D I C A T I O fj S 1. Procédé pour rechercher, à partir d'un argument de recherche composé d'une suite ordonnée de un ou plusieurs multiplets, dans un index comportant une succession de groupes de signaux enregis-5 très associés chacun à un bloc d'informations [groupes qui seront appelés par la suite "clés comprimées" ou "clés"), chaque clé comprimée comportant un champ "facteur" contenant une indication numérique et éventuellement un champ 'fiultiplets de clé" comportant une suite ordonnée de un ou. plusieurs multiplets, un ordre de classement ayant été préalablement défini pour les multiplets 10 susceptibles de se trouver dans un argument de recherche et dans le champ "multiplets de clé" d'une clé comprimée, une clé comprimée associée à on bloc d'informations correspondant à l'argument de recherche^ caractérisé par les opérations suivantes : a/ comptage des multiplets de l'argument de recherche, dans l'ordre 15 où ils sont rangés et comparaison, à chaque étape du comptage, du nombre compté et du contenu du champ "facteur" d'une clé comprimée, b/ arrêt du comptage, lorsque cette comparaison indique une égalité, lecture du dernier multiplet de l'argument de recherche compté, lecture du champ "multiplets de clé"de la clé comprimée et commande de la suite de 20 l'opération eh fonction, des informations résultant de ces lectures. 2. Dispositif pour rechercher, à partir d'un argument-de recherche composé d'un ou plusieurs multiplets, dans un index constitué conformément à la revendication 1, une clé comprimée permettant de retrouver un bloc d'informations correspondant audit argument de recherche, caractérisé par des moyens pour 25 effectuer les opérations suivantes : - comparaison du contenu du champ "facteur" d'une clé comprimée avec le contenu d'un compteur et, en fonction du résultat de cette comparaison. a/ si le contenu dudit champ est inférieur au contenu dudit compteur : accès au bloc d'information associé à cette clé, 30 d/ si le contenu dudit champ est supérieur au contenu du compteur : accès à la clé suivante et continuation de la recherche à partir d'une valeur inchangés eu contenu du compteur, c/ si le contenu dudit champ est égal au contenu du compteur : lecture successive dans l'ordre mentionné des multiplets 35 du champ "multiplet de clé" à partir du multiplet d'ordre le plus élevé, - lecture successive synchrone de multiplets de l'argument de recherche. 69 %78$£ 31 2027737 avancement du compteur à chaque, lecture, comparaison, à chaque lecture, entre le multiplet lu à partir de la clé et le multiplet lu à partir de l'argument de recherche et commande de la suite de l'opération en fonction du résultat de cette comparaison. 5 3. Dispositif conforme à la revendication 2, caractérisé en outre par des moyens pour commander les opérations suivantes en fonction du résultat de la comparaison entre le multiplet lu à partir de la clé comprimée (premier multiplet] et le multiplet lu à partir de l'ergument de recherche (second multiplet]' 10 "" a/ si le premier multiplet est situé avant le second multiplet dans l'ordre dé classement défini dans la revendication 1 : accès à la clé suivante et continuation de la recherche avec cette nouvelle clé, " b/ si le premier multiplet est situé après le second dans cet ordre de classemëift : accès au bloc d'information associé à la clé. 15 ~~4. Triëpoëitif conforme à la revendication 3, caractérisé en outre par des moyens pour effectuer les opérations suivantes, si le premier multiplet est égal au second! ** ' "Déterminer s'il existe dans l'argument de recherche, des multiplets placés après le multiplet traité, 20 "arrêter la recherche si de tels multiplets n'existent pas, si de tels multiplets existent, déterminer s'il existe dans la clé, des multiplets placés après le multiplet traité, J~ "accéder à la clé suivante et continuer la recherche avec cette clé si de tels multiplets n'existent pas, 25 'continuer la recherche avec la même clé si de tels multiplets existent. 5. Dispositif conforme à l'une des revendications 2 à 4 caractérisé en outre par des moyens pour détecter l'absence de champ "multiplets de clé" dans une clë comprimée et pour commander l'arrêt de la recherche si cette absence est détectée.