Brevet FR2796780A1 — publié le 20010126

Procédé et dispositif de codage à au moins deux codages en parallèle et permutation améliorée, et procédé et dispositif de décodage correspondants. Le domaine de l'invention est celui du codage de données numériques appartenant à une, ou plusieurs, séquences de données sources destinées à être transmises, ou diffusées, notamment en présence de bruits de transition, et du décodage des données codées ainsi transmises. Plus précisément, l'invention concerne une amélioration du procédé de codage notamment connu sous le nom de " turbo-codes " (marque déposée), et plus particulièrement de l'opération de permutation qu'il met en oeuvre. Le principe général de ce type de codage est notamment présenté dans le brevet français n FR-91 05280, ayant pour titre " Procédé de codage correcteur d'erreurs à au moins deux codages convolutifs systématiques parallèles, procédé de décodage itératif, module de décodage et décodeur correspondants ", et dans l'article de C. Berrou et A. Glavieux " Near Optimum Error Correcting Coding and Decoding: Turbo Codes " (IEEE Transactions on Communications, Volume 44, n 10, pages 1261-1271, Octobre 1996). Selon cette technique, on propose la mise en oeuvre d'un codage à " concaténation parallèle ", s'appuyant sur l'utilisation d'au moins deux codeurs élémentaires. Cela permet de disposer, lors du décodage, de deux symboles de redondance issus de deux codeurs distincts. Entre les deux codeurs élémentaires, on met en oeuvre des moyens de permutation, de façon que chacun de ces codeurs élémentaires soit alimenté par les mêmes données numériques source, mais prises dans des ordres différents. Une amélioration à ce type de technique, destinée au codage en blocs (codes produits), est décrite dans le brevet FR-93 13858, et ayant pour titre " Turbo décodage des codes produits ", ainsi que dans l'article de O. Aitsab et R. Pyndiah " Performance of Reed Solomon block turbo code " (IEEE Globecom'96 Conference, Vol. 1/3, pages 121-125, Londres, Novembre 1996). Les performances des " turbo codes " convolutifs à concaténation parallèle dépendent, pour une part relativement importante, de la fonction de permutation 2 2796780 mise en oeuvre. On constate en effet qu'un choix non optimisé de cette fonction peut conduire à une dégradation du " turbo code ", avec notamment l'apparition d'un changement de pente de la courbe de taux d'erreurs en deçà de 10-5 et 10-6. Ce phénomène est d'autant plus accentué que le rendement du " turbo codes " considéré est élevé, et que les blocs d'information à coder sont courts. Dans les différents documents cités, des fonctions de permutation permettant de construire des " turbo codes " présentant de bonnes performances ont été proposées. Dans le brevet FR-91 05280, les codes convolutifs élémentaires sont binaires, et les permutations ont donc lieu directement sur les éléments binaires. Plus généralement, de nombreuses solutions pour réaliser la fonction de permutation dans un " turbo code " à concaténation parallèle mettant en oeuvre des codes convolutifs binaires ont été proposées dans le cadre de la troisième génération de téléphones mobiles (UMTS). Dans le brevet FR-93 13858, ainsi que dans l'article de C. Berrou et M. Jezequel " Non-binary convolutional codes for turbo coding ", (Electronics Letters, Vol. 35, n 1, pages 39-40, Janvier 1999), il est également proposé une utilisation de codes convolutifs non binaires pour construire des " turbo codes ". Dans ce cas, la fonction de permutation porte donc sur les mots binaires (ensembles de bits, par exemple couples, ou plus généralement n-couples). D'une façon générale la fonction de permutation doit bien sûr permettre d'assurer une bonne dispersion des éléments issus de la source d'information et alimentant les différents codeurs parallèles, afin de créer un effet de désordre important. Il faut donc optimiser les propriétés de distance du codeur composite, et notamment maximiser sa distance minimale. Ainsi, l'invention a notamment pour objectif de fournir un procédé de codage à concaténation parallèle (" turbo codes ") construits à partir de codes convolutifs non binaires et présentant des qualités de permutation meilleures que celles des " turbo codes " connus. 3 2796780 Plus précisément, un objectif de l'invention est de fournir un procédé de codage à concaténation parallèle optimisant les propriétés de distance du codeur composite (le " turbo code "), c'est-à-dire notamment de maximiser sa distance minimale. Un autre objectif de l'invention est de fournir un tel procédé de codage, créant un effet de désordre important sur les données alimentant les différents codeurs élémentaires, bien sûr sans altérer l'effet de dispersion. L'invention a également pour objectif de fournir un tel procédé de codage, qui puisse aisément être mis en oeuvre en pratique, de façon peu coûteuse, par exemple sous la forme d'un circuit intégré. Encore un autre objectif de l'invention est de fournir un tel procédé de codage, qui puisse aisément être mis en oeuvre pour de très nombreux types d'applications. Ces objectifs, ainsi que d'autres qui apparaîtront plus clairement par la suite, sont atteints selon l'invention à l'aide d'un procédé de codage de données numériques source, mettant en oeuvre en parallèle au moins deux étapes de codage élémentaire prenant chacune en compte l'ensemble desdites données source, et comprenant une étape de permutation modifiant l'ordre de prise en compte desdites données source entre lesdites étapes de codage élémentaire, dans lequel lesdites données source sont organisées en mots de code source comprenant chacun n éléments binaires source, n supérieur ou égal à 2. Selon l'invention, ladite étape de permutation comprend: * une étape de modification réversible du contenu d'au moins certains desdits mots de code source, délivrant des mots de code modifiés; * une étape de permutation de l'ordre desdits mots de code source ou modifiés. En d'autres termes, l'invention propose d'agir à un double niveau, lors de l'étape de permutation (on conserve ici le terme visuel de "permutation", mais les termes de "brassage", ou de "traitement" pourraient être avantageusement utilisés, car, comme on le verra par la suite, il est possible de modifier la valeur de certains 4 2796780 éléments binaires). On agit en effet d'une part sur l'ordre des mots de code (ou n- uples), et d'autre part sur le contenu de ces derniers (modification intra-mots). On notera que la permutation des mots peut aussi bien être effectuée avant ou après le traitement des mots de code eux-mêmes. Selon un mode avantageux de réalisation, ladite étape de permutation de l'ordre des mots de code met en oeuvre une permutation uniforme appliquée sur un bloc de N mots de code consécutifs. Cette technique est très simple à mettre en oeuvre, et permet d'atteindre une efficacité quasi optimale. Elle peut avantageusement être mise en oeuvre à l'aide d' une mémoire contenant N mots de code introduits dans l'ordre 0 à N-1 et relue dans l'ordre j = P.i, i variant de 0 à N- 1, Pet N étant premiers entre eux. Préférentiellement, dans ce cas, P est voisin de VN. Selon une approche préférentielle de l'invention, que ladite modification du contenu n'est appliquée que sur certains desdits mots de code. Par exemple, ladite modification du contenu est appliquée à un mot de code sur deux. Avantageusement, ladite modification du contenu comprend une permutation de l'ordre des éléments binaires à l'intérieur du mot de code considéré. Selon un autre aspect avantageux, ladite modification du contenu comprend le remplacement d'au moins un des éléments binaires source du mot de code considéré par une combinaison d'au moins deux desdits éléments binaires source. Lesdits mots de code peuvent notamment être des couples. Toutefois, bien sûr, il peut plus généralement s'agir de n-uples, quel que soit la valeur de n, supérieure ou égale à 2. Dans le cas o il s'agit de couples, les combinaisons peuvent associer au couple source {a,b} au moins un des couples modifiés suivants: * (a, b) * (b,a) * (a+b,b) 2796780 * (b, a+b) * (a, a+b) * (a+b, a) Selon un mode de réalisation de l'invention, au moins une desdites étapes de codage élémentaires met en oeuvre un code convolutif, récursif et systématique de rendement naturel n/(n+m), associant à n entrées binaires n+m sorties binaires, avec n>2 et m>1. Avantageusement, le procédé associe à un mot de code de n entrées binaires n + ml + m2 sorties binaires comprenant: * les n entrées binaires; * ml sorties binaires délivrées par une première étape de codage élémentaire; * m2 sorties binaires délivrées par une seconde étape de codage élémentaire. Une étape de poinçannage peut être prévue. L'invention concerne également, bien sûr, les dispositifs de codage correspondant. Un tel dispositif met en oeuvre des moyens de permutation comprenant: * des moyens de modification réversible du contenu d'au moins certains desdits mots de code source, délivrant des mots de code modifiés; * des moyens de permutation de l'ordre desdits mots de code, source ou modifiés. L'invention concerne encore les dispositifs d'émission ou de transmission de données codées selon le procédé décrit ci-dessus. Selon un autre aspect, l'invention concerne les procédés et dispositifs de décodage correspondants. Le procédé de décodage comprend, symétriquement au codage, les étapes de: * modification du contenu d'au moins certains des mots de code reçus, ladite modification étant l'inverse de celle mise en oeuvre lors du codage; * permutation de l'ordre des mots de code reçus, de façon à remettre ces derniers dans l'ordre initial. 6 2796780 D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante d'un mode de réalisation préférentiel de l'invention, données à titre de simple exemple illustratif et non limitatif, et: - de la figure unique annexée, qui illustre le principe général d'un codeur selon l'invention. L'invention propose donc une nouvelle fonction de permutation pour codeur à concaténation parallèle de codes élémentaires, qui, associée à des codes élémentaires convolutifs, récursifs, systématiques, non binaires, de rendement naturel n/(n+m) avec n 2 2 et n > 1, conduit à des performances proches de la limite théorique, et ceci quels que soient le rendement considéré pour le " turbo code " et la longueur des blocs d'informations à coder. On rappelle que, dans le cadre de l'invention, les codes élémentaires considérés sont nécessairement non binaires, c'est-à-dire qu'ils présentent n > 2 entrées binaires et n+m, avec m > 1, sorties binaires. Un exemple de dispositif de codage selon l'invention est illustré en figure 1. Le procédé de codage correspondant s'en déduit directement. Sur cet exemple, on considère un code construit à partir de la concaténation parallèle de deux codes élémentaires C, et C2 11 et 12, qui sont identiques, convolutifs, récursifs, systématiques, non binaires, de rendement 2/3 (n = 2 entrées binaires: les mots de code sont des couples) séparés par une fonction de permutation 13. On suppose de plus que le bloc de données à coder est constitué de p données binaires, avec p pair ou, de manière équivalente, par N = p/2 couples binaires. Si le codeur composite n'est pas poinçonné, son rendement de codage est alors égal 1/2. Bien sûr, un poinçonnage 14 peut être mis en oeuvre, de façon classique. Comme déjà mentionné, selon l'invention, la fonction de permutation 13 repose sur une double opération: 7 2796780 * une permutation 131 de l'ordre des mots de code (dans l'exemple des couples, mais plus généralement tout n-uple); * un traitement 132 sur au moins certains des blocs de données. Les N couples issus de la source d'information 15 alimentent le codeur élémentaire Cl puis, après permutation 13, le codeur C2. Une fonction de permutation doit permettre d'assurer une bonne dispersion des couples (plus généralement des n-uples) issus de la source d'information 15, et créer un effet de désordre important. Un des objectifs à atteindre est en effet d'optimiser les propriétés de distance du codeur composite et notamment de maximiser sa distance minimale. Concernant le critère de dispersion, il s'agit de séparer le plus possible, après permutation 13, les couples adjacents (plus généralement les n-uples) en sortie de la source d'information 15. Cet objectif peut être atteint, de manière quasi optimale, en utilisant une permutation uniforme 131 au niveau des couples (plus généralement des n-uples). Cette permutation uniforme 131 peut être réalisée en écrivant uniformément les N couples binaires (plus généralement les n-uples) dans une mémoire 1311 à N positions (positions 0 à N-1) et en venant lire (1312) ces N couples successivement aux adresses j, avec la règle suivante: J = pi modulo N i = 0,1...(N-1) (1) Pour parcourir les N positions de la mémoire 1311 une fois et une seule, P et N doivent être deux nombres premiers entre eux (c'est-à-dire ne doivent pas avoir de diviseur commun sauf 1). De plus, pour assurer un espacement optimal entre les couples (plus généralement les n-uples) adjacents en sortie de la source , le paramètre P est préférentiellement voisin de vN. Pour illustrer cet aspect, on considère, par exemple, un bloc de N = 9 couples binaires à coder. P est fixé à 4 (4 est voisin de V/9 = 3). On obtient alors: 8 2796780 i O 1 2 3 4 5 6 7 8 j 0 4 8 3 7 2 6 1 5 Ainsi, les N couples à coder par le codeur C2 sont respectivement lus aux adresses 0, 4, 8,3, 7, 2, 6, 1, 5. Pour créer l'effet de désordre, sans altérer l'effet de dispersion, on fait de plus subir aux données binaires de (au moins) certains couples (plus généralement de certains n-uples) un traitement 132, ou une modification appropriée. Un traitement 132 simple et très efficace consiste à permuter les données binaires à l'intérieur d'un couple, de manière périodique, avant de présenter au codeur élémentaire C2, par exemple selon la règle suivante: soit {ak, bk} le couple binaire mémorisé en position k, k = O,1...(N-1) dans la mémoire. Pour les valeurs impaires de la variable i, les données binaires du couple lu à l'adresse j suivant la règle (1) sont permutées avant d'être présentées au codeur C2. En reprenant l'exemple précédent, les N = 9 couples à coder par le codeur C2 sont alors présentés dans l'ordre suivant: {a., b0}, {b4, a4}, {as, b8} , {b3, a3}, {a7, b7}, {b2, a2}, {a6, b6}, {bl, a1}, {as, bs} Les couples ayant subi une permutation ont été notés en gras. D'autres opérations que la permutation des données binaires d'un couple sont bien sûr possibles, telles que par exemple: {ak, bk} * {ak + bk, bk} ou {ak, bk}: {bk, ak + bk) modulo 2 ou {ak, bk} * {ak, ak + bk} ou {ak, bk} - {ak + bk, ak} modulo 2 9 2796780 Bien sûr, l'opération réalisée sur les données binaires de chaque couple est inversible. En effet, par exemple, connaissant {ak + bk, bk} on obtient ak en sommant les composantes {ak + bk} et {bk}. Eventuellement, plusieurs opérations peuvent être cumulées et/ou utilisées alternativement. Dans l'exemple illustré en figure 1, le traitement 132 des blocs de données est effectué après l'opération de permutation 131 de ces mêmes blocs. Il est clair cependant que l'ordre de ces opérations peut être inversé. Il est possible d'effectuer tout d'abord le traitement sur des mots de code (n-uples) puis leur permutation. Ce procédé de permutation permet donc de construire des " turbo codes ", à partir d'une concaténation parallèle de codes convolutifs, récursifs, systématiques de rendement naturel n/(n + m); n > 2; m > 1. Les propriétés de distance, et notamment de distance minimale, de ces " turbo codes " sont supérieures à celles des " turbo codes " convolutifs connus. Ce résultat est d'autant plus marqué que le rendement de codage du " turbo code " est grand et que les blocs de données binaires à coder sont courts. Cette fonction de permutation est donc particulièrement désignée pour construire des " turbo codes " convolutifs en blocs, pour le codage des transmissions o les données sont structurées par trames courtes (ATM par exemple). Le décodage met en oeuvre les opérations inverses de celles mises en oeuvre lors du codage, à savoir: * une modification du contenu des mots de code reçu (modification inverse), de façon à restituer les mots de code d'origine (hors perturbations dues au canal de transmission); * une permutation de l'ordre des mots de code reçus, de façon à remettre ces derniers dans l'ordre initial. Le principe général du décodage complet est avantageusement similaire à celui décrit dans le brevet FR - 91 OS 280 déjà cité. Les informations élémentaires 2796780 que s'échangent les décodeurs élémentaires (appelées informations extrinsèques) ne sont cependant plus, bien sûr, des valeurs binaires, mais des mots de code, ou n-uples. L'information extrinsèque est donc portée par 2n grandeurs, correspondant aux 2" cas possibles pour les n- uples. Dans le cas de couples, tel que décrit précédemment, les décodeurs élémentaires s'échangent donc des données quatre par quatre. 11 2796780 REVENDICATIONS 1- Procédé de codage de données numériques source, mettant en oeuvre en parallèle au moins deux étapes (11, 12) de codage élémentaire prenant chacune en compte l'ensemble desdites données source (15), et comprenant une étape de permutation (13) modifiant l'ordre de prise en compte desdites données source entre lesdites étapes (11, 12) de codage élémentaire, caractérisé en ce que lesdites données source (15) sont organisées en mots de code source comprenant chacun n éléments binaires source, n supérieur ou égal à 2, et en ce que ladite étape de permutation (13) comprend: * une étape (132) de modification réversible du contenu d'au moins certains desdits mots de code source, délivrant des mots de code modifiés; * une étape (131) de permutation de l'ordre desdits mots de code source ou modifiés. 2- Procédé de codage selon la revendication 1, caractérisé en ce que ladite étape (131) de permutation de l'ordre des mots de code met en oeuvre une permutation uniforme appliquée sur un bloc de N mots de code consécutifs. 3- Procédé de codage selon la revendication 2, caractérisé en ce que ladite permutation uniforme utilise une mémoire (1311) contenant N mots de code introduits dans l'ordre 0 à N-1 et relue dans l'ordre j = P.i, i variant de 0 à N-1, P et N étant premiers entre eux. 4- Procédé de codage selon la revendication 3, caractérisé en ce que P est voisin de vN. - Procédé de codage selon l'une quelconque des revendications 1 à 4, caractérisé en ce que ladite modification (132) du contenu n'est appliquée que sur certains desdits mots de code. 6- Procédé de codage selon la revendication 5, caractérisé en ce que ladite modification (132) du contenu est appliquée à un mot de code sur deux. 7- Procédé de codage selon l'une quelconque des revendications 1 à 6, caractérisé en ce que ladite modification (132) du contenu comprend une 12 2796780 permutation de l'ordre des éléments binaires à l'intérieur du mot de code considéré. 8- Procédé de codage selon l'une quelconque des revendications 1 à 7, caractérisé en ce que ladite modification (132) du contenu comprend le remplacement d'au moins un des éléments binaires source du mot de code considéré par une combinaison d'au moins deux desdits éléments binaires source. 9- Procédé de codage selon l'une quelconque des revendications 1 à 8, caractérisé en ce que lesdits mots de code sont des couples d'éléments binaires. - Procédé de codage selon la revendication 9, caractérisé en ce que ladite étape de modification (132) du contenu associe au couple source {a, b} au moins un des couples modifiés suivants: (a, b) * (b,a) * (a+b, b) * (b, a+b) * (a, a+b) * (a+b, a) 11 - Procédé de codage selon l'une quelconque des revendications 1 à 10, caractérisé en ce qu'au moins une desdites étapes (11, 12) de codage élémentaires met en oeuvre un code convolutif, récursif et systématique de rendement naturel n/(n+m), associant à n entrées binaires n+m sorties binaires, avec n>2 et m>1. 12- Procédé de codage selon l'une quelconque des revendications 1 à 11, caractérisé en ce qu'il associe à un mot de code de n entrées binaires n + ml + m2 sorties binaires comprenant: * les n entrées binaires; * ml sorties binaires délivrées par une première étape de codage élémentaire; * m2 sorties binaires délivrées par une seconde étape de codage élémentaire. 13- Procédé de codage selon l'une quelconque des revendications 1 à 12, caractérisé en ce qu'il met en oeuvre une étape de poinçonnage (14). 13 2796780 14 - Dispositif de codage de données numériques source comprenant au moins deux codeurs élémentaires (11, 12) prenant chacun en compte l'ensemble desdites données source (15), et des moyens de permutation (13) modifiant l'ordre de prise en compte desdites données source par chacun desdits codeurs élémentaires, caractérisé en ce que lesdites données source sont organisées en mots de code source comprenant chacun n éléments binaires source, n supérieur ou égal à 2, et en ce que lesdits moyens de permutation (13) comprennent: * des moyens (132) de modification réversible du contenu d'au moins certains desdits mots de code source, délivrant des mots de code modifiés; * des moyens (131) de permutation de l'ordre desdits mots de code, source ou modifiés. - Procédé de décodage de données numériques codées selon le procédé de codage de l'une quelconque des revendications 1 à 13, caractérisé en ce qu'il comprend une étape de permutation comprenant: * une étape de modification du contenu d'au moins certains des mots de code reçus, ladite modification étant l'inverse de celle mise en oeuvre lors du codage; * une étape de permutation de l'ordre des mots de code reçus, de façon à remettre ces derniers dans l'ordre initial. 16 - Dispositif de décodage de données numériques codées selon le procédé de codage de l'une quelconque des revendications 1 à 13, caractérisé en ce qu'il comprend des moyens de permutation comprenant: * des moyens de modification du contenu d'au moins certains des mots de code reçus, ladite modification étant l'inverse de celle mise en oeuvre lors du codage; * des moyens de permutation de l'ordre des mots de code reçus, de façon à remettre ces derniers dans l'ordre initial. 14 2796780 17 - Dispositif d'émission et/ou de réception de données numériques codées selon le procédé de codage de l'une quelconque des revendications 1 à 13 ou décodées selon le procédé de décodage de la revendication 15.