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

. ЮИЛОЮЕП ИХРЕОЪБЛИН 6 ГОСУД АРСТВЕННПО ДЕЛАМ ИЗ НОМИТЕТ СССРТЕНИЙ И ОТНРЬГВЮ ОПИСАНИЕ ИЗОБРЕТЕНИ дкеви(56) 1. Авторское свидетельство СССРВ 489103, кл. С 06 Р 7/02, 1972.2. Авторское свидетельство СССРВ 783790, кл, С 1 06 Р 7/04, 1979(54):(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИЧИСЕЛ, содержащее счетчики, триггеры,первый, второй, третий и четвертыйэлементы Ц, первый, второй элементыИЛИ и генератор импульсов, причемвыход генератора соединен с первымивходами первого, второго и третьегоэлементов И, выходы которых подключены к информационным входам .первого,второго и третьего счетчиков соответственно, выход переноса первого счетчика соединен с входом установки внулевое состояние первого триггера,прямой выход которого подключен квторому входу первого элемента И,выход переноса второго счетчика соединен с входом установки в нулевоесостояние второго триггера, прямойвыход которого подключен к второмувходу второго элемента И, выход переноса третьего счетчика соединенс входом установки в единичное состояние, третьего триггера, вход установки в единичное состояние второготриггера соединен с шиной ввода последовательности чисел устройства,вход установки в. нулевое состояниетретьего триггера подключен к шиневвода допустимой разности сравнивае г мых чисел, инверсный выход первого триггера соединен с первыми входами первого элемента ИЛИ и четвертого элемента И и первой выходной шиной несравнения чисел, инверсный выход второго триггера соединен с вторыми входами первого элемента ИЛИ и четвертого элемента И и второй выходной шиной несравнения чисел, выход первого элемента ИЛИ подключен к второму входу третьего элемента И, выходчетвертого элемента И соединен с пер-, вой выходной шиной сравнения разности с допустимой и с первым входом второго элемента ИЛИ второй вход ЮО которого подключен к прямому выходу . 9 третьего три; гера и к второй выход-, ной шине сравнения разности с допустимой, выход второго элемента ЙЛИ соединен с входом останова генератора импульсов, вход запуска которо- Я го подключен к входной шине запуска устройства, о т л.и ч а ю щ е е с я тем, что, с целью расширения Функциональных возможностей устройства за счет отбора последовательности чисел, отличающихся от сравниваемого числа на величину большую, меньшую или равную допустимой, в него введе ны три регистра, пятый, шестой, седьмой, восьмой элементы И и третий элемент ИЛИ, причем входы первого, второго и третьего регистров подклю: ь к входным шинам ввода первого сравниваемого числа, последовательности чисел и допустимой разности сравниваемых чисел соответственно, выходы первого, второго и третьего регистров соединены с установочными входами соответственно перво" го, второго и третьего счетчиков, 1051 первый вход установки в единичное состояние первого триггера соединен с шиной ввода первого сравниваемого сесна и первым управляющим входом первого счетчика, второй управляющий вход которого соединен с вторым входом установки в единичное состояние первого триггера, выходом второго элемента ИЛИ, вторым входом установки в нулевое состояние третьего тркг- гера и первым управляющим входом третьего счетчика, второй управляющий вход которого подключен к шине ввода допустимой разности сравниваемых чисел, управляющий вход второго счетчика подключен к шине ввода последовательности чисел устройства, первые Входы пятого и седьмого элементов И соединены с выходом четвертого элемента,И, инверсный выход которого подключен к первому входу шестого элемента И, шины задания признаковсортировки соединены с вторымк входами пятага, шестого и седьмого элементов И а ВыхОды, кОтОРых подключенык входам третьего элемента 11 ЛИ, выход которого соединен с входом разрешения выдачи информации второгорегистра, выход которого соединенс шиной считывания сортируемых чисел,третий вход пятого элемента И соединен с инверсным выходам третьеготриггера и первым входом восьмогоэлемента 11, второй и третий входыкоторого подключены к прямым выходам соответственно первого ивторого триггеров, а выходк входу повторного запуска генератора импульсов, третьи входышестого и седьмого элементов Исоединены с прямым выходом третьеготриггера, Изобретение относится к автоматике и вычислительной технике и может, быть использовано в устройствах обработки и сортировки данных в сис-.темах контроля и регулирования.Известно устройство для сравнениядвух чисел, содержащее генераторсчетных импульсов, счетчики, триггеры, схемы И, ИЛИ 11,Недостатком известного устройстваявляются ограниченные функциональныевозможности,Наиболее близким по техническойсущности к предлагаемому являетсяустройство для сравнения чисел, содержащее .счетчики, триггеры, элементы И, ИЛИ генератор, причем выход ,генератора соединен с первыми входами первого и второго элементов И,выходы которых подключены к информационвым входам первого и второгосчетчиков соответственно, выход переноса первого счетчика соединек свходом установки в нулевое состояниепервого триггера, прямой выход которого подключен к второму входу первого элемента И, выход переноса второго счетчика соединен с входомустановки в нулевое состояние второ-.го триггера, прямой выход которого подключен к второму входу второгоэлемента И входы установки в едиичкое состояние первого и второготриггеров и установочные входы второга счет"ика соединены с первой входной шиной установочные ъДн первого счетчика пацключены к второй входной шине выход генератора соединен с первым входом третьего элемента И, выход которого подключен к информационному входу третьего счетчика,выход переносов которого соединенс входам установки в единичное состаяние третьего триггера, вход установки в нулевое состояние которого к установочные входы третьего счетчика подключены к третьей входной пыке, инверсные выходы первого к второготриггеров соединены с первым и вторым входами соответственно первого элемента ИЛИ и четвертого элемента И, выход первого элемента й 21 подклю" чен к второму входу третьего элемен" та И, выход четвертого элемента И соединен с первым входом второго элемента 3 ГЯ, второй вход которого подключен к прямому выходу третьего триггера, выход второго элемента ИЛИ соединен с первым управляющим входом генератора, второй управляю 3 1051щий вход которого подключен к четвертой входной шине 12,Недостатком данного устройстваявляются ограниченные функциональныевоэможности, так как оно позволяет 5сравнивать между собой только двачисла и определять, превышает ли раз-,ность сравниваемых чисел допустимую,Данное устройство не позволяет сравнивать число с последовательностью Очисел, не позволяет формировать последовательность чисел, отличающих-ся от сравниваемого с ними числа навеличину большую,.меньшую или равнуюдопустимой, 15Цель изобретения - расширениефункциональных возможностей устройства путем сравнения числа с последо-вательностью Чисел и формированияпоследовательности чисел, отличных щот заданного числа на величину, мень- .шую или равную допустимой.Указанная цель достигается тем,что в устройство для сортировки чи"сел, содержащее счетчики, триггеры,первый, второй, третий и четвертыйэлементы И, первый, второй элементЫИЛИ и генератор. импульсов, причемвыход генератора соединен с первымивходами первого, второго и третьегоэлементов И, выходы которых подключены к информационным входам первого,второго и третьего счетчиков соот"ветственно, выход переноса первогосчетчика соединен с входом установкив нулевое состояние первого триггера, прямой выход которого подключенк второму входу первого элемента И,выход переноса второго счетчикасоединен с входом установки в нулевое состояние второго триггера, пря- .мой выход которого подключен к второму входу второго элемента И, выход переноса третьего счетчика соединен с входом установки в единичное.состояние третьего триггера, входустановки в единичное состояние второго триггера соединен с шиной ввода последовательности чисел устройст, ва, вход установки в нулевое состояние третьего триггера подключен к 5 Ошине ввода допустимой разности сравниваемых чисел, инверсный выход первого триггера соединен с первыми входами первого элемента ИЛИ и четвертого элемента И и первой выходной ши- Яной несравнения чисел, инверсныйвыход второго триггера соединен свторыми входами первого элемента ИДИ 531 4и четвертого элемента И и второй выходной шиной несравнения чисел, выход первого элемента ИЛИ подключен к второму входу третьего элемента И,выход четвертого элемента И соединен с первой выходной шиной сравнения ,разности с допустимой и с первым входом второго элемента ИЛИ втоЭрой вход которого подключен к прямому выходу третьего триггера и к второй выходной шине сравнения разности с допустимой, выход второго элемента ИЛИ соединен с входом оста- нова генератора импульсов, вход запуска которого подключен к входной шине запуска устройства, введенытри регистра, пятый, шестой, седьмой,восьмой элементы И и третий элемент ИЛИ, причем входы первого, второго и третьего регистров подключены к входным шинам ввода первого сравниваемого числа, последовательности чисел и допустимой разности сравниваемых чисел соответственно, выходы первого, второго и третьего регистров соединены с установочными входами соответственно первого, второго и третьего счетчиков, первый вход установки в единичное состояние первого триггера соединен с шиной ввода первого сравниваемого числа и первым управляющим входом первого счетчика, второй управляющий вход которого соединен с вторым входом установки в единичное состояние первого триггера, выходом второго элемента ИЛИ, вторым входом установки в нулевое состояние третьего триггера и ,первым управляющим входом третьеГо счетчика,. второй управляющий вход которого подключен к шине ввода допустимой разности сравниваемых чисел,управляющий вход второго счетчика подключен к шине ввода последовательности чисел устройства, первые входы пятого и седьмого элементов И соедииены с выходом четвертого элемента И, инверсий выход которого подключен к первому входу шестого элемента И, шины задания признаков сортировки соединены с вторыми входами пятого, шестого и седьмого элементов И, выходы котор"х подключены к входам третьего элемента ИЛИ, выход которого соединен с входом разрешения выдачи информации второго регистра, выход которого соединен с шиной считывания сортируемых чисел, третий вход иятого элемента И соединен с инверс 1051531ньм выходом третьего триггера и первым входом восьмого элемента И, второй и третий входы которого подключены к прямым выходам соответственно первого и второго триггеров, 5а выход - к входу повторного запуска генератора импульсов, третьи входы шестого и седьмого элементов Исоединены с прямым выходом третьеготриггера. 10На чертеже представлена Функциональная схема устройства.Устройство содержит регистры 1-3,предназначенные для промежуточногохранения сравниваемых чисел и допустимой разницы, счетчики 4-6; предназначенные для определения разностейи выполненные в виде последовательных вычитающих счетчиков с непосредственными связями, триггеры 7-9, 20предназначенные дляхранения инФормации в переполнении счетчиков, генератор 10 импульсов, элемент И 11предназначенньй для Формированиясигнала запуска генератора, элементы И 12-14, предназначенные для разрешения прохождения тактовых импульсов на инФормационные входы счетчиков, элемент ИЛИ 15, предназначенныйдля Формирования сигнала разрешения ЗО,прохождения тактовых импульсов черезэлемент И 14, элементы И 16, ШП 1 17,предназначенные для Формирования сигнала "Останов" генератора, элементыl,И 18-20,элемент ИЗИ 21,предназначен- З 5ные для Формирования режима отборапоследовательности чисел, удовлетворяющих заданным требованиям, входныешины 22-26, выходные шины 27"31,Устройство для сортировки чиселработает следующим образом.При включении питания вырабатывается сигнал, устанавливающий всетриггеры, счегчики и регистры устройства в исходное (нулевое) состояние,Узел выработки сигнала при включениипитания на чертеже не показанИмпульсом записи с входной шины22 в регистр 1 и счетчик 4 (черезустановочные входы) заносится число А. Этот же импульс записи устанавливает триггер 7 в единичное состояние, на прямом выходе триггера 7появляется сигнал, являющийся разрешающим для элементов И 11 и 12. Импульсом записи с входной шины 24 врегистр 3 и счетчик 6 (через установочные входы) заносится допустимаяразность " число Я, Этот же импульс записи устанавливает триггер 9 в нулевое состояние. На инверсном выходе триггера 9 появляется сигнал, являющийся разрешающим для элемента И 11, На входной шине 26 устанавливается один из режимов отбора:А-в 1 е,-В;)е,1-в;1=кИмпульсом записи с входной шины 23 в регистр 2 и счетчик 5 (через установочные входы) заносится первое число В иэ последовательности чисел В Этот же импульс ,записи устанавливает триггер 8 в единичное состояние, следовательно, с выхода элемента ИЛИ 15 на элемент И 14 поступает сигнал, запрещающий прохождение тактовых импульсов через элемент И 14 на инФормационный (счетный) вход счетчика б, На прямом выходе триггера 8 появляется сигнал, являющийся разрешающим для элемента И 13. Этот же сигнал поступает на третий вход элемента .И 11. Па выходе элемента И 11 появляется сигнал, поступающий в генератор 10 и являющийся разрешающим для выработки тактовых импульсов. С входной шины 25 на генератор 1 О подается сигнал, по которому на выходе генератора формируются тактовые импульсы, поступаюшне через элементы И 12 и 13 на инФормационные входы счетчиков 4 и 5 соответственно, и производящие последовательное вычитание единиц из содержимого счетчиков 4 и 5. Если 8,1 ( А, то импульс переполнения появ-. ляется на выходе счетчика 5 раньше, чем на выходе счетчика 4.,Этот импульс устанавливает триггер 8 в нулевое состояние, на прямом выходе триггера 8 появляется сигнал, запрещающий дальнейшее прохождение тактовых импульсов через элемент И 13 на вход счетчика 5. На инверсном выходе триггера 8 появляется сигнал, проходящий через элемент ШП 1 15 на вход элемента И 14 и являющийся разрешающим для прохождения тактовых импульсов через элемент И 14 на инФормационный вход счетчика 6. С инверсного выхода триггера 8 сигнал поступает также на выходную шину 29 и свидетельствует о том, что В, ( А. В счетчике 4 в этот момент находится число, равное разности (А-В). Тактовые импульсы, поступая через элементы И 12 и 14 на информационные входы счетчиков 4 и 6, производят последовательное вычитание еПИ10515 7ниц из содержимого счетчиков 4 и б.Если (А-П)сЯ, то импульс переполнения появляется на выходе счетчика 4 раньше, чем.на выходе счетчика б.Этот импульс устанавливает триггер 7 в нулевое состояние, на прямом выходе триггера 7 поянляется сигнал, за.прещающий дальнейшее прохождение тактовых импульсон через элемент И 12 на информационный вход счетчика 4. 10 На инверсном выходе триггера 7 появляется сигнал, поступающий .на выходную шину 27 и на вход элемента И 16, На выходе элемента И 16 появляется сигнал, означающий, что (А-В), Е, Этот сигнал поступает на выходную шину 28. Если на входной шине, 26 есть сигнал, означающий, что из последова" тельности В следует отбирать числа, удовлетворяющие условию (А"О) то этот сигнал является разрешающим для элемента И 18. Сигнал с выхода элемента И 16 через элементы И 18 и ИЛИ 21 поступает в регистр 2 и разрешает выдачу из регистра 2 информации на выходную шину 31. Таким образом на выходную шину 31 выдается число В, удовлетворяющее заданному условию (А-В )Е . Сигнал с выхода элемента И 16 через элемент ИЛИ 7 поступает на генератор 10 и .останавливает его. Таким образом, прекращается дальнейшая выработка, тактовых импуль 35 сон. Сигналом с выхода элемента ИЛИ 17 осуществляется установка в исходное состояние триггеров 7 и 9 (единичное для триггера 7 и нулевое - для триггера 9) и запись содержимого регистров 1 и 3 (через установочные входы) в счетчики 4 и 6 соответственно,.Таким образом, после сравнения числа А с первым числом из последовательности В, устройство автоматически устанавливается в следующее состояние. В регистре 1 и счетчике 4 записано число А, в регистре 3 и . счетчике 6 записано число Е, триг 50 гер 7 установлен в единичное состояние, триггер 9 установлен в нулевое состояние, на входе элемента И 12 сигнал, разрешающий прохождение тактовых импульсов, на входе элементаИ 14 сигнал, запрещающий прохождение,тактовых импульсов, генератор 10 невырабатывает тактовых импульсов. С приходом следующего числа Ву из последовательности В импульсом запичи с входной шины 23 в регистр 2 и счетчик 5 (через установочные входы) заносится число Ц. Этот же импульс записи устанавливает тригге 1 8 в единичное состояние, следовательно, с выхода элемента ИЛИ 15 на элемент И 14 поступает сигнал, запрещающий прохождение тактовых импульсов через элемент И 14 на информационный вход счетчика б, На прямом выходе триггера 8 появляется сигнал, являющийся разрешающим для элемента И 11, На выходе элемента И 11, появляется сигнал, поступающий в генератор 10 и являющийся разрешающим для выработки тактовых импульсов, Таким образом, элемент ИЛИ 17 организует выработку сигнала, запускающего генератор 10 при поступлении очередного числа из последовательности В;, Тактовые импульсы с выхода генератора 10 через элементы И 12 и 13 поступают на информационные входы. счетчиков 4 и 5 соответственно, производя последовательное вычитание единиц из содержимого счетчиков 4 и 5, Если ВрА, то импульс переполнения появляется на ныходе счетчика 4 раньше, чем на выходе счетчика 5, Этот импульс устанавливает триггер 7 в нулевое состояние, на прямом выходе триггера 7 появляется сигнал, запрещающий дальнейшее прохождение тактовых импульсов через элемент И 12 на вход счетчика 4, Этот же сигнал через элемент ИЛИ 15 поступает на вход элемента И 14 и является разрешающим для прохождения тактовых импульсов через элемент И 14 на информационный вход счетчика 6, С инверсного выхода триггера 7 сигнал поступает на выходную шину 27 и свидетельствует о том, что В А. В счетчике 5 в этот момент находится число, равное разности (В-А), Тактовые импульсы, поступая через эле. - менты И 13 и 14 на информационные входы счетчиков 5 и 6, производят последовательное вычитание единиц из содержимого счетчиков 5 и 6. Ес- ли (В-А)Е, то импульс переполнения на выходе счетчика б появляется раньше, чем на выходе счетчика 5. Импульс переполнения с выхода счетчика 6 устанавливает триггер 9 в единичное состояние, на прямом выходе триггера 9 появляется сигнал, поступаннпий9, 10515на выходную шину ЗО и означающий,что (811"А)1.", так как условием отбора чисел иэ последовательности В.было АЕ,а (В -А)Ето на вы"ходе элемента ШШ 21 появляется сиг"нап, запрещающий выдачу содержимогорегистра 2 на выходную шину 31. Еслиусловием отбора является (А-В)1;,то сиги р с прямого выхода триггера 9 через элементы И 19 и ИЛИ 21 поступает на регистр 2 и разрешает выдачу содержимого регистра 2 на выходную шину 31,Сигнал с прямого выхода триггера 9 через элемент ИЛИ 17 поступаетна генератор 1 О и останавливает ега,Таким образом, прекращается дальнейшая выработка тактовых импульсов.Сигнал с выхода элемента ИЛИ 17 поступает на входы триггеров 7 и 9, 2 Оустанавливая их в исходное состояние, и осуществляет запись содержимого регистров 1 и 3 в счетчики 4 и 6(через установочные входы) соответсменно. Следовательно, после сравнения числа А с вторым числом Вд иэ последоватепьности 8 устройство устанавливается в исходное состояние,Ири иоступлении следующего числаиз последовательности В устройствоработает аналогичным образом,Если разность чисел А и В; равна Й, то одновременно появляютсясигналы на выходных шинах 28 и 30. 31 10Если условием отбора чисел является (А"В) Г, о чем свидетельствует разрешающий сигнал, поступающий с входной шины 26 на вход элемента И 20, то сигнал с выхода элемента И 20 через элемент ИЛИ 21 поступает на рег;:стр 2 и разрешает выдачу содержимого регистра 2 на выходную шину 31.Таким образом, устройство. сравнивает число А с числами последовательности В, определяет, находится ли разность (А-В) в пределах допустимой разности и осуществляет отбор чисел из последовательности В поУ одному или совокупности заданных условий (1 А-В 1.", 1 А"В, С, А-Ц Е).Предлагаемое устройство позволяет Формировать из заданной последовательности чисел любую последовательность чисел, отличающихся от заданного числа на величину большую, меньшую или равную допустимой. Расширение функциональных воэможностей устройства достигается эа счет введения новых элементов и связей при не,значительном увеличении аппаратурных затрат.Так при работе с числами, пред". ставленными васьмиразрядным двоичным кодом, апнаратурные затраты по сравнению с базовым объектом увеличиваются примерно на 13 , при этом значительно расширяется область применения устройства.67748 Тираж 706 ВНИИПИ Государственного комите по делай изобретений и откры 113035 Москва ЖРаушская Филиал ППП Патент , г. Ужгород, одписноеа СССРтийнаб.д д. 4/5 Проектна Составитель Е. ИвановаРедактор Е. Папп Техред М.Костик КорреЗаказ 86 П утяг