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

59

45

КЛ

4 СО

, регистры 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, информационные входы АО, адресные выходы 41, информационные выходы 42, выходы разрешения считывания 43 и записи 44, выход окончания работы устройства 45. Упорядочение заключается в том, что

нуль, перемещаются во внешнем ЗУ.. в начало зоны, а все числа, в заданном разряде которых - единица, перемещаются в конец зоны. Числа последовательно считываются от начала зоны к концу, пока не будет считано число с единицей в заданном разряде, и последовательно считываются от конца зоны к началу, пока не будет считано число с нулем в заданном разряде. Затем считанные числа записьюаются в ЗУ одно на место другого и процесс повторяется, пока не будут обработаны все

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит регистры начала 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 ил.

все числа, в заданном разряде которых j числа. 1 ил.

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

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

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

Устройство содержит регистры 1 и начала и конца зоны соответственно, счетчики 3 и 4 начала и конца зоны соответственно, элемент 5 сравнения, регистры 6-8, мультиплексоры 9 и 10, триггеры 11-13, элементы И 14-20, элементы ИЛИ 21-25, элементы 26 и 27 задержки, группы элементов И 28-35 группы элементов ИЛИ 36 и 37, тактовый вход 38, вход 39 запуска, информационные входы (шины) 40, адресные выходы (шины) 41, информационные выходы 42, выходы (шины) 43 и 44 разрешения считывания и записи соответственно и выход 45 окончания работы устройства.

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

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

5

0

5

5

0

0

5

Триггеры 11-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 появляется сигнал, сигнализирующий об окончании работы устройства. Этот сигнал поступает также на инверсный

вход элемента И 14, закрывая его и запрещая тем самым поступление тактовых импул ьсов в устройство, В противном Т лучае цикл работы устройства повторяется. Если проверяемьш разряд числа - единица, то появляется сигнал на прямом выходе мультиплесора 9, который переключает триггер II в единичное состояние, переводя устройство из режима считывания по начальному адресу в режим считывания по конечному адресу. Очередной тактовый импульс через элементы И 14 16 и 20 и ИЛИ 24 возлуждает шину 43 разрешения считывания и разрешает поступление через элементы И группы 31 и элементы ШШ группы 36 адреса конца зоны из счетчика 4 на выходные адресные шины 41 устройства, а также-разрешает запись последнего числа массива из ЗУ через элементы И группы 35 в регистр 7. При равенстве заданного разряда числа единице появляется сигнал на прямом выход мультиплексора 10, который поступает через элемент ИЛИ 25 на счетный выхо вычитающего счетчика 4, т,е. в счетчике будет записан адрес предпоследнего числа массива сортируемых чисел При поступлении следующих тактовых импульсов цикл работы устройства повторяется, пока на инверсном выход мультиплексора 10 не появится единичный сигнал, который переведет трште 13 в единичное состояние, переключив тем самым устройство в режим записи по конечному адресу. Далее происходит запись числа с единичным заданным разрядом из регистра 6 в ЗУ по только что считанному адресу, по которому находилось число с нулевым выбранным разрядом. Очередной тактовый импульс через элементы И 16 и 19 возбуждает шину 44 записи и через элементы И 18 и ИЛИ 22 разрешает поступление адреса из счетчика 4 на выходные адресные шины 41 устройства, а из регистра 6 - на информационные выходы 42 устройства, а также переводит триггер 12 в единичное состояние разрео1ая тем самым прохождение сигнала через элемент И 17 и переключая тем самым устройство в режим записи по адресу, задаваемому счетчиком 3. При поступлении очередного тактового импульса устройство работает анало- гично, выводя число в ЗУ из регистра 7 по адресу, задаваемому счетчиком

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

5

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

Устройство для упорядочения массива чисел, содержащее регистры начала и концы зоны, счетчики начала и конца зоны, элемент сравнения, первый и второй регистры, первый и второй триггеры, семь групп элемен-. тов И, две группы элементов ИЛИ, семь элементов И, четыре элемента ИЛИ и два элемента задержки, причем выход i-ro разряда регистра начала зоны, где ,2,...,п; п - количество разрядов адреса чисел ма1ссива, соединен с первым входом i-i o элемента И пер- ,с вой группы, вторые входы которых подключены к входу запуска устройства, выходы i-x элементов I первой и второй групп соединены с i-ми информационными входами счетчиков соответственно начала и конца 3OHti, выходы i-x разрядов которых соединены с L-MH разрядами соответственно первой и второй групп информационньк входов элемента сравнения и с первыми входами i-x элементов И соответственно третьей и четвертой групп, выходы которых соединены соответственно с-первым и вторым входами i-ro элемента ИЛИ первой группы выход которого является выходом i-ro разряда адреса устройства, выход элемента сравнения является выходом окончания работы устройства и соединен с инверсным входом первого элемента И, прямой вход которого подключен к тактовому входу устройства, а выход соединен с первыми входами второго и третьего элементов И, вторые нходы которых подключены соответстиенно к инверсно0

0

5

0

5

му и прямому выходам первого триггера, вход установки в нулевое состояние которого объединен с входом установки в нулевое состояние второго триггера, прямой и инверсный выходы которого соединены с первыми входами соответственно четвертого и пятого элементов И, выходы которых соединены с первыми входами соответственно первого, и второго элементов ИЛИ, а также с первыми входами элементов И пятой и шестой групп, выход j-ro элемента И седьмой группы, где ,2, ...,mj m - количество разрядов чисел массива, соединен с j-м информацион- ым входом первого регистра, выходы J-X разрядов первого и второго регистров соединены с вто- - рыми входами j-x элементов И соответ- ственно шестой и пятой групп, выходы которых соединены соответственно с первым и вторым входами j-го элемента ИЛИ второй группы, выход которого является J-M информационным выходом устройства, выход четвертого элемента И соединен с входом первого элемента задержки, выход второго элемента задержки соединен с первьм входом третьего элемента ИЛИ, вторые входы четвертого и пятого элементов И объединены j первый вход шестого элемента И объединен с первым входом седьмого элемента И, выход которого соединен с первым входом четвертого элемента ИЛИ, выход второго элемента ИЛ соединен с вторыми входами элементов И четвертой группы, первые входы элементов И второй группы объединены, вторые входы элементов И третьей группы объединены, отличающееся тем, что, с целью повышения быстродействия, в него введены третий регистр, два мультиплексора, восьмая группа элементов И, третий триггер и пятый элемент ШШ, причем выход i-ro разряда регистра конца зоны соединен с вторым входом i-ro элемента И второй группы, первый вход которого подключен к входу запуска устройства, выходы второго и третье- Составитель В.Гор Редактор А.Ревин Техред Л.Сердюков

го элементов И соединены с вторьми входами соответственно первого и второго элементов ИЛИ, а также с первыми входами элементов И соответственно седьмой и восьмой групп, j-й информационный вход устройства соединен с вторыми входами j-го элемента К седьмой группы и j-ro элемента И восьмой группы, выход которого соединен с J-M информационным входом второго регистра, выходы j-x разрядов первого и второго регистров соединены с j-ми информационными входам первого и второго мультиплексоров соответственно, прямой и инверсный Ьы- ходы которых соединены с входами ус тановки в единичное состояние соотвественно первого и третьего триггеров входы установки в нулевое состояние которых подключены к выходу четвертого элемента И, выход первого элемента задержки соединен с входом второго элемента задержки и первым входом пятого элемента ИЛИ, выходы третьего рех истра соединены с управляющими входами первого и второго мультиплексоров соответственно, инверсный и прямой выходы которых соединены с вторыми входами соответственно третьего и пятого элементов ИЛИ, выходы которых соединены соответственно с суммирующим входом счетчика начала зоны и вычитающим входом счетчика конца зоны, выход второго элемента И соединен с вторым входом четвертого элемента ИЛИ, выход которого является выходом разрешения считьшания устройства, выход третьего элемента И соединен с первым входом шестого элементами, выход которого является выходом разрешения записи устройства и соединен с вторым входом пятого элемента И, выход которого соединен с входом установки в единичное состояние второго триггера, выход первого элемента liJIH соединен с вторыми входами элементов И третьей группы, прямой и инверсный выходы третьего триггера соединены с вторыми входами соот - ветственно шестого и седьмого элементо

Корректор Э.Лончакова