Parklar - McClellan filtrini loyihalash algoritmi - Parks–McClellan filter design algorithm

Parks - McClellan algoritmi asosida ishlab chiqilgan filtrning o'tish va to'xtash bantlari
Y o'qi chastotaga javob beradi H(ω) va x o'qi har xil radian chastotalari, ωmen. Shuni ta'kidlash kerakki, x o'qida belgilangan ikkita chastota, ωp va ωs. ωp pass bandining uzilish chastotasini va ωs to'xtash tasmasini kesish chastotasini bildiradi. Yuqoridagi chap tomondagi uchastka - bu o'tish bantining to'lqini va pastki o'ngdagi to'lqin - to'xtash tasmasi. Grafikning yuqori chap qismidagi ikkita chiziqli chiziq δ ni bildiradip va pastki o'ngdagi ikkita chiziq chiziq lines ni bildiradis. Ro'yxatda keltirilgan barcha boshqa chastotalar chastota javob uchastkasining ekstremal chastotalarini bildiradi. Natijada, oltita ekstremal chastota mavjud, keyin biz uchastkada jami sakkizta ekstremal chastotani berish uchun o'tish diapazonini va to'xtash diapazonini qo'shamiz.

The Parklar - McClellan algoritmitomonidan nashr etilgan Jeyms Makklelan va Tomas Parks 1972 yilda bu maqbul Chebyshevni topish uchun takrorlanadigan algoritmdir cheklangan impulsli javob (FIR) filtr. Parks - McClellan algoritmidan samarali va maqbul FIR filtrlarini loyihalash va amalga oshirish uchun foydalaniladi. Optimal filtr koeffitsientlarini topish uchun bilvosita usuldan foydalaniladi.

Algoritmning maqsadi Chebyshev yaqinlashuvidan foydalanib, o'tish va to'xtash bantlaridagi xatoni minimallashtirishdir. Parks - McClellan algoritmi - ning o'zgarishi Remez almashish algoritmi, FIR filtrlari uchun maxsus ishlab chiqilganligi bilan. Bu FIR filtri dizayni uchun standart usulga aylandi.

FIR filtrining optimal dizayni tarixi

1960-yillarda analog filtr dizayni sohasidagi tadqiqotchilar Chebyshevning taxminiyligi filtr dizayni uchun. Shu vaqt ichida, eng yaxshi filtrlarda chastotaga javob berish kattaligi va elliptik filtr (yoki Cauer filtri) Chebyshev yaqinlashuvi bo'yicha maqbul edi. 1960-yillarda raqamli filtr inqilobi boshlanganda tadqiqotchilar a ikki tomonlama konvertatsiya ishlab chiqarish cheksiz impulsli javob (IIR) raqamli elliptik filtrlar. Ular bir xil filtrlash vazifasini bajarish uchun FIR filtrlarini loyihalashtirish imkoniyatlarini tan oldilar va tez orada Chebyshev yaqinlashuvi yordamida optimal FIR filtrini qidirish boshlandi.[1]

Matematikada ham, muhandislikda ham yaxshi ma'lumki, eng maqbul javob ekvipipple xatti-harakatini namoyish etadi va to'lqinlar sonini Chebyshev yaqinlashuvi yordamida hisoblash mumkin. Chebyshev FIR optimal filtri uchun dizayn dasturini ishlab chiqarishga bir nechta urinishlar 1962-1971 yillar oralig'ida amalga oshirildi.[1] Ko'plab urinishlarga qaramay, ko'pchilik muvaffaqiyatsizlikka uchradi, odatda algoritmik dastur yoki muammolarni shakllantirishdagi muammolar tufayli. Masalan, Otto Herrmann cheklangan tarmoqli chekkalari bo'lgan ekvipipple filtrlarini loyihalashtirish usulini taklif qildi.[1] Ushbu usul chiziqsiz tenglamalar to'plamini echish orqali maksimal to'lqinlar soniga ega bo'lgan ekvipipple chastotali javobni oldi. O'sha paytda kiritilgan yana bir usul Chebyshevning optimal taxminiyligini amalga oshirdi, ammo algoritm nisbatan past darajadagi filtrlarni loyihalash bilan cheklandi.[1]

Herrmann uslubiga o'xshab, Ed Hofstetter FIR filtrlarini iloji boricha ko'proq to'lqinlar bilan ishlab chiqadigan algoritmni taqdim etdi. Bu Maksimal Ripple algoritmi sifatida tanilgan. Maksimal Ripple algoritmi interpolatsiya orqali o'zgaruvchan xato shartini qo'ydi va keyinchalik o'zgaruvchan echim qondirishi kerak bo'lgan tenglamalar to'plamini echdi.[1] Maksimal Ripple algoritmining diqqatga sazovor joylaridan biri shundaki, tarmoqli qirralari dizayn protsedurasiga kirish sifatida ko'rsatilmagan. Aksincha, dastlabki chastota o'rnatildi {ωmen} va kerakli funktsiya D.(ωmen) o'tish va to'xtash bandini bilvosita aniqladi. Optimal filtrni loyihalashtirish bo'yicha avvalgi urinishlardan farqli o'laroq, Maksimal Ripple algoritmi chastota to'plamini topishga harakat qilgan almashinuv usulidan foydalandi {ωmen} bu erda eng yaxshi filtrning to'lqinlari bor edi.[1] Shunday qilib, Maksimal Ripple algoritmi filtrning optimal dizayni emas edi, lekin Parks-McClellan algoritmini qanday shakllantirishiga sezilarli ta'sir ko'rsatdi.

Tarix

1970 yil avgustda Jeyms Makklellan Rays universiteti aspiranturasiga analog filtr dizayni matematik modellarida kontsentratsiya bilan o'qishga kirdi va filtr dizayniga qiziqishi sababli "Raqamli filtrlar" deb nomlangan yangi kursga o'qishga kirdi.[1] Kursni birgalikda Tomas Parks va Sid Burrus. O'sha paytda DSP rivojlanayotgan soha edi va natijada ma'ruzalarda tez-tez yaqinda chop etilgan tadqiqot ishlari qatnashdi. Keyingi semestrda, 1971 yil bahorida Tomas Parks "Signal nazariyasi" nomli kursni taklif qildi, u Makklelan ham o'qidi.[1] Semestrning bahorgi ta'tilida Parks konferentsiyada qatnashish uchun Xyustondan Prinstonga yo'l oldi, u erda Ed Hofstetterning FIR filtrini loyihalashtirishning yangi algoritmi (Maksimal Ripple algoritmi) haqidagi taqdimotini tingladi. U Xofstetter, Oppenxaym va Zigel tomonidan qog'ozni Xyustonga olib kelib, FIR filtrlarini loyihalash uchun Chebyshevning yaqinlashish nazariyasidan foydalanish imkoniyatini o'ylab topdi.[1] U Xofstetter algoritmida tatbiq etilgan usul Remez almashish algoritmiga o'xshashligini eshitdi va Remez almashish algoritmidan foydalanish yo'lini tanlashga qaror qildi. "Signal nazariyasi" kursi talabalari loyihani bajarishlari kerak edi va Chebyshevning taxminiyligi kursning asosiy mavzusi bo'lganligi sababli, ushbu yangi algoritmni amalga oshirish Jeyms Makklelanning kurs loyihasi bo'ldi. Bu oxir-oqibat Chebyshevning optimal yaqinlashuvi nazariyasini va samarali amalga oshirishni o'z ichiga olgan Parks-Makklelan algoritmiga olib keldi. Bahorgi semestr oxirida McClellan va Parks FIR filtrlari uchun Remez almashish algoritmining o'zgarishini yozishga harakat qilishdi. Taxminan olti hafta davom etdi va may oyining oxiriga qadar ba'zi optimal filtrlar muvaffaqiyatli ishlab chiqildi.

Jeyms Makklelan va Tomas Parks

Jeyms Makklelan 1947 yil 5 oktyabrda tug'ilgan Guam. Ilmiy bakalavrini qabul qildi Elektrotexnika (1969) dan Luiziana davlat universiteti.[2] Ilmiy magistr (1972) va doktorlik (1973) darajalarini olganidan so'ng Rays universiteti, Doktor Makklellan 1973 yildan 1975 yilgacha MIT Linkoln laboratoriyasida ishlagan.[2] 1975 yilda MIT elektrotexnika va informatika kafedrasi professori bo'ldi.[2] Universitetda etti yil ishlagandan so'ng doktor Makklelan qo'shildi Schlumberger 1982 yilda, u erda besh yil ishlagan.[2] 1987 yildan beri doktor Makklelan elektrotexnika kafedrasida professor Jorjiya Texnologiya Instituti.[2] Doktor Makklelan raqamli ishlash uchun ko'plab mukofotlarga sazovor bo'ldi signallarni qayta ishlash va uni sensorlar qatorini qayta ishlashga tatbiq etish: IEEE Signal Processing Technical Achievement Award (1987), IEEE Signal Processing Society Award (1996) va IEEE Jack S. Kilby Signal Processing Medal (2004).[1] Doktor Makklelan olgan mukofotlaridan tashqari, bir qator muhim adabiyotlarni nashr etdi: MATLAB 5 (1994), DSP First (1997), Signal Processing First (2003) va DSP-dagi raqamlar nazariyasi (1979).[1]

Tomas Parks 1939 yil 16 martda Nyu-Yorkning Buffalo shahrida tug'ilgan. Bakalavr (1961), fan magistri (1964) va doktorlik (1967) darajalarini elektrotexnika bo'yicha olgan Kornell universiteti.[3] Doktorlik dissertatsiyasini tugatgach, doktor Parks Rays universitetining fakultetiga qo'shildi. U 1967 yildan 1986 yilgacha, Kornel universitetining fakultetiga qo'shilgandan keyin o'qituvchi bo'lgan.[3] Doktor Parks raqamli signallarni qayta ishlashga yo'naltirilgan tadqiqotlari asosida ko'plab mukofotlarga sazovor bo'ldi signal nazariyasi, ko'p qavatli tizimlar, interpolatsiya va filtr dizayni: IEEE ASSP Jamiyatining Texnik yutuqlari mukofoti (1981), IEEE ASSP Jamiyati mukofoti (1988), Rays universiteti prezidentining mukofoti (1999), IEEE Uchinchi ming yillik medali (2000) va IEEE Jek S. Kilbi signalni qayta ishlash medali (2004) ).[1] Doktor Parks olgan mukofotlaridan tashqari, elektrotexnika sohasiga ko'plab hissa qo'shgan: DFT / FFT konvolyutsiyasi algoritmlari (1985), raqamli filtr dizayni (1987), TMS 32010 (1988) dan foydalangan holda raqamli signallarni qayta ishlash laboratoriyasi. , TMS 320C25 (1990) dan foydalangan holda signallarni qayta ishlashning raqamli laboratoriyasi, signallarni qayta ishlash uchun kompyuterga asoslangan mashqlar (1994) va MATLAB 5 yordamida signallarni qayta ishlash uchun kompyuterga asoslangan mashqlar (1994).[1]

Algoritm

Parklar - Makklelan algoritmi quyidagi bosqichlar yordamida amalga oshiriladi:[1]

  1. Boshlash: Ekstremal chastotalar to'plamini tanlang {ωmen(0)}.
  2. Sonli to'plamni yaqinlashishi: qiymatini berib, hozirgi ekstremal to'plamdagi eng yaxshi Chebyshev yaqinligini hisoblang.(m) hozirgi ekstremal to'plamdagi min-max xatosi uchun.
  3. Interpolatsiya: Xato funktsiyasini hisoblang E (ω) (2) yordamida butun chastota to'plami bo'yicha.
  4. Mahalliy | ning maksimal qiymatlarini qidiringE(m)(ω)| to'plamda Ω.
  5. Agar maksimal bo'lsa(ωεΩ)|E(m)(ω)| > δ(m), keyin ekstremal to'plamni {ga yangilangωmen(m + 1)} qaerda | yangi chastotalarni tanlash orqaliE(m)(ω)| uning mahalliy maksimal darajasiga ega. Xato (4) va (5) da tasvirlangan tartiblangan chastotalar to'plamida o'zgarib turishiga ishonch hosil qiling. 2-bosqichga qayting va takrorlang.
  6. Agar maksimal bo'lsa(ωεΩ)|E(m)(ω)| ≤ δ(m), keyin algoritm to'liq bo'ladi. {Ω to'plamidan foydalaningmen(0)} va filtr koeffitsientlarini olish uchun teskari diskret Furye konvertatsiyasini hisoblash uchun interpolatsiya formulasi.

Parklar - Makklelan algoritmi quyidagi bosqichlarda qayta ko'rib chiqilishi mumkin:[4]

  1. L + 2 ekstremal chastotalari haqida dastlabki taxminni tuzing.
  2. Berilgan tenglamadan foydalanib δ ni hisoblang.
  3. Lagrange Interpolation-dan foydalanib, biz o'tkazgich va to'xtash bandi ustida A (ω) ning zich to'plamlarini hisoblaymiz.
  4. L + 2 ning eng katta ekstremasini aniqlang.
  5. Agar alternativa teoremasi qoniqtirilmasa, biz (2) ga qaytamiz va alternativ teorema bajarilguncha takrorlanamiz.
  6. Agar almashtirish teoremasi qondirilgan bo'lsa, u holda h (n) ni hisoblaymiz va biz bajaramiz.

Yuqorida aytib o'tilgan Parklar-Makklelan algoritmi haqida asosiy tushunchalarni olish uchun yuqoridagi algoritmni sodda shaklda qayta yozishimiz mumkin:

  1. Ekstremmaning pozitsiyalari taxmin qilingki, o'tish va to'xtash zonasida bir tekis joylashgan.
  2. Polinom interpolatsiyasini bajaring va mahalliy ekstremaning holatini qayta baholang.
  3. Ekstremani yangi holatga o'tkazing va ekstremma o'zgarishni to'xtatguncha takrorlang.

Izoh

Yuqoridagi o'ngdagi rasmda ko'rsatilgan uchastka uchun turli xil ekstremal chastotalar ko'rsatilgan. Ekstremal chastotalar to'xtash va o'tish zonalarida maksimal va minimal nuqtalardir. To'xtash tasmasi to'lqini - uchastkaning pastki o'ng qismidagi dalgalanmalarning pastki qismi va o'tish zonasi dalgalanması uchastkaning yuqori chap qismidagi to'lqinlarning yuqori qismidir. Uchastka bo'ylab kesilgan chiziqlar δ yoki maksimal xatoni bildiradi. Ekstremal chastotalarning pozitsiyalarini hisobga olgan holda, tegmaslik δ yoki tegmaslik xatoning formulasi mavjud. Birinchi urinishda biz eng yaxshi δ yoki ekstremmaning aniq pozitsiyalarini bilmasligimiz sababli takrorlaymiz. Effektiv ravishda biz dastlab ekstremma pozitsiyalarini qabul qilamiz va $ Delta $ ni hisoblaymiz. Keyin ekstremani qayta ko'rib chiqamiz va move ni yoki xatoni qayta hisoblaymiz. Process o'zgarishni to'xtatguncha biz ushbu jarayonni takrorlaymiz. Algoritm δ xatosining yaqinlashishiga olib keladi, odatda o'ndan o'n ikki takrorlashgacha.[5]

Qo'shimcha eslatmalar

Chebyshev taxminini qo'llashdan oldin bir qator qadamlar kerak edi:

  1. Yaqinlashish uchun baz funktsiya to'plamini aniqlang va
  2. Bandpass filtrlarining o'tish va to'xtash bantlari har doim o'tish mintaqalari bilan ajralib turishi kerakligidan foydalaning.[1]

FIR filtrlari kosinuslar yig'indisiga kamaytirilishi mumkin bo'lganligi sababli, barcha mumkin bo'lgan chiziqli fazali FIR filtrlarini bajarish uchun bir xil yadro dasturidan foydalanish mumkin edi. Maksimal Ripple yondashuvidan farqli o'laroq, endi tarmoqli qirralari oldindan belgilanishi mumkin.

Parks-McClellan algoritmidan foydalangan holda optimal filtr dizaynini samarali amalga oshirishga erishish uchun ikkita qiyinchilikni engish kerak:

  1. Moslashuvchan almashinuv strategiyasini aniqlash va
  2. Sog'lom interpolatsiya usulini amalga oshirish.[1]

Ba'zi ma'noda, dasturlash FIR filtri dizaynida foydalanish uchun ma'lum algoritmni amalga oshirishni va moslashtirishni o'z ichiga oladi. Dasturni yanada samarali qilish uchun almashinuv strategiyasining ikkita yuzi ko'rib chiqildi:

  1. O'tish va to'xtash polosalari orasidagi ekstremal chastotalarni taqsimlash va
  2. Dastur takrorlanganda bantlar orasidagi ekstremal harakatlanishni ta'minlash.[1]

Ishga tushirish paytida, o'tish va to'xtash bandidagi ekstremallar sonini bantlarning o'lchamlari nisbati yordamida belgilash mumkin. Bundan tashqari, o'tish va to'xtash bandining chekkasi har doim ekstremal to'plamga joylashtirilgan bo'lar edi va dastur mantig'i ushbu chekka chastotalarni ekstremal to'plamda ushlab turardi. Tarmoqlar orasidagi harakat barcha nomzodlarning ekstremal chastotalaridagi xatolar hajmini taqqoslash va eng kattasini olish orqali boshqarildi. Algoritmning ikkinchi elementi xato funktsiyasini baholash uchun zarur bo'lgan interpolatsiya bosqichi edi. Ular Lagranj interpolatsiyasining Barsentrik shakli deb nomlangan usulni qo'lladilar, bu juda mustahkam edi.

Parks - McClellan algoritmi uchun barcha shartlar Chebyshevning galma teoremasiga asoslangan. O'zgarishlar teoremasi, maksimal darajadagi xatoni minimallashtiradigan L darajadagi polinom kamida L + 2 ekstremaga ega bo'lishini aytadi. Optimal chastotali javob deyarli to'lqinlanish chegaralariga etmaydi.[5] Ekstrema o'tish va to'xtash tasmalarining chekkalarida va ω = 0 yoki ω = π yoki ikkalasida bo'lishi kerak. L darajadagi polinomning hosilasi L-1 darajadagi polinom bo'lib, L-1 joylarida ko'pi bilan nolga teng bo'lishi mumkin.[5] Shunday qilib, mahalliy ekstremalarning maksimal soni L-1 mahalliy ekstremma va 4 ta qirralarning qirralari bo'lib, jami L + 3 ekstremasini beradi.

Adabiyotlar

  1. ^ a b v d e f g h men j k l m n o p q Makklelan, JH; Parklar, T.V. (2005). "Parks-Mc shaxsiy tarixi Klelan algoritm ". IEEE Signal Processing jurnali. 22 (2): 82–86. Bibcode:2005ISPM ... 22 ... 82M. doi:10.1109 / MSP.2005.1406492.
  2. ^ a b v d e McClellan, Jeyms (1997), Jeyms Makklelan, olingan 2009-03-28
  3. ^ a b Parklar, Tomas (2006), Kornell universiteti elektrotexnika va kompyuter texnikasi maktabi, olingan 2009-03-28
  4. ^ Jons, Duglas (2007), Parklar - McClellan FIR filtri dizayni, olingan 2009-03-29
  5. ^ a b v Lovell, Brayan (2003), Parklar - McClellan usuli (PDF), olingan 2009-03-30

Qo'shimcha ma'lumotnomalar

Quyidagi qo'shimcha havolalar Parklar - Makklelan Algoritmi, shuningdek boshqa tadqiqotlar va Jeyms Makklelan va Tomas Parks tomonidan yozilgan maqolalar haqida ma'lumot beradi:

  1. Chebyshevning chiziqli fazali nonrekursiv raqamli filtrlarga yaqinlashuvi
  2. Parklar bo'yicha qisqa yordam - MATLAB-dan foydalangan holda FIR past o'tkazgichli filtrlarni loyihalash - McClellan
  3. DSP-ga kirish
  4. MathWorks MATLAB hujjatlari
  5. ELEC4600 ma'ruza matnlari
  6. C kodini amalga oshirish (LGPL litsenziyasi) - Jeyk Yanovetz tomonidan
  7. Ayova Hills dasturiy ta'minoti. "C kodi namunasi". Olingan 3 may 2014.
  8. Qayta ko'rib chiqilgan va kengaytirilgan algoritm McClellan, Parks, & Rabiner, 1975; Fortran kodi.