Устройство для решения комбинаторных задач

СОЮЗ СОВЕТСОЦИАЛ ИСТИЧРЕСПУБЛИК ЕСНИХ 72466 А 51)5 (1 06 Р ОПИСАНИЕ ИЗОБРЕТЕНИЯК А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ(21) (22) (46) (/2) ШЕНИЯ КОМБИБюл, В 31ский политехнический чис инст (/1) (53) (56) нов и В С,88)В, Комбина- М.: Ми ляков а раса сче орика дл 1988, прогр с. 3 А 12Изобретение отнтельной технике и ится вычисли жет быть исполь специализирован овано при созданииых устройств обраЦель изобретения тки ормации рение к беспече решаемых задач за сче то 1 с" ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМПРИ ГКНТ СССР 4/22223 31. 05. 8 23089 Владими тут В.Ф.Ром 681.3(0 Липский аммисто40. торское 542/, к ния возможности вычисления и суммирования биномиальных коэффициентов.На фиг,.1 представлена функциональная схема устройства; на фиг,2 конкретный вариант ее выполнения для ш=4 с Функциональной схемой генератора двоичных последовательностей с неубывающим числом единиц.Ключом к достижению цели служитт факт, что смена числа единиц с 1 на 1 в выходном коде генератора(54) УСТРОЙСТВО ДЛЯ РЕНАТОРНЬХ ЗАДАЧ(5/) Изобретение относится к влительной технике и может бытьпольэовано при создании специалрованных устройств обработки иции. Целью изобретения являетсширение класса решаемых задачобеспечения возможности вычислбиномиальных коэффициентов и их сумм. Устроиство содержит триггер,генератор импульсов, генератор ш-разрядных двоичных последовательностейс неубывающим числом единиц, включающий тактовый вход, ш загрузочныхтриггеров и разрядные триггеры, элемент И, два коммутатора, счетчик ивход запуска устройства, 2 ил.,1 табл,двоичных последовательностей, т.е. переход от сочетаний "из ш по 1-1" к сочетаниям из ш по 1 происходит одновременно с установкой значения "0" на выходе 1 с-го загрузочного триггера (загрузочного триггера х-го регистра). Устройство содержит триггер 1, генератор 2 импульсов, генератор 3 и)-разрядных двоичных последовательностей с неубывающим числом единиц, включающий тактовый вход 4, ш загрузочных триггеров 5 и разрядные триггеры 6, элемент И /, первый 8 и второй 9 коммутаторы, счетчик 1 О, . вход 11 запуска устройства, генератор 3 двоичных последовательностей содержащий, (фиг,2) загрузочные триггеры5, разрядные триггеры 6, элементы ИЛИ 12, элементы И 13.Устройство работает следующим образом.5В исходном состоянии устройства три. гер 1 находится в нулевом состоянии, поэтому генератор 2 импульсов заблокирован. Коммутатор 8 соединяет инверсный выход 1-го загрузочного 10 три, гера генратора 3 с вторым входом эпеме;та И, коммутатор 9 соединяет инверсный выход 1-го загрузочного три. гера генератора 3 с входом установки григ; ра в нулевое состояние (1.= 1,2 и;-1, 1=2,3щ; 1 с (,1).При поступлении сигнала на вход 11 запуска устройства триггер 1 переходит в единичное состояние, генератор 3 двоичных последовательностей чстзнанливаетс;: в начальное состояние, пр кот р,и на вчходах эагрузочньк триггеров присутствуют значенияна ьгодах разрядных тригге 11 11 рг в в се С гь от р,з - з нач е ния О 25 (цепи начально,:1 установки не показаны). С выхода генератора 2 поступают тато;з;,1 ;:от.льсь на тактовый вод 4 гене;.атора 3, который вырабатывает на г,иод;.х ,1 нные кодовые комбинации с не тд,ающим чп л и единицПри этапы э: н:; вк:х-д- .ждог. -го загоузо тного триггера, где 1=1,2, т и.:еннется иа "О" на прямом и соо.яетственно "О" на "1" на инверс 35 ном . : оде) в тот момент, когда начинае:ся перебор кодовых комбинаций, что ;ответствует началу счета сочетания С., С момента .1 зменения состоя" ния 1-го загрузочного триггера с его инверсного вы:ода через коммутатор 8 на второй вход элемента И поступает сигнал "1", и тактовые импульсы проходят на счетчик 1 О, Счет заканчивается при .зменении состояния ;.-го за грузочнс го триггера (1 ) 1), поскольку в этот момент с его инверсного выхода сигнал "1" через коммутатор 9 пос:упит на вход установки риггера 1 в нулевое состояние. В результате в счетчике, 10 будет зафиксирован код, равныйС , Отметим, что в течев кние всего периода счета коммутаторы 8 и 9 находятся в Фиксированных позициях.55При ,подключении к элементу И и к входу обнуления триггера 1 соответственно двух загрузочных триггеров с последовательными номерами Е и 1+1 в счетчике 10 будет зафиксированокчисло , Сщ, т.е, биномиальный коэф=" кфициент С . Максимальная вычисляемая сумма биномиальных коэффициентов равна , С = 2 - 2, так как в вычисле 1 ание не включаются тривиальные коэфО 1 дфициенты С, = С = 1 (известно, что ,5 С = 2 ). В качестве коммутаторов 8 и 9 использованы ш-позиционные переключатели.В таблице приведены в виде двоичных массивов все 16 состояний генератора 3 для я=4 (Фиг,2), которые последовательно сменяют друг друга по тактам (левый столбец массива вьходы загрузочных триггеров; остальные элементы,образунцие треугольную матрицу - выходы разрядных триггеров), Выходы генератора 3 формируются как диэъюнкции значений элементов в разрядных столбцах. Из таблицы видно, что состояние:аз"ого загрузочного триггера изменяется за время полного цикла только один раэ, отмечая перехо к началу счета С ск111 новым к,Формула изобретенияУстройство для решения комбинаторных задач, содержащее генератор импульсов, вход запуска которого соединен с выходом триггера, а выход - с тактовым входом ш-разрядного генератора двоичных последовательностей с неубывающим числом единиц и выполненного на группе загрузочных и группе разрядных триггеров, элементах И, ИЛИ, элемент И, вход установки триггера в "1" является входом запуска уст" ройства, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет обеспечения возможности вычисления и суммирования биномиальных коэффициентов, в него введены первый и второй коммута" торы и счетчик, вход которого подключен к выходу элемента И, а выход является выходом устройства, причем первый вход элемента И соединен с выходом генератора импульсов, инверсный выход каждого -го загрузочного триггера генератора двоичных последоват"ьностей (где1,2ш) под16/2466ключен соответственно через первый И и через второй коммутатор - к вхокоммутатор к второму входу элемента ду обнуления триггера. СочетанияЧисло сочетаний Состояния С- Ф Иэ 4 па 0С,-4 Иэ 4 по С ф 6 Ф Ф С4 5 Ф Иэ 4 по 3 С ф 1 Ф Ф Иэ 4 по 4о о о оо о оо оо оо о о0 О 01 О Оо ооооооооо1 О оооо0010оо1 0 00001 0001 001 0 1Составитель В.Романов Техред 11,Сердокова Корректор О,Кравцова Редактор В.анко Заказ 2841 Тираж 381 ПодписноеВНИ 11 П 11 Государственного комитета по изобретениям и открытиям лри ГКНТ СССР 113035, осхвл И 35, Раушская наб д, 4/5 Производственно-издательскии комбинат Патенг", г. Ужгород, ул. Гагарина, 101