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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) (1 51) 4 ь-ь 06 Р 15 ффра т ОПИСАНИЕ ИЗОБРЕТЕНИК АВТОРСКОМУ СВИДЕТЕЛЬСТВУчески СССР981.ПЕРЕБОРА к авто может мбинат оля дл ностей,тике быть рных гене- Цель ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(54) УСТРОЙСТВО ДЛЯПЕРЕСТА НОВОК(57) Изобретение относитсяи вычислительной технике ииспользовано для решения козадач, а также в системах контррации кодовых последователь изобретения - повышение быстродействия. Устройство при а=5 содержит регистры 1 ь - 15, 2 ь - 25, группы элементов И 3, - 3;, элемент ЗАПРЕТ 4, группы элементов ЗАПРЕТ 5 з, 54, группы элементов И 6 з, 64, элементы И 72 - 74, 8, 9, группы элементов ИЛИ 1 Оз - 104, элементы ИЛИ 11, 12, дешифратор 13, счетчики 14 - 17, вход тактовых импульсов 18, две группы элементов И 191 - 195, 20 ь - 20;, элемент НЕ 21, группу элементов ИЛИ 221 - 225, информационные выход окончания работы 24. Принцип работы устройства заключается в следующем: каждая последуюшая перестановка получается из предыдущей путем циклического сдвига базовой комбинации. Устройство позволит получить все перестановки за и /2 тактов. 1 ил.Изобретение относится к автоматикеи вычислительной технике, может быть использовано для решения комбинаторныхзадач, а также в системах контроля для генерации кодовых последовательностей и является усовершенствованием изобретенияпо авт. св. Мо 957215,Целью изобретения является повышениебыстродействия устройства.На чертеже представлена схема устройства для перебора перестановок (для а=5).Устройство содержит регистры 1 - 1 ои 2 - 2 о, группы элементов И 31 - Зз, элемент 4 запрета, группы элементов 5 з - 54запрета, группы элементов И бз - 64, элементы И 72 - 74, 8 и 9, группы элементов ИЛИ10 з - 104, элементы ИЛИ 11 и 12, дешифратор 13, счетчики 14 - 17, вход 18 тактовыхимпульсов, две группы элементов И 191 - 19 о,20 - 20 о, элемент НЕ 21, группу элементовИЛИ 221 - 22 о, информационные выходы 23,выход 24 окончания работы.При этом счетчик 14 работает по модулюпять, счетчик 15 - по модулю четыре, счетчик 16 - по модулю три, счетчик 17 - помодулю два.Количество элементов в группах и разрядность регистров соответствуют количеству двоичных разрядов, необходимых дляпредставления в двоичном или унитарномкоде максимального из переставляемыхчисел.Принцип работы устройства для перебора перестановок состоит в следующем. Каждая последующая перестановка получаетсяиз предыдущей путем циклического сдвигабазовой комбинации.Приведем алгоритм формирования перестановок, записанный в форме Ван Хао,1. Ввод векторов А=(а,а 2, , а) и Т==(О, О, , 0)2. У,о.=О.3. К:=04. В:=А, выдача результата.5. Циклический сдвиг вектора В, выдачарезультата.6. Т.=Т +1,7. Если Т.,п - 1, то переход к 5,8. К:=К+1, Е.=й.9. Если 1=п - 1, то переход к 18,10. Т:=Т+1,11. Если Т)п - Ь - 1, то переход к 8.12. 1:=1.13. Циклический сдвиг вектора А с диаметром и - .14. :=1+1.15. Если Сй, то переход к 13.16. Обнулить Т; для всех Е 1 (О, 1, 2, ,К - 1),17. Переход к 3.18. Конец работы алгоритма.В приведенном алгоритме вектором Азадаются элементы, участвующие в перестановках, и сама начальная перестановка.Элементы вектора Т образуют счетчики с соответствующими модулями счета и обеспечивают организацию рекурсивных процедур.Первый (левый) элемент вектора Т образует счетчик по той (а), второй - тод (и - 1) 5 и т. д. Каждой перестановке соответствуетопределенное состояние счетчиков. Последовательность состояний счетчиков для случая четырех элементов перестановок выглядит следующим образом:0000 0100 0200 0010 0110 0210 1000 1100 1200 1010 1110 1210 2000 2100 2200 2010 2110 2210 3000 3100 3200 3010 3110 3210 Последовательность формирования при веденным алгоритмом всех перестановокс учетом выполнения рекурсивных процедур, организуемых счетчиками, в сокращенном виде имеет видА =12341. В=1234 Т=ОООО2. 4123 10003. 3412 20004. 2341 3000Счетчик Т достигает своего модуля, поэтому происходит циклический сдвиг с диаметром а - 1=3.А=14235. В=1423 Т=0100б, 3142 11007. 2314 21008. 4231 310030 Счетчик Т 1 вновь достигает своего модуля,поэтомуА=13429. В=1342 Т=020010, 2134 120011. 4213 220035 12, 3421 3200Теперь своих модулей достигают счетчики Т 1 и Т 2, поэтому в предыдущем значении вектора А необходимо осуществить последовательно два циклических сдвига соот ветственно с диаметром 3 и 2А=1234124313. В=1243 Т=001014. 3124 101015. 4312 201045 16. 2431 3010Счетчик Т 1 достигает своего модуляА=132417, В=1324 Т=011018. 4132 111019. 2413 211050 20. 3241 3110Счетчик Т вновь достигает своего модуляА=143221, В=1432 Т=021022. 2143 121023. 3214 221024. 4321 3210Счетчики Т 1, Т 2 и То одновременно достигают своих модулей, поэтому единица, появляющаяся в следующем такте в счетчике Т 4, сигнализирует об окончании перебора всех перестановок.У этого алгоритма имеется важное положительное свойство - каждой перестановке из первой половины последовательности всех перестановок соответствует ей зеркальная из второй половины. Это свойство используется в изобретении, которое выражается в получении двух перестановок - прямой и зеркальной за один такт работы устройства, используя оба фронта импульсов в тактовых сигналах. 5 О Перед началом работы в регистры 11 - 1 заносятся коды переставляемых величин, счетчики 14 - 17 находятся в состоянии 0, 15 элемент 4 запрета закрыт, а элементы И 3, - 3 открыты. Работа устройства начинается с подачей на вход 18 тактовых импульсов. При поступлении первого тактового импульса происходит перепись кодов из регистров 11 - 1 ь в соответствующие регистры 2 - 2, через элементы И 31 - 3;, переключение счетчика 14 в состояние 1, по которому закрываются элементы И З - Зь и открывается элемент 4 запрета, разрешающий поступление тактовых импульсов на тактовые входы 25 регистров 2, - 2. Появляется сигнал на втором выходе дешифратора 13, открывающий элемент И 7 и элементы И 7 э и 7 через элементы ИЛИ 11 и 12 и разрешающий поступление второго тактового импульса на тактовыевходы регистров- 1 х. При поступлении З 0 тактовых импульсов с второго по четвертый коды, записанные в регистрах 21 - 2, сдвигаются при каждом тактовом импульсе в соседние справа регистры, причем из регистра 2 сдвиг происходит в регистр 21, состояние счетчика 14 изменяется от 2 до 4. 35 Кроме этого, одновременно при поступлении второго тактового импульса коды, записанные в регистрах 12 - 11, сдвигаются в соседние справа регистры через открытые элементы 5 з - 54 запрета и элементы ИЛИ 10 з и 104, 40 причем из регистра 1 ь сдвиг происходит в регистр 12. При поступлении пятого тактового импульса происходит сдвиг кодов в регистрах 2, - 2 в соседние справа регистры, счетчик 14 переключается в О, соответственно счетчик 15 - в состояние 1, т. е. устанав ливается исходное состояние счетчика 14, и работа устройства повторяется до тех пор, пока счетчик 14 не будет в состоянии 1, а счетчик 15 в состоянии 3, При поступлении 17-го тактового импульса происходит сдвиг кодов в регистрах 12 - 11, 21 - 2 ь в со седние справа регистры, счетчик 14 переключается в состояние 2, на выходе элемента И 8 появляется сигнал, закрывающий элемент 5 з запрета и открывающий элемент И бз и элементы И 7 з и 74 через элементы ИЛИ 11 и 12. При поступлении 18-го тактового импульса происходит сдвиг кодов в регистрах 21 - 2; и 1 з - 1;, через открытые элементы И бз, запрета 5 и элементы ИЛИ 10 з - 104 в соседние справа регистры, счетчик 14 переключается в состояние 3, открывается элемент запрета 5, а элемент 6, закрывается. При поступлении 19-го тактового импульса происходит сдвиг кодов в регистрах 2 - 2 ь, а счетчик 14 переключается в состояние 4. При поступлении 20-го тактового импульса коды в регистрах 2, - 2; сдвигаются, счетчики 4 и 15 переключаются в 0, а счетчик 16 - в 1, т. е, устанавливается исходное состояние счетчиков 14 и 16 и работа устройства повторяется сначала аналогично описанной. При поступлении 58- го тактового импульса устройство работает так же, как при поступлении 18-го тактового импульса, кроме этого, появляется сигнал на выходе элемента И 9, так как счетчики 14 и 15 в состоянии 3, а счетчик 6 в состоянии 2, закрывающий элемент 54 запрета и открывающий элемент И 64 и элемент И 7, через элемент ИЛИ 12. При поступлении 59- го тактового импуЛьса происходит сдвиг кодов в регистрах 2 - 2 в соседние справа регистры и .в регистрах 14 - 1 через открытый элемент И 64 и элемент ИЛИ 104. При поступлении 60-го тактового импульса происходит сдвиг кодов в регистрах 21 - 2;, счетчики 14 - 16 переключаются в О и единичный сигнал появляется на выходе 24 окончания работы. При каждом тактовом импульсе по переднему фронту происходит поступление сигналов с выходов регистров 2- 2 через элементы И 191 - 19 ь, ИЛ И 22, - 22 на выходы 23 устройства в прямой последовательности, по заднему фронту происходит поступление сигналов с выходов регистров 2, - 2 через элементы И 20, - 20, элементы ИЛИ 22, - 22; на выход 23 устройства в зеркальной последовательности.Формула изобретенияУстройство для перебора перестановок по авт. св.957215, отличающееся тем, что, с целью повышения быстродействия, оно дополнительно содержит элемент НЕ, (2 п - 2) и (2 и - 1) -ю группы элементов И, (и - 2) -ю группу элементов ИЛИ, причем тактовый вход устройства соединен с входом элемента НЕ и первыми входами элементов И (2 п - 2) -й группы, вторые входы которых соединены с выходами регистров с (и+1) -го по 2 п-й соответственно, выход элемента НЕ соединен с первыми входами элементов И (2 п - 1) -й группы, вторые входы которых соединены с выходами регистров с 2 п-го по (и+1) -й соответственно, выходы элементов И (2 п - 2) и (2 п - 1)-й групп соединены соответственно с первыми и вторыми входами элементов ИЛИ (п - 2) -й группы, выходы которых являются выходами устройства.