Brevet FR2514969A1 — publié le 19830422

DISPOSITIF DE CODAGE D'UN TRAIN DE CARACTERES AVEC COMPRESSION DE L'INFORMATION La présente invention concerne le codage d'un train de caractères d'origine en un train de mots de code plus court, et le décodage des mots de code. Différents caractères d'origine peuvent apparal- tre avec différentes fréquences dans un train de caractè- res d'origine Le fait de coder sous forme de mots de code plus courts les caractères d'origine qui apparaissent plus fréquemment permet de réduire la longueur du train de mots de code Les fréquences relatives d'apparition de diffé- rents caractères d'origine peuvent changer au cours du temps. L'invention consiste de façon générale en un dis- positif destiné à coder un train de caractères d'origine en un train de mots de code, chacun des caractères d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui est susceptible de varier dans le temps Cha- cun des mots de code appartient à un groupe parmi un ensem- ble de groupes de mots de code et les mots de code dans les groupes respectifs comprennent des nombres respectifs différents de sous-mots Le dispositif comprend un codeur destiné à coder chacun des caractères d'origine sous la forme de l'un des mots de code, les caractères d'origine apparaissant le plus fréquemment étant codés sous la forme de mots de code ayant moins de sous-mots; et un sélecteur de taille de groupe destiné à remplacer par de nouveaux nombres les nombres de mots de codes appartenant respective- ment à certains des groupes, mais pas à tous, et à recalcu- ler les nombres de mots de code appartenant aux autres grou- pes, sur la base des nouveaux nombres, grâce à quoi une partie au moins du train de mots de code est raccourcie. Un autre aspect de l'invention fait intervenir un dispositif de contr 8 le destiné à compter le nombre d'appa ritions, dans le train de caractères d'origine, de chaque caractère d'origine dans un ensemble comprenant moins de la totalité des caractères d'origine, et un sélecteur de taille de groupe qui réagit au dispositif de contr 8 le en changeant les nombres de mots de code appartenant respecti- vement aux groupes, grâce à quoi une partie au moins du train de mots de code est raccourcie. Un autre aspect de l'invention porte sur un dispo- sitif dans lequel les mots de code appartiennent à un pre- mier, à un second ou à un troisième groupe de mots de code, et les mots de code qui appartiennent aux premier, second et troisième groupes comprennent respectivement un, deux et trois sous-mots Le dispositif comprend un codeur destiné à coder un premier ensemble des caractères d'origine sous la forme de mots de code appartenant au premier groupe, un second ensemble des caractères d'origine sous la forme de mots de code appartenant au second groupe, et un troisième ensemble des caractères d'origine sous la forme de mots de code appartenant au troisième groupe, les caractères d'ori- gine apparaissant le plus fréquemment étant codés sous la forme de mots de code ayant un plus petit nombre de sous- mots; et un sélecteur de taille de groupe destiné à charger les nombres de mots de code appartenant respectivement aux premier, second et troisième groupes, sous la dépendance de variations de la fréquence d'apparition, grâce à quoi une partie au moins du train de mots de code est raccourcie. Dans des modes de réalisation/avantageux,le sélec- teur de taille de groupe est connecté de façon à remplacer par un nouveau nombre le nombre de mots de code appartenant à l'un des groupes, et à recalculer les nombres de mots de code appartenant aux autres groupes, directement à partir du nouveau nombre. Un autre aspect de l'invention porte sur un appa- reil comprenant un dispositif de détermination de rang de fréquence d'apparition, destiné à affecter à chacun des caractères d'origine un rang correspondant à sa fréquence d'apparition relative estimée courante dans le train de caractères d'origine; un codeur destiné à coder en un mot de code ayant un sous-mot, conformément à un codé sélection- né, chacun des caractères d'origine,ayant un rang ne dépas- sant pas un premier nombre sélectionné, à coder sous la for- me d'un mot de code ayant deux sous-mots chacun des carac- tères d'origine ayant un rang supérieur au premier nombre et ne dépassant pas un second nombre, et à coder sous la forme d'un mot de code ayant trois sous-mots chacun des caractères d'origine ayant un rang supérieur au second nom- bre, le second nombre étant fixé par la valeur du premier nombre; un dispositif de contrôle destiné à compter le nombre d'apparitionsdans le train de caractères d'origine, de chaque caractère d'origine dans un ensemble ne comprenant pas la totalité des caractères d'origine; et un sélecteur qui fonctionne sous la dépendance du dispositif de contrôle de façon à mettre à jour le premier nombre pour lui donner une nouvelle valeur, lorsque la nouvelle valeur raccourcit une partie au moins du train de mots de code et de façon à recalculer le second nombre à partir du premier nombre. Dans des modes de réalisation préférés, l'ensemble ne comprenant pas la totalité des caractères d'origine com- prend les caractères d'origine pour lesquels le nombre de sous-mots dans les mots de code associés serait changé par des changements du premier nombre et du second nombre, et en particulier les caractères d'origine ayant des rangs égaux au premier nombre, au premier nombre diminué d'une unité, et à chaque nombre compris entre le second nombre moins le nombre de sous-mots dans l'alphabet de sous-mots, et le second nombre plus le nombre de sous-mots dans l'alpha- bet de sous-mots, diminué d'une unité; le dispositif de contrôle comprend un compteur destiné à compter en sens croissant à partir d'une valeur médiane pour chaque appari- tion des caractères d'origine ayant des rangs égaux au pre- mier nombre et au premier nombre diminué d'une unité, et à compter en sens décroissant pour chaque apparition des caractères d'origine ayant des rangs égaux à chaque nombre entre le second nombre moins le nombre de sous-mots dans l'alphabet de sous-mots, et le second nombre plus le nombre de sous-mots dans l'alphabet de sous-mots, diminué d'une unité, tandis que le sélecteur comprend un additionneur des- tiné à augmenter -le premier nombre d'une unité lorsque le compteur atteint une valeur supérieure et à diminuer le pre- mier nombre d'une unité lorsque le compteur atteint une valeur inférieure; le code sélectionné est changé lorsque le premier nombre est mis à jour pour prendre une nouvelle valeur; et il existe également un décodeur destiné à décoder le train de mots de code pour donner le train de caractères d'origine, le décodeur comprenant un dispositif de détermination de rang de fréquence d'apparition de déco- deur, destiné à déterminer pour chacun des caractères d'origine dans l'alphabet d'originele rang qui correspond à sa fréquence d'apparition relative estimée courante, et le décodeur détermine directement à par-tir des mots de code présents dans le train de mots de code quel est, parmi les codes qui peuvent être sélectionnés, celui qui a été utilisé pour le codage. Un autre aspect de l'invention porte sur un dispo- sitif destiné à coder un train de caractères d'origine en un train de mots de code, chacun des caractères d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui varie dans le temps Le dispositif comprend une mémoire de rang destinée à enregistrer le rang qui correspond à la fréquence d'apparition relative estimée courante de chaque caractère d'origine dans le train de caractères d'origine, et un dispositif de mise à jour de rang destiné à permuter le rang de chaque caractère d'origi- ne qui apparaît dans le train de caractères d'origine, avec le rang de celui des caractères d'origine qui a le rang immédiatement inférieur, à moins que le caractère d'origine qui apparaît dans le train ait le rang le plus faible possi- ble. Un autre aspect de l'invention porte sur un dispo- sitif qui comprend: un codeur destiné à coder sous la forme d'un mot de code ayant un sous-mot chacun des caractères d'origine ayant un rang de dépassant pas un premier nombre sélectionné, à coder sous la forme d'un mot de code ayant deux sous-mots chacun des caractères d'origine ayant un rang supérieur au premier nombre et ne dépassant pas un second nombre, et à coder sous la forme d'un mot de code ayant trois sous-mots chacun des caractères d'origine ayant un rang supérieur au second nombre, le second nombre étant fixé par la valeur du premier nombre; un modificateur de codage pour les mots à deux sous-mots, destiné à diviser par 16 tout mot de code ayant deux sous-mots et dont le dernier sous-mot est zéro, et à additionner le résultat à 15 plus le produit de 15 par le premier nombre, pour donner un mot de code révisé; et un modificateur de codage pour les mots de code à trois sous-mots, destiné à diviser par 16 tout mot de code ayant trois sous-mots et dont le dernier sous- mot est zéro, à additionner le résultat à 3573 plus le second nombre et, si le mot de code résultant est inférieur à 3856, à soustraire 16 du mot de code résultant, pour donner un mot de code révisé. L'invention permet un codage adaptatif rapide et. efficace d'un train de caractères d'origine pour donner un train de mots comprimé; le code change pour s'adapter à des changements de la fréquence d'apparition relative des caractères d'origine, afin de minimiser la longueur du train de mots de code; les adaptations de code sont effec- tuées rapidement et économiquement en changeant seulement une variable indépendante, à partir de laquelle les autres nombres qui interviennent peuvent 8 tre recalculés aisément et le décodeur peut s'adapter automatiquement à des codes qui changent, sur la base des mots de code reçus, sans nécessiter l'émission de signaux spéciaux de commutation de code du codeur vers le décodeur. L'invention sera mieux comprise à la lecture de la description qui va suivre d'un mode de réalisation, donné à titre d'exemple non limitatif La suite de la description se réfère aux dessins annexés sur lesquels: - La figure 1 est un schéma synoptique d'un système de codage-décodage. La figure 2 est un tableau représentant une séquence de codage caractéristique. La figure 3 est un schéma synoptique du codeur de la figure 1. La figure 4 est un schéma synoptique du décodeur de la figure 1. Les figures 5 A à 5 D sont des organigrammes du processus de codage. Les figures 6 A-6 D sont des organigrammes du pro- cessus de décodage. Structure d'ensemble et fonctionnement Sur la figure 1, le terminal 10 génère un train de caractères d'origine sur la ligne 12, sous forme de tensions, de courants, de fréquences ou d'autres paramètres représentant des éléments binaires Le codeur 14 reçoit les caractères d'origine sur son accès 16 et il les code en un train de mots de code binaires qui sont émis par l'accès 18 sur la liaison 20 Le nombre de bits dans le train de mots de code est généralement inférieur au nombre de bits dans le train associé de caractères d'origine La forme des mots de code permet d'effectuer un décodage indé- pendant pour obtenir le train initial de caractères d'origi- ne. La liaison 20 peut remplir diverses fonctions, parmi lesquelles la modulation et la démodulation, la commu- tation, l'enregistrement et la détection/correction des erreurs de transmission, mais, dans tous les cas, la liaison applique finalement à l'accès 22 du décodeur 24 une séquence de mots de code identique à celle qu'elle a reçue du codeur 14 Le décodeur 24 décode les mots de code pour donner un train de caractères d'origine identique au train reçu sur l'accès 16, et il les applique par l'accès 26 à la ligne 28 qui les transmet au terminal 30. Un autre train de données peut circuler simultané- ment dans le système dans la direction opposée, et pour ce train, le décodeur 24 fonctionne en codeur et le codeur 14 fonctionne en décodeur. Chaque caractère d'origine est l'un des 256 octects possibles Chaque mot de code est constitué par 1, 2 ou 3 sous-mots (appelés fragments) de quatre bits chacun. En général, la première étape dans le processus de codage consiste à ordonner les 256 caractères d'origine par ordre de fréquence d'apparition décroissante dans le train d'origine Le codeur conserve deux tables dont l'une est une liste de rangs (de O à 255) dans l'ordre des caractères d'origine, dans laquelle la iième rubrique est le rang du iieme caractère d'origine; et la seconde table est une lis- te des caractères d'origine (de O à 255) classés par rang,dans laquelle la iième rubrique estle caractère d'origine de rang i. Lorsqu'un caractère d'origine de rang r apparaît dans le train d'origine, les deux tables sont mises à jour de façon que le rang de ce caractère d'origine devienne r 1 (s'il n'est pas déjà égal à zéro), et de façon que le carac- tère d'origine qui avait le rang r 1 prenne le rang r. Les deux tables sont donc constamment mises à jour pour tra- duire les fréquences d'apparition relatives des caractères d'origine Le rang (avant la mise à jour des tables) de cha- que caractère d'origine apparaissant dans le train d'origine détermine le mot de code sous la forme duquel il sera codé. Pour effectuer le codage, les 256 caractères d'origine possibles sont divisés en trois groupes Les carac- tères d'origine ayant des rangs allant de zéro à un premier nombre (N 4 E) sont codés sous la forme de mots de code à un seul fragment, ceux dont les rangs vont de N 4 E à un second nombre (N 8 E 1) sont codés sous la forme de mots de code à deux fragments, et ceux dont les rangs vont de N 8 E à un troisième nombre (NL) sont codés sous la forme de mots de code à trois fragments. La détermination de N 4 E, N 8 E et NL est régie par l'égalité dite de Kraft: N 4 E + (N 8 E N 4 E) + NL N 8 E 1 NS NS NS dans laquelle NS est le nombre de fragments différents dis- ponibles et NL est un nombre sélectionné (ici 267) qui est au moins aussi grand que le nombre de caractères d'origine possibles Dans le cas présent, chaque fragment comporte 4 bits, ce qui permettrait normalement d'avoir 16 fragments différents, mais le fragment 0000 est spécifié comme étant un fragment illégal, ce qui donne NS 15, et l'égalité de Kraft devient: N 4 E N 8 E N 4 E NL N 8 E + + 3 15 15 Lorsque N 4 E est incrémenté d'une unité (c'est-à-dire lorsqu'un caractère d'origine de plus est ajouté au groupe codé sous la forme de mots de code à un seul fragment), l'égalité nécessite que NL N 8 E soit incrémenté de 15 et que N 8 E N 4 E soit décrémenté de 14 Inversement, si N 4 E est décrémenté d'une unité, NL N 8 E doit 8 tre décrémenté de 15 et N 8 E N 4 E doit être incrémenté de 14 Par consé- quent, si le caractère d'origine de rang N 4 E apparaît plus souvent que les caractères d'origine de rangs N 8 E 15 à N 8 E 1, N 4 E doit être incrémenté d'une unité (c'est-à-dire qu'un caractère d'origine supplémentaire doit être ajouté au groupe qui est codé sous la forme de mots de code à un seul fragment); et N 4 E doit 8 tre décrémenté d'une unité si le caractère d'origine de rang N 4 E i apparaît moins fré- quemment que les caractères d'origine de rangs N 8 E à N 8 E + 14, du fait que ceci raccourcira le train codé. On sélectionne N 4 E et N 8 E en comptant à partir d'une valeur médiane (par exemple 64), en sens croissant pour chaque apparition des caractères d'origine de rangs N 4 E 1 et N 4 E et en sens décroissant pour chaque apparition des caractères d'origine de rangs N 8 E-15 à N 8 E + 14. Lorsque ce compte dépasse un premier seuil (par exemple 128), N 4 E est incrémenté; et lorsque-le compte tombe en dessous d'un second seuil (par exemple 0), N 4 E est décrémenté Une fois que N 4 E est déterminé, la valeur de N 8 E est recalculée conformément à l'égalité de Kraft. L'étape suivante consiste à affecter chaque carac- tère d'origine à un mot de code Le processus est représenté sur la figure 2 qui montre un arbre ayant un nombre de niveaux (colonnes) 110 égal au plus grand nombre de fragments qui constituent un mot de code, soit trois dans ce cas Le premier niveau 115 comprend des branches 112 en nom- bre égal au nombre possible de fragments ( 16 dans ce cas) et chaque branche 112 du premier niveau représente soit un mot de code à 4 bits possible, soit un préfixe à 4 bits possible d'un mot de code à 8 bits ou à 12 bits Chaque branche 112 est désignée par un nombre, ne figurant pas entre parenthèses, qui indique sous forme décimale le numéro du fragment représenté par cette branche, et toute branche 112 à laquelle un caractère d'origine peut être affecté con- tient entre parenthèses le rang décimal de ce caractère d'origine Le second niveau 116 comprend 16 rameaux 118 pour chaque branche 112 dont le fragment fait fonction de préfixe Chaque rameau 118 est désigné de façon similaire par un numéro de fragment, ne figurant pas entre parenthèses, tandis que le rang du caractère d'origine affecté est indi- qué entre parenthèses Le troisième niveau 122 comprend de façon similaire 16 feuilles 124 pour chaque rameau 118 dont le fragment fait fonction de préfixe Chaque caractère d'origine affecté à une feuille 124 au troisième niveau est codé sous la forme d'un mot à trois fragments, comprenant les fragments représentés par la branche au premier niveau, le rameau au second niveau et la feuille au troisième niveau. Chaque branche, rameau ou feuille indiqué par une ligne en pointillés représente le fragment illégal 0000, ce qui fait que seuls 15 fragments différents sont réellement disponibles à chaque niveau 110 Les niveaux 110 de l'arbre de la figure 2 sont conçus de façon à procurer N 4 E branches disponibles au premier niveau, pour coder N 4 E caractères d'origine sous la forme de mots de code à un seul fragment, N 8 E N 4 E rameaux disponibles 116 au second niveau pour coder N 8 E N 4 E caractères d'origine sous la forme de mots de code à deux fragments, et NL N 8 E feuilles disponibles 124 au troisième niveau pour coder les caractères d'origine restants sous la forme de mots à trois fragments. Structure du codeur Comme le montre la figure 3, le codeur comporte une entrée 16 sur laquelle il reçoit le train de caractères d'origine à 8 bits, éventuellement à une cadence irréguliè- re. La mémoire Ml, 42, contient 256 éléments repré- sentant les 256 caractères d'origine possibles Le contenu des éléments de la mémoire Ml, 42 est fixé à des valeurs particulières comprises entre O et 255 La valeur r conser- vée dans le i ième élément de la mémoire Ml, 42, représente le rang r du iième caractère d'origine,en fréquence d'appa- rition dans le train de caractères d'origine Par exemple, si le 10 ième élément de la mémoire Ml, 42, contient la valeur 128, le caractère d'origine représenté par le 10 ième élément est estimé être le 128 ième caractère, par ordre d'apparition décroissant, dans le train d'origine. La mémoire M 2, 44, contient 256 positions repré- sentant les 256 rangs de fréquence possibles des caractères d'origine La valeur i conservée dans le r ime élément de M 2 représente le caractère d'origine i qui porte le rang r en ce qui concerne la fréquence d'apparition Par consé- quent, la mémoire Ml est une table des rangs dans l'ordre des caractères d'origine, tandis que la mémoire M 2 est une table des caractères d'origine dans l'ordre des rangs Si le lème ilème iièmeélément de Ml est r, le r élément de M 2 est i Il est très commode de fixer initialement à i les i ièmes élé- ments de Ml comme de M 2. Le registre N 4 E 46 contient le nombre N 4 E et le registre N 8 E 48 contient le nombre N 8 E N 4 E et N 8 E sont pris initialement égaux à des nombres entiers non négatifs, de façon que l'égalité de Kraft soit satisfaite, lorsqu'on-choi- sit pour NL la valeur 267, de la manière suivante 15 N 4 E + N 8 E222 Le registre CE 64, qui peut être fixé initialement à n'importe quelle valeur (par exemple 64), contient le compte sur la base duquel le nombre N 4 E est changé. L'unité arithmétique 60 effectue les calculs nécessaires Le train de mots de code qui résulte du codage est disponible sur l'accès de sortie 18 Le registre W 62 contient les fragments de chaque mot de code avant la trans- mission vers l'accès 18 Les registres Ri 54, R 2 56, Ai 52 et A 2 58 sont connectés de la manière représentée Chaque. composant du codeur 14 est connecté au bus de données 49, ainsi qu'au dispositif de commande de traitement de données , comme le montre la figure 3, et il est commandé par le dispositif 50 Les composants du codeur 14 sont réalisés sous la forme classique d'un microprocesseur et d'une mémoire. Fonctionnement du codeur Les résultats de chaque opération numérique décrite ci-dessous sont arrondis au nombre entier le plus proche. La description qui suit se réfère aux figures 3, SA, 5 B, 5 C et 5 D Lorsqu'un octet de caractère d'origine est reçu sur l'accès 16, le dispositif de commande 50 le trans- fère vers le registre Ai 52 Le caractère d'origine présent dans le registre Al 52 fait alors fonction de pointeur d'adresse pour la table Ml 42, qui fournit au registre Ri 54 le rang r du caractère d'origine Si le registre Ri 54 ne contient pas un O (c'est-à-dire si le caractère d'origine n'a pas le rang le plus bas, c'est-à-direla fréquence d'appa- rition la plus élevée), la valeur du rang (r) est transférée du registre Ri 54 vers le registre R 2 56 qui est ensuite décrémenté de 1 pour prendre la valeur (r-1) Le registre R 2 56 fait alors fonction de pointeur d'adresse pour la table M 2 44, et le caractère d'origine ayant le rang (r-1) est placé dans le registre A 2 58, qui fait fonction de pointeur d'adresse pour le registre MI 44 Le nombre présent dans le registre Ai 52 (c'est-à-dire le caractère d'origine) est chargé dans la position (r-1) de la table M 2 44 Le registre R 2 56 est alors incrémenté de 1 pour prendre la valeur r, et le nombre présent dans le registre Al 52 est enregistré dans la position r de M 2 44 La position Al de la table Ml 42 est décrémentée, et la position A 2 de la table Ml 42 est incré- mentée. ième Si on considère que le i élément de la table. Ml 42 contient le rang de caractère d'origine i, et si on considère que le r ième élément de la table M 2 44 contient le caractère d'origine de rang r, l'opération précédente a pour effet de placer le rang du caractère d'origine entrant dans le registre R? 54, de permuter le rang de ce caractère d'origine avec le rang du caractère d'origine de rang immé- diatement inférieur, et de mettre à jour de façon correspon- dante les tables MI 42 et M 2 43. Le contenu du registre R? 54 (c'est-à-dire le rang r du caractère d'origine entrant) est comparé aux contenus du registre N 4 E 46 et du registre N 8 E 48, et la valeur de CE est changée de la façon suivante Si r est égal à N 4 E ou N 4 E 1, CE est incrémenté Si r est inférieur à N 8 E + 15 et supérieur ou égal à N 8 E 15, CE est décrémenté. Sur la base des résultats des comparaisons précé- dentes entre les contenus des registres Ri 54, N 4 E 46 et N 8 E 48, les actions suivantes sont effectuées: Si le contenu de R? est inférieur à N 4 E (ce qui indique que le caractère d'origine entrant est compris dans le groupe à coder sous la forme de mots à un seul fragment), RI 54 est incrémenté de 1 et son contenu est transféré dans le registre W 62 (c'està-dire que le caractère d'origine est codé sous la forme d'un mot de code égal à un nombre supérieur d'une unité à son rang; ceci est représenté sur la figure 2, sur laquelle N 4 E 10 et le caractère d'origine de rang O est codé sous la forme du fragment 1, tandis que le caractère d'origine de rang 1 est codé sous la forme du fragment 2). Si le contenu du registre Rl est au moins aussi grand que N 4 E mais inférieur à N 8 E (c'est-à-dire que le carac- tère d'origine entrant doit être codé sous la forme d'un mot à deux fragments), la quantité (N 4 E) 15 + 17 + (N 8 E N 4 E 1) est additionnée au contenu du registre Rl 54 et elle est transférée vers le registre W 62 (pour devenir le mot de code à deux fragments potentiel) Si les 4 bits de faible poids du résultat sont égaux à O (c'est-à-dire qu'ils représentent le fragment illégal ( 0000)), la quantité w + 15 (N 4 E) + 15 est calculée et le résultat est transféré 1-6 vers le registre W 62 (pour devenir le mot de code à deux fragments final). Si le contenu du registre Rl est au moins aussi grand que N 8 E (c'est-à-dire que le mot de code aura une lon- gueur de trois fragments), la quantité 3829 est ajoutée au contenu du registre Rl 54 et le résultat est placé dans le registre W 62 Si les 4 bits de faible poids du résultat ne sont pas égaux à O (c'est-à-dire que le troisième fragment n'est pas illégal), le contenu du registre W 62 est divisé par 16 et le résultat est additionné à 3573 + N 8 E Si ce résultat est inférieur à 3856, on lui soustrait la quantité 16 Le résultat est transféré dans le registre W 62. L'opération de codage précédente a pour effet de charger un, deux ou trois fragments différents de zéro dans le registre W 62 en tant que mot de code, en fonction du rang du mot de source entrant Le fragment zéro n'est pas écrit de façon permanente dans le registre W 62 dans une position de poids plus faible que la position d'un fragment différent de zéro Le mot de code est ensuite émis à partir de l'accès de sortie 18, en commençant par le fragment différent de zéro ayant le poids le plus élevé. Enfin, si CE a atteint la valeur de seuil supérieu- re (SUP) ou inférieure (INF), il doit être restauré à la valeur médiane (MED) et N 4 E et N 8 E doivent être changés pour ajuster le nombre de caractères d'origine codés sous la for- me de mots de code à un fragment, à deux fragments et à trois fragments, afin de minimiser la longueur du train codé Ceci est accompli de la manière suivante. Si CE SUP et si N 8 E est supérieur à 15, CE est restauré à MED, N 4 E est incrémenté de 1 et N 8 E est décré- menté de 15. Si CE = INF et N 4 E n'est pas égal à zéro, CE est restauré à MED, N 4 E est décrémenté de 1 et N 8 E est incrémen- té de 15. SUP est le seuil supérieur mentionné précédemment et INF est le seuil inférieur mentionné précédemment SUP est supérieur à MED qui est lui-même supérieur à INF, et ces valeurs définissent la rapidité avec laquelle le codage est changé, lorsque les fréquences d'apparition relatives des caractères dans le train d'origine changent Pour des caractères d'origine à 8 bits, on utilise les valeurs sui- vantes: SUP = 128, MED, 64 et INF 0. Lorsque CE prend une valeur élevée, N 4 E est aug- menté, ce qui fait que davantage de caractères d'origine sont codés sous la forme de fragments uniques, et c'est l'inverse qui se produit lorsque CE prend une valeur faible. Ceci a pour effet de minimiser la longueur du train de mots de code lorsque la fréquence d'apparition relative des caractères d'origine change. A ce point, le codeur 14 attend l'apparition du caractère d'origine suivant, et le processus se répète. Une fois que chaque caractère d'origine a été traité, le codeur 14 contient des tables (Ml et M 2) qui représentent les rangs de fréquence de tous les caractères d'origine possibles, des nombres (N 4 E et N 8 E) qui détermi- nent les groupes de caractères d'origine qui seront codés 225 14969 sous la forme de mots de code à un, deux et trois fragments, un nombre CE qui mesure l'intérêt relatif de changer N 4 E et N 8 E, et un programme pour coder de façon déterminée le carac- tère d'origine reçu suivant, conformément à son rang et aux valeurs de N 4 E et N 8 E. Structure du décodeur Comme le montre la figure 4, le décodeur 24 com- porte un accès d'entrée 22, sur lequel il reçoit un train de mots de code, chacun d'eux comprenant un, deux ou trois fragments à 4 bits, un accès de sortie 26 sur lequel il fournit le train de caractères d'origine décodés, et une unité arithmétique 78 pour effectuer des calculs La table M 3 82 correspond à la table M 2 du codeur, les registres N 4 D 76 et N 8 D 77 correspondent aux registres N 4 E et N 8 E du codeur, le registre CD 80 correspond au registre CE du codeur et le registre S 74 contient une valeur qui indique si le fragment traité est le premier, le second ou le troi- sième fragment d'un mot de code Les composants du décodeur 24 sont connectés au bus de données 79, et ils sont comman- dés par le dispositif de commande de traitement de données Les composants du décodeur 24 sont réalisés sous la forme classique d'un microprocesseur et d'une mémoire. Fonctionnement du décodeur Avant le fonctionnement, la table M 3 est initiali- sée de façon à être identique à la table M 2 du codeur et les registres N 4 D, N 8 D et CD sont positionnés aux mêmes valeurs que les registres correspondants du codeur Le registre S est positionné initialement à zéro en préparation du traitement du premier fragment du premier mot de code entrant. La description qui suit se réfère aux figures 4, 6 A, 6 B, 6 C, et 6 D Lorsqu'un fragment est reçu sur l'accès 22, le dispositif de commande 70 le transfère vers le regis- tre R 3 72 et il effectue les actions suivantes, en fonction de la valeur qui est enregistrée dans le registre S 74 La valeur présente dans le registre S indique si le fragment en cours de traitement est un premier fragment, un second fragment ou un troisième fragment d'un mot de code. Si le registre S est à zéro, ce qui indique le pre- mier fragment dans un mot de code, le contenu du registre R 3 est comparé à la valeur présente dans le registre N 4 D 76 Si le contenu du registre R 3 est inférieur ou égal à N 4 D (c'est-à-dire que le mot de code a une longueur d'un seul fragment), le registre R 3 est décrémenté pour obtenir le rang du caractère d'origine; et dans le cas contraire le contenu du registre R 3 est transféré vers le registre S. Si le contenu du registre S est supérieur à O et inférieur à 16, ce qui indique le second fragment dans un mot de code, le contenu du registre S 74 est multiplié par 16 et le résultat est additionné au contenu de R 3 Si le (N 8 D N 4 D) contenu de R 3 est inférieur à 16 N 4 D + 17 + 15 la quantité 15 N 4 D + 15 est soustraite de R 3, le résultat est multiplié par 16 et il est ramené dans le registre R 3 Si le contenu de R 3 est inférieur à l 15 N 4 D + 17 + (N 8 D N 4 D) (N 8 D -N 4 D) 15 + * N 8 Dl, la quantité l 15 N 4 D + 17 + 1-5 est soustrai- te du contenu de R 3 et le registre S est mis à zéro, tandis que dans le cas contraire le contenu du registre R 3 est envo- yé vers le registre S. Si le contenu du registre S 74 est supérieur ou égal à 16; ce qui indique le troisième fragment d'un mot de code, le contenu de ce registre est multiplié par 16 et le résultat est additionné au contenu de R 3 Si le contenu de R 3 est supérieur à 3840, le nombre 16 lui est additionné, et si la valeur résultante de R 3 est inférieure à 3829 + N 8 D, la quantité 3573 + N 8 D est soustraite du conte- nu de R 3, le résultat est multiplié par 16 et ce résultat est enregistré dans le registre R 3 La quantité 3829 est ensuite soustraite du contenu du registre-R 3 et le registre S est mis à zéro. Lorsque ces opérations sont terminées, si la valeur présente dans S est égale à 0, ce qui indique qu'un nouveau mot de code va être reçu, la valeur présente dans le regis- 251 4969 tre CD doit être mise à jour pour la conformer à la valeur du registre CE, afin que le codeur et le décodeur travaillent avec les mêmes codes Ceci est accompli par le dispositif de commande 70 qui effectue les actions suivantes: Le contenu du registre R 3 (qui est le rang du caractère d'origine correspondant au mot de code qui vient d'être décodé) est comparé avec les contenus des registres N 4 D et N 8 D Si R 3 = N 4 D 1 ou R 3 = N 4 D, le registre CD 80 est incrémenté Si le contenu du registre R 3 est supérieur ou égal à N 8 D 15 et inférieur à N 8 D + 15, le registre CD est décrémenté. Le dispositif de commande 70 place ensuite, sur l'accès de sortie 26,le contenu de la position R 3 de la table M 3 82 (qui est le caractère d'origine de rang R 3) et, si R 3 est supérieur à zéro (c'est-à-dire si le caractère d'origine n'est pas celui de plus faible rang), les contenus des posi- tions R 3 et R 3 1 dans la table M 3 sont échangés, ce qui permute effectivement les rangs du caractère d'origine qui vient d'être traité et du caractère d'origine de rang immé- diatement inférieur, ce qui fait correspondre la table M 3 à la table M 2 44 du codeur 14. Le dispositif de commande 70 compare ensuite la valeur de CD avec des seuils SUP et INF identiques à ceux utilisés par le codeur 14, et il effectue les actions sui- vantes: Si CD = SUP et N 8 D est supérieur à 15, CD est positionné à MED, N 4 D est incrémenté de 1 et N 8 D est décré- menté de 15. Si CD = INF et N 4 D est supérieur à 0, CD est posi- tionné à MED, N 4 D est décrémenté de 1 et N 8 D est incrémenté de 15. Ces opérations ont pour effet de mettre à jour de façon interne les valeurs CD, N 4 D et N 8 D de façon qu'elles correspondent exactement aux valeurs respectives CE, N 4 E et N 8 E dans le codeur 14. Enfin, le caractère d'origine décodé présent sur 14969 l'accès de sortie 26 est appliqué à la ligne 28 Le dispositif de commande 70 attend l'apparition du mot de code suivant sur l'accès d'entrée 22, puis le processus se répète. Le décodeur 24 décode donc chaque mot de code reçu pour donner le caractère d'origine correspondant, en utili- sant le processus inverse de celui du codeur, basé sur les paramètres de décodage N 4 D et N 8 D et sur une liste M 3 de caractères d'origine, ordonnés par rang N 4 D et N 8 D sont changés lorsqu'une valeur CD dépasse des seuils SUP et INF, programmés à l'avance, qui sont les mêmes que ceux program- més dans le codeur 14 CD est mis à jour pour être identique à la valeur CE M 3 est mis à jour pour indiquer les rangs courants des caractères d'origine, par un processus identi- que à celui qui est utilisé dans le codeur 14 Aucune infor- mation autre que le train de caractères d'origine ne doit être transmise du codeur 14 vers le décodeur 24 pour coor- donner leurs activités respectives, du fait que l'informa- tion de codage nécessaire est implicitement contenue dans les mots de code eux-mêmes. Il va de soi que de nombreuses modifications peu- vent être apportées au dispositif décrit et représenté, sans sortir du cadre de l'invention Par exemple, les mots de code peuvent comprendre un groupe de mots de code constitués par plus de trois fragments Les points de sépa- ration entre les groupes de mots de code sont alors détermi- nés par plus de deux valeurs de séparation, conformément à l'inégalité de Kraft, et plusieurs de ces valeurs sont alors des variables indépendantes, tandis que les valeurs restan- tes sont déterminées une fois qu'on a fixé ces valeurs indépendantes. 251 4969 REVENDICATIONS 1 Dispositif destiné à coder un train de carac- tères d'origine en un train de mots de code, chacun des caractères d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui est susceptible de varier dans le temps, chacun des mots de code appartenant à un groupe parmi plusieurs groupes de mots de code, et les mots de code des groupes respectifs comprenant des nom- bres respectifs différents de sous-mots; caractérisé en ce qu'il comprend: un codeur ( 14) destiné à coder chacun des caractères d'origine sous la forme de l'un des mots de code, les caractères d'origine qui apparaissent le plus fréquem- ment étant codés sous la forme de mots de code ayant moins de.sous-mots; et un sélecteur de taille de groupe destiné à remplacer par de nouveaux nombres les nombres de mots de code appartenant respectivement à moins que la totalité des groupes, et à recalculer les nombres de mots de code appar- tenant aux autres groupes, sur la base des nouveaux nombres, grâce à quoi une partie au moins du train de mots de code est raccourcie. 2 Dispositif destiné à coder un train de carac- tères d'origine en un train de mots de code, chacun des caractères d'origine provenant d'un alphabet d'origine, cha- cun des caractères d'origine dans l'alphabet d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui est susceptible de varier dans le temps, cha- cun des mots de code appartenant à un groupe parmi plusieurs groupes de mots de code, et les mots de code qui se trouvent dans ces groupes comprenant des nombres respectifs différents de sous-mots; caractérisé en ce qu'il comprend: un codeur ( 14) destiné à coder chacun des caractères d'origine pour donner l'un des mots de code, les caractères d'origine appa- raissant le plus fréquemment étant codés sous la forme de mots de code ayant moins de sous-mots; un dispositif de contrôle destiné à compter le nombre d'apparitions, dans le train de caractères d'origine, de chaque caractère d'origine dans un ensemble comprenant moins que la totalité des carac- tères d'origine; et un sélecteur de taille de-groupe qui fonctionne sous la dépendance du dispositif de contrôle de façon à changer les nombres de mot de code appartenant res- pectivement aux groupes, grâce à quoi une partie au moins du train de mots de code est raccourcie. 3 Dispositif destiné à coder un train de caractè- res d'origine en un train de mots de code, chacun des carac- tères d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui est susceptible de varier dans le temps, chacun des mots de code appartenant à un pre- mier, un second ou un troisième groupe de mots de code, et les mots de code dans les premier, second et troisième groupes comprenant respectivement un, deux et trois sous- mots, caractérisé en ce qu'il comprend: un codeur ( 14) des- tiné à coder un premier ensemble de caractères d'origine sous la forme de mots de code-appartenant au premier groupe, un second ensemble des caractères d'origine sous la forme de mots de code appartenant au second groupe, et un troisième ensemble de caractères d'origine sous la forme de mots de code appartenant au troisième groupe, les caractères d'ori- gine qui apparaissent le plus fréquemment étant codés sous la forme de mots de code ayant moins de sous-mots; et un sélecteur de taille de groupe destiné à changer le nombre de mots de code appartenant respectivement auxpremier, second et troisième groupes, sous la dépendance de varia- tions de la fréquence d'apparition, grâce à quoi une partie au moins du train de mots de code est raccourcie. ou 3, 4 Dispositif selon la revendication 2 caractérisé en ce que le sélecteur de taille de groupe est connecté de façon à remplacer par un nouveau nombre le nombre de mots de code appartenant à l'un des groupes, et à recalculer les nom- bres de mots de code appartenant aux autres groupes, en pro- cédant directement à partir du-nouveau nombre. Dispositif destiné à coder un train de caractè- res d'origine en un train de mots de code, chacun des carac- tères d'origine provenant d'un alphabet d'origine, chacun des caractères d'origine dans l'alphabet d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui est susceptible de varier dans le temps, chacun des mots de code appartenant à un premier, un second ou un troisième groupe de mots de code, et les mots de code dans ces grou- pes comprenant respectivement un, deux ou trois sous-mots de même longueur, chacun des sous-mots provenant d'un alpha- bet de sous-mots; caractérisé en ce qu'il comprend: un dispositif de détermination de rang de fréquence d'appari- tion, destiné à affecter à chacun des caractères d'origine un rang qui correspond à sa fréquence d'apparition relative estimée courante dans le train de caractères d'origine; un codeur ( 14) destiné à coder sous la forme d'un mot de code ayant un sous-mot, conformément à un code qui peut être sélectionné, chacun des caractères d'origine ayant un rang qui ne dépasse pas un premier nombre qui peut être sélec- tionné, à coder sous la forme d'un mot de code ayant deux sous-mots chacun des caractères d'origine ayant un rang supérieur au premier nombre et ne dépassant pas un second nombre, et à coder sous la forme d'un mot de code ayant trois sous-mots chacun des caractères d'origine ayant un rang supérieur au second nombre, ce second nombre étant fixé par la valeur du premier nombre; un dispositif de contrôle destiné à compter le nombre d'apparitions, dans le train de caractères d'origine, de chaque caractère d'origine dans un ensemble comprenant moins que la totalité des caractères d'origine; et un sélecteur qui fonctionne sous la dépendance du dispositif de contrôle en mettant à jour le premier nombre pour lui donner une nouvelle valeur, lorsque cette nouvelle valeur raccourcit une partie au moins du train de mots de code, et en recalculant le second nombre à partir du premier nombre. 6 Dispositif selon la revendication 5, caractérisé en ce que ledit ensemble comprend les caractères d'origine pour lesquels le nombre de sous-mots dans les mots de code associés serait changé par des changements du premier nombre et du second nombre. 7 Dispositif selon la revendication 6, caractérisé en ce que ledit ensemble comprend les caractères d'origine ayant des rangs égaux au premier nombre, au premier nombre diminué d'une unité, et à chaque nombre compris entre le second nombre moins le nombre de sous-mots dans l'alphabet de sous-mots, et le second nombre plus le nombre de sous- mots dans l'alphabet de sous-mots, diminué d'une unit". 6 ou 7, 8 Dispositif selon la revendication 5, caractérisé en ce que le dispositif de contrôle comprend un compteur ( 64) destiné à compter à partir d'une valeur médiane, en sens croissant à chaque apparition des caractères d'origine ayant des rangs égaux au premier nombre et au premier nombre diminué d'une unité, et en sens décroissant à chaque appari- tion des caractères d'origine ayant des rangs égaux à chaque nombre compris entre le second nombre moins le nombre de sous-mots dans l'alphabet de sous-mots, et le second nombre plus le nombre de sous-mots dans l'alphabet de sous-mots, diminué d'une unité; et en ce que le sélecteur comprend un additionneur destiné à augmenter le premier nombre d'une unité lorsque le compteur atteint une valeur supérieure et à diminuer le premier nombre d'une unité lorsque le compteur atteint une valeur inférieure. 9 Dispositif selon la revendication 5, caractérisé en ce que le code qui peut être sélectionné est changé lorsque le premier nombre est mis à jour et prend une nouvel- le valeur. 231 'une quelconque des reven- Dispositif selon" dications 5 à 9, caractérisé en ce qu'il comprend en outre un décodeur ( 24) destiné à décoder le train de mots de code pour donner le train de caractères d'origine, ce décodeur comprenant un dispositif de détermination de fréquence d'apparition de décodeur, destiné à déterminer pour chacun des caractères d'origine dans l'alphabet d'origine, le rang qui correspond à sa fréquence d'apparition relative estimée courante; et en ce que le décodeur ( 24) détermine directement à partir des mots de code présents dans le train de mots de code quel est celui des codes pouvant être sélectionnés qui a été utilisé pour le codage. 11 Dispositif destiné à coder un train de carac- tères d'origine en un train de mots de code, chacun des caractères d'origine ayant une fréquence d'apparition dans le train de caractères d'origine qui varie dans le temps, caractérisé en ce qu'il comprend: une mémoire de rang (Ml) destinée à enregistrer le rang correspondant à la fré- quence d'apparition relative estimée courante de chaque caractère d'origine dans le train de caractères d'origine et un dispositif de mise à jour de rang destiné à permuter le rang de chaque caractère d'origine qui apparaît dans le train de caractères d'origine avec le rang du caractère d'origine de rang immédiatement inférieur, à moins que le caractère d'origine qui apparaît dans le train ait le plus faible rang possible. 12 Dispositif destiné à coder un train de carac- tères d'origine en un train de mots de code, chacun des caractères d'origine provenant d'un alphabet d'origine, chacun des caractères d'origine dans l'alphabet d'origine ayant une fréquence d'apparition dans le train de caractè- res d'origine qui varie dans le temps, ces caractères d'ori- gine étant ordonnés en fonction de leur fréquence d'appari- tion relative courante, chacun des mots de code appartenant à un premier, un second ou un troisième groupe de ces mots de code, et les mots de code dans ces groupes comprenant res- pectivement un, deux ou trois sous-mots de même longueur, chacun des sousmots appartenant à un alphabet de sous-mots, caractérisé en ce qu'il comprend: un codeur ( 14) destiné à coder sous la forme d'un mot de code ayant un sous-mot cha- cun des caractères d'origine ayant un rang qui ne dépasse pas un premier nombre qu'on peut sélectionner, à coder sous la forme d'un mot de code ayant deux sous-mots chacun des caractères d'origine ayant un rang supérieur au premier nom- bre et ne dépassant pas un second nombre, et à coder sous la forme d'un mot de code ayant trois sous-mots chacun des caractères d'origine ayant un rang supérieur au second nom- bre, ce second nombre étant fixé par la valeur du premier nombre; un modificateur de codage pour les mots de code à deux sous-mots, destiné à diviser par 16 tout mot de code ayant deux sous-mots et dont le dernier sous-mot est zéro, et à additionner le résultat à 15 plus le produit de 15 par le premier nombre, pour donner un mot de code révisé; et un modificateur de codage pour les mots de code à trois sous-mots, destiné à diviser par 16 tout mot de code ayant trois sous-mots et dont le dernier sous-mot est zéro, à additionner le résultat à 3573 plus le second nombre et, si le mot de code résultant est inférieur à 3856, à soustraire 16 du mot de code résultant, pour donner un mot de code révisé.