FR2871631A1 - Procede de decodage iteractif de codes blocs et dispositif decodeur correspondant - Google Patents

Abstract

Un procédé et un dispositif de décodage de code bloc.Chaque mot reçu (R) est soumis à un turbo-décodage SISO consistant à engendrer (A) par un algorithme itératif des mots de test décodés, calculer (B) pour le mot de test décodé le poids analogique de ce dernier, demi somme des produits de la valeur de chaque bit mappé à +/- 1 de ce mot de test décodé et de la log-vraisemblance de ce bit, classer (C) les valeurs de poids analogique des mots concurrents selon un premier (V1) respectivement un deuxième vecteur (V2) de poids analogique formés par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une première valeur et un deuxième vecteur de poids analogique formé par les composants de poids analogique des mots de test décodés dont le bit de rang j est à une deuxième valeur et calculer (D) la valeur de sortie de décision douce du décodage SISO comme la différence des composantes de poids analogique des premier, deuxième vecteur (V1) (V2).Application au décodage de codes blocs transmis ou stockés en mémoire.

Description

2871631 1

Les procédés de codage-décodage des signaux numériques ont été introduits afin d'assurer une transmission efficace des données numériques véhiculées par ces derniers.

Par principe, ils consistent à ajouter à des bits signifiants, support de l'information véhiculée par les signaux numériques précités, une redondance de bits connus, afin de permettre après transmission de l'ensemble, et introduction d'erreurs inhérentes au processus de transmission, un décodage et une reconstruction des bits signifiants avec une bonne probabilité de vraisemblance.

Dans le cas plus spécifique des codes blocs, incluant les codes produit, on considère, en référence à la figure 1a, deux codes blocs CI (ni, ki, di) et C2 (n2, k2, d2) dont les n bits, n = ni x n2 sont placés dans une matrice à ici lignes et k2 colonnes, k1 x k2 désignant les bits signifiants placés dans une matrice à Ici lignes et k2 colonnes, les n1 lignes étant codées par le code C2 et les n2 colonnes étant codées par CI.

Les paramètres du code produit P(n, k, d) sont donnés par n = ni x n2, k = k1 x k2, d = di x d2 et le rendement du code produit est donné par r = r x r2 produit des rendements des codes CI et C2.

Le décodage après réception d'un mot de code produit reçu R = {r1... rn} d'une seule ligne ou d'une seule colonne E = {el, ... en} codée par le code Cl ou C2 est exprimé sous la forme R = E+G où G = {gl, ... gn} désigne un bruit blanc gaussien additif introduit par le canal de transmission.

Le maximum de vraisemblance du mot de code R reçu vis-à-vis d'un mot du code produit est obtenu par la décision optimum D = {dl, ..., dn} vérifiant la relation: D = minci R C relation dans laquelle C' = {cl, ... cn} désigne un mot du code, et R C' =E (rl ci désigne la distance euclidienne du mot C' considéré vis-à-vis du mot de code reçu R. Une recherche exhaustive sur l'ensemble des mots du code étant irréalisable, pour trouver la décision optimum, un processus de décodage proposé par R. Pyndiah consiste à mettre en oeuvre un algorithme de Chase pour obtenir cette dernière.

Pour toute décision dure avec Y = {y1, ... yn} relative à un mot reçu R, l'algorithme précité consiste à effectuer les opérations suivantes: sélection des p = d/2, d désignant le nombre de bits les moins fiables, des log-vraisemblances ri de valeur absolue faible d'une ligne ou d'une colonne; - construction des Tc' vecteurs de test, Ta représentant toutes les combinaisons de valeurs binaires dans les p positions les moins fiables et valeur zéro pour les autres positions; - construction des mots de test Zq = Y O T' où le signe O désigne l'opération OU exclusif sur les composantes des vecteurs; - décodage dur des mots de test Z4 afin d'obtenir des mots Cq appartenant au code; - sélection du mot de code cd appartenant au code de distance euclidienne minimale par rapport au mot reçu et obtention de la décision optimum D. Il faut alors procéder au calcul de la fiabilité de cette décision optimum. La fiabilité précitée en termes de log-vraisemblance (LLR) est donnée, pour chaque bit di de la décision optimum D, par la relation: A(d) -1 nP{ej =+1/R1\ dans laquelle Pi = /Ry, E = 1, désigne la probabilité conditionnelle que le bit ej corresponde à la valeur mappée compte tenu du mot de code reçu R; ln désigne le logarithme Néperien.

Le calcul rigoureux de LLR doit tenir compte du fait que la décision optimum D est un mot parmi les 2k (pour k1 = k2) mots du code C. Dans la solution proposée par R. Pyndiah, une approximation de LLR pour des signaux à grand rapport signal à bruit RSB est donnée par la relation -I G) +1 G) m -m avec r'-= +1(j) R C et m-1() R-C-10) 2871631 3 où +1Q) _ +1(i) +(j)l et! -1Ü) C o,..., Cn C = o, ... ' Cn sont les mots concurrents du code à distance minimale de R ayant pour contrainte que le bit de rang j de ces mots soit mappé à la valeur +1 respectivement -1. Les mots concurrents précités sont trouvés grâce à l'algorithme de Chase. Dans le cas où l'un des mots n'existe pas, la fiabilité est fixée par une valeur prédéterminée constante [3, dont le signe est donné par la décision de Chase. Le fait d'augmenter p augmente la probabilité de trouver, pour un bit de rang j, le mot concurrent à D. En référence à la figure 1 b, le traitement des informations pour exécuter le turbo décodage à partir d'un décodeur SISO est alors le suivant: pour un mot de code produit reçu [R], le mot de code produit décodé engendré par l'itération précédente [R(m)] et le mot de code produit décodé [R(m)] engendré par l'itération courante délivrées par le décodeur SISO, le mot d'entrée [W(m+1)] du turbo décodage T pour l'itération suivante vérifie la relation: [W(m+1)] = [R'm) R(m)] avec [R(m+1)]=[R] + a (m+1)[W(m+1)] et [R(1)]=[R] pour la première itération.

Dans la relation précédente W(m) désigne l'information extrinsèque, 20 normalisée à 1 à chaque itération et a (m) désigne un coefficient qui dépend de l'itération courante, de rang m.

Ce processus de décodage est proche de l'optimal dans la mesure où l'information qui circule d'une itération de décodage à la suivante ne contient que l'information apportée par cette itération, en raison de l'opération de soustraction effectuée, l'information extrinsèque étant seule transmise.

Pour une description plus détaillée de ce processus de turbodécodage, on pourra utilement se reporter à la demande de brevet EP 0 827 284 publiée le 4 mars 1998.

La mise en oeuvre du processus de codage précité, pour une ligne ou 30 une colonne, peut être résumée de la manière ci-après: a) processus itératif selon l'algorithme de Chase avec décodage par utilisation d'un algorithme du type Berlekamp-Massey ou PGZ et stockage en mémoire des mots obtenus et de leurs poids; 2871631 4 b) recherche de la décision dure Cd = D décision optimum à distance euclidienne minimale parmi ces mots; c) pour chaque bit de rang j, recherche du mot concurrent cc à distance minimale de R tel que ça c; et calcul de la fiabilité, en termes de log- c d vraisemblance, à partir de l'approximation f = m m 4 d) calcul des informations extrinsèques pour le mot concurrent de rang j retenu à l'étape c), par la relation d Wj= !fi cd j.r'j cJ Dans la relation précédente, cd désigne le bit de rang j de cd = D et r'j 10 désigne la log-vraisemblance de la décision douce R' délivrée par le décodeur SISO.

Le mode de mise en oeuvre selon le processus décrit par R. Pyndiah nécessite la mise en mémoire effective de 2p mots de n bits à l'étape a) pour chaque ligne ou colonne décodée.

En outre, l'étape précitée ayant été exécutée, la mise en oeuvre des étapes c) et d) exige chacune la conduite d'un calcul en boucle pour discriminer le mot de code décision dure respectivement le mot concurrent à distance minimale, vis-à-vis du mot de code produit reçu R. De telles opérations sont grandes consommatrices de ressources et de 20 temps de calcul et ne peuvent être facilement mises en oeuvre que grâce à des moyens de calcul très performants.

La présente invention a pour objet de remédier aux inconvénients du procédé de l'art antérieur précédemment décrit.

En particulier, un objet de la présente invention est de supprimer sensiblement l'opération de mémorisation des mots de code produit par la mise en oeuvre du processus itératif, selon l'algorithme de Chase rapide par exemple, afin, notamment, de permettre l'implantation de dispositifs décodeurs dans des appareils de capacité de calcul beaucoup plus réduite, n'excédant pas, par exemple, celle d'ordinateurs nomades, de terminaux de téléphonie mobile, voire d'assistants numériques personnels de type PDA, ou encore dans les systèmes de stockage de données numériques.

2871631 5 Un autre objet de la présente invention est enfin, du fait de l'introduction de la simplification précitée, la mise en oeuvre d'un procédé et d'un dispositif de décodage itératif de codes blocs dans lesquels le processus itératif est réduit à une seule boucle, les traitements en boucle des étapes c) et d) du procédé de l'art antérieur étant sensiblement supprimées, ce qui permet d'obtenir une réduction significative du temps de calcul pour effectuer le décodage, d'augmenter le nombre de mots de code de test servant au décodage, ou encore d'augmenter la longueur du code traité.

Le procédé de décodage itératif de codes blocs par décodage SISO d'un mot de code produit reçu à partir de mots de test décodés, objet de la présente invention, est remarquable en ce qu'il consiste au moins à engendrer au moyen d'un processus itératif une pluralité de mots de test décodés, calculer pour chaque mot de test décodé le poids analogique exprimé comme la demi-somme des produits de la valeur de chaque bit mappé à la valeur + ou 1 de ce mot de test décodé et de la probabilité de cette valeur, en termes de log-vraisemblance, classer et mémoriser lesdites valeurs de poids analogique, pour constituer un premier vecteur de poids analogique formé par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une première valeur et un deuxième vecteur de poids analogique formé par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une deuxième valeur, calculer la valeur de sortie de décision douce du décodage SISO, exprimée comme la différence des composantes de poids analogique du premier et du deuxième vecteur de poids analogique.

Le dispositif de décodage itératif de codes blocs par décodage SISO d'un mot de code produit reçu, à partir de mots de test décodés, objet de la présente invention, est remarquable en ce qu'il comprend au moins pour le traitement de chaque mot de code produit reçu, un module générateur, à partir d'un algorithme itératif, d'une pluralité de mots de test décodés, un module de calcul, pour chaque mot de test décodé, du poids analogique exprimé comme la demi-somme des produits de la valeur de chaque bit mappé à la valeur +1 ou -1 de ce mot de test décodé et de la probabilité de cette valeur, en termes de log-vraisemblance, un module de tri, par classification, des valeurs de poids analogique pour les mots de test décodés pour constituer un premier vecteur de poids analogique formé par les composantes de poids analogique des mots de 2871631 6 test décodés dont le bit de rang j est à une première valeur et un deuxième vecteur de poids analogique formé par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une deuxième valeur, un premier et un deuxième registre permettant de mémoriser lesdites valeurs de poids analogique classifiées selon ce premier respectivement ce deuxième vecteur de poids analogique et un module de calcul de la valeur de sortie de décision douce du décodage SISO, comprenant au moins un module soustracteur des composantes de poids analogique du premier et du deuxième vecteur de poids analogique.

Le procédé et le dispositif de décodage itératif de codes blocs objets de la présente invention trouvent application à leur implantation, sous forme de circuit intégré, dans tous les appareils récepteurs de signaux numériques et, en particulier dans les appareils légers, de faible encombrement et possédant des ressources de calcul limitées.

Ils seront mieux compris à la lecture de la description et à l'observation des dessins ci-après dans lesquels, outre les figures la et 1 b relatives à l'art antérieur: - la figure 2 représente, à titre illustratif, un organigramme des étapes essentielles de mise en oeuvre du procédé de décodage itératif objet de la présente invention; - la figure 3a représente, à titre illustratif, un organigramme détaillé de l'étape de classement des valeurs de poids analogique des mots de test décodés représentée en figure 2; - la figure 3b représente, à titre illustratif, un organigramme détaillé de l'étape de calcul de la valeur de décision douce représentée en figure 2.

Préalablement à la description proprement dite du procédé de décodage itératif de code bloc objet de la présente invention, un rappel sur le mode de mise en oeuvre du processus itératif de Chase rapide sera tout d'abord introduit. Le processus itératif de Chase rapide sera pris comme exemple non limitatif de mise en oeuvre d'un algorithme itératif permettant d'engendrer des mots de test décodés pour la mise en oeuvre du procédé objet de l'invention.

Le processus ou algorithme itératif de Chase rapide précité permet de simplifier les opérations du processus de Chase, précédemment mentionné dans la description, en parcourant les vecteurs de tests ou moyens d'un comptage de 2871631 7 type comptage de Gray. Ce mode opératoire permet de simplifier l'expression du syndrome calculé pour chaque itération, la notion de syndrome correspondant à la notion d'emplacement d'erreur après codage, en tirant parti des propriétés des codes blocs linéaires. Le calcul du poids pour chaque vecteur de tests est également simplifié en raison de la simplification de la mise à jour lorsqu'on considère le changement d'un seul bit.

Introduction des variables mises en oeuvre par le processus de Chase rapide.

Dans la mise en oeuvre précitée: É H désigne la matrice de contrôle du code BCH 1-correcteur mis en oeuvre à titre d'exemple. m désignant l'ordre du corps de Galois, H possède m colonnes et 2m 1 = n lignes. Le syndrome calculé est donné par la relation S=YH, Y désignant la décision obtenue par décodage dur sur le mot d'entrée. H; désigne la ième ligne de la matrice H. Le code est un code de Hamming étendu par un bit de parité, noté yo. Le bit de parité n'est pas pris en compte dans le calcul du syndrome mais contrôlé après coup.

On indique que si l'on procède au changement d'un seul bit de rang quelconque de Y, le nouveau syndrome est obtenu simplement par addition à l'ancien syndrome, addition modulo-2, du vecteur H; précité correspondant au bit de rang i. Le comptage de Gray introduit pour discriminer les vecteurs tests permet de ne changer qu'un seul bit par itération et de ce fait, simplifie de manière particulièrement significative le calcul du syndrome S en conséquence.

É R = {ro, ... , rn} désigne l'entrée souple mot reçu du décodage SISO et R'={r'o, ... , r'n} désigne la sortie souple du décodage SISO.

É Y = {yo, ... , yn} désigne la décision dure du mot R entrée souple du décodeur SISO avec y; E {0, 1}. Dans ces conditions, Ybm = J 0 ybmç désigne le vecteur testé à chaque itération de l'algorithme de Chase rapide, lequel permet de parcourir l'espace de l'ensemble des mots possibles autour du mot reçu par le comptage de Gray précédemment introduit, Yt = {yto, ... , ytn} désignant le mot obtenu par décodage dur.

É Poidsbm et Poids désignent les poids analogique de Ybm et Yt respectivement, vecteur testé à chaque itération et mot obtenu par décodage dur.

20 25 30 2871631 8 É Bm = {Bmi, ..., Bm2p_1} désigne l'ensemble des numéros des bits modifiés d'un mot de test au suivant à partir du mot reçu pour parcourir l'espace autour de ce dernier lors de la mise en oeuvre de l'algorithme de Chase rapide. Cette opération est équivalent à un comptage en binaire de Gray sur les vecteurs de tests. p désigne le nombre des positions les moins fiables prises en compte dans l'algorithme de Chase rapide. A titre d'exemple, pour p = 3, si les positions les moins fiables sont {3, 5, 9} alors Bm = {3, 5, 3, 9, 5, 3}.

É O+ désigne l'addition des bits modulo-2 (OU exclusif), cette opération s'effectuant bit à bit. Le déroulement du processus de Chase rapide est alors 10 introduit dans le tableau ci-après: A) Initialisation Variables Les variables précitées utilisées sont initialisées de la manière suivante: Ybm = Y et Poidsbm=0 (le premier mot testé par l'algorithme est le mot reçu, et le poids est considéré comme nul pour le mot reçu) Yt = Y et Poids = 0 (Yt est initialisé à la valeur du premier mot testé avant d'être décodé dans la prochaine étape) Décodage dur Calcul du syndrome: S = YtH Si S 0 alors Détermination de la position de l'erreur e par tableau de correspondance puis correction par: yte 1 -> yte et mise à jour du poids par: Poids - (2yte -1) re -* Poids. Correction du bit de parité Calcul de b = yt, O+ ... O+ ytn Si b yto alors = correction par: yto c, 1+ yto et mise à jour du poids par: Poids - (2yto - 1) ro -> Poids.

On possède à ce moment le mot Yt obtenu par décodage dur du mot reçu Y et son poids analogique. C'est le premier mot de test et on le stocke en mémoire.

B) Itérations de l'algorithme A chaque nouvelle itération, les variables conservent les valeurs qu'elles avaient à la fin de la précédente itération et pour t = 1 à t = 2p -1 on effectue les opérations suivantes: Modification du bit pour obtenir le mot suivant On obtient le mot à tester pour l'itération courante à partir de celui de l'itération précédente par la modification d'un seul bit déterminé par le vecteur Bm: YBm(t) O+ 1 YBm(t) On met à jour le poids du vecteur testé : Poidsbm - (2ytBm(t) -1)rBm(t) PoidSbm Yt = Ybm et Poids = Poidsbm (Yt est initialisé à la valeur du premier mot testé avant d'être décodé) Décodage dur Le nouveau syndrome peut être déduit très simplement du précédent car un seul bit a été modifié : S HBm(t) 4 S Si S 0 alors Détermination de la position de l'erreur e par tableau de correspondance puis correction par: yte e -> yte et mise à jour du poids par: Poids - (2yte -1) re --> Poids. Correction du bit de parité Calcul de b = yt1 ... ytr, Si b yto alors correction par: yto e 1 -3> yto et mise à jour du poids par: Poids - (2yto - 1) ro Poids.

On dispose du mot Yt produit par le décodage dur du vecteur testé Ybm et son poids analogique. On sauvegarde alors le mot de test courant Yt ainsi que son poids.

L'indice i est incrémenté et on retourne à l'étape Itérations de l'algorithme, Modification du bit pour obtenir le mot suivant: 2871631 10 On calcule ensuite les fiabilités de la même manière qu'indiqué précédemment en utilisant les vecteurs précédemment stockés.

Dans les relations du tableau, le symbole -> représente l'opération d'affectation d'une valeur à une variable.

Le procédé de décodage itératif de codes blocs objet de la présente invention sera maintenant décrit en liaison avec la figure 2.

En référence à la figure 2 précitée, on indique que le procédé de décodage, objet de l'invention, consiste pour tout mot code produit reçu R, de la forme R = {al, ..., agi, ... an} où les composantes ai de R désignent les valeurs analogiques de R détectées après transmission ou lecture, à engendrer en une étape A, par un processus itératif, tel que l'algorithme de Chase rapide, une pluralité de mots de test décodés notés Yt = iyt,, Les mots de test décodés Yt sont obtenus à partir d'une ligne ou d'une colonne du mot de code produit reçu R. Ces opérations sont ensuite appliquées séquentiellement à toutes les lignes ou toutes les colonnes suivant l'itération considérée.

On effectue, en premier lieu, une décision dure Y sur le mot de code produit reçu R et l'on décide donc des valeurs des bits de Y, 0 ou 1 (ou 1 ou +1 selon la convention retenue) à partir des valeurs souples, sans effectuer de décodage.

A titre d'exemple pour un vecteur ligne ou colonne reçu VR = {-0.1 0.55; 0.2; -0.6} la décision dure retenue Y est Y ={0;1;1;0} ou {-1;+1;+1;-1} selon la convention choisie.

On engendre, en deuxième lieu, les vecteurs de test, en modifiant les p bits sélectionnés comme étant les moins fiables, sur la décision dure Y précitée, non décodée, selon toutes les combinaisons binaires possibles. Les mots de test décodés Yt sont alors obtenus en décodant par décodage dur les vecteurs de test précités.

Parmi l'ensemble de ces combinaisons, celle où l'on ne change pas les 30 p bits les moins fiables correspond au mot de test décodé Yt obtenu par décodage direct de la décision dure Y. 2871631 11 Les mots de test décodés suivants sont obtenus à partir de la décision dure Y dans laquelle on procède à la modification des p bits les moins fiables pour obtenir un vecteur de test, lequel est soumis à un décodage dur.

Le procédé objet de l'invention consiste, en particulier, à engendrer 2P mots de test décodés pour les 2P bits du mot reçu décodé Y issus du décodage dur, dont la valeur est la moins fiable.

On comprend, en particulier, que la mise en oeuvre de l'algorithme de Chase rapide précité permet d'obtenir les mots de tests décodés Yt précédemment décrits, lesquels correspondent aux mots de test précédemment mentionnés.

L'étape A est alors suivie d'une étape B, représentée sur la figure 2, consistant à calculer pour chaque mot de test décodé Yt le poids analogique exprimé comme la demi-somme des produits de la valeur de chaque bit mappé à la valeur 1 de ce mot de test décodé et de la probabilité de cette valeur en termes de log-vraisemblance.

On rappelle, en référence au tableau précédemment introduit, que les poids analogiques des mots de tests décodés Yt ont été obtenus, ainsi que mentionné dans le tableau précité.

Le poids analogique, noté Poids de façon générique pour les mots de 20 test décodés, vérifie alors la relation (15) : n Poids= 2E r; c. (15). -o

Dans la relation précédente: r; désigne la valeur de log-vraisemblance du bit de rang i correspondant, i étant un indice de calcul correspondant en fait à l'indice du bit mappé à la valeur +1 respectivement -1 et c; désigne cette valeur mappée pour chaque mot de test décodé Yt.

Un justificatif du mode de calcul du poids analogique à l'étape B et de l'expression de ce dernier pour la mise en oeuvre du procédé de décodage itératif objet de la présente invention sera maintenant donné ci-après.

Pour les mots concurrents C+1(i) et C-1U) mots concurrents à distance minimale du mot de code produit reçu R selon le processus de décodage de l'art antérieur de R. Pyndiah, la définition des poids analogique est donnée par: +1(j) m +1(j)

R-C

2 -1(i)-I et mR-C-1(j) La valeur de la log-vraisemblance pour chaque mot concurrent est donnée par la relation: -1(D +1 (i) m+1G)_ +1) i=o ri-ci i=o 2871631 m -m rj= 4 Cependant ces mêmes valeurs s'expriment par les relations 2 i=0 C: i 2 C t i \ / \ i=0 / L'introduction de la définition du nouveau poids analogique Poids pour chaque mot de test décodé par la relation (15) précédemment donnée dans la description permet alors de conserver le même ordre de classement qu'avaient les définitions classiques de l'art antérieur.

En conséquence, l'expression du poids analogique précédemment mentionné à la relation (15) peut donc être avantageusement utilisée pour classer les mots de test décodés engendrés par l'algorithme de Chase rapide.

Dans le cas particulier du processus de Chase rapide, on obtient toutes les combinaisons possibles des vecteurs de test, lesquels n'ont pas été encore décodés, en modifiant un seul bit du vecteur de test de l'itération t précédente pour obtenir le vecteur de test suivant de l'itération t+1 courante pour obtenir le vecteur de test suivant de l'itération t+1 courante, et ainsi de suite, à partir du premier vecteur de test, pour obtenir toutes les combinaisons possibles de ces bits sur les positions sélectionnées.

Pour ne pas retomber plusieurs fois sur le même vecteur, ou en oublier un, les bits du vecteur de test de l'itération précédente sont modifiés, à raison d'un seul de ceux-ci, selon une séquence spécifique à partir d'un comptage de Gray, permettant de passer en revue toutes les combinaisons possibles des bits.

m-1U) _ Ç+12rici1W) i=o En conséquence, la valeur de la log-vraisemblance peut être exprimée sous la forme de la relation (16) (16) 2871631 13 L'ordre de changement des bits est contenu dans un vecteur respectant ce mode de comptage.

Le fait de ne changer qu'un seul bit à chaque itération permet d'obtenir le poids P' du nouveau vecteur de test pour l'itération courante t+1 à partir de l'itération t précédente selon la relation: P'=P-rkc'k (17) où P désigne le poids du vecteur de test de l'itération précédente, rk désigne la fiabilité en termes de log-vraisemblance du bit de rang k modifié et c'k la nouvelle valeur mapée à 1 du bit de rang k modifié.

Le mot de test décodé de l'itération courante est obtenu en décodant par décodage dur le vecteur de test considéré de cette même itération.

En raison du fait que le décodage dur ne met en oeuvre la modification éventuelle que d'un seul bit à la fois, si le mot de test décodé n'appartient pas au code, la mise à jour des poids selon la relation (17) peut alors également être utilisée pour obtenir le poids analogique du mot de test décodé Yt.

Le processus de calcul du poids analogique précédemment mentionné dans la description en liaison avec l'étape B permet alors, conformément à un aspect particulièrement remarquable du procédé objet de la présente invention, de calculer la valeur de la sortie douce du décodage SISO selon la relation (16) précédemment citée dans la description. Ceci, tout en conservant à chaque fois la distance minimale avec la contrainte que le j1ème bit du mot concurrent soit à la valeur mappée à la valeur +1 ou - 1 pour j = 0 à n.

En conséquence, suite à l'étape B de la figure 2, le procédé de décodage itératif, objet de la présente invention, consiste à effectuer un classement et, bien entendu, une mémorisation des valeurs de poids analogique pour les mots de test décodés, de façon à constituer un premier vecteur VI de poids analogique formé par les composantes de poids analogique PME des mots de test décodés dont le bit de rang j est mappé à une première valeur +1 et un deuxième vecteur V2 de poids analogique formé par les composantes de poids analogique PME des mots de test décodés dont le bit de rang j est mappé à la deuxième valeur 1.

L'opération de classement est représentée symboliquement à l'étape C de la figure 2 par la relation: 2871631 14 Poids ->V1 (PMj) ou V2(PMj) On comprend en particulier que les étapes A, B, C représentées en figure 2 et, notamment les étapes B et C peuvent être intégrées dans le processus itératif de l'algorithme de Chase rapide, ce processus itératif étant représenté par l'étape de retour de l'étape C à l'étape A notée t = t+1 sur la figure 2. On comprend que l'indice t désigne le passage du mot de test décodé engendré à l'itération courante au mot de test décodé de l'itération suivante pour l'exploitation des 2 mots de test décodés.

L'ensemble des valeurs de poids analogique PM; et PMi ayant été classées sous forme des vecteurs VI et V2, l'on peut alors appeler une étape D de calcul de décision douce, c'est-à-dire du décodage SISO, exprimée comme la différence des composantes de poids analogique du premier et du deuxième vecteurs VI et V2 de poids analogique.

Une description plus détaillée du processus de classement des valeurs 15 de poids analogique pour les mots de test décodés, étape C de la figure 2 sera maintenant donnée en liaison avec la figure 3a.

En référence à la figure précitée, le processus de classement du procédé objet de la présente invention comporte une étape d'initialisation du premier VI et du deuxième V2 vecteur de poids analogique selon laquelle chaque composante de poids analogique PM; pour le premier vecteur VI relatif aux composantes de poids analogique des mots de test décodés dont le bit de rang j est à une première valeur et respectivement Pm-; pour le deuxieme vecteur V2 de poids analogique relatif aux composantes de poidsanalogique des mots de test décodés dont le bit de rang j est à la deuxième valeur sont initialisées à la valeur PMi = +oo respectivement PMi = +0o, pour toutes les valeurs de j appartenant à 0... n.

L'opération d'initialisation est représentée de manière symbolique par: V = Poids min+ _ 'M0 PMj PMn V2 = Poids min = PMO'ÉÉÉ'PMj,...,Pm-n} 2871631 15 les vecteurs VI et V2 représentant la liste des poids analogiques des mots de test décodés Yt issus du mot reçu avec le génie bit respectivement à la première valeur 1 et à la deuxième valeur 0 respectivement.

Une initialisation proprement dite s'écrit pour j = 0... n alors pM; = + 0o et pMi = + co.

La liste contenant les poids minimaux doit être comprise comme telle en raison du processus mis en oeuvre par les étapes CI et C2 ci-après appelées suite à l'étape d'initialisation Co et à la première itération de l'algorithme de Chase rapide notée CI sur la figure 3a.

L'opération consistant à classer et mémoriser les valeurs de poids analogique consiste alors à classer les valeurs de poids analogique du premier mot de test obtenu dans les vecteurs de poids analogique des poids minimaux en fonction de la valeur des bits de ce dernier, le premier mot de test premier testé présentant le poids minimum par rapport aux valeurs de poids arbitraires d'initialisation.

Le mot de test décodé considéré est le mot de test Yt.

L'opération dite de lancement effectuée en fin de première itération à l'étape CI s'écrit: Pour j = 0...n, Si ytt = 0 -+ pMi = Poids, le mot de test décodé Yt étant considéré pour le moment comme celui qui présente un bit de rang j = 0 à distance minimum du mot reçu R. Si yj = 1 pM; = Poids, le mot de test Yt étant considéré comme le mot ayant le bit de rang j = 1 à distance minimum du mot reçu.

L'étape CI de lancement est alors suivie d'une étape C2, dite de poursuite, qui a pour objet d'examiner tous les mots de tests décodés, Yt par itération. Ainsi, en référence à l'étape C2 de la figure 3a, le processus de classement consiste à classer le poids actuel obtenu au cours de l'itération courante de l'algorithme de Chase rapide dans le premier VI respectivement le deuxième V2 vecteur de poids analogique minimum, si et seulement si le poids actuel Poids est inférieur à la valeur de poids présente pour la composante de même rang mémorisée à l'itération précédente ou à une itération antérieure.

2871631 16 L'opération de classement proprement dite s'écrit: pour j = 0.. . n, si ytj = 0 et Poids < PM; -> PM; = Poids si yti = 1 et Poids < PM; * PM; = Poids Dans les relations indiquées avec la description des étapes CI et C2, on rappelle que le signe = indique l'affectation à la variable de la valeur poids, lorsque la condition d'infériorité est satisfaite.

Enfin, une description plus détaillée de l'étape D de la figure 2 de calcul de la valeur de sortie de décodage SISO sera maintenant donnée en liaison avec la figure 3b.

En référence à la figure 3a, à la fin de l'étape C2, on dispose des vecteurs VI et V2, listes des valeurs de poids analogique des mots de test décodés avec le j1ème bit à 1 première valeur et à 0 deuxième valeur.

L'opération de calcul représentée à l'étape D de la figure 2 consiste alors, à partir des valeurs pMj et pM7j, pour tout bit de rang j appartenant à 0, n, de chaque mot de test décodé si la valeur des composantes de poids analogique est différente de la valeur d'initialisation, c'est-à-dire +co, on calcule la probabilité de la valeur du bit de rang j correspondant comme la différence des valeurs de poids analogique effectif PM; et PM; A titre d'exemple non limitatif, la condition précitée peut être réalisée par les tests DI et D2 représentés en figure 3b, de différence des valeurs pMj et PM; à la valeur d'initialisation +0o précédemment mentionnée.

On comprend en fait que la valeur +00 peut être représentée par toute valeur arbitrairement grande et non compatible avec une valeur effective de poids analogique vraisemblable. Le test de différence peut alors consister en un test d'infériorité par exemple.

Le calcul de la différence des valeurs de poids analogique est représenté à l'étape D4.

Sinon, si la valeur de la composante de poids analogique pMi du mot de test décodé dont le bit de rang j est à une valeur, la valeur 0 par exemple, est seule différente de la valeur d'initialisation +00, on affecte à la probabilité de la 2871631 17 valeur du bit de rang j une première valeur déterminée négative. Cette opération peut être réalisée, ainsi que représenté en figure 3b, sur réponse négative au test DI en une étape D3.

Sinon, si la valeur de la composante de poids analogique pMi du mot de test décodé, dont le bit de rang j est à l'autre valeur la valeur 1 par exemple, est différente de la valeur d'initialisation, on affecte à la probabilité de la valeur du bit de rang j une valeur déterminée opposée à la première valeur déterminée. Cette opération est réalisée sur réponse négative au test D2 à l'étape D5.

Les première et deuxième valeurs déterminées négative respectivement positive sont les valeurs [3, coefficient de pondération du turbodécodage.

Une économie de mémoire supplémentaire peut être obtenue dans le but de mettre en oeuvre le procédé de décodage de code produit en éliminant Y, c'est-à-dire le mot de test décodé après décodage dur formant le mot de test décodé de la mise en oeuvre de l'algorithme. Dans cette situation, on n'utilise que le vecteur de test Ybm constituant le mot de test. Ce mot de test peut être réaffecté à sa vraie valeur du début de l'itération après avoir été soumis à un décodage dur pour constituer le mot de test correspondant, afin de ne pas changer la liste des mots de test, si l'on a conservé la valeur du bit erroné et une variable indiquant une erreur de parité éventuelle. Ce processus opératoire permet en outre d'éviter de réaffecter à chaque fois la valeur Yt du mot de test après décodage dur, c'est-à-dire du mot de test décodé à la valeur de Ybm Enfin, le bit de parité de chaque mot de test peut être mis à jour à chaque fois qu'un bit de rang j est modifié, ce qui évite la nécessité de faire la somme de tous les bits à chaque fois pour recalculer la valeur de parité.

Le procédé objet de la présente invention est remarquable vis-à-vis des procédés de l'art antérieur, en ce qu'il permet un gain considérable au niveau du nombre de portes logiques utilisées et de temps de calcul effectif nécessaire tout en conservant le même résultat de calcul.

D'une première part, le fait d'exploiter les propriétés des syndromes des codes blocs dans le cadre de l'algorithme de Chase rapide divise par n le temps de calcul du syndrome considéré. En fait, on divise par le même facteur la quantité d'opérations nécessaires au calcul du poids analogique et donc, de 2871631 18 manière globale, le temps de calcul du processus d'exploration de tous les vecteurs de test par l'algorithme de Chase rapide est lui-même divisé par n.

D'une deuxième part, le nouveau mode opératoire du calcul des fiabilités utilisé conformément à l'objet de la présente invention permet de s'affranchir totalement de la mise en mémoire des mots de test décodés examinés par le processus d'algorithme de Chase rapide itératif. Ce mode opératoire élimine ainsi la nécessité de mise en oeuvre d'une quantité de mémoire correspondant à nx2P bits et ce, pour chaque ligne ou colonne du code produit, ce qui donne une économie totale de n2x 2P bits pour le décodage du code produit complet sur une demi-itération. La quantité de mémoire alors nécessaire pour stocker les poids analogiques pMi et pMi ne dépend plus que de la longueur du code et du nombre de bits de la quantification, et, en conséquence, ne dépend aucunement du nombre de mots concurrents ou mots de tests choisis.

De plus, ainsi que représenté de manière illustrative en figure 2, toutes les opérations sont effectuées en une seule boucle pour l'ensemble des bits d'une ligne ou d'une colonne du code. Ce mode de mise en oeuvre permet donc une implantation très légère du procédé de décodage objet de l'invention et il est en outre possible d'augmenter le nombre de mots de tests décodés, afin d'améliorer les performances du turbo décodage.

Un dispositif de décodage itératif de codes blocs par décodage SISO d'un mot de code reçu R constitué de n bits, à partir de mots de test décodés, conformément au procédé objet de la présente invention, précédemment décrit, sera maintenant décrit en liaison avec la figure 4.

Le dispositif objet de l'invention est réputé, de manière non limitative, intégré dans un terminal de téléphonie mobile, un assistant numérique de type PDA ou un ordinateur portable par exemple.

Ce type d'appareil comprend, de manière classique, une unité centrale de traitement, CPU, formée par un microprocesseur, une mémoire vive, mémoire RAM, jouant le rôle de mémoire de travail, et une mémoire permanente, telle qu'une mémoire ROM, mémoire non volatile par exemple.

Le dispositif objet de l'invention représenté en figure 4 comprend en outre un module générateur à partir d'un algorithme itératif tel que l'algorithme de Chase rapide d'une pluralité de mots de test décodés.

2871631 19 On comprend que le module générateur précité peut consister en un module de programme enregistré en mémoire permanente ROM1 et appelé en mémoire de travail RAM pour exécution de l'algorithme de Chase rapide décrit précédemment en liaison avec le Tableau de la présente description conformément à l'étape A) de la figure 2.

Il comporte en outre un module de calcul du poids analogique de chaque mot de test décodé Yt conformément à l'étape B de la figure 2. Le module de calcul précité peut consister en un module de programme enregistré en mémoire permanente ROM2 et appelé en mémoire de travail pour exécution selon la relation indiquée à l'étape B) de la figure 2.

Il comporte également un module de tri par classification des valeurs de poids analogique pour les mots de test décodés Yt précités. Ce module de tri peut être constitué par un module de programme ROM3, appelé en mémoire de travail RAM pour exécution conformément au procédé objet de l'invention représenté en figures 2 étape C et 3a.

Il comporte, selon un aspect remarquable du dispositif objet de l'invention, un premier Ri et un deuxième registre R2 permettant de mémoriser les valeurs de poids analogique classifiées selon le premier et le deuxième vecteur Vt, V2 de poids analogique, relatif chacun aux composantes de poids analogique des mots de test décodés.

A titre d'exemple non limitatif, on indique que les registres précités peuvent être configurés comme une zone mémoire protégée de la mémoire de travail RAM ou par une mémoire non volatile reprogrammable électriquement, de façon à permettre une reconfiguration de chaque registre Ri, R2, en fonction du nombre de mots de test décodés finalement retenus pour la mise en oeuvre du décodage.

L'utilisation d'une mémoire non volatile reprogrammable électriquement permet de ménager une séparation et donc une protection physique des données de vecteurs de poids analogique et des données traitées en mémoire vive RAM.

Enfin, le dispositif objet de l'invention comporte, ainsi qu'illustré par la figure 4, un module de calcul de la valeur de sortie de décision douce de décodage SISO comprenant au moins un module soustracteur des composantes de poids analogique du premier et du deuxième vecteur analogique mémorisées dans les registres Ri respectivement R2.

2871631 20 Ce module de calcul peut être constitué par un module de programme ROM4 appelé en mémoire de travail pour exécution conformément au procédé objet de l'invention représenté en figure 2 étape D et 3b.

Enfin le mode de réalisation du dispositif de décodage objet de la 5 présente invention peut avantageusement être exécuté sous forme de chip, circuit intégré dédié.

En particulier le procédé et le dispositif de décodage selon l'invention trouvent application à la mise en oeuvre de systèmes ou appareils de stockage de données codées et de restitution de ces données codées sous forme 10 décodée.

2871631 21

Claims (5)

REVENDICATIONS

1. Procédé de décodage itératif de codes blocs par décodage SISO d'un mot de code produit reçu (R) constitué de n bits, à partir de mots de test décodés, caractérisé en ce que celui-ci consiste au moins à : - engendrer au moyen d'un processus itératif une pluralité de mots de test décodés; calculer, pour chaque mot de test décodé, le poids analogique exprimé comme la demi-somme des produits de la valeur de chaque bit mappé à 1 de ce mot de test décodé et de la probabilité de cette valeur, en termes de log-vraisemblance; - classer et mémoriser lesdites valeurs de poids analogique pour les mots de test décodés, pour constituer un premier vecteur de poids analogique formé par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une première valeur et un deuxième vecteur de poids analogique formé par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une deuxième valeur; - calculer la valeur de sortie de décision douce du décodage SISO comme la différence des composantes de poids analogique du premier et du deuxième vecteur de poids analogique.

2. Procédé selon la revendication 1, caractérisé en ce que celui-ci comporte une étape d'initialisation du premier et du deuxième vecteur de poids analogique, chaque composante de poids analogique pMJ pour le premier vecteur de poids analogique relatif aux composantes de poids analogique des mots de test décodés dont le bit de rang j est à la première valeur respectivement PME pour le deuxième vecteur de poids analogique relatif aux composantes de poids analogique des mots de test décodés dont le bit de rang j est à la deuxième valeur étant initialisées a la valeur PME = +.0 respectivement PM! = +00 pour toute valeur de j=0... n, le premier et le deuxième vecteur de poids analogique initialisé contenant les poids minimaux.

3. Procédé selon les revendications 1 et 2, caractérisé en ce que suite à l'étape d'initialisation et à la première itération de l'algorithme délivrant les mots de test décodés, ladite opération consistant à classer et mémoriser lesdites valeurs de poids analogique consiste à : 2871631 22 - classer les valeurs de poids analogique du premier mot de test décodé obtenu dans les vecteurs de poids analogique des poids minimaux en fonction de la valeur des bits de ce dernier, le premier mot de test décodé, premier testé, présentant le poids analogique minimum par rapport aux valeurs de poids arbitraire d'initialisation; et pour chaque itération successive courante, - classer le poids analogique actuel obtenu au cours de l'itération courante dans le premier respectivement le deuxième vecteur de poids analogique si et seulement si ledit poids analogique actuel est inférieur à la valeur de poids analogique présente pour la composante de même rang mémorisée à l'itération précédente ou à une itération antérieure.

4. Procédé selon l'une des revendications 1 à 3, caractérisé en ce que l'étape consistant à calculer la valeur de sortie de décodage SISO consiste, pour tout bit de rang j E [o, n], ^ si la valeur des composantes de poids analogique des vecteurs de poids est différente de la valeur d'initialisation, +cc, calculer la probabilité de la valeur du bit de rang j correspondant exprimée comme la différence des valeurs de poids analogique; ^ sinon, si la valeur de la composante de poids analogique de l'un des vecteurs de poids, est seule différente de la valeur d'initialisation, +. 0, affecter à la probabilité de la valeur du bit de rang j une première valeur déterminée; ^ sinon, si la valeur de la composante de poids analogique de l'autre des vecteurs de poids est seule différente de la valeur d'initialisation, , affecter à la probabilité de la valeur du bit de rang j une deuxième valeur déterminée opposée à ladite première valeur déterminée.

5. Dispositif de décodage itératif de codes blocs par décodage SISO d'un mot de code produit reçu constitué de n bits à partir de mots de test, caractérisé en ce que celui comprend au moins pour le traitement de chaque mot de code produit reçu: a) des moyens générateurs, à partir d'un algorithme itératif, d'une 30 pluralité de mots de test décodés; b) des moyens de calcul, pour chaque mot de test décodé, du poids analogique exprimé comme la demi-somme des produits de la valeur de chaque bit mappé à 1 de ce mot de test décodé et de la probabilité de cette valeur, en termes de log-vraisemblance; 2871631 23 c) des moyens de tri, par classification, desdites valeurs de poids analogique pour les mots de test décodés, pour constituer un premier vecteur de poids analogique formé par les composantes de poids analogique des mots de test décodés dont le bit de rang j est à une première valeur et un deuxième vecteur de poids analogique formé par les composantes de poids analogiques des mots de test décodés dont le bit de rang j est à une deuxième valeur; di) un premier et un deuxième registre permettant de mémoriser lesdites valeurs de poids analogique classifiées selon ledit premier respectivement ledit deuxième vecteur de poids analogique; d2) des moyens de calcul de la valeur de sortie de décision douce décodage SISO, comprenant au moins un module soustracteur des composantes de poids analogique du premier et du deuxième vecteur de poids analogique.