FR2952252A1 - Procede et dispositif de decodage, produit programme d'ordinateur, moyen de stockage correspondants et noeud destination correspondants - Google Patents

Abstract

Il est proposé un procédé de décodage d'une pluralité de paquets de données reçus à travers un réseau de communication maillé pour la récupération de paquets sources transmis par un ou plusieurs nœuds sources, le réseau de communication maillé comprenant des nœuds relais générant des paquets combinés, chaque paquet combiné consistant en une combinaison linéaire de paquets sources. Lors du décodage par un nœud destination, ce procédé consiste à effectuer deux décodages consécutifs dont le premier est un décodage par groupe de paquets et le second est un décodage qui tient compte d'informations de vraisemblance résultant du premier décodage. Le fait d'effectuer d'abord un décodage avec des groupes de paquets permet d'exploiter les répétitions (ou redondances) de paquets dans un réseau maillé pour optimiser le taux d'erreur binaire lors du décodage de données sources transmises sur le réseau de communication.

Description

Procédé et dispositif de décodage, produit programme d'ordinateur, moyen de stockage correspondants et noeud destination correspondants. 1. DOMAINE DE L'INVENTION Le domaine de l'invention est celui des réseaux de communications.

Plus précisément, l'invention s'applique dans le contexte d'un réseau de communication dans lequel chaque paquet de données issu d'un noeud source est encodé, par exemple avec un codage de type LDPC (pour « Low Density Parity Check » en anglais, c'est-à-dire un code dont la matrice de contrôle de parité est peu dense), puis décodé par un noeud destination. 2. ARRIÈRE-PLAN TECHNOLOGIQUE On s'attache plus particulièrement dans la suite de ce document à décrire la problématique existante dans le domaine des décodages de paquets de données sources encodées selon un codage de type LDPC dans un réseau maillé de communication, à laquelle ont été confrontés les inventeurs de la présente demande de brevet. L'invention ne se limite bien sûr pas à ce domaine particulier d'application. La figure 1 illustre schématiquement un réseau maillé sans-fil constitué d'un noeud source 101, de plusieurs noeuds relais (102, 103, 104, 105) et d'un noeud destination 106. Bien évidemment, un tel réseau maillé peut comporter plusieurs noeuds sources 101 et plusieurs noeuds destinations 106. Dans la suite de la description, on se place à titre d'exemple illustratif dans le cas où les paquets de données émis par le noeud source 101 sont des paquets source encodés b1 et b2, résultant d'un encodage de canal du type LDPC. Sur la figure 1, les paquets sources encodés b1 et b2 sont relayés par les noeuds relais 102 à 105. Classiquement, les paquets sources encodés b1 et b2 peuvent être soit relayés tels quels (c'est-à-dire sans combinaison avec d'autres paquets de données), comme c'est le cas par les noeuds relais 102 et 103 dans l'exemple de la figure 1, soit combinés avec d'autres paquets de données, comme c'est le cas par les noeuds relais 104 et 105 dans l'exemple de la figure 1. Un noeud relais peut donc : - soit combiner des paquets de données reçus en entrée puis transmettre un paquet de données combiné, par exemple une combinaison linéaire des paquets de données reçus en entrée. Dans ce cas, le noeud relais est appelé « noeud relais combinant » ; - soit simplement relayer des paquets de données reçus en entrée, sans réaliser une combinaison entre paquets de données. Dans ce cas, le noeud relais est appelé « noeud relais non combinant ». Il est à noter qu'un paquet reçu en entrée d'un noeud relais peut être soit un paquet source encodé (b1 ou b2), soit une combinaison linéaire de paquets sources encodés. Dans l'exemple de la figure 1, le noeud destination 106 reçoit quatre paquets : - deux paquets y1 et y2 non combinés par des noeuds relais non combinant 102 et 103 respectivement, et - deux paquets combinés Pc et Pc', résultant chacun d'une même combinaison linéaire des paquets sources encodés b1 et b2. Cette combinaison linéaire (b1 + b2) est effectuée par le noeud relais combinant 104 pour le paquet combiné Pc et par le noeud relais combinant 105 pour le paquet combiné Pc'). On décrit maintenant la technique connue utilisée actuellement dans le contexte précité, c'est-à-dire un réseau maillé comprenant un noeud destination devant effectuer un décodage à partir de plusieurs paquets reçus, et dont certains paquets (dits paquets combinés) résultent d'une même combinaison linéaire. Une fois l'ensemble des paquets de données reçus sur son entrée, le noeud destination 106 applique ensuite un décodage LDPC sur chaque paquet de données reçu. Chaque décodage est effectué avec une matrice de contrôle de parité pour le décodage LDPC sur un vecteur d'entrée formé des quatre paquets reçus : y1, y2, Pc et Pc'. Si le décodage LDPC converge vers une solution correcte, le noeud destination retrouve les paquets de données sources émis à l'origine. Une telle convergence d'un décodage LDPC est obtenue lorsque les lignes et les colonnes de la matrice de contrôle de parité de décodage construite au niveau du noeud destination 106 sont indépendantes entre-elles, c'est-à-dire que la matrice de contrôle de parité ne comporte pas de cycles. En effet, ces cycles sont présents lorsque les lignes ou les colonnes de la matrice de parité présentent une certaine corrélation ou ressemblance entre-elles. Les cycles en question sont déterminés à partir d'une représentation sous la forme d'un graphe d'une matrice de parité LDPC. Ces graphes lies des noeuds de variables (qui correspondent aux bits de chaque mot de code LDPC) et des variables de parité (qui correspondent aux bits de parité dans un mot de code LDPC). Un cycle sur un graphe est un chemin sur le graphe qui permet de partir d'un noeud et de revenir à ce même noeud sans passer par la même branche. La taille d'un cycle est donnée par le nombre de branches contenues dans le cycle. En anglais, la taille du cycle le plus court est appelée "girth". La présence de cycles dans le graphe dégrade les performances de décodage par un phénomène d'auto-confirmation lors du décodage. Or, lorsque le décodage est effectué à partir de paquets reçus qui résultent d'une même combinaison linéaire, cela conduit inévitablement à une corrélation entre les lignes de la matrice de parité, même en cas d'erreurs différentes présentes sur chacun des paquets. Des erreurs différentes peuvent entacher les paquets combinés lorsque ces derniers sont transmis à travers des canaux différents vers le noeud destination. C'est le cas dans l'exemple de la figure 1 où les paquets combinés Pc et Pc' sont issus d'une même combinaison de base, et donc corrélés entre-eux. Les lignes de la matrice de décodage ne sont donc pas indépendantes entre-elles.

Ainsi, pour un réseau maillé, le décodage LDPC classique avec une matrice de parité n'est pas optimal du fait de la présence de ces répétitions de messages au sein du réseau de communication. 3. OBJECTIFS DE L'INVENTION L'invention, dans au moins un mode de réalisation, a notamment pour objectif de pallier ces différents inconvénients de l'état de la technique. Plus précisément, dans au moins un mode de réalisation de l'invention, un objectif est de fournir une technique permettant d'optimiser le taux d'erreur binaire lors du décodage de données sources transmises sur un réseau de communication, dans le contexte précité, c'est-à-dire dans le cadre d'un réseau maillé comprenant un noeud destination devant effectuer un décodage à partir de plusieurs paquets reçus, et dont certains paquets (dits paquets combinés) résultent d'une même combinaison linéaire mais effectuée par au moins un noeuds relais combinant différent ( pour chaque paquet combiné). Dans au moins un mode de réalisation de l'invention, un autre objectif est de fournir une technique permettant la mise en oeuvre d'une solution adaptée à n'importe quel type de combinaison de paquets de données effectuée par les noeuds relais. Un autre objectif de l'invention est de fournir une technique permettant de ne pas modifier les opérations d'encodage effectuées par les noeuds sources et les opérations de combinaison ou de relais des noeuds relais. Un autre objectif est de fournir une telle technique permettant d'optimiser la bande passante. Un autre objectif est de fournir une telle technique qui soit simple à mettre en oeuvre et peu coûteuse. 4. EXPOSÉ DE L'INVENTION Dans un mode de réalisation particulier de l'invention, il est proposé un procédé 15 de décodage d'une pluralité de paquets de données reçus à travers un réseau de communication maillé pour la récupération de paquets sources transmis par un ou plusieurs noeuds sources, le réseau de communication maillé comprenant des noeuds relais générant des paquets combinés, chaque paquet combiné consistant en une combinaison linéaire de paquets sources, De manière remarquable, ce procédé est mis en oeuvre par un noeud destination et comprend des étapes consistant à : - former des groupes de paquets reçus comprenant des paquets combinés, chaque groupe ne comprenant pas plus d'un paquet combiné parmi une pluralité de paquets combinés qui consistent en une même combinaison linéaire de paquets sources ; - pour chaque groupe, effectuer un premier décodage des paquets dudit groupe, ledit premier décodage étant effectué par un premier décodeur mettant en oeuvre un algorithme de propagation de croyance délivrant une information de vraisemblance pour ledit groupe ; 20 25 - combiner les informations de vraisemblance obtenues par le premier décodage effectué pour les différents groupes, pour obtenir une combinaison d'informations de vraisemblance ; - effectuer un second décodage de ladite combinaison d'informations de vraisemblance, ledit second décodage étant effectué par un second décodeur apte à traiter des informations de vraisemblance. Ainsi, ce mode de réalisation particulier de l'invention repose sur une approche tout à fait nouvelle et inventive consistant, lors du décodage par un noeud destination, à effectuer deux décodages consécutifs (au lieu d'un seul décodage dans la technique classique), dont le premier est un décodage par groupe de paquets et le second est un décodage qui tient compte d'informations de vraisemblance résultant du premier décodage. Le fait d'effectuer d'abord un décodage avec des groupes de paquets permet d'exploiter les répétitions (ou redondances) de paquets dans un réseau maillé pour optimiser le taux d'erreur binaire lors du décodage de données sources transmises sur le réseau de communication. La présente invention trouve plus particulièrement son application lors d'un décodage mettant en oeuvre des matrices de décodage creuses conjointement avec une application de l'algorithme de propagation de croyance, de manière à faire converger ledit décodage, par exemple de type LDPC, vers une solution correcte. En effet, grâce à l'utilisation de groupes de paquets de données, chaque premier décodage est réalisé avec une matrice de décodage de faible taille et dont les lignes ne sont pas corrélées entre-elle. Le taux d'erreur binaire s'en trouve alors réduit lors de l'application du second décodage sur un unique vecteur formé à partir des valeurs de confiance de chaque groupe.

Ainsi, la présente invention permet de s'adapter à n'importe quel type de combinaison de paquets de données effectué par les noeuds relais. En outre, l'étape de combinaison des informations de confiance permet avantageusement d'optimiser la bande passante en moyennant les informations de confiance. Cette combinaison permet d'avoir une valeur moyenne de cette information avec une valeur faible de l'écart-type du bruit lié au canal de communication.

De façon avantageuse, chaque groupe de paquets reçus comprend des paquets de données correspondant à un même ensemble d'au moins un paquet source transmis par le ou lesdits noeuds sources. Ainsi, la présente invention permet l'utilisation de matrice de décodage de taille moindre et donc de réduire les temps de calcul lors du décodage des données sources par le noeud destination. De façon avantageuse, les premier et second décodages sont du type LDPC. Ainsi, le décodage s'en trouve amélioré, l'algorithme de propagation de croyance permettant d'améliorer un décodage lorsque les matrices de décodage sont creuses, ce qui est le cas pour un décodage LDPC. Avantageusement, les premier et second décodages sont des décodages dans le domaine logarithmique, l'étape consistant à combiner étant une étape de sommation ou de sommation pondérée de chaque information de confiance. Ainsi, on limite les opérations de calcul.

Selon une caractéristique avantageuse, chaque combinaison linéaire est effectuée au moyen d'une opération de type « OU exclusif ». Ainsi, on simplifie les opérations de calcul. Dans un autre mode de réalisation, l'invention concerne un produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur. Ce produit programme d'ordinateur comprend des instructions de code de programme pour la mise en oeuvre du procédé précité (dans l'un quelconque de ses différents modes de réalisation), lorsque ledit programme est exécuté sur un ordinateur. Dans un autre mode de réalisation, l'invention concerne un moyen de stockage lisible par ordinateur stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur pour mettre en oeuvre le procédé précité (dans l'un quelconque de ses différents modes de réalisation). Dans un autre mode de réalisation, l'invention concerne un noeud destination pour le décodage d'une pluralité de paquets de données reçus à travers un réseau de communication maillé pour la récupération de paquets sources transmis par un ou plusieurs noeuds sources, le réseau de communication maillé comprenant des noeuds relais générant des paquets combinés, chaque paquet combiné consistant en une combinaison linéaire de paquets sources. De manière remarquable, ledit noeud destination comprend : - des moyens de formation de groupes de paquets reçus comprenant des paquets combinés, chaque groupe ne comprenant pas plus d'un paquet combiné parmi une pluralité de paquets combinés qui consistent en une même combinaison linéaire de paquets sources ; - des premiers moyens de décodage permettant d'effectuer, pour chaque groupe, un premier décodage des paquets dudit groupe, ledit premier décodage étant effectué par un premier décodeur mettant en oeuvre un algorithme de propagation de croyance délivrant une information de vraisemblance pour ledit groupe ; - des moyens de combiner les informations de vraisemblance obtenues par le premier décodage effectué pour les différents groupes, pour obtenir une combinaison d'informations de vraisemblance ; - des seconds moyens de décodage permettant d'effectuer un second décodage de ladite combinaison d'informations de vraisemblance, ledit second décodage étant effectué par un second décodeur apte à traiter des informations de vraisemblance. De manière avantageuse, ledit noeud destination comprend des moyens de sélection d'un même ensemble d'au moins un paquet source transmis par le ou lesdits noeuds sources, chaque groupe de paquets reçus comprenant des paquets de données correspondant audit même ensemble. Avantageusement, les premier et second décodages sont du type LDPC. De manière avantageuse, les premier et second moyens de décodages opèrent dans le domaine logarithmique, lesdits moyens de combinaison des informations de vraisemblance effectuant une sommation ou une sommation pondérée de chaque information de confiance. En outre, chaque combinaison linéaire est effectuée au moyen d'une opération de type « OU exclusif ». 5. LISTE DES FIGURES D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante, donnée à titre d'exemple indicatif et non limitatif, et des dessins annexés, dans lesquels : - la figure 1 (décrite en relation avec l'art antérieur) illustre schématiquement un exemple classique d'un réseau de communication maillé sans fil à multiple chemins comprenant un noeud source, un noeud destination et des noeuds relais ; - la figure 2 illustre schématiquement un graphe de Tanner (a) et un graphe organisé (b) en vue d'un décodage sur graphe ; - la figure 3 illustre schématiquement un schéma de codage dans un réseau de communication maillé comprenant deux noeuds sources, deux noeuds relais, et un noeud destination, selon un mode de réalisation particulier de l'invention ; - la figure 4 illustre schématiquement une architecture d'un décodeur d'un noeud destination, selon un mode de réalisation particulier de l'invention ; - la figure 5 illustre schématiquement un procédé du décodage mis en oeuvre par le décodeur de la figure 4, selon un mode de réalisation particulier ; - la figure 6 illustre la courbe du taux d'erreur binaire en fonction du rapport signal à bruit pour un décodage sans noeuds relais, avec deux noeuds relais (méthode classique) et avec deux noeuds relais selon un mode de réalisation particulier de l'invention ; 20 - la figure 7 illustre schématiquement un dispositif adapté en mettre en oeuvre le procédé de la figure 5, selon un mode de réalisation particulier. 6. DESCRIPTION DÉTAILLÉE La figure 3 illustre schématiquement un exemple d'un schéma de codage dans un réseau maillé de communication comprenant deux noeuds source, deux noeuds relais 25 et un noeud destination, selon un mode de réalisation particulier de l'invention. Plus précisément, la figure 3 illustre un schéma de codage conjoint LDPC et réseau dans un même réseau maillé. Classiquement, un paquet reçu en entrée d'un noeud relais peut être soit un paquet source encodé, soit une combinaison linéaire de paquets sources encodés. Dans 30 ce dernier cas, l'opération de combinaison effectuée par les noeuds relais correspond au codage réseau. 10 15 Soit deux noeuds sources 301 et 302 appliquent un codage du type LDPC respectivement 306 et 307. Les noeud sources 301 et 302 transmettent chacun un paquet source encodé, respectivement bl et b2 : - à chaque noeud relais 303 et 304, via des canaux de communication 311, 312, 313 et 314 ; - au noeud destination 305 via des canaux de communication 315 et 318. Le noeud destination 305 reçoit ainsi directement des noeuds sources 301 et 302 les paquets b1 et b2 si l'on suppose le canal de transmission sans erreurs de communication. Si l'on considère les erreurs de transmission sur les canaux de transmission, aux paquets de données sources encodés b1 et b2 correspond respectivement des paquets de données Y1 et Y2, c'est-à-dire les paquets de données sources b1 et b2 entachés d'erreurs de communication.

Les noeuds relais 303 et 304 appliquent quant à eux une combinaison linéaire des paquets sources encodés b1 et b2 reçus en entrée, respectivement au moyen des blocs 308 et 309, afin de déterminer des paquets combinés, respectivement YR1 et YR2, qui seront ensuite transmis au noeud destination 305 via les canaux 316 et 317. Selon un mode de réalisation particulier de l'invention, la combinaison des paquets par les noeuds relais 303 et 304 peut être effectuée par une simple opération d'addition « OU exclusif » (plus connue sous l'abréviation « XOR ») sur l'ensemble des bits des paquets à combiner. Nous allons maintenant décrire un exemple de combinaison de paquets reçus en entrée d'un noeud relais (par exemple le noeud relais 303 de la figure 3). Ces paquets peuvent être soit des paquets sources encodés b1 et b2 non modifiés soit des combinaisons linéaires des paquets sources b1 et b2. Soit deux paquets sources d'une taille de 10 bits chacun : - un paquet b1 = [1 0 0 1 0 0 1 10 0] et ; - un paquet b2 = [0 1 0 1 1 0 1 0 0 0].

Le paquet combiné résultant s'écrit alors (en utilisant l'opération « OU exclusif ») : b1XOR b2 = [1 10 0 10 0 1 0 0] Un raisonnement identique est appliqué pour le noeud relais 304 de la figure 3. Les paquets non combinés Y1, Y2 correspondent aux paquets de données sources b1 et b2 reçus directement des noeuds sources 301 et 302 respectivement et éventuellement entachés d'erreurs de transmission du fait qu'un canal de communication d'un réseau est assujetti à des erreurs de communication lors de la transmission de données. Les paquets non combinés YR1 et YR2 correspondent quant à eux aux combinaisons des paquets de données sources encodés b1 et b2 ou bien des combinaison paquets de données Y1, Y2 éventuellement entachés d'erreurs. Ces deux paquets combinés YR1 et YR2 sont issus respectivement des deux noeuds relais 303 et 304. Le noeud destination 305 de la figure 3 reçoit donc quatre paquets (dans l'exemple de la figure 3) : Y1, Y2, YR1 et YR2. Ces paquets sont ensuite décodés par ce noeud destination au moyen d'un décodage conjoint réseau et LDPC à partir des quatre paquets reçus et d'une matrice de parité HH (ou matrice de décodage).

Nous allons maintenant décrire un exemple de calcul de la matrice de parité HH. Soit H la matrice de parité utilisée pour l'encodage des messages au niveau des noeuds source 301 et 302. Les paquets transmis par les noeuds sources sont constitués de blocs. Chacun de ces blocs est un mot de code LDPC noté b1 (pour le noeud source 301) et b2 (pour le noeud source 302). Ces deux derniers paquets satisfont aux deux équations suivantes: H. biT = 0 H. b2T = 0 Chacun des noeuds relais 303 et 304 (dans l'exemple de la figure 3) calcul quant à eux un paquet combiné b3 = b1 XOR b2. Une matrice de parité globale peut ainsi être déterminée en fonction de la matrice de parité H et de la relation entre b3, b2 et b1. La matrice de parité globale s'écrit : / H zeros(K, N) zeros(K, N) HH = zeros(K, N) H zeros(K, N) (1) I (N, N) I (N, N) I (N, N) / avec : * N la taille du mot de code LDPC; * K le nombre de bit de parité d'un mot de code LDPC; * zeros(K,N) représente une matrice à éléments nuls et de taille KxN; * I(N,N) représente une matrice identité NxN. La figure 4 illustre schématiquement une architecture d'un décodeur 400 conjoint LDPC et réseau, selon un mode de réalisation particulier, pour un réseau maillé comprenant au moins deux noeud relais et deux noeuds sources (correspondants aux deux noeuds sources 301 et 302 de la figure 3). Ce décodeur 400 correspond au décodeur 310 du noeud destination 305 de la figure 3. Selon un mode de réalisation particulier de l'invention, le décodeur 400 (du noeud destination 305) reçoit en entrée au moins deux groupes différents de paquets de données, chaque groupe comprenant des paquets non combinés, identiques pour tous les groupes, et un paquet combiné, différent pour chaque groupe, chaque paquet non combiné résultant de la transmission, par un noeud source différent, d'un paquet source encodé différent compris dans un ensemble déterminé de paquets sources encodés, tous les paquets combinés résultant d'une même combinaison linéaire des paquets sources encodés dudit ensemble, ladite combinaison linéaire étant effectuée par au moins un noeuds relais combinant différent pour chaque paquet combiné ; Dans l'exemple de la figure 4, le décodeur 400 (du noeud destination 305) reçoit en entrée n groupes différents de paquets de données, chaque groupe étant un triplet de paquets comprend les deux paquets non combinés Y1 et Y2 issus des noeuds sources et un paquet combiné YRi (i allant de 1 à n) issu d'un noeud relais i, le noeud destination recevant n paquets combinés issus de n noeuds relais de l'ensemble des noeuds relais du réseau maillé. Selon un mode de réalisation particulier de l'invention, sur l'ensemble des triplets de paquets (Y1, Y2, YRn) est appliqué un premier décodage LDPC effectué respectivement par des premier décodeurs LDPC 401, 402,...40n. Chaque premier décodage LDPC est effectué à partir du triplet de paquets correspondant et de la matrice HH, avec application d'un graphe de Tanner et des étapes d'un algorithme de « propagation de croyance ».

Nous allons maintenant détailler brièvement comment se construit un graphe de Tanner ainsi que les différentes étapes mise en oeuvre lors de l'exécution d'un algorithme de « propagation de croyance » pour réaliser un décodage plus connue sous le nom de « décodage sur graphe ». Un code peut être définit comme un ensemble de variables qui satisfont un ensemble de contraintes. Un graphe peut alors être construit de façon à représenter ces relations entre variables et contraintes. La figure 2 illustre schématiquement un tel graphe sur lequel une variable est représentée par un carré et une contrainte par un cercle. Soit C le code linéaire sur le corps de Galois des éléments binaires défini par sa matrice de vérification de parité H. 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 H 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 Le code linéaire C est l'ensemble des huit-uplets x={xl ,x2 ,x3 ,x4,x5 ,x6,x7,x8} 15 qui satisfont à l'équation : H.xt = O. Ainsi, vérifier que x appartient au code linéaire C équivaut à vérifier la condition : [xl +x2 +x3=0] et ; 20 [x4 +x5 +x6=0] et ; [xl +x4 +x7=0] et [x2 +x5 +x8=0]. Les contraintes consistent en la satisfaction de toutes les parités et la fonction associée à cette contrainte est la somme modulo 2. La figure 2 illustre le graphe correspondant sous deux représentations, où le 25 cercle représente la somme modulo 2. Ce graphe est plus connu sous le nom de graphe de Tanner. 10 Ce graphe de Tanner est notamment utilisé pour mettre en place un décodage à décision quantifiées. A chaque variable du code est associé la valeur du symbole reçu après sa transmission, cette valeur pouvant être quantifiée.

Un algorithme dit de « propagation de croyance », ou de « propagation de message» est alors mis en place avec le graphe comme support

Plusieurs versions de l'algorithme de propagation de croyance existent.

Nous allons maintenant décrite la version la plus implémentée manipulant des valeurs logarithmique et plus connu sous le nom d'algorithme de décodage dans le domaine logarithmique. En effet, les calculs dans le domaine logarithmique sont

souhaitables car les multiplications sont transformées en additions, ce qui rend les calculs beaucoup moins complexes.

Cet algorithme est plus amplement décrit dans le document "An introduction to Low Density Parity Check (LDPC) Codes", Jian Sun, WCRL Seminar Series, 3 June 2003" L'algorithme de décodage dans le domaine logarithmique se définit comme suit : L( )=aï. a; = sign (L, (y,; » f3i; = abs(L(c i; )) A l'étape d'initialisation: L(c, )= 2y/z 6 L(; )= L(ci ) Avec: * y, le "i" ème échantillon bruité reçu et modulé en BPSK (1 pour 0 et -1 pour 1)) * 6 l'écart type du bruit Une première étape (étape 1) consiste à l'envoie d'un message à un noeud de contrainte puis le calcul de la réponse L(r,,) :25 L(r,. )= 0 1,~(f3 ). na PER / PERy 1 Avec: ~(x)= log/ ex + Une quatrième étape (étape 4) permet de prendre une décision : Si L(Qi )< 0 alors c, =1 Sinon c, = 0 Dans cet algorithme de propagation de croyance, la connaissance de la valeur de l'écart type du bruit o est nécessaire. Ceci implique une estimation du rapport 15 signal à bruit. Une simplification décrite ci-après permet de s'affranchir de cette contrainte. Cependant, il en résulte un décodage un décodage moins optimal. Cette simplification est plus amplement décrite dans le document « A Bit-Serial Approximate Min-Sum LDPC Decoder and FPGA Implementation", Ahmad Darabiha, Anthony Chan 20 Carusone and Frank R. Kschischang, IEEE International Symposium on Circuits and Systems (ISCAS) 2006, Island of Kos, Greece. » En effet, à l'initialisation, on peut considérer: L(ci )=Y; 10 vex -1/ Une seconde étape (étape 2) consiste en la réception des réponses et le calcul d'un nouveau message L(gil )= L(c, )+L(rj,, ) ` Puis les étapes 1 et 2 sont répétées pour un nombre d'itérations prédéfini. Une troisième étape (étape 3) consiste à fournir une décision quantifiée à partir des valeurs logarithme calculées : )= )+ Y,L(r1,) 5 15 20 25 du calcul de

. En effet, cette dernière peut être approximée par qui est égale à min j3,, j . L'expression de l'étape 1 devient alors : L (;, )= min f3;,j . fl ai'j i ER/ Selon un mode de réalisation particulier de l'invention, chaque premier décodeur met en oeuvre uniquement les étapes d'initialisation, 1, 2 et 3 de l'algorithme de propagation de croyance. Ainsi, à chaque premier décodage d'un groupe (ou triplet de paquets yl, y2 et yRi) correspond en sortie de chaque premier décodeur LDPC (401, 402,...40n) un vecteur de valeurs de logarithme de vraisemblances, respectivement (L1, L2...Ln). En effet, chaque vecteur des valeurs de vraisemblances Li est la concaténation des vecteurs de vraisemblances des paquets yl, y2 et yRi. Ces vecteur, Li, sont obtenus à partir de l'application des étapes 1, 2 et 3 de l'algorithme de propagation de croyance en utilisant la matrice HH donnée par l'équation 1. Dans le cas où un des paquets yl, y2 et yRi est manquant avant le premier décodage, les valeurs initiales du logarithme de vraisemblances du paquet manquant sont initialisées avec la valeur zéro.

Ces valeurs de logarithmes de vraisemblances (L1, L2...Ln) calculées sont ensuite additionnées, bit par bit, au moyen d'un bloc d'addition 404. Le résultat Lr généré en sortie de ce bloc d'addition est alors un vecteur de taille 3*N si chaque groupe comporte trois paquets.

Ce résultat Lr est ensuite utilisé par un deuxième décodeur LDPC 405. Tout comme les premiers décodeurs LDPC 401, 402,...40n, le second décodeur LDPC 405 utilise la matrice de parité HH pour effectuer son décodage. En effet, les paquets b1, b2 et b3=b1 XOR b2 satisfont l'équation suivante: Une autre simplification peut être faite lors / / 1'expressionO( in13;,, l'expression O bl b2 bl xor b2 / H zeros(K, N) zeros(K, N) zeros(K, N) H zeros(K, N) I(N,N) I(N,N) I(N,N) /zeros(K,1)-zeros(K,1) zeros(N,1) ou bien encore : HH . B = zeros(K+K+N,1) avec B = [b1;b2;b1 xor b2] La figure 5 illustre schématiquement un procédé du décodage 500 mis en oeuvre par le décodeur 400 de la figure 4, ce décodeur 400 étant implanté au niveau du noeud destination 305 (figure 5).

Une première étape 501 consiste à initialiser le décodeur 400. Une seconde étape 502 permet de réceptionner : - au moins deux paquets de données non combinés (c'est-à-dire transmis directement par les noeuds sources 301 et 302 dans l'exemple d'architecture de la figure 3) et ; - n paquets combinés YR1, YR2,...YRn (c'est-à-dire les paquets générés et transmis par n noeuds relais parmi les noeuds relais appartenant au réseau maillé) Une troisième étape 503 détermine ensuite n groupes de paquets (ou n triplets), chaque nième groupe (ou triplet) comprenant au moins deux paquets non combinés et un nième paquet combiné.

Puis, dans une étape 504, un premier décodage LDPC (comme expliqué plus en détail précédemment) avec application du graphe de Tanner et d'un algorithme de « propagation de croyance » est effectué pour chacun des groupes afin de calculer une valeur d'un logarithme de vraisemblance Li associé à un groupe i parmi l'ensemble des groupes de paquets (ou triplets).

Ce premier décodage LDPC est ainsi effectué à partir de chaque triplet de paquets et de la matrice HH introduite précédemment. Une étape 505 permet ensuite d'additionner, au moyen du bloc d'addition 404 de la figure 4, les valeurs de logarithme de vraisemblance. On obtient alors un vecteur somme Lr des logarithmes de vraisemblance.

Puis, dans une étape 506, un second décodage LDPC est effectué à partir du vecteur somme Lr des logarithmes de vraisemblance. Ce second décodage est effectué par le second décodeur 405 de la figure 4. Ce dernier, comme les premiers décodeurs de l'étape 504, utilise la matrice de parité HH pour effectuer le second décodage. La figure 6 illustre schématiquement une évolution graphique du taux d'erreur binaire (ou « BER » pour « Bit Error Rate » en anglais) en fonction du rapport signal à bruit (ou « SNR » pour « Signal to Noise Ratio » en anglais) pour : - un décodage sans noeuds relais (représenté par des carrés sur une courbe 3) ; - un décodage classique avec deux noeuds relais (représenté par des ronds sur une courbe 2) ; - un décodage avec deux noeuds relais (représenté par des étoiles sur une courbe 1), selon un mode de réalisation particulier de la présente invention. La courbe de la figure 6 montre nettement que, pour un décodage avec deux noeuds relais, le taux d'erreur binaire obtenu selon le procédé de la présente invention (figure 5 ; courbe 1) est plus faible que celui obtenu avec la méthode classique (courbe 2), et ceci pour les mêmes valeurs du rapport signal à bruit. Le décodage LDPC classique, dans un réseau maillé, de deux paquets de données sources et de deux paquets combinés issus de deux noeuds relais correspond à un décodage LDPC effectué avec la matrice suivante (c'est-à-dire sans un premier décodage avec estimation des valeurs logarithmiques de chaque groupe de paquets de données, ces valeurs étant ensuite utilisées pour un second décodage LDPC).

/ H zeros(K, N) zeros (K, N) zeros(K, N) zeros(K, N) H zeros (K,N ) zeros(K, N) I(N,N) I(N,N) 1(N, N) zeros(N, N) I(N,N) 1(N, N) zeros(N, N) 1(N, N) / Dans ce décodage classique, le décodage LDPC est donc effectué avec la matrice HHH et un vecteur d'entrée [Y1; Y2; YR1; YR2] (dans l'exemple de la figure 20 3 avec réception de deux paquets combinés YR1 et YR2). Dans cet exemple, il apparaît une corrélation (ou vraisemblance) entre les deux dernières lignes de la matrice HHH correspondant aux lignes pour le décodage des deux paquets issus des deux noeuds relais. Dans cet exemple de matrice, pour une configuration donnée d'un réseau de 25 communication, cette corrélation entre les lignes est présente uniquement lorsque les noeuds relais effectuent chacun une même combinaison linéaire des paquets de données sources. Tel que discuté précédemment, un décodage (par exemple LDPC) effectué avec une telle matrice présente un taux d'erreur binaire plus important en 10 15 HHH = comparaison à une matrice de décodage HHH idéale dont les lignes et colonnes ne serait pas corrélées entre-elles. Cette corrélation des lignes et colonnes de la matrice de décodage est d'autant plus sensible pour un décodage de type LDPC nécessitant une matrice creuse, c'est-à- dire une matrice à faible corrélation entre les lignes et colonnes. -Egalement, cette valeur du taux d'erreur binaire est nettement plus faible si on la compare à la valeur obtenue pour un décodage LDPC sans noeuds relais (courbe 3) effectué avec la matrice H et un paquet bl. Il est à noter que cette simulation a été effectuée avec une modulation BPSK (pour « Binary Phase Shift Keying » en anglais). La figure 7 illustre schématiquement un dispositif de communication 700 adapté en mettre en oeuvre le procédé de la figure 5, selon un mode de réalisation particulier. Ce dispositif de communication 700 comprend : - un bloc 713 permettant d'exécuter le procédé 500 (figure 5) . Ce bloc 713 contient des blocs 714, 715, 716 et 717 correspondant respectivement à un bloc de sélection des groupes de paquets de données, à un bloc mettant en oeuvre le premier décodage LDPC pour chaque groupe de paquets (ou triplets), à un bloc d'addition des logarithmes de vraisemblance et à un bloc mettant en oeuvre le second décodage LDPC ; - un bloc 711 « CPU IF » correspondant à l'interface entre le CPU et la partie bande de base (ou « baseband » en anglais) ; - un bloc 712 correspondant à la mémoire de données ; - un bloc 718 correspondant à un circuit de réception des paquets de données ; - un bloc 719 correspondant à un circuit d'émission des paquets de données ; - un bloc 730 correspondant à une mémoire vive (ou « RAM » pour « Random Access Memory » en anglais) ; - un bloc 740 correspondant à une mémoire morte (ou « ROM » pour « Read Only Memory » en anglais) ; - un bloc 750 correspondant à un transmetteur radiofréquence ; 25 30 - un bloc 760 correspondant à une unité de traitement (ou « CPU » pour « Central Processing Unit » en anglais). On notera que l'invention ne se limite pas à une implantation purement logicielle, sous la forme d'une séquence d'instructions d'un programme informatique, mais qu'elle peut aussi être mise en oeuvre sous forme matérielle ou toute forme mixant une partie matérielle et une partie logicielle. Dans le cas où l'invention est implantée partiellement ou totalement sous forme logicielle, la séquence d'instructions correspondante pourra être stockée dans un moyen de stockage amovible (tel que par exemple une disquette, un CD-ROM ou un DVD-ROM) ou non, ce moyen de stockage étant lisible par un ordinateur ou un microprocesseur. Ainsi, l'invention se réalise indifféremment comme un programme exécuté : - sur une machine de calcul reprogrammable tel un ordinateur personnel (ou « PC » pour « Personnal Computer » en anglais), un processeur de signaux numériques (ou « DSP » « pour Digital Signal Processor ») ou un microcontrôleur ; - ou bien encore sur une machine de calcul dédiée comme un ensemble de portes logiques (par exemple un circuit logique programmable (ou « FPGA » pour Field-Programmable Gate Array en anglais) ou un circuit intégré spécialisé (ou « ASIC » pour « Application-Specific Integrated Circuit » en anglais)).20

Claims (12)

1. REVENDICATIONS1. Procédé de décodage d'une pluralité de paquets de données reçus à travers un réseau de communication maillé pour la récupération de paquets sources transmis par un ou plusieurs noeuds sources, le réseau de communication maillé comprenant des noeuds relais générant des paquets combinés, chaque paquet combiné consistant en une combinaison linéaire de paquets sources, le procédé étant mis en oeuvre par un noeud destination et caractérisé en ce qu'il comprend des étapes consistant à : - former des groupes de paquets reçus comprenant des paquets combinés, chaque groupe ne comprenant pas plus d'un paquet combiné parmi les paquets combinés consistant en une même combinaison linéaire de paquets sources ; - pour chaque groupe, effectuer (504) un premier décodage des paquets dudit groupe, ledit premier décodage étant effectué par un premier décodeur mettant en oeuvre un algorithme de propagation de croyance délivrant une information de vraisemblance pour ledit groupe ; - combiner (505) les informations de vraisemblance obtenues par le premier décodage effectué pour les différents groupes, pour obtenir une combinaison d'informations de vraisemblance ; - effectuer (506) un second décodage de ladite combinaison d'informations de vraisemblance, ledit second décodage étant effectué par un second décodeur apte à traiter des informations de vraisemblance.
2. 2. Procédé de décodage selon la revendication 1, caractérisé en ce que chaque groupe de paquets reçus comprend le même ensemble d'au moins un paquet source.
3. 3. Procédé de décodage selon l'une quelconque des revendications 1 et 2, caractérisé en ce que les premier et second décodages sont du type LDPC.
4. 4. Procédé de décodage selon l'une quelconque des revendications 1 à 3, caractérisé en ce que les premier et second décodages sont des décodages dans le domaine logarithmique, et en ce que l'étape (505) consistant à combiner est une étape de sommation ou de sommation pondérée de chaque information de confiance.
5. 5. Procédé de décodage selon l'une quelconque des revendications 1 à 4, caractérisé en ce que chaque combinaison linéaire est effectuée au moyen d'une opération de type « OU exclusif ».
6. 6. Produit programme d'ordinateur caractérisé en ce qu'il comprend des instructions de code de programme pour la mise en oeuvre du procédé selon au moins une des revendications 1 à 5, lorsque ledit programme est exécuté sur un ordinateur.
7. 7. Moyen de stockage lisible par ordinateur stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur pour mettre en oeuvre le procédé selon au moins une des revendications 1 à 5.
8. 8. Noeud destination pour le décodage d'une pluralité de paquets de données reçus à travers un réseau de communication maillé pour la récupération de paquets sources transmis par un ou plusieurs noeuds sources, le réseau de communication maillé comprenant des noeuds relais générant des paquets combinés, chaque paquet combiné consistant en une combinaison linéaire de paquets sources, ledit noeud destination étant caractérisé en ce qu'il comprend : - des moyens de formation de groupes de paquets reçus comprenant des paquets combinés, chaque groupe ne comprenant pas plus d'un paquet combiné parmi les paquets combinés consistant en une même combinaison linéaire de paquets sources ; - des premiers moyens de décodage permettant d'effectuer, pour chaque groupe, un premier décodage des paquets dudit groupe, ledit premier décodage étant effectué par un premier décodeur mettant en oeuvre un algorithme de propagation de croyance délivrant une information de vraisemblance pour ledit groupe ; - des moyens de combiner les informations de vraisemblance obtenues par le premier décodage effectué pour les différents groupes, pour obtenir une combinaison d'informations de vraisemblance ; - des seconds moyens de décodage permettant d'effectuer un second décodage de ladite combinaison d'informations de vraisemblance, ledit second décodage étant effectué par un second décodeur apte à traiter des informations de vraisemblance.
9. 9. Noeud destination selon la revendication 8, caractérisé en ce qu'il comprend des moyens de sélection d'un même ensemble d'au moins un paquet source transmis par le 30 ou lesdits noeuds sources, chaque groupe de paquets reçus comprend le même ensemble d'au moins un paquet source. 20 25
10. 10. Noeud destination selon l'une quelconque des revendications 8 et 9, caractérisé en ce que les premier et second décodages sont du type LDPC.
11. 11. Noeud destination selon l'une quelconque des revendications 8 à 10, caractérisé en ce que les premier et second moyens de décodages opèrent dans le domaine logarithmique, et en ce que lesdits moyens de combinaison des informations de vraisemblance effectuent une sommation ou une sommation pondérée de chaque information de confiance.
12. 12. Noeud destination selon l'une quelconque des revendications 8 à 11, caractérisé en ce que chaque combinaison linéaire est effectuée au moyen d'une opération de type « OU exclusif ».