Устройство для вычисления биномиальных коэффициентов

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУ БЛИН (,5ц 4 C. 06 F 15/20 жмюми

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГИНТ СССР

1 (21) 4281845! 24-24 (22) 13. 07. 87 (46) 07.10.89. Б . 1.- 37 (72) З.И. Волосников и О.А. Асеев (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР

Р 1008750, кл. G 06 F 15/31, 1981.

Авторское свидетельство СССР

Ф 1259283, кл. C Об F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛБНИЯ БИНОИИАЛЬНЫХ КОЭФФИЩПНТОВ (57) Изобретение относится к области автоматики и вычислительной техники и может быть применено в специализированных вычислительных машинах, ре-. шающих комбинаторные задачи, связан„„SU„„1513468 А1

2 ные с вычислением биномиальных коэфЬициентов. Целью изобретения являет- . ся упрощение устройства. Устройство содержит регистры 5, 14, счетчики

3, 11, сумматор 4, схему сравнения

10, преобразователь 6 двоичного кода в позиционный код, триггер 13 элементы И 2, 8, ИЛИ 9, 12. Ввод преобразователя кодов, сумматора и второго счетчика в состав устройства позволяет сократить общие аппаратурные затраты по сравнению с прототипом, так как при этом исключаются блоки вычитания, деления, умножения, . регистр и пять групп элементов И.

1 ил.

1513468

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

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

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

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

В устройстве вычисляются биномиальные коэффициенты С „, (и < m 4 N, ! где М - число разрядов счетчика 3) .

Значения m,, n перед началом работы записываются с входов 15 и 16 в k-разрядные регистры 5 и 14 (М . = 2 — 1) .

fc Преобразователь 6 преобразует k-разрядный двоичный код m в М-разрядный, позиционный код: нули в группе ш

1, младших разрядов и единицы в группе

,М-ш старших разрядов. Б счетчике 3 ,последовательно, начиная с нулевого, перебираются сочетания из М элементов., :Число элементов в сочетании равно числу единичньж разрядов счетчика 3 и подсчитывается сумматором 4. Груп- ®0 па 7 элементов И 8 совместно с элементом ИЛИ 9 позволяет зафиксировать момент появления единицы в (m+1)-и разряде счетчика 3, что используется как признак окончания перебора из m элементов (m младших разрядов счетчика 3) — единичный сигнал на выходе

20.

Схема 10 сравнения обеспечивает сравнение числа единиц в очередноМ

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

К моменту окончания перебора на выИ ходе 19 формируется значение С .

Триггер 13 необходим для управления работой устройства. Его установка в единичное состояние осуществляется подачей сигнала на запускающий вход

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

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

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

1513468 6

1 вход триггера яв."аяется Входом запус ка устройства„. выход триггера подкюпочен к второму входу элемента И и управляюцим выходам занесения информации первого.и второго регистров. элемента ИЛИ и вход начальной установки второго счетчика соединены с входом начальной установки устройства, выход второго элемента ИЛИ подключен к нулевому входу триггера, единичный

Составитель В. Байков

Редактор Н.Яцола Техред М.Дидык Корректор Л. Бескид

Заказ 6081/49 Тираж 668 Подписное

Государственного комитета по изобретениям и открытиям при rKHT CCCp

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101