Разработка методов синтеза и логического проектирования модулей сигнатурного мониторинга

Шаг 10: Уменьшить на единицу. Если , то определить функцию крайнего левого элемента сети. Перейти к шагу 12. Если , перейти к шагу 2.

Шаг 11: Заданная функция нереализуема бесповторной сетью Майтра.

Шаг 12: Конец алгоритма.

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

3.3 Синтез ГПТ на сдвиговых регистрах с нелинейной обратной связью

По аналогии со структурой ГПТ на СРЛОС/СР (рис.2.4а) генератор тестов на сдвиговых регистрах с нелинейной обратной связью (СРНОС) для псевдоисчерпывающего тестирования (n,m,k) схем имеет структуру, представленную на рис. 3.7. Первые k разрядов генератора на СР с нелинейной функцией обратной связи формируют различных двоичных векторов, которые через k тактов сдвигаются в цепи СР, определяя на каждом такте значения разрядов в СР. Так как длина цикла СРНОС равна , то максимальная размерность цепи генератора на СРНОС/СР . Условие формирования в разрядах СР различных двоичных k - мерных векторов определяется нижеследующим утверждением.

Рис.3.7. Структура ГПТ на СРНОС.

Теорема 3.2. Пусть задана схема ГПТ на СРНОС/СР длиной в n разрядов, в котором разряды формируют полный цикл длиной различных двоичных векторов с помощью функций нелинейной ОС , порождающей гамильтонов цикл в k - разрядном СР. Если начальные состояния всех n разрядов ГПТ совпадают со значениями функции , сдвинутых на тактов, то на выходах любых k смежных разрядов ГПТ формируются различных тестовых набора за тактовых сдвигов регистра.

Доказательство.Так как на вход первого триггера СРНОС поступает двоичная последовательность, формирующая гамильтонов цикл в k - разрядном СР, то за тактов на выходе сформируется функция ОС , которая на выходе будет сдвинута на k тактов, на - на тактов и т.д., а на выходе - на тактов. Следовательно, формирование на любых k смежных выходах , всех тестовых наборов за тактов возможно, если начальное состояние разряда СРНОС/СР будет эквивалентно значению функции на такте, что обеспечит генерацию гамильтоновых циклов на любых k смежных разрядах СР цепи . Теорема доказана.

Для иллюстрации условий установки начальных состояний ГПТ на СРНОС/СР в соответствии с Теоремой 3.2 рассмотрим пример ГПТ для и (рис.3.8).

Нелинейная обратная связь формируется схемой, реализующей функцию ; которая формирует Гамильтонов цикл в разрядах СР с начальной установкой . Начальная установка соответствует 0 - му такту функционирования генератора. Как видно из рис.3.8а, любые смежные три разряда генератора формируют 8 различных 3 - мерных векторов, при начальной установке их в соответствии с условиями Теоремы 3.2, что иллюстрируется на рис.3.8б.

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

Следствие 3.1. Разряды СРНОС/СР являются смежными и образуют полный Гамильтонов цикл в k - разрядном СР.

Это следствие имеет важное практическое значение, если стоит задача синтеза ГПТ для схем небольшой размерности . Для выше рассмотренного примера ГПТ на рис. 3.8 с параметрами и можно исключить схему нелинейной обратной связи, заменяя ее обратной связью с выхода разряда на вход разряда .

Следствие 3.2. Циркулирующий сдвиговый регистр с числом разрядов , в котором путем начальной установки записана последовательность, порождающая Гамильтонов цикл в k - разрядном СР, генерирует за тактов различные k - мерные векторы в любых k смежных разрядах СР.

Таким образом, ГПТ на рис.3.8 можно упростить и представить в виде схемы 3.9, в которой гамильтоновы циклы в k смежных разрядах порождаются соответствующей начальной установкой разрядов циркулирующего сдвигового регистра.

а) в)

Рис.3.8 Функциональная схема ГПТ на СРНОС/СР для , (а) и формирование начальной установки триггеров СР (в)

Рис.3.9 Схема ГПТ, эквивалентного по поведению схеме рис. 3.8

В общем случае если , схема ГПТ на СРНОС/СР в соответствии с Теоремой 3.2 генерирует k - мерные тривиальные тестовые наборы, подаваемые на n входов проверяемого устройства.

Определение 3.2. Последовательность k - мерных двоичных векторов длиной , в которой все векторы различны, будем называть счетчиковой последовательностью.

Пусть - выходы разрядов СРНОС/СР, а - входы проверяемой схемы.

Выходы любых k смежных разрядов ГПТ, представляемых подмножеством можно рассматривать как выходы k - разрядного счетчика, который формирует различных тестовых векторов. Так как все выходы разрядов счетчиковых схем являются линейно независимыми, то любая перестановка или коммутация элементов подмножества также образует счетчиковую последовательность и изменяет только порядок следования всех двоичных векторов, генерируемых этими разрядами. Наименьшим возможным изменением при переходе от одного подмножества разрядов к другому является удаление одного из крайних элементов подмножества и добавление разряда путем сдвига влево или вправо на один разряд. В терминах номеров разрядов подмножества могут различаться, по меньшей мере, одним разрядом. Следовательно, максимальное число различных подмножеств для СРНОС/СР длиной в n разрядов равно . Для постановки задачи синтеза ГПТ на СРНОС/СР введем следующее определение.

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

Очевидно, что множество независимых входов схемы может быть запитано выходом одного и того же разряда ГПТ или на пару независимых входов можно подать выходы ГПТ и , которые генерируют эквивалентные последовательности тестовых сигналов.

Таким образом, задача синтеза ГПТ на СРНОС/СР для тестирования схем псевдоисчерпывающими тестами сводится к нахождению минимального числа максимальных подмножеств независимых входных переменных , что позволяет для заданной схемы определить минимальную длину тестовой последовательности, которая может находиться в пределах .

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

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

Определение 3.4. Подграф P графа называют максимально полным подграфом или кликой графа , если все вершины подграфа Р попарно смежны и любой другой подграф графа , построенный на множестве вершин Н, содержащим Р , не является полным.

Тогда задача построения ГПТ для этой схемы сводится к нахождению минимального покрытия множества вершин графа максимальными подграфами независимых вершин или его кликами, что обеспечит построение ГПТ минимальной размерности с минимальной длиной тестовой последовательности.

Процедура синтеза ГПТ на СРНОС/СР для схем представлена следующим ниже алгоритмом.

Алгоритм 3.3.

Шаг 1.По заданной схеме вычислить подмножества переменных , где , от которых зависит j - ый конус схемы, и

Шаг 2.Установить .

Шаг3.Для переменной найти множество выходных конусов , , которые зависят от .

Шаг 4. Выполнить операцию объединения всех подмножеств переменных, от которых зависят , и записать множество переменных, зависимых с .

Шаг 5. Выполнить операцию вычитания множеств переменных .

Шаг 6.Если , то множество переменных независимых с записать в память. Если , то включить в список полностью зависимых вершин .

Шаг 7.Установить . Если , то перейти к шагу 3. Если , то перейти к шагу 8.

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

Шаг 9. Поставить в соответствие каждой переменной вершину графа независимых переменных.

Шаг 10.Построить матрицу достижимостей D графа . В строке матрицы D отмечены 1 множество столбцов, соответствующих переменным, входящим в , которые независимы с .

Шаг 11.Установить .

Шаг 12.Выполнить операцию пересечения двух строк матрицы D. Множество вершин является кликой графа . Записать в регистр клик графа .

Шаг 13.Выполнить операцию вычитания множеств ;

Шаг 14.Если , то определено полное множество клик, которые включают вершину . Перейти к шагу 15. Если , то перейти к шагу 12.

Шаг 15.Установить . Если , то перейти к шагу 12. В противном случае к шагу 16.

Шаг 16.Найти минимальное покрытие множества X входных переменных множеством клик графа независимых вершин, что определяет минимальную разрядность ГПТ на СРНОС/СР.

Шаг 17.Конец алгоритма.

Пример схемы, приведенный ниже, иллюстрирует процедуру синтеза ГПТ на СРНОС/СР в соответствие с Алгоритмом 3.3.

Пример 3.2. Пусть заданы схема, имеющая 8 входов и 8 выходов. В результате выполнения шага 1 Алгоритма 3.3 определена конусная зависимость в следующем виде:

Выполняя последовательность шагов 2, 3, 4 алгоритма находим подмножества переменных , связанных отношением зависимости с в виде:

Выполнив операцию вычитания множеств на шаге 5 алгоритма, с учетом поправок на множество полностью зависимых переменных и , определяемых на шаге 6, 7, и 8, находим подмножества независимых переменных , которые представлены графом независимых вершин на рис.3.10 (шаг 9).

Рис.3.10 Граф независимых вершин примера 3.2

На шаге 10 строим матрицу достижимостей D вершин графа независимых вершин (рис.3.11).

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

	1	0	0	1	1	0
	0	1	0	1	1	1
	0	0	1	0	0	1
	1	1	0	1	0	1
	1	1	0	0	1	0
	0	1	1	1	0	1

Рис.3.11 Матрица достижимостей графа на рис. 3.10.

Для нахождения минимального покрытия множества входных переменных X множеством клик графа независимых вершин на шаге 16 алгоритма формируется матрица покрытий, строки которой отмечены кликами графа , а столбцы множеством входных переменных за исключением полностью зависимых переменных. В клетке матрицы на пресечении строки и столбца устанавливается 1, если , в противном случае устанавливается 0.

Для рассматриваемого примера матрица покрытий представляется в следующем виде (табл.3.12):

Таблица 3.12

Матрица покрытий для примера 3.2

Клики графа
	1	0	0	1	0	0
	1	0	0	0	1	0
	0	1	0	0	1	0
	0	1	0	1	0	1
	0	0	1	0	0	1

Система булевых уравнений из матрицы покрытий записывается в виде:

		(3.14)

В (3.14) знак “+” обозначает логическую операцию дизъюнкции.

Множество решений системы уравнений (3.14) находится путем нахождения конъюнктивных термов, входящих в уравнение:

(3.15)

Так как a5 поглощает дизъюнкцию (а4+ a5), то уравнение (2.20) представляется в виде:

(3.16)

Из (3.16) следует, что существует два решения системы уравнений (3.14) с минимальным числом булевых переменных, входящих в конъюнктивные термы: .

Таким образом, минимальные множества клик, покрывающие все вершины графа независимых вершин исходной (8, 8, 4) схемы представляются в виде:

(3.17)

Объединяя множества и с множеством полностью зависимых вершин , определенных на шаге 6 алгоритма, получаем:

(3.18)

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

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

(3.19)

Условие (3.19) не выполняется для блоков разбиения , так как . Обеспечивая выполнение условия (3.19) в так, чтобы объединение всех блоков разбиения включало множество всех входных переменных , получаем:

(3.20)

Таким образом, разбиение множества входов схемы примера 3.2 на блоки, объединяющие подмножества независимых переменных, являются функциональным описанием трех схем генераторов псевдослучайных тестов для КС (8, 8, 4) с заданной конусной зависимостью. Так как мощность множеств , то выбрав функцию нелинейной обратной связи СР в виде:

(3.21)

можно легко построить три варианта схем ГПТ, которые представлены на рис. 3.12. Функция обратной связи позволяет генерировать гамильтонов цикл в 5 - разрядном СР и реализуется сетью Майтра, что обеспечивает минимальность аппаратурных затрат на схему генератора. Выбор этих решений осуществляется на основе Алгоритмов, представленных в разделах 3.1. и 3.2.

3.4 Минимизация длины проверяющей последовательности

Применение процедуры синтеза ГПТ на сдвиговых регистрах с нелинейной ОС, представленной в разделе 3.3, для схемы (8, 8, 4) примера 3.2 обеспечивает псевдоисчерпывающее тестирование схемы тестовой последовательностью длиной в 32 двоичных наборов. Это определяется отношением зависимости входных переменных, которое устанавливается путем нахождения минимального покрытия этих переменных множеством клик графа независимых входов и условиями генерации СРНОС/СР исчерпывающих тестов в соответствии с Теоремой 3.2.

а) Схема ГПТ, соответствующая разбиению .

b) Схема ГПТ, соответствующая разбиению .

c) Схема ГПТ, соответствующая разбиению .

Рис.3.12.Схема ГПТ на СРНОС/СР с функцией ОС (3.21) для КС (8,8,4) примера 3.2

Так как проверяемая схема имеет конусную зависимость ее выходов от входных переменных , то схема может быть проверена псевдоисчерпывающими тестами длиной . Возникает вопрос: существует ли схемная реализация такого генератора на основе СРНОС/СР?

Из Теоремы 3.2 следует, что в СРНОС/СР длиной при СРНОС размерности k лишь любые смежные k разрядов формируют счетчиковые последовательности. Поэтому в СРНОС/СР не существует разряда, не смежного с смежными разрядами СРНОС/СР, который в сочетании с ними позволяет сформировать k - разрядную счетчиковую последовательность. Следующее ниже утверждение определяет условия формирования разряда, обладающего таким свойством.

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

,

где - нелинейная булевая функция.

Если функцию возбуждения разряда цепи СРНОС/СР сформировать в виде , то разряд генерирует счетчиковые последовательности длиной в любых сочетаниях с разрядами из множества .

Функции возбуждения триггеров цепи СРНОС равны:

(3.22)

Так как функция возбуждения разряда Sk+1 равна:



(3.23)

Суммируя по mod2 левые и правые части равенств (3.22) и (3.23) получаем:

(3.24)

Так как разряды СР вместе с нелинейной обратной связью генерируют различных двоичных векторов, т.е. счетчиковую последовательность тестовых наборов, то формирование k - мерного вектора в сочетании с разрядом обеспечивается, если . Так как , то левая и правая часть равенства (3.24) равны 0, т.е.

(3.25)

Так как текущие состояния разрядов СР и последующие состояния в сумме по mod2 эквивалентны, то равенство (3.24) выполняется для всех наборов разрядов . Из равенства (3.25) следует, что

(3.26)

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

Предложенный подход определяет условие формирования в ГПТ на СРНОС/СР разряда, позволяющего в 2 раза сократить длину тестовой последовательности.

Обратимся вновь к примеру 3.2. Длина тестовой последовательности в этом примере определяется мощностью разбиения . Так как , то схема проверяется генератором псевдоисчерпывающих тестов в котором 5 выходов в любом сочетании должны обеспечить приложение к входам всех 8 конусов схемы различных двоичных наборов. В схеме СРНОС/СР это обеспечивается тестовой последовательностью длиной и схемами на рис.3.12.

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

Схема ГПТ на основе СРНОС/СР, построенного в соответствии с предложенной методикой минимизации длины проверяющей последовательности, приведена на рис.3.13.

Рис.3.13 Схема ГПТ на СРНОС/СР, (пример 3.2) .Аппаратурные затраты 5,4 в.э.

Для примера 3.2 схемы синтезируем ГПТ на основе метода МСРЛОС/СР, представленного в разделе 2.2. Обеспечить линейную независимость остатков для исчерпывающего тестирования заданной схемы (8, 8, 4) удается лишь для СР с линейной обратной связью на основе неприводимого полинома разрядностью равной 5, что определяет длину теста . Так как начальная установка СР не равна 0, то для формирования вектора необходимо использовать два мультиплексора 2 на 1. При этом схема управления процессом тестирования усложнится введением дополнительной процедуры. С учетом вышеуказанного аппаратурные затраты на реализацию схем генераторов на рис.3.13 и 3.14 равны 5,4 в.э. и 6,4 в.э. соответственно.

Преимущество ГПТ на СРНОС/СР как по длине псевдоисчерпывающего теста, так и по аппаратурным затратам, очевидно.

3.5 Синтез ГПТ на основе использования примитивных многочленов

В [64] предложен простой подход к построению генератора последовательности де Брейна, состоящий из двух этапов:

формирование элементарной конъюнкции вида

(3.27)

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

если формирующий многочлен имеет вид

(x) = xp + xa + xb + …+ xj + 1(3.28)

где j - наименьший показатель степени, входящий в (x),

то функция обратной связи генератора последовательности де Брейна реализуется по формуле:

F(x) = xp xa xb … (xj + mj)(3.29)

где mj - элементарная конъюнкция.

Однако, при разрядности n 7 генераторы с такой структурой не вырабатывают полный цикл длиной L = 2n.

Рис.3.14. Схема ГПТ на МСРЛОС/СР, полином f(x)=х5+х3+1, L=25=32,

Аппаратурные затраты 6,4 в.э.

В настоящем разделе предлагается расширение этого метода для получения генератора последовательности де Брейна разрядности [116]. Для объединения всех смежных циклов предлагается ввести дополнительный элемент И - НЕ по следующему алгоритму:

формируется m циклов исходного СР, каждый из которых имеет начальное состояние x = x =…= x = 0;

определяются смежные циклы, которые содержат левосопряженные состояния;

определяются отсутствующие в последовательности смежные циклы и соответствующие им левосопряженные состояния;

объединяются смежные циклы с помощью элемента И - НЕ для генерации полного цикла.

Дальнейшие исследования показали, что данный подход пригоден для синтеза генераторов последовательности де Брейна разрядности n = 16. В качестве примера рассмотрим СР с порождающим многочленом (x) = x16 + x12 + x3 + x + +1.

Согласно [64] функционирование генератора описывается формулой:

(3.30)

Полученная таким образом последовательность имеет длину L = 63770 и содержит следующие левосопряженные состояния:

1000100000000100 - 0000100000000100

1000100000000001 - 0000100000000001

1000100000000000 - 0000100000000000

1000100000000101 - 0000100000000101

1000000000000100 - 0000000000000100

1000000000000001 - 0000000000000001

Отсутствующие левосопряженные состояния:

1000000000000101 - 0000000000000101

1000000000000000 - 0000000000000000

Подчеркнутые векторы в последовательности отсутствуют. Для введения в последовательность цикла с начальным состоянием 1000100000000000 включим в схему элемент И - НЕ.

Особыми точками последовательности являются те, в которых значения переменных x2, x4, x5, x6, x7, x8, x9, x10, x11, x13, x14, x15 равны нулю. Именно эти точки предшествуют левосопряженным состояниям и определяют переходы в смежные циклы. Согласно [116] отличительными являются значения элементов x1, x3, x12. Для получения нуля на выходе элемента И-НЕ в состоянии 0001000000000001 необходимо на входы элемента И-НЕ подать значения . Таким образом, функция обратной связи определяется по следующей формуле:

(3.31)

Схема генератора последовательности де Брейна показана на рис. 3.15.

По вышеуказанному алгоритму составлена программа, которая осуществляет синтез многочлена обратной связи СРНОС для генерации последовательностей де Брейна. Листинг программы приведен в приложении В.2. В приложении Г приведены все примитивные многочлены степени 16 с минимальным числом элементов в цепи обратной связи и соответствующие функции обратной связи для получения последовательностей де Брейна. При этом длина последовательности L будет равна максимальному значению (L = 65536).

Таким образом, предложенный метод позволяет синтезировать генераторы последовательностей де Брейна разрядности n = 16. Полученные при этом последовательности обладают важным свойством - непредсказуемостью структуры последовательности по неискаженному ее фрагменту, что позволяет использовать такие генераторы при организации помехозащищенных каналов связи.

3.6. Кодирование состояний автомата, оптимальное по тестопригодности.

Известно, что если ДУ описано моделью автомата Мили или Мура, представленного в минимальной форме, то сложность его схемной реализации определяется вариантом кодирования внутренних состояний автомата [117].

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

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

Таблица 3.13.

ТПВ автомата А3.1.

Z(t)	Z(t+1), (t)
	xi	x0
A	.	B , 1
B	.	C , 1
C	.	D , 0
D	.	E , 0
E	.	A , 0

Рассмотрим вариант кодирования состояний автомата А3.1, которые иллюстрируется таблицей 3.14. Сложность реализации предложенного расширения ТПВ исходного автомата определяется сложностью реализации функции переходов и выходов, соответствующих столбцу .

Таблица 3.14.

Кодированная ТПВ автомата А 3.1.

z1	z2	z3	Z(t+1), (t)
			xi	x0
0	0	0	.	100 , 1
1	0	0	.	110 , 1
1	1	0	.	011 , 0
0	1	1	.	001 , 0
0	0	1	.	000 , 0

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

Коды состояний автомата (таблица 3.14), получены циклическим сдвигом последовательности , порождающей гамильтонов цикл в подграфе 3 - разрядного СР. Эта же последовательность кодирует функцию выходов автомата, обеспечивая наличие однородной отличительной последовательности минимальной длины. В общем случае для реализации легко тестируемого автомата с произвольным числом состояний оптимальное кодирование можно определить следующим образом.

Определение 3.5. Пусть задан автомат, имеющий состояний . Кодирование внутренних состояний автомата является оптимальным по тестопригодности, если между кодами состояний автомата и кодами вершин подграфа - разрядного СР, в котором последовательность порождает гамильтонов цикл, существует взаимно однозначное соответствие. Множество двоичных векторов, соответствующих множеству вершин подграфа , будем называть оптимальным кодом произвольного автомата с состояниями.

Как было показано в разделе 3.1 для любого числа существует последовательность , порождающая гамильтонов цикл в подграфе - разрядного СР. Следовательно, оптимальный код, соответствующий определению 3.5, существует для любого детерминированного автомата с состояниями.

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

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

Рис. 3.16. Структурная модель модифицированного автомата.

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

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

Очевидна простота и регулярность реализации функции обратной связи СР, так как схемы представляют собой класс легко диагностируемых бесповторных однородных сетей Майтра, синтез которых был рассмотрен в разделе 3.2.

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

На рис. 3.17 и 3.18 представлены схемы декадного двоично-десятичного счетчика и четырехразрядного счетчика, которые синтезированы предложенным выше методом. Счетчики имеют два выхода: - выход переноса, - диагностический выход, на котором формируется последовательность . Функции обратной связи реализуются цепями Майтра. Длина отличительной последовательности обоих схем равна . Введение дополнительного диагностического выхода не влечет за собой введение дополнительных аппаратурных затрат для реализации выходных функций.



3.7 Выводы

Проведен анализ существующих методов и алгоритмов генерации исчерпывающих двоичных последовательностей Де Брейна на сдвиговых регистрах с нелинейной ОС. Показано, что задача синтеза ГПТ на СРНОС эквивалентна нахождению остовных деревьев в графе СР, которые порождают гамильтоновы циклы в этом графе.

Предложена универсальная конечно-автоматная модель остовных деревьев графа n - разрядного СР и разработан алгоритм нахождения гамильтоновых циклов в графе (n+1) разрядного СР по автоматным моделям графа n - разрядного СР. Показано, что существует класс остовных деревьев, которые порождают гамильтоновы циклы в графе СР с минимальной аппаратурной реализацией ОС в виде бесповторной сети Майтра.

а)

	T1	T2	T3	T4
0	1	0	0	0
1	1	1	0	0
2	0	1	1	0
3	0	0	1	1
4	1	0	0	1
5	0	1	0	0
6	1	0	1	0
7	0	1	0	1
8	0	0	1	0
9	0	0	0	1

b)

Рис. 3.17. Декадный двоично - десятичный счетчик:

а) функциональная схема;

b) последовательность счета.

а)

	T1	T2	T3	T4
0	0	0	0	0
1	1	0	0	0
2	1	1	0	0
3	1	1	1	0
4	1	1	1	1
5	0	1	1	1
6	1	0	1	1
7	0	1	0	1
8	1	0	1	0
9	1	1	0	1
10	0	1	1	0
11	0	0	1	1
12	1	0	0	1
13	0	1	0	0
14	0	0	1	0
15	0	0	0	1

b)

Рис. 3.18. Четырехразрядный двоичный счетчик

а) функциональная схема

b) последовательность счета.

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

Предложен метод синтеза ГПТ на основе СРНОС/СР. Определены условия начальной установки разрядов СР, обеспечивающие генерацию гамильтоновых циклов на любых “k” смежных разрядах генератора. Показано, что задача синтеза ГПТ на СРНОС/СР для тестирования (n, m, k) схем сводится к нахождению минимального числа максимальных подмножеств независимых входных переменных (клик графа СР) и нахождению минимального покрытия множества входных переменных кликами этого графа, что обеспечивает построение ГПТ минимальной размерности с минимальной длиной проверяющей последовательности. На основе предложенного подхода разработан алгоритм синтеза.

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

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

РАЗДЕЛ 4. МОДУЛИ СИГНАТУРНОГО МОНИТОРИНГА НА КЛЕТОЧНЫХ АВТОМАТАХ

4.1 Анализ свойств клеточных автоматов

В последнее время растет число исследований, связанных с однородными сетями элементарных автоматов, т.е. с сетями, состоящими из однотипных и одинаково соединенных автоматов. Таким сетям под различными названиями - итеративные сети, однородные среды, автоматы Неймана - Чёрча, клеточные автоматы и т.д. посвящено большое число исследований [76, 86 - 96].

В конце 50-х годов теория однородных структур, у истоков которой стояли известные ученые Дж. Фон Нейман, С. Улам, А Чёрч, Э. Мур и др. привлекла к себе внимание многих исследователей. Интерес к таким объектам возник из двух различных источников. С одной стороны, это дальнейшее развитие идей Дж. Фон Неймана, который использовал понятие клеточного автомата для исследования условий, при которых машины способны к самовоспроизведению и самоорганизации [86]. С другой стороны, построение машин клеточных автоматов является перспективным направлением использования возможностей современных субмикронных технологий в электронной промышленности.

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

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

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

В связи с этим существующие компьютеры мало пригодны для решения этих задач. Моделирование одного события в клеточном автомате может потребовать последовательного выполнения до нескольких десятков машинных команд, скажем 10 мксек, на быстродействующем компьютере. Для того, чтобы вычислить событий при таком подходе потребуется 8 месяцев. Для сравнения двумерная сеть КА, содержащая клеточных автоматов (это несколько грубее, чем разрешающая способность телевизионного кадра) выполнит моделирование событий за 0,5 сек.

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

СКА характеризуется четырьмя основными параметрами: геометрия связей соседних КА, числом состояний КА и алгоритмом вычисления последующих состояний [98]. Изменение каждого из перечисленных выше параметров позволяет конструировать различные СКА, отличающиеся своими свойствами. Использование двумерных СКА для решения многих задач распознавания образов и связанных с ними проблемами, моделирование гидродинамических процессов и других физических явлений, в основе которых лежит статистическая механика, демонстрирует потенциальные возможности СКА с учетом простоты их схемной реализации на СБИС [97]. В качестве примера для этой демонстрации можно привести СКА, структуру которого и систему правил определил в 1970 г. известный математик Дж. Конвей для игры в «Жизнь» [87].

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

В других физических приложениях СКА использовались для моделирования роста кристаллов, где было показано, что анализ поведения этой сети позволил уточнить физическую сущность этих сложных процессов [98]. В большинстве опубликованных работ для анализа поведения одномерных и двумерных СКА использовался аппарат алгебры многочленов [88].

Такие СКА широко используются в качестве генераторов псевдослучайных последовательностей [88 - 95]. Достоинствами таких генераторов является простота (каждая клетка связана только с ближайшими соседними клетками) и регулярность структуры [99]. Увеличение разрядности устройств связано лишь с добавлением однотипных ячеек. В клеточных автоматах отсутствуют глобальные обратные связи, которые характерны для СРЛОС. Кроме этого, в КА отсутствует многовыходной элемент сумма mod 2, который вносит определенные временные задержки [99].

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

Различают одномерные и двумерные сети клеточных автоматов. Наибольшее практическое применение нашли структуры клеточных автоматов, у которых клеточные автоматы имеют два состояния [95].

Одномерные структуры КА представлены на рис. 4.1. Клеточный автомат имеет достаточно простую структуру и состоит из триггера M, имеющего два состояния, и комбинационной схемы (КС), реализующей функцию возбуждения М, равную

(4.1)

где - текущие состояниия соседних КА, расположенных слева и справа от ячейки , соответственно.

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

Рис. 4.1. Структуры одномерных сетей КА:

Структурная схема клеточного автомата;

Структура одномерной сети КА длиной n с нулевыми граничными условиями;

Структура одномерной сети КА длиной n с обратными связями.

Правило настройки - это удобный способ представления зависимости состояния клетки от состояний соседних клеток. Например, правило 150, связанное со следующей таблицей переходов (табл. 4.1), реализуется комбинационной логикой следующим образом:



где z - состояние клетки в определенный момент времени.

Таблица 4.1

Таблица переходов СКА с правилом 150.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

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

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

Определение 4.2. Однородная или гибридная СКА называется аддитивной СКА, если правила настройки клеток являются классом линейных логических функций.

Существует 10 различных правил настройки аддитивных СКА.

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

Все правила настройки в алгебраической форме представлены в таблице 4.2.

В [100] предложено правила настройки СКА, которые определяются логическими операциями сумма mod 2 называть безинверсными, а операциями эквивалентность называть инверсными правилами. Как видно из табл. 4.2. в гибридной СКА могут иметь место инверсные и безинверсные правила настройки.

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

Таблица 4.2

Аддитивные правила для СКА.

Правило	Функция
204
51
60
195
102
153
90
165
150
105

Правило 204: .

Это правило является просто правилом тождественности, которое не изменяет состояний СКА. Таким образом, правило 204 образует цикл длиной для всех СКА. Поведение правила 51 такое же.

Правило 60: .

Для правила 60 справедливо следующее утверждение [101].

Утверждение 4.1. Правило 60 формирует циклы любой длины , где - число клеток в СКА, .

Из утверждения 4.1 следует, что однородная СКА с правилом 60 настройки клеточных автоматов имеет множество циклов, которые определяются начальным состоянием СКА с нулевыми граничными условиями.

Правило 102: .

Так как это правило является симметричным отображением правила 60, то СКА с этими правилами настройки имеет тот же порядок циклических последовательностей.

Правило 90: .

В [88] показано, что правило 90 образует циклические последовательности ограниченной длины тогда и только тогда, когда .

Правило 150: .

Для правила 150 экспериментально показано, что циклы формируются только при условии [88].

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

4.2 Матричные модели сетей КА

4.2.1 Характеристическая матрица правил СКА

Последовательность, генерируемая - клеточной СКА, может быть однозначно представлена многочленом степени . Например, для 8 - клеточной СКА состояние, характеризуемое 8 разрядами, например 10111010, может быть представлено многочленом

(4.2)

На 8 - разрядном пространстве векторов это состояние может быть представлено вектором - строкой в виде:

(4.3)

где обозначает операцию транспонирования матрицы.

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

Определение 4.3. Квадратная матрица размерности , представляющая правила настройки клеточных автоматов сети, называется характеристической матрицей СКА, в которой - я строка матрицы представляет правило настройки - го клеточного автомата.

В соответствии с определением 4.3 характеристическая матрица СКА размерности с нулевыми граничными условиями и геометрией связей только с ближайшими соседями представляется в виде:

(4.4)

где отображают правила настройки - го клеточного автомата сети.

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

Например, характеристическая матрица СКА размерности представляется в виде:

(4.5)

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

Пример 4.1. Пусть дана 4 - клеточная СКА с нулевыми граничными условиями со следующими правилами <90, 204, 60, 150>.

Воспользовавшись таблицей 4.2 и введенными обозначениями (4.5), характеристическую матрицу СКА представим в виде:

Первая строка представляет правило настройки 90: и т.д. Если СКА имеет периодические граничные условия, то крайние столбцы матрицы являются соседними и отмечаются символами при соответстсвующих настройках.



4.2.2 Матричные модели СКА

Характеристическая матрица СКА (в дальнейшем Т - матрица) позволяет представить функцию переходов автоматной модели аддитивной сети клеточных автоматов в виде:

(4.6)

где - состояние СКА в момент времени , а - состояние СКА в момент времени .

Если настройка СКА позволяет генерировать циклическую последовательность, то для всех должно существовать целое число такое, что [118]

(4.7)

где - единичная матрица.

(4.8)

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

Правило 195 () является инверсией правила 60 (). Однако, поскольку операция эквивалентность не может быть представлена в мультипликативной форме, то обозначим ее . Таким образом, представляет обозначение соответствующей функции сумма mod 2. Исходя из этого, последующее состояние СКА определяется через инверсное правило в виде:

(4.9)

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

Пример 4.2. Однородная 4 - клеточная СКА с нулевыми граничными условиями и аддитивным инверсным правилом 195 (), последовательно используемым на полном цикле, представляется в виде:

Где

где Т матрица соответствует правилу 60 .

В общем случае, последующее состояние гибридной СКА может быть вычислено следующим образом:

(4.10)

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

Пример 4.3. Гибридную 4 - клеточную СКА с нулевыми граничными условиями и правилами <60, 51, 153, 153>, можно представить в матричной форме следующим образом:

где Т соответствует СКА с правилами и задается в виде:

В этом примере состояния всех клеток, за исключением первой, определяются операцией эквивалентности. Таким образом, .

Поскольку строки характеристической матрицы однозначно отображают правила настройки СКА с учетом специфики зависимости позиций клеток, то в матрице вектор можно представить в двоичной форме. Таким образом, матрицу для примера 4.3 можно записать в виде:

Соответственно, представляется в виде

Таким образом, инверсные правила настройки однородной и гибридной СКА также можно представить в матричной форме.

Утверждение 4.2. Пусть обозначает последовательное применение инверсного правила раз. Тогда

(4.11)

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

Доказательство: Так как

(4.12)

Тогда

(4.13)

Таким образом, может быть выражено через степени (где Т - характеристическая матрица с безинверсными правилами). Утверждение доказано.

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

4.3. Генераторы циклических последовательностей на клеточных автоматах.

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

Пусть мы имеем , где - квадратная матрица с элементами над полем .

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

Доказательство приведено в приложении А.1.

Для алгебраически инверсных правил настройки СКА справедливы нижеследующие утверждения.

Утверждение 4.4. Если СКА с характеристической матрицей генерирует группу, то ее инверсия также имеет свойство группы.

Доказательство приведено в приложении А.2.

Утверждение 4.5. Если R - правила настройки, формирующие группу, то также формирует группу, где представляет собой правило, полученное путем одной из возможных перестановок правил R или в каждой клетке СКА.

Доказательство приведено в приложении А.3.

Следствие: Если какая-либо перестановка формирует группу, то также будут формировать группу.

Этот вывод справедлив для любого числа правил и СКА любой длины .

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

Утверждение 4.6. Сеть клеточных автоматов с формирует циклические последовательности длиной или кратной с ненулевым начальным состоянием тогда и только тогда, когда .

Доказательство приведено в приложении А.4.

Утверждение 4.7. Если длина цикла является составным числом, то СКА генерирует циклические последовательности длиной, равной его множителям.

Доказательство приведено в приложении А.5.

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

Пример 4.4. Пусть 4 - клеточная СКА с нулевыми граничными условиями и правилом 90 имеет следующую характеристическую матрицу:

и . Для характеристической матрицы справедливо, что

Следовательно, в соответствии с вышедоказанными утверждениями, при ненулевых начальных условиях СКА генерирует циклы длиной 3 и 6, но не 1 и 2.

4.4 Изоморфизм СКА и СРЛОС

Для генерации циклических последовательностей максимальной длины, как было показано в разделе 2, можно использовать сдвиговый регистр с линейными обратными связями (СРЛОС). Исследуем структуру СРЛОС с позиций матричной модели аддитивной СКА.

СРЛОС с разрядами можно представить в виде гибридной аддитивной СКА, в которой функция возбуждения крайней левой клетки (входной клетки) содержит компонентов, а для остальных клеток - зависит только от ближайшей слева клетки.

На рис. 4.2 показан 4 - разрядный СРЛОС со следующим характеристическим многочленом:

(4.14)

Рис. 4.2. 4 - разрядный СРЛОС.

Соответствующая матрица гибридной СКА с учетом того, что состояние крайней левой клетки зависит от всех клеток, представляется в виде:

(4.15)

Так как матрица является невырожденной, то очевидно, что СРЛОС генерирует периодические последовательности.

Утверждение 4.8. Характеристический многочлен матрицы СКА эквивалентен характеристическому многочлену СРЛОС, генерирующему эквивалентную периодическую последовательность.

Доказательство: Пусть характеристический многочлен для - разрядного СРЛОС имеет вид:

(4.16)

В соответствии с классической теорией матриц [102] характеристический многочлен Т матрицы СКА определяется путем присоединения к ней диагональной матрицы, где - характеристические числа оператора Т. Из матрицы следует:

(4.17)

и характеристический многочлен матрицы Т равен:



(4.18)

Так как уравнения (4.17) и (4.18) совпадают с заменой на , то утверждение справедливо.

Таким образом, СРЛОС является одним из вариантов настройки гибридной аддитивной СКА и все свойства СРЛОС, как генератора последовательности максимальной длины, рассмотренные в разделе 2, изоморфны свойствам гибридной аддитивной СКА при соответствующих правилах ее настройки.

4.5 Генераторы последовательностей максимальной длины на СКА

Говорят, что - разрядная СКА генерирует последовательности максимальной длины, если все возможные ненулевые - разрядные наборы содержатся в одном цикле. Для СРЛОС справедливо простое свойство, которое позволяет достичь того, что единый цикл содержит все 2n - 1 возможные ненулевые наборы [119].

Пусть - характеристическая матрица СКА с групповыми свойствами. Для такой сети существует целочисленный показатель степени такой, что . Согласно Утверждению 4.7, циклические последовательности, генерируемые такой СКА, имеют период, равный или его множителям.

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

Утверждение 4.9. СКА с клетками генерирует последовательность максимальной длины, если выполняется условие:

где наименьшее значение равно .

Утверждение 4.10. (достаточное условие генерирования последовательности максимальной длины): Если является составным числом, то для всех возможных множителей матрица должна быть невырожденной.

В [95] приведены утверждения, на которых определен изоморфизм между СРЛОС и СКА, которые генерируют последовательности максимальной длины.

Утверждение 4.11. Сеть клеточных автоматов и СРЛОС, которые генерируют последовательности максимальной длины, изоморфны между собой.

Доказательство приведено в приложении А.6.

Утверждение 4.12. Сеть клеточных автоматов и СРЛОС, которые генерируют последовательности максимальной длины, имеют идентичные характеристические многочлены.

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