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

 

Союз Советсиии

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

Республик

<и> 11

К АВТОРСИОМУ СВИДЕТЕЛЬСТВУ (6I ) Допвлнительное к авт. свид-ву (22)Заявлено 24.05.78 (21) 2619268/18-24 (51)М. Кл.

G 06 F 15/20 с присоединением заявки М

1ооударстмкиый комитет (23) Приоритет, (53) УДК 681.325

{088.8) IIo делам изооретеиий и открытий

Опубликовано 07.03.82. Бюллетень М 9

Дата опубликования описания 07.03.82 м

Г.С.Цирамуа, Г.А.Чихладзе, В.А.Богатыреф и Л.Ш .Кмнаишвили

Грузинский ордена Ленина и ордена Трудового Красного.... ана ни политехнический институт им. В.И.Ленина (72) Авторы изобретения (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЕДИНЕНИЙ

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

Известен метод перебора таких соединений, как перестановка кодов на 3BN 1 11.

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

Наиболее близкое к предлагаемому по техническому решению является устройство для перебора соединений, содержащее (п-1) счетчиков, где И число переставляемых кодов, первый и второй элемент И, первую группу элементов ИЛИ, элемент задержки, при этом выход переноса 1 -го счетчика (1 2...n), кроме последнего, соединен со входом (i+1)-ro c er za, вход первого счетчика подключен к выходу первого элемента И, И запоминающих элементов, первую и.вторую группы элементов И, причем входы запоминающих элементов подключены к выходам элементов И первой группы, первый вход первого элемента И которой подключен к выходам элементов И второй группы, первые входы остальных элементов И первой группы подключены к выходам (i-1) -го запоминающего элемента, вы10 ходы запоминающих элементов, начиная со второго, подключены к первым входам элементов .И второй группы t 21.

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

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

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

11 запоминающих элементов и первую и На чертеже представлена блок-схема вторую группы элементов И, причем предлагаемого устройства, входы запоминающих элементов подклю- !0 Блок-схема содержит счетчик 1, чены к выходам элементов И первой первыи и второй выходы устройства 2 " 3 группы, первый вход первого элемента . 4 элементы И, первую группу элементов

И которой подключен к выходам эле- ИЛИ 5, вход устройства 6 элемент 7 ментов И второй группы, первые входы задержки, запоминающие элементы 8 перЭ Э остальных элементов И первой группы !з вую группу элементов И 9, вторую групподключены к выходам (i-1)-го запоми- пу элементов И 10 третью тью группу эленающего элемента, выходы запоминаю- ментов Я .11, четвертую группу элеменщих элементов, начиная со второго, тов И 12, пятую группу элементов И !3

И вт подключены к первым входам элементов группу элементов HJIH-НЕ !4 элемен

t нт второй группы, содержит третью, zp HJIH-НЕ 15, переключатель 16, вторую четвертую и пятую группы элементов группу элементов ИЛИ !7, вход синхроИ, группу элементов HJ1H-НЕ, переклю- низации счетчиков 18, распределитель чатель, элемент ИЛИ-НЕ, вторую груп- 19 импУльсов, объединяющий запоминапу элементов ИЛИ, первые входы -ых ющие элементы 8, пеРвУю гРУппУ элеменэлементов которой 1=2...и-1 и второй 25 тов И 9, вторую группу элементов вход (и-!) -го связаны со вторыми вхо- И 10 пЯтУю гРУппУ элементов И 13,: дами k-ых: (k=1 n) элементов И вто- вторую гРУппУ элементов ИЛИ 17. рои группы и через 1-ые элементы И Устройство работает следующим обтретьей группы — с выходами -ых эле- Разомментов ИЛИ первой группы, подключен- З0 Перед началом работы в запомина" ными к прямым выходам Разрядok сост- ющие элементы 8 распределителя имветствующих счетчиков, а вторые вхо- пульсов 19 записываются коды, соотцы 4 -ых элементов ИЛИ второй группы ветствующие переставляемым объектам, подключены к выходам (i+1)-ых.эле- С помощью переключателя 16 задаетментов ИЛИ второй группы и ко вторым З5 сЯ количество пеРеставлЯемых объеквходам 1 -ых элементов И первой груп- тов, пуи этом количество счетчиков bi îä первого элемента ИЛИ вто- 1, подключенных чеРез пеРеключатель рой группы подключен ко вторым вхо16 должно быть на единицу меньше чисд первого и второго элементов И пер- ла объектов. В счетчиках 1 автомати ой груп инверсные выходы первых 40 чески записываетсЯ. число, соответразрядов и прямые выходы остальных ствующее на .единицу увеличенному разрядов счетчиков подключены к вхо- его номеру, при этом коэффициенты дам элементов ИЛИ-НЕ, выходы которых пеРесчета вычитающих счетчиков таподключены к первым входам элементов

H четвертой группы, выходы которых 45 ть пЯть записываетсЯ это подключены через элемент задержки к число. инверсным входам элементов И пятои Пе ерестановка кодов реализуется группы, прямые входы которых связаны в распределителе 19 импульсов путем с выходами соответствующих запомина- циклического сдвига с изменяющимющих элементов, а выходы переноса 50 ся .ислом э ся числом элементов 8 памяти, учасчетчиков, кроме первого, соединены ствующих в нем. Сдвиги управляются через элемент ИЛИ-НЕ с первым входом счетчиками 1, соединенными так чтот так, чтопервого элемента Л, а через переклю- бы организовать циклическое (цикл чатель — с первым входом, второго эле- . в цикле) изменение числа элементов мента И, выходы переноса счетчиков 5 8 памяти участвую

Э ствующих в циклическроме последнего, соединены со вторы- ком сдвиге. ми входами соответствующих элементов Счетчики 1 работают в два подтакИ третьей и четвертой групп, осталь- та, при наличии импульса на входе

5 9115

6 происходит подготовка записи последующего по порядку числа !запись во вспомогательный регистр счетчика) в соответствующем счетчике 1, а при отсутствии импульса — запись 5 этого числа (перепись из вспомогательного регистра в основной), Циклы организуются следующим образом.

При подаче тактовых импульсов на вход 6 выдается сигнал "Сдвиг" с 1О выхода элемента И группы 11, связанного через элементы ИЛИ группы 5 с выходом счетчика 1, следующего за счетчиком 1, на выходе переноса которого образуется высокий потенциал.

К началу следующего такта содержимое счетчика 1, следующего за обнуленным, уменьшается на единицу, а счетчик 1, находящийся в нулевом 20 состоянии, принимает значение на единицу больше его номера. Если среди счетчиков 1 нет обнуленных, то выдача сигнала "Сдвиг" производится с элемента И группы 11 на выходе пер-25 вого счетчика, в этом случае единица с выхода элемента И 4 проходит на вычитающий вход первого счетчика через элемент И 3, управляемый элементом ИЛИ-НЕ 15, на выходе которо- 30 го имеется единица при отсутствии среди последующих счетчиков 1 обнуленных. К началу следующего такта его содержимое первого счетчика уменьшается на единицу. 35

При поступлении сигнала "Сдвиг в распределителе 19 импульсов происходит циклический сдвиг кодов в элементах 8 памяти, определяемых элементом И группы 11, с которого выдается 40 сигнал сдвига, при.этом выход последнего из них через соответствующий элемент И группы 10 подключается к входу первого элемента 8 памяти. Если содержимое счетчика 1 отлично от еди- 45 ницы, то сигнал с выхода элемента

И группы 12 через элемент 7 задержки не блокирует группу элементов И 13 и содержимое распределителя импульсов поступает на выход устройства (выдается очередная перестановка), в противном случае содержимое распределите" ля 19 импульсов на выход устройства

2 не поступает (вспомогательное состояние), При выборке всех й, перестановок ! при VI переставляемых объектах (кодов), задаваемых с помощью переклю35 6 чателя 16, сигнал переноса с (и-1) счетчика 1 производит останов устройства (отключения входа устройства 6).

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

В следующем такте при потенциале на выходе переноса первого счетчика произойдет выдача сигнала сдвига элемента 11 второго счетчика 1 и уменьшение его содержимого на единицу, при этом в распределителе 19 импульсов произойдет циклический сдвиг, захватывающий первые три регистра 8. Таким образом, в распределителе 19 импульсов будет записано: 2,3,1,4, а в счетчиках l — 2,2,4 и т.д.

Предлагаемый принцип работы устройства достаточен для получения всех перестановок кодов (объектов). Ниже для пояснения принципа работы устройства приведены все й, =24 пере-! становки для 4-х объектов, обозначенных через 1,2,3,4, состояния устройства, не поступающие на его выход (вспомогательные), заключены в скобки. Для каждого состояния представлено содержимое счетчиков I к концу соответствующего такта:

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

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

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

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

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

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

Устройство для перебора соединений, содержащее (n-1) счетчиков, где

И вЂ” число переставляемых кодов, первый и второй элементы И, первую группу элементов KIH, элемент задержки, 40 при этом выход переноса --го счетчика (i=2.. .и), кроме последнего, соединен со входом (i+1)-го счетчика, вход первого счетчика подключен к выходу первого элемента И, И И запоминающих элементов, первую и вторую группы элементов И, входы запоминающих элементов подключены к выходам элементов И первой группы, первый вход первого элемента И которой подключен к выходам элементов И второй группы, первые входы остальных элементов И первой группы подключены к выходам (i-1) "го запоминающего элемента, выходы запоминающих элементов, начиная со второго подключены к первым входам элементов И второй группы, о тл и ч а ю щ е. е с я тем, что, с целью расширения класса решаемых задач за счет возможности перебора всевозможных перестановок кодов, оно содержит третью, четвертую и пятую группы элементов И группу элементов

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

1-ые элементы И третьей группы — с.

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

ИЛИ второй группы подключены к выхо- . дам (i+1) -ых элементов ИЛИ второй группы и ко вторым входами k-ых элементов И первой группы, выход первого элемента ИЛИ второй группы подключен ко вторым входам первого и второго элементов И первой группы, инверсные выходы первых разрядов и прямые выходы остальных разрядов счетчиков подключены к входам элементов

ИЛ!1-НЕ, выходы которых подключены к первым входам элементов И четвертой группы, выходы которых подключены через элемент задержки к инверсным входам элементов И пятой группы, прямые входы которых связаны с выходами соответствующих запоминающих элементов, а выходы переноса счетчиков, кроме первого, соединены через элемент ИЛИ-HE с первым входом первого элемента И, а через переключательс первым входом второго элемента

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

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

Источники информации, принятые во внимание при экспертизе !. Implementation of permutation

functions in iiiiac, lV - Туре Com"

puters, !ЕЕЕ, Trans. Computers. !976, 25, Н Ъ, р. 929-93Ь, 2. Авторское свидетельство СССР !! 374606, кл. G 06 F !5/34, 1970 (прототип).