Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf

* '

■ •

4-

91

§ 4-5. Повышение надежности схем

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

'рассматриваются как составляющие логического вектора Х т. Индекс т используется для обозначения размерности про­ странства, в котором определен данный вектор. Выходы схемы

{^і» Уit• * •> У$

рассматриваются как составляющие вектора — результата Р; Действие логической схемы можно представить в виде свя­ зей групп точек пространства {Хт ) с точками пространства

F (Х т ), где

P = F p T ).

На рис. 4-7 схематически изображена сетка связей для схемы сумматора, реализующего функцию F ( X S) = У2. Ос­ нову анализа логических схем составляет деление их на че­ тыре класса в соответствии с тем, каков действительный ди­ скретный уровень выходного сигнала:

1.Выходной сигнал может восприниматься как 1, при этом должен быть правильный выходной сигнал 1.

2.Выходной сигнал воспринимается как 1, тогда как пра­ вильный, сигнал должен быть 0.

3.Выходно^ сигнал воспринимается как 0, тогда как пра­ вильный, должен быть 1.

4.Выходной сигнал воспринимается как 0, тогда как пра­ вильный должен быть 0.

Зная распределение вероятностей выходных уровней для элемента, можно определить вероятность попадания элемен­ та в каждый из этих классов схем. Обозначаются вероятно­ сти для классов 1 4 соответственно как р (1/1), р (1/0),

92.

р (0/1) и р (0/0). Элементы, для которых (1/0) и (0/1) не равны 0, называются элементами «с помехами» или «шумя­ щими». Используя этИ' вероятности, можно построить модель логического элемента «с помехами».

Эта модель будет разбита на 2 секции; за функциональ­ ной схемой, не учитывающей вероятности, следует вероят-

ностная, нефункциональная часть схемы. Для упрощения по­ следующего рассуждения вводятся дополнительные предпо­ ложения:

Наихудший случай будет, если р выбрать равной большей из двух вероятностей попадания схемы в классы 2 и 3. Удоб­ но назвать событие, состоящее в попадании схемы в классы 2 и 3j ошибками, а р — вероятностью ошибки устройства. Если предположить, что причины отказов таковы, что ошиб­ ки каждого элемента статистически не зависимы от ошибок других элементов, то эта вероятностная модель может быть использована для определения поведения параллельной си­ стемы «шумящих» элементов. Здесь выходы «шумящей» схемы

fo* г2* . . . 2ft*]

\

рассматриваются как составляющие выходного вектора Zk. Отказ элемента приведет к тому, что каждый вектор Z* бу­ дет связан болре чем с одним вектором — результатом У*.

93’

1

На рис. 4-8 показана «шумящая» Модель сумматора.

По «шумящей» модели определим граф G —<^V, t/> связности выходных величин (У) при наличии ошибок. Каж­ дой вершине щ еѴ сопоставим во взаимно-однозначное со­ ответствие выходной вектор, и две вершины щ и щ соединим ребром, если вероятность получения вектора У* вместо Yj

X

Рис. 4-8

.или наоборот вектора Yj вместо У,- является не нулевой ве­ личиной. Очевидно, схема корректирует 5 ошибок, если граф связности представляет собой к изолированных дуг при ошибках, в s разрядах. Построение такого графа возможно, если увеличить размерность пространств У и Z от k до не­ которого п.

Например, если выходные векторы 11, 10, 01, 00 в рас­ сматриваемом сумматоре закодировать как

94

I

Г л а в а 5

Ав т о м а т и з а ц и я п р о ц е с с а с и н т е з а

ав т о м а т о в

§5-1. Приближенная оценка трудоемкости вычислительного процесса

При синтезе реальных автоматов объем вычислений ста­ новится настолько большим, что необходимо применение современных ЦВМ при решении задачи синтеза автоматов.

Представим процесс решения задачи синтеза в виде де­ рева, корень которого отмечен исходными данными; верши­ на, не являющаяся корнем, отмечена промежуточными или окончательными результатами, а дуги — возможными направ­ лениями процесса решения. Тогда критерий синтеза задаст подмножество мажорант, каждая из которых отмечена авто­ матом, удовлетворяющим заданным ограничениям. В процесqe решения будет построен путь от корня к одной из выде­ ленных мажорант.

Трудоемкость Т (А (п, s, m) ) нахождения искомого пути ориентировочно оценим двоичным логарифмом «веса» дере­ ва. Полагая, что выбор одной из ,дуг, смежной только что построенной дуге, равновероятен, имеем

где A (n ,s,m ) — автоматный оператор, реализующийся син­ тезируемой логической структурой;

‘п — число входных переменных; 5 — число каналов обратной связи; m — число выходных переменных.

tvj — отношение числа всех возможных направлений про­ цесса решения к числу направлений, удовлетворяющих за­ данному критерию, на j- м ярусе дерева. Очевидно, /,,/ яв­ ляется функцией критерия качества С

^/(С)

96

где tѳ/ — число элементарных действий (соответствующее дуге), необходимое для решения задачи синтеза на /-м ярусе;

te j— число элементарных символов (бит), необходимые для представления информации о функциониро­ вании автомата на /-м ярусе;

бі —весовой коэффициент компоненты произведения Іц. Суммирование проводится по всем ярусам.

Под информационными Ѳ и п характеристиками языка понимаем соответственно

(5-2)

(5-3)

где QB — верхняя граница количества элементарных дейст­ вий, необходимого для синтеза автомата, удовлет­ воряющего критерию синтеза С и реализующего заданный автоматный оператор;

Q* —верхняя граница количества элементарных симво­ лов (бит), необходимого для представления задан­ ного оператора А ;

М —количество представимой информации (под коли­ чеством представимой информации понимаем дво­ ичный логарифм числа возможных состояний реа­

лизуемого автоматного оператора).

К определению Qe, Q * и М необходимо в конце фразы добавить слово «на рассматриваемом участке а вычислитель­ ного процесса»; участок а интерпретируется некоторым пу­ тем на рассматриваемом дереве.

ный ярус дерева, то Ѳ.,- и itj будут показывать соответственно скорость роста Qe и Q* и геометрически будут соответство­