Устройство для нумерации перестановок Советский патент 1990 года по МПК G06F7/38 

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

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

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

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

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

17и выход 18 номера перестановки, . Сущность изобретения поясняется v .

для случая.нумерации перестановок из цифр 1, 2, 3, 4, На множестве перестановок можно выявить факториаль- i кую систему счисления. При этом имеет: -место следующее соответствие между перестанов1 а в1 и Н-значными числами факториальной системы счисления (Н ; М-.): :

30

35

0 5

0

5

0

45

0

55

4312 - 122 (22)

4321 - 123 (23) , В скобках указань 1 порядковые номера перестановок.

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

N Z«;b,, :

где N - номер перестановки;

Ъ . - вес i-ro символа факториаль- ного числа, причем Ъд-, Ь,М, (М-1), Ъ,М(М-1) (М-2),,,,, .М(М-1).,,3; pjj- символ числа факториальной

системы счисления, Для рассматриваемого случая фак- ториальные числа - Осг Ofi и р , позиционные веса - Ъо 1, и , Пример 1, Перестановке 4132 соответствует факториальное, число 121 с номером

(,b,+(ХоЬо 1 12+2 «4+1 ,

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

N l«12+2 4+3 l 23,

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

Исходное состояние триггеров JO - единичное, счетчиков 11 - нулевое, В регистре 3 сдвига с входа 1 записана перестановка, например, 4132, ,

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

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

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

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

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

10

7026

конст йнту, сумматор, причем выходы блоков умножения на константу соединены с входами сумматора, выход сумматора является выходом устройства, о тлич ающее ся тем, что, с целью повышения быстродействия и упрощения устройства, оно содержит дешифратор и М-1 счетчиков, причем информационный вход регистра сдвига является входом перестановки устройстве, последовательный выход регистра сдвига соединен с входом дешифратора, i-й (, М-1) выход деигифратора соеди- 15 нея с нулевым входом i-ro триггера, выходы дешифратора с (j+l)-ro (j ; 1 , М-2)по М-й соединены с соответствующими входами j-ro элемента ИЛИ, выход j-ro элемента ИЛИ соединен с первым входом j-ro элемента И, М-й выход дешифратора соединен с первым входом (М-1)-го элемента И, выход 1-го триггера соединен с вторым входом i-ro элемента И, выхрд i-ro элемента И соединен с входом i-ro счетчика, выход первого счетчика, соединен с соответствующим входом сумматора, выход (j+l)-ro счетчика соединен с входом j-ro блока умножения на константу.

20

30

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