Устройство для вычисления биномиальных коэффициентов Советский патент 1989 года по МПК G06F7/38 

15

О)

ел

со

4

а

00

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

Цель изобретения - упрощение устройства.

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

Устройство содержит генератор 1 тактов, элемент И 2, счетчик 3, сумматор 4, регистр 5, преобразователь б двоичного кода в позидионньгй код, группу 7 элементов И 8, элемент 1-ШИ 9 схему 10 сравнения, счетчик 11, элемент 1ШИ 12, триггер 13, регистр 14, вход 15 числа перебираемых элементов вход 16 числа элементов в сочетании, вход 17 запуска, вход 18 начальной уЬтановки, информационный выход 19 и выход 20 окончания работы.

В з стройстве вычисляются биноми-

.альные коэффициенты С (п m 4 М, число разрядов счетчика 3), Значения т,, п перед началом работы записываются с входов 15 и 16 в k-pa3 рядные регистры 5 и 14 (М : 2 - 1).

Преобразователь 6 преобразует k-раз- 2ЯДНЫЙ двоичньш код та в М-разрядный позиционный код: нули в группе m младших разрядов и единихцз в группе М-тп старшж разрядов. В счетчике 3 последовательно, начиная с нулевогоj перебираются сочетания из М элементов Число элементов в сочетании равно числу единичных разрядов счетчика 3 и подсчитывается с мматором 4. Группа 7 элементов И 8 совместно с элементом ШШ 9 позволяет зафиксировать момент появления единицы в (т+1)-м разряде счетчика 3, что используется как признак окончания перебора из m элементов (т младших разрядов счетчика 3) - единичный сигнал на выходе 20.

Схема 10 сравнения обеспечивает сравнение числа е,диниц в очередном сочетании, сформированном счетчиком 3 с требуемым значением п. В случае . равенства этих значений к содержимому счетчика 11 прибавляется единица.

К моменту окончания перебора-на выходе 19 формируется значение С , Триггер 13 необходим для управления работой устройства. Его установка

в единичное состояние осу1дествляется подачей сигнала на запускающий вход 17. При этом разрешается занесение значений т, п в регистры 5 и 14 и поступление тактовых импульсов через элемент И 2 на счетный вход счетчика 3. При начальной установке устройства (вход 18) или по окончании перебора (выход 20) триггер 13 сбрасывается в нулевое состояние.

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

Устройство для вычисления биномиальных коэффициентов ,- содержащее первый и второй регистры, первый счетчик, схему cpaвнe шя, группу элементов И, генератор тактов, причем информационные входы первого и второго регистров являются соответственно входом числа перебираемых элементов и входом числа элементов в сочетании устройства, выход второго регистра подключен к первому входу схемы сравнения, входы начальной установки первого и второго регистров и первого счетчика соединены с входом начальной установив устройства, отличающее- с я тем, что, с целью зшрощения устройства, оно содержит второй счетчик, сзгмматор, триггер, преобразователь двоичного кода в позиционный код, элемент И, два элемента ИЛИ, причем выход генератора тактов подключен к первому входу элемента И, выход элемента И подключен к счетному входу первого счетчика, разрядные выходы первого счетчика подключены к первым входам соответствующих элементов И группы и входам еумматора, выход c S T-iMaTopa подключен к второму входу cxeribt сравнения, выход схемы сравнения подключен к счетног у входу второго счетчшса, выход второго счетчика является информационным выходом устройства, выход первого регистра подключен к входу преобразователя двоичного, кода в позиционный-кодj разрядные выходы которого.подключены к вторым входам соответствуютдих элементов И гpyппЫj выходы всех элементов И группы подключены к-соответствующим входам первого элемента ИЛИ, выход первого элемента ИЛИ является выходом окончания работы устройства и подключен к первому входу второго элемента ИЛИ, второй вход второго

J15134686

элемента ИЛИ и вход начальной установ™вход триггера, явгьчется входом запуски второго счетчика соединены с вхо-ка устройства,; выход триггера подклю- дом начальной установки устройства,чен к второму входу элемента И и уп- выход второго элемента ИЛИ подключен -:равляющда выходам занесения инАорма- к нулевому входу триггера, единичныйции первого, и второго регистров.

Изобретение относится к области автоматики и вычислительной техники и может быть применено в специализированных вычислительных машинах, решающих комбинаторные задачи, связанные с вычислением биномиальных коэффициентов. Целью изобретения является упрощение устройства. Устройство содержит регистры 5, 14, счетчики 3, 11, сумматор 4, схему сравнения 10, преобразователь 6 двоичного кода в позиционный код, триггер 13, элементы И 2, 8, ИЛИ 9, 12. Ввод преобразователя кодов, сумматора и второго счетчика в состав устройства позволяет сократить общие аппаратурные затраты по сравнению с прототипом, так как при этом исключаются блоки вычитания, деления, умножения, регистр и пять групп элементов И. 1 ил.