Устройство для сортировки информации

 

11

l1

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

1" > 463968

Союз Советский

Социалистимеских

Республик

К АВТОРСКОМУ СВИДЦТВЛЬСТВУ (61) Зависимое от авт. свидетельства— (22) Заявлено 28.12.72 (21) 1868427/18-24 с присоединением заявки №вЂ” (51) М.Кл. G 06f 7/08

Государственный комитет

Совета Министров СССР оо делам изооретений и открытий (23) Приоритет—

Опубликовано 15.03.75. (53) УДК 681.325.5 (088.8) Бюллетень № 10

Дата опубликования описания 14.10.75 (72) А вторы изобретения

В. И. Спиридонов и И. И. Бутенко (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ

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

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

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

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

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

Устройство работает следующим образом, На входы 1 подаются обрабатываемые числа последоВательным дВОичным кодом, начиная со стар1пих разрядов. Значения одноименных разрядов всех поступивших чисел

15 запоминаются соответствующими элементами памяти 2 и передаются на входы мажоритарного элемента 4. Если число единиц, поступивших на входы мажоритарного элемента 4, не меньше его порога, n — lг+ 1, то на его выходе формируется также единичное значение одноименного разряда выходого числа. При невыполнении указанного условия выходное число в данном разряде принимает нулевое значение.

Сформированное значение разряда выходного числа подается на один из входов схем сравнения 3, где производится его сравнение со значениями одноименных разрядов, подаваемыми на входы мажоритарного элемента з0 4. При несравнении схема сравнения 3 выра463968

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

Элемент памяти 2 независимо от значения последующих разрядов числа, подаваемого на его информацио нный вход, остается в состоянии, соответствующем значению первого несравнившегося разряда. По мере поступления на в оды 1 устройства разрядов обрабатываемых чисел íà его выходе формируется последовательность значений разрядов Й-го по величине числа.

Проиллюстрируем работу устройства на числовом примере.

Пусть имеется четыре двоичных числа:

А = 101, Б = 001, В = 100, I" = 010 (старший разряд левый). Из перечисленного набора чисел требуется определить первое число по величине (меньшее число), для чего в устройстве необходимо использовать мажоритарный элемент «4 из 4-х», т. е. схему «И» на четыре входа.

При подаче старших разрядов чисел на входы 1 устройства они запомнятся соответствующими элементами памяти 2. На входы мажоритарного элемента 4 поступает код

1010; так как число единиц в этом коде меньше порога мажоритарного элемента 4, то значение старшего разряда кода на его выходе принимает нулевое значение, при этом схемы сравнения 3, соответствующие входам, на которые подаются числа А и В, выпадают сигналы несравнения, которые блокируют запись, в соответствующие элементы памяти 2 последующих разрядов чисел А и В. Независимо от значений последующих разрядов этих чисел на выходе указа нных элементов памяти

2 присутствует единичная информация.

При подаче следующего разряда обрабатываемых чисел на входы мажоритарного элемента 4 поступает код 1011. Так как число единиц в этом коде меньше порога мажоритарного элемента, то второй разряд выходного числа принимает нулевое значение. Формиру4 ется новый сигнал несравнения по входу I, причем одноименный с ним элемент памяти 2 остается в единичном состоянии независимо от значений последующих разрядов этого чис5 ла.

При поступлении младших разрядов рассматриваемых чисел на .входы мажоритарного элемента 4 подается код 1111, на его выходе формируется единичное значение младшего

10 разряда .выходного числа.

Итак, на выходе мажоритарного элемента

4 формируется число 001, являющееся действительно первым по величине среди обрабатываемых чисел.

15 Для определения из ранее указанного набора чисел второго, третьего, четвертого числа по величине необходимо в устройстве поставить мажоритарные элементы «3 из 4-х», «2 из 4-х» и «1 из 4-х» соответственно, Мажо20 ритарный элемент «1 из 4-х» является схемой

«ИЛИ» на четыре входа. Работа устройства в этих случаях аналогична рассмотренной в предыдущем примере.

25 Таким образом, изобретение позволяет определить любое Й-е по величине число из произвольного набора чисел.

Предмет изобретения

Устройство для сортировки информации, содержащее элементы памяти, схемы сравнения и мажоритарный элемент, причем выходы

З5 всех элементов памяти соединены со входами мажоритарного элемента, выход которого соединен с первыми входами схем сравнения и вых одом устройства, отличающееся тем, что, с целью повышения точности, каждый

10 вход устройства соединен с первым входом соответствующего элемента памяти, выход каждого из кото рых соединен со вторым входом соответствующей схемы сра внения; выход каждой схемы сравнения соединен со вторым входом одноимен ного элемента памяти.

463968

Составитель В. Тюрин

Техред Т. Миронова

Редактор Т. Янова

Корректор Н. Лук

Подппсное

МОТ, Загорский филиал

Заказ 4359 Изд. М 1322 Тираж б79

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, A(-35, Раугиская наб., д. 4/5