Le développement de la théorie de l'information par Claude Shannon en 1948 a donné naissance à la théorie des codes. Dans la thèse, nous nous sommes concentrés sur l’aspect pratique de l’utilisation des codes d’effacement.
Notions de théorie de l’information et concept de canal
Théorie de l’information
La connaissance du canal nous donne ainsi la loi de transition définie par la probabilité de chaque couple de valeurs d'entrée et de sortie, Y et X. On considère alors l'information mutuelle des variables X et Y, notée I(X,Y), qui représente les informations qui peuvent être obtenues concernant
Exemple du canal binaire symétrique
La capacité du canal binaire symétrique est donc égale à 1 si la probabilité d'erreur est nulle. Lorsque la fonction d'entropie H(.) atteint son maximum à 0,5, 1, la capacité d'un canal binaire symétrique de paramètre 0,5 est nulle.
Le cas des canaux à effacements
Le canal binaire à effacements
EXEMPLE DE CANAUX D'EFFACEMENT 25 On constate que, pour une probabilité d'erreur donnée, la capacité d'un canal binaire d'effacement est supérieure à celle d'un canal binaire symétrique, qui est égale à (1−H(p)), puisque. En effet, sur un BEC la localisation des délétions est connue et il ne reste plus qu'à les corriger, alors que sur un canal binaire symétrique la position des erreurs est inconnue, ce qui complique la tâche de correction.
Le canal à effacements de paquets
Exemples pratiques de canaux à effacements
Le problème de perte de paquets peut être résolu en utilisant une requête de répétition automatique ou un système de type « Automatic Repeat reQuest » (ARQ), qui consiste à demander par un canal retour la retransmission des paquets manquants (par exemple : le protocole TCP) . Il permet également d'augmenter le nombre d'unités de stockage fournissant des informations pertinentes pour la récupération d'un ensemble de données.
Codes correcteurs d’erreurs
Notions relatives aux codes
La distance utilisée est la distance de Hamming dérivée de la fonction de poids de Hamming. Définition La distance minimale d'un code linéaire, notée edmin, est la plus petite distance de Hamming qui existe entre deux mots de code différents.
Codage pour le canal à effacements
En fait, cela nous donne une limite sur le nombre de correctifs fournis par le code. Le code correcteur de distance minimale dmin pourra toujours corriger sidmin≥2t+e+1, où e est le nombre de suppressions et t est le nombre d'erreurs.
Codage par paquets
On considérera donc désormais que les paquets d'un flux à protéger ont tous la même taille. Lorsque nous utilisons un code avec une longueur et une taille de symbole limitées (comme les codes de Reed-Solomon, voir section 2.4), nous utiliserons la troisième solution.
Codes Reed-Solomon
- Codes Reed-Solomon sur matrice de Vandermonde
- Codes Maximum Distance Séparable (MDS) sur matrice de Cauchy 35
- Représentation des codes LDPC
- Encodage des codes LDPC
- Décodage des codes LDPC
- Codes LDPC définis par une matrice de parité avec structure trian-
- Quelques outils associés aux codes LDPC
Il existe deux représentations courantes des codes LDPC : le graphe biparti et la matrice de parité. La matrice d'adjacence du graphe de Tanner d'un code LDPC est en fait sa matrice de parité.
Codes sans rendement
Codes LT
Lorsqu'ils sont décodés avec un décodeur itératif, les codes LT sont des codes asymptotiquement optimaux, quel que soit le canal d'effacement considéré. On peut observer que les codes LT sont en fait des codes LDGM irréguliers non systématiques dont les lignes matricielles génératrices sont réalisées en mouvement et ont une échelle moyenne proportionnelle à log(k).
Codes Raptor
Le décodage des codes Raptor consiste à récupérer les symboles K originaux à partir d'un ensemble de symboles codés. Cette étude confirme l'avantage de complexité des codes Raptor par rapport aux codes LT et le fait que le temps de décodage dépend linéairement de la taille du code.
Métriques de capacités de correction
Distance à la capacité
En revanche, les méthodes basées sur la simulation s'appuieront sur des mesures d'un ensemble de résultats expérimentaux, à partir desquels le comportement moyen du système sera déduit. Nous présenterons d’abord les métriques les plus couramment utilisées pour évaluer les codes de balayage, puis présenterons les méthodes permettant d’obtenir ces métriques.
Probabilité d’erreur de décodage
Dans le cas général, cette frontière n'est pas aussi nette et les courbes montrant la probabilité d'une erreur de décodage en fonction de la qualité du canal ont une forme particulière. Dans cette zone, la probabilité d'erreur de bloc évolue rapidement depuis des valeurs faibles du plancher d'erreur jusqu'à la valeur maximale de 1.
Ratio d’inefficacité de décodage
Probabilité d'erreur de bloc : La probabilité que le décodage échoue est appelée probabilité d'erreur de bloc ou BER (« Block Error Rate »). Terminologie associée aux courbes de probabilité d'erreur : Pour les codes parfaits, la probabilité d'erreur de décodage dérive directement de la taille du code et du nombre de symboles reçus.
Métriques de complexité algorithmique
Complexité théorique
Cette complexité exprime le nombre d'opérations effectuées par l'algorithme en fonction de la taille des données d'entrée. La complexité théorique nous donne un aperçu de la manière dont la complexité d'un algorithme varie en fonction de la taille de l'entrée.
Vitesse et débit
Ceci est réalisé en décomposant l’algorithme en opérations de base telles que l’addition et la multiplication. La fonction de coût d’un algorithme est alors comparée à une fonction usuelle dont le comportement est connu au fur et à mesure de sa croissance.
Consommation mémoire
Cela constitue donc une première évaluation du coût de l’algorithme, mais la plupart du temps elle ne suffira pas à déterminer si un algorithme de codage ou de décodage est plus rapide qu’un autre. De plus, les systèmes à environnement limité tels que les terminaux mobiles ont une capacité mémoire réduite qui doit souvent être partagée avec d'autres applications (par exemple, décodage d'un flux vidéo).
Méthodes d’évaluation de performances
Méthodes analytiques
Même si les capacités RAM des machines actuelles augmentent considérablement, les codes AL-FEC fonctionnent sur des quantités de données qui peuvent être très importantes (plusieurs Go pour les fichiers vidéo). Si la consommation totale de mémoire est importante, les architectures actuelles disposent d'une mémoire hiérarchique dont les capacités et les temps d'accès varient de plusieurs ordres de grandeur.
Simulations
A partir de cette technique il est possible de construire une méthode d'évaluation des performances d'un code. L'avantage de ce type de transmission est que quel que soit le modèle de perte de canal, du point de vue du code, la distribution sera équivalente à un modèle de perte indépendant.
Conclusions
Il a été démontré [86][76] que le décodage ML des codes LDPC permet une amélioration significative des capacités de débogage. Ce travail aboutit aux mêmes conclusions : le décodage hybride IT/ML des codes LDPC permet d’obtenir d’excellentes capacités de débogage tout en conservant une complexité réduite.
Décodeur hybride IT/ML
Principes
En fait, le décodage ML équivaut à résoudre un système linéaire par une méthode de type élimination gaussienne (GE) ; la complexité du décodage devient donc cubique. Pour combiner les avantages des deux types de décodage, nous proposons une approche hybride : le décodage itératif réduira la complexité globale du décodage, tandis que le décodage ML permettra d'obtenir une capacité de correction plus élevée.
Résolution du système linéaire du décodage ML
Décodage ML sur la matrice génératrice : Soit X (ou Y) un vecteur contenant k symboles sources (ou n−k symboles de parité), et soit G la matrice génératrice de code. Soit Xe(or.Ye) un vecteur dont les coordonnées sont les symboles d'origine (ou de parité) manquants.
Implémentation et optimisations
Simplification du système permis par le décodage IT
Pour de faibles taux de perte, le décodage itératif est toujours capable de décoder et dans ce cas la taille du système simplifié est nulle. Ainsi, le décodage itératif peut réduire considérablement la taille du système que le décodage ML devra résoudre et ainsi réduire sa complexité.
Performances
Conditions expérimentales
Les performances du décodage hybride IT/ML seront évaluées sur un code ladder LDPC à l'aide de simulations de type Monte-Carlo (voir Section 3.4.2). Nous utilisons le codec C++ LDPC, version 2.1 [118] auquel nous avons ajouté le support du décodage hybride IT/ML.
Capacités de correction
Nous avons exprimé cette probabilité en fonction du taux de perte sur la figure 4.4(a) et en fonction du nombre de symboles reçus sur la figure 4.4(b), pour les codes trap LDPC et les codes Raptor5. La figure 4.4(a) montre que le stade LDPC est proche de l'idéal avec une forte pente dans la région « cascade ».
Vitesse et débit de décodage
Travaux relatifs
Conclusions
Nous avons souligné dans le chapitre précédent que le décodage par maximum de vraisemblance (ML) permet d'améliorer significativement les capacités de correction de ces codes. En effet, nous montrons qu'en augmentant la valeur de N1, la capacité de correction des codes d'escalier LDPC décodés en ML se rapproche de l'optimum.
Influence du paramètre N1 sur les capacités de correction
Capacités de correction du décodage ML
INFLUENCE DU PARAMÈTRE N1 SUR LES CAPACITÉS DE CORRECTION81 d'inefficacité, pour la plupart des rendements considérés. La figure 5.3 montre la probabilité d'échec du décodage en fonction du taux d'effacement pour deux retours R et plusieurs valeurs de N1.
Capacités de correction du décodage itératif
5.3 – Probabilité d'échec du décodage en fonction du taux d'effacement pour le décodage ML (dimension du codec = 1 000). La probabilité d'échec du décodage en fonction du taux d'effacement est représentée sur la figure 5.6 pour plusieurs valeurs de N1.
Influence du paramètre N1 sur la vitesse de décodage
Sans surprise, nous observons que la valeur de N1 affecte significativement la complexité du décodage. La densité de la matrice sur laquelle sera effectué le décodage ML sera d'autant plus importante que N1 est grande, augmentant la complexité.
Conclusions
Matrices et polynômes
Nous allons donc commencer par présenter les objets et propriétés qui seront utilisés dans la suite de la discussion. Pour rendre cette collection stable par rapport au produit scalaire, le produit de 2 éléments de F2[x] sera tronqué en prenant le résultat moduloxn+1.
Construction du code
Structure globale du code
On remarque qu'à partir de la matrice M on peut déduire une relation entre la longueur du code, sa taille et la largeur de la bande. Ce résultat va nous permettre de construire des matrices génératrices de bandes prenant en compte les contraintes sur les colonnes de la matrice de parité.
Construction des matrices
Les expériences ont également montré que la manière dont les polynômes de la matrice sont permutés n'a qu'une influence limitée sur les performances du code. Il est alors possible d'ajuster le degré des lignes pour obtenir, ou du moins se rapprocher, une certaine répartition.
Optimisations
CONSTRUCTION DU CODE 93 De manière générale, il est préférable d'introduire de la diversité dans la matrice en entrelaçant les différents polynômes. En revanche, si l'on suppose une bande de largeur finie, l'hypothèse de cycles de longueur infinie, nécessaires à l'évolution de la densité, n'est plus valable.
Analyse théorique
Capacités de correction théorique
Studholme et Blake ont étudié l'influence de la bande passante sur des matrices binaires arbitraires. Le pouvoir de correction en décodage itératif sera donc également influencé par la bande passante.
Complexité théorique
Résultats de simulation
Capacités de correction
Avec une bande passante de B = 200, les bandes LDPC ont une inefficacité de décodage itératif essentiellement égale à celle des échelles LDPC, alors qu'elles sont légèrement moins bonnes en décodage ML. Ces résultats montrent que les LDPC-Band ont une capacité de correction plus faible, mais toujours très proche de celle des échelles LDPC, bien qu'elles soient plus limitées.
Vitesses de décodage
RÉSULTATS DE LA SIMULATION 97 bande passante nettement inférieure, les codes Windowed Erasure sont meilleurs que les codes LDPC-Band. Ceci est probablement dû au manque de contraintes associées à la matrice de parité LDPC-Band, qui permet une distribution véritablement aléatoire des entrées de bande.
Conclusions
En termes de capacités de correction, LDPC-Band est légèrement pire que les codes pièges LDPC sous décodage informatique. Lorsque le décodage ML est utilisé, la bande LDPC ressemble à l'étage LDPC, proche de la capacité du canal, avec un léger avantage pour l'étage LDPC.
Introduction
Une autre famille de codes LDPC à matrice structurée est constituée par les codes LDPC quasi-cycliques. En particulier, il a été montré [40] que cette approche permet de construire des codes LDPC avec une longueur de cycle minimale élevée, améliorant ainsi les capacités de correction de ces codes.
Codes LDPC quasi-cycliques
Codes quasi-cycliques
Dans ce chapitre, nous présentons une analyse préliminaire des codes LDPC-QC équipés d'un décodeur hybride IT/ML pour le canal d'effacement. Nous commencerons par présenter les codes LDPC-QC et les propriétés associées à ces codes, puis nous présenterons les résultats sur les capacités de correction obtenues grâce aux simulations.
Codes LDPC-QC de type I
A partir de ces informations, et grâce à un choix judicieux des coefficients de la matrice de base, il est possible de construire des codes dont la longueur de cycle est la plus longue possible. La matrice de base que nous utilisons est obtenue à partir d'une matrice d'un code piège LDPC, en remplaçant les entrées nulles par −1 et les entrées non nulles par un entier contenu dans [0.qmax].
Evaluation des capacités de correction
La figure 7.4 montre le taux d'inefficacité du décodage itératif en fonction de la taille du code. Le taux d'inefficacité du décodage ML en fonction de la dimension du code est illustré à la figure 7.5.
Evaluation de la complexité du décodage
Vitesse de décodage
Analyse détaillée de la complexité de la résolution du système
7.8 – Nombre moyen d'opérations XOR sur les symboles, en fonction de la taille du code, lors du décodage ML (R=2/3). Le nombre d’opérations sur les lignes et la densité matricielle sont deux quantités fortement liées.
Conclusions
Motivations
Comme le souligne la section 2.6, certaines applications peuvent nécessiter un grand nombre de symboles redondants. Pour répondre au besoin d'un codage à faible performance capable de produire une redondance à la volée, nous proposons une alternative aux schémas de codage précédents.
Codes à faible rendement
C'est le cas par exemple pour des applications de type carrousel [5] ou pour des transmissions sur des canaux dont la probabilité de suppression ne peut être connue à l'avance. Ce nouveau code est basé sur un code escalier LDPC [99] transformé en code LDPC généralisé.
Codes LDPC généralisés
SCHÉMA DE CODAGE PROPOSÉ 113 Cette généralisation s'obtient en tenant compte des limites qu'elle représente.
Schéma de codage proposé
Les premiers nœuds de symboles représentent soit les symboles sources, soit le symbole de débordement de la ligne précédente p1. Nous codons la séquence des premiers symboles de la ligne en utilisant le code systématique de Reed-Solomon.
Conception du code
Construire le code étendu nécessite de définir la répartition du nombre de symboles supplémentaires par nœud de contrainte. 8.3 - Graphe du code GLDPC avec répartition uniforme des symboles supplémentaires Une répartition irrégulière est telle que le nombre de symboles supplémentaires varie d'un nœud de contrainte à l'autre.
Optimisation par évolution de densité
Considérons un nœud de contrainte m de degré k+1, et soit e(m) =e le nombre de symboles supplémentaires redondants dem. L'axe horizontal inférieur montre le nombre moyen de symboles supplémentaires redondants par ligne (¯f), tandis que l'axe horizontal supérieur montre le rendement du code étendu correspondant (R).
Résultats des simulations
8.7 – Inefficacité moyenne en fonction du nombre moyen de symboles supplémentaires par ligne dans le cas d'une répartition uniforme. nombre moyen de symboles supplémentaires par ligne) Taux de code étendu. 8.8 – Le seuil de probabilité de suppression en fonction du nombre moyen de symboles supplémentaires par ligne dans le cas d'une répartition uniforme.
Conclusions
Plus précisément, notre système est capable de détecter des dommages aléatoires à des objets avec une probabilité proche de 1 avec un coût supplémentaire quasiment nul en termes de calcul. Dans le cas de transfert d'objets volumineux, le temps de calcul associé à la signature est faible comparé au temps de calcul de hachage d'objet.
Analyse du problème et observations
Modèle d’attaque
Phénomène de propagation des corruptions
Pour un code LDPC de matrice de parité H, cela signifie qu'un vecteur décodé w est tel que Hw=0. Ainsi, une corruption réussie peut être considérée comme l’ajout du mot de code, appelé code de corruption, au code transmis.
Premières conclusions
9.1 – Nombre de corruptions dans la sortie du décodeur (intervalles de confiance min/moy/max/90 %) en fonction du nombre de symboles endommagés lors de la transmission. Cependant, certaines expériences montrent très peu de symboles corrompus, ce qui signifie que les symboles corrompus n'ont été utilisés que pour reconstruire un petit nombre de symboles.
Notre solution : VeriFEC
Principes
Détails
PERFORMANCE CONTRE LES ATTAQUES ALÉATOIRES 131 symboles sources avec un PRNG initialisé avec un seedgraine_veri f_prel.
Performances contre les attaques aléatoires
- Dépendance vis-à-vis du ratio de vérification
- Gains en calcul
- Dépendance vis-à-vis de la dimension et du rendement du code . 135
- Prévention des attaques simples par extension de l’ensemble V des
- Prévention des attaques par mot de poids faible
9.5 - Probabilité de détection de pré-vérification par rapport à la taille du code (R=2/3). 9.7 - Probabilité de non-détection (PND) de pré-vérification en fonction du poids de Hamming du mot de passe de corruption pour différents ratios de vérification (n=30 000, k=20 000).
Travaux relatifs
L'idée de détecter la corruption basée sur le calcul d'un hachage partiel de l'objet a été présentée dans [30]. Grâce à cette fonction de hachage homomorphe, le récepteur peut calculer le hachage de n'importe quel symbole codé à partir des valeurs de hachage des symboles sources.
Généralisation aux codes MDS
Il peut donc vérifier l'intégrité de tout symbole reçu uniquement d'un ensemble de khashes à sa place. Cependant, il convient de noter que l'avantage d'un système VeriFEC typique avec des codes MDS peut être moins important qu'avec des codes à grande vitesse tels que l'échelle LDPC.
Conclusions
Introduction
Il est donc naturel d’essayer de combiner le système de cryptage avec le code d’effacement afin de réduire la complexité globale du système. La sécurité de la proposition reposera sur un système de « partage de secret » (voir section 10.2.2).
Conception du système proposé
- Objectifs
- Mécanisme de “secret sharing”
- Chiffrement partiel
- Gain théorique
En 1981, McEliece observa [72] que le système d'échange secret de Shamir était en réalité un cas particulier des codes de Reed-Solomon. Nous suggérons d'utiliser la fonctionnalité « partage secret » du code Reed-Solomon pour restreindre l'accès au contenu encodé.
Analyse de la sécurité du système
Attaques par "force brute"
Attaques avec texte clair partiellement connu
Connaître certains symboles sources réduira le nombre de variables du système linéaire à résoudre. Encore une fois, nous pouvons utiliser le paramètre pour adapter la sécurité du système à la quantité d'informations prévisibles dans le contenu et à la sécurité du système contre les attaques par force brute avec du texte clair partiellement connu.
Travaux relatifs
Sinon, le décodage n’est pas directement possible, mais la complexité d’une attaque par force brute sera réduite.
Conclusions
Les plateformes informatiques peer-to-peer peuvent être sujettes à un grand nombre de bugs et d’attaques. Boscila et al [15] ont présenté une nouvelle méthode ABFT pour la multiplication matricielle sur les plateformes de calcul haute performance (HPC).
ABFT appliquée aux calculs hautes performances
Un systèmeABFT consistant pour la multiplication matricielle
Dans ce chapitre, nous proposons une généralisation d'une approche dite de « points de contrôle sans disque » pour la tolérance aux pannes dans les systèmes informatiques hautes performances. Notre proposition de « contrôle sans disque » basée sur les codes de Reed-Solomon est capable de tolérer des erreurs malveillantes, mais se limite aux opérations sur des corps finis.
Certification de résultat
Limitations
Généralisation et extension aux réseaux P2P
Codes linéaires par bloc et multiplication matricielle
Le codage proposé dans [15] peut être facilement généralisé à tout code linéaire dont le corps fini est compatible avec les opérations arithmétiques des matrices. Dans la suite nous considérerons uniquement le codage des colonnes avec la matriceCC, où le codage des lignes avec la matriceCR est analogue.
ABFT reposant sur les codes linéaires
Les séparables sont tels que dmin=r+1 : leur distance minimale est la distance maximale relative au nombre de symboles redondants. Grâce à la structure algébrique des codes linéaires, le produit (ainsi que la somme) de deux matrices codées est toujours une matrice codée cohérente par rapport au code.
Adaptation de l’ABFT aux plate-formes P2P
Les matrices de contrôle de parité etCR sont remplacées par les matrices de génération du code linéaire choisi.
Codage LDPC pour plate-formes P2P non malicieuses
CODAGE LDPC POUR PLATEFORMES P2P NON MALVEILLANTES 157 valeur, perte d'informations ainsi que pour certifier les résultats intermédiaires. CODAGE REET-SOLOMON POUR PLATEFORMES P2P MALVEILLANTES159 pour empêcher l’algorithme de converger, voire lui permettre de diverger.
Codage Reed-Solomon pour plate-formes P2P malicieuses
Conclusions et travaux futurs
- Décodage hybride IT/ML
- Adaptation des codes LDPC-staircase au décodage hybride IT/ML 164
- Codes LDPC-QC
- Codes G-LDPC, ou LDPC Généralisés
Les résultats présentés montrent que ces codes ont des capacités de correction très proches de celles des codes Raptor. La structure de bande du système à résoudre permettra une réduction de la complexité du décodage ML.
Codes à effacements et primitives cryptographiques
VeriFEC
Le système résultant, VeriFEC, est capable de détecter la plupart des corruptions arbitraires avec une très faible surcharge (la vérification de 5 % de l'objet déchiffré permet de détecter 99,8 % des attaques), tandis qu'une vérification supplémentaire permet de certifier l'intégrité à 100 % de l'objet déchiffré. l'objet décodé. Ce travail a grandement bénéficié des échanges que nous avons eus avec Valentin Savin du CEA-LETI, Philippe Gaborit de l'équipe PI2C de l'Université de Limoges, Nicolas Sendrier et Jean-Pierre Tillich de l'équipe SECRET de l'INRIA.
Chiffrement et code Reed-Solomon
Le problème des attaques intelligentes a été abordé, et nous avons montré que des contre-mesures permettaient de les réduire dans le cas d'attaques aléatoires. Travaux futurs : les travaux futurs se concentreront sur l'assouplissement des restrictions qui doivent être ajoutées au système pour se protéger contre les attaques intelligentes.
Calcul distribué tolérant aux fautes sur plateforme P2P
Tout d’abord, nous avons envisagé d’ajouter une fonctionnalité de contrôle d’intégrité au code LDPC-Staircase. De plus, il devrait être possible de généraliser ce système à d'autres codes et à d'autres types de canaux, tels que les canaux erreur-valeur.
Le “mot de la fin”
Quasicyclic low-density parity-check codes of circulant permutation matrices.IEEE Transactions on Information Theory. Limit on the maximum probability decoding error probability of low density parity check codes.