Устройство для перебора сочетаний Советский патент 1976 года по МПК G06F15/20 

1

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

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

Однако в таком устройстве необходомо наличие дополнительных N тактовых импульсов при достижении последним счетчиком своего максимального значения для перехода устройства к следующему состоянию. Учи тывая, что общее число состояний, при которых необходимы дополнительные N тактоii l

вых. импульсов, равно С . , , получа/л - i ем общее количество дополнительных гактовых импульсов, для вспомогательных oneраций, равное N С .

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

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

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

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

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

Устройство содержит блок 1 памяти, кольцевой регистр 2 с входами 3 и выходами 4, распределитель 5 с выходами б, элемент ИЛИ 7, вспомогательный 8 и j основной 9 элементы задержки, основной 10 в вспомогательный 11 ключи, основной 12 в вспомогательный 13 счетчики, триг- гер 14 с входом 15 установки в единицу, входом 16 установки в нуль и единичным выходом 17, тактовый вход 18, выход 19 окончячия перебора сочетаний и установочный вход 20.

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

№ 1 111111000

N9 2 111110100

NO 3 111110010

№ 4 111101100

Ns 5 11110101040

Nfe 6 111100110

NO 7 111011100

№ 8 111011010

№ 9 111010110

Ns 10 11011011046

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

Назовем базовые сочетания полными, сли они дают М сочетаний, и неполными, М сли они дают меньше, чем М сочетаний. ля любых значений N и А можно опредевть базовые сочетания, из которых можно олучить все остальные сочетания, путем иклического сдвига. Однако не для всех 60

значений N и М можно .получить только одно неполное базовое со штание. Работа устройства BO3MO)kKa только для таквх зв ачевий N к М, для которых имеется только одно веп1эавое базовое сочетание ( вагример для N - б в М - 9). Вое базовые сочетания записываются в ячейки блока 1 памятв таквм образом, что первыми считываются все полные базовые сочетания, а единственное неполное базовое сочетание считывается последним.

Работает устройство следующим образом

т.

Первоначальное устройство вмпульсов йо установочному входу 20 заввмает всходвое положение. При этом распределитель 5 устанавлввается в первое положение, вспомогательный счетчик 13, триггер 14 и (через элемент ИЛИ 7) кольцевой регистр 2 в нулевые положения, а основной счетчик 12 - в положение (М - 1). Работа устройства происходит по тактам, при этом такто вые импульсы поступают по тактовому входу 18. В исходном состоянии выход вспомогательного счетчика 13 открывает основной ключ ДО, и импульсы с тактового входа 18 поступают на счетный вход основного счетчика 12 и на вход основного эле/ мента 9 задержки. На счетный вход вспомогательного счетчика 13 импульсы не про ходят, так как вспомогательный ключ 11 закрыт триггером 14. Основной счетчик 12 находится в положении (М-1), и первый импульс, поступивший на его счетный вход, перебрасывает его в положение М. При этом на выходе основного счетчика появляется импульс, который поступает на вход вспомогательного элемента 8 задержкн и через элемент ИЛИ 7 устанавливает В нулевое положение все разряды кольцевого регистра 2. Импульс на выходе основного элемента задержки оказывается раньше, чем на выходе вспомогательного элемента задержки. Поэтому импульс с выхода основного элемента задержки производит сдвиг кольцевого распределителя раньше, чем в него записывается очередное базовое сочетание.

Импульс с выхода вспомогательного элемента задержки устанавливает в нулевое положение основной счетчик и переводит распределитель 5 во второе положение. При переходе распределителя 5 из положения L в положение L + 1 на его Ь -м выходе появляется импульс. Поэтому на первом выходе 6 распределителя 5 образуется импульс, который считывает первое базовое сочетание из блока li памяти. Базовое сочетание из блока памяти записывается в кольцевой регистр 2. Последующие (М-1) тактовых импульса, поступающих по тактовому входу 3.8, продвигают через основной апемент задержки кольцевой регистр и увеличивают показания основного счетчика до положения М-1. (М + 1) импульс, поступивший по тактовому 18, перебрасывает основной счетчик в положение М, при этом на выходе основного счетчика появляется импульс, который сбрасывает (через элемент ИЛИ 7) :содержимое кольцевого регистра. Одновременно импульс с выхода основного счетчика поступает на вход вспомогательного элемента задержки. Далее импульс с выхода вспомогательного элемента задерж ки устанавливает в нулевое положение основной счетчик и переводит распределитель в третье положение. На втором выходе 6 распределителя появляется импульс, который считывает из блока памяти в кольцевой регистр второе базовое сочетание. Следующие (М-1) импульсов, поступивших по тактовому входу 18, продвигают содержимое кольцевого регистра н увеличивают показания осцовного счетчика до состояния ,(М - 1) . Далее работа происходит аналогич ным образом. Осуществляется считывание очередного базового;сочетания каждым (l+M- I )-м импульс ом у поступившим по так товому входу 18, где i О, 1, 2, 3,... Р а импульсами (2+Mi)-{M + M4), гГде О, 1, 2, ..., 0. , проводится сдвиг содержимого кольцевого регистра и увеличение на единицу содержимого основного счетчика до состояния (М-1). При появлении импульса на последнем выходе 6 распределителя происходит считывание из блока памяти в кольцевой регистр единственно го неполного базового сочетания. Одновременно переводится в единичное положение триггер 14 по входу 15 установки в единицу. Триггер в единичном состоянии разрешает поступление импульсов через вспомогательный ключ на счетный вход вспомс)гательного счетчика. Теперь импульсы с тактового входа 18 рдновременно подаются на основной и вспомогательный счетчики. Пусть неполное базовое сочетание дает Т сочетаний. Сигнал на выходе вспомогательного счетчика появляется после перевода вспомогательного счетчика в (Т -1)состояние. При этом запрещается прохожде ние через основной ключ импульсов с такто вого входа 18 и одновременно на выходе 1 окончания перебора сочетаний образуется ;:игнап. Таким образом, по каждому импульсу, постутпсвшему по тактовому входу 18, iaa s выходах кольцевого регистра получаем очс Для N 6 н М 9 редное сочетание g 84 тактов, в то время ребуется С как для прототипа (авт.св. СССР №238 238 ) сМ С + 6 С/ -420 ji + N - K-i - 9 больще, чем в тактов, т. е. в пять раз предлагаемом устройстве. Формула изобретен и-я Устройство для перебора сочетавнй, с« держащее триггер, элемент ИЛИ, основвые и вспомогательные счетчики, ключи, элембвты задержки, отличающееся , что, с целью повышения быстродействия, в него введены блок памяти, кольцевой регистр и распределитель, причем установоч ный вход распределителя соединен с соответствующим входом устройства, первым входом элемента ИЛИ,; входами уставовки в иуль соответственно BcnoMoraTenbHCb го счетчика и триггера, входом установки ь (М-1)-е положение( где М-1, 2,..,К) х:новного счетчика, а выходы распределителя соединены соответственно с входами блока памяти, причем последний (К-ый) выход распределителя соединен с входом установки в единицу триггера, выход которого соединен с первым входом вспомогательного ключа, выход которого соединен со счет ным входом вспомогательного счетчика, выход которого соединен с выходом окончания перебора сочетаний устройства и с первым входом тактового ключа, второй вход которого соединен с тактовым входом устройства, а выход соединен со счетным входом основного счетчика, с вторым входом вспомогательного ключа и с входом основного элемента задержки, выход которого соединен со сдвигающим входом кольцевого регистра, выходы которого соединены с соответству|« шими выходами устройства, а входы соединены с выходами блока памяти, и вход установки в нуль соединен с выходом элемента ИЛИ, второй вход которого соединен с выходом основного счетчика и с входом вспомогательного элемента задержки, выход которого соединен с входом установки в нуль основного счетчика и с переклк чающим входом распределителя.

to

о

J,A

Л

«ЩИ ... ,«A

Ч

Ц

12

-о}}