Brevet FR2837948A1 — publié le 20031003

PROCÉDÉ DE RÉALISATION DE DIVISIONS ENTIÈRES La présente invention concerne le domaine des calculs sur des nombres opérés par des moyens informatiques. L'invention concerne, plus particulièrement, la réalisation d'une opération de type division entière. Un exemple d'application de la présente invention est le traitement d'images numériques et, plus particulièrement, les calculs effectués sur des blocs d'image dans du codage fractal. Dans une telle application, l'image est découpée en blocs se chevauchant et différents calculs sont appliqués aux valeurs (niveaux de gris ou niveaux de couleur) des différents pixels codés numériquement. Une opération particulière qui est effectuée fréquemment dans le traitement d'images numériques et qui est gourmande en ressources de calcul est la division. Une telle division sert, par exemple, à effectuer des calculs de valeurs moyennes ou de variances sur des blocs de pixels. L'invention s'applique plus particulièrement à la réalisation de divisions dans des opérations itératives, c'est-àdire pour lesquelles au moins une partie du résultat d'une division précédente est réutilisée pour la division courante. C'est notamment le cas de l'exemple d'application au traitement d'images pour lequel, le fait que les blocs se chevauchent, conduit à ce que des opérations fassent intervenir des résultats d'opérations concernant un bloc précédent. La présente invention vise à proposer un procédé de calcul automatique de divisions entières qui permettent d'accélérer les calculs. L'invention vise également à proposer un procédé qui soit peu gourmand en termes de ressources informatiques et qui, plus particulièrement, économise du temps de cycle. L'invention vise également à proposer un procédé qui puisse s'appliquer quel que soit le dividende et le diviseur entiers, pourvu que le résultat recherché et exploité soit un entier. L'invention vise en outre à proposer un processeur intégré propre à mettre en oeuvre un tel procédé. Pour atteindre ces objets et d'autres, la présente invention prévoit un procédé de calcul automatique de plusieurs divisions entières par un même diviseur entier, de plusieurs dividendes entiers successifs, séparés les uns des autres d'un pas d'itération constant, inférieur ou égal au diviseur, caractérisé en ce qu'il consiste à sélectionner, dans une table d'incréments, en fonction d'un indice d' itération, un 0 ou un 1 à ajouter au résultat d'opération de l'itération précédente, le nombre de 0 dans la table d'incréments étant égal au diviseur moins 1. Selon un mode de mise en oeuvre de la présente invention, le nombre de 1 dans la table d'incréments est égal au pas d'itération. Selon un mode de mise en oeuvre de la présente invention, le pas d'itération est 1, l'indice d'itération étant réinitialisé à 1 modulo le diviseur. Selon un mode de mise en oeuvre de la présente invention, le procédé consiste à sélectionner l'indice d'itération dans une table d'indices contenant une succession de nombres entiers, la taille de la table d'indices étant égale à la taille d'incréments. Selon un mode de mise en oeuvre de la présente invention, le procédé comprend les étapes suivantes : créer une table d'incréments contenant div-1 valeurs nulles et un nombre de valeurs unitaires correspondant au pas d'itération, où div représente le diviseur ; initialiser un indice ; initialiser un résultat ; initialiser un dividende ; et exécuter en boucle la sélection d'une des div valeurs contenues dans la table d'incréments pour l'ajouter au résultat de l'itération précédente. Selon un mode de mise en oeuvre de la présente invention, le procédé comporte en outre les étapes suivantes : créer une table d'indices contenant div valeurs constituant une suite de nombres entiers de 1 à div-1+pas, où pas représentant le pas d'itération, la dernière valeur de la table étant l'unité ; et sélectionner l'indice de sélection de la valeur prise dans la table d'incréments à partir de la table d'indices. L'invention prévoit également un processeur intégré de calcul. Ces objets, caractéristiques et avantages, ainsi que d' autres de la présente invention seront exposés en détail dans la description suivante de modes de réalisation particuliers faite à titre non-limitatif en relation avec les figures jointes parmi lesquelles : la figure 1 représente, sous forme d'organigramme, un premier mode de mise en oeuvre de la présente invention ; et la figure 2 est un organigramme partiel d'une variante de l'invention. Pour des raisons de clarté, seules les étapes de procédé qui sont utiles à la compréhension de l'invention ont été représentées aux figures et seront décrites par la suite. En particulier, la réalisation d'opérations de base au moyen d'un système informatique est classique et ne fait pas l'objet de l'invention. On notera que celle-ci s'applique quel que soit le type d'outil informatique utilisé, la programmation d'un tel outil pour la mise en oeuvre de l'invention étant à la portée de l'homme du métier à partir des indications données dans la description qui suit. La présente invention tire profit de particularités des divisions entières auxquelles elle s'applique. L'invention tire notamment profit du fait que les divisions auxquelles elle s'applique sont des divisions qui font intervenir un index ou indice de boucle, c'est-à-dire qui font intervenir un calcul incrémentiel dans lesquelles deux divisions successives sont séparées l'une de l'autre d'un pas d'itération constant. Ce pas d'itération est inférieur ou égal au diviseur entier. Une caractéristique de la présente invention est d'utiliser une table d'incréments contenant des quantités à ajouter au résultat de la division précédente pour obtenir le résultat courant de la division entière. Une autre caractéristique de l'invention est que la taille (nombre de valeurs) de cette table correspond au diviseur. La figure 1 représente un organigramme d'un mode de mise en oeuvre du procédé de calcul automatique selon la présente invention. On suppose que la division à effectuer a pour dividende i, pour diviseur div, et pour résultats successifs j. En d'autres termes, j représente le résultat de la division entière opérée par l'invention à chaque étape de calcul. Les quantités i, j et div sont des entiers. On commence par enregistrer une table d'incréments tabinc propre à l'invention. Cette table d'incréments contient, par exemple, div éléments, c'est-à-dire un nombre d'éléments égal au diviseur entier des opérations à effectuer. Selon l'invention, toutes les valeurs de la table d'incréments sont 0, à l'exception de la dernière qui est 1. Puis, dans une première étape de division proprement dite (bloc 1 : i=0, j=0, in=l) , on initialise les différents compteurs et variables utilisés dans la mise en oeuvre du procédé de l'invention. Par exemple, on initialise le dividende i à 0, le résultat j à 0 ainsi qu'une variable d'indice in à 1. La variable in sert à sélectionner un des éléments de la table d'incréments en fonction de l'opération courante. L'étape suivante 2 est constituée par un test (i=imax?) afin de vérifier que le dividende i courant n'excède pas le dividende maximum à appliquer. Dans l'exemple d'application de la présente invention au traitement d'images, le dividende maximum correspond, par exemple, au nombre de pixels d'une ligne d'image. Puis, on incrémente (bloc 3, i=i+l) le dividende d'une unité ou, plus généralement, du nombre correspondant au pas d'itération des divisions à exécuter. Par la suite, on met en oeuvre (bloc 4, j=j+tabinc[in]) une étape caractéristique de l'invention consistant à sélectionner, dans la table d'incréments créée précédemment, le nombre correspondant à l'indice in courant. Lors de la première passe ou boucle, le nombre sélectionné est 0. Lors des boucles suivantes, ce nombre est encore 0 jusqu'à arriver à un indice égal au diviseur moins 1, où le nombre contenu dans la table d'incréments est 1. Par conséquent, le résultat de l'étape 4 donne 0 à la première passe ou boucle ainsi qu'à toutes les boucles suivantes, tant que le nombre de boucles n'a pas atteint le nombre égal au diviseur div. Alors, l'étape 4 incrémente le résultat j de 1. L'étape (bloc 5, in=in+l) suivant l'étape 4 à l'intérieur de la boucle courante consiste à incrémenter l'indice in en préparation de la boucle suivante. L'incrément correspond au pas d'itération, c'est-à-dire à l'écart entre deux dividendes successifs. Dans l'exemple de la figure 1 où le pas d'itération est égal à l'unité, on exécute ensuite un test 6 (in>inmax ? ) de façon à réinitialiser (étape 7, in=l) l' indice lorsque celui-ci a atteint le nombre maximal. Le nombre inmax correspond au diviseur div dans le mode de réalisation de la figure 1. Plus généralement, les étapes 5,6 et 7 correspondent à un incrément de l'indice in modulo le diviseur. Si l'indice ne correspond pas à la valeur maximale, on revient à l'étape 2 afin de tester la valeur du dividende i par rapport au dividende maximal et à l'incrémenter (étape 3) pour effectuer l'opération suivante. Si l'indice est supérieur à l'indice maximal (test 6), on réinitialise celui-ci avant de revenir, là encore, à l'étape 2 pour tester le dividende par rapport au dividende maximum. On voit que ce n'est que lorsque in=div-l, que l'incrément sélectionné dans la table d'incréments est l'unité 1. Cela revient à incrémenter le résultat j d'une unité. En prenant l'exemple d'une division par 3, la table d'incréments est {Or 0, 1}. Les résultats successifs de la division entière sont, en prenant une suite de dividendes entiers partant de 1 avec un pas d'itération unitaire, 0 (1/3), 0 (2/3), 1 (3/3), 1 (4/3), 1 (5/3), 2 (6/3), etc. En prenant un pas d'itération de 2, les résultats successifs sont 0 (1/3), 1 (3/3), 1 (5/3), 2 (7/3), etc. En prenant un pas d'itération de 3, les résultats successifs sont 0 (1/3), 1 (4/3), 2 (7/3), etc. Un avantage du recours à une table d'incréments est que cela simplifie considérablement les calculs à exécuter. En particulier, aucune division proprement dite n'est nécessaire. Or, ces divisions sont des séquences d'instructions particulièrement gourmandes en temps de cycle dans le traitement par un processeur de calcul. On notera que l'initialisation à 1 de la variable in aux étapes 1 et 7 pourrait être remplacée par une initialisation à 0 ou à n'importe quelle valeur (inférieure à div). La longueur de la table d'incréments tabinc est fonction de la valeur d'initialisation. Dans le cas d'une initialisation à 0, la longueur de la table tabinc est div+1. De plus, la valeur d'initialisation dépend bien entendu de la position, dans la boucle, de l'étape d'incrément 5 par rapport à l'étape de calcul 4. La figure 2 illustre, par un organigramme partiel, une variante de la figure 1 permettant de réduire encore le temps de boucle du procédé de l'invention. Pour cela, on cherche à supprimer le test 6 sur la valeur de l' incrément en remplaçant celui-ci par une table d'indices tabind dans laquelle vont être sélectionnés successivement les indices à utiliser dans l'étape 4. En figure 2, seule l'étape 4 et l'étape 9 (in=tabind[in]) remplaçant les étapes 5,6 et 7 de la figure 1 ont été représentées, les étapes 1,2, 3 et 8 étant reprises à l'iden- tique et les étapes 5, 6,7 étant supprimées. Selon ce mode de mise en oeuvre, on génère une table d'indices ayant, pour un pas d'itération de 1, une taille correspondant au diviseur div. Cette table d'indices contient dans ce cas successivement les entiers 1, 2, ..., div-1, puis la valeur 0. Par conséquent, en sélectionnant un indice, lors de l'étape 9 qui suit l'étape d'opération 4, on obtient successivement les indices à utiliser. La réinitialisation de l'indice intervenant par le dernier élément de la table d'indices. Dans l'exemple de la division par 3, par pas de 1, la table d'indices est {l, 2, 0}. Comme pour la table d'incréments tabinc, la longueur de la table d'indices dépend de la valeur d'initialisation de la variable in. Si la valeur d'initialisation est 0 plutôt que 1 ; la longueur de la table tabind est div+1. Un avantage du mode de mise en oeuvre illustré par la figure 2 est qu'il réduit encore le temps de boucle nécessaire à la réalisation de la division entière. Par conséquent, on accélère encore le traitement opératoire pour effectuer la division. Un avantage de la présente invention est qu'elle permet d'effectuer une division entière de façon particulièrement rapide sous forme logicielle, sans nécessiter le recours à des processeurs dédiés en logique câblés. Un autre avantage de l'invention est qu'elle est particulièrement simple à mettre en oeuvre et ne requiert, de façon logicielle, que des opérations simples. L'invention trouve un intérêt tout particulier dans le cas où les calculs sont mis en oeuvre dans un circuit intégré contenant le processeur de calcul et la mémoire (par exemple, de type ROM) stockant le programme à exécuter. Dans un tel cas, l'économie en termes de calculs et de capacité de stockage est particulièrement avantageuse. Dans l'exemple d'application de l'invention au traitement d'images numériques, l'invention présente un avantage tout particulier en ce qu'en accélérant le temps nécessaire à exécuter les divisions, elle accélère considérablement le traitement d'images sous forme logicielle. En particulier, l'invention permet un traitement en temps réel des images dans le cadre d'un affichage vidéo. Bien entendu, la présente invention est susceptible de diverses variantes et modifications qui apparaîtront à l'homme de l'art. En particulier, bien que l'invention ait été illustrée en relation avec un pas d'itération unitaire, on notera que celle-ci s'applique quel que soit le pas d'itération choisi, pourvu que celui-ci soit inférieur ou égal au diviseur. Une première solution préférée est d'étendre la longueur de la table tabinc (et tabind si elle existe. Sa longueur correspond alors à div-1+pas (ou div+pas en cas d'initialisation à 0), où pas représente le pas d'itération choisi (inférieur à div-1). Pour la table d' incréments, les "pas" dernières valeurs sont alors à 1. Une deuxième solution est de prévoir un test supplémentaire pour déterminer quand revenir au début de la table d'incréments. Le même raisonnement s'applique pour la table d'indices. L'adaptation de l'invention à une telle variante est à la portée de l'homme du métier à partir des indications fonctionnelles données ci-dessus. De plus, la mise en oeuvre pratique de l'invention par programmation d'un système informatique est également à la portée de l'homme du métier en adaptant les organigrammes indiqués aux figures 1 et 2 au langage de programmation utilisé. REVENDICATIONS 1. Procédé de traitement d'images numériques consistant à appliquer à des valeurs de pixels codées numériquement plusieurs divisions entières par un même diviseur entier (div), de plusieurs dividendes entiers successifs, séparés les uns des autres d'un pas d'itération constant, inférieur ou égal au diviseur, caractérisé en ce qu' il consiste à sélectionner, dans une table d'incréments mémorisée, en fonction d'un indice d'itération (in), un 0 ou un 1 à ajouter au résultat d'opération (j) de l'itération précédente, le nombre de 0 dans la table d'incréments étant égal au diviseur moins 1. 2. Procédé selon la revendication 1, caractérisé en ce que le nombre de 1 dans la table d'incréments est égal au pas d'itération. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que le pas d'itération est 1, l'indice d'itération (in) étant réinitialisé à 1 modulo le diviseur. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'il consiste à sélectionner l'indice d'itération (in) dans une table d'indices mémorisée contenant une succession de nombres entiers, la taille de la table d'indices étant égale à la taille d'incréments. 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce qu'il comprend les étapes suivantes : créer une table d'incréments contenant div-1 valeurs nulles (0) et un nombre de valeurs unitaires (1) correspondant au pas d'itération, où div représente le diviseur ; initialiser un indice (in) ; initialiser un résultat (j) ; initialiser un dividende (i) ; et exécuter en boucle la sélection d'une des div valeurs contenues dans la table d'incréments pour l'ajouter au résultat de l'itération précédente. 6. Procédé selon la revendication 5, caractérisé en ce qu'il comporte en outre les étapes suivantes : créer une table d'indices contenant div valeurs constituants une suite de nombres entiers de 1 à div-1+pas, où pas représentant le pas d'itération, la dernière valeur de la table étant l'unité ; et sélectionner l'indice (in) de sélection de la valeur prise dans la table d'incréments à partir de la table d'indices. 7. Processeur intégré de traitement d'images numériques, caractérisé en ce qu'il comporte des moyens pour mettre en oeuvre le procédé selon l'une quelconque des revendications 1 à 6.