3.1.2. Теория аппроксимации

Частотная характеристика цифрового фильтра определяется передаточной функцией, которая определена в предыдущем разделе как

и которая является -преобразованием вычисленным при условии В случае нерекурсивного фильтра частотная характеристика может быть записана в виде

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

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

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

и вместо (3.4) можно записать

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

Фиг. 3.1. (см. скан) Ограничения по симметрии; X — независимые коэффициенты импульсной характеристики; О — коэффициенты импульсной характеристики, обусловленные ограничениями по симметрии.

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

то

и частотную характеристику можно записать в виде (фиг. 3.1,6)

Наконец, если принять, что

то

и частотную характеристику можно записать в виде (фиг. 3.1, б)

Можно ли с помощью выражений (3.4) — (3.7) реализовать абсолютно точно «идеальные» фильтры? Если речь идет об идеальных фильтрах общего вида, то ответ на этот вопрос будет отрицательным. Например, для идеального «кругового» фильтра нижних частот частотная характеристика имеет вид

в пределах одного периода, например при и Соответствующая импульсная характеристика имеет

где функция Бесселя первого рода первого порядка. Аналогично частотная характеристика идеального кругового полосового фильтра имеет вид

а его импульсная характеристика имеет вид

Идеальный круговой фильтр верхних частот имеет частотную характеристику

и импульсную характеристику

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

Соответствующая импульсная характеристика имеет вид

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

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

Наилучшей аппроксимацией называют такую которая минимизирует чебышевскую норму функции ошибки.

Некоторые фундаментальные выводы теории линейной чебышевской аппроксимации применимы к задаче проектирования

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

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

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

для любой действительной константы X и для как элементов с. Более того, выражения (3.5) — (3.7) определяют конечномерное линейное подмножество этого нормированного линейного пространства. Таким образом, если «идеальный» фильтр принадлежит нормированному линейному пространству, существует по меньшей мере одна аппроксимация, которая является наиболее близкой (в смысле чебышевской нормы) к этому «идеальному» фильтру.

Выражения (3.5) — (3.7) можно записать в форме обобщенных полиномов вида

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

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

достаточно, чтобы начало координат -мерного пространства было расположено на выпуклой оболочке множества точек

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

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

Теорема единственности (теорема Хаара). Наилучшая аппроксимация непрерывной функции обобщенным полиномом является единственной при любом выборе если и только если удовлетворяет условию Хаара.

Множество непрерывных функций удовлетворяет условию Хаара, если каждый детерминант

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

Сразу же возникает следущий вопрос. Удовлетворяют ли косинусные функции (3.5) — (3.7) условию Хаара в пределах области Нет, не удовлетворяют по следующим причинам [14]. Предположим, что были выбраны такие точек, что детерминант не равен нулю, Будем перемещать

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

Когда множество функций удовлетворяет условию Хаара, это не только означает, что наилучшая аппроксимация является единственной: появляется возможность доказать одну исключительно мощную теорему идентификации, известную под названием теоремы чередования [6]. Эта теорема применима только к задачам одномерной аппроксимации.

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

Для задачи проектирования одномерного фильтра фундаментальное значение имеют два множества функций: Первое удовлетворяет условию Хаара на любом интервале, второе — на интервале (см. [16]). Благодаря этому проектировать одномерные фильтры значительно проще, чем двумерные.

Задачу проектирования двумерного фильтра можно сформулировать несколько иначе [17], если начать с системы (возможно, бесконечной степени) несовместных уравнений вида

где - идеальная (нереализуемая) частотная характеристика. Задача состоит в том, чтобы найти множество

которое минимизирует чебышевскую норму функции А, определяемой как

Конечномерная подсистема

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

где выражает изменение Теперь левая часть каждого уравнения равна абсолютному значению Если система неравенств

является несовместной, т. е. если невозможно удовлетворить всем этим неравенствам при произвольном выборе множества то ни при каких условиях невозможно одновременно уменьшить абсолютные значения всех Можно показать (с помощью теоремы о линейных неравенствах [6]), что эта система неравенств является несовместной, если и только если начало координат -мерного пространства расположено на выпуклой оболочке множества

Эти предварительные замечания позволяют доказать следующую теорему, являющуюся вариантом обобщенной теоремы Балле — Пуссена.

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

является ограничивающей, то

где наилучшая чебышевская аппроксимация на множестве

Доказательство. Правое неравенство является тривиальным, поскольку есть возможное наилучшее приближение к на Чтобы доказать левое неравенство, допустим, что

Это означает, что все значения были одновременно уменьшены в процессе перехода от к Однако это противоречит тому условию, что система

является ограничивающей. Следовательно, левое неравенство доказано.

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

Далее определяется новое множество точек такое, что

и такое, что система уравнений

является ограничивающей. Согласно теореме, имеем

или

где наилучшая аппроксимация на и

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

Точный метод определения множества по станет более понятным после рассмотрения линейного программирования.

Алгоритмы, подобные рассмотренному, можно подразделить на три широкие категории [18]: минимизирующие методы, максимизирующие методы и минимаксные методы. Любой минимизирующий метод гарантирует понижение верхней границы ошибки от итерации к итерации. Соответственно максимизирующий метод гарантирует повышение нижней границы ошибки. Наконец, минимаксный метод обеспечивает одновременно повышение нижней и понижение верхней границ ошибки. Неравенство (3.8) ясно показывает, что рассмотренный выше алгоритм является максимизирующим методом, поскольку есть нижняя граница ошибки причем гарантируется повышение при переходе от итерации к итерации однако не гарантируется, что верхняя граница ошибки понижается.