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

О

СА)

4V СО 00

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит регистры 1, блоки сравнения 2, блоки выбора кодов 3, коммутатор 4, счетчики 5, дешифраторы 6, блок загрузки 21, элементы ИЛИ 24, 25, 26, 29, элементы НЕ 27, 28, триггер 30. Первоначально 1-м числам присваиваются ранги, равные I, которые записываются в счетчики 5. Затем числа, ранги которых отличаются на ёдЫй- цу, попарно сравниваются друг с другом; и в результате сравнения меняются их ранги. Сравнивание чисел производится до тех пор, пока ранги не перестают изменяться. 6 ил., 3 табл. w/TTT

Шиг.1

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

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

- управления переписью, элемент И управления циклом, группу элементов ИЛИ, коммутатор чисел, коммутатор циклов, причем управляющий вход устройства соединен с входом узла синхронизации, первый выход которого соединен с выходом управления режимом схемы сравнения, выход которой соединен с первым входом элемента И, кроме того, регистры выполнены с третьим состоянием, а элементы И управления циклом с открытым коллектором, коммутаторы чисел и циклов выполнены .соответственно на первом и втором Сдвиговых регистрах, управляющий вход устройства является его тактовым входом, узел синхронизации выполнен на D-триггере, синхровход которого .является входом узла синхронизации,.прямой выход - выходом узла синхронизации, вход управления режимом схемы сравнения является входом задания режима Больше, вход задания режима Меньше схемы сравнения соединен с инверсным выходом D- триггера и его D-входом, первый вход первого элемента ИЛИ группы подключен к входу логического нуля устройства, выходы одноименных разрядов всех нечетных регистров с третьим состоянием подключены к соответствующим входам первой группы схемы сравнения и соответствующим информационным входам всех четных регистров с третьим состоянием, одноименные выходы разрядов которых подключены к соответствующим входам второй группы схемы сравнения и соответствующим информационным входам всех нечетных регистров с третьим состоянием, вход разрешения считывания 1-го .регистра, с третьим состоянием, где 1 1,2, ..., п, соединен с выходом i-ro элемента ИЛИ группы и первым входом 1-го элемента И управления переписью, выход которого соединен с синхровходом 1-го регистра с третьим состоянием, вторые входы всех элементов И управления переписью подключены к выходу элемента И, второй вход которого соединен с тактовым входом устройства и синхровходом первого сдвигового регистра, вход на чальной установки которого соединен с выходами всех элементов И управления циклом с открытым коллектором и входом

начальной установки второго сдвигового регистра, выход первого разряда которого является выходом конца цикла устройства, а выход j-ro разряда, где j 2, 3, ..., п, соединен с первым входом Q-1)-ro элемента И управления циклом с открытым коллекто- . ром, второй вход которого соединен с выходом J-ro разряда первого сдвигового регистра, вторым входом Q-l)-ro и первым

входом j-ro элементов ИЛИ группы, второй вход п-гр элемента ИЛИ группы подключен к входу логического нуля устройства.

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

Известно устройство для сортировки чисел, содержащее m регистров, т-1 схем

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

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

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

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел, содержащее m регистров, (где m -- количество сортируемых чисел), m элементов сравнения и m элементов И, причем выходы 1-го регистра (где 1 1,2, .,., т) соединены с первой группой входов 1-го элемента сравнения, кроме того, устройство содержит m счетчиков и коммутатор, первая группа информационных входов которого является группой информационных входов устройства, вход задания режима устройства соединен с управляющим входом коммутатора, выходы которого соединены с установочными входами пер- вого регистра и вторыми группами входов всех элементов сравнения, выходы j-ro регистра (где J 1, 2, .... т-1) соединены с установочными входами (j+)-ro регистра, выходы m -ro регистра являются информа- ционными выходами устройства и соединены с второй группой информационных входов коммутатора, выход 1-го элемента сравнения соединен с первым входом 1-го элемента И, выход которого соединен со счетным входом 1-го счетчика, выходы разрядов j-ro счетчика соединены с установочными входами (j+1)-ro счетчика, выходы разрядов m-ro счетчика являются адресными выходами устройства и соединены с ус- тановочными входами первого счетчика, первый тактовый вход устройства соединен с входами разрешения записи всех регистров и счетчиков, второй тактовый вход устройства соединен с вторыми входами всех элементов И.

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

Целью изобретения является повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее m регистров, где m - количество сортируемых чисел, m счетчиков, К блоков сравнения, где К т/2, Х - ближайшее целое, не больше X, коммутатор и два элемента И, причем вход начальной установки устройства соединен с входом установки счетчиков в нулевое состояние, введены К блоков выбора кодов, m дешифраторов, блок загрузки номеров чисел в счетчики, триггер, четыре элемента ИЛИ и два элемента НЕ. коммутатор содержит К блоков коммутации, содержащих каждый, кроме К- го, четыре группы элементов И и четыре элемента ИЛИ, К-й блок коммутации содержит четыре группы элементов И и (4+2 modam) элементов ИЛИ, каждый блок сравнения содержит шесть элементов И, три элемента ИЛИ, два элемента НЕ, четыре

элемента И-НЕ и три триггера, каждый блок выбора кодов содержит три мультиплексора, тактовый вход устройства соединен с входом управления сдвигом регистров, выход старшего разряда J-ro регистра 0 1,2, ... т) соединен с j-ми информационными входами мультиплексоров блоков кодов, выход Si-ro мультиплексора 1-го блока выбора кодов (Si 1, 2, 3, I 1, 2, .... К) соединен с первым входом Si-ro элемента И 1-го блока сравнения, $2-й выход которого ($2 1. 2) соединен с l-м входом Sa-ro элемента ИЛИ и с первыми входами всех элементов И (2S2- 1)-й и 2$2-й групп 1-го блока коммутации, входы г-го элемента ИЛИ (г 1, 2, 3, 4) 1-го блока коммутации подключены к выходам (21 - mod2f)-x элементов И (г+1) и ХЗ+3) групп всех блоков коммутации, при m - нечетном входы ($2+4)-го элемента ИЛИ К-го блока коммутации подключены к выходам (2Н-1)-х элементов И $2-й и (52+2)-й групп всех блоков коммутации, выход (2S2- 1)-го и 2$2-го элементов ИЛИ 1-го блока коммутации соединены соответственно с суммирующим и вычитающим входами (21- 2+$2)-го счетчика, выходы разрядов которого соединены с входами (21-2+$2)-го дешифратора, J-й выход р-го дешифратора, где р 2, 4,.... 2К, соединен с J-м управляющим входом второго мультиплексора p/2-ro блока/выбора кодов, j-й выход q-ro дешифратора, где q 3, 5,..., 2К-1, соединен с J-ми управляющими входами первого мультиплексора (q+1)/2-ro блока выбора кодов и третьего мультиплексора (q-1)/2-ro блока выбора кодов, j-й выход первого дешифратора соединен с j-м управляющим входом первого мультиплексора первого блока выбора кодов, при m - нечетно.-i j-й выход т-го дешифратора соединен с J-м управляющим входом третьего мультиплексора К-го блока выбора кодов, выходы j-ro дешифратора являются информационными выходами j-й . группы устройства, J-й выход (2l-1+ r/2D-ro дешифратора соединен с. вторым входом J- го элемента И r-й группы 1-го блока коммутации, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами третьего элемента ИЛИ, и через первый и второй элементы НЕ - соответственно с первым и вторым входами первого элемента И, выход которого соединен с входом установки триггера в единичное состояние и первым входом второго элемента И, выход которого является выходом окончания работы устройства, выход третьего элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с входом установки триггера в нулевое состояние, выход которого

соединен с вторым входом второго, элемента И, вход начальной установки устройства соединен с входами установки триггеров блоков сравнения в нулевое состояние и входом начальной установки блока загрузки номеров чисел в счетчики и вторым входом четвертого элемента ИЛИ, вход управления загрузкой устройства соединен с управляющим входом блока загрузки номеров чисел в счетчики, выходы которого соединены с установочными входами счётчиков, вход синхронизации устройства соединен с входом синхронизации первого и второго триггеров всех блоков сравнения, в каждом блоке сравнения первый вход четвертого элемента И подключен к первому входу второго элемента И, в каждом блоке сравнения выходы (2$2-1)-то и 252-го элементов И соединены соответственно с первым и вторым входами Sa-ro элемента ИЛИ, выход которого соединен с первым входом (3-52)-го элемента И-НЕ и через 52-й элемент НЕ - с вторым входом 52-го элемента И-НЕ, выход которого соединен с первым входом (52+2)- го элемента И-НЕ, выход которого соединен с информационным входом 52-го триггера, инверсный выход которого соединен с третьим входом (3-52)-го элемента И-НЕ и с вторым входом (52+2)-го элемента И-НЕ, прямой выход второго триггера соединен с информационным входом третьего триггера, выход которого соединен с первыми входами пятого и шестого элементов И, вход синхронизации третьего триггера подключен к выходу третьего элемента ИЛИ, 52-й управляющий вход устройства соединен с вторыми входами 52-го (52+4)-го и (5-52)-го элементов И блоков сравнения и с 52-м входом третьего элемента ИЛИ блоков сравнения.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - функциональная схема блоков выбора кодов и блоков сравнения; на фиг, 3 - функциональная схема коммутатора; на фиг. 4 - функциональная схема блока загрузки номеров чисел в счетчики; на фиг. 5 - временная диаграмма работы устройства; на фиг. 6 - функциональная схема элемента сравнения.

Устройство для сортировки (фиг. 1) содержит m регистров 1 i,.,.,1m, К блоков сравнения 21,...,2к (где К т/2 - целая часть числа т/2, К блоков выбора кодов 3;,...,3к, коммутатор 4, гп счетчиков 5i,...,5m, m дешифраторов 6i,...,6m, причем выход каждого регистра 1i,...,1m соединен с входом 7 блоков выбора кодов 31,...,3к. а выходы 8, 9, 10 каждого блока выбора кодов 31,...,3к соединены г входами соответствующего блока

сравнения 21,....2к. выходы 11 и 12 которых соединены с соответствующими входами коммутатора 4. Выходы 13 и 14 коммутатора 4 соединены попарно с суммирующим и вычитающим входами счетчиков 5i,...,5m, информационные выходы которых подключены к входам дешифраторов 6i,...,6m. Выходы 15 дешифраторов 6i,...,6m соединены соответственно с входами бло0 ков выбора кодов 31,...,3к и коммутатора 4, а также являются группой выходов устройства. Тактовый вход 16 устройства подключен к входам управления сдвигом регистров 1i,...,1m, управляющие входы 17, 18, вход

5 начальной установки 19 и вход синхронизации 20 устройства соединены с соответствующими входами блоков сравнения 21,...,2к, кроме того, вход начальной установки 19 устройства подключен также к входам уста0 новки в нулевое состояние счетчиков 5i,...,5m и входу начальной установки блока загрузки 2Т, управляющий вход которого соединен с входом управления загрузкой 22 устройства, а его информационные выходы

5 23 - к установочным входам счетчиков 5i,...,5m. Выходы 11 и 12 блоков сравнения 21....,2к соединены с входами элементов ИЛИ 24 и 25 соответственно, выходы которых подключены к входам элемента ИЛИ 26

0 и через элементы Н Е 27,28 к входам элемента ИЛИ 29, Выход которого соединен с входом установки в единичное состояние .триггера 30 и первым входом элемента И 31, второй вход которого подключен к прямому

5 выходу триггера 30, а выход является выходом 32 окончания работы устройства. Выход элемента ИЛИ 26 соединен с первым входом элемента ИЛИ 33, второй вход которого подключен к входу начальной установки 19

0 устройства, а выход - к входу установки в нулевое состояние триггера 30.

На фиг. 2 представлена функциональная схема двух блоков выбора кодов 3k и 3(|см)(где k 1,2,.... К, K m/2Q, каждый из

5 которых содержит три мультиплексора 34,

35, 36, выходы которых 37, 38, 39 являются

выходами 8, 9, 10 каждого блока выбора

кодов 31,.,.,3-к соответственно, .причем 1-е

входы мультиплексоров 34, 35, 36 соедине0 ны с выходом старшего разряда 1-ro регистра 1i,...,1m (где ,2,.... m), j-й выход 2k-ro дешифратора 6i,...,6m, k 1,2, .... К, соединен с j-м управляющим входом мультиплексора 35 k-ro блока выбора кодов Зт,...,3к- J-й

5 выход (2k+1)-ro дешифратора 6i,..,6m, соединен с j-м управляющим входом мультиплексора 34 2k-ro блока выбора кодов 31,...3к и мультиплексора 35 k-ro блока выбора кодов 31,...3к. -й выход первого дешифратора 61 соединён с j-м управляющим входом мультиплексора 34 первого блока выбора кодов Зч. При m - нечетном j-й выход m-ro дешифратора 6т соединен с j-м управляющим входом мультиплексора 36 К-го блока выбора кодов Зк.

На фиг. 2 также представлена функциональная схема двух блоков сравнения 2k, 2(k+i).(w k 1, 2,.... К, К m/2D. каждый из которых содержит элементы И 40, 41, 42, 43, 44, 45, элементы ИЛИ 46, 47 и элемент 48 сравнения, причем первые входы элементов И 40, 41 и 42 блока сравнения 2k подключены к выходам 8,9,10 блока выбора кодов 3k. первый вход элемента И 43 также подключен к выходу 9 блока выбора кодов 3k. Вторые входы элементов И 40, 43 и 44 блоков сравнения 21.,,,.2к соединены с управляющим входом 17 устройства, а вторые входы элементов И 41, 42 и 45 блоков сравнения 21,...,2к соединены с управляющим входом 18 устройства, выходы элементов И 40, 41 и элементов И 42, 43 подключены к входам элементов ИЛИ 46,47 соответственно, выходы которых соединены с информационными входами 49 и 50 элемента 48 сравнения соответственно. Входы установки в нулевое состояние и синхронизации элемента 48 сравнения блоков сравнения 21,...,2к подключены к входам начальной установки 19 и синхронизации 20 устройства соответственно, а его выход соединен с первыми входами элементов И 44 и 45, выходы которых являются выходами 11 и 12 блоков сравнения 21,.,.,2к соответственно.

Коммутатор 4 содержит К блоков коммутации 511,...,51 к (где К т/2, функциональная схема двух из которых 51k и 51{k+i) представлена на фиг. 3 (где k 1, 2, .... К). Каждый блок 511,...,51к содержит четыре группы 52г,...,524 элементов И и элементы ИЛИ 53г, 532, ИЛИ 54i, 542. В случае, когда m - нечетное число, блок 51 к содержит дополнительно элементы ИЛИ 53з, 54з. Каждая группа 52i,...,524 элементов И блоков 511,...,51к содержит m элементов И 55, причем первые входы элементов И 55 групп 52 г и 522 элементов И блока 51k соединены с выходом 11 блока сравнения 2k, а первые входы элементов И 55 групп 52з и 524 элементов И - с выходом 12 блока сравнения 2k. Вторые входы i-ro элемента И 55 групп 52ч элементов И блока 51k подключены к (2Ы)-му выходу 1-го дешифратора 6i,...,6m (где 1 1,2,.... т), вторые входы 1-го элемента И 55 групп 52а и 52з элементов И - к 2k-My выходу 1-го дешифратора 6i,...,6m, вторые входы 1-го элемента И 55 группы 524 элементов И - к (2k+1)-My выходу 1-го дешифратора 6i,...,6m. Выходы элементов И 55 групп 52i и 52з элементов И блоков 511,...,51к объединены и подключены таким образом, что(т-1) входы элемента ИЛИ 53i блока 51k подключены к выходам (2k-1)-x элементов И 55 групп 52i и 52з элементов И блоков 5 5Ti,...,51 к, (т-1) входы элемента ИЛИ 532-к выходам 2к-х элементов И 55 групп 521 и 52з элементов И блоков 511,...,51к. Аналогично, выходы элементов И 55 групп и 524 элементов И блоков 5Н,...,51к объединены и

0 подключены таким образом, что (т-1) входы элемента ИЛИ 541 бл.ока 51k подключены к выходам (2k-1)-x элементов И 55 групп 522 и 524 элементов И блоков 511,...,51к, (m-1) входы элемента ИЛИ 542 - к выходам 2(-х эле5 ментов И 55 групп 522 и 524 элементов И блоков 511,...,51к. Выходы элементов ИЛИ 531 и 532 блока 51k подключены к суммирующим входам (2k-1)-ro и 2k-ro счетчиков 5i,...,5m соответственно, а выходы элемен0 тов ИЛИ 54i и 542 - к вычитающим входам (2k-1)-ro и 2k-ro счетчиков 5i,...,5m соответственно.

Блок 21 загрузки номеров чисел в счетчики (фиг. 4} содержит счетчик 56 и рдемуль5 типлексоров571,...57р(гдер 1од2т), причем вход сброса и суммирующий вход счетчика 56 подключены к входам начальной установки 19 и управления загрузкой 22 устройства соответственно, р информационных выхо0 дов - к соответствующим адресным входам демультиплексоров 57i,...,57p, кроме тог о j-й информационный выход счетчика 56 соединен с информационным входом WOj-ro демультиплексоров 57i,...,57p (где j 1,

5 2, ..., р), а 1-е выходы демультиплексоров 57i,...57p являются выходами 23 блока 21 загрузки и соединены с соответствующими установочными входами 1-го счетчика 51,...,5m (где I 1, 2,..., m).

0 Элемент 48 сравнения (фиг. 6) содержит триггеры 58, 59. 60, элементы И-НЕ 61, 62, 63, 64 и элементы НЕ 65, 66 и ИЛИ 67, причем входы 49 и 50 элемента 48 сравне- ния соединены с первыми входами элемен5 тов И-НЕ 62 и 61 соответственно и через элементы НЕ 65 и 66 - со вторыми входами элементов И-НЕ 61 и 62 соответственно, третьи входы которых подключены к инверсным выходам триггеров 59 и 58 соответст0 венно и первым входам элементов И-НЕ 64 и 63 соответственно, а выходы - к вторым входам элементов И-НЕ 63 и 64 соответственно. Информационные входы триггеров 58 и 59 соединены с выходами элементов

5 И-НЕ 63 и 64 соответственно, а входы установки в нулевое состояние и синхронизации -с входами начальной установки 19 и синхронизации 20 устройства соответственно, причем прямой выход триггера 59 под- ключен к информационному входу триггера

60, прямой выход которого является выходом элемента 48 сравнения, вход установки в нулевое состояние триггера 60 подключен к входу начальной установки 19 .устройства, а вход синхронизации - к выходу элемента ИЛИ 67, входы которого соединены с управляющими входами 17 и 18 устройства.

Устройство работает следующим обра-ЗОМ.: . . . - .

В начале работы по управляющему сигналу на входе 19 устройства происходит установка в нулевое состояние счетчиков 5i,...,5m, счетчика 56 блока 21 загрузки и триггеров 58,59, 60 элемента 48 сравнения, а также триггера 30 устройства, в результате чего на выходе 32 устройства присутствует сигнал логического нуля. Одновременно с записью в регистры 1 i,...,1m исходных чисел (цепи начальной установки и занесения чисел не приводятся) в счетчиках 5i,...,5m формируется с помощью блока 21 загрузки необходимая информация, т.е. фиксируется порядковый номер соответствующего регистра 11,..,, 1 т- Затем начинается непосредственно процесс сортировки, в первом такте которого выполняется сравнение данных, находящихся в (2к-1)-м и 2к-м регистрах 1i,..,,1m, где к 1, 2, .... К, К т/2, под действием управляющего сигнала Y1 на входе 17 устройства. В результате для большего данного, находящегося в (2к-1)-м регистре 1к...,1m происходит увеличение на единицу содержимого в соответствующем (2k-1)-M счетчике 5i,...,5m. Одновременно происходит уменьшение на единицу содержимого 2к-го счетчика 5i,...,5m, соответствующего меньшему данному, находящемуся в 2k-M регистре 1i,...,1m. В случае, если большее число находится в 2к-м регистре 1i,...,1m, изменений содержимого, в соответствующих (2k-1)-M и 2k-M счетчиках 5i,.,.,5m не происходит. .

Во втором такте под действием управляющего сигнала Y2 на входе 18 устройства сравниваются пары чисел в 2k-M и (2k+1)-M регистрах 1i,...,1m аналогично процессу, описанному для первого.тактэ в (2k-1)-M и 2k-M регистрах 1i,...,1m соответственно. Далее выполняются действия, аналогичные выполняемым в первом и во втором тактах цикла сортировки до тех пор, пока не будет присвоен старший по- рядковый номер большему из исходных чисел, а меньший порядковый номер - меньшему числу, что фиксируется появлением единичного сигнала на выходе 32 окончания работы устройства.

В процессе сортировки в каждом из блоков выбора кодов 31,...,3к (фиг. 2) сигналы l(2k-i), l2k, l(2k+i) на выходах 37, 38, 39 формируются следующим образом:

.

,);3

где ai - значение (содержимое) 1-го регистра ii,..,im;

l(2k-i)i, l(2k), I(2k-H)i - значение (2k-1)-ro,

2k-ro (2k+1)-ro разрядов l-ro дешифратора

6l,...,6m.

Последовательность выполнения нечет- ного и четного тактов цикла сортировки инициируется последовательностью появления сигналов Yi,Ya на входах 17 и 18устройства. С помощью элемента 48 сравнения определяется случай, когда первое из пары сравни- ваемых чисел больше второго. В результате, в случае выполнения этого соотношения, в нечетном такте появляется единичный сигнал qk, на выходе 11 соответствующего k-ro блока сравнения 21,....2к, в четном такте - единичный сигнал qk1 на выходе 12 соответствующего k-ro блока сравнения 2т,...,2к (где ,2, .... К) (фиг. 2).

30

На выходах 13 и 14 блока 51k коммутатора 4 (фиг. 3) формируются сигналы q{2k-i)+ и q(2k-i) q(2k) и q(2k) соответственно, которые вызывают увеличение и уменьшение на единицу содержимого в (2к-1)-м и 2к-м счетчиках 5i,...,5m соответственно, для которых 35 характерны следующие соотношения:

. И

U

- Лег т -11 - исСт - 1

U

U

1(«Г ;е( Я -%(ч

где. .

uak-tf (2к.у;1 1сг ЛилЯ { 2ц;

Wk-irfk n- v ukrl (2kr 1г:МХ,Я.а Формирование соответствующих порядковых номеров в сметчиках 5i,...,5m выполняется следующим образом (фиг. 4). С

приходом каждого тактового импульса Yo по входу 22 управления загрузкой устройства в предварительно обнуленном счетчике 56 блока 21 загрузки номеров чисел в счетчики происходит увеличение его содержимого на единицу. Емкость счетчика 56 и количество демультиплексоров 57i,...,57p должно быть равно величине р logam. Информация, формируемая в каждом такте цикла загрузки Тзагр (фиг. 5) в счетчике 56, является адресом, поступающим на входы

A0,...,A(p-i) демультиплексоров 57i,...,57p, по которому осуществляется запись в счетчики 5i,...,5m. и одновременно данными, поступающими на информационный вход WO соответствующего демультиплексора 57i,...,57p. Таким образом, в 1-й такт цикла загрузки число, равное величине Т,записывается по 1-му адресу, т.е. в 1-й счетчик 5i....,5m (где I 1,2,.... т)..

Элемент 48 сравнения (фиг. 6) предназ- начен для выполнения анализа двоичных чисел, начиная со старших разрядов. В начальном состоянии триггеры 58.59,60 обну- лены. При сравнении значения одноименных разрядов величин а(2Ы) и apk) в нечетных тактах и величин a(2k) и a(2k+i) в четных тактах цикла сортировки последовательно и синхронно подаются на соответствующие входы 49 и 50 элемента 48 сравнения. С приходом каждого тактирую- - щего сигнала Y4 на вход 20 синхронизации устройства триггеры 58 и 59 переходит в новое состояние. Триггеры 58 и 59, элементы И-НЕ 61, 62, 63, 64 и элементы НЕ 65, 66 составляют схему ячейки, используемой при сравнении величин.

Триггер 60 и элемент ИЛ И 67 служат для фиксации окончательного результата процесса попарного сравнения исходных чисел в каждом такте (четном или нечетном) цикла сортировки. В случае, если выполняется соотношение a(2k-i) a(2k) или ару api-n), на выходе триггера 60, т.е. на выходе Больше элемента 48 сравнения, появляется единичный сигнал с приходом заднего фронта сиг- налов Yi(Y2J на управляющих входах 17 и 18 устройства соответственно.

Рассмотрим потактную работу устройства при сортировке чисел, например: ai 9, Э2 1, аз 3, ЗА 5, as 7.

В табл. 1 показано исходное состояние регистров 1i,...,1s и счетчиков 5i,...,5s, а также наличие соответствующих единичных сигналов на выходах дешифраторов 6i,,..,65 непосредственно перед началом цикла сор- тировки, в результате которого все числа должны быть отсортированы в порядке возрастания, т.е. большее по величине число должно находиться в регистре 1s(c большим индексом), а наименьшее число - соответст- венно в регистре 1i (с меньшим индексом). С приходом каждого тактового сигнала Yo на вход 22 управления загрузкой устройства в предварительно обнуленном счетчике 56 блока 21 загрузки происходит увеличение на единицу его содержимого. Емкость счетчика 56 равна величине р 3, где р Iog2m. Информация, формируемая в каждом такте цикла загрузки Т3агр., является адресом, поступающим с информацией-

ных выходов счетчика 56 на входы Ао,...,А2 дешифраторов-демультиплексоров 571,...,57з блока 21 загрузки, по которому осуществляется запись в счетчики 5i,...,5s, и одновременно данными, поступающими после инвертирования на входы УУСГдешифра- торов-демультиплексоров 571,...,57з, которые являются в этом случае информационными входами, Таким образом, необходи- мая информация, записывается по соответствующему адресу, т.е. в соответствующий счетчик 5i,...,55.

После загрузки исходных данных начинается непосредственно цикл сортировки. В табл. 2 наглядно представлен порядок попарного сравнения чисел и их перемещения во время каждого такта цикла сортировки. Приведенный пример сортировки является примером сортировки транспозициями, в процессе которой числа сравниваются попарно, при этом сначала (2Ы)-й и 2к-й элементы последовательности m чисел, а затем 2к-й и (2к+1)-й элементы (где k: 1,2, .... К, К т/2), причем при сравнении в парах чисел происходит перестановка, в результате которой меньшие числа фиксируются на младших позициях (в младших регистрах), большие - на старших позициях (в старших регистрах)..

В предлагаемом устройстве вместо перестановок в сравниваемых парах чисел в каждом такте цикла сортировки Тс выполняется изменение номеров позиций чисел в соответствующих счетчиках 5i,:..,5s таким образом, что перестановке числа ai из младшего 1-го регистра 1i,...,l5 в старший (1+1)-й регистр 1i,...,1s соответствует увеличение на единицу содержимого 1-го счетчика 51,„,55, а перестановке числа a(i+i) из старшего (+1)-го регистра 1i,.,.,1s в младший i-й регистр Ti,...,l5 - уменьшение на единицу содержимого (1+1)-го счетчика 5i,...,5s (где I 1,2, „..т),

В первом такте цикла сортировки выполняется попарное сравнение чисел (ai-a2) и (). Поскольку присутствуют единичные сигналы gn; 922; дзз; 944; д55(табл. 1) на выходах соответствующих дешифраторов б1,...,б5. то это позволяет подать числа аь 32, аз, 34, as с выходов 8, 9. 10 блоков выбора кодов 3i,32, на входы блоков сравнения 2i, 22. где будет выполняться сравнение чисел, поступающих только с выходов 8 и 9 блоков выбора кодов 3i, 32, а именно чисел ai, 32 и аз, ад, т.к. в первом такте, как и во всех последующих нечетных тактах цикла сортировки, присутствует единичный сигнал YI на входе 17 устройства, который не разрешает попарное сравнение чисел (а2-а з) и (). В приведенном примере (табл. 2) на первом

такте цикла сортировки перестановка должна осуществляться в первой паре чисел, а это значит, что наличие единичного сигнала QI инициирует появление единичного сигнала qi на выходе 11 первого блока сравнения 2i, что приведет к формированию единичных сигналов qn и q22, поскольку присутствуют единичные значения на выходах дц и 922 дешифраторов 6i,..,,62. Через элементы ИЛИ 53t и 54i сигналы qn и цгг - поступят с выходов 13 и 14 первого блока 511 коммутатора 4 в виде единичных сигналов на суммирующий и вычитающий входы счетчиков 5i и 52 соответственно, что приведет к фиксации единичных сигналов 921 и gi2-на выходах 15 дешифраторов 6i,...,6s соответственно, т.е. к фактической перестановке чисел в первой из сравниваемых пар..

Во время второго такта должно выполняться попарное сравнение содержимого регистров 1-2-1.3.. 1.4-15, т.е. чисел (ar-аз), (а4 as) (табл. 2). Это достигается за счет того, что на входе 18 устройства во втором и во всех последующих четных тактах цикла сортировки присутствует единичный сигнал Y2, что позволяет сравнивать данные, поступающие с выходов 9, 10 блоков выбора кодов 3i, 3-2 на соответствующие входы блоков сравнения 2i, 22, в то время, как присутствуют единичные сигналы 921, 912. дзз, 944, 955 на выходах соответствующих дешифраторов 6i,...,6s. Таким образом, на входы элементов 48 сравнения поступят пары чисел (ai-аз) и (a4-as), что приведет, как следует из табл.2, к появлению единичного сигнала qn на выходе 12 блока сравнения 2i. Последний факт при наличии единичных сигналов 921 и дзз вызовет формирование единичных

Форму л а изрбретени я Устройство для сортировки чисел, содержащее m регистров, где m - количество сортируемых чисел, m счетчиков, К блокое сравнения, где К т/2, Х - ближайшее целое, не больше X, коммутатор и два элемента И, причем вход начальной установки устройства соединен с входом установки счетчиков в нулевое состояние, отличаю- щ е е с я тем, что, с целью повышения быстродействия, в него введены К блоков выбора кодов, m дешифраторов, блок загрузки номеров чисел в счетчики, триггер, четыре элемента ИЛИ и два элемента НЕ, коммутатор --содержит К блоков коммутации, содержащих каждый, кроме К-го, четыре группы элесигналов q2 и q33 которые через элементы ИЛИ 53i блока 511 и ИЛИ 54i блока 512 поступят с выходов 13 и 14 блоков 511 и 512 коммутатора 4 в виде сигналов qi4 и qs на

суммирующий и вычитающий входы счетчиков 5i и 5з соответственно, что приведет к фиксации единичных сигналов gsi и д 23 на выходах 15 дешифраторов 6i, 63 соответственно. .

Таким образом, фактически произведена перестановка чисел ai и аз в регистрах 12 и 1з. Аналогичным образом выполняется процесс сортировки в последующие нечетные и четные такты цикла сортировки.

Для наглядности в табл. 3 приведены результаты, зафиксированные на выходах 15 дешифраторов 6i,...,65 по окончании соответствующего такта цикла сортировки. По данным табл. 2 и 3 видно, что окончание процесса сортировки фиксируется на выходе элемента И 31 после того, как на четном (нечетном) и на следующем за ним нечетном (четном) тактах цикла сортировки не выполняется перестановка ни в одной

паре сравниваемых чисел. Например, на пятом такте цикла сортировки (табл. 2) не формируется блоками сравнения 2i, 22 ни один сигнал qi, q2 и, следовательно, триггер 30 устанавливается в единичное состояние, на

следующем, шестом такте вновь не формируется блоками сравнения 2i, 22 ни один сигнал qi 1 q2. что свидетельствует об отсутствии перестановок в сравниваемых парах чисел, а значит фиксируется единичным сигналом на выходе 32 устройства момент завершения сортировки исходных чисел, Следовательно, максимальное время сортировки чисел в данном устройстве будет равно (т+1) тактам цикла сортировки.

...:

ментов И и четыре элемента ИЛИ, К-й блок коммутации содержит четыре группы элементов И и 4 + 2mod2m. элементов ИЛИ, каждый блок сравнения содержит шесть элементов И. три элемента ИЛИ, два элемента НЕ, четыре элемента И-НЕ; и три триггера, каждый блок выбора кодов содержит три мультиплексора, тактовый вход устройства соединен с входом управления сдвигом регистров, выход старшего разряда j-ro регистра (J 1, 2, ..., т) соединен с j-ми информационными входами мультиплексоров блоков выбора кодов, выход SVro мультиплексора 1-го блока выбора кодов (Si 1, 2,3,1 1,2-.... К) соединен с первым входом Si-ro элемента И 1-го блока сравнения, $2-й

выход которого (За 1, 2) соединен с 1-м входом 52-го элемента ИЛИ и с первыми входами всех элементов И (252-1)-й и 252-й групп 1-го блока коммутации, входы г-го элемента ИЛИ (г 1, 2, 3, 4) 1-го блока коммутации подключены к выходам (21 - mod2r)-x элементов И (г+1) и Хг+3) групп всех блоков коммутации, при m - нечетном входы (52+4}-го элемента ИЛИ К-го блока коммутации подключены к выходам (21+1)-х элементов И Sa-й и (52+2)-й групп всех блоков коммутации, выход (252-1)-го и 232-го элементов ИЛИ 1-го блока коммутации соединены соответственно с суммирующим и вычитающим входами (21-2+$2)-го счетчика, выходы разрядов которого соединены с входами (2l-2+2S)-ro дешифратора, j-й выход Р-го дешифратора, где Р 2,4,..., 2К, соединен с j-м управляющим .входом второго мультиплексора P/2-ro блока выбора кодов, j-й выход q-ro дешифратора, где q 3, 5,..., 2К-1, соединен с J-ми управляющими входами первого и третьего мультиплексоров (q- 1)/2-го блока выбора кодов, j-й выход первого дешифратора соединен с j-м управляющим входом первого мультиплексора первого блока выбора кодов, при m - нечетном j-й выход m-ro дешифратора соединен с j-м управляющим входом третьего мультиплексора К-го блока выбора кодов, выходы j-ro дешифратора являются информационными выходами j-й группы устройства, j-й выход (2l-1+ r/2Q-ro дешифратора соединен с вторым входом J-ro элемента И г-й группы 1-го блока коммутации, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами третьего элемента ИЛИ и через первый и второй элементы НЕ - соответственно с первым и вторым входами первого элемента И, выход которого соединен с входом установки триггера в единичное состояние и;первым входом второго элемента И, , выход которого является выходом окончания работы устройства, выход третьего элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с входом установки триггера в нулевое состояние, выход которого соединен с вторым входом второго элемента И,.вход начальной установки устройства соединен с входами установки триггеров блоков сравнения в нулевое состояние и входом начальной установки блока загрузки номеров чисел в счетчики и вторым входом четвертого элемента ИЛИ, вход управления загрузкой устройства соединен с управляющим входом блока загрузки номеров чисел в счетчики, выходы которого соединены с установочными входами счетчиков, вход синхронизации устройства соединен с входами синхронизации устройства первого и второго триггеров всех блоков сравнения, в каждом блоке сравнения первый вход четвертого элемента И подключен к первому входу второго элемента И, в Хаждом блоке сравнения выходы (2$2-1)-го и 252-го элементов И соединены соответственно с первым и вторым входами 52-го элемента ИЛИ, выход которого соединён с первым входом (3-52)-го элемента И-НЕ и через 52-й элемент НЕ - с вторым входом $2-го элемента И-НЕ, выход которого соединен с первым входом (52+2)-го элемента И-НЕ, выход которого соединен с информационным входом 52-го триггера, инверсный выход которого соединен с третьим входом (3-52)-го элемента И-НЕ и с вторым входом (52+2)-го элемента И-НЕ, прямой выход второго триггера соединен с информационным входом третьего триггера, выход которого соединен с первыми входами пяГого и шестого элементов И, вход синхронизации третьего триггера подключен к выходу третьего элемента ИЛИ, 52-й управляющий вход устройства соединен с вторыми входами 52-го, (52+4)-го и (5-52)-го элементов И блоков сравнения и с 52-м входом третьего элемента ИЛИ блоков сравнения.

Таблица 1

Таблица 2

Таблица 3

ог 6i

81 IV

eefrcea