Устройство для сложения n чисел по модулю

 

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

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

Известно устройство (аналог) (авт. свид. СССР 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 чисел за ]log₂m[ тактов (m - модуль устройства) и при ]log₂m[ < (N-1) происходит повышение быстродействия выполнения операции. Представим модульную сумму N двоичных чисел в виде где η_ij - соответствующее значение (0 или 1) i-го двоичного разряда числа α_j. Операция, которая заключена в квадратные скобки в выражении (1), реализуется с использованием группы 2 дешифраторов. Заключительная часть модульной операции производится за ]log₂m[ на табличном 7 вычислителе. Время проведения операции не зависит от числа слагаемых и определяется величиной модуля m устройства. Дешифраторы 2 группы преобразует код соответствующих i-ых разрядов N чисел в соответствующую модульную сумму (с учетом веса разрядов), представленную в позиционном коде. В частности, при N=5 и m=7 число дешифраторов 2 группы - два и они реализуют таблицу.

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

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

На чертеже представлена структурная схема устройства, где: 1_ij - информационные входы устройства m - модуль устройства; I = [log₂m] ; 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 устройства.

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

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

Рассмотрим пример конкретного выполнения модульного сложения при m=7 и N= 5. Пусть α₁ = 3 = 011₂, α₂ = 6 = 110₂, α₃ = 5 = 101₂, α₄ = 2 = 010₂, α₅ = 100₂.

В исходном состоянии нулевой разряд регистра 4 сдвига содержит единицу, остальные разряды - нули, а в регистре 8 записано число ноль в унитарном коде. На информационные входы 1_ij устройства поступают двоичные коды пяти чисел. На пять входов нулевого дешифратора 2 группы поступают нулевые разряды пяти чисел, образуя входной код 00101₂ = 5, на выходе будет число 2 в унитарном коде (см. таблицу). Входной код первого дешифратора 2 группы 01011₂, выходной - число 6, на входе второго дешифратора 2 группы код 10110₂, а на выходе - число 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 в виде 110₂ поступает на выход 10 устройства. Сложение производится за 3 такта, а в прототипе - за 4 такта. Проверка: (3 + 6 + 5 + 2 +4)mod 7 = 6.1

Формула изобретения

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3