Brevet FR2709892A1 — publié le 19950317

Procédé de compression et de décompression d'un flux de valeurs numériques hexadécimales codées en ASCII L'invention concerne un procédé de compression et de décompres- Sion de valeurs numériques. Ce procédé est particulièrement adapté à la transmission de don- nées entre un calculateur et un mobile par une liaison radiotélépho- nique série du type de celles que l'on rencontre dans les systèmes de radiotéléphonie mobile privés (dits "PMR"). Cette application, si elle est avantageuse, n'est cependant pas limitative et le procédé de l'invention pourrait s'appliquer à divers autres types de transmission de données numériques. Dans la présente description, le terme "données numériques" sera entendu au sens strict, c'est-à-dire correspondant à la représen- tation d'un nombre, à l'exclusion de la transmission de données alphanumériques non numériques telles que lettres, signes de ponc- tuation, caractères de commande, etc. Plus précisément. l'invention s'applique à la transmission de valeurs numériques hexadécimales (base 16), se présentant sous la forme d'une succession de valeurs appartenant à l'ensemble {0, 1, 9... 9, A, B....F}. Plus précisément encore, l'invention s'applique au cas particulier o ces valeurs numériques hexadécimales se présentent sous forme d'une suite d'octets contenant chacun le code ASCII, noté '0', '1', '2', 25... '9', 'A', 'B',... 'F', de la valeur numérique correspondante. Cette forme de codage est notamment employée, dans le domaine précité de la radiotéléphonie mobile, pour le téléchargement de mé- moires reprogranmmables, par exemple du type "flash EPROM", d'un radiotéléphone mobile. Ici encore, cette application n'est pas limita- tive et l'invention peut s'appliquer à d'autres types de données à transmettre. Du fait que l'on utilise pour la transmission des données une liai- son radio, il est important de pouvoir minimiser le temps de trans- mission, c'est-à-dire le temps d'occupation du canal radio utilisé. L'invention a précisément pour objet de réduire, au moyen d'un algorithme de compression/décompression particulier, le nombre d'octets à transmettre sur la liaison série et, par voie de conséquen- ce, la durée de cette transmission. On verra plus loin que la réduc- nion ainsi obtenue est supérieure à 40 %c, en conservant bien enten- du l'intégrité totale des données transmises. A cet effet, le procédé de compression de l'invention, qui opère sur un flux incident de valeurs numériques hexadécimales (0, 1, 2... 9. A, B,... F} se présentant sous forme d'une suite d'octets source contenant chacun le code ASCII {'0', '1', '', 9', A', 'B',... 'F'} de la valeur numérique correspondante, est caractérisé par les étapes con- sistant à: (a) pour chaque octet source, transposer les caractères ASCII ('A', 'B','C', 'D', 'E' et 'F'} respectivement en {':', ';', ' et'?') et laisser inchangés les caractères '0' à '9'; (b) extraire les quatre bits de poids le plus faible de chacun des octets obtenus à l'étape (a) pour donner un quartet représen- tant de façon univoque la valeur numérique hexadécimale initiale correspondante; et (c) concaténer les quartets successifs obtenus à l'étape (c) pour donner des octets codés résultants, en nombre (m) inférieur à celui (n) des octets source. De préférence, à l'étape (c), on concatène les quartets successifs par groupes de sept bits successifs et on insère entre chacun de ces groupes un bit séparateur de valeur fixe prédéfinie. L'invention concerne également le procédé de décompression as- socié, qui est caractérisé par les étapes consistant à: (d) discriminer du flux de données incident les quartets succes- sifs représentant la valeur numérique hexadécimale recher- chée correspondante, (e) associer à chaque quartet ainsi discriminé quatre bits 'x110' de poids plus fort de manière à obtenir un octet contenant un code ASCII. et (f) pour chaque octet de code ASCII obtenu à l'étape (e), trans- poser les caractères ASCII {':', ';', ' ' et'?') respective- ment en {'A', 'B','C', 'D', 'E' et 'F'} et laisser inchangés les caractères '0' à '9', de manière à obtenir un flux résultant de caractères ASCII ('0', 1', '2'... 9', 'A', B',... F'} représenta- tifs des valeurs numériques hexadécimales {0, 1, 2,... 9, A, B,... F} recherchées. D'autres caractéristiques et avantages de l'invention apparaî- tront à la lecture de la description détaillée ci-dessous, faite en réfé- rence aux dessins annexés. La figure 1 est un tableau donnant, conformément au code ASCII, la représentation binaire des données numériques à traiter par la procédé de l'invention. La figure 2 montre un ensemble de six octets de données, corres- pondant à six chiffres hexadécimaux, avant mise en oeuvre du pro- cédé de compression de l'invention. La figure 3 montre les données de la figure 2 sous forme compri- mée, après mise en oeuvre du procédé de l'invention. 0 Comme on l'a indiqué plus haut, le but de l'invention est de réali- ser une fonction de compression/décompression qui transforme une suite d'octets représentative de nombres hexadécimaux, plus exacte- ment représentés par une suite de chiffres codés en ASCII, en une autre suite d'octets qui ne contienne que les bits utiles avec inser- tion de bits de synchronisation, par exemple un bit à zéro tous les sept bits. Chaque octet de la suite de valeurs hexadécimales est donc codé par des caractères ASCII. Ainsi, la valeur hexadécimale "78" sera codée par les deux caractères consécutifs '7' et '8', la valeur "2F" par les deux caractères '2' et 'F', etc. Le code ASCII permet de coder sur sept bits 128 caractères al- phanumériques ou de contrôle différents, un bit supplémentaire étant généralement prévu pour servir de contrôle de parité. En ce qui concerne les valeurs concernées par la présente inven- tion, à savoir les caractères '0', '1', '2'... 9', 'A', 'B',... 'F', leur codage dans la table de concordance ASCII est donné figure 1: on voit que la représentation ASCII des chiffres O à 9 sera donnée par les v5 aleurs binaires 1100000 à 1101001, tandis que les lettres A à F seront représentées par les valeurs binaires 0011000 à 0010110 (sur le tableau de la figure 1, chaque ligne donne la valeur binaire des quatre bits de poids le plus faible b3, b2, bl et bO, tandis que chaque colonne donne la valeur binaire des bits de poids plus fort b6, b5 et b4; le bit de parité est le bit de poids le plus fort b7. Comme on le voit, pour discriminer les différentes valeurs con- cernées, il faudra analyser les sept bits b6 à bO, soit sept bits signifi- catifs pour coder seize valeurs différentes. La première étape du traitement de compression de l'invention va consister à transposer les caractères 'A' à 'F' pour donner respec- tivement les caractères ':', ';', ' ' et'?', de sorte que les bits b6, b5 et b4 seront toujours les mêmes et que l'on ne se trouvera plus en présence que de quatre bits significatifs, à savoir les bits b3, b2, bl et bO, pour coder les seize valeurs différentes, les bits b6, b5 et b4 étant alors toujours respectivement 1,1 et O quelle que soit la valeur numérique hexadécimale concernée. Une fois cette transposition effectuée, on va pouvoir procéder à la compression proprement dite des données. Celles-ci se présentent, avant compression, sous la forme illus- trée figure 2, à savoir une succession d'octets 01, 02,... Oi,... 06,... cooant chacun un caractère ASCII de la suite de nombres à transmettre. Comme on vient de l'exposer, la transposition de {'A', 'B', 'C', 'D', E' et 'F'} en {':', ';', ' ' et?'} permet de limiter les valeurs signi- ficatives au quartet de poids le plus faible I constitué des bits b3, b2, bl et bO, le quartet de poids le plus fort II étant constitué de bits non significatifs (bit b7 de parité et bits b6, b5 et b4 ayant une valeur constante 1, 1 et 0). La compression va consister à ne conserver que le quartet de poids le plus faible (quartet I) de chaque octet 01, 02,... et concaté- ner ces quartets successifs pour donner des octets codés résultants, en nombre inférieur a celui des octets source. La figure 3 donne la configuration de ces octets codés résultants 01, 0'2,... O'j,...s: ur cette figure, la notation "Oxby' signifie "bit y O de l'octet Ox de la suite d'octets illustrée figure 2" (après la transpo- sition préalable exposée plus haut). On choisit de placer un caractère de synchronisation à chaque octet résultant, par exemple en mettant à zéro le bit de poids le plus for: b'7 de chaque octet O'j. Il ne s'agit là cependant que d'un détail de conception non essentiel, et d'autres configurations peuvent être envisagées (un bit de synchronisation tous les deux octets, synchro- nisation par le dernier bit de chaque octet au lieu du premier, etc.), l'exemple donné du premier bit de chaque octet mis à zéro n'étant que purement illustratif. Comme on peut le voir, la compression a permis de réduire le vo- lume de données, pour six octets 01,... 06 de départ, à trois octets et demi 0'1,... 0'4. De façon générale, si l'on prévoit d'insérer un bit de synchronisation à chaque octet, le taux de compression sera de 12:7, soit 1,7 environ, ce qui correspond à une réduction du volume des données à transmettre de l'ordre de 42 %. En d'autres termes, on peut considérer que l'on a accru la propor- tion de bits utiles du flux de données, qui passe de 50 % de bits uti- les (4 bits sur 8) pour les données originelles 01, 02... à 87,5 % de bits utiles (7 bits sur S) pour les données sous forme comprimée 0'1, 0'2,.. On va maintenant donner un exemple détaillé d'algorithme de traitement permettant d'effectuer cette compression de données. Cet algorithme de compression proprement dit devra être pré- cédé, comme on l'a expliqué, d'une étape de transposition des carac- tères ASCII 'A', 'B'.'C'. D', 'E'et 'F' en ':', ';', ' ' et'?', respective- ment (cf. tableau de la figure 1). Cette transposition, ne pose aucune difficulté particulière de programmation et peut être réalisée soit par l'intermédiaire d'une table de correspondance, les différents ca- ractères ASCII étant alors considérés globalement, soit par analyse et modification éventuelle des différents bits de chaque caractère. L'algorithme de compression proprement dit va traiter un tam- pon de n octets (que l'on suppose donc préalablement transposés) contenant: un caractere de début, (n-2) octets de données (du type 01, 02,... de la figure 2) et un caractère de fin, et donne en sortie un tampon de m octets contenant: un caractère de début, (m-2) octets de données (du type 0'1. 0'2,... de la figure 3) et un caractère de fin. Cet algorithme général de compression sera présenté en méta- langage. La valeur POSITION BIT (Pb sur la figure 3) est un pointeur indiquant le numéro du prochain bit à écrire dans le tampon de sor- tie. Sa valeur est initialisée à 6, car on écrira de gauche à droite les différents bits de chaque octet résultant (du bit b'6 au bit b'0), le bit b7 étant toujours à zéro. La valeur INDEX SOURCE (Is sur la figure 2) est un pointeur indiquant le numéro de l'octet en cours d'extraction dans le tampon d'entrée. Sa valeur est initialisée à 1 (octet 01 sur la figure 2), la valeur O représentant le caractère de début, non significatif, du tam- pon d'entrée. La valeur INDEX CIBLE (Ic sur la figure 3) est un pointeur indi- quant le numéro de l'octet en cours d'écriture dans le tampon de sor- tie. Sa valeur est initialisée à 1 (octet O'1 de figure 3), la valeur O représentant le caractère de début, non significatif, du tampon de sortie. L'algorithme de compression des données est le suivant. Tant que octet lu <> caractère de fin TRAITEMENT Écriture caractères début et fin du tampon de sortie Fin tant que Proc TRAITEMENT Si (POSITION BIT)=6 alors TR6 Si (POSITION BIT)=5 alors TR5 Si (POSITION BIT)=4 alors TR4 Si (POSITION BIT)=3 alors TR3 Si (POSITION BIT)=2 alors TR2 Si (POSITION BIT)=i alors TR1 Si (POSITION BIT)=0 alors-TR0 Proc TR6 Si dernier caractère de l'octet source Incrémentation INDEX CIBLE Sinon Extraction bits b3 à bO de l'octet pointé par INDEX SOURCE Incrémentation INDEX SOURCE Écriture dans bits b'6 à b'3 de l'octet pointé par INDEX CIBLE 2 -+ POSITION BIT Proc TR5 Si dernier caractère ce l'octet zource 0 -+ bits b'5 à b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Sinon Extraction bits b3 à bO de l'octet pointé par INDEX SOURCE Incrémentation INDEX SOURCE Écriture dans bits b'5 à b'2 de l'octet pointé par INDEX CIBLE 1 -+ POSITION BIT Proc TR4 Si dernier caractère de l'octet source 0 -+ bits b'4 à b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Sinon Extraction bits b3 à bO de l'octet pointé par INDEX SOURCE Incrémentation INDEX SOURCE Écriture dans bits b'4 à b'l de l'octet pointé par INDEX CIBLE 0 -+ POSITION BIT Proc TR3 Si dernier caractère de l'octet source 0 --+ bits b'3 à b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Sinon Extraction bits b3 à bO de l'octet pointé par INDEX SOURCE Incrémentation INDEX SOURCE Écriture dans bits b'3 à b'0 de l'octet pointé par INDEX CIBLE 6 -- POSITION BIT Proc TR2 Si dernier caractère de l'octet source 0 -) bits b'2 à b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Sinon Extraction bits b3 à bl de l'octet pointé par INDEX SOURCE Écriture dans bits b'2 à b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Extraction bit bO de l'octet pointé par INDEX SOURCE Écriture dans bit b -i de l'octet pointé par INDEX CIBLE Incrémentation INDEX SOURCE -- POSITION BIT Proc TR1 Si dernier caractère de l'octet source 0 -+ bits b'l et b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Sinon Extraction bits b3 et b2 de l'octet pointé par INDEX SOURCE Écriture dans bits b'l et b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Extraction bits bl et bO de l'octet pointé par INDEX SOURCE Écriture dans bits b'6 et b'5 de l'octet pointé par INDEX CIBLE Incrémentation INDEX SOURCE 4 -- POSITION BIT Proc TR0 Si dernier caractère de l'octet source O -- bit b'0 de l'octet pointé par INDEX CIBLE 5. Incrémentation INDEX CIBLE Sinon Extraction bit b3 de l'octet pointé par INDEX SOURCE Écriture dans bit b'0 de l'octet pointé par INDEX CIBLE Incrémentation INDEX CIBLE Extraction bits b2 à bO de l'octet pointé par INDEX SOURCE Écriture dans bits b'6 à b'4 de l'octet pointé par INDEX CIBLE Incrémentation INDEX SOURCE 3 -- POSITION BIT On va maintenant décrire l'algorithme de décompression des données, qui opère de manière inverse, mutatis mutandis, de celui de l'algorithme de compression. Cet algorithme de décompression proprement dit devra être sui- vi, comme on l'a expliqué, d'une étape de transposition inverse des caractères, afin de retrouver le codage ASCII normalisé (cf. tableau de la figure 1). Cette transposition inverse, tout comme la trans- position directe, ne pose aucune difficuike particulière de program- mation et ne sera pas décrite en détail. La structure des données de départ est celle de la figure 3, à sa- voir une série d'octets contenant des caractères comprimés. La struc- ture d'arrivée est celle de la figure 2, à savoir un tampon de m octets contenant des caractères décomprimés. La valeur POSITION BIT est un pointeur indiquant le numéro du prochain bit à écrire dans le tampon de sortie. Sa valeur est ini- tialise - à 7, car on écrira de gauche à droite, du bit b7 au bit bO. La valeur INDEX CIBLE est un pointeur indiquant le numéro de l'octet en cours d'écriture dans le tampon de sortie. L'initialisation de cette valeur dépend de l'endroit o l'on veut écrire les données reçues, et correspond par exemple à l'adresse de début d'une zone de mémoire RAM ou flash EPROM, etc. Tant que octet lu <> caractère de fin TRAITEMENT Écriture caractères début et fin du tampon de sortie Fin tant que Proc TRAITEMENT Si (POSITION BIT)=7 alors TR7 Si (POSITION BIT)=6 alors TR6 Si (POSITION BIT)=5 alors TR5 Si (POSITION BIT)=4 alors TR4 Si (POSITION BIT)=3 alors TR3 Si (POSITION BIT)=2 alors TR2 Si (POSITION BIT)=1 alors TR1 Si (POSITION BIT)=0 alors TR0 Proc TR7 Décalage de i position vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE 0 - POSITION BIT Proc TR6 Extraction bit B7 de l'octet pointé par INDEX CIBLE Ecriture dans position du tampon pointée par INDEX CIBLE du bit B7 et de l'octet reçu Incrément INDEX CIBLE 7 -> POSITION BIT Proc TR5 Extraction bits B7 et B6 de l'octet pointé par INDEX CIBLE Écriture dans position du tampon pointée par INDEX CIBLE des bits B7 et B6 et de l'octet reçu, décalé de 1 position vers la droite Incrément INDEX CIBLE il Décalage de 7 positions vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE 6 -- POSITION BIT Proc TR4 Extraction bits B7 à B5 de l'octet pointé par INDEX CIBLE Écriture dans position du tampon pointée par INDEX CIBLE des bits B7 à B5 et de l'octet reçu, décalé de 2 positions vers la droite Incrément INDEX CIBLE Décalage de 6 positions vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE - POSITION BIT Proc TR3 Extraction bits B7 à B4 de l'octet pointé par INDEX CIBLE Écriture dans position du tampon pointée par INDEX CIBLE des bits B7 à B4 et de l'octet reçu, décalé de 3 positions vers la droite Incrément INDEX CIBLE Décalage de 5 positions vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE 4 -- POSITION BIT Proc TR2 Extraction bits B7 à B3 de l'octet pointé par INDEX CIBLE Écriture dans position du tampon pointée par INDEX CIBLE des bits B7 à B3 et de l'octet reçu, décalé de 4 positions vers la droite Incrément INDEX CIBLE Décalage de 4 positions vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE 3 POSITION BIT Proc TR1 Extraction bits B7 à B2 de l'octet pointé par INDEX CIBLE Écriture dans position du tampon pointée par INDEX CIBLE des bits B7 à B2 et de l'octet reçu, décalé de 5 positions vers la droite Incrément INDEX CIBLE Décalage de 3 positions vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE 2 -+ POSITION BIT Proc TR0 Extraction bits B7 à B1 de l'octet pointé par INDEX CIBLE Écriture dans position du tampon pointée par INDEX CIBLE des bits B7 à B1 et de l'octet reçu, décalé de 6 positions vers la droite Incrément INDEX CIBLE Décalage de 2 positions vers la gauche de l'octet reçu Écriture dans position du tampon pointée par INDEX CIBLE 1 -+ POSITION BIT REVENDICATIONS 1. Un procédé de compression d'un flux incident de valeurs numériques hexadécimales (O, 1, 2... 9, A, B,... FI se présentant sous forme d'une suite d'octets source contenant chacun le code ASCII ('0', '1', '2',... 9', 'A', 'B',... 'F'l de la valeur numérique corres- pondante, caractérisé par les étapes consistant à: (a) pour chaque octet source (01, 02,... Oi,... On), transposer les caractères ASCII {'A', 'B', 'C', 'D', 'E' et'F'} respectivement en {':', ';', ' ' et'?') et laisser inchangés les caractères 'O' à '9'; (b) extraire les quatre bits de poids le plus faible (Oib3, Oib2, Oibl, OibO) de chacun des octets obtenus à l'étape (a) pour donner un quartet (I) représentant de façon univoque la valeur numérique hexadécimale initiale correspondante; et (c) concaténer les quartets successifs obtenus à l'étape (c) pour donner des octets codés résultants (O'1, 0'2,... O'i,... O'm), en nombre (m) inférieur à celui (n) des octets source. 2. Le procédé de la revendication 1, dans lequel, à l'étape (c), on concatène les quartets successifs par groupes de sept bits successifs (b'6... b'O) et on insère entre chacun de ces groupes un bit sépara- teur (b'7) de valeur fixe prédéfinie. 3. Un procédé de décompression d'un flux de valeurs numériques hexadécimales codées par mise en oeuvre du procédé selon la reven- dication 1, caractérisé par les étapes consistant à: (d) discriminer du flux de données incident les quartets succes- sifs représentant la valeur numérique hexadécimale recher- chée correspondante, (e) associer à chaque quartet ainsi discriminé quatre bits 'x110' de poids plus fort de manière à obtenir un octet contenant un code ASCII: et (fi pour chaque octet de code ASCII obtenu à l'étape (e), trans- poser les caractères ASCII (':', ';', ' ' et'?') respective- ment en {'A', 'B','C', 'D', 'E' et 'F'} et laisser inchangés les caractères '0' à '9', de manière à obtenir un flux résultant de caractères ASCII {'0', '1', '2'... '9', 'A', 'B',... 'F'} représenta- tifs des valeurs numériques hexadécimales {0, 1, 2,... 9, A, B,... F} recherchées.