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

Союз Советскин Социалистические РеспубликОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(23) Приоритет(43) Опубликовано 30 3 (21) 1897788/18 24вки Кл.е06 О 15/2 Государстоенный комитет Совета Миннстроо СССР но деном нэобретеннй н отнропнй, 76,Бюллетень16 Дата опубликования описания 30 7 Епи 72) Автор изобретения) раз Изобретение относлительной техники и ного устройства.Это достигается за счет того, что в устройство введены блок памяти, кольцевой регистр и распределитель. Установочный вход респределителя соединен с соответствующим входом устройства, первым входом элемента "ИЛИ, входами установки в нуль" соответственно вспомогательного счет- чика и триггера, входом установки в (М)-е положение ( где М - 1, 2 К) основного счетчика, а выходы распределителя- соответственно с входами блока памяти, причем последний (К-й) выход распределив теля связан с входом "установки в единицу триггера. Выход триггера подключен к пеовому входу вспомогательного ключа, выход ля м з М гократног элементов по значени ко одно полн т Известно устройст ний содержащее тр новные и вспомогат лементы задержк днако втаком устдополнительнь тв бходомо ых импульналичие сов пр своего х М так оследним значения достижении и аксимального четчиком для перехотоянию, Учи й, при кода устройств тывая, что о торых необхо вых импульсо ем общее кол товых импул ющему сос о состоян л щее числимы допв, равноичествоьсов, дляЯ С олнительные Й тИ С , полудополнительных таквспомогательных оп акточаого ключа - к сче вспомогаеднего - кетаний" устового клюному вход выход пос тельного выходу " ройствача, второ вым вход четчика,ончания ребора соч входу такт ого соеди к первому" вход кот аций, рави ен с такт ом устройства, а выход - со счетом основного счетчика, с вторымспомогательного ключа и с входом м ход тся к области вычисможет быть использоо перебора сочетаний для таких фиксировандля которых имеется 5 базовое сочетание.о для перебора сочеиггер,. элемент "ИЛИ", ельные счетчики, клюи, 0 Бель изобретения - повышение быстроействия устройства, В общем случае бытродействие предлагаемого устройства в 25 е быстродействия, извес г.3осаовиого элемента задержки. Выход основ- ноге элемента задержки связан со сдвигающим входом кольцевого регистра, выходы последнего - с соответствукидими выходами устройства, входы - с выходами блока памя ти, а вход "установки в нуль - с выходом элемента ИЛИ, второй вход которого соеаииви с выходом осиовното счетчика и с входом вспомогательного элемента задержки. Выход вспомогательного элемента 10 задержки подключен к входу "установки в нульф основного счетчика и к переключающему входу распределителя.Схема предлагаемого устройства пред)б. ставлена на чертеже,Устройство содержит блок 1 памяти,кольцевой регистр 2 с входами 3 и выходами 4, распределитель 5 с выходами 6,элемент фИЛИф 7, вспомогательный 8 иосновной 9 элементы задержки, основной10 и вспомогательный 11 ключи, основной12 и вспомогательный 13 счетчики, триг-гер 14 с входом 15 установки в единицу,входом 16 доустановки в нуль" и единичнымвыходом 17, тактовый вход 18, выход 19фокончаиия перебора сочетаний" и установочный вход 20,Работа устройства основана на том, чтодля некоторых значений М и М все сочета- Зния из М по М элементов могут быть получены путом циклического сдвига базовыхсочетаний. Так, например, для Й 6 иМ=9базовыми сочетаниями являются следующио; 8И 1 111111000М 2 111110100Ив 3 111110010М 4 111101100М 5 111101010 40М 6 111100110Й 7 111011100М 8 111011010М 9 111010110М 10 110110110 45Все сочетания по шесть элементов иэдевяти могут быть получены путем циклического сдвига приведенных базовых сочетаний. Первые девять сочетаний дают по девать различных сочетаний, а десятое баэовое три сочетания, так как после трех циклических сдвигов получаем исхорную комбинацию.Назовем базовые сочетания полными,если они рают М сочетаний, и неполными, Месли они дают меньше, чем М сочетаний.Для любых значений Я и М можно определить базовые сочетания, иэ которых можнополучить все остальные сочетания, путемциклического сдвига. Однако не рля всех 60 значений Й и М можно.получить только одно неполное базовое сочетание. Работа устройства возможна только рля таких значений й и М, для которых имеется толькоодно неполное базовое сочетание ( нагример,для й - 6 и М - 9), Вое базовые сочета-.ния записываются в ячеВси блока 1 памятитаким образом, что первыми считываютсявсе полные базовые сочетания, а единственное неполное базовое сочетание считывает-,ся последним.Работает устройство следующим образом.Первоначальное устройство импульсов йоустановочному входу 20 занимает исходноеположение. При этом распределитель 5 устанавливается в первое положеНие, вспомогательный счетчик 13, триггер 14 и (черезэлемент фИЛИф 7) кольцевой регистр 2 в нулевые положения, а основной счетчик12 - в положение (М - 1), Работа устройства происходит по тактам, при этом тактовые импульсы поступают по тактовому входу 18. В исходном состоянии выход вспсмогательного счетчика 13 открывает основной ключ 10, и импульсы с тактового входа 18 поступают на счетный вход основного счетчика 12 и на вход основного элемента 9 задержки. На счетный вход вспомогательного счетчика 13 импульсы не проходят, так как вспомогательный ключ 11закрыт триггером 14, Основной счетчик12 находится в положении (М), и первыйимпульс, поступивший на его счетный вход,перебрасывает его в положение М. Приэтом на выходе основного счетчика появляется импульс, который поступает на входвспомогательного элемента 8 задержки ичерез элемент "ИЛИ" 7 устанавливает внулевое положение все разряды кольцевогорегистра 2. Импульс на выходе основногоэлемента задержки оказывается раньше, чемна выходе вспомогательного элемента задержки. Поэтому импульс с выхода основного элемента эарержки проиэворит сдвигкольцевого распределителя раньше, чем внего записывается очередное базовое сочетание,Импульс с выхода вспомогательного элемента задержки устанавливает в нулевое положение основной счетчик и переводит распределитель 5 во второе положение. При переходе распределителя 5 нэ положенияв положение Ь + 1 на его Ь -м выходе появляется импульс, Поэтому на первомвыходе 6 распределителя 5 образуется импульс, который считывает первое базовоесочетание иэ блока 1 памяти. Базовое сочетание иэ блока памяти записывается вкольцевой регистр 2. Последуюшие (М)тактовых импульса, поступающих по тактовому входу 18; продвигают через основной элемент задержки кольцевой регистр н увеличивают показания основного счетчика до положения М, (М + 1)-й импульс, поступивший по тактовому входу 18, перебрасывает основной счетчик в положение М при этом на выходе основного счетчика появляется импульс, который сбрасывает (через элемент ИЛИ" 7),содержимое кольце вого регистра.Одновременно импульс с выхода основного счетчика поступает иа вход вспомогательного элемента задержки. Далее импульс с выхода вспомогательного элемента эадерж-ф ки устанавливает в нулевое положение основной счетчик и переводит распределитель в третье положение, На втором выходе 6 распределителя появляется импульс, котэрый считывает из блока памяти в кольце вой регистр второе базовое сочетание. Следующие (М) импульсов, поступивших по тактовому входу 18, продвигают содержимое кольцевого регистра и увеличивают показания основного счетчика до состояния И (М 1), Далее работа происходит аналогичным образом, Осуществляется считывание очередного базового, сочетания каждым (1+М)-м импульсомпоступившим по тактовому входу 18, где 1 = О, 1, 2, 3, Р, ЭО а импульсами (2 + М) - (М + М 1 ), .где 1 О, 1, 2, , О., проводится сдвиг содержимого кольцевого регистра и увеличение на единицу содержимого основного счетчика до состояния (М). Прн появле- Вб нии импульса на последнем выходе 6 распределителя происходит считывание из блока памяти в кольцевой регистр единственного неполного базового сочетания. Одновременно переводится в единичное положение 4 О триггер 14 по входу 15 доустановки в еднннцуф. Триггер в единичном состоянии разрешает поступление импульсов через вспомогательный ключ на счетный вход вспомогательного счетчика. Теперь импульсы с 5 тактового входа 18 рдновременно подаются на основной и вспомогательный счетчики.Пусть неполное базовое сочетание дает 7 сочетаний. Сигнал на выходе вспомогательного счетчика появляется после пере- ф 0 вода вспомогательного счетчика в (У -1)-е состояние. При этом запрещается прохождение через основной ключ импульсов с тактового входа 18 н одновременно нв выходе 19М 6"окончания перебора сочетаний" образуетсасигнал.Таким образом, по каждому импульсу,поступившему по тактовому входу 18, навыходах кольцевого регистра получаем очередное сочетание. Для й6 и М " 9требуется С 84 тактов, в то времявкак для прототипа (авт.св. СССРМ 238 238)и мф " взС +ЯС Сй + 6 С д 420тактов, т. е. в пать раз больше, чемвпредлагаемом устройстве.Формула изобретенияУстройство для перебора сочетаний, содержашее триггер, элемент ФИЛИ, основные н вспомогательные счетчики, ключи, элейенты задержки, о т л и ч а ю щ е е с я там, что, с целью повышения быстродействия, в него введены блок памяти, кольцевой регистр и распределитель, причем установовный вход распределителя соединен с соотг ветствующим входом устройства, первым входом элемента ИЛИ, входами "устаиов ки в нуль соответственно вспомогательнэ-го счетчика и триггера, входом установки в (М)-е положение( где М - 1, 2 К) хновного счетчика, а выходы распределителя соединены соответственно с входами блока памяти, причем последний (К-ый) вы ход распределителя соединен с входом ус тановки в единицу триггера, выход которого соединен с первым входом вспомогательно го ключа, выход которого соединен со счетным входом вспомогвтельното счетчика, выход которого соединен с выходом окончания перебора сочетаний устройства и с первым входом тактового ключа, второй вход котэ- рого соединен с тактовым входом устройства, в выход соединен со счетным входом основного счетчика, с вторым входом вспо могательного ключа н с входом основного элемента задержки, выход которого соединен со сдвнгающим входом кольцевого регистра, выходы которого соединены с соответствующими выходами устройства, а входы соединены с выходами блока памяти, и вход "установки в нуль" соединен с выходом элемента "ИЛИ", второй вход которого соединен с выходом основного счетчика и с входом вспомогательного элемента задержки, выход которого соединен с входом установки в нуль основного счетчика и с переключающим входом распределителя.Составитель В. ЕпихинРедактор И. Груэова Техред И. Асталош Корректор Е, СкучкаЗькаэ 956/508 Тираж 864 ПодписноеЦНИИПИ Государственного комитета Совета Иинистров СССРпо делам изобретений и открытий113035 Москва, Ж, Раушская наб., д. 4/5Филиал ППП Патент, г. Ужгород, ул. Проектная, 4