RU2770798C1

RU2770798C1 - ВЫЧИТАТЕЛЬ ПО МОДУЛЮ q

Info

Publication number: RU2770798C1
Application number: RU2021109181A
Authority: RU
Inventors: Дмитрий Васильевич Андреев
Priority date: 2021-04-02
Filing date: 2021-04-02
Publication date: 2022-04-21

Abstract

Изобретение относится к области вычислительной техники. Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения реализации операции (А-В)mod q при q-2 либо при q=3, где А, В (0≤A<q, 0≤B<q) есть (log2(2×q-2))-разрядные двоичные числа, задаваемые двоичными сигналами. Вычитатель по модулю q предназначен для обработки двоичных чисел, задаваемых двоичными сигналами, и может быть использован в системах цифровой вычислительной техники как средство арифметической обработки дискретной информации. Вычитатель по модулю q содержит два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ (11, 12), два элемента И (21, 22), два элемента НЕ (31, 32) и два мажоритарных элемента (41, 42). За счет указанных элементов обеспечивается реализация операции (А-В) mod q при q=2 либо при q=3, где А, В (0≤A<q, 0≤B<q) есть (log2(2×q-2))-разрядные двоичные числа. 1 ил.

Description

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

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

К причине, препятствующей достижению указанного ниже технического результата при использовании известных вычитателей по модулю q, относятся ограниченные функциональные возможности, обусловленные тем, что не обеспечивается реализация операции (А-В)mod q при q=3.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип вычитатель по модулю q (рис. во второй снизу строке таблицы на рис. 3.35 в книге Токхейм Р. Основы цифровой электроники. М.: Мир, 1988 г.), который содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и реализует операцию (A-B)mod q при q=2, где А, В (0≤A≤q, 0≤В≤q) есть (log₂(2 × q - 2))-разрядные двоичные числа, задаваемые двоичными сигналами.

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, обусловленные тем, что не обеспечивается реализация операции (А-В)mod q при q=3.

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

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

элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединены соответственно с первым, вторым входами j-го элемента И и входом j-го элемента НЕ, а первый, второй, третий входы и выход j-го мажоритарного элемента соединены соответственно с выходами j-х элементов НЕ, И, выходом (3-j)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и j-м выходом вычитателя по модулю q, второй, третий и первый, четвертый входы которого соединены соответственно с первым, вторым входами первого и первым, вторым входами второго элементов ИСКЛЮЧАЮЩЕЕ ИЛИ.

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

Вычитатель по модулю q содержит элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 1₁, 1₂, элементы И 2₁, 2₂, элементы НЕ 3₁, 3₂ и мажоритарные элементы 4₁, 4₂, причем первый, второй входы и выход элемента 1_j

соединены соответственно с первым, вторым входами элемента 2_j и входом элемента 3_j, а первый, второй, третий входы и выход элемента 4_j соединены соответственно с выходами элементов 3_j, 2_j, 1_3-j, и j-м выходом вычитателя по модулю q, второй, третий и первый, четвертый входы которого соединены соответственно с первым, вторым входами элемента 1₁ и первым, вторым входами элемента 1₂.

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

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

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

Claims

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