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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советскнк

Социалистических

Республик

<щ981989 (&1) Дополнительное к авт. свид-ву(22) Заявлено27. 04. 81 (21) 3278025/18»24 (И) М. Ка.з с присоединением заявки NoG 06 F 7/08

Государствеииый комитет

СССР ио делам изобретеиий и открытий (23) ПриоритетОпубликовано 15,12.82.Бюллетень Йо 46

Дата опубликования описания 15 . 12. 82

tS3)УДК 681. 325 (088. 8) (72) Автор изобретения

A.Ñ.Èëüêí (71) Заявитель (54) УСТРОИСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

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

5 технических средств цифровых .вычнслительйых машин и дискретной автоматики.

Известно устройство для сортировки чисел, содержащее ячейки, каждая из которых: содержит и триггеров, группу из 2 (Il-l) входных элементов

И, группу из (п-1) выходных элементов И дешифратор с и входами и m выходами, (m-2) элементов НЕ, группу из m элементов И, m элементов ИЛИ (1), 15

Недостатком устройства является то, что выбор максимального числа в диапазоне 0-2 посредством дешифрац тора требует применения (m-2) элементов НЕ, m элементов И, m элементов ИЛИ, где m=2", что увеличивает аппаратурные затраты (в предлагаемом техническом решении аппаратурные затраты пропорциональны и).

Известно также устройство для сортировки чисел, содержащее матрицу ячеек, каждая из которых состоит иэ триггера со входными элементами И, инвертора, элементов И н ИЛИ (21 .

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

Наиболее близким к изобретению является устройство для сорткровки чисел, которое содержит m регистров, в которые записываются исходные числа, m схем сравнения, регистр результата, в котором формируется очередное максимальное (минимальное) число, элемент ИЛИ, элементы И, триггер, узлы запрета, коммутатор,переключатель, причем выходы i-ro регистра соединены со входами i-ой схемы сравнения, выходы схем сравнения соединены со входами переключателя, первые входы каждого из первых элементов И являются управлякицими входами устройства, первые или вторые выходы неравенства схем сравнения, в зависимости.от положения переключателя, связайы с соответствующими входами первого .элемента ИЛИ, выход которого соединен со входом установки в нулевое состояние триггера, выходы равенства схем сравнения подключены к управлякицему входу соответствующих узлов запрета, вторые и третьи вхо981989 ды которых связаны соответственно Г управляющими шинами устройства, выходы узлов запрета соединены со вторыми вхо дами соответствующих первых элементов

И, выход которого соединен с управляющим входом схемы сравнения, вход установки в единичное состояние триг- гера подключен к шине тактовых сигна-; лов, а его прямой и инверсный выходы связаны через переключатель с первым входом второго элемента И, второй вход которого подключен к управляющей шине устройства, выход второго эле» мента И соедйнен со входом установки в нулевое состояние. регистра результата, входы поразрядного управления 15 регистра результата подключены к соответствующим выходам коммутатора, вход которого связан с шиной тактовых сигналов, входы установки разрядов регистра результата в единичное состояние соединены с управляющей шиной устройства (3) .

Недостатком этого устройства является низкое быстродействие за счет того, что.максимальное (минимальное) число формируется в регистре результата путем последовательного внесения в его- разряды, начиная со старшего, значения "О" или " ", вследствие чего сортировка а и-разрядных чисел осуществляется за (и+1)щ тактов работы.

Цель изобретения — повышение бЫст- родействия устройства путем сравие ния одновременно различных пар чисел,35 записанных в регистры.

Поставленная цель достигается тем, что устройство для сортировки чисел, содержащее m регистров, m-1 схем сравнения, многовходовай элемент ИЛИ,эле-4О менты И, переключатели, причем выходы i-го и (i+1)-го регистров поразряу но соединены со входами i-й схемы сравнения (il,..., m-1, где m - максимальное количество соРтируемых чи- 45 сел), выходы которой соединены со входами соответствующего переключателя, выходы переключателей соединенЫ .с соответствующими входами многовходового элемента ИЛИ, входы управления обменом соединены с первыми входами соответствующих элементов И, содержит элементы неравнозначности, элементы ИЛИ, дополнительные элементы И, причем выходы i-ro и (1+1)-го регистров поразрядно. соединены со входами элементов неравнозначности, собтветствуюших 1-й схеме сравнения, выходы схем неравноэначности соединены с первыми входами соответственных дополнительных элементов И, вто- 60 рые входы которых соединены с выходом соответствующего .элемента И, вторые входы элементов И соединены с выходами соответствующих переключателей, выходы дополнительных элементов И, соответствующих i-й схеме сравнения соединены с первыми входами элементов ИЛИ, соответствующих

i-му регистру и со входами элементов

ИЛИ, соответствующих (i+1)-му регистру; выходы элементов ИЛИ поразряд-. но соединены со входами соответствующих регистров, выход многовходового элемента ИЛИ соединен с выходом сигнализации о неупорядоченном расположении чисел в регистрах устройства.

На чертеже представлена функциональная схема устройства.

Устройство содержит m регистров

1, m-1 схем сравнения 2, переключатели 3, многовходовой элемент ИЛИ 4, элементы И 5, входы управления обменом б, элементы неравнозначности 7, дополнительные элементы И 8, элементы ИЛИ 9 °

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

Схема сравнения 2, выбираемая в зависимости от кодировки чисел в регистрах, через соответствующий пере« ключатель 3 сигнализирует о необходимости поменять местами числа в регистрах 1. Этот сигнал является разре- шающим для выполнения операции обме. на чисел в регистрах 1 и с помощью элемента И 5 логически перемножается с управляющим сигналом, поступающим по входу б и передаваемым на вход схемы обмена чисел в регистрах, которая состоит из элементов неравнозначности 7, элементов И 8 и элементов ИЛИ 9. Йапичие сигналов на выходе схем неравнозначности 7 свидетельствует о том, что соответствующие триггеры регйстров 1 находятся в противоположных состояниях: один в состоянии "0", другой - "1", или наоборот, Следовательно, в момент появления управляющего сигнала по входу б, каждый из триггеров изменит свое состояние иа противоположное, что эквивалентно обмену чисел в регистрах 1.

Обмен происходит одновременно для всех разрядов сравниваемых чисел независимо от их кодировки. Переключатель 3 предназначен для подключения входов элементов И 5 и элемеита ИЛИ

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

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

S m(log m)

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

Устройство для сортировки чисел, содержащее m регистров, m-1 схем срав« кения, многовходовой элемент ИЛИ,элементы И, переключатели, причем вы.ходы i-го и (i+1)-ro регистров поразрядно соединены с входами i-й схемы сравнения (i=1,...,m-1; где m - максимальное количество сорткруемях чисел), выходы которой соединены с входами соответствующего переключателя, выходы переключателей соединены с соответствующими .входами многовходового элемента ИЛИ, входы управления обменом соединены с первыми входами соответствующих элементов И, о т л и ч а ю щ е е с я тем, что,с целью повыаенкя быстродействия,устройство содержит элементы неравнозначности, элементы ИЛИ, дополнительные элементы И, причем выходы i-го и (1+1)-го регистров поразрядно соединены с входами элементов неравнозначности, соответствующих i-й схеме сравнения, выходы схем неравнозначностк.соединены с первымк входами соответствующих дополнительных элементов И, вторые. входы которых сое» динены с выходом соответствующего элемента И, вторые входы .элементов

И соединены с выходами соответствующих переключателей, выходы дополнительных элементов Й, соответствукщкх

i-й схеме сравнения, соединены с первыми входами элементов ИЛИ, соответствующих i-му регистру, и с вторымивходами элементов ИЛИ, соответствующих (i+1)-му регистру, выходы элементов -ИЛИ поразрядно соединены с входами соответствующих регистров, выход многовходового элемента ИЛИ оединен с выходом сигнализации неупорядоченном расположении чи-. ел в регкстрах устройства.

Источники информации, ринятые во.внкмание при экспертизе

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

590728> клф G 06 F 7/00, 1978.

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

424141 кл С. 06 Р 7/00, 1974.

3. Авторское свйдетельство СССР

637810 кл. С 06 F 7/08, 1978 прототип). с

Для предлагаемого устройства грао ницы диапазонов изменения величин

t — количество тактов работы устрой- 5$ с ства и S — количество схем сравнения и обмена не зависят от разрядности чисел и и при заданном m определяются следующим образом. Р

Минимальными аппаратурными затратави обладает известный метод четно- Р нечетной сортировки с транспозициями.

В этом случае в данном устройстве Р количество схем сравнения S = m-1, .(I нительной схевы сравнения 2 и соответствукщей ей схемы обмена обеспечи.вает воэможность расширения устройства посредством последовательного

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

2 и входы элементов неравнозначности

7 соответствующей схемы обмена соединены с выходами только одного регистра 1, управляющий вход б, соответствующего им элемента И 5 должен - 10 быть обнулен.

Элементы неравнозначности 7, кроме своих основных функций в составе схем обмена, могут играть вспомогательную роль для схем сравнения 2. 15

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

Технический эффект от использования предлагаемого .технического решения заключается в повышении быстродействия работы устройства путем одновременного сравнения и обмена чисел различных пар регистров.При этом появляется возможность широко« го выбора желаемого (требуемого) 40 соотношения между аппаратурными затратами и временем работы устройства при заданном количестве регистров 1 путем изменения количества схем сравнения и обмена, их располо- 45 женкя между регистрами 1 и распределения сигналов по управляющим вхо» дам б.

Количество тактоз работы извест-ного устройства 50 (n+1) m, количество тактов работы устройства

t =. m, а управлялцне сигналы должны подаваться поочередно на все четные управляющие входы, затем на все нечетные и т.д.

Минимальными затратами времени обладают методы Бэтчера. В этом случае в: устройстве

981989

Составитель A. Суздалев

Техред T.Маточка Корректор Н. Король

Редактор N. Товтин

Заказ 9712/68 Тираж 731 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

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

 

Похожие патенты:

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

Изобретение относится к электронной карточке-кошельку и способу ее перезарядки для безналичного платежного оборота

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

Изобретение относится к вычислительной технике и может быть использовано для исследования систем массового обслуживания (СМО)

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

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

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

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