Brevet FR2645985A1 — publié le 19901019

DESCRIPTION 'CIRCUIT POUR OPERER UNE TRANSFORMATION LINEAIRE DE DONNEES NUMERIQUES". L'invention concerne un circuit pour opérer une transformation linéaire Xj/xj de N données numériques Xj de b bits en N données numériques Xj de c bits, comprenant des moyens d'entrée/sortie respectivement des données Xj et xj et des moyens de calcul de la transformation linéaire Xj/xj. Un tel circuit permet de réaliser des transformations linéaires telles qu'une transformée en cosinus discrète (DCT) ou une transformée en cosinus discrète inverse (IDCT) ou d'autres transformées linéaires discrètes c'est-à-dire où les signaux à traiter sont numérisés. De telles transformées trouvent leur application dans le traitement des images, de la parole, etc. Une transformée de ce genre est connue du document FR-2 596 892. Les transformées linéaires connues mettent en oeuvre des séries d'opérations de multiplication et d'addition. Diverses architectures ont été proposées pour réaliser ces séries d'opérations généralement à base de processeurs d'usage général ou d'opérateurs de conception classique. Ce document de l'art antérieur cité exploite les particularités de certaines opérations a effectuer et définit des opérateurs dédiés qui permettent de disposer d'une architecture globale plus compacte ayant un meilleur rapport performance/prix que les solutions précédentes. Ainsi chaque multiplieur est câblé selon la valeur du coefficient déterminé associé à la branche dans laquelle il se trouve.De même les opérations d'addition/soustraction sont effectuées a l'aide d'additionneurs/soustracteurs précâblés. Un tel circuit utilise des multiplieurs du type parallèle-série qui opèrent en boucle fermée sur plusieurs bits à l'aide d'un accumulateur qui stocke les résultats intermédiaires avant de délivrer le résultat. final de la multiplication. Ce résultat doit être sérialisé à l'issue de chaque multiplication pour opérer avec des additionneurs série. Dans un tel circuit les données numériques entrent et sortent habituellement en mode parallèle et rien n'est indiqué sur la manière d'interfacer un tel circuit avec le monde extérieur. Le problème posé est de réaliser un circuit intégré très économique qui simplifie les chemins suivis par les données à l'intérieur du circuit, en supprimant tout contrôle associé et en adaptant les interfaces entrée/sortie pour optimiser a la fois la densité d'intégration et les échanges des données avec l'extérieur, le calcul devant être effectué avec une grande précision-. La solution à ce problème posé consiste en ce que les moyens de calcul déterminent les données xj en effectuant la totalité du traitement en mode série à l'aide d'opérateurs à 1 bit organisés selon une structure en couches, commandée par une horloge H, une donnée Xj traversant au cours du traitement le même nombre de couches quel que soit le trajet suivi, et les moyens d'entrée/sortie comprenant N modules de sérialisationldésérialisation qui opèrent en entrée la sérialisation des données Xj reçues en parallèle et en sortie la désérialisation des données xj qui sont délivrées en parallèle par le circuit, chaque module comprenant une batterie de 1 registres qui opère en mode parallèle/série, où 1 est égal au plus grand des nombres b ou c, un expanseur de bit de signe qui donne à chaque donnée d'entrée sérialisée Xj une taille prédéterminée expansée sur p bits, liée au nombre de bits nécessaires aux moyens de calcul pour qu'ils opèrent avec une précision de calcul prédéterminée, Le calcul des échantillons transformés xj peut être présenté sous une forme minimisant le nombre d-'opérations à effectuer. Une telle mise en oeuvre universellement connue est appelée papillon et est aussi applicable à beaucoup de transformées. A titre d'exemple, une transformée IDCT monodimensionnelle de huit échantillons ne nécessite plus selon cette mise en oeuvre que 16 multiplications et 30 additions ou soustractions. Selon l'invention toutes les opérations sont faites en bits série c'est-à-dire que les opérateurs ne traitent qu'un bit de leurs opérandes à la fois.Pour toutes les opérations, le bit de poids faible des opérandes est utilisé le premier. Le résultat est aussi généré avec le bit de poids faible en tête. Pour tous les opérateurs du circuit, le temps d'utilisation d'un bit d'une opérande (une période) est égal au temps de génération d'un bit du résultat. Il en résulte que l'on peut directement câbler, à un retard constant près réalise sé par une ou plusieurs bascules, la sortie d'un opérateur à l'entrée du suivant. Ceci amène une grande simplicité matérielle pour le chemin de données et supprime le contrôle asso cle . Pour assurer un transfert efficace des données, à un instant donné, dans chaque batterie de registres circulent I bits pris en succession et continûment dans la suite de bits Xj(LSB) à Xj(MSB), xj-1(LSB) à xj-1(MSB), où les lettres LSB et MSB représentent le bit respectivement le moins et le plus significatif. Pour le chargement et le déchargement externe, chaque batterie qui est commandée par un signal de commande VP, recopie en mode parallèle le contenu de la batterie précédente de sorte qu'une donnée numérique transite successivement de la dernière batterie vers la première batterie, la première batterie étant connectée à un port de sortie et la dernière batterie à un port d'entrée, réalisant ainsi en N cycles les N introductions de données sur le port d'entrée et simultanément la présentation des N résultats précédents sur le port de sortie. On opère sans troncature interne avant que le résultat final soit obtenu avec la précision recherchée. On conserve ainsi toute la précision de calcul et tous les opérateurs possèdent une cadence constante. Pour cela le circuit possède sur chaque entrée un expanseur de bit de signe.L'expanseur comprend une bascule qui stocke le bit de signe de la donnée Xj et un sélecteur qui étend ledit bit de signe pour donner à la donnée Xj le nombre de bits prédéterminé p. L'invention sera mieux comprise à l'aide des figures suivantes qui représentent figure 1 : un schéma d'un circuit selon l'invention figure 2 : un diagramme des temps du fonctionnement du circuit selon l'invention. figure 3 . un schéma d'une batterie de registres R. figure 4 : un schéma représentant les connexions au port d'entrée et au port de sortie pour échanger les données en mode parallèle. A titre d'exemple, la figure t représente un schéma pour opérer la transformée en cosinus discrète inverse avec N=8 échantillons. Le circuit comprend N batteries de registres R1 à R8 à décalage de 1=16 cellules qui servent d'une part à l'introduction des données Xi à X8 de b=12 bits et d'autre part à la sortie des résultats x1 à xi de c=16 bits. L'interface avec l'extérieur se fait en parallèle grâce à ces registres. Les entrées parallèles d'une batterie de registres quelconque Ri sont reliées aux sorties parallèles du registre Ri+1 (à l'exception du dernier). Le port d'entrée 51 est connecté à l'entrée de la batterie de registres Ri et le port de sortie 52 à la sortie de la batterie de registres R1. Les sorties série des batteries sont reliées à des additionneurs à i bit t21 à 124 et à un soustracteur 13 et à des bascules 111 à 116 à travers des sélecteurs 91 à 98 permettant d'aiguiller (commande BS) soit les sorties des batteries R soit des bascules 101 à 108 ayant mémorisé, sur une horloge de commande Hs, le bit de signe des données. On réalise ainsi l'extension de signe nécessaire au fonctionnement de l'ensemble. Le calcul de la transformée linéaire proprement dite est effectué sur les couches Ci à C7. Les données traversent les deux premières couches en deux cycles d'horloge. En aval de ces deux couches une batterie de 16 multiplieurs 311 à 3116 de type série connu (couche 4) effectue les produits des signaux émis par la couche C2 par des coefficients constants codés sur q=lO bits et délivre 16 résultats. La valeur q est choisie en fonction de la précision prédétermi:iée des calculs. Ces 16 résultats sont repris par 3 couches Cs, Cs, C7 successives qui réalisent les combinaisons nécessaires à la transformée linéaire IDCT. Une dernière couche d'additionneurs Ci est utilisée pour réaliser des arrondis.Enfin les résultats xi à xi sont introduits par l'entrée série ES1 à ESg des batteries de registres à travers des cellules de retard (couche C9) 80t à 808. Les moyens de calcul de la transformation linéaire comprennent les couches C2 à Ci. Les moyens d'entrée-sortie comprennent les ports d'entrée Si et de sortie 52, les registres Ri à Ri, les couches Cr et Cg. L'ensemble est commandé par une horloge H qui m'est pas représentée sur la figure 1 pour ne pas alourdir le dessin. Les batteries de registres R sont l'une après l'autre chargées en mode parallèle, sous le contrôle du signal VP (fig. 3), avec les valeurs Xi à Xi. Les b bits occupent sur la figure 4 les positions les plus à droite des l registres des batteries. On présente successivement sur 8 cycles ces valeurs sur le port d'entrée Si. A chaque cycle le registre Ri recopie le contenu du registre Ri+1. Les registres fonctionnent ensuite en sérialiseurs sur 1 cycles sous le contrôle du signal VS. (fig. 3). Compte-tenu des divers étages d'addition/soustraction et de la multiplication par un coefficient de m bits, on doit pouvoir représenter des nombres sur une échelle accrue entre la colonne 2 et la colonne 9.Le fonctionnement de l'ensemble du circuit en mode pipeline impose d'allouer un même nombre de cycles à tous les opérateurs. Afin de maintenir cette cadence unique sur tout le circuit, on aligne à la valeur maximale, soit p bits, la taille des données bien que l'échelle des nombres à représenter passe progressivement de 2b sur la colonne 2 à 2P sur la colonne 9. Pour ce faire, après la sérialisation de b cycles, on sélectionne les bascules 101 à 108, qui sont connectées à l'entrée de chaque batterie sur la connexion propre au bit de signe, et le bit de signe des données est répliqué sur k cycles, ce qui réalise une extension de l'échelle de représentation des données à 2P, avec p=b+k.Après l'ensemble des calculs, pour ne garder que les c bits les plus significatifs, il faut réaliser une opération d'arrondi pour éviter l'erreur systématique par défaut que provoquerait une troncature effectuée sans précaution. Cette étape nécessite une dernière couche Ca d'additionneurs 721 à 728. Sur une entrée d'un tel additionneur, on injecte le nombre à arrondir et sur l'autre un nombre correspondant à la moitié du plus grand nombre susceptible d'être ignoré par la troncature effectuée par la prise en compte des seuls c bits les plus significatifs. Ce nombre est égal à 2P-C-1 et est tres facilement généré. Il suffit par exemple dans une batterie de (p-c-2) registres de placer un 1 dans le registre de poids le plus élevé et de placer des 0 dans tous les autres.Le contenu de cette batterie est utilisé pour effectuer l'opération d'arrondi en mode série. Cette valeur d'arrondi est connue au départ selon la précision désirée. Les résultats traversent les registres 801 à 808 qui réalisent un retard D. A la sortie de ces registres, les poids faibles sont ignorés, et les c poids forts sont introduits par leurs entrées série ESr à ESg dans les batteries de registres Ri à Ri. Les résultats x1 à xi contenus dans les batteries Ri à Ri sont ensuite envoyés sur le port de sortie 52 successivement sur 8 cycles. A chaque cycle le registre Ri recopie le contenu du registre Ri+1. Pour opérer une transformation en cosinus discrète inverse selon la structure dite en papillon représentée sur la figure 1, des opérations d'addition, de soustraction et de multiplication sont à réaliser Après leur chargement, les données d'entrée Xi à Xi sont respectivement contenues dans les batteries de registres Ri à Ri. Dans cet exemple les opérations suivantes sont effectuées La couche C2 comprend Il opérateurs à 1 bit l'additionneur 12t détermine X3+X7 l'additionneur 122 détermine X1+X5 l'additionneur t23 détermine X4+X6 l'additionneur 124 détermine X2+X8 . le soustracteur 13 détermine Xi-Xs . 6cellules à retard 111 à 116 retardent d'une période d'horloge H respectivement les données X7, Xg, Xi, X2t X4, Xi. La couche C3 comprend 12 opérateurs à 1 bit l'additionneur 22 qui additionne la sortie des additionneurs 123 et 124, 11 cellules à retard 21t à 2111 placées après chacun des opérateurs à 1 bit de la couche C2 La couche Cs comprend 16 opérateurs à 1 bit formés par les multiplieurs 311 à 3116. Chaque multiplieur effectue la multiplication de la donnée délivrée par un opérateur de la couche C3 par un coefficient déterminé. Le tableau 1 indique la sortie de l'opérateur et le coefficient qui est traité par le multiplieur concerné. Multiplieur 31i 312 313 314 315 316 317 Opérateur 211 212 213 214 215 216 217 Coefficient -334 98 138 181 181 301 71 318 319 3110 311r 3112 3113 3114 218 219 2110 22 219 211o 21 -464 201 355 213 355 301 163 3115 3116 21s 217 71 201 Tableau 1 L'exemple étant décrit avec une transformée IDCT, les coefficients sont choisis dans une table de cosinus. Ainsi par exemple, la valeur 181 est égale à 256/J2, c'est-à-dire cos fil/4, la valeur maximale 256 représentant cos 0. Les données sur les sorties des multiplieurs sont délivrées aux opérateurs de la couche Cs tel que l'additionneur 421 est connecté aux multiplieurs 311 et 312 l'additionneur 422 est connecté aux multiplieurs 312 et 313 l'additionneur 423 est connecté aux multiplieurs 318 et 3111 l'additionneur 424 est connecté aux multiplieurs 3112 et 3113 .le soustracteur 43i est connecté aux multiplieurs 316(+)et 317(-) .le soustracteur 432 est connecté aux multiplieurs 31s(+)et 31to(-) .le soustracteur 433 est connecté aux multiplieurs 3111(+)et 31rs(-) .le soustracteur 434 est connecté aux multiplieurs 311s(-)et 3lis(+) les deux cellules à retard-41t et 412 retardent les données respectivement des multiplieurs 314 et 315. La couche C6 est connectée à la couche Cs tel que l'additionneur 52t est connecté aux opérateurs 421 et 411 l'additionneur 522 est connecté aux opérateurs 422 et 412 l'additionneur 523 est connecté aux opérateurs 431 et 423 l'additionneur -524 est connecté aux opérateurs 423 et 432 .l'additionneur 525 est connecté aux opérateurs 433 et 434 .lè soustracteur 531 est connecté aux opérateurs 421(-)et 411(+) .le soustracteur 532 est connecté aux opérateurs 412(+)et 422(-) le soustracteur 533 est connecté aux opérateurs 424(-)et 433(+) La couche C7 est connectée à la couche C6 tel que l'additionneur 621 est connecté aux opérateurs 53t et 523 l'additionneur 622 est connecté aux opérateurs 521 et 524 l'additionneur 623 est connecté aux opérateurs 532 et 533 l'additionneur 624 est connecté aux opérateurs 522 et 525 .le soustracteur 63t est connecté aux opérateurs 53t(+) et 523(-) .le soustracteur 632 est connecté aux opérateurs 521(+) et 524(-) .le soustracteur 633 est connecté aux opérateurs 532(+) et 533(-) .le soustracteur 634 est connecté aux opérateurs 522(+) et 525(-) Le résultat de la transformée linéaire se présente à la sortie de la couche C7.Mais seulement c bits de ce résultat doivent être conservés. il est donc nécessaire d'effectuer une opération d'arrondi pour éviter l'erreur systématique par défaut que provoquerait une simple troncature. Pour cela chaque opérateur de la couche C7 est réuni respectivement à un additionneur d'une couche Ci, 72t à 728 dont l'autre entrée reçoit une valeur d'arrondi qui est égale à la moitié de la plus grande valeur susceptible d'être ignorée par la troncature. Une manière de la générer a été décrite précédemment dans un exemple. Le résultat final apparaît sur la couche Ci. Pour que ce résultat puisse être introduit dans les batteries de registres Ri à Ri d'entrée à l'instant optimal, une couche Cg formée uniquement de cellules de retard 80t à 808 permet de retarder les données d'une valeur D de sorte que le premier bit de chaque donnée Xi à Xi se présente exactement à l'instant où le premier registre de chaque batterie est libéré par le transfert série, cet instant correspondant au début du cycle de calcul suivant. Ainsi dans chaque batterie Ri à Ri, les données circulent de manière continue.Les cellules à retard soi à 80e génèrent respectivement les données xl, x2, X4, Xi, x6, x7, xs, xi. Selon le schéma de la figure 1 les données tranformées xi à xi sont introduites chacune en série respectivement dans les batteries de registres Ri à Ri. Tous les registres des additionneurs et des soustracteurs d'une couche, y compris ceux du multiplieur série doivent être remis à zéro au début du calcul opéré par cette couche. Un dispositif à décalage non représenté permet d'effectuer ces remises à zéro. Le déroulement temporel des opérations est décrit sur le diagramme des temps de la figure 2 où le temps se déroule de gauche à droite. On a représenté les opérations qui sont effectuées pour une donnée d'entrée Xj qui est transformée à la fin d'un cycle complet en une donnée Xj. Un cycle complet dure de l'instant t à l'instant tB. Chaque rectangle horizontal non-hachuré symbolise la période d'activité de la couche concernée. Dès qu'une couche a terminé le traitement complet des bits d'une donnée j, elle peut commencer celui relatif à la donnée j+1. Il peut être avantageux, pour des raisons pratiques, de ménager un léger intervalle G de durée r-p entre les deux traitements comme indiqué sur ce chronogramme, mais cela ne change en rien le principe du système. Les opérations en cours dans les différents opérateurs sont complètement pipelinées, la cellule d'une couche traitant un bit des opérandes pendant que celle de la couche amont effectue l'opération précédente sur le bit de poids immédiatement supérieur. Si l'on démarre le décalage des batteries de registres Ri à Ri au temps t, les b bits de Xj passent dans la couche Ci avec le bit le moins significatif LSB en tête. Après les b bits, chaque bit de signe est répliqué sur k cycles. Le signal de commande BS permet d'effectuer cette réplique. La cellule C2 délivre ses premières données au temps t+1 et la cellule C3 au temps t+2. Les données entrent dans les multiplieurs au temps t+2 et sortent à un temps t+2+d où d est la durée d'opération d'un multiplieur dépendant du multiplieur série choisi. Du temps t au temps t+b les batteries de registres se vident de leurs données Xj. -En sortie de C7 le résultat est sur p bits et la partie utile du résultat est constituée par les c bits de poids fort (partie non hachurée). La couche Ci effectue l'arrondi ce qui prend un temps d'horloge pour délivrer les c bits de xi. Les données xj sortent donc de la couche C9 entre. le temps t+r et t+r+c. On constate qu'à chaque période d'horloge comprise entre t et tA, un registre est libéré. On met à profit cette opportunité pour charger dans la batterie de registres, en série à la suite des données Xj, les données Xj-1 calculées au cycle précédent.Pour cela, le résultat xj (qui sera chargé dans les registres au cycle suivant) est retardé d'une durée D afin d'introduire les données Xj dans les batteries de registres R1 à Ri à l'instant t. Lorsque les données xj-1 retardées du cycle précédent ont été chargées sur C périodes d'horloge (du témps t au temps tA selon l'exemple), elles sont déchargées en parallèle (temps tA) sur un coup d'horloge pour la première batterie à l'aide du port de sortie puis de même pour les autres batteries en faisant passer les données d'une batterie dans l'autre. En utilisant les batteries de registres de cette manière on fait l'économie de registres de sortie supplémentaires. Préférentiellement, dans le cas général, le nombre 1 de registres est égal au nombre de bits le plus élevé soit de Xj (b) soit de xj (c). Ainsi au cours d'un même cycle les batteries de registres opèrent simultanément (de t à tA) en sérialiseur des données Xj et en désérialiseur des données Xj-1. Elles permettent aussi dans une autre phase du cycle de calcul (de tA à tB) de sortir en parallèle, pour l'ensemble des batteries, les résultats xj-1 et d'entrer en parallèle, pour l'ensemble des batteries, les données Xj+1. La figure 2 indique qu'au cours de la même période d'horloge, la batterie Ri par exemple se décharge sur le port 52 des données xj-1 et se charge en provenance du port 52 par les données Xj+1. La figure 3 représente le schéma d'une de ces batteries, par exemple la batterie Ri. Elle comprend 1 registres à décalage R11, R12,...RI1 chacun étant muni en entrée d'un sélecteur 301, 302,. ..30î qui permet de faire opérer les registresasoit en mode série soit en mode parallèle. Chaque sélecteur reçoit une commande VS pour déterminer le mode sélectionné pour l'entrée des données parallèle ou série selon l'état logique de la commande VS. L'horloge H entre sur une porte ET 32 qui reçoit la sortie d'une porte OU 33 qui reçoit elle-même la commande VS pour le transfert série et une commande VP pour le transfert parallèle (fig. 2). L'horloge qui contrôle les registres est ainsi validée lorsque l'une des commandes VS ou VP est active. En mode série chaque entrée d'un registre reçoit la sortie du registre précédent. La sortie série Ss des données s'effectue sur le dernier registre. La figure 4 représente le mécanisme de transfert en mode parallèle. Les sorties parallèle Spi des registres d'une batterie sont reliées aux entrées Ep-1,i des registres de la batterie précédente (i indice courant). La batterie de sortie Ri est reliée au port de sortie 52 par les c sorties les plus à gauche sur la figure 4. Dans ce cas, la batterie d'entrée Ri est reliée au port d'entrée 51 par les b entrées les plus à droite sur la figure 4. Cette présentation avec sortie à gauche et entrée à droite est liée directement à l'exemple tel qu'il a été décrit. Cette présentation des données peut être inversée. L'exemple qui vient d'être décrit concerne le calcul de la transformée en cosinus discrète inverse. Bien évidemment d'autres transformées peuvent être déterminées sans sortir du cadre de l'invention. Les interconnexions à réaliser sont alors adaptées en conséquence. REVENDICATIONS 1. Circuit pour opérer une transformation linéaire Xj/xj de N données numériques Xj de b bits en N données numériques xj de c bits, comprenant des moyens d'entrée/sortie respectivement des données X; et xj et des moyens de calcul de la transformation linéaire Xj/xj, caractérisé en ce que, toutes les données étant des entiers signés codés en représentation binaire complément à deux, les moyens de calcul déterminent les données xj en effectuant la totalité du traitement en mode série à l'aide d'opérateurs à 1 bit organisés selon une structure en couches, commandée par une horloge H, une donnée Xj traversant au cours du traitement le même nombre de couches quel que soit le trajet suivi, et les moyens d'entréefsortie comprenant N modules de sérialisation/désérialisation qui opèrent en entrée la sérialisation des données Xj reçues en parallèle et en sortie la désérialisation des données xj qui sont délivrées en parallèle par le circuit, chaque module comprenant une batterie de 1 registres qui opère en mode parallèle/série, où 1 est égal au plus grand des nombres b ou c, un expanseur de bit de signe qui donne à chaque donnée d'entrée sérialisée Xj une taille prédéterminée expansée sur p bits, liée au nombre de bits nécessaires aux moyens de calcul pour qu'ils opèrent avec une précision de calcul prédéterminée. 2. Circuit selon la revendication 1, caractérisé en ce que les opérateurs à 1 bit comprennent des additionneurs, des soustracteurs, des multiplieurs et des cellules à retard unitaire. 3. Circuit selon une des revendications 1 ou 2 caractérisé en ce que l'expanseur de bit de signe comprend une bascule qui stocke le bit de signe de la donnée Xj et un sélecteur qui étend ledit bit de signe pour donner à la donnée Xj le nombre de bits prédéterminé p. 4. Circuit selon les revendications 1 à 3 caractérisé en ce que à un instant donné, dans chaque batterie de registres circulent 1 bits pris en succession et continûment dans la suite de bits Xj(LSB) à Xj(MSB), xj-1(LSB) à (MSB) où les lettres LSB et MSB représentent le bit respectivement le moins et le plus significatif. 5. Circuit selon la revendication 4 caractérisé ce que chaque batterie qui est commandée par un signal de commande VP, recopie en mode parallèle le contenu de la batterie précédente de sorte qu'une donnée numérique transite successivement de la dernière batterie vers la première batterie, la première batterie étant connectée à un port de sortie et la dernière batterie à un port d'entrée, réalisant ainsi en N cycles les N introductions de données sur le port d'entrée et simultanément la présentation des N résultats précédents sur le port de sortie. 6 Circuit selon la revendication 5 caractérisé en ce que le port d'entrée et le port de sortie sont reliés à un seul bus d'entréeisortie; un étage de validation étant placé en sortie de la batterie Ri pour contrôler la sortie des données sur le bus.