Продукт без переноски

Произведение двух двоичных чисел без переноса является результатом умножения этих чисел без переноса. Эта операция концептуально работает как длинное умножение , за исключением того факта, что перенос отбрасывается, а не применяется к более значимой позиции. Его можно использовать для моделирования операций над конечными полями , в частности умножения полиномов из GF(2)[ X ], кольца полиномов над GF(2) .

Операция также известна как умножение XOR , так как сложение с отбрасыванием переноса эквивалентно исключающему ИЛИ.

Даны два числа и , где обозначены биты этих чисел. Тогда произведение этих двух чисел без переноса определяется как , где каждый бит вычисляется как исключающее ИЛИ произведений битов из входных чисел следующим образом: ^[1]${\ Displaystyle \ textstyle а = \ сумма _ {я} а_ {я} 2 ^ {я}}$${\ Displaystyle \ textstyle b = \ сумма _ {я} b_ {я} 2 ^ {я}}$${\ Displaystyle а_ {я}, b_ {я} \ в \ {0,1 \}}$${\ Displaystyle \ textstyle с = \ сумма _ {я} с_ {я} 2 ^ {я}}$${\ Displaystyle с_ {я}}$

Рассмотрим a = 10100010 ₂ и b = 10010110 ₂ , причем все числа даны в двоичном формате. Тогда их умножение без переноса — это, по сути, то, что можно было бы получить, выполняя длинное умножение, но игнорируя переносы.

Таким образом, произведение a и b без переноса будет равно c = 101100011101100 ₂ . Для каждого бита, установленного в числе a , число b сдвигается влево на столько битов, сколько указано позицией бита в a . Все эти сдвинутые версии затем объединяются с использованием исключающего или вместо обычного сложения, которое использовалось бы для обычного длинного умножения. Это можно увидеть в столбцах, обозначенных значком ^, где обычное сложение привело бы к переносу в столбец слева, чего здесь не происходит.

Произведение без переноса также можно рассматривать как произведение многочленов над полем GF(2) . Это связано с тем, что исключающее или соответствует добавлению в этом поле.

Вычисление продукта без переноса.