О ТЕСТАХ ОТНОСИТЕЛЬНО НЕКОТОРЫХ СУММИРУЮЩИХ ПО МОДУЛЮ ДВА СЛИПАНИЙ ВХОДОВ СХЕМ

​TEST SETS WITH RESPECT TO SOME MODULO-TWO SUMMING ADHESIONS OF PRIMARY INPUTS OF CIRCUITS

Stoletniy Alexander Vasilyevich

Student, Department of Mathematical Cybernetics, Kazakhstan Branch of the Moscow State University named after M.V. Lomonosov,

Kazakhstan, Astana

Romanov Dmitry Sergeevich

Scientific supervisor, Associate Professor, PhD, Moscow state University named after M. V. Lomonosov,

Russia, Moscow

АННОТАЦИЯ

В работе исследуются оценки длины минимального диагностического теста относительно локальных суммирующих по модулю два слипаний входов схем. Для класса неисправностей  при  доказаны нижняя и верхняя оценки:.

ABSTRACT

This paper studies bounds on the length of the minimum diagnostic test with respect to local modulo-two summing adhesions of circuit inputs. For the fault class  with , the following bounds are proved: .

Ключевые слова: диагностический тест; суммирующее по модулю два слипание; функция Шеннона; булева функция; входы схем.

Keywords: diagnostic test, modulo-two summing adhesion, Shannon function, boolean function, circuit inputs.

Данная работа относится к области контроля управляющих систем. Управляющая система представляется в виде схемы из функциональных элементов, реализующей булеву функцию . Предположим, что существует источник ошибок , воздействие которого может перевести схему в одно из конечного числа неисправных состояний, в каждом из которых реализуется некоторая функция неисправности . При неисправностях на входах схем схемная реализация булевой функции  не имеет значения.

Множество  входных наборов называется диагностическим тестом для схемы  относительно источника неисправностей , если для любых двух различных функций из рассматриваемого множества существует набор в , на котором значения этих функций различаются. Длина теста  определяется как количество входных наборов. Тест считается минимальным, если содержит наименьшее возможное количество наборов, необходимое для целей тестирования.

Функция Шеннона  представляет максимум длины минимального диагностического теста по всем булевым функциям  переменных. Эта функция исследовалась для различных типов неисправностей. Для константных неисправностей на входах схем.

В. Н. Носков [1, 2] установил, что функция Шеннона длины единичного диагностического теста равна . Для инверсных неисправностей Г. Р. Погосян [3] показал, что функция Шеннона длины проверяющего теста имеет вид . Для локальных -местных слипаний И. А. Кузнецов и Д. С. Романов [4] получили верхние оценки длины универсального проверяющего теста. Оценки для локальных константных неисправностей кратности  установлены в [5], а для зеркальных отражений — в [6].

В данной работе исследуется вопрос об оценках длины минимального диагностического теста относительно суммирующих по модулю два слипаний входов схем. В отличие от обычных слипаний, при которых несколько входов принимают одно и то же значение, суммирующее по модулю два слипание заменяет группу входов их суммой по модулю два.

Определение 1 (Модель неисправности). Пусть . Класс неисправностей  состоит из всех отображений  , таких, что для входного слова  

Зафиксируем  и . Определим  попарно различных входных слов , образующих характеристическое множество  специально сконструированной функции :  принимает значение  только на наборах из  и значение  на всех остальных. Строится таблица неисправностей — матрица, столбцы которой соответствуют функциям неисправности.

Анализ структуры таблицы неисправностей для чётных и нечётных позволяет установить количество классов эквивалентности  столбцов в зависимости от числа единичных наборов из , включённых в тест. При  число классов равно , при  для чётного  и  для нечётного.

Используя то, что общее количество наборов в минимальном тесте не менее  = , где  — мощность -го класса эквивалентности, доказывается следующий результат.

Теорема 1 (Нижняя оценка). Пусть , ,  ∈ . Тогда длина минимального диагностического теста относительно локальных -кратных суммирующих по модулю два слипаний входов схем удовлетворяет неравенству:  .

Теорема 2 (Верхняя оценка). Пусть . Тогда длина минимального диагностического теста относительно локальных -кратных суммирующих по модулю два слипаний входов схем удовлетворяет неравенству:

В работе получены оценки длины минимального диагностического теста относительно локальных k-кратных суммирующих по модулю два слипаний входов схем: .

Список литературы:

1. Носков В. Н. О сложности тестов, контролирующих работу входов логических схем // Методы дискретного анализа в синтезе управляющих систем. — Новосибирск: ИМ СО АН СССР. — 1975. — № 27. — С. 23–51.
2. Носков В. Н. О длинах минимальных единичных диагностических тестов, контролирующих работу входов логических схем // Методы дискретного анализа в синтезе управляющих систем. — Новосибирск: ИМ СО АН СССР. — 1978. — № 32. — С. 40–51.
3. Погосян Г. Р. О проверяющих тестах для логических схем. — М.: Изд-во ВЦ АН СССР, 1982.
4. Кузнецов И. А., Романов Д. С. О полных проверяющих тестах относительно локальных слипаний переменных в булевых функциях // Учёные записки Казанского университета. Серия Физико-математические науки. — 2009. — Т. 151, кн. 2. — С. 90–97.
5. Антюфеев Г. В., Романов Д. С. О тестах относительно локальных константных неисправностей фиксированной кратности на входах схем // Математические заметки. — 2023. — Т. 114, вып. 3. — С. 458–463.
6. Альбек М. К., Романов Д. С. О диагностических тестах относительно локальных зеркальных отражений на входах схем // Математические заметки. — 2024. — Т. 115, вып. 5. — С. 791–796.