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

 

Изобретение относится к вычислительной технике и может быть использовано в качестве устройства сортировки чисел в системах обработки информации. Цель изобретения - повышение надежности устройства за счет возможности определения отказов блока памяти типа "константа 1 или 0". Устройство содержит блок памяти 1, счетчик 2, информационные входы 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 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН ц11 4 С 06 F 7/06

3. 5",0 3ЯЩ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (2l) 4215604/24-24 (22) 27.03.87 (46) 07 ° 05.89. Бюл. В 17 (72) В.С.Лупиков и В.В.Богданов (53) 681. 325.5 (088. 8) (56) Авторское свидетельство СССР

В 1183956, кл. G 06 F 7/06, 1984.

Авторское свидетельство СССР

У 1277092, кл. G 06 F 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в качестве устройства сортировки чисел в системах обработки информации. Цель изобретения— повышение надежности устройства эа счет воэможности определения отказов блока памяти типа "константа 1 . или 0". Устройство содержит блок памяти 1, счетчик 2, информационные

ÄÄSUÄÄ 1478210 А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 устанавливаются в нулевое состояние.

Режим "Очистка" задается комбинацией сигналов Ol на входах 31 устройства, которая переписывается в ре- 35 гистр 25 сигналом с выхода элемента

НЕ 20, Высокий уровень сигнала на выходе 1 "Очистка" дешифратора 26 разрешает прохождение импульсов генератора 21 через элемент И 15 и эле- 40 мент ИЛИ 9 на вход записи/считывания блока 1 памяти.

Период повторения импульсов генератора 21 определяется суммой времени чтения информации из блока 1 памя- д ти, времени распространения сигналов о на регистре 25, дешифраторе 26, элементе ИЛИ 7 и времени срабатывания счетчика 2 по установочному входу.

При этом осуществляется запись уровня сигнала, присутствующего на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 23 в блок 1 памяти по адресу, сформированному на выходах счетчика 2. По окончании записи задним фронтом сигнала на выходе элемента ИЛИ 10 производится модификация содержимого счетчика 2, т.е. к его содержимому добавляется единица. Запись сигналов по последующим адресам блока 1 памяти производится аналогично ° Сигнал на выходе переноса счетчика 2 проходит через открытый элемент И 16 и свидетельствует об окончании режима "Очистка" на выходе 36. В режиме "Очистка" в блок l памяти по всем адресам saписывается нулевой уровень сигнала при нулевом уровне сигнала на вкоде устройства 29. Однако в этом режиме по всем адресам блока 1 памяти может быть записан и единичный уровень сигнала при единичном уровне сигнала на входе 29 устройства.

Рвжим "Сортировка" задается комбинацией сигналов 10 на входах 31 устройства, которая переписывается в регистр 25 сигналом с выхода элемента

НЕ 20. Высокий уровень сигнала на втором выходе "Сортировка" дешифратора 26 открывает элемент И 14. Сортируемый массив из К различных по величине и разрядных чисел /К 6 2 / поступает на информационные входы 3 устройства. Синхронно с каждым числом на вход устройства 30 поступает сигнал синхронизации, который, проходя

I элемент И 14, осуществляет запись числа с информационных входов 3 в счетчик 2, выходные сигналы которого поступают на адресные входы блока 1 памяти.

Минимальный период следования чисел сортируемого массива при сортировке определяется суммой времени чтения данных из блока 1 памяти, времени распространения сигналов на счетчике 2 по информационным входам н времени записи данных в блок 1 памяти.

По каждому сигналу сопровождения в устройстве сначала производится чтение бита данных из блока 1 памяти по адресу, равному принятому в счетчик 2 числу сортируемой последовательности. Для этого сигнал синхронизации задерживается на элементе 22 задержки, величина задержки которого должна быть больше суммы задержки сигнала на счетчике 2 и чтения данных из блока 1 памяти. По переднему фронту сигнала на выходе элемента 22 задержки формирователь 28 импульса выдает короткий импульс опроса элемента И 11. Если уровни сигналов на входе устройства 29 и считанного иэ блока 1 памяти одинаковые, т,е. нулевые или единичные, на выходе элемен1478210 та ИСКЛЮЧАЮЩЕЕ ИЛИ 24 низкий уровень сигнала и высокий уровень сигнала— на выходе элемента HE 19, который разрешает прохождение импульса с фор5 мирователя 28 импульса на суммирующий вход счетчика 5 через элемент

И Il.

Длительность импульса, формируемого формирователем 28 импульса, опре- 10 деляется минимально допустимой длительностью счетных импульсов счетчи— ка 5 °

Под воздействием поступившего сигнала с выхода элемента И 11 к содержимому счетчика 5 добавляется единица. Одновременно с этим выходной сигнал элемента 22 задержки проходит через элемент ИЛИ 9 на вход записи/считывания блока 1 памяти и осуществля- 2р ет запись в блок 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 памяти записываются нулевые биты данных. Пусть сортируемая последовательность чисел имеет вид

1 5, 8, 6, 15, 32. В режиме сортировки в ячейки с адресами 15, 8, 6, 32 записаны единичные биты данных, а в счетчике 5 по окончании сортировки зафиксировано число 4. При правильной работе устройства в режиме считывания на выходы 4 устройства последовательно выведены числа 6, 8, 15, 32, и в конце режима счетчик 5 находится в нулевом состоянии. Если в блоке 1 памяти по адресу, например, 14 имеет место отказ типа константа

"1", то выходная последовательность в режиме считывания имеет вид 6, 8, 14, 15, 32 и в конце считывания фиксируется сбой устройства, так как

14782 10 счетчик 5 не находится в нулевом состоянии. В этом случае представляется возможность повторить сортировку данной последовательности, но уже при

5 единичном уровне сигнала на входе

29 устройства. При этом в режиме очистки в блок 1 памяти по всем адресам записаны единичные биты данных.

В режиме сортировки по адресам блока

1 памяти 15, 6, 8, 32 записываются нулевые биты данных, а в режиме считывания выдается пользователю сортированная последовательность чисел 6, 8, 15, 32 и не фиксируется сбой в ра- 5 боте устройства. формула изобретения

Устройство для сортировки информа- 2р ции, содержащее счетчик, реверсивный счетчик, первый элемент ИЛИ, три элемента И, пва элемента НЕ, генератор импульсов, элемент задержки и блок памяти, адресные входы которого сое- 25 динены с разрядными выходами счетчика, которые являются информационными выходами устройства, информационные входы которого подключены к информационным входам счетЧика, выходы раз- 3р рядов реверсивного счетчика соединены с входами первого элемента ИЛИ, суммирующий и вычитающий входы реверсивного счетчика соединены с выходами первого и второго элементов И со-, 35 ответственно, первый вход первого элемента И соединен с выходом первого элемента НЕ, вход которого соединен с первым входом второго элемента

И, выход генератора импульсов соеди- 4р нен с первым входом третьего элемента И, о т л и ч а ю щ е е с я тем, что, с целью повышения надежности устройства за счет воэможности определения отказов блока памяти типа константа "l." или "0" в него введены два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, регистр, дешифратор, два формирователя импульсов, четыре элемента ИЛИ, пять элементов И, второй элемент задержки, причем вход сброса устройства соединен с первыми входами второго и третьего элементов ИЛИ и входом установки в "0" реверсивного счетчика, второй вход второго элемента ИЛИ соединен с выходом первого формирователя импульса, инверсный вход которого со" единен с первым выходом дешифратора и первы и входами четвертого элемента И и первого элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ, выход которого соединен с информационным входом блока памяти, вход записи-считывания которого соединен с выходом четвертого элемента ИЛИ, первый вход которого соединен с выходом первого элемента задержки и входом второго формирователя импульса, выход которого соединен с вторым входом первого элемента И, второй вход четвертого элемента ИЛИ соединен с первым входом пятого элемента ИЛИ и выходом пятого элемента И, первый вход которого соединен с вторым выходом дешифратора и первым входом шестого элемента И, второй вход пятого элемента И соединен с первым входом третьего элемента И, второй вход которого соединен с третьим выходом дешифратора и первым входом седьмого элемента И, второй вход которого соединен с вторым входом шестого элемента И и через второй элемент задержки с выходом переноса счетчика, инверсный счетный вход которого соединен с выходом пятого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И и вторым входом второго элемента И, выход которого является синхронизирующим выходом устройства, вход синхронизации которого соединен с вторым входом четвертого элемента И, выход которого соединен с входом первого элемента задержки и входом управления записью счетчика, вход установки в "0" которого соединен с выходом второго элемента ИЛИ, второй вход первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, являющийся входом управления записью устройства, соединен с первым входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с выходом блока памяти, выход второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом первого элемента НЕ, выход первого элемента ИЛИ соединен с первым входом восьмого элемента И, выход которого является выходом сбоя устройства, выход "Конец считывания" которого соединен с вторым входом восьмого элемента И, с выходом седьмого элемента И и вторым входом третьего элемента ИЛИ, выход которого соединен с входом установки в "0" регистра, вход синхронизации которого через второй элемент НЕ соединен с выходом генератора импульсов, входы

14782)0

Составитель А.Апександров

Техред М. Ходанич Корректор О. Кравцова

Редактор О. Головач

Заказ 2 364 /.48 Тираж 669 Подписное

ВНИИПИ Государственного комитета по изобретениям н открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 дешифратора соединены с соответствующими выходами разрядов регистра, информационные входы которого являются входами задания режима работы устройства, выходом "Конец очистки" которого является выход шестого элемента И.