УСТРОЙСТВО ДЛЯ ПЕРЕБОРА ПЕРЕСТАНОВОК

Полезная модель относится к области вычислительной техники и предназначено для решения комбинаторных задач, а также может быть использовано для решения задач целочисленного линейного программирования и генерации кодовых последовательностей.
Известно устройство для перебора перестановок (RU №2012054 C1, МПК G06F 15/419, G06F 15/20, заявлено 01.07.1991, опубликовано 30.04.1994), содержащее две группы из n регистров (n - максимальная длина генерируемых перестановок), блок выбора минимального числа, два дешифратора, два мультипликатора, две группы элемента ИЛИ, группу из n сумматоров, n блоков деления, три группы элементов задержки и группу элементов И. Устройство реализует процедуру преобразования исходного числа m в однозначно соответствующую ему перестановку исходных, предварительно пронумерованных числами 1, 2, …, k элементов.
Недостатками данного устройства является большой объем оборудования и низкое быстродействие.
Известно устройство для перебора перестановок (SU №1410056 A1, G06F 15/20, заявлено 03.11.1986, опубликовано 15.07.1988, Бюл. №26), содержащее блок управления для формирования множества чисел в соответствии с выбранным вариантом перестановки и шагом работы, который содержит n регистров (n - длина перестановок), n ключей, элемент задержки, дешифратор и схему выбора минимального числа, и блок декодирования предназначенный для преобразования заданного натурального числа в соответствующую ему перестановку, который содержит регистр, две группы по n регистров, n блоков деления, n сумматоров, две группы по n элементов задержек, два элемента ИЛИ, группу из n ключей, а также вход пуска, информационный вход и группу из n информационных выходов.
Недостатками данного устройства является большой объем оборудования и низкое быстродействие.
Наиболее близким устройством того же назначения к заявленной полезной модели по совокупности признаков является, принятое за прототип, устройство для перебора перестановок (SU №1397933 A, G06F 15/20, заявлено 04.11.1986, опубликовано 23.05.1988, Бюл. №19), содержащее n регистров (n - число переставляемых кодов), (n-1) счетчиков, две группы из (n-2) элементов И, две группы элементов ИЛИ, три элемента задержки, элемент И, элемент ИЛИ, группу из (n-1) триггеров, группу из (n-1) элементов запрета, четыре группы по 2m элементов И (m - разрядность переставляемых кодов), четыре группы по m элементов ИЛИ, тактовый вход устройства, вход начальной установки, n выходов устройства по m разрядов и выход окончания работы устройства, причем выход переноса каждого счетчика, кроме последнего, соединен со счетным входом последующего счетчика.
К причинам, препятствующим достижению указанного ниже технического результата, относятся большие аппаратные затраты и связи между ними, что приводит к снижению быстродействия, уменьшению надежности и усложнению устройства.
Техническим результатом изобретения является увеличение быстродействия устройства, уменьшение аппаратных затрат и повышение надежности устройства.
Указанный технический результат при осуществлении полезной модели достигается тем, что в устройство для перебора перестановок содержащее n регистров (n - число переставляемых кодов), (n-1) счетчиков, группу из (n-2) элементов И, первую группу из (n-3) элементов ИЛИ, вторую группу из n элементов ИЛИ, тактовый вход устройства, вход начальной установки, n выходов устройства по m разрядов (m - разрядность переставляемых кодов) и выход окончания работы устройства,
дополнительно введены группа из (n-1) двухвходовых мультиплексоров по m разрядов каждый, триггер разрешения, триггер окончания работы, вход пуска устройства, входная m разрядная шина данных и вход разрешения записи,
причем каждый из n регистров содержит по m разрядов, выходы n регистров являются n выходами устройства, у каждого i-го счетчика модуль счета (i+1) (i=1, 2, …,(n-1)),
выход переноса каждого счетчика, кроме последнего, соединен с входом разрешения последующего счетчика, а также соединен со вторыми инверсными входами соответствующих (n-2) элементов И группы, первые входы со второго до (n-2) элементов И группы соединены соответственно с выходами переносов с первого до (n-3) счетчиков,
выходы (n-3) элементов И группы, кроме последнего, соединены с первыми входами соответствующих элементов ИЛИ первой группы,
выход каждого нечетного элемента И группы, начиная с третьего, соединен с соответствующими входами предыдущих нечетных элементов ИЛИ первой группы, выход каждого четного элемента И группы, начиная с четвертого, соединен с соответствующими входами предыдущих четных элементов ИЛИ первой группы, выход предпоследнего (n-2) счетчика соединен с соответствующими входами предыдущих нечетных элементов ИЛИ первой группы при четном значении числа n или с соответствующими входами предыдущих четных элементов ИЛИ первой группы при нечетном значении числа n,
выходы переноса каждого счетчика, кроме последнего, также соединены с первыми входами соответствующих элементов ИЛИ второй группы, начиная с третьего, первый вход первого элемента ИЛИ второй группы соединен с выходом первого элемента ИЛИ первой группы, первый вход второго элемента ИЛИ второй группы соединен с выходом триггера разрешения, который также соединен с первым входом первого элемента И группы, а также входом разрешения первого счетчика,
вторые входы каждого элемента ИЛИ второй группы соединены с входом разрешения записи, который также соединен с адресным входом первого мультиплексора группы, выходы каждого элемента ИЛИ второй группы соединены с входами разрешения соответствующих n регистров, информационные входы данных (n-1) регистров, кроме последнего, соединены с соответствующими выходами одноименных разрядов мультиплексоров группы, информационные входы данных последнего n-го регистра соединены с соответствующими выходами одноименных разрядов предпоследнего (n-1)-го регистра,
входная m разрядная шина данных соединена со вторыми входами одноименных разрядов первого мультиплексора группы, первые входы первого мультиплексора группы соединены с выходами одноименных разрядов второго регистра,
первые входы мультиплексоров группы, начиная со второго, соединены с выходами одноименных разрядов соответствующих предыдущих (n-2) регистров, кроме двух последних, вторые входы мультиплексоров группы, начиная со второго, соединены с одноименными разрядами соответствующих последующих (n-2) регистров, начиная с третьего,
выходы (n-4) элементов ИЛИ первой группы, кроме первого, соединены с адресными входами соответствующих (n-4) мультиплексоров группы, начиная со второго кроме двух последних, выход последнего (n-2)-го элемента И группы также соединен с адресными входами предпоследнего (n-2)-го мультиплексора группы, а адресные входы последнего (n-1)-го мультиплексора группы соединены с выходом переноса предпоследнего (n-2)-го счетчика,
тактовый вход устройства соединен с входами синхронизации n регистров, (n-1) счетчика, триггера разрешения и триггера окончания работы,
вход начальной установки устройства соединен с входами синхронной установки в нулевое состояние вторыми входами триггера разрешения и триггера окончания работы, вторыми входами (n-1) счетчиков,
вход пуска устройства соединен с третьим входом синхронной установки в единичное состояние триггера разрешения,
выход переноса последнего (n-1)-го счетчика соединен с первым входом синхронной установки в нулевое состояние триггера разрешения и с первым входом синхронной установки в единичное состояние триггера окончания работы, выход которого является выходом окончания работы устройства.
На фиг. 1 представлена схема предлагаемого устройства для перебора перестановок для случая семи переставляемых кодов (элементов) при n=7.
На фиг. 1 приняты следующие обозначения:
1
2
6
1, 1, …, 1 - (n-1) счетчиков,
1
2
5
2, 2, …, 2 - группа из (n-2) элементов И,
1
2
4
3, 3, …, 3 - первая группа из (n-3) элементов ИЛИ,
1
2
6
4, 4, …, 4 - группа из (n-2) двухвходовых мультиплексоров по m разрядов каждый,
1
2
7
5, 5, …, 5 - вторая группа из n элементов ИЛИ,
1
2
7
6, 6, ..., 6 - n регистров m разрядов каждый,
1
2
7
7, 7, ..., 7 - n выходов устройства по m разрядов каждый,
8 - триггер разрешения,
9 - триггер окончания работы,
10 - входная m разрядная шина данных,
11 - вход разрешения записи,
12 - вход пуска устройства,
13 - вход начальной установки,
14 - тактовый вход устройства,
15 - выход окончания работы устройства.
1
2
6
Вход начальной установки устройства 13 соединен с входами синхронной установки в нулевое состояние вторыми входами триггера разрешения 8 и триггера окончания работы 9, вторыми входами (n-1) счетчиков 1, 1, …, 1.
1
2
7
1
2
6
Тактовый вход устройства 14 соединен с входами синхронизации n регистров 7, 7, …, 7, (n-1) счетчика 1, 1, …, 1, триггера разрешения 8 и триггера окончания работы 9.
Вход пуска устройства 12 соединен с третьим входом синхронной установки в единичное состояние триггера разрешения 8.
1
2
6
6
1
2
7
1
2
7
У каждого i-го счетчика модуль счета (i+1) (i=1, 2, …, (n-1)). При n=7 для первого счетчика Сч1 (1) - модуль M=2, второго счетчика Сч2 (1) - M=3, …,  шестого счетчика Сч (1) - M=7. Выходы n регистров 6, 6, …, 6 являются n выходами устройства 7, 7, …, 7 по m разрядов каждый.
1
2
5
6
2
6
1
2
5
2
5
1
2
4
Выход переноса каждого счетчика 1, 1, …, 1, кроме последнего 1, соединен с входом разрешения последующего счетчика 1, …, 1, а также соединен со вторыми инверсными входами соответствующих (n-2) элементов И группы 2, 2, …, 2, первые входы со второго до (n-2) элементов И группы 2, …, 2 соединены соответственно с выходами переносов с первого до (n-3) счетчиков 1, 1, …, 1.
1
2
4
1
2
4
3
4
5
Выходы (n-3) элементов И группы 2, 2, …, 2, кроме последнего 2$, соединены с первыми входами соответствующих элементов ИЛИ первой группы 3, 3, …, 3. Выход каждого нечетного элемента И группы 2, начиная с третьего 2, соединен с соответствующими входами предыдущих нечетных элементов ИЛИ первой группы 3, выход каждого четного элемента И группы 2, начиная с четвертого 2, соединен с соответствующими входами предыдущих четных элементов ИЛИ группы. Выход предпоследнего (n-2) счетчика 1 соединен с соответствующими входами предыдущих нечетных элементов ИЛИ первой группы 3 при четном значении числа n или с соответствующими входами предыдущих четных элементов ИЛИ первой группы 3 при нечетном значении числа n.
1
2
5
6
3
7
1
1
2
1
Выходы переноса каждого счетчика 1, 1, …, 1, кроме последнего 1, также соединены с первыми входами соответствующих элементов ИЛИ второй группы 5, …, 5, начиная с третьего. Первый вход первого элемента ИЛИ второй группы 5 соединен с выходом первого элемента ИЛИ первой группы 3. Первый вход второго элемента ИЛИ второй группы 5 соединен с выходом триггера разрешения 8, который также соединен с первым входом первого элемента И группы 2, а также входом разрешения первого счетчика 1.
1
2
7
1
1
2
7
1
2
7
1
2
6
7
1
2
6
6
Вторые входы каждого элемента ИЛИ второй группы 5, 5, …, 5 соединены с входом разрешения записи 11, который также соединен с адресным входом первого мультиплексора группы 4. Выходы каждого элемента ИЛИ второй группы 5, 5, …, 5 соединены с первыми входами разрешения соответствующих n регистров 6, 6, …, 6. Информационные входы данных (n-1) регистров 6, 6, …, 6, кроме последнего регистра 6, соединены с соответствующими выходами одноименных разрядов мультиплексоров группы 4, 4, …, 4. Информационные входы данных последнего n-го регистра 67 соединены с соответствующими выходами одноименных разрядов предпоследнего (n-1)-го регистра 6.
1
1
2
Входная m разрядная шина данных 10 соединена со вторыми входами одноименных разрядов первого мультиплексора группы 4, первые входы первого мультиплексора группы 4 соединены с выходами одноименных разрядов второго регистра 6.
2
6
1
2
5
2
6
3
7
Первые входы мультиплексоров группы 4, …, 4, начиная со второго, соединены с выходами одноименных разрядов соответствующих предыдущих (n-2) регистров 6, 6, …, 6, кроме двух последних, вторые входы мультиплексоров группы 4, …, 4, начиная со второго, соединены с одноименными разрядами соответствующих последующих (n-2) регистров 6, …, 6, начиная с третьего.
2
4
2
4
5
6
5
5
6
5
Выходы (n-4) элементов ИЛИ первой группы 3, …, 3, кроме первого, соединены с адресными входами соответствующих (n-4) мультиплексоров группы 4, …, 4, начиная со второго и кроме двух последних 4 и 4, выход последнего (n-2)-го элемента И группы 2 также соединен с адресными входами предпоследнего (n-2)-го мультиплексора группы 4, а адресные входы последнего (n-1)-го мультиплексора группы 4 соединены с выходом переноса предпоследнего (n-2)-го счетчика 1.
6
Выход переноса последнего (n-1)-го счетчика 1 соединен с первым входом синхронной установки в нулевое состояние триггера разрешения 8 и с первым входом синхронной установки в единичное состояние триггера окончания работы 9, выход которого является выходом окончания работы устройства 15.
Принцип работы устройства состоит в следующем.
Каждая очередная перестановка получается из предыдущей перестановки путем обмена элементами (кодами) между соседними элементами, причем последовательность обмена изменяется по строго определенной закономерности.
1
2
3
4
2
3
1
Рассмотрим алгоритм работы устройства на примере перестановок четырех элементов (кодов) при n=4. Предположим, что элементы перестановок соответствуют кодам 1, 2, 3, 4, которые записываются в четыре первых регистра 6, 6, 6, 6. Тогда для данных четырех элементов получим 4!=24 перестановки, приведенные в таблице 1. Стрелками показаны регистры, между которыми проводится обмен кодами для получения очередной перестановки. Кроме того, в таблице 1 приведены состояния счетчиков второго Сч2 (1) по модулю M=3 и третьего Сч3 (1) по модулю М=4, а также значения сигналов переносов трех счетчиков: Сч1 (1) перенос П2, Сч2 - П6, Сч3 - П24.
1
2
1
2
3
1
1
2
1
2
3
4
Из приведенной в таблице 1 последовательности перестановок следует, что в каждых первых пяти из шести перестановок обмен между первым 6 и вторым регистрами 6 проводится через одну перестановку, при нулевом сигнале переноса П2=0 младшего первого счетчика Сч1 (1), а обмен между вторым 6 и третьим 6 регистрами проводится через одну перестановку при единичном сигнале переноса П2=1 младшего первого счетчика Сч1 (1). В каждой шестой перестановке при единичном сигнале переноса П2=1 младшего первого счетчика Сч1 (1) и П6=1 второго счетчика Сч2 (1) проводится одновременный обмен между двумя парами регистров: первым 6 - вторым 6 и третьим 6 - четвертым 6. В 24-й перестановке при n=4 формируется единичный сигнал ГОТОВ окончания перестановок.
j
j+1
j-1
j
j-1
1
Из приведенного примера следует, что обмен регистра 6 (j=2, …, n) с последующим регистром 6 выполняется при единичном сигнале переноса П=1 соответствующего счетчика 1 и при нулевом сигнале переноса П=0 следующего счетчика 1, а также проводится обмен между соседними предыдущими парами младших регистров, начиная с регистра 6. Если нет пары для младшего регистра 6, то его состояние не меняется.
4
5
3
4
3
2
1
Данное правило может быть экстраполировано на большее число переставляемых элементов n>4. В таблице 2 приведена последовательность перестановок для семи элементов n=7, при этом общее число перестановок составит 7!=5040. Из таблицы 2 видно, что обмен между четвертым 6 и пятым 6 регистрами проводится через 24 перестановки, при единичном сигнале переноса П24=1 третьего счетчика Сч3 (1) и нулевом сигнале переноса П120=0 четвертого счетчика Сч4 (1) и одновременно проводится обмен между третьим 6 и вторым 6 регистрами, а состояние первого регистра 6 сохраняется.
Аналогично для каждой 120-й перестановки при переносах П120=1 и П720=0 будет проводиться обмен между шестым и пятым, четвертым и третьим, вторым и первым регистрами. Аналогично для каждой 720-й перестановки при переносах П720=1 и П5040=0 будет проводиться обмен между седьмым и шестым, пятым и четвертым, третьим и вторым регистрами, и сохранением состояния первого регистра. В 5040-й перестановке при n=7 формируется единичный сигнал ГОТОВ окончания перестановок и значения всех регистров возвращаются к первой перестановке.
2
1
3
Из таблиц 1 и 2 видно, что на каждом шаге в обмене участвует второй регистр 6, который обменивается или с первым регистром 6, или с третьим регистром 6.
Предлагаемое устройство для перебора перестановок работает следующим образом.
1
2
6
При подаче сигнала на вход начальной установки устройства 13 в нулевое состояние устанавливаются триггер разрешения 8, триггер окончания работы 9, все счетчики 1, 1, …, 1.
Тактовые импульсы постоянно поступают на входы синхронизации счетчиков, регистров и триггеров, режимы работы которых задаются сигналами на соответствующих входах управления.
7
6
1
1
7
1
2
6
7
6
1
7
6
1
Перед началом работы устройства подается единичный сигнал на вход разрешения записи 11 и на входной m разрядной шине данных 10 последовательно задаются значения переставляемых элементов (кодов), которые будут записаны в регистры 6, 6, …, 6. Значения кодов задаются в порядке записи со старшего регистра, например, коды 7, 6, 5, 4, 3, 2, 1, так как запись в регистры выполняется последовательным сдвигом данных между регистрами от первого 6 к последнему 6. Данный сдвиг осуществляется при последовательном задании кодов исходной перестановки на вторые входы первого мультиплексора 4, так как на его адресном входе установлен единичный сигнал с входа 11, и через первые входы остальных мультиплексоров 4, …, 4, на адресных входах которых установлен нулевой сигнал. Запись в регистры выполняется за n тактов, в течение которых на входе разрешения записи 11 удерживается единичный сигнал и в каждом из тактов на входной шине данных 10 устанавливается значение кода одного из переставляемых элементов. Например, в схеме устройства при n=7, приведенной на фиг. 1, через семь тактов на регистрах 6, 6, …, 6 и выходах устройства 7, 7, …, 7 будут зафиксированы коды 7, 6, 5, 4, 3, 2, 1.
1
1
1
1
1
2
1
2
2
1
2
1
2
7
6
1
1
1
1
3
3
2
3
2
2
2
2
3
Работа устройства начинается после подачи сигнала ПУСК на вход устройства 12, по которому синхронно с тактовым импульсом 14 устанавливаются в единичное состояние выход триггера разрешения 8, который соединен с входом разрешения счета первого счетчика 1. При этом единичный сигнал с выхода триггера управления 8 через элемент И 2, элемент ИЛИ 3, элемент ИЛИ 5 разрешает запись в первый регистр 6 информации, поступающей из второго регистра 6 через первые входы первого мультиплексора 4, а также через элемент ИЛИ 5 запись во второй регистр 6 информации поступающей из первого регистра 6 через первые входы второго мультиплексора 4. Обмен кодами между первым 6 и вторым 6 регистрами выполняется по фронту первого тактового импульса 14 и на выходах устройства 7, 7, …, 7 будут установлены значения второй перестановки 7, 6, 5, 4, 3, 1, 2. Одновременно срабатывает первый счетчик 1, модуль которого М=2, поэтому на выходе переноса установится единичный сигнал П2=1, по которому будет установлен нулевой сигнал на выходе элемента И 2 и который будет также на входе разрешения записи в первый регистр 6, а также через элемент ИЛИ 5 устанавливается единичный сигнал на входе разрешения записи в третий регистр 6 информации, поступающей из второго регистра 6 через первые входы третьего мультиплексора 4, при этом через элемент И 2, элемент ИЛИ 3 на адресных входах второго мультиплексора 4 будет установлен единичный сигнал, по которому со вторых входов на информационные входы второго регистра 6 поступает код с третьего регистра 6.
2
2
2
1
1
2
На входе разрешения записи во второй регистр 6 в течение всего времени работы устройства будет установлен единичный сигнал с триггера разрешения 8 через второй элемент ИЛИ 5, таким образом, разрешается обмен во втором регистре 6 на каждом шаге по фронту тактовых сигналов 14. На адресном входе первого мультиплексора 4 в течение всего времени работы устройства будет установлен нулевой сигнал, что обеспечивает передачу на информационные входы первого регистра 6 значений со второго регистра 6.
2
3
7
6
1
По фронту второго тактового импульса проводится обмен содержимым между вторым 6 и третьим 6 регистрами и на выходах устройства 7, 7, …, 7 будут зафиксированы коды 7, 6, 5, 4, 1, 3, 2.
1
2
1
3
1
1
3
3
4
4
1
2
4
2
3
3
3
4
После пятого тактового импульса 14 единичные сигналы будут установлены на выходах переносов П2=1 первого счетчика 1, и П6=1 второго счетчика 1, по которым единичные значения будут установлены на входе разрешения записи в первый регистр 6 через элементы И 2, ИЛИ 3, ИЛИ 5, на входе разрешения записи в третий регистр 6 через элемент ИЛИ 5, на входе разрешения записи в четвертый регистр 6 через элемент ИЛИ 5. При этом на адресных входах первого 4, второго 4 и четвертого 4 мультиплексоров будут установлены нулевые сигналы и, следовательно, информация передается с первых входов мультиплексоров. Одновременно единичные сигналы будут установлены на адресных входах второго мультиплексора 4 через элементы И 2, ИЛИ 3 и поэтому информация на информационные входы третьего регистра 6 будет передана с четвертого регистра 6.
4
3
2
1
7
6
1
По фронту шестого тактового импульса 14 будет проведен обмен между четвертым 6 и третьим 6, вторым 6 и первым 6 регистрами и на выходах устройства 7, 7, …, 7 будут зафиксированы коды 7, 6, 5, 2, 4, 1, 3.
1
2
3
5
4
3
2
7
6
1
Аналогично после двадцать третьего импульса 14 единичные сигналы будут установлены на выходах переносов П2=1 первого счетчика 1, П6=1 второго счетчика 1 и П24 третьего счетчика 1, по которым будет подготовлен обмен между пятым 6 и четвертым 6, третьим 6 и вторым 6 регистрами. Обмен будет проведен по фронту 24-го тактового импульса и на выходах устройства 7, 7, …, 7 будут зафиксированы коды 7, 6, 3, 5, 1, 4, 2.
В следующих циклах обмен между регистрами будет выполняться в соответствии с рассмотренным выше алгоритмом.
7
6
1
7
6
1
После формирования на выходах переноса всех счетчиков единичного сигнала, перенос последнего (n-1)-го счетчика П5040=1 поступает на синхронные вход установки в нулевое состояние триггера разрешения 8 и вход установки в единичное состояние триггера окончания работы 9. Поэтому по фронту тактового импульса 14 триггер разрешения работы 8 устанавливается в нулевое состояние, а триггер окончания работы 9 в единичное состояние и на выходе 15 формируется сигнал ГОТОВ об окончании работы. При этом на всех регистрах 6, 6, …, 6 и на выходах устройства 7, 7, …, 7 будут установлены значение кодов первой перестановки 7, 6, 5, 4, 3, 2, 1.
В предлагаемом устройстве организована синхронная работа счетчиков, в отличие от организации в прототипе асинхронного переноса между счетчиками, а также исключены элементы задержки, что позволило увеличить быстродействие предлагаемого устройства. Кроме того, в предлагаемом устройстве организована начальная запись произвольных m-разрядных кодов переставляемых элементов.
Таким образом, вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство обеспечивает перебор перестановок для n элементов, обладает регулярностью узлов и связей, практически однородной структурой, при этом упрощается конструкция и, следовательно, устройство соответствует заявляемому техническому результату - сокращение аппаратных затрат, увеличение быстродействия и повышение надежности.