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