Результат интеллектуальной деятельности: Устройство для перебора перестановок

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

Известно устройство [1], обеспечивающее генерацию перестановок исходных величин. Недостатком этого устройства является низкая надежность из-за больших аппаратных затрат.

Наиболее близким по технической сущности к заявляемому является устройство для перебора перестановок [2], содержащее первые элементы И 2_ij (i=1,…n, j=1,…n), вторые элементы И 3_ij (i=1,…n, j=1,…n), первые элементы ИЛИ 4_ij (i=1,…n, j=1,…n), третьи элементы И 5_ij (i=1,…n, j=1,…n), вторые элементы ИЛИ 6_ij (i=1,…n, j=1,…n), четвертые элементы И 7_ij (i=1,…n, j=1,…n), генератор тактовых импульсов 8, первый счетчик 10, первый регистр 12, второй счетчик 13, второй регистр 15, выход первого элемента И 2_ij (i=1,…n, j=1,…n) подсоединен к первому входу первого элемента ИЛИ 4_ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу второго элемента И 3_ij (i=1,…n, j=1,…n), выход третьего элемента И 5_ij (i=1,…n, j=1,…n) подсоединен к первому входу второго элемента ИЛИ 6_ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу четвертого элемента И 7_ij (i=1,…n, j=1,…n).

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

Задача изобретения - создать устройство, обеспечивающее формирование в произвольной последовательности перестановок двоичных кодов и при существенном сокращении аппаратных затрат.

Это решение достигается тем, что в устройство, содержащее первые элементы И 2_ij (i=1,…n, j=1,…n), вторые элементы И 3_ij (i=1,…n, j=1,…n), первые элементы ИЛИ 4_ij (i=1,…n, j=1,…n), третьи элементы И 5_ij (i=1,…n, j=1,…n), вторые элементы ИЛИ 6_ij (i=1,…n, j=1,…n), четвертые элементы И 7_ij (i=1,…n, j=1,…n), генератор тактовых импульсов 8, первый счетчик 10, первый регистр 12, второй счетчик 13, второй регистр 15, выход первого элемента И 2_ij (i=1,…n, j=1,…n) подсоединен к первому входу первого элемента ИЛИ 4_ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу второго элемента И 3_ij (i=1,…n, j=1,…n), выход третьего элемента И 5_ij (i=1,…n, j=1,…n) подсоединен к первому входу второго элемента ИЛИ 6_ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу четвертого элемента И 7_ij (i=1,…n, j=1,…n), введены матрица n*n триггеров 1_ij (i=1,…n, j=1,…n), пятый элемент И 9, первая схема сравнения 11, вторая схема сравнения 14, шестой элемент И 16, седьмой элемент И 17, выход генератора тактовых импульсов 8 подсоединен к первому входу пятого элемента И 9, инверсный вход которого подсоединен к выходу седьмого элемента И 17, а выход - к входу первого счетчика 10, к первому входу шестого элемента И 16 и к С-входам триггеров 1_ij (i=1,…n, j=1,…n), прямой выход триггера 1_ij (i=1,…n, j=1,…n) подсоединен к первому входу третьего элемента И 5_ij (i=1,…n, j=1,…n) и к второму входу четвертого элемента И 7_(i-1)(j-1) (i=1,…n, j=1,…n), обратный выход триггера 1_ij (i=1,…n, j=1,…n) подсоединен к первому входу первого элемента И 2_ij (i=1,…n, j=1,…n) и к второму входу второго элемента И 3_(i-1)(j-1) (i=1,…n, j=1,…n), выход шестого элемента И 16 подсоединен к управляющим входам первых элементов И 2_ij (i=1,…n, j=1,…n), третьих элементов И 5_ij (i=1,…n, j=1,…n), выход первого счетчика 10 подсоединен к первому входу первой схемы сравнения 11, второй вход которого подсоединен к выходу первого регистра 12, а выход - к входу счетчика 13, к входу сброса в ноль счетчика 10, к инверсному входу шестого элемента И 16, к первому входу седьмого элемента И 17, к вторым входам второго элемента И 3_ij (i=1,…n, j=1,…n), к вторым входам четвертого элемента И 7_ij (i=1,…n, j=1,…n), выход первого элемента ИЛИ 4_ij (i=1,…n, j=1,…n) подсоединен к R - входу триггера 1_i(j+1) (i=1,…n, j=1,…n), выход второго элемента ИЛИ 6_ij (i=1,…n, j=1,…n) подсоединен к S - входу триггера 1_i(j+1) (i=1,…n, j=1,…n), выход второго счетчика 13 подсоединен к первому входу второй схемы сравнения 14, второй вход которого подсоединен к выходу второго регистра 15, а выход - к второму входу седьмого элемента И 19.

Проведенный поиск в известной научно-технической литературе не выявил наличие подобных технических решений.

Сущность изобретения поясняется чертежом, где на чертеже (фиг. 1) представлены: матрица n*n триггеров 1ij (i=1,…n, j=1,…n), элементы И 2ij (i=1,…n, j=1,…n), элементы И 3_ij (i=1,…n, j=1,…n), элементы ИЛИ 4_ij (i=1,…n, j=1,…n), элементы И 5_ij (i=1,…n, j=1,…n), элементы ИЛИ 6_ij (i=1,…n, j=1,…n), элементы И 7_ij (i=1,…n, j=1,…n), генератор тактовых импульсов 8, элемент И 9, счетчик 10, схема сравнения 11, регистр 12, счетчик 13, схема сравнения 14, регистр 15, элемент И 16, элемент И 17, вход 18, выход 19.

Матрица триггеров 1_ij (i=1,…n, j=1,…n) на рис. 1 из-за громоздкости представлена только триггерами 1_ij, 1_(i-1)j, 1_i(j+1), 1_(i-1)(j+1).

Работа устройства основана на реализации процедуры n последовательных циклических сдвигов всех триггеров 1_ij (i=1,…n, j=1,…n) одного j-го столбца в триггеры 1_ij соседнего (j+1) - го справа столбца, после чего аналогично происходит n последовательных циклических сдвигов всех триггеров 1_ij одной i-ой строки в триггеры 1_ij соседней сверху (i-1) - ой строки и т.д. При этом сдвиг содержимого триггеров 1_ij (i=1,…n, j=l,…n) n-го столбца происходит циклически в триггеры 1_ij первого столбца, а сдвиг содержимого триггеров 1_ij (i=1,…n, j=1,…n) первой строки происходит циклически в триггеры 1_ij n ой строки.

В исходном состоянии счетчики 10 и 13 находятся в нулевом состоянии. На регистрах 12 и 15 хранятся коды числа n. Триггеры 1_ij (i=1,…n, j=1,…n) хранят исходную информацию, при этом триггер 1_ij установлен в единичное или нулевое состояние в зависимости от исходных данных.

На выходе схемы сравнения 14 будет нулевой сигнал, который подается на первый вход элемента И 17. На инверсный вход элемента И 9 подается нулевой сигнал с выхода элемента И 17. На инверсный вход элемента И 16 подается нулевой сигнал с выхода схемы сравнения 11.

После подачи пускового сигнала по входу 18 на управляющий вход элемента И 9 импульсы с выхода генератора 8 через открытый элемент И 9 начинают поступать на первый вход элемента И 16, на входы синхронизации С триггеров 1_ij (i=1,…n, j=1,…n) и на вход счетчика 10, с выхода которого код поступает на первый вход схемы сравнения 11.

Сигнал с выхода элемента И 9 через открытый элемент И 16 поступает на управляющие входы элементов И 2_ij (i=1,…n, j=1,…n) и элементов И 5_ij (i=1,…n, j=1,…n), после чего осуществляется циклический сдвиг содержимого всех триггеров 1_ij одного j-го столбца в триггеры 1 соседнего (j+1)-го справа столбца. При этом сдвиг содержимого триггеров 1_ij (i=1,…n, j=1,…n) n-го столбца происходит циклически в триггеры 1_ij первого столбца. Аналогичный циклический сдвиг содержимого всех триггеров 1_ij одного столбца в триггеры 1_ij соседнего справа столбца происходит ровно n раз, после чего на выходе схемы сравнения 11 появляется единичный сигнал.

После достижения счетчиком 10 числа n на выходе схемы сравнения 11 появляется единичный сигнал, который подается на вход сброса в ноль счетчика 10, на управляющие входы элементов И 3_ij (i=1,…n, j=1,…n) и входы элементов И 7_ij (i=1,…n, j=1,…n), после чего осуществляется циклический сдвиг содержимого всех триггеров 1 одной строки в триггеры 1 соседней сверху строки. При этом сдвиг содержимого триггеров 1_ij (i=l,…n, j=1,…n) первой строки происходит циклически в триггеры 1_ij n-ой строки.

Аналогичный циклический сдвиг содержимого всех триггеров 1_ij одной строки в триггеры 1 соседней сверху строки происходит ровно n раз, после чего на выходе схемы сравнения 14 появляется единичный сигнал.

После достижения счетчиком 13 числа n на выходе схемы сравнения 14 появляется единичный сигнал, который подается на первый вход элемента И 17, а после достижения счетчиком 10 числа n на выходе схемы сравнения 11 появляется также единичный сигнал, который подается на второй вход элемента И 17. Единичный сигнал на выходе элемента И 17 подается на выход 19 (конец работы устройства) и на инверсный вход элемента И 9, после чего прекращается подача счетных импульсов с выхода генератора 8 на вход счетчика 10. Получаемые все перестановки последовательно снимаются с выходов триггеров 1_in (i=1,…n).

Частота сигналов генератора 8 выбирается с учетом последовательности надежного срабатывания элемента И 9, элемента И 16, элемента И 2, элемента ИЛИ 4, триггера 1, счетчика 10, схемы сравнения 11, счетчика 13, схемы сравнения 14, элемента И 17.

Таким образом, предлагаемое устройство обеспечивает формирование перестановок детерминированного числа элементов n, определяемого пользователем. Это свидетельствует о достигнутом существенном снижении аппаратных затрат расширении функциональных возможностей по сравнению с прототипом и достижении цели изобретения.

Использованные источники

1. RU N 1190388, кл. G06F 15/20.

2. RU N 1383381, кл. G06F 15/20.