Устройство для анализа потоков случайных чисел Советский патент 1992 года по МПК G06F15/36 

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

Известно устройство для определения медианы, содержащее источник чисел, блок управления и блок анализа чисел

Недостатками данного устройства являются низкая точность оценки медианы и ограниченные функциональные возможности, что делает невозможным использовать устройство в отказоустойчивых управляющих вычислительных системах

Наиболее близким по технической реализации является устройство для определения медианы, содержащее источник чисел (блок формирования входной информации) и блок управления. Устройство определяет медиану из нечетного количества чисел, пу тем выбора среднего числа из упорядоченного массива

Недостатками данного устройства также являются низкая точность оценки медианы и ограниченные функциональные возможности, что делает устройство неприемлемым для использования в отказоустойчивых управляющих вычислительных системах,

Низкая точность обусловлена тем. что оценка медианы определяется выбором среднего числа из упорядоченного массива

М

без учета состояния исправности источников чисел,

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

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

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

Устройство для анализа потоков случайных чисел содержит: группы 1--4 элементов И; группу 5 элементов НЕ; элемент 6 И; счетчик 7; узлы 8-11 сравнения (УС); узел 12 обнаружения равных чисел (УОРЧ12); счетчик 13; группу 14 элементов задержки; дешифратор 15; узлы 16-19 определения адресов (УОА), каждый из которых содержит группу 20 элементов И и группу 21 триггеров; регистры 22-25; сумматоры 26-28; узлы 29-31 сравнения; триггеры 32-34; элемент 35 задержки; дешифратор 36 со стробмроваиием; элементы 37, 38 ИЛИ; блок 39 мультиплексоров, арифметические узлы 40-42; группы 43-47 элементов И; группу 48 элементов ИЛИ; выходные триггеры 49-52. Кроме того, на чертеже обозна- чены;вход 53 пуска; тактовый вход 54; информационные входы 55-58; вход 59 сброса; вход 60 для ввода значения допустимого отклонения; информационный выход 61; управляющие выходы 62-66.

Устройство работает следующим образом.

В начале работы на вход 59 устройства поступает импульс сброса. С окончанием этого импульса на выходах триггеров 49-52 устанавливаются нулевые потенциалы, которые означают, что все источники чисел исправны. Периодически на информационные входы 55-58 одновременно в параллельных кодах поступают четыре (М-1)-раэрядные числа от соответствующих источников чисел. Затем с помощью групп 1-4 элементов I/I и элементов 5.1-5.4 НЕ на основе управляющих сигналов, поступающих от выходов соответствующих триггеров 49-52, формируются четыре М-разрядных числа. Это про- .исходит следующим образом. Сначала

рассмотрим случай, когда все источники чисел исправны. В таком случае все сигналы неисправности на выходах 63-66 имеют нулевые потенциалы, которые поступают на

входы BN соответствующих УС 8-11 и через элементы 5.1-5.4 НЕ на вторые входы элементов И соответствующих групп 1-4 и открывают их. Далее, числа, установленные на информационных входах 55-58 через от0 крытые элементы И проходят на входы Bi- BN-I соответствующих УС 8-11. В случае отказа некоторых источников чисел, соответствующие управляющие сигналы на выходах 63-66 имеют единичные потенциалы,

5 которые через соответствующие элементы 5.1-5.4 НЕ поступают на вторые входы элементов И соответствующих групп 1-4 и блокируют их. Следовательно, числа, установленные на входах 55-58 не проходят на

0 входы BI-BN-I соответствующих УС 8-11, на входах BN, которых установлены единичные потенциалы от соответствующих выходов 63-66 устройства.

Таким образом, в случае отсутствия

5 отказавших источников чисел на входы BI-BN-I УС 8-11 проходят числа, установленные на соответствующих информационных входах 55-58, без изменения, а на входах BN всех УС устанавливается нулевой

0 потенциал. При отказе некоторых источников чисел, в качестве числа, от этих источников, на входы ВЧ-BN соответствующих УС 8-11 выдаются числа, которые в М-х разрядах имеют единичные потенциалы, а на ос5 тальных разрядах 1-(М-1)--нулевые потенциалы, В дальнейшем числа, которые имеют в N-x разрядах единичный потенциал, будем обозначать оо (бесконечность). Обозначение се соответствует самому

0 большому значению чисел, которые поступают на входы BI-BN УС 8-11,

На вход 53 подается последовательность импульсов пуска, а на вход 54 - последовательность тактовых импульсов. При

5 этом частота аи импульсов пуска должна соответствовать частоте поступления данных от источников чисел, а частота о# тактовых импульсов должна выбираться из условия

0

-.N

W2 2 Ш1 где N-разрядность чисел,

С появлением импульса пуска счетчики 7, 13 и группа 21 триггеров УОА 16-19 обнуляются и устройство готово к следующему рабочему циклу. При этом на выходе отсутствие равных чисел (ОРЧ)-УОРЧ12 4 устанавливается единичный потенциал, который разрешает прохождение импульсов с тактового входа 54 через элемент 6 14 на вход С счетчика 7. С приходом каждого тактового импульса содержимое счетчика 7

увеличивается на единицу, а состояние других элементов не изменяется до тех пор, пока не установится число на выходе счетчика 7, равное меньшему из чисел, поступающих на входы BI-BN УС 8-11. С наступлением этого момента на выходе соответствующего УС 8-11 устанавливается единичный потенциал. При этом на выходе ОРЧ УОРЧ12 устанавливается нулевой потенциал, запрещающий прохождение импульсов через элемент 6 И, а тактовые импульсы, поступающие на вход С УОРЧ12, обеспечивают выделение одного импульса на выходе наличие равных чисел (НРЧ), который поступает на тактовый вход С счетчика 13 и на его выходных разрядах устанавливает соответствующий код. Этот код поступает на входы дешифратора 15, при этом на соответствующем выходе дешифратора устанавливается единичный потенциал, разрешающий запись числа с выхода счетчика 7 в соответствующий регистр 22- 25 и открывающий элементы И группы 20 соответствующего УОА 16-19. Информация с соответствующего информационного выхода Yi-Y4 УОРЧ12 через соответствующий элемент задержки группы 14 и через соответствующий открытый элемент И группы 20 соответствующего УОА 16-19 записывается в соответствующий триггер группы 21 и с его выхода поступает на соответствующий разряд группы управляющих выходов УОА 16-19, следовательно, на соответствующий вход блока 39 мультиплексоров и определяет номер источника чисел, который передал соответствующее число упорядоченного массива, записанное В соответствующий регистр 22-25. Последовательность УОА 16-19 соответствует последовательности номеров чисел упорядоченного массива или последовательности регистров 22-25. а последовательность триггеров группы 21 всех УОА 16-19 соответствует последовательности номеров источников чисел. Например, появление сигнала высокого уровня на выходе триггера 21.3 УОА16 означает, что первое число упорядоченного массива передано от третьего источника чисел.

Время задержки группы 14 элементов должно выбираться из условия

т Г|з + 15 : где пз - время задержки счетчика 13;

Г15 - время задержки дешифратора 15.

Устройство аналогично осуществляет запись в регистры 22-25 всех нарастающих чисел вплоть до максимального, а также определяет с помощью групп управляющих сигналов УОА 16-19, которые поступают на соответствующие входы блока 39 мультиплексоров, номера источников, передавших соответствующие числа упорядоченною массива.

Числа упорядоченного по возрастанию

массива с выходов регистров 22 -25 в параллельных кодах поступают на соответствующие входы сумматоров 26-28, арифметических узлов 40-42 и группы 43 элементов И.

Предположим, что на выходах регистров 22-25 установлены числа а, Ь, с, d упорядоченного массива, а на вход 60 поступает число д , где д - значение допустимого отклонения разности любых двух

соседних чисел упорядоченного массива. При этом на соответствующие информационные входы сумматоров 26-28 соответственно поступают числа а, Ь; Ь, с и с, d. В них вычисляются соответствующие выражения:

(b-a); (c-d) и (d-c). Результаты вычисления поступают на первую группу входов соответствующих УС 29-31, на вторую группу входов которых поступает число д. Далее, УС 29-31 соответственно реализуют следующие арифметические выражения: (b-а) 5 (c-d) д и (d-c) S д. Дешифратор 37 со стро- бированием в зависимости от результатов выполнения этих арифметических выражений формирует управляющие сигналы. Это

происходит следующим образом. Если выше указанные арифметические выражения выполняются, то на первых выходах УС 29-31 устанавливаются единичные потенциалы, которые устанавливают соответствующие триггеры 32-34 в нулевое состояние, в противном случае единичные потенциалы появляются на вторых выходах, которые устанавливают соответствующие триггеры в единичное состояние. В зависимости от сигналов, установленных на прямых выходах триггеров 32-34, дешифратор 36 с поступлением через элемента 35 задержки стробиру- ющего импульса на соответствующем выходном разряде формирует единичный

потенциал.

Время задержки элемента 35 должно выбираться из условия

г - ту 4- гс + туе + гт ; где гу - время, за которое проводится упорядочивание четырех N разрядных чисел:

гс - время для реализации суммирования в 26-28;

гус - время для реализации сравнения в УС 29-31;

fj - время задержки триггеров 32-34.

Соответствие между сигналами, установленными на первых и вторых выходах УС 29-31, на прямых выходах триггеров 32-34 и на выходных разрядах 1-8 группы управляющих выходов дешифратора 36 со стро- бированием, а также назначение этих управляющих сигналов приведены в таблице.

В таблице обозначены; f 1 и h первый и второй выходы УС 29, тз и f4 - первый и второй выходы УС 30 и fs и fe - первый и второй выходы УС 31, а также Fi, F2 и Рз - соответственно прямые выходы триггеров 32-34. О и 1 в таблице означают, что сигналы на соответствующих выходах имеют соответственно нулевые и единичные потенциалы.

Выше отметили, что если источник неисправен, то в качестве информации от этого источника передается оо, Поэтому, если некоторые числа упорядоченного массива равны со то, следовательно, соответствующие арифметические выражения, где некоторые аргументы равны будут выполняться и на вторых выходах соответствующих УС будут появляться единичные потенциалы. Дешифратор 36 на основе этих потенциалов формирует соответствующие управляющие сигналы, которые не позволяют использование числа от неисправных источников при определении оценки медианы.

Рассмотрим процедуру определения оценки медианы по трем выше перечисленным алгоритмам с помощью устройства.

Алгоритм 1: Если все источники чисел исправны, то за медиану необходимо выбирать второе число упорядоченного массива. Согласно таблице, исправным состояниям всех источников чисел соответствует управляющий сигнал на выходе 1 дешифратора 36. В таком случае за оценку медианы, согласно алгоритму, необходимо выбирать значение . Это реализуется следующим образом. Управляющий сигнал через элемент 37 ИЛИ поступает на вторые входы элементов И группы 43 и открывает их. Следовательно, значения разрядов числа Ь, установленные на первых входах элементов И группы 43, через элементы ИЛИ группы 48 выдаются на соответствующие разряды группы 61 информационных выходов устройства.

Алгоритм 2: Если три источника чисел исправны, то за медиану необходимо выбирать среднее число упорядоченного массива. Согласно таблице, исправным состоянием трех источников чисел соответствуют управляющие сигналы на выходах 2 и 5 дешифратора 36;

а) Управляющий сигнал на выходе 2 дешифратора 36 означает, что оценку медианы необходимо выбирать из следующих чисел: а, Ь, с. В таком случае за оценку медианы, согласно алгоритму, необходимо

выбирать значение . Реализация этого алгоритма аналогично предыдущему случаю.

б) Управляющий сигнал на выходе 5 дешифратора 36 означает, что оценку медианы необходимо выбирать из следующих чисел: Ь. с, d. В таком случае за оценку медианы, согласно алгоритму, необходимо выбирать значение . Это реализуется

0 следующим образом. Управляющий сигнал с выхода 5 дешифратора 36 поступает на втооые входы элементов И группы 45 и открывает их. Следовательно, значения разрядов числа с, установленные на первых

5 входах элементов И группы 45, через элементы ИЛИ группы 48 выдаются на соответствующие разряды группы 61 информационных выходов устройства.

Алгоритм 3: Если два источника чисел

0 исправны, то за медиану необходимо выбирать среднее арифметическое значение этих двух чисел. Согласно таблице, исправным состоянием двух источников чисел соответствуют четыре управляющих сигнала

5 на выходах 3, 4, 6 и 7 дешифратора 36.

а)Управляющие сигналы на выходах 3 и 4 дешифратора 36 означают, что оценку медианы необходимо выбирать из следующих чисел: а, Ь. В таком случае за оценку медиа0 ны, согласно алгоритму, необходимо выбирать значение Ме(а+Ь)/2. Это реализуется следующим образом. На соответствующие информационные входы арифметического узла 40 поступают числа:а, Ь. Далее, он вы5 числяет арифметическое выражение (а+Ь)/2 и выдает результат вычисления на первые входы элементов И группы 44. Управляющие сигналы с выходов 3 и 4 дешифратора 36 через элемент 38 ИЛИ поступают на вто0 рые входы элементов И группы 44 и открывают их. Следовательно, разряды значения (а+Ь)/2, установленные на первых входах элементов И группы 44, через элементы ИЛИ группы 48 выдаются на соответствую5 щие разряды группы 61 информационных выходов устройства.

б)Управляющий сигнал на выходе 6 дешифратора 36 означает, что оценку медианы необходимо выбирать из следующих

0 чисел: Ь, с. В таком случае за оценку медианы, согласно алгоритму, необходимо выбирать значение Ме(Ь+с)/2. Это реализуется следующим образом. На соответствующие информационные входы арифметического

5 узла 41 поступают числа:Ь, с. Далее, он вычисляет арифметическое выражение (Ь+с)/2 и выдает результат вычисления на первые входы элементов И группы 46. Управляющий сигнал с выхода б дешифратора 36 поступает на вторые входы элемента И группы

46 и открывает их Следовательно, разряды значения (Ь+с)/2, установленные на первых входах элементов И группы 46, через элементы ИЛИ группы 48 выдаются на соответствующие разряды группы 61 информационных выходов устройства.

в) Управляющий сигнал на выходе 7 дешифратора 36 означает, что оценку медианы необходимо выбирать из следующих чисел: с, d. В таком случае за оценку медианы, согласно алгоритму, необходимо выбирать значение Me(c+d)/2. Это реализуется следующим образом. На соответствующие информационные входы арифметического узла 42 поступают числа: с, d. Далее, он вычисляет арифметическое выражение (c+d)/2 и выдает результат вычисления на первые входы элементов И группы 47. Управляющий сигнал с выхода 7 дешифратора 36 поступает на вторые входы элементов И группы 47 и открывает их. Следовательно, разряды значения (c+d)/2, установленные на первых входах элементов И группы 47, через элементы ИЛИ группы 48 выдаются на соответствующие разряды группы 61 информационных выходов устройства.

Блок 39 мультиплексоров на основе управляющих сигналов, поступающие: от всех УОА 16-19, определяющие номера источников чисел, которые выдали соответствующие числа а, Ь, с, d упорядоченного массива и с выходов 1-7 дешифратора 36, определяющие состояние отказа соответствующих источников чисел формирует сигналы неисправности соответствующих источников чисел и записывает эти сигналы в соответствующие триггеры 49-52, следовательно, эти сигналы с выходов соответствующих триггеров поступают на соответствующие управляющие выходы 63-66 устройства.

Согласно таблице, управляющие сигналы на выходах 2, 3, 4 и 6 дешифратора 36 означают, что источник, который выдал число d, отказал. Необходимо определить номер этого источника и установить соответствующий триггер 49-52 в единичное состояние. Это реализуется следующим образом. Управляющие сигналы с выхода 2, 3, 4 и 6 дешифратора 36 поступают на соответствующие входы блока 39 мультиплексоров. Числу d в упорядоченном массиве соответствует УОА19. Следовательно, при поступлении соответствующего управляющего сигнала, с выходов триггеров группы 21 УОА19 на соответствующие входы, блок 39 мультиплексоров формирует на соответствующем выходе управляющий сигнал, который определяет номер отказавшего источника чисел.

Согласно таблице, управляющие сигналы на выходах 3 и 4 дешифратора 36 означают, что источник, который выдал число с, отказал, управляющий сигнал на выходе 7 дешифратора 36 означает, что источник, который выдал число Ь, отказал и управляющие сигналы на выходах 5, 6 и 7 дешифратора 36 означают, что источник, который выдал число а, отказал. Определение

0 номеров отказавших источников чисел в соответствующих случаях реализуется аналогично предыдущему.

При отказе трех источников чисел на выходе 8 дешифратора 36 и, следовательно,

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

0 Таким образом, устройство для анализа потоков случайных чисел позволяет повысить точность оценки медианы путем определения медианы по трем алгоритмам в зависимости от состояния исправности ис5 точников чисел, расширить функциональные возможности за счет формирования сигналов неисправности и сигнала предварительное состояние, а также за счет блокировки отказавших источников, что дает

0 возможность использовать данное устройство в составах управляющих отказоустойчивых многомашинных и многопроцессорных вычислительных систем.

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

5 Устройство для анализа потоков случайных чисел, содержащее два счетчика, первую группу блоков элементов И, первый элемент И первой группы, первую группу блоков сравнения, элемент задержки, два

0 регистра, три триггера, первый элемент ИЛИ и элемент И, причем информационные входы блоков элементов И первой группы являются информационными входами устройства, а выходы подключены к первым

5 входам одноименных блоков сравнения первой группы, вторые входы которых соединены с выходом первого счетчика, счетный вход которого подключен к выходу элемента И, первый вход которого является

0 тактовым входом устройства, выход первого счетчика подключен к информационному входу первого регистра, отличающее- с я тем, что, с целью повышения точности, в него введены группа элементов НЕ, допол5 нительно элементы И первой группы, группа элементов И, вторая группа блоков элементов И, два дешифратора, два регистра, две группы триггеров, группа сумматоров, вторая группа блоков сравнения, группа элементов задержки, второй элемент ИЛИ. группа арифметических блоков, блок элементов ИЛИ. узел упорядочения чисел и блок мультиплексора, выходы которого соединены соответственно с D-входами триггеров первой группы, прямые выходы которых являются выходами устройства, прямой выход каждого триггера первой группы соединен с тактовым входом одноименного блока сравнения первой группы и через соответствующий элемент НЕ группы с управляющим входом одноименного блока элементов И первой группы, выходы Равно блоков сравнения первой группы подключены к информационным входам узла упорядочения чисел, тактовый вход которого соединен с тактовым входом устройства, выходы признаков Отсутствие равных чисел и Наличие равных чисел узла упорядочения чисел подключены соответственно к второму входу элемента И и счетному входу второго счетчика, информационные выходы узла упорядочения чисел через одноименные элементы задержки группы соединены с первыми входами одноименных элементов И групп, выходы элементов И каждой группы подключены к D-входам одноименных триггеров последующей группы, выходы триггеров всех групп, кроме первой, соединены с информационными входами блока мультиплексоров, вход пуска устройства соединен с входами сброса счетчиков, с R-входами триггеров всех групп, кроме первой и, через элемент задержки подключен к входу стробирования первого дешифратора, выходы второго счетчика соединены с входами второго дешифратора, выходы которого подключены соответственно к вторым входам элементов И групп и к входам синхронизации всех регистров, информационные входы второго, третьего и четвертого регистров соединены

с выходом первого счетчика, выход первого регистра подключен к первым входам первого сумматора и первого арифметического блока группы, выход которого соединен с

информационным входом второго блока элементов И второй группы, выход второго регистра подключен к второму входу первого сумматора группы и первому входу второго сумматора группы, к второму входу

первого арифметического блока группы, к первому входу второго арифметического блока группы и к информационному входу первого блока элементов И второй группы, выход третьего регистра соединен с вторым

входом второго сумматора группы, с первым входом третьего сумматора группы, с вторым входом второго арифметического блока группы, с первым входом третьего арифметического блока группы и с информационным входом третьего блока элементов И второй группы, выход четвертого регистра подключен к вторым входам третьего сумматора и третьего арифметического блока группы, выходы сумматоров группы

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

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

Фил 2