Brevet FR2673012A1 — publié le 19920821

PROCEDE ET CIRCUIT POUR TRANSFORMATION COSINUS DISCRETE BIDIMENSIONNELLE La présente invention se rapporte à une transformation cosinus discrète bidimensionnelle, (qui sera désignée par la suite 2-D DCT) pour utilisation dans un système de transmission de données, dans lequel la durée du calcul de la 2-D DCT peut être raccourcie, en obtenant par ce moyen une 2-D DCT rapide. D'une manière générale, en transmission de données, les données devant être transmises sont comprimées dans un émetteur et ensuite les données comprimées sont converties dans le format des données originelles dans un récepteur pour traiter les données. Une telle donnée comprimée est soumise à la transformation et, à cette fin, le procédé le plus largement connu est appelé 2-D DCT. Par exemple, pour une séquence de données bidimensionnelle donnée [Xij :i, j = 0, 1, 2, .., N-ll, la séquence de 2-D DCT E#mn : m, n = 0, 1, 2, ..., N-1 ] est donnée par 4 dans laquelle un facteur d'échelle Np U(m) U(n) peut être négligé par commodité.Alors une forme de 2-D DCT dénormalisée Ymn de la séquence de 2-D DCT est définie comme Par conséquent, il est à noter qu'à partir de la formule (2') ci-dessus que la séquence 2-D DCT dénormalisée est exprimée en termes de N l-D DCT (transformation cosinus discrète unidimensionnelle) en effectuant dans le sens des lignes et, ensuite en effectuant dans le sens des colonnes. C'est-à-dire, qu'à partir de la formule (2'), la 2-D DCT peut être exprimée par la formule (3') comme cela est montré ci-dessous. 4 Ym = N2U(m) U(n) ym ... (3') Par conséquent, afin d'effectuer une DCT (transformation cosinus discrète) pour une donnée numérique bidimensionnelle de NxN basée sur les formules (2') et (3'), un système représenté comme constitué à la figure 1 peut être utilisé. C'est-à-dire que la l-D DCT est effectuée N fois dans le sens des lignes pour la donnée numérique bidimensionnelle de NxN entrée, et les sorties qui en résultent sont alors transposées sous la forme d'une matrice par un transposeur de matrice 2. Ensuite, les sorties résultant du transposeur de matrice 2 sont soumises à N 1-D DCT dans le sens des colonnes, pour obtenir par ce moyen la 2-D DCT résultante de sortie Ymn. Cependant, dans le cas où une 2-D DCT est effectuée pour la donnée numérique bidimensionnelle de NxN dans le procédé décrit ci-dessus, la durée de calcul de la DCT est retardée en raison de l'exécution de 2N 1-D DCT, et en même temps, la construction matérielle (hardware) pour cela devient compliquée, en rendant par cela difficile de réaliser un VLSI (circuit intégré à très grande échelle) à haute densité. C'est-à-dire qu'un circuit 1-D DCT est d'une manière générale composé de nombreux additionneurs et multiplieurs; cependant, l'utilisation d'un grand nombre de l-D DCT inclus dans un circuit implique qu'un grand nombre de multiplieurs doivent être utilisés. Il est par conséquent évident à partir de ce qui précède que si un circuit de 2-D DCT comprend un grand nombre de circuits de 1-D DCT, le temps de calcul est augmenté et la construction du matériel devient compliquée.En outre, puisque la donnée numérique entrée est soumise à une 1-D DCT dans le sens des lignes, et qu'ensuite, les résultats obtenus sont transposés sous la forme de lignes et de colonnes d'une matrice pour être soumis à la 1-D DCT dans le sens des colonnes. Dans ce cas, il y a de grandes difficultés dans la construction du transposeur de matrice sous la forme de matériel (hardware). Cependant, afin d'effectuer la compression des données en temps réel pour une grande quantité de données, une combinaison de DCT rapide est obligatoirement nécessaire, d'une manière préférable, une combinaison spécifique, telle qu'une structure en parallèle avec une vitesse de transformation rapide et une complexité réduite, est requise. En vu de surmonter les problèmes décrits ci-dessus qui sont inhérents au procédé de la figure 1, différents procédés ont été proposés. Un certains nombres d'exemples sont décrits dans "A TWO-DIMENSIONAL FAST COSINE TRANSFORM" par M. A. Hague CIEEE Trans. Acoust., Speech, Signal processing, Volume ASSP-33, pages 1532 à 1539, Décembre 1985], et "A FAST RECURSIVE TWO-DIMENSIONAL COSINE TRANSFORM" par C. Ma [Intelligent Robots and Computer Vision : Septième d'une série, David P. Casasent, Editeur, Pro.SPIE 1002, pages 541 à 548, 1988]. Dans les publications ci-dessus, sont proposés plusieurs voies pour exécuter la 2-D DCT, sans utiliser la l-D DCT. Ainsi, si la 2-D DCT est exécutée dans le procédé ci-dessus, un matériel distinct est requis en ce qui concerne le circuit de 1-D DCT. En outre, pour effectuer la DCT, le nombre de multiplications est réduit d'environ 25 par comparaison avec les procédés classiques. Néanmoins, le temps de calcul de la DCT est encore long, ce qui constitue un problème pour la réalisation d'une DCT rapide. Par conséquent, c'est un objectif de la présente invention que de créer un procédé et un dispositif pour une 2-D DCT rapide dans laquelle la 2-D DCT pour une entrée d'une donnée numérique de NxN est exécutée en termes de N l-D DCT en additionnant et en décalant les données. C'est un autre objectif de la présente invention que de créer un procédé et un dispositif pour une 2-D DCT rapide dans lesquels le nombre de multiplications est réduit, en convertissant une forme de multiplication de la fonction cosinus en une forme de sommation de celle-ci de manière à effectuer la 2-D DCT au moyen de la sommation de l-D DCT. C'est encore un autre objectif de la présente invention que de créer un procédé et un dispositif pour une 2-D DCT rapide dans lesquels la forme de multiplication d'une fonction cosinus est réarrangée en forme de sommation de celle-ci, la donnée numérique réarrangée est soumise à un processus primaire d'addition, N l-D DCT sont exécutées sur le résultat de l'addition primaire, et ensuite, le résultat est soumis à un processus secondaire d'addition. C'est encore un autre objectif de la présente invention que de créer un procédé et un dispositif pour réarranger une donnée numérique NxN en N groupes de données de manière à effectuer la 2-D DCT au moyen de l'exécution de N l-D DCT. C'est encore un autre objectif de la présente invention que de créer un procédé et un dispositif pour une 2-D DCT rapide dans lesquels, N/2 groupes de données de rangs impairs et N/2 groupes de données de rangs pairs issus des N groupes de données réarrangées sont soumis à une addition et une soustraction primaires, une 1-D DCT est effectuée sur le résultat, et la valeur résultante de la 1-D DCT est soumise à une sommation et une soustraction secondaires pour log2N étages. C'est encore un autre objectif de la présente invention que de créer un procédé et un dispositif pour réduire le nombre d'exécutions de la 1-D DCT à N/2 fois dans un circuit de 2-D DCT de NxN, dans lequel lors d'une addition primaire de N/2 groupes de données issus de N groupes de données réarrangées dans un circuit qui effectue une 1-D DCT dans une structure pipeline, les N/2 groupes de données restants sont soumis à une 1-D DCT, et pendant l'exécution de la l-D DCT pour l'addition primaire de N/2 groupes de données, une sommation secondaire des N/2 groupes de données restants est effectuée. Selon un aspect de la présente invention, un dispositif pour effectuer des transformations de fonctions cosinus discrètes rapidement sur une donnée d'entrée bidimensionnelle de NxN, comprend; un circuit pour réarranger les NxN données d'entrée pour qu'elles soient identiques au fond d'une transformation cosinus discrète unidimensionnelle d'une fonction cosinus de manière à transformer une forme de multiplication de la fonction cosinus, la forme de multiplication étant le fond d'une transformation cosinus discrète bidimensionnelle en une forme de sommation; un circuit pour produire les premières N/2 données additionnées en additionnant ensemble les données réarrangées respectives de groupes pair et de groupes impairs parmi les données réarrangées, et pour produire les premières N/2 données soustraites en soustrayant l'un de 11 autre les groupes de données restants; un circuit pour effectuer des transformations cosinus discrètes unidimensionnelles sur les premières données additionnées et les premières données soustraites produites au moyen de la première étape de calcul; et un circuit couplé au circuit de transformation cosinus discrète unidimensionnelle, pour produire des données de transformation cosinus discrète bidimensionnelle en effectuant des sommations et des soustractions sur les sorties des transformations cosinus discrètes unidimensionnelles dans log2N étages papillons, et ensuite en décalant le résultat des sommations et soustractions en multipliant par 1/2. Les caractéristiques et avantages de l'invention ressortiront d'ailleurs de la description qui va suivre à titre d'exemple en référence aux dessins annexés, sur lesquels la figure 1 représente la structure d'un circuit de 2-D DCT classique; les figures 2A et 2B représentent un circuit de 2-D DCT et un circuit de 2-D DCT inverse, respectivement, selon la présente invention; les figures 3A et 3B représentent un format de données réarrangées pour une donnée d'entrée de 8x8 de la figure 2; les figures 4A 4C représentent un premier mode de réalisation d'un circuit de 2-D DCT de 8x8 selon la présente invention; les figures SA à 5C représentent la structure d'un circuit de 2-D DCT inverse de 8x8 selon la présente invention; la figure 6 représente un autre mode de réalisation du premier additionneur et le circuit de l-D DCT des figures 2A et 2B; et les figures 7A à 7C représentent un autre mode de réalisation d'un circuit de 2-D DCT de 8x8 selon la présente invention. En se référant à la figure 2A, une mémoire tampon d'entrée 100 reçoit une entrée de données numériques bidimensionnelles de NxN et une section de réarrangement 200 reçoit la sortie de données de la mémoire tampon d'entrée 100. Afin de transformer la multiplication de fonction cosinus qui constitue le fond de la 2-D DCT, en la sommation de la fonction cosinus, la section de réarrangement 200 réarrange l'entrée de données en N groupes de données de manière à ce que la sommation de fonction cosinus puisse être la même que le fond de la 1-D DCT.Un premier additionneur 300 reçoit la sortie de la section de réarrangement 200 pour produire les données de sommation de même que les données de soustraction pour N/2 groupes de données en additionnant les données des groupes de données de rangs impairs respectifs aux données des groupes de données de rangs pairs adjacents des N groupes de données réarrangées, ou en soustrayant les données des groupes de données de rangs impairs respectifs des données des groupes de données de rangs pairs adjacents des N groupes de données réarrangées. Ensuite, les données de sommation et les données de soustraction de N/2 groupes sont appliquées à une section de l-D DCT 400 qui effectue la 1-D DCT pour produire la donnée de 1-D DCT par rapport aux données de sommation et de soustraction des N/2 groupes de données.Un second additionneur 500 reçoit la sortie de la section de l-D DCT 400 pour produire la donnée de 2-D DCT en effectuant des opérations de sommation, de soustraction et de décalage pour log2N étages. De plus, une mémoire tampon de sortie 600 mémorise en tampon la sortie de la seconde section d'addition 500. En plus, un circuit de DCT inverse bidimensionnelle (mentionnée dans la suite sous la forme 2-D IDCT) montré à la figure 2B a une structure qui est l'inverse, en fonctionnement, du circuit de 2-D DCT de la figure 2A. En se référant aux figures 3A et 3B, il y est montré la procédure de réarrangement de la donnée d'entrée de 8x8 en 8 groupes de données. Après réception de la donnée d'entrée de 8x8 comme cela est montré à la figure 3A, la donnée est réarrangée en 8 groupes pour que la sommation de la fonction cosinus soit la même que le fond de la 1-D DCT, de sorte que la multiplication de la fonction cosinus qui est le fond de la 2-D DCT puisse être transformée en la sommation de la fonction cosinus. Aux figures 4A à 4C, un mode de réalisation d'une DCT de 8x8 est montré dans lequel un premier additionneur 300, (c'est-à-dire les additionneurs 301 à 308) recevant les 8 ensembles de données de groupe réarrangées additionne ou soustrait un ensemble de données de groupe R1a, R3a, R5a, R7a, a, ou d'un, autre ensemble de donnés d'un groupe adjacent R1b, R3b, R5b, R7b pour produire à partir de là les données de sommation et les données de soustraction des deux groupes. La section de l-D DCT 400 (c'est-à-dire, les sections 401 à 408), recevant la sortie du premier additionneur 300 effectue la 1-D DCT pour les 8 groupes d'ensembles de données par rapport aux données de sommation et de soustraction.En outre, le second additionneur 500 recevant les données de DCT issues de la section de 1-D DCT 400 effectue la sommation, l'opération de décalage et la soustraction pour log2N étages pour produire les données de 2-D DCT. Aux figures 4A à 4C, "o" indique un additionneur, les lignes tirettes indiquent des facteurs de transfert "-1", les lignes en traits pleins indiquent des facteurs de transfert unité, et " [ # ] " avec 1/2 indique la multiplication par 1/2 qui est équivalente à une opération de décalage.La figure 4A représente un processus par lequel, parmi les 8 groupes d'ensembles de données réarrangées Xi~, les groupes de rangs impairs et les groupes de données adjacents sont additionnés l'un à l'autre ou l'un de l'autre, et les 1-D DCT sont effectuées pour les données de sommation et de soustraction, pour produire par ce moyen des données de groupe de sommation fpi et des données de groupe de soustraction La figure 4B représente un processus par lequel une sommation secondaire est effectuée sur les données de groupe de sommation fpi et les données de 2-D DCT Ymn sont produite. La figure 4C représente un processus par lequel une sommation secondaire est effectuée sur les données de groupe soustraites gpit et la donnée de 2-D DCT Ymn est produite. Les figures SA à 5C représentant une IDCT de 8x8, montrent un processus inverse de celui de la DCT de 8x8 des figures 4A à 4C. La figure 6, représente une autre structure du premier additionneur 300 et de la section de l-D DCT 400 de la figure 1 et elle montre le fait que, même si l'opération de sommation primaire est effectuée après avoir soumis l'entrée de données bidimensionnelles aux l-D DCT, elle est équivalente à l'opération dans laquelle les l-D DCT sont exécutées après exécution d'une sommation primaire. La figure 7 représente un autre mode de réalisation de la DCT de 8x8, et selon ce dessin, la structure de la section de l-D DCT 400 est réduite en complexité par un facteur de 1/2 en utilisant des multiplexeurs 701, 702 et des démultiplexeurs 801, 802. La présente invention va maintenant être décrite en détail ci-dessous en ce qui concerne son fonctionnement, en se référant aux structures décrites ci-dessus. Selon la présente invention, une 2-D DCT de NxN est exécutée en effectuant une 1-D DCT N fois, de sorte que le nombre des multiplications peut être grandement diminué, et que la 2-D DCT peut être effectuée à une vitesse élevée, en améliorant la régularité et en permettant au système d'être réalisé avec une haute densité. A cette fin, la multiplication de fonctions cosinus en lignes et colonnes du fond de la 2-D DCT doit être transformée en la sommation des fonctions cosinus. En outre, les ensembles de données transformées doivent être réarrangés en N groupes de l-D DCT d'ensembles de données, de sorte que les ensembles de données peuvent être équivalents au fond de la 1-D DCT. Par conséquent, lorsque la section de réarrangement 200 qui reçoit l'entrée de données numériques bidimensionnelles de NxN, transforme la multiplication des fonctions cosinus qui est le fond de la 2-D DCT en la sommation des fonctions cosinus, les ensembles de données d'entrée doivent être réarrangés en N groupes de manière à ce que la sommation des fonctions cosinus puisse être équivalente au fond de la l-D DCT. Ensuite, chacun des N groupes d'ensembles de données réarrangées aura une caractéristique unique, et en fonction de la caractéristique, le premier additionneur 300 effectue la sommation ou la soustraction sur les groupes respectifs. Ainsi, le premier additionneur 300 reçoit N groupes d'ensembles de données pour effectuer la sommation et la soustraction et, en effectuant les calculs, deux ensembles de données sont additionnés ensemble pour N/2 groupes d'ensembles de données. Tandis que, un ensemble de données est soustrait d'un autre ensemble de données pour les N/2 groupes d'ensembles de données restants. Par conséquent, la sortie de données résultante issue du premier additionneur 300 est constituée des données de sommation pour les N/2 premiers groupes et des données de soustraction pour les N/2 groupes restants. Les données de sommation et de soustraction qui sont sorties du premier additionneur 300 sont alors transformées respectivement en données de DCT par la section de l-D DCT 400, tandis que la sortie de la section de l-D DCT 400 est soumise à la soustraction pour log2N étages et décalée par le second additionneur 500, en produisant par ce moyen des données Ymn de 2-D DCT.Par conséquent, parmi les données yrnii de 2-D DCT obtenues en fin de compte, les données de 2-D DCT ayant un rang pair "n" sont la sommation des résultats qui sont obtenus en effectuant la l-D DCT sous la forme de l'addition des deux ensembles de données au moyen de la totalité d'entre eux par la première section d'addition 300, tandis que ceux ayant un rang "n" impair sont la sommation des résultats qui sont obtenus en exécutant la l-D DCT sous la forme de soustraction d'un ensemble de données d'un autre ensemble de données par la première section d'addition 300. Maintenant un processus pour effectuer la 2-D DCT de NxN dans le procédé ci-dessus va être décrit ci-dessous en plus grand détail. En supposant que les séquences de données bidimensionnelles sont représentées par [ xij : i, j = 0, 1, 2, ..., N-1 ] et que les séquences de 2-D DCT sont représentées par 1Ymn : m, n = 0, 1, 2, ..., N-i ] , puis la relation entre relies peut être exprimée par la formule (1) telle qu'elle est montrée ci-dessous. Dans la formule (1), le facteur d'échelle 4 U(m) U(n) peut être négligé et ainsi une forme dénormalisée de Ymn est définie comme Par conséquent, la DCT normalisée Ymn peut être exprimée comme cela est montré ci-dessous, Ymn = N2 U(m) U(n)y# .... (3) Dans ce cas, la multiplication en termes de fonctions cosinus du fond de la 2-D DCT peut être exprimée en une sommation en termes de fonctions cosinus comme cela est montré dans la formule (4) ci-dessous. A partir de la formule (4), la 2-D DCT Ymn de la formule (2) peut être exprimée comme cela est montré dans la formule suivante (5). dans laquelle m, n = 0, 1, 2, ..., N-1. Par commodité, la 2-D DCT peut être divisée en 1-D DCT Amn et Bmn en se basant sur le théorème de l'addition des cosinus, comme cela est montré dans les formules (6) et (7). Par conséquent, Ymn qui est le résultat de la 2-D DCT peut être exprimé par la formule (8) telle que ci-dessous, Ymn = (Amn + Bmn) ~~~~~~ (8) Maintenant la possibilité qu'une DCT de NxN puisse être réalisée en effectuant N l-D DCT indépendantes va être présentée en montrant que Ymn peut être représenté par la sommation de N 1-D DCT au moyen d'un léger réarrangement des données de Amn et Brnii Si les fonds de transformation des formules (6) et (7) sont rendus égaux aux fonds des 1-D DCT, il est nécessaire que [ (2i+l)m + (2j+l)n ] soit exprimé sous la forme de (2i+l) fois un entier. Si cette condition doit être satisfaite, le reste trouvé après division de (2j+1) par 2N doit être égal soit au reste restant après division d'un multipliple de (2i+1) par 2N, soit au reste restant après division de 2N moins un multiple de (2i+l) par 2N. C'est-à-dire que la relation ci-dessus doit satisfaire les formules (9) et (10) montrées ci-dessous. (2j+1) = p(2i+1) modulo 2N ... (9) (2j+1) = p(2i+l) + N modulo 2N ... (10) dans lesquelles p est un entier impair dans la fourchette de 1 à N-1. Par conséquent, les formules (9) et (10) peuvent être exprimées par les formules (11) et (12) telles que montrées ci-dessous, j = pi + p-l modulo N ..... (11) 2 j = N-1-pi ~ P21 modulo N .... (12) 2 dans lesquelles p = 1, 3, 5, ..., N-1. Dans ce qui précède, lorsque la variable i varie de 0 à N-l, les séquences de la variable j qui sont déterminées respectivement par les formules (9) et (10) sont différentes l'une de l'autre. Par conséquent, les données bidimensionnelles de NxN peuvent être séparées en N groupes de données différents qui satisfont les formules (9) et (10). Puis, les fonds de transformation de la formule (5) pour les groupes de données respectifs deviennent égaux aux fonds des 1-D DCT. Par conséquent, afin de distinguer entre les séquences de j produites par les formules (11) et (12) pour p= 1, 3, 5, ..., N-1, les formules (13) et (14) sont définies comme montrées ci-dessous. j(p;a) = pi + P21 modulo N ..... (13) 2 j (pub) = (N-l) - pi - modulo N ... (14) dans lesquelles p = 1, 3, 5, ..., N-l, et i = 0, 1, 2, 3,..., N-1. C'est-à-dire que pour p donné [j (p;a) : i = 0, 1, 2, ..., N-1 ] est une séquence de j produite par la formule (9), tandis que [ j (p;b) : i = 0, 1, 2, ..., N-1] est une séquence de j produite par la formule (10). Par conséquent, les données d'entrée bidimensionnelles et [ xij i, j = 0, 1, 2, ..., N-l ] peuvent être séparées en N données unidimensionnelles distinctes sous la forme de tX~Wia) i = O, 1, 2, ..., N-1] et : i = 0, 1, 2, ..., N-1 ] , de sorte que la formule (5) peut être exprimée dans les termes de la sommation des 1-D DCT. Dans ce cas, si les groupes de données unidimensionnelles sont représentés respectivement par Na et Nbt les formules (15) et (16) peuvent être définies de la manière suivante. Rpa = [Xij(p;a): i=0,1,2 2, .... ,N - 1 j (p; a)=pi+ . . ,N-1, j(p;a)=pi+ p-1 modulo N] 2 ..... (15) Rpb= [Xij;b): i= 0,1, ,N-l, j(p;b)=N-l-pi P2 modulo N] ..... (16) La valeur exacte obtenue en divisant pi + P21 par N 2 doit être connue à partir de ce qui précède, cependant, seul les restes des divisions peuvent être connus à partir des formules (15) et (16). C'est-à-dire, que le produit de la division et le reste de l'exécution de la division doivent être tous les deux connus. Par conséquent, si une nouvelle séquence entière qpl qui représente le produit de la division pi + p-i doit être définie, le "modulo" peut 2 être omis à partir des formules (15) et (16) comme cela est montré dans les formules (17) et (18). RP [Xij(p;a):i= 0,l,2, i = 0,1,2, ~ ~ ~ . ,N-1, j(p;a)=pi+ P21 2 Nq## ] (17) Rpb=[Xij(p;b) i=0rlt2 ~ . . . ,N-1, j(p;b)=N-1-pi P21 dans lesquelles p = 1, 3, 5, ..., N-l. Si les réarrangements de données sont appliqués aux formules (17) et (18), alors Amn et Bmn qui sont exprimés par les formules (7) et (8) peuvent être exprimés par les formules (19) et (20) ci-dessous. dans lesquelles p est un entier impair. En outre, Tpa(m,n), Tpb(m,n), Spa(m,n) et peuvent être exprimés par les formules (21) à (24) comme cela est montré ci-dessous. Par conséquent, Ymn de la formule (8) peut être réécrit comme Ainsi, afin de montrer que Ymn est la sommation de 1-D DCT, il doit être simplement montré que Tpa(m,n), Spa(m,n) et Spb(m,n) peuvent être exprimés en termes de sommation de 1-D DCT. A cette fin, on peut remplacer dans la formule (17) un terme correspondant par la formule (21) pour obtenir la formule (26) comme cela est montré ci-dessous. La formule (26) peut être séparée en deux formules (27) et (28) pour l'état où n est un entier pair et un entier impair comme cela est montré ci-dessous. dans laquelle p est un entier pair dans laquelle n est un entier impair. En outre, on peut remplacer dans la formule (22) un terme par le terme correspondant de la formule (8), pour obtenir la formule (29) comme cela est montré ci-dessous. Cependant, la formule (29) peut être séparée en deux formules (30) et (31) en fonction du cas où n est un entier pair ou un entier impair. dans laquelle p est un entier pair dans laquelle n est un entier impair. De la même façon, si on remplace dans la formule (23) un terme par le terme correspondant de la formule (7), Spa(m,n) peut être exprimé par les formules (32) et (33) comme cela est montré ci-dessous. dans laquelle p est un entier pair dans laquelle n est un entier impair. En outre, si on remplace dans la formule (18) un terme par le terme correspondant de la formule (24), Spb(m,n) peut être exprimé par les formules (34) et (35) comme cela est montré ci-dessous. dans laquelle p est un entier pair dans laquelle n est un entier impair. Ainsi, dans les formules (27) à (35) on remplace les termes correspondant par ceux de la formule (25), alors Ymn peut être exprimé par les formules (36) et (37) telles que montrées ci-dessous. dans laquelle n est un entier pair. dans laquelle n est un entier impair. Cependant, les formules (38) et (39) montrées ci-dessous correspondent à l'une des l-D DCT de la séquence de données d'entrée [ X\j#;a) + Xij#;b) ] pour les m et n donnés. C'est-à-dire que fpi qui montre le résultat de l'exécution d'une l-D DCT en soumettant les données réarrangées à une première addition peut être exprimé par la formule (40) comme cela est montré ci-dessous, et il peut être vu que les formules (38) et (39) correspondent soit à +fp1 ou fpl pour 1 (oh 1 = 0, 1, 2, ..., N-1). Tandis que gpl qui montre le résultat de l'exécution d'une 1-D DCT en soumettant les données réarrangées (réarrangées par la formule (37)) à une première soustraction, peut être exprimé par la formule (41) de la manière suivante. Dans ce cas, il peut être vu que gpl qui est définit par la formule (41) correspond soit à +gpl ou -gp1 comme cela est montré par les formules (42) et (43) ci-dessous pour 1 (où 1 = 0, 1, 2, ..., N-l). Par conséquent, il est à noter que seulement [ Ymn: m,n = 0, 1, 2, .., N-îJ qui correspond à la DCT de NxN est nécessaire, et ceci implique que seulement N l-D DCT sont requises pour le calcul de la 2-D DCT de NxN. Outre les gpl et fpi manipulés comme indiqué ci-dessous, les processus d'exécution des additions et soustractions secondaires vont être considérés dans la suite. Il peut être vu que la 2-D DCT Ymn peut être exprimée par la sommation de fpi et gplcomme cela a été mis en évidence par les formules (36), (37), (40) et (41). Les formes des additions secondaires pour gpl et fpl pour obtenir la valeur de yrnn sont constituées d'étages papillons comme dans le cas des algorithmes de la DFT (transformation de Fourier discrète) et de la DCT (transformation cosinus discrète). Dans le processus décrit ci-dessus, la formule (44) comme montré ci-dessous deviendra valide là où n est un entier pair. cos (2i+1) [m-n (N-P)] # =# cos (2i=1) (m+nP) #... (44) 2N 2N La formule ci-dessus implique que les formules (45) et (46) deviennent valides lorsque le 1 (1 = 0, 1, 2, N-l) est donné. En outre, à partir de ce qui précède, il peut être vu que les formules (47) et (48) deviendront valides là où n est un entier impair. Par conséquent, fpl qui montre le résultat de l'exécution d'une l-D DCT en la soumettant à la première addition dans les formules (45) et (46) apparaît toujours en même temps que +fwp)l, en permettant par ce moyen de former un étage papillon. Tandis que, gpl qui montre le résultat de l'exécution d'une l-D DCT en la soumettant à la première soustraction dans les formules (47) et (48), apparaît toujours en même temps que #g (N-P)(N-1), en permettant par ce moyen de former un étage papillon. Maintenant le processus pour réaliser la 2-D DCT va être décrit en se référant à la figure 2A. D'abord une donnée numérique bidimensionnelle de NxN est mémorisée dans la mémoire tampon d'entrée 100 et ensuite la section de réarrangement 200 réarrange la donnée numérique bidimensionnelle de NxN en N groupes séparés en se basant sur les formules (17) et (18). Ensuite, le premier additionneur 300 effectue les opérations d'addition et de soustraction sous la forme d'un étage papillon afin d'exécuter le calcul de (Xij#;a) + Xi~(p;b)) et ( q#1 (Xij(p;a) Xij(p;b)) en se basant sur les formules (40) et (41). Dans ces conditions, la façon de calculer est telle que décrite ci-dessous.C'est-à-dire que, si n est un entier pair, une opération d'addition des données réarrangées des groupes adjacents est effectuée, tandis que si n est un entier impair, une opération de soustraction de un de l'ensemble de données des groupes adjacents est effectuée. La donnée qui a été soumise aux premières opérations d'addition et de soustraction par le premier additionneur 300 est délivrée au circuit de 1-D DCT dans lequel la donnée est soumise à une l-D DCT. Ici la sortie de celui-ci apparaît sous la forme de fpl montrant le résultat de la l-D DCT pour la première donnée additionnée d'une part, et sous la forme de gpl montrant le résultat de la l-D DCT pour la première donnée soustraite d'autre part. Puis, le second additionneur 500 effectue une opération d'addition secondaire sous la forme d'un étage papillon après réception de fpl et gplavant de sortir Ymn de la 2-D DCT. La sortie du second additionneur 500 est délivrée à la mémoire tampon de sortie 600 dans laquelle la donnée est réarrangée dans une forme convenable appropriée en tant qu'une sortie avant d'être délivrée à un codeur. La donnée de 2-D DCT est à nouveau transformée par inversion comme cela est montré à la figure 2B. c'est-à-dire, que la figure 2B représente la structure d'un circuit de 2-D IDCT (transformation cosinus discrète inverse bidimensionnelle), et la 2-D IDCT est exécutée dans un processus inverse de celui de la 2-D DCT. Maintenant le processus pour effectuer une 2-D DCT sur une donnée numérique bidimensionnelle de 8x8 va être décrit de façon spécifique. D'abord, pour N = 8, Ymn d'une 2-D DCT est exprimé comme montré ci-dessous en se basant sur la formule (5). dans laquelle m, n = 0, 1, 2, 3, 4, 5, 6 et 7. En outre, Amn et Bmn des formules (6) et (7) sont également exprimés comme cela est montré ci-dessous. Dans ce cas, s'il est établi que Amn et B mn montrés ci-dessus sont les mêmes qu'une DCT à 8 points au moyen du processus de réarrangement de données, il serait possible que la 2-D DCT puisse être calculée à partir des 8 1-D DCT distinctes. Par conséquent, si les fonds des transformations pour Amn et B mn doivent être les mêmes que les fonds des transformations unidimensionnelles, [ (2i+l)m + (2j+1)n ] peut être exprimé par un multiple de (2i+l), tandis que si cette condition doit être satisfaite, (2j+1) doit devenir soit un multiple de (2i+l) modulo 2N, soit un multiple de (2i+1) + N modulo 2N.Par conséquent, si une donnée d'entrée bidimensionnelle de 8x8 et divisée en 8 groupes constitués de 8 ensembles de données basés respectivement sur les formules (13) et (14), alors les transformations des formules (6) et (7) deviennent 8 l-D DCT distinctes. Dans le cas de N = 8, le résultat devient p = 1, 3, 5, et 7, et les valeurs de i et j pour diviser la donnée d'entrée de 8x8 en 8 groupes en se basant sur les formules (13) et (14) sont déterminées. Par conséquent, la donnée d'entrée tXij : ij = 0, 1, 2, 3, 4, 5, 6 et 7 ] est divisée en 8 groupes comme cela est montré ci-dessous en se basant sur les formules (17) et (18). Ria = {XOO,X11, X22, X33, X44t X55t X661 X77} Rlb = #Xo7, X16, X25, X34, X43t X52, X611 X70} R3a = {X01 X14, X27, X32, X45, X50, X63 X76} R3b = {X06, X13, X20t X35, X42, X57, X64, X71} Rsa = {X02t X17, X24, X31, X46, X53, X60, X75} Rsb = #xo5, Xlor X23, X36, X41, X54 X67 X72} R7a = (X03, X12t X21, X30, X471 X56t X65t X74} R7b = {X04, X15, X26, X37, X4o, X5l' X62, X73} Tandis que les séquences qpi pour p = 1, 3, 5, 7 sont les suivantes q1i = Co, o, o, o, o, O, O, O} 93i = CO, 0; 0, 1, 1, 2, 2, 2} ssi = Co, 0, 1, 2, 2, 3, 4, 4} q7i = CO, 1, 2, 3, 3, 4, 5, 6} Par conséquent, lorsque la donnée d'entrée de 8x8 est transformée en une 2-D DCT en utilisant 8 1-D DCT comme cela est montré à la figure 3A, la section de réarrangement 200 réarrangent les 8 ensembles de données d'entrée respectifs en 8 groupes comme cela est montré à la figure 3B afin de convertir la forme de multiplication de la fonction cosinus en la forme de sommation. Maintenant, le processus d'exécution d'une 2-D DCT sous la forme de 8 l-D DCT distinctes en utilisant les données réarrangées de 8 groupes va être décrit. Amn et B mn qui sont montrés par les formules (19) et (20) peuvent être exprimés comme montré ci-dessous dans le cas où N = 8. Amn = [T1a(m,n) + Tlb(m,n) + T3a(m,n) + T3b(m,n) + T5a(m,n) + T5b(m,n) + T7a(m,n) + T7b(m,n) ] = = S1a(m,n) + Slb(m,n) + S3a(m,n) + S3b(m,n) + S5a(m,n) + S5#(m,n) + S7a(m,n) + S7b(m,n) ] Dans ce qui précède, Tpa(m, n) i Tpb(m,n), Spa(m,n) et sont sont définis dans les formules (27) et (28), (30) et (31), (32) et (33) et (34) et (35), respectivement. Ainsi, Ymn peut être exprimé comme montré ci-dessous en se basant sur les formules (36) et (37). dans laquelle n est pair et p est un entier impair. dans laquelle n est impair et p est un entier impair. Cependant, dans ce qui précède, et de Y# correspondent à la l-D DCT des 2N séquences d'entrée de données [Xij(p;a) - Xjj#;b ] pour les m, n donnés. De la même façon, et correspondent à la 1-D DCT de la séquence d'entrée de données pour les m et n donnés, de sorte que qpi peut être défini dans la forme de la formule (41). Par conséquent, fpl peut être défini en se basant sur la formule (40). Par conséquent, le premier additionneur 300 produit une première donnée additionnée après exécution de (Xü(p;a) + Xii(p;b) de la formule (40), et il produit la première donnée soustraite après exécution de (-1) qpi (Xij(p;a) Xij(p;b)) de la formule (41). C'est-à-dire que le premier additionneur 300 produit la première donnée additionnée et la première donnée soustraite en utilisant les 8 groupes de données réarrangées. D'une manière plus précise, les additionneurs 301 à 304 produisent la première donnée additionnée en additionnant les données réarrangées du groupe R1 (rial R1b) du groupe R3 (R3a, R3b), du groupe R5 (R5a, R5b), et du groupe R71 (R7af R7b). Dans le même temps, les additionneurs 305 à 308 produisent la première donnée soustraite en effectuant des soustractions l'un de l'autre des ensembles de données réarrangées des groupes R1, R3, R5, R7. Lors de la production des premières données additionnée et soustraite par le premier additionneur 300, la section l-D DCT 400 exécute les 1-D DCT sur les premières données additionnée et soustraite en se basant sur les formules (40) et (41) et en utilisant 8 l-D DCT. D'une manière plus précise, des éléments de l-D DCT 401 à 404 produisent les données fpl après réception de la première donnée additionnée issue des additionneurs 301 à 304. Tandis que des éléments de l-D DCT 405 à 408 produisent les données gpl après réception de la première donnée soustraite des additionneurs 305 à 308. Par conséquent si la séquence de DCT de 8x8 Ymn doit être calculée, seulement fpl et gpl sont nécessaires et ainsi il peut être vu que seulement 8 l-D DCT sont nécessaires pour calculer la DCT de 8x8. Comme cela a été décrit ci-dessus, yrnn est produit sous la forme de la sommation de fpl et gplt et, à ce propos les définitions de yrnn pour un m et un n prédéterminés sont présentées ci-dessous afin que la relation entre yrnn et fpl et gplsoit vue. y30 = 1/2 (f13+f13+f33+f33+f53+f53+f73+f73) y52 = 1/2 (f17+f13+f35+f3 1+f51+f55-f73-f77) y34 = 1/2 (f17+f11-f31-f37-f57-f51-f71+f77) Y26 = 1/2 (0+f14-f34-f30+f50+f54-f74+0) Y41 = 1/2 (g15+g13+g37+g31-g57+g51-g75+g73) y03 = 1/2 2 (g13 1/2 (g13+g13-g37-g37-g51-g51-g75-g75) y35 = 1/2 (0+g12-g32-g34+g54-g56+g76+g70)) y57 = 1/2 (-g14+g12+g35-g30+0 +g52-g76-g74) Dans ce cas, si n est un entier pair, fpl apparaît toujours en même temps que +fN-pl) dans les formules (45) et (46), en faisant ainsi en sorte qu'il soit possible de former un étage papillon.Dans le même temps, si n est un entier impair, gpl apparaît toujours en même temps que dans dansles formules (47) et (48), en faisant ainsi en sorte qu'il soit possible de former un étage papillon. Par conséquent lorsque N = 8, les exemples ci-dessus peuvent être exprimés comme cela est montré ci-dessous. y30 = 1/2 {((f13+f73)+(f13+f73)+(f33+f53)+(f33+f53) ) y52 = 1/2 + (f17+f77) +(f13-f73) -(f35+f55) - (f31-f51) y34 = 1/2 + (f17+f77)+(f11+f71)-(f31+f51)-(f31+f51) } y26 = 1/2 + (0+0) +(f14-f74) - (f34-f54) -(f30+f50) ) } Y41 = 1/2 + (g15+g73)+(g13-g75)+(g37+g51)+(g31-g57) } y03 = 1/2 + (g13-g75)+(g13-g75)-(g37+g51)-(g37+g51) > y35 = 1/2 + (0+g70)+(g12+g76)-(g32+g56) -(g34-g54) g54))} y57 = 1/2 ± (g14+g74) + (g12-g76) + (g36+g52) - (g30+0) } Dans ce contexte, les fonctionnements de l'additionneur secondaire 500 vont être décrits en prenant y30 = 1/2 [ (f13+f73)+(f13+f73)+(f33+f53)+(f33+f53) ] en tant qu'exemple. (f13+f73), (f13+f73), (f33+f53) et (f33+f53)sont réalisés par l'additionneur 501, (f 13+f73 > +(f13+f73) et (f33+f53)+(f33+f53) sont réalisés par l'additionneur 502, et [ (f13+f73) + (f13+f73) + (f33+f53) + (f33+f53) ] est réalisé par l'additionneur 503, tandis que "1/2" est réalisé par le registre à décalage 504. Maintenant la structure des figures 4A à 4C va être décrite. C'est-à-dire, comme cela est montré à la figure 4A, que le premier additionneur 300 produit la première donnée additionnée et la première donnée soustraite afin de délivrer les données réarrangées Xij à la section de 1-D DCT 400. A son tour, la section de l-D DCT 400 produit fpl et en enexécutant la l-D DCT sur les premières données additionnée et soustraite. Dans le même temps, le second additionneur 500 tel que montré à la figure 4B sert à calculer yrnn (avec n étant un entier pair) à partir de fpl produit par la section de 1-D DCT 400, tandis que le second additionneur 500 tel que montré à la figure 4C sert à calculer yrnn (avec n étant un entier impair) à partir de gplZ Le nombre des sommations effectuées par l'additionneur 500 est déterminé par log2N étages. Tandis, que dans le cas de N = 8 comme cela est montré aux figures 4B et 4C, le nombre des additions est de 3 étages. (log28). En outre, la multiplication par 1/2 effectuée par le second additionneur 500 est exécutée sous la même forme que l'opération de décalage, et par conséquent, les multiplications réelles sont exécutées par la section de 1-D DCT 400. La réalisation de la 2-D DCT est décrite ci-dessus, et maintenant le fonctionnement de la transformation inverse va être décrit en se référant aux figures SA à 5C. D'une manière générale, dans l'algorithme de la transformation rapide, le déroulement d'une transformation inverse peut être calculée en prenant le déroulement inverse du déroulement en avant, si le facteur d'échelle n'est pas pris en considération. Cependant, dans le cas où le facteur d'échelle est pris en considération, la transformation inverse doit être effectuée après ajout d'une légère modification. C'est-à-dire, comme cela est montré aux figures 4A à 4C, qu'il y a certains noeuds qui n'ont pas leurs correspondants, en faisant ainsi qu'il est impossible pour le second additionneur 500 de former un étage papillon lors de la réalisation de la 2-D DCT. Par conséquent, si les signaux doivent s'écouler d'une manière inverse lors de l'exécution de la 2-D IDCT, il doit simplement être garanti que la première section de 1-D DCT 350 qui effectue des calculs de manière inverse par rapport à ceux du premier additionneur 500 prenne un double de la valeur du noeud correspondant pour qu'ainsi la valeur de la transformation inverse ne soit pas modifiée. C'est-à-dire qu'il est vu qu'il n'y a pas de corespondant pour les deux noeuds existants entre les lignes f50 et f70 dans le second additionneur 500. Par conséquent, en exécutant la 2-D IDCT, si la première section de l-D IDCT 350 prend un double de la valeur de la ligne, un résultat correct peut être obtenu.De plus, une première section d'opération 450 doit multipliée la Oième entrée par 1/2, lorsque le facteur d'échelle est pris en considération, et ceci est résolu par l'opération de décalage. Cependant, lors de l'exécution de la l-D IDCT pour gplt le facteur 1/2 de la multiplication ci-dessus et le facteur de multiplication 2 pour le noeud peuvent être décalés l'un par rapport à l'autre dans la première section d'opération 450. Dans le cas où les facteurs d'échelle pour Xij doivent être conservés dans la forme d'origine, les valeurs des noeuds doivent être multipliées par 1/2, ou l'entrée yrnn doit être divisée par N2/2. Cependant, en considérant le fait que le calcul concerne un nombre limité de bits, il est plus avantageux d'adopter la multiplication par 1/2. En outre, lors de la réalisation de la 2-D DCT au moyen d'un circuit de densité élevée, le facteur le plus important est de réduire le nombre des multiplications, parce que les multiplieurs occupent une superficie importante dans le circuit intégré. Dans le cas où la 2-D DCT est exécutée en utilisant le procédé des figures 3A à 3B, les N l-D DCT sont requises et par conséquent, si NxN DCT sont exécutés en parallèle, une structure de N 1-D DCT est requise. Les figures 7A à 7C représentent le procédé de réalisation de N/2 1-D DCT en utilisant un multiplexeur 700 et un démultiplexeur 800, pour le cas où une réalisation en parallèle de NxN DCT est prévue de manière structurelle. Comme cela est montré à la figure 3A, le premier additionneur 300 produit une première donnée additionnée et une première donnée soustraite en calculant la donnée préarrangée pour les groupes d'unités respectifs, tandis que la section de l-D DCT 400 effectue la l-D DCT sur les sorties de la première section d'addition 300 pour produire fpl et gpl. Cependant, comme cela est montré à la figure 6, les l-D DCT sont d'abord exécutées sur les données du groupe réarrangées par la section de l-D DCT 400, et ensuite, le résultat de l'exécution des l-D DCT est traité par la première section d'addition 300, en produisant par ce moyen fpl et gpl. C'est-à-dire que, pendant le temps où les données réarrangées des groupes Ria et Rib sont traitées par les additionneurs 301, 302, les l-D DCT sont effectuées sur les données réarrangées des groupes R3a et R3b par les éléments de l-D DCT 403, 404. Ensuite, les mêmes résultats de fpl et gpl peuvent être obtenus même si la première donnée additionnée et la première donnée soustraite des groupes Ria et Rlb produites à partir des additionneurs 301, 302 et la donnée de l-D DCT des groupes R3a et R3b sont produites à partir des éléments de l-D DCT 403, 404 sont traitées par les additionneurs 303, 304. C'est-à-dire, comme cela est montré à la figure 6, que même si l'ordre des réalisations de la première addition et de la l-D DCT pour les données réarrangées des groupes R3a et R3b et les données réarrangées des groupes R7a et R7b sont inversées, les valeurs de fpl et gpl ainsi obtenues sont les mêmes. Par conséquent, comme cela est montré aux figures 7A à 7C, pendant le temps où les additionneurs 311 et 315 traitent les données réarrangées des groupes Ria et Rlb, le multiplexeur 701 sélectionne les données réarrangées des groupes R3a et R3b pour les fournir aux éléments de l-D DCT 411, 412. Dans le même temps, le multiplexeur 702 sélectionne les données réarrangées des groupes R7a et R7b pour les délivrer aux éléments de l-D DCT 413, 414 pendant le temps où les additionneurs 313, 317 traitent les données réarrangées des groupes R5a et R5b. Puis, pendant le temps où les données réarrangées des groupes R la et R lb et les données réarrangées des groupes R5a et R5b sont traitées par la première section d'addition 300, la section de 1-D DCT 400 exécute les 1-D DCT sur les données réarrangées des groupes R3a et R3b et les données réarrangées des groupes R7a et R7b. Ensuite, les multiplexeurs 701 et 702 sélectionnent respectivement les sorties des additionneurs 311, 315 et des additionneurs 313 et 317 et en même temps les démultiplexeurs 801 et 802 sélectionnent respectivement les sorties des éléments 1-D DCT 411, 412, 413 et 414 pour les sortir vers les additionneurs 312, 316 et 314, 318. Par conséquent, pendant le temps où les données des groupes Ria et Rlb et des groupes Rsa et R5b sont soumises à la réalisation de la l-D DCT par la section de l-D DCT 400, les données des groupes R3a et R3b sont traitées par le premier additionneur 300. Ensuite, les résultats sont délivrés au second additionneur 500 où les données sont soumises à la réalisation des sommations et des soustractions sous la forme de log2N étages papillons. Selon la présente invention décrite ci-dessus, lors de la réalisation de la 2-D DCT sur une entrée de données bidimensionnelles de NxN, celle-ci peut être exécutée en effectuant N l-D DCT distinctes et en effectuant des première et seconde sommations sous la forme d'étages papillons. Par conséquent, en réalisant une structure en parallèle du matériel utilisant des multiplexeurs et des démultiplexeurs, seulement N/2 l-D DCT sont nécessaires, et par conséquent le nombre des multiplications peut être grandement réduit, en rendant par ce moyen possible de réaliser une 2-D DCT rapide et un circuit à haute densité. Bien que l'invention ait été particulièrement montrée et décrite en se référant à un mode de réalisation préféré de celle-ci, il sera compris aisément par les personnes expérimentées dans cette technique que des modifications dans la forme et dans des détails peuvent être effectuées sans sortir de l'esprit et du domaine de l'invention. REVENDICATIONS 1. Procédé pour effectuer des transformations de fonctions cosinus discrètes rapidement sur une donnée d'entrée bidimensionnelle de NxN, comprenant les étapes consistant à réarranger les NxN données d'entrée pour qu'elles soient identiques au fond d'une transformation cosinus discrète unidimensionnelle d'une fonction cosinus de manière à transformer une forme de multiplication de ladite fonction cosinus, ladite forme de multiplication étant le fond d'une transformation cosinus discrète bidimensionnelle en une forme de sommation; produire des premières N/2 données additionnées en additionnant ensemble les données réarrangées respectives de groupes pair et de groupes impairs parmi lesdites données réarrangées, et produire des premières N/2 données soustraites en soustrayant l'un de l'autre les groupes de données restants;; effectuer des transformations cosinus discrètes unidimensionnelles sur lesdites premières données additionnées et lesdites premières données soustraites produites au moyen de ladite première étape de calcul; et produire des données de transformation cosinus discrète bidimensionnelle en effectuant des sommations et des soustractions sur lesdites sorties des transformations cosinus discrètes unidimensionnelles dans log2N étages papillons, et ensuite en décalant le résultat des sommations et soustractions. 2. Dispositif pour effectuer des transformations de fonctions cosinus discrètes rapidement sur une donnée d'entrée bidimensionnelle de NxN, comprenant des moyens (200) pour réarranger les NxN données d'entrée pour qu'elles soient identiques au fond d'une transformation cosinus discrète unidimensionnelle d'une fonction cosinus de manière à transformer une forme de multiplication de ladite fonction cosinus, ladite forme de multiplication étant le fond d'une transformation cosinus discrète bidimensionnelle en une forme de sommation; des moyens (300) pour produire des premières N/2 données additionnées en additionnant ensemble les données réarrangées respectives de groupes pair et de groupes impairs parmi lesdites données réarrangées, et pour produire des premières N/2 données soustraites en soustrayant l'un de l'autre les groupes de données restants; ; des moyens (400) pour effectuer des transformations cosinus discrètes unidimensionnelles sur lesdites premières données additionnées et lesdites premières données soustraites produites au moyen de ladite première étape de calcul; et des moyens (500) couplés auxdits moyens (400) de transformation cosinus discrète unidimensionnelle, pour produire des données de transformation cosinus discrète bidimensionnelle en effectuant des sommations et des soustractions sur lesdites sorties des transformations cosinus discrètes unidimensionnelles dans log2N étages papillons, et ensuite en décalant le résultat des sommations et soustractions en multipliant par 1/2.