Sistema de clases residuales

Residual class system (SOC) ( sistema de números de residuos en inglés ) es un sistema numérico basado en la aritmética modular .

La representación de un número en el sistema de clases de resto se basa en el concepto de residuo y el teorema chino del resto . RNS está determinado por un conjunto de módulos coprimos por pares , es decir, tales que , llamados una base, y un producto, de modo que cada número entero del segmento está asociado con un conjunto de residuos , donde $(m_{1},\,m_{2},\,\puntos,\,m_{n})$ ${\ estilo de visualización \ gcd (m_ {i}, \, m_ {j}) = 1}$ ${\ estilo de visualización (i, \, j = 0, \, 1, \, \ puntos, \, n; \ i \ neq j)}$ $M=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n},$ $X$ ${\ estilo de visualización [0, \ M-1]}$ ${\ estilo de visualización (x_{1},\,x_{2},\,\puntos,\,x_{n})}$

x_{1}\equiv x{\pmod {m_{1))};

x_{2}\equiv x{\pmod {m_{2))};

\puntos \puntos \puntos \puntos \puntos \puntos \puntos

x_{n}\equiv x{\pmod {m_{n))}.

Al mismo tiempo, el teorema chino del resto garantiza la unicidad (unicidad) de la representación de los números enteros no negativos del intervalo . ${\ estilo de visualización [0, \ M-1]}$

Beneficios del sistema de clases residuales

En RNS, las operaciones aritméticas (suma, resta, multiplicación, división) se realizan componente por componente si se sabe que el resultado es un número entero y también se encuentra en . $[0,M-1]$

Fórmula de adición: donde $(x_{1},x_{2},\puntos,x_{n})+(y_{1},y_{2},\puntos,y_{n})=(z_{1},z_ {2},\puntos,z_{n})$

z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}};

z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}};

\puntos \puntos \puntos \puntos \puntos \puntos \puntos \puntos \puntos

z_{n}\equiv (x_{n}+y_{n}){\pmod {m_{n))}.

La resta, la multiplicación y la división se realizan de manera similar. Nota : Hay restricciones adicionales sobre la división. La división debe ser un número entero, es decir, el divisor debe dividir el dividendo por un número entero. El divisor debe ser coprimo con todos los módulos de la base.

Desventajas del sistema de clases residuales

falta de algoritmos eficientes para comparar números; Habitualmente, la comparación se realiza traduciendo los argumentos del RNS al sistema numérico (poliádico) con bases mixtas: ; ${\displaystyle m_{1},m_{1}m_{2},\puntos,m_{1}m_{2}\puntos m_{n-1))$
algoritmos lentos para la transformación mutua de la representación de números del sistema de numeración posicional a RNS y viceversa;
algoritmos de división complejos (cuando el resultado no es un número entero);
Dificultad para detectar el desbordamiento.

Aplicación del sistema de clases residuales

SOC es ampliamente utilizado en microelectrónica en dispositivos DSP especializados , donde se requiere:

control de errores mediante la introducción de módulos redundantes adicionales;
alta velocidad, que es proporcionada por la implementación paralela de operaciones aritméticas básicas;
seguridad de la información

Aplicación práctica: computadora de tubo de vacío checoslovaca "EPOS" , supercomputadora multiprocesador militar soviética 5E53 , diseñada para resolver problemas de defensa antimisiles .

Sistemas de módulos especiales

En la aritmética modular, existen conjuntos especiales de módulos que le permiten nivelar parcialmente las deficiencias y para los cuales existen algoritmos efectivos para comparar números y para la traducción directa e inversa de números modulares en un sistema numérico posicional. Uno de los sistemas de módulos más populares es un conjunto de tres números coprimos por pares de la forma {2 n −1, 2 n , 2 n +1} .

Ejemplo

Considere un RNS con base . En esta base, es posible representar números del intervalo de a uno a uno , ya que . Tabla de correspondencia de números del sistema de numeración posicional y el sistema de clases residuales: ${\ estilo de visualización (2; 3; 5)}$ ${\ estilo de visualización 0}$ $29$ $M=2\times 3\times 5=30$

${\ estilo de visualización 0 = (0; 0; 0)}$	${\ estilo de visualización 1 = (1; 1; 1)}$	${\ estilo de visualización 2 = (0; 2; 2)}$	${\ estilo de visualización 3 = (1; 0; 3)}$	${\ estilo de visualización 4 = (0; 1; 4)}$
${\ estilo de visualización 5 = (1; 2; 0)}$	${\ estilo de visualización 6 = (0; 0; 1)}$	${\ estilo de visualización 7 = (1; 1; 2)}$	${\ estilo de visualización 8 = (0; 2; 3)}$	${\ estilo de visualización 9 = (1; 0; 4)}$
${\ estilo de visualización 10 = (0; 1; 0)}$	${\ estilo de visualización 11 = (1; 2; 1)}$	${\ estilo de visualización 12 = (0; 0; 2)}$	${\ estilo de visualización 13 = (1; 1; 3)}$	${\ estilo de visualización 14 = (0; 2; 4)}$
${\ estilo de visualización 15 = (1; 0; 0)}$	${\ estilo de visualización 16 = (0; 1; 1)}$	${\ estilo de visualización 17 = (1; 2; 2)}$	${\ estilo de visualización 18 = (0; 0; 3)}$	${\ estilo de visualización 19 = (1; 1; 4)}$
${\ estilo de visualización 20 = (0; 2; 0)}$	${\ estilo de visualización 21 = (1; 0; 1)}$	${\ estilo de visualización 22 = (0; 1; 2)}$	${\ estilo de visualización 23 = (1; 2; 3)}$	${\ estilo de visualización 24 = (0; 0; 4)}$
${\ estilo de visualización 25 = (1; 1; 0)}$	${\ estilo de visualización 26 = (0; 2; 1)}$	${\ estilo de visualización 27 = (1; 0; 2)}$	${\ estilo de visualización 28 = (0; 1; 3)}$	${\ estilo de visualización 29 = (1; 2; 4)}$

Ejemplo de adición

Sumemos dos números 9 y 14 en la base . Su representación en la base dada y (ver tabla arriba). Usemos la fórmula para la suma: ${\ estilo de visualización (2; 3; 5)}$ ${\ estilo de visualización 9 = (1; 0; 4)}$ ${\ estilo de visualización 14 = (0; 2; 4)}$ ${\ estilo de visualización (z_{1},z_{2},z_{3})=(1,0,4)+(0,2,4)}$

z_{1}\equiv (x_{1}+y_{1}){\pmod {m_{1}}}\equiv (1+0){\pmod {2}}=1;

z_{2}\equiv (x_{2}+y_{2}){\pmod {m_{2}}}\equiv (0+2){\pmod {3}}=2;

z_{3}\equiv (x_{3}+y_{3}){\pmod {m_{3}}}\equiv (4+4){\pmod {5}}=3;

${\ estilo de visualización (z_{1},z_{2},z_{3})=(1,2,3)}$ - según la tabla, nos aseguramos de que el resultado sea 23.

Ejemplo de multiplicación

Multiplica dos números 4 y 5 en base . Su representación en la base dada y (ver la placa de arriba). Usemos la fórmula para la multiplicación: ${\ estilo de visualización (2; 3; 5)}$ ${\ estilo de visualización 4 = (0; 1; 4)}$ ${\ estilo de visualización 5 = (1; 2; 0)}$ ${\ estilo de visualización (z_{1},z_{2},z_{3})=(0,1,4)*(1,2,0)}$

z_{1}\equiv (x_{1}*y_{1}){\pmod {m_{1}}}\equiv (0*1){\pmod {2}}=0;

z_{2}\equiv (x_{2}*y_{2}){\pmod {m_{2}}}\equiv (1*2){\pmod {3}}=2;

z_{3}\equiv (x_{3}*y_{3}){\pmod {m_{3}}}\equiv (4*0){\pmod {5}}=0;

${\ estilo de visualización (z_{1},z_{2},z_{3})=(0,2,0)}$ - según la tabla, nos aseguramos de que el resultado sea 20.

Nota: si tuviéramos que multiplicar o sumar números que dieran como resultado de la multiplicación un número mayor o igual que, entonces el resultado obtenido, donde es el resultado de la operación en el sistema numérico posicional. ${\ estilo de visualización M = 30}$ $RES\equiv REAL{\pmod {M}}$ ${\ estilo de visualización REAL}$

Un ejemplo de división, asumiendo que la división de enteros es posible

La división se puede realizar de la misma manera que la multiplicación, pero solo si el divisor divide el dividendo en partes iguales, sin resto.
Para módulos , divida el número 1872 entre 9. Divida entre . ${\ estilo de visualización (29; 31; 32)}$
${\ estilo de visualización 1872 = (16; 12; 16)}$ ${\ estilo de visualización 9 = (9; 9; 9)}$

Usemos la fórmula
$z_{i}\equiv (x_{i}*y_{i}^{-1}){\pmod {m_{i}}}.$

Aquí hay que decir que , que no es lo mismo que simplemente dividir por . Según la fórmula obtenemos: ${\displaystyle y_{i}^{-1}*y_{i}=1{\pmod {m_{i))))$ $X$ $y$
${\displaystyle y_{i}^{m_{i}-1}=1{\pmod {m_{i))))$
$9^{29-2}{\pmod {29}}=13,$
$9^{31-2}{\pmod {31}}=7.$
$9^{32-2}{\pmod {32}}=17;$

$z_{1}\equiv (16*13){\pmod {29}}=5,$
$z_{2}\equiv (12*7){\pmod {31}}=22,$
$z_{3}\equiv (16*17){\pmod {32}}=16.$

Este es el resultado correcto: el número 208. Sin embargo, tal resultado solo se puede obtener si se sabe que la división se lleva a cabo sin resto.

Véase también

Literatura

Akushsky I.Ya. , Yuditsky D. I. Aritmética de Máquinas en Clases Residuales . - Búhos. radio , 1968. - 439 págs.
Torgashev, Valéry Antonovich. Sistema de Clases Residuales y Confiabilidad de Computadores . - M . : Sov. radio , 1973. - 118 págs.
Amerbaev V. M. Fundamentos teóricos de la aritmética de máquinas . - Academia de Ciencias de la República Socialista Soviética de Kazajstán, Instituto de Matemáticas y Mecánica. Alma-Ata: Ciencia , 1976. - 324 p.
Finko O. A. Aritmética modular de cálculos lógicos paralelos : Monografía - M .: IPU RAS , 2003. - 214 p.
Aniversario Congreso científico y técnico internacional "50 años de aritmética modular" . - OJSC "Angstrem" , MIET . - 23-25 de noviembre de 2005; Moscú, Zelenograd: FIZMATLIT , 2006. - 775 p. — ISBN ISBN 5-7256-0409-8 .
Amos Omondi, Benjamin Premkumar. Sistemas numéricos de residuos: teoría e implementación . - 57 Shelton Street Covent Garden Londres: Imperial College Press , 2007. - 296 p. - ISBN 978-1-86094-866-4 .
Chervyakov N. I., Evdokimov A. A., Galushkin A. I. , Lavrinenko IN et al.. Aplicación de redes neuronales artificiales y sistema de clases residuales en criptografía . — M .: FIZMATLIT , 2012. — 280 p. - ISBN 978-5-9221-1386-1 .
Ananda Mohan, Sistemas de numeración de residuos fotovoltaicos. - Cham: Springer International Publishing , 2016. - 351 p. - ISBN 978-3-319-41385-3 .
Amir Sabbagh, Molahosseini, Leonel Seabra de Sousa y Chip-Hong Chang (editores). Diseño de Sistemas Embebidos con Aritmética Especial y Sistemas Numéricos. - Cham: Springer International Publishing , 21 de marzo de 2017. - 389 p. — ISBN 978-3-319-49742-6 .

Enlaces

Artículo "Aritmética modular" en la Gran Enciclopedia Rusa