Brevet FR2945391A1 — publié le 20101112

La présente invention concerne un procédé de commande d'une unité de calcul, telle qu'un noeud de parité élémentaire dans un décodeur de codes LDPC non binaires, et l'unité de calcul correspondante. Les codes LDPC (Low Density Parity Check en langue anglaise) sont des codes correcteurs d'erreur connus pour approcher la limite théorique de transmission de Shannon. En raison de leurs performances en termes d'immunité au bruit, les codes LDPC, et notamment les codes LDPC non binaires, trouvent une application dans le domaine de la transmission et du stockage de données numériques. Les codes LDPC non binaires sont construits dans un corps de Galois non binaire d'ordre q, notés classiquement GF(q). Un code LDPC dans GF(q) est défini par une matrice de parité H creuse de dimension M x N dont les éléments appartiennent à GF(q), N étant le nombre d'éléments de GF(q) dans le mot de code et M étant le nombre de contraintes de parité. Pour un corps de Galois GF(4) composé de 4 éléments }0, a°, al, a2}, la matrice de parité pour N=6 et M=3 est par exemple la suivante: 0 a° a° 0 2 0 H = al 0 0 a° 0 a2 a° 0 a2 0 0 al) Cette matrice peut également être représentée par un graphe bipartite (graphe de Tanner) ayant N noeuds de variable recevant les symboles du mot de code et M noeuds de parité. Chaque colonne de la matrice de parité est associée à un noeud de variable et chaque ligne de la matrice est associée à un noeud de parité. Dans le cas d'un code LDPC régulier, chaque noeud de parité est connecté, par l'intermédiaire de d, branches, à un même nombre d, de noeuds de variable. Réciproquement, chaque 2 noeud de variable est connecté, par l'intermédiaire de dV branches, à un même nombre dV de noeuds de parité. Dans le cas d'un code LDPC irrégulier, le nombre d, ou dV de branches varie selon le noeud de variable ou noeud de parité. Le décodage de ces codes LDPC est itératif et consiste à échanger via ces branches des messages, chaque noeud de variable ou de parité traitant les messages reçus et délivrant, après traitement, d'autres messages à destination, selon le cas, des noeuds de parité ou des noeuds de variable auxquels ils sont connectés par des branches. Les messages échangés représentent des densités de probabilité des symboles du code et se présentent donc sous la forme de vecteurs de taille q. Un tel décodage est décrit dans le document intitulé � Decoding Algorithms for Nonbinary LDPC Codes Over GF(q) � de D.Declercq et M.Fossorier, Communications IEEE Transactions on Volume 55, Issue 4, April 2007, Pagess633 - 643. L'invention concerne plus particulièrement le procédé de commande des noeuds de parité du décodeur. En référence à la figure 1, chaque noeud de parité P reçoit une pluralité de messages entrants Ui et délivre des messages sortants Vi, avec i e [0.. .dv û 1], tels que Vj = O Ui j~i où O+ est l'opérateur sur les densités de probabilité associé à 1"addition du corps de Galois GF(q). Dans l'exemple de la figure 1, le noeud de 30 parité reçoit d,=4 messages entrants Uo, Ui, U2, U3 et délivre 4 messages sortants Vo, V1r V2, V3 tels que: V0 = U1 O+ U2 O+ U3 Vl = U0 O+ U2 O+ U3 V2 = U0 O+ U1 O+ U3 V3 = Uo U1 O+ U2 On peut décomposer chacun de ces calculs en calculs élémentaires exécutés par des noeuds de parité élémentaires ayant deux entrées et une sortie. Par exemple, pour le calcul de Vo, un premier noeud de parité élémentaire effectue l'opération U1 O+ U2 = Uint puis un second noeud de parité élémentaire effectue l'opération Uint O+ U3. A noter que le résultat intermédiaire Uint à la sortie du premier noeud de parité élémentaire est également utilisé pour calculer V3. Ainsi, on peut décomposer chaque noeud de parité en une pluralité de noeuds de parité élémentaires recevant chacun deux messages entrants, par exemple Ui et U2, et délivrant un message sortant Uout=Uint. Un tel noeud est représenté schématiquement à la figure 2. Chaque message entrant ou sortant est un vecteur de taille q associant une densité de probabilité à chaque élément du corps de Galois. Dans la suite de la description, on considère à titre d'exemple un corps de Galois GF(4) composé des éléments }0, a°, al, a2} dont les lois d'addition et de multiplication sont définies par les tableaux suivants: 3 o a° al a2 o o a° al 2 îO a° o a2 al al al a2 0 a° a2 a2 al a° 0 0 o a° al a2 0 0 0 0 o îO o a° al a2 al 0 al a2 ° a2 0 a2 ° al L e messages entrants sont par exemple Ui= (ao, ai, a2r a3) et U2= (bo, bi, b2, b3) où ai est la densité de probabilité associé à l'élément o' dans le message Ui et 4 où bi est la densité de probabilité associé à l'élément OC' dans le message U2, i e [0...3], avec ao+a1+a2+a3=1 et bo+b1+b2+b3=1 . Compte tenu de la loi d'addition définie ci-5 dessus pour le corps de Galois GF(4), le message sortant Uout est égal à Uout = (co, cir c2, c3) où co= ao-bo + ai-bi + a2-b2 + a3-b3 c1= ao-bi + ai-bo + a3-b2 + a2-b3 c2= ao-b2 + ai-b3 + a2-bo + a3-bi 10 c3= ao-b3 + ai-b2 + a2-bi + a3-bo Des densités de probabilité sont ainsi échangées entre les noeuds de parité et les noeuds de variable, et inversement, jusqu'au décodage complet du mot de code. On parle alors d'algorithme de propagation 15 de croyances ou "belief propagation" en langue anglaise. La mise en oeuvre d'un tel algorithme est relativement complexe et nécessite l'exécution de q2 multiplications dans chaque noeud de parité élémentaire pour des éléments appartenant à GF(q). 20 Pour réduire cette complexité, il est connu de travailler dans le domaine logarithmique pour transformer les multiplications en additions. Les données échangées entre noeuds sont des logarithmes de rapport de vraisemblance ou LLR (pour Log Likelihood Ratio en langue 25 anglaise). Une autre solution connue pour réduire cette complexité consiste à ne tenir compte, pour le calcul des densités de probabilité du message sortant, que des nm plus grandes densités de probabilité dans les messages 30 entrants, nm 6 a) sélectionner les p premiers éléments de la première liste d'entrée et le premier élément de la deuxième liste d'entrée, p étant un nombre prédéterminé inférieur à nm, b) effectuer des opérations de calcul (p entre les éléments sélectionnés de la première liste d'entrée et l'élément sélectionné de la seconde liste d'entrée de manière à générer une liste de p éléments candidats pour la liste de sortie, c) déterminer, parmi les p éléments candidats, l'élément candidat ayant la valeur la plus élevée si l'ordre défini est l'ordre décroissant ou l'élément candidat ayant la valeur la plus faible si l'ordre défini est l'ordre croissant, et l'introduire dans la liste de sortie, l'élément candidat introduit dans la liste de sortie étant le résultat de l'opération de calcul (p entre un élément d'ordre i de la première liste d'entrée et un élément d'ordre j de la deuxième liste d'entrée, i et j étant compris entre 1 et nm, d) sélectionner, selon un critère prédéterminé, l'élément d'ordre i de la première liste d'entrée et l'élément d'ordre j+1 de la deuxième liste d'entrée ou l'élément d'ordre i+1 de la première liste d'entrée et l'élément d'ordre j de la deuxième liste d'entrée, e) effectuer une opération de calcul (p entre les éléments sélectionnés à l'étape précédente de manière à générer un nouvel élément candidat, et remplacer, dans la liste des p éléments candidats, le dernier élément candidat introduit dans la liste de sortie par ledit nouvel élément candidat, f) déterminer, parmi les p éléments candidats, l'élément candidat ayant la valeur la plus élevée si l'ordre défini est l'ordre décroissant ou l'élément candidat ayant la valeur la plus faible si l'ordre défini est l'ordre croissant, et l'introduire dans la liste de sortie dans l'ordre de détermination, l'élément candidat 7 introduit dans la liste de sortie étant le résultat de l'opération de calcul entre un élément d'ordre i de la première liste d'entrée et un élément d'ordre j de la deuxième liste d'entrée, et g) réitérer les étapes d) à f) jusqu'à ce que la liste de sortie comporte nm' éléments. Ainsi, selon l'invention, la liste des éléments candidats pour chaque élément de la liste de sortie ne comporte que p 8 plus faible ou la plus élevée, une étape de détermination du symbole associé audit élément candidat déterminé, ledit élément candidat déterminé étant introduit dans la liste de sortie si et seulement si le symbole associé audit élément candidat déterminé n'est pas associé à un élément candidat déjà présent dans liste de sortie c'est-à-dire à l'élément candidat introduit dans la liste de sortie à l'étape c) ou à un élément candidat introduit dans la liste de sortie à une étape f) précédente. L'invention concerne également une unité de calcul, telle qu'un noeud de parité élémentaire pour décodeur de codes LDPC non binaires, comprenant: - des première et seconde entrées pour recevoir des première et seconde listes, dites première et seconde listes d'entrée, de nm éléments triés dans un ordre défini parmi un ordre décroissant et un ordre croissant, nm étant supérieur à 1, - une sortie pour délivrer une liste, dite liste de sortie, de nm' éléments triés dans l'ordre défini, nm' étant supérieur ou égal à 1, chaque élément de la liste de sortie étant le résultat d'une opération de calcul cp entre un élément de la première liste d'entrée et un élément de la deuxième liste d'entrée, ladite opération de calcul cp étant telle que si a?b et c?d alors cp(a, c) cp(b, d), - des premiers moyens de stockage pour stocker les éléments desdites première et secondes listes d'entrée, - un circuit de calcul pour effectuer des opérations de calcul cp entre des éléments de la première liste d'entrée et des éléments de la seconde liste d'entrée stockés dans lesdits premiers moyens de stockage de manière à générer, à chaque opération, un élément candidat, 9 - des seconds moyens de stockage pour stocker les éléments candidats calculés par lesdits moyens de calcul, - un circuit de comparaison pour déterminer, parmi les éléments candidats stockés dans les seconds moyens de stockage, l'élément candidat ayant la valeur la plus élevée si l'ordre défini est l'ordre décroissant ou l'élément candidat ayant la valeur la plus faible si l'ordre défini est l'ordre croissant, et fournir ledit élément candidat déterminé à ladite sortie, l'élément candidat fourni à la sortie étant le résultat de l'opération de calcul cp entre un élément d'ordre i de la première liste d'entrée et un élément d'ordre j de la deuxième liste d'entrée, i et j étant compris entre 1 et nm, et - un circuit de commande pour contrôler la sélection des éléments stockés dans lesdits premiers moyens de stockage à fournir au circuit de calcul et le stockage des éléments candidats calculés dans les seconds moyens de stockage, caractérisé en ce que les seconds moyens de stockage comprennent p registres pour stocker p éléments candidats, p étant un nombre prédéterminé inférieur à nm, en ce que ledit circuit de comparaison est apte à fournir au circuit de commande une information représentative des ordres i et j associés audit élément candidat fourni à la sortie, et le circuit de commande est apte à commander lesdits premiers moyens de stockage et lesdits seconds moyens de stockage pour la mise en oeuvre du procédé de commande défini précédemment. L'invention sera mieux comprise, et d'autres buts, détails, caractéristiques et avantages apparaîtront plus clairement au cours de la description explicative détaillée qui va suivre de modes de réalisation de 10 l'invention, en référence aux figures annexées, parmi lesquelles : - la figure 1, déjà décrite, représente schématiquement un noeud de parité recevant quatre messages entrants (partie gauche de la figure) et délivrant quatre messages sortants (partie droite de la figure) ; et, - la figure 2, déjà décrite, représente schématiquement un noeud de parité élémentaire recevant deux messages entrants et délivrant un message sortant, et - la figure 3 représente la structure d'un noeud de parité élémentaire apte à mettre en oeuvre le procédé de l'invention. Dans la suite de la description, on considère que l'unité de calcul est un noeud de parité élémentaire recevant en entrée des listes de nm éléments triées dans l'ordre décroissant et délivrant en sortie une liste de nm éléments également triée dans l'ordre décroissant. On considère également que ce noeud de parité élémentaire travaille dans le domaine logarithmique, les données échangées entre noeuds étant alors des valeurs de LLR. Plus particulièrement, l'invention sera décrite ci-après en référence à un noeud de parité élémentaire recevant, en tant que messages entrants, deux listes d'entrée U1 et U2 de nm valeurs de LLR triées dans l'ordre décroissant et délivrant, en tant que message sortant, une liste de sortie Uout de nm' valeurs de LLR, avec nm' >l . Les éléments des listes U1 et U2 sont notés respectivement U1 (i) et U2 (j) , avec i =1...nm et j=1...nm. Ces listes étant triées dans l'ordre décroissant, on a : V i e [1,nm û 1] , U1(i)? U1(i+l), et 35 d j e [1, nm û 1] , U2 (j) ? U2 (j + 1) . 11 La liste de sortie Uout comprend nm' valeurs correspondant aux nm' valeurs de LLR les plus élevées de l'ensemble U~ = Uz _ {(i, j) e [1, nm] 2, U1(i) + U2(j)} triées dans l'ordre décroissant. L'ensemble UE est obtenu à 5 partir de la matrice TE de taille nm*nm ou chaque élément TE (i, j) =U1 (i) +U2 (j) avec i =1...nm et j=1...nm. Pour bien comprendre le procédé de l'invention et ses avantages, nous allons tout d'abord décrire, à 10 travers un exemple, le processus de génération de la liste de sortie Uout selon l'algorithme EMS de l'art antérieur. Chacune des listes d'entrée U1 et U2 comporte un nombre nm restreint d'éléments correspondant aux nm plus grandes valeurs de LLR contenues dans chacun des 15 messages entrants du noeud de parité élémentaire. Pour cet exemple, on considère deux listes d'entrée UE={90, 87, 60, 55, 54, 30, 29, 23, 18, 17} et U2={90, 81, 73, 60, 59, 49, 31, 30, 29, 28}. Chacune de ces listes d'entrée comporte nm=10 éléments. On cherche à 20 générer une liste de sortie Uout comportant nm'=15 éléments. La matrice TE est alors définie par le tableau suivant: U2(1) U2(2) U2(3) U2(4) U2(5) U2(6) U2(7) U2(8) U2(9) U2(10) 90 81 73 60 59 49 31 30 29 28 180 171 163 150 149 139 121 120 119 118 177 168 160 147 146 136 118 117 116 115 150 141 133 120 119 109 91 90 89 88 145 136 128 115 114 104 86 85 84 83 144 135 127 114 113 103 85 84 83 82 120 111 103 90 89 79 61 60 59 58 119 110 102 89 88 78 60 59 58 57 113 104 96 83 82 72 54 53 52 51 108 99 91 78 77 67 49 48 47 46 107 98 90 77 76 66 48 47 46 45 Tableau 1 Pour générer la liste de sortie Uout, on commande le noeud de parité élémentaire de la façon suivante. On sélectionne tout d'abord les nm éléments de la liste U1 et le premier élément de liste U2 et on effectue les nm additions correspondant à la première colonne du tableau. On obtient ainsi une liste de nm éléments candidats pour le premier élément de la liste Uout. On extrait de la liste des candidats l'élément ayant la valeur la plus élevée en comparant les éléments candidats entre eux (nm comparaisons). Cet élément, qui est T(1,1), constitue le premier élément de la liste de sortie Uout On remplace ensuite, dans liste des candidats, l'élément candidat extrait T2(1,1) par l'élément T2(1,2) qui est l'élément de la ligne i=1 ayant la valeur la plus élevée parmi les éléments non encore extraits de cette ligne, l'élément T2(1,2) ayant été préalablement obtenu en sélectionnant les éléments U2(1) et U2(2) et en les additionnant. On extrait ensuite de cette nouvelle liste de candidats l'élément ayant la valeur la plus élevée. L'élément extrait constitue le deuxième élément de la liste Uout. On opère ainsi jusqu'à obtenir une liste de sortie comportant nm' valeurs. A Ul(1) 90 U1(2) 87 U1(3) 60 U1(4) 55 ul(5) 54 U1(6) 30 U1(7) 29 U1(8) 23 U1(9) 18 Ul(10) 17 13 chaque itération, on remplace l'élément extrait TE(i,j) par l'élément TE(i,j+l) qui est l'élément de la ligne i ayant la valeur la plus élevée parmi les éléments non encore extraits de cette ligne. Au final, on obtient la liste de sortie Uout={180, 177, 171, 168, 163, 160, 150, 150, 149, 147, 146, 145, 144, 141, 1361. Selon cet algorithme EMS, le noeud de parité élémentaire effectue, pour la première itération (génération du premier élément de la liste Uout), nm additions et nm comparaisons et, pour chacune des itérations suivantes (génération des nm' - 1 derniers éléments de la liste Uout) , 1 addition et nm comparaisons. La génération de la liste Uout complète (nm' éléments) requiert donc l'exécution de nm+nm' -1 additions et nm*nm' comparaisons. Le procédé de l'invention vise à réduire ce nombre d'opérations. Le procédé de l'invention va maintenant être explicité. Etant donné que les listes U1 et U2 sont triées dans l'ordre décroissant, on a les propriétés suivantes: Vj e [1,nm] et i > i', alors TT(i, j) > TT(i', j) (1) Vi e [1, nm] et j > j' , alors TT(i, j) > TT(i, j' ) (2) La conséquence de ces deux propriétés est que la valeur la plus élevée de la matrice TE est TE(1,1). La valeur la plus élevée suivante de la matrice est soit T(2,1), soit T(1,2). Seuls deux candidats sont donc possibles pour le deuxième élément de la liste Uout. De manière plus générale, le nombre de candidats possibles pour le nième élément de la liste de sortie Uout peut être déterminé par la fonction NJ(n) = -1+7+8n 2 (3) 14 où ry1 est la fonction définissant le plus petit nombre entier naturel supérieur ou égal au nombre réel y. Cette fonction est déduite des tableaux suivants représentant la matrice TE. Dans ces tableaux, une croix x représente un élément candidat préalablement sélectionné dans la liste Uout et un rond 0 représente un élément candidat possible pour être le prochain élément de la liste Uout. Si on prend nm=5, la matrice TE représentée comprend 5 colonnes et 5 lignes. Comme indiqué précédemment, le premier élément de la liste de sortie Uout est nécessairement l'élément T(1,1). Une croix est donc représentée dans la case correspondante du tableau. Pour la détermination du deuxième élément de la liste Uout (n=2), il y a deux candidats possibles qui sont TE(2,1) et TE(1,2) comme illustré par le tableau suivant: U1(1) U1(2) U1(3) U1(4) U1(5) Tableau 2 Pour la détermination du troisième élément (n=3) de la liste Uout, on a les tableaux suivants: le tableau 3 représente le cas où l'élément TE(1,2) est le deuxième élément de la liste Uout et le tableau 4 représente l'autre cas (cas où l'élément TE(2,1) est le deuxième élément de la liste Uout). Dans les deux cas, il y a deux candidats possibles 0 pour extraire le troisième élément. X 0 0 U2(1) U2(2) U2(3) U2(4) U2(5) Tableau 3 Tableau 4 X X 0 0 X X 0 0 Pour la détermination du quatrième élément (n=4) de la liste Uout, on a les tableaux suivants: Tableau 5 Tableau 6 Tableau 7 X X X 0 0 X X X 0 0 0 X X X 0 0 Le tableau 6 illustre le cas le plus défavorable (cas où le nombre de candidats possibles est le plus élevé) avec 3 candidats possibles. Sinon, les cas les plus défavorables où le nombre de candidats possibles est supérieur à 3 sont obtenus pour la détermination du septième élément (n=7) et du onzième élément (n=11) de la liste Uout. Ces cas sont illustrés par les tableaux suivants: X X X 0 X X 0 X 0 0 Tableau 8 X X X X 0 X X X 0 X X 0 X 0 0 Tableau 9 De ces tableaux, on peut déduire que, dans le cas le plus défavorable (nombre maximum de candidats possibles), il y a m+1 candidats possibles pour la détermination du n m(m + 1) n + 1 . élément de la liste avec ème t 2 On peut alors en déduire la fonction y(n) = -1+7+8n 2 qui donne le nombre maximum de candidats possibles pour la détermination du nième élément de la liste Uout La fonction yf étant croissante, la valeur y(n) est maximale pour la dernière itération (n=nm') du processus de génération de la liste Uout. Aussi, quel que 10 soit l'élément de la liste Uout à déterminer, il y a au maximum yJ(nm') _ -1+.Jù7+8nm' 2 candidats possibles. Selon l'invention, on propose d'utiliser ce résultat pour réduire le nombre d'opérations (additions 15 et comparaisons) effectuées par le noeud de parité élémentaire. Plus précisément, étant donné que le nombre de candidats possibles pour générer la liste Uout est au maximum de p=yJ(nm'), on propose selon l'invention de ne sélectionner qu'un nombre réduit, p, de candidats 20 possibles à chaque itération du processus de génération de la liste de sortie Uout, ces éléments candidats possibles étant alors sélectionnés de manière appropriée. On va illustrer comme précédemment le procédé 25 de l'invention à l'aide de tableaux représentant la matrice TE. Dans ces tableaux, on considère que nm=5 et nm'=10. Comme précédemment, une croix x représente un élément candidat préalablement sélectionné dans la liste Uout et un rond 0 représente un candidat possible pour 30 l'itération en cours. On a W(nm')=4, soit une liste de 4 candidats possibles à chaque itération. A la première itération (n=1), les 4 candidats possibles sont les 4 premiers éléments de la première colonne de la matrice 17 TE, i.e. TE(1,1), TE(2,1), TE(3,1) et TE(4,1), comme illustré par le tableau suivant: U1(1) U1(2) U1(3) U1(4) U1(5) Tableau 10 L'élément sélectionné pour cette première itération (n=1) est T(1,1). Cet élément est extrait de la liste des candidats possibles et est remplacé par TE(1,2). D'une manière plus générale, à chaque fois qu'un élément TE(i,j) est extrait de la liste des candidats, il est connu de le remplacer par l'élément TE(i,j+l). Pour l'itération suivante (n=2), la liste des candidats est illustrée par le tableau suivant. U1(1) U1(2) U1(3) U1(4) U1(5) Tableau 11 Le fait d'avoir un nombre restreint de candidats possibles peut poser problème dans certaines situations, par exemple lorsque l'élément TE(yl(nm'),1) est sélectionné puis extrait comme illustré par le tableau suivant: 0 0 0 0 X 0 0 0 0 U2(1) U2(2) U2(3) U2(4) U2(5) U2(1) U2(2) U2(3) U2(4) U2(5)20 U1(1) U1(2) U1(3) U1(4) U1(5) X 0 X 0 X 0 X 0 Tableau 12 Si on applique la loi de remplacement décrite ci-avant, l'élément T(4,1) extrait à la quatrième itération (n=4) est remplacé par l'élément TE(4,2). Or, TE(4,2) n'est pas un "vrai" candidat puisqu'il est nécessairement inférieur à TE(3,2) qui est déjà dans la liste des candidats. A contrario, TE(5,1) qui est un vrai candidat pour l'itération suivante (n=5) n'est pas dans la liste de candidats. Aussi, pour éviter ce problème, on propose de modifier la règle de remplacement au moins pour certains éléments de la liste des candidats possibles. Selon un premier mode de réalisation, on utilise un drapeau D permettant de modifier la sélection de l'élément à introduire dans la liste des candidats. Ce drapeau D présente deux états "horizontal" et "vertical". Lorsque le drapeau D est "horizontal" et que l'élément extrait de la liste des candidats est TE(i,j), alors l'élément TE (i, j) est remplacé par l'élément TE(i,j+l) dans la liste des candidats. En revanche, lorsque le drapeau D est "vertical" et que l'élément extrait de la liste des candidats est TE(i,j), alors l'élément TE(i,j) est remplacé par l'élément TE(i+l,j) dans la liste des candidats. En début de processus de génération de la liste Uout, le drapeau est initialisé à l'état "horizontal" et reste dans cet état tant que l'ordre i de l'élément extrait TE(i,j) est inférieur à U2(1) U2(2) U2(3) U2(4) U2(5) 19 yJ(nm') . Lorsque l'ordre i de l'élément extrait TE(i,j) est supérieur ou égal à p=yJ(nm'), le drapeau D change d'état et passe à l'état "vertical". Il reste dans l'état "vertical" tant que l'ordre j de l'élément extrait TE(i,j) est inférieur à p. Enfin, lorsque l'ordre j de l'élément extrait TE(i,j) est supérieur ou égal à p, le drapeau D repasse à l'état "horizontal". Le drapeau D dépend donc du dernier indice i ou j à devenir supérieur à p. S i on reprend l'exemple de la matrice TE définie dans le tableau 1, on commande le noeud de parité élémentaire de la façon suivante avec nm=10, nm'=15 et p=5. Au départ, on sélectionne les p=5 premiers éléments de la liste U1 et le premier élément de la liste U2 et on les additionne ensemble de manière à obtenir les 5 éléments suivants: T2(1,1), T2(2,1), T2(3,1), T2(4,1) et T2(5,1). Ces 5 éléments forment alors la liste de candidats possibles pour le premier élément de la liste de sortie Uout. On extrait l'élément candidat ayant la valeur la plus élevée, T(1, 1)=180, pour former le premier élément de la liste de sortie Uout et, comme le drapeau D est à l'état "horizontal" et que i=1 20 Les itérations n=3 jusqu'à n=12 sont identiques aux itérations n=1 et n=2. Les itérations n=1 à n=12 sont illustrées par les 12 tableaux suivants, chaque tableau étant associé à une itération. La deuxième colonne de chacun des tableaux représente la liste des éléments candidats TE(i,j) pour l'itération considérée et la première colonne représente les coordonnées i et j desdits éléments candidats. L'élément extrait de la liste des éléments candidats lors de cette itération apparait en caractères gras dans le tableau. n=1 i,j TE(i,j) 1, 1 180 2,1 177 3, 1 150 4, 1 145 5, 1 144 n=6 i,j TE(i,j) 1, 4 150 2, 3 160 3, 1 150 4, 1 145 5, 1 144 n=2 i,j TE(i,j) 1, 2 171 2, 1 177 3, 1 150 4, 1 145 5, 1 144 n=7 i,j TE(i,j) 1, 4 150 2,4 147 3, 1 150 4, 1 145 5, 1 144 n=3 i,j TE(i,j) 1, 2 171 2,2 168 3, 1 150 4, 1 145 5, 1 144 n=8 i,j TE(i,j) 1,5 149 2,4 147 3, 1 150 4, 1 145 5, 1 144 n=4 i,j TE(i,j) 1, 3 163 2, 2 168 3, 1 150 4, 1 145 5, 1 144 n=9 i,j TE(i,j) 1, 5 149 2,4 147 3, 2 141 4, 1 145 5, 1 144 n=5 i,j TE(i,j) 1, 3 163 2, 3 160 3, 1 150 4, 1 145 5, 1 144 n=10 i,j TE(i,j) 1, 6 139 2, 4 147 3, 2 141 4, 1 145 5, 1 144 n=11 i,j TE(i,j) 1, 6 139 2, 5 146 3, 2 141 4, 1 145 5, 1 144 n=12 i,j TE(i,j) 1, 6 139 2, 6 136 3, 2 141 4, 1 145 5, 1 144 Pour l'itération n=13, la liste des éléments candidats comporte les éléments: T(1,6), T(2,6), TE(3,2), TE(4,2) et TE(5,1). On extrait l'élément candidat ayant la valeur la plus élevée, TE(5,1)=144, pour constituer le treizième élément de la liste de sortie Uout. Comme le drapeau D est à l'état "horizontal" et que i=5 ? yl(nm' ), le drapeau D passe à l'état "vertical" et on remplace T(5,1) par TE (6, 1) dans la liste des candidats possibles. Pour l'itération n=14, la liste des éléments candidats comporte les éléments: TE (1, 6) , T(2,6), TE(3,2), TE(4,2) et TE(6,1). On extrait l'élément candidat ayant la valeur la plus élevée, TE(3,2)=141, pour constituer le quatorzième élément de la liste de sortie Uout. Comme le drapeau D est à l'état "vertical" et que i=3 22 A noter que la liste des candidats possibles obtenue à l'issue de l'étape n=14 comporte deux fois l'élément candidat TE(4,2), ce qui revient à réduire la taille de cette liste. Pour éviter une telle situation, on vérifie avantageusement si l'élément candidat à introduire dans la liste de candidats possibles n'appartient pas déjà à cette liste. Si tel est le cas, l'élément introduit dans la liste est alors celui correspondant au cas où l'état du drapeau D serait l'autre état. L'état du drapeau D reste toutefois inchangé pour les itérations suivantes. Dans le cas présent (itération n=14), on remplace donc TE(3,2) par TE(4,2) dans la liste des candidats possibles et le drapeau D reste à l'état "vertical". On obtient la liste suivante pour l'itération n=15 et on extrait soit l'élément T(4,2)=136 ou T(2,6)=136 pour former le dernier élément de la liste de sortie Uout. n=15 i,j TE(i,j) 1, 6 139 2, 6 136 3, 3 133 4, 2 136 6, 1 120 On obtient au final la liste de sortie suivante Uout={180, 177, 171, 168, 163, 160, 150, 150, 149, 147, 146, 145, 144, 141, 136} identique à celle obtenue avec le procédé de l'art antérieur mais avec un nombre réduit d'opérations. Selon l'invention, le nce ud de parité élémentaire effectue yf(nm') additions et yf(nm' ) comparaisons pour la première itération (génération du premier élément de la liste Uout) et effectue, pour chacune des itérations suivantes (génération des nm' - 1 23 derniers éléments de la liste Uout) , 1 addition et yJ(nm' ) comparaisons. La génération de la liste Uout complète (nm' éléments) requiert donc l'exécution de yJ(nm')+nm'-1 additions et yJ(nm')*nm' comparaisons. En variante, on peut sélectionner p Dans le mode de réalisation décrit précédemment, la sélection de l'élément candidat qui doit remplacer l'élément candidat T2(i,j) extrait de la liste des candidats est effectuée en fonction du drapeau D et des ordres i et j. En variante, on propose d'effectuer cette sélection uniquement en fonction des ordres i et j. Selon ce mode de réalisation en variante, on définit une règle de remplacement basée uniquement sur les ordres i et j de l'élément candidat extrait. Par exemple, si on considère une première liste de candidats possibles T2(1,1), T2(2,1), T2(3,1) et T2(4,1), la règle de remplacement est par exemple définie de la manière suivante: - Vj e [1, nm], si i 35 Par ailleurs, chaque élément des listes U1 et U2 représentant une valeur de LLR associée à un symbole 24 dans le corps de Galois GF(q), chaque élément de la liste des éléments candidats est aussi associé à un symbole dans le corps de Galois GF(q) . Or, il arrive que l'élément candidat ayant la valeur la plus élevée soit associé à un symbole qui est également associé à un élément candidat déjà contenu dans la liste de sortie Uout. Un même symbole de GF(q) peut en effet être associé à deux éléments candidats T2(i+l,j) différents. Aussi, avantageusement, le noeud de parité élémentaire effectue, après détermination de l'élément candidat ayant la valeur la plus élevée, une étape de détermination du symbole associé audit élément candidat déterminé. L'élément candidat déterminé est alors introduit dans la liste de sortie Uout si et seulement si le symbole qui lui est associé n'est pas associé à un élément candidat déjà présent dans la liste de sortie. La structure d'un noeud de parité élémentaire apte à mettre en oeuvre le procédé de l'invention est représentée à la figure 3. Ledit noeud comprend deux entrées E1 et E2 pour recevoir respectivement les listes d'entrée U1 et U2 à traiter, chacune de ces listes comportant nm éléments triés dans l'ordre décroissant, et une sortie S pour délivrer la liste de sortie Uout générée par le noeud de parité élémentaire, la liste de sortie comprenant nm' éléments triés dans l'ordre décroissant. Le noeud de parité élémentaire comprend également - des moyens de stockage, tels que des mémoires M1 et M2, pour sauvegarder les listes d'entrée U1 et U2 reçues aux entrées El et E2, - un circuit de calcul C pour additionner des éléments de la liste d'entrée U1 avec des éléments de la liste d'entrée U2 pour générer les éléments candidats, - p=yJ(nm') registres Rk, k e [1,p] pour stocker les éléments candidats calculés par le circuit de calcul, 25 un circuit de comparaison COMP pour déterminer, parmi les éléments candidats stockés dans les registres Rk, l'élément candidat ayant la valeur la plus élevée, et délivrer une information IR identifiant le registre Rk duquel provient l'élément candidat ayant la valeur la plus élevée, - un bloc NR, dit de suppression de redondance, pour supprimer les éléments candidats délivrés par le circuit de comparaison qui sont associés à un symbole de GF(q) déjà associé à un élément fourni à la sortie S du noeud, et - un circuit de commande CTRL pour recevoir l'information IR et contrôler l'ensemble des circuits du noeud, notamment les mémoires M1 et M2, les registres Ri et le bloc de suppression de redondance NR conformément au procédé de commande de l'invention. Dans l'exemple de la figure 3, le noeud comporte p=5 registres. En début de procédé, le circuit de commande CTRL commande la mémoire M1 pour qu'elle délivre les p premiers éléments de la liste U1 et la mémoire M2 pour qu'elle délivre le premier élément de la liste U2. Ces éléments sont additionnés par le circuit de calcul C et les p résultats sont stockés dans les p registres Rk. Ces p résultats constituent la liste de candidats possibles pour le premier élément de la liste Uouk. Ces p résultats sont ensuite chargés dans le circuit de comparaison COMP chargé de délivrer l'élément candidat, noté MAX, ayant la valeur la plus élevée sur la sortie S. A noter que plusieurs structures de circuit de comparaison sont possibles pour délivrer l'élément candidat MAX. Selon une première structure, le circuit de comparaison comporte p-1 circuits élémentaires de comparaison montés en arbre, chaque circuit élémentaire comparant deux valeurs d'entrée entre elles. Selon une deuxième structure, le circuit de comparaison comprend un 26 nombre différent de circuits élémentaires de comparaison arrangés entre eux pour former une structure de tri par insertion bien connue en soi. Le circuit de comparaison COMP est également prévu pour fournir au circuit de commande l'information IR identifiant le registre Rk duquel provient l'élément candidat MAX. L'information IR est générée à partir des signaux de commande des circuits élémentaires de comparaison. A partir de l'information IR et d'un registre interne sauvegardant les coordonnées (i,j) des éléments candidats TE (i, j) =U1 (i) +U2 (j) stockés dans les registres Rk, le circuit de commande détermine les coordonnées (i,j) de l'élément candidat MAX délivré par le circuit de comparaison COMP. Il détermine ensuite, en fonction de l'état d'un drapeau D sauvegardé dans un registre interne et desdites coordonnées (i,j), les coordonnées (i',j') du prochain élément candidat à charger dans le circuit de comparaison. En fonction du drapeau D, (i',j')=(i+l,j) ou (i' , j ') _ (i, j+1) . Le circuit de commande CTRL commande ensuite les mémoires M1 et M2 pour qu'elle délivre les éléments U1 (i') et U2 (j') et commande le registre Ri identifié dans l'information IR pour sauvegarder l'élément candidat TE (i' , j ') =U1 (i') +U2 (j ') . Ainsi, seul le registre Ri identifié dans l'information IR est rechargé avec un nouvel élément candidat. L'information IR est également employée pour supprimer les éléments candidats délivrés par le circuit de comparaison COMP qui sont associés à un symbole de GF(q) déjà associé à un élément fourni à la sortie S du noeud. Les coordonnées (i,j) déterminées à partir de l'information IR sont utilisées par le circuit de commande CTRL pour déterminer le symbole associé à l'élément candidat TE(i,j) présent à la sortie du circuit de comparaison. Cette information de symbole, notée IS, est par exemple enregistrée dans un registre spécifique, 15 20 27 dit de symboles, du circuit de commande CTRL. Avant chaque enregistrement, l'information de symbole IS est toutefois comparée à celles déjà enregistrées dans le registre. Si l'information de symbole est déjà présente dans le registre, cela signifie que la liste de sortie U0 comporte déjà un élément associé au symbole contenu dans l'information IS. Dans ce cas, le circuit CTRL commande le bloc NR pour qu'il ne fournisse pas l'élément candidat TE(i,j) à la sortie S. Si l'information de symbole IS n'est pas déjà présente dans le registre de symboles, elle y est enregistrée et le bloc NR fournit l'élément candidat TE(i,j) à la sortie S. Comme on peut le voir sur la figure 3, ce noeud de parité élémentaire comporte un nombre réduit (p= W(nm')) de registres. Il permet donc d'utiliser un nombre réduit de circuits élémentaires de comparaisons dans le circuit de comparaison COMP. Il permet également d'obtenir des temps de latence plus faibles que les noeuds de parité élémentaires classiques. Pour accélérer le débit du noeud de parité élémentaire, il est également possible de générer la liste de sortie U0 en traitant les listes d'entrée par blocs de plusieurs éléments. Les moyens du noeud de parité élémentaire sont alors dupliqués pour permettre un 25 traitement parallèle des éléments des blocs. Bien que l'invention ait été décrite en liaison avec différents modes de réalisation particuliers, il est bien évident qu'elle n'y est nullement limitée et qu'elle 30 comprend tous les équivalents techniques des moyens décrits ainsi que leurs combinaisons si celles-ci entrent dans le cadre de l'invention. L'invention a notamment été décrite dans le cadre de listes d'entrée et de sortie comprenant des 35 éléments appartenant à un corps de Galois GF(q) mais, d'une manière plus générale, elle est applicable à toute 28 liste comprenant des éléments appartenant à un ensemble muni d'au moins une loi de composition interne. Par ailleurs, l'invention a été décrite dans le cadre d'une liste de sortie comprenant des éléments qui sont les résultats d'opérations d'addition entre éléments des listes d'entrée. D'une manière plus générale, l'invention est applicable à des opérations de calcul cp où cp est une fonction telle que, si a?b et c?d, alors cp(a, c) cp(b, d) . D'autre part, dans les modes de réalisation décrits précédemment, la liste de candidats possibles pour chaque élément de la liste de sortie U0 comprend p=yl(nm') éléments candidats mais, bien entendu, p peut être choisi différemment à condition toutefois d'être inférieur à nm pour réduire le nombre de comparaisons. Il peut être inférieur à yl(nm') (solution sous-optimale) ou supérieur à nm (solution sur-optimale). Enfin, l'invention a été décrite dans le cadre d'une unité de calcul destinée à générer, à partir de deux listes d'entrée triées dans l'ordre décroissant, une liste de sortie triée dans l'ordre décroissant comportant les plus grandes valeurs des deux listes d'entrée. L'invention est aussi applicable à une unité de calcul destinée à générer, à partir de deux listes d'entrée triées dans l'ordre croissant, une liste de sortie triée dans l'ordre croissant comportant les plus petites valeurs des deux listes d'entrée en sélectionnant à chaque itération du procédé la plus petite valeur de la liste des candidats. Cette unité de calcul peut par exemple être utilisée dans un récepteur apte à recevoir des signaux modulés selon une modulation MAQ (Modulation d'amplitude en quadrature). L'unité de calcul est alors utilisée pour déterminer, parmi les symboles de la constellation, les symboles les plus proches du symbole reçu. Si la constellation est représentée selon un diagramme en (x,y), la première liste d'entrée représente 29 par exemple les écarts en x au carré, triés par ordre croissant, entre le symbole reçu et les symboles de la constellation et la deuxième liste d'entrée représente les écarts en y au carré, triés par ordre croissant, entre le symbole reçu et les symboles de la constellation. La fonction p est alors p(x,y) = x+y pour obtenir en sortie la liste des nm symboles ou points de la constellation les plus proches du symbole reçu, ladite liste étant triée par distance quadratique croissante.10 REVENDICATIONS1. Procédé de commande d'une unité de calcul, telle qu'un noeud de parité élémentaire d'un décodeur de codes LDPC binaires ou non binaires, ledit noeud de parité élémentaire recevant des première et seconde listes (U1r U2) , dites première et seconde listes d'entrée, de nm éléments triés dans un ordre défini parmi un ordre décroissant et un ordre croissant, nm étant supérieur à 1, et délivrant une liste (Uout) , dite liste de sortie, de nm' éléments triés dans ledit ordre défini, nm' étant supérieur à 1, chaque élément de la liste de sortie (Uout) étant le résultat d'une opération de calcul cp entre un élément de la première liste d'entrée (U1) et un élément de la deuxième liste d'entrée (U2), ladite opération de calcul c) étant telle que si a?b et c?d alors cp(a, c) (p(b, d), ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes : a) sélectionner les p premiers éléments de la première liste d'entrée (U1) et le premier élément de la deuxième liste d'entrée (U2), p étant un nombre prédéterminé inférieur à nm, b) effectuer des opérations de calcul cp entre les éléments sélectionnés de la première liste d'entrée (U1) et l'élément sélectionné de la seconde liste d'entrée (U2) de manière à générer une liste de p éléments candidats pour la liste de sortie, c) déterminer, parmi les p éléments candidats, l'élément candidat ayant la valeur la plus élevée si l'ordre défini est l'ordre décroissant ou l'élément candidat ayant la valeur la plus faible si l'ordre défini est l'ordre croissant, et l'introduire dans la liste de sortie (Uout), l'élément candidat introduit dans la liste de sortie étant le résultat de l'opération de calcul cp entre un élément d'ordre i de la première liste d'entrée 31 et un élément d'ordre j de la deuxième liste d'entrée, i et j étant compris entre 1 et nm, d) sélectionner, selon un critère prédéterminé, l'élément d'ordre i de la première liste d'entrée et l'élément d'ordre j+1 de la deuxième liste d'entrée ou l'élément d'ordre i+1 de la première liste d'entrée et l'élément d'ordre j de la deuxième liste d'entrée, e) effectuer une opération de calcul cp entre les éléments sélectionnés de manière à générer un nouvel élément candidat, et remplacer, dans la liste des p éléments candidats, le dernier élément candidat introduit dans la liste de sortie par ledit nouvel élément candidat, f) déterminer, parmi les p éléments candidats, l'élément candidat ayant la valeur la plus élevée si l'ordre défini est l'ordre décroissant ou l'élément candidat ayant la valeur la plus faible si l'ordre défini est l'ordre croissant, et l'introduire dans la liste de sortie (Uout) dans l'ordre de détermination, l'élément candidat introduit dans la liste de sortie étant le résultat de l'opération de calcul entre un élément d'ordre i de la première liste d'entrée et un élément d'ordre j de la deuxième liste d'entrée, et g) réitérer les étapes d) à f) jusqu'à ce que 25 la liste de sortie comporte nm' éléments. 2. Procédé selon la revendication 1, caractérisé en ce que le nombre p est égal à ù 1 + 7 + 8nm' 2 où rxj représente le plus petit nombre 30 entier supérieur ou égal au nombre réel x. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que, selon un premier critère prédéterminé, la sélection effectuée à l'étape d) dépend 35 de l'ordre i de l'élément de la première liste d'entrée 32 (U1) et/ou de l'ordre j de l'élément de la deuxième liste d'entrée (U2) associé à l'élément candidat introduit dans la liste de sortie. 4. Procédé selon la revendication 1 ou 2, caractérisé en ce que, selon un deuxième critère prédéterminé, la sélection effectuée à l'étape d) dépend de l'ordre i de l'élément de la première liste d'entrée (U1) et de l'ordre j de l'élément de la deuxième liste d'entrée (U2) associé à l'élément candidat introduit dans la liste de sortie et d'un drapeau représentatif de la sélection effectuée à l'étape d) précédente. 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que les éléments des listes d'entrée et de la liste de sortie sont des logarithmes de rapport de vraisemblance. 6. Procédé selon la revendication 5, 20 caractérisé en ce que l'opération de calcul est une addition. 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, chacun 25 des éléments desdites première et seconde listes d'entrée (U1rU2) étant associé à un symbole dans un corps de Galois, l'étape f) comprend en outre, après détermination de l'élément candidat ayant la valeur la plus faible ou la plus élevée, une étape de détermination du symbole 30 associé audit élément candidat déterminé, ledit élément candidat déterminé étant introduit dans la liste de sortie si et seulement si le symbole associé audit élément candidat déterminé n'est pas associé à un élément candidat présent dans la liste de sortie. 35 33 8. Unité de calcul, comprenant: - des première et seconde entrées pour recevoir des première et seconde listes (U1rU2), dites première et seconde listes d'entrée, de nm éléments triés dans un ordre défini parmi un ordre décroissant et un ordre croissant, nm étant supérieur à 1, - une sortie pour délivrer une liste (Uout), dite liste de sortie, de nm' éléments triés dans l'ordre défini, nm' étant supérieur ou égal à 1, chaque élément de la liste de sortie étant le résultat d'une opération de calcul cp entre un élément de la première liste d'entrée et un élément de la deuxième liste d'entrée, ladite opération de calcul cp étant telle que si a?b et c?d alors cp(a, c) cp(b, d), - des premiers moyens de stockage pour stocker les éléments desdites première et secondes listes d'entrée (U1r U2) , - un circuit de calcul pour effectuer des opérations de calcul cp entre des éléments de la première liste d'entrée et des éléments de la seconde liste d'entrée stockés dans lesdits premiers moyens de stockage de manière à générer, à chaque opération, un élément candidat, - des seconds moyens de stockage pour stocker 25 les éléments candidats calculés par ledit circuit de calcul, - un circuit de comparaison pour déterminer, parmi les éléments candidats stockés dans les seconds moyens de stockage, l'élément candidat ayant la valeur la 30 plus élevée si l'ordre défini est l'ordre décroissant ou l'élément candidat ayant la valeur la plus faible si l'ordre défini est l'ordre croissant, et fournir ledit élément candidat déterminé à ladite sortie, ledit élément candidat fourni à la sortie étant le résultat de 35 l'opération de calcul cp entre un élément d'ordre i de la première liste d'entrée et un élément d'ordre j de la 34 deuxième liste d'entrée, i et j étant compris entre 1 et nm, et - un circuit de commande pour contrôler la sélection des éléments stockés dans lesdits premiers moyens de stockage fournis au circuit de calcul et le stockage des éléments candidats calculés dans les seconds moyens de stockage, caractérisé en ce que les seconds moyens de stockage comprennent p registres pour stocker p éléments candidats, p étant un nombre prédéterminé inférieur à nm, en ce que ledit circuit de comparaison est apte à fournir au circuit de commande une information représentative des ordres i et j associés audit élément candidat fourni à la sortie, et en ce que le circuit de commande est apte à commander lesdits premiers moyens de stockage et lesdits seconds moyens de stockage pour la mise en oeuvre du procédé de commande selon l'une quelconque des revendications 1 à 7.20