Устройство для сортировки информации Советский патент 1989 года по МПК G06F7/06 

I14

Изобретение относится к вычислительной технике и может быть -использовано в качестве устройства для сортировки чисел в системах обработки информации.

Цель изобретения - повышение надежности устройства за счет возможности определения отказов блока памяти типа константа 1 или О.

На чертеже представлена схема устройства.

Устройство содержит блок 1 памяти, счетчик 2, информационные входы 3 и выходы 4, реверсивный счетчик 5, элементы ИЛИ 6-10, элементы И 11-18, элементы НЕ 19 и 20, генератор 21 импульсов, элемент 22 задержки, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 23 и 24, регистр 25, дешифратор 26, формирователи 27 и 28 импульса, вход 29 управления за- писью, вход 30 синхронизации, вход 31 задания режима, вход 32 сброса, выход 33 синхронизации, выход 34 сбоя, выход 35 Конец считывания, выход 36 Конец очистки и элемент 37 задержки.

Устройство работает следующим образом.- Перед началом работы сигналом по входу 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, т.е. к его содержимому добавляется единица. Запись сигналов по

102

последующим адресам блока 1 памяти производится аналогично. Сигнал на выходе переноса счетчика 2 проходит через открытый элемент И 16 и свидетельствует об окончании режима Очистка на выходе 36. В режиме Очистка в блок 1 памяти по всем адресам записывается нулевой уровень сигнала при нулевом уровне сигнала на входе устройства 29. Однако в этом режиме по всем адресам блока 1 памяти может быть записан и единичный уровень сигнала при единичном уровне сигнала на входе 29 устройства.

Режим Сортировка задается комбинацией сигналов 10 на входах 31 устройства, которая переписывается в регистр 25 сигналом с выхода элемента НЕ 20. Высокий уровень сигнала на втором выходе Сортировка дешифратора 26 открывает элемент И 14. Сортируемый массив из К различных по величине п разрядных чисел /К 2 h/ поступает на информационные входы 3 устройства. Синхронно с каждым числом на вход устройства 30 поступает сигнал синхронизации, который, проходя элемент И 14, осуществляет запись числа с информационных входов 3 в счетчик 2, выходные сигналы которого поступают на адресные входы блока 1 памяти.

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

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

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

Под воздействием поступившего сигнала с выхода элемента И 11 к содер- жимому счетчика 5 добавляется единица. Одновременно с этим выходной сигнал элемента 22 задержки проходит через элемент ИЛИ 9 на вход записи/считывания блока 1 памяти и осуществля- ет запись в блок 1 памяти по адресу, записанному в счетчике 2, единичного бита данных - при нулевом уровне сигнала на входе 29 устройства или нулевого бита данных при единичном уровне сигнала на входе 29 устройства, так как в этом режиме на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ поступает высокий уровень сигнала с второго выхода Сортировка дешифратора 26. Работа устройства при приеме других слов сортируемой последовательности аналогична. Таким образом, после окончания режима сортировки в счетчике 5 зафиксировано количество отличных друг от друга чисел в сортируемом массиве.

Режим Считывание задается комбинацией сигналов 11 на входах 31 устройства.

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

50

Длительность импульса, формируемого формирователем 27 импульса, определяется минимально допустимой длительностью сигнала установки в нуль счетчика 2.

Высокий уровень сигнала на третьем выходе Считывание дешифратора 26 разрешает прохождение импульсов гене-5- ратора 21 через элемент И 13 на вход элемента И 12 и через элемент ИЛИ 10 на суммирующий вход счетчика 2.

g

5 0 5 0 5

0

5

0

-

Производится чтение бита данных из блока 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 находится в нулевом состоянии. Если в блоке 1 памяти по адресу, например, 14 имеет место отказ типа константа 1, то выходная последовательность в режиме считывания имеет вид 6, 8, 14, 15, 32 и в конце считывания фиксируется сбой устройства, так как

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

Формула изобретения

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

15

10

25

30

35

20 782106

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

50

55

714782108

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

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