Комбинаторное устройство

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(51 М, Кл,з с присоединением заявки Мо С 06 Г 7/00 Государственный квинтет СССР по аеааи изобретений н открытий(088.8) Дата опубликования описания 15.02)31 УиО.В, Викторов, М.Г. ЛУкашевич, С.И. Орел и АМ.:;7 ЯИФФкезнч,фод 4 ЯГ4 ., л 2 гЯЦ г,(72) Авторы изобретения(71) Заявитель Киевский политехнический институт им. 56"-тйггия- Великой Октябрьской социалистической революции(54) КОМБИНАТОРНОЕ УСТРОЙСТВО Изобретение относится к автомати ке и вычислительной технике и может быть использовано для решения комбинаторных задач, а также для генерации фкодовых последовательностей в устройствах кбнтроля.Известно комбинаторное устройство, осуществляющее перебор сочетаний,в содержащее последовательно соединенные счетчики с коэффициентами пересчета, разнящимися на единицу, схе" мы И, схемы ИЛИ, линии задержки, триггеры, дешифраторы, фоомирователи, генераторы импульсов 11.Недостаток устройства в том, что он не осуществляет генерацию перестановрк.%ниболее близким техническим решением к изобретению является комбииаторное устройство, содержащее в 1 том 2 О =1И) разряде регистр, три элемента И, элемент ИЛИ, причем выход ре истра каждого разряда соединен с первым входом первого элемента И того же разряда, выход которого соединен с первым входом элемента ИЛИ, выход которого соедйнен с первым входом второго элемента И следующего разряда, и первым входом регистра следую щего разряда, а второй вход соеди нен с выходом второго элемента И того же разряда, второй вход которогосоединен с первым входом третьего элемента И того же разряда и вторым входом первого элемента И того же разряда, выход третьего элемента И каждого разряда соединен со вторым входом регистра того же разряда, Устройство содержит крОме того дешифратор 23.Недостатком его является низкое быстродействие.Цель изобретения - повышение быст родействия.Цель достигается тем, что устрдй, ство содержит Мраспределителя, Мкольцевых сдвиговых регистров, группу элементов И, первую группу из йэлементов .ИЛИ, вторую группу элементов ИЛИ, причем первый и последний выходы первого распределителя соединены с первым входом третьего элемента И соответственно первого и последнего разрядов устройства и с первыми входами соответственно первого и йэлементов группы ИЛИ. Каждый остальной выход первого распределителя сое динен с первым входом соответствующего элемента ИЛИ первой группы и со вторыми входами следующего элементаИЛИ первой группы, выходы элементовИЛИ группы соединены с первыми входами третьих эпементов И соответствующих разрядов, вторые входы которых соединены между собой и являютсятактовым входом устРойства, входыпервого распределителя, кроме последнего, соединены с выходами следующегораспределителя и выходами 1-тогокольцевого регистра сдвига, входыпоследнеГо распределителя соединеныс выходами двух последних кольцевыхрегистров сдвига, управляющий входкаждого кольцевого регистра сдвигасоединен с выходом соответствующегоэлемента И группы, нервый вход которого соединен с выходом следующегоэлемента И группы, а второй вход соединен с выходом соответствующего элемента ИЛИ второй группы, первый ивторой входы которого соединены спервы и последним выходами соответствующего кольцевого регистра,На чертеже схематически показаноустройство,Оно содержит регистры 1-6, элементы И 7-12, элементы И 13-18, элемен- дты И 19-24, элементы ИЛИ 25-30, кольцевые рсгистры сдвига 31-33, распределители 34-35, триггеры управлениясдвигом 36-38, тактовый вход 39 устройства, выход 40 распределителя,элемент ИЛИ 41, выход 42 распределителя, зле:,ент ИЛИ 43, выход 44 расапределителя, выход 46 распределителя,элемент, ИЛИ 45, элемент ИЛИ 47, выход 48 Распределителя, входы 49-57распределителя, выходы 58-66 распре -делителя, входы 67-84 распределителя,элементы И 85-90, элемент ИЛИ 91,элементы И 92 н 93, элементы .ИЛИ 9499, элементы И 100-111, элементыИЛИ 112-118, элементы И 119-126. 40Комбинаторное устройство работает. следующим образом.В первом такте работы устройстварегистры 1-6 устанавливаются соот"3", "4", "5". На информационные выходы регистров 1-6 поступают соответственно сигналы 000, 001, 016, 011,100, 101. Таким образом, в первом такте работы устройства реализуется первая перестановка "012345" (см. таблицу), где номера позиций цифр в перестановке соответствуют номерам регистров, а цифры, стоящие на этихпозициях, соответствуют десятичнойзаписи двоичных кодов состояний соответствующих регистров.Регистр 31 устанавливается в состояние 00010, регистр 32 - в состояние 000010, регистр 33 - в состояние 0000010 (см. таблицу), 60На входы распределителя 34 с выходов кольцевого регистра 31 поступаютсоответственно сигналы 0,0,0,1,0.На входы элемента ИЛИ 112 с входов68 и 71 распределителя 34 поступают 65 нулевые сигналы, а единичный сигналс входа 70 распределителя 34 поступает через элемент ИЛИ 113 на входкаждой из схем И 107, 109-111.На входы 79-84 распределителя 35с выходов сдвигающего регистра 32поступают соответственно сигналы0,0,0,0,1,0.Йулевой сигнал с входа 79 черезвыход 59 этого распределителя и вход50 поступает на вход каждого из эле-,ментов И 102, 104, 106, 108, 110, 111Нулевой сигнал с входа 84 распределителя 35 через выход 65 этой схемы ивход 56 распределителя 34 поступаетна вход каждого из элементов И 100,.101, 103, 105, 107, 109. Нулевые сигналы с выходов первого и последнегоразряда сдвигающего регистра 33 поступают, соответственно на входы 72и 78 распределителя сигналов 35, Свыхода 72 этой схемы нулевой сигналпоступает на вход каждого из элементов И 120, 124, 125, а также черезвыход 58 распределителя 35 и вход 49распределителя 34 поступает на входкаждого из элементов И 101, 104,105, 108, 109, 111. С входа 78 распределителя 35 нулевой сигнал поступает на вход каждого из элементовИ 119, 121, 123, 125, а также черезвыход бб распределителя 35 и вход 57распределителя 34 поступает на входкаждого из элементов И 100, 102, 103,106, 107, 110,Таким образом, все элементы И 100111, 119-126 закрыты нулевыми сигналами на входах, и сигналы из регистров 31 и 32 через распределители 34и 35 соответственно не поступают,Нулевой сигнал с выхода второгоразряда регистра 33 через вход 73,элемент ИЛИ 114, выход 60, вход 51,элемент ИЛИ 95, выход 40 закрываетэлементы И 7 и 19 и открывает. элемент И 13. Нулевой сигнал с выходатретьего разряда сдвигающего регистра 13 через вход 74 распределителясигналов 35, элемент ИЛИ 115, выход 61, вход 52 распределителя сигналов 34, элемент ИЛИ 96, выход 42,элемент ИЛИ 41 закрывает элементыИ 8 и 20 и открывает элемент И 14.Нулевой сигнал с выхода четвертогоразряда регистра 35 через вход 75распределителя 35, элемент ИЛИ 116,выход 62, вход 53 распределителя сигналов 34, элемент ИЛИ 97, выход 44,элемент ИЛИ 43 закрывает элементыИ 9 и 21 и оТкрывает элемент И 15.Нулевой сигнал с выхода пятого разряда регистра 33 через вход 76 распределителя 35, элемент ИЛИ 117, вы.ход 63, вход 54 распределителя 34,элемент ИЛИ 98, выход 46, элементИЛИ 45 закрывает элементы И 10 и 22и открывает элемент И 16. Единичныйсигнал с выхода шестого разряда регистра 33 через вход 77 распредели60 теля 35, элемент ИЛИ 118, выход 64, вход 55 распределителя 34, элемент ИЛИ 99, выход 48, элемент ИЛИ 47 открывает элементы И 11 и 23 и закрывает элемент И 17. Кроме того, единичный сигнал, поступающий с выхода 48 распределителя 34, открывает элементы И 12 и 24 и закрывает элемент И 18;Триггеры управления сдвигом 36-38 устанавливаются в нулевое состояние (см. таблицу), и на первые входы элементов И 85, 88 и 92 поступают нулевые сигналы, а на первые входы элементов И 86, 89 и 93 поступают единичные сигналы с соответствующих выходов триггеров, благодаря чему в ре 15 гистрах разрешается левый сдвиг.Нулевые сигналы с выходов первого .и последнего разрядов регистра 33 через элемент ИЛИ 94 поступают на вход элемента И 90 и закрывают его, Нуле вые сигналы с выходов первого и последнего разрядов сдвигающего регистра 32 через элемент ИЛИ 91 поступают на вход элемента И 87 и закрывают его, 25Во втором такте работы устройства тактовый сигнал поступает на вход каждого из элементов И 19-24, и единичные сигналы с выходов открытых элементов И 23 и 24 поступают на так- З 0 товые входы регистров 5 и б. Код 100 с информационного выхода регистра 5 через открытые элементы И 11, 13-16 и элементы ИЛИ 25-29 поступает на вход установки регистра б, Код 101 с информационного выхода регистра б через открытый .элемент И 12 и элемент ИЛИ 30 поступает на вход установки регистра 5. Регистры 5 и б устанавливаются соответственно в состояния "5" и "4", Информация в дру гих,регистрах фиксируется нулевыми сигналами из тактовых входов.. Таким образом, во втором такте работы устройства реализуется перестановка "012354". 45Кроме того, во втором такте тактовый сигнал поступает на вторые входы элементов И 92 и 93, единичный сигнал с выхода элемента И 93 поступает в цепь левого сдвига регистра 33, 50 и единица в этом регистре сдвигается на один разряд влево.В третьем такте работы устройства тазовый сигнал 39 поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода пятого разряда регистра 33 через элементы ИЛИ 117 и 98 распределителей 35 и 34 соответственно, элементы ИЛИ 45 и 47 и охкрытые схемы И 22 и 23 поступает на тактовые входы регистров 4 и 5, обеспечивая обмен информацией между этими регистрами.Таким образом, в третьем такте работы устройства реализуется переставовка "012534". Кроме того, единица 65 в регистре 33 сдвигается на один раз ряд влево.В следующих трех тактах работы устройства реализуются последовательно перестановки "015234", 051234" и "501234". Единица в регистре 33 сдвигается влево и в шестом такте сдвигается в первый разряд регистра 33. Единичный сигнал с выхода первого разряда сдвигающего регистра 33 поступает на единичный вход триггера 38 управления сдвигом, триггер 38 управления сдвигом устанавливается в единичНое состояние, и в регистре 33 разрешается .первый сдвиг. Кроме того, единичный сигнал с выхода первого разряда регистра 33 через элемент ИЛИ 94 открывает элемент И 90, а также поступает на вход 72 распределителя 35 и открывает элементы И 120, 122, 124, 126.В седьмом такте работы устройства тактовый сигнал с шины 39 тактовых сигналов поступает на вход каждого из элементов И 19-24. Единичный сигнал с выхода пятого разряда регистра. 32 через открытый элемент ИЛИ 118 распределителя 35 сигналов, элемент ИЛИ 99 распределителя 34 сигналов поступает на выход 48, обеспечивая обмен информацией между регистрами 5 и б. Реализуется перестановка "501243". Кроме того, тактовый сигнал с входа тактовых сигналов 39 поступает в цепь правого сдвига регистра 33, а через открытые схемы И 90 и 89 - в цепь левого сдвига сдвигающего регистра 32. Единица в сдвигающем регистре 33 сдвигается на один разряд вправо, а единица в сдвигающем регистре 32 - на один разряд влево.В тридцатом такте работы устройства реализуется перестановка "540123", единица в регистре 32 находится в первом разряде этого регистра, а единица в регистре 33 сдвигается в первый разряд этого регистра.Единичный сигнал.с выхода первого разряда регистра 33 поступает на единичный вход триггера 38 управления сдвигом, этот триггер устанавливается в единичное состояние, и в регистре 33 разрешается правый сдвиг.Элементы И 87 и 90 открыты единич ными сигналами, поступающими через элементы ИЛИ 91 и 94 соответственно с выходов первых разрядов, регистров 32 и 33, Единичные сигналы с выходов первых разрядов регистров 32 и 33 через распределители 35 поступают соответственно на входы 50 и 49 схемы распределителя 34 сигналов и открывают в ней элементы И 104, 108, 111.В тридцать первом такте работы устройства тактовый сигнал с шины 39 тактовых сигналов поступает на вход каждого из элементов и 19-24."530132" 00100.0100000100000 Единичный сигнал с выхода четвертого разряда сдвигающего регистра 31 через элемент,ИЛИ 113, открытый элемент ИЛИ 111, элемент ИЛИ 99 схемы распределения сигналов 34 поступает на выход 48 этой схемы, обеспечивая обмен инФормацией между регистрами 5 и 6. Реализуется перестановка "540132".Кроме того, тактовый сигнал с шины тактовых сигналов 39 через открытые элементы И 90 и 88 поступает в цепь правого сдвига сдвйгающего регистра 32, через открытые элементы И 90, 87. и 86 - в цепь левого сдвига сдвигающего регистра 31, а через открытый элемент И 92 - в цепь правого 15 сдвига сдвигающего регистра 33. Единица в сдвигающем регистре 31 сдвигается на один разряд влево, а единицы в сдвигающих разрядах 32 и 33 - на один разряд вправо, 20В семьсот девятнадцатом такте ра-, боты устройства реализуется перестановка "102354", единицы в сдвигающих регистрах 31 и 32 находятся в последних разрядах этих регистров, а единица в сдвигающем регистре 33 сдвигается в предпоследний разряд этого регистра.В семьсот двадцатом такте работы устройства тактовый сигнал с шины тактовых сигналов поступает на вход каждогоиз элементов И 19-24. Единичный сигнал с выхода предпоследнего разряда сдвигающего регистра 33 через элементы ИЛИ 118 и 99, соответственно схем распределения сигналов 35 и 34 поступает на выход 48 схемы распределения сигналов 34, обеспечивая обмен инФормацией между регистрами 5 и 6. Реализуется последняя перестановка "102345", а единица в сдвигающем регистре 33 сдвигается в последний разряд этого регистра.В таблице показаны состояния регистров, триггеров управления сдэигом и кольцевых регистров,00010000010000001000010000010000010000010000010000100000010.Продолжение таблицы СОСТОЯНИЯтриггеровуправления Состояниерегистра Номер такта Состояния кольцевых регистров сдвигом 00001"102345" 720 0 Формула изобретения 55 Известное устройство обеспечивает перечисление перестановок, но обладает существенным недостатком - низким быстродействием, Для перечисления 20 всех Р = и перестановок требуется и" тактов работы.По сравнению с известным предлагаемое комбинаторное устройство является более быстродействующим, так как обеспечивает генерацию всех Рпиперестановок за итактов работы. Так, для реализации Р 6 = 720 перестановок шести элементов предлагаемому ксмбинаторному устройствУ требуется 720 тактов работы, в то время как известному устройству требуется 46 656 тактов. Комбинаторное устройство, содержащее в 1-том (1=1й) разряде регистр, три элемента И, элемент ИЛИ, причем выход регистра каждого разря да соединен с первым входом первогофэлемента И того же разряда, выход которого соединен с первым входом элемента ИЛИ, выход которого соединен с первым входом второго элемен .та И следующего разряда, и первым входом регистра следующего разряда, а второй вход соединен с выходом второго элемента И того же разряда, второй вход которого соединен с первым 50 входом третьего элемента И того же разряда и вторым входом первого элемента И того же разряда, выход третьег,элемента И каждого разряда соедийен со вторым входом регистра того же разряда, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит (й) распределителя, Мкольцевых сдвиговых регистров, группу элементов И,первую группу элЕментов ИЛИ, вторуюгруппу элементов ИЛИ, причем первыйи последний выходы первого распределителя соединены с первым входомтретьего элемента И соответственнопервого и последнего разрядов устройства и с первыми входами соответственно первого и последнего элементов ИЛИ первой группы, остальные выходы первого распределителя соединены с первыми входами соответствующихэлементов ИЛИ первой группы и со вторыми входами следующего элемента ИЛИпервой группы, выходы элементов ИЛИпервой группы соединены с первыми входами третьих элементов И соответствующих разрядов, вторые входы которыхсоединены между собой и являются тактовым входом устройства, входы 1-того(3=1И-З) распределителя, кромепоследнего, соединены с выходами следующего распределителя и выходами1-того кольцевого регистра сдвига,входы последнего распределителя соединены с выходами двух последних кольцевых. регистров сдвига, управляющийвход каждого кольцевого регистра сдвига соединен с выходом соответствующего элемента И группы, первый вход которого соединен с выходом следующегоэлемента И группы, а второй вход соединен с выходом соответствующего элемента ИЛИ второй группы, первый ивторой входы которого соединены спервым и последним выходами соответствующего кольцевого регистра. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР Р 374606, кл. 6 06 Г 15/32, 1970. 2. Авторское свидетельство СССР Ф 446057, кл. 6 06 Г 7/38, 1972.805302 оставитель Е, Пупыревехред Т. Маточка . Корректор М. Вигул Цитк кто 903 Зака 5 П нт", фг, Ужгород, ул. Проектн Филиа Тира ВНИИПИ Г по дел 13035, Мос756 Подписноударственного комитета СССизобретений и открытийа, Ж, Раушская наб., д.