Генератор перестановок

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано для решения задач автоматизированного конструирования радиоэлектронной и вычислительной аппаратуры. Цель изобретения - повышение быстродействия генератора. Генератор содержит счетчик 3, триггер 11, элементы И 6, 8, 7, элемент 4 задержки, одновибратор 5, блоки 221 - 25 формирования последовательных кодов сочетаний. Введение блоков формирования последовательных кодов сочетаний позволяет исключить перебор повторяющихся перестановок элементов. 1 з.п. ф-лы, 2 ил.

союз соВетских

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

РЕСПУБЛИК (я)5 G 06 F 15/20

ГОСУДАРСТВЕ HHblI КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОП ИСАН И Е И ЗОБ РЕТЕ НИ Я ..

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4721268/24 (22) 20,07.89 (46) 30,08.91. Бюл, № 32 (71) Таганрогский радиотехнический институт им. В.Д, Калмыкова (72) В.M. Глушань и И,Г. Ефремов (53) 681:3(088,8) (56) Авторское свидетельство СССР

¹ 922755, кл. G 06 F 15/20, 1981, Авторское свидетельство СССР

N 1190388, кл. G 06 F 15/20, 1984. („>SU(„) 1674151 À1 (54) ГЕНЕРАТОР ПЕРЕСТАНОВОК (57) Изобретение относится к области авто. матики и вычислительной техники и может быть использовано для решения задач автоматизированного конструирования радиоэлектронной и вычислительной аппаратуры.

Цель изобретения — повышение быстродействия генератора. Генератор содержит счетчик 3, триггер 11, элементы И 6, 8, 7, элемент

4 задержки, одновибратор 5, блоки 21 — 25 формирования последовательных кодов сочетаний. Введение блоков формирования последовательных кодов сочетаний позволяет исключить перебор повторяющихся перестановок элементов. 1 з.п. ф-лы, 2 ил.

1674151

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

На фиг, 1 представлена функциональ,ная схема генератора (n =- 5), на фиг. 2— функциональная схема блока формирования последовательных кодов сочетаний, Генератор содержит тактовый вход 1, блоки 21-26 формирования последовательных кодов сочетаний, счетчик 3, элемент задержки 4, одновибратор 5, элементы И 6, 7, 8, выход 9 окончания работы генератора, информационные выходы 10, триггер 11, вход 12 начальной установки, Блок 2 формирования последовательных кодов сочетаний содержит элемент задержки 13, регистр 14, узел 15 формирования параллельнь1х кодов сочетаний, элементы И 16, регистр 17, регистр сдвига 18, элементы И 19, 20, 21, ИЛИ 22.

Принцип работы устройства состоит в следующем, Пусть n — число переставляемых элементов (разрядность перестановки), i = 1„2, ..., n — индекс элементов перестановки, ml— число элементов с индексом I в перестановке. Тогда

mt== и, i=1 и ричем my =- 0 означает отсутствие элемента с индексом k, п1 > 1 -- наличие повторяющихся элементов.

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

m1

Сц, указывающих позиции повторяющихся элементов в перестановке из и элементов, Можно положить

N1= п йн-1= n — mi

1=1

Последовательность сочетаний по каждому

mj формируется в устройстве соответствующим блоком 2. Сочетание представляется

Ц-разрядным двоичным кодом, пц разрядов которого имеют единичное значение и определяют позиции элементов сочетания. Код начального сочетания содержит единицы в

mi левых позициях из Ni, код последнего сочетания — в m; правых позициях из Ni, что используется как признак окончания перебора, Так как все блски 2 имеют разрядность и, то и — Ni правых неиспользуемых разрядов должны быть заполнены единицами.

Рассмотрим алгоритм работы устройства при и = 6, m1 = 3, mz =- 1, п13 = 2, Из

5 сказанного выше следует, что в работе алгоритма будут участвовать три блока формирования сочетаний (21, 22, 2з) из шести (на фиг, 1 представлено только пять блоков 2;).

mm1 3

Соответственно, N1 = 6, С1ч1 = С 6 = 20;

mz юг=6 — 3=3, CN2 = С з=3;

3 2

N3 = 6 — (3 + 1) = 2, Сыз = C2 = 1.

Общее число неповторяющихся перестановок из шести элементов при указанных условиях оказывается равным

С6 Сз С 2=20 3 1=60, Формирование перестановки осуществляется следующим образом.

Просматриваем первый разряд первого сочетания (блок 21), Если он содержит "1", то в первую позицию перестановки помещаем элемент с номером 1, если содержит "0", то переходим к первому разряду второго сочетания (блок 2г), Если он содержит "1", то в первую позицию перестановки помещаем элемент с номером 2, если содержит "0", то переходим к первому разряду третьего сочетания и т.д, Вторая позиция перестановки заполняется аналогичным образом, но при этом из просмотра исключаются ранее просмотренные разряды всех сочетаний при заполнении первой позиции перестановки, и т,д. Исходную перестановку следует записать в таком виде

1 1 1 2 3 3

Затем блоком 21 формируется новое сочетание, а второй и третий блоки сохраняют прежние состояния. Получение нового сочетания блоком 22 происходит лишь после перебора всех сочетаний первым блоком.

Получение нового сочетания в блоке 2з возможно лишь после перебора всех сочетаний

45 первым и вторым блоками, и т.д.

Таким образом, двадцати первым сочетанияМ блока 21 и неизменным (исходным) сочетаниям второго и третьего блоков будут соответствовать перестановки (в левом

50 столбце — сочетания, в правом — перестановки):

1,111000 111233

2,110100 112133

3,101100 121133

4011100 211133

5.110010 112313

6.101010 121313

7011010 211313

8.100110 123113

9010110 213113

1674151

10001 1.10 231113 . 11.110001 112331

12.1 0 1 0 0 1 1 2 1 3 3 1

13011001 211331

14.100101 123131 5

15010101 213131

16001101 231131

17.100011 123311

18010011 213311

19001011 231344 10

20000111 233111.

При появлении единичной комбинации в правых разрядах первого сочетания дается разрешение на формирование нового сочетания в блоке 2г и восстановление ис- 15 ходного состояния в первом блоке. При получении 21-й перестановки в блоках 21, 2г, 2з будут установлены такие коды:

1. 1 1 1 0 0 0 2.0 1 0 3. 1 1, а сама перестановка будет иметь вид — 1 1 1 20

32 3.

Следующие 20 перестановок формируются аналогично первым 20-ти, При получении 41-й перестановки будут зафиксированы коды сочетаний: 25

1.111000 2.001 3.11, а перестановка будет иметь вид — 1 1 1 3 3

2. На 60-й перестановке будут зафиксированы коды сочетаний:

1.000111 2,001 3.11, 30 а сама перестановка будет такой: 3 3 2 1 1 1.

Появление всех единиц в правых разрядах сочетаний по всем блокам (2f, 2г, 2з) свидетельствует об окончании работы алгоритма. Приведенный алгоритм позволяет 35 получить перебор всех возможных перестановок с любым количеством повторяющихся элементов без повторяющихся перестановок в последовательности, Формирование перестановок устройст- 40 вом осуществляется в последовательновременной форме . Это значит, что последовательность появления единиц на выходах 10 устройства определяет позиции элементов, а номер элемента определяется 45 номером выхода устройства, на котором появляется единичный сигнал.

Получение новой перестановки состоит из двух этапов; формирование новых внутренних состояний блоков 2 и передача их 50 через регистры сдвига 18 на выходы 10 устройства. При этом формирование новых внутренних состояний блоков 2 осуществляется за один такт, а передача состояний на выходы 10 устройства через регистры 18 за 55 и тактов.

При поступлении тактовых импульсов на входы регистров 18 информация в них сдвигается влево, причем появление единицы на первом разряде одного регистров 18 запрещает поступление тактовых импульсов на все остальные регистры 18, стоящие правее этого регистра (фиг. 1), Записывая единицы в правые разряды любого из блоков 2 до начала его работы, можно изменять количество его разрядов, участвующих в работе. В этом случае единицы в правых разрядах будут фиктивными, не участвующими в сочетаниях, и их попадание на входы сдвиговых регистров 18 следует исключить. Это осуществляется с помощью регистров 17.

В нижние разряды этих регистров записываются нулевые потенциалы, количество которых равно количеству единиц, установленных в правые разряды соответствующего блока 2. Поступая на вторые входы элементов И 16, они запрещают прохождение через них информации. Модуль счетчика 3 равен числу элементов (c учетом повторений), участвующих в перестановках.

Работу устройства рассмотрим на примере 5-ти переставляемых элементов, два из которых имеют номер 1. До начала работы устройства нужно установить разрядность кодов сочетаний и записать в них соответстуующую информацию. Блок 21 будет формировать сочетания из множества

С 5 = 10, поэтому в первый регистр 14 нужно г записать код 11000. Второй блок будет формировать сочетания из множества Сз = 3, поэтому число его разрядов нужно уменьшить с 5до З-х, записывая две единицы в его правые разряды, Во второй регистр 14 в результате должен быть записан код 10011.

Третий блок будет формировать сочетания из множества Сг = 2, а число его разрядов

1 нужно уменьшить с 5 до 2-х путем записи трех "1" в его правые разряды. Поэтому в третий регистр 14 нужно записать код

10111. Четвертый блок должен формировать сочетания из множества C f = 1, а число

f его разрядов нужно уменьшить с 5 до 1, Поэтому в четвертый блок нужно записать код 11111. Так как элемент с номером 5 не используется в перестановках, то в пятый блок следует записать все "1", т.е. в пятый регистр 14 нужно записать код 11111. В нижние разряды регистров 17 записываются нули, количество которых равно количе1 ству единиц, записанных в правые разряды регистров 14. Поэтому в первый регистр

17 записывается код 11111, во второй регистр 17 записывается код 11100, в третий- — 11000, в четвертый — 10000, в пятый—

00000. Триггер 11 путем подачи на вход 12 единичного сигнала устанавливается в единичное сОстояние.

Первый тактовый импульс, поступая с тактового входа 1 устройства на счетчик 3, вызывает появление на его выходе единич20

50 ного сигнала, который через открытый элемент И 19, элементы ИЛИ 22 и элементы задержки 13 всех блоков 2 поступает и вызывает запись в них информации с регистров 14. В (1 — 5)-м блоках 2 будут записаны соответствено коды: 11000; 10011; 10111;

11111; 11111, Кроме того, "-адержанный пер-. вый тактовый импульс, пройдя элемент задержки 4, сбросит триггер 11 и, поступая на вход "Запись" регистров сдвига 18 всех блоков 2, переписывает в них информацию, поступающую через элементы И 16. Так в регистр 18 первого блока 2 будет записан код 11000, в регистр 18 второго блока 2 — код

10000, в регистр 18 третьего блока 2 — код

10000, в регистр 18 четвер ого блока 2 — код

10000, а в регистр-18 пятого блока 2 — код

00000. Единичный сигнал- с последовательного выхода регистра 18 блока 21 (первая позиция сочетания) проходит через первый элемент И 8 на выход 10 устройства, что соответствует появлению в первой позиции перестановки элемента с номером один, Этим же сигналом запрещается прохождение информации через другие элементы И8.

Второй тактовый импульс, отформированный одновибратором 5,по амплитуде и длительности, поступиг через первый элемент И 6 на сдвигающий вход регистра 18 в блоке 2I. Остальные элементы И 6 закрыты единичным сигналом с информационного выхода блока 21 (первая позиция сочетания), В результате сдвига в регистре 18 на информационном выходе блока 2> появится единица, соответствующая второй позиции сочетания, а на выходе 10 первого элемента

И 8 — сигнал, соответствующий элементу с номером 1 на второй позиции перестановки, Третий тактовый импульс. вызовет сдвиг только в первом регистре 18 и появление нуля на информационном выходе блока 2ъ

Состояние остальных блоков 2 не изменится. Теперь старшей окажется единица на информационном выходе блока 22 (первая позиция сочетания), и сигнал появится на выходе 10 второго элемента И 8 — элемент с номером 2 на третьей позиции перестановки.

Четвертый тактовый импульс вызовет сдвиг в блоках 21, 22 (открыты первый и второй элементы И 6), и т,д.

На шестом такте появигся сигнал переполнения счетчика 3, который, пройдя через элемент И 20 на синхронизирующий вход узла 15 в блс ке 21, вызовет перехоц к новому сочетанию, Через время, равное задержке на элементе 4, новое сочетание перег1ишется в регистр 18. Состоянле остальных блоков 2 остается неизменным, До перехода к последнему сочетанию в блоке 2> работа устройства выполняется аналогично. При обработке последнего сочетания на выходе узла 15 появляется сигнал окончания перебора, запирающий элемент И 20 и отпирающий И 21. Очередной сигнал переполнения счетчика 3 проходлт через элементы И 21, ИЛИ 22, блока 21 и через элемент И 20 блока 2 на вход синхронизации узла 15, вызывая переход к новому сочетанию в блоке 22.

Через время, равное задержке элемента И 13, в блоке 21 восстанавливается начальный код сочетания, хранимый регистром 14.

Аналогично на последующих этапах подключаются к работе остальные блоки 2.

Сигналы окончания работы блоков 2 объединяются элементом И 7 в сигнал окончания работы устройства на выходе 9, Формула изобретения

1. Генератор перестановок, содержащий счетчик, триггер, элемент задержки, две группы по и эгементов И (и — число переставляемых элементов), о т л и ч а юшийся тем, что, с целью повышения быстродействия, он содержит и блоков формирования последовательных кодов сочетаний, одновибратор и элемент И, причем счетный вход счетчика и вход одновибратора объединены с тактовым входом генератора, выход переполнения счетчика соединен с входом элемента задержки и входом синхронизации перебора сочетаний первого блока формирования последовательных кодов сочетаний, выход элемента задержки соединен с.нулевым входом триггера и входом синхронизации начальной установки разрядов последовательного кода каждого блока формирования последовательных кодов сочетаний, выхододновибратора соединен с прямым входом каждого элемента И первой группы, выход I-го (i = 1, n) элемента

И первой группы соединен со сдвигающим входом i-го блока формирования последовательных кодов сочетаний, информационный выход J-го (J = 1, 1, и — 1) блока формирования последовательных кодов сочетаний соединен с j-м инверсным входом k-ro (k = j+ 1, и) элемента И первой и второй групп, информационный выход I-го блока формирования последовательных кодов сочетаний соединен с прямым входом f ãо элемента И второй группы, выходы элементов И второй группы являются информационными выходами генератора, единичный вход триггера являетс.я входом начальной установки генератора, выход триггера соединен с входами началь1б74151

10 ной установки всех блоков формирования последовательных кодов сочетаний, выход начала перебора сочетаний J-ro блока формирования последовательных кодов сочетаний соединен с входом синхронизации перебора сочетаний (J + 1)-ro блока формирования последовательных кодов сочетаний, выход окончания перебора сочетаний

L-ro блока формирования последовательных кодов сочетаний соединен с i-м входом элемента И, выход элемента И является выхоом окончания работы генератора, 2, Генераторпоп.1, отличающийс я тем, что каждый блок формирования последовательных кодов сочетаний содержит узел формирования параллельных кодов сочетаний, два регистра, регистр сдвига, группу элементов И, три элемента И, элемент ИЛИ, элемент задержки, причем входы первого и второго регистров являются входами задания числа элементов в сочетании и числа разрядов в коде сочетания соответствующего блока формирования последовательных кодов сочетаний, выход первого регистра соединен с информационным входом узла формирования параллельных кодов сочетаний, информационные выходы которого и второго регистра поразрядно через соответствующие элементы И группы подключены к информационному параллельному входу регистра сдвига, последовательный выход которого является информационным выходом соответствующего блока формирования последовательных кодов сочетаний, первые входы nepeoro и второго элементов И, а также прямой вход третьего элемента И объединены и

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

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

1674151

Составитель В. Байков

Техред M.Moðãåíòàë Корректор Н. Король редактор К. Крупкина

Производственно издательский комбинат "Патенг", г. Ужгород, ул.Гагарина, 101

Заказ 2924 Тираж 387 Подписное

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

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