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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (L9) ((1) (51)4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1-"

Н ABTOPGHOMV СВИДЕТЕЛЬСТБУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3747196/24-24 (22) 30.05.84 (46) 07.11.85. Бюл. № 41 (71) Таганрогский радиотехнический институт им.В.Д.Калмыкова (72) В.И.Глушань, Б.Н.Ковтун, В.M. Kóðåé÷èê, M.È.Ïóïêîâ и Л.И.Щербаков (53) 681.325.5(088.8) (5e) Авторское свидетельство СССР № 643883, кл. G 06 F 15/20, 1977.

Авторское свидетельство СССР

¹ 922755, кл. G 06 Р 15/20, 1980.

Авторское свидетельство СССР № 748416, кл.. С 06 Г 15/20, 1978. (54)(57) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА

ПЕРЕСТАНОВОК, содержащее и --1 счетчиков, где n — - число переставляемых элементов, две группы элементов И, матрицу элементов И, первый элемент ИЛИ, первую группу элементов ИЛИ, два элемента зацержки, регистр сдвига и и регистров, причем выход каждого i-ro (1=1, n ) элемен. та ИЛИ первой группы соединен с еинхронизирующими входами i --ro и 1 +1го регистров, первый вход каждого элемента ИЛИ первой группы соединен с выходом соответствующего элемента И первой группы, выходы разрядов каждого регистра соединены с первыми входами элементов И соответствующего столбца матрицы и с первым информационным выходом устройства, вход управления сдвигом регистра сдвига соединен с первым тактовым входом устройства, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей путем обеспечения возможности формирования перестановок в пространственно — временной форме, в него введены триггеры, вторая и третья группы элементов ИЛИ, элементы saпрета и второй элемент ИЛИ, причем выход каждого разряда регистра сдвига соединен с вторыми входами элементов И соответствующего столбца матрицы, выход переноса регистра сдвига соединен с первым входом первого элемента ИЛИ, выход которого соединен со счетным входом первого счетчика и с входом первого элемента задержки, выход которого соединен с входом второго элемента задержки и .с первыми входами элементов И первой и второй групп,-выход второго элемента задержки подключен к первому входу второго элемента ИЛИ, выход которого соединен с нулевыми входами триггеров, второй вход второго элемента ИЛИ, первые входы элементов ИЛИ второй группы и установочный вход последнего счетчика соединены с входом установки исходного состояния устройства, выход переноса каждого счетчика, кроме последнего, соединен со счетным входом. после. дующего счетчика, с входами соответствующих элементов запрета и с еди.ничным входом соответствующего триггера, выход каждого из которых соединен с вторым входом .соответствующего элемента И .второй группы, выход которого подключен к второму входу соответствующего элемента ИЛИ второй группы, выход каждого элемента ИЛИ второй группы соединен с установочным входом соответствующего счетчика, выход первого разряда первого счетчика соединен с вторым входом

11 первого элемента И первой группы, выход переноса предпоследнего счетчика соединен с вторым входом последнего элемента И. первой группы, вторые входы элементов И первой группы, кроме первого и.последнего, соединены с выходами соответствую-. щих элементов запрета, выход каждого нечетного элемента И первой группы, начиная с третьего, соединен с соответствующими входами предыдущих нечетных элементов ИЛИ первой группы, выход каждого четного элемента И первой группы, начиная с четвертого, соединен с соответству90388 ющими входами предыдущих четных элементов ИЗЯ первой группы, выходы разрядов каждого регистра соединены с входами одноименных разрядов предыдущего и последующего регистров, выходы элементов И каждой строки матрицы соединены с входами соответствующего элемента ИЛИ третьей группы, выходы элементов ИЛИ третьей .группы являются группой информационных выходов устройства, выход переноса последнего счетчика является выходом сигнала окончанияработы устройства, второй входпервого элемента ИЛИ является вторым тактовым входомустройства.

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

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

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

Счетчики 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 разряда регистра.

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

1234

1234 1234

1234

0001

0010

0100

1000

1 0010 7 1000 13 0100 19 0001

0001

0100

1000

0010

1000

+-Ф

1234

1234

0001

1234

1234

2 0001 8 0010 14 0100 20 1000

0010

1000

0001

0100

0100

1000 0001

0010

0100

0001

0001

0010

1000

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

0100 0010

i 000 0001

3 1000 9 0001 15 0100 21 0010

0100

1000 0010

0001

0100 0001

0010

1000

4 0010 10 0100 16. 0001 22 1000

0001 . 1000 0100 0010

1000 0100 . 0010 0001

5 0010 11 0001 17 1000 23 0100

0100 0010 0001 1000

0001 0100 1000 0010

0010 0001

0100 1000

6 0010 12 0001 18 0100 24 1000

1000 0010 0001 0100

0001

1000

0001

0010

0100

123456

123456

000001

010000

120 . 000001

000010 121

100000

1190388 утверждать, что обмен между четвертым и пятым столбцами будет происходить через 24 перестановки, между пятым и шестым столбцами обмен будет происходить через 120 перестановок.

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

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

15 6 столбцами.

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

Из приведенной последовательности перестановок матрицы нетрудно заметить, что.между третьим и четвертым столбцами обмен происходит через шесть перестановок, между вторым и третьим — через одну перестановку, между первым и вторым столбцами тоже через одну. Причем смена элементов (кодов) между двумя старшими столбцами влечет за собой смену элементов (кодов) между всеми парами всех младших столбцов. Это видно из приведенного примера. Когда через шесть перестановок происходит обмен элементов (кодов) между 3 и 4 столбцами, то одновременно должен происходить обмен кодов между первым и вторым столбцами. Когда же старшими при обмене являются столбцы первый и вто; рой или второй и третий, то они не вызывают обмена между парами младших столбцов, поскольку таковых просто нет — они сами являются младшими.

Экстраполируя приведенное правило на большее число элементов, можно

30 Аналогично, для получения 721 перестановки должен происходить обмен элементами (кодами) между 2 и 3, 4 и 5, 6 и 7 столбцами

720

0000100 721 0001000

После того, как произойдет обмен элементами (кодами) между любыми старшими столбцами, процесс обмена элементами (кодами) между столфцами начинает повторяться между вторым и третьим столбцами и т.д.

В предлагаемом устройстве каждая перестановка получается путем обме1234567

0000001

0000010

1000000

1234567

0000001

1000000.1190388

55 на содержимым разрядов соседних регистров по описанной закономерности.

Устройство работает в двух режимах: в режиме выдачи параллельного кода перестановок и в режиме пространственно-временной формы последовательности появления сигналов на выходах устройства.

Устройство в режиме формирования перестановок в форме параллельного кода работает следующим образом.

По сигналу, поступающему на вход

16 установки исходного состояния, сбрасываются счетчики 1-4 и триггеры 34-36, во второй разряд регистра

66, первый разряд регистра 67, третий разряд регистра 68, четвертый разряд регистра 69 и пятый разряд регистра 70 записываются единицы, на выходах .19 устройства будут ко ды 2, 1, 3, 4, 5 соответственно. По первому тактовому импульсу, поступающему на вход 18 устройства, на выходе первого разряда счетчика 1 появится единичный потенциал, который, пройдя через открытый элемент И 5, одновременно на вход которого подается задержанный первый импульс, через элемент ИЛИ 2 i попадет на синхронизирующие входы 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

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 и далее в соответствии с описанным алгоритмом.

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

1190388

1190388

77 78 Щдг.Я

Составитель А.М(еренов

Редактор С.Патрушева Техред Л.Мартяшова Корректор М.Максимишинец

Заказ 6989/52 Тираж 709 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Филиал ППП "Патент", r.Óæãîðoä, ул.Проектная, 4