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

Ввес -.-,зь я т

wL т ь н т H с 1 . .:: ..,;:!, - к 343 биби я отdli2 в", !.

Союз Советских

Социалистических

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (> i 512 7 (6!) Дополнительное к авт. свид-ву(22) Заявлено23.03.73 (21) 1897788/18-24 с присоединением заявки №(23) Приоритет(43) Опубликовано30.04.76.Бюллетень № 16 (46) Дата опубликования описания30.06.77 (51) М. Кл.е (:т06 G 15/20

Государстоенный комитет

Совета Министроо СССР но деном иэооретений н отнропий (53) УДК681.3(088.8) В, В. Епихин (72) Автор изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ

Изобретение относится к области вычислительной техники и может быть использовано для многократного перебора сочетаний по N из М элементов для таких фиксированных значений N и М, для которых имеется 5 только одно неполное базовое сочетание.

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

Однако в таком устройстве необходомо наличие дополнительных N тактовых импульсов при достижении последним счетчиком своего максимального значения для перехода устройства к следующему состоянию. УчиЛ5 тывая, что общее число состояний, при которых необходимы дополнительные N тактоИ-3 вых импульсов, равно С, получаМ-1 ем общее количество дополнительных BKтовых импульсов, для вспомогательных опе- 20

N-k раций, равное N С „

Бель изобретения — повышение быстродействия устройства. В общем случае быстродействие предлагаемого устройства в 25

2 (1 + N ) раз выше быстродействия,извесь ного устройства.

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

53 2472

3 основного элемента задержки. Выход основного элемента задержки связан со сдвигающим входом кольцевого регистра, выходы последнего - с соответствукииими выходами устройства, входы - с выходами блока памя- 5 ти, а вход "установки в нуль — с выходом элемента ИЛИ, второй вход которого соединен с выходом основното счетчика и с входом вспомогательного элемента задержки. Выход вспомогательного элемента 1р задержки подключен к входу "установки в нуль основного счетчика и к переключаюаеью входу распределителя.

Схема предлагаомого устройства пред)5 ставлена ga чертеже.

Устройство содержит блок 1 памяти, кольцевой регистр 2 с входами 3 и выходами 4, распределитель 5 с выходами 6, элемент "ИЛИ 7, вспомогательный 8 и основной 9 элементы задержки, основной

10 и вспомогательный 11 ключи, основной

12 и вспомогательный 13 счетчики, триг- гер 14 с входом 15 установки в единицу, входом 16 установки в нуль" и единичным выходом 17, тактовый вход 18, выход 19

"окончания перебора сочетаний" и установочный вход 20, Работа устройства основана иа том, что для некоторых значений М и М все сочета- 50 иия из М по N элементов могут быть получены путом циклического сдвига базовых сочетаний. Так, например, дляй биМ=9 базовыми сочетаниями являются следующио: 85

¹ 1 . 111111000 № 2 111110100 № 3 111110010 № 4 111101100

¹ 5 111101010 40 № 6 111100110

¹ 7 1110%1100 № 8 111011010 № 9 111010110 № 10 110110110 45

Все сочетания по шесть элементов иэ девяти могут быть .получены путем циклического сдвига приведенных базовых сочетаний. Первые девять сочетаний дают по девать различных сочетаний, а десятое баэо- 50 вое три сочетания, так как после трех циклических сдвигов получаем исходную комбинацию.

Назовем базовые сочетания полными, если они дают М сочетаний, и неполными, 55 если они дают меньше, чем N сочетаний. ,Пля любых значений N и М можно определить базовые сочетания, иэ которых можно

<аолучить все остальные сочетания, путем циклического сдвиге. Однако не для всех 60 значений И и М можно .получи ть только од« но неполное базовое сочетание. Работа уст ройства возможна только для таких значений N и М, для которых имеется только одно неполное базовое сочетание (на ример, для Й - 6 и М - 9), Вое базовые сочета-. ния записываются в ячейки блока 1 памяти таким образом, что первымн считываются все полные базовые сочетания, а единствен« ное неполное базовое сочетание считывает-, ся последним.

Работает устройство следуиицим образом. »

Первоначальное устройство импульсов йо установочному входу 20 занимает исходное положение. При этом распределитель 5 устанавливается в первое положеиие, вспомогательный счетчик 13, триггер 14 и (через элемент ИЛИ" 7) кольцевой регистр 2в нулевые положения, а основной счетчик

12 - в положение (М - 1). Работа устройства происходит по тактам, при этом тактовые импульсы поступают по тактовому вхо ду 18. В исходном состоянии выход вспо

/ могательного счетчика 13 открывает основной ключ 10, и импульсы с тактового входа 18 поступают на счетный вход основного счетчика 12 и на вход основного элемента 9 задержки. На счетный вход вспомогательного счетчика 13 импульсы не gpo» ходят, так как вспомогательный ключ 11 закрыт триггером 14. Основной счетчик

12 находится в положении (М-1), и первый импульс, поступивший на его счетный вход, перебрасывает его в положение М. При этом на выходе основного счетчика появляется импульс, который поступает на вход вспомогательного элемента 8 задержки и через элемент "ИЛИ" 7 устанавливает в нулевое положение все разряды кольцевого регистра 2. Импульс на выходе основного элемента задержки оказывается раньше, чем на выходе вспомогательного элемента задержки. Поэтому импульс с выхода основного элемента задержки производит сдвиг кольцевого распределителя раньше, чем в него записывается очередное базовое сочетание.

Импульс с выхода вспомогательного элемента задержки устанавливает в нулевое положение основной счетчик и переводит распределитель 5 во второе положение. При переходе распределителя 5 иэ положения 1 в положение ) + 1 на его L -м выходе появляется импульс. Поэтому на первом выходе 6 распределителя 5 образуется импульс, который считывает первое базовое сочетание иэ блока li памяти. Базовое с<>четание иэ блока памяти записывается в кольцевой регистр 2. Последуюшие (М-1) 512472 тактовых импульса, поступающих по тактовому входу 18; продвигают через основной элемент задержки кольцевой регистр н увеличивают показания основного счетчика до положения М-1. (М + 1)-й импульс, по. ступивший по тактовому входу 18, перебрасывает основной счетчик в положение М при этом на выходе основного счетчика появляется импульс, который сбрасывает (через элемент ИЛИ 7):содержимое кольце- тй вого регистра.

Одновременно импульс с выхода основного счетчика поступает иа вход вспомогательного элемента задержки. Далее импульс с выхода вспомогательного элемента эадерж-I5 ки устанавливает в нулевое положение основной счетчик и переводит распределитель в третье положение. На втором выходе 6 распределителя появляется импульс, котэрый считывает иэ блока памяти В кольц яй вой регистр второе базовое сочетание. Следующие (М-1) импульсов, поступивших по тактовому входу 18, продвигают содержимое кольцевого регистра и увеличивают показания основного счетчика до состояния 25 (М 1) .,Палее работа происходит аналогичным образом, Осуществляется считывание очередного базового, сочетания каждым (1+М ° ()-м импульсом„поступившим по тактовому входу 18, где 1 = О, 1, 2, 3,... P, ЭО а импульсами (2 + М ° i ) — (М + М 1 ), .rae t О, 1, 2, ..., Q,, проводится сдвиг содержимого кольцевого регистра и увеличение на единицу содержимого основного счетчика до состояния (М-1). Прн появле- 55 нии импульса на последнем выходе 6 распределителя происходит считывание из блока памяти в кольцевой регистр единственного неполного базового сочетания. Одновременно переводится в единичное положение 40 триггер 14 по входу 15 установки в единицу . Триггер в единичном состоянии разрешает поступление импульсов через вспомогательный ключ на счетный вход вспомогательного счетчика. Теперь импульсы с тактового входа 18 рдновременно подаются на основной и вспомогательный счетчики.

Пусть неполное базовое сочетание дает сочетаний. Сигнал на выходе вспомогательнот о счетчика появляется после перевода вспомогательного счетчика в (V -1)-е состояние. При этом запрещается прохождение через основной ключ импульсов с тактового входа 18 н одновременно нв выходе 19

6

"окончания перебора сочетаний образуетса

„-игнал.

Таким образом, по каждому импульсу, поступившему по тактовому входу 18, не выходах кольцевого регистра получаем оче редное сочетание. Для )ч 6 и М 9 требуется С " 84 тактов, в то время в как для прототипа (ввт.св. СССРМ238 238)»

° и Мf "В 3

С + g C Сй + 6 С 420 тактов, т. е. в пять раз больше, чем в предлагаемом устройстве.

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

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

r. (М-1)-е положение(где М - 1, 2,,К) основного счетчика, а выходы распределителя соединены соответственно с входами блока памяти, причем последний (К-ый) вы» ход распределителя соединен с входом ус тановки в единицу триггера, выход которого соединен с первым входом вспомогательно го ключа, выход которого соединен со счетным входом вспомогвтельното счетчика, выход которого соединен с выходом окончания перебора сочетаний устройства и с первым входом тактового ключа, второй вход которого соединен с тактовым входом устройства, в выход соединен со счетным входом основного счетчика, с вторым входом вспо могательного ключа н с входом основного элемента задержки, выход которого соединен со сдвнгаюшим входом кольцевого регистра, выходы которого соединены с соответствуюшими выходами устройства, а входы соединены с выходами блока памяти, и вход установки в нуль" соединен с выходом элемента "ИЛИ", второй вход которого соединен с выходом основного счетчика и с входом вспомогательного элемента задержки, выход которого соединен с входом установки в нуль основного счетчика и с переключвкхпим входом распределителя.

512472

Составитель В. Епихин

Редактор И. Груэова . Техред И. Асталош Корректор Е, Скучка

Зькаэ 956/508 Тираж 864 Подписное

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

113035, Москва, Ж-35, Раушская наб„д. 4/5 филиал ППП Патент, г. Ужгород, ул. Проектная, 4