Алгоритм проектирования фильтра Паркса-Макклеллана

Алгоритм Паркса–Макклеллана , опубликованный Джеймсом Макклелланом и Томасом Парксом в 1972 году, представляет собой итеративный алгоритм для поиска оптимального фильтра с конечной импульсной характеристикой (КИХ) Чебышева . Алгоритм Паркса–Макклеллана используется для проектирования и реализации эффективных и оптимальных КИХ-фильтров. Он использует косвенный метод для поиска оптимальных коэффициентов фильтра.

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

В 1960-х годах исследователи в области проектирования аналоговых фильтров использовали приближение Чебышева для проектирования фильтров. В то время было хорошо известно, что лучшие фильтры содержат равноволнистую характеристику в амплитуде своей частотной характеристики, а эллиптический фильтр (или фильтр Кауэра) был оптимальным относительно приближения Чебышева. Когда в 1960-х годах началась революция цифровых фильтров, исследователи использовали билинейное преобразование для создания цифровых эллиптических фильтров с бесконечной импульсной характеристикой (БИХ). Они также осознали потенциал проектирования КИХ-фильтров для выполнения той же задачи фильтрации, и вскоре начался поиск оптимального КИХ-фильтра с использованием приближения Чебышева. ^[1]

В математике и инженерии было хорошо известно, что оптимальный отклик будет демонстрировать равноволновое поведение и что количество волн можно подсчитать с помощью приближения Чебышева. Несколько попыток создать программу проектирования оптимального фильтра Чебышева FIR были предприняты в период между 1962 и 1971 годами. ^[1] Несмотря на многочисленные попытки, большинство из них не увенчались успехом, как правило, из-за проблем в алгоритмической реализации или формулировке задачи. Например, Отто Херрманн предложил метод проектирования равноволновых фильтров с ограниченными краями полосы. ^[1] Этот метод получил равноволновую частотную характеристику с максимальным количеством волн путем решения набора нелинейных уравнений. Другой метод, представленный в то время, реализовал оптимальное приближение Чебышева, но алгоритм был ограничен проектированием фильтров относительно низкого порядка. ^[1]

Подобно методу Херрманна, Эд Хофштеттер представил алгоритм, который проектировал КИХ-фильтры с максимально возможным количеством пульсаций. Это стало известно как алгоритм максимальной пульсации. Алгоритм максимальной пульсации накладывал условие чередующейся ошибки с помощью интерполяции, а затем решал набор уравнений, которым должно было удовлетворять чередующееся решение. ^[1] Одним из заметных ограничений алгоритма максимальной пульсации было то, что края полосы не были указаны в качестве входных данных для процедуры проектирования. Вместо этого начальный набор частот { ω _i } и желаемая функция D ( ω _i ) неявно определяли полосу пропускания и задерживания. В отличие от предыдущих попыток разработать оптимальный фильтр, алгоритм максимальной пульсации использовал метод обмена, который пытался найти набор частот { ω _i }, где наилучший фильтр имел свои пульсации. ^[1] Таким образом, алгоритм максимальной пульсации не был оптимальной конструкцией фильтра, но он оказал довольно значительное влияние на то, как будет формулироваться алгоритм Паркса–Макклеллана.

В августе 1970 года Джеймс Макклеллан поступил в аспирантуру Университета Райса, специализируясь на математических моделях проектирования аналоговых фильтров, и записался на новый курс под названием «Цифровые фильтры» из-за своего интереса к проектированию фильтров. ^[1] Курс преподавали совместно Томас Паркс и Сид Беррус . В то время DSP была новой областью, и в результате лекции часто включали недавно опубликованные исследовательские работы. В следующем семестре, весной 1971 года, Томас Паркс предложил курс под названием «Теория сигналов», который Макклеллан также прослушал. ^[1] Во время весенних каникул семестра Паркс поехал из Хьюстона в Принстон, чтобы посетить конференцию, где он услышал презентацию Эда Хофштеттера о новом алгоритме проектирования КИХ-фильтров (алгоритм максимальной пульсации). Он привез статью Хофштеттера, Оппенгейма и Сигеля обратно в Хьюстон, размышляя о возможности использования теории приближения Чебышева для проектирования КИХ-фильтров. ^[1] Он услышал, что метод, реализованный в алгоритме Хофштеттера, был похож на алгоритм обмена Ремеза, и решил пойти по пути использования алгоритма обмена Ремеза. Студенты курса «Теория сигналов» должны были сделать проект, и поскольку приближение Чебышева было основной темой курса, реализация этого нового алгоритма стала курсовым проектом Джеймса Макклеллана. Это в конечном итоге привело к алгоритму Паркса–Макклеллана, который включал теорию оптимального приближения Чебышева и эффективную реализацию. К концу весеннего семестра Макклеллан и Паркс пытались написать вариацию алгоритма обмена Ремеза для КИХ-фильтров. На разработку ушло около шести недель, и к концу мая были успешно разработаны некоторые оптимальные фильтры.

Этот раздел может потребовать очистки для соответствия стандартам качества Википедии . Конкретная проблема: есть ссылка на «приведенное уравнение» без указания уравнения. Пожалуйста, помогите улучшить этот раздел, если можете. ( Декабрь 2024 ) ( Узнайте, как и когда удалить это сообщение )

Алгоритм Паркса–Макклеллана реализуется с помощью следующих шагов: ^[1]

1. Инициализация: Выберите экстремальный набор частот {ω _i ⁽⁰⁾ }.
2. Аппроксимация конечных множеств: вычислить наилучшее чебышевское приближение на текущем экстремальном множестве, дав значение δ ^(m) для минимальной и максимальной ошибки на текущем экстремальном множестве.
3. Интерполяция: вычислить функцию ошибки E(ω) по всему набору частот Ω, используя (2).
4. Найдите локальные максимумы | E ^(m) (ω) | на множестве Ω.
5. Если max _(ω∈Ω) | E ^(m) (ω) | > δ ^(m) , то обновите экстремальный набор до { ω _i ^(m+1) }, выбрав новые частоты, где | E ^(m) (ω) | имеет свои локальные максимумы. Убедитесь, что ошибка чередуется на упорядоченном наборе частот, как описано в (4) и (5). Вернитесь к шагу 2 и повторите.
6. Если max _(ω∈Ω) | E ^(m) (ω) | ≤ δ ^(m) , то алгоритм завершен. Используйте набор {ω _i ⁽⁰⁾ } и формулу интерполяции для вычисления обратного дискретного преобразования Фурье для получения коэффициентов фильтра.

Алгоритм Паркса-Макклеллана можно переформулировать следующим образом: ^[2]

1. Сделайте предварительное предположение о экстремальных частотах L+2.
2. Вычислите δ, используя данное уравнение.
3. Используя интерполяцию Лагранжа, мы вычисляем плотный набор выборок A(ω) в полосе пропускания и полосе задерживания.
4. Определите новые L+2 наибольших экстремумов.
5. Если теорема о чередовании не выполняется, то мы возвращаемся к (2) и повторяем процедуру до тех пор, пока теорема о чередовании не будет выполнена.
6. Если теорема о чередовании выполняется, то мы вычисляем h(n) и все готово.

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

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

На рисунке выше справа показаны различные экстремальные частоты для показанного графика. Экстремальные частоты — это максимальные и минимальные точки в полосах останова и пропускания. Пульсация полосы останова — это нижняя часть ряби в правом нижнем углу графика, а пульсация полосы пропускания — это верхняя часть ряби в левом верхнем углу графика. Пунктирные линии, проходящие через график, указывают δ или максимальную ошибку. Учитывая положения экстремальных частот, существует формула для оптимального δ или оптимальной ошибки. Поскольку мы не знаем оптимального δ или точных положений экстремумов с первой попытки, мы повторяем. Фактически, мы изначально предполагаем положения экстремумов и вычисляем δ. Затем мы повторно оцениваем и перемещаем экстремумы и повторно вычисляем δ или ошибку. Мы повторяем этот процесс до тех пор, пока δ не перестанет меняться. Алгоритм приведет к сходимости ошибки δ, как правило, в течение десяти-двенадцати итераций. ^[3]

Прежде чем применить приближение Чебышева, необходимо было выполнить ряд шагов:

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

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

Для эффективной реализации оптимальной конструкции фильтра с использованием алгоритма Паркса-Макклеллана необходимо преодолеть две трудности:

1. Определение гибкой стратегии обмена и
2. Реализация надежного метода интерполяции. ^[1]

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

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

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

Все условия для алгоритма Паркса–Макклеллана основаны на теореме Чебышева о чередовании. Теорема о чередовании утверждает, что полином степени L, который минимизирует максимальную ошибку, будет иметь по крайней мере L+2 экстремума. Оптимальная частотная характеристика едва достигнет максимальных границ пульсации. ^[3] Экстремумы должны возникать на краях полосы пропускания и полосы задерживания и либо при ω=0, либо при ω=π, либо при обоих. Производная полинома степени L — это полином степени L−1, который может быть равен нулю максимум в L−1 местах. ^[3] Таким образом, максимальное количество локальных экстремумов равно L−1 локальным экстремумам плюс 4 края полосы, что дает в общей сложности L+3 экстремума.

Следующие дополнительные ссылки предоставляют информацию об алгоритме Паркса–Макклеллана, а также о других исследованиях и работах, написанных Джеймсом Макклелланом и Томасом Парксом:

1. Приближение Чебышева для нерекурсивных цифровых фильтров с линейной фазой
2. Краткая справка по проектированию КИХ-фильтров нижних частот по методу Паркса-Макклеллана с использованием MATLAB
3. Введение в DSP
4. Документация MathWorks MATLAB
5. ELEC4600 Lecture Notes (исходная ссылка, архив 15 апреля 2012 г.)
6. Реализация кода C (лицензия LGPL) – Джейк Яновец
7. Iowa Hills Software. "Пример кода C" . Получено 3 мая 2014 г.
8. Пересмотренный и расширенный алгоритм Макклеллана, Паркса и Рабинера, 1975; Код Фортрана.