Brevet FR2800941A1 — publié le 20010511

Procédé de décodage de données codées à l'aide d'un code entropique, dispositif de décodage et système de transmission correspondants. Le domaine de l'invention est celui de la transmission, ou de la diffusion, de signaux de données numériques. Plus précisément, l'invention concerne le décodage de signaux numériques transmis, et en particulier le décodage de source. Plus précisément encore, l'invention s'applique au décodage de données codées à l'aide d'un codage de source mettant en #uvre des codes entropiques de type codes à longueur variable (VLC, en anglais : Variable Length Code ). Les systèmes de communication numérique couramment utilisés aujourd'hui s'appuient sur des systèmes de codage mettant en #uvre d'une part un codage de source et d'autre part un codage de canal. Classiquement, ces deux codages sont optimisés séparément. Le codeur de source a pour but de réduire au maximum la redondance du signal source à transmettre. Ensuite, pour protéger cette information des perturbations inhérentes à toute transmission, le codeur de canal introduit de la redondance, de manière contrôlée. Actuellement, les meilleurs résultats sont obtenus en codage de source (source audio, images et/ou vidéo) par des codeurs par transformée en cosinus discrète (DCT, en anglais : "Discrete Cosine Transform") ou ondelettes notamment, associés à des codes VLC. Le codage de canal met en #uvre avantageusement le concept des turbo-codes [1](les références bibliographiques sont rassemblées en annexe C, afin de faciliter la lecture de la présente description), et plus généralement des décodeurs itératifs à décisions douces. Ces techniques ont permis de franchir un pas décisif vers la limite théorique définie par Shannon [2]. Toutefois, l'optimalité de la séparation du codage de source et du codage de canal n'est garantie que pour des codes de longueur tendant vers l'infini. De ce fait, des recherches sont également menées pour réaliser, avec des codes canal de longueur finie, des systèmes de codage et/ou de décodage conjoints source-canal. L'invention concerne ainsi le décodage de codes entropiques, et en particulier, mais non exclusivement, le décodage conjoint source-canal d'un système mettant en #uvre un code entropique. Le décodage conjoint possède de nombreux champs d'application, par exemple la transmission d'images vidéo, en particulier selon la norme MPEG 4 (Moving Picture Expert Group). Les codes à longueur variable sont bien connus. A titre d'exemple, on présente rapidement, en annexe A, le code de Huffman. Le mode de réalisation particulier de l'invention décrit par la suite s'applique notamment, mais non exclusivement, à ce type de code entropique. Les codes à longueur variable présentent un enjeu important pour la limitation de la bande occupée par le signal émis, mais leur utilisation rend la transmission moins robuste aux erreurs. De plus, il est difficile d'utiliser les probabilités a priori de la source au décodage, car on ne connaît pas le début et la fin de chaque mot, puisque la longueur de ceux-ci est, par définition, variable. Diverses techniques ont été proposées pour effectuer un décodage conjoint source-canal lié à l'utilisation de ces codes à longueur variable. Notamment : K. Sayood et N. Demir ont proposé dans [4] un décodage au niveau des mots de codes VLC. On retrouve les deux inconvénients majeurs de ce type de décodage, à savoir une complexité de treillis qui augmente rapidement avec le nombre de mots VLC différents et un décodage qui reste au niveau symbole (ou mot) ; Ahshun H. Murad et Thomas E. Fuja [5] proposent une méthode de super- treillis où le treillis de décodage est celui obtenu par le produit du treillis du décodeur de canal, du treillis du décodeur de source et du treillis représentant la source. Cette solution est clairement limitée par la complexité du décodage ; K. P. Subbalaskshmi et J. Vaisey [6] donnent une structure de treillis qui permet de connaître le début et la fin de chaque mot et donc d'utiliser l'information a priori que l'on a sur les mots VLC émis. Ce décodeur travaille au niveau des mots et ne renvoie pas d'information extrinsèque sur les bits décodés ; Jiangtao Wen et John D. Villasenor [7] utilisent un bloc de décodage travaillant au niveau des mots et renvoyant une fiabilité quant à la séquence décodée. Ce décodeur utilise comme information a priori le nombre de mots VLC dans la séquence reçue. L'invention a notamment pour objectif de pallier les différents inconvénients de ces techniques de l'état de l'art. Plus précisément, un objectif de l'invention est de fournir une technique de décodage de données codées à l'aide d'un code entropique permettant d'obtenir une réduction du taux d'erreur symbole, notamment par rapport à des schémas de décodage séparé (tandem). Sur les aspects de mise en #uvre, un objectif de l'invention est de fournir une telle technique de décodage présentant une complexité très réduite, par rapport aux techniques connues. En particulier, un objectif de l'invention est de fournir une telle technique de décodage présentant une complexité opératoire raisonnable, c'est-à-dire possible à mettre en #uvre en pratique à un coût raisonnable, en particulier lorsque le nombre de mots différents considérés par le code entropique est élevé. L'invention a également pour objectif de fournir une telle technique délivrant des informations de confiance au niveau bit pouvant être exploitées par le décodage de canal. En d'autres termes, un objectif particulier de l'invention est de fournir des procédés de décodage conjoints source-canal bien adaptés aux codes entropiques, notamment les codes VLC. Encore un autre objectif de l'invention est de fournir une telle technique de décodage, permettant d'améliorer les performances obtenues avec les codes de canal connus, et notamment les codeurs mettant en #uvre un turbo-code. Ces objectifs, ainsi que d'autres qui apparaîtront plus clairement par la suite, sont atteints à l'aide d'un procédé de décodage de données numériques reçues correspondant à des données numériques émises codées à l'aide d'un code entropique associant à chacun des mots d'un alphabet une séquence de bits distincte, dont la longueur est fonction de la probabilité d'occurrence dudit mot. Selon l'invention, ce procédé met en #uvre un treillis de décodage dont chaque transition correspond à une valeur binaire 0 ou 1 d'un des bits d'une séquence de bits correspondant à l'un desdits mots. En d'autres termes, l'invention repose sur une approche nouvelle du décodage des codes à longueurs variables, selon laquelle on considère les transitions au niveau des bits, et non classiquement au niveau des mots, ou symboles. Cette approche est nouvelle, et non évidente, l'homme du métier étant persuadé que le fait que les symboles sont de longueurs variables imposent de travailler au niveau des symboles, afin de connaître le début et la fin de ceux-ci. Les inventeurs montre que cela n'est pas obligatoire. De plus, le fait de travailler au niveau des bits permet d'obtenir une information exploitable par un décodeur canal, et donc d'effectuer un décodage conjoint, comme cela apparaîtra plus clairement par la suite. Ledit code entropique peut être représenté sous la forme d'un arbre binaire comprenant un n#ud racine, une pluralité de n#uds intermédiaires et une pluralité de n#uds feuilles, une séquence de bits correspondant à un desdits mots étant formée en considérant les transitions successives dudit arbre depuis ledit n#ud racine jusqu'au n#ud feuille associé audit mot. Dans ce cas, de façon avantageuse, les états de chaque étage dudit treillis comprennent un unique état dit extrémal, correspondant audit n#ud racine et à l'ensemble desdits n#uds feuilles, et un état distinct, dit état intermédiaire pour chacun desdits n#uds intermédiaires. On obtient ainsi un treillis simple, à nombre d'états réduit. De façon préférentielle, on associe à chaque transition dudit treillis une information de vraisemblance. Ladite information de vraisemblance est alors avantageusement une métrique tenant compte d'une part d'une information représentative du canal de transmission et d'autre part d'une information a priori relative à la source. Ainsi, on peut calculer, pour chacune desdites transitions, la métrique suivante : ï,[(Xk,Xt),dk,dk-l] = Pr(xk / ak = i)Pr(y[ / ak = l,dk,dk-L)Prak = i,dkldk-11, dont les informations et paramètres sont décrits par la suite. Ledit code entropique peut notamment appartenir au groupe comprenant : # les codes de Huffman ; # les codes à longueur variable réversibles. L'invention concerne également un procédé de décodage conjoint sourcecanal d'un signal numérique reçu, basé sur cette approche, le codage source mettant en #uvre un code entropique associant à chacun des mots d'un alphabet une séquence de bits distincte, dont la longueur est fonction de la probabilité d'occurrence dudit mot. Selon l'invention, ce procédé de décodage conjoint met donc en #uvre un décodage source utilisant au moins un treillis de décodage dont chaque transition correspond à une valeur binaire 0 ou 1 d'un des bits de la séquence de bits correspondant à l'un desdits mots, ledit décodage source délivrant une information extrinsèque au décodage canal. Le décodage canal peut avantageusement mettre en #uvre un décodage de type turbo-code, pouvant reposer sur une mise en #uvre de type parallèle ou sur une approche de type série . De façon avantageuse, le procédé de décodage conjoint de l'invention repose sur une mise en #uvre itérative. Dans ce cas, chacune des itérations peut comprendre séquentiellement une étape de décodage canal et une étape de décodage source, ladite étape de décodage canal délivrant une information de canal prise en compte dans ladite étape de décodage source, cette dernière délivrant une information a priori prise en compte dans ladite étape de décodage canal. Notamment, le procédé peut comprendre : # une première étape de décodage canal ; # une première étape de décodage source, alimentée par ladite première étape de décodage canal ; # une seconde étape de décodage canal, alimentée par ladite première étape de décodage canal et ladite première étape de décodage source, via un entrelaceur identique à l'entrelaceur mis en #uvre au codage, et alimentant ladite première étape de décodage canal, via un désentrelaceur symétrique audit entrelaceur ; # une seconde étape de décodage source alimentée par ladite seconde étape de décodage canal via ledit désentrelaceur, et alimentant ladite première étape de décodage canal. Selon un autre aspect de l'invention, celle-ci concerne encore un procédé de décodage conjoint source-canal d'un signal numérique reçu, le codage source mettant en #uvre un code entropique associant à chacun des mots d'un alphabet une séquence de bits distincte, dont la longueur est fonction de la probabilité d'occurrence dudit mot, ledit procédé mettant en #uvre un treillis de décodage canal, similaire au treillis de codage canal, dans lequel on associe à chaque état de chaque étage une information désignant la position du bit considéré dans l'arbre représentant ledit code entropique. Dans ce cas, le procédé de décodage conjoint comprend avantageusement, pour chacun desdits états, les étapes suivantes : # ajout, aux deux branches arrivant dans ledit état, de la métrique du canal et de la métrique de la source ; # comparaison des deux nouvelles métriques obtenues, et sélection de la métrique la plus faible ; # si ladite information désignant la position indique la fin d'un mot, considérer que le n#ud est une feuille de l'arbre, sinon, passer au n#ud suivant dans l'arbre. Préférentiellement, ce procédé met en #uvre une procédure itérative, qui peut par exemple comprendre les étapes suivantes : # premier décodage canal, mettant en #uvre un treillis de décodage canal dont chaque état dispose d'une information désignant la position du bit considéré dans l'arbre représentant ledit code entropique ; # deuxième décodage canal, alimenté par ledit premier décodage canal, via un entrelaceur identique à celui mis en #uvre au codage, et alimentant ledit premier décodage canal, via un désentrelaceur symétrique dudit entrelaceur ; # décodage source, alimenté par ledit deuxième décodage canal, via ledit désentrelaceur. Bien entendu, l'invention concerne également tous les dispositifs de décodage de données numériques mettant en #uvre l'un des procédés de décodage décrits ci-dessus, ainsi que les systèmes de transmission d'un signal numérique, mettant en #uvre, à l'émission, un codage source entropique et un codage canal, et à la réception, un décodage tel que décrit plus haut. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante de modes de réalisation préférentiels de l'invention, donnés à titre de simple exemple illustratif et non limitatif, et des dessins annexés, parmi lesquels : - la figure 1 présente un exemple d'un code de Huffman, sous la forme d'un arbre binaire ; la figure 2 illustre un treillis symbole dit réduit, correspondant à l'arbre de la figure 1 ; - la figure 3 présente un treillis binaire dit réduit selon l'invention, correspondant à l'arbre de la figure 1 ; - la figure 4 est un schéma illustrant une structure de décodage conjoint de type turbo-code, mettant en #uvre un module "SISO~huff"selon l'invention ; la figure 5 illustre le déroulement de l'algorithme de décodage conjoint source-canal selon un second mode de mise en #uvre ; - la figure 6 présente un schéma itératif de décodage conjoint mettant en #uvre l'algorithme illustré en figure 5 ; - la figure 7 présente une combinaison des procédés des figures 4 et 6; la figure 8, commentée en annexe A, illustre la construction d'un codage de Huffman. Modes de réalisation préférentiels 1-Introduction L'invention a donc notamment pour objectif de présenter une technique de décodage réduisant le taux d'erreurs symboles, en utilisant les informations a priori sur la source, probabilités sur les mots du code VLC ou probabilités de transition entre les mots. On a constaté que cette réduction est plus élevée si les décodeurs utilisent les informations a priori sur la source au niveau bit, car l'extraction d'informations du décodage de canal ne peut se faire qu'à ce niveau bit. Jusqu'à présent, la plupart des méthodes proposées pour le décodage des codes VLC travaillent au niveau des mots (ou symboles, ces deux termes étant utilisés indifféremment par la suite) et ne peuvent donc pas fournir d'informations extrinsèques au niveau bit. De plus, ces méthodes deviennent pour la plupart trop complexes, et donc non réalisables en pratique, lorsque le nombre de mots différents à transmettre augmente. La seule tentative faite au niveau bit est présentée dans [5]. Très clairement, cette solution présente une complexité opératoire très élevée, et rapidement rédhibitoire. La technique de l'invention permet en revanche de déterminer non seulement la séquence de mots optimale, mais également la fiabilité associée à chacun des bits de chaque mot. Pour ce faire, l'invention utilise une information a priori sur la source, c'est-à-dire la probabilité a priori des mots du code VLC, ou celle de transition de Markov entre les mots du code. Cette technique peut avantageusement être utilisée dans un schéma itératif de type turbo-code, et améliore les performances de la transmission. 2- Notation On utilise notamment par la suite les notations suivantes : # une décision douce correspond à une décision réelle non binaire. Un seuillage sur celle-ci donnera une décision dure. Une décision douce est aussi appelée décision soft ; # le rapport EB/N0 correspond au rapport entre l'énergie reçue par bit utile divisée par la densité spectrale monolatérale du bruit ; # la bande DC (Direct Component) d'une image est la composante continue de l'image après transformation par ondelette ou par DCT ; # une séquence de bit reçus est notée par X ou Y. Cette séquence se compose de mots notés xi, ces mots étant composés de bits notés xij; # on utilise la notation p(a) = Pr{x' = a # un code RVLC (en anglais : Réversible VLC ) [8] est un code à longueur variable dont les mots se décodent dans les deux sens ; # un algorithme SISO ( Soft-In Soft-Out ) a pour entrées des valeurs soft et délivre des sorties soft . 3- Décodage "soft " source de codes à longueur variable On montre, en annexe B, comment il est possible d'extraire de l'information des suites de mots de longueur variable émise par un codeur de Huffman (voir annexe A), en modélisant la source, soit par un processus aléatoire générant des symboles indépendants, soit par un processus aléatoire markovien. La figure 1 présente l'exemple d'un code de Huffman, sous la forme d'un arbre binaire. Il est composé de cinq mots a, b, c, d, e de probabilités p(a), p(b), p(c), p(d), et p(e), et de longueurs respectivement 3, 3, 2, 2 et 2. La table de codage correspondante est donnée ci-dessous : a 111 b 110 c 10 d 01 e 00 Table 1 : des codes VLC de l'arbre de la figure 1. En se plaçant, selon l'approche de l'invention, au niveau bit, on observe que quatre états sont nécessaires pour décrire sous forme de treillis, l'arbre de la figure 1. Ces états sont dO pour le début et la fin des symboles, dl , d2 et d3 pour les positions intermédiaires. Par contre, au niveau symbole, on remarque qu'un seul état dO peut suffire, ainsi que l'illustre la figure 2. Le treillis symbole réduit ainsi défini est donc alors un treillis à un seul état dO, duquel partent et arrivent autant de branches qu'il existe de mots VLC. Dans l'exemple de la figure 1, à chaque étage (t-2, t-1, t), ce treillis présente cinq branches correspondant aux mots a, b, c, d et e. Le treillis symbole réduit utilise les probabilités a priori sur les mots de la source, en travaillant au niveau des mots. Ce treillis peut également être utilisé comme treillis annexe lors du décodage utilisant les probabilités de Markov. 4- Décodage selon l'invention. au niveau des bits On a vu que, selon les techniques connues, les procédés de décodage d'une source VLC utilisent les probabilités a priori des mots VLC au niveau des mots, ce qui empêche de renvoyer la fiabilité sur chaque bit de la séquence décodée. On montre par la suite comment les probabilités a priori sur les mots peuvent être décomposées en un produit de probabilité a priori sur les bits, puis on décrit les procédés de décodage s'appuyant sur cette approche. 4.1 Utilisation des probabilités a priori des mots de codes VLC au niveau des bits Cette partie explique la décomposition des probabilités des mots en un produit de probabilités binaires. Prenons l'exemple du mot a : On a d'après l'arbre de la figure 1 : p(a) = Prix, = a} = Pr{x = I,x, = 1, x\ = Il (8) Cette probabilité se décompose suivant l'équation : p(a) = Pro = 1} Prx; =1 / xô = 1} Prx = 1 x =1, x; = Il (9) La probabilité p(a) est donc le produit de trois probabilités associées à chacun des bits du mot a. Avec un treillis qui indique la position du bit dans le mot que l'on décode, ces probabilités binaires permettent de faire du décodage soft binaire. Par exemple, si on sait que l'on est dans la deuxième position du mot a alors la probabilité à utiliser sur la branche est Pr(x1i = 1/x0i = 1). Calculons, pour le mot a et pour k - 0,1,2 les probabilités Pvlx'k +1I(x = +1, j L'arbre de la figure 1 donne immédiatement la solution. On en déduit, aux différents sommets de l'arbre, les égalités : Pr{x0i 1} Pr{sommeti,0= SI} p(a) + p(b) + p(c) (10) Prjxj = 11 x lr Prsommet,,l 53/ sommet [0 SI} p(a) + p(b) (11) p(a) + p(b) + p(c) Prjxj = 1 / x = 1, x; = If pr{ sommet,,2 S7/ sommet"l S3} p(a) (12) p(a) + p(b) Ce calcul peut se généraliser facilement au cas d'un code de Huffman réel. Soit C=(w') l'ensemble des mots de code Huffman, Sk = In ENI'v'p Ce principe de calcul est illustré ici dans le cas d'une source de mots indépendants. Pour une source de Markov, le principe est le même sauf que chaque distribution des probabilités calculée dépend du mot précédent trouvé. Ainsi, le calcul est à faire pour tous les mots précédents possibles. Une fois cette décomposition faite pour tous les mots du code VLC, il faut trouver le treillis binaire réduit qui permette d'utiliser les probabilités binaires. La décomposition de p(a), p(b),... en un produit de probabilités binaires a imposé une certaine relation entre les probabilités binaires et les probabilités de mots. Ces relations sont conservées uniquement, s'il y a une bijection entre les branches de l'arbre et celles du treillis. Il faut donc le treillis le moins complexe possible qui donne la position des bits dans chaque mot et qui évite les branches parallèles identiques (même état de départ, même état d'arrivée et même étiquette). 4. 2 Le treillis binaire réduit (appelé SISO-huff ) Premièrement, nous allons décrire l'algorithme de construction du treillis binaire réduit. Puis nous donnerons l'algorithme de décodage sur ce treillis et notamment l'utilisation des probabilités binaires a priori. 4.2.1 Algorithme de construction du treillis binaire réduit Initialisation du treillis Premier état du treillis, état 0 : de l'arbre i = boucle de construction Pour chaque mot de la table VLC, Pour chaque bit de ce mot, construction des états Si l'état de départ de la branche de l'arbre étiquetée par ce bit n'est pas associé à un état du treillis, ajouter un état au treillis, état i i++ Si l'état d'arrivée de la branche n'est pas associé à un état du treillis, Si il correspond à un n#ud non terminal de l'arbre, Ajouter un état au treillis, état j (j==i) i++ Sinon associer cet état à l'état j (j = 0) étiquetage des branches Créer, si non existante, une branche entre l'état i et l'état y étiquetée par le bit traité Dans le cas de notre exemple, on obtient ainsi le treillis de la figure 3. Ce treillis donne la position du bit dans le mot. Si on est dans l'état i, on sait, à partir de l'arbre, que l'on est dans la position} du mot traité car il existe une correspondance bijective entre les états i du treillis et les positions} dans l'arbre. 4.2.2 Algorithme de décodage à partir du treillis binaire réduit L'algorithme de décodage utilisé sur ce treillis pour les simulations données par la suite est un algorithme de type BCJR (Bahl Cocke Jelinek Raviv) [13] modifié par Benedetto dans [14] pour traiter les branches parallèles. La métrique calculée sur chaque branche tient compte de la connaissance que l'on a sur le canal et des probabilités a priori binaire calculée précédemment. Plus précisément, la formule de calcul sur une branche [ 15] est : A l'instant discret k, le couple (xk,xkp) est le couple de vraisemblances des bits reçus, dk-1 et dk sont respectivement les états de départ et d'arrivée de la branche, ak est le bit d'information associé à la branche. Les deux premiers termes de droite de l'équation (13) font référence à la connaissance que l'on a sur le canal. Le troisième, Pr{ak = i,dkdk-1}, correspond à la probabilité binaire a priori. Ce treillis est utilisable dans un décodage soft binaire de type BCJR ou de type SOVA (en anglais : "Soft Output Viterbi Algorithm"). Lors de l'utilisation des probabilités a priori de Markov, si on utilise l'algorithme BCJR, le décodage soft nécessite un traitement parallèle qui indique pour chaque étage le mot précédent le plus probable. Ce traitement est celui réalisé par le treillis symbole réduit. Cette augmentation de complexité implique une préférence pour l'algorithme SOVA ou pour l'algorithme SUBMAP [11]. 4. 3 Généralisations La méthode présentée se généralise sans difficulté aux cas où la table de Huffman contient plus de bits. Cependant la complexité du treillis binaire réduit augmente avec le nombre de mots de la table de Huffman. L'application de la méthode de l'invention aux codes RVLC [8] peut bien sûr être envisagée. Le treillis du bloc SISO~huff peut être utilisé en décodant dans l'autre sens mais cela implique une augmentation de la complexité. Une alternative serait d'utiliser les probabilités a priori dans un sens pour la phase forward et dans l'autre pour la phase backward . D'autre part, il est intéressant de chercher parmi les codes de Huffman équivalents [17], celui qui est le mieux adapté pour le décodage soft du bloc SISO~huff . 5- Décodage conjoint source-canal 5. Schéma de principe d'utilisation du bloc " SISO huff" " Le treillis binaire réduit ou "SISO~huff" permet un décodage de type SISO et peut donc s'insérer dans un schéma de décodage itératif comme celui de la figure 4. Chaque bloc de décodage 41 à 44 de la figure 4 extrait de l'information extrinsèque sur les bits à décoder et envoie cette information au bloc suivant. Les informations qui circulent entre les différents blocs sont, comme dans la référence [15] des probabilités extrinsèques. Des deux décodeurs de canal DECIet DEC2,41 et 43, on extrait deux informations extrinsèques différentes suivant qu'elles sont utilisées par le bloc "SISO~huff'' 42 ou 44 ou par l'autre décodeur de canal 41 ou 43. L'information extrinsèque 451, 452 utilisée par le décodeur de canal suivant est celle classiquement utilisée dans les turbo-codes. Celle utilisée par le bloc "SISOJhuff" 42,44, représentée en gras, 461, 462 correspond à cette première information à laquelle on a enlevé l'information issue du précédent bloc "SISO~huff", 44,42, ceci dans le but de respecter la règle selon laquelle tout bloc du décodage itératif ne doit pas utiliser une information qu'il a déjà produite. La structure globale du décodeur itératif n'est pas discutée plus en détail. Elle est en effet connue en soi [1]. Les modules E 471et 472 sont des entrelaceurs (identiques à ceux mis en #uvre au codage) et le module E* 48 un désentrelaceur, symétrique à l'entrelaceur. Les informations prises en compte sont les suivantes : # Xk: Information de vraisemblance reçue sur les bits d'information émis ; # Y1k : Information de vraisemblance sur les bits de parité issus du codeur 1 ; # Y2k : Information de vraisemblance sur les bits de parité issus du codeur 2 ; # Proba : probabilité a priori ; # Sortie~hard : bit d'information décodé. Ce schéma est un exemple de décodage conjoint itératif où l'information a priori et l'information du canal sont utilisées tour à tour sur leur treillis associé. Il est aussi envisageable d'utiliser conjointement ces deux informations sur le treillis du décodeur canal comme le montre le deuxième procédé proposé. 5.2 Second algorithme de décodage conjoint source-canal Le décodage conjoint proposé à la figure 4 réalise itérativement et séquentiellement les deux fonctions de décodage. On présente ci-après une technique où un bloc unique de décodage réalise simultanément les deux opérations. Cette technique s'applique aussi au décodage d'une source markovienne. Le concept développé est applicable à toute chaîne de transmission composée d'un treillis de décodeur de canal (convolutif ou en bloc) et d'une source représentable par un arbre. 5.2.1 Algorithme de construction du treillis Le treillis utilisé est celui du codeur de canal et ne nécessite aucune nouvelle construction. 5.2.2 Algorithme de décodage L'algorithme de décodage est de type Viterbi. Il décode la séquence de mots la plus probable. Le calcul de métrique fait intervenir non seulement l'information du canal (cas usuel) mais aussi les probabilités a priori binaires. Cette méthode s'apparente à celle présentée par Hagenauer [15] mais appliquée ici aux codes à longueur variable. Pour ceci, l'algorithme doit savoir à quelle branche de l'arbre de Huffman correspond la branche actuellement traitée sur le décodeur de canal. Cette information lui suffit pour donner la probabilité a priori binaire adéquate (calculée comme dans le paragraphe 4.1et stockée au préalable dans un tableau). Cette information est facilement accessible en tenant à jour pour chaque étage et pour chaque état du treillis du décodeur de canal la position du bit dans l'arbre. Pour chaque étage du décodeur de canal, Pour chaque état, corps de l'ACS (Add Compare Select) ajouter aux deux branches arrivant dans l'état la métrique du canal et celle de la source comparer les deux nouvelles métriques obtenues, choisir celle de métrique la plus faible remise à jour si on atteint la fin d'un mot, n#ud = racine de l'arbre sinon n#ud = noeud suivant dans l'arbre } Reprenons l'exemple de l'arbre de la figure 1. L'algorithme se déroule comme présenté sur la figure 5. A l'étage considéré, il y a deux séquences concurrentes arrivant au deuxième état du treillis. Chacune correspond à un enchaînement de mots VLC différents. La première, en trait plein, correspond à l'émission de e, d,..., la seconde, en trait pointillé à b, e,.......La probabilité de branche a priori pour chacune d'elle, P [S2][0] et P [S0][1], dépend du noeud Si noté sur la séquence et du bit 0 ou lqui étiquette la branche. Une fois le calcul de la probabilité de la branche effectué, par la relation (6), on peut faire l'ACS classique. Cette solution est très intéressante car, contrairement à la solution du bloc "SISO~huff", elle n'est pas limitée en complexité par la taille de la table de Huffman et n'augmente que de très peu la complexité actuelle des décodeurs de canal. 6- Application du second algorithme à un schéma itératif de décodage conjoint 6.1 Utilisation de cette méthode dans un schéma itératif Un schéma pour l'utilisation dans un décodage itératif est représenté sur la figure 6. Le premier décodeur 61 utilise sur le même treillis l'information du canal et l'information a priori. Par contre, le deuxième décodeur 62 ne peut pas utiliser l'information a priori car l'entrelaceur 63, noté E, casse les relations entre les mots de code VLC. Ce dernier utilise alors les probabilités p(0) et p(1) qui sont dans la plupart des cas différentes. 6.2 Cumul des deux approches de décodage conjoint Il est possible d'utiliser les deux procédés proposés ci-dessus dans un schéma itératif, tel que celui donné à titre d'exemple en figure 7. Sur cette figure, les notations sont identiques à celles utilisées précédemment. L'élaboration d'un entrelaceur conservant les relations entre les mots permet de trouver un compromis entre entrelacement binaire optimal et conservation de la structure a priori sur les mots. 7- Performances On a montré la possibilité de réaliser un décodage à décision douce des codes de Huffman. Par rapport à des travaux déjà publiés, la méthode de l'invention permet de travailler au niveau bit. Il est ainsi possible d'introduire un bloc de décodage source à entrées et sorties pondérées, dit "SISO~huff", dans un schéma de décodage canal de type turbo-codes. Une autre possibilité est d'utiliser l'information a priori sur la source directement au niveau du décodeur de canal. Cette deuxième méthode est nettement moins complexe et donne des résultats équivalents à ceux obtenus avec "SISO~huff". Les gains apportés par ce type de schéma dépend d'une part de la modélisation utilisée pour la source avec la connaissance a priori des probabilités des symboles de Huffman ou de leurs probabilités de transition, et d'autre part, du rapport Eb/N0 sur le canal. Dans les comparaisons que nous avons effectuées, nous évaluons nos gains par rapport au schéma tandem correspondant. Dans la gamme des taux d'erreur binaire autour de 10-2à 10-3, les deux nouvelles techniques permettent des gains entre 0,5 et 1 dB dès leur première itération, ceci avec des codeurs NSC (en anglais : Non Systematic Coder ). Par ailleurs leur utilisation dans un schéma itératif de type Turbo-Codes améliore les performances de 0,5 à 1,5 dB. De plus l'utilisation conjointe des 2 méthodes permet d'espérer un gain cumulé encore plus important. Dans les fourchettes de gains annoncés, les valeurs les plus fortes sont obtenues à faible rapport signal à bruit, ce qui permet d'accroître notablement la plage de fonctionnement en transmission. A noter également que dans un schéma de type Turbo-Code, cela peut permettre de décaler d'autant, et donc de 0,5 à 1,5 dB, le point de déclenchement de l'effet Turbo-Codes. Le premier procédé nécessite le déroulement d'un algorithme de décodage sur le treillis "SISO~huff"alors que le deuxième nécessite simplement une remise à jour d'une table lors du décodage sur le treillis du décodeur de canal. De plus, contrairement au premier procédé, le deuxième a une complexité de calcul qui n'augmente pas avec le nombre de mots dans la table VLC. L'utilisation des codes à longueur variable de type Huffman étant très largement répandue, ces techniques de décodage peuvent convenir dans de nombreux contextes. Les applications sont multiples. On retrouve par exemple des tables de Huffman dans la norme MPGE4 pour le codage des coefficients de la bande DC et de la bande AC pour les images codées en intra mais aussi pour le codage des vecteurs de mouvement. L'invention peut également être utilisée dans une chaîne de transmission plus complète en prenant en compte un système de codage d'images à la norme, ou proche de la norme, et un modèle de canal représentatif du canal radio-mobile comme BRAN ( Broadcast Radio Network ). ANNEXE A VLC Huffman Le code de Huffman ([17]) est un code entropique qui compresse une source en codant les données peu probables sur une longueur binaire supérieure à la moyenne et ceux très probables sur une longueur binaire courte. Le code de Huffman est très utilisé car il n'existe pas d'autres codes entier (dont les symboles sont codés sur un nombre entier de bits) qui donne un plus faible nombre moyen de bits par symbole. Une de ses caractéristiques essentielles est qu'une séquence binaire ne peut jamais être à la fois représentative d'un élément codé et constituer le début du code d'un autre élément. Cette caractéristique du codage de Huffman permet une codification à l'aide d'une structure d'arbre binaire. Il existe plusieurs façon de présenter la construction du code de Huffman. Celle qui semble la plus simple est basée sur une structure d'arbre. Soient les N mots ai de probabilités respectives p(ai). L'arbre est construit à partir de ses N sommets terminaux. Chaque sommet terminal i est affecté de la probabilité p(ai) et permettra d'avoir la décomposition binaire du mot a,. L'algorithme de construction de l'arbre consiste à chaque étape à sommer les deux probabilités les plus faibles de l'étape précédente pour les réunir en un sommet affecté de la probabilité somme. A la dernière étape, on obtient un sommet de probabilité 1. Il reste à étiqueter les branches de l'arbre obtenu en indexant par un 1 les branches de droite de chaque sommet et par 0 les branches de gauche. La décomposition binaire du mot ai est alors obtenue en descendant l'arbre en partant du sommet de probabilité 1 jusqu'au sommet i. L'exemple expliqué prend le cas de 4 mots comme le montre la figure @, mot proba codage a0 p (a0) 111 a1 p(a1) 110 a2 p (a2) 10 a3 p (a3) 0 Décodage source de symboles indépendants ou markoviens Deux structures optimales sont utilisées pour le décodage d'une séquence codée. Chacune se base sur un critère différent, le critère de la séquence la plus vraisemblable ou le critère du symbole le plus vraisemblable couramment appelé MAP 4 ax. M:n ., \0.;t..-.-r; Algorithme de Viterbi La recherche de la séquence la plus vraisemblable se fait avec l'algorithme de Viterbi [9] qui cherche la séquence X émise la plus probable connaissant la séquence Y reçue : max P(X/Y) (1) X Comme la fonction logarithme est strictement croissante, il est équivalent de maximiser log P (X/Y) maxlog P(X/Y) (2) En appliquant la loi de Bayes : P(X/Y)P(Y) = P(Y/X)P(X) (3) le critère devient : max[log P(Y/X) + log P(X)] (4) L'information a posteriori sur X se décompose en deux termes. Le premier log P(Y/X) concerne l'information fournie par le canal, le second log P(X) concerne l'information a priori sur la séquence émise. Si les échantillons de bruit du canal sont indépendants alors la loi du bruit P(Y/X) s'exprime comme le produit des lois de probabilités des bruits perturbant chacun des mots xi et yi et des bits transmis x,et yji: En ce qui concerne la probabilité a priori P(X), les deux hypothèses envisagées sont: - les mots émis par la source sont indépendants : - les mots émis suivent un processus de Markov d'ordre 1 comme par exemple dans le cas d'un codeur d'image en sous-bandes pour ce qui concerne la composante continue. On a alors Classiquement, le décodage suivant l'algorithme de Viterbi comprend une phase d'ACS (Add Compare Sélect) : à chaque étage et à chaque état, on additionne la métrique de la branche associée à chacune des deux séquences concurrentes, on compare les deux métriques obtenues et on sélectionne la séquence de métrique la plus faible. Algorithme du MAP Le décodage selon le MAP [10] se fait suivant la règle ci-dessous : Le calcul de la probabilité p(xji = +1/Y) est complexe. Cette complexité peut-être réduite au prix d'une perte en performances. L'algorithme moins complexe est appelé algorithme SUBMAP [11]. Pondération des décisions du décodeur Cette pondération est une information de fiabilité sur l'estimation réalisée par le décodeur. Cette information "soft", parfois appelée information extrinsèque, est utilisable par un décodeur externe, un décodeur de source ou tout autre dispositif intervenant dans la réception de l'information [12]. Plusieurs algorithmes fournissent des décisions pondérées sur les valeurs décodées : . G-...tr ..,c v.C;', 4"lre;...) - l'algorithme SOYA [13] se base sur une légère modification de l'algorithme de Viterbi; Coke Jeunch Raviv) - l'algorithme BCJR@[14] est établi sur le critère du MAP. Une source codée VLC ou issue d'un codeur de canal peut être représentée par un treillis duquel on peut extraire de l'information extrinsèque. L'invention propose une nouvelle méthode de construction d'un tel treillis à partir du code VLC de la source. Références [1] C. Berrou, A. Glavieux, and P. Thitimajshima. "Near Shannon limit error-correcting coding and decoding: Turbo-Codes". Proceedings of ICC, pages 1064-1070, May 1993. [2] C. E. Shannon. "A Machemaltical Theory of Communication", volume 27. Bell System Tech. J., 1948. [3] S. B. Zahir Azami. "Codage conjoint Source/Canal, protection hiérarchique". PhD thesis, ENST Paris, May 1999. [4] N. Demir and K. Sayood. "Joint source/channel coding for variable length codes". In Data Compression Conference (DCC), pages 139-148, Snowbird, Utah, March 1998. [5] A. H. Murad and T. E. Fuja. "Joint source-channel decoding of variable length encoded sources". In Information Theory Workshop (ITW), pages 94-95, Killarney, Ireland, June 1998. [6] K. P. Subbalakshmi and J. Vaisey. "Joint source-channel decoding of entropy coded markov sources over binary symmetric channels". In Proc. International Conference on Communications (ICC), pages 94-95, Vancouver, June 1999. [7] J. Wien and J. D. Villasenor. "Utilizing soft information in decoding of variable length codes". In Data Compression Conference (DCC), Snowbird, Utah, March 1999. [8] Y. Takishima, M. Wada, and H. Murakami. "Réversible variable length codes". IEEE Transactions on Communications, 43 :158-162, 1995. [9] A. Viterbi. "Error bounds for convolutional codes and an asymptotically optimal decoding algorithm". IEEE Transactions on Information theory, 13 :260-269, 1967. [10] W. Koch and A. Baier. "Optimum and sub-optimum detection of coded data dis- turbed by time-varying intersymbol interférence". Proceedings GLOBECOM, pages 1679-1684, December 1990. [11] P. Robertson, E. Villebrun, and P. Hoeher. "A comparaison of optimal and sub- optimal map decoding algorithms operating in the log-domain". In Proc. Internatio- nal Conférence on Communications (ICC), pages 1009-1013, Seattle, Washington, June 1995. 12] J. Hagenauer. "Soft-in/Soft-out: the benefit of using soft values in all stages of digital receiver". Institute for communications technology, 1990. [13] J. Hagenauer and P. Hoeher. "A Viterbi algorithm with soft-decision outputs and its applications". Proceedings GLOBECOM, pages 1680-1686, November 1989. [14] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv. "Optimal decoding of linear codes for minimizing symbol error rate". IEEE Transactions on Information theory, pages 284-287, March 1974. [15] S. Benedetto and G. Montorsi. "Generalized concatenated codes with interleavers". In International Symposium on Turbocodes, pages 32-39, Brest, September 1997. [16] J. Hagenauer. "Source-controlled channel decoding". IEEE Transactions on Com- munications, 43:2449-2457, September 1995. [17] A. E. Escott and S. Perkins. "Binary Huffman équivalent codes with a short synchro- nizing codeword". IEEE Transactions on Information theory, 44 :346-351, January 1998. [18] D. A. Huffman. "Method for the reconstruction of minimum redundancy codes". Key Papers in The development of Information Theory, pages 47-50,1952. [19] K. Sayood and J. C. Borkenhagen. "Utilization of corrélation in low rate dpcm systems for channel error protection". In Proc. International Conférence on Communications (ICC), pages 1888-1892, June 1986. REVENDICATIONS 1. Procédé de décodage de données numériques reçues correspondant à des données numériques émises codées à l'aide d'un code entropique associant à chacun des mots (50 à 58) d'un alphabet une séquence de bits distincte, dont la longueur est fonction de la probabilité d'occurrence dudit mot (50 à 58), caractérisé en ce qu'il met en #uvre un treillis de décodage dont chaque transition correspond à une valeur binaire 0 ou 1 d'un des bits d'une séquence de bits correspondant à l'un desdits mots. 2. Procédé de décodage selon la revendication 1, ledit code entropique étant représenté sous la forme d'un arbre binaire comprenant un n#ud racine (50), une pluralité de n#uds intermédiaires (51 à 53) et une pluralité de n#uds feuilles (54 à 58), une séquence de bits correspondant à un desdits mots étant formée en considérant les transitions successives dudit arbre depuis ledit n#ud racine jusqu'au n#ud feuille associé audit mot, caractérisé en ce que les états de chaque étage dudit treillis comprennent un unique état dit extrémal (dO), correspondant audit n#ud racine et à l'ensemble desdits n#uds feuilles, et un état distinct, dit état intermédiaire (dl à d3) pour chacun desdits n#uds intermédiaires. 3. Procédé de décodage selon l'une quelconque des revendications 1 et 2, caractérisé en ce que l'on associe à chaque transition dudit treillis une information de vraisemblance. 4. Procédé de décodage selon la revendication 3. caractérisé en ce que ladite information de vraisemblance est une métrique tenant compte d'une part d'une information représentative du canal de transmission et d'autre part d'une probabilité binaire a priori. 5. Procédé de décodage selon la revendication 4, caractérisé en ce que l'on calcule, pour chacune desdites transitions, la métrique suivante : 6. Procédé de décodage selon l'une quelconque des revendications 1 à 5, caractérisé en ce que ledit code entropique appartient au groupe comprenant : # les codes de Huffman ; # les codes à longueur variable réversibles. 7. Procédé de décodage conjoint source-canal d'un signal numérique reçu, le codage source mettant en #uvre un code entropique associant à chacun des mots (50 à 58) d'un alphabet une séquence de bits distincte, dont la longueur est fonction de la probabilité d'occurrence dudit mot, caractérisé en ce qu'il met en #uvre un décodage source (42,44) utilisant au moins un treillis de décodage dont chaque transition correspond à une valeur binaire 0 ou 1 d'un des bits de la séquence de bits correspondant à l'un desdits mots (50 à 58), ledit décodage source délivrant une information extrinsèque au décodage canal (41, 43). 8. Procédé de décodage conjoint selon la revendication 7, caractérisé en ce que le décodage canal (42,44)met en #uvre un décodage de type turbo-code. 9. Procédé de décodage conjoint selon la revendication 8, caractérisé en ce que ledit décodage de type turbo-code repose sur une mise en #uvre de type parallèle. 10. Procédé de décodage conjoint selon la revendication 8, caractérisé en ce que ledit décodage de type turbo-code repose sur une mise en #uvre de type série. 11. Procédé de décodage conjoint selon l'une quelconque des revendications 7 à 10, caractérisé en ce qu'il repose sur une mise en #uvre itérative. 12. Procédé de décodage conjoint selon la revendication 11, caractérisé en ce que chacune des itérations comprend séquentiellement une étape de décodage canal (41, 43) et une étape de décodage source (42,44), ladite étape de décodage canal délivrant une information de canal prise en compte dans ladite étape de décodage source, cette dernière délivrant une information a priori prise en compte dans ladite étape de décodage canal. 13. Procédé de décodage conjoint selon la revendication 12, caractérisé en ce qu'il comprend : # une première étape de décodage canal (41) ; # une première étape de décodage source (42), alimentée par ladite première étape de décodage canal ; # une seconde étape de décodage canal '43), alimentée par ladite première étape de décodage canal et ladite première étape de décodage source, via un entrelaceur (47) identique à l'entrelaceur mis en #uvre au codage, et alimentant ladite première étape de décodage canal, via un désentrelaceur (48) symétrique audit entrelaceur ; # une seconde étape de décodage source (44) alimentée par ladite seconde étape de décodage canal via ledit désentrelaceur (48), et alimentant ladite première étape de décodage canal (41). 14. Procédé de décodage conjoint source-canal d'un signal numérique reçu, le codage source mettant en #uvre un code entropique associant à chacun des mots d'un alphabet une séquence de bits distincte, dont la longueur est fonction de la probabilité d'occurrence dudit mot, caractérisé en ce qu'il met en #uvre un treillis de décodage canal, similaire au treillis de codage canal, dans lequel on associe à chaque état de chaque étage une information désignant la position du bit considéré dans l'arbre représentant ledit code entropique. 15. Procédé de décodage conjoint selon la revendication 14, caractérisé en ce qu'il comprend, pour chacun desdits états, les étapes suivantes : # ajout, aux deux branches arrivant dans ledit état, de la métrique du canal et de la métrique de la source ; # comparaison des deux nouvelles métriques obtenues, et sélection de la métrique la plus faible ; # si ladite information désignant la position indique la fin d'un mot, considérer que le n#ud est une feuille de l'arbre, sinon, passer au n#ud suivant dans l'arbre. 16. Procédé de décodage conjoint selon l'une quelconque des revendications 14 et 15, caractérisé en ce qu'il met en #uvre une procédure itérative. 17. Procédé de décodage conjoint selon la revendication 16, caractérisé en ce qu'il comprend les étapes suivantes : # premier décodage canal, mettant en #uvre un treillis de décodage canal dont chaque état dispose d'une information désignant la position du bit considéré dans l'arbre représentant ledit code entropique ; # deuxième décodage canal, alimenté par ledit premier décodage canal, via un entrelaceur identique à celui mis en #uvre au codage, et alimentant ledit premier décodage canal, via un désentrelaceur symétrique dudit entrelaceur ; # décodage source, alimenté par ledit deuxième décodage canal, via ledit désentrelaceur. 18. Dispositif de décodage de données numériques mettant en #uvre le procédé de décodage selon l'une quelconque des revendications 1 à 17. 19. Système de transmission d'un signal numérique, caractérisé en ce qu'il met en #uvre, à l'émission, un codage source entropique et un codage canal, et à la réception, un décodage selon le procédé de l'une quelconque des revendications 1 à 17.