Producto que no requiere transporte

El producto sin acarreo de dos números binarios es el resultado de la multiplicación sin acarreo de estos números. Esta operación funciona conceptualmente como la multiplicación larga, excepto que el acarreo se descarta en lugar de aplicarse a la posición más significativa. Se puede usar para modelar operaciones sobre cuerpos finitos , en particular la multiplicación de polinomios de GF(2)[ X ], el anillo de polinomios sobre GF(2) .

Esta operación también se conoce como multiplicación XOR , ya que la suma con descarte de acarreo es equivalente a una operación OR exclusiva.

Dados dos números${\displaystyle \textstyle a=\sum _{i}a_{i}2^{i}}$y${\displaystyle \textstyle b=\sum _{i}b_{i}2^{i}}$, con${\displaystyle a_{i},b_{i}\in \{0,1\}}$denotando los bits de estos números, el producto sin acarreo de estos dos números se define como${\displaystyle \textstyle c=\sum _ {i}c_ {i}2^{i}}$, con cada bit${\displaystyle c_{i}}$calculado como el OR exclusivo de productos de bits de los números de entrada de la siguiente manera: ^{[ 1 ]}

${\displaystyle c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{ij}}$

Consideremos a = 10100010² _y b = 10010110² _, con todos los números expresados ​​en binario. La multiplicación sin acarreo de estos números es esencialmente la misma que se obtendría al realizar una multiplicación larga, pero ignorando los acarreos.

 1 0 1 0 0 0 1 0 = a ---------------|---|-------|-- 1 0 0 1 0 1 1 0|0 0 0 0 0 0 0 1 0 0 1 0 1 1 0|0 0 0 0 0 1 0 0 1 0 1 1 0|0 ------------------------------ 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 ^ ^

Por cada bit lógico 1 en el número a , el número b se desplaza a la izquierda tantos bits como indique la posición de estos bits a . Todas estas versiones desplazadas se "suman" mediante una operación XOR en lugar de la suma binaria regular utilizada en la multiplicación larga regular. Los resultados de la operación XOR se indican mediante ^. En un sumador binario completo, esto daría como resultado un acarreo a la columna de la izquierda. Aquí esto no sucede, por lo que el producto sin acarreo de a y b sería c = 101100011101100 ₂ .

El producto sin acarreo también puede verse como una multiplicación de polinomios sobre el cuerpo GF(2) . Esto se debe a que la disyunción exclusiva corresponde a la suma en este cuerpo.

En el ejemplo anterior, los números a y b corresponden a polinomios.

${\displaystyle A=\sum _{i}a_{i}X^{i}=X^{7}+X^{5}+X^{1}\qquad B=\sum _{i}b_{i}X^{i}=X^{7}+X^{4}+X^{2}+X^{1}}$

y el producto de estos es

${\displaystyle C=A\cdot B=\sum _{i}c_{i}X^{i}=X^{14}+X^{12}+X^{11}+X^{7}+X^{6}+X^{5}+X^{3}+X^{2}}$

que es lo que codifica el número c calculado anteriormente. Observe cómo${\displaystyle (X^{7}\cdot X^{1})+(X^{1}\cdot X^{7})\equiv 0}$y${\displaystyle (X^{7}\cdot X^{2})+(X^{5}\cdot X^{4})\equiv 0}$gracias a la aritmética en GF(2). Esto corresponde a las columnas marcadas ^en el ejemplo.

Los elementos de GF(2 ⁿ ), es decir, un cuerpo finito cuyo orden es una potencia de dos , se representan habitualmente como polinomios en GF(2)[ X ]. La multiplicación de dos elementos de dicho cuerpo consiste en la multiplicación de los polinomios correspondientes, seguida de una reducción con respecto a algún polinomio irreducible tomado de la construcción del cuerpo. Si los polinomios se codifican como números binarios, se puede utilizar la multiplicación sin acarreo para realizar el primer paso de este cálculo.

Estos campos tienen aplicaciones en criptografía y en algunos algoritmos de suma de verificación .

Muchas arquitecturas de CPU modernas admiten diversas extensiones que proporcionan soporte de hardware para algún tipo de multiplicación sin acarreo. Este soporte puede adoptar la forma de instrucciones vectoriales o escalares.

A continuación se enumeran algunas extensiones del conjunto de instrucciones para la multiplicación sin acarreo en diversas arquitecturas de CPU.

Para otros objetivos, es posible implementar el cálculo anterior como un algoritmo de software, y muchas bibliotecas de criptografía incluirán una implementación como parte de sus operaciones aritméticas de campo finito.

Para multiplicaciones amplias sin acarreo, es posible adaptar algoritmos rápidos de multiplicación de enteros, como los algoritmos de Karatsuba y Toom-Cook, para que funcionen con multiplicaciones sin acarreo. ^{[ 11 ] [ 12 ]}

La definición de un producto sin acarreo, como resultado de una multiplicación larga descartando el acarreo, se aplicaría fácilmente a bases distintas de 2. Sin embargo, el resultado depende de la base, que es, por lo tanto, una parte esencial de la operación. Dado que esta operación se utiliza habitualmente en ordenadores que trabajan con binario, la forma binaria descrita anteriormente es la que se emplea en la práctica.

Los polinomios sobre otros campos finitos de orden primo tienen aplicaciones, pero tratar los coeficientes de dicho polinomio como los dígitos de un solo número es bastante inusual, por lo que la multiplicación de tales polinomios no se consideraría una multiplicación de números sin acarreo.

• Conjunto de instrucciones CLMUL , una extensión ISA x86
• Aritmética de cuerpos finitos
• Modo Galois/Contador