Códigos AN

Los códigos AN son códigos de corrección de errores que se utilizan en aplicaciones aritméticas. ^{[1] Los códigos} aritméticos se usaban comúnmente en procesadores de computadoras para garantizar la precisión de sus operaciones aritméticas cuando la electrónica era menos confiable. Los códigos aritméticos ayudan al procesador a detectar cuándo se comete un error y corregirlo. Sin estos códigos, los procesadores no serían confiables ya que cualquier error pasaría desapercibido. Los códigos AN son códigos aritméticos que reciben su nombre de los números enteros y que se utilizan para codificar y decodificar las palabras clave. ${\estilo de visualización A}$${\estilo de visualización N}$

Estos códigos se diferencian de la mayoría de los demás códigos en que utilizan un peso aritmético para maximizar la distancia aritmética entre las palabras del código, en lugar del peso y la distancia de Hamming . La distancia aritmética entre dos palabras es una medida de la cantidad de errores cometidos al calcular una operación aritmética. El uso de la distancia aritmética es necesario ya que un error en una operación aritmética puede causar una gran distancia de Hamming entre la respuesta recibida y la respuesta correcta.

El peso aritmético de un entero en base se define por ${\estilo de visualización x}$${\estilo de visualización r}$

${\displaystyle w(x)=\min\{t|x=\sum _{i=1}^{t}a_{i}r^{n(i)}\}}$

donde < , , y . ^[2] La distancia aritmética de una palabra está limitada superiormente por su peso de Hamming, ya que cualquier entero puede representarse por su forma polinómica estándar de donde son los dígitos del entero. Eliminar todos los términos donde simulará un igual a su peso de Hamming. El peso aritmético normalmente será menor que el peso de Hamming, ya que se permite que sean negativos. Por ejemplo, el entero que está en binario tiene un peso de Hamming de . Este es un límite superior rápido del peso aritmético, ya que . Sin embargo, dado que puede ser negativo, podemos escribir que hace que el peso aritmético sea igual a . ${\displaystyle |{a_{i}}|}$${\estilo de visualización r}$${\displaystyle n(i)\geq 0}$${\displaystyle r,n(i)\in \mathbb {Z} }$${\displaystyle x=\suma _{i=1}^{n}b_{i}r^{i}}$${\displaystyle b_{i}}$${\displaystyle b_{i}=0}$${\displaystyle t}$${\displaystyle a_{i}}$${\displaystyle x=29}$${\displaystyle 11101}$${\displaystyle 4}$${\displaystyle x=2^{0}+2^{2}+2^{3}+2^{4}}$${\displaystyle a_{i}}$${\displaystyle x=2^{5}-2^{1}-2^{0}}$${\displaystyle 3}$

La distancia aritmética entre dos números enteros se define por

${\displaystyle d(x,y)=w(x-y)}$

Esta es una de las métricas principales que se utilizan al analizar códigos aritméticos. ^{[3] [4]}

Los códigos AN se definen mediante números enteros y se utilizan para codificar números enteros de a tales que ${\displaystyle A}$${\displaystyle B}$${\displaystyle 0}$${\displaystyle B-1}$

${\displaystyle C=\{AN|N\in \mathbb {Z} ,0\leq N}$<${\displaystyle B\}}$

Cada elección de dará como resultado un código diferente, mientras que sirve como un factor limitante para asegurar propiedades útiles en la distancia del código. Si es demasiado grande, podría dejar entrar en el código una palabra de código con un peso aritmético muy pequeño, lo que degradará la distancia de todo el código. Para utilizar estos códigos, antes de realizar una operación aritmética en dos números enteros, cada número entero se multiplica por . Sea el resultado de la operación en las palabras de código . Tenga en cuenta que también debe estar entre a para una decodificación adecuada. Para decodificar, simplemente divida . Si no es un factor de , entonces se ha producido al menos un error y la solución más probable será la palabra de código con la menor distancia aritmética de . Al igual que con los códigos que utilizan la distancia de Hamming, los códigos AN pueden corregir hasta errores donde es la distancia del código. ${\displaystyle A}$${\displaystyle B}$${\displaystyle B}$${\displaystyle A}$${\displaystyle R}$${\displaystyle R}$${\displaystyle 0}$${\displaystyle B-1}$${\displaystyle R/A}$${\displaystyle A}$${\displaystyle R}$${\displaystyle R}$${\displaystyle \lfloor {\frac {d-1}{2}}\rfloor }$${\displaystyle d}$

Por ejemplo, un código AN con , la operación de sumar y comenzará codificando ambos operandos. Esto da como resultado la operación . Luego, para encontrar la solución dividimos . Mientras > , esta será una operación posible bajo el código. Suponga que ocurre un error en cada una de las representaciones binarias de los operandos tales que y , entonces . Observe que como , el peso de Hamming entre la palabra recibida y la solución correcta es después de solo errores. Para calcular el peso aritmético, tomamos que puede representarse como o . En cualquier caso, la distancia aritmética es la esperada ya que este es el número de errores que se cometieron. Para corregir este error, se utilizaría un algoritmo para calcular la palabra de código más cercana a la palabra recibida en términos de distancia aritmética. No describiremos los algoritmos en detalle. ${\displaystyle A=3}$${\displaystyle 15}$${\displaystyle 16}$${\displaystyle R=45+48=93}$${\displaystyle 93/3=31}$${\displaystyle B}$${\displaystyle 31}$${\displaystyle 45=101101\rightarrow 101111}$${\displaystyle 48=110000\rightarrow 110001}$${\displaystyle R=101111+110001=1100000}$${\displaystyle 93=1011101}$${\displaystyle 5}$${\displaystyle 2}$${\displaystyle 1100000-1011101=11}$${\displaystyle 11=2^{0}+2^{1}}$${\displaystyle 11=2^{2}-2^{0}}$${\displaystyle 2}$

Para asegurarnos de que la distancia del código no sea demasiado pequeña, definiremos códigos AN modulares. Un código AN modular es un subgrupo de , donde . Los códigos se miden en términos de distancia modular que se define en términos de un gráfico con vértices que son los elementos de . Dos vértices y están conectados si y solo si ${\displaystyle C}$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle m=AB}$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle x{\pmod {m}}}$${\displaystyle x'{\pmod {m}}}$

${\displaystyle x-x'\equiv \pm c\cdot r^{j}{\pmod {m}}}$

donde y < < , . Entonces la distancia modular entre dos palabras es la longitud del camino más corto entre sus nodos en el gráfico. El peso modular de una palabra es su distancia desde la cual es igual a ${\displaystyle c,j\in \mathbb {Z} }$${\displaystyle 0}$${\displaystyle c}$${\displaystyle r}$${\displaystyle j\geq 0}$${\displaystyle 0}$

${\displaystyle w_{m}(x)=min\{w(y)|y\in \mathbb {Z} ,y\equiv x{\pmod {m}}\}}$

En la práctica, el valor de se suele elegir de forma que, dado que la mayor parte de la aritmética informática se calcula de forma que no haya una pérdida adicional de datos debido a que el código se salga de los límites, ya que la computadora también estará fuera de los límites. La elección también tiende a dar como resultado códigos con distancias mayores que otros códigos. ${\displaystyle m}$${\displaystyle m=r^{n}-1}$${\displaystyle \mod 2^{n}-1}$${\displaystyle m=r^{n}-1}$

Al utilizar el peso modular con , los códigos AN serán códigos cíclicos . ${\displaystyle m=r^{n}-1}$

definición : Un código AN cíclico es un código que es un subgrupo de , donde . ${\displaystyle C}$${\displaystyle [r^{n}-1]}$${\displaystyle [r^{n}-1]=\{0,1,2,\dots ,r^{n}-1\}}$

Un código AN cíclico es un ideal principal del anillo . Hay números enteros y donde y satisfacen la definición de un código AN. Los códigos AN cíclicos son un subconjunto de los códigos cíclicos y tienen las mismas propiedades. ${\displaystyle [r^{n}-1]}$${\displaystyle A}$${\displaystyle B}$${\displaystyle AB=r^{n}-1}$${\displaystyle A,B}$

Los códigos de Mandelbaum-Barrows son un tipo de códigos AN cíclicos introducidos por D. Mandelbaum y JT Barrows. ^{[5] [6]} Estos códigos se crean eligiendo un número primo que no divida tal que se genere mediante y , y . Sea un entero positivo donde y . Por ejemplo, eligiendo , y el resultado será un código de Mandelbaum-Barrows tal que < en base . ${\displaystyle B}$${\displaystyle r}$${\displaystyle \mathbb {Z} /B\mathbb {Z} }$${\displaystyle r}$${\displaystyle -1}$${\displaystyle m=r^{n}-1}$${\displaystyle n}$${\displaystyle r^{n}\equiv 1{\pmod {B}}}$${\displaystyle A=(r^{n}-1)/B}$${\displaystyle r=2,B=5,n=4}$${\displaystyle A=(r^{n}-1)/B=3}$${\displaystyle C=\{3N|N\in \mathbb {Z} ,0\leq N}$${\displaystyle 5\}}$${\displaystyle 2}$

Para analizar la distancia de los Códigos de Mandelbaum-Barrows, necesitaremos el siguiente teorema.

Teorema : Sea un código AN cíclico con generador , y ${\displaystyle C\subset [r^{n}-1]}$${\displaystyle A}$

${\displaystyle B=|C|=(r^{n}-1)/A}$

Entonces,

${\displaystyle \sum _{x\in C}w_{m}(x)=n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

Prueba : Supongamos que cada uno tiene una representación cíclica única de NAF ^[7] que es ${\displaystyle x\in C}$

${\displaystyle x\equiv \sum _{i=0}^{n-1}c_{i,x}r^{i}{\pmod {r^{n}-1}}}$

Definimos una matriz con elementos donde y . Esta matriz es esencialmente una lista de todas las palabras clave en donde cada columna es una palabra clave. Como es cíclica, cada columna de la matriz tiene la misma cantidad de ceros. Ahora debemos calcular , que es multiplicado por la cantidad de palabras clave que no terminan en . Como una propiedad de estar en NAF cíclica, si y solo si hay un con < . Como con < , entonces < . Entonces, la cantidad de números enteros que tienen un cero como su último bit son . Multiplicar esto por los caracteres en las palabras clave nos da una suma de los pesos de las palabras clave de como se desee. ${\displaystyle n\times B}$${\displaystyle c_{i,x}}$${\displaystyle 0\leq i\leq n-1}$${\displaystyle x\in C}$${\displaystyle C}$${\displaystyle C}$${\displaystyle n|\{x\in C|c_{n-1,x}\neq 0\}|}$${\displaystyle n}$${\displaystyle 0}$${\displaystyle c_{n-1,x}\neq 0}$${\displaystyle y\in \mathbb {Z} }$${\displaystyle y\equiv x{\pmod {r^{n}-1}},{\frac {m}{r+1}}}$${\displaystyle y\leq {\frac {mr}{r+1}}}$${\displaystyle x=AN{\pmod {r^{n}-1}}}$${\displaystyle 0\leq N}$${\displaystyle B}$${\displaystyle {\frac {B}{r+1}}}$${\displaystyle N\leq {\frac {Br}{r+1}}}$${\displaystyle \lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor }$${\displaystyle n}$${\displaystyle n(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

Ahora usaremos el teorema anterior para demostrar que los códigos de Mandelbaum-Barrows son equidistantes (lo que significa que cada par de palabras de código tiene la misma distancia), con una distancia de

${\displaystyle {\frac {n}{B-1}}(\lfloor {\frac {rB}{r+1}}\rfloor -\lfloor {\frac {B}{r+1}}\rfloor )}$

prueba : Sea , entonces y no es divisible por . Esto implica que hay . Entonces . Esto demuestra que es equidistante ya que todas las palabras de código tienen el mismo peso que . Como todas las palabras de código tienen el mismo peso, y por el teorema anterior conocemos el peso total de todas las palabras de código, la distancia del código se encuentra dividiendo el peso total por el número de palabras de código (excluyendo 0). ${\displaystyle x\in C,x\neq 0}$${\displaystyle x=AN{\pmod {r^{n}-1}}}$${\displaystyle N}$${\displaystyle B}$${\displaystyle \exists j(N\equiv \pm r^{j}{\pmod {B}})}$${\displaystyle w_{m}(x)=w_{m}(\pm r^{j}A)=w_{m}(A)}$${\displaystyle C}$${\displaystyle A}$

• Detección y corrección de errores
• Corrección de errores hacia adelante