Устройство для ранжирования чисел
NUMBER RANKING DEVICE

Изобретение относится к автоматике и вычислительной технике и предназначено для защиты информации в автоматизированных системах.
Известно устройство для ранжирования чисел  (авторское свидетельство СССР на изобретение № 1425653, опубл. 23.09.1988 г., БИ № 35), которое по своей технической сущности является наиболее близким к предлагаемому устройству. Это устройство содержит генератор тактовых импульсов, счетчик, первый и второй буферные регистры, блок сравнения, первый  и второй коммутаторы, блок оперативной памяти и блок управления, причём входы ранжируемых чисел устройства соединены с информационными входами первой группы первого коммутатора и информационными входами первой группы блока сравнения, информационные входы второй группы первого коммутатора соединены с выходами  первого буферного регистра и информационными входами второй группы блока сравнения, информационные входы третьей группы первого коммутатора  подключены к выходам второго буферного регистра, информационные входы четвертой группы первого коммутатора подключены к шине «земля», а выходы первого коммутатора подключены к информационным входам блока оперативной памяти, выходы которого являются выходами ранжируемых чисел устройства и соединены с информационными входами первого и второго буферных регистров, выход генератора тактовых импульсов соединен со вторым входом блока управления, вход сброса информации в счетчике подключен к управляющему входу начала работы устройства и к первому входу блока управления, счетный вход счетчика подключен к шестому выходу блока управления, выход переполнения счетчика подключен к четвертому входу блока управления и к выходу окончания цикла сравнения устройства, информационные выходы счетчика подключены к первой группе информационных входов второго коммутатора и к выходу номера ранга числа устройства, ко второй группе информационных входов второго коммутатора подключены входы адреса запроса устройства, а выход второго коммутатора подключен к адресным входам блока оперативной памяти, управляющий вход второго коммутатора подключен к управляющему входу запроса устройства и к пятому входу блока управления, третий и шестой входы которого подключены соответственно, к выходу блока сравнения и к управляющему входу очистки памяти устройства, а первый, второй, третий, четвертый, пятый, седьмой и восьмой выходы блока управления подключены, соответственно, к первому,  второму, третьему и четвертому адресным входам первого коммутатора, входу записи-чтения блока оперативной памяти, управляющим входам второго и первого буферных регистров.
Недостатком устройства-прототипа является недостаточная универсальность, связанная с отсутствием возможности регистрации и представления порядкового номера числа из последовательности чисел в процессе ранжирования, с потерей чисел с минимальной величиной после каждой операции ранжирования, с отсутствием операции в процедуре ранжирования, учитывающей поступление нескольких  чисел одинаковой величины.
Техническим результатом настоящего изобретения является   расширение арсенала технических средств.
Для достижения результата в устройство для ранжирования чисел, содержащее блок оперативной памяти, первый и второй регистры, первый и второй коммутаторы,  счетчик адресов, выходы которого через второй коммутатор подключены к адресным входам блока оперативной памяти; блок управления, один из входов которого подключен ко входу начала работы устройства, а выходы подключены к управляющим входам счетчика адресов,  первого коммутатора, блока памяти, ко входам занесения регистров, дополнительно включены: реверсивный счетчик поступающих чисел, дешифратор порядковых номеров поступающих чисел, блок логических элементов ИЛИ,  счетчик определения порядковых номеров чисел,  первый и второй логические элементы И,  многовходовый логический элемент ИЛИ, третий коммутатор и счетчик ранга числа,  причем в качестве второго регистра использован сдвиговый регистр, первый вход устройства подключен к информационным входам первого регистра,  второй, третий и четвертый входы устройства подключены, соответственно, к первому, третьему и четвертому входам блока управления, второй вход которого соединен с выходом младшего разряда дешифратора порядковых номеров поступающих чисел, выход первого регистра  подключен к информационным входам первого блока коммутации, выходы счетчика адреса подключены к информационным входам второго блока коммутации, выходы первого и второго блоков коммутации объединены и подключены к информационным входам блока оперативной памяти, выходы реверсивного счетчика поступающих чисел подключены ко входам дешифратора порядковых номеров поступающих чисел, выходы которого подключены к первым входам блока логических элементов ИЛИ, ко вторым входам которого подключены выходы второго регистра и входы многовходового элемента ИЛИ, выходы блока логических элементов ИЛИ подключены к информационным входам блока  оперативной памяти, выходы которого подключены к информационным входам второго регистра, а управляющие входы записи и обращения к памяти подключены, соответственно, к шестому и седьмому выходам блока управления, у которого  первый, второй, третий, четвертый, пятый, восьмой, девятый, десятый, одиннадцатый, двенадцатый и тринадцатый выходы подключены, соответственно, к  счетному входу счетчика адресов, к управляющему входу  второго блока коммутаторов, к объединенным входу занесения первого регистра и инкрементирующему входу реверсивного счетчика поступающих чисел, к управляющему входу первого блока коммутаторов, к декрементирующему входу реверсивного счетчика поступающих чисел, ко входу занесения второго регистра, к объединенным управляющему сдвиговому входу второго регистра и к инкрементирующему входу счетчика определения порядкового номера чисел, к управляющему входу сброса счетчика определения порядкового номера чисел, к первому входу первого логического элемента И, ко второму входу второго логического элемента И, второй вход первого логического элемента И подключен к пятому входу блока управления и к выходу младшего информационного разряда второго регистра, первый вход второго элемента И подключен к шестому входу блока управления и к выходу многовходового логического элемента ИЛИ,  выход первого логического элемента И подключен к управляющему входу третьего коммутатора и к четвертому выходу устройства, выход  второго логического элемента И подключен к счетному входу счетчика рангов чисел, выходы третьего коммутатора являются первыми выходами устройства, а выходы счетчика рангов чисел, соответственно, вторыми выходами устройства.
На фиг.1 представлена структурная схема предлагаемого устройства, на фиг.2 – структурная схема  блока логических элементов ИЛИ,  на фиг.3 – структурная схема  блока управления, на фиг.4 – структурная схема распределителя  импульсов блока управления, на  фиг.5 - временные диаграммы работы устройства в режиме регистрации чисел, на фиг.6 - временные диаграммы работы устройства в режиме ранжирования и выдачи результатов.
Устройство содержит:  реверсивный счетчик 1 поступающих чисел, первый регистр 2, счетчик адреса 3, дешифратор 4 порядковых номеров поступающих чисел, первый блок коммутатора 5, второй блок коммутатора 6,   блок логических элементов  ИЛИ 7, блок оперативной памяти 8, блок управления 9, второй регистр 10, счетчик 11 номеров поступающих чисел, первый логический  элемент И 12, второй логический элемент И 13, многовходовый логический элемент ИЛИ 14, третий блок коммутатора 15 и счетчик рангов чисел 16, причем в качестве второго регистра использован сдвиговый регистр, первый вход устройства подключен к информационным входам первого регистра,  второй, третий и четвертый входы устройства подключены, соответственно, к первому, третьему и четвертому входам блока управления, второй вход которого соединен с выходом младшего разряда дешифратора порядковых номеров поступающих чисел, выход первого регистра  подключен к информационным входам первого блока коммутации, выходы счетчика адреса подключены к информационным входам второго блока коммутации, выходы первого и второго блоков коммутации объединены и подключены к информационным входам блока оперативной памяти, выходы реверсивного счетчика поступающих чисел подключены ко входам дешифратора порядковых номеров поступающих чисел, выходы которого подключены к первым входам блока логических элементов ИЛИ, ко вторым входам которого подключены выходы второго регистра и входы многовходового элемента ИЛИ, выходы блока логических элементов ИЛИ подключены к информационным входам блока  оперативной памяти, выходы которого подключены к информационным входам второго регистра, а управляющие входы записи и обращения к памяти подключены, соответственно, к шестому и седьмому выходам блока управления, у которого  первый, второй, третий, четвертый, пятый, восьмой, девятый, десятый, одиннадцатый, двенадцатый и тринадцатый выходы подключены, соответственно, к  счетному входу счетчика адресов, к управляющему входу  второго блока коммутаторов, к объединенным входу занесения первого регистра и инкрементирующему входу реверсивного счетчика поступающих чисел, к управляющему входу первого блока коммутаторов, к декрементирующему входу реверсивного счетчика поступающих чисел, ко входу занесения второго регистра, к объединенным управляющему сдвиговому входу второго регистра и к инкрементирующему входу счетчика определения порядкового номера чисел, к управляющему входу сброса счетчика определения порядкового номера чисел, к первому входу первого логического элемента И, ко второму входу второго логического элемента И, второй вход первого логического элемента И подключен к пятому входу блока управления и к выходу младшего информационного разряда второго регистра, первый вход второго элемента И подключен к шестому входу блока управления и к выходу многовходового логического элемента ИЛИ,  выход первого логического элемента И подключен к управляющему входу третьего коммутатора и к четвертому выходу устройства, выход  второго логического элемента И подключен к счетному входу счетчика рангов чисел, выходы третьего коммутатора являются первыми выходами устройства, а выходы счетчика рангов чисел, соответственно, вторыми выходами устройства.
n
n
7-11
7-1n
7-21
7-2n
71
7n
Блок логических элементов ИЛИ 7, как показано на фиг. 2, содержит  двухвходовых логических элементов ИЛИ, где  – число выходных разрядов дешифратора порядковых номеров поступающих чисел, равное разрядности данных в блоке оперативной памяти 8 и второго регистра 10, причем первые входы  двухвходовых логических элементов ИЛИ подключены к первым входам I – I блока логических элементов ИЛИ, а вторые входы логических элементов ИЛИ 7, соответственно, ко вторым входам I– I блока логических элементов ИЛИ 7.  Выходы логических элементов ИЛИ подключены к выходам O-O блока логических элементов ИЛИ 7. Принцип работы блока логических элементов ИЛИ 7 понятен из описания его структурной схемы.
Блок управления 9, как показано на фиг.3, содержит первый, второй и третий одновибраторы под соответствующими номерами: 18, 19 и 20, триггер пуска-останова 21, генератор тактовых импульсов 22, первый, второй, третий и четвертый логические элементы И под соответствующими номерами: 23, 24, 25 и 26, распределитель  управляющих импульсов 27, причем входы первого, второго и третьего одновибраторов подключены, соответственно, к третьему, четвертому и пятому входам блока управления, а выходы этих одновибраторов подключены, соответственно,  к  первому входу блока распределения импульсов 27, к первому входу первого логического элемента И и к первому входу второго логического элемента И, установочный вход триггера пуска-останова подключен к выходу второго логического элемента И и к пятому входу распределителя  импульсов 27, сбросовый вход триггера пуска-останова 21 подключен к выходу четвертого элемента И и к седьмому входу распределителя импульсов 27, выход генератора тактовых импульсов подключен ко вторым входам логических элементов 23, 24 25 и 26,  выходы первого  и третьего логических элементов И подключены, соответственно ко второму и шестому входам распределителя управляющих импульсов 27, третий и четвертый входы которого подключены, соответственно  к пятому и шестому входам блока управления 9, а выходы распределителя управляющих  импульсов 27 с первого по тринадцатый подключены, соответственно, к выходам блока управления 9 с первого по тринадцатый. Одновибраторы 18-20 блока управления предназначены для согласования временного режима подачи значений чисел из-вне на вход устройства - с режимом регистрации этих чисел в устройстве. Принцип работы блока управления  9 понятен из описания его структурной схемы и режимов работы устройства.
271
277
901
913,
Блок формирования импульсов 27 (фиг. 4), как показано на фиг. 4, содержит 11 двухвходовых логических элементов И под номерами: 28, 29, 40, 42, 44-47, 48-50 и 53, два трехвходовых  логических элемента И под номерами 31 и 43, один логический элемент НЕ под номером 30 и восемь триггеров под номерами 32-38 и 41, один двухвходовый элемент ИЛИ под номером 52 и две схемы задержки сигнала под номерами 39 и 48, выполненные в виде R-C цепочки. Входы блока формирования импульсов 27 на фиг. 4 обозначены как I-I, а на фигуре 3, соответственно, 1-7. Выходы  блока формирования импульсов 27 на фиг. 4 обозначены, как O-Oи подключены к соответствующим выходам: 1-13 -  блока управления 9 на фигуре 3. При обозначении входов и выходов учитывались обозначения, принятые на фиг. 3. Принцип работы блока формирования импульсов понятен из описания его структурной схемы и режимов работы устройства.
Устройство работает в двух режимах.
Режим 1: режим регистрации значений чисел в блоке оперативной памяти устройства.
Режим 2: режим ранжирования и выдачи результатов.
В режиме 1 устройство работает следующим образом. В исходном состоянии содержимое блока оперативной  памяти 8 (фиг.1),  счетчиков 1, 3, 11 и 16, а также первого (2)  и второго (10) регистров  обнулены, блоки коммутаторов (5, 6 и 15)  находятся в закрытом состоянии. Для начала работы устройства на второй вход его подается сигнал «Пуск». При этом на выходе 3 устройства  появляется сигнал готовности («Гот»)  ввода значений чисел  в первый регистр 2. В ответ на сигнал «Гот» на первый вход устройства поступает первое ранжируемое число, а на третьем входе появляется сигнал ввода числа в первый регистр 2  - «Ввод», который инициирует подачу с выхода 3 блока управления 9 сигнала занесения данных с входа 1 устройства в первый регистр 2 и счетного сигнала на первый вход реверсивный счетчика 1 поступающих чисел. Далее, по сигналу с выхода 4 блока управления 9 на первый коммутатор 5 выходы первого регистра (2) подключаются к адресным входам блока оперативной памяти 8,  на информационные входы которого через дешифратор 4 порядковых номеров поступающих чисел и блок логических элементов ИЛИ 7 поступает зашифрованный унарный код поступающего  числа.  Процедура записи унарного кода числа в блок оперативной  памяти 8 состоит из двух последовательных операций: операции считывания содержимого ячейки блока оперативной  памяти 8 по адресу, соответствующему текущему значению числа в первом регистре 2,  во второй регистр 10, и последующей операции одновременной записи зашифрованного в унарном коде содержимого двоичного счетчика 1 поступающих чисел и содержимого второго  регистра 10 в одну ячейку по адресу содержимого первого регистра 2.  Для этого со входов 6 и 7 блока управления 9 на вход обращения блока оперативной  памяти 8 и вход занесения данных во второй  регистр 10 подаются соответствующие сигналы. Затем, для записи совокупного содержимого зашифрованного значения содержимого реверсивного счетчика 1 поступающих чисел и содержимого второго  регистра 10 на вход записи блока оперативной памяти 8 с выхода 6 блока управления 9 подается сигнал записи. При этом с выхода 13 блока управления 9 на третий выход устройства подается сигнал готовности принять следующее  число в первый регистр 2. Процедура записи данных в блок оперативной  памяти 8 продолжается до подачи на четвертый вход устройства сигнала об окончании ввода данных, по которому устройство переключается в режим ранжирования чисел и выдачи результата. Для пояснения работы устройства в режиме регистрации чисел на фигуре 5 представлены временные диаграммы сигналов основных блоков и узлов. Сигналы S1, S2 и S3 представляют, соответственно, сигналы с выхода генератора тактовых импульсов 22 (фиг.3), сигнал установки триггера пуска-останова 21 (фиг.3),   сигнал на прямом выходе триггера пуска-останова 21 (фиг.3). Сигналы: I901-I904 соответствуют сигналам на входах блока управления 9 (фиг. 3), а сигналы O903-O913 соответствуют сигналам на выходе блока управления 9 (фиг. 3).
В режиме 2 устройство работает следующим образом.  При подаче на вход 4 устройства сигнала об окончании ввода данных с выходов 1, 2 и 5 блока управления 9, соответственно: на счетный вход счетчика адреса 3, декрементирующий вход реверсивного счетчика поступающих чисел 1 и управляющий вход второго блока коммутатора 6 - подаются сигналы   инкрементации счетчика адреса 3, декрементации  счетчика поступающих чисел 1 и выдачи содержимого счетчика адреса 3 на адресные входы блока оперативной  памяти 8. С выходов 6 и 7 блока управления 9 на входы блока оперативной  памяти 8,   второго  регистра 10 подаются, соответственно, сигналы чтения содержимого блока памяти 8 и занесения его во  второй регистр 10. В случае обнаружения в содержимом ячеек памяти разрядов с единичной информацией на счетный вход счетчика рангов чисел 16 посредством многовходового элемента ИЛИ 14 и второго логического элемента И 13 с выхода 12 блока управления 9 подается счетный импульс. При этом на выход 2 устройства поступает код ранга числа. Далее на управляющий сдвиговый вход второго регистра 10 и счетный вход счетчика определения порядковых номеров чисел 11 с выхода 9 блока управления 9 поступает сигнал, по которому во втором  регистре 10 производится сдвиг содержимого в сторону младших разрядов, а в счетчике определения порядковых номеров  чисел 11 - инкрементация его содержимого. Наличие единичного значения в младшем разряде второго  регистра 10  позволяет посредством разрешающего сигнала с выхода 11 блока управления 9, первого логического элемента И 12 и третьего блока коммутации 15  подать на выход 1 устройства соответствующий двоичный код порядкового номера числа, а на выход 4 устройства - сигнал о готовности считывания с выходов 1 и 2 устройства результатов ранжирования. Сигналы сдвига и определения разряда с единичным кодом поступают до обнуления всех разрядов второго  регистра 10 и подачи нулевого сигнала с выхода многовходового логического элемента ИЛИ 14 на управляющий вход 6 блока управления 9. При этом на сбросовый вход счетчика определения порядковых номеров  чисел 11  с выхода 10 блока управления 9 поступает сигнал сброса содержимого счетчика. Далее процедура перебора адресов блока оперативной  памяти 8 продолжается до обнуления содержимого реверсивного счетчика поступающих чисел 1. При этом с выхода младшего разряда дешифратора порядковых номеров поступающих чисел 4 на второй вход блока управления 9 поступает единичный сигнал о завершении режима ранжирования и выдачи результатов. Таким образом, на выход 2 устройства  последовательно по мере возрастания значения ранга поступают все коды рангов чисел, а на выход 1 устройства – соответствующие рангам порядковые номера чисел в исходной последовательности. Для пояснения работы устройства в режиме ранжирования и выдачи результата на фигуре 6 представлены временные диаграммы сигналов основных блоков и узлов устройства. Условные обозначения сигналов аналогичны обозначениям из фиг.5. Сигналы, выделенные темным цветом, соответствуют единицам совокупного унарного кода содержимого блока памяти 8 (фиг.1).
Для пояснения принципа работы устройства приводится пример, представленный в таблице 1.
Допустим, что на вход устройства поступает последовательно пять чисел. Значения чисел заданы произвольно, например: 10, 15, 6, 15 и 1. Допустим, что разрядность реверсивного счетчика 1 поступающих чисел равна, 4 при этом использован дешифратор 4 порядковых номеров поступающих чисел, имеющий  4 входа и 16 выходов. В таблице 1 в строках 4-8 представлены данные на этапе получения унарных кодов  порядковых номеров чисел на выходах дешифратора 4 порядковых номеров поступающих чисел и определения адресов для записи этих кодов в блоке оперативной памяти 8 по величинам значений чисел.
Таблица 1 – Пример работы устройства
В строках 11-14 в колонках 3-5 представлены результаты ранжирования чисел по зарегистрированным в блоке оперативной памяти 8 кодам порядковых номеров  чисел, представленным в колонках 6-21. По данным строк 11-14 видно, что ранжирование произведено в порядке увеличения значений чисел (колонка 5), значения чисел определяют адреса ячеек. Всего определено 4 ранга, причем числа с порядковыми номерами 2 и 4 имеют одинаковую величину и соответствуют  рангу под номером 4. В строке 11 в колонках 19 и 17 зарегистрированы в виде единиц порядковые номера  чисел 2 и 4.
Таким образом, предлагаемое устройство, в отличие от известного, имеет большую универсальность, оно позволяет: регистрировать, представлять номера чисел из  исходной последовательности, ранжировать без  потерь чисел с минимальным значением, учитывать порядок поступления и ранжирование нескольких  чисел  одинаковой величины.
Достоинством предлагаемого устройства также является: высокая производительность, обусловленная тем, что процесс ранжирования осуществляется без дополнительных операций сравнения данных и поиска максимальных и минимальных значений, завершается  непосредственно после чтения из блока оперативной памяти последнего ранжируемого числа без перебора всех адресов памяти устройства.
Изобретение может быть использовано в системах распознавания образов для ранжирования образов по числовым оценкам близости их к неизвестному образу. Например, в качестве распознаваемых образов могут быть буквы алфавита, при этом ранг каждой буквы из алфавита свидетельствует о мере близости ее к распознаваемой букве. В другом примере ранг может соответствовать частоте встречаемости различных букв алфавита в тексте. В данных примерах в устройстве ранжирования чисел буква определяется по ее порядковому номеру в последовательности букв, а значение числа характеризует ранг буквы. Устройство может использовано в системах  защиты информации для оперативного ранжирования рисков угроз при построении моделей угроз, а также при решении других задач,  связанных с управлением рисками.
Устройство может быть реализовано на доступной элементной базе  электронных микросхем. В частности, блок памяти 6 может быть реализован на базе микросхем серии К565РУ1, а остальные блоки устройства на базе типовых микросхем серии К155.