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

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

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

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

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

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

Целью изобретения является упрощение устройства и повышение его быстродействия.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники информации

1. Авт. св. СССР № 830399, кл. G 06 F 15/36, 1979.

2. Авт. св. СССР № 1310842, кл. G 06 F 15/36, 1986.

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

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

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