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

эо

Ч

СО 9

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

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

На чертеже представлена схема устройства для переставляемых элементов.

Устройство содержит группу счетчиков 1(- 1, группу элементов И 2,- 2, группу элементов запрет 3i 3, группу элементов ИЛИ 4(- 4, группу регистров 5,- 5 сдвига, коммутаторы 6-10, элемент НЕ 11, . триггер 12, элемент И 13, счетчик 14, вькоды 15-19 устройства, тактовы вход 20, выход 21 признака окончания перебора,, выход 22 признака окончани выдачи одной перестановки, вход 23 установки исходного состояния, групп 24,- 244 триггеров, модуль счетчика 1, равен двум, у каждого последующег счетчика - на единицу больше.

1

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

Последовательность обменов в соответствии с используемым алгоритмом для случая 4-х переставляемых элементов (элемент представлен числом в десятичной системе, а пары разрядов, между которыми происходит обмен элементами, указаны дугами) имеет ви

1.1234 12о3412

V-

2, 2 1 3 4

-J

3,2314

4.3 4

5.3 1 2 4

6.1 3 2 4

V1

13о 4J 21

14.3

15. 41

16.

17.. 2 А 31

23, 1 243

5

0

0

5

0

5

0

5

24. 2 1 4 3

tf- - -J

Устройство работает в двух режимах: в режиме выдачи паралельного кода перестановок и в режиме пространственно-временной формы последовательности появления сигнала на выходах устройства..

В режиме пространственно-временной формы представления перестановок по сигналу, поступающему на вход 23, счетчики - 1, триггер 12 и триггеры 24 2. - 24 устанавливаются э , нулевое состояние, триггер 24,, первый разряд регистра 5( сдвига, второй разряд регистра 5 сдвига, третий разряд регистра 5 сдвига, четвертый разряд регистра 5 сдвига и пятый разряд регистра 5 сдвига устанавливаются в единичные состояния. При этом на выходах 15 появляется код 10000,означающий,что первая цифра йервой перестановки находится на первой позиции. Перед - ний фронт тактового импульса не изменяет состояния устройства, так как элемент И 13 закрыт, а триггер 12 срабатывает по переднему фронту импульса. По заднему фронту первого тактового импульса через открытый элемент НЕ 11 триггер 12 переходит в единичное состояние и открывает элемент И 13 для прохождения следующих тактовых импульсов на регистры 5(- 5, Таким образом, первому тактовому импульсу соответствует код 10000 на выходах 15.

На втором выходе счетчика 14 появляется каждый in-й тактовый импульс, а на первом выходе - второй и каждый (1п+2)-й импульс, где ,2,,.

Второй тактовый импульс проходит через открытьй элемент И 13 и поступает на синхровходы регистров 5 сдвига, а также через счетчик 14 - на счетные входы счетчиков 1,, ..,, 1, в результате чет о счетчик 1, переходит в единичное состояние, сигнал с выхода которого, пройдя через открытые элементы 3. и

4, появляется

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

20

ноль из последнего разряда регистра 5 - в первый разряд регистра 5 . При этом на выходах 15 появляется код 01000. Так как после пяти первых тактовых импульсов состояния триггеров 24 - 244 не изменяется, то регистры 5, и 5 сдвига полностью обменяются содержимым, а содержимое регистров 5 - 5 будет таким же как и в исходном состоянии, причем после прихода каждого тактового импульса на выходах 15 появляются коды расположения очередной цифры первой nepe- s становки. По приходу пятого тактового импульса одновременно с перезаписью состояний регистров 5 сдвига появляется сигнал на выходе счетчика 14, а в результате чего триггер 242. переходит в единичное состояние, а триггер 24( обнуляется.

Под действием сигнала на вых-оде триггера 24 коммутаторы 7 и 8 соединяют выход регистра 5 сдвига со вхоРабота устройства в режиме форми- рования перестановок в форме параллельного кода отличается только тем, что параллельные коды снимаются с вы- 5 ходов, 15-19 после каждого (in)-ro импульса, а код первой перестановки после импульса установки каждого состояния .

30

Кроме того, в устройстве на выходах 15-19 можно получить информацию одновременно о положении п единиц генерируемой последовательности перестановок.

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

Устройство для перебора перестановок, содержащее группу из n-l счетчиков (п - количество элементов перебора), группу элементов ЗАПРЕТ, группу элементов 1-ШИ и группу из п-1 триггеров, отличающееся тем, что, с целью упрощения и повьшения быстродействия, оно содом регистра 5, сдвига и выход регист- б з п- элементов И, ра 5j с входом регистра 5, выходы

п п-разрядных регистров сдвига, счетчик по модулю п, триггер, элемент Й элемент НЕ, п коммутаторов, причем выход i-ro коммутатора, (, ...п) 0 соединен с информационным входом. i-ro регистра сдвига, выход j-ro регистра сдвига (, ..., п-2) соединен с первым информационным входом j-ro коммутатора, с вторым информаостальных регистров будут соединены со своими же входами.

После прихода очередных 6-10 тактовых импульсов поменяются содержимым регистры 52 и 5}, а содержимое остальных регистров станет таким же как после прихода 5-го тактового импульса. Причем после прихода каждого

.из этих импульсов на выходах 15 будут 45 ционным входом (j-l)-ro коммутатора появляться коды расположения очеред- и с третьим информационным входом ной цифры второй перестановки. (j+1)-ro коммутатора, выход (п-1)

I го регистра сдвига соединен с перПосле прихода каждого (in)-го им- информационным входом пульса состояния триггеров 24 изменя- gQ коммутатора, с вторым информационным

входом {п-2)-го коммутатора и с вторым информационным входом п-го коммутатора, выход п-го регистра сдвига соединен с вторым информационным вхо- 55 дом (п-1)-го и первым информационным входом п-го коммутаторов, выход j-ro триггера группы соединен с первым инверсным и первым прямым управляющими входами j-ro коммутатора, вторым

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

сле каждого 24-го, на выходе элемента И 2} после каждого 120-го импульса. Элементы ИЗ, И За пропускают импульсы только .со старших разря- дов регистров 1, а элементы ИПИ 4, 4,2 одновременно пропускают и тульсы на входы триггеров 24 младших разрядов, совпадающих по четности со старшими.

Работа устройства в режиме форми- рования перестановок в форме параллельного кода отличается только тем, что параллельные коды снимаются с вы- ходов, 15-19 после каждого (in)-ro импульса, а код первой перестановки после импульса установки каждого состояния .

Кроме того, в устройстве на выходах 15-19 можно получить информацию одновременно о положении п единиц генерируемой последовательности перестановок.

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

Устройство для перебора перестановок, содержащее группу из n-l счетчиков (п - количество элементов перебора), группу элементов ЗАПРЕТ, группу элементов 1-ШИ и группу из п-1 триггеров, отличающееся тем, что, с целью упрощения и повьшения быстродействия, оно з п- элементов И,

п п-разрядных регистров сдвига, счетчик по модулю п, триггер, элемент Й элемент НЕ, п коммутаторов, причем выход i-ro коммутатора, (, ...п) соединен с информационным входом. i-ro регистра сдвига, выход j-ro регистра сдвига (, ..., п-2) соединен с первым информационным входом j-ro коммутатора, с вторым информаинверсным и вторым прямым управляющим входами (j+1)-ro коммутатора, выход (п-1)-го триггера группы соединен с первым инверсным и первым прямым управлякнцими входами (п-1)-го И п-го коммутаторов, единичный вход k-ro триггера группы (,,,.п-3) соединен с выходом соответствующего элемента ИЛИ группы, единичньй вход (п-2)-г о триггера группы соединен .с выходом (п-З)-го элемента ЗАПРЕТ 1|руппы, а единичный вход (n-l)-ro триггера группы соединен с выходом (п-З)-го элемента И группы и первым йходом (п-З)-го элемента ШШ группы, Синхровходы всех триггеров соединены с первым информационным выходом счетчика, второй информационный вы- Ход которого соединен со счетными йходами всех счетчиков группы и выходом признака окончания вьщачи одной перестановки устройства, счетный вход счетчика соединен с тактовым входом устройства и с первым входом элемента И, второй вход которого соединен с выходом триггера, единичный вход и вход установки начального состояния которого соединены соответственно с выходом элемента НЕ и входом установки начального состояния устройства, соединенного с

одноименными входами всех счетчи-, ков группы, триггеров группы и регистров сдвига, синхровходы которых соединены с выходом элемента И, выходы j-ro элемента И группы соединены с выходами с первого по (j+1)-u счетчиков группы, инверсный выход первого счетчика группы соединен с первым входом первого элемента ИЛИ группы, а прямой выход первого С етчика группы соединен с синхровходом|второго счетчика группы, с прямым входом первого элемента ЗАПРЕТ группы, выход к-го элемента И группы соединен с сийхровходом (к+2)-го счетчика и с соотв.етствуннцимк входами всех элементов ЗАПРЕТ группы, выход (2р-1)- го элемента ЗАПРЕТ группы (,...

Гп-3 LTj

)

соединен с соответствующими

входами всех четных элементов ИЛИ, начиная с второго и до (2р)-го, а выход каждого (2р)-го элемента ЗАПРЕТ соединен с входами всех нечетных элементов ИЛИ группы, выход последнего элемента И группы соединен с выходом признака окончания еребора устройства, информационные выходы которого соединены с выходами регистров сдвига.

Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач при автоматизированном конструировании радиоэлектронной и вычислительной аппаратуры. Цель изобретения - упрощение устройства. При устройство содержит группу счетчиков 1,- Ij-, группу элементов И 2,- 2j, группу элементов ЗАПРЕТ 3,- 3i, группу элементов И 4,- группу регистров 5,сдвигар коммутаторы 6-10, элемент НЕ 11, триггер 12, элемент И 13, счетчик 14,- выходы 15-19, тактовый вход 20, выход 21 признака окончания перебора 21, выход 22 признака окончания выдачи одной перестановки, вход 23 установки исходного состояния, группу триггеров 24,- 244.. Устройство реализует перебор всех перестановок и элементов перебора, 1 ил. (Л