Устройство для сортировки чисел

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ по авт.св. 9 1051531, отличающееся тем, что, с цепью расширения функциональных воз1« жностей за счет формирования условий сортировки в зависимости от величины сортируемого числа, оно содержит группу элементов ШШ, группу элементов НЕ, группы элементов И и группу выходных элементов ИЛИ, выходы которых подключены к соответствующим установочным входам третьего регистра, входы выходных элементов ИЛИ группы соединены с выходами соответствуннцих разрядов элементов И всех групп сортировки, информационные входы которых подключены к шинам ввода допустимой погрешности сравнения соответствующей группы , входы разрешения записи разрядов элементов И -и группы, где i 1,2... Я,

СОКИ COBETCHHX

РЕСПУБЛИН

0% (11) (5п G 06 F 7/06

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГП4

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТБУ (61) 1051531 (21) 3572883/18-24 (22) 06.04.83 (46) 15.09.84. Вюл. У 34 (72) Т.В.Попова, В.Н.Радкевич и О.И.Чигиринова, (53) 681.325.5(088.8) (56) 1. Авторское свидетельство СССР

В 1051531, кл. С 06 F 7/06, 1982 (прототип).

i (54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ по авт.св. Ф 1051531, о т л и— ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет формирования условий сортировки в зависимости от величины сортируемого числа, оно содержит группу элементов ИЛИ, группу элементов НЕ группы элементов И и группу выходных элементов ИЛИ, выходы которых подключены к соответствующим установочным входам третьего регистра, входы выходных элементов ИЛИ группы соединены с выходами соответствующих разрядов элементов И всех групп сортировки, информационные входы которых подклю-.чены к шинам ввода допустимой погрешности сравнения соответствующей группы, входы разрешения записи разрядов элементов И 1 -й группы, где (=1,2...

8, О - число диапазонов допустимой погрешности„ соединены с выходами, -х ,элементов ИЛИ группы и входами 1-х элементов НЕ группы, выходы которых соединены с управляющими входами эле- д ментов И (1+1)-й, (1+2)-й, и -й групп, Е входы элементов ИЛИ группы подключены к соответствующим разрядам шины ввода первого сравниваемого числа. С

1 1113

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

По основному авт.св. Ф 1051531 известно устройство для сортировки чисел, содержащее счетчики, триггеры, первый, второй, третий и четвертый элементы И, первый, второй элемен- 1ð ты ИЛИ и генератор импульсов, причем выход генератора соединен с первыми входами первого, второго и третьего элементов И, выходы которых подключены к информационным входам первого, второго и третьего счетчиков соответственно, выход переноса первого счетчика соединен с входом установки в нулевое состояние первого триггера, прямой выход которого подключен к второму входу первого элемента И, выход переноса второго счетчика сое динен с входом установки в нулевое состояние второго триггера, прямой выход которого подключен к второму входу второго элемента И, выход переноса третьего счетчика соединен с входом установки в единичное состояние третьего триггера, вход установки в единичное состояние второго триггера соединен с шиной ввода последовательности чисел устройства, вход установки в нулевое состояние третьего триггера подключен к шине ввода допустимой разности сравниваемых чисел, инверсный выход пер- З5 вого триггера соединен с первыми входами первого элемента ИЛИ и четвертого элемента И и первой выходной шиной несравнения чисел, инверсный выход второго триггера соединен с вторыми входами первого элемента ИЛИ и четвертого элемента И и второй выходной шиной несравнения чисел, выход первого элемента ИЛИ подключен к второму входу третьего элемента И, вы45 ход четвертого элемента И соединен с первой выходной шиной сравнения разности с допустимой и с первым входом второго элемента ИЛИ, второй вход которого подключен к прямому выходу третьего триггера и к второй выходной шине сравнения разности с допустимой, выход второго элемента ИЛИ соединен с входом останова генератора импульсов, вход запуска которого подключен к входной шине запуска устройства, а также содержит три регистра, пятый, шестой, седьмой, восьмой

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

Недостатком данного устройства является ограниченная область применения ввиду отсутствия формирования условия сортировки (величины допустимой погрешности) в зависимости от величины сортируемого числа.

В практике, например при классификации (маркировке) или контроле элек797 4

3 1113 грорадиоэлементов, неооходимо формиро. вать условие сортировки (величину до1 пустимой погрешности) в зависимостиот сортируемого параметра (сопротивления, емкости и т.п.). Если параметры представляются числами в большом диапазоне значений (от 1 до 10 ), то

Ф? для чисел от 1 до 10 условием сортировки будут единицы, для чисел от 102 до 10 — десятки и т.д. Следовательно 1р условие сортировки должно меняться в зависимости от величины сортируемого числа.

Цель изобретения — расширение области применения за счет автоматичес- 15 кого формирования условия сортировки, функционально зависящего от величины сортируемого числа.

Указанная цель достигается тем, что устройство для сортировки чисел 2р по авт.св. N - 1051531 содержит группу элементов ИЛИ, группу элементов НЕ, группы элементов И и группу выходных элементов ИЛИ, выходы которых подключены к соответствующим установочным входам третьего регистра, входы выходных элементов ИЛИ группы соединены с выходами соответствующих разрядов элементов И всех групп сортировки, информационные входы которых подключе-ЗО ны к шинам ввода допустимой погрешности сравнения соответствующей группы, входы разрешения разрядов элементов И -й группы, где 1 --1,2... п,n— число диапазонов допустимой погрешности, соединены с выходами 1 -х эле35 ментов ИЛИ группы и входами 1-ых элементов НЕ группы, выходы которых соединены с управляющими входами элементов И (1+1)-й (1+2)-й ... и-й

40 групп, входы элементов ИЛИ группы подключены к соответствующим разрядам шины ввода первого сравниваемого числа.

В устройстве анализируется сортируемое число, и в зависимости от 45 результата анализа формируется условие сортировки.

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

Устройство содержит регистры

1-3, предназначенные для промежуточного хранения сравниваемых чисел и величины допустимой погрешности, счетчики 4-6 с непосредственными связями, построенные на триггерах RS-T типа, при этом запись чисел в счетчики 4,6 осуществляется по двум управляющим сигналам в параллельном коде, запись числа в счетчик 5 осуществляется по одному управляющему сигналу в параллельном коде, счетчи- ки 4-6 выполнены на микросхемах серии 136 (счетчики 4,6-субблок Ф0010

ЛТЗ. 096. О!7, счетчик 5 — субблок

Ф0028 ЛТЗ. 096. 112), триггеры 7-9, предназначенные для хранения информации о переполнении счетчиков генератор 10 импульсов, элемент 11 И,, предназначенный для формирования сигнала запуска генератора, элементы

12-14 И, предназначенные для разрешения прохождения тактовых импульсов на входы счетчиков, элемент 15 ИЛИ, предназначенный для формирования сигнала разрешения прохождения тактовых импульсов через элемент 14 И; элемент 16 И, предназначенный для формирования сигнала А -Ь „ !(K элемент 17 ИЛИ, предназначенный для формирования сигнапа на останов генератора 10; элементы 18 -18 И и элемент 19 ИЛИ, предназначенные для формирования режима отбора чисел, удовлетворяющих заданным требованиям, группу 20 элементов ИЛИ, предназначенную для определения наличия информации в разрядах сортируемого числа," группу 21 элементов НЕ, предназначенную для определения отсутствия информации в разрядах сортируемого числа, группу 22 элементов И, группу выходных элементов 23 ИЛИ, предназначенных для организации прохождения. допустимой погрешности сравнения в регистр 3, входные шины: 24 ввода числа, 25 ввода чисел последовательности, 26 ввода допустимой погрешности сравнения, 27 запуска устройства, 28 задания режима отбора, выходные шины: первую шину 29 несравнения чисел, первую шину 30 сравнения разности чисел с допустимой погрешностью, вторую шину 31 несравнения чисел, вторую шину 32 сравнения разности чисел с допустимой погрешностью, шину 33 считывания чисел.

Устройство для сортировки чисел . работает следующим образом.

При включении питания вырабатывается сигнал, устанавливающий все триггеры, счетчики и регистры в исходное (нулевое) состояние. Узел выработки сигнала при включении питания на фиг.1 не показан.

При сортировке чисел последовательности о; импульсом записи с входной

1113797 шина 24 в регистр 1 и счетчик 4 через установочные входы заносится заданное число А . Этот же импульс записи устанавливает триггер 7 в единичное состояние, на прямом выходе триггера 7 5 появляется сигнал, являющийся разрешающим для элементов 11 и 12 И. Одновременно число А поступает на группу 20 элементов ИЛИ в параллельном, коде. Если старшая группа разрядов числа содержит информацию, то на выходе элемента 201 ИЛИ появится сигнал, который поступает на вход элемента 22 у И и разрешает запись с шины 26 допустимой погрешности Я„, соразмер- 15 ной с величиной: старших разрядов числа Й, через элементы 22 И, 23 ИЛИ в регистр и счетчик 6 (через у тановоч. ные входы). Если в старших разрядах числа A нет информации, то сигнал об этом с выхода элемента 21 НЕ поступает на разрешающие входы элементов 22, 22), 22 И. Если в следующих разря дах числа А есть информация, то сигнал с выхода элемента 20 ИЛИ поступает на вход элемента 22 И и разрешает запись с шины 26 допустимой погрешности E < соразмерной с величиной

I анализируемых разрядов числа А, через элементы 22 И, 23 ИЛИ в регистр 30

3 и счетчик .6.

Таким образом, в элементах 20rt20 ИЛИ группы анализируется наличие информации в разрядах числа h . Элементы 21< -21 НЕ формируют сигнал

35 отсутствия информации в старших (предшествующих) разрядах числа A элементы 22„- 22) И, элемент 23 ИЛИ формируют условия сортировки, разре40 шая прохождение с входной шины 26 той допустимой погрешности 1, которая зависит от числа A . .С выходов элементов 23 ИЛИ сигнал поступает также на вход триггера 9 и устанавливает его в нулевое состояние. На инверсном вы.45 ходе триггера 9 появится сигнал,яв.ляющийся разрешающим для элемента 11 И. На выходной шине 28 устанавливается один из режимов отбора (А-$„) g,! А-3 >(А- Ь1)C. Импульсом записи с входной шины 25 в регистр 2 и счетчик 5 заносится первое число В из последовательности .В„". Этот же импульс записи устанавливает триггер 8 в единичное состояние, следовательно, 55 с выхода элемента 15 ИЛИ на элемент

14 И поступает сигнал, запрещающий прохождение тактовых импульсов через элемент 14 И на информационный (счет ный) вход счетчика 6. На прямом выходе триггера 8 появляется сигнал,являющийся разрешающим для элемента 13 И. Этот же сигнал поступает на третий вход элемента 11 И. На выходе элемента 11 И появляется сигнал, поступающий в генератор 10 и являющийся разрешающим для выработки тактовых импульсов. С входной шины 27 на генератор 10 подается сигнал, по которому на выходе генератора формируются тактовые импульсы", поступающие через элементы 12 и 13 И на информационные входы счетчиков 4 и 5 соответственно и производящие последовательное вычитание единиц из содержимого счетчиков 4 и 5, осуществляя таким образом сравнение чисел 4 и Ь .

Импульс переполнения появляется на выходе того счетчика, содержимое которого меньше, т. е. если A c Ь< то импульс переполнения появляется на выходе счетчика 4 и устанавливает триггер 7 в нулевое состояние. Сигнал с прямого выхода триггера 7 запрещает дальнейшее прохождение тактовых импульсов через элемент 12 И на вход счетчика 4 ° Сигнал с инверсного выхода триггера 7 поступает на выходную шину 29 (свидетельствует о том, что

A c Ьл) и через элемент 15 ИЛИ поступает на элемент 14 И, разрешая прохождение тактовых имйульсов на вход счетчика 6.

Если А > Ьq то импульс переполнения появляется на выходе счетчика 5 и устанавливает триггер 8 в нулевое состояние. Сигнал с прямого выхода триггера 8 запрещает дальнейшее прохождение тактовых импульсов через элемент 13 И на вход счетчика 5. Сигнал с инверсного выхода триггера 8 поступает на выходную шину 31 (свидетельствует о том, что,A> Ь 4 ) и через элемент 15 ИЛИ поступает на элемент 14 И, разрешая прохождение так-. товых импульсов на вход счетчика 6.

В результате сравнения чисел,А и

8„ ooT eT T eM eT HKe (5, если А < Ъ или 4, если А > Ью ) содержится величина j i Ь4. Тактовые импульсы с выхода генератора 10 поступают через элемент 14 И в счетчик 6 и через один из элементов 13 или 12 И в тот счетчик, где содержится величина iA-Ь 1

Импульс переполнения появляется на выходе того счетчика, содержимое

ИЛИ в регистр 2 и разрешающий выдачу из регистра 2 числа о на выходную шину 33.

Сигналом с выхода элемента 17 ИЛИ осуществляется также установка в исходное состояние триггеров 7 и 9 (единичное для триггера 7 и нулевое для триггера 9) и запись содержимого регистров 1 и 3 (через установочные входы) в счетчики 4 и 6 соответственно. Устройство готово к приему следующего числа из последовательности Ь „ . При поступлении каждого следующего числа из последовательности В; устройство работает аналогично.

Таким образом, при сортировке чисел последовательности Ь „ по заданному числу и зависящему от него условию сортировки, на выходной шине

33 Формируется. новая последовательность чисел, удовлетворяющая режиму отбора.

При сортировке (классификации) чисел A устройство работает аналогично, т.е. в зависимости от величины сортируемого числа A е помощью групп

20 ИЛИ, 21 НЕ, 22 И, элементов 23 ИЛИ формируется условие сортировки, записываемое в регистр 3 и счетчик 6. На входной шине 28 устанавливается режим

IA-Ü } 6. В результате сравнения числа

А с числами заданной последовательности Ь на выходной шине 33 появляется число Ь„, удовлетворяющее условию IA-Ь „ I (., величиной которого можно классифицировать сортируемое число А

Таким образом, сортировка чисел осуществляется в зависимости от условия сортировки, формируемого в устрой. стве.

Базовым объектом изобретения является устройство для сортировки чисел по авт.св. У 105!531, которое имеет широкую область применения, выполнено на простых унифицированных элементах, позволяет отбирать числа из последовательности, отличающиеся от заданного на величину большую, меньшую или равную допустимой и классифицировать заданные числа с допус-. тимой погрешностью. Однако в базовом объекте не предусмотрено автоматическое формирование допустимой погрешности, т.е. не предусмотрено формирование условия сортировки в зависимости от величины сортируемого числа.

7 1113797 8 которого меньше; т .е. если 1А - <(-, то импульс переполнения появляется на выходе того счетчика (5 или 4), где содержалась величина А- Ь„1 . Этот импульс устанавливает соответствую- 5 щий триггер в единичное состояние.

Следовательно, на выходе элемента 16 И появляется сигнал, поступающии на выходную шину 30 и свидетельствующий о том, что r — о }< . Одновременно сиг- 10 нал с выхода элемента 16 И поступает через элемент 17 ИЛИ в генератор 10 останавливает его, прекращая таким образом выработку тактовых импульсов. Если режимом отбора, установленным на входной шине 28, было

1А- $q}

33. Если режимом отбора было)А-Bi}>E или }А - В „ i = с, а }" л }

Если IA -B ) L> то импульс переполнения появляется на выходе счетчика 6 и устанавливает триггер 9 в единичное состояние. Сигнал с прямо;го выхода триггера 9 через элемент 17 ИЛИ поступает в генератор 10, останавливая его. Этот же сигнал поступает на выходную шину 32 и свидетельствует о том, что IA-Ь }>

Если режимом отбора, установленным на. входной шине 28, было !А — 0 < }>с . то сигнал с прямого выхода триггера

9 является разрешающим для элемента 18 И, на выходе которого появляет40 ся сигнал, поступающий через элемент 19 ИЛИ в регистр 2 и разрешающий выдачу из регистра 2 числа В„ на выходную шину 33.

Если }Й- Ь q}--C, то сигнал перепол45 нения появляется одновременно на выходе счетчика 6 и того счетчика, где содержалась величина, и того счетчика, где содержалась величина IA - $

32 свидетельствует о том, что

}А †}=с . Сигналом с выхода элемента 17 ИЛИ останавливается генератор

10. Если режимом отбора, установленным на входной шине, было !А-I g}=, то на выходе элемента 18 И появляется сигнал, поступающий через элемент 19

97

ВНИИПИ Заказ 6620/40 Тираж 698 Подписное

Филиаи ШЩ "Патеит" ° г.Ужгород, ул.Проектная, 4

9 11137

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

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

Так, например, предлагаемое устройство может быть использовано при присвоении номиналов (маркировке) электрорадиоэлементам, где в качестве заданнбго или сортируемого числа 2р выступает измеренный параметр, в качестве последовательности чисел— шкапа номиналов и где допустимая погрешность (условие сортировки) функционально зависит от величины параметра.

Предлагаемое устройство может быть использовано при сортировке изделий (например, деталей), продукции сель- . ского хозяйства и животноводства, где в качестве сортируемого числа (параметра) выступает масса, в качестве последовательности, чисел — шкала стандартных масс и где условие сортировки также зависит от величины параметра.

Значительное расширение области применения предлагаемого устройства достигается за счет. незначительного увеличения аппаратурных затрат.

Так, при работе с числами, представленными восьмиразрядным двоичным кодом, аппаратурные затраты увеличиваются примерно на 0,177.