リチャードハミング：第14章デジタルフィルター-1

「このコースの目標は、技術的な未来に向けて準備することです。」

こんにちは、Habr。 「You and Your Work」という素晴らしい記事（+219、2372のブックマーク、375kの読み取り）を覚えていますか？



そのため、ハミング（はい、はい、自己チェックと自己修正のハミングコード ）には、彼の講義に基づいて書かれた本があります。 男性がビジネスを話しているので、私たちはそれを翻訳します。



この本はITだけでなく、信じられないほどクールな人の思考スタイルに関する本です。 「これは単なる肯定的な思考の責任ではありません。 素晴らしい仕事をする可能性を高める条件を説明しています。」



すでに16（30のうち）の章を翻訳しています。

第14章デジタルフィルター-1

（翻訳のおかげで、Maxim LavrinenkoとAndrey Pakhomov、「前の章」で私の電話に答えてくれました。）翻訳を手伝いたい人-PMで書くかmagisterludi2016@yandex.ruにメールしてください



コンピューターを研究し、情報がどのように表示されるかを理解したので、コンピューターが情報を処理する方法を見てみましょう。 もちろん、それらのアプリケーションのいくつかの方法のみを学習できるため、基本原則に焦点を当てます。



コンピューターが処理するもののほとんどは、さまざまなソースからの信号であり、離散化システムから取得した数値のストリームの形式であることが多い理由については既に説明しました。 この本の枠組みの中で十分な時間がある唯一の線形処理は、デジタルフィルターの存在を意味します。 現実の生活ですべてがどのように起こるかを示すために、最初に私が彼らとどのように仕事を始めたのか、次に私がやったことについてお話します。



第一に、私は副社長W. O. Bakerのオフィスに行ったことがない。 私たちは廊下でのみ会い、通常は話をするためにほんの数分間立ち止まりました。 1973年から1974年頃、廊下で出会ったとき、1946年にベル電話研究所に到着したとき、会社がリレーから電子中央制御に徐々に移行し、多くの従業員がオシロスコープやその他の最新の電子技術に切り替えることができなかったため、他のユニットに移されました。 彼にとっては、彼らは深刻な経済的損失に過ぎませんでしたが、私にとっては社会的損失でもありました。 さらに、古いアナログコンピューター（ベル電話研究所には多くの専門家がいたため、第二次世界大戦中にほとんどの技術を開発したため）からより現代のデジタルコンピューターに切り替えたときに同様の状況を観察したと述べました-再び多くのエンジニアを失い、再び彼らは経済的および社会的損失でした。



それから、私たちは、会社が最短時間でデジタル信号伝送に切り替えることを知っていることに気付きました。その結果、不満を持つエンジニアがさらに増えます。 したがって、私は今、状況を改善するために何かをしなければならないという結論に達しました。たとえば、初等の教科書やその他のトレーニング資料を入手して、従業員の適応を促進し、失くすことを減らします。 彼は私をまっすぐに見て、「はい、ハミング、あなたはそれをしなければなりません。」と言いました。 そして去った！ さらに、彼はジョン・テューキーを通して私を励まし続けました。ジョン・テューキーはよく話しましたが、彼は私の努力を追っていることを知っていました。



どうする 最初は、デジタルフィルターについてはほとんど知らないと思っていましたが、実際、彼らは興味を持ちませんでした。 しかし、あなたの副社長とあなた自身の観察の信頼性を無視するのは賢明ですか？ いや！ 社会的損失の可能性が大きすぎて、私はそれらを重要視できませんでした。



そのため、当時のデジタルフィルターの分野の世界的専門家の1人である友人のジムカイザーに目を向け、現在の研究を中断し、電子フィルターに関する本を書くという提案をしました。これは、すべての科学者の発展における自然な段階であると主張しています。 いくつかの圧力の後、彼は本を書くことに同意し、私は救われたと思いました。 しかし、彼が何をしていたかを観察すると、彼は何も書いていないことがわかりました。



私の計画を保存するために、私は彼に次の提案をしました：彼が私にレストランで朝食を教えて（ダイニングルームよりも考える時間があります）一緒に本を書くのを助けるなら（少なくとも最初の部分）、私たちはリリースしますKaiserとHammingによって作成されています。 彼は同意した！



しばらくして、私は彼から多くの知識を借り、本の最初の部分は準備ができていましたが、彼はまだ何も書いていませんでした。 したがって、私はかつて言った：「あなたが何も書かないなら、本の著者は最終的にハミングとカイザーとして示されるでしょう。」 そして彼は同意した。 その結果、私が本を書き終えたとき、彼は何も書いたことはなかったので、序文で彼に感謝することができると言ったが、著者はハミングだけを示すだろう、と彼は同意した-そしてそれにもかかわらず、私たちは今日まで良い友達！ そこで、私が書いたデジタルフィルターに関する本があり、最終的には3つのエディションを経ました。



また、この本のおかげで、私は多くの興味深い場所を訪れました。何年もの間、週に1度の短いコースを実施しました。 フィードバックが必要なため、本の執筆中に短いコースを開始し、カリフォルニア大学ロサンゼルス校（UCLA）のエクステンション部門にトレーニングコースを依頼し、彼らは同意しました。 これにより、UCLAで何年も教鞭を執り、イギリス、パリ、ロンドン、ケンブリッジ、そして米国の他の多くの場所で、そしてカナダで少なくとも2回教えました。 私はそれをやりたくはありませんでしたが、やらなければならないことをすることは最終的に報われました。



それでは、より重要な部分-新しいテーマの研究を始めた方法-デジタルフィルターに移りましょう。 新しいテーマを研究することは、リーダーになりたい、最新の開発に遅れをとらないために、キャリアの中で何度もしなければならないことです。 すぐに、大学で勉強していたフーリエ級数がデジタルフィルターの理論を支配していることが明らかになりました。 さらに、プリンストン教授であり、天才であり、ベルテレフォンラボラトリーズで週に1日か2日働いていたジョン・テューキーのために信号処理を行ったおかげで、多くの追加知識が得られました。 ほぼ10年間、ほとんどの場合、私は彼のコンピューターでした。



数学者として、私は皆さんと同じように、関数の完全なシステムは、他のすべての関数のシステムと同様に、一連の任意の関数を拡張するのにちょうどよいことを知っていました。 では、なぜフーリエ級数がそれほど違うのでしょうか？ さまざまな電気技師に尋ねましたが、満足のいく答えが得られませんでした。 エンジニアの一人は、交流は正弦波であると言ったので、正弦波を使用しましたが、私には意味がないと答えました。 ここでは、学校を卒業した後、典型的な電気技師の通常の教育を受けています！



したがって、エラー検出機能を備えたコンピューターを使用する際に既に行っていたように、基本的な原則について考える必要がありました。 本当に何が起こっているのですか？ 私たちが望むのは信号の時間不変表現であることを知っている人が多いと思います。通常、信号の始まりを確立する方法はないからです。 したがって、物事を表現するための手段として、フーリエ級数とフーリエ積分の両方の形式の三角関数（適切な伝達関数）になります。



第二に、この段階で私たちが興味を持っている線形システムは同じ固有関数を持っています-実際の三角関数と同等の複素指数関数です。 したがって、簡単なルール：時不変システムまたは線形システムのいずれかがある場合、複素指数を使用する必要があります。



さらにトピックを掘り下げて、デジタルフィルターの分野でそれらを使用する3番目の理由を見つけました。 「ナイキスト離散化定理」と呼ばれることの多い定理があります（ナイキストの定理を知っていても、ほとんど理解できない形式でウィッタカーによって公開されたと信じられていました）。周波数が制限されたスペクトルの信号があり、信号スペクトルの最大周波数の少なくとも2倍の周波数で定期的にサンプルを取得する場合、元の信号は受信サンプルから損失なく復元できます。 したがって、量子化レベルが実数の行全体をカバーしていれば、連続信号を等間隔のレポートに置き換えても、離散化プロセスで情報が失われることはありません。 サンプリングレートは、「ナイキスト周波数」と呼ばれることもよくあります。これは、ハリーナイキストを称えるもので、サーボの安定性などに貢献していることでも知られています。 無制限のスペクトル幅で関数をサンプリングすると、高い周波数は低い周波数を「オーバーラップ」します。 この用語は、1つの高い周波数がナイキスト範囲の低い周波数として後で現れる場合の現象を記述するためにTukeyによって導入されました。



度tなど、他の関数セットについても同じことが言えません。 均一なサンプリング時間とその後の信号の再構成により、1つの高次tは低次tの多項式（複数のメンバーで構成される）になります。

したがって、フーリエ関数を使用する3つの理由があります。（1）時間不変性、（2）線形性、（3）離散表現から元の関数を復元するのは簡単で簡単です。



したがって、フーリエ関数の観点から信号を分析し、周波数を表すために実際の三角関数ではなく複雑な指数関数を通常使用する理由を電気技術者と議論する必要はありません。 線形操作があり、フィルターに信号（数値のストリーム）を入れると、数値の別のストリームが出力されます。 当然、線形代数のコースからではなく、微分方程式のコースなどの他の主題からの場合、スケールを除いて、変化せずに関数が出入りする問題が発生しますか？ 上記のように、彼らは複雑な出展者です。 これらは、時間的に一様な離散化を伴う線形で時間不変の離散システムの固有関数です。



そして、これが、有名な伝達関数が対応する固有関数の固有値である方法です！ さまざまな電気技術者に伝達関数について尋ねたところ、誰もそれについて教えてくれませんでした！ はい、彼らは同じことだと言われたとき、彼らは同意しなければなりませんでしたが、彼ら自身、それについては考えなかったようです！ 彼らは同じ考えを心に持っていましたが、2つ以上の異なるイメージで、それらの間の接続を疑うことさえしませんでした！ 常に基本原則から始めましょう！



それでは、「シグナルとは何ですか？」 自然界には、連続的な信号が多数あり、定期的にサンプリングしてさらにデジタル化（量子化）します。 通常、信号は時間の関数ですが、たとえば同じピッチの電圧変化を使用して対応する応答をキャプチャする実験室での実験もデジタル信号です。 したがって、デジタル信号は、一定の間隔で取得される一連の測定値であり、数字の形式で表示されます。 そして、デジタルフィルターの出力で、互いに等間隔の別の数値セットを取得します。 不等間隔のデータの処理は許可されますが、ここではそれらについては検討しません。



信号をいくつかの出力レベルの1つに量子化すると、多くの場合、驚くほど小さな効果があります。 2、4、8、またはそれ以上のレベルに量子化された画像を見たことがあり、通常2レベルの画像でさえ認識できます。 時々非常に重要ですが、通常はほとんど効果がないため、ここでは量子化を検討しません。



時間的に均一なサンプリングの結果はオーバーラップします。ナイキスト周波数（サイクル内に2つのサンプルがある）よりも高い周波数は、低い周波数で重畳されます。 これは、三角関数のアイデンティティの単純な結果です。







ここで、aは整数の回転数kを削除した後の正の剰余です（結果を議論するときは常に回転を使用し、10進数や基本自然対数を使用するのと同じように計算でラジアンを使用します）、nはステップ数です。 > 1/2の場合、次のように記述できます。







したがって、スーパーインポーズ範囲は、1/2ターン未満、プラスまたはマイナスになります。 2つの実三角関数sinとcosを使用すると、周波数ごとに固有関数のペアが取得され、回転範囲は0から1/2回転になります。複素指数表記を使用すると、周波数ごとに1つの固有関数が取得されますが、これで、範囲は-1/2〜1/2の速度になります。 このような複数の固有値の防止は、実際の正弦関数や余弦関数よりも複雑な周波数の処理がはるかに簡単な理由の1つです。 オーバーラップが発生しない最大サンプリング周波数は、サイクル内の2つのサンプルです。この周波数はナイキスト周波数と呼ばれます。 元の信号は、重畳周波数の範囲のカウントから復元できません。非重畳周波数の間隔（-1/2〜½）に含まれる周波数のみを一意に決定できます。 さまざまな重畳周波数からの信号は、範囲内の1つの周波数に移動し、代数的に追加されます。 これは、サンプリングの結果として得られるものです。 したがって、重ね合わせ中に特定の周波数の増幅または抑制が発生する可能性があり、重ね合わせた信号から元の信号を取得することはできません。 最大サンプリング周波数では、1の結果を言うことはできません。これは、課されていない周波数が範囲内にある必要があるためです。



時間をストレッチ（圧縮）して、サンプリングレートを単位時間あたり1サンプルとして測定できるようにします。これにより、すべてが大幅に簡素化され、ミリ秒およびマイクロ秒からサンプル間で数日または数年かかることがある間隔にデータを分散できるためです。 標準的な番号体系と、ある領域から別の領域への思考の構造を採用することは常に賢明です。アプリケーションの領域によっては、別の領域で問題の解決策を見つけることができます。 可能な限りそうすることは非常に理にかなっていると確信しました-スケールの無関係な要素を取り除き、元の表現に移ります。 （しかし、最初は数学を勉強しました）



重複は基本的な離散化効果であり、信号処理とは関係ありません。 サンプルが取得されるとすぐに、すべての周波数がナイキスト範囲にあると考えるのが便利でした。したがって、信号に他の周波数がもはや存在しないため、何かの周期的な継続を描画する必要はありません-サンプリング後、高周波数はより低い範囲に移動しますそして存在しなくなります。 なんて間違ったんだ！ サンプリングの行為は、私たちが作業しなければならない重畳信号を生成します。



次に、離散化とオーバーレイのアイデアのみを使用する3つのストーリーに移ります。 最初の話では、28の常微分方程式のシステムの数値解を計算しようとしましたが、使用するサンプリング周波数を知る必要がありました（解のステップサイズは使用するサンプリング周波数です）。予想よりも、計算カウンターは約2倍大きくなります。 最も一般的で実用的な数値解法では、数学的理論により5次導関数のステップサイズが計算されます。 誰がこれを知ることができますか？ 誰も。 しかし、離散化内のステップを考慮すると、負から正の無限大までのデータがある場合、オーバーレイは最高周波数の2つのサンプルから始まります。 最大5つのデータポイントの短い範囲しかない場合、約2倍、つまりサイクルあたり4カウントが必要になることを直感的に理解しました。 そして最後に、片側にのみデータがある場合、別の倍増要因が考えられます。 サイクルあたり8カウントのみ。



その後、2つのことを行いました。（1）理論を開発し、（2）単純な微分方程式の数値テストを実施しました







両方とも、サイクルごとに7カウントで、（ステップごとに）おおよその精度が得られ、10-絶対で得られることが示されました。 だから私はすべてをそのまま説明し、予想されるソリューションで最高の周波数を要求しました。 私のリクエストの妥当性は高く評価され、数日後、1秒あたり最大10サイクルまでの周波数について心配する必要があると言われましたが、上記は私の心配ではありません。 そしてそれは正しかった、そして答えは満足だった。 アクションの離散化定理！



2番目の話は、西海岸のある下請業者がナイキロケットの打ち上げをシミュレートするのに問題があり、1/1000から1/10 000秒までのサンプルの間隔を使用したことを偶然Bell Telephone Laboratoriesで話した話に触れています。 私はすぐに笑い、彼らが使用したモデルでは70から100個のサンプルで十分だから、それはある種の間違いでなければならないと言った。 バイナリ番号が7桁左にシフトし、128倍大きいことが判明しました。 離散化定理を使用して、大陸の反対側で大規模なプログラムをデバッグします！



3番目のストーリーは、海軍大学院のグループが、非常に高い周波数の信号の周波数を下げて、サンプリング定理に従ってサンプリングできるようにする方法についてです。しかし、高周波数をインテリジェントにサンプリングすると、サンプリング自体が信号の周波数を下げることに気付きました（元の信号をスペクトルの下部に重ね合わせます）。数日間の論争の後、彼らはまだ周波数を下げるために機器を備えたラックを取り外し、その後、機器の残りの部分はより良く機能し始めました！そして今回は、サンプリング中の重ね合わせの影響をしっかりと理解するだけでした。これは、基本原則をよく知る必要があるもう1つの例です。残りを簡単に考えて、誰もあなたに言ったことがないことをすることができます。







図14.I



離散化は、デジタルコンピューターで作業しながらデータを処理するときに使用する基本的なアプローチです。信号とは何か、信号に対して離散化が行うことは理解できたので、信号処理のより詳細な検討に安全に進むことができます。



まず、非再帰フィルターについて説明します。その目的は、一部の周波数を通過させ、他の周波数を抑制することです。ある音声メッセージのすべての周波数を別の音声メッセージの周波数範囲外に上げる（信号を変調する）場合、これら2つの信号を同時に追加して送信できるという考えがあったときに、電話会社でも同様の問題が初めて発生しました。ワイヤを使用し、反対側でフィルタリングして分離した後、高信号の周波数を通常の周波数範囲に転送します（復調）。このような周波数シフトは、単に正弦関数と、次の三角関数のアイデンティティから生じる2つの周波数のいずれかを選択すること（シングルバンド変調）による乗算です（今回は実関数を使用します）





信号の周波数（変調）を変更することについて不思議なことはありませんが、それは三角関数の1つにすぎません。



最初に検討する非再帰フィルターは、主に平滑化フィルターで、入力値はu（t）= u（n）= u _nで、出力はy _n





でC _j = C _-j（係数は中心に対して対称です） C _0の値）。



最小二乗法は、これから行うことで基本的な役割を果たすため、最小二乗法を思い出す必要があります。このため、フィルターの作成方法を示す平滑化フィルターを開発します。 「ノイズ」が追加された信号があり、それを滑らかにしてノイズを除去する必要があるとします。最小二乗法で直線の連続した5つの値を近似し、この線の平均値をこの時点で「関数の平滑化された値」として取るのは合理的だと思います。



数学的な便宜のために、t = -2、-1,0,1,2 で5点を選択し、

直線を描きます（図）。 14.I.







最小二乗法では、データと線上の点との差の二乗の合計を最小化する必要があります。つまり、最小化







最小値を見つけるために、微分にはどのパラメーターを使用する必要がありますか？これらは、t（現在の離散変数k）とuではなく、aとbです。行はパラメーターaとbに依存し、これは多くの場合

、生徒にとって障害となります。方程式のパラメーターは最小化する変数です！したがって、aとbに関して微分し、最小値を得るために導関数をゼロに等化する場合、次のようになります







。この場合、a-中間点での線の値のみが必要です。したがって、







上式から







これは、隣接する5つの値の平均です。見つかったaの平滑化された値を計算する方法を考えるとき、垂直列のデータについて考えます。図。 14.II、係数1/5で移動加重値として取得。データを表示するウィンドウを想像できます。ウィンドウの「形状」はフィルター係数です。考慮される平滑化のケースは均一です。



2k + 1個の対称的に配置されたポイントを使用した場合、データポイントの平均は、ノイズを除去する平滑化された値として取得されます。



関数を直線ではなく放物線で近似することにより平滑化したと仮定します。 14.III：







正方形の差を確立し、a、b、およびcに関して今回を微分すると、次のようになります。







繰り返しますが、aだけが必要です。 1番目と3番目の方程式を書き換え（平均にはaは含まれません）、上記で計算した合計を代入







すると、変数cを除外するために、不要な上限の方程式に17を、下限の方程式に-5を掛けて、







今回は「 「平滑化ウィンドウ」には同じ係数がありません。さらに、それらのいくつかは負です。窓について比meta的に話しているので、これについて心配する必要はありません。したがって、否定的な伝達が可能です。





図14.II







図14.III



これらの最小二乗平滑化式を正しい位置にシフトして、ポイントnで値を取得すると、次のようになります。











ここで、入力に純粋な固有関数を配置するとどうなるかを自問します。方程式は線形であるため、固有関数を返す必要がありますが、固有関数の周波数に対応する固有値（その周波数での伝達関数の値）を乗算する必要があります。 2つの式の上部を使用して、





基本三角法を適用し、周波数ωで固有値を取得します（伝達関数）。







放物線平滑化の場合







、次のようになります。 14.IV.



平滑化式は係数に関して中心対称性を持ち、微分式は奇数対称性を持ちます。明白な式から







式は奇数関数と偶数関数の合計であるため、非再帰デジタルフィルターは平滑化フィルターと微分フィルターの合計です。これら2つの特殊なケースを扱ったとき、一般的なケースがありました。



平滑化の式では、固有値曲線（伝達関数）は余弦のフーリエ展開であり、微分の式では正弦の展開であることがわかります。したがって、望ましい離散伝達特性を取得する問題は、フーリエ級数の連続表現を拡張する問題に帰着するという結論に達しました。



次に、フーリエ級数を簡単に再定式化します。任意の関数f（t）が次のように表されると仮定します。





直交性の条件を使用する（基本的な三角法と単純な積分を使用して見つけることができます）：





私たちは得る





また、最初の係数として_0/2を使用したため、k = 0の場合にもa _kの同じ式が有効です。複素指数の形式では、これはもちろん非常に単純に見えます。



次に、直交関数セットの展開近似が最小二乗法に対応することを証明する必要があります。重み関数w（t）≥0で、直交関数のセットを{fk（t）}として与えます。直交性とは、











図14.IVを意味します。



上記のように、通常の分解では係数が得られます。







どこで





関数が実数の場合、複雑な関数の場合、複素共役関数を掛けます。



ここで、最小二乗法の観点から係数C _k（資本C）を使用した直交関数の完全なセットによる近似を検討します。我々は持っている







最小化します。 C _mに関して微分し





、Ck = ckであることがわかる順列から取得します。したがって、関数の直交セットによる近似も最小二乗近似です。



不等式によって得られた不等式を観察し続けると、一般的な場合、ベッセル不等式が得られます





行の展開に使用される係数の数。この不等式により、有限級数の展開を近似するのに十分なメンバーを取得したかどうかを判断できます。実際には、フーリエ級数のいくつの用語を使用すべきかの優れたガイドとしての地位を確立しています。



継続するには...



誰が翻訳を手伝いたいのか-個人のメールまたはメールに記入してくださいmagisterludi2016@yandex.ru



ちなみに、私たちはまた別のクールな本の翻訳を開始しました- 「The Dream Machine：The History of the Computer Revolution」）