Brevet FR2543323A1 — publié le 19840928

DECODEUR D'UNE DONNEE DANS UN SOUS-GROUPE DE P DONNEES APPARTENANT A UN GROUPE DE N DONNEES. La présente invention concerne de façon générale un décodeur permettant de sélectionner une donnée prédéterminée dans un groupe de P données, ces P données faisant partie d'un groupe plus important de N données La présente invention trouve notam- ment des applications dans les systèmes d'affichage graphiques et alphanumériques, mais pourra s'appliquer au décodage de données dans de nombreux autres cas. Dans la description suivante de 9 l'art antérieur et de la présente invention, on considerera généralement le cas o N = 2 N et o P = 2 P Néanmoins, P et N peuvent être quelconques du moment que P est inférieur ou égal à No. La présente invention s'intéresse aux decodeurs dans le cas particulier ou l'on cherche à effectuer un décodage en temps reel, ce qui exclut par exemple l'emploi de compteurs explorant sequentiellement un registre pour determiner l'emplacement du premier ou du nième '1 " contenu dans ce registre En informatique, dans de nombreux cas, on cherche à retrouver une donnée faisant partie d'un ensemble de N donnees Pour cela, il convient de prevoir une mémoire ou un registre contenant ces N données et un adressage de cette memoire Cet adressage doit correspondre a un mot de N bits si N = 2 n Si l'on a enregistre une succession d'evenements correspondant à l'incidence successive des diverses données, on enregistrera la succession des mots de N bits correspondant aux adresses des données Si l'on tient à mémoriser une séquence importante de données, ou plus exactement d'adresses de données, il est souhaitable que ces adresses soient aussi cour- tes que possible. Il existe un cas au moins o il est possible de raccour- cir la longueur du mot d'adresse à une valeur inférieure à n. C'est le cas ou, pendant une séquence determinée, la donnée choisie n'est pas I'une quelconque des N donnees, mais appartient à un sous-groupe P de ces N données On concevra alors que, pen- dant cette séquence, on puisse désigner la donnée recherchée par son numéro d'ordre ou son adresse parmi les P données, c'est-à- dire utiliser une adresse de seulement p bits si P = 2 p Il reste alors à faire la corrélation entre l'adresse ou le numéro d'ordre parmi les P données et l'adresse ou le numéro d'ordre parmi les N données En d'autres termes, à partir du numéro parmi les P données, il faut déterminer le numéro parmi les N données. Pour résoudre ce problème, si l'on utilise les méthodes classiques et immédiates de l'informatique, on considérera qu'il existe 2 N combinaisons des N données et qu'il faudra done prévoir un décodeur comprenant une mémoire morte ou un réseau logique programmable d'une capacité ou d'un nombre de noeuds égal à p.n 2 N. La présente invention vise à réaliser un décodeur particulièrement simple et n'exigeant pas une mémoire de si grande capacité. Pour atteindre cet objet, la pre ente invention prévoit un décodeur en temps réel d'une donnre appartenant à un sous- groupe de P données faisant elles-mêmes partie d'un groupe de N données avec P inférieur à N, comprenant: un premier registre de N cases, chacune de ces cases correspondant de façon ordonnée a l'une des données, la présence ou l'absence de chaque donnée étant indiquée par l'état binaire de la case correspondante, P données parmi les N étant presentes; un deuxieme registre de P cases dont l'une, correspondant au numéro parmi P de la donnée à decoder, est dans un état binaire different de celui des autres; un circuit d'aiguillage à P lignes et N colonnes, chaque intersection de ligne et de colonne étant occupée par une cellule comprenant une borne de commande d'aiguillage, une entrée et deux sorties, la première sortie étant reliée à l'entre de-la cellule suivante de la même ligne, la deuxième sortie étant reliée à l'entrée de la cellule suivante de la ligne suivante, sauf en ce qui concerne les cellules de la ligne de rang le plus faible pour lesquelles la deuxième sortie est reliése à une borne de sortie; les P entrees des cellules de la première colonne étant reliées aux cases du deuxième registre; les commandes d'aiguillage de toutes les cellules d'une colonne étant reliées à une case du premier registre; d'o il résulte que l'on retrouve sur les bornes de sortie des cellules de la ligne de plus faible rang un état binaire différent pour la colonne parmi les N correspondant-à la donnée parmi les P fixée dans le deuxième registre. Des modes de réalisation particuliers des cellules du circuit d'aiguillage ainsi qu'une application de la présente invention à un système d'affichage de signes graphiques ou alphanumériques seront exposés dans la description détaillée ci- apres Cette description est faite en relation avec les figures jointes parmi lesquelles: la figure 1 représente divers registres et servira de soutien à un exposé général des buts de l'invention; la figure 2 représente sous forme de blocs un décodeur selon la présente invention; la figure 3 représente schématiquement sous forme de relais des cellules d'un décodeur selon la présente invention; la figure 4 représente schématiquement une réalisation sous forme de transistors MOS de cellules d'un decodeur selon la présente invention; et la figure 5 illustre une application d'un décodeur selon la présente invention à un circuit d'affichage graphique ou alphanumérique. Dans ce qui suit, on prendra essentiellement comme exemple le cas ou le nombre N = 8 (n = 3) et ou le nombre P = 4 (p = 2). Etant donné un ensemble de huit (N) objets ou données ou mots, désignés par les lettres A à H, et rassemblés dans une memoire ou registre de données 0, on cherche à désigner parmi ces huit données, quatre (P) d'entre elles, par exemple les données B, C, F et H Pour ce faire, on associe au registre de données 10 un registre image 20 comprenant également N (huit) cases, dans lesquelles on introduit un état binaire distinct selon que la donnée correspondante appartient ou non au sousgroupe sélectionné Ainsi, on a associé l'état binaire O aux données A, D, E, G et l'état binaire 1 aux données B, C, F et H On cherche à 25481 t 3 identifier la lettre F en l'identifiant par son numéro d'ordre (i) dans le sous-groupe des P (quatre) données présentes, c'est-à-dire le numéro 3 dans le sous-groupe des données B, C, F et H Le décodeur doit permettre de convertir cette indication (i) du numero d'ordre dans le sous-groupe en une indication (j) du numéro d'ordre dans le groupe de N données figurant dans le registre image 20, ce deuxième numéro d'ordre étant, dans le cas illustré, le numéro 6 pour la lettre F. Le dcodeur selon la présente invention comprend un ensemble de cellules d'aiguillage disposées selon P lignes et N colonnes En figure 2, les P cellules d'une même colonne ne sont pas représentées individuellement; on a seulement représenté sous forme de blocs ( 301 à 308) les N (huit) ensembles de cellules constituant les colonnes du circuit d'aiguillage Des réalisations de ces blocs seront d&crites en relation avec les figures 3 et 4. Les P cellules de chacune des colonnes respectives ( 301 308) sont commandées par une sortie respective du registre image 20 mentionné précédemment L'entrée ( 401 à 404) de chaque ligne (c'est-à-dire les entrées des cellules de la première colonne) reçoit un signal dans un premier ou un second état binaire, figuré dans un registre 50, le second état binaire, par exemple un 1, correspondant i l'indication du numéro parmi P de la donnée que l'on cherche à identifier En d'autres termes, la ieme case du registre 50 est à l'etat 1, i étant le numero parmi P de la donnee recherchée Chaque cellule d'une colonne transmet le signal de son entrée vers l'entrée de la cellule de la colonne suivante et de la même ligne, si les cellules de cette colonne correspondent à un contenu O dans le registre 20 Si le contenu de la case du registre image 20 correspondant à une colonne de cellules est à 1, toutes les cellules de cette colonne auront pour effet de transmettre le signal à leur entrée vers l'entrée des cellules de la colonne suivante, mais de la ligne de rang inférieur La cellule inférieure de chaque colonne est connectée à une borne de sortie ( 601 à 608) Le signal d'entrée de cette dernière cellule est dirigé vers la borne de sortie si la commande de cette cellule est à 1 et vers la cellule correspondante de la colonne suivante si le signal de commande de cette cellule est à 0. Dans la figure 2, on a représenté le cas o l'on cherche à identifier le numéro j parmi N d'une donnée dont le numéro i parmi P est égal à trois Ainsi, dans le registre 50, la troisième case contient un 1 et les autres 'cases contiennent un 0 La première cellule rencontrée est commandée par un O du registre 20 et transmet sa sortie à l'entrée de la cellule suivante de même rang de la colonne 302 Par contre, au niveau des colonnes 302 et 303, qui sont commandées par des 1 dans le registre 20, le signal d'entrée est transmis vers la cellule de la colonne suivante de niveau inférieur Dans les cellules des colonnes 304 et 305, commandées par des 0, aucun décalage du signal de sortie par rap- port au signal d'entrée n'apparaît Puis, au niveau de la cellule inférieure de la colonne 306, qui est commandée par un 1, le signal d'entrée est envoyé vers la borne -de sortie On obtient donc aux sorties 601 à 608 une succession de 0, puis un 1 à l'emplacement correspondant à la donnée sélectionnée La position de ce 1 correspond au numéro j parmi N de la donnée sélectionnée. Dans l'exemple représenté, il apparaît que la troisieme parmi les P données est la sixième parmi les N données Les bornes de sor- ties 601 à 608 ont été figurées comme connectées à un registre 70 : normalement ce registre pourra être le même que le registre de données 10 de la figure 1. Les cellules de la figure 2 peuvent être réalis&es sous forme de relais comme cela est représenté en figure 3 pour les cellules d'une même colonne, par exemple de la première colonne 301 Cette colonne comprend quatre entrées el à e 4 correspondant aux lignes 401 à 404, quatre sorties sl à S 4 vers les entrées des cellules de la colonne suivante et une sortie de commande 601. Dans le cas représenté ou la colonne considérée est commandée par un 0, chacune des entrées el à e 4 est connectée à la sortie correspondante s I à S 4 et la sortie de commande 601 est connectée à une source de tension correspondant à l'état binaire 0, par exemple la masse Si par contre cette colonne de cellules est commandée par un 1, tous les relais représentés passent en posi- tion basse, la sortie S 4 est reliée à une tension de référence correspondant à l'état 0, par exemple la masse, la sortie S 3 est reliée à l'entrée e 4, la sortie S 2 à l'entrée e 3, la sortie sl à l'entrée e 2 et la sortie de commande 601 à l'entrée el. La figure 4 représente un mode de réalisation d'une colonne de cellules selon la présente invention utilisant des transistors MOS Tl à T 4 et T'l à T'4 Les transistors MOS T à T 4 d'une part et les transistors MOS T'Il à T'4 d'autre part sont commandés par des signaux complémentaires Q et Q*, le signal Q par exemple correspondant au contenu du registre 20 de la figure 2. Ainsi, si les transistors MIOS Tl à T 4 sont conducteurs, les entrées et les sorties de même rang sont reliées Par contre, si les transistors MOS T'i à T'4 sont conducteurs, les entrées sont reliées aux sorties de rang inférieur, l'entrée el étant connectée à la borne de commande 601 En outre, deux transistors T 5 et T'5 sont destinés à éviter que dans certains cas des bornes se trouvent "en l'air" Dan -cette réalisation, le circuit d'aiguillage selon la présente invention comprendra donc seulement ( 2 P + 2)N transistors MOS. Encore convient-il de remarquer que certaines des cellu- les apparaissant dans le circuit d'aiguillage de la figure 2 peuvent être supprimées, notamment, les trois derniires cellules (ou cellules supérieures) de la dernière colonne 308, les deux dernières cellules de l'avant-dernière colonne 307 et la dernière cellule de l'anté-pénultieme colonne 306 De façon genérale, on peut supprimer P 1 cellules de la dernièere colonne, P 2 cellules de la colonne précédente, P 3 cellules de la colonne précédente, et ainsi de suite En effet, puisqu'il y a en tout P descentes de niveaux, dès la (N P + l)ieme colonne, on est sûr qu'une descente de niveau a déja eu lieu La cellule supérieure de cette colonne est donc non nécessaire et ainsi de suite pour les colonnes suivantes Néanmoins, dans certains cas, pour simplifier la réalisation automatique des masques correspondant à l'implantation du circuit iutégré, on préférera maintenir les cellules inutiles. La figure 5 illustre un cas ou la présente invention peut s'appliquer de façon particulièrement intéressante, c'est le cas d'un afficheur graphique couleur Dans un tel afficheur, un contrôleur 80 fournit des signaux indicatifs d'un balayage d'écran et d'adressage d'une mémoire de page La mémoire de page 81 con- tient les informations correspondant à la couleur de chaque point de l'écran C'est donc une mémoire de grande dimension, par exemple de 80 000 cases Le contenu de chaque case, adressé séquentiellement, est envoyé à un interpréteur 82, qui fournit, pour le point adressé correspondant à l'instant présent du balayage, des informations sur la proportion, ou la présence ou l'absence, des informations R, V, B (rouge, vert, bleu) pour les trois canons de l'afficheur couleur On peut obtenir huit couleurs sur l'écran si chacun des canons peut être excité à l'une ou l'autre de deux valeurs Ainsi, pour mémoriser l'une ou l'autre de ces huit informations, la mémoire de page doit normalement con- tenir trois bits par case. Pour réduire la dimension de cette mémoire, on souhaite par exemple ne prévoir que deux bits par case, ce qui réduit d'un tiers la dimension de la mémoire de page, mais qui limite bien entendu la possibilité de choix de couleur à quatre Il a été propos& de diviser la page ou l'écran en fenêtres, par exemple de dimensions 5 x 10 pas élémentaires et dans chaque fenêtre de n'inclure que quatre couleurs On peut alors, à condition de prévoir une mémoire de fenêtre 83 indiquant pour chaque instant du balayage quel est l'ensemble de quatre couleurs choisi, ne memoriser dans la memoire de page que deux informations par case. L'interpreteur 82 peut typiquement être un circuit selon la présente invention, la mémoire de fenêtre fournissant à tout instant le contenu du registre image 20 des figures 1 et 2 et la mémoire de page fournissant le contenu du registre 50 de la figure 2 Avec le circuit d'aiguillage simple selon la présente inven- tion, l'économie d'un tiers de la capacité de la mémoire de page, c'est-àdire de sensiblement 80 000 points mémoire, est particulièrement intéressante vu le faible nombre de composants additionnels nécessaires et vu que ces composants additionnels peuvent simplement être réalisés dans un circuit intégré par des techniques classiques. Bien que l'on ait décrit la présente invention seulement dans le cas ou P = 4 et ou N = 8, bien entendu l'invention s'applique à des valeurs quelconques de P et N pour autant que P soit inférieur ou égal à N D'autre part, bien qu'une application particulière de la présente invention a été décrite, l'invention pourra s'appliquer à de nombreux autres systemes informatiques. REVENDICATIONS. 1 Décodeur en temps réel d'une donnée comprise dans un sous-groupe de P données appartenant à un groupe de N données (P inférieur ou égal à N) comprenant: un premier registre ( 20) de N cases, chacune de ces cases correspondant de façon ordonnée à une des données, la présence ou l'absence de chaque donnée étant indiquée par l'état binaire de la case correspondante, P données parmi les N étant présentes; un deuxième registre ( 50) de P cases dont l'une, correspondant au numéro (i) parmi P de la donnée à décoder, est dans un état binaire distinct de celui des autres cases; caractérisé en ce qu'il comprend en outre un circuit d'aiguillage à P lignes ( 401 à 404) et N: colonnes ( 301 à 308), chaque intersection de ligne et de colonne étant occupée par une cellule comprenant une borne de commande d'aiguillage, une entrée et deux sorties, la premiere sortie étant reliée à l'entrée de la cellule suivante de la même ligne, la deuxième sortie étant reliée à l'entrée de la cellule suivante de la ligne de rang inférieur, sauf en ce qui concerne les cellules de la ligne du rang le plus faible pour lesquelles la deuxieme sortie est reliée à une borne de sortie ( 601 à 608), les P entrées des cellules de la premiere colonne ( 301) étant reliées aux cases du deuxieme registre; les commandes d'aiguillage de toutes les cellules d'une même colonne étant reliées à une case du premier registre pour relier l'entrée de chaque cellule vers la première ou la deuxième sortie de cette cellule selon le contenu de la case; d'ou il résulte que l'on retrouve sur les bornes de sortie des cellules de la ligne de plus faible rang un état binaire différent dans la colonne j parmi les N qui correspond à la donnée parmi P fixée dans le deuxième registre. 2 Décodeur selon la revendication 11 caractérisé en ce que chaque cellule est constituée d'un relais à une entrée et deux sorties. 3 Décodeur selon la revendication 1, caractérisé en ce que chaque cellule comprend deux transistors MOS commandés par des signaux complémentaires, l'un de ces transistors étant connecté à l'entrée de la cellule suivante de même rang et l'autre de ces transistors étant connecté à l'entrée de la cellule suivante de rang inférieur.