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

Группа изобретений относится к области обработки информации и может быть использована в специализированных устройствах обработки нечеткой информации для осуществления сортировки исходных данных. Техническим результатом является уменьшение аппаратных затрат и повышение быстродействия вычислений. Устройство содержит блок ввода данных, блок дешифрации, блок хранения результата, блок управления, блок нахождения максимального элемента, блок нахождения минимального элемента, шину унарных данных. 2 н. и 5 з.п. ф-лы, 4 ил.

 

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

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

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

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

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

В качестве прототипа нами выбран способ, реализованный в "Устройство сортировки информации методом дешифрации данных" (патент RU 2319197), который позволяет упорядочить информацию по возрастанию / убыванию.

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

Заявленное изобретение направлено на быстрое нахождение экстремальных (максимального и минимального) значений среди предъявляемых данных за счет использования унарных кодов в процессе сортировки этих данных. Поставленная задача возникает при разработке систем и средств контроля и управления на основе нечеткой (качественной) информации для реализации «мягких» вычислений.

Задачи предлагаемого способа и устройства заключаются в следующем:

1) уменьшить аппаратные затраты устройства;

2) упростить алгоритм блока управления;

3) повысить скорость нахождения наибольшего/наименьшего данного в массиве;

4) распараллелить основную операцию по сортировке информации,

5) повысить надежность работы узла сортировки информации.

Способ заключается в следующем: исходные данные - целые числа разрядности m, среди которых необходимо найти набольшее или наименьшее, хранят в памяти вычислительного устройства в виде массива ячеек информации. Для реализации заявленного способа необходимо совершить следующие действия.

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

Для реализации заявленного способа может быть применено устройство (фиг. 1), включающее блок ввода данных (БВД) 3, блок дешифрации (БД) 4, блок хранения результата (БХ) 7 и блок управления (БУ) 2, отличающееся тем, что с целью нахождения наибольшего/наименьшего значения элементов массива из блока ввода данных 3 дополнительно введены шина унарных данных (ШУД) 1, блок нахождения максимального элемента (БМХ) 5 и блок нахождения минимального элемента (БМН) 6, причем выходы регистров блока входных данных 9_i (i-1,…,n) соединены со входами отдельных дешифраторов 4_i (i=1,…,n), выходы которых 10_i (i=1,…,n) соединены с соответствующими разрядами шины унарных данных, образующих входы данных блока нахождения максимального 5 и блока нахождения минимального 6 значений, выходы которых 14, 15 образуют адресные входы блока хранения результата 7, а выходы блока управления осуществляют синхронизацию 19 блоков дешифрации 4_i (i=1,…,n), нахождения 17 максимума и 18 минимума, а также 16 блока хранения результата 7. При этом для обеспечения электрической развязки в блоке дешифрации по каждому из n каналов вводится блок вентилей, по числу выходов отдельного дешифратора. В свою очередь, блок хранения включает постоянное запоминающее устройство, адресный вход которого формируется первым и вторым входом данных, объединенных между собой одноименных разрядных линий, с учетом электрической диодной развязки.

Шина унарных данных 1 (фиг. 2) образована объединением, с соответствующей электрической развязкой, выходов 8_i (i=1,…,n) дешифраторов отдельных ячеек исходных данных. После формирования данных на этой шине, находят «самый старший» (ненулевой из 2^m-1) / «самый младший» (ненулевой) ее разряды, которые и будут соответствовать наибольшему/наименьшему значениям элементов исходного массива.

Реализация блоков наибольшего (фиг. 3) и наименьшего (фиг. 4) значений, для обеспечения универсальности технической реализации различается только очередностью подключения разрядов линий, причем блок наибольшего значения (фиг. 3) включает 2^m-1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 2^m-1 элементов ИЛИ, элемент И на два входа, 2^m-1 элементов И на два прямых и один инверсный вход, причем нулевой вход блока является первым входом двухвходового элемента И, второй вход которого является входом управления данного блока, а выход образует нулевой разряд выходной шины данных блока, каждый 1-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ первым входом подключен i-1-му, а вторым к i-му разрядам входной для блока шины данных, выход которого образует первый прямой вход трехвходового элемента И, второй вход которого является входом управления данного блока, а инверсный вход первого трехвходового элемента И подключен к нулевому разряду выходной шины данных блока, инверсные входы остальных j=2…2^m-1 трехвходовых элементов И подключены к элементам ИЛИ с номерами j-1, входы которых подключены к j-2 и j-1 разрядам выходной шины данных блока, выходы элементов И образуют соответствующие разряды выходной шины данных блока.

Блок наименьшего значения (фиг. 4) включает 2^m-1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 2^m-1 элементов ИЛИ, элемент И на два входа, 2^m-1 элементов И на два прямых и один инверсный вход, причем нулевой вход блока является первым входом двухвходового элемента И, второй вход которого является 2^m-1 входом управления данного блока, а выход образует нулевой разряд выходной шины данных блока, каждый i-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ первым входом подключен i-1-му, а вторым к i-му разрядам входной для блока шины данных, выход которого образует первый прямой вход трехвходового элемента И, второй вход которого является входом управления данного блока, а инверсный вход первого трехвходового элемента И подключен к нулевому разряду выходной шины данных блока, инверсные входы остальных j=2^m-1…3 трехвходовых элементов И подключены к элементам ИЛИ с номерами j-1, входы которых подключены к j-2 и j-1 разрядам выходной шины данных блока, выходы элементов И образуют соответствующие разряды выходной шины данных блока.

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

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

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

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

4. Устройство по п. 2, отличающееся тем, что блок поиска максимального элемента включает 2^m-1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 2^m-1 элементов ИЛИ, элемент И на два входа, 2^m-1 элементов И на два прямых и один инверсный вход, причем нулевой вход блока является первым входом двухвходового элемента И, второй вход которого является входом управления данного блока, а выход образует нулевой разряд выходной шины данных блока, каждый i-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ первым входом подключен к i-1-му, а вторым - к i-му разрядам входной для блока шины данных, выход которого образует первый прямой вход трехвходового элемента И, второй вход которого является входом управления данного блока, а инверсный вход первого трехвходового элемента И подключен к нулевому разряду выходной шины данных блока, инверсные входы остальных j=2…2^m-1 трехвходовых элементов И подключены к элементам ИЛИ с номерами j-1, входы которых подключены к j-2 и j-1 разрядам выходной шины данных блока, выходы элементов И образуют соответствующие разряды выходной шины данных блока.

5. Устройство по п. 2, отличающееся тем, что блок поиска минимального элемента включает 2^m-1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 2^m-1 элементов ИЛИ, элемент И на два входа, 2^m-1 элементов И на два прямых и один инверсный вход, причем нулевой вход блока является первым входом двухвходового элемента И, второй вход которого является 2^m-1 входом управления данного блока, а выход образует нулевой разряд выходной шины данных блока, каждый i-й элемент ИСКЛЮЧАЮЩЕЕ ИЛИ первым входом подключен к i-му, а вторым - к i-му разрядам входной для блока шины данных, выход которого образует первый прямой вход трехвходового элемента И, второй вход которого является 2^m-2 входом управления данного блока, а инверсный вход первого трехвходового элемента И подключен к нулевому разряду выходной шины данных блока, инверсные входы остальных j=2^m-3…0 трехвходовых элементов И подключены к элементам ИЛИ с номерами j-1, входы которых подключены к j-2 и j-1 разрядам выходной шины данных блока, выходы элементов И образуют соответствующие разряды выходной шины данных блока.

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

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