УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ N ЧИСЕЛ ПО МОДУЛЮ Российский патент 1999 года по МПК G06F7/72 G06F7/49 

Описание патента на изобретение RU2131618C1

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

Известно устройство (аналог) (авт. свид. СССР 1571583, МКИ G 06 F 7/72, Б. И. N 22, 1990), содержащее дешифраторы, группы элементов И, элементы ИЛИ, сумматор по модулю два, элементы И, элементы НЕ, группы элементов ИЛИ, коммутатор, шифраторы. Недостаток устройства - низкое быстродействие выполнения модульной операции.

Известно также устройство (аналог) (авт. свид. СССР N 1689949, МКИ G 06 F 7/72, Б.И. N 41, 1991 г.), содержащее дешифраторы, два элемента НЕ, элемент ИЛИ-НЕ, три группы элементов ИЛИ, коммутатор, три группы элементов И, шифратор. Недостаток устройства - низкое быстродействие выполнения модульной операции.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (авт. свид. СССР N 1599857, МКИ G 06 F 7/72, Б.И. N 38, 1990 г.), содержащее дешифратор, кольцевой регистр сдвига, блоки элементов И, шифратор, элемент запрета, вычитатель по модулю, блок элементов ИЛИ, приемный регистр, схему сравнения и счетчик. Недостаток устройства - низкое быстродействие выполнения модульной операции.

Недостаток прототипа - низкое быстродействие ввиду того, что модульное сложение двух чисел ограничено величиной второго операнда B. Для сложения N чисел требуется Nxm тактов работы.

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

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

Технический результат достигается тем, что в устройство для сложения N чисел по модулю, содержащее основной дешифратор, шифратор, регистр, регистр сдвига, блок элементов И, выход которого соединен со входом шифратора, выход которого является выходом устройства, введены табличный вычислитель, дополнительные дешифраторы, которые вместе с основным дешифратором образуют группу дешифраторов, группа блоков элементов И, причем информационные входы устройства i-ых двоичных разрядов m - модуль устройства j-ых чисел соединены с j-ми входами i-ых дешифраторов группы, выходы которых соединены с первыми входами соответствующих боков элементов И группы, вторые входы которых соединены с выходами соответствующих разрядов регистра сдвига, последний разряд которого соединен с первым входом блока элементов И, а тактовый вход соединен с тактовым входом устройства, выходы блоков элементов И группы соединены с первым входом табличного вычислителя, второй вход которого соединен с выходом регистра, а выход - со вторым входом блока элемента И и входом регистра.

Сущность изобретения заключается в проведении поразрядного модульного сложения N чисел за ]log2m[ тактов (m - модуль устройства) и при ]log2m[ < (N-1) происходит повышение быстродействия выполнения операции. Представим модульную сумму N двоичных чисел в виде

где ηij - соответствующее значение (0 или 1) i-го двоичного разряда числа αj.
Операция, которая заключена в квадратные скобки в выражении (1), реализуется с использованием группы 2 дешифраторов. Заключительная часть модульной операции производится за ]log2m[ на табличном 7 вычислителе. Время проведения операции не зависит от числа слагаемых и определяется величиной модуля m устройства. Дешифраторы 2 группы преобразует код соответствующих i-ых разрядов N чисел в соответствующую модульную сумму (с учетом веса разрядов), представленную в позиционном коде. В частности, при N=5 и m=7 число дешифраторов 2 группы - два и они реализуют таблицу.

Иначе говоря, дешифраторы 2 группы производят преобразование кода числа единиц на входных шинах (с учетом веса разряда) в модульный унитарный код. Эта операция может быть выполнена также на программируемых логических матрицах. Устройство может быть реализовано для любого модуля. Количество входных шин дешифраторов 2 группы равно числу слагаемых N, а выходные шины (число которых - m) скоммутированы так, чтобы выполнялось выражение в квадратных скобках из (1). Табличный 7 вычислитель реализует функцию сложения двух чисел по модулю устройства. Регистр 4 сдвига содержит ]log2m[ разрядов, а регистр 8 - m разрядов.

Следует отметить, что для сложения N чисел по модулю при табличном способе требуется (N-1) тактов, а в данном случае нужно ]log2m[ тактов. Если ] log2m[ < (N-1), то быстродействие заявляемого устройства превышает табличный вариант обработки числовой информации. С ростом отношения количества суммируемых чисел по отношению к разности модуля устройства выигрыш в быстродействии нарастает.

На чертеже представлена структурная схема устройства, где: 1ij - информационные входы устройства m - модуль устройства; I = [log2m] ; j = 1, N); 2 - группа дешифраторов; 3 - группа блоков элементов И; 4 - регистр сдвига; 5 - блок элементов И; 6 - тактовый вход устройства; 7 - табличный вычислитель; 8 - регистр; 9 - шифратор; 10 - выход устройства.

Информационные входы 1 устройства i-ых двоичных разрядов i-ых двоичных разрядов m - модуль устройства) j-ых чисел соединены с j-ми входами j-ых дешифраторов 2 группы, выходы которых соединены с первыми входами соответствующих блоков 3 элементов И группы, вторые входы которых соединены с выходами соответствующих разрядов регистра 4 сдвига, последний разряд которого соединен с первым входом блока 5 элементов И, а тактовый вход соединен с тактовым входом 6 устройства, выходы блоков 3 элементов И группы соединены с первым входом табличного 7 вычислителя, второй вход которого соединен с выходом регистра 8, а выход - с входом регистра 8 и вторым входом блока 5 элементов И, выход которого соединен с входом шифратора 9, выход которого является выходом 10 устройства.

Рассмотрим работу устройства. На информационные входы 1ij устройства поступают двоичные коды N чисел. На N входов нулевого дешифратора 2 группы поступают нулевые разряды N чисел.

На его выходе образуется частичная модульная сумма вида (см (1)), ввиду того, что 2i = 20 = 1. Одновременно, на N входов каждого из оставшихся дешифраторов 2 группы поступают соответствующие двоичные разряды N чисел, образуя на выходах частичные модульные суммы. На выходе [log2m]-го дешифратора 2 группы образуется в унитарном коде число

где I = [log2m] . Эти числа поступают на первые входы соответствующих блоков 3 элементов И группы. Первоначально в нулевом разряде регистра 4 сдвига была произведена запись единицы, которая поступает на второй вход нулевого блока 3 элементов И группы и данная частичная модульная сумма в унитарном коде поступает на первый вход табличного 7 вычислителя. В исходном состоянии в регистре 8 записано число ноль в унитарном коде, следовательно на второй вход табличного 7 вычислителя поступает ноль. На первом такте работы производится сложение с нулем. Полученный результат с выхода табличного 7 вычислителя поступает на вход регистра 8 и записывается в унитарном коде. С тактового входа 6 устройства поступает импульс и единица в регистре 4 сдвига смещается на один разряд. На второй вход первого блока 3 элементов И поступает сигнал и частичная модульная сумма с выхода первого дешифратора 2 группы поступает на первый вход вычислителя 7, на второй вход которого поступает число с выхода регистра 8. Происходит модульное сложение двух частичных сумм. Процесс повторяется. Когда единица в регистре 6 сдвига поступает в последний [log2m]-ый разряд, открывается блок 5 элементов И. При этом результат модульного сложения N чисел в унитарном коде поступает на вход шифратора 9, с выхода которого в двоичном коде поступает на выход 10 устройства.

Рассмотрим пример конкретного выполнения модульного сложения при m=7 и N= 5. Пусть α1 = 3 = 0112, α2 = 6 = 1102, α3 = 5 = 1012, α4 = 2 = 0102, α5 = 1002.

В исходном состоянии нулевой разряд регистра 4 сдвига содержит единицу, остальные разряды - нули, а в регистре 8 записано число ноль в унитарном коде. На информационные входы 1ij устройства поступают двоичные коды пяти чисел. На пять входов нулевого дешифратора 2 группы поступают нулевые разряды пяти чисел, образуя входной код 001012 = 5, на выходе будет число 2 в унитарном коде (см. таблицу). Входной код первого дешифратора 2 группы 010112, выходной - число 6, на входе второго дешифратора 2 группы код 101102, а на выходе - число 5 (см. таблицу). Через открытый нулевой блок 3 элементов И группы число 2 поступает в унитарном коде на первый вход табличного 7 вычислителя. Следует отметить, что коды чисел, поступающие на вход вычислителя 7, - унитарные. На второй вход вычислителя 7 поступает код числа 0. Результат, число 2, поступает с его выхода на запись в регистр 8. С тактового входа 6 устройства поступает импульс и единица в регистре 4 сдвига смещается на один разряд. При этом на первый вход вычислителя поступает число 6 с выхода открытого первого блока 3 элементов И группы, на второй вход вычислителя 7 поступает с регистра 8 код числа 2. С выхода вычислителя 7 результат модульного сложения, равный коду числа 1, записывается в регистр 8. Единица с выхода регистра 4 сдвига поступает на второй вход второго блока 3 элементов И. В этом случае на первый вход вычислителя 7 поступает код числа 5, а на второй вход - код числа 1. На выходе табличного 7 вычислителя будет код числа 6. Результат сложения пяти чисел по модулю семь через открытый блок 5 элементов И и далее через шифратор 9 в виде 1102 поступает на выход 10 устройства. Сложение производится за 3 такта, а в прототипе - за 4 такта. Проверка: (3 + 6 + 5 + 2 +4)mod 7 = 6.1

Похожие патенты RU2131618C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ N ЧИСЕЛ ПО МОДУЛЮ P 2000
  • Овчаренко Л.А.
RU2188448C2
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов И.М.
  • Гульбин С.С.
RU2137181C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1996
  • Ирхин В.П.
RU2110087C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Обухов А.Н.
  • Гульбин С.С.
RU2145112C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов И.М.
  • Гульбин С.С.
RU2143723C1
АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ПО МОДУЛЮ 1999
  • Ирхин В.П.
  • Овчаренко Л.А.
  • Болкунов А.Н.
  • Долгачев А.А.
RU2157560C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ 1995
  • Ирхин В.П.
RU2109326C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА 1996
  • Ирхин В.П.
RU2110147C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ 1999
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов М.А.
  • Долгачев А.А.
  • Крюков Ю.Г.
RU2156998C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА 1999
  • Ирхин В.П.
  • Долгачев А.А.
  • Крюков Ю.Г.
RU2157589C1

Иллюстрации к изобретению RU 2 131 618 C1

Реферат патента 1999 года УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ N ЧИСЕЛ ПО МОДУЛЮ

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных структурах, функционирующих в модулярной системе счисления. Технический результат изобретения заключается в повышении быстродействия выполнения модульных операций. Технический результат достигается за счет введения табличного вычислителя, дешифраторов, группы блоков элементов И в устройство, содержащее регистр сдвига и шифратор. Сущность изобретения состоит в проведении поразрядного модульного сложения N чисел за ] log2m[ тактов (m - модуль устройства). При ]log2m[ (N - 1) происходит повышение быстродействия выполнения операции. 1 ил., 1 табл.

Формула изобретения RU 2 131 618 C1

Устройство для сложения N чисел по модулю, содержащее основной дешифратор, шифратор, регистр сдвига, блок элементов И, выход которого соединен со входом шифратора, выход которого является выходом устройства, отличающееся тем, что в него введены табличный вычислитель, дополнительные дешифраторы, которые вместе с основным дешифратором образуют группу дешифраторов, группа блоков элементов И, причем информационные входы устройства i-х двоичных разрядов m - модуль устройства) j-х чисел соединены с j-ми входами i-х дешифраторов группы, выходы которых соединены с первыми входами соответствующих блоков элементов И группы, вторые входы которых соединены с выходами соответствующих разрядов регистра сдвига, последний разряд которого соединен с первым входом блока элементов И, а тактовый вход соединен с тактовым входом устройства, выходы блоков элементов И группы соединены с первым входом табличного вычислителя, второй вход которого соединен с выходом регистра, а выход - с вторым входом блока элементов И и входом регистра.

Документы, цитированные в отчете о поиске Патент 1999 года RU2131618C1

Устройство для сложения и вычитания чисел по модулю 1988
  • Глушков Валерий Иванович
  • Долгов Виктор Иванович
  • Краснобаев Виктор Анатольевич
  • Кононова Ирина Викторовна
  • Сахно Анатолий Иванович
SU1599857A1
SU 1487035 A1, 15.06.89
Арифметическое устройство по модулю 1991
  • Краснобаев Виктор Анатольевич
  • Ирхин Валерий Петрович
  • Можаев Николай Иванович
  • Кукушкин Михаил Николаевич
  • Квасов Михаил Владимирович
  • Приходько Игорь Викторович
SU1775721A1
Арифметическое устройство по модулю 1988
  • Фоменко Олег Николаевич
  • Краснобаев Виктор Анатольевич
  • Ирхин Валерий Петрович
  • Журавлев Александр Александрович
  • Куцый Сергей Иванович
  • Иванов Сергей Викторович
  • Панков Владимир Михайлович
SU1571583A1
Устройство для вычитания по модулю 1989
  • Фоменко Олег Николаевич
  • Краснобаев Виктор Анатольевич
  • Ирхин Валерий Петрович
  • Журавлев Александр Александрович
  • Куцый Сергей Иванович
  • Иванов Сергей Викторович
  • Гладченко Сергей Олегович
SU1689949A1
RU 94035322 A1, 20.07.96.

RU 2 131 618 C1

Авторы

Ирхин В.П.

Даты

1999-06-10Публикация

1997-12-04Подача