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

Группа изобретений относится к области вычислительной техники и может быть использована в устройствах обработки информации для осуществления сортировки исходных данных. Техническим результатом является упрощение обработки. Устройство содержит n-2 устройств, каждое из которых содержит четыре блока нахождения max и min значений. 2 н. и 1 з.п. ф-лы, 2 ил.

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Техническим результатом является упрощение сравнения многоразрядных двоичных чисел за счет использования последовательности одинаковых операций, регулярности структуры вычислений. Способ заключается в следующем: для нахождения наибольшего и наименьшего чисел в массиве (в области памяти) выделяются наибольшее и наименьшее числа среди трех (в трех последовательных ячейках памяти) элементов массива, к этим выделенным числам добавляется очередной элемент массива, вновь находятся среди них наибольшее и наименьшее, и так далее до последнего сравниваемого элемента массива (ячейки памяти), а результатом, наибольшим и наименьшим элементами всего массива являются последние из полученных наибольших и наименьших значений. Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Известны способы сравнения двоичных чисел (см., например, Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др. / Под ред. Б.Н. Малиновского. Киев: Техника, 1974 г.), Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь, 1990 г., патент RU 2300134). К причине, препятствующей достижению заявляемого технического результата, относится то, что эти способы ориентированы только на однозначные двоичные числа.

Известны также способы сравнения и нахождения наибольших и наименьших чисел и устройства для их реализации (Патенты RU 2298219, 2300133, 2361266, 2363034, 2365975, 2389063). К причине, препятствующей достижению заявляемого технического результата при использовании этих известных селекторов двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что выполняется селекция только большего или только меньшего из указанных двоичных чисел.

Наиболее близким способом и устройством для его реализации того же назначения к заявленному изобретению по совокупности признаков является, принятый за прототип, селектор двоичных чисел (патент РФ 2365975, кл. G06F 7/02, 2007 г.), состоящий в том, что технический результат при осуществлении изобретения достигается тем, в что включает 2n-1 элементов «2ИЛИ», 4n элементов «Запрет», 2n замыкающих и 2n размыкающих ключей, причем все элементы и ключи сгруппированы в n групп так, что j-я группа содержит два элемента «2ИЛИ», четыре элемента «Запрет», два замыкающих и два размыкающих ключа, в j-й группе выход i-го элемента «Запрет», подключенного инвертирующим входом к неинвертирующему входу (3-i)-го элемента «Запрет», и выход (2+i)-го элемента «Запрет», подключенного инвертирующим входом к второму входу (3-i)-го элемента «2ИЛИ», соединены соответственно с неинвертирующим входом (2+i)-го элемента «Запрет» и первым входом i-го элемента «2ИЛИ», подсоединенного выходом к входу управления объединенных выходами i-ых замыкающего и размыкающего ключей, входы которых соединены соответственно с неинвертирующим и инвертирующим входами первого элемента «Запрет», выход i-го элемента «2ИЛИ» предыдущей группы соединен с вторым входом i-го элемента «2ИЛИ» последующей группы, а второй вход i-го элемента «2ИЛИ» первой группы, неинвертирующие входы первого, второго элементов «Запрет» и выходы первого, второго замыкающих ключей j-и группы соединены соответственно с шиной нулевого потенциала, j-ым, (n+j)-ым входами и j-ым, (n+j)-ым выходами селектора двоичных чисел. Недостатками этого способа и устройства его реализующего являются невозможность получения наибольшего или наименьшего значений массива данных и относительная сложность реализации. Техническим результатом данного изобретения является упрощение сравнения двоичных чисел за счет четырех элементов селекции, входами которых являются три исходных числа, а выходами два - наибольшее и наименьшее из этих трех. Указанный технический результат при осуществлении изобретения достигается тем, что в способе сравнения двоичных чисел формируются две пары из трех чисел а3, а2, a1, например, < max{а3, а2}, min{а3, а2} > и < max{a2, a1}, min{a2, a1} > (фиг. 1), а затем находят наибольшее max{max{а3, а2}, max{a2, a1}} и наименьшее min{min{а3, а2}, min{a2, a1}} значения чисел а, b с. Полученная таким образом ячейка 2i (фиг. 1) используется для завершения операции поиска наибольшего и наименьшего чисел во всем массиве (фиг. 2).

В качестве формирователя max/min из двух чисел может быть использовано устройство (патент RU 2365975 G06F 7/02).

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

В заявляемом способе сравнения двоичных чисел для нахождения наибольшего и наименьшего чисел из массива реализуются две последовательности:

1. max {an, max{an-1, max{an-2, max{… max{а4, max{а3, а2, а1}…}}}

2. min {an, min{an-1, min{an-2, min{… min{a4, min{a3, a2, a1}}…}}} Вышеизложенные сведения позволяют сделать вывод, что предлагаемый способ сравнения двоичных чисел обеспечивает нахождение наибольшего и наименьшего чисел из массива данных.

Алгоритм реализации заявляемого способа включает:

1) перенос элементов массива исходных данных из памяти (ячейки 3i ) на внутренний носитель - регистры 4; (фиг. 2);

2) пересылку первых трех элементов массива данных с регистров 41-43 на входы a1, а2, ai ячейки 21 (фиг. 1);

3) поиск наибольшего и наименьшего значений среди трех элементов массива данных и подачу результатов этого поиска на входы, соответственно, а1 и а2 ячейки 22;

4) подача значения очередного элемента данных на вход я, ячейки 22;

5) продолжение операций пп. 3 и 4 до тех пор, пока не будут обработаны все n элементы массива. На выходах max и min ячейки 2n-2 окажутся наибольшее и наименьшее значения исходного массива данных.

Примеры выполнения вычислений по данному способу.

1. Пусть а32>a14, тогда на выходах ячейки 21 окажутся значения, соответственно, max=а3, min=a1. На выходах ячейки 22, соответственно, max=а3, min=а4.

2. Пусть а32>a14, тогда на выходах ячейки 21 окажутся значения, соответственно, max=а3, min=а1. На выходах ячейки 22, соответственно, max=а3, min=а4,

3. Пусть а32>a14, тогда на выходах ячейки 21 окажутся значения, соответственно, max=а3, min=a1. На выходах ячейки 22, соответственно, max=а3, min=a1.

4. Пусть а3214, тогда на выходах ячейки 21 окажутся значения, соответственно, max=а3, min=а3. На выходах ячейки 22, соответственно, max=а3, min=а4.

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

1. Способ нахождения наибольшего и наименьшего значений среди элементов массива данных произвольного объема n, включающий операции сортировки данных, отличающийся тем, что параллельно реализуются две последовательности операций max {an, max{an-1, max{an-2, max{… max{а4, max{а3, а2, a1}}…}}} и min {an, min{an-1, min{an-2, min{… min{a4, min{a3, a2, a1}}…}}} на двух устройствах, каждое из которых содержит четыре блока сортировки и осуществляет сортировку трех данных, при этом первые два таких блока находят наибольшее и наименьшее значения для первого и второго, а также второго и третьего значений данных, результаты подают на третий и четвертый блоки сортировки, причем на третий блок сортировки подают наибольшие значения с первого и второго блоков сортировки, а на четвертый блок сортировки подают наименьшие значения с первого и второго блоков, а выходом устройства является выход наибольшего значения с третьего блока сортировки и выход наименьшего значения с четвертого блока сортировки, которые подают на первые два входа следующего устройства, на третий вход которого подают очередной элемент исходного массива данных, на выходах последнего устройства формируются наибольшее и наименьшее значения исходного массива данных.

2. Устройство для нахождения наибольшего и наименьшего значений среди элементов массива данных произвольного объема n, включающее блоки сортировки данных, отличающееся тем, что используют одновременно четыре блока сортировки трех данных таким образом, что первые два таких блока находят наибольшее и наименьшее значения для первого и второго, а также второго и третьего значений данных, результаты подают на третий и четвертый блоки сортировки, причем на третий блок сортировки подают наибольшие значения с первого и второго блоков сортировки, а на четвертый блок сортировки подают наименьшие значения с первого и второго блока сортировки, выходом устройства являются выход наибольшего значения с третьего блока сортировки и выход наименьшего значения с четвертого блока сортировки.

3. Устройство по п. 2, отличающееся тем, что используются n-2 таких устройства, причем выходы предыдущего устройства соединяются с первым и вторым входами следующего устройства, на третий вход которого подается очередной элемент исходного массива данных, а на выходах последнего n-2 устройства появляются наибольшее и наименьшее значения для всего исходного массива данных.



 

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

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

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

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

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

Изобретение относится к способам создания набора виртуальных машин защиты (ВМЗ) для автоматического выбора ВМЗ с последующим соединением с агентом виртуальной машины с учетом ограничительной области автоматического выбора виртуальных машин защиты.

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых компараторах, ассоциативных процессорах и машинах баз данных. Техническим результатом является упрощение распознавания отношений А>В, А=В, А<В, где А, В есть четырехразрядные двоичные числа, и уменьшение количества элементов аппаратурного состава.

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

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