К. Г. Кирьянов сигнатурный анализ
Скачать 445.86 Kb.
|
2.работа анализатора сИГнаТУр 2.1.математическая модель анализатора Наиболее распространенная схема АС цифровых данных на сдвиговом регистре показана на Рис. 2. Математическая модель анализатора общего вида (Рис. 3,а) очевидна и соответствует системе уравнений (8), а Рис. 3,б - матричной форме (9), (10) этих же самых уравнений (8):   В формулах (8)-(10) компонента векторов ui, xi, y и элементы матриц А, В , С, D принадлежат пота Галуа GF(2) и принимают значения 0 и 1 с действиями сложения и вычитания по правилам 1+1=0+0=0, 1+0=0+1=1, -1+1, т.е. из a + b = с следует, что а = с + (-b) = с + b. Везде далее знак mod2 при сложении опускается, а знак “–” ставится там, где формулы справедливы в случае ui, xi, y R, т. е. в непрерывной по u, х, у ДС, или, когда ui, xi, y FG(2), q>2. Далее везде, где не оговорено противное, можем под матрицами А, В, С, D понимать матрицы произвольного, а не частного вида, как в случае (10).   2.2. ФОРМУлЫ ДЛя ПОдсчета СиГнаТУр Способом, аналогичным использованному при выводе уравнения (6), для их частного случая (9) получим:  В (13) и (14) матричная импульсная реакция Н() выражается в форме  Иногда вместо (13), (14) удобнее использовать форму  где штрих - знак транспонирования,  Все приведенные формулы можно использовать в качестве алгоритмов для подсчета сигнатур на ЦВМ, а при небольших размерностях матриц А, B, C, D и длине tk -tн+1 слова данных и “вручную”. Хотя формально приведенные формулы описывают все варианты поведения АС при однократном вводе в него слова данных, чтобы “почувствовать” работу AC в общем случае, полезно, как увидим далее, рассмотреть примеры с небольшими размерами матриц A, В, C, D в двух случаях: в автономном (при u(t)=const) и вынужденном (при u(t) const) режимах. Подход к изучению автономного режима рассмотрен в разделе 2.3, неавтономного – в разделе 2.4. В случае повторяющихся данных, при каждом цикле их ввода в АС для изучения его работы достаточно приведенных выше формул для однократного ввода. Если данные меняются на каждом из циклов ввода, для оценки распределения сигнатуры следует воспользоваться рекомендациями раздела 1.1 и формулой (7), в которой в качестве функции может быть взята любая из правых частей формул (11)-(14) или (16). 2.1 пространство состояний анализатора сигнатур Автономный режим работы АС не является “рабочим режимом” АС, однако значение его работы, во-первых, помогает правильно использовать схему АС в качестве генератора теста и, во-вторых, а это самое главное, позволяет понять связь свойств АС в автономном и неавтономном режимах работы. Изучение автономного режима работы естественно проводить по структуре пространства состояний (фазового пространства) АС. Состояние x(t)= (x1(t),…, xn(t)) определяется двоичным n-битным кодом, представляющим собой содержимое регистра сдвига (Рис. 3,а) или задержек (Рис. 3,б), а пространство состояний - множеством состояний с указанием переходов (графом переходов) АС из одного состояния в другое согласно формулам раздела 2.2. Пространство состояний АС при u(t) = 0 и всех вариантах вектора с = (с1,……,сn) обратной связи ((8)-(10) и Рис.3) для n=3 и n=4 представлено на Рис. 4. Все состояния (Рис. 4) изображаются точками с метками для компактности в десятичном коде, вычисляемыми по формуле  , а переходы в каждый такт работы - стрелками. Видим, что состояние x=(0, 0, ... , 0) во всех случаях соответствует устойчивому состоянию. Из него система АС не может выйти без воздействия (u(t)0) извне. АС перед началом работы удобно установить именно в это состояние, так как при любой длине последовательности “данных” m= tk -tн+1 (размера “окна” данных) сигнатура “корпуса” проверяемого объекта равна “нулю”  . Как следует из Рис. 4, фазовое пространство (пространство состояний) АС имеет структуру, зависящую от вектора с = (с1,……,сn) обратной связи.   При некоторых с могут существовать несколько точек равновесия (с = (1000) и др.) или несколько раздельных предельных циклов (с = (1011)и др.). а также и точки равновесия, и предельные циклы вместе взятые (с = (001) и др.). Кроме того, у одного и того же количества точек равновесия и предельных циклов (с = (001), с = (0010) и др.) могут быть различные множества состояний (областей притяжения), из которых система приходит к какому-либо предельному множеству (состоянию равновесия или предельному циклу). Для удобства анализа рядом с графами пространства состояний приведены некоторые справочные данные. Во-первых, указаны все - предельные множества  , характеризующие поведение АС при tk – tн . Максимальное значение индекса уi характеризует их число, первый аргумент  в i – число элементов в i-м - предельном множестве (при =1 имеем состояние равновесия, при > I предельный цикл с состояниями). Второй аргумент  характеризует множество состояний, из которых осуществляется переход к предельным состояниям. Всегда . Если > имеются области притяжения из – состояний. Как видно из Рис. 4 и 5, по i (,) можно построить все i для n меньших 3 и 4, а также некоторые i , для n больше 4. Указаны все различные степени матрицы A, необходимые для использования формул (11) – (17). Указана матрица Ф(m) для случая С=Е, B=(1, 0, ..., 0)’, D = 0. Приведенное число столбцов в матрице Ф определяется их периодом и предпериодом (Рис. 4).  Структура пространства состояний, как известно, жестко связана с характеристическим уравнением ДС для А и А-1 , если последняя существует. Характеристические уравнения x()=det|E-A|mod2 и  для примеров поведения систем Рис. 4 приведены на Рис.6. Обратная матрица А-1, соответствующая матрице A втада (10), находится по формуле а характеристические полиномы прямой и обратной матрицы - по формулам  Изучение АС в автономном режиме с матрицей А вида (10) исчерпывает все способы его поведения, так как в случае матрицы А произвольного вида можно, как известно, неособым преобразованием x(t)-= Fz(t) всегда придти к перкой естественной форме матрицы F, т.е.. р одному или нескольким блокам вида (10). Характеристическое уравнение х() системы при этом, как нетрудно проверить, сохраняется и, следовательно, имеет такие яе корни. 2.4. таблицы соответствия Для изучения работа АС в вынужденном режиме (U(t)O), режиме приемника целесообразно результаты расчета сигнатур последовательностей данных фиксированной длины m по формулам раздела 2.2 представлять в форме таблицы соответствия (рис.7).представляющей собой часть таблицы приведенной на стр. 6,так как “событие”, представляемое сигнатурой уi (рис. 7), содержит только слова, коды Kij длины m соответствующей выбранному размеру “окна” данных. Из соотношения (16) ясно, что столбец сигнатур зависит от начальных условий, а коды Kij в строках таблицы - только от матрицы Ф и не зависят от начальных условий.  Из соотношения (16) следует, что таблица соответствия (Рис. 7) определяет гомоморфизм группы входных кодов { Kij}{u’(tн), u’(tн+1), …., u’(tk-1), u’(tk)}ij в группу сигнатур {yi} Л с групповыми операциями 1 и 2, определенными в каждой из указанных групп как сложение по модулю 2 (или q, если xi, yj, u GF(q)) соответствующих компонент векторов Кij и yi и элементами симметрии относительно векторов с нулевыми компонентами, равными самим элементам групп (при (q = 2) или их дополнениям до нулевых векторов (q2). Действительно, из формулы (16) для сигнатур yi и ys в i-й и S-й строке Рис. 7 имеем  Складывая почленно эти отношения, при q = 2 имеем  т.е. “суммарный” элемент группы входных кодов отображается в “суммарный” элемент группы сигнатур с помощью исходного преобразования Ф, задаваемого Рис. 7. Если q>2, формула (20) справедлива только при х(tн) = 0. Tax как среди yi есть один (например, y1) нейтральный элемент  , то при x(tн) = 0 соответствующий ему нейтральный элемент Kij в силу линейности (16) также находится в первой строке среди кодов Кij, j=-l, 2,.... Все коды первой строки (нулевого класса эквивалентности) образуют подгруппу группы всех входных кодов. Этот факт следует из (20) при i = s =1. Все остальные классы эквивалентности , соответствующие сигнатурам yi, i = 1, 2, . . . , qn, представляют собой разложение группы входных кодов по подгруппе кодов нулевого класса эквивалентности. Как следует из теории группы [20], все классы эквивалентности АС должны содержать одинаковое число элементов, т.е. таблица Рис. 7 всегда прямоугольная, если АС построен на базе линейной ДС. Таблица имеет N=qn классов эквивалентности с Рqm-n элементами в каждом классе. Если mn, то соответствие между кодами и сигнатурами однозначно.Рекомендуется до обращения к разделу 4, где перечислены основные свойства АС в неавтономном режиме, внимательно рассмотреть полученные в результате моделирования таблицы соответствия (Рис.8, а, б) для АС с векторами обратной связи с = (0011) и с = (1001), матрицами С=Е, В=(1,0,0,0)`, D =0, x(tн)=0, m=(17), проверив их групповые свойства. Заметим, что в каждой из таблиц Рис. 8 имеется фактически семь таблиц типа Рис.7 с m=1, 2,…., 7, каждая из которых имеет описанные свойства. В отличие от таблицы на стр.6, которая может содержать -е число элементов, в таблице Рис. 8 каждый класс эквивалентности, который представляет соответствующая сигнатура, содержит конечное число элементов в силу ограничения на m7.  Рис. 8. Таблицы соответствий кодов данных и сигнатур с n=4, C=E, D =0, В = (1000)', x(tн) = (0000)' при m=1-7 для с=(0011), (а) и с=(1001), (б). Порядок следования компонент: сигнатуры - у4, у3, у2, у1,; кода данных - u(m), u(m-1), …., u(2), u(1). С помощью матриц Ф с В =(1000)', С = Е ,3)=0 Рис. 4 легко проверить соответствие любого кода данных и сигнатуры, приведенных на Рис.8. Действительно,для кода OIOOII нулевого класса с с=(1001) по формуле (16) имеем:  3. свойства анализатора сИГНаТУр 3.1. свойства анализатора сигнатур в автономном режиме U(t)=0 (режим генератора последовательностей) Рассмотрим основные особенности автономного режима работы АС, связанные с характеристическими уравнениями (19), существованием обратной матрицы А-1 и структурой и - и - предельных множеств, являющихся подмножествами пространства состояний АС. —предельным множеством пространства состояний называется его подмножество, в которое может ДС придти и оставаться в нем при t . —предельным множеством называется подмножеством пространства состояний, в которое АС может однозначно придти и оставаться в нем при t - . Когда АС является конечным автоматом (см. раздел 1.1) в - и - предельные множества он приходит за конечное число шагов. 1. - предельные множества существую всегда, - предельные — только у систем, у которых существует А-1. Существование - предельных множеств означает, что можно восстановить прошлые значения последовательности генерируемой АС по их настоящему значению. Действительно, из (16) имеем  2. Если в характеристическом уравнении x() присутствует корень = 0,то ДС имеет области притяжения у всех -предельных множеств с числом шагов до попадания в эти - предельные множества, равным кратности “s” корня =0. При этом, очевидно, А-1 не существует, а вектор обратной связи (о.с.) имеет вид  и для каждого  .3. - предельные множества существуют, ели у - предельных множеств нет областей притяжения, которые вносят неоднозначность при обратном движении по траекториям (ветвям графа) пространства состоянии, т.е. при s = 0 (см. п. 2). 4. Если в характеристическом уравнении х() Т-й степени матрицы А имеется корень =1, то у ДС существует хотя бы одно - предельное множество  .При Т= 1 получаем состояние равновесия, а при Т> 1 - предельный цикл. Действительно, из условия  в силу (16) получаем уравнение  или  . Это уравнение имеет нетривиальное решение при  . Это условие совпадает с условием  .5. Любая последовательность, генерируемая в АС, удовлетворяет разностному уравнению  имеющему характеристическое уравнение x() вида (20) (следствие уравнения (8)).6. Существует 2n различных последовательностей, которые могут генерировать АС при каждом с= (с1 …… сn). Из свойства 5 следует, что существует 2n начальных состояний АС, а так как траектория пространства состояний однозначно определяется начальным состоянием и уравнением в свойстве 5, то число различных последовательностей будет 2n. 7. Среди последовательностей п. 6 существуют шумоподобные псевдослучайные последовательности максимальной длины (ПСПМД) со структурой пространства состояний 1(1, 1) и 2(2n –1, 2n –1). ПСПМД существуют при таких векторах обратной связи (такой матрице А), при которых в силу свойств 2, 3, 4 xA () не содержит ни нулевых, ни единичных корней. Однако этого условия (см. Рис. 5, 6) недостаточно. Дополнительно требуется, чтобы xA () не делил многочлен  при Т<2n –1 и делил при Т=2n –1, т.е. необходимо представление  только при Т=2n –1.Действительно, по теореме Гамильтона–Кели матрица А является корнем своего характеристического уравнения xA ()0. Поэтому из представления  следует, что  и в силу свойства 4 условие делимости на xA () эквивалентно естественному условию Ат = Е.Например (см. Рис. 4-6), для n= 4 вектору с = (1001) соответствует ПСПМД с периодом Т=2n –1 = 15. Характеристическое уравнение  (см. Рис. 6) делит полином   и не делит полиномы степеней Т<15.8. Если генерируемые АС последовательности снимаются с соответствующих разрядов регистра не непосредственно(СЕ в (16) ), то установившийся период последовательности yr(t) совпадает с таковым для С=Е. Все приведенные свойства легко проверяются на конкретных примерах (см. Рис. 4-6). 3.2. СвоЙСТва ПОслЕДОВАТЕльностей МАКСИМАльной длинЫ 1. Для каждого вектора обратной связи, дающего ПСПМД, существует 2n –1 вариантов, отличающихся циклическим сдвигом. Каждый вариант ПСПМД однозначно определяется начальным состоянием регистра сдвига (свойство тривиально в силу периодичности ПСПМД). 2. Любая ПСПМД удовлетворяет разностному уравнению (следствие свойства 5 п.3.1.).3. Если окно ширины n перемещается вдоль ПСПМД длины 2n –1, то каждый из 2n –1 наборов нулей и единиц будет виден точно один раз (следствие однозначно определяется свойствами 1 и 2). 4. Любая ПСПМД длины 2n –1 содержит 2n-1 единиц и 2n-1 –1 нулей (нулей на один меньше, так как состояние 0 = (0...0) не содержится на цикле 2(2n –1, 2n –1)). 5. Любая ПСПМД длины 2n –1 имеет одну серию символов, состоящую из n единиц подряд: две серии символов из n-1 единиц подряд и т.д. до половины серий, состоящих из одной единицы. Столько же и таких же серий имеется из нулей за исключением серии из n нулей подряд, которая отсутствует (следствие свойств 1-4). 6. Любые две одинаковые по длине ПСПМД в сумме почленно дают также ПСПМД, так как сумма двух решений (8) есть также решение. 7. Отличавшиеся сдвигом ПСПМД длины 2n –1 в соответствующих позициях имеют: 2n-1 –1 несовпадающих символов, 2n-2 совпадающих единиц, 2n-2 –1 совпадающих нулей (в силу свойств 5 и 6). 8. Коэффициент корреляции (i) периодически продолженной ПСПМД представляет собой периодическую функцию периода 2n –1 и равную (im)=1 (1, 2, …) и (s)= –1/m,sim (m=2n –1) [21,22] (в силу свойства 7). 9. Любая ПСПМД, реализованная на регистре сдвига с вектором обратной связи c=(c1, c2, …, cn-1, cn), cn=1, может быть превращена в обратную по отношению к исходной последовательности выбором симметричного вектора обратной связи (сn-1, сn-2, ..., с1, 1). Свойство является следствием существования обратной матрицы A-1 с вектором обратной связи, соответствующим ПСПМД, и вида характеристических уравнений (19). 10. Число любых ПСПМД с фиксированным вектором о.с. - четное число (в силу свойства 9). О полном числе ПСПМД длины 2n –1 cм. в работах [21, 22]. 11. Любые ПСПМД имеют четное число единиц в векторе обратной связи. (В противном случае =1 будет корнем x() над полем GF(2) и x() распадется на множители). 12. ПСПМД, которые требуют минимальное число (двух) ненулевых компонент вектора обратной связи для n 33, приведены в работе [22], векторы обратной связи для каждого n 168 - в работе [23], ненулевые компоненты вектора для n 41 - в приложении 1. 13. При u(t) = 1 вместо u(t) = 0 ПСПМД превращается в ПСПМД с инвертированными символами. Действительно, замена  в уравнении (8) для xi(t) приводит в силу свойства 11 к такому же уравнению, но для  .Другие доказательства ряда перечисленных и некоторых, не приведенных здесь свойств, рассмотрены в работах [21, 22, 24, 28]. 3.3. СВОЙСТВА AнAлизаTOра СиГНаТУр в ВЫНУЖДЕННОМ реЖиМе U(t)0 (режиМ ПриеМника посЛЕДОВаТельностей) В вынужденном режиме свойства АС характеризуются свойствами таблицы соответствия между последовательностями данных и сигнатурами (Рис. 7). Далее рассматриваем АС для конкретности, но без потери общности для случая xi, yi, uGF(2). 1. При каждом m таблица входных кодов имеет 2n строк и 2m-n столбцов. Чем больше “сжатие” (2m)/2n = 2m-n) входных последовательностей, тем больше неоднозначность (2m-n) их кодирования АС (см. Рис. 7). 2. При любых параметрах АС таблица входных данных фиксированной длины представляет собой разложение группы (в алгебраическом' смысле) всех кодов длины m на смежные классы (классы эквивалентности) по собственной подгруппе кодов, помещенной в первую строку таблицы (определение групповой операции дано в разделе 2.4.). 3. i-я строка (i = 2,..., 2n) таблицы входных кодов получается из первой путем сложения ее кодов с каким-нибудь одним из кодов i-й строки, например, стоящим под нулевым кодом первой строки. Доказательство следует из свойства 2 и материалов, рассмотренных в разделе 2.4. Например, из Рис. 8, б для m = 7 для кодов второй строки имеем равенства: 0011111 = =0010011+0001100, 0101010 = 0100110+0001100 и т.д. 4. Каждая строка входных кодов образует класс эквивалентности, соответствующий одной и той же сигнатуре. Первая строка образует “нулевой” класс эквивалентности (следствие свойства 2). 5. “Разность” (сумма, так как q=2) между входными кодами одного и того же класса эквивалентности всегда соответствует коду, который расположен в первой строке таблицы (следствие свойства 3 или соотношения (20)). (Проверяется по Рис. 8.) 6. “Сумма” (разность, так как q=2) любого входного кода i-й. (i =1, 2, ..., 2n) и первой строки образует код, расположенный в той же i-й строке (следствие соотношения (20)). (Проверяется по Рис. 8.) 7. “Сумма” (разность) любого входного кода из i-й строки и с любого входного кода из j-й строки таблицы дают код, расположенный в новой не i-й и не j-й строке таблицы (следствие соотношения (20)). (Проверяется по Рис. 8.) 8. “Сумма” (разность) сигнатуры любого кода из i-й строки и сигнатура любого кода из j-й строки таблицы дают сигнатуру класса эквивалентности, в который попадает сумма любого из входных кодов i-й и j-й строки таблицы соответствия (следствие соотношения (20)). (Проверяется по Рис. 8). Действительно, например, выбирая при m = 7 код 0001100 для i=2 и код 1110001 для j = 16, получим сумму 1111101, которой соответствует сигнатура 1110. Сигнатуры для i =2 и j = 16 (cм. Рис. 8) соответственно равны 0001 и 1111, а их сумма, очевидно, соответствует сигнатуре 1110 суммарного входного кода. Все перечисленные свойства АС являются фактически следствием того, что алгоритм работы АС определяет гомоморфизм группы входных кодов в группу сигнатур. Практическая роль этих следствий становится яснее из следующих свойств АС. |
Похожие:
 | Учебно-методический комплекс по дисциплине учет и анализ: финансовый анализ Виды финансового анализа. Бухгалтерский баланс как объект финансового анализа. Анализ финансовой устойчивости, ликвидности и платежеспособности... |  | Методические подходы к оценке популяционного риска здоровью на основе... Зайцева Н. В., Шур П. З., Кирьянов Д. А., Камалтдинов М. Р., Цинкер М. Ю. Методические подходы к оценке популяционного риска здоровью... |
| Утверждено Стр. 5711. Анализ себестоимости продукцииСтр. 6012. Анализ прямых материальных затратСтр. 6913. Анализ прямых трудовых затратСтр.... | | Анализ работы шмо учителей естественнонаучного цикла за 2011-12 учебный год Методы анализа: анализ документации мо, анализ анкетирования педагогов, Источники анализа |
| Темы рефератов авс анализ Анализ объема заказов Оптимизация объемов... Финансовый контроллинг: задачи, основные элементы и инструменты финансового контроллинга | | В. од. 9 Анализ финансовой отчетности «Анализ финансовой отчетности» обучающийся, в соответствии с фгос впо по направлению подготовки 080100. 62 «Экономика», профиль подготовки... |
| Учебно-методический комплекс по дисциплине комплексный экономический... Анализ результатов социального развития организации. Анализ использования материальных ресурсов и состояния их запасов. Оценка эффективности... | | Сопоставительный анализ русской орфографии и пунктуации 19 и 20 веков Пунктуационно-орфографический анализ издания 1887г романа И. А. Гончарова «Обломов» |
| Реферат Тема: криминалистический анализ уголовного дела Научный д ю. н., профессор Колдин В. Я Источники криминалистической информации и анализ информационных полей | | Анализ учебного плана параллели, завершившей обучение в год Анализ соответствия cодержания подготовки обучающихся и выпускников требованиям фгос |
| Методические указания по выполнению курсовых работ по дисциплине... «Экономический анализ хозяйственной деятельности» разработаны в соответствии с государственным стандартом по специальности 080105.... | | Анализа данных-4: анализ издержки-выгод Методы анализа данных-4: анализ издержки-выгоды, анализ издержки-эффективность (17 ноября 2005)1 |
| Лекции Анализ и проектирование программного обеспечения. Анализ по Моу «Богатищевская средняя общеобразовательная школа», п. Богатищево, Каширского района, Московской области | | Конспект лекционного материала учебной дисциплины «анализ и аудит... Страховая деятельность (страховое дело) это сфера деятельности страховщиков (страховых организаций) в страховании. Финансовый анализ... |
| '''''Структурный анализ прозаического текста как методический прием раскрытия Анализ основных открытий Н. И. Лобачевского и Н. Коперника в сравнении с существующими теориями Евклида и Птолемея | | Анализ работы средней общеобразовательной школы №20 г. Грозный за1 полугод Для специальности Бухгалтерский учет, анализ и аудит (гос 060500 / оксо 080109) |
