Brevet FR3011409A1 — publié le 20150403

MÉTHODE DE DÉCODAGE .à,diAP P'AR ÉSEAU DE POINTS AUGMENTÉ DESCRIPTION INE TECHNIQUE La présente invention concerne le domaine des télécommunications numériques et plus particulièrement du décodage d'une source d'information dont les symboles ne suivent pas une distribution uniforme. Elle s'applique notamment au décodage dans des réseaux utilisant une technique de codage réseau de couche physique (Physical Layer 10 Network Coding). ÉTAT DE LA TECHNQUE Aif1-11EURE Les communicalions numériques s'appuient en général sur un modèle de canal discret entre un émetteur capable de transmettre des messages constitués de symboles 15 et un récepteur capable de restituer le message à partir du signal reçu. Un canal discret peut être considéré comme un systéme stochastique acceptant en entrée dessyrnbo|esx. appartenant à un alphabet et fournissant en sortie des symboles y, appartenant à un alphabet 4, les entrées et sorties du canal étant liées par un modèle probabiliste défini par les probabilités : 2O = (1) Le canal est en pratique bruyant autrement dit les symboles en sortie du canal sont affectés par un bruit que l'on suppose généralement blanc et gaussien (BBAG). On 25 note Ri Z, 1,...,m, les échantillons de signal reçu où les Z. sont des échantillons de bruit. Le récepteur recherche la séquence de syrnbo|es la plus probable compte tenu du signal reçu, autrement dit recherche la séquence de symboles d'entrée qui maximise la probabilité conditionnelle : = r (2) 1,-,R m que l'on notera plus simplement R) où X est le vecteur des symboles d'entrée que l'on cherche à estimer et R le vecteur des échantillons du signal reçu. En d'autres termes, on recherche le vecteur maximisant la probabilité : 10 P X1R), P R )P(X)/ P(R) (3) Le terme P(R) étant indépendant de X, il suffit de rechercher le vecteur Î maximisant la probabilité : 15 P(R1X)P(X) (4) On distingue à ce stade deux types de méthodes de décodage. Le premier type de décodage utilise un critère dit à maximum de vraisemblance ou ML (Maximum Likelihood), rcpn58nt sur l'hypothèse que les symboles de l'alphabet sont 20 équiprobables. Il suffit alors de maximiser P _À` ) c'est-à-dire, lorsque le canal est sans mémoire : arg max P( R ) lrgmax P xi (5) 25 Cette méthode de décodage est optirna|e lorsque les symboles d'entrée sont effectivement équiprobables, c'est-à-dire lorsque l'alphabet J, présente une distribution de probabilité uniforme. Un second type de décodage, dit de Maximum A Posteriori ou 1V1/\P, ne fait pas cette hypothèse simplificatrice. Il nécessite par conséquent de pondérer les probabilités conditionnelles par les probabilités des symboles d'entrée selon l'expression (5). Lorsque le canal est sans mémoire, cette expression devient : = argmax P(RIX)- arg maxi IP(Riki)P(xj (6) Bien qu'un grand nombre de sources d'information présentent une distribution de probabilité non uniforme des symboles de leur alphabet (ci-après désignées comme sources d'information non-uniformes), le décodage ML est généralement préféré en raison de sa plus grande simplicité, malgré son caractère sous-optimal. Parmi les sources d'information non-uniformes, on peut citer la plupart des sources d'information multimédia (texte, parole, audio, vidéo) en raison de la forte corrélation qu'elles présentent entre symboles (bits) successifs. Si la compression d'information permet de réduire fortement cette redondance, elle ne l'élimine pas complètement. La non-uniformité de la distribution de probabilité des symboles à décoder peut ne pas résulter de la source d'information mais de la stratégie de communication utilisée. Ainsi dans les réseaux coopératifs utilisant une technique de codage réseau au niveau de la couche physique (Physical Layer Network Coding), des terminaux relais reçoivent des combinaisons de signaux de différents terminaux sources. On trouvera une introduction au codage réseau au niveau de la couche physique dans l'article de S. Zhang et a/. Intitulé « Physical Layer Newark Coding », publié dans Proc. Of ACM Mobicom, 2006, pp. 358- 365. Même si la distribution de probabilité des symboles émis par les terminaux sources est uniforme, la combinaison de ces symboles au niveau du terminal relais ne l'est pas. Ainsi dans l'exemple simple illustré en F 1 où deux terminaux sources S,,S2 transmettent des symboles et x2 à deux terminaux elais qui les décodent avant de les recoder éventuellement et les retransmettre à un terminal de destination D , si l'on suppose les gains des canaux unitaires entre sources et relais, les relais recevront tous deux le symbole somme xl +x2. Si les terminaux sources utilisent un alphabet BPSK à probabilité uniforme, les probabilités des symboles sommes -2,0,2 seront respectivement de 1/4, 1/2 et 1/4. De manière plus générale, si un terminal relais reçoit des symboles BPSK d'une pluralité de K terminaux sources, le symbole somme reçu du relais suivra une distribution de probabilité binomiale B(K,2). La même conclusion vaut pour des symboles QPSK, la distribution de probabilité étant alors binomiale sur chacun des axes en phase et en quadrature. Dans les deux cas précités, non-uniformité originelle de la source d'information, non-uniformité induite par le réseau, il s'agit pour le récepteur de décoder des symboles d'information appartenant à un alphabet présentant une distribution de probabilité non- uniforme. Comme indiqué plus haut, la méthode de décodage optimale est un décodage IVIAP mais celui-ci est difficilement réalisable en pratique en raison de sa grande complexité. En particulier, dans le contexte du codage réseau, il faut faire une recherche exhaustive sur toutes les combinaisons possibles de symboles des différents terminaux sources. Par ailleurs, le décodage ML est sous-optimal n termes de taux d'erreur. D'autre part, es méthodes de décodage ML existantes dans un système de télécommunication utilisant un codage réseau sont également très complexes. Le but de la présente invention est par conséquent de proposer une méthode de décodage de symboles d'information appartenant à un alphabet présentant une distribution de probabilité non-uniforme, qui soit sensiblement plus simple que le décodage MAP par recherche exhaustive et qui présente un taux d'erreur inférieur à celui obtenu au moyen d'un décodage conventionnel par maximum de vraisemblance (ML). DPOSÉ DE L'iNVENTIGI1 La présente invention est définie par une méthode de décodage MAP d'un signal reçu à travers un canai bruité, ledit signal étant constitué de symboles appartenant à un alphabet prédéterminé, affectés par un bruit additif blanc gaussien, |a distribution de probabilité des symboles au sein de cet alphabet étant non-uniforme, les symboles étant représentés par des points d'un réseau de points A = 1 x! - Ma, a E Z généré par une matrice M de taille NxN, dans laquelle on détermine un vecteur y de taille N représentatif du signal reçu ; on construit un vecteur augmenté où est un vecteur nul de taille N ; on forme un réseau augmenté ice [génératrice e rapport entre la variance du bruit et celle d'une distribution de probabilité gaussienne modélisant la distribution de probabilité non uniforme des symboles de l'alphabet ; on recherche parmi les points du réseau augmenté celui qui est le plus proche voisin du vecteur représentatif du signal reçu' ; on estime le symbole reçu à partir de la matrice génératrice et du plus proche voisin, Avantageusement, la recherche du plus proche voisin est limitée à un sous- ensemble fini du réseau de points traduisant une contrainte sur l'énergie du signal. Selon un premier mode de réalisation de l'invention, le canal bruité est un canal composé d'une pluralité K de canaux élémentaires entre des terminaux source et un terminal relais d'un réseau et les symboles sont chacun constitués d'une combinaison de symboles élémentaires respectivement transmis par les terminaux source audit terminal relais, lesdits symboles élémentaires appartenant chacun à un alphabet élémentaire d'un terminal source. Dans un exemple d'application, les alphabets élémentaires des terminaux source 25 sont identiques et la variance o-v2 de la distribution de probabilité gaussienne modélisant la distribution de probabilité non uniforme des symboles de l'alphabet est obtenue par 2 où crA2, est la variance de la distribution de probabilité des symboles 0-v = élémentaires au sein d'un alphabet élémentaire. La variance o-,2x est obtenue dans ce cas par o-x2 = K7pu., où P est la puissance d'émission maximale d'un terminal source. Avantageusement, la recherche du plus proche voisin est effectuée au moyen d'un décodeur par sphère et le décocfage par sphère utilise une énumération des points selon l'algorithme de Pohst. Alternativement, |a recherche du plus proche voisin pourra être effectuée au moyen d'un décodage par décodeur à pile et à borne sphérique. BRÈVE DESCRIPTION DES DESSINS D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de modes de réalisation préférentiels de l'invention, en référence aux figures jointes parmi lesquelles: La Fig. 1 représente un exemple simplifié de réseau coopératif utilisant un codage réseau au niveau de la couche physique ; La Fig. 2 représente une courbe de taux d'erreur en fonction du rapport signa bruit pour un exemple d'application de la méthode de décodage MAP par réseau augmenté selon un mode de réalisation de la présente invention ; La Fig. 3 représente un ordinogramme de la méthode de décodage MAP par réseau augmenté selon un mode de réalisation de la présente invention. EXPOSÉ DÉTAI E MODES DE RÉALISATION PARTICULIERS Nous considérerons dans |a suite un alphabet de symboles d'information 2S présentant une distribution de probabilité non-uniforme. Autrement, dit les symboles de cet alphabet ne sont pas équiprobables. Cet alphabet peut être par exemple celui utilisé par une source d'information non-uniforme ou bien celui résultant d'une combinaison au niveau d'un relais dans un réseau coopératif mettant en oeuvre un codage réseau au niveau de la couche physique. Dans un but d'illustration et sans préjudice de généralisation, nous présenterons la méthode de décodage selon l'invention dans le cadre d'un réseau coopératif. Nous supposerons pour cela que f[ terminaux sources Sic transmettent respectivement K symboles et qu'un terminal relais reçoit un signal correspondant à une combinaison de ces symboles, soit : +z (7) k=1 10 où ...,K sont les gains respectifs des canaux entre les terminaux sources et le terminal relais. Sans perte de généralité, nous supposerons que ces gains sont unitaires. Les symboles xk sont des éléments d'un alphabet fini A; A (-)S-2, dit alphabet élémentaire, où /\ est un réseau de points de dimension N, et12 est un convexe de , contenant l'origine et définissant la contrainte de puissance d'émission d'un 15 terminal source (supposée identique pour tous les terminaux). Par exemp e si les symboles x, sont des éléments d'un alphabet PSK ou QAM, le réseau sera de dimension 2. On rappelle qu'un réseau de points de dimension N est défini de manière générale par une matrice M de taille NxN, où les vecteurs colonne de la matrice sont appelés les vecteurs 74rérateurs du réseau, un point x du réseau 20 étant défini sous forme vectorielle par u a E ZN est un vecteur de dimension N dont les éléments sont des entiers relatif.;. On comprendra que l'on peut toujours considérer les gains grA unitaires sous réserve de modification de la matrice . Le convexe 1l est typiquement une sphère de centrée sur l'origine, le rayon de la sphère étant donné par la puissance maximale d'émission du terminai source. Ainsi, 25 si P est la puissance maximale d'émission d'un terminal source, le convexe Q peut être défini par les points x, tels que : (8) où E{.} est la valeur moyenne. Le vecteur x figurant dans l'expression (7) est un vecteur de bruit de dimension dont les composantes sont des variables aléatoires gaussiennes de moyenne nulle et de variance 0.2 . Le terminal relais est équipé d'un décodeur pour décoder la somme v= xk ° Après recodage éventuel, celui-ci le transmet au terminal de dest ation. Le symbole somme v xk appartient à un alphabet 4>, résultant de la superposition des alphabets élémentaires A. . Etant donné que le réseau A est stable par addition ( A muni de l'addit)on possède une structure de groupe), le symbole somme y appartient encore au réseau A Il en résulte que le réseau de points Ar définissant l'alphabet Ar est un sous-ensemble de A ( Av c A). L'alphabet A, des symboles somme est tel que oà g, est un convexe de traduisant la contrainte de puissance d'émission des K terminaux sources. Un décodage MAP au niveau du relais conduirait à rechercher le vecteur somme mAp tel que : 2O AfAp argrriax(P (v (9) veAv soit encore : rni (10) arg n en tenant compte du fait que P(yly)= exp L'idée à la base de l invention est de modéliser le symbole somme y par une variable aléatoire gaussienne de moyenne nulle et de variance 2 KNP.... Cette approximation se justifie par application du théorème central limite aux variables aléatoires Sur la base de cette approximation, la loi de distribution de probabilité du symbole somme est donnée par : 10 P(y 1 exp En remplaçant cette estimation de P(y) dans l'expression (10), on obtient un nouveau critère de décodage : 15 arg n (12) Etant donné que le premier terme ne dépend pas de y, le décodage revient à déterminer : 2 0 arg min (13) veA, On introduit un vecteur, ya, , dit vecteur augmenté, de taille 2N, résultant de la concaténation verticale du vecteur y et d'un v e nu de taille N , soit y., = une matrice de rang plein B 1 où IN est la matrice identité de taille Nx N et P est un coefficient traduisant le rapport entre la variance de bruit et la variance du symbole somme à décoder, scit I -cr2 CFF Le critère de décodage (13) peut alors s'exprimer comme : - arg m in (1 -B (14) où l'on a traduit la condition sur la limite de puissance de transmission en contraignant le vecteur a à appartenir à un sous-ensemble de Z" tel que la contrainte de puissance 10 d'émission soit vérifiée, c'est-à-dire a e Si l'on définit la matrice augmentée de taille 2Nx N par r = , le critère de décodage s'exprime enfin sous la forme : 15~mup= min (15) ,,, - Nla elén. autrement dit, cela revient à rechercher le point d'un réseau augmenté engendré par la matrice , qui est le plus proche du point 7 , représentant le signal reçu. On comprend par conséquent que l'on se ramène ainsi à un décodage de type ML classique 20 dans un espace augmenté, de dimension 2N, le réseau de points A ainsi que le point représentatif du signal reçu y.' étant tous deux de dimension 2N. La recherche du plus proche voisin de y., dans le réseau augmenté A., peut être réalisée de manière classique au moins d'un décodage par sphère. On rappelle qu'un décodage par sphère permet de limiter la recherche du plus proche voisin aux points du réseau appartenant à une boule de bruit centrée sur le point représentant le nal reçu. On trouvera une description du décodeur par sphère dans l'article d'E. Viterbo et a/. intitulé « A un/verso/ iottice code decoder for fading channels » publié dans IEEE Transactions on Information Theory, vol. 45, pages 1639-1642, Juillet 1999. On pourra également utiliser un décodeur à pile et à borne sphérique (SB-Stock decoder) tel que décrit dans l'article de G. Rekaya Ben-Othman intitulé « The spherical bound stock decocier » publié dans Proc. of IEEE International Conference on Wireless & Mobile Computing, Networking & Communication, pp. 322-327. La recherche du plus proche voisin par le décodeur par sphère pourra notamment utiliser une énumération de Pohst connue en soi. Le décodeur par sphère part d'une sphère de bruit de rayon C centrée sur le point 37,,,g représentatif du signal reçu. Les points a du réseau .Aaue appartenant à cette sphère vérifient : Yaie 2 (16) A l'étape 350, on estime le symbole reçu au sens du critère MAP par = On comprendra que la recherche du plus proche voisin dans le réseau pourra être effectuée à i'aide d'un décodeur par sphère ou d'un décodeur à pile et à borne sphérique, comme indiqué plus haut. Les différentes variantes connues de décodage par sphère sont ici applicables, en particulier celles mettant en oeuvre une énumération des points selon l'algorithme de Pohst. L'homme du métier comprendra que le décodage de symboles somme dans le cadre d'un canal d'un réseau coopératif est un cas particulier du décodage de la Fig. 3 dans la mesure où ces symboles somme font partie d'un alphabet obtenu par superposition des alphabets élémentaires des différents terminaux source et que la distribution des symboles somme au sein de cet alphabet et non-uniforme. Enfin, comme indiqué précédemment, d'autres algorithmes de recherche de plus proche voisin dans un réseau de points, notamment le décodage de Schnorr-Euchner, pourront être mis en oeuvre sans sortir du cadre de la présente invention. REVENDICATIONS1. Méthode de décodage MAP d'un signal reçu à travers un canal bruité, ledit signal étant constitué de symboles appartenant à un alphabet prédéterminé, affectes par un bruit additif blanc gaussien, la distribution de probabilité des symboles au sein de cet alphabet étant non-uniforme, les symboles étant représentés par des points d'un réseau de points A= x =Ma, a e Z généré par une matrice 1 de taille N xN , caractérisée en ce que : on détermine 310) un vecteur y de taille représentatif du signal reçu ; 10 on construit (320) un vecteur augmenté yaug =| ~ | où 0 est un vecteur 0 nul de taille N ; on forme (330) un réseau augmenté A,,,g x Mauga, matrice génératrice 111., = 0-2 est le rapport entre la variance du bruit et celle d'une distribution de probabilité gaussienne modélisant la distribution de 15 probabilité non uniforme des symboles de l'a(phabet ; on recherche (340) parmi les points du réseau augmenté celui qui est le plus proche voisin du vecteur représentatif du signal reçu, ; on estime (350) le symbole reçu à partir de la matrice génératrice NI et du plus proche voisin, = 20 2. Méthode de décodage MAP selon la revendication 1, caractérisée en ce que la recherche du plus proche voisin est limitée à un sous-ensemble fini S8, du réseau de points traduisant une contrainte sur l'énergie du signal. 3. Méthode de décodage MAP selon la revendication 1 ou 2, caractérisée en ce que le canal bruité est un canal composé d'une pluralité K de canaux élémentaires entre des terminaux source et un terminal relais d'un réseau et que les symboles sont chacun constitués d'une combinaison de symboles élémentaires respectivement transmis par les terminaux source audit terminal relais, lesdits symboles élémentaires appartenant chacun à un alphabet élémentaire d'un terminal source. 4. Méthode de décodage MAP selon la revendication 3, caractérisée en ce que les alphabets élémentaire des terminaux source sont identiques et que la variance de la distribution de probabilité gaussienne modélisant la distribution de probabilité non uniforme des symboles de l'alphabet est obtenue par cr,2 = Ka où cy2x est la variance de la distribution de probabilité des symboles élémentaires au sein d'un alphabet 10 élémentaire. S. Méthode de décodage MAP selon la revendication 4, caractérisée en ce que la variance (3-2', est obtenue par c)-2x= NPmax où Pmax est la puissance d'émission maximale d'un terminal source. 15 6. Méthode de décodage MAP selon l'une des revendications précédentes, caractérisée en ce que la recherche du plus proche voisin est effectuée au moyen d'un décodeur par sphère. 7. Méthode de decodage MAP selon la revendication 6, caractérisée en ce que le décodage par sphère utilise une énumération des points selon l'algorithme de Pohst. 8. Méthode de décodage MAP selon l'une des revendications 1à 5, caractérisée en ce que la recherche du plus proche voisin est effectuée au moyen d'un décodage par décodeur à pile et à borne sphérique,