СПОСОБ ПОСТРОЕНИЯ ЦИФРОВЫХ КИХ-ФИЛЬТРОВ СЕТЕВОЙ СТРУКТУРЫ Российский патент 2015 года по МПК G06K7/00 G06F17/00 

Изобретение относится к способам структурного построения цифровых фильтров (ЦФ) с конечной импульсной характеристикой (КИХ). Импульсная характеристика (ИХ) таких фильтров имеет свойства симметричности или антисимметричности, а также свойства четности или нечетности. Целевыми устройствами, в которые предлагается включить предлагаемые цифровые фильтры не классической, сетевой структуры, являются устройства на программируемых логических интегральных схемах (ПЛИС).

В последние годы широкое распространение получили способы синтеза нейронных сетей с использованием эволюционных вычислений и имитационных процессов. При разработке таких систем, в качестве базового алгоритма оптимизации параметров систем, применяется широко известный генетический алгоритм с необходимым набором модификаций (RU 2381553, RU 2304307 C1, RU 2295152 C1, US 2003215115 A1, US 6108437 A).

Недостатки указанных решений связаны с использованием элементов умножения и алгоритмов, содержащих операции умножения на произвольное число. Это обусловливает появление сложностей при проектировании цифровых фильтров на ПЛИС. Использование элементов умножения в структуре фильтра, разработанного на ПЛИС, затруднено ввиду относительно малого количества умножителей в современных ПЛИС. Что ограничивает вычислительную производительность систем на ПЛИС. Представлен способ построения цифровых КИХ-фильтров без умножителей, позволяющий использовать преимущества эволюционных и поведенческих (имитационных) методов структурной оптимизации параметров фильтра (автор использовал данные методы структурной оптимизации фильтра). На основе предложенного способа реализуемы алгоритмы быстрой структурной перестройки фильтров сетевой структуры, что позволит применять их в системах: аналитики в биржевой торговле, автоматического производства, машинного обучения, компьютерного зрения, робототехники, медицинского оборудования, сетевых устройств и когнитивного радио.

Цифровой КИХ-фильтр сетевой структуры состоит из связанных базовых ячеек (базовых компонентов фильтра). Базовая ячейка содержит сумматор, элемент линейного сдвига и элемент задержки. Структура связей между базовыми ячейками, показатели задержки, количество операций побитового сдвига в ячейках, описываются с помощью векторов строк. Оптимизация параметров базовых ячеек производится с помощью эволюционного алгоритма, управление которым описывается поведенческой моделью толпы.

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

Наиболее близким аналогом (прототипом) настоящего изобретения выбран способ, описанный в патенте US 4792943 (DE 3610195, DE 3732085). Согласно указанному известному способу возможно разделить структуру фильтра на древа подструктур. Производят быстрое преобразование Фурье (БПФ) сигнала по выходам ячеек древа, чтобы получить частотный спектр. Данный подход применим при мультиплексировании и демультиплексировании сигналов. Банки фильтров образованы по ветвям древа и образуют структуры, которые реализуемы для фильтров сетевой структуры. В рамках способа строится древо банков цифровых фильтров, или более конкретно древо банков цифровых фильтров для мультиплексирования сигналов. Такие банки цифровых фильтров используются в изобретении демультиплексирования и мультиплексирования оцифрованных сигналов с разделением частот. К недостаткам банков цифровых фильтров относят то, что алгоритм БПФ, который приспособлен для преобразования сложных сигналов, не может быть использован эффективно для банков фильтров наилучшим образом. При очень большом (десятки тысяч) количестве элементов массивов отдельные несвязанные расчеты алгоритмов БПФ становятся весьма критичными к временным требованиям, что обуславливает довольно низкую эффективность расчетов.

Настоящее техническое решение представляет собой разработанный способ построения КИХ-фильтров с использованием алгоритма соединения в матрицу базовых компонент (базовых ячеек) без рекурсии. Это обуславливает простоту итеративного сложения векторов строк, дополняемых нулями до нужной длины, импульсных характеристик связанных между собой ячеек. Что позволяет эффективно решать задачу численного расчета частотных и временных характеристик фильтра с эффективным применением алгоритма БПФ.

Задачей настоящего изобретения является создание такого способа построения цифровых КИХ-фильтров, который может быть внедрен на этапах синтеза ЦФ для устройств на микропроцессорах и(или) ПЛИС. Данная технология позволила бы снизить финансовые затраты, связанные с недостаточным быстродействием устройств цифровой фильтрации классической топологии ЦФ на умножителях. Также предложено решение ускорения сходимости алгоритма оптимизации параметров фильтра сетевой структуры к приемлемому результату с помощью применяемых техник структурного дополнения фильтра с усеченной импульсной характеристикой до частотно-избирательной системы с симметричной (антисимметричной) импульсной характеристикой.

Данная задача решается за счет того, что в способе построения цифровых КИХ-фильтров сетевой структуры Кокарева включаются:

задание требования к импульсной характеристике (количество отсчетов L), построение матрицы m×n, состоящей из базовых ячеек, где $$n=\lceil \frac{L-1}{D}\rceil =\lceil \frac{N}{D}\rceil$$ , L=N+1, D=1…N, m≥1, L - длина фильтра, N - порядок фильтра, D - максимально допустимая величина показателя задержки в каждой базовой ячейке. m - количество строк матрицы (может принимать произвольное натуральное число ≥1), причем базовая ячейка имеет множество входов и один выход, причем базовая ячейка представляет собой последовательно соединенные сумматор, элемент линейного сдвига и элемент задержки, параметры которых зависят от требуемых параметров импульсной характеристики; соединение базовых ячеек в сеть любым доступным алгоритмом оптимизации по критерию минимума суммарной квадратичной ошибки между заданными и полученными отсчетами ИХ или АЧХ, причем входы базовых ячеек первого столбца матрицы соединяют со входом проектируемого фильтра, ячейки одного столбца матрицы не соединяют, выход базовой ячейки не может быть соединен с входами базовых ячеек предыдущих столбцов; дублирование полученной структуры; соединение входа дублированной структуры с входом первоначально полученной структуры через дополнительный элемент задержки; последовательное проведение дополнительного элемента задержки по базовым ячейкам дублированной структуры, при этом проводят преобразование элементов задержки каждой базовой ячейки таким образом, чтобы элемент задержки принял минимально возможный показатель; соединение выходов двух структур на суммирующее устройство.

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

Суть изобретения поясняется на фиг.1-6.

На фиг.1 приведены устройства, которые могут использовать цифровые КИХ-фильтры сетевой структуры с симметричной импульсной характеристикой.

На фиг.2 представлена структурная схема базовой ячейки ЦФ.

На фиг.3 представлена структурная схема матрицы из базовых ячеек ЦФ сетевой структуры.

На фиг.4 представлены иллюстрации трех правил преобразования показателей задержки в структурной схеме цифрового КИХ-фильтра, по итеративному методу структурного дополнения ЦФ.

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

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

На фиг.1 указаны 4 основные целевые группы устройств, которые содержат микросхемы ПЛИС или цифровой сигнальный процессор (ЦСП) и используют алгоритмы цифровой фильтрации. Устройства, на которых могут быть реализованы приложения цифровых КИХ-фильтров сетевой структуры:

1) Специальные устройства, которые используют алгоритмы цифровой фильтрации для финансовой аналитики в биржевой торговле;

2) Программируемое оборудование автоматического производства, подвижные и статичные устройства робототехники, использующие машинное обучение и компьютерное зрение;

3) Медицинское оборудование;

4) Сетевые устройства и когнитивное радио.

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

На фиг.2 представлена структурная схема базовой ячейки ЦФ, которая содержит сумматор, элемент линейного сдвига и элемент задержки. Элемент линейного сдвига представляет собой сдвиговый регистр, для тактового сдвига бит влево (умножение, кратное двум) или вправо (деление, кратное двум). Элемент задержки в устройствах реального времени представляет собой буфер чисел. Сдвиг отсчетов сигнала (чисел вектора строки) в буфер, эквивалентно сдвигу чисел в векторе строке вправо на n позиций, где n - показатель задержки отсчетов сигнала.

На фиг.3 представлена структурная схема матрицы из базовых ячеек (Бnm) ЦФ сетевой структуры, при этом все базовые ячейки расположены по строкам и столбцам матрицы. Элементы первого столбца соединены с входом фильтра, каждый элемент (базовая ячейка) матрицы может быть соединен с сумматором перед выходом фильтра. Наличие связей между базовыми ячейками, показатели задержки и количество операций побитового сдвига в базовых ячейках, описываются с помощью логических и алгебраических переменных, которым присваиваются допустимые значения. Эти значения параметров изменяются с помощью выбранного метода оптимизации, для нахождения удовлетворяющей требованию импульсной характеристики ЦФ (или соответствующую ей передаточную функцию).

На фиг.4 представлены иллюстрации трех правил преобразования показателей задержки в структурной схеме цифрового КИХ-фильтра:

а - свойство суммирования показателей;

б - свойство ветвления элементов задержки;

в - свойство, объединяющее суммирование и ветвление элементов задержки.

n, m, k - переменные показателей задержки, i - номер показателей задержки. Оригинальный метод структурного дополнения ЦФ применим для КИХ-фильтров сетевой структуры. Такая структура должна состоять из базовых ячеек и сумматора в матрице из базовых ячеек, согласно тому описанию, что предложил автор. С помощью итеративного метода структурного дополнения КИХ-фильтров сетевой структуры ЦФ с произвольной ИХ всегда можно достроить до ЦФ с симметричной (антисимметричной) ИХ.

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

Предметом изобретения является способ структурного построения цифровых КИХ-фильтров сетевой структуры, образованных многосвязными базовыми ячейками фильтра (фиг.2). Базовые ячейки образуют 2-мерную матрицу (фиг.3) и обладают не рекурсивными связями. Матрица содержит m∗n элементов (базовых ячеек), m - строк, n - столбцов. Элементы первого столбца по умолчанию связаны со входом. Каждая ячейка (Б) второго столбца может иметь m+1 связей (вектор связей длиной m+1), то есть может быть связана с выходом каждой ячейки 1-го столбца и входом inp. Каждая ячейка третьего столбца уже может иметь 2 m+1 связей (вектор связей длиной 2 m+1), то есть может быть связана с выходом каждой ячейки 1-го, 2-го столбца и входом inp. Ячейка n-го столбца может иметь (n-1)∗m+1 связей (вектор связей длиной (n-1)∗m+1). Таким образом, вектор, описывающий наличие связей ячеек n-го столбца с входом inp и ячейками 1-го, 2-го, …, n-1 столбца, содержит последовательность чисел: 0 - отсутствие связи между ячейками, 1 - наличие связи со знаком «+» на входе сумматора данной ячейки, -1 - наличие связи со знаком «-» на входе сумматора данной ячейки.

Каждая базовая ячейка (сокращенно Б) из 1-го столбца имеет 1 вход. Базовая ячейка Б21 будет иметь вектор связей длиной m+1, где первый элемент вектора строки указывает на наличие связи с входом inp и знак по данному входу сумматора Б21. Второй элемент вектора строки Б21 указывает на наличие связи с Б11 и знак по данному входу сумматора Б21. Третий элемент вектора строки Б21 указывает на наличие связи с Б12 и знак по данному входу сумматора Б21. Таким образом, описывается наличие связей Б21 со всеми элементами 1-го столбца и входом inp. Аналогичным образом описывается наличие связей всех ячеек из 2-го по n столбец, с ячейками предыдущих столбцов и входом inp. Между ячейками одного столбца матрицы связей нет. Между ячейками так же нет обратных связей. Ячейки соединены от столбца к столбцу последовательными или перекрестными связями. Выход (outp) ЦФ, образует выход сумматора после столбцов базовых ячеек матрицы фильтра.

В ходе оптимизации параметров ЦФ (имитационно управляемых эволюционных поисков) находится сетевая структура фильтра с усеченной последовательностью ИХ, аппроксимирующей часть ИХ эталонного ЦФ. В формулах 1, 2 и 3 указана связь ИХ оптимизируемого ИХ₀ и эталонного ИХ_э фильтров.

$$И{Х}_{э}\left(k_1,k_2,\dots ,k_{\frac{n}{2}}\right)\Rightarrow \left(алгоритм\text{ оптимизации}\right)\Rightarrow И{Х}_{оч.}$$

$$И{Х}_{оч}\left(k_1^{\text{'}},k_2^{\text{'}},\dots ,k_{\frac{n}{2}}^{\text{'}}\right)=И{Х}_{оч}\left(r_1,r_2,\dots ,r_L\right),еслиИ{Х}_{э}четная;\left(1\right)$$

Где n - длина четной ИХ эталонного фильтра, $$\frac{n}{2}=L$$ .

$$И{Х}_{э}\left(k_1,k_2,\dots ,k_{\frac{n+1}{2}}\right)\Rightarrow \left(алгоритмоптимизации\right)\Rightarrow И{Х}_{онч}$$

$$И{Х}_{онч}\left(k_1^{\text{'}},k_2^{\text{'}},\dots ,k_{\frac{n+1}{2}}^{\text{'}}\right)=И{Х}_{онч}\left(r_1,r_2,\dots ,r_L\right),еслиИ{Х}_{э}нечетная;\left(2\right)$$

Где n - длина нечетной ИХ эталонного фильтра, $$\frac{n+1}{2}=L$$ .

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

$$И{Х}_{онч}\left(k_1^{\text{'}},k_2^{\text{'}},\dots ,k_{\frac{n-1}{2}}^{\text{'}}\right)=И{Х}_{онч}\left(r_1,r_2,\dots ,r_L\right),еслиИ{Х}_{э}нечетная;\left(3\right)$$

- В данном случае, n - длина нечетной ИХ эталонного фильтра, $$\frac{n-1}{2}=L$$

Для того чтобы получить сетевую структуру фильтра с четной или нечетной, симметричной или антисимметричной ИХ, необходимо:

1) Произвести непосредственный синтез фильтра с использованием метода оптимизации (автор изобретения использовал эволюционно-поведенческий метод оптимизации), с требованием к ИХ_оч, задаваемой по формуле 1, 2 и 3.

2) Полученную структуру фильтра с помощью итеративного метода структурного дополнения фильтра с усеченной ИХ дополнить до фильтра с симметричной (антисимметричной ИХ).

Предложен оригинальный итеративный метод структурного дополнения ЦФ сетевой структуры с произвольной ИХ до ЦФ сетевой структуры с симметричной (антисимметричной) ИХ.

Простой и эффективный итеративный метод основан на итеративном преобразовании значений показателей элементов задержки в базовых ячейках дополнительного фильтра. Дополнительный фильтр - ЦФ, структурно дополняющий ЦФ с усеченной ИХ до ЦФ с симметричной/антисимметричной ИХ. Чтобы дополнить сетевую структуру фильтра с четной симметричной или антисимметричной ИХ по итеративному методу, необходимо воспользоваться следующим описанием:

Метод опирается на структурное свойство симметричности $$И{Х}_{доп}^{\text{'}}$$ дополнительного фильтра.

$$И{Х}_{доп}^{\text{'}}=\left(d_{-L}=r_L,d_{-L+1}=r_{L-1},\dots ,d_{-1}=r_1\right)\left(4\right)$$

Если существует передаточная функция H(z) физически реализуемого КИХ-фильтра с импульсной характеристикой ИХ_оч, то всегда существует передаточная функция КИХ-фильтра, обладающего импульсной характеристикой $$И{Х}_{доп}^{\text{'}}$$ , являющейся зеркальной копией ИХ_оч, отображенной в отрицательной временной области. В данном контексте, этот физически нереализуемый фильтр обладает симметричной ИХ, относительно ИХ своего физически реализуемого прототипа. Кроме того, передаточная функция нереализуемого фильтра точно такая, как в положительной временной области, с тем лишь отличием, что показатели задержек положительны, то есть имеют обратный знак. Таким образом, такой фильтр обладает идентичной структурой с фильтром прототипом, с отличием лишь в положительных знаках при показателях задержек. Однако, следует подчеркнуть, что дополнительный физически нереализуемый фильтр обязательно приводится к физически реализуемому с помощью итеративного преобразования показателей элементов задержек в базовых ячейках.

Метод структурного дополнения содержит всего одно правило преобразования значений показателей задержек, которое основано на двух фундаментальных и одном дополнительном свойствах этого преобразования (фиг.4). Чтобы дополнить структуру КИХ-фильтра по итеративному методу, необходимо воспользоваться набором действий для поэтапного получения единой сетевой структуры фильтра с симметричной/антисимметричной ИХ.

Произвести точную копию фильтра сетевой структуры с ИХ_оч.

Сменить знаки при показателях, во всех элементах задержки дополнительного фильтра.

После этой процедуры ИХ данного фильтра должна соответствовать $$И{Х}_{доп}^{\text{'}}$$ .

Вход оптимизированного фильтра с ИХ_оч соединить через элемент задержки с входом дополнительного фильтра с $$И{Х}_{доп}^{\text{'}}$$ . Показатель элемента задержки N_start, через который соединены два фильтра, рассчитывается по формуле 5

$$N_{start}=-\left(2\ast L-1\right),\left(5\right)$$

где L - длина ИХ_оч

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

необходимо через вход дополнительного фильтра, подключенного к элементу задержки с показателем N_start, пройти через все связанные базовые ячейки фильтра, при этом произвести преобразования элементов задержек для каждой базовой ячейки таким образом, чтобы в структуре фильтра не осталось положительных задержек, и для каждой базовой ячейки дополнительного фильтра существовал элемент задержки с минимально возможным показателем. После применения данного правила ИХ преобразованного дополнительного фильтра должна соответствовать ИХ_доп, описанной по формуле 1. Для получения симметричной ИХ выходы обоих фильтров коммутируют на сумматор с двумя входами и одним выходом. Чтобы получить антисимметричную импульсную характеристику, необходимо выходы (после сумматоров) обоих фильтров (дополнительного и дополняемого) коммутировать на сумматор с двумя входами (положительный знак по входу - с выхода дополняемого фильтра, отрицательный знак по входу - с выхода дополнительного фильтра).

Для того чтобы получить сетевую структуру фильтра с нечетной симметричной ИХ, необходимо в точно таком же порядке дополнить ЦФ по итеративному методу, так как это было проделано для получения структур фильтров с четной симметричной ИХ. ИХ_доп должна удовлетворять формуле 3. Однако следует учесть следующие особенности нечетной ИХ: $$И{Х}_{доп}^{\text{'}}$$ физически не реализуемого фильтра должна иметь вид

$$И{Х}_{доп}^{\text{'}}=\left(d_{-L}=r_L,d_{-L+1}=r_{L-1},\dots ,d_{-1}=r_1\right),L=\frac{n-1}{2}\left(6\right)$$

Показатель элемента задержки по входу дополнительного фильтра:

$$N_{start}=-2\ast L\left(7\right)$$

Так же необходимо ввести еще один структурный элемент - последовательно включенные умножитель на константу и элемент задержки. Данная связка элементов схемы включается параллельно с дополнительным и дополняемым фильтром, на 3 вход выходного сумматора, так как указано на фиг.5. Показатель элемента задержки равен $$-\left(\frac{n+1}{2}+1\right)$$ . Константа равна $$\frac{kn+1}{2}$$ отсчету нечетной симметричной ИХ_э (n - длина ИХ_э) эталонного фильтра.

Для того чтобы получить сетевую структуру фильтра с нечетной антисимметричной ИХ, необходимо в точно таком же порядке дополнить ЦФ по итеративному методу, так как это было проделано для получения структур фильтров с четной симметричной ИХ. ИХ_доп должна удовлетворять формуле 2. Однако, в каждом из методов структурного дополнения, следует учесть поправки для нечетной ИХ, которые были введены при построении структуры фильтра с нечетной симметричной ИХ. Дополнительный и дополняемый фильтры включаются параллельно, так как указано на фиг.6.

Изобретение относится к способам структурного построения цифровых фильтров (ЦФ) с конечной импульсной характеристикой (КИХ). Технический результат заключается в создании способа построения цифровых КИХ-фильтров, который может быть внедрен на этапах синтеза ЦФ для устройств на микропроцессорах и/или ПЛИС. Технический результат достигается за счет цифрового КИХ-фильтра сетевой структуры, который состоит из связанных базовых ячеек, обладающих не рекурсивными связями, и сумматора. Базовые ячейки образуют 2-мерную матрицу с набором элементов, расположенных по строкам и столбцам. Базовая ячейка содержит сумматор, элемент линейного сдвига и элемент задержки. Структура связей между базовыми ячейками, показатели задержки, количество операций побитового сдвига в ячейках, описываются с помощью векторов строк. Оптимизация параметров базовых ячеек производится с помощью избранного алгоритма оптимизации. 1 з.п. ф-лы, 6 ил.

1. Способ построения цифровых КИХ-фильтров, включающий задание требования к импульсной характеристике, а именно задание количества отсчетов L,
построение матрицы m x n, состоящей из базовых ячеек, где , L=N+1,
D = 1 ...N, m > 1, L - длина фильтра, N - порядок фильтра, D - максимально допустимая величина показателя задержки в каждой базовой ячейке, m - количество строк матрицы, где m может принимать произвольное натуральное число > 1, причем базовая ячейка имеет множество входов и один выход, причем базовая ячейка представляет собой последовательно соединенные сумматор, элемент линейного сдвига и элемент задержки, параметры которых зависят от требуемых параметров импульсной характеристики; соединение базовых ячеек в сеть эволюционно-поведенческим алгоритмом оптимизации по критерию минимума суммарной квадратичной ошибки между заданными и полученными отсчетами ИХ или АЧХ, причем входы базовых ячеек первого столбца матрицы соединяют со входом проектируемого фильтра; дублирование полученной структуры; соединение входа дублированной структуры с входом первоначально полученной структуры через дополнительный элемент задержки; последовательное проведение дополнительного элемента задержки по базовым ячейкам дублированной структуры, при этом проводят преобразования элементов задержки каждой базовой ячейки путем осуществления операций суммирования показателей, ветвления элементов задержки и объединения суммирования и ветвления элементов задержки таким образом, чтобы элемент задержки принял минимально возможный показатель; соединение выходов двух структур на суммирующее устройство.

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