Brevet FR2747489A1 — publié le 19971017

La présente invention concerne un procédé pour le calcul approché du produit de mots de code d'information codés dans un format à virgule flottante utilisé notamment pour convoyer des informations de débit dans des réseaux de transmission de données par paquet connu sous l'abréviation anglo-saxonne ATM de "asynchronous transfer mode". Une particularité des réseaux ATM est qu'ils permettent à chaque usager d'utiliser pleinement la bande passante disponible sur le trajet d'une connexion préalablement établie sans nécessiter une réservation statique de ressources lors de l'établissement d'une connexion. Ce service est connu sous l'abréviation anglo-saxonne ABR de "Available bit rate". En contrepartie de cette souplesse, les deux extrémités d'une connexion ont à adapter leur débit de transmission à la bande passante disponible. A cet effet, des cellules ATM particulières désignées sous l'abréviation anglosaxonne RM de "ressource management" permettent de renseigner les extrémités d'une connexion sur la disponibilité des ressources dans le réseau. Ces cellules sont émises et traitées en temps réel par les équipements d'extrémité qui sont connectés aux différentes artères du réseau aussi bien que par les commutateurs disposés à ses différents noeuds. Les cellules RM comportent des champs destinés à convoyer des informations de débit comme par exemple, le débit autorisé courant de la source CCR, ou le débit conseillé par le réseau à la source ER. Cependant comme ces champs font appel à un codage en virgule flottante particulier caractérisé par un bit de nullité, 5 bits d'exposant et 9 bits de mantisse la multiplication ou la division qu'il est nécessaire d'effectuer pour adapter le débit d'une source de transmission à la bande passante disponible sur le trajet d'une connexion devient une opération longue car elle nécessite le transcodage des données dans un format à virgule fixe sur 41 bits, ce dont les microprocesseurs commercialisés actuellement ne sont pas capables naturellement de par la taille de leurs registres de travail. Le but de l'invention est de pallier les inconvénients précités. A cet effet, l'invention a pour objet un procédé pour le calcul approché du produit de mots de code d'information codés dans un format en virgule flottante, chaque mot de code étant défini à l'aide d'un exposant e et d'une mantisse m par une relation de la forme R(e,m)=2e.f(m) à laquelle est associé un code l(e,m)=2M.e+m où e et m sont des entiers tels que O O 2M 2M P(m) est la partie entière de Logf(m)-m. Log 2 L'invention a également pour objet un dispositif pour la mise en oeuvre du procédé selon l'invention. L'invention a principalement pour avantage qu'elle permet de simplifier le calcul du produit de nombres codés en virgule flottante, en limitant considérablement la taille des registres des microprocesseurs mis en oeuvre pour effectuer les calculs. D'autres caractéristiques et avantages de l'invention apparaîtront dans la description qui suit faite en regard des dessins annexés qui représentent: Les figures la et lb les lois d'approximation utilisées pour la multiplication de nombres codés dans un format en virgule flottante selon l'invention. La figure 2 un graphe montrant l'erreur d'approximation résultante. La figure 3 un mode de réalisation d'un dispositif pour la mise en oeuvre du procédé selon l'invention. Le code utilisé pour coder l'information de débit dans une cellule RM d'un réseau ATM est un code exprimé en virgule flottante suivant une relation de la forme R(z,e,m)=z.2e.(l +m/512) (1) dans laquelle z=O ou 1 l'exposant e est un entier compris entre 0 et 31 et la mantisse m est un entier compris entre 0 et 511. L'exposant e est codée sur une longueur de 5 bits et la mantisse m est codée sur une longueur de 9 bits. Au total, suivant la valeur de z, 25+9=16384 valeurs non nulles peuvent être codées, auxquelles peuvent être ajoutées 16384 valeurs nulles. A chacune de ces valeurs est associé un code I(z, e, m) = 214z + 29e + m (2) pour coder l'information de débit R(z, e, m) dans une cellule RM. En considérant les cas où z=l et en ignorant la quantité 214z, le procédé selon l'invention consiste à approximer la quantité R(e, m)=2e.(l+m/512) (3) qui est associée à un mot de code l(e,m)=29.e+m (4) par la quantité: R(e, m)approx=exp(k.(l(e,m)+p(m))) (5) dans laquelle k est une constante, p(m) est une fonction monotone croissante puis décroissante de la mantisse m telle que définie par les 512 valeurs du tableau de l'annexe 1 et dont la courbe représentative est montrée à la figure la. La fonction p(m) peut également être caractérisée analvtiauement comme étant la Dartie entière de 738.66Log(1+m)-m 512 (remarque 738,66= Log2 Soit W un mot de code ayant e comme exposant et m comme mantisse, c'est-à-dire W=l(e,m), désignons par P(W) I'expression l(e,m)+p(m). En appliquant la relation (4) il vient . P(W)=29e+m+p(m). Comme m+p(m) reste inférieur à 512 d'après la figure 1, P(W) est également un mot de code, ayant e comme exposant et m+p(m) comme mantisse, c'està-dire P(W)=l(e,m+p(m)). Comme indiquée sur le graphe de la figure 2, I'erreur relative qui résulte de la substitution de la relation (1) par la relation (5) est très faible sa valeur reste positive et inférieure à 1,5%o quels que soient les débits compris entre 1 et 1 o10 cellules/secondes. Le procédé selon l'invention permet d'obtenir une approximation du produit de deux valeurs de code R(e,m) et R(e', m') exprimées suivant la relation (5) et associées à deux mots de code W=l(e,m) et W'=l(e',m') par une fonction exponentielle de P(W) + P(W') multipliée par la constante k. La somme P(W)+P(V) est un mot de code, que l'on peut exprimer sous la forme P(W"), sous réserve de montrer que P est inversible, soit ws=p-1 (P(W)+P(W')) (8) Comme montré plus haut P(W)=l(e,m+p(m)). II apparaît donc que l'exposant e est invariant dans la transformation P et que la mantisse m+p(m) peut être considérée comme une fonction inversible car monotone croissante. Si q désigne cette fonction inverse, l'inverse de la fonction P s'exprime alors sous la forme #-I (1(e,m))=l(e,q(m)) (9) Une table représentative des valeurs prises par la fonction q et correspondant au graphe de la figure I b est donnée en annexe 2. La fonction q(m) peut également etre caractérisée analytiquement comme étant la partie entière de 512.(exp (m)-1) 738,66 Un algorithme permettant l'exécution du produit W' défini par la relation (8) et utilisant les données fournies par les tables p et q est le suivant: r t~wordl6 type entier codé sur au moins 16 bits p[ 1 tableau constant de 512 entiers entre 0 et 511 q[ ] tableau constant de 512 entiers entre 0 et 511 table p (annexe 1) t table q (annexe 2) #define ZERO~MASK 0x4000 &num;define EXPONENT~MASK 0x3E00 #define MANTISSA~MASK 0x01FF t~word16 mult (t~word16 W1, t~word16 W2) f if (W1 8 W2 8 ZERO~MASK) ( /* les deux opérandes sont non-nuls */ t~word16tmp = W1 + W2 + P[W1 & MANTISSA~MASK] + P[W2 & MANTISSA~MASK] ; /* insérer un test de dépassement */ retum (ZERO~MASKltmp 8 EXPONENT~MASK I q[tmp & MANTISSA~MASKl); else f /* un des opérandes est nul ! return 0; Dans cet algorithme "W1" et "W2" désignent respectivement le premier et le deuxième opérande de la multiplication. Son exécution n'offre pas de difficulté et peut être réalisée à l'aide d'un microprocesseur du commerce convenablement programmé à cet effet. Toutefois, un dispositif ayant une fonction équivalente utilisant des composants discrets assemblés de la façon représentée à la figure 4 peut aussi être réalisé. Celui-ci comporte, représenté à l'intérieur de lignes fermées en pointillés, un premier ensemble 1 pour le calcul de P(W1 )+P(W2), suivi d'un deuxième ensemble 2 pour le calcul du mot de code résultant selon la relation (9). Dans cet exemple le premier et le deuxième opérande de la multiplication ont un format binaire composé de 5 bits pour le codage de l'exposant et de 9 bits pour le codage de la mantisse. Ceux-ci sont appliqués respectivement sur des entrées d'adresse d'une première 3 et d'une deuxième 4 mémoire morte programmable au travers de circuits d'adressage 5 et 6. Les mémoires 3 et 4 mémorisent chacune la table p des nombres représentatifs de la fonction P(m). décrite en annexe. Les mémoires 3 et 4 reçoivent en entrée la mantisse de l'opérande concernée (respectivement W1 et W2) obtenue grâce à un masque MSKmantisse=[0000000111111111] appliqué à W1 et W2. Leurs sorties sont reliées à une entrée d'opérande des circuits additionneurs 7 et 8, respectivement, dont l'autre entrée reçoit les opérandes W1 et W2, respectivement, afin de calculer P(W1) et P(W2). Un troisième circuit additionneur 9 effectue l'addition P(W) des mots de code P(W1) et P(W2) obtenus en sortie des circuits additionneur 7 et 8. Le calcul de W= p-1 (P(W1)+P(W2)) donnant le mot de code résultant est obtenu par l'ensemble 2 qui est formé par deux portes ET 10 et 11, d'une mémoire morte programmable 12 pour la mémorisation des nombres constituant la table q définie en annexe, et d'un circuit multiplexeur 13. Les portes ET 10 et 11 sont commandées par des mots de masquage pour sélectionner respectivement dans le mot binaire obtenu en sortie du circuit additionneur 9, les bits d'exposant ou les bits de mantisse composant le mot P(W'). Les bits d'exposant e sont transmis par la porte ET 10 à destination d'un circuit OU 13, et les bits de mantisse m sont appliqués aux entrées d'adressage de la mémoire 12 contenant la table q, dont la sortie des données est appliquée également sur une entrée de la porte OU 13. Le résultat obtenu en sortie de la porte OU 13 correspond alors au mot W=l(e,q(m)) défini par la relation (9). Un dispositif à peu près identique peut être réalisé pour le calcul de la division de deux nombres codés dans un format en virgule flottante selon la relation (1). il suffit pour cela de substituer le signe + par un signe ce qui revient à changer l'additionneur 9 de la figure 3 par un circuit soustracteur. Si l'un des opérandes est une constante le procédé et le dispositif sont susceptibles de simplifications ultérieures. C'est notamment le cas dans le problème pratique qui consiste à déterminer le nombre de cycles d'horloge de fréquence F séparant l'émission de deux cellules consécutives au débit R(e,m). En appliquant le même raisonnement que ci-dessus le rapport R(eF,mF)/R(e,m) apparaît comme une valeur R(E,M) dont l'exposant E=(eF-e) ou (eF-e-1) selon que m est supérieur ou non à une valeur seuil (dépendant de mF), et dont la mantisse M est une fonction de m (dépendant de mF) facile à tabuler. Plus précisément: si m E=eF-e M=q(mF+p(mF)-m-P(m)) sinon E=eF-e-1 M=q(mF+p(mF)-m-p(m)+51 2) L'algorithme ci-dessus est susceptible d'être employé dans les dispositifs dits d'égrenage qui permettent d'imposer un débit spécifié à un flot de cellules ATM. Le procédé de calcul approché du produit de nombres codés en virgule flottante présenté ci-dessus peut être étendu à d'autres types de codage en virgule flottante. En effet soit un codage de la forme R(e,m)=2e.f(m) et l(e,m)=2M.e+m O 1 R(e,m)=exp(e.Log 2+Log f(m)) R(e,m)=exp(K(2M.e+m+p(m))) Log 2 2M où k=Log2 et p(m)= 2M.Logf(m)-m 2M Log2 En remplaçant p(m) par sa partie entière on obtient une valeur approchée de R(e,m). Compte-tenu de l'hypothèse faite sur f(m), le même raisonnement que ci-dessus s'applique et aboutit au résultat suivant: soient R(e,m) et R(e',m') deux valeurs du code, soient e" et m" les parties exposant et mantisse du mot code 2Me+m+2Me'+m'+p(m)+p(m') alors l'exposant du mot code produit est e" et sa mantisse est q(m")=-1(exp(Log2.m)). Il en découle un procédé de calcul approché du 2M produit en remplaçant p et q par leur partie entière. Annexez (Table p) int p[] = 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 38, 38, 38, 38, 38, 38, 38, 38, 38, 37, 37, 37, 37, 37, 37, 37, 37, 36, 36, 36, 36, 36, 36, 36, 36, 35, 35, 35, 35, 35, 35, 35, 34, 34, 34, 34, 34, 34, 34, 33, 33, 33, 33, 33, 33, 33, 32, 32, 32, 32, 32, 32, 31, 31, 31, 31, 31, 31, 30, 30, 30, 30, 30, 30, 29, 29, 29, 29, 29, 29, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 23, 23, 23, 23, 23, 22, 22, 22, 22, 22, 21, 21, 21, 21, 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 18, 18, 18, 18, 17, 17, 17, 17, 17, 16, 16, 16, 16, 15, 15, 15, 15, 14, 14, 14, 14, 13, 13, 13, 13, 13, 12, 12, 12, 12, 11, 11, 11, 11, 10, 10, 10, 10, 9, 9, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0 Annexe Il (Table q) int q[] = 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 10, 11, 11, 12, 13, 14, 14, 15, 16, 16, 17, 18, 19, 19, 20, 21, 21, 22, 23, 24, 24, 25, 26, 27, 27, 28, 29, 29, 30, 31, 32, 32, 33, 34, 35, 35, 36, 37, 38, 38, 39, 40, 41, 41, 42, 43, 44, 44, 45, 46, 47, 47, 48, 49, 50, 50, 51, 52, 53, 53, 54, 55, 56, 57, 57, 58, 59, 60, 60, 61, 62, 63, 63, 64, 65, 66, 67, 67, 68, 69, 70, 71, 71, 72, 73, 74, 75, 75, 76, 77, 78, 79, 79, 80, 81, 82, 83, 83, 84, 85, 86, 87, 87, 88, 89, 90, 91, 91, 92, 93, 94, 95, 96, 96, 97, 98, 99, 100, 101, 101, 102, 103, 104, 105, 106, 106, 107, 108, 109, 110, 111, 111, 112, 113, 114, 115, 116, 116, 117, 118, 119, 120, 121, 122, 122, 123, 124, 125, 126, 127, 128, 129, 129, 130, 131, 132, 133, 134, 135, 135, 136, 137, 138, 139, 140, 141, 142, 143, 143, 144, 145, 146, 147, 148, 149, 150, 151, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 297, 298, 299, 300, 301, 302, 303, 304, 305, 307, 308, 309, 310, 311, 312, 313, 314, 315, 317, 318, 319, 320, 321, 322, 323, 324, 326, 327, 328, 329, 330, 331, 332, 334, 335, 336, 337, 338, 339, 340, 342, 343, 344, 345, 346, 347, 349, 350, 351, 352, 353, 354, 356, 357, 358, 359, 360, 361, 363, 364, 365, 366, 367, 369, 370, 371, 372, 373, 375, 376, 377, 378, 379, 381, 382, 383, 384, 385, 387, 388, 389, 390, 392, 393, 394, 395, 396, 398, 399, 400, 401, 403, 404, 405, 406, 408, 409, 410, 411, 413, 414, 415, 416, 418, 419, 420, 421, 423, 424, 425, 427, 428, 429, 430, 432, 433, 434, 435, 437, 438, 439, 441, 442, 443, 444, 446, 447, 448, 450, 451, 452, 454, 455, 456, 458, 459, 460, 461, 463, 464, 465, 467, 468, 469, 471, 472, 473, 475, 476, 477, 479, 480, 481, 483, 484, 485, 487, 488, 490, 491, 492, 494, 495, 496, 498, 499, 500, 502, 503, 505, 506, 507, 509, 510 REVENDICATIONS 1. Procédé pour le calcul approché du produit de mots de code d'information codés dans un format en virgule flottante, chaque mot de code étant défini à l'aide d'un exposant e et d'une mantisse m par une relation de la forme R(e,m)=2e.f(m) à laquelle est associé un code l(e,m)=2M.e+m où e et m sont des entiers tels que 0 2M 2M Log f(m) - m. Log 2 2. Procédé selon la revendication 1, caractérisé en ce qu'il consiste à exprimer f(m) et l(e,m) par les relations f(m)=l+m/512 et l(e,m)=29e+m dans lesquelles e est un nombre entier codé sur 5 bits et 0 R(e,m)approx=exp(k.(l(e,m)+p(m))) dans laquelle k est une constante et p(m) est une fonction monotone croissante puis décroissante de la mantisse m, fonction nulle pour les valeurs m=O et m=512 et telle que la quantité m+p(m) reste toujours inférieure à 512. 3. Procédé selon la revendication 2, caractérisé en ce qu'il consiste à substituer dans la relation R(e,m)approx la quantité P(W)=l(e,m)+p(m) par la quantité l(e,m+p(m)). 4. Procédé selon la revendication 3, caractérisé en ce qu'il consiste à approximer le produit de deux valeurs de code R(e,m) et R(e',m') associé à deux mots de code W et W, par une valeur résultante qui est l'exponentielle de P(W)+P(W') multiplié par k. 5. Procédé selon la revendication 4, caractérisé en ce que le mot de code résultant W est obtenu par un calcul de la transformée inverse p-1 défini par P-1 (I(e,m))=l(e,q(m)) où q est la fonction inverse de m+p(m). 6. Procédé selon l'une quelconque des revendications 2 à 5, caractérisé en ce que la fonction p(m) est la partie entière de 738,66 Log(1 + 512 Lolm 7. Utilisation du procédé selon l'une quelconque des revendications 1 à 5 à la multiplication et à la division de nombres par une constante. 8. Dispositif pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'il comprend un premier ensemble de calcul 1 de la fonction résultante P(W') comportant deux mémoires mortes programmables (3, 4) pour la mémorisation de la fonction p(m) couplé à des circuits additionneurs (7, 8, 9) pour le calcul de la fonction résultante (P(W) ainsi qu'un deuxième ensemble 2 comportant une mémoire morte programmable pour la mémorisation de la fonction inverse q et le calcul du mot de code résultant W"=P-1 (P(W)+P(W)).