OK_metodichka_part_4 (1132799), страница 2
Текст из файла (страница 2)
Сопоставим i-й строке, i ∈ [1, p], матрицыM БП yi , а каждому набору β, β ∈ B p , значений этих переменных y = (y1 , . . . , yp ) — множество строк матрицы M сномерами из множества I = I (β) ⊆ [1, p], где i ∈ I (β) тогда и только тогда, когда β hii = 1. Рассмотрим ФАЛ F (y),§1. Задача контроля схем и тесты для таблиц9для которой F (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует тест для(M, N), и будем называть эту ФАЛ функцией теста для(M, N).
Сопоставим паре (M, N) матрицу M из множестваB p,S , S = |N|, столбцы которой пронумерованы парами изN, а ее столбец с номером (i, j) ∈ N получается в результатепоразрядного сложения по модулю 2 столбцов с номерами i иj матрицы M . Заметим, что строки матрицы M с номерамииз множества T, T ⊆ [1, p], образуют тест (тупиковый тест,минимальный тест) для пары (M, N) тогда и только тогда,когда строки матрицы M с номерами из T образуют покрытие (тупиковое покрытие, покрытие минимальной длины)матрицы M. Отсюда вытекает, в частности, что ФАЛ тестаF для пары (M, N) является одновременно ФАЛ покрытиядля матрицы M и обратно, а значит для нее, в силу леммы6.1 главы 1, справедливо следующее утверждение.Лемма 1.1.
Функция теста f (y1 , . . . , yp ) для отделимойпо столбцам матрицы M, M ∈ B p,s , и цели контроля Nможет быть задана с помощью КНФ^ _f (y1 , . . . , yp ) =yt ,(1.1)(i,j)∈N16t6pM ht,ii6=M ht,jiСледствие. Каждая элементарная конъюнкция вида yt1 · · · ytrсокращенной ДНФ функции f (y1 , . . . , yp ), получающаяся изКНФ (1.1) в результате раскрытия скобок и приведенияподобных, соответствует тупиковому тесту, связанномус множеством T = {t1 , .
. . , tr } и обратно.На данной лемме основан следующий алгоритм построения всех тупиковых тестов для матрицы M относительноцели контроля N:1. выписываем для функции теста КНФ вида (1.1);10 Глава 4. Надежность и контроль управляющих систем2. раскрывая в ней скобки и приводя подобные, получаемсокращенную ДНФ функции теста;3.
сопоставляем каждой элементарной конъюнкции этойсокращенной ДНФ тупиковый тест.Так, например, для построения всех тупиковых диагностических тестов матрицы M вида0 1 00 1 1M =1 0 11 1 0выпишем соответствующую ей КНФ (1.1):F (y1 , y2 , y3 , y4 ) = (y1 ∨ y2 ∨ y3 ) · (y2 ∨ y4 ) · (y1 ∨ y3 ∨ y4 ) .Раскрывая в этой КНФ скобки и приводя подобные, получим сокращенную ДНФ для функции теста:F (y1 , y2 , y3 , y4 ) = y1 y2 ∨ y1 y4 ∨ y2 y3 ∨ y2 y4 ∨ y3 y4 .Следовательно, тупиковыми диагностическими тестами матрицы M являются множества ее строк с номерами{1, 2} , {1, 4} , {2, 3} , {2, 4} , {3, 4} .Для упрощения преобразований, связанных с применением описанного алгоритма, вместо исходной матрицы Mможно рассматривать отделимую по строкам матрицу M̌ ,получающуюся из M удалением повторных вхождений одинаковых строк.
При этом, очевидно, любой тупиковый тестматрицы M получается из тупикового теста той же длиныматрицы M̌ в результате замены каждой его строки равнойей строкой матрицы M и обратно.Рассмотрим, далее, некоторые оценки длины диагностических тестов для матриц с заданным числом столбцов.§1. Задача контроля схем и тесты для таблиц11Лемма 1.2. Длина любого тупикового диагностическоготеста для отделимой по столбцам матрицы из множества B p,s заключена в пределах от dlog se до (s − 1).Доказательство. Пусть M ∈ B p,s и пусть, для определенности, первые t строк матрицы M образуют ее тупиковыйдиагностический тест.
Очевидно, что в этом случае всеc, состоящей из первых t строк матрицыстолбцы матрицы MM , различны и, следовательно, s 6 2t , то есть t > dlog se,поскольку число различных булевых столбцов высоты t равно 2t . Требуемая нижняя оценка длины диагностическоготеста установлена.Докажем теперь, что t 6 (s − 1). Для этого на множеc при любом q, q ∈ [1, t], опредестве столбцов матрицы Mлим отношение эквивалентности ∼ так, что m0 ∼ m00 тогдаq0m иqm00c совпаи только тогда, когда столбцыматрицы Mдают в строках с номерами из отрезка [1, q]. Будем считать,по определению, что ∼ — тривиальное отношение с одним0классом эквивалентности, а число классов эквивалентностипо отношению ∼, где q ∈ [1, t], будем обозначать через θ (q).qИз общих свойств отношений эквивалентности (см.
??)вытекает, что при любом q, q ∈ [1, t), каждый класс эквивалентности по отношению ∼ либо является классом эквиваqлентности по отношению ∼ , либо представляет собой объq+1единение двух таких классов и, следовательно, θ (q) 6 θ (q + 1).В силу тупиковости теста полученное неравенство являетсястрогим, так как равенство θ (q) = θ (q + 1) возможно тогдаи только тогда, когда каждый класс эквивалентности отношения ∼ является классом эквивалентности отношения ∼qq+1и обратно, то есть строка с номером (q + 1) является «лишней» в рассматриваемом тесте.Из диагностичности теста вытекает, что θ (t) = s, и, та-12 Глава 4.
Надежность и контроль управляющих системким образом, выполняются соотношения1 = θ (0) < θ (1) < · · · < θ (t) = s,из которых следует, что t 6 (s − 1).Лемма доказана.Замечание. Указанные в лемме границы достигаются: нижняя — на любой отделимой по столбцам матрице из B p,s , гдеp = dlog se, а верхняя — на матрице из B s−1,s , все столбцыкоторой различны и содержат не более одной единицы (обематрицы имеют единственный диагностический тест, состоящий из всех строк).Следующее утверждение характеризует «типичное» значение длины диагностического теста, то есть длину минимального диагностического теста у «почти всех» таблиц контроля.Лемма 1.3. Пусть ϕ (s) , t (s) и p (s) — целочисленныенеотрицательные функции натурального аргумента s, длякоторыхt (s) = d2 log se + ϕ (s) ,p (s) > t (s) ,ϕ (s) −−−→ ∞.s→∞Тогда у почти всех отделимых по столбцам матриц изB p(s),s первые t (s) строк образуют диагностический тест.Доказательство.
Заметим, что все матрицы из B p,s , гдеp = p (s), у которых первые t = t (s) строк образуют диагностический тест, отделимы по столбцам. Легко видеть также,что число таких матриц равно2t 2t − 1 · · · 2t − s + 1 · 2(p−t)s =(s − 1)1ps,=21 − t ··· 1 −22t§2. Самокорректирующиеся КС13а их доля среди всех отделимых по столбцам матриц из B p,sне меньше, чем(s − 1)s21>1−> 1 − 2−2ϕ(s) ,1 − t ··· 1 −22t2tи, следовательно, стремится к 1 при s стремящемся к бесконечности.Лемма доказана.Следствие. Для любой неотрицательной и неограниченновозрастающей функции ϕ (s) у почти всех отделимых постолбцам матриц из B p,s длина минимального диагностического теста не больше, чем 2 log s + ϕ (s).§2Самокорректирующиеся контактные схемыи методы их постороения.
Асимптотическинаилучший метод синтеза контактных схем,корректирующих один обрыв (одно замыкание)Рассмотрим вопрос повышения надежности схем на примерет. н. самокорректирующихся КС. Будем считать, что контакты рассматриваемых КС могут выходить из строя, переходя в одно из двух возможных неисправных состояний:состояние обрыва, когда контакт не проводит, и состояниезамыкания, когда контакт проводит при любых значенияхуправляющей им БП.Будем говорить, что КС Σ является (p, q) - самокорректирующейся КС или, иначе, корректирует p обрывов и qзамыканий, где p > 0 и q > 0, если любая КС Σ0 , котораяможет быть получена из КС Σ в результате обрыва не болеечем p, и замыкания не более, чем q, контактов, эквивалентнаΣ. Обозначим через UK(p,q) множество всех (p, q) - самокорKректирующхся КС и заметим, что UK(0,0) = U .
Заметим,14 Глава 4. Надежность и контроль управляющих системтакже, что для любой КС Σ КС Σ(p,q) , получающаяся из Σв результате замены любого ее контакта вида xσi π-схемой,состоящей из (q + 1) последовательно соединенного пучка,каждый из которых, включает в себя (p + 1) параллельносоединенный контакт вида xσi , принадлежит UK(p,q) .Построение КС Σ(p,q) , основанное на последовательном и(или) параллельном дублировании контактов КС Σ, является простейшим способом получения самокорректирующихся КС, эквивалентных заданной КС. Он дает следующуютривиальную верхную оценку сложности самокорректирующихся КС, эквивалентных данной.Лемма 2.1.
Для любых p > 0, q > 0 и любой КС Σ существует эквивалентная ей КС Σ0 , Σ0 ∈ UK(p,q) , для которойL(Σ0 ) 6 (p + 1)(q + 1)L(Σ).Рассмотрим, далее, нетривильный способ построения (1, 0)или (0, 1)-самокорректирующихся КС, связанный с коррекцией одного обрыва или одного замыкания в т.
н. однородных подсхемах. Будем называть однородной любую связнуюКС с неразделенными полюсами, состоящую из контактоводного и того же типа. Заметим, что в любой такой КС, состоящей из контактов вида xσi , ФАЛ проводимости междулюбыми двумя полюсами равна xσi . Отсюда следует, в частности, что любые две однородные КС, состоящие из контактов одного типа и имеющие один и тот же набор полюсов,эквивалентны.Обозначим через Cm (xσi ) (Zm (xσi )) m-полюсную однородную КС, которая состоит из m контактов вида xσi и представляет собой цикл, проходящий через все полюса (соответсвенно звезду из контактов, соединяющих ее центр с поσKлюсами). Очевидно, что Cm (xσi ) ∈ UK(1,0) и Zm (xi ) ∈ U(0,1) .Представление КС Σ в виде объединения ее однородныхподсхем без общих контактов будем называть однородным§2. Самокорректирующиеся КС15разбиением КС Σ, а минимальное число подсхем в такихразбиениях будем обозначать через ζ(Σ).
Если Σ1 , ..Σζ - однородное разбиение КС Σ, а эквивалентная ей КС Σ0 (КСΣ00 ) получается из КС Σ в результате замены каждой подсхемы Σi эквивалентной ей КС Σ0i вида Cm (соответственно00KКС Σ00i вида Zm ), то Σ0 ∈ UK(1,0) (соответственно Σ ∈ U(0,1) ).Заметим, что при этомL(Σ0i ) 6 L(Σi ) + 1, L(Σ00i ) 6 L(Σi ) + 1и, следовательно,L(Σ0 ) 6 L(Σ) + ζ, L(Σ00 ) 6 L(Σ) + ζУказанный нетривиальный способ построения (0, 1)- или(1, 0)-самокорректирующихся КС, эквивалентных заданной,дает следующую оценку их сложности.Лемма 2.2. Для любой КС Σ существуют эквивалентныеей (1, 0)- и (0, 1)-самокорректирующиеся КС Σ0 и Σ00 соответственно такие, чтоL(Σ0 ) 6 L(Σ) + ζ(Σ), L(Σ00 ) 6 L(Σ) + ζ(Σ).(2.1)Этот способ позволяет установить асимптотику функцииKШеннона для сложности КС из UK(0,1) и U(1,0) .Для ФАЛ f и p > 0, q > 0 определим ее (p, q)-самокорректирующуюся контактную сложность LK(p,q) (f ) как миниKмальную сложность КС Σ, Σ ∈ U(p,q) , реализующей f , азатем введем соответствующую функцию ШеннонаKLK(p,q) (n) = max L(p,q) (f ).f ∈P2 (n)Очевидно, чтоKKLK (f ) 6 LK(p,q) (f ) L (n) 6 L(p,q) (n)Kтак как UK(p,q) ∈ U .(2.2)16 Глава 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
