Построение тестов и оценка их параметров для некоторых классов контактных схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет им. М. В. Ломоносова Факультет вычислительной математики и кибернетики

На правах рукописи

РГБ ОД

РОМАНОВ Дмитрий Сергеевич 2 5 £ ,03

УДК 519.718.7

ЮСТРОЕНИЕ ТЕСТОВ И ОЦЕНКА ИХ ПАРАМЕТРОВ ДЛЯ НЕКОТОРЫХ КЛАССОВ КОНТАКТНЫХ СХЕМ

Специальность 01.01.09 — математическая кибернетика)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2000

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова.

Научные руководители:

член-корреспондент РАН

профессор | С. В. Яблонский], доктор физико-математических наук профессор С. А. Ложкин

Официальные оппоненты:

доктор физико-математических наук профессор Н. П. Редькин, кандидат физико-математических наук старший научный сотрудник X. А. Мадатян

Ведущая организация:

Институт прикладной математики при Нижегородском государственном университете

Защита состоится 19 мая 2000 г. в 11-00 часов в ауд. 685 2-го учебного корпуса МГУ на заседании Диссертационного Совета Д 053.05.38 при факультете ВМиК МГУ по адресу: 119899, Москва, Воробьевы горы, МГУ, факультет вычислительной математики и кибернетики.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан

апреля 2000 г.

Ученый секретарь Диссертационного Совета Д 053.05.38 профессор

Н. П. Трифонов

Г)

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория надежности и контроля является жным разделом теории управляющих систем (УС). В рамках теории .дежности и контроля предполагается, что на УС, характеризуются схемной частью и функционированием, воздействует источник исправностей, способный каким-то образом повреждать ее схемную ,сть (при этом функционирование УС может нарушаться). Анализ 1!, находящихся под действием источников неисправностей, привел к >рмированию трех основных направлений теории надежности и конт-ля: синтеза надежных схем из ненадежных элементов, синтеза само-рректирующихся схем, теории контроля работы УС1. Значительное ^сто в теории контроля УС занимают вопросы построения тестов для нтактных схем (КС). Актуальным направлением в исследованиях стов для КС является построение достаточно коротких тестов для нкретных классов КС, а также изучение особенностей этих тестов, ленно к этому направлению относится данная диссертация, в "кото-й исследуются вопросы построения и анализа тестов для некоторых :ассов так называемых каскадных блочных КС (КБКС).

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

Методы исследования. При получении основных результатов [ссертации использовались комбинаторные методы, методы теории роятностей и теории чисел, а также методы и подходы из различных зделов дискретной математики и математической кибернетики.

Научная новизна. Одним из самых распространенных классов 3, допускающих короткие тесты, является класс блочных КС. В .боте В. В. Глаголева2 было предложено достаточное условие лога-[фмичности длины диагностического теста размыкания для блочных ем, у которых число контактов в каждом блоке не превосходит неторой постоянной. Впоследствии С. М. Вартаняном3 был получен алогичный результат для тестов замыкания.

Среди блочных КС в данной диссертации выделяется класс т. н. скадных блочных контактных схем (КБКС), характеризуемых тем,

Чегис И. А., Яблонский С. В. Логические способы контроля работы -электрических ;м // Труды МИАН СССР. — Т. 51. — С. 270-360.

Глаголев В. В. Построение тестов для блочных схем. // ДАН СССР. —■ 1962. — 144. — N 6. — С. 1237-1240.

Вартанян С. М. Единичные диагностические тесты для последовательных блоч-х схем. — Дисс. на соиск. уч. ст. к. ф.-м. н. — М., 1987. — 114 с.

что каждый блок схемы является типичным для применения метода каскадов синтеза КС. В диссертации предложен метод мультиразбие-ний построения единичных диагностических тестов для одного достаточно широкого класса КБКС — периодических КБКС из "перестановочных" 2(£~полюсных блоков. Для всех исследованных в диссертации КБКС применяется единая методика построения тестов замыкания и тестов размыкания, связанная с диагностическими множествами цепей. Значительно развита в диссертации и техника получения нижних оценок длин единичных диагностических тестов для КС.

Одним из интенсивно изучаемых классов КБКС являются так называемые счетчики по модулю d, реализующие элементарные периодические симметрические функции. Тесты для этих схем строились в работах С. В. Яблонского и й. А. Чегис1, X. А. Мадатяна4, Р. Н. Тоноя-на5, С. М. Вартаняна3. При этом С. М. Вартаняну3 удалось установить порядок длины минимального единичного диагностического теста для счетчиков по модулю d от п булевых переменных, где тг = 1,2,... и d — d(n). Однако, полученные оценки не давали асимптотики длинь теста ни при фиксированном, ни при медленно растущем d = d(n). Е данной диссертации на основании метода мультиразбиений строят« единичные диагностические тесты на размыкание и на замыкание цш счетчиков по модулю d, являющиеся асимптотически оптимальныш при достаточно медленно растущем d, что улучшает известные прежд< результаты.

Другим интересным классом КБКС являются двухполюсны< "треугольные" КС, реализующие симметрические функции, частник случаем которых являются "прямоугольные" КС, реализующие эле ментарные симметрические функции. Эти схемы могут быть получень из построенной по методу каскадов схемы с одним входом и п -+- ] выходами, реализующей систему всех элементарных симметрически: функций тг переменных, путем отождествления некоторых выходов i применения операции "усечения". Единичные тесты для таких схе* изучались в работах С. В. Яблонского и И. А. Чегис1, И. Томес ку6, X. А. Мадатяна4, Р. Н. Тонояна7. При этом И. Томеску6 yKa3aj

«Мадатян X. А. Единичный тест для симметрических функций // Discret

mathem-atics Banach center publications. — Vol. 7. — Warsaw: PWN-Folish Scientifi

Publishers, 1982. — P. 65-71.

5Тоноян P. H. О единичных тестах дня контактных схем, реализующих линейны функции // Изв. АН Арм. ССР. — T. VI. — N 1. — 1971. — С. 61-66.

•Tomcscu I. La construction, des tests minimaux pour les fonctions Booléennes symétriques // Cdcolo. — Vol. 6, N 1. — 1971. — P. 59 68.

7Тоноян P. H. Некоторые тесты для контактных схем, реализующих элементарны симметрические функции // Прикладная математика, межвузовски а сборник. -

чные значения длин минимальных единичных проверяющих тестов я "треугольных" схем, X. А. Мадатян4 фактически получил nopain длины минимального диагностического теста для таких схем, а Н. Тоноян7 установил в ряде случаев асимптотику длины мини-льного диагностического теста для "прямоугольных" КС. В дис-этации получены достаточно полные асимптотические результаты товедении длины минимального диагностического теста для "пря-угольных" КС, реализующих элементарные симметрические функ-и. Эти результаты существенно дополняют опенки Р. Н. Тонояна7. следованы также минимальные диагностические тесты размыкания я "треугольных" КС, реализующих симметрические функции. При-цено условие, при выполнении которого асимптотика длины теста впадает с верхней оценкой из работы X. А. Мадатяна4. При невыпол-нии указанного условия для специальных последовательностей схем рхние оценки длины теста понижены. Исследовано, какой вид могут [еть асимптотики длины тестов. Для каждой возможной асимптоти-приведена последовательность схем, на которой такал асимптотика ализуется.

Метод мультиразбиений позволил автору диссертации построить тимальные по порядку единичные диагностические тесты для пе-:одических с ограниченной длиной периода КБКС, составленных из язных 2d-полюсных "сдвиговых" блоков.

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

Теоретическая и практическая ценность. Диссертация нот теоретический характер. Результаты диссертации могут быть пользованы для построения близких к оптимальным единичных диа-остических тестов для некоторых классов КС и получения нижних ;енок длин таких тестов, для изучения свойств некоторых комбина->рных объектов, для тестирования больших и сверхбольших интег-льных схем.

Апробация работы. Результаты, представленные в работе, до-[адывались на XI и XII Международных конференциях "Проблеет теоретической кибернетики" (Ульяновск, июнь 1996 г., и Ниж-гй Новгород, май 1999 г., соответственно), II и III Международных нференциях "Дискретные модели в теории управляющих систем" фасновидово, июнь 1997 и 1998 годов, соответственно), на II и III олодежных школах по дискретной математике и ее приложениям 83, вып. 2. — Ереван: Изд-во ЕГУ. — С. 129-140.

(Нижний Новгород, ноябрь 1998 г., и Новосибирск, декабрь 1999 г.), на Шестых математических чтениях МГСУ (январь 1998 г.), на семинарах по математическим вопросам кибернетики под руководством члена-корреспондента РАН профессора С. В. Яблонского, на научных семинарах под руководством профессора А. А. Сапоженко.

Публикации. По теме диссертации имеется 7 публикаций, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из четырех глав, разбитых на девять параграфов, двух приложений и списка литературы. Объем работы — 114 страниц. Список литературы содержит 55 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Функция /(^1,.,. ,хп) : {0,1}Л —> {0,1} называется булевой функцией. Булева функция, инвариантная относительно произвольных перестановок переменных, называется симметрической. Симметрическая функция /(х1,... ,хп), обращающаяся в единицу на таких и только таких наборах, число единиц в которых является одним из элементов некоторого множества 91 = {г1}..., га} (г* € {0,..., п}, 5 £ {1,..., п}), называется симметрической функцией с множеством рабочих чисел и обозначается ..., хп). Если |£И| = 1, симметрическая функция

называется элементарной. Если все числа из образуют арифметическую прогрессию, симметрическая функция называется элементарной периодической.

Базовым классом УС в диссертации являются контактные схемы (КС), традиционно вводимые как сети, ребрам которых (именуемым контактами) приписаны символы управляющих переменных (возможно, с отрицаниями), а среди вершин выделяются множества входных и выходных полюсов. При подаче значений (нулей гели единиц) нг управляющие переменные "проводят" те и только те контакты, для которых значения приписанных им выражений равны единице. Функция проводимости между некоторым входом и некоторым выходом будет равна единице на данном наборе значений переменных тогда ^ только тогда, когда из входа можно "достигнуть" выхода по проводя щим контактам. Функционирование КС понимается как упорядоченная

б

эвокупность функций проводимости между всевозможными парами ходов и выходов. В диссертации рассматриваются блочные КС, кото-ые строятся путем "последовательного присоединения" друг к другу азовых схем, называемых блоками (множество всех различных блоков бразует базис) и, возможно, отождествления некоторых входов схе-:ы, отождествления некоторых выходов схемы и применения операции усечения", заключающейся в удалении тех контактов схемы, которые е принадлежат ни одной проводящей цепи, ведущей от построенного хода к построенному выходу. Блочная КС называется периодической, ели последовательность типов ее блоков периодическая без предперио-а (этот термин также будет применяться к блочным КС, полученным ак "усечение" периодических). Блочная КС S называется каскадной лочной контактной схемой (КБКС), если каждый ее блок управляется дной переменной, разные блоки управляются разными переменными, сякий контакт блока соединяет какой-то вход блока с каким-то выхо-ом, и каждому входу блока инцидентны либо два противоположных онтактат либо один контакт. ,

"Перестановочным" 2с!-полюсным блоком, порожденным подста-овкой Р, называется КС II¿{Р) с d входами и d выходами, пронуме-юванными числами от 0 до d — 1, управляемая своей переменной ж и •акая, что всякий вход г соединен с выходом i размыкающим контактом временной х, т. е. контактом вида х, и всякий вход | г соединен с ыходом P(i) замыкающим контактом переменной х, т. е. контактом ида х. "Сдвиговым" блоком Щ называется "перестановочный" блок, горожденный циклической подстановкой, переводящей всякий элемент в г + е (mod d) (е £ {1,...,ci — 1}). Основным сверхпериодом Па ¿-полюсной КБКС из "перестановочных" блоков с периодом П<г назы-ается такая минимальная последовательность блоков, что произведе-. ¡ие всех соответствующих блокам подстановок равно тождественной юдстановке и общее число блоков кратно основному периоду схемы здесь и далее нижний индекс в обозначении периода указывает на [исло входов и выходов блоков, составляющих период).

В диссертации рассматриваются периодические КБКС из "пере-тановочных" блоков, периодические КБКС из "сдвиговых" блоков (в [астности, счетчики по модулю d), а также "треугольные" КБКС, >еализующие симметрические функции, и "прямоугольные" КБКС, >еализующие элементарные симметрические функции, построение ко-•орых связано с построенной по методу каскадов схемой, реализующей истему всех элементарных симметрических функций. .

КБКС Sn с п блоками называется r-достижимой, если из любого

входа г-го блока можно попасть по проводящей цепи в любой выход] (г 4- г — 1)-го блока, { = 1,..., п — г 4-1.

Пусть на контактную схему 3, управляемую множеством переменных {21,..., !„}, действует источник неисправности способны» каким-то определенным образом размыкать и замыкать контакты схемы. При размыкании соответствующий контакт всегда "не проводит" при замыкании — всегда "проводит". Пусть все схемы, порождаемые источником неисправностей по исходной схеме, известны. Тогда можнс разбить функционирования этих схем (включая и функционированш исходной схемы) на классы эквивалентности и сформулировать ж языке этих классов эквивалентности цель контроля. Наиболее распро страненными целями контроля являются обнаружение неисправностей (определение того, совпадает ли функционирование схемы с правиль ным) и диагностика неисправностей (определение класса эквивалент ности, к которому относится функционирование данной — возможно неисправной — схемы). Достижение цели контроля обычно осущест вляется путем подачи на входы схемы наборов входных значений I анализа значений, полученных на выходах схемы. Множество входныэ наборов, которое достигает цели контроля, называется тестом. Тесты контролирующие неисправности, называются проверяющими, тесты диагностирующие неисправности — диагностическими. Если источ ник неисправностей способен повредить в схеме не более одного эле мента, о соответствующих тестах, говорят, что они единичные. Числ< наборов теста называется длиной теста. Важными являются понятие минимального теста (теста минимальной длины) и тупикового (неиз быточного) теста. При указанных схеме 5 и источнике неисправност 1А длину минимального диагностического теста будем обозначать че рез 1(3, Ы). Длину минимального диагностического теста для схемь Б и источника неисправностей ¿/1,0, допускающего одно размыкание будем обозначать через 1р(5), а длину минимального диагностическое теста для схемы Б и источника неисправностей ¿4,1) допускающее одно замыкание, будем обозначать через ¡'(в). Под диагностическим! (проверяющими) тестами для множества контактов К схемы 5 бу дем понимать тесты, диагностирующие (проверяющие) неисправност] контактов множества К при заданном источнике неисправностей. Дли ну минимального диагностического теста для множества контактов Ь схемы 5 и источника неисправностей Ы обозначим через 1(3,И, К).

Пусть на схему 5 действует источник неисправности, являющий ся или источником ^1,0, или источником ¿/од. Если при неисправност некоторого контакта схемы 5 функционирование схемы на наборе (

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

Пусть все контакты периодической т-блочной 2^-полюсной КБКС из "перестановочных" блоков с основным периодом Щ и основным сверхлериодом Щ покрыты к пронумерованными проводящими цепями длины т (считается, что контакты в каждом блоке упорядочены определенным образом и что т кратно длине основного сверхпериода). Тогда по признаку прохождения цепей через контакты фиксированного блока номера цепей образуют разбиение, а последовательность таких разбиений для всех тп блоков образует связанный со схемой объект, называемый (П^, к, гл)-мультиразбиением. Если дано (Щ, к, т)-мультиразбиение, то по нему исходные цепи восстанавливаются однозначно. Если начальная и конечная вершины каждой цепи имеют одинаковые номера, то (П^, Ж,т)-мультиразбиение называется циклическим. Назовем (П^, к, то)-мультиразбиение различимым, если все компоненты его разбиений попарно различны, и слаборазличимым, если при добавлении й цепей размыкающих контактов и Л цепей замыкающих контактов соответствующее мультиразбиение окажется различимым.

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

Теорема 4.1. Пусть 5 — двухполюсная КС, на которую воздействует источник неисправности Ы, где Ы = 1Л\$ или и = ¿/од-Пусть, далее, в схеме Я существует N непересекающихся групп К\, К..., .., Кл контактов, причем в группе К{ число контактов не менее ¿¿, любой входной набор проверяет (относительно и) в этой группе не более А* контактов (г £ {1,..., Ы}, 6{ 6 М, А, 6 и функции неисправностей различных контактов из всех указанных групп различны и отличны от функции проводимости исправной схемы. Пусть, далее, К = К{.

1. Тогда

1{8М,К)> (21>)/

2. Если же для всех i,i £ {1,... Aj = 1, S, 6 ^ 3, то

1

1{S,U,K) ^

1 X * п /F^T'C0^"1'5) bg25 - Ylog2(5- 1)

В пятом параграфе диссертации предлагается метод построения нетривиальных единичных диагностических тестов для класса периодических КБКС из "перестановочных" блоков. Этот метод опирается на рекурсивное построение мупьтиразбиений некоторых типов. Основными утверждениями параграфа являются теоремы 5.1 и 5.2.

Теорема 5.1. Если существует циклическое слаборазличимое (П^, к,т)-мулътирв,збиение, то для двухполюсной п-блочной г-достижимой КБКС из "перестановочных" блоков 5П(П^) с периодом П<г длины т, и сверхпериодом Щ длины Т при п ^ тах{т,3г} имеют место следующие оценки:

P(Sn(nd)) < + log2 n + k + 2d] log2 r[+12d,

I'&W) $ (d - 1) • ((log;(r]i[_r+l)) bg2n 4- k + 2d) log2 r[+12d) .

Теорема 5.2. Если существует циклическое слаборазличимое (П^,fc,тп)-мулътиразбиение, то для двухполюсной п-блочной r-достижимой КБКС из "сдвиговых" блоков с периодом lid

длины т и сверхпериодом Щ длины Т при п ^ тах{т,3г} имеют место следующие оценки:'

Jp(S»(Hi)) < log2 п + k + 2d] log2 г[+Ш,

х ((iog,(r]?[-r+i)) " + * + 1о82 •

В третьей главе, состоящей из параграфов 6 и 7 диссертации, строится близкие к оптимальным единичные диагностические тесты для некоторых типов КБКС. При этом в шестом параграфе диссертации существенно используется метод мультиразбиений.

Теоремы 6.2 и 6.3 представляют собой результат применения метода мультиразбиений к классу периодических КБКС из "сдвиговых" связных блоков.

Теорема 6.2. Пусть — двухполюсная периодическая

КБКС из "сдвиговых" связных блоков с периодом П^ длины т, и п > 3dr. Тогда

^ (bj^ry) log2 гг + к + 2d] log2(r(d - 1))[+Ш,

min {] Iii [ f d _ !} . iog2 n + k + 2d] log2(r(d - 1))[+ш) ■

Теорема 6.3. Пусть Sn(R<i) — двухполюсная периодическая ЗКС из "сдвиговых" связных блоков с периодом Пдлина которого не превосходит некоторой фиксированной постоянной. Тогда при -> оо и d таком, что log2 d = О (\/log2 п), имеют место соотносил:

Заметим, что теорема 6.3 дает оптимальную по порядку оценку ины минимального единичного диагностического теста для рассмат-ваемых схем.

Следующие три теоремы представляют собой результат приме-яия метода мультиразбиений к схемам Sn(Hj) счетчиков по молю d. Укажем, что множители v'd при двоичных логарифмах п в авных членах нижних оценок длин соответствующих тестов для :м счетчиков по модулю d (оценки получены С. М. Вартаняном3) еют вид v'd = (log2(2<i) — 2|=ilog2(2i - 1)) \ при этом для схем этчиков четности v'2 — 1,23262 ..., для схем счетчиков по модулю 3 = 1,538408....

Теорема 6.4.

max{l»(Sn(Hl)),l>{Sn{Hl))} < Vzlog2 n + 44 (n > 16), max{l'(Sa{Hb),l'(Sn(H}))} < t;3!og2n + 64 (n > 24),

2 «2 = ¡3¿MS = 3844441 • • ■■' "3 = = 1,7858230....

Теорема 6.5. При n ^ 3d — 3 для длин тестов схемы §п(Щ) еют место следующие оценки:

тах{Р(5„(Я])) Л5„(#]))} < j^^y ' bg2 n + к + 14d.

Теорема 6.6. Пусть п —> оо, d -> оо, d ^ п^, где г) = o(log2n), 7(л) -> оо, тогда

P(Sn(tf])) ~ 2d\ogdп, nSn{H\)) ~ 2dlog(in.

Отметим, что приведенные в теореме 6.6 результаты являюта первыми асимптотически точными оценками длин рассматриваемы: тестов.

Результаты параграфа 7 диссертации касаются длин минималь ных единичных диагностических тестов для "прямоугольных" схе л реализующих элементарные симметрические функции п перемен ных с рабочим числом г, и "треугольных" схем S^, реализующи: симметрические функции от п переменных с множеством рабочи: чисел iH. Все нижние оценки этого параграфа являются следствиям! теоремы 4.1.

Теорема 7.1. Пусть t = min{r,n — г}. Если п оо, 1 ^ £ ^ п/2 t — фиксировано, то имеют место асимптотики:

* »> t+1' ^ *> i + 2

Если же п —> оо, 1 <С £ iC п/2, t —>■ оо, mo имеют место асимптотики l'(ITn) ~ 2га, ~ 2п.

Отметим, что ранее асимптотика при п —> оо длин минимальны: единичных тестов замыкания и размыкания для схем была извести, для случаев n/2 — t = о(п) и t оо, t = о(п) (Р. Н. Тоноян7).

Теорема 7.2. Если {Е^} — такая последовательность схе. симметрических функций что у каждой функции S^ можн

указать два рабочих числа т'п и так, что г'п —» оо, r'l —> ос г' — о(п), п — г" = o(ra) при п —» оо; то

Если же {Е^} — такая последовательность схем симметрически функций {>5^}, что у функций S^ нельзя выделить подпоследователь ностъ рабочих чисел {г^} так, что или г'п —> оо, г' — о(п) при п ос или г'п —> оо, п — г' — о(п) при п —> оо, то существует константа i с < 4, такая, что

1'(Б*)<сп(1 + о(1)).

Теорема 7.3. Для любой константы с из множеств М — {jVf | i 6 N} U [2; 4] существует такая последовательное схем } симметрических функций что

ПS?) ~ СП.

Если с $ М, то не существует такой последовательности схе, симметрических функций что ~ сп.

В четвертой главе диссертации, состоящей из параграфов 8 и 9, :ледуются метрические характеристики множества тупиковых про-эяющих замыкания тестов для схем счетчиков четности. В частнос-, доказываются следующие теоремы.

Теорема 9.2. Для числа Тп тупиковых проверяющих замыкания ]„ тестов при п -4 оо имеют место следующие асимптотические едставления:

если п —оо по четным значениям, то

Тп = -Jp=2(n/2+1)2(l + о(1)),

V ¿7ГП

если п —ь оо по нечетным значениям, то

Гя = -^=2^2+1^4(1 + 0( 1)), \j2im

оо оо

г Nü = 1 + 2 ¿ 2"> , JVi = 2 £

j=l j—O

Теорема 9.3. Предельные распределения случайной величины впой длине случайного тупикового проверяющего теста размыкая для схемы счетчика четности п переменных, при п —> оо имеют едующий вид.

Если п —> оо по четным значениям, то для любого фиксирован-го j, j = 0,1,...

lim P{¿„ = n/2 - j} = lim P{£„ = n/2 =

n—>oo

Если n —> оо по нечетным значениям, то для любого фиксиро-нного j, j = 0,1,...

l™ Р{£„ = (п - 1)/2 - j} = lim P{£„ = (п - 1)/2 + ;} -

->00 п—>оо 1

В диссертации разработаны достаточно общие методы построе-я единичных диагностических тестов размыкания и единичных диа-эстических тестов замыкания для КБКС, а также методы получения жних оценок длины таких тестов. Эти методы позволили существо улучшить известные ранее оценки и построить, в частности, гимальные по порядку тесты для периодических КБКС из связных двиговых" блоков с ограниченной длиной периода, асимптотически гимальные при медленно растущем d тесты для счетчиков по молю d, асимптотически оптимальные тесты для "прямоугольных" ЖС. Исследованы также некоторые метрические характеристики асса тупиковых проверяющих замыкания тестов для счетчиков чет-сти.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Романов Д. С. О верхних оценках длины минимальных диагности ческих тестов на размыкания в блочных контактных схемах счет чиков четности // Труды III Межд. коиф. "Дискретные модели в теории управляющих систем". Красновидово-98 (22-27 июш 1998 г.). — М.: Диалог МГУ, 1998 г. — С. 97-101.

2. Романов Д. С. О числе тупиковых проверяющих замыкания теста для блочных контактных схем счетчиков четности // Дискретнаj математика. — Т. 9. — Вып. 4. — 1997. — С- 32-49.

3. Romanov D. S. On the number of deadlock tests for closings of blocl circuits of parity counters // Discrete mathematics and applications — Vol. 7. — N 6. — 1997. — P. 573-591.

4. Романов Д. С. Обобщение теоремы С. М. Вартаняна о нижни: оценках длин единичных диагностических тестов для контактны: схем // Мат. методы и приложения. Труды шестых мат. чтени МГСУ (23-30 января 1998 г.). — М.: Изд-во МГСУ "Союз". -1999. — С. 47-51.

5. Романов Д. С. Об асимптотически минимальных тестах, диагнос тируюгцихгединичное замыканиелразмыкание контакта в блочны контактных схемах счетчиков по модулю d // Труды II Междунц конференции "Дискретные модели в теории управляющих систем (23-28 июня 1997 г.). — М.: Диалог МГУ, 1997. — С. 47-48.

6. Романов Д. С. О числе тупиковых тестов, проверяющих замыкани контактов в схемах, реализующих линейные булевы функции / Дискретный анализ и исследование операций. — Июль-сентябр 1995 г. — Т. 2. — N 3. — С. 78-79.

7. Романов Д. С. Об оценках длин минимальных единичных ди< гностических тестов для контактных схем, реализующих элем« тарные симметрические функции // Проблемы теоретической кг

: бернетики. Тезисы докладов XII Междун. конф. (Ниж. Новгоро< 17-22 мая 1999 г.). — Часть II. — М.: Изд-во мех.-мат. ф-та МГЗ 1999. — С. 200.

Глава 1. Введение

§ 1. Общая характеристика работы

§ 2. Основные определения и обозначения.

§ 3. Формулировки основных результатов диссертации.

Глава 2. Метод мультиразбиений и оценки длины минимальных единичных диагностических тестов для периодических КБКС.

§ 4. Диагностические множества цепей и мультиразбиения, их связь с тестами. Нижние оценки длин тестов.

§ 5. Рекурсивное построение слаборазличимых мультиразбиений и верхние оценки длины единичных диагностических тестов для одного класса периодических КБКС.

Глава 3. Построение близких к оптимальным единичных диагностических тестов для некоторых классов КБКС.

§ 6. Тесты для одного класса периодических КБКС из "сдвиговых" блоков и для счетчиков по модулю (1.

§ 7. Построение асимптотически минимальных единичных тестов для "прямоугольных" схем и построение тестов размыкания для треугольных" схем.'.

Глава 4. О метрических свойствах одного класса тестов для схем счетчиков четности.

§ 8. О числе тупиковых проверяющих замыкания тестов заданной длины.

§ 9. Предельное распределение длины тестов.

Теория надежности и контроля управляющих систем является важным разделом теории управляющих систем (УС). В рамках теории надежности и контроля предполагается, что на УС, характеризующуюся схемной частью и функционированием [15], воздействует источник неисправностей, способный каким-то образом повреждать ее схемную часть (при этом функционирование УС может нарушаться). Анализ УС, находящихся под действием источников неисправностей, привел к формированию трех основных направлений теории надежности и контроля: синтеза надежных схем из ненадежных элементов, синтеза самокорректирующихся схем, теории контроля работы УС.

Математической базой теории контроля работы УС является тестовый подход, сформировавшийся в середине 50-х годов в работах С. В. Яблонского и И. А. Чегис [46] и [42]. Смысл тестового подхода состоит в следующем. Пусть все схемы, порождаемые источником неисправностей по исходной схеме, известны. Тогда можно разбить функционирования этих схем (включая и функционирование исходной схемы) на классы эквивалентности и сформулировать на языке этих классов эквивалентности цель контроля. Наиболее распространенными целями контроля являются обнаружение неисправностей (определение того, совпадает ли функционирование схемы с правильным) и диагностика неисправностей (определение класса эквивалентности, к которому относится функционирование данной — возможно, неисправной — схемы). Достижение цели контроля обычно осуществляется путем подачи на входы схемы наборов входных значений и анализа значений, полученных на выходах схемы (реже в схемах допускаются внутренние контрольные точки). Множество входных наборов, которое достигает цели контроля, называется тестом. Тесты, контролирующие неисправности, называются проверяющими, тесты, диагностирующие неисправности — диагностическими. Если источник неисправностей способен повредить в схеме не более одного элемента, о соответствующих тестах говорят, что они единичные. Если же источник неисправностей способен повреждать в схеме любые элементы, тесты для него называются полными. По тому, зависит ли вид подаваемых на входы схемы наборов от полученных на предыдущих шагах выходных значений, или нет, тесты делятся на условные и безусловные. Число наборов теста называется длиной теста. Важными являются понятия минимального теста (теста минимальной длины) и тупикового (неизбыточного) теста.

Построение и анализ тупиковых и минимальных тестов представляет значительный интерес. С. В. Яблонским и И. А. Чегис в [46], [42] был предложен первый алгоритм построения всех тупиковых тестов по так называемой таблице неисправностей (таблице, в которой заданы столбцами своих значений все попарно неэквивалентные функционирования исходной и неисправных схем), однако высокая трудоемкость этого алгоритма не позволила использовать его для исследования тупиковых и минимальных тестов уже при сравнительно небольших размерах таблиц неисправностей. Этот факт стимулировал создание конкретных алгоритмов построения тестов, получение оценок длин тестов и исследование метрических характеристик множеств тестов для различных классов управляющих систем. В настоящее время теория контроля представляет собой развитую научную область, объединяющую работы многих российских и зарубежных авторов, среди которых

A. Е. Андреев, А. Д. Коршунов, X. А. Мадатян, М. Ю. Мошков,

B. Н. Носков, Г. Р. Погосян, Н. П. Редькин, В. А. Слепян, Н. А. Соловьев, В. И. Шевченко, С. В. Яблонский, D. В. Armstrong, В. D. Eldred, Е. F. Moore, J. P. Roth и другие. Из литературы по теории контроля хотелось бы упомянуть монографии Н. А. Соловьева [38], Н. П. Редьки-на [24], М. Ю. Мошкова [19], П. П. Пархоменко и Е. С. Согомоняна [23], а также обзор С. В. Яблонского [45].

В настоящей диссертации исследуются вопросы построения и изучения тестов для некоторых классов контактных схем (КС). Типичными для КС неисправностями являются размыкание и замыкание контакта. Отметим два направления в исследованиях тестов для КС:

1) изучение функций Шеннона, характеризующих длину минимального теста для наиболее легкотестируемой контактной схемы, реализующей "самую труднотестируемуто" функцию п переменных, при различных источниках неисправностей,

2) изучение тестов для конкретных классов КС.

В первом направлении были получены, например, следующие интересные результаты. Установлено точное значение функции Шеннона для случая полного диагностического теста [18] для функций алгебры логики от п булевых переменных — ее величина оказалась равной 2П, то есть минимальный тест должен в общем случае содержать все наборы. В [25] доказано, что полный проверяющий тест не обязан содержать все наборы: и что соответствующая функция Шеннона не превосходит Щ2п. Глубокие результаты были получены в [26] и для полных проверяющих тестов замыкания и размыкания.

При изучении поведения функций Шеннона оказалось, что все верхние оценки, не относящиеся к тестам для входов схем, носят экспоненциальный характер [42], [16], [25]. В связи с этим представляет особый интерес второе направление в теории тестов для КС, связанное с выделением среди широких классов схем подклассов легкотестиру-емых схем, то есть схем, допускающих короткие тесты, и изучением метрических характеристик их тестов. Именно к этому направлению и относится данная диссертация.

Интересным примером класса схем, допускающих короткие тесты некоторых типов, может служить класс т. н. бесповторных двухполюсных КС, то есть таких КС, в которых встречается ровно по одному контакту каждой переменной. Тесты для таких схем изучались в работах В. В. Ваксова [3], И. В. Когана [9] и X. А. Мадатяна [18]. Оказалось, что значения функций Шеннона длин полного проверяющего [9] и единичного диагностического [3] тестов для класса булевых функций п переменных, реализуемых бесповторными КС, равны п + 1, тогда как функция Шеннона длины полного диагностического теста [18] ведет себя экспоненциально по п.

Одним из самых распространенных классов легкотестируемых КС является класс блочных КС. Схемы этого класса синтезируются путем "последовательного" присоединения друг к другу базовых схем, называемых блоками, и, возможно, отождествления некоторых входов схемы, отождествления некоторых выходов схемы и применения операции "усечения", заключающейся в удалении тех контактов схемы, которые не принадлежат ни одной проводящей цепи, ведущей от построенного входа к построенному выходу. В работе В. В. Глаголева [7] было предложено достаточное условие логарифмичности длины диагностического теста размыкания для блочных схем, у которых число контактов в каждом блоке не превосходит некоторой постоянной. Впоследствии С. М. Вартаняном [4] был получен аналогичный результат для тестов замыкания.

Одним из интенсивно изучаемых классов блочных контактных схем являются так называемые счетчики по модулю с/, реализующие элементарные периодические симметрические функции ([54], [49], [14], [8], [5], [20], [12]). Тесты для этих схем строились в работах [42], [17], [39], [4]. При этом С. М. Вартаняну [4] удалось установить порядок длины минимального единичного диагностического теста для счетчиков по модулю с1 от п булевых переменных, где п = 1,2,. и с? = с?(п). Однако, полученные оценки не давали асимптотики длины теста ни при фиксированном, ни при при медленно растущем с1 = <1{п). В данной диссертации строятся единичные диагностические тесты на размыкание и на замыкание для счетчиков по модулю с?, являющиеся асимптотически оптимальными при достаточно медленно растущем (¿, что улучшает результаты как работы [17], так и [4].

Другим классом легкотестируемых блочных схем являются двухполюсные "треугольные" КС, реализующие симметрические функции, частным случаем которых являются "прямоугольные" КС, реализующие элементарные симметрические функции. Эти схемы могут быть получены из построенной по методу каскадов (см., например, [13]) схемы с одним входом ип+1 выходами, реализующей систему всех элементарных симметрических функций п переменных, путем отождествления некоторых выходов и применения операции "усечения". Единичные тесты для таких схем изучались в [42], [55], [17], [40]. При этом И. Томеску [55] указал точные значения длин минимальных единичных проверяющих тестов для "треугольных" схем, X. А. Мадатян фактически получил порядок длины минимального диагностического теста для таких схем, а Р. Н. Тоноян [40] установил в ряде случаев асимптотику длины минимального диагностического теста для "прямоугольных" КС. В диссертации получены достаточно полные асимптотические результаты о поведении длины минимального диагностического теста для "прямоугольных" КС, реализующих элементарные симметрические функции. Эти результаты существенно дополняют оценки Р. И. Тонояна [40]. Исследованы также минимальные диагностические тесты размыкания для "треугольных" КС, реализующих симметрические функции. Приведено условие, при выполнении которого асимптотика длины теста совпадает с верхней оценкой из [17]. При невыполнении указанного условия для специальных последовательностей схем верхние оценки длины теста понижены. Исследовано, какой вид могут иметь асимптотики длины тестов. Для каждой возможной асимптотики приведена последовательность схем, на которой такая асимптотика реализуется.

И счетчики по модулю и "треугольные" КС, и "прямоугольные" КС относятся к классу т. н. каскадных блочных контактных схем (КБКС), характеризуемых тем, что каждый блок схемы является типичным для применения метода каскадов синтеза КС. В диссертации предложен метод мультиразбиений построения единичных диагностических тестов для одного достаточно широкого класса КБКС — периодических КБКС из "перестановочных" блоков. Для всех исследованных в диссертации КБКС применяется единая методика построения тестов замыкания и тестов размыкания, связанная с диагностическими множествами цепей. Значительно развита в диссертации и техника получения нижних оценок длин единичных диагностических тестов для КС.

Важное место в общей теории тестов занимает изучение тестов для всех или почти всех таблиц, а также для некоторых специальных классов таблиц (см., например, [1], [2], [21], [22], [35]—[37]). Вместе с тем взгляд на множество тестов для "узкого" класса УС как на метрическую структуру также представляет определенный интерес. В этом направлении в диссертации получены некоторые асимптотические представления числа тупиковых тестов заданной длины, асимптотика числа тестов, предельное распределение длины случайного тупикового теста для случая проверки кратных замыканий в блочных КС счетчиков четности (счетчиков по модулю 2).

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

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

Во второй главе, состоящей из двух параграфов, указываются некоторые базовые свойства используемых в диссертации конструкций, доказывается общая теорема о нижних оценках длин единичных диагностических тестов для КС (теорема 4.1), существенно обобщающая результаты С. М. Вартаняна [4], предлагается использующий комбинаторные конфигурации конечных размеров (называемые муль-тиразбиениями) метод построения единичных диагностических тестов для одного класса периодических КБКС.

В третьей главе, состоящей из двух параграфов, строятся близкие к оптимальным единичные диагностические тесты для периодических с ограниченной длиной периода блочных КС из связных "сдвиговых" блоков (в частности, для схем счетчиков по модулю (I), "прямоугольных" схем, реализующих элементарные симметрические функции. Также в главе приводятся некоторые утверждения о диагностических тестах размыкания для "треугольных" схем, реализующих симметрические функции.

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

Полученные в диссертации результаты являются новыми. Материалы диссертации опубликованы в работах [27]—[32] и [52].

1. Андреев А. Е. О тупиковых и минимальных тестах // ДАН СССР.1981. — Т. 256, N 1. — С. 521-524.

2. Андреев А. Е. Об асимптотическом поведении числа тупиковых тестов и минимальной длины теста для почти всех таблиц // Проблемы кибернетики. — Вып. 41. — М.: Наука, 1987. — С. 117-141.

3. Ваксов В. В. О тестах для бесповторных контактных схем. —Автоматика и телемеханика. — 1965. — Т. 26, N 3. — С. 521-524.

4. Вартанян С. М. Единичные диагностические тесты для последовательных блочных схем. — Дисс. на соиск. уч. ст. к.ф.-м.н. — М., 1987. — 114 с.

5. Вартанян С. М. Новое доказательство минимальности контактной схемы, реализующей линейную функцию // Методы дискретного анализа в изучении реализаций логических функций. — Вып. 41. — Новосибирск: Изд-во ИМ СО АН СССР, 1984 г. — С. 27-34.

6. Виноградов И. М. Основы теории чисел. — M.-JL: Гостехиздат, 1949. — 180 с.

7. Глаголев В. В. Построение тестов для блочных схем. // ДАН СССР. — 1962. — Т. 144. — N 6. — С. 1237-1240.

8. Гринчук М. И. О сложности реализации симметрических булевых функций контактными схемами // Матем. вопросы кибернетики.Вып. 3. — М.: Наука, 1991. — С. 77-114.

9. Коган И. В. О тестах для бесповторных контактных схем // Проб-лемм кибернетмки. — Вып. 12. — М.: Наука, 1964. — С. 39-44.

10. Коршунов А. Д. О длине минимальных тестов для прямоугольных таблиц. I, II // Кибернетика. — 1970, N 6; 1971, N 1.

11. Кострыкин А. И. Логический контроль релейно-контактных схем.М.: Связь, 1970.

12. Ложкин С. А. Об одном методе получения нижних оценок сложности контактных схем и о некоторых минимальных схемах для линейных функций // Сб. трудов семинара по дискретной математике и ее приложениям. — М.: Изд-во мех.-мат. ф-та МГУ, 1997.С. 113-115.

13. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — М.: Изд-во МГУ, 1984. — 137 с.

14. Лупанов О. Б. К вопросу о реализации симметрических функций алгебры логики контактными схемами // Проблемы кибернетики.Вып. 15. — М.: Наука, 1965. — С. 85-99.

15. Ляпунов А. А., Яблонский С. В. Теоретические проблемы кибернетики // Проблемы кибернетики. — Вып. 9. — М.: Физматгиз, 1963.С. 5-22.

16. Мадатян X. А. Построение единичных тестов для контактных схем // Сборник работ по математической кибернетике. — М.: Изд-во ВЦ АН СССР, 1981. — С. 77-86.

17. Мадатян X. А. Единичный тест для симметрических функций // Discrete mathematics Banach center publications. — Vol. 7. — Warsaw: PWN-Polish Scientific Publishers, 1982. — P. 65-71.

18. Мадатян X. А. Полный тест для бесповторных контактных схем // Проблемы кибернетики. — Вып. 23. — М.: Наука, 1970. — С. 103-118.

19. Мошков М. Ю. Деревья решений. Теория и приложения. — Нижний Новгород: Изд-во Нижегородского ун-та, 1994. — 176 с.

20. Нигматуллин Р. Г. Сложность булевых функций. — М.: Наука, 1991. — 240 с.

21. Носков В. Н. О тупиковых и минимальных тестах для одного класса таблиц // Дискретный анализ. — Вып. 12. — Новосибирск: ИМ СО АН СССР, 1968. — С. 27-49.

22. Носков В. Н., Слепян В. А. О числе тупиковых тестов для некоторого класса таблиц // Кибернетика. — 1972. — N 1. — С. 60-65.

23. Пархоменко П. П., Согомонян Е. С. Основы технической диагностики. — М.: Энергоиздат, 1981. —■ 320 с.

24. Редькин Н. П. Надежность и диагностика схем. — М.: Изд-во МГУ, 1992. — 192 с.

25. Редькин Н. П. О полных проверяющих тестах для контактных схем // Методы дискретного анализа в исследовании экстремальных структур. — Вып. 39. — Новосибирск: Изд-во ИМ СО АН СССР, 1983. — С. 80-87.in

26. Редькин Н.П. О проверяющих тестах замыкания и размыкания // Методы дискретного анализа в оптимизации управляющих систем. — Вып. 40. — Новосибирск: Изд-во ИМ СО АН СССР, 1983.С. 87-99.

27. Романов Д. С. О числе тупиковых проверяющих замыкания тестов для блочных контактных схем счетчиков четности // Дискретная математика. — Т. 9. — Вып. 4. — 1997. — С. 32-49.

28. Романов Д. С. Обобщение теоремы С. М. Вартаняна о нижних оценках длин единичных диагностических тестов для контактных схем // Мат. методы и приложения. Труды шестых мат. чтений МГСУ (23-30 января 1998 г.). — М.: Изд-во МГСУ "Союз". — 1999. — С. 47-51.

29. Романов Д. С. О числе тупиковых тестов, проверяющих замыкания контактов в схемах, реализующих линейные булевы функции // Дискретный анализ и исследование операций. — Июль-сентябрь 1995 г. — Т. 2. — N 3. — С. 78-79.

30. Сачков В. Н. Введение в комбинаторные методы дискретной математики. — М.: Наука, 1982. — 384 с.

31. Сачков В. Н. Вероятностные методы в комбинаторном анализе.М.: Наука, 1978. — 288 с.

32. Сачков В. Н. Случайные минимальные покрытия // Дискретная математика. — 1992. — Т. 4. — N 5. — С. 65-74.

33. Слепян В. А. Вероятностные характеристики распределения тупиковых тестов // Дискретный анализ. — Вып. 12. — Новосибирск: ИМ СО АН СССР, 1968. — С. 50-74.

34. Слепян В. А. Параметры распределения тупиковых тестов и информационные веса столбцов в бинарных таблицах // Дискретный анализ. — Вып. 14. — Новосибирск: ИМ СО АН СССР, 1969. — С. 28-43.

35. Соловьев Н. А. Тесты (теория, построение, применение). — Новосибирск: Наука (Сибирское отделение), 1978. — 192 с.

36. Тоноян Р. Н. О единичных тестах для контактных схем, реализующих линейные функции // Изв. АН Арм. ССР. — Т. VI. — N 1.1971. — С. 61-66.

37. Тоноян Р. Н. Некоторые тесты для контактных схем, реализующих элементарные симметрические функции // Прикладная математика, межвузовский сборник. — 1983, вып. 2. — Ереван: йзд-во ЕГУ.С. 129-140.

38. Харари Ф. Теория графов. — М.: Мир, 1973. — 304 с.

39. Чегис И. А., Яблонский С. В. Логические способы контроля работы электрических схем // Труды МИАН СССР. — Т. 51. — С. 270-360.

40. Шевченко В. И. Исследование сложности условных тестов для диагностики неисправностей схем из функциональных элементов.Автореферат дисс. на соиск. уч. ст. к. ф.-м. н. — Нижний Новгород: Изд-во Нижегородского ун-та, 1995. — 16 с.

41. Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.

42. Яблонский С. В. Надежность и контроль управляющих систем // Математические вопросы кибернетики. — Вып. 1. — М.: Наука, 1991. — С. 10-25.

43. Яблонский С. В., Чегис И. А. О тестах для электрических схем // Успехи мат. наук. — 1955. — Т. 10. — Вып. 4 (66). — С. 182-184.

44. Armstrong D. В. On finding of nearly minimal set of fault detection tests for combinational logic nets // IEEE Trans. Comput. — 1966. — EC-15, N 1. — P. 66-73.

45. Bleick W. E. Asymptotics of Stirling numbers of the second kind // Proc. Amer. Math. Soc. — 1974. — Vol. 42, N2. — P. 575-580.

46. Cardot C. Quelques résultats sur l'application de l'algèbre de Boole à la synthèse des circuits à relais // Annales des Telecommunications. — 1952. — V. 7, N 2. — P. 75-84.

47. Eldred B. D. Test routines based on symbolic logic statements // J. ACM. — 1959. — Vol. 6, N 1. — P. 33-36.

48. Moore E. F. Gedanken-experiments on sequental machines // Automata studies. — Princeton Univ. Press, 1956. — P. 129-153. (Рус. пер.: Автоматы. — M.: ИЛ, 1956. — С. 159-210).

49. Romanov D. S. On the number of deadlock tests for closings of block circuits of parity counters // Discrete mathematics and applications.Vol. 7. — N 6. — 1997. — P. 573-591.

50. Roth J. P. Diagnosis of automata failures: a calculus and method // J. Research and development. — July, 1966. — P. 278-291.

51. Shannon C. E. A symbolic analysis of relay and switching circuits // Trans. AIEE. — 57. — 1938. — P. 713-722. (рус. перевод: К. Шеннон. Работы по теории информации и кибернетике. — М.: ИЛ, 1963.С. 59-101).

52. Tomescu I. La construction des tests minimaux pour les fonctions Booléennees symétriques // Calcolo. — Vol. 6, N 1. — 1971. — P. 59-68.