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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 191 О 1) 1114 С 06 Г 5/ ЕНИЯ / У 35П.Жигулев етельство СССРР 15/31, 1980,ельство СССРР 15/31, 1983. ОПРЕДЕЛЕНИЯ ЧИСосится к вычис может быть исОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(57) Изобретение отлительной технике и пользовано в устройствах, решающих комбинаторные задачи, связанные с вычислением числа сочетаний. Целью изобретения является повышение быстродействия устройства. Устройство содержит блок 13 сравнения, блок 18 деления, блок 23 умножения, блок 1 О вычитания, четыре регистра 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 ил. г 9 Ж40 Изобретение относится к вычислительной технике.Цель изобретения - повышение быстродействия устройства.На фиг,1 приведена схема устройст ва; на фиг.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. устройства.,11Для вычисления числа сочетаний С иэ К по и используется итеративный метод, основанный на вычислении на каждой итерации до и включительно произведения К- Й; - ) К- ,-1)Т;.,где 1 - текущее состояние счетчика12 на 1 -й итерации, таким образом,, что где П - знак произведения.Перед началом работы устройства производится запись в регистр 2 числа К в двоичном коде, причем 1 од К+, ,+ 16 ш, а в регистр 5 - числа в двоичном коде (1 од и + 1т)Работа устройства начинается по команде "Пуск", которая подается на вход 1 пуска. По этой команде производится начальная установка блока 10 вычитания, блока 18 деления, блока 23 умножения, счетчика 12 и регистра 20 в нулевое состояние, а ,в регистр 2 записывается единица в двоичном коде. Одновременно сигнал"Пуск" через элемент 3 задержки, 55 который обеспечивает задержку сигнала на время, необходимое на осуществление начальной установки блоков устройства, запускает генератор 4тактовых импульсов,Очередной импульс с выхода генератора 4 поступает на счетный вход.счетчика 12, увеличивая его содержимое на единицу первый импульсустанавливает его состояние равным1, а и -й - в состояние, равное и),устанавливает в состояние Й. Потенциалы двоичного кода состояния счетчика подаются на входы соответственно блока 16 элементов И, .блока 17элементов И и блока 19 элементов И.Одновременно тактовый импульспоступает на входы соответственноэлементов 7 и 8 задержки. Сигнал свыхода элемента 7, задержанный в основном на время срабатывания счетчика 12, поступает одновременно навходы соответственно блоков 6, 1,9 и 17 элементов И и вход элемента15 задержки. По этому сигналу двоичный код числа .параллельно подается из регистра 5 через блок 9элементов И на вход блока 13 сравнения, на второй вход которого поступает двоичный код текущего состояния счетчика 12 через блок 17 элементов И. Блок 5 производит, сравнение двух двоичных чисел, Еслисравниваемые числа равны, то блоксравнения формирует сигнал, который, поступая на вход останова генератора 4, запрещает генерированиетактовых импульсов. Если числа неравны, то генератор через время, определяемое периодом следования тактовых импульсов, формирует очередной импульс, и работа устройствапродолжается,Пусть. числа не равны. Тогда код числа из регистра 2 поступает через блок 6 элементов И на вход блока, 10 вычитания, на второй вход которого подается двоичный код состояния счетчика предыдущей итерации, хранившийся в регистре 20 (на первой итерации хранился О, записанный при начальной установке устройства, Таким образом, на выходе блока вычи. - . тания имеют место потенциалы, соответствующие двоичному коду разности К - 1; (на первой итерации К-О). По истечении времени, определяемого длительностью задержки 1 -го тактового импульса элементом 8 задержки., разрешается прохождение двоичного кода состояния счетчика 12 с его вы- хода через блок 16 элементов И навход регистра 20, где он записывается, На-й итерации импульс, задержанный на элементе 15, поступая на соответствующие входы блоков 14 и 19 элементов И, обеспечивает прохождение через них соответственно с выхода блока вычитания двоичного кода числа и -(, (на первой итерации, К) и кода текущего состояния счетчика 1 (на первой итерации 1) на1входы блока 18 деления. Блок деления осушеетвляет вычисление частного 10 и-о(на первой итерации - в )1 Одновременно импульс с выхода элемента 15 задержки поступает на вход элемента 22 задержки, где задерживаетсяна время, определяемое в основном временем срабатывания блока деления. Сигнал с выхода элемента задержки поступает соответственно на входы блоков 21 и 24 элементов И и вход элемента 26 задержки, разрешая тем самым прохождение на входы блока 23 умножения с выхода блока деления двоичного кода числа и-Ь/ п - о----- на первой итерации), а с.30 выхода регистра 27 - кода числа п.- (1 - на первой итерации). Блок умножения осуществляет операцию умножения двух двоичных чисел, резульп;., и -6п-о тат которой( 1 - на11-первом шаге) в двоичном коде поступает через блок 25 элементов И, открытый по сигналу от элемента 26 задержки, на вход регистра 27, где записы вается и хранится до следующего шага работы устройства. На й -й итерации вычислейия на . выходе счетчика 12 образуется код . 4 состояния, соответствующий числу= и. В результате блок сравнения при 1 = и формирует сигнал, который, йоступая в генератор 4, прекращает формирование тактовых импуль сов, Вместе с этим на в -й итерации будут выполнены все действия, описанные для-й итерации, Таким образом, в регистре 27 будет накоплено в двоичном коде произведение 55 равное числу сочетаний из К по и, которое можно снять на выход 28 в двоичном параллельном коде.Ф о р м у л а изобретенияУстройство для определения числа сочетаний, содержащее первый регистр, четыре блока элементов И, элементы задержки, о т л и ч а ю - щ и й с я тем, что, с целью повышения быстродействия, в него введены блок вычитания, блок деления, блок умножения, блок сравнения, счетчик, второй, третий и четвертый регистры, генератор тактовых импульсов и шесть блоков элементов И, причем входы первого и второго регистров являются соответственно первым и вторым входами установки начальных значений устройства, вход пуска которого подключен к установочным входам блока вычитания, блока деления, блока умножения, счетчика, третьего и четвертого регистров и первого элемента задержки, выход которого соединен с входом запуска генератора тактовых импульсов, вход останова которого подключен к выходу блока сравнения, а выход соединен с входами второго и третьего элементов задержки и с счетным входом счетчика, первые входы первого и второго блоков элементов И соединены соответсвенно с выходами разрядов первого и второго регистров, выходы первого и третьего блоков элементов И соединены соответсвенно с первым и вторым информационными входами блока вычита- . ния, выход которого подключен к первым входам четвертого блока элементов И, выход которого подключен к первому информационному входу блока деления, выход пятого блока элементов И соединен с информационным входом третьего регистра, выходы второго и шестого блоков элементов И соединены соответственно с первым и вторым входами блока сравнения, выход седьмого блока элементов И соединен с вторым информационным входом блока деления, выход которого подключен к первому входу восьмого блока элементов И, выход которого и выход девятого блока элементов И соединены соответственно с первым и вторым информационными входами блока умножения, выход которого подключен к первому входу десятогоаж 671 арственног изобретени 5, Раушска Подписикомитета СССРи открытийнаб., д,4/5 акаэ 5124 Ти ИИПИ Госу по делам113035 оскв оизводственно-полиграфическое предприятие, г,ужгород, ул,Проектная,4блока элементов И, выход которого соединен с информационным входом четвертого регистра, выход которого подключен к выходу устройства и к первому входу девятого блока элементов И, выход третьего регистра подключен к первому входу третьего блока элементов И, выход счетчика подключен к первому входу пятого, шестого и седьмого блоков элементов И, выход второго элемента задержки соединен с вторыми входами первого, второго, третьего и шестого блоков яз ьэлементов И и с входом четвертогоэлемента задержки, выход которогоподключен к вторым входам четвертогои седьмого блоков элементов И и квходу пятого элемента задержки, выход которого подключен к вторым входам восьмого и девятого блоков элементов И и к выходу шестого элемента задержки, выход которого подключен к второму входу десятого блокаэлементов И, выход третьего элемента задержки соединен с вторым входом пятого блока элементов И.