Введение к работе
Актуальность темы. Теория надежности и контроля является ясным разделом теории управляющих систем (УС). В рамках теории дежности и контроля предполагается, что на УС, характеризую-уюся схемной частью и функционированием, воздействует источник исправностей, способный каким-то образом повреждать ее схемную ,сть (при этом функционирование УС может нарушаться). Анализ 3, находящихся под действием источников неисправностей, привел к >рмированию трех основных направлений теории надежности и конт-ля: синтеза надежных схем из ненадежных элементов, синтеза само-рректирующихся схем, теории контроля работы УС1. Значительное їсте в теории контроля УС занимают вопросы построения тестов для нтактных схем (КС). Актуальным направлением в исследованиях стов для КС является построение достаточно коротких тестов для нкретных классов КС, а также изучение особенностей этих тестов, ченно к этому направлению относится данная диссертация, в кото-й исследуются вопросы построения и анализа тестов для некоторых :ассов так называемых каскадных блочных КС (КБКС).
Цель работы. Основной целью данной работы является разра-тка методов построения близких к оптимальным единичных диагнос-іческих тестов для некоторых типов контактных схем и получения [жних оценок их длин.
Методы исследования. При получении основных результатов [ссертации использовались комбинаторные методы, методы теории роятностей и теории чисел, а также методы и подходы из различных зделов дискретной математики и математической кибернетики.
Научная новизна. Одним из самых распространенных классов 3, допускающих короткие тесты, является класс блочных КС. В .боте В. В. Глаголева2 было предложено достаточное условие лога-[фмичности длины диагностического теста размыкания для блочных ем, у которых число контактов в каждом блоке не превосходит неторой постоянной. Впоследствии С. М. Вартаняном3 был получен алогичный результат для тестов замыкания.
Среди блочных КС в данной диссертации выделяется класс т. н. скадных блочных контактных схем (КБКС), характеризуемых тем,
Чегис И. А., Яблонский С. В. Логические способы контроля работы -электрических
;м // Труды МИАН СССР. — Т. 51. — С. 270-360.
Глаголев В. В. Построение тестов для блочных схем. // ДАН СССР. — 1962. —
144. — N 6. — С. 1237-1240.
Вартанян С. М. Единичные диагностические тесты для последовательных блоч-
х схем. — Дисс. на соиск. уч. ст. к. ф.-м. н. — М., 1987. — 114 с.
что каждый блок схемы является типичным для применения метода каскадов синтеза КС. В диссертации предложен метод мультиразбие-ний построения единичных диагностических тестов для одного достаточно широкого класса КБКС — периодических КБКС из "перестановочных" 2<~полюсных блоков. Для всех исследованных в диссертации КБКС применяется единая методика построения тестов замыкания и тестов размыкания, связанная с диагностическими множествами цепей. Значительно развита в диссертации и техника получения нижних оценок длин единичных диагностических тестов для КС.
Одним из интенсивно изучаемых классов КБКС являются так называемые счетчики по модулю d, реализующие элементарные периодические симметрические функции. Тесты для этих схем строились в работах С. В. Яблонского и й. А. Чегис1, X. А. Мадатяна4, Р. Н. Тоноя-на5, С. М. Вартаняна3. При этом С. М. Вартаняну* удалось установить порядок длины минимального единичного диагностического теста для счетчиков по модулю d от п булевых переменных, где тг = 1,2,... ь d — d(n). Однако, полученные оценки не давали асимптотики длинь теста ни при фиксированном, ни при медленно растущем d = d(n). Е данной диссертации на основании метода мультиразбиений строятс* единичные диагностические тесты на размыкание и на замыкание дл* счетчиков по модулю d, являющиеся асимптотически оптимальным! ТпріГдостаточно медленно раы'ущем^^чтгоулучшает известные прежд< результаты.
Другим интересным классом КБКС являются двухполюсник "треугольные" КС, реализующие симметрические функции, частньа случаем которых являются "прямоугольные" КС, реализующие эле ментарные симметрические функции. Эти схемы могут быть получень из построенной по методу каскадов схемы с одним входом к п + 1 выходами, реализующей систему всех элементарных симметрически: функций тг переменных, путем отождествления некоторых выходов 1 применения операции "усечения". Единичные тесты для таких схе* изучались в работах С. В. Яблонского и И. А. Чегис1, И. Томес ку6, X. А. Мадатяна4, Р. Н. Тонояна7. При этом И. Томеску6 указа]
«Мадатян X. А. Единичный тест для симметрических функций // Disc.ret mathematics Banach center publications. — Vol. 7. — Warsaw: PWN-Folish Scientifi Publishers, 1982. — P. 65-71.
5Тояоян P. H. О единичных тестах дня контактных схем, реализующих линейны функции // Язе. АН Арм. ССР. — Т. VI. — N 1. — 1971. — С. 61-66.
Tomescu I. La coastructioa des tests minimaux pour les fonctions Booleennee symetriques // Cdcolo. — Vol. 6, N 1. — 1971. — P. 59 68.
гТоноян P. H. Некоторые тесты для контактных схем, реализующих .элементарны симметрический функции // Прикладная математика, межвузовски а сборник. -
чные значения длин минимальных единичных проверяющих тестов я "треугольных" схем, X. А. Мадатян4 фактически получил поря-к длины минимального диагностического теста для таких схем, а Н. Тоноян7 установил в ряде случаев асимптотику длины мини-льного диагностического теста для "прямоугольных" КС. В дис-этации получены достаточно полные асимптотические результаты говедении длины минимального диагностического теста для "пря-угольных" КС, реализующих элементарные симметрические функ-и. Эти результаты существенно дополняют оценки Р. Н. Тонояна7. следованы также минимальные диагностические тесты размыкания я "треугольных" КС, реализующих симметрические функции. При-цено условие, при выполнении которого асимптотика длины теста впадает с верхней оценкой из работы X. А. Мадатяна4. При невыпол-нии указанного условия для специальных последовательностей схем рхние оценки длины теста понижены. Исследовано, какой вид могут іеть асимптотики длины тестов. Для каждой возможной асимптоти-приведена последовательность схем, на которой такая асимптотика ализуется.
Метод мультиразбиений позволил автору диссертации построить тимальные по порядку единичные диагностические тесты для пе-:одических с ограниченной длиной периода КБКС, составленных из язньгх 2й-полгосных "сдвиговых" блоков.
В диссертации приведено также исследование некоторых мет-:ческих характеристик класса тупиковых проверяющих замыкания стов для схем счетчиков четности.
Теоретическая и практическая ценность. Диссертация но-т теоретический характер. Результаты диссертации могут быть пользованы для построения близких к оптимальным единичных диабетических тестов для некоторых классов КС и получения нижних ;енок длин таких тестов, для изучения свойств некоторых комбина-рных объектов, для тестирования больших и сверхбольших интег-льных схем.
Апробация работы. Результаты, представленные в работе, до-[адывались на XI и XII Международных конференциях "Проблеет теоретической кибернетики" (Ульяновск, июнь 1996 г., и Ниж-гй Новгород, май 1999 г., соответственно), II и III Международных нференциях "Дискретные модели в теории управляющих систем" Ірасновидово, июнь 199? и 1998 годов, соответственно), на II и III олодежных школах по дискретной математике и ее приложениям S3, вып. 2. — Ереван: Изд-во ЕГУ. — С 129-140.
(Нижний Новгород, ноябрь 1998 г., и Новосибирск, декабрь 1999 г.), на Шестых математических чтениях МГСУ (январь 1998 г.), на семинарах по математическим вопросам кибернетики под руководством члена-корреспондента РАН профессора С. В. Яблонского, на научных семинарах под руководством профессора А. А. Сапоженко.
Публикации. По теме диссертации имеется 7 публикаций, список которых приводится в конце автореферата.
Структура и объем работы. Диссертация состоит из четырех глав, разбитых на девять параграфов, двух приложений и списка литературы. Объем работы — 114 страниц. Список литературы содержит 55 наименований.