Parks – McClellan filtre tasarım algoritması - Parks–McClellan filter design algorithm

Image
Parks-McClellan algoritması ile tasarlanmış bir filtrenin geçiş ve durdurma bantları
Y ekseni, H (ω) frekans tepkisidir ve x ekseni çeşitli radyan frekanslarıdır, ω i . X ekseninde işaretlenen iki frekansın ω p ve ω s olduğu not edilebilir . ω p , geçiş bandı kesme frekansını ve ω s , durdurma bandı kesme frekansını gösterir. Sol üstteki dalgalanma benzeri grafik geçiş bandı dalgalanması ve sağ alttaki dalgalanma durdurma bandı dalgalanmasıdır. Grafiğin sol üst kısmında iki kesikli çizgiler δ gösterir p ve altta iki kesikli çizgiler doğru δ göstermektedir s . Listelenen diğer tüm frekanslar, frekans yanıt grafiğinin aşırı frekanslarını gösterir. Sonuç olarak, altı ekstrem frekans vardır ve daha sonra grafik üzerinde toplam sekiz ekstrem frekans vermek için geçiş bandı ve durdurma bandı frekanslarını ekliyoruz.

Park-McClellan algoritması tarafından yayınlanan, James McClellan ve Thomas Parks , 1972 yılında, uygun Chebyshev bulmak için yinelemeli bir algoritma sonlu dürtü yanıtı (FIR) filtresi . Parks-McClellan algoritması, verimli ve optimum FIR filtreleri tasarlamak ve uygulamak için kullanılır. Optimal filtre katsayılarını bulmak için dolaylı bir yöntem kullanır.

Algoritmanın amacı, Chebyshev yaklaşımını kullanarak geçiş ve durdurma bantlarındaki hatayı en aza indirmektir. Parks-McClellan algoritması , özellikle FIR filtreleri için tasarlanmış değişikliğiyle Remez değişim algoritmasının bir varyasyonudur . FIR filtre tasarımı için standart bir yöntem haline geldi.

Optimum FIR filtre tasarımının geçmişi

1960'larda, analog filtre tasarımı alanındaki araştırmacılar, filtre tasarımı için Chebyshev yaklaşımını kullanıyorlardı . Bu süre zarfında, en iyi filtrelerin, frekans yanıt büyüklüklerinde bir eşitlik özelliği içerdiği ve eliptik filtrenin (veya Cauer filtresinin) Chebyshev yaklaşımı açısından optimal olduğu iyi biliniyordu . 1960'larda dijital filtre devrimi başladığında, araştırmacılar sonsuz dürtü tepkisi (IIR) dijital eliptik filtreler üretmek için iki doğrusal bir dönüşüm kullandılar . Aynı filtreleme görevini gerçekleştirmek için FIR filtreleri tasarlama potansiyelini de fark ettiler ve kısa süre sonra Chebyshev yaklaşımı kullanılarak optimum FIR filtresi için arama başladı.

Hem matematikte hem de mühendislikte en iyi cevabın eş uçlu bir davranış göstereceği ve dalgalanma sayısının Chebyshev yaklaşımı kullanılarak sayılabileceği iyi biliniyordu. 1962 ile 1971 arasındaki dönemde, optimal Chebyshev FIR filtresi için bir tasarım programı üretmek için çeşitli girişimlerde bulunuldu. Çok sayıda denemeye rağmen çoğu, genellikle algoritmik uygulamadaki veya problem formülasyonundaki problemler nedeniyle başarılı olamadı. Örneğin Otto Herrmann, kısıtlı bant kenarları olan eşit uçlu filtreler tasarlamak için bir yöntem önerdi. Bu yöntem, bir dizi doğrusal olmayan denklemi çözerek maksimum dalgalanma sayısıyla bir eş uçlu frekans tepkisi elde etti. O sırada tanıtılan başka bir yöntem, optimum bir Chebyshev yaklaşımı uyguladı, ancak algoritma nispeten düşük dereceli filtrelerin tasarımıyla sınırlıydı.

Ed Hofstetter, Herrmann'ın yöntemine benzer şekilde, mümkün olduğunca çok dalgalı FIR filtreleri tasarlayan bir algoritma sundu. Bu, Maksimal Ripple algoritması olarak bilinir hale geldi. Maksimal Ripple algoritması, enterpolasyon yoluyla alternatif bir hata koşulu uyguladı ve ardından alternatif çözümün karşılaması gereken bir dizi denklemi çözdü. Maksimal Dalgalanma algoritmasının dikkate değer bir sınırlaması, bant kenarlarının tasarım prosedürüne girdi olarak belirtilmemesiydi. Daha ziyade, başlangıç ​​frekans seti { ω i } ve istenen fonksiyon D ( ω i ), geçiş ve durdurma bandını örtük olarak tanımladı. Optimal filtre tasarımı için daha önceki girişimlerde farklı olarak, Maksimal Dalgalanma algoritması frekans setini {bulmaya çalıştık bir değişim yöntemi kullanılmıştır ω i iyi filtrenin dalgaların vardı}. Dolayısıyla, Maksimal Dalgalanma algoritması optimal bir filtre tasarımı değildi, ancak Parks-McClellan algoritmasının nasıl formüle edileceği üzerinde oldukça önemli bir etkiye sahipti.

Tarih

Ağustos 1970'te James McClellan, analog filtre tasarımının matematiksel modellerinde yoğunlaşarak Rice Üniversitesi'nde yüksek lisans okuluna girdi ve filtre tasarımına olan ilgisi nedeniyle "Dijital Filtreler" adlı yeni bir kursa kaydoldu. Kurs, Thomas Parks ve Sid Burrus tarafından ortaklaşa öğretildi . O zamanlar, DSP gelişmekte olan bir alandı ve sonuç olarak dersler genellikle yakın zamanda yayınlanan araştırma makalelerini içeriyordu. Bir sonraki dönem olan 1971 baharında Thomas Parks, McClellan'ın da aldığı "Sinyal Teorisi" adlı bir ders verdi. Parks, dönemin bahar tatilinde, Ed Hofstetter'in yeni bir FIR filtre tasarım algoritması (Maximal Ripple algoritması) hakkındaki sunumunu duyduğu bir konferansa katılmak için Houston'dan Princeton'a gitti. FIR filtreleri tasarlamak için Chebyshev yaklaşım teorisini kullanma olasılığını düşünerek Hofstetter, Oppenheim ve Siegel tarafından yazılan makaleyi Houston'a geri getirdi. Hofstetter'in algoritmasında uygulanan yöntemin Remez değişim algoritmasına benzer olduğunu duydu ve Remez değişim algoritmasını kullanma yolunu izlemeye karar verdi. "Sinyal Teorisi" dersindeki öğrencilerden bir proje yapmaları istendi ve derste Chebyshev yaklaşımı önemli bir konu olduğundan, bu yeni algoritmanın uygulanması James McClellan'ın ders projesi oldu. Bu sonuçta, optimum Chebyshev yaklaşımı teorisini ve verimli bir uygulamayı içeren Parks-McClellan algoritmasına yol açtı. Bahar döneminin sonunda McClellan ve Parks, FIR filtreleri için Remez değişim algoritmasının bir varyasyonunu yazmaya çalışıyorlardı. Geliştirilmesi yaklaşık altı hafta sürdü ve bazı optimum filtreler Mayıs ayı sonuna kadar başarıyla tasarlandı.

James McClellan ve Thomas Parkları

James McClellan 5 Ekim 1947'de Guam'da doğdu . Elektrik Mühendisliği alanında Lisans derecesini (1969) Louisiana Eyalet Üniversitesi'nden aldı . Rice Üniversitesi'nden Yüksek Lisans (1972) ve Doktora (1973) derecelerini aldıktan sonra , Dr. McClellan 1973-1975 yılları arasında MIT Lincoln Laboratuvarı'nda çalıştı. 1975'te MIT Elektrik Mühendisliği ve Bilgisayar Bilimleri Bölümü'nde profesör oldu. Üniversitede yedi yıldır çalışan Dr. McClellan , 1982'de Schlumberger'e katıldı ve beş yıl burada çalıştı. 1987 yılından bu yana, Dr. McClellan Georgia Teknoloji Enstitüsü'nde Elektrik Mühendisliği profesörüdür . Dr. McClellan, dijital sinyal işleme alanındaki çalışmaları ve sensör dizisi işlemeye uyguladığı için çok sayıda ödül almıştır : IEEE Signal Processing Technical Achievement Award (1987), IEEE Signal Processing Society Award (1996) ve IEEE Jack S. Kilby Signal Processing Medal (2004). Dr. McClellan, aldığı ödüllere ek olarak, bir dizi önemli literatür yayınladı: MATLAB 5 Kullanarak Sinyal İşleme İçin Bilgisayar Tabanlı Egzersizler (1994), DSP First (1997), Signal Processing First (2003) ve DSP'de Sayı Teorisi (1979).

Thomas Parks 16 Mart 1939'da New York, Buffalo'da doğdu. Cornell Üniversitesi'nden Elektrik Mühendisliği alanında Lisans (1961), Master of Science (1964) ve Doktora (1967) derecelerini aldı . Doktora ile mezun olduktan sonra, Dr. Parks Rice Üniversitesi'nde fakülteye katıldı. Cornell Üniversitesi'nde fakülteye katıldığı 1967'den 1986'ya kadar öğretim üyesidir. Dr. Parks, sinyal teorisi , çoklu oranlı sistemler, enterpolasyon ve filtre tasarımına uygulamasıyla dijital sinyal işlemeye odaklanan araştırmasına dayanan çok sayıda ödülün sahibidir : IEEE ASSP Society Technical Achievement Award (1981), IEEE ASSP Society Award (1988) ), Rice Üniversitesi Başkanlık Ödülü (1999), IEEE Üçüncü Milenyum Madalyası (2000) ve IEEE Jack S. Kilby Sinyal İşleme Madalyası (2004). Dr.Park, aldığı ödüllere ek olarak, elektrik mühendisliği alanına sayısız katkıları yayınlamıştır: DFT / FFT Evrişim Algoritmaları (1985), Dijital Filtre Tasarımı (1987), TMS 32010 Kullanan Dijital Sinyal İşleme Laboratuvarı (1988) , TMS 320C25 (1990) Kullanan Dijital Sinyal İşleme Laboratuvarı, Sinyal İşleme için Bilgisayar Tabanlı Alıştırmalar (1994) ve MATLAB 5 Kullanarak Sinyal İşleme için Bilgisayar Tabanlı Alıştırmalar (1994).

Algoritma

Parks-McClellan Algoritması aşağıdaki adımlar kullanılarak uygulanır:

  1. Başlatma: Uç bir frekans kümesi seçin {ω i (0) }.
  2. Sonlu Küme Yaklaşımı: Mevcut uç küme üzerindeki en iyi Chebyshev yaklaşımını hesaplayın, mevcut uç küme üzerindeki min-maks hatası için bir δ (m) değeri verin .
  3. Enterpolasyon: (2) 'yi kullanarak tüm frekanslar Ω üzerinden hata fonksiyonu E (ω)' yi hesaplayın .
  4. Yerel maksimum | E (m) (ω) | sette Ω.
  5. Eğer max (ωεΩ) | E (m) (ω) | > δ (m) , sonra yeni frekansları seçerek uç kümeyi { ω i (m + 1) } olarak güncelleyin burada | E (m) (ω) | yerel maksimum değerine sahiptir. Hatanın, (4) ve (5) 'de açıklandığı gibi sıralı frekanslar setinde değiştiğinden emin olun. 2. Adıma dönün ve yineleyin.
  6. Eğer max (ωεΩ) | E (m) (ω) | ≤ δ (m) ise algoritma tamamlanır. Filtre katsayılarını elde etmek için bir ters ayrık Fourier dönüşümünü hesaplamak için {ω i (0) } kümesi ve enterpolasyon formülünü kullanın.

Parks-McClellan Algoritması aşağıdaki adımlarla yeniden ifade edilebilir:

  1. L + 2 ekstrem frekanslarının ilk tahminini yapın.
  2. Verilen denklemi kullanarak δ hesaplayın.
  3. Lagrange İnterpolasyonunu kullanarak, geçiş bandı ve durdurma bandı üzerindeki yoğun A (ω) örnek kümesini hesaplıyoruz.
  4. Yeni L + 2 en büyük ekstremayı belirleyin.
  5. Değişim teoremi karşılanmazsa, o zaman (2) 'ye geri döneriz ve alternatif teoremi karşılanana kadar yineleriz.
  6. Değişim teoremi karşılanırsa, h (n) 'yi hesaplarız ve biter.

Yukarıda bahsedilen Parks-McClellan Algoritması hakkında temel bir anlayış kazanmak için, yukarıdaki algoritmayı daha basit bir biçimde aşağıdaki gibi yeniden yazabiliriz:

  1. Ekstremanın konumlarının geçiş ve durdurma bandında eşit aralıklarla yerleştirildiğini tahmin edin.
  2. Polinom enterpolasyonunu gerçekleştirin ve yerel ekstremanın konumlarını yeniden tahmin edin.
  3. Ekstremayı yeni konumlara taşıyın ve ekstremanın kayması durana kadar yineleyin.

Açıklama

Sağdaki yukarıdaki resim, gösterilen çizim için çeşitli uç frekansları göstermektedir. Ekstrem frekanslar, durdurma ve geçiş bantlarındaki maksimum ve minimum noktalardır. Durdurma bandı dalgalanması, grafiğin sağ alt kısmındaki dalgalanmaların alt kısmıdır ve geçiş bandı dalgalanması, grafiğin sol üstündeki dalgaların üst kısmıdır. Çizim boyunca giden kesikli çizgiler δ veya maksimum hatayı gösterir. Aşırı frekansların pozisyonları göz önüne alındığında, optimum δ veya optimum hata için bir formül vardır. İlk denemede ekstremanın optimum δ veya tam konumlarını bilmediğimiz için, yineliyoruz. Etkili bir şekilde, başlangıçta ekstremanın konumlarını üstleniyoruz ve δ'yi hesaplıyoruz. Daha sonra ekstremayı yeniden tahmin edip taşıyoruz ve δ veya hatayı yeniden hesaplıyoruz. Bu işlemi δ değişmeyi bırakana kadar tekrar ederiz. Algoritma, δ hatasının, genellikle on ila on iki yineleme içinde yakınsamasına neden olacaktır.

Ek Notlar

Chebyshev yaklaşımını uygulamadan önce bir dizi adım gerekliydi:

  1. Yaklaşım için temel işlev kümesini tanımlayın ve
  2. Bant geçiren filtrelerin geçiş ve durdurma bantlarının her zaman geçiş bölgeleri ile ayrılması gerçeğinden yararlanın.

FIR filtreleri kosinüs durumunun toplamına indirgenebileceğinden, tüm olası doğrusal fazlı FIR filtrelerini gerçekleştirmek için aynı çekirdek program kullanılabilir. Maksimum Ripple yaklaşımının aksine, bant kenarları artık önceden belirlenebilir.

Parks-McClellan algoritmasını kullanarak optimum filtre tasarımının verimli bir şekilde uygulanmasını sağlamak için iki zorluğun üstesinden gelinmesi gerekir:

  1. Esnek bir değişim stratejisi tanımlamak ve
  2. Sağlam bir enterpolasyon yöntemi uygulamak.

Bir anlamda, programlama, FIR filtre tasarımında kullanılmak üzere bilinen bir algoritmanın uygulanmasını ve uyarlanmasını içeriyordu. Programı daha verimli hale getirmek için değişim stratejisinin iki yüzü alındı:

  1. Uç frekansların geçiş ve durdurma bantları arasında tahsis edilmesi ve
  2. Program yinelendikçe uçların bantlar arasında hareket etmesini sağlar.

Başlangıçta, geçiş ve durdurma bandındaki uçların sayısı, bantların boyutlarının oranı kullanılarak atanabilir. Ayrıca, geçiş ve durdurma bandı kenarı her zaman uç kümeye yerleştirilir ve programın mantığı bu kenar frekanslarını uç kümede tutar. Bantlar arasındaki hareket, tüm aday aşırı frekanslardaki hataların boyutu karşılaştırılarak ve en büyüğü alınarak kontrol edildi. Algoritmanın ikinci öğesi, hata fonksiyonunu değerlendirmek için gereken enterpolasyon adımıdır. Lagrange interpolasyonunun Barycentric formu adı verilen ve çok sağlam olan bir yöntem kullandılar.

Parks-McClellan algoritmasının tüm koşulları, Chebyshev'in alternasyon teoremine dayanmaktadır. Değişim teoremi, maksimum hatayı en aza indiren L derecesinin polinomunun en az L + 2 ekstremaya sahip olacağını belirtir. Optimum frekans tepkisi, maksimum dalgalanma sınırlarına zorlukla ulaşacaktır. Ekstrema, geçiş ve durdurma bandı kenarlarında ve ya ω = 0 ya da ω = π ya da her ikisinde meydana gelmelidir. L dereceli bir polinomun türevi, L-1 derecesinde bir polinomdur ve en fazla L-1 konumunda sıfır olabilir. Dolayısıyla maksimum lokal ekstremma sayısı L-1 yerel ekstremma artı 4 bant kenarıdır ve toplam L + 3 ekstremma verir.

Referanslar

Ek referanslar

Aşağıdaki ek bağlantılar, Parks-McClellan Algoritmasının yanı sıra James McClellan ve Thomas Parks tarafından yazılan diğer araştırma ve makaleler hakkında bilgi sağlar:

  1. Doğrusal Fazlı Yinelemeli Olmayan Dijital Filtreler için Chebyshev Yaklaşımı
  2. Parklar Üzerine Kısa Yardım - MATLAB Kullanarak FIR Düşük Geçişli Filtrelerin McClellan Tasarımı
  3. TTP'ye Giriş
  4. MathWorks MATLAB belgeleri
  5. ELEC4600 Ders Notları
  6. C Kodu Uygulaması (LGPL Lisansı) - Jake Janovetz tarafından
  7. Iowa Hills Yazılımı. "Örnek C Kodu" . Alındı 3 Mayıs 2014 .
  8. Revize edilmiş ve genişletilmiş algoritma McClellan, Parks ve Rabiner, 1975; Fortran kodu.