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

(5 ТЕ ВИДЕТЕЛЬСТВ К АВТОРСКОМ ОСУДАРСТВЕННОЕ ПАТЕНТНОЕЕДОМСТВО СССРОСПАТЕНТ СССР)(71) Винницкий политехнический институт(56) Авторское свидетельство СССРМ 1030797, кл. 0 06 Р 7/08, 1982.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ(57) Изобретение относится к автоматикеи вычислительной технике. Цель изобретения - повышение быстродействия. Устройство содержит регистры 1, блоки сравнения 2, блоки выбора кодов 3, коммутатор 4, счетчики 5, дешифраторы 6, блок загрузки 21, элементы ИЛИ 24, 25, 26, 29, элементы НЕ 27, 28, триггер 30. Первоначально 1-м числам присваиваются ранги, равные 1, ко.торые записываются в счетчики 5. Затем числа, ранги которых отличаются на единицу, попарно сравниваются друг с другом, и в результате сравнения меняются их ранги. Сравнивание чисел производится до тех пор, пока ранги не перестают изменяться. 6 ил., 3 табл.Таблица 1 гистры акты: 1793438 Та бл Их содержимо и 20 6.4 ИФиг 5 оСоставитель Т. мартынюк Редактор С. Кулакова Техред М.Моргентал Корректор М, Петро аказ 505 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., 4/5Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах обработки информации при реализации технических средств цифровых вычислительных машин и дискретной автоматики.Известно устройство для сортировки чисел, содержащее и регистров, где и - число сортируемых чисел, схему сравнения, элемент И, узел синхронизации, элемент И . управления переписью, элемент И управления циклом, группу элементов ИЛИ, коммутатор чисел, коммутатор циклов, причем управляющий вход устройства соединен с входом узла синхронизации, первый выход которого соединен с выходом управления режимом схемы сравнения, выход которой соединен с первым входом элемента И, кроме того, регистры выполнены с третьим состоянием, а элементы И управления циклом с открытым коллектором, коммутаторы чисел и циклов выполнены соответственно на первом и втором Сдвиговых регистрах, управляющий вход устройства является его тактовым входом, узел синхронизации выполнен на О-триггере, синхровход которого .является входом узла синхронизации,. прямой выход - выходом узла синхронизации, вход управления режимом схемы сравнения является входом задания режима "Больше", входзадания режима "Меньше" схемы сравнения соединен с инверсным выходом О- триггера и его О-входом, первый вход первого элемента ИЛИ группы подключен к входу логического нуля устройства, выходы одноименных разрядов всех нечетных регистров с третьим состоянием подключены к соответствующим входам первой группы схемы сравнения и соответствующим информационным входам всех четных регистров с третьим состоянием, одноименные выходы разрядов которых подключены к соответствующим входам второй группы схемы сравнения и соответствующим информационным входам всех нечетных регистров с третьим состоянием, вход разрешения считывания 1-го.регистра с третьим состоянием, где 1 = 1, 2, , и, соединен с выходом 1-го элемента ИЛИ группы и первым входом 1-го элемента И управления переписью, выход которого соединен с синхровходом 1-го регистра с третьим состоянием, вторые входы всех элементов И уп.равления переписью подключены к выходу элемента И, второй вход которого соединен с тактовым входом устройства и синхровходом первого сдвигового регистра, вход начальной установки которого соединен с выходами всех элементов И управления пилом с открытым коллектором и входомначальной установки второго сдвигового регистра, выход первого разряда которого является выходом конца цикла устройства, а выход 1-го разряда, где ) = 2, 3, , и, соединен с первым входом О)-го элемента И управления циклом с открытым коллектором, второй вход которого соединен с выходом )-го разряда первого сдвигового регистра, вторым входом Д)-го и первым 10 входом )-го элементов ИЛИ группы, второй вход и-го элемента ИЛИ группы подключен к входу логического нуля устройства,Недостатком известного устройства яв ляется организация последовательной сор 15 тировки и чисел, а также необходимость перезаписи информации между двумя регистрами в процессе сравнения пэры чисел,Известно устройство длясортировки чисел, содержащее щ регистров, гпсхем сравнения, многовходовый элемент ИЛИ,20 элемент И, переключатели, элементы неравнозначности, элементы ИЛИ, причем выходы 1-го и (1+1)-го регистров поразрядно соединены с входами 1-й схемы сравнения (1 = 1 т -1, где п - максимальное количество сортируемых чисел), выходы которой соединены с входами соответствующего 25 управления обменом соединены с первыми входами соответствующих элементов И, выходы 1-го и (1+1)-го регистров поразрядно соединены с входами элементов неравноз 35. начности, соответствующих 1-й схеме сравнения, выходы схем неравнозначности соединены с первыми входами соответствующих элементов И, вторые входы которых соединены с выходом соответствующего элемента И, вторые входы элементов И соединены с выходами соответствующих пере 40 ключателей, выходы элементов И, соответствующих 1-й схеме сравнения, соединены с первыми входами элементов ИЛИ, соответствующих 1-му регистру, и с вторыми входами элементов ИЛИ, соответствующих (1+1)-му регистру, выходы элементов ИЛИ поразрядно соединены с входами соответствующих регистров, выход многовходового 50 элемента ИЛИ соединен с выходом сигнализации о неупорядоченном расположениичисел в регистрах устройства,В известном устройстве сортировка чисел выполняется одновременно с перезаписью информации в регистрах в порядке убывания или возрастания. Таким образом, недостатком его является невозможность выполнения сортировки без перестановки информации в регистрах,переключателя, выходы переключателей соединены с соответствующими входами мно говходового элемента ИЛИ, входыНаиболее близким по технической сущности к предлагаемому является устройство для сортировки чисел, содержащее в регистров, (где гп - количество сортируемых чисел), п элементов сравнения и а элементов 5 И, причем выходы -го регистра (где= 1, 2, ., гп) соединены с первой группой входов -го элемента сравнения, кроме того, устройство содержит в счетчиков и коммутатор, первая группа информационных 10 входов которого является группой информационных входов устройства, вход задания режима устройства соединен с управляющим входом коммутатора, выходы которого соединены с установочными входами пер вого регистра и вторыми группами входов всех элементов сравнения, выходы )-го регистра (где ) = 1, 2 т) соединены с установочными входами О+1)-го регистра, выходы в -го регистра являются информа ционными выходами устройства и соединены с второй группой информационных входов коммутатора, выход -го элемента сравнения соединен с первым входом -го элемента И, выход которого соединен со 25 счетным входом -го счетчика, выходы разрядов 1-го счетчика соединены с установочными входами О+1)-го счетчика, выходы разрядов гп-го счетчика являются адресными выходами устройства и соединены с ус тановочными входами первого счетчика, первый тактовый вход устройства соединен с входами разрешения записи всех регистров и счетчиков, второй тактовый вход устройства соединен с вторыми входами всех 35 элементов И.Недостатком известного устройства является незначительное быстродействие.Целью изобретения является повышение быстродействия устройства. 40Поставленная цель достигается тем, что в устройство для сортировки чисел, содержащее в регистров, где гп - количество сортируемых чисел, в счетчиков, К блоков сравнения, где К = )гп/2, )Х - ближайшее 45 целое, не больше Х, коммутатор и два элемента И, причем вход начальной установки устройства соединен с входом установки счетчиков в нулевое состояние, введены К блоков выбора кодов, гп дешифраторов, 50 блок загрузки номеров чисел в счетчики, триггер, четыре элемента ИЛИ и два элемента НЕ, коммутатор содержит К блоков коммутации, содержащих каждый, кроме К- го, четыре группы элементов И и четыре 55 элемента ИЛИ, К-й блок коммутации содержит четыре группы элементов И и (4+2 вобрав) элементов ИЛИ, каждый блок сравнения содержит шесть элементов И, три элемента ИЛИ, два элемента НЕ, четыре элемента И-НЕ и три триггера, каждый блок выбора кодов содержит три мультиплексора, тактовый вход устройства соединен с входом управления сдвигом регистров, выход старшего разряда )-го регистра О = 1, 2,в) соединен с )-ми информационными входами мультиплексоров блоков кодов, выход Я 1-го мультиплексора -го блока выбора кодов (Я = 1, 2, 3,= 1, 2, , К) соединен с первым входом Я 1-го элемента И -го блока сравнения, Я 2-й выход которого (Я 2 = 1, 2) соединен с -м входом Яр-го элемента ИЛИ и с первыми входами всех элементов И 2 Я 2- 1)-й и 2 Я 2-й групп -го блока коммутации, входы г-го элемента ИЛИ г = 1, 2, 3, 4) -го блока коммутации подключены к выходам (2 - восгг)-х элементов И )(г+1)/2-й и )(3+3)/2-й групп всех блоков коммутации, при а - нечетном входы (Я 2+4)-го элемента ИЛИ К-го блока коммутации подключены к выходам (2+1)-х элементов И Я 2-й и Яр+2)-й групп всех блоков коммутации, выход (2 Я 2- 1)-го и 2 Я 2-го элементов ИЛИ (-го блока коммутации соединены соответственно с суммирующим и вычитающим входами (2- 2+Яг)-го счетчика, выходы разрядов которого соединены с входами (2-2+Яр)-го дешифратора, )-й выход р-го дешифратора, где р = 2, 4, , 2 К, соединен с )-м управляющим входом второго мультиплексора р/2-го блока выбора кодов, )-й выход ц-го дешифратора, где р = 3, 5, , 2 К, соединен с)-ми управляющими входами первого мультиплексора ц+1)/2-го блока выбора кодов и третьего мультиплексора с)/2-го блока выбора кодов, )-й выход первого дешифратора соединен с )-м управляющим входом первого мультиплексора первого блока выбора кодов, при щ - нечетнол -й выход гп-го дешифратора соединен с)-м управляющим входом третьего мультиплексора К-го блока выбора кодов, выходы)-го дешифратора являются информационными выходами 1-й . группы устройства, -й выход (2-1+)г/2)-го дешифратора соединен с вторым входом )- го элемента И г-й группы -го блока коммутации, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами третьего элемента ИЛИ, и через первый и второй элементы НЕ - соответственно с первым и вторым входами первого элемента И, выход которого соединен с входом установки триггера в единичное состояние и первым входом второго элемента И, выход которого является выходом окончания работы устройства, выход тоетьего элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с входом установки триггера в нулевое состояние, выход которогосоединен с вторым входом второго элемента И, вход начальной установки устройства соединен с входами установки триггеров блоков сравнения в нулевое состояние и входом начальной установки блока загрузкиномеров чисел в счетчики и вторым входом четвертого элемента ИЛИ, вход управления загрузкой устройства соединен с управляющим входом блока загрузки номеров чиселв счетчики, выходы которого соединены с.установочными входами счетчиков, вход синхронизации устройства Соединен с входом синхронизации первого ивторого триггеров всех блоков сравнения, в каждомблоке сравнения первый вход четвертого элемента И подключен к первому входу второго элемента И, в каждом блоке сравнения выходы (232-1)-го и 232-го элементов И соединены соответственно с первым и вторымвходами 32-го элемента ИЛИ, выход которого соединен с первым входом (3-Я 2)-го элемента И-НЕ и через Я 2-й элемент НЕ - с вторым входомЯ 2-го элемента И-НЕ, выход которого соединен с первым входом (32+2)- го элемента И-НЕ, выход которого соединенс информационным входом 32-го триггера, инверсный выход которого соединен стретьим входом (3-52)-го элемента И-НЕ и с вторым входом (52+2)-го элемента И-НЕ,прямой выход второго триггера соединен синформационным входом третьего триггера, выход которого соединен с первыми входами пятого и шестого элементов И, входсинхронизации третьего триггера подключен к выходу третьего элемента ИЛИ, 32-йуправляющий вход устройства соединен свторыми входами 32-го (52+4)-го и (5-32)-го элементов И блоков сравнения и с Я 2-м входом третьего элемента ИЛИ блоков сравнения. На фиг. 1 представлена структурная схема устройства, на фиг. 2 - функциональная схема блоков выбора кодов и блоков сравнения; на фиг, 3 - функциональная схема коммутатора; на фиг. 4 - функцибнальнаясхема блока загрузки номеров чисел в счетчики; на фиг. 5 - временная диаграмма работы устройства; на фиг. 6функциональная схема элемента сравнения.Устройство для сортировки (фиг. 1) содержит в регистров 11,1 п 1, К блоков сравнения 212 к (где К = )гп/2( - целая часть числа в/2, К блоков выбора кодов 3;Зк, коммутатор 4, в.счетчиков 515, е дешифраторов 616 П, причем выход каждогорегистра 111 П соединен с входом 7 блоков выбора кодов 313 к, а выходы 8, 9, 10каждого блока выбора кодов 313 к соединень 1 г входами соответствующего блока10 15 20 30 40 50 55 сравнения 212 к, выходы 11 и 12 которых соединены с соответствующими входами коммутатора 4. Выходы 13 и 14 коммутатора 4 соединены попарно с суммирующим и вычитающим входами счетчиков 515 п, информациойные выходы которых подключены к входам дешифраторов 616 п. Выходы 15 дешифраторов 616 п 1 соединены соответственно с входами блоков выбора кодов 313 к и коммутатора 4, а также являются группой выходов устройства. Тактовый вход 16 устройства подключен к входам управленйя сдвигом регистров 111 п, управляющие входы 17, 18, вход начальной установки 19 ивходсинхронизации 20 устройства соединены с соответствующими входами блоков сравнения 212 к, кроме того, вход начальной установки 19 устройства подключен также к входам установки в нулевое состояние счетчиков 515 п и входу начальной установки блока загрузки 21, управляющий вход которого соединен с входом управления загрузкой 22 устройства, а его информационные выходы 23 - к установочным входам счетчиков 515 п, Выходы 11 и 12 блоков сравнения 212 к соединены с входами элементов ИЛИ 24 и 25 соответственно; выходы которьх подключены к входам элемента ИЛИ 26 и через элементы НЕ 27,28 к входам элемента ИЛИ 29, выход которого соединен с входом установки в единичное состояние ,триггера 30 и первым входом элемента И 31, второй вход которого подключен к прямому выходу триггера 30, а выход является выходом 32 окончания работы устройства. Выход элемента ИЛИ 26 соединен с первым вхо- . дом элемента ИЛИ 33, второй вход которого подключен к входу начальной установки 19 устройства, а выход - к входу установки в нулевое состояние триггера 30,На фиг, 2 представлена функциональная схема двух блоков выбора кодов З и 3(к+1) (где К = 1, 2, , К, К = 1 а/20, каждый из которых содержит три мультиплексора 34, 35, 36, выходы которых 37, 38, 39 являются выходами 8, 9, 10 каждого блока выбора кодов 313 к соответственно, .причем 1-е входы мультиплексоров 34, 35, 36 соединены с выходом старшего разряда 1-го регистра 111 п(где 1= 1, 2, ., т),)-й выход 2 К-го дешифратора 61,.,6 п, 3 с = 1, 2, ., К, соединен с)-м управляющим входом мультиплексора 35 К-го блока выбора кодов 313 к-)-й выход (23+1)-го дешифратора 61,ба, соединен с )-м управляющим входом мультиплексора 34 2-го блока выбора кодов 31.,3 к и мультиплексора 35 М-го блока выбора кодов 31,3 к. )-й выход первого дешифратора 61 соединен с )-м управляющим входом мультиплексора 34 первого блока выбора кодов31. При гп - нечетном)-й выход гп-го дешифратора 6 соединен с)-м управляющим входом мультиплексора 36 К-го блока выборакодов Зк. 5На фиг. 2 также представлена функциональная схема двух блоков сравнения 2,2(+1)(где 1 с = 1, 2, К, К =)гп/2), каждый изкоторых содержит элементы И 40, 41, 42,43, 44, 45, элементы ИЛИ 46, 47 и элемент 1048 сравнения, причем первые входы элементов И 40, 41 и 42 блока сравнения 2 кподключены к выходам 8,9, 10 блока выборакодов Зк, первый вход элемента И 43 такжеподключен к выходу 9 блока выбора кодов 153, Вторые входы элементов И 40, 43 и 44блоков сравнения 21 ,.2 к соединены с управляющим входом 17 устройства, а вторыевходы элементов И 41, 42 и 45 блоков сравнения 21,.,2 к соединены с управляющим 20входом 18 устройства, выходы элементов И40, 41 и элементов И 42, 43 подключены квходам элементов ИЛИ 46,47 соответственно, выходы которых соединены с информационными входами 49 и 50 элемента 48 25сравнения соответственно. Входы установки в нулевое состояние и синхронизацииэлемента 48 сравнения блоков сравнения212 к подключены к входам начальной установки 19 и синхронизации 20 устройства 30соответственно, а его выход соединен с первыми входами элементов И 44 и 45, выходыкоторых являются выходами 11 и 12 блоковсравнения 212 к соответственно,Коммутатор 4 содержит К блоков коммутации 511;,51 к(где К =гп/2, функциональная схема двух из которых 51 к и 51(+1)представлена на фиг. 3 (где Е = 1, 2, , К).Каждый блок 51151 к содержит четырегруппы 521524 элементов И и элементы 40ИЛИ 531, 532, ИЛИ 541, 542. В случае, когдагп - нечетное число, блок 51 к содержит дополнительно элементы ИЛИ 53 з, 54 з. Каждая группа 521.,524 элементов И блоков51151 к содержит в элементов И 55, причем первые входы элементов И 55 групп 521и 522 элементов И блока 51 соединены свыходом 11 блока сравнения 2 К а первыевходы элементов И 55 групп 52 з и 524 элементов И - с выходом 12 блока сравнения 502 к. Вторые входы 1-го элемента И 55 групп521 элементов И блока 51 подключены к(где =1,2, , гп), вторые входы 1-го элементаИ 55 групп 522 и 52 з элементов И - к 2 К-му 55выходу 1-го дешифратора 616, вторыевходы 1-го элемента И 55 группы 524 элементов И - к (21+1)-му выходу 1-го дешифратора61. 6 П. Выходы элементов И 55 групп 521 и52 з элементов И блоков 51151 к обьединены и подключены таким образом, что(щ) входы элемента ИЛИ 53 блока 51 подключены к выходам (2 Е)-х элементов И 55 групп 521 и 52 з элементов И блоков 511, 51 к, (гп) входы элемента ИЛИ 532 - к выходам 21-х элементов И 55 групп 521 и 52 з элементов И блоков 51151 к. Аналогично, выходы элементов И 55 групп 522 и 524 элементов И блоков 511,.,51 к объединены и подключены таким образом, что (в) входы элемента ИЛИ 541 блока 51 подключены к выходам (2 К)-х элементов И 55 групп 522 и 52 д элементов И блоков 511, ,51 к, (п 1-1) входы элемента ИЛИ 542 - к выходам 21-х элементов И 55 групп 522 и 524 элементов И блоков 51151 к, Выходы элементов ИЛИ 531 и 532 блока 51 подключены к суммирующим входам 21-1)-го и 2 Е-го счетчиков 515 п 1 соответственно, а выходы элементов ИЛИ 541 и 542 - к вычитающим входам (2 К)-го и 2 К-го счетчиков 515 п соответственно.Блок 21 загрузки номеров чисел в счетчики (фиг. 4) содержит счетчик 56 и р демультиплексоров 57157 р(где р = о 92 гп), причем вход сброса и суммирующий вход счетчика 56 подключены к входам начальной установки 19 и управления загрузкой 22 устройства соответственно, р информационных выходов - к соответствующим адресным входам демультиплексоров 57157 р, кроме того, )-й информационйый выход счетчика 56 соединен с информационным входом ЧЧО)-го демультиплексоров 571,.,57 р (где ) = 1, 2, . р), а 1-е выходы демультиплексоров 571,57 р являются выходами 23 блока 21 загрузки и соединены с соответствующими установочными входами 1-го счетчика 51,5 в (где 3 = =1, 2, , гп).Элемент 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 подключен к информационному входу триггера60, прямой выход которого является выходом элемента 48 сравнения, входустановки в нулевое состояние триггера 60 подключен к входу начальной установки 19 .устройства, а вход синхронизации - к выхо ду элемента ИЛИ 67, входы которого соединены с управляющими входами 17 и 18 устройства.Устройство работает следующим обра .эом.В начале работы по управляющему сигналу на входе 19 устройства происходит установка в нулевое .состояние счетчиков 515 в, счетчика 56 блока 21 загрузки и 15 триггеров 58, 59, 60 элемента 48 сравнения, а также триггера 30 устройства, в результате чего на выходе 32 устройства присутствует сигнал логического нуля. Одновременно с записью в регистры 1,1 п исходных чисел 20 (цепи начальной установки и занесения чисел не приводятся) в счетчиках 515 п формируется с помощью блока 21 загрузки необходимая информация, т.е. фиксируется порядковый номер соответствующего реги стра 11, 1 п. Затем начинается непосредст.венно процесс сортировки, в первом такте которого выполняется сравнение данных, находящихся в (2 с)-м и 2 с-м регистрах 11,.,1 П, где с = 1, 2, , К, К = )гп/2, под 30 действием управляющего сигнала У 1 на входе 17 устройства. В результате для большего данного, находящегося в (2 с)-м регистре 11 п происходит увеличение на единицу содержимого в соответствующем 35 (2 с)-м счетчике 515 П. Одновременно происходит уменьшение на единицу содержимого 2 с-го счетчика 55 и, соответствующего меньшему данному, находящемуся в 2 с-м регистре 111 П В случае, если боль шее число находится в 2 с-м регистре 11 п, изменений содержимого в соответствующих (2 с)-м и 2 с-м счетчиках 51.,5 п не происходит.45Во втором такте под действием управляющегого сигнала У 2 на входе 18 устройства сравниваются пары чисел в 2 с-м и (2 с+1)-м регистрах 11 П аналогично процессу; описанному для первого такта в 50 (2 с)-м и 2 с-м регистрах 111 п соответственно. Далее выполняются действия,аналогичные выполняемым в первом й вовтором тактах цикла сортировки до тех пор, пока не будет присвоен старший по рядковый номер большему из исходных чи-.сел, а меньший порядковый номер - меньшему числу, что фиксируется появлением единичного сигнала на выходе 32 окончания работы устройства. В процессе сортировки в каждом иэ блоков выбора кодов 3 Зк (фиг. 2) сигналыайс-),2 с, рс+1) на выходах 37, 38, 39 формируются следующим образом:К=Цо;.Е:Оа(Ь.) =;, -Люк. )где а - значение (содержимое) 1-го регистра11 1 п,1(2 с)ь (2 к), (2 с+) - значение (21 с)-го,2 с-го (2 с+1)-го разрядов 1-го дешифратора61,6 в.Последовательность выполнения нечетного и четного тактов цикла сортировки инициируется последовательностью появлениясигналов У 1, У 2 на входах 17 и 18 устройства.С помощью элемента 48 сравнения определяется случай, когда первое из пары сравниваем йх чисел больше второго. В результате,в случае выполнения этого соотношения, внечетном такте появляется единичный сигнал цс, на выходе 11 соответствующего с-гоблока сравнения 21,.,2 к, в четном такте -единичный сигнал цс на выходе 12 соответГствующего с-го блока сравнения 21,2 к (гдес = 1, 2, ., К) (фиг. 2). На выходах 13 и 14 блока 51 к коммутатора 4 (фиг, 3 формируются сигналы црк) и ц(2 с-)ц(ь) и. црс) соответственно, которые вызывают увеличение и уменьшение на единицу содержимого в (2 с)-м и 2 с-м счетчиках 515 П соответственно, для которых характерны следующие соотношения:1 Сь-) - , % МЧЫл 1 - ЧВ,(, =лс(ц)., с.( 1-сл с. (1;,с(,=Я, л с. ОьУФормирование соответствующих порядковых номеров в счетчиках 515 П выполняется следующим образом (фиг. 4). С приходом каждого тактового импульса Уо по входу 22 управления загрузкой устройства в предварительно обнуленном счетчике 56 блока 21 загрузки номеров чисел в счетчики происходит увеличение его содержимого на единицу. Емкость счетчика 56 и количество демультиплексоров 5757 Р должно быть равно величине р =о 92 а. Информация, формируемая в каждом такте цикла загрузки Тзагр (фиг. 5) в счетчике 56, является адресом, поступающим на входы14 13 1793438 5 10 30 А,А(р) демультиплексоров 57157 р, по которому осуществляется запись в счетчики 515 п 1, и одновременно данными, поступающими на информационный вход ЮО соответствующего демультиплексора 57157 р. Таким образом, в 1-й такт цикла загрузки число, равное величине , записывается по -му адресу, т.е. в -й счетчик 51,5 П (где= 1, 2 гп).,Элемент 48 сравнения (фиг. 6) предназначен для выполнения анализа двоичных чисел, начиная со старших разрядов. В начальном состоянии триггеры 58, 59, 60 обнулены. При сравнении значения одноименных разрядов величин а(2-1) и арк) в нечетных тактах и величин арк) и арк+1) в четных тактах цикласортировки последовательно и синхронно подаются на соответствующие входы 49 и 50 элемента 48 сравнения. С приходом каждого тактирующего сигнала У 4 на вход 20 синхронизации устройства триггеры 58 и 59 переходит в новое состояние. Триггеры 58 и 59, элементы И-НЕ 61, 62, 63, 64 и элементы НЕ 65, 66 составляют схему ячейки, используемой при сравнении величин.Триггер 60 и элемент ИЛ И 67 служат для фиксации окончательного результата процесса попарного сравнения исходных чисел в каждом такте (четном или нечетном) цикла сортировки. В случае, если выполняется соотношение арк)а(2 к) или а 2 цар+1), на выходе триггера 60, т,е. на вйходе "Больше" элемента 48 сравнения, появляется единичный сигнал с приходом заднего фронта сигналов У 1(У 2) на управляющих входах 17 и 18 устройства соответственно,Рассмотрим потактную работу устройства при сортировке чисел, например: а 1 = 9, а 2 = 1, аз = 3, а 4 = 5, а 5 = 7.В табл. 1 показано исходное состояние регистров 1115 и счетчиков 5155, а также наличие соответствующих единичных сигналов на выходах дешифраторов 6165 непосредственно перед началом цикла сортировки, в результате которого все числа должны быть отсортированы в порядке возрастания, т.е, большее по величине число должно находиться в регистре 15(с большим индексом), а наименьшее число- соответственно в регистре 11(с меньшим индексом),С приходом каждого тактового сигнала Уо на вход 22 управления загрузкой устройства в предварительно обнуленном счетчйке 56 блока 21 загрузки происходит увеличение на единицу его содержимого. Емкость счетчика 56 равна величине р = 3, где р = )о 92 в. Информация, формируемая в каждом такте цикла загрузки Тзагр является адресом, поступающим с информационных выходов счетчика 56 на входы АоА 2 дешифраторов-демул ьти плексо ров 57157 з блока 21 загрузки, по которому осуществляется запись в счетчики 5155, и одновременно данными, поступающими после инвертирования на входы 6(0 дешифраторов-демультиплексоров 571.57 з, которые являются в этом случае информационными входами. Таким образом, необходимая информация записывается по соответствующему адресу, т.е, в соответствующий счетчик 515 б.После загрузки исходных данных начинается непосредственно цикл сортировки,В табл, 2 наглядно представлен порядок попарного сравнения чисел и их перемещения во время каждого такта цикла сортировки, Приведенный пример сортировки является примером сортировки транспозициями, в процессе которой числа сравниваются попарно; при этом сначала (2 К)-й и 2-й элементы последовательности в чисел, а затем 2 Е-й и (2 К+1)-й элементы (где )с = 1, 2, К, К =гп/2, причем при сравнении в парах чисел происходит перестановка, в результате которой меньшие числа фиксируются на младших позициях (в младших регистрах), большие - на старших позициях (в старших регистрах). В предлагаемом устройстве вместо перестановок в сравниваемых парах чисел вкаждом такте цикла сортировки Тс выполняется изменение номеров позиций чисел всоответствующих счетчиках 51,;,55 таким35 образом, что перестановке числа а из младшего 1-го регистра 11,.,1 б в старший (+1)-йрегистр 11,15 соответствует увеличениена единицу содержимого 1-го счетчика. 51,55, а перестановке числа ар+1) из стар 40 шего (+1)-го регистра 1115 в младший )-йрегистр 1115 - уменьшение на единицу=1,2,.;., гп),В первом такте цикла сортировки вы 45 полняется попарное сравнение чисел (а 1-а 2)и (аз - а 4). Поскольку присутствуют единичные сигналы 911: 922: дзз; 944; 955 (табл, 1) навыходах соответствующих дешифрэторов6165, то это позволяет подать числа а 1. а 2,50 аз, а 4, а 5 с выходов 8, 9, 10 блоков выборакодов 31,32, на входы блоков сравнения 21,22, где будет выполняться сравнение чисел,поступающих только с выходов 8 и 9 блоковвыбора кодов 31, 32, а именно чисел а 1, а 2 иаз, а 4, т.к, в первом такте, как и во всехпоследующих нечетных тактах цикла сортировки, присутствует единичный сигнал У 1 навходе 17 устройства, который не разрешаетпопарное сравнение чисел (э 2-аз) и (э 4-э 5).В приведенном примере (табл, 2) нэ первом1793438 16 20 25 такте цикла сортировки перестановка должна осуществляться в первой паре чисел, а это значит, что наличие единичного сигнала О 1 инициирует появление единичного сиг. нала ц 1 на выходе 11 первого блока сравнения 21, что приведет к формированию единичных сигналов ц 11 и ц 22, поскольку присутствуют единичные значения на выходах 911 и 922 дешифраторов 61.62. через элементы ИЛИ 531 и 541 сигналы ц 11 и ц 22 . поступят с выходов 13 и 14 первого блока 511 коммутатора 4 в виде единичных сигна+лов ц 1 и ц 2 на суммирующий и вычитаЮщий входы счетчиков 51 и 52 соответственно, что приведет к фиксации единичных сигналов 921 и 912 на выходах 15 дешифраторов 6165 соответственно, т.е. к фактической перестановке чисел в первой из сравниваемых пар.. Во время второго такта должно выполняться попарное сравнение содержимого ретистров 12 - 13, 14-15, т.е, чисел (а 1 - аз), (а 4- а 5) табл. 2). Это достигается за счет того, что на входе 18 устройства во втором и во всех последующих четных тактах цикла сортировки присутствует единичный сигнал У 2, .что позволяет сравнивать данные, поступающие с выходов 9, 10 блоков выбора кодов 31, 32 на соответствующие входы блоков сравнения 21,22, в то время, как присутствуют единичные сигналы 921, 912, 933, 944 955 на выходах соответствующих дешифрато ров 61,65. Таким образом, на входы элементов 48 сравнения поступят пары чисел (а 1 - аз) и (а 4-а 5), что приведет, как следует из табл, 2, к появлению единичного сигнала ц 11 на выходе 12 блока сравнения 21. Последний факт при наличии единичных сигналов д 21 и 933 вызовет формирование единичных Ф о р мул а и зоб ретен и я Устройство для сортировки чисел, содержащее а регистров, где в - количество сортируемых чисел, в счетчиков, К блоков сравнения, где К = 1 а/2, )Х - ближайшее целое, не больше Х, коммутатор и два элемента И, причем вход начальной установки устройства соединен с входом установки счетчиков в нулевое состояние, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него введены К блоков выбора кодов, п 1 дешифраторов, блок загрузки номеров чисел в счетчики, триггер, четыре элемента ИЛИ и два элемента НЕ, коммутатор "содержит К блоков коммутации, содержащих каждый, кроме К-го, четыре группы элесигналов ц 21 и ц 33которые через элементы ИЛИ 531 блока 511 и ИЛИ 541 блока 512 поступят с выходов 13 и 14 блоков 511 и 512 коммутатора 4 в виде сигналов ц 1 и ц 3 на суммирующий и вычитающий входы счетчиков 51 и 53 соответственно, что приведет к фиксации единичных сигналов 931 и 923 на выходах 15 дешифраторов 61, 63 соответственно,.10 Таким образом, фактически произведена перестановка чисел а 1 и аз в регистрах 12 и 13. Аналогичным образом выполняется процесс сортировки в последующие нечетные и четные такты цикла сортировки. 15 Для наглядности в табл. 3 приведенырезультаты, зафиксированные на выходах 15 дешифраторов 6165 по окончании соответствующего такта цикла сортировки. По данным табл. 2 и 3 видно, что окончание процесса сортировки фиксируется на выходе элемента И 31 после того, как на четном (нечетном) и на следующем за ним нечетном (четном) тактах цикла сортировки не выполняется перестановка ни в одной йаре сравниваемых чисел. Например, на пятом такте цикла сортировки (табл. 2) не формируется блоками сравнения 21, 22 ни один сигнал ц 1, ц 2 и, следовательно, триггер 30 устанавливается в единичное состояние, на 30 следующем, шестом такте вновь не формируется блоками сравнения 21, 22 ни одинсигнал ц 1 ц 2, что свидетельствует об отсут.ствии перестановок в сравниваемых парахчисел, а значит фиксируется единичным сиг 35 налом на выходе 32 устройства момент завершения сортировки исходных чисел,Следовательно, максимальное время сортировки чисел в данном устройстве будет равно (гп+1) тактам цикла сортировки,40 ментов И и четыре элемента ИЛИ, К-й блок коммутации содержит четыре группы элементов И и 4 + 2 гпоб 2 п 1 элементов ИЛИ, каждый блок сравнения содержит шесть элементов И, три элемента ИЛИ; два элемента НЕ, четыре элемента И-НЦ и три триггера, каждый блок выбора кодов содержит три мультиплексора, тактовый вход устройства соединен с входом управления сдвигом регистров, выход старшего разряда )-го регистра О = 1, 2, . п 1) соединен с )-ми информационными входами мультиплексоров блоков выбора кодов, выход 31-го мультиплексора Ио блока выбора кодов (51= 1, 2, 3; = 1, 2- , К) соединен с первым входом 31-го элемента И 1-го блока сравнения, Я 2-йвыход которого (Я 2 = 1, 2) соединен с 1-м входом Я 2-го элемента ИЛИ и с первыми входами всех элементов И (2 Я 2-1)-й и 2 Я 2-й групп 1-го блока коммутации, входы г-го элемента ИЛ И (г = 1, 2, 3, 4) 1-го блока коммутации подключены к выходам (21- тоо 2 г)-х элементов И (г+1)/2(-й и /(г+3)/2(-й групп всех блоков коммутации, при а - нечетном входы (Я 2+4)-го элемента ИЛИ К-го блока коммутации подключены к выходам (2+1)-х элементов И Я 2-й и (Я 2+2)-й групп всех блоков коммутации, выход (2 Я 2-1)-го и 2 Я 2-го элементов ИЛИ 1-го блока коммутации соединены соответственно с суммирующим и вычитающим входами (21-2+Я 2)-го счетчика, выходы разрядов которого соединены с входами (21-2+2 Я)-го дешифратора, /-й выход Р-го дешифратора, где Р = 2, 42 К, соединен с /-м управляющим входом второго мультиплексора Р/2-го блока выбора кодов, /-й выход о-го дешифратора, где ц = 3, 5,;2 К, соединен с/-ми управляющими входами первого и третьего мультиплексоров (ц)/2-го блока выбора кодов, /-й выход первого дешифратора соединен с /-м управляющим входом первого мультиплексора первого блока выбора кодов, при в - нечетном /-й выход щ-го дешифратора соединен с /-м управляющим входом третьего мультйплексора К-го блока выбора кодов, выходы /-го дешифратора являются информационными выходами /-й группы устройства, /-й выход (21-1+1 г/2 Ц-го дешифратора соединен с вторым входом /-го элемента И г-й группы 1-го блока коммутации, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами третьего элемента ИЛИ и через первый и второй элементы НЕ - соответственно с первым и вторым входами первого элемента И, выход которого соединен с входом установки триггера в единичное состояние и первым входом второго элемента И выход которого является выходом окончания работы устройства, выход третьего элемента ИЛИ соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с входом установки триггера в нулевое состояние, выход которого соединен с вторым входом второго элемента И,.вход начальной установки устройства соединен с входами установки триггеров блоков сравнения в нулевое состояние и входом начальной установки блока загрузки номеров чисел в счетчики и вторым входом четвертого элемента ИЛИ, вход управления загрузкой устройства соединен с управляющим входом блока загрузки номеров чисел в счетчики, выходь 1 которого соединены с установочными входами счетчиков, вход синхронизации устройства соединен с входами синхронизации устройства первого и второго триггеров всех блоков сравнения, в каждом блоке сравнения первый вход четвертого элемента И подключен к первому входу второго элемента И, вкаждом блоке сравнения выходы (2 Я 2-1)-го и 2 Я 2-го элементов И соединены соответственно с первым и вторым входами Я 2-го элемента ИЛИ, выход которого соединен с первым входом (3-Я 2)-го злемента И-НЕ и через Я 2-й элемент НЕ - с вторым входом Я 2-го элемента И-НЕ, выход которого соединен с первым входом (Я 2+2)-го элемента И-НЕ, выход которого соединен с информационным входом Я 2-готриггера, инверсный выход которого соединен с третьим входом (3-Я 2)-го элементаИ-Н Е и с вторым входом (Я 2+2)-го элемента И-НЕ, прямой выход второго триггера соединен с информационным входом третьего триггера, выход которого соединен с первыми входами пяУого и шестого элементов И, вход синхронизации третьеготриггера подключен к выходутретьего элемента ИЛИ, Я 2-й управляющий вход устройства соединен с вторыми входами Я 2-го, (Я 2+4)-го и (5-Я 2)-го элементов И блоков сравнения и с Я 2-м входом третьегоэлемента ИЛИ блоков сравнения