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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Цель изобретения - повышение быстродействия. Устройство при содержит регистры li-Is, 2i-25, группы элементов И 3:-Зз, элемент ЗАПРЕТ 4, группы элементов ЗАПРЕТ 5з, 54, группы элементов И 6з, 64, элементы И 1ч-74, 8, 9, группы элементов ИЛИ Юз-104, элементы ИЛИ И, 12, дешифратор 13, счетчики 14-17, вход тактовых импульсов 18, две группы элементов И 19i -195, 20i-205, элемент НЕ 21, группу элементов ИЛИ 22i-225, информационные выход окончания работы 24. Принцип работы устройства заключается в следующем: каждая последуюш,ая перестановка получается из предыдущей путем циклического сдвига базовой комбинации. Устройство позволит получить все перестановки за п /2 тактов. 1 ил. €

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

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

РЕСПУБЛИК 511 4 G 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ф гь „

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 3

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

I (61) 957215 (21) 4098341/24-24 (22) 04.06.86 (46) 23.03.88. Бюл. № 11 (71) Таганрогский радиотехнический институт им. В. Д. Калмыкова (72) В. М. Глушань, И. Г. Ефремов и М. И. Пупков (53) 681.3 (088.8) (56) Авторское свидетельство СССР № 957215, кл. G 06 F 15/20, 1981. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА

ПЕРЕСТА НОВОК (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Цель

„„SU„„1383381 А2 изобретения — повышение быстродействия.

Устройство при n=5 содержит регистры

1i — 15, 21 — 2>, группы элементов И 31 — 3;, элемент ЗАПРЕТ 4, группы элементов

ЗАПРЕТ 53, 54, группы элементов И 63, 64, элементы И 72 — 74, 8, 9, группы элементов

ИЛИ 1Од — 104, элементы ИЛИ 11, 12, дешифратор 13, счетчики 14 — 17, вход тактовых импульсов 18, две группы элементов

И 19 — 195, 20 — 20;, элемент НЕ 21, группу элементов ИЛИ 22 — 22s, информационные выход окончания работы 24. Принцип работы устройства заключается в следующем: каждая последуюшая перестановка получается из предыдущей путем циклического сдвига базовой комбинации. Устройство позволит получить все перестановки за и /2 тактов. 1 ил.

1383381

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

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

На чертеже представлена схема устройства для перебора перестановок (для n=5).

Устройство содержит регистры I i — 1о и 2i — 2о, группы элементов И 3i — Зз, элемент 4 запрета, группы элементов 5З вЂ” 54 запрета, группы элементов И бз — 64, элементы И 7> — 74, 8 и 9, группы элементов ИЛИ

10з — 104, элементы ИЛИ 11 и 12, дешифратор 13, счетчики 14 — 17, вход 18 тактовых импульсов, две группы элементов И 19 — 19о, 20 — 20о, элемент НЕ 21, группу элементов

ИЛИ 22 — 22о, информационные выходы 23, выход 24 окончания работы.

При этом счетчик 14 работает по модулю пять, счетчик 15 — по модулю четыре, счетчик 16 — по модулю три, счетчик 17 — по модулю два.

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

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

Приведем алгоритм формирования перестановок, записанный в форме Ван Хао.

1 . Ввод векторов A=(ai,а, ..., aÄ} и Т=

=10, О, ..., 0)

2 . Lî.=О.

3 . К:=О

4 . В:=А, выдача результата.

5 . Циклический сдвиг вектора В, выдача резул ьтата.

6 . Т .=Т +1.

7 . Если T>(n — 1, то переход к 5 .

8 . К:=К+1, L .— -lг.

9 . Если 1 I, =n — 1, то переход к 18 .

10 . Т>.— Т +1.

11 . Если T )n — La — 1, то переход к 8 .

12 . j:=1.

13 . Циклический сдвиг вектора А с диаметром и — j.

14 . i:=1+1.

15 . Если j(k, то переход к 13 .

16 . Обнулить Т; для всех ii

17 . Переход к 3 .

18 . Конец работы алгоритма.

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

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

Первый (левый) элемент вектора Т образует счетчик по mod (n), второй — mod (и — 1) и т. д. Каждой перестановке соответствует определенное состояние счетчиков. Последовательность состояний счетчиков для случая четырех элементов перестановок выглядит следующим образом:

0000 0100 0200 0010 0110 0210

1000 1100 1200 1010 1110 1210

2000 2100 2200 2010 2110 2210

3000 3100 3200 3010 3110 3210

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

А =1234

1. В=1234 Т=ОООО

20 2. 4123 1000

3. 3412 2000

4. 2341 3000

Счетчик Ti достигает своего модуля, поэтому происходит циклический сдвиг с диаметром n — 1=3.

А=1423

5. В=1423 T=0100 б. 3142 1100

7. 2314 2100

8. 4231 3100

30 Счетчик Т вновь достигает своего модуля, поэтому

A=1342

9. В=1342 T=0200

10. 2134 1200

11. 4213 2200

35 12. 3421 3200

Теперь своих модулей достигают счетчики Т и Т, поэтому в предыдущем значении вектора А необходимо осуществить последовательно два циклических сдвига соот4 ветственно с диаметром 3 и 2

А=1234

1243

13. В=1243 T=0010

14. 3124 1010

15. 4312 2010

45 16. 2431 3010

Счетчик Т достигает своего модуля

A=1324

17. В=1324 Т=0110

18. 4132 1110

19. 2413 2110

50 20. 3241 3110

Счетчик Ti вновь достигает своего модуля

А=1432

21. В=1432 T=0210

22. 2143 1210

23. 3214 2210

55 24. 4321 3210

Счетчики Т, Т и То одновременно достигают своих модулей, поэтому единица, появляющаяся в следующем такте в счет1383381

4 чике Т4, сигнализирует об окончании перебора всех перестановок.

У этого алгоритма имеется важное положительное свойство — каждой перестановке из первой половины последовательности всех перестановок соответствует ей

«зеркальная» из второй половины. Это свойство используется в изобретении, которое выражается в получении двух перестановок — «прямой» и «зеркальной» за один такт работы устройства, используя оба фронта импульсов в тактовых сигналах.

10

Перед началом работы в регистры 11 — 1 заносятся коды переставляемых величин, счетчики 14 — 17 находятся в состоянии «О», 15 элемент 4 запрета закрыт, а элементы И 3,—

3 открыты. Работа устройства начинается с подачей на вход 18 тактовых импульсов.

При поступлении первого тактового импульса происходит перепись кодов из регистров

l i — 1 в соответствующие регистры 2i — 2 через элементы И 3i — 3;, переключение счетчика 14 в состояние «1», по которому закрываются элементы И З вЂ” Зь и открывается элемент 4 запрета, разрешающий поступление тактовых импульсов на тактовые входы 25 регистров 2 — 2 . Появляется сигнал на втором выходе дешифратора 13, открывающий элемент И 7 и элементы И 7э и 7 через элементы ИЛИ 11 и 12 и разрешающий поступление второго тактового импульса на тактовые входы регистров 1» — 1х. При поступлении З0 тактовых импульсов с второго Ilo четвертый коды, записанные в регистрах 21 — 251 сдвигаются при каждом тактовом импульсе в соседние справа регистры, причем из регистра 2 сдвиг происходит в регистр 2i, состояние счетчика 14 изменяется от «2» до «4». - З5

Кроме этого, одновременно при поступлении второго тактового импульса коды, записанные в регистрах 1 — 11, сдвигаются в соседние справа регистры через открытые элементы 5з — 54 запрета и элементы ИЛИ 10з и 104, 40 причем из регистра 1 сдвиг происходит в регистр 12. При поступлении пятого тактового импульса происходит сдвиг кодов в регистрах 2i — 2 в соседние справа регистры, счетчик 14 переключается в «0», соответственно счетчик 15 — в состояние «1», т. е. устанав- 45 ливается исходное состояние счетчика 14, и работа устройства повторяется до тех пор, пока счетчик 14 не будет в состоянии «1», а счетчик 15 в состоянии «3». При поступлении 17-го тактового импульса происходит сдвиг кодов в регистрах 12 — 1д, 2i — 2 в со- 50 седние справа регистры, счетчик 14 переключается в состояние «2», на выходе элемента

И 8 появляется сигнал, закрывающий элемент 5з запрета и открывающий элемент

И 63 и элементы И 7з и 74 через элементы

ИЛИ 11 и 12. При поступлении 18-го тактового импульса происходит сдвиг кодов в регистрах 21 — 2; и lз — 1;, через открытые элементы И 6з, запрета 5 и элементы ИЛИ

10з †1 в соседние справа регистры, счетчик 14 переключается в состояние «3», открывается элемент запрета 5, а элемент 6З закрывается. При поступлении 19-го тактового импульса происходит сдвиг кодов в регистрах 2 — 2, а счетчик 14 переключается в состояние «4». При поступлении 20-го тактового импульса коды в регистрах 2 — 2; сдвигаются, счетчики 14 и 15 переключаются в «О», а счетчик 16 — в «1», т. е. устанавливается исходное состояние счетчиков 14 и 16 и работа устройства повторяется сначал а аналогично описанной. При поступлении 58ro тактового импульса устройство работает так же, как при поступлении 18-го тактового импульса, кроме этого, появляется сигнал на выходе элемента Hg, так как счетчики 14 и 15 в состоянии «3», а счетчик 16 в состоянии «2», закрывающий элемент 54 запрета и открывающий элемент И 64 и элемент И 7, через элемент ИЛИ 12. При поступлении 59го тактового импульса происходит сдвиг кодов в регистрах 2i — 2 в соседние справа регистры и .в регистрах 1 — 1 через открытый элемент И 64 и элемент ИЛИ 10<. При поступлении 60-го тактового импульса происходит сдвиг кодов в регистрах 2i — 2;, счетчики 14 — 16 переключаются в «О» и единичный сигнал появляется на выходе 24 окончания работы. При каждом тактовом импульсе по переднему фронту происходит поступление сигналов с выходов регистров

2 — 2> через элементы И 19 — 19;, ИЛИ 22,—

22з на выходы 23 устройства в прямой последовательности, по заднему фронту происходит поступление сигналов с выходов регистров 2 — 2 через элементы И 20) — 20, элементы ИЛИ 22 — 22; на выход 23 устройства в «зеркальной» последовательности.

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

Устройство для перебора перестановок по авт. св. № 957215, отличающееся тем, что, с целью повышения быстродействия, оно дополнительносодержитэлемент НЕ, (2n Ä2} и (2n — 1)-ю группы элементов И, (n — 2)-ю группу элементов ИЛИ, причем тактовый вход устройства соединен с входом элемента

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