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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 5 ц 4 С 06 Г 15 2 ИЕ ИЗОБРЕТЕНМУ СВИДЕТЕЛЬСТВУ ОПИСА Н АВТОРСКО ский.Щеродом после дами соотве ета и с еди вующего тригкоторых соеоответствуюгруппы, выхоорому входута ИЛИ второ лемента ИЛИс устано щего счетчи да первого рым входом УДАРСТВЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) Авторское свидетельство СССРВ 643883, кл, 6 06 Р 15/20 в 1977.Авторское свидетельство СССРКф 922755, кл, С 06 Г 15/20, 1980.Авторское свидетельство СССРР 748416, кл С 06 Р 15/20, 1978.(54)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРАПЕРЕСТАНОВОК, содержащее д -1 счетчиков, где ь - число переставляемыхэлементов, две группы элементов И,матрицу элементов И, первый элемент ИЛИ, первую группу элементов ИЛИ, два элемента зацержки, регистр сдвига и о регистров, причемвыход каждого -го (1=1, ь ) элемен-та ИЛИ первой группы соединен с еин.хронизирующими входами 1-го и 1 +1 го регистров, первый вход каждогоэлемента ИЛИ первой группы соединенс выходом соответствующего элемента И первой группы, выходы разрядовкаждого регистра соединены с первыми входами элементов И соответствующего столбца матрицы и с первым информационным выходом устройства,вход управления сдвигом регистрасдвига соединен с первым тактовымвходом устройства, о т л и ч а ю -щ е е с я тем,что, с целью расширения функциональных возможностейпутем обеспечения возможности формирования перестановок в пространственно - временной форме, в него введены триггеры, вторая и третья группы элементов ИЛИ, элементы запрета и второй элемент ИЛИ, причем выход каждого разряда регистра сдвига соединен с вторыми входами элементов И соответствующего столбца матрицы, выход переноса регистра сдвига соединен с первым входом первого элемента ИЛИ, выход которого соединен со счетным входом первого счетчика и с входом первого элемента задержки, выход которого соединен с входом второго элемента задержки и .с первыми входами элементов И первой и второй групп,.выход второго элемента задержки подключен к первому входу второго элемента ИЛИ, выход которого соединен с нулевыми входами триггеров, второй вход второго элемента ИЛИ, первые входы элементов ИЛИ второй группы и установочный вход последнего счетчика соединены с входом установки исходного состояния устройства, выход переноса каждого счетчика, кроме последнего, соединен со счетнымдующего счетчика, с вхоствующих элементов запр.ничным входом соответстгера, выход каждого издинен с вторым входом сщего элемента И второйкоторого подключен к втсоответствующего элеменгруппы, выход каждого эвторой группы соединенным входом соответствую ка, выход первого разря счетчика соединен с вто11 первого элемента И первой группы, выход переноса предпоследнего счетчика соединен с вторым входом последнего элемента И. первой группы, вторые входы элементов И первой группы, кроме первого и.последнего, соединены с выходами соответствую-. щих элементов запрета, выход каждого нечетного элемента И первой группы, начиная с третьего, соединен с соответствующими входами предыдущих нечетных элементов ИЛИ первой группы, выход каждого четного элемента И первой группы, начиная с четвертого, соединен с соответству 90388ющими входами предыдущих четных элементов И 331 первой группы, выходы разрядов каждого регистра соединены с входами одноименных разрядов предыдущего и последующего регистров, выходы элементов И каждой строки матрицы соединены с входами соответствующего элемента ИЛИ третьей группы, выходы элементов ИЛИ третьей группы являются группой информационных выходов устройства, выход переноса последнего счетчика является выходом сигнала окончанияработы устройства, второй входпервого элементаИЛИ являерся вторым тактовым входомустройства.Изобретение относится к вычисли тельной технике и может быть использовано для решения задач автоматизи. рованного конструирования радиоэлектронной и вычислительной аппаратуры. 5Цельизобретения - расширение функцнональных возможностейпутем обеспечения возможности формирования перестановок в пространственно- временной форме и повышение быстро действия.На фиг.1 представлена схема устройства для случая пяти переставляемых элементов; на фиг.2 - схема взаимосвязи регистров; на фиг,З - 15схема разряда регистра.Счетчики 1-4, группы элементов И 5-8, 9-11, элемент ИЛИ 12, элементы 13 и 14 задержки, регистр 15 сдвига, вход 16 установки исходного состояния устройства, тактовые входы 17 и 18 устройства, выход 19 устройства, группа выходов 20 устройства, группа элементов ИЛИ 21-24, элемент ИЛИ 25, группы элементов ИЛИ 26-28, 29-33, триггеры 34- Зб, элементы 37 и 38 запрета, вход 39 и выход 40 регистра сдвига, матрица элементов И 41-65, регистры 6670, триггер 71, элементы И 72 и 73, элементы ИЛИ 74 и 75, выход 76 раз-, ряда регистра, входы 77 и 78 разряда регистра, синхронизирующие входы79 и 80 разряда регистра.Принцип работы устройства состоит в следующем.0100 1234 0001 1234 0010 1234 2 0001 8 0010 14 0100 20 1000 0010 1000 0001 0100 1000 0001 0010 0100 0100 0001 1000 0100 0001 0010 0010 1000 2Каждая очередная перестановка получается из предыдущей путем обмена элементов (кодов) между соседними вертикальными рядами ячеек, причем последовательность обмена изменяется по строго определенной закономерности. Эту закономерность рассмот-. рим на примере перестановок четырех элементов (кодов). Пронумеруем вертикальные столбцы слева направо и запишем диагональ матрицы снизу . вверх и слева направо ."1". Тогда для четырех элементов получим следующие 24 перестановки:123456 123456 000010 000001 001000 000100 100000 010000 120 . 000001 20 000010 121 000100 001000 010000 100000 1190388утверждать, что обмен между четвертым и пятым столбцами будет происходить через 24 перестановки, междупятым и шестым столбцами обмен будетпроисходить через 120 перестановок.В конечном счете между И и 0-1 столбцами такая смена будет происходитьчерез (И) 1 перестановок.На основании сказанного можно, 10 например, подсчитать, что после стодвадцатой перестановки, т.е. дляполучения сто двадцать первой перестановки должна происходить сменаэлементов между 1 и 2, 3 и 4, 5 и 15 6 столбцами.З 0 Аналогично, для получения 721 перестановки должен происходить обменэлементами (кодами) между 2 и 3, 4и 5, 6 и 7 столбцами 12345670000001 0000010 1234567 0000010 0000001 40720 0001000 0010000 0100000 1000000 0000100 0100000 0010000 1000000 50После того, как произойдет обменэлементами (кодами) между любымистаршими столбцами, процесс обменаэлементами (кодами) между столрцаминачинает повторяться между вторыми третьим столбцами и т.д. Стрелки показывают между какимивертикальными столбцами должен происходить обмен кодами для полученияочередной перестановки,Из приведенной последовательностиперестановок матрицы нетрудно заметить, что.между третьим и четвертымстолбцами обмен происходит черезшесть перестановок, между вторым итретьим - через одну перестановку,между первым и вторым столбцами тожечерез одну. Причем смена элементов(кодов) между двумя старшими столбцами влечет за собой смену элементов(кодов) между всеми парами всех млад.ших столбцов. Это видно из приведенного примера, Когда через шесть перестановок происходит обмен элементов(кодов) между 3 и 4 столбцами, тоодновременно должен происходить обмен кодов между первым и вторымстолбцами. Когда же старшими при обмене являются столбцы первый и вто;рой или второй и третий, то они невызывают обмена между парами младшихстолбцов, поскольку таковых простонет - они сами являются младшими.Экстраполируя приведенное правилона большее число элементов, можно 0000100 721 0001000 В предлагаемом устройстве каждаяперестановка получается путем обме45 50 55 на содержимым разрядов соседних регистров по описанной закономерности. Устройство работает в двух режимах; в режиме выдачи параллельного кода перестановок и в режиме пространственно-временной формы последовательности появления сигналов на выходах устройства.Устройство в режиме формирования перестановок в форме параллельного кода работает следующим образом.По сигналу, поступающему на вход 16 установки исходного состояния, сбрасываются счетчики 1-4 и триггеры 34-36, во второй разряд регистра 66, первый разряд регистра 67, третий разряд регистра 68, четвертый разряд регистра 69 и пятый разряд регистра 70 записываются единицы, на выходах .19 устройства будут коды 2, 1, 3, 4, 5 соответственно. По первому тактовому импульсу, поступающему на вход 18 устройства, на вы" ходе первого разряда счетчика 1 появится единичный потенциал, который, пройдя через открытый элемент И 5, одновременно на вход которого подается задержанный первый импульс, че. рез элемент ИЛИ 21 попадет на синхронизирующие входы 79 и 80, разрядов регистра 66 и синхронизирующие входы разрядов регистра 67, что приведет к обмену содержимым между регистрами 66 и 67. На выходах 19 устройства будут зафиксированы коды 1, 2, 3, 4, 5 соответственно. По второму тактовому импульсу единичный потенциал появится на выходе счетчика 1 и, пройдя через элемент 37 запрета, элементы И 6, ИЛИ 22, попа-. дет на соответствующие синхронизирующие входы регистров 67, 68, что приведет к обмену содержимым между ними. На выходах 19 устройства будут зафиксированы коды 1, 3, 2, 4, 5 соответственно. Задержанный второй тактовый импульс, пройдя через элементы И 9, ИЛИ 26, сбросит счетчик 1 в исходное состояние. После шестого тактового импульса на выходах счетчиков 1 и 2 появится единичный потенциал, но сигнал с выхода счетчика 1 является старшим, он закроет элемент 37 запрета и пройдет через элемент 38 запрета, открытый эле 5 10 15 20 25 30 35 40 мент И 7, элементы ИЛИ 23, ИЛИ 2 1 и попадает на соответствующие входы разрядов регистров 66-69, что вызовет обмен содержимым между первым и вторым, третьим и четвертым "столбцами одновременно, аналогично двадцать пятый тактовый импульс вызовет обмен между 2 и 3, 4 и 5 столбцами. После прихода 120 тактового импульса на выходе счетчика 4 появится единичный потенциал, что будет свидетельствовать об окончании работы устройства.Аналогично устройство работает в режиме пространственно-временной формы последовательности появления сигналов на выходе устройства. Устройство приводится в исходное состояние и в первый разряд регистра сдвига записывается единица. Тактовые импульсы, поступающие на вход устройства 17, а затем на вход 39 регистра 15, будут продвигать последовательно но всем разрядам записанную ранее в первый разряд "1", поэтому на выходах элементов И 41, 47, 53, 59, 65 будут последовательно появляться единичные импульсы. Так как выходы элементов И 41-65 соединены с соответствующими входами элементов ИЛИ 29-33, то единичный сигнал появится последовательно на выходах элементов ИЛИ 30, 29, 31, 32, 33. Сигнал с выхода регистра 15 сдвига попадет на вход элемента ИЛИ 25, что приведет к обмену содержимым межцу регистрами 66 и 67. В результате нового цикла работы регистра 15 единичные сигналы появятся на выходах элементов ИЛИ 29-33 в следующей последовательности: 29, 30, 31, 32, 33. В следующем цикле очередность появления сигналов на выходах элементов ИЛИ 29-33 будет такая: 30, 29, 31, 32, 33 и далее в соответствии с описанным алгоритмом.Устройство представляет собой практически однородную структуру, так как разряды строятся по одному и тому же принципу. Поэтому, если возникает необходимость увеличить число элементов в перестановках, то необходимо добавить соответствующее число разрядов.1190388 7 78 Составитель А,ЖереновРедактор С.Патрушева Техред Л.Мартяшова Корректор М.Максимиши лиал ППП "Патент", г.ужгород, ул.Проектн каз 6989/52 Тираж 709 ВНИИПИ Государственного комите по делам изобретений и откр 113035, Москва, Ж, Раушская н