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

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

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

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

Устройство содержит регистры 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.

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

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

348272

входные информационные шины -39 устройства и записывается в регистр 3. Будем условно называть числа, записанные в регистре 3, числами А, а

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

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

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

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

25 ции из регистра 4 на информационные. I выходы-44 устройства. Этот же сигнал,

задержанньш в элементе 26 задержки на время, необходимое для записи ин- фо1жации в ЗУ, переключает триггер 11 в единичное состояние. Третий тактовый HMnyjjbc, поступив по входу 38 и пройдя элементы И 14 и 15, разрешает поступление через элементы И группы 31 и элементы ИЛИ группы 35 адреса

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

И группы 33 и элементы ШШ группы 36 . информаи;ии из регистра 3 на информационные выходы устройства 44, а через элементы И группы 30 перепись информаи;ии из регистра 3 в регистр 4, а также, пройдя через элемент ИЛИ 21, возб;5Г)кдает выход 42 записи. Этот же , задержанный в элементе 25

- задержки на время, необходимое для записи информации в ЗУ, переключает триггеры 10 и 11 в нулевое состояние, а таюке, пройдя через элементы ИЛИ 22 и И 17, поступает на счет50 ный вход счетчика 6, увеличивая содержимое счетчика на единицу, т.е. в счетчике записывается адрес следующей за начальной зоны. При поступлении четвертого тактового импульса

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

40

чисел А и В возможны два случая работы устройства: если , то устройство работает аналогично описанному; если , то появляется сигнал на втором выходе схемы 9 сравнения, который, пройдя через элемент И 19, на второй вход которого поступает четвертый тактовый импульс, задержанный в элементе 27 задержки на время , необходимое для выбора и считывания информации из ЗУ, элементы ИЛИ 22 и И 17, поступает на счетный вход счетчика 6, увеличивая содержимое его на единицу, т.е. в счетчике записывается адрес следующей зоны. При поступлении очередного тактового импульса устройство работает аналогично описанному до тех пор, пока содержимое счетчика 6 не будет равно содержимому регистра адреса . конца зоны 2. При равенстве значений, записанных в счетчике 6 и регистре 2, появляется сигнал на втором выходе схемы 8 сравнения, который, пройдя через элемент И 18 (на второй вход последнего поступает очередной тактовый импульс с выхода элемента ИЛИ 22), поступает на счетный вход счетчика 5, увеличивая содержимое его на единицу, т.е. в счетчике записывается адрес следующей за начальной зоны, проходит через элемент ИЛИ 20, элемент 24 задержки, разрешает перепись информации из счетчика 5 в счетчик 6 через элементы И группы 29 и переключает регистры 3 и 4 в исходное состояние. При поступлении очередного тактового импульса устройство.работает так же, как при поступлении первого тактового сигнала и так до тех пор, пока значение в счетчике 5 не будет равно значению адреса конца зоны, записанному в регистре 2. Тогда на выходе схемы 7 сравнения появляется сигнал, поступающий на выход 40 устройства и сигнализирующий об окончании работы устройства, а также на ин версный вход элемента И 12, закрывая его и запрещая тем самым поступление тактовых импульсов в устройство.

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

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

348274

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

причем информационные входы устройст- 5 ва подключены к соответствующим

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

выходы которых соединены с соответствующими инфopмaциoнны D входами регистра результата, выходы разрядов которого подключены к второй группе t5 входов схемы сравнения и информационным входам соответствующих выходных элементов И первой группы, выходы второго регистра соединены с информационными входами соответствующих 0 элементов И переписи второй группы, выходы третьего регистра подключены к первым группам входов второй и третьей схем сравнения, выход второй схемы сравнения подключен к управляю- 5 .щему входу первого элемента И, выход равенства третьей схемы сравнения соединен с первым входом второго элемента И,вькод которого соединен с пер- вьт входом первого элемента ИЛИ, о т- 0 л и чающееся тем, что, .с целью уменьшения аппаратурных затрат с увеличением количества сортируемых чисел, в него введены второй счетчик, третья и четвертая группы выходных элементов И, две группы выходньпс элементов ИЛИ, элементы задержки, причем вход тактовых импульсов устройства подключен к информационному входу первого элемента И, выход кото- и рого соединен с первыми входами третьего и четвертого элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам первого триггера, вход установки в , единичное состояние которого соединен с выходом Больше первой схемы сравнения, выход четвертого элемента И соединен с первыми входами пятого и шестого элементов. И, вторые 0 входы которых подключены соответственно к прямому и инверсному выходам второго триггера, вход установки в

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

5

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

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

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

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

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

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

0

р-Ш Щ -ШШ-Ш

I - - - г I

т-Ш

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

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

Составитель Е. .Иванова Техред М.Ходаннч ;

Заказ 2986/51 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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