Устройство для определения числа сочетаний Советский патент 1986 года по МПК G06F7/16 

Изобретение относится к вычисли- тельной технике.

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

На фиг.1 приведена схема устройст ва; на фиг.2 - временная диаграмма его работы.

Устройство содержит вход 1 пуска, регистр 2, элемент 3 задержки, генератор 4 тактовых импульсов, регистр 5, блок 6 элементов И, элемент 7 задержки, элемент 8 задержки, блок 9 элементов И, блок 10 вычитания, блок 11 элементов И, счетчик 12, блок 13 сравнения, блок 14 элементов И, элемент 15 задержки, блок 6 элементов И, блок 17 элементов И, блок 18 деления, блок 19 элементов И, регистр 20, блок 21 элементов И, элемент 22 задержки, блок 23 умножения, блок 24 элементов И, блок 25 элементов И, элемент 26 задержки, регистр 27, выход 28 и входы 29 и 30. устройства.

Для вычисления числа сочетаний С из К по п используется итеративный метод, основанный на вычислении на каждой итерации до п включительно произведения

(f; - 1) К - (,м- 1)

,J

€f1-,

текущее состояние счетчика -и итерации, таким образомj,

п

п

1

K.i.liii)

i

где П - знак произведения.

Перед началом работы устройства производится запись в регистр 2 чис, ла К в двоичном коде, причем 3 fog кГ+

.+ , а в регистр 5 - числа в ДвоJH4HOM коде (Jfog п + 1 m)

Работа устройства начинается по команде Пуск, которая подается на вход I пуска. По этой кома нде производится начальная установка блока 10 вычитания, блока 18 деления, блока 23 умножения, счетчика 12 и регистра 20 в нулевое состояние, а

.в регистр 27 записывается единица в двоичном коде-. Одновременно сигнал Пуск через элемент 3 задержки, который обеспечивает задержку сигна - ла на время, необходимое на осуществление начальной установки блоков

устройства, запускает генератор 4 тактовых импульсов.

Очередной импульс с выхода генератора 4 поступает на счетный вход, счетчика 12, увеличивая его содер- жимое на единицу (первый импульс устанавливает его состояние равным 1, а п -и - в состояние, равное п), устанавливает в состояние €), Потен

циалы двоичного кода состояния счетчика подаются на входы соответственно блока 16 элементов И, .блока 17 элементов И и блока 19 элементов И.

Одновременно тактовый импульс поступает на входы соответственно элементов 7 и 8 задержки . Сигнал с выхода элемента 7, задержанный в основном на время срабатывания счетчика 12, поступает одновременно на входы, соответственно блоков 6, М, 9 и 17 элементов И и вход элемента 15 задержки. По этому сигналу двоичный код числа AV параллельно подается из регистра 5 через блок 9 элементов И на вход блока 13 .-сравнения, на второй вход которого поступает двоичный код текущего состояния счетчика 12 через блок 17 элементов И. .Блок 15 производит, срав- нение двух двоичных чисел. Если сравниваемые числа равны, то блок сравнения формирует сигнал, ..который, поступая на вход останова генератора 4, запрещает генерирование тактавьгк импульсов. Если числа не равны, то генератор через время, определяемое периодом следования тактовых импульсов, формирует очередной импульс, и работа устройства

продолжается.

.

Пусть.числа не равны. Тогда код

числа из регистра 2 поступает через блок 6 элe шнтoв И на вход блока, 10 вычитания, на второй вход которого подается двоичный код состояния счетчика предьщущей итерации, хранивщийся в регистре 20 на первой итерации хранился О, записанный при начальной установке устройства. Таким образом, на выходе блока вычи.т тания имеют место потенциалы, соответствующие двоичному коду разности К - f-.j (на первой итерации К-0) . По истечении времени, определяемого длительностью задержки i -го такто- вого импульса элементом 8 задержки, разрешается прохождение двоичного кода состояния счетчика I2 с его вы- хода через блок 16 элементов И на

вход регистра 20, где он записывается. На i -и итерации импульс, задержанный на элементе 15, поступая на соответствующие входы блоков 14 и 19 элементов И, обеспечивает прохождение через них соответственно с выхода блока вычитания двоичного кода числа п - С;,, (на первой итерации . К-0) и кода текущего состояния счетчика (на первой итерации 1) на входы блока 18 деления. Блок деления осушествляет вычисление частного

,„П-Оч

(на первой итерации --).

Одновременно импульс с выхода элемента 15 задержки поступает на вход элемента 22 задержки, где задерживается на время, определяемое в основном временем срабатывания блока деления. Сигнал с выхода элемента задержки поступает соответственно на входы блоков 21 и 24 элементов И и вход элемента 26 задержки, разрешая тем самым прохождение на входы блока 23 умножения с выхода блока деления двоичного кода числа

- о

.„

на первой итерации), а с

кода числа

выхода регистра 27

на первой итерации). Блок

iумножения осуществляет операцию ум; ножения двух двоичных чисел, резуль-

„ п-1, -г п хП-о .

тат которой - f( 1 - на

(-1

:t1

первом шаге) в двоичном коде поступает через блок 25 элементов И, открытый по сигналу от элемента 26 задерж ки, на вход регистра 27, где записы- ваетс я и хранится до следующего шага работы устройства.

На п-и итерации вычисления на выходе счетчика 12 образуется код . jсостояния, соответствующий числу С п. В результате блок сравнения при € п формирует сигнал, который, Поступая в генератор 4, прекращает формирование тактовых импуль- 50 единен с вторым информационным вхосов. Вместе с этим на п-и Ите рации будут выполнены все действия, описанные для ( -и итерации. Таким . образом, в регистре 27 будет накоплено в двоичном коде произведение

с п

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

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

Устройство для определения числа сочетаний, содержащее первьй регистр., четыре блока элементов И,

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

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

0

5

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

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

1 -I

CS

J

26

Редактор Н.Луола

Составитель А.Жер.енов

Техред И.Ходанич Корректор А.Зимокосов

Заказ 5124/48Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035,- Москва, Ж-35, Раушская наб, , д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4

59283

элементов И и с входом четвертого элемента задержки, выход которого подключен к вторым входам четвертого и седьмого блоков элементов И и к входу пятого элемента задержки, выход которого подключен к вторым вхо дам восьмого и девятого блоков элементов И и к выходу шестого элемента задержки, выход которого подклю- 10 чен к второму входу десятого блока элементов И, выход третьего элемента задержки соединен с вторым входом пятого блока элементов И.

Фиг. 2

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