Codes AN

des codes correcteurs d'erreurs utilisés dans les applications arithmétiques. Les codes arithmétiques étaient couramment utilisés dans les processeurs informatiques pour garantir la précision des opérations arithmétiques à une époque où l'électronique était moins fiable. Ces codes permettent au processeur de détecter et de corriger les erreurs. Sans eux, les processeurs seraient peu fiables, car les erreurs passeraient inaperçues. Les codes AN sont des codes arithmétiques nommés d'après des entiers et utilisés pour coder et décoder les mots de code.

Ces codes diffèrent de la plupart des autres codes en ce qu'ils utilisent un poids arithmétique pour maximiser la distance arithmétique entre les mots codés, contrairement au poids et à la distance de Hamming . La distance arithmétique entre deux mots mesure le nombre d'erreurs commises lors d'un calcul. Son utilisation est nécessaire car une seule erreur de calcul peut engendrer une distance de Hamming importante entre la réponse reçue et la réponse correcte. où < , , et . La distance arithmétique d'un mot est majorée par son poids de Hamming, car tout entier peut être représenté par sa forme polynomiale standard de , où les sont les chiffres de l'entier. Supprimer tous les termes où simule un poids de Hamming égal à celui de l'entier. Le poids arithmétique est généralement inférieur au poids de Hamming, car les peuvent être négatifs. Par exemple, l'entier , qui est représenté en binaire, a un poids de Hamming de . Ceci constitue une majoration rapide du poids arithmétique, car . Cependant, comme les peuvent être négatifs, on peut écrire , ce qui rend le poids arithmétique égal à . La distance arithmétique entre deux entiers est définie par Il s'agit de l'une des principales métriques utilisées lors de l'analyse des codes arithmétiques.

Codes AN

Les codes AN sont définis par des entiers et sont utilisés pour coder les entiers de à tels que

<

Chaque choix de donnera lieu à un code différent, tandis que sert de facteur limitant pour garantir des propriétés utiles à la distance du code. Si est trop grand, il pourrait introduire un mot de code de très faible poids arithmétique, ce qui dégraderait la distance de l'ensemble du code. Pour utiliser ces codes, avant d'effectuer une opération arithmétique sur deux entiers, chaque entier est multiplié par . Soit le résultat de l'opération sur les mots de code . Notez que doit également être compris entre et pour un décodage correct. Pour décoder, il suffit de diviser . Si n'est pas un facteur de , alors au moins une erreur s'est produite et la solution la plus probable sera le mot de code ayant la plus petite distance arithmétique par rapport à . Comme pour les codes utilisant la distance de Hamming, les codes AN peuvent corriger jusqu'à erreurs, où est la distance du code.

Par exemple, pour un code AN avec , l'opération d'addition de et commence par encoder les deux opérandes. On obtient ainsi l'opération . Ensuite, pour trouver la solution, on divise . Tant que > , cette opération est possible avec ce code. Supposons qu'une erreur se produise dans la représentation binaire de chaque opérande, de sorte que et , alors . Remarquons que, puisque , le poids de Hamming entre le mot reçu et la solution correcte est après seulement erreurs. Pour calculer le poids arithmétique, on prend , qui peut être représenté par ou . Dans les deux cas, la distance arithmétique est conforme aux attentes, puisqu'elle correspond au nombre d'erreurs commises. Pour corriger cette erreur, un algorithme est utilisé afin de calculer le mot de code le plus proche du mot reçu en termes de distance arithmétique. Nous ne décrirons pas les algorithmes en détail.

Pour garantir que la distance du code ne soit pas trop petite, nous définirons des codes AN modulaires. Un code AN modulaire est un sous-groupe de , où . Les codes sont mesurés en termes de distance modulaire, définie à l'aide d'un graphe dont les sommets sont les éléments de . Deux sommets et sont connectés si et seulement si .

où et < < , . Alors la distance modulaire entre deux mots est la longueur du plus court chemin entre leurs nœuds dans le graphe. Le poids modulaire d'un mot est sa distance à laquelle est égal à

En pratique, la valeur de λ est généralement choisie de telle sorte que, la plupart des calculs informatiques étant effectués en λ = 0, il n'y ait pas de perte de données supplémentaire due au dépassement des limites du code, puisque l'ordinateur sera lui aussi hors limites. Choisir λ = 0 tend également à produire des codes avec des distances plus importantes que d'autres codes.

En utilisant un poids modulaire avec , les codes AN seront un code cyclique .

définition : Un code AN cyclique est un code qui est un sous-groupe de , où .

Un code AN cyclique est un idéal principal de l'anneau . Il existe des entiers et tels que et satisfont la définition d'un code AN. Les codes AN cycliques sont un sous-ensemble des codes cycliques et possèdent les mêmes propriétés.

Codes Mandelbaum-Barrows

Les codes de Mandelbaum-Barrows sont un type de codes AN cycliques introduits par D. Mandelbaum et J.T. Barrows. Ces codes sont créés en choisissant un nombre premier non divisible par , tel que soit généré par et , et . Soit un entier positif tel que et . Par exemple, en choisissant , le résultat sera un code de Mandelbaum-Barrows tel que < en base .

Pour analyser la distance des codes de Mandelbaum-Barrows, nous aurons besoin du théorème suivant.

théorème : Soit un code AN cyclique de générateur , et

Alors,

Démonstration : Supposons que chaque possède une représentation NAF cyclique unique qui est

On définit une matrice dont les éléments sont tels que et . Cette matrice est essentiellement une liste de tous les mots de code de , chaque colonne étant un mot de code. Puisque est cyclique, chaque colonne de la matrice contient le même nombre de zéros. Il faut maintenant calculer , qui est multiplié par le nombre de mots de code ne se terminant pas par . Étant donné qu'il existe un tel que < . Puisque tel que < , alors < . Le nombre d'entiers dont le dernier bit est un zéro est alors . En multipliant ce nombre par le nombre de caractères des mots de code, on obtient la somme des poids des mots de code de , comme souhaité.

Nous allons maintenant utiliser le théorème précédent pour montrer que les codes de Mandelbaum-Barrows sont équidistants (ce qui signifie que chaque paire de mots de code a la même distance), avec une distance de

Démonstration : Soit , alors et n'est pas divisible par . Ceci implique que . Donc . Ceci prouve que est équidistant puisque tous les mots de code ont le même poids que . Puisque tous les mots de code ont le même poids, et d'après le théorème précédent, nous connaissons le poids total de tous les mots de code, la distance du code est obtenue en divisant le poids total par le nombre de mots de code (0 exclu).