Brevet FR2890806A1 — publié le 20070316

PROCEDE D'AMELIORATION DE DECODAGE ITERATIF DE CODES L'invention concerne notamment un procédé permettant d'améliorer le décodage itératif de codes courts (une centaine de bits) à moyennement longs (de la taille MPEG = 1504 bits par exemple) codés avec un code correcteur d'erreur de rendement faible tel que 1/3 ou élevé : 90% ou plus. Elle s'applique, notamment, dans le domaine des télécommunications, par exemple pour les communications satellite. Dans la description, on introduit la notion de décodeur super itératif pour différencier une itération effectuée au sein d'un décodeur selon 10 l'art antérieur et l'étape d'itération dans le procédé selon l'invention. Les communications à accès multiples (TDMA time Divisional multiple access) ou lorsque la latence doit être faible utilisent généralement des codes courts ou moyennement longs précités (par exemple de la taille MPEG) . Dans ces conditions, pour les turbo codes au sens général du terme, incluant les turbo codes ou TPC Turbo Product Codes, les codes obtenus par concaténation en série des codes convolutionnels ou SCCC (abréviation anglo-saxonne de Serial Concatenated Convolutional Code), les codes obtenus par une concaténation en parallèle de codes convolutionnels ou PCCC (abréviation anglo-saxonne de Parallel Concatenated convolutional code), les contrôles de parité faible densité LDPC (abréviation anglo saxonne de Low density parity check), dans leur variante binaire ou maire, un compromis doit être trouvé entre complexité de décodage et performances du code. Le principe du décodage itératif est de générer deux informations de cohérence locale dans deux dimensions, aussi indépendantes que possible. L'indépendance est notamment assurée entre les deux dimensions par un entrelaceur. La taille du mot de code limite le découplage entre les deux dimensions. Une taille réduite amplifie aussi l'effet statistique d'un mauvais codage local, qui est moins bien compensé par le reste du code. Pour cette raison, les codes de petite ou de moyenne taille sont aujourd'hui assez loin de la limite théorique pour des complexités de 10 décodage raisonnable. Pour des codes de grande taille (supérieure par exemple à 5000 bits d'information), il est connu de l'art antérieur des méthodes de concaténation, par exemple des concaténations de code LPCD et turbo, pour réduire le plancher d'erreur (error floor) du turbo code, dû à une distance libre (au sens de Hamming) trop faible. Une autre possibilité consiste à ne pas réduire le taux de codage du code interne. Le taux de codage étant plus petit, le point de fonctionnement (exprimé en Eb/NO avec Eb Energie par bit et NO densité spectrale de bruit et non des bits codés par le code externe) n'est pas compensé par le gain du code externe. Lorsque le système utilise des codes petits, soit pour des problèmes de latence liée à de petits débits tels que dans la téléphonie, ou pour des problèmes de granularité dans des systèmes à allocation dynamique, le système de codage utilisant de grands mots de code devient inefficace. L'invention concerne un procédé d'amélioration de décodage itératif de codes courts au sein d'un démodulateur caractérisé en ce qu'il comporte au moins les étapes suivantes: É Décoder le vecteur de métriques des bits considérés en sortie du démodulateur, É comparer la valeur du code de contrôle du CRC du mot décodé à une valeur prédéterminée, É Si la valeur du CRC est considérée comme formant un message acceptable pour l'étape de décodage, transmettre le mot décodé au destinataire, le super décodeur transmet le mot décodé, É Si la valeur du CRC est incompatible d'un message correctement décodé, alors modifier les paramètres de décodage itératif du message initial reçus du démodulateur et exécuter au moins une nouvelle étape de décodage itératif avec ces nouveaux paramètres. Le super décodeur modifie les paramètres de décodage itératif. La valeur du CRC est définie, par exemple, afin que le taux de codage global ne soit pas changé par l'insertion du CRC, grâce à une 15 perforation effectuée dans le code décodé itérativement. L'invention présente notamment les avantages suivants: É Une réduction du rapport signal à bruit nécessaire pour obtenir un taux d'erreur binaire donné, É Une indication de validité du paquet reçu afin de destruction éventuelle par les couches protocolaires supérieures. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description d'un exemple de réalisation donné à titre illustratif et nullement limitatif annexé des figures qui représentent: É La figure 1 le schéma de mise en oeuvre de l'invention, indiquant les blocs ajoutés: CRC (2), vérification du CRC (8) et fonction de rétroaction (6) et le point d'action du retour de décision utilisé par l'invention, É La figure 2 indique le gain de l'invention dans le cas d'une cellule ATM (asynchronous transfer mode), et É La figure 3 indique le gain de l'invention dans le cas d'une cellule ATM. L'idée de base du procédé selon l'invention est notamment d'utiliser un code de contrôle CRC (abréviation anglo-saxonne de Cyclic redondancy check) adapté pour indiquer, notamment en fin de décodage soit que le résultat obtenu doit être considéré comme valide, CRC exact, ou au contraire que le résultat décodé ne peut être conforme au message émis. Lorsque le CRC n'est pas correct, le décodeur recommence un décodage depuis la première itération, mais en modifiant l'information initiale reçue du démodulateur. Sur la figure 1, on a représenté en traits pleins, les étapes et les moyens mis en oeuvre par l'invention dans le cas où le procédé de décodage inclus déjà un CRC. En traits pointillés, un moyen permettant d'introduire un CRC au niveau du codeur est représenté. La source 1 émet des signaux composés de bits qui sont codés par un codeur itératif 3. Les bits codés sont ensuite transmis à un modulateur 4. Les bits modulés transitent à travers un canal de propagation et sont reçus par un récepteur 5,6,7,8. Le récepteur comprend, par exemple, un démodulateur 5 recevant le signal issu du canal de propagation. Les signaux démodulés sont ensuite transmis à un décodeur super itératif 6,7, 8 présentant les caractéristiques de l'invention et comprenant notamment un dispositif anti-gradient 6, un décodeur itératif 7 et un dispositif de contrôle de CRC 8. Le contrôleur 8 a notamment pour fonction de contrôler la valeur du code de contrôle CRC présent dans le signal à une valeur fixée au préalable. La fonction décodage est notamment adaptée à : É Sortir les informations pondérées qu'elle utilise pour la dernière itération, par exemple les deux itérations pour un PCCC. On utilise l'information issue du décodage (en anglo-saxon soft output brute) et non la métrique extrinsèque utilisée lors du rebouclage itératif, On rappelle que l'équation métrique extrinsèque est égale à l'information issue du décodage ou soft output brute la ( L'information introduite dans le CRC est, par exemple, une valeur de type binaire, message acceptable ou message incorrectement décodé. Le 20 procédé selon l'invention met en oeuvre notamment les étapes suivantes: A) Super encodage à l'émission: É Ajout d'un CRC au message original (dans le cas où il n'existe pas) ou utilisation d'un CRC dans le cas où les couches hautes le définissent explicitement), É Encodage du message original grâce à un code susceptible de décodage itératif. B) Super décodage à la réception: É Décodage du vecteur de métrique en sortie du démodulateur, On décode le vecteur de métriques des bits considérés en sortie du démodulateur, É Comparaison de la valeur du code de contrôle CRC du mot décodé à une valeur prédéterminée, par exemple la valeur du CRC calculé sur le message décodé, É Si le CRC calculé sur le mot décodé est conforme à la valeur du CRC décodée, la valeur est considérée comme formant un message acceptable pour l'étape de décodage, alors, le super décodeur transmet le mot décodé au destinataire, É Si la valeur du CRC n'est pas cohérente, c'est à dire si la valeur du CRC est incompatible d'un message correctement décodé, alors le super-décodeur modifie les paramètres de décodage itératif du message initial reçues du démodulateur et exécute au moins une nouvelle étape de décodage itératif avec ces nouveaux paramètres. La modification des paramètres de décodage peut alors être une modification de la vitesse de convergence, une modification de la puissance de calcul, une modification des entrées du décodeur telle que détaillée dans la suite. Pour un dispositif ne comportant pas de vérification intrinsèque (2) , le procédé comporte une étape où l'on ajoute ce vérificateur intrinsèque et l'on exécute ensuite les étapes de décodage précitées. Selon une variante de réalisation, on ajoute un CRC adapté à détecter un faux décodage et à relancer un deuxième décodage itératif, lorsque le taux de codage global est diminué par l'insertion du CRC, le code décodé itérativement conservant son taux de codage. Le CRC ajouté est par exemple adapté à relancer un deuxième décodage itératif, lorsque le taux de codage global n'est pas changé par l'insertion du CRC, grâce à une perforation c'est à dire la suppression arbitraire de certains bits codés, le plus souvent uniformément répartis dans le message codé) effectuée dans le code décodé, et l'on en informe le décodeur par l'envoi pour le bit perforé d'une valeur correspondant à pas d'information a priori , le plus souvent la LLR (Log Likelihood Ratio) nulle). Selon une variante de mise en oeuvre, le procédé comporte, par exemple, un CRC existant et adapté à relancer un deuxième décodage itératif, en partant du même vecteur d'initialisation (i.e. les valeurs pondérées fournies par le démodulateur) fourni par le démodulateur, avec un procédé de décodage plus onéreux, mais plus proche de l'optimal. Selon une variante de mise en oeuvre, le procédé utilise un CRC déjà existant pour décider de relancer un deuxième décodage itératif, en partant du même vecteur d'initialisation fourni par le, mais avec un procédé de décodage à convergence plus lente en utilisant des coefficients de pondération de la métrique extrinsèque plus faibles que lors du premier décodage. Ce deuxième décodage peut également utiliser plus d'itérations que la première tentative. Le décodage itératif classique fourni par le décodeur classique comporte plusieurs itérations. A la fin de ces itérations, le décodeur 7 fournit au comparateur de CRC 8 l'information décodée. Le comparateur de CRC choisit alors de valider le résultat proposé par le décodeur, ou choisit de demander à l'opérateur gradient inverse 6 un nouveau point de départ pour un nouveau décodage du mot de code à décoder. Ce nouveau décodage prendra alors plusieurs itérations. Dans une seconde variante de réalisation, le deuxième décodage est exécuté en partant d'un vecteur d'initialisation différent du vecteur d'initialisation fourni par le démodulateur. Le vecteur correctif, représentant la différence entre le vecteur initial et le vecteur sur lequel est tenté le nouveau décodage est fourni par un bruit de faible amplitude_(faible température) suivant une méthode de recuit simulé. Dans une autre variante de réalisation, le deuxième décodage peut être exécuté en partant d'un vecteur d'initialisation différent du vecteur d'initialisation fourni par le démodulateur, lorsque le vecteur correctif, représentant la différence entre le vecteur initial et le vecteur sur lequel est tenté le nouveau décodage est fourni par l'anti-gradient des dernières demi itérations. On appelle ici anti-gradient le vecteur quasi nul constitué, pour ses valeurs non nulles, des valeurs décodées considérées comme étant les moins fiables lors de la dernière demi itération, de l'avant dernière demi itération ou d'une pondération des demi itérations du décodage itératif classique. Le nombre des valeurs retenues non nulles dans cet anti-gradient est typiquement de l'ordre de trois quarts de la distance libre du code sans que cette valeur constitue une obligation. La valeur absolue des points non nuls de l'anti-gradient est typiquement égale à la moitié de la métrique moyenne. Leur signe est inverse de la décision correspondant au décodage. Selon une autre variante de mise en oeuvre, le deuxième décodage est une combinaison des deux méthodes précédentes, lorsque le vecteur correctif, représentant la différence entre le vecteur initial et le vecteur sur lequel est tenté le nouveau décodage est nul sur les points présentant une métrique décodée importante, et un bruit aléatoire (par exemple gaussien) sur les points correspondant à une moins bonne convergence, caractérisés par une métrique décodée faible. Dans une sous variante de ce décodage par modification du vecteur d'initialisation, le deuxième décodage est par exemple de type multi hypothèse et consiste à forcer un bit décodé à une valeur donnée, correspondant par exemple à l'inverse de la valeur trouvée par le décodage de la première super itération; le vecteur correctif correspond alors à une décision dure, et force la métrique (LLR) du bit considéré à la valeur maximale correspondant à un bit extrêmement sûr. La deuxième super itération est répétée pour différentes position de bits. La position du bit inversé est prise a priori (comme pour un recuit simulé) ou a posteriori grâce au décodage de la première super itération (comme pour un gradient inverse). Le nombre de super itérations peut être supérieur à deux et le point de départ de la nouvelle super itération constitué du point initial en sortie du démodulateur, et d'un vecteur correctif de taille (nombre de coordonnées non nulles) ou de poids (norme euclidienne) variable en fonction de l'itération (typiquement croissant) ou fixe. Le nombre de super itérations est par exemple supérieur à 2 et le point de départ de la nouvelle super itération est constitué, itérativement donc, du point en entrée de la super itération précédente, et d'un vecteur correctif de taille ou de poids fixe ou non. La suite de la description concerne deux exemples de mise en oeuvre du procédé donnés à titre illustratif et nullement limitatif. Les figures 2 et 3 expriment le gain d'un point de vue théorique; gain en TEB (taux d'erreur binaire) pour un rapport signal à bruit donné. Exemple 1 Le graphique représenté sur les figures 2 et 3 montre l'intérêt du procédé dans de cadre d'un turbo code voisin de hiperlan2: un turbo code produit basé sur un BCH(26,32,t=1) étendu par contrôle de parité, ce qui lui garantit une distance libre de 4 pour chaque composant (ligne/colonne) pour une composante de spectre qui vaut sensiblement Sligne=Scolonne=1000. La distance libre est donc dfree=dl*d2=4*4=16 et le premier terme du spectre du code produit est STPC=S1*S2=1000*1000. La première composante de la borne de l'union est donc sensiblement: PER^É=STpCÉQ(dfree.2.Eb/No) 1 " u2 où Q(x)= f exp du 2p Y 2 i Le code transporte ici 80 octets = 640 bits. Ces 80 octets sont protégés par 10 bits de CRC. Les 10 bits ajoutés dans l'information sont perforés aléatoirement dans le code produit afin de garder le taux de codage strictement égal à celui du code classique. Le code produit initial est raccourci d'une ligne. Dans le code initial, 10 bits de bourrage (arbitrairement pris égaux 10 à zéro) sont ajoutés aux 640 bits pour entrer dans la matrice initiale 650=26*25. Le codeur ajoute des bits de redondance de manière classique, jusqu'à concurrence de 31*32=992 bits. Le codeur extrait des 10 bits de bourrage, qui n'ont pas besoin d'être transmis, et fournit 982 bits au modulateur, soit un taux de codage de 640/982= 0,65173... voisin de 2/3. Le nouveau codeur ajoute 10 bits de CRC (par exemple). Il ne doit donc pas ajouter de bits de bourrage. Le code produit sort 992 bits dont aucun bit de bourrage. Le nouveau codeur perfore donc 10 bits codés à des positions déterminées. Ces positions ne font pas l'objet du procédé. Exemple 2 Un exemple pratique est donné sur un code petit, comportant 96 bits de données, 4 bits de CRC, et protégé par un BCH(11) étendu par parité sur les lignes et les colonnes et raccourci d'une ligne et d'une colonne. Le taux du code sans CRC est de 96/221. Dans cet exemple avec 25 conservation du taux de codage, le code avec CRC est donc perforé de 4 bits. La matrice d'entrée est donc la suivante, en considérant que l'information initiale est uniformément nulle. La redondance est en italique, le CRC est en gras, et les 4 positions perforées sont marquées ?? , et correspondent à une métrique nulle. Entrée du décodeur: 7 1 -5 30 19 0 31 14 3 26 19 19 32 25 9 12 5 13 18 28 14 17 25 10 16 8 22 15 9 6 19 0 13 19 17 18 -15 22 25 ?? 11 27 14 19 10 27 38 19 19 5 13 18 -13 34 -8 15 6 28 15 16 22 37 18 15 13 16 19 12 18 26 7 10 15 21 -5 18 22 34 10 5 ?? 18 19 10 22 5 16 16 24 36 14 26 19 26 24 18 24 7 12 13 21 35 31 20 21 4 -8 36 -13 19 26 17 10 -1 19 8 -13 32 32 26 39 47 5 2 6 4 7 33 14 42 34 22 14 15 -6 13 3 0 21 4 2 2 11 25 8 -3 -3 ?? 9 16 -3 0 23 42 8 11 8 -23 6 3 1 -6 7 44 19 29 13 5 18 28 -4 0 2 12 12 18 3 34 23 9 8 23 28 19 21 30 -1 12 -2 12 3 10 26 10 11 ?? 13 5 -13 23 4 -4 3 13 15 4 33 8 11 -6 -2 21 1 36 40 14 21 22 13 10 19 _ 4 Sortie du décodeur après la première super itération: 59 29 40 30 62 55 52 31 30 55 55 42 74 46 45 51 29 43 32 74 55 46 35 37 58 45 46 52 25 48 -13 41 -7 50 59 -10 38 42 -31 41 42 45 46 41 51 51 40 15 37 49 -10 -3 50 -31 41 -6 70 44 41 74 60 47 30 50 57 37 37 44 53 47 29 42 34 41 52 52 7 37 50 37 47 37 57 39 35 45 54 62 58 69 48 43 72 66 57 32 47 48 58 61 60 55 54 51 -13 60 - 7 55 56 10 -3 30 41 39 -6 68 44 54 63 77 71 16 41 49 39 31 59 51 76 57 68 40 46 51 -13 41 -7 37 50 10 -3 30 41 54 -6 42 25 41 51 50 40 7 55 66 -10-. '-- ' -3 35 -31 39 -6 42 25 45 78 50 49 21 41 55 50 32 35 46 46 30 52 25 61 59 29 40 41 54 58 39 45 30 46 45 42 46 49 57 66 -13 46 ' -7 37 49 =10 39 35 -31 39 29 42 34 45 51 33 41 16 48 49 60 42 37 56 60 30 46 51 45 La sortie du décodeur est plus vraisemblable que le message initial: on vérifie que les sommes des produits métriques fois décision (Log Likelihood Ratio) pour le décodage correspondant au message initial (tout zéro) est inférieure à celle du message décodé. Message initial 267 219 246 166 222 217 217 205 171 147 202 217 249 206 238 Message décodé 267 227 246 148 222 217 221 185 171 217 202 209 249 206 238 différence 0 8 0 -18 0 0 4 -20 0 70 0 -8 0 0 0 Le calcul du CRC donne une valeur non nulle pour le message décodé pour le TPC seul. L'analyse après relève les valeurs des douze nombres suivants comme ayant la plus petite valeur absolue: -3 -6 -7 -3 -6 -7 -3 -6 -3 -6 Elle crée donc le rétro stimuli. 7 4 9 7 4 9 6 8 6 o La nouvelle entrée pour la deuxième super itération est donc: 7 1 -5 30 19 0 31 14 3 26 19 19 32 25 9 12 5 13 18 28 14 17 25 10 16 8 22 15 9 6 19 0 13 24 17 18 -15 22 25 0 11 27 14 19 10 27 38 19 19 5 13 18 -3 34 -8 15 13 28 15 16 22 37 18 15 13 16 19 12 18 26 7 10 15 21 -5 18 22 34 5 5 0 18 19 10 22 5 16 16 24 36 14 26 19 26 24 18 24 7 12 13 21 35 31 20 21 4 -8 36 -9 19 26 17 19 -1 19 8 -6 32 32 26 39 47 5 2 6 4 7 33 14 42 34 22 14 15 -6 13 7 0 21 4 11 2 11 25 14 -3 -3 0 9 16 -3 0 23 42 8 19 8 -23 6 9 1 -6 7 44 19 29 13 5 18 28 -4 0 2 12 12 18 3 34 23 9 8 23 28 19 21 30 -1 12 -2 12 3 10 26 10 11 0 13 5 -13 23 4 -4 3 13 15 4 33 8 11 - 6 -2 21 1 36 40 14 21 22 13 10 19 4 Le décodage converge alors vers la valeur du message initial. Le CRC est alors évidemment vérifié. Dans l'exemple précédent, le faible nombre de bits de CRC, 4 bits, permet un gain asymptotique de la méthode réduit à un facteur 2^4=16 sur le taux 5 d'erreur paquet. REVENDICATIONS 1 Procédé d'amélioration de décodage itératif de codes courts au sein d'un démodulateur (5) caractérisé en ce qu'il comporte au moins les étapes 5 suivantes: É Décoder (6, 7, 8) le vecteur de métriques des bits considérés en sortie du démodulateur (5), É comparer (8) la valeur du code de contrôle du CRC du mot décodé à une valeur prédéterminée, É Si la valeur du CRC est considérée comme formant un message acceptable pour l'étape de décodage, transmettre le mot décodé au destinataire, É Si la valeur du CRC est incompatible d'un message correctement décodé, alors modifier les paramètres de décodage itératif du message initial reçus du démodulateur et exécuter au moins une nouvelle étape de décodage itératif avec ces nouveaux paramètres. 2 Procédé selon la revendication 1 caractérisé en ce que l'on définit la valeur du CRC afin que le taux de codage global ne soit pas changé par l'insertion du CRC, grâce à une perforation effectuée dans le code décodé itérativement. 3 Procédé selon la revendication 1 caractérisé en ce que l'on utilise un CRC existant, en partant du même vecteur d'initialisation fourni par le 25 démodulateur. 4 Procédé selon la revendication 1 caractérisé en ce que l'on utilise un CRC existant, en partant du même vecteur d'initialisation fourni par le démodulateur, avec un procédé de convergence utilisant des coefficients de la métrique extrinsèque plus faibles que ceux utilisés lors du premier décodage. Procédé selon la revendication 1 caractérisé en ce qu'on exécute le deuxième décodage (7) en partant d'un vecteur d'initialisation différent du vecteur d'initialisation fourni par le démodulateur (5), lorsque le vecteur correctif, représentant la différence entre le vecteur initial et le vecteur sur lequel est tenté le nouveau décodage est fournit un bruit de faible amplitude (faible température) suivant une méthode de recuit simulé. 6 - Procédé selon la revendication 1 caractérisé en ce que le deuxième décodage (7) est effectué en partant d'un vecteur d'initialisation différent du vecteur d'initialisation fourni par le démodulateur (5), lorsque le vecteur correctif, représentant la différence entre le vecteur initial et le vecteur sur lequel est tenté le nouveau décodage est obtenu par un anti-gradient (6) des dernières demi-itérations, l'anti-gradient étant constitué des valeurs décodées les moins fiables lors de la dernière demi-itération, de l'avant dernière demi-itération ou d'une pondération des demi-itérations du décodage itératif classique. 7 - Procédé selon la revendication 6 caractérisé en ce que l'on retient comme nombre des valeurs retenues non nulles dans cet anti-gradient (6) un nombre typiquement de l'ordre de trois quarts de la distance libre du code sans que cette valeur constitue une obligation, la valeur absolue des points non nuls de l'anti-gradient (6) est typiquement égale à la moitié de la métrique moyenne, leur signe est choisi inverse de la décision correspondant au décodage. 8 - Procédé selon la revendication 1 caractérisé en ce que pour le deuxième 5 décodage (8) on injecte un bruit sur un nombre réduit de points. 9 - Procédé selon la revendication 1 caractérisé en ce que dans la deuxième étape de décodage (7), on force un bit décodé à une valeur donnée, inverse de la valeur trouvée. Procédé selon la revendication 1 caractérisé en ce que la deuxième super itération est répétée pour différentes position de bits. 11 - Procédé selon la revendication 1 caractérisé en ce que le nombre de super itérations (6, 7, 8) est supérieur à deux et le point de départ de la nouvelle super itération est constitué du point initial en sortie du démodulateur, et d'un vecteur correctif de taille (nombre de coordonnées non nulles) ou de poids (norme euclidienne) variable en fonction de l'itération (typiquement croissant) ou fixe. 12 - Procédé selon la revendication 1 caractérisé en ce que le nombre de super itérations (6, 7, 8) est supérieur à 2 et le point de départ de la nouvelle super itération est constitué, itérativement donc, du point en entrée de la super itération précédente, et d'un vecteur correctif de taille ou de poids fixe ou non.