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

 

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

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

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

РЕСПУБЛИК (я)ю G 06 F 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

СО

О (л) ! 0

iO

|О

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4834086/24 (2 ) 04.06.90 (45) 23.03.93. Бюл. ¹ 11 (71) Дзержинское опытно-конструкторское бюро автоматики Научно-производственного объединения "Химавтоматика" (72) В.Л,Авдоничев, В.Г,Водяницкий, О. .Столяров и С,Ю,Макаров (58) Авторское свидетельство СССР

¹ 1234827, кл, G 06 F 7/06, 1986.

Авторское свидетельство СССР №,1494001, кл, G 06 F 7/06, 1987. (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ

МАССИВА I VICEfl (57) Изобретение относится к автоматике и вычислительной технике и может быть исИзобретение относится к автоматике и вычислительной технике, Целью изобретения является расширение функциональных возможностей за счет упорядочивания массива чисел по нескольким двоичным разрядам.

На фиг. 1 представлена блок-схема предлагаемого устройства; на фиг. 2 — логическая диаграмма работы устройства; на фиг, 3 — схема блока упорядочения массива; на фиг. 4 — схема одного разряда, Устройство для упорядочения массива чисел содержит регистры адреса начала 1 и конца 2 массива чисел, регистр 3 количества

М разрядов чисел, вычитающий счетчик 4 номера разряда, блок аппаратной стековой памяти 5 адресов, зон, блок аппаратной стековой памяти 6 номера разряда М регистров, первый 7, второй 9 элементы сравнения, первый 10, второй 11, третий 12 — регистры, первый 13, второй 14, третий 15

„„Я2„„1803909 А1 пользовано при реализации технических средств ЭВМ. Целью изобретения является расширение функциональных возможностей устройства за счет упорядочения по нескольким разрядам. Устройство содержит регистры начала и конца зоны, счетчики начала и конца эоны, блок подготовки адресов начала и конца зоны, блок формирования номера разряда упорядочения массива чисел, блок памяти номера разряда, элементы сравнения, мультиплексоры, группы элементов И, ИЛИ, Устройство осуществляет упорядочение массива чисел по нескольким расположенным подряд двоичным разрядам. 2 з.п. ф-лы, 4 ил„1 табл. — ключи, первый 16, второй 17, третий 18— элементы И, первый 19, второй 20 — элементы ИЛИ, первый 21, второй 22, третий 23, четвертый 8 — элементы задержки, первый

24, второй 25, третий 26, четвертый 28, пятый 29 — мультиплексоры, тактовый вход 38, вход запуска 39, блок упорядочения массива (УР) 40. Регистры 10 и 11 собраны на

D-триггерах. Блок 40 содержит счетчики 41 и 42 начала и конца зоны соответственно, элемент 43 сравнения, регистры 44 — 45, мультиплексоры 46-47, триггеры 48-50, элементы И 51 — 57, элементы ИЛИ 58 — 62, элементы 63 — 64 задержки, группы элементов И

65 — 72, группы элементов ИЛИ 73 — 74, тактовый вход 75, вход запуска 76, информационные входы (шины) 77, адресные выходы (шины) 78, информационные выходы 79, выходы (шины) 80-81 разрешения считывания и записи соответственно, и выход окончания работы блока.

1803909

Блок 40 работает следующим образом, При поступлении сигнала по входу 76 запуска через элементы И группы 65 с выхода 3 в счетчик 41 переписывается адрес начала зоны, а через элементы И группы 66 с входа

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

Упорядочение заключается в том, что все числа в выбранном разряде которых "0" перемещаются в ЗУ в начале зоны, а все числа, в выбранном разряде которых "1", перемещаются в конец зоны. Триггеры 48—

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

ИЛИ 61, возбуждают шину 80 разрешения считывания, а также, пройдя через элемент

ИЛИ 58, разрешает поступление через элементы И группы 67 и элементы ИЛИ группы

73 адреса начала зоны из счетчика 41 на выходные адресные шины 78 устройства, Сигналы по этим выходам поступают в ЗУ, в котором происходит считывание числа, записанного по данному адресу, т,е. первого числа массива, которое поступает из ЗУ на выходные шины 77 устройства и через элементы И группы 71 записываются в регистр

44 и поступает на входы мультиплексора 46, который осуществляет выборку из числа двоичного разряда, номер которого подается с входа 4, При равенстве проверяемого разряда числа нулю появляется сигнал на инверсном выходе мультиплексора 46, который через элемент ИЛИ 60 поступает на счетный вход счетчика 41, увеличивая его содержимое на единицу, т.е, в счетчике записывается адрес следующего числа, Содержимое счетчиков 41 и 42 сравнивается элементом 43 сравнения при их равенстве на выходе 62 появляется сигнал, логическая единица, сигнализирующий об окончании работы блока, Этот сигнал поступает также на инверсный вход элемента И

51, закрывая его и запрещая тем самым поступление тактовых импульсов в блок, кроме этого с регистра 42 на выход 1 поступает адрес середины зоны. В противном случае цикл работы блока повторяется.

Если проверяемый разряд числа — "1", то появляется сигнал на прямом выходе мультиплексора 46, который переключает триггер 48 в единичное состояние, переводя блок 40 из режима считывания по начальному адресу в режим считывания по конечному адресу. Очередной тактовый импульс через элементы И 51, 53 и 57 и ИЛИ 61 возбуждает шину 40 разрешения считыва5

55 ния и разрешает поступление через элемент

И группы 68 и элементы ИЛИ группы 73 адреса конца зоны из счетчика 42 на выходные адресные шины 78 блока 40, а также разрешает запись последнего числа массива из ЗУ через элементы И группы 72 в регистр 45. При равенстве заданного разряда числа единицы появляется сигнал на прямом выходе мультиплексора 47, который поступает через элементы ИЛИ 62 на счетный выход вычитающего счетчика 42, т,е. в счетчике будет записан адрес предпоследнего числа массива сортируемых чисел. При поступлении следующих тактовых импульсов цикл работы блока 40 повторяется, пока на инверсном выходе мультиплексора 47 не появится единичный сигнал, который переведет триггер 50 в единичное состояние, переключив тем самым блок 40 в режим записи по конечному адресу. Далее происходит запись числа в единичным заданием разрядом из регистра 44 в ЗУ по только что считанному адресу, по которому находились число с нулевым выбранным разрядом. Очередной тактовый импульс через элементы И

53 и И 56 возбуждает шину 81 записи и через элементы И 55 и ИЛИ 59 разрешает поступление адреса из счетчика 42 на выходные адресные шины 78 блока 40, а из регистра

44 на информационные выходы 79 блока 40, также переводит триггер 40 в единичное состояние, разрешая тем самым прохождение сигнала через элемент 54 и переключая тем самым блок 40 в режим записи по адресу, задаваемому счетчиком 41. При поступлении очередного тактового импульса блок

40 работает аналогично, выводя число в ЗУ из регистра 45 по адресу, задаваемому счетчику 41, а также переводит триггеры 48 — 50 в нулевое состояние, переключая тем самым блок 40 в режим считывания числа по адресу, задаваемому счетчиком 41. Этот же им- . пульс, задержанный элементом 63 задержки на время записи в 40, поступает через элемент 63 задержки на время записи числа в 40, поступает через элемент ИЛИ 62 на вход счетчика 42, уменьшая его значение на единицу, и задержанный элементом задержки 64 на время работы элемента ИЛИ

62, счетчика 41 и элемента 43 сравнения, поступает через элемент ИЛИ 60 на вход счетчика 41, увеличивается его содержимое на единицу. Далее цикл работы блока 40 повторяется с приходом очередного тактового импульса.

Предлагаемое устройство работает следующим образом. B исходном состоянии в регистре 1 записан адрес начала зоны, в регистре 2 и в первом регистре аппаратной стековой памяти 5 — адрес конца зоны мас1803909 сива чисел, записанного в запоминающее устройство общего назначения, который надо упорядочить, B регистре аппаратной стек вой памяти 6 записано количество М двоичных разрядов числа, по которым необходимо выполнить упорядочение, начиная с разряда со старшим номером.

Упорядочение заключается в том, что все числа, в старшем разряде которых "О", перемещаются в ЗУ в начале зоны, а все числа, в старшем разряде которых "1", перемещаются в конец зоны, Затем этот процесс повторяется отдельно для зон с нулями и единицами в старшем разряде, а упорядочение ведется по разряду, с номером на единицу меньшим. Процесс повторяется, пока не будет произведено упорядочение чисел в зонах

ЗУ по младшему, первому разряду. Логика повторения устройства обеспечивает минимальные затраты оборудования, которые не зависят от количества чисел и количества ! разрядов для упорядочения числами по проме куточным от М до 1 номерами разряда.

; При поступлении сигнала на входу 39 заг уска содержимое регистра 2 переписыва тся через мультиплексор 25 в регистр 11, содержимое регистра 3 переписывается через мультиплексор 28 в вычитающий и элемент ИЛИ 20 на вход запуска блока УР 40, инИциируя тем самым работу устройства в режиме неупорядочения. Описанные циклы работы устройства повторяются, пока текущит адрес начала зоны ЗУ регистра 10 станет равным записанному 1 регистра 2

aAjeca конца зоны всего массива чисел в

ЗУ, что контролируется элементом сравнения 7, вырабатывающим по равенству сигнал 58 окончания работы устройства.

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

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

Реализация предложения предлагается в системе обработки хроматографических данных микрохроматографа MX-1.

Содержательное описание работы устройства представлено в таблице.

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

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

ИЛИ, а также с первыми входами элементов

И пятой и шестой групп, выход j-го элемента

И седьмой группы, где j = 1, 2, ..., m, m— количество разрядов чисел массива, соединен с j-м информационным входом первого регистра, выходы j-x разрядов первого и второго регистров соединены с вторыми входами j-x элементов И соответственно шестой и пятой групп, выходы которых соединены соответственно с первым и вторым входами j-ro элемента ИЛИ второй группы, выход которого является j-м информацион1803909

20

30

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

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

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

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

35

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

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

Соединены с информационными выходами третьей группы блока подготовки адресов начала и конца зоны упорядочения массива, выходы первой группы блока памяти номера разряда соединены с информационными входами третьего регистра и входами первой группы блока памяти номера разряда, информационные входы

30 второй группы которого соединены с выходами второй группы блока памяти номера разряда.

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

3. Устройство по п. 1, о т л и ч а ю щ е ес я тем, что блок формирования номера упорядочения чисел содержит вычитающий счетчик, два мультиплексора, регистры номера и количества разрядов, причем вход начала цикла блока соединен с входом вычитающего счетчика, выход переполнения которого является выходом конца цикла блока, а выходы разрядов подключены к информационным входам первой группы блока и первого мультиплексора, информационные входы второй группы которого являются информационными входами второй группы блока, управляющие входы — соответственно вторым и четвертым управляющими входами блока, а выходы соединены с входами регистра номера разряда, выходы которого соединены с информационными входами первой группы второго мультиплексора, информационные входы второй группы которого соединены с выходами регистра количества разрядов, управляющие входы первым и третьим управляющими входами блока, а выходы соединены с входами разрядов вычитающего счетчика.

1803909

4рлряй числа

1803909

1803909

Составитель В. Авдоничев

Редактор Т. Мельникова Техред М.Моргентал Корректор: М, Керецман

Заказ 1057 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101