Algoritmus návrhu filtru Parks – McClellan - Parks–McClellan filter design algorithm

Projděte a zastavte pásma filtru navrženého algoritmem Parks – McClellan
Osa y je frekvenční odezva H(ω) a osa x jsou různé frekvence radiánů, ωi. Je možné poznamenat, že dvě frekvence označené na ose x, ωstr a ωs. ωstr označuje mezní frekvenci propustného pásma a ωs označuje mezní frekvenci zastavovacího pásma. Zvlnění podobné grafu vlevo nahoře je zvlnění pásma propusti a zvlnění vpravo dole je zvlnění zastavovacího pásma. Dvě přerušované čáry v levé horní části grafu označují δstr a dvě přerušované čáry vpravo dole označují δs. Všechny ostatní uvedené frekvence označují extrémní frekvence grafu frekvenční odezvy. Výsledkem je, že existuje šest extrémních frekvencí, a pak přidáme propustné a zastavovací pásma, abychom na grafu dostali celkem osm extrémních frekvencí.

The Algoritmus Parks – McClellan, publikováno James McClellan a Thomas Parks v roce 1972, je iterační algoritmus pro nalezení optimálního Čebyševa konečná impulzní odezva (JEDLE) filtr. Algoritmus Parks – McClellan se používá k návrhu a implementaci účinných a optimálních filtrů FIR. K nalezení optimálních koeficientů filtru používá nepřímou metodu.

Cílem algoritmu je minimalizovat chybu v pásmech pass a stop využitím Chebyshevovy aproximace. Algoritmus Parks – McClellan je variantou Algoritmus Remezovy výměny, se změnou, která je speciálně navržena pro filtry FIR. Stala se standardní metodou pro návrh filtru FIR.

Historie optimálního návrhu filtru FIR

V šedesátých letech minulého století vědci v oblasti designu analogových filtrů používali Čebyševova aproximace pro design filtru. Během této doby bylo dobře známo, že nejlepší filtry obsahují ekvipripplikační charakteristiku ve velikosti frekvenční odezvy a eliptický filtr (nebo Cauerův filtr) byl optimální s ohledem na Čebyševovu aproximaci. Když revoluce digitálních filtrů začala v 60. letech, vědci použili a bilineární transformace k výrobě nekonečná impulzní odezva (IIR) digitální eliptické filtry. Rovněž uznali potenciál pro navrhování filtrů FIR, aby splnili stejný úkol filtrování, a brzy bylo zahájeno hledání optimálního filtru FIR pomocí Čebyševovy aproximace.[1]

Jak v matematice, tak ve strojírenství bylo dobře známo, že optimální odezva bude vykazovat ekvipripple chování a že počet vln lze spočítat pomocí Čebyševovy aproximace. V letech 1962 až 1971 bylo podniknuto několik pokusů o vytvoření návrhového programu pro optimální Čebyševův FIR filtr.[1] Navzdory mnoha pokusům většina neuspěla, obvykle kvůli problémům s implementací algoritmu nebo formulaci problému. Například Otto Herrmann navrhl metodu pro konstrukci ekvipripple filtrů s omezenými hranami pásma.[1] Tato metoda získala ekvivalentní frekvenční odezvu s maximálním počtem zvlnění řešením sady nelineárních rovnic. Další metoda zavedená v té době implementovala optimální Čebyševovu aproximaci, ale algoritmus byl omezen na návrh filtrů relativně nízkého řádu.[1]

Podobně jako Herrmannova metoda představil Ed Hofstetter algoritmus, který navrhoval filtry FIR s co největším počtem vln. Toto se stalo známé jako algoritmus Maximálního zvlnění. Algoritmus Maximal Ripple uložil alternativní chybový stav pomocí interpolace a poté vyřešil sadu rovnic, které muselo střídavé řešení uspokojit.[1] Jedno pozoruhodné omezení algoritmu Maximal Ripple bylo, že okraje pásma nebyly specifikovány jako vstupy do procedury návrhu. Spíše počáteční frekvence nastavena {ωi} a požadovaná funkce D(ωi) implicitně definoval pásmo průchodu a zastavení. Na rozdíl od předchozích pokusů o návrh optimálního filtru použil algoritmus Maximal Ripple výměnnou metodu, která se pokusila najít sadu frekvencí {ωi} kde nejlepší filtr měl své vlnky.[1] Algoritmus Maximal Ripple tedy nebyl optimálním designem filtru, ale měl docela významný dopad na to, jak bude algoritmus Parks – McClellan formulovat.

Dějiny

V srpnu 1970 vstoupil James McClellan na postgraduální studium na Rice University se zaměřením na matematické modely designu analogových filtrů a kvůli svému zájmu o design filtrů se zapsal do nového kurzu s názvem „Digitální filtry“.[1] Kurz společně vyučovali Thomas Parks a Sid Burrus. V té době byl DSP rozvíjející se obor a jako výsledek přednášky často zahrnovaly nedávno publikované výzkumné práce. Následující semestr, na jaře roku 1971, nabídl Thomas Parks kurz s názvem „Teorie signálu“, kterého se zúčastnil také McClellan.[1] Během jarních prázdnin semestru jel Parks z Houstonu do Princetonu, aby se zúčastnil konference, kde vyslechl prezentaci Eda Hofstettera o novém algoritmu návrhu filtru FIR (algoritmus Maximal Ripple). Přinesl příspěvek od Hofstettera, Oppenheima a Siegela zpět do Houstonu a přemýšlel o možnosti použití Čebyševovy aproximační teorie k návrhu FIR filtrů.[1] Slyšel, že metoda implementovaná v Hofstetterově algoritmu byla podobná výměnnému algoritmu Remez a rozhodl se pokračovat cestou použití výměnného algoritmu Remez. Studenti kurzu "Teorie signálu" byli požádáni, aby vytvořili projekt, a protože Čebyševova aproximace byla hlavním tématem kurzu, implementací tohoto nového algoritmu se stal projekt kurzu Jamese McClellana. To nakonec vedlo k algoritmu Parks – McClellan, který zahrnoval teorii optimální Čebyševovy aproximace a efektivní implementaci. Na konci jarního semestru se McClellan a Parks pokoušeli napsat variantu výměnného algoritmu Remez pro filtry FIR. Vývoj trval asi šest týdnů a některé optimální filtry byly úspěšně navrženy do konce května.

James McClellan a Thomas Parks

James McClellan se narodil 5. října 1947 v Guam. Získal Bachelor of Science v Elektrotechnika (1969) z Louisianská státní univerzita.[2] Po získání titulu Master of Science (1972) a doktorátu (1973) od Rice University Dr. McClellan pracoval v Lincoln Laboratory MIT v letech 1973 až 1975.[2] V roce 1975 se stal profesorem na katedře elektrotechniky a informatiky na MIT.[2] Poté, co sedm let pracoval na univerzitě, se připojil Dr. McClellan Schlumberger v roce 1982, kde pracoval pět let.[2] Od roku 1987 je Dr. McClellan profesorem elektrotechniky na Gruzínský technologický institut.[2] Dr. McClellan získal řadu ocenění za svou práci v digitální oblasti zpracování signálu a její aplikace na zpracování senzorových polí: IEEE Signal Processing Technical Achievement Award (1987), IEEE Signal Processing Society Award (1996) a IEEE Jack S. Kilby Signal Processing Medal (2004).[1] Kromě ocenění, která získal, publikoval Dr. McClellan řadu významných literárních děl: Počítačová cvičení pro zpracování signálu pomocí MATLAB 5 (1994), DSP First (1997), Signal Processing First (2003) a Teorie čísel v DSP (1979).[1]

Thomas Parks se narodil 16. března 1939 v Buffalu v New Yorku. Získal bakalářské (1961), magisterské (1964) a doktorské (1967) tituly z elektrotechniky z Cornell University.[3] Po absolvování doktorátu nastoupil Dr. Parks na fakultu na Rice University. Byl členem fakulty od roku 1967 do roku 1986, kdy nastoupil na fakultu na Cornell University.[3] Dr. Parks je držitelem několika ocenění na základě svého výzkumu zaměřeného na digitální zpracování signálu s jeho aplikací na teorie signálu, víceúrovňové systémy, interpolace a design filtru: Cena IEEE ASSP Society Technical Achievement Award (1981), Cena IEEE ASSP Society (1988), Cena prezidenta Rice University (1999), medaile IEEE Third Millennium Medal (2000) a medaile IEEE Jacka S. Kilbyho Signal Processing (2004) ).[1] Kromě ocenění, která získal, publikoval Dr. Parks řadu příspěvků v oblasti elektrotechniky: DFT / FFT Convolution Algorithms (1985), Digital Filter Design (1987), A Digital Signal Processing Laboratory Using the TMS 32010 (1988) „Laboratoř zpracování digitálního signálu využívající TMS 320C25 (1990), Počítačová cvičení pro zpracování signálu (1994) a Počítačová cvičení pro zpracování signálu pomocí MATLAB 5 (1994).[1]

Algoritmus

Algoritmus Parks – McClellan je implementován pomocí následujících kroků:[1]

  1. Inicializace: Vyberte extrémní sadu frekvencí {ωi(0)}.
  2. Aproximace konečné množiny: Vypočítejte nejlepší Čebyševovu aproximaci na současné extrémní množině, přičemž získáte hodnotu δ(m) pro chybu min-max na současné extrémní sadě.
  3. Interpolace: Vypočítejte chybovou funkci E (ω) přes celou sadu frekvencí Ω pomocí (2).
  4. Hledejte místní maxima |E(m)(ω)| na množině Ω.
  5. Pokud max(ωεΩ)|E(m)(ω)| > 8(m), poté aktualizujte extrémní sadu na {ωi(m + 1)} výběrem nových frekvencí, kde |E(m)(ω)| má své lokální maxima. Ujistěte se, že se chyba střídá na seřazené sadě frekvencí, jak je popsáno v (4) a (5). Vraťte se ke kroku 2 a proveďte iteraci.
  6. Pokud max(ωεΩ)|E(m)(ω)| ≤ δ(m), pak je algoritmus kompletní. Použijte množinu {ωi(0)} a interpolační vzorec pro výpočet inverzní diskrétní Fourierovy transformace pro získání filtračních koeficientů.

Algoritmus Parks – McClellan lze přepracovat podle následujících kroků:[4]

  1. Počáteční odhad extrémních frekvencí L + 2.
  2. Vypočítejte δ pomocí dané rovnice.
  3. Pomocí Lagrangeovy interpolace vypočítáme hustou sadu vzorků A (ω) přes propustné a stopové pásmo.
  4. Určete nové největší extrémy L + 2.
  5. Pokud věta o střídání není splněna, vrátíme se k (2) a iterujeme, dokud věta o střídání nebude splněna.
  6. Pokud je věta o střídání splněna, vypočítáme h (n) a máme hotovo.

Abychom získali základní znalosti o výše zmíněném algoritmu Parks – McClellan, můžeme výše uvedený algoritmus přepsat jednodušší formou jako:

  1. Hádejte, že polohy extrémů jsou rovnoměrně rozmístěny v pásmu pass a stop.
  2. Proveďte polynomiální interpolaci a přehodnoťte polohy lokálních extrémů.
  3. Přesuňte extrémy do nových pozic a opakujte, dokud se extrémy nezastaví.

Vysvětlení

Obrázek výše vpravo zobrazuje různé extrémní frekvence pro zobrazený graf. Extrémní frekvence jsou maximální a minimální body v pásmech stop a pass. Zvlnění zastavovacího pásma je spodní část zvlnění v pravé dolní části grafu a zvlnění pásmové propusti je horní část zvlnění v levé horní části grafu. Přerušované čáry procházející grafem označují δ nebo maximální chybu. Vzhledem k pozicím extrémních frekvencí existuje vzorec pro optimální δ nebo optimální chybu. Jelikož neznáme optimální δ ani přesnou polohu extrémů na první pokus, iterujeme. Efektivně nejprve předpokládáme polohy extrémů a vypočítáme δ. Poté znovu odhadneme a přesuneme extrémy a přepočítáme δ nebo chybu. Tento postup opakujeme, dokud se δ nepřestane měnit. Algoritmus způsobí, že se chyba δ sblíží, obvykle v deseti až dvanácti iteracích.[5]

Další poznámky

Před použitím Čebyševovy aproximace byla nutná řada kroků:

  1. Definujte sadu základní funkce pro aproximaci a
  2. Využijte skutečnost, že pásma propustnosti a zastavení pásmových filtrů by byla vždy oddělena přechodovými oblastmi.[1]

Vzhledem k tomu, že filtry FIR lze redukovat na součet kosinových případů, lze k provedení všech možných filtrů FIR s lineární fází použít stejný základní program. Na rozdíl od přístupu Maximum Ripple by nyní mohly být okraje pásma specifikovány předem.

K dosažení efektivní implementace optimálního designu filtru pomocí algoritmu Parks-McClellan je třeba překonat dvě potíže:

  1. Definování flexibilní směnné strategie a
  2. Implementace robustní metody interpolace.[1]

V jistém smyslu programování zahrnovalo implementaci a adaptaci známého algoritmu pro použití při návrhu filtru FIR. K zefektivnění programu byly vzaty dvě tváře výměnné strategie:

  1. Přidělení extrémních frekvencí mezi pásmem propustnosti a zastavení a
  2. Umožnění pohybu extrémů mezi pásmy při iteraci programu.[1]

Při inicializaci lze počet extrémů v propustném a zastavovacím pásmu přiřadit pomocí poměru velikostí pásem. Okraj propustného a zastavovacího pásma by navíc byl vždy umístěn v extrémní sadě a logika programu udržovala tyto okrajové frekvence v extrémní sadě. Pohyb mezi pásmy byl řízen porovnáním velikosti chyb na všech kandidátních extremálních frekvencích a převzetím největší. Druhým prvkem algoritmu byl interpolační krok potřebný k vyhodnocení chybové funkce. Použili metodu zvanou barycentrická forma Lagrangeovy interpolace, která byla velmi robustní.

Všechny podmínky pro algoritmus Parks – McClellan jsou založeny na Čebyševově alternační větě. Věta o střídání uvádí, že polynom stupně L, který minimalizuje maximální chybu, bude mít alespoň extrémy L + 2. Optimální frekvenční odezva stěží dosáhne maximálních hranic zvlnění.[5] Extrémy se musí vyskytovat na hranách pásma propustnosti a zastavení a buď na ω = 0 nebo ω = π nebo na obou. Derivát polynomu stupně L je polynom stupně L-1, který může být nula nanejvýš na místech L-1.[5] Takže maximální počet lokálních extrémů je místní extrémy L-1 plus 4 hrany pásma, což dává celkem extrémů L + 3.

Reference

  1. ^ A b C d E F G h i j k l m n Ó str q McClellan, J.H .; Parks, T.W. (2005). „Osobní historie Parks-Mc Clellan algoritmus". IEEE Signal Processing Magazine. 22 (2): 82–86. Bibcode:2005ISPM ... 22 ... 82M. doi:10.1109 / MSP.2005.1406492.
  2. ^ A b C d E McClellan, James (1997), Profil Jamese McClellana, vyvoláno 2009-03-28
  3. ^ A b Parks, Thomas (2006), School of Electrical and Computer Engineering, Cornell University, vyvoláno 2009-03-28
  4. ^ Jones, Douglas (2007), Design FIR filtrů Parks – McClellan, vyvoláno 2009-03-29
  5. ^ A b C Lovell, Brian (2003), Metoda Parks – McClellan (PDF), vyvoláno 2009-03-30

Další odkazy

Následující další odkazy poskytují informace o algoritmu Parks-McClellan a také o dalších výzkumech a článcích od Jamese McClellana a Thomase Parkse:

  1. Čebyševova aproximace pro nerekurzivní digitální filtry s lineární fází
  2. Krátká nápověda k Parks – McClellan Design FIR Low Pass filtrů pomocí MATLABu
  3. Úvod do DSP
  4. Dokumentace MathWorks MATLAB
  5. Poznámky k přednášce ELEC4600
  6. Implementace kódu C (licence LGPL) - autor Jake Janovetz
  7. Software Iowa Hills. „Příklad C kódu“. Citováno 3. května 2014.
  8. Revidovaný a rozšířený algoritmus McClellan, Parks & Rabiner, 1975; Fortranský kód.