СПОСОБ НАХОЖДЕНИЯ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ЧИСЛА В ПРОИЗВОЛЬНОМ МАССИВЕ ДВОИЧНЫХ МНОГОЗНАЧНЫХ ЧИСЕЛ И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ
METHOD OF FINDING THE LARGEST AND SMALLEST NUMBER IN ARBITRARY ARRAY OF BINARY MULTI-DIGIT NUMBERS AND DEVICE FOR IMPLEMENTING SAID METHOD

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Техническим результатом является упрощение сравнения многоразрядных двоичных чисел за счет использования последовательности одинаковых операций, регулярности структуры вычислений. Способ заключается в следующем: для нахождения наибольшего и наименьшего чисел в массиве (в области памяти) выделяются наибольшее и наименьшее числа среди трех (в трех последовательных ячейках памяти) элементов массива, к этим выделенным числам добавляется очередной элемент массива, вновь находятся среди них наибольшее и наименьшее, и так далее до последнего сравниваемого элемента массива (ячейки памяти), а результатом, наибольшим и наименьшим элементами всего массива являются последние из полученных наибольших и наименьших значений. Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении соответствующих конечных автоматов. Известны способы сравнения двоичных чисел (см., например, Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др. / Под ред. Б.Н. Малиновского. Киев: Техника, 1974 г.), Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь, 1990 г., патент RU 2300134). К причине, препятствующей достижению заявляемого технического результата, относится то, что эти способы ориентированы только на однозначные двоичные числа.
Известны также способы сравнения и нахождения наибольших и наименьших чисел и устройства для их реализации (Патенты RU 2298219, 2300133, 2361266, 2363034, 2365975, 2389063). К причине, препятствующей достижению заявляемого технического результата при использовании этих известных селекторов двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что выполняется селекция только большего или только меньшего из указанных двоичных чисел.
3
2
1
3
2
3
2
2
1
2
1
3
2
2
1
3
2
2
1
i
Наиболее близким способом и устройством для его реализации того же назначения к заявленному изобретению по совокупности признаков является, принятый за прототип, селектор двоичных чисел (патент РФ 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 (фиг. 1) используется для завершения операции поиска наибольшего и наименьшего чисел во всем массиве (фиг. 2).
В качестве формирователя max/min из двух чисел может быть использовано устройство (патент RU 2365975 G06F 7/02).
Сведения, подтверждающие возможность осуществления изобретения с получением вышеуказанного технического результата, заключаются в следующем.
В заявляемом способе сравнения двоичных чисел для нахождения наибольшего и наименьшего чисел из массива реализуются две последовательности:
n
n-1
n-2
4
3
2
1
1. max {a, max{a, max{a, max{… max{а, max{а, а, а}…}}}
n
n-1
n-2
4
3
2
1
2. min {a, min{a, min{a, min{… min{a, min{a, a, a}}…}}} Вышеизложенные сведения позволяют сделать вывод, что предлагаемый способ сравнения двоичных чисел обеспечивает нахождение наибольшего и наименьшего чисел из массива данных.
Алгоритм реализации заявляемого способа включает:
i
1) перенос элементов массива исходных данных из памяти (ячейки 3) на внутренний носитель - регистры 4;  (фиг. 2);
1
3
1
2
i
1
2) пересылку первых трех элементов массива данных с регистров 4-4 на входы a, а, a ячейки 2 (фиг. 1);
1
2
2
3) поиск наибольшего и наименьшего значений среди трех элементов массива данных и подачу результатов этого поиска на входы, соответственно, а и а ячейки 2;
2
4) подача значения очередного элемента данных на вход я, ячейки 2;
n-2
5) продолжение операций пп. 3 и 4 до тех пор, пока не будут обработаны все n элементы массива. На выходах max и min ячейки 2 окажутся наибольшее и наименьшее значения исходного массива данных.
Примеры выполнения вычислений по данному способу.
3
2
1
4
1
3
1
2
3
4
1. Пусть а>а>a>а, тогда на выходах ячейки 2 окажутся значения, соответственно, max=а, min=a. На выходах ячейки 2, соответственно, max=а, min=а.
3
2
1
4
1
3
1
2
3
4
2. Пусть а=а>a>а, тогда на выходах ячейки 2 окажутся значения, соответственно, max=а, min=а. На выходах ячейки 2, соответственно, max=а, min=а,
3
2
1
4
1
3
1
2
3
1
3. Пусть а=а>a=а, тогда на выходах ячейки 2 окажутся значения, соответственно, max=а, min=a. На выходах ячейки 2, соответственно, max=а, min=a.
3
2
1
4
1
3
3
2
3
4.
4. Пусть а=а=а>а, тогда на выходах ячейки 2 окажутся значения, соответственно, max=а, min=а. На выходах ячейки 2, соответственно, max=а, min=а
Предложенный способ нахождения наибольшего и наименьшего элементов массива данных произвольного объема n позволяет использовать устройства его реализующие как для сортировки данных, так и в процедурах обработки нечеткой информации, в частности, для операций объединения и пересечения при мягких вычислениях.