Brevet FR2596892A1 — publié le 19871009

Circuit pour effectuer une transformation linéaire sur un La présente invention a pour objet un circuit pour effectuer une transformation linéaire sur un signal numérique 5 composé de N échantillons numériques, o N est un nombre entier. L'invention trouve notamment une application dans le traitement des signaux numériques, par exemple les signaux d'image ou de parole, en vue du codage de ces signaux avant leur émission sur une Ligne de transmission. Dans ces applications, on utilise différents types de transformation linéaire, tels que par exemple la transformée de Fourier discrète, la transformée en cosinus discrète, la transformé en sinus discrète, la transformée de Hadamard discrète, ou autres. Ces transformées sont dites "discrètes" par 15 référence au caractère numérique du signal traité. La transformation linéaire appliquée à un signal numérique de N échantillons est représentée classiquement par un graphe dans lequel les branches représentent une opération de multiplication et les noeuds une opération d'addition ou de 20 soustraction. De tels graphes sont décrits, pour une transformation en cosinus discrète, dans les documents suivants: - demande de brevet français n 85 15649 déposée le 22 octobre 1985, - "A fast computational algorithm for the discrete cosine transform" de W.H. CHEN et aI, IEEE Transactions on Communication, vol COM-25, nO9, sept. 1977, pages 1004 à 1009, - "A high FDCT processor for real-time processing of NTSC color TV signal" de A. JALALI et aL, IEEE Transactions on 30 Electromagnetic Compatibility, vol. EMC-24, nO2, mai 1982, pages 278 à 286, - brevet US-4 385 363. La réalisation pratique d'un circuit fondé sur un graphe de transformation linéaire se heurte à deux problèmes : :: : : À: l:::: : :: D;: 0: ::: X : : 0 \ : A: : : :: 1 0 :::::: :: - i 0 15 ::: ::::::: : 0: 0::: 7 0 20 ::::: :: : :,. ::::: : X: :: : -:: V :::: :::::: 0 : : D:: :: : :;::: : : ::: f -- 35 : 'à 0:::: :.: :: ::: ::0: principaux, qui sont, d'une part, le volume des calculs à réaliser et, d'autre part, un flot de données très compliquées entre les différents étages du graphe, à cause de la complexité de ce graphe. De nombreux travaux ont déjà été réalisés sur la simplification des algorithmes de transformation, c'est-à-dire sur les graphes, par réduction du nombre d'opérations de multiplication, afin de diminuer le débit de données. En effet, cette réduction est souhaitée, car les muttiplieurs sont les éléments coûteux du circuit, aussi bien en ce qui concerne leur prix, que leur surface ou leur consommation. Le nomre de multiplieurs est donc réduit au maximum en affectant à chaque multiplieur les calculs de plusieurs branches du graphe, de façon à obtenir un taux d'utilisation maximal de chacun de ces multiplieurs. On connaÂt deux types de circuit pour La réalisation d'une transformation linéaire, notamment une transformation en cosinus discrète ou une transformation de Fourier discrète. Une première architecture connue consiste à utiliser un grand nombre de microprocesseurs de traitement de signal travaillant en parallèle. L'autre architecture connue consiste à utiliser des multiplieurs et des additionneurs standards reliés entre eux. Un tel circuit est décrit notamment dans le brevet US-4 385 363 déjà cité. Il s'agit, pour ces deux architectures, de réaliser un assemblage de circuit intégré. On a également déjà proposé de réaliser un circuit de transformation linéaire sous la forme d'un circuit intégré spécifique comprenant plusieurs multiplieurs travaillant en parallèle. Ces multiplieurs ne sont pas spécialisés, c'est-à-dire qu'ils peuvent multiplier entre eux deux nombres quelconques. Les circuits de l'art antérieur présentent l'inconvénient de n'utiliser que des multiplieurs et des additionneurs standards, ce qui ne permet pas de prendre en compte les caractéristiques spécifiques du graphe de la transformation que l'on désire réaliser. Cet écart entre l'architecture des circuits de transformation linéaire et La structure de l'algorithme représenté par le graphe ne permet pas d'optimiser le traitement. Le but de l'invention est de supprimer Les 5 inconvénients, notamment le faible rapport performance à prix, des circuits selon l'art antérieur. Ce but est atteint par un circuit pour la réalisation d'une transformation linéaire dont l'architecture est calquée sur celle du graphe de La transformation. A l'encontre des circuits connus dans Lesquels Les multiplieurs et les additionneurs sont des circuits standards, pouvant multiplier ou additionner deux opérandes quelconques, on utilise dans le circuit de l'invention des multiplieurs et -es additionneurs dédiés. Plus précisément, à chaque branche du graphe Je a transformation correspond un multiplieur spécifique, et de ànme chaque noeud du graphe de la transformation correspond un additionneur spécifique. Ainsi, chaque muLtiptieur dOjit multiplier deux opérandes dont l'un est fixe et représente lD 20 poids de la branche du graphe associée. De même, chaque additionneur est conçu pour ne réaliser qu'une seule opération parmi l'addition ou la soustraction. L'invention a donc pour objet un circuit pour effectuzune transformation linéaire sur un signal numérique composé de N 25 échantillons, o N est un nombre entier, ledit circuit comprenant une suite d'étages réalisant des opérations d'addition et/ou de multiplication suivant un graphe de transformation linéaire déterminé, ledit graphe comprenant des branches représentant chacune une opération de multiplication entre un opérande 30 variable et un coefficient déterminé, et des noeuds représentant chacun une addition ou une soustraction entre deux opérandes variables, ledit circuit étant caractérisé en ce qu'il comprend un multiplieur associé à chaque branche, ce multiplieur étant câblé selon la valeur du coefficient déterminé associé a La 35 branche, et un additionneur pour chaque noeud, chaque q additionneur étant ciblé seton La nature de l'opération, addition ou soustraction, associée à ce noeud. De manière préférée, le circuit de l'invention est réalisé sous la forme d'un circuit intégré unique. Le circuit de l'invention présente notamment l'avantage, par rapport aux circuits connus, d'une puissance de calcul supérieure grâce au parallélisme entre son architecture et la structure du graphe de la transformation linéaire qu'ilt réalise. Ceci permet également, dans une version intégrée, 10 d'optimiser le coût en diminuant la surface et le nombre de circuits utilisés, la puissance consommée et le coût du développement. La fiabilité du circuit s'en trouve par ailleurs accrue. L'utilisation d'autant d'opérateurs que de noeuds et de 15 branches du graphe permet d'obtenir dans le circuit un flot de données régulier et sans aiguillage. De plus, chaque multiplieur étant associé à une seule branche, un de ses opérandes est constant. Dans le cas d'une transformation en cosinus discrète, cette opérande constant est un cosinus ou un sinus. Le fait qu'un 20 opérateur soit constant permet de spécialiser chaque multiplieur. On va maintenant décrire, à titre d'exemple ilLustratif mais non limitatif, un mode de réalisation d'un circuit de transformation linéaire conforme à l'invention. A titre d'exemple, on décrit un circuit réalisant la 25 transformée en cosinus discrète en temps réel pour une image organisée en pavés de 16x16 pixels. De manière connue, le débit de calcul est optimisé grâce à une structure de type "pipe line" et dans lequel le nombre d'opérations maximal que doit subir un échantillon de 30 données est minimal. On minimise ainsi La quantité de mémorisations ou de regitres tampons utilisés. Le graphe de transformation en cosinus discrète décrite dans la demande de brevet français nO 85 15649, déjà citée, et qui porte sur la transformation d'une ligne ou d'une colonne de 35 16 pixels (figure 4a à 4c) est de ce point de vue particulièrement intéressante. Le circuit de transformation en cosinus discrète d'un pavé de 16x16 pixels est réalisé sous la forme d'un seul circuit intégré comprenant les modules suivants: - un opérateur de calcul de la transformation en cosinus discrète d'une ligne d'un pavé de 16x16 pixels, - un opératuer de calcul de la transformation en cosinus discrète d'une colonne d'un pavé de 16x16 pixels, - un tableau de registre de stockage et de transposition qui sert 10 à mémoriser les coefficients de transformation en cosinus discrète ligne de tout le pave avant d'attaquer les calcuts de transformation en cosinus discrète colonne. Pour cela les différents coefficients qui arrivent ligne après ligne doivent être réarrangés par colonne. L'utilisation d'un tableau de 15 registre avec décalage horizontal et vertical et de multiplexeurs d'entrée et de sortie permet de n'employer qu'un seul tableau de mémorisation, - un tableau de registre réalisant la conversion de 16 pixels reçus en séquence et codés en parallèle, en 16 pixels délivré 20 bit à bit, en parallèle, - un tableau de registre qui réalise la conversion inverse en sortie. Les opérateurs de calcul de la transformée en cosinus discrète d'une ligne ou d'une colonne sont chacun conforme au 25 graphe représenté dans la demande de brevet français déjà citée. Chacun de ces opérateurs comprend 44 multiplieurs du type parallèle-série et 56 additionneurs de type série. Les multiplieurs parallèle-série travaillent avec des multiplicateurs codés en code complément à 2 et sont délivrés 30 avec le bit le moins significatif (LSB) en tête. Pour chaque multiplieur, le multiplicande qui représente un coefficient en cosinus ou en sinus est positif et câblé dans un additionneur de type "Manchester Carry Chain" modifié, pour prendre en compte le fait que ce multiplicande est fixe. Outre l'opérateur de calcul proprement dit, chaque 15 multtipLieur comprend un registre d'accumulation et de décalage, et un registre tampon pour délivrer à L'étage de calcul suivant dans Le graphe Les données bit à bit. Ce registre de type parallèle-série comprend de plus un inverseur permettant de fournir à l'étage suivant Le résultat avec Le signe adéquat. Les additionneurs sont de type série et travailLent également sur des opérandes codés en code complément à 2. Chaque additionneur est ciblé de manière à réaliser entre les deux opérandes l'opération souhaitée, addition ou soustraction. Des registres tampon supplémentaires sont utiliséspour conserver Les informations qui sont inchangées entre deux noeuds. Le demandeur a réalisé un circuit intégré pour la transformée en cosinus discrète décrite ci-dessus. Ce circuit comporte 80 000 transistors sur une puce de 49 mm. Ce circuit est réalisé dans une technologie CMOS à 2 microns avec deux niveaux de métalLisation. La transformée en cosinus discrète d'un pavé de 16x16 pixels, codés chacun sur 8 bits, est réalisée en temps réel à une fréquence de 16 Mégahertz et avec une précision interne des calculs sur 14 bits. REVENDICATIONS 1. Circuit pour effectuer une transformation linéaire sur un signal numérique composé de N échantillons, o N est un nombre entier, ledit circuit comprenant une suite d'étages 5 réalisant chacun des opérations d'addition et/ou de multiplication suivant un graphe de transformation linëaire déterminé, ledit graphe comprenant des branches représentant chacune une opération de multiplication entre un opérande variable et un coefficient déterminé, et des noeuds représertant 10 chacun une opération d'addition ou de soustraction entre deux opérandes varibles, ledit circuit étant caractérisé en ce qu'i. comprend un multiplieur pour chaque branche, ledit multiptieur étant câblé selon la valeur du coefficient déterminé associe & ladite branche, et un additionneur pour chaque noeud, chaque 15 additionneur étant ciblé selon la nature de l'opération, dditin ou soustraction, associée audit noeud. 2. Circuit selon la revendication 1, caractérisé e-n C qu'il est réalisé sous la forme d'un circuit intégré. 3. Circuit selon l'une quelconque des revendications 20 et 2, caractérisé en ce qu'il comporte en outre, pour cacLe branche du graphe représentant l'opération identité, un regs tampon pour mémoriser l'opérande variable transmis du rnoeud c ladite branche prend son origine vers le noeud o ladite brancraboutit.