(57)【要約】離散ウェーブレット変換演算を実行するためのマイクロプロセッサ構造であって、前記離散ウェーブレット変換演算はｒ×ｋｍ個の入力サンプルのベクトルを含んでいる入力信号の分解を含み、ｒ×ｍは非ゼロの正の整数であり、規定された数の分解レベルｊ（ここで、ｊは１からＪまでの範囲の整数）にわたって、第１の分解レベルから開始して最終の分解レベルまで進行し、前記マイクロプロセッサ構造はいくつかの処理段を備え、前記処理段の数が離散ウェーブレット変換演算の分解レベルｊに対応していて、いくつかの基本処理要素によって実施され、前記各処理段の中で実施されている基本処理要素の数が分解レベルｊから分解レベルｊ＋１に対してｋのファクタだけ減少している。
2005500595.tif 000002
【特許請求の範囲】
【請求項１】
離散ウェーブレット変換の演算を実行するためのマイクロプロセッサ構造であって、前記離散ウェーブレット変換演算はいくつかの入力サンプルを含む入力信号ベクトルの分解を含み、１からＪまでの範囲内の整数であるｊの規定された数の分解レベルｊにわたって、最初の分解レベルからスタートして最終分解レベルまで進行し、前記マイクロプロセッサ構造はいくつかの処理段を備え、前記段のそれぞれが離散ウェーブレット変換の分解レベルｊに対応していて、いくつかの基本処理要素によって実施され、前記処理段のそれぞれにおいて実施されている基本処理要素の数が、増加している各分解レベルｊにおいて一定のファクタだけ減少しているマイクロプロセッサ構造。
【請求項２】
前記入力信号ベクトルがｒ×ｋｍ個の入力サンプルを含み、ｒ、ｋおよびｍが非ゼロの正の整数であり、前記マイクロプロセッサ構造の前記処理段のそれぞれにおいて実施される基本処理要素の数が、分解レベルｊから分解レベルｊ＋１までｋのファクタだけ減少していることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項３】
前記マイクロプロセッサ構造が、前記入力ベクトルの前記ｒ×ｋｍ個の入力サンプルのすべてを並列に処理するように構成されていることを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項４】
前記入力ベクトルの前記ｒ×ｋｍ個の入力サンプルのすべてを受信するように構成されているｒ×ｋｍ個の入力をさらに含むことを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項５】
前記第１の処理段における前記基本処理要素の数がｒ×ｋｍ−１であることを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項６】
各処理段の各基本処理要素が所定の数の入力を有し、ｋ組の係数値と前記所定の数の入力において受信された一組の入力値との間で一組のｋ個の内積演算を並列に実行するように配置され、一組の中の前記係数値の数、および並列に受信される前記入力値の数がそれぞれ前記ｋ個の内積を形成するために使用されるフィルタ長Ｌに等しく、前記基本処理要素がさらにｋ個の出力を含み、各出力が前記ｋ組の係数値と前記入力値の組との間で実行された前記ｋ個の内積の組のうちの１つの結果に対応している出力値を出力するように構成されていることを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項７】
各処理段の各基本処理要素が所定の数の入力を有し、ｋ組の係数値と前記所定の数の入力において並列に受信された入力値との間で一組のｋ個の内積演算を実行するように構成され、前記入力の数および前記並列に受信された入力値の数がフィルタ長Ｌｌｏｎｇに等しく、Ｌｌｏｎｇが前記ｋ個の内積のどれかを形成するために使用される係数値の最大数であり、前記処理要素がさらにｋ個の出力を含み、各出力が前記ｋ組の係数値の１つと前記Ｌ個の入力値の組との間で実行された前記ｋ個の内積の組のうちの１つの結果に対応している出力値を出力するように構成されていることを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項８】
各処理段の各基本処理要素が所定の数の入力を有し、２組の係数値と前記Ｌ個の入力において並列に受信された一組の入力値との間の２つの内積を実行するように構成され、前記２つの内積のうちの最初のものが低域フィルタリング演算を表し、前記２つの内積のうちの第２のものが高域フィルタリング演算を表し、前記入力の数、前記係数値の数および並列に受信された前記入力値の数が前記２つの内積を形成するために使用されるフィルタ長Ｌに等しく、前記基本処理要素が２つの出力をさらに含み、第１の出力は前記入力値の組について実行された低域フィルタリング演算の結果に対応している低域フィルタされた出力値を出力し、第２の出力が前記入力値の組について実行された高域フィルタリング演算の結果に対応している高域フィルタされた出力値を出力するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項９】
前記処理段２乃至Ｊのうちの少なくとも１つが、直前の処理段ｊ−１の各基本処理要素から前記ｋ個の出力値のうちの指定された１つを受信するように構成されたデータ・ルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記ｋ個の出力値のうちの前記規定されたものを、Ｌ個の出力値の組にまとめ、前記Ｌ個の出力値の組を処理段ｊの基本処理要素の入力に対して並列に供給するようにさらに構成されており、処理段ｊの各基本処理要素が前記直前の処理段ｊ−１から得られた所定のＬ個の出力値の組を受信するようになっていることを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項１０】
前記処理段２乃至Ｊのうちの少なくとも１つが、直前の処理段ｊ−１の各基本処理要素から低域フィルタされた出力値を受信するように構成されているルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記低域フィルタされた出力値をＬ個の低域フィルタされた出力値の組にまとめ、前記Ｌ個の低域フィルタされた出力値の組を処理段ｊの基本処理要素の入力に対して並列に供給するようにさらに配置され、処理段ｊの各基本処理要素が前記直前の処理段ｊ−１から得られた所定のＬ個の低域フィルタされた出力値の組を受信するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項１１】
前記第１の分解レベルに対応している前記処理段が、前記入力ベクトルの前記ｒ×ｋｍ個の入力サンプルを受信するように構成されたルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記ｒ×ｋｍ個の入力サンプルをＬ個の入力サンプルの組にまとめ、前記Ｌ個の入力サンプルの組を第１の処理段の基本処理要素の入力に対して並列に供給し、前記第１の処理段の各基本処理要素が所定のＬ個の入力サンプルの組を受信するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項１２】
前記第１の分解レベルに対応している前記処理段が、前記入力ベクトルの２ｍ個の入力サンプルを受信するように構成されているルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記２ｍ個の入力サンプルをＬ個の入力サンプルの組にまとめ、前記Ｌ個の入力サンプルの組を前記第１の処理段の前記基本処理要素の入力に対して並列に供給し、前記第１の処理段の各基本処理要素が所定のＬ個の入力サンプルの組を受信するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項１３】
各処理段の各基本処理要素が所定の数の入力を有し、２組の係数値と前記所定の数の入力において並列に受信された一組の入力値との間で２つの内積演算を実行するように構成され、前記入力の数、組内の前記係数値の数および並列に受信された前記入力値の数がそれぞれ２つの内積を形成するために使用されるフィルタ長Ｌに等しく、前記基本処理要素が２つの出力をさらに含み、各出力が前記２つの内積のうちのそれぞれの１つを出力するように構成され、前記マイクロプロセッサ構造は前記基本処理ユニットから内積のペアを受信するように構成されているデータ・ルーティング・ブロックをさらに含み、前記処理ユニットは完全アンシャッフル演算を実行していて、各処理要素からのそのようなフィルタリング演算からの内積を一緒にまとめるように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項１４】
各処理段の各基本処理要素が所定の数の入力を有し、ｋ組の係数値と前記所定の数の入力において並列に受信された一組の入力値との間のｋ個の内積演算を実行するように構成され、前記入力の数、一組の中の前記係数値の数および並列に受信された前記入力値の数、がそれぞれｋ個の内積を形成するために使用されるフィルタ長Ｌに等しく、前記処理要素がｋ個の出力をさらに含み、各出力が前記ｋ個の内積のうちのそれぞれの１つを出力するように構成され、前記マイクロプロセッサ構造が前記基本処理要素からのｋ個の内積を受信するように構成されているデータ・ルーティング・ブロックをさらに含み、前記基本処理要素が前記各処理要素の同様なフィルタリング演算からの内積を一緒にまとめるためにストライド置換を実行するように構成されていることを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項１５】
任意の分解レベルｊに対する離散ウェーブレット変換の結果が前記任意の分解レベルｊに対応している処理段における高域フィルタリング演算および低域フィルタリング演算からの出力値、およびすべての前の処理段の高域フィルタリング演算からの出力値から構築されるベクトルによって形成されるようになっていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項１６】
前記マイクロプロセッサ構造が少なくとも１つのコア処理ユニットを含み、前記コア処理ユニットが各処理段ｊにおいてｋｊ−１個の基本処理要素を含むことを特徴とする請求項２に記載のマイクロプロセッサ構造。
【請求項１７】
各処理段の各基本処理要素が所定の数の入力を有し、ｋ組の係数値と前記所定の数の入力において並列に受信された一組の入力値との間で一組のｋ個の内積演算を実行するように構成され、前記入力の数、一組の中の前記係数値の数、および並列に受信された前記入力値の数がそれぞれ前記ｋ個の内積演算を実行するために使用されるフィルタ長Ｌに等しく、各基本処理要素がｋ個の出力をさらに含み、各出力が前記ｋ組の係数値の１つと前記入力値の組との間で実行された前記ｋ個の内積演算のうちの１つの結果に対応している出力値を出力するように構成されていることを特徴とする請求項１６に記載のマイクロプロセッサ構造。
【請求項１８】
前記処理段２乃至Ｊのうちの少なくとも１つが、直前の処理段ｊ−１の各基本処理ユニットから前記ｋ個の出力値を受信するように構成されているデータ・ルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記ｋ個の出力値のうちの選択されたものをＬ個の出力値の組に一緒にまとめ、前記Ｌ個の出力値の組を処理段の前記基本処理要素の前記入力に対して並列に供給し、処理段ｊの前記各基本処理要素が前記直前の処理段ｊ−１から受信された所定のＬ個の出力値の組を受信するようにさらに構成されていることを特徴とする請求項１６に記載のマイクロプロセッサ構造。
【請求項１９】
前記第１の分解レベルに対応している前記処理段が、ｋＪ個の入力サンプルを含む前記連続したサブベクトルｉを受信するように構成されているルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記ｋＪ個の入力サンプルを、直後のサブベクトルｉ＋１からのいくつかのサンプルを付加することによって前記Ｌ個の組に正確に分割されるようにサブベクトルｉを構成することによって、前記ｋＪ個の入力サンプルをＬ個の入力サンプルの組に形成するように構成されており、前記ルーティング・ブロックは前記第１の処理段の前記基本処理要素の前記入力に対して並列に前記Ｌ個の入力サンプルの組を供給するようにさらに構成され、前記第１の処理段の各基本処理要素が所定のＬ個の入力サンプルの組を受信するようになっていることを特徴とする請求項１６に記載のマイクロプロセッサ構造。
【請求項２０】
前記マイクロプロセッサが前記入力ベクトルの前記ｒ×ｋｍ個の入力サンプルのうちのｋＪ個の入力サンプルを含むサブベクトルを受信するように構成されていることを特徴とする請求項１６に記載のマイクロプロセッサ構造。
【請求項２１】
前記ｋＪ個の入力サンプルを並列に受信するように構成されていることを特徴とする請求項２０に記載のマイクロプロセッサ構造。
【請求項２２】
前記マイクロプロセッサ構造の前記第１の処理段が時間的に進行しながら前記ｒ×ｋｍ個の入力サンプルの前記ベクトルを、連続したサブベクトルとして受信するように構成されていることを特徴とする請求項２０に記載のマイクロプロセッサ構造。
【請求項２３】
少なくとも１つの処理段が、第１の期間の直後の第２の期間においてサブベクトルｉ＋１からの少なくとも１つのサンプルを含むサブベクトルｉを第１の期間において処理するように構成されていることを特徴とする請求項２２に記載のマイクロプロセッサ構造。
【請求項２４】
前記少なくとも１つの処理段が、前記サブベクトルｉ＋１からＬ／２個のサンプルが付加されたサブベクトルｉを処理するように構成されていることを特徴とする請求項２３に記載のマイクロプロセッサ構造。
【請求項２５】
各基本処理要素がすべての基本処理要素に対して実質的に同じである１つの時間の期間において基本演算サンプルを実行するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項２６】
前記入力サンプルのベクトルが前記サブベクトルを形成するために構成されたシフト・レジスタをさらに含むことを特徴とする請求項１９に記載のマイクロプロセッサ構造。
【請求項２７】
前記基本処理要素のすべてが同じ演算を実行するように実施されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項２８】
前記サブベクトルｉに対して付加されるサンプルの数がＬ／２であることを特徴とする請求項１８に記載のマイクロプロセッサ構造。
【請求項２９】
各処理段の各基本処理要素が所定の数の入力ｐを有し、ｋ組の係数値と一組の入力値との間の一組のｋ個の内積演算を実行するように構成され、一組の中の前記入力値の合計数および一組の中の前記係数値の数がＬに等しく、ここで、Ｌは１からＬｍａｘまでの範囲内で選択可能であり、前記基本処理要素が所与の時刻において前記ｐ個の入力において並列に一組のｐ個の入力値を受信し、ｐ個の係数値と前記ｐ個の入力値との間の所与の動作期間においてｋ個の内積演算を含む内積演算のサブセットを実行するようにさらに構成されていることを特徴とする請求項１６に記載のマイクロプロセッサ構造。
【請求項３０】
各基本処理要素が一組のｐ個の入力値を連続した動作期間において受信するように構成されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項３１】
各基本処理要素がｋ個の出力をさらに含み、各出力が、前記ｋ組の係数値のうちの１つと前記入力値の組との間で実行された前記ｋ個の内積演算のうちの１つの結果に対応している出力値を出力するように構成されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項３２】
前記処理段２乃至Ｊのうちの少なくとも１つが、直前の処理段ｊ−１の前記処理要素のそれぞれから前記ｋ個の出力値を受信するように構成されているデータ・ルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記ｋ個の出力値のうちの指定されたものをＬ個の出力値の組にまとめ、前記Ｌ個の出力値の組を連続している動作期間において処理段ｊの前記基本処理要素の前記ｐ個の入力に対して並列にｐ個の値の連続したグループの中に前記Ｌ個の出力値の組を供給するようにさらに構成されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項３３】
前記第１の分解レベルに対応している前記処理段が、ｋＪ個の入力サンプルを含む前記連続したサブベクトルｉを受信するように構成されているルーティング・ブロックをさらに含み、前記ルーティング・ブロックが前記ｋＪ個の入力サンプルを、直後のサブベクトルｉ＋１からいくつかのサンプルを付加することによってＬ個の組に正確に分割されるようにサブベクトルｉを構成することによって、Ｌ個の入力サンプルの組に形成するように構成され、前記ルーティング・ブロックが、連続した動作期間において前記第１の処理段の前記基本処理要素の前記ｐ個の入力に対して並列にｐ個の値の連続したグループで前記Ｌ個の組を供給するようにさらに構成されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項３４】
少なくとも１つの基本処理要素が同じ処理段の少なくとも１つの他の基本処理要素に対して機能的に接続されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項３５】
少なくとも１つの基本処理要素が同じ処理段ｊの少なくとも１つの他の基本処理要素に対して機能的に接続されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項３６】
処理段ｊの少なくとも第１の基本処理要素が、同じ処理段ｊ内の第２の基本処理要素から入力を受信するように構成されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項３７】
同じ処理段内の前記第２の基本処理要素からの前記入力が、以前の動作期間において前記第２の基本処理要素において実行された内積演算のｐ個の中間結果を表している一組のｐ個の値であり、前記第１の基本処理要素が、現在の動作期間においてその内積演算を実行する際に前記ｐ個の中間結果の組を使用するように構成されていることを特徴とする請求項３６に記載のマイクロプロセッサ構造。
【請求項３８】
前記ｐ個の中間結果が前記第１の基本処理要素において並列に受信されるようになっていることを特徴とする請求項３７に記載のマイクロプロセッサ構造。
【請求項３９】
前記第１の基本処理要素が前記第２の基本処理要素から、初期の第１の動作期間の後、連続している各動作期間において一組のｐ個の入力値を受信するようになっていることを特徴とする請求項３７に記載のマイクロプロセッサ構造。
【請求項４０】
離散ウェーブレット変換を実行するための第２のマイクロプロセッサ構造を備えた１つのデバイスに集積化され、前記第２のマイクロプロセッサ構造が、前記最終の分解レベルＪに加えて少なくとも１つの更なる分解レベルを実行するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【請求項４１】
離散ウェーブレット変換を実行するための第２のマイクロプロセッサ構造を伴った１つのデバイスに集積化され、前記第２のマイクロプロセッサ構造が前記最終の分解レベルＪに加えて少なくとも１つの更なる分解レベルを実行するように構成されていることを特徴とする請求項１６に記載のマイクロプロセッサ構造。
【請求項４２】
離散ウェーブレット変換を実行するための第２のマイクロプロセッサ構造を伴った１つのデバイスに集積化され、前記第２のマイクロプロセッサ構造が前記最終の分解レベルＪに加えて少なくとも１つの更なる分解レベルを実行するように構成されていることを特徴とする請求項２９に記載のマイクロプロセッサ構造。
【請求項４３】
前記第２のマイクロプロセッサ構造が再帰型ピラミッド・アルゴリズムを実行するように構成されていることを特徴とする請求項４０に記載のマイクロプロセッサ構造。
【請求項４４】
請求項１の構造において実施するために離散ウェーブレット変換演算の実行ステップを実施するための方法。
【請求項４５】
前記マイクロプロセッサ構造が少なくとも１つのコア処理ユニットを含み、前記コア処理ユニットがｋＪ点のウェーブレット変換演算を実行するように構成されていることを特徴とする請求項１に記載のマイクロプロセッサ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散ウェーブレット変換（ＤＷＴ）を実施するためのアーキテクチャに関する。本発明は、ＤＷＴを使用する可能性のある任意の分野に関し、特に、ディジタル信号および画像の処理、データ圧縮、マルチメディア、および通信の分野において使用されるアーキテクチャに関するが、それらに限定されない。
【背景技術】
【０００２】
ドキュメントのリストがこの説明書の終りに与えられている。これらのドキュメントは、角括弧中のそれぞれの対応している数値によって以降で参照される。
「離散ウェーブレット変換」（ＤＷＴ）［１］‐［４］は、プロトタイプ・ウェーブレットと呼ばれる単独ベース関数の拡大／縮小および変換されたバージョンを使用することによって、時間領域において長さＮ＝ｒ×ｋｍの入力信号を分解する数学的技法である。１つの特定のケースでは、Ｎ＝２ｍ（すなわち、ｒ＝１およびｋ＝２）である。ＤＷＴは、Ｈａａｒウェーブレット、Ｈａｄａｍａｒｄウェーブレットおよびウェーブレット・パケットを使用して実行することができる。Ｈａａｒウェーブレットによる分解は低域および高域フィルタリングを含み、その後に両方の結果の帯域の２つによるダウンサンプリングおよび低周波帯域のＪレベルまたはオクターブへの繰り返された分解が続く。
【０００３】
過去１０年間において、ＤＷＴは他の従来の信号処理技法より好ましいことがしばしば見出されてきた。何故なら、ＤＷＴは、例えば、本来的なスケーラビリティ、Ｏ（Ｎ）（ここで、Ｎは処理されるシーケンスの長さ）の計算的複雑度、信号処理の用途に対する低いエイリアシング歪み、および適応型時間‐周波数ウィンドウなどの他の有用な特徴を提供するからである。従って、ＤＷＴは数値解析［５］‐［６］、生医学［７］、画像およびビデオ処理［１］、［８］‐［９］、信号処理技術［１０］および音声圧縮／解凍［１１］などの広範囲の用途に対して研究され、適用されてきた。ＤＷＴベースの圧縮方法は、ＪＰＥＧ２０００およびＭＰＥＧ‐４などの国際標準のベースとなっている。
【０００４】
これらの用途の多くにおいて、有用な結果を得るためにリアルタイム処理が必要である。ＤＷＴは線形複雑性を有しているが、多くの用途はソフトウェアによる解決法だけでは処理できない。ディジタル信号プロセッサ（ＤＳＰ）を使用したＤＷＴの実施により計算速度が大幅に改善され、いくつかの用途に対しては十分である。しかし、多くの用途においては、汎用プロセッサの場合、あるいはＤＳＰにおいてさえも、ソフトウェアによるＤＷＴ実施は遅過ぎる。従って、専用超大規模集積（ＶＬＳＩ）特定用途向け集積回路（ＡＳＩＣ）が最近多くの研究者の注目を集めており、いくつかのＤＷＴアーキテクチャが提案されている（［１２］‐［２４］）。これらのデバイスのいくつかはハードウェアの複雑性が低いことを目標にしている。しかし、サンプル数がＮであるシーケンスのＤＷＴを計算するためには少なくとも２Ｎクロック・サイクル（ｃｃ）を必要とする。それにもかかわらず、周期が約Ｎｃｃであるデバイスが設計されてきた（例えば、二重ハードウェアで提供される時の［１４］における３つのアーキテクチャ、［１５］におけるアーキテクチャＡ１、［１６］‐［１８］におけるアーキテクチャ、［１９］における並列フィルタなど）。これらのアーキテクチャのほとんどは、計算される分解能レベル（オクターブ）の数とは無関係に１つまたは２つのフィルタ・ユニットを採用することと、メモリの容量を減らすことの両方のために、「再帰型ピラミッド・アルゴリズム」（ＲＰＡ）［２６］、または同様なスケジューリング技法を使用する。これは作り出すことができる「最も早い」瞬間において各出力を発生することによって行われる［２６］。
【０００５】
［１７］および［１８］において提示されているアーキテクチャは、２つのパイプライン段から構成され、第１のパイプライン段は第１のＤＷＴオクターブを実施し、第２の段はそれ以降のすべてのオクターブをＲＰＡに基づいて実施する。［１７］および［１８］のアーキテクチャは、十分多い数のＤＷＴオクターブに対して約１００％のハードウェア利用率で動作するが、それらは制御が複雑であり、および／またはメモリの必要量が大きい。さらに、それらは２つのパルプライン段しか採用していないので、比較的低速である。従来のアーキテクチャにおいて得られる最高のスループットは、２ｍ点ＤＷＴの実施に対してＮ＝２ｍクロック・サイクルである。［３１］、［３２］および［３４］において以前に提案のアーキテクチャによって、約１００％のハードウェア利用率およびより高いスループットが得られる。［３４］において提示されているＦＰＰおよびＬＰＰのアーキテクチャはＤＷＴフィルタの長さに依存し、ＦＰＰアーキテクチャの場合、入力信号の長さに依存する。
【０００６】
現代の移動／ビジュアル通信において、低電力ＶＬＳＩ回路に対する需要が増加している。ＶＬＳＩ技術における改善によって、ハードウェアのコストが大幅に削減されている。従って、ハードウェアの増加のコストが掛かっても、周期を低減する方が価値のあることが多い。１つの理由は、周期の短いデバイスは消費電力が少ないことである。例えば、周期がＴ＝Ｎ／２ｃｃであるデバイスＤを採用して、周期がＴ’＝ＮｃｃであるデバイスＤ’の２倍の速度で処理することができる。別の方法として、デバイスＤが周波数ｆでクロックされている場合、周波数ｆ’＝２ｆでクロックされているデバイスＤ’と同じ性能を達成することができる。従って、デバイスＤに対して電源電圧（ｆに対して線形）およびワット損（ｆ２に関して線形）を、デバイスＤ’［２７］の電源電圧に対してそれぞれ２倍および４倍低減することができる。
【０００７】
高スループットのアーキテクチャは、通常、パイプラインまたは並列性を使用し、その中でＤＷＴのオクターブが同様なハードウェア・ユニット（パイプライン段）から構成されているパイプラインで実施される。パイプラインは既存のＤＷＴアーキテクチャ（例えば、［１２］、［２３］‐［２４］）によって既に使用されているが、最高速のパイプライン型の設計はＮ点のＤＷＴを実施するために少なくともＮ個のタイム・ユニットを必要とする。
【０００８】
ＤＷＴの実施に対する既知の設計のほとんどは、図１に示されているＤＷＴのツリー構造のフィルタ・バンク表現に基づいており、その場合、信号の分解のいくつかの（Ｊ個の）段（すなわち、オクターブ）があり、それぞれがその後に２のファクタによるダウン・サンプリングを伴っている。ダウンサンプリングの結果として、それ以降の各分解段に対するデータ入力の量は直前の分解段の直前に対する入力の量の半分である。これは、ツリー構造の方法を使用してＤＷＴを実施するように設計された代表的なパイプライン型のデバイスにおける分解段のハードウェアの利用率を大幅に低下させる。何故なら、オクターブｊ＝１，．．．，Ｊを実施している段は、普通は第１のオクターブにおいて使用されるクロック周波数より２ｊ−１倍低い周波数でクロックされるからである［２４］。この利用率の低さはＤＷＴオクターブを実施する時のパイプライン段のバランシングが悪いことからきており、その結果、効率が低くなる。
【０００９】
［３０］において、ツリー構造のフィルタ・バンク表現に基づいて１つのパイプライン・アーキテクチャが提案されており、それは２ｍ点のＤＷＴに対して約１００％のハードウェア利用率およびＮ／２＝２ｍ−１クロック・サイクルのスループットを達成する。これは可能な限りにおいて、ある段から次の段への半数の処理ユニットを使用しているＪ段のパイプラインを含む。［３４］‐［３５］において、ＤＷＴの流れ図表現が提案され、並列／パイプラインのＤＷＴアーキテクチャを作り出すためにツリー構造のフィルタ・バンク表現と比較された。特に、その流れ図表現はオクターブ内およびオクターブ間でのデータ転送を示すこと以外に、すべてのオクターブにおいて本来的な並列性を完全に具現している。これによって、パイプラインと並列性を組み合わせてより高いスループットおよびハードウェア利用率を達成することができる。特に、流れ図表現は２ｍ点のＤＷＴのｊ番目（ｊ＝１，．．．，Ｊ）のオクターブが全面的に、または部分的に並列に実施することができる独立の同様な２ｍ−ｊ個の演算を必要とすることを示している。ＤＷＴのオクターブはパイプライン型のモードで実施され、一方、すべてのオクターブは並列モードで実施され、その並列性のレベルは１つのオクターブから次のオクターブへ半分になっている。パイプライン段内に可変レベルの並列性を組み込むことによって、パイプライン段が完全にバランスされている並列パイプライン型のデバイスが設計される。これはパイプライン型のモードでオクターブを実施し、その中でパイプライン段が段から段へ変化している度合いで並列化されていることを意味する。このアイデアは多くの異なる方法で実現することができる。［３４］において、完全並列パイプライン型（ＦＰＰ）および制限された並列パイプライン型（ＬＰＰ）ＤＷＴアーキテクチャと呼ばれる２つのアーキテクチャが提案された。この２つのアーキテクチャは両方ともＪ個のパイプライン段から構成され、各パイプライン段は前の段に比べて半分の数のプロセッサ要素を含んでいる。結果として、非常に高いスループットおよび約１００％のハードウェア利用率が得られる。
【００１０】
既知の並列またはパイプライン型のアーキテクチャは本質的に入力の長さ、オクターブの数、長さ、およびある場合においては、低域および高域フィルタの実際の係数値などのＤＷＴのパラメータに本質的に依存する。これらのパラメータの値が大きい場合、これらのアーキテクチャは非常に大きくなる可能性がある。さらに、所与のアーキテクチャの所与のハードウェア実現の中でパラメータが固定されているＤＷＴを実現することだけが可能である。しかし、ＪＰＥＧ２０００においては、ＤＷＴは１つの画像のファイルに対して別々に適用され、その中で、タイルのサイズは１から２３２−１の範囲で変化することができる。分解のオクターブの数は異なるタイルに対して０から２５５まで変化する可能性がある。従って、パラメータが変化しているＤＷＴを実施することができるデバイス、言い換えれば、ＤＷＴパラメータには比較的依存しない一体化されたデバイスがあることが望ましい。そのようなデバイスを設計することは、直列のアーキテクチャの場合には簡単である。それは並列またはパイプライン型のアーキテクチャの場合にはそれほど簡単ではない。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来のアーキテクチャ［１２］‐［２６］のほとんどが、ＤＷＴフィルタの長さに対して比例している数の乗算器および加算器を採用している。いくつかのアーキテクチャ［１７］、［１８］はオクターブの数が変化しているＤＷＴを実施することができるが、オクターブの数が増えるにつれてそれらの効率が急激に低下する。
【課題を解決するための手段】
【００１２】
本発明の態様によれば、本発明は離散ウェーブレット変換の演算を実行するためのマイクロプロセッサ構造に向けられている。１つの実施形態においては、その離散ウェーブレット変換の演算は、規定された数の分解レベルｊにわたっていくつかの数の入力サンプルを含んでいる入力信号ベクトルの分解を含み、ここで、ｊは１からＪまでの整数であり、それは第１の分解レベルから始まって最終の分解レベルまで進行する。このマイクロプロセッサ構造はいくつかの処理段を備え、各段は離散ウェーブレット変換の分解レベルｊに対応し、いくつかの基本処理要素によって実施されている。各処理段の中で実施されている基本処理要素の数は分解レベルｊが増加するごとに一定のファクタだけ減少する。
このマイクロプロセッサ構造は、離散ウェーブレット変換の流れ図表現に基づいて一般にスケーラブルな構造である。
【００１３】
本発明においては、タイプ１およびタイプ２のコアＤＷＴアーキテクチャと呼ばれる２種類のＤＷＴアーキテクチャの一般的なパラメトリック構造、およびコアＤＷＴアーキテクチャのいずれかに基づいて構築され、そして複数コアＤＷＴアーキテクチャおよび可変分解能ＤＷＴアーキテクチャとそれぞれ呼ばれる２つの他のＤＷＴアーキテクチャの一般的なパラメトリック構造が導入されている。すべてのアーキテクチャは可変レベルの並列性で実施することができ、従って、特定の用途において必要なハードウェア資源の量を決定し、そして計算速度、コスト、チップ面積および消費電力の条件の間のトレードオフを行うための機会が提供される。本発明においては、効率（ハードウェアの利用率）が改善され、結果としてスループットまたは消費電力が改善されているＤＷＴアーキテクチャを開発するために、並列型およびパイプライン型の処理が組み合わされている。すべてのレベルの並列性においてほぼ１００％のハードウェア利用率で動作するいくつかのＤＷＴアーキテクチャの一般的な構造が提案されている。提示されているアーキテクチャは入力信号のサイズ、ＤＷＴフィルタの長さには比較的依存せず、そして可変分解能ＤＷＴアーキテクチャの場合には、オクターブの数にも依存せず、そして可変レベルの並列性で実施することができる。さらに、そのアーキテクチャは既存のＤＷＴ設計に比べて面積‐時間特性が極めて優れている。本発明は規則的で簡単に制御されるアーキテクチャを提供し、フィードバック、長い（入力の長さによって変わる）接続またはスイッチを含まない。それらはセミシストリック・アレイ(semisystolic array)として実施することができる。
本発明の実施形態を、添付の図面を参照しながら以下に記述するが、これは単なる例示としてのものにすぎない。
【発明を実施するための最良の形態】
【００１４】
本発明において提案されているアーキテクチャを説明するためには、ＤＷＴを定義し、そのアーキテクチャ内に実施される基本アルゴリズムを提示する必要がある。ツリー構造のフィルタ・バンク、格子構造、リフティング方式または行列表現などの、いくつかの代案の定義／表現がある。次の説明はＤＷＴの行列定義および流れ図表現を使用し、それは効率的な並列／パイプライン型ＤＷＴアーキテクチャの設計において非常に有効である。
離散ウェーブレット変換は線形変換ｙ＝Ｈ・ｘであり、ここで、ｘ＝［ｘ０，．．．，ｘＮ−１］Ｔおよびｙ＝［ｙ０，．．．，ｙＮ−１］Ｔは、それぞれ、長さＮ＝２ｍの入力および出力のベクトルであり、そしてＨは疎行列の積として形成されるＮ×Ｎ次のＤＷＴ行列である。
【００１５】
【数１】
2005500595.tif 000003
ここで、Ｉｋは単位（ｋ×ｋ）行列（ｋ＝２ｍ−２ｍ−ｊ＋１）であり、Ｄｊは次の構造を備えている段ｊにおける解析（２ｍ−ｊ＋１×２ｍ−ｊ＋１）行列である。
【００１６】
【数２】
2005500595.tif 000004
【００１７】
ここで、ＬＰ＝［ｌ１，．．．，ｌＬ］およびＨＰ＝［ｈ１，．．．，ｈＬ］は、それぞれ低域フィルタおよび高域フィルタの係数のベクトル（Ｌはフィルタの長さ）であり、そしてＰｊはサイズ（２ｍ−ｊ＋１×２ｍ−ｊ＋１）の完全アンシャッフル演算子の行列である。完全アンシャッフル演算子は構成要素のナンバリングがゼロから始まっていると仮定して、出力ベクトルの第１の（第２の）半分における入力ベクトルの偶数（奇数）番号の構成要素を収集する。簡単のため、低域フィルタおよび高域フィルタは両方とも長さが同じであり、その長さは偶数であると仮定される。その結果を任意のフィルタ長の一般的な場合に対して容易に拡張することができる。一般的な場合、（すなわち、Ｎ＝２ｍではなく、Ｎ＝ｒ×ｋｍの場合）ここで、ｋは２に等しくない（すなわち、２以外のフィルタリング演算がある）場合、アンシャッフル演算ではなく、適切なストライド置換が適用される。
【００１８】
式（１）および（２）において導入された表現を採用して、そのＤＷＴはＪ個の段（分解レベルまたはオクターブとも呼ばれる）において計算され、ここで、ｊ番目の段（ｊ＝１，．．．，Ｊ）は、スクラッチ変数の現在のベクトルによる疎行列Ｈ（ｊ）の乗算を含み、最初のそのようなベクトルは入力ベクトルｘである。すべての行列Ｈ（ｊ）の右下隅が単位行列であることに注目し、行列Ｄｊの構造を考慮に入れて、対応しているアルゴリズムを次の擬似コードとして書くことができる。
ここで、ｘ（ｊ）ＬＰ＝［ｘ（ｊ）ＬＰ（０）,．．．，ｘ（ｊ）ＬＰ（２ｍ−ｊ−１）］Ｔおよび、ｘ（ｊ）ＨＰ＝［ｘ（ｊ）ＨＰ（０）,．．．，ｘ（ｊ）ＨＰ（２ｍ−ｊ−１）］Ｔ（ｊ＝１，．．．，Ｊ）はスクラッチ変数の（２ｍ−ｊ×１）ベクトルであり、表記［（ｘ１）Ｔ，．．．，（ｘｋ）Ｔ］Ｔは列ベクトルｘ１，．．．，ｘｋの連結を表す。
【００１９】
アルゴリズム１
１．ｘ（０）ＬＰ＝［ｘ（０）ＬＰ（０）,．．．，ｘ（０）ＬＰ（２ｍ−ｊ−１）］Ｔ＝ｘを設定;
２．ｊ＝１，．．．，Ｊについて、ｘ（ｊ）ＬＰ＝［ｘ（ｊ）ＬＰ（０）,．．．，ｘ（ｊ）ＬＰ（２ｍ−ｊ−１）］Ｔおよびｘ（ｊ）ＨＰ＝［ｘ（ｊ）ＨＰ（０）,．．．，ｘ（ｊ）ＨＰ（２ｍ−ｊ−１）］Ｔを計算。
ここで、
【００２０】
【数３】
2005500595.tif 000005
【００２１】
または、同等に
２．ｉ＝０，．．．，２ｍ−ｊ−１について、
開始
ベクトル形成  //＊ベクトルｘ（ｊ−１）ＬＰの長さＬのサブベクトル＊//
ｘ〜＝［ｘ（ｊ−１）ＬＰ（２ｉ），ｘ（ｊ−１）ＬＰ（２ｉ＋１），ｘ（ｊ−１）ＬＰ（（２ｉ＋２）ｍоｄ２ｍ−ｊ＋１，．．．，ｘ（ｊ−１）ＬＰ（（２ｉ＋Ｌ−１）ｍоｄ２ｍ−ｊ＋１））］Ｔ
ｘ（ｊ）ＬＰ（ｉ）＝ＬＰ・ｘ〜；ｘ（ｊ）ＨＰ（ｉ）＝ＨＰ・ｘ〜を計算
終了
【００２２】
３．出力ベクトル形成
ｙ＝［ｘ（Ｊ）ＬＰ，ｘ（Ｊ）ＨＰ，ｘ（Ｊ−１）ＨＰ，．．．，ｘ（２）ＨＰ，ｘ（１）ＨＰ］Ｔ
式（２）の行列Ｄｊによるアルゴリズム１の計算は流れ図表現を使用して示すことができる。Ｎ＝２３＝８、Ｌ＝４、Ｊ＝３の場合の一例が図２に示されている。この流れ図はＪ個の段から構成され、ｊ番目の段（ｊ＝１，．．．，Ｊ）が２ｍ−ｊ個のノード（図２においてボックスとして示されている）を有している。各ノードは基本のＤＷＴ演算（図２（ｂ）参照）を表す。段ｊ＝１，．．．，Ｊのｉ番目（ｉ＝０，．．．，２ｍ−ｊ−１）のノードは、前の段のＬ個の巡回的に連続したノード２ｉ，２ｉ＋１，（２ｉ＋２）ｍｏｄ２ｍ−ｊ＋１．．．，（２ｉ＋Ｌ−１）ｍｏｄ２ｍ−ｊ＋１からまたは（第１の段のノードの場合には）入力から入って来るエッジを有している。すべてのノードは２つの出て行くエッジを有している。上側（下側）の出て行くエッジは低域（高域）フィルタ係数のベクトルと入って来るエッジの値のベクトルとの内積の値を表す。１つの段の出て行く値は完全アンシャッフル演算子に従って置換され、すべての低域構成要素（上側の出て行くエッジの値）が、置換されたベクトルの最初の半分の中に収集され、そして高域構成要素が、置換されたベクトルの第２の半分の中に収集される。次に低域構成要素が次の段に対する入力を形成するか、あるいは（最後の段のノードの場合は）出力値を表す。その段における高域構成要素および低域構成要素は所与の分解能での出力値を表す。
【００２３】
本質的に、流れ図表現は離散ウェーブレット変換の１つの代案の定義を提供する。それは少なくとも実施の観点から、従来のＤＷＴ表現、例えば、ツリー構造のフィルタ・バンク、リフティング方式または格子構造表現などと比較して、いくつかの利点を有する。
しかし、示されてきたようなＤＷＴの流れ図表現にはＮの値が大きい場合に非常に大きくなるという欠点がある。この欠点は次のことに基づいて克服することができる。Ｊ＜ｌｏｇ２Ｎ、すなわち、分解レベルの数が入力ベクトル内の点の数より大幅に小さいと仮定して（ほとんどの用途においてはＪ＜＜ｌｏｇ２Ｎである）、ＤＷＴの流れ図はＮ／２Ｊ個の同様なパターンから構成されていることが分かる（図２の２つの斜線領域参照）。
【００２４】
各パターンは入力信号をその各オクターブに対して形成する特定の戦略による２Ｊ点のＤＷＴとみなすことができる。ｊ番目（ｊ＝１，．．．，Ｊ）のオクターブの２ｍ−ｊ＋１個の入力値が元のＤＷＴ（Ｎ＝２ｍの長さの）内で、２Ｊ−ｊ＋１個の連続した値から構成されているＮ／２Ｊ＝２ｍ−Ｊ個のオーバラップしていないグループに分割される。
これは式（３）のベクトルｘ（ｊ−１）ＬＰをサブベクトルｘ（ｊ−１，ｓ）＝ｘ（ｊ−１）ＬＰ（ｓ・２Ｊ−ｊ＋１：（ｓ＋１）・２Ｊ−ｊ＋１−１）、（ｓ＝０，．．．２ｍ−Ｊ−１）に分割することに等価であり、ここで、そして以降において、表記ｘ（ａ：ｂ）はｘのａ番目からｂ番目までの構成要素から構成されるｘのサブベクトルを表す。ｓ番目のパターン内のｊ番目（ｊ＝１，．．．，Ｊ）の入力は次のベクトルのサブベクトルｘ＾（ｊ−１，ｓ）（０：２Ｊ−ｊ＋１＋Ｌ−３）である。
【００２５】
【数４】
2005500595.tif 000006
【００２６】
これはベクトルｘ（ｊ−１，ｓ）ＬＰと巡回的に次のＱｊベクトルＱｊ＝［（Ｌ−２）／２Ｊ−ｊ＋１］との連結である。
２ｍ−Ｊ個のパターンが１つのパターンに併合される場合、ＤＷＴのコンパクトな（またはコアの）流れ図表現が得られる。Ｊ＝３、Ｌ＝４の場合に対するＤＷＴのコンパクト流れ図表現の一例が図３に示されている。このコンパクトＤＷＴの流れ図はそのｊ番目の段（ｊ＝１，．．．，Ｊ）において２Ｊ−ｊ個のノードを有し、ここで、２ｍ−Ｊ個の一時的に分散されている値の組がすべてのノードに対して割り当てられている。すべてのノードは（「非コンパクトな」）ＤＷＴの流れ図の場合と同様に、Ｌ個の入って来るエッジおよび２つの出て行くエッジを有している。再び、入って来るエッジは前段のＬ個の「巡回的に連続した」ノードから入って来るが、ここではすべてのノードが一時的に分散された値の組を表す。すなわち、入力のｓ番目の値、ｓ＝０，．．．，２ｍ−Ｊ−１に対する、ｊ番目の段（ｊ＝１，．．．，Ｊ）のｉ番目のノードのＬ個の入力が、（ｊ−１）番目の段のノード（２ｉ＋ｎ）ｍｏｄ２Ｊ−ｊ＋１（ｎ＝０，．．．，Ｌ−１）に対して連結され、それはここではそれぞれの（ｓ＋ｓ’）番目の値を表し、ここで、ｓ'＝［（２ｉ＋ｎ）／２Ｊ−ｊ＋１］である。また、出力はここではコンパクトな流れ図の出て行くエッジにわたって、空間的にだけでなく時間的にも分散されている。すなわち、１つのノードの高域フィルタリングの結果または最後の段のノードの低域フィルタリングの結果に対応している各出て行くエッジは２ｍ−Ｊ個の出力値の組を表す。コンパクトＤＷＴ流れ図の構造は、ＤＷＴの長さには依存せず、分解レベルの数およびフィルタの長さにのみ依存することに留意されたい。ＤＷＴの長さは、すべてのノードによって表される値の数においてのみ反映される。また、このコンパクト流れ図は僅かに変更された付加戦略によって２Ｊ点のＤＷＴの構造を有していることにも留意されたい。実際に、この付加戦略はＤＷＴ定義の行列形成においてしばしば使用される。
【００２７】
Ｄ＾ｊがＤｊ（式（２）参照）（ｊ＝１，．．．，Ｊ）のメインの（２Ｊ−ｊ＋１×（２Ｊ−ｊ＋１＋Ｌ−２））個の小行列式を示すものとする。すなわち、Ｄ＾ｊを、Ｄｊの最初の２Ｊ−ｊ＋１個の行および最初の２Ｊ−ｊ＋１＋Ｌ−２個の列から構成されている行列であるとする。例えば、Ｊ−ｊ＋１＝２、そしてＬ＝６である場合、Ｄ＾ｊは次の形式となる。
【００２８】
【数５】
2005500595.tif 000007
【００２９】
式（４）の表記を採用して、コンパクト流れ図によって表される計算のプロセスを次の擬似コードによって記述することができる。
アルゴリズム２
１．ｓ＝０，．．．，２ｍ−Ｊ−１について、
ｘ（０，ｓ）ＬＰ＝ｘ（ｓ・２Ｊ：（ｓ＋１）・２Ｊ−１）を設定
２．ｊ＝１，．．．，Ｊ、ｓ＝０，．．．，２ｍ−Ｊ−１について
開始
２．１．  式（４）に従ってｘ＾（ｊ−１，ｓ）を設定
２．２．  ［（ｘ（ｊ，ｓ）ＬＰ）Ｔ，（ｘ（ｊ，ｓ）ＨＰ）Ｔ］Ｔ＝Ｄ＾ｊ・ｘ＾（ｊ−１，ｓ）（０：２Ｊ−ｊ＋１＋Ｌ−３）を計算
終了
【００３０】
３．出力ベクトル形成
【００３１】
【数６】
2005500595.tif 000008
【００３２】
ｓに対してサイクルを並列に実施することによって、並列のＤＷＴが実現される。他方、ｊおよびｓに対してサイクルのネスティングの順序を交換することによって、そしてｊに対して並列に（入れ子）サイクルを実施することによって、パイプライン型のＤＷＴの実現を実施することができる。しかし、これらの実現は両方とも効率が悪い。何故なら、演算の数が１オクターブから次のオクターブへ半分になるからである。しかし、２つの方法を組み合わせることによって、非常に効率の良い並列パイプライン型の、あるいは部分的並列パイプライン型の実現が実施される。
【００３３】
アルゴリズム２に対してパイプライン化を適用するには、リタイミングが適用されなければならない。何故なら、ｓに対する計算はｓ＋１，．．．，ｓ＋Ｑｊ−１に対する計算の結果を含み、それはｊ番目（ｊ＝１，．．．，Ｊ）のオクターブがＱｊステップの遅延を導入することを意味するからである。その遅延が累積されるので、ｊ番目（ｊ＝１，．．．，Ｊ）のオクターブに対する計算は、ステップｓ＝ｓ＊（ｊ），．．．，２ｍ−Ｊ＋ｓ＊（ｊ）−１の間に次の時間だけ遅れて始まらなければならない。
【００３４】
【数７】
2005500595.tif 000009
【００３５】
従って、計算はステップｓ＝ｓ＊（１）からステップｓ＝ｓ＊（Ｊ）＋２ｍ−Ｊ−１まで行われる。ステップｓ＝ｓ＊（１），．．．，ｓ＊（２）−１において、最初のオクターブだけの計算が実施され、ステップｓ＝ｓ＊（２），．．．，ｓ＊（３）−１において最初の２つのオクターブの演算だけが実施され、以下同様に実施される。ステップｓ＝ｓ＊（Ｊ）から開始して、ステップｓ＝ｓ＊（１）＋２ｍ−Ｊ−１まで（ｓ＊（Ｊ）＜ｓ＊（１）＋２ｍ−Ｊの場合）すべてのオクターブｊ＝１，．．．，Ｊの計算が実施されるが、ステップｓ＝ｓ＊（１）＋２ｍ−Ｊから始まって第１のオクターブに対する計算は実施されず、ステップｓ＝ｓ＊（２）＋２ｍ−Ｊから始まって、最初の２つのオクターブに対する計算は実施されない。以下同様になる。
【００３６】
一般に、ステップｓ＝ｓ＊（１），．．．，２ｍ−Ｊ＋ｓ＊（Ｊ）−１において、オクターブｊ＝Ｊ１，．．．，Ｊ２に対する計算が実施される。ここでＪ１＝ｍｉｎ｛ｓ＊（ｊ）≦ｓ＜ｓ＊（ｊ）＋２ｍ−ＪとなるようなＪ｝、そしてＪ１＝ｍａｘ｛ｓ＊（ｊ）≦ｓ＜ｓ＊（ｊ）＋２ｍ−ＪとなるようなＪ｝である。次の擬似コードは本発明において提案されるアーキテクチャの範囲内で実施されるパイプライン型のＤＷＴの実現を示す。
【００３７】
アルゴリズム３
１．ｓ＝０，．．．，２ｍ−Ｊ−１について、ｘ（０，ｓ）ＬＰ＝ｘ（ｓ・２Ｊ：（ｓ＋１）・２Ｊ−１）を設定
２．ｓ＝ｓ＊（１），．．．，２ｍ−Ｊ＋ｓ＊（Ｊ）−１
ｊ＝Ｊ１，．．．，Ｊ２について、並列に以下を実行
開始
２．１．（４）に従ってｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））を設定
２．２．［（ｘ（ｊ，ｓ−ｓ＊（ｊ））ＬＰ）Ｔ，（ｘ（ｊ，ｓ−ｓ＊（ｊ））ＨＰ）Ｔ］Ｔ＝Ｄ＾ｊ・ｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））（０：２Ｊ−ｊ＋１＋Ｌ＋３）を計算
終了
【００３８】
３．出力ベクトル形成
【００３９】
【数８】
2005500595.tif 000010
【００４０】
本発明においては、タイプ１およびタイプ２のコアＤＷＴアーキテクチャと呼ばれる２つのタイプのＤＷＴアーキテクチャの一般的なパラメトリック構造が導入され、それ以外に、コアＤＷＴアーキテクチャのいずれかに基づいて、複数コアＤＷＴアーキテクチャ、および可変分解能ＤＷＴアーキテクチャとそれぞれ呼ばれる２つの他のＤＷＴアーキテクチャの一般的なパラメトリック構造が導入される。
【００４１】
すべてのアーキテクチャは可変レベルの並列性で実施することができ、従って、速度とハードウェアの複雑度との間のトレードオフが可能である。並列性のレベルに依存して、一定時間の実施（タイム・ユニットごとに１つの２ｍ点のＤＷＴ）までのスループットを得ることができる。並列性のすべてのレベルにおいて、このアーキテクチャは約１００％のハードウェア利用率で動作し、従って、直列のＤＷＴ実施に比較して並列性のレベルに関してほとんど線形のスピードアップが得られる。このアーキテクチャはＤＷＴのパラメータには比較的依存しない。すなわち、提案のアーキテクチャの１つを備えているデバイスは１つのＤＷＴだけでなく、異なるフィルタ長のある範囲の異なるＤＷＴを効率的に実施することができ、そして可変分解能ＤＷＴアーキテクチャの場合において、任意の長さのベクトル上での異なる数の分解レベルで効率的に実施することができる。
【００４２】
提案のアーキテクチャの多くの異なる実現が可能である。従って、それらの一般的な構造が機能レベルで説明される。レジスタ・レベルでの一般的な構造の実現の例も示される。これらの実現はこの一般的な構造の妥当性を示す。提案のアーキテクチャは機能的技術レベルに関して既知のアーキテクチャとは本質的に異なっている。提案の各アーキテクチャのより詳しい要約が次に示される。［３４］において発表されているＦＰＰおよびＬＰＰのアーキテクチャはタイプ１（複数コアおよび単一コア）ＤＷＴアーキテクチャの特定の実現とみなすことができることは留意されるべきである。
【００４３】
タイプ１およびタイプ２のコアＤＷＴアーキテクチャは、所与の数Ｌｍａｘを超えない長さＬの低域および高域フィルタに基づいてＪ≦ｍオクターブでの２ｍ点のＤＷＴを実施する。ここで、ＪおよびＬｍａｘ（ｍまたはＬではなく）は、その実現のパラメータである。タイプ１およびタイプ２のコアＤＷＴアーキテクチャは両方とも直列または並列のデータ入力ブロックおよびＪ個のパイプライン段を含み、ｊ番目の段（ｊ＝１，．．．，Ｊ）は１つのデータ・ルーティング・ブロックおよび２Ｊ−ｊ個の処理要素（ＰＥ）から構成されている。これは図４に関連して説明される。このアーキテクチャのｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ）は、ｊ番目のＤＷＴオクターブの２ｍ−ｊ個の独立の同様な演算を２ｍ−Ｊ個の演算ステップで実施する。すべてのステップにおいて、２Ｊ−ｊ個の演算のグループがそのパイプライン段の２Ｊ−ｊ個のＰＥ内で並列に実施される。ＰＥはその入力の数ｐ≦Ｌｍａｘによって規定される可変レベルの並列性で実施することができる。
【００４４】
ｐ個の入力を備えた１つのＰＥは、１つの基本ＤＷＴ演算（図２（ｂ）参照）を、［Ｌ／ｐ］のタイム・ユニットから構成されている１つの演算ステップにおいて実施し、ここですべてのタイム・ユニットにおいて、２ｐ個の乗算および加算の結果が並列に得られる。従って、その時間周期（連続している入力ベクトルがこのアーキテクチャに入る時のタイム・ユニット間の時間間隔で測定される）は、２ｍ−Ｊ［Ｌ／ｐ］のタイム・ユニットに等しく、ここでそのタイム・ユニットの持続時間は１つの乗算演算の期間に等しい。これは以前に知られているアーキテクチャ［１２−２６］の最善の期間より２Ｊ／［Ｌ／ｐ］倍早く、［３０］において記述されているアーキテクチャより２Ｊ−１／［Ｌ／ｐ］倍早い。両方のアーキテクチャの効率（すなわち、ハードウェアの利用率）はＬ／（ｐ［Ｌ／ｐ］）・１００％＝１００％に等しい。ｐ＝Ｌ＝Ｌｍａｘの場合、その時間周期は２ｍ−Ｊタイム・ユニットであり、それは［３４］および［３５］に示されているＬＰＰアーキテクチャの場合と同じであるが、フィルタの長さに依存する（すなわち、ＬＰＰアーキテクチャは固定長ＬのフィルタでＤＷＴを実施することができるだけである）。この２つのタイプのコアＤＷＴアーキテクチャは、１つのパイプライン段のＰＥ間の相互接続の不在（タイプ１）または存在（タイプ２）に従って異なっている。この２つのタイプのコアＤＷＴアーキテクチャの可能な実現が図５乃至１０に示されている。上記２種類のコアＤＷＴアーキテクチャは、パラメータｐに依存して可変の度合いの並列性で実施することができる。
【００４５】
並列性のレベルにおける更なる柔軟性が、新しいパラメータｒ＝１，．．．，２ｍ−Ｊを導入することによって複数コアＤＷＴアーキテクチャ内で得られる。複数コアＤＷＴアーキテクチャは、実際には、対応している「単一」コアＤＷＴアーキテクチャからそれをｒ回拡張することによって得られる。その一般的構造が図１１に示されている。そのアーキテクチャは直列または並列のデータ入力ブロックおよびＪ個のパイプライン段から構成され、そのｊ番目（ｊ＝１，．．．，Ｊ）のパイプライン段は、１つのデータ・ルーティング・ブロックおよびｒ２Ｊ−ｊ個のＰＥから構成されている。複数コアＤＷＴアーキテクチャの時間周期は（２ｍ−Ｊ［Ｌ／ｐ］）／ｒタイム・ユニットに等しく、それは単一コアＤＷＴアーキテクチャの時間周期よりｒ倍早い。すなわち、線形のスピードアップが提供される。複数コアＤＷＴアーキテクチャの効率は単一コアアーキテクチャの場合と同じであり、すなわち、約１００％である。ｐ＝Ｌ＝Ｌｍａｘおよびｒ＝２ｍ−Ｊの場合、その周期は２ｍ点のＤＷＴに対して丁度１タイム・ユニットであることに留意されたい。同様な性能が［３４］および［３５］において示されているＦＰＰアーキテクチャにおいて達成され、それは複数コアＤＷＴアーキテクチャの可能な１つの実現の特殊ケース（ｐ＝Ｌ＝Ｌｍａｘおよびｒ＝２ｍ−Ｊ）とみなすことができる。
【００４６】
単一コアおよび複数コアＤＷＴアーキテクチャは、入力の長さおよびフィルタの長さには比較的依存せず、そのことは、任意のフィルタ（長さがＬｍａｘを超えない）に基づいていて、任意の長さの信号に対して適用されるＤＷＴが、タイプ１またはタイプ２のコアＤＷＴアーキテクチャのいずれかを備えている同じデバイスで効率的に実施できることを意味する。しかし、タイプ１、タイプ２および複数コアのアーキテクチャはＤＷＴオクターブＪの数に依存する。それらはオクターブの数がＪより小さいＤＷＴを実施することができるが、ハードウェアの利用率がある程度損なわれる。
【００４７】
可変分解能のＤＷＴアーキテクチャは、任意の数のオクターブＪ’のＤＷＴを実施し、そしてそのアーキテクチャの効率はＪ’が所与の数より大きいか、あるいはそれに等しい時は常に約１００％のままである。可変分解能のＤＷＴアーキテクチャはＪｍｉｎの分解能レベルに対応している１つのコアＤＷＴアーキテクチャと、任意の直列のＤＷＴアーキテクチャ、例えば、ＲＰＡベースのアーキテクチャ（図１２（ａ）参照）とを含む。コアＤＷＴアーキテクチャはＪ’オクターブのＤＷＴの最初のＪｍｉｎ個のオクターブを実施し、そして直列のＤＷＴアーキテクチャはＪ’オクターブのＤＷＴの最後のＪ’−Ｊｍｉｎ個のオクターブを実施する。コアＤＷＴアーキテクチャは可変レベルの並列性で実施できるので、Ｊ‘≧Ｊｍｉｎである時は常に約１００％のハードウェア利用率が得られるように直列のＤＷＴアーキテクチャとバランスを取ることができる。
【００４８】
複数コアＤＷＴアーキテクチャに基づいた可変分解能ＤＷＴアーキテクチャも構築することができ（図１２（ｂ）参照）、その場合、１つのデータ・ルーティング・ブロックが複数コアＤＷＴアーキテクチャと直列のＤＷＴアーキテクチャとの間に挿入される。
【００４９】
提案のＤＷＴアーキテクチャ
本節では、タイプ１およびタイプ２のコアＤＷＴアーキテクチャと呼ばれる２種類のＤＷＴアーキテクチャ、およびそれ以外に、いずれかのＤＷＴアーキテクチャに基づいて構築され、複数コアＤＷＴアーキテクチャおよび可変分解能ＤＷＴアーキテクチャとそれぞれ呼ばれている２つの他のＤＷＴアーキテクチャの一般的構造を示す。複数コアＤＷＴアーキテクチャはコアＤＷＴアーキテクチャのいずれか１つの拡張であり、これはパラメータｒに依存して可変レベルの並列性で実施することができ、そして１つの特定のケース（ｒ＝１）においては、単一コアＤＷＴアーキテクチャとなる。理解し易くするために、このアーキテクチャのプレゼンテーションは、単一コアＤＷＴアーキテクチャの説明から開始される。
【００５０】
両方のタイプのコアＤＷＴアーキテクチャは、与えられた数値Ｌｍａｘを超えない長さＬの低域および高域フィルタに基づいてＪの分解レベル（オクターブ）で任意の離散ウェーブレット変換を実施する。それらの演算は前に示されたアルゴリズム３に基づいている。両方のタイプのコアＤＷＴアーキテクチャを表している一般的構造が図４に示されており、ここで点線は接続を表し、それは特定の実現に依存して存在する場合もあり存在しない場合もある。接続はタイプ１には存在しないが、タイプ２には存在する。両方の場合、そのアーキテクチャは１つのデータ入力ブロックとＪ個のパイプライン段とから構成され、各段が１つのデータ・ルーティング・ブロックとプロセッサ要素（ＰＥ）のブロックとを含んでいて、データ入力ブロックはアルゴリズム３のステップ１を実施し、データ・ルーティング・ブロックはステップ２．１を担当し、ＰＥのブロックはステップ２．２を計算するためにある。２つのコア・アーキテクチャのタイプは同じパイプライン段のＰＥ間のデータ交換の可能性によって主として区別される。タイプ２のコアＤＷＴアーキテクチャにおいては、１つの段のＰＥが相互接続を経由して中間のデータを交換することができ、一方、タイプ１のコアＤＷＴアーキテクチャにおいては、１つのパイプライン段内のＰＥ間には相互接続がなく、従って、１つの段のＰＥはそれぞれの演算中にデータを交換しない。
【００５１】
一般に、データ・ルーティング・ブロックおよびＰＥのブロックの多くの異なる実現が可能である。従って、１つの態様においては、本発明はブロック・レベルにおいて示されているようなアーキテクチャ（図４、図１１、および図１２）、およびＰＡおよびデータ・ルーティング・ブロックに対して選定された正確な実施とは独立に、機能レベルにおいて以下に説明されるようなアーキテクチャの中に存在することができる。しかし、より高いレベルにおける提案のコアＤＷＴアーキテクチャの実際的ないくつかの実現が図５乃至１０を参照して、例示の方法によって示されている。これらの例示としての実施は本発明の妥当性を示している。
【００５２】
図４はタイプ１およびタイプ２のコアＤＷＴアーキテクチャの一般的構造を示している。前に説明されたように、タイプ１とタイプ２は段内のＰＥ間の相互接続が存在するかしないかにおいてのみ異なっている。両方のコアＤＷＴアーキテクチャのデータ入力ブロックはワード直列またはワード並列のいずれかとして実現することができる。前者の場合、そのデータ入力ブロックは１つ（ワード直列）の入力ポートから構成され、それは各セルからのワード並列の出力を備えている長さ２Ｊのシフト・レジスタ（図４の点線のブロック）に対して接続されている。後者の場合、データ入力ブロックは２Ｊ個の並列入力ポートを含む。両方の場合、データ入力ブロックは２Ｊ個の並列の出力を備え、それらは第１のパイプライン段のデータ・ルーティング・ブロックの２Ｊ個の入力に接続されている。図６において、ワード並列のデータ入力ブロックの一例が示されており、一方、図７および図１０はワード直列のデータ入力ブロックの例を示している。
【００５３】
タイプ１のコアＤＷＴアーキテクチャ
タイプ１のコアＤＷＴアーキテクチャ内に実施されている基本アルゴリズムは特定の順序の実施ステップ２．２によるアルゴリズム３である。２Ｊ−ｊ＋１×２Ｊ−ｊ＋１個の行列Ｄ＾ｊの構造はステップ２．２の行列ベクトル乗算を、次のようにベクトル間の内積の計算の２Ｊ−ｊ個のペアに分解することができるようになっている。
ｘ（ｊ，ｓ−ｓ＊（ｊ））（ｉ）＝ＬＰ・ｘ＾（ｊ−１，（ｓ−ｓ＊（ｊ）））（２ｉ：２ｉ＋Ｌ−１）
ｘ（ｊ，ｓ−ｓ＊（ｊ））（ｉ＋２Ｊ−ｊ）＝ＨＰ・ｘ＾（ｊ−１，（ｓ−ｓ＊（ｊ）））（２ｉ：２ｉ＋Ｌ−１）
ｉ＝０，．．．，２Ｊ−ｊ−１
これは並列に実施することができる。
【００５４】
他方、長さＬのすべてのベクトル間の内積は、長さｐのＬｐ＝［Ｌ／ｐ］の内積のシーケンスに分解することができ、その結果が累積される（係数ベクトルおよび入力ベクトルが任意の数のゼロを伴って付加され、連続したｐ個の構成要素のサブベクトルに分解されると仮定して）。結果として、アルゴリズム３は前の擬似コードに対して次の変更を行うことによって示すことができる。
【００５５】
アルゴリズム３．１
１．ｓ＝０，．．．，２ｍ−Ｊ−１について、ｘ（０，ｓ）ＬＰ＝ｘ（ｓ・２Ｊ：（ｓ＋１）・２Ｊ−１）を設定
２．ｓ＝ｓ＊（１），．．．，２ｍ−Ｊ＋ｓ＊（Ｊ）−１
ｊ＝Ｊ１，．．．，Ｊ２について、以下を並列に実行
開始
２．１．（４）に従ってｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））を設定
２．２．ｉ＝０，．．．，２Ｊ−ｊ−１について、以下を並列に実行
開始
ＳＬＰ（ｉ）＝０，ＳＨＰ（ｉ）＝０を設定
ｎ＝０，．．．，ＬＰ−１について、以下をシーケンシャルに実行
開始
【００５６】
【数９】
2005500595.tif 000011
【００５７】
【数１０】
2005500595.tif 000012
終了
ｘ（ｊ，ｓ−ｓ＊（ｊ））ＬＰ（ｉ）＝ＳＬＰ（ｉ）；
ｘ（ｊ，ｓ−ｓ＊（ｊ））ＨＰ（ｉ）＝ＳＨＰ（ｉ）を設定
終了
終了
【００５８】
３．出力ベクトル形成
【００５９】
【数１１】
2005500595.tif 000013
【００６０】
ｓおよびｊが与えられて、演算（６）および（７）のグループはｎ＝０に対するサブベクトルｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））（０：２Ｊ−ｊ＋１＋ｐ−３）、サブベクトルｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））（ｐ：２Ｊ−ｊ＋１＋２ｐ−３）、および一般に、ｎ＝０，．．．，Ｌｐ−１に対するサブベクトルｘ＾（ｊ−１，ｓｊ，ｎ）＝ｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））（ｎｐ：２Ｊ−ｊ＋１＋（ｎ＋１）ｐ−３）を含む。言い換えれば、ｎ＝０，．．．，Ｌｐ−１に対する計算はベクトルｘ＾（ｊ−１，ｓｊ，ｎ）の最初の２Ｊ−ｊ＋１＋ｐ−２個の構成要素を含み、それはベクトルｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））をｎｐポジションだけその構成要素を左にシフトすることによって得られることに留意されたい。また、所与のｉ＝０，．．．，２Ｊ−ｊ−１に対する計算は常に現在のベクトルｘ＾（ｊ−１，ｓｊ，ｎ）の構成要素２ｉ，２ｉ＋１，．．．，２ｉ＋ｐ−１を常に含むことにも留意されたい。
【００６１】
タイプ１のコアＤＷＴアーキテクチャの一般的構造が図４に示されている。このアーキテクチャの場合、１つの段のＰＥ間に接続がないので、点線を無視することができる。このアーキテクチャは１つのデータ入力ブロック（既に上で説明された）とＪ個のパイプライン段とから構成されている。一般に、タイプ１のコアＤＷＴアーキテクチャのｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ）は、その段に対する入力を形成している２Ｊ−ｊ＋１個の入力ＩＰＳ（ｊ）（０），．．．，ＩＰＳ（ｊ）（２Ｊ−ｊ＋１−１）および２Ｊ−ｊ個のＰＥの入力に接続される２Ｊ−ｊ＋１＋ｐ−２個の出力ＯＤＲＢ（ｊ）（０），．．．，ＯＤＲＢ（ｊ）（２Ｊ−ｊ＋１＋ｐ−３）を備えているデータ・ルーティング・ブロックを含む。すべてのＰＥはｐ個の入力と２つの出力を備え、ここで、ｐ≦ＬｍａｘはすべてのＰＥの並列性のレベルを記述している実現のパラメータである。Ｊ番目（ｊ＝１，．．．，Ｊ）の段のデータ・ルーティング・ブロックの連続したｐ個の出力ＯＤＲＢ（ｊ）（２ｉ），ＯＤＲＢ（ｊ）（２ｉ＋１），．．．，ＯＤＲＢ（ｊ）（２ｉ＋ｐ−１）が同じ段のｉ番目（ｉ＝０，．．．，２Ｊ−ｊ−１）のＰＥ（ＰＥｊ，ｉ）のｐ個の入力に接続されている。ｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ−１）の２Ｊ−ｊ個の各ＰＥの第１の出力がその段の出力ＯＰＳ（ｊ）（０），．．．，ＯＰＳ（ｊ）（２Ｊ−ｊ−１）を形成し、次の（ｊ＋１）番目の段のデータ・ルーティング・ブロックの２Ｊ−ｊ個の入力ＩＰＳ（ｊ＋１）（０），．．．，ＩＰＳ（ｊ＋１）（２Ｊ−ｊ−１）に接続されている。最後のＪ番目の段の（１つの）ＰＥの第１の出力がこのアーキテクチャのゼロ番目の出力ｏｕｔ（０）である。ｊ番目（ｊ＝１，．．．，Ｊ）のパイプライン段の２Ｊ−ｊ個のＰＥの第２の出力が、このアーキテクチャの（２Ｊ−ｊ）番目から（２Ｊ−ｊ＋１−１）番目までの出力ｏｕｔ（２Ｊ−ｊ），．．．，ｏｕｔ（２Ｊ−ｊ＋１−１）を形成する。
【００６２】
タイプ１のコアＤＷＴアーキテクチャのブロックがここで機能レベルで記述される。便宜上、タイム・ユニットはＰＥが１つの演算を完了するための時間周期（ＰＥに入って来るｐ個のデータの連続したグループ間の期間に等しい）と定義され、このアーキテクチャの１つの演算ステップはＬｐ個のタイム・ユニットを含んでいると定義される。
データ入力ブロックは入力ベクトルの構成要素のグループを、演算ステップあたり２Ｊ構成要素のレートで直列に、あるいは並列に受け入れて並列に出力する。従って、ベクトルｘ（０，ｓ）ＬＰはステップｓ＝０，．．．，２ｍ−Ｊ−１においてデータ入力ブロックの出力において形成される。
【００６３】
（段ｊ＝１，．．．，Ｊの）データ・ルーティング・ブロックは、一般に、任意の回路として実現することができ、それはすべての演算ステップの最初のタイム・ユニットｎ＝０において２Ｊ−ｊ＋１個の構成要素のベクトルを並列に受け入れ、次にその演算ステップのすべてのタイム・ユニットｎ＝０，．．．，Ｌｐ−１においてベクトルの２Ｊ−ｊ＋１＋ｐ−２個の構成要素ｎｐ，ｎｐ＋１，．．．，（ｎ＋１）ｐ＋２Ｊ−ｊ＋１−３を並列に出力する。そのベクトルは前のＱ＾ｊステップにおいて受け入れられたベクトルの連結（時間的順序での）であり、ここで、Ｑ＾ｊは下式で表される。
【００６４】
【数１２】
2005500595.tif 000014
【００６５】
タイプ１のコアＤＷＴアーキテクチャにおいて使用されるＰＥの機能は、そのｐ個の入力におけるベクトルと所定の係数の２つのベクトルとの２つの内積を計算すること、および計算された両方の内積の結果を１つの演算ステップの間に累積する（別々に）ことである。すべての演算ステップの終りにおいて、２つの累積された結果がＰＥの２つの出力に渡され、そして新しい累積が開始される。明らかに、すべてのＰＥはその正しい引数がそれぞれの入力において形成された場合、一対の演算（６）および（７）を実施する。
【００６６】
ここで、このアーキテクチャはアルゴリズム３．１に従って計算を実施することが示される。Ｌ＜Ｌｍａｘの場合、余分の遅延が導入される。その余分の遅延は任意のフィルタ長Ｌ≦ＬｍａｘでＤＷＴを実施することができるこのアーキテクチャの柔軟性の結果（コスト）である。これは固定のフィルタ長ＬでＤＷＴの計算を提示するアルゴリズム３．１と比較される必要がある。実際に、このアーキテクチャはフィルタ長Ｌｍａｘに対して設計されている。しかし、遅延時間が僅かに増加するが、時間周期における増加がない、より短いフィルタでＤＷＴを実施することも行う。
次のように定義する。
【００６７】
【数１３】
2005500595.tif 000015
【００６８】
このアーキテクチャの動作時に、ベクトルｘ（０，ｓ）ＬＰがステップｓ＝０，．．．，２ｍ−ｊ−１においてデータ入力ブロックの出力において形成され、これが第１のパイプライン段のデータ・ルーティング・ブロックの入力に入る。このアーキテクチャがアルゴリズム３．１に従って計算を実施することを示すためには、ｊ番目の段のＰＥの第１の出力（それは（ｊ＋１）番目の段の入力に接続されている）においてベクトルｘ（ｊ，ｓ―ｓ＾（ｊ））ＬＰが形成され、そしてベクトルｘ（ｊ−１，ｓ―ｓ＾（ｊ−１））ＬＰがステップｓ＝ｓ＾（ｊ−１），．．．，ｓ＾（ｊ−１）＋２ｍ−Ｊ−１においてｊ番目の段に入る場合にベクトルｘ（ｊ，ｓ―ｓ＾（ｊ））ＨＰがステップｓ＝ｓ＾（ｊ），．．．，ｓ＾（ｊ）＋２ｍ−Ｊ−１においてそれぞれの第２の出力において形成されることを示すだけで十分である（数学的帰納法による証明）。従って、段ｊ＝１，．．．，Ｊのデータ・ルーティング・ブロックはベクトルｘ（ｊ−１，ｓ―ｓ＾（ｊ−１））ＬＰをステップｓ＝ｓ＾（ｊ−１），．．．，ｓ＾（ｊ−１）＋２ｍ−Ｊ−１において受け入れると仮定される。次に、データ・ルーティング・ブロックの機能的記述に従って、次のベクトルの構成要素ｎｐ，ｎｐ＋１，．．．，（ｎ＋１）ｐ＋２Ｊ−ｊ＋１−３がすべてのステップｓ＝ｓ＾（ｊ），．．．，ｓ＾（ｊ）＋２ｍ−Ｊ−１のタイム・ユニットｎ＝０，．．．，Ｌｐ−１においてデータ・ルーティング・ブロックの出力において形成される。それはそれぞれステップｓ−Ｑ＾ｊ，ｓ−Ｑ＾ｊ＋２，．．．，ｓにおいて受け入れられたベクトルの連結である。
【００６９】
【数１４】
2005500595.tif 000016
【００７０】
ｓ＾（ｊ）≧ｓ＊（ｊ）（（３）および（９）を比較）なので、ベクトルｘ＾（ｊ−１，ｓ―ｓ＾（ｊ））（式（４）に従って定義された）はｘ〜（ｊ−１，ｓ―ｓ＾（ｊ））のサブベクトルであり、従って、それぞれの最初の２Ｊ−ｊ＋１＋Ｌ−３個の構成要素は正確に同じである。従って、ベクトルｘ＾（ｊ−１，ｓｊ，ｎ）＝ｘ＾（ｊ−１，ｓ―ｓ＾（ｊ））（ｎｐ：２Ｊ−ｊ＋１＋（ｎ＋１）ｐ−３）がステップｓ＝ｓ＾（ｊ），．．．，ｓ＾（ｊ）＋２ｍ−Ｊ−１のタイム・ユニットｎ＝０，．．．，Ｌｐ−１において段ｊ＝１，．．．，Ｊのデータ・ルーティング・ブロックの出力において形成される。データ・ルーティング・ブロックとＰＥとの間の接続のために、ベクトルｘ＾（ｊ−１，ｓｊ，ｎ）の構成要素２ｉ，２ｉ＋１，．．．，２ｉ＋ｐ−１（それらは実際には、演算（６）および（７）の引数である）が、ＰＥｊ，ｉ（ｉ＝０，．．．，２Ｊ−ｊ−１）の入力において、ステップｓ＝ｓ＾（ｊ），．．．，ｓ＾（ｊ）＋２ｍ−Ｊ−１のタイム・ユニットｎ＝０，．．．，Ｌｐ−１において形成される。従って、ＰＥは対応している係数に従ってそれぞれの演算を実施し、ベクトルｘ（ｊ，ｓ−ｓ＾（ｊ））ＬＰがそのＰＥの第１の出力において形成され、ベクトルｘ（ｊ，ｓ−ｓ＾（ｊ））ＨＰがステップｓ＝ｓ＾（ｊ），．．．，ｓ＾（ｊ）＋２ｍ−Ｊ−１の後でそれぞれの第２の出力において形成される。ＰＥの第１の出力は次のパイプライン段の入力に接続されているので、これはこのアーキテクチャがたとえ異なるタイミングにおいてでも（アルゴリズム３．１内のすべての場所のｓ＊（ｊ）をｓ＾（ｊ）で置き換える）、アルゴリズム３．１に従って計算を実施することを証拠立てる。
【００７１】
上記考察から、２ｍ個の点のＤＷＴが、それぞれがＬｐのタイム・ユニットから構成されている２ｍ−Ｊ＋ｓ＾（Ｊ）ステップにおいてタイプ１のコアＤＷＴアーキテクチャで実施されることは明らかである。従って、入力ベクトルと対応している出力ベクトルとの間の遅延時間は次のタイム・ユニット数に等しい。
【００７２】
【数１５】
2005500595.tif 000017
【００７３】
明らかに、このアーキテクチャは入力ベクトルのストリームのＤＷＴを実施することができる。従って、スループットまたは時間周期（連続している入力ベクトルがこのアーキテクチャに入る時のタイム・ユニット間の時間間隔として測定される）は、次のタイム・ユニット数に等しい。
【００７４】
【数１６】
2005500595.tif 000018
【００７５】
並列／パイプライン型アーキテクチャの性能は次のように定義されるハードウェア利用率、すなわち、効率に関して評価されることが多い。
【００７６】
【数１７】
2005500595.tif 000019
【００７７】
ここで、Ｔ（１）は１つのＰＥでのアルゴリズムの実施の時間であり、Ｔ（Ｋ）はＫ個のＰＥを含んでいるアーキテクチャでの同じアルゴリズムの実施の時間である。タイプ１のコアＤＷＴアーキテクチャにおいて使用されるＰＥと同様な１つのＰＥを使用して２ｍ点のＤＷＴを実施するのに必要な時間はＴ（１）＝（２ｍ−１）［Ｌ／ｐ］タイム・ユニットであることが分かる。式（１１）および（１２）を一緒にし、そしてタイプ１のコアＤＷＴアーキテクチャ内に合計Ｋ＝２Ｊ−１個のＰＥがあることを考慮に入れて、このアーキテクチャに対して遅延時間、あるいはさらには、時間周期の複雑性に関しての両方において約１００％の効率（ハードウェア利用率）が得られることを示すことができる。ＦＰＰアーキテクチャの効率に近い効率が、従来の技術から知られている少数のパイプライン型のＤＷＴ設計（［１７］参照）だけで達成され、一方、既知のパイプラインのＤＷＴアーキテクチャは１００％の平均効率よりずっと小さい効率であることに留意されたい。また、少なくともＯ（Ｎ）のタイム・ユニットの時間周期が、既知のＤＷＴアーキテクチャによって必要とされることにも留意されたい。提案のアーキテクチャはパラメータｐによって変わる並列性の可変レベルで実現することができるように、所望の時間周期を達成することができる。
【００７８】
式（１２）から分かるように、この実施の時間周期の複雑性はＴＬ（Ｃ１）＝２ｍ−ＪとＴ１（Ｃ１）＝Ｌ２ｍ−Ｊとの間で変化する。従って、このアーキテクチャのスループットは既知の最高速のアーキテクチャのスループットより２Ｊ／Ｌ乃至２Ｊ倍早い。また、可変レベルの並列性でこのアーキテクチャを実現することができることによって、時間とハードウェアの複雑性とのトレードオフの機会が与えられる。また、このアーキテクチャは非常に規則的であり、例えば、［１７］のアーキテクチャとは違って、単純な制御構造（本質的に、１クロックだけ）を必要とするだけであることにも留意されたい。それはフィードバック、スイッチ、または入力のサイズに依存する長い接続を含まず、長さの最大値がＯ（Ｌ）に過ぎない接続だけを備えている。従って、それはセミシストリック・アレイとして実施することができる。
【００７９】
タイプ１のコアＤＷＴアーキテクチャの可能な実現
タイプ１のコアＤＷＴアーキテクチャに対する、ｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ）の可能な１つの構造が図５に示されている。Ｌｍａｘ＝６、Ｊ＝３の場合に対するそのような実現の２つの例が図６および図７に示されており、それぞれｐ＝Ｌｍａｘ＝６、およびｐ＝２である。ｐ＝Ｌｍａｘに対応しているこの特定の実現の場合、そして特に、図６の例の特定のバージョンの場合が出版物［３４］および［３５］の中で示されていた（そこではそれは制限された並列パイプライン型（ＬＰＰ）アーキテクチャと呼ばれていた）ことに留意されたい。対照的に、タイプ１のコアＤＷＴアーキテクチャおよびその図５における実現は、任意のｐの場合に対するものである。さらに、ドキュメント［３４］および［３５］の中で記述されているＬＰＰアーキテクチャは、フィルタ長がＬｍａｘより小さいＤＷＴの効率的な計算をサポートせず、一方、図５に示されているタイプ１のコアＤＷＴアーキテクチャの実現はそれをサポートすることに留意されたい。
【００８０】
図５を参照して、この実現において、データ・ルーティング・ブロックがそれぞれ２Ｊ−ｊ＋１の遅延時間のＱ＾ｊチェーン接続されたグループと、すべてのタイム・ユニットごとにセル内の値をｐポジションだけ上方にシフトする長さ２Ｊ−ｊ＋１＋Ｌｍａｘ−２のシフト・レジスタとから構成されていることが分かる。その段に対する２Ｊ−ｊ＋１個の入力は、第１のグループの遅延要素に対して並列に接続されており、その出力が次のグループの遅延要素の入力に接続されている。以下同様に接続されている。遅延要素の各グループの出力はシフト・レジスタの２Ｊ−ｊ＋１個の連続したセルに対して並列に接続されている。遅延要素の最後のＱ＾ｊ番目のグループの出力は最初の２Ｊ−ｊ＋１個のセルに接続されており、遅延要素の（Ｑ＾ｊ−１）番目のグループの出力は次の２Ｊ−ｊ＋１個のセルに接続されており、以下同様に接続されている。ただし、その段の第１のｑｊ＝（Ｌｍａｘ−２）−（Ｑ＾ｊ−１）２Ｊ−ｊ＋１入力はシフト・レジスタの最後のｑｊ個のセルに対して直接に接続されている。
【００８１】
シフト・レジスタの最初の２Ｊ−ｊ＋１＋ｐ−２個のセルの出力はデータ・ルーティング・ブロックの出力を形成し、そしてＰＥの入力に対して接続されている。ｐ＝Ｌｍａｘの場合（図６参照）、シフト・レジスタは不要であるが、遅延要素のグループの出力およびその段の最初のｑｊ個の入力がＰＥの入力に直接に接続されている。他方、ｐ＝２の場合（図７参照）、データ・ルーティング・ブロックとＰＥとの間の相互接続が単純化される。何故なら、この場合、シフト・レジスタの第１のセルからＰＥの入力に２Ｊ−ｊ＋１個の並列の接続だけがあるからである。タイプ１のコアＤＷＴアーキテクチャのデータ・ルーティング・ブロックに対して提示された実現が機能的に制約を満足することはこの分野の技術において普通の技能を有する人には明らかである。実際には、すべてのステップの開始時に、シフト・レジスタは、第１のＬｍａｘ−２個の構成要素のベクトルについて次の受け入れられたベクトルからＱ＾ｊステップだけ以前に受け入れられたデータのベクトルの連結を含む。従って、Ｌｐタイム・ユニットの間に、それは毎時ｐポジションだけ上方にその構成要素をシフトする。
【００８２】
タイプ１のコアＤＷＴアーキテクチャに対するＰＥの可能な構造が、任意のｐ、ｐ＝１、ｐ＝２、およびｐ＝Ｌｍａｘの場合に対して図８に示されている（図８の（ａ）、（ｂ）、（ｃ）、および（ｄ）のそれぞれ）。再び、これらの構造は式（６）および（７）の演算を実施し、従って、ＰＥの機能的記述を満足することは、この分野の通常の技能を有する人にとって明らかである。また再び、これらの構造はフィルタ係数とは独立に一般的なＤＷＴ実施に対して適しており、この特定のフィルタ係数に対して最適化されたＰＥの構造を実施できることにも留意されたい。
【００８３】
タイプ２のコアＤＷＴアーキテクチャ
タイプ２のコアＤＷＴアーキテクチャは僅かに変更されたバージョンのアルゴリズム３．１を実施する。その変更は演算（６）および（７）のオペランドがインデックスｉおよびｎのペア（ｉ１，ｎ１）および（ｉ２，ｎ２）に対して同じであり、２ｉ１＋ｎ１ｐ＝２ｉ２＋ｎ２ｐであることの観察に基づいている。偶数のｐを仮定して（奇数の場合は同様に扱われるが、その表示のためにより多くの表記を必要とする）、このことは、式（６）および（７）の演算を実施する時、ブランチｉ＝０，．．．，２Ｊ−ｊ−ｐ／２−１内のタイム・ユニットｎ＝１，．．．，Ｌｐ−１において使用するために必要な被乗数が、ブランチｉ＋ｐ／２内のステップｎ−１において得られた被乗数から得られることを意味する。対応している計算プロセスが次の擬似コードで記述される。ここで次のように定義する。
【００８４】
【数１８】
2005500595.tif 000020
【００８５】
アルゴリズム３．２
１．ｓ＝０，．．．，２ｍ−Ｊ−１について、ｘ（０，ｓ）ＬＰ＝ｘ（ｓ・２Ｊ：（ｓ＋１）・２Ｊ−１）を設定
２．ｓ＝ｓ＊（１），．．．，２ｍ−Ｊ＋ｓ＊（Ｊ）−１
ｊ＝Ｊ１，．．．，Ｊ２について、以下を並列に実行
開始
２．１．（４）に従って、ｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））を設定
２．２．ｉ＝０，．．．，２Ｊ−ｊ−１について、以下を並列に実行
開始
ｋ＝０，．．．，ｐ−１について
開始
ｚＬＰ（ｉ，０，ｋ）＝ｌｋｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））（２ｉ＋ｋ）；
ｚＨＰ（ｉ，０，ｋ）＝ｈｋｘ＾（ｊ−１，ｓ−ｓ＊（ｊ））（２ｉ＋ｋ）を設定
【００８６】
【数１９】
2005500595.tif 000021
【００８７】
を計算
終了
ｎ＝１，．．．，Ｌｐ−１について、次をシーケンシャルに実行
開始
ｋ＝０，．．．，ｐ−１
開始
【００８８】
【数２０】
2005500595.tif 000022
を設定
【００８９】
【数２１】
2005500595.tif 000023
を設定
終了
【００９０】
【数２２】
2005500595.tif 000024
を計算
終了
ｘ（ｊ，ｓ−ｓ＊（ｊ））ＬＰ（ｉ）＝ＳＬＰ（ｉ）；
ｘ（ｊ，ｓ−ｓ＊（ｊ））ＨＰ（ｉ）＝ＳＨＰ（ｉ）を設定
終了
【００９１】
３．  出力ベクトル形成
【００９２】
【数２３】
2005500595.tif 000025
【００９３】
タイプ２のコアＤＷＴアーキテクチャの一般的構造が図４に示されている。この場合、同じパイプライン段に属しているＰＥ間の接続（点線）は有効である。図４から分かるように、タイプ２のコアＤＷＴアーキテクチャはタイプ１のコアＤＷＴアーキテクチャに似ているが、この場合は、ｐ個の入力および２つの出力（これ以降ではメイン入力およびメイン出力と呼ばれる）を除いて、すべてのＰＥは１つの追加のｐ個の入力およびｐ個の出力（これ以降では中間入力および中間出力と呼ばれる）を備えている。ＰＥｊ，ｉ＋ｐ／２のｐ個の中間出力はＰＥｊ，ｉ（ｉ＝０，．．．，２Ｊ−１−ｐ／２−１）のｐ個の中間入力に接続されている。タイプ２のコアＤＷＴアーキテクチャ内の他の接続は、タイプ１のコアＤＷＴアーキテクチャ内のそれらと似ている。
【００９４】
タイプ２のコアＤＷＴアーキテクチャのブロックの機能は、タイプ１のコアＤＷＴアーキテクチャのそれらと実質的に似ている。データ入力ブロックの機能はタイプ２のコアＤＷＴアーキテクチャの場合と正確に同じである。
データ・ルーティング・ブロック（段ｊ＝１，．．．，Ｊの）は一般に、任意の回路として実現することができ、その回路はすべての演算ステップの最初のタイム・ユニットｎ＝０において、２Ｊ−ｊ＋１個の構成要素のベクトルを並列に受け付け、そして１つのベクトルの最初の２Ｊ−ｊ＋１＋ｐ−２個の構成要素０，１，．．．，２Ｊ−ｊ＋１＋ｐ−３のベクトルを並列に出力し、そのベクトルは前のＱ＾ｊステップにおいて受け入れられたベクトルの連結（時間的順序での）であり、ここで、Ｑ＾ｊは式（８）において定義されている。次に、その演算ステップのすべてのタイム・ユニットｎ＝０，．．．，Ｌｐ−１において、データ・ルーティング・ブロックはその最後のｐ個の出力上に同じベクトルのｐ個の構成要素２Ｊ−ｊ＋１＋ｎｐ−２，．．．，２Ｊ−ｊ＋１＋（ｎ＋１）ｐ−３の次のサブベクトルを並列に出力する。
【００９５】
すべての演算ステップのすべてのタイム・ユニットｎ＝０，．．．，Ｌｐ−１においてタイプ２のコアＤＷＴアーキテクチャにおいて使用されるＰＥの機能は、長さｐの所定の係数、ＬＰ’およびＨＰ’の２つのベクトルとそのｐ個のメインまたはｐ個の中間入力のいずれの上に存在するベクトルｘとの２つの内積を計算すること、およびそれ以外にｘとＬＰ’とのポイントごとの積を計算することである。タイム・ユニットｎ＝０において、ベクトルｘはＰＥのメインのｐ個の入力を使用して形成され、タイム・ユニットｎ＝１，．．．，Ｌｐ−１において、ベクトルｘはＰＥの中間入力を使用して形成される。１つの演算ステップの間に計算された両方の内積の結果が累積され、ＰＥの２つのメイン出力に渡され、一方、ポイントごとの積はＰＥの中間出力に渡される。
【００９６】
タイプ１のコアＤＷＴアーキテクチャの場合と同様に、タイプ２のコアＤＷＴアーキテクチャは式（１１）および（１２）によって与えられる時間遅延および時間周期の特性を伴ってアルゴリズム３．２を実施する。タイプ１およびタイプ２のアーキテクチャの他の特性も同様に似ている。特に、タイプ２のアーキテクチャは非常に高速であり、セミシストリック・アーキテクチャとして、そして可変レベルの並列性で実施することができ、時間とハードウェアの複雑性との間のトレードオフを生成するための機会を提供する。これら２つのアーキテクチャの間の違いは、タイプ１のコアＤＷＴアーキテクチャ内のデータ・ルーティング・ブロックのシフト・レジスタが、タイプ２のコアＤＷＴアーキテクチャ内ではＰＥ間の追加の接続で置き換えられていることである。
【００９７】
タイプ２のコアＤＷＴアーキテクチャの１つの可能な実現
タイプ２のコアＤＷＴアーキテクチャに対するｊ番目（ｊ＝１，．．．，Ｊ）のパイプライン段の１つの可能な構造が図９に示されている。Ｌｍａｘ＝６、Ｊ＝３およびｐ＝２の場合に対するそのような実現の一例が図１０（ａ）に示されている。この実現においては、データ・ルーティング・ブロックは２Ｊ−ｊ＋１個の各遅延要素がチェーン接続されているＱｊ個のグループ、およびすべてのタイム・ユニットにおいて値をｐポジションだけ上方にシフトする長さＬｍａｘ−２のシフト・レジスタから構成されている。その段に対する２Ｊ−ｊ＋１個の入力は遅延要素の第１のグループに対して並列に接続され、その出力は次の遅延要素のグループの入力に接続されている。以下同様である。遅延要素の最後のＱ＾ｊ番目のグループの出力はデータ・ルーティング・ブロックの最初の２Ｊ−ｊ＋１個の出力を形成し、ＰＥのメイン入力に接続されている。遅延要素（ｔ＝１，．．．，Ｑ＾ｊ−１）の（Ｑ＾ｊ−ｔ）番目のグループの出力はシフト・レジスタの２Ｊ−ｊ＋１個の連続したセルに並列に接続されている。遅延要素の（Ｑ＾ｊ−１）番目のグループの出力は最初の２Ｊ−ｊ＋１個のセルに接続され、遅延要素の（Ｑ＾ｊ−２）番目のグループの出力は次の２Ｊ−ｊ＋１個のセルに接続されている。以下同様である。しかし、その段の最初のｑｊ＝（Ｌｍａｘ−２）−（Ｑｊ−１）２Ｊ−ｊ＋１個の入力は、シフト・レジスタの最後のｑｊ個のセルに直接接続されている。
【００９８】
シフト・レジスタの最初のｐ−２個のセルからの出力はデータ・ルーティング・ブロックの最後のｐ−２個の出力を形成し、一般的な構造内の接続に従ってＰＥのメイン入力に接続されている。提示された実現はタイプ２のコアＤＷＴアーキテクチャのデータ・ルーティング・ブロックに対する機能的制約を満足することを示すことができる。実際に、すべてのステップの初めにおいて、以前のＱ＾ｊ項のステップにおいて受け入れられたベクトルの連結（期間的順序での）であるベクトルの最初の２Ｊ−ｊ＋１＋ｐ−２個の構成要素が、データ・ルーティング・ブロックの出力において形成され、次に、すべての次のタイム・ユニットの間に、そのベクトルの次のｐ個の構成要素がその最後のｐ個の出力において形成される。
【００９９】
ｐ＝２の場合に対するタイプ２のコアＤＷＴアーキテクチャのための１つの可能なＰＥ構造が図１０（ｂ）に示されている。この分野の技術に通常の技能を有する人にとっては、任意のｐおよびｐ＝１、ｐ＝２、およびｐ＝Ｌｍａｘに対する構造を、図８（ａ）、（ｂ）、（ｃ）、および（ｄ）に示されているものと同様に設計できることは明らかである。
ｐ＝Ｌｍａｘの場合、タイプ２のコアＤＷＴアーキテクチャのこの実現は図６に示されているタイプ１のコアＤＷＴアーキテクチャの実現と同じであることに留意されたい。
【０１００】
複数コアＤＷＴアーキテクチャ
上記２つのタイプのコアＤＷＴアーキテクチャは、パラメータｐによって変わる可変レベルの並列性で実施することができる。新しいパラメータｒ＝１，．．．，２ｍ−Ｊを導入することによって、複数コアＤＷＴアーキテクチャ内で並列性のレベルにおける更なる柔軟性が得られる。複数コアＤＷＴアーキテクチャは、対応している単一コアＤＷＴアーキテクチャからそれをｒ倍拡張することによって実際に得られる。その一般的な構造が図１１に示されている。その構造は１つのデータ入力ブロックおよびＪ個のパイプライン段から構成され、各段は１つのデータ・ルーティング・ブロックおよびＰＥのブロックを含んでいる。
【０１０１】
データ入力ブロックはワード直列として、あるいはワード並列として、コアＤＷＴアーキテクチャの場合と同様に実現することができるが、この場合、それはｒ２Ｊ個の並列の出力を備え、それは第１のパイプライン段のデータ・ルーティング・ブロックのｒ２Ｊ個の入力に接続されている。データ入力ブロックの機能は入力ベクトルの構成要素のグループを演算ステップあたりｒ２Ｊ個の構成要素のレートで並列に受け入れて並列に出力することである。
【０１０２】
先ず最初に、タイプ１の複数コアＤＷＴアーキテクチャを考える。この場合、ｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ）は、その段に対する入力を形成しているｒ２Ｊ−ｊ＋１個の入力ＩＰＳ（ｊ）（０），．．．，ＩＰＳ（ｊ）（ｒ２Ｊ−ｊ＋１−１）を備えている１つのデータ・ルーティング・ブロック、およびｒ２Ｊ−ｊ個のＰＥの入力に接続されているｒ２Ｊ−ｊ＋１＋ｐ−２個の出力ＯＤＲＢ（ｊ）（０），．．．，ＯＤＲＢ（ｊ）（ｒ２Ｊ−ｊ＋１＋ｐ−３）から構成されている。すべてのＰＥはｐ個の入力および２つの出力を備え、ここで、ｐ≦ＬｍａｘはすべてのＰＥの並列性のレベルを記述している実現のパラメータである。ｊ番目（ｊ＝１，．．．，Ｊ）の段のデータ・ルーティング・ブロックの連続したｐ個の出力ＯＤＲＢ（ｊ）（２ｉ），ＯＤＲＢ（ｊ）（２ｉ＋１），．．．，ＯＤＲＢ（ｊ）（２ｉ＋ｐ−１）は、同じ段のｉ番目（ｉ＝０，．．．，ｒ２Ｊ−ｊ−１）のＰＥ（ＰＥｊ，ｉ）のｐ個の入力に接続されている。ｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ−１）のｒ２Ｊ−ｊ個のＰＥの第１の出力は、その段の出力ＯＰＳ（ｊ）（０），．．．，ＯＰＳ（ｊ）（ｒ２Ｊ−ｊ−１）を形成し、そして次の（ｊ＋１）番目の段のデータ・ルーティング・ブロックのｒ２Ｊ−ｊ個の入力ＩＰＳ（ｊ＋１）（０），．．．，ＩＰＳ（ｊ＋１）（ｒ２Ｊ−ｊ−１）に接続されている。最後のＪ番目の段のｒ個のＰＥの第１の出力は、そのアーキテクチャの第１のｒ個の出力ｏｕｔ（０），．．．，ｏｕｔ（ｒ−１）を形成する。ｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ）のｒ２Ｊ−ｊ個のＰＥの第２の出力は、そのアーキテクチャの（ｒ２Ｊ−ｊ）番目から（ｒ２Ｊ−ｊ＋１−１）番目までの出力ｏｕｔ（ｒ２Ｊ−ｊ），．．．，ｏｕｔ（ｒ２Ｊ−ｊ＋１−１）を形成する。
【０１０３】
データ・ルーティング・ブロック（段ｊ＝１，．．．，Ｊの）は、一般に、任意の回路として実現され、その回路はすべての演算ステップの最初のタイム・ユニットｎ＝０においてｒ２Ｊ−ｊ＋１個の構成要素のベクトルを並列に受け入れ、次に、その演算ステップのすべてのタイム・ユニットｎ＝０，．．．，Ｌｐ−１において、以前のＱ＾ｊ個のステップ（（８）参照）において受け入れられたベクトルの連結（時間的順序での）であるベクトルのｒ２Ｊ−ｊ＋１＋ｐ−２個の構成要素ｎｐ，ｎｐ＋１，．．．，（ｎ＋１）ｐ＋ｒ２Ｊ−ｊ＋１−３のベクトルを並列に出力する。ＰＥの機能はタイプ１のコアＤＷＴアーキテクチャの場合と全く同じである。
【０１０４】
ここでタイプ２の複数コアＤＷＴアーキテクチャを考える。そのデータ入力ブロックはタイプ１の複数コアＤＷＴアーキテクチャの場合と全く同じである。タイプ２の複数コアＤＷＴアーキテクチャおよびそれらの間の相互接続において使用されているＰＥは、タイプ２の単一コアＤＷＴアーキテクチャの場合に類似している。その違いは、このアーキテクチャのｊ番目のパイプライン段（ｊ＝１，．．．，Ｊ）内にはｒ２Ｊ−ｊ（２Ｊ−ｊではなく）個のＰＥがあることである。この場合のデータ・ルーティング・ブロックはタイプ１の複数コアＤＷＴアーキテクチャの場合のようにＰＥに対する同様な接続によるｒ２Ｊ−ｊ＋１個の入力およびｒ２Ｊ−ｊ＋１＋ｐ−２個の出力を備えている。データ・ルーティング・ブロック（段ｊ＝１，．．，Ｊの）は、一般に、任意の回路として実現することができ、その回路はすべての演算ステップの最初のタイム・ユニットｎ＝０においてｒ２Ｊ−ｊ＋１個の構成要素のベクトルを並列に受け入れ、そして以前のＱ＾ｊ個のステップにおいて受け入れられたベクトルの連結（時間的順序での）であるベクトルの最初のｒ２Ｊ−ｊ＋１＋ｐ−２個の構成要素０，１，．．．，ｒ２Ｊ−ｊ＋１＋ｐ−３のベクトルを並列に出力する。次に、その演算ステップのすべてのタイム・ユニットｎ＝０，．．．，Ｌｐ−１において、同じベクトルのｐ個の構成要素ｒ２Ｊ−ｊ＋１＋ｎｐ−２，．．，ｒ２Ｊ−ｊ＋１＋（ｎ＋１）ｐ−３の次のサブベクトルをその最後のｐ個の出力において並列に出力する。
【０１０５】
両方のタイプの複数コアＤＷＴアーキテクチャは、単一コアＤＷＴアーキテクチャよりｒ倍早い。すなわち、パラメータｒに関して線形のスピードアップが得られる。入力ベクトルと対応している出力ベクトルとの間の遅延は、タイム・ユニットの単位で次の値に等しく、
【０１０６】
【数２４】
2005500595.tif 000026
そのスループットまたは時間周期はタイム・ユニットの単位で次の値に等しい。
【０１０７】
【数２５】
2005500595.tif 000027
【０１０８】
従って、時間とハードウェアの複雑性との間のトレードオフのための更なるスピードアップおよび柔軟性が、複数コアＤＷＴアーキテクチャにおいて得られる。さらに、これらのアーキテクチャはモジュール型であり、規則正しく、そしてセミシストリック・アレイとして実施することができる。
ｐ＝Ｌ＝Ｌｍａｘおよびｒ＝２ｍ−Ｊの場合に対する複数コアＤＷＴアーキテクチャの１つの可能な実現として、ノード（四角形）がＰＥを表し、小さい円がラッチを表しているＤＷＴの流れ図そのもの（図２参照）を考えることができる。この実現は［３４］において示されたものであり、完全並列パイプライン型（ＦＰＰ）アーキテクチャと呼ばれていた。しかし、それは本発明に従って提案される複数コアＤＷＴアーキテクチャの１つの特定の実現に過ぎない。
【０１０９】
可変分解能ＤＷＴアーキテクチャ
上記アーキテクチャはオクターブの数が所与の数Ｊを超えないＤＷＴを実施する。それらはハードウェアの利用率がある程度損なわれるが、オクターブの数がＪより小さいＤＷＴを実施することができる。可変分解能のＤＷＴアーキテクチャは任意の数のオクターブＪ’でＤＷＴを実施し、一方、そのアーキテクチャの効率はＪ’が所与の数Ｊｍｉｎより大きいか、あるいはそれに等しい場合は常にそのアーキテクチャの効率が約１００％のままである。
【０１１０】
可変分解能ＤＷＴアーキテクチャの一般的構造が図１２（ａ）に示されている。それはＪｍｉｎの分解レベルに対応している１つのコアＤＷＴアーキテクチャ、および任意の直列のＤＷＴアーキテクチャ、例えば、ＲＰＡ（［１４］‐［１７］、［１９］‐［２０］、［２２］）に基づいたアーキテクチャから構成されている。そのコアＤＷＴアーキテクチャはＪ’オクターブＤＷＴの最初のＪｍｉｎオクターブを実施する。コアＤＷＴアーキテクチャのｏｕｔ（０）からの低域フィルタの結果が直列のＤＷＴアーキテクチャに渡される。直列のＤＷＴアーキテクチャはＪ’オクターブＤＷＴの最後のＪ’−Ｊｍｉｎオクターブを実施する。コアＤＷＴアーキテクチャは可変レベルの並列性で実施することができるので、Ｊ’≧Ｊｍｉｎである時は常にほぼ１００％のハードウェア利用率が得られるように直列のＤＷＴアーキテクチャとバランスを取ることができる。
【０１１１】
２つの部分間のバランスを達成するために、コアＤＷＴアーキテクチャはＪｍｉｎオクターブのＮ点のＤＷＴを、直列のアーキテクチャが（Ｊ’−Ｊｍｉｎ）オクターブのＭ点のＤＷＴ（Ｍ＝（Ｎ／２Ｊｍｉｎ））を実施するのと同じか、あるいはより速いスループットで実施するように構成されている。文献において見られる直列のアーキテクチャはＭ点のＤＷＴを２Ｍタイム・ユニット（［１４］、［１５］）、あるいはＭタイム・ユニット（［１４］‐［１９］）のいずれかで実施し、それに対応してＬ個または２Ｌ個の基本ユニット（ＢＵ、乗算器‐加算器ペア）を採用している。それらは任意の個数Ｋ≦２ＬのＢＵを含み、Ｍ点のＤＷＴがＭ［２Ｌ／Ｋ］個のタイム・ユニットで実施されるようにスケールダウンすることができる。タイプ１またはタイプ２のコアＤＷＴアーキテクチャは、Ｎ［Ｌ／ｐ］／２Ｊｍｉｎ個のタイム・ユニットにおいてＪｍｉｎオクターブのＮ点のＤＷＴを実施するので、そのバランシングの条件は［Ｌ／ｐ］≦［２Ｌ／Ｋ］となり、それはｐ＝［Ｋ／２］である場合に満足される。この条件で可変分解能ＤＷＴアーキテクチャは合計で次の個数のＢＵから構成され、
Ａ＝２ｐ（２Ｊｍｉｎ−１）＋Ｋ＝（Ｋが偶数の場合）Ｋ２Ｊｍｉｎ、（Ｋが奇数の場合）（Ｋ＋１）２Ｊｍｉｎ−１
タイム・ユニット単位での次の値の時間周期でＪ’オクターブのＮ点のＤＷＴを実施する。
Ｔｄ＝Ｎ［２Ｌ／Ｋ］／２Ｊｍｉｎ
【０１１２】
複数コアＤＷＴアーキテクチャに基づいた可変分解能ＤＷＴアーキテクチャを、複数コアＤＷＴアーキテクチャと直列のＤＷＴアーキテクチャとの間に１つのデータ・ルーティング・ブロックを挿入して構築することもできる（図１２（ｂ）参照）。そのデータ・ルーティング・ブロックの機能は、演算ステップあたりｒ個のサンプルのレートでディジットを並列に受け入れて直列に出力することである。この場合におけるバランシングの条件は、ｒｐ＝［Ｋ／２］であり、その面積時間特性は次のように表される。
Ａ＝２ｐｒ（２Ｊｍｉｎ−１）＋Ｋ＝（Ｋが偶数の場合）Ｋ２Ｊｍｉｎ、（Ｋが奇数の場合）（Ｋ＋１）２Ｊｍｉｎ−１、Ｔｄ＝Ｎ［２Ｌ／Ｋ］／２Ｊｍｉｎ
【０１１３】
図１４において示されている表１は、提案のアーキテクチャといくつかの従来のアーキテクチャとの間で性能を比較している。この表の中で、文献において一般に受け入れられているように、乗算器‐加算器ペア（これらはＤＷＴアーキテクチャにおける基本ユニット（ＢＵ）である）の数は、所与のアーキテクチャの面積を表していると考えられる。そのタイム・ユニットは１つの乗算によって必要とされる時間周期であると取られる。何故なら、これがその臨界のパイプライン段であるからである。表１の最後の７つの行内に示されている、本発明による提案のＤＷＴアーキテクチャの特性は、パラメータ選定のいくつかの例として以外に、任意の実現パラメータＬｍａｘ、ｐおよびｒに対して与えられている。提案のアーキテクチャにおいて使用されているＢＵの数は、図８のＰＥの例（そこではｐ個の入力を有するＰＥが２ｐのＢＵを含んでいる）を仮定して与えられている。しかし、ＰＥをさらに最適化し、より少ない個数のＢＵを含むようにすることができる。
【０１１４】
便宜上、図１５において示されている表２は、ＤＷＴパラメータＪ＝３またはＪ＝４、Ｎ＝１０２４、およびＬ＝９の選定に対する面積‐時間特性の数値例を示している（これは最も広く使用されているＤＷＴ、Ｄａｕｂｅｃｈｉｅｓ９／７ウェーブレットに対応する）。図１６に示されている表３は、Ｊ＝３またはＪ＝４、Ｎ＝１０２４、およびＬ＝５（Ｄａｕｂｅｃｈｉｅｓ５／３ウェーブレット）に対する数値例を示している。この表の中で示されているゲート数は、ＢＵが１６ビットのＢｏｏｔｈの乗算器の後に階層的な３２ビット加算器が続くものから構成されており、従って、合計１９１４個のゲートを含む（［３７］参照）ことを仮定して計算された。図１３は表２からの行のいくつかをグラフィック形式で示している。提案のアーキテクチャに対応しているラインをずっと大きな数の基本ユニットにまで拡張することができることに留意されたい。ただし、これらの示されていないケースは非常に大きなシリコン面積を必要とし、現在の技術水準においては非実際的である可能性がある。
【０１１５】
これらの例示から分かるように、提案のアーキテクチャは従来のアーキテクチャに比べて、程良い面積条件において卓越した時間特性を示す。提案のアーキテクチャの利点はＡＴｐ２基準に関してそれらの性能を考える時に最も高く評価することができる。この基準は高速指向のアーキテクチャの性能を評価するために一般に使用されている。表の最初の行は汎用のＤＳＰアーキテクチャを表していることに留意されたい。次の２つの行の中で示されているアーキテクチャは非パイプライン型または制限された（２段のみ）パイプライン型のいずれかであり、それらは本発明による提案のアーキテクチャと同様に約１００％のハードウェア利用率で動作する。従って、それらの性能は提案のアーキテクチャの性能に「比例している」が、達成できる並列性のレベルにおいてより大きい柔軟性があり、結果として広い範囲の可能な時間および面積の複雑度となる。表の第４行はハードウェアの利用率が悪く、そして結果として性能の悪いＪ段のパイプライン型アーキテクチャを示している。表の第５から第７までの行は以前の刊行物からのアーキテクチャを示しており、それらはＪ段のパイプライン型アーキテクチャであり、１００％のハードウェア利用率および良好な性能を達成するが、本発明による提案のアーキテクチャによって提供されるような柔軟な範囲の面積および時間の複雑度は可能ではない。
【０１１６】
前記において、フィルタ長およびフィルタ係数、入力長、および分解レベルの数などの任意のパラメータのウェーブレット変換を実施することができる「汎用の」ウェーブレット変換器の一般的構造を説明してきた。特定の離散ウェーブレット変換（上記パラメータの特定の組に対応している）に対するアーキテクチャの更なる最適化が、そのアーキテクチャに含まれている処理要素（ＰＥ）の構造を最適化することによって可能である。
【０１１７】
本発明はＣＭＯＳ技術を使用した専用のセミシストリックＶＬＳＩ回路として実施することができる。これはスタンドアローンのデバイスまたは汎用プロセッサに対する組込み型のアクセレレータのいずれかとすることができる。提案のアーキテクチャは各種のレベルの並列性で実施することができ、それによって種々のコストおよび性能が導かれる。所望のレベルの並列性と同様に、実施のモードの選定は応用分野によって変わる。前記において、このアーキテクチャは任意のＤＷＴを実行するための実施のコンテキストにおいて記述された。しかし、それらは特定のタイプのＤＷＴに対して専用であるような方法でさらに最適化および実施することができる。これは、例えば、Ｄａｕｂｅｃｈｉｅｓの５／３または９／７ウェーブレットが基本のＤＷＴとして計画されている、ＪＰＥＧ２０００に関連した用途において望ましい可能性がある。
【０１１８】
これまで本発明の特定の実施および実施形態が説明されてきた。当業者なら、本発明が上記の実施形態の詳細には限定されず、本発明の特性から逸脱することなしに等価な手段を使用して他の実施形態において実施できることは明らかである。本発明の範囲は添付の特許請求の範囲によってのみ制限される。
＜略号＞
ＡＳＩＣ  特定用途向け集積回路
ＣＭＯＳ  相補型金属酸化物シリコン
ＤＳＰ    ディジタル信号プロセッサ
ＤＷＴ    離散ウェーブレット変換
ＦＰＰ    完全並列パイプライン型（ＤＷＴアーキテクチャ）
ＬＰＰ    制限された並列パイプライン型（ＤＷＴアーキテクチャ）
ＰＥ      プロセッサ要素
＜参照文献＞
[1]  S. G. Mallat, "A Theory for Multiresolution Signal Decomposition: The Wavelet Representation," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 2, n. 12, Dec. 1989, pp. 674-693.
[2]  M. Vetterli and J. Kovacevic, Wavelets and Subband Coding, Englewood Cliffs (NJ): Prentice- Hall, 1995.
[3]  1. Daubachies, Ten Lectures on Wavelets, Philadelphia (PA): SIAM, 1992.
[4]  1. Daubechies, "The Wavelet Transform, Time Frequency, Localization and Signal Analysis," IEEE Trans. on Information Theory, vol. 36, n. 5, Sept. 1990, pp. 961-1005.
[5]  G. Beylkin, R. Coifman, and V. Rokhlin, "Wavelet in Numerical Analysis" in Wavelets and their Applications, New York (NY): Jones and Bartlett, 1992, pp. 181-210.
[6]  G. Beylkin, R. Coifman, and V. Rokhlin, Fast Wavelet Transforms and Numerical Algorithms, New Haven (CT): Yale Univ., 1989.
[7]  L. Senhadji, G. Carrault, and J. J. Bellanguer, "Interictal EEG Spike Detection: A New Frame- work Based on The Wavelet Transforms," in Proc. IEEE-SP Int. Symp. Time-Frequency Time- Scale Anal., Philadelphia (PA) Oct 1994, pp. 548-551.
[8]  S. G Mallat, "Multitrequency Channel Decompositions of Images and Wavelet Models," IEEE Trans. On Acoust., Speech, Signal Processing, vol. 37, n. 12,1989, pp. 2091-2110.
[9]  Z. Mou and P. Duhamel,"Short-Length FIR Filters and Their Use in Fast Non Recursive Fil- tering,"IEEE Trans. on Signal Processing, vol. 39, n. 6, Jun. 1991, pp. 1322-1332.
[10]  A. N. Akansu and R. A. Haddad, Multiresolution Signal Decomposition : Transforms, Subbands and Wavelets, New York (NY): Academic, 1992.
[11]  R. Kronland-Martinet, J. Morlet, and A. Grossman, "Analysis of Sound Patterns through Wavelet Transform," Int. Journ. Pattern Recognitiona and Artificial Intell., vol. n.2, 1987, pp. 273-302.
[12]  S. B. Pan, and R. H. Park, "New Systolic Arrays for Computation of the 1-D Discrete Wavelet Transform," Proceedings of the IEEE Internationald Conference on Acoustics, Speech, and Sig- nal Processing, 1997, Vol. 5, 1997, pp. 4113-4116.
[13]  A. B. Premkumar, and A. S. Madhukumar, "An Efficient VLSI Architecture for the Computation of 1-D Discrete Wavelet Transform," Proc. of the IEEE Int. Conf. On Information, Communications and Signal Processing (ICICS'97), Singapore 9-12 September 1997, pp. 1180-1183.
[14] M. Vishwanath, R. M. Owens, and M. J. Irwin, "VLSI Architectures for the Discrete Wavelet Transform," IEEE Trans. on Circ. and Syst. II:Analog and Digital Signal Processing, vol. 42, n. 5, May 1995, pp. 305-316.
[15]  J. Fridman, and S. Manolakos, "Discrete Wavelet Transform: Data Dependence Analysis and Synthesis of Distributed Memory and Control Array Architectures," IEEE Trans. on Signal Processing, vol. 45, n. 5, May 1997, pp. 1291-1308.
[16]  K. K. Parhi, and T. Nishitani,"VLSI Architectures for Discrete Wavelet Transforms," IEEE Trans. on VLSI Systems, vol. 1, n.2, 1993, pp. 191-202.
[17]  T. C. Denk, and K. K. Parhi, "Systolic VLSI Architectures for 1-D Discrete Wavelet Transform,"  Proceedings of the Thirty-Second Asilomar Conference on Signals, Systems & Computers, 1998, vol. 2 pp. 1220-1224.
[18]  G. Knowles, "VLSI Architecture for the Discrete Wavelet Transform," Electronics Letters, vol. 26, n. 15, 1990, pp. 1184-1185.
[19]  C. Chakrabarti and M. Vishwanath, "Efficient Realizations of Discrete and Continuous Wavelet Transforms: From Single Chip Implementations to Mappings on SIMD Array Computers," IEEE Trans. on Signal Processing, vol. 43, n. 3,1995, pp. 759-771.
[20]  C. Chakrabarti, M. Vishwanath, and R. M. Owens, "Architectures for Wavelet Transforms: A Survey," Journal of VLSI Signal Processing, vol. 14, n. 2,1996, pp. 171-192.
[21]  A. Grzeszczak, M. K. Mandal, S. Panchanatan, "VLSI Implementation of Discrete Wavelet Transform," IEEE Trans. on VLSI Systems, vol. 4, n. 4, Dec. 1996, pp. 421-433.
[22]  M. Vishwanath, and R. M. Owens, "A Common Architecture for the DWT and IDWT," Proceedings of IEEE Int. Conf. On Application Specific Systems, Architectures and Processors, 1996, pp. 193-198.
[23]  C. Yu, C. H. Hsieh, and S. J. Chen, "Design and Implementation of a Highly Efficient VLSI Ar- chitecture for Discrete Wavelet Transforms," Proceedings of IEEE Int. Conf. On Custom Integrated Circuits, 1997, pp. 237-240.
[24]  S. B. Syed, M. A. Bayoumi, "A Scalable Architecture for Discrete Wavelet Transform," Proceedings of Computer Architectures for Machine Perception (CAMP '95), 1995, pp. 44-50.
[26]  M. Vishwanath, "The Recursive Pyramid Algorithm for the Discrete Wavelet Tranform," IEEE Transactions on Signal Processing, vol. 42, n. 3,1994, pp. 673-677.
[27]  D. Liu, C. Svensson, "Trading Speed for Low Power by Choice of Supply and Threshold Voltages," IEEE Journal of Solid State Circuits, vol. 28, n. 1, 1993, pp. 10-17.
[28]  H. T. Kung, "Why Systolic Architectures?" IEEE Computer, 1982.
[30]  F. Marino, D. Gevorkian, and J. Astola, "High-Speed/Low-Power 1-D DWT Architectures with high efficiency," in Proceedings of the IEEE International Conference on Circuits and Systems, May 28-31 2000, Geneva, Switzerland, vol. 5, pp. 337-340.
[31]  D. Z. Gevorkian, "Computational Aspects of Discrete Linear Transforms and Rank Order Based Filters", Thesis for the degree of Doctor of Technology, May 1997,214 pages.
[32]  J. T. Astola, S. S. Agaian, and D. Z. Gevorkian, "Parallel Algorithms and Architectures for a Family of Haar-like Transforms," in Proceedings of SPIE's International Symposium on Electronic Imaging: Science and Technology, vol. 2421, Feb, 1995, San Jose, California, USA.
[34]  D. Gevorkian, F. Marino, S. Agaian, and J. Astola, "Flowgraph Representation of Discrete Wavelet Transforms and Wavelet Packets for their Efficient Parallel Implementation," to appear in Proceedings of TICSP Int. Workshop on Spectral Transforms and Logic Design for Future Digital Systems, June 2-3,2000, Tampere, Finland.
[35]  D. Gevorkian, J. Astola, F. Marino, and S. Agaian, "Highly Efficient Fast Architectures for Discrete Wavelet Transforms Based on Their Flowgraph Representation," in Proceedings of the X European Signal Processing Conference, Sept. 4-8,2000, Tampere, Finland.
[36]  http://www. ti. com/sc/docs/products/dsp/c6000/benchmarks/64x. htm#filters
[37]  P. Pirsch, Architectures for Digital Signal Processing, J. Willey & Sons, 1998,419 pages.
【図面の簡単な説明】
【０１１９】
【図１】ほとんどの既知のＤＷＴアーキテクチャがベースにしているＤＷＴのツリー構造の定義／表現を示す。
【図２】本発明において提案されているアーキテクチャがベースにしているＤＷＴの新しい流れ図表現の一例を示す。
【図３】ＤＷＴのコンパクトな形式の流れ図表現の１つの実施形態を示す。
【図４】本発明による２種類のコアＤＷＴアーキテクチャの一般的なアーキテクチャを示す。
【図５】図４のタイプ１のアーキテクチャの１つの段の１つの可能な実施形態を示す。
【図６】ｐ＝Ｌｍａｘ＝６；Ｊ＝３；Ｎ＝２ｍ、ｍ＝３，４，．．．のパラメータに対応している、図５のタイプ１のコアＤＷＴアーキテクチャの１つの実施形態を示す。
【図７】ｐ＝Ｌｍａｘ＝６；Ｊ＝３；Ｎ＝２ｍ、ｍ＝３，４，．．．のパラメータに対応している、図５のタイプ１のコアＤＷＴアーキテクチャのもう１つの実施形態を示す。
【図８】図４のタイプ１のコアＤＷＴアーキテクチャにおいて使用することができる処理要素（ＰＥ）の４つの可能な実施形態を示す。
【図９】図４のタイプ２のコアＤＷＴアーキテクチャの１つの段の１つの可能な実施形態を示す。
【図１０】タイプ２のコアＤＷＴアーキテクチャの可能な実現の１つの実施形態を示す。
【図１１】本発明による複数コアＤＷＴアーキテクチャの一般的アーキテクチャを示す。
【図１２】本発明による可変分解能ＤＷＴアーキテクチャの一般的アーキテクチャを示す。
【図１３】既知のアーキテクチャおよび本発明によるＤＷＴアーキテクチャの遅延時間対基本ユニット（ＢＵ）数のグラフを示す。
【図１４】表１を示す。
【図１５】表２を示す。
【図１６】表３を示す。
【図１】
2005500595.tif 000028
【図２】
2005500595.tif 000029
【図３】
2005500595.tif 000030
【図４ａ】
2005500595.tif 000031
【図４ｂ】
2005500595.tif 000032
【図５】
2005500595.tif 000033
【図６】
2005500595.tif 000034
【図７】
2005500595.tif 000035
【図８ａ】
2005500595.tif 000036
【図８ｂ】
2005500595.tif 000037
【図８ｃ】
2005500595.tif 000038
【図８ｄ】
2005500595.tif 000039
【図９】
2005500595.tif 000040
【図１０ａ】
2005500595.tif 000041
【図１０ｂ】
2005500595.tif 000042
【図１１ａ】
2005500595.tif 000043
【図１１ｂ】
2005500595.tif 000044
【図１２ａ】
2005500595.tif 000045
【図１２ｂ】
2005500595.tif 000046
【図１３】
2005500595.tif 000047
【図１４】
2005500595.tif 000048
【図１５】
2005500595.tif 000049
【図１６】
2005500595.tif 000050
【国際公開パンフレット】
2005500595.tif 000051
2005500595.tif 000052
2005500595.tif 000053
2005500595.tif 000054
2005500595.tif 000055
2005500595.tif 000056
2005500595.tif 000057
2005500595.tif 000058
2005500595.tif 000059
2005500595.tif 000060
2005500595.tif 000061
2005500595.tif 000062
2005500595.tif 000063
2005500595.tif 000064
2005500595.tif 000065
2005500595.tif 000066
2005500595.tif 000067
2005500595.tif 000068
2005500595.tif 000069
2005500595.tif 000070
2005500595.tif 000071
2005500595.tif 000072
2005500595.tif 000073
2005500595.tif 000074
2005500595.tif 000075
2005500595.tif 000076
2005500595.tif 000077
2005500595.tif 000078
2005500595.tif 000079
2005500595.tif 000080
2005500595.tif 000081
2005500595.tif 000082
2005500595.tif 000083
2005500595.tif 000084
2005500595.tif 000085
2005500595.tif 000086
2005500595.tif 000087
2005500595.tif 000088
2005500595.tif 000089
2005500595.tif 000090
2005500595.tif 000091
2005500595.tif 000092
2005500595.tif 000093
2005500595.tif 000094
2005500595.tif 000095
2005500595.tif 000096
2005500595.tif 000097
2005500595.tif 000098
2005500595.tif 000099
2005500595.tif 000100
2005500595.tif 000101
2005500595.tif 000102
2005500595.tif 000103
2005500595.tif 000104
2005500595.tif 000105
2005500595.tif 000106
2005500595.tif 000107
2005500595.tif 000108
2005500595.tif 000109
2005500595.tif 000110
2005500595.tif 000111
2005500595.tif 000112
2005500595.tif 000113
2005500595.tif 000114
2005500595.tif 000115
2005500595.tif 000116
2005500595.tif 000117
2005500595.tif 000118
2005500595.tif 000119
2005500595.tif 000120
2005500595.tif 000121
2005500595.tif 000122
2005500595.tif 000123
2005500595.tif 000124
【国際調査報告】
2005500595.tif 000125
2005500595.tif 000126
2005500595.tif 000127