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

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

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

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

(Zi ,Xa)=(Zi ,Xa)=Z'j ,Zi , ZjZ , XaX , (3.10)

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

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

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

Определение 3.8 Пусть ячейка одномерной сети представлена моделью автомата Мура (Х, Z, ). Множество входных символов Xc={ X1, X2, …, Xr } называется множеством входных характеристических символов тогда и только тогда, когда для любой пары состояний (Zа , Zb) Z автомата (Za ,X1)(Za ,X2) … (Za ,Xr) (Zb ,X1)(Zb ,X2) … (Zb ,Xr) (3.11)

Определение 3.9 Пусть Z'={ Z1, Z2, Z3, … Zr } подмножество состояний минимального автомата А. Множество Хс={ X1, X2, X3, … Xp } , будем называть множеством характеристических последовательностей, если для каждого начального состояния ZiZ', реакция на Хс различна, то есть

(Z ,X1)(Zi ,X2) … (Zi ,Xp) (Zj ,X1)(Zj ,X2) … (Zj ,Xp) Zi Zj,

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

Множество отличительных и характеристических символов может быть найдено из характеристического дерева автомата ячейки сети, которое строится по правилам, приведенным в разделе 1.5 [1]. На рисунке 3.4 приведено характеристическое дерево сети (рисунок 1.2), из которого следует, что символ X1=1 является отличительным для множества состояний {Z0, Z1, Z2, Z3} символ X0=0 для состояний Z2 и Z3. Пара состояний {Z0, Z1} является X0-совместимой.

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

Характеристическое дерево ячейки сети, представленной автоматной диаграммой в таблице 3.4, приведено на рисунке 3.5, из которого можно найти множество отличительных и характеристических символов. Так как произведение разбиений =() и =() равно (0), то множество Хc={ X1, X3 } является множеством входных характеристических символов. Простые - множества для каждой вершины характеристического дерева определяют множества состояний, для которых метка вершины дерева является отличительным входным символом. Исключения составляют лишь те простые - множества, которые являются состояниями преемниками, принадлежащими множеству Zc то есть множеству состояний, неразличимых для всех входных символов.

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

 = {Z3, Z4} ; = {Z1, Z3, Z4} ; = {Z1, Z3}, (3.13)

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

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

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

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

Zc= ={Z3}, (3.14)

Определив множество Zc , из характеристического дерева можно легко найти множество отличительных символов и состояний ячейки, которые различаются этими символами в соответствии с определением 3.7. Для рассматриваемого примера состояние Z1, различается символом X1, состояния Z2 и Z4 - символом X3.

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

(Zj ,Xт) (Zi ,Xт) , ZiZ[Zj] . (3.15)

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

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

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

Zj Zk+1Zk+2… Zp-1Zp , (3.16)

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

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

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

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

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

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

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

Z1 - X2 ; Z2 - X2 ; Z3 - X3 ; Z4 - X1 (3.17)

Автомат удовлетворяет условию теоремы 3.1, следовательно, он имеет циклическую отличительную последовательность. Последовательность переходов по отличительным символам

Z1Z2Z3Z4Z4 завершается циклом Z4Z4.

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

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

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

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

Z1 - X1 ; Z2 - X2 ; Z3 - X3 ; Z4 - X1; (3.18)

Последовательность переходов Z1Z3Z0Z2Z1 является циклической отличительной последовательностью.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а)

б)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) ;

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

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

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

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

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

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

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

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

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

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

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

6) Sl= vi.

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

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

9) l=l+1;

10) Sl(1)=vi;

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

12) Конец.

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

1. n=8

2. k=7

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

1. 4, 33, 128, 50, 146, 101, 17, 17

2. 9, 65, 34, 5, 144, 195, 101, 65

3. 9, 129, 193, 212, 152, 33, 135, 21

4. 2, 9, 193, 66, 168, 200, 160, 20

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

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

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

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

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

Маркетинговые исследования включают:

описание товара;

назначение товара;

область применения;

расчеты по определению емкости;

сегментация рынка по потребителям и конкурентам;

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

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

6.2 Исследования и анализ рынков сбыта

6.2.1 Сегментация рынка по потребителям

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

Таблица 6.2 - Сегментация рынка по потребителям

Область использования	Код сегмента	Потребители
		1	2	3
Исследовательские лаборатории	А	+
Конструкторские бюро	Б		+
Организации по разработке специализированной аппаратуры	В			+

Группы потребителей:

1 - сотрудники НИИ;

2 - инженеры электронщики и разработчики электронных устройств;

3 - прочие разработчики.

6.2.2 Анализ емкости сегментов

Данные об анализе сегментов рынка представлены в таблице 6.3.

Таблица 6.3 - Емкость сегментов рынка

Область использования (сегменты)	Количество объектов, которые будут использовать изделие (шт.)	Предполагаемое число продаж одному объекту (шт.)	Предполагаемая емкость сегмента (шт.)
Исследовательские лаборатории	15	1	15
Конструкторские бюро	25	1	25
Организации по разработке специализированной аппаратуры	5	1	5
Итого емкость рынка	45

6.2.3 Параметрическая сегментация рынка

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

Таблица 6.4 - Параметрическая сегментация рынка

Параметры	Код сегмента	Итого	% к общему итогу
	А	Б	В
Цена	4	5	4	13	22,6
Простота реализации	5	5	5	15	25,8
Скорость работы	5	5	5	15	25,8
Коэффициент покрытия неисправностей	5	5	5	15	25,8
Итого	58	100,0

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

6.3 Оценка затрат на разработку продукта

6.3.1 Определение потребности в материальных ресурсах

Оценивается объем материальных ресурсов для производства программного продукта.

Стоимость материальных затрат приведена в таблице 6.5.

Таблица 6.5 - Покупные материалы при разработке данного продукта

Материалы	Количество (шт.)	Стоимость	Общая стоимость	Назначение
Дискеты	4	2,50	10,00	Сохранение программы
Бумага	500	0,04	20,00	Распечатка исходных текстов
Картридж для принтера	1	99,00	99,00	Распечатка документации текстов программ
Суммарная стоимость	141,00

6.3.2 Расчет основной заработной платы на разработку программы

В таблице 6.6 приведена оценка основной заработной платы

Таблица 6.6 - Расчет заработной платы (в гривнах)

Должность	Оклад	Количество исполнителей	Время занятости (в месяцах)	Основная заработная плата
Руководитель темы	250	1	3	150,00 (процент участия 20%)
Итого	150,00

6.3.3 Расчет дополнительной заработной платы

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

Дополнительная заработная плата = 150 * 0,1 = 15 грн.

6.3.4 Отчисления на социальные мероприятия

а) Отчисления в пенсионный фонд составляют 32% от основной заработной платы.

Отчисления в пенсионный фонд = 150 * 0,32 = 48 грн.

б) Отчисления на медицинское страхование составляют 4% от основной заработной платы.

Отчисления на медицинское страхование = 150*0,04 = 6 грн.

в) Отчисления в фонд занятости составляют 1,5% от основной заработной платы.

Отчисления в фонд занятости = 150 * 0,015 = 2,25 грн.

6.3.5 Расчет машинного времени

Все работы по созданию проекта велись 3 месяца по 3 часа в день. Рабочих дней в месяце - 21. Цена за один час - 1 грн.

Стоимость машинного времени = 3 * 3 *21 *1 = 189 грн.

6.3.6 Расчет накладных расходов

Накладные расходы = 150 * 0,7 = 105 грн.

6.3.7 Расчет коммунального налога

Коммунальный налог составляет 10% минимальной заработной платы. На момент разработки проекта минимальная заработная плата составляла 118 грн.

Коммунальный налог = 11,80 грн.

6.3.8 Расчет себестоимости программного продукта

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

Себестоимость = 141+150+15+48+6+2,25+189+105+11,8 = 668,05 грн.

6.3.9 Расчет прибыли

Прибыль составляет 25% от себестоимости.

Прибыль = 668,05 * 0,25 = 167,01 грн.

6.3.10 Расчет оптовой цены

Оптовая цена состоит из себестоимости и прибыли.

Оптовая цена = 668,05 + 167,01 = 835,06 грн.

6.3.11 Расчет налога на добавочную стоимость

НДС на данный момент составляет 20% от оптовой цены.

Сумма НДС = 835,06 * 0,2 = 167,01 грн.

6.3.12 Расчет цены на продажу

Цена на продажу состоит из оптовой цены и налога на добавленную стоимость.

Цена на продажу = 835,06 + 167,01 = 1002,07 грн.

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

Таблица 6.7 - Калькуляция себестоимости (в гривнах)

Наименование статьи и затрат	Сумма
Стоимость материалов и покупных изделий	141,00
Основная заработная плата	150,00
Дополнительная заработная плата	15,00
Отчисления на социальные мероприятия в том числе:	-
- Отчисления на медицинское страхование	48,00
- Отчисления в пенсионный фонд	6,00
- Отчисления в фонд занятости	2,25
Стоимость машинного времени	189,00
Оптовая цена	835,06
НДС	167,01
Цена	1002,07

6.4 Экономическая эффективность научно-исследовательской работы

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

Определение экономической эффективности научно-исследовательской работы базируется на общих методах расчета сравнительной экономической эффективности новой техники.

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

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

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

Сущность этой методики состоит в том, что на основе оценок работы определяется коэффициент научно-технического эффекта НИОКР:

, (6.1)

где: ri - весовой коэффициент і-го признака научно-технического эффекта (таблица 4.8);

ki - количественная оценка і-го признака научно-технического эффекта научно-исследовательской работы.

Таблица 6.8 - Коэффициент весомости признаков

Признак научно-технического эффекта НИОКР	Значение весового коэффициента
Уровень новизны Теоретический уровень Возможность реализации	0,6 0,4 0,2

Классификатор признаков научной новизны принимается равным k1=7, так как уровень новизны разработки определяется как новая.

Классификатор признаков теоретического уровня принимается равным k2=6, так как производится разработка нового способа.

Классификатор признаков времени реализации принимается равным:

k3=k31+k32; (6.2)

k31= 10, так как время реализации в течение первых 4 лет;

k32=2, так как масштабы реализации в пределах нескольких предприятий.

Отсюда:

Нт = 0,6?7+0,4?10+0,2?(10+2)=10,6

Так как максимально возможное значение коэффициента научно-технического эффекта НИОКР Нт=12, то проведенный анализ позволяет сделать вывод о целесообразности проведения данной исследовательской работы.

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

7. Охрана труда и окружающей среды

7.1 Общие вопросы охраны труда и окружающей среды

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

Охрана труда - система правовых, социально-экономических, организационно-технических, санитарно-гигиенических и лечебно-профилактических мероприятий и средств, направленных на охрану здоровья и работоспособности человека в процессе труда (Закон Украины “Об охране труда” от 21.11.02) [22].

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

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

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

В данном разделе рассматриваются вопросы охраны труда и окружающей среды для дипломного проекта: “Модули сигнатурного мониторинга на клеточных автоматах”.

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

При выполнении данной работы использовалось такое оборудование: ПЭВМ, принтер, сканер, ксерокс.

Перечисленное оборудование использует напряжение промышленной электросети до 1000В, поэтому необходимо выполнять правила по безопасному ведению работы с электрооборудованием - ПУЭ-87 [23].

При работе на ПЭВМ на человека воздействует ряд опасных и вредных факторов, которые классифицируются согласно ГОСТ 12.0.003-74 [24]. Опасным фактором называется фактор, вызывающий травму или повреждение организма. Вредный фактор _ фактор, длительное воздействие которого приводит к патологии в организме _ профессиональным заболеваниям. Эти факторы разделяются на физические, химические, биологические и психофизические основные из них приведены в таблице 7.1.

Таблица 7.1 _ Перечень опасных и вредных факторов

Наименование фактора	Источник возникновения фактора	Характер воздействия на человека	Нормированные параметры и нормативные значения	Норматив- ный документ
1.Повышенный уровень статического электричества	ЭЛТ	Опасность поражения током, раздражение кожи	Потенциал не более 500 В.	ГОСТ 12.1.038-82 [25]
2 Повышенный уровень шума.	Устройства охлаждения ЭВМ, печатающие устройства	Утомление слуховых анализаторов	Уровень звука L < 50 дБА	ГОСТ12.1. 003-83 [26]
3 .Повышенная пульсация светового излучения.	Лампы дневного света.	Утомление зрения.	Коэффициент пульсаций, Кп=10	СНиП II-4-79 [27]
4.Статическая нагрузка.	Постоянная рабочая поза.	Влияние на ЦНС, утомление организма.		НПАОП 0.00-1.31-99 [28]
5. Недостаток естественного освещения	Неправильное расположение ПЭВМ	Утомление зрительного анализатора	КЕО=1, 0125%	СНиП II-4-79 [27]
6. Недостаток искусственного освещения	Неправильная планировка систем освещения	Утомление зрительного анализатора	Минимальная освещенность Е = 500-700лк	СНиП II-4-79 [27]
7. Отраженная блескость	Неправильное расположение ПЭВМ	Утомление зрительного анализатора	Должна отсутствовать в поле зрения	ДНАОП 0.00-1.31-99 [28]
8.Монотонность труда.	Особенности технологического процесса.	Влияние на ЦНС, утомление организма.		ДНАОП 0.00-1.31-99 [28]
9. Повышенное значение напряжения в электрической цепи.	Электрооборудование.	Опасность поражения электричеством.	Сила тока I=0.6 mA при U=220 V.	ГОСТ 12.1.038-82 [25]
10. Яркость экрана	Экран монитора ПЭВМ	Утомление зрительных анализаторов	В = 100 кд/м2	ДНАОП 0.00-1.31-99 [28]

7.2 Производственная санитария

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

7.2.1 Метеорологические условия помещения

Согласно ГОСТ 12.1.005-88 [29] оптимальные параметры микроклимата для выполнения работы должны находиться в пределах, указанных в таблице 7.2. Параметры являются оптимальными, так как категория работы III напряженная.

Категорию работы учитываем по физической нагрузке. Наша работа относится к категории Iа, то есть расход энергии при выполнении работы до 120 ккал/час и не требует физического напряжения.

Таблица 7.2 - Оптимальные параметры микроклимата

Категория работы	Период года	Температура t, c	Относительная влажность, ?,%	Скорость движения воздуха V, м/с
Легкая работа Iа	Холодный	22...24	40...60	0,1
Легкая работа Iа	Теплый	23...25	40...60	0,1

Для обеспечения вышеуказанных оптимальных метеорологических условий в помещении предусмотрена система отопления (общее паровое), вентиляции (общая приточно-вытяжная искусственная) и кондиционирование согласно СНиП 2.04.05-91 [30].

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

Режим работы кондиционера должен обеспечить максимально возможное поступление наружного воздуха, но не менее 50% от производительности кондиционера.

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

Качественный состав воздуха: содержание кислорода в дисплейном классе должно быть в пределах 21-22 об. %. Двуокись углерода не должна превышать 0,1 об. %, озон - 0,1 мг/м3, аммиак - 0,2 мг/м3, фенол - 0,01 мг/м3, хлористый винил - 0,005 мг/м3, формальдегид - 0,003 мг/м3 [29].

7.2.2 Характеристика производственного помещения

Разработка производилась в трехэтажном здании Электрокорпуса на кафедре “Автоматика и управление в технических системах”.

По категории пожароопасности здание относится к категории В - ОНТП - 24-86 [31], класс по пожарной опасности оборудования закрытого типа - П-IIа ПУЭ-87 [23], огнестойкость конструкции здания - II степени, согласно ДБН В1.1-7-2002 [32]. В помещениях имеется система пожаротушения в соответствии с ГОСТ 12.1.004-91 [33]. Для обеспечения в помещении заданного температурного режима в соответствии с требованиями СНиП 2.04.05-91 [30] имеется централизованное отопление, вентиляция, кондиционер.

7.2.3 Виды вентиляции

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

В соответствии с СНиП 2.04.05-91 [30], вентиляция обеспечивает поддержание санитарно-гигиенических норм температуры, влажности, запыленности воздуха в рабочих помещениях. Для обеспечения необходимых санитарно-гигиенических параметров воздушной среды при эксплуатации устройства в помещении имеется естественная и искусственная вентиляция. Естественная вентиляция осуществляется через оконные проёмы и двери. Основным недостатком естественной вентиляции является то, что приточный воздух вводится в помещение без предварительной очистки и подогрева, а удаляемый воздух не очищается и загрязняет атмосферу.

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

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

клеточный автомат сигнатурный мониторинг

7.2.4 Естественное и искусственное освещение

Работоспособность оператора во многом зависит от освещения. Неудовлетворительное освещение количественно или качественно утомляет не только зрение, но и вызывает утомление организма в целом, оказывает влияние на производительность труда оператора.

Для обеспечения нормального освещения применяется естественное, искусственное и смешанное освещения, которые нормируются СНиП 4-II-79 [27].

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

Нормированные значения КЕО, согласно СНиП 4-II-79 [27], для зданий, расположенных в I, II, IV, V поясах светового климата, определяются по следующей формуле:

(7.1)

где - значение КЕО для III пояса светового климата, составляет 1.5 СНиП 4-II- 79 [27];

m _ коэффициент светового климата (для г. Харькова m=0,9 % - СНиП 4-II-79 [27]);

c _ коэффициент солнечности климата, равен 0,75 т.к. окна расположены на южной стороне здания - СНиП 4-II-79 [27].

Значение КЕО для естественного освещения: е = 1.5*0.9*0.75=1.0125%.

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

Таблица 7.3 - Характеристики производственного освещения

Точность зрительных работ	Миним альный размер объекта различения, мм	Разряд зрительной работы	Характ еристика типа фона	Контраст объекта с фоном	Подразряд зрительной работы	Нормировочное значение при освещении
						Естественном еHN, %	Искуст-ном Еmin,
Средней точности	0,51	IV	Сред-няя	малый		1,0125	300

Все производственные помещения, с постоянным нахождением в них людей, в соответствии с санитарными нормами и правилами, имеют естественное освещение.

7.2.5 Статическое электричество

Защита от статического электричества производится в соответствии с санитарно-гигиеническими нормативами допустимой надежности электрического поля. Допускаемые напряженности электрических полей не должны превышать 20 кВ/м в течение 1 часа, ГОСТ 12.1.045-84 [34].

7.4 Пожарная безопасность

Пожарная безопасность в соответствии с ГОСТ 12.1.004-91 [33] обеспечивается системами предотвращения пожара, пожарной защиты, организационно-техническими мероприятиями. Система предотвращения пожара:

контроль и профилактика изоляции;

наличие плавких вставок и предохранителей в электронном оборудовании;

для защиты от статического напряжения используется заземление;

молниезащита зданий и оборудования согласно РД 34.21.122-87 [35].