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

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано при реализации технических средств ЭВМ. Цель изобретения - уменьшение аппаратур- , ных затрат с увеличением количества сортируемых чисел. Устройство содержит три регистра, в которые записаны адрес начала и конца зоны ЗУ и анализируемое число, регистр результата, счетчики, схемы сравнения, элементы И, ИЛИ, триггеры, группы элементов И.переписи, группы выходных элементов И, группы выходных элементов ИЛИ. Предлагаемое устройство позволяет организовать запись отсортированных чисел с адреса начала зоны в ЗУ„общего назначения и заканчивает работу при совпадении адреса текущего числа с адресом конца зоны сортировки. 1 ил. о (Л

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

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

РЕСПУБЛИН (50 4 С 06 F 7/06

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

Ь":""

ОПИСАНИЕ ИЗОБРЕТЕНИ5} ".

Н А BT0PCH0MV СВИДЕТЕЛЬСТВУ

"Ч, / (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ

МАССИВА ЧИСЕЛ (21) 3730024/24-24 (22) 21.02.84 (46) 30.05.86. Бюп. № 20 (72) Н.И. Крыпов и Н.Н. Шубина (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

¹ 981988, кл. G 06 F 7/06, 1980. . Авторское свидетельство СССР № 1107118, кл. С 06 F 7/06, 1983. (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано при реализации технических средств 3BN. Цель

„Л0„„12 4 2 А1 изобретения — уменьшение аппаратур-, ных затрат с увеличением количества сортируемых чисел. Устройство содержит три регистра, в которые записаны адрес начала и конца зоны ЗУ и анализируемое число, регистр результата, счетчики, схемы сравнения, элементы И, ИЛИ, триггеры, группы элементов И переписи, группы выходных элементов И, группы выходных элементов ИЛИ. Предлагаемое устройство позволяет организовать запись отсортированных чисел с адреса начала зоны в ЗУ общего назначения и заканчивает работу при совпадении адреса текущего числа с адресом конца зоны сортировки. 1 ил.

В исходном состоянии в регистре записи адрес начала зоны, а в регистре 2 — адрес конца зоны массива чисел, записанного н запоминающем устройстве (ЗУ) общего назначения, который надо упорядочить. В регистрах 3 и 4 записано минимальное машинное число. Счетчики 5 и 6 и триггеры lO и 11 находятся в нулевом состоянии. При поступлении сигнала по входу 38 запуска содержимое регистра 1 переписывается через элементы И группы 28 в счетчик 5, а также по этому же сигналу, задержанному в элементе 24 задержки на время, необходимое для переписи информации из регистра 1 в счетчик 5, через элементы И группы 29 из счетчика 5 н счетчик 6. Первый тактовый импульс, поступив по входу 37 и пройдя через .элемент И 13, возбуждает пину 41 считывания, а также, пройдя через элемент ИЛИ 23, разрешает поступление через элементы И группы 32 и элементы ИЛИ группы 35 адреса начальной зоны из счетчика 6 на выходные адресные шины 43 устройства. Сигналы по выходам 41 считывания и выходным адресным шинам 43 устройства поступают в ЗУ, н котором происходит считывание информации, записанной по данному адресу, т.е. первого числа массива, которое поступает из ЗУ на

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

Цель изобретения — уменьшение аппаратурных затрат с увеличением количества сортируемых чисел.

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

Устройство содержит регистры 1-3 и регистр 4 результата, счетчики 5 и 6, схемы 7-9 сравнения, триггеры

10 и 11, элементы И 12-19, элементы

ИЛИ 20-23, элементы 24-27 задержки, группы 28-30 элементов И переписи, группы 31-34 выходных элементов И, группы 35 и 36 элементов ИЛИ, вход

37 тактовых импульсов, вход 38 запуска, информационные входы 39, выход 40, выходы разрешения считывания 41, записи 42, адресные 43, информационные 44.

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

1234827 2 нходные информационные шины 39 устройства и .записывается в регистр 3.

Будем условно называть числа, записанные в регистре 3, числами А, а числа, записанные в регистре 4, числами B. После записи числа А в регистр 3 числа А и В сравниваются н схеме 9 сравнения. После сравнения чисел А и В появляется сигнал

10 на первом выходе (А>В) схемы 9 сравнения (так как поступившее число А всегда больше минимального машинного числа), который переключает триггер 10 в единичное состояние. Второй

15 тактовый импульс поступает по входу

37 и проходит элементы И 14 и 16.

Далее, пройдя через элемент ИЛИ 21, возбуждает выход 42 записи, а пройдя через элемент ИЛИ 23, разрешает

20 поступление через элементы И группы 32 и ИЛИ группы 35 адреса зоны из счетчика 6 на адресные выходы 43 устройства, а через элементы И группы

34 и элементы ИЛИ группы 36 информации из регистра 4 на информационные. ! выходы.44 устройства. Этот же сигнал, задержанный в элементе 26 задержки на время, необходимое для записи информации в ЗУ, переключает триггер 11 в единичное состояние. Третий тактовый импульс, поступив по входу 38 и пройдя элементы И 14 и 15, разрешает поступление через элементы И группы

31 и элементы ИЛИ группы 35 адреса

35 зоны из счетчика 5 на адресные выхоI ды устройства 43, через элементы

И группы 33 и элементы ЮЫ группы 36 информации из регистра 3 на информационные выходы устройства 44, а через элементы И группы 30 перепись информации из регистра 3 в регистр 4, а также,, пройдя через элемент ИЛИ 21, возбуждает выход 42 записи. Этот же сигнал, задержанный в элементе 25 задержки на время, необходимое для записи информации в ЗУ, переключает триггеры 10 и 11 в нулевое состоя" ние, а та|сже, пройдя через элементы

ИЛИ 22 и И 17, поступает на счетный вход счетчика 6, увеличивая содержимое счетчика на единицу, т.е ° в счетчике записывается адрес следую" щей за начальной зоны. При поступлении четвертого тактового импульса

S устройство работает так же, как при поступлении первого тактового импульса, и в регистр 3 записывается второе число массива. После сравнения

1234827 чисел А и В возможны два случая работы устройства: если А>В, то устройство работает аналогично описанному; если АВ, то появляется сигнал на втором выходе схемы 9 сравнения, который, пройдя через элемент И 19, на второй вход которого поступает четвертый тактовый импульс, задержанный в элементе 27 задержки на время, необходимое для выбора и считы- 10 вания информации из ЗУ, элементы

ИЛИ 22 и И 17, поступает на 0÷åòíûé вход счетчика 6, увеличивая содержимое его на единицу, т.е. в счетчике записывается адрес следующей зо- t5 ны. При поступлении очередного такто— вого импульса устройство работает аналогично описанному до тех пор, пока содержимое счетчика 6 не будет равно содержимому регистра адреса . 20 конца зоны 2. При равенстве значений, записанных в счетчике 6 и регистре 2, появляется сигнал на втором выходе схемы 8 сравнения, который, пройдя через элемент И 18 (на 25 второй вход последнего поступает очередной тактовый импульс с выхода элемента ИЛИ 22), поступает на счетный вход счетчика 5, увеличивая содержимое его на единицу, т.е. в 30 счетчике записывается адрес следующей за начальной зоны, проходит через элемент ИЛИ 20, элемент 24 задержки, разрешает перепись информации из счетчика 5 в счетчик 6 через элементы И группы 29 и переключает регистры 3 и 4 в исходное состояние.

При поступлении очередного тактового импульса устройство. работает так же, как при поступлении первого тактового сигнала и так до тех пор, пока значение в счетчике 5 не будет равно значению адреса конца зоны, записанному в регистре 2. Тогда на выходе схемы 7 сравнения появляется 45 сигнал, поступающий на выход 40 устройства и сигнализирующий об окончании работы устройства, а также на инверсный вход элемента И 12, закрывая его и запрещая тем самым поступление тактовых импульсов в устройство.

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

Устройство для упорядочения масси-55 ва чисел, содержащее три регистра, регистр результата, первый счетчик, три группы элементов И переписи, три схемы сравнения, две группы выходных элементов И, два триггера, вссемь элементов И, четыре элемента ИЛИ, причем информационные входы устройства подключены к соответствующим информационным входам первого регистра, выходы которого подключены к первой группе входов первой схемы сравнения и информационным входам соответствующих элементов И переписи, выходы которых соединены с соответст— вующими информационными входами регистра результата, выходы разрядов которого подключены к второй группе входов схемы сравнения и информационным входам соответствующих выходных элементов И первой группы, выходы второго регистра соединены с информационными входами соответствующих элементов И переписи второй группы, выходы третьего регистра подключены к первым группам входов второй и третьей схем сравнения, выход второй схемы сравнения подключен к управляющему входу первого элемента И, выход равенства третьей схемы сравнения соединен с первым входомвторого элемента И,выход которого соединен с первым входом первого элемента ИЛИ, о тл и ч а ю щ е е с я тем, что, .с целью уменьшения аппаратурных затрат с увеличением кдличества сортируемых чисел, в него введены второй счетчик, третья и четвертая группы выходных элементов И, две группы выходных элементов ИЛИ, элементы задержки, причем вход тактовых импульсов устройства подключен к информационному входу первого элемента И, выход которого соединен с первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам первого триггера, вход установки в единичное состояние которого соединен с выходом "Больше" первой схемы сравнения, выход четвертого элемента И соединен с первыми входами пятого и шестого элементов. И, вторые входы которых подключены соответственно к прямому и инверсному выходам второго триггера, вход установки в ноль которого объединен с входом установки в ноль первого триггера и первым входом второго элемента ИЛИ и подключен к выходу первого элемента задержки, вход которого соединен с выходом пятого элемента И, первым

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

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

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

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

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

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

1234827

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

Техред М.Ходанич

Корректор Е. Рошко

Редактор Е. Копча

Подписное

Заказ 2986/51

Тираж 671

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4