Идентификация статики и динамики технических объектов
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ы найти множество Р всех множеств столбцов, так чтобы для любого элемента Pi множества Р нашелся в каждой строке, по крайней мере, один элемент 1 в столбце, принадлежащем Рi и так, чтобы вычеркивание любого столбца из Рi приводило бы к потере указанного свойства.
Вторая задача допускает следующую алгебрологическую интерпретацию. Каждый столбец булевой ма трицы представляется булевой переменной, а каждая строка - булевой суммой (дизъюнкцией) этих переменных (в зависимости от того, равна переменная 1 или 0, она входит или не входит в указанную дизъюнкцию). Это означает, что элементарный тест, являющийся решением задачи, должен содержать, по крайней мере, одну проверку, по которой пара состояний (si, sr) R, соответствующая данной строке булевой матрицы, различима. Указанная дизъюнкция записывается для каждой строки булевой матрицы. Для того чтобы определить тест, необходимо образовать произведение (конъюнкцию) полученных дизъюнкций, поскольку сконструированная таким образом булева функции вида &v (конъюнкция дизъюнкций) будет истинна тогда и только тогда, когда одновременно все пары состояний, принадлежащие множеству R, различимы. Применяя дистрибутивный закон, а также известные правила алгебры логики
Идемпотентностиpk & pk = pk
И
Поглощенияpk Q & pk = pk
где Q - произвольная конъюнкция, преобразуем полученное выражение к виду v& (дизъюнкция конъюнкций). Полученная булева сумма не будет содержать лишних слагаемых, а элементы, входящие в одно слагаемое (дизъюнкцию) выражения v&, порождают множество, которое является элементарным диагностическим тестом, поскольку каждое слагаемое выражения v& обусловливает истинность исходной булевой функции вида &v (попарную различимость всех состоянии диагностируемого объекта), так как оно имеет общим с каждым сомножителем в выражении &v по крайней мере один элемент.
Рисунок 12. Исходная структурная схема объекта.
1.По структурной схеме составляем таблицу состояний, которая имеет вид:
Таблица 1. Таблица состояний.
011011111100000111110111111111011111111101111110100111110000000110000100110100110
2.Булева матрица, построенная по таблице состояний, выглядит следующим образом:
Таблица 2. Булева матрица, построенная по таблице состояний.
111011000101100000100000000100110000101111000101011111101011011101111001010111000011011000011101000010100000010000111010000011010100001001100000001010000000011000000111111000111011000011001000110000001111000001011111001011011001111001001001000001101111001101011001001001000100111000100011000000001000000100000100110000100010
. По булевой матрице записывается функция в форме дизъюнкция конъюнкций:
Таким образом, множество элементарных тестов состоит из четырех элементов
Т1 = {, , , , , }
Т2 = {, , , , , , }
Т3 = {, , , , , , }
Т4 = {,, , , , , }
Минимальным является тест Т1 = {, , , , , }
4.2 Построение достаточно простых диагностических тестов с помощью алгоритма Яблонского-Мак-Класки
Предлагаемый алгоритм в общем случае приводит к построению некоторого достаточно простого диагностического теста, однако иногда может приводить и к минимальному варианту. Пусть множество Е = {еk}, k= есть множество всех двоичных наборов еk = (), {0, 1} длины m ( j = ). Для всех еkЕ, норма еk опреде ляется числом единиц в данном наборе, т. е. || еk || = . Наборы еk и еrЕ называются сравнимыми (обо значается еkеr) если для всех j , j = (напри мер, 1010010110).
Исходная информация задается в виде некоторой булевой матрицы М, которую необходимо упрощать по следующим правилам:
. Правило поглощения строк. Если в матрице М имеется такая пара строк ai и ar (i, r =), что ai ar , то строка ar вычеркивается.
. Правило поглощения столбцов. Если в матрице М имеется такая пара столбцов bj и bt ( j, t = ), что bt bj, то столбец bt вычеркивается.
. Критерий вхождения столбца во все неприводимые матрицы. Если в матрице М имеется строка ai, которая содержит только одну единицу (т.е. ||ai|| = 1), стоящую на пересечении i-й строки и j-го столбца, то столбец bj отмечается, как входящий в минимальный диагностический тест, и вычёркивается из М.
4. Если в матрице имеется столбец , не содержащий единиц (т. е. ||bj||=0), то этот столбец вычеркивается из М.
Правила преобразования применяются к исходной матрице М до тех пор, пока эти правила приводят к упрощению М. Такое упрощение может привести к двум результатам.
. После применения правил преобразования в матрице М не осталось ни одного столбца. В этом случае отмеченные столбцы образуют неприводимую матрицу М*, имеющую минимальное число столбцов. Следовательно, подмножество проверок из П, имеющих те же номера, что и столбцы в М*, образует минимальный диагностический тест.
. Из матрицы М получена матрица М0, которая не упрощается при дальнейшем применении правил преобразования. Такая матрица называется циклической. В этом случае любой тест Т, полученный при помощи матрицы М, можно представить в виде
T = T1 T2
где T1 - подмножество проверок из П, номера которых совпадают с номерами отмеченных столбцов из M;
T2 - подмножество проверок из П, которое можно рассматривать как некоторый тест, полученный в том случае, если исходную матрицу М заменить на циклическую матрицу М0. Очевидно, что тест Т будет минимальным диагностическим тестом только в том случае, когда T2 будет содержать минимальное число проверок. Поэтому задача построения минимального диагностического теста Т0 с помощью матрицы М сводится к задаче построения теста Т0 с помощью циклической булевой матрицы М0.
Для упрощения циклич