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

I

Фиг.

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

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

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

Устройство для сортировки чисел (фиг.1) содержит блок 1 памяти входных массивов, коммутатор 2. второй блок 3 памяти, дешифратор 4, блок 5 подсчета массивов, первый элемент И 6, первый блок 7 памяти, блок 8 сравнения, вторую группу 9 элементов И, группу 10 элементов ИЛИ, буферный блок 11 памяти, выходной блок 12 памяти, первую группу 13 элементов И, второй элемент И 14.

Блок 5 подсчета массивов (фиг.2) содержит элемент ИЛИ 15, одновибратор 16, счетчик 17, блок 18 сравнения/регистр 19 и генератор 20 тактовых импульсов (ГТИ).

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

Предварительно опишем решаемую задачу.

Пусть имеется N исходных массивов, в каждом из которых находится щ (, N) упорядоченных чисел. Необходимо из элементов этих исходных массивов составить

N

единый массив, содержащий п 2 (ni)

1 1

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

Перед началом работы устройства на вход регистра 19 блока 5 подается число N упорядоченных массивов. Первый массив подается на информационный вход первого блока 7 памяти, а остальные N-1 массивов заносятся в блок 1 памяти входных массивов. Кроме того, обнуляется содержимое. первого блика 7 памяти, второго блока 3 памяти и буферного блока 11 памяти,

При включении блока 5 на его выходе последовательно формируются адреса регистров 1-1 блока 1 памяти входных массивов, которые поступают на управляющий

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

На четвертом выходе блока 5 появляется импульс, при поступлении которого на первый управляющий вход первого блока 7 памяти в него записывается первый массив чисел, а при поступлении этого импульса на 0 второй управляющий вход второго блока 3 памяти происходит запись массива с выхода коммутатора 2 во второй блок 3 памяти. Первое число из первого блока 7 памяти и первое число из второго блока 3 памяти

5 поступают на первый и второй входы блока

8сравнения, первый и второй входы дешифратора 4, а также на информационные входы первой 13 и второй 9 групп элементов И соответственно.

0 Если число, поступающее на первый вход блока 8 сравнения,меньше или равно числу, поступающему на его второй вход, то на втором выходе блока 8 появляется единичный потенциал, который поступает на

5 второй вход первой группы 13 элементов И ,и открывает их. В результате этого число с информационного входа и первой группы 13 элементов И поступает на первый вход группы 10 элементов ИЛ И. Так как вторая группа

0 элементов И в этот момент закрыта, то число через группу Ю элементов ИЛИ поступает в буферный блок 11 памяти. Кроме того, единичный потенциал со второго выхода блока 8 сравнения поступает на второй вход

5 первого элемента -И 6. В результате управляющий импульс с третьего выхода блока 5 через первый элемент И 6 поступает на второй управляющий вход первого блока 7 памяти. При этом содержимое первого блока

0 у памяти продвигается на одну ячейку и на его выходе появляется второе число упорядочиваемого массива. После этого процесс сравнения двух чисел повторяется.

Если число, поступающее на первый

5 вход блока 8 сравнения, больше числа по- ступающего на его второй вход, то на первом выходе блока 8 сравнения появляется единичный потенциал, который, поступая на первый вход второй группы элементов И

0 9, открывает его, поэтому число с информационного входа второй группы элементов И

9поступает на второй вход группы 10 элементов ИЛИ. Так как первая группа элементов И 13 в этот момент закрыта, то число

5 через группу 10 элементов ИЛИ поступает в буферный блок 11 памяти. Кроме того, единичный потенциал с первого выхода блока 8 сравнения поступает на первый вход второго элемента И 14 и управляющий импульс с третьего выхода блока 5 через второй элемент И 14 поступает на первый управляющий вход второго блока 3 памяти. При этом содержимое второго блока 3 памяти сдвигается на одну ячейку и на его выходе появляется второе число упорядочиваемого массива. После этого процесс сравнения двух чисел повторяется.

При появлении на выходе первого блока

7или второго блока 3 признака конца массива происходит запись в буферный блок 11 памяти числа,-появившегося на выходе другого блока памяти, поскольку блок 8 сравнения интерпретирует признак конца массива как очень большое число.

Описанный выше процесс сравнения двух чисел заканчивается в тот момент, когда на выходах первого 7 и второго 3 блоков устанавливаются признаки конца массива.

8результате поступления двух признаков конца массива на входы блока 8 сравнения один из них записывается в буферный блок 11 памяти и становится признаком конца упорядоченного массива, сформированного из элементов первого и второго массивов. Кроме того, оба признака поступают на входы дешифратора 4, который при этом формирует на выходе единичный потенциал, поступающий на вход блока,5, который изменяет адрес на своем первом выходе и формирует на своем четвертом выходе управляющий импульс, который поступает на первый управляющий вход первого блока 7 памяти, второй управляющий вход второго блока 3 памяти и второй управляющий вход буферного блока 11 памяти.

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

Описанный процесс упорядочивания повторяется до тех пор, пока не будут отработаны все массивы из блока 1 памяти входных массивов. После этого на втором выходе блока 5 появляется единичный импульс, который поступает на управляющий вход выходного блока 12 памяти, и в выходной блок 12 памяти из буферного блока 11 памяти.записывается результирующий упорядоченный массив.

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

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

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

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

15 с информационными входами второго блока памяти, выходы которого соединены с входами второй группы блока сравнения, входы первой и второй групп блока сравнения объединены с соответствующими

0 входами первой и второй групп дешифратора и с информационными входами элементов И соответственно первой и второй групп, управляющие входы которых соединены соответственно с выходами Мень5 ше и больше блока сравнения, а выходы соединены с соответствующими первыми и вторыми.входами элементов ИЛИ группы, выходы которых соединены с информа- ционными входами буферного блока

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

5 входы которого являются входами числа массивов устройства, § вход запуска - входом запуска устройства, выход Больше блока сравнения соединен с первым входом второго элемента И, второй вход которого

0 соединён с тактовым выходом блока подсчета массивов, входом записи буферного блока памяти и вторым входом первого элемента И. выходы первого и второго элементов И соединены с входами сдвига соот5 ветственно первого и второго блоков памяти, входы записи которых и вход считывания буферного блока памяти соединены с выходом разрешения записи блока подсчета массивов, вход приращения адреса кото0 рого соединен с выходом дешифратора.

2. Устройство по п. 1.отличающее

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

одновибратор. схему сравнения, счетчик,

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано для формирования упорядоченного массива чисел. Цель изобретения - расширение функциональных возможностей за счет возможности сортировки чисел в едином массиве из исходных массивов. Устройство содержит блок 1 памяти входных массивов, коммутатор 2, два блока памяти 3 и 7, дешифратор 4, блок 5 подсчета массива из исходных массивов неравных объемов, элементы И 6,9 и 14, блок сравнения, блок элементов ИЛИ, буферный блок 11 памяти, выходной блок 12 памяти и группы 10 и 13 элементов И. 2 ил.

Фиг,. 2