| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Краткие сообщения О диагностических тестах относительно локальных зеркальных отражений на входах схем М. К. Альбекa, Д. С. Романовb a Казахстанский филиал Московского государственного университета им. М. В. Ломоносова, г. Астана b Московский государственный университет им. М. В. Ломоносова
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 5, Pages DOI: https://doi.org/10.1134/S0001434624050195 
Реферативные базы данных:
  В настоящей статье исследуются специальные задачи, связанные с тестированием логических схем, реализующих булевы функции. Задачи такого рода могут рассматриваться и как сугубо математические задачи, связанные с распознаванием и классификацией булевых функций, и как прикладные задачи, соотносимые с тестированием и верификацией логических частей интегральных схем. Пусть $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$ в любую схему из конечного множества $H$ схем, содержащего исходную схему $S$ (обыкновенно такое множество $H$ схем может быть восстановлено по исходной схеме и описанию источника неисправностей). Обычно предполагается, что источник неисправностей не добавляет к схеме новые входы и выходы (то есть как сама схема $S$, так и любая схема, полученная из нее действием источника неисправностей $U$, имеют один и тот же набор входных переменных $(x_1,\dots,x_n)$ и один выход). Тестовое исследование схемы заключается в анализе выходных значений, возникающих как реакция схемы на подачу на входы схемы входных наборов (т.е. наборов значений входных переменных). Определение 1. Множество $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)$. Определение 2. Множество $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)$. Число наборов в тесте $T$ называется длиной теста и обозначается $L(T)$. Тест минимальной длины называется минимальным. Длина минимального диагностического теста для схемы $S$ относительно источника неисправностей $U$ обозначается через $L^{\mathrm{dn}}(U,S)$. Под длиной диагностического теста для булевой функции $f$ относительно источника неисправностей $U$ понимается величина $L^{\mathrm{dn}}(U,f)$, равная минимуму по всем реализующим $f$ схемам из функциональных элементов $S$ над базисом $B$ величин $L^{\mathrm{dn}}(U,S)$. Определение 3. Функцией Шеннона длины диагностического теста относительно источника неисправностей $U$ называется величина $L^{\mathrm{dn}}(U,n)=\max_{f\in P_2(n)}L^{\mathrm{dn}}(U,f)$. Аналогично вводится функция Шеннона $L^{\mathrm{dt}}(U,n)$ длины проверяющего теста относительно источника неисправностей $U$. Неисправности на входах схем действуют одинаково вне зависимости от реализующей функцию схемы, так что схемная реализация функции для таких неисправностей не имеет значения, важна лишь сама функция. Неисправности типа перепутываний входов схем представляют собой перестановки аргументов булевых функций. Зеркальные неисправности на входах схем определяются следующим образом. При одиночной зеркальной неисправности на входах схем источником неисправностей выбираются два натуральных числа $a_1$, $b_1$ таких, что $1\leqslant a_1< b_1\leqslant n$, и вместо исходной булевой функции
$$
\begin{equation*}
f(x_1,\dots,x_{a_1-1},x_{a_1},x_{a_1+1},\dots,x_{b_1-1},x_{b_1},x_{b_1+1},\dots,x_n)
\end{equation*}
\notag
$$
неисправной схемой реализуется булева функция
$$
\begin{equation*}
f(x_1,\dots,x_{a_1-1},x_{b_1},x_{b_1-1},\dots,x_{a_1+1},x_{a_1},x_{b_1+1},\dots,x_n)
\end{equation*}
\notag
$$
(т.е. переменные с $x_{a_1}$ по $x_{b_1}$ выстраиваются в противоположном порядке). При кратной зеркальной неисправности произвольной кратности на входах схем источником неисправностей выбираются натуральные числа $t,a_1,b_1,\dots,a_t,b_t$ такие, что $1\leqslant a_1<b_1<\dots<a_t<b_t\leqslant n$, и вместо исходной булевой функции
$$
\begin{equation*}
\begin{aligned} \, &f(x_1,\dots, x_{a_1-1}, x_{a_1}, x_{a_1+1},\dots,x_{b_1-1}, \\ &\qquad x_{b_1}, x_{b_1+1},\dots, x_{a_t-1}, x_{a_t}, x_{a_t+1},\dots,x_{b_t-1}, x_{b_t}, x_{b_t+1},\dots,x_n) \end{aligned}
\end{equation*}
\notag
$$
неисправной схемой реализуется булева функция
$$
\begin{equation*}
\begin{aligned} \, &f(x_1,\dots, x_{a_1-1}, x_{b_1}, x_{b_1-1},\dots,x_{a_1+1}, \\ &\qquad x_{a_1}, x_{b_1+1},\dots, x_{a_t-1}, x_{b_t}, x_{b_t-1},\dots,x_{a_t+1}, x_{a_t}, x_{b_t+1},\dots,x_n) \end{aligned}
\end{equation*}
\notag
$$
(т.е. для каждого $i$, $i\in\{1,\dots,t\}$, переменные с $x_{a_i}$ по $x_{b_i}$ выстраиваются в противоположном порядке). Каждый отрезок из максимального по включению множества подряд идущих переменных, переставляемых источником неисправностей в противоположном порядке, мы будем называть зеркалом, а количество переменных в этом отрезке будем называть размером зеркала. Далее будут рассматриваться зеркальные отражения с зеркалами как произвольных, так и фиксированных размеров.
В обозначениях источников константных неисправностей на входах схем будем придерживаться следующих правил. Буква $P$ показывает, что это – источник неисправностей на входах схем. Верхний индекс указывает на тип неисправностей входов схем: “$\mathrm{prm}$” – произвольные перестановки, “$\mathrm{ccl}$” – циклические сдвиги всех переменных, “$\mathrm{tr}$” – транспозиции, “$\mathrm{lm}$” – локальные зеркальные неисправности с зеркалами произвольного размера, “$\mathrm{lm}(l)$” – локальные зеркальные неисправности с зеркалами размера $l$. Для случая последних трех верхних индексов нижний индекс “$k$” означает, что количество поломок (т.е. транспозиций для “$\mathrm{tr}$” и зеркал для “$\mathrm{lm}$”, “$\mathrm{lm}(l)$”) не больше $k$; отсутствие нижнего индекса отражает произвольность числа произведенных источником неисправностей поломок. Приведем обзор известных оценок функций Шеннона длин тестов относительно перепутываний входов схем и сходных источников неисправностей. Если не оговорено иное, то приведенные оценки справедливы при всех целых положительных $n$. Согласно Глазунову и Горяшко [2], 1986 г.,
$$
\begin{equation*}
L^{\mathrm{dt}}(P^{\mathrm{tr}},n)\geqslant\frac{1}{4}\cdot n\log_2 n\cdot(1+o(1)).
\end{equation*}
\notag
$$
Согласно Романову [3], 2007 г.,
$$
\begin{equation*}
L^{\mathrm{dn}}(P^{\mathrm{tr}}_1,n)\sim\frac{n^2}{2}\,;
\end{equation*}
\notag
$$
им же доказано [4], 2012 г., что
$$
\begin{equation*}
L^{\mathrm{dt}}(P^{\mathrm{prm}},n)\leqslant n\log_2 n
\end{equation*}
\notag
$$
и что $L^{\mathrm{dn}}(P^{\mathrm{prm}},n)\sim 2^n$. В работе Курбацкой [5], 2019 г., установлено, что $L^{\mathrm{dn}}(P^{\mathrm{ccl}},n)=n-1$ и что функция Шеннона длины диагностического теста относительно циклических сдвигов всех переменных и одиночной подстановки фиксированной константы вместо произвольной переменной ведет себя квадратично по числу переменных. Действие источника $P^{\mathrm{psh}}$ ($P^{\mathrm{psh}(l)}$) примитивных сдвигов переменных влево заключается в одновременном увеличении индексов всех $n$ переменных на произвольное (соответственно на равное $l$) и не большее $n$ натуральное число и в подстановке на места переменных с индексами, бо́льшими $n$, некоторых констант. Согласно Антюфееву и Романову [6], 2013 г.,
$$
\begin{equation*}
L^{\mathrm{dt}}(P^{\mathrm{psh}},n)=2, \qquad L^{\mathrm{dn}}(P^{\mathrm{psh}},n)=\Theta(2^{0,5n}),
\end{equation*}
\notag
$$
ими же в работе [7], 2020 г., получен такой результат:
$$
\begin{equation*}
L^{\mathrm{dn}}(P^{\mathrm{psh}(l)},n) \in[\min(2^l-1,2^{n-l});\min(2^l,2^{n-l}+1)].
\end{equation*}
\notag
$$
Антюфеевым в работе [8], 2020 г., показано, что функция Шеннона длины диагностического теста относительно примитивных сдвигов с фиксированным “наползающим” набором двоичных констант ведет себя линейно по числу переменных.
В настоящей работе авторы изучают поведение функций Шеннона длин диагностических тестов относительно локальных зеркальных неисправностей на входах схем. В теореме 1 приводятся оценки функций Шеннона длины диагностического теста относительно локальных зеркальных неисправностей (на входах схем) с размером зеркал $l$. Теорема 1. Пусть $n$ и $l$ – целые положительные, $2\leqslant l\leqslant n$. Тогда имеют место равенства Доказательство. Верхние оценки рассматриваемых функций Шеннона длины диагностического теста вытекают из того, что длина минимального диагностического теста для произвольной булевой функции $f(\widetilde x^n)$ не превосходит уменьшенного на 1 количества попарно неравных функций неисправности, включая исходную функцию $f$ (см., например, [1; теорема 7, с. 111–112]). Для случая одиночной зеркальной неисправности с размером зеркала $l$ указанное число функций неисправности всегда не превосходит $n-l+2$. Для случая кратных зеркальных неисправностей произвольной кратности с размерами зеркал $l$ указанное число функций неисправности по определению не превосходит количества способов выбора целых положительных чисел $t$, $a_1$, $a_2,\dots$, $a_t$ таких, что $1\leqslant a_1$, $a_i<a_{i+1}-(l-1)$ ($i=1,\dots,t-1$), $a_t\leqslant n-(l-1)$, т.е. не превосходит величины $\sum_{t=0}^{\lfloor n/l\rfloor}\binom{n-t(l-1)}{t}$.
Докажем нижние оценки. Для рассматриваемых в условии теоремы $n$, $l$ выберем булеву функцию $h_l(\widetilde x^n)$, обращающуюся в единицу лишь на одном наборе значений аргументов, а именно, на наборе Заметим: любая одиночная зеркальная неисправность, примененная к этому набору, заменит находящиеся по краям зеркала значения на противоположные. Поэтому все наборы, в которые может перейти $\widetilde\gamma_l^n$ при всевозможных одиночных зеркальных неисправностях (соответственно кратных зеркальных неисправностях произвольной кратности), попарно различны и не равны $\widetilde\gamma_l^n$, а границы зеркал конкретной неисправности легко распознаются по анализу значений функции неисправности на множестве $\widehat T_1$ (соответственно $\widehat T$), состоящем из всех таких наборов и самого́ набора $\widetilde\gamma_l^n$, – это притом, что на остальных наборах никакие функции неисправности, включая $h_l$, не будут отличаться одна от другой. Поскольку на каждом наборе из ${\widehat T}_1$ (соответственно из $\widehat T$) ровно одна из функций неисправности обращается в $1$, а все функции неисправности попарно различны, в любой минимальный диагностический тест относительно одиночных зеркальных неисправностей войдут все наборы из $\widehat T_1$ (соответственно из $\widehat T$), кроме какого-то произвольного одного набора: при включении в тест меньшего числа наборов найдутся две неотличимые функции неисправности, что противоречит определению диагностического теста. Поэтому (соответственно $L^{\mathrm{dn}}(P^{\mathrm{lm}(l)},h_l(\widetilde x^n)) \geqslant\sum_{t=1}^{\lfloor n/l\rfloor}\binom{n-t(l-1)}{t}$), что завершает доказательство теоремы.В теореме 2, фактически, устанавливается квадратичность по $n$ порядка роста функции Шеннона длины диагностического теста относительно одиночных локальных зеркальных неисправностей (на входах схем) с произвольными размерами зеркал. Доказательство. Верхняя оценка функции Шеннона длины диагностического теста аналогично доказательству теоремы 1 вытекает из теоремы 7 книги [1; с. 111–112].
Докажем нижнюю оценку функции Шеннона. Рассмотрим булеву функцию $\widehat h(\widetilde x^n)$, обращающуюся в единицу ровно на двух наборах, а именно, на наборах
$$
\begin{equation*}
\widetilde\gamma_2^n=(0,1,0,1,0,1,0,1,\dots)\qquad \text{и}\qquad \widetilde\gamma_3^n=(0,0,1,1,0,0,1,1,\dots).
\end{equation*}
\notag
$$
Имеют место следующие факты. Каждая функция неисправности имеет ровно два единичных значения. Любое зеркало нечетного размера переводит набор $\widetilde\gamma_2^n$ в себя. Зеркала четного размера переводят набор $\widetilde\gamma_2^n$ в попарно различные отличные от $\widetilde\gamma_2^n$ наборы. Всевозможные одиночные зеркала четного размера, на границах которых в наборе $\widetilde\gamma_3^n$ стоя́т неравные значения, переводят набор $\widetilde\gamma_3^n$ в попарно различные отличные от $\widetilde\gamma_3^n$ наборы (обозначим множество всех таких наборов через $B_n$, множество соответствующих функций неисправности – через $\mathscr B_n$, а множество всех наборов, в которые эти зеркала переводят набор $\widetilde\gamma_2^n$ – через $A'_n$). Всевозможные одиночные зеркала нечетного размера, на границах которых в наборе $\widetilde\gamma_3^n$ стоя́т неравные значения, переводят набор $\widetilde\gamma_3^n$ в попарно различные отличные от $\widetilde\gamma_3^n$ наборы (обозначим множество всех таких наборов через $C_n$, а множество соответствующих функций неисправности – через $\mathscr C_n$). Всевозможные одиночные зеркала четного размера, на границах которых в наборе $\widetilde\gamma_3^n$ стоя́т равные значения, переводят набор $\widetilde\gamma_3^n$ в себя (обозначим множество соответствующих функций неисправности через $\mathscr D_n$, а множество всех наборов, в которые эти зеркала переводят набор $\widetilde\gamma_2^n$ – через $A''_n$). Любое одиночное зеркало нечетного размера, на границах которого в наборе $\widetilde\gamma_3^n$ стоя́т равные значения, переводит набор $\widetilde\gamma_3^n$ в такой же набор, в который его переводит зеркало нечетного размера, получаемое из данного отбрасыванием концевых переменных по одной с каждой стороны, поэтому соответствующие этим двум зеркалам функции неисправности оказываются равными. Заметим: множества $\{\widetilde\gamma_2^n,\widetilde\gamma_3^n\}$, $A'_n$, $A''_n$, $B_n$ и $C_n$ попарно не пересекаются при $n\geqslant 8$. Таким образом, функции неисправности из множества $\mathscr B_n$ отличаются друг от друга только на наборах множества $A'_n\cup B_n$, функции неисправности из множества $\mathscr C_n$ отличаются друг от друга только на наборах множества $C_n$, функции неисправности из множества $\mathscr D_n$ отличаются друг от друга только на наборах множества $A''_n$. Поскольку на каждом наборе из множеств $A'_n\cup A''_n\cup B_n\cup C_n$ не более чем одна функция из каждого из множеств $\mathscr B_n$, $\mathscr C_n$, $\mathscr D_n$ обращается в единицу, получаем: длина любого диагностического теста для $\widehat h(\widetilde x^n)$ не меньше, чем $(|\mathscr B_n|-1)+(|\mathscr C_n|-1)+(|\mathscr D_n|-1)$. С учетом того, что получаем: Теорема доказана. Следствие 1. Пусть $n$ – целое положительное, $n\to\infty$, $n\geqslant 8$. Тогда имеет место следующее равенство функций по порядку роста: $L^{\mathrm{dn}}(P_{1}^{\mathrm{lm}},n)=\Theta(n^2)$. В теореме 3 доказываются оценки функции Шеннона длины диагностического теста относительно кратных локальных зеркальных неисправностей (на входах схем) любой кратности с произвольными размерами зеркал. Доказательство. Для произвольной булевой функции $f(\widetilde x^n)$ количество функций неисправности (включая $f$) относительно кратных локальных зеркальных неисправностей любой кратности с произвольными размерами зеркал по определению равно количеству способов выбрать такие целые неотрицательные числа $t$, $a_1$, $b_1,\dots$, $a_t$, $b_t$, что $1\leqslant a_1<b_1<\dotsb<a_t<b_t\leqslant n$, т.е. равно
$$
\begin{equation*}
\sum_{t=0}^{\lfloor n/2\rfloor}\binom{n}{2t}=2^{n-1},
\end{equation*}
\notag
$$
откуда по теореме 7 книги [1; с. 111–112] вытекает верхняя оценка функции Шеннона $L^{\mathrm{dn}}(P^{\mathrm{lm}},n)$.
Докажем нижнюю оценку функции Шеннона. Рассмотрим булеву функцию $h_2(\widetilde x^n)$, обращающуюся в единицу ровно на одном наборе – наборе $\widetilde\gamma_2^n=(0,1,0,1,0,1,0,1,\dots)$. Подсчитаем количество $\widehat F_n$ попарно различных наборов, в которые может переходить набор $\widetilde\gamma_2^n$ под действием произвольных зеркальных неисправностей, с учетом того, что а) любое одиночное зеркало нечетного размера переводит набор $\widetilde\gamma_2^n$ в себя (и потому можно далее исключить из рассмотрения зеркала нечетных размеров), б) последовательно примыкающие друг к другу без пропусков зеркала четных размеров переводят набор $\widetilde\gamma_2^n$ в такой же набор, в какой набор $\widetilde\gamma_2^n$ переводится “объединяющим” все эти зеркала зеркалом четного размера, в) а во всех остальных случаях возникают попарно различные наборы. Положив $\widehat F_0=1$ (пустое слово), отметим, что $\widehat F_1=1$ (сам набор $\widetilde\gamma_2^1=(0)$). При $n\geqslant 2$ имеет место равенство $\widehat F_n=\widehat F_{n-1}+\widehat F_{n-2}$, поскольку последний разряд набора $\widetilde\gamma_2^n$ либо относится к последнему зеркалу четной длины (в этом случае имеем $\widehat F_{n-2}$ порожденных наборов), либо не относится ни к какому зеркалу (в этом случае имеем $\widehat F_{n-1}$ порожденных наборов). Таким образом, $\widehat F_n$ есть $(n+1)$-е число Фибоначчи, откуда по формуле Бине получаем нижнюю оценку функции Шеннона вида $\widehat F_n-1$, поскольку из всех $\widehat F_n$ рассмотренных наборов в минимальный диагностический тест для функции $h_2(\widetilde x^n)$ обязаны входить все наборы, за исключением любого одного. Теорема доказана. 
Цитирование в формате AMSBIB
\RBibitem{AlbRom24} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|