В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2011), страница 7

. , xn ) = x1 ⊕ x2 ⊕ . . . ⊕ xn несуществует КС от n переменных, имеющей полный тест длины меньшей,чем 2n .6.16.∗ Рассматривается построенная по методу каскадов КС Σn , реализующая линейную функцию x1 ⊕ x2 ⊕ · · · ⊕ xn ⊕ 1 при n ≥ 3 (см.рис. 21).1) Докажите эквивалентность единичных замыканий одноименныхконтактов.2) Найдите длину минимального единичного проверяющего тестаа) замыкания,б) размыкания,в) как размыкания, так и замыкания.3) Постройте асимптотически минимальный единичный тест замыкания.4) Постройте единичный тест размыкания, длина которого не превосходита) 2 log2 n + 7,б) 23 log2 n + 10.6.17.∗ Доказать, что любую булеву функцию можно реализовать КС,допускающей единственный полный проверяющий тест, состоящий извсех наборов.6.2.

Тесты для схем из функциональных элементов6.18. 1) Построить минимальный единичный диагностический тестотносительно константных неисправностей на выходах ФЭ схемы нарис. 22 а), б)3 и указать число таких тестов.2) Построить минимальный единичный проверяющий тест относительно константных неисправностей на выходах ФЭ схемы на рис. 23 а).3) Построить минимальный единичный проверяющий тест относительно константных неисправностей на выходах ФЭ схемы на рис. 24 а).4) Построить минимальный проверяющий тест относительно константных неисправностей на выходах тех ФЭ схемы на рис. 25, которыесодержат входы схемы.6.19. 1) Показать, что тест, проверяющий константные неисправности на выходах ФЭ, среди входов которых есть либо входы схемы, либоветвящиеся выходы функциональных элементов, является проверяющимтестом для константных неисправностей на выходах всех ФЭ схемы (приэтом предполагается, что базис не содержит ФЭ, реализующих константы).xqΣ1 :yqAQQ QQAAA&A∨AA@@z1 A− A@@ A&A?z2а)xqΣ0 :q 0qyqΣ11A∨ A?z1Σ1?z22б)При изображении схем из функциональных элементов в настоящем пособии действуют правила:1) общими точками проводников могут являться лишь точки выходов функциональных элементов,2) входы каждого функционального элемента упорядочены слева направо.3xq 1 yq1xq 2 xq n yq2 yqn...Σ0Σn :...Σn−1?.

. . . .z10 z2znв)Рис. 22. Схема сумматора Σn??z0z1xq0Σ̂ :yqqqAQQ QQAA A&A∨AAA&AA AAAAA∨ A 00q?a q bq qxСхема Σ̂n :xq 1 yq1...Σ̂n−1?б)anq bnq xq n−1qyn−1A&A0 ? ?0a...Схема Σ̃n :A∨ Aа)xq 2 xq n yq2 yqnΣ̂0yqA&AA∨ A0z0Рис. 23.а)Σ̃2 :?Σ̃2bxn−2xy qq . . . q 1q . n−2. . y1Σ̃n−1?a1 ?b1б)Рис. 24.2) Показать, что СФЭ на рис. 25 является примером схемы, для которой единичный тест, проверяющий константные неисправности на выходах лишь тех ФЭ, среди входов которых есть входы схемы, не являетсяединичным проверяющим тестом для константных неисправностей навыходах всех ФЭ схемы.6.20.∗ Реализовать линейную функцию x1 ⊕ x2 ⊕ . .

. ⊕ xn СФЭ в стандартном базисе, допускающей единичный тест из четырех наборов, проверяющий константные неисправности на выходах ФЭ схемы.6.21.∗ 1) Доказать, что длина минимального единичного теста, диагностирующего константные неисправности на выходах ФЭ схемы сумматора Σn при n ≥ 3 (рис. 22 в)), равна 5.2) Схема Σ̂n на рис. 23 б) имеет сложность 4n−3 и вычисляет старшийразряд z0 суммы z0 z1 .

. . zn двоичных чисел x1 . . . xn и y1 . . . yn (схемаΣ̂1 представляет собой конъюнктор). Доказать, что длина минимальногоединичного теста, проверяющего константные неисправности на выходахФЭ схемы Σ̂n , равна 2n.3) Построить единичный тест, проверяюxq 1 xq 2 xq 3 xq 4щий константные неисправности на выхоA−A−A−A−AX AP AXAдах ФЭ схемы Σ̃n на рис. 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 .