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

(51)5 С 06 Р 7/08 ОПИСАНИЕ ИЗОБРЕТЕНИ е ТОРСКОМУ СВ раз- атор ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССРВ 1244659, кл. С 06 Р 7/04, 1984.Патент США В 3505653,кл. 340-172.5, 1970.(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автома" тике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения сортировки чисел в скользящей выборке. :Устройство содержит регистр 1, К групп ячеек анализа ЯА 21 -2 пп 1 (1=2юВ 2апертура выборки, а " количество рядов анализируемых чисел), генер 3 импульсов, триггер 4, счетчик 5, коммутаторы 6 -6, элементы ИЛИ 7 -7 входы 8, выходы 9-9 разрядов чисел отсортированной выборки. ЯА 2 содержит т.риггер, элементы И, ИЛИ, два коммутатора, информационные управляющие и тактовые входы, вход перекоса, вход управления режимом, информационные выходы, выход переноса.Устройство обеспечивает сортировку в порядке убывания чисел в скользящей выборке, т.е. сначала - сортировке выборки чисел 1 А и Ае Ак, а следующем такте - выборки чисел А р А 11 р Ак р Арти т.д. 2 ил.Изобретение относится к области автоматики и вычислительной техники.Цель изобретения -. расширение функциональных возможностей за счет обеспечения сортировки чисел в сколь 5 вящей выборке.На фиг. 1 приведена схема устройства; на фиг. 2 - схема ячейки анализа.Устройство содержит регистр 1, первую и вторую матрицы ячеек анализа, которые содержат 1 групп ячеек 2-,2 (п 1 анализа Ь = 2 - апери тура выборки, ш - количество разрядов анализируемых чисел), генератор 3 импульсов, триггер 4, счетчик 5, коммутаторы 6-6, элементы ИЛИ 7- 7, входы 8, выходы 9, -9 щразрядов чисел отсортированной выборки. Ячейка 2 анализа содержит триггер 10, элементы И 11-11, элементы ИЛИ 2-. 12 э, коммутаторы 13 и 13, информационные входы 14 и 14, управляющие входы 15 и 15, тактовые входы 1.6 и 16, вход 17 переноса, вход 18 управления режимом, информационные выходы 19-19, выход 20 переноса.Устройство работает следующим образом.При работе устройства в ячейках 2, -2, находятся К ш-разрядных чисел, отсортированных в порядке убывания (в ячейке 2- старший разряд самого большого числа), а в ячейках 2 ,+1 в 2 ( 1 в величина шойМ, где И - номер числа в порядке поступления.Очередное анализирующее число поступает на входы 8 и сигналами с выхода а генератора 3 импульсов записывается в регистр 1.Одновременно число, хранящееся в счетчике 5, увеличивается на единицу, а триггер 4 устанав .ливается в единичное состояние, Далее происходит поиск числа, записанного в триггер ячеек 2 -2,анализ а 1 тактов назад (т, е, само го старого из хранящихся в устройстве). Это число имеет тот же самый номер (так как емкость счетчика 5 равна 1 с), что и только что поступившее число, и этот номер хранится в триггерах ячеек 2, -2, 1, Поиск номераи т.и 55 числа, равного текущему номеру, хранящемуся в счетчике 5, выполняется в ячейках 2,1 -2 , 1 с помощью элементов И 114, 117 и элемента ИЛИ 12, На выходе 20 переноса ячейки 21(0(, - номер строки, содержащей искомое число) формируется логйческая единица, которая по цепоч"ке из элементов ИЛИ 7-7 распространяется на управляющие входы 15соответствующих ячеек 2 - 2, ,(т+М фКроме того, сформированная на выходе 20 переноса ячейки 211 логическая единица через коммутатор 6поступает на управляющие входы 151ячеек 2- 2 (,1 выбранной строки М, . В результате число, записанное в ячейках 2 -2 теряется; числа. с их номерами, записанныев ячейках 2 р, -2, р,+1) ф-(0 +1)(1+2) Зс), переписываются каждоев предыдущую (3-1) строку (т.е. вячейке 2 (р., -2 в-),(гнп 1ячейке 2 -2 ,+д 1) 1 с-й строки записываются нули.На втором полутакте сигналом свыхода б генератора 3 импульсовтриггер 4 устанавливается в нулевоесостояние. Происходит поиск чисел,меньших, чем текущее, находящеесяв регистре 1. На выходах переносаячеек 2- 2строк, содержащихтакие числа, формируется логическаяединица, которая через коммутаторыбс поступает на входы 15 всех ячеек2 р, -2 п,п 1 анализа. В результатечисла с их номерами, записанные вячейках 2 р -2 у,пп 1 Я=И, В+1),(т.е, в ячейки 2(у 1, -2(рм),в+и) )а затем по сигналу с выхода в генератора 3 импульсов в ячейку строки 06записывается текущее число с его номером,Таким образом, на выходе 9 устройства на каждом 1-м такте работы устройства формируется выборка чиселРА; 1,. А отсортированная в порядке убывания.Формула изобре тенияУстройство для сортировки чисел,содержащее регистр и первую и вторую матрицы ячеек анализа которое содУдержат Егрупп ячеек анализа соответственно по ш и и ячеек анализа в группе, где Е - апертура сортировки, в - количество разрядов со ртируемых чисел, причем каждая ячейка анализа содержит триггер, первый, второй,5 1 О 15 25 30 45 50 55 5 164третий и четвертый элементы И и первый элемент ИЛИ, а каждая ячейка анализа. первой матрицы содержит, кроме того, пятый и шестой элементы И ивторой элемент ИЛИ, причем вход ь-горазряда сортируемого числа устройства, где ь=1,2 ш, соединен синформационным входом -го разрядаре гистра, выход которо го соединен спервым информационным входом ь-йячейки анализа первой группы первойматрицы, первые информационные выходы 1-й и 1.-й ячеек анализа 1-й группы соответственно первой и второйматриц, где 3=1,2и, 1=1,2Ь), соединены с первыми информационными входами соответственно -йи 1-й ячеек анализа (1+1)-й группытой же матрицы, в каждой группе ячеек анализа выход переноса р-й и ц-йячеек анализа соответственно первой .и второй матриц, где р=1,2(тп), с 1,2,, (и-) соединен свходом переноса соответственно (р++1)-й и (ц+1)-й ячейки анализа тойже группы той же матрицы, в каждойячейке анализа первый тактовый входсоединен с первыми входами первогои второго элементов И, первый информационный вход соединен с вторым входом второго и первым входом третьегоэлементов И, выход третьего элемента И соединен с первым входом первого элемента ИЛИ, второй вход которого подключен к выходу четвертогоэлемента И, первый и второй входыкоторого подключены соответственно к прямому выходу триггера и к входу переноса этой ячейки анализа, кроме того, в каждой ячейке анализа первой матрицы ее второй информационный вход соединен с первым входом пятого элемента И, выход которого соединен с .первым входом второго элемента ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем обеспечения сортировки чисел в скользящей выборке, в него введены счетчик, триггер, генератор импульсов, К коммутаторов, К эле.ментов ИЛИ, в каждую ячейку анализа второй матрицы введены пятый и шестой элементы И и второй элемент ИЛИ, в каждую ячейку анализа обеих матриц введены седьмой элемент И, третий элемент ИЛИ и два коммутатора, причем выход 1-го разряда счетчика соединен с первым информационным входом 4128 6-й ячейки анализа первой группы второй матрицы, вторые информационныевходы -й и 1-й ячеек анализа 1-хгрупп соответственно первой и второйматриц подключены к вторым информационным выходам соответственно -йи 1-й ячеек анализа (1+1)-й группытой же матрицы, входы переноса первых ячеек анализа всех групп обеихматриц подключены к входу .логической единицы устройства, выходы переноса п-й и и-й ячеек анализа з-йгруппы соответственно первой и второй матрицы, где з,2 соединены соответственно с первым информационным входом з-го коммутатора и спервым входом з-го элемента ИЛИ,выходы которых соединены соответственно с первыми и вторыми управляющнми входами всех ячеек анализа з-й группы обеих матриц, выход переносаи-й ячейки анализа з-й группы второй матрицы соединен с вторым информационным входом з"го коммутатора,выход 1-го элемента ИЛИ соединен свторым входом (1+1)-го элемента ИЛИ,вторые информационные входы всехячеек анализа 1-й группы обеих матриц подключены к входу логическогонуля устройства, входа задания режима всех ячеек анализа первой и второй матриц подключены к входам соответственно логической единицы и логического нуля устройства, первыйвыход генератора импульсов соединенс входом разрешения записи регистраи со счетным входом счетчика, первыйн второй выходы генератора импульсовсоединены с входами установки триггера соответственно в единичное инулевое состояния, прямой выход которого соединен с управляющими входами всех коммутаторов, второй и третий выходы генератора импульсовсоединены соответственно с первым ивторым тактовыми входами всех ячееканализа обеих матриц, второй входпервого и третий вход 1-х элементовИЛИ подключены соответственно к входам логического нуля и логическойединицы устройства, третий. информационный вход -й ячейки анализа 1-йгруппы первой матрицы является выходом - го раз ряда К-го числа о тсо ртированной выборки устройства,в ячейкаханализа второй матрицы второй информационный вход соединен с первым входомпятого элемента И, выход которого1644128 8 триггера является третьим информационным выходом ячейки анализа и соединен с вторыми информационными входами первого и второго коммутаторов, выходы которых являются соответственно первым и вторым информационными выходами этой ячейки анализа, вход переноса ячейки анализа соединен с первым входом седьмого элемента И, выход которого соединен с третьим входом первого элемента ИЛИ, выход которого является выходом переноса ячейки анализа, инверсный выход триггера соединен с вторыми входами третьего и седьмого элементов И, второй управлякщнй вход ячейки анализа соединен с управляющим входом второго коммутатора, вторым входом пятого и первым входом шестого элементов И, второй тактовый вход ячейки соединен с третьим входом пятого и вторым входом шестого элементов И, вход выбора режима ячейки анализа объединен с 25 третьим входом третьего элемента И. соединен с первым входом пятого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, во всех ячейках анализа обеих матриц первый информационный вход соединен с первым информационным входом первого коммутатора, третьим входом четвертого элемента И и с инверсными . входами первого и седьмого элементов И, второй информационный вход ячейки анализа соединен с первым информационным входом второго коммутатора и с инверсным входом шестого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, первый управляющий вход ячейки анализа соединен с управляющим входом первого коммутатора, третьим входом второго и вторым входом первого элементов И, выходы которых соединены с вторыми входами соответственно второго и третьего элементов ИЛИ, выходы которых соединены с входами установки триггера соответственно в единичное и нулевое состояния, прямой выход г Составитель В. Горох едактор Е.Папп Техред Л.Сердюковабруч оррек т Т ССС 01 1 11оизводственно-издательский комбинат Патент , г.ужг Гаг аказ 1241, Тираж 399 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям и113035, Москва, Ж, Раушская наб., д. 4/5