УДК 681.32

КОНСТРУКТИВНОЕ ПЕРЕЧИСЛЕНИЕ ДИАГНОСТИЧЕСКИХ МОДЕЛЕЙ

Павлик Анна Владимировна
Национальный аэрокосмический университет «Харьковский авиационный институт», Украина
ассистент

Аннотация
Проведен анализ методов функционального контроля. Предложена классификация диагностических моделей. Рассмотрено решение задачи перечисления типовых диагностических моделей. Получены оценки количества типовых представителей и построены каталоги типовых вариантов. Полученные результаты позволят упростить процесс построения схем контроля.

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


CONSTRUCTIVE ENUMERATION OF DIAGNOSTIC MODELS

Pavlik Anna Vladimirovna
National Aerospace University "Kharkiv aviation institute", Ukraine
assistant

Abstract
The analysis of the functional control methods is lead. Classification of diagnostic models is offered. The decision of a typical diagnostic models enumeration problem is considered. Estimations of typical representatives quantity are received and catalogues of typical variants are constructed. The received results will allow to simplify process of schemes control construction.
.

Keywords: a class of equivalence, check, constructive enumeration, diagnostic model, technical diagnostics, the functional control, the typical representative


Библиографическая ссылка на статью:
Павлик А.В. Конструктивное перечисление диагностических моделей // Современная техника и технологии. 2014. № 4 [Электронный ресурс]. URL: http://technology.snauka.ru/2014/04/3383 (дата обращения: 03.06.2017).

Постановка проблемы

Рост сложности автоматизированных систем управления промышленного и специального назначения требует повышение надежности систем и элементов, осуществляющих управление. Одним из основных направлений в решении данной проблемы является повышение достоверности информации на выходах системы. Требуемая эффективность функционирования цифровых систем может быть достигнута путем своевременного обнаружения отказавших элементов и их восстановления. Автоматизация процесса проверки и наладки сложных технических систем – важнейшее средство ускорения процесса создания, выпуска, внедрения и повышения эффективности создаваемых систем различного назначения. Эта проблема может быть решена путем исследования, разработки и внедрения в эксплуатацию прогрессивных методов и средств контроля технического состояния объектов [1, 2].

Анализ последних исследований и публикаций

Общей тенденцией современных технических систем является значительное усложнение их аппаратурного состава и увеличение потоков разнородной информации, циркулирующей между отдельными компонентами системы. Вместе с тем резко возросли требования к надежности и эффективности функционирования этих систем в процессе их целевого применения. Сокращение длительности простоев техники может быть достигнуто за счет сокращения времени определения работоспособности технических объектов и поиска места отказа в них. Наиболее выгодной является интегрированная автоматизация процессов проверок технических систем, включающая в себя автоматизацию процессов подготовки проверочных воздействий, организацию самого процесса проверки и принятия решения, устранения неисправностей, прогноза состояния объекта. Поэтому важное значение приобретает теория рациональной организации процессов проверки, включающая в себя анализ моделей объектов диагноза, выбор технических средств для проверки и организацию их взаимодействия, увязку их с процессами восстановления отказавших элементов [3].
Техническая диагностика исследована в работах Беннетс Р. [4], П.П. Пархоменко и Е.С. Согомоняна [5], и др. Новые подходы к разработке систем контроля предложены в работах Г.П. Аксеновой [6], А.В. Дрозд [7], Р. Айзермана [8].
Для оперативного обнаружения ошибок используется функциональное диагностирование, которое осуществляется в процессе непосредственного использования объекта контроля по назначению, когда на него поступают только рабочие воздействия, предусмотренные алгоритмом функционирования объекта. Функциональное диагностирование обеспечивает возможность немедленного реагирования системы контроля и управления объектом на нарушения правильности функционирования. К сожалению, в настоящее время отсутствуют эффективные методы построения схем функционального контроля дискретных систем [9, 10].

Цель работы

Разработка метода классификация диагностических моделей и метода их перечисления.

Основные результаты исследований

Одним из эффективных подходов к построению схем контроля является метод, описанный в работах [11, 12], который состоит в следующем. Рассмотрим комбинационное устройство (КУ) с n входами, значения которых описываются множеством X={x1,…,xn} и k выходами, значения которых описываются множеством логических функций Y = {y1(X),…,yk(X)}. Обозначим множество различных выходных слов при отсутствии ошибок Y*={Y*1,…,Y*s}. Разобьем множество входных слов (наборов) на подмножества X*1, …, X*s, называемых группами. К одной группе относятся входные слова, которым соответствуют одинаковые выходные слова. Тогда при правильном функционировании: если X X*i то Y = Y*i и если Y = Y*i, то X X*i. Количество слов в группах обозначим D = {d1,…, ds}. 
Для упрощения процедуры построения схемы контроля разобьем диагностические модели (ДМ) на классы эквивалентности. Результатом классификации является построение каталогов типовых решений, которые используются при построении средств контроля и поиск оптимального варианта проводить на множестве типовых решений, количество которых значительно меньше общего количества вариантов [13].
При решении задачи классификации необходимо определить некоторую полную систему инвариантов, разделяющей любые два неэквивалентных объекта из рассматриваемой совокупности. Инварианты отражают неизменные наиболее фундаментальные свойства изучаемых объектов. Существуют различные подходы к определению инварианта в зависимости от способа задания группы преобразований. При явном задании группы преобразований G = {g1, g2, … , gd} на множестве Х, в результате любого преобразования gi Є G на элемент x Є Х будет получен элемент x* Є Х. Во втором случае группа преобразований G явно не вводится, а вводится отношение эквивалентности , удовлетворяющее требованиям рефлексивности, симметричности и транзитивности. В результате множество объектов разбивается на эквивалентные по подмножества [14, 15].
Любой объект из класса эквивалентности с помощью заданных преобразований может перейти в другой объект из этого же класса эквивалентности. Любая эквивалентность определяет разбиение множества: два класса одной эквивалентности либо не пересекаются, либо совпадают. И обратно, любое разбиение множества на непересекающиеся классы порождает эквивалентность 
Поскольку все объекты, принадлежащие одному классу эквивалентности, переходят друг в друга в результате заданной группы преобразований, то для описания класса эквивалентности достаточно определить типового представителя, в качестве которого может быть выбран любой элемент, принадлежащий рассматриваемому классу эквивалентности. Для однозначного описания типовых представителей целесообразно определение простейшего вида, к которому можно привести исследуемый математический объект с помощью рассматриваемой группы преобразований, т.е. построение канонических форм. Представителя класса эквивалентности, имеющего минимальную каноническую форму, будем называть типовым представителем класса эквивалентности [13, 15].
Рассмотрим применение описанного подхода к классификации диагностических моделей.
ДМ – это формализованное описание объекта, необходимое для решения задач диагностирования. При определении множества обнаруживаемых неисправностей существенным является вид множества D = {d1,…, ds}. Поэтому будем полагать, что две ДМ относятся к одному классу эквивалентности, если имеют одинаковые значения n, k, s и одинаковые лексикографически упорядоченные множества D. 
Конструктивное перечисление типовых ДМ сводится к построению полного списка типовых представителей. Общий подход к определению типового представителя состоит из следующих этапов [13].
1. Выбор любого элемента – представителя класса эквивалентности.
2. Выполнение множества заданных преобразований объекта, т.е. порождение всех элементов рассматриваемого класса эквивалентности.
3. Определение канонической формы для элементов, полученных в результате каждого преобразования.
4. Определение типового представителя – элемента, имеющего минимальную каноническую форму.
В качестве канонической формы при описании типовых диагностических моделей предлагается представлять множество D = {d1,…, ds} в виде серийной символьной последовательности, свойства которых исследованы в работе [16]. 
В общем случае, для алфавита ={1, …, r}, символьной (r, m) последовательностью называется последовательность W = {w1,…, wm), в которой wi , i = 1,…, m; m r и в последовательности Wпредставлены все символы из алфавита Для рассматриваемой задачи .
Подпоследовательность wp+1wp+2…wp+q называется серией в W, если
wp+1 = wp+2 = … = wp+q;
wp wp+1; при p 1; 
wp+q wp+q+1; при p + q m.
i–ая серия описывается в виде Si(ui,vi), где ui – символ, образующий i–ю серию, vi – длина i–й серии (количество символов ui). Символьная (r, m) последовательность W, состоящая из h серий представляется в виде

W = S1(u1,v1)S2(u2,v2)…Sh(uh, vh),

где ui ;

.

Множество U = {u1, u2, … , uh} называется структурой серийной последовательности, а множество V = {v1, v2, …, vh} – составом серийной последовательности.
Серия Sj(uj, vj) называется серией i–го вида, если ui. Количество серий i–го вида (i) и количество символов i–го вида (i) в последовательности W определяются следующим образом:

,
.

Множества ={1,2,…,r} и ={12,…, r} обладают следующими свойствами:

 

На множестве символьных последовательностей введены следующие операции.
1. Слиянием последовательности W1 = S11(a11,v11)…S1h1(a1h1, v1h1) с алфавитом 1 и последовательности W2 = S21(a21,v21)…S2h2(a2h2, v2h2) с алфавитом 2 (обозначается W3 = (W1, W2)) называется последовательность W3 = S31(a31,v31) … S3h3(a3h3,v3h3) с алфавитом 3 = 1 2. Количество серий в последовательности W3 зависит от вида символов a1h1 и a21, следующим образом. 
При a1h1 a2последовательность W3 имеет вид:

W= S11(a11,v11) … S1h(a1h, v1h1) S21(a21,v21) … S2h2(a2h2, v2h2),
h3 = h1 + h2.

При a1h = a21 последовательность W3 имеет вид:

W= S11(a11,v11) … S1h–1(a1h–1, v1h–1) S*(a*,v*) S22(a22,v22) … S2h2(a2h2, v2h2),

где a*= a1h, v* = v1h1 + v21, h3 = h1 + h2 – 1. 
2. Выделение подпоследовательности в серийной последовательности W1 = S1(a1,v1) S2(a2,v2) … Sh1(ah1, vh1) (обозначается W2 = (W1, , )), состоит в формировании последовательности W2 вида S(a, v)…S(a, v), т.е. выделение серий с номерами с по .
3. Вставка последовательности W2 в последовательность W1, начиная с -ой серии (обозначается W3 = (W1, W2)) определяется следующим образом:

W3 = (W1, W2, ) = ((W1, 1, – 1), W2, (W1, , v1h1)).

4. Соединением m–ичных последовательностей W1, W2, … , Wk (обозначается W = Ф(W1, W2, … , Wk) называется последовательность W, элементы которой (слова) формируются следующим образом

wi = w1iw2i…wki, i = 1, … , m.

Количество различных слов в последовательности W обозначено .
Конструктивное перечисление ДМ состоит в построении для заданных значений n и s = 1,…, n множеств D = {d1,…, ds}. Поскольку

,

то данная задача сводится к задаче разбиения чисел [15]. 
Разбиение числа n – это представление его в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается, то есть разбиения, отличающиеся только порядком частей, считаются равными. 
В теории чисел разработаны различные подходы к оценке числа разбиений p(n), которые можно разделить на два вида: асимптотические [15, 17] и точные [18, 19]. Первые дают приближенную оценку, а вторые имеют большую трудоемкость. 
При построении множества разбиений и оценке их количества эффективными являются рекуррентные методы, основанные на последовательном формировании множества разбиений. Для рассматриваемой задачи классификации ДМ необходимо построить все разбиения числа 2n. Анализ методов генерации разбиений показал, что множество типовых ДМ для КУ с n входами, обозначенное T(2n), состоит из двух подмножеств T(2n) = {T1(2n), T2(2n)}, которые отличаются способом формирования своих элементов.
К подмножеству T1(2n), мощность которого p(2n-1) относятся типовые ДМ, сформированные на основании каталога T(2n-1) типовых ДМ следующим образом:
ti(2n) = (S(1,1), ti(2n-1)),
где ti(2n) T(2n), t1i(2n-1)) T(2n-1) , i = 1,…, p(2n-1).
К подмножеству T2(2n), мощность которого p2 относятся типовые ДМ, сформированные на основании каталогов T(2- s) типовых ДМ для s = 1,…, 2n-1 следующим образом:
Для выбранного значения s в каталоге T(2- s) выбираются представители, имеющие s частей в разбиении, подмножество которых обозначено T(2– s, s), а его мощность р(2– s, s). Состав серийных последовательностей W(2n)= S1(u1,v1)…Sh(uh, vh), входящих в описание 2n типа формируется на основании состава серийных последовательностей W(2n-s)=S*1(u*1,v*1)…S*h(u*h,v*h), входящих в описание (2n-s) типа, следующим образом:
Si(ui,vi)= S*i(u*i+1,v*i), i=1,…,h.
Следовательно, количество типовых ДМ равно количеству разбиений р(2n) и определяется следующим образом:

при начальных условиях р(1,1)=1.

В табл. 1 приведены значения р(2n, s) для n=6, s=1,…,2n-1

Таблица 1. – Значения р(2n, s) для n=6.

s
р(26,s)
s
р(26, s)
s
р(26, s)
s
р(26, s)
s
р(26,s)
s
р(26,s)
2
32
13
129883
24
36654
35
4565
46
385
57
15
3
341
14
127786
25
30812
36
3718
47
297
58
11
4
1906
15
121510
26
25820
37
3010
48
231
59
7
5
6747
16
112540
27
21540
38
2436
49
176
60
5
6
17180
17
101982
28
17932
39
1958
50
135
61
3
7
34082
18
90889
29
14864
40
1575
51
101
62
2
8
55974
19
79855
30
12303
41
1255
52
77
63
1
9
79403
20
69414
31
10141
42
1002
53
56
64
1
10
100654
21
59755
32
8349
43
792
54
42
11
116792
22
51087
33
6842
44
627
55
30
12
126560
23
43371
34
5604
45
490
56
22

В табл. 2.приведены каталоги Т(1)-Т(7).

Таблица 2. – Каталоги Т(1)-Т(7).

n
s
u1
u2
v1
v2
n
s
u1
u2
u3
v1
v2
v3
1
1
1
1
1
6
3
1
2
3
2
2
1
1
2
3
2
1
2
3
1
1
1
1
1
2
1
3
3
1
4
2
1
3
3
1
1
3
2
1
3
2
2
1
1
2
1
1
2
2
2
4
1
1
1
1
3
1
2
3
1
5
1
1
4
4
1
1
4
1
1
6
1
3
1
1
2
2
1
7
7
1
1
7
2
1
2
2
6
1
1
2
5
1
2
2
1
3
1
1
5
1
1
2
3
2
1
1
4
1
5
2
1
3
4
1
5
5
1
1
5
4
1
1
2
1
3
4
1
1
2
3
1
4
2
1
2
3
2
1
1
3
1
1
2
1
2
4
3
1
4
3
1
3
2
1
3
2
1
3
1
2
3
2
1
2
1
2
3
1
1
3
2
1
3
1
2
2
2
1
4
1
1
3
3
1
2
4
1
1
1
1
1
5
1
3
4
1
5
2
1
6
6
1
1
6
2
1
3
4
1
1
5
1
1
2
4
1
2
2
2
5
1
1
4
1
1
2
2
2
2
3
1
6
1
1
4
2
1
3
3
1
1
1
7
1

Определим количество ДМ, относящихся к одному классу эквивалентности с лексикографически упорядоченным множеством D = {d1,…, ds}, которому соответствует серийная последовательность с составом V = {v1, v2, …, vh}, обозначенное O(n, s, D).
Значение O(n, s, D) определяется количеством вариантов построения групп:
O(n, s, D) = LX(n, s , D)LY(k, s),
где LX(n, s, D) – количество вариантов построения подмножеств X*1, …, X*,

,

LY(k, s) – количество вариантов построения множества выходных слов Y*1,…, Y*s.

.

На рис. 1. приведены значения O(8).


Рисунок 1. – Значения O(8)

На рис. 2 приведены значения О(16, s)

Рисунок 2. – Значения О(16, s) для s = 1,…, 16

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


Библиографический список
  1. Павлов, А.А. Методы обнаружения и коррекции ошибок устройств хранения и передачи информации/ А.А. Павлов, А.Н. Царьков, А.В. Шандриков // Контроль и диагностика. – 2005. – № 6. – С. 22-26.
  2. Дрозд А. В. Нетрадиционный взгляд на рабочее диагностирование вычислительных устройств/ Проблемы управления. – 2008. – №2. – С. 48–56.
  3. Гуляев В.А. Техническая диагностика управляющих систем. Киев: Наукова думка, 1983.
  4. Беннетс Роберт Дж. Проектирование тестопригодных логических схем.М.: Радио и связь. 1990.
  5. Пархоменко П.П., Согомонян Е.Н. Основы технической диагностики: Оптимизация алгоритмов диагностирования, аппаратурные средства.-М.:Энергия, 1981.
  6. Аксeнова, Г.П. О функциональном диагностировании дискретных устройств в условиях работы с неточными данными [Текст]/ Г. П. Аксeнова // Проблемы управления. – 2008. – Т. 5. – С. 62–66.
  7. Дрозд, А. В. Нетрадиционный взгляд на рабочее диагностирование вычислительных устройств/ А.В. Дрозд // Проблемы управления. – 2008. – №2. – С. 48–56.
  8. Isermann R. Model-based fault detection and diagnosis. Status and applications/ Annual Reviews in Control. – 2005. – V. 29.- P. 71-85.
  9. Кошевой Н.Д., Павлик А.В. Функциональный контроль комбинационных устройств// Радіоелектронні і комп’ютерні системи. – 2013. – № 1(57). С. 45 – 49.
  10. Павлик А.В. Метод построения минимальных контрольных и диагностических тестов [Текст]  // Современная техника и технологии. – Март, 2013 [Электронный ресурс]. URL: http://technology.snauka.ru/2013/03/1697
  11. Программно-аппаратные средства контроля [Текст] /  Дергачев В.А., Савельев А.С., Аникин А.Н., Цеховской М.В., Павлик А.В. // Современные научные исследования и инновации. – Июль 2013. – № 7 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2013/07/25508
  12. Павлик А.В. Адаптивные схемы контроля. Журнал докторантов и аспирантов/ г. Курск. – 2013. – № 7. С. 74-76.
  13. Применение инвариантов в комбинаторных исследованиях/ Н.Д. Кошевой, А.В. Павлик, В.П. Сироклын, Н.А. Дидык // Зб. наук. пр. військ. ін-у Київського нац. ун-ту ім. Т. Шевченка: - 2008. – Вып. 14.- С. 83 – 87.
  14. Сачков В.Н. Комбинаторные методы дискретной математики//   М.: Наука, 1977 – 319с.
  15. Andrews G. E., Integer Partitions/ G. E. Andrews, K. Eriksson // Cambridge University Press, 2004. – 141 p.
  16. Метод перечисления символьных последовательностей [Текст] / Н.Д. Кошевой, Е.М. Костенко, Н.В. Доценко, А.В. Павлик // Радіоелектронні ікомп’ютерні системи. – 2012. – №3(55). – С. 45–49.
  17. Flajolet P. Analytic combinatorics/ P. Flajoret, R. Sedgewick // Cambridge University Press,  2009.
  18. Banderier C. Generating functions of generating trees / Discrete Mathematics 246, 1-3,  2002. -  pp. 29–55.
  19. Stanton D., White D., Constructive combinatorics. — New York: Springer–Verlag, 1986.


Все статьи автора «Павлик Анна Владимировна»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: