Устройство для сортировки чисел

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных для упорядочения произвольных массивов чисел. Цель изобретения - повышение быстродействия устройства и упрощение устройства. Устройство содержит регистры 1, схемы сравнения 2, группы 3 элементов И, счетчик 4, регистр результата 5, дешифратор 6, буферный регистр 7, элемент ИЛИ 8, элемент И 9, группу элементов И 10, группу элементов И-ИЛИ 11, группу элементов ИЛИ 12, группу элементов И 13, 14, элемент НЕ 15, элемент И 16, группу триггеров 17, группу элементов ИЛИ 18, 19, группу триггеров 20, элемент задержки 21, элемент НЕ 22, узел выбора опорного адреса 23, регистр максимального числа 25, элемент И-ИЛИ 26, дополнительный блок 27 элементов И, вход тактовых импульсов 28. 3 ил. 2 табл.

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4731793/24 (22) 12.06.89 (46) 15,11.91. Бюл. М 42 (72) С,Н,Ази, В.В,Туравинин, А,А.Заболотнев и B.ВМажников (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 911513, кл, G 06 F 7/06, 1980.

Авторское свидетельство СССР

1в 1117631, кл. G 06 F 7/06, 1983, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных для упорядочения произ„„5IJ „„ 1691833 А1

BQllbHbIx массивов чисел. Цель изобретения — повышение быстродействия устройства и упрощение устройства. Устройство содержит регистры 1, схемы сравнения 2, группы

3 элементов И, счетчик 4, регистр результата

5, дешифратор 6, буферный регистр 7, элемент ИЛИ 8, элемент И 9, группу элементов

И 10, группу элементов И-ИЛИ 11, группу элементов ИЛИ 12, группу элементов И 13, 14, элемент НЕ 15, элемент И 16, группу триггеров 17, группу элементов ИЛИ 18, 19, группу триггеров 20, элемент задержки 21, элемент НЕ 22, узел выбора опорного адреса 23, регистр максимального числа 25, элемент И вЂ” ИЛИ 26, дополнительный блок

27 элементов И, вход тактовых импульсов

28. 3 ил. 2 табл.

1691833

Таблица 1

Код на выходах

00...00

00...Î1

00...01

00...10

00...01

00...10

00...10

00...11

00...01 дна в>

0...0000

0...0000

0„.0000

О...ОООС

0...000C

О...OOOC

0...000C

О. „000C

)...0001

01...11

10...00! ... 1 1 1

1...111

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

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

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

Устройство содержит (К+1) регистров 1, (К+1) схем 2 сравнения, группы 3 элементов

И, счетчик 4, регистр 5 результата, дешифратор б, буферный регистр 7, элемент ИЛИ

8, элемент И 9, группы 10 управляющих элементов И, группы 11 элементов И-I/IllN, группу 12 элементов ИЛИ, группа 13 управляющих элементов И, группы 14 управляющих элементов И. элемент НЕ 15, элемент И

16, группы 17 триггеров, группы 18 элементов ИЛИ, группы 19 элементов ИЛИ, группы

20 триггеров, элемент 21 задержки, элемент

НЕ 22, узел 23 выбора опорного адреса, регистр 24 максимального числа, триггер

25, элемент И-ИЛИ 2б, дополнительную группу 27 элементов И и вход тактовых импульсов устройства 28.

Узел 23 выбора опорного адреса состоит из групп 29 и 30 элементов И.

Счетчик 4 содержит элементы И 31 — 34, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 35-38 и элемент ИЛИ 39.

Счетчик 4 предназначен для подсчета числа единичных сигналов, пришедших на его входы. Hai выходе счетчика формируется двоичный код этого числа, Счетчик имеет выход переполнения (первый выход), Работу счетчика, имеющего (К41) входов и (К+2) выходов, можно описать табл,1.

Такой счетчик может быть реализован, например, на логических элементах, Если

К = 3, то выходов у счетчика 3. Его работа описывается табл.2.

5.Таблица 2

Код на входах

0001

0011

0101

0111

1001

1011

1 101

1111

20

Если К = 7, то параллельно этому счетчику ставится такой же счетчик и добавляется третья ступень и т,д.

Нулевой выход линии 21 задержки

30 предназначен для согласования работы дополнительной числовой руппы И и регистра

5 результата, Узел выбора опорного адреса выбирает адрес с минимальным порядковым номе35 ром, по которому триггер 17 группы находится в единичном состоянии, Сигнал на инверсном выходе этого триггера запрещает прохождение единичных сигналов через элементы 29 и 30 групп с

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

45 Сигнал "Меньше" на выходе схемы 2 сравнения появляется в том случае, если число в регистре 1 меньше числа, записанного в буферный регистр 7, и "Равно на выходе в том случае, если числа равны.

50 Триггер 17 группы решает двойственную задачу. Установленный в нулевое состояние он показывает, что данное число уже участвовало в сравнении, а также вместе с соответствующими элементами И 10 группы

55 обеспечивает правильное формирование отсортированного- массива при наличии одинаковых чисел (при последующих сравнениях с равными числами на выходе элемента И 10 группы и, соответственно, 1 691833

10 зом элемента ИЛИ 12 группы формируется сигнал нулевого уровня).

Группа 20 триггеров предназначена для фиксации факта совпадения исходного адреса числа в массиве с его истинным адресом (адресом в отсортированном массиве), Для этого выбирается обгций исходный адрес (опорный) для всех чисел, участвуюших в текущем такте в сравнении (соответствующий триггер 20 группы в единичном состоянии), При совпадении опорного адреса числа с его истинным адресом единичный сигнал на выходе соответствующего элемента И 14 группы не формируется, так как на инверсном выходе соответствующего триггера 20 группы имеется нулевой сигнал.

Число записывается по этому адресу, и узлом 23 выбора опорного адреса выбирается новый опорный адрес, Вначале опорным является {К+1)-й адрес (регистр 24 максимального числа).

Устройство работает следующим обраВ регистры 1, регистр 5 результата и буферный регистр 7 заносят сортируемые числа (в регистры 5 и 7 — одно и то же число), триггеры 20 группы устанавливают в йулевое, а триггер 25 и триггер 17 группы — в единичное состояние. После этого устройство готово к сортировке чисел в порядке возрастания.

Число, хранящееся в буферном регистре 7, сравнивается в схемах 2 сравнения с числами, находящимися в регистрах 1.

На выходах счетчика 4 формируется код количества элементов ИЛИ 12 группы, имеющих единичный сигнал на своем выходе, Таким образом определяется истинный адрес данного числа в отсортированном массиве.

Если на выходе переполнения счетчика

4 нулевой сигнал, то при поступлении его на инверсный вход синхронизации дешифратора 6 происходит расшифровка адреса и на соответствующем выходе дешифратора 6 формируется единичный сигнал. Так как триггеры 20 группы в нулевом состоянии, то на выходе соответствующего элемента И 14 группы формируется единичный сигнал, который, проходя через элемент ИЛИ 8, разрешает прохождение сигнала с входа 22 тактовых импульсов через элемент И 16 и, поступая через элемент 22 НЕ, запрещает прохождение этого сигнала через элемент

И 9. Единичный сигнал с выхода элемента И

14, находящегося по выбранному адресу, поступает также через соответствующий элемент ИЛИ 19 группы на первые входы соответствующей группы 3 элементов И. По этому сигналу число из регистра 1 поступает

50 на информационны входы буферного регистра 7 и дополнительноtо элементов И. По тактовому сигналу с входа 28 через нулевой выход элемента 21 задержки тактовых импульсов разрешается прохождение этого числа через дополнительную группу

27 элементов И на информационные входы регистров 1, а при поступлении тактового сигнала на вход разрешения записи буферного регистра 7 число записывается в этот регистр, поступая чсрез элемент НЕ 15 на вход разрешения хранящсгося в этом регистре. Так как триггер 25 находится в единичном состоянии,;а тактовому сигналу, поступающему через элемент И элемента

И-ИЛИ 26 на вход разрешения записи в регистр 24 максимального числа, число, находящееся по выбранному адресу, записывается в рeãèñòð ?4. При отсутствии тактового сигнала на входе 28 тактовых импульсов запрещается прохождение числа через дополнительную группу 27 элементов

И, а выдача числа из регистра 5 результата разрешается, По сигналу с выхода элемента 21 задержки, поступающего через элемент И соответствующего элемента И-ИЛИ 11 группы (на входе элемента И единичный сигнал с выхода дешифратора б) на вход разрешения записи в соответствующий регистр 1, число из регистра 5 резуль-,ата записывается в регистр 1 по свое у истинному адресу в отсортированном массиве. При прохождении сигнала с выхода элемента 21 задержки через соответствующий элемент И 13 группы (единичный сигнал с выхода дешифратора 6 поступает через элемент ИЛИ 18 группы на вход элемента И 13) соответствующий триггер 17 группы устанавливается в. нулевое состояние. Таким образом, число, участвующее в сравнении. записывается в регистр 1 по своему истинному адресу, из которого предварительно переписывается в буферный регистр 7 и в регистр 24 максимального числа (регистр находящийся по опорному адресу).

Параллельно с определением истинного адреса числа в узле 23 выбора опорного адреса подготавливается новый опорный адрес — адрес с максимальным порядковым номером, по которому триггер 17 группы находится в единичном состоянии. При единичном сигнале на выходе переполнения счетчика 4 (истинный адрес (К+1)-й) триггер 25 устанавливается в нулевое состояние, расшифровка адреса дешифратором 6 не про-, изводится. На выходах элементов И 14 группы нулевые сигналы, поступая через элемент ИЛИ 8, запрещают прохождение тактового импульса через элемент И 16 и

19 1833 разр.гшают его прохождение через элемент

И 9. При поступлении единичного сигнала с выхода элемен ra 22 Н Е на вход запуска узла

23 выбора опорного адреса на выходе узла, соответствующего вновь выбранному опорному адресу, формируется единичный сигнал, который поступает на информационный вход соответствующего триггера 20 группы, а через элемент ИЛИ 19 группы — на входы соответствующего блока группы элементов И 3. По сигналу с входа 28 тактовых импульсов число, находящееся по вновь выбранному опорному адресу, записывается в буферный регистр 7, а по сигналу с выхода элемента И 9, поступающему на входы синхронизации триггеров 20 второй группы, соответствующий триггер устанавливается в единичное состояние. По сигналу с первого выхода элемента 21 задержки, поступающему через первый элемент И элемента И-ИЛИ

26 на вход разрешения записи в регистр 24 максимального числа, число из регистра 5 результата (на входе 28тактовых импульсов— нулевой сигнал) записывается на свое место в отсортированном массиве — в регистр 24.

Триггер 17 первой группы, находящийся по опорному адресу, устанавливается в нулевое состояние (на первый вход элемента И

13 второй группы с соответствующего выхода узла 23 выбора опорного адреса поступает единичный сигнал). По сигналу со второго выхода элемента 21 задержки число из буферного регистра 7 переписывается в регистр 5 результата, На этом заканчивается первый такт работы устройства.

В последующих тактах работы устройства также определяется истинный адрес числа, находящегося в буферном регистре 7 и регистре 5 результата, Если этот адрес не совпадает с опорным, то на выходе соответствующего элемента И 14 третьей группы формируется единичный сигнал, который, поступая через элемент ИЛИ 8, разрешает прохождение тактового сигнала через элемент И 16 и запрещает его прохождение через элемент И 9, Число. находящееся по истинному адресу, поступает через соответствующую группу элементов 3 И на вход буферного регистра 7. По тактовому сигналу это число записывается в буферный регистр

7, а через дополнительную группу 27 элементов И вЂ” в регистр, находящийся по опорному адресу (тактовый сигнал через элемент

16 И поступает через второй вход элемента

И-ИЛИ 11 руппы, на первый вход которого поступает единичный сигнал с прямого выхода соответствующего триггера 20 второй группы). Выдача числа из регистра 5 результата тактовым сигналом запрещается. По сигналу с первого B) Ixo/1,. элемента 21 засоответствующих элементов И соответству55 ющих групп и первыми группами входов соответствующих схем сравнения. выходы равенства которых соединены с первыми входами соответствующих управляющих элементов И группы, вторые входы которых соединены с прямыми входами соответству10

50 держки число из регистра 5 результата злписывается по своему истинному адресу в отсортированном массиве и соответствующий триггер 17 группы устанавливается в нулевое состояние

Если истинный адрес числа совпадает с опорным, то единичный сигнал с соответствующего выхода дешифратора 6 не проходит через элемент И 14 третьей группы. так как íà его второй вход поступает нулевой сигнал с инверсного выхода соответствующего триггера 20 второй группы. Поэтому на выходе элемента ИЛИ 8 присутствуют нулевой сигнал, который запрещает прохождение тактового импульса через второй элемент И 16 и поступая через элемент 22

НЕ, разрешает его прохождение через первый элемент И 9 и запускает узел 23 выбора опорного адреса. Число, находящееся по этому адресу, по тактовому сигналу записывается в буферный регистр 7. По сигналу с первого выхода элемента 21 задержки число из регистра 5 результата записывается по своему адресу в отсортированном массиве, а триггеры 17 первой груп и ы, находя щиеся по вновь выбранному опорному и истинному адресам, устанавливаются в нулевое состояние. По сигналу со второго выхода элемента 21 задержки буферного регистра

7 число записывается в регистр 5 результата, Дальнейшая работа устройства аналогична описанному.

После того, как устройство отработает К тактов, в регистрах 1 начиная с первого и в регистре 24 максимального числа, находится отсортированный массив чисел, так как положение (К+1)-ro числа однозначно соответствует его истинному адресу.

Для сортировки чисел в порядке убывания необходимо в регистр 1 записать инверсные значения кодов сортируемых чисел.

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

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

1691833

10

40

45 ющих триггеров группы, а выходы соединены с первыми входами соответствующих элементов ИЛИ первой группы, вторые входы которых соединены с выходами неравенства соответствующих схем сравнения, а выходы соединены с соответствующими входами счетчика, I-й выход дешифратора (i

= О, 1,...,К) соединен с первым входом i-ro элемента ИЛИ второй группы, прямой выход j-ro триггера группы O = О, 1,. „K-1) соединен с /-м входом узла выбора опорного адреса, а инверсный выход j-го триггера группы соединен с (j-K)-м входом узла выбора опорного адреса, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и упрощения устройства, оно содержит буферный регистр, элемент ИЛИ, два элемента И, группу элементов И-ИЛИ, третью группу элементов ИЛИ, вторую и третью группы управляющих элементов И, два элемента НЕ, вторую группу триггеров, элемент задержки, регистр максимального числа, триггер, элемент И-ИЛИ, дополнительную группу элементов И, причем выход переполнения счетчика соединен с первым входом первого элемента И, элемента ИИЛИ, входом установки в "О" триггера и инверсным входом синхронизации дешифратора, информационные входы которого соединены с выходами разрядов счетчика, а

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

I-го элемента ИЛИ третьей группы и I-м входом элемента ИЛИ, выход которого соединен с первым входом элемента И и через элемент НЕ с первым входом второго элемента И и входом запуска узла выбора опорного адреса, i-й выход которого соединен с первым входом I-го элемента ИЛИ второй группы, информационным входом i-ro триггера второй группы и вторым входом i-ro элемента ИЛИ третьей группы, выход которого соединен с вторыми входами элементов И I-й группы, выходы которых соединены с первыми входами элементов И дополнительной группы и информационными входамй буферного регистра, выходы разрядов которого соединены с информационными входами регистра результата и входами второй группы схем сравнения, выходы элементов И дополнительной группы соединены монтажным ИЛИ с выходами разрядов регистра результата и с информационными входами регистра максимального числа, вход разрешения записи которого соединен с выходом элемента И-ИЛИ, первый вход второго элемента И которого соединен с прямым выходом триггера, а второй вход является входом тактовых импульсов устройства и соединен с вторыми входами первого и второго элементов И, входом элемента задержки, входом разрешения записи буферного регистра и через второй элемент НЕ с входом разрешения выдачи регистра результата, выход второго элемента И соединен с входами синхронизации триггеров второй группы, прямой выход i-го триггера второй группы соединен с первым входом второго элемента И i-ro элемента

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

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

Составитель В.Козлов

Редактор Л,Пчолинская Техред M,Moðãåíòàë Корректор М.Демчик

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

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

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

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