| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Краткие сообщения О тестах относительно локальных константных неисправностей фиксированной кратности на входах схем Г. В. Антюфеев, Д. С. Романовa a Московский государственный университет им. М. В. Ломоносова
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 3, Pages DOI: https://doi.org/10.1134/S0001434623090109 
Реферативные базы данных:
  Задачи тестирования логических схем, реализующих булевы функции или системы булевых функций, могут представлять интерес и как чисто математические задачи, связанные с распознаванием и классификацией булевых функций или их систем, и как задачи, имеющие прикладной аспект, связанный с тестированием и верификацией логических частей интегральных схем. Пусть $E_2=\{0,1\}$, $E_2^n=\{(\alpha_1,\dots,\alpha_n)\mid\alpha_i\in E_2,\, i=1,\dots, n\}$. Через $P_2(n)$ будем обозначать множество всех булевых функций вида $f(x_1,\dots,x_n)$ (иначе: $f({\widetilde x}^n)$), т.е. $P_2(n)=\{f({\widetilde x}^n)\mid f\colon E_2^n\to E_2\}$. Отсутствующие в этой работе определения можно найти в книге [1]. Допустим, на логическую схему (для определенности – на схему из функциональных элементов над полным базисом $B$) $S$, реализовывавшую булеву функцию $f(x_1,\dots,x_n)$, мог до момента исследования подействовать источник неисправностей $U$, способный преобразовать схему $S$ в любую схему из конечного содержащего исходную схему $S$ множества $H$ схем (традиционно такое множество $H$ схем восстанавливается однозначно по исходной схеме и описанию источника неисправностей полным перебором). Обычно предполагается, что источник неисправностей не вносит в схемы новые входы и выходы (т.е. как сама схема $S$, так и любая схема, полученная из нее действием источника неисправностей $U$, имеют один и тот же набор входных переменных $(x_1,\dots,x_n)$ и один выход). Тестовое исследование схемы заключается в анализе выходных значений, возникающих как реакция схемы на подачу на входы схемы входных наборов (т.е. наборов значений входных переменных). Определение 1. Множество $T$ входных наборов называется проверяющим тестом для схемы $S$ относительно источника неисправностей $U$ тогда и только тогда, когда для любой схемы $S'$ из множества $H$ справедливо: если $S'$ реализует некоторую булеву функцию $g(x_1,x_2,\dots,x_n)$, не равную $f(x_1,x_2,\dots,x_n)$, то найдется набор $\widetilde{\alpha}$ из $T$ такой, что $f(\widetilde{\alpha})\ne g(\widetilde{\alpha})$. Определение 2. Множество $T$ входных наборов называется диагностическим тестом для схемы $S$ относительно источника неисправностей $U$ тогда и только тогда, когда для любых двух схем $S_1$, $S_2$ из множества $H$ справедливо: если $S_1$ и $S_2$ реализуют неравные булевы функции $g'(x_1,x_2,\dots,x_n)$ и $g''(x_1,x_2,\dots,x_n)$ соответственно, то найдется набор $\widetilde{\alpha}$ из $T$ такой, что $g'(\widetilde{\alpha})\ne g''(\widetilde{\alpha})$. Число наборов в тесте $T$ называется длиной теста и обозначается $L(T)$. Тест минимальной длины называется минимальным. Длина минимального проверяющего (диагностического) теста для схемы $S$ относительно источника неисправностей $U$ обозначается через $L^{\mathrm{dt}}(U,S)$ ($L^{\mathrm{dn}}(U,S)$). Под длиной проверяющего (диагностического) теста для булевой функции $f$ относительно источника неисправностей $U$ понимается величина $L^{\mathrm{dt}}(U,f)$ (соответственно $L^{\mathrm{dn}}(U,f)$), равная минимуму по всем реализующим $f$ схемам из функциональных элементов $S$ над базисом $B$ величин $L^{\mathrm{dt}}(U,S)$ (соответственно $L^{\mathrm{dn}}(U,S)$). Определение 3. Функцией Шеннона длины проверяющего (диагностического) теста относительно источника неисправностей $U$ называется величина (соответственно $L^{\mathrm{dn}}(U,n)=\max_{f\in P_2(n)}L^{\mathrm{dn}}(U,f)$). Неисправности на входах схем действуют одинаково вне зависимости от реализующей функцию схемы, так что схемная реализация функции для таких неисправностей не имеет значения, важна лишь сама функция. Константные неисправности на входах схем, фактически, заключаются в подстановках происвольных булевых констант вместо переменных булевых функций. Константные неисправности являются классическим и, в ряде случаев, модельным классом неисправностей. В обозначениях источников константных неисправностей на входах схем будем придерживаться следующих правил. Буква $P$ показывает, что это источник неиправностей на входах схем. Верхний индекс “${\mathrm{c}}$” (“${\mathrm{lc}}$”) указывает на произвольные константные неисправности (соответственно локальные произвольные константные неисправности, при которых константы подставляются только вместо подряд идущих переменных) на входах схем. Верхний индекс “0” (“1”) указывает на однотипные константные неисправности типа “нуль” (соответственно типа “один”) на входах схем. Нижний индекс “$k$” (соответственно “$=k$”) означает, что количество забитых константами переменных не больше $k$ (соответственно в точности равно $k$); отсутствие нижнего индекса символизирует произвольность числа забитых константами переменных. Приведем обзор известных оценок функций Шеннона длин тестов относительно константных неисправностей на входах схем. Если не оговорено иное, то приведенные оценки справедливы при всех целых положительных $n$. Согласно Вейссу [2], 1972 г, для $n\geqslant 5$. Согласно Носкову [3], 1975 г.,
$$
\begin{equation*}
L^{\mathrm{dt}}(P^{\mathrm{c}},n)=L^{\mathrm{dt}}(P_1^{\mathrm{c}},n)=2n-2t+1,
\end{equation*}
\notag
$$
если $n=k^{t-1}+t$, и
$$
\begin{equation*}
L^{\mathrm{dt}}(P^{\mathrm{c}},n)=L^{\mathrm{dt}}(P_1^{\mathrm{c}},n)=2n-2t,
\end{equation*}
\notag
$$
если $k^{t-1}+t<n\leqslant k^{t}+t$, при $k=2$, $n\geqslant 136$. Последний результат был обобщен Погосяном [4] на $k$-значный случай при всех $k\geqslant 2$ и $n\geqslant 1$ (1982 г.). Согласно Носкову [5], 1978 г., Согласно Носкову [6], 1974 г.,
$$
\begin{equation*}
\log_2 L^{\mathrm{dn}}(P_k^{\mathrm{c}},n)=k\log_2\biggl(\frac nk\biggr)\cdot (1+o(1))
\end{equation*}
\notag
$$
при $n\to\infty$ и $k=o(n)$;
$$
\begin{equation*}
2^{\lfloor n/2\rfloor}-1\leqslant L^{\mathrm{dn}}(P^{\mathrm{c}},n)\leqslant 4(n+1)^3\cdot 2^{0,773n},
\end{equation*}
\notag
$$
причем нижняя оценка только заявлена, а доказывается более слабая нижняя оценка. Согласно Попкову [7], 2016 г., при четных $n$ и
$$
\begin{equation*}
L^{\mathrm{dn}}(P^{\mathrm{c}},n)\geqslant \biggl\lfloor\frac{2\sqrt{2}}{3}\cdot 2^{n/2}\biggr\rfloor
\end{equation*}
\notag
$$
при нечетных $n$;
$$
\begin{equation*}
L^{\mathrm{dn}}(P^{\mathrm{0}},n)=L^{\mathrm{dn}}(P^{\mathrm{1}},n)> \frac{2^{n/2}\cdot {\sqrt[4]{n}}}{2\sqrt{n+0,5\log_2n +2}}.
\end{equation*}
\notag
$$
Согласно авторам [8], 2016 г.; [9]
$$
\begin{equation*}
L^{\mathrm{dn}}(P^{\mathrm{c}},n)\geqslant 2^{\lfloor n/2\rfloor+1}\cdot(1+o(1)), \qquad \log_2 L^{\mathrm{dn}}(P_{=k}^{\mathrm{lc}},n)= k\cdot (1+o(1))
\end{equation*}
\notag
$$
при $n\to\infty$, $k=k(n)\to\infty$, $2\leqslant k\leqslant n/2$ и $\log_2 n=o(k)$. Вытеснениями переменных константные неисправности на входах схем обобщаются следующим образом. Каждая переменная булевой функции считается или вытесняемой, или вытесняющей. Под вытеснением переменных понимается подстановка вместо каждой вытесняемой переменной произвольной функции, зависящей лишь от вытесняющих переменных. Источник вытеснений переменных обозначим через $P^{\mathrm{extr}}$. Морозов [10] в 2015 г. установил следующие оценки:
$$
\begin{equation*}
L^{\mathrm{dt}}(P^{\mathrm{extr}},n)=2n-\log_2{n}\cdot (1+o(1)), \qquad L^{\mathrm{dn}}(P^{\mathrm{extr}},n)=2^n\cdot (1+o(1)).
\end{equation*}
\notag
$$
В настоящей работе авторами продолжено исследование функций Шеннона длин тестов относительно локальных константных неисправностей фиксированной кратности на входах схем. В доказательствах теорем используются некоторые идеи из работ [6], [3] и [1; с. 117–119]. В теореме 1 приводятся оценки функции Шеннона длины проверяющего теста относительно локальных константных неисправностей кратности $k$ на входах схем. Теорема 1. Пусть $n$ и $k$ – целые положительные, $2\leqslant k\leqslant n$. Тогда имеют место неравенства Доказательство. Установим справедливость верхней оценки $L^{\mathrm{dt}}(P_{=k}^{\mathrm{lc}},n)$. Рассмотрим произвольную булеву функцию $f({\widetilde x}^n)$. Организуем следующий процесс, выбирающий по функции $f({\widetilde x}^n)$ конечную возрастающую последовательность $A_f$ натуральных чисел $\nu_1$, $\nu_2,\dots$, $\nu_t$, являющихся индексами существенных переменных функции $f$. Если функция $f({\widetilde x}^n)$ тождественно равна константе, то искомая последовательность $A_f$ не содержит элементов. Далее рассматривается альтернативный случай. Разобьем набор $(x_1,\dots,x_n)$ всех переменных на непересекающиеся последовательные отрезки:
$$
\begin{equation*}
\begin{gathered} \, d_1=(x_1,\dots,x_k), \qquad d_2=(x_{k+1},\dots,x_{2k+1}), \qquad d_3=(x_{2k+2},\dots,x_{3k+2}), \qquad \dots, \\ d_{w-1}=(x_{(w-2)k+w-2},\dots,x_{(w-1)k+w-2}), \qquad d_{w}=(x_{(w-1)k+w-1},\dots,x_{n}). \end{gathered}
\end{equation*}
\notag
$$
При этом в отрезке $d_1$ ровно $k$ переменных, в каждом из отрезков $d_2, \dots,d_{w-1}$ ровно по $k+1$ переменных, в отрезке $d_w$ – не более чем $k$ переменных. Нетрудно видеть, что при $n=k$ имеется ровно один отрезок, а при $n>k$ число отрезков $w=\lceil(n+2/(k+1)\rceil$. Элементами последовательности $A_f$ оказываются (при наличии существенных переменных функции $f$ в соответствующих отрезках): максимальный индекс существенной переменной из отрезка $d_1$, минимальный и максимальный индексы существенных переменных из отрезка $d_j$, $j\in\{1, \dots, w-1\}$; если в $d_j$ имеется ровно одна существенная переменная, то ее индекс используется один раз в качестве элемента последовательности $A_f$, минимальный индекс существенной переменной из отрезка $d_w$. Другие числа не могут являться элементами $A_f$, выбранные же элементы $\nu_1,\nu_2,\dots, \nu_t$ упорядочиваются по возрастанию. Очевидно, что Для каждого элемента $\nu_s$ построенной последовательности, $s\in \{1,\dots,t\}$, включим в множество $T$ два соседних по переменной $x_{\nu_s}$ набора значений переменных $(x_1,\dots, x_n)$, на которых функция $f$ принимает разные значения (такая пара наборов найдется в силу существенности переменной $x_{\nu_s}$ для функции $f$). Один и тот же набор из множества $T$ в указанном в предыдущем предложении смысле может входить в несколько пар наборов – для нескольких существенных переменных функции $f$. Ясно, что при этом Оказывается, $T$ – проверяющий тест для функции $f$ относительно локальных константных неисправностей кратности $k$ на входах схем. Действительно, рассмотрим подстановку $k$ произвольных булевых констант $\sigma_1,\sigma_2,\dots,\sigma_k$ вместо переменных $x_j$, $x_{j+1},\dots,x_{j+k-1}$ соответственно,$j\in \{1,\dots,n-k+1\}$. Если все эти переменные функции $f({\widetilde x}^n)$ – фиктивные, то соответствующая подстановке функция неисправности $g({\widetilde x}^n)$ неотличима от $f({\widetilde x}^n)$. Если же среди переменных $x_j$, $x_{j+1},\dots,x_{j+k-1}$ имеется хотя бы одна существенная переменная, то среди индексов этих переменных по построению последовательности $A_f$ найдется хотя бы один элемент $\nu_{s'}$ этой последовательности. Действительно, если все переменные $x_j$, $x_{j+1},\dots,x_{j+k-1}$ попадают в один отрезок, то в случае отрезка $d_1$ или $d_w$ переменные $x_j$, $x_{j+1},\dots,x_{j+k-1}$ исчерпывают все переменные отрезка, так что искомый элемент $\nu_{s'}$ найдется (ибо не все переменные фиктивны для $f$), а в случае любого отрезка из числа $d_2, \dots,d_{w-1}$ переменными $x_j$, $x_{j+1},\dots,x_{j+k-1}$ выпускается ровно одна переменная из отрезка, но, поскольку среди переменных $x_j$, $x_{j+1},\dots,x_{j+k-1}$ есть существенная, то среди них есть переменная с минимальным или с максимальным индексом существенной переменной из отрезка, так что искомый элемент $\nu_{s'}$ найдется. Иначе, если переменные $x_j$, $x_{j+1},\dots,x_{j+k-1}$ попадают в два последовательных отрезка, то в силу наличия среди них существенной переменной по построению последовательности $A_f$ среди этих переменных найдется переменная с максимальным индексом $\nu_{s'}$ из первого (по возрастанию индексов) отрезка или найдется переменная с минимальным индексом $\nu_{s'}$ из второго отрезка. Значит, во всех возможных случаях искомый элемент $\nu_{s'}$ существует. На двух соответствующих элементу $\nu_{s'}$ соседних наборах из $T$ функция $f$ отличается от соответствующей рассматриваемой подстановке функции неисправности $g({\widetilde x}^n)$, ибо, в отличие от $f$, функция $g$ на этих наборах принимает одинаковые значения. Отметим, что в случае не содержащей элементов последовательности $A_f$ функция $f$ тождественно равна константе, так что минимальный проверяющий тест для $f$ пуст. Верхняя оценка доказана.
Докажем нижнюю оценку. Пусть сначала $n>k$. Найдем такое минимальное натуральное $l$, что имеет место неравенство
$$
\begin{equation*}
\biggl\lfloor\frac{2(n-l)}{k+1}\biggr\rfloor\leqslant 2^l.
\end{equation*}
\notag
$$
Ясно, что
$$
\begin{equation*}
l\leqslant\biggl\lceil\log_2\biggl\lfloor \frac{2n}{k+1}\biggr\rfloor\biggr\rceil.
\end{equation*}
\notag
$$
Рассмотрим булеву функцию мультиплексорного типа
$$
\begin{equation*}
h_{n,k}(x_1,\dots,x_{n-l},x_{n-l+1},\dots,x_n)= \bigvee_{j=0}^{\lfloor2(n-l)/(k+1)\rfloor-1}K_j(x_{n-l+1},\dots,x_n)\cdot x_{\lfloor j(k+1)/2\rfloor+1},
\end{equation*}
\notag
$$
где $K_j(x_{n-l+1},\dots,x_n)=x_{n-l+1}^{\delta_1}\dotsb x_{n}^{\delta_l}$, причем $(\delta_1,\dots,\delta_l)\in E_2^l$ и $\sum_{i=1}^l\delta_i\cdot 2^{l-i}=j$. Заметим: неисправность, связанная с тем, что $k$ подряд идущих переменных
$$
\begin{equation*}
x_{\lfloor j(k+1)/2\rfloor+2},\dots, x_{\lfloor(j+2)(k+1)/2\rfloor}
\end{equation*}
\notag
$$
забиваются булевыми константами так, что переменная $x_{\lfloor(j+1)(k+1)/2\rfloor+1}$ забита константой $\sigma$, $j\in\{0,\dots,\lfloor 2(n-l)/(k+1)\rfloor-3\}$, $\sigma\in E_2$, обнаруживается на тех и только тех наборах значений переменных $(x_1,\dots,x_n)$, на которых $x_{\lfloor (j+1)(k+1)/2\rfloor+1}=\overline{\sigma}$, $x_{n-l+i}=\delta'_i$, $i=1,\dots,l$, причем $\sum_{i=1}^l\delta'_i \cdot 2^{l-i}=j+1$. А поскольку эти множества наборов для различных пар $(j+1,(\delta'_1,\dots,\delta'_l))$ попарно не пересекаются, из каждого из них в любой проверяющий тест должен войти хотя бы один набор, откуда получаем нижнюю оценку:
$$
\begin{equation*}
L^{\mathrm{dt}}(P_{=k}^{\mathrm{lc}},n)\geqslant L^{\mathrm{dt}}(P_{=k}^{\mathrm{lc}},h_{n,k})\geqslant 2\cdot\biggl(\biggl\lfloor\frac{2(n-l)}{k+1}\biggr\rfloor-2\biggr)\geqslant 2\cdot\biggl(\biggl\lfloor\frac{2\cdot(n-\lceil\log_2\lfloor 2n/(k+1)\rfloor\rceil)}{k+1}\biggr\rfloor-2\biggr).
\end{equation*}
\notag
$$
При $n=k$ имеем: $L^{\mathrm{dt}}(P_{=k}^{\mathrm{lc}},k)\geqslant L^{\mathrm{dt}}(P_{=k}^{\mathrm{lc}},x_{1})\geqslant 2$, что лучше нижней оценки, заявленной в формулировке теоремы. Теорема доказана. Следствие 1. Пусть $n$ и $k$ – целые положительные, $n\to\infty$, $2\leqslant k\leqslant n$, $k=k(n)$, $k=o(n)$. Тогда имеет место асимптотическое равенство В следующей теореме приводятся оценки функции Шеннона длины диагностического теста относительно локальных константных неисправностей кратности $k$ на входах схем. Теорема 2. Пусть $n$ и $k$ – целые положительные, $c>1$ – действительная константа, $2\leqslant k\leqslant n/(2c)$. Тогда имеют место неравенства Доказательство. Верхняя оценка функции Шеннона длины диагностического теста элементарно вытекает из того, что количество всех попарно неравных функций неисправности, получаемых из произвольной булевой функции $f({\widetilde x}^n)$ всевозможными локальными $k$-кратными неисправностями на входах схем (включая саму функцию $f$), не превосходит величины $(n-k+1)\cdot 2^{k}+1$ (см., например, [11; лемма 8.2 на с. 68]). Докажем нижнюю оценку функции Шеннона. Найдем такое минимальное натуральное $l$, что имеет место неравенство $(n-l-k+1)\cdot 2^{k-2}\leqslant 2^l$. Ясно, что
$$
\begin{equation*}
k-2+\lceil\log_2(n-k+1)\rceil\geqslant l> k-3+\log_2(n-2k+2).
\end{equation*}
\notag
$$
Выберем некоторое инъективное отображение $\eta\colon \{1,\dots,n-l-k+1\}\times E_2^{k-2}\to E_2^{l}$ (оно, очевидно, существует). Рассмотрим булеву функцию
$$
\begin{equation*}
\begin{aligned} \, h_{n,k}({\widetilde x}^n) &=\bigvee_{j=1}^{n-l-k+1}\bigvee_{(\sigma_2,\dots,\sigma_{k-1})\in E_2^{k-2}} {\overline x}_1\dotsb {\overline x}_{j-1}x_jx_{j+1}^{\sigma_2}\times \dotsb \\ &\qquad\times x_{j+k-2}^{\sigma_{k-1}}x_{j+k-1}{\overline x}_{j+k}\dotsb {\overline x}_{n-l}x_{n-l+1}^{\xi_{j,1}}\dotsb x_{n}^{\xi_{j,l}}, \end{aligned}
\end{equation*}
\notag
$$
где $(\xi_{j,1},\dots,\xi_{j,l})=\eta(j,(\sigma_2,\dots,\sigma_{k-1}))$. Для всякого $j$, $j\in \{1,\dots,n-l-k+1\}$, при подстановке в функцию $h_{n,k}(x_1,\dots,x_n)$ булевых констант $1$, $\sigma_2,\dots, \sigma_{k-1}$, $1$ вместо переменных $x_j$, $x_{j+1},\dots,x_{j+k-2}, x_{j+k-1}$ (соответственно) получается функция неисправности вида
$$
\begin{equation}
h_{n,k}^{(j,(\sigma_2,\dots,\sigma_{k-1}))}({\widetilde x}^n)= {\overline x}_1\cdots {\overline x}_{j-1}{\overline x}_{j+k}\cdots {\overline x}_{n-l}x_{n-l+1}^{\xi_{j,1}}\cdots x_{n}^{\xi_{j,l}},
\end{equation}
\tag{1}
$$
где $(\xi_{j,1},\dots,\xi_{j,l})=\eta(j,(\sigma_2,\dots,\sigma_{k-1}))$. Пусть $h_{n,k}^{(j',(\sigma'_2,\dots,\sigma'_{k-1}))}({\widetilde x}^n)$ и $h_{n,k}^{(j'',(\sigma''_2,\dots,\sigma''_{k-1}))}({\widetilde x}^n)$ – две различные функции неисправности вида (1), $(j',(\sigma'_2,\dots,\sigma'_{k-1}))\ne (j'',(\sigma''_2,\dots,\sigma''_{k-1}))$. Поскольку любые две такие функции обращаются в единицу на непересекающихся множествах наборов в силу инъективности отображения $\eta$, заключаем: для того, чтобы попарно отличить друг от друга все различные функции неисправности вида (1), требуется не менее $(n-l-k+1)\cdot 2^{k-2}-1$ наборов. Отсюда получаем оценку: Теорема доказана. Следствие 2. Пусть $n$ и $k$ – целые положительные, $n\to\infty$, $c>1$ – действительная константа, $2\leqslant k\leqslant n/(2c)$, $k=k(n)$. Тогда имеет место следующее равенство функций по порядку роста: $L^{\mathrm{dg}}(P_{=k}^{\mathrm{lc}},n)=\Theta(n2^{k})$. 
Цитирование в формате AMSBIB
\RBibitem{AntRom23} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|