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

(Л С

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

- ... П-1

- 3-г

1429

версивпый счетчик 9, блок памяти 8, группу из N элементов И 11, элемент I И 12, блок ограничений 10 и элемент i задержки 7. При упорядочивании мас- сива чисел осуществляется запись в блок памяти одноразрядных признаков наличия числа по адресу, задаваемому значением числа. Считывание информа- jJ,Tfli производится счетчиком с линей- 1 ным нарастанием или убыванием всех I возможных значений числа. Функции

1

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

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

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

Устройство для сортировки массива чисел (фиг. 1) содержит управляю- щий вход 1 Ввод-вывод массиваJ входы 2-2, 2-3 задания признаков, вход 3 Перезапись, информационные входы 4-1 - 4-N, управляющий вход 5 Возрастание-убывание, коммутатор 6, элемент 7 задержки, блок 8 памяти реверсивный счетчик 9, блок )0 ограничения, группу из N элементов И 11-1 - , элемент И 12, информационные выходы 13-1 - 13-N, синхрони- зирующий выход 14.

Блок 10 ограничения (первый вариант фиг. 2) содержит управляюшрий вход 15 Запись, информационные входы 15 и 16, управляющий вход 17 Запись, вход 18- Запись, регистры 19, схемы 20 сравнения, первый 21-1 второй 21-2 мультиплексоры, элемент И 22, элемент И-НЕ 23, элемент ИЛИ 24, элемент ИЛИ-НЕ 25, выходной мультиплексор 26 и управляющий выход 27.

Блок 10 ограничения (второй вариант, фиг. 3) содержит информационные входы 28 и 29, управляющие входы 30 и 31 Запись, регистры 32, схему

07

обработки задаются кодами, записываемыми в блок ограничения. Блок ограничения (два варианта) позволяет осуществлять вывод группы чисел, принадлежащих заданному интервалу, вывод группы чисел, не принадлежащих заданному интервалу, исключение произвольных чисел из упорядоченного массива и определение принадлежности произвольных чисел упорядоченному массиву. 2 з.п. ф-лы, 3 ил., 6 табл.

33 сравнения, мультиплексор 34, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 35 и управляющий выход 36.

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

Перед каждым вводам чисел упорядочиваемого информационного массива производится очистка блока В памяти (табл. 1, п. 1), осуществляемая подачей нулевого кода на входы 2-1+2-3 устройства (колонки 3-5) и одного импульса на вход 3 (колонка 15). При этом коммутатор 6 переходит в режим передачи сигнала с входа Р на выход А (колонка 7) и затем на вход 17 (фиг. 2) блока 8 (фиг. 1).

При выполнении указанной операции состояние входов 1, 2, 4 и 5 устройства, а также состояние счетчика 9 и регистра 19 может быть любым..

Ввод чисел упорядочиваемого массива осуществляется после установки единичного потенциала на входе I, переводящего блок 8 в режим записи, и входе 2-3 устройства (табл. 1, п. 2), разрешающего прохождение импульсов со входа 3 устройства на выход 8 коммутатора 6 (колонка 8), которые затем подаются на вход Запись счетчика 9 и через элемент 7 задержки - на вход Запись блока 8. Импульс на вход 3 устройства в этом случае должен подаваться синхронно с подачей очередного числа упорядочиваемого массива, что обеспечивает вначале запись этого числа в счетчик 9, а затем благодаря элементу 7 задержки - запись логической единицы в один из триггеров блока В, соответствующий

31А291

адресу, заданному выходным кодом счетчика 9. В этом случае счетчик 9 служит в качестве буферного регистра.

Предлагаемое устройство осуществляет одну из семи функций- при выводе упорядоченной информации в порядке возрастания (логическая единица на входе 5) или убывания (логический нуль на входе 5) чисел (табл. 2 и 1 - табл, 2, п. 7). Установка необхо- Ю димого варианта режима вывода осуществляется записью кодов, указанных в колонках 5-7 (табл. 2), в регистры 19 (фиг. 3) и установкой начального состояния счетчика 9 (фиг. ), при- J5 веденного в табл. 2, колонка 8. Запись необходимых значений кодов в регистры 19 производится путем установки требуемого кода на входах 4-1 4-N устройства и подачей импульса записи 20 на тактовые входы 15, 17 и 18 регистров 19. Коммутацию импульса Перезапись с входа 3 устройства на входы Запись 15, 17 и 18 осуществляет коммутатор 6 в соответствии с табл.1 25 и 3.1 - 3.3.

Установка режимов работы устройства сортировки приведена в табл. 1. Этот же коммутатор 6 аналогично обеспечивает возможность установки про- 30 извольного начального состояния счетчика 9 по шинам Установка в ноль (табл. 1, п. 3, 4), Запись (табл.1, п. 2) и подачу тактовых импульсов на него (табл. I, п. 3, 5). 5

Установка вариантов режима вывода представлена в табл. 2.

Схемы 20-1, 20-2 сравнения блока 10 Ограничения (фиг. 2) работают в соответствии с табл. 3.40

Мультиплексоры 21-1, 21-2 обеспечивают передачу информации с входов А на выход В в зависимости от состояния управляющих сигналов W 1, W 2, представленных в табл. 4.

Пусть, например, в регистре 19-3 записан нулевой код, разрешающий прохождение сигналов с входов А мультилексоров 20-1, 20-2, 26 на. выход В (табл. 4, п. 1). Так как входы А1 50 мультиплексоров 20-1, 20-2 соединены с шиной Логическая единица, на их выходах В, а следовательно, и на выходе элемента И 22 будет установлен единичный потенциал, который переда- ется мультиплексором 26 на выход 27 блока 10 ограничения. Таким образом, при любом состоянии кодов на информационных входах 16-1 - 16-N и 15-1 074

- 5-N блока 10 ограничения обеспечивается наличие сигнала логической единицы на первых входах элементов И 11-1 - 11-N, И 12, что позволяет осуществить вывод всего упорядоченного массива (табл. 2, п. 1). Пусть например, ранее было установлено начальное состояние счетчика 9, а на управляющем входе 5 - единичный потенциал, обеспечивающий работу счетчика 9 в режиме суммирования. С подачей каждого тактового импульса на вход 3 Перезапись устройства, которьй благодаря установке кода ПО (табл-( 1, п. 3, 5) на его управляющих входах 2-1 - 2-3 выделяется на. выходе G KONtMyTaTopa 6 и поступает на TaKTOBbrfi вход счетчика 9 и на третий вход элемента И 12, значение выходного кода счетчика 9 возрастает на единицу. Поскольку ранее в блок 8 были записаны единичные признаки присутствия чисел во входном массиве, при установке нулевого потенциала на входе 1 устройства (фиг. 1) происходит чтение признака по адресу соответствующему коду на выходе счетчика 9.

Если при обработке массива число на выходе счетчика 9 присутствовало в потоке данных, то блок 8 памяти выдает единичный потенциал, который, при поступлении на первые входы элементов И 11-1 - I1-N, И 12 открывает их и код с выходов счетчика 9 поступает на выходы 13-1 - 13-N, 14 устройства. Если такого числа нет, то блок 8 выдает нулевой потенциал и запрещает выдачу кода с выхода счетчика 9 на выход устройства.

Линейное нарастание кода счетчика 9 позволяет осуществить упорядоченный вывод зафиксированного в блок 8 массива в порядке возрастания (табл. 2, п. 1, верхняя строка).

Аналогично можно рассматривать работу устройства при выводе в порядке убывания чисел,- т.е. при нулевом потенциале на входе 5 устройства и максимальном значении счетчика (табл. 2, п. I, нижняя строка).

Пусть в регистре 19-3 (фиг. 2) записан код 001110 (младший разряд крайний правый), разрешающий передачу информации: мультиплексору 21-1 с входа А2 на выход 8, мультиплексору 21-2 с входа А4 на выход 8, мультиплексору 26 с входа А1 на выход В.

8регистрах 19-1, 19-2 записаны ми

5

нимальное и максимальное числа некоторого интервала. В соответствии с табл. 3 блок 10 огран1гчения в таком случае обеспечивает нулевой потенциал на выходе 27, если число, по- даваемое на информационные входы 15-1 - 15-N, лежит за пределами интервала, заданного его минимальным и максимальным числами. Если число лежит в пределах заданного интервала, то на .выходе 27 (фиг. 2) блока 10 ограничения присутствует единичный потенциал. Это обеспечивается подключением выхода схемы 20-1 сравнения через мультиплексор 21-1 к первому входу элемента .И 22, и выхода схемы 20-2 сравнения через мультиплексор 21-2 к второму входу элемента И 22, а также выхода элемента И 22 через вход А1 мультиплексора 26 на выход В и далее на выход 27 блока 10 ограничения.

В этом случае и при нарастании (табл. 2, п. 2, первая строка) и при убывании (табл. 2, п. 2, третья строка) кода счетчика 9 при соответствующих кодах (табл. 2, п. 2) в регистрах и 19-2, начальных состояниях счетчика 9 и состояниях сигнал на входе б осуществляется выдача сиг нала разрешения с выхода блока 10 на третьи входы элементов И I1- - - 11-N, И 12, что позволяет произвести вывод чисел упорядоченного массива, принадлежащих заданному интервалу.

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

Следующий (табл. 2, п. 3, первая : строка) вариант режимов работы уст- |ройства при выводе информации отли- чается от предыдущего тем, что мультиплексор 26 осуществляет коммутацию на выход 27 сигнала с входа А2, который соединен с выходом элемента И-НЕ 23, входы которого подключены к выходам мультиплексоров 21-1, 21-2. Мультиплексоры осуществляют коммутацию тех же сигналов, что и в предыдущем случае. Это обеспечивается установкой кодов в регистрах 19-1 - 19и счетчике 9 (табл. 2, п. 3, колонки 5-7) и позволяет получить единичный потенциал на выходе блока 10 в слу

5

0

5

91

0

5

0

5

0

5

076

чае, если число на входах Л (фиг. ) блока 10 лежит за пределами заданного интервала. Работу всего устройства в этом случае можно рассмотреть по аналогии с предыдущим случаем.

Возможна реализация режима вывода чисел массива больших или меньших заданного числа при записи в регистры 19-1 и 19-2 нулевого или единичного кодов.

Вариант режима вывода (табл. 2, п. 4) устанавливается записью в регистр 19-3 кода 011010 (мл. разряд справа), которьй обеспечивает подключение выходов схем 20-1, 20-2 сравнения через ьгультиплексоры 21-1, 21-2 к входам элементов И-НЕ 23 и его выхода через мультиплексор 26 (вход А2) к выходу 27 блока 10 ограничения. В этом случае как в регистр 19-1, так и в регистр 19-2 записывается число, которое должно быть исключено при выводе из упорядоченного массива.

Таким образом, как только на выходах счетчика 9 установится записанное в регистры 19-1, 19-2 число, сигналь; уровня логической единицы с выхода схем 20-1, 20-2 сравнения через мультиплексоры 21-1, 21-2 поступают на входы элемента И-НЕ 23, устанавливая его в нулевое состояние. Через мультиплексор 26 этот нулевой уровень поступает на выход 27 блока 10 ограничения.

Это приводит к тому, что как и в случае табл. 2, п. 1 числа массива могут выводиться в порядке возрастания и убывания, но по шине с выхода 27 (фиг. 2) блока 10 ограничения осуществляется запрет происхождения числа, а именно записанного в регистры 19-1, 19-2 через элементы И - - 11-N, и синхронизирующего импульса через элемент И 12.

Вариант режима вывода (табл. 2, п. 5) отличается тем, что сигналы с выходов схем 20-1, 20-2 сравнения подаются на входы элемента ИЛИ-НЕ 25 И через мультиплексоры 21-1, 21-2 и его выход через мультиплексор 26 подключается к выходу 27 блока 10 ограничения. При этом сигнал Запрет запрещает прохождение чисел с выхода счетчика через элемент И 12 - на синхро шзирующий выход устройства.

Проверка принадте :ности числа упорядоченном массиву (табл. 2,

71

п. 6) осуществляется установкой в регистре кода 011010, обеспечивающего подключение в соответствии с табл. А выходов схем 20-1, 20сравнения к входам элемента И 22 че- рез мультиплексоры 21-1, 21-2 и его выхода через мультиплексор 16 к выходу блока 10 ограничения. При этом число, проверка принадлежности которого упорядоченному массиву осущест- вляется, должно быть записано в регистры 19-1, 18, а счетчик устанавливается в нулевое состояние (на входе 5 - единичный потенциал) при проверк возрастания чисел и в единичное (на входе 5 - логический ноль) при проверке в порядке убывания чисел. Указанные действия приводят к тому, что при развертывании выходных кодов счетчика 9, например, от нулевого до максимального элементы , И-12 будут закрыты нулевым потенциалом с выхода элемента 22, которьй устанавливается за счет нулевых потенциалов на входах схем 20-1, 20-2 срав- нения до тех пор, пока число на выходе счетчика 9 не сравняется с числом, записанным в регистры 19-1, 19-2. При этом на выходах схем 20-1, 20-2 сравнения, на входах элемента И 22, на его выходе и на выходе блока 10 устанавливается единичньм потенциал, и если это число в упорядоченном массиве присутствует, т.е. по адресу, задаваемому счетчиком 9, в блоке 8 записана логическая единица, элементы И 11 и 12 открываются единичным потенциалом с выхода блока 8 и выходы счетчика через открытые элементы И 11-1 - И 11-N подключаются к 13-1 - 13-N устройства, выделяя указанное число и подтверждая его принадлежность упорядоченному массиву наличием выходного кода и импульса синхронизации на выходе 14 устройства. Ее- ли такого числа нет, то на выходе блока 8 присутствует уровень логического нуля и элементы И П-1 - - И 11-N, И-12 будут закрыты дпя пе редачи информации на выход устрой- ства.

Последний вариант режима работы устройства (табл. 2, п. 7) отличается от предыдущего тем, что в регист- ры 19-1, 19-2 заносятся два проверяемых числа, мультиплексоры 21-1, 21обеспечивают подключение выходов схем 20-1, 20-2 сравнения к входам

078

элемента 1-ШИ 24, а его выход через гyльтиплeкcop 26 подключается к выходу 27 блока 10 ограничения. Такое подключение приводит к тому, что еди Н1ГЧНЫЙ потенциал на выходе 27 блока 10 ограничения появляется как при достижении кода счетчика одного, так и другого числа . Начальные этапы рабо- ты устройства д.пя сортировки массива чисел с блоком 10 ограничения (фиг.З могут быть рассмотрены аналогично. После очистки блока 8, ввода чисел упорядочиваемого Maccirea и переключения устройства в режим вывода осуществляется установка необходимого варианта режима вывода. При этом счетчик 3 служит для записи минимального или максимального числа интервала при выводе чисел, принадлежащих или лежащих за пределами .заданного интервала и проверки принадлежности или исключения одного числа иэ упорядо- ченного массива. Регистр 32-1 исполь зуется для записи второго числа интервала, регистр 32-2 необходим для запоминания выбранного режима работы схема 33 сравнения осуществляет сравнение чисел на вькоде счетчика 9 и дописаь ного в регистр 32-1 , мультиплексор 34 производит коммутацию выходов схемы 33 сравнения на выход устройства, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 35 используется как управляемый инвертор (табл. 5).

В табл, 6 приведены варианты установки режимов вывода чисел.

. Первый вариант (табл. 6, п. 1) режима вывода обеспечивается установкой соответствующих (табл. 6, колонка 7) состояний счетчика и состояния сигнала на выходе 5 устройства (табл. 6, колонка 4). Состояние регистра 32-2 (табл. 6, колонка 4) управляет работой мультиплексора ЗА, обеспечивая подключение логической единицы с входа А1 мультиплексора 34 к выходу 3, и прямую передачу сигнала с его выхода через управляемый инвертор 35 на выход блока 10 ограничения (фиг. 3).

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

1

Второй вариант (табл. 6, п. 2) устанавливается записью максимального и минимального чисел интервала либо b счетчик 9, либо в регистр 32-1 |(табл. 6, колонка 5, табл. 6, колон- а 7) и подключением выходов или и к выходу блока 10 ограниче 1ИЯ.

Работа устройства в этом случае отличается от рассмотренной тем, что счетчик 9 начинает свою работу не с нулевого или единичного кодов, а с минимального или максимального числа, начиная сразу же вьшод чисел заданного интервала. При этом по сравнению |с рассмотренным вьшге аналоп-гчным случаем повышается быстродействие при выводе чисел заданного интервала. i Третий и четвертый варианты Ктабл. 6, п. 3, табл. 6, п. 4) обес- |печиваются записью в регистре RG, 32-1, соответствующей установки начального кода счетчика 9 (табл. 6, колонки 4, 7) и входа 5 устройства

;и подключением выходов или

схемы 33 сравнения через мультиплексор 34 и схему ИСКЛЮЧАЮЩЕЕ ИЛИ к выходу блока 10 ограничения, что производится установкой соответствующего (табл. 6, колонка 6) состояния регистра 32-2. При этом схема сравнения в зависимости от состояния сигналов на входах 28 и 29 либо разрешает либо запрещает вьшод чисел массива.

Установка последующих двух вариан тов работы устройства обеспечивается подключением выхода схемы 33 к выходу 36 блока 10 ограничения, либо через инвертор, либо напрямую, что осуществляется установкой кодов соот ветствутощих табл. 6, колонки 4-7, п. 5, 6. .

При этом в случае .(табл. 6, п. 5) управляемый инвертор 35 работает в режиме инвертирования, запрещая про- хождение кода с выхода счетчика 9 через элементы И 11-1 - 11-N на выходы 13 устройства.

В случае табл. 6, п. 6 схема 33 сравнения через мультиплексор 34, управляемый инвертор 35, работающий как повторитель, разрешает прохождение через элементы И 11 числа с выхода счетчика 9 лишь в случае, если оно равно числу, записанному в ре- гистр 32. , Формула изобретения

5 0

5

0

0

5

0 5

10710

реверсивный счетчик, блок памяти, группу из N элементов И, (N - разрядность сортируемых двоичных чисел), элемент И, причем информационные входы устройства соединены с информа- ifliOHHMMH входами реверсивного счетчика, управляющий вход Ввод-вывод устройства соединен с входом выбора режима блока памяти, выходы разрядов реверсивного счетчика соединены с адресными входами блока памяти и первыми входами соответствующих элементов И группы, вторые входы которых соединены с выходом блока памяти и подключены к первом входу элемента И выход которого является синхронизирующим вьтходом устройства, выходы элементов И группы являются информационными выходами устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет отбора отсортированных чисел по заданным признакам, введены блок ограничений и элемент задержки, причем входы задания признаков устройства соединены с информационными входами коммутатора, управляющий вход которого соединен с входом Перепись устройства, вход Возрастание-убьгеание устройства соединен с входом выбора режима реверсивного счетчика, информационные входы которого объединены с соответствующими входами первой группи информационных входов блока ограничения, информационные входы второй группы которого соединены с соответствующими выходами разрядов реверсивного счетчика, первый выход коммутатора соединен с входом установки в О блока памяти, второй выход коммутатора соединен с Запись реверсивного счетчика и через элемент задержки - с входом Запись блока памяти, третий, четвертый и пятьй выходы коммутатора соединены соответственно с первым, вторым и третьим управляющими входами блока ограничения, щестой выход коммутатора соединен с входом установки в О реверсивного счетчика, а седьмой выход - с тактовым входом реверсивного счетчика и вторым входом элемента И, третий вход которого соединен с выходом блока ограничения и с объединенными третьими входами элементов И группы.

ннчений содержит пегтый, второй и третий регистры, первую и вторую схе 4JI сравнения, первьй, второй и трети ьтультиштексоры, элемент И, элемент И-НЕ и элемент ШШ-НЕ, причем первая группа информационных входов блока ограничений соединена с соответствующими объединенными i-входами (i 1.,.N) первого, второго регистров и k-входами (k I ., .6) третьего ре- гистра, вторая группа информационных входов блока ограничения соединена с входами первых групп первой и второй схем сравнения, группы входов которых соединены с выходами соответ ствующих разрядов первого и второго регистров, первый, второй и третий управляющие входы блока ограничений соединены соответственно с входами Запись первого, второго и третьего регистров, выходы первой и второй схем сравнения соединены соответственно с первыми, вторыми и третьими информационными входами первого и второго мультиплексоров, четвертые входы которых соединены с входом логической единицы устройства, первый и второй, третий и четвертый, пятый и шестой выходы третьего регистра соединены соответственно с управляю- щими входами первого, второго и третьего мультиплексоров, выходы первого и второго мультиплексоров соединены с соответствующими объединенными первыми и вторыми входами элементов И, элемента ИЛИ и элемента ИЛИ-НЕ, выходы которых соединены с соответст07.12

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

4O tи

u о

a

«7

и

fО

ex

ь

к

и

X

со

о о 1

о

о о

ТаВлипа 2

«гг.З