Устройство для упорядочения массива чисел

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит регистры начала 1 и конца 2 зоны, счетчики начала 3 и конца 4 зоны, элемент сравнения 5, регистры 6, 7, 8, мультиплексоры 9, 10, триггеры 11, 12, 13, элементы И 14, 15, 16, 17, 18, 19, 20, элементы ИЛИ 21, 22, 23, 24, 25, элементы задержки 26, 27, группы элементов И 28, 29, 30, 31, 32, 33, 34, 35, группы элементов ИЛИ 36, 37, тактовый вход 38, вход запуска 39, информационные входы 40, адресные выходы 41, информационные выходы 42, выходы разрешения считывания 43 и записи 44, выход окончания работы устройства 45. Упорядочение заключается в том, что все числа, в заданном разряде которых - нуль, перемещаются во внешнем ЗУ в начало зоны, а все числа, в заданном разряде которых - единица, перемещаются в конец зоны. Числа последовательно считываются от начала зоны к концу, пока не будет считано число с единицей в заданном разряде, и последовательно считываются от конца зоны к началу, пока не будет считано число с нулем в заданном разряде. Затем считанные числа записываются в ЗУ одно на место другого и процесс повторяется, пока не будут обработаны все числа. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

4ь

С0

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

r0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4351691/24-24 (22) 28.12.87 (46) 15.07.89, Бюл. В 26 (72) В.Г.Водяницкий (53) 681.325.5(088.8) (56) Авторское. свидетельство СССР

В 1107118, кл. G 06 F 7/06, 1983, Авторское свидетельство СССР

У 1234827, кл. G 06 F 7/06, 1984.

„„SU„„14 4001 А1 (51)4 С 06 F 7/06

2 (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ YiACСИВА ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения — повышение быстродействия. Устройство содержит регистры начала 1 и конца 2 эоны, счетчики нача-. ла 3 и концы 4 зоны, элемент 5 срав1494001 цени), регистры 6, 7, 8, мультиплексоры 9, 10, триггеры 11, 12, 13, элементы И 14, l5, 16, 17 18, 19, 20, элементы ИЛИ 21, 22, 23, 24, 25, элементы задержки 26, 27, группы элемен5 тон И 28, 29, 30, 31, 32, 33, 34, 35, группы элементов ИЛИ 36, 37, тактовьй нход 38, вход запуска 39, информаци-. онные входы 40, адресные выходы 41, информационные выходы 42, выходы разрешения считывания 43 и записи 44, выход окончания работы устройства 45.

Упорядочение заключается в том, что все числа, в заданном разряде которых !5

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

Цель изобретения — понышение быстродействия устройства. 25

На чертеже изображена схема предлагаемого устройства.

Устройство содержит регистры 1 и 2 начала и конца зоны соответственно, счетчики 3 и 4 начала и конца эоны 30 соответственно, элемент 5 сраннения, регистры 6-8, мультиплексоры 9 и 10, триггеры Ii — 13, элементы И 14-20, элементы ИЛИ 21-25, элементы 26 и 27 задержки группы элементов И 28-35 35

) группы элементов ИЛИ 36 и 37, тактовый вход 38, вход 39 запуска, информационные входы (шины) 40, адресные выходы (шины) 41, информационные выходы 42, выходы (шины) 43 и 44 раэ- 4О решения считывания и записи соответственно и выход 45 окончания работы устройства, Устройство работает следующим образом. 45

В исходном состоянии в регистре 1 записан адрес начала зоны, в регистре 2 — адрес конца зоны массива чисел, записанного в запоминающем устройстве (ЗУ) общего назначения, который надо упорядочить. В регистре 8 записан номер двоичного разряда числа, по которому необходимо выполнить упорядочение. Упорядочение заключается н том, что все числа, в выбранном разряде которых — нуль, перемещаются н ЗУ в начало зоны, а все числа, н выбранном разряде которых единица, перемещаются в конец зоны. нуль, перемещаются во внешнем ЗУ,в начало зоны, а все числа, в заданном разряде которых — единица, перемещаются н конец эоны. Числа последовательно считываются от начала зоны к концу, пока не будет считано число с единицей в заданном разряде, и последовательно считываются от конца эоны к началу, пока не будет считано число с нулем в заданном разряде, Затем считанные числа записываются в ЗУ одно на место другого и процесс повторяется, пока не будут обработаны все числа. 1 ил.

Триггеры II — 13 находятся в нулевом состоянии. При поступлении сигнала по входу 39 запуска содержимое регистра 1 переписывается через элементы

И группы 28 в счетчик 3, а содержимое регистра 2 через элементы И группы 29 — в счетчик 4.

Первый тактовый импульс, поступив по входу 38 и пройдя через элементы

И 15 и ИЛИ 24, возбуждает шину 43 разрешения считынания, а также, пройдя через элемент ИЛИ 21, разрешает поступление через элементы И группы

30 и элементы ИЛИ группы 36 адреса начала зоны иэ счетчика 3 на выходные адресные шины 41 устройства. Сигналы по этим выходам поступают в ЗУ, в котором происходит считывание чис.ла,записанного по данному адресу (т.е. первого числа массива), которое поступает из ЗУ на входные информационные шины 40 устройства и через элементы И группы 34 записывается в регистр 6 и поступает на входы мультиплексора 9, который осуществляет выборку из числа двоичного разряда, номер которого записан в регистре 8.

При равенстве проверяемого разряда числа нули появляется сигнал на инверсном выходе мультиплексора 9, который через элемент ИЛИ 23 поступает на счетньй вход счетчика 3, увеличивая его содержимое на единицу, т.е. в счетчике записывается адрес следующего числа ° Содержимое счетчикон 3 и

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

1494001 вход элемента И 14, закрывая его и запрещая тем самым поступление тактовых импульсов н устройство. В противном случае цикл работы устройст5 на повторяется, Если проверяемый разряд числа — единица, то появляется сигнал на прямом выходе мультиплексора 9, который переключает триггер

ll в единичное состояние, переводя 1р устройство из режима считывания по начальному адресу в режим считывания по конечному адресу. Очередной тактовый импульс через элементы И 14, 1Ь и 20 и ИЛИ 24 возлуждает шину 43 )5 разрешения считывания и разрешает поступление через элементы И группы

31 и элементы ИЛИ группы 36 адреса конца зоны из счетчика 4 на выходные адресные шины 41 устройства, а 20 также разрешает запись последнего числа массива из ЗУ через элементы

И группы 35 н регистр 7, При равенстве заданного разряда числа единице появляется сигнал на прямом выходе мультиплексора 10, который поступает через элемент ИЛИ 25 на счетный выход вычитающего счетчика 4, т,е. в счетчике будет записан адрес предпоследнего числа массива сортируемых чисел. Зр

При поступлении следующих тактовых импульсов цикл работы устройства повторяется, пока на иннерсном выходе мультиплексора 10 не появится единичный сигнал, котоРый пеРеведет триггер

13 в единичное состояние, переключив тем самым устройство в режим записи по конечному адресу. Далее происходит запись числа с единичным заданным разрядом из регистра 6 в ЗУ по 4р только что считанному адресу, по которому находилось число с нулевым выбранным разрядом. Очередной тактовый импульс через элементы И 16 и 19 возбуждает шину 44 записи и через эле- 45 менты И 18 и ИЛИ 22 разрешает поступление адреса из счетчика 4 на выходные адресные шины 41 устройства, а из регистра 6 — на информационные выходы 42 устройсr a, а также переводит триггер 12 в единичное состояние, разрешая тем самым прохождение сигнала через элемент И 17 и переключая тем самым устройство н режим записи по адресу, задаваемому счетчиком 3 °

При поступлении очередного тактового импульса устройство работает аналогично, выводя число в ЗУ из регистра

7 по адресу, задаваемому счетчиком

3, а также переводит, триггеры ll — 13 в в нулевое состояние, переключая тем самым устройство н режим считывания числа по адресу, заявляемому счетчиком 3. Этот же импульс, задержанный элементом 26 задержки на время записи числа в ЗУ поступает через элемент ИЛИ 25 на вход счетчика 4, уменьшая его значение на единицу, и, задержанный элементом 27 задержки на время работы элемента ИЛИ 25, счетчика 3 и элемента 5 сравнения, поступает через элемент ИЛИ 23 на вход счетчика 3, увеличивая его содержимое на единицу. Далее цикл работы устройства повторяется с приходом очередного тактового импульса.

Формула изобретения

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

ТоВ И, две группы элементов ИЛИ, семь элементов И, четыре элемента ИЛИ и два элемента задержки, причем выход

i-ro разряда регистра начала эоны, где i=1,2,...,n; n — количество разрядов адреса чисел массива, соединен с первым входом i-го элемента И первой группы, вторые входы которых подключены к входу запуска устройства, выходы i-x элементов 1 первой и вто— рой групп соединены с i-ми информа.ционными входами счетчиков соответственно начала и конца зоны, выходы

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

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

Корректор 3,Лончакова

Заказ 4111/45 Тираж 668 Подписное

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

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

Произволственно-издательский комбинат Патент", r.ужгород, ул. Гагарина,101 му и прямому выходам первого триггера, вход установки в нулевое состояние которого объединен с входом уста— новки в нулевое состояние второго триггера, прямой и инверсный выходы которого соединены с первыми входами соответственно четвертого и пятого элементов И, выходы которых соедине" ны с первыми входами соответственно первого,и второго элементов ИЛИ, а также с первыми входами элементов Е пятой и шестой групп, выход j-ro элемента И седьмой группы, где 3=1,2, ...,m„ m — количество разрядов чисел 15 массива, соединен с j-м информационным входом первого регистра, выходы -х разрядов первого и второго регистров соединены с вто- . рыми входами j-x элементов И соответ- 20 ственно шестой и пятой групп, выходы которых соединены соответственно с первым и вторым входами j -го элемента

ИЛИ второй группы, выход которого является 3 -м информационным выходом устройства, выход четвертого элемента

И соединен с входом первого элемента задержки, выход второго элемента задержки соединен с первым входом третьего элемента ИЛИ, вторые входы четвертого и пятого элементов И объединены первый вход шестого элемента И объединен с первым входом седьмого элемента И, выход которого соединен с первым входом четвертого элемента ИЛИ, выход второго элемента ЕЛИ

° ° 35 соединен с вторыми входами элементов

И четвертой группы, первые входы элементов h второй группы объединены, вторые входы элементов И третьей

40 группы объединены, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия,.в него введены третий регистр, два мультиплексора, восьмая группа элементов И, третий триггер и пятый элемент KIN, причем выход 1.-го разряда регистра конца эоны соединен с вторым входом i-го элемента И второй группы, первый вход

50 которого подключен к входу запуска устройства, выходы второго и третьеСоставитель В.Горохов

Редактор А,Ревин Техред JI,Сердюкова

ro элементов И соединены с вторыми входами соответственно первого и второго элементов ИЛИ, а также с первыми входами элементов И соответственно седьмой и восьмой групп, 3-й информационный вход устройства соединен с вторыми входами j -го элемента

Y. седьмой группы и j-ro элемента И восьмой группы, выход которого соединен с j ì информационным входом второго регистра, выходы j -x разря-. дов первого и второго регистров соединены с j ìè информационными входами первого и второго мультиплексоров соответственно, прямой и инверсный вьходы которых соединены с входами ус». тановки в единичное состояние соответственно первого и третьего триггеров, входы установки в нулевое состояние которых подключены к выходу четвертого элемента И, выход первого элемента задержки соединен с входом второго элемента задержки и первым входом пятого элемента ИЛИ, выходы третьего регистра соединены с управляющими входами первого и второго мультиплексоров соответственно, инверсный и прямой выходы которых соединены с вторыми входами соответственно треть его и пятого элементов ИЛИ, выходы которых соединены соответственно с суммирующим входом счетчика начала зоны и вычитающим входом счетчика конца зоны, выход второго элемента

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

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