Worldlex Wiki En théorie du codage , les codes Justesen forment une classe de codes correcteurs d'erreurs qui ont un taux constant, une distance relative constante et une taille d'alphabet constante.
Avant la découverte du code de correction d'erreurs Justesen, aucun code de correction d'erreurs connu ne comportait ces trois paramètres comme une constante.
Par la suite, d'autres codes ECC possédant cette propriété ont été découverts, par exemple les codes expanseurs . Ces codes ont d'importantes applications en informatique , notamment pour la construction d' espaces d'échantillonnage à faible biais .
Les codes Justesen sont dérivés de la concaténation d'un code Reed-Solomon et de l' ensemble Wozencraft .
Les codes Reed-Solomon utilisés permettent d'obtenir un débit constant et une distance relative constante au prix d'une taille d'alphabet linéaire par rapport à la longueur du message.
L' ensemble Wozencraft est une famille de codes qui atteignent un taux constant et une taille d'alphabet constante, mais la distance relative n'est constante que pour la plupart des codes de la famille.
La concaténation des deux codes encode d'abord le message à l'aide du code Reed-Solomon, puis encode chaque symbole du mot de code à l'aide d'un code de l' ensemble Wozencraft – en utilisant un code différent de l'ensemble à chaque position du mot de code.
Cela diffère de la concaténation de codes classique où les codes internes sont identiques pour chaque position. Le code de Justesen peut être construit très efficacement en utilisant uniquement un espace logarithmique .
Définition
Le code Justesen est la concaténation d'un
Plus précisément, la concaténation de ces codes, notée par
Ensuite, nous appliquons chaque code des N codes internes linéaires à chaque coordonnée de ce mot de code pour produire le mot de code final ; c'est-à-dire,
Si l'on se réfère à la définition du code externe et des codes internes linéaires, cette définition du code Justesen prend tout son sens car le mot de code du code externe est un vecteur.
Voici pour le code Justesen, le code externe
Le code externe
Propriété du code Justesen
Les codes linéaires de l'ensemble Wonzencraft ont le taux
Théorème
Laisser
Preuve
Afin de prouver une borne inférieure pour la distance d'un code
nous voulons une limite inférieure pour
Remarquez que si
Supposer
Rappelons que
De plus, si nous avons
La dernière tâche consiste donc maintenant à trouver une borne inférieure pour
Alors
Maintenant, nous voulons estimer
En vertu du théorème d'ensemble de Wozencraft , il y a au plus
Finalement, nous avons
Cela est vrai pour tout arbitraire
Commentaires
Nous souhaitons étudier le « code fortement explicite ». La question est donc de savoir ce qu'est un « code fortement explicite ». En termes simples, pour un code linéaire, la propriété « explicite » est liée à la complexité de la construction de sa matrice génératrice G.
Cela signifie concrètement que nous pouvons calculer la matrice dans un espace logarithmique sans utiliser l'algorithme de force brute pour vérifier qu'un code a une distance donnée satisfaite.
Pour les autres codes non linéaires, nous pouvons considérer la complexité de l'algorithme d'encodage.
Jusqu'à présent, nous pouvons constater que les codes d'ensemble de Wonzencraft et de Reed-Solomon sont fortement explicites. Par conséquent, nous obtenons le résultat suivant :
Corollaire : Le code concaténé
Un exemple de code Justesen
Le code légèrement différent suivant est appelé code Justesen dans MacWilliams/MacWilliams. Il s'agit du cas particulier du code Justesen mentionné ci-dessus pour un ensemble Wonzencraft très spécifique :
Soit R un code Reed-Solomon de longueur N = 2 m − 1, de rang K et de poids minimum N − K + 1.
Les symboles de R sont des éléments de F = GF(2 m ) et les mots de code sont obtenus en prenant chaque polynôme ƒ sur F de degré inférieur à K et en listant les valeurs de ƒ sur les éléments non nuls de F dans un ordre prédéterminé.
Soit α un élément primitif de F. Pour un mot de code a = ( a 1 , ..., a N ) de R , soit b le vecteur de longueur 2 N sur F donné par
et soit c le vecteur de longueur 2Nm obtenu à partir de b en exprimant chaque élément de F comme un vecteur binaire de longueur m . Le code de Justesen est le code linéaire contenant tous ces c .
Les paramètres de ce code sont une longueur de 2 m N , une dimension de m K et une distance minimale d'au moins
où