Устройство для сортировки информации

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН С 51) 4 С 06 Р 7/06 8. 1".,13398 ПАТГ. ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССР В 1183956, кл. С 06 Р 7/06, 1984.Авторское свидетельство СССР У 1277092, кл. С 06 Г 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ(57) Изобретение относится к вычислительной технике и может быть использовано в качестве устройства сортировки чисел в системах обработки информации. Цель изобретения - повышение надежности устройства эа счет воэможности определения отказов блока памяти типа "константа 1 . или 0". Устройство содержит блок памяти 1, счетчик 2, информационные 801478210 А 1 входы 3 и выходы 4, реверсивный счет;чик 5, элементы ИЛИ 6,7,8,9,10, элементы И 11, 12,13,14,15,16,17, 18, элементы НЕ 19,20, генератор импульсов21, элемент задержки 22, элементыИСКЛЮЧАЮЩЕЕ ИЛИ 23,24, регистр 25,дешифратор 26, формирователи импульса 27,28, вход управления записью29, вход синхронизации 30, входы задания режима 31, вход "Сброс" 32,выход синхронизации 33, выход "Сбой"34, выход "Конец считывания" 35, выход "Конец очистки" 36, элемент задержки 37. Устройство позволяет вкачестве признака наличия чисел сортируемой последовательности записывать вблок памяти как логическийнуль, так и логическую единицу. Этопозволяет в процессе работы устройства обнаружить отказ блока памятитипа "константа 1 или 0". 1 ил,1478210 Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для сортировки чисел в системах обработки5информации.Цель изобретения - повышение надежности устройства за счет воэможности определения отказов блока памяти типа константа "1" или "0".На чертеже представлена схема устройства.Устройство содержит блок 1 памяти,счетчик 2, информационные входы 3 ивыходы 4, реверсивный счетчик 5, эле-.15менты ИЛИ 6-10, элементы И 11-18,элементы НЕ 19 и 20, генератор 21 импульсов, элемент 22 задержки, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 23 и 24, регистр25, дешифратор 26, формирователи 27 щи 28 импульса, вход 29 управления записью, вход 30 синхронизации, вход31 задания режима, вход 32 сброса,выход 33 синхронизации, выход 34сбоя, выход 35 "Конец считывания", 25выход 36 "Конец очистки" и элемент37 задержкиУстройство работает следующим об.разом.оПеред началом работы сигналом по 30входу 32 счетчики 2, 5 и регистр 25устанавливаются в нулевое состояние.Режим "Очистка" задается комбинацией сигналов 01 на входах 31 устройства, которая переписывается в регистр 25 сигналом с выхода элементаНЕ 20, Высокий уровень сигнала навыходе 1 "Очистка" дешифратора 26разрешает прохождение импульсов генератора 21 через элемент И 15 и элемент ИЛИ 9 на вход записи/считыванияблока 1 памяти.Период повторения импульсов генератора 21 определяется суммой времени чтения информации из блока 1 памя- дти, времени распространения сигналовфна регистре 25, дешифраторе 26, элементе ИЛИ 7 и времени срабатываниясчетчика 2 по установочному входу,При этом осуществляется записьуровня сигнала, присутствующего навыходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 23в блок 1 памяти по адресу, сформированному на выходах счетчика 2. Поокончании записи задним фронтом сигнала на выходе элемента ИЛИ 10 производится модификация содержимого счетчика 2, т,е. к его содержимому добавляется единица. Запись сигналов по последующим адресам блока 1 памяти производится аналогичноСигнал на выходе переноса счетчика 2 проходит через открытый элемент И 16 и свидетельствует об окончании режима "Очистка" на выходе 36. В режиме "Очистка" в блок 1 памяти по всем адресам записывается нулевой уровень сигнала при нулевом уровне сигнала на вкоде устройства 29. Однако в этом режиме по всем адресам блока 1 памяти может быть записан и единичный уровень сигнала при единичном уровне сигнала на входе 29 устройства.Рвжим "Сортировка" задается комбинацией сигналов 10 на входах 31 устройства, которая переписывается в регистр 25 сигналом с выхода элемента НЕ 20. Высокий уровень сигнала на втором выходе "Сортировка" дешифратора 26 открывает элемент И 14. Сортируемый массив из К различных по величине и разрядных чисел /К 6 2 / поступает на информационные входы 3 устройства. Синхронно с каждым числом на вход устройства 30 поступает сигнал синхронизации, который, проходя элемент И 14, осуществляет запись числа с информационных входов 3 в счетчик 2, выходные сигналы которого поступают на адресные входы блока 1 памяти.Минимальный период следования чисел сортируемого массива при сортировке определяется суммой времени чтения данных из блока 1 памяти, времени распространения сигналов на счетчике 2 по информационным входам н времени записи данных в блок 1 памяти.По каждому сигналу сопровождения в устройстве сначала производится чтение бита данных из блока 1 памяти по адресу, равному принятому в счетчик 2 числу сортируемой последовательности. Для этого сигнал синхронизации задерживается на элементе 22 задержки, величина задержки которого должна быть больше суммы задержки сигнала на счетчике 2 и чтения данных из блока 1 памяти. По переднему фронту сигнала на выходе элемента 22 задержки формирователь 28 импульса выдает короткий импульс опроса элемента И 11. Если уровни сигналов на входе устройства 29 и считанного иэ блока 1 памяти одинаковые, т,е. нулевые или единичные, на выходе элемен 1478210та ИСКЛЮЧАЮЩЕЕ ИЛИ 24 низкий уровеньсигнала и высокий уровень сигнала -на выходе элемента НЕ 19, которыйразрешает прохождение импульса с фор 5мирователя 28 импульса на суммирующий вход счетчика 5 через элементИ 11.Длительность импульса, формируемого формирователем 28 импульса, опре Оделяется минимально допустимой длительностью счетных импульсов счетчика 5Под воздействием поступившего сигнала с выхода элемента И 11 к содержимому счетчика 5 добавляется единица. Одновременно с этим выходной сигнал элемента 22 задержки проходит через элемент ИЛИ 9 на вход записи/считывания блока 1 памяти и осуществляет запись в блок 1 памяти по адресу,записанному в счетчике 2, единичногобита данных - при нулевом уровне сигнала на входе 29 устройства или нулевого бита данных при единичном уровне 25сигнала на входе 29 устройства, таккак в этом режиме на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ поступает высокий уровень сигнала с второго выхода"Сортировка" дешифратора 26. Работа 30устройства при приеме других словсортируемой последовательности аналогична, Таким образом, после окончания режима сортировки в счетчике 5зафиксировано количество отличныхдруг от друга чисел в сортируемоммассивеРежим "Считывание" задается комбинацией сигналов 11 на входах 31устройства,При этом по отрицательному перепаду сигнала на втором выходе "Сортировка" дешифратора 26 срабатываетформирователь 27 импульса, выходнойсигнал которого через элемент ИЛИ 7 45устанавливает счетчик 2 в нулевоесостояние. Длительность импульса, формируемого формирователем 27 импульса, опре 50 деляется минимально допустимой длительностью сигнала установки в нуль счетчика 2.Высокий уровень сигнала на третьем выходе "Считывание" дешифратора 26 разрешает прохождение импульсов гене 55 ратора 21 через элемент И 13 на вход элемента И 12 и через элемент ИЛИ 10 на суммирующий вход счетчика 2. Производится чтение бита данных из блока 1 памяти по адресу, сформированному на выходах счетчика 2, Если на выходе элемента ИСКИЧАЮЩЕЕ ИЛИ 24 присутствует высокий уровень сигнала, то выходной сигнал элемента И 12 поступает на вычитающий вход счетчика 5, уменьшая его содержимое на единицу, и на выход 33 устройства как сигнал синхронизации числа, присутствующего в данный момент на информационных выходах 4 устройства, Задним фронтом сигнала на выходе элемента ИЛИ 10 производится модификация содержимого счетчика 2, т.е. к его содержимому добавляется единица. Считывание данных из других ячеек блока 1 памяти производится аналогич-, но. По окончании считывания выходной сигнал переполнения счетчика 2 через элемент 37 задержки и элемент И 17 поступает на выход 35 устройства как сигнал окончания считывания, через элемент ИЛИ 8 регистр 25 устанавливается в нулевое состояние и опрашивает элемент И 18, Если в это время содержимое счетчика 5 отлично от нулевого, что фиксируется элементом ИЛИ 6, на выходе элемента И 18, т.е. на выходе 34 устройства, фиксируется сбой устройства при сортировке данной последовательности. Величина задержки на элементе 37 задержки должна быть больше половины такта работы генератора 21 импульсов. Пусть на входе 29 устройства установлен нулевой уровень сигнала. При этом в режиме очистки по всем адресам блока 1 памяти записываются нулевые биты данных. Пусть сортируемая последовательность чисел имеет вид 15, 8, 6, 15, 32, В режиме сортировки в ячейки с адресами 15, 8, 6, 32 записаны единичные биты данных, а в счетчике 5 по окончании сортировки зафиксировано число 4, При правильной работе устройства в режиме считывания на выходы 4 устройства последовательно выведены числа 6, 8, 15, 32, и в конце режима счетчик 5 находится в нулевом состоянии. Если в блоке ) памяти по адресу, например, 14 имеет место отказ типа константа "1", то выходная последовательность в режиме считывания имеет вид 6, 8, 14, 15, 32 и в конце считывания фиксируется сбой устройства, так каксчетчик 5 не находится в нулевом состоянии. В этом случае представляется возможность повторить сортировку данной последовательности, но уже при5 единичном уровне сигнала на входе 29 устройства. При этом в режиме очистки в блок 1 памяти по всем адресам записаны единичные биты данных. В режиме сортировки по адресам блока 1 памяти 15, 6, 8, 32 записываются нулевые биты данных, а в режиме считывания выдается пользователю сортированная последовательность чисел 6, 8, 15, 32 и не фиксируется сбой в ра боте устройства.Формула изобретенияУстройство для сортировки информа О ции, содержащее счетчик, реверсивный счетчик, первый элемент ИЛИ, три элемента И, пва элемента НЕ, генератор импульсов, элемент задержки и блок памяти, адресные входы которого сое динены с разрядными выходами счетчика, которые являются информационными выходами устройства, информационные входы которого подключены к информационным входам счетчика, выходы раз- ЗО рядов реверсивного счетчика соединены с входами первого элемента ИЛИ, суммирующий и вычитающий входы реверсивного счетчика соединены с выходами первого и второго элементов И со-,35 ответственно, первый вход первого элемента И соединен с выходом первого элемента НЕ, вход которого соединен с первым входом второго элемента И, выход генератора импульсов соеди О нен с первым входом третьего элемента И, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности устройства за счет воэможности определения отказов блока памяти типа 45 константа 1." или 0", в него введены два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, регистр, дешифратор, два формирователя импульсов, четыре элемента ИЛИ, пять элементов И, второй элемент задержки, причем вход сброса устройства соединен с первыми входами второго и третьего элементов ИЛИ и входом установки в "О" реверсивного счетчика, второй вход второго элемента ИЛИ соединен с выходом первого формирователя импульса, инверсный вход которого со" единен с первым выходом дешифратора и первыъи входами четвертого элемента И и первого элемента ИСКЛЮЧАЮЩЕЕИЛИ, выход которого соединен с информационным входом блока памяти, входзаписи-считывания которого соединенс выходом четвертого элемента ИЛИ,первый вход которого соединен с выходом первого элемента задержки и входом второго формирователя импульса,выход которого соединен с вторым входом первого элемента И, второй входчетвертого элемента ИЛИ соединен спервым входом пятого элемента ИЛИ ивыходом пятого элемента И, первыйвход которого соединен с вторым выходом дешифратора и первым входомшестого элемента И, второй вход пятого элемента И соединен с первымвходом третьего элемента И, второйвход которого соединен с третьим выходом дешифратора и первым входомседьмого элемента И, второй вход которого соединен с вторым входом шестого элемента И и через второй элемент задержки с выходом переносасчетчика, инверсный счетный вход которого соединен с выходом пятого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента Ии вторым входом второго элемента И,выход которого является синхронизирующим выходом устройства, вход синхронизации которого соединен с вторым входом четвертого элемента И, выход которого соединен с входом первого элемента задержки и входом управления записью счетчика, вход установки в "О" которого соединен с выходомвторого элемента ИЛИ, второй входпервого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, являющийся входом управления записьюустройства, соединен с первым входомвторого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,второй вход которого соединен с выходом блока памяти, выход второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом первого элемента НЕ, выход первого элемента ИЛИ соединен спервым входом восьмого элемента И,выход которого является выходом сбояустройства, выход "Конец считывания"которого соединен с вторым входомвосьмого элемента И, с выходом седьмого элемента И и вторым входом третьего элемента ИЛИ, выход которогосоединен с входом установки в "О" регистра, вход синхронизации которогочерез второй элемент НЕ соединен свыходом генератора импульсов, входы1478210 Составитель А,АлександровТехред М. Ходанич Корректор О. Кравцова Редактор О.Головач Заказ 2364/48 Тираж 669 ПодписноеВНИИПИ Государственного комитета по изобретениям н открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб д. 4/5 Производственно в издательск комбинат "Патент", г.ужгород, ул. Гагарина,101 дешифратора соединены с соответствующими выходами разрядов регистра, информационные входы которого являютсяа входами задания режима работы устройства, выходом "Конец очистки" которого является выход шестого элемента И.