Brevet FR2847410A1 — publié le 20040521

CODEUR ARITHMETIQUE JBIG La présente invention se rapporte au domaine du codage d'image numérique, en particulier du codage d'image sans pertes, dont un des exemples est la norme JBIG. La présente invention se rapporte plus particulièrement à la partie du codage appelée codage arithmétique et au procédé de codage mis en oeuvre. L'art antérieur connaît déjà, par la demande de brevet américain US 5668737, un procédé de codage arithmétique parallélisé permettant de réduire le temps de codage. Un procédé de calcul de données à haute vitesse et de compression de données comprend un module d'entrée pour recevoir un flux de données d'entrée d'un port d'entrée. Un encodeur est couplé à un module d'entrée et effectue un codage arithmétique pour encoder le flux de données d'entrée. Un module de sortie fournit un flux de données encodées de l'encodeur à un port de sortie. Pendant le processus d'encodage, l'encodeur effectue une combinaison d'étapes de calcul en parallèle et en série sur les données du flux de données d'entrée. Le résultat est que le temps de cycle de calcul pour le processus d'encodage est réduit de façon significative. Ce procédé de l'art antérieur ne concerne que la partie spécifique au codage arithmétique. Ce codage est annexé de processus complémentaires qui peuvent également être parallélisés. Ce document ne concerne pas ces parties annexes. La présente invention entend remédier aux inconvénients de l'art antérieur en proposant un procédé de codage comportant une étape de renormalisation particulièrement optimisée. A cet effet, l'invention concerne dans son acception la plus générale un procédé de codage arithmétique par une architecture matérielle comprenant notamment un registre A contenant la taille de l'intervalle courant, un registre C contenant la borne inférieure de l'intervalle courant et un registre CX contenant le contexte nécessaire au codage arithmétique, et o la valeur contenue dans ledit registre A est renormalisée si elle est inférieure à une valeur prédéfinie caractérisé en ce que ladite renormalisation consiste à * calculer en parallèle N valeurs Ai, chaque valeur résultant de la multiplication de la valeur contenue dans le registre A par un entier; * déterminer la valeur Ai supérieure à ladite valeur prédéfinie et inférieure ou égale à toutes les valeurs Ai supérieures à ladite valeur prédéfinie; * enregistrer la valeur Ai déterminée à l'étape précédente dans le registre A. De préférence, ladite valeur prédéfinie est Ox8000. Avantageusement, lesdits entiers utilisés pour calculer les Ai sont des multiples croissants de 2. Selon une variante particulière, le procédé conforme à l'invention comporte en outre une étape consistant calculer la nouvelle valeur du symbole le plus probable (MPS) du registre CX en effectuant une opération de " OU EXCLUSIF " sur les deux valeurs suivantes: * la valeur de commutation correspondant à l'état du registre CX, et * la valeur du symbole le plus probable (MPS) du registre CX. On comprendra mieux la présente invention à l'aide de la description, faite ci-après à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux figures annexées: - La figure 1 représente le mécanisme de doublement des registres A et C; - La figure 2 illustre le procédé conforme à l'invention. Un codeur arithmétique standard comporte une première étape de subdivision d'intervalle. La subdivision d'intervalle selon la probabilité et de manière récursive est la base du codage arithmétique. Conceptuellement, une séquence de symboles d'entrée est associée à un nombre réel x sur l'intervalle (0,1) o le crochet à l'extrémité d'un intervalle signifie que la valeur extrême est incluse et la parenthèse signifie que la valeur extrême est excluse. On ne transmet alors plus la séquence originale mais l'expression binaire de x. La portion de (0,1) dans laquelle on sait que x est situé après avoir codé une séquence initiale de symboles est appelée intervalle de codage courant. Pour chaque entrée binaire, l'intervalle de codage courant est divisé en deux sous-intervalles dont les tailles sont proportionnelles aux probabilités relatives des occurrences de chaque valeur pour le symbole. Le nouvel intervalle de codage courant est le sous-intervalle associé à la valeur effectivement attribuée au symbole. Dans un codeur, la connaissance de l'intervalle de codage courant est contenue dans une variable donnant sa taille et une variable donnant sa base (plus petite valeur). Le flux de sortie est obtenu par la variable donnant la base. Dans la partition de l'intervalle courant en deux sous-intervalles, le sous-intervalle pour le symbole le moins probable (LPS) est placé audessus du sousintervalle pour le symbole le plus probable (MPS). Ainsi, quand le LPS est codé, on ajoute le sous-intervalle MPS à la base. Cette convention de codage requiert que les symboles soient reconnus comme soit MPS, soit LPS et non comme 0 ou 1. Par conséquent, la taille de l'intervalle LPS et la signification du MPS pour chaque symbole doivent être connues pour coder ledit symbole. Comme le flux de code pointe toujours sur un nombre réel dans l'intervalle de codage courant, le processus de décodage se rapporte à la question de déterminer, à chaque décision, quel sous-intervalle est pointé par la chaîne codée. Ceci est également fait récursivement en utilisant le même processus de subdivision d'intervalle que dans le codeur. Chaque fois qu'une décision est décodée, le décodeur soustrait au flux de code chaque intervalle ajouté par le codeur. Ainsi, le flux de code dans le décodeur est un pointeur sur l'intervalle courant relatif à la base de l'intervalle courant. Comme le processus de codage implique l'addition de fractions binaires plutôt que la concaténation de mots de code entiers, les décisions binaires les plus probables peuvent souvent être codées à un cot inférieur à un bit par décision. Il est possible de réaliser ces opérations de codage en utilisant l'arithmétique des entiers à précision fixe. Un registre A contient la taille de l'intervalle de codage courant et ce registre est normalisé de telle sorte qu'il est toujours contenu dans l'intervalle [Ox8000,OxlOOOO] o le préfixe " Ox " caractérise un entier hexadécimal. Si le résultat du codage d'un symbole A tombe temporairement sous la valeur Ox8000, on double ledit résultat le nombre de fois nécessaire pour qu'il soit supérieur ou égal à Ox8000. Ces doublements sont appelés " renormalisations ". Un deuxième registre C contient les bits du flux de code correspondant aux décisions d'intervalle précédentes. Le registre C est aussi doublé chaque fois que le registre A est doublé. Pour éviter une congestion du registre C, un octet est périodiquement retiré, ledit octet étant composé des bits de plus grands poids de C et placé dans une mémoire tampon extérieure. Le contenu de cette mémoire tampon ne peut être envoyé sans que d'éventuels reports de retenue ne soient effectués. Le mécanisme de doublement des registres A et C utilisé habituellement est illustré Figure 1. Dans ce mécanisme habituel, il convient de répéter la boucle autant de fois que nécessaire, ce qui peut s'avérer gourmand en temps, notamment lorsque l'intervalle choisi au pas précédent est celui correspondant au LPS, car il est alors de taille réduite par rapport à l'intervalle qui le précédait. Afin d'éviter le cot de temps, qui peut être important et qui est surtout non maîtrisé, le procédé selon l'invention propose de paralléliser cette étape afin de garantir un nombre de coups d'horloge maximal pour la réaliser. Le procédé selon l'invention, illustré figure 2, utilise une architecture comprenant une pluralité de modules de calcul placés en parallèle par rapport au flux de données entrant. La valeur du registre A est fournie en entrée de chacun desdits modules, simultanément. Chaque module de calcul réalise le calcul pour lequel il est programmé et fournit un résultat Ai. Les opérations réalisées par les modules de calcul sont de préférence une multiplication du registre A par un entier. Dans le cas d'un codage arithmétique JBIG, chaque module de calcul réalise une multiplication du registre A par un multiple de 2. On obtient ainsi N valeurs Ai. Un opérateur logique standard permet de déterminer quelle est la valeur Ai minimale, supérieure à seuil prédéfini par l'utilisateur. Ledit seuil est " arithmétique. On définit alors l'état du registre: ST[CX]. Cet état est une valeur comprise entre 0 et 113 et est codée sur sept bits. A chaque état ST[CX] du registre CX correspond une valeur de commutation SWTCH[ST[CX]]. Si SWTCH[ST[CX]] vaut 1, MPS[CX] est inversé. L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet. REVENDICATIONS 1. Procédé de codage arithmétique par une architecture matérielle comprenant notamment un registre A contenant la taille de l'intervalle courant, un registre C contenant la borne inférieure de l'intervalle courant et un registre CX contenant le contexte nécessaire au codage arithmétique, et o la valeur contenue dans ledit registre A est renormalisée si elle est inférieure à une valeur prédéfinie, caractérisé en ce que ladite renormalisation consiste à * calculer en parallèle N valeurs Ai, chaque valeur résultant de la multiplication de la valeur contenue dans le registre A par un entier; * déterminer la valeur Ai supérieure à ladite valeur prédéfinie et inférieure ou égale à toutes les valeurs Ai supérieures à ladite valeur prédéfinie; * enregistrer la valeur Ai déterminée à l'étape précédente dans le registre A. 2. Procédé de codage arithmétique selon la revendication 1, caractérisé en ce que ladite valeur prédéfinie est Ox8000. 3. Procédé de codage arithmétique selon la revendication 1 ou 2, caractérisé en ce que lesdits entiers utilisés pour calculer les Ai sont des multiples croissants de 2. 4. Procédé de codage arithmétique selon l'une des revendications précédentes, caractérisé en ce qu'il comporte en outre une étape consistant calculer la nouvelle valeur du symbole le plus probable (MPS) du registre CX en effectuant une opération de " OU EXCLUSIF " sur les deux valeurs suivantes: * la valeur de commutation correspondant à l'état du registre CX, et * la valeur du symbole le plus probable (MPS) du registre CX.