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

 

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

((9) (И) СОЮЗ СОВЕТСКИХ . СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s 6 06 Р 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

1 (21) 4735756/24 (22) 05.09,89 (46) 07.02.93. Бюл. М 5 (71) Винницкий политехнический институт (72) В.П.Кожемяко, Ю.Ф.Кутаев.

В, Б. Гайда, Т.Б.Мартынюк, В,Г.Степанов и И;В.Ищенко (56) Авторское свидетельство СССР

Гч . 1030797, кл. G 06 F 7/08, 1982. .Авторское свидетельство СССР . N 1267403, кл. G 06 F 7/06, 1985, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике. Цель изобРетения — повышение быстродействия. Устройство содержит регистры 1, блоки сравнения 2, блоки выбора кодов 3, коммутатор 4, счетчики 5, дешифраторы 6, блок загрузки

21, элементы ИЛИ 24, 25, 26, 29, элементы

НЕ 27. 28, триггер 30. Первоначально i-м числам присваиваются ранги, равные 1, ко.торые записываются в счетчики 5. Затем числа, ранги которых отличаются на единицу, попарно сравниваются друг с другом, и в результате сравнения меняются их ранги.

Сравнивание чисел производится до тех пор, пока ранги не перестают изменяться. 6 ил., 3 табл.

1793438

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

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

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

««vnov с открытым коллектором и входом начальной установки второго сдвигового регистра, выход первого разряда которого является выходом конца цикла устройства, а выход )-го разряда, где ) = 2, 3, ..., и, соединен с первым входом (j-1)-ro элемента И управления циклом с открытым коллектором, второй вход которого соединен с выходом )-го разряда первого сдвигового регистра, вторым входом 0-1)-го и первым входом j-ro элементов ИЛИ группы, второй вход и-ro элемента ИЛИ группы подключен к входу логического нуля устройства.

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

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

= 1...„m -1, где m — максимальное количество сортируемых чисел), выходы которой соединены с входами соответствующего

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

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

35 начности, соответствующих 1-й схеме сравнения, выходы схем неравнозначности

1793438

Наиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел, содержащее m регистров, (где m — количество сортируемых чисел), m элементов сравнения и m элементов 5

И, причем выходы I-го регистра (где I = 1, 2, .„, m) соединены с первой группой входов

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

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

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

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

modem) элементов ИЛИ, каждый блок сравнения содержит шесть элементов И, три элемента ИЛИ, два элемента НЕ, четыре элемента И-НЕ и три триггера, каждый блок выбора кодов содержит три мультиплексора, тактовый вход устройства соединен с входом управления сдвигом регистров, выход старшего разряда J-го регистра (j = 1, 2, ... m) соединен с )-ми информационными входами мультиплексоров блоков кодов, выход S>-го мультиплексора I-го блока выбора кодов (St = 1, 2, 3, I = 1, 2, ..., К) соединен с первым входом S>-го элемента И I-го блока сравнения, $2-й выход которого ($2 = 1, 2) соединен с I-м входом $2-го элемента ИЛИ и с первыми входами всех элементов И (2$ 1)-й и 2$g-й групп I-го блока коммутации, входы r-го элемента ИЛИ (r = 1, 2, 3, 4) 1-го блока коммутации подключены к выходам (2l - modzr)-x элементов И )(г+1)/2(-й и

)(3+3)/2(-й групп всех блоков коммутации, при m — нечетном входы (Sz+4)-го элемента

ИЛИ К-го блока коммутации подключены к выходам (2i+1)x элементов И $2-й и (Sz+2)-й групп всех блоков коммутации, выход (2$21)-го и 2$2-ro элементов ИЛИ I-ro блока коммутации соединены соответственно с суммирующим и вычитающим входами (2I2+Sz)-го счетчика, выходы разрядов которого соединены с входами (2l-2+ST)-го дешифратора, J-й выход р-го дешифратора, где р = 2, 4, ..., 2К, соединен с J-м управляю. щим входом второго мультиплексора р/2-ro блока выбора кодов, j-й выход q-го дешифратора, где q = 3, 5, ..., 2К-I, соединен с )-ми управляющими входами первого мультиплексора (о+1)/2-го блока выбора кодов и третьего мультиплексора (q-1)/2-го блока выбора кодов, J"й выход первого дешифраторэ соединен с j-м управляющим входом первого мультиплексора первого блока выбора кодов, при m — нечетно,.1 J-й выход m-ro дешифратора соединен c J-м управляющим входом третьего мультиплексора К-го блока выбора кодов, выходы J-го дешифратора являются информационными выходами j-A . группы устройства, )-й выход (2И+)г/2()-го дешифраторэ соединен с вторым входом jro элемента И г-й группы I-го блока коммутации, выходы первого и второго элементов

WIN соединены соответственно с первым и вторым входами третьего элемента ИЛИ, и через первый и второй элементы НŠ— соответственно с первым и вторым входами первого элемента И, выход которого соединен с входом установки триггера в единичное состояние и первым входом второго элемента И, выход которого является выходом окончания работы устройства, выход третьего элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с входом установки триггера в нулевое состояние, выход которого

1793438

15

30

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

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

Устройство для сортировки (фиг. 1) содержит m регистров 11, 1m К блоков сравнения 2>...Д2к (где К = )m/2(— целая часть числа m/2, К блоков выбора кодов 3;,...,Зк, коммутатор 4, m счетчиков 51,".,5m, m дешифраторов 6)„...6П1, причем выход каждого регистра 1i...„1 соединен с входом 7 блоков выбора кодов 31„...3к, а выходы 8, 9, 10 каждого блока выбора кодов 31,...,3к соединены входами соответствующего блока сравнения 2>,...,2к, выходы 11 и 12 которых соединены с соответствующими входами коммутатора 4. Выходы 13 и 14 коммутатора

4 соединены попарно с суммирующим и вычитающим входами счетчиков 51,...,5, информациойные выходы которых подключены к входам дешифраторов

61,...,6 . Выходы 15 дешифраторов 61,...,6 и соединены соответственно с входами блоков выбора кодов 31,...,3y, и коммутатора 4, а также являются группой выходов устройства. Тактовый вход 16 устройства подключен к входам управленйя сдвигом регистров

11,...,1m, управляющие входы 17, 18, вход начальной установки 19 и вход синхронизации 20 устройства соединены с соответствующими входами блоков сравнения 2>,...,2к, кроме того, вход начальной установки 19 устройства подключен также к входам установки в нулевое состояние счетчиков

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

23 — к установочным входам счетчиков

51,...,5 . Выходы 11 и 12 блоков сравнения

21,...,2к соединены с входами элементов

ИЛИ 24 и 25 соответственно; выходы которых подключены к входам элемента ИЛИ 26 и через элементы НЕ 27,28 к входам элемента ИЛИ 29, выход которого соединен с входом установки в единичное состояние .триггера 30 и первым входом элемента И 31, второй вход которого подключен к прямому выходу триггера 30, а выход является выходом 32 окончания работы устройства. Выход элемента ИЛИ 26 соединен с первым вхо- . дом элемента ИЛИ 33, второй вход которого подключен к входу начальной установки 19 устройства, а выход — к входу установки в нулевое состояние триггера 30.

На фиг. 2 представлена функциональная схема двух блоков выбора кодов 3 и

3(k+<) (где k = 1, 2, ..., К, К = )m/20 каждый из которых содержит три мультиплексора 34, 35, 36, выходы которых 37, 38, 39 являются выходами 8, 9, 10 каждого блока выбора кодов 31,...,3к соответственно, .причем i-e входы мультиплексоров 34, 35, 36 соединены с выходом старшего разряда 1-го регистра 1,...,1„(где 1= 1, 2, ..., m), j-й выход 2k-ro дешифратора 6i,...,6m, k = 1, 2, .„, К, соединен с j-м управляющим входом мультиплексора 35 k-ro блока выбора кодов 31,...,3к- j-й выход (2k+1)-го дешифратора 61,...6m, соединен с j-м управляющим входом мультиплексора 34 2k-го блока выбора кодов 31,...3y, и мультиплексора 35 k-ro блока выбора кодов

31,...3к. )-й выход первого дешифратора 61 соединен с j-м управляющим входом муль1793438

10 типлексора 34 первого блока выбора кодов

3>. При m — нечетном j-й выход m-ro дешифратора 6 соединен с j-м управляющим входом мультиплексора 36 К-ro блока выбора кодов 3к. 5

На фиг. 2 также представлена функциональная схема двух блоков сравнения 2, 2(p+>) (где k = 1, 2, ..., К, К =)m/2P, каждый из которых содержит элементы И 40, 41, 42, 43, 44, 45, элементы ИЛИ 46, 47 и элемент 10

48 сравнения, причем первые входы элементов И 40, 41 и 42 блока сравнения 2 подключены к выходам 8, 9, 10 блока выбора кодов 3к, первый вход элемента И 43 также подключен к выходу 9 блока выбора кодов 15

3 . Вторые входы элементов И 40, 43 и 44 блоков сравнения 2i.„,.2к соединены с управляющим входом 17 устройства, а вторые входы элементов И 41, 42 и 45 блоков сравнения 21,.Д,2к соединены с управляющим 20 входом 18 устройства, выходы элементов И

40, 41 и элементов И 42, 43 подключены к входам элементов ИЛИ 46, 47 соответственно, выходы которых соединены с информационными входами 49 и 50 элемента 48 25 сравнения соответственно. Входы установки в нулевое состояние и синхронизации элемента 48 сравнения блоков сравнения

2>,...,2к подключены к входам начальной установки 19 и синхронизации 20 устройства 30 соответственно, а его выход соединен с пе рвыми входами элементов И 44 и 45, выходы которых являются выходами 11 и 12 блоков сравнения 21, 2к соответственно, Коммутатор 4 содержит К блоков комму- 35 тации 511;...,51к(где К =)m/2(, функциональная схема двух из которых 51 и 51i>+>) представлена на фиг. 3 (где k = 1, 2, ..., K).

Каждый блок 51>,...,51к содержит четыре группы 52,...,524 элементов И и элементы 40.

ИЛИ 53), 53г, ИЛИ 54, 54г. В случае. когда

m — нечетное число, блок 51к содержит дополнительно элементы ИЛИ 53з, 54з. Каждая группа 521,...,524 элементов И блоков

511,...,51к содержит m элементов И 55, при- 45 чем первые входы элементов И 55 групп 52> и 522 элементов И блока 51k соединены с выходом 11 блока сравнения 2k, а первые входы элементов И 55 групп 52з и 524 элементов И вЂ” с выходом 12 блока сравнения 50

2к. Вторые входы i-ro элемента И 55 групп

52> элементов И блока 51р подключены к (2k-1)-му выходу i-ro дешифратора 6>,...,6m (где! = 1, 2, ..., m), вторые входы i-го элемента

И 55 групп 52 и 52з элементов И вЂ” к 2k-му 55 выходу i-ro дешифратора 6>,...,6,, вторые входы i-ro элемента И 55 группы 524 элементов И вЂ” к (2k+1)-му выходу i-ro дешифратора

61„.„6m. Выходы элементов И 55 групп 521 и

52з элементов И блоков 51i,...,51K обьединены и подключены таким образом, что (m-1) входы элемента ИЛИ 53> блока 51р подключены к выходам (2k-1)-х элементов И 55 групп 521 и 52з элементов И блоков

51, „51к, (m-1) входы элемента ИЛИ 53 — к выходам 2k-х элементов И 55 групп 52i и 52з элементов И блоков 511,...,51к. Аналогично, выходы элементов И 55 групп 522 и 524 элементов И блоков 511,...,51к обьединены и подключены таким образом, что (m-1) входы элемента ИЛИ 54 блока 51у подключены к выходам (2k-1)-х элементов И 55 групп 52 и

52 элементов И блоков 51>, .„51к, (m-1) входы элемента ИЛИ 542 — к выходам 2k-х элементов И 55 групп 52 и 52 элементов И блоков 511....,51к. Выходы элементов ИЛИ

53 и 53г блока 51k подключены к суммирующим входам (2k-i)-го и 2k-го счетчиков

5>,...,5m соответственно, а выходы элементов ИЛИ 54> и 54 — к вычитающим входам (2k-1)-го и 2k-ro счетчиков 51,...,5 соответственно.

Блок 21 загрузки номеров чисел в счетчики (фиг. 4) содержит счетчик 56 и р демультиплексоров 571,.Д57р(где р =!оцуп ), причем вход сброса и суммирующий вход счетчика

56 подключены к входам начальной установки 19 и управления загрузкой 22 устройства соответственно, р информационных выходов — к соответствующим адресным входам демультиплексоров 57,...,57p, кроме того, j-й информационйый выход счетчика 56 соединен с информационным входом WOj-го демультиплексоров 57>,. „57р (где j = 1, 2, ..., р), à i-å выходы демультиплексоров

571,...57р являются выходами 23 блока 21 загрузки и соединены с соответствующими установочными входами i-го счетчика

5 т....,5m (где i = =1, 2, ..., m).

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

58 и 59 соединены с выходами элементов

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

1793438

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

Устройство работает следующим обра- "0

-эом.

В начале работы по управляющему сигналу на входе 19 устройства происходит установка в нулевое .состояние счетчиков

51,...,5П, счетчика 56 блока 21 загрузки и 15 триггеров 58, 59, 60 элемента 48 сравнения. а также триггера 30 устройства, в результате чего на выходе 32 устройства присутствует сигнал логического нуля. Одновременно с записью в регистры 1>,...,1> исходных чисел 20 (цепи начальной установки и занесения чисел не приводятся) в счетчиках 51,. 5m формируется с помощью блока 21 загрузки необходимая информация, т.е. фиксируется порядковый номер соответствующего реги- 25 стра 11,....1п. Затем начинается непосредст.венно процесс сортировки, в первом такте которого выполняется сравнение данных, находящихся в (2k- l)-м и 2k-м регистрах

11."„1m, где k = 1, 2, ..., K, К = )m/2(, под 30 действием управляющего сигнала У1 на входе 17 устройства. В результате для большего данного, находящегося в (2k-1)-м регистре 11, 1> происходит увеличение на единицу содержимого в соответствующем 35 (2k-1)-м счетчике 51,...,5m. Одновременно происходит уменьшение на единицу содержимого 2k-го счетчика 51...,5m, соответствУющего меньшему данному, находящемуся в

2k-м регистре 11,...,1П1. В случае, если боль- 40 шее число находится в 2k-м регистре

11, 1m, изменений соДеРжимого в соответствующих (2k-1)-.м и 2k-м счетчиках 51,...,5п не происходит.

Во втором такте под действием управляющегого сигнала У2 на входе 18 устройства сравниваются- пары чисел в 2k-м и (2k+1)-м регистрах 11,..., lm аналогично процессу, описанному для первого такта в 50 (2k-1)-м и 2k-м регистрах 11,...,1 соответственно. Далее выполняются действия, аналогичные выполняемым в первом и во втором тактах цикла сортировки до тех пор, пока не будет присвоен старший по- 55 рядковый номер большему из исходных чи-. сел, а меньший порядковый номер— меньшему числу, что фиксируется появлением единичного сигнала на выходе 32 окончания работы устройства.

В процессе сортировки в каждом иэ блоков выбора кодов 31,...,3к (фиг. 2) сигналы

l(2k-1), l2k, l(2k+1) на выходах 37, 38, 39 формируются следующим образом:

=u а; ° e = 0 а.

Ф-»l ег,— „ 3 (2k-»li (2Ц; (,— „ 9(2Ц; (21 +»1 ;е » an) 3 (й» +») > где а1 — значение (содержимое) 1-го регистра

1 i,..., 1 m, l(2k-1)l, l(2k)i, l(2k+1)i — значение (2k-1)-го, 2k-го (2k+1)-го разрядов l-ro дешифратора

61„.„6m.

Последовательность выполнения нечетного и четного тактов цикла сортировки инициируется последовательностью появления сигналов У1, У2 на входах 17 и 18 устройства.

С помощью элемента 48 сравнения определяется случай, когда первое из пары сравниваем йх чисел больше второго. В результате, в случае выполнения этого соотношения, в нечетном такте появляется единичный сигнал qk на выходе 11 соответствующего k-го блока сравнения 21,...,2к, в четном такте— единичный сигнал Qk на выходе 12 соответ-! ствующего k-го блока сравнения 21,...,2к (где

k=1,2,.„, К)(фиг. 2).

На выходах 13 и 14 блока 51к коммутатора 4 (фиг. 3) формируются сигналы як-1) и Q(2k-1) Q(2k) и Q(2k) сООтветственнО, которые вызывают увеличение и уменьшение на единицу содержимого в (2k-1)-м и 2k-м счетЧИКаХ 51,...,5m СООтВЕтСтВЕННО, дЛя КОтарЫХ характерны следующие соотношения:

1(2М-tl ° (» (((1с-»1 ) 1 Ы -ц е(,, (Ы-П >

0 ц

Ъ(21=;,(,,,Р (Ы l(ail;ckem3%1(qkl где

)1(Вс-Q 3k 5(2a-<), (Lkl (2Ч

)1(21с-11 $k (О(-!); Ч (ац tk Л 1 (Ц

skQkllY qk ОкпУ,,..

Формирование соответствующих порядковых номеров в счетчиках 51,...,5m выполняется следующим образом (фиг. 4). С приходом каждого тактового импульса Уо по входу 22 управления загрузкой устройства s предварительно обнуленном счетчике

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

1793438

Ao,...,A(p-1) демультиплексоров 571,...,57p, по которому осуществляется запись в счетчики

51,...,5п1, и одновременно данными, поступающими на информационный вход WO соответствующего демультиплексора 57>,...,57р.

Таким образом, в i-й такт цикла загрузки число, равное величине "i", записывается по

i-му адресу, т.е. в i-й счетчик 51....,5, (где i =

1,2,...,m)..

Элемент 48 сравнения (фиг. 6) предназначен для выполнения анализа двоичных чисел, начиная со старших разрядов. В начальном состоянии триггеры 58, 59, 60 обнулены. При сравнении значения одноименных разрядов величин a(2k-1) и а(г )

I в нечетных тактах и величин а(21) и a(2k+1) в четных тактах цикла сортировки последовательно и синхронно подаются на соответствующие входы 49 и 50 элемента 48 сравнения. С приходом каждого тактирую. щего сигнала У4 на вход 20 синхронизации устройства триггеры 58 и 59 переходит в новое состояние. Триггеры 58 и 59, элементы И-НЕ 61, 62, 63, 64 и элементы НЕ 65, 66 составляют схему ячейки, используемой при сравнении величин.

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

Рассмотрим потактную работу устройства при сортировке чисел, например: а! = 9, a2 = 1, аз = 3, а4 = 5, ag = 7.

В табл. 1 показано исходное состояние регистров 1>,...,15 и счетчиков 51....,55, а также наличие соответствующих единичных сигналов на выходах дешифраторов 6!„...65 непосредственно перед началом цикла сортировки, в результате которого все числа должны быть отсортированы в порядке возрастания, т.е, большее по величине число должно находиться в регистре 15(с большим индексом), а наименьшее число- соответственно в регистре 1! (с меньшим индексом).

С приходом каждого тактового сигнала

Уо на вход 22 управления загрузкой устройства в предварительно обнуленном счетчйке 56 блока 21 загрузки происходит увеличение на единицу его содержимого.

Емкость счетчика 56 равна величине р = 3, где р = iog2m. Информация, формируемая в каждом такте цикла загрузки Taarp., является адресом, поступающим с инфармационных выходов счетчика 56 на входы Аа,...,А2 дешифраторов-демул ьти плексо ров

57>,...,57з блока 21 загрузки, по которому осуществляется запись в счетчики 5),...,55, и одновременно данными, поступающими после инвертирования на входы Й О дешифраторов-демультиплексоров 571„.„57з, которые являются в этом случае информационными входами. Таким образом, необходимая информация записывается по соответствующему адресу, т.е. в соответст,вующий счетчик 51,...,5 .

После загрузки исходных данных начинается непосредственно цикл сортировки, В табл, 2 наглядно представлен порядок попарного сравнения чисел и их перемещения во время каждого такта цикла сортировки.

Приведенный пример сортировки является примером сортировки транспозициями, в процессе которой:числа сравниваются попарно; при этом сначала (2k-1)-й и 2k-й элементы последовательности m чисел, а затем

2k-й и (2k+1)-й элементы (где k = 1, 2, „„К, К

=)m/2(), причем при сравнении в парах чи25 сел происходит перестановка, в результате которой меньшие числа фиксируются на младших позициях (в младших регистрах), большие — на старших позициях (в старших регистрах).

В предлагаемом устройстве вместо перестановок в сравниваемых парах чисел в каждом такте цикла сортировки Тс выполняется изменение номеров позиций чисел в соответствующих счетчиках 5!,;,55 таким

35 образом, что перестановке числа а! из младшего i-го регистра 11,.„,1в в старший (i+1)-й регистр 1!„„,1в соответствует увеличение на единицу содержимого )-го счетчика

5!".,55 а перестановке числа a(1+1) из стар40 шего (!+1)-го регистра 1>,...,15 в младший i-й регистр 11, 1s — уменьшение на единицу .содержимого (!+1)-го счетчика 5>,...,55 (где

=1,2, ..., m), В первом такте цикла сортировки вы45 полняется попарное сравнение чисел (а1-а2). и (аз — а4). Поскольку присутствуют единичные сигналы 9! ; 922, 9зз, g44, 955(табл, 1) на выходах соответствующих дешифратаров

61,...,65, то это позволяет подать числа à1. а2

50 аз, а4. аь с выходов 8, 9. 10 блоков выбора кодов 3>,32, на входы блоков сравнения 2>, 22, где будет выполняться сравнение чисел, поступающих только с выходов 8 и 9 блоков выбора кодов 31, 32, а именно чисел а1, а2 и аз. а4, т.к, в первом такте, как и Во всех последующих нечетных тактах цикла сортировки, и рисутствует единичн ый сигнал У1 на входе 17 устройства, который не разрешает попарное сравнение чисел (а — аз) и (a4 — а5).

В приведенном примере (табл, 2) на первом

1793438

20

25 такте цикла сортировки перестановка должна осуществляться в первой паре чисел, а это значит, что наличие единичного сигнала

Q1 инициирует появление единичного сиг. нала q1 на выходе 11 первого блока сравнения 21, что приведет к формированию единичных сигналов q11 и q22, поскольку присутствуют единичные значения на выходах g11 и 922 дешифраторов 61...„62. через элементы ИЛИ 531 и 541 сигналы q11+ и q22

-поступят с выходов 13 и 14 первого блока

511 коммутатора 4 в виде единичных сигна+. лов q1 и q2 на суммирующий и вычитаЮщий входы счетчиков 51 и 52 соответственно, что приведет к фиксации единичных сигналов

g21 и 912 -на выходах 15 дешифраторов

61,...,65 соответственно, т.е. к фактической перестановке чисел в первой из сравниваемых пар. . Во время второго такта должно выполняться попарное сравнение содержимого регистров 12 — 13. 14 — 15, т.е, чисел (а1 — аз), (а4а )(табл. 2). Это достигается за счеттого, что на входе 18 устройства во втором и во всех последующих четных тактах цикла сортировки присутствует единичный сигнал У2, что позволяет сравнивать данные, поступающие с выходов 9, 10 блоков выбора кодов

31, 32 на соответствующие входы блоков сравнения 21 22, в то время, как присутствуют единичные сигналы g21, 912, 933, 944, 955 на выходах соответствующих дешифрато ров 61,...,65. Таким образом, на входы элементов 48 сравнения поступят пары чисел (а1 — аз) и (а4-а5), что приведет, как следует из табл. 2, к появлению единичного сигнала q11 на выходе 12 блока сравнения 21. Последний факт при наличии единичных сигналов

g21 и 9зз вызовет формирование единичных

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

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

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

ИЛИ 531 блока 511 и ИЛИ 541 блока 512 поступят с выходов 13 и 14 блоков 511 и 512 коммутатора 4 в виде сигналов q1 и цз на суммирующий и вычитающий входы счетчиков 51 и 5з соответственно, что приведет к фиксации единичных сигналов 9з1 и 92з на выходах 15 дешифраторов 61, бз соответствен но..

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

15 Для наглядности в табл. 3 приведены результаты, зафиксированные на выходах

15 дешифраторов 61,...,65 по окончании соответствующего такта цикла сортировки.

По данным табл. 2 и 3 видно, что окончание процесса сортировки фиксируется на выходе элемента И 31 после того, как на четном (нечетном) и на следующем за ним нечетном (четном) тактах цикла сортировки не выполняется перестановка ни в одной йаре сравниваемых чисел. Например, на пятом такте цикла сортировки (табл. 2) не формируется блоками сравнения 21, 22 ни один сигнал q1, ц2 и, следовательно, триггер 30 устанавливается в единичное состояние, на

30 следующем, шестом такте вновь не формируется блоками сравнения 21, 22 ни один сигнал q1 q2, что свидетельствует об отсутl.

° ствии перестановок в сравниваемых парах чисел, а значит фиксируется единичным сиг35 налом на выходе 32 устройства момент завершения сортировки исходных чисел, Следовательно, максимальное время сортировки чисел в данном устройстве будет равно (гп+1) тактам цикла сортировки, 40 ментов И и четыре элемента ИЛИ, К-й блок коммутации содержит четыре группы элементов И и 4 + 2mod2m элементов ИЛИ, каждый блок сравнения содержит шесть элементов И, три элемента ИЛИ; два элемента НЕ, четыре элемента И-Н(-, и три триггера, каждый блок выбора кодов содержит три мультиплексора, тактовый вход устройства соединен с входом управления сдвигом регистров, выход старшего разряда J-ro регистра 0 = 1, 2, . „m) соединен с f-ми информационными входами мультиплексоров блоков выбора кодов, выход S1-го мультиплексора (-го блока выбора кодов (S1 = 1.

2, 3; (= 1, 2- ..., К) соединен с первым входом

31-го элемента И I-ro блока сравнения, S2-й

1793438 выход которого (Sz = 1, 2) соединен с I-м входом Sz-го элемента ИЛИ и с первыми входами всех элементов И (2S2-1)-й и 2S2-й групп I-ro блока коммутации, входы г-го эле-. мента ИЛИ (г = 1, 2, 3, 4) 1-го блока коммутации подключены к выходам (21 - modzr)-õ элементов И )(r+1)/2(-й и )(г+3)/2(-й групп всех блоков коммутации, при m — нечетном входы (Sz+4)-го элемента ИЛИ К-го блока коммутации подключены к выходам (21+1)-х элементов И Sz-й и (32+2)-й групп всех блоков коммутации, выход (2S2-1)-го и 2Sz-го элементов ИЛИ I-го блока коммутации соединены соответственно с суммирующим и вычитающим входами (21-2+Sr)-го счетчика, выходы разрядов которого соединены с входами (21-2+2S)-го дешифратора, J-й выход

P-го дешифратора, где P = 2, 4...„2К, соединен с J-м управляющим входом второго мультиплексора Р/2-ro блока выбора кодов, j-й выход q-го дешифратора, где q = 3. 5,;...

2К-1, соединен с J-ми управляющими входами первого и третьего мультиплексоров (с11)/2-го блока выбора кодов, J-й выход первого дешифратора соединен с J-м управляющим входом первого мультиплексора первого блока выбора кодов, при m — нечетном /-й выход m-ro дешифратора соединен с /-м управляющим входом третьего мультйплексора К-ro блока выбора кодов, выходы

/-го дешифратора являются информационными выходами j-й группы устройства, J-й выход (21-1+)r/2()-го дешифратора соединен с вторым входом J-го элемента И г-й группы

1-го блока коммутации, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами третьего элемента ИЛИ и через первый и второй элементы НŠ— соответственно с первым и вторым входами первого элемента И, выход которого соединен с входом установки триггера в единичное состояние и первым входом второго элемента И,, выход которого является выходом окончания работы устройства, выход третьего элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с входом установки триггера в нулевое состояние, выход которого соединен с вторым входом второго элемента И,.вход начальной установки устройства соединен с входами установки триггеров блоков сравнения в нулевое состояние и входом начальной установки блока загрузки номеров чисел в счетчики и вторым входом четвертого элемента ИЛИ, вход управления загрузкой устройства соединен с управляющим входом блока загрузки номеров чисел в счетчики, выходы которого соединены с установочными входами счетчиков, вход синхронизации устройства соединен с входами синхронизации устройства первого и второго триггеров всех блоков сравнения, в каждом блоке сравнения первый вход четвертого элемента И подключен к первому входу второго элемента И. s каждом блоке сравнения выходы (2Sz-1)-го и 232-го элементов И соединены соответственно с первым и вторым входами Sz-го элемента ИЛИ, выход котороro соединен с первым входом (3-Sz)-ro злемента И-НЕ и через Sp-й элемент НŠ— с вторым входом Sz-ro элемента И-НЕ, выход которого соединен с первым входом (32+2)-го элемента И-НЕ, выход которого соединен с информационным входом Sz-го триггера, инверсный выход которого соединен с третьим входом (3-Sp)-ro элемента

И-НЕ и с вторым входом (Sr+2)-ro элемента

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

S2-го, (S2+4)-го и (5-$2)-го элементов И блоков сравнения и с Sz-м входом третьего элемента ИЛИ блоков сравнения

1793438

Таблица 1

Таблица 2

GOOGLY

5 5 . 5 9 7

7 7 7 7 9

Регистры

Такты

Таблица 3

1-й 2-й 3-й 4-й 5-й 6-й

1793438

15 7

Фиг.2.

1793438

1 ° j(2k. Ai

31 о —— (:ЬФ

$(24-, ф - 1

@2 (;

3(гЫ

И 2

3и > (2с1

)/gal) (Т {2 Pw

2 а, фК

3 и il . г

Я (с фгй.ii !

0,А i, Ъ

of(2k++1)Tn ch

Я2 1 2 !

Л ;

1 4)

) ( с,,-. ср.

1 б-{ ), L::/ 5?yt

I, Г1 с -

1793438

19

2Х

Фиг.4

Фиг,5 гс

Фиг.6

Составитель Т. мартынюк

Редактор С. Кулакова Техред M.Moðãåíòàë Корректор М. Петрова

Заказ 505 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101