СПОСОБ ИДЕНТИФИКАЦИИ СИГНАЛОВ
METHOD OF IDENTIFYING SIGNALS

Изобретение относится к технической кибернетике, представляет собой способ, который может быть использован для идентификации сигналов при решении задач определения состояний наблюдаемых объектов при их диагностировании или мониторинге динамических процессов. Функционально способ предназначен для сокращения вычислительных операций при процедуре сравнения анализируемого сигнала с эталонными сигналами каждого класса состояний, а также снижения объемов памяти для хранения эталонных сигналов.
Известен способ анализа сигнала о состоянии объекта (Киселев Н.В., Сечкин В.А. Техническая диагностика методами нелинейного преобразования. - Л., Энергия, 1980, 109 с.), включающий формирование с последующей коррекцией распознающих эталонов на основе обучающих сигналов, сравнение распознающих эталонов с анализируемым сигналом с получением набора оценок о принадлежности реального состояния объекта каждому из множества возможных состояний объекта, сравнение полученных оценок между собой и с заданным порогом распознавания, в результате которого формируется решение о предполагаемом состоянии объекта. Недостатком данного способа является невозможность оценить достоверность процесса обучения и распознавания, что является критическим в условиях шумов, приводящих к слабой различимости сигналов, относящихся к разным состояниям объекта.
Выявленный недостаток устраняет способ анализа сигналов о состоянии объекта (Патент РФ №2090928, кл. G06K 9/00, G06K 9/62, G06K 9/66. Способ анализа сигналов о состоянии объекта), позволяющий распознавать состояние объекта путем введения механизма измерения достоверности сигналов и эталонов через сравнение сигналов с эталонами по нормированной шкале. Данный способ имеет ограничения в его применении по двум существенным аспектам. Первый аспект ограничения выражается в возможности анализировать только оцифрованные сигналы и невозможности анализировать сигналы, представленные не только в оцифрованном виде, но и (или) в виде двухградационного изображения на неквантованной плоскости. Второй аспект ограничения заключается в необходимости априорного знания конечного количества классов состояний объекта, что ограничивает сферу его применения в случаях, когда это количество неизвестно или множество сигнальных последовательностей изначально не полно. Дополнительный недостаток способа выражается в отсутствии механизма предварительного объективного разделения сигналов по классам состояний, учитывающих изменение формы сигналов во времени, в свою очередь, допускает возможность определения ложного класса или необъективного объединения множества сигналов в ложные классы состояний объекта, что снижает достоверность дальнейшего определения состояния объекта.
Данные недостатки устраняет способ анализа сигналов о состоянии объекта (Патент РФ №2355028, кл. G06K 9/00, опубликованный 10.05.2009, Бюл. №13). Он позволяет анализировать сигналы, представленные как в цифровом виде, так и (или) в виде двухградационного изображения на неквантованной плоскости, с неизвестным заранее количеством классов состояний объекта, что, в свою очередь, повышает достоверность распознавания состояния объекта в системах технической кибернетики. Данный способ заключается в том, что последовательно осуществляют цепное кодирование сигналов, представленных как в цифровом виде, так и (или) в виде двухградационного изображения на неквантованной плоскости, определяют минимальное количество классов состояний применением иерархической классификацией цепей с определением порогов объединения в классы, рассчитывая евклидовы расстояния между классами всех цепей и средней цепью ортогонального пространства, объединяют различные классы цепей в один класс при значении порога объединения, не превышающем значения минимального евклидова расстояния между классами цепей и средней цепи ортогонального пространства, при процедуре распознавания сигналы нормируют, формируют и корректируют распознающие эталоны сигналов по количеству классов состояний, осуществляют оптимизацию и сравнение сигналов и эталонов в евклидовом векторном пространстве с последующим распознаванием состояния объекта до тех пор, пока результат распознавания не удовлетворит заданному критерию достоверности или неудачи. Данный способ является наиболее близким по технической сущности и выбран в качестве прототипа.
Недостатками данного способа являются два существенных аспекта. Первый аспект заключается в большой временной длительности процедуры идентификации, так как последовательное сравнение анализируемого сигнала с каждым эталонным сигналом отдельного класса в худшем случае сравним с числом эталонных классов. Второй аспект заключается в требовании значительного объема памяти для хранения эталонных сигналов, представленных для каждого сигнала N дискретными отсчетами или (N-1) кодированными значениями при представлении сигналов в виде цепей.
Задачей изобретения является создание способа идентификации сигналов, при котором достигается два положительных эффекта: снижение временной длительности процедуры идентификации анализируемого сигнала с эталонами и сокращение памяти, необходимой для хранения эталонных образцов сигналов.
Эта задача решается тем, что из способа-прототипа на этапе распознавания анализируемого сигнала исключают три последовательные процедуры:
1. Корректирование распознающих эталоны сигналов по количеству классов состояний;
2. Оптимизация сигналов и эталонов в евклидовом векторном пространстве;
3. Сравнение сигналов и эталонов в евклидовом векторном пространстве.
Вместо данных процедур на этапе обучения, когда формируются эталонные сигналы и осуществляется их запись в память для идентификации текущих анализируемых сигналов, дополнительно к действиям способа-прототипа:
1) осуществляют сегментацию сигналов, преобразованных ранее к виду цепей в соответствии с выбранной формой созвездия Т, на равные m сегменты кратные значению восьми кодов в интервале;
i
2) в вычислительном устройстве (ВУ) каждый сегмент из n элементов цепи кодируют двоичной последовательностью B, состоящей из двух бинарных последовательностей кратных 1-му байту, вида:
где  - 1-я двоичная последовательность кратная 1-му байту,  - 2-я двоичная последовательность кратная 1-му байту.
Первую двоичную последовательность  получают для каждого от 1-го до n-го элемента сегмента цепи кодированием значений созвездий: для возрастающих направлений и нулевого направления - значений созвездий (1, 2, 3, 4) единицами, а для убывающих направлений - значений созвездий (5, 6, 7) нулями. Фактически двоичная последовательность  описывает качественный характер возрастания или убывания сегмента цепи без указания количественных значений. Так для сегмента цепи со значениями созвездий равными 12344567, двоичная последовательность =11111000, что в десятичном исчислении представляет собой число 248; для сегмента цепи со значениями созвездий равными 76544321, двоичная последовательность =00011111, что в десятичном исчислении представляет собой число 31.
i
Вторую двоичную последовательность  получают объединением в десятичное число D количественных значений созвездия от 1-го до n-го элемента выделенного сегмента цепи, и вычислением хеш-функции следующим выражением:
где bin - функция бинарного представления значения числа десятичной системы исчисления;
i
D - десятичное число объединения значений созвездия от 1-го до n-го элемента сегмента цепи;
mod - функция модуля по основанию;
k
k
k
k
n
n
n
n
G - наибольшее десятичное простое число, не превышающее десятичное число кратное 2 (для n=8, G=251, так как 2=256; для n=16, G=65521, так как 2=65536, для n=24, G=16777213, так как 2=16777216, и т.д.).
i
j
i
i
3) по адресу памяти B осуществляют запись числа принадлежности данного адреса к C классу эталонных сигналов. Так для двух эталонных классов достаточно двух бинарных значений 0 и 1; для эталонных классов превышающих число 3, необходимо использовать бинарную запись десятичных чисел, от 0 до (j-1). Адрес памяти B обладает свойством уникальности для каждого m сегмента участка цепи и является тем самым идентификатором принадлежности данного интервала цепи к эталонному классу поименованному в данном адресе памяти.
При распознавании сигнала:
1) идентифицируемый сигнал преобразовывают к виду цепи в соответствии с созвездием, выбранным на этапе обучения формы Т, на равные m сегменты кратные значению восьми кодов в сегменте;
i
i
j
2) каждый m сегмент преобразовывают к двоичной последовательности B и определяют значение C класса принадлежности данного сегмента по записи в памяти идентификатора класса для этого сегмента;
j
3) оценочное решение о принадлежности сигнала к C эталонному классу принимается по мажоритарному правилу с указанием отношения числа совпавших идентификаторов к числу не совпавших идентификаторов, что фактически покажет процентную степень соответствия распознанного сигнала эталонному Q.
i
j
Новая совокупность существенных признаков заявленного способа достигается применением различных по сущности преобразований цифровых последовательностей в виде цепей, для получения уникальных сокращенных характеристик данных последовательностей, использование которых в качестве адресов позволит сократить число последовательных сравнений с эталонами. Сокращение операций сравнения идентифицируемого интервала сигнала с эталонным снизится в крайнем случае с j операций сравнения по количеству эталонных сигналов до двух операций: расчета бинарного адреса B и определения C значения принадлежности к эталонному классу.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественным всем признакам технического решения, отсутствуют, что указывает на соответствие изобретения условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного способа, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявляемый способ соответствует критерию «изобретательский уровень».
Заявленный способ поясняется чертежами, на которых показаны:
на фиг.1 - алгоритм, поясняющий способ идентификации сигналов;
на фиг.2 созвездие кодирования разности соседних нормированных отсчетов цифровой последовательности сигнала;
на фиг.3 - двумерная плоскость адресов для каждого сегмента из 32 классов сигналов;
на фиг.4 - увеличенная двумерная плоскость адресов для сегментов со значениями  превышающими в десятичной форме записи значение 235;
на фиг.5 - увеличенная двумерная плоскость адресов для классов 13 и 15;
на фиг.6 - увеличенная двумерная плоскость адресов для классов 6 и 15.
Для лучшего понимания сущности заявляемого способа на фигуре 1 представлен алгоритм реализации предлагаемого способа идентификации сигналов. Между терминаторами начала и конца (Моделирование систем: Учебник для вызов / Б.Я.Советов, С.А.Яковлев - 4-е изд., стер. - М.: Высшая школа., 2005. - С.93) алгоритм разбит на отдельные процедуры. Процедуры 3-7 соответствуют этапу обучения, процедуры 9-15 соответствуют этапу распознавания при идентификации сигнала. Блоки 2, 8 и 14 являются блоками выполнения условий. Блок 1 является блоком ввода данных, а блок 16 - блоком вывода данных. Ниже приведен перечень номеров, блоков ввода и вывода, процедур и блоков выполнения условий алгоритма:
1 - Блок ввода данных, учитывающий следующие переменные и константы:
j
C - классы эталонных сигналов, определенные по способу-прототипу;
k
n
G - наибольшее десятичное простое число, не превышающее десятичное число кратное 2 для выбранной переменной n;
m - количество сегментов, кратных значению восьми кодов в сегменте цепи;
Т - выбранная форма созвездия для кодирования сигнала в цепь.
i
j
2 - Блок выполнения условия, определяющий этап обучения при положительном исходе, или этап распознавания и переход к блоку 3, а при отрицательном исходе или сформированной на раннем этапе обучения структуры адресов B и идентификаторов принадлежности к C классу эталонных сигналов, записанных по данным адресам памяти, переход к блоку 9.
i
i
3 - Блок процедуры кодирования сигнала в цепь S (КСЦ S), осуществляет представление сигнала любой формы в виде последовательности, состоящую из n кодов, полученных преобразованием сигнала по выбранному правилу в значения ее изменений относительно точки отсчета.
i
4 - Блок выделения сегментов m (ВС m) в цепи S, осуществляет последовательную сегментацию цепи на m равных сегментов, кратных значению восьми кодов в сегменте.
i
5 - Блок кодирования m сегмента в двоичную последовательность  (KC к ).
6 - Блок расчета двоичной последовательности  (Расчет ) по формуле 2.
j
i
i
7 - Блок записи идентификатора принадлежности к классу C по адресу B осуществляет запись числа, соответствующего значению эталонного класса в память по адресу B.
8 - Блок выполнения условия, определяющий окончание этапа обучения при положительном исходе и переход к блоку 2, или продолжение этапа обучения при отрицательном исходе и переход к блоку 3.
i
i
9 - Блок процедуры кодирования сигнала в цепь S (КСЦ S), осуществляет действия аналогичные действиям блока 3.
i
10 - Блок выделения сегментов m (ВС m) в цепи S, осуществляет действия аналогичные действиям блока 4.
i
11 - Блок кодирования m сегмента в двоичную последовательность  (KC к ).
12 - Блок расчета двоичной последовательности  (Расчет ) по формуле 2.
i
j
i
13 - Блок вывода из памяти по адресу B идентификатора принадлежности к C эталонному классу для m сегмента цепи.
14 - Блок выполнения условия, определяющий последний сегмент цепи при положительном исходе и переход к блоку 15, или при отрицательном исходе переход к блоку 11.
15 - Блок вычисления показателя качества идентификации Q равного отношению суммарного числа совпавших идентификаторов к числу сегментов цепи.
j
16 - Блок вывода пары значений C эталонного класса принадлежности и показателя качества идентификации Q.
В способе-прототипе (Патент РФ №2355028. кл. G06K 9/00, опубликованный 10.05.2009, Бюл. №13) достаточно подробно описана процедура преобразования как произвольной кривой, так и цифровой последовательности в цепь. Последовательность, состоящую из n кодов, полученных преобразованием кривой по выбранному правилу в значения ее изменений относительно точки отсчета, называют цепью (Теория распознавания и анализ сцен: Пер. с англ. / Р.О.Дуда, П.Е.Харт.; Под. ред. В.Л.Стефанюка. М.: Мир, 1976. - 511 с.). Так как значения уровня сигналов могут принимать различные значения, то для предотвращения превосходства признаков с большими числовыми значениями осуществляется нормировка сигналов. Все значения сигналов преобразуют в одномерные массивы с математическим ожиданием, равным 0, и значением дисперсии, равной 1. Данное преобразование для каждого i-го значения отсчета одномерного массива k-го сечения карты аттрактора  к значению  осуществляется в соответствии с выражением (Статистический анализ в MS ExeL: - М.: Издательский дом «Вильяме», 2004. С.142):
k
где µ - математическое ожидание одномерного массива отсчетов k-го сечения карты аттракторов;
k
σ - стандартное отклонение одномерного массива отсчетов k-го сечения карты аттракторов.
k
Данное преобразование позволит нормировать любые сигналы к последовательностям единой размерности. Преобразование k-й преобразованной цифровой последовательности в цепь x осуществляется вычислением арксинуса разности между n соседними нормированными отсчетами  и , при  и i∈[1;n], в соответствии с выражением
k
В результате данного преобразования формируется цепь x, элементами которой являются значения углов для n участков с интервалом измерения углов (-90÷90°). В рамках данного интервала используем созвездие в градусной мере для кодирования разности соседних нормированных значений сигналов, представленное на фигуре 2. С учетом нулевого интервала для созвездия кодирования получим семь интервалов разностей нормированных соседних значений сигнала, которые сведены в таблицу 1. Порядковые номера таблицы 1 показывают, что первые четыре порядковых номера соответствуют положительной динамике изменения цепи или участка сигнала, а 5, 6 и 7 порядковые номера определяют отрицательную динамику изменения. Характер положительной динамики цепей (интервалов цепей) обозначим значением 1, а убывающей динамики - значением 0. Это условие позволит описать качественное изменение сигнала во времени.
Таблица 1
Значения интервалов созвездия кодирования для семи интервалов разностей нормированных соседних значений карты аттракторов
№ п/п
Значение интервала в градусах
Разность нормированных соседних значений карты аттракторов
1
[60÷90°)
[0,433÷0,5)
2
[30÷60°)
[0,25÷0,433)
3
(0÷30°)
(0÷0,25)
4
[0°]
[0]
5
(0÷-30°)
(0÷-0,25)
6
[-30÷-60°)
[-0,25÷-0,433)
7
[-60÷-90°)
[-0,433÷-0,5)
i
k
Рассмотрение заявленного способа целесообразно провести на следующем примере. Для j=32 различных по форме сигналов из N=33 нормированных отсчетов осуществили преобразование по созвездию T=7 (см. фигуру 2), и получили 32 значения цепи для каждого из 32 сигналов. В таблицу 2 сведены значения цепей S для первых девятнадцати цепей, принадлежащих тридцати двум эталонным сигналам, а в таблицу 3 сведены остальные тринадцать цепей. Порядковые номера в таблицах 2 и 3 указывают на порядковый номер кода в цепи и соответствуют по значениям порядковому номеру таблицы 1. Сегментация каждой цепи по 8 ее элементов позволит получить по 4 сегмента на каждую цепь. Значения данных сегментов для 32 классов сигналов сведены в таблицу 4. Порядковые номера таблицы 4 соответствуют номерам классов эталонных сигналов. Определение двоичных последовательностей  для каждого от 1-го до n-го элемента сегмента цепи осуществляют кодированием значений созвездий: для возрастающих направлений и нулевого направления - значений созвездий (1, 2, 3, 4) единицами, а для убывающих направлений - значений созвездий (5, 6, 7) нулями. Результат соответствующего кодирования сегментов цепей таблицы 4 сведены в таблицу 5. Двоичные последовательности  таблицы 5 описывают качественный характер возрастания или убывания сегмента цепи без указания количественных значений. Для получения двоичных последовательностей  для каждого сегмента таблицы 4 осуществили вычисление по формуле 2, при G=251. Совместные значения  и  в десятичной форме исчисления для удобства отображения по всем 32 эталонным классам сведены в таблицы 6 и 7 по шестнадцать классов в каждой таблице.
i
i
j
15
15
Визуальное отображение представлено в виде двумерной плоскости адресов для каждого сегмента из 32 классов сигналов фигурой 3. На данной фигуре по оси абсцисс отложены десятичные значения  а по оси ординат десятичные значения  Расположение координат-адресов B на квантованной двумерной плоскости указывает на их признаковую обособленность в пространстве адресов для различных классов. Увеличенные изображения двумерной плоскости адресов для сегментов со значениями  превышающими в десятичной форме записи значение 235 фигуры 4, а также увеличенные двумерные плоскости адресов для классов 13 и 15 фигуры 5 и для классов 6 и 15 фигуры 6 указывают на разделение уникальных адресов для каждого сегмента цепи эталонного сигнала. По адресу B осуществляется запись идентификатора принадлежности сегмента цепи C эталонному классу. Так для 3-го сегмента 15-го класса по десятичному адресу B=[255, 8] (см. фигуру 5) на этапе обучения будет записано десятичное значение 15 или значение 001111 в двоичной записи. Для 1-го сегмента 15-го класса по десятичному адресу В=[252, 169] (см. фигуру 6) на этапе обучения также будет записано десятичное значение 15 или значение 001111 в двоичной записи.
i
Хранение в памяти идентификаторов для обозначений эталонного класса целесообразно осуществлять в бинарном виде. Размерность идентификаторов для финитного множества сигналов будет определяться числом эталонных классов j. В рассматриваемом примере это число составляет значение 32 классов, следовательно, в качестве идентификатора эталонного класса достаточно использовать 6 бит. Значение 000000 в поле адреса B укажет на то, что идентифицируемый сегмент цепи не соответствует ни одному из j эталонных классов.
1
1
2
1
Для хранения в памяти одного эталонного сигнала в виде цепи из М=(N-1) элементов потребуется М единиц памяти. При T=7 потребуется общий объем памяти для хранения всех j=32 эталонных сигналов, равный значению V=(3×32×М) бит.Так как в нашем случае М=32, следовательно, эффективный объем памяти составит значение V=384 байт. По предлагаемому способу каждая j-ая цепь из М=32 (каждый j-й эталонный сигнал) потребует 8 байт адресного поля и 6 бит для записи идентификатора, что обобщая на 32 класса, составит объем эффективной памяти V=280 байт, что на 104 байта меньше чем V.
В способе-прототипе для отнесения анализируемого сигнала к одному из j=32 эталонных сигналов в наихудшем случае потребовалось бы 32 процедуры расчета мер евклидовых расстояний между цепями для определения минимального порога классификации, в наилучшем случае потребуется 1 процедура расчета евклидова расстояния, при равновероятной стратегии средняя расчетная потребность составит 16 процедур. В заявленном способе для каждого идентифицируемого сигнала в виде цепи осуществляют процедуру сегментации, рассчитывают адрес для каждого сегмента и фиксируют по данному адресу идентификатор эталонного класса, а далее вычисляют показатель качества идентификации Q - отношение числа совпавших идентификаторов к числу сегментов цепи. Таким образом, имеем по две вычислительные операции на сегмент и одну дополнительную операцию на вычисление принадлежности к эталонному классу. Характерно, что эта величина не критична к количеству эталонных классов и в отличие от способа-прототипа является величиной постоянной, не зависящей от стратегий. Сокращение вычислительных процедур прямым образом влияет на снижение временной длительности процедуры идентификации анализируемого сигнала. Рассмотренные оба аспекта подтверждают положительный эффект технического решения предлагаемого способа.
Дополнительные расчеты способа не требуют значительных вычислительных затрат, их можно реализовать на существующей в настоящее время элементной базе, например, на любых серийно выпускаемых программируемых логических интегральных схемах (ПЛИС).
Из рассмотренной сущности заявляемого способа следует, что он обеспечивает снижение временной длительности процедуры идентификации анализируемого сигнала с эталонами до двух процедур на каждый сегмент цепи и сокращение памяти, необходимой для хранения эталонных образцов сигналов.