Brevet FR2641098A1 — publié le 19900629

DISPOSITIF DE CALCUL SIMULTANE DE DEUX FONCTIONS TRANSFORMES DE FOUILlER DE DEUX FONCTIONS RELLES L'invention concerne un dispositif permettant de calculer simultanément deux fonctions transformées de Fourier de deux fonctions réelles. Un circuit classique de transformation de Fourier permet de traiter une fonction complexe, et comporte un premier et un second registre d'entree recevant respectivement N valeurs discrètes de la partie réelle de la fonction à transformer, et N valeurs discrètes de la partie imaginaire de la fonction à transformer. Il comporte aussi un premier et un second registre de sortie fournissant respectivement N valeurs de la partie réelle, et N valeurs de . la partie imaginaire de la fonction transformée. Dans le cas où la fonction à transformer est une fonction réelle, seul le premier registre d'entrée est utilisé, le second registre d'entrée recevant N valeurs nulles en permanence. Par contre, les deux registres de sortie sont utilisés, puisque la fonction transformée de Fourier est en général une fonction complexe. Pour calculer deux fonctions transformées de deux fonctions réelles, il est connu d'utiliser en parallèle deux circuits classiques de transformation de Fourier, ou bien d'utiliser un seul circuit classique de transformation, associé à des moyens de multiplexage temporel, pour traiter successivement les deux fonctions. Le but de l'invention est de proposer un dispositif permettant de calculer simultanément deux fonctions transformées de Fourier de deux fonctions réelles indépendantes, sans utiliser en parallele deux circuits classiques de transformation, et sans utiliser deux fois successivement un même circuit classique, afin de réduire le nombre de circuits de transformation de Fourier, ou bien de diviser par deux le temps de calcul. L'objet de l'invention est un dispositif de calcul comportant essentiellement un seul circuit classique de transformation de Fourier, et un circuit arithmétique qui calcule des combinaisons de valeurs fournies par les deux registres de sortie de ce circuit classique. Selon l'invention, un dispositif de calcul simultané de deux fonctions transformées de Fourier de deux fonctions réelles, est caractérisé en ce qu'il comporte - un circuit classique de transformation de Fourier diune fonction complexe, comportant un premier et un second registre d'entrée recevant respectivement N valeurs d'une ~ première fonction réelle et N valeurs d'une seconde fonction réelle à transformer, et comportant un premier et un second registre de sortie fournissant respectivement N valeurs de la partie réelle et N valeurs de la partie imaginaire de la fonction transformée d'une fonction complexe dont la partie réelle est constituée par la première fonction réelle et dont la partie - imaginaire est constitué par la seconde fonction réelle - des premiers moyens de calcul pour calculer la demi-somme de deux valeurs fournies par le premier registre de sortie, pour déterminer chaque valeur de la partie réelle de la fonction transformée de la première fonction réelle - des deuxièmes moyens de calcul pour calculer la demi-différence de deux valeurs fournies par le premier registre de sortie pour déterminer chaque valeur de la partie imaginaire de la fonction transformée de la seconde fonction réelle - des troisièmes moyens de calcul pour calculer la demi-somme de deux valeurs fournies par le second registre de sortie, pour déterminer chaque valeur de la partie réelle de la fonction transformée de la seconde fonction réelle; - des quatrièmes moyens de calcul pour calculer la demi-différence de deux valeurs fournies par le second registre de sortie, pour déterminer chaque valeur de la partie imaginaire de la fonction transformée de la première fonction réelle. L'invention sera mieux comprise et d'autres détails apparaîtront à l'aide de la description d'un exemple de réalisation et de la figure représentant le schéma synoptique de cet exemple de réallsatlon. Tout d'abord considérons les propriétés mathématiques de la transformation de Fourier qui permettent d'expliquer le fonctionnement du dispositif selon l'invention. La transformée de Fourier F(u) d'une fonction f(x) et la transformée de Fourier G(u) d'une fonction g(x), dans le cas où ces deux fonctions sont échantillonnées selon N valeurs discrètes, peuvent être calculées selon les formules suivantes N-l F(u) = 1 #f(x).exp(-2i.~.x.u/N) pour u = 0 à N-1 (1) N x=0 N-1 G(u) =1#g(x).exp(-2i.@.x.u/N) pour u = 0 à N-1 (2) N x=0 La transformée de Fourier d'une fonction réelle possède la propriété de symétrie hermitienne.Les fonctions f et g étant réelles, cette propriété se traduit par les formules suivantes F(u) = conjugué [F(N-u)] (3) G(u) = conjugué [G(N-u)] (4) La partie réelle et la partie imaginaire de ces fonctions transformées ont donc les propriétés suivantes Re = Re[F(N-u)] (5) Im[F(u)] = -Im[F(N-u)] (6) Un circuit classique de transformation de Fourier permet de transformer une fonction complexe h(x), échantillonnée pour x=0 à N-1, en une fonction complexe H(u), échantillonnée pour u=0 à N-1. Supposons que la fonction complexe à transformer, h(x), ait pour partie réelle la fonction f(x) et pour partie imaginaire réelle la fonction g(x). h(x) = f(x)+i.g(x) (7) Le circuit classique fournit chaque valeur de la fonction transformée complexe H(u), pour u=O à N-1, en séparant sa partie réelle Re#H(u) ] et sa partie imaginaire Im [ H(u)j H(u) = Re[H(u)]+i.Im[H(u)] (8) Par ailleurs, la transformation de Fourier étant linéaire, la fonction H(u) peut être écrite comme étant une combinaison linéaire de la transformée F(u) de la fonction réelle f(x), et de la transformée G(u) de la fonction réelle g(x) H(u) = F(u)+i.G(u) (9) Les fonctions F(u) et G(u) étant complexes, il est nécessaire de faire apparaître leur partie réelle et leur partie imaginaire:: H(u) = Re[F(u)]-Im[G(u)]+i.[Im[F(u)]+Re[G(u)]] (10) Il est possible alors d'identifier les parties réelles, respectivement les parties imaginaires, des formules ( 10) et (8) Re = Re[F(u)]-Im[G(u)] (11) Im[H(u)] = Im[F(u)]+Re[G(u)] Il y a quatre inconnues à déterminer : Re[F(u)], Im[F(u)],Re[G(u)],Im[G(u)]. Il est donc nécesssaire de disposer de quatre équations. Deux autres équations peuvent être obtenues à partir des formules (11) et de la propriété de symétrie hermitienne exprimée par les formules (5) et (6) Re = Re[F(u)]+Im[G(u)] (12) Im[H(N-u)] = -Im[F(u)]+Re[G(u)] Les formules (11) et (12) permettent de déterminer les quatre inconnues.Celles-ci sont égales à Re[F(u)] = [Re[H(u)]+Re[H(N-u)]] (13) Im[F(u)] = [Im[H(u)]-Im[H(N-u)]] (14) Re[G(u)] = [Im[H(u)]+Im[H(N-u)]] (15) Im[G(u)] = [Re[H(N-u)]-Re[H(u)]] (16) Il apparaît que chaque inconnue peut être calculée au moyen d'une addition de deux termes ou dtune soustraction de deux termes, et au moyen d'une multiplication par 1/2. Considérons l'exemple de réalisation représenté sur la figure 1, où N ~ 512. Il comporte : un circuit classique 1 de transformation de Fourier d'une fonction complexe, réalisant une transformation sur 512 valeurs ; 1020 dispositifs pour diviser par deux une valeur binaire, D1,..., D510, D'1,. ., D'510 ; 508 additionneurs A1,..., A254, A'1,. ., A'254 ; 508 soustracteurs, SI 5254, S'1, . . ., S'254; et 4 registres pouvant stocker chacun 512 valeurs, RE2, IM1,RE1,IM2. Ces 4 registres constituent la sortie du dispositif de calcul. Le circuit 1 est représenté schématiquement par ses deux registres d'entrée et par ses deux registres de sortie. Il comporte une borne d'entrée 2 reliée à un registre d'entrée IME pour stocker la partie imaginaire d'une fonction complexe h(x) à tranformer, et il comporte une borne d'entrée 3 reliée à un registre REE pour stocker la partie réelle de la fonction complexe h(x) à transformer. Ces deux registres ont une capacité de 512 valeurs. Le circuit 1 comporte un registre de sortie IMS pour fournit les valeurs de la partie imaginaire ImlH(u)l de la fonction complexe H(u) transformée de la fonction h(x) ; et comporte un registre de sortie RES pour fournir les valeurs de la partie réelle RetH(u31 de la fonction transformée H(u) de h(x). Ces deux registres ont eux aussi une capacité de 512 valeurs.Par exemple, ce circuit classique 1 peut être constitué d'un circuit de transformation de Fourier commercialisé par la marque ZORAN, et du type ZDF 325. Dans cet exemple, les deux fonctions réelles à transformer sont deux fonctions f (x) et g(x), échantilionnées pour x=0 a 511. Par exemple, ce sont les valeurs de luminance de deux lignes d'image successives comportant chacune 512 pixels. Les valeurs de la fonction f (x) sont appliquées à la borne d'entrée 2, alors que les valeurs de la fonction g(x) sont appliquées à la borne d'entrée 3.Tout se passe, comme Si le dispositif 1 avait à calculer une fonction transformée H(u) d'une fonction complexe h(x) : f(x)+i.g(x) (7) 512 valeurs complexes de F(u) et 512 valeurs complexes de G(u) sont calculées å partir des 512 valeurs de ImtH(u)j et de 512 valeurs de Re [ H(u)1 que fournit le circuit 1. Considérons tout d'abord le calcul des valeurs de la partie réelle de la transformée de f(x), RetF(u) i' qui consiste à appliquer la formule (13). Les valeurs RelH(u) 7 et RetH(N-u)i, sont fournies par le registre RES a la sortie du dispositif 1. Elles sont situées dans deux cellules symétriques par rapport a. la cellule correspondant à u=257. Le multiplication par le facteur 1/2 est réalisée par l'un des dispositifs D'1, . . . ,D'510. Ces dispositifs sont très simples car 11 suffit de décaler d'un rang en permanence les bits vers les poids les plus faibles, pour diviser par deux la valeur d'un mot binaire.L'addition des deux termes de la formule (13) est réalisée au moyen de l'un des additionneurs A'1, . . ., A'254. Les valeurs de R[F(u)] sont stockées dans le registre de sortie REI. Un même additionneur fournit à la fois la valeur Re[F(u)] et la valeur Re [ F(N-u) I, par conséquent sa sortie est reliée à deux cellules du registre REI, correspondant respectivement à u et à 512-u. Par exception, les valeurs Re[F(0)] et Re[F(257)] sont obtenues directement sans passer par ces moyens de calcul car elles sont égales respectivement à Re[H(0)] et Re[H(257)]. Pour u différent de 0 et différent de 257, la valeur Re et la valeur ReiF(N-u) j sont fournies par la sortie d'un additionneur recevant sur deux entrées les valeurs l/2xRelH(u) ] et l/2xRetH(N-u) 1. Les valeurs de la partie imaginaire de la transformée de f(x), (lm(F(u)j, sont calculées conformément à la formule (14), au moyen des mêmes dispositifs D'1,...,D'510, et au moyen des soustracteurs S'1, . . . ,S'254, à l'exception des valeurs correspondant à u=O et u=257 qui sont toujours nulles et qui sont donc obtenues directement. Les valeurs Im [ G(u) et lm [ G(N-u) j sont fournies par la sortie d'un soustracteur recevant sur une première entrée (1/2)xIm[H(u)] et recevant sur une autre entrée, correspondant au terme à soustraire, la valeur (1/2)xlm[H(N-u)]. La sortie de ce soustracteur est reliée à la cellule du registre IM2 correspondant à u et à la cellule correspondant à 512-u.Les valeurs de Im[G(u)] sont stockées dans le registre de sortie IM2. Le registre RE2 fournit les valeurs de la partie réelle de la transformée de la fonction g(x), Re [ G(u)l ; alors que le registre IM1 fournit les valeurs de la partie imaginaire de la transformée de la fonction f(x), ImlF(u)l. Ces valeurs sont calculées conformément aux équations (15) et (16), au moyen d'un circuit analogue au circuit décrit précédemment pour le calcul de Re [ F(u) ] et Im [ G(u)l, respectivement. L'invention ne se limite pas à l'exemple de réalisation décrit précédemment, de nombreuses variantes sont à la portée de l'homme de l'art. Il est possible notamment de réaliser la multiplication par 1/2. non pas avant les additions et les soustractions, mals après. Le nombre N d'échantillons peut être une puissance de 2 quelconque. Le dispositif de calcul selon l'invention est applicable notamment aux traitements de signaux. En particulier, il est applicable aux traitements d'images, tels que le filtrage ou le recalage d'images. REVENDICATIONS 1. Dispositif de calcul simultané de deux fonctions transformées de Fourier de deux fonctions réelles, caractérisé en ce qu'il comporte - un circuit classique (1) de transformation de Fourier d'une fonction complexe, comportant un premier et un second registre d'entrée (REE, IME) recevant respectivement N valeurs d'une première fonction réelle (f(x)) et N valeurs d'une seconde fonction réelle (g(x)) à transformer, et comportant un premier et un second registre de sortie (RES, IMS) fournissant respectivement N valeurs de la partie réelle et N - valeurs de la partie imaginaire de la fonction transformée (H (u) ) d'une fonction complexe (f(x+i.g(x))) dont la partie réelle est constituée par la première fonction réelle (f(x)) et dont la partie imaginaire est constitué par la seconde fonction réelle (g(x)) - des premiers moyens de calcul (D'1 å D'510, A'1 à A'254) pour calculer la demi-somme de deux valeurs fournies par le premier registre de sortie (RES), pour déterminer chaque valeur de la partie réelle de la fonction transformée (F(u)) de la première fonction réelle (f(x)) - des deuxièmes moyens de calcul (D'1 à D'510, S'1 à S'254) pour calculer la demi-différence de deux valeurs fournies par le premier registre de sortie (RES), pour déterminer chaque valeur de la partie imaginaire de la fonction transformée (G(u)) de la seconde fonction réelles (g(x)) - des troisièmes moyens de calcul (D1 å D510, Ai à A254) pour calculer la demi-somme de deux valeurs fournies par le second registre de sortie (IMS) pour déterminer chaque valeur de la partie réelle de la fonction transformée (G(u)) de la seconde fonction réelle (g(x) des quatrièmes moyens de calcul (Dl à D250, S1 à S254) pour calculer la demi-différence de deux valeurs fournies par le second registre de sortie (IMS), pour déterminer chaque valeur de la partie imaginaire de la fonction transformée (F(u)) de la première fonction réelle (f(x)). 2. Dispositif selon la revendication 1, caractérisé en ce que le premier et le second registre de sortie (RES, IMS) possèdent chacun N sorties en parallèle ; et en ce que - les premiers moyens de calcul comportent : N/2-2 dispositifs de calcul d'une demi-somme (D'1,D'510,A'1), ayant deux entrées couplées respectivement à une u-ième et à une (N-u)ième sortie du premier registre de sortie (RES), et ayant une sortie fournissant le u-ième et le (N-u)ième valeur de la partie réelle de la fonction transformée (F(u)) de la première fonction réelle (f(x)), pour u variant de 1 à N/2 - les deuxièmes moyens de calcul comportent :N/2 - 2N/2-2 dispositifs de calcul d'une demi-différence (D'l,D'510,S'1) ayant deux entrées couplées respectivement une u-ième et a une (N-u)ième sortie du premier registre de sortie (RES), et ayant une sortie fournissant la u-ième et la (N-u)lème valeur de la partie imaginaire de la fonction transformée (G(u)) de la seconde fonction réelle (g(x)), pour u variant de 1 à N/2 - les troisièmes moyens de calcul comportent N/2-2 dispositifs de calcul d'une demi-somme (D1,D510,A1), ayant deux entrées couplées respectivement à une u-ième et à une (N-u)ième sortie du second registre de sortie (IMS), et ayant une sortie fournissant la u-ième et la (N-u)iême valeur de la partie réelle de la fonction transformée (G(u)) de la seconde fonction réelle (g(x)). pour u variant de la X,2 - les quatrièmes moyens de calcul comportent N/2-2 dispositifs de calcul d'une demi-différence (D1,D510,S1) ayant deux entrées couplées respectivement à une u-ième et une (N-u)ieme sortie du second registre de sortie (IMS). et ayant une sortie fournissant la u-ième et la (N-u)ième valeur de la partie imaginaire de la fonction transformée (F(u)) de la première fonction réelle (f(x)), pour u variant de 1 à N/2.