(1) _{1 2 3 3}' ₄ = (0), (3.4)

которую можно упорядочить в виде

(1) >₁ > ₂ > ₃ = ₃' > ₄ = (0). (3.5)

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

3.1.2 Установочные последовательности

В первой фазе диагностического эксперимента с автоматом предусматривается установка его в известное начальное состояние. Это достигается использованием установочных или синхронизирующих последовательностей [14, 10]. Методы построения условных и безусловных установочных экспериментов, а также синтез установочных синхронизирующих последовательностей достаточно полно и глубоко изложен в [10]. В этом разделе получена оценка сложности безусловного установочного эксперимента.

Определение 3.5 Входная последовательность X_u называется установочной для автомата (X, Y, Z, , ), если его конечное состояние (Z_i,X_u) может быть однозначно определено по выходной последовательности (Z_i, X_u) для всех Z_i Z.

В соответствии с определением 3.5 если автомат исправен и имеет установочную последовательность, то независимо от начального состояния его можно перевести в определенное состояние. Как показано в [15] любой минимальный автомат имеет установочную последовательность. Правила усечения дерева преемников автомата, приведенные в [10], позволяют построить установочное дерево по его таблице переходов-выходов, из которого определяется множество установочных последовательностей автомата.

Следует отметить, что каждая отличительная последовательность является установочной, в то время как обратное неверно.

3.1.3 Синхронизирующие последовательности

В [10] приведены методы синтеза синхронизирующих последовательностей (СП) по таблице переходов-выходов автомата и по функциональной схеме ДУ. В этом разделе определена верхняя граница длины СП, которая сравнивается с известными оценками [16], анализируется сложность построения СП и условия существования в автомате однородных синхронизирующих последовательностей.

Определение 3.6 Входная последовательность X_S автомата, которая устанавливает его в определенное конечное состояние независимо от состояния выхода и начального состояния, называется синхронизирующей последовательностью.

Если автомат A (X, Y, Z, , ) задан таблицей переходов-выходов, то из определения 3.6 следует, что автомат имеет синхронизирующую последовательность тогда и только тогда, когда существует входная последовательность X_s такая, что (Z_i, X_S) =Z₀; Z_i Z, Z₀ Z. Множество переходов (Z_i, X_S) =Z₀; для Z_i Z, автомата определяет отображение множества его состояний Z в некоторое определенное состояние Z₀ при подаче на автомат входной последовательности X_S, то есть Z Z₀.

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

Так как синхронизирующая последовательность не связана с анализом выходной последовательности автомата, то функции выходов автомата не рассматриваются при построении синхронизирующего дерева. Вершины синхронизирующего дерева отмечаются - множествами, коорые являются X_i-преемниками ( X_i X) состояний, входящих в - множества предшествующих вершин. Вершина ранга j - синхронизирующего дерева является висячей, если:

а) вершина отмечается группой - множеств, которая соответствует группе - множеств какой-либо вершины ранга меньше j;

б) вершина j-го ранга отмечена одним простым - множеством.

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

В качестве иллюстрации предлагается рассмотреть автомат А-2, заданный таблицей переходов-выходов (таблица 3.2). Синхронизирующее дерево (рисунок 3.2) является синхронизирующей последовательностью, которая устанавливает А-2 в состояние 4 независимо от начального состояния.

Таблица 3.2 - Автомат А-2

Z (t)	Z (t + 1), (t)
	X=0	X=1
1	4, 1	2, 0
2	4, 1	3, 0
3	1, 0	4, 0
4	2, 0	1, 0

Рисунок 3.2 - Синхронизирующее дерево автомата А-2

3.1.4 Построение проверяющих последовательностей

Методы решения задач проверки ДУ, использующие явные и неявные модели ДУ, рассмотрены в [14, 10]. В качестве модели неисправности принята модель неисправности F₁ и предполагается, что автомат является минимальным, сильносвязным, имеет отличительную последовательность и не меняет свое поведение в процессе эксперимента.

Для модели неисправности проверяющая последовательность состоит из 3-х частей или фаз:

а) установка в исходное начальное состояние;

б) проверка (идентификация) состояний;

в) проверка правильности переходов.

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

Фаза идентификации состояний заключается в попеременном приложении отличительной X₀ и переводящих последовательностей X_п, определении реакции автомата на X₀ для каждого начального состояния и определении X₀-преемника каждого состояния. Фиксированная последовательность, идентифицирующая состояния автомата содержит n различных выходных последовательностей для всех состояний.

В третьей фазе эксперимента проверяются все m x n переходов автомата, каждое состояние до перехода и после перехода идентифицируется X₀. Сокращение длины проверяющей последовательности достигается за счет совмещения второй и третьей фазы эксперимента [14].

Другой путь сокращения длины проверяющей последовательности заключается в использовании однородных отличительных последовательностей.

Рассмотрим автомат А-3, заданный таблицей переходов-выходов (таблица 3.3). Отличительное и синхронизирующее деревья автомата А-3 приведены на рисунке 3.3a и рисунке 3.3б соответственно. Автомат имеет синхронизирующую последовательность X_s = 11 и две отличительные последовательности X₀₁ = 01 и X₀₂ = 00.

Построим последовательность, проверяющую состояния автомата, с использованием вначале X₀₁=01, а затем X₀₂=00.

Проверяющая последовательность начинается с X_s = 11, которая устанавливает автомат в начальное состояние 1. Затем X₀₁=01 используется для идентификации состояний. Приложение X₀₁ к автомату, находящемуся в состоянии 1, вызывает появление на выходе последовательности Y = 01. Прикладывая X₀₁ повторно, проверяется 01 приемник начального состояния автомата.

Таблица 3.3 - Автомат А-3

Z (t)	Z (t + 1), (t)
	X=0	X=1
1	2, 0	1, 1
2	3, 0	1, 1
3	1, 1	2, 0

С помощью переводящей последовательности X_п= переводим автомат из состояния 1 в 2. Прикладывая X₀₁=1, получаем на выходе Y=00 и конечное состояние 2. Это конечное состояние проверяется X₀₁=01 правильной реакцией автомата Y=00. Затем, автомат из состояния 2 с помощью X_п=0/0 переводится в 3, прикладывается X₀₁=01 проверяется состояние 3 по выходной последовательности Y=11.

a) Отличительное дерево автомата А-3

б) Синхронизирующее дерево автомата А-3

Рисунок 3.3 - Отличительное и синхронизирующие деревья автомата А-3

Рассмотренная выше фаза идентификации состояний автомата А-3 представляется следующей последовательностью

X 11 01 01 0 01 01 0 01 01

Z 1 1 1 2 2 2 3 1 1 (3.6)

Y 01 01 0 00 00 0 11 01

Если автомат реагирует правильно на приложение входной последовательности, проверяющей правильность состояний автомата, то эта последовательность одновременно проверяет правильность переходов (1,0) =2 и (2,0) =3, которые используются для построения второй фазы эксперимента. Кроме того, анализ последовательности X / Z показывает, что в фазе проверки состояний автомата дополнительно проверяются переходы (2,1) = 1, и (3,1) =2, которые подчеркнуты в последовательности

X 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1

Z 1 2__1 2_1 2 3_2 3__2 3 1 1 2 1 (3.7)

Y 0 1 0 1 0 0 0 0 0 0 1 1 0 1

Анализ последовательности (3.7), проверяющей состояния автомата А-3 показывает, что в заключительной третьей фазе эксперимента проверки правильности переходов остается проверить лишь два перехода: (1,1) =1 и (3,0) =1. Так как после фазы идентификации состояний А-3 находится в состоянии 1, то для проверки перехода (1,1) = 1 необходимо приложить последовательность 101 и проверить выходную последовательность 101. Перевести автомат с помощью Х_п = из 1 в состояние 3, осуществить (3,0) и, приложив отличительную последовательность X₀₁=01, проверить правильность перехода (3,0).

Полная проверяющая последовательность для А-3, включающая все три фазы эксперимента и состоящая из 24 входных символов представляется в виде:

X 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1

Z 1 2 1 2 1 2 3 2 3 2 3 1 1 2 1 1 2 1 2 3 1 2 1 (3.8)

Y 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1

Так как для автомата А-3 существует две отличительных последовательности, то эксперимент, построенный выше, не является единственным. Нетрудно убедиться, что более короткий эксперимент получается при использовании однородной отличительной последовательности X₀₂=00. Это связано с тем, что X₀₂ - преемники не совпадают с начальными состояниями. В этом случае полный проверяющий эксперимент для автомата А-3 представляется в виде:

X 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0

Z 1 2 3 1 2 3 1 2 3 2 3 1 1 2 3 2 1 2 3 (3.9)

Y 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0

Легко убедиться в том, что использование однородной отличительной последовательности сокращает длину эксперимента на 4 символа.

В эксперименте с автоматом, имеющим отличительные последовательности, считается, что в фазе идентификации состояний автомата проверяются все n состояний, если на выходе автомата появляется n различных последовательностей, как реакция на некоторую фиксированную входную последовательность [17].

В общем случае использование фиксированной входной последовательности в фазе идентификации состояний автомата является лишь необходимым условием проверки всех его состояний.

3.1.5 Отличительные последовательности в ОС

На функциональном уровне описания ячейки однородной одномерной сети без наблюдаемых выходов Х' будем рассматривать ее таблицу истинности как таблица переходов - выходов автомата Мура, задаваемого тройкой (X,Y,), у которого функции переходов и выходов совпадают, то есть

(Z_i,X_a) = (Z_i,X_a) =Z'_j,Z_i, Z_jZ, X_aX, (3.10)

Пусть Z={Z₁,…Z_i,…Z_n} - множество состояний автоматной модели ячейки сети. Будем обозначать Z [Z_i] = { Z₁,… Z_i-1, Z_i+1,…Z_n } = { Z - Z_i } - множество состояний ячейки сети, из которого исключен элемент Z_i. Как было показано на примере одномерной сети (рисунок 1.2), при синтезе проверяющих тестов сложность решения задачи анализа полноты полученных тестов и их расширения связана с наличием в автоматной модели ячейки сети пар X - совместимых состояний. Из таблицы переходов ячейки легко можно определить множества X_i - совместимых состояний для каждого входного символа X_i X, i= . Образуем множество Z_C = …элементы, которого представляют собой состояния, X - совместимые для всех входных символов множества X.

Определение 3.7 Пусть ячейка одномерной ОС без наблюдаемых выходов X' представлена моделью автомата Мура (Х,Z,), в котором X - преемником состояния Z_iZ является состояние Z_k, не обязательно отличное от Z_i. Входной символ X X будем называть отличительным символом состояния Z_i тогда и только тогда, когда Z_k не является X - преемником для множества Z [Z_i] начальных состояний автомата и Z_k Z_C.

Если столбец X таблицы переходов ячейки сети содержит пару неразличимых состояний (Z_а, Z_b), то есть (Z_a, X) = Z_k, (Z_b,X) = Z_k состояния (Z_а, Z_b) неразличимы для входного символа Х. В общем случае может быть две альтернативы. Пара состояний (Z_а, Z_b) различается, по меньшей мере, одним входным символом Х_, либо пара (Z_а, Z_b) - X_i совместима для каждого входного символа X_i X. В первом случае состояния Z_а и Z_b можно идентифицировать только приложением к входу проверяемой ячейки входного символа Х_. Во втором случае для различения состояний (Z_а, Z_b) можно воспользоваться множеством характеристических входных символов подобно тому, как в [1] использовались характеристические последовательности при построении диагностических экспериментов для автоматов, не имеющих отличительных последовательностей.

Определение 3.8 Пусть ячейка одномерной сети представлена моделью автомата Мура (Х, Z, ). Множество входных символов X_c={ X₁, X₂, …, X_r } называется множеством входных характеристических символов тогда и только тогда, когда для любой пары состояний (Z_а, Z_b) Z автомата

(Z_a,X₁) (Z_a,X₂) … (Z_a,X_r) (Z_b,X₁) (Z_b,X₂) … (Z_b,X_r) (3.11)

Определение 3.9 Пусть Z'={ Z₁, Z₂, Z₃, … Z_r } подмножество состояний минимального автомата А. Множество Х_с={ X₁, X₂, X₃, … X_p }, будем называть множеством характеристических последовательностей, если для каждого начального состояния Z_iZ', реакция на Х_с различна, то есть

(Z_,X₁) (Z_i,X₂) … (Z_i,X_p) (Z_j,X₁) (Z_j,X₂) … (Z_j,X_p) Z_i Z_j, ₍3.12)

для Z_i, Z_j Z', а исключение любой последовательности из множества Х_с не позволяет различить, по меньшей мере, одно состояние Z_iZ'.

Множество отличительных и характеристических символов может быть найдено из характеристического дерева автомата ячейки сети, которое строится по правилам, приведенным в разделе 1.5 [1]. На рисунке 3.4 приведено характеристическое дерево сети (рисунок 1.2), из которого следует, что символ X₁=1 является отличительным для множества состояний {Z₀, Z₁, Z₂, Z₃} символ X₀=0 для состояний Z₂ и Z₃. Пара состояний {Z₀, Z₁} является X₀-совместимой.

Рисунок 3.4 - Характеристическое дерево ячейки сети

Характеристическое дерево ячейки сети, представленной автоматной диаграммой в таблице 3.4, приведено на рисунке 3.5, из которого можно найти множество отличительных и характеристических символов.

Так как произведение разбиений = () и = () равно (0), то множество Х_c={ X₁, X₃ } является множеством входных характеристических символов. Простые - множества для каждой вершины характеристического дерева определяют множества состояний, для которых метка вершины дерева является отличительным входным символом.

Исключения составляют лишь те простые - множества, которые являются состояниями преемниками, принадлежащими множеству Z_c то есть множеству состояний, неразличимых для всех входных символов.

Например, из характеристического дерева ячейки сети (рисунок 3.5, таблица 3.4) следует, что

= {Z₃, Z₄}; = {Z₁, Z₃, Z₄}; = {Z₁, Z₃}, (3.13)

Таблица 3.4 - Таблица переходов выходов ячейки сети

Z (t)	Z (t+1)
	X1	X2	X3
Z1	Z2	Z1	Z3
Z2	Z3	Z3	Z4
Z3	Z4	Z1	Z3
Z4	Z4	Z1	Z1

Рисунок 3.5 - Характеристическое дерево ячейки сети

Множества Х - совместимых состояний ячейки позволяют определить множество Z_c в виде:

Z_c= ={Z₃}, (3.14)

Определив множество Z_c, из характеристического дерева можно легко найти множество отличительных символов и состояний ячейки, которые различаются этими символами в соответствии с определением 3.7 Для рассматриваемого примера состояние Z₁, различается символом X₁, состояния Z₂ и Z₄ - символом X₃.

Определение 3.10 Пусть состояние Z_j правого выхода ячейки C (k) однородной одномерной сети транспортируется на крайний правый выход сети приложением входного набора X_т к входам ячеек C (k+1), C (k+2),…. C (p). Входной набор X_т является проверяющим тестом, идентифицирующим состояние Z_j ячейки C (k), если состояние наблюдаемых выходов сети различно, когда Z_j и каждое из состояний множества Z [Z_j], приложено к левому входу ячейки C (k+1), то есть

(Z_j,X_т) (Z_i,X_т), Z_iZ [Z_j]. (3.15)

Если для каждого состояния ячейки сети существует проверяющий входной набор X_т, то проверяющий тест всей однородной сети можно построить путем проверки правильности всех m x n переходов автоматной модели каждой ячейки сети, используя проверяющие тестовые наборы X_т для идентификации правильности переходов.

Нижеследующая теорема определяет необходимые и достаточные условия существования в однородной сети проверяющих тестовых наборов X_т.

Теорема 3.1 Пусть правый выход ячейки C (k) одномерной однородной сети находится в состоянии Z_j и к верхним входам ячеек C (k+1), C (k+2),…. C (p) приложен входной набор X_k={ X_k+1, X_k+2,…,X_p }, вызывающий последовательность переходов состояний ячеек сети в виде

Z_j Z_k+1Z_k+2… Z_p-1Z_p, (3.16)

где состояние слева от входного символа XX_k, = (k+1) (k+2) …. является предшествующим, а состояние справа от X - последующим. Если существует последовательность состояний ячеек C (k+1),C (k+2), …. C (p), порождаемая приложением входного наборa X_k, в котором каждый символ XX_k является отличительным символом предшествующего состояния, то последовательность этих символов образует проверяющий тестовый набор состояния Z_j, ячейки C (k) сети.

Как будет показано ниже, задача построения проверяющих входных наборов для заданной одномерной ОС значительно упрощается, если существуют циклические переводящие последовательности, образованные от отличительных входных символов. При построении диагностических экспериментов (ДЭ) по автоматным моделям ДУ возникает задача нахождения множества переводящих последовательностей T (Z_i,Z_j), с помощью которых ДУ из начального состояния Z_i переводится в состояние Z_j. Известно, что эта задача тривиальна, если ДУ задано графом или таблицей переходов [10]. Как показано в [10], переводящая последовательность T (Z_i,Z_j) определяется путем построения фрагментов дерева преемников состояния Z_i, содержащего путь или множество путей, оканчивающихся состоянием Z_j.

При построении проверяющих тестов для одномерных ОС возникает аналогичная задача нахождения множества переводящих последовательностей по автоматной модели ячейки сети. Тестопригодность сети, число ячеек которой превышает число состояний автоматной модели ячейки сети, определяется наличием в ней циклических переводящих последовательностей T (Z_i,Z_i), которые так же, как и любые другие переводящие последовательности, можно легко найти из автоматной модели ячейки сети. В соответствии с теоремой 3.1 циклическая переводящая последовательность T (Z_i,Z_i), которая образована из отличительных входных символов, является одновременно проверяющим тестовым набором, который транспортирует состояние проверяемой ячейки сети на наблюдаемый выход.

Определение 3.11 Циклическую переводящую последовательность, образованную из входных отличительных символов предшествующих состояний ячеек сети, будем называть циклической отличительной последовательностью (ЦОП).

Рассмотрим класс однородных одномерных сетей без наблюдаемых выходов X', состоящих из p ячеек, каждая из которых имеет m входных символов, n состояний и каждое состояние имеет, по меньшей мере, один отличительный символ. Для сетей такого типа справедливо следующее утверждение.

Теорема 3.2 Если в ячейке ОС с n состояниями, каждое состояние имеет, по крайней мере, один отличительный символ, то для такой сети существует, по меньшей мере, одна циклическая отличительная последовательность.

В качестве примера рассматривается автомат, заданный в таблице 3.5 Из характеристического дерева автомата (рисунок 3.6) находим отличительные символы состояний:

Z₁ - X_2; Z₂ - X_2; Z₃ - X_3; Z₄ - X_{1 (}3.17)

Автомат удовлетворяет условию теоремы 3.1, следовательно, он имеет циклическую отличительную последовательность. Последовательность переходов по отличительным символам Z₁Z₂Z₃Z₄Z₄ завершается циклом Z₄Z₄.

Таблица 3.5 - Таблица переходов-выходов ячейки

Z (t)	Z (t+1)
	X1	X2	X3
Z1	Z1	Z2	Z2
Z2	Z1	Z3	Z2
Z3	Z1	Z4	Z4
Z4	Z4	Z4	Z2

Рисунок 3.6 - Характеристическое дерево ячейки

Аналогично, ЦОП имеется в автомате, заданном в таблице 1.2 Из характеристического дерева (рисунок 3.4) находим:

Z_{1 -} X_1; Z₂ - X₂; Z₃ - X_3; Z₄ - X₁; (3.18)

Последовательность переходов Z₁Z₃Z₀Z₂Z₁ является циклической отличительной последовательностью.

Теорема 3.2 определяет необходимые условия существования в ячейке ОС циклической отличительной последовательности. В следующем подразделе будет показано, что существование ЦОП для заданной однородной сети упрощает процедуру построения проверяющего эксперимента для этой сети также, как и наличие отличительных последовательностей для автоматных моделей произвольных ДУ с элементами памяти. Такие ОС в дальнейшем будем называть легко тестируемыми.

Выводы:

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

Если для проверки цифровой схемы применяется детерминированный подход, сложность состоит в том, что детерминированный набор тестов должен быть встроен в схеме, то есть схема должна иметь дополнительные аппаратные средства, которые в режиме самотестирования выдают тестовые последовательности.

Схема самотестирования может быть реализована двумя различными способами:

а) тестовые наборы могут быть или записаны на кристалле с помощью ПЗУ (которая должна также содержать правильные выходные последовательности для сравнения с реальными выходными последовательностями);

б) тестовые наборы также могут быть сгенерированы, с помощью специальных генераторов, предназначенных для этой задачи, в данном проекте рассматривается реализация на КА;

ПЗУ можно использовать, когда размер тестовых наборов невелик. С другой стороны, наличие генератора тестовых наборов, в сильной степени зависит от регулярности тестовых наборов.

Для схем умножителей, использование ПЗУ может быть оправдано, когда умножитель модифицируется в соответствии с требованиями C-тестируемости. Основной недостаток этого подхода заключается в том, что модификация схемы в соответствии с требованиями тестопригодного проектирования приводит к увеличению занимаемой основной схемой умножителя площади кристалла, введению дополнительных входов-выходов, и снижению производительности [18-21].

Никакие модификации тестопригодного проектирования не могут применяться схеме умножителя, т.к. они вызывают существенное снижение производительности.

Если не модифицировать схему умножителя, то для тестирования требуется набор тестов линейного размера. Например, в [20], был предложен линейный набор тестов размера 3N + 60, где N - общая длина обоих операндов умножителя. В этом случае, размер тестового набора намного больший чем при С-тестируемости, так что затраты на хранение тестовых наборов в ПЗУ - предельно высокие. Эти затраты могли бы быть уменьшены, если бы нашелся такой генератор тестовых наборов, который генерирует нужные образцы теста. К сожалению, наборы тестов, предложенные в [18 - 21] неправильные и не могут быть эффективно произведены с использованием небольших аппаратурных затрат. Также, этот подход зависит от размерности умножителя, потому что размер набора тестов увеличивается с размерностью умножителя.

3.2 Псевдослучайное тестовое диагностирование

Согласно псевдослучайному подходу, на схему подаются псевдослучайные тестовые наборы, и эффективность метода вычисляется, используя моделирование неисправности. Встроенное самотестирование реализованное по псевдослучайному подходу (рисунок 3.8), имеет важное преимущество, с точки зрения небольших аппаратурных затрат, так как обычные регистры могут легко модифицироваться в сдвиговые регистры с линейной обратной связью (СРЛОС), представленные на рисунках 3.9а и 3.9б, которые формируют тестовые наборы для встроенного самотестирования и оценку выходных данных, соответственно.

ГПП - генератор псевдослучайной последовательности

Рисунок 3.8 - Встроенное самотестирование по псевдослучайному подходу

а)

б)

Рисунок 3.9 - Сдвиговые регистры с линейной обратной связью

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

Рисунок 3.10 - Сигнатурный анализатор

Недостаток применения псевдослучайного подхода к умножителю со встроенным самотестированием состоит в том, что он не может обеспечивать гарантируемое покрытие неисправностей независящее от размерности умножителя. Чтобы достигнуть высокого покрытия неисправностей для умножителя с другой длиной операнда, должен быть найден новый генератор псевдослучайных тестовых наборов. Эффективность каждого псевдослучайного генератора образцов должна быть вычислена путем моделирования неисправности.

4. Модули сигнатурного мониторинга на сетях клеточных автоматов

Схемы встроенного самотестирования (СВС) широко используются в дискретных устройствах (ДУ), построенных на одном кристалле. Структура ДУ с СВС показана на рис.4.1, где тестируемая схема (ТС) - комбинационная схема с наблюдаемыми входами и выходами.

Рисунок 4.1 - Структура ДУ с встроенным самотестированием

Для достижения соответствующего качества тестирования, необходимо выполнить три условия:

1. Минимизировать аппаратные затраты на построение генератора;

2. Минимизировать время тестирования;

3. Максимизировать покрытие неисправностей.

В настоящее время существуют следующие способы генерирования тестовых векторов в СВС: исчерпывающее тестирование (счетчик генерирует все 2ⁿ векторов, где n - количество входов тестируемой схемы), псевдослучайное тестирование (на основе сдвиговых регистров с линейными и нелинейными обратными связями, сетей клеточных автоматов), детерминированное тестирование (запись тестовых векторов в ПЗУ и формирование адресов на счетчиках) [6].

Большое распространение получают генераторы тестов на основе СКА. Главное достоинство таких сетей по сравнению с другими схемами - регулярность структуры и локальность взаимосвязей между клеточными автоматами (КА), что делает их привлекательными при реализации ДУ на программируемых логических интегральных схемах типа CPLD, FPGA. Важной характеристикой СКА является более высокая частота генерации тестов.

4.1 Метод генерирования субпоследовательностей

Исходным данным для работы алгоритма является детерминированное множество двоичных векторов М, в виде произвольной последовательности

где v_i - i-й вектор M, m - количество векторов в M.

В процессе работы алгоритма, исходное множество М сортируется определенным образом, при этом М, как правило, разбивается на несколько субпоследовательностей S_l, каждая из которых реализуется генератором на СКА. Необходимо, чтобы эти субпоследовательности удовлетворяли следующим условиям:

1) Каждая субпоследовательность S_l должна быть детерминированной;

2) ;

3) Длина субпоследовательностей S_{l -} ;

4) Последний вектор S_l берется в качестве первого S_l+1.

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

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

Упорядочивание исходного множества в субпоследовательности

Первый этап состоит из таких шагов:

1) Все векторы из исходного множества пронумеровываются.

2) Путём подбора отыскивается начальный вектор v_н.

3) Текущая субпоследовательность S_l= [], l=1.

4) Присоединить начальный вектор к S_l (S_l (1) =v_н).

5) Если в М не существует непомеченного вектора v_i, такого, чтобы для субпоследовательности S_l+ v_i выполнялось (2.2), перейти к пункту 8.

6) S_l= v_i.

7) Пометить v_i как использованный.

8) Если в М все векторы помечены, перейти к пункту 12.

9) l=l+1;

10) S_l (1) =v_i;

11) Перейти к пункту 5;

12) Конец.

Знак "+" в пунктах 5 и 6 означает операцию присоединения вектора v к субпоследовательности S_l.

4.2 Алгоритмы отыскания субпоследовательностей

4.2.1 Алгоритм основной программы

На рисунке 4.2 показана блок-схема алгоритма первого этапа, реализованного в системе Delphi.

В данной схеме переменные М, List2 - объектного типа. Они содержат в себе список строк, а так же свойства и методы, предназначенные для работы со списком. Переменная М содержит исходный список векторов, а List2 предназначен для хранения полученных субпоследовательностей. Переменные i, j, L - целочисленного типа, i используется как счетчик, в j хранится индекс начального вектора, L используется для сравнения длинны субпоследовательности, полученной с различными начальными векторами.

В алгоритме используется подпрограмма GetSubSeq, с тремя параметрами. Первый параметр представляет собой список и должен содержать исходный список векторов. Второй параметр - это строка, содержащая первый вектор искомой субпоследовательности. Третий параметр - список к которому будет добавлена найденная субпоследовательность. Векторы, вошедшие в субпоследовательность удаляются из исходного списка.

Операторы с 4 по 8 составляют тело цикла, в котором отыскивается наилучший начальный вектор для первой субпоследовательности. Критерий качества этого вектора - максимально возможная длина первой субпоследовательности. В блоке 4 запоминается i-й вектор из исходного списка в переменную Sample, удаляется i-й вектор из исходного списка, очищается список, предназначенный для сохранения результата. В переменной L сохраняется длина субпоследовательности, полученная для предыдущего начального вектора. На первом проходе цикла L = 0. Оператор 6 выполняет переход по ветви "Да", если длина субпоследовательности для текущего начального вектора больше, чем для предыдущего, в этом случае запоминается улучшенный результат (блок 7). В результате в переменной Sample2 останется наилучший начальный вектор для первой субпоследовательности.

В блоке 9 выполняется поиск индекса вектора Sample2 в исходном множестве, а затем этот индекс удаляется. Это нужно для того, чтобы данный вектор не повторился дважды в первой субпоследовательности. После выполнения блока10, в List2 запоминается первая субпоследовательность. Далее, построение остальных субпоследовательностей происходит в цикле, условием выхода из которого (блок 11) является отсутствие неиспользованных векторов в исходном множестве.

4.2.2 Алгоритмы подпрограмм

Основой алгоритма, приведенного в п.4.2.1 является подпрограмма GetSubSeq. Ее блок-схема представлена на рис.4.3 Переменная М содержит исходное множество двоичных векторов. Sample - содержит начальный вектор, Lst2 - список, к которому будет добавлена полученная субпоследовательность. List3 и List4 - два вспомогательных списка, которые создаются в операторе 2 и существуют все время выполнения подпрограммы. List3, после выполнения подпрограммы, будет содержать искомую субпоследовательность, List4 предназначен для хранения результатов выполнения подпрограммы GetByMask.

В результате выполнения блока 2, в List3 находится начальный вектор. В блоке 3 вызывается подпрограмма GetMask, которая на основе списка List3 получает маску, используемую для нахождения следующего вектора субпоследовательности (удовлетворяющего выражению (2.2)). Найденная маска помещается в переменную Mask.

В блоке 4 вызывается подпрограмма GetByMask, которой в качестве входных параметров передаются М и Mask. Данная подпрограмма отыскивает все векторы в М, отвечающие заданной маске, и сохраняет их в список List4.

В блоке 5 используется свойство Count переменной List4. Оно содержит количество векторов, которое содержит список. Если List4. Count = 0, т.е. не найдено ни одного вектора, то на этом нахождение текущей субпоследовательности завершается. Найденная субпоследовательность, которая содержится в List3, присоединяется к списку Lst2 (блок 8). В этом же блоке происходит освобождение памяти, занимаемой объектами List3 и List4.

Если же в результате выполнения блока 4 был найден хотя бы один вектор, то нахождение субпоследовательности продолжается в цикле. Подпрограмма SelectVector, вызываемая в блоке 6, позволяет выбрать наиболее подходящий из возможных векторов (из List4), и сохраняет его в переменной V, после чего V присоединяется к List3 (блок 7). В этом же блоке все неиспользованные векторы возвращаются в исходный список М. Далее выполняется следующая итерация цикла.

Далее рассмотрим алгоритм функционирования подпрограммы GetMask. Исходными данными для работы является List - это список, который передается в подпрограмму из вызвавшей программы, на его основе строится маска. Результат работы подпрограммы возвращается через переменную Result. Строковые переменные Subl и Sub2 используются для выделения и сравнения частей векторов. На i-м шаге внешнего цикла Subl содержит подстроку, состоящую из трех элементов последнего вектора из списка List, стоящих в позициях i-1, i, i+l Sub2 содержит те же три элемента j-гo вектора:

Subl = List [List. Count-ll [i-1] + List [List. Count-1] [i] + List [List. Count - l] [i+l];

Sub2 = List [j] [i-1] + List [j] [i] + List [j] [i+1],

где '+' обозначает конкатенацию строк.

Если в подпрограмму передан пустой список, это вызовет ошибку, для исключения такой ситуации выполняется проверка, если возникла ошибочная ситуация, подпрограмма посылает 'сообщение об ошибке' вызвавшей программе и завершает работу. Символ '*' в маске означает незафиксированный разряд, т.е. при проверке соответствия вектора маске (в подпрограмме GetByMask) такой разряд не сравнивается.

На рис.4.4 приведена блок-схема подпрограммы GetByMask, которая по заданной маске Mask, извлекает векторы из списка L1 и добавляет эти векторы в список L2, который и является результатом ее выполнения. Переменная j - это счетчик строк, a i - позиций (разрядов). При достижении j значения, соответствующего количеству строк в L1, подпрограмма завершается (блок 4). При достижении значения i>n (т.е. пройдена вся строка), текущий вектор заносится в список L2, происходит переход к следующему вектору и переустановка i. Соответствие вектора маске проверяется в блоке 6 поразрядно, при первом несоответствии происходит переход к следующему вектору и переустановка i (блоки 9 и 8 соответственно).

Подпрограмма SelectVector, блок-схема алгоритма которой приведена на рис.4.5, необходима для того, чтобы выбрать наиболее подходящий из всех векторов, которые могут быть присоединены к субпоследовательности на данном шаге. Переменные LI, L2 - списки, содержащие строящуюся субпоследовательность и векторы, которые могут быть присоединены к ней на данном шаге соответственно; переменная V содержит выбранный вектор после завершения работы подпрограммы. Переменная i - счетчик строк, j - содержит значение номера выбранного вектора в L2. Здесь также используется функция GetFreeColCount, которая подсчитывает количество символов '*' в аргументе.

4.2.3 Результаты работы основного алгоритма

Исходными данными для работы алгоритма являлась тестовая последовательность, которая в результате выполнения программы должна быть преобразована в несколько субпоследовательностей, в совокупности перекрывающие исходную. Исходные данные:

T = {11111111; 10100101; 01110000; 00111110; 01011100; 00000110; 00011001; 11100011; 11010010; 10001101; 11110000; 00001111; 00010000; 00001101; 11111010; 00101111}.

В результате работы алгоритма получены следующие субпоследовательности:

S1	S2	S3	S4
11111010 10100101 01011100 00001111 01110000 00101111 00010000	00010000 11111111 10001101 00000110 11010010 11111110 10001110	10001110 00011001 11100011 11110000 11111111 11111010 11110111	11110111 00111110 00001101 01111111 11101110 00111101 00001111

4.2.4 Правила настроек КА

Этот этап связан с отысканием правил функционирования клеточных автоматов генерирующей сети по известной субпоследовательности. Номера правил вычисляются для каждой ячейки СКА по ее диаграмме состояний.

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

S1 - 4, 33, 128, 50, 146, 101, 17, 17

S2 - 9, 65, 34, 5, 144, 195, 101, 65

S3 - 9, 129, 193, 212, 152, 33, 135, 21

S4 - 2, 9, 193, 66, 168, 200, 160, 20

5. Программа моделирования ска на языке Delphi

5.1 Исходные требования к программе моделирования

Исходными данными для работы программы являются:

1. Количество сегментов сети клеточных автоматов n.

2. Начальные значения каждой клетки.

3. Количество шагов эволюции клеточного автомата k.

4. Правило функционирования для каждой клетки, заданное в виде минимальной дизъюнктивной нормальной форм

Результатом работы программы должны быть значения каждого КА на каждом шаге эволюции в следующем виде:

Программа должна работать в среде Windows 98/Me/2000/XP и иметь визуализированный интерактивный интерфейс.

5.2 Алгоритм реализации программы

На рисунке 5.1 изображена блок-схема основного алгоритма программы.

Текст программы и ее внешний вид, описание элементов управления представлены в ПРИЛОЖЕНИИ А и ПРИЛОЖЕНИИ Б соответственно.

Блок 1. Осуществляется ввод исходных данных, n - количество клеток, k - количество шагов эволюции.

Блок 2. Устанавливаются начальные значения счётчиков i, j. В массиве sp [j, i] хранятся значения клеток, полученные на предыдущем шаге, в массиве s [j, i] - текущие значения. До начала работы этого алгоритма в этом массив помещаются начальные значения.

Блок 3. Проверяется условие прохода всех шагов эволюции системы.

Блок 4. Проверяется условие прохода всех клеток сети.

Блок 5. Производится вычисление нового значения текущей клетки с последующим занесением его в массив s [j, i] по отдельному алгоритму с учётом значений массива sp [j, i].

Блок 6. Увеличение счётчика на 1. В массив sp [j, i] заносятся текущие значения.

Блок 7. Вывод нового значения текущей клетки на экран.

Блок 8. Увеличение счётчика цикла

5.3 Результаты моделирования сети клеточных автоматов

Исходные данные:

1. n=8

2. k=7

Были произведены 4 эксперимента со следующими настройками КА

1.4, 33, 128, 50, 146, 101, 17, 17

2.9, 65, 34, 5, 144, 195, 101, 65

3.9, 129, 193, 212, 152, 33, 135, 21

4.2, 9, 193, 66, 168, 200, 160, 20

Полученные результаты:

S1	S2	S3	S4
11111010 10100101 01011100 00001111 01110000 00101111 00010000	00010000 11111111 10001101 00000110 11010010 11111110 10001110	10001110 00011001 11100011 11110000 11111111 11111010 11110111	11110111 00111110 00001101 01111111 11101110 00111101 00001111

6. Экономическая часть

6.1 Технико-экономическое обоснование дипломной работы

В данном разделе экономической части выполняются маркетинговые исследования для дипломной работы на тему "Модули сигнатурного мониторинга на клеточных автоматах" конкретного изделия.