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

первого элемента И первой группы, выход переноса предпоследнего счетчика соединен с вторым входом последнего элемента И первой группы, вторые входы элементов И первой группы, кроме первого и последнего, соединены с выходами соответствующих элементов запрета, выход каждого нечетного элемента И цервой группы, начиная с третьего, соедине с соответствующими входамипредьщущих нечетных элементов ИЛИ первой группы, выход каждого четного элемента И первой группы, начиная с четвертого, соединен с соответствующими входами предыдущих четных элементов ШШ первой группы, выходы разрядов каждого регистра соединены с входами одноименных разрядов предьщущего и последуклдего регистров, выходы элементов И каждой строки матрицы соединены с входами соответствукяцего элемента ИЖ третьей гРУПпы, выходы элементов ИЛИ третьей-группы являются группой информационных выходов устройства, выход переноса последнего счетчика является выходом сигнала окончания работы устройства, второй вход первого элемента ИЛИ являеся вторым тактовым входом устройства.

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК, содержащее п-1 счетчиков, где п- число переставляемых элементов, две группы элементов И, матрицу элементов И, первый элемент ИЛИ, первую группу элемен- тов ИЛИ, два элемента задержки, регистр сдвига и п регистров, причем выход каждого л-го

J

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

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

На фиг.1 представлена схема устройства для случая пяти перестарляемых элементов , на фиг.2 - схема взаимосвязи регистров; на фиг.3 схема разряда регистра.

Счетчики 1-4, группы элементов И 5-8, 9-11, элемент ИЛИ 12, элементы 13 и 14 задержки, регистр 15 сдвига, вход 16 установки исходного состояния устройства, тактовые входы 17 и 18 устройства, выход 19 устройства, группа выходов 20 устройства, группа эдементов ИЛИ 21-24 элемент ИЛИ 25, группы элементов ИЛИ 26-28, 29-33, триггеры 3436, элементы 37 и 38 запрета; вход 39 и выход 40 регистра сдвига, матрица элементов И 41-65, регистры 6670, триггер 71, элементы И 72 и 73, элементы ИЛИ 74 и 75, выход 76 раз-. ряда регистра, входы 77 и 78 разряда регистра, синхронизирующие входы 79 и 80 разряда регистра.

Принцип работы устройства состоит в следующем.

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

1234

1234

1234

1234

0001

1000

0010

0100

7 100013 0100 190001 0001 00101000

0100 00010010

-

1234 12341234

8 001014 0100 201000 0100 10000001 Стрелки показывают между какими вертикальными столбцами должен происходить обмен кодами для получения очередной перестановки. Из приведенной последовательности перестановок матрицы нетрудно заме- тить, что. между третьим и четвертым столбцами обмен происходит через шесть перестановок, между вторым и третьим - через одну перестановку, между первым и вторым cтoлбцa ш тоже через одну. Причем смена элементов (кодов) между двумя старшими столбцами влечет за собой смену элементов (кодов) между всеми парами всех млад ших столбцов. Это видно из приведенного примера. Когда через шесть пере становок происходит обмен элементов (кодов) между 3 и 4 столбцами, то одновременно должен происходить обмен кодов между первым и вторым столбцами. Когда же старшими при обмене являются столбцы первый и вто.рой или второй и третий, то они не вызывают обмена между парами младших столбцов, поскольку таковых просто нет - .они сами являются младшими. Экстраполируя приведенное правило на большее число элементов, можно

1903884

утверждать, что обмен между четвертым и пятым столбцами будет происходить через 24 перестановки, между пятым и шестым столбцами обмен будет 5 происходить через 120 перестановок. , В конечном счете между N и N-1 столбцами такая смена будет происходить через (N-1) перестановок.

На основании сказанного можно, О например, подсчитать, что после сто двадцатой перестановки, т.е. для получения сто двадцать первой пере. становки должна происходить смена элементов между 1и2, Зи4, 5и t5 6 столбцами.

100000

010000 Аналогично, для получения 721 перестановки должен происходить обмен элементами (кодами) между 2 и 3, 4 и 5, 6 и.7 столбцами 12345671234567 00000010000010 00000100000001 720 0000100 7210001000 00010000000100 00100000100000 01000000010000 1000000 1000000 После того, как произойдет обмен элементами (кодами) между любыми старшими столбцами, процесс обмена элементами (кодами) между столбцами начинает повторяться между вторым и третьим столбцами и т.д. В предлагаемом устройстве каждая перестановка получается путем обмена содержимым разрядов соседних регистров по описанной закономерности Устройство работает в двух режимах: в .режиме выдачи параллельного кода перестановок и в режиме пространственно-временной формы последовательности появления сигналов на выходах устройства.

Устройство в режиме формирования перестановок в форме параллельного кода работает следующим образом. По сигналу, поступающему на вход 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, 2j 3, 4, 5 соответственно. По второму тактовому импульсу единичны потенциал появится на выходе счетчика 1 и, пррйдя через элемент 37 запрета, элементы И 6, ИЛИ 22, попадет на соответствующие синхронизирующие входы регистров 67, 68, что приведет к обмену содержимым между ними. На выходах 19 устройства буду зафиксированы коды 1, 3, 2, 4, 5 соответственно. Задержанный второй тактовый импульс, пройдя через элементы И9, ИЛИ 26, сбросит счетчик 1 в исходное состояние. После шестого тактового импульса на выходах счетчиков 1 и 2 появится единичный потенциал, но сигнал с выхода счетчика 1 является старшим, он закро-ет элемент 37 запрета и пройдет через элемент 38 запрета, открытый.элемент И 7, элементы ИЖ 23, ШИ 21 и попадает на соответствующие входы разрядов регистров 66-69, что вызовет обмен содержимым между первым и вторым, третьим и четвертым-столбцами одновременно, аналогично двадцать пятый тактовый импульс вызовет обмен меходу 2 и 3, 4 и 5 столбцами. После прихода 120 тактового импульса на выходе счетчика 4 появится единичный потенциал, что будет свидетельство вать об окончании работы устройства Аналогично устройство работает в режиме пространственно-временной формы последовательности появления сигналов на выходе устройства. Устройство приводится в исходное состояние и в первый разряд регистра сдвига записывается единица. Тактовые импульсы, поступающие на вход устройства 17, а затем на вход 39 регистра 15, будут продвигать последовательно по всем разрядам записанную ранее в первый разряд 1.

поэтому на выходах элементов И 41, 47 53, 59, 65 будут последовательно появляться единичные импульсы. Так как выходы элементов И 41-65 соединены с соответствующими входами элементов ИЛИ 29-33, то единичньм сигнал появится последовательно на выходах элементов UMi 30, 29, 31, 32, 33. Сигнал с выхода регистра 15 сдвига попадет на вход элемента ИЖ 25, что приведет к обмену содержимым между регистрами 66 и 67. В результате нового цикла работы регистра 15 единичные сигналы появятся на выходах элементов ИЛИ29-33 в следующей последовательности: 29, 30, 31, 32, 33.

В следующем цикле очередность появления сигналов на выходах элементов ИЛИ 29-33 будет такая: 30, 29, 31, 32, 33 и далее в соответствии с описанным алгоритмом.

Устройство представляет собой практически однородную структуру, так как разряды строятся по одному и тому же принципу. Поэтому, если возникает необходимость увеличить число элементов в перестановках, то необходимо добавить соответствующее число разрядов.

77 18 фиг. 2