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

Номер патента: 903891

Автор: Полищук

ZIP архив

Текст

Сфеэ СоветснииСоциапнстнчесннкРеснублин ОП ИСАНИЕ ИЗОБРЕТЕНИЯ к лвтоскомю свидетельствуп 903891(51)М. Кл. б 06 Р 15/31 3 ЬЮдвРотокикы конитет СССР в долан иаобротоиий и открытий(53) УДК 681,3088.8) Дата опубликования описания 09,02.82(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ Изобретение относится к вычислительной технике и может быть применено, например, в вычислительных машинах, решающих комбинаторные задачи.Известно устройство для перебора со четаний, содержащее основной регистр,3запоминающий регистр, вспомогательный регистр, блок управления, триггеры, элементы И и ИЛИ, элементы задержки Ю.Недостатком известного устройства является то, что оно содержит большоето количество элементов, что снижает надежность работы.Наиболее близким по технической сущности к изобретению является устройство для перебора сочетаний изб элементовпо , содержащее регистры сдвйга, счетчик, дешифратор, триггер, элементы И, элементы задержки, распределитель импульсов, первый выход которого соединен20 с первым входом первого регистра сдви-га, второй вход - с первым входом первого элемента И, второй вход которого подключен к управляющей шине, выход первого элемента И подключен к второму входу регистра сдвига и через последовательно соединенные счетчик и. первый элемент задержки подключен к нулевому входу триггера, первый, второй и третий входы второго регистра сдвига соединены соответственно с первым и вторым выходами дешифратора н выходом первого элемента задержки, выход второго регистра сдвига соединен с первым входом первого регистра сдвига и выходом устройства, первый выход первого регистра сдвига соединен с первым входом второго элемента И, третий вход первого регистра сдвига соединен с выходом второго элемента задержки, первый выход первого регистра сдвига соединен с первым входом второго элемента И, второй вход которого подключен к нулевому выходу триггера, выход элемента И через второй элемент задержки подключен к единичному входу триггера, нулевой вход которого подключен к первому входу дешифратора, второй вход которого подклю 3 9038 чен к второму входу второго элемента И, третий вход дешифратора подключен к третьему входу первого, регистра сдвига, четвертый вход дешифратора подключен к выходу первого элемента И 23.Недостатком этого устройства является его сложность, обусловленная наличием двух регистров сдвига, дешифратора, счетчика (с коэффициентом пересчета м ), распределителя импульсов, выполненного О в виде регистра сдвиге. Вследствие этого устройство обладает невысоким быстродей ствием и низкой приспособленностью к схемным изменениям при изменении величины ж. 15Цель изобретения - упрощение устройства.Поставленная цель достигается тем, что устройство для перебора сочетаний,20 содержащее и -разрядный регистр, группу из ( м) элементов задержки, элемент И и триггер, нулевой выход которого подключен к первому входу элемента И, содержит первую группу из ( и =1)25 элементов И, вторую группу из элементов И, третью группу из ( - 1) элементов И, четвертую группу из (-2) элементов И, первую группу из ( кл -1) элементов ИЛИ, вторую группу из ( и) элементов ИЛИ, причем вход устройЗО ства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, второй вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единиЧному выходу 40 триггера, второй вход-го элемента Ивторой группы (= 1, 2м) подключен к единичному выходу-го разряда регистра и к первому входу-го элемента И четвертой группы ( 3 = 2 3,.", 45 м - 2), выход-го элемента И второй группы (Фи ) подключен к первым входам 1 -х элементов И и ИЛИ первых групп соответственно (= 1, 2 и - 1), второй вход 1 -го элемента ИЛИ, 50 первой группы подключен к выходу 8 -го элемента И третьей группы и к первому входу ( Х + 1)-го элемента И третьей группы, второй вход 8 -го элемента И третьей группы подключен к нулевому 55 выходу 1;го разряда регистра соответственно, который подключен ко второму входу-го элемента И первой группыПри переборе сочетаний каждое очередное состояние образуется из предыдущего путем замены крайней справа комбинации "01" на 10" и переписи всех единиц, расположенных правее, в крайние правые позиции. При этом в первоначальном состоянии все единицы должны располагаться в крайних справа позициях, в последнем же состоянии они переходят в крайние слева позиции. Например, при ил = 5 и м = 3 устройством вырабатываются сочетания1 0011 1 6 103.01 2 01011 7 10110 8 11001 9 11010 10 11100 303.101 4 03.110 3.0011 Перед началом работы для перебора всех сочетаний иэ ил элементов по и производится установка всех триггеров 1 регистра в нулевое состояние, а затем запись единиц в м крайние справа триггеры ( о =1,2 ил). выход которого подключен к первому единичному входу разряда регистра, вто-, рой единичный вход которого подключен к выходу-го элемента И четвертой группы и ко второму входу ( 3 + 1) элемента И четвертой группы, нулевой вход-го разряда регистра ( 1,щ ) подключен к выходу-го элемента И второй группы й к первому входу 3 -го элемента ИЛИ второй группы, второй вход кото-" рого подключен к выходу 3 -го элемента задержки группы, вход которого под ключен к выходу+ 1-го (1м) элемента ИЛИ второй группы, выход Ф-го элемента И второй группы подключен к выходу окончанияперебора сочетаний устройства и к нулевому входу и-го разряда регистра, вход ( ич - 2)-го элемента задержки группы подключен к нулевому входу ( м - 1)-го разряда регистра.На чертеже представлена схема устройства.Устройство содержит регистр, образованный триггерами 1, и распределитель импульсов, образованный элементами И 2, элементами И 3, элементами ИЛИ 4, элементами И 5, элементами И 6, элементами 7 задержки, элементами ИЛИ 8, триг.,гером 9, элементом И 3.0, шину 11 входного импульса, шину 12 сигнала окончания перебора.9038 Каждый раэ при поступлении входного импульса по шине 11 триггер 9 распределителя импульсов устанавливается в нулевое состояние, обеспечивая тем самым разрешающий потенциал на управ ляющем входе элемента И 10 и запрещающий - на управляющем входе первого элемента И 6 четвертой группы. Этот же импульс поступает на информационные входы первого элемента И 3 второй группы и пер-О вого элемента И 5 третьей группы. При единичном состоянии триггеров 1 регистра на управляющих входах элементов И 3 и И 6 второй и четвертой групп находятся разрешающие потенциалы, а на управляющих входах элементов И 2 и И 5 - запрещающие потенциалы, при нулевом состоянии триггеров 1 регистра, наоборот, на управляющих входах элементов И 3 и И 6 находятся запрещающие потенциалы, а 20 на управляющих входах элементов И 2 и И 5 - разрешающие. Если( Р = 1, 2 м ) крайние справа триггеры 1 находятся в единичном состоянии, то входной импульс проходит последовательно элементы И 3 второй группы и ИЛИ 4 первой группы и устанавливает эти триггеры в нулевое состояние, а ( н + 1)-ый триггер 1 через оч- крытый элемент И 2 первой группы - в единичное состояние и, кроме того поступает на входы элементов ИЛИ 8 второй группы, что обеспечивает формирование на выходе первого элемента ИЛИ 8 вто 35 рой группы серию изимпульсов (элементы 7 задержки обеспечивают временную растяжку серии импульсов, необходимую для стабильности переходных процессов при дальнейшей работе). Первый 40 импульс серии, пройдя через элемент И 10, устанавливает триггер 9 распределителя импульсов в единичное состояние, чем обеспечивается подача на управляющий вход первого элемента И 6 чет вертой группы разрешающего потенциала.Второй импульс серии, пройдя первый элемент И 6 четвертой группы, устанавливает первый триггер. 1 регистра в единичное состояние, чем обеспечивается про 50 хождение третьего импульса серии через второй элемент И 6 четвертой группы и установка в единичное состояние второго триггера 1 регистра, а с каждым очередным импульсом серии установка очередного по порядку триггера 1 регистра включительно (- 1)-ый триггер, На этом заканчивается такт формирования очередного сочетания, которое снимается 91 6с единичных входов ( а, а,"., О)триггеров1 регистра.Если г (= 12,., м-и ) крайниеправые триггеры 1 регистра находятсяв нулевом состоянии, то входной импульс,пройдя " открытых элементов И 5 третьей группы, поступает через г -ыйэлемент ИЛИ 4 первой группы на открытый ( Г + 1)-ый элемент И 3 второй группы и в дальнейшем выполняет действия,аналогичные описанным,Если в текущем сочетании в крайнейсправа позиции имеется комбинация 01,то при формировании очередного сочетания она преобразуется в комбинацию 10,что соответствует сдвигу единицы на одинразряд влево, Если и крайние слеватриггеры 1 регистра находятся в единичном состоянии.(последнее иэ формируемых сочетаний), то при поступлении очередного входного импульса с выходапоследнего элемента И 3 второй группывыдается по шине 12 сигнал окончанияперебора.Технико-зкономический эффект от использования данного устройства состоитв упрощении технической реализации устройства и повышении его надежности эасчет сокращения количества элементов(около 30%), а также в повышении егобыстродействия за счет исключения регистров сдвига и необходимости переписи кодов из регистра в регистр. Крометого, конструкция устройства может бытьпредставлена в виде .соединенных последовательно м ячеек, каждая из которыхсодержит триггер 1, четыре элементаИ (2,3, 5 и 6), два элемента ИЛИ (4и 8) и один элемент 7 задержки. Такоепостроение обеспечивает простоту схемного изменения устройства - при увеличении (уменьшении) значения ю в устройство включается (исключается) соответствующее количество ячеек. Формула изобретения Устройство для перебора сочетаний, содержащее м -разрядный регистр, группу иэ ( м - 2)элементов задержки, эле мент И и триггер, нулевой выход которого подключен к первому входу элемен- таИ, отличающееся тем, что, с целью упрощения устройства, оно содержит первую группу из ( чи -1) эл- ментов И вторую группу из элементов И, третью группу из ( м - 1) элементов И, четвертую группу из ( ф - 2)7 9038 элементов И,первую группу из 1 ю - 1 элементов ИЛИ, вторую. группу из 1 и 2) элементов ИЛИ, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И треТьей группы и к нулевому входу триггера, единичный вход которогоподключен к выходу элемента И, второй вход которого под- . ключен к выходу первого элемента ИЛИ 1 о второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй входго элемента И второй группыч, " 1, 2 й) подключен к единичному выходу-го разряда регистра и к первому . входу 1 -го элемента И четвертой группы2,3 м), выход 1 го элемента И второй группы (Ф фи) подключен к первым входам-х элемен тов И и ИЛИ первых групп соответственно (ф= 32в, ич - 1)второй входХ -го элемента ИЛИ первой группы1подключен к выходу ф -го элемента И третьей группы и к первому входу (1 + Ф 1)-го элемента И третьей группы, второй вход Х -го элемента И третьей группы подключен к нулевому выходу1 -го разряда регистра соответственно,91 8который подключен ко второму входу, - го элемента И первой группы, выход которого подключен к первому единичному, .входу разряда регистра, второй единичный вход которого подключен к выходу-го элемента И четвертой группы и ко второму входу (+ 1) элемента И четвертой группы, нулевой вход-го разряда регистра (+ь) подключен к выходу 4 го элемента И второй группы и к первому входу-а.о элемента ИЛИ второй группы, второй вход которого подключен к%выходу 1 -го элемента задержки группы, вход которого подключен к выходу ( + М-го (Фи -3) элемента ИЛИ второй группы, выход м -го элемента И второй группы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу ь -го разряда регистра, вход ( ю 2)-го элемента задержки группы подключен к нулевому входу ( м - 1)-го разряда регистра. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР-35, Раушская наб. 23/31 Тираж ВНИИПИ Государств по делам иэобре 113035, Москва, Ж

Смотреть

Заявка

2927360, 16.05.1980

ВОЙСКОВАЯ ЧАСТЬ 25840

ПОЛИЩУК ВИКТОР МИХАЙЛОВИЧ

МПК / Метки

МПК: G06F 17/10

Метки: перебора, сочетаний

Опубликовано: 07.02.1982

Код ссылки

<a href="https://patents.su/5-903891-ustrojjstvo-dlya-perebora-sochetanijj.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для перебора сочетаний</a>

Похожие патенты