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

(1)	Правило 150:
(2)	Правило 90:

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

Длина СКА	Число различных настроек СКА, генерирующих последовательности максимальной длины
4	4
5	12
6	12
7	36
8	32
9	96
10	120
11	352
12	288

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

Для каждого примитивного многочлена степени существует единственный СРЛОС, который генерирует последовательности максимальной длины для всех клеток. В [70] приведены все примитивные многочлены для . Существует 2 примитивных многочлена степени 4; 6 многочленов степеней 5 и 6; 18 многочленов степени 7; 16 многочленов степени 8; 48 многочленов степени 9; 60 многочленов степени 10; 176 многочленов степени 11; 144 многочлена степени 12 и т.д.

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

Для приведенных в приложении Б СКА степени 5 можно отметить, что пары СКА (1, 7), (2, 9), (3, 5), (4, 11), (6, 12) и (8, 10) являются зеркальными отображениями друг друга. Сеть клеточных автоматов и ее зеркальное отображение имеют одинаковую структуру. На рис. 4.3 показана пара СКА (2, 9). Они имеют одинаковый характеристический многочлен, который является примитивным.

Рис. 4.3. Зеркальные отображения СКА

а) <150 150 90 90 90> с нулевыми граничными условиями

б) <90 90 90 150 150> с нулевыми граничными условиями

Поскольку также равно числу различных примитивных многочленов степени , то можно сделать вывод, что для каждого примитивного многочлена степени существует единственная СКА с нулевыми граничными условиями, использующая только правила 90 и 150.

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

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

Пример 4.5: Пусть выбран примитивный многочлен 4 степени и СКА на его основе с нулевыми граничными условиями и правилами настройки . Матричная модель СКА представляется в виде:

Последовательность, генерируемая такой СКА, представлена на рис. 4.4.

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

Рис. 4.4. Последовательность векторов, генерируемых СКА с характеристическим многочленом .

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

4,2 =	{ 011110001001101, 101111000100110, 010111100010011, 101011110001001, 110101111000100, 011010111100010, 001101011110001, 100110101111000, 010011010111100, 001001101011110, 000100110101111, 100010011010111, 110001001101011, 111000100110101, 111100010011010}

Рис. 4.5. Периодическая двоичная последовательность с периодом .

Последовательности в обладают следующими свойствами [100]:

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

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

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

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

Определим две операции следующим образом:

(а) - обозначает исключение - го разряда из общего - разрядного набора.

(б) - - обозначает операцию конкатенации потока двоичных разрядов.

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

(4.19)

И

(4.20)

где - целое число и .

Следует отметить, что

(4.21)

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

(4.22)

Следует отметить, что появляется один раз в - разрядном наборе, который принадлежит одному циклу состояний. Таким образом, результат суммирования (4.22) является последовательностью, которая принадлежит .

4.7 Метод синтеза генераторов последовательностей максимальной длины на аддитивных СКА

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

Алгоритм 4.1.

Построить характеристическую матрицу в виде (4.4) для заданной размерности СКА.

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

Синтезировать формулу расчета коэффициентов характеристического многочлена трехдиагональной матрицы для каждого на основе следующей рекуррентной формулы[103]:

(4.23)

где

- порядок матрицы

Составить систему уравнений по формуле п.3.

Вычислить значения для каждой строки в соответствии с выбранным в п.2. примитивным многочленом.

В качестве примера возьмем СКА длиной 4 с нулевыми граничными условиями [118,120]. Характеристическая матрица такой СКА имеет следующий вид:

(4.24)

где , а характеристический многочлен рассчитывается по формуле:

(4.25)

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

Получаем следующую систему уравнений:

(4.26)

Решая систему уравнений, получаем:

(4.27)

Характеристическая матрица СКА имеет вид:

(4.28)

Следовательно, СКА реализуется в соответствии с правилами .

Используя этот алгоритм, были получены правила эволюции СКА длиной 4 - 20, которые генерируют последовательности максимальной длины. Результаты вычислений представлены в табл. 4.3.

Таблица 4.3.

Правила эволюции СКА для генерации последовательностей максимальной длины.

Длина n	Характеристический многочлен	Правила настройки СКА
4		150,90,150,90
5		150,150,150,150,90
6		90,150,150,90,90,90
7		90,150,150,150,90,150,90
8		90,150,150,90,90,90,90,90
9		90,150,90,90,150,150,150,90,90
10		150,150,150,150,90,90,90,90,150,150
11		90,150,90,150,150,90,90,90,90,150,90
12		90,150,150,90,150,150,90,90,90,150,150,90
13		150,90,90,90,150,90,90,90,90,150,150,90,90
14		90,90,150,90,150,150,150,90,90,150,90,150,90,90
15		90,150,150,90,150,90,150,150,150,150,90,150,90,90,90
16		150,90,150,90,90,90,90,90,90,90,150,150,150,90,90,150
17		150,90,90,150,150,90,90,150,150,90,90,90,150,150,90,90, 150
18		150,150,90,90,150,90,90,90,90,90,90,90,150,90,90,90,150, 150
19		150,90,150,90,90,150,90,150,90,90,150,90,90,150,90,90, 150,90,150
20		90,150,150,90,150,90,150,150,150,90,90,90,90,150,90,150, 90,150,150,90

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

4.8 Выводы

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

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

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

Определен изоморфизм между СКА и СРЛОС. Доказано, что характеристический многочлен матричной модели СКА эквивалентен определенному характеристическому многочлену сдвигового регистра с линейной обратной связью, а характеристический многочлен СКА, генерирующей последовательности максимальной длины, является примитивным. Показано, что достаточно использовать лишь два правила настройки 90 и 150 для синтеза схемы СКА любой размерности, генерирующей последовательности максимальной длины.

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

РАЗДЕЛ 5. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МОДУЛЕЙ СИГНАТУРНОГО МОНИТОРИНГА

В данном разделе поставлена задача анализа свойств генерируемых последовательностей, достоверности функционирования и реализации предложенных схем сигнатурного мониторинга на современных ПЛИС ALTERA MAX 7000S, оценки аппаратурных затрат и быстродействия.

5.1 Анализ сложности последовательностей де Брейна

Для повышения помехозащищенности в военных системах связи, системах связи с большим числом абонентов, спутниковых навигационных системах получили широкое распространение последовательности де Брейна, которые генерируются сдвиговыми регистрами с нелинейной обратной связью [104]. При этом одним из основных требований, предъявляемых к последовательностям, является степень ее непредсказуемости по известным символам. Степень непредсказуемости последовательностей определяется разрядностью эквивалентного СРЛОС. Например, для М - последовательностей достаточно иметь символов ( - длина СРЛОС), идущих подряд, для раскрытия ее структуры [105]. Оценим сложность последовательностей де Брейна, полученных при помощи генераторов на СРНОС, метод синтеза которых предложен в разделе 3.5.

Пусть двоичная последовательность генерируется - разрядным СРЛОС. Тогда полностью определяется начальной установкой СР и линейной рекурсией в виде

(5.1)

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

Выражение (5.1) можно представить линейным разностным уравнением

(5.2)

где Е - оператор сдвига, т.е. .

Многочлен является многочленом обратной связи СР.

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

(5.3)

В [106] определены верхняя и нижняя граница сложности последовательностей, генерируемых - разрядным СР, которые определяются неравенством

(5.4)

Пусть - двоичная последовательность с периодом - векторное пространство поля . Справедливо следующее утверждение [107].

Теорема 5.1. Пусть , а - левая и правая половины двоичного вектора . Вычислим . Тогда выполняется:

а) если , то ;

б) если , то .

На основании теоремы 5.1 разработан алгоритм вычисления сложности последовательностей, генерируемых СРНОС, граф-схема которого представлена на рис. 5.1 [121]. Если длина последовательности , то вычисляется за шагов. В качестве примера вычислим сложность последовательности, генерируемой СРНОС с функцией обратной связи (3.21): :

(s) = 00000110010110111110101000100111

В соответствии с алгоритмом, представленным на рис. 5.1, выполняются следующие шаги:

Инициализация:
		l	c(s)
Шаг 1.	R(a) = 1110101000100111
	L(a) = 0000011001011011
	b = 1110110001111100	16	16
Шаг 2.	R(a) = 01111100
	L(a) = 11101100
	b = 10010000	8	24
Шаг 3.	R(a) = 0000
	L(a) = 1001
	b = 1001	4	28
Шаг 4.	R(a) = 01
	L(a) = 10
	b = 11	2	30
Шаг 5.	R(a) = 1
	L(a) = 1
	b = 0	0	30
	т.к. и , то	1	31

В результате .

По вышеуказанному алгоритму составлена программа расчета сложности последовательностей де Брейна. Листинг программы приведен в приложении В.4. В приложении Г приведены значения сложности последовательностей, генерируемых при помощи примитивных многочленов степени 16.

Проведенный анализ показал, что из 24 генераторов разрядности n = 16 четырнадцать генераторов вырабатывают последовательности максимальной сложности c(s) = 65535, четыре генератора вырабатывают последовательности со сложностью c(s) = 65534, пять генераторов вырабатывают последовательности со сложностью c(s) = 65533 и один генератор вырабатывает последовательность со сложностью c(s) = 65532.

Рис. 5.1. Блок - схема алгоритма определения сложности последовательности.

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

5.2 Достоверность функционирования самопроверяемого многоканального сигнатурного анализатора

Оценим эффективность функционирования модуля самопроверяемого МСА, схема которого представлена в разделе 2.5.

Определение 5.1. Достоверность функционирования ДУ - это свойство, которое определяется способностью средств контроля фиксировать правильность или ошибочность его функционирования [108].

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

Достоверность работы ДУ характеризуется достоверностью функционирования и достоверностью правильного функционирования.

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

Определение 5.3. Пропуск ошибки - это ситуация, при которой устройство работает неправильно, но сигнал ошибки отсутствует.

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

Достоверность функционирования [122]:

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

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

Достоверность правильного функционирования :

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

Оценку достоверности работы самопроверяемого МСА проводем в соответствии с общей структурной схемой аппаратного контроля (рис. 5.2), где

- вероятность безотказной работы исходной контролируемой схемы;

- вероятность безотказной работы схемы контроля;

- вероятность безотказной работы схемы сравнения (решающего органа).

Рис. 5.2. Структурная схема аппаратного контроля.

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

где - вероятность обнаружения ошибок выбранным методом контроля.

При этом можно записать:

Вероятность безотказной работы в течение наработки t = 10000 ч [109]:

вероятность обнаружения ошибки методом контроля на четность [71]:

где - кратность ошибки.

Теперь определим достоверность работы самопроверяемого МСА:

Надежность работы всего устройства снижается в результате ввода дополнительной аппаратурной избыточности, но при этом повышается вероятность обнаружения ошибки. Выполненные расчеты показывают, что ошибки нечетной кратности всегда обнаруживаются самопроверяемым МСА. Ошибки четной кратности обнаруживаются с вероятностью 0,9772. Следовательно, введение схемы встроенного контроля повышает достоверность работы многоканального сигнатурного анализатора и вероятность обнаружения ошибки.

5.3 Краткое описание и анализ ПЛИС ALTERA MAX 7000

Семейство ПЛИС ALTERA MAX 7000 представляет собой перепрограммируемые (EEPROM) устройства, основанные на архитектуре массивов матриц второго поколения. Характеристики семейства MAX 7000 приведены в табл. 5.1 [110].

ПЛИС MAX 7000 содержат от 32 до 256 макроячеек, которые объединены в группы по 16 макроячеек, называемые блоками сетевой логики. Каждая макроячейка состоит из матрицы с программируемыми элементами И и фиксированными элементами ИЛИ и реконфигурируемого регистра с независимо программируемыми функциями синхронизации, разрешения синхронизации, сброса и установки. Для реализации сложных логических функций каждая макроячейка может быть дополнена как общими расширителями элементарных конъюнкций (ЭК), так и высокоскоростными параллельными расширителями ЭК для обеспечения до 32 ЭК на макроячейку.

Архитектура MAX7000 (рис. 5.3), включает следующие элементы:

- блоки сетевой логики (БСЛ);

- расширители элементарных конъюнкций (ЭК);

- матрица программируемых внутренних соединений;

- блок управления вводом/выводом.

Таблица 5.1.

Краткие характеристики ПЛИС семейства MAX 7000.

Характеристика	EPM 7032	EPM 7064	EPM 7096	EPM 7128	EPM 7160	EPM 7192	EPM 7256
Число эквивалентных вентилей	600	1250	1800	2500	3200	3750	5000
Макроячейки	32	64	96	128	160	192	256
Блоки сетевой логики	2	4	6	8	10	12	16
Максимальное число выводов	36	68	76	100	104	124	164
Время задержки прохождения сигнала, нс	6	5	7,5	6	6	7,5	7,5
Тактовая частота, МГц	151,5	178,6	125	151,5	151,5	125	125

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

Множество БСЛ связано между собой через программируемую матрицу внутренних соединений (ПМВС), глобальные шины, которые распределяют все специализированные входы, входы/выходы ПЛИС и макроячейки.

Макроячейки в устройствах МАХ7000 могут быть сконфигурированы для выполнения последовательностных либо комбинационных схем. Макроячейки состоят из 3 функциональных блоков: матрицы логических операций, матрицы выбора ЭК и программируемого регистра (рис. 5.4).

Каждый БСЛ включает в себя 16 общих расширителей, которые могут рассматриваться как накопители одиночных ЭК (по одному от каждой макроячейки). Каждый общий расширитель может использоваться отдельно любой макроячейкой или совместно всеми макроячейками БСЛ для реализации сложных логических функций. При использовании общих расширителей неизбежна задержка ().

ПЛИС MAX 7000S программируются через стандартный JTAG интерфейс [3]. Архитектура MAX 7000S самостоятельно вырабатывает высокое напряжение, необходимое для программирования EEPROM - ячеек, что позволяет проводить программирование системы при помощи единого напряжения 5 В. Во время программирования входы/выходы ПЛИС находятся в состоянии высокого импеданса во избежание конфликтов на плате.

5.4 Моделирование модулей сигнатурного мониторинга, реализованных на ПЛИС ALTERA MAX 7000S

VHDL - модели модулей сигнатурного мониторинга реализованы на ПЛИС ALTERA MAX 7000S:

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

Генератор последовательности де Брейна на основе многочлена .

Генератор последовательности де Брейна на основе многочлена .

Генератор М - последовательности на СКА разрядности 12 со следующими правилами: 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150.

Генератор М - последовательности на СКА разрядности 16 со следующими правилами: 150, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150, 90, 150.

Исходными данными для программы моделирования MAX + PLUS II являются описания схем, выполненные на языке VHDL, представленные в приложении В.5. Схема самопроверяемого многоканального сигнатурного анализатора (1) реализована на ПЛИС EPM 7064 SLC 84 - 5. Схемы генераторов последовательностей де Брейна (2) и (3), генераторов М - последовательностей на СКА (4) и (5) реализованы на ПЛИС EPM 7032 SLC 44 - 6. Аппаратные затраты приведены в табл. 5.2. Временные задержки распространения сигнала от тактового входа на выход D - триггера приведены в табл. 5.3 и 5.4.

Таблица 5.2

Аппаратные затраты на реализацию схем пп. 1 - 5.

Устрой-ство	ПЛИС	Число входов	Число выходов	Число логич. клеток	Общие расширители	% использования ПЛИС
1	EPM7064SLC84-5	18	18	42	17	65 %
2	EPM7032SLC44-6	2	16	16	6	51 %
3	EPM7032SLC44-6	2	16	16	6	51 %
4	EPM7032SLC44-6	2	12	12	0	37 %
5	EPM7032SLC44-6	2	16	16	0	50 %

Таблица 5.3

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

Выводы	А	В	D1	D2	D3	D4 - 16
Clk	21,8 нс	3,2 нс	3,2 нс	3,2 нс	3,2 нс	3,2 нс

Таблица 5.4

Временные задержки генераторов пп. 2 - 5.

Устройство	Выводы	D1	D2	D3	D4	D5	D6 - 16
2	Clk	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс
3	Clk	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс
4	Clk	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс
5	Clk	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс	4,0 нс

В результате проведенных экспериментов было установлено, что реализованная на ПЛИС EPM 7064 SLC 84 - 5 схема самопроверяемого многоканального сигнатурного анализатора (1) может работать на частоте 45 МГЦ, реализованные на ПЛИС EPM 7032 SLC 44 - 6 схемы генераторов последовательностей де Брейна (2) и (3) и схемы генераторов М - последовательностей (4) и (5) могут работать на частоте 150 МГЦ. При необходимости эту частоту можно увеличить путем выбора ПЛИС с меньшими временными задержками.



5.5 Выводы

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

Проведен анализ достоверности функционирования самопроверяемого МСА. Показано, что надежность работы всего устройства снижается на 1% из-за ввода дополнительной аппаратурной избыточности, однако при этом повышается вероятность обнаружения ошибки. Ошибки нечетной кратности всегда обнаруживаются самопроверяемым МСА. Ошибки четной кратности обнаруживаются с вероятностью 0,9772.

Получена реализация предложенных в разделах 2 - 4 методов синтеза самопроверяемого многоканального сигнатурного анализатора и генераторов тестовых последовательностей. Анализ временных характеристик синтезируемых устройств показал, что схема самопроверки МСА увеличила задержку распространения сигнала на этапе вход - контрольный выход (21,8 нс). Анализ аппаратной сложности показал, что схемы на основе КА реализованы без использования общих расширителей, в то время как для реализации генераторов последовательности де Брейна потребовалось использовать 6 расширителей.

ЗАКЛЮЧЕНИЕ

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

Основные научные и практические результаты:

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

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

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

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

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

Разработанные программно - аппаратные средства синтеза модулей сигнатурного мониторинга использовались при разработке диагностического обеспечения исполнительного автомата управления приводом ШЭМ - М системы управления и защиты реакторной установки, которые выполнялись на ОАО ХАРТРОН, в составе встроенных средств диагностирования системы автоматизированного управления выращиванием крупногабаритных монокристаллов в опытном производстве Института сцинтиляционных материалов НАН Украины (г. Харьков), в учебном процессе УкрГАЖТ и НТУ «ХПИ».

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Основы технической диагностики / Под ред. П.П. Пархоменко. - М.: Энергия. - 1976. - 460 с.

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

JTAG Boundary Scan Architecture Standard Proposal, Version 2.0. Technical Sub - Committee of the Joint Test Action Group. - March 30, 1988.

Беннетс Р.Дж. Проектирование тестопригодных логических схем: Пер. с англ. - М.: Радио и связь, 1990. - 176 с.

Aitken R.C. Nanometer technology effects on fault models for IC testing // Computer. - 1999. - № 11. - P. 46 - 51.

Cheng K.T., Krstic A. Current Directories in Automatic Test-Pattern Generation // Computer. - 1999. - № 11. - P. 58 - 64.

Foote T.G. at al. Testing the 500-MHz IBM S/390 Microprocessor //IEEE Design & Test of Computers. - 1998. - № 3. - P. 83 - 89.

Новеллино Д. Стандарт по периферийному сканированию - в центре внимания международной конференции по методам и средствам тестирования // Электроника. - 1990. - № 16. - С. 7 - 12.

Закревский Л.А., Калоша Е.П., Хаткевич Н. Н., Ярмолик В. Н. Метод граничного сканирования и его использование для тестирования цифровых устройств // Автоматика и телемеханика. - 1994. - № 1. - С. 3 - 31.

Быков Ю.В., Ярмолик В. Н. Синтез преобразователей псевдослучайных чисел для реализации самотестирования цифровых устройств, удовлетворяющих требованиям стандарта IEEE // Автоматика и телемеханика. - 1996. - № 4. - С. 148 - 154.

Хаханов В.И., Сысенко И.Ю., Абу Занух Халиль И.М. Проектирование тестов для структурно - функциональных моделей цифровых схем // Радиоэлектроника и информатика. - 1999. - № 3. - С. 51 - 59.

Williams T.W., Parker K.P. Design for testability. A survey // IEEE Trans. On Computers. - 1982. - Vol. C-31, №1. - P. 2 - 15.

McCluskey E.J. A survey of design for testability scan techniques // VLSI Design. - 1984. - №12. - P. 38 - 61.

Nicolaidis M. Self-Exercising checkers for unified built-in self-test // IEEE Trans. On Computer-Aided Design. - 1989. - Vol. 8, № 3. - P. 203 - 218.

Gupta S.K., Pradhan D.K. Can concurrent checkers help BIST? // Proc. IEEE Test Conference. - 1992. - P. 140 - 150.

Gupta S.K., Pradhan D.K. Utilization of on-line (concurrent) checkers during built-in self-test and vice versa // IEEE Trans. On Computers. - 1996. - Vol. C-46, № 1. - P. 63 - 73.

Barzilai Z. et al. Exhaustive generation of bit patterns with applications to VLSI self - testing // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 2. - P. 190 - 194.

McCluskey E.J. Verification testing - a pseudoexhaustive test technique// IEEE Trans. On Computers. - 1984. - Vol. C-33. - № 6. - P. 495 - 500.

McCluskey E.J., Bozorqui-Nesbat S. Design for autonomous test // IEEE Trans. On Computers. - 1981. - Vol. C-30, № 11. - P. 866 - 875.

Tang D.T., Woo L.S. Exhaustive test pattern generation with constant weight vectors // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 9. - P. 1145 - 1150.

Pradhan D.K. Sequential network design using extra inputs for fault detection // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 3. - P. 319 - 323.

Бондаренко М.Ф., Кривуля Г.Ф., Рябцев В.Г., Фрадков С.А., Хаханов В.И. Проектирование и диагностика компьютерных систем и сетей. - К.: НМЦ ВО. - 2000. - 306 с.

Savir J. Syndrome - testable design of combinatorial circuits // IEEE Trans. On Computers. - 1980. - Vol. C-29, № 6. - P. 442 - 451.

Barzilai Z. at al. VLSI self-testing based on syndrome technique // Proc. IEEE Test Conference. - 1982. - P. 102 - 109.

Miller D.M., Muzio J.C. Spectral fault signatures for internally unate combinatorial networks // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 11. - P. 1058 -1062.

Susskind A.K. Testing for verifying Walsh coefficients // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 2. - P. 198 - 201.

Hayes J.P. Transition count testing of combinatorial circuits // IEEE Trans. On Computers. - 1976. - Vol. C-25, № 6. - P. 613 - 620.

David R. Signature of multi-output circuits // Proc. 14-th Annu. Int. Symp. Fault-Tolerant Computing. - 1984. - P. 366 - 371.

Уильямс Т.У., Паркер К.П. Проектирование контролепригодных устройствю - ТИИЭР, 1983. - Т. 71, № 1, с. 122 - 139.

Халчев В.Ф. Преобразование структурного автомата с памятью к пригодному для контроля виду // Автоматика и телемеханика. - 1975. - № 9. - с. 189 - 197.

Williams T.M., Parker K.P. Testing logic networks and designing for testability // Computer. - 1979. - № 10. - P. 42 - 53.

Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. - М.: Радио и связь, 1989. - 208 с.

Fujiwara E., Muto N., Matsuoka K. A self-testing group parity prediction checker and its use for built-in testing // IEEE Trans. On computers. - 1984. - Vol. C-33, №6. - P. 578 - 583.

Sogomonyan E.S., Goessel M. Design of self-testing and on-line fault detection combinatorial circuits with weakly inderendent outputs // Electronic Testing: Theory and Applications. - 1993. - № 4. - P. 267 - 281.

Согомонян Е.С. Достоверность самотестирования с использованием средств функционального диагностирования // Автоматика и телемеханика. - 1988. - №10. - с. 154 - 160.

Литиков И.П., Согомонян Е.С. Тестово-функциональное диагностирование цифровых устройств и систем // Автоматика и телемеханика. - 1985. - № 3. - с. 111 - 121.

Sedmak R.M. Design for self-verification. An approach for dealing with testability problems in VLSI-based design // Proc. IEEE Test Conference. - 1979. - P. 112 - 120.

Kim K. at al. On using signature registers as pseudo-random pattern generators in built-in self-testing // IEEE Trans. On Computer-Aided Design. - 1988. - Vol. 7, № 8. - P. 919 - 928.

Гессель М., Согомонян Е.С. Построение кодоразделительных самопаритетных комбинационных схем для самотестирования и функционального диагностирования // Автоматика и телемеханика. - 1996. - № 11. - с. 155 - 165.

Сперанский Д.В. Об одном методе синтеза схем встроенного контроля для комбинационных устройств // Автоматика и телемеханикаю - 1996. - № 4. - с. 155 - 161.

Friedman A.D. A functional approach to efficient fault detection in iterative logic arrays // IEEE Trans. On Computers. - 1994. - Vol. 43, № 12. - P. 1365 - 1375.

Namjoo M. Techniques for concurrent checking of VLSI processor operation // IEEE Test Conference. - 1982. - P. 461 - 468.

Устройство для контроля выполнения программ (его варианты): А.с. 1315981 СССР, МКИ G06 F 11/26/ В.В. Антосик, Л.В. Дербунович, А.Н. Мызь (СССР). - № 3888708/24; Заявл. 22.04.85; Опубл. 07.06.87, Бюл. № 21. - 58 с.

Романкевич А.М., Валуйский В.Н., Остафин В.А. Стркутурно - временная избыточность в управляющих системах. - К.: Вища школа. - 1979. - 160 с.

Скобцов Ю.А., Иванов Д.Е. Параллельное моделирование функциональных неисправностей // Техническая диагностика и неразрушающий контроль. - 1998. - № 3. - С. 43 - 47.

Миков И.Н., Дербунович Л.В., Нешвеев В.В., Мечникова Е.А. Программируемые контроллеры повышенной надежности для управления автоматическими линиями. Обзор. - М.: НИИмаш, 1984. - 52 с.

Беличенко Т.П., Белов Г.И., Дербунович Л.В. Нахождение кратчайшей различающей последовательности для конечного автомата // Гибридные вычислительные машины и комплексы. - К.: Наукова думка, 1980. - Вып. 3. - с. 36 - 39.

Белов Г.И., Дербунович Л.В. Синтез контролепригодных дискретных устройств с элементами памяти // Техническая диагностика, эксплуатация управляющих и вычислительных машин. - К.: Наукова думка, 1980. - с. 76 - 85.

Горяшко А.П. Синтез и проектирование легко тестируемых цифровых элементов и устройств: Дис. … докт. техн. наук: 05.13.05 - М., 1986. - 266 с.

Дербунович Л.В., Белов Г.И. Проверочный эксперимент для класса инициальных последовательных автоматов // Локальные автоматизированные системы автоматики. - К.: Наукова думка, 1979. - с. 93 - 102.

Каширова Л.Ф. Построение контролируемых автоматов. ч. 1, 2 // Автоматика и телемеханика. - 1983. - № 11. - с. 141 - 146. - № 12. - с. 115 - 121.

Сперанский Д.В. Методы преобразования структур дискретных систем с целью повышения их контролепригодности и оптимизации процессов диагностирования: Дисс. … докт. техн. наук: 05.13.05. - К., 1983. - 334 с.

Fujiwara H., Kinoshita K. Design of diagnosable sequential machines utilising extra outputs // IEEE Trans. On Computers. - 1974. - Vol. C-23, № 2. - P. 138 - 145.

Kohavi Z., Lavalee P. Design of sequential machines with fault detection capabalities // IEEE Trans. Electr. Comput. - 1967. - Vol. EC-16, № 8. - P. 473 - 484.

Fujiwara H. et al. Easily testable sequential machines with extra outputs // IEEE Trans. On Computers. - 1975. - Vol. C-24, № 8. - P. 821 - 826.

Fujiwara H., Kinoshita K. Checking experiments for stable memory faults in sequential machines // Journal of Design automation & Fault-Tolerant Computing. - 1978. - Vol. 2, № 1. - P. 3 - 14.

Murakami S., Kinoshita K., Ozaki H. Sequential machines capable of fault diagnosis // IEEE Trans. On Computers. - 1970. - Vol. C-19, № 11. - P. 1079 - 1085.

Phatte S.M., Abraham J.A. Test generation for microprocessors // IEEE Trans. On Computers. - 1980. - Vol. C-29, № 6. - P. 429 - 441.

Тоценко В.Г. Технический диагноз дискретных устройств с элементами памяти: Дис. … докт. техн. наук: 05.13.05. - К., 1975. - 298 с.

Bhattacharyya A. On novel approach of fault-detection in an easily testable sequential machine with extra inputs and extra outputs // IEEE Trans. On Computers. - 1983. - Vol. C-32, № 3. - P. 323 - 325.

Das S.R., Chen Z., Dai Y.L. Easily testable sequential machines with extra inputs and extra outputs // Electronic Letters. - 1980. - Vol. 16, № 2. - P. 119 - 121.

Hennie F.C. Fault detection experiments for sequential circuits // Proc. 5-th Symp. On Switching Circuits Theory and Logical Design. - 1964. - P. 95 - 110.

Bardell P.H., McAnney W.H., Savir J. Built-in Test for VLSI: Pseudorandom techniques. - New York: John Wiley & Sons, 1987. - 274 p.

Генератор псевдослучайных чисел: А.с. 1377167 CCCР, МКИ G06 F 11/26/ Л.В. Дербунович, В.Ф. Бохан, И.Г. Либерг (CCCР). - №4022981/21; Заявл.07.02.86; Опубл. 30.09.87, Бюл. № 39. - 112 с.

Fredricksen H. A Survey of full length nonlinear shift register cycle algorithms // SIAM Review. - 1982. - Vol. 24, № 2. - P. 195 - 221.

Srinivasan R., Gupta S.K., Breuer M.A.. Novel test pattern generators for pseudorandom testing // IEEE Trans. On Computers. - 2000. - Vol. C-49, № 11.- P. 1228 - 1240.

Tang D.T., Chen C.L. Logic test pattern generation using linear codes // IEEE Trans. On Computers. - 1984. - Vol. C-33, № 9. - P. 845 - 850.

Barzilai Z., Savir J., Markovsky G., Smith M.G. The weighted syndrome sums approach to VLSI testing // IEEE Trans. On Computers. - 1981. - Vol. C-30, № 12. - P. 996 - 1000.

Wang L.T., McCluskey E.J. Condensed linear feedback shift register testing - a pseudoexhaustive test technique // IEEE Trans. On Computers. - 1986. - Vol. C-35, № 4. - P. 367 - 370.

Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976. - 600 с.

Гессель М., Согомонян Е.С. Функционально-тестовое диагнострование на основе сохраняющего четность сигнатурного анализатора // Автоматика и телемеханика. - 1998. - № 5. - С. 162 - 171.

Ralston A. De Bruijn sequences - a model example of interaction of discrete mathematics and computer science // Am. Math. Monthly. - 1982. - Vol.55,№3. - P. 131 - 143.

Lempel A. On homomorphism of the de Bruijn graph and its application to the design of feedback shift registers // IEEE TC. - 1970. - Vol.19, №12. - P. 1204 - 1209.

Blelloch G.E. NESL: a nested data-parallel language // Tehnical report CMU - CS - 94, 1994.

Raimund Ubar. Test synthesis with alternative graphs // IEEE Design & Test of Computers. - 1996. - 1. - P. 48 - 57.

Golomb W.S. Shift register sequences. - Laguna Hills, CA: Aegean Park Press, 1982.- 341 p.

Пападимитриу Х. Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир,1995. - 512 с.

Annexstein F.S. Generating de Bruijn sequences: An efficient Implementation // IEEE Trans. On. Computers. - 1997. - Vol. C-46, №2. - P.198 - 200.

Басакер Р., Саати Т. Конечные графы и сети. - М.: Наука, 1974. - 482 с.

Fredricksen H., Maiorana J. Necklaces of beads in k colors and k-ary de Bruijn sequences // Discrete Mathematics. - 1978. - № 23. - P. 207 - 210.

Maitra K.K. Cascaded switching networks of two-input flexible cells // IRE Trans. Electr. Computers. - 1964. - Vol. EC-13, № 4. - P. 136 - 143.

Варшавский В.И., Мараховский В.Б. и др. Однородные структуры. (Анализ. Синтез. Поведение.). - М.: Энергия, 1973. - 248 с.

Mukhopadhyay A. Unate cellular logic // IEEE Trans. On Computers. - 1969. - Vol. C-18, № 2. - P. 114 - 121.

Weiss C.D. The characterization and properties of cascade realizable switching functions // IEEE Trans. On Computers. - 1969. - Vol. C-18, № 7. - P. 624 - 633.

Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432 с.

L. Wang, M. Marhoefen, E.J. McCluskey. A self - test and self - diagnosis architecture for boards using boundary scan // Technical report, Center for Reliable Computing, 1989. - P. 20 - 27.

Berlekamp E.R., Conway J.H., Guy R.K. Winning ways for your mathematical plays. - New York: Academic Press, 1982. - Vol. 2. - Chap. 25.

W. Pries, A. Thanailakis, and H.C. Card. Group properties of cellular automata and VLSI applications // IEEE Trans. Comput. - 1986. - vol. C-35. - p. 1013 - 1024.

P.D. Hortensius, R.D. McLeod, W. Pries, D.M. Miller and H.C. Card. Cellular automata - based pseudorandom number generators for built - in self - test. // IEEE Trans. CAD. - 1989. - № 8 - p. 842 - 859.

C.R. Gloster, F. Borglez. Boundary scan with cellular - based built - in self - test // Proc. Intern. Test Conference - 1988. - p. 138 - 145.

P.D. Gortensius, H.C. Card, R.D. McLeod, W. Pries. Importance sampling for using computers using one - dimensional cellular automata. // IEEE Trans. Comput. - 1989. - Vol. C-38, № 6. - p. 769 - 774.

P.D. Gortensius, H.C. Card, R.D. McLeod. Parallel random number generation for VLSI systems using cellular automata. // IEEE Trans. Comput. - 1989. - Vol. C-38, № 10. - p. 1466 - 1473.

Neebel D.J., Kime C.R. Cellular automata for weighted random pattern generation // IEEE Trans. On Computers. - 1997. - Vol. C-46,№ 11. - P. 1219 - 1228.

Hortensius P.D., McLeod R.D., Card H.C. Cellular automata-based signature analysis for built-in self-test // IEEE Trans. On Computers. - 1990. - Vol. C-39, № 10. - P. 1273 - 1283.

A.K. Das, M. Pandey, A. Gupta, and. P. Pal Chaudhuri. Built - in self - test structures around cellular automata and counters. // IEE Proc. Part (E). - 1990. - Vol. 137, № 7. - P. 268 - 276.

Мур Е.Ф. Умственные эксперименты с последовательными машинами. // Автоматы: Пер. с англ. - М.: Физматгиз, 1956, с. 179 - 213.

E.J. McCluskey. Built - in verification test // Proc. Intern. Test Conference. - 1982. - P. 183 - 190.

Wolfram S. Computation theory of cellular automata // Communications in Mathematical Physics. - 1984. - Vol. 93. - P. 15 - 57.

Wolfram S. Statistical mechanics of cellular automata // Reviews of Modern Physics. - 1983. - Vol. 55, № 3. - P. 601 - 644.

Das A.K. at al. Efficient characterization of cellular automata // IEE Proc. Part (E). - 1990. - Vol. 137, № 1. - p. 81 - 87.

O. Martin, A.M. Odlyzko, and S. Wolfram. Algebraic properties of cellular automata. // Communications in Mathematical Physics. - 1984. - Vol. 93. - p. 219.

Гантмахер Ф.Р. Теория матриц. - М.: Изд-во технико - теоретич. литературы, 1954. - 492 с.

Воеводин В.В. Вычислительные основы линейной алгебры. - М.: Наука, 1977. - 304 с.

Клименко Н.Н., Кисель В.В. , Замарин А.И. Сигналы с расширением спектра в системах передачи информации // Зарубежная радиоэлектроника. - 1983. - № 11. - С. 45 - 59.

Спельмашенко Б.Г., Тараненко П.Г. Нелинейные псевдослучайные последовательности в широкополосных системах передачи информации // Зарубежная радиоэлектроника. - 1988. - № 9. - С. 3 - 16.

Chan A.H., Games R.A., Key E.L. On the complexity of de Bruijh sequences // Journal of Combin. Theory. - 1982. - Vol. 33, № 4. - P. 233 - 246.

Games R.A., Chan A.H. A fast algorithm for determining the complexity of a binary sequences with period 2n // IEEE Trans. On Inform. Theory. - 1983. - Vol. 29, № 1. - P. 144 - 146.

Щербаков Н.С. Влияние аппаратного контроля на критерии надежности дискретных устройств // Теоретические и прикладные вопросы проектирования систем управления. - Киев: Наукова думка, 1980. - С.141 - 149.

ALTERA reliability report 4.0 // www.altera.com/literature/rr/rr.pdf

ALTERA MAX 7000S СPLD Overview // www.altera.com/products/devices/max7k/ overview/m7k-overview.html

Дербунович Л.В., Суздаль В.С., Тавровский И.И., Темников И.Н. Отказоустойчивые микроконтроллеры на основе сигнатурного мониторинга // Информационно - управляющие системы на железнодорожном транспорте. - 2002. - №4, 5. - с. 71 - 73.

Дербунович Л.В., Темников И.Н. Синтез самопроверяемого сигнатурного анализатора // Вестник ХГПУ. - Харьков: ХГПУ. - 2000. - Вып. 92. - с. 100 - 103.

Бережная М.А., Дербунович Л.В., Суздаль В.С., Тавровский И.Н., Темников И.Н. Отказоустойчивые системы управления на основе микроконтроллеров // Вестник НТУ ХПИ. - Харьков: НТУ ХПИ. - 2002. - Вып. 12. - с. 218 - 220.

Дербунович Л.В., Темников И.Н., Косс М.Н. Оптимальное кодирование состояний автомата // Информационно - управляющие системы на железнодорожном транспорте. - 2000. - №2. - с. 70 - 73.

Дербунович Л.В., Татаренко Д.А., Темников И.Н. Генераторы тестов для дискретных ДУ с самотестированием // Информационно - управляющие системы на железнодорожном транспорте. - 2004. - № 1. - с. 40 - 45.

Темников И.Н. Генератор нелинейной псевдослучайной тестовой последовательности // Вестник ХГПУ. - Харьков: ХГПУ. - 2000. - Вып. 112. - с. 130 -134.

Дербунович Л.В., Косс М.Н., Темников И.Н. Синтез легко тестируемых дискретных устройств // Вестник ХГПУ. - Харьков: ХГПУ. - 2000. - Вып. 102. - с. 46 - 51.

Темников И.Н. Генераторы последовательностей максимальной длины на клеточных автоматах // Тр. 7 - й Междунар. конф. «Теория и техника передачи, приема и обработки информации». - Харьков - 2001. с. 297 - 298.

Бережная М.А., Дербунович Л.В., Темников И.Н. Диагностирование ПЛИС на основе моделей клеточных автоматов // Информационно - управляющие системы на железнодорожном транспорте. - 2002. - приложение к журналу №4, 5. - с. 33.

Темников И.Н. Методика синтеза генераторов М - последовательностей на клеточных автоматах // Системы обработки информации. Сборник научных трудов. - Харьков: НАНУ, ПАНМ, ХВУ, 2001. - Вып. 6(16), с. 120 - 122.

Темников И.Н. Анализ сложности нелинейных последовательностей максимальной длины // Автоматизированные системы управления и приборы автоматики. - 2001. - Вып. 117. - с. 48 - 49.

Темников И.Н. Достоверность работы самопроверяемого многоканального сигнатурного анализатора // Информационно - управляющие системы на железнодорожном транспорте. - 2003. - № 6. - с. 82 - 84.

модуль сигнатурный мониторинг микроконтроллерный

ПРИЛОЖЕНИЕ А

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

А.1. Доказательство утверждения 4.3: Необходимость. Для того, чтобы выполнялось условие необходимо, чтобы . Это следует из того факта, что если , то при условии .

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

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

:

где - целое число.

Пусть - целое число такое, что . Чтобы доказать, что также образует циклические последовательности, покажем, что существует такое , что:

Для :

Поскольку выполняется операция сумма mod 2 и , то можно сделать вывод, что такое существует. Утверждение доказано.

А.3. Доказательство утверждения 4.5: Пусть R - строгое правило эволюции СКА (т.е. все клетки описываются одинаковым правилом). Пусть соответствует гибридной СКА длины с любой перестановкой и соседних клеток СКА. Любая перестановка может быть представлена общей формулой:

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

Если существует такое , что , то, согласно Лемме 4.4, также существует такое , что:

Утверждение доказано.

А.4. Доказательство утверждения 4.6: Если для существует циклическая последовательность длиной , то

при условии, что - ненулевой вектор. Из теории матриц известно, что если , то существует по крайней мере один ненулевой вектор такой, что

Отсюда

Утверждение доказано.

А.5. Доказательство утверждения 4.7: Проведем доказательство от противного: Пусть порядок цикла равен и существует цикл длиной и при этом не является делителем .

Тогда ; и - целые числа и и для ненулевого вектора является наименьшим целым числом таким, что .

Так как

То

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

А.6. Доказательство утверждения 4.11: Рассмотрим отображение цикла, содержащего наборы, которые вырабатываются СРЛОС (цикл 1), в цикл, содержащий наборы, которые вырабатываются СКА (цикл 2):

Для набора a в цикле 1 и набора b в цикле 2 можно записать:

и для всех в цикле 1,

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

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



ПРИЛОЖЕНИЕ Б

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

(1)	(2)
(3)	(4)
(5)	(6)
(7)	(8)
(9)	(10)
(11)	(12)

ПРИЛОЖЕНИЕ В

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

В.1. Определение линейной зависимости остатков для (n, m, k) схемы на МСРЛОС/СР.

Программа написана на языке программирования Delphi 7. По алгоритму (раздел 2.2) программа осуществляет определение линейной зависимости остатков для (n,m,k) схемы на основе МСРЛОС/СР. Программа также хранит все остатки полинома СР, полученные делением многочленов. Деление многочленов, считывание остатков в массив, сравнение массивов, сортировка входного массива осущетвлены отдельными функциями. С помощью данной программы осуществляется синтез ГПТ схем для степеней полиномов .

unit fMain;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Spin, ComCtrls,Math, Grids, cxControls, cxContainer,

cxEdit, cxTextEdit, cxMaskEdit, cxSpinEdit, cxCheckBox, Buttons,

cxTimeEdit, ExtCtrls, cxDropDownEdit;

type

TfrmMain = class(TForm)

StatusBar1: TStatusBar;

StringGrid1: TStringGrid;

Panel1: TPanel;

Label1: TLabel;

Label2: TLabel;

Label4: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

SpeedButton1: TSpeedButton;

SpinEdit1: TSpinEdit;

Button1: TButton;

SpinEdit2: TSpinEdit;

cxCB1: TcxCheckBox;

cxCB2: TcxCheckBox;

cxCB3: TcxCheckBox;

cxCB4: TcxCheckBox;

cxCB5: TcxCheckBox;

cxCB6: TcxCheckBox;

cxCB7: TcxCheckBox;

cxCB8: TcxCheckBox;

cxCB9: TcxCheckBox;

cxCB10: TcxCheckBox;

cxCB11: TcxCheckBox;

cxCB12: TcxCheckBox;

cxCB13: TcxCheckBox;

cxCB14: TcxCheckBox;

cxCB15: TcxCheckBox;

cxCB16: TcxCheckBox;

Edit2: TEdit;

cxTimeEdit1: TcxTimeEdit;

cxTimeEdit2: TcxTimeEdit;

Label8: TLabel;

Label9: TLabel;

Splitter1: TSplitter;

cxComboBox1: TcxComboBox;

procedure Button1Click(Sender: TObject);

procedure SetSi;

procedure FormCreate(Sender: TObject);

procedure SpinEdit1Change(Sender: TObject);

procedure SpeedButton1Click(Sender: TObject);

procedure cxCBClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

Cx=array[1..16] of TcxCheckBox ;

Tx=array [0..16] of integer;

Ex=array of array of integer;

function DevPOL (var x0,x1:Tx) :Tx;

function ReadPOL:Tx;

function SortSheiker(var x0:Tx;r:integer):Tx;

var

frmMain: TfrmMain;

Lab:Cx;

Si:Tx;

implementation

{$R *.dfm}

function DevPOL (var x0,x1:Tx) :Tx;

var

x2,x3,x4:Tx;

i:integer;

z1,z2:integer;

begin

x2[0]:=1;

while x0[1]>=x1[1] do begin

for i:=1 to x2[0] do x2[i]:=x0[1]-x1[1];

for i:=1 to x1[0] do x3[i]:=x1[i]+x2[1];

x3[0]:=x1[0];

x4[0]:=0;

z1:=1;

z2:=1;

while (z1<=x3[0]) or (z2<=x0[0]) do begin

if (z1<=x3[0]) and (z2<=x0[0]) then begin

if x3[z1]=x0[z2] then begin

inc(z1);

inc(z2);

end else

if x3[z1]>x0[z2] then begin

inc(x4[0]);

x4[x4[0]]:=x3[z1];

inc(z1);

end else begin

inc(x4[0]);

x4[x4[0]]:=x0[z2];

inc(z2);

end;

end else if (z1>x3[0]) then begin

inc(x4[0]);

x4[x4[0]]:=x0[z2];

inc(z2);

end else begin

inc(x4[0]);

x4[x4[0]]:=x3[z1];