1. Domaine de l'invention

Le domaine de l'invention est celui du codage et du décodage de données, mettant en œuvre un code correcteur d'erreurs.

Plus précisément, l'invention propose une nouvelle technique de codage de données source, délivrant des paquets de données codées ou un flux de données codées, destiné(s) à être transmis sur un canal de transmission (par exemple de type hertzien, optique ou électrique), ou stocké(s) dans un support matériel. L'invention concerne également une technique de décodage correspondante, permettant notamment de corriger les erreurs de transmission inhérentes au canal de transmission, et en particulier les erreurs de type effacement.

L'invention trouve notamment des applications dans les domaines suivants :

la transmission d'information par télécommunications filaires électriques, comme dans les normes ADSL, ou optiques, sur fibres optiques ou en espace libre ;

la transmission d'information dans les communications radios spatiales et terrestres sans fil (« wireless » en anglais), comme dans les systèmes de télévision numérique TNT, de radio numérique DAB, de téléphonie GSM ou U MTS, de réseau radio WiFi, et aussi dans les futurs systèmes de communications, comme les futures normes DVB, 4G, LTE, « Internet du futur », ou dans les communications entre véhicules, objets ou machines communicants ... ;

la compression et la décompression de source d'informations ;

la génération et la détection de séquences dites d'embrouillage (« scrambling » en anglais) dans les systèmes CDMA ;

le stockage d'informations dans des mémoires de masse magnétiques, optiques, mécaniques ou électriques pour constituer des disques durs, ou des mémoires vives d'ordinateurs, ou des clés mémoire à interface de type USB... ;

la correction d'informations lors des calculs dans un circuit intégré d'un microprocesseur ou dans un ordinateur ;

etc.

2. Art antérieur

De nombreuses techniques de codage permettent la correction d'erreurs de transmission (au décodage) en générant des données de redondance à partir de données source.

Ainsi, un code correcteur d'erreurs est classiquement défini par :

une longueur n, correspondant aux données en sortie du codeur (mot de code de longueur n formé de k données source et de (n - k) données de redondance), un nombre de bits ou de symboles d'information utiles k, correspondant aux données en entrée du codeur, encore appelées données source, et

une distance minimale d _min .

La distance minimale d'un code d _mjn correspond au minimum de distance entre deux mots de code. Elle permet de déterminer le nombre maximum d'erreurs que le code peut corriger dans un mot de code. Le rendement du code est quant à lui défini par R = k/n

Par exemple, un code de Hamming (8, 4, 4) est un code de longueur n = 8, prenant en entrée k = 4 symboles d'information utiles, de distance minimale d _mjn = 4, et de rendement 1/2.

Dans le brevet européen EP 1 101 288, J.C. Carlach et C. Vervoux ont présenté une technique de construction de codes quasi-optimaux, désignés par l'expression « codes Cortex ». De tels codes sont construits en utilisant plusieurs étages de codage, mettant chacun en œuvre plusieurs modules de codage de base simples, et des étages de brassage entre deux étages de codage. Une telle technique permet de construire des codes auto-duaux de type-l et de tye-ll, selon la parité du nombre d'étages.

Un inconvénient d'une telle technique est qu'elle nécessite un grand nombre d'étages de codage pour obtenir des codes de grandes distances minimales d _min par rapport à la longueur n d'un mot de code.

De manière générale, la distance minimale d _mjn n'est donc pas optimale pour ces longueurs n et k, c'est-à-dire que la distance minimale n'est pas la plus proche possible d'une borne pour laquelle le code permet de détecter le nombre maximum d'erreurs (borne de Hamming ou « Sphere-Packing Bound », telle que d _min /n≤ 0,22 pour un code auto-dual de k

rendement - = 1/2) ou de la borne de Gilbert-Varshamov (telle que d _min /n « 0,11 pour un k

code auto-dual de rendement - = 1/2).

Or, plus la distance minimale d _mjn est grande, meilleur est le code correcteur d'erreurs, puisqu'il permet de détecter (d _min — 1) symboles erronés et d'en corriger [(d _min — 1)/2J (où l'opérateur [. J désigne la partie entière).

Or les décodeurs de codes Cortex actuels ne fonctionnent pas de façon optimale dès que le nombre d'étages de codage utilisés pour construire le code Cortex dépasse un nombre de trois étages de codage. Ceci est principalement dû au fait que les variables intermédiaires (variables d'état internes) entre les étages de codage ne sont pas transmises et ne possèdent donc pas de valeurs de vraisemblance ou de probabilités a priori avec lesquelles on puisse les initialiser, notamment lors de la mise en œuvre au décodage d'un algorithme de type propagation des probabilités (en anglais « Belief Propagation » ou BP).

Cette difficulté à décoder des codes Cortex construits en utilisant plus de trois étages de codage rend problématique l'utilisation de codes Cortex plus longs, devant comporter plus d'étages de codage pour obtenir des distances minimales beaucoup plus grandes. Or un nombre supérieur d'étages de codage permet d'obtenir des codes offrant des capacités pratiques importantes de correction d'erreurs.

Il existe donc un besoin pour une nouvelle technique de codage correcteur d'erreurs, permettant de générer des mots de code présentant de grandes distances minimales, et pouvant être décodés simplement.

3. Exposé de l'invention

L'invention propose une solution nouvelle qui ne présente pas l'ensemble de ces inconvénients de l'art antérieur, sous la forme d'un dispositif de codage correcteur d'erreurs, apte à mettre en œuvre un code correcteur d'erreurs global associant des données de redondance à des données source, le code correcteur global étant susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage des données source aux données de redondance inversible.

Selon l'invention, le dispositif de codage comprend :

deux étages de permutation de premier niveau, dont :

o un premier étage de permutation de premier niveau connecté, en entrée, d'une part à des variables d'entrée associées à un premier ensemble des données source et/ou de redondance, et d'autre part à des variables internes associées à des données d'entrée et des données de sortie d'un premier étage de codage de deuxième niveau, et

o un deuxième étage de permutation de premier niveau connecté, en sortie, d'une part à des variables de sortie associées à un deuxième ensemble des données source et/ou de redondance, et d'autre part à des variables internes associées à des données d'entrée et des données de sortie d'un deuxième étage de codage de deuxième niveau,

le premier ensemble et le deuxième ensemble formant un mot de code,

un étage de codage de premier niveau connecté d'une part aux variables associées aux données de sortie du premier étage de permutation de premier niveau et d'autre part aux variables associées aux données d'entrée du deuxième étage de permutation de premier niveau,

chaque étage de codage comprenant au moins deux modules de codage de base mettant chacun en œuvre un code de base susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible. Dit autrement, selon l'invention le dispositif de codage comprend :

un étage de codage de premier niveau et

deux étages de permutation de premier niveau, dont :

o un premier étage de permutation de premier niveau connecté d'un côté à des variables d'entrée associées à un premier ensem ble desdites données source et/ou de redondance, et à des variables internes associées à des données d'entrée et des données de sortie d'un premier étage de codage de deuxième niveau, et d'un autre côté audit étage de codage de premier niveau,

o un deuxième étage de permutation de premier niveau connecté d'un côté à des variables de sortie associées à un deuxième ensemble desdites données source et/ou de redondance, et à des variables internes associées à des données d'entrée et des données de sortie d'un deuxième étage de codage de deuxième niveau, et d'un autre côté audit étage de codage de premier niveau,

ledit premier ensemble et ledit deuxième ensemble formant un mot de code, et chaque étage de codage comprenant au moins deux modules de codage de base mettant chacun en œuvre un code de base susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible.

L'invention propose ainsi un nouveau dispositif de codage correcteur d'erreurs, dont la structure particulière permet de construire un code global performant avec une grande distance minimale, même si le nombre d'étage de codage est faible (trois étages de codage par exemple).

De ce fait, les mots de code obtenus en utilisant un code global ainsi construit peuvent être décodés en utilisant les décodeurs de codes Cortex actuels, basés sur des décodages itératifs de type « Belief Propagation » performants, ou un décodeur selon l'invention.

Selon l'invention, on considère que la matrice de passage des données source aux données de redondance est inversible. Aucune autre contrainte n'est imposée sur le code correcteur d'erreurs, et notamment sur la longueur de ce code ou la longueur des cycles. On peut donc considérer que le code correcteur d'erreurs mis en œuvre est quasi-aléatoire.

En particulier, le codeur proposé permet de construire un code global auto-dual avec une grande distance minimale quelque soit la longueur du code, et notamment pour un code assez court (de l'ordre de n < 1000). L'invention permet ainsi un décodage plus simple et plus performant que les techniques de l'art antérieur, notamment pour les codes présentant de petites longueurs et/ou des cycles courts.

Pour ce faire, on considère au moins trois étages de codage, comprenant chacun au moins deux modules de codage de base fonctionnant indépendamment, chaque module de codage de base mettant en œuvre un code de base. Seul l'étage de codage de premier niveau est connecté à des variables d'entrée et à des variables de sortie correspondant aux données source et aux données de redondance, après permutation. Les autres étages de codage sont connectés uniquement à des variables internes, qui sont des variables d'état, non transmises au décodeur. La structure est donc récursive et fermée.

En particulier, les codes de base appartiennent au groupe comprenant :

un code de Hamming ;

un code identité ;

un code de Golay ;

un code à répétition simple ;

Par exemple, un code de base est un code de Hamming (8,4,4), ou un code définit sur un alphabet quaternaire TL\, ou un code de Golay (24, 12, 8) ....

On choisit avantageusement un code de base présentant une grande distance minimale. Ainsi, les codes de base ont la propriété de mettre en œuvre des codes auto-duaux. Cette propriété d'auto-dualité permet un décodage optimal avec une complexité de décodage réduite.

Elle garantit notamment un rendement de codage égal à 1/2.

Selon une caractéristique particulière de l'invention, le dispositif de codage comprend au moins deux étages de permutation de q-ème niveau, avec q un entier supérieur ou égal à 2, dont : un premier étage de permutation de q-ème niveau connecté, en entrée, à des variables internes associées aux données d'entrée et aux données de sortie d'un premier étage de codage de (q+l)-ème niveau, et, en sortie, à des variables internes associées aux données d'entrée et aux données de sortie d'un premier étage de codage de q-ème niveau ;

un deuxième étage de permutation de q-ème niveau connecté, en entrée, à des variables internes associées aux données d'entrée et aux données de sortie d'un deuxième étage de codage de q-ème niveau et, en sortie, à des variables internes associées aux données d'entrée et aux données de sortie d'un deuxième étage de codage de (q+l)-ème niveau. Selon un exemple de réalisation, chaque module de codage de base du ou des étages de codage de i-ème niveau comprend c entrées et c sorties, et chaque étage de permutation de i- ème niveau met en œuvre une permutation de type c-cyclique, avec i et c des entiers supérieurs ou égaux à 1. En particulier, c est égal à 4.

Une permutation de type c-cyclique est une permutation selon laquelle un même motif de permutation est appliqué pour chaque bloc de longueur c.

En particulier, de telles permutations cycliques par bloc sont faciles à implémenter. L'utilisation de permutations c-cycliques permet notamment de minimiser le nombre d'opérations d'accès mémoire (lecture/écriture), et d'éviter les problèmes de conflit d'accès mémoire.

Par exemple, une telle permutation de type c-cyclique s'écrit sous la forme :

avec, pour conditions, que D = {Δο, Δ-^ ... , Δ^ _! ) soit un ensemble de paramètres entiers tels que :

les paramètres (Δ ₀ , A ₁ ... , A _C--1 ) doivent prendre au moins trois valeurs différentes, ou si les paramètres (à ₀ , A ₁ ... , Δ _ε _ ₁ ) ne prennent que deux valeurs différentes, alors chacune des deux valeurs est au moins présente deux fois dans l'ensemble .

Selon un autre exemple de réalisation, chaque étage de permutation de i-ème niveau met en œuvre une permutation affine, avec i un entier supérieur ou égal à 1.

Selon un aspect spécifique de l'invention, le ou les étages de codage de i-ème niveau comprennent chacun au moins deux modules de permutation locale, chaque module de permutation locale permutant les variables internes obtenues en sortie d'un module de codage de base.

De telles permutations locales permettent notamment d'obtenir des mots de code de base présentant de bonnes distances minimales.

Selon une caractéristique particulière, le dispositif de codage présente une structure symétrique.

Ainsi, les deux étages de codage de q-ième niveau sont localisés de part et d'autre de l'étage de codage de premier niveau (q≥ 2), et comprennent un même nombre d'entrées et de sorties.

De la même façon, les deux étages de permutation de (q-l)-ième niveau, inséré chacun entre un des étages de codage de (q-l)-ième niveau et un des étages de codage de q-ième niveau sont symétriques. Par exemple, si l'on note π ₀ la permutation insérée entre le premier étage de codage de deuxième niveau et l'étage de codage de premier niveau, alors la permutation insérée entre le deuxième étage de codage de deuxième niveau et l'étage de codage de premier niveau, notée π-L, sera telle que π ₁ = π ₀ ^_1 .

En particulier, une symétrie entre les données source et les données de redondance permet de concevoir des algorithmes de type « Belief-Propagation » plus rapides à converger, car travaillant sur des couples (χ _ί( ) pour i = 0,1, ... , k— 1.

Selon une caractéristique particulière de l'invention, le nombre de variables internes est deux fois supérieur au nombre de variables associées aux données source.

Selon un mode de réalisation particulier, tous les modules de codage de base mettent en œuvre un code de base identique.

Ainsi, le dispositif de codage selon l'invention est simplifié par l'utilisation de modules de codage de base mettant en œuvre des codes de base identiques.

Selon un aspect particulier de l'invention, le dispositif comprend un module de forçage à zéro, mettant à la valeur nulle au moins une des données source et/ou au moins une des données de redondance.

Ce « forçage » à zéro de certaines données permet notamment d'obtenir, de façon très flexible, des codes de rendement différent de ½ et dont les distances minimales restent bonnes, même lorsque le rendement tend vers 1. De même, on peut construire des codes quasi-optimaux avec des rendements tendant vers zéro. En effet, les données forcées à zéro au moment du codage représentent à la réception des informations nulles parfaites non-bruitées.

Il est également possible d'obtenir un rendement différent de ½ en utilisant une structure non symétrique.

En particulier, l'ensemble des étages de codage et de permutation forme un graphe de Tanner, dont les entrées sont les variables d'entrée associées au premier ensemble de données source et/ou de redondance, et les sorties sont les variables de sortie associées au deuxième ensemble de données source et/ou de redondance.

Par exemple, les deux étages de codage de (q+l)-ème niveau et les deux étages de permutation de q-ème niveau sont symétriques l'un de l'autre par rapport à l'axe du milieu du graphe de Tanner.

Dans un autre mode de réalisation, l'invention concerne un procédé de codage correcteur d'erreurs, apte à mettre en œuvre un code correcteur d'erreurs global associant des données de redondance à des données source, le code correcteur global étant susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage des données source aux données de redondance inversible.

Selon l'invention, un tel procédé de codage met en œuvre :

deux étapes de permutation de premier niveau, dont : o une première étape de permutation de premier niveau recevant, en entrée, d'une part un premier ensemble des données source et/ou de redondance, et d'autre part des données d'entrée et des données de sortie obtenues à partir d'une première étape de codage de deuxième niveau, et

o une deuxième étape de permutation de premier niveau délivrant, en sortie, d'une part un deuxième ensemble des données source et/ou de redondance, et d'autre part des données d'entrée et des données de sortie obtenues à partir d'une deuxième étape de codage de deuxième niveau,

le premier ensemble et le deuxième ensemble formant un mot de code, et

une étape de codage de premier niveau recevant les données de sortie de la première étape de permutation de premier niveau et délivrant des données d'entrée à la deuxième étape de permutation de premier niveau,

chaque étape de codage mettant en œuvre au moins deux modules de codage de base mettant chacun en œuvre un code de base susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible.

Un tel procédé peut notamment être mis en œuvre par un dispositif de codage correcteur d'erreurs tel que décrit précédemment. Ce procédé pourra bien sûr comporter les différentes caractéristiques relatives au dispositif de codage selon l'invention, qui peuvent être combinées ou prises isolément. Ainsi, les caractéristiques et avantages de ce procédé sont les mêmes que ceux du dispositif de codage, et ne sont pas détaillés plus amplement.

En particulier, chaque étape correspond avantageusement à un étage de la structure du dispositif de codage correspondant, et peut être implémentée sous la forme d'un circuit intégré, ou dans un composant électronique de type microprocesseur. Cette structure permet une compréhension plus aisée de l'invention. Cependant, le procédé de l'invention peut être mis en œuvre sous tout autre forme adéquate, et notamment sous forme essentiellement logicielle, un ou plusieurs processeurs effectuant le traitement correspondant.

L'invention concerne par ailleurs un dispositif de décodage correcteur d'erreurs, apte à retrouver des données source à partir d'un mot de code reçu, les données source ayant été codées par un code correcteur d'erreurs global associant des données de redondance aux données source, le code correcteur global étant susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage des données source aux données de redondance inversible.

Selon l'invention, un tel dispositif de décodage comprend :

deux étages de permutation de premier niveau, dont : o un premier étage de permutation de premier niveau connecté, en entrée, d'une part à des variables d'entrée associées à un premier ensemble des données source et/ou de redondance, et d'autre part à des variables internes associées à des données d'entrée et des données de sortie d'un premier étage de décodage de deuxième niveau, et

o un deuxième étage de permutation de premier niveau connecté, en sortie, d'une part à des variables de sortie associées à un deuxième ensemble des données source et/ou de redondance, et d'autre part à des variables internes associées à des données d'entrée et des données de sortie d'un deuxième étage de décodage de deuxième niveau,

le premier ensemble et le deuxième ensemble formant le mot de code, et

un étage de décodage de premier niveau connecté d'une part aux variables associées aux données de sortie du premier étage de permutation de premier niveau et d'autre part aux variables associées aux données d'entrée du deuxième étage de permutation de premier niveau,

chaque étage de décodage comprenant au moins deux modules de décodage de base mettant chacun en œuvre un code de base susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible.

Un tel dispositif de décodage présente une structure similaire à celle du dispositif de codage décrit ci-dessus. Il présente donc les mêmes caractéristiques que le dispositif de codage selon l'invention, qui peuvent être combinées ou prises isolément.

En particulier, un tel dispositif peut être utilisé pour décoder des mots de code obtenus à partir du dispositif de codage décrit ci-dessus.

Dans un autre mode de réalisation, l'invention concerne un procédé de décodage correcteur d'erreurs, apte à retrouver des données source à partir d'un mot de code reçu, les données source ayant été codées par un code correcteur d'erreurs global associant des données de redondance aux données source, le code correcteur global étant susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage des données source aux données de redondance inversible.

Selon l'invention, un tel procédé de décodage met en œuvre :

deux étapes de permutation de premier niveau, dont :

o une première étape de permutation de premier niveau recevant, en entrée, d'une part un premier ensemble des données source et/ou de redondance, et d'autre part des données d'entrée et des données de sortie obtenues à partir d'une première étape de décodage de deuxième niveau, et

o une deuxième étape de permutation de premier niveau délivrant, en sortie, d'une part un deuxième ensemble des données source et/ou de redondance, et d'autre part des données d'entrée et des données de sortie obtenues à partir d'une deuxième étape de décodage de deuxième niveau,

le premier ensemble et le deuxième ensemble formant le mot de code, et

une étape de décodage de premier niveau recevant les données de sortie de la première étape de permutation de premier niveau et délivrant des données d'entrée à la deuxième étape de permutation de premier niveau,

chaque étape de décodage mettant en œuvre au moins deux modules de décodage de base mettant chacun en œuvre un code de base susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible.

Un tel procédé peut notamment être mis en œuvre par un dispositif de décodage correcteur d'erreurs tel que décrit précédemment. Ce procédé pourra bien sûr comporter les différentes caractéristiques relatives au dispositif de décodage correcteur d'erreurs selon l'invention, qui peuvent être combinées ou prises isolément. Ainsi, les caractéristiques et avantages de ce procédé sont les mêmes que ceux du dispositif de décodage correcteur d'erreurs, et ne sont pas détaillés plus amplement.

En particulier, chaque étape correspond avantageusement à un étage de la structure du dispositif de décodage correspondant ; et peut être implémentée sous la forme d'un circuit intégré, ou dans un composant électronique de type microprocesseur. Cette structure permet une compréhension plus aisée de l'invention. Cependant, le procédé de l'invention peut être mis en œuvre sous tout autre forme adéquate, et notamment sous forme essentiellement logicielle, un ou plusieurs processeurs effectuant le traitement correspondant.

Ainsi, l'invention concerne également un ou plusieurs programmes d'ordinateur comportant des instructions pour la mise en œuvre d'un procédé de codage et/ou d'un procédé de décodage lorsque le ou les programmes sont exécutés par un processeur. De tels programmes peuvent être stockés sur un support de stockage.

Finalement, l'invention concerne un dispositif apte à mettre en œuvre les opérations de codage et de décodage correspondantes.

4. Liste des figures

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 particulier, donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés, parmi lesquels :

la figure 1 présente les principales étapes mises en œuvre par un procédé de codage selon un mode de réalisation de l'invention ;

la figure 2 illustre la structure d'un codeur et/ou d'un décodeur à trois étages de (dé)codage selon un mode de réalisation de l'invention ;

la figure 3 présente les principales étapes mises en œuvre par un procédé de décodage selon un mode de réalisation de l'invention ;

la figure 4 illustre la structure d'un codeur et/ou d'un décodeur à sept étages de (dé)codage selon un mode de réalisation de l'invention ;

les figures 5A et 5B présentent un exemple de construction et d'utilisation du code Golay (24, 12, 8) selon un mode de réalisation de l'invention ;

les figures 6A et 6B présentent un exemple de construction et d'utilisation d'un code auto-dual (72,36,12) de type II selon un mode de réalisation de l'invention.

5. Description d'un mode de réalisation de l'invention

5.1 Principe général

Le principe général de l'invention repose sur une structure particulière d'un code correcteur d'erreurs, basée sur une alternance d'étages de codage et d'étages de permutation.

En particulier, la structure de codage proposée permet de construire des codes correcteurs d'erreurs auto-duaux avec seulement trois étages de codage et un nombre minimum de variables internes « cachées » (i.e. non-transmises), encore appelées variables intermédiaires ou variables d'état, et ayant de grandes distances minimales. Elle fournit notamment une solution pratique pour protéger le mieux possible de petits paquets d'information (n < 1000 bits) contre les bruits et les interférences inhérents à tout canal de transmission. Elle simplifie en outre le décodage, du fait du faible nombre d'étages de codage utilisé.

En particulier, on rappelle que parmi les techniques de codage permettant la correction d'erreurs de transmission, les turbo-codes et les codes LDPC (en anglais « Low-Density Parity Check ») présentent de très bonnes performances en termes de correction d'erreurs pour des codes de grande longueur n, avec n de l'ordre de quelques milliers de bits au moins (n > 1000). En revanche, les turbo-codes et les codes LDPC présentent des performances plus faibles pour des codes de plus petite longueur.

La solution proposée permet d'obtenir des codes performants mêmes assez courts (/i<1000), présentant une grande distance minimale, où par exemple d _min est une faction de n, et permet donc notamment de concurrencer ces turbo-codes et ces codes LDPC.

On présente, en relation avec la figure 1, les principales étapes mises en œuvre par un procédé de codage correcteur d'erreurs selon l'invention. Un tel procédé est notamment apte à mettre en œuvre un code correcteur d'erreurs global auto-dual, c'est-à-dire susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage des données source (X) aux données de redondance ( ) inversible.

Comme illustré en figure 1, le procédé de codage met en œuvre :

une étape de codage de premier niveau 11, notée C _N1 , recevant par exemple en entrée des données source X, après permutations, et délivrant par exemple en sortie des données de redondance R, après permutations. Une telle étape de codage de premier niveau met en œuvre au moins deux modules de codage de base, connectés d'une part à toutes les variables associées aux données source et aux données de redondance, et d'autre part à des variables internes ;

une première 121 et une deuxième 122 étapes de codage de deuxième niveau, notées respectivement C _N2jl et C _N2,2 , mettant chacune en œuvre au moins deux modules de codage de base connectés uniquement aux variables internes de l'étape de codage de premier niveau 11 C _N1 après permutations ;

une première 131 et une deuxième 132 étapes de permutation de premier niveau, notées respectivement π ₀ et π . La première étape de permutation 131 π ₀ est mise en œuvre entre l'étape de codage de premier niveau 11 C _m et la première étape de codage de deuxième niveau 121 C _N2 ,i, et reçoit donc, en entrée, d'une part les données source X et d'autre part les données d'entrée et des données de sortie obtenues à partir de la première étape de codage de deuxième niveau 121 C _N2j i. La deuxième étape de permutation 132 π ₁ est mise en œuvre entre l'étape de codage de premier niveau 11 C _m et la deuxième étape de codage de deuxième niveau 122 C _{N2 2} et délivre donc, en sortie, d'une part les données de redondance R et d'autre part des données d'entrée et des données de sortie à la deuxième étape de codage de deuxième niveau 122 C _{N2 2} .

En particulier, on note que chaque module de codage de base met en œuvre un code de base auto-dual, susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible.

On considère ici une définition générale de la dualité, encore appelée iso-dualité, telle qu'exprimée notamment dans le document « Handbook of coding theory », V.S. Pless et W.C.

Huffman - Volume I - Chapitre 3 - pages 177 et 199. Cette définition impose pour seule contrainte l'inversibilité de la matrice de passage des données d'entrée aux données de sortie.

La figure 2 illustre plus spécifiquement la structure d'un dispositif de codage correspondant, sous la forme d'un graphe de Tanner comprenant trois étages de codage, dit « Cortex-Compact ».

Un tel dispositif reçoit en entrée des données sources X, organisées par exemple en blocs de m bits. Le premier bloc de données source comprend par exemple les bits d'information x ₀ à x _m -i, le deuxième bloc les bits d'information x _m à a¾m-i _> ··· _< le (k+l)-ième bloc les bits d'information x _k - _m à χ¾_ι, avec k un multiple de m. Un tel dispositif délivre en sortie des données de redondance , organisées également en blocs de m bits. Le premier bloc de données de redondance comprend par exemple les bits de redondance r ₀ à r _m _ , le deuxième bloc les bits de redondance r _m à r _2m _i, le (k+l)-ième bloc les bits de redondance r _k _ _m à r _k _ _lt avec k un multiple de m.

On note que selon l'exemple illustré en figure 2, les données source sont associées à des variables d'entrée et placées à gauche du graphe de Tanner représentatif du dispositif de codage, et les données de redondance sont associées à des variables de sortie et sont placées à droite du graphe de Tanner. Il ne s'agit ici que d'un choix de représentation, et une partie des données de redondance (voire l'ensemble des données de redondance) pourraient être placée à gauche du graphe de Tanner, et donc associées à des variables d'entrée du graphe de Tanner. De même, le nombre de bits d'information k n'est pas nécessairement égal au nombre de bits de redondance (n-k).

Un tel dispositif de codage comprend au moins :

un étage de codage de premier niveau 21 comprenant au moins deux modules de codage de base Cb, connectés d'une part à toutes les variables associées aux données source x _t et aux données de redondance , pour / ^' allant de 0 à k-1, et d'autre part à des variables internes dj et fj, par exemple pour j allant de 0 à 2k-l, par l'intermédiaire d'un premier 231 ou d'un deuxième 232 étage de permutation de premier niveau ;

un premier 221 et un deuxième 222 étages de codage de deuxième niveau, connectés chacun à l'étage de codage de premier niveau 21 respectivement par l'intermédiaire du premier 231 ou du deuxième 232 étage de permutation de premier niveau.

Chaque étage de codage de deuxième niveau comprend au moins deux modules de codage de base Cb, connectés uniquement aux variables internes de l'étage de codage de premier niveau 21, par l'intermédiaire d'un premier 231 ou d'un deuxième 232 étage de permutation de premier niveau.

Les seules variables auxquelles on a accès sont donc les variables d'entrée et de sortie du graphe de Tanner, auxquelles sont associées des données source et/ou de redondance. Les autres variables internes ne sont pas transmises au décodeur.

Selon l'exemple illustré, chaque module de codage de base met en œuvre un même code de base noté Cb. Bien entendu, les modules de codage de base peuvent mettre en œuvre différents codes de base, au sein d'un même dispositif de codage. En effet, les différents modules de codage sont indépendants. De préférence, le nombre d'entrées (respectivement le nombre de sorties) de chaque module de codage de base est identique.

On considère par exemple que m = 4 et que chaque module de codage de base met en œuvre un code de Hamming (8, 4, 4). Un tel code est optimal pour sa longueur n = 8 et sa dimension k = 4 avec une distance minimale d _min = 4. Ce code de base de Hamming (8,4,4) est auto-dual et a tous ses mots de code de poids multiples de 4. Il est donc dit par définition auto-dual de type-Il.

Selon un autre exemple, on considère que m = 1 et que chaque module de codage de base met en œuvre un code à répétition simple, dont un mot de code est obtenu à partir d'une répétition d'une donnée source. Par exemple, on obtient le bit de redondance r ₀ = x ₀ à partir du bit source x ₀ . Ce code de base est auto-dual de type-l.

Selon d'autres exemples, les modules de codage de base mettent en œuvre des codes de Golay (comme le code (24, 12, 8), avec m = 12), des codes définis sur des alphabets quaternaires Z4, des codes identités, des codes à répétition simple, etc.

En revenant à la figure 2, et en considérant que chaque module de codage de base met en œuvre un code de Hamming (8, 4, 4), le premier étage de permutation de premier niveau 231, mettant en œuvre une permutation π ₀ , reçoit d'une part des bits d'information par paquets de quatre bits, notés par exemple x ₀ _ ₃ pour le paquet de bits d'information x _Q , x , x ₂ , x^), d'autre part des variables internes d'entrée et de sortie des modules de codage du premier étage de codage de deuxième niveau 221, également par paquets de quatre bits.

Ainsi, chaque module de codage de base Cb du premier étage de codage de deuxième niveau 221 est connecté à quatre variables internes, notées par exemple d ₀ _ ₃ pour le paquet (d ₀ , d ₁ , d ₂ , d ₃ ). Ces quatre variables internes sont transformées linéairement, modulo 2, en quatre variables images, notées par exemple f ₀ _ ₃ pour le paquet ( ο _< Λ _< 2 _< 3)< conformément au code de base de Hamming (8, 4, 4), telles que :

où P est la matrice de passage des données d'entrée d ₀ _ ₃ aux données de sortie ₀ _ ₃ correspondant à la matrice identité de dimension 4, inversée modulo 2 :

0 1 1 1

P = 1 0 1 1

1 1 0 1

1 1 1 0

On note que les sorties de chaque module de codage de base des différents étages de codage peuvent être permutées localement pour obtenir des codes « locaux » de bonne distance minimale d _min . Par exemple, il est possible de permuter les quatre bits ₀ _ ₃ pour obtenir un code « local » de grande distance minimale. On note qu'il y a 14 = 24 permutations possibles pour un vecteur de quatre bits.

Le premier étage de permutation de premier niveau 231 est donc connecté en entrée à k variables correspondant aux k bits d'information (χ ₀ _^_^) et à 2k variables internes (do- _(f e-i ₎ ' o- _(f c-i ₎ )- Ces 3k variables, après permutations, sont connectées à l'étage de codage de premier niveau 21.

L'étage de codage de premier niveau 21 met en œuvre 3k/4 modules de codage de base de t e Hamming (8,4,4), délivrant k bits de redondance (r ₀ _ _(fe _ ₁ - ₎ ) et 2k variables internes

Si l'on considère une structure symétrique, le deuxième étage de permutation de premier niveau 232 reçoit ces 3k variables, met en œuvre une permutation π ₁ = π ₀ ^_1 et délivre d'une part des bits de redondance par paquets de quatre bits, notés par exemple r ₀ _ ₃ pour le paquet de bits de redondance _Q , r , r ₂ , r^) , d'autre part des variables internes d'entrée et de sortie des modules de codage du deuxième étage de codage de deuxième niveau 222, également par paquets de quatre bits.

On note qu'il est possible de trouver de très bons codes correcteurs globaux en gardant la contrainte de la symétrie miroir entre les données source et les données de redondance sur cette structure, par rapport à l'axe du milieu du graphe de Tanner. Une telle symétrie permet un repliement par rapport à cet axe et donc un décodage par couples de variables symétriques. La conséquence en est la possibilité de concevoir des algorithmes à propagation de probabilités (BP) performants et plus rapides à converger car travaillant sur des couples (X _j , r _j ) pour i = 0, 1, . . . , k - 1.

Ainsi, si le nombre de bits d'information est égal à k comme présenté dans l'exemple ci- dessus, alors la longueur totale du code global est de n = 2k et la taille des permutations π ₀ et π ₁ est égale à l = 3k pour un code de base de Hamming (8,4,4) par paquet de 4 bits d'information, ce qui fait aussi 2k variables internes dj, soit un bit associé à une variable interne par bit de code.

On note qu'une telle structure symétrique n'est cependant pas obligatoire. Notamment, il est possible de définir une structure dissymétrique en utilisant des permutations non symétriques dans les premier et deuxième étages de permutation de i-ème niveau (i.e. π ₁ ≠ π ₀ ^_1 ), un nombre de modules de codage différents dans les premier et deuxième étages de codage de i-ème niveau, et/ou des modules de codage mettant en œuvre des codes de base différents dans les premier et deuxième étages de codage de i-ème niveau, pour i≥ 1. Il est également possible de généraliser la structure en prenant un plus grand nombre de variables internes, et donc de modules de codage de base, au niveau des étages de codage de q- ème niveau, avec q≥ 2.

La figure 3 illustre ainsi un exemple de dispositif de codage mettant en œuvre :

- un étage de codage de premier niveau 31, comprenant des modules de codage de base B0, Bl, etc ;

deux étages de permutation de premier niveau 321, 322, de part et d'autre de l'étage de codage de premier niveau 31 ;

deux étages de codage de deuxième niveau 331, 332, de part et d'autre de l'ensemble de premier niveau formé par l'étage de codage de premier niveau 31 et les deux étages de permutation de premier niveau 321, 322, dont un premier étage comprenant des modules de codage de base AO, Al, etc, et un deuxième étage comprenant des modules de codage de base CO, Cl, etc ;

deux étages de permutation de deuxième niveau 341, 342, de part et d'autre de l'ensemble formé par l'ensemble de premier niveau et les deux étages de codage de deuxième niveau

331, 332 ;

deux étages de codage de troisième niveau 351, 352 de part et d'autre de l'ensemble de deuxième niveau formé par l'ensemble de premier niveau, les deux étages de codage de deuxième niveau 331, 332, et les deux étages de permutation de deuxième niveau 341, 342, dont un premier étage comprenant des modules de codage de base DO, Dl, etc, et un deuxième étage comprenant des modules de codage de base EO, El, etc ;

deux étages de permutation de troisième niveau 361, 362, de part et d'autre de l'ensemble formé par l'ensemble de deuxième niveau et les deux étages de codage de troisième niveau 351, 352 ;

- deux étages de codage de quatrième niveau 371, 372 de part et d'autre de l'ensemble de troisième niveau formé par l'ensemble de deuxième niveau, les deux étages de codage de troisième niveau 351, 352, et les deux étages de permutation de troisième niveau 361, 362.

On note toutefois qu'une telle augmentation du nombre de variables internes complexifie la structure et rend moins performant un éventuel décodage itératif par propagation de probabilités.

On note par ailleurs, en revenant à la figure 2, que comme les modules de codage de base de l'étage de codage de premier niveau 21 mettent chacun en œuvre un code de Hamming (8, 4, 4) de poids tous multiples de 4, le code équivalent de l'étage de codage de premier niveau 21 est de poids multiple de 4. Par soustraction, l'ensemble des variables internes d _Q _ ₂ k ^et o-2¾ formant aussi un code de poids multiple de 4, chaque mot de code formé par les bits d'information χ ₀ _^_^ et les bits de redondance r ₀ _( _fe _ ₁ - ₎ est de poids multiple de 4 et donc le code global obtenu, dit Cortex-Compact, est aussi auto-dual de type-I l.

On note finalement que l'existence d'un code global n'est assurée que si l'on peut résoudre le système d'équations liant toutes les variables entre-elles, par l'intermédiaire des codes de base. De façon équivalente, cela signifie que l'on peut déterminer une matrice génératrice du code global dont le déterminant est non nul (par exemple égal à 1 (modulo 2) dans le cas binaire), ou encore que la matrice génératrice comprend, sous sa forme systématique, une matrice identité et une matrice de passage des données source aux données de redondance inversible.

A partir de la structure illustrée en figure 2, il est ainsi possible de déterminer un système d'équations. En effet, un tel graphe de Tanner comprend des variables d'entrée, correspondant par exemple aux bits d'information, et des variables de sortie, correspondant par exemple aux bits de redondance, les bits de redondance étant liés aux bits d'information par l'intermédiaire de contraintes et de permutations.

Ces contraintes peuvent être de deux types :

- les contraintes de type égalité, correspondant à une répétition de la variable connectée à cette contrainte ;

- les contraintes de type addition modulo 2, correspondant à une contrainte logique de type « ou-exclusif ».

Ces contraintes et permutations permettent de définir des relations algébriques, et de calculer une matrice génératrice permettant de réaliser le codage. En particulier, le calcul des données de redondance doit se faire par le pré-calcul de la matrice de passage, qui peut être construite à partir du système d'équations.

Ainsi, un codeur selon l'invention prend en entrée des données source X, sous la forme de paquets ou d'un flux continu, et délivre en sortie au moins un mot de code, comprenant les données source X et des données de redondance . Ces mots de code peuvent être véhiculés dans un canal de transmission ou stockées sur un support, puis décodées par un décodeur selon l'invention.

En particulier, un tel décodeur peut également utiliser un graphe de Tanner tel qu'illustré en figure 2, pour corriger des erreurs de type effacement notamment.

Par exemple, comme illustré en figure 4, le décodeur reçoit en entrée au moins un mot de code, comprenant les données source X et des données de redondance R éventuellement entachées d'erreur, et délivre une estimation des données source X.

Un tel procédé de décodage met en œuvre, de façon symétrique au codage : une étape 41 de décodage de premier niveau, notée DC _N1 , recevant en entrée un mot de code formé de données source X et/ou de redondance , après permutations, et délivrant en sortie une estimation des données source X, après permutations. Une telle étape de décodage de premier niveau met en œuvre au moins deux modules de décodage de base, connectés d'une part à toutes les variables associées aux données source et aux données de redondance du mot de code, et d'autre part à des variables internes ;

une première 421 et une deuxième 422 étapes de décodage de deuxième niveau, notées respectivement DC _{N2 1} et DC _{N2 2} , mettant chacune en œuvre au moins deux modules de décodage de base connectés uniquement aux variables internes de l'étape 41 de décodage de premier niveau DC _N1 , après permutations ;

une première 431 et une deuxième 432 étapes de permutation de premier niveau, notées respectivement π ₀ et π . La première étape de permutation 431 π ₀ est mise en œuvre entre l'étape de décodage de premier niveau 41 DC _N i et la première étape de décodage de deuxième niveau 421 DC _N2 ,i, et reçoit donc, en entrée, d'une part le mot de code formé des données source X et/ou de redondance R et d'autre part les données d'entrée et des données de sortie obtenues à partir de la première étape de décodage de deuxième niveau 421 DC _N2j i. La deuxième étape de permutation 432 π ₁ est mise en œuvre entre l'étape de décodage de premier niveau 41 DC _N i et la deuxième étape de décodage de deuxième niveau 422 DC _{N2 2} et délivre donc, en sortie, d'une part une estimation des données source et d'autre part des données d'entrée et des données de sortie à la deuxième étape de décodage de deuxième niveau 422 DC _{N2 2} .

En particulier, on note que chaque module de décodage met en œuvre un code de base auto-dual, susceptible d'être représenté par une matrice génératrice comprenant, sous sa forme systématique, une matrice identité et une matrice de passage de données d'entrée aux données de sortie inversible.

Le fonctionnement de ce décodeur est similaire à celui du codeur décrit ci-dessus. Il n'est donc pas expliqué plus en détails. En particulier, le décodage peut être mis en œuvre en utilisant un algorithme de type « Belief Propagation », selon lequel les données reçues sont celles du mot de code reçu c = (x, r), éventuellement bruité, sous forme d'un vecteur de probabilités ou de métriques (par exemple de type logarithme de rapport de vraisemblance ou LLR: Log (~~))· Les valeurs de ce vecteur associées aux variables d'entrée et de sorties du graphe de Tanner sont propagées entre les nœuds du graphe, qui sont les codes de base de la structure.

5.2 Construction et mise en œuvre du code de Golay (24, 12, 8) On présente désormais, en relation avec les figures 5A et 5B, la construction et l'utilisation d'un code de Golay (24, 12, 8) sous forme Cortex-Compact selon l'invention.

Le graphe de Tanner représentatif du dispositif de codage illustré en figure 5A comprend : un étage de codage de premier niveau 51, comprenant neuf modules de codage de base notés B0 à B8 ;

un premier étage de codage de deuxième niveau 521, comprenant trois modules de codage de base notés AO à A2 ;

un deuxième étage de codage de deuxième niveau 522, comprenant trois modules de codage de base notés C0 à C2 ;

- un premier étage de permutation de premier niveau 531 ;

un deuxième étage de permutation de premier niveau 532.

Chaque module de codage de base met en œuvre un code de Hamming (8,4,4), suivi d'une permutation locale prenant par exemple en entrée un paquet de quatre bits aux positions d'indice {0,1,2,3), et délivrant en sortie ces mêmes bits aux positions d'indice {0,2,1,3) respectivement. On note qu'une autre permutation locale pourrait être mise en œuvre, comme la permutation locale prenant en entrée un paquet de quatre bits aux positions d'indice {0,1,2,3), et délivrant en sortie ces mêmes bits aux positions d'indice {0,3,1,2) respectivement.

Par ailleurs, les douze bits d'information (source), notés x ₀ à x _llt sont associés à des variables d'entrée du graphe de Tanner, et les douze bits de redondance, notés r ₀ à r _l sont associés à des variables de sortie du graphe de Tanner.

Les bits d'information entrent par paquets de quatre bits sur le premier étage de permutation de premier niveau 531. Le premier étage de permutation de premier niveau 531 est donc connecté à des variables d'entrée associées à un premier ensemble des données source et de redondance, ici les bits d'information x ₀ à x _l . Le premier étage de permutation de premier niveau 531 est également connecté, en entrée, aux entrées et aux sorties du premier étage de codage de deuxième niveau 521. Plus précisément, chacun des trois modules de codage de base AO, Al, A2 du premier étage de codage de deuxième niveau 521 reçoit en entrée un paquet de quatre bits, notés respectivement d ₀ à d ₃ , d ₄ à d ₇ , et d ₈ à d _llt et délivre en sortie un paquet de quatre bits, notés respectivement f ₀ à f ₃ , f ₄ à f ₇ , et f ₈ à / ₁₁ conformément au code de base de Hamming (8, 4, 4). Chaque paquet de quatre bits f ₀ à f ₃ , f ₄ à f ₇ , et f ₈ à f _llt subit une permutation locale {0,1,2,3)→ {0,2,1,3), comme illustré en figure 5A. Le premier étage de permutation de premier niveau 531 est donc connecté, en entrée, aux 12 bits d'information x ₀ à x _l et à 24 bits internes d ₀ à d _l et f ₀ à f _l associés à des variables internes. Selon cet exemple, on dispose donc d'un module de codage de base pour chaque paquet de quatre bits associés à des variables d'entrée. Le premier étage de permutation de premier niveau 531 met en œuvre une permutation 4-cyclique de longueur l = 36, telle que, en notant / ^' la position d'un bit en entrée et π ₀ (ί) la position de ce même bit en sortie, on a :

i≡ 0 (mod 4) : π ₀ (ί) = i— 2 (mod l)

i≡ 1 (mod 4) : π ₀ (ί) = i— 2 (mod l)

i≡ 2 (mod 4) : π ₀ (ί) = i + 2 (mod l)

i≡ 3 (mod 4) : π ₀ (ί) = i + 2 (mod l)

En variante, d'autres permutations pourraient être mises en œuvre, comme des permutations affines associant à un bit/symbole d'entrée à la position i, un même bit/symbole à la position a * i + b, avec a un nombre premier avec la longueur (ou l'ordre) l de la permutation mise en œuvre par le premier ou le deuxième étage de permutation de premier niveau, et b un entier tel que b < a.

De ce fait, le premier étage de permutation de premier niveau 531 délivre les 12 bits d'information x ₀ à x _l et les 24 bits internes d ₀ à d _l et f ₀ à f _l permutés à l'étage de codage de premier niveau.

Plus précisément, chaque module de codage de base de l'étage de codage de premier niveau 531 reçoit deux bits d'information, et deux bits d'entrée ou de sortie d'un module de codage de base du premier étage de codage de deuxième niveau 521, par l'intermédiaire du premier étage de permutation de premier niveau 531.

Par exemple, le premier module de codage de base B0 reçoit les bits d'entrée d ₀ et d _lt et les bits de sortie f ₉ et f _llt le deuxième module de codage de base Bl reçoit les bits de sortie f ₀ et f ₂ , et les bits d'information x ₂ et x ₃ , le troisième module de codage de base B2 reçoit les bits d'entrée d ₂ et d ₃ et les bits d'information x ₄ et x ₅ , le quatrième module de codage de base B3 reçoit les bits de sortie f _x et f ₃ , et les bits d'entrée d ₄ et d ₅ , le cinquième module de codage de base B4 reçoit les bits de sortie f ₄ et f ₆ , et les bits d'information x ₆ et x ₇ , le sixième module de codage de base B5 reçoit les bits d'entrée d ₆ et d ₇ , et les bits d'information x ₈ et x ₉ , le septième module de codage de base B6 reçoit les bits de sortie f ₅ et f ₇ , et les bits d'entrée d ₈ et d ₉ , le huitième module de codage de base B7 reçoit les bits d'information x ₁₀ et x _llt le les bits de sortie f ₈ et f _w , et le neuvième module de codage de base B8 reçoit les bits d'information x ₀ et x _lt et les bits d'entrée d ₁₀ et d _l .

Chaque module de codage de base de l'étage de codage de premier niveau 51 reçoit en entrée un paquet de quatre bits et délivre en sortie un paquet de quatre bits conformément au code de base de Hamming (8,4,4). Les bits en sortie du module de codage subissent une permutation locale, dans un module de permutation locale non illustré, selon la permutation {0,1,2,3}→ {0,2,1,3}. Les sorties de l'étage de codage de premier niveau 51 sont connectées au deuxième étage de permutation de premier niveau 532. Ce deuxième étage de permutation de premier niveau 532 met en œuvre une permutation π ₁ inverse à la permutation mise en œuvre par le premier étage de permutation de premier niveau 531, telle que π ₁ = π ₀ ^_1 . Ce deuxième étage de permutation de premier niveau 532 est connecté, en sortie, d'une part à des variables de sortie associées à un deuxième ensemble des données source et de redondance, ici les bits de redondance r ₀ à r _llt et d'autre part aux entrées et aux sorties du deuxième étage de codage de deuxième niveau 522. Plus précisément, chacun des trois modules de codage de base CO, Cl, C2 du deuxième étage de codage de deuxième niveau 522 reçoit en entrée un paquet de quatre bits, notés respectivement d ₁₂ à d ₁₅ , d ₁₆ à d ₁₉ , et d ₂₀ à d ₂₃ , et délivre en sortie un paquet de quatre bits, notés respectivement f ₁₂ à f ₁₅ , f ₁₆ à f ₁₉ , et f ₂₀ à f ₂₃ , conformément au code de base de Hamming (8,4,4). Chaque paquet de quatre bits f ₁₂ à f ₁₅ , f ₁₆ à f ₁₉ , et f ₂₀ à f ₂₃ subit une permutation locale {0,1,2,3)→ {0,2,1,3). Le deuxième étage de permutation de premier niveau 532 est donc connecté, en sortie, aux 12 bits de redondance r ₀ à r _l et à 24 bits internes d ₁₂ à d ₂₃ et f ₁₂ à f ₂₃ associés à des variables internes.

En particulier, si l'on considère le module de codage de base B8 par exemple, les variables internes associées aux bits d ₁₀ , d _llt d ₂₂ et d ₂₃ sont liées par des contraintes aux bits d'information x ₀ et x ₁ et aux bits de redondance r ₀ et r _lt et disposent donc d'informations relatives au canal, ce qui permet de favoriser le décodage.

A partir d'un tel graphe de Tanner, il est possible d'écrire un système d'équations tenant compte des contraintes que doivent respecter les bits d'information et de redondance d'un mot pour être un mot du code global.

En particulier, on rappelle qu'un code global peut être représenté par une telle structure si le pré-calcul du déterminant de la matrice génératrice obtenue à partir du système d'équations réunissant toutes les équations booléennes de la structure est non-nul.

Ainsi, à partir du graphe de Tanner illustré en figure 5A, il est possible d'écrire et de résoudre un système de 60 équations (4 équations obtenues à partir de chaque module de codage de base), dans lequel les inconnues sont les données associées aux variables internes et les données de redondance

Par exemple, les équations obtenues à partir du module de codage de base AO du premier étage de codage de deuxième niveau sont telles que : d ₁ + d ₂ + d ₃ + f ₀ = 0, d ₀ + d ₂ + d ₃ + f ₂ = 0, d ₀ + d ₁ + d ₃ + f = 0 et d ₀ + d ₁ + d ₂ + f ₃ = 0. Les équations obtenues à partir du module de codage de base BO de l'étage de codage de premier niveau sont telles que : f ₉ + n + f ₂₁ + x ₃ = 0, f ₉ + n + f ₂₃ + x ₂ = 0, d ₁₂ + f ₁₁ + x ₂ + x ₃ = 0 et d ₁₃ + f ₉ + x ₂ + x ₃ = 0. Les équations obtenues à partir du module de codage de base CO du deuxième étage de codage de deuxième niveau sont telles que : d _lt + d ₁₃ + d ₁₅ + f ₁₂ = 0, d _lt + d ₁₂ + d ₁₅ + f ₁₄ = 0, d ₁₂ + d ₁₃ + d ₁₅ + f ₁₃ = 0 et d _l + d ₁₂ + d ₁₃ + f ₁₅ = 0.

On peut ainsi « pré-calculer » une matrice de passage permettant de déterminer les bits de redondance à partir des bits d'information (également appelée « matrice de transfert »).

Lors de la construction du code, on définit par exemple le code de base que l'on souhaite utiliser dans les modules de codage de base, ce qui permet de définir le nombre de variables internes. On note que plus le nombre de variables internes est élevé, plus le code global obtenu est puissant. En ajoutant à ces variables internes le nombre de variables d'entrée associées à des données source, on obtient le nombre d'entrées de l'étage de codage de premier niveau. On peut ainsi définir le nombre de modules de codage de base à utiliser dans l'étage de codage de premier niveau.

La matrice génératrice du code de Golay obtenue à partir du graphe de la figure 5A, composée d'une matrice identité et de la matrice de passage des données source aux données de redondance, est illustrée en figure 5B, où les ronds blancs correspondent à 0 et les ronds noirs correspondent à 1.

5.3 Construction et mise en œuvre d'un code auto-dual (72, 36, 12)

On présente désormais, en relation avec les figures 6A et 6B, la construction et l'utilisation d'un code auto-dual (72, 36, 12) de type-ll sous forme Cortex-Compact selon l'invention.

Le graphe de Tanner représentatif du dispositif de codage illustré en figure 6A comprend : un étage de codage de premier niveau 61, comprenant 27 modules de codage de base notés BO à B26 ;

un premier étage de codage de deuxième niveau 621, comprenant 9 modules de codage de base notés AO à A8 ;

- un deuxième étage de codage de deuxième niveau 622, comprenant 9 modules de codage de base notés CO à C8 ;

un premier étage de permutation de premier niveau 631 ;

un deuxième étage de permutation de premier niveau 632.

Selon l'exemple illustré, chaque module de codage de base met en œuvre un code de Hamming (8,4,4), suivi :

pour les modules de codage de base du premier étage de codage de deuxième niveau 621, pas de permutation locale (ou une permutation locale identité ({0,1,2,3)→ {0,1,2,3}),

pour les modules de codage de base de l'étage de codage de premier niveau 61, d'une permutation locale prenant en entrée un paquet de quatre bits aux positions d'indice {0,1,2,3), et délivrant en sortie ces mêmes bits aux positions d'indice {0,1,3,2) respectivement ({0,1,2,3)→ {0,1,3,2)),

pour les modules de codage de base du deuxième étage de codage de deuxième niveau 622, d'une permutation locale prenant en entrée un paquet de quatre bits aux positions d'indice {0,1,2,3), et délivrant en sortie ces mêmes bits aux positions d'indice {0,2,1,3) respectivement ({0,1,2,3)→ {0,2,1,3)).

Selon un deuxième exemple, non illustré, chaque module de codage de base met en œuvre un code de Hamming (8,4,4), suivi d'une permutation locale prenant en entrée un paquet de quatre bits aux positions d'indice {0,1,2,3), et délivrant en sortie ces mêmes bits aux positions d'indice {3,0,2,1) respectivement.

Par ailleurs, les 36 bits d'information (source), notés x ₀ à x ₃₅ , sont associés à des variables d'entrée du graphe de Tanner, et les 36 bits de redondance, notés r ₀ à r ₃₅ sont associés à des variables de sortie du graphe de Tanner.

Les bits d'information entrent par paquets de quatre bits sur le premier étage de permutation de premier niveau 631. Le premier étage de permutation de premier niveau 631 est également connecté, en entrée, aux entrées et aux sorties du premier étage de codage de deuxième niveau 621. Le premier étage de permutation de premier niveau 631 est donc connecté, en entrée, aux 36 bits d'information et à 72 bits internes.

Selon l'exemple illustré, le premier étage de permutation de premier niveau 631 met en œuvre une permutation 4-cyclique, telle que, en notant / ^' la position d'un bit en entrée et π ₀ (ί) la position de ce même bit en sortie :

( π ₀ (ί) = 5 + i (mod 108) si i≡ 0(mod 4)

7T ₀ (j) = -18 + i (mod 108) si i≡ l(mod 4)

π ₀ (ί) = 18 + i (mod 108) si i≡ 2(mod 4)

7T ₀ (j) = -5 + i (mod 108) si i≡ 3(mod 4)

Les bits obtenus après permutations sont délivrés à l'étage de codage de premier niveau

61.

Selon le deuxième exemple, non illustré, le premier étage de permutation de premier niveau 631 met en œuvre une permutation affine de longueur l = 108, telle que, en notant / ^' la position d'un bit en entrée et π ₀ (ί) la position de ce même bit en sortie, on a n ₀ (i) = 7i(mod 108), et délivre les bits permutés à l'étage de codage de premier niveau 61.

Selon l'exemple illustré, chaque module de codage de base de l'étage de codage de premier niveau 61 reçoit en entrée un paquet de quatre bits et délivre en sortie un paquet de quatre bits conformément au code de base de Hamming (8,4,4), après permutation locale {0,1,2,3)→ {0,1,3,2). Les sorties de l'étage de codage de premier niveau 61 sont connectées au deuxième étage de permutation de premier niveau 632. Ce deuxième étage de permutation de premier niveau 632 met en œuvre une permutation π ₁ inverse à la permutation mise en œuvre par le premier étage de permutation de premier niveau 631, telle que π ₁ = π ₀ ^_1 . Ce deuxième étage de permutation de premier niveau 532 est connecté, en sortie, d'une part aux bits de redondance r ₀ à r ₃₅ , et d'autre part aux entrées et aux sorties du deuxième étage de codage de deuxième niveau 622.

A partir d'un tel graphe de Tanner, il est possible d'écrire un système d'équations tenant compte des contraintes que doivent respecter les bits d'information et de redondance d'un mot pour être un mot du code global.

Ainsi, à partir du graphe de Tanner illustré en figure 6A, il est possible d'écrire et de résoudre un système de 180 équations (4 équations par module de codage de base).

La matrice génératrice du code auto-dual (72,36,12) de type-ll obtenue à partir du graphe de la figure 6A, composée d'une matrice identité et de la matrice de passage des données source aux données de redondance, est illustrée en figure 6B, où les ronds blancs correspondent à 0 et les ronds noirs correspondent à 1.