FR 2703482 A1 19941007 FR 9303589 A 19930329 "Procédé de mise à jour de la taille de l'intervalle dans la méthode du codage arithmétique" Domrnaine technique La présente invention concerne un procédé de mise à jour de la taille de l'intervalle dans la méthode du codage arithmétique. Etat de la technique antérieure Explication générale du codage arithmétique Comme décrit dans l'article de Glen a Langdon, Jr intitulé "An Introduction to Arithmnetic Coding" (IBM Journal of Research and Development, 28 ( 2): 135-149, mars 1984), le codage arithm 6 étique est une méthode bien connue de compression de 1 5 données sans perte d'information. Le codage arithmétique établit une correspondance entre une suite de symboles et un intervalle de nombres réels On commence avec l'intervalle lO, 1 Ll Lorsque chaque symbole est codé, l'intervalle courant est remplacé par un sousintervalle de celui-ci. Après le codage d'une suite de symboles, la suite originale peut être reconstruite 2 O exactement, n'importe quel point dans l'intervalle courant étant donné. Dans ce type de codage il est usuel de mémoriser le point le plus à gauche de l'intervalle comme résultat, la valeur obtenue étant appelée la valeur du code. Cet algorithme de codage est récursif Pour chaque symbole à coder, l'algorithme partage l'intervalle courant en fonction des probabilités d'occurence et de l'ordre SP 7644 DB donné par la liste des symboles qui peuvent être code Puis l'algorithme remplace l'intervalle courant par le sous intervalle correspondant au symbole à coder Cette procédure est répétée autant de fois que nécessaire pour coder une séquence donnée. Explication mathématique du codage arithmétique Jusqu'ici, on a donné une explication géométrique du codage arithm Ctique On parle des intervalles et leur sous-division Pour la mise en oeuvre dans un ordinateur, il faut expliquer la méthode en utilisant les quantités numériques Cette explication est donnée maintenant 1 o Dans la description qui va suivre, on adopte les notations suivantes: S = {s ,sl, 'v-l} Si P(si) P(Si) Ai Xi Xmar Ri Ci ensemble des N symboles pouvant 8 tre codes symbole à coder à étape i probabilité d'occurrence du symbole probabilité cumu 16 e du symbole taille de l'intervalle courant plage de valeurs admissibles de Ai décalage pour représenterp(si) Ai dans R la valeur maximum possible de Xi cumulande de P(si) Ai valeur du point de code courant (emplacement de l'extremit gauche de l'intervalle) SP 7644 DB c(i comme C, + Ri non décalée Bl 1 + X, bits de sortie Tk bloc de bits de largeur fixé Comme expliqué plus haut, h chaque étape, l'état du codeur est donné par un sous-intervalle de l'ensemble l 0, If Le processus pour coder un symbole consiste à remplacer l'intervalle courant par un sous-intervalle de lui-même. Pour representer l'intervalle courant dans un ordinateur, on maintient à jour deux quantités arithmétiques: Ci, le point plus à gauche de l'intervalle, et Ai la taille de l'intervalle Donc à chaque étape l'intervalle actuel et lCi, C, + AJ. 1 O Ainsi, le processus donné plus haut pour coder un symbole est exprimé par ces Equations: Ai, = p(si) Ai ( 1) C+, = Ci + P(s,) * Ai ( 2) o p(s,) est la probabilité modélisée du symbol si, et P(si) est la somme des probabilités 1 5 de tous les symboles qui précèdent si dans la liste de l'alphabet source, P() Ep() j l'intervalle, et la seconde à la récurrence de la valeur du code. SP 7644 DB Explication de l'algorithme de précision finie pour le codage arithmétique Ces équations supposent une arithmétique de précision infinie Pour la mise en oeuvre d'un codage arithm 6 tique sur des opérations arithmétiques de précision finie, on utilise l'approche de Frank Rubin dans un article intitulé "Arithmetic Stream Coding Using Fixed Precision Registers" (IEEE Transactions on Information Theory, IT- 25 ( 6): 672-675, novembre 1979) On fixe le nombre de bits qui sont utilisés pour représenter chacun des si, Ri, Ai, Ci, Bi, p(si) et P(si): on désigne ces quantités par Is, R, JA, g C, fi, op et NP Il y a lieu de noter que g P = gp On choisit aussi la plage X = la, 2 al, 1 o o a > O, des tailles d'intervalles admissibles On s'assure alors que l'on a toujours Ai C R; pour cela, à chaque étape du codage on effectue les opérations suivantes: 1 Obtenirp(si) et P(si) Calculer exactementp(si) Ai. 2 Déterminer le décalage Xi tel que p(si) ' Ai 2 xi E R. 3 Trouver l'approximation inférieur sur NA-bits la plus proche de p(si) Ai 2 xl; ceci donne Ai+l 4 Calculer exactement Ri = P(sl) ' Ai. Calculer exactement Ci Ci + Ri. 6 Emettre le bit de retenue et les Xi bits les plus significatifs de Ci: ceci forme le bloc de taille variable Bi. SP 7644 DB Notez que les définitions des quantités dans l'algorithme determinent certaines relations de longueur: * par définition de probabilité cumulée, g P = p, * par étapes 1 et 2, X, = p, * par étape 4 R = g P + g A = p + 4, * par 6 tape 6, i B I + X,1 = I + p (la taille des Bis sont variable, mais il faut assez des bits pour représenter la plus longue valeur de Bl possible), a par étape 7, 9 C = _Ip + M. Donc les paramètres lP et A d 6 terminent la longueur de toutes les autres quantités dans ces équations. On a ainsi expliqué comment la suite de blocs de taille variable Bl est engendr 6 par l'algorithme Chaque bloc contient I + Xi bits, consistant en la retenue de sortie et des Xi bits les plus significatifs de la somme Ci = Ci + Ri Ces blocs de longueur variable peuvent alors t re assembl 6 S en une séquence de blocs de longueur fixe Tk La 1 5 séquence des blocs Tk constitue le flux de codage de sortie Le processus d'assemblage est fait par une m 6thode standard qui ne nous concerne pas dans la suite du document actuel. On peut résumer les étapes I à 7 de l'algorithme de précision finie ci-dessus par les équations: z 2 o O (A+, X;, Ri) = f(si, Ai) ( 3) (Ci+,, Bi) = g(C,, Ri, Xl) ( 4) SP 7644 DB La fonctionf effectue les étapes 1 à 4 mentionnées ci-dessus La fonction g effectue les étapes 5 à 7. Etat de la technique antérieure de la mise à Jour de la taille d'intervalle L'actualisation de la taille d'intervalle consiste dans les étapes suivantes: 1 Obtenir p(si) et P(si) Calculer exactement p(si) Ai. 2 Déterminer le décalage Xi tel que p(si) Ai 2 X' E 7 R. 3 Trouver l'approximation inférieur sur It A-bits la plus proche de p(si) Ai, 2 Xi; ceci donne A 1 +l 1 O 4 Calculer exactement Ri-= P(s,) Ai. Cette technique de mise à jour de la taille d'intervalle présente également un inconvénient qui réside dans le fait que cet algorithme nécessite deux multiplications pour chaque symbole codé, ce qui représente un obstacle à la mise en oeuvre à grande vitesse. 1 5 Pour cette raison, divers auteurs ont proposé des versions de codeur n'ayant aucune multiplication Ces versions peuvent tre classées en deux catégories Ceux de la premlire catégorie exigent que la représentation binaire de Ai soit toujours d'une certaine forme n Ils en profitent pour remplacer les multiplications par d'autres opérations plus simples Celle de la seconde catégorie utilise le principe de consultation z o de table Nous décrivons ces méthodes maintenant. SP 7644 DB Nous commencons avec la première categorie Ainsi différents articles de Jorma Rissanen et K M Mohiuddin intitulé "A Multiplication-Free Mutlialphabet Arith- metic Code" (IEEE Transactions on Communications, 37 ( 2): 93-98, 1989), de Dan Chevion, Ehud Karnin et Eugene Walach intitulé "High Efficiency, Multiplication Frce Approximation of Arithmetic Codlng" (Proceedlngs of the IEEE Data Compression): dans les deux autres méthodes, en supprimant des multiplications, ils introduisent une nouvelle complication. De plus, dans chacune de ces méthodes, les valeurs possibles de Ai ne sont pas distribuées uniformément dans leur plage admissible I Ceci conduit à une inefficacité 1 O dans le codage En augmentant g A pour ces méthodes on n'obtient qu'une amélioration légère du rendement ou pas d'amélioration du tout, car les nouvelles valeurs que Ai peut atteindre sont groupées au voisinage de 1/2 dans le cas de Chevion, Karnin et Walach, ou au voisinage de 1 dans le cas de Tong et Blake (On ne peut pas augmenter MA dans le cas de Rissanen et Mohiuddin) L'approche de la seconde catégorie de solutions de ce problème consiste à mettre à jour l'état du codeur par une consultation de table. Remarquons que l'état du codeur, comme décrit par les équations ( 3) et ( 4), est tout à fait déterminé par les bits des quantités Ai et Ci Ces équations expriment comment mettre à jour cet état, en codant le symbole si et en produisant le bloc Bi Écrivons Z 5 2 o pour les bits qui représentent l'état courant du codeur (c'est à dire les bits de Ai et Ci), et Zi+l pour leur prochaine valeur On peut mélanger les deux équations ( 3) et ( 4) pour obtenir SP 7644 DB (Bi, Xi, Z,+ 1) = h(si, Z) ( 3) o la fonction h représente toutes les tapes 1 à 7 ci-dessus. Ainsi, les auteurs Paul G Howard et Jeffrey Scott Vitter, dans leur article intitulé "Practical Implementations of Arithmetic Coding" (dans le livre Image and Text Compression, Kluwer Academic Publishers, Boston, 1992, pages 85-I 12), ont proposé l'implémentation d'un codeur arithmétique o une telle fonction h est reprcsente par une table Pour coder un symbole si, on prend le symbol et l'état du codeur Zi, on consulte la table, et on y trouve le bloc Bi, sa taille Xi, et le nouvel état du codeur, Z, 1. Pourtant, cette méthode présente un défaut important: la taille d'une telle table, en bits, est: + x + gz) 2 s+ 4 Z Ce nombre grandit à une vitesse superexponentielle en g Z Donc à l'exception du cas o lZ est petit, ce méthode n'est pas applicable De plus, on voudrait avoir une valeur de lZ assez grande, pour les raisons suivantes. Tout d'abord, notons que le nombre des bits d'entrée pour l'équation ( 5) est 1 5 NS+ OZ = S + 24 2 + Maintenant nous rappellons que chaque quantitép(s) ou P(S) est un nombre réel entre O et 1, qu'on doit représenter sur p bits Pour bien comnpresser le flux d'entrée, la distribution de probabilités doit tre non uniforme De plus, cette non uniformité doit se refilter dans les valeurs de probabilité qui servent au calcul. Bien entendu, on n'a aucun contrôle sur le contenu du flux d'entrée, Mais, si l'on a 2 O une distribution favorable, on doit être en mesure, afin de l'exploiter, de représenter les nombres qui sont juste lnf 6 rleurs à 1, ainsi que ceux qui sont juste supérieurs à O Ainsi, il est souhaitable d'avoir lp aussi grand que possible de manière à pouvoir SP 7644 DB représenter la plage des probabilités la plus large possible. En fait, Howard et Vitter connaissent ce problème, et Introduisent d'autres idles pour le résoudre Mais leur solution est spécialisé au cas d'un alphabet binaire, qui ne comprend que deux symboles Notre invention traite la cas d'un multialphabet. Exposé de l'invention La présente invention concerne un procédé de mise à jour de la taille de l'intervalle dans le codage arithmétique, caractérisé par le fait qu'on sélectionne un ensemble de valeurs A = (AlOl, Aile,, Alr 1 lj}, i O et que l'on maintient la taille de l'intervalle comme un indice Wi dans cet ensemble. On peut représenter ces valeurs à n'importe quelle précision. Pour construire un codeur arithmétique utilisant cet indice Wi autant que la valeur Ai, on remnplace l'équation ( 3) par l'6 quation: (Wi+,, Xi, Ri) = "(s, W 1). 1 5 La fonction f' est mdmoris&e dans une table Une seule référence à cette table remplace tous ces opérations: à partir de si on détermnine p(si) et P(si); à partir de Wi, on détermine AlWil; on calcule p(Si) AlWi J et Ri = P(si) AlWil; on détermine le décalage Xi necessaire pour repr 6 senterp(svi) AlWi l 2 Xi dans 2; on détermine Wil,1 SP 7644 DB de telle sorte que AlWi+ 1 l soit le meilleur représentantde p(si) 'AlWil 2 xi; on revient à Wi+l, Xi et Ri. Dans une première variante de réalisation la table est calculée à l'avance. Dans une seconde variante de réalisation la table est calculée de façon dynamique. Comme on ne traite que la mise à jour de la taille d'intervalle par la méthode de référence à table, on évite le problème de Howard et Vitter, cité plus haut: le nombre de bits d'entrée de fonctionfn n'est que fs + NW, une quantité qui est tout à fait ind Ependante de d. Comme on peut choisir les valeurs de l'ensemble 4 on peut les distribuer O uniformément dans la rang IR, est donc éviter la perte de taux de compression portée par les méthodes de Rissanen et Mohiuddin, de Chevion, Karnin et Walach, et de Tong et Blake. Comme on traite la quantité Wi, de largeur #W bits, autant que Ai, de largeur IA bits, on peut arriver à une table plus petite qu'une implementation par table de la fonctionf 1 5 de l'équation ( 3). L'invention permet d'améliorer le rendement du codage d'agencements non adap- tatifs pour le codage arithrnmtique à grande vitesse en améliorant le rendement dans la taille d'intervalle actualis E La présente Invention permet à la fois une plus grande vitesse et une compression 2 o plus efficace des données par la technique de codage arithmétique bien connue Elle peut constituer la base d'un produit matériel ou logiciel destiné à la compression de SP 7644 DB 1 1 données Ce produit peut étre utilisé, par exemple, pour la compression de donnée&s devant être transmises sur un canal de communication, ou être stockées dans un système de fichiers. Un algorithme simple pour le codage arithmétique nécessite deux multiplications pour chaque symbole cod E L'invention supprime l'une et l'autre des multiplications et atteint une efficacité de compression supérieure aux méthodes précédentes sans multiplications. Brève description des dessins * La figure 1 représente l'architecture d'un codeur arithméetique de l'art connue: i O a La figure 2 représente une unité de mise à jour de la taille de l'intervalle de l'art connu; * La figure 3 représente une unité de mise à jour de la taille de l'intervalle selon l'invention. Exposé détaillé de modes de réalisation Structure général d'un système pour le codage arithmétique La figure 1 représente l'architecture d'un codeur arlthmétique de l'art connu qui a pour objet de coder le symbole si. SP 7644 DB 1 2 Il comprend une unité de mise à jour de la taille d'intervalle 10, une unité de mise à jour de la valeur du code 11 et éventuellement un circuit tampon 12. L'unité de mise à jour de la taille d'intervalle 10 délivre deux signaux Xi et Ri à l'unité de mise à jour de la valeur du code 11 Une sortie de cette unité 10 reliée à un registre 13 permet tant de délivrer à une entrée dudit module le signal Ai Une sortie de l'unité 11 reliée à un registre 14 permet d'envoyer un signal Ci à une autre entrée de ce module 11 Le circuit tampon 13 reçoit sur ses deux entrées les signaux de l'unité de mise à jour de la valeur du code 1 à savoir Xi et Bi, pour délivrer un signal Tk. L'unité de mise à jour de l'intervalle 10 permet le maintien à jour de Ai dans le registre 13 A chaque étape de l'algorithme elle prend un nouveau symbole si et la valeur courante du registre 13 Elle génère le cumulande Ri le décalage Xi, et la nouvelle valeur Ai+l pour le registre Elle maintient donc à jour la taille de l'intervalle courant Ai De même, l'unité de mise à jour de la valeur du code I 1 permet le maintien à jour de Ci dans le registre 14 A chaque étape elle prend en compte le décalage Xi, i 5 le cumulande Ri et la valeur courante du registre 14 en produisant une nouvelle valeur pour Ri et un bloc de longueur variable Bl de taille 1 +Xi La valeur Xi, elle, n'est pas modifiée. Le circuit tampon de variable bloc 12 assemble la séquence de blocs de longueur variable dans des blocs de longueur fixe TA qui constituent la sortie du codeur. Fonction de l'unité de mise à Jour de la taille d'intervalle SP 7644 DB L'unité de mise à jour de la taille de l'intervalle de l'art connu 10, représentée à la figure 2, comprend un module de modelisation de probabilité 15 dont les deux sorties, délivrant les signaux p(si) et P(si), sont relies respectivement à un premier multiplieur 16 suivi d'un module de normalisation 18 pour délivrer le signal Xi et à un second multiplieur 17 délivrant le signal Ri Une sortie du module de normalisation 18 est reliée à une entrée de chaque multiplieur 16 et 17 au travers du registre 13. Cette unit 6 est un réalisation en materiel des étapes suivantes: 1 Obtenirp(si) et P(si) Calculer exactementp(si) Ai. 2 Déterminer le décalage Xi tel que p(vi) Ai 2 xi E XR. 1 o 3 Trouver l'approximation inférieur sur SA-bits la plus proche de p(si) Ai 2 Xi; ceci donne A+,. 4 Calculer exactement Ri = P(si) Ai. Dans l'unit de mise à jour de l'intervalle 10, représentée à la figure 2, à chaque cycle d'opération une nouvelle valeur peut être générée dans le registre 13 Dans cette unité, il y a une boucle qui part du registre à travers le premier muliplieur 16 et 1 'unite de normalisation 18 et qui retourne au registre 14. La présence de cette boucle impose une limite fondamentale à la vitesse de fonctionnement du circuit. Si l'on considère cette boucle, si ti est l'instant auquel Ai est mémorisé dans le 2 O registre 14, et ti +l l'instant auquel Ai +l est mémorisé dans le registre 14, la différence SP 7644 DB tt.l ti ne peut tre r&éduite en dessous du temps nécessaire au signal 1 électrique pour se propager au travers du premier mutliplieur 16 et l'unité de normalisation 18. On peut ainsi terminer le calcul en mémorisant une mauvaise valeur pour Ai, si la sortie de l'unité de renormalisation n'est pas alors stabilisée Ainsi cette unité a une vitesse de fonctionnement limitée par la taille des opérandes consid 6 rés: dans cette boucle, la vitesse dépend de p et A. Ainsi pour bien réaliser la compression de données il faut pouvoir représenter des valeurs p(si) et P(si) très proches de O ou 1; ce qui nécessite la valeur Op grande Mais pour que le circuit puisse fonctionner rapidement p doit être petit. On se trouve donc oblig 6 de faire un compromis entre un circuit rapide qui réallse une compression efficace et un circuit efficace qui fonctionne lentement. Exposé du principe fondamental de l'invention On propose de remplacer cette unité avec une seule référence à la memoire du système Comme cite plus haut, l'article de MM Howard et Vitter propose à peu près q 5 la mêmrne idée, mais pour la mise à jour de toute l'état du codeur Nous proposons aussi de consulter une table, stockée en memoire, mais que pour la mise à jour de la taille de l'intervalle, et en utilisant une representation non-arithrnétique pour la taille de l'intervalle La notion de représentation non-arithnmétique est une idée clef de l'invention que l'on va maintenant expliquer. Dans le proc&édé de l'invention, on sélectionne un ensemble de r valeurs 4 A- SP 7644 DB {Ar OI, AlIl,, Alr 1 l}, eton maintient la taille d'intervalle comme une indice Wi dans cet ensemble On appelle cette méthode une représentation non-arithmetique de la taille de l'intervalle Ccci permet de distribuer les valeurs uniformément à l'intérieur de la plage admissible et permet donc d'atteindre un taux de compression plus élevé. Ce procédé pourrait sembler réduire la vitesse du traitement de codage, étant donné que les multiplications et le recadrage doivent maintenant être précéd 6 S par une référence de table (destinée à convertir l'indice Wi en une valeur arithmétique Ai) et suivis par une recherche (destinée à reconvertir le produit de valeur approchée en un indice actualisé Wi t) On observe cependant que l'étape d'actualisation de 1 O l'intervalle peut 8 tre réalisée par une seule consultation de table qui effectue à la fois une actualisation de la taille d'intervalle et fournit le cumulande de le décalage En terme de symboles, cette opération peut être écrite par: (W+, Xi, Ri) =f(si, wi) ( 6) o f indique la référence à la table stockée un mémoire. 1 5 Ainsi, une seule consultation de table de f' remplace toutes ces opérations: à partir de si on détermine p(si) et P(si); à partir de Wi, on détermine AlWil; on calcule p( si) AlW,l et Ri = P(si) AlWil; on détermine le décalage Xi necessaire pour représenterp(si) AlWil 2 X dans R,; on détermine Wil de telle sorte que AlW,+ll soit le meilleur representant de p(si) AlWil 2 xi; on revient à Wil,, Xi et Ri Une 2 o caractéristique essentielle de l'invention consiste donc h ajouter un niveau d'indirection cc qui supprime les limitations qu'impose un agencement particulier quelconque pour la représentadtion des nombres D'ordinaire, ceci devrait imposer un certain coût de traitement supplémentaire à chaque cycle, d'abord pour déréfércnccr l'index puis pour exprimer le résultat calculé sous forme d'index Mais dans le procédé de l'invention, le coût est compensé par la création autonome de la table. La table peut être calculée à l'avance ou de façon dynamique S'il est envisageable d'utiliser des probabilités fixées, on peut calculer la table à l'avance, en utilisant les étapes vues plus haut Cela s'appelle une compression non-adaptative. En revanche, si l'on désire avoir un système qui puisse s'adapter aux changements des suites de symboles, on peut le réaliser en: * faisant un sous-échantillonnage de suite de symboles si; * les utilisant pour estimer le changement de probabilités; * recréant la table en utilisant les étapes cités plus haut, avec les nouvelles probabilités; 1 5 * stockant cette nouvelle table dans un autre secteur de RAM * consultant cette nouvelle table. Cette représentation non-arithm 6 tique de la taille d'intervalle permet une représen- tation particulièrement réduite de la table nécessaire L'adresse de table est constitu Ee comme un enchaînement du symbole courant si et de l'indice de taille d'intervalle Wi. SP 7644 DB Le nombre de bits utilisés pour représenter Wi est toujours lnférieur ou égal au nombre de bits utiliser pour représenter Ai. Comme la quantité d W peut ttre inf 6 rieure à MA, on peut obtenir une réduction sensible de la dimension de la table; bien que les équations ( 3) et ( 6) soient de formes identiques, la seconde ne nécessite que (W + X + 9 R) 22 s+ 9 W bits alors que la première nécessite (MA + IX + g R) 2 s+ 4. Enfin, étant donne qu l'on peut choisir librement un ensemble quelconque de representants, le rendement à cette méthode est en général supérieur ou égal à celui correspondant aux références citées précédemment puisqu'on peut utiliser comme 1 O représentants les valeurs admissibles Ai de l'un ou l'autre de ces agencements. Caractéristiques d'une mise en oeuvre de l'invention Dans un exemple de réalisation on met en oeuvre l'agencement du codeur de l'invention sur un coprocesseur reconfigurable Celui-ci est constitué d'un réseau de bascules programmables et de quatre bancs de RAM statiques, et d'un FIFO de 32 bits 1 5 de large servant d'interface à un calculateur central. Compte tenu de la structure de ce coprocesseur, on choisit d C = 16 On appelle p,,a, pour la probabilité représentable la plus petite, Si l'on souhaite coder un ensemble de symboles ASCII (à 256 caractères), on doit prendre ep > 8; toute valeur plus petite conduirait àp,,an > 1/128, ce qui rendrait au moins la moitié des symboles non codables Mais en prenant p = 8, ceci conduit àp(') = 1/256 pour chaque symbole, SP 7644 DB ce qui ne fournit aucune compression On pose p -= 12. Etant donné que chaque produit P(si) Ai doit être représenté suivant OC bits de telle sorte que lA + Ip c une vitesse de compression de 16,3 M Bytes/s. SP 7644 DB REVENDICATIONS 1 Procédé de compression de mise à jour de la taille de l'intervalle dans le codage arithmétique, caractérisé par le fait que a on sélectionne un ensemble de valeurs A = {AlOl, AlI 1 l,, Alr 1 l}, et on maintient la taille de l'intervalle comme un indice Wi dans cet ensemble à une seule consultation de table cffectue à la fois une actualisation de la taille d'intervalle et fournit le cumulande et le décalage en effectuant l'opération suivante (W 1,1 Xi, R) = f/(s, wi) o la fonction ô' est mise en oeuvre par une seule référence à la table, dans 1 O laquelle à partir de si on détermine P(Sj) et P(si); à partir de Wi, on détermine A lWil; on calcule p(si) AlWil et Ri = P(si) AlWil; on détermine le décalage Xi necessaire pour représenterp(si) À AlWil 2 X dans I; on détermine Wi+l de telle sorte que AlWi+il soit le meilleur représentant dcp(si) AlWil 2 XI'; on revient à Wi,1, Xi et Ri. 1 5 2 Procédé selon la revendication 1 caractérisé en ce que la table est calculée à l'avance. 3 Procédé selon la revendication 1, caractérisé en ce que la table est calculée de façon dynamique. SP 7644 DB