3. Сигнатурный анализ.

4. Замкнутые системы диагностики.

Особенности замкнутых систем обусловлены эффектом "размножения" дефекта по контуру, усиливающим обнаруживающие способности.

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

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

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

2. Принципы генерирования случайных и псевдослучайных последовательностей.

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

Известны два основных метода получения цифрового белого шума: физический — генерирование случайных двоичных чисел с помощью специальных устройств — генераторов случайных чисел (ГСЧ); математический— формирование псевдослучайных числовых последова­тельностей (ПСЧП) по специальным программам или с использованием генераторов псевдослучайных чисел (ГПСЧ).

Возможен также и третий путь, совмещающий в себе физический и математический принципы.

Принцип действия ГСЧ состоит в преобразовании случайного сигнала на выходе физического источника шума в импульсную последовательность с вероятностью появления импульса р (1) = 0,5.

В зависимости от способа формирования числовых последовательностей ,существующие ГСЧ можно разде­лить на четыре основных типа:

1) ГСЧ, основанные на использовании случайных состояний бистабильной схемы при периодическом вклю­чении и выключении источника питания;

2) ГСЧ с пересчетом импульсов периодической по­следовательности за случайный интервал времени;

3) ГСЧ с пересчетом импульсов случайной последо­вательности за фиксированный интервал времени;

4) ГСЧ, основанные на дискретизации непрерывного шумового сигнала по двум уровням.

Наиболее часто при разработке быстродействующих и высококачественных ГСЧ применяются последних два способа.

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

Общими и наиболее существенными недостатками, за­трудняющими применение ГБШ, являются следующие факторы:

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

2. низкая стабильность основных вероятностных характеристик, объясняемая нестабильно­стью первичных источников, дрейфом параметров преоб­разующих схем, источников питания и др., что требует периодической статистической проверки качества гене­рируемой последовательности;

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

4. невозможность воспроизведения и предсказания генерируемых последовательностей в силу их случайной природы; неоднородность структуры генераторов вследст­вие наличия как аналоговых, так и цифровых узлов, что затрудняет миниатюризацию ГСЧ.

Указанные недостатки физических ГСЧ явились при­чиной все более широкого распространения математических методов получения шумовых числовых последова­тельностей. Мгновенные значения таких псевдослучайных последовательностей в отличие от случайных последовательностей в принципе, могут быть предсказаны заранее. В то же время все оцен­ки статистических характеристик конкретной реализации ПСЧП совпадают с оценками соответствующей ей слу­чайной выборки. Любую статистическую характеристику псевдослучайной числовой последовательности можно получить, используя реализацию длиной в один период повторения ПСЧП. Для истинно случайной последова­тельности это потребовало бы бесконечно большую дли­ну реализации. Искусственное увеличение периода ПС-сигнала неограниченно приближает его структуру к структуре одной из возможных реализаций истинно слу­чайного процесса. Однако и при ограниченных величинах периода в определенных условиях псевдослучайные чис­ловые последовательности могут заменить случайные. При анализе псевдослучайной реализации равной или меньшей длине периода вообще практически невозможно определить, является ли она отрезком регулярной или случайной последовательности. С другой стороны, если записать конкретную случайную реализацию на каком-либо носителе, и периодически воспроизводить ее, то по­лучим регулярную ПСЧП.

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

1. периодический характер псевдослучайного сигнала обусловливает низкий уровень дисперсии оценок, получаемых при усреднении в течение целого числа периодов; характеристики ПСЧП абсолют­но стабильны и определяются алгоритмом формирования псевдослучайных чисел;

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

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

X_k=AX_k-1+C(mod R), k=1,2,3,…

где A,C,R - постоянные числа; X₀>0, A>0, C>0, R>X₀, R> A, R>C.

Данный метод получил название мультипликативного конгруэнтного (при с=0) или смешанного конгруэнтного (при с>0), а формируемая в соответствии последовательность – линейной конгруэнтной.

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

k = 0, 1, 2, 3, . . . , (1.1)

где k — номер такта; —символы выходной по­следовательности; — постоянные коэффициен­ты; знак означает суммирование по модулю два. Циклические свойства генератора ПС последовательности определяются характеристическим многочленом:

, где α₀=α_m=1 . (1.2)

Оценка эффективности представленных методов мате­матического генерирования предусматривает исследова­ние свойств формируемых ПСЧП.

Построение генераторов с линейными обратными связями.

Одним из главных преимуществ метода генерирования ПС–последовательностей максимальной длины является простота его реализации. Важнейшим классом ПСП являются последовательности, формируемые генераторами на основе регистров сдвига с линейными обратными связями –LFSR (Linear Feedback Shift Register) .

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

- простота аппаратурной реализации;

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

- хорошие статистические свойства формируемых последовательностей;

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

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

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

рис.1.1.

Если последовательность состояний РС представить как последовательность m—мерных векторов А = (a₁,a₂,…a_m), где α_n€{0,1}, n=1,m то преобразование, осуществляемое схемой в некотором к – м такте работы, можно записать в матричной форме:

(1.3)

или в более компактном виде

(1.3а)

где

(1.3б)

Последовательное применение (1.1) позволяет найти состояние РС генератора в произвольный последующий такт работы:

(1.3в)

Аппаратурный генератор ПСП, в котором ОС включены в межразрядные связи элементов памяти регистра сдвига, представлен на рис.1.2.

Рис.1.2

Для построения таких генераторов выражение 1.2, матрица V записывается как (1.3), а коэффициенты α определяются из обратного полинома .

(1.4)

Генераторы М-последовательности.

При соответствующем выборе коэффициентов α_i на основании характеристического полинома (1.2). который должен быть неприводимым и примитивным, последовательность имеет максимальную длину, равную . Такая последовательность называется M-последовательностью. Неприводимым называется такой многочлен φ(x) степени m, который не делится ни на какой другой многочлен от пониженной степени. Характеристический полином φ(x) будет примитивным в том случае, если полином делится на полином φ(x) только при . При этом необходимо, чтобы начальное состояние регистра сдвига не было нулевым, так как в противном случае генерируемая последовательность будет состоять из одних нулей, что соответствует тривиальному нулевому циклу генератора.

Основная задача синтеза генератора ПС—последовательности максимальной длины это нахождение многочлена φ(x), удовлетворяющего условию примитивности и неприводимости. Известно, что для данного m существует Ф(L)/m примитивных различных и неприводимых полиномов, где Ф(L)—функция Эйлера. Поскольку с ростом m число Ф(L) быстро увеличивается, то соответственно возрастает и количество многочленов φ(x) степени m, порождающих М—последовательности. Среди этого множества можно отыскать полиномы, имеющие наименьшее число нулевых членов. Данный случай характерен для минимальной конфигурации ГПСЧ, где в состав цепи ОС входит наименьшее число сумматоров по модулю два.

Необходимо отметить, что для формирования М–последовательности наряду с примитивным неприводимым полиномом φ(x) может использоваться и обратный ему . Получаемая в этом случае последовательность максимальной длины будет инверсна по отношению к последовательности, порождаемой φ(х).

Так как нулевое состояние регистра ГПК является запрещенным, максималь­но возможное число состояний устройства, а значит, и максимально возможная длина формируемой двоичной последовательности, снимаемой с выхода любого из триггеров, равны 2^m-1. В этом случае диаграмма состояний генератора со­стоит из одного тривиального цикла и цикла максимальной длины 2^m – 1.

В качестве примера построим генератор M-последовательностей для порождающего полинома  (x)=x⁴x³1. В соответствии с (1.3а) и (1.3б) для рассматриваемого примера имеем

. (1.5)

Для построения одноканального генератора М-последовательности получим систему логических уравнений:

(1.6)

На рис.1.3 изображена схема гене­ратора М-последовательности для полинома в соответствии с системой логических уравнений (1.6), а в табл.1.1 представлена последовательность смены состояний регистров сдвига при начальном состоянии A(0)=1000. Регистр сдвига реализован на D-триггерах, состояния которых изменяются по приходу на С-входы тактовых импульсов .

Рис.1.3

Таблица 1.1

№ такта	а1	а2	а3	а4	Выход
0	1	0	0	0
1	0	1	0	0	0
2	0	0	1	0	1
3	1	0	0	1	1
4	1	1	0	0	0
5	0	1	1	0	1
6	1	0	1	1	0
7	0	1	0	1	1
8	1	0	1	0	1
9	1	1	0	1	1
10	1	1	1	0	1
11	1	1	1	1	0
12	0	1	1	1	0
13	0	0	1	1	0
14	0	0	0	1	1
15	1	0	0	0	0

Из табл.1 следует, что длина формируемой последовательности равна 15, т.е. через 15 тактов регистр устанавливается в начальное состояние.

Перейдём к рассмотрению свойств последовательностей максимальной длины.

1. Период М–последовательности, формируемый в соответствии с выражением

, k = 0, 1, 2, 3, . . . ,

где а_k€{0,1}–символы последовательности; α_i€{0,1}–коэффициенты, определяемые примитивным неприводимым порождающим полиномом φ(х), для которого m=deg φ(х), равен 2^m -1

2. Для заданного φ(х) существует L различных М—последовательностей, сдвинутых относительно друг друга.

3. Число единичных символов на периоде М—последовательности равно 2^m-1, а нулевых—2^m-1-1. Вероятности появления 1 и 0 определяются выражениями

;

и при увеличении m достигают значений сколь угодно близких к 0,5.

4. В псевдослучайной последовательности максимальной длины серии из одного символа (1 или 0) встречаются 2^m-2 раз, из двух единиц или нулей 2^m-3 и т.д. Серии из m-1 нулей и m единиц встречаются лишь по одному разу. Сравнивая выражения для оценки вероятности появлении серий из l одинаковых символов, можно убедиться в их практической эквивалентности.

5. Для каждого целого s(l≤s<L) существует такое целое r≠s (l≤r<L), что {a_i}{a_i-s}={a_i-r}. Данное свойство обычно называют свойством сдвига и сложения.

6. Автокорреляционная функция М–последовательности определяется выражением

7. Децимацией последовательности {a_i} по индексу q(q=1, 2, 3,…) называется формирование новой последовательности {bi} из q—х элементов {a_i}, т.е. b_k=a_kq. Если {b_i} является нулевой последовательностью, то она порождается полиномом ψ(х), и имеет период L/(L,q), где (L,q)наибольший общий делитель L и q. При (L,q)=1период {b_i} равен L=2^m-1, где m=deg φ(х), и децимация называется собственной или нормальной.

Результатом всякой нормальной децимации является М–последовательность периода L, порождаемая примитивным неприводимым полиномом ψ(х). При этом если децимация выполняется над последовательностью, сдвинутой на j тактов относительно исходной {a_i}, то получаемая последовательность будет также сдвинутой на некоторое число j тактов по сравнению с {bi}. Иначе говоря, независимо от того, какой именно сдвиг последовательности, порождаемой полиномом φ(х), выбран, результатом ее всегда оказывается М–последовательность, порождаемая полиномом ψ(х). В частности, при децимации характеристической М—последовательности {a_i}*, порождаемой многочленом φ(х), получается также характеристическая последовательность {b_i}*, соответствующая полиному ψ(х).

Рассмотрим несколько разновидностей М—последовательностей, формируемых в результате нормальных децимаций. Поскольку децимация по индексу q будет давать тот же результат, что и децимация по q(mod L), ограничимся q≤L. Прежде всего, очевидно, что децимация по единичному индексу будет равна исходной последовательности b_k=a_k*l=a_k. Результатом децимации характеристической последовательности по индексу 2 будет исходная характеристическая последовательность b_k*=a_2k*=a_k*. Следовательно, для произвольной последовательности {a_i} существует такое n, при котором ее децимация {a_i} по индексу 2 равна сдвигу на n тактов a_k2=a_k-n. Отсюда следует, что характеристическая последовательность {a_i}* есть результат сдвига исходной {a_i} на 2*n тактов, a*_k=a*_k-2n. Тогда, поскольку для любого s a*_2k^s=a_k, справедливо равенство a_2k^s=a_k-r, где величина сдвига r зависит от s. В общем случае М—последовательность периода L может быть сформирована из исходной посредством ее децимации по нечетному индексу q.

Среди децимации по четному индексу выделяют случай q=L-1, при котором b_k=a_k(l-1)=a_-k. Иными словами, последовательность {b_i} является инверсной к {a_i} и порождается полиномом ψ(х), обратным к φ(х), ψ(х)=φ (х).

Данное свойство это тест, который позволяет различать М—последовательности и последовательности случайных двоичных цифр. Пусть а₀,а₁,…,а_n-1—сегмент М–последовательности периода L=2^m-1, где n<L. Составим матрицу:

где m<b<n/2. ранг данной матрицы меньше величины b, что следует из наличия линейной зависимости между символами М—последовательности. С другой стороны, если а₀а₁…а_n-1—последовательность равновероятных двоичных случайных цифр, то вероятность того, что rang(M)<b, не превышает 2^2b-n-1 и при соответствующем выборе b и n оказывается весьма незначительной величиной.

Таким образом, вопрос rang(M)<b? является тестом, с помощью которого по ограниченному числу элементов М—последовательности можно показать, ее отклонение от абсолютной случайности. Например, при m=11, L=2^m-1=2047 и b=15 для М—последовательности rang(M)<b, начиная с n=50, тогда, как вероятность получить такой же результат для случайной последовательности не превышает 2^-21.

Многоканальные генераторы М-последовательностей.

Если последовательность состояний регистра сдвига представить как последовательность m—мерных векторов А=(a1,a2,…am), где an€{0,1}, n=1,m то преобразование, осуществляемое схемой в некотором к–ом такте работы, можно записать в матричной форме:

(1.7)

или в более компактном виде

, (1.8)

где

(1.9)

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

, (1.10)

где s – это величина сдвига.

Реализация многоканального генератора М-последовательности.

Рассмотрим построение двухканального генератора М-последовательности, т.е. n=S=2. В качестве порождающего полинома выберем полином  (x)=x⁴x³1. В соответствии с (1.10) для рассматриваемого примера имеем

.

Для построения одноканального генератора М-последовательности получим систему логических уравнений:

(1.11)

На рис. 1.4 изображена схема гене­ратора М-последовательности для полинома в соответствии с системой логических уравнений (1.11).

Рис.1.4

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

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

Генераторы нелинейных последовательностей.

Помимо рассмотренных линейных генераторов при компактной диагностике используются генераторы на регистрах сдвига с нелинейной функцией обратной связи. Эти генераторы порождают нелинейные рекуррентные последовательности, которые по своим диагностическим свойствам отличаются от линейных. В частности, в n-разрядном нелинейном генераторе достаточно просто порождается двоичная последовательность де Брейна. Она представляет собой нелинейную двоичную последовательность {x_i} периода T=2ⁿ , в которой всевозможные векторы (x_j x _j+1… x _j+n-1) длины n при любом j встречается только один раз. Исключение запрещенного нулевого состояния всех триггеров генератора позволяет увеличить период формируемой последовательности и сделать его максимально возможным, равным 2^m, повысить ее качество, так как вероятности появления 0 и 1 становятся равными 0,5. Последовательности длиной 2^m называются последовательностями де Брейна. Алгоритм построения генератора де Брейна:

Записываем уравнения в общем виде работы линейного генератора

где

Если последовательность состояний РС представить как последовательность m—мерных векторов А = (a₁,a₂,…a_m), где α_n€{0,1}, n=1,m то преобразование, осуществляемое схемой в некотором к – м такте работы, можно записать в матричной форме:

Далее изменяем запись для следующим образом;

(1.12)

Следующие состояния – обычный сдвиг.

Пример:

Для построения одноканального генератора М-последовательности получим систему логических уравнений:

(1.13)

На рис. 1.5 изображена схема гене­ратора М-последовательности для полинома в соответствии с системой логических уравнений (1.13),а в табл. 1.2 представлена последовательность смены состояний регистров сдвига при начальном состоянии A(0)=1000. Регистр сдвига реализован на D-триггерах, состояния которых изменяются по приходу на С-входы тактовых импульсов .

Рис. 1.5

Таблица 1.2

№ такта					Выход
0	1	0	0	1
1	1	1	0	0	1
2	1	1	1	0	0
3	0	1	1	1	1
4	1	0	1	1	0
5	0	1	0	1	0
6	0	0	1	1	0
7	0	0	0	1	1
8	1	0	0	1	1

Из табл.1.2 следует, что длина формируемой последовательности равна 8, т.е. через 8 тактов регистр устанавливается в начальное состояние