Алгоритм построения фильтра Паркса – Макклеллана - Parks–McClellan filter design algorithm

Полосы пропускания и остановки фильтра, разработанного алгоритмом Паркса – Макклеллана.
Ось Y - частотная характеристика. ЧАС(ω) и ось абсцисс - различные радианные частоты, ωя. Можно отметить, что две частоты, отмеченные на оси x, ωп и ωs. ωп указывает частоту среза полосы пропускания и ωs указывает частоту среза полосы заграждения. График в виде пульсации в верхнем левом углу - это пульсация полосы пропускания, а пульсация в правом нижнем углу - это пульсация полосы заграждения. Две пунктирные линии в верхнем левом углу графика обозначают δп а две пунктирные линии в правом нижнем углу обозначают δs. Все остальные перечисленные частоты указывают на экстремальные частоты графика частотной характеристики. В результате получается шесть экстремальных частот, а затем мы добавляем частоты полосы пропускания и полосы заграждения, чтобы получить в общей сложности восемь экстремальных частот на графике.

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

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

История создания оптимального КИХ-фильтра

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

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

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

История

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

Джеймс Макклеллан и Томас Паркс

Джеймс Макклеллан родился 5 октября 1947 г. в г. Гуам. Он получил степень бакалавра наук в Электротехника (1969) из Университет штата Луизиана.[2] После получения степени магистра наук (1972 г.) и доктора (1973 г.) от Университет Райса Доктор Макклеллан работал в лаборатории Линкольна Массачусетского технологического института с 1973 по 1975 год.[2] В 1975 году он стал профессором кафедры электротехники и информатики Массачусетского технологического института.[2] Проработав в университете семь лет, доктор Макклеллан присоединился к Schlumberger в 1982 году, где проработал пять лет.[2] С 1987 г. д-р Макклеллан был профессором электротехники в Технологический институт Джорджии.[2] Доктор Макклеллан получил множество наград за свою работу в области цифровых технологий. обработка сигналов и его применение к обработке матрицы датчиков: награда IEEE за технические достижения в области обработки сигналов (1987 г.), награда Общества обработки сигналов IEEE (1996 г.) и медаль за обработку сигналов IEEE Джека С. Килби (2004 г.).[1] В дополнение к полученным наградам, доктор Макклеллан опубликовал ряд значительных публикаций: компьютерные упражнения для обработки сигналов с использованием MATLAB 5 (1994), DSP First (1997), Signal Processing First (2003) и Теория чисел в DSP (1979).[1]

Томас Паркс родился 16 марта 1939 года в Буффало, штат Нью-Йорк. Он получил степени бакалавра (1961 г.), магистра наук (1964 г.) и доктора (1967 г.) в области электротехники от Корнелл Университет.[3] После получения докторской степени доктор Паркс присоединился к преподавательскому составу Университета Райса. Он был преподавателем с 1967 по 1986 год, когда поступил на факультет Корнельского университета.[3] Доктор Паркс является лауреатом множества наград, основанных на его исследованиях в области цифровой обработки сигналов с ее применением в теория сигналов, многоскоростные системы, интерполяция и дизайн фильтра: Премия Общества IEEE ASSP за технические достижения (1981), Премия Общества IEEE ASSP (1988), Премия президента Университета Райса (1999), Медаль третьего тысячелетия IEEE (2000) и Медаль за обработку сигналов Джека С. Килби (2004). ).[1] В дополнение к полученным наградам, доктор Паркс опубликовал многочисленные работы в области электротехники: алгоритмы свертки DFT / FFT (1985), дизайн цифровых фильтров (1987), Лаборатория цифровой обработки сигналов с использованием TMS 32010 (1988). , Лаборатория цифровой обработки сигналов с использованием TMS 320C25 (1990), Компьютерные упражнения для обработки сигналов (1994) и Компьютерные упражнения для обработки сигналов с использованием MATLAB 5 (1994).[1]

Алгоритм

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

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

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

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

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

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

Объяснение

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

Дополнительные примечания

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

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

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

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

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

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

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

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

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

Рекомендации

  1. ^ а б c d е ж грамм час я j k л м п о п q McClellan, J.H .; Паркс, Т. (2005). "Личная история Паркс-Мак Clellan алгоритм". Журнал IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM ... 22 ... 82M. Дои:10.1109 / MSP.2005.1406492.
  2. ^ а б c d е Макклеллан, Джеймс (1997), Джеймс Макклеллан Профиль, получено 2009-03-28
  3. ^ а б Парки, Томас (2006), Школа электротехники и компьютерной инженерии Корнельского университета, получено 2009-03-28
  4. ^ Джонс, Дуглас (2007), Дизайн КИХ-фильтра Паркс – Макклеллана, получено 2009-03-29
  5. ^ а б c Ловелл, Брайан (2003), Метод Паркс – Макклеллана (PDF), получено 2009-03-30

Дополнительные ссылки

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

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