Brevet FR2099446A1 — publié le 19720317

L'invention se rapporte à des procédés et dispositifs pour élaborer des fonctions, et notamment des fonctions trigonométriques, par des processus d'interpolation. Lorsqu'on traite des informations, il est souvent nécessaire de con-5 naître la valeur d'une fonction F(x) pour n'importe quelle valeur de x dans un intervalle donné. La fonction F(x) peut être mise en mémoire sous forme d'un tableau de valeurs mais une telle mémoire doit avoir une capacité très importante dès que l'on désire taie précision élevée, de l'ordre de 16 bits par exemple. Jusqu'à présent différentes techniques d'interpolation ont été propo-10 sées sais du fait qu'elles utilisent généralement des interpolations linéaires, de nombreuses valeurs de F(x) -ou les différences premières de ces valeurs-doivent être sises en mémoire pour approcher la courbe désirée avec suffisamment de précision. Le procédé selon l'invention se rapporte à une forme modifiée d'inter-15 polation linéaire, qui permet d'introduire des termes correctifs de degré deux, trois ou plus, grâce auxquels on obtient des interpolations très précises. Ces termes sont ceux d'une série polynomiale qu'on appellera série de polynômes binaires et dont les propriétés seront expliquées par la soite. La technique de base de cette interpolation sera désignée par l'ex-20 pression "interpolation par bissection répétée du segment d'interpolation", c'est-à-dire du segment joignant deux valeurs de la fonction situées de part et d'autre de la valeur donnée de x. La valeur correspondant au milieu de ce segment peut être obtenue par interpolation. On dispose alors de deux segments moitiés obtenus par bissection du segment original, dont l'un comprend la 25 valeur donnée de x et constitue le nouveau segment intéressant. Ce dernier segment peut être à nouveau bissecté et ainsi de suite autant de fois qu'on le désire de façon à converger vers la valeur donnée de x. La bissection répétée du segment d'interpolation constitue donc un processus itératif très facile à mettre en oeuvre tant au point de vue circuits qu'au point de vue programmes• 30 Selon l'invention un dispositif pour interpoler une fonction d'une variable indépendante en effectuant les bissections répétées d'un intervalle de valeurs de ladite variable, comprend au moins tin premier, un deuxième et un troisième registre pour garder des quantités qui définissent la fonction, des moyens pour introduire dans chacun desdits registres une combinaison linéaire 55 des contenus d'un ou plusieurs desdits registres, divisée par une puissance de deux différente pour chaque registre, ladite combinaison étant commandée de façon sélective, pour au moins un desdits registres, par les digits d'un mot binaire définissant la valeur donnée de la variable indépendante, lesdlts digits étant pris successivement, un par bissection. 71 26328 2099446 Pour obtenir une bonne précision on utilise de préférence plus de trois registres. Ainsi, en plus des premier et deuxième registres le dispositif peut comprendre une pluralité de registres ordonnés qui inclut ledit troisième registre, chacun de ces registres recevant une combinaison algébrique 5 linéaire de son propre contenu et, excepté pour le registre d'ordre le plus élevé, des contenus des registres d'ordre plU3 élevé, ladite combinaison étant divisée par 2^ = 4 dans le cas du troisième registre, par 2? = 8 dans le cas du quatrième registre et ainsi de suite. Les quantités initiales introduites dans le troisième registre ou 10 les registres d'ordre plus élevé doivent être des valeurs prédéterminées appropriées à la fonction étudiée et sont généralement fournies par une mémoire permanente en même temps que les valeurs initiales de la fonction. L'Invention permet d'Interpoler avec précision des fonctions à partir d'un très petit nombre d'informations mises ai mémoire. 15 L'intérêt de la technique peut être démontré en mentionnant brièvement quelques exemples. Sin x peut être interpolé dans l'intervalle 0* à 90° arec une précision de 12 bits à partir d'informations mises «a mémoire comportant seulement (en plus des deux valeurs Initiales sin 0° et sin 90*) trois coefficients qui permettent d'obtenir respectivement des termes du deuxième, troisième 20 et quatrième degré. De plus, le même dispositif permet d'interpoler de nombreuses autres fonctions pour chacune desquelles il suffit de mettre en mémoire deux valeurs Initiales de la fonction et trois coefficients. Les registres peuvent faire partie de circuits de calcul spécialement destinés à cette utilisation comme dans les modes de réalisation décrits par 25 la suite. Ils peuvent aussi consister en différentes adresses permettant l'accès à la mémoire d'un calculateur à usages multiples, progrenoé de façon à fonctionner selon les principes de l'invention. Le calcul itératif des combinaisons algébriques linéaires peut être représenté par un algorithme dont la forme varie. Des exemples particuliers 30 d'algorithmes sont donnés par la suite, de rême que certaines variantes possibles. Il est Impossible de donner toutes les variantes qui peuvent être envisagées. La forme de 1'algorithme est principalement déterminée par les quantités sélectionnées corne» entrées initiales des registres. Ces quantités peuvent être différentes de celles mentionnées par la suite. Par exemple, en modifiant de 35 façon convenable les algorithmes, on peut effectuer une série d'interpolations à partir d'échantillons de valeurs de la variable dépendante. On peut toutefois utiliser les mêmes registres, c'est-à-dire un registre diviseur par 1, un registre diviseur par 2, un registre diviseur par 4 etc.. 71 26328 3 2099446 En général les algorithmes sont du type "addition-décalage" et par conséquent particulièrement faciles à mettre en oeuvre du fait que les seules opérations à effectuer sont des sommes (étant entendu que le signe doit être pris en considération, certaines sommes pouvant être des soustractions) et 5 des décalages vers les bits les moins significatifs, ces décalages constituant des divisions par 2, 4 etc.. De tels décalages sont effectués facilement en numération série comme décrit par la suite. En numération parallèle, il existe aussi des techniques connues permettant de réaliser de tels décalages. L'une de ces techniques utilise des registres à entrées parallèles qui sont aussi 10 des registres à décalage. Après avoir introduit un nombre dans le registre par l'intermédiaire d'une voie multiple, on applique des impulsions de décalage de feçanà]e diviser par la puissance de deux choisie. Une autre technique consiste à introduire le nombre au moyen d'une voie de transmission multiple reliée au registre de façon à introduire le nombre après avoir effectué le 15 décalage. Pour diviser par 4, par exemple, et en supposant que l'on a numéroté les lignes de la voie et les entrées du registre du bit le plus significatif au bit le moins significatif, la première ligne est reliée à la troisième entrée du registre, la deuxième ligne est reliée à la quatrième entrée du registre, et ainsi de suite. 20 Jusqu'à présent on a décrit l'utilisation de l'algorithme dans le mode direct c'est-à-dire que l'on calcule jr connaissant x. Un avantage important de l'invention réside dans le fait que l'algorithme peut également être utilisé dans le mode inverse pour calculer x connaissant jr. Les mêmes circuits peuvent en effet servir à calculer par exemple sin x dans le mode direct et 25 arc sin y dans le mode inverse. Cette solution est possible car, dans le mode direct, les choix successifs du demi-segment supérieur ou inférieur, sont commandés par les bits successifs de x. Dans le mode inverse un essai permet pour chaque interpolation de déterminer si la sélection du demi-segment supérieur donne une valeur calculée de jr supérieure ou non à la valeur donnée de jr appelée 30 Y. Si ;jr est inférieur à Y un bit 1 est introduit dans x et l'on garde là sélection du demi-segment supérieur. Si £ est supérieur à Y un bit O est introduit dans x et le demi-segment supérieur est écarté au profit du demi-segment inférieur. De cette façon, les interpolations successives font converger la valeur calculée de £ vers Y à mesure que les bits de x sont introduits, en partant du 35 bit le plus significatif. Evidemment, si, à un moment donné y = Y le calcul s'arrête, tous les bits restants de x étant égaux à 0. 71 26328 4 2099446 Les caractéristiques et avantages de l'invention ressortiront d'ailleurs mieux de la description qui va suivre donnée à titre d'exemple non limitatif en référence aux dessins annexés dans lesquels : - la figure 1 est un diagramme qui représente une interpolation 5 linéaire, - les figures 2 et 3 sont des diagrammes représentant une interpolation du deuxième degré, - la figure 4 est un schéma d'ensemble d'un dispositif pour la mise en oeuvre d'un algorithme d'interpolation du deuxième degré, 10 - les figures 5 et 6 sont des diagrammes représentant l'utilisation des séries binaires pour approcher une fonction sin ©. - la figure 7 est un schéma d'ensemble d'un mode de réalisation de l'invention pour la mise en oeuvre d'un algorithme d'interpolation du troisième degré, 15 - la figure 7A est un circuit de cadencement pour la figure 7, - les figures SA à 8g sont des représentations graphiques des polyno-mes binaires du deuxième au huitième degré, - les figures 9 à 13 sont des diagrammes fonctionnels représentant des algorithmes du deuxième au huitième degré, 20 - la figure 11A est une variante de l'algorithme du quatrième degré de la figure 11, - la figure 14 est un schéma d'ensemble d'un autre mode de réalisation de l'invention pour mettre en oeuvre l'algorithme du troisième degré en utilisant une numération bits-parallèles et mots-série, 25 - la figure 15 est un schéma d'ensemble d'un autre mode de réalisa tion de l'invention pour mettre en oeuvre l'algorithme du troisième degré utilisant une numération bits-série, mots-série, - la figure 16 est un schéma d'ensemble représentant un fonctionnement dans le mode inverse pour un algorithme donné, et 30 - la figure 17 est un diagramme représentant la~détermination des coefficients pour un polynome binaire. Interpolation par bissection répétée La figure 1 représente une fonction linéaire y(x) sur un segment allant de x = 0 à x = 1. y(0) = 2a et y(l) =» 2b. Dans la première inter- 35 polation, y(l/2) est obtenu simplement par l'expression (2a + 2b)/2 = a + b. Pour la deuxième interp-1 -ution, on a le choix entre deux options. On peut calculer : 71 26328 5 2099446 soit y(3/4) - [y(V2) + 2b} /2 = (y(l/2) ]/2 + b soit y(3A) « [2a + y(l/2)J /2 » a + Jy(l/2)J /2 Le choix dépend de l'intervalle, l/2 à 1 ou 0 à l/2, dans lequel se trouve la valeur donnée de x. Sur la figure 1 on a supposé que la valeur donnée de x 5 était 3/8. La suite des interpolations, symbolisées par des flèches verticales, est donc : 1°) Interpolation donnant y(2/2) = a + b 2°) Interpolation donnant y(l/4) = a*£y(l/2)J /2 3e) Interpolation donnant y(3/8) « jy(l/4) J/2 + Jy(l/2)J /2 10 Ce processus peut évidemment être poursuivi en augmentant le nombre d'interpolations de façon à approcher la valeur donnée de x avec la précision désirée. Le choix effectué après chaque interpolation consiste à calculer la valeur suivante de j soit au-dessus soit au-dessous de la valeur de j obtenue préeédeœnent. En d'autres termes le choix est soit montant (M), soit descendant 15 (D). Ainsi, y(3/4) est M par rapport à y(l/2) et y(l/4) est D par rapport à y Cl/2). Interpolation sur une parabole La figure 2 représente une parabole de la forme : y a 4x(l - x), dans laquelle y(0) = y(l) » 0 et y(l/2) = 1 20 L'interpolation donnant y(l/2) peut être considérée comme une interpolation linéaire à laquelle est ajouté un terme correctif K = 1 que l'on appellera la correction résiduelle et que l'on désignera pour plus de précision par le symbole K n étant le numéro d'ordre de l'interpolation. Pour la deuxième rbsJL interpolation on choisit soit x = 1/4 soit x = 3/4 qui donnent tous les 25 deux y « 3/4. D'après les segments 101 et 102 de la figure 2 on constate que l'interpolation linéaire donne des valeurs égales à l/2 et qu'il existe par conséquent une correction résiduelle égale à 1/4. On peut montrer, de la même façon, que K_ , = l/l6, k On constate que Kn = 1/4 Kn ^ et qu'il est donc possible d'interpoler exactement sur une parabole, étant données les deux valeurs initiales et la valeur initiale de K, cette dernière étant divisée par quatre avant chaque 35 nouvelle interpolation. Cette caractéristique apparaît plus clairement sur 71 26328 2099446 la figure 3 qui représente une parabole 105 superposée à un segment de droite 104. Pour des raisons de simplification les différentes interpolations possibles ne sont pas toutes données, un choix arbitraire de la direction M ou D étant effectué pour chaque étape : y(l/2) - a + b + K D y(V*0 - a + jy(3/2)J /2 + K/4 yOA)] /2 + [y(3/2)T/2 + K/16 y(3/8)" /2 + |y(3/2) " /2 + K/64 Ces calculs peuvent être résinés par l'algorithme suivant s M y (3/8) M y(7/l6) 10 y = a + b + K 'n n n n dans lequel t al* ^i» e't ^ son'f' ^es valeurs initiales, - K « (K , )/4 n v n-1 ' - Montant î b=b, et a » (y . )/2 n n-1 n wn-l 15 - Descendant: b =• (y . )/2 et a » a , n n-l n n-l Mise en oeuvre de 1'algorithme du deuxième degré Avant de décrire les algorithmes d'une façon générale, on va tout d'abord considérer un «ode de réalisation simple de l'invention, représenté sur la figure 4. Dans cet exemple on suppose que l'on utilise des registres 20 à décalage pour recevoir les valeurs apparaissant dans l'algorithme et qie l'on effectue les divisions par des puissances de deux en décalant, suivant une technique bien connue, le contenu du registre dans la direction des digits les moins significatifs. Sur ce schéma on n'a pas représenté les circuits de eadencement four-25 nlssant les impulsions de décalage des registres et les impulsions de commande de succession des différentes étapes, ni les portes qui commandent les transferts d'informations. De tels détails, qui sont bien connus des spécialistes, ne feraient que compliquer le schéma. Des circuits de cadencement seront d'ailleurs déerits brièvement par la suite en référence à la figure *fk. 30 Le circuit représenté sur la figure 4 comprend des registres à décalage identifiés par les lettres ED et deux additionneurs complets AC1 et AC3. Les registres à décalage sont les suivants : 71 26328 7 2099446 KDA contient a n REB contient b n RDF contient yn REK contient K n RDx contient x A l'origine, a^, et sont appliqués aux registres appropriés à partir d'une mémoire permanente 9 et la valeur donnée de x est introduite dans RDx. AÇ3 ajoute a et b pour donner a 4- b . AC1 additionne K à la n n nn n sortie de AC3 de façon à donner yn qui est transféré dans RDF. yn est égale-10 ment recyclé, avec un décalage de un bit qui divise yn par deux, de façon à remplacer aR ou bn suivant la direction montante ou descendante nécessitée par la valeur de x. Pour ce faire, le bit le plus significatif de REbc est détecté par un circuit 10 pour déterminer si c'est un 0 ou un 1. Si ce bit est un 0, deux 15 portes lia sont rendues passantes par le signal de sortie d'un inverseur 10a de façon que y^/2 remplace bR et que a^ soit simplement recyclé. Par contre si ce bit est un 1, deux portes 11b sont rendues passantes de façon que yn/2 remplace a^ pendant que bn est recyclé. Après chaque cycle, RDx est décalé d'un pas vers la gauche de façon 20 à éliminer le bit le plus significatif et à amener le bit suivant dans cette position, pour le cycle suivant. Dès que tous les digits de x sont des 0, un circuit 13 arrête le fonctionnement du système permettant de lire jr à partir de RDF. Dans ce mode de réalisation, l'algorithme est mis en oeuvre unique-25 ment grâce à des registres à décalage et à des additionneurs. Une telle réalisation est possible du fait que l'algorithme ne comporte que des additions et des divisions par des puissances de deux, cet algorithme pouvant être par conséquent appelé algorithme "addition-décalage". L'invention n'est toutefois pas limitée à tin mode de réalisation particulier. 30 Introduction de termes d'ordre plus élevé Avant de considérer la série de polynomes binaires on va tout d'abord considérer le problème de l'interpolation de y = sin 0 sur un intervalle 0 à 90°, c'est-à-dire dans lequel x = 1 correspond à © = 9&°, x = l/2 correspond à 6 = 45° et ainsi de suite. Sur la figure 5» sin © est repH^enté par la 35 courbe 110. L'algorithme d'interpolation linéaire avec & --- 0 &;b = l donne la 71 26328 8 2099446 ligne 111 qui soustraite de la courbe 110 laisse une courbe de correction résiduelle 112 voisine d'une parabole 113 représentée en pointillés. Comme sin 45° = 0,70711, le terme parabolique de l'algorithme donne la parabole 113 si est égal à 0,20711. La différence est alors une nouvelle courbe de cor-5 rection résiduelle qui pour plus de clarté est représentée sur la figure 6 avec une échelle des y dilatée. En plus de cette courbe 114-, dont la forme est voisine de celle d'une courbe du troisième degré, on a tracé en pointillés une courbe du troisième degré 115 correspondant à l'équation 0(64/3) x(l - x) (x - 1/2) qui s'annule 10 pour x = 0, l/2 et 1 et dont le coefficient C est choisi de façon à approcher le plus possible de la courbe 114. Pour obtenir ce résultat, on s'arrange pour que les corrections résiduelles pour x = l/4 et x = 3/4 soient de même valeur et de signe opposé. La nouvelle courbe de correction résiduelle est la courbe 116 dont la forme est approximativement celle d'une courbe du quatrième 15 degré. Une approximation de cette courbe 116 peut être obtenue par un terme 2 0,(256/3) x(l - x) (x - 1/2) dans lequel Q est choisi de façon à obtenir avec la courbe 116 deux points confondus d'abscisses respectives x = 1/4 et x = 3/4- Dans cet exemple Q est en fait un coefficient négatif. On constate que la correction résiduelle, et notamment la correction 20 résiduelle la plus grande possible sur tout l'intervalle, convergé rapidement vers zéro (voir la différence d'échelle des entre la figure 5 et la figure 6). On se rend compte par conséquent que la série polynomiale dont les termes viennent d'être donnés jusqu'auquatrième degré, constitue une excellente approximation des fonctions. De plus, les termes jusqu'au deuxième degré 25 peuvent être interpolés exactement au moyen d'un algorithme simple. Cette propriété est également vraie pour les termes d'ordre plus élevé bien qu'il apparaisse des facteurs additionnels plus complexes. C'est ainsi que l'algorithme d'ordre trois nécessite simplement l'addition d'un terme Cn = (Cn ^)/8 que l'on introduit pour la première fois lorsque h = 2, mais qui, du fait de 30 la double polarité de la courbe, doit être additionné dans le cas d'une interpolation montante et soustrait dans le cas d'une interpolation descendante. p. d! Ce terme peut être représenté par le symbole + M C . n La figure 7 représente un mode de réalisation permettant de mettre en oeuvre l'algorithme du troisième degré, ce mode de réalisation découlant de 35 celui de la figure 4. Le registre à décalage RDC contient C et un additionneur n complet supplémentaire AC2 combine Cn à Kn pour donner 1!Kn qui est ajouté à 71 26328 9 2099446 + b^. Le signal de sortie du circuit 10 (constitué par une bascule bistable) a maintenant la double fonction de commander AC2 de façon à additionner C n quand le bit de x est 1 et de soustraire C^ lorsque ce bit est 0. L'algorithme d'ordre quatre introduit un terme duquatrièrae degré 5 = (Q^ j)/l6 nais C^ doit être remplacé par TC^ => + + M 8q^, le _n-l choix du signe dépendant alors du sens montant ou descendant selon lequel a été effectué l'étape précédente (n - l). Cette particularité sera expliquée plus en détail par la suite. Pour décrire un exemple des fonctions de coœnande, on Ta supposer 10 que le calcul est effectué avec une précision de 16 digits et que EDA, REB, HGK et RDC ont une capacité de 20 bits pour tenir compte des calculs arrondis. RDx et RDF ont une capacité de 16 bits. Le fonctionnement est commandé par une horloge 160 (figure 7a) reliée à un compteur en anneau l6l comportant 23 étages par l'Intermédiaire d'une porte 162 rendue passante lorsqu'une bascule 163 est 15 à l'état actif. Une porte OU 164 reliée aux vingt premiers étages du compteur, donne des groupes de vingt Impulsions de décalage pour chaque groupe de vingt-trois impulsions traversant la porte 162. Les signaux de sortie de la porte OU 164 sont appliqués à la borne de commande de décalage RDF et aussi, par l'intermédiaire de portes OU 165 et 166, aux bornes de commande de décalage 20 de kda. et HCB. L'un de ces deux registres reçoit de plus la vingt et unième impulsion par l'intermédiaire d'une porte ET 167 ou 168. Si le bit de x est un 1 et si le recyclage de RDB est autorisé, yn doit être introduit dans RD& avec tin décalage réalisant une division par 2. Pour ce faire, le signal provenant du circuit 10 (figure 7) valide la porte 167 et la 21 impulsion peut passer 25 vers la porte OU 165 et, de là, à RDft.. Inversement, lorsque le bit de x est un 0, le signal de la ligne 170 provenant de l'inverseur 10a valide la porte ET 168. j V Tnf ■ Lorsque la 21 impulsion de REA (ou REB) apparaît, il faut éviter qu'un bit soit introduit au niveau le plus significatif de RM (ou REB). Pour 30 ce faire, une porte EE 171 placée dans la boucle de recyclage de y est irihi- j Xrnfk ^ bée grâce à un inverseur 172 lors de l'apparition de la 21 impulsion. Cosne REK doit effectuer une division par 4, il reçoit à la fois les 21i^me et 22i^B>e impulsions de décalage par l'intermédiaire des portes OU 173 et 174 en plus de la 20ièffle impulsion. Pendant l'apparition des 21iemeet 22ièœe impulsions, 35 une porte ET 175, plaeée dans la boucle de recyclage de TKn, est inhibée grâce à un inverseur 176. RDC doit effectuer une division par 8 et reçoit par conséquent, les 21i^Me, 22^™® et 2J^me impulsions par l'intermédiaire de portes 71 26328 2099446 OU 177 et 178 de même que la 20 impulsion par 1'intermédiaire de la porte 164. Pendant l'apparition des 21*®106, 22'*'®!ne et 23*®me impulsions, une porte ET 179* placée dans la boucle de recyclage de CQ est inhibée grâce à un inverseur 180. 5 La 23 impulsion de chaque groupe décale RDx d'un bit dans la direction inverse, de façon à amener le bit suivant de x en position de cowwn-de. Lorsque tous les digits de x qui restent dans HQx sont des 0, le circuit 13 donne un signal d'arrêt. Ce signal remet à l'état passif la bascule 165 de façon à bloquer la porte 162 et à arrêter le fonctionnement du système, lais-10 sant ainsi la valeur de jr dans UDF. Comme KQx comporte 16 bits, un cycle complet d'itérations nécessite 16 x 23 = 368 impulsions d'horloge. Coopte tenu du fait qu'il faut 100 périodes d'horloge pour introduire x, a, b, K et C, le temps total de calcul sera de 46,8 ^usec avec une horloge de fréquence 10 ïflz. A titre de oomparàison, le 15 système à bits parallèles, mots série de la figure 14 décrit par la suite nécessite 88 périodes d'horloge c'est-à-dire 8,8jpsec pour la mène précision et la même fréquence d'horloge. Le mode de réalisation série/série de la figure 15 nécessite 1560 périodes d'horloge soit 156 jisec. Les polynômes binaires 20 On va maintenant définir les polynômes binaires jusqu'au terme du huitième degré et expliquer leurs propriétés. Lorsqu'on utilise une approximation polynomiale de y » f (x), sur tin intervalle donné de x, on a coutume de normaliser le problème à un intervalle de x compris soit entre -1 et +1, soit entre 0 et 1. Les familles de polynômes binaires seront définies pour ces deux 25 intervalles, le polynôme d'ordre n étant désigné par le symbole : Bn pour l'intervalle de -1 à +1 B * pour l'intervalle de 0 à 1. n Quel que soit l'intervalle, la forme graphique des polynômes binaires ne change pas, chaque changement d'échelle de x ayant toutefois pour résultat 30 de faire varier l'expression des polynômes. A titre d'exemple, on va décrire l'intervalle de x compris entre 0 et 1. Le processus d'interpolation déjà décrit fait passer successivement : 1°) à la valeur moitié de x 2e) aux multiples impairs du quart de x 35 3e) aux multiples impairs du huitième de x et ainsi de suite par bissections répétées de façon à obtenir une 71 26328 11 2099446 succession binaire de points. Les polynômes binaires ont pour propriété, si l'on sélectionne des valeurs correctes pour les coefficients K^, C^, etc..., d'avoir autant de points confondus avec la fonction étudiée qu'il est possible d'en obtenirjcompte tenu du degré du polynôme utilisé Si l'on considère l'approximation : y S0B0 + S1B1 + s2B2 + S3B3 dans laquelle les termes gR sont les coefficients et les polynômes binaires (x varie de 0 à l), les polynômes nécessaires pour obtenir les points confondus suivants sont : 10 Points confondus Polynômes nécessaires x = 0 et 1 g0B0* et g^* 1/2 *2B2* x = 1/4 et 3/4 zf-Ç + g4B4* x - 3/8 et 5/8 g^* + ggBg* 15 x = 2/8 et 7/3 + ggBg* La règle fondamentale est que, si l'on obtient un certain nombre de points confondus, les polynômes suivants ne doivent pas modifier ces points confondus. Par exemple, à la suite d'une approximation du deuxième degré trois points confondus sont obtenus pour x = 0, 1/2 et 1. Le polynôme cubique B^* 20 et tous les autres polynômes suivants doivent par conséquent contenir l'expression x(l - x) (x - l/2). Le polynôme du quatrième degré doit donc contenir l'expression x(l - x) (x - l/2). Comme B^* est du quatrième degré, l'expression complète est obtenue en répétant le facteur (x - l/2). B^* contient donc : 2 25 x(l - x) (x - l/2) ; g^ et g^ sont choisis de façon à donner des points confondus pour x = 1/4 et x = 3/4. Les termes du cinquième et du sixième degré B* et Bg doivent comprendre (x - l/4) et (x - 3/4) de façon à présenter des zéros x = l/4 et x = 3/4, g_ et g,- étant choisis pour donner des points confondus jfc pour x = 3/8 et x = 5/8. Les termes du septième et du huitième degré B_ et 30 Bg doivent comprendre (x - 3/8) et (x - 5/8) > Sj et gg étant choisis pour donner des points confondus pour x = l/8 et x = 7/8- Ces définitions ne sont évidemment pas les seules possibles. Par exemple g,_ et g^ pourraient donner des * 5^6 points confondus pour x = 1/8 et x = 7/8 et et Bg comprendraient alors (x - 1/8) et (x - 7/8). De même, les zéros pour x = l/-. st x ~ 3/4 pourraient 35 être répétés dans By* et Bg*. Dans ce cas, quatre équatiors sirssltanées doivent 71 26328 12 2099446 être résolues pour obtenir g^, gg, et gg de façon que les points confondus correspondent aux abscisses x = 1/8, 3/8, 5/8 et 7/8. Les mêmes remarques s'appliquent aux polynômes de l'autre type. Chaque polynôme binaire comprend les facteurs dépendant de x décrits 5 précédemment, multipliés par un facteur de normalisation. A première vue, ces facteurs de normalisation semblent redondants du fait qu'ils pourraient être incorporés dans les coefficients. Toutefois, ils ont une valeur pratique significative car ils indiquent l'erreur due à la troncature de la série. En effet le (ou les deux) coefficients qui suivent immédiatement le dernier terme consi-10 déré de la série polynomiale indique de façon directe l'erreur d'approximation, quel que soit le degré du dernier terme considéré de la série. Ces facteurs de normalisation ont été établis sur le principe que la valeur de pic de chaque polynôme est égale à l'unité, ou aussi proche de l'unité qu'il est possible de l'obtenir au moyen d'algorithmes du type addition-15 décalage. La condition "addition-décalage? quel que soit le polynôme, et du fait de l'interpolation pour des valeurs binaires de x, est de la forme : nombre entier nombre binaire une valeur 7/8 étant par exemple acceptable alors que 8/7 ne l'est pas. Il est intéressant de remarquer que les facteurs de normalisation 20 peuvent être choisis de façon que l'intégrale de chaque polynôme pair soit égale à l'unité. L'intégrale de tous les polynômes impairs étant égale à zéro, l'intégrale de la fonction approchée serait alors la sonane des coefficients des termes pairs. Les tableaux suivants donnent les polynômes binaires jusqu'au huitième 25 degré, le tableau I donnant les polynômes B* et le tableau II les polynômes B. 71 26328 » 2099446 TABLEAU I Polraowes binaires poor l'intervalle 0 à 1 Degré du polynôme PolynSme B Linéaire Deuxième degré Troisième degré Quatrième degré Cinqelèae degré Slxiè«e degré Septième degré B, B. ■n 1 2x - 1 B« - 4x(l-x) Bj* =. (64/5)x(l-x) (x-l/2) B* = (256/3 )x(l-x) (x-V2)2 • b5* « (2I2/15)x(1-x) (x-1/2) (x-l/4) (x-3/4) bg* = (215A5)x(1-x) (x-1/2)2(x-1/4) (x-3/4) by* - (217/105)x(1-x) (x-1/2) (x-1/4) (x-3A) ... ... (x-3/8)(x-5/8) ,19 Symbole du coefficient gQ = (b + a) Ex = (b - a) gg = K «5 = ° g^ — I g6 = s *7 = * Huitième degré Bg* « (219/l05)x(l-x)(x-3/2)2(x-lA)(x-3/4) ...gg - E ... (x-3/8)(x-5/8) 71 26328 « 2099446 TABLEAU II Polynômes binaires pour l'interyalle -1 à +1 Degré du polynôme Polynôme B n Linéaire Deuxième degré Troisième degré Quatrième degré Cinquième degré Sixième degré Septième degré Huitième degré B0 = 1 B2 = (l+x)(l-x) = (8/3)X(1+X)(1-X) » (l6/5)x2(l+x)(l-x) 85 = (2^/l5)x(l+x) (l-x) (x+l/2) (x-l/2) Bg - (29A5)x2(1+x) (l-x) (x+l/2) (x-1/2) By = (210/l05)x(l+x) (l-x) (x+l/2) (x-1/2).. ... (x+lAKx-lA) Bq - (2n/l05)x2(l+x)(l-x)(x+l/2)(x-1/2). ... (x+l/4)(x-lA) Symbole du coefficient gQ = (b + a) g-L « (b - a) gj - C 84 -«5 - 1 «6 " S S? = P «8 E 71 26328 15 — 7 2099446 Les polynômes Bn sont représentés depuis le deuxième jusqu'au huitième degré sur les figures 8A à 8G- Cette forme graphique s'applique aussi aux polynômes pourvu que 11 intervalle (-1, +l) soit remplacé par un intervalle (0, l) c'est-à-dire que -1 devienne 0, -0,5 devienne 0,25, 0 devienne 5 0,5 et ainsi de suite. L'exemple de sin 6 déjà décrit en référence aux figures 5 et 6 montre comment les polynômes binaires peuvent être utilisés pour approcher ■une fonction donnée. Des informations complémentaires seront données par la suite sur la façon de déterminer les coefficients K, C, Q, etc. 10 Algorithmes des polynômes binaires Les algorithmes du premier au quatrième degré ont déjà été expliqués avec plus ou moins de détails. Les algorithmes allant jusqu'au huitième degré vont maintenant être présentés au moyen d'organigrammes dont les blocs représentent des quantités telles que an> b^, Kfl, ou les opérations aboutissant 15 à la détermination de y . Les conditions initiales se présentent sous forme d'un tableau. Les boucles de recyclage ne sont pas représentées mais chaque bloc contient une équation indiquant la nature de ce recyclage. La figure 9 représente l'algorithme du deuxième degré selon cette représentation, cette figure 9 étant par conséquent équivalente à la figure 4. 20 La figure 10 représente tin algorithme du troisième degré et correspond à la figure 7' Pour les algorithmes de degré supérieur à deux il est parfois préférable de traiter les termes pairs et impairs comme étant obtenus par des voies parallèles séparées représentées respectivement à droite et à gauche des orga- nigraianes. De plus, la correction résiduelle d'un terme K , C , etc... est n n 25 désignée par RK , RC , etc..., la somme K + RK étant égale à TK , la somme n n n n n C + RC étant égale à TC et ainsi de suite. n n ° n Pour mieux faire comprendre les organigrammes, on va maintenant expliquer plus en détail la correspondance entre les figures 10 et 7> L'équation située à l'intérieur du bloc 120 (figure 10) est réali-30 sée par la boucle "Recyclage et Division par huit" du registre RDC de la figure 7' —u Cn (figure 10) est effectuée par les signaux de L'opération -D +M In J commande "Addition" et "Soustraction" de l'additionneur complet AC2 de la figure 7' 35 L'équation du bloc 121 (figure 10) est réalisée par la boucle "Recyclage et Division par quatre" du registre RDK de la figure 7- 71 26328 16 2099446 Les équations des blocs 122 et 123 sont réalisées par les portes lia et 11b commandées par le circuit 10 de la figure 7* L'opération d'addition du bloc 124 (figure 10) est effectuée par l'additionneur complet AC2 de la figure 7-5 Les opérations d'addition des blocs 125 et 126 (figure 10) sont effectuées par les additionneurs complets AC1 et ACJ de la figure 71 l'ordre des additions étant différent dans les deux figures. Les figures 11, 12 et 13 représentent les algorithmes d'ordre quatre, six et huit respectivement. La mise en oeuvre de ces algorithmes est évidente 10 par analogie avec les modes de réalisation des figures 4 et J. Toutefois, comme le symbole +$ apparaît, il est évidemment nécessaire de séparer le bit de RDx qui était le plus significatif dans le cycle (n-l) et de l'utiliser dans le cycle n pour commander l'addition ou la soustraction. En outre, il faut d'une part prévoir pour un registre ayant me boucle de recyclage et 15 de division par 16 et d'autre part introduire le tenue 8Q = (Q, , )/2 par n n-1 exemple au moyen d'un registre tampon. De cette façon, lorsque ^ est décalé de quatre bits dans le registre Qn de façon à diviser par seize et obtenir ainsi Qn ^ est simultanément décalé de un bit dans le registre tampon de façon à diviser par deux et obtenir ainsi 8Q . n 20 Autres algorithmes A partir de l'algorithme du quatrième degré, de nombreuses variantes peuvent être conçues tout en restant dans le cadre de l'invention. Les formes données sur les figures 11 à 13 sont, semble-t-il, les plus efficaces. On perd un peu d'efficacité en choisissant une forme d'algorithme dans laquelle 25 les termes pairs et impairs sont traités séquentiellement plutôt que parallèlement. La figure lia représente un exemple d'une telle variante dans laquelle une partie de la figure 11 est modifiée pour obtenir RK^j le reste de l'algorithme est le même. . Dans les algorithmes décrits jusqu'à présent, il n'y a pas de chan-30 çement de logique, c'est-à-dire qu'après obtention d'un terme logique tel que ^ TCn pour n = 2, ce terme est utilisé sans changement pour toutes les étapes suivantes. De plus, chaque donnée initiale telle que K, C, etc ... est introduite une fois pour toutes. On peut toutefois concevoir des algorithmes dans lesquels des changements de logique se produisent et/ou dans lesquels 35 des coefficients sont réintroduits par la suite. Ces variantes sont moins efficaces que les exemples que l'on vient de donner (mais restent toutefois dans le cadre de l'invention). +M 71 26328 17 2099446 Algorithmes du cinquième au huitième degré La figure 12 représente une forme préférée d'algorithme du sixième degré, l'algorithme du cinquième degré étant le même mais tronqué par omission du terme du sixième degré. En fait la figure 12 représente tous les algorithmes 5 de degré inférieur ou égal à six du fait que les algorithmes des figures 9» 10 et 11 peuvent être obtenus en tronquant la série au-dessus du terme de degré deux, trois ou quatre respectivement. La figure 13 représente une forme préférée d'algorithme du huitième degré que l'on peut tronquer pour obtenir 11algorithme du septième degré si on 10 le désire. L'algorithme de la figure 13 tronqué au-dessus du sixième degré constituerait un algorithme possible du sixième degré quoique différent et moins efficace que celui de la figure 12. ■ Les deux premiers termes de l'algorithme sont représentés sur la figure 13 différemment des figures précédentes. Sur les figures 9 à 12 et 15 bn sont toujours les valeurs de j à l'extrémité respectivement inférieure et supérieure du segment d'interpolation. Si l'on adopte la convention selon laquelle aQ est toujours la valeur qui ne change pas tandis que bQ est celle qui est remplacée par une nouvelle valeur, à savoir yn ^/2, on obtient l'organigramme de la figure 13. 20 L'avantage d'un tel algorithme est d'obtenir une suite de registres entièrement ordonnée depuis le degré zéro jusqu'au huitième degré, chaque registre ayant son contenu divisé par 2B, m étant le numéro d'ordre du registre. On a ainsi un registre diviseur par 1(degré 0),un registre diviseur par 2 (premier degré) et ainsi de suite jusqu'au registre diviseur par 256 25 (huitième degré). Mise en oeuvre des algorithmes Les figures 4 et 7 représentent des mises en oeuvre avec une numération bits-série, mots parallèles, 1'invention pouvant évidemment utiliser n'importe quelle forme de numération. Bien qu'il soit difficile d'éearter les bases 30 binaires des algorithmes, on peut envisager, en théorie tout au moins, des opérations arithmétiques effectuées dans un système de numération non binaire. En pratique, seule l'arithmétique binaire ou binaire-décimale est intéressante et l'on peut alors trouver quatre possibilités de base. 71 26328 is 2099446 1. Fonctionnement bits parallèles-mots parallèles. Cette technique donnerait des interpolations pratiquement instantanées mais nécessite une avance technique relativement importante avant de pouvoir être considérée comme une possibilité pratique. De ce fait, ce mode de fonctionnement ne sera 5 pas exposé plus en détail. 2. Bits parallèles-mots série, fonctionnement à grande vitesse. 3- Bits-série-mots parallèles, fonctionnement à moyenne vitesse. 4. Bits-série-mots série, fonctionnement à vitesse faible. Ces quatre possibilités de base peuvent être combinées si on le désire. 10 A titre d'exemple, et par comparaison avec l'approche bits série- mots parallèles de la figure J, les figures 14 et 15 représentent des circuits permettant de mettre en oeuvre l'algorithme cubique avec des numérations respectives bits parallèles, mots série d'une part et bits série, mots série d'autre part. 15 Sur la figure 14, les informations sont transmises sur trois voies parallèles Hl, H2 et H5« Les voies H1 et H2 sont reliées aux deux entrées d'un additionneur parallèle 130 comportant quatre sorties J1 à J4 conandées par des portes. J1 et J2 sont reliées aux voies Hl et H2 respectivement. J3 donne un signal proportionnel à la demi-somme appliqué à la voie alors que J4 est 20 utilisée pour la lecture de y^. La voie H3 est reliée aux entrées parallèles des registres 131 à 134 donnant respectivement aQ, bQ, et CQ. Cette voie H5 est également utilisée pour introduire les valeurs initiales provenant d'une mémoire permanente 135- Les sorties b^ et sont appliquées à Hl alors que les sorties a et C sont appliquées à H2. n n 25 Les différentes portes représentées sur la figure sont commandées par un circuit de cadenceaent (non représenté) qui donne la séquence des opérations décrite par la suite. Les registres Kn et C^, 133 et 134, sont des registres à décalage (à entrées parallèles) qui effectuent les divisions nécessaires. Le registre CQ 134 comporte un circuit associé permettant d'introduire 30 au choix + C^ conformément à l'algorithme. En supposant que toutes les entrées initiales ont été effectuées, un cycle d'interpolation s'effectue comme suit, par exemple pour n = 3. ajoute C ou -C sur H2 à K sur Hl pour donner TK sur Jl-n n n n ajoute TK sur Hl à a sur H2, la souae étant obtenue sur J2 . n n ajoute (TKn + a^) sur H2 à bn sur Hl pour obtenir 7^/2 sur et on recycle y /2 vers a ou b . n n n décale Kn de deux bits et Cq de trois bits pour obtenir 35 (1) On (2) On (3) On J3 (4) On et 71 26328 2099446 Si n est le dernier cycle, le point (3) est modifié de façon à obtenir yn sur J4 et le point (4) est alors supprimé. La figure 15 représente la mise en oeuvre de l'algorithme cubique avec une numération bits série, mots série, dans laquelle on utilise la tech-5 nique bien connue consistant à mettre en mémoire toutes les quantités dans un registre à décalage unique 140 qui comprend donc, dans ce cas, les registres bn, an, Kn et Cn« La sortie du registre 140 "est reliée à line entrée d'un additionneur complet l4l dont la sortie est reliée à un registre tampon 142 lui même connecté à l'autre entrée de l'additionneur. Cet additionneur est commandé 10 de façon à ajouter ou soustraire de la même façon que l'additionneur complet AC2 de la figure Y' Deux boucles de recyclage sont réalisées par l'intermédiaire de la logique de recyclage et de division 143. La première boucle 144 permet de recycler des quantités sans changement. La deuxième boucle 145 provenant de 15 la sortie de l'additionneur l4l permet de recycler C , -TK et y , ce dernier n n n (divisé par deux) remplaçant a^ ou bn suivant le sens montant ou descendant de l'interpolation. La logique 143 divise y^ par deux, Kn par quatre et C^ par huit en supprimant suivant les cas les 1, 2 ou 3 premiers bits de la quantité recyclée. Cette logique applique aussi 1, 2 ou 3 impulsions de décalage 20 au premier quart (à partir de l'extrémité gauche) du registre à décalage 140 de façon à amener le premier bit non éliminé dans la position la moins significative du registre qui reçoit la quantité recyclée. La logique 143 commande également l'introduction des quantités initiales à partir de la mémoire permanente 146. 25 Un cycle d'interpolation comprend les étapes, suivantes : (l) Transférer Cn dans le registre tampon 142 par l'intermédiaire de l'additionneur l4l et réintroduire simultanément dans le registre 140 par l'intermédiaire de la logique 143 qui effectue line division par huit donnant C , = C /S. . -n+1 n • 30 (2) Transférer Kn de 140 et Cn de 142 dans l'additionneur commandé de façon à ajouter ou soustraire selon la règle C*?] pour donner TK^. Introduire TK simultanément dans 1^2 et dans 140 eii effectuant la division Dar n * quatre sur 1'entrée 140 pour obtenir = TK^/4. (3) Transférer a^ de 140 et ÏK^ de 142 dans l'additionneur pour 35 obtenir (an + ®n) introduit dans 142. copvJ 71 26328 20 2099441 (4) Transférer b de 140 et (a + TK ) de 142 dans l'additionneur n n n pour obtenir y . Si l'interpolation est descendante, introduire simultanément yn par la boucle 145 pour remplacer bn, et effectuer une division par deux pour obtenir b , = y /2, a n'étant pas modifié pour donner a „ = a . Si n+1 n n n+1 n 5 l'interpolation est montante, introduire y^ dans 142 et recycler bn par l'intermédiaire de la boucle 144 pour donner b , = b puis continuer avec le n+1 n point (5)' (5) (Interpolation montante seulement) Recycler Cn+^ et sans changement par la boucle 144. Extraire aR de 140 et transférer simultanément 10 y^ de 142 par l'intermédiaire de l'additionneur et de la boucle 145 de façon à remplacer a et effectuer une division par deux pour obtenir a ,= y /2. n n+1 h recycler b sans changement par l'intermédiaire de la boucle 144. n-ri Les portes nécessaires pour effectuer les transferts d'information indiqués ci-dessus ne sont pas décrites car il est bien connu d'effectuer de 15 telles commandes connaissant la séquence des opérations. Pour le spécialiste en effet, il suffit de spécifier ces opérations simples pour connaître les moyens de mise en oeuvre nécessaires. Dans le même ordre d'idée, les spécialistes peuvent se rendre compte que le mode de réalisation bits série, mots série s'adapte particulièrement 20 bien aux techniques de circuits intégrés MSI ou LSI. Un générateur de fonction extrêmement précis et versatile peut être fabriqué économiquement dans le cadre de ces techniques sur la base de la présente invention. Signes et autres considérations Pour simplifier l'exposé on a, jusqu'à présent, traité les signes 25 d'un point de vue purement mathématique (mis à part le circuit associé au registre 134 mentionné en référence à la figure 14). En pratique il faut adopter l'une des techniques connues permettant de traiter les signes. La technique la plus souhaitable est de faire précéder chaque nombre par un bit de signe et d'utiliser le complément à 2 pour les nombres négatifs. 30 Dans ce cas, lorsqu'une division est effectuée par décalage, la logique doit remplacer le bit le moins significatif qui a été écarté, par un bit équivalent au niveau le plus significatif, plus précisément un bit 0 pour un nombre positif et un bit 1 pour un nombre négatif. Par suite du grand nombre d'itérations utilisées, il est nécessaire 35 de prendre quelques précautions pour tenir compte des erreurs d'approximation. Une solution simple est d'utiliser des registres ayant un nombre de bits surabondant. Pour obtenir une précision de 24 bits, il suffit que le registre ait 71 26328 2099446 une capacité de quatre bits supplémentaires. Les valeurs initiales de a, b, et K, etc... doivent être données avec un bit en excès par rapport à la précision recherchée. Génération de fonctions multiples 5 Bien que l'on ait seulement décrit en entier la fonction sin 0, on peut utiliser les polynômes binaires pour 1'approximation d'un grand nombre de fonctions telles que les fonctions circulaires, hyperboliques, exponentielle^ la racine carrée, le logg et le cologg. Pour chaque fonction il est nécessaire de spécifier l'intervalle de variation approprié de la variable indépendante 10 et les coefficients a, b, K, C, etc... SI l'on utilise par exemple l'algorithme du quatrième degré, chaque fonction est complètement définie par cinq mots, les Mêmes-circuits pouvant être utilisés pour engendrer n'importe quelle fonction pourvu qu'une mémoire permanente de faible capacité permette d'emmagasiner les coefficients des différentes fonctions. Des adresses permettront de choisir 15 les coefficients corrects ainsi que la valeur donnée de la variable indépendante. Perfectionnement pour une meilleure précision Pour améliorer la précision de l'interpolation, le moyen le plus efficace est de passer à un algorithme de degré plus élevé. Toutefois, si l'on 20 doit élaborer un ensemble de fonctions au moyen des mêmes circuits, me (ou plusieurs) de ces fonctions est très souvent plus difficile à obtenir que les autres. La possibilité de passer à un algorithme de degré plus élevé, seulement pour quelques fonctions, peut ne pas être justifiée. On divise alors ces fonctions en un certain nombre de zones ayant leurs propres données initiales a, 25 b, K, C, eto... A titre d'exemple, il est préférable, pour obtenir la racine carrée, de diviser cette fonction en intervalles allant de 0,5 à 1 et de 0,25 à 0,5- Bien que les algorithmes d'ordre élevé puissent donner de bonnes approximations de fonctions périodiques, comme par exemple sin 6 sur l8o° ou 30 même sur 360°, 11 peut être préférable de faire l'interpolation seulement sur 90e et d'utiliser une logique donnant les inverses et les compléments pour obtenir les quatre cadrans. 71 26328 20994'*5 Un autre moyen pour améliorer la précision est de ne pas se .ier exclusivement aux termes calculés (après l'introduction des valeurs initiales) mais d'ajouter des termes correctifs comme SK ou SC, au moins pour les premières valeurs de n. Cette technique n'est pas forcément préférable du fait que les 5 termes correctifs doivent être gardés en. mémoire et sont en général différents pour chaque segment de la courbe- La quantité d'informations mise en mémoire est toutefois encore très faible par comparaison aux méthodes connues- La même précision peut être cependant obtenue plus efficacement en passant à un algorithme de degré plus élevé. 10 Opération inverse La nature des algorithmes est telle qu'ils peuvent fonctionner dans le mode inverse c'est-à-dire qu'on peut déterminer x connaissant j. La Méthode . utilisée est tin procédé par approximations successives similaire à celui employé dans les convertisseurs analogiques-numériques. 15 Dans le mode direct, les digits du registre x commandent le sens montant ou descendant de l'algorithme pour chaque étape. Dans le mode inverse, il est nécessaire de déterminer par comparaison si le sens doit être nontant ou descendant et de remplir le registre de x en conséquence. En se reportant à l'exemple de sin 0 on va considérer le cas spéci-20 fique de arc sin 0,800 ... La première étape de l'algorithme amène à sin 45* « 0,7071 ... La comparaison avec 0,800 ... montre que le résultat est trop bas et que l'algorithme doit être montant dans l'étape suivante. Le premier bit de x est ainsi un 1. L'essai suivant sera sin 67,5° = 0,9238 ... Ce résultat est trop élevé, la prochaine étape doit être descendante et un zéro doit être 25 introduit dans le registre x et ainsi de suite. Si la fonction mise en mémoire est monotone il n'y a qu'une solution mais il faut mettre en mémoire la polarité de la pente. Dans le cas où la fonction n'est pas monotone, deux ou plusieurs solutions peuvent exister. Les premières étapes de l'algorithme sont alors commandées de façon que la solution 30 désirée soit obtenue. Ce principe est illustré sur la figure 16 des dessins. Le bloc 150 qui contient le mot "Algorithme" comprend les registres a, b, K, etc..i et les circuits associés, y compris la mémoire permanente pour introduire les valeurs initiales. Les registres 151 et 152 de x et y^ sont représentés séparément et 35 un registre "inverse" N 153 contient la valeur donnée de j- Un comparateur 154 indique si yQ est trop haut, trop bas ou exact par rapport à jr. La logique 155 /.l £03x0 25 2099446 associe "trop haut" à "Descendant" et "trop bas" à "montant" si la pente de la fonction est positive, cette correspondance étant inversée si la pente est négative. Fonctions de deux ou plusieurs variables 5 Une fonction de deux ou plusieurs variables peut être définie par des polynômes binaires et interpolée en répétant le même algorithme tout en utilisant à chaque fois les mêmes circuits. On va considérer un exemple simple dans lequel une surface courbe est définie par sa distance z_ à partir du plan x, cette surface étant du 10 deuxième degré. On désire obtenir z connaissant les coordonnées x et Pour une valeur particulière jr' de £, z_ est donné en fonction de x par des coefficients a', b' et K'. Etant donné les trois coefficients ci-dessus, £ peut être obtenu pour n'importe quelle valeur de x par une seule interpolation de l'algorithme. 15 Chacun de ces trois coefficients est ensuite déterminé en fonction de £ par trois coefficients mis en mémoire. a est déterminé par a , b., K 3. ci a. b est déterminé par a^, b^, K est déterminé par a^., bj., 20 Pour une valeur donnée de jr trois cycles d'interpolation sont donc nécessaires pour établir les trois coefficients du cycle final. Dans le cas de deux variables indépendantes, l'algorithme du deuxiène degré nécessite neuf mots à mettre en mémoire et quatre cycles d'interpolation, l'algorithme du troisième degré nécessite 16 mots à mettre en mémoire et cinq 25 cycles d'interpolation et ainsi de suite. Pour trois variables indépendantes, l'algorithme du deuxième degré nécessite 27 mots mis en mémoire et 13 cycles d'interpolation, l'algorithme du troisième degré nécessitant 64 mots mis en mémoire et 21 cycles d'interpolation. Détermination des coefficients naturels 30 Les coefficients naturels K, C, Q, ete •.. des polynômes binaires sont définis comme ceux qui donnent une superposition exacte pour la séquence binaire de valeurs de x, ces coefficients pouvant être obtenus par d^s procédés algébriques simples. Cette propriété est un avantage trèa important des polynômes binaires que ne possède aucun des polyncmes de Chebysnev généralement 71 26328 24 2099446 utilisés pour l'approximation des fonctions. Les polynômes de Chebyshev sont orthogonaux et demandent des calculs complexes de multiplication et d'intégration pour obtenir les coefficients. Les polynômes binaires ne sont pas orthogonaux et la détermination des coefficients est purement algébrique. 5 En référence à la figure 17, on a représenté la longueur des diffé rentes ordonnées. On suppose que les valeurs de la fonction y(0), y(l/4) etc... sont connues, a et b sont obtenues immédiatement par £y(0Q /2 et Cy(l)3 /2-Ensuite, K peut être déterminé par l'expression y(l/2) - (a + b). Deux équations simultanées peuvent ensuite être choisies pour obtenir C et Q. 10 C + Q = y(3/4) - (3b/2 + a/2) - 3K/4 -C + Q = y(l/4) - (3a/2 + b/2) - 3K/4 En résolvant ces équations on obtient : 2C = y(3/4) - y(l/4) - b + a c'est-à-dire : C = [y(3/4) - y(l/4) + a - b] /2 15 et ?Q. = y(3/4) - y(l/4) - 2a - 2b - 6K/4 En remplaçant y(l/2) par a + b + K et en divisant par 2 il vient \ = [y(3/4) - y(l/4) + K/a] /2 - y(3/2) Ce processus peut être étendu systématiquement. Ainsi, on peut trouver deux équations simultanées pour I et S à partir de y(l/8) et y(3/8) et 20 deux autres équations pour P et E à partir de y(5/8) et y(7/8). Les circuits utilisés pour la mise en oeuvre de cet algorithme peuvent être utilisés pour déterminer les coefficients en interpolant pour les valeurs x - l/°; x = 1/4 et 3/4 et ainsi de suite et en déterminant les corrections résiduelles z définies comme suit : 25 z(l./2)=y(l/2)- (interpolation linéaire pour x = l/2) z(l/4) = y(l/4) - (interpolation du deuxième degré pour x = l/4) z(3/4) =* y(3/4) - (interpolation du deuxième degré pour x = 3/4) z(l/8) - y(l/8) - (interpolation du sixième degré pour x = 1/8) z(3/8) - y(3/8) - (interpolation du quatrième degré pour x = 3/8) 30 z(5/8) = y(5/8) - (interpolation du quatrième degré pour x = 5/8) z(7/8) = y(7/8) - (interpolation du sixième degré pour x = 7/8) Pour simplifier la notation on désignera z(l/8) par z^, z(l/4) par z2, z(3/8) par z^ et ainsi de suite. On peut ainsi montrer que : K = z4 35 C = (1/2) (zg - z?) Q = (3/2) [z6 + z2) 71 26328 « 2Q99446 I = (V3) (z^ - z5) S = -4(z^ + z,.) P = Zj - E = (2/5) (z? + Z;L) 5 Modification des coefficients naturels On peut concevoir de nombreuses méthodes pour modifier les coefficients naturels dans le but soit d'améliorer la précision de l'interpolation, soit de simplifier la détermination des coefficients* Cette dernière considération gui est de peu d'importance lorsqu'on utilise les coefficients pour l'éla-10 bor&tion classique de fonctions, est par contre importante dans le cas d'un processus temps réel au moyen d'un système de traitement d'information rapide. Dans ce dernier cas le système est adapté à déterminer les coefficients k intervalles réguliers à partir des échantillons de données et à effectuer les interpolations entre ces intervalles. 15 La précision de l'approximation polynomiale d'une fonction est généralement exprimée par la différence maximale entre 1'approximation et la fonction proprement dite sur tout l'intervalle intéressant. On a trouvé que les coefficients du cinquième et sixième degré donnés ci-dessous améliorent légèrement la précision lorsque les polynômes sont tronqués au niveau du 20 sixième degré, ces coefficients étant en outre beaucoup plus faciles à déterminer que les coefficients naturels : I' - I + (9/16) P s' = S + (9/8) E ou ïes relations plus complexes i 25 C' - C + P/l6 Q1 - Q - E/32 I' = I + 9P/I6 S' » S + 93/8 On a montré que ces dernières relations appliquées à cos © de 0 à 9# 30 donnent une différence maximale au pltis égale à 1,22 fois celle donnée par l'approximation polynomiale du sixième degré de Chebyshev (les polynômes de Chebyshev étant bien connus des mathématiciens comme les approximations polyno-miales les plus précises possibles). Même si l'on utilise l'approximation polynomiale binaire du sixième degré avec des coefficients naturels on obtient une 35 différence maximale qui ne dépasse pas 5»03 fois celle de Chebyshev. 71 26328 26 2099446 De plus, les polynômes binaires ont, sur les polynômes de Chebyshev, l'avantage de donner une superposition exacte aux extrémités de l'intervalle de variation de x. Extrapolation Pourvu que la fonction convienne, les algorithmes donnés ci-dessus peuvent être utilisés pour extrapoler à l'extérieur de l'intervalle normal de x. Si l'on prend l'intervalle normal de 0 à 1, et si l'on suppose que les coefficients naturels a, b, K, C et Q ont été déterminés précédemment, les coefficients a', b', K', C' et Q' pour un intervalle de x de zéro à deux par exemple seront les suivants : a' = a b' = 2b - a - 4K - 32C - 192Q. K' = 4K + 32C + 192Q C* - 8C + 64Q Q' - l6ft On remarquera que les circuits destinés à la vis* en oeuvre des algorithmes peuvent aussi être utilisés pour réaliser des opérations d'addition et de soustraction ou même de multiplication, et de division. Une multiplication de x et de j est équivalente à une interpolation linéaire avec À - 0, b = y/2, une division pouvant être obtenue comme l'Inverse d'une multiplication. Les mêmes circuits peuvent donc fonctionner à la fois comme générateur de fonctions et comme imité arithmétique. 71 26328 27 2099446 REVENDICATIONS 1. Dispositif pour interpoler une fonction d'une variable indépendante en effectuant des bissections répétées d'un intervalle de ladite variable caractérisé en ce qu'il comprend au moins un premier, un deuxième et un 5 troisième registre pour emmagasiner des quantités qui définissent la fonction, des moyens pour introduire dans chaque registre une combinaison linéaire des contenus d'un ou plusieurs desdits registres divisée par une puissance de deux, différente pour chacun desdits registres, ladite combinaison linéaire étant commandée sélectivement, pour au moins un desdits 10 registres, suivant les digits d'un mot binaire représentant la valeur donnée de la variable indépendante, les digits étant pris successivement, un par bissection. 2. Dispositif selon la revendication 1, caractérisé en ce que lesdits premier et deuxième registres emmagasinent des valeurs définissant un segment de 15 droite correspondant à une interpolation linéaire de la fonction. J. Dispositif selon la revendication 2, caractérisé en ce que lesdits premier et deuxième registres emmagasinent des valeurs de la fonction aux extrémités du segment d'interpolation. 4. Dispositif selon l'une des revendications 1, 2 et 3, caractérisé en ce que 20 ledit troisième registre emmagasine un terme correctif adapté à appliquer une correction à une interpolation linéaire. 5» Dispositif selon l'une des revendications 1 à 4;; caractérisé en ce que la combinaison linéaire introduite dans l'un desdits premier et deuxième registres est divisée par deux à la puissance zéro; la combinaison linéaire in-25 troduite dans l'autre desdits premier et second registres est divisée par deux à la puissance un^et la combinaison linéaire introduite dans ledit troisième registre est divisée par une puissance de deux supérieure à un. 6. Dispositif selon la revendication 5t caractérisé en ce que l'un desdits premier ou deuxième registres, sélectionné selon que la ralsus? d:=- la varia-30 ble indépendante est contenue dans le demi-segment infér-ieia? ou supérieur, reçoit son propre contenu divisé par deux à la puissance :spo, l'autre 71 26328 28 2099446 desdits premier et deuxième registre recevant la somme des contenus d'au moins lesdits premier, deuxième ettroisième registres divisée par deux à la puissance un. 7- Dispositif selon la revendication 5» caractérisé en ce que ledit premier 5 registre reçoit le contenu, divisé par deux à la puissance zéro, dudit premier ou deuxième registre suivant que le demi-segment inférieur ou supérieur contient la valeur de la variable indépendante, ledit deuxième registre recevant 3a somme des contenus d'au moins les premier, deuxième et troisième registres divisée par deux à la puissance un. 10 8. Dispositif selon l'une des revendications précédentes, caractérisé en ce qu'il comprend en plus desdits premier et deuxième registres une pluralité ordonnée de registres comprenant le troisième registre, chacun desdits registres recevant une combinaison algébrique linéaire de son propre contenu et, excepté pour le registre d'ordre le plus élevé, des contenus des 15 registres d'ordre plus élevé, ladite combinaison étant divisée par 2 =4 dans le cas du troisième registre, par 2^ = 8 dans le cas du quatrième registre et ainsi de suite, s'il existe un plus grand nombre de registres. 9> Dispositif selon la revendication 8, caractérisé en ce que certaines desdites combinaisons algébriques linéaires comprennent un multiple d'un terme 20 de degré plus élevé, ledit multiple étant obtenu en ajoutant une pluralité de quotients intermédiaires apparaissant pendant les divisions par deux successives effectuées au cours du calcul dudit terme de degré plus élevé pendant l'interpolation précédente. 10. Dispositif selon l'une des revendications 8 ou S, caractérisé en ce qu'il 25 comprend des moyens pour choisir le signe d'au moins un terme d'une combi naison algébrique linéaire, ledit signe dépendant du demi-segment qui a été sélectionné dans l'interpolation précédente. 11. Dispositif selon l'une des revendications 8 ou 9, caractérisé en ce qu'il comprend des moyens pour sélectionner le signe d'au moins un terme d'une 30 combinaison algébrique linéaire, ledit signe dépendant du demi-segment sélectionné dans l'interpolation en cours. 71 26328 29 2099446 12. Dispositif selon l'une des revendications 1 à 11, caractérisé en ce qu'il comprend un registre binaire pour emmagasiner une valeur donnée de la variable indépendante, et des moyens pour examiner tour à tour les digits dudit registre, un par interpolation, de façon à déterminer selon la valeur 5 de chaque digit, laquelle des deux moitiés du segment bissecté doit être choisie. 13- Dispositif selon l'une des revendications 1 à 11 adapté à fonctionner dans le mode inverse de façon à déterminer la valeur de la variable indépendante correspondant à une valeur donnée de la variable dépendante, caractérisé 10 en ce que ledit dispositif est adapté à déterminer pour chaque interpolation si la valeur de la variable dépendante obtenue par sélection d'un demi-segment déterminé est supérieure ou inférieure à ladite valeur donnée de la variable dépendante; à maintenir ladite sélection du demi-segment déterminé dans l'un de ces cas} et à remplacer dans l'autre cas ladite sélection 15 déterminée par la sélection de l'autre demi-segment, un digit 1 ou un digit 0 étant introduit suivant le cas dans un registre donnant la variable indépendante, lesdits digits étant introduits du plus significatif au moins significatif. 14. Dispositif selon la combinaison des revendications 12 et 13, caractérisé 20 en ce qu'il comprend une mémoire permanente pour emmagasiner les valeurs initiales destinées à être introduites dans les registres, et des circuits de commande adaptés à faire fonctionner le dispositif sélectivement soit coame générateur de fonction soit comme unité arithmétique effectuant des multiplications par interpolation linéaire et des divisions dans le mode 25 inverse. 15» Dispositif selon l'une des revendications 1 à 14 dans lequel les registres sont des registres à décalage, caractérisé en ce qu'il comprend : une pluralité d'additionneurs complets pour ajouter les contenus des registres en numération bits-série, mots parallèles; une pluralité de boucles de 30 recyclage pour réintroduire les combinaisons algébriques linéaires dans lesdits registres; et des circuits de commande adaptés à décaler des quantités réintroduites dans les registres de façon à effectuer les divisions par des puissances de deux. 71 26328 jo 2099446 16. Dispositif selon l'une des revendications 1 à 14, dans lequel les registres sont des registres à entrées parallèles, caractérisé en ce qu'il comprend : un additionneur parallèle; une pluralité de voies reliant les registres audit additionneur par l'intermédiaire de portes; et des circuits de coonan-5 de de portes adaptés à réaliser lesdites combinaisons algébriques linéaires par une séquence d'opérations bits-parallèles, mots-série, et à recycler dans lesdits registres les quantités ainsi obtenues- 17- Dispositif selon la revendication 16, caractérisé en ce qu'au soins un des registres est un registre à décalage, lesdits circuits de eo—nnrie étant 10 adaptés à décaler les quantités recyclées de façon à effectuer les divisions par les puissances de deux correspondantes. l8. Dispositif selon l'une des revend!cations 1 & 14, caractérisé en ce qu'il comprend : un registre à décalage principal qui se subdivise pour former lesdits registres; un additionneur complet relié audit registre principal; 15 et un registre tampon pour effectuer les additions ai numération bits-série, mots-série, la sortie de l'additionneur étant reliée à l'entrée du registre tampon et à une boucle de recyclage adaptée à recycler les combinaisons algébriques linéaires aux différentes parties du registre principal par l'intermédiaire d'une logique de division adaptée à diviser lesdites com-20 binaisons par les puissances de deux correspondantes. 19* Procédé pour le calcul automatique de la valeur d'une première variable fonction d'une deuxième variable, pour une valeur donnée de cette deuxième variable, caractérisé en ce qu'un ensemble d'au moins trois valeurs initiales, définissant la fonction de ladite deuxième variable, est traité de 25 façon à obtenir des ensembles successifs de nouvelles valeurs qui remplacent les valeurs initiales, chaque nouvelle valeur étant obtenue par une combinaison linéaire d'au moins une des valeurs de 1 'ensemble précédent, chaque combinaison étant divisée par une puissance de deux différente comprenant au moins la puissance zéro, la puissance un et une puissance supérieure à 30 un, lesdites nouvelles valeurs qui correspondent aux divisions par 2^ et 2"*" remplaçant sélectivement les valeurs correspondantes de 1 ' ensemble précédent selon la valeur 0 ou 1 affectée à des bits de moins en moins significatifs représentant une quantité qui converge progressivement vers ladite valeur donné de la deuxième variable. 71 26328 31 2099446 20. Procédé selon la revendication 19, dans lequel on calcule une valeur approchée de la fonction d'une variable indépendante par interpolation entre deux valeurs mises en mémoire, caractérisé en ce que le segment d'interpolation est bissecté de façon répétitive en effectuant une interpolation 5 pour le point milieu de ce segment et en remplaçant l'une desdites valeurs mises en mémoire par la nouvelle valeur obtenue par interpolation, de façon à obtenir un nouveau segment d'interpolation contenant la valeur donnée de la variable indépendante, les segments d'interpolation successifs, de plus en plus petits, convergeant vers cette valeur donnée, chaque nouvelle valeur 10 étant corrigée par addition d'un premier terme correctif dans au moins une des premières interpolations, ledit premier terme correctif étant successivement divisé par quatre pour obtenir le terme correctif des interpolations successives suivantes. 21. Procédé selon la revendication 20, caractérisé en ce qu'un deuxième terme 15 correctif est successivement divisé par huit pour obtenir le terme correctif des interpolations successives suivantes. 22. Procédé selon la revendication 20, caractérisa en ce qu'une pluralité de termes correctifs pour corriger lesdites nouvelles valeurs sont introduits dans la première interpolation et dans quelques interpolations suivantes, 20 chacun desdits termes correctifs étant divisé par une puissance de deux particulière avant chaque interpolation. 23- Procédé selon la revendication 22, caractérisa en oe qu'au moins un des termes correctifs est modifié en combinant ee terme à un terme auxiliaire qui est un multiple d'un autre, terme correctif. 25 24. Procédé selon l'une des revendications 22 ou 23, caractérisé en ee que le signe d'au moins un desdits termes correctifs utilisés au- cours d:une interpolation dépend de la position du nouveau segment obtenu dans ladite interpolation par rapport à la nouvelle valeur obtenue dans ladite interpolation. 71 26328 32 2099446 25- Procédé selon l'une des revendications 22, 23 ou 24, caractérisé en ce que le signe d'au moins un desdits termes correctifs utilisés au cours d'une interpolation dépend de la position du nouveau segment obtenu dans l'interpolation précédente par rapport à la nouvelle valeur obtenue dans l'inter-5 polation précédente. 26. Procédé selon l'une des revendications 20 à 25, caractérisé en ce que des valeurs initiales des termes correctifs sont calculées par la même méthode en fonction d'une autre variable indépendante. 27- Procédé selon l'une des revendications 20 à 25 caractérisé en ce que des 10 valeurs Initiales des termes correctifs sont calculées dans un processus temps réel, pendant certains intervalles de temps à partir de valeurs données de la fonction, les valeurs de la fonction entre lesdites valeurs données étant calculées par interpolation entre lesdits intervalles. 28. Procédé selon la revendication 19 dans lequel on calcule la valeur d'une 15 variable indépendante correspondant à une valeur donnée d'une fonction de cette variable indépendante, caractérisé en ce que l'on interpole linéairement par bissection deux valeurs de la fonction entourant la valetir donnée pour donner une nouvelle valeur, ladite nouvelle valeur étant corrigée par addition d'au moins un terme correctif, on divise ledit terme correctif par 20 'quatre pour obtenir le terme correctif des interpolations successives, on remplace par ladite nouvelle valeur corrigée l'une desdites deux valeurs de façon à donner deux nouvelles valeurs entourant ladite valeur donnée et l'on forme une succession de bits, allant du plus significatif au moins significatif, afin d'obtenir la valeur de la variable indépendante, chacun 25 desdits bits prenant la valeur 0 ou 1 suivant que ladite nouvelle valeur corrigée remplace la valeur supérieure ou inférieure de l'interpolation précédente.