УСТРОЙСТВО ДЛЯ КЛАССИФИКАЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ ЦИФРОВЫХ СИГНАЛОВ Российский патент 2012 года по МПК G06F17/18 

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

Известно устройство (Авторское свидетельство СССР №830399, МПК G06F 15/36), содержащее аналого-цифровой преобразователь, информационный вход которого является входом устройства, а управляющий вход соединен с первым выходом блока управления, блок памяти и комбинационный сумматор, выход которого подключен к первому информационному входу блока памяти, второй информационный вход которого соединен с выходом аналого-цифрового преобразователя, управляющий вход - со вторым выходом блока управления, а выход блока памяти подключен к входу комбинационного сумматора.

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

Известен также статистический анализатор (Авторское свидетельство СССР №1310842, МПК G06F 15/36), содержащий аналого-цифровой преобразователь, блок сравнения, регистры, блок памяти. Кроме того устройство содержит синхронизатор, сумматор, счетчик, демультиплексор, элементы ИЛИ.

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

Наиболее близким по технической сущности к заявляемому изобретению является устройство для классификации последовательности цифровых сигналов (Патент РФ №2268485, МПК G06F 17/18), содержащее аналого-цифровой преобразователь, n компараторов, дешифратор, n счетчиков, два блока памяти. Первые входы компараторов являются входом устройства, вторые входы компараторов соединены с выходом первого блока памяти. Выходы компараторов соединены с входами дешифратора, выходы которого соединены с входами счетчиков. Выходы счетчиков соединены с входами второго блока памяти, с выхода которого считывается найденная вероятность принадлежности последовательности к эталонному закону распределения.

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

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

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

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

Таким образом, изобретение соответствует критерию «Новизна».

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

Таким образом, изобретение соответствует критерию «Изобретательский уровень», так как оно для специалиста явным образом не следует из уровня техники.

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

Таким образом, изобретение соответствует критерию «Промышленная применимость».

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

Устройство для классификации последовательности цифровых сигналов (фиг.1) содержит аналогово-цифровой преобразователь 1, регистр 2, n компараторов 3, первый дешифратор 4, n счетчиков 5, первый блок 6 памяти, второй дешифратор 7, второй блок 8 памяти, третий дешифратор 9, генератор тактовых импульсов 10. Вход аналогово-цифрового преобразователя 1 является входом устройства, выход соединен с входом регистра 2. Регистр 2 соединен с первыми входами компараторов 3 и входом дешифратора 9. Вторые входы компараторов 3 соединены с выходом блока 8 памяти, с которого считываются эталонные значения для сравнения. Выходы компараторов 3 соединены с входами дешифратора 4, выходы которого соединены с входами счетчиков 5. Выходы счетчиков 5 соединены со входами блока 6 памяти, с выхода которого считывается найденная вероятность и поступает на вход дешифратора 7. Выход дешифратора 7 соединен со входом дешифратора 9 и также является выходом устройства, обеспечивает выдачу максимального рассчитанного значения вероятности и номера соответствующего ей эталона. Генератор тактовых импульсов 10 синхронизирует работу элементов устройства.

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

До поступления на вход устройства классифицируемой последовательности в блок 8 памяти вводятся эталонные значения величин, относящихся к законам распределения, соответствие с которыми определяется (m эталонов). Аналоговая последовательность, после оцифровки в аналого-цифровом преобразователе 1, поступает на вход регистра 2. Регистр 2 обеспечивает сохранение последовательности во внутренней памяти и выдачу ее элементов на первые входы компараторов 3 в соответствии с сигналами генератора тактовых импульсов 9. Объем памяти регистра определяется длиной исследуемой последовательности. С выхода регистра 2 исследуемые величины последовательно поступают на вход дешифратора 9 и на первые входы компараторов 3, на вторые входы которых последовательно поступают эталонные значения величин, относящихся к закону распределения (эталону), соответствие с которым определяется. При превышении исследуемого значения над эталонным компаратор вырабатывает 1, в противном случае - 0. Количество компараторов определяется длиной исследуемой последовательности. Выходы компараторов соединены со входами дешифратора 4, таблица преобразования которого приведена в таблице 1 (на примере 6-ти входных значений в последовательности).

Таблица 1 Таблица преобразования дешифратора 4 (на примере 6 входных значений) Входные последовательности Выходные последовательности 011111 100000 001111 010000 000111 001000 000011 000100 000001 000010 000000 000001

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

Выходы счетчиков соединены со входами блока 6 памяти, таблица преобразования которого приведена в таблице 2 (на примере 6-ти входных значений в последовательности).

Таблица 2 Таблица преобразования блока 6 памяти (на примере 6 входных значений) Входная последовательность Вероятность отнесения к эталонному закону распределения 6000000 0.018 5100000 0.073 4200000 0.118 4110000 0.251 3300000 0.263 3210000 0.531 3111000 0.591 2220000 0.648 2211000 0.888 2111100 0.991 1111110 0.999

Дешифратор 7 обеспечивает выбор максимального значения из рассчитанных вероятностей, обладает встроенной памятью, в которой сохраняются максимальное из рассчитанных значений вероятности и номер соответствующего ей эталона. Вероятность, рассчитанная блоком 6 памяти по первому эталону, сохраняется в памяти дешифратора, также в памяти сохраняется номер эталона. Каждое последующее рассчитанное блоком 6 памяти значение вероятности сравнивается со значением, сохраненным в памяти дешифратора 7, если рассчитанное значение больше, то осуществляется перезапись значения вероятности и номера соответствующего ей эталона в памяти дешифратора 7. Выход дешифратора 7 является выходом устройства и обеспечивает по сигналу генератора тактовых импульсов 9 выдачу значения вероятности и номера соответствующего ей эталона.

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

Дешифратор 9 обеспечивает уточнение эталонов в блоке 8 памяти, обладает встроенной памятью. Во встроенной памяти дешифратора 9 сохраняется входная последовательность, поступающая на вход из регистра 2, а также данные, необходимые для рекурсивного уточнения эталонов. По сигналу генератора тактовых импульсов 10 на вход из дешифратора 7 поступает номер эталона, соответствующего классифицируемой последовательности, а также значение вероятности и обеспечивается считывание данного эталона из блока 8 памяти. При реализации операции уточнения эталона устройство работает как адаптивный линейный сумматор (Адаптивные фильтры: Пер. с англ. / Под ред. К.Ф.Н.Коуэна и П.М.Гранта. - М: Мир, 1988. - 392 с.). Дешифратор 9 выступает в качестве блока адаптации, блок 8 памяти с заданным эталоном является адаптивным фильтром размерности n (определяемой количеством элементов в эталоне). Уточнение эталона производится с использованием метода наименьших квадратов (Уидроу Б., Стирнз С. Адаптивная обработка сигналов: Пер. с англ. - М.: Радио и связь, 1989. - 440 с.: ил.). Данный метод не требует операций возведения в квадрат, усреднения и вычисления производных, поэтому является достаточно удобным и эффективным при реализации в устройстве. При расчете на k-ом шаге работы алгоритма в соответствии с положениями метода наименьших квадратов используются следующие исходные данные:

X_k - вектор отсчетов входного сигнала (входная классифицируемая последовательность);

W_k - вектор весовых коэффициентов (эталонная последовательность);

y_k=Р_расп - выходной сигнал (значение вероятности, рассчитанное по корректируемому эталону);

d_k=1 - образцовый сигнал.

Сигнал ошибки с временным индексом к вычисляется следующим образом:

Формула алгоритма метода наименьших квадратов, которая используется для рекурсивного обновления эталонов, имеет вид:

где µ - параметр сходимости алгоритма, который определяет скорость и устойчивость процесса адаптации.

Уточненный эталон записывается в блок 8 памяти.

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

Генератор тактовых импульсов 10 обеспечивает синхронизацию элементов устройства на трех частотах: f₁ - частота, соответствующая одному полному циклу работы устройства (сравнение входной последовательности из n элементов по m эталонам); f₂ - частота, обеспечивающая цикл сравнения входной последовательности по m-ому эталону (f₁=f₂/m); f₃ - частота, обеспечивающая обработку каждого n-ого элемента входной последовательности (f₁=f₃/(m*n)). Импульс f₁ обеспечивает выдачу дешифратором 7 рассчитанного значения вероятности, номера соответствующего ей эталона, уточнение данного эталона дешифратором 9, запись уточненного эталона в блок 8 памяти. Импульс f₂ обеспечивает подключение записанной в памяти регистра 2 входной последовательности для сравнения с новым эталоном; подключение следующего эталона для сравнения в блоке 8 памяти; приведение счетчиков 5 в исходное состояние для обеспечения сравнения с новым эталоном. Импульс f₃ обеспечивает проведение последовательных операций для каждого элемента входной последовательности, поступающей из регистра 2.

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

Однако практическое применение этих статистик связано со следующими трудностями:

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

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

- необходимость удовлетворения требованиям разбиения вариационного ряда на число интервалов (не менее 8-10) и количество элементов в интервалах (не менее 50-60), что не всегда возможно при малых объемах выборки.

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

Теоретической основой правомерности таблицы преобразования, которая приведена в таблице 2, является концептуальная модель канонического представления пар распределений и статистики мер рассогласования плотностей распределений с использованием данной модели, изложенная в (Борисоглебская, Л.Н. Критерий принятия решений, основанный на кодах, в задачах обнаружения и распознавания, ж. Телекоммуникации, №7, 2001 г.).

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

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

Выражения для вычисления статистик мер рассогласования по Кульбаку (ΔI, ΔI*), хи-квадрат (Δχ²), Питмену (Δp) с использованием концептуальной модели имеют вид

где n₁ и n₂ - объемы первой и второй выборок; Jν₁=1 при ν₁≠0 и Jν₁=0 при ν₁=0; ν₁ - число элементов второй выборки, находящихся между (i-1)-й и i-й порядковыми статистиками вариационного ряда первой выборки.

Если определить последовательность значений ν₁, ν₂, …, ν₆ как код конкретной концептуальной модели, то для приведенного примера (фиг.3) код определяется в виде 101231.

Способ формирования кода показан на фиг.4, где представлен общий вариационный ряд для рассматриваемого примера. На оси X символом ″х″ обозначены значения элементов первой выборки и символом ″•″ - значения второй выборки.

В связи с аддитивностью функций статистик их значения будут одинаковыми для всевозможных перестановок. Например, концептуальные модели с кодами 110231; 231110; 312110 и т.д. будут иметь одинаковые значения статистик. Число всевозможных концептуальных моделей с одинаковым значением статистик определяется числом перестановок в коде и представляется формулой

Понятие числового значения кода определяется как число с (n₁+1) разрядом и основанием позиций n₂, т.е. как код, упорядоченный по убыванию значащих разрядов, начиная со старшего разряда.

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

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

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

Для технической реализации устройства для классификации последовательности цифровых сигналов использован аналогово-цифровой преобразователь иностранного производства типа AD9054ABST-200, регистр, дешифраторы, компараторы, счетчики, второй блок памяти и генератор тактовых импульсов реализованы на перепрограммируемых логических интегральных схемах XC2S200E с памятью хранения структуры схемы XCF02S - фирмы XILINX, первый блок памяти реализован на постоянном запоминающем устройстве Т27С1024.

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

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

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