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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (19) (11) 3 А1

g1) 4 G 06 F 15/20

„, )3

ОПИСАНИЕ ИЗОБр(ц цщ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Т " т .

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4182809/24-24 (22) 15.01.87 (46) 23.08 ° 88. Бюп. Ф 3 1 (71) Таганрогский радиотехнический институт им. В.Д. Калмыкова (72) В.М. Глушань и А.Л. Хамутов (53) 68 1.323(088.8) (56) Авторское свидетельство СССР

У 995093, кл. G 06 F 15/20, 1981.

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

9 1190388, кл. G 06 F 15/20, 1984 ..(54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК (57) Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач при автоматизированном конструировании радиоэлектронной и вычислительной аппаратуры. Цель изобретения — упрощение устройства.

При п=5 устройство содержит группу счетчиков 1 — 1, группу элементов

И 2, — 2З, группу элементов ЗАПРЕТ

3<- 3, группу элементов И 4, — 4, группу регистров 5 - 5 сдвига, ком" мутаторы 6-10, элемент HF. 11, триггер 12, элемент И 13, счетчик 14," выходы 15-19, тактовый вход 20, выход 21 признака окончания перебора

21, выход 22 признака окончания выдачи одной перестановки, вход 23 ус" тановки исходного состояния, группу триггеров 24 - 24 . Устройство реа" лизует перебор всех перестановок и элементов перебора. 1 ил.

14 l8733

7. 3 1 4 2

8.1342

9 ° 1432

10. 4132

18.4231

19.2413

20. 4213

21.4123

22. 1 4 2 3

23. 1 243

1011.4312

2.2134

3. 23 14

4.3214

13. 4321

14. 3 42

15.3241

1б. 234 1

5. 3 1 24

6.1324

17. 2 4 3 1

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

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

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

Устройство содержит группу счетчиков 14 в 1, группу элементов И 15

2, — 2, группу элементов запрет

3, — 3, группу элементов ИЛИ 4,—

4, группу регистров 5, — 5 сдвига, коммутаторы б-10 элемент НЕ 11, триггер 12, элемент И 13, счетчик

14, выходы 15-19 устройства, тактовый вход 20, выхоц 21 признака окончания перебора, выход 22 признака окончания выдачи одной перестановки, вход 23 установки исходного состояния, группу 25

24 - 244 триггеров, модуль счетчика

1, равен двум, у каждого последующего счетчика — на единицу больше.

Принцип работы устройства состоит 30 в том, что при помощи управляющих

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

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

1. 1 2 3 4 12. 3 4 1 2 .) 24. 2143

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

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

54- 5 . Таким образом, первому тактовому импульсу соответствует код 10000 на выходах 15.

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

Второй тактовый импульс проходит через открытый элемент И 13 и поступает на синхровходы регистров 5 сдвига, а также через счетчик 14 — на счетные входы счетчиков 1,, ..., 1, в результате чего счетчик 1, пере1418733 ходит в единичное состояние, сигнал с выхода которого, пройдя через открытые элементы 3, и 42, появляется на входе триггера 242 . Так как триггер 24, находится в единичном состоянии, коммутаторы 7 пересоединяют выход регистра 52 сдвига на вход регистра 5, сдвига, а выход 5 .на вход

52 и по приходу тактового импульса единица из последнего разряда 5,-переписывается в первый разряд 5, а ноль иэ последнего разряда регистра

5 " в первый разряд регистра 5< .

При этом на выходах 15 появляется код 01000. Так как после пяти первых тактовых импульсов состояния триггеров 24 — 24 не изменяется, то регистры 5, и 5 сдвига полностью

Обменяются содержимьп, а содержимое 20 регистров 5 — 5> будет таким же как и в исходном состоянии, причем после прихода каждого тактового импульса на выходах 15 появляются коды расположения очередной цифры первой пере-25 становки. По приходу пятого тактового импульса одновременно с перезаписью состояний регистров 5 сдвига появляется сигнал на выходе счетчика

14, а в результате чего триггер 24 переходит в единичное состояние, а триггер 24, обнуляется.

Под действием сигнала на выходе триггера 24 коммутаторы 7 и 8 соединяют выход регистра 5 сдвига со вхо2

35 дом регистра 5 сдвига и выход регистра 5> с входом регистра 5, выходы остальных регистров будут соединены со своими же входами.

После прихода очередных 6-10 так40 товых импульсов поменяются содержимым регистры 5z и 5> а содержимое остальных регистров станет таким же как после прихода 5-го тактового импульса. Причем после прихода каждого .из этих импульсов на выходах 15 будут 45 появляться коды расположения очередной цифры второй перестановки.

После прихода каждого (in)-ro импульса состояния триггеров 24 изменя- 5 ются таким образом, что генерация перестановок происходит по вьппеупомянутому алгоритму. Достигается это тем, что после прихода каждого импульса с первого выхода счетчика 14 на инверсном и прямом выходах счетчика 1, импульсы появляются по очереди, на выходах И 2 после каждого шестого, на выходе элемента И 2 после каждого 24-го, на выходе элемента И 2 после каждого 120-го импульса. Элементы И 3<, И 32 пропускают импульсы только со старших разрядов регистров 1, а элементы ИЛИ 4, 4 2 одновременно пропускают импульсы на входы триггеров 24 младших разрядов, совпадающих по четности со старшими.

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

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

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

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

n-I триггеров, о т л и ч а ю щ ее с я тем, что, с целью упрощения и повьппения быстрод йствия, оно содержит группу из п-1 элементов И, и и-разрядных регистров сдвига, счетчик по модулю и, триггер, элемент И, элемент НЕ, и коммутаторов, причем выход i-го коммутатора, (i=1 ...n) соединен с информационным входом

i-ro регистра сдвига, выход j-го регистра сдвига (j=1, °, ., n-2) соединен с первым информационным входом

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

1418733

t и-31 †- ) соединен с соответствующими г) входами всех четных элементов ИЛИ, начиная с второго и до (2р)-го, а выход каждого (2р)-ro элемента

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

Составитель M. Горяинов

Техред А. Кравчук Корректор И. Эрдеии

Редактор Г. Волкова

Тираж 704

Заказ 4155/47

Подписное

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

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

gpovзводственно-полиграфическое предприятие, г. ужгород, ул. Проектная, 4 инверсным и вторым прямым управляющим входами (j+1)-ro коммутатора, выход (n-1)-го триггера группы соединен с первым инверсным и первым пря5 мым управляющими входами (п-1) -го и и-ro коммутаторов, единичный вход

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

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