В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики, страница 7
Описание файла
PDF-файл из архива "В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов, А.А. Сапоженко, С.Н. Селезнева - Задачи по курсу Основы кибернетики", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 7 страницы из PDF
24 б), имеющийXX SPPXXXSS S PP длину не более 4.A∨ A∨ A∨ AAA∗6.22. Показать существование такогоA−A−A−базиса из ФЭ, в котором для любой булеAAASSвой функции n переменных существует схе SS∨∨∨AAAA∨ ма, допускающая единичный проверяющийAAAAконстантные неисправности на выходах ФЭA−A−A−A−AAAHAтест длины, не превосходящей n + 1. HH CHC6.23.∗ Доказать, что длина полного проA∨ A∨ AAверяющего теста для входов n-входовой схеSS A∨ мы не превосходит 2n.
Показать неулучшаA?zемость предыдущей оценки для некоторойРис. 25.функции.6.24.∗ Показать, что, начиная с некоторого n, любая булева функция n переменных обладает схемой, допускающей нетривиальный единичный тест, диагностирующий константныенеисправности на выходах ФЭ.6.25. Покажите, что минимальный проверяющий единичные константные неисправности на выходах ФЭ тест для произвольного дешифратора (для произвольного универсального многополюсника) состоит извсех наборов.§ 7. Оценка надежности схем.
Самокорректирующиеся схемы.Для определения уровня надежности схемы часто применяется вероятностный подход (см., например, [6, 12]). Пусть M = (Σ, И) — ненадежная схема Σ от переменных x1 , . . . , xn , переходящая под действиемисточника неисправностей И в состояния Σ = Σ(1) , Σ(2) , . . . , Σ(t) , в которых реализуются функции F = F (1) , F (2) , . . .
, F (t) соответственно, определенные на множестве наборов N = {β1 , . . . , βp }. Пусть далее вероят(i)ность того, что схема Σ находитсяPt в состоянии Σ ,известна и равна πi ,где i = 1, . . . , t, 0 ≤ πi ≤ 1 и i=1 πi = 1. Введем следующие величины,характеризующие ненадежность схемы Σ в модели M:Xξ(M) =πj ,(6.1)F (j) 6= F2≤j≤tXξ(M, β) =Fπj ,(6.2)(j)(β) 6= F (β)2≤j≤tгде β ∈ N , а затем положимη(M) = max ξ(M, β),(6.3)qM (x1 , . . . , xn ) = ξ(M, (x1 , .
. . , xn )).(6.4)β∈NЗаметим, что величина ξ(M) (ξ(M, β)) задает вероятность того, чтосхема Σ реализует функцию, не равную F (соответственно не равную Fна наборе β), и поэтомуη(M) ≤ ξ(M) ≤ pη(M),(6.5)откуда следует, в частности, что η(M) = 0 тогда и только тогда, когда ξ(M) = 0. Схема Σ считается абсолютно надежной в модели M,если η(M) = 0 (или ξ(M) = 0). Это означает, что все состояния схемы Σ, имеющие положительную вероятность, эквивалентны Σ. ФункцияqM (x1 , . . .
, xn ) называется функцией вероятности неправильного срабатывания схемы Σ. В дальнейшем, при записи введенных величин вместопары M = (Σ, И) будем писать просто Σ, если из контекста ясно, какойисточник неисправностей имеется в виду.Рассмотрим вероятностный подход на примере ненадежных СФЭ надбазисом Б = {Ei }bi=1 , где ФЭ Ei реализует булеву функцию ϕi (u1 , . . . , uki ).Пусть для каждого i, i = 1, .
. . , b, известно распределение режимов раkботы ФЭ Ei , то есть для каждого j, j = 1, . . . , 22 i , известна и равна πi,jвероятность того, что ФЭ Ei реализует j-ю булеву функцию от булевыхпеременных u1 , . . . , uki (если считать, что все булевы функции от переменных u1 , . . . , uki упорядочены в соответствии с номерами их столбцовзначений). При нахождении ненадежности схемы Σ над базисом Б будемсчитать, что все ее ФЭ переходят в свои состояния независимо друг отдруга и что любое состояние СФЭ Σ определяется состояниями ФЭ Σ(см. § 5). В соответствии с этим на основе введенных выше соотношений(6.1)-(6.4) можно найти значения ненадежности ξ(Σ) и η(Σ) для СФЭΣ, а также распределение режимов ее работы и функцию qΣ (x1 , .
. . , xn ).Считается, что функция f (x1 , . . . , xn ) допускает сколь угодно надежную реализацию в базисе Б, если для любого ε, ε > 0, существует СФЭΣ над Б, которая реализует f и для которой ξ(Σ) < ε. Повышение надежности при реализации ФАЛ f (x1 , . . . , xn ) возможно, если в базисе Бимеется абсолютно надежный ФЭ Ei , реализующий функцию голосования m(x1 , x2 , x3 ) = x1 x2 ∨x1 x3 ∨x2 x3 (см. [12]). Действительно, если СФЭΣ реализует f и η(Σ) = ε, то для ненадежности СФЭ Σ(1) , показаннойна рис. 26 а), которая тоже реализует f , имеет место равенствоη(Σ(1) ) = H(ε) = 3ε2 − 2ε3(график функции τ = H(ε) показан на рис. 26 б)).xXq 1qXq q xq nXXXXXXXXX XXX XXΣΣτ1ΣQQ12QQQQ@ E@ i@0?а)12ε1б)Рис. 26.1Заметим, что H(0) = 0, H 2 = 12 , что первые две производныефункции H(ε) на отрезке 0; 21 неотрицательны, причем H 0 (0) = H 00 21 = 0 иH 0 12 > 0, H 00 (0) > 0, и что η(Σ(1) ) < ε, если ε < 21 .
Поэтому, рекурсивно применяя указанную процедуру повышения надежности к СФЭ Σ(k) ,результатом которой является СФЭ Σ(k+1) , k = 1, 2, ..., построим последовательность СФЭ Σ(1) , Σ(2) , ..., Σ(k) , ..., реализующих f , для которойη(Σ(k) ) = H(η(Σ(k−1) )) → 0.k→∞kЗаметим также, что СФЭ Σ(k) содержит 3 подсхем вида Σ и 1 + 3 +k· · · + 3k−1 = 3 2−1 ФЭ Ei .Аналогичные построения и оценки применимы и для повышения ξненадежности СФЭ.7.1. 1) Доказать, что ξ(M) = η(M) тогда и только тогда, когда дляM существует проверяющий тест длины 1.2) Доказать, что функция f допускает сколь угодно надежную реализацию в базисе Б тогда и только тогда, когда для любого ε, ε > 0,существует СФЭ Σ над Б, которая реализует f и для которой η(Σ) < ε.3) Доказать, что для вычисления ненадежности η(Σ) в соответствиис (6.3) для СФЭ Σ над базисом Б достаточно знать ненадежности видаξ(Ei , β) для всех ФЭ Ei базиса Б и всех наборов β из B ki , i = 1, .
. . , b.7.2. Ниже указана СФЭ Σ и распределения режимов работы ее ненадежных ФЭ. Найти распределение режимов работы СФЭ Σ, а затем вычислить ξ(Σ), η(Σ) и функцию qΣ .1) Σ — СФЭ на рис. 22 а), где конъюнктор работает абсолютно надежно, а распределения режимов работыдизъюнктора u1∨ u2 и инвертораu1 ∨ u2 u1 ⊕ u2ū1 u1ū1 имеют, соответственно, види.321133442) Σ — СФЭ на рис.
23 а), где дизъюнктор работает абсолютно надежно,а распределениережимов работы конъюнктора u1 &u2 имеет видu1 &u2 ū1.31443) Σ — СФЭ на рис. 24 а), где конъюнктор работает абсолютно надежно,а распределениережимов работы дизъюнктора u1 ∨ u2 имеет видu1 ∨ u2 u1 &u2.21337.3. 1) Пусть в СФЭ Σ на рис. 22 а) дизъюнктор работает абсолютнонадежно, а распределения режимовработы конъюнктораu1 &u 2 и инверu1 &u2 0ū1 0тора ū1 имеют, соответственно, види. Известно,311−p p44что вероятность такого функционирования схемы, при котором на обоихвыходах схемы реализуются тождественные нули, равна 16 . Найти p.2) Пусть распределения режимов работы конъюнктора u1 &u2 и дизъu1 &u2 1юнктора u1 ∨ u2 в СФЭ Σ на рис.
23 а) имеют види1−p pu1 ∨ u2 x, соответственно. Известно, что вероятность такого функ1233ционирования схемы, при котором на выходе Σ реализуется тождественная единица, равна 83 . Найти p.7.4. Пусть базис Б состоит из ФЭ, реализующего функцию голосования, который работает абсолютно надежно, и конъюнктораu1 &u2 , расu1 &u2 1.пределение режимов работы которого имеет вид12331) Достаточно ли 40 функциональных элементов, чтобы реализоватьфункцию u1 &u2 c ненадежностью не более 0.1?2) Достаточно ли 400 функциональных элементов, чтобы реализоватьфункцию u1 &u2 c ненадежностью не более 0.002?7.5.∗ Ниже приведены распределения режимов работы ФЭ Ei , i =1, ..., b, ненадежного базиса Б.
Покажите, что в данном базисе возможнасколь угодно надежнаяреализация произвольной функции.u1 ⊕ u2 u1 ∨ u21) b = 1, E1 :;1−ppu1 ∨ u2 1u1 ⊕ u2 1u1 &u22) b = 3, E1 :, E2 :, E3 :.1−p p1−p p1Другой (так называемый логико-комбинаторный [12]) подход к определению уровня надежности схемы связан с понятием самокорректируемости. Схема Σ называется самокорректирующейся относительноисточника неисправностей И, если в модели (Σ, И) все состояния эквивалентны. Естественно считать, что чем больше неисправностей корректирует схема Σ, тем выше уровень ее надежности.
Задача синтезасамокорректирующихся схем является важным частным случаем общейзадачи синтеза.Рассмотрим задачу синтеза контактных схем, которые являются самокорректирующимися относительно источника неисправностей Иr,s (см. §5). Простейший способ решения этой задачи связан с последовательными (или) параллельным дублированием двухполюсной КС.
Легко видеть,что если при этом взять l экземпляров самокорректирующейся относительно Иr,s КС Σ и соединить их последовательно (параллельно), то получим эквивалентную Σ КС Σ0 , которая является самокорректирующейся относительно ИR,S , где R = r, S = (s + 1) · l − 1 (соответственноR = (r + 1) · l − 1, S = s). Аналогичный результат дает указанное выше дублирование, если его применять к каждому контакту схемы (этотспособом можно строить многополюсные самокорректирующиеся КС).Другой способ перехода от (многополюсной) КС Σ к эквивалентной ейКС Σ0 , которая является самокорректирующейся относительно Иσ,1−σ ,где σ ∈ {0, 1}, заключается в следующем.
Разобьем КС Σ на непересекающиеся связные (многополюсные) подсхемы Σ1 , . . . , Σl , каждая изкоторых состоит из контактов одного типа, а затем заменим КС Σi ,i = 1, . . . , l, на КС Σ0i , состоящую из контактов того же типа, которая(i)(i)представляет собой цикл, проходящий через все вершины v1 , . . . , vai КСΣi , если σ = 1 (см. рис. 27 а)) и звезду с центром в новой вершине, соеди(i)(i)ненной со всеми вершинами v1 , . . . , vai КС Σi , если σ = 0 (см. рис. 27 б)).(i)xδv2(i)v2xδ(i)v1(i)v3xδ(i)v1xδ•xδ ....(i)xδxδ..(i)v3(i)vaivaiа)б)Рис.
277.6. 1) Доказать, что если функция xσi , где 1 ≤ i ≤ n и σ ∈ {0, 1}может быть получена из функции f (x1 , ..., xn ) в результате некоторойподстановки констант вместо БП x1 , ..., xi−1 , xi+1 , ..., xn , то в любой КС,реализующий f и корректирующей r обрывов (r замыканий), содержитсяне менее (r + 1) контактов xσi .2) Построить для функции x1 ⊕x2 минимальную КС, корректирующуюа) одно размыкание,б) одно замыкание.7.7.
По контактной схеме Σ построить эквивалентную схему, корректирующую замыкание m контактов и содержащую не более l контактов.1) m = 1, l = 6Σ:2) m = 1, l = 7Σ:3) m = 1, l = 10Σ:4) m = 1, l = 4Σ:5) m = 1, l = 10Σ:6) m = 1, l = 6Σ:7) m = 1, l = 9Σ:8) m = 1, l = 4Σ:7.8. По контактной схеме Σ построить эквивалентную схему, корректирующую размыкание (обрыв) m контактов и содержащую не более lконтактов.1) m = 1, l = 10Σ:2) m = 1, l = 4Σ:3) m = 1, l = 9Σ:4) m = 1, l = 8Σ:5) m = 1, l = 4Σ:6) m = 1, l = 9Σ:7) m = 1, l = 10Σ:8) m = 1, l = 4Σ:7.9.