Задача контроля сводит различение исправного и неисправных состояний схемы к выбору небольшого набора входных воздействий. Пусть состояния реализуют функции \(f_1,\ldots,f_s\), а допустимые входные наборы — \(\alpha_1,\ldots,\alpha_p\). Тогда строится таблица \(M\in B^{p,s}\) с элементами \(M_{ij}=f_j(\alpha_i)\)
Тест — набор строк, на которых различаются все пары столбцов, указанные целью контроля. Диагностический тест различает все состояния попарно, а проверяющий отличает исправное состояние от каждого неисправного. Для тупикового диагностического теста отделимой по столбцам таблицы выполняются границы
Что важно запомнить
- Строки таблицы контроля соответствуют входным наборам, столбцы — состояниям схемы.
- Функционально неотличимые состояния дают одинаковые столбцы и предварительно объединяются в один класс.
- Цель контроля задаёт пары состояний, которые требуется различить.
- Диагностический тест различает все пары состояний. Проверяющий отличает исправное состояние от каждого
- Тупиковый тест нельзя сократить удалением строки, а минимальный имеет наименьшую возможную длину.
Таблица контроля
Пусть возможные состояния модели реализуют булевы функции \(f_1,\ldots,f_s\). Для выбранных входных наборов \(A=\{\alpha_1,\ldots,\alpha_p\}\) строят матрицу \(M_{ij}=f_j(\alpha_i)\)
Если два столбца совпадают, соответствующие состояния функционально неразличимы на рассматриваемом множестве входов. В таблице контроля обычно оставляют по одному представителю каждого класса неотличимости.
Цель контроля и тест
Цель контроля задаётся множеством \(N\) неупорядоченных пар номеров столбцов. Множество строк \(T\subseteq\{1,\ldots,p\}\) называется тестом, если для каждой пары \((i,j)\in N\) найдётся строка \(t\in T\), где \(M_{ti}\ne M_{tj}\). Иными словами, выбранные воздействия должны давать разные выходы для каждой пары состояний, которую требуется
Если \(N\) содержит все пары столбцов, тест называется диагностическим. Если нужно отличить только исправный первый столбец от остальных, получают проверяющий тест.
Тупиковость и минимальность
Тест тупиковый, если удаление любой выбранной строки разрушает свойство теста. Минимальный тест имеет минимальное число строк среди всех тестов для данной цели. Для отделимой по столбцам таблицы любой тупиковый диагностический тест длины \(t\) удовлетворяет \(\lceil\log_2 s\rceil\le t\le s-1\)
Нижняя граница возникает потому, что \(t\) бинарных строк дают не более \(2^t\) различных кодов столбцов. Верхняя граница связана с тем, что каждая существенная строка тупикового теста должна дробить хотя бы один класс ещё не различённых столбцов.
Пример простыми словами
Если возможны четыре функционально различные состояния, один входной набор даёт только один бит и способен разделить их максимум на две группы. Два правильно выбранных входа уже могут дать четыре разных двухбитных кода. Поэтому информационная нижняя граница равна \(\lceil\log_2 4\rceil=2\).
Частые ошибки
- Путать строки и столбцы таблицы: строки — тестовые входы, столбцы — состояния.
- Называть проверяющий тест диагностическим. Проверяющий тест может не различать неисправные состояния между собой.
- Отождествлять тупиковость и минимальность. Тупиковый тест локально несократим, но может быть длиннее минимального.
