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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДДШ СОРТИРОВКИ ЧИСЕЛ, содержащее счетчики, триггеры, первый, второй третг й и четвертый элементы Ц, первый, второй элементы ИЛИ и генератор импульсов, причем выход генератора соединен с первыми ; входами первого, второго и третье злемеятов И, выходы которых подключи ib К информационным входзм первого, второго и третьего счетчиков соответственно , выход переноса первого счбт«шка соединен с входом установки в нулевое состояние первого Триггера, щзямой ш,1ход которого подключен к второму входу первого элемента И, выход переноса второго счетчика соединен с входом установки в нулевое состояние второго триггера, прямой выход которого подключен к второму входу .второго элемента И выход переноса третьего счетчиха соединен с входом установки в единичное состояние , третьего триггера, вход установки в единичное состояние второго триггера соединен с шиной ввода последовательности чисел устройства, вход установки в нулевое состояние третьего триггера подключен к шине ввода допустимой разности сравнивае №1Х чисел, инверсный выход первого триггера соединен с первыми входами первого элемента ИЛИ и четвертого элемента И и первой выходной шиной несравнения чиеел, инверсный выход второго триггера соединен с вторыми входами первого элемента ИЛН и четвертого элемента И и второй выходной шиной несравнения чисел, выход первого элемента ИЛИ подключен к второму входу третьего элемента И, выход четвертого элемента И соединен с первой выходной шиной сравнения раэности с допустимой и с первым входом второго элемента ИЛИ, второй вход которого подюхючен к прямому выходу третьего три1гера и к второй выход- ; |НОй шине сравнения разности с допустимой , выход второго элемента lUDI 1соединен с входом останова генератора импульсов, вход запуска которо;го подключен к входной шине запуска j устройства, о т л.и ч а к щ е е с я О тем, что, с целью расширения функцио:д нальных возможностей устройства за счет отбора последовательности чисел , отличающихся от сравниваемого :о числа на величину большую, меньшую или равную допустимой, в него введе ны три регистра, пятый, шестой, седьмой, восьмой элементы И и третий элемент ИЛИ, причем входы первого, второго и третьего регистров подключены к входным шинам ввода первого сравниваемого числа, последовательности чисел и допустимой разности сравниваемых ч.исел соответственно , выходы первого, второго и третьего регистров соединены с установочными входами соответственно первого , второго и третьего счетчиков.

(1% (И) СОЮЗ СОВЕТСКИХ

МЮВ

PECfMiЛИН

3(59 06 F 06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ (Н АВ й)РСИОМЪ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbffl4A (21} 3472608/18-24 (22) 35.07. 82 (46) 30.!0,83. Бюл. Р 40 (72) T.В. Попова, В,Н. Радкевич и 11., K. Велько (Ы) 6М,3и Д(08ВЛ} (56) 1. Авторское свидетельство СССР

И 489103, кл. $ 06 г. 7/02, 1972.

2. Авторское свидетельство СССР

Ф 783790, кл. С1 06 Р 7/04, 1979 (прототип}. (54):(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее счетчики, триггеры, первый, второй, третий и четвертый элементы Ц, nepabN, второй элементы

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

Ф ввода допустимой разности сравнивае" мых чисел, инверсный выход первого триггера соединен с первыми входами первого элемента ИЛИ и четвертого элемента И и первой выходной шиной несравнения чисел, инверсный выход второго григгера соединен с вторыми входами первого элемента ИЛИ и четвертого элемента И и второй выходной шиной несравнения чисел, выход первого элемента ИЛИ подключен к второму входу третьего элемента И, выход четвертого элемента И соединен с пер-, вой выходной шиной сравнения разности с допустимой и с первым входом второго элемента ИЛИ, второй вход которого подключен к прямому выходу . третьего три-. гера и к второй выход-; ной шине сравнения разности с допустимой, выход второго элемента ЙЛИ соединен с входом останова генератора импульсов, вход запуска которого подключен к входной шине запуска устройства, о т л.и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства sa счет отбора последовательности чисел, отличающихся от сравниваемого числа на величину большую, меньшую или равную допустимой, в него введе ны три регистра, пятый, шестой, седьмой, восьмой элементы И и третий элемент ИЛИ, причем входы первого, второго и третьего регистров подклю-:яь к входным шинам ввода первого сравниваемого числа, последовательности чисел и допустимой разности сравниваемых чисел соответственно, выходы первого, второго и третьего регистров соединены с установочными входами соответственно перво" го, второго и третьего счетчиков, 1051 первый вход установки в единичное состояние первого триггера соединен с шиной ввода первого сравниваемого ясла и первым управляющим входам первого счетчика, второй управляющий вход которого соединен с вторым входом установки в единичное состояние первого триггера, выходом второго элемента ИЛИ, вторым входом установки в нулевое состояние третьего триг-i гера и первым управляющим входом третьего счетчика, второй управляющий вход которого подключен к шине ввода допустимой разности сравниваемых чисел, управляющий вход второго счетчика подключен к шине ввода последовательности чисел устройства, первые входы пятого и седьмого элементов И соединены с выходом четвертого элемента,И, инверсный выход которого подключен к первому входу шестого элемента И, шины задания признаков сортировки соединены с вторыми входами пятага, шестого и седьмого элементов Ир ВыхОды, которых подключены к входам третьего элемента 11ЛИ, выход которого соединен с входом разрешения выдачи информации второго регистра, выход которого соединен с шиной считывания сортируемых чисел, третий вход пятого элемента И соединен с инверсным выходам третьего триггера и первым входом восьмого элемента 11, второй и третий входы которого подключены к прямым выходам соответственно первого и второго триггеров, а выход к входу повторного запуска генератора импульсов, третьи входы шестого и седьмого элементов И соединены с прямым выходом третьего триггера, Изобретение относится к автоматике и вычислительной технике и может, быть использовано в устройствах обработки и сортировки данных в системах контроля и регулирования.

Известно устройство для сравнения двух чисел, содержащее генератор счетных импульсов, счетчики, триггеры, схемы И, ИЛИ (I) .

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

Наиболее близким по технической сущности к предлагаемому является устройство для сравнения чисел, содержащее .счетчики, триггеры, элементы И, ИЛИ,, генератор, причем выход . генератора соединен с первыми входами первого и второго элементов И, выходы которых подключены к информационвым входам первого и второго счетчиков соответственно, выход переноса первого счетчика соединек с входом установки в нулевое состояние первого триггера, прямой выход которого подключен к второму входу первого элемента И, выход переноса второго счетчика соединен с входом установки в нулевое состояние второ-го триггера, прямой выход которого подключен к второму входу второго элемента И„ входы установки в еди-:печное состояние первого и второго триггеров и установочные входы второга счет= ика соединены . п;"ер- ой входной шикай,. установочные :. Ды первоro счетчика подключены к второй входной шине„ выход генератора соединен с первым входом третьего элемента И, выход которого подключен к информационному входу третьего счетчика, выход переносов которого соединен с входам установки в едккк кое состаяние третьего триггера, вход установки в нулевое состояние которого к установочные входы третьего счетчика подключены к третьей входной пыке, инверскыe выходы первого к второго

f триггеров соединены с первым и вторым входами соответственна первого элемента ИЛИ и четвертога элемента И, выход первого элемента ИМ1 подклю" чен к второму входу третьего элемента И, выход четвертого элемента И соединен с первым входом второго элемента KIH, второй вход которого подключен к прямому выходу третьего триггера, выход второго элемента

ИЛИ соединен с первым управляющим входом генератора, второй управляю3 1051 щий вход которого подключен к четвер той входной шине (2) .

Недостатком данного устройства являются ограниченные функциональные воэможности, так как oHd позволяет 5 сравнивать между собой только два числа и определять, превышает ли раз-, ность сравниваемых чисел допустимую, Данное устройство не позволяет сравнивать число с последовательностью 10 чисел, не позволяет формировать последовательность чисел, отличающих- ся от сравниваемого с ними числа на величину большую,-меньшую или равную допустимой. 15

Цель изобретения - расширение функциональных возможностей устройства путем сравнения числа с последо- вательностью чисел и формирования

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

Указанная цель достигается тем, что в устройство для сортировки чисел, содержащее счетчики, триггеры, I первый, второй, третий и четвертый элементы И, первый, второй элементЫ

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

531 4 и четвертого элемента И и второй выходной шиной несравнения чисел, выход первого элемента ИЛИ подключен к второму входу третьего элемента И, выход четвертого элемента И соединен с первой выходной шиной сравнения ,разности с допустимой и с первым

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

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

ИЛИ, вторым входом установки в нулевое состояние третьего триггера и ,первым управляющим входом третьеГо счетчика,. второй управляющий вход которого подключен к шине ввода допустимой разности сравниваемах чисел, управляющий вход второго счетчика подключен к шине ввода последовательности чисел устройства, первые входы пятого и седьмого элементов И соедииены с выходом четвертого элемента И, инверсыай выход которого подключен к первому входу шестого элемента И, шины задания признаков сорТНроВКН соединены с вторыми входами пятого, шестого и седьмого элементов И, выходы котор".z подключены к входам гуетьего элемента ИЛИ, выход которого соединен с входом разрешения выдачи информации второго регистра, выход которого соединен с шиной считывания сортируемых чисел,.третий вход иятого элемента И соединен с инверс1051531 нь<м выходом третьего триггера и первым входом восьмого элемента. И, второй и третий входы которого подключены к прямым выходам соответственно первого и второго триггеров, 5 а выход — к входу повторного запуска генератора импульсов, третьи входы шестого и седьмого элементов И соединены с прямым выходом третьего триггера. 10

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

Устройство содержит регистры 1-3, предназначенные для промежуточного хранения сравниваемых чисел и допус- 15 тимой разницы, счетчики 4-6; предназначенные для определения разностей и выполненные в виде последовательных вычитающих счетчиков с непосредственными связями, триггеры 7-9, 20 предназначенные для хранения информации в переполнении счетчиков, генератор 10 импульсов, элемент И 11„ предназначенньй для формирования сигнала запуска генератора, элементы И 12-14, предназначенные для разрешения прохождения тактовых импульсов на информационные входы счетчиков, элемент ИЛИ 15 предназначенный для формирования сигнала разрешения ЗО ,прохождения тактовых импульсов через элемент И 14, элементы И 16, Ш1И 17, предназначенные для формирования сигнала "Останов" генератора, элементы

l, Ч 18-20,элемент ИЗИ 21,предназначен- 35 ные для формирования режима отбора

TIocJIeä0âàòåëüHoeòè чисел, удовлетворяющих заданным требованиям, входные шины 22-26, выходные шины 27"31, Устройство для сортировки чисел работает следующим образом.

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

Импульсом записи с входной шины

22 в регистр 1 и счетчик 4 (через установочные входы) заносится число A. Этот же импульс записи устанавливает триггер 7 в единичное состояние, на прямом выходе триггера 7 появляется сигнал, являющийся разрешающим для элементов И 11 и 12. Импульсом записи с входной шины 24 в регистр 3 и счетчик 6 (через установочные входы) заносится допустимая разность " число P . Этот же импульс записи устанавливает триггер 9 в нулевое состояние. На инверсном выходе триггера 9 появляется сигнал, являющийся разрешающим для элемента H 11.

На входной шине 26 устанавливается один из режимов отбора:

1А-в„i,1 -8;1,1 -Я; =е

11мпульсом записи с входной шины

23 в регистр 2 и счетчик 5 (через установочные входы) заносится первое число В„ иэ последовательности чисел В,, Этот же импульс .записи устанавливает триггер 8 в единичное состояние, следовательно, с выхода элемента ИЛИ 15 на элемент И 14 поступает сигнал, запрещающий прохождение тактовых импульсов через элемент И 14 на информационный (счетный) вход счетчика б. На прямом выходе триггера 8 появляется сигнал, являющийся разрешающим для элемента И 13. Этот же сигнал поступает на третий вход элемента .И 11. Па выходе элемента И 11 появляется сигнал, поступающий в генератор 10 и являющийся разрешающим для выработки тактовых импульсов. С входной шины 25 на генератор 10 подается сигнал, по которому на выходе генератора формируются тактовые импульсы, поступаюаггге через элементы И 12 и 13 на информационные входы счетчиков 4 и 5 соответственно, и производящие последовательное вычитание единиц из содержимого счетчиков 4 и 5. Если

8,1 4 A то импульс переполнения появляется на выходе счетчика 5 раньше, чем на выходе счетчика 4.,Этот импульс устанавливает триггер 8 в нулевое состояние, на прямом выходе триггера 8 появляется сигнал, запрещающий дальнейшее прохождение тактовых импульсов через элемент И 13 на вход счетчика 5. На инверсном выходе триггера 8 появляется сигнал, проходящий через элемент KBI 15 на вход элемента И 14 и являющийся разрешающим для прохождения тактовых импульсов через элемент И 14 на информационный вход счетчика б. С инверсного выхода триггера 8 сигнал поступает также на выходную шину 29 и свидетельствует о том, что В, А, В счетчике 4 в этот момент находится число, равное разности (А-В>).

Тактовые импульсы, поступая через элементы И 12 и 14 на информационные входы счетчиков 4 и 6, производят последовательное вычитание еПи1051

7 ниц из содержимого счетчиков 4 и б.

Если (А-П )сЕ, то импульс переполнения появляется на выходе счетчика

)4 раньше, чем.на выходе счетчика б.

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

На инверсном выходе триггера 7 появляется сигнал, поступающий .на выходную шину 27 и на вход элемента И 16, На выходе элемента И 16 появляется сигнал, означающий, что (А-В,).< Е, Этот сигнал поступает на выходную шину 28.

Если на входной шине, 26 есть сигнал, означающий, что из последова" тельности В„ следует отбирать числа, удовлетворяющие условию (A"D„)

17 осуществляется установка в исходное состояние триггеров :7 и 9 (единичное для триггера 7 и нулевое— для триггера 9) и запись содержимого регистров 1 и 3 (через установочные входы) в счетчики 4 и 6 соответственно..Таким образом, после сравнения ..числа А с первым числом из последовательности В, устройство автоматически устанавливается в следующее состояние. В регистре 1 и счетчике 4 записано число A в регистре 3 и . счетчике 6 записано число Е, триг50 гер 7 установлен в единичное состояние, триггер 9 установлен в нулевое состояние, на входе элемента И 12 сигнал, разрешающий прохождение тактовых импульсов, на входе элемента

И 14 сигнал, запрещающий прохождение ,тактовых импульсов, генератор 10 не вырабатывает тактовых импульсов.

С приходом следующего числа Bg из последовательности В импульсом запичи с входной шины 23 в регистр

2 и счетчик 5 (через установочные входы) заносится число Pg. Этот же импульс записи устанавливает тригге1

8 в единичное состояние, следовательно, с выхода элемента ИЛИ 15 на элемент И 14 поступает сигнал, запрещающий прохождение тактовых импульсов через элемент И 14 на информационный вход счетчика б, На прямом выходе триггера 8 появляется сигнал, являющийся разрешающим для элемента И 11, На выходе элемента И

11, появляется сигнал, поступающий в генератор 10 и являющийся разрешающим для выработки тактовых импульсов, Таким образом, элемент ИЛИ 17 организует выработку сигнала, запускающего генератор 10 при поступлении очередного числа из последовательности В;, Тактовые импульсы с выхода генератора 10 через элементы И 12 и 13 поступают на информационные входы. счетчиков 4 и 5 соответственно, производя последовательное вычитание единиц из содержимого счетчиков 4 и

5. Если 02> А, то импульс переполнения появляется на выходе счетчика 4 раньше, чем на выходе счетчика 5, Этот импульс устанавливает триггер

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

12 на вход счетчика 4, Этот же сигнал через элемент ИЛИ )5 поступает на вход элемента И 14 и является разрешающим для прохождения тактовых импульсов через элемент И 14 на информационный вход счетчика 6. С инверсного выхода триггера 7 сигнал поступает на выходную шину 27 и свидетельствует о том, что В >А. В счетчике 5 в этот момент находится число, равное разности (B -А), Тактовые импульсы, поступая через эле.— менты И 13 и )4 на информационные входы счетчиков 5 и 6, производят последовательное вычитание единиц из содержимого счетчиков 5 и 6. Ес ли (В -А)>Е, то импульс переполнения на выходе счетчика б появляется раньше, чем на выходе счетчика 5. Импульс переполнения с выхода счетчика б устанавливает триггер 9 в единичное состояние, на прямом выходе триггера 9 появляется сигнал, постчпанмпий

9, 10515 на выходную шину ЗО и означающий, что {В11"A)>f так как условием отбора чисел иэ последовательности 8 .:;было )A-В; j< 6.,а (В -А)>Е„ то на вы" ходе элемента ШШ 21 появляется сиг" нап, запрещающий выдачу содержимого регистра 2 на выходную шину.31. Если условием отбора является (А-В ), то сигнал с прямого выхода триггера 9 через элементы И 19 и ИЛИ 21 по- 19 ступает на регистр 2 и разрешает выдачу содержимого регистра 2 на выходную шину 31.

Сигнал с прямого выхода триггера 9 через элемент ИЛИ 17 поступает на генератор IG и останавливает его.

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

Сигнал с выхода элемента ИЛИ 17 поступает на входы триггеров 7 и 9, 2О устанавливая их в исходное состояние, и осуществляет запись содержимого регистров I и 3 в счетчики 4 и 6 (через установочные входы) соответственно. Следовательно, после сравне- 25 ния числа А с вторым числом 8g иэ последовательности 8 устройство устанавливается в исходное состояние.

Ири иоступлении следующего числа из последовательности В устройство работает аналогичньж образом. . Если разность чисел А и В; равна f то одновременно появляются сигналы на выходных шинах 28 и 30.

31 10 .

Если условием отбора чисел является

{А"В ) Г, о чем свидетельствует разрешающий сигнал, поступающий с входной шины 26 на вход элемента И 20, ".o сигнал с выхода элемента И 20 через элемент ИДИ 21 поступает на рег; стр 2 и разрешает выдачу содержимого регистра 2 на выходную шину 31.

Таким образом, устройство. сравнивает число А с числами последовательности В, определяет, находится ли разность (А-В„ ) в пределах допустимой разности и осуществляет отбор чисел из последовательности В по

/ одному или совокупности заданных условий (1А 8 t Å IA"8 Ж1 IA-Ц И °

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

Так при работе с числами, пред". ставленными восьмиразрядным двоичным кодом, апнаратурные затраты по сравнению с базовым объектом увеличиваются примерно на 13, при этом значительно расширяется область применения устройства.

1051531

Составитель Е. Иванова

Редактор E. Папй Техред N,Êîñòèê КорректорВ. Бутяга

Заказ 8667748 Тираж 706

Подписное

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

113035 Москва Ж-35 Раушская наб.д д. 4/5

Р И

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