4 (1132840), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

, yp ) — множество строк матрицы M сномерами из множества I = I (β) ⊆ [1, p], где i ∈ I (β) тогда и только тогда, когда β hii = 1. Рассмотрим ФАЛ F (y),Введение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может быть задана с помощью КНФ_^ yt ,(1.1)f (y1 , . . . , yp ) =(i,j)∈N16t6pM ht,ii6=M ht,jiСледствие. Каждая элементарная конъюнкция вида yt1 · · · ytrсокращенной ДНФ функции f (y1 , . . . , yp ), получающаяся изКНФ (1.1) в результате раскрытия скобок и приведенияподобных, соответствует тупиковому тесту, связанномус множеством T = {t1 , .

. . , tr } и обратно.На данной лемме основан следующий алгоритм построения всех тупиковых тестов для матрицы M относительноцели контроля N:1. выписываем для функции теста КНФ вида (1.1);10Введение2. раскрывая в ней скобки и приводя подобные, получаемсокращенную ДНФ функции теста;3. сопоставляем каждой элементарной конъюнкции этойсокращенной ДНФ тупиковый тест.Так, например, для построения всех тупиковых диагностических тестов матрицы M вида0 1 00 1 1M =1 0 11 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 и обратно.Рассмотрим, далее, некоторые оценки длины диагностических тестов для матриц с заданным числом столбцов.Введение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Из общих свойств отношений эквивалентности (см. Гл. 1, §1)вытекает, что при любом q, q ∈ [1, t), каждый класс эквивалентности по отношению ∼ либо является классом эквиваqлентности по отношению ∼ , либо представляет собой объq+1единение двух таких классов и, следовательно, θ (q) 6 θ (q + 1).В силу тупиковости теста полученное неравенство являетсястрогим, так как равенство θ (q) = θ (q + 1) возможно тогдаи только тогда, когда каждый класс эквивалентности отношения ∼ является классом эквивалентности отношения ∼qq+1и обратно, то есть строка с номером (q + 1) является «лишней» в рассматриваемом тесте.Из диагностичности теста вытекает, что θ (t) = s, и, та-12Введениеким образом, выполняются соотношения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 =1(s − 1)ps=21 − t ··· 1 −,22tВведение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Введениетакже, что для любой КС Σ КС Σ(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 и представляет собой цикл, проходящий через все полюса (соот-Введение15ветсвенно звезду из контактов, соединяющих ее центр с поσKлюсами). Очевидно, что Cm (xσi ) ∈ UK(1,0) и Zm (xi ) ∈ U(0,1) .Представление КС Σ в виде объединения ее однородныхподсхем без общих контактов будем называть однороднымразбиением КС Σ, а минимальное число подсхем в такихразбиениях будем обозначать через ζ(Σ).

Характеристики

Список файлов лекций