Brevet FR2640096A1 — publié le 19900608

DESCRIPTLON 'Dispositif de décodage de mots statistiques à longueur variable". La présente invention concerne un dispositif de décodage de mots binaires à longueur variable, ces mots formés d'un nombre variable d'éléments binaires se présentant en une suite d'éléments binaires pour etre décodés, dispositif comportant un premier circuit de décodage muni d'un nombre déterminé de premiers accès d'entrée et des accès de sortie pour fournir des mots décodés à longueur fixe, un circuit d'entrée pour présenter auxdits accès d'entrée le nombre détermine d'éléments. Les mots formés d'un nombre variable d'éléments binaires peuvent résulter d'un codage préalable selon un code de Huffman par exemple. Pour établir ce code1 on effectue une statistique de l'information à coder, et on attribue des mots à grande longueur pour une information à faible occurrence et des mots à courte longueur pour des informatons à forte occurrence. Ce mode de codage est particulièrement intéressant dans le domaine de la transmission de signaux, pour lequel on sait extraire des grandeurs statistiques (exemple : parole, image, texte) car il permet de réduire considérablement le débit sans altérer l'information. lin décodeur capable d'effectuer l'opération inverse de décodage est décrit dans le brevet Européen 0 149 893. Le circuit d'entrée de ce dispositif est formé d'un registre à décalage dont la capacité est prévue pour contenir des mots formés du nombre maximal d'éléments binaires. Les éléments binaires de la suite sont emmagasinés l'un après l'autre dans le registre jusqu'à ce qu'un mot soit reconnu par le circuit-de décodage. Cette reconnaissance, effectuée pour chaque entrée d'élément binaire, est considérée comme un inconvénient majeur pour obtenir un traitement rapide. Les traitements rapides s'imposent dans de nombreuses applications, en télévision notamment où chaque mot est relatif à la luminance et/ou la chrominance d'un pixel. La présente invention propose un dispositif de décodage du genre mentionné dans le préambule présentant un temps de décodage court. Pour cela un tel dispositif est remarquable en ce qu'il comporte un circuit d'aide pour fournir à des deuxièmes accès d'entrée de ladite mémoire une information supplémentaire résultant du décodage du nombre déterminé d'éléments binaires précédent. De tels dispositifs sont appelés à coopérer avec des mémoires-tampons destinées à compenser les variations de débit entre les données reçues, codées par un code statistique et les données à fournir au circuit d'utilisation sous forme de mots à longueur fixe. Un avantage obtenu par l'invention est qu'un tel dispositif peut être relié sans prendre de mesures particulières aux sorties de mémoires-tampons qui sont organisées, de préférence, en nots de longueur fixe correspondant ainsi au nombre d'éléments binaires à présenter au circuit d'entrée. Il est à noter que ce dispositif convient particulièrement bien pour coopérer avec le dispositif de codage déposé en France au nom de la demanderesse le 15 octobre 1988 sous le numéro 88 10 617. La description suivante faite en regard des dessins ci-annexés, le tout donné à titre d'exemple non limitatif, fera bien comprendre comment l'invention peut cotre réalisée. La figure 1 représente un premier dispositif de décodage de mots statistiques conforme & l'invention. La figure 2 représente l'arbre de codage des lots statistiques. La figure 3 montre comment les suites d'éléments binaires sont décomposées en blocs formés d'un nombre déterminé d'éléments binaires. La figure 4 est un diagramme temps destiné à l'explication du dispositif de l'invention de la figure 1. La figure 5 représente un deuxième dispositif de décodage conforme à l'invention. Les figures 6a et 6b sont des diagrammes temps destinés à l'explication du dispositif de l'invention de la figure 5. A la figure 1, la référence 1 indique le dispositif de décodage de l'invention. Ce dispositif est muni d'un accès d'entrée 2 pour recevoir les mots statistiques à décoder et d'un accès de sortie 4 pour fournir des mots décodés. Le dispositif de décodage doit effectuer le décodage suivant, explicité dans le tableau I ci-dessous, qui se déduit de l'arbre de codage montré à la figure 2. TABLEAU I Longueur Réf. de la du Mots statistiques Mots de sortie mot feuille 1 1 1000 F8 2 01 0 1 1 1 F 7 3 001 1 0 0 1 F 9 5 00011 O I 1 0 F 6 6 000101 1 0 1 O F10 7 0001000 0 1 0 t F 5 7 0000000 - ST 8 00010010 1 0 1 1 F11 10 0001001111 0 1 0 0 F 4 11 0001001000 0 0 1 1 F 3 11 00010011001 1 1 0 0 F12 12 00100110100 0 0 1 0 F 2 12 000100110110 1 1 1 0 F14 12 000100111000 O O 0 1 F 1 12 000100111001 I 1 0 1 F13 12 000100111010 1 1 1 1 F15 12 0000Q0111111 - SL Ainsi, les mots statistiques dont la longueur, mesurée en nombre d'éléments binaires, varie de 1 à 12, sont convertis en mots de sortie de 4 éléments binaires. Les mots statistiques proviennent d'une mémoire tampon 5. Pour y être emmagasinés les éléments binaires sont groupés en blocs de 12 éléments binaires où 12 est la longueur maximale des mots statistiques à la borne de réception 10. Ces blocs de 12 éléments binaires sont appliqués à l'accès 2 au rythme d'un signal VAL élaboré par le dispositif 1 disponible à une sortie 15. La cadence d'apparition des mots de sortie aux accès 4 est fixée par un signal H appliqué à la borne 17. Une mémoire morte 20 dont la programmation sera explicitée dans la suite du présent exposé, effectue différents décodages nécessaires au bon fonctionnement du dispositif 1. A des premiers accès Al la mémoire 20 reçoit un bloc d'éléments binaires comportant un nombre déterminé de ceux-ci ; ce bloc est enregistré dans un circuit d'entrée 22 constitué d'un registre. Ce registre 22 reçoit aussi le signal VAL qui, lorsqu'il est actif, autorise le chargement d'un nouveau bloc à la prochaine transition active du signal H. Un circuit d'aide 23 formé de quatre registres 24, 25, 26 et 27 fournit des informations supplémentaires à des deuxièmes accès d'entrée A2 de la mémoire 20. Une première information supplémentaire est une information d'emplacement d'élément binaire PB, une deuxième information est une information d'emplacement d'arbre PA pour définir le noeud (N1 à N26, figure 2) de l'arbre, une troisième information est une information de mode MD pour valider l'une des informations PA ou PB, une quatrième information concerne le nombre de mots restant à décoder contenus dans le registre 22. On notera que les entrées d'enregistrement de tous ces registres 22, 24, 25, 26 et 27 sont reliées à la borne 17 et que le registre 22 est muni d'une commande d'inhibition reliée à la borne 15. Ce signal VAL n'autorise liennaga- sinage d'un nouveau bloc d'éléments binaires que lorsque tous les mots du registre 22 susceptibles d'être décodés l'ont été. Les mots décodés apparaissent à la borne 4 en transitant dans un registre 30 dont l'entrée d'enregistrement est reliée à la borne 17. On explique maintenant le fonctionnement du dispositif de décodage de la figure 1. On se reporte à la figure 3a où l'on a représenté une succession d'éléments binaires représentant plusieurs mots décodés, selon l'arbre de décodage précité, mis bout à bout. Cette succession est découpée en blocs de 12 éléments binaires BL1, BL2, BL3,... correspondant aux nombres de fils des pre miers accès Al, tels que représentés à la figure 3b et ce sont ces blocs qui, finalement, se retrouvent dans le registre 22. A la figure 4, on a représenté en fonction des fronts actifs du signal H d'une part l'évolution des contenus des registres 22, 24, 25 et 30 et d'autre part l'apparition de la valeur active du signal VAL. Soit l'instant tO où l'on a un front actif du si- gnal H, on admet qu'en ce temps tO la valeur VAL = O, de sorte que le bloc BL1 soit contenu dans le registre 22. On admet en outre que les contenus des autres registres sont initialisés et donc non significatifs. Soit l'instant tl où l'on a le front actif suivant du signal H. Le contenu du registre 22 est identique, les deux premiers éléments binaires vont être reconnus et le mot décodé correspondant (F7) est mis dans le registre de sortie 30. Le registre 27 contient l'indication du nombre de mots décodés statistiques contenus dans le registre 22 et restant à décoder ; ce contenu est 3. Dans le registre 26 on trouve l'élément binaire '1' signifiant que des registres 24 et 25, seul le contenu du registre 24 doit être considéré, c'est-à-dire celui contenant la position du premier élément binaire du mot de code statistique suivant à décoder, ici 2. Aux instants t2 et t3 les deux mots suivants sont décodés F8 et F9. A l'instant t3, le registre 27 contient le chiffre 1 signifiant qu'il n'y a plus qu'un mot à décoder de sorte que le signal VAL va prendre sa valeur active "0" à l'instant t4. Lorsqu'à l'instant t5 apparait un front actif du signal H le bloc BL2 sera emmagasiné dans le registre 22. A cet instant t5 aussi le mot F10 est enregistré dans le registre 30 qui correspond aux six derniers éléments binaires à traiter contenus dans le registre 22 à l'instant t3. A l'instant t6 où apparait le front actif suivant du signal H, le deuxième mot statistique contenu dans le registre 22 est considéré pour le décodage. C'est le dernier de ce bloc à décoder, de sorte que le signal VAL va prendre la valeur "0 à l'instant t7.Les derniers éléments binaires "O", O","O'a contenus dans ce bloc BL2 appartiennent au mot statistique sui vant. Si on se reporte à l'arbre de décodage représenté à à la figure 2, cette succession de trois 0" définit le noeud N4 qui sera enregistré à l'instant t8, défini par un front actif de H, dans le registre 25, le contenu du registre 26 devient "0" pour signifier alors que seul des deux registres 24 et 25 ctest le contenu du registre 25 qui doit etre considéré. L'indication du noeud va servir à décoder la fin de ce mot qui appartient au bloc BL3 enregistré dans le registre 22 à l'instant ta. A l'instant t9 où le signal H est actif, le mot décodé F6 sera contenu dans le registre 30.Il est évident, pour un homme de l'art de concevoir le circuit 20 à partir d'éléments connus tels que mémoires mortes, multiplexeurs, circuits FPLA, etc. Le dispositif de décodage montré à la figure 5 comporte un ensemble de mémoires 201, 202, 203, 211 et 212 qui scindent en plusieurs parties le décodage effectué par la mémoire 20 du dispositif de la figure 1. Ainsi ces décodages sont effectués sur des mémoires de plus petites capacités facilement disponibles dans le commerce. Une première partie du décodage est effectuée par les mémoires 201 et 202 qui fournissent le mot décodé à la borne de sortie 220 par l'intermédiaire d'un multiplexeur 222 à deux entrées. A l'entrée de ces mémoires 201 et 202 sont appliqués des blocs de douze éléments binaires à décoder et provenant de la sortie d'une cascade de trois registres 225, 226 et 227 dont l'entrée est connectée à l'accès d'entrée 230. Les blocs sont ici décomposés en deux groupes de 6 éléments binaires chacun, correspondant aux accès Al des mémoires 201 et 202, pour y être traités respectivement. Les mémoires sont munies de sorties DC respectivement reliées aux deux entrées du multiplexeur 222 et pour fournir, donc, le mot décodé.Elles sont munies aussi des deux sorties (référencées par PB) reliées respectivement aux entrées de registres 251 et 252 pour fournir l'information d'emplacement PB qui indique la position du premier élément binaire du mot à traiter, contenu dans le groupe. Les sorties de ces registres 251 et 252 sont reliées respectivement à des premières entrées de multiplexeurs 261 et 262 à deux entrées. Les deuxièmes entrées de ces multiplexeurs reçoivent une information supplémentaire PA provenant de sorties (référencées aussi par PA) des mémoires 211 et 212 Pour cela la deuxième entrée du multiplexeur 261 est reliée à la sortie PA de la mémoire 211 par l'intermédiaire de trois registres 269, 270 et 271 montés en cascade. L'information supplémentaire provenant de la sortie PA de la mémoire 212 est appliquée à la deuxième entrée du multiplexeur 261 en transitant par deux registres 272 et 273 montés en cascade aussi. Cette information supplémentaire fournie au moyen d'une deuxième partie de décodage effectuée par les mémoires 211 et 212 est aussi établie respectivement à partir deys deux groupes de six éléments binaires d'un bloc appliqués aux entrées de ces mémoires 211 et 212. Ces groupes sont considérés à la sortie du registre 225. L'information supplémentaire est aussi nécessaire pour cette deuxième partie de décodage, Ainsi la sortie PA de la mémoire 212 est reliée directement à un accès d'entrée de la mémoire 211 et la sortie PA de la mémoire 211 est reliée à un accès d'entrée de la mémoire 212 par l'intermédiaire du registre 271. Une troisième partie du décodage est effectuée par la mémoire 203. Les accès d'entrée de cette mémoire sont reliés, par l'intermédiaire des registres 271 et 272 à des sorties NC des mémoires 211 et 212. A ces sorties est fournie l'indication du nombre de fins de mots contenues dans les groupes présents aux accès des mémoires 211 et 221. Cette mémoire fournit différentes informations, d'une part des informations NCSS, PC et MD qui transitent avant d'être utilisées dans un registre 280 et d'autre part l'information VAL qui est appliquée directement aux entrées d'inhibition des registres 225, 226, 270 et 271. L'information NCSS est une information indiquant le nombre de mots contenus dans un bloc, restant à décoder. Cette information est rebouclée sur un accès NCSE de la mémoire 203.L'information provenant de la sortie PC est utilisée pour commander la position du multiplexeur 222 et celle provenant de la sortie MD, la position des multiplexeurs 261 et 262. Les différents registres 225, 226, 227, 251, 252, 269, 270, 271, 272, 273 et 280 reçoivent sur leur entrée le signal H définissant la cadence des mots décodés à fournir à la borne 220 comme indiqué par le dispositif de la figure 1. Le tableau II ci-dessous donne la manière dont sont programmés les mémoires 211 et 212. TABLEAU II ENTREE SORTIE PA Groupe NC PA N1 000000 0 N 9 000001 0 N 1 -- ------ -- -- a 000101 1 N 1 -- ------ -- --b 011001 3 N 1 -- ------ -- --c 100010 1 N8 N2 000000 1 N 1 -- ------ -- -- ---------------------- N4 000000 1 N 3 -- ------ -- -- 110000 1 N 5 ---------------------- d N8 010000 1 N 4 ---------------------- Le tableau III, ci-dessous, donne la manière dont sont programmées les mémoires 201 et 202 et le tableau IV, qui suit, donne la manière -dont est programmée la mémoire 203. TABLEAU III MD = 0 Groupe PA CODE DECODE PB 000000 N1 - 000001 N1 - 000101 N1 F10 0 011001 N1 F 7 2 . . . . . . . . . . . MD = 1 G PB PB 000000 0 . . I I li 011001 2 F 8 3 011001 3 F 9 0 TABLEAU IV TABLEAU IV ENTREE SORTIE NCE NC1 NC2 NCS PC MD VAL a X X X 0 - - 0 0 0 b#0 ##0 1 0 1 k I O a#0 b#0 a+b-1 0 1 0 1 1 d # a+0|b=# #-1 1 0 1 # a#0 b > # #-1 1 1 1 c # a#0 b #-1 0 1 1 On explique maintenant à l'aide des figures 6a et 6b le fonctionnement du dispositif de la figure 5. Sur les figures 6a et 6b, on a représenté sur la ligne supérieure différents instants t10, t11, t12,... définis par le front actif du signal R. Entre ces instants le contenu des différents registres reste fixe. Ainsi aux lignes 211-E et 211-S on a représenté l'évolution des codes d'entrée et de sortie de la mémoire 211 aux lignes 212-E et 212-S les codes d'entrée et de sortie de la mémoire 212, à la ligne 271-S, le code à la sortie du registre 271, à la ligne 272-5 le code à la sortie du registre 272, aux lignes 203-E et 203-S les codes d'entrée et de sortie de la eéooirez203, à la ligne 226-S le code-à ia sortie du registre 226, à à la la ligne 270-S le code à la sortie du registre 270 aux lignes 201-E et 201-S les codes d'entrée et de sortie de la mémoire 201, aux lignes 202-E et 202-S les codes d'entrée et de sortie de la mémoire 202 et enfin à la ligne 220-S le code à la sortie 220. On a aussi re présente à la ligne (VAL) les variations dii signal VAL. On rappelle que lorsque VAL = O le contenu des registres 225, 226, 271, 272 et 273 est renouvelé du code présent à leur entrée à l'apparition du front actif du signal H. Soit 11 instant t10, où l'on considère le bloc BLI ; ce bloc est divisé en deux groupes : le groupe "000101" adresse la mémoire 211 et le groupe "011001" la mémoire 212. Ces groupes sont notés respectivement GR1 et GR2 à la figure 4. Les mémoires 211 et 212 sont aussi adressées par une information supplémentaire qui indique le noeud (voir figure 2) à partir duquel le décodage doit commencer. On suppose que le noeud N1, déterminé en un instant antérieur à t10, est contenu dans le registre 271. On suppose également que VAL = 0. La consultation du tableau II à la ligne b montre que le contenu des codes à la sortie des mémoires 212 est tel que : NC = 3 et PA = Ni, cette valeur de PA est directement appliquée aux accès d'entrée de la mémoire 211 avec le groupe GRI ; la consultation du tableau II à la ligne a montre qu'à la sortie de cette mémoire 211 on a NC = 1 et PA = N1. On considère l'instant titi. Comme le signal VAL est tel que VAL = O le bloc BL2 va se trouver aux entrées des mé robres 211 et 212, la consultation du tableau il aux lignes c et d va donner les valeurs respectives NC = 1, PA = N8 d'une part et NC = 1 et PA = N4 d'autre part. Les codes disponibles aux sorties des mémoires 211 et 212 se retrouvent respectivement aux sorties des registres 271 et 272. On notera également que le bloc BLI se retrouve à la sortie du registre 226.A l'entrée de la mémoire 203, on suppose que NCSE = O et si on affecte aux valeurs NC1 et NC2 les valeurs NC aux sorties NC des mémoires 211 et 212, la consultation des lignes situées en dessous de la ligne a du tableau IV indique que VAL prend ins tantanément la valeur "1" puisque NCS prend une valeur différente de O (NCI + NC2 - 1 # O) ce qui survient à l'instant t11 situé juste après l'instant tII. La consultation du tableau IV donne les valeurs suivantes (voir ligne ) : PC = O, MD = O. Survient alors l'instant t12. Le bloc BL1 se trouve aux accès d'entrée des mémoires 201 et 202. L'information sup plémentaire pour décoder le groupe "0011001" présent aux accès d'entrée de la mémoire 202 provient de la sortie du registre 273.Cette information N1 était disponible déjà à la sortie du registre 272 après l'instant t11 puisque le bloc 010000" était appliqué à l'entrée de la mémoire 211 (ligne d tableau Il > et que le bloc 100010" était appliqué à l'entrée de la mémoire 212 (ligne c du tableau II). Après l'instant t12 à la sortie de la mémoire 202 on a à la sortie DC le code correspondant à la feuille F7, ce code se trouve donc à la sortie 220 puisque le code PC = O défini après l'instant t11 se retrouve à l'instant t12 à la Sortie du registre 280.A l'instant t12 la valeur de NC2 est inférieure à NCE (voir ligne c du tableau IV), la valeur MD passe à "1", ce qui fait que pour décoder le deuxième élément binaire du groupe 011001* à l'instant t13 l'information supplémentaire pour le décodage provient de la sortie du registre 252 contenant la position du premier des éléments binaires constituant le mot suivant. A cet instant t13 la valeur NCE est diminuée d'une unité, ce qui ne change pas la valeur des codes de sortie de la mémoire 203. Par contre à l'instant t14 le code NCE prend la valeur 1 ce qui a pour première conséquence que NCS prend la valeur "0" donc VAL atteint cette valeur à l'instant t14' situé juste après l'instant t14 (ligne a du tableau IV). Une deuxième conséquence est que la valeur PC change c'est-à-dire que le code de sortie provient de la mémoire 201, la troisième et dernière conséquence est que la valeur MD prend la valeur "O" (ligne d du tableau IV). L'information supplémentaire provient de la sortie du registre 270 et donc déjà emmagasinée à l'instant tii. Avant d'examiner ce qui va se passer après l'instant t15, il convient de noter qu'à l'instant titi le signal VAL est "0" ce qui fait qu'après cet instant le bloc BL2 est contenu dans le registre 225 et le reste jusqu'à l'instant t15. A cet instant tirs, le signal VAL est "0" de sorte que le registre 225 contient le bloc BL3 et le registre 227 le bloc BL2, les registres 271 et 272 contiennent des valeurs relatives au bloc BL2. A cet instant t15 le dernier code du bloc BL1, le code correspondant à la feuille F10 est fourni à la borne 220 avec les valeurs PC et MD définies après l'instant t14. Les codes NC contenus dans les registres 271 et 272 sont appliqués aux accès d'entrée de la mémoire 203 c'est-à-dire NCE. = O, NC1 = 1, NC2 = i si on se reporte au tableau IV. Le fait que NC1 + NC2 - i est différent de "0" entraîne que VAL prend la valeur "1" à l'instant ti5' et la ligne k indique que PC = O, MD = O ces valeurs seront utiles pour le décodage du mots après l'instant t16. Après cet instant le code correspondant à la feuille F8 est transmis à la borne 220. Il est facile maintenant pour un homme de l'art de voir que les différents codes correspondant aux feuilles F11, F6 sont fournis aux instants. ti7 et t18. REVENDICATIONS 1. Dispositif de décodage de mots binaires à longueur variable, ces mots formés d'un nombre variable d'élénents binaires se présentant en une suite d'éléments binaires pour entre décodés, dispositif comportant un premier circuit de décodage muni d'un nombre déterminé de premiers accès d'entrée et des accès de sortie pour fournir des mots décodés à longueur fixe, un circuit d'entrée pour présenter auxdits accès d'entrée le nombre déterniné d'éléments binaires, caractérisé en ce qu'il comporte un circuit d'aide pour fournir à des deu fières accès d'entrée dudit circuit de décodage une informa- tion supplémentaire résultant du décodage du nombre déterminé d'éléments binaires précédent. 2. Dispositif de décodage selon la revendication 1, caractérisé en ce que l'information supplémentaire peut être constituée par une information d'emplacement d'élément binaire pour définir l'emplacement du début ou de la fin d'un mot à longueur variable parmi le nombre déterminé d'éléments binaires. 3. Dispositif de décodage selon la revendicaiton i pour lequel le processus de décodage est établi sur la base d'un arbre de décodage dans lequel on distingue des noeuds et des feuilles, caractérisé en ce que l'information supplémentaire peut être constituée par une information d'emplacement de noeud pour définir l'emplacement du noeud obtenu lors du décodage précédent. 4. Dispositif de décodage selon l'une des revendications I à 3, caractérisé en ce que le circuit de décodage est muni d'un accès de sortie pour fournir un signal de traitement pour un nouveau nombre déterniné d'éléments binaires. 5. Dispositif de décodage selon la revendication I ou 4 pour lequel le processus de décodage est établi sur la base d'un arbre de décodage dans lequel on distingue des noeuds et des feuilles, caractérisé en ce que l'inforiation supplénen- taire peut être constituée par une information d'emplacement d'élément binaire pour définir l'emplacement du début ou de la fin d'un mot à longueur variable parmi le nombre déterminé d'éléments binaires, par une information d'emplacement d'arbre pour définir l'emplacement dans l'arbre obtenu lors du décodage précédent et par une information de mode pour valider l'une des informations d'emplacement d'élément binaire et d'emplacement d'arbre. 6. Dispositif de décodage selon la revendication 1 ou 2 ou 3 ou 4 ou 5, caractérisé en ce qu'il comporte un deuxième circuit de décodage et un circuit d'aiguillage pour fournir à la sortie les mots' décodés provenant du premier ou du deuxième circuit de décodage. 7. Dispositif de décodage selon l'une des revendications 1 à 6, caractérisé en ce que le ou les circuits de décodage sont constitués par une pluralité d'unités de décodage. 8. Dispositif de décodage selon la revendication 7, caractérisé en ce qu'il est prévu des registres entre les différentes unités de décodage pour assurer la cohérence des différentes opérations.