Построение тестов и оценка их параметров для некоторых классов контактных схем тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Романов, Дмитрий Сергеевич

• Романов, Дмитрий Сергеевич
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Романов, Дмитрий Сергеевич

Глава 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].

Список литературы диссертационного исследования кандидат физико-математических наук Романов, Дмитрий Сергеевич, 2000 год

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.