Устройство для определения числа сочетаний

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах, рев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 ил. (Л

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

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

РЕСПУБЛИН (19) 01) AS)) 4 G 06 F 15/20

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

flO ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITHA

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

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 3882067/24-24 (22) 08.04.85 (46) 23.07.86. Бюл. 9 35 (72) В.А.Лукоянов, Т.П.Жигулева и Н.Г.Лукоянова (53) 681.323 (088.8) (56) Авторское свидетельство СССР

9 903891, кл. G 06 F 15/31, 1980.

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

9 1140127, кл. G 06 F 15/31, 1983. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА СОЧЕТАНИЧ (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах, решающих комбинаторные задачи, связанные с вычислением числа сочетаний. Целью изобретения является повышение быстродействия устройства. Устройство содержит блок 13 сравнения, блок 18 деления, блок 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 ил.

29 1 Ж

1259283

1 К вЂ” i-1)

П

С =П 1 к

1=1

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

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

На фиг.l приведена схема устройства; на фиг.2 — временная диаграмма

его работы.

Устройство содержит вход 1 пуска, регистр 2, элемент 3 задержки, генератор 4 тактовых импульсов, регистр

5, блок 6 элементов И, элемент 7 задержки, элемент 8 задержки, блок 9 элементов И, блок 10 вычитания, блок

11 элементов И, счетчик 12, блок 13 сравнения, блок 14 элементов И, !5 элемент 15 задержки, блок 16 элементов И, блок 17 элементов И, блок 18 деления, блок 19 элементов И, регистр 20, блок 21 элементов И, элемент 22 задержки, блок 23 умножения, 20 блок 24 элементов И, блок 25 элементов И, элемент 26 задержки, регистр

27, выход 28 и входы 29 и 30. устройства. ,и

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

K — (; - !) K - (Ь- - 1) 1

1; Т;, где. 1 — текущее состояние счетчика

2 на 1 -й итерации, таким образом, . что где 1 — знак произведения.

Перед началом работы устройства производится запись в регистр 2 числа К в двоичном коде, причем j fog Kl+,,+ 1 m а в регистр 5 — числа в дво1ичном коде ()fog nt + l < m)

Работа устройства начинается по команде "Пуск", которая подается на вход 1 пуска. По этой команде производится начальная установка блока

10 вычитания, блока 18 деления, блока 23 умножения, счетчика 12 и регистра 20 в нулевое состояние, а .в регистр 2? записывается единица в двоичном коде. Одновременно сигнал

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

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

1, а п -й — в состояние, равное n), устанавливает в состояние Й1. Потенциалы двоичного кода состояния счетчика подаются на входы соответственно блока 16 элементов И, блока )7 элементов И и блока 19 элементов И.

Одновременно тактовый импульс поступает на входы соответственно элементов 7 и 8 задержки . Сигнал с выхода элемента 7, задержанный в основном на время срабатывания счетчика 12, поступает одновременно на входы соответственно блоков 6, 1, 9 и 17 элементов И и вход элемента

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

Пусть. числа не равны. Тогда код числа из регистра 2 поступает через блок 6 элементов И на вход блока, 10 вычитания, на второй вход которого подается двоичный код состояния счетчика предыдущей итерации, хранившийся в регистре 20 (на первой итерации хранился О, записанный при начальной установке устройства) . Таким образом, на выходе блока вычи. — . тания имеют место потенциалы, соответствующие двоичному коду разности К вЂ” 1; (на первой итерации К-О).

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

3 1259283 4 вход регистра 20, где он записывается. На i -й итерации импульс, за. держанный на элементе 15, поступая на соответствующие входы блоков !4 и 19 элементов И, обеспечивает прохождение через них соответственно с выхода блока вычитания двоичного кода числа и -(„, (на первой итерации .

К-0) и кода текущего состояния счетчика {на первой итерации 1) на

1 входы блока 18 деления. Блок деления осушеетвляет вычисление частного

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

Одновременно импульс с выхода элемента 15 задержки поступает на вход элемента 22 задержки, где задерживается на время, определяемое в основном временем срабатывания блока деления. Сигнал с выхода элемента задержки поступает соответственно на входы блоков 21 и 24 элементов И и вход элемента 26 задержки, разрешая тем самым прохождение на входы блока 23 умножения с выхода блока деления двоичного кода числа и-6. / п — о — — ((— — — на первой итерации), а с ;/ . 30

На 1l -й итерации вычислейия на выходе счетчика 12 образуется код . 4> состояния, соответствующий числу = n. В результате блок сравнения при 1„ = n формирует сигнал, который, йоступая в генератор 4, прекращает формирование тактовых импуль- 50 сов. Вместе с этим íà n --й "итерации будут выполнены все действия, описанные для -й итерации, Таким образом, в регистре 27 будет накоплено в двоичном коде произведение и г n" "(i-1)

С =I

f(. ° Э

1=!

1 выхода регистра 27 — кода числа

n- f- — (1 — на первой итерации). Блок

1-l умножения осуществляет операцию умножения двух двоичных чисел, резульи f - 11 1 - и о тат которой (1 — на

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

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

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

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

12592

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

Фиг. 2

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

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

Редактор Н,ЛУола

Заказ 5124/48

Тираж 671

ВНИИПИ Государственного по делам изобретений

113035, Москва, Ж-35, Раушская

Подписное комитета СССР и открытий наб., д.4/5

Производственно-полиграфическое предлриятие, r.Óæãîðîä, ул.Проектная,4

S с

1 !

5 (ф

22

Я

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