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

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

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

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

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

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

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

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

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

четвертый элементов НЕ, выходы которых соединены с первыми входами соответствующих блоков элементов И, выход (4К+Р)-го (К 0-3, Р 1-4) разряда регистра соединен с входом Р-го разряда второго входа (К+1)-го

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

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

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

Устройство содержит регистр 1 четырехразрядного числа в двоичном коде, элемент ИЛИ 2, цифровую схему 3 сравнения

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

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

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

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

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

(см. последнюю строку таблицы) и на ее выходе А В появится 1, которая через элемент ИЛИ 2 поступит на счетный вход счетчика 4 и непосредственно на счетный

вход счетчика б, который переполнится и выдаст Г на вход 27 разрешения записи. В регистре 1 от внешнего источника по входу 8 будет записано одно из разрешенных чисел, например, 7326 в двоичном коде, как

0 показано на чертеже. В этот же момент

двухразрядное число 01 с выхода счетчика

4 (первая строка таблицы) поступит на вход

дешифратора 17, в результате чего с его

выхода единичный сигнал через элемент НЕ

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

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

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

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

Для получения следующей комбинации на вход 26 запуска подается единичный сиг5 нал, который установит в счетчике 4 двоичное число 10 (вторая строка таблицы), что приведет к закрытию блока 19 и та же цифра 0110 с выхода регистра 1 будет аналогичным образом подана на выходы 28, разо0 мкнутые блоком 19.

Блоки 18-21 в это время будут находиться в замкнутом состоянии. Установится очередная комбинация - число 7626,

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

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

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

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

сравнения, выход которой соединен с вторым входом элемента ИЛИ и со счетным входом третьего счетчика, выход переполнения которого соединен с входом разрешения записи регистра, и с входом сброса

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

первого по четвертый мультиплексоров и с соответствующими разрядами второго входа схемы сравнения, выходы дешифратора соединены соответственно с входами с первого по четвертый элементов НЕ, выходы г

которых соединены с первыми входами соответствующих блоков элементов И, выход (4К+Р)-го (К 0-3, Р 1-4) разряда регистра соединен с входом Р-го разряда второго входа (К+1)-го блока элементов И и с (К+1)-м

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

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

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