close

Вход

Забыли?

вход по аккаунту

?

О тестах относительно локальных линейных слипаний переменных в булевых функциях.

код для вставкиСкачать
О тестах относительно локальных линейных слипаний переменных в булевых функциях
153
УДК 519.718
О ТЕСТАХ ОТНОСИТЕЛЬНО ЛОКАЛЬНЫХ ЛИНЕЙНЫХ СЛИПАНИЙ
ПЕРЕМЕННЫХ В БУЛЕВЫХ ФУНКЦИЯХ
2012 г.
Е.В. Морозов, Д.С. Романов
Московский госуниверситет им. М.В. Ломоносова
morozov-msu@yandex.ru, romanov@cs.msu.ru
Поступила в редакцию 10.09.2012
Доказываются нетривиальные оценки функций Шеннона длины проверяющего теста (на уровне
порядка роста) и длины диагностического теста (на уровне асимптотики при соблюдении ряда условий) относительно локальных k-кратных линейных слипаний переменных в булевых функциях.
Ключевые слова: булева функция, слипание переменных, проверяющий тест, диагностический
тест, функция Шеннона длины теста.
Вводные определения
Пусть n, k, t – натуральные числа (2 ≤ k ≤ n,
n
22 ), f ( x n) – булева функция, формаль-
2 t
но зависящая от переменных
k
x1 … xn , и
k
) { i ( y ) i 1 … t} – система попарно неравных булевых функций k переменных
y1, y2, …, yn.
Обозначим
через
n
( x ) систему функций, в которую
nkt f
t (y
входят всевозможные функции
n
f ( x1 … x j
j i (x )
i (x j
… xj
k 1)
…
i (x j
… xj
2
1
k 1)
как максимум по всем булевым функциям
f ( x n) длины минимального теста требуемого
типа для булевой функции f. Кроме того, введем
(n) длины проверяюфункцию Шеннона Ldetect
k
щего теста относительно локальных k-кратных
-слипаний переменных как максимум по всем
существенно зависящим от всех своих переменных булевым функциям f ( x n) длины минимального теста данного типа для булевой функции f. В случае, когда
есть система
k
lin
lin
k 1 ( y ) всемозможных попарно нерав-
, xj
k
… xn ),
k раз
где 1 j n k 1 , i {1, …, t}.
Множество T наборов значений переменных
x1 … xn называется проверяющим (диагностическим) тестом относительно локальных
k-кратных
-слипаний переменных булевой
n
функции f ( x ) тогда и только тогда, когда любая не равная f ( x n) функция из
отличается
от f на множестве T (соответственно, тогда и
только тогда, когда любые две не равные друг
другу функции из
{ f ( x n)} различаются на
множестве T).
Длину теста T (число наборов в нем) будем
обозначать через l(T) или |T |. Традиционным
( n) и
образом введем функции Шеннона Ldetect
k
Ldiagn
( n) длины проверяющего и диагностичеk
ского (соответственно) тестов относительно
локальных k-кратных -слипаний переменных
ных линейных функций k переменных (при
t 2k 1 ), будем говорить о локальных k-кратных линейных слипаниях переменных функции f.
Все не введенные в данной статье определения
можно найти в книге [1].
В настоящей работе приводятся оценки для
введенных функций Шеннона относительно
локальных k-кратных линейных слипаний переменных булевой функции.
Ранее рядом авторов изучались некоторые
близкие к рассматриваемым в данной работе
тесты относительно источников неисправностей, воздействующих на переменные булевых
функций (так называемые тесты для входов
схем). Следует отметить [2], а также цикл работ
В.Н. Носкова [3–6] (о тестах относительно константных неисправностей на входах схем и относительно произвольных неисправностей ограниченной кратности на входах схем), статью
Н.Н. Нурмеева [7], препринт Г.Р. Погосяна [8]
(о тестах относительно константных и инверсных неисправностей на входах схем и относительно дизъюнктивных слипаний входов схем).
154
Е.В. Морозов, Д.С. Романов
В настоящей статье изучаются тесты, близкие к
исследуемым в статьях [9, 10].
Таблицу с 2k строками и t столбцами, состоящую из столбцов значений всех функций из
Φ, обозначим через M(Φ), а поэлементное отрицание этой таблицы через M (Φ ) . Под под% %
Bkα,β
,j ,
кубом
где α% = (α1 ,…, α j −1 ) , а β% = (βj+k, …,
βn), будем понимать грань Γγ, где γ =
% 2,…, 2,β% ) (двойки стоят на местах пере= (α,
менных x j ,…, x j + k −1 и обозначают произвольность значений этих переменных), то есть множество всех наборов из B n , начинающихся с α%
и заканчивающихся β% .
Зафиксируем число j (1 ≤ j ≤ n − k + 1 ). Рассмотрим таблицу неисправностей, построенную
для произвольной булевой функции f ( x% n) на
всех (следующих в лексикографическом поряд% %
% j −1 , 2% k , β% n − j − k +1) .
ке) наборах подкуба Bkα,β
, j = (α
Вектор значений функции f ′( x% n) на подкубе
%
%
ния переменных x j ,…, x j + k −1 относительно выбранной системы функций. Если
n − j − k +1
n − j − k +1
f (α% j −1, 0% k , β%
) = 0 , f (α% j −1, 1% k , β%
) = 1,
то фрагмент таблицы неисправностей, связанный с проверкой переменной xj, на подкубе
%
%
Bkα,β
, j имеет вид M(Φ). Если же
n − j − k +1
f (α% j −1, 0% k , β%
) = 1,
n − j − k +1
f (α% j −1, 1% k , β%
) = 0,
то фрагмент таблицы неисправностей, связанный с проверкой переменной xj на подкубе
%
%
Bkα,β
, j , имеет вид M (Φ ) . В последних двух слу-
чаях для проверки функций неисправностей
ψ j ,1 ,…,ψ k +1 ( x% n) достаточно взять некоторые
j ,2
%
%
k + 1 наборов куба Bkα,β
, j и еще один некоторый
набор. Для проверки функций неисправности
g k ( x1 ,..., xk ) , g k ( x1 ,..., xk ) ⊕ 1 достаточно взять
%
%
один произвольный набор куба Bkα,β
, j и еще один
некоторый набор.
Дадим несколько новых определений, свя%
%
%
α,β
Bkα,β
, j обозначим через f ′[ Bk , j ] . Заметим, что
%
занных с классификацией векторов f [ Bkα,β
,j ]=
n − j − k +1
n − j − k +1
) = f (α% j −1, 1% k , β%
)=σ ,
если f (α% j −1, 0% k , β%
= (ξ1 ,...,ξ2k ) . Вектор называется константным,
%
%
то для любой функции ψ j ,i вектор ψ j ,i [ Bkα,β
,j ]
k
равен (σ% 2 ) = (σ,…,σ) . При этом, если сущестчто
вует
такой
булев
набор
δ% k ,
n − j − k +1
f (α% j −1, δ% k , β%
) ≠ σ , то этот набор проверяет
функции
ψ
( x% n) . В этом случае тройку наборов
j , 2k +1
(α% j −1, 0% k , β%
неисправностей
ψ j ,1 ( x% n),…,
все
n − j − k +1
),
(α% j −1, δ% k , β%
(α% j −1, 1% k , β%
n − j − k +1
),
n − j − k +1
),
такую, что
f (α%
n − j − k +1
n − j − k +1
, 0% k , β%
) = f (α% j −1, 1% k , β%
)≠
,
j −1 % k % n − j − k +1
≠ f (α% , δ , β
)
j −1
назовем замечательной тройкой для переменной x j булевой функции f, а набор (α% j −1 , δ% k ,
n − j − k +1
) – особым набором для переменной xj
β%
булевой функции f.
Через g k ( x1 ,..., xk ) обозначим функцию x1 ⊕
⊕ x2 ⊕ … ⊕xk .
Под проверкой переменной xj относительно
системы Φ будем понимать процесс построения
множества наборов, обнаруживающих всевозможные линейные локальные k-кратные слипа-
если все его компоненты равны. Если первая
компонента вектора не равна последней, то вектор будем называть вектором
F-типа, а иначе – вектором C-типа. Вектор называется замечательным, если он порождает замечательную тройку по xj. Если в векторе найдутся две
неравные компоненты, модуль разности номеров которых есть 2k −1 , то соответствующие
этой паре компонент входные наборы для f назовем перспективной парой. Если вектор F-типа
порождает перспективную пару, то такой вектор будем называть перспективным. Все другие
векторы F-типа назовем бесперспективными.
%
%
α% ′′,β
и соответствующие
Два подкуба Bkα%,′,β
j и Bk , j
%
%
α% ′′,β
им векторы f [ Bkα%,′,β
j ] и f [ Bk , j ] назовем сосед-
% ′′ отличаются только
ними, если наборы α% ′ и α
последней компонентой.
О проверяющих тестах
Исследуем поведение функции Шеннона
длины проверяющего теста относительно локальных k-кратных линейных слипаний переменных.
Теорема 1. Ldetectlin (n) ≤ ⎡ n−k +1 ⎤ ⋅ 4k + 2k .
k ,Φ
⎢ k ⎥
Доказательство. Пусть f (xn) – произвольная
О тестах относительно локальных линейных слипаний переменных в булевых функциях
булева функция. Организуем процесс построения проверяющего теста для f (xn) следующим
образом. Будем последовательно строить множества наборов, проверяющих сначала переменную xn–k+1 , затем – переменную xn–k , и т. д.,
наконец – переменную x1 . Проверку каждой
переменной будем называть шагом.
Под lin-наследованием наборов будем понимать следующий процесс добавления наборов
при переходе от шага к шагу. Пусть на шагах,
связанных с проверкой переменных xj , xj–1 , …,
xj–s+1, в проверяющий тест были добавлены некоторый набор η% , s + k – 1 наборов, соседних с
η% по переменным xj–s+1, xj–s+2, …, xj+k–1, и еще по
одному какому-то набору для каждой из переменных xj , xj–1 , …, xj–s+1. Тогда для осуществления шага, связанного с проверкой переменной
xj–s, в проверяющий тест достаточно добавить
набор, соседний с η% по переменной xj–s , и еще
один какой-то набор. При этом набор η% будем
называть главным набором lin-наследования.
Пусть начинается очередной шаг построения
теста и при этом проверяется переменная xj .
Рассмотрим различные случаи в зависимости от
того, какие векторы порождаются различными
% %
% % ),
(для всевозможных α,β
подкубами вида B α,β
k, j
– далее просто «подкубами».
1. Для переменной xj существует замечательная тройка. Тогда особый набор из нее
включаем в тест, переходим к следующему шагу.
2. Замечательных троек нет, но есть перспективная пара наборов. Рассмотрим k подку(1),β% (1)
бов Bkα%, j
(2), % (2)
( k ), % ( k )
, Bkα%, j −1β ,… , Bkα%, j − kβ+1 , содержащих
эту пару. Заметим, что векторы значений функции f на всех этих подкубах неконстантные.
Выберем входной набор, принадлежащий всем
подкубам (главный набор lin-наследования),
добавим в тест его и все соседние ему по компонентам xj+k–1, …, xj–k+1 наборы. Если вектор
( i ), % ( i )
f [ Bkα%, j −iβ+1 ] ( i ∈ {1,..., k} ) — вектор F-типа, то
так мы сможем отличить от исходной функции f
все функции неисправностей, связанные с проверкой переменной xj–k+1, кроме, быть может,
одной. Добавим еще по одному некоторому набору для каждой переменной xj–k+1 (i ∈ {1, …,
k}). Так мы сможем отличить исходную функцию f от всех отличных от нее функций неисправностей, связанных с проверкой переменной
( i ), % ( i )
xj–k+1 (если f [ Bkα%, j −iβ+1 ] – вектор C-типа, то следует добавлять его особый набор). Итого, сде-
155
лано k шагов, добавлено 3k наборов в тест. Это
типичный пример lin-наследования.
%
%
3. Все подкубы Bkα,β
, j порождают констант-
ные векторы. В этом случае в тест добавить нечего, шаг завершен.
4. Пусть теперь среди векторов
%
%
f [ Bkα,β
,j ]
встречаются только константные и бесперспективные, но не одни только константные.
4.1. Пусть для переменной xj найдутся два
соседних подкуба, порождающих различные
бесперспективные векторы или же бесперспективный и константный векторы. Тогда на следующем шаге один из векторов значений, который «покрывается» двумя данными векторами
(первая половина компонент принадлежит одному вектору, вторая половина – другому), будет либо перспективным, либо замечательным.
%
%
Выберем подкуб Bkα,β
, j , соответствующий бес-
перспективному вектору данного шага, и доба% %
% Bkα,β
вим в тест тот набор η∈
, j , который порождает перспективную пару наборов следующего
шага, а также k соседних с η% по переменным xj ,
…, xj+k–1 наборов из этого подкуба и еще один
набор для проверки переменной xj . Затем выберем еще k подкубов, содержащих перспективную пару наборов следующего шага, и проведем в итоге k + 1 шаг с lin-наследованием (как в
п. 2), – тогда, добавив в тест 3k + 2 набора, завершим k + 1 шаг.
4.2. Пусть для xj есть только такие соседние
подкубы, которые порождают либо равные бесперспективные векторы, либо константные векторы, но не только равные константные векторы. Тогда на данном шаге добавим k + 2 набора,
необходимые для проверки переменной xj , а на
следующем один из векторов, покрываемый
соседними различными константными векторами, будет перспективным. Проведем еще k шагов с lin-наследованием (как в п. 2). Итого, завершен k + 1 шаг, добавлено 4k + 2 набора в
тест.
4.3. Пусть теперь среди векторов для xj
встречаются только соседние равные бесперспективные векторы и соседние равные константные векторы. Заметим, что при «склейке»
равных константных векторов (порожденных
соседними подкубами) на следующем шаге получаются равные константные векторы. При
«склейке» равных бесперспективных векторов
(порожденных соседними подкубами) на следующем шаге получаются два вектора, у каждого из которых первая половина значений равна
второй. Эти векторы могут быть константными,
156
Е.В. Морозов, Д.С. Романов
бесперспективными или замечательными. Возможны следующие варианты.
4.3.1. Можно провести некоторое количество
p шагов с lin-наследованием, такое, что главный
его набор η% на всех этих шагах будет лежать в
подкубах, порождающих бесперспективные или
замечательные векторы, а на шаге p + 1 набор a%
будет лежать в подкубе, порождающем перспективную пару. Тогда следует выполнить еще
k шагов с lin-наследованием (как в п. 2), выбирая за главный набор нового lin-наследования
один из наборов перспективной пары. Итого,
выполнено p + k шагов, добавлено 4k + 2p наборов в тест.
4.3.2. Пусть при любом таком lin-наследовании, что главный его набор η% на всех шагах лежит в подкубах, порождающих бесперспективные или замечательные векторы, оказывается, что на следующем шаге η% лежит в подкубе, порождающем константный вектор. Пусть
p – максимальное число шагов в таком linнаследовании. Если p ≥ k, то за p = k + q шагов в
тест добавлено k + 2p = 3k + 2q наборов. Пусть
теперь p < k и на (p + 1)-м шаге проверяется переменная xj – p .
%
%
4.3.2.1. Допустим, есть подкуб Bkα,β
, j − p , по-
рождающий неконстантный вектор. Тогда в
этом подкубе найдутся два набора η% ′ , η% ′′ , соседних по какой-то переменной xj – p + i – 1 (i ∈ {1,
~′) ≠ f (η
~′′). Если j – p +
2, …, k}) и таких, что f (η
+ i – 1 < j, то на шаге p – i + 2 наборы η% ′ и η% ′′ –
перспективная пара. Далее можно провести, как
в п. 2, еще k шагов lin-наследования: сделан
p – i + k + 1 шаг, в тест добавлено 4k + 2(p – i)
наборов. Если же j – p + i – 1 ≥ j, то можно было
бы провести p + 1 шаг такого lin-наследования с
главным набором η% ′ , что на всех этих шагах η% ′
лежит в подкубах, порождающих неконстантные векторы. Тогда либо имеет место случай,
отличный от 4.3.2 (и рассмотренный выше), либо приходим к противоречию с максимальностью выбора p.
4.3.2.2. Теперь допустим, что переменная
xj – p непроверяема, но некоторая переменная
xj – l , p ≤ l, проверяема (l выбирается наименьшим натуральным из возможных). Тогда у переменной xj – l + 1 существует пара соседних различных константных векторов. В этом случае в
тест за не менее чем p + 1 + k шагов добавится
не более чем 4k + 2p наборов.
Легко видеть, что если проверка переменной
x1 не прерывает никакую из описанных выше
серий шагов, то за каждые k шагов в тест добав-
ляется не более чем 4k наборов. Общее число
наборов в тесте при этом не превзойдет
⎡(n − k + 1) / k ⎤ ⋅ 4k . Если проверка переменной
x1 прервет последнюю серию шагов, то к полученной в предыдущем случае верхней оценке
следует добавить еще 2k наборов. Построение
теста и доказательство теоремы завершено.
Теперь докажем, что, рассматривая только
функции f ( x n ) без фиктивных переменных,
верхнюю оценку можно в ряде случаев понизить.
Теорема 2. Пусть n, k ∈ N, 2 ≤ k ≤ n. Тогда
(detect
Lk ,Φ (n) ≤ 2n + ⎡ n−k +1 ⎤ (k + 4) + 6 .
⎢ k ⎥
Доказательство. Разобьем процесс построения теста на две части. В первой в качестве системы функций-слипаний ϕi ( y% k ) рассмотрим
систему
двух
функций
{ y1 ⊕ ... ⊕ yk , y1 ⊕ …
⊕ yk ⊕ 1} . Пусть f ( x1 ,…, xn ) — произвольная
булева функция. Организуем процесс построения теста для f аналогично предыдущей теореме, но вместо lin-наследования будем использовать lin*-наследование, заключающееся в следующем. Пусть на шагах, связанных с проверкой переменных xj, xj–1, …, xj–s+1, в проверяющий тест были добавлены некоторый набор η% и
еще по одному какому-то набору для каждой из
переменных xj, xj–1, …, xj–s+1. Тогда для осуществления шага, связанного с проверкой переменной xj–s , в проверяющий тест достаточно
добавить еще один какой-то набор. При этом
набор η% будем называть главным набором lin*наследования.
Поскольку все рассматриваемые в этой части
доказательства случаи буквально соответствуют
случаям из доказательства теоремы 1, опустим
их перебор, заметив, что если проверка переменной x1 не прерывает никакую из серий шагов одного случая, то за каждые k шагов в тест
добавляется не более чем 4 + k наборов. Общее
число наборов, добавленных в тест, при этом не
превзойдет ⎡(n − k + 1) / k ⎤ ⋅ (4 + k ) . Если проверка переменной x1 прервет последнюю серию
шагов, то к полученной в предыдущем случае
оценке следует добавить еще 6 наборов.
Теперь рассмотрим в качестве системы
функций-слипаний ϕi ( y% k ) систему всех линейных функций k переменных, у каждой из которых есть хотя бы одна фиктивная переменная.
Так как функция f существенно зависит от всех
своих переменных, то для каждой ее переменной существует пара соседних наборов, на ко-
О тестах относительно локальных линейных слипаний переменных в булевых функциях
торой значения функции различаются. Заметим,
что если слипание произошло, то хотя бы одна
переменная получившейся функции неисправности стала фиктивной, и на каждой паре соседних наборов ее значения совпадают. Таким
образом, для построения проверяющего теста к
построенному ранее множеству наборов следует добавить проверяющий тест существенности
переменных функции f, в котором не более 2n
наборов.
Итого, получаем верхнюю оценку 2n –
− ⎡(n − k + 1) / k ⎤ ⋅ (4 + k ) + 6 . Теорема доказана.
Замечание. В.Н. Носков [4] установил точное значение функции Шеннона D(n) длины
проверяющего теста относительно константных
неисправностей переменных в булевых функциях (λ ∈ N ∪ {0}):
⎧⎪2n − 2λ + 1, если 2λ−1 + λ < n ≤ 2λ + λ,
D ( n) = ⎨
если n = 2λ−1 + λ.
⎪⎩ 2n − 2λ,
С использованием этого результата оценку в
последней теореме можно понизить не менее
чем на 2log2 (n – log2 n – 1) – 1.
Теорема 3. Каждая из функций Шеннона
(
detect
L lin (n) , Ldetect
k ,Φ ( n) не меньше величины n – k +
k ,Φ
+ 1 + ⎡(n – k + 1)/(k – 1)⎤ .
Доказательство.
Будем
рассматривать
функцию h( x% n ) = x1 x2 L xn . Пусть T — некоторое неупорядоченное множество наборов, 1 ≤ j ≤
≤ n – k + 1. Всякий булев набор вида (1, …, 1, αj,
…, αj,k–1, 1, …, 1) назовем xj-набором. Пусть
χ(α% ) есть число тех переменных xj , для которых набор α% ∈ B n является xj-набором. Пусть,
далее, νj (T) есть число различных xj-наборов,
входящих во множество T. Нетрудно показать,
что если найдется j′ ∈ {1, 2, …, n – k + 1}, такое,
что νj′ (T) < k + 2, то T не является полным проверяющим тестом относительно локальных линейных k-кратных слипаний переменных для
h( x% n) . Обозначим νˆ j (T ) = min(ν j (T ), k + 2) . Тогда ясно, что для того, чтобы множество T было
проверяющим тестом относительно линейных
локальных k-кратных слипаний переменных,
необходимо, чтобы величина I (T ) =
n − k +1
∑ νˆ j (T )
j =1
была бы не меньше (n – k + 1)(k + 2). А следовательно, и величина J (T ) = ∑χ(α% ) должна быть
% T
α∈
не меньше (n – k + 1)(k + 2) (так как
J (T ) =
n − k +1
∑ ν j (T ) ). Заметим, что
j =1
χ(1% n ) = n − k +
157
+1 , что при любом j ∈ {k, …, n – k + 1}:
χ(1% j −1 , 0, 1% n − j ) = k , и что для всех остальных наборов α% ∈ B n : χ(α% ) ≤ k − 1 . Теперь легко видеть,
что для выполнения неравенства J(T) ≥ (n – k +
+ 1)(k + 2) необходимо (поскольку J (T ) ≤
≤ (n − k + 1) + (n − k )k + (| T | −(n − k + 1)) × (k − 1)),
чтобы
|T |≥ (n − k + 1) +
⎡ (n − k + 1)(k + 2) − (n − k + 1)k − (n − k + 1) ⎤
+⎢
⎥=
k −1
⎢
⎥
⎡ n − k + 1⎤
=n−k +1+ ⎢
⎥.
⎢ k −1 ⎥
Из теорем 1–3 вытекает
Теорема 4. Пусть n, k ∈ N, 2 ≤ k ≤ n, n →∞,
n – k → ∞. Тогда порядок роста каждой из
(
функций Шеннона Ldetectlin (n) , Ldetect
k ,Φ ( n) есть
k ,Φ
Θ(n – k).
О диагностических тестах
Исследуем теперь поведение функции Шеннона длины диагностического теста относительно локальных k-кратных линейных слипаний переменных.
В работе [3] доказана следующая теорема.
Теорема 5. Пусть n, k ∈ N, 2 ≤ k ≤ n . Пусть,
далее, l(Ψ) – длина минимального диагностического теста для матрицы, составленной из
всех столбцов системы Ψ. Тогда начиная
с некоторого n имеет место неравенство
Ldiagn
k ,Φ ( n) ≥ (l ( Ψ ) − 1)( n − k + 1) .
В случае линейных локальных слипаний
lin
l(Φ ) = k + 1. Поэтому получаем нижнюю оценку функции Шеннона Ldiagnlin (n) ≥ k (n − k + 1) .
k ,Φ
Лемма (см. [2]). Если строки теста T в
матрице M линейно зависимы относительно
операций покоординатного сложения строк по
модулю 2 и умножения строки на число 0 или 1,
то тест T не является тупиковым.
Через M + (Φ) будем обозначать матрицу, полученную из M(Φ) добавлением снизу строки
из единиц, через w(M) – максимальное число
линейно независимых строк M (ранг M).
Теорема 6. Пусть n, k ∈ N, 2 ≤ k ≤ n. Тогда
имеет место неравенство Ldiagnlin (n) ≤ (k + 1) ×
k ,Φ
×(n – k + 1) + 1.
Доказательство. Образуем линейное пространство P′ как линейную оболочку всех строк
158
Е.В. Морозов, Д.С. Романов
lin
матрицы M +(Φ ) относительно операций покоординатного сложения строк по модулю 2 и
умножения строки на число 0 или 1, а линейное
пространство P″ – как пространство из двух
элементов 0, 1 относительно тех же операций.
Ясно, что dim P′ = w( M + (Φ lin )) , dim P′′ = 1 . Рас-
смотрим произвольную булеву функцию f ( x% n) .
Легко видеть, что каждая строка таблицы неис(1)
( n − k +1)
) , где θ ∈
правностей имеет вид (θ, ξ% ,…, ξ%
( j)
∈ P″, ξ% ∈ P′ ( j = 1, n − k + 1 ). Линейную оболочку всех строк такого вида обозначим через
P. Пусть линейное пространство P0 состоит из
k +1
k +1
двух векторов (1, 0% 2 ( n − k +1) ) и (0, 0% 2 ( n − k +1) ) , а
линейное пространство Pj – из векторов
k +1
% 0% 2k +1 ( n − j ) ) ( ξ% ∈ P ′ , j = 1, n − k + 1 ).
(0, 0% 2 ( j −1) , ξ,
Ясно, что P = P0 ⊕ P1 ⊕ …⊕ Pn − k +1 (прямая сумма подпространств), а значит,
dim P =
n − k +1
∑
j =0
+
n − k +1
∑
dim Pj = dim P′′ +
dim P′ = 1 + w( M + (Φ lin ))(n − k + 1).
j =1
Так как минимальный диагностический тест
для f ( x1 ,…, xn ) относительно локальных kкратных слипаний переменных является минимальным (и, значит, тупиковым) для таблицы
неисправностей, то, в силу произвольности выбора f ( x1 ,…, xn ) , по лемме имеем:
Ldiagnlin (n) ≤ w( M + (Φ lin ))(n − k + 1) + 1.
k ,Φ
Утверждение теоремы теперь следует из того, что w( M + (Φ lin )) ≤ dim P′ = k + 1 .
Из теорем 5 и 6 получаем утверждение.
Теорема 7. Пусть n, k ∈ N, 2 ≤ k ≤ n, n → ∞,
k → ∞, k = o(n). Тогда Ldiagnlin (n) = k (n − k ) ×
k ,Φ
×(1 + o(1)).
Авторы выражают глубокую благодарность
профессору Сергею Андреевичу Ложкину за
обсуждение работы и ценные замечания.
Работа выполнена при финансовой поддержке
грантов РФФИ № 10-01-00768-а и № 12-01-00964-а.
Список литературы
1. Редькин Н.П. Надежность и диагностика схем.
М.: Изд-во МГУ, 1992. 192 с.
2. Соловьев Н.А. Тесты (теория, построение,
применение). Новосибирск: Наука, СО, 1978. 192 с.
3. Носков В.Н. Диагностические тесты для входов логических устройств // Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1974. № 26. С. 72–83.
4. Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ. Новосибирск: ИМ СО АН СССР, 1975.
№ 27. С. 23–51.
5. Носков В.Н. О длинах минимальных единичных диагностических тестов, контролирующих работу входов логических схем // Методы дискретного
анализа в синтезе управляющих систем. Новосибирск: ИМ СО АН СССР, 1978. № 32. С. 40–51.
6. Носков В.Н. Об универсальных тестах для диагностики одного класса неисправностей комбинационных схем // Методы дискретного анализа в решении экстремальных задач. Новосибирск: ИМ СО
АН СССР, 1979. № 33. С. 41–52.
7. Нурмеев Н.Н. Об универсальных диагностических тестах для одного класса неисправностей комбинационных схем // Вероятностные методы и кибернетика. Вып. 18. Казань: КазГУ, 1982. С. 73–76.
8. Погосян Г.Р. О проверяющих тестах для логических схем // М.: Изд-во ВЦ АН СССР, 1982. 57 с.
9. Кузнецов И.А., Романов Д.С. О полных проверяющих тестах относительно локальных слипаний
переменных в булевых функциях // Уч. зап. Казан.
гос. ун-та. Сер. Физико-математические науки. 2009.
Т. 151, кн. 2. С. 90–97.
10. Романов Д.С. О диагностических тестах относительно локальных слипаний переменных в булевых функциях // Прикладная математика и информатика. Тр. факультета Вычислительной математики и
кибернетики МГУ им. М.В. Ломоносова. Вып. 36.
М.: МАКС Пресс, 2010. С. 91–98.
ON THE TESTS FOR LOCAL LINEAR CONGLUTINATIONS OF VARIABLES IN BOOLEAN FUNCTIONS
E.V. Morozov, D.S. Romanov
Nontrivial bounds are proved for Shannon functions for checking test length (within the order of growth) and for diagnostic test length (within the asymptotics under certain conditions) for local k-adic linear conglutinations of variables
in Boolean functions.
Keywords: boolean function, conglutination of variables, checking test, diagnostic test, test-length Shannon function.
Документ
Категория
Без категории
Просмотров
3
Размер файла
498 Кб
Теги
локальные, теста, функция, булевых, слипания, линейный, переменных, относительные
1/--страниц
Пожаловаться на содержимое документа