Поисковые технологии проектирования целочисленных цифровых фильтров. Часть 2

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

Все статьи цикла.

Относительные функциональные показатели

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

Вектор текущего функционирования цифрового фильтра Yj (рис. 1), определяющий ту или иную частотную характеристику проектируемого фильтра, имеет своими компонентами индивидуальные абсолютные показатели качества функционирования Формула, которые в общем случае могут быть противоречивыми и неоднородными, то есть иметь различную физическую природу, различную размерность и диапазон изменения. Такие показатели нельзя непосредственно использовать для постановки и решения экстремальной задачи многокритериального (векторного) синтеза. Для этих целей необходимы безразмерные, нормированные и непротиворечивые выходные характеристики, какими в квалиметрии являются относительные показатели качества функционирования ki(X), также именуемые частными критериями качества. Частные критерии связаны с абсолютными показателями некоторой функциональной зависимости ki = ji(yi), причем совокупность частных критериев образует вектор частных критериев K(k1, k2 … km), соответствующий той или иной характеристике фильтра. Правильный выбор функциональной зависимости ji — это ответственный момент при постановке задачи синтеза, во многом определяющий успех ее решения.

Структурно-функциональное описание фильтра

Рис. 1. Структурно-функциональное описание фильтра

Формирование частных критериев ki(X) в задачах многокритериального синтеза целочисленных цифровых фильтров (ЦЦФ) осуществляется исходя из следующих требований:

  • Обеспечение нормирования частных критериев, приведение их к безразмерному виду.
  • Зависимость φi(yi) должна отражать правило предпочтения одного варианта синтезируемого фильтра другому, то есть экстремум ki (обычно минимум) должен доставлять объекту необходимое качество (требуемые значения частных абсолютных показателей yiТ). Таким образом, именно на данном этапе задача синтеза цифрового фильтра переводится в класс экстремальных математических задач.

В настоящее время для формирования частных критериев наиболее широко используется нелинейная зависимость φi(yi) — зависимость в виде ξ-парабол [2, 3, 4]:

Формула

где yiТ — требуемое значение абсолютного частного показателя фильтра; ξ — показатель степени, положительное целое число.

Зависимость (1) характеризует степень близости абсолютного показателя yi к его требуемому значению yiТ. При yiТ = yi частный критерий ki имеет минимальное значение, равное нулю. На рис. 2 приведен вид функциональной зависимости ki = j(yi), построенной при различных значениях параметра ξ. Как видно, показатель степени определяет характер изменения частного критерия синтеза вблизи точки минимума. При ξ =1 крутизна склонов частного критерия постоянна, а условие непрерывной дифференцируемости функции в точке минимума не выполняется. При ξ > 1 крутизна склонов нарастает и в окрестности точки минимума образуется плоская площадка тем большая, чем больше ξ. Этим облегчается решение многокритериальной задачи, однако при возрастании ξ увеличивается и погрешность достижения требуемых значений yi (то есть возрастает погрешность синтеза требуемых характеристик). Наиболее целесообразно в реальных проектных задачах выбирать значения ξ в пределах от 2 до 5.

Зависимость ki(yi) в виде ξ-парабол

Рис. 2. Зависимость ki(yi) в виде ξ-парабол

Рассмотрим некоторые случаи формирования частных критериев, имеющие большое практическое значение:

1) В задачах с однородными критериями, формирующими одну из характеристик фильтра (например, АЧХ или ФЧХ), часто используют ненормированную форму критерия (1), так называемый квадратичный критерий:

Формула

2) В тех случаях, когда в процессе синтеза необходимо достигнуть не требуемого значения абсолютного показателя yiТ, а его наибольшего значения yimax, частные критерии формируются следующим образом:

Формула

3) Если максимальное значение yimax заранее не может быть определено, то используется следующая форма записи частного критерия:

Формула

где ni — нормирующий множитель.

4) Критерий типа не выше yiТ формируется для участков частотных характеристик фильтра, в которых текущая характеристика не должна превосходить требуемую характеристику:

Формула

5) Критерий типа не ниже yiТ формируется для участков характеристик, в которых текущая частотная характеристика должна лежать выше требуемой:

Формула

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

Относительно вектора частных критериев задача параметрического синтеза цифрового фильтра записывается как задача векторной оптимизации [3, 4,5]:

Формула

где K(k1, k2km) — вектор частных функциональных критериев; X(x1, x2xn) — вектор варьируемых параметров (коэффициентов) фильтра; D — допустимая область изменения параметров.

Как известно, формальным решением задачи (5) является так называемое парето-оптимальное, или эффективное, решение X0, которое может быть далеко не единственным. Совокупность таких решений образует множество парето-оптимальных, или эффективных, решений. Понятие «эффективное решение» является фундаментальным в теории решения векторных экстремальных задач [3, 4]. Эффективное решение формально, безусловно, не худшее решение среди других решений в области D, но между собой эффективные решения уже формально несравнимы, поскольку не существует формальных признаков, по которым их можно было бы сравнивать. Поиск эффективных решений векторной задачи (5) осуществляется, как известно, путем ее скаляризации с помощью введения скалярной функции качества (цели) F(X) проектируемого фильтра, сформированной тем или иным способом из частных критериев ki(X). Процедуру формирования скалярной целевой функции часто называют свертыванием векторного критерия K(k1, k2 … km). Относительно целевой функции F(X) исходная векторная задача (5) записывается уже как задача математического программирования [5, 6, 7, 8].

 

Постановка задачи целочисленного нелинейного программирования

Как было показано в работе [1], синтез рекурсивных целочисленных фильтров по совокупности необходимых характеристик с учетом требований их устойчивости и практической реализуемости наиболее целесообразно осуществлять методами нелинейного математического программирования. В общей трактовке постановку задачи нелинейного математического программирования (часто применяют термин «смешанное программирование») можно записать так [6, 8]:

Формула

Прежде всего, к характерным особенностям задачи (6) следует отнести ее высокую размерность, нелинейность, полимодальность и обычно недифференцируемость целевой функции, неоднородность суммарного пространства параметров РХ, а также наличие системы нелинейных функциональных ограничений (9), определяющих конкретные функциональные особенности решаемой задачи. Соотношение (8) определяет прямые ограничения на значения независимых параметров (компонентов вектора Х). Вектор Х0, минимизирующий скалярную целевую функцию F(X) на множестве допустимых решений, является эффективным (парето-оптимальным) решением задачи.

Как видно, суммарное пространство параметров РХ не однородно, а состоит из непересекающихся подмножеств (7) переменных различного типа. Общее число таких подмножеств может быть любым, однако все они могут принадлежать только четырем теоретически возможным типам. Например:

  1. Непрерывное вещественное подмножество переменных РЕ = Еr размерностью r, когда каждая переменная этого подмножества xi  РЕФормула– может принимать любое значение на интервале своего определения (8).
  2. Дискретное вещественное подмножество переменных РD = Qp размерностью p, когда каждая переменная подмножества qxi  РDФормула– может иметь только счетное число вещественных значений на интервале своего определения.
  3. Счетное целочисленное подмножество переменных РI = Ig размерностью g, когда каждая переменная этого подмножества ixi  РIФормулаg– на интервале своего определения принимает значения натурального ряда чисел.
  4. Счетное подмножество булевых переменных РB = Bh размерностью h, в котором каждая переменная bxi  РB, Формула– на интервале своего определения может принимать только два значения: «0» или «1» (false или true).

При этом размерность суммарного пространства параметров n = r+p+g+h. Именно к задаче (6) в общей своей трактовке сводится большинство современных прикладных задач синтеза, принятия решений.

Покажем это на примере задачи целочисленного нелинейного программирования (ЦНП) при машинном синтезе целочисленного рекурсивного фильтра в форме каскадного соединения m звеньев второго порядка. Постановку такой задачи можно записать так:

Формула

где m — число звеньев второго порядка; d — индекс коэффициента передаточной функции звена; IX — вектор целочисленных параметров (коэффициентов) проектируемого фильтра; Wk — длина битового слова целочисленных коэффициентов; Kimin, Kimaх — допустимые границы изменения коэффициента усиления i‑го звена фильтра.

Как видно, экстремальная задача синтеза (10) записана относительно целочисленного пространства I6m параметров (коэффициентов фильтра) размерностью 6m. Ограничения (11) задают границы изменения этих целочисленных коэффициентов, а соотношение (12) определяет принадлежность коэффициентов a0i биномиальному ряду. Функциональные ограничения (13) контролируют в процессе синтеза условие устойчивости рекурсивного фильтра по всем полюсам коэффициента передачи, а соотношения (14) масштабируют коэффициенты усиления звеньев фильтра в заданный интервал.

Поисковое итеративное решение экстремальной задачи ЦНП (10) в заданном пространстве параметров осуществляет программный алгоритмический комплекс, обращаясь к модельному блоку программы для расчета текущих функциональных характеристик фильтра. Вектор IX0, минимизирующий скалярную целевую функцию F(IX) на множестве допустимых целочисленных решений (11) и (12), является эффективным решением задачи параметрического синтеза рекурсивного целочисленного фильтра.

Все попытки с доступной нам глубиной поиска найти зарубежные или российские аналоги не привели к успеху: в трактовке (10)–(14) задачу проектирования цифровых фильтров не решает никто, практического применения данного подхода в проектировании не обнаружено. Поэтому синтез целочисленных цифровых фильтров методами ЦНП на сегодня обладает безусловной новизной.

 

Формирование целевой функции

В теории векторной оптимизации разработан целый ряд методов формирования целевых функций в многокритериальных задачах нелинейного математического программирования. Это, прежде всего, методы главного критерия, обобщенного критерия, минимаксного критерия, метод последовательных уступок [2, 3, 4 , 5, 6, 9], а также комбинированные подходы. Причем в зависимости от особенностей конкретной задачи синтеза (числа функциональных показателей фильтра, их значимости, их однородности) для отыскания эффективных решений может быть использован тот или иной способ формирования целевой функции. Оценим возможность применения указанных подходов к формированию целевых функций F(IX) в задачах многокритериального синтеза ЦЦФ.

Метод главного критерия

Этот метод заключается в том, что исходная многокритериальная задача сводится к задаче оптимизации по одному основному критерию kµ при условии, что значения всех остальных критериев не должны превышать некоторых установленных уровней (пороговых значений Ai):

Формула

Экстремальная задача математического программирования в данном случае записывается так:

Формула

Эффективным считается всякое решение IX0 этой задачи.

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

Формула

где FS — функция штрафа.

Если условие штрафа выполнено, то целевая функция F(IX) = FS независимо от текущей точки. Поэтому метод главного критерия очень критичен к выбору начальной точки поиска. Ее желательно задавать в рабочей зоне, то есть там, где условие штрафа выполняется, либо по возможности ближе к этой зоне. В противном случае поисковый алгоритм может не найти рабочей зоны и поиск завершится безрезультатно.

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

Метод обобщенного критерия

Сущность метода состоит во введении обобщенного критерия, который в данном случае характеризует качество синтезируемого ЦЦФ в целом. В зависимости от того, каким образом частные критерии объединяются в скалярной функции качества, различают:

  • аддитивные обобщенные критерии:

Формула

    где ai — весовые коэффициенты;

  • мультипликативные обобщенные критерии:

Формула

Минимизация целевых функций вида (16) и (17) приводит к эффективному решению экстремальной задачи синтеза. В настоящее время метод обобщенного критерия находит широкое практическое применение. Как и метод главного критерия, он эффективен при большом числе и однородных, и неоднородных частных критериев; преимущество обобщенного критерия состоит в том, что здесь решение задачи ведется с учетом всех критериев, что и определяет его большую эффективность. Аддитивный критерий (16) рекомендуется использовать при малом разбросе значений частных критериев в допустимой области поиска D, а мультипликативный (17) — при достаточно сильном их разбросе. Вторая особенность состоит в том, что метод обобщенного критерия определяет сходимость yi к yiT в среднем, так как минимизируется сумма ki(IX). Текущие значения yi(IX) будут флуктуировать вокруг yiT, причем максимальное отклонение (ошибка): δi = maxyi(IX)–yiT никак не контролируется.

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

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

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

В задачах многофункционального синтеза, то есть синтеза ЦЦФ по совокупности функциональных характеристик, для каждой такой j‑й характеристики из соответствующих критериев ki(IX) формируется частная целевая функция fj(IX), определяющая выполнение требований по данной частотной характеристике ЦЦФ. При использовании метода обобщенного критерия очень часто такая аддитивная функция соответствует стандартному среднеквадратичному отклонению (СКО) текущей характеристики цифрового фильтра от требуемой характеристики (ненормированная (18) или нормированная (19) форма):

Формула

где Yn(IX) — текущее значение характеристики фильтра на n‑й дискретной частоте диапазона определения; YnT — требуемое значение частотной характеристики.

В компьютерном пакете синтеза частные целевые функции fj(IX) формирует графический многооконный функциональный редактор.

Таким образом, идеология обобщенного критерия наиболее естественна и эффективна при машинном синтезе ЦЦФ. Во многом эта идеология соответствует критерию p‑ошибки [10], хорошо известному из теории аппроксимации характеристик электрических цепей. При этом для синтеза по совокупности функциональных характеристик частные целевые функции целесообразно объединять в обобщенный критерий качества с помощью метода комбинированного критерия.

Метод минимаксного критерия

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

Формула

Тогда экстремальная задача синтеза записывается так:

Формула

Минимизация целевой функции (20) приводит к эффективному решению.

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

Можно отметить следующие особенности минимаксной постановки задачи:

  • при решении задачи синтеза ЦЦФ минимаксный критерий целесообразно использовать в случае однородности частных критериев поиска. При неоднородных критериях часто не удается получить приемлемого решения из-за различной чувствительности частных критериев к изменению вектора переменных;
  • целевая функция F(IX) в случае минимаксного критерия не является гладкой и условия ее непрерывной дифференцируемости обычно не выполняются. Поэтому для решения задачи (10) необходимо использовать алгоритмы поиска, для которых указанная особенность не существенна;
  • метод минимаксного критерия гарантирует минимизацию максимального выброса, максимальной ошибки δi= maxyi(IX)–yiT, пусть даже ценой роста меньших ошибок.

Частные целевые функции, определяющие ту или иную частотную характеристику цифрового фильтра в задачах многофункционального синтеза, в случае минимаксной стратегии решения обычно формируются по соотношению (20), используя ненормированную форму частного критерия [11]:

Формула

Метод последовательных уступок

Этот подход применяется в том случае, когда частные критериальные функции можно ранжировать по их важности, например: k1(IX)  k2(IX)  …  km(IX), то есть считается, что наиболее важным является критерий k1(IX), затем k2(IX) и т. д. В таком случае задача векторного синтеза сводится к m последовательным скалярным (однокритериальным) задачам [9], когда на каждом этапе целевой функцией является последовательно каждый из частных критериев ранжированного ряда, начиная с k1(IX). При этом на каждом i‑м этапе решения {Fi(IX) = ki(IX)} вводится уступка или пороговое значение Ai, характеризующее допустимое ухудшение предыдущего, ki–1(IX)-го критерия от его минимального значения. Тем самым на i‑м этапе, для ki(IX)-го критерия формируется своя область поиска Di, определяемая как прямыми ограничениями на значения переменных X D, так и функциональными ограничениями типа неравенства на значение предыдущих критериев:

Формула

при i = 1 — D1 = D.

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

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

Формула

В качестве эффективного решения задачи принимается точка IXm0  D, являющаяся решением на последнем, m‑м этапе.

Метод последовательных уступок целесообразно использовать для поиска эффективных решений в задачах с четкой иерархией частных критериев качества по их значимости. Для большинства практических задач синтеза ряд приоритетов частных критериев всегда может быть записан либо на основании технического задания, либо исходя из физических особенностей конкретной задачи. При этом использование метода последовательных уступок позволяет в ходе последовательного решения задачи синтеза достичь предварительно заданных значений показателей качества объекта (путем соответствующего выбора допустимых пороговых значений Аi). Метод применим в случае как однородных, так и неоднородных критериев или характеристик, однако общее число частных критериев не должно быть велико, поскольку иначе область поиска по последним критериям приоритетного ряда значительно сужается, что не позволяет осуществить эффективный поиск по данным критериям. При большом числе частных критериев целесообразно объединять критерии в группы по иерархическому признаку и применять для решения задачи метод комбинированного критерия.

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

Метод комбинированного критерия

Применяется в практических задачах параметрического синтеза ЦЦФ с большим числом критериев и является по своей сути обобщением вышерассмотренных методов на задачи многофункционального синтеза — синтеза ЦЦФ по совокупности требуемых характеристик. Сущность комбинированного метода состоит в том, что из всей совокупности частных критериев ki(IX) формируется несколько иерархических по важности групп желательно однородных критериев (рис. 3). Каждая группа (вектор) отображает ту или иную частотную характеристику проектируемого фильтра. В функциональном редакторе пакета синтеза каждой выделенной группе соответствует специальное частотное окно. Далее задача многокритериального синтеза решается по отношению к этим ранжированным группам частных критериев — частотным характеристикам ЦЦФ. Для каждой иерархической группы формируется, как уже было сказано, частная (оконная) целевая функция fj(IX) одним из ранее рассмотренных способов. Затем относительно этих частных целевых функций формируется общая целевая функция обычно в аддитивной форме:

Формула

где bj — вес (значимость) характеристики (окна).

Формирование частных целевых функций

Рис. 3. Формирование частных целевых функций

При сильной групповой иерархии характеристик фильтра иногда выгодно применять идеологию метода последовательных уступок. Это позволяет получить как бы «гарантированное» решение в отношении наиболее важных групп (характеристик) и по возможности улучшить значения второстепенных характеристик цифрового фильтра.

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

 

Поисковое проектирование. Поисковый алгоритм

Экстремальная задача математического программирования в принципе может быть решена аналитическими методами, известными в математическом анализе и в вариационном исчислении (метод стационарных точек, множителей Лагранжа, симплекс-метод в линейном программировании и др.). Однако классические аналитические методы практически неприемлемы для решения задач векторного синтеза ЦЦФ в любой форме записи экстремальной задачи (15, 21, 23). В данной ситуации необходимо применять поисковые подходы, основанные на приближенных численных методах решения экстремальных задач [2, 3, 4, 12]. При использовании поисковых методов оптимальное проектирование часто называют поисковым проектированием. Характерным отличием поисковой оптимизации от аналитического решения является то, что определение эффективного решения задачи ЦНП осуществляется не путем последовательного его расчета по некоторым аналитическим правилам и формулам, а путем его выбора (поиска) на некотором конечном целочисленном множестве вариантов синтезируемого цифрового фильтра, определяемом областью проектирования или областью поиска D  In. Критерий выбора (цели) формализован целевой функцией F(IX), чье значение при поиске необходимо минимизировать.

При численном решении экстремальной задачи ЦНП поисковый алгоритм в дискретном целочисленном пространстве строит минимизирующую последовательность, то есть такую последовательность векторов {IXk}, при которой соответствующая последовательность функций {F(IXk)} сходится, убывая к минимуму целевой функции F(IX). Поисковый алгоритм строит минимизирующую последовательность итерационно — так, что каждый элемент последовательности {IXk} вычисляется по предыдущим элементам на основе единого для данного алгоритма правила. В общем виде этот итерационный процесс можно записать как:

Формула

где Pk — вектор, определяющий направление движения от точки IXk к точке IXk+1 в многомерном целочисленном пространстве, а коэффициент hk задает длину шага в направлении Pk.

Условное отображение линии, соединяющей точки минимизирующей последовательности в пространстве поиска D (то есть траектории поиска экстремума), приведено на рис. 4.

Траектория поиска экстремума

Рис. 4. Траектория поиска экстремума

Для нахождения hk и Pk различные алгоритмы используют разные сведения о целевой функции. Алгоритмы нулевого порядка поиска предусматривают для этого только значения самой функции, а алгоритмы n‑го порядка требуют вычисления производных целевой функции вплоть до n‑го порядка включительно. В современных комплексах целочисленной минимизации применяются поисковые алгоритмы исключительно нулевого порядка, так как условия дифференцируемости целевой функции в реальных задачах ЦНП-синтеза обычно не выполняются.

К основным характеристикам численных итерационных алгоритмов минимизации многомерных целевых функций можно отнести:

  • Надежность алгоритма. По этому признаку все алгоритмы подразделяются на локальные, то есть способные минимизировать только унимодальные (одноэкстремальные) функции, и глобальные алгоритмы, способные минимизировать полимодальные (многоэкстремальные) целевые функции.
  • Эффективность алгоритма (время решения задачи минимизации). Во многом определяется скоростью сходимости итерационной последовательности (25). Обычно большей эффективностью обладают алгоритмы более высокого порядка.
  • Точность решения задачи. Разные классы алгоритмов имеют разные возможности уточнения положения минимума целевой функции. Так, сеточные алгоритмы [2] дискретизируют исходную непрерывную область поиска D и могут уточнять положение экстремума только с точностью, не превышающей шаг дискретной сетки, в то время как алгоритмы, строящие минимизирующую последовательность непосредственно в исходной непрерывной области D Еn, имеют возможность уточнять координаты экстремума значительно лучше.
  • Минимум или полное отсутствие априори настраиваемых параметров.

Для численного решения экстремальной задачи ЦНП (10) при проектировании ЦЦФ используется эффективный метод синтеза с поиском глобального экстремума на дискретной сетке кода Грея, подробное описание и применение которого приведено в работе [2]. Данный метод адаптирован к поиску решений в целочисленном пространстве параметров (коэффициентов фильтра), когда эксклюзивный поисковый алгоритмический комплекс минимизации действует в режиме дискретного целочисленного представления многомерной области поиска D  In.

При разработке данного поискового комплекса необходимо было выполнить следующие условия:

  • Разрешение системы нелинейных функциональных ограничений устойчивости (13) и масштабирования усиления каскадов фильтра (14) методом штрафных функций [2].
  • Разработка базового итеративного алгоритма целочисленной минимизации на детерминированной сетке кода Грея.
  • Разработка общей модельной стратегии поискового решения задачи ЦНП на основе базового алгоритма и дополнительных формализованных или эвристических методов.

Базовый поисковый алгоритм данного комплекса относится к классу глобальных алгоритмов направленного сканирования на детерминированной сетке. Для преобразования массива дискретных целочисленных значений каждой i‑й переменной в кодовое пространство используется код Грея, который позволяет осуществить неразрывное кодирование массива, то есть так, что каждая соседняя кодовая комбинация отличается не более чем на один символ. Это позволяет организовать поиск на дискретной сетке при помощи так называемых сфер поиска. Каждая сфера представляет множество точек пространства поиска в виде узлов сетки, расположенных вокруг некоторой центральной точки (рис. 5). Данные сферы используются для поиска глобального экстремума по определенной стратегии.

Упрощенное отображение стратегии поиска:

Рис. 5. Упрощенное отображение стратегии поиска:
а) нулевой режим;
б) первый режим

Процесс поиска начинается со сферы C1 минимального радиуса r = 1 с центром O1; а затем происходит автоматическое увеличение радиуса r сферы поиска (сфера C2 на рис. 5а) с последующим автоматическим сужением радиуса до минимального (r = 1) с переносом центра в лучшую точку на сфере, на которой такая точка найдена (например, точка O3 на сфере C2). Для нулевого режима работы алгоритма минимизации характерны концентрические сферы поиска. Далее может продолжаться нулевой режим работы или осуществляться переход в первый режим. Как видно, для первого режима характерно неконцентрическое расширение сфер поиска при наличии на сферах точек лучше центра. Пусть сформирована сфера C3 радиуса r = 1 с центром О3 (рис. 5б). Если на сфере С3 нашлась точка О4  С3 с лучшим (меньшим) значением целевой функции, чем в О3, то центр поиска переносится из О3 в О4 и вокруг него формируется сфера С4 удвоенного радиуса 2r. При отсутствии на сфере С4 точки лучше, чем О4, осуществляется переход от сферы С4 к сфере С5 наименьшего радиуса с тем же центром О5  О4. Переход к нулевому режиму осуществляется в случае, если на сфере С5 наименьшего радиуса не нашлось лучшей точки. Таким образом, при последовательном автоматическом расширении и сужении сфер поиска происходит направленное сканирование всей области поиска, без полного ее перебора.

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

  • является алгоритмом нулевого порядка;
  • не имеет настраиваемых параметров;
  • обладает работоспособностью в целочисленном пространстве большой размерности (до 1000 переменных);
  • имеет малые потери на поиск, обеспечивая существенное сокращение полного перебора (например, вместо 1019вариантов — всего 103 вариантов при 16 переменных);
  • имеет высокую надежность поиска экстремума, которая составляет не менее 75% и имеет малую чувствительность к характеру целевой функции.

Подробное описание базового алгоритма поиска на сетке кода Грея приведено в работах [2, 13, 14].

Алгоритмический комплекс целочисленной минимизации, в состав которого входит рассмотренный базовый алгоритм, осуществляет прямой поиск глобального минимума многомерной функции цели в соответствии с выбранной моделью, стратегией поиска. Алгоритм из заданной пользователем начальной точки (начальное приближение) осуществляет последовательные шаги к точке глобального минимума F0(IX0), обеспечивающей совпадение текущей характеристики ЦЦФ с требуемыми характеристиками. Графики характеристик на каждом шаге синтеза отображаются на экране.

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

В программном комплексе параметрического синтеза ЦЦФ объявлено шесть моделей. Из них первые пять являются формализованными (пакетными), не допускающими вмешательства в процесс синтеза. Последняя модель интерактивная и обеспечивает такую возможность. Выбор модели целочисленной минимизации осуществляется на панели настроек пакета синтеза (рис. 6). Приведем краткое описание данных моделей:

  • Минимальная модель. Определяет решение задачи синтеза ЦЦФ по условно минимальной стратегии поиска, соответствующей базовой стратегии глобальной минимизации на сетке кода Грея, приведенной выше. Это самая быстрая модель по критерию эффективности поиска, однако в некоторых случаях надежность отделения глобального экстремума может быть недостаточной.
  • Расширенная модель. Определяет решение задачи синтеза по расширенной стратегии поиска. Повышает надежность решения задачи ЦНП-синтеза за счет использования процедуры (метода) повторного поиска из новой сгенерированной точки (после поиска из начальной точки, заданной пользователем). Время синтеза при этом возрастает примерно в 1,5–2 раза (здесь и далее по сравнению с минимальной моделью).
  • Адаптивная модель. Определяет решение задачи синтеза по адаптивной стратегии поиска, когда надежность решения повышается за счет как повторного поиска из трех сгенерированных начальных точек, так и использования дополнительной эвристической процедуры (метода), ускоряющей движение по вычислительному «дребезгу», свойственному целевым функциям, рассчитанным по численным, приближенным алгоритмическим математическим моделям объекта синтеза. Время синтеза возрастает в 3–4 раза.
  • Максимальная модель. Определяет решение задачи синтеза по условно максимальной стратегии поиска. Максимальная модель существенно повышает надежность поиска за счет использования:
    • процедуры повторного поиска из девяти новых сгенерированных начальных точек, квазиравномерно распределенных в области поиска;
    • дополнительного метода ускоряющей движение по вычислительному «дребезгу» целевой функции;
    • дополнительного метода минимизации овражных целевых функций, часто встречающихся при решении практических задач синтеза ЦЦФ.
Панель настроек пакета синтеза

Рис. 6. Панель настроек пакета синтеза

    Однако это наиболее трудоемкая модель. Время синтеза может возрасти в 7–10 раз;

  • Непрерывная модель. Определяет пакетное решение задачи синтеза в непрерывном режиме (non stop), когда осуществляется непрерывный цикл поиска из новой, случайно сгенерированной начальной точки по идеологии минимальной модели. Процесс синтеза может быть остановлен только пользователем. При достаточной экспозиции непрерывная модель позволяет реализовать режим, близкий к полному перебору, что обеспечивает наивысшую надежность поиска оптимального решения ценой, естественно, существенных временных затрат на процесс минимизации.
  • Диалоговая модель. Реализует интерактивный режим синтеза ЦЦФ. В этой модели работает «открытая» минимальная модель, когда формальная стратегия минимизации сочетается с персональной стратегией пользователя. При работе в диалоговой модели на каждом шаге синтеза пользователь имеет возможность приостановить процесс, скорректировать текущие данные (положение точки останова, границы поиска и т. п.), а также исследовать целевую функцию в точке останова путем построения ее координатных разрезов. Успех решения задачи синтеза (а также и время ее решения) определяется опытом пользователя. При наличии определенного навыка работы в диалоге эффективность решения задачи синтеза ЦЦФ может быть повышена в десятки раз. Однако если пользователь не имеет достаточного опыта диалогового проектирования, ему лучше начать с пакетных моделей синтеза.

Исследование целевой функции

При поисковом проектировании по совокупности характеристик ЦЦФ целевые функции экстремальных задач ЦНП могут иметь весьма сложный, полимодальный характер. В алгоритмическом комплексе предусмотрена возможность исследования профиля целевой функции в любой точке поиска (начальной, промежуточной, конечной). Это исследование осуществляется путем построения координатных разрезов целевой функции — зависимости общей функции цели от выбранной переменной F(ixn) при фиксированных значениях остальных параметров задачи. Переменная разреза ixn при этом изменяется в пределах заданных границ области поиска (проектирования). Примером могут служить координатные разрезы целевой функции (рис. 7) задачи многофункционального синтеза 8‑битового рекурсивного ЦЦФ шестнадцатого порядка, осуществляющего коррекцию амплитудных искажений гидроакустического тракта [15]. На рисунках приведена чистая зависимость целевого функционала данной задачи от указанных целочисленных коэффициентов звеньев (номер звена указан в скобках) без наложения функции штрафа.

Разрез ЦФ по параметру:

Рис. 7. Разрез ЦФ по параметру:
а) а1[3];
б) b0[7];
в) а2[2];
г) b2[3]

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

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

 

Структура программного комплекса

Компьютерная программа позволяет осуществлять параметрический синтез как рекурсивных (IIR), так и нерекурсивных (FIR) целочисленных цифровых фильтров различного порядка в широкой области допустимых изменений параметров (целочисленных коэффициентов) фильтра, проводить подробный анализ полученного оптимального решения в частотной области, исследовать чувствительность оптимального решения к изменению параметров (коэффициентов) синтезированного ЦЦФ, выводить на печать графики частотных характеристик синтезированного фильтра и формировать файл протокола решения текущей задачи синтеза. Блок-схема компьютерной программы приведена на рис. 8.

Блок-схема программы синтеза ЦЦФ

Рис. 8. Блок-схема программы синтеза ЦЦФ

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

Функциональный редактор осуществляет ввод в графическом режиме требуемых функциональных характеристик и формирует общий целевой функционал задачи синтеза в аддитивной форме (24). На панели функционального редактора (рис. 9) представлены:

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

Пример ввода требуемой АЧХ полосового ЦЦФ в модуле функционального редактора программы представлен на рис. 9.

Функциональный редактор с открытой панелью задания типа характеристик

Рис. 9. Функциональный редактор с открытой панелью задания типа характеристик

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

Все заказанные характеристики синтезируемого фильтра отображаются на панели синтеза компьютерной программы на каждом итеративном шаге решения задачи. На рис. 10 в качестве примера приведено состояние панели на текущем итеративном шаге поиска при синтезе полосового ЦЦФ по четырем его характеристикам.

Панель синтеза программного комплекса

Рис. 10. Панель синтеза программного комплекса

После нахождения эффективного решения задачи ЦНП осуществляется подробное его исследование в модуле анализа с построением графиков всех характеристик фильтра, их распечаткой и формированием стандартного протокола решения задачи синтеза. Пример исследования АЧХ двухполосного 8‑битового гауссова ЦЦФ в модуле анализа программы представлен на рис. 11.

Исследование АЧХ двухполосного гауссова ЦЦФ

Рис. 11. Исследование АЧХ двухполосного гауссова ЦЦФ

Более чем десятилетний опыт применения методологии ЦНП для решения задач проектирования целочисленных цифровых фильтров показал ее высокую надежность и эффективность. С помощью разработанного программно-алгоритмического комплекса поискового синтеза ЦЦФ было решено множество практических задач, как типовых, так и весьма сложных, примеры которых можно найти в работах [8, 11, 15, 16]. Практическая реализация полученных решений на целочисленных цифровых платформах полностью подтверждает синтезированные характеристики целочисленных цифровых фильтров.

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

Литература
  1. Бугров В. Н., Пройдаков В. И., Артемьев В. В. Поисковые технологии проектирования целочисленных цифровых фильтров. Часть 1 // Компоненты и технологии. 2014. № 6.
  2. Воинов Б. С., Бугров В. Н., Воинов Б. Б. Информационные технологии и системы: поиск оптимальных, оригинальных и рациональных решений. М.: Наука. 2007.
  3. Моисеев Н. Н., Иванилов Ю. П. и др. Методы оптимизации. М.: Наука. 1978.
  4. Батищев Д. И. Методы оптимального проектирования. М.: Радио и связь. 1984.
  5. Батищев Д. И. Поисковые методы оптимального проектирования. М.: Советское радио. 1975.
  6. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука. 1990.
  7. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. М.: Наука. 1959.
  8. Бугров В. Н., Лупов С. Ю., Земнюков Н. Е., Корокозов М. Н. Дискретный синтез цифровых рекурсивных фильтров // Вестник ННГУ. 2009. № 2.
  9. Подиновский В. В., Гаврилов В. И. Оптимизация по последовательно-применяемым критериям. М.: Советское радио. 1979.
  10. Мингазин А. Т. Синтез передаточных функций цифровых фильтров в области дискретных значений коэффициентов (обзор) // Электронная техника. Сер. 10. 1993. № 1, 2.
  11. Артемьев В. В., Бугров В. Н. Синтез цифровых рекурсивных фильтров с линейной фазой // Компоненты и технологии. 2013. № 7.
  12. Стронгин Р. Г. Численные методы в многоэкстремальных задачах (информационностатистические алгоритмы). М.: Наука. 1978.
  13. Новиков Л. В. О поиске двоичного слова заданной длины, удовлетворяющего определенным требованиям // Некоторые вопросы и проблемы ЭМС радиосистем. Изд. ГГУ, Горький, 1975. Вып. 3.
  14. Воинов Б. С. Алгоритм направленного сканирования на детерминированной сетке // Малков В. П., Угодчиков А. Г. Оптимизация упругих систем. Раздел 3.7.3. М.: Наука. 1981.
  15. Шкелев Е. И., Бугров В. Н., Пройдаков В. И., Артемьев В. В. Целочисленные цифровые фильтры — эффективное решение для 8‑битовых цифровых платформ // Компоненты и технологии. 2013. № 10.
  16. Бугров В. Н. Целочисленное проектирование гауссовых цифровых фильтров // Вестник ННГУ. 2012. № 5.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *