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

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

Иллюстрации

Показать все

Реферат

 

1т Атал .1Я бк -анко тм ит ":-. Ф

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Сфк а Сфветс аии

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

Республик (11) 525948

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22) Заявлено03.09.73 (21) 1956682/24 с присоединением заявки ¹ (23) Приоритет (43) Опубликовано 25.08.76Бюллетень X 31 (45, Дата опубликования описания 21.02.77 (51) M. Кл, G 06 Г 7/00

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

Савета Министров СССР ав делам изобретений и открытий (53) УДК

681.332.65 (088.8) (72) Автор изобретения

В. В. Епихин (71) Заявитель (54) УСТРОЙСТВО ЯЯ ПЕРЕЙРА СОЧЕТАНИЙ

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

Известные устройства обладают низким быстродействием и не поз>воляют осушествить выдачу очередного сочетания в каждом такте ere работы.

Lleab изобретения — повышение быстро— действия.

Зто достигается тем, что входы блоков перебора соединены со входами первого элемента "И", выход которого подключен ко входу сброса распределителя и через элемент задержки ко входу сброса блоков перебора, управляюший вход первого из которых подключен к выходу второго элемента "И", один из входов которого соединен с выходом второго блока перебора, а другой вход — с его у-правляюшим входом и с выходом третьего элемента "И", один из входов которого соединен с выходом второго блока перебора, а другой вход- с его управляюшим входом и с выходом третьего элемента "И", один из входов которого и один из входов чет вертого элемента "И" подключены к шине тактовых сигналов, à нх другие входы соеены с соответствуюшими выходами триггера, входы которого подключены к выходу первого элемента "И" и через другой эле..ент задержки к управляюшему входу распределителя и к выходу четвертого эпемен// 1 fl т=i,

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

Оно содержит блок памяти 1, блок пе20 ребора 2 с выходами 3 и управляющим входом 4, блок перебора 5 с выходами 6 и управляющим входом 7, элемент "И" 8, элемент задержки 9, элементы "И" 10 и

11, триггер 12 со входом установки в

25 единичное состояние 13, входом установ525948

10!

Для М = 4

0000 = О

00011

001011

010011

010101

0001 =1

001 1

0101

0111 = 3

1111 = 4

001111

010111 = 4

011011

011111 = 5

llllll = 6

Для М = 5

00000 = О

00001 = 1

0001 11

ОО101)

001111

О1О11

11000 1111000

1lOOO 1110100

11000 1110010

11111 1000000

11110 1100000

11110 1010000 ки в нулевое состояние 14, прямым выхо дом 15 и инверсным выходом 16, элемент

"И" 17, элемент задержки 18, распределитель 19, шину 20 тактовых импульсов, шину 21 установки и шину 22 окончания работы.

Устройство работает следующим образом, Перебор сочетания из М элементов по и заменяется перебором двух сочетаний, каждое из которых в качестве исходных имеет полное базовое сочетание. Полным базовым сочетанием называется такое сочетание, из которого можно получить М (включая исходное) различных сочетаний благодаря циклическому сдвигу исходного сочетания. Например, из сочетания

111... 11000.... 00

Д можно получить еше М-1 сочетаний благодаря его циклическому сдвигу.

Базовые сочетания подбираются по опре» деленным правилам. Для некоторых значений М и значений М (от О до Й ) все базовые сочетания будут равны:

Для М = 3 Для М = 6

ООО = О 000000 = О

001 = 1 000001 = 1

011 = 2 000011

111 = 3 000101 = 2

001001

01111 = 4

11111 = 5

Для любых значений N и М двоичные базовые сочетания получают путем всех комбинаций соответствующих базовых сочетаний, например, для N = 6 и М = 12 соответствуют следующие базовые сочетания (R =5,Т=7):

4

1lllO 1OOlOOO llOOO l1Ol1OO

1l1OO l1lOOOO 11000 1101010

11100 11О1ООО 1О1ОО 1111000

l1lOO 11OO1OO 1О1ОО 111OlOO

11100 1100010 1О1ОО 111OO1O

111ОО 10101ОО 101ОО 11О11ОО

11О1О 111ОООО 1О1ОО 11О1О1О

11010 11О1ООО 1ОООО lllllOO

11О1О 11ОО1ОО 1ОООО 111101О

1lOlO 1100010 1ОООО 1110110

1lO1Î 1О1О1ОО ООООО 111111О

Таким образом, каждое сочетание из двенадцати по шести можно представить в виде комбинации двух базовых сочетаний (дво ных базовых сочетаний).

При этом исходные базовые сочетания имеют разрядность R и Т (R + Т = М).

Максимальное количество сочетаний, которое можно получить из двойного базового, равно R ° Т (включая само двойное базовое сочетание).

Порядок получения всех сочетаний из двойных базовых следующий.

Сначала сдвигается циклически одно из составляющих сочетаний; если оно содержит Т разрядов, то сдвигается (Т-1 ) раз, и после этого осуществляется одновременный циклический сдвиг первого и второго составляющих сочетаний. Такая процедура повторяется К раз.

Рассмотрим работу устройства на примере перебора сочетаний при М = 12, Й =

= 6, R = 5 и Т = 7.

Перед началом работы устройство устанавливают в исходное состояние по шине

20. При этом триггер 12 устанавливается в единичное состояние, распределитель 19 в первое положение. а блоки перебора 2 и 5 — в нулевое состояние. Блок перебора

2 имеет пять разрядов и первые пять выходов блока памяти 1 подключены к его входам. Блок перебора 5 имеет семь разрядов, и к его входам подключены семь последних выходов блока памяти 1. Далее по шине 20 начинают поступать тактовые импульсы. Так как перед поступлением первого тактового импульса триггер 12 находится в единичном состоянии, открыт элемент "И" 1.7, и первый тактовый импульс через элемент И" 17 поступает на продвижение распределителя 19. Распределитель 19 переводится во второе положение, при этом на его первом выходе появляется импульс, который производит считывание первой строки из блока памяти 1. Содержимое первой строки из блока памяти 1 записывается в блоках перебора 2 и 5.

В результате этого в блоке перебора 2

525 948 имеется базовое сочетание 11111, а в блохе перебора 5 — базовое сочетание

1000000.

Блоки перебора 2 и 5 осуществляют Ь циклический сдвиг их содержимого. Сигнал на управляющих входах 4 или 7 блоков перебора 2 или 5 появляется в случае, если на все разряды блока перебора поданы из блоха памяти 1 все единицы или все нули, а также в том случае, если содержимое блока циклически сдвигается на величину равную разрядности блоха, уменьшенную на единицу, т.е. для блока перебора 2 после четырех сдвигов, а для блоха перебора 5 — после шести сдвигов.

На выходах 3 и 6 блоков перебора 2 и 5 появляются сочетания двенадцати элементов по шесть. После первого тактового импульса на выходах 3 и 6 блоков пере20 бора 2 и 5 будет первое сочетание

111111000000.

Так как импульс с выхода элемента "И"

17 поступил на вход элемента задержки

18, перед приходом второго тактового импульса триггер 12 находится в нулевом состоянии и открыт элемент "И" «1.

Последующие шесть тахтовых импульсов, поступивших по шине 20, пройдут. через элемент И 11 на продвижение блока перебора 5 и на вход элемента "И" 10. Элемент "И"

10 открыт, если на управляющем входе 7 блока перебора 5 имеется сигнал.

Таким образом, по шести последующим тактовым импульсам получим следующие сочетаниЯ: lj 11) 01000QQ

111110000100 40

111110000001

Таким образом, произошло шесть циклических сдвигов содержимого блока перебора 5. После этого на управляющем входе 7 блока перебора 5 появляется сигнал, Тах как и на управляющем входе 4 блока

2 имеется сигнал, собирается элемент "И"

8, и по переднему фронту сигнала с его щ выхода перебрасывается триггер 12 в единичное положение и сбрасываются блоки перебора 2 и 5 в нулевое положение через первый элемент задержки 9. Следующий тактовый импульс через элемент "И" 17 пере- ц ведет распределитель 19 в третье положение, и происходит считывание второй строки блока памяти 1. В результате на выходах 3 и 6 блоков перебора 2 и 5 имеется сочетание 111101100000. 60

Триггер 12 импульсом с элемента задержки 18 перебрасывается в нулевое состояние и открывается элемент "И" 11.

Следующие шесть тахтовых импульсов поступят на продвижение блока перебора 5, в результате чего получим следующие сочетания:

llll00000110

111100000011

111101000001

Так как содержимое блока перебора 5 сдвигалось шесть раз, на управляющем входе 7 появляется сигнал, который откры вает элемент "И" 10, Следующий тактовый импульс осуществит циклический сдвиг содержимого блока перебора 2 и содержимого блока перебора 5. При этом на управляющем входе 7 блока перебора 5 пропадает сигнал и сдвиг этим тактовым импульсом не входит в подсчет импульсов сдвига для выдачи сигнала на управляющем входе 7. В результате получаем очередное сочетание 011111100000.

Последующие шесть тактовых импульсов поступят на продвижение только блока перебора 5 и в результате получим еше шесть из двенадцати по шесть:

011110000011

011110000001

Далее опять происходит одновременный циклический сдвиг содержимого блоков перебора 2 и 5 при поступлении очередного тактового импульса. Последующие шесть тактовых импульсов циклически сдвигают только содержимое блока перебора 5 и т.д. до тех пор, пока на управляющих входах

4 и 7 одновременно появятся сигналы. После этого происходит сброс содержимого блоков перебора 2 и 5 и очередной так— товый импульс, поступивший по шине 20, продвинет распределитель 19 в следующее положение и произойдет считывание очередной строки блока памяти 1 в блоки перебора 2 и 5. Далее опять продолжается циФлический сдвиг содержимого блоков перебора 2 и 5. Этот процесс повторяется до тех пор, пока не будут считаны все стрс ки блока памяти 1 и на шине 22 (последний выход распределителя 19) не появится импульс, сигнализируюший об окончании перебора сочетаний.

525 948

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

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

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

525948

Составитель В. Белкин

Редактор Н. Данилович Техред М. Левицкая Корректор Т. Чаброва

Заказ 5450/204 Тираж 864 Подписное

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

1l3035,Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул, Проектная, 4