Ответы к экзамену 2010 (1133259), страница 4
Текст из файла (страница 4)
Пусть подмн-во строк Т - это тест для А. Тогда соответствующее мн-во Т’- покрытие для A(2)Опр. Покрытие матрицы - это подмножество ее строк такое, что в каждомстолбце окажется хотя бы одна единицаЕсли тест тупиковый, то соответствующее покрытие тупиковое.Для построения тупикового (диагностического?) теста:• Матрице A(2) сопоставляем КНФ (i-й скобке соответствует i столбец А, в скобкеиспользуются переменные, соответствующие тем строкам, где в этом столбцеединица)• По КНФ построить сокращенную ДНФ. Каждое слагаемое ДНФ - тупиковыйтест19Оценки длины теста для КС, реализующей счетчикчетности*Что это за КС такая?*Теорема Существует тест Т для Σf , диагностирующий обрыв не более одногоконтакта и такой, что |T | ≤ 5 + dlog2 (n − 2)eД-воТест (Рис.8) будет состоять из двух частей.
Первая состоит из 4х наборов еслиn нечетно и из 5, если четно.γi выбирается так, что в iй строке нечетное кол-во единиц. В М (внутренняячасть таблицы) все столбцы попарно различны.Каждая цепь соответствует некоторому набору.Выберем 4 цепи (Рис.9):В верхней части таблицы будут наборы αf1 , αf2 , αf3 , αf4 и еще одна строка причетных n.Свойства:• z1 , z2 , z3 , z4 охватывает все внутренние контакты ровно 1 раз, т.е. узнаем,произошел ли обрыв контакта19Рис. 8: Тест• любой концевой контакт входит в эти цепи 2 раза, то есть подача на вход первыхчетырех наборов проверяет, произошел ли обрыв концевого или внутреннегоконтакта• все внутренние контакты можно разбить на 4 класса (в какую из цепей онивходят).
Первые 4 набора позволяют определить, в какой из них они входят.Рассмотрим распознавание неисправностей в концевых контактах(Рис.10)При нечетных n все столбцы попарно различны. При четных n не различаютсястолбцы для x1 и xn , поэтому добавляется 5й набор. В качестве 5го набораберется набор, соотв. цепи, проходящей через один из неразличимых контактови не проходящий через другой.• 5 первых наборов тогда диагностируют все неисправности концевых контактов.По реакции на первые 4 набора мы узнаем, в какой цепи находится неисправныйвнутренний контакт.
Осталось определить номер переменной, которой помеченоборванных контакт.В М все столбцы должны быть попарно различными, например, для еепостроения можно воспользоваться наборами, записанными в лексикографическомпорядке. Надо подобрать l строк, чтбы все столбцы были различны (Рис.11)Таблица T позволяет установить, в каком контакте произошел обрыв.20Рис. 9: 4 цепиРис. 10: табличка20Синтез СФЭ из надежных элементов. Оценкавероятности неправильного срабатывания СФЭ.Невозможность построения сколь угодно надежныхсхем. Пример нарастания ненадежностиОпр.Вероятность P (Σ) (фактической) неисправности схемы (элемента) Σ являетсяважнейшей характеристикой надежности схемы.Пусть pi - вероятность выхода из строя (неправильного срабатывания) элемента.Fi ∈ Φ, т.е.
pi = P (Fi ). Пусть ν(i)(i = 1, 2...l) указывает тип элемента с номером iТеоремаP (Σ) ≤ 1 −lY(1 − pν(i) )i=1Распределение вероятностей появления для схемы Σ режимов g1 , ..., gm , гдеng1 = f (x1 , ..., xn ) и 1 ≤ m ≤ 22 определяется указанием вероятностей q (1) , ..., q (m)21Рис. 11: табличкаих появления, для которых Σq (i) = 1. ПоэтомуP (Σ) = 1 − q (1) =Xmq (i) i=2Для элементов Fi распределние вероятностей имеет вид!(r )(1). . . fi ifi(r )(1).
. . pi ipiX (j) mn(1)pi j=1 = 1fi = fi0 (x1 , ..., xn )2 ≤ ri ≤ 22 iЗная распределение для элементов Fi можно построить распределение для схемыΣ, реализующей функцию f (x1 , ..., xn )Для этого для каждого элемента схемы выбираем одну из возможных функцийнеисправности и вычисляем вероятность этой выборки как произведение вероятностейпоявления выбранных неисправностей для отдельных элементов. Затем находимрежим схемы Σ, соответствующий данному выбору. Эту процедуру проделываем длявсевозможных комбинаций выборов.Суммируя все вероятности, соответствующие режиму gi , находим величину(i)q . Закон распределение вероятностей для базисных элементов является полнойхарактеристикой источника HВлияние ошибок на надежность схемыЭффект нарастания ненадежности.Базис состоит из одного ненадежного элемента конъюнктора; источник Н.Конъюнктор реализует f1 = x1 &x2 с вероятностью 1-р и f2 ≡ 0 с вероятностьюp.Рассмотрим схему Рис.12Эта схема должна реализовывать f = x1 &x2 &...&xnP (Σn ) = 1 − (1 − p)n−1 , т.к.
если хоть один из элементов превратится в 0, то навыходе будет 0. При n → ∞P (Σn ) → 1 - нарастание ошибкиТеорема Для того. чтобы в базисе Б с источником Н для любой булевойфункции можно было построить сколь угодно надежную схему, необходимо идостаточно, чтобы можно было построить сколь угодно надежную схему для каждойфункции некоторой полной системы.Д-воНеобходимость очевидна.Достаточность: рассмотрим некоторую полную систему φ1 , ..., φl , все ф-и к-ройдопускают сколь угодно надежную реализацию в базисе B. Пусть f (x1 , ..., xn ) произвольная булева функция и > 0 - произвольное число.22Рис. 12: схемаРассмотрим реализацию f в базисе {Fφ1 , ..., Fφl } = B 0 .
Соответствующая схема. Построим реализацию функцийΣ, L(Σ) - число элементов в ней. Пусть δ = L(Σ)φ1 , ..., φl в базисе В с ненадежностью, не превосходящей δ.Если в схеме Σ заменить эл-ты Fφ1 , ..., Fφl через указанные реализации, тополучим схему Σ и P (Σ ) ≤ L(Σ)L(Σ) = Пусть Hn - неймановский источник, если для каждого Fi ∈ B2 распределениевероятностей имеет вид!n(1)fi (x1 , ..., xni ) . .
. f ( 22 i )i (x1 , ..., xni )n(1)pi...p( 22 i )iгде(1)fi= fi0 (x1 , ..., xni );X2 ni(j) 2j=1pi(j)= 1; pi > 0то есть у ненадежных элементов неймановский источник вызывает всевозможныефункциональные повреждения. Обозначим для Fi ∈ B2 через(i)pmin =(j)min n pi1≤j≤22 iи(i)pmin = min pmini,Fi ,B2Теорема Для неймановского источника Hn и B1 = ∧ P (Σ) ≥ pmin2321Вопрос 20.
Пример изменения выразительнойспособности СФЭ. Критерий возможности скольугодно надежной реализации булевых функцийДля произвольных источников U можно дать следующий критерийТеорема Для того, чтобы в базисе B = B1 ∪ B2 с источником Н для любойбулевой функции можно было построить сколь угодно надежную схему, необходимо идостаточно, чтобы можно было построить сколь угодно надежную схему для каждойфункции некоторой полной системыСм.
пред. вопрос.ПримерПусть B = B2 = {F1 }, где F1 - элемент, реализующий в исправном состояниифункцию f = x1 ⊕ x2 . Пусть H - источник, действующий на F1f1 = x1 ⊕ x2 ; p1 = 1 − p;f2 = x1 ∨ x2 ; p2 = p; 0 < p < 0.5Функции f1 и f2 совпадают на всех наборах, кроме (0, 0)Функции, реализуемые Σn : Рис.13 и их вероятностные параметры: Рис.14Рис. 13: ФункцииРис. 14: Параметры24То есть {Σ2i+1 } реализует штрих Шеффера сколь угодно надежно. Значит, всилу пред. теоремы этот базис позволяет реализовать любую функцию сколь угоднонадежно.Замечания:• Базис В состоит только из ненадежных элементов• Базис В в исправном состоянии не является полным• Наличие источника неисправностей иногда может давать дополнительныевозможности для реализации булевских функций22Повышение надежность с помощью функцииголосования. Однородные деревья. Число внутреннихвершин однородного дерева с q висячими вершинамиФункция голосования: h(x1 , x2 , x3 ) = x1 x2 ∨ x1 x3 ∨ x2 x3Пусть на входе одна и та же величина x с соответствующими вероятностями0 ≤ p1 , p2 , p3 ≤ 1.
Тогда вероятность θ ошибки на выходе этого элемента (впредположении, что его реализация абсолютно надежна) θ = p1 p2 + p1 p3 + p2 p3 −2p1 p2 p3 .θ неубывающая функция. Пусть p = maxp1 , p2 , p3 . Тогда θ ≤ 3p2 − 2p3 = θ1 (p).Значит, при p < 0.5θ(p) < p, то есть элемент голосования позволяет увеличитьнадежность входного сигнала.Рассмотрим схему Рис.15Рис. 15: СхемаЕсли на входы этой схемы передавать независимым образом величину x свероятностью ошибки не большей p то ошибка на выходе θl (p) = θ1 (θ1 (...θ1 (p)...)).| {z }lθl (p) может быть сделана сколь угодно малой при увеличении lЛемма Если вероятность неправильного срабатывания элемента p<0.5, томожно построить схему с вероятностью неисправности θl ≤ O( 212l )Опр.Дерево назовем k-однородным, если это корневое дерево и на каждомуровне i<l степень исхода вверх из каждой вершины k (присутствуют все вершиныяруса) на l-м уровне исходит q ребер, причем из всех (кроме одной возможной)вершины l-го яруса исходит k ребер или ни одного25Лемма Пусть k=3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
