Institut de Recherche en Communications et Cybernétique de Nantes 1 Implémentation en précision finie modélisation et recherche de réalisations optimales

1

Institut de Recherche en Communications et Cybernétique de Nantes

Implémentation en précision finie modélisation et recherche de

réalisations optimalesThibault HILAIRE1,3 - Philippe CHEVREL1,2

Yvon TRINQUET1 - Jean Philippe CLAUZEL3

1 IRCCyN, 2 École des Mines de Nantes, 3 PSA Peugeot Citroën

GdR MACS : GT MOSAR et GT SARLille, le 10 juin 2005

2


Plan général

• I. Contexte

• II. Problématique FWL

• III. Forme implicite spécialisée

• IV. Mesure de sensibilité

• V. Exemples

• VI. Conclusion

3


I. Contexte• Thèse Th. HILAIRE financée par PSA

• Lois de contrôle/commande LTI implémentées (mises en œuvre numériquement) dans un calculateur numériquement contraint– Calculs en précision finie (virgule fixe)

– Problématique venant du domaine automobile (PSA)

• Problématique "temps réel"

• Problématique numérique– Dégradation de la loi lors de l'implémentation

• Modification des caractéristiques

• Modification des performances

Comment maîtriser et minimiser cette dégradation ?

4


Plan général

• I. Contexte• II. Problématique FWL

– 1. Présentation générale– 2. Méthodologie "logicielle"– 3. Méthodologie "automatique"– 4. Exemples d'implémentation

• III. Forme implicite spécialisée• IV. Mesure de sensibilité• V. Exemples• VI. Conclusion

5


II.1 Présentation générale• Calculs en précision finie (Finite Word Length)

– On considère principalement la représentation des nombres en virgule fixe (par opposition à la virgule flottante)

– Le pas de quantification est fixé– La dynamique des variables est limitée et figée

€

2p N

€

N nombre entier (signé ou non) sur b bitsentier représentant le facteur d'échelle

€

p

1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 … 1 0 1 1 0 … …,819,26562.… approximé par 819,25 (4 bits derrière la virgule)

6


II.1 Présentation générale• La dégradation FWL a deux origines

1. Quantification des coefficients mis en jeu

2. Bruits de quantification qui apparaissent dans les calculs (dus aux arrondis)

7


II.1 Présentation générale• Deux points de vue

– Point de vue "logiciel"Choix d'un code logiciel permettant de réaliser au mieux un ensemble d'équations mathématiques (augmenter la précision, diminuer le coût de calcul)

– Point de vue "automatique"Choix des équations mathématiques les mieux adaptées pour l'implémentation

• Ces points de vue sont complémentaires, mais peu confrontés

8


II.2 Techniques du logiciel• Consiste principalement

– À traduire en code un ensemble d'équations mathématiques, en prenant en compte les contraintes de précision

• Méthodologie de conversion automatique de code en virgule flottante vers du code en virgule fixe [Kedi98],[Kim98]

• Choix du positionnement de la virgule, gestion des overflow, underflow

– À évaluer la dégradation due à la virgule fixe• Evaluation du Rapport Signal à Bruit de Quantification Analytiquement

(dans certains cas) ou par la simulation [Mena02]

– À choisir la forme du calcul• Il est possible d'émuler un calcul à une précision supérieure, au

détriment du temps de calcul – (Ex: calculs 32 bits sur un calculateur 16 bits)

• Utilisation de techniques logicielles pour diminuer la dégradation

9


Plan général

• I. Contexte• II. Problématique FWL

– 1. Présentation générale– 2. Méthodologie "logicielle"– 3. Méthodologie "automatique"

• Modélisation• Analyse : mesures de sensibilité et du bruit de quantification• Opérateur

– 4. Exemples d'implémentation

• III. Forme implicite spécialisée• IV. Mesure de sensibilité• V. Exemples• VI. Conclusion

10


II.3 Modélisation• Lois de contrôle/commande :

•Filtres / Régulateurs LTI

•Cartographies

•Régulateurs LPV

•Etc.

– Lois caractérisées par leur relation entrée(s)/sortie(s) (avec calcul d'un état)

• On ne s'intéressera ici qu'au cas LTI

€

xk +1 = f (xk,uk )

yk = g(xk,uk )

⎧ ⎨ ⎩

11


II.3 Modélisation• Cas LTI :

• Pour une loi donnée, il existe une infinité de réalisations équivalentes (par exemple, par changement de base).

En précision finie, ces réalisations ne sont plus équivalentes

La dégradation dépend de la réalisation choisie

• Il convient donc de rechercher, parmi les réalisations possibles, celles qui minimisent un critère caractérisant la dégradation FWL

€

Xk +1 = AX k + BUk

Yk = CX k + DUk

⎧ ⎨ ⎩

12


II.3 Sensibilité de la fonction de transfert vis à vis des coefficients

On ne considère que la quantification des coefficients (les calculs sont supposés exacts)

• Pour un système (A,B,C,D) de fonction de transfert H(z)

[Geve93] propose une mesure de sensibilité

Le problème de recherche de réalisation "optimale" s'écrit

€

ML2(A,B,C) =

∂H

∂A 2

2

+∂H

∂B 2

2

+∂H

∂C 2

2

€

minT inversible

ML2(T−1AT,T−1B,CT)

13


II.3 Sensibilité vis à vis des coefficients

D'autres mesures de sensibilité vis à vis des coefficients sont étudiées :

• Sensibilité des pôles/zéros [Geve93],…

• Sensibilité de la stabilité (en boucle fermée) [Iste01]

• Sensibilité des pôles en boucle fermée [Wu00]

• Autres mesures dérivées

14


II.3 Bruits de quantificationOn ne considère que les bruits de quantifications dus aux

calculs (les coefficients sont représentés exactement)• Hypothèses de réalisation des calculs

– Roundoff Before Multiplication

– Roundoff After Multiplication

• On étudie la variance de l'erreur de sortie (entre réalisation exacte et réalisation implémentée)– Dans le cas RBM, la variance s'exprime en fonction du Grammien

d'observabilité

€

˜ x (t +1) = AQ ˜ x (t)[ ] + BQ u(t)[ ]

€

˜ x (t +1) = Q A˜ x (t)[ ] + Q Bu(t)[ ]

15


II.3 Bruits de quantification• Les hypothèses de calcul sont tout de même réductrices

– Pas de prise en compte de la taille des calculs (nb de bits)

– Pas de prise en compte de la méthode de représentation des coefficients et du vecteur d'état

– Quelques cas spécifiques (réinjection de la partie tronquée Residue Feedback, …) sont traités

– Différent types d'arrondis (roundoff, truncate, …)

16


II.3 Opérateur On considère d'autres réalisations

• Opérateur

• Réalisations équivalentes

€

=q −1

Δ

€

qXk = Aq Xk + BqUk

Yk = Cq X k + DqUk

⎧ ⎨ ⎩

⇔ δX k = Aδ Xk + Bδ Uk

Yk = Cδ Xk + Dδ Uk

⎧ ⎨ ⎩

€

Aδ =Aq − I

ΔBδ =

Bq

ΔCδ = C Dδ = Davec

[Midd90]

17


II.3 Opérateur • On montre que les réalisations en sont mieux

conditionnées numériquement– Sensibilité de la fonction de transfert et de la stabilité vis à vis des

coefficients est meilleure en qu'en q, dès que ∆<1

– Nouvelles mesures de sensibilité pour les réalisations en – Études, comparaisons de réalisations en q et en

18


II.4 Exemples d'implémentationPar exemple, on considère un système du 2nd ordre

€

H(z) =b0 + b1z

−1 + b2z−2

1+ a1z−1 + a2z

−2

Une 1ère façon (la plus naturelle) d'implémenter serait :

€

Yk = b0Uk + b1Uk−1 + b2Uk−2 − a1Yk−1 − a2Yk−2

On peut aussi utiliser une représentation dans l'espace d'état minimale. Le choix de l'espace est important (forme canonique, forme équilibrée, …)

€

Xk +1 = AX k + BUk

Yk = CXk

⎧ ⎨ ⎩

19


II.4 Exemples d'implémentationOn peut aussi écrire l'algorithme en utilisant l'opérateur

€

T = Aδ Xk + Bδ Uk

Xk +1 = Xk + ΔT

Yk = Cδ Xk

⎧

⎨ ⎪

⎩ ⎪

Ou bien encore avec une forme retour d'état/observateur

Pour chaque forme, les coefficients implémentés ne sont pas les mêmes, les effets de la quantification sont différents

€

Xk +1 = (Aδ Δ + I)Xk + Bδ ΔUk

Yk = Cδ Xk

⎧ ⎨ ⎩

Choix de la réalisation

20


II.4 Exemples d'implémentations• En plus de la structure, il est aussi possible d'agencer les

calculs de différentes façons– Ex:

€

T = b0Uk + b1Uk−1 + b2Uk−2

Yk = Q[T] − a1Yk−1 − a2Yk−2

Calcul émulé 32b

Une implémentation :des coefficients (paramétrisation)une structure de calculs

21


II.4 Problèmes ouverts• Les travaux théoriques de l'Automatique ne prennent pas en

compte les solutions algorithmiques souvent mises en oeuvre– Rapprochement des deux approches automatique/informatique

– Savoir qualifier des techniques/algorithmes existants

• Les coefficients implémentables exactement (0, ±1, puissances de 2, …) ne sont pas pris en compte

• Cas MIMO

• Méthodologie d'implémentation

22


Plan général

• I. Contexte• II. Problématique FWL• III. Forme implicite spécialisée

– 1. Recherche d'un modèle plus réaliste– 2. Forme implicite spécialisée– 3. Exemples

• IV. Mesure de sensibilité• V. Exemples• VI. Conclusion

23


III.1 Recherche d'un modèle plus réaliste• On recherche un modèle macroscopique suffisamment

général et davantage représentatif de l'implémentation– Prise en compte des diverses possibilités d'algorithmes et de

réalisations (q, , retour d'état observateur, …) : formalisme unificateur

– Relation avec le code plus explicite

24


III.1 Forme implicite spécialisée• On propose de décrire les diverses possibilités d'algorithmes

€

(1) JTk +1 = MX k + NUk

(2) EXk +1 = KTk +1 + PX k + QUk

(3) Yk = LTk +1 + RXk + SUk

Calculs des variables intermédiaires

Calculs de l'état

Calculs des sorties

€

J 0 0

−K E 0

−L 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 M N

0 P Q

0 R S

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

25


III.1 Forme implicite spécialisée• Variables intermédiaires

– Il est intéressant de faire apparaître explicitement tous les calculs réalisés, ainsi que les variables intermédiaires utilisées

– Cela permet de distinguer/séparer des calculs réalisés différemment, afin de les caractériser

• Exemple : réalisation en

€

T = Aδ Xk + Bδ Uk

Xk +1 = Xk + Δ.T


26


III.1 Forme implicite spécialisée• Forme implicite spécialisée :

€

J 0 0

−K E 0

−L 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 M N

0 P Q

0 R S

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk est une variable intermédiaire

27


III.1 Forme implicite spécialisée• Forme implicite

– L'état ou la sortie pouvant être calculé à partir des variables intermédiaires, cela implique une forme implicite

– Une variable intermédiaire peut être calculée à partir d'une autre variable intermédiaire préalablement calculée, le calcul de T s'écrit

– J n'a pas à être inversée

€

JT = MX k + NUk

avec

⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜

⎝

⎛

∗∗

∗=

1

1

1

L

OOMJ

28


III.1 Forme implicite spécialisée• Forme implicite spécialisée :

€

J 0 0

−K E 0

−L 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 M N

0 P Q

0 R S

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Réutilisation des variables intermédiaires

Forme implicite classique

29


III.1 Forme implicite spécialisée• On peut la rendre explicite

€

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 J−1M J−1N

0 A B

0 C D

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

• D'où une fonction de transfert H(z)

€

A = E−1KJ−1M + E−1P

B = E−1KJ−1N + E _1Q

C = LJ−1M + R

D = LJ−1N + S

avec

€

H(z) = C(zI − A)−1B + D

30


III.4 Exemples• Réalisations en

€

In 0 0

−ΔIn I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 Aδ Bδ

0 I 0

0 Cδ Dδ

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟€

Xk = Aδ Xk + Bδ Uk


⎧ ⎨ ⎩

Une réalisation en s'exprime comme une réalisation implicite non minimale avec l'opérateur q

31


III.4 Exemples• Réalisations cascade

€

A1 B1

C1 D1

⎛

⎝ ⎜

⎞

⎠ ⎟

€

A2 B2

C2 D2

⎛

⎝ ⎜

⎞

⎠ ⎟

€

A1 0

B2C1 A2

B1

B2D1

D2C1 C2 D2D1

⎛

⎝

⎜ ⎜

⎞

⎠

⎟ ⎟

€

I 0 00

−B2

⎛

⎝ ⎜

⎞

⎠ ⎟ I 0

−D2 0 I

⎛

⎝

⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 C1 0( ) D1

0A1 0

0 A2

⎛

⎝ ⎜

⎞

⎠ ⎟

B1

0

⎛

⎝ ⎜

⎞

⎠ ⎟

0 0 C2( ) 0

⎛

⎝

⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

32


III.4 Exemples• Retour d'état observateur

€

ˆ X k +1 = A ˆ X k + BUk + L(Yk − C ˆ X k )

Uk = −K ˆ X k

⎧ ⎨ ⎪

⎩ ⎪

Une réalisation possible :

€

I 0 0

B I 0

−I 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 −K 0

0 A − LC L

0 0 0

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk

Xk

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

33


III.4 Exemples• La forme implicite spécialisée permet bien

– une meilleure représentativité de la mise en œuvre numérique

– d'unifier des représentations diverses

• Il faut ensuite mettre en place des critères génériques de qualité permettant d'évaluer l'impact de l'implémentation

– Coût de calcul

– Sensibilité à la quantification des coefficients

– Bruits de quantification

– …

34


Plan général

• I. Contexte• II. Problématique FWL• III. Forme implicite spécialisée• IV. Mesure de sensibilité• V. Exemples• VI. Conclusion

35


IV. Mesure de sensibilité• Maintenant que l'on peut exprimer tous les coefficients qui

entrent en jeu dans une mise en œuvre numérique, il est intéressant d'exhiber une mesure de sensibilité de la fonction de transfert vis à vis des coefficients mis en jeu

• Par analogie avec [Geve93], on propose une 1ère mesure

€

ML2

1 =∂ ˜ H

∂XX ∈ E ,J ,K ,L,M ,N ,P ,Q,R ,S{ }

∑2

2

€

˜ H (z) = H(z) − Davec

est strictement propre

est indépendant de toute transformation

€

˜ H

€

∂D

∂X

36


IV. Mesure de sensibilité• Il faut ensuite prendre en compte les coefficients qui vont

être quantifiés pour l'implémentation– Dans la forme implicite spécialisée, de nombreux coefficients sont

nuls ou égaux à 1 et n'ont pas à être implémentés

– Certains coefficients (puissances de 2, …) peuvent être représentés exactement

• À une matrice X de coefficients, on associe une matrice de pondération WX

€

WX( )i, j=

0 si X i, j peut être exactement implémenté

1 sinon

⎧ ⎨ ⎩

37


IV. Mesure de sensibilité

• On pose la matrice des normes des sensibilités par

rapport aux éléments de X

• La précédente mesure s'écrit :

• On pondère cette mesure :

€

H

δX

⎛

⎝ ⎜

⎞

⎠ ⎟i, j

=∂H

∂X i, j 2

€

H

δX

€

ML2

1 =δ ˜ H

δXX ∈ E ,J ,K ,L,M ,N ,P ,Q,R ,S{ }

∑F

2

€

ML2

W =δ ˜ H

δX×WX

X ∈ E ,J ,K ,L,M ,N ,P ,Q,R ,S{ }

∑F

2

produit direct

38


IV. Mesure de sensibilité• Cette mesure peut aussi s'écrire

€

ML2

W =δ ˜ H

δZ×WZ

F

2

+δ ˜ H

δE×WE

F

2

avec

€

Z =

−J M N

K P Q

L R S

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

39


Plan général

• I. Contexte• II. Problématique FWL• III. Forme implicite spécialisée• IV. Mesure de sensibilité• V. Exemples• VI. Conclusion

40


V.1 Exemples• On considère la fonction de transfert suivante

– Ce filtre choisi car il possède un triple zéro pour z=-1, et que la position des zéros est donc très sensible par rapports aux coefficients implémentés [Geve93],[Hwan77]

• Comparaison de différentes réalisations (par rapport à leur sensibilité paramétrique et à leur coût de calcul)

4538.05562.19749.1

)1(01594.0)(

23

3

−+−+

=zzz

zzH

41


V.1 Exemples• réalisation canonique, opérateur q

€

1 0 0

0 I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 0 0 0 0

0 1.9749 −1.5562 0.4538 1

0 1 0 0 0

0 0 1 0 0

0 0.0793 0.0230 0.0230 0.0159

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Sensibilité (A,B,C non pondérés)

€

˜ H

δP Q

R S

⎛

⎝ ⎜

⎞

⎠ ⎟

=

3.7652 3.7652 3.7652 0.48065

4.3081 4.3081 4.3081 0.55775

1.7248 1.7248 1.7248 0.21935

4.1308 4.1308 4.1308 0

⎛

⎝

⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟€

ML2

W =158.91

42


V.1 Exemples• réalisation canonique, opérateur q

€

I 0 0

0 I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 0 0 0 0

0 1.9749 −1.5562 0.4538 1

0 1 0 0 0

0 0 1 0 0

0 0.0793 0.0230 0.0230 0.0159

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Sensibilité (A,B,C pondérés)

€

˜ H

δP Q

R S

⎛

⎝ ⎜

⎞

⎠ ⎟

×W =

3.7652 3.7652 3.7652 0

0 0 0 0

0 0 0 0

4.1308 4.1308 4.1308 0

⎛

⎝

⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟€

ML2

W = 93.72

43


V.1 Exemples• réalisation équilibrée (opérateur q)

€

I 0 0

0 I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

X k +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 0 0 0 0

0 0.8237 0.3999 0.0164 −0.4424

0 0.3999 0.5935 0.3425 0.3799

0 0.0164 −0.3425 0.5578 0.1671

0 −0.4424 −0.3799 0.1671 0.0159

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Sensibilité

€

˜ H

δP Q

R S

⎛

⎝ ⎜

⎞

⎠ ⎟

×W =

1.4756 0.9201 0.4604 0.9122

0.9201 0.7845 0.3242 0.6704

0.4604 0.3242 0.1577 0.3426

0.9122 0.6704 0.3426 0

⎛

⎝

⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟€

ML2

W = 7.9432

[Geve93]

44


V.1 Exemple• Réalisations avec l'opérateur

– On choisit ∆=0.5

– On étudie les différentes réalisations, parmi celles équivalentes par changement de base€

Aδ =Aq − I

ΔBδ =

Bq

ΔCδ = C Dδ = D

€

T _1Aδ T,T−1Bδ ,Cδ T,Dδ( )

45


V.1 Exemple• Réalisation avec l'opérateur

– Forme canonique

€

I 0 0−Δ 0 0

0 −Δ 0

0 0 −Δ

I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 −2.0502 −2.4256 −1.0200 1

0 1 0 0 0

0 0 1 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0.1586 0.7265 1.0039 0.0159

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

€

˜ H

δZ×WZ =

0 0 0 0.4761 0.4121 0.4706 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

1.2129 0 0 0 0 0 0

0 2.0131 0 0 0 0 0

0 0 1.3099 0 0 0 0

0 0 0 0.7881 0.5214 0.5163 0

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

€

ML2

W = 9.0171

€

ML2

W =1.7777

46


V.1 Exemple• On a vu que, pour les deux structurations (en q et en ), on

pouvait obtenir des réalisations équivalentes par un changement de base sur les matrices systèmes A,B,C,D– Classes et sous-classes de réalisations équivalentes

• On cherche donc le changement de base qui minimise la mesure de sensibilité– Problème d'optimisation

– Utilisation d'un algorithme de recuit simulé adaptatif

47


V.1 Exemple• Réalisation optimale, structuration en q

€

I 0 0

0 I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 0 0 0 0

0 0.8173 0.5439 −0.0483 −0.2718

0 −0.4718 0.5373 0.1256 −0.4674

0 0.1476 −0.1042 0.6203 −0.3215

0 −0.3210 −0.3189 −0.4389 0.0159

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

Sensibilité

€

˜ H

δP Q

R S

⎛

⎝ ⎜

⎞

⎠ ⎟

×W =

1.2307 0.8584 0.6776 0.8240

0.9495 0.7652 0.4105 0.6806

0.5904 0.3402 0.4703 0.5308

0.8180 0.6698 0.5263 0

⎛

⎝

⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟

€

ML2

W = 7.8704

48


V.1 Exemple• Réalisation optimale avec l'opérateur

€

I 0 0−Δ 0 0

0 −Δ 0

0 0 −Δ

I 0

0 0 I

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟

Tk +1

Xk +1

Yk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟=

0 −0.7254 −0.5211 −0.5718 0.2110

0 0.2399 −0.4314 −0.7084 −0.8189

0 0.3830 1.0377 −0.8933 0.0981

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0.8098 −0.0173 −0.2696 0.0159

⎛

⎝

⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

Tk

Xk

Uk

⎛

⎝

⎜ ⎜ ⎜

⎞

⎠

⎟ ⎟ ⎟

€

ML2

W = 4.5671

49


V.1 Exemple• Comparaisons

Réalisation Mesure sensibilité "nb opérations"

q canonique 93.72 6x 6+

q équilibrée 7.94 16x 16+

q optimale 7.87 16x 16+

canonique 9.01 9x 9+

optimal 4.56 20x 16+

Autres critères pertinents :- taille mémoire utilisée, lisibilité des calculs, flexibilité (face aux changement des paramètres signifiants), généricité

50


VI. Conclusion• État de l'art

– Problèmatique FWL

• Un résultat clé : la forme implicite spécialisée– Formalisme unificateur

– Forme macroscopique plus représentative des calculs mis en œuvre

– Cela ouvre le champ de l'analyse et la synthèse d'implémentations

• Des illustrations

51


VI. Conclusions• Réflexions en cours

– Caractérisations de classes d'équivalences élargies

– Efficacité de la synthèse d'implémentation optimisée

– Outils d'analyse et d'aide à la conception

– Prise en compte du bruit de quantification

– Extension au cas LPV

52


VI. Conclusions

53


VIII. Références[Kedi98] H. Keding, M. Willems, M. Coors, and H. Meyr, "FRIDGE : A fixed-point design and simulation

environment", EDAA, 1998

[Kim98] S. Kim, K. Kum, and W. Sung, "Fixed-point optimization utility for C and C++ based digital signal processing programs", IEEE Transactions on Circuits and Systems, vol. 45, pp. 1455-1464, November 1998.

[Mena02] D. Ménard, "Méhodologie de compilation d'algorithmes de traitement du signal pour les processeurs en virgule fixe sous contrainte de précision". PhD thesis, ENSSAT, december 2002.

[Geve93] M. Gevers and G. Li, "Parametrizations in Control, Estimation and Filtering Probems". Springer-Verlag, 1993.

[Iste01] R. Istepanian and F. Whidborne, eds., "Digital Controller implementation and fragility". Springer, 2001.

[Wu00] J. Wu, S. Chen, R. Istepanina, and J. Chu, "Shift and delta operator realizations for digital controllers with finite-word-length considerations", IEE Proc. Control Theory and Applications, 2000.

[Will92] D. Williamson, "Digital Control and Implementation, Finite Wordlength Considerations". Prentice-Hall International Editions, 1992.

54


A. Sensibilité vis à vis des coefficients

€

∂H(z)

∂A= C(zI − A)−1

( )T

(zI − A)−1B( )T

∂H(z)

∂B= C(zI − A)−1

( )T

∂H(z)

∂C= (zI − A)−1B( )

T

En SISO, on a

55


B. Sensibilité des pôles/zéros vis à vis des coefficients

• Si on note ()k et (µ)k les pôles et zéros de H(z), on peut s'intéresser à leur sensibilité face aux coefficients mis en jeu

• Plusieurs mesures sont proposées [Geve93],…

et les mesures dérivées (différentes pondérations)

€

Ψz =∂μ k

∂A F

2

+∂μ k

∂B F

2

+∂μ k

∂C F

2

+∂μ k

∂D F

2

k

∑

€

Ψp =∂λ k

∂A F

2

k

∑

56


C. Stabilité boucle fermée• Des mesures de stabilité en boucle fermée [Iste01],…

€

Ap Bp

Cp Dp

⎛

⎝ ⎜

⎞

⎠ ⎟

plant

€

Ac Bc

Cc Dc

⎛

⎝ ⎜

⎞

⎠ ⎟

controller €

A (X) =Ap + BpDcCp BpCc

BcCp Ac

⎛

⎝ ⎜

⎞

⎠ ⎟

€

X =Ac Bc

Cc Dc

⎛

⎝ ⎜

⎞

⎠ ⎟avec

€

μ0(X) = inf ΔX∞

: A (X + ΔX) is unstable{ }

€

μI (X) = mini

1− λ i(A (X))

∂λ i(A (X))

∂X 1X ∈{Ac ,Bc ,Cc ,Dc }

∑i(A) est la ième valeur propre de A

57


D. Dérivation matricielleSoient et une fonction différentiable selon tous les éléments de X

La sensibilité de f vis à vis de X est définie par

€

X ∈Rm×n

€

f :Rm×n → C p×q

€

∂f

∂X

⎛

⎝ ⎜

⎞

⎠ ⎟(i−1)p +k,( j−1)q +l

=∂fk,l

∂X i, j

€

∂f

∂Xpeut être vu comme

€

C p×q

€

∂f

∂X i, j

⎛

⎝ ⎜

⎞

⎠ ⎟i, j

une matrices d'éléments de

58


D. Dérivée matricielle• Pour le calcul de la sensibilité, on utilisera la notation

Soit G et H deux matrices (ou fonctions de transfert) de taille m,p et q,n.

Soit X une matrice de taille p,q

On suppose G et H indépendant vis à vis de X

On a alors :

( ) ( )( )( )

HG

HVecGVec

HIX

XGI

X

GXH

TT

qp

◊=

=

⊗⊗=

).(

)(

∂

∂

∂

∂

◊

59


D. Dérivée matricielle• On peut montrer que

( )⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

◊=

q

p

I

zH

zH

IzHzHZ

zH)(

)(

)()()(

2

4

13∂

∂

( )⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

◊=

−

−

q

p

I

NJ

ILJZ

D00

1

1

∂

∂

)()(~

51 zHzHE

H◊−=

∂∂

€

H1(z) = C(zIn − A)−1 E−1

H2(z) = (zIn − A)−1B

H3(z) = H1(z)KJ−1 + LJ−1

H4 (z) = J−1MH2(z) + J−1N

H5(z) = AH2(z) + B

avec

60


E. Terminologie• Réalisation R

Valeurs spécifiques des matrices de la forme implicite spécialisée

• Réalisations RH d'une fonction de transfert H(z)

Ensembles de réalisations ayant H(z) pour fonction de transfert

Ces fonctions sont dites equivalentes, de part leur même relation entrées/sorties

€

R =(E,J,K,L, M,N,P,Q,R,S)

61


E. Terminologie• Structuration S

Ensembles de réalisations qui ont une structure particulière : certains coefficients sont fixés a priori

Ex : structuration en

• Réalisation structuréeEnsemble des réalisations d'une fonction de transfert H(z) sous une

même structure

€

S = R \ R = I,I,ΔI,0,Aδ ,Bδ ,I,0,Cδ ,Dδ( ){ }

€

R HS = R H ∩ S

€

R HS

62


E. Problèmes de réalisations optimales• Soit H(z) une fonction de transfert à réaliser et M une

mesure de la qualité vis à vis de l'implémentation d'une réalisation (comme la sensibilité de la fonction de transfert vis à vis des coefficients, par exemple)

Le problème de recherche de réalisations optimales (optimal design) consiste à trouver la (ou les) réalisations Ropt de la fonction de transfert H selon la mesure M

• Ce problème est difficile, vu la taille de RH

€

R opt = argminR ∈R H

M R( )

63


E. Problèmes de réalisations optimales• Il peut être alors interessant de considérer un sous-problème

: la recherche de réalisations optimales pour une structuration donnée.

• Pour une structuration donnée (ordre fixé), on peut souvent exprimer à partir d'un élément et de changements de base

€

R HS

64


II.4 Bruits de quantification

On définit

€

σΔy2 = lim

t →∞E Δy(t){ }

2

[ ]et

€

Δy(t) = y(t) − ˜ y (t)

Variance d'erreur de sortie

[Will92],[Geve93],…

Pour l'arrondi avant la multiplication, la variance d'erreur de sortie est donnée par le Grammien d'observabilité

€

σΔy2 = tr(WO )σ u

2

Documents

Institut de Recherche en Communications et Cybernétique de Nantes 1 Implémentation en précision finie modélisation et recherche de réalisations optimales