Устройство для перебора соединений Советский патент 1982 года по МПК G06F7/06 G06F7/38 

I

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

Известен метод перебора таких соединений, как перестановка кодов на ЭВМ 1.

Однако это связано с нерациональным использованием дорогостоящего машинного времени.

Наиболее близкое к предлагаемому по техническому решению является устройство для перебора соединений, содержащее (п-1) счетчиков, где VI число переставляемых кодов, первый и второй элемент И, первую группу элементов ИШ, элемент задержки, при этом выход переноса i-го счетчика (..,п), кроме последнего, соединен со входом (i +1)-го счетчика, вход первого счетчика подключен к выходу первого элемента И, И запоминающих элементов, первую и.вторую

Группы элементов И, причем входы запоминающих элементов подключены к выходам элементов И первой группы, первый вход первого элемента И которой подключен к выходам элементов И второй группы, первые входы остальных элементов И первой группы подключены к выходам (i-l)-ro запоминающего элемента, выходы запоминающих элементов, начи10ная со второго, подключены к первым входам элементов И второй группы 2.

Недостатком этого устройства является невозможность реализации пе15рестановки кодов.

Цель изобретения - расширение класса решаемых задач за счет возможности перебора всевозможных перестановок кодов.

20

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

39

первый и второй элементы И, первую группу элементов ИЛИ, элемент задержки, при этом выход переноса /-го счетчика (..«n), кроме последнего, соединен со входом (1+1)-го счетчика, вход первого счетчика подключен к выходу первого элемента И, И запоминающих элементов и первую и вторую группы элементов И, причем входы запоминающих элементов подключены к выходам элементов И первой группы, первый вход первого элемента И которой подключен к выходам эле-. ментов И второй группы, первые входы остальных элементов И первой группы подключены к выходам (i-l)-ro запоминающего элемента, выходы запоминающих элементов, начиная со второго, подключены к первым входам элементов И второй группы, содержит третью, четвертую и пятую группы элементов И, группу элементов ШМ-НЕ, переключатель, элемент ИЛИ-НЕ, вторую группу элементов ИЛИ, первые входы j-ых элементов которой ,n-1 и второй вход (n-J)-ro связаны со вторыми входами k-ых: (.on) элементов И второй группы и через i-ые элементы И третьей группы - с выходами -1-ых элементов ШМ первой группы, подключенными к прямым выходам разрядов соответствующих счетчиков, а вторые входы i-ых элементов ИЛИ второй группы подключены к выходам (1+1)-ых-элементов ИЛИ второй группы и ко вторым входам k-ых элементов И первой группы, выход первого элемента ИЛИ второй группы подключен ко вторым входам первого и второго элементов И первой группы, инверсные выходы первых разрядов и прямые выходы остальных разрядов счетчиков подключены к входам элементов ИЛИ-НЕ, выходы которых подключены к первым входам элементов И четвертой группы, выходы которых подключены через элемент задержки к инверсным входам элементов И пятой группы, прямые входы которых связаны с выходами соответствующих запоминающих элементов, а выходы переноса счетчиков, кроме первого, соединены через элемент ИЛИ-НЕ с первым входом первого элемента И, а через переключатель - с первым входом .второго элемента И, выходы переноса счетчиков, кроме последнего, соединены со вторыми входами соответствующих элементов И третьей и четвертой групп, осталь5 ,4

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

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

Блок-схема содержит счетчик 1,

выходы устройства 2, первый 3 и второй 4 элементы И, первую группу элементов ИЛИ 5, вход устройства 6 элемент 7 задержки, запоминающие элементы 8, первую группу элементов И 9, вторую группу элементов И 10 третью группу элементов И I1, четвертую группу элементов И 12, пятую группу элементов И 13 группу элементов ИЛИ-НЕ 14, элемент

ИЛИ-НЕ 15, переключатель 16, вторую группу элементов ИЛИ 17, вход синхронизации счетчиков 18, распределитель 19 импульсов, объединяющий запоминающие элементы 8, первую группу элементов И 9, вторую группу элементов И 10, пятую группу элементов И 13,: вторую группу элементов ИЛИ 17.

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

Перед началом работы в запоминающие элементы В распределителя импульсов 19 записываются коды, соответствующие переставляемым объектам, С помощью переключателя 16 задается количество переставляемых объектов, при.этом количество счетчиков 1, подключенных через переключатель 16 должно быть на единицу меньше числа объектов. В счетчиках 1 автомати--

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

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

Счетчики 1 работают в два подтакта, при наличии импульса на 5 6 происходит подготовка записи последующего по порядку числа запись во вспомогательный регистр счет чика) в соответствугацем счетчике 1, а при отсутствии импульса - запись этого числа (перепись из вспомогательного регистра в основной), Циклы организуются следующим образом. При подаче тактовых импульсов на вход 6 выдается сигнал Сдвиг с выхода элемента И группы 11, связанного через элементы ИЛИ группы 5 с выходом- счетчика 1, следующего за счетчиком 1, на выходе переноса которого образуется высокий потенциал. К началу следующего такта содержимое счетчика 1, следукицего за обнуленным, уменьшается на единицу, а счетчик 1, находящийся в нулевом состоянии, принимает значение на еди ницу больше его номера. Если среди счетчиков 1 нет обнуленных, то выдача сигнала Сдвиг производится с элемента И группы 11 на выходе пер вого счетчика, в этом случае единица с выхода элемента И 4 проходит на вычитающий вход первого счетчика через элемент И 3, управляемый элементом ИЛИ-НЕ 15, на выходе которого имеется единица при отсутствии среди последующих счетчиков 1 обнуле ных. К началу следующего такта его с держимое первого счетчика уменьшается на единицу. При поступлении сигнала Сдвиг в распределителе 19 иМпульсов происходит циклический сдвиг кодов в элементах 8 памяти, определяемых элемен том И группы 11, с которого вьздается сигнал сдвига, при этом выход последнего из них через соответствующи элемент И группы 10 подключается к входу первого элемента 8 памяти. Есл содержимое счетчика 1 отлично от еди ницы, то сигнал с выхода элемента И группы 12 через элемент 7 задержки не блокирует группу элементов И 13 и содержимое распределителя импульсо поступает на выход устройства (выдается очередная перестановка), в противном случае содержимое распределит ля 19 импульсов на выход устройства 2 не поступает (вспомогательное состояние:) . При выборке всех и перестановок при И переставляемых объектах CKOяов), задаваемых с помощью переклю5 . 6 чателя 16, сигнал переноса с (п-1) счетчика 1 производит останов устройства (отключения входа устройства б) о Рассмотрим несколько тактов работы устройства. Пусть в элементах памяти записаны коды 1-4, а в счетчиках 1-2-4, тогда в первом такте производится обмен содержимого первого и второго элементов 8 памяти и уменьшение на 1 содержимого первого счетчика 1, который теперь содержит единицу и, следовательно, при следующем такте будет получено вспомогательное состояние устройства, не поступагацее на его выход и произойдет обнуление первого счетчика 1. В следующем такте при потенциале на выходе переноса первого счетчика I произойдет выдача сигнала сдвига элемента 11 Второго счетчика 1 и уменьшение его содержимого на единицу, при этом в распределителе 19 импульсов произойдет циклический сдвиг, захватывающий первые три регистра 8. Таким образом, в распределителе 19 импульсов будет записано: 2,3,1,4, а в счетчиках 1 - 2,2,4 и т.д. Предлагаемый принцип работы устройства достаточен для получения всех перестановок кодов (объектов), Ниже для пояснения принципа работы устройства приведены все Vi 24 перестановки для 4-х объектов, обозначенных через 1,2,3,4, состояния устройства, не поступающие на его выход (вспомогательные), заключены в скобки. Для каждого состояния представлено содержимое счетчиков 1 к концу соответствующего такта: 1,2,3,4 2,3,4 2,1,3,4 1,3,4 (1,2,3,4) 0,3,4 2,3,1,4 2,2,4 3,2,1,4 1,2,4 (2,3,1,4) 0,2,4 3,1,2,4 2,1,4 1,3,2,4 Г,1,4 (3,1,2,4) 0,1,4 (1,2,3,4) 2,0,4 2,3,4,1 2,3,3 3,2,4,1 1,3,3 (2,3,4,1) 0,3,3 3,4,2,1 2,2,3 4,3,2,1 1,2,3 (3,4,2,1) 0,2,3 4,2,3,1 2,1,3 2,4,3,1 1,1,3 .(4,2,3,0 0,1,3

(2.3.4.1)2,0,3 3,4,1,2 2,3,2 4,3,1,2. 1,3,2

(3,4,1,2; 0,3,2

4,1,3,2 2,2,2

1,4,3,2 1,2,2 (4,1,3,2; 0,2,2

1,3,4,2 2,1,2

3.1.4.21,1,2

(1.3.4.2)0,1,2

(3.4.1.2)2,0,2

4.1.2.32,3,1 1,4,2,3 1,3,1

(4.1.2.3)0,3,1 1,2,4,3 2,2,1 2,1,4,3 1,2,1

(1,2,4,3) 0,2,1

2,4,1,3 . 2,1,1

4,2,1,3 1,1,1 (2,4,1,3) 0,1,1

(4.1.2.3)2,0,1

(1.2.3.4)2,3,0

При появлении нуля в третьем счике 1 перебор перестановок прекрщается..

Предлагаемое устройство позволет осуществить перебор всевозможных перестановок кодов и может бы использовано в качестве составной части (блока) ЭВМ для решения комнаторных задач..

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

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

ИЛИ-НЕ, переключатель, элемент ИЛИ-НЕ вторую группу элементов ИЛИ, первые входы -ых элементов которой 2,„.„ п-1 и второй вход (n-l)-ro связаш

со вторыми входам k-ых (,on) элементов И второй группы и через -(-ые элементы И третьей группы - с выходами -f-ых элементов |ШИ первой группы, подключенными к прямым выходам разрядов соответствукядих счетчиков, а вторые входы f-ых элементов ИЛИ второй группы подключены к выхо- . дам ()-ых элементов ШШ второй группы и ко вторым входами k-ых элементов И первой группы, вгиход первого элемента ИЛИ второй группы подключен ко вторым входам первого и второго элементов И первой группы, инверсные выходы первых разрядов и прямые выходы остальных разрядов счетчиков подключены к входам элементов MJBl-HE, выходы которых подключены к первым входам- элементов И четвертой группы, выходы которых подключены

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

кроме первого, соединены через элемент ИЛИ-НЕ с первым входом первого элемента И, а через переключательс первым входом второго элемента И, выходы переноса счетчиков, кроме

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

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

Источники информации,

принятые во внимание при экспертизе

1.Implementation of permutation functions in illlac, IV - Type Computers, iEEE, trans Computers. 1976,

25, (ПГ, p. 929-936.

2.Авторское свидетельство СССР N 374606, кл. G Об F 15/34, 1970 (прототип),