Brevet FR2649226A1 — publié le 19910104

CMI}IT DE BRASSA E DNEE La présente invention concerne un circuit de brassage de données, c'est-àdire un circuit reoevant un train de données et fournissant en sortie oes mames donrme- agenrees dans un ordre différent et prédéterminé. De nombreuses applications, notamment dans le domaine du traitament d'image, réoessitent l'utilisation d'opérateurs ou circuits capables de changer l'ordre d'une série de donées suivant une séquence préétablie. Un exeample d'une telle application est le calcul de la transformée bidi siorelle, telle que la transformée cosinus discrète (DCT), d'un bloc d'image dans une image de télévision o è problème du brassage intervient plusieurs fois: - brassage des données pour le calcul de la transformée nmordimensionselle, - transposition de matrioe, - conversion du balayage de la matrice de coefficients en un balayage zig zag. Un autre exemple d'application réside dans le cryptage d'un signal vidéo par mélange de pixels. On va décrire ci-après l'état de la technique et la présente invention dans le cas particulier o 1 'on souhaite effectuer le balayage zig zag d'un bloc de données. On notera toutefois qu'il ne n'agit là que d'un cas particulier de la présgente invention qui est décgrit de façon détaillée seulement pour faciliter la oapréIension de l'invention. Les figures lA et 1B illustrent oe qu'est un balayage zig zag. Etant donné une suite de dnnées, par exemple 16 données telles que reprsentes en figure lA so^^ forme d'un bloc d'image 4 x 4, un balayage zig zag consiste à lire oes nnées selc des diagonales successives, c'est-à-dire comme oela est illustré en figure 1B.dans l'ordre: 1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16. La façrn la plus classique de réalister un tel brassage de donrnées consiste & utiliser un circuit du type de celui illus- tré en figure 2. Ce circuit comprend deux mémoires dynamiques (RAM) M1 et M12 ayant chacune la taille du train ou bloc de données que l'on veut brasser. Chacune des mnmoires est adressa- ble ou bien dans l'ordre naturel de la figure 1A par un compteur C ou bien dans l'ordre correspndant à une séquence mdmarisée dans une mémoire morte ROM 10 dont le contenu correspond à ce qui est indiqué en figure lB pour un brassage zig zag. Chaque train ou bloc de données arrivant sur une entrée 11 est écrit dans l'une des mnnoires dans l'ordre naturel tandis que l'autre mémoire est lue dans l'ordre zig zag vers une sortie 12. Au coup d'après, les données sont écrites dans la mémoire qui vient d'être lue tandis que la mémoire dans laquelle on vient d'écrire est lue. Cette technique réocessite une capacité de mémrorisation de deux trains ou blocs de données dans les mémoires dynamiques Ml et M2 et d'une séquence de mots d'adresse dans la ROM 10. A titre d'exemple, si 1 'on onsidere des blocs 4 x 4 et des mots de 12 bits, la capacité de mémorisation des RAM devra être de 32 mots de 12 bits (384 bits) et la capacité de nmémari- sation de la ROM 10 de seize mots de 4 bits (64 bits), soit une capacité de mémarisation totale de 448.bits. Dans le ca de blocs de 64 mots (8 x 8) il convient de prévoir une capacité RAM de 128 (2 x 64) mots de 12 bits (1536 bits) et une ROM d'une capacité de 64 mots de 6 bits (384 bits), soit une capacité de mémorisation totale de 1920 bits. Pour rdie la capacité de mnmrisation néoessaire, on a pesé utiliser le schema s/mplifié illustré en figure 3 comprraia une seule mnmoire RAM MD dont la capacité de nmmori- sation est égale à la dimension du bloc de dnées incident que l'on veut transformer recevant les trains de &ries sur urn entre 11 et les fotrnissant de façon r__dor&r=e sur une sortie 12. Cette néîoire MD est adressée par une R1M 13 cenna,, par un compteur C. Initialement, la mnmoire MD est remplie du premier bloc de doées agenc normalement dans l'ordre de 1 à 16. Pour le bloc de dmnns suivant, la R0M détermine que l'adressage se fait selon un ordre déterminé. Chaqe fois qu'une dconée est lue à une adresse spécifiée, une d&nnée du train incident est simultanrment écrite à l'endroit qui vient d'être lu. Cette archtecture permet donc de diviser par deux la capacité de la mémoire RAM et de sim- plifier les circuits d'adressage puisque les lecture/criture se font séquentiellement dans une reme case sans réadressage. Toute- fois, il faut prévoir une augmentation de la capacité de la ROM 13 pour fournir les adresses séquentielles neoessaires au traite- ment de blocs de &nnées sucssifs. Cette structure a été utili- sée dans le cas ou le brassage des do&nées correspond à une transposition matricielle (symetrisation par raport une diagconle). En effet, ètte opération est involutive c'est-a-dire qu'après deux transpositions on retrouve l'ordre initial. Il est donc seulaet nécessaire de mmroriser dans la R0M 13 une séquence d'adresse. Par contre, l'cpératicn est plus oemplexe dans le cas d'un balayage zig zag, comme cela est illustré dans les figures 4A à 4F pour le cas de blocs de domnfs 4 X 4. La preiière séquence d'adresses, cxrrespondant à l'ordre naturel est illus- trse en figure 4A. La séquence d'adresses suivante est illustrée en figure 4B o0 l'on peut voir que la troisième adresse corres- pcnd à la case 5 et la quatrième à la case 9. Le tableau de la figure 4B est obtenu en suivant les flèmhes représentées en figure 4A. Pour le bloc de données suivant, en suivant la même séquence zig zag que oelle qui permet de passer de la figure 4A à la figure 4B et en appliquant oette séquence à la figure 4B, on peut voir que l'ordre successif sera 1, 2, 6, 10... (figure 4C). On passe de même de chacune des figures à la suivante. En regar- dant la figure 4F, on voit qu'en appliquant un balayage zig zag aux données qui y sont contmeues, on retrouve la séene naturelle de la figure 4A. Il faut dom prévoir six cycles d'adressage dans la ROM pour pouvoir recrnvertir selon un ordre zig zag des trains de données successifs. En xonsidérant les mâmes données nmériques que ci- dessus, pour des blocs 4 X 4 de dcnnées & 12 bits, il faudra dnc prévoir une capacité RAM de 16 mots de 12 bits (192 bits) et une capacité ROM de 6 x 16 mots d'adresse de 4 bits (384 bits), soit une capacité de mémorisation totale de 576 bits. Dans le caq d'un balayage zig zag de blocs 8 X 8, il faudra enchaîner 136 séquences différentes avant de retomber sur la séquence initiale oe qui nécessite une ROM de stockage de 8704 (136X64) mots de 6 bits soit 51 kbits auxquels il convient d'ajouter les 64 mots de 12 bits de la RAM. Il est dnc clair que dans oe cas la solution initiale à deux RAM telle qu'illustrée en figure 2 est beaurcoup plus économique que la solution à une RAM telle qu'illustrée en figure 3. En outre, dans les représentations extrêmement schma- tiques des figures 2 et 3, on n'a pas figuré les divers décodeurs qui sont rkesvsiment associés aux RM de stockage et qui eux aussi occupent une surface de silicium non négligeable. Un autre inccxevénient des circuits de brassage de données de l'art antérieur réside dans le fait que les structures à points mémoire sont irnvitablement de fabrication délicate et entramnent la nécessité de prévoir des étapes de tri et de test pour vérifier qu'aucun des points mémoire n'est en défaut. Un autre irc'rvénient des str-ctures de l'art antérieur est que le procédé d'utilisation des circuits de brassage décrits nécessite le remplissage initial d'un bloc nDmoire complet. Le temts de latence est donc égal à la durée du reripliqsage initial d'une mâmoire complète, c'est-à-dire à la durée d'introduction de tous les uots d'un train de doaées. Un objet de la présente invention est de prévoir un circuit de brassage palliant les irlwxvnients des deux circuits si3ticxns de l'art antérieur et, plus particulièrement: - réduisant la surface de silicium nécessaire, - ae enttant la fiabilité du systéme, - réduisant le teimps de latenhe. Pour atteindre ces objets ainsi que d'autres, la présente inventicn prévoit un circuit de brassage de donmes de type pipeline recevant des trains successifs de n mots de données s&qentiels et rérdonnant dans chaque train les mots de données selon un ordre prédéterminé, comportant: - - p (pn) mDdules éléoentaires de traitement placés en série, chaque module comprenant une entrée, une sortie, un regis- tre de mnmorisation d'un mot, et un moyen d'aiguillage pour, en répcanise à une ommande binaire, o=ncter l'entrée à la sortie ou bien directement ou bien par l'intermédiaire du registr; et - des moyens pour fournir cycliquement à chacun des p moyens d'aiguillage une séqoene de n bits de coummalde fixés en foncticn dudit ordre prédéterminé. Ainsi, la présente invention évite complèteent l'uti- lisaticn de mémoires RAM et n'utilise que des registres indivi- duels d'un mot de données qui sont a priori des dispositifs beau- Coup plus fiables que des mémoires. En outre, on n0tera que le circuit selcn la présente invention fonctionne en mode pipeline, c'est-à-dire réduit au maximum le temps de latence. Ces objets, carctéristiques et avantages ainsi que d'autres de la présente inventicn seront exposs plus en détail dans la description suivante de modes de réalisaticn p artioliers faite en relation avec les figures jointes parmi lesquelles les figures 1A et 1B sont des tableaux illustrant un balayage de type zig zag; la figure 2 représente un premier circuit de brassage selon l'art antérieur; la figure 3 représente un secondx circuit de brassage selon l'art antérieur; les figures 4A à 4F repréentent des étapes suessives d'adressage associées au circuit de la figure 3; la figure 5 illustre un module élémentaire de traite- ment selon la présente invention; la figure 6 est un chraxgjramme illustrant le fnction- nement du module élémentaire de la figure 5 pour une séquence particulière d'ordres de sélection; la figure 7 illustre un circuit de brassage selon la présente invention; - la figure 8 illustre une variante du module élémentaire selon la présente invention; et la figure 9 illustre un circuit de brassage selon la présente invention utilisant la variante de la figure 8. La présente invention propose un circuit permettant un ré rdnaeent séquentiel d'un train de données entre un ordre de départ déterminé et un ordre d'arrivée déterminé par itéra- tions successives réalisées dans des modules élémentaires uccs_ sifs. Plus particulièraement, si l'on o rnsidère le balayage zig zag, l'ordre de départ est l'ordre naturel allant de 1 à 16 et l'ordre d'arrivée est l'ordre susmentionné 1, 2, 5, 9, 6.... , 16. Si l'on appelle E la séquence d'entrée et S la séquence de sortie, on pourra utiliser pour passer de E à S un algorithme dit algorithme de tri par bulles c'est-à-dire que pour chaque donneée dans une première série, on- regarde dans la série d'arrivée si cette dcrrne se trouve avant ou après la donnée iUmédiatement suivante. Si elle se trouve avant, elle reste en place; si elle se trouve après, elle est décalée jusqu'à ce qu'un'r dne se trouve après das la série d'arrivée. Ainsi, pour passer de la série E à la série S on passe par les séries inmiaies X1 à X4 lustrées dans le tableau ci-après. E 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 X1 1 2 3 5 6 4 7 9 10 11 8 13 14 12 15 16 X2 1 2 5 6 3 4 9 7 10 11 13 14 8 12 15 16 X3 1 2 5 6 3 9 4 7 10 13 14 11 8 12 15 16 Xi 1 2 5 6 9 3 4 7 10 13 14 11 8 12 15 16 S 1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16 Plus précisment, la série XI est cbtenue à partir de la série de départ E de la façon suivante: les éléients 1 et 2 de la série de départ sant dans cet ordre dans la série d'arrivée. Ils ne sonat doc pas déplacés. De mr l'élment 3 est dans la série S avant l'éléent 4 il reste dorc en plae. Par oantre, l'élément 4 se trouve dans la série S après l'élent 5, il est doc interchangé avec l' éliment 5. De mêne, il se trouve après l'élément 6 il est donc également inter- changé avec 1'élém1ent 6. Par contre cet éléient 4 se trouve avant l'élient 7 il reste doc en place, suivi de 1 'élment 7 et ainsi de suite. L'élémnt suivant est l'élément 7. Le 8 intervient après 9, 10, 11 dans l'ordre d'arrivée mais avant 12; les élé- nEts suivants sont donc 9, 10, 11, 8. 12 intervient après 13 et 14 dans l'odre d'arrivée mais avant 15; les éléments suivants sant dcon 13, 14, 12. Enfin viennent 15 et 16 qui sont dans cet ordre dans la série d'arrivée. Par itératioes s ssives An peut doc passer de la série E à la série S. Dans le oes particulier considéré, il faut prévoir avec l'algorithme décrit quatre étapes inte iai XI, X2, X3 et X. La figure 5 représente un module élémentaire de traite- mlet permettant de mettre en oeuvre l'algcrithme de tri par bulles décrit prcd nt pour passer d'une série à la série suivante. On a désigné par E l'entrée de oe module et par X1 sa sortie. Ce module comprend un registre 20 acticrn au zythme d'une horloge CK correspondant au rythme d'introduction des ées et un circuit de sélection 21 actionné par un signal SFL.l La figure 6 illustre un choegrmT destiné à expli- quer le fonctionnement du circuit de la figure 5. Le signal SEL.1 est un signal binaire, correspondant par exemple à un élément d'une suite de zéros et de uns mâmorisés dans une mmoinre morte. Quand le signal SETl est à bas niveau le registre est actionré et sa sortie est reliée à la sortie X1. Quand le signal SFTEL est à haut niveau, l'entrée E est directment reliée à la sortie Xi, aucun décalage n'étant appliqué au registre. Les deux deznières lignes de la figure 6 représentent les signaux E et X1, le signal X1 étant décalé du signal E d'un temps d'horloge. On retrouve bien dans le signal X1 la série X1 décrite éréEdnent. Pour passer de E à S on pourra utiliser crroe l'illus- tre la figure 7 une suite de modules I à V dont chacun orrespond à un module de la figure 5. Ces modules sont commandéiis par des suites de zéros et de uns mémorisés dans des colonnes d'une ROM 22 comprenant autant de colonnes qu'il y a de modules et autant de lignes qu'il y a de mots données dans un train ou bloc à brasser. COeme il y a dans le ca dgcrit cinq modules, la sortie sera décalée de cinq temps d'horloge par rapport à l'entrée. C'est-à-dire que le temps de latence du circuit selon la présente invention est de 5 alors qu'il était égal au rnmbre d'éléments d'un train de données à brasser soit 16 pour les circuits de l'art antérieur. D'autre part, on s'aperçoit qu'en pratique il existe souvent plusieurs séries d'ordres de commande identiques pour des modules sucrcessifs (les deux dernières dans le cas de la figure 7). On peut alors utiliser des modules élémentaires simplifiés tels que oelui représenté en figure 8, les registres de aes modules étant commandés par la -mme horloge que les registres des Modules identiques du mà sous-groupe. La figure 9 illustre doc wur variante de la figure 7 dans laoelle le module 4 est zr il par un module du type de celui de la figure 8 dont les deux entrées sont n et dont les deux sorties vont ver les deux entrées rnn In d' module du type de celui de la figure 5. Qon voit donc qu'en pratique, la mèmoire ROM desti à mDh-riser les bits d'ordre de sélection est de dimension encore réduite par rapport à la dimension réomdnt représentée. Le temps de laten: reste de 5 comwe prcd-m-net puis- qu'il y a 5 modules mais le temps critique de transit des dcnnées est réduit puisque l'on a supprime un circuit de sélection. Avec un cirait selon la présente invention, pour des blocs de 16 donnaées, on utilisera seulement 5 registres d'un mot mnoire et une ROM ccçprenant quatre fois 16 bits. Pour des blocs 8 X 8, il faudra prévoir 27 registres et l'on montre que par suite d'une optimisation utilisant des circuits simplifiés tels que celui de la figure 8, on a besoin de seulement 15 sélecteurs, c'est-à-dire de mémoriser seulement 15 fois 64 bits (64 = 8 X 8 étant le rxombre de mots dans la série que l'on veut brasser). La capacité de mémorisation de la ROM est dorec de 15 fois 64 = 960 bits à quoi il convient d'ajouter 27 registres d'un mot de 12 bits chacuns. Ces valeurs sont à comparer au 1920 bits de mémoDire du mode de réalisation antérieur à 2 RAM et aux 51 kbits du mode de réalisation antérieur à une RAM. Ainsi, non seulement la présente Invention permet d'cbtenir un brassage réduisant beaucoup le nombre de cases mfmibre néoessaires, mais encore elle utilise des registres qui sont des composants particulièrement fiables et une mémomire ROM de fhaible capacité. La présente invention a été décrite seulement dans le cas particulier du brassage zig zag. Plus généralement, elle s'appliquera à tout brassage de données choisi. C'est seulement pour des brassages très simples, tels que des simples transpo- sitions de matrice que les dispositifs de l'art antérieur peuvent être d'une simplicité équivalente. Un avantage supplmtaire de la présente invention est que, pour une opération de brassage donrée, si l'on veut faire l'pcération de brassage inverse (par exemple passer d'un balayage zig zag à un balayage linraire), la mêe structure optimnise que oelle du type décrit en figure 9 permet avec un contenu différent des ROM de commarde de faire l'opération inverse. En outre, le rnxveau contenu des ROM est le nfme que le premier à des permuta- tions de lignes près. Ainsi, au lieu de prévoir une deuxièm ROM on pourra, en jouant sur la progressicn du pointeur d'une ROM unique, utiliser la mnme mémoire de bits de cmmandLe. De plus, on a décrit prl9,emnt la memorisation des bits de commarxnde dans des RoM, on pourrait utiliser tout autre moyen pour envoyer une suite presélectionnée de bits de commande, par exemple des réseaux logiques programmables (PLA). REVDICATIONS 1. Circuit de brassage de données de type pipeline rcevant des trains successifs de n nmots de donées séquentiels et zrérdonnent dans chaque train les mots de données selon un ocdre prdétein, ceractérisé en ce qu'il comprend: - p (p omman.de binaire, conmcter l'entrée à la sortie. ou bien direc- tement ou bien par l'intermédiaire du regisLtre; et - des moyens pour fournir cycliquement à chacun des p m'oyens d'aiguillage une séquence de n bits de coumnde fixés en fonction dudit crdre prédéterminé. 2. Circuit de brassage de donaées selon la revendi- cation 1, caractérisé en ce que, quand des modules élémentaires successifs sont commanrdés par des séquerces identiques, les noyens d'aiguillage qui les séparent sont supprimés.