2. Проектирование в машиностроении и электронике

Матрично-диагональный способ локализации неисправностей в дискретном устройстве

Г.П. Аксенова,
с.н.с, к.т.н., aksenova@ipu.ru
ИПУ РАН, г. Москва

В целях сокращения объема контролирующей аппаратуры предложен матричный метод локализации неисправностей, который определяет местонахождение любой одиночной неисправности в дискретном устройстве. На основе матричного метода разработан новый, матрично-диагональный способ локализации, отличающийся от матричного тем, что в нем повышена размерность проверки матрицы, Доказано, что матрично-диагональным способом локализуются все двух- и трехкратные неисправности.

In order to reduce the cost of testing hardware, the matrix fault localization method is proposed. The method determines the location of any single fault in the discrete device. The new matrix-diagonal method based on the matrix method is developed. It differs from the matrix method in that it has the increased dimension of the check-up of the matrix, It is proved that the matrix-diagonal method localizes all the double and triple faults.

Введение

Проектирование отказоустойчивых систем опирается на широкое использование в них диагностирования с целью определения технического состояния компонент и указания места неисправных компонент. В режиме диагностирования исходный объект приводится к контролепригодному виду, т.е. в нем проводится декомпозиция, в результате чего оно распадается на блоки (подсхемы), имеющие управляемые входы (на которые будет подаваться тестовая последовательность) и наблюдаемые выходы (контрольные точки), с которых снимается тестовая реакция. В качестве аппаратуры, анализирующей тестовую реакцию, обычно используют сигнатурные анализаторы (СА), одноканальные (одновходовые) и многоканальные (многовходовые) [1]. Одноканальные СА предназначены для анализа реакции, снимаемой только с одной контрольной точки тестируемого устройства. Так как контрольных точек, как правило, оказывается достаточно много, то выгоднее применять многоканальный СА, который, имея такой же объем аппаратуры, что и одноканальный СА, может анализировать реакцию сразу k контрольных точек, где k - число разрядов (триггеров) в СА, Обычно используют k ≥ 16.

Для задачи проверки исправности проверяемого объекта использование многоканального СА имеет преимущество по аппаратурным затратам. Однако для задачи локализации неисправности, т.е. определения контрольной точки, выдающей неправильную тестовую реакцию, использование многоканальных СА в качестве средств контроля вносит некоторые осложнения, обусловленные тем, что поступающая в СА реакция с k контрольных точек смешивается в нем и невозможно указать, какая именно контрольная точка выдает неправильную тестовую реакцию.

Отсюда возникает задача: как в случае использования многоканальных СА локализовать неисправную контрольную точку, причем с меньшими аппаратурными затратами, чем при использовании одноканальных СА.

1. Матричный метод локализации неисправности

Пронумеруем контрольные точки тестируемого объекта в произвольном порядке и расположим эти номера в виде (m × n )-матрицы, где m − число ее строк, n – число ее столбцов. Номера точек теперь будем называть элементами матрицы.

Рис. 1

На рис. 1 матрица выделена штрих-пунктирной линией, а элементы ее изображены в виде квадратов. Все дальнейшие рассуждения будем проводить для матрицы. Элемент, соответствующий неисправной контрольной точке, будем называть неисправным элементом; строку (столбец), в которой находится неисправный элемент, − неисправной строкой (столбцом). Если число контрольных точек N меньше mn, то последняя строка будет не полностью заполнена. Не умаляя общности, будем считать, что N = mn.

Контроль элементов (под контролем будем понимать анализ их тестовой реакции) предлагается осуществлять следующим образом. Элементы каждой строки и каждого столбца подключим к своему многоканальному СА (см. рис. 1). Всего потребуется m n-разрядных СА для строк и n m-разрядных СА для столбцов (на рисунке последние обозначены через СА¹). Такую организацию контроля назовем матричным способом контроля.

Как видим, при матричном способе контроль элементов организуется по строкам и столбцам. На это требуется m+n СА, что гораздо меньше, чем при использования одноканальных СА, где затраты составляют N = mn СА.

При матричном контроле каждый элемент проверяется дважды: в составе строки и в составе столбца при одноразовой подаче теста. Неисправный элемент находится (локализуется) на пересечении строки и столбца, зафиксированных своими СА как неисправные. В работе автора [2] доказано, что метод обеспечивает локализацию любой одиночной неисправности в матрице и некоторых кратных неисправностей таких, что неисправные элементы находятся все в одной строке или все в одном столбце.

Здесь предпринята попытка расширить класс неисправностей, который матричный метод способен локализовать, т.е. повысить разрешающую способность матричного метода.

2. Матрица и её свойства

Расположенные в матрице элементы определяются двумя координатами (i, j), где i – номер строки, i =1,…, m, j – номер столбца, j=1,…, n. Сначала рассмотрим квадратные матрицы, где m = n. Через каждый элемент можно провести две взаимно перпендикулярные диагонали. Диагональ, соединяющая первый элемент матрицы с последним, называется главной. Её и диагонали, ей параллельные, назовем прямыми диагоналями или, короче, диагоналями. Перпендикулярные им диагонали назовем ортогональными. В квадратной матрице главная диагональ содержит m элементов, также как строки и столбцы. Все остальные диагонали, параллельные главной, имеют число элементов, меньшее m, вплоть до одного элемента. Проведем объединение диагоналей так, чтобы каждое объединение содержало m элементов. Так, соседнюю сверху от главной диагональ, имеющую m-1 элементов, объединим с последней в нижней половине матрицы диагональю, содержащей один элемент (см. рис. 2). Вторую сверху от главной диагональ объединим с предпоследней внизу и т.д. Аналогичные объединения сделаем и для ортогональных диагоналей. В результате получим m объединенных прямых диагоналей и m объединенных ортогональных диагоналей. В дальнейшем будем рассматривать только объединенные диагонали, но при этом опускать слово «объединенная».

Рассмотрим произвольную матрицу, у которой m - нечетное число. Подробный анализ выявляет следующие свойства такой матрицы.

1. Через элемент может проходить только одна строка, один столбец, одна прямая диагональ и одна ортогональная диагональ, которые условно назовем параметрами элемента.

2. Два различных элемента могут иметь только один общий параметр или не иметь ни одного. Например, если два элемента находятся в одной строке (т.е. имеют уже общий параметр), то из просмотра матрицы видно, что столбцы и обе диагонали у них будут различаться. То же самое наблюдаем, когда два элемента находятся, скажем, в одной диагонали. Тогда столбцы, строки и вторые диагонали у них будут разные.

Заметим, что свойством 2 не обладают матрицы с четным m.

3. Локализация двукратных неисправностей

Как уже говорилось выше, матричный метод локализует кратную неисправность, если неисправные элементы находятся все в одной строке или все в одном столбце. Пусть, например, два неисправных элемента находятся в 1-й строке, скажем, это элементы 1 и 4 (см. рис. 2). Тогда при контроле будут зафиксированы как неисправные строка 1 и столбцы 1, 4. Следовательно, неисправные элементы будут определены однозначно на пересечениях строки 1 со столбцами 1 и 4. Если же два неисправных элемента находятся в разных строках и в разных столбцах, например элементы 1 и 9 на рис. 1, то неисправными будут две строки и два столбца и уже будут не два, а четыре их пересечения. Значит, в неисправные будут зачислены ещё два элемента 4 и 6, которые будем называть подозреваемыми. Таким образом, если для локализации одиночной неисправности требуется проверка по двум параметрам (строкам и столбцам), то для двукратной неисправности этого уже недостаточно.

Рис. 2

Попробуем повысить размерность проверки и проведем ее по трём параметрам, включив диагонали, например прямые. При такой проверке диагонали, проходящие через неисправные элементы, будут, естественно, зафиксированы как неисправные, а диагонали через подозреваемые элементы – как исправные. Тем самым подозрение с элементов 4 и 6 будет снято. Назовем такой способ контроля матрицы матрично-диагональным.

Отсюда можно сформулировать теорему.

Т е о р е м а 1. Матрично-диагональный способ контроля по трем параметрам локализует любую одиночную и любую двукратную неисправность. При тестировании неисправные элементы имеют все три своих параметра (строку, столбец и диагональ) неисправными, а у исправных элементов хотя бы один параметр будет исправен.

Д о к а з а т е л ь с т в о для одиночных неисправностей см. в [2], Проведем доказательство для двукратных неисправностей. Очевидно, что при тестировании у неисправного элемента будут зафиксированы как неисправные все три его параметра (строка, столбец и диагональ). Покажем, что у всех остальных (т.е. исправных) элементов хотя бы один параметр будет исправен. Это действительно так. Исправный элемент может иметь с неисправным только один общий параметр по свойству 2. Так как неисправность двукратная, то общих параметров с неисправными элементами будет максимум два. Эти параметры будут зафиксированы при тестировании как неисправные. Поскольку контроль ведется по трём параметрам, то третий параметр наверняка будет исправным. Теорема доказана.

4. Локализация трёхкратных неисправностей

Перейдём к рассмотрению трехкратных неисправностей. Сначала проведем рассуждения на примере рис. 3, где трехкратная неисправность элементов 3, 4, 8 (они отмечены крестами) при контроле по строкам и столбцам дает шесть подозреваемых элементов 1, 2, 5, 6, 7, 9. Значит, необходимо добавить диагональный контроль. Если возьмем прямые диагонали, то подозрение с элементов 1, 2, 5, 6 будет снято. Но элемент 7 останется под подозрением, потому что в его диагонали находится неисправный элемент 3 и при контроле СА зафиксирует ее как неисправную. То же имеет место и для подозреваемого элемента 9: в его прямой диагонали находится неисправный элемент 4.

Если же возьмем не прямые, а только ортогональные диагонали, то не будет снято подозрение с элементов 2 и 5, потому что в их диагоналях находятся неисправные элементы 4 и 3 соответственно.

Следовательно, трёхмерного контроля недостаточно для локализации трехкратной неисправности и надо ввести контроль по четырем параметрам: строкам, столбцам и обеим диагоналям. Тогда, как видно из рис. 3, все подозреваемые элементы будут признаны исправными по одной из своих диагоналей.

Т е о р е м а 2. Матрично-диагональный способ контроля по четырем параметрам локализует любую одно-, двух- и трехкратную неисправность. При тестировании неисправные элементы имеют все четыре своих параметра (строку, столбец и обе диагонали) неисправными, а у исправных элементов хотя бы один параметр будет исправен.

Рис. 3

Д о к а з а т е л ь с т в о. Ясно, что теорема 2 включает в себя как составляющую теорему 1. Поэтому доказательство проведем только для трехкратных неисправностей, построив его аналогично доказательству теоремы 1. Ясно, что при тестировании у неисправного элемента будут зафиксированы как неисправные все четыре его параметра (строка, столбец и обе диагонали). У исправного элемента всегда хотя бы один параметр будет исправным, потому что по свойству 2 исправный элемент может иметь с тремя неисправным элементами не больше трех общих параметров, значит, четвертый параметр у него будет исправным. Теорема доказана.

5. Локализация неисправностей кратности больше трёх

Т е о р е м а 3. Матрично-диагональный способ контроля по трём и четырем параметрам локализует неисправности любой кратности, большей трёх (но не превышающей m), если неисправные элементы находятся или все в одной строке, или все в одном столбце, или все в одной из диагоналей. При тестировании неисправные элементы имеют все свои параметры неисправными, а у исправных элементов хотя бы один параметр будет исправен.

Д о к а з а т е л ь с т в о. Длина строки, столбца и диагонали в матрице не превышает m, следовательно, речь идет о кратности, не превышающей m. При тестировании у неисправных элементов будут зафиксированы как неисправные все их параметры. Теперь рассмотрим исправные элементы.

Если неисправные элементы находятся все в одной строке (столбце), то, значит, остальные строки (столбцы) не содержат неисправных элементов (т.е. исправны). Следовательно, у элементов этих строк (столбцов) будет исправный параметр. Для исправного элемента, расположенного (при кратности, меньшей m) в неисправной строке (столбце), исправным параметром будет столбец (строка) и обе диагонали.

Теперь рассмотрим случай, когда все неисправности находятся в одной диагонали. Тогда все остальные диагонали, параллельные ей, не содержат неисправных элементов и будут служить исправными параметрами для своих элементов. Для исправного элемента, расположенного (при кратности, меньшей m) в неисправной диагонали, исправным параметром будет и столбец, и строка, и ортогональная диагональ. Теорема доказана.

Выводы

1. Исходя из изложенного в разделах 4 и 5 можно сделать вывод, что с повышением кратности неисправности на единицу следует увеличить размерность проверки на единицу. В качестве нового параметра надо взять какое-то другое подмножество из m элементов. Например, можно составить подмножество из элементов с номерами {1, m+3, 2m+5, 3m +7, …}, аналогичное подмножеству из m элементов главной диагонали {1, m+2, 2m+3, 3m +4, …}, но с бо'льшим (на единицу) смещением вправо в последующей строке. Затем в качестве следующего параметра выбрать подмножества элементов с ещё бо'льшим смещением вправо и т.д.

Как видим, с дальнейшим повышением кратности неисправности геометрическое представление параметров элемента теряет наглядность. Возможно, надо воспользоваться другим математическим аппаратом, но это тема дальнейших исследований.

2. Увеличивая размерность проверки, следует помнить, что выигрыш в контролирующей аппаратуре (т.е. в аппаратуре СА) получится тогда, когда число проверяемых параметров для одного элемента матрицы меньше длины СА k (напомним, k - число разрядов (триггеров) в СА). При контроле элемента по одному параметру (в составе или строки, или столбца, или диагонали) на один элемент тратится один триггер СА; при контроле по четырем параметрам – четыре триггера из разных СА; а при контроле по k параметрам – k триггеров из разных СА, т.е. как и в случае использования в каждой контрольной точке своего одноканального СА. Значит, если число параметров равно или превышает k , то выигрыш в контролирующей аппаратуре не получится. В этом случае, как говорится, «нечего огород городить», а следует применять одноканальные СА.

Заключение

Матричный способ расширен на класс кратных неисправностей. Это сделано за счет повышения размерности проверки матрицы, т.е. увеличения числа подмножеств элементов матрицы, в составе которых каждый элемент проверяется при одноразовой подаче теста. Раньше (в [2]) матрица проверялась по двум параметрам: по строкам и по столбцам. Здесь добавлены проверки по диагоналям (одной и двум). Доказано, что при этом локализуются двух- и трехкратные неисправности (соответственно).

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

Рассмотрены матрицы, у которых количество строк m нечетное. Использование только таких матриц не является сильным ограничением для излагаемого метода. Одним из вариантов локализации неисправностей при четном числе контрольных точек дискретного устройства может быть покрытие множества контрольных точек несколькими нечетными матрицами с разными значениями числа m. Рассмотрение матриц с чётным m – это тема дальнейших исследований.

Литература

1. Ярмолик В.Н. Контроль и диагностика цифровых узлов ЭВМ. Минск: Наука и техника, 1988.

2. Аксенова Г.П. Матричный способ локализации неисправностей в ПЛИС // АиТ. 2013. № 9. С. 119 - 124.

3. Aksenova G.P. A Matrix Method for PLD Failure Localization // Autom. Remote Control. 2013. V. 74. No. 9. P. 1525 – 1529.