パークス・マクレランフィルタ設計アルゴリズム
信号処理方法
Parks–McClellan アルゴリズムによって設計されたフィルタの通過帯域と阻止帯域。
y 軸は周波数応答H (ω) で、 x 軸はさまざまなラジアン周波数ω iです。 x 軸にω pとω sの 2 つの周波数がマークされていることがわかります。ω p は通過帯域カットオフ周波数を示し、ω s は阻止帯域カットオフ周波数を示します。 左上のリップルのようなプロットは通過帯域リップルで、右下のリップルは阻止帯域リップルです。 グラフの左上の 2 本の破線は δ pを示し、右下の 2 本の破線は δ sを示しています。記載されている他のすべての周波数は、周波数応答プロットの極値周波数を示しています。 その結果、6 つの極値周波数があり、通過帯域周波数と阻止帯域周波数を追加すると、プロット上に合計 8 つの極値周波数が得られます。

パークス・マクレランアルゴリズムは、ジェームズ・マクレランとトーマス・パークスによって1972年に発表された、最適なチェビシェフ有限インパルス応答（FIR）フィルタを求める反復アルゴリズムです。パークス・マクレランアルゴリズムは、効率的で最適なFIRフィルタの設計と実装に用いられます。このアルゴリズムは、間接的な手法を用いて最適なフィルタ係数を求めます。

このアルゴリズムの目的は、チェビシェフ近似を用いて通過帯域と阻止帯域の誤差を最小化することです。パークス・マクレランアルゴリズムはレメズ交換アルゴリズムの派生版であり、FIRフィルタ向けに特化して設計されています。FIRフィルタ設計の標準的な手法となっています。

歴史

最適FIRフィルタ設計の歴史

1960年代、アナログフィルタ設計の研究者たちは、フィルタ設計にチェビシェフ近似を用いていました。当時、最良のフィルタは周波数応答振幅に等リプル特性を持ち、楕円フィルタ（またはカウアーフィルタ）がチェビシェフ近似に関して最適であることがよく知られていました。1960年代にデジタルフィルタ革命が始まると、研究者たちは双線形変換を用いて無限インパルス応答（IIR）デジタル楕円フィルタを開発しました。彼らはまた、同じフィルタリングタスクを達成するためにFIRフィルタを設計する可能性を認識し、すぐにチェビシェフ近似を用いた最適なFIRフィルタの探索が始まりました。[1]

数学と工学の両方において、最適応答は等リップル挙動を示し、リップル数​​はチェビシェフ近似を用いて数えられることはよく知られていました。1962年から1971年にかけて、最適チェビシェフFIRフィルタの設計プログラムを作成する試みがいくつか行われました。[1]多くの試みにもかかわらず、そのほとんどはアルゴリズムの実装や問題の定式化における問題のために成功しませんでした。例えば、オットー・ヘルマンは、帯域端を制限した等リップルフィルタの設計法を提案しました。[1]この方法は、一連の非線形方程式を解くことで、リップル数​​が最大となる等リップル周波数応答を得ました。当時導入された別の方法は、最適チェビシェフ近似を実装していましたが、そのアルゴリズムは比較的低次のフィルタの設計に限定されていました。[1]

Herrmann の方法に似て、Ed Hofstetter は、可能な限り多くのリップルを持つ FIR フィルタを設計するアルゴリズムを提示しました。これは、最大リップル アルゴリズムとして知られています。最大リップル アルゴリズムは、補間により交互誤差条件を課し、交互解が満たすべき一連の方程式を解きました。[1]最大リップル アルゴリズムの 1 つの顕著な制限は、バンド エッジが設計手順への入力として指定されないことです。そうではなく、初期周波数セット { ω i } と目的の関数D ( ω i ) によって、パス バンドとストップ バンドが暗黙的に定義されます。最適なフィルタを設計するこれまでの試みとは異なり、最大リップル アルゴリズムでは、最良のフィルタがリップルを持つ周波数セット { ω i } を見つけようとする交換法を使用しました。 [1]つまり、最大リップル アルゴリズムは最適なフィルタ設計ではありませんでしたが、Parks–McClellan アルゴリズムの定式化にかなり大きな影響を及ぼしました。

パークス・マクレランの歴史

1970年8月、ジェームズ・マクレランはライス大学大学院に入学し、アナログフィルタ設計の数理モデルを専攻しました。フィルタ設計への関心から、「デジタルフィルタ」という新設の講義を受講しました。[1]この講義はトーマス・パークスとシド・バーラスが共同で担当していました。当時、DSPは新興分野であったため、講義では最近発表された研究論文が頻繁に取り上げられました。翌学期、1971年春学期には、トーマス・パークスが「信号理論」という講義を開講し、マクレランもこの講義を受講しました。[1]その学期の春休み中、パークスは学会に出席するためヒューストンからプリンストンまで車で移動し、そこでエド・ホフステッターによる新しいFIRフィルタ設計アルゴリズム（最大リップルアルゴリズム）の発表を聞きました。彼はホフステッター、オッペンハイム、シーゲルによる論文をヒューストンに持ち帰り、チェビシェフ近似理論を用いてFIRフィルタを設計する可能性について考えました。[1]彼は、ホフステッターのアルゴリズムに実装されている手法がレメズ交換アルゴリズムに類似していることを知り、レメズ交換アルゴリズムを用いる道を進むことを決意した。「信号理論」コースの学生はプロジェクトに取り組まなければならなかったが、チェビシェフ近似はコースの主要なトピックであったため、この新しいアルゴリズムの実装はジェームズ・マクレランのコースプロジェクトとなった。これは最終的に、最適チェビシェフ近似の理論と効率的な実装を含むパークス・マクレランアルゴリズムにつながった。春学期の終わりまでに、マクレランとパークスはFIRフィルタ用のレメズ交換アルゴリズムのバリエーションを作成しようと試みていた。開発には約6週間かかり、5月末までにはいくつかの最適なフィルタの設計に成功した。

アルゴリズム

パークス・マクレランアルゴリズムは次の手順で実装される。[1]

  1. 初期化: 極値周波数セット{ω i (0) }を選択します。
  2. 有限集合近似: 現在の極値集合における最良のチェビシェフ近似を計算し、現在の極値集合における最小最大誤差の値 δ (m)を算出します。
  3. 補間： （2）を使用して、周波数Ωの全セットにわたって誤差関数E（ω）を計算します。
  4. Ω集合上で| E (m) (ω) |の局所的最大値を探します。
  5. max (ω∈Ω) | E (m) (ω) | > δ (m)の場合、 | E (m) (ω) | が極大値をとる新たな周波数を選び、極値集合を { ω i (m+1) } に更新する。(4) および (5) で示したように、順序付けられた周波数集合上で誤差が交互に現れることを確認する。ステップ 2 に戻り、これを繰り返す。
  6. max (ω∈Ω) | E (m) (ω) | ≤ δ (m)の場合、アルゴリズムは完了です。集合 {ω i (0) } と補間式を用いて逆離散フーリエ変換を計算し、フィルタ係数を求めます。

パークス・マクレランアルゴリズムは、以下の手順で言い換えることができる。[2]

  1. L+2 極値周波数の初期推測を行います。
  2. 与えられた式を使用して δ を計算します。
  3. ラグランジュ補間を使用して、通過帯域と阻止帯域にわたるA(ω)の密なサンプル集合を計算します。
  4. 新しい L+2 最大極値を決定します。
  5. 交替定理が満たされない場合は、（2）に戻り、交替定理が満たされるまで繰り返します。
  6. 交替定理が満たされる場合は、h(n) を計算して完了です。

前述のパークス・マクレランアルゴリズムの基本を理解するために、上記のアルゴリズムをより単純な形で書き直すことができます。

  1. 極値の位置は通過帯域と阻止帯域内で均等に間隔が空いていると推測します。
  2. 多項式補間を実行し、局所的極値の位置を再推定します。
  3. 極値を新しい位置に移動し、極値の移動が止まるまで繰り返します。

説明

右上の図は、図示されたプロットにおける様々な極値周波数を示しています。極値周波数は、阻止帯域と通過帯域における最大値と最小値です。阻止帯域リップルはプロットの右下にあるリップルの下部、通過帯域リップルはプロットの左上にあるリップルの上部です。プロットを横切る破線は、δ、つまり最大誤差を示しています。極値周波数の位置が分かれば、最適なδ、つまり最適な誤差を求める式があります。最初の試行では最適なδ、つまり極値の正確な位置が分からないため、反復処理を行います。実際には、最初に極値の位置を仮定し、δを計算します。次に、極値を再推定して移動させ、δ、つまり誤差を再計算します。このプロセスを、δが変化しなくなるまで繰り返します。このアルゴリズムにより、δ誤差は通常10～12回の反復処理で収束します。[3]

追加メモ

チェビシェフ近似を適用する前に、一連の手順が必要でした。

  1. 近似のための基底関数の集合を定義し、
  2. バンドパスフィルタの通過帯域と阻止帯域は常に遷移領域によって分離されるという事実を利用します。[1]

FIRフィルタはコサインの和に簡約できるため、同じコアプログラムを使用して、あらゆる線形位相FIRフィルタを実行できます。最大リップル法とは異なり、バンドエッジを事前に指定できるようになりました。

Parks-McClellan アルゴリズムを使用して最適なフィルタ設計を効率的に実装するには、次の 2 つの困難を克服する必要があります。

  1. 柔軟な交換戦略の定義、
  2. 堅牢な補間法の実装。[1]

ある意味、このプログラミングには、FIRフィルタ設計に用いる既知のアルゴリズムの実装と適応が含まれていました。プログラムの効率を高めるために、以下の2つの交換戦略が採用されました。

  1. 通過帯域と阻止帯域の間の極値周波数を割り当て、
  2. プログラムが反復されるにつれてバンド間の極値の移動を可能にする。[1]

初期化時に、通過帯域と阻止帯域の極値数は、帯域の大きさの比を用いて割り当てることができました。さらに、通過帯域と阻止帯域のエッジは常に極値セットに配置され、プログラムのロジックによってそれらのエッジ周波数は極値セット内に保持されました。帯域間の移動は、すべての候補極値周波数における誤差の大きさを比較し、最大値を取ることで制御されました。アルゴリズムの2つ目の要素は、誤差関数を評価するために必要な補間ステップです。彼らは、非常に堅牢な重心型ラグランジュ補間と呼ばれる手法を使用しました。

パークス・マクレランアルゴリズムのすべての条件は、チェビシェフの交代定理に基づいています。交代定理によれば、最大誤差を最小化するL次多項式は少なくともL+2個の極値を持ちます。最適な周波数応答は、最大リップル境界にほとんど到達しません。[3]極値は、通過帯域と阻止帯域のエッジ、およびω=0またはω=πのいずれか、あるいはその両方で発生する必要があります。L次多項式の導関数はL−1次多項式であり、最大L−1個の場所でゼロになることができます。[3]したがって、局所的極値の最大数は、L−1個の局所的極値と4つの帯域エッジの合計で、極値の総数はL+3個になります。

参考文献

  1. ^ abcdefghijklm McClellan, JH; Parks, TW (2005). 「Parks-Mc Clellanアルゴリズムの個人的な歴史」. IEEE Signal Processing Magazine . 22 (2): 82– 86. Bibcode :2005ISPM...22...82M. doi :10.1109/MSP.2005.1406492. S2CID  15400093.
  2. ^ Jones, Douglas (2007), Parks–McClellan FIR Filter Design , 2009年3月29日閲覧
  3. ^ abc Lovell, Brian (2003), Parks–McClellan Method (PDF) , 2009年3月30日閲覧

追加参考文献

以下の追加リンクでは、Parks–McClellan アルゴリズムに関する情報や、James McClellan と Thomas Parks が執筆したその他の研究および論文に関する情報が提供されています。

  1. 線形位相を持つ非再帰型デジタルフィルタのチェビシェフ近似
  2. MATLABを使用したParks-McClellan FIRローパスフィルタの設計に関する簡単なヘルプ
  3. DSP入門 2014年4月23日アーカイブWayback Machine
  4. MathWorks MATLABドキュメント
  5. ELEC4600 講義ノート（オリジナルリンク、2012年4月15日アーカイブ）
  6. Cコード実装（LGPLライセンス） – ジェイク・ジャノベッツ著
  7. Iowa Hills Software。「Cコードの例」。2021年5月11日にWayback Machineにアーカイブされました
  8. 改訂および拡張されたアルゴリズム McClellan、Parks、Rabiner、1975 年; Fortran コード。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Parks–McClellan_filter_design_algorithm&oldid=1331288079"