close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
КОМПЬЮТЕРНАЯ
ИНЖЕНЕРИЯ И
ТЕХНИЧЕСКАЯ
ДИАГНОСТИКА
УДК 681.325.59:519.6
МЕТОД ОЦЕНКИ
АВТОКОРРЕКТИРУЮЩИХ
СВОЙСТВ ПОРАЗРЯДНЫХ
ЛОГИЧЕСКИХ ОПЕРАЦИЙ
ТАРАСЕНКО В.П., ТАРАСЕНКО-КЛЯТЧЕНКО О.В.
Предлагается методика оценки автокорректирующих
свойств поразрядных логических операций путем вычисления вероятности получения правильного результата при заданных вероятностях искажений цифр
операндов.
Для обеспечения высокой надежности специализированных компьютерных систем [1] важное значение имеет не только создание высоконадежных
инструментальных средств (как аппаратных, так и
программных), но и знание характера влияния
входной информации с искажениями на достоверность результатов её обработки. Далее искажением
цифры xi некоторого операнда X=(x1, x2,..., xn-1,xn),
xiЏ{0,1}, i=1,...,n будем называть произвольную
замену истинного значения цифры xi на постоянное
(например, 0 или 1), инверсное или еще какое-либо
детерминированное значение. Число возможных
искажений при этом равно k. Такое определение
искажения обусловлено характером преобладающих ошибок в компьютерных системах [2] из-за
константных неисправностей в аппаратных средствах, являющихся источниками информации, а
также случайными сбоями, ошибками округления
и трансформированными погрешностями последовательностей предыдущих операций [3,4].
Однако наличие искажений во входной информации еще не означает, что результат работы некоторого операционного устройства (ОУ) будет неправильным, так как сами операции (и, соответственно, исправные ОУ) часто обладают корректирующими свойствами. Дальше будем называть автокоррекцией явление, состоящее в формировании
ОУ правильных результатов при действии на его
входах операндов с искажениями. Примером операции с автокоррекцией может служить логическое
умножение двух операндов X1=(x11, x12,...,x1n-1, x1n)
и X2=(x21, x22,..., x2n-1, x2n), где x1i, x2i Џ {0,1},
i=1,...,n. Здесь для каждой пары фиксированных
значений операндов (цифр) x1i и x2i вида (1,0) их
РИ, 2001, № 1
входные искажения вида (0,0) и (0,1) не дают
неправильного результата, и лишь искажение вида
(1,1) приводит к ошибке. Другим примером может
быть тот факт, что сумма по модулю 2 двух
искаженных двоичных цифр равна истинной сумме
неискаженных цифр.
Количественной характеристикой автокоррекции
может служить вероятность появления правильного результата на выходе ОУ при заданных вероятностях появления неискаженных и искаженных
цифр на его входе. Пусть ОУ реализует некоторое
функциональное преобразование, описываемое
системой логических функций вида
y1=f1(x1, x2,..., xn-1, xn),
y2=f2(x1, x2,..., xn-1, xn),
..........................................
(1)
ym=fm(x1, x2,..., xn-1, xn),
где xi, yi Џ{0,1}, i=1,...,n, j=1,...,m. Далее в подходящих случаях систему (1) будем записывать как
Y=F(X), где Y=(y1, y2,..., ym-1, ym), F=(f1,f2,...,fm-1,
fm), X=(x1, x2,..., xn-1, xn). Поставим в соответствие
каждой цифре xi операнда X набор вероятностей
Qi=(pi0, pi1,..., pi k-1, pik), где компонента pi0 есть
вероятность появления на входе ОУ неискаженного
(истинного) значения цифры xi, а компоненты pir,
r=1,...,k представляют собой вероятность появления на входах ОУ всех k искаженных значений xi.
При этом выполняется условие
так как перечисленные компоненты набора Qi
соответствуют всем k+1 возможным состояниям
входа xi ОУ и образуют полную группу событий [5].
В общем случае на входах ОУ возможны m(k+1)n
состояний, образующих полную группу событий.
Очевидно, что с ростом k, m и, особенно, n это число
быстро увеличивается. Это, в свою очередь, снижает
практическую эффективность методов оценки вероятности получения правильного результата, ориентированных на перебор всех состояний полной
группы. Однако, как показано далее, в частных
случаях учет особенностей функционального преобразования Y=F(x) и реальных практических ограничений на величины k, m, n позволяет существенно
уменьшить число событий в полной группе.
Обозначим xi0 ? значение цифры xi без искажения
и xir , r=1,...,k - значение цифры xi с искажением
типа r. Тогда на основе системы (1) каждому выходу
ОУ yj, j=1,...,m, можно поставить в соответствие
систему из M=(k+1)n функций вида
yj0=fj(x10, x20,..., xn-10, xn0),
yj1=fj(x10, x20,..., xn-10, xn1),
yj2=fj(x10, x20,..., xn-10, xn2),
83
.................................. .
yjk=fj(x1
0,
x2
yjk+1=fj(x1
0,
0,...,
x2
xn-1
0,...,
0,
xn-1
xnk),
1,
(2)
xn0),
yjk+2=fj(x10, x20,..., xn-11, xn1),
...................................
yjM-1=fj(x1k, x2k,..., xn-1k, xnk).
Первое выражение в системе (2) соответствует
?образцовой? (т.е. без искажений на входах xi)
реализации ОУ функции yj. Остальные выражения
определяют значение yj при наличии соответствующих искажений цифр операндов. Поэтому можно
записать, что вероятности реализации функций
системы (2) составляют
Rj0=p10p20pn-10pn0,
Rj1=p10p20pn-10pn1,
Rj2=p10p20pn-10pn2,
.............................
Rjk=p10p20pn-10pnk,
(3)
ристику автокорректирующих свойств операций,
реализуемых ОУ.
Изложенный метод оценки вероятности правильной работы ОУ при наличии искажений операндов,
в принципе, применим для ОУ, реализующих
функциональное преобразование Y=F(X) любого
вида. Однако, как уже указывалось выше, наиболее
эффективным он может быть в частных случаях.
Одним из таких случаев есть реализация ОУ
поразрядных логических операций, когда результат операции в некотором j-м разряде, j=1,...,m, не
зависит от результатов этой операции в остальных
разрядах [7]. Поразрядность операций означает
разбиение множества разрядов операндов на непересекающиеся подмножества и реализацию отдельных функций fj от таких подмножеств. Отсутствие
межразрядных связей позволяет легко обобщить
для всего ОУ оценки вероятности правильной
работы, полученные для одного разряда, а также
для упрощения записей в дальнейших построениях
опустить индекс j.
Простейшие поразрядные операции получим в
случае, когда n=m, а система функций (1) имеет вид
f(x1), f(x2),..., f(xn-1), f(xn).
Rjk+1=p10p20pn-11pn0,
Rjk+2=p10p20pn-11pn1,
..............................
RjM-1=p1kp2kpn-1kpnk.
Функции системы (2) в дальнейшем удобно представлять в табличном виде. В каждой из таблиц для
функций yj1, yj2,..., yjM-2, yjM-1 может оказаться по sjk,
k=1,...,M-1 значений, совпадающих со значениями в
?образцовой? таблице для yj0. Очевидно, что 0dsjkd2n,
кроме того, sjk=0 означает полное несовпадение (и,
как следствие, отсутствие автокоррекции) таблиц для
yj0 и yjk, а sjk=2n ? полное совпадение (полную
автокоррекцию) таблиц для yj0 и yjk. Обозначим
вероятность получения правильного значения yj на
выходе ОУ как Pj. Тогда, исходя из формулы полной
вероятности [5], можно записать, что
Исходя из практических соображений положим,
что kd3. Это соответствует искажениям цифр операндов из-за константных неисправностей и инверсных ошибок. Далее будем считать, что p1 ?
вероятность единичного константного искажения,
p2 ? вероятность нулевого константного искажения, p3 ? вероятность инверсного искажения цифры xi. Кроме того, p0+p1+p2+p3=1. Существует
всего одна нетривиальная логическая функция
одного аргумента [7] ? инверсия, для которой
система (2) будет иметь вид y0=x0, y1=x1, y2=x2,
y3=x 3.
Таблицы этих функций приведены на рис.1, где
совпадающие значения y0, y1, y2, y3 выделены
жирным шрифтом.
.
Для ОУ в целом вероятность получения правильного результата равна произведению вероятностей
получения правильного результата на каждом из
его выходов, т.е.
x0
0
1
1
0
0
1
0
x
y1
1
2
84
0
y0
.
Изложенное выше обладает всеми необходимыми
и существенными признаками метода [6], так как
позволяет на основе знаний о функциях F(x) ОУ и
о вероятностях истинных и искаженных значений
операндов на входе ОУ определить вероятности
появления правильных результатов на его выходе
и, тем самым, получить количественную характе-
x1
1
1
0
0
1
3
0
1
x
y2
y3
Рис.1
В этом случае система вероятностей (3) будет очень
простой:
РИ, 2001, № 1
R0=p0, R1=p1, R2=p2, R3=p3.
Из рис. 2 следует, что
s1=3, s2=3, s3=2, s4=3, s5=1, s6=3, s7=1, s8=3,
Непосредственно из рис.1 следует
s1=1, s2=1, s3=0.
s9=3, s10=3, s11=3, s12=2, s13=1, s14=3, s15=2.
Поэтому для поразрядной инверсии имеем
Следовательно, для поразрядной конъюнкции имеем:
P=p0+2-1(p1+p2).
P=p02+4-1(p12+3p22+2p32+6p0p1+ +6p0p2+4p0p3+
Как и следовало ожидать, инверсное искажение
операнда не влияет на вероятность правильного
результата, а зависимость P от p0, p1, p2 имеет
линейный характер. Если считать, что p1=p2=pc , а
также учесть, что p0+2pc=1, то нетрудно получить
P(p0)=0,5+0,5p0 и P(pc)=1-pc.
+6p1p2+2p1p3+6p2p3).
Это означает, что вероятность правильного результата на выходе инвертора в самом худшем случае
(p0=0, pc=0,5) не может быть ниже 0,5.
Рассмотрим теперь поразрядные операции с двумя
операндами. В этом случае n=2m, а система (1)
вырождается в систему вида
y1=f1(x1, x2), y2=f2(x3, x4),..., ym-1= fm-1(xn-3, xn-2),
ym=fm(xn-1, xn).
Предположим далее, что искажения операндов
обусловлены, главным образом, константными
неисправностями, т.е. p1, p2>>p3, p0+p1+p2=1 и,
кроме того, p1=p2=pc.
Тогда предыдущее выражение для P можно записать как
P(p0,pc)=p02+4-1(pc2+3pc2+6p0pc+6p0pc+6pc2)=
=p02+4-1(10pc2+12popc)= p02+2,5pc2+3p0pc.
Учитывая, что в рассматриваемом случае pc=0,5(1-p0), получим
P(po)=0,125p02+0,25p0+0,625.
y0=x10x20, y1=x10x21, y2=x10x22, y3=x10x23,
Таким образом, для поразрядной конъюнкции
зависимость P(p0) имеет квадратичный характер,
показанный на рис.3,а, причем при любой вероятности p0 вероятность P не может быть ниже 0,625.
Если теперь в выражении для P выполнить подстановку p0=1-2pc, то получим
y4=x11x20, y5=x11x21, y6=x11x22, y7=x11x23,
P(pc)=0,25pc2-pc+1.
Из 10 нетривиальных логических операций с двумя
операндами [7] рассмотрим вначале поразрядную
операцию конъюнкции. Для такой операции систему (2) можно записать как
y8=x12x20, y9=x12x21, y10=x12x22, y11=x12x23,
y12=x13x20, y13=x13x21, y14=x13x22, y15=x13x23.
Таблицы этих функций приведены на рис.2, где
совпадающие с y0 значения выделены жирным
шрифтом.
x20
x10
0
1
x21
1
1
1
1
1
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
0
0
y1
1
1
0
0
1
1
y4
x12
0
0
0
0
1
0
0
0
y12
1
1
0
0
0
0
0
0
1
0
y3
0
0
1
1
y6
0
0
y9
1
0
0
0
y2
y5
y8
x13
x23
0
y0
x11
x22
y10
1
0
y13
0
0
0
0
1
0
0
0
y15
Рис.2
Систему (3) применительно к этим функциям
можно записать как
R0=p10p20, R1=p10p21, R2=p10p22, R3=p10p23,
R4=p11p20, R5=p11p21, R6=p11p22, R7=p11p23,
R8=p12p20,R9=p12p21, R10=p12p22, R11=p12p23,
R12=p13p20,R13=p13p21,R14=p13p22,R15=p13p23.
РИ, 2001, № 1
P(p0,p3)=p02+4-1(2p32+4p0p3)=p02+0,5p32+p0p3.
При подстановке p3=1-p0 имеем (рис.3,б)
Подстановка p0=1-p3 дает результат (рис.3,б)
P(p3)=0,5p32-p3+1.
y11
0
0
y14
0
0
0
0
Рассмотрим теперь ситуацию, когда довлеющими
есть инверсные искажения операндов, т.е. p3>>p1,
p2, p0+p3=1. Тогда
P(p0)=0,5p02+0,5.
y7
0
0
Характер этой зависимости также показан на рис.
3,а. Примечательно, что даже при pc=0,5 (согласно
принятым допущениям pcd0,5) вероятность правильного результата больше 0,5.
Нетрудно убедиться в том, что для поразрядной
операции Шеффера выражение для Р и последующий его анализ будут точно такими же, как и для
поразрядной конъюнкции.
Аналогично изложенному выше можно показать,
что для поразрядных дизъюнкции и операции Пирса
P = p 02+ 4 -1( 3 p 12+ p 22+ 2 p 32+ 6 p 0p 1+ 6 p 0p 2+
+4p0p3+6p1p2+p1p3+2p2p3);
для поразрядных равнозначности и неравнозначности
P = p 02+ 4 -1( 2 p 12+ 2 p 22+ 4 p 32+ 4 p 0p 1+ 4 p 0p 2+
+4p1p2+4p1p2+4p2p3);
для поразрядных запрета и импликации
P = p 02+ 4 -1( 3 p 12+ 3 p 22+ 2 p 32+ 6 p 0p 1+ 6 p 0p 2+
+4p0p3+4p1p2+4p1p3+4p2p3).
85
Графические результаты анализа этих пар функций
приведены на рис. 3, в-з.
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
0
0.2 0.4 0.6 0.8
0
P(po)
P(pc)
0.2 0.4 0.6 0.8
P(po)
P(p3)
а
б
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
Таким образом, изложенный метод позволяет оценить естественные корректирующие свойства поразрядных логических операций по вероятности
получения правильного их результата при известных вероятностях входных искажений. Проведенный анализ показывает, что при любых вероятностях входных детерминированных искажений типа
?константа 0?, ?константа 1?, ?инверсия? вероятность получения правильного результата операций
поразрядной конъюнкции, операции Шеффера,
поразрядной дизъюнкции, операции Пирса, поразрядных равнозначности и неравнозначности, поразрядных запрета и импликации не ниже 0,5.
0
0.2 0.4 0.6 0.8
0
P(po)
P(pc)
0.2 0.4 0.6 0.8
P(po)
P(p3)
в
г
Литература: 1. Мельник А.О., Тарасенко В.П. Сучасні
ситуативно-методологічні аспекти створення спеціалізованих комп?ютерних систем // Наукові вісті НТУУ
?КПІ?. 1997. №1. С. 18-21. 2. Хаханов В.И., Кривуля Г.Ф.
Логическое моделирование цифровых устройств. К.:
УМК ВО, 1989. 147с. 3. Проектирование ЭЦВМ / Под
ред. С.А.Майорова. М.: Высш. шк., 1972. 344с. 4. Stummel
F. Rounding error analysis of elementary numerical
algorithms // ?Computing?. 1980. №2. P. 169-195. 5. Rump
S.M. Computer und Rechengenaugkeit // ?Electron.
Rechenanlag?. 1982. T. 24, №6. S. 268-277. 6. Гмурман В.Е.
Теория вероятностей и математическая статистика.
М.: Высшая школа, 1998. 480 с. 7. Самофалов К.Г.,
Корнейчук В.И., Тарасенко В.П. Цифровые ЭВМ. Теория и проектирование. К.: Вища шк., 1989. С. 424.
Поступила в редколлегию 07.07.2000
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
0
0.2 0.4 0.6 0.8
Рецензент: д-р техн. наук Володарский Е.Т.
0
P(po)
P(pc)
P(po)
P(p3)
д
е
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
0.2 0.4 0.6 0.8
0
0.2 0.4 0.6 0.8
P(po)
P(pc)
0
Тарасенко Владимир Петрович, д-р техн. наук, профессор, заведующий кафедрой специализированных компьютерных систем НТУУ ?КПИ?. Научные интересы:
компьютерная арифметика в специализированных
компьютерных системах. Адрес: Украина, 03056, Киев,
пр. Победы, 37, тел. (044) 274-3202.
Тарасенко-Клятченко Оксана Владимировна, аспирантка кафедры специализированных компьютерных систем НТУУ ?КПИ?. Научные интересы: компьютерная арифметика. Адрес: Украина, 03056, Киев, пр.
Победы, 37, тел. (044) 441-1436.
0.2 0.4 0.6 0.8
P(po)
P(p3)
ж
з
Рис.3
86
РИ, 2001, № 1
Документ
Категория
Без категории
Просмотров
5
Размер файла
1 011 Кб
Теги
логические, оценки, метод, поразрядных, автокорректирующих, свойства, операция
1/--страниц
Пожаловаться на содержимое документа