Операция умножения по mod2

Схема умножения n -разрядного двоичного числа А на фиксированный образующий полином Р m -йстепени показана на рис. 1. Схема содержит n -разрядный регистр числа RGA со сдвигом влево (в сторону старших разрядов), (m+1)-разрядный регистр полинома RGP со сдвигом вправо (в сторону младших разрядов), умножители на коэффициенты p_i и сумматоры по mod2.

В исходном состоянии в регистре RGA записано число A, в регистре RGP – нули. Формирование n+m -разрядного произведения по mod2 осуществляется за n+m тактов в реальном масштабе времени. Произведение формируется на выходе устройства (выход правого сумматора по mod2) старшими разрядами вперед (в такте Т1 формируется старший разряд и т.д.).

Так как в двоичных полиномах коэффициенты p_i могут принимать значения 1 или 0, то умножители на коэффициенты p_i на схемах трактуются следующим образом: если p_i =1, то связь между выходом i -го разряда регистра RGP и входомсумматора по mod2 имеется; и если p_i =0, то связь между выходом i -го разряда регистра RGP и входомсумматора по mod2 отсутствует.

Пример построения схемы умножения 7-разрядных чисел A на порождающий полином 5-йстепени Р = 2⁵+2³+2⁰ = 101001показан на рис. 2. Работа схемы при умножении 7-разрядного числа A= 1011011 на этот полином иллюстрируется таблицей 1.

В исходном состоянии в регистре RGA записано число A= 1011011, в регистре RGP – нули. В каждом такте содержимое регистра RGA сдвигается на 1 разряд влево, а содержимое регистра RGP – вправо. При этом “выталкиваемый” из регистра RGA старший разрядзаносится в освобождающийся старший разрядрегистра RGP. Для такта Т1 этот разряд помечен звездочкой (1* в строках “исх. сост.” регистра RGA и “Т1” регистра RGP). Для такта Т2 – 0* в строках “Т1” регистра RGA и “Т2” регистра RGP). В овобождающиеся при сдвиге разряды регистра RGA заносятсянули.

Произведение по mod2 двух чисел может быть получено (и использовано для проверки) способом привычного умножения “в столбик” (таблица 2.).

Первая строка под верхней чертой представляет собой результат умножения множимого на младший разряд множителя, вторая строка – на третий разряд, третья строка – на пятый разряд множителя, т.е на те разряды, которые равны 1. В отличие от обычного умножения суммирование этих строк осуществляется по mod2.

Таблица 1. Умножение 7-разрядного числа A на порождающий полином 5-йстепени

Таблица 2. Умножение чисел “в столбик”