СПОСОБ И УСТРОЙСТВО НАХОЖДЕНИЯ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ЭЛЕМЕНТОВ МАССИВА МЕТОДОМ ДЕШИФРАЦИИ ДАННЫХ
METHOD AND DEVICE FOR FINDING LARGEST AND SMALLEST ELEMENTS OF ARRAY BY METHOD OF DATA DECODING

Изобретение относится к техническим способам и средствам информатики и вычислительной техники и может быть использовано для создания быстродействующих специализированных цифровых устройств по упорядочению двоичной информации, в том числе выполняющих «мягкие» расчеты. Техническим результатом является снижение количества аппаратных средств, что ведет к упрощению алгоритма работы блока управления устройства, и повышение надежности работы.
Указанный результат достигается за счет того, что способ нахождения наибольшего и наименьшего элементов массива методом дешифрации данных предполагает представление всех элементов массива в унарном коде, их объединение на едином поле, например, на единой шине унарных данных, нахождение наибольшего/наименьшего значения и восстановление двоичного представления этих значений, а устройство нахождения наибольшего и наименьшего элементов массива методом дешифрации данных содержит: блок данных, блоки дешифрации, блок формирования результата, блок управления и логические элементы. Новым в устройстве является то, что нахождение наибольшего/наименьшего элементов массива методом дешифрации выполняется параллельно над всеми элементами массива данных, хранящихся в блоке данных, а результат - наибольшее или наименьшее значение элементов массива считывается из памяти в блоке формирования результата.
Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано для создания быстродействующих специализированных цифровых устройств по упорядочению двоичной информации, в том числе, выполняющих «мягкие» расчеты и осуществлению основных операций над нечеткой информацией.
Известные способы сравнения двоичных чисел (см., например, Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др. / Под ред. Б.Н. Малиновского. Киев: Техника, 1974 г.), Шевкопляс Б.В. Микропроцессорные структуры. Инженерные решения: Справочник. М.: Радио и связь, 1990 г., патент RU 2300134) ориентированы только на однозначные двоичные числа, что препятствует достижению заявляемого технического результата.
Известны также способы сравнения и нахождения наибольших и наименьших чисел и устройства для их реализации (Патенты RU 2298219, 2300133, 2361266, 2363034, 2365975, 2389063). К причине, препятствующей достижению заявляемого технического результата, при использовании этих известных селекторов двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что выполняется селекция только большего или только меньшего из указанных двоичных чисел.
В качестве прототипа нами выбран способ, реализованный в "Устройство сортировки информации методом дешифрации данных" (патент RU 2319197), который позволяет упорядочить информацию по возрастанию / убыванию.
В прототипе по сортировке информации методом дешифрации данных выполняется задача упорядочения входной числовой и символьной информации по возрастанию и убыванию. В устройстве осуществляются поисковые операции по указанному интервалу или по конкретному заданному символу или числу. К причине, препятствующей достижению заявляемого технического результата при использовании данного способа и устройства относятся сложный алгоритм реализации, большие аппаратные затраты на техническое исполнение и, как следствие, низкое быстродействие.
Заявленное изобретение направлено на быстрое нахождение экстремальных (максимального и минимального) значений среди предъявляемых данных за счет использования унарных кодов в процессе сортировки этих данных. Поставленная задача возникает при разработке систем и средств контроля и управления на основе нечеткой (качественной) информации для реализации «мягких» вычислений.
Задачи предлагаемого способа и устройства заключаются в следующем:
1) уменьшить аппаратные затраты устройства;
2) упростить алгоритм блока управления;
3) повысить скорость нахождения наибольшего/наименьшего данного в массиве;
4) распараллелить основную операцию по сортировке информации,
5) повысить надежность работы узла сортировки информации.
Способ заключается в следующем: исходные данные - целые числа разрядности m, среди которых необходимо найти набольшее или наименьшее, хранят в памяти вычислительного устройства в виде массива ячеек информации. Для реализации заявленного способа необходимо совершить следующие действия.
Над группой из n ячеек двоичной информации разрядности m, находящихся в блоке исходных данных, реализуется одновременная дешифрация этих данных и их представление в унарных кодах, объединение этих кодов на одном носителе, и нахождение наибольшего/наименьшего номеров разрядов с ненулевым значением, с последующим преобразованием этих номеров в двоичный код, являющийся наибольшим/наименьшим значением среди элементов исходного массива.
i
i
i
i
Для реализации заявленного способа может быть применено устройство (фиг. 1), включающее блок ввода данных (БВД) 3, блок дешифрации (БД) 4, блок хранения результата (БХ) 7 и блок управления (БУ) 2, отличающееся тем, что с целью нахождения наибольшего/наименьшего значения элементов массива из блока ввода данных 3 дополнительно введены шина унарных данных (ШУД) 1, блок нахождения максимального элемента (БМХ) 5 и блок нахождения минимального элемента (БМН) 6, причем выходы регистров блока входных данных 9 (i-1,…,n) соединены со входами отдельных дешифраторов 4 (i=1,…,n), выходы которых 10 (i=1,…,n) соединены с соответствующими разрядами шины унарных данных, образующих входы данных блока нахождения максимального 5 и блока нахождения минимального 6 значений, выходы которых 14, 15 образуют адресные входы блока хранения результата 7, а выходы блока управления осуществляют синхронизацию 19 блоков дешифрации 4 (i=1,…,n), нахождения 17 максимума и 18 минимума, а также 16 блока хранения результата 7. При этом для обеспечения электрической развязки в блоке дешифрации по каждому из n каналов вводится блок вентилей, по числу выходов отдельного дешифратора. В свою очередь, блок хранения включает постоянное запоминающее устройство, адресный вход которого формируется первым и вторым входом данных, объединенных между собой одноименных разрядных линий, с учетом электрической диодной развязки.
i
m
Шина унарных данных 1 (фиг. 2) образована объединением, с соответствующей электрической развязкой, выходов 8 (i=1,…,n) дешифраторов отдельных ячеек исходных данных. После формирования данных на этой шине, находят «самый старший» (ненулевой из 2-1) / «самый младший» (ненулевой) ее разряды, которые и будут соответствовать наибольшему/наименьшему значениям элементов исходного массива.
m
m
m
m
Реализация блоков наибольшего (фиг. 3) и наименьшего (фиг. 4) значений, для обеспечения универсальности технической реализации различается только очередностью подключения разрядов линий, причем блок наибольшего значения (фиг. 3) включает 2-1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 2-1 элементов ИЛИ, элемент И на два входа, 2-1 элементов И на два прямых и один инверсный вход, причем нулевой вход блока является первым входом двухвходового элемента И, второй вход которого является входом управления данного блока, а выход образует нулевой разряд выходной шины данных блока, каждый 1-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ первым входом подключен i-1-му, а вторым к i-му разрядам входной для блока шины данных, выход которого образует первый прямой вход трехвходового элемента И, второй вход которого является входом управления данного блока, а инверсный вход первого трехвходового элемента И подключен к нулевому разряду выходной шины данных блока, инверсные входы остальных j=2…2-1 трехвходовых элементов И подключены к элементам ИЛИ с номерами j-1, входы которых подключены к j-2 и j-1 разрядам выходной шины данных блока, выходы элементов И образуют соответствующие разряды выходной шины данных блока.
m
m
m
m
m
Блок наименьшего значения (фиг. 4) включает 2-1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 2-1 элементов ИЛИ, элемент И на два входа, 2-1 элементов И на два прямых и один инверсный вход, причем нулевой вход блока является первым входом двухвходового элемента И, второй вход которого является 2-1 входом управления данного блока, а выход образует нулевой разряд выходной шины данных блока, каждый i-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ первым входом подключен i-1-му, а вторым к i-му разрядам входной для блока шины данных, выход которого образует первый прямой вход трехвходового элемента И, второй вход которого является входом управления данного блока, а инверсный вход первого трехвходового элемента И подключен к нулевому разряду выходной шины данных блока, инверсные входы остальных j=2-1…3 трехвходовых элементов И подключены к элементам ИЛИ с номерами j-1, входы которых подключены к j-2 и j-1 разрядам выходной шины данных блока, выходы элементов И образуют соответствующие разряды выходной шины данных блока.
В данном случае, совокупность блока нахождения максимального элемента и блока нахождения минимального элемента - это два блока поиска экстремальных значений, отличающихся между собой только очередностью разрядов линий.