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

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

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

не больше и не меньше.

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

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

Блок управления содержит счетчик 8 длины массива, регистр 9 состояний, мультиплектор 10, регистр 11 адреса микрокоманды, ПЗУ 12, регистр 13 микрокоманд, формирователь 14 им- пульсов, информационный вход 15, тактовый вход 16, вход Ошибка 17, выходы 18-21 управления регистром, первым, вторым блоком памяти и арифметико-логическим блоком соответственно. 30 торых выполняется усл овие А i а ,

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

очередной микрокоманды из ПЗУ 12. . Каждое вновь поступающее i-e число а- поступает на адресные входы блока памяти 2. Код, считанньй по адресу, складывается арифметико-логическим

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

t5 же адресу а j,

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

Для подсчета количества чисел, удовлетворяющих критерию не больше

или не меньше, т.е. таких, для ко- или а- А

макс.

необходимо выполнить

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

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

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

JJ rflflH

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

40 Для этого определяется количество циклов этого этапа, для чего из блока памяти 1 считывается код А (например, максимальньш адрес блока памяти 2, или любой другой, больший,

45 чем А), который поступает без изменений через арифметико-логический блок 4 и в регистр 3, затем из него вычитается считанная из блока памяти 1 величина А.„. , результат записымин

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

торых выполняется усл овие А i а ,

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

очередной микрокоманды из ПЗУ 12. Каждое вновь поступающее i-e число а- поступает на адресные входы блока памяти 2. Код, считанньй по адресу, складывается арифметико-логическим

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

же адресу а j,

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

Для подсчета количества чисел, удовлетворяющих критерию не больше

торых выполняется усл овие А i а ,

или не меньше, т.е. таких, для ко30 торых выполняется усл овие А i а ,

- или а- А

макс.

необходимо выполнить

50 вается в счетчик 8. После этого происходит сложение содержимого яче- ек блока памяти 2, начиная с адреса

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

JJ rflflH

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

40 Для этого определяется количество циклов этого этапа, для чего из блока памяти 1 считывается код А (например, максимальньш адрес блока памяти 2, или любой другой, больший,

45 чем А), который поступает без изменений через арифметико-логический блок 4 и в регистр 3, затем из него вычитается считанная из блока памяти 1 величина А.„. , результат записымин

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

-А ) и подсчет выполняется, нами«

до

чиная с ячейки с адресом от А., А. для режима больше и ячейки с адресом от А до А- для режима меньше. Результат- записывается в ячейку А |.

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

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

,

10 )5 20 - 25 30.j 40 45

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

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

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

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

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

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

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

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