Brevet FR2608802A1 — publié le 19880624

CIRCUIT INTEGRE DE TRAITEMENT DE SIGNAL POUR LA SOMMATION EN LIGNE ET EN COLONNE DE MATRICES DE VALEURS NUMERIQUES L'invention concerne l'architecture des circuits intégrés effectuant un traitement numérique de signal d'un type particulier. Plus précisément, le traitement numérique considéré ici est une double sommation pondérée, en ligne puis en colonne, de valeurs numériques x(ij) d'une matrice de n x n valeurs numériques. A partir des coefficients x(i,J) o i est un indice de ligne de la matrice, et j un indice de colonne, on cherche à produire une matrice de coefficients C(u,v) o u est un indice de ligne et v un indice de colonne, avec i = n-1 C(uv) = FCi(v) g(i,u) - i=O j =n-1 avec Ci (V) = x (i,j) f(j,v) j=0 A partir de signaux électriques d'entrée représentant les valeurs numériques x(i,j), on produit d'abord n x n signaux représentants des coefficients Ci(v); chaque coefficient Ci(v) représente une sonmmation pondérée des valeurs x(i,j) de la ligne i affectées de coefficients ú (j,v); v représente un indice de colonne variant de O à n- 1 et il y a n coefficients Ci(v) pour chaque ligne d'indice i. Cette opération est appelée transformation ligne. A partir des n x n signaux représentant les coefficients Ci(v), on produit n x n signaux représentant les coefficients C(u,v); chaque coefficient C(u,v) est une sommation pondérée des valeurs Ci(v) de la colonne v, affectées de coefficients g(i,u); u représente un indice de ligne variant de O à n-1 et on produit n coefficients C(u,v) pour chaque colonne d'indice v. Cette opération est la transformation colonne. Ce type de traitement numérique se rencontre notamment pour réaliser des transformations dites transformations cosinus o les coefficients f(j,v) et g(i,u) sont de la forme cos (2i+1)uÂT/2n; ces transformations sont utiles pour faciliter la compression d'informations dans les transmissions numériques de signaux, et plus particulièrement pour la transmission numérique d'images. Les architectures de circuits intégrés permettant de réaliser ce type de transformation sont relativement complexes parce qu'elles doivent permettre un traitement en temps réel, c'est-à-dire que le débit de données numériques à traiter est imposé à l'entrée du circuit et le débit de données traitées à la sortie doit être aussi rapide que le débit à l'entrée. Bien entendu, ce débit est élevé et, à titre indicatif, pour la transmission numérique d'images, on veut pouvoir traiter un bloc de 16 x 16 valeurs numériques (256 points d'image) en moins de 20 microsecondes; des blocs successifs de 256 valeurs se présentant à l'entrée du circuit avec une périodicité de l'ordre de 20 microsecondes. La figure i représente sous forme de schéma-bloc une architecture de circuit intégré assez simple que l'on peut imaginer pour réaliser sur une même puce de circuit intégré la transformation complète d'un bloc de n x n valeurs numériques x(i,J) en un bloc de n x n coefficients C(u,v). Dans ce schéma, on utilise un premier opérateur CTL exécutant la sommation en ligne, un deuxième opérateur CTC exécutant la sommation en colonne, deux mémoires MEM 1 et MEM 2 pour le stockage de valeurs représentant les coefficients C (v), et deux aiguillages AIG 1 et AIG 2 pour établir des chemins de i connexion d'une part entre l'opérateur CTL et les mémoires MEM 1 et MEM 2 et d'autre part entre ces mémoires et l'opérateur CTC. L'ensemble est commandé par un séquenceur SEQ. Un bloc de n x n données x(i,3) à traiter est amené, par un bus d'entrée E, à l'opérateur de transformée ligne CTL qui produit n x n données numériques représentant n x n coefficients numériques C (v). Ces données sont stockées dans les n x n adresses de la mémoire MEM 1 (mémoire de n x n mots). Le rythme de traitement des blocs de n x n données est par exemple de un bloc traité par 20 microsecondes; une donnée x(i,j) se présente par exemple toutes les 74 nanosecondes (pour n x n = 256). Pour le traitement du bloc suivant de n x n valeurs x(i,j), le circuit CTL reçoit les valeurs successives x(l,j) et effectue la transformation ligne; mais cette fois, le séquenceur SEQ commande l'aiguillage AIGI de manière à stocker les résultats C1(v) dans la deuxième mémoire MEM 2. Pendant ce temps, les données précédemment enregistrées dans la mémoire MEM 1 sont appliquées à titre de valeurs numériques d'entrée à traiter, à travers l'aiguillage AIG2, au circuit de transformation colonne CTC qui produit à sa sortie les coefficients C(u,v). Ainsi de suite, alternativement, un bloc de n x n coefficients Ci(v) est stocké dans l'une des mémoires pendant qu'un bloc de coefficients Ci(v) enregistré à la période précédente dans l'autre mémoire est traité. Cette architecture est élégante mais nécessite deux mémoires i capables de stocker' chacune n x n données C (v). Il faut bien comprendre en effet que pour pouvoir effectuer une transformation colonne sur les coefficients C1(v) tous les coefficients C1(v) d'une même colonne v doivent être mémorisées. Or, comme ces coefficients C (v) arrivent du circuit CTL ligne par ligne, et non colonne par colonne,veut dire en pratique que la transformation colonne ne peut commencer que lorsque tous les coefficients Ci(v) de la matrice sont arrivés du circuit CTL. C'est la raison pour laquelle l'architecture de la figure 1 utilise deux mémoires fonctionnant alternativement. De plus, il faut noter que si les données C1(v) sont inscrites dans une mémoire ligne par ligne (i étant l'indice de ligne), alors elles doivent être lues à la période suivante colonne par colonne (v étant l'indice de colonne). L'invention proposée ici permet de se contenter d'une seule mémoire de n x n coefficients Ci(v). Elle économise donc une surface importante sur la puce de circuit intégré. Le circuit intégré de traitement numérique de signaux selon l'invention réalise, comme celui de la figure 1, une transformation de n x n signaux d'entrée représentant une matrice de valeurs numériques x(i,j) ou i est un indice de ligne et j un indice de colonne de la matrice, et il produit n x n signaux de sortie représentant des coefficients C(u,v), par une double sommation, en ligne et en colonne, de la forme n-1 C(u,v) = _ Ci(v) g (i,u) i = O 1=0 n-1 avec Ci(v) = x(i,j) f (j,v) j =0 Ce circuit comporte, - un premier circuit de sommation, apte à recevoir les signaux représentant les valeurs numériques x(i,j) et à produire des signaux représentant les coefficients C (v), - une mémoire apte à enregistrer les signaux C1(v) puis à les restituer, l'adressage de cette mémoire étant organisé en n lignes et n colonnes, - un deuxième circuit de sommation, apte à recevoir en i succession les signaux représentant les valeurs C (v) et A produire des signaux représentant les valeurs C (u, v), - un séquenceur d'adressage de la mémoire, pour fournir à la mémoire des adresses successives de données C (v) à enregistrer en provenance du premier circuit de sommation ou à restituer vers le deuxième circuit de sommation, - le séquenceur fournissant alternativement une succession de n x n adresses, ligne par ligne, puis une succession de n x n adresses, colonne par colonne, et une opération de lecture suivie d'une opération d'écriture étant effectuée pour chaque adresse fournie par le séquenceur. Dans un mode de réalisation préférentiel, la mémoire comporte deux bus de données séparés, l'un pour recevoir des données du premier circuit de sommation, l'autre pour fournir des données au deuxième circuit de sommation. Dans ce cas l'opération d'écriture peut commencer alors que l'opération de lecture n'est pas tout à fait terminée. Dans une autre réalisation, la mémoire ne comporte qu'un seul bus d'entrée/sortie de données et dans ce cas il faut s'assurer qu'on effectue la totalité de l'opération de lecture avant de commencer une opération d'écriture à la même adresse. La mémoire est de préférence une mémoire statique (SRAM). D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description détaillée qui suit et qui est faite en référence aux dessins annexés dans lesquels: - la figure 1, déjà décrite, représente une possibilité d'architecture de circuit exécutant une double sommation, en lignes et en colonnes, de valeurs numériques; - la figure 2 représente l'architecture selon l'invention pour exécuter le même traitement numérique; - la figure 3 représente schématiquement une partie du séquenceur d'adressage, servant à alterner l'adressage ligne par ligne et l'adressage colonne par colonne. - la figure 4 représente un diagramme temporel des signaux de lecture et écriture d'un mot de la mémoire. A la figure 1 on voit l'architecture de circuit selon l'invention. Les données à traiter x(i,j) sont amenées successivement, par un bus d'entrée E; une donnée arrive périodiquement (période T); un bloc de n x n données arrive avec une périodicité de Tech = n x n x T. Les données sont traitées par un premier circuit de sommation CTL effectuant une transformée ligne (sommation pondérée des données x(i,j) d'une même ligne d'indice i), aboutissant à la production de n x n coefficients Ci(v) sur un bus interne E1 qui relie la sortie du circuit CTL aux entrées de données d'une mémoire MEM de n x n mots. i Les coefficients C (v) stockés dans les n x n positions de la mémoire MEM peuvent être restitués sur un bus de sortie Si qui relie la mémoire à un deuxième circuit de sommation CTC effectuant une transformée colonne (sommation pondérée des coefficients Ci(v) d'une même colonne d'indice v). Ce deuxième circuit de sommation CTC produit des coefficients C(u, v), résultats de la transformation cosinus bidimensionnelle, sur un bus de sortie S. La mémoire et les circuits de sommation sont contrôlés par un séquenceur SEQ. Ce séquenceur sert en particulier à définir les séquences d'adressage des différentes positions de mots de la mémoire M, lors du stockage des coefficients Ci(v) et lors de leur restitution. Les adresses de ces positions sont définies par des mots de 2k bits (avec 2!= n) fournis par le séquenceur à la mémoire sur un bus d'adresses AD. Sur ces 2k bits, la moitié (c'est-à-dire les k premiers bits) définissent des poids forts de l'adresse et l'autre moitié (k bits également) des poids faibles de l'adresse. Par commodité, on appellera adresse de ligne les k bits de poids forts, et adresses de colonne les k bits de poids faible; cela permet d'imaginer la mémoire comme une matrice carrée de n x n points ayant la même structure que la matrice carrée de n x n coefficients Ci(v), chaque coefficient correspondant à un point. Bien entendu, la structure physique de la mémoire n'est pas forcément carrée. Selon l'invention, le séquenceur inverse périodiquement, avec une période Tech qui est la période d'arrivée de chaque nouveau bloc de n x n données à traiter, les adresses de ligne et de colonne dans la mémoire MEM. Autrement dit, alors que deux blocs successifs de n x n données x(i,j) sont traités de manière rigoureusement identique par le circuit CTL et que leurs résultats C1(v) doivent aussi être traités de manière rigoureusement identique par le circuit CTC, on prévoit que le stockage intermédiaire des coefficients Ci(v) correspondant au premier bloc se fait différemment du stockage des coefficients C 1(v) correspondant au bloc suivant. Les coefficients Ci(v), qui arrivent dans un certain ordre sur le bus El, sont stockés ligne par ligne dans la mémoire si c'est le premier bloc qui est traité; ils sont stockés colonne par colonne si c'est le deuxième bloc qui est traité; et ainsi de suite, il y a alternance de stockage en ligne puis en colonne, bien qu'il n'y ait aucun changement dans le traitement effectué par le circut CTL et bien que les données x(i,j) arrivent dans le même ordre sur le bus E. Ainsi, on peut supposer que les coefficients C1(v) arrivent dans l'ordre C (O), C0(1), C0(2)..... C0(n-1) puis C1 (0), C (1), C1(n-1) etc, et enfin Cn-1(O), cn-(1),... Cn-1 (n-l). Cela veut dire que les coefficients de la première ligne (indice i = O) de la matrice C1(v) arrivent d'abord, puis ceux de la deuxième ligne (i = 1), etc... puis ceux de la dernière ligne (i = n-l). Considérons le premier bloc de coefficients traités C i(v). Il sera stocké dans la mémoire en utilisant l'indice i (indice de ligne de la matrice numérique de coefficients Ci(v)) comme adresse de ligne de la mémoire, et l'indice v (indice de colonne de la matrice) comme adresse de colonne de la mémoire. Mais si c'est le deuxième bloc qui arrive, à la période Tech suivante, on utilisera l'indice de ligne i comme adresse de colonne et l'indice de colonne v comme adresse de ligne. Comme dans les deux cas les coefficients arrivent dans le même ordre CO(0), C0(1)... CO(n-l), C1(0), C1(1)... cl(n-1)... C n- (o), cn l(1), Cn-l(n-1), c'est le séquenceur qui doit faire une modification de la séquence d'adresses successives fournies à la mémoire. A titre d'exemple simplifié pour n = 4, le bloc traité est la matrice de coefficients suivants CO(0) C0(1) C0(2) C0(3) C1 (0) C (1) C1(2) C1 (3) C (0) C (1) C (2) C2(3) C3(0) C3(i) C3(2) C3(3) En supposant que le circuit CTL fournisse les résultats C1(v) dans l'ordre indiqué ci-dessus, le stockage s'effectue comme ci-dessous pour le premier bloc traité. adresse dans la mémoire poids forts poids faibles mots stockés C(0) o00 01 C (1) oO 10 C0(2) 00 11i CO(3) 01 00 C1(o) 01i 01 C(1) i 01 10 C1(2) 01 11 C1(3) o00 c2(0) 01 C2(1) 10 C2(2) 11 C2(3) il o00 c3(o) 11 01 C3(1) 11 10 C3(2) 11 11i C3(3) Mals pour le deuxième bloc traité le stockage s'effectue dans l'ordre ci-dessous adresse dans la mémoire mots stockés poids forts poids faibles 00 00 CO(o0) O1 O0 C0(1) 10 00 C0(2) 11 oo C (3) 00oo 01 C0(o) o1 01 C0(1) O1 C0(2) 11 O1 C0(3) 00 10 C0(O) O1 10 C0(1) 10 C0(2) il 10 CO(3) O0 11 CO(0) O1 11 C0(1) 11 C0(2) il 11 C0(3) Le tableau ci-dessus se déduit du précédent en permutant les colonnes poids faibles et poids forts. Cela revient virtuellement à stocker la matrice de coefficients Ci(v) sous la forme C0(0) C1() C2 (0) C3(0) C0(1) cl(1) c2(1) C3(1) C0(2) C1(2) C2(2) C3(2) C0(3) C1(3) C2(3) C3(3) Le circuit opère de la manière suivante Les données x(i,j) arrivent à la cadence de la période T les coefficients Ci(v) sont produits à la même cadence et stockés dans la mémoire toujours à la même cadence. Ils sont également lus à partir de cette mémoire à la même cadence et transmis au deuxième circuit de sommation CTC qui produit les coefficients C(u,v). A chaque période T, définissant la cadence de traitement, on exécute les deux opérations suivantes: - lecture d'un coefficient Ci(v) contenu dans la mémoire à l'adresse (r, s) fournie par le séquenceur; r représente les poids forts de l'adresse, s les poids faibles; le mot est transmis au circuit CTC par le bus S1 - écriture à la même adresse d'un nouveau coefficient Ci(v) fourni par le circuit CTL sur le bus El. Pendant toute une période Tech correspondant à un bloc de n x n données, les adresses (r, s) sont incrémentées de manière à effectuer un stockage ligne par ligne: s est incrémenté avec r constant, puis r est incrémenté etc... Pendant toute la période suivante Tech, correspondant au traitement du bloc suivant, les adresses (r, s) sont incrémentées de manière à effectuer un stockage colonne par colonne: r est incrémenté avec s constant, puis s est incrémenté etc.. On aboutit au résultat que le deuxième circuit de sommation CTC voit arriver une succession de coefficients transmis colonne par colonne s'ils ont été enregistrés ligne par ligne à la période précédente et réciproquement. Dans tous les cas on obtient que le circuit de sommation traite une matrice de coefficients colonne par colonne si cette matrice a été obtenue par une sommation ligne par ligne. Ceci est vrai même si les résultats Ci(v) du traitement par le premier circuit CTL sont produits et stockés dans un ordre autre que l'ordre banal indiqué ci-dessus (indice de colonne v croissant à i constant, puis indice i croissant). La seule condition à respecter est qu'en principe le circuit de transformation ligne qui fournit les coefficients Ci (v) ligne par ligne, établisse un ordre de ligne compatible avec l'ordre dans lequel ces coefficients, une fois prélevés par colonne, doivent être appliqués au circut CTC. Ainsi, en supposant que la deuxième sommation exige que les 4 coefficients Ci(v) de la colonne v arrivent dans un ordre brouillé CO(v), Cl(v), C3(v), C2(v), alors, il faut que le circuit CTL fournisse les lignes de coefficient Ci(v) dans le même ordre brouillé, à savoir successivement les lignes 0, 1, 3, 2. La constitution du circuit servant à fournir les adresses successives de la mémoire est extrêmement simple. Elle est visible à la figure 3. Le séquenceur comporte essentiellement un compteur CPT de 2 k + 1 bits pour une mémolre de n x n mots avec n = 2 k. La sortie du poids le plus fort commande un aiguillage MUX. Cet aiguillage reçoit les 2 k autres bits, en deux groupes de k bits, le premier groupe correspondant aux poids les plus forts et le deuxième aux poids les plus faibles. L'aiguillage a 2 k sorties, et, selon l'état du bit qui le commande, il restitue sur ses sorties soit les 2 k sorties du compteur dans leur ordre naturel, soit ces 2 k sorties croisées, les k bits de poids forts devenant k bits de poids faibles et réciproquement. Les 2k sorties de l'aiguillage MUX constituent les adresses (r, s) transmises à la mémoire. Le compteur est Incrnémenté par un signal d'horloge à une fréquence H correspondant à la période T d'introduction des données x(i,j) et de fourniture des résultats Ci(v). Toutes les 2 k périodes T, le sIquencement des adresses est modifié. La lecture d'un coefficient Cl(v) à une adresse (r, s) et l'écriture d'un autre coefficient à la mêmne adresse peuvent s'effectuer différemment selon les types de mémoires utilisées et notamment selon que les bus d'entrées et sortie E2 et S2 de la mémoire sont constitués par deux bus séparés ou par un bus unique multiplexé. S'il s'agit d'un bus unique, il est nécessaire que la lecture d'un mot soit complètement effectuée et terminée avant que l'écriture d'un autre mot ne commence. Il faut donc que la somme des phases de lecture à la phase d'écriture soit contenu dans la période T. En gros, il faut que la lecture ait lieu pendant une demi-période (par exemple 37 ns) et l'écriture pendant la demi-période qui suit. Comme la lecture et l'écriture sont elles-mêmes parfois divisées en sous-phases (précharge et lecture ou écriture proprement dite), on doit disposer d'une horloge de période T/2. Si les bus d'entrée et de sortie sont clairement séparés, un recouvrement partiel des phases de lecture et d'écriture est possible. Les phases peuvent être celles indiquées à la figure 4. La ligne a représente un signal d'horloge H à 13,5 Mhz dont la demi-période est T/2 = 37 ns. Le front descendant définit le déclenchement de la phase de lecture; une adresse (r, s) est supposée présente depuis le front montant précédent. La ligne b représente le bus de sortie Si: les données lues apparaissent environ 10 nanosecondes après le front descendant de H. Ces données restent bloquées sur le bus S1 jusqu'au front descendant suivant. Elles ne seront effectivement introduites dans le circuit CTC que pendant la deuxième période d'horloge. La ligne c représente un signal de validation d'écriture WE. Ce signal définit le moment pendant lequel les données à écrire, présentes sur le bus E1 après le front descendant de l'horloge H, sont reportées sur les lignes de bit de la mémoire. Le signal WE peut être activé par l'apparition de données lues sur le bus S1 et désactivé par le front remontant de l'horloge H. REVENDICATIONS 1. Circuit intégré de traitement numérique de signal, réalisant une transformation de signaux d'entrée représentant une matrice de valeurs numériques x(i,j), o i est un indice de ligne et j un indice de colonne de la matrice pour produire des signaux de sortie représentant des coefficients C (u, v), par une double sommation, en ligne et en colonne, de la forme i = n-1 C(u,v) =. Ci(v) g (i,u) i=O avec j = n-1 li c Ci(v) = 17x (i,j) f (jv) caractérisé en ce qu'il comporte - un premier circuit de sommation (CTL) apte à recevoir les signaux représentant les valeurs numériques x(i,j) et à produire i des signaux représentant les valeurs Cl(v) - une mémoire tampon (MEM) apte à enregistrer les signaux Ci(v) puis à les restituer, l'adressage de cette mémoire étant organisé en n lignes et en n colonnes - un deuxième circuit de sommation (CTL) apte à recevoir en succession les signaux représentant les valeurs Ci(v) et à produire des signaux représentant des valeurs C(u,v), - un séquenceur (CPT, MUX) d'adressage de la mémoire, pour fournir à la mémnoire des adresses successives de données Ci(v) à enregistrer en provenance du premier circuit de sommation ou à restituer vers le deuxième circuit de sommation, - le séquenceur fournissant alternativement une succession de n x n adresses, ligne par ligne, puis une succession de n x n adresses, colonne par colonne, et une opération de lecture suivie d'une opération d'écriture étant effectuée pour chaque adresse fournie par le séquenceur. 2. Circuit Intégré selon la revendication 1, caractérisé en ce que la mémoire comporte un bus d'entrée E1 et un bus de sortie S1, distincts l'un de l'autre. 3. Circuit intégré selon l'une des 'revendications i et 2 caractérisé en ce que le séquenceur d'adressage comporte un compteur de 2k + i bits dont la sortie de poids le plus fort commande un circuit d'aiguillage, les 2 k bits restants étant divisés en un groupe de k bits de poids forts et un groupe de k bits de poids faibles, et l'aiguillage étant apte à transmettre, selon l'état du bit qui le commande, soit les deux groupes tels qu'ils apparaissent en sortie du compteur, soit les deux groupes permutés. 4. Circuit intégé selon l'une des revendications i à 3, caractérisé par le fait que la mémoire est une mémoire statique.