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

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

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

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

Одним из эффективных подходов к построению схем контроля является метод, описанный в работах [11, 12], который состоит в следующем. Рассмотрим комбинационное устройство (КУ) с n входами, значения которых описываются множеством X={x₁,…,x_n} и k выходами, значения которых описываются множеством логических функций Y = {y₁(X),…,y_k(X)}. Обозначим множество различных выходных слов при отсутствии ошибок Y^*={Y^*₁,…,Y^*_s}. Разобьем множество входных слов (наборов) на подмножества X^*₁, …, X^*_s, называемых группами. К одной группе относятся входные слова, которым соответствуют одинаковые выходные слова. Тогда при правильном функционировании: если X X^*_i то Y = Y^*_i и если Y = Y^*_i, то X X^*_i. Количество слов в группах обозначим D = {d₁,…, d_s}. 
Для упрощения процедуры построения схемы контроля разобьем диагностические модели (ДМ) на классы эквивалентности. Результатом классификации является построение каталогов типовых решений, которые используются при построении средств контроля и поиск оптимального варианта проводить на множестве типовых решений, количество которых значительно меньше общего количества вариантов [13].
При решении задачи классификации необходимо определить некоторую полную систему инвариантов, разделяющей любые два неэквивалентных объекта из рассматриваемой совокупности. Инварианты отражают неизменные наиболее фундаментальные свойства изучаемых объектов. Существуют различные подходы к определению инварианта в зависимости от способа задания группы преобразований. При явном задании группы преобразований G = {g₁, g₂, … , g_d} на множестве Х, в результате любого преобразования g_i Є G на элемент x Є Х будет получен элемент x^* Є Х. Во втором случае группа преобразований G явно не вводится, а вводится отношение эквивалентности , удовлетворяющее требованиям рефлексивности, симметричности и транзитивности. В результате множество объектов разбивается на эквивалентные по подмножества [14, 15].
Любой объект из класса эквивалентности с помощью заданных преобразований может перейти в другой объект из этого же класса эквивалентности. Любая эквивалентность определяет разбиение множества: два класса одной эквивалентности либо не пересекаются, либо совпадают. И обратно, любое разбиение множества на непересекающиеся классы порождает эквивалентность 
Поскольку все объекты, принадлежащие одному классу эквивалентности, переходят друг в друга в результате заданной группы преобразований, то для описания класса эквивалентности достаточно определить типового представителя, в качестве которого может быть выбран любой элемент, принадлежащий рассматриваемому классу эквивалентности. Для однозначного описания типовых представителей целесообразно определение простейшего вида, к которому можно привести исследуемый математический объект с помощью рассматриваемой группы преобразований, т.е. построение канонических форм. Представителя класса эквивалентности, имеющего минимальную каноническую форму, будем называть типовым представителем класса эквивалентности [13, 15].
Рассмотрим применение описанного подхода к классификации диагностических моделей.
ДМ – это формализованное описание объекта, необходимое для решения задач диагностирования. При определении множества обнаруживаемых неисправностей существенным является вид множества D = {d₁,…, d_s}. Поэтому будем полагать, что две ДМ относятся к одному классу эквивалентности, если имеют одинаковые значения n, k, s и одинаковые лексикографически упорядоченные множества D. 
Конструктивное перечисление типовых ДМ сводится к построению полного списка типовых представителей. Общий подход к определению типового представителя состоит из следующих этапов [13].
1. Выбор любого элемента – представителя класса эквивалентности.
2. Выполнение множества заданных преобразований объекта, т.е. порождение всех элементов рассматриваемого класса эквивалентности.
3. Определение канонической формы для элементов, полученных в результате каждого преобразования.
4. Определение типового представителя – элемента, имеющего минимальную каноническую форму.
В качестве канонической формы при описании типовых диагностических моделей предлагается представлять множество D = {d₁,…, d_s} в виде серийной символьной последовательности, свойства которых исследованы в работе [16]. 
В общем случае, для алфавита ={₁, …, _r}, символьной (r, m) последовательностью называется последовательность W = {w₁,…, w_m), в которой w_i , i = 1,…, m; m r и в последовательности Wпредставлены все символы из алфавита . Для рассматриваемой задачи .
Подпоследовательность w_p+1w_p+2…w_p+q называется серией в W, если
w_p+1 = w_p+2 = … = w_p+q;
w_p w_p+1; при p 1; 
w_p+q w_p+q+1; при p + q m.
i–ая серия описывается в виде S_i(u_i,v_i), где u_i – символ, образующий i–ю серию, v_i – длина i–й серии (количество символов u_i). Символьная (r, m) последовательность W, состоящая из h серий представляется в виде

где u_i ;

.

Множество U = {u₁, u₂, … , u_h} называется структурой серийной последовательности, а множество V = {v₁, v₂, …, v_h} – составом серийной последовательности.
Серия S_j(u_j, v_j) называется серией i–го вида, если u_j = _i. Количество серий i–го вида (_i) и количество символов i–го вида (_i) в последовательности W определяются следующим образом:

, ,
.

Множества ={₁,₂,…,_r} и ={₁, ₂,…, _r} обладают следующими свойствами:

 

На множестве символьных последовательностей введены следующие операции.
1. Слиянием последовательности W¹ = S¹₁(a¹₁,v¹₁)…S¹_h1(a¹_h1, v¹_h1) с алфавитом ₁ и последовательности W² = S²₁(a²₁,v²₁)…S²_h2(a²_h2, v²_h2) с алфавитом ₂ (обозначается W³ = (W¹, W²)) называется последовательность W³ = S³₁(a³₁,v³₁) … S³_h3(a³_h3,v³_h3) с алфавитом ₃ = _1 2. Количество серий в последовательности W³ зависит от вида символов a¹_h1 и a²₁, следующим образом. 
При a¹_h1 a²₁ последовательность W³ имеет вид:

При a¹_h = a²₁ последовательность W³ имеет вид:

где a^*= a¹_h, v^* = v¹_h1 + v²₁, h₃ = h₁ + h₂ – 1. 
2. Выделение подпоследовательности в серийной последовательности W¹ = S₁(a₁,v₁) S₂(a₂,v₂) … S_h1(a_h1, v_h1) (обозначается W² = (W¹, , )), состоит в формировании последовательности W² вида S(a, v)…S(a, v), т.е. выделение серий с номерами с по .
3. Вставка последовательности W² в последовательность W¹, начиная с -ой серии (обозначается W³ = (W¹, W², )) определяется следующим образом:

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

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

,

то данная задача сводится к задаче разбиения чисел [15]. 
Разбиение числа n – это представление его в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается, то есть разбиения, отличающиеся только порядком частей, считаются равными. 
В теории чисел разработаны различные подходы к оценке числа разбиений p(n), которые можно разделить на два вида: асимптотические [15, 17] и точные [18, 19]. Первые дают приближенную оценку, а вторые имеют большую трудоемкость. 
При построении множества разбиений и оценке их количества эффективными являются рекуррентные методы, основанные на последовательном формировании множества разбиений. Для рассматриваемой задачи классификации ДМ необходимо построить все разбиения числа 2ⁿ. Анализ методов генерации разбиений показал, что множество типовых ДМ для КУ с n входами, обозначенное T(2ⁿ), состоит из двух подмножеств T(2ⁿ) = {T¹(2ⁿ), T²(2ⁿ)}, которые отличаются способом формирования своих элементов.
К подмножеству T¹(2ⁿ), мощность которого p(2ⁿ-1) относятся типовые ДМ, сформированные на основании каталога T(2ⁿ-1) типовых ДМ следующим образом:
t_i(2ⁿ) = (S(1,1), t_i(2ⁿ-1)),
где t_i(2ⁿ) T(2ⁿ), t¹_i(2ⁿ-1)) T(2ⁿ-1) , i = 1,…, p(2ⁿ-1).
К подмножеству T²(2ⁿ), мощность которого p₂ относятся типовые ДМ, сформированные на основании каталогов T(2ⁿ - s) типовых ДМ для s = 1,…, 2ⁿ-1 следующим образом:
Для выбранного значения s в каталоге T(2ⁿ - s) выбираются представители, имеющие s частей в разбиении, подмножество которых обозначено T(2ⁿ – s, s), а его мощность р(2ⁿ – s, s). Состав серийных последовательностей W(2ⁿ)= S₁(u₁,v₁)…S_h(u_h, v_h), входящих в описание 2ⁿ типа формируется на основании состава серийных последовательностей W(2ⁿ-s)=S^*₁(u^*₁,v^*₁)…S^*_h(u^*_h,v^*_h), входящих в описание (2ⁿ-s) типа, следующим образом:
S_i(u_i,v_i)= S^*_i(u^*_i+1,v^*_i), i=1,…,h.
Следовательно, количество типовых ДМ равно количеству разбиений р(2ⁿ) и определяется следующим образом:

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

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

Таблица 1. – Значения р(2ⁿ, 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 = {d₁,…, d_s}, которому соответствует серийная последовательность с составом V = {v₁, v₂, …, v_h}, обозначенное O(n, s, D).
Значение O(n, s, D) определяется количеством вариантов построения групп:
O(n, s, D) = LX(n, s , D)LY(k, s),
где LX(n, s, D) – количество вариантов построения подмножеств X^*₁, …, X^*_s ,

,

LY(k, s) – количество вариантов построения множества выходных слов Y^*₁,…, 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.

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