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

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

 

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

Известно устройство [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.

Устройство для перебора перестановок двоичных кодов, содержащее первые элементы И 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.



 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники. Технический результат заключается в расширении функциональных возможностей.

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

Изобретение относится к области вычислительной техники. Технический результат заключается в повышении точности определения результата доступности к этапу обработки для объекта обработки.

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники, предназначенной для формирования в произвольной последовательности перестановок двоичных кодов. Технический результат заключается в повышении надежности работы устройства для перестановок двоичных кодов. Технический результат достигается за счет устройства для перебора перестановок двоичных кодов, содержащего первые элементы И 2ij, вторые элементы И 3ij, первые элементы ИЛИ 4ij, третьи элементы И 5ij, вторые элементы ИЛИ 6ij, четвертые элементы И 7ij, генератора тактовых импульсов 8, первого счетчика 10, первого регистра 12, второго счетчика 13, второго регистра 15, введения матрицы n*n триггеров 1ij, пятого элемента И 9, первой схемы сравнения 11, второй схемы сравнения 14, шестого элементы И 16, седьмого элемента И 17, R-входа триггера 1i, S-входа триггера 1i, седьмого элемента И 19. 1 ил.

Наверх