FR 2582424 A1 19861128 FR 8507717 A 19850522 82424 CIRCUIT DE CALCUL RAPIDE DE LA TRANSFORMEE EN COSINUS, DIRECTE OU INVERSE, D'UN SIGNAL DISCRET La présente invention a pour objets un cir- cuit de calcul rapide de la transformée en cosinus d'un signal discret et un circuit de calcul rapide de la transformée en cosinus inverse d'un signal discret. Ces transformées sont utilisées notamment dans le traitement des signaux d'images numériques, et en par- ticulier pour le codage et le décodage des images de haute résolution. L'invention concerne les transfor- mées en cosinus discrète, directe ou inverse, dans lesquelles le signal à traiter est représenté par N n points. N est de la forme 2, o n est un entier. De manière générale, la transformée en cosi- nus d'une suite (xi),O Si% N-1, représentant le signal discrétisé à traiter, en une suite (Xi),O Xi 4N-1 est obtenue par une suite d'opérateurs, chaque opérateur recevant de l'opérateur précédent un ensemble de N points et délivrant à l'opérateur suivant un ensemble de N points qui s'obtiennent à partir des points reçus en entrée par des opérations mathématiques simples. Ces opérations mathématiques sont essentiellement des additions et des multiplications auxquelles peuvent s'ajouter éventuellement une permutation. Dans la présente invention, le circuit de calcul de la transformée en cosinus comporte une suite d'étages, chaque étage réalisant un opérateur et fai- sant apparaître N nombres intermédiaires, chacun étant une combinaison linéaire d'au plus deux nombres de l'étage précédent. Chaque opérateur peut être représenté ma- thématiquement par une matrice de taille NxN. Le cir- cuit de la transformée en cosinus est alors défini par un produit de matrices. Dans le cas o ces matrices sont orthogonales, elles sont facilement inversi- 82424 bles: en effet, leur inverse est égale, éventuelle- ment à un facteur multiplicatif près, à leur transpo- sée. Le circuit de la transformée inverse en cosinus est alors défini par le produit des matrices transpo- sées, prises dans l'ordre inverse de celui du produit des matrices de la transformée directe. Dans le circuit de l'invention, les matrices de la transformée directe ne sont pas orthogonales. Cependant, le produit de chaque matrice par sa trans- posée est une matrice diagonale, et on constate que la transformation inverse est définie par le produit des- dites matrices transposées, effectué dans l'ordre in- verse du produit des matrices de la transformée direc- te, multiplié par un coefficient égal à 2. Le circuit de la transformée inverse s'obtient ainsi simplement en inversant l'ordre des étages du circuit de la transformée directe, le coefficient N étant soit in- clus dans l'un des étages multiplicatifs de la trans- formée directe soit obtenu au moyen d'un étage multi- plicatif supplémentaire. Un étage additif de la forme a+b, définit la valeur d'un point de sortie comme la somme ou la dif- férence des valeurs de deux points d'entrée. Un étage multiplicatif de la forme o.a+p.b, associe à chaque point de sortie la somme, ou la différence, de la va- leur de deux points d'entrée affectés de coefficients prédéterminés a et p. Cet étage peut être muni de moyens pour échanger les coefficients o et P de maniè- re à produire "a+Pb ou pa+&b. L'opérateur d'un étage peut ne pas s'appli- quer à tous les points d'entrée; la valeur de cer- tains points de sortie est alors simplement égale à la valeur d'un point d'entrée ou à son opposé. Un tel opérateur est dit à état transparent. Le circuit 74181 de Texas Instruments est un exemple d'un additionneur- soustracteur à état transparent. 82424 Sur le plan pratique, un étage additif com- porte au moins un additionneur-soustracteur. Un étage multiplicatif est plus complexe puisqu'il requiert au moins un multiplieur avec accumulateur ou un multi- plieur avec un additionneur-soustracteur. Ces cir- cuits doivent être rapides pour traiter en temps réel des signaux d'images tels que des signaux vidéo. Ce sont des circuits onéreux. Le nombre d'additionneur-soustracteurs et de multiplieurs d'un circuit de calcul rapide de la transformée en cosinus est donc un critère particuliè- rement important dans le domaine de l'invention. IL faut par ailleurs noter que le coQt d'un multiplieur est notablement plus important que Le coût d'un addi- tionneur et que la diminution du nombre d'étages mul- tiplicatifs dans le circuit est particulièrement re- cherchée. On connait un procédé de calcul rapide de la transformée en cosinus par l'article "A fast computa- tional algorithm for the discrete cosine transform" de W.H. CHEN et ai paru dans IEEE Transactions on Commu- nications, vol.25, n 9, sept 1977, pages 1004 à 1009. Dans cet article, le procédé de calcul rapi- de de la transformée en cosinus est défini par une matrice [AN] égale à un produit de matrices de taille NxN. Chaque matrice représente un opérateur et corres- pond à un étage du circuit. La matrice [ANi est égale à; AN/2 PNI. - B N [Na [: RN/21 [N o PN est une matrice de permutation NxN, le bloc 82424 [AN/21 est la matrice correspondant à la transformée en cosinus d'un ensemble de N/2 points, le bloc [RN/2] est un produit de 2n-3 matrices, o n=log2N, et LBN] est une matrice dont les termes situés sur les deux diagonales sont égaux à +1, les autres termes étant nu Ls. Les 2n-3 matrices se décomposent en n-1 ma- trices multiplicatives et n-2 matrices additives. Les matrices additives sont celles dans lesquelles les coefficients non nuls sont égaux à +1. Les matrices multiplicatives comportent des termes en sinus ou en cosinus. Le circuit de transformée en cosinus décrit dans cet article comprend donc n-1 étages multiplica- tifs et n-1 étages additifs, en tenant compte de t'étage correspondant à la matrice -[BN. On ne compte pas d'étage pour la matrice de permutation PN qui ne constitue pas un calcul proprement dit. Le circuit connu de calcul rapide de la transformée en cosinus qui vient d'être décrit a été légèrement modifié pour permettre un traitement pipe- line. Ces modifications consistent essentiellement à retarder d'un ou plusieurs étages le calcul effectué sur certains points de l'ensemble des N points traités et à prévoir des opérateurs à 4 entrées. Ceci permet de faire travailler en parallèle tous les étages du circuit mettant en oeuvre le procédé. On pourra se reporter à -l'article "A high- speed FDCT processor for real-time processing of NTSC color TV signal",de A. JALALI et K.R. RAO paru dans IEEE Transactions on Electromagnetic Compatibility, vol.24, n 2, mai 1982, pages 278 à 286 pour une des- cription plus détaillée de ce circuit. L'invention a pour objet un circuit de cal- cuL rapide de la transformée en cosinus comportant un 82424 nombre d'étages inférieur au nombre d'étages des cir- *uits connus. Le gain d'étages dans Le circuit de L'invention porte principalement sur Les étages multi- pticatifs. Ceci est important du point de vue économi- que car, ainsi qu'on L'a souligné plus haut, le prix d'un multiplieur est particulièrement éLevé. De manière précise, l'invention a pour objet un circuit de calcul rapide de La transformée en cosi- nus (X:),0.i 15, d'un signal discrétisé défini par une suite (xi),O Si 415, ledit circuit comprenant en série une pluralité d'étages, chaque étage comportant 16 entrées et 16 sorties, ledit circuit étant caracté- risé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage d'addition, recevant la suite (xi),0 (i Z15, un deuxième étage d'addition, un premier étage de multiplication, un troisième étage d'addition et un deuxième étage de multiplication, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués sur chaque entrée. L'invention a également pour objet un cir- cuit de calcul rapide de la transformée en cosinus (Xi),O Xi 431, d'un signal discrétisé défini par une suite (x),0. une pluralité d'étages, chaque étage comportant 32 en- trées et 32 sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages sui- vants: un premier étage d'addition, un deuxième étage d'addition, un troisième étage d'addition, un premier étage de multiplication, un deuxième étage de multi- plication, un quatrième étage d'addition et un troi- sième étage de multiplication, le signal délivré sur chaque sortie de chaque étage étant obtenu par combi- naison linéaire d'au plus deux signaux appliqués sur chaque entrée. 82424 De manière préférée, le circuit de calcul rapide de la transformée en cosinus (Xi),0 si 4 N-1, d'un signal discrétisé défini par une suite (xi), 0 si \N-1, o N=2n et n est un nombre entier pair supérieur ou égal à 6, comprend une pluralité d'étages ayant chacun N entrées et N sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage d'addition, un ensemble d'étages, un deuxième étage d'addition et un étage de multiplication, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages comportant les mêmes étages en nombre, en ordre et en type, que ceux du circuit de N calcul de la transformée en cosinus d'un ensemble de N points. Le circuit se construit donc par récurrence en partant du circuit correspondant à N=16, puis en ajoutant deux étages d'addition et un étage de multi- plication à chaque fois que l'on multiplie par 4 la taille du signal à traiter. De manière préférée, le circuit de calcul rapide de la transformée en cosinus (Xi),O Xi 4 N-1, d'un signal discrétisé défini par une suite (xi),O, pair supérieur ou égal à 7, comprend une pluralité d'étages ayant chacun N entrées et N sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage d'ad- dition, un ensemble d'étages, un deuxième étage d'ad- dition et un étage de multiplication, le signal déli- vré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages comportant les mê- mes étages en nombre, en ordre et en type, que ceux du 82424 circuit de calcul de la transformée en cosinus d'un ensemble de points. Le circuit se construit par récurrence de la même manière que dans le cas précédent, Le point de départ étant ici constitué du circuit correspondant à N=32. L'invention a enfin pour objet un circuit comprenant un premier étage d'addition et un ensemble d'étages, ledit premier étage recevant la suite (x),0 étant composé d'un demi-étage supérieur et d'un demi- étage inférieur, les demi-étages d'un même étage étant du même type, lesdits demi-étages supérieurs étant re- liés en série, le premier demi-étage supérieur rece- O N vant la première suite (x.),0 4j4 N-1 et le dernier demi-étage supérieur délivrant la suite N (X2q),O q4 N-1, des composantes d'indice pair de la transformée en cosinus, lesdits demi-étages infé- rieurs étant reliés en série, le premier demi-étage inférieur recevant la seconde suite (Yj),O 1) - la suite des demi-étages supérieurs consti- tue un circuit de transformée en cosinus N pour 2 points, 2) - la suite des demi-étages inférieurs com- prend dans l'ordre: a) un premier demi-étage inférieur d'addition déli- vrant une troisième suite (x3),O 82424 x3j=Y4+2+y4j +1 une quatrième suite (x j),0 - 1, et une cinquième suite (x2j)0 j -1 o xj=Y424j+l2 -Y4+' b) un ensemble de demi-étages inférieurs dont l'ordre et la nature des étages sont ceux d'un circuit de N transformée en cosinus pour une suite de N points, Ledit ensemble délivrant une sixième suite (a2q+1), 0 q N-1, égale aux parties réelles des composantes d'indice impair de la transformée de Fourier d'ordre-2 de la quatrième suite, une septiè- me suite (A2q+1),'0 q 4--1, égale aux parties imagi- naires des composantes d'indice impair de la trans- formée d'ordre N de Fourier de la quatrième suite, une huitième suite ( 2q+1).0 q N-1, égale aux composantes d'indice impair de La transformée en si- N nus d'ordre N de la cinquième suite, une neuvième suite (y2q+1),0 Nqi -1 égale aux composantes d'in- N dice impair de la transformée en cosinus d'ordre T de la troisième suite, c) un deuxième demi-étage inférieur d'addition pour délivrer les suites (2q+1+2q+1 q -1 (O(),0 4-qN d) un demi-étage inférieur de multiplication déLi- vrant la suite (X2j+i), 0 4j -1 des composantes d'indice impair de la transformée en cosinus d'ordre N de la suite (x.), O j 4N-1. L'invention a également pour objet un cir- cuit de calcul rapide de la transformée inverse en cosinus d'un signal discret. Ce circuit s'obtient ai- sément à partir du circuit de la transformée directe. On constate en effet que la suite des étages du cir- cuit de la transformée directe, prisedans l'ordre in- verse de celle de la transformée directe, constitue, à 82424 un facteur multiplicatif près égal à, un circuit de transformée inverse en cosinus. La démonstration de cette propriété, bien que ne présentant mathématique- ment aucune difficulté, sort du cadre de cette des- cription. Cette démonstration repose sur le fait que le produit de la matrice associée à chaque étage de la transformée directe par sa transposée est égale à une matrice diagonale. Le coefficient multiplicatif - peut N être intégré dans l'un des étages multiplicatifs de la transformée directe; il peut aussi être pris en comp- te sous la forme d'un étage multiplicatif supplémen- taire, qui peut être par exemple en position termina- le. De par sa structure analogue à celle du circuit de la transformée directe, il apparait à l'évidence que le circuit de la transformée inverse peut être construit par récurrence pour des valeurs de N successives. Les coefficients de la matrice associée à un étage de la transformée directe sont en général con- tenusdans une mémoire morte. Cette mémoire ne peut pas être utilisée pour l'étage correspondant de la trans- formée inverse, sauf si des moyens sont prévus pour modifier l'adressage de la mémoire afin d'échanger les lignes et les colonnes de la matrice des coefficients. Il peut paraître plus simple de remplacer la mémoire morte contenant la matrice de la transformée directe par une autre mémoire morte contenant la matrice transposée. Le même étage peut donc être utilisé pour la transformée directe ou pour la transformée inverse par simple changement de la mémoire morte contenant les coefficients de la matrice. De manière précise, l'invention a pour objet un circuit de calcul rapide de la transformée inverse en cosinus (xi), 0 si 515 d'un signal discrétisé défi. ni par une suite (Xi), 0 82424 nant en série une pluralité d'étages, chaque étage comportant 16 entrées et 16 sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage de multiplica- tion recevant la suite (Xi), 0 i d'au plus deux signaux appliqués sur chaque entrée. L'invention a également pour objet un cir- cuit de calcul rapide de La transformée inverse en cosinus (xi), 0Si en série une pluralité d'étages, chaque étage compor- tant 32 entrées et 32 sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage de multiplication, recevant la suite (Xi), 0{i d'addition, un troisième étage d'addition et un qua- trième étage d'addition, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués sur chaque entrée. De manière préférée, le circuit de calcul rapide de la transformée inverse en cosinus (xi) 0%i d'étages, chaque étage comprenant N entrées et N sor- ties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un étage de multiplication, un premier étage d'addition, un ensemble d'étages et un deuxième étage d'additionle si- 8B2424 il gnal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages compor- tant les mêmes étages en nombre, en ordre et en type, que ceux du circuit de calcul de la transformée inver- N se en cosinus d'un ensemble de 4 points. Le c-ircuit se construit donc par récurrence en partant du circuit correspondant à N=16, puis en ajoutant un étage de multiplication et deux étages d'addition à chaque fois que l'on multiplie par 4 la taille du signal à traiter. De manière préférée, le circuit de calcul rapide de la transformée inverse en cosinus (xi), 0 i, N-1 d'un signal discrétisé défini par une suite (Xi), OSi N-1, o N=2 et n est un nombre impair supérieur ou égal à 7, comprend une pluralité d'éta- ges, chaque étage comprenant N entrées et N sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un étage de multi- plication, un premier étage d'addition, un ensemble d'étages et un deuxième étage d'addition, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appli- qués en entrée, ledit ensemble d'étages comportant les mêmes étages en nombre, en ordre et en type, que ceux du circuit de calcul de la transformée inverse en co- N sinus d'un ensemble de N points. Le circuit se construit par récurrence de la même mahière que dans le cas précédent, le point de départ étant ici constitué du circuit correspondant à N=32. De manière avantageuse, le circuit pour la transformée directe ou inverse de l'invention comprend 82424 une mémoire d'au moins N cellules de mémorisation en- tre chaque étage. De manière préférée, Le circuit pour La transformée directe ou inverse de l'invention comprend une mémoire double entre chaque étage, chacune desdites mémoires comprenant deux séries de N cellules de mémorisation. Ces mémoires doubles permettent un traite- ment de type "pipe-line", l'une des séries de N cellu- les recevant les N valeurs délivrées par l'étage pré- cédent et l'autre série de N celluLes délivrant N va- leurs à l'étage suivant. Les deux séries de cellules d'une mémoire double fonctionnent en mode bascule ou ping-pong, c'est-à-dire que les N valeurs délivrées par l'étage précédent sont dirigées alternativement vers l'une des séries et vers l'autre série. De manière préférée, le circuit de l'inven- tion comprend également une mémoire à N cellules de mémorisation devant le premier étage. Les caractéristiques et avantages de l'in- vention ressortiront mieux de la description qui va * suivre, donnée à titre illustratif mais nullement li- mitatif, en référence aux dessins annexés, sur les- quels: - la figure 1 est un tableau illustrant, pour différentes valeurs de N, le nombre d'étages d'addition et de multiplication dans un circuit pour le calcul rapide de la transformée en cosinus selon le procédé connu de CHEN et selon le procédé de l'inven- tion, - la figure 2 est un graphe rappelant la représentation conventionnelle des opérations d'addi- tion et de multiplication par un treillis, 82424 - la figure 3a représente schématiquement le treillis associé au circuit de transformée en cosinus selon l'invention et illustre la construction de ce treillis par récurrence sur le nombre N de points de signal traité, la figure 3b illustre la structure de la moitié inférieure du treillis de la figure précédente qui produit les composantes d'indice impair de la transformée en cosinus, - la figure 4a représente schématiquement un treillis associé au circuit de l'invention dans le cas n=16, - les figures 4b et 4c représentent respec- tivement des treillis produisant les composantes d'indice pair et les composantes d'indice impair de la transformée en cosinus selon le treillis de la figure 4a, - la figure 5a représente schématiquement un treillis associé au circuit de l'invention dans le cas N=32, - les figures 5b et 5c représentent respec- tivement des treillis produisant les composantes d'in- dice pair et les composantes d'indice impair de la transformée en cosinus selon le treillis de la figure 5a, - la figure 6 est un dessin schématique d'un mode de réalisation du circuit de l'invention, - la figure 7 représente un premier mode de réalisation d'un étage d'addition du circuit de la fi- gure 6, - la figure 8 représente un second mode de réalisation d'un étage d'addition du circuit de la fi- gure 6, - la figure 9 représente un premier mode de réalisation d'un étage de multiplication du circuit de la figure 6, 82424 - La figure 10 représente un second mode de réalisation d'un étage de multiplication du circuit de La figure 6, - La figure 11 représente un treillis asso- cié au circuit de transformée en cosinus inverse seLon l'invention dans le cas N=16, et - la figure 12 est un dessin schématique d'un circuit conforme à l'invention pour Le calcul ra- pide de la transformée inverse correspondant au treil- lis de la figure 10. Le tableau représenté sur la figure 1 indi- que, pour différentes valeurs de N, le nombre d'étages du circuit de calcul rapide de la transformée en cosi- nus, selon l'article de CHEN cité plus haut, et selon l'invention. Pour chacun de ces circuits, on a indiqué respectivement le nombre d'étages de multiplication notés , le nombre d'étages d'addition notés O, et le nombre d'étages total noté E. On constate que pour n=2 ou n=3, les deux circuits comportent les mêmes étages. En revanche, pour n >,4 ce qui correspond aux valeurs les plus fré- quemment utilisées en pratique, le circuit de l'inven- tion comporte au moins un étage de multiplication de moins que le circuit connu décrit dans l'article de CHEN. De manière générale, le nombre d'étages de multiplication est de l'ordre de n dans le circuit de CHEN et de l'ordre de 3n/4 dans le circuit de l'inven- tion. Le gain d'étages de multiplication est donc de l'ordre de 25%, ce qui est considérable. Pour les cas N=16, 32, 64, le nombre d'éta- ges d'addition est identique dans le circuit de CHEN et dans le circuit de l'invention. Le nombre d'étages d'addition dans le circuit de CHEN étant égal au nom- 82424 bre d'étages de multiplication et le nombre d'étages d'addition dans le circuit de L'invention étant égal, éventuellement à une unité près, au nombre d'étages de multiplication, il apparaît également un gain moyen de 25% d'étages d'addition dans Le circuit- de L'inven- tion. Ce gain n'est effectif qu'a partir de la valeur N=128. On va maintenant décrire Le circuit de L'in- vention pour plusieurs valeurs de N en utilisant la représentation conventionnelle sous forme de treil- lis. On va tout d'abord rappeler rapidement, en réfé- rence à la figure 2, les notations utilisées dans un treillis. Le treillis de la figure 2 représente un opérateur à cinq points d'entrée et cinq points de sortie. Cet opérateur reçoit en entrée cinq valeurs a1, a2, a3, a4 et a5 et délivre en sortie cinq autres vaLeurs b1, b2, b3, b4 et b5. L'opérateur est repré- senté par un ensemble d'arcs reliant chacun un point d'entrée à un point de sortie. Ces arcs sont affectés d'un coefficient: a, P, -1. Pour simplifier la repré- sentation, on convient de ne pas indiquer le coeffi- cient lorsqu'il est égal à +1. Le coefficient associé à un arc est un coefficient multiplicatif. L'opérateur de la figure 2 réalise les opé- rations suivantes: b1 = al+p a2 b2 a1+ a2, b3 = a3, b4 a4 a5 b5 -a4+ a5. Un opérateur est dit additif si tous les coefficients associés aux arcs sont égaux à -1 ou +1. Dans le cas contraire, l'opérateur est dit multiplica- tif. 82424 Pour faciLiter La Lecture des treilLis qui vont suivre et qui iLlustrent Le circuit de caLcul rapide de la transformée en cosinus de L'invention, on va tout d'abord formaliser Les opérations effectuées dans chaque treiLLis. Pour ceLa, on considère une fa- mille (xi), O N-1 x = 2.c(i) xj. co 0 s,2(2j+1)i0 N XiN ' 4N ji=O o c(i) est égal à 1/ 2 si i=0 et à 1 si iO0. La composante Xi, o 0 si N-1, de la trans- formée en cosinus discrète d'ordre N d'une famille (Xj), 0 ij (N-1, sera notée dans la suite TCD(i, N, x). La formule inverse s'écrit: N-1 2n (2j +1l)i xj= cCi).Xi.cos 2(4N i, 0 jj o c(il est égal à 1/\V si ï=O et à 1 si i#0. Le calcul de la composante Xi de la trans- formée en cosinus discrète selon l'invention utilise deux expressionsdifférentes selon la parité de i. Ces expressions sont les suivantes: X2p = TCD(2p,N,x) = TCD(p,NxO) 2p 2CC,, o x0 (x +x_1, i1 O X =(X -Xi -1 7_4i Xp+= cos2(+4N cosTFD(2p+1,, x1) +TCD(2p+1,.4,X3 - sin C42Np+1). [sinTFD(2p+1,,1NI N 2 4N b 4 x 82424 o cosTFD(2p+1,7,x1) et sinTFD(2p+1,7,x1) notent res- pectivement la partie réelle et la partie imaginaire de la composante d'indice 2p+1 de la transformée de Fourier discrète d'ordre T de La familLe x1, et o TSD signifie transformée en sinus discrète. I 2 3 Les familles x, x et x qui apparaissent dans l'expression de la composante X2p+l sont définies de la manière suivante: N i. 0 x.:-0- j y4j+2 Y4j+I1 3 N x j: Y4j+2 + Y4j+I j8 - o i- La relation X2p=TCD(p,-,x) montre que l'ensemble des composantes d'indice pair d'une trans- formée en cosinus d'une suite x de taille N est égal à l'ensemble des composantes de la transformée en cosi- nus d'une suite x de taille N En d'autres termes, pour un treillis de taille N, l'ensemble des composantes d'indice pair de la transformée s'obtient directement en appliquant le treillis de taille N/2 à la suite x , déduite de la famille x. De même, le calcul des composantes d'indice impair X2p+l d'une suite x de N points fait appel à la transformée en cosinus d'une suite x3 de N points, ainsi qu'à la transformée en sinus et à la transformée de Fourier qui sont proches, du point de vue structu- rel, de la transformée en cosinus. Il apparaît donc que le treillis de la transformée en cosinus peut être construit par récur- rence sur N. On va d'abord décrire en référence aux figures 3a et 3b la structure d'un treillis de taille N correspondant à la transformée en cosinus selon l'invention mettant en oeuvre cette récurrence. On dé- 82424 crira ensuite des treillis correspondant aux cas par- ticuliers N=16 et N=32, ces treillis servant de base à La construction des treillis de tailles supérieures. La figure 3a représente schématiquement un treillis correspondant au calcul de la transformée en cosinus, selon l'invention, d'une suite (xi), O si!N-1 de taille N. Ce treillis est composé de trois opérations référencées 2, 4 et 6. L'opération 2 est une addition et correspond à un étage unique. Elle transforme la suite (xj),O 4j $N-1 en deux suites (xj), O Nj -1,et j N (yj), 0 j -1 selon les équations: o xj = xj + XN_-1-_j N yj= +xj - xNIj -1 Les opérations 4 et 6 sont parallèles, N l'opération 4 produisant la suite (X2q), 0 Sq,-2 des composantes d'indice pair de la transformée en cosinus à partir de la suite (x.), O j,.2-1 et l'opération 6 produisant la suite (X2q+1), 0 q (2-1 des composantes d'indice impair de la transformée en cosinus à partir de la suite (yj), 0 (j -1. - Les opérations 4 et 6 sont réalisées par un ensemble d'étages ayant chacun N points d'entrée et N points de sortie, chaque point de sortie de chaque étage recevant un signal obtenu par combinaison li- néaire d'au plus deux signaux reçus sur des points d'entrée dudit étage. Chaque étage se comporte comme une juxtapo- sition de deux demi-étages de même type, additif ou N.N multiplicatif, ayant chacun 2 points d'entrée et points de sortie. On appelle demi-étage supérieur la partie d'un étage associée à l'opération 4 et demi- étage inférieur la partie d'un étage associée à l'opé- ration 6. 8242k L'opération 4 est réalisée par un circuit de N transformée en cosinus de taiLle 2 conforme à l'inven- tion, ainsi qu'il résulte de l'expression déjà citée 2q' O$qN -1, en fonction de la des composantes X 2q, o nction de La suite (x )O0 j, N-1: X2q=TCD(q,7, x ). Par hypothèse N de récurrence, la structure de ce circuit de taille est supposée établie. Ainsi que le montre l'expression des compo- santes X2q+l, o 0 *q 2 -1, de La transformée en co- sinus, l'opération 6 fait apparaître des quantités telles que la transformée en cosinus et la transformée N en sinus de taille N, et la transformée de Fourier de N4 taille 2. L'opération 6 peut ainsi être décomposée en un ensemble d'opérations plus simples. La figure 3b illustre cette décomposition. L'opération 6 com- prend: a) - une opération d'addition 8 recevant la suite (y.), 0 Zj N-1 et délivrant trois suites (x), %z N2 3 2 N' 3 co 0 Ai 4-1, Cx3),0 -g 81et(x.), 0 Nj 1,ces 0$$8-1,e ces suites étant définies par les relations suivantes: x= y4j si 0 j N- 2 -YN-4J-1 si N3 N -1 xj Y4j+2 Y4j+l x3j = Y4j+2 + Y4j+l b) - une opération 10 recevant la suite x et déli- vrant les composantes de la transformée en cosinus N d'ordre N de cette suite. Compte tenu de symétries, les N/2 nombres délivrés par cette opération, égaux.à 3ON TCD(2q+1,N/4,X) pour q compris entre 0 et -1, se ramènent à N/8 nombres différents notés (y2q+1, 0 c) - une opération 12 recevant la suite x1 et déli- vrant les parties réelles des composantes d'indice 82424 impair de la transformée de Fourier discrète d'ordre N/2 de cette suite. Compte tenu de symétries, les N/2 nombres délivrés par cette opération, égaux à i N cosTFD(2q+1,N/2,x) pour q compris entre 0 et N-1, se ramènent à N/8 nombres différents notés (o2q+ N (2q+1) 0 q -1Q, d) - une opération 14 recevant la suite x et déli- vrant les parties imag.inaires des composantes d'indice impair de la transformée de Fourier discrète d'ordre N/2 de cette suite. Compte tenu de symétries, les N nombres délivrés par cette opération, égaux à sinTFD (2q+1,N/2,x 1) pour q compris entre 0 et T -1, N se ramènent à - nombres différents notés (2q+1) 0 Nq -1, e) - une opération 16 recevant la suite x et déli- vrant les composantes de la transformée en sinus d'or- N dre N de cette suite. Compte tenu de symétries, les N/2 nombres délivrés par cette opération, égaux à TSD(2q+1,N/4,x2) pour q compris entre 0 et N-1, se ramènent à N/8 nombres différents notés (2q+1) 0 q4 1, f) - une opération 18 recevant les suites impaires ", À, y et ú, et délivrant les suites impaires A, p, etP selon les équations suivantes: X2q+1 =2q+1 -2q+1 l2q+1 = 2q+1 + T2q+1 )2q+1 = 2q+1 + S2q+1 3O 32q+1: 2q+ 1 - 2q+1 avec 0 q, N-1 g) - une opération 20 recevant les suites impaires A, p,) et f et délivrant les composantes d'indice impair de la transformée en cosinus, cette opération étant définie par les relations suivantes: 82424 N+2q+l N+2q+l1 N/2+(2q+1) = (8)'A2q+1 + s(8 '2q+ l 2q+l c(2 - 8-) p2q+1 + 5() 2q+1 = - 2q+1 N-(2q+1) ()*P2q+1 - C() 2q+1 X N/2(2q+I) N-(2q+1)) X s(N-(2q+1) N/2-(2q+) 8 ' 2q+1 -)-f2q+1 avec 0 Nq4 -1 et o c() = cos-i-2 et s()= sin N. Les symétries qui permettent de réduire à N/8 le nombre des points de sortie des opérations 10, 12, 14 et 16 résultent directement des expressions TCD, TSD, cosTFD et sinTFD. Par exemple, TCD(2q+1+N/2,N/4,x3) s'écrit N/8-1 3 2u(2j+1)(2q+1) + (2q+1) zi xcos N + n(2q+l j=O c'est-à-dire -TCD(2q+1,N/4,x3). De manière générale, on a ainsi les rela- t ions suivantes pour 0 Zq [Z-1: y2q+l = TCD(2q+1,N/4,x3) T2q+1 = N 3 = TCD(N-(2q+1),N/4,x) =-TCD(e +(2q+),N/4,x3) = TCD(N-(2q+I),N/4,xx) De même, o2q+l=cosTFD(2q+1,N/2,x) = cosTFD( -(2q+l),N/2,x) = cosTFD( 82424 Il est intéressant de remarquer que Les sui- tes impaires X et y représentent les parties réelles des composantes d'indice impair de la transformée de Fourier d'une suite x5 définie par: x5 = Y2j si j5 ii-1 et x =-YN-2j-1 si N/4 j c-1. Ces compo- santes sont cosTFD(2q+1,N,x), pour q compris entre 0 N et -1. De même, les suites impaires) et f repré- sentent les parties imaginaires des composantes d'in- dice impair de la transformée de Fourier de la suite 5. x et sont notées, sinTFD(2q+1,N,x5) pour q compris entre 0 et N-1. Les opérations 12 et 14 peuvent ainsi être construites par récurrence sur N. Par ailleurs, L'opé- ration 16 est structurellement identique à l'opération et peut également se construire par récurrence. Enfin, on peut vérifier que les opérations 12, 14, 16 comportent un nombre d'étages inférieur ou égal au nombre d'étages de l'opération 10 et que pour chacune des opérations ces étages sont du même type (additif ou multiplicatif). La récurrence peut donc être bâtie sur le nombre d'étages nécessaires pour réaliser l'opération 10. Cette opération qui calcule les composantes impai- res de la transformée en cosinus de taille N/4 est réalisée par une suite d'étages égale aux étages de calcul de la transformée en cosinus complète privée de l'étage d'addition initial. Comme l'opération 8 est une addition, on peut dire que les opérations 8 et 10 nécessitent un ensemble d'étages identique à l'ensem- ble des étages d'un circuit de la transformée en cosi- nus de taille N/4. Ainsi, ayant un ensemble d'étages formant un circuit de transformée en cosinus de taille N/4 (cor- respondant aux opérations 8 et 10), il suffit d'ajou- 82424 ter deux étages d'addition et un étage de multiplica- tion (correspondant respectivement aux opérations 2, 18 et 20) pour obtenir un circuit de calcul de la transformée en cosinus de taille N. Les figures 3a et 3b illustrent le graphe de la transformée directe en cosinus. Le graphe de la transformée inverse s'en déduit aisément. Il suffit de reprendre les opérations dans l'ordre inverse, en rem- plaçant ces opérations par les opérations transposées, celles-ci étant définies comme étant les operations dont les matrices associées sont les transposées des matrices associées aux opérations de la transformée directe. On va maintenant décrire successivement un treillis correspondant au cas N=16 et un treillis cor- respondant au cas N=32. Les figures 4a, 4b et 4c représentent un treillis de la transformée en cosinus pour le cas N=16. Ce treillis peut être décomposé en trois opéra- tions référencées respectivement 22, 24 et 26 (figure 4a). L'opération 22 est l'opération d'addition initia- le commune à tous les treillis. Cette étape consiste à transformer la suite (x;), O xj 0.j47. L'opération 24 appliquée à la suite (c.), O Fji 7 est représentée sur la figure 4b par le treil- lis de la transformée en cosinus de taille N=8, selon l'invention. Cette opération 24 déLivre les composan- tes d'indice pair de la transformée en cosinus dans l'ordre suivant: X0, X8, X4, X12, X2, X10, X6 et X14. Ce treillis comporte successivement quatre étapes, une addition, une multiplication, une addition et une multiplication. La première addition délivre huit valeurs do, d1,...d7 selon les relations suivan- tes: 82424 dj= c +c 7j pour 0 j 43 dj =cj -c7_j pour 4 4 7 Les quatre premières valeurs do, d1, d2, d3 donnent les composantes d'indice pair X0, X8, X4 et 2 de la transformée en cosinus. La première multiplication est définie par: e0 = do e1 d1 e2 = d2 e d2 e3 = d3 = e4 = d4 -e, -ce-d5 +c-'.d6 = -c. d5+c.4 d6 e6c' d5+cZ-d6 e7 = d7 Notons que La première multiplication ap- pliquée aux composantes do, dl, d2 et d3 est en fait l'opération d'identité. Cette opération permet de re- porter la deuxième addition effectuée sur ces compo- santes en même temps que la deuxième addition effec- tuée sur les quatre composantes e4, e5, e6 et e7. Cha- que étage de calcul reçoit ainsi simultanément toutes les composantes d'une suite, ce qui permet un traite- ment de type "pipe-line". La deuxième addition est définie par: fo = eo + e3 f= e+ e2 2 e1 -e2 f3 = eo - e3 f4 e4 + e5 f5 = e4 -e5 f6 =-e6 + e7 f e6+e 7 = e6 + e7 Enfin, la troisième multiplication est dé- finie par: 82424 X0 = c4. f0 + c.f = c4f0 41 n T X= s.-f2 + c.f3 cX12--C'.f2 + S.f3 X2 = s6. f4 + Cn.f7 x10= s5-f5 + ci-.f6 _ 5 + 5u X6 =-a-.f5 + s1-.f6 X14=-CTS. f4 + s1-.f7 L'opration 26 transforme la suite (cj), 8 j 15, en composantes d'indice impair de la trans- formée en cosinus. Cette opération 26 est constituée, conformément à l'invention, des quatre opérations suc- cessives suivantes: une addition, une multiplica- tion, une addition, une multiplication. Le treillis détaillé correspondant à cette opération 26 est représenté sur La figure 4c. Ces opérations sont définies par les équa- tions suivantes: - première addition (tableau I), - première multiplication (tableau II), - deuxième addition (tableau III), - deuxième multiplication (tableau IV), Dans ce treillis, les éléments ei, o 8 Ai e15, représentent les différentes valeurs de cosTFD, sinTFD, TCD et TSD apparaissant dans la figure 3b. Les composantes fi, o 8.Si par l'opération 18 de la figure 3b. Le treillis selon l'invention représenté sur les figures 4a, 4b et 4c apporte un gain d'un 82424 étage de multiplication par rapport au treillis selon l'art antérieur. Un gain identique est obtenu dans le cas N=32. Le treillis correspondant comporte en effet seulement sept étages dont trois étages de multiplica- tion. On a représenté sur la figure 5a le treillis correspondant au procédé de calcul rapide de la trans- formée en cosinus selon l'invention dans le cas N=32. Ce treillis est représenté sous la forme d'un bloc de trois opérations référencées respectivement 28, 30 et 32. L'opération 28 est l'addition initiale commune à tous les treillis, elle transforme la suite (xi), 0 Ai 31, en une suite (ai),O 4i\31, définie par aj=xj+x31 -j et a16+j= xj 31 -j' pour 0%j 15. L'opération 30 représente le treillis sui- vant l'invention pour N=16. Il transforme les 16 pre- mières composantes a0, a1,..., a15 en composantes d'indice pair de la transformée en cosinus de la suite (xi), 0.i 31, dans l'ordre suivant: X0, X16, X8, X24, X4, X20, X12, X28, X30, X6, X18, X10, X22, X14, X26 et X2 L'opération 30 est représentée par le treil- lis de la figure 5b. Elle est fonctionnellement iden- tique au treillis représenté sur les figures 4a, 4b et 4c et correspondant à N=16. Il en diffère légèrement dans sa réalisation par l'adjonction entre les deux premières étapes additives d'une étape multiplicative égale à l'opération identité. Cette étape supplémen- taire permet de synchroniser les additions et les mul- tiptications réalisées par-les opérations 30 et 32, ce qui rend possible un traitement de type "pipe-line". On va maintenant décrire, en référence à la figure 5c, le treillis correspondant à l'opération 32. Celle-ci transforme les 16 dernières composantes a16, a17,..., a31 en composantes d'indice impair de la 82424 transformée en cosinus de la suite (xi), 0i 31. * Elle est constituée d'une suite d'étapes comprenant successivement une première addition, une deuxième addition, une première multiplication, une deuxième multiplication, une troisième addition et une troisiè- me multiplication. Ces opérations sont définies par les relations suivantes: - première addition (tableau V), - deuxième addition (tableau VI), première multiplication (tableau VII), - deuxième multiplication (tableau VIII), - troisième addition (tableau IX), - - troisième multiplication (tableau X). Les calculs correspondant aux treillis re- présentés sur les figures 3a à 5c sont réalisés par des circuits comportant en série des étages d'addition et des étages de multiplication. A titre d'exemple, on va décrire le schéma de principe d'un circuit corres- pondant à N=16. Ce circuit est représenté sur la figu- re 6. Ce circuit comprend en série 5 étages de calculs référencés 114, 116, 118, 120 et 122. Ces cir- cuits comprennent chacun 16 entrées et 16 sorties. Les étages 114, 116, et 120 sont des étages d'addition de la forme a+b et les étages 118 et 122 sont des étages de multiplication de la forme oca+pb. Le calcul effec- tué par l'étage de rang k, o k est compris entre 1 et , correspond à l'étape de rang k du treillis repré- senté sur les figures 4a, 4b et 4c. On décrira en référence aux figures 7 et 8 des modes de réalisation particulier d'un étage d'ad- dition et en référence aux figures 9 et 10 des modes de réalisation particuliers d'un étage de multiplica- tion. Le circuit représenté sur la figure 6 com- prend en outre des mémoires doubles 124, 126, 128 et 82424 disposées chacune en série entre deux étages suc- cessifs. Dans le cas représenté sur la figure, chaque mémoire double comporte deux séries de 16 cellules de mémorisation. Plus généralement, la taille de chaque série est égale à N. Chaque série de N cellules d'une mémoire double peut recevoir les N valeurs délivrées par l'étage qui la précède. Les deux séries d'une même mémoire fonction- nent en bascule. A un instant donné, une série reçoit les N valeurs délivrées par l'étage précédent alors que l'autre série délivre les N valeurs mémorisées à l'étage suivant. A l'instant suivant, le rôle de cha- que série est inversé; la série réceptrice devient émettrice et la série émettrice, réceptrice. Ces mémoires doubles sont utilisées pour synchroniser les flux de données entre les différents étages de calculs et permettre ainsi un traitement de type pipe-line. Dans le cas d'un traitement séquentiel sans pipe-line, ces mémoires doubles peuvent être sup- primées. En général, chaque étage d'addition compor- te un seul additionneur et un seul soustracteur, et de même, chaque étage multiplicatif comporte deux multi- plieurs, un additionneur et un soustracteur. Le trai- tement des N valeurs reçues par l'étage se fait dans ce cas de manière séquentielle. Il est alors nécessai- re d'adjoindre entre chaque étage de calcul une mémoi- re simple si le circuit ne comporte pas de mémoire double. De plus, une mémoire tampon 132 peut être dis- posée en entrée de l'étage d'addition 114. On va maintenant décrire des modes de réali- sation d'un étage d'addition et d'un étage de multi- plication en référence aux figures 7 à 10. La figure 7 représente un premier mode de réalisation d'un étage d'addition. Il comprend essen- 82424 tiellement deux tampons d'entrée 134, 136 pour mémori- ser des nombres a et b, un additionneur 138, un sous- tracteur 140 et deux tampons- de sortie 142, 144. L'additionneur 138 comporte une entrée de commande 139 qui commande soit l'addition des deux nombres contenus dans les tampons d'entrée, soit la transmission de l'un de ces nombres. Le soustracteur 140 comprend de même une entrée 141 ayant un roLe semblable. Le tampon de sortie 142 peut ainsi recevoir a+b, a ou b; le tampon de sortie 144 a-b, a ou -b. La figure 8 illustre une variante de réali- sation de l'étage d'addition. Le soustracteur et l'ad= ditionneur sont remplacés par un additionneur-sous- tracteur 148 ayant deux entrdes de commande 147e 149 pour définir le nombre délivré au tampon de sortie 146 qui peut être égatl a, -b, a+b ou a-b. Les étages d'addi 'in représentés sur les figures 7 et 8 comprennent èégaleient un séquenceur et un moyen d'adressage (non re-prsentés), ce dernier étant utilisé pour charger les tampons d0entrée avec des nombres contenus dans la mémoire précédant cet étage et pour staocker dans la mésmoire suivante le con- tenu d'un tampon de sortie. La figure 9 représente un premier mode de réalisation d'un étage de multiplication. Il comprend quatre tampons d'entrée 150, 152e 154 et 156 contenant respectivement les nombres c, p, a et b, deux multi- plieurs 158 et 160 pour délivrer les produits aa et Ob, un additionneur-soustracteur 162 ayant deux en- trées de commande 161, 163 et un tampon de sortie 164 recevant, selon les signaux appliqués sur les entrées de commande 161 et 163, "a, Pb, aa+pb ou ca-Pb. Les tampons d'entrée 154 et 156 reçoivent des nombres de la mémoire précédant l'étage multipli- catif. Les tampons d'entrée 150 et 152 sont chargés 82424 avec des nombres contenus dans une mémoire morte 149 associée à cet étage. Celui-ci comprend également un séquenceur et un moyen d'adressage (non représentés). Les tampons d'entrée 150 et 152 peuvent re- cevoir respectivement les coefficients " et À, mais aussi les coefficients p et a. Dans ce cas, le tampon 164 peut recevoir les nombres "b, Pa, pa-ob, pa+ob. S'il n'est pas possible d'orienter chaque coefficient a et p indifféremment vers les tampons d'entrée 150 et 152, il faut prévoir deux circuits comme celui de la figure 9, l'un dans lequel les tampons d'entrée 150 et 152 reçoivent respectivement " et p et l'autre dans lequel ils reçoivent respectivement P et a. Une première variante de réalisation du cir- cuit de la figure 9 consiste à remplacer l'addition- neur-soustracteur 162 par un additionneur et un sous- tracteur distinct. Dans ce cas, quatre muttiplieurs sont nécessaires, deux étant associés à l'additionneur et deux au soustracteur. Une seconde variante de réalisation est re- présentée sur la figure 10. Ce circuit est intéressant dans le cas o une vitesse de traitement moins impor- tante est acceptée. Dans cette figure, les éléments identiques à ceux de la figure 9 portent les mêmes références. Dans cet étage, on a supprimé les tampons d'entrée 152 et 156, et le multiplieur 160. Une mémoi- re 166 de type accumulateur à une entrée et deux sor- ties, est disposée entre le multiplieur 158 et l'addi- tionneur-soustracteur 162. La mémoire 166 et l'addi- tionneur-soustracteur 162 peuvent être remplacés par un additionneursoustracteur ayant une entrée de type accumulateur. L'avantage de ce mode de réalisation est de ne nécessiter qu'un seul multiplieur, ce qui est très avantageux du point de vue économique. On a indiqué en référence aux figures 3a à c des treillis correspondant au calcul de la trans- 82424 formée en cosinus selon l'invention. Le traitement en cosinus effectué sur un signal a souvent pour but de réaliser un traitement de ce signal dans le domaine fréquentiel. Celui-ci est généralement suivi de la transformée en cosinus inverse de ce signal traité. Le treillis correspondant à la transformée inverse en cosinus s'obtient très facilement à partir du treillis de la transformée directe. Il suffit en effet de rem- placer les opérations de calcul par leurs transposées et de renverser l'ordre de ces opérations, comme on l'a indiqué en référence aux figures 3a et 3b. - On trouvera à titre d'exemple sur la figure 11i le treillis correspondant à la transformée inverse en cosinus pour le cas N=16. Ce treillis correspond exactement au treillis de la figure 4a lu de droite à gauche avec les mêmes coefficients. On a représenté sur la figure 12 le schéma de principe du circuit associé à cette transformation inverse. Les étages de calcul sont identiques à ceux du circuit de la figure 6, mais leur ordre est inver- sé. Entre ces étages de calcul sont insérées des mé- moires doubles 166, 168, 170 et 172 dont le r6le est identique aux mémoires 124, 126, 128 et 130 du circuit de la figure 7. Par ailleurs, la mémoire 174 située en entrée du circuit de la figure 12 joue un rôle identi- que à celui de la mémoire 132 du circuit de la figure 6. 82424 TABLEAU I d8 = c8 d9= c9+c10- d10 = c9-c10 d11 Cl +C12 d12 = c11-c12 d =c +c 13 c13 14 d14 c13-c14 d15 = c15 TABLEAU II e8 -ds+c-d12 iTE e9 -cE d9+s-. d13 e10 C.d10+sg-d14 el, =-c4.d11+d15 e12 = d8+c4.d12 e13 = s8-.d9+c-.d13 144 1 e14 = -s.d10+C-. d14 e15 = cI.d11+ d15 TABLEAU III f8= e8+e10 f9 = e9e11 f10 = -es+e10 fil = -e9+e11 f12 = -e12+e14 f13 = e13+e15 f14= e12+e14 = e13+e15 Lúe = Iúq q 0úe _ 62e = Oúq Oúe + 62e = 62q gze - z 2 L' =82q 0ú ze _ Z2e = z2q 9Le + Z2e = Z2q 9-e _ Se= 9Zq 9Ze + Se = S2q Ze _ ú2e = 2q 2e + ú2e = úZq ze G e = 2q 22e+[,e= ú2q 02e 6 - =02q 0Ze+ 6Le = 6lq 91q 8[e. ' t. q 7 [i 1 2=V - 2LX ZL O 2 nizs T - X + 14 ZS!lo2 - 3 -.3Zú = [X AlRúS _I1Z5.= g ú..,.s + OL *ú=6 -".ú úLx SL -úS +;._ZúD = SIX AI lluV A IL ús -_.. AI + V1B1. 82424 TABLEAU VI c16 = b16 c17 = b17 c18 = b18 C19 = b19 c20 = b20 c21 = b21 + b25 c22 = b22. b26 c23 = b23 c24 = b24 c25 -b25 + b21 c26 = b22 + b26 c27 = b27 c28 b28 c29 = b29 c30 = b30 c31 = b31 82424 TABLEAU VII d16 = C16 + 4 'C24 d17 =-c17 + cT.c25 d18 = -c18 + CóC26 d19:-c1 + ó1 'c27 d 20: -s9.c20 + cI.c28 d21 = CT'C21 + c29 d22 4 -c.c22+ C30 d23 = cT. c23 + c31 24= -c16 + c.c24 d25 =c17 +4c.c25 d26 c18 +4c-c26 27= -c.c19 + 27 d28 c8.c20+ s8.c28 d 2 d29 = -c4-.c21+ c29 d30 4 c.c22+ c30 dC -c'.c2 + c 31 C4C 23+ 31 Lúp + ZZp = Lúa úp.9_ + 9zp.9__s_= 0ú 6PZ.9_S+ Sp.9_J= 6Z Iúp + Zp_ = ZeZa Oúp-9_s + 9zp.9_3 = 9Za 6Zp.93s + sZp9Ls_ = sza 8Zp + -Zp_ = L úZp + 6 p_ = úza ?-P ú s + PI P'3Lú3 = z za Uú + - vz3-91- + 81p-91s_ = ZZa Oe + = Ozp + 9Lp= OZa úZp + 6Lp = 6Le ZEP--ú3 + LP.-9s_ = 8le +ú UL.. - lL ILZp9 -s + iLp-91, zLa u = oz 9L 91. OZp + 9p = 9e IIIA NlV3']V. 9ú 82424 TABLEAU IX 16 e16 + e22 f e1= e17 + e23 f8 18 e18e20 19 = e19 e21 2 0 = e18 + e20 f = + e 1 0 f2 21 e 19 e21 f22 =-e16 'F e22 f =-C 23 ='7y + e f24 =-e2 e30 f 1 f25 '2- 5 f e6 '2:e2s f267- 7 29 f28 e26 e28 f =2 f2s9 = 27 e29 f30 - e24 + e30 31 '25 e31. 82424 TABLEAU X 3Tu 3Tt X29 = C64.f16 + s.f31 7TO 7T 3 7 -64 64'f30 = 11uT 11ET 2 21 c.64f18 + S64-f29 t I 15Tt c 64f19 64f28 27 C64'f20 + 64- 27 X1 = c64-.f21 - S64.f26 c64.f22 S 64 25 X9=64.f23 - 24 = c5-f2 133- - X23 = C64-.f24 + s64.f23 X13 = c64-f25 -5&'22 31 C64-2 564-2 = c5-.f27 - S64- f20 17 = c64.f28 +S -f19 1 111.= il ilu. X = C 64f2 - s64- f18 X = 7-.f + s7.f X25 C64 -f30 64 17 X5= c.f312 - s3. nf2 6 64 5T64I51 82424 REVENDICATIONS 1. Circuit de calcul rapide de la transfor- mée en cosinus (Xi), 0 li 315 d'un signal discrétisé défini par une suite (xi), 0 i} 15, ledit circuit comprenant en série une pLuralité d'étages, chaque étage comportant 16 entrées et 16 sorties, ledit cir- cuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage d'ad- dition recevant la suite (xi), O i A15, un deuxième étage d'addition, un premier étage de multiplication, un troisième étage d'addition et un deuxième étage de multiplication, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués sur chaque entrée. 2. Circuit de calcul rapide de la transfor- mée en cosinus (Xi), 0 i 331 d'un signal discrétisé défini par une suite (xi), Oi 431, Ledit circuit comprenant en série une pluralité d'étages, chaque étage comportant 32 entrées et 32 sorties, Ledit cir- cuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage d'ad- dition, recevant la suite (xi), O i sur chaque entrée. 3. Circuit de calcul rapide de la transfor- mée en cosinus (Xi), O Li N-1 d'un signal discrétisé défini par une suite (xi), O;i N-1, o N=2n et n est un nombre entier pair supérieur ou égal à 6, ledit circuit comprenant une pluralité d'étages, chaque 82424 étage comprenant N entrées et N sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage d'addition, un ensemble d'étages, un deuxième étage d'addition et un étage de multiplication, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages comportant les mêmes étages en nombre, en ordre et en type, que ceux du circuit de N caLcul de la transformée en cosinus d'un ensemble de points, ledit ensemble d'étages étant conforme au circuit selon la revendication 1 lorsque ledit ensem- ble de points comprend 16 points. 4. Circuit de calcul rapide de la transformée en cosinus (Xi), 0 i A N-1 d'un signal discrétisé défini par une suite (xi), 04.iiN-1, o N=2n et n est un nombre impair supérieur ou égal à 7, ledit circuit comprenant une pluralité d'étages, chaque étage comprenant N entrées et N sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans L'ordre, les étages suivants: un premier étage d'ad- dition, un ensemble d'étages, un deuxième étage d'ad- dition et un étage de multiplication, Le signaL déli- vré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages comportant les mêmes étages en nombre, en ordre et en type, que ceux du circuit de calcul de la transformée en cosinus d'un N ensemble de X points, ledit ensemble d'étages étant conforme au circuit selon la revendication 2 lorsque ledit ensemble de points comprend 32 points. 5. Circuit de calcul rapide de la transfor- mée encosinus (Xi), 0 Mi N-1, d'un signal discrétisé défini par une suite (xi), 0 ii N-1, caractérisé en 82424 ce qu'il comprend un premier étage d'addition et un ensemble d'étages, Ledit premier étage recevant la suite (xj), 0) j'N-1, o N=2 et n est un entier su- périeur à 7, et délivrant une première suite (xO), 0 Oj -1, o x: x +XN j et une seconde suite (yj)p 0j -1, o yj=x1:y N lji chaque étage dudit ensem2 ble d'étages éèant conipose' d'un demiétage supérieur et d'un demi dt nge inférieur, les de- i-é tages d0uni même étage étant dueme ev, lesdits rniétag Su I0 périeurs étant reli -s C- s-rie, le pr -iSeri clemin g-e superieur recei;: La prreFière sui'L c- -0 Oj-" = [') et le dernier Le-; u d li'ran' la suite (X 0 q r, ci ' tc- _o i 'p o S ^ sd' indice-pairdeLa transformée,i eCosinius,u s- sd i's úteJi 4;, -2ges in:, rieurs étant rc i4,s en _Aiji pe'm ier d ié-;'ageJg inférieur rce':_. l. s e cd,vsi'^ -' O j 01" et le dernier - Pu....... L a i (X2q+, f0, 4!- "-) cl GOir opor S i d indc i3 pai r de la transforrm.e 9s3:oSiUs uSi-;; S Jei 'c- g a g ec tant définis par r'-u.'s:. s r La;--a id il de la manière suivante: 1) - la su.:,s de-i ';. ies su6erieurs consi S tue u 5ci reui de transf-ormie eCri cosinus pour i/ po in i's con 'orme _-c l une quel conque des rî-- dications 3 et 4e 2) - la sui;^ de-s demiaé eages inôérieurscor-- prend dans l ordre c a) un premier d-..a étage in'eraeur daddition déL-- vrant une trois,ème Suie uD jc- 1 rr 3j X y4j+y2+y4j+ - unre qu sie. suite j) là1, o.i3-4jpour j e' C -=-' pour j> -1, et une cinquièmue Su i e sX) i ';j 1 o xj-Y4j+2-Y4j+1., 0 >j'-1. o:"=Yj po u 2'' et y j, _, b) un ensemble de demi-étages inférieurs dont l'ordre eet la nature des étages sont ceu:x d'un circuit de 82424 transformée en cosinus pour une suite de N/4 points conforme à L'une quelconque des revendications 3 et 4, ledit ensemble délivrant une sixième suite (a2q+1), q 1, égale aux parties réelles des composantes d'indice impair de la transformée de N Fourier d'ordre 2 de la quatrième suite, une septiè- me suite (P2q+1), 0 q l-I1 égale aux parties imaginaires des composantes d'indice impair de la transformée de Fourier d'ordre 2 de la quatrième suite, une huitième suite (.2q+1), 0úq -1 égale aux composantes d'indice impair de la transformée en sinus d'ordre de la cinquième suite, une neuvième suite (y2q+1), 0 q -I1 égale aux composantes d'in- q N dice impair de la transformée en cosinus d'ordre de la troisième suite, c) un deuxième demi-étage inférieur d'addition pour délivrer les suites ( 2q+10 2q' -1, (e2q+1-Y2q+1)' q 8 (82q+1+ 2q+1' et (g2q+1 -2q+1), T -l d) un demi-étage inférieur de multiplication déli- vrant la suite (X2q+), 0 &q i-1, des composantes d'indice impair de la transformée en cosinus d'ordre N de la suite (xj), 0 j N-1. 6. Circuit selon l'une quelconque des reven- dications 1 à 5, caractérisé en ce qu'il comprend une mémoire d'au moins N cellules de mémorisation entre chaque étage. 7. Circuit selon l'une quelconque des reven- dications 1 à 5, caractérisé en ce qu'il comprend une mémoire double entre chaque étage, comportant au moins deux séries de N cellules de mémorisation. 8.Circuit selon l'une quelconque des reven- dications 6 et 7, caractérisé en ce qu'il comprend en outre une mémoire d'au moins N cellules de mémorisation devant le premier étage. 82424 9. Circuit de calcul rapide de la transfor- mée inverse en cosinus (xi), 0 $is 15 d'un signal dis- crétisé défini par une suite (Xi), 0 premier étage d'addition, un deuxième étage de multi- plication, un deuxième étage d'addition et un troisiè- me étage d'addition, le signal déLivré sur chaque sor- tie de chaque étage étant obtenu par combinaison li- néaire d'au plus deux signaux appliqués sur chaque en- trée. 10. Circuit de calcul rapide de la transfor- mée inverse en cosinus (xi), 0.i 31 d'un signal dis- crétisé défini par une suite (Xi), 0 if 31, ledit circuit comprenant en série une pluralité d'étages, chaque étage comportant 32 entrées et 32 sorties, le- dit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un premier étage de multiplication, recevant la suite (Xi), 0 un premier étage d'addition, un deuxième étage de mul- tiplication, un troisième étage de multiplication, un deuxième étage d'addition, un troisième étage d'addi- tion et un quatrième étage d'addition, le signal déli- vré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués sur chaque entrée. 11. Circuit.de calcul rapide de la transfor- mée inverse en cosinus (xi), 0 Si N-1 d'un signal discrétisé défini par une suite (Xi), 0 {i. N-1, o N=2n et n est un nombre entier pair supérieur ou égal à 6, ledit circuit comprenant une pluralité d'étages, chaque étage comprenant N entrées et N sorties, ledit 82424 circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un étage de multiplica- tion, un premier étage d'addition, un ensemble d'éta- ges et un deuxième étage d'addition, le signal délivré sur chaque sortie de chaque étage- étant obtenu par combinaison Linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages comportant les mê- mes étages en nombre, en ordre et en type, que ceux du circuit de calcul de la transformée inverse en cosinus N d'un ensemble de N points, ledit ensemble d'étages étant conforme au circuit selon la revendication 9 lorsque ledit ensemble de points comprend 16 points. 12. Circuit de calcul rapide de la transfor- mée inverse en cosinus (xi), 0 i N-1 d'un signal discrétisé défini par une suite (Xi), 0 Si. N-1, o N=2n et n est un nombre impair supérieur ou égal à 7, ledit circuit comprenant une pluralité d'étages, cha- que étage comprenant N entrées et N sorties, ledit circuit étant caractérisé en ce qu'il comprend, dans l'ordre, les étages suivants: un étage de multiplica- tion, un premier étage d'addition, un ensemble d'éta- ges et un deuxième étage d'addition, le signal délivré sur chaque sortie de chaque étage étant obtenu par combinaison linéaire d'au plus deux signaux appliqués en entrée, ledit ensemble d'étages comportant les mê- mes étages en nombre, en ordre et en type, que ceux du circuit de calcul de la transformée inverse en cosinus d'un ensemble de N points, ledit ensemble d'étages étant conforme au circuit selon la revendication 10 lorsque ledit ensemble de points comprend 32 points. 13. Circuit selon l'une quelconque des re- vendications 9 à 12, caractérisé en ce qu'il comprend une mémoire d'au moins N cellules de mémorisation en- tre chaque étage. 14. Circuit selon l'une quelconque des re- vendications 9 à 12, caractérisé en ce qu'il comprend 82424 une mémoire double entre chaque étage, comportant au moins deux séries de N cellules de mémorisation. 15. Circuit selon l'une quelconque des re- vendications 13 et 14, caractérisé en ce qu'il com- prend en outre une mémoire d'au moins N cellules de mémorisation devant le premier étage.