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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИН

1 А1 (19) (И) (51)4 G 06 F 15/20

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4175932/24-24 (22) 05 ° 01.87 (46) 23.08.88. Бюл. № 31 (71) Институт кибернетики им.В.M.ÃëóøêîBà (72) Л.Е.Горша, А.К.Беляев, В.И.Гриценко и Б.Г.Мудла (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 995093, кл. G 06 F 15/20, 1981.

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

¹ 446057, кл. С 06 F 15/20, 1972. (54) УСТРОЙСТВО ДЛЯ НУМЕРАЦИИ ПЕРЕСТАНОВОК НАТУРАЛЬНОГО РЯДА ЧИСЕЛ И

НУЛЯ (57) Изобретение относится к автоматике и вычислительной технике, Целью изобретения является расширение области применения эа счет вычисления номера перестановки. Изобретение впервые реализует непосредственный алгоритм вычисления номера перестановки по ее кодированному представлению и позволяет значительно сократить время поиска нумерованных объектов при одновременном уменьшении объемов памяти, необходимых для хранения элементов изображений. Устройство для нумерации перестановок содержит входную информационную шину 1 иэ (и-1)-й кодовой группы для подключения всех кодов элементов перестановки степени и, кроме нулевого, (и-2) блока понижения степени перестановки

2, (п-1) умножителей 3 на константу, многовходовый сумматор 4, выходную информационную шину 5 номера перестановки. 2 ил.

1418731

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

Целью изобретения является расширение области применения за счет вычисления номера генерируемой переста- 10 новки, На фиг. 1 представлена блок-схема устройства; на фиг. 2 — структурная ,схема блока понижения степени перестановки. 15

Устройство содержит вход 1 элементов массива перестановки, блоки 2,-2 „,понижения степени перестанов.ки, где и — количество элементов в перестановке, умножители 3<-3 „, на 20 константу, многовходовой сумматор 4, выход 5.

Блок понижения степени перестановки содержит блоки 6„-6; памяти, где номер блока понижения степени перестановок, Устройство осуществляет вычисление номера перестановки степени с нумерацией элементов от 0 до (n 1).

Принцип работы предлагаемого уст- 30 ройства основан на разбиении некоторого множества перестановок Л„ степени и „a классы мощностью (n 1)t таким образом, что крайний слева. элемент перестановки равняется номеру класса„ при этом имеет место следующее соотношение:

n! = n(n — 1), В результате такого разбиения классы будут пронумерованы числами сф от 0 до (n-1), Номер класса, к которому будет отнесена заданная перестановка, обозначим С,. Продолжая прод цесс, получаем соответственно С и (п-2) и т.д.

Д5

Процесс понижения степени перестановки при переходе к множеству перестановок меньшей степени состоит в перенумерации элементов исходной перестановки. о

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

Значение крайнего слева элемента перестановки является номером класса

С, который для данного преобразования имеет смысл управляющей информации.

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

Коды элементов перестановки поступают на вход 1 устройства, при этом на входе i „, ïðåäñòàâëÿåò собой номер класса С,. В блоке 2<„, происходит преобразование перестановки степени (n-I) в перестановку степени (и-2) под управлением кода С,. Код на (n-2) выходе блока 2<„ > соответствует номеру класса С, который управляет процессом уменьшения степени перестановки в блоке 2(„>) H т.д, Kopef номеров классов С „, где k = 1, (n-1) поступают также на умножители на константу 3 „ ), которые выполняют умножение С на величину (n-k)

Коды с выходов умножителей на коэффициент три суммируются в многовходовом сумматоре 4, на выходе которого формируется код номера перестановки, который поступает на выход 5. !

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

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

{i = 1,2,...n-2) содержит i узлов памяти, входы кодов элементов массива перестановок с первого по (n-2)-й устройства соединены с первыми адресными входами соответственно с первого по (п-2)-й узлов памяти (п-2)-го блока понижения степени, вторые адресные входы узлов памяти которого объединены и соединены с входом (и-1)-го элемента массива перестановок устройства и входом (п-1)-го умножителя на константу, выход k-ro узла памяти 1-ro блока понижения степени перестановки (k = 1,2,..., 1-1;

1 .= 2,3,..., n-2) соединен с первым адресным входом k-го узла памяти

141

Составитель А.Зорин

Редактор Г.Волкова Техред A.Êðàâ÷óê

Корректор И.Эрдейи

Заказ 4155/47 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4 (1-1)-го блока понижения степени перестановки, выход 1-го узла памяти

1-го блока понижения степени перестановки соединен с вторыми адресными входами всех узлов памяти (1-1)-ro блока понижения степени перестановки и входом 1-го умножителя íà константу, выход первого узла памяти перво8731 4 го блока понижения степени перестановок соединен с входом первого умножителя на константу, выходы умножителей на константу с первого по

5 (n-1)-й соединены с соответствующими входами многовходового сумматора, выход которого соединен с выходом устройства.

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

 

Похожие патенты:

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

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

Изобретение относится к вычислительной технике и предназначено для сортировки (ранжирования) N чисел по амплитуде

Изобретение относится к вычислительной технике и предназначено для решения комбинаторных задач

Изобретение относится к автоматике и вычислительной технике и может быть использовано для обработки изображений

Изобретение относится к вычислительной технике и позволяет значительно повысить быстродействие при формировании сочетаний и размещений

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

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

Изобретение относится к устройствам и способам обработки информации, в которых информация записывается, например, на дисковом носителе записи для однократной записи

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

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

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

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

Изобретение относится к области вычислительной техники, а именно к устройствам обработки числовых массивов информации, и предназначено для перестановки строк двумерного массива (матрицы), хранящейся в памяти вычислительного устройства

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

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

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

Изобретение относится к автоматике и вычислительной технике

Наверх