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

 

Изобретение относится к вычислительной технике и позволяет получить неповторяющиеся комбинации четырехразрядных чисел в двоичном коде с однократными повторениями цифр в каждой комбинации, причем эти комбинации могут быть заранее предсказаны и выдаются по запросу мгновенно. Целью изобретения является повышение быстродействия . Устройство содержит мультиплексоры 9-12, демультиплексоры 13-16, дешифратор 17, блоки 18-21 элементов И, элементы НЕ 22-25, счетчики 4-6, регистр 1, схему 3 сравнения и элемент ИЛИ 2.1 табл., 1 ил. X Ш Ш Ш 7 Ш I ч| N3 00 ю 00

союэ СОветских

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)э G 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЭОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4814999/24 (22) 16.04.90 (46) 23.06.92. Бюл. М 23 (71) Луганский филиал Конструкторского бюро автоматических линий (72) В.В.Голованов (53) 681.3 (088;8) (56) Авторское свидетельство СССР

hL 1388887, кл. G 06 F 15/20, 1986.

Авторское свидетельство СССР

М 622121, кл, G 06 F 7/38, 1977.

{54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА РАЗМЕЩЕНИИ

„„5Ц„„1742828 А1 (57) Изобретение относится к вычислительной технике и позволяет получить неповторяющиеся комбинации четырехраэрядных чисел в, двоичном коде с однократными повторениями цифр в каждой комбинации, причем эти комби-нации могут быть заранее предсказаны и выдаются по запросу мгновенно, Целью изобретения является повышение быстродействия. Устройство содержит мультиплексоры

9-12, демультиплексоры 13-16, дешифратор

17,.блоки 18-21 элементов И, элементы НЕ

22 — 25, счетчики 4-6, регистр 1, схему 3 сравнения и элемент ИЛИ 2. 1 табл., 1 ил.

1742828

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

Это устройство не обеспечивает перебора комбинаций с однократными повторениями, что ограничивает диапазон работы программирующего устройства из-за малого количества комбинаций.

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

Однако это устройство имеет низкое быстродействие, обусловленное тем, что процесс формирования комбинаций основан на пересчете импульсов.

Кроме того, вероятностный характер появления комбинаций не исключает возможности многократного повторения одних и тех же размещений, что также снижает быстродействие.

Целью .изобретения является повышение быстродействия.

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

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

Ь

50 ми разрядами управляющим входом с первого по четвертый демультиплексоров, с соответствующими разрядами входа дешифратора и с соответствующими разрядами первого входа схемы сравнения, выход которой соединен с вторым входом элемента ИЛИ и со счетным входом третьего счетчика, выход переполнения которого соединен с входом разрешения записи регистра и с входом сброса третьего счетчика, выход переполнения второго счетчика соединен с входом сброса второго счетчика, выходы первого и второго разрядов которого соединены с соответствующими разрядами управляющих входов с первого по четвертый мультиплексоров и с соответствующими разрядами второго входа схемы сравнения, выходы дешифратора соединены соответственно с входами с первого по четвертый элементов НЕ, выходы которых соединены с первыми входами соответствующих блоков элементов И, выход (4К+Р)-ro (К=Π— 3, P =1 — 4) разряда регистра соединен с входом Р-го разряда второго входа (К+1)-го блока элементов И и с (К+1}м информационным входом P-ro мультиплексора, выход P-ro мультиплексора соединен с информационным входом Р-го демультиплексора, выход

P-го разряда (К+1)-го блока элементов И соединен с (К+1)-м выходом P-ro демультиплексора и является информационным выходом (4К+Р)-го разряда устройства, выходы первого и второго разрядов первого счетчика выходы nepooro и второго разрядов второго счетчика и выход переполнения третьего счетчика являются соответственно выходами разрядов расширения устройства.

На чертеже изображена электрическая функциональная схема устройства для перебора размещений из m = 4 элементов по n =

4.

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

Устройство также содержит мультиплексоры 9 — 12, демультиплексоры 13-16, дешифратор 17, блоки 18-21 элементов И, элементы HE 22 — 25, вход 26 запуска устройства, вход 27 разрешения записи регистра.

На чертеже показаны также информационные выходы 28 устройства и выходы 29 разрядов расширения устройства.

1742828

Устройство характеризуется также новыми связями: вход запуска устройства соединен с первым входом элемента ИЛИ, выход которого соединен со счетным входом первого счетчика, выход переполнения которого соединен с входом сброса первого счетчика, выходы первого и второго разрядов которого соединены с соответствующими разрядами управляющих входом с первого по четвертый демультиплексоров, с соответствующими разрядами входа дешифратора и с соответствующими разрядами первого входа схемы сравнения, выход которой соединен с вторым входом элемента ИЛИ и со счетным входом третьего счетчика, выход переполнения которого соединен с входом разрешения записи регистра и с входом сброса третьего счетчика, выход переполнения второго счетчика соединен с входом сброса второго счетчика, выходы первого и второго разрядов которого соединены с соответствующими разрядами управляющих входов с первого по четвертый мультиплексоров и с соответствующими разрядами второго входа схемы сравнения, выходы дешифратора соединены соответственно с входами с первого по четвертый элементов НЕ, выходы которых соединены с первыми входами соответствующих блоков элементов И, выход (4К+Р)-ro (К = 0 — 3, P = 1 — 4) разряда регистра соединен с входом P-го разряда второго входа (К+1)-ro блока элементов И и с (К+1}-м информационным входом Р-ro мультиплексора, выход

P-го мультиплексора соединен с информационным входом P-ro демультиплексора, выход Р-ro разряда (К+1)-го блока элементов

И соединен с (К+1)-М выходом P-го демультиплексора и является информационным выходом (4К+Р)-ro разряда устройства.

Выходы первого и второго разрядов первого счетчика, выходы первого и второго разрядов второго счетчика и выход переполнения третьего счетчика являются соответст.венно выходами разрядов расширения устройства, которые в этом случае подключаются аналогичным образом к другому комплекту аналогичных. элементов схемы: 1, 9, 10, ..., 25,. 28. При этом комбинации размещений будут состоять из восьмиразрядных чисел.

Устройство для перебора размещений работает циклически, как показано в таблице истинности. При подаче питания статические цепи (не показаны) устанавливают счетчики 4 и 5 в "0", а счетчик 6 в положение

"3".-Однако это состояние будет кратковременным, так как на входы схемы 3 сравнения из счетчиков 4 и 5 поступят два равных двухразрядных двоичных числа "00" и "00" (см. последнюю строку таблицы) и на ее выходе "А = В" появится "1", которая через элемент ИЛИ 2 поступит на счетный вход счетчика 4 и непосредственно на счетный вход счетчика 6, который переполнится и выдаст "1" на вход 27 разрешения записи, В регистре 1 от внешнего источника по входу

8 будет записано одно из разрешенных чисел. например, "7326" в двоичном коде, как показано на чертеже. В этот же момент

10

Х демультиплексоров 13-16 и разомкнутым блоком 18 элементов И. Блоки 19 — 21 в зто время находятся в замкнутом состоянии, поэтому на выходах 28 установится первая комбинация, т.е. число "6326" в двоичном коде (первая строка таблицы).

Для получения следующей комбинации

30 на вход 26 запуска подается единичный сиг35 нал, который установит в счетчике 4 двоичное число "10" (вторая строка таблицы), что приведет к закрытию блока 19 и та же цифра

"0110" с выхода регистра 1 будет аналогичным образом подана на выходы 28, разомкнутые блоком 19.

Блоки 18 — 21 в это время будут находить40 ся в замкнутом состоянии. Установится очередная комбинация — число "7626", После подачи 4-го запускающего импульса на выходах первого и второго разря45 дов счетчиков 4 и 5 установятся числа "01", "01". Такое совпадение чисел не будет принято к исполнению, так как оно не ввдет к, появлению новой комбинации. В этом. слу50 чае сработает схема 3 сравнения и изменит состояние счетчика 4, на выходе которого установится число "10".При этом на счетный вход счетчика 6 будет подан импульс схемы 3 (пятая строка таблицы), а на выходах 28 установится число "7726" (шестая строка таблицы).

Аналогичным образом не будут приняты к исполнению совпадающие комбинации чисел "10" и "11" на выходах счетчиков 4 и 5 в моменты подачи соответственно 8-го и 1255 двухразрядное число "01" с выхода счетчика

4 (первая строка таблицы) поступит на вход дешифратора 17, в результате чего с его выхода единичный сигнал через элемент НЕ

15 22 закроет блок 18 элементов И,.разомкнув таким образом шины первого разряда, и на управляющие входы "АВ" демультиплексоров 13 — 16. На выходах счетчика 5 и управляющих входах "АВ" мультиплексоров 9 — 12

20 будет присутствовать число "00" (первая строка таблицы).

Поэтому выходы регистра 1 (где записана цифра "0110"), связанные с информационнымими входами Хо мультиплексоров 9-12, 25 будут подключены к информационным выходам 28 устройства, связанным с выходами

1742828

ro импульсов запуска, в результате чего на счетный вход счетчика 6 поступят еще 2 импульса схемы 3 сравнения. Третий импульс схемы 3 сравнения (предпоследняя строка . таблицы) установит счетчики 4 и 5 в состоя- 5 ния "00", "00", но и эти числа не являются реализуемыми, Поэтому схема 3 выдаст 4-й импульс (последняя строка таблицы), который установит счетчики 4, 5 в положение начала рассмотрения процесса (первая 10 строка таблицы), а импульс переполнения счетчика 6 поступит на вход 27 регистра 1 и на выходахего разрядов установится другое разрешенное четырехразрядное число. Начнется новый цикл перебора размещений. 15

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

Устройство для перебора размещений, содержащее регистр, элемент ИЛИ, схему 30 сравнения, с первого по третий счетчики, причем информационный вход устройства соединен с информационным входом регистра, выход переполнения первого счетчика соединен со счетным входом второго счет- 35 чика, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит четыре мультиплексора, четыре демультиплексора, дешифратор, четыре блока элементов И и четыре элемента НЕ, причем вход 40 запуска устройства соединен с первым входом элемента ИЛИ. выход которого соединен со счетным входом первого счетчика, выход переполнения которого соединен с входом сброса первого счетчика, выходы первого и второго разрядов которого соединены с соответствующими разрядами управляющих входов с первого по четвертый мультиплексоров, с соответствующими разрядами входа дешифратора и с соответствующими разрядами первого входа схемы сравнения, выход которой соединен с вторым входом элемента ИЛИ и со счетным входом третьего счетчика, выход переполнения которого соединен с входом разрешения записи регистра, и с входом сброса третьего счетчика, выход переполнения второго счетчика соединен с входом сброса второго счетчика, выходы первого и второго разрядов которого соединены с соответствующими разрядами управляющих входов с первого по четвертый мультиплексоров и с соответствующими разрядами второго. входа схемы сравнения, выходы дешифратора соединены соответственно с входами с первого по четвертый элементов НЕ, выходы, которых соединены с первыми входами соответствующих блоков элементов И, выход (4К+Р)-го (К = 0-3, P = 1-4) разряда регистра соединен с входом Р-го разряда второго входа (К+1)-го блока элементов И и с (К+1)-м информационным входом Р-ro мультиплексора, выход P-ro мультиплексора соединен с информационным входом Р-ro демультиплексора, выход Р-го разряда (K+1)-ro блока элементов И соединен с (К+1)-м выходом

P-го демультиплексора и является информационным выходом (4К+Р)-го разряда устройства, выходы первого и второго разрядов первого счетчика, выходы первого и второго разрядов второго счетчика и выход переполнения третьего счетчика являются соответственно выходами разрядов расширения устройства.

1742828

10 втт им" пульсов на входе 26

Примечание

Состояние выходов, счетчик 4!!нформационные выходы 28 счетчик 5

3-й раз- 4-й раз- 8 деся ряд ряд тичном коде

83 82 81 80.L

А3 A2 Al AO

2-й разряд

О О

О 1

О 1

О О

О О

0011 0010 0110 6326

0!10 0010 Î110 7626

0011 0110 0110 7366

0011 0010 Ollt 7327

О 0110

О 0111

О 0111

1 0111

1-й импульс компаратора 3 О О О О ! О О О

О О О 1

1 О О 1

О О О 1

О О 1

О О 1

О О О

О О О

0 О 1

1 0111

l 0111

О 0111

О 0011

0111

0011

0011

0111

6

О 011 1

1 0111

1 0010

1 01 11

О 1

О О

О О

О 1

О 1

1 О О 1

О О О 1

1 О О 1

0 О О 1

1 О О 1

0011

0011

001!

ОО!О

11

3-й импульс компврааора 3

4-й импульс компарвтора 3

0 О О 0 О О 0 О

Составитель А.Клюев

Редактор В.Бугренкова Техред М.Моргентал Корректор Н.Король

Заказ 2286 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж 35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, ИИ

1 О О О

О О О О

1 О О О

О О О О

1 О О О

0010 0110 7726

0111 0110 7376 У

0010 0011 7323 "

0010 0110 3726

2 и импульс компаратора 3

0011 0110 7336

0010 0010 7322

ОО!О 0110 2326

0110 0110 7226