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

СОЮЗ СОЕКСОЦИАЛРЕСПУБЛ ТСН СНИ 04 С 06 Р 7/ ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕпО изОБРетениям и ОтнРмтпРи пют сссР ОПИСАНИЕ ИЗОБРЕТЕНК А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ 54) УСТРОЙСТВО ДЛЯ У 110 РЯПОЧЕНИЯ ХАИВА ЧИСЕЛ обретение отно вычислительной тик иэо ьство СССР/06 ф 1983тво СССР /06, 1984. ени овьпюени ия ал Устроист 1 и конц содержи эонь,оны, эл.07.89, Бюл. ВГ,Водяницкий1.325.5(088.8)торское свидете18, кл. С 06 Ррское свидетель27, кл, С 06 Г ится к автомаехнике. Цельбыстродейстт регистры насчетчики начаемент 5 срав1494001 цени), регистры 6, 7, 8, мультиплексоры 9, 10, триггеры 11, 12, 13,элементы И 14, 15, 16, 17 18, 19, 20, элементы И.Е 21, 22, 23, 24, 25, элементы задержки 26, 27, группы элемен 5 тон И 28, 29, 30, 31, 32, 33, 34, 35, группы элементов ИЛИ 36, 37, тактовьй нход 38, вход запуска 39, информационные входы 40, адресные выходы 41, информационные выходы 42, выходы разрешения считывания 43 и записи 44, выход окончания работы устройства 45. Упорядочение заключается в том, что все числа, в заданном разряде которых 5 Изобретение относится к автоматике и вычислительной технике и можетбыть использовано при реализации технических средств ЭВИ.Цель изобретения - понышение быстродействия устройства, 25На чертеже изображена схема предлагаемого устройства.Устройство содержит регистры 1 и 2начала и конца зоны соответственно,счетчики Э и 4 начала и конца эоны 30соответственно, элемент 5 сраннения,регистры 6-8, мультиплексоры 9 и 10,триггеры 11 - 13, элементы И 14-20,элементы ИЛИ 21-25, элементы 26 и 27задержки, группы элементов И 28-35)группы элементов ИЛИ 36 и Э 7, тактовый вход 38, вход 39 запуска, информационные входы (шины) 40, адресныевыходы (шины) 41, информационные выходы 42, выходы (шины) 43 и 44 раэрешения считывания и записи соответственно и выход 45 окончания работыустройства,Устройство работает следующим образом. 45В исходном состоянии в регистре 1записан адрес начала зоны, в регистре 2 - адрес конца зоны массива чисел,записанного в запоминающем устройстве (ЗУ) общего назначения, которыйнадо упорядочить, В регистре 8 записан номер двоичного разряда числа,по которому необходимо выполнитьупорядочение. Упорядочение заключается н том, что все числа, в выбранном разряде которых - нуль, перемещаются н ЗУ в начало зоны, а все числа, н выбранном разряде.которыхединица, перемещаются в конец зоны,нуль, перемещаются во внешнем ЗУ,внаЧало зоны, а все числа, в заданномразряде которых - единица, перемещаются н конец эоны. Числа последовательно считываются от начала зоны кконцу, пока не будет считано число с единицей в заданном разряде, и последовательно считываются от конца эоны к началу, пока не будет считано число с нулем в заданном разряде, Затем считанные числа записываются в ЗУ одно на место другого и процесс повторяется, пока не будут обработаны все числа, 1 ил. Триггеры 1-13 находятся в нулевомсостоянии. При поступлении сигналапо входу 39 запуска содержимое регистра 1 переписывается через элементыИ группы 28 в счетчик 3, а содержимое регистра 2 через элементы И группы 29 - в счетчик 4,Первый тактовый импульс, поступивпо входу 38 и пройдя через элементыИ 15 и ИЛИ 24, возбуждает шину 43разрешения считынания, а также, пройдя через элемент ИЛИ 21, разрешаетпоступление через элементы И группы30 и элементы ИЛИ группы 36 адресаначала зоны иэ счетчика 3 на выходные адресные шины 41 устройства. Сигналы по этим выходам поступают в ЗУ,в котором происходит считывание числа,записанного по данному адресу(т.е. первого числа массива), котороепоступает из ЗУ на входные информационные шины 40 устройства и через элементы И группы 34 записывается врегистр 6 и поступает на входы мультиплексора 9, который осуществляетвыборку из числа двоичного разряда,номер которого записан в регистре 8,При равенстве проверяемого разрядачисла нули появляется сигнал на инверсном выходе мультиплексора 9, который через элемент ИЛИ 23 поступаетна счетньй вход счетчика 3, увеличивая его содержимое на единицу, т,е.в счетчике записывается адрес следующего числаСодержимое счетчикон 3 и4 сравнивается элементом 5 сравнения,и при их равенстве на выходе 45 появляется сигнал, сигналиэирующий обокончании работы устройства, Этотсш вал поступает также на инверсньйвход элемента И 14, закрывая его и запрещая тем самым поступление тактовых импульсов в устройство. В противном случае цикл работы устройст 5 ва повторяется, Если проверяемыйразряд числа - единица, то появляется сигнал на прямом выходе мультиплексора 9, который переключает триггер 11 в единичное состояние, переводя 10 устройство из режима считывания по начальному адресу в режим считывания по конечному адресу, Очередной тактовый импульс через элементы И 14, 1 Ь и 20 и ИЛИ 24 возлуждает шину 4315 разрешения считывания и разрешает поступление через элементы И группы 31 и элементы ИЛИ группы 36 адреса конца зоны из счетчика 4 на выходные адресные шины 41 устройства, а 20 также разрешает запись последнего числа массива из ЗУ через элементы И группы 35 в регистр 7, При равенстве заданного разряда числа единице появляется сигнал на прямом выходе 25 мультиплексора 10, который поступает через элемент ИЛИ 25 на счетный выход вычитающего счетчика 4 т,е. в счетчике будет записан адрес предпоследнего числа массива сортируемых чисел, 30 При поступлении следующих тактовых импульсов цикл работы устройстваповторяется, пока на инверсном выходе мультиплексора 10 не появится единичный сигнал, который переведет триггер 13 в единичное состояние, переключив тем самым устройство в режим записи по конечному адресу. Далее происходит запись числа с единичным заданным разрядом из регистра 6 в ЗУ по 40 только что считанному адресу, по которому находилось число с нулевым выбранным разрядом, Очередной тактовый импульс через элементы И 16 и 19 возбуждает шину 44 записи и через эле менты И 18 и ИЛИ 22 разрешает поступление адреса из счетчика 4 на выходные адресные шины 41 устройства, а из регистра о - на инФормационные выходы 42 устройства, а также переводит триггер 12 в единичное состояние, разрешая тем самым прохождение сигнала через элемент И 17 и переключая тем самым устройство в режим записи по адресу, задаваемому счетчиком 3При поступлении очередного тактового импульса устройство работает аналогично, выводя число в ЗУ из регистрапо адресу, задаваемому счетчиком 3, а также переводит, триггеры 11-13 в в нулевое состояние, переключая тем самым устройство в режим считывания числа по адресу, заявляемому счетчиком 3. Этот же импульс, задержанный элементом 26 задержки на время записи числа в ЗУ поступает через элемент ИЛИ 25 на вход счетчика 4, уменьшая его значение на единицу, и, задержанный элементом 27 задержки на время работы элемента ИЛИ 25, счетчика 3 и элемента 5 сравнения, поступает через элемент ИЛИ 23 на вход счетчика 3, увеличивая его содержимое на единицу, Далее цикл работы устройства повторяется с приходом очередного тактового импульса.Формула изобретенияУстройство для упорядочениямассива чисел, содержащее регистры начала и концы эоны, счетчики начала и конца зоны, элемент сравнения, первый и второй регистры, первый и второй триггеры, семь групп элемен- . тов И, две группы элементов ИЛИ, семь элементов И, четыре элемента ИЛИ и дна элемента задержки, причем выход 1-го разряда регистра начала эоны, где 1=1,2п; п - количество разрядов адреса чисел массива, соединен с первым входом 1-го элемента И первой группы, вторые входы которых подключены к входу запуска устройства, выходы 1-х элементов Г первой и второй групп соединены с 1-ми информационными входами счетчиков соответственно начала и конца зоны, выходы 1-х разрядов которых соединены с 1.-ми разрядами соответственно первой и второй групп инФормационных входов элемента сравнения и с первыми входами 1-х элементов И соответственно третьей и четвертой групп, выходы которых соединены соответственнО с первым и вторим входами 1.-го элемента ИЛИ первой группы, выход которого является выходом 1-го разряда адреса устройства, выход элемента сравнения является выходом окончания работы устройства и соединен с инверсным входом первого элемента И, прямой вход которого подключен к тактовому входу устройства, а выход соединен с первыми входами второго и третьего элементов И, вторые входы которых подключены соответственно к инверсно1494001 Корректор З,Лончакова Заказ 4111/45 Тираж 668 Подписное Ф ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб д. 4/5 лПроизводственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 му и прямому выходам первого триггера, вход установки в нулевое состояние которого объединен с входом установки в нулевое состояние второго триггера, прямой и инверсный выходы которого соединены с первыми входами соответственно четвертого и пятого элементов И, выходы которых соедине" ны с первыми входами соответственно первого,и второго элементов ИЛИ, а также с первыми входами элементов Е пятой и шестой групп, выход 3-го элемента И седьмой группы, где 3=1,2, ,ш, ш - количество разрядов чисел 15 массива, соединен с -м информационным входом первого регистра, выходы 1-х разрядов первого и второго регистров соединены с вто- . рыми входами 3-х элементов И соответ ственно шестой и пятой групп, выходы которых соединены соответственно с первым и вторым входами 3 -го элемента ИЛИ второй группы, выход которого является 3 -м информационным выходом устройства, выход четвертого элемента И соединен с входом первого элемента задержки, выход второго элемента задержки соединен с первым входом третьего элемента ИЛИ, вторые входы четвертого и пятого элементов И объединены первый вход шестого элемента И объединен с первым входом седьмого элемента И, выход которого соединен с первым входом четвертого элемента ИЛИ, выход второго элемента ЕЛИ35 соединен с вторыми входами элементов И четвертой группы, первые входы элементов И второй группы объединены, вторые входы элементов И третьей40 группы объединены, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия,.в него введены третий регистр, два мультиплексора, восьмая группа элементов И, третий триггер и пятый элемент ИЛИ, причем выход 1.-го разряда регистра конца эоны соединен с вторым входом -го элемента И второй группы, первый вход50 которого подключен к входу запуска устройства, выходы второго и третьеСоставитель В.ГороховРедактор А,Ревин Техред Л,Сердюкова го элементов И соединены с вторымивходами соответственно первого и второго элементов ИЛИ, а также с первыми входами элементов И соответственно седьмой и восьмой групп, 3-й информационный вход устройства соединен с вторыми входами 3 -го элементаИ седьмой группы и 3-го элемента Ивосьмой группы, выход которого соединен с 3 -м информационным входомвторого регистра, выходы 3 -х разря-.дов первого и второго регистров соединены с 3-ми информационными входамипервого и второго мультиплексоров соответственно, прямой и инверсный выходы которых соединены с входами установки в единичное состояние соответственно первого и третьего триггеров,входы установки в нулевое состояниекоторых подключены к выходу четвертого элемента И, выход первого элемента задержки соединен с входом второго элемента задержки и первым входомпятого элемента ИЛИ, выходы третьегорегистра соединены с управляющимивходами первого и второго мультиплексоров соответственно, инверсныйи прямой выходы которых соединены свторыми входами соответственно третьего и пятого элементов ИЛИ, выходыкоторых соединены соответственно с суммирующим входом счетчика началазоны и вычитающим входом счетчикаконца зоны, выход второго элементаИ соединен с вторым входом четвертого элемента ИЛИ, выход которого является выходом разрешения считыванияустройства, выход третьего элементаИ соединен с первым входом шестогоэлемента,И, выход которого являетсявыходам разрешения записи устройства н соединен с вторым входом пятогоэлемента И, выход которого соединенс входом установки в единичное состояние второго триггера, выход пер"вого элеменза ИЛИ соединен с вторьйчивходами элементов И третьей группы,прямой и инверсный выходы третьего триггера соединены с вторыми входами соот -ветс твенно шестого и седьмого элементов И,