Brevet FR2420167A1 — publié le 19791012

La présente invention a pour objet un système de manipulation de champs d'éléments binaires. Dans les systèmes de traitement d'informations en temps réel, il est courant de confier des fonctions d'analyse et de commande à un système de traitement de données qui est constitué d'un calculateur numérique à programme enregistré. Ce calculateur reçoit des informations sur des événements survenant à la périphérie du système ; il traite ces données et, en réponse, donne des ordres appropriés. Le traitement des données est accompli par une suite d'opérations élémentaires commandées chacune par une instruction de programme. Chaque instruction désigne la ou les données en cause et le type d'opération à accomplir. D'une oanière générale, un calculateur de ce type traite des "notes" de données, c'est-à-dire des groupes d'éléments d'information binaires ou bits. Dans nombre d'applications, le mot comprend seize bits. Or, dans les applications les plus courantes, les données à traiter ne comportent souvent qu'un nombre restreint de bits contigus, Ainsi, une donnée contenue dans un mot de seize bits n'occupera qu'une partie de ce mot, appelée "champ1,, constituée par un groupe de bits contigus situés en un emplacement défini à l'intérieur du mot.L'invention s-' applique dans le cas assez général où le mot de N bits du calculateur est divisé en M champs égaux et, entre autres, dans le cas où le mot de seize bits est divisé en quatre champs de quatre bits ou quartets. On a alors souvent à effectuer des manipulations sur un champ situé dans un emplacement quelconque d'un mot. Il s'agit soit de mettre tous les bits de ce champ à zéro, ou à un, soit de lire ce champ ce qui conduit à l'écrire dans un registre en le cadrant à droite (ou à gauche), soit d'écrire dans ce champ une donnée préalablement cadrée à droite. Ces opérations se déroulent en plusieurs temps, le premier de ceux-ci consistant à mettre le champ considéré en position avec remplissage de zéros. De telles opérations de manipulations de champs peuvent etre exécutées par prograrnation ; elles sont alors conrmandées par des instructions successives de décalage et de rotation. Les processeurs actuellement cormnescla lisés sont dotés de moyens pour exécuter de telles instructions et la manipulation demandée ne nécessite aucun matériel complementaire. Cette solution présente l'inconvénient d'exiger un temps d'exécution prohibitif. Une autre solution consiste à effectuer les précédentes opérations à l'aide de circuits logiques cabalés associés à l'unité centrale de traitement du calculateur. Le temps d'exécution de la manipulation deinandee est alors très bref. Par contre, cette solution présente l'inconvénient d'exiger l'adjonction de circuits logiques encombrants et couteux et manquant par ailleurs de souplesse. La présente invention a donc pour objet un système de manipulation de champs qui évite les inconvénients des solutions précédentes. Elle permet d'échapper au dilemne posé par ces solutions, à savoir la recherche d'un compromis entre les deux pâles habituels, traitement par programme ou à l'aide de circuits spécialisés. La présente invention propose de traiter la manipulation de champs comme un transcodage et d'ut liser des mémoires pour accomplir ce transcodage. Pour une manipulation donnée, on adresse une mémoire à l'aide des bits du mot initial, pour lire le mot résultant.Quels que soient la longueur du mot initial, son mode de découpage et le type de manipulation demandée, le temps d'exécution est constant et sensiblement égal au temps de lecture de la me moire. En outre, grâce à une simple modification du contenu de la mémoire on peut procéder aisément à d'autres types de manipulation. La présente invention concerne donc un système de manipulation de champs d'éléments binaires ou bits partant d'un mot initial de N éléments binaires divisé en M champs de N/M éléments binaires et aboutissant à un mot résultant divisé en champs de la meme façon que le mot initial et dans lequel le contenu d'un ou plusieurs champs du mot initial se retrouve dans un ou plusieurs champs du mot résultant, caractérisé par le fait qu'il comprend essentiellement N/M mémoires identiques, ayant chacune 2H cellules de mémoire de H emplacements d'éléments binaires, lues simultanément et adressées chacune respectivement à l'aide du groupe de M éléments binaires de meme rang contenus dans les H champs dudit mot initial, et fournissant chacune les M éléments binaires de meme rang du mot résultant. Les différents objets et caractéristiques de l'invention seront maintenant détaillés dans la description qui va suivre, donnée à titre d'exemple non limitatif, en se reportant aux figures annexées qui représentent - la figure 1, un exemple de découpage d'un mot en champs identiques ainsi qu'un exemple de manipulation à effectuer sur ce mot ; - la figure 2, l'exécution de la manipulation définie par la figure 1 selon le principe de transcodage utilisé par la présente invention ; - la figure 3, l'organisation de la zone de mémoire élémentaire utilisée pour effectuer le transcodage défini par la figure 2 ; - la figure 4, un exemple d'un second type de manipulation pouvant etre exécutée par le système de la présente invention ; - la figure 5, un exemple de constitution du système de manipulation de la présente invention. On décrira tout d'abord, en se reportant à la figure 1, un exemple de découpage d'un mot d'information binaire ainsi qu'un exemple de manipulation à effectuer sur ce mot. La figure 1 représente un registre RS dans lequel est écrit un mot initial de N = 16 éléments binaires, par exemple1 divisé en M =4 champs identiques W, X, Y et Z de N/M =4 éléments binaires. Chacun de ces champs est appelé "quartet". La figure 1 représente également un registre RD dans lequel est chargé un mot résultant de 16 éléments binaires divisé en quatre quartets W', X', Y' et Z'. Selon l'exemple choisi, on se propose de transférer le quartet de rang 3, Z, du mot inscrit dans le registre RS, dans le registre RD, en remplacement du quartet de rang 1, X', les quartets W', Y' et Z' étant mis à zéro. Selon les méthodes connues, pour accomplir une telle manipulation, on peut transférer le contenu du registre RS dans un registre accusulateur. On décale le contenu de ce dernier registre de huit pas à gauche. Le quartet Z est alors cadré à l'emplacement désiré. Les autres quartets contenus dans le registre accumulateur sont ensuite mis à zéro à l'aide d'une instruction ET, en faisant appel à une constante appropriée, en l'espèce 0000 1111 0000 0000. La manipulation demandée est effectuée et on transfère le contenu du registre accuiulateur dans le registre RD. Le temps mis pour accomplir ces opérations successives est prohibitif. Une autre solution consiste à transférer sélectivement le contenu du registre accuntulateur dans le registre RD à l'aide d'un opérateur spécialisé intercalé entre ces deux registres et comprenant seize groupes de quatre portes ou seize multiplexeurs à quatre entrées. Cette solution nécessite donc l'adjonction de circuits logiques nombreux donc encombrants et coûteux. On décrira maintenant, en se reportant également à la figure 2, le principe utilisé par le système de manipulation de la présente invention. La figure 2 représente un mot réduit MSO de quatre bits Wo, xO, L0 et zO, qui sont respectivement les bits de rang 0 des quartets W, X, Y et Z du mot initial inscrit dans le registre RS. En appliquant à chaque bit du mot réduit MSO la manipulation effectuée précédemment et illustrée par la figure 1, on obtient un mot réduit MDO, également représenté sur la figure 2. Ce mot est compose de quatre bits 0, zO, O et 0. On voit donc que pour passer du mot réduit MSO au mot reduit MDO, il suffit d'opérer une peroutation avec le remplacement de certains bits (wO, #0 et zO) par des zéros. On ferait de meme pour passer respectivement des mots réduits MSi#, MS2 et MS3, composés respectivement des bits de rangs 1, 2 et 3 des quartets W, X, Y et Z du mot initial inscrit dans le registre RS, aux mots réduits WDI, ND2 et MD3, la perlutation effectuée étant la meme que celle effectue pour passer du mot réduit NSO au mot réduit MDO. L'invention part de la constatation que cette permutation peut etre considérée conne une forme de transcodage et propose donc de l'effectuer à l'aide d'une #moire. La figure 3 représente de façon schématique une zone de mémoire MO permettant de réaliser la manipulation sur les quatre bits wO, xO, yO et zO illustrée par la figure 1. La zone de mémoire MO comprend seize cellules adressables contenant chacune quatre bits. On lit une de ces cellules en utilisant les bits wO, xO, et etzO comme adresse. L'information contenue dans chaque cellule comprend quatre bits : w'O = O, x'O = zO, y'O =O et z'O = 0. Ainsi, pour toute valeur du mot réduit MSO, la zone de mémoire MO fournit le mot réduit correspondant à la permutation voulue, NDO. On a vu précédemment que la manipulation à effectuer, illustréepar la figure pouvait etre réalisée par quatre transcodages identiques tels que celui défini par la figure 2. L'invention prévoit donc quatre zones de mémoire telles que la zone MO pour exécuter la manipulation définie par la figure 1. Chacune de ces zones, pour toute valeur du mot réduit composé de quatre bits qui sont respectivement les bits de meme rang des quartets W, X, Y et Z du mot initial inscrit dans le registre RS, fournit le mot réduit correspondant à la permutation voulue. Les transcodages à effectuer étant identiques, les contenus respectifs de ces quatre zones de mémoire sont identiques. Chacune des seize cellules adressables de ces zones contient quatre bits dont trois sont des zéros et dont le quatrième (le bit de rang 1) est 0 ou 1 selon que le bit de rang correspondant du quartet Z du mot initial inscrit dans le registre RS (figure 1) est O ou 1. La loi de remplissage de chacune de ces quatre zones peut donc etre écrite de façon symbolique : (Mi) = O.zi.O.O. On remarque que, les zones de mémoire étant lues simultanément, le temps nécessaire pour effectuer ce transcodage est égal au temps nécessaire pour effectuer une opération de lecture. On peut, si on le désire, ne prévoir qu'une seule zone de mémoire, MO par exemple. Dans ce cas, on procède à quatre lectures successives des mots de cette zone, en utilisant respectivement comme adresses : wO xO 9 zO, wl xlyl zl, w2 x2 2 z2 -etw3 x3 y3 z3. On divise ainsi la capacité de mémoire nécessaire par 4, le temps d'exécution étant multiplié par 4. Le système décrit permet donc bien d'effectuer la manipulation de la figure 1, dans un temps relativement réduit. Il permet de meme l'exécution d'autres manipulations, telle la manipulation illustrée par la figure 4, c'est-à-dire une manipulation portant sur deux quartets contigus (octet). Cette manipulation sera effectuée selon le principe décrit précédemment, à l'aide de quatre zones de mémoire supplémentaires ou de cellules supplémentaires dans les zones de mémoire utilisées précédemment. D'une façon générale, chaque nouveau type de manipulation demande seize cellules supplémentaires par zone de mémoire.Ainsi, pour transférer le quartet Z du mot initial inscrit dans le registre RS (figure 1) dans le registre RD, en remplacement du quartet W! et non plus en remplacement du quartet X', seize cellules de mémoire supplémentai- res sont nécessaires. Plus generalement, pour pouvoir transférer le quartet Z dans le registre RD, en remplacement de l'un quelconque des quatre quartets W', X', Y' et Z', a capacité de chacune des quatre zones de mémoire telles que M0 doit etre de 16 x 4 = e4 cellules de quatre bits chacune.Une capacité de mémoire supplémentaire identique sera requise si on seut pouvoir effectuer le transfert de l'un quelconque des quartets du mot initial inscrit dans lc registre RS dans le champ cadré à droite par exemple du met résultant inscrit dans le registre ED. An décrira maintenant, en se reportant a' la figure 5, un exemple de réalisation couplet du système de manipulation de champs da la présente Invention. Sur la figure 5 on retrouve le registres d'entrée Rs ct de sertie RD de la figure 1. Dans le registre RS est inscrit le mot initial de 16 bits divisé en quatre quartets composes resnectivement des bits w0 a w39 xO à x8, y0 à y3 et ZO à z3. On a également représente une porte du système de traite- ment de données UC. Cette partie comprend essentiellement un registre d'instruc- tison RI et un circuit de décodage DEC.Dans le registre d'instruction RI est charge un mot d'instruction comprenant notamment le code d'instruction CO définissant la manipulation à effectuer ainsi que le mot sur lequel porte cette manipulation. Ce mot d'instruction comprend également cinq éléments binaires Si, 52, D, E et B qui définissent le groupe de seize cellules de mémoire qui convient pour le type de manipulation désire.Ainsi les bits S1, S2, par exemple, désignent le quartet du mot initial écrit dans le registre RS que l'on doit transférer dans le registre RD, en remplacement du quartet de rang 3 du mot résultant, ou désignent l'emplacement du mot résultant dans lequel doit etre écrit le quartet cadré à droite du mot initial (un de ces cas étant illustré par la figure 1), le bitD indiquant duquel des deux cas ci-dessus il s'agit, tandis que le bit B indique si la manipulation considérée porte sur un quartet ou sur un octet (cas de la figure 4). Le bit E est disponible pour d'autres cas de manipulation. Le système de la figure 5 comprend également quatre mémoires, dont seulement la première MO et la dernière M3 ont été représentées. Selon l'exemple choisi, chacune de ces mémoires comprend 512 cellules de 4 bits, c 'est-à-dire 32 groupes de 16 cellules. Le groupe de cellules qui convient pour effectuer la manipulation demandée est sélectionné à l'aide des cinq bits SI, 52, D, E et B.La cellule de ce groupe qui contient le mot restreint résultant dans chacune des mémoires HO à M3 est adressee à l'aide des bits de meme rang de chaque quartet du mot initial transmis à la me moire correspondante via une porte logique commandée par un signal de validation vali. Ainsi, les bits de rang 0 de chaque quartet du mot initial, 0, xO, #0 et zO, sont transmis à la mémoire M0 via une porte logique d!entrëe peO, les bits de rang 3 de chacun de ces quartets, w3, x3, ç et z3 > e tant transmis a la mémoire M3 via une porte logique d'entre pe3. Les mots résultants restreints lus dans les mémoires MO à M3 sont respectivement fournis au registre de sortie RD via des portes logiques de sortie psO à ps3. Ainsi les quatre bits wtO, x'O, 9'0 et z'O du mot restreint resultant, lus dans la mémoire NO, sont fournis respectivement au registre RD via la porte psO, commandée par un signal de validation val2, aux emplacements des bits de rang O de chaque quartet du mot résultant, les quatre bits w'3, x'3, y'3 et z'3 du mot restreint résultant, lus dans la mémoire M3, étant fournis aux emplacements des bits de rang 3 de chaque quartet du mot résultant via la porte ps3 coandée par le signal val2. Lorsqu'une manipulation sur un mot est demandée, ce mot initial est déjà inscrit dans le registre RS et le mot d'instruction vient s'inscrire dans le registre d'instruction RI. Le circuit de décodage DEC, commandé par des impulsions dthorloge HG, lit le code d'instruction CO inscrit dans le registre RI et fournit, en temps voulu, les signaux de validation vall et val2 ainsi qu'un ordre de lecture lec des mémoires. Le mot résultant est alors inscrit dans le registre de sortie RD. Le système de 11 invention permet donc bien ltexécution de manipulations de champs d'éléments binaires. Il ne nécessite que l'adjonction de mémoires, quatre me'moires de 512 cellules de 4 bits selon l'exemple choisi, qui couvrent les différentes manipulations rencontrées couramment. Ce système est donc d'un prix de revient faible. D'autre part, le temps d'exécution est constant, quels que soient le type de manipulation à effectuer et le découpage du mot initial. Par ailleurs, il est facile de modifier les opérations de manipulations prévues, simplement en variant le contenu des mémoires HO à M3, ou d'en ajouter, en prévoyant à l'origine une capacité de mémoire supérieure aux besoins. Il est bien évident que la description qui précède n'a été donnée qu'à titre d'exemple non limitatif et que de nombreuses variantes peuvent etre envisagées sans sortir pour autant du cadre de l'invention. Les précisions numériques, notamment, n'ont été fournies que pour faciliter la compréhension et peuvent varier avec chaque cas d'application. REVENDICATIONS 1. Système de manipulation de champs d'éléments binaires ou bits partant d'un mot initial de N éléments binaires divisé en M champs de N/M éléments binaires et aboutissant à un mot résultant divisé en champs de la nîme façon que le mot initial et dans lequel le contenu d'un ou plusieurs champs du mot initial se retrouve dans un ou plusieurs champs du mot résultant, caracterise par le fait qu'il comprend essentiellement une mémoire, ayant 2H cellules de me moire de M emplacements d'éléments binaires, lue et adressée à l'aide d'un groupe de M éléments binaires d'un meme rang contenus dans les M champs dudit mot initial, et fournissant alors les M éléments binaires de ce meme rang des M champs dudit mot résultant. 2. Systeme de manipulation de champs d'éléments binaires tel que défini en 1, caractérisé par le fait qu'il comprend essentiellement N/H me moires identiques, ayant chacune 2M cellules de mémoire de N emplacements d'éléments binaires, lues simultanément et adressées chacune respectivement à l'aide d'un groupe particulier de M éléments binaires de meme rang contenus dans les M champs dudit mot initial et fournissant chacune le groupe correspondant de H éléments binaires du meme rang des M champs dudit mot-résultant. 3. Système de manipulation de champs d'éléments binaires tel que défini en 2, caractérisé par le fait qu'il comprend essentiellement (N/M)/2n mémoires identiques adressées lacune 2n fois, une telle disposition permettant de réduire la capacité de mémoire requise. 4+ Système de manipulation de champs d'éléments binaires tel que défini en 1 et partant d'un mot initial de N éléments binaires divise en M champs de M/M éléments binaires pour aboutir à un de plusieurs mots résultants selon le cas de manipulation envisagé, caractérisé par le fait qu'il comprend essentiellement une me moire ayant, pour chaque cas de manipulation pouvant etre effectué, 2M cellules de mémoire de M emplacements d'éléments binaires, ladite mémoire étant lue et adressée à l'aide d'un groupe de M él8sents binaires d'un meme rang contenus dans les M champs dudit mot initial et fournissant alors les H éléments binaires de ce meme rang des M champs dudit mot résultant.