Устройство для упорядочивания чисел

СОЮЗ СОВЕТСНИСОЦИАЛИСТИЧЕСНРЕСПУБЛИН 8012412 а)4.С 06 АНИЕ ИЗОБРЕТЕНИЯБ йЯ:, Всэлемент ретью групп и, группу э инхронизаци отехническ и оператив ыковаи И.А. Анисиперезаписи, т тыре элемента задержки, эле определения н гистра. Исход разбивается н ьство СССР 7/04, 1981 ство СССР 7/Об, 1983 чал ва масси ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ АВТОРСКОМУ СВИДЕТЕЛЬСТ(57) Изобретение относится .к вычислительной технике, в частности к устройствам для автоматическойсортировки и упорядочивания чисел, и может быть использовано при реализации технических средств систем ;автоматического контроля тенхологических процессов. Цель изобретения в повышение быстродействия устройства. Устройство содержит и групп входных элементов И,п входных регистров,п групп элементов перезаписи,две группы элементов И, и групп элементов ИЛИ переписи, груп " ИЛИ, первую, вторую и элементов И, блок памяементов задержки и блока также дополнительно регистров, элементы ИЛИ ри регистра сдвига, че- ИЛИ, группу элементов мент задержки и блок омера оперативного реный массив чисел сна а причем в массиве А находятся числа с "1" в первом разряде, в массиве В - с "0". Затем каждый из массивов А и В также разбивается на две части А 1 и АО, В 1 и ВО, причем в А 1 и В 1 помещаются числа с "1" во втором разряде, в АО и ВО - с "0" во втором разряде. Далее каждый из полученных массивов А 1, АО, В 1, ВО также разби- %ваэ вается на две части - в одной числа с "1" в третьем разряде, в другой - с "0". Такое .разбиение осуществляется аналогично и по остальным (ш)-м разрядам чисел, где щ - количество разрядов в числе. В итоге получается массив упорядоченно распоФащ ложенных чисел. 2 з.п, ф-лы, 4 ил. ЮЮ4 1241Изобретение относится к автоматикеи вычислительной технике, в частностик устройствам автоматической сортировки и упорядочивания чисел, и можетбыть использовано при реализации технических средств цифровых систем контроля параметров технических объектов,Цель изобретения - повышениебыстродействия устройства,Но фиг, 1 представлена структурнаясхема устройства для случая упорядочивания четырех кодов числовогомассива; на фиг, 2 - структурная схема блока управления; на Фиг. 3структурная схема блока определенияномера оперативного регистра; наФиг. 4 - структурная схема блока памяти.Устройство (фиг.1) содержит, груп"пы входных элементов И 14,группыэлементов ИЛИ 58 переписи, группуэлементов ИЛИ 9, входные регистры1013, первый регистр 14 сдвига,первую группу элементов И 15, группы элементов И 1619 перезаписи,блок 20 управления, оперативные регистры 21;24, третий регистр 26сдвига, элементы ИЛИ 2 перезаписи,блок 28 памяти, второй регистр 30сдвига группы элементов 31 и 36 задержки группы элементов И 32 и 35,блок 33 определения номера оперативного регистра, первый, второй,третий и четвертый элементы ИЛИ 34,29. 25 и 37, и элемент 38 задержки.Блок 20 управления (фиг,2) содержит элементы ЗАПРЕТ 39, элементыИЛИ 40, счетчик 41, дешифратор 42,элементы 43 задержки, одновибратор44 генератор 45 тактовых импульсов,Т-триггер 46 и элементы И 47.Блок 33 определения номера оперативного регистра (фиг,3) содержитгруппу элементов ЗАПРЕТ 48, группуэлементов И 49, элемент НЕ 50, группу триггеров 51, группу элементовИЛИ 52, группу элементов И 53 и 55 игруппу элементов ЗАПРЕТ 54.Блок 28 памяти (Фиг.4) содержитэлемент ИЛИ 56, элемент 57 задержки,группу триггеров 58, группы элементов ИЛИ 59 и 62, группы элементовИ 60 и 63, и группу 0-триггеров 61,Устройство работает следующимобразом.После подачи сигнала "Пуск" наодновибратор 44 он вырабатывает прямоугольный импульс длительностью228 10 15 поступает на элемент 43.4 задержки и 20 25 30 3 ) 40 44, который обнуляет счетчик 41 и поступает наэлемент 43,1 задержки ина четвертый выход блока 20 управления. Импульс с четвертого выходаблока 20 управления обнуляет регистры 14, 26 и 30 сдвига и устанавливает в нулевое состояние триггеры58. 1-58.3 блока 28 памяти через зле менты ИЛИ 56 и 59.1-59.3 и в единичное состояние триггер 58,4, таким образом устанавливая блок 28 памяти в исходное состояние, По истечении времени задержки С ,43,1 элемента 43. 1 задержки импульс с его выхода на второй вьвсод блока управления, производит запись "1" в первые информационные разряды регистров 14, 26 и30 сдвига через элементы ИЛИ 40,2,25 и 29, одновременно открывая группы вхоцных элементов И 1.4 и поступая через группу элементов ИЛИ 9 натактовые входы регистров 1013, темсамым записывая вхоцную информацию скодовой шины чисел устройства в видекодов чисел с их адресами в эти регистры .1013, причем число занимает разряды 1-ш, а адресф- разряды(ш+1)-р. По истечении43.4 импульсс выхода элемента 43:4 задержки запускает генератор 45 тактовых импульсов.Прямоугольные импульсы на обоих выходах генератора 45 тактовых импульсов с периодом Т=2 г 44=2 с 43. 1=24 г 43.4 поступают на элементы И47,1 и 47.2, а так как только на одном из выходов Т-триггера 46 уровень1 импульсы проходят через одинэлемент И (47.1 либо 47,2) и черезэлемент ИЛИ 40 на четвертый выходблока 20 управления и элементыИ 47.3 и ЗАПРЕТ 39.3,С помощью регистра 14 сдвига, группы элементов И 15 и группы элементов И 1619 исходный массив перезаписывается в оперативные регистры 2124 с разбиением на массивы А и В причем массивы А и В записываются в регистр 2124 управляющими сигналами соответственно регистров 26 и 30 сдвига, поступающими на тактовые входы регистров 2124 через группу управляющих элементов ИЛИ 27. При этом группы элементов И 1619 перезаписи состоят из бистабильных элементов И, т, е. при отсутствии управляющего сигнала имеют большое выходное сопротивление.Тактовые сигналы для регистров 26и 30 сдвига вырабатываются соответственно элементами И 47.4 и ЗАПРЕТ39.4, так как значение первогоразряда очередного числа поступаетна второй вход блока 20 управления.После четвертого такта блок28 памяти запоминает номер оперативного регистра, в котором хранитсяпоследнее число массива А, и регистр26 сдвига через группу элементов 31задержки, а регистр 30 сдвига черезблок 33, группу И элементов 35 игруппу элементов 36 задержки устанавливаются соответственно на началои конец массива А. На пятом тактевсе числа записываются через группыэлементов ИЛИ 58 в регистры 10.,13 тактовым сигналом с группы управляющих элементов ИЛИ 9. Числа записываются со сдвигом на один разрядвлево, и при перезаписи на второйвход блока 20 управления будет поступать значение второго разряда исходного числа. Адреса датчиков чиселзаписываются без изменений. ЭлементЗАПРЕТ 39.3 блока 20 управленияпредотвращает ложное срабатываниерегистра 26 и 30 сдвига на пятомтакте,На второй серии тактовых импульсов регистра 14 сдвига и группы элементов И 15 в регистры 2124 перезаписываются сначала массив А (с разбиением на две части А 1 и АО), а затем при окончании массива А массив В (с разбиением на В 1 и ВО). После определения опроса массива А, регистры 26 и 30, сдвига сбрасываются и устанавливаются соответственно на начало и конец массива В, Затем на пятом такте второй серии тактовых импульсов полученные массивы А 1, АО, В 1 и ВО снова записываются в регистры 1013, причем блок 28 памяти теперь помнит номера регистров, в которых хранятся последние числа массивов А, А 1 и В 1. На третьей серии тактовых импульсов каждый из имеющихся четырех массивов аналогично разбивается еще на две части. После прохождения каждого из массивов А 1, АО, В 1 и ВО регистры 26 и 30 сдвига устанавливаются соответственно на начало и конец следующего .массива.Конец очередного массива опреде.ляется элементами И 32 и ИЛИ 34. Выдается сигнал на очередные сброс и установку регистров 26 и 30 сдвига,При этом элемент 38 задержки черезэлемент ИЛИ 37 сбрасывает регистры26 и 30 сдвига. Сигнал с элементаИЛИ 34 разрешает установку регистра30 сдвига, и сигнал с блока 33 черезгруппы элементов И 35 и элементов 36задержки устанавливает его на конец массива. Регистр 26 сдвига уста навливается с помощью группы элементов 31 задержки. Сигнал с элемента ИЛИ 34 также поступает на тре,тий вход блока 20 управления и далеена элемент И 47.3. Так как на выходе 15 элемента ИЛИ 40. 1 в этот момент времени уровень "1,", пришедший сигналпоступает на элемент 43.3. задержки.По истечении времени задержки43.3,прямоугольный импульс переводит Т-триггер 46 в противоположное состояние, тем самым обеспечивая задержкупрямоугольных импульсов с генератора45 тактовых импульсов на время=0,5 Т, необходимое для установки регистров 26 и 30 сдвига. При этомвремена задержки групп элементов 31и 36 задержки и элемента 38 задержки с 31= 36 = 2с 38 = С 43.3 = ТНа (и+1)-м такте ш-й серии тактовых импульсов, что определяется счетчиком 41, единичный уровень на ш-мвыходе дешифратора 42 запрещает запись " 1" в регистре 14 сдвига через элемент ИЛИ 40,2 и останавливаетгенератор 45 тактовых импульсов поистечении времени задержки с 43.2элемента 43.2 задержки, причем с 43.2==0,5 Т. Тецерь во входных регистрах10-13. расположены числа в убывающемпорядке или в возрастающем при пос 4 о,ледовательном опросе регистров с 13по 10).з Блок 28 памяти служит для запоминания номеров регистров, в которыххранятся .последние числа получаемыхмассивов А, А 1, В 1 и т.д. Импульсы срегистра 26 сдвига поступают на КЯтриггеры 58.1- 58.3, поочередно переводя их в единичное состояние. КаждыйВ+1)-й триггер 58.1+1, переходяв единичное состояние, переводитЕ-й триггер 58.Е в исходное нулевоесостояние через элементы И 63.1 с иИЛИ 59,1.(п+1)-й импульс первой се рии тактовых импульсов, поступающийна пятый вход блока 28 памяти черезэлемент И 60.х устанавливает в единичное состояние тот П-триггер 61.х, 1241 28гдех может принять одно из значений от 1 до т., на Р-вход которого подана "1" с КБ-.триггера 58.х. "0" на инверсном выходе Р-триггера 61.хпредотвращает ложный сброс триггера 58.х при работе со следующим массивом на других тактовых сериях. Для предотвращения потери т 1" на выходе блока 28 памяти группа элементов ИЛИ 62 объединяет выходы соответствующих КБ- и Р-триггеров, (и+1)-е импульсы всех серий переводят триггеры 58 в исходное состояние через элемент 57 задержки и элемент ИЛИ 56. Через15 элемент ИЛИ 56 также осуществляется первоначальная установка блока 28 памяти в исходное состояние. На и-мтт тт выходе блока 28 памя ти всегда 1 т, е . ин формация о н омер е регистра , в котором хранится последнее число исходного массива , Триггер 5 8 , 3 переводится в нулевое состояние импульсом с последнего (и- г о ) выхода регистра 2 6 сдвига . Блок 33 опрецеления номера опера-, тивного регистра служит для определения номе 1 эа регистра, в котором хранится последнее число следующего массива, При этом, если на 3-м информационном входе " 1", она запрещает через элементы ЗАПРЕТ 54, И 55 и ИЛИ 52 прохождение остальных "1", на выходы блока 33 и разрешает прохождение 1 на 3 - й выход блока. 33тт тт 35 через элементы И 53 и И 49. Если на 1-и информационном входе ттОтт, он через элементы ЗАПРЕТ 54, ИЛИ 52, И 55 разрешает прохождение на выход блока 33 только следующей х-й 1 . Триггерн тт тт4 О 51 служит для запрещения появления "1" на 3 -м выходе блока 33 на остальных итактах данной серии тактовых импульсов. Таким образом, если на 1-м информационном входетт 45 она будет на 3-м выходе блока 33 до )-го такта, причем на остальных (1 - 1)-х выходах будут "О". На 1-м такте на инверсном выходе триггера 51,1 устанавливается "О", который поступает на элемент И.49.1, запрещая прохождение 1-й тт 1 т на выход и разрешая прохождение на выход .х-й " 1" определяемой концом следующего массива, Элемент ЗАПРЕТ 48.3 пред отвращает ложное срабатывание блока 33 в момент переключения триггера.51,3. Элемент НЕ 50 выполняет функцию триггера, если в массиве одночисло, занимающее первый регистр. Иа,и-м такте триггер 51 переводитсяв нулевое состояние и блок 33 выгает"1" на выходе, соответствующуюномеру последнего регистра старшегомассива.Формула изобретени я1. Устройство для упорядочивания чисел содержащее и групп входных элементов И, и входных регистров, и групп элементов И перезаписи, и групп элементов ИЛИ переписи, группу элементов ИЛИ, первую, вторую, третью . группы элементов И, блок памяти, первую группу элементов задержки и блок управления, включающий генератор тактовых импульсов, триггертт,счетчик, четыре элемента зацержки, первый элемент И, первый элемент ИЛИ, формищ рователь импульсов, причем вход запуска устройства соединен с входом формирователя импульсов блока управ, ления в блоке управления первый выход генератора тактовых импульсов соединен с первым входом первого элемента И причем входы упорядочцвэния чисел соединены с информац:энньтми входами соответствующих групп входных элементов И, выходы разрядов входных регистров подключены к информационным входам элементов И пере. записи соответствующих групп, о т л ич а ю щ е е с я тем, что, с цельюповышения быстродействия, в него, введены и оперативных регистров, элементы ИЛИ перезаписи, три регистра сдвига, четыре элемента ИЛИ, вторая группа элементов задержки, элемент задержки и блок определения номера оперативного регистра, в блок управ-. ления введены дешифратор, три элемента ЗАПРЕТ, второй элемент ИЛИ и второй, третий, четвертый элементы И, причем в блоке управЛения выходы счетчика соединены с входами дешифратора, ш-Й выход которого соединен с запрещающим входом первого элемента ЗАПРЕТ и через первый элемент задержки с входом останова генератора тактовых импульсов, второй выход которого соединен с первым входом второго элемента И, выходы первого и второго элементов И соединены с входами первого элемента ИЛИ, второй: вход первого элемента И сое 124 1228выход которого соединен с вхадмпервого разряда первого регистрасдвига, выходы которого соединен;.с информационными входами элпементавИ первой группы, выход 1 вэлемента И первой группы соединен с вторыми входами элементов И перезаписисоответствующей группы и с:1-и управляющим входом блока определения номера оперативного регистра, с первымвходам х-га элемента И второй группы элементов И, выход т-го элементаИ второй группы соединен с входом-га элемента задержки нервай группы и с -м входам третьего элемента ИЛИ, выход которого соединенс входом элемента задержки н с управляющими входами элементов И третьейгруппы а также с первым входом тре. -тьего элемента И блока управлениявторой вход третьего элемента И катарага соединен с выходам гервагаэлемента ИЛИ и с информационным входам второго элемента ЗАПРЕТ блокауправления, а также соединен с тактовым входом первого регистра сдвигаи с управляющими входами элементовИ первой группы, выход (и+1)-гоэлемента И первой группы соединенс вторым входом каждого элементаИЛИ группы, с (и+1)-и информационнымвходом блока памяти, с управляющимвходом второго элемента ЗАПРЕТ, сасчетным входом счетчика и с информационным входом первого элемента ЗАПРЕТ блока управления, выходы третьего элемента ЗАПРЕТ и четвертогоэлемента И блока управления соединены с тактовыми входами соответственно второго и третьего регистровсдвига, каждый -й выход блока определения номера оперативного регистрасоединен с информационным входом -гаэлемента И третьей группы, выход которого соединен с входом -га элемента задержки второй группы, выходЕ-га элемента задержки второй группы,где 1 = 1 псоединен с(п 1-1 с)-м информационным входом второго регистра сдвига, выход и-га элемент" задержки второй группы соецинен с вторым входом третьего элемента ИЛИ, выход которого соединен спервым информационным входом третьегорегистра сдвига, выход каждого-га элемента задержки первой группы соединен с(1 с+1)-м информационным входом третьего регистра сдвига, выход х-га элемендинен с прямым выходом триггера, инверсный выход которого соецинен свторым входом второго элемента И, асчетный вход через второй элемент5задержки - с выходом третьего элемента И, выход второго элемента ЗАПРЕТсоединен с информационными входамитретьего элемента ЗАПРЕТ и четвертого элемента И, выход первого элемента 1 ОЗАПРЕТ соединен с первым входом второго элемента ИЛИ, выход третьегоэлемента задержки соединен с входомзапуска генератора тактовых импульсов,выход формирователя импульсов соеЪдинен с входом четвертого элементазадержки, с входом установки в "Осчетчика и входами установки впервого регистра сдвига и блока памяти и первым входом первого элемента ИЛИ, выход которого соединен свходом установки в 0 второго итретьего регистров сдвига, 1-й выход,где 1 = 1 п, третьего регистрасдвига соединен с первым входом (и+1 --го элемента ИЛИ перезаписи соединен ссинхронизирующим входом 1 - го опе-ративного регистра, выход первого разряда 1 -го оперативного регистра сое- Одинен с первым входом щ-го элементаИЛИ )-й группы элементов ИЛИ переписи, где ) = 1щ; щ - число разрядов числа массива, Я+1) -й. разрядныйвыход -го оперативного регистрасоединен с первым входом 1-го эле 35-го элемента ИЛИ -й группы элементов ИЛИ перезаписи, выходы группэлементов ИЛИ переписи соединеныс информационными входами соответствующих входных регистров, выходывходных элементов Икаждой д-й группысоединены с вторыми входами элементов ИЛИ переписи соответствующей .группы, а управляющие входы входныхэлементов И каждой д-й группы соединены с первыми входами соответствующих элементов ИЛИ группы и с первыми входами второго и третьего эле.ментов ИЛИ и подключены к выходучетвертого элемента задержки блока 55управления, к входу третьего элемента задержки и к второму входу второ.га элемента ИЛИ блока управления, 1241228т задержки первой группы соединен с вторым входом второго элемента ИЛИ, выход которого соединен с входом первого разряда второго регистра сдвига, 1-й выход которого соединенвторым входом г.-го элемента ИЛИ перезаписи и с д.-м информационным входом блока памяти, каждый 1-й выход которого соединен.с вторым входом 10 д.-го элемента И второй группы и с ь-и информационным входом блока определения номера оперативного регист. ра выход элемента задержки соединен с вторым входом четвертого элемента ИЛИ, выход д.-го элемента ИЛИ группы соединен с тактовым входом соответствующего входного регистра выходы элементов И перезаписи каждой х-й группы соединены с инфориационньдми входами д.-го оперативного регистра, выход первого элемента И перезаписи кадддой группы соединен с управляющими входами соответственно третьего элемента ЗАПРЕТ и четвертого элемента И 25 блока управления.2. Устройство по п.1, о т л ич аю щ е е с я тем, что блок определения номера оперативного регистра содержит первую группу из п элементов И, группу КБ-триггеров 1 элемент НЕ, вторую и третью группы по пэлементов И, первуб группу из п элемеддтов 11 ЗАПРЕТ 1 группу элементов ИЛИ, вторую группу из пэлементов ЗАП 35 РЕТ, причем х-и информационныи вход блока определения номера оперативного регистра соединен с информационным входом д.-го элемента ЗАПРЕТ первой группы, выход которого соединен с4 О первым входом д.-го элемента И первой группы, выход которого является д.-м выходом блока определения номера оперативного регистра, д-й управляющий вход блока определения номера опера 5 тивного регистра соединен с управляющим входом 1.-го элемента ЗАПРЕТ первой11 11 группы и входом установки в 1 К-го дБ- триг г ер а группы , прямой выход котор о го соединен с первым входом д- го элемента ИЛИ группы, выход 1;- г о элемента ИЛИ ( 8= 1 1 2 1 . . . , и ) соединен с информационным входом К-го элеме нт а ЗАПРЕТ второй группы и с первым входом Г- г о элемента И второй группы , выход которого соединен с вторым 55 входом ( г+ 1 ) - г о элемента И первой группы, и-и управляющий вход блока определения номера оперативного регистра соединен с управляющим входом и-го элемента ЗАПРЕТ первой группы, и с входами установки в "О" всех триггеров группы, выход (и)-го элемента ИЛИ группы соединен с вторым входом и-го элемента И первой группы, инверсный выход первого дБ-триггера группы соединен с вторым входом первого элемента И первой группы, выход г-го элемента ЗАПРЕТ первой группы где г-.- .2, ,п, соединен с вторым входом (г)-го элемента И второй группы и с управляющим входом (г)- го элемента ЗАПРЕТ второй группы, выходы которых соединены с первым входом (г)-го элемента И третьей группы, выход которого соединен с вторым входом (г)-го элемента ИЛИ группы, а второй вход подключен к инверсному выходу г;го КБ-триггера группы и к третьему входу г-го элемента И третьей группы, выход первого элемента. ЗАПРЕТ первой группы через элемент НЕ подключен к второму входу первого элемента ИЛИ группы.3. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок памяти содержит группу КБ-триггеров, две группы элементов ИЛИ; группу 0-триггеров, две группы элементов И, элемент задержки, элемент ИЛИ, причем 1 с-й информационный вход блока памяти соединен с входом установки в "1" 1 Б-триггера группы, прямой выход которого соединен с первым входом 1-го элемента И первой группы,син хровходом 1-го 0-триггера и первым входом Ы-го элемента ИЛИ первой группы, выход которого является Е-м информационным выходом блока памяти, вход установки в "О" блока памяти подкгдючен к первому входу. элемента ИЛИ, первым входам элементов ИЛИ второй группы, входу установки в "1" и-го КБ-триггера группы, выход котодрого является и-м выходом блока памя.ти 1 выход д Го элемента ИЛИ второй .группы подключен к входу установки в "О" 1-го КБ в тригге группы (и + +1) -й вход блока памяти соединен с вторыми входами элементов И .первой группы и через элемент задержки соединен с вторым входом элемента ИЛИ, выходЕ-го элемента И первой группы соединен с информационным входом к-го0- триггера группы, прямой выход которого подключен к второму входу элемента ИЛИ первой группы, а инвер-;12 1241228 г.1 0 из сный выход соединен с первым входомК"го элемента И второй группы, выход которого подключен к второму входу К-го элемента ИЛИ второй группы,прямой выход г-го КБ-триггера группы соединен с вторым входом Ь)-гоэлемента И второй группы, второй зход; Редактор А.Огар Техред К,Бонкало 1(оррек А,Зимокосов Заказ 3489 д. 4 ушска зводственно-полиграфическое предприятие, г.ужгород,ул.Проектная,4 Тираж 671 ВНИИПИ Государственн по делам изобретени 13035, Москва, Ж,Подписи о комитета ССС и открытий