Устройство для сортировки чисел Советский патент 1984 года по МПК G06F7/06 

СдЭ

со Изобретение относится к автоматике и вычислительной технике и может быть использовано в устройствах обработки и сортировки данных в системах контроля и регулирования, По основному авт.св. № 1051531 из вестно устройство для сортировки чисел содержащее счетчики, триггеры, первый, второй, третий и четвертый элементы И, первый, второй элементы ИЛИ и генератор импульсов, причем выход генератора соединен с первыми входами первого, второго и третьего элементов И, выходы которых подключе ны к информационным входам первого, второго и третьего счетчиков соответ ственно, выход переноса первого счет чика соединен с входом установки в нулевое состояние первого триггера, прямой выход которого подключен к второму входу первого элемента И, выход переноса второго счетчика сое дивен с входом установки в нулевое состояние второго триггера, прямой выход которого подключен к второму входу второго элемента И, выход переноса третьего счетчика соединен с входом установки в единичное состояние третьего триггера, вход установки в единичное состояние второго триггера соединен с шиной ввода последовательности чисел устройства, вход установки в нулевое состояние третьего триггера подключен к шине ввода допустимой разности сравниваемых чисел, инверсный выход первого триггера соединен с первыми вхо дами первого элемента ИЛИ и четверто го элемента И и первой выходной шиной несравнения чисел, инверсный выход второго триггера соединен с вторьми входами первого элемента ИЛИ и четвертого элемента И и второй выход ной шиной несравнения чисел, выход первого элемента ИЛИ подключен к вто рому входу третьего элемента И, выход четвертого элемента И соединен с первой выходной шиной сравнения разности с допустимой и с первым входом второго элемента ИЛИ, второй вход которого подключен к прямому выходу третьего триггера и к второй выходной шине сравнения разности с допустимой, выход второго элемента ИЛИ со единен с входом останова генератора импульсов, вход запуска которого подключен к входной шине запуска уст ройства, а также содержит три регист ра, пятый, шестой, седьмой, восьмой 97. 2 элементы И и третий элемент ИЛИ, причем входы первого, второго и третьего регистров подключены к входным шинам ввода первого сравниваемого числа, последовательности чисел и допустимой разности сравниваемых чисел соответственно, выходы первого, второго и третьего регистров соединены с установочными входами соответственно первого, второго и третьего счетчиков, первый вход установки в единичное состояние первого триггера соединен с шиной ввода первого сравниваемого числа и первым управляющим входом счетчика, второй управляющий вход которого с-оединен с вторым входом установки в единичное состояние первого триггера, выходом второго , элемента ИЛИ, вторым входом установки в нулевое состояние третьего триггера и первым управляющим входом третьего счетчика, второй управляющий вход которого подключен к шине ввода допустимой разности сравниваемьгх чисел, управляющий вход второго счетчика подключен к шине ввода последовательности чисел устройства, первые входы пятого и седьмого элементов И соединены с выходом четвертого элемента И, инверсный выход которого подключен к первому входу шестого элемента И, шины задания признаков сортировки соединены с вторыми входами пятого, шестого и седьмого элементов И, выходы которых подключены к входам третьего элемента ИЛИ, выход которого соединен с входом разрешения вьщачи информации второго регистра, выход которого соединен с шиной считывания сортируемых чисел, третий вход пятого элемента И соединен с инверсным выходом третьего триггера и первым входом второго элемента И, второй и третий входы которого подключены к прямым выходам соотватственно первого и второго триггеров, а выход - к входу повторного запуска генератора импульсов, третьи входы шестого и седьмого элементов И соединены с прямым выходом третьего триггера. Недостатком данного устройства является ограниченная область применения ввиду отсутствия формирования условия сортировки (величины допустимой погрешности) в зависимости от величины сортируемого числа. В практике, например при классификации (маркировке) или контроле элекгрорадиоэлементов, неооходимо формировать условие сортировки (величину допустимой погрешности) в зависимости от сортируемого параметра (сопротивления, емкости и т.п.). Если параметры представляются числами в большом диапазоне значений (от 1 до 10 ), то для чисел от 1 до 10 условием сортировку будут единицы, для чисел от 10 до 10 - десятки и т.д. Следовательно.ю условие сортировки должно меняться в зависимости от величины сортируемого числа. Цель изобретения - расширение области применения за счет автоматичес-ts кого формирования условия сортировки, функционально зависящего от величины сортируемого числа. Указанная цель достигается тем, что устройство для сортировки чисел по авт.св. № 1051531 содержит группу элементов ИЛИ, группу элементов НЕ, группы элементов И и группу выходных элементов ИЛИ, вькоды которых подключены к соответствующим установочным входам третьего регистра, входы выходных элементов ИЛИ группы соединены с выходами соответствующих разрядов элементов И всех групп сортировки. информационные входы которых подключ ны к шинам ввода допустимой погрешности сравнения соответствующей груп пы, входы разрешения разрядов элемен тов И 1-и группы, где i 1,2...vi ,Г число диапазонов допустимой погрешности, соединены с выходами 1 -х элементов ИЛИ группы и входами i-ых эле ментов НЕ группы, выходы которых сое динены с управляющими входами элемен тов И (1 + 1)-й, ((+2)-й, ..., п-й групп, входы элементов ИЛИ группы подключены к соответствующим разряда шины ввода первого сравниваемого числа. В устройстве анализируется сортируемое число, и в зависимости от результата анализа формируется условие сортировки. Функциональная схема устройства представлена на чертеже. Устройство содержит регистры 1-3, предназначенные для промежуточного хранения сравниваемых чисел и величины допустимой погрешности счетчики 4-6 с непосредственными свя зями, построенные на триггерах RS-, -Т типа, при этом запись чисел в счетчики, 4,6 осуществляется по двум управлякнцим сигналам в параллельном

коде, запись числа в счетчик 5 осуществляется по одному управляющему сигналу в.параллельном коде, счетчики 4-6 выполнены на микросхемах серии 136 (счетчики 4,6-субблок ФООЮ ЛТЗ. 096. 017, счетчик 5 - субблок Ф0028 ЛТЗ. 096. 112), триггеры 7-9, предназначенные для хранения информации о переполнении счетчиковj генератор 10 импульсов, элемент 11 И,, предназначенный для формирования сигнала запуска генератораi элементы 12-14 И, предназначенные для разрешения прохождения тактовых импульсов на входы счетчиков, элемент 15 ИЛИ, предназначенный для формирования сигнала разрешения прохождения тактовых импульсов через элемент 14 И, элемент 16 И, предназначенный для формирования сигнала | А-6 1 , элемент 17 ИЛИ, предназначенный для формирования сигнала на останов генератора 10; элементы 18;)-18 И и элемент 19 ИЛИ, предназначенные для формирования режима отбора чисел, удовлетворяющих заданным требованиям, группу 20 элементов ИЛИ, предназначенную для определения наличия информации в разрядах сортируемого числа; группу 21 элементов НЕ, предназначенную для определения отсутствия информации в разрядах сортируемого числа группу 22 элементов И, группу выходных элементов 23 ИЛИ, предназначенных для организации прохождения, допустимой погрешности сравнения в регистр 3, входные шины: 24 ввода числа, 25 ввода чисел последовательности, 26 ввода допустимой погрешности сравнения, 27 запуска устройства, 28 задания режима отбора, выходные шины: первую шину 29 несравнения чисел, первую шину 30 сравнения разности чисел с допустимой погрешностью, вторую шину 31 несравнения чисел, вторую шину 32 сравнения разности чисел с допустимой погрешностью, шину 33 считывания чисел. Устройство для сортировки чисел . работает следукицим образом. При включении питания вьграбатьшается сигнал, устанавливающий все триггеры, счетчики и регистры в исходное (нулевое) состояние. Узел выработки сигнала при включении питания на фиг.1 не показан. При сортировке чисел последовательности Ь i импульсом записи с входной 511 пшнБ 24 в регистр 1 и счетчик 4 через установочные входы заносится заданное число А . Этот же импульс записи устанавливает триггер 7 в единичное сос тояние, на прямом выходе триггера 7 появляется сигнал, являющийся разрешающим для элементов 11 и 12 И. Одновременно число А поступает на группу 20 элементов ИЛИ в параллельном . коде. Если старшая группа разрядов числа А содержит информацию, то на вы ходе элемента 20 ИЛИ появится сигнал который поступает на вход элемента 22 И и разрешает запись с шины 26 допустимой погрешности , соразмерной с величиной старших разрядов числа А , через элементы 22 И, 23 ИЛИ в регистр и счетчик 6 (через установоч ные входы). Если в старших разрядах числа А нет информации, то сигнал об этом с выхода элемента 21 НЕ поступа ет на разрешающие входы элементов 22/ 22i, 22к И. Если в следующих разря дах числа А есть информация, то сигнал с выхода элемента 20j ИЛИ поступает на вход элемента 22 И и разрешает запись с шины 26 допустимой погрешности 0 , соразмерной с величиной анализируемых разрядов числа А , через элементы 221 И, 23 ИЛИ в регистр 3 и счетчик 6. Таким образом, в элементах 20 20ц| ИЛИ группы анализируется наличие информации в разрядах числа А . Элементы 21;,-21j НЕ формируют сигнал отсутствия информации в старших (предшествующих) разрядах числа А , элементы 22 И, элемент 23 ИЛИ формируют условия сортировки, разрешая прохождение с вхбдной шины 26 той допустимой погрешности € , которая зависит от числа А . С выходов элементов 23 ИЛИ сигнал поступает также на вход триггера 9 и устанавливает его в нулевое состояние. На инверсном выходе триггера 9 появится сигнал,яйгляющийся разрешающим для элемента 11 И. На выходной шине 28 устанавливается один из режимов отбора (A-6i) ,|A-6-il e,tA-bil e-. Импульсом записи с йходной шины 25 в регистр 2 и счетчик 5 заносится первое число В из последовательности В. Этот же импульс записи устанавливает триггер 8 в единичное состояние, следовательно, с выхода элемента 15 ИЛИ на элемент 14 И поступает сигнал, запрещакицнй прохождение тактовых импульсов через 7 элемент 14 И на информационный (счет(Ный) вход счетчика 6. На прямом выходе триггера 8 появляется сигнал,являющийся разрешающим для элемента 13 И. Этот же сигнал поступает на третий вход элемента 11 И. На выходе элемента 11 И появляется сигнал, поступающий в генератор 10 и являющийся разрешающим для вьфаботки тактовых импульсов. С входной шины 27 на генератор 10 подается сигнал, по которому на выходе генератора формируются тактовые импульсы поступающие через элементы 12 и 13 И на информационные входы счетчиков 4 и 5 соответственно и производящие последовательное вычитание единиц из содержимого счетчиков 4 и 5, осуществляя таким образом срав 1ение чисел Ани/,. 1йшульс переполнения появляется на выходе того счетчика,содержимое которого меньше, т.е. еслиА Ё, то импульс переполнения появляется на выходе счетчика 4 и устанавливает триггер 7 в нулевое состояние. Сигнал с прямого выхода триггера 7 запрещает дальнейшее прохождение тактовых импульсов через элемент 12 И на вход счетчика 4. Сигнал с инверсного выхода триггера 7 поступает на выходную шину 29 (свидетельствует о том, что А &,() и через элемент 15 ИЛИ поступает на элемент 14 И, разрешая про- хождение тактовых импульсов на вход счетчика 6. , Если ., то импульс переполнения появляется на выходе счетчика 5 и устанавливает триггер 8 в нулевое состояние. Сигнал с прямого выхода триггера 8 запрещает дальнейшее прохождение taKTOBHx импульсов через элемент 13 И на вход счетчика 5. Сигнал с инверсного выхода триггера 8 поступает на выходную шину 31 (свидетельствует о TOMj что.( ) и через элемент 15 ИЛИ поступает на элемент 14 И, разрешая прохождение так-, товых импульсов на вход счетчика6. В результате сравнения чисел ,А и 6VI в соответствунщем счетчике (5, если А - G, или 4, если ) содержится величина |А f b/il. Тактовые импульсы с выхода генератора 10 поступают через элемент 14 И в счетчик 6 и через один из элементов 13 или 12 И в тот счетчик, где содержится величина iA -&-,. Импульс переполнения появляется на выходе того счетчика, содержимое

711

которого меньше, т.е. если iА , то импульс переполнения появляется на выходе того счетчика (5 или 4), где содержалась величина . Этот импульс устанавливает соответствующий триггер в единичное состояние. Следовательно, на выходе элемента 16 И появляется сигнал, поступающий на выходную шину 30 и свидетельствующий о том, 4TofA-6i| €. Одновременно сигнал с выхода элемента 16 И поступает через элемент 17 ИЛИ в генератор 10 останавливает его, прекращая таким образом выработку тактовых импульсов. Если режимом отбора, установленным на входной шине 28, было , то сигнал с выхода элемента 16 И является разрешающим для элемента 8 И, на выходе которого появляется сигнал, поступающий через элемент 19 ИЛИ в регистр 2 и разрешающий выдачу из регистра 2 информации (числа В ) на выходную шину 33. Если режимом отбора было|А-&1| или jA-В 1 6, а 1 fe/tl C , то информация из регистра 2 (число S/) ) на выходную шину не вьщается.

Если IA-&il , то импульс переполнения появляется на выходе счетчика 6 и устанавливает триггер 9 в единичное состояние. Сигнал с прямо|го выхода триггера 9 через элемент 17 ИЛИ поступает в генератор 10, останавливая его. Этот же сигнал поступает на выходную шину 32 и свидетельствует о том, что Если режимом отбора, установленным на входной шине 28, бьшо j , то сигнал с прямого выхода триггера 9 является разрешающим для элемента 18 И, на выходе которого появляется сигнал, поступаюш;ий через элемент 19 ИЛИ в регистр 2 и разрешающий выдачу из регистра 2 числа В . на выходную шину 33.

Если , то сигнал переполнения появляется одновременно на выходе счетчика 6 и того счетчика, где содержалась величина, и того счетчика, где содержалась величина |А - , следовательно, одновременное появление сигналов на выходных шинах 30 и 32 свидетельствует о том, что . Сигналом с выхода элемента 17 ИЛИ останавливается генератор 10. Если режимом отбора, установленным на входной шине, бьшо |А-1Ь 1 , то на выходе элемента 18 И появляется сигнал, поступающий через элемент 19

9/8

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

Сигналом с выхода элемента 1 7 ИЛИ осуществляется также установка в исходное состояние триггеров 7 и 9 (единичное для триггера 7 и нулевое для триггера 9) и запись содержимого регистров 1 и 3 (через установочные

входы) в счетчики 4 и 6 соответственно. Устройство готово к приему следующего числа из последовательности Ь . При поступлении каждого следующего числа из последовательности fei устройство работает аналогично.

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

При сортировке (классификации)

чисел А устройство работает аналогично, т.е. в зависимости от величины сортируемого числа А с помощью групп 20 ИЛИ, 21 НЕ, 22 И, элементов 23 ИЛИ формируется условие сортировки, записываемое в регистр 3 и счетчик 6. На

входной шине 28 устанавливается режим . В результате сравнения числа А с числами заданной последовательности 6;j на выходной шине 33 появляется число fci , удовлетворяющее условию .,, величиной которого можно Классифицировать сортируемое число Л

Таким образом, сортировка чисел

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

Базовым объектом изобретения является устройство для сортировки чи-

сел по авт.св. № 1051531, которое

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

0 от заданного на величину большую,

меньшую или равную допустимой и классифицировать заданные числа с допустимой погрешностью. Однако в базовом объекте не предусмотрено автоматичес5 кое формирование допустимой погрешности, т.е. не предусмотрено формирование условия сортировкив зависимости от величины сортируемого числа. 911 Предлагаемое устройство выполняет все функции базового объекта, обладает той же простотой, так как выполнено на простых ун|1фицированных элементах, однако обладает более широкой областью применения за счет того, что в нем автоматически формируется условие сортировки в зависимости от величины сортируемого числа. Предлагаемое устройство может быть использовано при обработке и сортировке данных в системах контроля, регулирования при .идентификации и классификации предметов и параметров, представленных числовыми кодами. Так, например, предлагаемое устрой ство может быть использовано при присвоении номиналов (маркировке) электрорадиоэлементам, где в качестве заданного или сортируемого числа выступает измеренный параметр, в качестве последовательности чисел 7шкача номиналов и где допустимая погрешность (условие сортировки) функционально зависит от величины параметра. Предлагаемое устройство может быть использовано при сортировке изделий (например, деталей), продукции сель- . ского хозяйства и животноводства, где в качестве сортируемого числа (параметра) выступает масса, в качестве последовательности.чисел - шкала стандартных масс и где условие сортировки также зависит от величины параметра. Значительное расширение области применения предлагаемого устройства достигается за счет, незначительного увеличения аппаратурных затрат. Так, при работе с числами, представленными восьмиразрядным двоичным кодом, аппаратурные затраты увеличиваются примерно на 0,17%.

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