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

 

Сеюэ Советснии

Социапнстнчесннк

Рес у

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ к авторском свидетельств

««903891 (6l ) Дополнительное к авт. санд-ву (22) Заявлено 16.05.80(21) 2927360/18-24 с присоединением заявки J6 (23) Приоритет

Опубликовано 07.02.82. Бюллетень Фе 5 (51)М. Кл.

G 06 F 15/31

3Ьеудвротокикый комитет

СССР аа делан иаобоетеиий и открытий (53) УДК 681.3 (088.8) Дата опубликования описания 09.02.82 (72) Автор изобретения

B. М. Полищук (7!) Заявнтель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

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

Известно устройство для перебора со» четаний, содержащее основной регистр, S запоминающий регистр, вспомогательный регистр, блок управления, триггеры, элементы И и ИЛИ, элементы задержки 513.

Недостатком известного устройства является то, что оно содержит большое î количество элементов, что снижает надежность работы.

Наиболее близким по технической сущности к изобретению является устройство для перебора сочетаний из и элементов !

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

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

Недостатком этого устройства является его сложность, обусловленная наличием двух регистров сдвига, дешифратора, счетчика (с коэффициентом пересчетам ), распределителя импульсов, выполненного >о в виде регистра сдвиге. Вследствие этого устройство обладает невысоким быстродей ствием и низкой приспособленностью к схемным изменениям при изменении величины ж. 35

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

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

И, содержит первую группу из (- 1)

25 элементов И, вторую группу из элементов И, третью группу из (— 1) элементов И, четвертую группу из (. — 2) элементов И, первую группу из (v -1) элементов ИЛИ, вторую группу из (2) элементов ИЛИ, причем вход устройЗО ства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, второй вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход -го элемента И

\ второй группы (= 1, 2,..., ) подключен к единичному выходу j, -го разряда регистра и к первому входу ) -го элемента И четвертой группы (j = 2, 3„... 4>

% м — 2), выход е -го элемента И второй группы (Фи ) подключен к первым входам 8 -x элементов И и HJIH первых групп соответственно (L = 1, 2,..., и —

1), второй вход 4 -ro элемента ИЛИ . 5О первой группы подключен к выходу 3 -го элемента И третьей группы и к первому входу (L + 1)-го элемента И третьей группы, второй вход К -ro элемента И третьей группы подключен к нулевому ы выходу ;го разряда регистра соответственно, который подключен ко второму входу 4 -го элемента И первой группы, При переборе сочетаний каждое очередное состояние образуется из предыдущего путем замены крайней справа комбинации "Ol на 10" и переписи всех единиц, расположенных правее, в крайние правые позиции. При этом в первоначальном состоянии все единицы должны располагаться в крайних справа позициях, в последнем же состоянии они переходят в крайние слева позиции. Например, при

v = 5 и = 3 устройством вырабатываются сочетания

1 0011 1 6 10101

2 01011 7 10110

8 11001

9 11010

10 11100

3 01101

4 01110

10011

Перед началом работы для перебора всех сочетаний иэ vn элементов по и производится установка всех триггеров

1 регистра в нулевое состояние, а затем запись единиц в м крайние справа триггеры (и =1,2,..., ил-l). выход которого подключен к первому единичному входу разряда регистра, вто-, рой единичный вход которого подключен к выходу -ro элемента И четвертой группы и ко второму входу (j + 1) элемента И четвертой группы, нулевой вход

-го разряда регистра (ф ) подключен к выходу -го элемента И второй группы и к первому входу J -го элемента ИЛИ второй группы, второй вход которого подключен к выходу 1 -го элемента задержки группы, вход которого под» ключен к выходу j + 1-го (j 9 1 ъ- 3) 1 элемента ИЛИ второй группы, выход ro элемента И второй группы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу и-го разряда регистра вход (m — 2)-ro элемента задержки группы подключен к нулевому входу (и — l)-го разряда регистра.

На чертеже представлена схема устройства.

Устройство содержит регистр, образованный триггерами l, и распределитель импульсов, образованный элементами И 2, элементами ИЗ,,элементами ИЛИ 4, элементами И 5, элементами И 6, элементами 7 задержки, элементами ИЛИ 8, триг.,гером 9, элементом И lO, шину 11 входного импульса, шину 12 сигнала окончания перебора.

9038

Каждый раэ при поступлении входного импульса по шине 11 триггер 9 распределителя импульсов устанавливается в нулевое состояние, обеспечивая тем самым разрешающий потенциал на управляющем входе элемента И 10 и запрещающий - на управляющем входе первого элемента И 6 четвертой группы. Этот же импульс поступает на информационные входы первого элемента И 3 второй группы и пер- 0 вого элемента И 5 третьей группы. При единичном состоянии триггеров 1 регистра на управляющих входах элементов

И 3 и И 6 второй и четвертой групп находятся разрешающие потенциалы, а на управляющих входах элементов И 2 и И 5— запрещающие потенциалы, при нулевом состоянии триггеров 1 регистра, наоборот, на управляющих входах элементов И 3 и

И 6 находятся запрещающие потенциалы, а 20 на управляющих входах элементов И 2 и

И 5 — разрешающие.

Если (Y = 1, 2,..., ) крайние справа триггеры 1 находятся в единичном состоянии, то входной импульс проходит последовательно элементы И 3 второй группы и ИЛИ 4 первой группы и устанавливает эти триггеры в нулевое состояние, а (+1)-ый триггер 1 через о крытый элемент И 2 первой группы — в единичное состояние и, кроме того поступает на входы элементов ИЛИ 8 второй группы, что обеспечивает формирование на выходе первого элемента ИЛИ 8 вто35 рой группы серию из Y импульсов (элементы 7 задержки обеспечивают временную растяжку серии импульсов, необходимую для стабильности переходных процессов при дальнейшей работе). Первый 40 импульс серии, пройдя через элемент

И 10, устанавливает триггер 9 распределителя импульсов в единичное состояние, чем обеспечивается подача на управляющий вход первого элемента И 6 чет« вертой группы разрешающего потенциала.

Второй импульс серии, пройдя первый элемент И 6 четвертой группы, устанавливает первый триггер. 1 регистра в единичное состояние, чем обеспечивается про50 хождение третьего импульса серии через второй элемент И 6 четвертой группы и установка в единичное состояние второго триггера 1 регистра, а с каждым очередным импульсом серии установка очередного по порядку триггера 1 регистра включительно (— 1)-ый триггер.

На этом заканчивается такт формирования очередного сочетания, которое снимается

91 6 с единичных входов (а„, а,..., О.„„J е триггеров 1 регистра.

Если г (= 1,2,..., м- ) крайние правые триггеры 1 регистра находятся в нулевом состоянии, то входной импульс, пройдя открытых элементов И 5 третьей группы, поступает через r --ый элемент HPH 4 первой группы на открытый (t" + 1)-ый элемент И 3 второй группы и в дальнейшем выполняет действия, аналогичные описанным, Если в текущем сочетании в крайней справа позиции имеется комбинация 01 то при формировании очередного сочетания она преобразуется в комбинацию 10, что соответствует сдвигу единицы на один разряд влево. Если и крайние слева триггеры 1 регистра находятся в единичном состоянии.(последнее иэ формируемых сочетаний), то при поступлении очередного входного импульса с выхода последнего элемента И 3 второй группы выдается по шине 12 сигнал окончания перебора.

Технико-экономический эффект от использования данного устройства состоит в упрощении технической реализации устройства и повышении его надежности эа счет сокрашения количества элементов (около 30%), а также в повышении его быстродействия за счет исключения регистров сдвига и необходимости переписи кодов из регистра в регистр. Кроме того, конструкция устройства может быть представлена в виде .соединенных последовательно м ячеек, каждая из которых содержит триггер 1, четыре элемента

И (2, 3, 5 и 6), два элемента ИЛИ (4 и 8) и один элемент 7 задержки. Такое построение обеспечивает простоту схемного изменения устройства — при увеличении (уменьшении) значения м в устройство включается (исключается) соответствующее количество ячеек.

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

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

И, третью группу из (м — 1) элементов И, четвертую группу из (— 2) 7 9038 элементов И,первую группу из (м - 1) элементов ИЛИ, вторую. группу из L м

2) элементов ИЛИ, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И треТьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, второй вход которого подключен к выходу первого элемента ИЛИ ip второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход «го элемента И второй группы (+ 1. 2" ) подключен к единичному выходу

-го разряда регистра и к первому . входу j -го элемента И четвертой группы L j 2,3,"., t2), выход 4 го элемента И второй группы (-„ и) подключен к первым входам 3 -х элемен тов И и ИЛИ первых групп соответственно (1, 2,..., м - l), второй вход

Х -го элемента ИЛИ первой группы

I подключен к выходу ф -го элемента И третьей группы и к первому входу (4 +

Ф1)-го элемента И третьей группы, второй вход 4 -ro элемента И третьей группы подключен к нулевому выходу

1 -го разряда регистра соответственно, 91 8 который подключен ко второму входу, — го элемента И первой группы, выход которого подключен к первому единичному, .входу разряда регистра, второй единичный вход которого подключен к выходу, -го элемента И четвертой группы и ко второму входу (j + 1) элемента И четвертой группы, нулевой вход t -го разряда регистра (j, +ü ) подключен к выходу го элемента И второй группы и к первому входу -а.о элемента ИЛИ второй группы, второй вход которого подключен к

% выходу 1 -го элемента задержки группы, вход которого подключен к выходу (+

g.-го (j +w -3) элемента WIH второй группы, выход м -го элемента И второй группы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу ь -го разряда регистра, вход (- 2)-го элементе задержки группы нодключен i нулевому входу (м — 1)-го разряда регистра.

Источники информации, принятые во внимание при экспертизе

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

% 514295, кл. G 06 F 15/20, 1973.

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

% 634285, кл. G 06 F 15/32, 1974 (прототип).

903891

Составитель В. Кайданов

Редактор Т. Кугрышева Техред Е.Харитончик Корректор Г. Назарова

Заказ 123/31 Тираж 731 Подписное

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

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

Филиал П(И1 "Патент, г. Ужгород, ул. Проектная, 4