93

Architecture hautement concurrente de I'algorithme des moindres carres moyens*

Highly parallel architecture for the least mean squares (LMS) algorithm*

Marcel Lapointe, Huu Tue Huynh et Paul Fortier, Departement de genie electrique, Faculte des sciences et de genie, Universite Laval, Quebec G1K 7P4.

Les auteurs proposent dans cet article une realisation numerique rapide de ralgorithme des moindres carres moyens (MCM). La tres haute concurrence qui la caracterise autorise une periode d'echantillonnage de 0(log N), ou N est le nombre de coefficients. L'encombrement des circuits lie normalement a une haute concurrence, est minimise par l'usage de multiplieurs series-paralleles. Une particularite des multiplieurs utilises ici reside dans la circulation des variables series qui se fait en commen^ant par le chiffre de poids fort. Cette structure est rendue possible avec l'aide des arithmetiques redondantes.

In this paper, a fast digital implementation for the least mean squares (LMS) algorithm is proposed. The high concurrency of its structure allows for high processing speed with a sampling period of 0(log N), where N is the number of filter taps. Chip area is minimized by the use of serial-parallel multipliers. In these multipliers, which use redundant arithmetic, the serial variables are transferred digit by digit, the most significant first.

Introduction

La mise en oeuvre numerique de ralgori thme des moindres carres moyens^ (MCM) 1 est souvent realisee a l'aide d 'un processeur, genre DSP (Digital Signal Processor) par exemple. Malheureuse-ment, comme l ' implantation est souvent de nature sequentielle, ce type de realisation limite fortement les applications aux seuls domaines audio et vocal. 2 Pourtant la gamme d'applications pourrait utilement s'etendre a des frequences bien plus elevees si la realisation se faisait en mode parallele. Par exemple, N multiplieurs fonctionnant en parallele seraient utilises pour le calcul de la convolution et N autres, pour le calcul de l 'adaptation. Le point d 'ombre de cette approche, cependant, est qu'elle exige de nombreux circuits et aboutit a un encombrement extreme des bus de communication. En d'autres termes, on peut s 'attendre a une tres grande complexite de cette realisation.

L'approche parallele presentee dans cet article attenue ces difficultes en faisant appel a des multiplieurs series-paralleles. Ces derniers sont plus simples que les multiplieurs en tableau et, de ce fait, peuvent etre integres en plus grand nombre dans un meme micro-circuit, diminuant du meme coup la complexite globale de la realisation. Mieux encore, la circulation en serie de certaines variables autorise la simplification des bus, amenant un encombre­ment moindre de ceux-ci. U n e particularite des multiplieurs utilises ici est que la circulation s'effectue en commengant par le chiffre de poids fort. La cascade de tels multiplieurs permet alors le chevauchement d 'une succession de calculs, accroissant du meme coup la concurrence par l 'etablissement d 'une structure en pipeline.

Le processus de multiplication se fait habituellement en deux etapes : les produits partiels sont d 'abord generes, puis sommes iterativement. Lorsque la sommation des produits partiels se fait

dans un ordre croissant, la partie poids faible du resultat se stabilise au fur et a mesure que Fiteration progresse. De fac,on similaire, la sommation des produits partiels dans un ordre decroissant amenerait Femergence chiffre par chiffre du resultat, poids fort d 'abord. Mais ceci n'est envisageable que dans la mesure ou une arithmetique redondante est utilisee. En effet, la propagation de la retenue dans une telle arithmetique est limitee, typiquement, a une position seulement. 3 Par consequent, la somme des produits partiels qui restent a sommer apres un pas donne de Fiteration, ne peut affecter la partie deja extraite du resultat. U n nouvel algorithme, dit de Faccumulateur, est propose pour la realisation de cette operation. II permet de construire facilement ce type de multiplieur, de maniere systematique. 4 " 5

Le fait done de realiser I'algorithme M C M en mode parallele permet un gain appreciable de la rapidite d'execution. Cependant, la boucle de recursion qui existe a Finterieur de I'algorithme est une autre embuche a la rapidite. En effet, le calcul de la convolution qui s'effectue avec Farrivee du nouvel echantillon Xt{n -f 1) ne peut debuter tant que les valeurs corrigees des coefficients Q ( « + 1) ne sont pas fixees. II importe done de rendre disponible ces valeurs le plus tot possible. On y arrive par le chevauchement des calculs successifs. La realisation de I'algorithme M C M se fait done en trois etapes. D 'abord les termes de la convolution sont calcules en parallele. Ensuite un dispositif de sommation calcule leur somme, generant simultanement la reponse du filtre et Ferreur d'estimation. Finalement les coefficients sont ajustes (ou adaptes) en parallele. La structure des divers organes de calcul est telle que les resultats respectifs des trois etapes emergent chiffre par chiffre, poids fort d 'abord. II est alors aise de disposer en cascade ces organes en formant une structure en pipeline de trois niveaux. De cette maniere, les resultats de la derniere etape emergent avant meme que ne soit termines les calculs de la premiere etape, rendant ainsi disponible les valeurs des coefficients tres tot apres la reception d'un nouvel echantillon.

* This work was presented at the 15 t h Biennial Symposium on Communications, Kingston, Ontario, June 3-6, 1990. * Ce travail a ete presente au 15 t h Biennial Symposium on Communications, Kingston, Ontario, 3-6 juin 1990. f En anglais: "Least Mean Squares" (LMS).

Can. J. Elect. & Comp. Eng., Vol. 16 No. 3, 1991

94 CAN. J. ELECT. & COMP. ENG., VOL. 16, NO. 3, 1991

L'algorithme M C M est presente brievement a la deuxieme section. Les proprietes de Parithmetique redondante sont exposees a la troisieme section. La quatrieme section donne une breve description de ralgori thme de l 'accumulateur a partir duquel sont construits deux multipheurs series-paralleles et un sommateur dont les structures sont presentees a la cinquieme section. Ces multipheurs sont finalement utilises a la sixieme section pour la realisation du filtre adaptatif M C M . Les avantages remarquables de cette architecture sont discutes a la septieme section. L'article se termine par une conclusion a la huitieme section.

Algorithme MCM

L'algorithme M C M est defini par les trois equations qui suivent.1

D 'abord, une convolution est effectuee entre les echantillons decales d 'une signal X et les coefficients d 'un filtre transversal de longueur TV :

N-\

Y(n) = 2 Xt(n) ' Qin). i=0

On a ici substitue Xt(n) a X(n — i). La reponse du filtre Y(n) est ensuite comparee a un signal secondaire Z(n), dit de reference, pour produire une erreur d'estimation :

E(n) = Z(n) - Y(n). (2.2)

Tableau 1 Codage des chiffres de la numeration binaire

redondante chiffre code

r s

0 0 1 0 1 0

P2 - P { + 1 > b. (3.2)

Les chiffres Xj appart iennent a un repertoire de nombres entiers consecutifs variant entre px et p 2 . Le facteur b represente la base de la numeration. Le parametre m indique la taille du nombre. On doit noter que, dans les cas pratiques, le repertoire est souvent symetrique autour de zero. On a alors :

xj e { - p , . . . , p } (3.3)

avec les conditions suivantes :

~2 < p < b - 1. (3.4)

Cette variable sert alors a corriger graduellement les coefficients vers des valeurs optimales de maniere a ce que l'erreur quadrat ique moyenne* se rapproche de son minimum. L'algorithme d'adapta-tion s'ecrit comme suit :

L'inegalite de gauche etablie le redondance tandis que l'inegahte de droite force la representation du nombre zero, une exception dans ce cas precis, a etre unique. On dira que la redondance est minimale lorsque p = b/2, et maximale lorsque p — b— 1. Deux exemples de numerat ions en base 4 sont donnes :

Ci(n + 1) = Ct{n) + iiE(n) • Xt{n). (2.3)

La vitesse a laquelle ralgori thme convergence est proportionnelle a la valeur du pas d'incrementation JU. Ce parametre doit obeir a la condition suivante pour assurer la convergence :

(2.4)

Le terme tr[R] represente la trace de la matrice d'autocorrelation du signal X. Sachant que cette trace est egale a N fois la puissance moyenne du signal X, la relation (2.4) peut egalement s'ecrire :

0 < /x < — (2-5) N • P

oil P est la puissance moyenne du signal.

Arithmetique redondante

Les numerations redondantes sont caracterisees par un repertoire de chiffres dont la taille est superieure a la base. De fa9on generale, un nombre redondant est represente comme suit :

m

X = 2 b~jxj9 Xj e { p b . . . , p 2 }

avec la condition

(3.1)

m

X = 2 A~Jx: ; X i g { - 2 , . . . , 2} ,

7=1

m

X = 2 4--/JC.- ; X.- e { - 3 , . . . , 3}. 7=1

(3.5)

(3.6)

La premiere est a redondance minimale tandis que la deuxieme est a redondance maximale.

U n e premiere propriete des numerations redondantes est le fait de pouvoir representer une valeur donnee par plusieurs nombres. Par exemple, la valeur 6 pourra etre representee en base 4 comme suit :

6 = (0 1 2 ) 4 = (0 2 2 ) 4 = (1 2 2 ) 4 .

Le trait sur un chiffre indique une valeur negative. On peut constater que plus p est grand, plus il y a de fac,ons differentes de representer une valeur donnee, et ainsi plus la redondance est forte. On a l 'habitude de mesurer la redondance par le facteur de redondance K, defini comme suit :

(3.7)

U n e deuxieme propriete des numerations redondantes est leur faculte de s'affranchir de la propagation de la retenue pendant une

* En anglais: "Mean Square Error" (MSE).

AT = — 2 — . b - 1

2 0 < u < .

tr[R]

LAPOINTE/HUYNH/FORTIER: ARCHITECTURE HAUTEMENT CONCURRENTE 95

A, C : binaire redondant B : complement h deux

Figure 1: Additionneurs binaires: (a) Redondant; (b) Hybride.

addit ion. 3 U n exemple est donne avec la numeration binaire redondante*. Celle-ci est caracterisee par une base egale a 2, avec un repertoire de trois chiffres, symetrique autour de zero :

* = 2 2~jxj9 Xj e { - 1 , 0 , 1}. 7=1

(3.8)

(p. fort) (p. faible)

ai

1 1 "2 1 | II II

U T

u T

U U T T ' t •

C2

T t

c 3 c 4

Figure 2: Convertisseur de binaire redondant d complement a deux.

sortie. Cela montre done que la propagation de la retenue se limite a deux positions seulement.

Ment ionnons que le couple de bits (1 ,0) situe sur le cote droit de F addit ionneur represente, selon le tableau 1, le chiffre 0. Ce chiffre joue un role analogue a celui de la retenue entrante d'un addit ionneur plus traditionnel. On pourrait, par exemple, placer le couple (0, 0), lequel code le chiffre — 1, et provoquer ainsi une soustraction de 1 a la position de poids faible. Cette particularite sera utile plus loin.

U n autre exemple d 'addit ionneur a redondance est donne a la figure lb . Cette fois les operandes sont mixtes : le nombre A est en binaire redondant tandis que B est en complement a deux. Le resultat C est toujours en binaire redondant . La propagation se limite dans ce cas a une position seulement. On souligne que, pour les deux additionneurs, le temps d'execution est court et constant, peu importe la taille des variables, ce qui rend 1'addition parfaitement parallele. Mentionnons egalement la presence du signal Inc a la droite de Fadditionneur hybride. Son role est de provoquer une addition de 1 a la position de poids faible.

U n troisieme dispositif est presente a la figure 2. II effectue la conversion d 'un nombre binaire redondant, A, en un nombre complement a deux, C. Comme le resultat est en numeration traditionnelle, on ne peut s'affranchir de la propagation de la retenue. Soulignons le fait que, encore une fois, on fait usage ici de cellules d 'addition traditionnelles.

Les trois dispositifs precedents seront utilises a la cinquieme section pour la realisation de deux multiplieurs et d 'un troisieme organe de calcul appele sommateur.

Algorithme de Paccumulateur

On peut montrer qu 'un additionneur fonctionnant avec cette numeration peut etre realise a partir de cellules d'addition traditionnelles^ celles utilisees couramment en arithmetique binaire traditionnelle. 4" 5 C'est ce que montre la figure l a ou les operandes A et B sont additionnees pour dormer le resultat C. Comme le repertoire est compose de trois chiffres, deux bits sont necessaires pour coder un chiffre. C'est ce qui explique l'existence de deux lignes par chiffre. Le codage utilise est celui du tableau 1. II est facile de constater a la figure l a que Finfluence d 'un chiffre a Fen tree ne depasse jamais deux positions vers le poids fort a la

A Fencontre de ce qui se fait traditionnellement, le processus de multiplication est effectue ici en sommant les produits partiels dans un ordre decroissant. Cette procedure permet d'extraire le resultat chiffre par chiffre, poids fort d 'abord, a mesure que les produits sont sommes. La bonne marche de cette procedure exige que la numerat ion a t t r ibute au resultat soit redondante, ceci afin de s'affranchir de la propagation de la retenue. Un algorithme a ete conc,u specialement a cet effet pour mener a bien cette procedure. Precisions, toutefois, que le concept de sommation des produits partiels est generalise a celui d 'une accumulation de termes

* En anglais: "Signed-Digit Binary Notation" (SDBN). f En anglais: "Full-Adder Cells".

(p. fort) (p. faible)

b\ b2 &3 &4

a\ #2 a3 a4

(a) (+) \ 3 & 0

1 (°) CO c l c2 C3 c4

A, B, C : binaire redondant

(p. fort) (p. faible)

bQ b\ bi 63 £>4

a\ «2 a3 a4

c0 c l c2 c3 c4

96 CAN. J. ELECT. & COMP. ENG., VOL. 16, NO. 3, 1991

Venant du ponderateur precedent Multiplicateur X,-(«)

Vers le ponderateur suivant

Vers le correcteur Venant du correcteur

I 1 1 : 1 Multiplicande C/(«)

n n ... "... „ . ... . . ' ^

!0 i o Initialisation

Extrait w, ,*

Vers le sommateur Residu moins l'extrait

Multiplicande : binaire redondant Multiplicateur: complement a deux Extrait: complement a deux

Figure 3: Ponderateur.

decroissants, d'ou le vocable algorithme de Vaccumulateur.

La sequence de termes est definie comme suit :

{h-iy: i = 1 km). (4.1)

Tableau 2 Example de multiplication effectuee par le ponderateur

0.00 10 000000 00 0 Wo

4 = 0 000.100 .11 To 00 00 00 00 0

*Qi

.00 1010 11 10 01 1 o.oiol n o ! tooo 1

y, x, = i wx

4 = 0 000.11 1 .1001 01 1000 l o o 4 W , - r f 2

.00000000 00000 0.1001 01 1001 100

Y2 x 2 = 0

0 10.01 0 .oo iT loo l i o o o o

4Q2

4W2-d3

.oT oi oi TT oo i l o o.To i o o o o i T o i T o

y3 x 3 = ~ 2

1 10.100 .11 l oo t To n ooo 4 W 3 ~ 4

.01 OlOl 11 00 Tl 0 o . i l o i io n o t n o

y4 x 4 = 2

001.01 1 .00 00 llOl 11 000 4W4-ds

.00To 10TT Tool T o.oo u i l Tl 1T01T

4 = - i T n . io l . i l oi TT n o i Too 4W5-d6

.0000000000 00 0 0.01 00 11 01 00 100

Y6 * 6 = 0 We

4 = 1 001.00 1 .01 OT 01 00 10000

4 0 6 4W^6-4

.ol oi oT TToo iT o 0.100001 10 10 11 0

y7 x 7 = - 2 Wj

4 = - 2 T 10.000

La raison b est un nombre entier positif et les termes sont bornes comme suit :

(4.2)

Parce qu'on est dans un contexte d'accumulation, il convient de nommer ajout le terme Yt.

L'algorithme de l 'accumulateur procede par iteration. Ainsi, pendant qu 'un ajout est additionne, un chiffre appartenant au resultat est extrait. La recursion sur laquelle est basee ralgori thme est :

La constante K est le facteur de redondance (3.7). Dans un pas donne, une valeur d est donnee au chiffre dk seulement si cela permet au residu Wk d 'appartenir au domaine de convergence. Par consequent, la valeur d sera choisie en autant que le residu ancien Wk-X appart ienne a un intervalle bien precis, defini comme suit :

(4.3) Cet intervalle sera nomme intervalle de selection.

L'indice k indique le pas de Piteration. La variable dk represente le chiffre du resultat, que Pon nommera extrait, et Wk represente le residu de Paccumulation au pas k. La chaine des extraits jusqu 'au pas k represente le resultat partiel, nomme plus a propos extraction. II est defini comme suit :

(4.4)

Pour que la selection d 'un extrait se fasse en tout temps, il importe que les intervalles de selection consecutifs se touchent, ou plus encore, se chevauchent. II est facile de montrer qu 'une condition necessaire a cet etat de chose est que la numeration at tr ibute a l'extraction soit redondante . 5 Une autre condition importante est que Pamphtude des ajouts soit limitee comme suit :

(4.7)

Le parametre b represente la base de la numeration. Elle est identique a la raison de la sequence des ajouts (4.1). La base sera egale a une puissance entiere de 2 pour facihter la realisation avec des circuits binaires. Souhgnons egalement que la valeur de p est choisie de maniere a ce que la numeration soit redondante.

II est important de mentionner que la convergence de l'algorithme est liee a ce que le residu soit confine a Pinterieur d 'un certain intervalle, qu'il convient de nommer domaine de conver­gence :

W k ^ D = \ - K + — , K - ^ A . ( 4-5)

L b - \ b - u

Cette condition interviendra plus tard dans les exemples de multiphcation pour connaitre la position exacte du point de numeration au resultat.

Le chevauchement des intervalles de selection permet, entre autres choses, de simplifier grandement la mise en oeuvre de la selection des extraits. En effet, la localisation du residu ancien Wk _ j parmi les Id exige une comparaison. Pour simplifier cette operation, on emploie une approximation de Wh_x. Celle-ci s'obtient en tronquant Wk_x sur les premiers chiffres. Mais ce faisant, on produit du meme coup une incertitude autour de la valeur approchee, ce qui pourrait provoquer eventuellement une erreur

-b(K--±-iY~» + d ) l <4£>

Generation

Sommation

Extraction

- | Booth |

— Y < Y < Y

Wk = bWk_x + Yk - dk.

k

Zk = 2 b~Jdp dj G { - p , . . . , p } . 7 = 1

Y + Y < 2 p j M _ , xmax 1 1min — 1-

b

LAPOINTE/HUYNH/FORTIER: ARCHITECTURE HAUTEMENT CONCURRENTE 97

dans le processus de selection de l'extrait. Toutefois, cette erreur peut etre annulee si 1'approximation est faite suffisamment precise de maniere a compenser l 'incertitude par le chevauchement.

Le lecteur trouvera dans la reference 5, chapitre 3, un developpement detaille de la realisation d 'un accumulateur. Mentionnons seulement que 1'accumulateur se compose de deux parties. La premiere effectue l 'addition de l'ajout. Elle utilise pour cela un des additionneurs de la figure 1, selon que l'ajout est en binaire redondant ou en complement a deux, respectivement. Dans les deux cas, le residu est represente en binaire redondant. Le fait d'utiliser ces types d'additionneurs permet d'obtenir un temps d'execution court et constant a chaque pas de Fiteration, peu importe la taille des variables.

La deuxieme partie effectue la selection de l'extrait. Celle-ci s'execute a partir de la troncature du residu avec l'aide du convertisseur de la figure 2. Ce dernier sera evidemment de courte longueur a cause de la troncature ef fectuee. En plus de la troncature, une operation d'arrondissement est faite. Dans ce cas, l 'approxi-mation Q^-\ est d 'abord multipliee par 4, ce qui donne :

4 2 * - 1 = - 4 < 7 o + 2qx + q2 + 2 " ^ + 2~2q4 + 2~3q5.

Cette expression represente un nombre complement a deux comportant une partie fractionnaire. Ensuite un arrondissement a un entier pres est effectue. II suffit pour cela d'additionner 112 et de prendre la partie entiere. Le resultat donne alors la valeur de l'extrait :

<*k = ~ 4 a o + 2Q\ + 42 +

On fait remarquer que le fait d 'additionner 1/2 cree un biais sur le residu. Les structures des accumulateurs presentees dans la section suivante elimineront bien sur ce biais avant de passer au pas suivant.

Multiplieurs et sommateur

Les deux premieres realisations presentees dans cette section sont des multiplieurs series-paralleles. La troisieme est un sommateur qui a pour tache de sommer les termes de la convolution. Chacune de ces realisations fait appel a un type particulier d'accumula-teur.

Le processus de multiplication se divise habituellement en deux etapes : Fune genere les produits partiels et Fautre en fait la somme. Dans notre cas une troisieme etape s'ajoute, qui est l 'extraction du resultat. La realisation d 'un multiplieur est done formee de trois blocs de circuits : Generation, Sommation et Extraction.

U n premier multiplieur serie-parallele effectue la multiplication d 'un nombre binaire redondant, Ct(n), le multiplicande, avec un nombre complement a deux, Xt{n\ le multiplicateur (figure 3). Le multiplicande est contenu dans un registre parallele tandis que le multiplicateur circule dans un registre a decalage. Ces registres sont symbolises par de grands rectangles en haut de la figure. Une premiere operation est effectuee sur le multiplicateur. Elle consiste a le convertir en numerat ion redondante minimale, en base 4, comme celle de (3.5). L'algorithme de Booth modifie est utilise a cette fin. 6" 7 On apergoit le dispositif de conversion place a la sortie du registre a decalage, a la droite du bloc Generation. La conversion procede d 'abord par le poids fort. Les chiffres multiplicateurs x'k qui en resultent multiplient a tour de role le multiplicande, ce qui produit une sequence decroissante de produits partiels. La raison est ici b = 4. Comme le repertoire des chiffres multiplicateurs est { — 2 , . . . , 2} , un simple multiplexeur suffit a generer les produits partiels. Ce dispositif est symbolise par les cercles marques d 'un X. II convient de mentionner que Foppose d 'un nombre binaire

redondant s'obtient par Fin version booleenne de tous ses bits (voir a cet effet le tableau 1). Mentionnons egalement que le produit par 2 d 'un nombre binaire est realise par un decalage d'une position vers le poids fort. Ces operations elementaires sont toutes effectuees par le multiplexeur.

Comme le multiplicande est en binaire redondant, les produits partiels sont generes dans la meme numeration, ce qui implique Futilisation d 'un addit ionneur redondant pour effectuer la somme. L'addit ionneur est symbolise par Fensemble des cercles marques d 'un A. Son resultat est sauvegarde a chaque pas de Fiteration par un registre parallele, symbolise par les petits carres blancs et noirs. La configuration des couleurs indique la maniere de mettre a zero ce registre, une operation qui doit etre effectuee au depart de Fiteration. Le noir est pour le bit 1 et le blanc est pour le bit 0. Ainsi le couple de bits (1 ,0 ) code le chiffre zero (voir le tableau 1). Une exception a lieu a la quatrieme position a gauche ou les bits (1 ,1) sont memorises. Le chiffre + 1 ainsi code sert a ajouter le biais intervenant dans le processus de selection de l'extrait. Ce biais est automatiquement elimine au pas suivant par la structure de Faccumulateur. 5 On constate que le registre parallele coupe tout parcours entre Fentree et la sortie. C'est ce registre qui cree le niveau pipeline dont il etait question au debut de Farticle. Ce registre sera appele dans la suite registre de Yaccumulateur.

Le selecteur est compose des six cercles marques d'un S. II emprunte la structure du convertisseur de la figure 2. II effectue l 'extraction du resultat dans une numeration a redondance maximale, de base 4, comme celle de (3.6). Les extraits, represented par mih sont codes en complement a deux par les trois bits a gauche a la sortie. A noter que le bit sortant a la ligne pointillee n'est pas utilise puisque trois bits suffisent a representer l'extrait dans le repertoire { — 3 , . . . , 3} . Mentionnons egalement la presence d'un inverseur sur un des bits codant l'extrait. Son etat est inverse pour une raison qui sera expliquee plus tard. La chaine des chiffres w 3 - w 7

constitue le residu. II est retourne a Fentree de Fadditionneur redondant , en haut du bloc Sommation, afin de boucler la recursion.

II convient de souligner que la figure 3 n'est qu 'un exemple de realisation. En fait la longueur du multiplieur devra s'ajuster en fonction de la taille du multiplicande. Ainsi Fadditionneur redondant et le multiplieur seront allonges en consequence. Le selecteur, quant a lui, sera toujours de meme longueur. La raison en est que la troncature fait sur le residu est toujours la meme, peu importe la taille du residu. II est ainsi permis de dire que le parcours critique sera toujours identique et de courte longueur, ce qui autorise un temps d'execution constant et rapide a chaque pas de Fiteration.

La representation du multiplicande dans cette realisation est la suivante :

C, = 2 2-Jch Cj <= { - 1 , 0 , 1}. (5-1) j=-\

II est important de souligner que le bon fonctionnement de Faccumulateur exige ici que le multiplicande soit limite dans la plage definie par : \Ct\ < l . 5 Mais alors, on pourrait croire que les chiffres c_ j et c 0 sont inutiles puisque Fon peut couvrir entierement cette plage tout en faisant c_x — 0 et c 0 = 0. En pratique, cependant, il en sera autrement a cause de la redondance caracterisant la numerat ion du multiplicande.

On aura sans doute devine, grace aux symboles Ct(n) et Xt(n) donnes aux operandes, que ce multiplieur est destine au calcul des termes de la convolution. Pour cette raison, il sera appele : ponderateur.

98 CAN. J. ELECT. & COMP. ENG., VOL. 16, NO. 3, 1991

U n exemple de multiplication est presente au tableau 2. Le multiplicande et le multiplicateur sont respectivement :

C, = (Ol.OTOl 11 00 T l ) 2 = 0.8584,

Xl = (0.01 11 00 11 01 11)2 = 0.4509.

Une conversion a l'aide de ralgori thme de Booth est d 'abord effectuee sur Xb ce qui donne :

y = (.1022T02)4.

On se souvient que l 'amplitude des ajouts etait limitee par la condition (4.7). Sachant que la numerat ion de l'extraction est caracterisee par les parametres b = 4 et p = 3, cette limite devient :

| y | < y <c 2 p + 1 - 1 = 1 (5.2)

On a fait ici Ymax = Ymin. On sait par ailleurs que | Q | < 1 et x'k e { — 2 , . . . , 2} . Les produits partiels sont done limites comme suit : \x'k - Cj\ < 2. Pour que les produits partiels respectent les limites imposees a un ajout, un facteur 1/8 multiphe chacun des chiffres du multiphcateur, ce qui amene :

X 1 -j = -( .1022102) 4 . 16 o

Le resultat de la multiphcation donnera done :

Xf - Ct _ 1 6 - (A d2 d 3 d 4 . . .)4.

Le dernier nombre est le resultat arrondi de la multiplication de 0.8584 par 0.4509.

U n second multiplieur serie-parallele effectue la multiplication d 'un nombre complement a deux, Xt(n\ le multiplicande, avec un nombre a redondance minimale de base 4, E(n), le multiplicateur (figure 4). Le multiplicande est contenu dans un registre parallele tandis que le multiplicateur est regu chiffre par chiffre, poids fort d 'abord. Etant donne le repertoire {— 2 , . . . , 2} , les chiffres du multiplicateur, eh actionnent directement un multiplexeur pour la generation des produits partiels. Ceux-ci sont en complement a deux, comme le multiplicande. La sequence des produits partiels decroit avec la raison b = 4.

Le facteur 1/16 qui affecte le membre de gauche a pour effet de decaler le point de numeration de deux positions. Ainsi on obtient :

X r Q = ( d ] d 2 . d 3 d 4 . . . ) 4 .

Le tableau 2 donne comme resultat :

Xt • Q = (00.221 Tl2) 4 = .3872.

V e n a n t du p o n d e r a t e u r

- y 2 | x 3 \x4 q V e n a n t du s o m m a t e u r

M u l t i p l i c a t e u r E(n)

- In i t i a l i sa t ion

Res idu m o i n s l 'extrai t

I Resu l ta t C,{n + l) I

V e r s le p o n d e r a t e u r M u l t i p l i c a n d e : c o m p l e m e n t a d e u x

Mul t i p l i c a t eu r : r e d o n d a n t base 4 ,

{ - 2 . . . - . 2 }

Hxtrait : b ina i r e r e d o n d a n t

Resul ta t : b in ; ire r e d o n d a n t

U n additionneur hybride effectue l 'accumulation. Celui-ci est symbolise par l 'ensemble des cercles marques d'un A. Son resultat est sauvegarde a chaque pas de l'iteration par un registre parallele, les carres blancs et noirs, nomme egalement registre de 1'accumu­l a t e s . La configuration des couleurs qui est presentee a la figure est donnee ici a titre d'exemple. Elle code un nombre nul. Mais, dans les faits, l 'iteration devra etre amorcee avec un residu initial non nul, egal au coefficient a corriger Ct(n), comme on le verra a la section suivante. Comme precedemment, un biais est donne au residu initial en memorisant (1 , 1) a la troisieme position a gauche, pour la bonne marche du selecteur. Signalons que le signal Inc place a la droite du registre a pour but de creer une incrementation lorsque le chiffre multiplicateur ek est negatif. En effet, l 'oppose d'un nombre complement a deux s'obtient en inversant chacun des bits et en addit ionnant 1 a la position de poids faible. Dans notre realisation, Tin version des bits s'effectue par Fentremise du multiplexeur tandis

Figure 4: Correcteur.

Tableau 3 Exemple de multiplication effectuee par le correcteur

.00 10 00 00 0001 II 1001 Ol 10 II

000.10 .0000000001 II1001 01 lOll 4 W o - 4

1000 0000 0000 .01 To0000 l l IT TOO! Of 10Tl

4 = 0 0 00.10 .oooooo i l i l Tool 01 l o l l 41+' , -4

10 00 00 00 00 00 .01 Tool T i l l To i l oi i o n

e - , = 0

4 = 0 000.10 .oooi I I I I To 11 oT io Ti

4Q2

4 H ^ 2 - 4 . 1000 00000000 . 0 1 0 ! ! ! IT Ti TT 01 10 11

e 0 = 0

4 = 0 000.11 .01 I I I ! Il i l o ! io Tl 4 W 3 - 4

10 1101 10 11 11 . i l o i ooooooTi i l Ti

e , = l

4 = 0 000.11 .01 ooooooTi i l l i . 000100 100001 Inc .i l oo n oo io Ti oi WWm}:

e 2 = - 2

.10 11 00 10II 01 00

. 0100 10 010000 Inc

.Ti Tool oo To i l o i

4 - - 2 I 10.10 .0001 0010 11 01 00 4 ^ 6 - 4

10 11 01 1011 11 .01 0001 000001 ol

e 4 = I

4 = 1 0 01.00 .Tool 00 0001 o loo

407 4 ^ 7 - 4

10 00 00 00 00 00 .Ti TiooooiToToo

n e 5 = 0

4 = - 2 I 10.01 .11 oooo n o ! oo oo

4 0 8

4 1 f 8 - 4 . 000100 1000 01 Inc .01 00 10 Io II 00 10

e 6 - ~ 2

4 0 = - i I 11.00 .To io io IT oo moo

409 4 W , - 4 0

. 01 00 1001 0000 Inc

.Ti ol io ol io To oi ww

e 7 = - l

4 , = - 2 T 10.11 40,o

Generation

Sommation

Extraction |

k Ext ra i t

LAPOINTE/HUYNH/FORTIER: ARCHITECTURE HAUTEMENT CONCURRENTE 99

Extraits venant des ponderateurs

Ajout, vers les deux accumulateurs sommateurs

Extraits : complement a deux Ajout: stockage de la retenue

Figure 5: Tableau additionneur.

que l 'addition de 1 se fait en activant a 1 le signal Inc. Mentionnons, enfin, que le registre de Faccumulateur se prolonge en fait beaucoup plus qu'il n'y parait a la figure. Cela est du au fait que le residu initial sera, a la section suivante, de taille plus grande que la taille du multiplicande, et aussi au fait que l'arrivee des chiffres ek sera retardee, forgant ainsi le decalage de la valeur initiale.

Le selecteur est compose de quatre cellules d'addition marquees d 'un S. II effectue l 'extraction du resultat dans une numeration a redondance maximale, de base 4, comme celle de (3.6). Les extraits sont d 'abord codes en complement a deux, puis transferee a un convertisseur. Celui-ci est constitue des deux cellules d 'addition marquees d'un C. II convertit un extrait de trois bits en un nombre binaire redondant de deux positions. Ainsi le resultat de la multiplication C((n + 1) peut etre represente en binaire redondant en effectuant simplement la concatenation des extraits ck qui emergent. Cette operation est realisee par un registre a decalage place a la sortie du multiplieur, qui recueillent les extraits un a un, poids fort d 'abord. Finalement, le bit q3 et les chiffres Wj, j — 4, 5 , . . . , qui composent la representation du residu moins l'extrait, sont retournes a Fentree de Fadditionneur hybride en haut du bloc Sommation pour boucler la recursion.

A Finstar du premier multiplieur, celui-ci aura une longueur ajustee en fonction de la taille du multiplicande. En revanche, la longueur du selecteur restera fixe en toute circonstance. La meme conclusion s'applique ici, a Feffet que le temps d'execution a chaque pas de Fiteration est constant et rapide.

Les symboles Xt(n) et E(n) donnes aux operandes et Ct(n + 1) donne a la sortie, donnent a penser que ce multiplieur est destine a la correction des coefficients a Finterieur du processus d 'adaptat ion. C'est pourquoi il sera appele : Correcteur.

U n exemple de multiplication de ce multiplieur est presente au tableau 3. Le multiplicande et le multiplieur sont respective-ment :

Xt = (0.1101 1011 11) 2 = 0.8584,

E = (000.12Tl02T) 4 = 0.1127,

et la valeur initiale est :

Ci = (Ol.TTTOOlOl 10Tl) 2 = 0.1384.

Ici on desire effectuer F operation C, 4- 4E • Xt. On peut obtenir ce resultat en decalant d 'une position le multiplicateur, comme s u i t :

4E = (0001 .2 l l 02 l ) 4 = 0.4509.

Les parametres b et p sont les memes que ceux de F exemple precedent. Normalement les limites devraient etre celles de (5.2). D an s cette realisation, toutefois, le correcteur est conc,u de maniere a ce qu'il accepte des ajouts avec une amplitude deux fois moindre. Les nouvelles limites seront donnees par: \Yt\ < 3/16. Cette contrainte supplementaire permet un selecteur plus court. Par ailleurs, etant donne que \Xl| < 1 et ek e { — 2 , . . . , 2} , les produits partiels sont limites comme suit :\ek- Xt | < 2. II faut done multiplier par 1/16 chacun des produits partiels de sorte que les limites imposees aux ajouts soient respectees. De plus, comme le poids du premier chiffre de 4E est egal a 4 3 , et que le premier terme de la sequence a accumuler doit etre 4~~ 1 Yh il faut raj outer un facteur 4 - 4

aux produits partiels, ce qui fait un facteur total de 4 - 6 . Ce meme facteur doit multiplier la valeur initiale Ct. Le resultat emergeant du correcteur sera done :

4 - 6 ( C , + AE'Xt) = {.dxd1...d^d1..\

et apres decalage du point du numerat ion :

Ct + AE-Xt = (</, d2...d6.d7...)4.

Le resultat affiche par le tableau 3 donne :

Ct + 4E • Xt = (000001.212T2) 4 = 0.5254.

Le dernier nombre correspond bien au resultat arrondi espere de C, + 4E - Xj une fois les valeurs numeriques prises en compte.

Quelques remarques doivent etre ajoutees en rapport avec le tableau 3. Le bit de poids fort de chacun des ajouts Yk est inverse au tableau, ce que fait Finverseur a cet endroit a la figure 4. Cette inversion a Feffet interessant d'ajouter le biais necessaire a la bonne marche du selecteur. D 'aut re part, le bit q3 appartenant au residu (a la droite du selecteur, figure 4) est associe a un second bit de valeur 0 avant d'etre affiche au tableau. Cette paire de bits code alors un chiffre binaire redondant . De cette maniere, le biais apporte avant la selection est elimine a cet endroit apres la selection.

II etait fait mention plus tot que N multiplieurs series-paralleles, en Foccurrence N ponderateurs, calculaient en parallele les termes de la convolution. Par consequent, N extraits sont produits simultanement par ces multiplieurs a Finterieur d'un pas. Le tableau addit ionneur de la figure 5 a pour fonction d'effectuer la somme de ces extraits. II est constitue d'additionneurs semblables a Fadditionneur redondant (figure la) , a Fexception du couple de bit (0 ,0) qui penetre au cote droit au lieu du couple (1,0). Etant donne que les extraits mik sont en complement a deux, l 'addition effectuee a Finterieur du tableau additionneur se fait par stockage de la retenue*. L'utilisation d'additionneurs comme celui de la figure la exige toutefois que le bit de poids fort des extraits a Fentree soit inverse, ce qui explique la presence de Finverseur a la sortie du selecteur d 'un ponderateur (voir figure 3). On aura constate a la figure 5 que les additionneurs sont disposes selon une topologie arborescente. Cette disposition autorise un temps de traverse de 0 ( log N), ce qui devient tres avantageux lorsque la longueur du filtre est grande.

* En anglais: "Carry-Save".

100 CAN. J. ELECT. & COMP. ENG., VOL. 16, NO. 3, 1991

V e n a n t du t ab leau a d d i t i o n n e u r

a jout

Sommation

Extraction

— <73 <74 q5 w 6 w 7 w 8 w 9 w 1 0 w n wn

w\3w\A extrait

residu moins l'extrait Vers les correcteurs

Figure 6: A ccumulateur sommateur.

La sortie du tableau additionneur produit une sequence de nombres, Sh a mesure que Fiteration progresse. Cette sequence est decroissante avec la raison b — 4, du fait que la serie des extraits a sommer decroit avec cette raison. Par consequent, un accumulateur pourra facilement effectuer la somme de cette sequence. La sortie donnera le resultat de la convolution, Y{n).

La variable Sk est representee en numeration stockage de la retenue. II est facile de convertir ce nombre en binaire redondant en interpretant autrement les bits qui le composent . 5 Ainsi les bits retenue et somme d'une position donnee exprimeront les bits rj et Sj de la numeration binaire redondante selon le tableau 1. Cette operation cree cependant un biais sur Sk. De meme, l'inversion prealable effectuee sur les bits de poids fort des extraits mik cree egalement un biais. On peut corriger ces biais en soustrayant 1 a la position de poids faible de Sk. La realisation de l 'accumulateur est illustree a la figure 6. Les deux premieres rangees de cellules d'addition, les cercles marques d 'un A, constituent un additionneur redondant . Pour soustraire 1 a la position de poids faible de Sk, il suffit de faire penetrer sur le cote droit de Fadditionneur le couple (0,0) au lieu du couple habituel (1,0). Le premier, on le sait, code le chiffre binaire redondant — 1.

Nous donnons ici un exemple. On effectue la somme des extraits : + 2, + 2, 4 - 1 et — 2. Ceux-ci sont d 'abord codes en complement a deux :

010, 010, 001, 110,

puis le bit de poids fort de chacun d'eux est inverse :

110, 110, 101, 010.

U n e somme avec stockage de la retenue est ensuite effectuee. On obtient :

chaine des bits sommes : 1011

chaine des bits retenues : 1000.

Si Fon interprete les colonnes de bits a l 'aide du tableau 1, on obtient le nombre binaire redondant suivant :

(1T00) 2 = 4.

II suffit alors de soustraire 1 a ce nombre pour obtenir la somme des extraits.

L'accumulateur (figure 6) est done compose d 'un additionneur redondant , suivi d 'un registre parallele pour la sauvegarde du residu. Ce registre est remis a zero au debut de Fiteration. La configuration a suivre dans ce cas est celle indiquee par les carres

noirs et blancs. Encore une fois, un biais est cree en memorisant le couple (1 , 1) a la quatrieme position a partir de la gauche. Ment ionnons que la longueur du registre est appelee a etre beaucoup plus grande que la taille des ajouts Sh ce qu'illustre la poursuite des carres a la droite de la figure.

U n selecteur, compose ici de cinq cellules d'addition, effectue l'extraction dans une numeration redondante minimale, en base 4, de repertoire { — 2 , . . . , 2} . Les extraits sont codes par les trois bits a gauche a la sortie. Les bits q3, q4, q5 et les chiffres WjJ — 6, 7 , . . . , constituent le residu. Celui-ci est retourne a Fentree de Faddition­neur redondant en haut du bloc Sommation pour boucler la recursion.

Le meme accumulateur peut egalement servir a calculer Ferreur d'estimation E(n). Pour cela, le residu initial de l 'accumulateur est fait egal a F oppose de la reference Z(n\ et le signe de chacun des extraits qui emergent est inverse, ce qui inverse automatiquement le signe du resultat. Ainsi, on obtient :

E = —(Y - Z ) = Z - y ,

ce qui est de forme identique a la relation (2.2).

L'ensemble du tableau additionneur et de deux accumulateurs tels qu'illustres a la figure 6 composent un troisieme organe de calcul, appele sommateur. II recueille les extraits produits par les ponderateurs pour produire deux resultats : la reponse du filtre et Ferreur d'estimation. Cette derniere est transmise telle quelle aux correcteurs. La reponse, pour sa part, demande a etre convertie en complement a deux avant d'etre emise a l'exterieur du circuit. II existe un algorithme qui effectue cette operation de fac,on iterative. 8

II presente le grand avantage de s'affranchir de la propagation de la retenue, ce qui lui donne un temps d'execution court et constant a chaque pas. Cet algorithme est done tout a fait compatible avec notre algorithme de l 'accumulateur.

Ceci complete la description des organes de calcul qui seront utilises a la section qui suit pour la realisation du filtre M C M .

Realisation du filtre M C M

On sait deja que N ponderateurs sont utilises en parallele pour effectuer le calcul des termes de la convolution, et qu 'un sommateur recueille ces termes pour en faire la somme. D'une des sorties de ce dernier emerge Ferreur d'estimation qui est aussitot transmise a N correcteurs mis en parallele. Ceux-ci mettent alors en oeuvre I'algorithme d 'adaptat ion a Fendroit des coefficients. A la fin de Fiteration, les N nouvelles valeurs des coefficients sont transmises aux ponderateurs, et le cycle recommence avec un nouvel echantillon de X. Voila pour la description globale de la realisation. Nous allons maintenant discuter de la circulation des variables a travers les differents organes de calcul.

Le ponderateur effectue le produit d 'un echantillon Xt avec un coefficient Ct. On assume d'abord que Fechantillon est en complement a deux a cause de la popularity de cette numeration. Ensuite, par souci de simplicity materielle, Fechantillon est converti en une numeration redondante a l'aide de I'algorithme de Booth modifie. Ainsi on passe d 'une representation complement a deux :

Xt = -x0 + 2 2~Jxi9 x0, X.- g {0, 1}, (6-1) .7=1

a cette representation redondante minimale en base 4 :

$ - (.x\ x'2x',.. .)4 - 2 4 " * 4 , 4 e { " 2 , • • •, 2} . (6-2) 2 k = \

LAPOINTE/HUYNH/FORTIER: ARCHITECTURE HAUTEMENT CONCURRENTE 101

Dans les deux cas, Fechantillon Xt est borne comme su i t : \Xt\ < 1. Le coefficient Ch pour sa part, est represente par (5.1). II est borne comme suit : | Q | < 1.

Supposons, dans un cas hypothetique, que la redondance de C, soit ehminee. Alors les chiffres c_ x et c 0 seront toujours nuls. Dans ce cas, la partie significative de C, debute a partir du chiffre q . Si on je t te un coup d'oeil a la figure 3, on remarque alors que la partie significative de Ct est en retrait a droite par rapport au selecteur. Par ailleurs il y a le registre de l 'accumulateur place entre Fadditionneur et le selecteur. Ces deux points expliquent le retard qui existe a la sortie du ponderateur. Ce retard resulte en une ponderation plus forte a l'extraction. Ainsi le ponderateur produira un resultat ayant cette representation :

Mi ~ (m { m{). mx .. .)4

= 2 4 2 ~ * m , _ 2 , m , _ 2 e { - 3 , . . . , 3}. (6-3) k = \

La variable Mt represente le produit de Xt et Ct. On constate que le point de numeration a ete decale de deux positions vers la droite par rapport a (6.2). Ce decalage se prononcera a mesure que Fon avancera dans la chaine des organes de calcul.

L'indice k present dans (6.2) et (6.3) indique le pas de Fiteration. Ainsi lorsque, au pas k — 1, le chiffre x\ emerge du convertisseur et actionne le multiplexeur, l'extrait m_l emerge simultanement du ponderateur. D 'autre part, comme les operations debutent au pas k — 1, la remise-a-zero de l 'accumulateur se fait au pas k — 0. Au meme moment, le multiplicande est charge dans son registre parallele. II est important de souligner que l'extrait m _ i sera toujours nul, en raison de la mise a zero de l 'accumulateur au debut de Fiteration (voir l 'exemple du tableau 2).

II est evident que |M,| < 1 du fait que \Xt\ < 1 et |C,| < 1. Par consequent, le resultat de la convolution sera borne comme suit : | Y| < N. II convient ici de normaliser Y. Ainsi on aura :

Y = VN\(y_Ay__2...y0.yx . . .)4

= VN12 2 4 5 ~ V * - 5 , yk-5 e { - 2 , . . . . 2} , (6-4) k— 1

Ce facteur s'explique par le fait que le tableau additionneur (figure 5) soit un arbre binaire.

O n constate que le point de numeration de (6.4) a fait un bond de trois positions vers la droite. Ceci s'explique pour les memes raisons que celles mentionnees precedemment, a savoir la presence du registre de l 'accumulateur et la position en retrait de l'ajout par rappor t au selecteur. Incidemment, on montre que les chiffres >>_4

— y~ \ sont toujours nuls. Le cas est evident pour j>_ 4 lorsque Fon considere que l 'accumulateur dedie a la convolution (figure 6) est remis a zero au debut de Fiteration, ce qui force le premier extrait a etre nul. Nous allons passer directement a la preuve p o u r y _ h les preuves etant similaires pour jy_ 3 et j>_ 2 . On considere Fun des pires cas ou Mi; ~ 1, pour tous_les /', F autre pire cas etant Afz- « — 1. Ainsi on a : Ml• — (01.00 . . . 01) 4 . Ce qui signifie que x = 0, m0 = 1 et mx = 0. La selection dey_x depend essentiellement de ces trois chiffres. La sequence des trois premiers nombres qui emergent du tableau addit ionneur est montree au tableau 4a, ainsi que la somme sous le trait horizontal. Les chiffres en caracteres gras sont ceux pris en consideration par le selecteur de l 'accumulateur. Cette partie de la somme, laquelle est en binaire redondant, est decomposee en couples de bits au tableau 4b. Le selecteur additionne ces bits. Une particularite a lieu a Fendroit du dernier couple a droite. En effet, le bit 0 est decale d 'une position vers la gauche tandis que le bit 1 est omis de l 'addition. II convient de noter que Fon aurait pu tout aussi bien intervertir les roles de ces bits, sans que cela nuise au resultat. A noter egalement l 'addition d 'un biais facilitant la selection. Le resultat de la selection est alors presente sous le trait horizontal. II faut noter Finversion du bit de poids fort a gauche (voir a cet effet le selecteur, figure 6). Grace a cette operation, la valeur d e y _ x est donnee par les trois premiers bits de poids forts sous une representation en complement a deux. Ainsi on a >>_ x — 0, ce qu'il fallait demontrer. D 'aut re part, il est possible de montrer, a partir d 'une preuve similaire, que le premier chiffre de Y susceptible d'etre non nul est y0, et qu'il est compris dans { — 1, 0, 1}.

Les structures qui calculent la convolution et Ferreur d'estima­tion sont semblables. C'est pourquoi il convient de donner a Ferreur la meme representation que la convolution. De maniere similaire a (6.4), on a :

E = YN\(e_-4e_3 . . . e 0 . «? , . . . ) 4

= VN\ 2 4 5 ~ V 5 , * * - 5 e { - 2 , . . . . 2} , (6.6) k = \

ou TAH2 est un facteur d'echelle proport ionnant un nombre borne comme suit : \ (y_4 y_3 y_2 • - O4I < 1. Le facteur d'echelle est defini ainsi :

T A n 2 = au plus petit de 2a \ a e {entiers positifs},

2a > N. (6.5)

Tableau 4 Selection du chiffre a) Somme des trois premiers ajouts b) Selection de Fextrait

0 0 0 0 0 0 0 0 . . . 2

a) 0 1 0 0 0 0 . . . 2

0 0 0 0 . . . 2

1 1 . 1 1 1 X oo.oi o(3

biais —» 1 OS 0 0 0 . 1 0 1

avec des valeurs nulles pour e _ 4 - e _ b et e 0 £ { — 1, 0, 1}. Ces caracteristiques sont obtenues en autant que le resultat de Z — Y s'y prete. II faut done poser la condition |Z — Y\ < N.

U n correcteur effectue le produit de Ferreur E avec un echantillon Xj. Cependant , il faut savoir que le correcteur utilise en fait la chaine ( e _ 4 e _ 3 e _ 2 . . . ) 4 qui est generee par le sommateur. II en resulte que le produit reellement effectue est E • Xt/YN\. Si, par convention, on decale d 'une position le point de numeration de Ferreur, on obtient dans ce cas 4E • X^rNl^ L'utilite de ce stratageme deviendra apparent a la section suivante.

Le correcteur est initialise au depart par Cj(n), la valeur actuelle du coefficient. L'operation effectuee est alors :

Cf-(/i + 1) = CXn) + ~E(n) • Xt{n\ (6.7) I N \ 2

ce qui est semblable par la forme au processus d'adaptation (2.3). Ici, l 'expression 4/VNl2 remplace le pas d e c r e m e n t a t i o n JU. L'extraction a la sortie du correcteur sera :

102 CAN. J. ELECT. & COMP. ENG., VOL. 16, NO. 3, 1991

Tableau 5 Sequence d'evenements d'une realisation k cycles

lllltllll 1 # xj x's x\ x'5 x'6 0 0 0 0 0 0 0 0 2 0 0 m0 .wj m2 m3 m4 m5 m6 m-] m% m9 X X X 3 0 0 0 0 0 tf0 .e} ^ e3 4̂ 5̂ e6 7̂ *8 9̂ 4 0 0 0 0 0 0 t% .c\ c'2 4 c 4 c's 4 c7 4

':M A/,(«4 1) 0 0 £ ( » + ! ) 0 0

Ct(n + 1) = (c '_ 7 c'_6 . . . 4 . cr! . . . ) 4

{ - 3 , . . . , 3}. (6.8) = 2 4 8

k = \

A noter le decalage important du point de numeration. On doit poser ici la condition \Ct(n + 1) | < 1 de maniere a respecter celle qui etait posee precedemment dans le cas du ponderateur ou on avait \Cj(n) \ < 1. Si, de plus, on impose :

(6.9)

on peut alors montrer que les extraits c'_ 7 -c'_i sont tous nuls et que le premier extrait susceptible d'etre non nul est c 0 avec c0 G { — 1,0, 1}. La preuve est similaire a celle des tableaux 4a et 4b.

On rappelle la conversion en binaire redondant qui a lieu a l 'endroit de la representation de Ct(n + 1) a la sortie du correcteur. Cette operation est effectuee en convertissant en binaire redondant chacun des chiffres c £ _ 8 , P m s e n ^ e s concatenant dans un registre a decalage. On fait remarquer que la longueur du registre peut etre raccourcie du fait que les extraits c / _ 7 - c / _ 1 sont toujours nuls.

On mentionnait precedemment que les chiffres e _ 4 - e _ i etaient tous nuls. S'ils n 'ont aucune valeur significative, alors l'initialisation des correcteurs peut se faire indifferemment entre les pas k — 0 et k = 4. Dans un autre ordre d'idees, on a constate qu 'un retard s'ajoutait a mesure que Ton avangait dans la chaine des organes de calcul. Ce qui signifie que les ponderateurs et le sommateur peuvent atteindre une meilleure precision que les correcteurs, etant donne qu'ils ont plus d'extraits produits apres le point de numeration. Toutefois, les derniers extraits sont superflus puisqu'ils n 'ont pas ou peu d'influence sur les derniers extraits du resultat final, ce dernier etant les valeurs corrigees Ct(n + 1). C'est done dire que le cycle de calcul reserve aux ponderateurs et au sommateur pourrait, sans probleme, etre raccourci du cote des derniers extraits. De meme, le cycle de calcul reserve aux correcteurs pourrait etre raccourci du cote des premiers extraits en effectuant une initialisation retardee, au pas k — 2 par exemple. Dans ce cas, les cycles respectifs des ponderateurs-sommateur et des correcteurs se chevauchent dans le temps. Le tableau 5 en donne un exemple. Une colonne montre l 'occurrence d'evenements simultanes. U n grand X indique pour l'extrait concerne une valeur sans effet sur les resultats futurs. On voit dans cet exemple que le cycle des ponderateurs-sommateur (les trois rangees du haut) dure 15 pas, soit de k = 0 a k — 14. La meme duree vaut pour les correcteurs mais les pas vont dek — 2kk — 16 (la 4 e rangee). II y a done chevauchement des cycles sur 2 pas. Les trois dernieres rangees du tableau 5 montre le debut du cycle suivant des ponderateurs-sommateur.

CQ. D 'autre part, un autre echantillon est pris au pas k — 16 a titre de valeur initiale pour le correcteur au cycle suivant. Ce deuxieme echantillon a, pour sa part, 8 positions, excluant c'0. Ainsi le processus d 'adaptat ion est calcule avec des coefficients de meilleure precision que dans le cas de la convolution. II est montre que cette caracteristique peut empecher l'arret premature de l 'adaptation. 9

Celui-ci a lieu dans une implantation numerique lorsqu'une precision insuffisante est accordee au calcul de l 'adaptation.

On resume ici la circulation des variables. Les echantillons X(

circulent dans les registres a decalage des ponderateurs. Ces registres sont relies en serie de maniere a ce qu 'un echantillon passe d 'un ponderateur a l 'autre a chaque cycle de calcul. Les termes Mt

emergent chiffre par chiffre pendant qu'ils sont sommes par un sommateur. Celui-ci produit simultanement, chiffre par chiffre, la reponse du filtre Y et l 'erreur d'estimation E. En ce qui regarde le calcul de l'erreur, la valeur de la reference Z doit au prealable etre presente dans le sommateur des l 'amorce du cycle de calcul. Les operations enumerees ici sont effectuees a l'interieur du cycle de calcul appartenant a la convolution.

U n autre cycle de calcul opere le processus d'adaptation. Dans ce cas, l'erreur est transmise en serie aux correcteurs. Peu de temps avant la fin du cycle, un echantillonnage des valeurs corrigees des coefficients Ct est pris dans les registres a decalage a la sortie des correcteurs. Ces valeurs sont transmises en parallele aux pondera­teurs correspondants pour l 'amorce d 'un nouveau cycle de calcul de la convolution. Pendant que le cycle de calcul de l 'adaptation se poursuit , une meilleure precision est atteinte a l'endroit des coefficients corriges. A la fin du cycle, les valeurs obtenues sont utilisees pour initialiser les correcteurs respectifs. Au meme moment , les valeurs des echantillons Xi9 presents dans les registres a decalage des ponderateurs, sont fixees dans les registres paralleles des correcteurs a titre de multiphcandes.

O n observe ici que la circulation des variables se fait pour la plupart en serie. II y a exception pour ce qui est du transfert en mode parallele des valeurs corrigees des coefficients allant des correcteurs aux ponderateurs, et de la prise des echantillons Xt allant des ponderateurs aux correcteurs. A cet effet on note qu 'un ponderateur est toujours associe a un meme correcteur, les deux partageant le meme coefficient et le meme echantillon. II convient done d'accoler physiquement ces deux organes de calcul, minimisant ainsi l 'encombrement des bus paralleles transportant les dites variables. L'ensemble de ces deux organes forme un premier module. A cela s'ajoute un second module forme du sommateur. II appert alors que la circulation des variables se fait exclusivement en serie, d'un module a l 'autre.

Discussion

La comparaison entre les relations (2.3) et (6.7) montre que le pas d e c r e m e n t a t i o n a ete substitue comme suit dans la realisation :

M = — . (7.1)

On demontre ici que cette valeur assure la convergence de ra lgori thme M C M dans la majorite des cas.

On a vu a la section 2 que la condition de convergence etait donnee par :

2 0 < a < .

N • P Mentionnons par ailleurs, en rapport avec le tableau 5, qu 'un

echantillon du coefficient corrige Ct(n + 1) est pris au pas k = 14 pour etre transfere a un ponderateur a titre de mult iphcande au cycle suivant. La taille de cet echantillon est de 6 positions, excluant Rappelons que la variable P represente la puissance moyenne du

\N12

LAPOINTE/HUYNH/FORTIER: ARCHITECTURE HAUTEMENT CONCURRENTE 103

liX(n-N + 1)

Module 1

i[X(n-N + 2)

Module 1

Module 1

X(n)

Module 1

Module 2

I T Z(n)

Y(n)

E(n)

X(n+ 1)

Figure 7: Realisation simple de ralgorithme MCM.

signal X. Cette puissance subit une contrainte liee a la taille finie des variables. En effet la puissance crete Pc est limitee comme suit :

n X (n-N + 1 )

Module 2

Module 1

I F Z(n)

Y(n)

E(n)

X(n+ 1)

Figure 8: Realisation comportant plusieurs modules 2.

n'atteint jamais le minimum. A cet effet, pour representer cet ecart avec le minimum theorique, on a cree le concept de facteur de mauvais ajustement* M, defini comme etant le rapport entre l'exces d'erreur et Ferreur minimale. II est montre que le facteur de mauvais ajustement est proportionnel au pas d e c r e m e n t a t i o n (reference 1, page 111) :

M _ Mtr[R]

2 (7.6)

Ainsi, afin de favoriser le rapprochement des valeurs des coefficients vers leurs valeurs optimales, on fait en sorte de diminuer ju. On y arrive dans cette realisation en retardant Farrivee aux correcteurs des chiffres composant Ferreur. En effet, le fait de retarder d 'un coup, par exemple, la chaine des chiffres ek^5, a pour effet de diminuer leurs poids respectifs d 'un facteur 4. U n facteur 1 / 4 s'ajoute alors au pas d e c r e m e n t a t i o n original, et on obtient un pas effectif de /x = l / r A n 2 . Ainsi, pour chaque coup de retard, un facteur 4 diminue les pas d e c r e m e n t a t i o n .

II est clair que la longueur de Fiteration des multiplieurs est proportionnelle a la taille M des variables. D'autre part, chaque pas de Fiteration a une duree qui depend principalement du temps de traversee dans Farbre sommateur (le tableau additionneur). Ce temps est proportionnel a log N. Par consequent, la duree totale d 'une iteration sera 0 ( M • log N). II est possible d'ameliorer cette performance en ajoutant des niveaux pipelines a Finterieur de Farbre sommateur. Ainsi, pour chaque niveau ajoute, un pas s u p p l e m e n t a l doit etre ajoute a Fiteration. A la limite, lorsque les trajets entre les niveaux pipelines sont equilibres, on obtient une duree totale de 0 ( M + log N). Par ailleurs, lorsque N croit, il faut du meme coup accroitre la precision du calcul de la convolution. Ainsi la taille M doit etre proportionnelle a log N, ce qui permet de simplifier l'expression de la duree totale a 0 ( log N). Cette duree represente en fait la periode d 'un echantillonnage sur le signal X. Cette realisation peut done atteindre une frequence d'echantillon-nage elevee, meme avec un tres grand nombre de coefficients.

Dans une premiere approche, la realisation se presente comme suit (figure 7 ) : N modules N ° l etc. (ponderateurs-correcteurs) sont disposes en parallele et un seul module N°2 (sommateur) recueille les extraits des termes de la convolution. Ainsi, a chaque fois que le nombre N double, le nombre de lignes reliant les modules N° l a Funique module N°2 double, ce qui peut rapidement devenir

* En anglais: "Misadjustment".

J

Module 1

Module 1

'•w Module 2

: ^ Module 2 ^

: ^ Module 2 ^

Module 2

P = X2 < 1 (7.2)

puisqu'on a \Xt\ < 1 dans le cadre de la realisation. Si on prend l'exemple d 'un signal sinusoidal, la puissance crete est egale au (

double de la puissance moyenne. Par consequent, on obtient : ^

- J - = ^ l = _ * ( ^ ; N - P N • P N • X2

iy ± iy ±c iv ^max ]

Mais puisque \X2

max\ < 1 et N < TA^12, on obtient : ]

4 4 2 nd\ YN\ N-X2

max NP 1

Bien entendu, cette preuve n'est valable que dans le cas particulier 1

d'un signal sinusoidal. Or, il arrive que, dans la plupart des signaux (

rencontres en pratique, la puissance crete est bien plus elevee que le j double de la puissance moyenne. Dans ce cas, on a :

max p ( 2 <

i

et la relation (7.4) est remplacee par : i (

4 4 2 1

/x = < — < , (7.5) TAH2 N • X2

max N • P

ce qui complete la preuve. s

c On mentionnait a la section 2 que I'algorithme d 'adaptat ion etait 1

concu de mamere a minimiser Ferreur quadrat ique moyenne. Mais r comme les signaux sont souvent de nature stochastique, ce critere 1

104 CAN. J. ELECT. & COMP. ENG., VOL. 16, NO. 3, 1991

deraisonnable. De plus, la duree d 'un pas de l'iteration depend fortement du temps de traversee dans l 'arbre sommateur, qui augmente notamment d 'un etage a chaque fois que N double. On expliquait precedemment qu'il y avait avantage a intercaler des niveaux pipelines a l'interieur de cet arbre. Ceci peut se faire en decomposant l 'arbre sommateur en plusieurs modules N°2 disposes selon une topologie arborescente (figure 8). On peut, par exemple, diviser les N modules N ° l en groupes de L modules. A chaque groupe est connecte un module N°2. Les N/L modules N°2 ainsi utilises sont a leur tour divises en groupe de L modules. La aussi, a chaque groupe de modules N°2 est connecte un module N°2 s u p p l e m e n t a l qui recueille et somme les extraits produits par les premiers sommateurs. Cette procedure se repete recursivement jusqu 'a ce qu'il n'y ait qu 'un module N°2 a la tete de l 'arbre. Ainsi la duree d'un pas reste constant, de meme que la cadence de l'horloge, peu importe N.

Conclusion

La realisation numerique de l 'algorithme M C M , decrite dans ce papier, permet de deborder facilement des domaines d'applications courantes que sont l 'audio et le vocal. En effet, le traitement qui est de nature parallele, permet une periode d'echantillonnage de 0 ( log N). L' implantation contient relativement peu de circuits puisque que plusieurs multipheurs sont integres dans le meme. De plus, la communication entre les circuits se fait en serie, ce qui restreint de fa9on appreciable la dimension des bus. Comme l ' implantation ne requiert que deux types de circuits, elle autorise des economies d'echelle. Enfin, on n 'a pas a se soucier de la convergence de l 'algorithme puisque le pas d e c r e m e n t a t i o n se

regie automatiquement. Toutefois, il est possible d'ajuster ce dernier en retardant le transfert serie de l'erreur d'estimation aux correcteurs.

Remerciements

Les auteurs tiennent a remercier l'un des correcteurs anonymes pour les commentaires qui ont permis de clarifier la presentation de ce papier. Ce travail a ete supporte financierement par le Conseil de recherches en sciences naturelles et en genie du Canada.

References

1. Widrow, B., et Stearns, S.D., "Adaptive signal processing," Series in Signal Processing, Englewood Cliffs: Prentice-Hall, 1985.

2. Lee, E.A., "Programmable DSP architectures: Part 1," IEEE ASSP Magazine, Vol. 5, No. 4, octobre 1988, pp. 4-19.

3. Avizienis, A., "Signed-digit number representations for fast parallel arithmetic," IRE Trans, on Electronics Computers, Vol. 10, septembre 1961, pp. 389-400.

4. Lapointe, M., et Huynh, H.T., "Algorithme de l'accumulateur," Congres canadien en Genie electrique et informatique, Montreal, 17-20 septembre 1989, pp. 185-190.

5. Lapointe, M., "Architecture concurrente et applications a des realisations rapides de filtres numeriques invariants et adaptatifs," These de doctorat, Departement de Genie electrique, Universite Laval, Janvier 1991.

6. Booth, A.D., "A signed binary multiplication technique," Quart. J. Mech. and Applied Math., Vol. 4, Part 2, 1951, pp. 236-240.

7. MacSorley, O.L., "High-speed arithmetic in binary computers," Proc. of the IRE, Vol. 49, janvier 1961, pp. 67-91.

8. Ercegovac, M.D., et Lang, T., "On-the-fly conversion of redundant into conventional representations," IEEE Trans, on Computers, Vol. 36, No. 7, juillet 1987, pp. 895-897.

9. Caraiscos, C , et Liu, B., "A roundoff error analysis of the LMS adaptive algorithm," IEEE Trans, on ASSP, Vol. 32, No. 1, fevrier 1984, pp. 34-41.