Brevet FR2818407A1 — publié le 20020621

PROCEDE ET APPAREIL POUR CALCULER UNE RECIPROQUE DOMAINE DE L'INVENTION La présente invention se rapporte au domaine du traitement du signal. La présente invention se rapporte plus particulièrement à un procédé et un appareil pour calculer la réciproque ou l'inverse d'un nombre. CONTEXTE DE L'INVENTION Le calcul de la réciproque joue un rôle important dans l'opération de division, notamment avec des nombres décimaux à virgule flottante. En utilisant une réciproque, le résultat de la division de deux nombres peut être obtenu en multipliant le dividende par l'inverse du diviseur. Ce procédé de division peut être utilisée pour augmenter la vitesse de traitement des calculs complexes dans les dispositifs de traitement numérique tels que les ordinateurs et dans les circuits intégrés spécifiques à une application (ASIC) tels que les processeurs de traitement numérique du signal (DSP). Selon la norme IEEE sur l'arithmétique à virgule flottante binaire 0754P-1985, laquelle est incluse ici par référence, les nombres standard à virgule flottante aux formats à virgule flottante sont compactés en 32 bits avec une longueur (mantisse) de 24 bits significatifs en précision simple ou alors compactés en 64 bits avec une longueur de 53 bits significatifs en double précision. Plusieurs procédés d'interpolation et d'itération sont largement utilisés par les développeurs pour calculer les réciproques, dont l'approximation directe, l'interpolation linéaire, l'interpolation carrée, l'interpolation cubique, etc. Dans le procédé d'approximation directe pour obtenir la réciproque d'un nombre, toutes les mantisses possibles des réciproques sont stockées dans un tableau dans une ROM. Ce procédé permet d'obtenir le résultat rapidement, mais il exige une capacité de mémoire très importante. Pour obtenir une réciproque selon la norme IEEE 754, par exemple, le format virgule flottante à précision simple nécessite 223 x 23 = 184 Mbits de mémoire. Le procédé d'interpolation linéaire est basé sur le théorème d'une valeur moyenne obtenue du calcul et peut être résumé comme suit pour le calcul de la réciproque : 1 1 1 x =---T (X-Xo) (1) où e [xo, x] et x xo. Il est également possible d'employer l'interpolation carrée, l'interpolation cubique et d'autres procédés d'interpolation pour obtenir une réciproque ayant la précision requise. Tous ces procédés nécessitent cependant des opérations de multiplication supplémentaires et ont besoin d'une mémoire supplémentaire pour stocker les facteurs de correction. Le principal inconvénient des procédés d'interpolation est le fait que l'espace mémoire nécessaire pour stocker les données nécessaires augmente en même temps que la précision souhaitée. La procédé d'itération de Newton-Raphson est largement utilisée dans les ordinateurs numériques pour calculer les réciproques. Ce procédé donne la solution de l'équation f (z) =0 (2) en se basant sur l'utilisation de la formule récurrente Les valeurs z ; obtenues après l'itération i convergent de manière quadratique vers z, ce qui a pour résultat que les erreurs correspondantes # après l'itération i et l'itération i+1 sont liées par l'expression : e (z) (Zj) (4) L'utilisation du procédé de Newton-Raphson pour calculer la réciproque x ==a produit l'expression suivante : Xi+, = XI * (2-a*Xi) (5) Comme le montre l'équation (5), chaque étape itérative de ce procédé fait appel à deux opérations de multiplication effectuées dans l'ordre et à une opération de complément de 2. La précision d'une réciproque double ainsi après chaque étape itérative. L'inconvénient du procédé d'itération de Newton-Raphson en elle-même est qu'elle peut nécessiter plusieurs étapes d'itération pour obtenir une réciproque ayant la précision requise. Pour venir à bout des inconvénients ci-dessus, des procédés ont évolué vers l'utilisation de certains types de procédés d'interpolation pour obtenir l'approximation initiale de la réciproque et emploient ensuite un procédé d'itération qui se base sur cette approximation. Il a été proposé, par exemple, d'utiliser des tableaux d'inverses pour obtenir les valeurs initiales pour des itérations consécutives. RESUME DE L'INVENTION La présente invention fournit un procédé et un appareil pour diviser une valeur qui peuvent fournir rapidement et avec une grande précision l'inverse (la réciproque) d'un nombre. Conformément au procédé de l'invention, l'interpolation linéaire est employée pour obtenir une approximation de la réciproque d'un nombre. Cette approximation peut ensuite être utilisée comme valeur d'entrée pour des itérations de NewtonRaphson afin de calculer une réciproque avec une grande précision. Contrairement aux procédés de l'art antérieur, le procédé de l'invention fournit une formule pour calculer un nombre minimum d'entrées dans un tableau de recherche afin d'obtenir l'approximation d'une réciproque avec la précision requise. Le procédé de l'invention fournit également des formules pour calculer les approximations initiales et les facteurs de correction en vue de composer des entrées ou lignes dans les tableaux de recherche. Un appareil destiné à mettre en oeuvre le procédé de l'invention comprend une mémoire de tableau de recherche pour stocker ces valeurs, un multiplicateur de nombres entiers et un soustracteur. Par conséquent, la présente invention fournit un procédé pour générer un signal de sortie représentant une valeur de sortie qui représente une approximation de la réciproque de la valeur d'entrée D ayant une mantisse normalisée M (où 1 réciproque avec une précision souhaitée s = 2-N, où N Dans d'autres aspects du procédé de l'invention, l'étape consistant à générer n lignes dans les tableaux de recherche comprend les sous-étapes consistant à : iii) calculer le nombre minimum 1 de lignes de tableau de recherche nécessaires pour obtenir une précision supérieure à la précision souhaitée, où et iv) rechercher un nombre minimum requis n de lignes de tableau de recherche pour n=2, où 2 A. calculer où i = 0,..., n-1, Xo = 1 et x, +j = XI +1et n B. rechercher les lignes yi comprenant un ensemble de N bits significatifs puis réaliser une approximation d'une mantisse de y, pour i = 0,..., n-1. Avantageusement, l'étape consistant à générer un ensemble de lignes d'entrée dans le deuxième tableau de recherche comprenant les sous-étapes consistant à : calculer 2N-P 1 KI =-----où i = 0,..., n-1, xo = 1 et x, +t = x, ± 1 n Xj (X, ±) n et rechercher les lignes Ki comprenant un ensemble de (N-P) bits significatifs puis réaliser une approximation des parties entières de i pour i = 0,..., n-1. La présente invention fournit également un appareil pour calculer un inverse 1 ayant une précision E = 2-N d'une valeur d'entrée D ayant une mantisse normalisée M (où 1 s M N, l'appareil comprenant au moins un processeur, une première mémoire formant un tableau de recherche adressé sous la forme d'une fonction des P bits de poids fort de la mantisse M et ayant une sortie 10 comprenant un ensemble de N bits significatifs ; une deuxième mémoire formant un tableau de recherche adressé sous la forme d'une fonction des P bits de poids fort de la mantisse M et ayant une sortie K comprenant un ensemble de (N-P) bits significatifs ; un multiplicateur de dimension (N-P) x (NP) ayant deux entrées d'un ensemble de (N-P) bits significatifs suivant l'ensemble des P bits de poids fort de la mantisse M et de la sortie K, et une sortie MU comprenant un ensemble de (N-P) x (N-P) bits significatifs ; et un additionneur/soustracteur ayant une sortie 1 et ayant deux entrées reliées pour recevoir respectivement la sortie Io et l'ensemble des (N-P) bits de poids fort de la sortie MU. Dans d'autres aspects de l'appareil de l'invention, les première et deuxième mémoires sont combinées en un dispositif de stockage qui stocke à la fois Io et K et qui est adressé sous la forme d'une fonction des P bits de poids fort de la mantisse M. Avantageusement, l'appareil comprend en plus un dispositif pour effectuer une itération de Newton-Raphson programmée basée sur 1. De préférence, la première mémoire comprend une mémoire morte (ROM). Selon un mode de réalisation préféré, la deuxième mémoire comprend une mémoire morte (ROM). Selon un autre mode de réalisation préféré, le dispositif de stockage comprend au moins une mémoire morte (ROM). Selon un dernier mode de réalisation préféré, l'appareil est intégré dans un dispositif de traitement numérique du signal. BREVE DESCRIPTION DES DESSINS Dans les dessins qui illustrent à titre d'exemple un seul mode de réalisation préférentiel de l'invention, La figure 1 est un graphique représentant le procédé d'interpolation linéaire telle qu'elle est utilisée dans la présente invention ; La figure 2 est un synoptique représentant un appareil d'interpolation linéaire conforme à l'invention pour obtenir une précision de N bits de la mantisse d'une réciproque ; et La figure 3 est un synoptique représentant un appareil d'itération de NewtonRaphson pour obtenir une précision de 2N bits pour la mantisse d'une réciproque. DESCRIPTION DETAILLEE DE L'INVENTION L'invention est applicable aux calculs qui emploient la mantisse M d'un nombre binaire D dans le format à virgule flottante. La mantisse M du nombre en entrée est supposée avoir été préalablement normalisée, c'est-à-dire être égale ou supérieure à 1 et inférieure à 2 de manière à ce que 1 La figure 1 illustre un mode de réalisation préférentiel du procédé d'interpolation linéaire employé dans le procédé de l'invention pour réaliser une approximation de la réciproque d'un nombre. En comparaison du procédé d'approximation directe, l'interpolation linéaire réduit de manière significative le nombre de lignes qu'il faut stocker dans un tableau de recherche. Pour obtenir une précision de N bits E = 2-N pour la mantisse M de la réciproque tout en employant le procédé d'approximation directe, le tableau de recherche aurait besoin de 2N-1 lignes à écarts égaux, alors que pour obtenir la même précision de N bits s = 2-N pour la mantisse de la réciproque en employant le procédé d'interpolation linéaire, il est suffisant de disposer de 2P lignes dans le tableau de recherche avec P s N. Chaque ligne est distincte de la ligne précédente de 2-P, les P bits de poids fort (MSB) de la mantisse M constituent ainsi l'adresse du tableau de recherche. Les valeurs xi et xs+l dans la figure 1 représentent deux lignes consécutives du tableau de recherche. La valeur yi représente l'approximation de la valeur-qui est xi stockée dans le tableau de recherche. La valeur (x - Xi) est représentée par les bits de la mantisse immédiatement après ses P premiers MSB. L'approximation d'une réciproque requise est exprimée par la formule suivante : y = yi - ki (x-xi) (6) où ki est le facteur de correction et Xi S x Pour obtenir la mantisse M d'une réciproque avec une précision de N bits, au moins (N-P) bits après les P MSB de la mantisse M doivent être mis en concordance avec au moins (N-P) bits significatifs du facteur de correction Ki indiqué dans la figure 1. Ces facteurs sont stockés dans le tableau de recherche sous forme de nombres entiers Ki = 2N-P x kl. Par conséquent, le fait d'obtenir la mantisse M de la réciproque avec une précision de N bits comprend les étapes consistant à multiplier les (N-P) bits de la mantisse M par les (N-P) bits du facteur Ki dans le multiplicateur de nombres entiers de dimension (N-P) x (N-P), à diviser le résultat par 2N-P et ensuite à soustraire le quotient de y,. Les N bits de la mantisse M pour yi et les (N-P) bits pour le nombre entier Ki sont stockés dans le tableau de recherche. Les valeurs yi et Ki sont calculées d'après les formules suivantes avec une précision respective de N et de (N-P) : où n est le nombre de lignes dans le tableau de recherche. L'erreur maximale E du procédé d'interpolation linéaire pour rechercher la réciproque d'une mantisse M, normalisée de manière à être comprise entre 1 et 2, dépend de n et elle est exprimée par la formule suivante : Le nombre n nécessaire de lignes dans le tableau de recherche peut être déterminé à partir de la formule (9) où l'erreur maximale requise s est connue. Pour n = 64, par exemple, l'erreur maximale s du procédé d'interpolation linéaire destiné à obtenir une réciproque est égale à 2. 98jcl0 > 2-16, alors que pour n =128 l'erreur maximale selon le procédé d'interpolation linéaire est s 7, 54*10- La figure 2 illustre un appareil 10 pour calculer les réciproques conformément à l'invention, lequel met en oeuvre le procédé tel qu'il est décrite ci-dessus. Les P MSB de la mantisse M du numéro d'entrée D forment la ligne d'adresse de la ROM 12 qui contient 2'lignes. La ROM 12 stocke de préférence N bits pour l'inverse Yi des P MSB d'une mantisse (bien qu'il soit suffisant de stocker (N-1) bits car le bit de tête de l'inverse est toujours 0 ) et (N-P) bits du facteur de correction K, pour effectuer l'interpolation linéaire. Les (N-P) bits des facteurs de correction K sont acheminés à une entrée du multiplicateur de nombres entiers 14 ayant une dimension (N-P) x (N-P). La valeur de (N-P) bits qui se trouvent immédiatement après les P MSB de la mantisse d'entrée M est acheminée à une autre entrée du multiplicateur 14. Les (N-P) MSB MU du produit obtenu en multipliant la longueur de (N-P) x (N-P) bits sont acheminés à une entrée du soustracteur de nombres entiers 16 ayant une dimension N. Les P MSB de l'entrée MU sont tous à 0 et les (N-P) bits de poids faible (LSB) du produit sont éliminés. Les N bits de l'approximation de la réciproque Yi en provenance de la ROM 12 (représentés par 10 dans la figure 2) sont acheminés à une autre entrée du soustracteur 16. Le résultat de la soustraction forme la sortie de N bits (représentés par 1 dans la figure 2) de l'appareil 10. Notez que si les P MSB de la mantisse d'entrée M sont égaux à 1 (ce qui veut dire que le bit de poids fort est à 1 alors que les (P-1) autres bits sont à 0 ), la sortie 1 peut alors être représentée comme le complément à 1 de (N-P) bits de MU, ce qui simplifie les calculs. La figure 3 illustre un appareil 20 pour réaliser des itérations de NewtonRaphson du résultat de l'interpolation linéaire afin d'augmenter la précision de N bits du résultat à une précision de 2N bits. Les N bits de la sortie 1 de l'appareil d'interpolation 10 sont acheminés à une entrée du multiplicateur de nombres entiers 22 ayant une dimension N x 2N. Les 2N bits de la sortie du multiplexeur 24 sont acheminés à une autre entrée du multiplicateur 22. Le multiplexeur 24 sélectionne alternativement 2N MSB ou bits de poids fort de la mantisse d'entrée M (rempli avec des 0 supplémentaires si nécessaire) et 2N bits de la sortie d'un dispositif 26 à complément de 2. Le multiplicateur 22 produit un résultat de 3N bits de long. Les N ensembles de poids faible du produit de cette multiplication sont éliminés. Les 2N bits de poids fort MU1 du produit sont acheminés au dispositif 26 à complément de 2. La sortie du dispositif 26 à complément de 2 de 2N bits de long est acheminée au multiplexeur 24. Lors du deuxième passage à travers le multiplexeur 22, les 2N MSB ou bits de poids fort du produit de la multiplication forment la sortie de 2N bits de l'appareil 20 (représentée par Il dans la figure 3). Bien qu'un mode de réalisation préférentiel de la présente invention a été présenté et décrit au moyen d'un seul exemple, il sera évident aux personnes compétentes dans l'art que des changements et des modifications peuvent être effectués sans s'écarter de la portée de l'invention telle qu'elle est définie dans les revendications jointes. REVENDICATIONS 1. Appareil pour calculer un inverse 1 ayant une précision s = 2-N d'une valeur d'entrée D ayant une mantisse normalisée M (où 1 sM 2. Appareil selon la revendication 1, dans lequel les première et deuxième mémoires sont combinées en un dispositif de stockage qui stocke à la fois Io et K et qui est adressé sous la forme d'une fonction des P bits de poids fort de la mantisse M. 3. Appareil selon la revendication 1 ou 2, comprenant en plus un dispositif pour effectuer une itération de Newton-Raphson programmée basée sur 1. 4. Appareil selon l'une des revendication 1 à 3, dans lequel la première mémoire comprend une mémoire morte (ROM). 5. Appareil selon l'une des revendications 1 à 4, dans lequel la deuxième mémoire comprend une mémoire morte (ROM). 6. Appareil selon la revendication 2, dans lequel le dispositif de stockage comprend au moins une mémoire morte (ROM). 7. Dispositif de traitement numérique du signal, comprenant l'appareil selon l'une des revendications 1 à 6. 8. Procédé pour générer dans un appareil selon l'une des revendications 1 à 6 un signal de sortie représentant une valeur de sortie qui représente une approximation de la réciproque de la valeur d'entrée D ayant une mantisse normalisée M (où 1 M 9. Procédé selon la revendication 8, dans laquelle l'étape consistant à générer n lignes dans les tableaux de recherche comprend les sous-étapes consistant à : iii. calculer le nombre minimum 1 de lignes de tableau de recherche nécessaires pour obtenir une précision supérieure à la précision souhaitée, où iv. rechercher un nombre minimum requis n de lignes de tableau de recherche pour n = 2P, où 2 10. Procédé selon la revendication 8 ou 9, dans laquelle l'étape consistant à générer un ensemble de lignes d'entrée dans le premier tableau de recherche comprend les sous-étapes consistant à : 1 1 Jjc, (. f, ±) +A. calculer , =-----" où i = 0,..., 1 Xi (Xi ±) n n-l, xo = 1 et Xi+l = xi ± ; et n B. rechercher les lignes yi comprenant un ensemble de N bits significatifs puis réaliser une approximation d'une mantisse de yi pour i = 0,..., n-l. 11. Procédé selon l'une des revendications 8 à 10, dans laquelle l'étape consistant à générer un ensemble de lignes d'entrée dans le deuxième tableau de recherche comprend les sous-étapes consistant à : 2' 1 A. calculerKj= oùi=O,..., n-l, xo=letx1+l=Xi± ; et 1 n Xi (xi ±) n B. rechercher les lignes Ki comprenant un ensemble de (N-P) bits significatifs puis réaliser une approximation des parties entières de iCi pour i = 0,..., n-1.