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

(Л

со СХ)

со со

00

к

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

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

На чертеже представлена схема устрой- ства для перебора перестановок (для ). Устройство содержит регистры Ь - Is и 2|-25, группы элементов И 3i-Зз, элемент 4 запрета, группы элементов 5з-54 запрета, группы элементов И 6з-64, элементы И 72-74, 8 и 9, группы элементов ИЛИ Юз-104, элементы ИЛИ 11 и 12, дешифратор 13, счетчики 14-17, вход 18 тактовых импульсов, две группы элементов И 19i -195, 20|-205, элемент НЕ 21, группу элементов ИЛИ 22i-225, информационные выходы 23, выход 24 окончания работы.

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

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

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

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

1°. Ввод векторов , 0:2, .--, Ол) и 7 {0, О, ..., 0} 2°. . 3°.

4°. , выдача результата.

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

6°. Г,.

7°. Если , то переход к 5°. 8°. , Lk-k.

9°. Если , то переход к 18° 10°. Tk: Tk+.

11°. Если Tk n-Lk-, то переход к 8° 12°. .

13°. Циклический сдвиг вектора А с диаметром п-/.

14°. 1.

15°. Если , то переход к 13°. 16°. Обнулить Ti для всех , 1, 2, ..., -1).

17°. Переход к 3°. 18°. Конец работы алгоритма. В приведенном алгоритме вектором Л задаются элементы, участвующие в перестановках, и сама начальная перестановка. Элементы вектора Т образуют счетчики с

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

0000 0100 0200 0010 ОНО 0210

1000 1100 1200 1010 1110 1210

2000 2100 2200 2010 2110 2210

3000 3100 3200 ЗОЮ 3110 3210

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

1.

2.4123 1000

3.3412 2000

4.2341 3000

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

5.

6.3142 1100

7.2314 2100

8.4231 3100

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

9.

10.2134 1200

11.4213 2200

12.3421 3200

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

13.В 1243

14.3124 1010

15.4312 2010

16.2431 ЗОЮ

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

17.

18.4132 1110

19.2413 2110

20.3241 3110

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

21.S 1432

22.2143 1210

23.3214 2210

24.4321 3210

Счетчики 7ь 72 и 7з одновременно достигают своих модулей, поэтому единица, появляющаяся в следующем такте в счетчике T, сигнализирует об окончании перебора всех перестановок.

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

Перед началом работы в регистры Ь - Ь заносятся коды переставляемых величин, счетчики 14-17 находятся в состоянии «О, элемент 4 запрета закрыт, а элементы И 3i - ЗБ открыты. Работа устройства начинается с подачей на вход 18 тактовых импульсов. При поступлении первого тактового импульса происходит перепись кодов из регистров li-is в соответствующие регистры через элементы И 3i-Зз, переключение счетчика 14 в состояние «1, по которому закрываются элементы И 3i-Зз и открывается элемент 4 запрета, разрешающий поступление тактовых импульсов на тактовые входы регистров 2i-25. Появляется сигнал на втором выходе дешифратора 13, открывающий элемент И 72 к элементы И Т и 7 через элементы ИЛИ 11 и 12 и разрещающий поступление второго тактового импульса на тактовые входы регистров Ь - 1г. При поступлении тактовых импульсов с второго по четвертый коды, записанные в регистрах 2|-25, сдвигаются при каждом тактовом импульсе в соседние справа регистры, причем из регистра 2$ сдвиг происходит в регистр 2i, состояние счетчика 14 изменяется от «2 до «4. Кроме этого, одновременно при поступлении второго тактового импульса коды, записанные в регистрах Ь-Ь, сдвигаются в соседние справа регистры через открытые элементы 5з-5 запрета и элементы ИЛИ Юз и 104, причем из регистра Is сдвиг происходит в регистр Ь. При поступлении пятого тактового импульса происходит сдвиг кодов в регистрах 2|-25 в соседние справа регистры, счетчик 14 переключается в «О, соответственно счетчик 15 - в состояние «1, т. е. устанавливается исходное состояние счетчика 14, и работа устройства повторяется до тех пор, пока счетчик 14 не будет в состоянии «1, а счетчик 15 в состоянии «3. При поступлении 17-го тактового импульса происходит сдвиг кодов в регистрах Ь-Is, 2i-2s в соседние справа регистры, счетчик 14 переключается в состояние «2, на выходе элемента И 8 появляется сигнал, закрывающий элемент 5з запрета и открывающий элемент И бз и элементы И 7з и 74 через элементы ИЛИ 11 и 12. При поступлении 18-го тактового импульса происходит сдвиг кодов в регистрах 2i-2s и 1з-Is через открытые элементы И 6з, запрета 5 и элементы ИЛИ Юз-104 в соседние справа регистры, счетчик 14 переключается в состояние «3, открывается элемент запрета 5з, а элемент 6з закрывается. При поступлении 19-го тактового импульса происходит сдвиг кодов в регистрах 2i-2s, а счетчик 14 переключается в состояние «4. При поступлении 20-го так0 тового импульса коды в регистрах 2i-2s сдвигаются, счетчики 14 и 15 переключаются в «О, а счетчик 16 - в «1, т. е. устанавливается исходное состояние счетчиков 14 и 16 и работа устройства повторяется сначала аналогично описанной. При поступлении 585 го тактового импульса устройство работает так же, как при поступлении 18-го тактового импульса, кроме этого, появляется сигнал на выходе элемента Ид, так как счетчики 14 и 15 в состоянии «3, а счетчик 16 в состоянии «2, закрывающий элемент 54 запрета и открывающий элемент И 64 и элемент И 74 через элемент ИЛИ 12. При поступлении 59- го тактового импуЛьса происходит сдвиг кодов в регистрах в соседние справа регистры и-В регистрах Ц-Is через откры5 тый элемент И 64 и элемент ИЛИ 104. При поступлении 60-го тактового импульса происходит сдвиг кодов в регистрах 2i-2s, счетчики 14-16 переключаются в «О и единичный сигнал появляется на выходе 24 окончания работы. При каждом тактовом им0 пульсе по переднему фронту происходит поступление сигналов с выходов регистров 2|-2s через элементы И 19i -195, ИЛИ 22i - 22s на выходы 23 устройства в прямой последовательности, по заднему фронту происходит поступление сигналов с выходов ре5 гистров 2i-2s через элементы И 20i-20s, элементы ИЛИ 22i-225 на выход 23 устройства в «зеркальной последовательности.

0

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

40

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

45 группу элементов ИЛИ, причем тактовый вход устройства соединен с входом элемента НЕ и первыми входами элементов И {2п-2)-и группы, вторые входы которых соединены с выходами регистров с (п-+-1)-го по 2п-й соответственно, выход элемента НЕ

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

55

Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей. Цель изобретения - повышение быстродействия. Устройство при содержит регистры 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 ил. €