Brevet FR2027738A1 — publié le 19701002

6" 3 2027738 compression d'index est l'accélération da la recherche avec une mémoire de capacité inférieure. Par conséquent, un objet de cette^invention est de réaliser un procédé et un système nouveaux qui permettent d'engendrer un index comprimé en suppri-5* mant la redondance due au classement. Un autre objet da cette invention est de réaliser un procédé et un système nouveaux qui permettent d'effectuer une recherche dans un indieoc comprimé pour .•sa Jias , Tsis si . • * . - •• ' .• •••-. réduire le nombre des multiplets qui doit Ôtre exploré par la machine pendant une recherche par rapport au nombre de multiplets qui doit ôtre exploré pour srrj , « . . • . - . 10 une recherche analogue avec l'index non comprimé correspondant. Ceci augmente > sL-piizrèn^H.ïr .T~-J •. - - ... - la vitesse de recherche de la machine par rapport à la vitesse de recherche -nor srm ^s-j'jcnz • • • - • - • - de l'index d'origine non comprimé pour une même vitesse de lecture des multiplets- dans ia machine. -•T Un objet plus particulier de cette invention est d'effectuer une" recher- rsv &jnîSi!2- rsvycr . - . - • . . • 15 che dans un index comprimé dans lequel chaque entrée comprimée a une'longueur qui ne dépend pas du tout de la longueur de la clef non comprimée correspondante. Par exemple, une clef non comprimée qui comporte cent ou mille multiplets peut être représentée par une clef comprimée ayant un seul chânp de commande et un seul multiplet de clef. La valeur de la compression dépend princi-20 paiement du resserrement de l'index,j'est-à-dire de l'importance des variations dans la relation ordonnée parmi les clefs non comprimées de l'index. L'invention utilisa un format de clef comprimée ayant un champ de comman-..'sbrr: as :■ - . • ■ de qui représente la position du multiplet inéégél d'ordre supérieur dans la -•£b to.ir^-scssc:: • • • clef non comprimée qu'il représente. Cette position est obtenue en comparant 25 la clef non comprimée représentée avec la clef non comprimée immédiatement suivante dans la séquence ordonnée. La dernière clef non comprimée d'un couple devient la première cle-f non comprimée du couple suivant dans la séquence pour, engendrer la clef comprimée suivante. L'invention fournit au moins un multiplet avec chaque cle-f coaiprimée qui 30 est le multiplet d'ordre le plus bas dans la clef. Ce multiplet: est obtenu à partir d'une clef lion comprimée suivant immédiatement la clef non comprimée représentée. Ce multiplet de la. clef est le^multiplet inégal d'ordre le plus haut, dans la clef non comprimée immédiatement suivante qui à son emplacement représenté par le champ de commande. j» ~ 35 . - Certaines clefs comprimées auront plus d'un seul multiplet. Ceci est déterminé- par la relation entre le 'champ de commande'en cours (P ) et le champ de commande antérieur CP^ ^3. Si le champ de commande en cours est égal au • inférieur au champ de commande antérieur,' un seul multiplet de clef CK.Î est obtenu dans la clef comprimée en cours (CiO. Mais "si le.champ de commande-en 40 cours est supérieur "âu champ de commande antérieure la clef comprimée en cours 45787 4 2027738 aura plusieurs multiplets, ce nombre de multiplets étant égal à un plus la différence entre les deux champs de commande. Les indicateurs d'adresses et les données peuvent être associés aux clefs comprimées en les plaçant à cûté de leurs clefs respectives. Lorsqu'on effectue une recherche, le dispositif de l'invention emmagasine le champ de commande CP^_yj ) de la clef comprimée antérieure et le compare au champ de commande CP^ de la clef comprimée en cours en soustrayant le premier du dernier *-a différence détermine le nombre des multiplets dans la clef comprimée en cours. Il y aura un multiplet si la différence est nulle ou négative. Mais il aura plusieurs multiplets dans la clef si la différence est égal# à une différence positive plus un. Le champ de commande détermine toujours la position du multiplet d'ordre la plus bas dans la clef comprimée. Cependant, les multiplets dans la clef sont généralement lu de l'ordre le plus haut à l'ordre le plus bas. Pour déterminer la position du multiplet lu en premier et d'ordre le plus haut dans la clef comprimée en cours par rapport è la clef non comprimée qu'il représente, les champs de commande antérieur et en cours sont nécessaires. La position du multiplet de la clef d'ordre le plus haut est un facteur nécessaire pour déterminer la position de multiplet dans l'argument de recherche avec laquelle le premier multiplet de la clef (ordre le plus haut) peut être comparé. Les multiplets restants dans la clef comprimée correspondront aux multiplets de l'argument de recherche d'ordre inférieur. Au début de la recherche un compteur d'égalité est mis aux conditions initiales, par exemple on le met à un. Cette valeur dans le compteur est comparée au facteur calculé pour chaque clef comprimée recherchée en séquence. D'autres objets caractéristiques et avantages de la présente invention ressortiront mieux de l'exposé qui suit, fait en référence aux dessins annexés à ce texte, qui représentent un mode de réalisation préféré de celle-ci. La figure 1A représente un index non comprimé et la figure 1B représente l'index comprimé obtenu à partir de l'index non comprimé. Les figures 2A et B représentent les circuits d'emmagasinage intermédiaires et les circuits entrée-sortie utilisés pour emmagasiner un index non comprimé et un index comprimé respectivement. La figure 3 représente les circuits d'horloge et de commande de mode. La figure 4A représente la chronologie du "mode formation" pour le circuit de la figure 6 et la figure 4B représente la chronologie du mode de recherche pour le circuit des figures 9A et b. La figure 5A représente le format pour un bloc d'index comprimé bas alors que la figure 5B représente un format pour un bloc d'index comprimé haut. La figure B représente les commandes dB l'horloge de mode de formation. 69 45787 5 2027738 La figure 7 représente les commandes d'adresses de la mémoire intermédiaire et autres commandes utilisées 'pendant la formation de clef comprimée. Les figures 8A-D représentent des circuits commandant la formation des clefs comprimées. 5 Les figures 9A et B représentent les commandes d'horloge de mode de re cherche utilisées dans la présente invention. Les figures 10 et 11 représentent les commandes de mémoire utilisées pour engendrer un index comprimé et effectuer une recherche dans un index comprimé. Les figures 12 et 13 représentent les circuits .utilisés pour effectuer 10 une recherche dans un index comprimé. Les figures 14A-C représentent le procédé utilisé pendant le mode de recherche. A. MODE DE FORMATION Dans ce mode, l'invention utilise une séquence de clefs non comprimées 15 [UK]. Les clefs peuvent comprendre un index de recherche pour un type quelconque de bloc d'information. Par exemple, chaque clef peut être un nom, un numéro, ou n'importe quelle désignation exprimée en caractères alphabétiques ou numériques et/ou spéciaux, qui peut représenter un bloc d'informations tel qu'un enregistrement magnétique, fichier ou inventaire etc.. L'adresse (emplacement] 20 du bloc que représente la clef est acheminée avec chaque clef. Cette adresse est appelée par la suite indicateur puisqu'elle détermine en effet l'emplacement du bloc d'origine représenté par la clef. Bien que les blocs d'informations se présentent de préférence sous une forme accessible par machine, ils peuvent aussi être retrouvés manuellement en utilisant les indicateurs. Les 25 emplacements réels des blocs peuvent être dans un ordre quelconque par rapport à leurs clefs, c'est-à-dire, ils peuvent être disposés au hasard, séquentiellement, etc... Si les clefs non comprimées sont initialement obtenues, non classées, elles sont disposées dans une séquence ordonnée avant que l'opération en mode 30 de formation commence. On peut donner comme exemple de séquences de clefs non comprimées les noms d'un annuaire téléphonique, les noms des habitants des Etats-Unis, les numéros d'employés dans une entreprise, les titres de tous les livres dans une bibliothèque, les numéros d'articles dans un inventaire, etc... Il ne peut y avoir deux clefs non comprimées identiques dans la séquence, 35 par exemple les adresses sont ajoutées aux noms identiques pour les distinguer. L'ordre des clefs ordonnées est déterminé par une séquence de caractères choisis telle que l'ordre numérique, alphabétique, EBCDIC, ASCII, etc... Par exemple, dans un annuaire téléphonique ou dans un dictionnaire on utilise la séquence de classement utilisant les lettres dans l'ordre alphabétique. Lors-40 qu'on ordonne les clefs, l'indicateur associé à chaque clef est acheminé avec 69 45787 8 2027738 la clef à chaque emplacement où la clef est placée dans la séquence ordonnée. Pour faire la description détaillée de cette invention, on prendra-des séquences croissantes mais il est clair que les mêmes principes s'appliquent aux séquences décroissantes. . . .^ . 5 Si la séquence de clefs non comprimées est très longue, elle peut être divisée en sous groupes dans la séquence globale. La longueur des groupes séquentiels les plus.petits peut être choisie de façon à être compatible- avec la dimension d'un enregistrement physique utilisé par un dispositif entrée/sortie dans un ordinateur. Chaque enregistrement peut être traité sous forme d'une 10 unité d'entrée distincte pour cette invention. Chaque sous groupe sera appelé par la suite enregistrement d'index non comprimé. La figure 1A représente un enregistrement d'index non comprimé, tandis que la figure 1B représente les clefs comprimées engendrées à partir de cet 15 enregistrement par cette invention. La première clef.comprimée CK au sommet de la figure 1B est obtenue à partir de la comparaison des première et seconde clefs non comprimées UK. placées dans la partie supérieure de l'index non comprimé de la figure 1A. La seconde clef comprimée est obtenue en comparant les seconde et troisième clefs 20 non comprimées etc... Finalement on obtient la dernière clef comprimée lorsque la clef non comprimée est comparée avec l'indication de fin d'enregistrement, ce qui constitue la dernière comparaison pour l'enregistrement d'index non comprimé. L'indicateur associé à la dernière clef comprimée est placé au bas de la figure 1B. 25 On considère que chaque comparaison commence à partir du caractère d'or dre supérieur dans les clefs non comprimées. Chaque clef comprimée tsauf la dernière) est constituée dé deux parties, un multiplet de position (P) et un ou plusieurs multiplets de clefs (K). Les multiplets P et K sont déterminés pendant la comparaison de deux clefs non 30 comprimées adjacentes. Le multiplet P est mis à une valeur qui représente l'emplacement des premiers multiplets inégaux résultant de la comparaison de la partie d'ordre supérieur des clefs non comprimées. Si deux positions de multiplets d'ordre le plus haut de deux clefs non comprimées sont inégales, P est égal à un. Si les premières positions de multiplet sont égales et que les se-35 condes sont inégales, P est égal à deux. Dans, cette réalisation P est mis à zéro avant de commencer les comparaisons pour un enregistrement d'index non comprimé et pour la dernière comparaison de chaque enregistrement d'index non comprimé. Le champ K est constitué d'un ou plusieurs multiplets pris à partir de 40 la seconde clef non comprimée dans un couple de clefs non comprimées compa 69 45787 7 2027738 rées. Las multiplets particuliers pris pour le champ K sont déterminés par les deux valeurs de P engendrées par la comparaison de clefs non comprimées en cours et la dernière comparaison de clefs non comprimées. Si la valeur P en cours est égale ou inférieure à la dernière valeur P, un seul multiplet 5 K est obtenu, qui est le premier multiplet inégal dans la seconde clef non comprimée de la comparaison en cours. Cependant, si la valeur actuelle de P est supérieure à la dernière valeur de P, le champ K. comprend plusieurs multiplets de la seconde clef non comprimée dans la comparaison en cours, placés après la position de multiplet définie par la dernière valeur P et tous les 10 multiplets suivants jusqu'à un multiplet comprenant le premier multiplet inégal à la valeur actuelle de P. Ainsi, tous les multiplets K sauf le dernier sont égaux. On va donner un résumé des régies pour engendrer un index comprimé Ci)s 1.- Formation de P^ 15 Pour engendrer la clef comprimée i, les clefs non comprimées i et (i+1) sont comparées multiplet par multiplet en commençant par la position de multiplet la plus significative jusqu'à ce qu'une différence soit détectée. L'emplacement de multiplet pour lequel on détermine une première inégalité détermine la valeur P actuel P^. (La com-20 paraison nécessaire pour engendrer la clef comprimée peut se termi ner au premier multiplet inégal, mais elle peut se prolonger pour des mises en ordre). 2.- Formation de K.^ La dernière valeur P ] est conservée pour déterminer K^. 25 (a) si PA Pi-iJ Un seul multiplet est enregistré dans le champ K, et il est à la position de multiplet P^ de la clef non comprimée (i+1). (b) si P± > P^_.jl Le nombre de multiplets à enregistrer dans le champ K est 30 ^i"^! 1" 1-8 c'1amP K commence avec le multiplet situé à la posi tion pi_1+1 jusqu'au multiplet compris à la position P.^ de la clef non comprimée (i+1). 3.- ^Indicateur L'indicateur (R) associé à la clef non comprimée i (pendant que l'on 35 compare les clefs non comprimées i et i+1) est relié à la clef com primée i pour fournir un index comprimé de la forme PKR. 4.- Fin d'enregistrement Le nombre de clefs comprimées engendrées est égal au nombre de clefs non comprimées dans l'enregistrement d'index non comprimé. Cependant 40 les clefs comprimées résultantes ne comportent qu'une fraction des 69 45787 6 2027738 multiplets que l'on trouve dans l'enregistrement des index non comprimés. Lorsqu'on atteint la fin de l'enregistrement des index non comprimés, la dernière clef comprimée est formée de la manière suivante; 5 Ca) P est mis à zéro (ce qui représente la fin du bloc d'index comprimé) (b) K. est sauté (il n'y a pas de multiplet K dans ce cas) et (c) L'indicateur R associé à la dernière clef non comprimée est placé à côté du multiplet P nul. 10 Exemple: Liste non comprimée Index comprimé P » 15 1 2 3 4 5 Indicateur P K Indicateur A B C D 1 3 ABD 1 A B □ D 2 4 E 2 A B D E F 3 2 C 3 A C □ E F 4 5 DEG 4 A C □ E G 5 2 D 5 A □ 0 B B. MODE DE RECHERCHE 20 Dans le mode de recherche on utilise un argument de recherche, qui peut être une clef non comprimée Quelconque que l'on trouve au non dans l'index non comprimé initial représentant un bloc d'informations à trouver. Régie pour la Recherche (Utilisée sur les figures 11 à 14): 1. La recherche pour argument de recherche donné commence au début d'un 25 bloc d'index comprimée et continue d'une clef comprimés à la suivante en série. Le champ K dans chaque clef comprimée est examiné un multiplet à la fois en partant du multiplet d'ordre le plus haut et il est comparé avec un multiplet de l'argument en cours. 2. Le multiplet P^ de chaque clef comprimée en cours qui est lu est 30 conservé. Initialement la valeur P "^ est mise à zéro pour lire la premiere clef comprimée. Le multiplet P.^ conservé devient le multiplet P ^ lorsque P^ de la clef comprimée suivante est lu. Par suite la longueur du premier champ K est pi~0=pi' La longueur du champ K dans une clef comprimée quelconque a (P^ - Pi_13 multiplets de long si > P^-35 3. La clef comprimée est comparée avec l'argument de recherche un mul tiplet à la fois en commençant au multiplet d'ordre le plus haut de l'argument de recherche. Chaque fois qu'un multiplet de l'argument de recherche est égal au multiplet K, ce multiplet est remplacé par le multiplet d'ordre inférieur suivant dans l'argument de recherche. Le multiplet approprié de l'argument 45787 9 2027738 de recherche est comparé séquentiellement avec les multiplets K en commençant par les. multiplets K d'ordre supérieur dans chaque clef comprimée. Pour une clef comprimée quelconque avec (P^ - > 1, le premier multiplet K. comparé est à la position + D et on continue au multiplet K suivant d'ordre inférieur lorsque A > K jusqu'à ce que le multiplet K en P^ soit comparé. Pour une clef comprimée quelconque avec CP^ - £-1» seul le multiplet K identifié par P^ est comparé au multiplet de l'argument. Ceci est réalisé de la manière suivante: a. Un nombre E appelé valeur d'égalité est conservé et représente le nombre actuel de multiplets de l'argument trouvé égaux aux multiplets K pendant la balayage des clefs comprimées. Chaque fois que A = K, la valeur E est augmentée de un, uniquement si E (position du multiplet de l'argument de recherche) est égale à la position dans la clef non comprimée du multiplet K comparé à ce moment. b. Si A > K dans une comparaison entre les multiplets A et K appropriés la recherche se poursuivra en passant à la clef comprimée suivante. c. La recherche est terminée par la première comparaison qui trouve A d. L'indicateur désiré associé à la clef comprimée terminant la recherche est utilisé pour rechercher le bloc d'informatiops qu'il repré-' sente qui est alors trouvé. e. On peut faire une vérification en comparant le bloc d'informations retrouvé avec l'argument de recherche. Il-y aura égalité si le bloc est représenté dans l'index non comprimé initial. Une inégalité indique que le bloc n'est pas représenté initialement et l'index comprimé peut alors être mis à jours pour représenter le nouveau bloc si nécessaire. C. SYSTEME FONCTIONNANT EN MODE DE FORMATION 1. Description générale Sur la figure 2A, un signal d'entrée pour une opération en mode de formation est amené à une mémoire intermédiaire 10 dans laquelle les clefs non comprimées UK sont disposées suivant l'organisation représentée. La mémoire intermédiaire 10 emmagasine les données par multiplets (caractères), chaque multiplet peut comprendre huit bits de données. (Chaque multiplet emmagasiné peut comprendre un bit de parité classique pour le contrôle d'erreurs Puisque le bit de parité n'a pas d'importance pour l'invention, il ne sera pas décrit). L'opération de l'invention est amorcée par un signal d'entrée "Mode de 69 45787 10 2027738 formation" ou "Mode de départ" sur la figure 3. Un signal de départ peut être envoyé d'un certain nombre de façons. Il peut être engendré1 manuellement en fermant un commutateur 50 sur la figure B ou 210 sur la figure 9A. Mais ce signal est de préférence envoyé à partir d'un ordinateur en réponse à l'exé-5 cution d'une instruction particulière qui peut être classique. L'instruction peut être le mot de commande de canal particulier CCW lorsque la présente invention est utilisée dans un canal d'ordinateur ou dans une commande de dispositif entrée/sortie. Lorsque l'invention est exécutée entièrement, dans l'unité centrale de traitement CPU d'un ordinateur, une instruction spéciale, 10 telle qu'une instruction appel superviseur SVC) peut amorcer le fonctionnement. Dans tous les cas, le code opération de l'instruction ou le code interruption de l'instruction SVC est nécessaire pour faire la distinction entre le mode de formation et le mode de recherche pour amener les signaux d'entrée corrects au basculeur de mode 20 sur la figure 3. 15 Les quatre premiers multiplets dans la mémoire intermédiaire 10 sont des multiplets de repère (appelés drapeaux) qui fournissent des paramètres fondamentaux définissant l'organisation des données dans la mémoire intermédiaire. Le multiplet initial MUK.L contient une valeur qui définit la longueur en multiplets de chaque registre UK-1, UK.-2 ... UK-N), qui sont reservés respecti-20 vement aux clefs non comprimées. Chaque registre a la longueur maximum des clefs non comprimées MUK.L. Le multiplet LV/L désigne un niveau (LVL) pour l'index comprimé qui est à engendrer à partir de l'index non comprimé initialement dans la mémoire intermédiaire 10. On utilise généralement un indexage à plusieurs niveaux pour accé-25 lérer la recherche. L'invention peut être appliquée pour "engendrer un niveau quelconque d'index. Le multiplet RL fournit la longueur en multiplets de chaque registre indicateur (R-1, R-2 .... ; R-N). Le nombre de multiplets nécessaire dépend du type d'adresses utilisées pour rechercher un bloc. Par exemple, si ce bloc est enre-30 gistré sur un disque, on doit avoir une longueur de dix multiplets. Le multiplet suivant est réservé au premier multiplet P engendré. Les registres UK et R suivent. Chaque registre UK est suivi par un registre R associé avec la même référence numérique. Par exemple l'indicateur introduit dans le registre R-1 adresse la clef non comprimée introduite dans 35 le registre UK-1. L'utilisation des multiplets de repère RL et MUKL permet de faire varier facilement la capacité des registres UK et R dans divers cas lorsque la longueur maximum pour les clefs non comprimées ou indicateurs reçus est différente. 11 n'est pas nécessaire de changer la capacité de la mémoire intermédiaire 40 10 pour loger un plus grand nombre de clefs non comprimées et indicateurs lors 69 45787 n 2027738 que la longueur maximum de l'un ou l'autre ou des deux est rendue plus petitej il suffit d'introduire simplement des valeurs plus petites-dans l'un ou l'autre des multiplets de repère ou dans les deux. Le caractère d'ordre le plus haut d'une clef non comprimée quelconque 5 est introduit dans un registre UK avec un alignement des multiplets situés à gauche sur la figure 1. C'est-à-dire le premier caractère (le plus significatif) de la clef est introduit dans la position de multiplet la plus à gauche du registre UK. Les autres caractères de la clef suivent immédiatement à droite. Toute position de multiplet inutilisée dans le registre UK à droite d'une 10 clef non comprimée est remplie par le caractère d'ordre le plus bas dans la séquence de classement de la série de caractères utilisés, par exemple, un zéro, un blanc ou un caractère nul. Par suite une clef non comprimée introduite quelconque peut avoir une longueur variable allant jusqu'à la capacité maximum de son registre UK. Une clef non comprimée supérieure à la capacité 15 du registre UK est coupée à son côté d'ordre inférieur, c'est-à-dire, on élimine les caractères situés à gauches, qui ne rentrent pas dans le registre UK. Cette élimination n'affecte pas nécessairement la clef comprimée engendrée ainsi. La clef non comprimée coupée doit cependant être une clef unique. Le dernier indicateur R-N de la chaîne d'entrée peut être suivi par un ou 20 plusieurs multiplets d'indication de fin pour indiquer la fin de l'enregistrement des clefs non comprimées. La façon d'alimenter la mémoire intermédiaire 10 ne fait pas partie de cette invention, mais il est évident que cette opération peut être réalisée par une programmation classique d'un ordinateur universel. 25 Les circuits décrits dans les schémas fonctionnent en utilisant des cycles d'horloge. Les modes de formation et de recherche utilisent différentes séquences de cycles de commande d'horloge. Pour le même mode, la séquence des cycles d'horloge peut être différente pour les niveaux supérieurs et pour le niveau le plus bas. 30 Dans un mode, un seul cycle d'impulsions T0-T7 est engendré par le circuit d'impulsions de synchronisation représenté sur la figure 3. Ces impulsions sont transmises aux commandes d'horloge de la figure B pour traiter chaque multiplet de données, lorsque le basculeur de mode 20 est enclenché par un signal de mode de formation. 35 Une séquence entière de cycles de commande d'horloge dans le mode de for mation se produit une fois par chargement de la mémoire intermédiaire 10 par une liste de clefs comprimées. Les commandes d'horloge de la figure B déterminent la succession des opérations nécessaires pour le fonctionnement de la réalisation décrite en mode de formation. Une succession séquentielle et une 40 succession désordonnée (branchement) sont commandées par la commande d'horlo 69 45787 12 2027738 ge représentée sur la figure 6). La succession des types de cycles est différente pour les opérations de niveau haut et de niveau bas qui sont représentées sur les figures 5A et 5B, Sur la figure 3, lorsque le basculeur de mode 20 est enclenché par un 5 signal de mode de formation (qui peut être obtenu à partir d'une instruction de l'ordinateur) il conditionne alors une porte ET 21 pour transmettre des impulsions à partir d'un oscillateur 23 à un circuit en anneau qui fournit les impulsions de sortie TD-T7 sur les figures 6-0, Chaque cycle d'impulsions de sortie T0-T7 détermine un cycle de fonctionnement pour les commandes d'hor-10 loge de la figure 6 avec la chronologie associée représentée au haut de la figure 4A. La figure 4A donne les signaux représentant la séquence des commandes d'horloge utilisée par la réalisation fonctionnant en mode de formation. Les commandes d'horloge dans cette réalisation donnent une séquence de sept types 15 de cycles de mode de formation utilisé chacun dans un but différent. Sur la figure 4A, un cycle est actif lorsque le signal est au niveau haut et inactif lorsqu'il est au niveau bas. Chaque cycle de commande d'horloge fait avancer d'un multiplet l'adresse de recherche dans un compteur d'adresses 110 représenté sur la figure 7. Le premier est le cycle MUKL qui provoque le transfert 20 du multiplet MUKL de la mémoire 10 à un registre MUKL sur la figure 7. Un cycle LVL suit immédiatement et provoque le transfert du multiplet de niveau à un registre LVL sur la figure 7. Le multiplet de niveau détermine si un index comprimé de niveau haut ou de niveau bas doit être engendré comme représenté sur la figure 5A ou 50. Ensuite, suit un cycle RL pour transférer de façon 25 analogue le multiplet de longueurs d'indicateur RL au registre RL sur la figure 7. On suppose à ce moment que la valeur du multiplet RL indique l'index de niveau le plus bas. Ensuite, il se produit un cycle IP qui ne provoque pas de transfert mais arrête seulement l'adresse de la mémoire. Le multiplet IP est sauté pendant cette séquence de recherche dans la mémoire intermédiaire 30 10. Un cycle A1 suit le cycle RL sur la figure 4A pour rechercher le multiplet d'ordre le plus haut dans la clef UK-1. Un cycle A2 suit le cycle A1 pour rechercher le multiplet d'ordre le plus haut dans UK-2 pour une comparaison de ces multiplets de même ordre. L'indexage d'adresses est réalisé sur l'adresse 35 du multiplet A1 pour rechercher le multiplet A2 correspondant. Pour cela l'adresse du multiplet A1 (de la clef non comprimée i) est indexée par la somme des valeurs dans.les registres MUKL et RL afin d'adresser le multiplet A2 correspondant (de la clef non comprimée i+1). Ceci est réalisé sur la figure 7 par les additionneurs A et B pour obtenir l'adresse effective du multiplet 40 comparé pendant le cycle A2. Le compteur d'adresses de recherche 110 sur la 69 45787 13 2027738 figure 7 maintient les adresses de recherche en cours sauf l'adresse du multiplet A2. L'adresse, effective A2 provenant de l'additionneur A adresse le multiplet à rechercher à partir de la mémoire intermédiaire 10. Etant donné qu'il est conditionné par le cycle d'horloge A2, l'additionneur B ne fournit un si-5 gnal de sortie non nul que pendant un cycle A2. Lorsqu'il est conditionné l'additionneur B fournit un signal de sortie qui est la somme des contenus des registres MUKL et RL.Par suite l'additionneur A reconnait normalement que son entrée B a une valeur nulle sauf pendant le cycle A2. En conséquence, les multiplets les plus à gauche dans les registres UK-10 1 et UK-2 sont recherchés par les cycles A1 et A2 initial et ils sont transférés respectivement dans le registre de multiplets A1 et le registre de multiplets A2 sur la figure SA. Un comparateur 125 compare les multiplets dans les registres A1 et A2 représentés sur la figure SA. Après la comparaison des multiplets d'ordre le 15 plus haut, les multiplets d'ordre le plus haut suivant sont recherchés par le cycle A1 suivant suivi par le cycle A2 suivant et on fait une comparaison de ces deux multiplets. Les cycles d'horloge A1 et A2 alternent de cette manière un certain nombre de fois ce qui est déterminé par la valeur dans le registre MUKL de la figure 7 qui est indiquée par la sortie d'un comparateur 114 20 sur cette même figure. Le compteur d'adresses de recherches 110 est avancé à la fin (T7) de chaque cycle d'horloge, sauf à la fin du cyle A1 puisque l'adresse A1 doit alors rester à indexer au multiplet A2 correspondant. Dans le dernier cas le compteur d'adresses de recherche 110 est avancé à l'adresse du multiplet suivant 25 à la fin de chaque cycle A2 par une impulsion T7 pour adresser les multiplets A1 suivant d'ordre inférieur. Un compteur de multiplets UK CCTR) sur la figure 7 est avancé par chaque cycle A2 Cà l'instant T1 sur la porte 106) pour indiquer la position des multiplets comparés dans le couple de clefs non comprimées actuel. 30 Le dernier multiplet recherché à partir de chaque registre UK-i et UK- i+1 est indiqué par un signal de sortie FIN UK provenant du comparateur 114 de la figure 7 qui signale lorsque le compteur de multiplets UK (qui est avancé par les cycles A2) atteint la fin des registres UK comparés Cla valeur MUKL). Pendant le dernier cycle A2 pour un couple de clefs non comprimées, le 35 compteur d'adresses de recherche 110 de la figure 7 est avancé par la porte 100 à l'instant 17 pour adresser le premier multiplet dans le premier registre d'indicateur R-1 dans la mémoire intermédiaire 10. Ceci amorce le premier cycle R comme représenté sur la figure 4A. Les cycles R se répètent une fois par transfert de multiplets indicateurs pendant le nombre de multiplets déter-40 miné par la valeur dans le registre RL de la figure 7. Chaque cycle R fait 69 45787 14 2027738 avancer un compteur RL sur la figure 6D à l'instant T1 par l'intermédiaire de la porte 166 pour conserver un compte actuel des multiplets R recherchés. Un comparateur 169 reçoit les signaux de sortie du compteur RL et du registre RL pour indiquer un signal de sortie "égalité sur RL" lorsque le dernier mul-5 tiplet d'un indicateur est recherché. Ensuite les commandes d'horloge sur la figure 6 sont utilisées pour amorcer un cycle A1 pour commencer une comparaison pour le couple suivant de clefs non comprimées dans les registres UK-2 et UK-3. (C'est-à-dire UK-i+1 du dernier couple devient UK-i pour le couple en cours). L'Intercalage des cycles A1 et 10 A2 se répète de la manière précédemment décrite qui concerne les clefs non comprimées dans les registres UK-2 et UK-3 suivant la comparaison des clefs non comprimés dans UK-1 et UK-2. Cet adressage automatique dans la mémoire intermédiaire 10 sa produit car le compteur d'adresses de recherches 110 de la figure 7 adresse le multiplet d'ordre le plus haut dans le registre UK-15 2 lorsqu'il est avancé à partir du dernier multiplet de R-1. Le registre UK-3 est adressé pendant chaque cycle A2 en indexant l'adresse A1 actuelle avec la somme des contenus des registres MUKL et RL comme précédemment expliqué. Cette séquence de comparaison de chaque couple de clefs non comprimées Ci et i+15 suivant chaque indicateur se poursuit jusqu'à ce que l'entrée (i+1) 20 soit détectée comme étant une indication de fin d'index par un décodeur d'indication de fin 180 sur la figure 8D. Le cycle A2 initial pour cette dernière comparaison provoque le transfert du premier multiplet d'indication de fin dans le registre A2 de la figure 8A. Le décodeur d'indication de fin 180 sur la figure 8D examine chaque multiplet dans le registre A2 pour le codage du 25 multiplet de fin d'index. Lorsqu'il est détecté, il signale la fin de l'enregistrement .non comprimé pour la mémoire intermédiaire 10 et qu'une dernière clef comprimée doit terminer l'index comprimé correspondant. 2. Description particulière Un signal de mode de formation provenant de la figure 3 à la figure 30 6 enclenche un basculeur de départ 45. Lorsqu'il est enclenché, ce basculeur conditionne une porte ET 52 qui reçoit l'impulsion d'horloge suivante TO provenant de l'horloge de la figure 3. La sortie de la porte 52 restaure le basculeur de départ par l'intermédiaire d'un circuit OU 49 et enclenche un basculeur qui fournit un signal de sortie pendant le cycle MUKL. Ce signal de 35 sortie est actif pendant un cycle MUKL. Il provoque le transfert du multiplet MUKL de la mémoire intermédiaire 10 de la figure 2A au registre MUKL de la figure 7 comme décrit-précédemment. L'enclenchement du basculeur MUKL assure que tous les autres basculeurs de cycle sur la figure 4 sont à l'état restauré en envoyant son signal de sortie par l'intermédiaire des circuits OU 36, 42, 40 44, 48, 51 et 56 aux entrées de restauration de ces basculeurs. De même le 69 45787 15 2027738 signal de sortie cycle MUKL conditionne le cycle LVL suivant provenant des commandes d'horloge en conditionnant une porte ET 46. ' L'impulsion TO provenant du cycle suivant du circuit; eut anneau de la figure 3 passe par la porte 46 pour enclencher un basculeur qui. fournit un si-5 gnal de sortie cycle LVL. Ce signal de sortie restaure le basculeur de cycle MUKL par l'intermédiaire du circuit OU 53 et assure la restauration de tous les autres basculeurs dans les commandes d'horloge de formation. Le multiplet LVL est transféré pendant le cycle LVL comme expliqué précédemment. Un basculeur de cycle RL est enclenché par l'impulsion TO suivante appli-10 quée à une porte ET 46 qui est alors conditionnée par le signal de sortie ey-le LVL. Ce signal de sortie cycle RL restaure le basculeur de cycle LVL par l'interdiaire du circuit OU 51 et assure la restauration de tous les autres basculeurs de cycles. De la même manière l'impulsion suivante TO enclenche un basculeur de cycle 15 IP par l'intermédiaire d'une porte ET 54 qui est conditionnée pendant le cycle RL et le basculeur RL est restauré par le signal de sortie cycle 1P par l'intermédiaire du circuit OU 48. L'impulsion TO suivante enclenche un basculeur cycle A1 par l'intermédiaire d'un circuit OU 38 et d'une porte ET 39 conditionnée par le signal de 20 sortie cycle 1P. Le signal de sortie cycle A1 restaure le basculeur cycle 1P et conditionne une porte ET 41. Après un seul cycle de A1, l'impulsion TO suivante arrive à la porte 41 pour enclencher un basculeur cycle A2. Une porte ET 43 est conditionnée par le signal de sortie du basculeur cycle A2 et aussi par un signal "pas d'égalité 25 sur MUKL" qui est actif jusqu'à ce que le multiplet d'ordre le plus bas d'une clef non comprimée quelconque soit recherché. Par suite l'impulsion TO suivante passe par la porte 43 et un circuit OU 33 pour enclencher de nouveau un basculeur cycle A1 qui restaure le basculeur cycle A2. De cette manière, les déclenchement et restauration alternés du basculeur 30 cycle A1 et du basculeur cycle A2 se produisent tant que dure le signal "pas d'égalité sur MUKL". Lorsque le niveau de ce signal chute, pour désexciter la porte ET 43, le basculeur cycle A1 ne peut plus être enclenché par l'impulsion TO suivante. En conséquence, d'une seule série comprenant MÈJK.L de cycles A1 et A2, 35 les multiplets P et K pour une clef comprimée sont engendrés à partir du couple de clefs non comprimées i et i+1 correspondantes qui sont comparées. Le cycle R est amorcé par la première impulsion TO pendant l'apparition d'un signal égalité sur MUKL. Une seule série de cyles R se poursuit pendant le nombre RL de cycles R, ce qui est signalé par un signal "égalité sur RL" 40 à une porte ET 37 provenant du comparateur 188 de la figure 0D. Une seule série 69 45787 16 2027738 de ces cycles recherche tous les multiplets dans un registre R dans la mémoire intermédiaire 10 suivant une clef non comprimée i. Le type de cycle d'horloge suivant dépend du fait qu'un signal d'index de niveau haut ou d'index de niveau bas est fourni à partir du registre LVL dans la figure 7. Les portes ET 30 5 et 33 de la figure 6 sont conditionnées respectivement par un des signaux indiquant le niveau de l'index comprimé nécessaire. Les formats des séquences de niveaux hauts et de niveaux bas sont représentées respectivement sur les figures 5A et 5B. Dans une opération de niveau bas, chaque série de cycles A1-A2 est suivie par une série unique de RL cycles R. Dans une opération de 10 niveau haut, deux séries de cycles A1-A2 sont suivies par une seule série de cycles R. Sur la figure 6, un signal "niveau bas" maintient continuellement un basculeur binaire BT dans son état restauré par l'intermédiaire d'un circuit OU 33a. Lorsqu'elle est conditionnée par un signal "niveau bas", la porte ET 33 15 est excitée par chaque signal "égalité sur MUKL" pour enclencher le basculeur cycle R suivant chaque série de cycles A1-A2. A la fin du nombre RL de cycles R indiqué par un signal "égalité sur RL" allant à la porte ET 37, le basculeur cycle A1 est enclenché pour amorcer la série suivante de cycles A1-A2 pour comparer le couple suivant de clefs non comprimées afin d'engendrer l'index 20 comprimé suivant. D'autre part si un signal "niveau haut" est amené à la porte 30 le basculeur binaire est enclenché (il est intialement à l'état restauré à cause de la restauration générale antérieure). Par conséquence, dans une opération de niveau haut, le premier signal "égalité sur MUKL" enclenche un basculeur binai-25 re BT qui engendre une impulsion par l'intermédiaire d'un""dispositif de mise en forme d.'impulsions 34 (qui peut être un monostable) pour enclencher le bas-culBur cycle A1 par l'intermédiaire du circuit OU 36. Ceci amorce une autre série de cycles A1-A2, suivant immédiatement la première série de cycles A1-A2 pour engendrer deux clefs comprimées successives comme couple de clefs com-30 primées de haut niveau. Lorsque le signal "égalité sur MUKL" se produit à la fin de la seconde série de cycles A1-A2 la porte ET 30 est de nouveau excitée pour fournir une autre entrée au basculeur binaire qui revient à son état restauré qui fournit donc un signal de sortie sur sa sortie de restauration pour engendrer une impulsion par l'intermédiaire du dispositif de mise en forme 35 d'impulions 31 qui enclenche les basculeurs de cycle R pendant l'impulsion T0. La fin de la série de cycles R (indiquée par un signal "égalité sur RL") excite la porte 37 pour commencer une série de cycles A1-A2 comme décrit précédemment. Le dernier cycle A2 de la série est indiqué par un signal "égalité sur MUKL" qui trouve le basculeur BT dans l'état restauré pour provoquer un 40 second cyle A1-A2 comme décrit précédemment. 69 45787 17 2027738 Une fois que le dernier signal UK. a été balayé dans la mémoire intermédiaire 10, une dernière clef comprimée doit être engendrée» Ceci nécessite un cycle P suivi par RL cycles-R. Le circuit OU 33b de la figure 6 reçoit un signal "Fin d'enregistrement" provenant de la figure 8D et provoque un cycle 5 R comme cycle suivant à partir du circuit de commande de cycle. Le nombre RL de cycles R est mesurés par le compteur RL de la figure 6D et une impulsion de restauration générale est fournie à partir du monostable 185 de la figure 8D à la figure 6 pour restaurer le circuit de commande de cycle et ainsi terminer son fonctionnement jusqu'à ce que l'impulsion de départ suivante soit 10 reçue. 3. Sortie - Description Générale On a décrit précédemment comment l'adresse de recherche en cours pour chaque multiplet indicateur, UK et de repère dans la miméire intermédiaire 10 est incrémentée séquentiellement et maintenue par le: compteur d'adresses 15 de recherche de la figure 7. D'une manière analogue une adresse d'emmagasinage est incrémentée séquentiellement ou maintenue dans un compteur d'adresses d'emmagasinage 156 de la figure 8C pour chaque multiplet CK et indicateur à emmagasiner dans la mémoire intermédiaire 10. Les opérations UK et CK sont simultanées bien que les transmissions de 20 multiplets provenant et allant à la mémoire intermédiaire 10 soient multiple-xées dans le temps puisque cette mémoire ne peut adresser qu'un seul multiplet à la fois dans la réalisation décrite. Après avoir été restauré le compteur d'adresses de recherche de la figure 7 commence en adressant l'adresse de multiplet zéro (multiplet MUKL). Le multi-25 plet MUKL initial est considéré ici comme ayant une adresse de déplacement nulle qui peut être à l'emplacement d'adresse de base dans un type quelconque de mémoire. Après avoir été restauré le compteur d'adresses d'emmagasinage de la figure 6C commence à adresser l'adresse de multiplet 3 (multiplet 1P). Par suite, les multiplets de repère originaux MUKL, LVL, et RL aux adresses 30 de déplacement 0, 1 et 2 ne sont pas perturbées par les opérations d'emmagasinage. Ils peuvent être ensuite emmagasinés avec l'index comprimé une fois que l'enregistrement d'index comprimé est engendré. Le multiplet P pour la première clef comprimée est; emmagasiné dans l'emplacement de multiplet 1P réservé dans la mémoire intermédiaire 10. Le premier 35 multiplet K est emmagasiné pour chevaucher le premier multiplet UK (multiplet d'ordre le plus haut). Les multiplets CK et R associés suivent successivement sans que des emplacements de multiplets soient sautés, à l'intérieur ou entre les clefs CK ou les indicateurs. Après le retard initial d'un multiplet de l'adresse d'emmagasinage CK 40 par rapport à l'adresse de recherche UK, l'adresse d'emmagasinage est de plus 69 45787 18 2027738 en plus eEt retard par rapport à l'adresse de recherche au fur.et,-à mesure que le traitement se poursuit puisque chaque clef CK emmagasiné est plus courte que la clef UK recherchée qu'elle remplace. Chaque clef CK est suivie par une série de multiplets indicateurs qui 5 (sauf le dernier) sont suivis immédiatement par un multiplet P commençant la clef CK suivante. Mise à part qu'elles sont, disposées en séquences, il n'y a pas d'emplacements prédéterminés pour, les clefs comprimées comme, il y en a pour les clefs non comprimées (à cause des valeurs dans les multiplets MUKL et RL). 10 Chaque couple constitué par les multiplets correspondants dans la clef non comprimée en cours (i)-et la clef non comprimée suivante (i+1) est comparé par un comparateur de multiplets 125 sur la figure 8A. Le comparateur 125 détermine l'égalité ou la différence des multiplets UK dans le registre de multiplets A1 et le registre de multiplets A2. Les multiplets en cours de 15 comparaison sont recherchés à partir de la mémoire intermédiaire 10 et envoyés au registre A1 et A2 à partir des positions de multiplets identiques dans les clefs non comprimées i et i+1. L'identité de positions de ces multiplets dans les clefs non comprimées comparées est indiquée par le compteur de multiplets UK 116 de la figure 7. 20 Les circuits de la figure BB décident la chronologie qui choisit l'état du compteur P et les multiplets A2 qui deviendront les multiplets CK. On va donner la légende pour la figure 8B qui facilitera la compréhension du fonctionnement. LEGENDE POUR LA FIGURE BB 25 Indications sur les conducteurs Fonction indiquée lorsque le conducteur est excité Transfert K - 1 Multiplet A2 égal entre P^ et P^ de UK i+1. Transfert K - 3 (transfert K de P^_1 à P^) Multiplet A2 égal à > Pi_>|* 30 Transfert P - 1 (transfert K à P^ > Pi_ Transfert contenu compteur P à mémoire 10 quand Transfert K - 2 (transfert P^ Multiplet A2 inégal à P^ 35 (transfert K à P^ Transfert P - 2 Transfert contenu compteur P au bus d'entrée mémoire 10 quand P^ Etat C (transfert P. i i-1 Balayage sur les multiplets UK après la position P^ 40 (multiplets bruit) 69 5 10 15 20 25 30 35 40 45787 2027738 C Terminé Fin de chaque balayage sur UK jusqu'à P^ du balayage des clefs UK suivant. (multiplets égaux redondants) Etat E Signal P± Etat F Multiplet A2 égal à P^_^ pour le balayage des clefs. UK en cours Etat F Premier balayage UK ou dernier balayage avec P ou dernier balayage non à la position P^ ^ avec pi > pi-r Restaurer Etat C Compte UK * P^^ ^+1 Marche Compteur P Pendant que chaque multiplet K est extrait de la clef UK i+1 Arrêt Compteur P Pendant qu'aucun multiplet K n'est extrait. Le compteur P de la figure BA est initialement remis à zéro par le cycle IP. La valeur P^ est enregistrée dans le compteur P de deux façons différentes suivant que P^ ^t-1 ou _ cette condition est indiquée par un signal "marche compteur P" provenant de la figure QB. Il provoque l'avancement du compteur P par la porte 135 à chaque impulsion T2 une fois que la valeur P^ est atteinte, tant que les multiplets UK sont égaux et le compteur P s'arrête au premier multiplet UK inégal ce qui se produit à la valeur P^. Au début d'une comparaison de clef UK, la valeur P^^ contenue dans le compteur P devient la valeur P.^ pour la comparaison suivante. Une fois que la valeur P^ est établie pendant une comparaison de clefs non comprimées, le compteur P n'est plus perturbé pendant le reste de cette comparaison, ni pendant la comparaison suivante jusqu'à ce que la première position P^ ou P^ ^ soit atteinte par le compteur de multiplets UK. Avant que la position P^-j soit atteinte pendant une comparaison de clefs non comprimées, la valeur dans le compteur UK 116 de la figure 7 est comparée à la valeur Pi_1 dans le compteur P de la figure 8A par un comparateur 132 représenté sur la figure BA. A cause de la réalisation particulière du compteur P, les valeurs P^ et P ^ ne peuvent être déterminées par le comparateur 132 seulement. La comparaison P^^ et P^_,j nécessite dans cette réalisation le circuit de la figure 8B. La condition c ^ est détectée par la porte 144a de la figure QB et elle est indiquée en enclenchant le basculeur 144b pour fournir un signal 69 45787 20 ... * 2027738 "état E". Le compteur P est chargé avec cette valeur (par l'intermédiaire des portes 134 et 136) par le compte de multiplets UK existant à l'apparition du signal "état E". Ensuite, P^ reste dans le compteur P et le comparateur 132 reste fixe pendant le reste du balayage de ce couple de clefs non compri-5 mées. La condition P^ P^ ^pendant une égalité des multiplets UK est détectée par la porte 146a et l'enclenchement du basculeur 147a de la figure 8B pour fournir un signal "état F". C'est-à-dire, il détecte lorsque l'égalité des multiplets UK se produit et que le couple suivant de multiplets est à comparer 10 pour trouver une égalité. La porte 147b signale la chronologie lorsque le compteur de multiplets UK contient la valeur P.^-1*''' L'égalité des multiplets UK se poursuit à c'est la première position de multiplet K dans une clef comprimée à plusieurs multiplets. Le dernier multiplet K et sa position Pj dans une clef comprimée à plusieurs multiplets sont indiqués par les signaux 15 K - 3 et P- 1 provenant des portes 140a et 140b sur la figure BB pour indiquer la première position de multiplets inégaux suivant la position dans la comparaison de clefs non comprimées en cours. Un basculeur 141b est enclenché par le signal K - 3 pour fournir un signal "état C" qui existe pendant que la partie restante du couple de clefs non comprimées est analysée par le compteur 20 UK de la figure 7. Les portes 140a et 140b indiquent un multiplet K à P^ Pi-1" L'incrémentation du compteur P s'arrête lorsque la porte 140b détecte la première position de multiplets UK inégaux avec un signal "transfert P-1" qui enclenche le basculeur 141b pour fournir le signal "arrfit compteur P" 25 et faire chuter 18 signal "marche compteur P". Pendant ce même cycle A2, la porte 140a -signale le transfert du multiplet A2 comme dernier multiplet K (il peut être le seul) de la clef comprimée en cours alors que la porte 140b signale le transfert du multiplet P correspondant. Le compteur P conserve la valeur P^ pendant le reste de cette comparaison de clefs non comprimées et 30 il devient P^ ^ pour la formation de la clef comprimée suivante. Le balayage des clefs non comprimées UK final se produit pendant l'état C. Le balayage se poursuit quand le compteur de multiplets UK continue à être incrémenté à l'instant T1 pendant chaque cycle A2 par l'intermédiaire de la porte ET 106 de la figure 7, même si le compteur P est fixe avec la valeur 35 P . Par suite, le compte de clefs UK n'est plus égal au compte P après la position P . Cette incrémentation par le compteur de multiplets UK se poursuit jusqu'à ce que le cycle A2 soit terminé par le comparateur 114 de la figure 7. Il fournit un signal "fin UK" à la porte ET 142 de la figure 8B, qui enclenche un basculeur 142a pour fournir un signal "C terminé" qui indique qdie 40 le balayage des clefs UK est terminé. 69 45787 21 2027738 Chaque multiplet de chaque clef non comprimée i+1 dans une comparaison est transféré au registre A2 124 de la figure 8A par l'intermédiaire de la ports 123. Cependant, seuls'les multiplets CK sélectionnés peuvent être transférés du registre A2 au champ CK dans la mémoire intermédiaire 10 par 1'inter-5 médiaire d'une porte 128b. Le circuit de la figure 8b décide quels multiplets A2 dans le registre A2 124 doivent être transférés par la porte 120b comme multiplets K pour le champ CK en cours. Une porte 128b sur la figure SA exécute ces décisions de chronologie à partir de la figure 8B, qui sont reçues ensemble par un circuit OU 130 sur la figure BA. Il conditionne sélectivement 10 une porte 128b pour transférer chaque multiplet A2 sélectionné è la mémoire intermédiaire 10 comme élément de la clef comprimée en cours. Le circuit de la figure 8C commande les adresses d'emmagasinage à la mémoire intermédiaire 10, sous commande d'un compteur d'adresses d'emmagasinage 156, qui est initialement chargé par la première adresse de multiplet K Cdépla-15 cernent 4) pour la première clef comprimée. Ce compteur est incrémenté quand c'est nécessaire à l'adresse de déplacement pour les multiplets respectifs à emmagasiner. Un circuit OU 159 commande le décalage des adresses pour les multiplets K et R. Les signaux de transfert K-1, K-2 et K-3 provenant de la figure 8B sont appliqués à un circuit OU 159 ainsi que chaque signal de cycle 20 R par l'intermédiaire de la porte ET 160 pour faire avancer le compteur 156 par l'intermédiaire du circuit OU 158 et pour enclencher le basculeur de commande 161. Le basculeur 161 tient compte des différentes chronologies des signaux provenant du circuit OU 159 qui se produisent avant T6 pendant un cycle K ou R lorsqu'une porte ET 162 est conditionnée pour actionner la porte de 25 sortie 157 afin de fournir une adresse au bus d'adresses de la mémoire intermédiaire 16 par l'intermédiaire du circuit OU 153. Le basculeur 161 est restauré par l'impulsion T0 suivante. La valeur est transférée à l'emplacement P^ adressée dans la mémoire intermédiaire 10 à partir du compteur P par l'intermédiaire de la porte P^ 00 129, du circuit OU 131 et du bus 13 de la figure 8A. Les instants du transfert sont déterminés par le circuit OU 133b qui reçoit les signaux transfert P-1 et transfert P-2 provenant de la figure 8B ou un signal spécial fin d'enregistrement provenant du circuit ET 133a. Le registre 124 de la figure 8A peut traiter les multiplets R ainsi que 35 les multiplets A2 sans contradiction puisqu'ils se produisent à des instants différents comme on l'a expliqué précédemment pour les cycles d'horloge A2 et R de la figure 6. Les cycles R de la porte 123 de la figure 8A transfèrent les multiplets indicateurs séquentiellement au registre de multiplets 124. De même la porte 40 128b peut commander la sélection des multiplets A2 ou R sans contradiction 69 45787 22 2027738 puisqu'ils se produisent à des instants différents. Les multiplets indicateurs sont transférés séquentiellement à chaque cycle Rà T5 sur le circuit ET 127 qui excite la porte 128b. Les multiplets indicateurs sont emmagasinés temporairement par le registre 124 pour qu'ils puissent être réemmagasinés 5 dans la mémoire intermédiaire 10 à une adresse différente-de celle où ils étaient recherchés comme indiqué précédemment par le compteur d'adresses de recherche 110 sur la figure 7 et le compteur d'adresses d'emmagasinage 156 sur la figure 8C. Ces deux compteurs sont avancés de façon synchrone par chaque cycle R. Ceci est réalisé par une porte ET 100 sur la figuré 7 et par un circuit OU 10 159,-un circuit ET 160 et un circuit OU 158 sur la figure 8C. Le dernier multiplet R pendant un transfert d'indicateur est signalé par un comparateur 189 sur la figure 8D lorsque la valeur RL est atteinte pour les cycles R. L'avancement normal du compteur d'adresses d'emmagasinage 156 se produit de la même façon pendant le dernier cycle R pour faire avancer le 15 compteur d'adresses d'Binmagasinage à l'adresse du multiplet P de la clef comprimée suivante. Cette adresse est emmagasinée dans un registre 150 "adresse P suivante" puisque la détection de la valeur P^ suivante par le signal transfert P-1 peut se produire après l'emmagasinage d'un ou plusieurs multiplets K. L'adresse 20 P^ est emmagasinée dans le registre 150 pendant le dernier multiplet R en faisant avancer le compteur d'adresses d'emmagasinage 156 par un signal Réserve Fin R en vu du multiplet P suivant pour la nouvelle clef comprimée. Pour commander cette valeur P et la première opération d'adressage du multiplet K sur la figure 8C, un signal est engendré pendant le dernier mul-25 tiplet R de chaque indicateur. Le signal "Réserve Fin R" place l'adresse d'emmagasinage. P^^ suivante par l'intermédiaire d'une porte 152 dans le registre 150 "adresse P w suivante" à partir d'où l'adresse P^ suivante est disponible pendant que le compteur d'adresses d'emmagasinage est avancé à l'adresse supérieure suivante qui est la valeur finalement contenue dans le registre 30 150. Le signal "égalité sur RL" pour chaque indicateur fait passer les cycles d'horloge des cycles R aux cycles A1 et A2 pour amorcer une comparaison sur le couple suivant de clefs non comprimées de la manière décrite précédemment, ce qui"donne la formation de la clef comprimée suivante. 35 Cette opération est reprise pour chaque couple de clefs non comprimées ultérieur jusqu'à ce que tous les couples de clefs non comprimées dans la mémoire 10 aient été traités. La fin de l'enregistrement des clefs UK dans la mémoire intermédiaire 10 est détectée lorsque le premier cycle A2 (et le dernier) transfère le mul-40 tiplet "fin d'enregistrement" au registre de multiplets A2. Chaque multiplet 69 45787 23 2027738 A2 est détecté par un décodeur "fin "de multiplet" 180 sur la figure 8D et un circuit ET 180a qui enclenche un basculeur 181 pour indiquer un signal de fin d'enregistrement représenté sur la figure B. La dernière clef comprimée est engendrée en réponse au signal de fin d' 5 enregistrement. Cette dernière clef comprimée a une valeur nulle, aucun multiplet K, et le champ indicateur associé à la dernière clef non comprimée. Le compteur P est remis à zéro par un signal de fin d'enregistrement provenant du basculeur 181 de la figure 8D, et le compteur de multiplets UK est remis à zéro par les cycles R antérieurs. 10 Le cycle A2 final incrémente de un le compteur UK par l'intermédiaire de la porte 106 de la figure 7, ce qui rend le compteur UK supérieur au compte P. Cette condition empêche le circuit de la figure 8B de fonctionner. Le compteur P reste à zéro car aucun signal "marche compteur P" n'est amené à la porte 135 de la figure 8A. L'adresse P^ emmagasinée dans le registre 150 de la figure 15 8C est extraite pendant le dernier cycle A2 par le signal de fin d'enregistrement appliqué au circuit ET 151c par l'intermédiaire du circuit OU 151a et de la bascule 151d. La valeur P^ nulle dans le compteur P est transférée par l'intermédiaire de la porte P^ 129 au bus d'entrée 13 de la mémoire intermédiaire au moyen du circuit ET 133a qui est excité par le dernier cycle A2 et 20 le signal de fin d'enregistrement à l'instant T6 par l'intermédiaire du circuit OU 133b. Sur la figure 6, le signal de fin d'enregistrement remplace le signal de fin de UK par l'intermédiaire du circuit OU 33b pour amorcer la succession des cycles R (et terminer la succession des cycles A1 et A2), ce qui amorce 25 le transfert du champ R de la manière précédemment expliquée. A la fin du transfert du dernier champ indicateur, la succession des cycles d'horloge est arrêtée par un signal de restauration générale provenant du monostable 185 qui est actionné par une porte ET 183 sur la figure 8D, cette porte étant conditionnée par le signal "égalité sur RL" pendant l'existence d'un 30 signal de fin d'enregistrement. 4. Sortie - Description particulière Le fonctionnement détaillé de la réalisation en mode formation décrite ici est représenté par la séquence suivante: I Le signal de départ sur la figure 6 provoque les cycles de repère 35 et met aux conditions initiales le système avant de rechercher un premier multiplet UK en: a. chargeant le registre "adresse P suivante" à l'adresse du "multiplet IP" (multiplet =3). b. chargeant le compteur d'"adresses d'emmagasinage" en vue de la 40 première adresse K (multiplet = 3) 69 45787 24 2027738 c, en mettant le compteur P et le compteur UK. à zéro avant que la première clef UK soit recherchée. d. en restaurant tous Ibs basculeurs de la figures 8B avec les seuls signaux actifs qui sont le signal "état F" et "marche compteur P". 5 Commence la succesion des cycles d'horloge A1-A2 sur la figure 6. II. A l'instant T1 le compteur de multiplets UK est incrémenté de un sur la figure 7. A l'instant T2, le compteur P est incrémenté de un sur la figure BA. •10 A l'instant T3, si A1»A2 on passe à III, mais si A1 / A2 on passe à IV. III. A l'instant T3, on obtient le signal K-1 sur la figure 8B puisque le contenu du compteur UK est égal au contenu du compteur P et on passe à II. IV. A l'instant. T3, on obtient le signal transfert K-3 sur la figure 15 8B, puisque le contenu du compteur UK est égal au contenu du compteur P. Mise à l'état haut du signal "état C" sur la figure BB. A l'instant T4, on obtient le signal transfert P-1 sur la figure BB. Mise en service le compteur "arrêt P" et mise hors service du compteur "marche P" sur la figure BB, et on passe à V. 20 V. On fait avancer le compteur de multiplets UK de un sur. la figure 7 [le compteur P est maintenant inhibé avec P ? par suite les contenus des compteurs UK et P sont différents.) Tant que les contenus des compteurs UK et MUKL sont différents (c'est-à-dire qu'il n'y a pas de signal "fin UK"}, on passe à V. Lorsque les 25 contenus des compteurs UK et MUKL sont égaux (c'est-à-diré" qu'il y a un signal "fin UK") on passe à VI. VI. Met à l'état haut le signal "C terminé" sur la figure BB. Met à l'état bas le signal "état C" sur la figure BB. Commence la succession des cycles R sur la figure B pour transférer 30 les multiplets indicateurs de la clef UK i à la clef CK i. Fin du transfert des multiplets R indiquée par le signal "avance fin R" sur la figure BD. Passe à VII VII. Amorce la succesion des cycles d'horloge A1 et A2 sur la figure 35 6 pour le couple de clefs UK suivant (valeur P dans le compteur P maintenant réattribuée comme valeur A l'instant T1, le compteur de multiplets UK est incrémenté de un. Si le premier multiplet A2 est décodé comme fin d'enregistrement 40 sur la figure BD, on passe à XIII. 69 45787 25 2027738 Si le premier multiplet A2 n'indique pas une fins d'enregistrement on passe à VIII. " VIII. Si le contenu du compteur de multiplets UK est inférieur ai* contenu du compteur P, et que A1 A1 sur la figure 8B, on passe à IXV autrement 5 on passe à X. IX A l'instant T3, on obtient le signal "état E" de la figure 6B. A l'instant T4, le contenu du compteur de multiplets UK est transféré au compteur P sur la figure 8A pour obtenir la nouvelle valeur P.. i A l'instant T5, le signal transfert K-2 de la figure 8B transfère 10 le multiplet A2 de la figure 8A comme multiplet K, au bus d'entrée de la mémoire intermédiaire. Sur la figure 8B, les signaux "état C et "arrêt compteur P" sont mis à l'état haut. Le signal "C terminé" est mis au niveau bas. 15 A l'instant T6, le signal transfère P-2 de la figure 8B, transfère la valeur dans le compteur P de la figure 8A au bus d'entrée de la mémoire intermédiaire. Le signal "arrêt compteur P" de la figure 8B est mis a l'état haut. □n passe à V. 20 X. Si les contenus des compteurs de multiplets UK et P sont égaux et que A1 est égal à A2 Cporte 146a) on passe à XI autrement on passe à XII. XI. A l'instant T2, le signal "état F" est mis à l'état haut sur la figure 8B, A l'instant 17, le signal "restauration état C" est engendré. 25 La bascule "état C" est restaurée. La bascule "C terminé" est restaurée. Le signal "marche compteur P" est mis à l'état haut. □n passe à II XII. Si les deux conditions de VIII et X'ne sont pas vérifiées, on passe 30 à VIII. XIII. Restaure à zéro le compteur P de la figure 8A. (Il existe des conditions qui font que les signaux de la figure 8B restent à l'état initial). Commence les cycles R de la figure 6, et transfère la dernier champ 35 indicateur. Restauration générale à partir de la figure 60 à la fin du transfert du multiplet R pour terminer l'opération. D. SYSTEME FONCTIONNANT EN MODE DE RECHERCHE Le système fonctionnant en mode de recherche a été décrit précédemment. 40 On conséquence, on va maintenant décrire une parmi les nombreuses réalisations 69 45787 26 2027738 possibles de cette invention. - 1. Circuits de mode de recherche • • Le signal d'entrée provenant du bus de sortie de données et allant à la figure 12 est un index comprimé qui peut être fourni à partir d'une parmi 5 différentes sources. On prendra deux sources différentes, pour cette réalisation. Une de ces sources est constituée par un dispositif à accès aléatoire telle qu'une mémoire à noyaux 10 et l'autre est un dispositif entrée/sortie (I/O) du type série tel qu'un disque, un tambour ou une bande. La figure 10 représente un circuit pour connecter ces différents dispo-10 sitifs comme un dispositif entrée/sortie ou une mémoire intermédiaire. UN basculeur de sélection d'entrée 305 est actionné par l'exécution d'un type classique d'instructions de sélection dans un ordinateur, telle qu'une instruction de sélection I/O. L'instruction peut avoir deux modes qui sont.un mode I/O et un mode mémoire intermédiaire. Le mode I/O enclenche un basculeur de sé-15 lection 301 sur la figure 10 et le mode mémoire intermédiaire restaure ce basculeur. Lorsqu'il est enclenché, il connecte le dispositif I/O 300 au bus de sortie de données par l'intermédiaire d'une porte 302 et d'un circuit OU 304. Lorsqu'il est restauré, le basculeur 301 connecte le bus de sortie de la mémoire intermédiaire 14 (à partir de la mémoire intermédiaire 10 de la figure 20 2B) au bus de sortie de données par l'intermédiaire d'une porte 303 et d'un circuit OU 304. Le mode de recherche utilise le circuit de commande d'horloge représenté sur les figures 9A et B qui fournit les mêmes cycles de repère que la commande d'horloge du mode de formation de la figure 6. De même, sur la figure 9A, 25 le cycle MUKL est utilisé principalement pour la restauration initiale mais le multiplet MUKL n'est pas transféré dans cette réalisation fonctionnant en mode de recherche. La figure 4B représente la chronologie pour le circuit de commande d'horloge représenté sur les figures 9A et B. Pendant la durée du cyle LVL et T1, le multiplet d'entrée suivant LVL est transféré au registre 30 LVL 268 sur la figure 12. Les sorties du registre LVL définissent si 1'enregistrement des index comprimés traités a le format de niveau haut ou de niveau bas. Pendant le cycle RL et à l'instant TL le multiplet d'entrée suivant est transféré au registre RL. Le registre RL définit la longueur de chaque champ 35 indicateur suivant une clef CK. Un cycle P suit le cycle RL. A l'instant T0 pendant chaque cycle P, un registre P^ 308 sur la figure 13 est remis à la condition initiale nulle. A l'instant T1 pendant le cycle P, le multiplet P d'une clef CK est envoyé depuis le dispositif d'entrée à un registre -P 308 sur la figure 13 à l'instant T1 40 par l'intermédiaire de la porte 307. Le registre P^_^ est initialement remis 69 45787 27 2027738 à +1- par le cycle MUKL. Les sorties-du registre 308 et du compteur P^ ^ 314 sont amenées au comparateur 31B pour comparer la valeur P {initialement un ou plus! à P 1 (initialement un ) » Plus tard si P. est inférieur à P, , i" i i-1 la bascule 319 est enclenchée. 5 Le circuit de commande d'horloge de la figure 9B fournit un ou plusieurs cycles K suivant chaque cycle P unique. Pendant chaque cycle K, un multiplet K (qui est le multiplet suivant provenant du dispositif d'entrée) est transféré à l'instant T1 dans le registre K 256 de la figure 12. Le registre K est toujours remis à zéro pendant chaque cycle K à l'instant TO par l'intermédi-10 aire de la porte ET 257 et il est chargé au temps T1 par l'intermédiaire de la porte 254 avec la valeur du multiplet K reçu. Un compteur d'égalité 301 (figure 13) permet d'améliorer le fonctionnement en permettant à chaque multiplet de l'argument de recherche de n'être examiné qu'une fois par séquence d'index comprimé. Ceci permet aux multiplets égaux 15 d'ordre supérieur des clefs non comprimées comparées, d'être abandonnés pendant le mode de formation. Si pendant le cycle K, le contenu du compteur P^_-j est égal au contenu du compteur d'égalité 301 sur la figure 13, un multiplet de l'argument de recherche (A) est transféré dans le registre d'argument de recherche 252 sur 20 la figure 12. Si le multiplet de l'argument de recherche (A) est supérieur au multiplet K (dans le registre K) le multiplet A reste dans le registre d'argument de recherche alors que le premier multiplet K de la clef comprimée suivante est transféré dans le registre K pour une comparaison suivante. Si le multiplet A est inférieur au multiplet K, la recherche se termine et les mul-25 tiplets R associés à cette clef CK sont recherchés et placés dans le registre "indicateur trouvé"-sur la figure 2B dans lequel est placé l'indicateur avec la première clef comprimée supérieure (en supposant un classement dans l'ordre croissant pour les clefs non comprimées initiales). La condition initiale du compteur d'égalité 301 de la figure 13 est la 30 valeur un, établie pendant le cycle MUKL à l'instant T0 par l'intermédiaire de la porte ET 302. Ainsi, la première comparaison entre les valeurs dans le compteur P. ^ 314 et le compteur d'égalité 301 seront égales et cette égalité est indiquée par un signal de sortie provenant d'un comparateur 303. Chaque égalité entre les contenus des compteurs 314 et 301 enclenche une bascule d'é-35 galité 306 pendant un cycle K au temps T2. La bascule 306 est restaurée un peu après au temps T4, de sorte que l'impulsion d'égalité de l'argument de recherche est signalée pendant T2-T4. Si le comparateur 253 sur la figure 12 signale que K est égal à K et que la bascule d'égalité 306 est enclenchés, le compteur d'égalité 301 est incré-40 menté de un par l'impulsion d'égalité par l'intermédiaire de la porte ET 326 69 4S787 28 2027738 et du circuit OU 324. Pendant le cycle K suivant, un nouveau multiplets est introduit dans le registre K 256 de la figure 12 à partir du bus de sortie de données. Un test est de nouveau réalisé par le comparateur 303 de la figure 13 pour voir 5 si 1b contenu du compteur 3.1-4 est égal au contenu du compteur d'égalité 301. Si ces contenus sont égaux, le multiplet suivant de l'argument de recherche est recherché et une autre comparaison est réalisée. Le compteur d'égalité 301 n'est pas chargé si le multiplet K. est supérieur au multiplet A, mais à sa place une bascule "A haut" 328 est enclenchée par l'intermédiaire de la 1q porte ET 327 qui conditionne une porte ET 329, ce qui termine l'opération de recherche pour cet argument de recherche après avoir retrouvé l'indicateur avec la clef comprimée en cours en enclenchant une bascule "recherche terminée" 331. Sur la figure 13, pendant chaque cycle K, au temps T3, le compteur P^_^ 15 314 est incrémenté de un. Lorsque P^ est égal à P ^ pendant un cycle K au temps TO, la bascule cycle R suivant est enclenchée sur la figure 9B. Le cycle suivant sera un cycle R. Pendant les cycles R les multiplets indicateurs provenant du dispositif d'entrée sont transférés au registre 256 de la figure 12, par la porte 254 qui est conditionnée par les cycles R par l'intermédiaire 20 du circuit OU 255. Les multiplets indicateurs viennent du bus d'entrée de la mémoire intermédiaire 13 par l'intermédiaire d'une porte 265 lorsqu'elle est conditionnée par un circuit ET 260 en réponse à un signal de sélection de R. Une comparaison est réalisée entre le contenu du registre RL 259 et le contenu du compteur R 264 pour déterminer lorsqu'ils sont égaux. Lorsqu'ils 25 sont égaux, la fin de l'indicateur est indiquée par un signal R = RL. Ensuite, la bascule' cycle P suivant est enclenchée et le cycle suivant sur la figure 9B est un cycle P. Pendant le cycle P, le registre P^ de la figure 13 est remis à zéro au temps T0 et il est chargé au temps T1 par la porte 307 pour contenir le nouveau 30 multiplet P^ existant alors sur le bus de sortie de données à partir du dispositif d'entrée. Un cycle K suit chaque cycle P et provoque le chargement dans le registre K au temps T1, du multiplet suivant provenant du dispositif d'entrée. Pendant chaque cycle P, un test est réalisé par un comparateur 316 pour 35 déterminer si la valeur dans le registre P est inférieure à la valeur dans le registre P^» Si PA-est inférieur à P^ et que Pj[ n'est pas égal à zéro (comme déterminé par la porte ET 317) le contenu du registre P^ est placé par l'intermédiaire de la porte 313 dans le compteur P^_,| pour obtenir une nouvelle valeur représentant P^ à ce moment. 40 Cependant, si le comparateur 316 indique que P est supérieur à Pi-1' 45787 29 2027738 la valeur Pi restant de la clef comprimée antérieure devient la Valeur Çt est directement utilisée. Dans ce cas,-pendant chaque cycle K suivant immédiatement, le compteur P^_^ est incrémenté de un par l'intermédiaire du circuit ET 321 pour représenter le multiplet K suivant et la valeur du compteur P^_«l incrémentée est comparée à la valeur du registre P^ au moyen du comparateur 31B. La valeur du compteur incrémentée est comparée à la valeur du compteur d'égalité au moyen du comparateur 303. Il est important de comprendre qu 'une valeur P exacte est seulement représentée dans le compteur P^^ 314 avant qu'elle soit incrémentée pendant une nouvelle opération CK. Une fois qu'elle est incrémentée, la valeur dans le compteur Pi_1 est supérieure à la valeur Pi_^ en cours. Chaque valeur incrémentée dans le compteur P^_^ représente la position réelle de la clef non comprimée pour le multiplet K en cours dans la clef UK représentée par la clef comprimée CK en cours. Seulement lorsqu'on détermine que la valeur incrémentée dans le compteur P^_-j est égale à la valeur dans le compteur d'égalité, le multiplet suivant de l'argument de recherche peut être obtenu à partir de la mémoire intermédiaire 10 et chargé dans le registre d'argument 252. Le compteur d'égalité est incrémenté de un par un signal "ajouter plus un au compteur d'égalité" provenant du circuit ET 326 qui est conditionné au temps T3 pendant un cycle K chaque fois que le multiplet K en cours est égal au multiplet A de l'argument en cours et qu'un signal "égalité argument de recherche" est reçu à partir du basculeur 306. Le signal "égalité argument de recherche" est fourni entre T2-T4 après un signal "compte argument de recherche = P provenant du comparateur 303 au temps T2 pendant un cycle K. A l'apparition de l'incrémentation du compteur d'égalité, le multiplet de l'argument suivant n'est pas transféré dans le registre d'arguments de recherche 252 jusqu'au cycle K suivant. Après le chargement du registre d'argument de recherche, les basculeurs 242 et 243 sont enclenchés pour inhiber l'accès à l'argument de recherche suivant jusqu'au moment où' un autre signal "ajouté plus un au compteur d'égalité" est engendré. Le même multiplet de l'argument de recherche est utilisé pour balayer séquentiellement les clefs comprimées, jusqu'à ce que l'argument de recherche soit égal au multiplet K situé à la même position relative dans la clef non comprimée (représentée par la valeur incrémentée dans le compteur P^_^ 314) que la position relative dans l'argument de recherche du multiplet de l'argument en cours (représentée par la valeur dans le compteur d'égalité 301). La recherche est terminée pendant le balayage des clefs comprimées dans trois cas: (1) un multiplet de l'argument en cours A est supérieur à un multiplet K dans tout l'index de clefs comprimées (c'est-à-dire, le multiplet P 69 45787 30 2027738 est décodé pour obtenir un zéro par le détecteur de "zéro partout" 309, ou (2) est inférieur à la valeur dans le compteur d'égalité, actuel, ou (3) la valeur dans le compteur P^_^ est égale à la valeur dans le compteur d'égalité et le multiplet A est inférieur à K. La troisième condition est indiquée par 5 la sortie du circuit ET 327 qui enclenche un basculeur 328. La seconde condition est indiquée par un circuit ET 315 sur la figure 13, qui est conditionnée par un signal provenant du comparateur 303 qui indique que Pj^ est inférieur à la valeur en cours dans le compteur d'égalité au temps T2 du cycle K. La première condition est évidente lorsque l'argument de recherche est supérieur 10 à une clef quelconque et elle est provoquée par un signal de sortie provenant du circuit ET 332 enclenchant le basculeur 328. Le basculeur 328 reste enclenché pour obtenir un signal de sélection R pendant que l'indicateur en cours suivant la dernière clef comprimée est recherché et emmagasiné dans le champ du registre "indicateur trouvé" dans la 15 mémoire intermédiaire 10 de la figure 2B. La fin du transfert d'indicateur est ainsi indiquée par un signal R ■ RL allant à un circuit ET 334 qui enclenche un basculeur "recherche terminée" 331 par l'intermédiaire d'une porte ET 329 qui est conditionnée par le basculeur 328 ou le basculeur 333. Le basculeur 331 conditionne un circuit ET 336 pour 20 engendrer une impulsion de restauration générale à l'instant T6 suivant qui restaure les basculeurs 328 et 333, et les circuits d'horloge sur les figures 9A et B et terminent l'opération en mode de recherche. Si l'argument n'est pas trouvé dans l'index comprimé une valeur P nulle est finalement détectée par le détecteur 309 de la figure 13. Il en résulte 25 que la porte ET 332 est conditionnée pendant le dernier cycle P et elle enclenche le basculeur 333 qui fournit alors un signal "saut cycle K" au circuit de commande d'horloge de la figure 9B pour le forcer à commencer les cycles R pour mettre en place le dernier indicateur dans le registre "indicateur trouvé" de la figure 2B. Le basculeur 333 fournit aussi un signal de sortie par 30 l'intermédiaire du circuit OU 333 à la porte ET 329 afin d'enclencher le basculeur "recherche terminée" 331 lorsque le dernier indicateur est enregistré. Par suite, le signal "recherche terminée" sur la figure 13 indique que tout l'indicateur a été emmagasiné dans le registre R désigné pour l'indicateur trouvé. L'opération de recherche est ainsi terminée, 35 Le dernier indicateur peut être utilisé pour rechercher la dernière clef non comprimée initiale afin de vérifier que l'argument de recherche fait partie de la liste initiale des clefs non comprimées. Si non, l'index peut être mis à jour en insérant de nouvelles clefs non comprimées et en régénérant l'in^ dex de clefs comprimées. 40 Le circuit de la figure 11 détermine l'emplacement dans la mémoire inter- 69 45787 31 2027738 médiaire 10 pour les multiplets "indicateurs trouvés" qui sont transférés par le registre 256 sur la figure 12 au bus d'entrée de la rnémoire intermédiaire lorsque le basculeur 328 est enclenché sur la figure 13. L'adressage du registre "indicateurs trouvés" prédéterminé sur la figure 2B est réalisé par 5 le compteur 156 de la figure 11. Le signal cycle R suivant provenant de la figure 9B charge le compteur d'adresses 158 avec l'adresse du.multiplet de départ du registre "indicateur trouvé" dans la mémoire intermédiaire 10 qui peut être à un emplacement prédéterminé disponible dans la mémoire intermédiaire 10. (Le compteur d'adresses peut être le même que le compteur d'adres-10 ses d'emmagasinage 156 utilisé dans le mode de formation). Un circuit ET 314 incrémente le compteur 156 au temps T6 pendant chaque cycle R pendant que le basculeur 328 est enclenché pour engendrer chaque multiplet R dans le champ du registre "indicateur trouvé". L'autre l'entrée à l'additionneur A contient des zéros partout puisque la porte 315 n'est pas conditionnée par les cycles 15 K. Le compteur d'adresses de recherche 110 peut aussi être le même que celui utilisé pendant le mode de formation. Le compteur 110 est remis à zéro dans le mode de recherche par le cycle MUKL et il est ensuite incrémenté de un au temps T7 par chaque cycle sucessif de l'horloge de la figure 3. L'adresse de recher-20 che est extraite du compteur 110 à chaque temps zéro et envoyée au bus d'adresses de la mémoire intermédiaire 16 par l'intermédiaire de la porte ET 312a et de la porte OU 312b. Par suite, le compteur d'adresses de recherche balaie séquentiellement un enregistrement d'index comprimés. Les multiplets de l'argument de recherche sont aussi adressés par le comp-25 teur 156, qui pendant chaque cycle P est chargé au début d'une adresse prédéterminée dans le registre d'arguments de recherche dans la mémoire intermédiaire 10 de la figure 2B. La position du multiplet en cours dans l'argument de recherche nécessaire pour une comparaison est obtenue à partir du compteur d'égalité 301 de la figure 13. Elle est amenée à une porte 315 sur la figure 11 30 qui l'envoie pendant chaque cycle K à l'additionneur A qui ajoute la valeur du compteur d'égalité à l'adresse initiale de l'argument dans le compteur d'adresses 156. La sortie de l'additionneur A est amenée par l'intermédiaire d'une porte ET 313 et une porte OU 312b au temps T7 au bus d'adresses de la mémoire intermédiaire 16 pour rechercher le multiplet de l'argument nécessaire pour 35 faire une comparaison avec le multiplet K en cours. Une recherche de l'argument de recherche suivant dans le même index comprimé peut être commencée. 2. Commande d'horloge pour le mode de recherche Les figures 9A et B représentent les commandes de l'horloge de re-40 cherche fournissant les six types de cycles représentés sur la figure 4B 69 45787 32 2027738 utilisés pour effectuer une recherche dans un index comprimé. Les commandes d'horloge de recherche pour les multiplets de repères initiaux sur la figure 9A sont analogue aux commandes pour les multiplets de repère des commandes d'horloge de formation représentées sur la figure 6. 5 Une séquence globale est fournie par les commandes d'horloge de recherche lorsqu'on effectue une recherche dans un seul bloc d'index comprimés se terminant avec une clef comprimée ayant un multiplet P nul. Les cycles de multiplets de recherche (MUKL, LVL et RL) se produisent une fois par recherche d'enregistrement pour un argument de recherche. Le cycle P se produit une fois 10 pendant le multiplet P commençant chaque clef CK. Un cycle K se produit une fois par multiplet K dans une clef CK. Un cycle R se produit une fois par mut-liplet indicateur associé à une clef CK. Le fonctionnement des commandes d'horloge est amorcé par un signal de départ sur le conducteur 205 de la figure 9A. Ce signal est engendré de la 15 même manière que précédemment pour le signal de départ sur le conducteur 45 de la figure B pour lequel un commutateur de départ 210, ou de préférence une instruction de départ est nécessaire pour faire la distinction entre le mode de recherche pour enclencher le basculeur de mode 20 de la figure 3 et pour actionner le monostable 27 afin d'engendrer le signal de départ de la figure 20 9A, Les basculeurs et les opérations pendant ces trois cycles (MUKL, LVL, et RL) sur la figure 9A sont identiques aux circuits identifiés de la même façon sur la figure 6 et précédemment décrits pour le mode de formation. Ensuite, les circuits de commande de l'horloge de recherche diffèrent 25 des commandes de l'horloge de formation. Ceci est principalement du à la longueur variable des clefs comprimées dans le mode de recherche, ce qui est opposé à la longueur fixe des clefs non comprimées dans le mode de formation. Les conditions de longueur variable sont traitées sur la figure 9B par une bascule "cycle suivant" pour signaler en avance lorsque le type suivant de 30 cycle est à sélectionner. Ainsi, une bascule "cycle P suivant" 213 est enclenchée par une porte 212 au temps T1 pendant le cycle de repère RL puisqu'un cycle P doit suivre le cycle RL. Un cycle P suit aussi le dernier cycle P de chaque balayage d'indicateurs et ceci est indiqué par un signal "RL égal" au circuit ET 218 qui enclenche la bascule 213 au temps T6 pendant le cycle RL. 35 Lorsqu'elle est enclenchée la bascule "cycle Psuivant" 213 conditionne la porte 214 qui enclenche alors le basculeur "cyle P" au temps T0 suivant. Par suite, le cycle P commence au temps T0 suivant et la bascule "cycle P suivant" est restaurée à l'impulsion T1 suivante. La bascule "cycle K suivant" 229 est enclenchée par la porte 228 au temps 40 T6 pendant le cycle P lorsque P n'est pas nul (c'est-à-dire, n'est pas la 69 45787 33 2027738 dernière clef comprimée). La porte 231 est ainsi conditionnée pour transmettre l'impulsion TO suivante qui enclenche la bascule "cycle K" pour commencer un cycle K. Le premier cycle K restaure la bascule "cycle P" par I"intermédiaire du circuit OU 21B. - - 5 La bascule "cycle K" reste enclenchée pendant le nombre ds multiplets K (un ou plus) dans la clef CK en cours et ainsi les cycles K sent réalisés séquentiellement jusqu'à ce qu'un signal P^P^ ^ provenant du comparateur 31B sur la figure 13 indique que le contenu du compteur P 314 est devenu égal à la valeur P_^ actuellement dans le registre 308. 10 Le signal Pi"Pi_^ allant au circuit ET 221 provoque l'enclenchement de la bascule "cycle R suivant" 222 pendant chaque dernier mutlipletK dans un format d'enregistrement de bas niveau. Au temps T1 suivant, la bascule "cycle K suivant" est restaurée et la bascule "cycle R" est enclenchée pour commencer une séquence de RL cycles R. Le premier cycle R restaure la bascule "cycle 15 K" par l'intermédiaire d'un circuit OU 232. Les cycles R se poursuivent jusqu'à ce que la valeur R soit égale à la valeur RL dans le registre 259 de la figure 12 ce qui est signalé par le signal de sortie RL CT provenant du comparateur 261 sur la figure 12 et allant à la porte 218 sur la figure 9B. Ceci enclenchB le basculeur "cycle P suivant" au temps T6 et l'opération est reprise 20 pour chaque clef CK suivante pendant une opération de bas niveau jusqu'à ce qu'un multiplet P nul soit détecté ce qui indique la fin du groupe CK. Il en résulte qu'un signal "saut cycle K" est engendré à partir du basculeur 333 de la figure 13 qui enclenche la bascule "cycle R suivant" 222 sur la figure 9B pour provoquer les cycles R suivants et de ce fait sauter les cycles K pour 25 la dernière clef CK. Ceci termine l'opération des commandes d'horloge dans le mode d'index comprimé de bas niveau. Les opérations pour le mode de haut niveau sont analogues sauf qu'une seconde série des cycles P et K suit chaque première série de cycles P et K avant que les cycles R soient engendrés comme représentés par la séquence de 30 la figure 5B. Ceci est commandé par un basculeur binaire 211 qui est initialement restauré et mis à l'état opposé par chaque cycle P suivant., Par suite après les clefs comprimées de numéros impairs, 1er basculeur binaire 211 conditionne un circuit ET 209 pour enclencher le basculeur "cycle P suivant" 213 à la fin du dernier cycle K de la dernière clef CK,, ce qui fait 35 qu'un cycle P (au lieu d'un cycle R) suit chaque clef CK de; numéro impair. Les clefs comprimées de numéros pairs provenant du basculeur 211 conditionnent le circuit ET 221 par l'intermédiaire du circuit QU 219 pour enclencher la bascule "cycle R suivant". Pour éviter une ambuiguité dans la recherche, le multiplet d'ordre le 40 plus bas de l'argument de recherche sera suivi par un multiplet spécial qui 69 45787 34 2027738 est aussi faible que le plus petit multiplet L possible dans l'index. Le caractère d'ordre le plus bas dans la séquence de classement utilisée peut être utilisé comme multiplet spécial. Ainsi, si tous les multiplets de l'argument de recherche donnent une égalité pendant une recherche, ce multiplet spécial 5 donnera une condition A inférieure à K. pour le multiplet K. suivant pour terminer la recherche à la clef comprimée en cours avec la lecture de son indicateur pour indiquer le point de sortie pour cet argument de recherche. Bien que l'on ait décrit dans, ce qui précède et représenté sur le dessin, les caractéristiques essentielles de l'invention appliquées à un mode de réa-10 lisation préféré de celle-ci, il est évident que l'homme de l'art peut y apporter toutes modifications de forme ou de détail qu'il juge utiles, sans pour autant sortir du cadre de ladite invention. 69 45787 35 2027738 REVENDICATIONS 1.- Procédé pour engendrer à partir d'un ensemble de groupes de signaux enregistrés représentant des clefs destinées à la recherche de blocs d'information (groupes qui seront ap-5 pelés "clefs non comprimées" ou éventuellement "clefs"J, chacune des clefs non comprimées étant composée d'un ou plusieurs multiplets rangés suivant un certain ordre, la position occupée par le premier multiplet étant dite "position d'ordre le plus élevé" et les positions suivantes se succédant, par définition en ordre décroissant, un ordre de classement ayant été préalablement défini 10 pour l'ensemble des multiplets susceptibles de composer des clefs, cet ordre permettant de définir un ordre de classement pour les clefs, la position relative de deux clefs dans ce classement étant déterminée par celle des multiplets d'ordre le plus élevé, ou à défaut par celle des multiplets suivants et ainsi de suite, 15 un autre ensemble de groupes de signaux [groupes qui seront appelés "clefs comprimées") chaque clef comprimée correspondant à une clef non comprimée et une seule caractérisé par les opérations suivantes: a) les clefs sont lues par paires successives, chaque paire comprenant 20 deux clefs consécutives dans l'ordre de classement défini ci-dessus, la première paire étant constituée,par les deux premières clefs de ce classement et la deuxième clef de chaque paire autre que la dernière constituant la première clef de la paire suivante, b) les multiplets occupant des positions correspondantes dans les deux 25 clefs sont comparés, les comparaisons étant effectuées successivement par ordres de position décroissants, à partir de la position d'ordre le plus élevé jusqu'à ce qu'une différence soit détectée c) les comparaisons sont comptées d) le résultat du compte est utilisé comme élément de la clef compri-30 mée correspondant à une des clefs non comprimées de la paire pour laquelle les comparaisons ont été effectuées 2.- Dispositif pour engendrer, à partir d'un ensemble de clefs non comprimées tel que défini dans la revendication 1, et pouvant être ordonné suivant le système défini dans cette revendication, un ensemble de clefs comprimées 35 tel que défini dans cette revendication caractérisé par des moyens permettant d'effectuer les opérations suivantes : - accès à une paire de multiplets occupant des poàitions de mime ordre 69 45787 36 2027738 dans une première clef non comprimée et dans la clef immédiatement suivante -comparaison des deux multiplets occupant les positions d'ordre le plus élevé dans les deux clefs de la paire, puis des multiplets occupant les posi-5 tions immédiatement suivantes, et poursuite des comparaisons jusqu'à détection d'une inégalité, - comptage des comparaisons et arrêt du comptage lorsque l'inégalité est détectée, - enregistrement du multiplet de ladite clef immédiatement suivante 10 située à la position représentée par le résultat du comptage au moment de l'arrêt, ledit multiplet étant retenu comme élément de la clef comprimée élaborée. 3r- Dispositif conforme à la revendication 2, caractérisé en outre par des moyens pour effectuer les opérations suivantes lorsque ladite première clef non comprimée est la première clef de tout l'ensemble d'après le système de 15. classement, - enregistrement du résultat du comptage, ce résultat étant retenu pour constituer une zSne de la première clef comprimée (champ "facteur"), - enregistrement de tous les multiplets de ladite clef immédiatement suivante à partir de la position d'ordre le plus élevé jusqu'à la position 20 représentée par le résultat du comptage au moment de l'arrêt. 4.- Dispositif conformé à la revendication 2 ou 3, caractérisé en outre par des moyens'pour effectuer les opérations suivantes: - détection d'un signal enregistré indiquant que ladite clef immédiatement suivante est la dernière clef dans l'ordre de classement mentionné dans 25 la revendication 1, - élaboration, provoquée par la détection de ce signal, d'un code "zéro", - accès à un signal d'adresse représentant l'emplacement du bloc d'informations associé avec ladite clef immédiatement suivante, - enregistrement du code zéro et de ladite adresse, l'ensemble de ces 30 enregistrements représentant la dernière clef comprimée de l'index. 5.- Dispositif conforme à l'une des revendications 2 à 4, caractérisé en outre par des moyens pour effectuer les opérations suivantes: - accès successif à deux paires de clefs au mmins, chaque paire comportant une première clef et une deuxième clef suivant immédiatement la première 69 45787 37 2027738 dans l'ordre de classement défini dans la revendication 1, la deuxième clef de la première paire étant la première clef de la deuxième paire, et exécution, pour chacune des paires, des opérations définies dans la revendication 2, 5 - comparaison des résultats de comptage, et, en fonction du résultat de cette comparaison: a. si le second résultat de comptage est inférieur aui premier? sélection dans la clef comprimée, du multiplet occupant la position pour laquelle une inégalité a été détectée 10 b. si le second résultat de comptage est supérieur au premier: sélec tion pour introduction dans la clef comprimée, de ce multiplet et de tous ceux qui occupent des positions intermédiaires entre œlles représentées par les deux résultats de comptage. 6.- Procédé pour eechercher, à partir d'un argument de recherche composé 15 d'une succession ordonnée dB un ou plusieurs multiplets, dans un index constitué par une suite de clefs comprimées telles que définies dans la revendication 1, une clef comprimée associée au bloc d'information correspondant à l'argument de recherche, chaque clef comprimée comportant un champ, "commande" contenant une indication numérique et un champ "multiplet de clef" conte- 20 nant au moins un multiplet caractérisé par les opérations suivantes: - lecture des champs "commande" d'une clef comprimée et de la clef suivante, comparaison des deux lectures, et, en fonction du résultat de cette comparaison: 25 a. si le contenu du champ "commande" de la second clef comprimée est inférieur ou égal à celui de la première clef comprimée: production d'un signal "facteur" représentant un nombre égal à ce contenu b. si le contenu du champ "commande" de la seconde clef comprimée est supérieure à celui de la première clef comprimée: production) d'un signal 30 "facteur" égal à la différence, augmentée d'une unité, entre les deux; contenus. 7.- Dispositif pour rechercher une clef comprimée à partir d'un argument de recherche conformément au procédé défini dans la revendication B, caractérisé par des moyens pour réaliser ces opérations et pour réaliser en outre les 35 opérations suivantes : - accès successif aux multiplets de l'argument de recherche, dans l'ordre de la succession, et comparaison ëe ces multiplets avec le multiplet d'une clef comprimée occupant la positbn d'ordre le plus élevé 69 45787 38 2027738 production, à chaque comparaison, d'un signal indiquant si ce multiplet de la clef comprimée est placé avant ou après le multiplet: de l'argument de recherche, dans l'ordre de classement préalablement défini mentionné dans la revendication 1, ce signal commandant les opérations ultérieures. 8.- Dispositif conforme à la revendication 7_r caractérisé en outre par des 5 moyens pour effectuer les opérations suivantes, sous l'action dudit signal commandant les opérations ultérieures : a. si le multiplet de la clef comprimée est classé avant celui de l'ar-gumetot de recherche: arrêt de la recherche, b. si le multiplet de la clef comprimée est identique à celui de l'ar-10 gument de recherche: comparaison du multiplet suivant de la clef comprimée avec le multiplet suivant de l'argument de recherche, c. si le multiplet de la clef comprimée est classé après celui de l'argument de recherche: continuation de la recherche en utilisant la clef comprimée suivante.