Устройство для перебора перестановок - RU2693996C1
Код документа: RU2693996C1
Чертежи
Описание
Изобретение относится к вычислительной технике, предназначено для формирования в произвольной последовательности перестановок двоичных кодов и может быть использовано для решения комбинаторных задач, а также в системах контроля для генерации кодовых последовательностей.
Известно устройство [1], обеспечивающее генерацию перестановок исходных величин. Недостатком этого устройства является низкая надежность из-за больших аппаратных затрат.
Наиболее близким по технической сущности к заявляемому является устройство для перебора перестановок [2], содержащее первые элементы И 2ij (i=1,…n, j=1,…n), вторые элементы И 3ij (i=1,…n, j=1,…n), первые элементы ИЛИ 4ij (i=1,…n, j=1,…n), третьи элементы И 5ij (i=1,…n, j=1,…n), вторые элементы ИЛИ 6ij (i=1,…n, j=1,…n), четвертые элементы И 7ij (i=1,…n, j=1,…n), генератор тактовых импульсов 8, первый счетчик 10, первый регистр 12, второй счетчик 13, второй регистр 15, выход первого элемента И 2ij (i=1,…n, j=1,…n) подсоединен к первому входу первого элемента ИЛИ 4ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу второго элемента И 3ij (i=1,…n, j=1,…n), выход третьего элемента И 5ij (i=1,…n, j=1,…n) подсоединен к первому входу второго элемента ИЛИ 6ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу четвертого элемента И 7ij (i=1,…n, j=1,…n).
Недостатком данного устройства является низкая надежность из-за больших аппаратных затрат.
Задача изобретения - создать устройство, обеспечивающее формирование в произвольной последовательности перестановок двоичных кодов и при существенном сокращении аппаратных затрат.
Это решение достигается тем, что в устройство, содержащее первые элементы И 2ij (i=1,…n, j=1,…n), вторые элементы И 3ij (i=1,…n, j=1,…n), первые элементы ИЛИ 4ij (i=1,…n, j=1,…n), третьи элементы И 5ij (i=1,…n, j=1,…n), вторые элементы ИЛИ 6ij (i=1,…n, j=1,…n), четвертые элементы И 7ij (i=1,…n, j=1,…n), генератор тактовых импульсов 8, первый счетчик 10, первый регистр 12, второй счетчик 13, второй регистр 15, выход первого элемента И 2ij (i=1,…n, j=1,…n) подсоединен к первому входу первого элемента ИЛИ 4ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу второго элемента И 3ij (i=1,…n, j=1,…n), выход третьего элемента И 5ij (i=1,…n, j=1,…n) подсоединен к первому входу второго элемента ИЛИ 6ij (i=1,…n, j=1,…n), второй вход которого подсоединен к выходу четвертого элемента И 7ij (i=1,…n, j=1,…n), введены матрица n*n триггеров 1ij (i=1,…n, j=1,…n), пятый элемент И 9, первая схема сравнения 11, вторая схема сравнения 14, шестой элемент И 16, седьмой элемент И 17, выход генератора тактовых импульсов 8 подсоединен к первому входу пятого элемента И 9, инверсный вход которого подсоединен к выходу седьмого элемента И 17, а выход - к входу первого счетчика 10, к первому входу шестого элемента И 16 и к С-входам триггеров 1ij (i=1,…n, j=1,…n), прямой выход триггера 1ij (i=1,…n, j=1,…n) подсоединен к первому входу третьего элемента И 5ij (i=1,…n, j=1,…n) и к второму входу четвертого элемента И 7(i-1)(j-1) (i=1,…n, j=1,…n), обратный выход триггера 1ij (i=1,…n, j=1,…n) подсоединен к первому входу первого элемента И 2ij (i=1,…n, j=1,…n) и к второму входу второго элемента И 3(i-1)(j-1) (i=1,…n, j=1,…n), выход шестого элемента И 16 подсоединен к управляющим входам первых элементов И 2ij (i=1,…n, j=1,…n), третьих элементов И 5ij (i=1,…n, j=1,…n), выход первого счетчика 10 подсоединен к первому входу первой схемы сравнения 11, второй вход которого подсоединен к выходу первого регистра 12, а выход - к входу счетчика 13, к входу сброса в ноль счетчика 10, к инверсному входу шестого элемента И 16, к первому входу седьмого элемента И 17, к вторым входам второго элемента И 3ij (i=1,…n, j=1,…n), к вторым входам четвертого элемента И 7ij (i=1,…n, j=1,…n), выход первого элемента ИЛИ 4ij (i=1,…n, j=1,…n) подсоединен к R - входу триггера 1i(j+1) (i=1,…n, j=1,…n), выход второго элемента ИЛИ 6ij (i=1,…n, j=1,…n) подсоединен к S - входу триггера 1i(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), элементы И 3ij (i=1,…n, j=1,…n), элементы ИЛИ 4ij (i=1,…n, j=1,…n), элементы И 5ij (i=1,…n, j=1,…n), элементы ИЛИ 6ij (i=1,…n, j=1,…n), элементы И 7ij (i=1,…n, j=1,…n), генератор тактовых импульсов 8, элемент И 9, счетчик 10, схема сравнения 11, регистр 12, счетчик 13, схема сравнения 14, регистр 15, элемент И 16, элемент И 17, вход 18, выход 19.
Матрица триггеров 1ij (i=1,…n, j=1,…n) на рис. 1 из-за громоздкости представлена только триггерами 1ij, 1(i-1)j, 1i(j+1), 1(i-1)(j+1).
Работа устройства основана на реализации процедуры n последовательных циклических сдвигов всех триггеров 1ij (i=1,…n, j=1,…n) одного j-го столбца в триггеры 1ij соседнего (j+1) - го справа столбца, после чего аналогично происходит n последовательных циклических сдвигов всех триггеров 1ij одной i-ой строки в триггеры 1ij соседней сверху (i-1) - ой строки и т.д. При этом сдвиг содержимого триггеров 1ij (i=1,…n, j=l,…n) n-го столбца происходит циклически в триггеры 1ij первого столбца, а сдвиг содержимого триггеров 1ij (i=1,…n, j=1,…n) первой строки происходит циклически в триггеры 1ij n ой строки.
В исходном состоянии счетчики 10 и 13 находятся в нулевом состоянии. На регистрах 12 и 15 хранятся коды числа n. Триггеры 1ij (i=1,…n, j=1,…n) хранят исходную информацию, при этом триггер 1ij установлен в единичное или нулевое состояние в зависимости от исходных данных.
На выходе схемы сравнения 14 будет нулевой сигнал, который подается на первый вход элемента И 17. На инверсный вход элемента И 9 подается нулевой сигнал с выхода элемента И 17. На инверсный вход элемента И 16 подается нулевой сигнал с выхода схемы сравнения 11.
После подачи пускового сигнала по входу 18 на управляющий вход элемента И 9 импульсы с выхода генератора 8 через открытый элемент И 9 начинают поступать на первый вход элемента И 16, на входы синхронизации С триггеров 1ij (i=1,…n, j=1,…n) и на вход счетчика 10, с выхода которого код поступает на первый вход схемы сравнения 11.
Сигнал с выхода элемента И 9 через открытый элемент И 16 поступает на управляющие входы элементов И 2ij (i=1,…n, j=1,…n) и элементов И 5ij (i=1,…n, j=1,…n), после чего осуществляется циклический сдвиг содержимого всех триггеров 1ij одного j-го столбца в триггеры 1 соседнего (j+1)-го справа столбца. При этом сдвиг содержимого триггеров 1ij (i=1,…n, j=1,…n) n-го столбца происходит циклически в триггеры 1ij первого столбца. Аналогичный циклический сдвиг содержимого всех триггеров 1ij одного столбца в триггеры 1ij соседнего справа столбца происходит ровно n раз, после чего на выходе схемы сравнения 11 появляется единичный сигнал.
После достижения счетчиком 10 числа n на выходе схемы сравнения 11 появляется единичный сигнал, который подается на вход сброса в ноль счетчика 10, на управляющие входы элементов И 3ij (i=1,…n, j=1,…n) и входы элементов И 7ij (i=1,…n, j=1,…n), после чего осуществляется циклический сдвиг содержимого всех триггеров 1 одной строки в триггеры 1 соседней сверху строки. При этом сдвиг содержимого триггеров 1ij (i=l,…n, j=1,…n) первой строки происходит циклически в триггеры 1ij n-ой строки.
Аналогичный циклический сдвиг содержимого всех триггеров 1ij одной строки в триггеры 1 соседней сверху строки происходит ровно n раз, после чего на выходе схемы сравнения 14 появляется единичный сигнал.
После достижения счетчиком 13 числа n на выходе схемы сравнения 14 появляется единичный сигнал, который подается на первый вход элемента И 17, а после достижения счетчиком 10 числа n на выходе схемы сравнения 11 появляется также единичный сигнал, который подается на второй вход элемента И 17. Единичный сигнал на выходе элемента И 17 подается на выход 19 (конец работы устройства) и на инверсный вход элемента И 9, после чего прекращается подача счетных импульсов с выхода генератора 8 на вход счетчика 10. Получаемые все перестановки последовательно снимаются с выходов триггеров 1in (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.
Реферат
Изобретение относится к области вычислительной техники, предназначенной для формирования в произвольной последовательности перестановок двоичных кодов. Технический результат заключается в повышении надежности работы устройства для перестановок двоичных кодов. Технический результат достигается за счет устройства для перебора перестановок двоичных кодов, содержащего первые элементы И 2, вторые элементы И 3, первые элементы ИЛИ 4, третьи элементы И 5, вторые элементы ИЛИ 6, четвертые элементы И 7, генератора тактовых импульсов 8, первого счетчика 10, первого регистра 12, второго счетчика 13, второго регистра 15, введения матрицы n*n триггеров 1(i=1,…n, j=1,…n), пятого элемента И 9, первой схемы сравнения 11, второй схемы сравнения 14, шестого элементы И 16, седьмого элемента И 17, R-входа триггера 1S-входа триггера 1, седьмого элемента И 19. 1 ил.
