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

вход 17 установки исходного состояния, тактовый вход 18, информационные выходы 19, группу элементов ИЛИ 20-23, элемент ИЛИ 24, группу элементов ИЛИ 25-27, триггеры 28-30, группу элементов запрета 31-32, элементы запрета 33,34, элемент И 35,1397933Т-триггер 36, элемент НЕ 37, регистры 38-42, группу элементов И 43-66,группу элементов ИЛИ 67-78, Устройство позволяет генерировать п перестановок из п переставляемых элеменитов затактов. 4 ил.2Изобретение относится к вычислительной технике и может быть использовано для решения задач автоматизированного конструирования радиоэлектронной и вычислительной аппаратуры, а 5 также в системах контроля для гене.ации кодовых последовательностей.Целью изобретения является повышение быстродействия устройства.На фиг. 1 приведена структурная схема устройства для ипереставляемых элементов; на фиг. 2 - струкгурная схема взаимосвязи всех репстрон, на фиг, 3 и 4 - схемы разрядов регистров.15Устройство содержит счетчики 1-4, бичем счетчик 1 - по пюд 2, счетчик 2 - го шоЛ 3, счетчик 3 - по шод 2, счетчик 4 - по пюд 3, группу элементов И 5-8, элемент И 9, группу зле 20 ментов И 10-12, элементы 13-15 задержки, элемент ИЛИ 16, вход 17 установки исходного состояния, тактовый вход 18, информационные выходы 19, группу элементов ИЛИ 20-23, элемент ИЛИ 24, группу элементов ИЛИ 25-27, триггеры 28-30, группу элементов 31 и 32 запрета, элементы 33 и 34 запрета, элемент И 35, Т-триггер 36, элемент НЕ 37, регистры 38-42, группы 43=48, 49-54, 55-60, 61-66 элементов И, груп пу элементов ИЛИ 67-78, синхронизирующие входы 79-81 разрядов регистров, входы 82-84 разрядов регистров, выход 85 разряда регистра, элементы 35 И 86 и 87,элементы ИЛИ 88 и 89, 0- триггер 90 и элемент И 91Принцип работы устройства состоит в следующем.Каждая очередная перестановка по лучается из предыдущей путем обмена элементами (кодами) между соответствующими позициями по строго опре деленной закономерности. Алгоритмперестановок предусматривает отображение первых ч тырех элементов послекаждого такта обмена информациеймежду ячейками независимо от общего количества элементов, участвующихв перестановках, Зеркальное отображение подразумевает перестановку элемента, занимающего первую позицию, вчетвертую позицию, а элемента, занимающего четвертую позицию, - в первую, и, соответственно, элемента, занимающего вторую позицию, - в третью,а элемента, занимающего третью позицию, - во вторую,Рассмотрим алгоритм работы устройства на примере перестановки четырех элементов. Нумеруют позиции, занимаемые элементами, слева направои в позиции 1,2,3,4 записывают соответственно элементы 1 2 3 4, Получают 12 основных и 12 зеркальных перестановок. Стрелки показывают в каких позициях происходит смена элементов, После каждой перестановки формируется зеркальное отображение первых четырех элементов, Из приведенной послелова 1234 1. 1234 2.2134 3. 2314 4,3214 5. 3124 6.1324 ф - -Ф Ф -7. 3142 8. 134 9, 1243 10. 2 1 4 3 11. 2 3 4 1 12, 3 2 4 1123456 60. 123456 61. 213456 123456 60. 432156 61, 431265 з 13979тельности видно, что обмен элементов,стоящих в первой и во второй позициях, происходит через одну перестановку, а элементов, стоящих в третьейч5и четвертои позициях, через шесть перестановок. В перных шести перестановках обмен элементов, стоящих вовторой и третьей позициях, происходитчерез одну перестановку, а в следующих шести перестановках обмен элементов, стоящих во второй и третьейпозициях, не происходит, а происходитчерез одну перестановку обмен элементов, стоящих во второй и четвертой позициях. Смена элементов, стоящих в двух старщих позициях, влечетза собой смену элементов между всемипарами всех младших позиций, Это хорошо видно из приведенного примера. 20Когда через шесть перестановок происходит обмен элементов, находящихся нтретьей и четвертой позициях, то одновременно должен происходить обменэлементов, стоящих в первой и второй 25позициях. Когда старшими при обменеявляются первая и вторая, вторая итретья, вторая и четвертая позициито они не вызывают обмена парами младших позиций, поскольку таковых прос- ЗОто нет.Приведенное правило легко применяется на большее число элементов с не. пременным условием, что после каждойперестановки элементов в ячейках ре 35гистров зеркальному отображению подвергаются только первые четыре младших разряда, а старшие разряды остаются нетронутыми. Так, обмен элементов, находящихся в четвертой и пя Отой позициях, происходит через 12 перестановок, в пятой и шестой позицияхчерез 60 перестановок. В конечномсчете такая смена элементов, стоящих.в И и Мпозициях происходит через 45)должна происходить смена элементов в 50первой и второй, третьей и четвертой, пятой и шестой позициях, т.е. Перестановки 60 .и 6 1 являютсязеркальньии для перестановок 60 и 33461 соответственно. Аналогично лля получения 721-й перестановки должен происходить обмен элементов, стоящих во второй и третьей, четвертой и пятой, шестой и седьмой позициях.1234567 1234567 720. 1234567 720 . 4321567 721. 1325476 721 . 5231476После того, как произойдет обмен элементов, стоящих в старших позициях, процесс обмена начинает повторяться.Реализация приведенной закономерностй в устройстве осуществляется тем, что каждая очередная перестановка получается путем обмена содержимым разрядов соседних регистров либо путем обмена содержимым второго и четнертого регистров, а также получением нонои перестановки путем зеркального отображения информации, записанной в первых четырех регистрах по описанной закономерности.Устройство работает следующим образом.По сигналу, поступающему на вход 17 установки исходного состояния, сбрасываются триггеры 28-30, счетчи" ки 1-4 и Т-триггер 36, в регистры 38-42 записываются двоичные коды чисел 2,1,3,4,5 соответственно. При отсутствии тактовых импульсов на входе 18 устройства на выходе элемента НЕ 37 присутствует логическая "1", которая разрешает прохождение информации, поступающей от регистров 38- 4 1, через нечетные элементы И 43-66, элементы ИЛИ 67-78 на информационные выходы 19 устройства, на которых фиксируются коды чисел 4,3, 1,2,5 соответственно. Верхний уровень тактового импульса, поступающего на вход устройства 18, вызывает появление на выходе первого разряда счетчика 1 единичного потенциала, который, пройдя через открытый элемент И 5, одновременно на первый вход которого подается задержанный первый импульс, через элемент ИЛИ 20 попадает на синхронизирующие входы 79 и 82 разрядов регистра 38 и синхронизирующие входы 79 разрядов регистра 39, что приводит к обмену информацией между регистрами 38 и 39. Задержанный первый импульс вызывает появление логического "0" на выходе элемента НЕ 37, который запрещает прохождение информации, поступающей с выходов раз.рядов регистров 38-41 через нечетные элементы И 43-66, а логическая "1" на выходе элемента 15 задержки разрешает прохождение информации, поступающей от регистров, через четные элементы И 43-66 и соответствующие элементы И 43-66 и ИЛИ 67-78. На выходах 19 устройства фиксируются коды чисел 1,2,3,4,5 соответственно, Нижний уровень тактового импульса, пройдя через элемент 15 задержки, вызывает появление "1" на выходе элемента НЕ 37, которая разрешает прохождение информации через нечетные элементы И 43-66 и соответствующие элементы ИЛИ 67-78, "0" с выхода элемен та 15 задержки запрещает прохождение информации через четнье элементы И 43-66.На выходах 19 устройства фик сируются коды чисел 4,3,2,1,5 соответственно.Верхний уровень тактового импульса вызывает появление на выходе счетчика 1 единичного потенциала, 25 который поступает на первые входы элемента 34 запрета и элемента И 35, на вторые входы которых поступает "0" со сброшенного триггера 36, который запрещает прохождение сигнала через элемент И 35 и разрешает через элемент 34 запрета, далее сигнал проходит через открытый элемент 31 запрета, на вторые входы которого поступают "0" со сброшенных счет 35 чиков 2 и 3, проходит открытый элемент И 6, элемент ИЛИ 21 и поступает на синхронизирующие входы разрядов регистров 39 и 40, что приводит к обмену информацией между ними, 0 4 О на выходе элемента НЕ 37 запрещает прохождение информации через нечетные элементы И 43-66, а "1" на выходе элемента 15 задержки разрешает прохождение информации через четные элементы И 43-66 и соответствующие элементы ИЛИ 67-78. На выходах 19 устройства фиксируются коды чисел 1,3,2,4,5 соответственно.Нижний уровень второго тактового импульса, пройдя через элемент 15 задержки, вызывает появление "1" на выходе элемента НЕ 37, в результате чего на выходах 19 устройства появляются коды чисел 4,2,3, 1,5 соответственно.Верхний уровень шестого тактового импульса вызывает появление на выходах счетчиков 1 и 2 единичного потенциала. Сигнал с выхода счетчика 2 является старшим, он запирает элементы 31 и 33 запрета, проходит через элементы 32 запрета, открытый элемент И 8, элементы ИЛИ 22 и 20 и попадает на синхронизирующие входы разрядов регистров 38-4 1, что вызывает обмен информацией между ними, Единичный потенциал на выходе счетчика 2 одновременно вызывает опрокидывание Т-триггера 36, " 1" на выходе которого запрещает в дальнейшем прохождение сигнала через элемент 34 запрета и разрешает через элемент И 35.Нижний уровень шестого тактового импульса вызывает появление "1" на выходе элемента НЕ 37, что приводит к коммутации выходов регистров 38- 41 и получению очередной перестановки. Верхний уровень восьмого тактового импульса вызывает появление сигнала на выходе счетчика 1, который, пройдя через элемент И 35, элемент 33 запрета, элементы И 9, ИЛИ 24, вызывает обмен информацией между регистрами 39 и 4 1. Двенадцатый тактовый импульс вызывает обмен информацией между регистрами 39-42. После прихода 60 тактового импульса на выходе счетчика 4 появляется единичный потенциал, что свидетельствует об окончании работы устройства.Если возникает необходимость увеличить число элементов в перестановках, то необходимо добавить соответствующее число разрядов, Каждый разряд, начиная с четвертого, содержит счетчик по модулю (Р), где Р - номер разряда, элемент И в первой и второй группах, элемент ИЛИ в первой и второй группах, элемент запрета, триггер, регистр.Формула изобретенияУстройство для перебора перестановок, содержащее псчетчиков (и - число переставляемых элементов), группу триггеров, две группы элементов И, три группы элементов ИЛИ, группу элементов ЗАПРЕТ, два элемента задержки, первый элемент ИЛИ и и регистров, причем выход первого элемента задержки соединен с первыми входами элементов И первой и второй групп и входом второго элемента задержки, выход которого соединен с первым входом пер 1397933вого элемента ИЛИ, выход которого соединен с нулевыми входами триггеров группы, выходы которых соединены с вторыми входами элементов И первой5 группы, выходы которых соединены с первыми входами элементов ИЛИ первой группы, выход -го элемента ИЛИ группы (1 = 1,п) соединен с установочными входами -го счетчика, устано вочные входы (и)-го счетчика соединен с вторым входом первого элемента ИЛИ, вторыми входами элементов ИЛИ первой группы и входом установки исходного состояния устройства, выход признака окончания работы которого соединен,с выходом (и) -го счетчика, счетный вход 1-го счетчика (3 = 2,п) соединен с выходомпереноса (3-1)-го счетчика, единичными входами триггеров группы и с входами соответствующих элементов ЗАПРЕТ группы, выход первого разряда первого счетчика соединен с вторым входом первого элемента И второй группы, второй вход 25 Е-го элемента И которой Ь = 2,п) соединен с выходом соответствующего элемента ЗАПРЕТ группы, второй вход (и)-го элемента И второй группы соединен с выходом (и)-го счетчи 30 ка, выходы элементов И второй группы соединены с первыми входами соответствующих элементов ИЛИ второй груп. пы, вьиод каждого нечетного элемента И второй группы соединен с соответствующими входами предыдущих не 35 четных элементов ИЛИ второй группы, выход каждого четного элемента И второй группы, начиная с четвертого, соединен с соответствующим входом предыдущих четных элементов ИЛИ второй группы, выходы элементов ИЛИ второй группы, выход каждого т-го (в = 1,п) элемента ИПИ которой соединен с синхронходом 1 п-Го и (Гп+ 1) Го регистров выходы разрядов каждого регистра соединены с входами одноименных разрядов предыдущего и последующего регистров, выходы элементов ИЛИ третьей группы и и-го регистра являются информационными выходами устройства,50 о т л и ч а ю щ е е с я тем, что,с целью повышения быстродействия, оносодержит третий элемент задержки,Т-триггер, элемент НГ, первый и второй элементы ЗАПРЕТ, первый и второйэлементы И, второй элемент ИЧИ н и"1групп элементов И, причем выход переноса первого счетчика соединен спервыми входами первых элементовЗАПРЕТ и И, вторые входы которых соединены с выходом Т-триггера, вход которого соединен с выходом переносавторого счетчика, выходы первых элементов ЗАПРЕТ и И соединены с третьимвходом первого элемента ЗАПРЕТ груп"пы и первым входом второго элементаЗАПРЕТ, остальные вхоцы которого соединены с соответствующими выходамипереноса счетчиков, выход второгоэлемента ЗАПРЕТ соединен с первымвходом второго элемента И, второйвход которого соединен с выходом первого элемента задержки, выход второго элемента И соединен с входом второго элемента ИЛИ, выход которого соединен с синхровходами второго и четвертого регистров, восход первогоэлемента задержки соединен с входомтретьего элемента задержки, выходкоторого соединен с входом элемента ПЕ, выход которого соединен с первыми входами нечетных элементов И стретьей по (и+1)-ю групп, первые входы четных элементов И которых соединены с выходом третьего элемента задержки, выход каждого ра;ряда второго и четвертого регистров соединен содним из входов разряда соответственно второго и четвертого регистров,выходы каждого разряда 1 - го регистра(1 = ,п) соединены с вторыми входами четных элементов И 1-й группыи вторыми входами нечетных элементовИ (1+2) -й и (1-2) -й групп, выходыэлементов И с третьей по (и+1)-югрупп соединены попарно с входамиэлементов ИЛИ третьей группы, счетный вход первого счетчика соединенс входом первого элемента задержкии тактовым входом устройства,1397933 фиа 2 Составитель О,БереэиковаРедактор И.Николайчук Техред М.Ходанич ректор А. Обруч Зак одписно Проиэводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,272/48 Тираж 704 ВНИИПИ Государственного по делам иэобретений и 113035, Москва, Ж, Раушс