Устройство для нумерации перестановок

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано, например, в вычислительных машинах, решающих комбинаторные задачи, в специализированных моделирующих устройствах для решения задач синтеза сетей связи, транспортных сетей, вычисления характеристик графов и др. Цель изобретения - повышение быстродействия и упрощение устройства. Устройство содержит регистр сдвига 3, дешифратор 2, элементы ИЛИ 4,5, И 9, триггеры 10, счетчики 11, блоки 15,16 умножения на константу, сумматор 17. Повышение быстродействия достигается параллельной обработкой разрядов. Упрощение конструкции обусловлено исключением ряда блоков : (схемы сравнения, коммутатора, кольцевых регистров, генераторов импульсов) в конструкции прототипа. 1 ил.

СО10Э СОВЕТСКИХ

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

РЕСПУБЛИК щ)5 G06F7!

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

C ф

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЭОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ П4НТ СССР (21) 4635616/24-24 (22) 10.0).89, (46) 23.12.90. Вюл. № 47

1(72) Ю.П.Зубков (33) 681.3 (088.8) ,(56) Авторское свидетельство СССР № 888107, кл. G 06 F 7/38, 1980.

Авторское свидетельство. СССР

9 1300460, кл. G 06 F 7/38, 1985. (54) УСТРОЙСТВО ДЛЯ НУМЕРАЦИИ ПЕРЕСТАНОВОК (57) Изобретение относится к автома тике и вычислительной технике и может быть использовано, например, в . вычислительных машинах, решающих комбинаторные задачи, в специализированных моделирующих устройствах для ре„„SU „„1615702

2 шения задач синтеза сетей связи, транспортньгк сетей, вычисления характеристик графов и др. Цель изобретения— повышение быстродействия и упрощение устройства. Устройство содержит регистр сдвига 3, дешифратор 2, элементы ИЛИ 4, 5, И 9, триггеры IQ, счетчики 11, блоки 15, 16 умножения на константу, сумматор 17. Повышение быстродействия достигается параллельной обработкой разрядов. Упрощение конструкции обусловлено исключением ряда блоков схемы сравнения, коммутатора, кольцевых регистров, генераторов импульсов в конструкции прототипа. 1 ил, 1615702

4О

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

Целью изобретения является повышение быстродействия и упрощение. 15

На чертеже представлена функциональная схема устройства для М=4 (число элементов в перестановке).

Устройство содержит вход 1 перестановки, дешифратор 2, регистР 3 сдви- 20 га, М-2 элементов ИЛИ 4 и 5, N-1 иден= тнчных групп 6-8 блоков, в каждой из ! которых содержится элемент И 9, триггер 10 и счетчик 11, выходы !2-14 дешифратора, соединенные с единичными 25 входами триггеров, М-2 блоков 15 и

16 умножения на константу, сумматор

17 и выход 18 номера перестановки.

Сущность изобретения поясняется для случая. нумерации перестановок из

11=4 цифр 1, 2, 3, 4. На множестве перестановок можно выявить факториаль-: ную систему счисления. При этом имеет

-место следующее соответствие между перестановками и Н-.значными числами факториальной системы счисления (Н=

=М-,.1=3):

1234 — 000 (О)

2134 — 001 (1)

2314 — 002 (2)

2341 — 003 (3)

1324 — 010 (4)

3124 — 011 (5)

3214 — 012 (6)

3241 — 013 (7)

1342 — 020 (8)

3142 — 021 (9)

341г — огг (1о)

3421 — 023 (11)

1243 — 100 (12)

2143 — 101 (13)

2413 — 102 (14)

2431 — 103 (15)

1423 — 110 (16)

4123 — 1 11 (17)

4213 — 112 (18)

4231 — 113 (19)

1432 — 120 (20)

4132 — 121 (21}

4312 — 122 (22)

4321 — 123 (23)

В скобках указайы t порядковые номера перестановок.

Алгоритм нумерации осуществляется в соответствии с выражением

H-1

N=+ g;b, =0 где N - номер перестановки;

Ь . — вес i-го символа факториаль1 ного числа, причем b =1, ь,=м, ь,=м(м-1), ь„=м(м-l) (M-2),..., Ь„, Ì(Ì-1)...3;

И, - символ числа факториальной системы счисления.

Для рассматриваемого случая факториальные числа — О 0(, и О по зиционные веса — Ь =1, д =4 и Ь =12, Пример 1, Перестановке 4132 соответствует факториальное, число

121 с номером

И=К Ь +ф<Ь,+ф Ь„=! ° 12+2 4+1 1 21.

Пример 2. Перестановке 4321 соответствует число 123 факториальной системы счисления с порядковым номером

N=l ° 12+2 ° 4+3 ° 1=23.

Устройство работает следующим образом.

Исходное состояние триггеров 10— единичное, счетчиков 11 " нулевое. В регистре 3 сдвига с входа 1 записана перестановка, напримеР, 4132.

Иод действием тактовых импульсов элементы перестановки цоследовательно сдвигаются в регистре 3 на вход дешифратора 2 ° В соответствующей последовательности возбуждаются выходы дешифратора: четвертый (символ ".4"), первый (символ "1") — шина 12, третий (символ "3") — шина 14, второй (символ "2") — шина 13.

Сигналы от дешифратора определяет моменты переключения триггеров 10 в нулевое состояние, проходя через элементы ИЛИ 4 и 5, элементы И 9 в группах 6-, 8, и посчитываются счетчиками 11 до тех пор, пока соответствую-. щие триггеры сохраняют единичное состояние. После М тактов в счетчиках 11 оказываются зафиксированными значения разрядов номера перестановки в факториальной системе счисления. В рассматриваемом примере в счетчике 11 группы .7 будет зафиксировано число 1

Формула изобретения

Устройство дпя нумерации перестановок, содержащее регистр сдвига, М-2

Ф элементов ИЛИ (М - число элементов перестановки), М-1 элементов И, М-1 триггеров, М-2 блоков умножения на

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

Техред M.Ходанич Корректор Т.Малец

Редактор О,Юрковецкая

Заказ 3987 Тираж 562 Подписное

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

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

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

5 1615 (воздействие символа "4" с последующей блокировкой от символа "1"), в счетчике 1! группы 6 — число 2 (воздействие символов "4" и "3" с последующей блокировкой от символа "2"), в счетчике 11 группы 8 — число 1 (воздействие символа "4" с .последующей блокировкой от символа "3"), Таким образом в факториальной системе код номера перестановки 4132 представляется в виде 121. Блоки 15 и 16 умножения на константу обеспечивают взвешивание разрядов; в блоке 15 осущестйляется умножение на 4, в блоке 16— умножение на 12 и т.п. в соответствии с весом разрядов факториальной системы (разряд, соответствующей группе 7 блоков, имеет единичный вес), Сумматор 17 позволяет получить двоичный, десятичный или иной код номера перестановки на выходе 18 устройства.

702 6 константу, сумматор, причем выходы блоков умножения на константу соединены с входами сумматора, выход сумматора является выходом устройства, 5 отличающееся тем,что,с целью повышения быстродействия и упрощения устройства, оно содержит дешифратор и М-1 счетчиков, причем инфор— мационный вход регистра сдвига является входом перестановки устройства,, последовательный выход регистра сдвига соединен с входом дешифратора, i-й (i=1, М-1) выход дешифратора соеди15 нек с нулевым входом i-ro триггера, выхо ы дешифратора с (j+I )-го (1=

=1, М-2 по М-й соединены с соответствующими входами j-ro элемента ИЛИ, выход j-ro элемента ИЛИ соединен с

20 первым входом j-ro элемента И, М-й выход дешифратора соединен с первым входом (М-1 ) -го элемента И, выход

i-го триггера соединен с вторым входом i-го элемента И, выход i-ro элемента И соединен с входом i-го счетчика, выход ..tepaoro счетчика. соединен с соответствующим входом сумматора, выход (j+I)-го счетчика соединен с входом j-го блока умножения на кон30 станту, I