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

Номер патента: 1425652

Авторы: Крылов, Полищук, Шубина

ZIP архив

Текст

(51)4 С Об Р 7 ПИСАНИЕ ИЗОБРЕТЕНИ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ регистре 1. Для из Н чисел разм ной зоне предлаг зоны, записанного сортировки массива щение чисел в зада емым устройством о ко в конце каждого ется тол авнения. ущест цикла СУДАРСТНЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(56) Авторское свидетельство СССР Р 981988, кл, 6 06 Р 7/06, 1980.Авторское свидетельство СССР У 1234827, кл. С 06 Р 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ МАССИВА ЧИСЕЛ(57) Изобретение может быть использовано в .области вычислительной техники. Цель изобретения " повышение быстродействия устройства. Устройство содержит регистры 1-5, счетчики6,7, схемы сравнения 8-10, триггеры11-14, элемент запрета 15, группыэлементов И переписи 16-20, группывыходных элементов И 21-25, группыэлементов ИЛИ 26,27, элементы И 2838, элементы ИЛИ 39-42, формирователь импульсов 43, элементы задержки44-48. Устройство выполняет упорядочение чисел, начиная с адреса началаИзобретение относится к автоматикеи вычислительной технике и можетбыть использовано при реализации технических средств ЭВМ,Целью изобретения является повы"шение быстродействия устройства.На чертеже представлена схема устройства.Устройство содержит регистры 1 - 5,счетчики 6 и 7, схемы 8-10 сравнения,триггеры 11-14, элемент 15 запрета,группы 16-20 элементов И переписи,группы 21-25 выходных элементов И,группы элементов ИЛИ 26 и 27, элементы И 28"38, элементы ИЛИ 39-42, фор"иронатель 43 импульсов, элементы4-48 задержки, информационные вхоы 49, вход 50 запуска, вход 51 таконых импульсов, информационные выхсы 52, выход 53 окончания работы,20ыходы 54 разрешения считывания,аписи 55, адресные выходы 56,В качестве формирователя 43 имульсов может использоваться извест"ая. схема мультинибратора, котораятозволяет сформировать управляющийигнал при каждом изменении состоянияхемы сравнения.Устройство работает следующим образом. 30В исходном состоянии в регистре 1аписан адрес начала зовы, а-в регистре 2 - адрес конца эоны массивачисел, записанного в запоминающемустройстве (ЗУ) общегО назначения,который требуется упорядочить, В рефгистрах 3 и 4 записано минимальноемашинное число, счетчики 6 и 7,триггеры 11-14 находятся в нулевомс 1 остоянии. Так как содержимое регис 1 тров 3 и 4 равно, то на первом выХоде схемы 10 сравнения имеется едиНичный сигнал, который подтверждаетустановку триггера 11 в нулевое состояние, и, следовательно, открыты 45элементы И группы 19. При поступлении сигнала запуска на вход 50 содержимое регистра 1 переписывается черезэлементы И группы 18 н счетчик 6,а затем через время задержки, опредееляемое элементом 44 задержки, переписывается через элементы И группы 16в счетчик 7. Содержимое счетчиков би 7 сравнивается схемами 8 и 9 с содержимым регистра 2. Так как содержимое счетчиков 6 и 7 меньше, то навыходах схем 8 и 9 сравнения имеетсянулевой сигнал и, следовательно, элемент 15 запрета открыт. Тактовый им" пульс с входа 51 через открытые элементы 15 запрета и И 29 поступает на выход 54 разрешения считывания (из ЗУ) и через элемент И 30 на входы элементов И группы 23, в, результате чего на выходах 56 устройства сформирован адрес первого числа через элементы И группы 23 и элементы ИЛИ группы 27 и из ЗУ считано первое число, которое поступает, на входы 49 устройства и далее через элементы И группы 19 в регистр 3.Схема 10 сравнения и триггер 11 меняют свое состояние, так как со" держимое регистра 3 больше, чем содержимое регистра 4, а формировательо 43 вырабатывает импульс, по которому из счетчика 7 через элементы И группы 17 в регистр 5 записывается адрес первого числа. Затем .этим же такто" вым импульсом, задержанным на элементе 45 задержки на время переходных процессов, содержимое счетчика оувеличивается на единицу. При поступлении нторого тактового импульса на вход 51 из ЗУ считывается второе число по адресу счетчика 7, описанным вьппе способом, Поступающее на входы 49 второе число записывается н ре" гистр 4 через открытые элементы И групп 20, так как триггер 11 находится в единичном состоянии. Если поступившее второе число, записанное в регистре 4, больше или равно первому числу, записанному в регистре 3, то схема 10 сравнения и триггер 11 меняют свое состояние, подготавливая запись очередного числа в регистр 3, а формирователь 43 вырабатывает импульс, по которому адрес нторого (очередного) числа записывается в регистр 5. При поступлении очередного тактового импульса очередное число считывается из ЗУ и записывается в тот из регистров 3 или 4, где записано меньшее число. Если при этом соотношение чисел, записанных в регистрах 3 и 4, меняется, то формирователь 43 вырабатывает сигнал, по которому в регистр 5 через элементы И группы 17 записывается содержимое счетчика 7. Таким образом, в одном из регистров 3 или 4 записано максимальное число, а в регистре 5 - его адрес, Работа устройства продолжается аналогично до тех пор пока содержимое счетчика 7 не превышает значение адреса конца зоны, записанного в регистре 2. Как только н счетчике7 будет значение, превышающее значение адреса конца зоны, схема 9 сравнения вырабатывает сигнал, который устанавливает триггер 12 в единичное состояние, и очередной тактовый импульс поступает на выход 54 и через элементы И 31 и ИЛИ 40 на входы элементов И группы 24, в результате чего по первому адресу считывается первое число в один из регистров 3 или 4. Таким образом, в одном из регистров 3 или 4 записано максимальное, а в другом - первое число. Затем этим же тактовым импульсом, за" держанным в элементе 46 задержки на время переходных процессов триггер 13 устанавливается в единичное состояние.При поступлении очередного тактового импульса максимальное число из регистра 3 или 4 соответственно через элементы И группы 21 или И группы 22 записывается в ЗУ по адресу счетчика 6, а при поступлении следующего тактового импульса первое число иэ регистра 4 или 3 соответственно через элементы И группы 22 или И группы 21 записывается в ЗУ по адресу максимального числа следующим образом.Очередной тактовый импульс, пройдя открытые элементы И 32, И 33, И 35 или И 36, ИЛИ 41 или ИЛИ 42, открывает элементы И группы 21 или И группы 22 в зависимости от состояния триггера 11, который находится в единичном состоянии, если в регистре 3 записано большее,чем в регистре 4, число, и в нулевом - в противном случае, и максимальное число из регистра 3 или 4 через элементы И группы 21 или И группы 22 и элементы ИЛИ группы 26 поступает на выход 52 устройства Этим же тактовым импульсом открываются элементы И группы 24 и по адресу, находящемуся в счетчике 6, в ЗУ записывается максимальное число. Этот же импульс, задержанный элементом 47 задержки на время переходных процессов, устанавливает триггер 14 в единичное состояние. Следующий тактовый импульс, пройдя элементы И 32, И 34, И 38 или И 37, ИЛИ 42 или ИЛИ 41, открывает элементы И группы 22 или И группы 21, и меньшее число, которое ранее записано в регистре 4 или 3 через элементы И группы 22 или И группы 21 и элементы ИЛИ,группы 26, поступает на выход 52 устройства. По этому же тактовому импульсу на выходы56 через элементы И группы 25 и ИЛИгруппы 27 поступает адрес, по которому в ЗУ записано максимальное число,5и число из регистра 4 или 3 записывается по этому адресу, Этот же импульс, задержанный в элементе 48задержки на время переходных процессов, устанавливает счетчик 6 в очередное состояние, а регистры 3 - 5,триггеры 12 - 14 - в исходное (нулевое) состояние, а далее по этому жеимпульсу, задержанному в элементе 44задержки на время переходных процессов,содержимое счетчика 6 через элементы И группы 16 переписывается всчетчик 7.Работа устройства продолжаетсяописанным вьппе способом до тех пор,пока содержимое счетчика 6 не станетравным содержимому регистра 2. Кактолько они сравняются, схема 8 сравнения вырабатывает сигнал, которыйзакрывает элемент 15 запрета и поступает на выход 53, сигнализируя обокончании сортировки,П р и м е р, Пусть в ЗУ записанмассив чисел, который необходимоупорядочить:адрес 1 2 3 4 5Число 13 11 12 14 15 Из ЗУ в устройство последовательносчитываются числа из упорядочиваемого35массива и устройство работает следующим образом,Первый цикл сравнения:1-й такт - считывается (в регистр3) первое число (13) и запоминается40(в схеме 10 сравнения) с первым числом (13) и запоминается максимальное45 из двух чисел (13 в регистре 3) иего адрес (1 в регистре 5),3-й такт - считывается (в регистр4) третье число (12), сравнивается(в схеме 10 сравнения) с максимальным50 из двух чисел (13 в регистре 3) и запоминаеъся максимальное иэ трех чисел (13 в регистре 3) и его адрес ( 1в регистре 5),4-й такт - считывается (в регистр55 4) четвертое число (14), сравнивается (в схеме сравнения 10) с максимальным из трех чисел (13 в регистре 3) Ы запоминается максимальное из(в схеме 10 сравнения) с максимальным из четырех чисел (14 в регистре4) и запоминается максимальное изпяти чисел (15 в регистре 3) и егоадрес (5 в регистре 5),6-8"й такты - после сравнениявсех чисел массива происходит перезапись в ЗУ: по адресу максимальногочисла (5) записывается первое число(13), а по адресу первого числа (1), аксимальное число (15), т.е. после1-го цикла сравнения в ЗУ имеетсяследующая последовательность чиселАдрес 1 2 3 4 5Число 15 11 2 14 13торой цикл сравнения:1-й такт - считывается (в регистр) третье число (12), сравниваетсяв схеме 10 сравнения) с вторым чис,ом (11) и запоминается максимальноез двух чисел (12 в регистре 4) и егодрес (3 в регистре 5),3-й такт - считывается (в регистр30) четвертое число (14), сравниваетсяв схеме 10 сравнения) с максимальнымиз двух чисел (12 в регистре 4) изапоминается максимальное иэ трех чисел (14 в регистре 3) и его адрес 35(в схеме 10 сравнения) с максимальнымЙз трех чисел (14 в регистре 3) и эапоминается максимальное иэ четырехчисел (14 в регистре 3) и его адрес(4 в регистре 5),5-7-й такт - после сравнения всехчисел массива происходит перезапись 45чисел в ЗУ: по адресу максимальногочисла (4) записывается второе число, а по адресу второго числа (2)максимальное число (14), т.е. послевторого цикла сравнения в ЗУ имеется 50следующая последовательность чисел:Адрес 1 2 3 4 5Число 15 14 12 11 13 20 Далее аналогично выполняются третий и четвертый циклы сравнения, сравнение в которых начинается соответственно с третьего и четвертого чисел . После третьего цикла сравне 6ния (6 тактов) в ЗУ имеется следующая последовательность чисел:Адрес 1,2 34 5Число 15 14 13 11 12После четвертого цикла сравнения (пять тактов) в ЗУ имеется упорядоченный (в порядке убывания) массив чисел:Адрес 1 2 3 4 5Число 15 14 13 12 11Таким образом, на упорядочение данного массива чисел в.предлагаемом устройстве требуется 26 тактов, а перезапись чисел в ЗУ осуществляется эа три такта работы устройства.Для упорядочения данного массива чисел в известном устройстве требуется 30 тактов, а перезапись чисел в ЗУ осуществляется за два такта работы устройства, так как известное устройство работает по следующему алгоритму:Первый цикл сравнения: 1-й такт - из ЗУ считывается первое число (13),2-й такт - из ЗУ считывается второе число (11), так как оно меньшепервого (13), то перезапись чисел вЗУ не происходит,3-й такт - из ЗУ считываетсятретье число (12), так как оно меньше первого (13), то перезапись чиселв ЗУ не происходит,4-й такт - из ЗУ считывается четвертое число (14), так как оно больше первого числа (13), то происходитперезапись чисел в ЗУ;5 и 6-й такты - в ЗУ на место первого числа (13) записывается четвертое число (4), а на место четвертогочисла (14) - первое число (13), большее число (14) запоминается в устройстве и последующие числа теперьсравниваются с этим чисЪом,7-й такт - из ЗУ считывается пятоечисло (15), так как оно больше первого числа (14), то происходит перезапись в ЗУ,8 и 9-й такты - в ЗУ на место пер"вого числа (14) записывается пятоечисло (15), а на место пятого числа(15) - первое число (14) .Таким образом, после сравнениявсех чисел массива (первого цикласравнения) в ЗУ записана следующаяпоследовательность чисел:Адрес 1 2 3 4 5Число 15 11 12 13 141425652 50 55 1Второй цикл сравнения: 1-й такт - из ЗУ считывается второе число (11) и сравнение выполняется аналогично описанному 1-му циклу сравнения.После второго цикла сравнения (десять тактов) в ЗУ имеется следующая последовательность чисел:Адрес 1 2 3 4 5 Число 15 14 11 12 13 Далее аналогично выполняются третий ичетвертый циклы сравнения, сравнение в которых начинается соответственно с третьего и четвертого чисел. После третьего цикла сравнения (семь тактов) в ЗУ имеется следующая последовательность чисел:Адрес 1 2 3 4 5 Число 15 14 13 11 12 После четвертого цикла сравнения (четыре такта) в ЗУ имеется упорядоченный (в порядке убывания) массив чисел:1АдресЧисло 1 2 3 4 515 14 13 12 11 Формула изобретения Устройство для упорядочения массива чисел, содержащее четыре регистра, два счетчика, три схемы сравнения, три группы элементов И переписа, че" ,тыре группы выходных элементовИ, 1две группы выходных элементов ИЛИ, два триггера, семь элементов И, четыре элемента ИЛИ, четыре элемента задержки, элемент запрета, причем вход тактовых импульсов. устройства подключен к прямому входу элемента запрета, выход которого соединен с первыми входами первого и второго элементов И, вторые входы которых соединены соответственно с прямым и инверсным выходами первого триггера, выход первого элемента И является выходом разрешения считывания устройства,.выход второго элемента И подключен к первым входам третьего и четвертого элементов И, вторые входы которых соединены .соответственно с прямым и инверсным выходами второго триггера, входы установки в "О" первого и второго триггеров соединены с выходом первого элемента задержки, выходы разрядов первого и второго регистров подключены к входам соответственно первой и второй групп первой схемы сравнения и первым входам соответствующих вы 8кодных элементов И соответственно первой и второй групп, выходы которых подключены соответственно к первым и вторым входам соответствующих выходных элементов ИЛИ первой группы, выходы которых являются информационными выходами устройства, вход запуска устроиства подключен к первым входам первого элемента ИЛИ и элементов И переписи первой группы, вторые входы которых подключены к выходам соответствующих разрядов третьего регистра, а выходы соединены с соответствующими информационными входами первого счетчика, выходы разрядов которого подключены к входам первой группы второй схемы сравнения, первым входам соответствующих выходных элементов И третьей группы и первым входам соответствующих элементов И переписи второй группы, вторые входы которых подключены через второй элемент задержки к выходу первого элемента ИЛИ, а выходы соединены с соответствующими информационными входами второго счетчика, выходы разрядов которого соединены с первыми входами соответствующих выходных элементов И четвертой группы и с входами первой группы третьей схемы сравнения, входы второй группы которой соединены с выходами соответствующих разрядов четвертого регистра и входами второй группы второй схемы сравнения, выход которой является выходом окончания работы устройства и подключен к инверсному входу элемента запрета, выходы выходных элементов И третьей и четвертой групп соединены с первыми и вторыми входами выходных элементов ИЛИ второй группы, выходы которых являются адресными выходами устройст" ва, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродейст" 5 1 О 15 20 25 ЗО 35 40 вия, в устройство введены пятый регистр, четвертая и пятая группы элементов И переписи, пятая группа выходных элементов И, третий и четвертый триггеры, восьмой, девятый, десятый и одиннадцатый элементы И,формирователь импульсов и пятый элемент задержки, причем информационныевходы устройства подключены к первымвходам соответствующих элементов Ипереписи четвертой и пятой групп,выходы которых соединены с соответствующими информационными входами соответственно первого и второго регистров, входы установки в "О" которых.Шекм 47 О/46 Тираж 704 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, РаушПодписномитета СССР Зак открытийая наб., д. 4/ оизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 соединены со счетным входом первого счетчика, вторым входом первого элемента ИЛИ, выходом первого элемента задержки, входами установки,в "О третьего триггера и пятого регистра,5 информационные входы которого подключены к выходам соответствующих элементов И переписи третьей группы, а выходы соединены с первыми входами соответствующих выходных элементов И пятой группы, выходы которых подключены к третьим входам соответствующих выходных элементов ИЛИ второй группы, выход первого элемента И подключен к первым входам пятого и шестого элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам третье го триггера, вход установки,в еди ичное состояние которого соединенвыходом третьей схемы сравнения, ыход пятого элемента И подключен вторым входам выходных элементов четвертой группы и через третий лемент задержки к счетному входу торого счетчика, выходы разрядов оторого подключены к первым входам оответствующих элементов И перепии третьей группы, вторые входы ко 30 торых подключены к выходу седьмого лемента И, первый вход которого соединен с инверсным выходом третьего триггера, а второй вход подключен к выходу формирователя импульсов, первый вход которого соединен с инерсным выходом четвертого триггера, Первыми входами восьмого и девятого элементов И и вторыми входами элементов И переписи четвертой группы,второй вход формирователя импульсовсоединен с первыми входами десятогои одиннадцатого элементов И, вторымивходами элементов И переписи пятойгруппы и прямым выходом четвертоготриггера, вход установки в единичноесостояние которого подключен к выходу"Меньше" первой схемы сравнения,выход "Больше", равно" которой подключен к входу установки в "0" чет"вертого триггера, выход шестого элемента И соединен с первым входомвторого элемента ИЛИ и через четвертый элемент задержки с входом установки в единичное состояние первоготриггера, выход второго элемента ИЛИподключен к вторым входам выходныхэлементов И третьей группы, а второйвход соединен с выходом четвертогоэлемента И и вторыми входами девятогои.десятого элементов И, выходы которых подключены к первым входам соответственно третьего и четвертого элементов ИЛИ, выходы которых подключенык вторым входам выходных элементов Исоответственно второй и первой групп,а вторые входы соединены с выходамисоответственно одиннадцатого и восьмого элементов И, вторые входы которых соединены с входом первого элемента задержки, вторыми входами выходных элементов И пятой группы ивыходом третьего элемента И, выходвторого элемента И является выходомразрешения. записи устройства и черезпятый элемент задержки подключен квходу установки в единичное состоя"ние второго триггера.

Смотреть

Заявка

4063507, 30.04.1986

ВОЙСКОВАЯ ЧАСТЬ 25840

КРЫЛОВ НИКОЛАЙ ИВАНОВИЧ, ПОЛИЩУК ВИКТОР МИХАЙЛОВИЧ, ШУБИНА НАТАЛЬЯ НИКОЛАЕВНА

МПК / Метки

МПК: G06F 7/06

Метки: массива, упорядочения, чисел

Опубликовано: 23.09.1988

Код ссылки

<a href="https://patents.su/6-1425652-ustrojjstvo-dlya-uporyadocheniya-massiva-chisel.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для упорядочения массива чисел</a>

Похожие патенты