Brevet FR2124562A1 — publié le 19720922

La présente invention concerne un convertisseur perfectionné de code, destiné à un dispositif de traitement de données et comportant un circuit de traduction séquentielle qui convertit les signaux d'entrée en symboles de sortie qui dépendent des signaux 5 d'entrée présents et précédents et un circuit de traduction à longueur variable qui convertit les symboles d'entrée provenant du circuit de traduction séquentielle en signaux de sortie codés de longueur variable. l'utilisation de codes préfixes à longueur variable, en vue 10 de réduire au minimum la redondance des informations codées numériquement, est bien connue. Ces procédés sont décrits par D.A. Huffman dans "A Method for the Construction of Minimum Redundancy Codes", 40 Proc. IRE 1098,Septembre 1952. Il a été remarqué que les classes légèrement sous-optimales de ces codes (appelés ici "codes 15 systématiques") présentent des possibilités d'auto-synchronisâtion de très loin supérieures aux codes optimaux (Huffman). Cette propriété a été signalée dans "Efficient Error-Limiting Variable-Length Codes", IRE trans. 15-8, Juillet 1962, page 292. Il est également connu et il a été signalé que ceux des co-20 des séquentiels qui sont appliqués par des machines séquentielles sans perte d'information, telles que codeurs et décodeurs, présentent des possibilités notables d'auto-synchronisation, ainsi que le montre "Error-Limiting Coding Using Information-Lossless Sequential Machines" IEEE Trans. IT-10, Avril 1964» page 108. Dans 25 ce contexte, un code séquentiel implique un code dont les éléments dépendent des entrées précédentes aussi bien que des entrées présentes. Ce type de dépendance dans le temps se retrouve le plus généralement dans les codes différentiels simples qui représentent les différences entre les entrées actuelles et précéden-30 tes. Ces codages différentiels sont particulièrement utiles dans le cas d'informations qui contiennent d'importantes redondances, les signaux d'image par exemple, néanmoins, le codage différentiel conduit à une perte en contenu d'informations dans un message de données, à cause de 1*introduction d'informations de synchronisa-35 tion séparées. Le convertisseur de code selon l'invention élimine cet inconvénient de la perte d'informations dans un message. En effet, 72 04145 2 2124562 le circuit de traduction à longueur variable est agencé de manière à convertir les symboles d'entrée en un sous-groupe prédéterminé de mots de code préfixe à longueur variable. Un eircuit logique de modification réagit aux signaux d'entrée précédents et modifie 5 les valeurs sélectionnées des symboles de sortie du circuit de traduction séquentielle en en changeant l'ordre. En fonction des signaux d'entrée retardés, un circuit logique complémente sélectivement et permute les sous-groupes de mots de code de préfixe de longueur variable. 10 Les codeurs séquentiels à longueur variable selon l'inven tion sont réalisés de manière à fonctionner d'après des noyaux de codes préfixes à longueur variable. Un noyau est un groupe ou un sous-groupe de mots de code de préfixe ; un code de préfixe est un code dont aucun des mots ne se présente comme le début 15 d'un autre mot de code. Le cadrage de ces noyaux de code dans la matrice séquentielle d'entrée/sortie s'effectue de manière à présenter certaines propriétés qui tendent à augmenter au maximum 1'aut o-synchronis ation. Plus particulièrement, ce cadrage et les codeurs et détec-20 teurs correspondants sont étudiés de manière à être symétriques, c'est-à-dire que le cadrage total se ramène à une simple complémentation et une inversion des mots de code d'un seul ou d'un petit nombre de noyaux. En outre, tous les mots de code correspondant à une valeur d'entrée donnée sont formés de manière à se 25 terminer par le même chiffre, quelle que soit la sortie correspondante. Cette propriété facilite la détection de la fin de chaque mot de code et réduit ainsi le temps nécessaire à la resynchronisation lorsqu'une erreur s'est produite. Enfin, la plupart des mots de code sont choisis de manière à n'apparaître que dans un 30 nombre relativement faible de symboles et à éviter que chaque apparition corresponde à un symbole différent. Lorsque des codes sont formés de manière à présenter toutes ces propriétés, le résultat constitue un code séquentiel d'une haute efficacité, permettant une compression proche de la compres-35 sion optimale, susceptible d'une bonne auto-synchronisation, et dont le codage et le décodage ne présentent que très peu de complications. Du fait que les codes sont caractérisés par des trans 72 04145 3 2124562 formations simples (complètementations et inversions) des mots de code, les codeurs et décodeurs peuvent être réalisés avec des portes logiques, ET et OU-exclusif disposées en série avec des codeurs séquentiels courants. Ces codes sont d'une grande utilité 5 dans le cas de signalisation redondante, comme celle des signaux d'image de télévision. la présente invention combine donc avantageusement les possibilités de compression du codage différentiel avec les possibilités d'auto-synchronisation du codage séquentiel. Plus particu-10 lièrement, la présente invention réduit la redondance au minimum, tout en augmentant au maximum l'auto-synchronisation des convertisseurs de codes préfixes à longueur variable. l'invention sera décrite plus en détail en regard des dessins annexés à titre d'exemple nullement limitatif et sur les-15 quels : la figure 1 est un diagramme synoptique d'un codeur diffé-fentiel de type connu ; la figure 2 est un diagramme synoptique d'un décodeur dif-rérentiel destiné à être associé au codeur de la figure 1 ; 20 la figure 3 est un diagramme synoptique d'un codeur diffé rentiel, modifié selon la présente invention et comportant les circuits logiques de modification et de complémentation qui assurent l'auto-synchronisation ; la figure 4 est un diagramme synoptique d'un décodeur dif-25 férentiel modifié, destiné à être associé au codeur de la figure 3 ; la figure 5 est un schéma plus détaillé du codeur de préfixe représenté par la case 12' sur la figure 3 ; la figure 6 est un schéma plus détaillé du décodeur de pré-30 fixe représenté par la case 151 sur la figure 4 ; la figure 7 est un schéma détaillé d'un codeur simple à deux chiffres du type représenté sous sa forme générale sur la figure 3 ; la figure 8 est un schéma plus détaillé d'un décodeur sim-35 pie à deux chiffres représenté sous sa forme générale sur la figure 4 ; 72 04145 4 2124562 la figure 9 est un diagramme synoptique d'un circuit de codage dont le circuit de soustraction est incorporé dans le circuit logique de modification ; la figure 10 est un diagramme synoptique d'un codeur du 5 type représenté sur la figure 4 et dans lequel le circuit additionneur est incorporé dans le circuit logique de modification ; la figure 11 est un schéma détaillé du circuit logique de complémentation des circuits des figures 3, 4» 9 et 10 ; la figure 12 est le schéma détaillé du circuit logique com-10 biné de modification et de soustraction du codeur de la figure 9 j et la figure 13 est un tableau de différents codes de préfixes à longueur variable qui permettraient également de réaliser les codeurs et décodeurs, représentés sous leur forme générale sur les 15 figures 3 et 4. Avant de passer à la description détaillée des figures, il n'est pas inutile de revoir les définitions des termes particuliers qui seront utilisés. Un "code" est un ensemble de successions de chiffres (chif-20 fres de code) qui sont appelés chacune "mot de code". Un texte codé est formé d'un enchaînement de mots de code, et le codage consiste à faire correspondre des symboles sources S(i) à des mots de code ¥(i). Un code est préfixe si, et seulement si, aucun mot de code n'apparaît au début (préfixe) d'un quelconque autre mot 25 de code. Dans un texte en code préfixe, un mot de code peut être décodé aussitôt reçu, même s'il n'existe aucun marqueur inter-mot explicite. Un code est "exhaustif" si, et seulement si, chaque succession de chiffres de code constitue le préfixe d'un texte codé, 30 c'est-à-dire d'une succession de mots de code. Un code qui est décodable d'une manière univoque doit donc être un code préfixe s'il est exhaustif. Une succession de chiffres de code est une "séquence de synchronisation" pour un code donné si l'apparition de la fin de 35 cette succession dans un texte codé (correct) doit correspondre à la fin d'un mot de code (bien qu'il ne soit pas nécessairement un mot de code déterminé) indépendamment de ce qui précède cette succession. 72 04145 5 2124562 Il est connu, et Schtltzenberger et ses collaborateurs l'ont décrit dans "On An Application of Semi-G-roup Methods to Some Problems in Coding", IBB Trans. IT-2, Septembre 1956, page 47, que les codes préfixes les plus exhaustifs ont tendance à se re-5 synchroniser d'eux-mêmes lorsque la synchronisation est décrochée, par exemple après des erreurs arbitraires ou au démarrage. Aussi bien selon l'article précité que selon l'invention, la re-syn-chronisation est une propriété intrinsèque du code, grâce à laquelle aucune synchronisation extérieure n'est nécessaire. Après 10 une ambiguïté, la synchronisation résulte directement d'une séquence de synchronisation qui apparaît naturellement dans le texte codé. Le retard à la synchronisation I d'un code préfixe est défini par le nombre moyen de chiffres de code nécessaire pour que 15 la synchronisation puisse être assurée à la fin d'un mot de code (qui n'est pas nécessairement connu) suivant une ambiguïté totale. En supposant que 2~^ soit la probabilité de caractéristique Huffman pour chaque mot de code, d étant la longueur en chiffres du mot de code, le retard à la synchronisation est en fait la lon-20 gueur moyenne des séquences de synchronisation. Cette synchronisation à la fin d'un mot de code non spécifié est appelée synchronisation au premier étage. La synchronisation au second étage a lieu lorsque le texte codé est synchronisé a la fin d'un mot de code déterminé et connu. Le retard de synchronisation séquentiel-25 le J est le nombre moyen de chiffres de code nécessaire pour que la fin d'un mot de code connu se présente dans un état connu du code et il est égal à la longueur moyenne des séquences de synchronisation des codes séquentiels. Le "codage séquentiel" consiste à faire correspondre des 30 symboles S(i) à des mots de code W(i/j), le mot de code sélectionné dépendant du symbole S(j) codé précédemment ainsi que du symbole S(i) en cours de codage. Si le groupe de mots de code ¥ est un code préfixe pour chaque le mot de code est un code préfixe séquentiel. En ce qui concerne ces codes, une séquence de 35 synchronisation est une séquence de chiffres de code dont la fin doit correspondre à la fin d'un mot de code (qui peut être inconnu) résultant d'un symbole connu S(i), indépendamment de ce qui 72 04145 6 2124562 a précédé cette séquence, le décodage suivant est correct, quelle que soit l'ambiguïté initiale. la présente invention concerne des codeurs et des décodeurs adaptés à des classes particulières de codes préfixes séquentiels 5 qui présentent un degré élevé de compression dans leur codage et décodage et des propriétés excellentes d'auto-synchronisation. le tableau I ci-après donne un exemple simple permettant de mieux comprendre le codage séquentiel. TAB1EAÏÏ I \ S(I) i=00 01 10 il A B C D S(J) \ - j=00 A lrf(0) ' W(l) W(2) w(3) j=01 B w(3) w(o) w(i) W(2) j=10 C W(2) w(3) w(o) ¥(1) j=ll D W(l) W(2) w(3) ¥(0) 10 Dans ce tableau A, B, C, D représentent quatre symboles source S(i), i=00, 01, 10, 11, i étant le niveau du symbole. C'est un exemple de codage dans lequel le mot de code ¥(i/j) qui doit être émis est une fonction de la différence cyclique entre le niveau du symbole S(i) à coder (colonne) et le niveau du sym-15 bole 3(j) qui vient d'être codé (rangée) : ¥ (i/j) = ¥(k) où k = i-j( modulo 4). Il s'agit donc d'un codage par différence. Il faut noter que, quel que soit le choix du code [W(k)], il y a toujours une ambiguïté aussitôt qu'une erreur est commise. Si par exemple S(10) est décodé au lieu de S(Q1) par suite d'une faute 20 de transmission, le décodage suivant produira par conséquent S(i+1) au lieu de S(i), i+1 étant considéré modulo 4, tant que d'autres erreurs ne viennent pas compenser les erreurs initiales. la figure 1 représente un codeur différentiel destiné à coder dans le code du tableau I. Ce codeur comporte un circuit à 25 retard 10 dont le rôle consiste à retarder d'un intervalle le sym 72 04145 7 2124562 bole d'entrée i de manière à produire un symbole I>9s symboles i et 2. sont tous deux appliqués à un circuit soustracteur 11 qui extrait la différence i-j = k. Le groupe de symboles de différence k peut ensuite être codé dans un codeur à compression 12 5 qui tire parti des propriétés du codage différentiel pour compresser le train de données sortantes sur le fil 13. Selon une application particulière, le codeur 12 doit traiter un nombre réduit de chiffres de code, en raison des faibles valeurs de k. Ceci est dû bien entendu à la redondance des données d'entrée i, 10 par laquelle les symboles d'entrée changent relativement lentement et les différences k restent faibles. Il est cependant préférable que le codeur 12 sôit un codeur à longueur variable appliquant les codes Huffman optimaux, ou voisins des codes optimaux à longueur variable. 15 La figure 2 montre le diagramme synoptique d'un décodeur destiné à être associé au codeur de la figure 1. Les données codées sur le fil 13 de la figure 1 sont appliquées,après avoir été transmises par un circuit de transmission, à un décodeur à compression 15, par le fil 14. Le décodeur 15 est l'inverse du co- 20 deur à compression 12 et, en l'absence d'erreur, il rétablit les le codes de différences k sur/ fil 16. Ces codes de différence sont appliqués à un circuit additionneur 17 dont la sortie i est appliquée, par l'intermédiaire d'un circuit 18-de retard de symbole, à l'autre entrée du circuit additionneur 17. Ce dernier délivre 25 sur son fil de sortie 19, la somme des signaux 2 et k constituant le signal i d'information initiale appliqué au codeur de la figure 1 . La figure 3 montre le codeur différentiel de la figure 1, modifié selon la présente invention. Un circuit logique 21 de mo-30 dification et un circuit logique 22 de complémentation ont été ajoutés. Les éléments qui correspondent à ceux de la figure 1 sont désignés par les mêmes références numériques "prime". Le circuit logique 21 de modification est introduit dans le circuit des données entre le soustracteur 11' et le codeur 12', et il est 35 commandé par les signaux de sortie du circuit à retard 10'. Le circuit logique 22 de complémentation est connecté entre le co- • deur 12' et le fil de sortie 131• Il est également commandé par la sortie du circuit à retard 10'. Ainsi qu'il sera décrit plus 72 04145 8 2124562 en détail par la suite, le circuit logique 21 de modification et le circuit logique 22 de complémentation sont des circuits logiques numériques simples qui, lorsqu'ils sont introduits de la manière représentée sur la figure 3, dans un codeur différentiel, 5 produisent un code présentant une auto-synchronisation élevée. Cette auto-synchronisation est une propriété intrinsèque du code et aucune synchronisation extérieure n'a besoin d'être appliquée. La synchronisation résulte directement des séquences qui apparaissent naturellement dans le texte codé. \ 10 La figure 4 représente un décodeur différentiel modifié destiné au décodage des signaux provenant du codeur de la figure 3. Les éléments qui correspondent directement à ceux de la figure 2 sont désignés par les mêmes références numériques "prime". Un circuit logique 23 de "décomplémentation" est intercalé entre le 15 fil d'entrée 14' et le décodeur de préfixe 15*. Ce circuit est commandé par les signaux de sortie retardés du circuit à retard 18'. Le circuit logique 24 de "démodification" est introduit entre le décodeur de préfixe 151 et une entrée du circuit additionneur 17'• Il est également commandé par les signaux de sortie retardés 20 du circuit à retard 18'. Les codeurs et décodeurs représentés respectivement sur les figures 3 et 4 permettent, selon la présente invention, de tirer tous les avantages de l'auto-synchronisâtion avec des retards de synchronisation très faibles. En outre, les circuits 25 logiques supplémentaires 21, 22, 23 et 24 sont constitués par des simples portes logiques ET, OU et OU-exclusif, interconnectées de manière simple. Ces avantages découlent en partie du choix et de la disposition de la matrice de codage. Cette matrice est choisie de manière à optimiser l1auto-synchronisation 30 et à ne nécessiter en même temps que des circuits de codage simples et peu coûteux. Avant de passer à une description plus détaillée du convertisseur de code selon la présente invention, le codeur et le décodeur de base seront décrits rapidement en regard des figures 5 35 et 6. La figure 5 montre un fil d'entrée 34 sur lequel un texte codé en code binaire à longueur fixe arrive et est appliqué à un registre à décalage 32 d'entrée. Le fil d'entrée 34 peut être un 72 041^5 9 2124562 circuit électrique de transmission, ou encore conduire les données provenant d'un support d'enregistrement magnétique ou à "bande perforée. Ces mots de code binaires normaux sont introduits dans le registre à décalage 32 d'entrée, un par un, jusqu'à ce que le 5 registre 32 soit plein, et un mot de code complet apparaît sur les fils de sortie 38. Un circuit 36 de traduction par combinaison convertit le groupe de codes binaires de longueur fixe apparaissant sur les fils 38 en un code préfixe de longueur variable et applique les signaux binaires résultants aux fils de sortie 10 40. En outre, une impulsion "1" de marquage est ajoutée à la fin de chaque groupe de code lorsqu'il est introduit dans le registre à décalage 42 de sortie. Cet élément binaire marqueur sert à commander le circuit local de codage et il n'est pas émis vers le récepteur. Ce signal "1" est introduit immédiatement après le mot 15 de code et il se comporte comme un marqueur suffixe qui indique la fin du mot de code à longueur variable. Le circuit d'identification 50 détecte la présence d'un "1" dans toutes les positions, sauf celle d'extrême droite, du registre à décalage 42 de sortie. Le circuit d'identification 50 dé-20 livre donc un signal de sortie sur le fil 52 jusqu'à ce que l'impulsion de marquage arrive dans la dernière position de mémorisation du registre. Lorsque l'impulsion de marquage atteint le dernier étage du registre à décalage 42, le groupe de codes à longueur variable a été complètement émis sur le fil de sortie 48. 25 A ce moment, tous les signaux disparaissent du fil de sortie 52 et cette absence de signal, après inversion par le circuit inverseur 54, fait apparaître un signal actif qui ouvre la porte 58 et provoque l'introduction du groupe de codes à longueur variable suivant dans le registre de sortie 42. Les nouveaux codes, super-30 posés au contenu du registre 42, détruisent le signal de marquage précédent. La sortie du circuit inverseur 54 est également appliquée au circuit à retard 60 dont la sortie provoque l'introduction du groupe de codes d'entrée suivant dans le registre à décalage 32 d'entrée. 35 Le codeur de la figure 5 peut donc être considéré comme com portant un traducteur généralisé de longueur fixe en longueur variable, permettant de convertir des signaux d'entrée à longueur 72 04145 10 2124562 fixe, pouvant représenter des codes différentiels, en codes de longueur variable qui présentent des propriétés de redondance minimale. Il faut noter que les signaux marqueurs "1" ne quittent jamais le registre à décalage 42 de sortie et qu'ils ne servent 5 qu'à marquer la fin des codes à longueur variable dans le registre. la figure 6 représente un décodeur destiné à effectuer l'opération inverse de celle du codeur de la figure 5. Sur la figure 6, les signaux codés à longueur variable arrivent sur le 10 fil d'entrée 69 et sont appliqués au registre à décalage 70 d'entrée. les signaux sur les fils de sortie 71, provenant du registre à décalage 70 d'entrée, sont appliqués au circuit 64 de traduction par combinaison où ils sont convertis en un groupe 80 de codes à longueur fixe, et mémorisés dans le registre à décalage 15 66. les groupes de codes à longueur fixe provenant du registre à décalage 66 de sortie sont émis sur la ligne de sortie 68. Chaque fois qu'un groupe de codes valable est détecté par le circuit 64 de traduction par combinaison, un signal "code valable" est émis sur le fil de commande 76, afin de ramener à zéro les étages 20 du registre à décalage 70 d'entrée. Ce même signal "code valable" provoque l'application d'impulsions de progression au registre à décalage 66 de sortie, de manière à faire passer le nouveau code sur la ligne de transmission 68. les circuits de traduction 36 et 64 des figures 5 et 6 sont 25 constitués chacun par une combinaison de circuits de portes logiques qui sont commandés par les signaux d'entrée et qui, lorsqu'ils sont ouverts, délivrent des signaux binaires sur les fils de sortie correspondants. En plus du code à longueur variable normal, le circuit de traduction 36 produit également l'impulsion 30 de marquage qui termine chaque groupe. Ces impulsions de marquage ne sont pas nécessaires au circuit de traduction 64. Il est possible d'ajouter un circuit de détection de code valable constitué par exemple par une porte OU à plusieurs entrées, chaque entrée correspondant à un code valable. 35 le dispositif selon l'invention peut être .incorporé à d'autres formes de codeurs et de décodeurs à longueur variable. Ceux représentés par les figures 5 et 6 servent d'exemple et ne 72 04145 n 2124562 doivent pas être considérés comme limitatifs. Le brevet des Etats-Unis d'Amérique F0 3 016 527 décrit un exemple de ces circuits. Un exemple particulier de combinaison de codage du type représenté génériquement sur le tableau I peut être utile. A titre 5 illustratif, un système simple à deux chiffres a é>é choisi et est représenté sur le tableau II ci-après. TABLEAU II O O :i •h 01 10 1.1 S(j) A B C D j = 00 A 0 11 100 101 j = 01 B " 010 1 00 011 J = 10 C 100 11 0 101 j = 11 D 010 011 00 1 Dans cet exemple, 4 codages de préfixes différents sont utilisés, un pour chaque valeur de Le codage particulier utilisé 10 dépend de la valeur de i qui suit toute valeur particulière de jj_. Il est visible que la séquence "0011" est une séquence de synchronisation qui se termine par une valeur de i égale à "01". La séquence "0011" synchronise donc le décodeur à la fin d'un mot de code particulier, indépendamment de ceux qui précédaient la 15 séquence de synchronisation. De la même manière, la séquence "00101" synchronise le décodeur sur i = "11", la séquence "1100" synchronise sur i = "10", et la séquence "11010" synchronise sur i = "00". En supposant que les mots de code apparaissent avec les probabilités Huffman , il est facile de voir que la synchronisa-20 tion s'effectue, à partir de l'ambiguïté totale, après une moyenne de 7,67 chiffres binaires seulement (J = 7,67). Ce retard J à la synchronisation séquentielle est, ainsi que noté précédemment, le nombre moyen d'éléments binaires de codage jusqu'à ce que se présente la fin d'un mot de code correspondant à un symbole codé. 25 En d'autres termes, J est la longueur moyenne de toutes les séquences de synchronisation. 72 04145 12 2124562 le choix du code du tableau II est infiniment supérieur à celui dix tableau I, en ce qui concerne l'auto-synchronisation. En utilisant la même séquence, (0 , 11, 100, 101), le codage selon le tableau I ne présente aucune propriété d'auto-synchronisation. 5 Au contraire, le codage selon le tableau II offre une auto-synchronisation extrêmement serrée garantissant que les erreurs de synchronisation ne persistent en moyenne que pendant huit éléments binaires environ. Ces deux codes sont cependant identiques en ce qui concerne leur possibilité de compression, c'est-à-dire leur 10 capacité à comprimer les données d'entrée par codage de probabilité. Un examen plus approfondi du codage selon le tableau II montre que le code de la ligne B est le complément binaire du code de la ligne A, mais décalé cycliquement d'un mot. Le code de la 15 ligne C est symétrique du code A, décalé de deux mots. Enfin, le code de la ligne D est le décalage cyclique du complément, ou le complément du décalage, du code de la ligne A.. Chaque code du tableau II est donc lié individuelllmen^a ïout^îes" autres6/.Grâce à cette propriété, le codage et le décodage présentent des avanta-20 ges nets qui apparaîtront plus en détail ci-après. La figure 7 représente le diagramme synoptique d'un codeur destiné à coder des signaux selon le tableau II. Ce tableau montre que si le premier chiffre (p) de j est un "1", le code réfléchi est utilisé. Cette opération est effectuée sur la figure 7 par la 25 porte ET 100 et la porte OU-exclusif 101. Sur la figure 7, les éléments qui correspondent à ceux de la figure 3 sont identifiés par les mêmes références numériques. La sortie £ du circuit à retard 10', apparaissant sur le fil 102, est appliquée à une entrée de la porte ET 100. L'autre entrée de la porte ET 100 est reliée 30 à une sortie du circuit soustracteur 11'. La sortie de la porte ET 100 est reliée à une entrée de la porte OU-exclusif 101. L'autre sortie du circuit soustracteur 11' est reliée à l'autre entrée de la porte OU-exclusif 101. Les portes 100 et 101 constituent ensemble le circuit logique 21 de modification destiné à produire 35 les codes réfléchis à partir des codes différentiels normaux délivrés par le circuit soustracteur 11'. Ces codes modifiés sont appliqués au codeur de préfixe 12' qui peut avoir la forme repré 72 04145 13 2124562 sentée sur la figure 5. Les portes représentées sur la figure 7 peuvent être réalisées de toute manière connue, mais de préférence, sous forme de circuits à semi-conducteur intégrés. L'examen des codes du tableau II montre que si le second 5 chiffre (q) est un "1" le groupe de code est complémenté à partir du groupement de code normal. Sur la figure 7, la sortie £ du fil 103 est donc appliquée à des portes Oïï-exclusif 104 et 105 qui, lorsqu'elles sont ouvertes, complémentent la sortie du codeur 12' et délivrent les signaux de sortie sur les fils 13*. 10 II est donc visible qu'un codeur différentiel de base, tel que celui représenté sur la figure 1, peut être modifié de manière à présenter de très grandes qualités d'auto-synchronisation en y ajoutant seulement des circuits logiques 21 et 22 simples. Ces circuits logiques représentent un coût marginal très faible 15 par rapport à l'ensemble du codeur tout en apportant des avantages de synchronisation extrêmement importants. La figure 8 représente le diagramme synoptique d'un circuit de décodage destiné à décoder des codes tels que ceux représentés sur le tableau "II. Les éléments correspondant à ceux de la figure 20 4 sont désignés par les mêmes références. La sortie £ du circuit à retard 18' est appliquée, par le fil 106, à des circuits de portes OU-exclusif 107 et 108 afin de complémenter les codes d'entrée lorsque la valeur de ç|_ est " 1 ". La sortie £ du circuit à retard 18' est appliquée à la porte ET 109 dont la sortie est reliée à la 25 porte OU-exclusif 110. Les portes 109 et 110 constituent ensemble le circuit logique 24 de modification, et elles servent à extraire la sortie réfléchie du codeur 15* afin de l'appliquer au circuit additionneur 17'. Là aussi, le coût marginal de ces caractéristiques d'auto-synchronisation est représenté par le coût des cir-30 cuits logiques 23 et 24 qui ne représentent qu'une faible partie de l'ensemble des circuits de décodage. Il ressort de 1'examen des codes du tableau II et des circuits correspondants des figures 7 et 8 que, pour simplifier les processus de codage et de décodage, et également pour faciliter 35 la construction de codages importants, les codes séquentiels devraient posséder une structure considérable. Des recherches approfondies ont montré que les propriétés ci-après présentent une im 72 04145 14 2124562 portance considérable dans la construction des structures voulues. En premier lieu, et afin de simplifier le codage et le décodage, le nombre des noyaux de codes de préfixe distincts qui forment des groupes de codes non dérivés distincts doit être très 5 faible, un ou deux au plus. Il en est ainsi car un codeur et un décodeur indépendants et séparés sont généralement nécessaires pour chaque noyau de code indépendant. le fait de conserver un petit nombre de noyaux de code, a été appelé propriété de "symé-trisation" car elle conduit à des matrices de codage qui compor-10 tent un petit nombre de noyaux de code et de différents compléments, rotations et réflexions de ces noyaux de base0 Il faut noter que, dans le codage selon le tableau II, tous les mots de code correspondant à une valeur donnée de i se terminent par le même chiffre, quelle que soit la valeur de Cette 15 propriété, qui a été appelée "mise en colonne", améliore beaucoup l'auto-synchronisation par le fait qu'elle termine de manière uniforme les valeurs de i. Une troisième propriété du codage selon le tableau II a étéappelée "propriété d'association" et elle détermine le nombre de symboles différents auxquels un mot de code 20 donné correspond. La propriété d'association implique que ce nombre de symboles différents auxquels correspond un mot de code donné soit aussifeible que possible tout en évitant encore que chaque apparition corresponde à un symbole S(i) différent. La propriété d'association améliore considérablement la synchronisation 25 au second étage. Un exemple de code à deux noyaux qui satisfait aux propriétés de mise en colonne et d'association et dont le retard J à la synchronisation séquentielle est égal à 8, 9, est représenté sur le tableau III. 30 TABLEAU III S(J) S ( i ) - A B C D E A 0 11 100 1011 1010 B 010 1 00 0111 0110 C 1010 11 0 1011 100 D 010 0111 00 1 0110 E 1010 11 100 1011 0 72 04145 15 2124562 Certaines propriétés du code du tableau III seront décrites avec leurs conséquences. Dans un code en colonnes tel que celui représenté sur ce tableau, un groupe de symboles S(i) pour lesquels tous les mots de code se terminent par "0" est appelé groupe 5 0 et le groupe de symboles S(i) pour lesquels tous les mots de code se terminent par "1" est appelé groupe 1. Dans l'exemple du tableau III, la séquence "00", parmi d'autres, marque la fin d'un mot de code correspondant au groupe zéro, A, C ou E, i étant un nombre pair. De même, la séquence "111" marque la fin d'un mot de 10 code correspondant au groupe 1, B ou D, i étant impair, lorsque l'ambiguïté a été réduite à un symbole du groupe zéro ou un symbole du groupe un, la propriété d'association à l'intérieur de ces groupes apporte une aide importante pour atteindre la synchronisation au second étage. Cette propriété d'association est 15 particulièrement utile à la synchronisation au second étage si le code préfixe est le même pour chaque symbole S(j) dans le groupe zéro et également dans le groupe un. Cette propriété spéciale d'association des codes en colonnes est appelée propriété de "bifurcation". Par définition, les codes bifurqués peuvent être mis 20 en colonne. Si la propriété de mise en colonne doit être réalisée dans, un code séquentiel complémenté, tout noyau de code préfixe et son complément doivent comporter le mime nombre de mots de code se terminant par "zéro" et le même nombre se terminant par "un". 25 Par conséquent, la moitié des mots de code d'un code préfixe et de son complément doivent se terminer par le même chiffre. Un tel code préfixe est appelé "code équilibré" et bien entendu doit comporter un nombre pair de mots de cocle. le code du tableau II est un exemple d'un code préfixe équilibré utilisant un code à un 30 noyau complémenté. Il peut être montré que, pour chaque groupe de longueurs de mots de code avec n pair, et pour lequel il existe un code préfixe exhaustif, il existe également au moins un code préfixe équilibré, le tableau IY ci-après donne un exemple d'un codage présentant toutes les propriétés voulues décrites ci-dessus 35 et pouvant être étendues à des groupes de codes très importants. 72 0.4145 16 2124562 TABLEAU IV Matrice d'entrée-sortie d'un code symétrique, en colonne, bifurqué et équilibré comportant un noyau de code préfixe arbitraire W(k) ^ paii i=0 1=1 1=2 i=n-3 i=n-2 i=n-l D impair j=o v/(o) W(l) W(2) W(n-3) Vj(n-2) W(n-l) n-1 2 W(2) W(l) W(0) W(n-3) W(n-2) W(n-l) n-3 4 W (4) W(l) W(2) W(n-3) V,'(n-2) W(n-l) n-5 6 W(6) W W( 2) W(n-3) W(n-2) W(n-l) n-7 n-8 W(n-8) W(l) W(2) ... W(n-3) W(n-2) W(n-l) 7 n-6 V.r(n-6) v:(i) W(2) W(n-3) W(n-2) VJ(n-l) 5 n-4 W(n-4) w(D W(2) W(n-3) lï(n-2) W(n-l) 3 n-2 W(n-2) v;(i) v;(2) ... v:(n-3) w(o) W(n-l) J=l 5 Le code du tableau IV est mis en colonnes, complémenté bifur qué et associé au maximum, sans pour autant être trivial. Il suppose une probabilité i = 3 très élevée dans un but de compression. Il faut noter que si j. est pair, le mot de code complémentaire est utiliséjet le tableau IV est lu de bas en haut. Le groupe de codes 10 présente donc une symétrie réfléchie complémentaire La disposition du tableau IV peut être considérée de la manière suivante. Pour chaque valeur paire de jj_ autre que zéro, la valeur du code du noyau W(k) estjcelle pour laquelle k = 0 lorsque i = 3". Pour i = 0 la valeur de k = 3* et k = i toutes les autres 15 fois. Les mots de code correspondant aux valeurs impaires de j. sont déterminés par symétrie réfléchie complémentaire. Bien que les codes préfixes optimaux Huffmann puissent être tronqués, et utilisés comme noyaux de code, la synchronisation est améliorée considérablement si les codes préfixes utilisés sont 72 04145 17 2124562 systématiques. Un "code systématique" est un code dans lequel les mots de code suçcessifs sont produits selon une règle fixe, ou un algorithme, et présentent donc des propriétés systématiques. De cette manière, le retard de synchronisation au premier étage peut 5 être maintenu à une valeur faible, même si la longueur des mots de code augmente. le tableau V ci-après représente un code de préfixe systématique tronqué qui peut être utilisé comme noyau de la combinaison. de codage du tableau IV. 10 TAEIiEAÏÏ Y L=2,I=4 xl x2 *3 x4 yi >'2 *3 V4 V5 >'6 y? y 8 Vs *10 Vu y\z yia yi4 vis 0 0 0 0 0 0 0 0 1 i i 0 0 1 0 i 0 0 0 0 1 1 i 0 1 1 0 1 0 0 i 0 1 0 0 - 0 1 0 1 i 0 1 0 1 1 0 1 1 0 i 0 1 0 1 0 0 0* 1 1 1 i 0 ! 0 1 0 1 1 I 0 0 0 i 0 1 0 1 0 1 0 0 I 0 0 1 i 0 1 0 1 0 1 0 1 1 I 0 i 0 i 0 1 0 1 0 i 0 \ 0 0 I 0 ! 1 i 0 1 0 1 0 1 0 I 0 1 ] 1 1 0 0 i 0 1 0 i 0 1 0 i 0 1 0 0 1 i 0 1 i 0 1 0 1 0 1 0 1 0 I 0 1 i. 1 1 1 0 i 0 1 0 1 0 1 0 1 0 I 0 1 0 0 1 1 ] 1 i 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Sur ce tableau, les groupes x^, x2, x^, x^ de codes à longueur fixe correspondent aux valeurs de k tandis que y^ à cor- 72 04145 18 2124562 respondent aux éléments binaires des groupes de codes à longueur variable. En supposant que chaque mot de code apparaisse avec la probabilité caractéristique de Huffmann, la longueur moyenne 1 de ces mots est égale à 2. Le retard I de synchronisation est 5 égal à 4. L'algorithme de génération du code est représenté en haut du tableau V sous la forme graphique d'un arbre binaire. Un chiffre de code "0" correspond à un déplacement vers le bas et la gauche tandis qu'un chiffre de code "1" correspond à un déplacement 10 vers le bas et la droite. Un embranchement sans flèche indique la fin d'un mot de code. Un embranchement avec une flèche indique le passage à un autre embranchement sur le diagramme. Si la flèche ne désigne pas explicitement l'embranchement d'entrée, ce dernier est supposé être en haut ou en bas du diagramme. Le groupe de 15 code est produit en partant, eh haut ou en bas et en suivant l'embranchement sans flèche. Des longueurs de mots différentes sont obtenues en utilisant de manière exhaustive les flèches d'entrée dans toutes les combinaisons possibles. Il faut noter que le code du tableau ne comporte qu'un seul 20 groupe pour chaque longueur et qu'il est donc plus commode pour un signal qui présente la probabilité de distribution correspondante. En outre, le noyau de codes particulier du tableau Y représente une classe de codes qui ne nécessite pas de circuits différentiels. En raison de la construction du code, il est plus fa-25 cile de coder directement à partir des groupes de codes d'entrée i et de combiner le circuit de différence avec le circuit logique de modification. La figure 9 représente un codeur réalisé selon cette disposition. Le codeur de la figure 9 correspond à celui de la figure 3, 30 à l'exception que le circuit logique de modification 200 n'est pas précédé d'un soustracteur similaire au soustracteur 11'. Ces codes présentent donc l'avantage supplémentaire de simplifier encore le codeur et le décodeur, tout en offrant une auto-synchronisation extrêmement bonne. 35 La figure 10 montre un circuit décodeur correspondant dans lequel la fonction d'additionneur a été incorporée dans le circuit logique 201 de "démodification" et dans lequel aucun additionneur correspondant à l'additionneur 17l n'est nécessaire. 72 04145 19 2124562 Les circuits logiques de complémentation et de décomplémentation des figures 9 et 10 peuvent être facilement réalisés sous forme d'un circuit similaire à celui représenté sur la figure 11. 5 Plusieurs éléments binaires d'entrée qui doivent être com- plémentés sont appliqués aux fils d'entrée 210, 211...212. Chacun des fils d'entrée 210, 211„..212 est relié à l'une correspondante des portes OU-exclusif 213, 214...215. L'autre entrée de toute ces portes OU-exclusif est reliée au fil de commande 216. 10 Les signaux de sortie qui apparaissent sur les fils de sortie 217» 218...219 sont les compléments des signaux d'entrée si, et seulement si, les portes 213 à 215 sont commandées par un signal sur le fil 216. Sinon, ces signaux de sortie sur les fils 217 à 219 sont identiques aux signaux d'entrée des fils 210 à 212. 15 La figure 12 illustre un circuit logique de modification qui peut constituer le circuit logique de modification 200 de la figure 9 et également le circuit logique de"démodification" 201 de la figure 10 dans le cas du code du tableau V. Selon le tableau IV, si j, est pair, la relation ci-après peut être écrite : 20 k = j pour i = 0 k = 0 pour i = j et sinon : k = i Si 2. es"k impaire : " k = 15 - j pour i = 15 25 k = 0 pour i = j et sinon k = 15 - i. i et 2 seront supposés être des nombres binaires, i étant représenté par (x^ , x2, x^, x^) et jj. Par (x^, x2', x^', x^' ). Avec la notation d'une barre placée sur un chiffre binaire pour 30 indiquera complémentation : ï = 15 - i = x2, X3» x4^ En faisant u = "1" si, et seulement si : ï X2_T X2 = X4 = ° il vient î u = x, . x0. x„. x.. (produit Booléen). 12 3 4 35 En posant t = 1 si, et seulement si i = j il vient;t = (x1 + x^). (x2 + x2'). (x^ + x^'). (x^ + x^') t est donc le produit booléen de quatre sommes modulo deux (OU- 72 04145 20 2124562 exclusif). Si k est représenté par le nombre binaire à 4 chiffres, k = (P* il en découle : p = t. x.j + u. x.j1 5 q = t. x2 + u. x2l r = t. x, + u. x,1 3 3 s = t. x. + u. x.1 4 4 Pour en revenir , à la figure 12., la valeur u est obtenue à partir de en connectant chacun des fils 250, 251, 252 et 253 à 10 l'un correspondant des inverseurs 254 à 257. Les sorties de ces inverseurs sont reliées à une porte ET 258 dont la sortie délivre la valeur binaire u. Le signal u est appliqué à une entrée de chacune des portes ET 259, 260, 261 et 262, dont les autres entrées sont reliées aux fils 250 à 253. 15 La valeur binaire t est obtenue en connectant chacun des fils d'entrée 250 à 253 à l'une correspondante des entrées des portes OU-exclusif 263 à 266. Les autres entrées des portes OU-exclusif 263 à 266 reçoivent respectivement les valeurs x^, x2, x^, x^, par les fils 267 à 270. Les signaux de sortie des portes 20 OU-exclusif 263 à 266 sont tous appliqués à la porte ET 271. Cette dernière, quand elle est ouverte, ouvre les portes ET 272, 273, 274, et 275 dont les autres entrées reçoivent les valeurs de x1, x2, x^, x^ par les fils 267 à 270„ Les sorties des portes ET 259 à 262 sont reliées aux entrées 25 correspondantes des portes OU 276 à 279. Les sorties des portes 272 à 275 sont reliées aux autres entrées des portes OU 276 à 279 dont les signaux de sortie apparaissent sur les fils 280 à 283. Ces signaux de sortie représentent les valeurs binaires p, q, r et s et, dans le codeur de la figure 9, ils peuvent être appliqués 30 directement à un codeur de préfixe 12'. Le circuit logique de la figure 12 peut être utilisé directement comme circuit de "démodification" 201 de la figure 10 simplement en appliquant les valeurs de k aux fils d'entrée 267 à 270. Les sorties des portes OU 276 à 279 constituent alors le 35 nombre binaire i. 72 04145 21 2124562 Lorsqu'il est associé au codeur de la figure 9» avec les codes du tableau IV, le circuit logique de complémentation de la figure 11 est commandé par l'élément binaire x^' qui indique si 2 est impair ou non. Un signal qui représente la valeur de x^1 5 doit donc être appliqué sur le fil 216 de la figure 11. Bien qu'avec le codeur de la figure 9, lé noyau de codes du tableau V présente certains avantages, cela ne signifie pas qu'il soit le seul groupe de codes utilisables. La figure 13 montre six autres noyaux identifiés par les colonnes I-VI. Ces codes 10 présentent des distributions de longueurs et des retards de synchronisation différents. Ils peuvent constituer chacun le code de noyau de la combinaison de codage illustrée par le tableau IV. D'autres noyaux et d'autres combinaisons de codage permettent également l'auto-synchronisation et les exemples qui ont été don-15 nés ne visent qu'à illustrer les propriétés voulues du codage. D'autres codes sont indiqués dans l'article "Efficient Error-Limiting Variable-length Codes" précité. La première phase du choix d'un codage séquentiel consiste à déterminer la" longueur optimale du mot de code pour chaque va-20 leur de 2» basée sur les probabilités conditionnelles de S(i), S(J) étant donné. Cela peut se faire selon l'algorithme de Huffman décrit dans "A Method for the Construction of Minimum Redundancy codes" Proceedings of the IEE, vol. 40, Septembre 1952, pages 1098 à 1101. L'examen de la matrice des longueurs ainsi obtenue 25 montre les symétries que le code doit présenter, si une symétrie réfléchie est nécessaire et si le code doit être à un seul noyau. La phase suivante consiste à choisir le code de noyau dont les longueurs correspondent le plus exactement possible aux longueurs voulues. Les codages sont ensuite agencés de manière à optimiser 30 les propriétés de mise en colonne et d'association. Bien entendu, le code qui permet la meilleure auto-synchronisation correspond à celui qui possède les qualités voulues de symétrie, de mise en colonne et d'association. Il va de soi que de nombreuses modifications peuvent être 35 apportées au dispositif décrit et représenté sans sortir du cadre de l'invention. 72 04145 22 2124562 KEVBHDICATIONS 1. Convertisseur de code destiné à un dispositif de traitement de données et comportant un circuit (11®) de traduction séquentielle destiné à convertir les signaux d'entrée en symboles 5 de sortie qui dépendent des signaux d'entrée présents et précédents, et un circuit (12') de traduction à longueur variable destiné à convertir les symboles d'entrée provenant du circuit de traduction séquentielle en signaux de sortie codés de longueur-variable, convertisseur caractérisé en ce que le circuit (12') 10 de traduction à longueur variable est agencé de manière à convertir les symboles d'entrée en un sous-groupe prédéterminé de mots de code préfixe de longueur variable, le convertisseur comportant un circuit logique (21) de modification commandé par les signaux d'entrée précédents et destiné à modifier des valeurs sélection-15 nées des symboles de sortie du circuit de traduction séquentielle en changeant l'ordre desdits symboles de sortie et un circuit logique (22) de complémentation commandé par les signaux d'entrée retardés et destiné à complémenter et à permuter sélectivement le sous-groupe de mots de code préfixe de longueur variable. i 20 2. Convertisseur de code selon la revendication 1, caracté risé en ce que le circuit logique (21) de modification comporte une porte OU-exclusif (101) et une porte ET logique (100) commandées par les signaux d'entrée retardés. 3. Convertisseur de code selon la revendication 1, caracté-25 risé en ce que le circuit logique (22) de complémentation comporte plusieurs portes OU-exclusif qui sont toutes commandées par une entrée commune à laquelle sont appliqués les signaux d'entrée retardés. 4. Convertisseur de code selon la revendication 1, caracté-30 risé en ce que le circuit de modification change les valeurs sélectionnées des symboles de sortie du circuit de traduction séquentielle en inversant l'ordre desdits symboles de sortie et en les décalant.