Умножитель по модулю q

Изобретение относится к вычислительной технике. Технический результат заключается в расширении арсенала средств того же назначения. Умножитель по модулю q, содержащий элемент И, при этом в умножитель q дополнительно введены два элемента И и четыре элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. 1 табл., 1 ил.

 

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.

Известны умножители по модулю q (см., например, правый рис. во второй сверху строке хвостовой части таблицы на рис. 3.20 в книге Токхейм Р. Основы цифровой электроники. М.: Мир, 1988 г.), которые реализуют операцию (А×В)mod 2, где A, B∈{0,1} есть одноразрядные двоичные числа, задаваемые двоичными сигналами.

К причине, препятствующей достижению указанного ниже технического результата при использовании известных умножителей по модулю q, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется операция (А×В)mod 3, где А, В∈{00,01,10,11} есть двухразрядные двоичные числа, задаваемые двоичными сигналами.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип умножитель по модулю q (рис. в первой сверху строке хвостовой части таблицы на рис. 3.35 в книге Токхейм Р. Основы цифровой электроники. М.: Мир, 1988 г.), который содержит элемент И и реализует операцию (А×В)mod 2, где А, В∈{0,1} есть одноразрядные двоичные числа, задаваемые двоичными сигналами.

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется операция (А×B)mod 3, где А, В∈{00,01,10,11} есть двухразрядные двоичные числа, задаваемые двоичными сигналами.

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения реализации операции (А×В)mod q при q=2 либо при q=3, где А, В (0≤A<2×q-2, 0≤В<2×q-2) есть (log₂(2×q-2)) - разрядные двоичные числа, задаваемые двоичными сигналами.

Указанный технический результат при осуществлении изобретения достигается тем, что в умножителе по модулю q, содержащем элемент И, особенность заключается в том, что в него дополнительно введены два элемента И и четыре элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первый вход третьего и первый, второй входы четвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с вторыми и первыми входами второго, первого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый, второй входы j-го и первый, второй входы третьего элементов И соединены соответственно с выходом j-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выходом третьего элемента И и выходами третьего, четвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, а первый, второй входы (j+2)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и выход j-го элемента И соединены соответственно с (2×j-1)-м, (2×j)-м входами и j-м выходом умножителя по модулю q.

На чертеже представлена схема предлагаемого умножителя по модулю q.

Умножитель по модулю q содержит элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 1₁, 1₂, 1₃, 1₄ и элементы И 2₁, 2₂, 2₃, причем первый вход элемента 1₃ и первый, второй входы элемента 1₄ соединены соответственно с вторыми и первыми входами элементов 1₂, 1₁, первый, второй входы элемента 2_j и первый, второй входы элемента 2₃ соединены соответственно с выходами элементов 1_j, 2₃ и 1₃, 1₄, а первый, второй входы элемента 1_j+2 и выход элемента 2_j соединены соответственно с (2×j-1)-м, (2×j)-м входами и j-м выходом умножителя по модулю q.

Работа предлагаемого умножителя по модулю q осуществляется следующим образом. На его первый, второй и третий, четвертый входы подаются соответственно двоичные сигналы a₀,a₁∈{0,1} и b₀,b₁∈{0,1}, которые задают подлежащие обработке двухразрядные двоичные числа А=a₁a₀, B=b₁b₀, причем a₁,b₁ и a₀,b₀ определяют значения старших и младших разрядов соответственно, А, В∈{00,01,10,11}. В представленной ниже таблице приведены значения выходных сигналов y₀,y₁ предлагаемого умножителя, полученные с учетом работы элементов 1₁, 1₂, 1₃, 1₄, 2₁, 2₂, 2₃ для всех возможных наборов значений сигналов а₀,а₁,b₀,b₁.

Согласно представленной таблице имеем Y=(А×В)mod 3, где Y=y₁y₀ - двухразрядное двоичное число, задаваемое двоичными сигналами y₀, y₁∈{0,1} (y₁ и y₀ определяют значения старшего и младшего разрядов соответственно). Если a₁=b₁=0, то согласно представленной таблицы (см. значения сигналов a₀, b₀, y₀, выделенные жирным шрифтом) получим Y=(А×В)mod 2, где А=а₀, B=b₀, Y=y₀ - одноразрядные двоичные числа, задаваемые указанными сигналами.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемый умножитель по модулю q обладает более широкими по сравнению с прототипом функциональными возможностями, так как реализует операцию (A×B)mod q при q=2 либо при q=3, где А, В (0≤A<2×q-2, 0≤В<2×q-2) есть (log₂(2×q-2)) - разрядные двоичные числа, задаваемые двоичными сигналами.

Умножитель по модулю q, содержащий элемент И, отличающийся тем, что в него дополнительно введены два элемента И и четыре элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, причем первый вход третьего и первый, второй входы четвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с вторыми и первыми входами второго, первого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый, второй входы j-го и первый, второй входы третьего элементов И соединены соответственно с выходом j-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выходом третьего элемента И и выходами третьего, четвертого элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, а первый, второй входы (j+2)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и выход j-го элемента И соединены соответственно с (2×j-1)-м, (2×j)-ым входами и j-м выходом умножителя по модулю q.