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

СС 80 Э СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 0 51)5 0 06 Р тран- териск Ряд тат кольцевимпульсов1 ил,торо ф, ных ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЭОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ П(НТ СССР ИСАНИЕ ИЗОБРЕ А ВТОРСНОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ НУМЕРАЦИИ ПЕРЕСТАНОВОК(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано, например, в , вычислительных машинах, решающих кобинаторные задачи, в специализировамоделирующих устройствах для ре щения задач синтеза сетеи связи,спортньи сетей, вычисления характик графов и др. Цель изобретения -повышение быстродействия и упрощениеустройства. Устройство содержит регистр сдвига 3, дешифратор 2, злементы ИЛИ 4, 5, И 9, триггеры 1 О, счетчики 11, блоки 15, 16 умножения наконстанту, сумматор 17, Повышениебыстродействия достигается параллельной обработкой разрядов. Упрощениеконструкции обусловлено исключениемсравнения, комму- регистров, генераконструкции протоао 45 Изобретение относится к автоматике и вычислительной технике и может быть использовано, например, в вычислительных машинах, решающих комбина торные задачи, в специализированных моделирующих устройствах для решения задач синтеза сетей связи, транспортных сетей, вычисления характеристик графов, в системах, передачи телеметрической информации дпя формирования больших ансамблей зондирующих сигналов на основе плоских кодов.Целью изобретения является повышение быстродействия и упрощение. 15На чертеже представлена функциональная схема устройства для М=4 (число элементов в перестановке),Устройство содержит вход 1 перестановки, дешифратор 2, регистР 3 сдви га, Мэлементов ИЛИ 4 и 5, Миден-.тичных групп 6-8 блоков, в каждой из которых содержится элемент И 9, триггер 1 О и счетчик 11, выходы 2-14 дешифратора, соединенные с единичными 25 входами триггеров, Мблоков 15 и 16 умножения на константу, сумматор 17 и выход 18 номера перестановки.Сущность изобретения поясняетсядля случая. нумерации перестановок из И=4 цифр 1, 2, 3, 4. На множестве перестановок можно выявить факториальную систему счисления. При этом имеет -место следующее соответствие между перестановками и Н-.значными числами факториальной системы счисления (Н=35=М-,.1=3):1234 - 000 (0)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 г - огг (о)3421 - 023 (11)1243 - 100 (12)2143 - 101 (13)2413 - 102 (14)2431 - 103 (15)1423 - 110 (16)4123 - 111 (7)423 - 112 (18)4231 - 113 (19)1432 - 120 (20)4132 - 121 (21) 4312 - 122 (22)4321 - 123 (23)В скобках указайыпорядковые номера перестановок.Алгоритм нумерации осуществляется в соответствии с выражениемК И=,7 ;Ь,(М), Ь =М(М),.31И, - символ числа факториальнойсистемы счисления.Для рассматриваемого случая факториальные числа - Оа О(, и р, позиционные веса - Ь =1, д 4=4 и Ь=12,П р и м е р 1, Перестановке 4132 соответствует факториальное, число 121 с номеромИ фаьа+фЬ+ф Ьо 1 ф 12+2 4+11 21П р и м е р 2. Перестановке 4321 соответствует число 123 факториальной системы счисления с порядковым номером0=112+24+31=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Формула изобретения Устройство дпя нумерации перестановок, содержащее регистр сдвига, Мэлементов ИЛИ (М - число элементов перестановки), Мэлементов И, Мтриггеров, Мблоков умножения на Составитель В,БайковТехред М,Ходанич Корректор Т,Малец Редактор О,Юрковецкая Заказ 3987 Тираж 562 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 1 Р 113035, Москва, Ж, Раушская наб., д. 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-й (=1, М) выход дешифратора соеди 15 нек с нулевым входом -го триггера,выхо ы дешифратора с (1+1)-го (1==1, Мпо М-й соединены с соответствующими входами )-го элемента ИЛИ,выход 1-го элемента ИЛИ соединен с20первым входом 1-го элемента И, М-йвыход дешифратора соединен с первымвходом (М) -го элемента И, выход-го триггера соединен с вторым входом -го элемента И, вых 9 д 1-го элемента И соединен с входом х-го счетчика, выход первого счетчика соединен с соответствующим входом сумматора, выход (1+1)-го счетчика соединенс входом 1-го блока умножения на кон 30 станту,1