FR 2618925 A1 19890203 FR 8710821 A 19870730 Dispositif de calcul numérique Pour installation de transmission de données en code 2B 10 ou analaogue. L'invention concerne les dispositifs de calcul numérique permettant de calculer en temps réel une somme de termes de la forme: Eh(iT).e((n-i)T) dans laquelle T désigne une période d'échantillonnage, - h(iT) des coefficients, et te les valeurs estimées de données émises qe pouvant prendre les valeurs -3, -1, +3 et+1. Le problème du calcul d'une telle somme se pose notamment dans la réalisation de filtres linéaires utilisables dans des annuleurs d'écho (qu'on désignera par la suite par l'abréviation habituelle ECC) pour installation de transmission numérique de données en code 2B1Q. On sait que ce code, susceptible d'être adapté comme standard à la suite de la normalisation de l'interface U aux Etats- Unis, associe à chaque ensemble de deux élément binaires, dit "dibit-", un niveau parmi quatre, suivant le tableau: dibit niveau émis 00 -3 01 -1 +3 11 +1 Les données émises en ligne qe(t) peuvent donc prendre les quatre valeurs ci-dessus. Dans une installa- tion de transmission dont la chaine a une réponse impul- sionnelle h(t), le signal sr(nT) reçu à l'instant nT est: sr(nT) = E h(iT) .qe((n-i)T) (1) i=O La recherche de valeurs estimées qe de qe impli-- que, dans une installation de réception, de calculer des sommes de la forme (1). Par exemple chaque fois que les lignes de transmission sont hétérogènes, la décision sur la valeur de qe(nT) ne peut être faite qu'après avoir soustrait, du signal reçu sr(nT), une estimation de l'interférence intersymbole, ou ISI, dont la valeur exacte serait: N E h(it) * qe((n-i)T) i=i L'estimation est classiquement faite par un égaliseur récursif adaptatif à décision dans la boucle, fréquemment désigné par l'abréviation DFE, à N coeffi- cient qui calcule le terme Tr(nT): N Tr(nT) = E h(iT). qe((n-i)T (2) i=1 o h(iT) est le ième coefficient mémorisé dans le DFE (généralement adaptatif), constituant une estimation du ième échantillon de la réponse impulsionnelle h(t). Le calcul numérique de Tr(nT) impose, si on applique la formule (2): A N multiplications h(iT) * qe((n-i)T), et N additions Si on tient compte du fait que la donnée estimée qe peut prendre les valeurs +3, +1, -3 et - 1 et est donc codée sur 2 bits, on peut décomposer chaque multiplica- tion en deux additions et un décalage: l'opération 3 * h(iT) devient par exemple: h(iT)) + 2 * h(iT) Mais si on peut, grace à cette transformation utiliser un dipositif de calcul sans multiplieur, on double le temps de calcul qui passe de N à 2N cycles. L'invention vise à fournir un dispositif qui tout à la fois ne comporte pas de multiplieur et n'allonge pas sensiblement le temps de calcul. Pour cela elle part d'une analyse complète de la chaine de trans- mission et de ses composants, permettant de mettre l'équation (2), ou l'équation correspondante que l'on trouve dans le cas d'un ECC, sous une forme comportant des termes que l'on peut négliger sans conséquences défavorables. Une première étape consiste à introduire une variable qde = 1+qe qui, du fait que qe prend les valeurs +3, +1, -3,r -1, ne pourra prendre que les valeurs +4, +2, -2, O qui sont des puissances de 2. L'équation (2) qui donne Tr(nT) devient, en fonction des valeurs qde((n-1) T): N Tr(nT) = E h(iT) [q'e((n-i)T)-l] (3) i=l qu'on peut encore écrire: N ^ Tr(nT) = E h(iT). qe((n-i)T) N - E h(iT) (4) i=1 Le second terme de l'équation (4) peut être transformé si on tient compte que, la chaine de trans- mission ne laissant pas passer la composante continue du signal, le gain total de la chaine E h(iT) i=o pour cette composante est nul. Or ce gain peut s'écrire N h(O) + E h(iT) + E h(iT) = O (5) i=1 i=N+1 Par ailleurs, le terme E h(iT) i=N+1 peut être négligé, car dans un DFE ayant N coefficients on admet que la valeur de la traînée au delà de NT n'a pas à être prise en considération. L'équation (5) fait donc apparaître qu'on peut remplacer N ^ - E h(iT) i=1 dans (4) par h(0). L'équation (4) devient donc N) Tr(nT) = h(iT). qde((n-i)T) + h(O) (6) i=1 Le premier terme de l'équation (6) se calcule par N additions et des décalages éventuels suivant la valeur de qde, puisque qde est toujours une puissance de 2; l'addition du second terme se traduit par un allon- gement d'un seul cycle de calcul. Au total il suffit N+1 cycles suffisent au lieu de 2N cycles dans le cas de l'équation (2). En conséquence l'invention propose un dispositif de calcul comprenant des moyens pour transformer les valeurs qe en des valeurs qde qui sont des puissances de 2, par addition ou soustraction d'un même nombre à tou- tes les valeurs; des moyens pour calculer les produits élémentaires obtenus par des décalages éventuels de h suivant la valeur de qde; des moyens pour faire la som- me des produits élémentaires et des moyehs pour y ajou- ter éventuellement une constante constituant une évalua- tion de la différence de résultat dû au changement de variable. Dans le cas évoqué ci-dessus o le dispositif constitue un égaliseur récursif adaptatif fonctionnant suivant l'équation (6) ladite constante constitue une évaluation évaluation h(0) du premier terme de la fonction de transfert. Les valeurs h peuvent être adaptées en permanence par un réseau de type connu, utilisant par exemple l'algorithme du gradient ou du signe. Dans le cas o le dipositif doit être utilisé comme annuleur d'écho, l'écho synthétisé Ec(nT) est donné par une formule similaire à l'équation (2), faisant intervenir N coefficients évalués qui seront désignés par (iT). N-1 Ec(nT) = E g(iT) * qe((n-i)T) (2 bis) i=O avec qe = +3, +1, -1 ou -3. Là encore, pour calculer Ec(nT) par cette formu- le sans multiplication, il faudrait 2N cycles de calcul. Un dispositif suivant l'invention effectue un changement de variable sur les données émises qe: on pose qde"n-i)T) = 1 + qe((n-i)T) qde ne peut alors prendre que des valeurs +4, +2, 0 et -2. L'écho s'écrit N-1i Ec(nT) = g(iT) * [qde((n-i)T)-l] (3 bis) i=O ou encore N-1 N-i Ec(nT) = E 9(iT) * qde((n-i)T) - E t(iT) (4 bis) i=O i=O Le second terme de l'équation peut être remplacé par E (iT) i=N car le gain de la chaine d'écho & fréquence nulle A E g(iT) i=O est nul, or dans un annuleur d'écho de longueur NT, on admet que l'énergie d'écho est nulle au delà de NT, donc que E CiT) = O i=N L'écho Ec(nT) se limite donc au premier terme de l'équation (4 bis) c'està-dire à N-1 Ec(nT) = E (iT). qde((n-i)T) (6bis) 1-0 On peut encore poser ici q'de(i) = 1/2 qde(i) et dans ce cas q'de(i) peut prendre uniquement les va- leurs -1, O, 1 ou 2; et si on utilise des coefficients g'(i) = 2g(i) l'équation (6 bis) peut s'écrire N-i1 Ec(nT) = E g'(iT). q'de((n-i)T) (6 ter) i=O On constate ainsi que, moyennant la mémorisation des coefficients d'ECC doubles, les produits qui inter- viennent dans la somme peuvent être implantés: - par génération de zéro pour qde = O, - par transparence (égalité de la sortie et de l'entrée avec changement de signe éventuel) pour qde = 2 ou -2, 0 - par décalage d'un bit vers les poids forts pour qde = 4. L'invention sera mieux comprise à la lecture de la description qui suit d'un mode particulier d'exécu- tion de l'invention, donné à titre d'exemple non limitatif et à la comparaison qui en est faite avec un dispositif connu. La description se réfère aux dessins qui l'accompagnent dans lesquels: - la figure 1 est un schéma de principe d'un dispositif de calcul utilisable dans un ECC, de type connu; - la figure 2 similaire à la figure 1, est un schéma'd'un ECC suivant l'invention. Le dispositif de la figure 1, qu'on supposera destiné à calculer en temps réel des valeurs successives estimées d'un écho Ec(nT) met en oeuvre la fonction (2 bis) ci-dessus, c'est à dire: N-1 Ec(nT) = E g(iT). qe((n-i)T) i=O o g(iT) pour i=O,..., N-1 sont les N coefficients du filtre d'écho, qe((n-i)T) pour i=O,..., N-1, sont les N dernières données émises en code 2B1Q. Pour simplifier l'écriture, on utilisera dans ce qui suit la notation qe(n-i) au lieu de qe((n-i)T). Le dispositif montré en tigure i comporte une mémoire 10 de stockage des coefficients g(iT). Cette mémoire sera généralement une mémoire vive associée à un filtre adaptatif de calcul des coefficients par un algo- rithme d'adaptation qui peut être connu. On trouvera des exemples de tels filtres dans de nombreux documents, tels que par exemple le document US-A4 564 934 (MACCHI). Une seconde mémoire vive 12, comportant souvent un registre à décalage, reçoit les N dernières données estimées qe(n-i), codées sur 2 bits en 2B1Q. Les entrées d'un multiplieur 14 sont reliées l'une au bus de données 16 de la mémoire 10 des coeffi- cients, l'autre au bus de sortie 18 de la mémoire de données 12. Le bus 20 du multiplieur est relié à une des deux entrées d'un circuit additionneur/soustracteur 22. Un registre 24 d'accumulation de résultats fourni par l'additionneur/soustracteur est placé à la sortie de ce dernier. Il contient en permanence le résultat de la dernière opération et alimente un second registre 26 et la seconde entrée de l'additionneur/soustracteur. Le second registre 26 mémorise le contenu du registre 24 lorsque celui-ci contient le résultat final de l'opéra- tion: il contient alors le résultat Ec(nT) qui peut alors être lu soit par un autre calculateur, soit par un convertisseur numérique/analogique (non représenté). Un circuit 28 constituant base de temps et contenant une mémoire de programme permet de séquencer les opérations de calcul en activant les circuits 10, 12, 22, 24 et 26. La somme: N-1 Ec(nT) = E g(iT). qe(n-i) i=O est calculée en N cycles de calcul de la façon suivante, après remise à zéro de 24 et 26 par la base de temps. Cycle 1 lecture de g(O) et de qe(nT) dans les mémoires 10 et 12; multiplication de g(0) par qe(n) dans 14; écriture du résultat g(O).qe(n) dans le registre 24. Cycle 2: lecture de 9(1T) et de qe(n-1) dans les mémoires; multiplication de g(1T) par qe(n-1); addition de la sortie du multiplieur avec le contenu du registre 24, c'est-à-dire g(O).qe(n); écriture du résultat dans le registre 24. Cycle N: lecture de g((N-1)T) et de qe(n-N+1) dans les mémoires; multiplication de g(N-1) par qe(n-N+1); addition de la sortie du multiplieur avec le contenu du registre 24 N-2 E g(j)qe(n-j) j=O écriture du résultat n-1 E g(j)qe(n-j) j=0 dans le registre 24. Enfin, à l'issue du Nème cycle, la base de temps provoque le transfert du résultat du registre 24 au registre de sortie 26. Le dispositif suivant l'invention montré schéma- tiquement en figure 2 permet de remplir la même fonction que celui de la figure 1, sans augmentation du volume de mémoire nécessaire au calcul de Ec(nT), avec le même nombre N de cycles de calcul pour chaque valeur et sans multiplieur. Sur la figure 2, la base de temps et la mémoire de programme n'ont pas été représentées pour plus de simplicité. Les organes correspondant à ceux de la fi- gure 1 portent le même numéro de référence. De plus, pour illustrer la disposition de l'annuleur d'écho dans une station, la figure 2 montre schématiquement un émetteur 30 fournissant les données successives qe(nT) vers une ligne de transmission 32. Un échantillonneur 34 prélève des échantillons successifs qui sont mémorisés dans la mémoire 12 munie d'un additionneur et d'un diviseur par 2 permettant d'obtenir q'de. Les signaux provenant de la ligne sont appliqués au récepteur 36 par l'intermédiaire d'un organe de calcul 38 constituant additionneur dont l'entrée additive reçoit des échantil- lons découpés sur le signal reçu par un échantillonneur et l'entrée soustractive, la sortie de la mémoire 26. En général le dispositif comportera un circuit 42 d'a- daptation des coefficients g(iT) de l'annuleur d'écho. Cette disposition de l'annuleur d'écho dans une station d'émission/réception. associée à une ligne de transmission en duplex est classique: on pourra en trouver une description plus complète, en cas de besoin, dans l'article de FALCONER et autres "Adaptive echo cancellation AGC structures for two wire full duplex data transmission" dans Bell Technical Journal, volume 58, n'7, septembre 1979, page 1593 ou dans le brevet US 4 564 934 déjà mentionné. Le dispositif de la figure 2 calcule l'écho Ec(nT) en appliquant la formule (6 ter) ci-dessus. Le multiplieur 14 est remplacé par un circuit 44 très simple, puisqu'il applique, au coefficient g(iT), l'une de trois fonctions, sélectionnée par les deux bits de données correspondant à q'de qui est obtenu par simple décalage des valeurs qde d'une position vers la droite. Les trois opérations possibles sont: - transfert pur et simple de l'entrée vers la sortie (fonction transparence) équivalente à- une multiplication par 1, lorsque q'de(n-i) = 1 ou -1; -.décalage de la donnée de 1 bit vers les poids forts, équivalent à une multiplication par 2,.lorsque A q'de(n-i) = 2; - génération d'un zéro en sortie, c'est-à- dire multiplication par zéro ou effacement, lorsque q'de(n-i) = 0. De plus, une opération de changement de signe doit être effectuée lorsque q'de = -1. On voit que chaque opération est réalisable en un seul cycle. Par exemple le cycle i+1 est le suivant: lecture de ''(iT) et q'de((n-i)T) dans les mémoires, décalage de g'(iT) par 1 bit, ou génération de zéro, ou "transparence"; addition de la sortie de 44 avec le contenu du registre 24; écriture du résultat dans le registre 24. Cette suite d'opérations pour i = O à N-1 réalise le calcul décrit dans l'équation (6 ter). Par conséquent, sans utiliser de multiplieur, on effectue le calcul en seulement N cycles. Le calculateur fonctionne donc à la même vitesse que dans une réalisa- tion classique, et la quantité de mémoire programme requise ne change pas. Un dispositif égaliseur ayant la même constitu- tion que l'annuleur d'écho montré schématiquement en figure 2 pourrait être réalisé. Le fonctionnement cor- respond alors à la formule (6) ci-dessus et la seule opération supplémentaire requise consiste en l'addition du terme estimé h(O) qui dans certains cas pourra être fixé une fois pour toute mais, plus fréquemment, sera en permanence adapté en même temps que les coefficients h(iT) sur la base d'un algorithme classique, tel que l'algorithme du gradient ou du signe. L'invention ne se.limite pas aux deux applica- tions particulières qui ont été données à titre d'exemple et il doit être entendu que la portée du présente brevet s'étend à tout dispositif restant dans le cadre des équivalences. ll REVENDICATIONS 1. Dispositif de calcul numérique permettant de calculer en temps réel une somme de termes de la forme: Eh(iT).qe((n-i)T) dans laquelle T désigne une période d'échantillonnage, h(iT) des coefficients, et qe les valeurs estimées de données émises qe pouvant prendre les valeurs -3, -1, +3 et+1, caractérisé en ce qu'il comprend: - des moyens pour transformer les valeurs qe en des valeurs qe qui sont des puissances de 2,par addi- tion ou soustraction d'un même nombre à toutes les valeurs; - des moyens pour calculer les produits élémen- taires obtenus par des décalages éventuels de h suivant la valeur de qde; - des moyens pour faire la somme des produits élémentaires; et - des moyens pour ajouter éventuellement à la somme une constante constituant une évaluation de la différence de résultats due au changement de variable. 2. Dispositif selon la revendication 1, carac- térisé en ce que les moyens pour transformer les valeurs qe en des valeurs qde sont constitués par un addition- neur (12) ajoutant +1, suivi d'un diviseur par 2 qui forme la valeur q'de égale & 2, 1, O ou -1. 3. Dispositif selon la revendication 2, carac- térisé en ce que les moyens pour calculer les produits élémentaires sont constitués par un circuit (44) per- mettant, suivant la valeur de q'de, d'appliquer à h une des trois fonctions: - transfert de l'entrée vers la sortie, - décalage de 1 bit vers les poids forts, - génération de zéro en sortie. 4. Dispositif annuleur d'écho selon la revendi- cation 2 ou 3, caractérisé en ce qu'il comprend des moyens (34) d'échantillonnage des signaux qe émis à partir d'une station et d'envoi des échantillons auxdits moyens pour transformer les valeurs qe en des valeurs q'de = 1/2 (qe +1), en ce que les moyens pour faire la somme des produits élémentaires comprennent un registre (24) et un additionneur dont la sortie est reliée à l'entrée du registre (24) de totalisation et dont les entrées sont reliées l'une à la sortie des moyens (44) de calcul des produits élémentaires et l'autre à la sortie du registre (24).