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

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения - уменьшение количества оборудования. Цель достигается за счет введения с третьего по шестой (16, 3, 17, 4) дешифратор, с пятого по девятый (20, 7, 23, 24, 25) блоков элементов И, второго 9 и третьего 10 табличных вычислителей, регистра 11, первого 12 и второго 13 кольцевых регистров сдвига. Сущность изобретения состоит в использовании группы таблиц при проведении модульной операции, ввиду чего происходит уменьшение числа логических элементов, необходимых для реализации устройства. 1 табл., 1 ил.

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

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

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

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

Недостаток прототипа - большое количество используемого оборудования ввиду того, что число логических элементов коммутатора пропорционально квадрату модуля.

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

Технический результат выражается в уменьшении количества оборудования для выполнения модульной операции сложения. Он достигается тем, что в устройство, содержащее первый и второй дешифраторы, с первого по четвертый блоки элементов И, первый и второй элементы И, первый табличный вычислитель, первый и второй элементы ИЛИ и элемент НЕ, введены с третьего по шестой дешифраторы, с пятого по девятый - блоки элементов И, и второй и третий табличные вычислители, регистр, первый и второй кольцевые регистры сдвига, причем нулевой, первый и второй разряды первого информационного входа устройства соединены с входами соответственно второго, четвертого и шестого дешифраторов, выходы которых соединены с первыми входами соответственно второго, четвертого и шестого блоков элементов И, а их выходы - с соответствующими информационными входами соответственно первого, второго и третьего табличных вычислителей, выходы которых соединены с входами соответствующих разрядов соответственно регистра, первого и второго кольцевых регистров сдвига, нулевой, первый и второй разряды второго информационного входа устройства соединены с входами соответственно первого, третьего и пятого дешифраторов, выходы которых соединены с первыми входами соответственно первого, третьего и пятого блоков элементов И, а их выходы - с соответствующими управляющими входами соответственно первого, второго и третьего табличных вычислителей, выходы переполнения которых соединены с входом разрешения сдвига первого кольцевого регистра сдвига, с первым входом первого элемента ИЛИ и с первым входом второго элемента ИЛИ, выход которого соединен с вторыми входами седьмого, восьмого и девятого блоков элементов И, первые входы которых соединены с выходами соответственно второго, первого кольцевых регистров сдвига и регистра, а выходы - с соответствующими управляющими выходами соответственно третьего, второго и первого табличных вычислителей, выходы готовности переполнения второго и третьего табличных вычислителей соединены с первыми входами соответственно первого и второго элементов И, выходы которых соединены с вторыми входами соответственно первого и второго элементов ИЛИ, выход первого элемента ИЛИ соединен с входом разрешения сдвига второго кольцевого регистра сдвига и с вторым входом второго элемента И, вход разрешения сдвига первого кольцевого регистра сдвига соединен с вторыми входами первого, второго, третьего, четвертого, пятого и шестого блоков элементов И, выход второго элемента ИЛИ соединен с нулевыми информационными входами второго и третьего табличных вычислителей, с (d³ - m)-м (d - основание системы счисления, m - модуль операции) информационным входом первого табличного вычислителя и с входом элемента НЕ, выход которого является управляющим выходом устройства.

Сущность изобретения состоит в использовании группы таблиц при проведении модульной операции, ввиду чего происходит уменьшение числа логических элементов, необходимых для реализации устройства. Общее число этих элементов N в трех прямоугольных таблицах со стороной d с учетом симметрии при модуле операции m составляет Найдем оптимальную величину d, при которой N минимально: Рассмотрим реализацию основных узлов устройства при m = 509. В этом случае d = 8, а кольцевые регистры 13, 12 и регистр 11 содержат по восемь разрядов. Для выполнения операции модульного сложения необходимо иметь три одинаковые таблицы.

В приведенной таблице приняты следующие обозначения: величины α_i и β_i - разряды соответствующих операндов A и B, (i = 0,2 в данном случае). Клетки таблицы, в которых результат операции отмечен знаком "+", объединены в выход переполнения, а клетки, отмеченные знаком "-", - а выход готовности переполнения. Операция модульного сложения производится таблично-групповым методом в d-ичной системе счисления, результат которой располагается в регистре 11 и кольцевых регистрах сдвига 12 и 13. Первый 12 и второй 13 концевые регистры сдвига служат для коррекции результата операции при появлении сигналов переполнения. Если сигнал переполнения возникнет в старшем (втором) разряде, то производится ввод суммы операндов в диапазон (модуль устройства) путем последующего сложения с величиной (d³ - m). При d, равной степени числа два, в регистрах 13, 12 и 11 результат модульного сложения после преобразования его шифраторами представляется в двоичной системе счисления. Также в этом случае удобно подавать входные операнды на информационные 1, 14 входы устройства. В частности, при d = 8 = 2³ это будут группы по три двоичных разряда операндов, представленных в двоичной системе счисления. Следует отметить, что m≅d³ - 1, а выбором величины d можно обеспечить d³ - m<d, при этом приведение результата к модулю устройства реализуется коммутацией только в нулевом разряде устройства, хотя это критично. Данный подход можно использовать и в обычных двоичных сумматорах (без приведения к модулю устройства) для повышения быстродействия (уменьшения числа переносов между разрядами) с использованием таблиц. Выбором величины d можно регулировать соотношение между аппаратными затратами и быстродействием Если использовать этот подход при работе в полиадической системе счисления, то возрастет неоднородность структуры.

Возможность достижения положительного эффекта от использования данного изобретения состоит в уменьшении количества оборудования, применяемого при построении табличных устройств модулярной арифметики. В случае трех разрядов зависимость числа логических элементов таблиц от модуля устройства пропорциональна Этот эффект существенно возрастает с ростом числа разрядов (таблиц в группе).

На чертеже представлена структурная схема устройства, где 1 - первый информационный вход (1_i - разряды; i = 0,2) устройства, 2 - второй дешифратор, 3 - четвертый дешифратор, 4 - шестой дешифратор, 5 - второй блок элементов И, 6 - четвертый блок элементов И, 7 - шестой блок элементов И, 8 - первый табличный вычислитель, 9 - второй табличный вычислитель, 10 - третий табличный вычислитель, 11 - регистр, 12 - первый кольцевой регистр сдвига, 13 - второй кольцевой регистр сдвига, 14 - второй информационный вход (14_i - разряды; i = 0,2) устройства, 15 - первый дешифратор, 16 - третий дешифратор, 17 - пятый дешифратор, 18 - первый блок элементов И, 19 - третий блок элементов И, 20 - пятый блок элементов И, 21 - первый элемент ИЛИ, 22 - второй элемент ИЛИ, 23 - седьмой блок элементов И, 24 - восьмой блок элементов И, 25 - девятый блок элементов И, 26 - первый элемент И, 27 - второй элемент И, 28 - управляющий вход устройства, 29 - элемент НЕ, 30 - управляющий выход устройства.

Нулевой 1₀, первый 1₁ и второй 1₂ разряды первого 1 информационного входа устройства соединены с входами соответственно второго 2, четвертого 3 и шестого 4 дешифраторов, выходы которых соединены с первыми входами соответственно второго 5, четвертого 6 и шестого 7 блоков элементов И, а их входы - с соответствующими информационными входами соответственно первого 8, второго 9 и третьего 10 табличных вычислителей, выходы которых соединены с входами соответствующим разрядов соответственно регистра 11, первого 12 и второго 13 кольцевых регистров сдвига, нулевой 14₀, первый 14₁ и второй 14₂ разряды второго 14 информационного входа устройства соединены с входами соответственно первого 15, третьего 16 и пятого 17 дешифраторов, выходы которых соединены с первыми входами соответственно первого 18, третьего 19 и пятого 20 блоков элементов И, а их выходы - с соответствующими входами соответственно первого 8, второго 9 и третьего 10 табличных вычислителей, выходы переполнения которых соединены соответственно с входом разрешения сдвига первого 12 кольцевого регистра сдвига, с первым входом первого элемента ИЛИ и с первым входом второго 22 элемента ИЛИ, выход которого соединен с вторыми входами седьмого 23, восьмого 24 и девятого 25 блоков элементов И, первые входы которых соединены с выходами соответственно второго 13 первого 12 кольцевых регистров сдвига и регистра 11, а выходы - с соответствующими управляющими входами соответственно третьего 10, второго 9 и первого 8 табличных вычислителей соединены с первыми входами соответственно первого 26 и второго 27 элементов И, выходы которых соединены с вторыми входами соответственно первого 21 и второго 22 элементов ИЛИ, выход первого 21 элемента ИЛИ соединен с входом разрешения сдвига второго 13 кольцевого регистра сдвига и с вторым входом второго 27 элемента И, вход разрешения сдвига первого 12 кольцевого регистра сдвига соединен с вторым входом первого 26 элемента И, управляющий вход 28 устройства соединен с вторыми входами первого 18, второго 5, третьего 19, четвертого 6, пятого 20 и шестого 7 блоков элементов И, выход второго 22 элемента ИЛИ соединен с нулевыми информационными входами второго 9 и третьего 10 табличных вычислителей, с (d³ - m)-м (d - основание системы счисления, m - модуль операции) информационным входом первого 8 табличного вычислителя и с входом элемента НЕ 29, выход которого является управляющим выходом 30 устройства.

Рассмотрим работу устройства.

Одиночный импульс поступает на управляющий 28 вход устройства, а с его выхода на вторые входы первого 18, второго 5, третьего 19, четвертого 6, пятого 20 и шестого 7 блоков элементов И.

Операнд A = (α₂α₁α₀), представленный в d-ичной системе счисления (d-основание системы) поступает на нулевой 1₀, первый 1₁ и второй 1₂ разряды первого 1 информационного входа устройства. Разряды α₀,α₁ и α₂ с выходов соответственно второго 2, четвертого 3 и шестого 4 дешифраторов в единичном коде поступают на первые входы соответственно второго 5, четвертого 6 и шестого 7 блоков элементов И, с выходов которых сигналы поступают на информационные входы соответственно первого 8, второго 9 и третьего 10 табличных вычислителей. Операнд B = (β₂β₁β₀), представленный в d-ичной системе счисления, поступает на нулевой 14₀, первый 14₁ и второй 14₂ разряды второго 14 информационного входа устройства. Разряды β₀,β₁ и β₂ с выходов соответственно первого 15, третьего 16 и пятого 17 дешифраторов в единичном коде поступают на первые входы соответственно первого 18, третьего 19 и пятого 28 блоков элементов И, с выходов которых сигналы поступают на управляющие входы соответственно первого 8, второго 9 и третьего 11 табличных вычислителей. Предварительный результат операции фиксируется в единичном коде в регистре 11, первой 12 и втором 13 кольцевых регистрах сдвига. Сигнал переполнения в нулевом разряде (первом 8 табличном вычислителе) формируется непосредственно, а в старших разрядах либо непосредственным образом, либо в случае, когда есть сигнал на выходе готовности переполнения (результат операции в данном разряде равен d - 1), а из младшего разряда поступил сигнал переполнения. В первом разряде схемно это реализуется первым 26 элементом И и первым 21 элементом ИЛИ, во втором - вторым 27 элементом И и вторым 22 элементом ИЛИ. Коррекция результата операции производится сигналом переполнения, поступающим на входы разрешения сдвига первого 12 и второго 13 кольцевых регистров сдвига из соответствующих младших разрядов. Если сигнал на выходе второго 22 элемента ИЛИ не будет (нет переполнения по второму разряду), то на выходе элемента НЕ 29 будет сигнал, который поступает на управляющий выход 30 устройства и свидетельствует об окончании модульной операции. В случае наличия сигнала на выходе второго 22 элемента ИЛИ производится сложение промежуточного результата операции с величиной d³ - m), после завершения которого на управляющем выходе 30 устройства будет сигнал. Эта коррекция реализуется путем подачи на управляющие входы первого 8, второго 9 и третьего 10 табличных вычислителей соответственно нулевого, первого и второго разрядов промежуточного результата, а на управляющие входы соответственно поступают величины (d³ - m), 0 и 0. Результат операции в единичном коде d-ичной системы счисления размещается в регистре 11, первом 12 и втором 13 кольцевых регистрах сдвига.

Рассмотрим пример выполнения операции (A + B)modm при m = 509, d = 8, A = 348 и B = 229.

Одиночный импульс поступает на управляющий 28 вход устройства, а с его выхода на вторые входы первого 18, второго 5, третьего 19, четвертого 6, пятого 20 и шестого 7 блоков элементов И. Операнд A = 534₈ поступает на соответствующие разряды 1₂1₁1₀ первого 1 информационного входа устройства. С выхода шестого 4, четвертого 3 и второго 2 дешифраторов сигналы поступают соответственно на пятый, третий и четвертый информационные входы третьего 10, второго 9 и первого 8 табличных вычислителей. Операнд B = 345₈ поступает на соответствующие разряды 14₂14₁14₀ второго 14 информационного входа устройства. С выходов пятого 17, третьего 16 и первого 15 дешифраторов сигналы поступают соответственно на третий, четвертый и пятый управляющие входы третьего 10, второго 9 и первого 8 табличных вычислителей. В нулевом разряде второго 13 кольцевого регистра сдвига, седьмом разряде первого 12 кольцевого регистра сдвига и первом разряде регистра 11 происходит запись единицы (см. табл. ). С выхода переполнения первого 8 табличного вычислите поступает сигнал (см. табл. ) на вход разрешения сдвига первого 12 кольцевого регистра сдвига, производя сдвиг единицы из седьмого разряда в нулевой. Этот сигнал поступает также на второй вход первого 26 элемента И, на первый вход которого поступает сигнал с выхода готовности переполнения второго 9 табличного вычислителя (см. табл.). Сигнал с выхода первого 21 элемента ИЛИ поступает на вход разрешения сдвига второго 13 кольцевого регистра сдвига, производя сдвиг единицы из нулевого разряда в первый. Сигнал с выхода переполнения третьего 10 табличного вычислителя (см. табл.) поступает на открытие седьмого 23, восьмого 24 и девятого 25 блоков элементов И. Промежуточный результат операции поступает на первый, нулевой и первый управляющие входы соответственно третьего 10, второго 9 и первого 8 табличных вычислителей, на нулевой, нулевой и третий (d³ - m = 512 - 509 = 3), информационные входы которых с выхода второго 22 элемента ИЛИ поступают сигналы. В первом разряде второго 13 кольцевого регистра, нулевом разряде первого 12 и четвертом разряде регистра 11 (см. табл.) происходит запись единицы. На выходе элемента НЕ 29 будет сигнал, который свидетельствует о завершении модульной операции.

Проверка: 534₈ + 345₈ = 104₈ (mod 509).

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

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

РИСУНКИ

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