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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике. Цель изобретениярасширение функциональных возможностей за счет обеспечения возможности подсчета количества чисел, удовлетворяющих критерию равно, больше, меньше не больше и не меньше. Устройство содержит блоки памяти (БП) , регистр,арифметико-логический блок (АЛБ) и блок управления (БУ),который обеспечивает микропрограммное управление блоками устройства.В каждой ячейке первого БП накапливается количество чисел в массиве, равных адресу этой ячейки, для чего при поступлении очередного 1-го числа а,- из БП считывается записанное по адресу а число, к нему прибавляется единица и затем оно записьшается по тому же адресу. Для сортировки чисел по критерию больше (меньше) или не больше (не меньше) подсчитывается сумма чисел, находящихся в ячейках с адресами от заданных А до включительно . Сложение выполняется АЛБ, результат записывается в БП. 1 з.п. ф-лы, 2 ил. с $ (Л 00 о 4

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

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

РЕСПУБЛИК

„„Я0„„1304015

А1 (51)4 G 06 Р 7 06

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

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

"ъ-. ЛММ-ВОЙ я ю»» - »»

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3889399/24-24 (22) 23.04.85 (46) 15.04.87. Бюл. ¹ 14 (71) Киевский завод электронных вычислительных и управляющих машин (72) Н.Т. Пшеничный (53) 681.325(088.8) (56) Авторское свидетельство СССР № 1183956, кл. G 06 F 7/06, 1984.

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

N- 1183957, кл. G 06 F 7/06, 1984..(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57). Изобретение относится к вычислительной технике. Цель изобретения— расширение функциональных возможностей за счет обеспечения возможности подсчета количества чисел, удовлетворяющих критерию "равно", "больше", "меньше" "не больше" и "не меньше".

Устройство содержит блоки памяти (БП), регистр,арифметико-логический блок (АЛВ) и блок управления (БУ),который обе спечивает микро про граммное управление блоками устройства. В каждой ячейке первого БП накапливается количество чисел в массиве, равных адресу этой ячейки, для чего при поступлении очередного i-ro числа а; из БП считывается записанное по адресу а1 число, к нему прибавляется единица и затем оно записывается по тому же адресу.

Для сортировки чисел по критерию

"больше" (" меньше" ) или "не больше" ("не меньше") подсчитывается сумма чисел, находящихся в ячейках с адресами от заданных А „ до А„, вклю- б чительно. Сложение выполняется АЛБ, результат записывается в БП. 1 з.н. ф-лы, 2 ил. С:

1 13040

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

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

На фиг. 1 представлена схема предлагаемого устройства; на фиг. 2— схема блока управления. 15

Устройство для сортировки чисел содержит блоки памяти 1, 2, регистр

3, арифметико-логический блок 4, блок 5 управления, шину 6 входа-вы хода, тактовый вход 7, Блок управления содержит счетчик

8 длины массива, регистр 9 состояний, мультиплектор 10, регистр 11 адреса микрокоманды, ПЗУ 12, регистр

13 микрокоманд, формирователь 14 импульсов, информационный вход 15, тактовый вход 16, вход "Ошибка" 17, выходы i8-21 управления регистром, первым, вторым блоком памяти и арифметико-логическим блоком соответственно. 30

Устройство для сортировки чисел позволяет производить подсчет количества чисел, равных заданному, меньше,(больше) заданного и не меньших (не больших) заданного. Управление работой устройства выполняется микропрограммно: очередная микрокоманда выбирается из ПЗУ 12 по адресу, определяемому содержимым регистра 11 адреса микрокоманды, и помещается в 40 регистр 13 микрокоманды. Содержимое определенных разрядов регистра 13 поступает на адресные входы блока памяти 1 и входы управления блоком памяти 2, регистра 3 и арифметико- 45 логического блока 4.

Режим сортировки задается по двунаправленной шкале ввода-вывода 6 заданием начального адреса микропрограмм выборки чисел по критерию "рав- 50 но", "больше", "меньше", "не больше", "не меньше". Этот адрес поступает через мультиплексор 10 в регистр 11 адреса микрокоманды. Далее выполняется прием длины сортируемого массива 55 в счетчик 8 длины массива, а в ячейки блока памяти 1 — рабочих констант, величины которых зависят от режима сортировки. После этого по шине 6

15 поступают числа, сопровождаемые тактовыми сигналами по входу 7. Те же тактовые сигналы через формирователь

14 импульсов обеспечивают выборку очередной микрокоманды из ПЗУ 12.

Каждое вновь поступающее i-e число а

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

Таким образом, после приема всего массива (что фиксируется появлением нуля в счетчике 8 длины массива, содержимое которого уменьшается с каждым приходом нового числа), по адресу а (а =1,2 ... M, где M — емкость блока памяти 1) будет находиться количество в массиве чисел, равных а;. На этом подсчет и сортировка чисел по критерию "равно" заканчивается.

Для подсчета количества чисел, удовлетворяющих критерию "не больше" или "не,меньше, т.е. таких, для которых выполняется условие А а мин— или а А, необходимо выполнить мака суммирование содержимого всех ячеек блока памяти 2, начиная с А и мин старше, и результат записать в ячейку А . Последовательно выполнив эту мин операцию для всех ячеек с адресами, не большими, чем А „,, можно полу-. чить массив, отсортированный по данному критерию.

Для этого определяется количество циклов этого этапа, для чего из бло" ка памяти 1 считывается код А (на;

Маис пример, максимальный адрес блока памяти 2, или любой другой, больший, чем А „), который поступает без изменений через арифметико-логический блок 4 и в регистр 3, затем из него вычитается считанная из блока памяти 1 величина А„„„, результат записывается в счетчик 8. После этого происходит сложение содержимого ячеек блока памяти 2, начиная с адреса

А „ и до адреса А „„, включительно (всего А „„ -А „ сложение). Результат записывается по адресу А мин

Сортировка чисел по критерию

"больше" и "меньше" происходит аналогично, однако количество сложений в счетчике 8 задается равным (А маис

3 13040

-А „„-1), и подсчет выполняется, начиная с ячейки с адресом от А до макс

А. для режима "больше" и ячейки с

1+1 адресом от А „ до А, для режима

"меньше". Результат- записывается в ячейку А;.

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

1. Устройство для сортировки чи- 10 сел, содержащее два блока памяти, регистр и блок управления, причем выходы управления первым блоком памяти блока управления соединены с адресными входами и входами управления ре- (5 с жимом первого блока памяти, о т л и— ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет обеспечения возможности подсчета количества чисел, удовлет- 20 воряющих критерию "равно", "больше", "меньше", "не больше", "не меньше", в него введен арифметико-логический блок, причем информационная шина ввода-вывода устройства подключена к 25 выходу арифметико-логического блока, входу адреса и данных второго блока памяти, информационным входами регистра, первого блока памяти и блока управления, тактовый вход которого яв- 30 ляется тактовым входом устройства, выходы управления регистром, вторым блоком памяти и арифметико-логическим блоком блока управления соединены соответственно с входами разрешения записи регистра, входом выбора режима второго блока памяти и входом задания операции арифметико-логического блока, первый информационный вход которого подключен к выходу первого 4р блока памяти, а одноименные выходы второго блока памяти и регистра объединены и подключены к второму информационному входу арифметико-логического блока, выход переполнения

15 4 которого соединен с входом "Ошибка" блока управления.

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

Фиг.Z

Составитель В. Горохов

Редактор М. Бандура Техред М.Ходанич Корректор А. Зимокосов

Заказ 1312/49 Тираж 6?3 Подписное

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

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

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