СПОСОБ НАХОЖДЕНИЯ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ЧИСЛА В ПРОИЗВОЛЬНОМ МАССИВЕ ДВОИЧНЫХ МНОГОЗНАЧНЫХ ЧИСЕЛ И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ Российский патент 2020 года по МПК G06F7/02 G06F7/06 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Техническим результатом является упрощение сравнения многоразрядных двоичных чисел за счет использования последовательности одинаковых операций, регулярности структуры вычислений. Способ заключается в следующем: для нахождения наибольшего и наименьшего чисел в массиве (в области памяти) выделяются наибольшее и наименьшее числа среди трех (в трех последовательных ячейках памяти) элементов массива, к этим выделенным числам добавляется очередной элемент массива, вновь находятся среди них наибольшее и наименьшее, и так далее до последнего сравниваемого элемента массива (ячейки памяти), а результатом, наибольшим и наименьшим элементами всего массива являются последние из полученных наибольших и наименьших значений. Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Известны способы сравнения двоичных чисел (см., например, Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др. / Под ред. Б.Н. Малиновского. Киев: Техника, 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)-ым выходами селектора двоичных чисел. Недостатками этого способа и устройства его реализующего являются невозможность получения наибольшего или наименьшего значений массива данных и относительная сложность реализации. Техническим результатом данного изобретения является упрощение сравнения двоичных чисел за счет четырех элементов селекции, входами которых являются три исходных числа, а выходами два - наибольшее и наименьшее из этих трех. Указанный технический результат при осуществлении изобретения достигается тем, что в способе сравнения двоичных чисел формируются две пары из трех чисел а₃, а₂, a₁, например, < max{а₃, а₂}, min{а₃, а₂} > и < max{a₂, a₁}, min{a₂, a₁} > (фиг. 1), а затем находят наибольшее max{max{а₃, а₂}, max{a₂, a₁}} и наименьшее min{min{а₃, а₂}, min{a₂, a₁}} значения чисел а, b с. Полученная таким образом ячейка 2_i (фиг. 1) используется для завершения операции поиска наибольшего и наименьшего чисел во всем массиве (фиг. 2).

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

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

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

1. max {a_n, max{a_n-1, max{a_n-2, max{… max{а₄, max{а₃, а₂, а₁}…}}}

2. min {a_n, min{a_n-1, min{a_n-2, min{… min{a₄, min{a₃, a₂, a₁}}…}}} Вышеизложенные сведения позволяют сделать вывод, что предлагаемый способ сравнения двоичных чисел обеспечивает нахождение наибольшего и наименьшего чисел из массива данных.

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

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

2) пересылку первых трех элементов массива данных с регистров 4₁-4₃ на входы a₁, а₂, a_i ячейки 2₁ (фиг. 1);

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

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

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

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

1. Пусть а₃>а₂>a₁>а₄, тогда на выходах ячейки 2₁ окажутся значения, соответственно, max=а₃, min=a₁. На выходах ячейки 2₂, соответственно, max=а₃, min=а₄.

2. Пусть а₃=а₂>a₁>а₄, тогда на выходах ячейки 2₁ окажутся значения, соответственно, max=а₃, min=а₁. На выходах ячейки 2₂, соответственно, max=а₃, min=а₄,

3. Пусть а₃=а₂>a₁=а₄, тогда на выходах ячейки 2₁ окажутся значения, соответственно, max=а₃, min=a₁. На выходах ячейки 2₂, соответственно, max=а₃, min=a₁.

4. Пусть а₃=а₂=а₁>а₄, тогда на выходах ячейки 2₁ окажутся значения, соответственно, max=а₃, min=а₃. На выходах ячейки 2₂, соответственно, max=а₃, min=а_4.

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

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

1. Способ нахождения наибольшего и наименьшего значений среди элементов массива данных произвольного объема n, включающий операции сортировки данных, отличающийся тем, что параллельно реализуются две последовательности операций max {a_n, max{a_n-1, max{a_n-2, max{… max{а₄, max{а₃, а₂, a₁}}…}}} и min {a_n, min{a_n-1, min{a_n-2, min{… min{a₄, min{a₃, a₂, a₁}}…}}} на двух устройствах, каждое из которых содержит четыре блока сортировки и осуществляет сортировку трех данных, при этом первые два таких блока находят наибольшее и наименьшее значения для первого и второго, а также второго и третьего значений данных, результаты подают на третий и четвертый блоки сортировки, причем на третий блок сортировки подают наибольшие значения с первого и второго блоков сортировки, а на четвертый блок сортировки подают наименьшие значения с первого и второго блоков, а выходом устройства является выход наибольшего значения с третьего блока сортировки и выход наименьшего значения с четвертого блока сортировки, которые подают на первые два входа следующего устройства, на третий вход которого подают очередной элемент исходного массива данных, на выходах последнего устройства формируются наибольшее и наименьшее значения исходного массива данных.

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

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