(57)【要約】  最初および最後のプロセッサを含む、プロセッサのアレイを利用して、フィルタ関数によるデータ関数の畳み込みを計算するシステム。フィルタ関数の微分（derivation）に基づく係数値と、データ関数を表すデータ値とが掛け合わされて、現在の中間値が生成される。最初のプロセッサ以外のプロセッサにおいて、前の中間値が現在の中間値に加算される。最後のプロセッサ以外のプロセッサにおいて、データ値および現在の中間値が次のプロセッサに送られる。次に、最後のプロセッサの、前の中間値（あれば）が、最後のプロセッサの現在の中間値に加算されて、フィルタ関数によるデータ関数の畳み込みを集合的に表す結果値が生成される。
2010524080.tif 000002
【特許請求の範囲】
【請求項１】
フィルタ関数によるデータ関数の畳み込みを計算するシステムであって、
最初および最後のプロセッサを含む複数のプロセッサからなるアレイを備え、
前記プロセッサは、
前記フィルタ関数の微分に基づく係数値と、前記データ関数を表すデータ値とを掛け合わせて、現在の中間値を生成するロジックと、
前記最初のプロセッサ以外の前記プロセッサにおいて、前記プロセッサのうちの別のプロセッサで以前に実行された計算を表す前の中間値を受け取り、前記前の中間値を前記現在の中間値に加算するロジックと、
前記最後のプロセッサ以外の前記プロセッサにおいて、前記データ値および前記現在の中間値を別の前記プロセッサに送るロジックと、
前記最後のプロセッサからの、前の中間値（あれば）を、前の部分値として保持し、前記前の部分値を、前記最後のプロセッサからの前記現在の中間値に加算して、結果値を生成するロジックと、
を含み、
複数のプロセッサからなる前記アレイは、一連の前記データ値を受け取って、前記フィルタ関数による前記データ関数の畳み込みを集合的に表す一連の前記結果値を生成する
ことを特徴とするシステム。
【請求項２】
複数の前記プロセッサは、処理を並列に実行することを特徴とする請求項１に記載のシステム。
【請求項３】
複数の前記プロセッサは、処理を非同期で実行することを特徴とする請求項１に記載のシステム。
【請求項４】
複数の前記プロセッサは、非同期で互いに通信し合うことを特徴とする請求項１に記載のシステム。
【請求項５】
複数の前記プロセッサは、単一の半導体ダイを占有することを特徴とする請求項１に記載のシステム。
【請求項６】
複数のプロセッサからなる前記アレイのすべてが、前記半導体ダイを占有することを特徴とする請求項５に記載のシステム。
【請求項７】
複数の前記プロセッサはそれぞれ、前記係数値を保持するためにフィルタ記憶素子をさらに含むことを特徴とする請求項１に記載のシステム。
【請求項８】
前記システムの外部から、前記最初のプロセッサに前記データ値を受け取るロジックをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項９】
前記最後のプロセッサから、前記システムの外部へ前記結果値を送るロジックをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項１０】
前記前の中間値を保持する前記ロジックは、前記最後のプロセッサにあることを特徴とする請求項１に記載のシステム。
【請求項１１】
フィルタ関数によるデータ関数の畳み込みの結果値を計算する方法であって、
（ａ）前記フィルタ関数の微分に基づく、係数値のシーケンスを取得すること、
（ｂ）前記データ関数を表すデータ値に対して、
（ｉ）前記各係数値について、最初および最後のプロセッサを含むコンピュータ制御のプロセッサからなるパイプ・ラインにおいて、
（Ａ）前記係数値と前記データ値とを掛け合わせて現在の中間値を生成すること、
（Ｂ）前記最初のプロセッサ以外の前記プロセッサにおいて、前記プロセッサのうちの別のプロセッサで以前に実行された計算を表す前の中間値を、前記現在の中間値に加算すること、および
（Ｃ）前記最後のプロセッサ以外の前記プロセッサにおいて、前記データ値および前記現在の中間値を後続の前記プロセッサに送ること、
（ｉｉ）前記最後のプロセッサからの、前の中間値である前の部分値（あれば）を、前記最後のプロセッサからの前記現在の中間値に加算して、結果値を生成すること、ならびに
（ｉｉｉ）前記結果値を、前記方法を採用するデジタル信号プロセッサに出力すること
を含むことを特徴とする方法。
【請求項１２】
フィルタ関数によるデータ関数の畳み込みを計算する方法であって、
（ａ）前記フィルタ関数の微分に基づく係数値のシーケンスを取得すること、
（ｂ）前記データ関数を表すデータ値のシーケンスを取得すること、
（ｃ）前記各データ値に対して、
（ｉ）前記各係数値について、最初および最後のプロセッサを含む複数のコンピュータ制御のプロセッサからなるパイプ・ラインにおいて、
（Ａ）前記係数値と前記データ値とを掛け合わせて現在の中間値を生成すること、
（Ｂ）前記最初のプロセッサ以外の前記プロセッサにおいて、前記プロセッサのうちの別のプロセッサで前に実行された計算を表す前の中間値を、前記現在の中間値に加算すること、および
（Ｃ）前記最後のプロセッサ以外の前記プロセッサにおいて、前記データ値および前記現在の中間値を後続の前記プロセッサに送ること、
（ｉｉ）前記最後のプロセッサからの、前の中間値である前の部分値（あれば）を、前記最後のプロセッサからの前記現在の中間値に加算して、結果値を生成すること、
（ｄ）前記（ｃ）の前記結果値を、前記畳み込みとして累積すること、ならびに
（ｅ）前記畳み込みを、前記方法を採用するデジタル信号プロセッサに出力すること
を含むことを特徴とする方法。
【請求項１３】
前記（ｃ）（ｉ）（Ａ）は、複数の前記プロセッサにおいて、複数の前記データ値に対して同時に実行されることを特徴とする請求項１２に記載の方法。
【請求項１４】
前記（ｃ）（ｉ）（Ａ）は、複数の前記プロセッサにおいて、係数値の前記シーケンスに対して同時に実行されることを特徴とする請求項１２に記載の方法。
【請求項１５】
少なくとも１つのプロセッサが、フィルタ関数を表す係数値と、データ関数を表すデータ値とを掛け合わせるような形式の畳み込みを計算する改良システムであって、
前記改良は、前記フィルタ関数の微分に基づく前記係数値を含むことを特徴とする改良システム。
【請求項１６】
前記改良は、複数の前記係数値と複数の前記データ値とを並列に掛け合わせる複数の前記プロセッサをさらに含むことを特徴とする請求項１５に記載の改良システム。
【請求項１７】
フィルタ関数を表す係数値とデータ関数を表すデータ値とを掛け合わせて、畳み込みを集合的に表す結果値を生成するような形式のコンピュータ制御プロセッサにおける畳み込みを計算するための改良方法であって、
前記改良は、前記フィルタ関数の微分に基づく前記係数値を用いることを含む
ことを特徴とする改良方法。
【請求項１８】
前記改良は、複数の前記プロセッサにおいて、複数の前記データ値に対して前記掛け合わせを同時に実行することをさらに含むことを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、算術処理および算術計算のための電気的コンピュータに関し、特に、デジタル形式で重畳積分が求められるような電気的コンピュータに関する。
【背景技術】
【０００２】
既存のシステムや新たに出現しつつあるシステムの多くは、基礎をなすシステムを記述する数学に基づいて適切にプログラムされた現代的なデジタル・プロセッサを用いて解析することが可能である。たとえば、そのような解析は、今日では、電気回路、光学素子、機械的機構、および他の多くのシステムなどの、線形時不変システム（linear time-invariant systems）を解析することに関して、ますます有用になりつつある。
【０００３】
数学、および数学を広範に使用する今日の科学および工学の多くの部門などの、多くの分野において、「変換（する）（transform）」という用語は、方程式解析手法のクラスについて述べる場合に使用される。この変換の概念は、数学の関数解析学（functional analysis branch of mathematics）の分野までさかのぼる。関数解析学は、本来、特定の関数が別の関数を引数として有する関数空間の研究を扱う。したがって、変換は、個々の方程式で、または複数の方程式の全セットで使用することができ、その変換方法（process of transformation）は、あるドメインで表される元の方程式または方程式群から、異なるドメインで表される別の方程式または方程式群への１対１のマッピングである。
【０００４】
変換を実行するための動機付けは、多くの場合、単純明快である。元の表現では解くのが困難だが、他の１つまたは複数の表現ではより容易に解くことが可能な、多くの方程式が存在する。このため、変換が実行されて、解を求め、つぎに逆変換を実行して、その解を元のドメインにマッピングすることが可能である。積分変換の一般形式は、次式で定義される。
【０００５】
【数１】
2010524080.tif 000003
【０００６】
ここで、Ｋ（α，ｔ）は、変換の「積分核（integral kernel）」と呼ばれることが多い。
【０００７】
ラプラス変換は、式（１）で定義される変換のクラスのサブセットであり、特に、多くの場合に有用である。システムへの入力またはシステムからの出力についてシンプルな数学的記述または関数的記述が与えられた場合、ラプラス変換は、そのシステムの動作をシンプルに解析することが可能な代替の関数的記述を与えることが可能である。ラプラス変換の一般形式は、次式で定義される。
【０００８】
【数２】
2010524080.tif 000004
【０００９】
ここで、積分範囲および積分核は、式（１）から、ａ＝０、ｂは∞に置換され、およびＫ（α，ｔ）＝ｅ-stとして再定義されている。ｆ（ｔ）に対してラプラス変換を行うことができるのは、ｓが十分大きく、特定の条件が満たされる場合のみであるが、それらの条件は、通常、ｆ（ｔ）が、実在する、任意の有用な関数に近い関数形態をとることを可能とするのに十分に柔軟であることである。
【００１０】
特定の関数、たとえば、Ｆ（ｓ）が、単独の既知の関数の変換ではなく、それぞれが既知の関数ｆ（ｔ）またはｇ（ｔ）の変換の結果である２つの関数の積、で表されることが可能であることは、よくあることである。すなわち、
【００１１】
【数３】
2010524080.tif 000005
【００１２】
である。ここで、ｇ（ｔ）は、ｆ（ｔ）と同じ条件を満たさなければならない。この、Ｆ（ｓ）、ｆ（ｔ）、およびｇ（ｔ）のつながりから、以下の関係が成り立つ。
【００１３】
【数４】
2010524080.tif 000006
【００１４】
これは、しばしば「畳み込み（重積分）定理（convolution theorem）」と呼ばれる。
【００１５】
畳み込み定理は、変数が１つだけの積分の変換をもたらすことがわかる。したがって、この手法は、変数が１つだけの積分の数値近似に対して適用可能である。
【００１６】
積分表現（integral representation）とリーマン和表現（Riemann sum representation）との間には、以下の等式が成り立つ。
【００１７】
【数５】
2010524080.tif 000007
【００１８】
ここで、各ｃt-kおよびｃkは、ｋ番目の部分区間において任意に選択される。実際には、式（５）の等式の右辺は、微小なΔτを利用することによって、および、選択された数値的手法およびΔτの値に依存する、ある次数の誤差項が存在することを了解することによって、次式のように近似される。
【００１９】
【数６】
2010524080.tif 000008
【００２０】
ここで、ｍは、結果である和で表現されることが可能な精度の次数（かつ、さらに、期待されることが可能な有効桁数）であり、Ｏは、従来の数学のコンテキストにおけるビッグオー記法（big-O notation）である。
【００２１】
前述の内容から示されるように、畳み込み（convolution）を使用することによって恩恵が得られる変換には、重要な応用における既存の使い方および潜在的な用途がある。たとえば、１つのそのような応用は、デジタル信号処理（ＤＳＰ）において実行されるデジタル・フィルタリングに関連する畳み込みの用途である。
【００２２】
数学的関数として表すことが可能なすべてのフィルタリングは、デジタル・フィルタを用いて達成されることが可能であり、これは、現代のＤＳＰの実行のまさしくその出発点基礎の１つである。たとえば、信号からサンプリングされたデータ値に関するデジタル・フィルタリングは、信号の不要な部分を除去したり、信号の有用な部分を抽出したりすることを可能にする。有限インパルス応答（ＦＩＲ）および無限インパルス応答（ＩＩＲ）は、より一般的なものは、ＦＩＲフィルタであるけれども、今日のＤＳＰ応用で用いられるデジタル・フィルタの、２つの主なタイプである。
【００２３】
通常、ＦＩＲフィルタのほうが、内部フィードバックを必要としないために、使いやすいとされている。たとえば、内部フィードバックは、ＩＩＲフィルタに、インパルスへの応答を無限に行わせる可能性がある。名称に使われている「有限」という言葉は、ＦＩＲフィルタの別の利点も意味している。そのようなフィルタからのインパルスは、最終的にはゼロに落ち着き、行われた反復加算計算の誤差が伝搬されない。すなわち、誤差項は、計算過程全体を通して一定のままである。このことは、たとえば、それぞれの追加の反復出力加算時に誤差が潜在的に増大する可能性がある、ＩＩＲフィルタに対する明確な優位点である。
【００２４】
残念なことに、様々なアプリケーションに対して、デジタル・フィルタの重要な制限は、デジタル・フィルタの速度が、数値計算に使用されるプロセッサまたはプロセッサ群の速度によって制限されることである。たとえば、高いフィルタリング速度が必要な場合には、これは、デジタル・フィルタの実装に必要なハードウェアを高価にしたり、単純に実現不可能にしたりする可能性がある。実際上、すべてのアプリケーションにおいて、そして、一般に多くの電子式システムに当てはまることは、用いられる速度が高いほど、電磁ノイズを抑えたり、放熱させたりすることなどの、同時発生する現象に対処することもまた、より困難になる。
【発明の概要】
【発明が解決しようとする課題】
【００２５】
したがって、数値的畳み込み計算を実行するのに使用するシステムを改良することは、現在の、および新たに出現しつつある、信号処理関連タスクを、より高い速度で、より経済的に、さらに、基礎をなすシステムおよび周辺システムにおける悪影響を減らして、実行することが可能になる、ということになる。
【課題を解決するための手段】
【００２６】
したがって、本発明の目的は複数のコンピュータ・プロセッサを備える畳み込み計算用システムを提供することである。
【００２７】
簡潔に、本発明の好適な第１の実施形態は、フィルタ関数によるデータ関数の畳み込みを計算するシステムである。最初のプロセッサと最後のプロセッサとを含む、複数のプロセッサからなるアレイが提供され、各プロセッサは、フィルタ関数の微分（derivation）に基づく係数値と、データ関数を表すデータ値とを掛け合わせて、現在の中間値を生成するロジックを含む。最初のプロセッサ以外のプロセッサでは、それらのプロセッサのうちの別のプロセッサで以前に実行された計算を表す前の中間値を受け取り、その、前の中間値を、現在の中間値に加算するロジックが提供される。最後のプロセッサ以外のプロセッサでは、データ値と現在の中間値とを別のプロセッサに送るロジックが提供される。さらに、最後のプロセッサからの、前の中間値（あれば）を、以前の部分値として保持し、この、以前の部分値を、最後のプロセッサからの現在の中間値に加算して、結果値を生成するロジックが提供される。したがって、複数のプロセッサからなるアレイは、一連のデータ値を受け取って、フィルタ関数によるデータ関数の畳み込みを集合的に表す、一連の結果値を生成する。
【００２８】
簡潔に、本発明の好適な別の実施形態は、フィルタ関数によるデータ関数の畳み込みにおいて結果値を計算するための方法である。フィルタ関数の微分（derivation）に基づく、係数値のシーケンスが取得される。データ関数を表すデータ値に対しては、その係数値が、最初および最後のプロセッサを含むコンピュータ制御のプロセッサからなるパイプ・ラインにおいて用いられ、その係数値の１つとデータ値とが掛け合わされて現在の中間値が生成される。最初のプロセッサ以外においては、それらのプロセッサのうちの別のプロセッサで前に実行された計算を表す以前の中間値が、現在の中間値に加算される。最後のプロセッサ以外においては、データ値と現在の中間値とが後続のプロセッサに送られる。最後のプロセッサからの現在の中間値に、前の部分値（最後のプロセッサからの、前の中間値）（あれば）が加算されて、結果値が生成される。この結果値は、本方法を採用するデジタル信号プロセッサに出力される。
【００２９】
簡潔に、本発明の好適な別の実施形態は、フィルタ関数によるデータ関数の畳み込みを計算する方法である。フィルタ関数の微分に基づく、係数値のシーケンスが取得され、データ関数を表す、データ値のシーケンスが取得される。そのような係数値のそれぞれに関し、そのようなデータ値のそれぞれについて、最初および最後のプロセッサを含むコンピュータ制御のプロセッサからなるパイプ・ラインにおいて、係数値とデータ値とが掛け合わされて現在の中間値が生成される。最初のプロセッサ以外においては、それらのプロセッサのうちの別のプロセッサで以前に実行された計算を表す、前の中間値が、現在の中間値に加算される。最後のプロセッサ以外においては、データ値と現在の中間値とが後続のプロセッサに送られる。最後のプロセッサからの現在の中間値に、前の部分値（最後のプロセッサからの、前の中間値）（あれば）が加算されて、結果値が生成される。これらの結果値は、畳み込みとして累積され、その畳み込みが、本方法を採用するデジタル信号プロセッサに出力される。
【００３０】
簡潔に、本発明の好適な別の実施形態は、少なくとも１つのプロセッサが、フィルタ関数を表す係数値と、データ関数を表すデータ値とを掛け合わせるタイプの畳み込みを計算する、改良されたシステムである。この改良は、係数値がフィルタ関数の微分（derivation）に基づくことを含む。
【００３１】
また、簡潔に、本発明の好適な別の実施形態は、係数値がフィルタ関数を表し、データ値がデータ関数を表し、係数値とデータ値とが掛け合わされて、畳み込みを集合的に表す結果値が生成されるタイプの、コンピュータ・プロセッサにおいて畳み込みを計算する改良された方法である。この改良は、フィルタ関数の微分（derivation）に基づく係数値を用いることを含む。
【００３２】
本発明の以上およびその他の目的および利点については、当業者であれば、本明細書に記載され、図面の各図に示されている、本発明を実施するための現在知られている最良の形態、ならびに好ましい実施形態の産業上の利用可能性の説明を参照することにより、明らかになるであろう。
【図面の簡単な説明】
【００３３】
本発明の目的および利点は、添付の図面とともに以下の詳細な説明から理解できるであろう。添付図面の各図においては、類似の参照符号が、類似または同様の要素またはステップを表すために用いられている。
【図１】複数のコンピュータからなるプロセッサのアレイの形で用いられる、本発明の畳み込みシステムを示す線図である。
【図２】（背景技術）図１のプロセッサの１つ（具体的には、本明細書の多数の実施例で使用されている、ＩｎｔｅｌｌａＳｙｓ  Ｃｏｒｐｏｒａｔｉｏｎ（Ｃｕｐｅｒｔｉｎｏ，Ｃａｌｉｆｏｒｎｉａ）のＳＥＡｆｏｒｔｈ−２４Ａプロセッサ内のコア）の主な内部機能の線図である。
【図３ａ】図１のプロセッサを使用するインバウンド通信を示す、図１の一部分図であって、入力装置と第１のプロセッサとの間、および第１のプロセッサと第２のプロセッサとの間におけるデータの受け渡し方法を示す図である。
【図３ｂ】図１のプロセッサを使用するアウトバウンド通信を示す、図１の一部分図であって、最後から２番目のプロセッサと最後のプロセッサとの間、および最後のプロセッサと出力装置との間におけるデータの受け渡し方法を示す図である。
【図３ｃ】図１のプロセッサを使用する内部通信を示す、図１の一部分図であって、アレイの中心部で使用される２個の例示的プロセッサの間におけるデータの受け渡し方法を示す図である。
【図４ａ】図１に示されたようなプロセッサのアレイにおける畳み込み計算を開始可能な段階を概略的に表したブロック図である。
【図４ｂ】図１に示されたようなプロセッサのアレイにおける畳み込み計算の最初の０の段階を概略的に表したブロック図である。
【図４ｃ】図１に示されたようなプロセッサのアレイにおける畳み込み計算の次の１の段階を概略的に表したブロック図である。
【図４ｄ】図１に示されたようなプロセッサのアレイにおける畳み込み計算のｎの段階を概略的に表したブロック図である。
【図４ｅ】図１に示されたようなプロセッサのアレイにおける畳み込み計算のｎ＋１の段階を概略的に表したブロック図である。
【図４ｆ】図１に示されたようなプロセッサのアレイにおける畳み込み計算のｎ＋ｎの段階を概略的に表したブロック図である。
【図５ａ】図１に示されたようなプロセッサのアレイにおける、新しいアルゴリズムに基づく畳み込み計算を開始可能な段階を概略的に表したブロック図である。
【図５ｂ】やはり図１に示されたようなプロセッサのアレイにおける、新しいアルゴリズムに基づく畳み込み計算の最初の０の段階を概略的に表したブロック図である。
【図５ｃ】やはり図１に示されたようなプロセッサのアレイにおける、新しいアルゴリズムに基づく畳み込み計算の、次の１の段階を概略的に表したブロック図である。
【図５ｄ】やはり図１に示されたようなプロセッサのアレイにおける、新しいアルゴリズムに基づく畳み込み計算の、ｍの段階を概略的に表したブロック図である。
【図５ｅ】やはり図１に示されたようなプロセッサのアレイにおける、新しいアルゴリズムに基づく畳み込み計算の、ｍ＋１の段階を概略的に表したブロック図である。
【図５ｆ】やはり図１に示されたようなプロセッサのアレイにおける、新しいアルゴリズムに基づく畳み込み計算の、ｍ＋ｍの段階を概略的に表したブロック図である。
【図６ａ】図４ａ〜ｆおよび図５ａ〜ｆで提示されたアプローチの両方を用いて実行された畳み込みを表すグラフであって、従来型の畳み込み係数の使用を表す第１のトレースと、微分（derivation）畳み込み係数の使用を表す第２のトレースとを示す図である。
【図６ｂ】図４ａ〜ｆおよび図５ａ〜ｆで提示されたアプローチの両方を用いて実行された畳み込みを表すグラフであって、畳み込みが実行される入力データを表す第１のトレースと、微分（derivation）信号データの使用を表す第２のトレースとを示す図である。
【図６ｃ】図４ａ〜ｆおよび図５ａ〜ｆで提示されたアプローチの両方を用いて実行された畳み込みを表すグラフであって、前述のアプローチの結果を表す単一トレースを示す図である。
【図７】直接フィルタでの使用に好適なコードのリストである。
【図８ａ】微分（derivation）フィルタでの使用に好適なコードのリストであって、図７と概念的に類似する機能を実行するコードのリストである。
【図８ｂ】微分フィルタでの使用に好適なコードのリストであって、微分（derivation）ベースのアルゴリズムで使用される追加コードのリストである。
【発明を実施するための形態】
【００３４】
本発明の好ましい一実施形態は、複数のコンピュータ・プロセッサにより畳み込み計算が実行されるシステムである。本明細書の各種図面（特に図１）において示されるように、本発明の好ましい実施形態は、全体が参照符号１０で示される。
【００３５】
簡単に言えば、本発明は、改良された畳み込みシステム１０であり、これは、その解をフィルタ関数によるデータ関数の畳み込みに数値的に近似する。数値的手法を用いて畳み込み計算を実行することには、本質的に、多数の乗算および加算の演算を伴う傾向がある。本発明は、２つの特定の様式で、そのような計算の実行に必要な全体時間を大幅に減らすことを可能にする。第１に、本発明は、必要な計算の大半を、直列ではなく並列に達成することを可能にする。第２に、本発明は、より少ないデータ・ビット数で表されることが可能なフィルタ値およびデータ値を用い、新しい種類のアルゴリズムを採用することを可能にし、この結果、プロセッサの本質的な制限の点から見て、より高速に実行されることができる。
【００３６】
図１は、コンピュータ・プロセッサ１４のアレイ１２の形で用いられる、本発明の畳み込みシステム１０を示す線図である。畳み込みシステム１０自体に焦点を当てるために、アレイ１２をサポートする外部要素は省略されたり、一般的な形で示されたりしている。しかしながら、当業者であれば理解されるように、そのような要素は、実際の稼動する実施形態には存在するものであり、それらは、事実上、従来のものである。たとえば、図１は、アレイ１２の電源供給に関連する細部をすべて省略し、外部入力装置１６、入力バス１８、出力バス２０、および外部出力装置２２についての総称的形態を含んでいる。説明を簡潔にするために、一般的なコンピュータの初期化（initialization）および終了（termination）に関する事柄について最初に説明することを省略し、プログラム命令および畳み込み係数値は、プロセッサ１４に既にロードされているものとする。入力装置１６は、ここでは、畳み込みが実行される入力データ値を提供することにのみ関するものとし、出力装置２２は、ここでは、畳み込みが実行された出力データ値を受け取ることにのみ関するものとする。
【００３７】
図１はまた、入力装置１６から始まり、出力装置２２で終わるフロー経路２４を様式的に示している。しかしながら、これ以外の配置も容易に可能であることを理解されたい。たとえば、他の開始位置および終了位置が可能であり、図示されたフロー経路２４と異なる経路も可能であり（さらに代替実施形態においても同様に可能であり）、（たとえば、アレイ１２と通信する入力チャネルおよび出力チャネルを有する）単一の複合型Ｉ／Ｏ装置（図示せず）が代わりに用いられることが可能である。
【００３８】
畳み込みシステム１０用の、本願発明者が現時点で好ましいとするハードウェア・プラットフォームは、複数のプロセッサ１４ならなるアレイ１２を単一の半導体ダイ２６内に有するものであって、ＩｎｔｅｌｌａＳｙｓ  Ｃｏｒｐｏｒａｔｉｏｎ（Ｃｕｐｅｒｔｉｎｏ，Ｃａｌｉｆｏｒｎｉａ）のＳＥＡｆｏｒｔｈ−２４ＡやＳＥＡｆｏｒｔｈ−４０Ａなどのデバイスである。本明細書では、ほとんどの実施例において、ＳＥＡｆｏｒｔｈ−２４Ａを用いる（厳密には、これらの実施例におけるプロセッサ１４（複数）を「コア（複数）」または「ノード（複数）」と呼ぶことが可能である）。さらに説明を容易にするために、図示されるように、複数のプロセッサ１４からなる集合の複数のメンバは、個々にプロセッサ１４ａ〜ｘとして参照され、各プロセッサ１４は、存在している他の複数のプロセッサ１４との相互通信を可能にするバス２８を有する。
【００３９】
図１に示されている各プロセッサ１４は、自身に隣接するプロセッサ１４のすべてと自身とを相互接続するバス２８を有するが、フロー経路２４の道筋からわかるように、すべてのバス２８が必ずしも使用されるわけではない。実際、図示されている畳み込みシステム１０の実施形態は、代替として、直列に通信するプロセッサの一次元アレイ（プロセッサの「パイプ・ライン」と呼ばれる）の形で実施されることも可能である。
【００４０】
図２（背景技術）は、図１のプロセッサ１４（すなわち、ＳＥＡｆｏｒｔｈ−２４Ａプロセッサ・コア）の１つのプロセッサの主な内部機能の線図である。プロセッサ１４ａ〜ｘのそれぞれは、一般に、単独で機能するコンピュータであって、これには、演算論理装置（ＡＬＵ  ３０）、いくつかの読み出し専用メモリ（ＲＯＭ  ３２）、いくつかのランダム・アクセス・メモリ（ＲＡＭ  ３４）、命令復号ロジック部３６、命令エリア３８、データ・スタック４０、およびリターン・スタック４２が含まれる。さらに、１８ビットの「Ａ」レジスタ（Ａレジスタ４４）、９ビットの「Ｂ」レジスタ（Ｂレジスタ４６）、９ビットのプログラム・カウンタ・レジスタ（Ｐレジスタ４８）、および１８ビットのＩ／Ｏ制御およびステータス・レジスタ（ＩＯＣＳレジスタ５０）が含まれる。さらに、４個の通信ポート（まとめてポート５２、個々のポートはポート５２ａ〜ｄ）が含まれる。ポート５２のそれぞれは、エッジおよびコーナーのノードの場合を除き、それぞれのバス２８に接続される（さらに、１８本のデータ線と、読み出し線と、書き込み線とを有するが、これらは、個々には示されていない）。
【００４１】
ＳＥＡｆｏｒｔｈ−２４Ａデバイス内のノードは、通信および処理を、いずれも非同期で、特に簡潔な（elegant）かつ効率的な様式で行うことにより、このデバイスを、本発明の畳み込みシステム１０の実施形態での使用に非常に好適なものにしている。しかしながら、この特定のデバイスを使用することや、あるいはその機能を実現しようとするハードウェアを使用することは、必須ではないことに注意されたい。また、アレイ１２のプロセッサ１４間でデータが実際にどのように伝達されるかについて、誤解がないように注意されたい。たとえば、デバイス間通信について考える場合には「プッシュ」か「プル」か、のたとえを用いることが可能であるが、通信が実際にはデバイス間の共同作業であることを留意していなければならない。
【００４２】
図３ａ〜ｃは、プロセッサ１４を使用するインバウンド通信、アウトバウンド通信、および内部通信を示す、図１の部分図である。図３ａは、入力装置１６とプロセッサ１４ａとの間、およびプロセッサ１４ａとプロセッサ１４ｂとの間でデータが渡される様子を示している。図３ｂは、プロセッサ１４ｗとプロセッサ１４ｘとの間、およびプロセッサ１４ｘと出力装置２２との間でデータが渡される様子を示している。そして、図３ｃは、プロセッサ１４ｉとプロセッサ１４ｊとの間でデータが渡される様子を示している。
【００４３】
図３ａ〜ｃの各プロセッサ１４は、総称キー（generic key）情報を保持する要素を有するように表されている。ＳＥＡｆｏｒｔｈ−２４Ａデバイスは、ＲＡＭ、ＲＯＭ、レジスタ、およびポートを備えており、それらはすべて、プログラムで計算を実行する際に使用されることが可能である。それは、ここでは特に、これから説明される、汎用情報（generic information）を保持する要素が、ＲＡＭ、ＲＯＭ、レジスタ、およびポートのいずれであってもよいことを意味している。プロセッサ１４ａの場合は、信号データ要素６０が、重要情報を保持する要素である。プロセッサ１４ｂ〜ｗの場合は、信号データ要素６０、積分核フィルタ要素６２、および計算された要素（calculated elements）６４の１つずつが、それぞれの重要情報を保持する要素である。そして、プロセッサ１４ｘの場合は、結果要素６６が、重要情報を保持する要素である。
【００４４】
図３ａは、データがどのようにしてアレイ１２に入力されることができるかを示している。この、畳み込みシステム１０の例示的実施形態では、プロセッサ１４ａは、入力装置１６からデータを受け取り、そのデータをプロセッサ１４ｂに提供することに専念する。したがって、プロセッサ１４ａは、入力装置１６からデータ・ワードを受け取って保存し、その信号データ要素６０を使用して、これらのデータ・ワードのインスタンスをプロセッサ１４ｂに提供することが可能であり、そのＲＡＭ  ３４の容量と、プロセッサ１４ａが適切にプログラムされているかどうか、とによる制限のみを受ける。
【００４５】
ＳＥＡｆｏｒｔｈ−２４Ａデバイスにおける通信および処理が、両方とも非同期であるため、いったんプロセッサ１４ａがプロセッサ１４ｂに対してデータを利用可能にすると、当面のタスクの処理が、概念上は、アレイ１２の残りの部分に「流れる」可能性がある。
【００４６】
図３ｂは、データがどのようにしてアレイ１２から抽出されることができるかを示している。プロセッサ１４ｘは、ここでは、プロセッサ１４ｗからデータを受け取り、そのデータを出力装置２２に提供することに専念する。したがって、プロセッサ１４ｘは、プロセッサ１４ｗからデータ・ワードを受け取って保存し、その結果要素６６を使用して、データ・ワードを出力装置２２に提供することが可能であり、この場合も、すべてが、そのＲＡＭ  ３４の容量と、プロセッサ１４ｘが適切にプログラムされているかどうか、とによる制限のみを受ける。
【００４７】
図３ｃは、信号データ要素６０および計算された要素６４の内容が全体としてプロセッサ１４ｂ〜ｗ間をどのように流れるかを示し、さらに、それらの合計が、畳み込み計算の過程において、どのようにして、各プロセッサ１４に累積として保存され、一度にすべてが渡されることが可能かを示している。後で詳述されるように、ここでは、プロセッサ１４ｂ〜ｗのそれぞれが、全体計算に寄与する演算を実行しているとすることができる。プロセッサ１４ｂの場合、この演算は、（その信号データ要素６０にある）新しい入力データ値と、（その積分核フィルタ要素６２にある）あらかじめ保存された畳み込み係数値とを使用する。この特定の実施例において、プロセッサ１４ｂは、それ以前の計算段階からの「部分的な」ものがまだないために、「計算された要素」６４を必要としない。しかしながら、プログラムの簡潔さのために、プロセッサ１４ｂは、ゼロがロードされた「計算された要素」６４を有することが可能である。さらに、ノードあたり複数の畳み込み係数が処理されるアプリケーションの場合（後述）、プロセッサ１４ｂは、計算された要素６４を有し、使用することが可能である。
【００４８】
引き続いて、プロセッサ１４ｃ〜ｗの場合、各プロセッサ１４は、あらかじめ保存された畳み込み係数値、フロー経路２４に沿ってそのそれぞれの先行のプロセッサ１４から得られた入力データ値、および、先行のプロセッサ１４から得られた中間値を用いることによって、全体の畳み込み計算に寄与する演算を実行する。畳み込み係数値は、それぞれの積分核フィルタ要素６２に保持され、入力データ値は、それぞれの信号データ要素６０に一時的に保持され、中間値は、それぞれの「計算された要素」６４に一時的に保持される。
【００４９】
図２と図３ａ〜ｃとを組み合わせると、ＳＥＡｆｏｒｔｈ−２４Ａデバイス内のプロセッサ１４ａ〜ｘのポートおよびレジスタが、どのようにして、上述のように用いられることが可能かをより全体的に知ることができる。たとえば、プロセッサ１４ａは、そのポート５２ｄを用いて入力データ値を右方向のプロセッサ１４ｂに渡し、プロセッサ１４ｂは、それを自身のデータ・スタック４０に入力することが可能である。これを実際に行う場合、プロセッサ１４ｂは、そのポート５２ｃに到着した入力データ値を読み取り、それを自身のデータ・スタック４０に入力する。つぎにプロセッサ１４ｂは、そのデータ・スタック４０に現在ある入力データ値と、そのデータ・スタック４０に既にあった畳み込み係数値とを用いて、畳み込みに寄与する演算を実行し、この結果である中間データ値を、そのポート５２ｄに入力する。
【００５０】
その後、同様の演算を、フロー経路２４に沿って、プロセッサ１４ｂ〜ｗにおいて行うことが可能である。ＳＥＡｆｏｒｔｈ−２４Ａデバイス内の各ノードの動作は非同期であるが、ここでのプロセッサ１４ｂ〜ｗにおける動作はすべて、概念上は、並列に行われるものと見なされることが可能である。したがって、プロセッサ１４ｂに関する上述の動作と基本的に同時に、同様の演算がプロセッサ１４ｉおよび１４ｊにおいて行われることが可能であり、たとえば、プロセッサ１４ｉおよび１４ｊは、単に、それぞれの畳み込み係数値を使用し、中間データ値を処理し、フロー経路２４に沿うそれぞれのポート５２を使用する。さらに基本的に同時に、プロセッサ１４ｗが、そのポート５２ｃにおいて、プロセッサ１４ｘが上述のように取り扱うべき出力データ値を利用可能にする。しかしながら、この場合も、ＲＡＭ、ＲＯＭ、レジスタ、およびポートはすべて、ＳＥＡｆｏｒｔｈ−２４Ａデバイス内でプログラムによって使用されることが可能であり、この前述の実施例は、同じ結果を達成するためにプロセッサ１４をプログラムすることが可能な、いくつもの方法のうちの１つに過ぎないことに注意されたい。
【００５１】
図４ａ〜ｆは、図１などに示したプロセッサ１４のアレイ１２の畳み込み計算の諸段階を概略的に表したブロック図である。概して、これらの各段階は、以下の動作を必要とする。
（１）データ・サンプル値と畳み込み係数値とを並列に掛け合わせる。
（２）段階（１）で得られた乗算した積の合計を計算する。
（３）アレイ１２内で（すなわち、パイプ・ラインに沿って）データ・サンプル値をシフトし、次のデータ・サンプル値を最初のノードに受け取らせ、最後のノードからデータ・サンプル値をドロップさせる。
（４）必要に応じて繰り返す（たとえば、以下に詳細に示すように）。
【００５２】
ＳＥＡｆｏｒｔｈ−２４Ａデバイスが備えるＲＡＭ、ＲＯＭ、レジスタ、およびポートのすべては、プログラムで実行される計算に使用可能であること、ならびに、本発明の畳み込みシステム１０は、機能および構造が、より少ない、より多い、または、異なる他のデバイスでも使用されることが可能であることから、図４ａ〜ｆにおけるデータ格納要素を、ここでは総称して「ビン」と呼ぶ。この後の説明を簡潔にするために、ここでの実施例では、実際の畳み込み計算で用いられる、畳み込み係数値、サンプル・データ値、およびプロセッサ１４を、同数（具体的には、それぞれ２２個）とする。このような数量は、多くの「現実世界」の応用では一般的でない可能性があるので、代替事例についての考察も後述するが、いずれの事例でも、以下のことが完全に理解されていれば、他の数量を用いることは、当業者にとって一般的に単純明快であるはずである。
【００５３】
図４ａは、正式の計算を開始することが可能な段階を示す。畳み込み係数値（ｃ0．．．ｃn（全部でｎ＋１個の値）（図１および図３ａ〜ｃのＳＥＡｆｏｒｔｈ−２４Ａデバイスではｎ＝２１））が、ビン（総称ではｃビン７２、個別にはｃビン７２(0..n)）にロードされており、別のビン（総称ではｄビン７４、個別にはｄビン７４(0..n)）にはゼロがロードされており、別のビン（総称ではｒビン７６、個別にはｒビン７６(0..2n-1)）が、最初は重要でない内容を有する。図４ａ〜ｆおよび以下の説明では、インデックスはゼロから始まり、「ｃ」は「係数」を意味し、「ｄ」は「データ」を意味し、「ａ」は「累積された」中間値であり、「ｒ」は「結果」を意味する。
【００５４】
図４ｂは、次の段階を示し、この段階では、最初のデータ・サンプル値（ｄ0）がｄビン７４(0)に受け取られている。計算は、図示されるように、基本的には、パイプ・ラインの長さにわたって同時かつ並列に進められ、最初の結果値（ｒ0）がｒビン７６(0)に格納される。
【００５５】
図４ｃは、次の段階を示し、この段階では、前のデータ・サンプル値（ｄ0）がｄビン７４(1)に移動しており、第２のデータ・サンプル値（ｄ1）がｄビン７４(0)に受け取られている。この場合も、計算は、図示されるように、基本的には、パイプ・ラインの長さにわたって同時かつ並列に進められ、第２の結果値（ｒ1）がｒビン７６(1)に格納される。
【００５６】
図４ｃと図４ｄとの間にｎ−２個の段階があり、それらは、概念上は、上述の段階と非常によく似ている。
【００５７】
図４ｄは、最後のデータ・サンプル値（ｄn）がｄビン７４(0)に受け取られている段階を示す。この場合も、計算は、図示されるように進められ、結果値（ｒn）がｒビン７６(n)に格納される。
【００５８】
図４ｅは、次の段階を示す。この時点では、ｎ＋１個のデータ・サンプル値（ｄ0．．．ｄn）のすべてが部分的に処理されており、最後のデータ・サンプル値（ｄn）がｄビン７４(1)に移動しており、ｄビン７４(0)にゼロ値が入力されている。計算が進められ、結果値（ｒn+1）がｒビン７６(n+1)に格納される。
【００５９】
図４ｅと図４ｆとの間に、さらにｎ−２個の段階があり、それらは、概念上は、上述の段階と非常によく似ている。
【００６０】
図４ｆは、最後のデータ・サンプル値（ｄn）の処理が最終的に完了する段階を示す。ここでの計算後、（ｎ＋ｎ−１）番目の結果値がｒビン７６(2n-1)に格納され、処理が完了する。この時点で、ｒビン７６(0..2n-1)は、ここで、ｎ＋１個のデータ・サンプル値（ｄ0．．．ｄn）と、ｎ＋１個の畳み込み係数値（ｃ0．．．ｃn）とに基づいて実行された畳み込み計算の完全な結果を保持している。
【００６１】
図５ａ〜ｆは、図１に示されたようなプロセッサ１４のアレイ１２の形で示される、新しいアルゴリズムに基づく畳み込み計算の諸段階を概略的に表したブロック図である。簡単に言えば、この新しいアルゴリズムは、フィルタ関数の微分（derivation）を用いる。この点を強調するために、ここで使用される畳み込み係数値を、ｃ'0．．．ｃ'mのように、異なる表記とする（図１および図３ａ〜ｃのＳＥＡｆｏｒｔｈ−２４Ａデバイスではｍ＝２１であるが、ここで別のインデックス参照を用いた理由については後述する）。
【００６２】
図５ａは、正式の計算を開始することが可能な段階を示す。微分（derivation）畳み込み係数値（ｃ'0．．．ｃ'm）は、ビン（総称ではｃ'ビン８２、個別にはｃ'ビン８２(0..m)）にロードされており、別のビン（総称ではｄビン８４、個別にはｄビン８４(0..m)）にはゼロがロードされており、単一のｐビン８６および一連の結果ビン（総称ではｒビン８８、個別にはｒビン８８(0..2m-1)）が、最初は重要でない内容を有する。前の実施例といくらか似ているが、インデックスはゼロから始まり、「ｃ'」は「係数」の微分（derivation）を意味し、「ｄ」はここでも「データ」を意味し、「ａ」はここでも、累積された中間値であり、「ｐ」は「部分」を意味し（結果に寄与する「部分」の場合と同様）、「ｒ」は「結果」を意味する。
【００６３】
図５ｂは、次の段階を示し、この段階では、最初のデータ・サンプル値（ｄ0）がｄビン８４(0)に受け取られている。計算は、図示されるように、基本的には、パイプ・ラインの長さにわたって同時かつ並列に進められ、最初の部分値（ｐ0）がｐビン８６に提供される。しかしながら、図４ａ〜ｆに示された従来型の畳み込みアルゴリズムを使用する変形形態と異なり、ここでは、「前の」部分値が現在の部分値に加算され、その結果がｒビン８８(0)に格納される。しかしながら、この早い段階では「前の」値が存在しないため、ゼロが最初の部分値（ｐ0）に加算されて最初の結果値（ｒ0）が計算され、これがｒビン８８(0)に格納される。
【００６４】
図５ｃは、次の段階を示し、この段階では、前のデータ・サンプル値（ｄ0）がｄビン８４(1)に移動しており、第２のデータ・サンプル値（ｄ1）がｄビン８４(0)に受け取られている。この場合も、計算は、図示されるように、基本的には、パイプ・ラインの長さにわたって同時かつ並列に進められ、第２の部分値（ｐ1）がｐビン８６に提供される。前の部分値（ｐ0）が現在の部分値（ｐ1）に加算され、この結果が、第２の結果値（ｒ1）としてｒビン８８(1)に格納される。
【００６５】
図５ｃと図５ｄとの間にｍ−２個の段階があり、それらは、概念上は、上述の段階と非常によく似ている。
【００６６】
図５ｄは、最後のデータ・サンプル値（ｄm）がｄビン８４(0)に受け取られている段階を示す。さらにこの場合も、計算は、図示されるように進められ、ｍ番目の結果値（ｒm）がｒビン８８(m)に格納される。
【００６７】
図５ｅは、次の段階を示す。この時点では、ｍ＋１個のデータ・サンプル値（ｄ0．．．ｄm）のすべてが部分的に処理されており、最後のデータ・サンプル値（ｄm）がｄビン８４(1)に移動しており、ｄビン８４(0)にゼロ値が入力されている。計算が進められ、結果値（ｒm+1）がｒビン８８(m+1)に格納される。
【００６８】
図５ｅと図５ｆとの間に、さらにｍ−２個の段階があり、それらは、概念上は、上述の段階と非常によく似ている。
【００６９】
図５ｆは、最後のデータ・サンプル値（ｄm）の処理が最終的に完了する段階を示す。ここでの計算後、（ｍ＋ｍ−１）番目の結果値（ｒ2m-1）がｒビン８８(2m-1)に格納され、処理が完了する。この時点で、ｒビン８８(0..2m-1)は、ここで、ｍ＋１個のデータ・サンプル値（ｄ0．．．ｄm）と、ｍ＋１個の微分（derivation）畳み込み係数値（ｃ'0．．．ｃ'm）とに基づいて実行された畳み込み計算の完全な結果を保持している。
【００７０】
ここまでをまとめると、本発明の畳み込みシステム１０が、必要な計算の大半を、直列ではなく並列に完結することを可能にすることは明らかである。たとえば、上述の簡略化された実施例では、２２個のプロセッサ１４が計算を並列に実行する。なお、ＳＥＡｆｏｒｔｈ−２４Ａデバイスの２４個のプロセッサ１４をすべて用いることも可能であるが、プロセッサ１４ａおよびプロセッサ１４ｘが計算とＩ／Ｏの両方をカバーしなければならないため、それほど高速にはならない。
【００７１】
このセクションの冒頭で述べたように、本発明の畳み込みシステム１０はさらに、新しい種類のアルゴリズムを用いることを可能にする。以下では、その態様について説明する。図６ａ〜ｃは、前述のアプローチの両方を用いて実行された畳み込みを表すグラフである。つまり、これらの図は、図４ａ〜ｆおよび図５ａ〜ｆで示されたものの概念的概要を与える。
【００７２】
図６ａは、従来型の畳み込み係数の使用を表す第１のトレース９２と、微分（derivation）畳み込み係数（すなわち、新しい種類のアルゴリズムで使用可能であって、本発明で使用されることが可能な畳み込み係数）の使用を表す第２のトレース９２'とを示す。図６ｂは、前述の両方のアプローチを用いて畳み込みが実行される入力データを表す単一トレース９４を示す（ここに示された他方のトレース９４'については後述）。図６ｃは、前述の両方のアプローチの結果を表す単一トレース９６を示す。図６ａ〜ｃに示された特定の実施例の場合、トレース９２は、次式で表される。
【００７３】
【数７】
2010524080.tif 000009
【００７４】
トレース９２'は、ｕ'（ｔ）で表される。トレース９４は、次式で表される。
【００７５】
【数８】
2010524080.tif 000010
【００７６】
そして、トレース９４'は、ν'（ｔ）で表される。ここで、ｔは、ステップサイズ０．０１で、−１から１までの区間に対して定義され、ｉは、ステップサイズ１で、１からｑまでの範囲であり、ｑは、フィルタ関数を通過するデータ点の数（この例では２０００）である。まとめて言えば、図６ａ〜ｃは、前述のアプローチのいずれかを用いて、まったく同じ結果がどのようにして達成されることができるかを示しており、その結果は、ここではトレース９６で示されている。
【００７７】
新しい種類のアルゴリズムを用いると、さらに別のアプローチも可能である。たとえば、図６ａ〜ｃを再度参照すると、（たとえば、トレース９４'で表される）微分（derivation）データ関数と（たとえば、トレース９２で表される）従来型のフィルタ関数とを用いることも可能であり、トレース９６で表される結果も同じになる。他の文献には、他者がこのアプローチを検討しているという何らかの暗示があるが、本明細書で開示された新規な様式で実装されるものではない。関数の微分（derivation）を使用することは、さらに論理的に考えられることも可能である。たとえば、データ関数およびフィルタ関数の両方の微分（derivation）を使用することは、理論的に可能である。さらにまた、データ関数およびフィルタ関数のいずれかまたは両方の、より高次の微分（derivation）を使用することも、理論的に可能である。実際問題として、これらのアプローチは、現実世界では有用性が限られる可能性があるが、それでもなお、本発明の趣旨によって包含される。図６ａ〜ｃでは、データ関数およびフィルタ関数の両方を微分するアプローチは、トレース９２'およびトレース９４'で表されており、結果はやはりトレース９６になる。
【００７８】
これらのどのアプローチにおいても、微分（derivation）を用いる際の幾つかの重要な考慮すべき事柄は、関数の微分（function derivation）を求めるために必要な作業から得られる。畳み込み計算では、使用されるデータ・サンプル値の数は、使用される係数値の数より多くなるのが普通である。したがって、通常、データ関数の微分（derivation）を求めるために必要な作業量より、フィルタ関数の微分（derivation）を求めるために必要な作業量のほうが少ないことになる。もちろん、状況によっては、データ関数の微分（derivation）を求めるための追加作業がほとんどまたはまったく不要な場合もあるが、そのようなことはほとんどまれである。さらに、通常異なるデータ・サンプル値に対して複数の畳み込み計算を実行する場合には、同じフィルタ係数値が使用されることが多いため、フィルタ係数値を求めるための作業は、再利用が可能な作業であり、また、「償却される」作業である。実際、多くのアプリケーションにおいて、この作業量は設計時に費やされ、フィルタ値は、プログラム定数として入力されることが可能である（たとえば、ＳＥＡｆｏｒｔｈ−２４ＡのようなデバイスのＲＯＭ  ３２に格納されることも可能である）。
【００７９】
引き続き図６ａ〜ｃについてであるが、トレース９２およびトレース９４は、振幅範囲が広く、トレース９２'およびトレース９４'は振幅範囲が著しく狭いことが見てとれる。実際問題として、これは、トレース９２'およびトレース９４'の各値を、より少ないビット数で表現することが可能であることを意味する。このことの重要性が認識されるのは、利用可能なツールの性質、すなわち、デジタル・プロセッサの本来的な制限について考えるときである。ＳＥＡｆｏｒｔｈ−２４Ａデバイスは、実際に、他の多くの好適な候補より相当優秀であるが、発明者らは、本発明の畳み込みシステム１０が、現代のデジタル・プロセッサの本来的な制限のいくつかを克服することに役立つかについて、幾つかのポイントを大まかに示すことが可能であり、ここでは、引き続き、ＳＥＡｆｏｒｔｈ−２４Ａデバイスの使用を再開する。
【００８０】
たとえば、トレース９２の畳み込みフィルタ値は、１８ビット値で表現されなければならないかもしれないのに対し、トレース９２'において本発明のアプローチに用いられる値は、９ビットあるいはさらに少ないビット数の値で表現されることができる。同様に、トレース９４で使用されるデータ・サンプル値は、１８ビット値で表現されなければならないかも知れないのに対し、トレース９４'において本発明のアプローチに用いられる値は、９ビットあるいはさらに少ないビット数の値で表現されることができると考えることが可能である。すべて９ビットの値を用いることは、本発明の畳み込みシステム１０において、約４倍（４Ｘ）の速度増加をもたらすことができるというのが本願発明者の観察であった。
【００８１】
演算を直接実行できる値のサイズに関して、デジタル・プロセッサは本来的に制限される。たとえば、１９７１年にＩｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎが世に出した４００４プロセッサが処理できたのは４ビット値であり、現行世代のほとんどのパーソナル・コンピュータに搭載されているプロセッサが直接処理できるのは、３２ビット値か６４ビット値である。さらに、一般的に、今日のほとんどのプロセッサで可能な演算のうちで、速度が最も遅くなるものの１つが、大きな値の乗算である。本願発明者の行った観察によれば、乗算演算は、畳み込みアルゴリズムの実行時間の６０〜９０％を占める可能性がある。
【００８２】
ＳＥＡｆｏｒｔｈ−２４Ａデバイスも、デジタル・プロセッサのこうした一般原則の例外ではない。ＳＥＡｆｏｒｔｈ−２４Ａデバイスは、Ｆｏｒｔｈ言語を用い、符号なしの値の場合は１８ビット（符号付きの値の場合は１７ビット）で表される数値、または、符号なしの値の場合は９ビット（符号付きの値の場合は８ビット）で表される数値を扱うことを前提とする。したがって、たとえば、１０ビットを要する値の場合は、実質的に、値が１８ビットを要する場合と同じに処理されなければならない。図２を再度参照すると、ＳＥＡｆｏｒｔｈ−２４Ａデバイス内の各プロセッサ１４において、１個のＡレジスタ４４が１８ビットであり、１個のＢレジスタ４６が９ビットであり、ＲＯＭ  ３２およびＲＡＭ  ３４のワード幅が１８ビットであり、ポート５２の幅が１８ビットであることを再確認されるであろう。
【００８３】
ここで、プロセッサ１４における、Ｆｏｒｔｈ言語での２個の１８ビット値の乗算と等価な処理は、３６個のオペコードからなる次のシーケンスを必要とする（ここで「．」はｎｏｐ（無演算）命令を表し、「＋＊」はｐｌｕｓ−ｓｔａｒ（ビットごとの乗算）命令を表す）。
（９）  ．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊  
これに対し、プロセッサ１４における、Ｆｏｒｔｈ言語での１個の１８ビット値と１個の９ビット値との乗算と等価な処理は、１８個のオペコードからなる次のシーケンスを必要とする。
（１０）  ．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊．＋＊  
そして、プロセッサ１４における、Ｆｏｒｔｈ言語での２個の９ビット値の乗算と等価な処理は、９個のオペコードからなる次のシーケンスを必要とする。
（１１）  ＋＊＋＊＋＊＋＊＋＊＋＊＋＊＋＊＋＊  
明らかに、計算の負荷および達成可能速度に関しては、式（９）の計算が最も好ましくないタスクであり、式（１１）の計算が最も好ましいタスクである。これらはそれぞれ、１倍、２倍、および４倍の速度の動作であると言うことができる。
【００８４】
ここで、上述の概念的な内容に関して、より厳密な「証明」を行う。本発明の畳み込みシステム１０に用いることが可能な、新しい種類のアルゴリズムでは、積分核の直接表現（たとえば、式（１）、および大まかには「背景技術」のセクションを参照）の代わりに微分表現を用いる。次式は、基本的には、式（５）を書き換えたものである。
【００８５】
【数９】
2010524080.tif 000011
【００８６】
ここで、ｆ（ｔ−τ）は積分核（integral kernel）を表す。しかしながら、その代わりに、積分核をｆ'（ｔ−τ）で表すものとする。その結果が次式である。
【００８７】
【数１０】
2010524080.tif 000012
【００８８】
ここで、この積分核は特定のローパス・フィルタであるか、ローパス・フィルタで表されることが可能であるとすると、次式の近似のようになり、
（１４）  ｆ'（ｃt-k）＝ｆ（ｃt-k）−ｆ（ｃt-k-Δτk）
これにより、次式が得られる。
【００８９】
【数１１】
2010524080.tif 000013
【００９０】
ここで、式（１５）の等号の右辺の第１項が、単純にｒ（ｔ）であることは自明である。また、それほど自明ではないが、等号の右辺の第２項は、単純に、ちょうど時間ステップ１つ分（Δτ）前からの、以前の畳み込み値に等しく、これは、次式で表される。
【００９１】
【数１２】
2010524080.tif 000014
【００９２】
したがって、直接積分核関係を利用する畳み込みと、直接積分核関係の微分（derivation）を利用する畳み込みとの間には、次の関係が成り立つ。
（１７）  ｒ'（ｔ）＝ｒ（ｔ）−ｒ（ｔ−Δτ）  →  ｒ（ｔ）＝ｒ'（ｔ）＋ｒ（ｔ
−Δτ）
ここで重要な点として、直接表現を利用する畳み込みは、核の微分（derivation）を利用する畳み込みと前に計算された畳み込みとの和と、まったく同じであることを理解されたい。このことは、新しい和が、古い和に、丁度計算されたばかりのものを加えたものに等しい、と言うことと同じである。
【００９３】
これを、本発明の畳み込みシステム１０で使用可能な、新しい種類のアルゴリズムのコンテキストに適用すると、直接フィルタ係数値（ｃ0．．．ｃn）を用いて、微分（derivation）係数値（ｃ'0．．．ｃ'n+1）を、ｃ'0＝ｃ0−０、ｃ'1＝ｃ1−ｃ0、ｃ'2＝ｃ2−ｃ1、．．．、ｃ'n＝ｃn−ｃn-1、およびｃ'n+1＝０−ｃnのように計算することが可能である。ただし、ｃ0の値が非ゼロの場合は、単純に、ｃ'0＝ｃ0−０＝ｃ0にする。同様に、ｃ0の値がゼロの場合は、単純に、ｃ'0＝０−０＝０とする。微分（derivation）フィルタ値を値ゼロに関連付けることまでする理由がない。それは、微分（derivation）フィルタ値が、累積された中間値（ａ0）に寄与しないからである。この理由付けを、ゼロである、任意の直接フィルタ値または任意の直接フィルタ値の微分（derivation）に拡張することが可能である。これは、フィルタ係数値が、特定のノードで計算されている累積された中間値に寄与しない場合には、そのフィルタ係数値をそのノードに関連付ける必要がないためである。それにもかかわらず、第１のノード以外では、各ノードにおける部分和を、依然として、計上しなければならない。
【００９４】
ここで、なぜ、図４ａ〜ｆでインデックスｎを使用し、図５ａ〜ｆでインデックスｍを使用したかに戻ると、これは、直接ベースのアルゴリズムを使用することと、微分（derivation）ベースのアルゴリズムを使用することとの、ある重要な違いを強調するためである。前のパラグラフからわかるように、ｎ個の直接フィルタ係数値（ｃ0．．．ｃn）が使用可能である場合は、ｎ＋１個の微分（derivation）係数値（ｃ'0．．．ｃ'n+1）が必要である。したがって、たとえば、直接ベースのアルゴリズムを使用する応用に２１個のプロセッサを適用するのであれば、同じアプリケーションに微分（derivation）ベースのアルゴリズムを使用する場合には、２２個のプロセッサが必要である。また、直接ベースのアルゴリズムを使用する応用に２２個のプロセッサを適用するのであれば、同じ応用に微分（derivation）ベースのアルゴリズムを使用する場合には、２３個のプロセッサが必要である。このため、図１および図３ａ〜ｃのＳＥＡｆｏｒｔｈ−２４Ａデバイスの場合には、１個のプロセッサを未使用のままにするか、１個のプロセッサにＩ／Ｏ機能を結合して、微分（derivation）ベースのアルゴリズムには２３個のプロセッサを用いるようにする必要がある。このことは、２４プロセッサ・デバイス（たとえば、ＳＥＡｆｏｒｔｈ−２４Ａ）を使用する場合には多少の問題を呈するが、４０プロセッサ・デバイス（たとえば、ＳＥＡｆｏｒｔｈ−４０Ａ）を使用する場合には、かなり軽微な問題となり、８０個のプロセッサ、９６個のプロセッサ、１２８個のプロセッサなどのデバイスを使用する場合には、ますます問題にならなくなる。
【００９５】
なお、本明細書では、使用する畳み込み係数値およびサンプル・データ値の数を同じにすることにより、説明を簡単にしている。直接ベースのアルゴリズムを使用する場合に２２個のサンプル・データ値を処理しなければならないとすると、微分（derivation）ベースのアルゴリズムを使用する場合には２３個のサンプル・データ値を処理しなければならない。もちろん、２２個の実データ値を使用し、２３番目の値にゼロを「パディング」することは可能である。しかしながら、より一般的には、このことは問題にならない。現実世界の応用のほとんどでは、大量の（場合によっては無限量に近づく）サンプル・データ値が使用されるからである。
【００９６】
まとめると、直接表現ではなく微分（derivation）表現を利用する利点は、たいていの場合に、微分（derivation）の振幅を表現するために必要な値の絶対値が、直接フィルタの振幅を表現するために必要な値の絶対値より、ずっと小さいことである。今一度ＳＥＡｆｏｒｔｈ−２４Ａデバイスを例にとると、ＳＥＡｆｏｒｔｈ−２４Ａデバイスの場合には、振幅値を表すためにフル１８ビットのデータ・ワードを用いなくとも、９ビットのデータ・ワードで十分であることが多い。９ビット表現で十分であると見なすことを可能にする要件は２つある。第１の要件は、係数値が９ビットの符号なし（または８ビットの符号付き）で表されることである。第２の要件は、連続する直接フィルタ係数値間の差が９ビットの符号なし（または８ビットの符号付き）で表されることである。図６ａ〜ｃで示された例で使用されるような、典型的なローパス・フィルタの場合は、最上位ビットが符号ビットのままなので、微分（derivation）値は８ビットだけで表されなければならない。原則として、問題の値が符号なしであるか、符号なしとして扱われることが可能であって、かつ、連続する直接係数値間の差が５１２単位未満である場合は、微分（derivation）近似が適切な方法である。そうでない場合、連続する直接係数値間の差は、２５６単位未満でなければならない。
【００９７】
図７は、例示的な直接フィルタのコード・リスト７００である。ここで使用されているプログラミング言語は、Ｆｏｒｔｈであり、ターゲット・ハードウェア・プロセッサ１４は、ＳＥＡｆｏｒｔｈ−２４Ａデバイスである。
【００９８】
アイテム７０２は、「ＩＯ」を、ＩＯＣＳレジスタ５０と等しくするコンパイラ命令である。これは、データがどこから読み出され、どこに書き込まれるかを指定する。ただし、ＳＥＡｆｏｒｔｈ−２４ＡデバイスのＩＯＣＳレジスタ５０は、同時に別々のポート５２に対して読み出しと書き込みとを指定することが可能である。あまり高機能ではないデバイスに慣れている人は、混乱を回避するため、以降を読み進める際にこの点に留意されたい。
【００９９】
アイテム７０４は、「Ｈ」を、係数値と等しくするコンパイラ命令である。ここで「１２３」は、単純に、例として使用される値である。これは、このプロセッサ１４の場合のｃビン７２の内容になる。
【０１００】
アイテム７０６は、Ｆｏｒｔｈ言語におけるコメントである。
【０１０１】
アイテム７０８は、Ｆｏｒｔｈ言語におけるロケーション・ラベルである。
【０１０２】
アイテム７１０は、畳み込み計算を行うためにプロセッサ１４を初期化するＦｏｒｔｈ命令のシーケンスである。具体的には、まず、データ・スタックの一番上にＩＯがロードされる。つぎに、そこからＢレジスタ４６にポップされて、その結果、ＩＯＣＳレジスタ５０をポイントする。つぎに、データ・スタックの一番上にＨがロードされる。つぎに、ここでこの命令シーケンスを収容するのに用いられる１８ビット命令ワードにｎｏｐがパディングされる。
【０１０３】
アイテム７１２は、条件付きコンパイルによって３つのケースが扱われるループの先頭を指定する。これは、プロセッサ１４が、パイプ・ラインにおける最初のプロセッサ（プロセッサ１４ｂ）なのか、中間のプロセッサ（プロセッサ１４ｃ〜ｖのいずれか）なのか、最後のプロセッサ（プロセッサ１４ｗ）なのかに応じて、プログラムされる。図３ａ〜ｃも参照されたい。
【０１０４】
アイテム７１４は、最も典型的な場合（対象プロセッサ１４がプロセッサ１４ｃ〜ｖのうちの１つである場合）について、命令のコンパイルの開始を指定する。
【０１０５】
［注  図７〜８の命令ワードの右側のコメントは、関連する場合に、データ・スタックおよびリターン・スタックを表す２カラム形式を使用しており、この形式では、右寄りの要素が、各スタックの一番上である。以下の説明中の丸括弧（parentheticals）は、この形式を、多くのＦｏｒｔｈ教科書で見られる「前−−後、および左寄りの要素が一番上」の形式に「変換」したものを示す。このように、本実施例が理解しやすくなるように、両方の形式を提示している。］
【０１０６】
アイテム７１６は、別のシーケンスのＦｏｒｔｈ命令である。具体的には、まず、データ・サンプル値が、Ｂレジスタ４６がポイントしている場所から読み出され、データ・スタックにプッシュされる（h -- s h）。つぎに、累積値（ａ）も読み出され、データ・スタックにプッシュされる（s h -- a s h）。つぎに、データ・スタックの一番上の要素がポップされ、リターン・スタックの一番上にプッシュされる（D: a s h -- s h R: -- a）。つぎに、データ・スタックの一番上の要素が複製され、データ・スタックにプッシュされる（D: s h -- ssh R: a -- a）。
【０１０７】
アイテム７１８では、データ・スタックの一番上の要素がポップされ、リターン・スタックの一番上にプッシュされる（D: s s h -- s h R: a -- s a）。つぎに、大規模乗算（「ＭＵＬＴ」（ＳＥＡｆｏｒｔｈ−２４ＡデバイスのＢＩＯＳにおいて与えられている定義））が実行される。データ・スタックの上２つの要素は、ここでは乗数および被乗数として使用され、一番上の要素が乗算の結果（ａ'）に置き換えられ、被乗数は、そのままデータ・スタックの２番目の要素として残される（D: s h -- a' h R: s a -- s a）。
【０１０８】
アイテム７２０が続き、ここでは、リターン・スタックの一番上の要素がポップ・オフされて、データ・スタックにプッシュされる（D: a' h -- s a' h R: s a -- a)。つぎに、データ・スタックの一番上の要素がポップ・オフされて、Ｂレジスタ４６がポイントしている場所に書き込まれる（D: s a' h -- a' h R: a -- a）。つぎに、リターン・スタックの一番上の要素がポップ・オフされて、データ・スタックにプッシュされる（D: a' h -- a a' h R: a --）。つぎに、ｎｏｐが、使用されている１８ビット命令ワードにパディングされる。
【０１０９】
アイテム７２２では、データ・スタックの上２つの要素が互いに加算され、一番上の要素が新しい累積和（ａ''）に置き換えられ、２番目の要素が１つ下の要素に置き換えられる（D: a a' h -- a'' h R: -- ）。
【０１１０】
アイテム７２４では、対象プロセッサ１４がプロセッサ１４ｃ〜ｖのうちの１つである場合についてのコードの条件付きコンパイルを終了する。
【０１１１】
図７に示される他の２つの条件付きコンパイルの選択肢については、明快に理解されるであろう。プロセッサ１４ｂの場合は、読み出して加算すべき「事前」累積値がないため、より単純である。また、プロセッサ１４ｖの場合も、現在のデータ・サンプル値を「後続の」プロセッサに書き込む必要がないため、いくらか単純である。
【０１１２】
最後にアイテム７２６は、プロセッサ１４ｂ〜ｗのすべてについてコンパイルされる命令シーケンスであって、ここでは、データ・スタックの一番上の要素がポップ・オフされ、Ｂレジスタ４６がポイントしている場所に書き込まれる（D: a'' h -- h R: --）。つぎに、ループがアイテム７１２に戻る。
【０１１３】
図８ａ〜ｂは、例示的な微分（derivation）フィルタのコード・リスト８００である。図８ａは、（計算が９ビットか１８ビットかということ以外は）図７と概念的に同様の機能を実行するコードを示しており、図８ｂは、微分（derivation）ベースのアルゴリズムで使用される追加コードを示している。
【０１１４】
図８ａからわかるように、コードの大部分は、前述の直接フィルタ７００の場合と基本的に同じである。しかし、１つの例外はアイテム８０２であり、ここでは、（ＭＵＬＴ定義を用いて実行される大規模乗算の代わりに）小規模乗算を実行するために、９個のｐｌｕｓ−ｓｔａｒ（＋*」）演算が用いられる。
【０１１５】
アイテム８０４は、リターン・スタック内の部分値（ｐ）をゼロに初期設定するＦｏｒｔｈ命令のシーケンスである。具体的には、まず、リテラルがデータ・スタックに配置され（D: h -- p h R: -- ）、つぎに、そこからリターン・スタックの一番上にプッシュされ（D: p h -- h R: -- p）、命令ワードに書き込む（fill out）ために２つのｎｏｐが使用される。［ただし、この特定のアプローチは、直接フィルタ７００との概念的比較を容易にするために選択されたものであり、プログラミング分野の当業者であれば、この処理を行うための、より効率的かつエレガントな方法があることは自明であろう。］
【０１１６】
次のアイテム８０６は、現在の部分値（ｐ）を用いて追加の加算を行う。現在の部分値（ｐ）は、リターン・スタックからポップされ、データ・スタックにプッシュされる（D: a'' h -- p a'' h R: p -- ）。つぎに、第１のｎｏｐが、次の命令まで時間を稼ぐ。つぎに、データ・スタックの上２つの要素が互いに加算される。ここで、一番上の要素が加算結果（累積和（ａ''）であると同時に次の部分値（ｐ'）である）に置き換えられ、２番目の要素が１つ下の要素に置き換えられる（D: p a'' h -- p' h R: --）。つぎに、第２のｎｏｐが、１８ビット命令ワードにパディングされる。
【０１１７】
次のアイテム８０８は、累積和（ａ''）を次の部分値（ｐ'）としてリターン・スタック内に保持する。累積和（ａ''）は複製される（D: a'' h - - p' a'' h R: -- ）。次の部分値（ｐ'）は、データ・スタックからポップされ、リターン・スタックにプッシュされる（D: a'' h -- a'' h R: -- p'）。つぎに、２つのｎｏｐが、１８ビット命令ワード以外にパディングされる。
【０１１８】
図８ｂは、微分（derivation）ベースのアルゴリズムが用いられる場合の「積分器」ステップに用いられる追加コードを示している。ただし、この特定の例では、このコードは、追加のプロセッサ１４で実行される。
【０１１９】
アイテム８１０は、Ｆｏｒｔｈ言語におけるコメントであり、アイテム８１２は、Ｆｏｒｔｈ言語におけるロケーション・ラベルである。このコードは、図８ａのコードに適切なコンパイラ命令を追加することによって条件付きでコンパイルされるか、独立してコンパイルされることが可能である。
【０１２０】
アイテム８１４は、第１に値ＩＯをＢレジスタ４６にフェッチし、第２に値＄３Ｆ（ポート・アドレス）をＡレジスタ４４にフェッチする、Ｆｏｒｔｈ命令のシーケンスである。
【０１２１】
アイテム８１６は、別のシーケンスのＦｏｒｔｈ命令である。具体的には、データ・スタックをゼロにする命令である。データ・スタックの一番上の要素は置き換えられて、そのデータ・スタック上にプッシュされ、つぎに、これがもう一度行われる（その一番上の要素が何であるかは無関係である）。つぎに、その上２つの要素がデータ・スタックからポップ・オフされ、それらの排他的論理和が計算され、その結果（ゼロ）が、またデータ・スタックにプッシュされる。
【０１２２】
アイテム８１８は、ループの開始を指定する。
【０１２３】
アイテム８２０は、別のシーケンスのＦｏｒｔｈ命令である。具体的には、まず、Ｂレジスタ４６がポイントしている場所から値が読み出され、その値がデータ・スタックにプッシュされる。つぎに、データ・スタックの上２つの要素が互いに加算され、一番上の要素が加算結果に置き換えられる（そして、２番目の要素が１つ下の要素に置き換えられる）。つぎに、データ・スタックの一番上の要素が複製され、データ・スタックにプッシュされる。つぎに、一番上の要素がデータ・スタックからポップされ、Ａレジスタ４４がポイントしている場所に書き込まれる。この操作の最終的な結果として、和が出力され、さらにコピーが、ループの次の実行の間、保持（累積）される。
【０１２４】
そして、アイテム８２２では、ループがアイテム８１８に戻る。
【０１２５】
以上のように、本発明の畳み込みシステム１０で使用される微分（derivation）ベースのアルゴリズムは、必要とする追加コードが非常に少ない。
【０１２６】
ここまで様々な実施形態を説明してきたが、それらは例としてのみ提示されていること、ならびに本発明の範囲は、前述の例示的実施形態のいずれによっても限定されてはならず、添付の特許請求の範囲およびそれらの等価物によってのみ定義されなければならないことを理解されたい。
【図１】
2010524080.tif 000015
【図２】
2010524080.tif 000016
【図３ａ】
2010524080.tif 000017
【図３ｂ】
2010524080.tif 000018
【図３ｃ】
2010524080.tif 000019
【図４ａ】
2010524080.tif 000020
【図４ｂ】
2010524080.tif 000021
【図４ｃ】
2010524080.tif 000022
【図４ｄ】
2010524080.tif 000023
【図４ｅ】
2010524080.tif 000024
【図４ｆ】
2010524080.tif 000025
【図５ａ】
2010524080.tif 000026
【図５ｂ】
2010524080.tif 000027
【図５ｃ】
2010524080.tif 000028
【図５ｄ】
2010524080.tif 000029
【図５ｅ】
2010524080.tif 000030
【図５ｆ】
2010524080.tif 000031
【図６ａ】
2010524080.tif 000032
【図６ｂ】
2010524080.tif 000033
【図６ｃ】
2010524080.tif 000034
【図７】
2010524080.tif 000035
【図８ａ】
2010524080.tif 000036
【図８ｂ】
2010524080.tif 000037
【国際調査報告】
2010524080.tif 000038