(57)【特許請求の範囲】
【請求項１】
ロー及びカラムでエンコードされたデータのブロックの変換を決定する装置であって、前記エンコードされたデータのブロックは、ローデータ及びカラムデータとして表わされることができ、各ロー及びカラムは、複数のデータ要素を具備し、前記装置は:
前記エンコードされたデータのブロックを記憶するように構成されたトランスポーズランダムアクセスメモリ（ＲＡＭ）；
前記トランスポーズＲＡＭに接続された少なくとも１の入力レジスタであって、前記少なくとも１の入力レジスタは、前記トランスポーズＲＡＭから前記ブロックのカラムに対応する所定の量のデータ要素を具備するカラムデータを受信するように構成される少なくとも１の入力レジスタ；
前記少なくとも１の入力レジスタに接続された少なくとも１のバタフライプロセッサであって、前記少なくとも１のバタフライプロセッサは、１次のカラムデータを出力するために前記カラムデータから選択された対の前記所定の量のデータ要素について１次元変換の第１の部分を実行するように構成される少なくとも１のバタフライプロセッサ；
前記少なくとも１のバタフライプロセッサに接続された少なくとも１の中間レジスタであって、前記少なくとも１の中間レジスタは、前記１次のカラムデータを一時的に記憶するように構成される少なくとも１の中間レジスタ；
前記少なくとも１の中間レジスタ及び前記少なくとも１のバタフライプロセッサに接続するフィードバックループであって、前記フィードバックループは、イネーブルにされる場合、前記１次のカラムデータの第１の部分に前記１次元変換の第２の部分を実行するために前記少なくとも１の中間レジスタから前記少なくとも１のバタフライプロセッサに前記１次のカラムデータの第１の部分を転送し、前記少なくとも１の中間レジスタは、前記フィードバックループがディスエイブルにされる間、追加の数学演算を実行する前記少なくとも１のバタフライプロセッサに前記１次のカラムデータの第２の部分を転送することなく、保持レジスタに前記１次のカラムデータの第２の部分を転送する、フィードバックループ、
ここで、前記保持レジスタは、前記カラムデータに対する前記１次元変換が終了すると前記トランスポーズＲＡＭに前記カラムデータを与え；
前記少なくとも１の入力レジスタは、前記トランスポーズＲＡＭから前記ブロックのローに対応する所定の量のデータ要素を具備するローデータを受信するようにさらに構成され、前記少なくとも１のバタフライプロセッサは、１次のローデータを出力するために前記ローデータからの選択された対の前記所定の量のデータ要素について１次元変換の一部分を実行するようにさらに構成され、前記少なくとも１の中間レジスタは、前記１次のローデータを一時的に記憶するようにさらに構成され、前記フィードバックループは、イネーブルされる場合、前記１次元変換の追加の部分が前記第１の部分に実行されるように前記少なくとも１のバタフライプロセッサに前記１次のローデータの第１の部分を転送し、前記少なくとも１の中間レジスタは、前記フィードバックループがディスエーブルにされる間追加の数学演算を実行する前記少なくとも１のバタフライプロセッサに前記１次のローデータの第２の部分を転送することなく、前記保持レジスタに前記１次のローデータの第２の部分を転送し、
前記保持レジスタは、前記ローデータに対する前記１次元変換が終了すると出力レジスタに前記ローデータを与える；
前記フィードバックループに接続された制御シーケンサであって、前記制御シーケンサは、前記フィードバックループをイネーブル若しくはディスエーブルにするように構成され、前記制御シーケンサは、ブロックサイズ割当てに基づいて前記バタフライプロセッサへ前記ブロックの処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにする、制御シーケンサ；
を具備する装置。
【請求項２】
前記フィードバックループは、前記カラムデータ若しくはローデータについて１次元変換が終了するとディスエーブルにされる、請求項１に記載の装置。
【請求項３】
前記フィードバックループ及び前記中間レジスタに接続する少なくとも１の入力マルチプレクサをさらに具備する、ここで、各入力マルチプレクサは、データ要素を一時的に選択するため、及び前記少なくとも１のバタフライプロセッサにデータ要素を転送するように構成される、請求項１に記載の装置。
【請求項４】
前記バタフライプロセッサ及び前記中間レジスタに接続する少なくとも１の出力マルチプレクサをさらに具備する、ここで、各出力マルチプレクサは、データ要素を一時的に選択し、前記少なくとも１の中間レジスタにデータ要素を転送するように構成される、請求項１に記載の装置。
【請求項５】
前記変換は、離散コサイン変換（ＤＣＴ）、差分カッドツリー変換（ＤＱＴ）、逆離散コサイン変換（ＩＤＣＴ）、及び逆差分カッドツリー変換（ＩＤＱＴ）からなるグループから選択される、請求項１に記載の装置。
【請求項６】
前記トランスポーズＲＡＭは、エンコードされたデータの２個のブロックを記憶するように構成可能である、請求項１に記載の装置。
【請求項７】
前記保持レジスタに接続する書き込みマルチプレクサをさらに具備する、ここで、前記書き込みマルチプレクサは、前記１次元変換を終了させるためにデータ要素を再び順番に並べるように構成される、請求項１に記載の装置。
【請求項８】
前記バタフライプロセッサは、ブロックサイズ割当て、変換のタイプ若しくは数学演算のタイプに関係なく変換の少なくとも一部を実行する、請求項１に記載の装置。
【請求項９】
前記制御シーケンサは、前記バタフライプロセッサにスカラーを与える、請求項１に記載の装置。
【請求項１０】
前記スカラーは、ビー・ジー・リーのアルゴリズムに基づいて選択される、請求項９に記載の装置。
【請求項１１】
前記制御シーケンサは、所定の基準に基づいて、前記入力レジスタ、バタフライプロセッサ、中間レジスタ、若しくは出力レジスタのうち特定のものをイネーブルにする、請求項１に記載の装置。
【請求項１２】
前記数学演算は、足し算、掛け算、及び引き算のうちの１つである、請求項１に記載の装置。
【請求項１３】
各バタフライプロセッサは、１次元変換の一部分を実行する、請求項１に記載の装置。
【請求項１４】
前記バタフライプロセッサは、エンコードされたデータのブロックの前記変換を一連の１次元変換として実行する、請求項１に記載の装置。
【請求項１５】
ロー及びカラムでエンコードされたデータのブロックの逆離散コサイン変換を決定するための装置であって、前記エンコードされたデータのブロックは複数のデータ要素を具備し、前記装置は:
前記ブロックのローまたはカラムに対応する所定の量のデータ要素を受信するように構成された入力レジスタ；
前記入力レジスタに接続された少なくとも１のバタフライプロセッサであって、前記少なくとも１のバタフライプロセッサは、処理されたデータ要素を出力するために、選択された対の前記所定の量のデータ要素について前記逆離散コサイン変換の複数の数学演算のうち少なくとも１の数学演算を実行するように構成される、少なくとも１のバタフライプロセッサ；
前記少なくとも１のバタフライプロセッサに接続された少なくとも１の中間レジスタであって、前記少なくとも１の中間レジスタは、前記処理されたデータ要素を一時的に記憶するように構成される、少なくとも１の中間レジスタ；及び
前記少なくとも１の中間レジスタ及び前記少なくとも１のバタフライプロセッサに接続するフィードバックループであって、ここで、前記フィードバックループは、イネーブルにされた場合、前記複数の数学演算の追加の数学演算が第１の部分に実行されるように、前記少なくとも１の中間レジスタから前記少なくとも１のバタフライプロセッサの１つに前記処理されたデータ要素の第１の部分を転送し、前記少なくとも１の中間レジスタは、前記フィードバックループがディスエーブルにされる間、追加の数学演算を実行する前記少なくとも１のバタフライプロセッサに前記処理されたデータ要素の第２の部分を転送することなく、少なくとも１の保持レジスタに前記処理されたデータ要素の第２の部分を転送する、フィードバックループ；
ここで、前記少なくとも１の保持レジスタは、前記データ要素の第１の部分に対する前記追加の数学演算が終了するまで、前記処理されたデータ要素の第２の部分を記憶するように構成される；
前記フィードバックループに接続された制御シーケンサであって、ここで、前記制御シーケンサは、前記フィードバックループをイネーブル若しくはディスエーブルにするように構成され、前記制御シーケンサは、ブロックサイズ割当てに基づいて前記バタフライプロセッサへ前記ブロックの前記処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにする、制御シーケンサ
を具備する装置。
【請求項１６】
ロー及びカラムでエンコードされたデータのブロックの変換を決定する装置であって、前記エンコードされたデータのブロックは、ローデータ及びカラムデータとして表わされることができ、前記ブロックの各ロー及びカラムは、複数のデータ要素を具備する、前記装置は:
前記エンコードされたデータのブロックを記憶するように構成されたトランスポーズランダムアクセスメモリ（ＲＡＭ）；
前記トランスポーズＲＡＭに接続された少なくとも１の入力レジスタであって、前記少なくとも１の入力レジスタは、前記トランスポーズＲＡＭから前記ブロックのカラムに対応する所定の量のデータ要素を具備するカラムデータを受信するように構成される、少なくとも１の入力レジスタ；
前記入力レジスタに接続された少なくとも１のバタフライプロセッサであって、前記少なくとも１のバタフライプロセッサは、１次のカラムデータを出力するために前記カラムデータから選択された対の前記所定の量のデータ要素について１次変換を実行するように構成される、少なくとも１のバタフライプロセッサ；
前記少なくとも１のバタフライプロセッサに接続された少なくとも１の中間レジスタであって、前記少なくとも１の中間レジスタは、前記１次のカラムデータを一時的に記憶するように構成される、少なくとも１の中間レジスタ；
前記少なくとも１の中間レジスタ及び前記少なくとも１のバタフライプロセッサに接続するフィードバックループであって、前記フィードバックループは、イネーブルにされる場合、前記１次元変換の追加の部分が第１の部分に実行されるように、前記少なくとも１の中間レジスタから前記少なくとも１のバタフライプロセッサに前記１次のカラムデータの第１の部分を転送し、前記少なくとも１の中間レジスタは、前記フィードバックループがディスエイブルにされる間、追加の数学演算を実行する前記少なくとも１のバタフライプロセッサに前記１次のカラムデータの第２の部分を転送することなく、保持レジスタに前記１次のカラムデータの第２の部分を転送するフィードバックループ；
ここで、前記保持レジスタは、前記カラムデータに対する前記１次元変換が終了すると前記トランスポーズＲＡＭに前記カラムデータを与える；及び
前記フィードバックループに接続された制御シーケンサであって、前記制御シーケンサは、前記フィードバックループをイネーブル若しくはディスエーブルにするように構成され、前記制御シーケンサは、ブロックサイズ割当てに基づいて前記バタフライプロセッサへ前記ブロックの処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにする、制御シーケンサ、
を具備し、
ここで、前記少なくとも１の入力レジスタは、前記トランスポーズＲＡＭから前記ブロックのローに対応する所定の量のデータ要素を具備するローデータを受信するようにさらに構成され、前記少なくとも１のバタフライプロセッサは、１次のローデータを出力するために前記ローデータから選択された対の前記所定の量のデータ要素について１次元変換の一部分を実行するようにさらに構成され、前記少なくとも１の中間レジスタは、前記１次のローデータを一時的に記憶するようにさらに構成され、前記フィードバックループは、イネーブルにされる場合、前記１次元変換の追加の部分が前記第１の部分に実行されるように、前記少なくとも１のバタフライプロセッサに前記１次のローデータの第１の部分を転送し、前記少なくとも１の中間レジスタは、前記フィードバックループがディスエーブルにされる間、追加の数学演算を実行する前記少なくとも１のバタフライプロセッサに前記１次のローデータの第２の部分を転送することなく、前記保持レジスタに前記１次のローデータの第２の部分を転送し、
ここで、前記保持レジスタは、前記ローデータに対する前記１次元変換が終了すると出力レジスタに前記ローデータを与える、
装置。
【請求項１７】
ロー及びカラムでエンコードされたデータのブロックの変換を決定するための方法であって、前記エンコードされたデータのブロックは、複数のデータ要素を具備し、前記方法は:
（ａ）  入力レジスタにより、前記ブロックのローまたはカラムに対応する所定の量のデータ要素を受信すること、
（ｂ）  処理されたデータ要素の出力を生成するために、上記（ａ）において受信した前記所定の量のデータ要素から選択された対のデータ要素について少なくとも１のバタフライプロセッサにより複数の数学演算のうちの少なくとも１の数学演算を実行すること、
（ｃ）  制御シーケンサにより、上記（ｂ）において処理された対のデータ要素のいずれかが追加の数学演算を必要とするか否かに関する決定をすること、
（ｄ）  第１の部分に前記追加の数学演算を実行するために、フィードバックループを介して前記少なくとも１のバタフライプロセッサにフィードバックとして与えるために、上記（ｃ）において前記追加の数学演算を必要とすることが決定される前記処理されたデータ要素の第１の部分を、前記制御シーケンサにより選択し、前記フィードバックループをイネーブルまたはディスエーブルにする、なお、前記制御シーケンサは、ブロックサイズ割当てに基づいて前記バタフライプロセッサへ前記ブロックの前記処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにすること、
（ｅ）  上記（ｃ）において前記追加の数学演算が必要でないと決定された前記処理されたデータ要素の第２の部分を、前記制御シーケンサにより選択すること、
（ｆ）  処理されたデータ要素の第２の出力を生成するために、前記少なくとも１のバタフライプロセッサにより、上記（ｄ）において選択された対の前記処理されたデータ要素の第１の部分に対して少なくとも１の追加の数学演算を実行することであって、ここで、前記第２の出力は、前記複数の数学演算を終了した前記処理されたデータ要素の前記第１の部分と第２の部分とを含む、実行すること、及び
（ｇ）  上記（ｆ）において前記処理されたデータ要素の第１の部分に実行された前記追加の数学演算が終了するまで、保持レジスタで（ｄ）において選択した前記処理されたデータ要素の第２の部分を記憶すること、
を具備する方法。
【請求項１８】
（ｈ）  必要に応じてステップ（ｃ）、（ｄ）、（ｅ）、（ｆ）及び（ｇ）を繰り返すことをさらに具備する、請求項１７に記載の方法。
【請求項１９】
（ｉ）  前記エンコードされたデータのブロックの前記データ要素の全てが追加の数学演算を必要としない場合、出力レジスタに前記エンコードされたデータのブロックを出力することをさらに具備する、請求項１７に記載の方法。
【請求項２０】
前記変換は、離散コサイン変換（ＤＣＴ）、差分カッドツリー変換（ＤＱＴ）、逆離散コサイン変換（ＩＤＣＴ）、及び逆差分カッドツリー変換（ＩＤＱＴ）からなるグループから選択される、請求項１７に記載の方法。
【請求項２１】
前記エンコードされたデータのブロックは、ローデータ及びカラムデータとして表わすことができる、請求項１７に記載の方法であって、
前記カラムデータが処理されている間、トランスポーズランダムアクセスメモリ（ＲＡＭ）を用いて前記ローデータを記憶すること；及び
前記ローデータが処理されている間、前記トランスポーズランダムアクセスメモリ（ＲＡＭ）を用いて前記カラムデータを記憶すること
をさらに具備する、請求項１７に記載の方法。
【請求項２２】
書き込みマルチプレクサを用いて、前記記憶するステップの前に、データ要素を再び順番に並べることをささらに具備し、その結果、データ要素のその後の配信が効率的な方法で実行される、請求項１７に記載の方法。
【請求項２３】
ブロックサイズ割当てに基づきステップ（ａ）、（ｂ）、（ｃ）、（ｄ）、（ｅ）、（ｆ）、（ｇ）及び（ｈ）を制御することをさらに具備する、請求項１７に記載の方法。
【請求項２４】
ブロックサイズ割当てに基づき特定のデータ要素に適用するために前記バタフライプロセッサにスカラーを与えることをさらに具備する、請求項２３に記載の方法。
【請求項２５】
前記スカラーは、ビー・ジー・リーのアルゴリズムに基づいて選択される、請求項２４に記載の方法。
【請求項２６】
前記数学演算は、足し算、掛け算、及び引き算のうちの１つである、請求項１７に記載の方法。
【請求項２７】
各バタフライプロセッサは、１次元変換の一部分を実行する、請求項１７に記載の方法。
【請求項２８】
前記バタフライプロセッサは、エンコードされたデータのブロックの前記変換を一連の１次元変換として実行する、請求項１７に記載の方法。
【請求項２９】
一方法を実行するためにコンピュータシステムを制御するための命令を包含するコンピュータで読み取り可能な媒体であって、前記方法は:
（ａ）  ロー及びカラムでエンコードされたデータのブロックのローまたはカラムに対応する所定の量のデータ要素を入力レジスタにより受信すること；
（ｂ）  処理されたデータ要素の第１の出力を生成するために、選択された対の前記所定の量のデータ要素について複数の数学演算のうちの少なくとも１の数学演算を少なくとも１のバタフライプロセッサにより実行すること；
（ｃ）  前記処理されたデータ要素のいずれが追加の数学演算を必要とするか否かを制御シーケンサにより決定をすること；
（ｄ）  追加の数学演算を必要とすると決定された処理されたデータ要素の第１の部分を前記制御シーケンサにより選択し、フィードバックループをイネーブル若しくはディスエーブルにすることであって、なお、前記制御シーケンサは、ブロックサイズ割当てに基づいて前記バタフライプロセッサへ前記ブロックの前記処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにする、選択し、イネーブル若しくはディスエーブルにすること；
（ｅ）  追加の数学演算を必要としないと決定された処理されたデータ要素の第２の部分を前記制御シーケンサにより選択すること；
（ｆ）  処理されたデータ要素の第２の出力を生成するために、選択された対の前記処理されたデータ要素の第１の部分について少なくとも１の追加の数学演算を前記少なくとも１のバタフライプロセッサにより実行すること；及び
（ｇ）  前記処理されたデータ要素の第１の部分に実行される前記追加の数学演算が終了するまで、前記処理されたデータ要素の第２の部分を少なくとも１のバタフライプロセッサに記憶すること、
を具備する方法である、コンピュータで読み取り可能な媒体。
【請求項３０】
ロー及びカラムでエンコードされたデータのブロックの変換を決定する装置であって、前記エンコードされたデータのブロックは複数のデータ要素を具備し、前記装置は:
（ａ）  前記ブロックのローまたはカラムに対応する、所定の量のデータ要素を受信するための手段；
（ｂ）  処理されたデータ要素の第１の出力を生成するために、選択された対の前記所定の量のデータ要素について少なくとも１の数学演算を実行するための手段であって、前記少なくとも１の数学演算はバタフライ演算である、実行するための手段；
（ｃ）  前記処理されたデータ要素のいずれが追加の数学演算を必要とするか否かに関する決定をするための手段；
（ｄ）  追加の数学演算を必要とする前記処理されたデータ要素の第１の部分を選択し、フィードバックループをイネーブル若しくはディスエーブルにするための手段であって、前記決定をするための手段は、ブロックサイズ割当てに基づいて前記実行するための手段へ前記ブロックの前記処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにする、選択し、イネーブル若しくはディスエーブルにするための手段；
（ｅ）  追加の数学演算を必要としない前記処理されたデータ要素の第２の部分を選択するための手段；
（ｆ）  処理されたデータ要素の第２の出力を生成するために、フィードバックループを介して選択された対の前記処理されたデータ要素の第１部分について前記少なくとも１の追加の数学演算を実行するための手段；及び
（ｇ）  前記処理されたデータ要素の第１の部分に実行される前記少なくとも１の数学演算が終了するまで、前記処理されたデータ要素の第２の部分を記憶するための手段、を具備する装置。
【請求項３１】
（ｈ）  必要に応じて、構成要素（ｃ）、（ｄ）、（ｅ）、（ｆ）及び（ｇ）によって実行される機能を繰り返すための手段、をさらに具備する、請求項３０に記載の装置。
【請求項３２】
（ｉ）  エンコードされたデータの前記ブロックのデータ要素の全てが、追加の数学演算を必要としない場合、前記エンコードされたデータのブロックを出力するための手段、をさらに具備する、請求項３０に記載の装置。
【請求項３３】
前記変換は、離散コサイン変換（ＤＣＴ）、差分カッドツリー変換（ＤＱＴ）、逆離散コサイン変換（ＩＤＣＴ）、及び逆差分カッドツリー変換（ＩＤＱＴ）からなるグループから選択される、請求項３０に記載の装置。
【請求項３４】
前記エンコードされたデータのブロックは、ローデータ及びカラムデータとして表わすことができる、請求項３０に記載の装置であって、
前記カラムデータが処理されている間、前記ローデータを記憶するための手段；及び
前記ローデータが処理されている間、前記カラムデータを記憶するための手段、をさらに具備する、請求項３０に記載の装置。
【請求項３５】
処理されたデータ要素の前記第２の部分を記憶する前にデータ要素を再び順番に並べるための手段をさらに具備し、その結果、データ要素のその後の配信が効率的な方法で実行される、請求項３０に記載の装置。
【請求項３６】
ブロックサイズ割当てに基づいて構成要素（ａ）、（ｂ）、（ｃ）、（ｄ）、（ｅ）、（ｆ）、（ｇ）、及び（ｈ）を制御するための手段、をさらに具備する、請求項３０に記載の装置。
【請求項３７】
ブロックサイズ割当てに基づいて、特定のデータ要素にスカラーを与えること、をさらに具備する、請求項３６に記載の装置。
【請求項３８】
前記スカラーは、ビー・ジー・リーのアルゴリズムに基づいて選択される、請求項３７に記載の装置。
【請求項３９】
前記数学演算は、足し算、掛け算、及び引き算のうちの１つである、請求項３０に記載の装置。
【請求項４０】
各バタフライプロセッサは、１次元変換の一部分を実行する、請求項３０に記載の装置。
【請求項４１】
エンコードされたデータをピクセルドメインから周波数ドメインへ変換する方法であって、前記エンコードされたデータは複数のデータ要素を具備し、前記方法は:
（ａ）  前記ピクセルドメイン中の前記複数のデータ要素を複数のブロックにグループ分けする、前記複数のブロックの各ブロックは前記ピクセルドメイン中に複数のデータ要素を具備すること；
（ｂ）  処理されたデータ要素の第１の出力を生成するために、上記（ａ）においてグループ分けした前記複数のデータ要素から選択された対のデータ要素に対して少なくとも１のバタフライプロセッサにより複数の数学演算のうち少なくとも１の数学演算を実行すること；
（ｃ）  制御シーケンサにより、上記（ｂ）において処理された前記対のデータ要素のいずれかが追加の数学演算を必要とするか否かに関する決定をすること；
（ｄ）  上記（ｃ）において追加の数学演算を必要とすると決定された前記処理されたデータ要素の第１の部分を、前記制御シーケンサにより選択し、フィードバックループをイネーブル若しくはディスエーブルにする、前記制御シーケンサは、ブロックサイズ割当てに基づいて前記バタフライプロセッサへ前記ブロックの前記処理されたデータ要素の第１の部分を転送するために前記フィードバックループをイネーブルにすること；
（ｅ）  上記（ｃ）において追加の数学演算を必要としないと決定された前記処理されたデータ要素の第２の部分を、前記制御シーケンサにより選択すること；
（ｆ）  処理されたデータ要素の第２の出力を生成するために、上記（ｄ）において選択された、選択した対の処理されたデータ要素の第１部分に対して前記少なくとも１のバタフライプロセッサにより少なくとも１の追加の数学演算を実行することであって、ここで、前記第２の出力は、複数の数学演算を終了した前記処理されたデータ要素の前記第１の部分と前記第２の部分を含む、実行すること；
（ｇ）  上記（ｄ）において選択した前記処理されたデータ要素の前記第１の部分に実行された前記追加の数学演算が終了するまで、保持レジスタで上記（ｅ）において選択した前記処理されたデータ要素の第２の部分を記憶すること；
（ｈ）  前記処理されたデータ要素の全てが追加の数学演算を必要としなくなるまで、及び周波数ドメインデータ要素に変換されるまで、必要に応じて、ステップ（ｃ）、（ｄ）、（ｅ）、（ｆ）及び（ｇ）を繰り返すこと；
（ｉ）  人間の視覚システムにより敏感なそれらのデータ要素を強調するように、及び前記人間の視覚システムに敏感でないそれらのデータ要素を強調しないように、上記（ｈ）において変換された前記周波数ドメインデータ要素をコンタイザーにより量子化すること；
（ｊ）  周波数ドメインデータ要素の順番に並べられたストリームを生成するために上記（ｉ）において変換された、前記量子化された周波数ドメインデータデータ要素をスキャンシリアライザーにより順番に並べること；及び
（ｋ）  連続する周波数ドメインデータ要素及び不連続の周波数ドメインデータ要素を決定するために上記（ｊ）において順番に並べられた前記周波数ドメインデータ要素をコーダによりコーディングすること、
を具備する方法。
【請求項４２】
前記エンコードされたデータのブロックは、ローデータ及びカラムデータとして表わすことができる、請求項４１に記載の方法であって、
前記カラムデータが処理されている間、トランスポーズランダムアクセスメモリ（ＲＡＭ）を用いて前記ローデータを記憶すること；及び
前記ローデータが処理されている間、前記トランスポーズランダムアクセスメモリ（ＲＡＭ）を用いて前記カラムデータを記憶すること、
をさらに具備する、請求項４１に記載の方法。
【請求項４３】
要求される制御信号に基づきステップ（ａ）、（ｂ）、（ｃ）、（ｄ）、（ｅ）、（ｆ）、（ｇ）及び（ｈ）を制御すること、をさらに具備する請求項４１に記載の方法。
【請求項４４】
ブロックサイズ割当てに基づき特定のデータ要素に適用するために前記バタフライプロセッサにスカラーを与えること、をさらに具備する、請求項４３に記載の方法。
【請求項４５】
各バタフライプロセッサは、１次元変換の一部分を実行する、請求項４１に記載の方法。
【請求項４６】
前記バタフライプロセッサは、エンコードされたデータのブロックの前記変換を一連の１次元変換として実行する、請求項４１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、米国特許出願番号Ｎｏ．６０／２９１，４６７、２００１年５月１６日出願、に基づいて優先権を主張するものであり、それは全てここに引用されている。本発明は、デジタル信号処理に係わる。さらに詳しくは、本発明は、エンコードされたデータのブロックの変換を決定するための装置及び方法に係わる。
【背景技術】
【０００２】
デジタル画像処理は、デジタル信号処理の一般的な学術分野において卓越した地位を有する。人間の視覚認識力の重要性は、デジタル画像処理の芸術及び科学において巨大な利益及び発展をもたらしている。フイルムや映画を映写するために使用されるような、ビデオ信号の送信及び受信の技術分野において、各種の改善が画像圧縮技術になされてきている。現在のビデオシステム及び提案されたビデオシステムの多くは、デジタルエンコーディング技術を使用する。この技術分野の態様は、画像コーディング、画像再生、及び画像特徴選択を含む。画像コーディングは、効率的な方法でデジタル通信チャネルの画像を送信するための試みを表わし、必要なバンド幅を最小化するために可能な限り少ないビットを使用する、一方で同時に、ある限度の中に歪を維持する。画像再生は、対象物の実際の画像を再現する取り組みを表わす。通信チャネルを通して送信されるコード化された画像は、各種の要因によって歪められているであろう。劣化の原因は、対象から画像を製作する時に最初に発生するであろう。特徴選択は、画像のある種の特性を選択することをいう。そのような特性は、幅広いコンテクストにおいて認識、分類、及び決定の際に必要とされるであろう。
【０００３】
デジタル映画におけるようなビデオのデジタルエンコーディングは、画像圧縮技術の改善から利益を受ける分野である。デジタル画像圧縮は、２つのカテゴリー、無損失(loss-less)及び損失のある(lossy)方法、に一般に分類される。無損失画像は、情報のいかなる損失なしに再現される。損失のある方法は、圧縮比、圧縮アルゴリズムの品質、及びそのアルゴリズムの実行に依存する、ある情報の再現できない損失を含む。一般に、損失のある圧縮アプローチが、コスト効率のよいデジタル映画のアプローチために望ましい圧縮比を得るために考慮される。デジタル映画の品質レベルを達成するために、圧縮アプローチは、視覚的に無損失の性能を提供すべきである。そのように、圧縮プロセスの結果、情報の数学的な損失があるとはいえ、この損失によって生ずる画像の歪は、通常に見られる状態では視聴者に気付かれないものでなければならない。
【０００４】
現存のデジタル画像圧縮技術は、他のアプリケーションに対して、即ち、テレビジョンシステムに、開発されてきている。そのような技術は、目的のアプリケ-ションに適したように妥協した設計をしており、映画上映に必要な品質要求を満足しない。
【０００５】
デジタル映画圧縮技術は、映画好きの人間が、これまでに見てきた視覚的品質を提供すべきである。理想的には、デジタル映画の視覚的品質は、高品質版のプリント・フイルムの品質を超えるようにすべきである。同時に、圧縮技術は、実際に用いられるようになるために高いコーディング効率を有すべきである。ここで決められたように、コーディング効率は、ある品質的なレベルを満足するために、圧縮された画像品質に必要なビットレートをいう。さらに、そのシステム及びコーディング技術は、異なったフォーマットに適応するために、組み込まれた順応性を持つべきであり、コスト効率的であるべきである。すなわち、小さなサイズにされそして効率的なデコーダプロセス又はエンコーダプロセスである。
【０００６】
品質の要求されたレベルを保ちながら、かなりのレベルの圧縮を提供できる１つの圧縮技術は、エンコードされた離散コサイン変換（ＤＣＴ）係数データの適用できるサイズにされたブロック及びサブブロックを利用する。ＤＣＴ技術は、デジタル圧縮方法として広く受け入れられようとしているが、効率的なハードウェアの実装は、困難であった。
【発明の概要】
【０００７】
本発明は、適応性のあるブロックサイズにされたＤＣＴエンコードされたデータの効率的なハードウェアの実装を提供する。エンコードされたデータのブロックの変換を決定するための装置であり、エンコードされたデータのブロックは、複数のデータ要素を具備する。入力レジスタは、所定の量のデータ要素を受信するように構成される。少なくとも１のバタフライプロセッサは、入力レジスタに接続され、データ要素の選択された対について少なくとも１の数学演算を実行して処理されたデータ要素の出力を生成するように構成される。少なくとも１の中間レジスタは、バタフライプロセッサに接続され、処理されたデータを一時的に記憶するように構成される。フィードバックループは、中間レジスタ及びバタフライプロセッサに接続され、もしイネーブルであるならば、追加の数学演算を実行するために適切なバタフライプロセッサに処理されたデータ要素の第１の部分を送信するように構成される、及び、もしディスエーブルであるならば、少なくとも１の保持レジスタに処理されたデータ要素の第２の部分を送信するように構成される。
【０００８】
したがって、離散コサイン変換（ＤＣＴ）及び離散カッドツリー変換（ＤＱＴ）技術を効率的に実行するプロセッサを提供することが、一実施形態の１つの観点である。
【０００９】
逆離散コサイン変換（ＩＤＣＴ）及び逆離散カッドツリー変換（ＩＤＱＴ）技術を効率的に実行するプロセッサを提供することが、一実施形態の他の１つの観点である。
【００１０】
同一ハードウェア構成要素が、同一の変換トレリス(transform trellis)の中で異なった数学演算を計算するために再構成できる点で柔軟であるプロセッサを提供することが、一実施形態の他の１つの観点である。
【００１１】
画像歪を最小化しつつ、高品質画像を維持する画像プロセッサを提供することが、一実施形態の他の１つの観点である。
【００１２】
エンコードされたデータの部分毎に並列に処理することが、他の観点の一実施形態である。
【００１３】
単一のクロックサイクルの中で、読み出し、書き込み、及びバタフライ演算を処理することが、一実施形態の他の１つの観点である。
【００１４】
異なるブロックサイズのデータを制御すること及びリアルタイム処理のために必要なスピードを維持することの可変性を有する制御シーケンサを提供し、実装することが、一実施形態の他の１つの観点である。
【００１５】
プロセッサが可変ブロックサイズ上で動作するように設定可能であるように、プロセッサを実装することが、一実施形態の他の１つの観点である。
【図面の簡単な説明】
【００１６】
【図１Ａ】データのブロックのカラム処理のブロック図である。
【図１Ｂ】データのブロックのロー処理のブロック図である。
【図２Ａ】エンコーディング処理を通るデータの流れを図示するブロック図である。
【図２Ｂ】デコーディング処理を通るデータの流れを図示するフロー図である。
【図２Ｃ】ブロックサイズ割り当てに基づく変動に含まれた処理ステップを図示するブロック図である。
【図３】本発明を組み込んでいる離散コサイン変換（ＤＣＴ）及び離散カッドツリー変換（ＤＱＴ）のような、変換を計算するための装置を図示するブロック図である。
【図４】図３の装置で実行されるＤＣＴトレリスを示す。
【図５】図３の装置で実行されるＩＤＣＴトレリスを示す。
【図６】入力及び出力マルチプレクサを有する１つのバタフライプロセッサを示す。
【図７】書き込みマルチプレクサのブロック図を示す。
【図８】バタフライプロセッサのブロック図を示す。
【図９Ａ】図８のバタフライプロセッサにより実行される無演算構成を示す。
【図９Ｂ】図８のバタフライプロセッサにより実行される累積演算構成を示す。
【図９Ｃ】図８のバタフライプロセッサにより実行されるバタフライＤＣＴ演算構成を示す。
【図９Ｄ】図８のバタフライプロセッサにより実行されるバタフライＩＤＣＴ演算構成を示す。
【図９Ｅ】図８のバタフライプロセッサにより実行される累積レジスタ演算構成を示す。
【図９Ｆ】図８のバタフライプロセッサにより実行されるＤＣＴ／ＩＤＣＴ演算構成を示す。
【図１０】本発明を組み込んでいる離散コサイン変換（ＤＣＴ）及び離散量子化変換（ＤＱＴ）のような、変換を計算するプロセスを示すフローチャートを示す。
【図１１Ａ】具体例のブロックサイズ割り当てを示す。
【図１１Ｂ】図１１Ａのブロックサイズ割り当てに関する対応するカッドツリー分解を示す。
【図１１Ｃ】図１１Ａのブロックサイズ割り当てに関する対応するＰＱＲデータを示す。
【詳細な説明】
【００１７】
本発明の観点、特徴、目的、及び利点は、図面を使用して以下に述べる詳細な説明から、さらに明確になるであろう。図面では、一貫して対応するものは同じ参照符号で識別する。
【００１８】
デジタル信号のデジタル送信を容易にするため、そして付随する利益を享受するために、ある形式の信号圧縮を採用することが、一般に必要である。結果としての画像で高い鮮明度を達成するために、高品質の画像が維持されることも重要である。さらに、コンピュータ使用上の効率は、コンパクトなハードウェアの実装が好ましく、それは、多くのアプリケーションにおいて重要である。
【００１９】
したがって、フーリエ変換、ウェーブレット(wavelet)、及び離散コサイン変換（ＤＣＴ）のような空間周波数ドメイン技術は、一般に上記の基準を満足する。ＤＣＴは、エネルギーパッキング能力を有し、そして信号のデコリレーティング(decorellating)において統計的に最適な変換をアプローチする。ＤＣＴの効率的な実施に関する種々のアルゴリズムの開発は、その主流の実用性にさらに寄与する。これらのアルゴリズム及びその帰納的な構造の減少と計算機使用上の複雑性は、より単純化されたハードウェアスキームに帰着する。ＤＣＴは、一般に直交し、分離可能である。ＤＣＴが直交するという事実は、信号のエネルギー、すなわち情報、が、変換の下で保存される、すなわち、ＤＣＴドメインにマッピングされる、ことを意味する。ＤＣＴが分離できるという事実は、多次元ＤＣＴが一連の１次元変換により実行できることを意味する。したがって、速いアルゴリズムは、１次元ＤＣＴに対して開発でき、そして多次元変換に直接拡張される。
【００２０】
ＤＣＴにおいて、ピクセルのブロックは、周波数ドメイン中の同じサイズの係数のブロックに変換される。本質的には、変換は、直交基準(orthogonal basis)画像の線形結合としてピクセルのブロックを表わす。係数の大きさは、ピクセルのブロック及び基準画像が同じである範囲を表わす。
【００２１】
一般に、デジタルドメインにおいてこれから処理される画像は、Ｎ×Ｎの大きさの重ならないブロックのアレイに分割されたピクセルデータで構成される。２次元ＤＣＴは、各ブロック上で実行される。２次元ＤＣＴは、次の関係式により定義される：  
【数１】
0005623565.tif 000002
【００２２】
ｘ（ｍ，ｎ）は、Ｎ×Ｍブロック中でのピクセル位置（ｍ，ｎ）、及び
Ｘ（ｋ，ｌ）は、対応するＤＣＴ係数である。
【００２３】
ピクセルの値は負ではないので、ＤＣＴ成分Ｘ（０，０）は、常に正であり、通常最大のエネルギーを有する。事実、代表的な画像に関して、変換エネルギーの大部分は、成分Ｘ（０，０）のまわりに集中する。このエネルギー圧縮特性は、ＤＣＴ技術をそのように魅力的な圧縮方法にする。
【００２４】
大部分の自然の画像は、平面的で比較的ゆっくりと変化する領域及び対象物の境界や高コントラストの構造のような混み入った領域から成り立っている。コントラストに適応性のあるコーディングスキームは、混み入った領域に多くのビットを割り当て、混入ってない領域に少ないビットを割り当てることによってこの要因を利用する。この技術は、米国特許Ｎｏ．５，０２１，８９１、題名“順応性のあるブロックサイズ画像圧縮方法及びシステム”に開示されており、本発明の譲り受け人に譲渡されており、ここに引用例として含まれている。ＤＣＴ技術も米国特許Ｎｏ．５，１０７，３４５、題名“順応性のあるブロックサイズ画像圧縮方法及びシステム”に開示されており、本発明の譲り受け人に譲渡されており、ここに引用例として含まれている。さらに、差分カッドツリー変換(Differential Quadtree Transform)技術と組み合わせてＡＢＳＤＣＴの使用は、米国特許Ｎｏ．５，４５２，１０４、題名“順応性のあるブロックサイズ画像圧縮方法及びシステム”に記載されており、これも本発明の譲り受け人に譲渡されており、ここに引用例として含まれている。これらの特許に開示されたシステムは、“フレーム内”エンコーディングと呼ばれるものを利用する。“フレーム内”エンコーディングでは、画像データの各フレームは、他のいずれかのフレームの内容にかかわらずエンコードされる。ＡＢＳＤＣＴ技術を使用して、達成できるデータレートは、画像品質の識別できる劣化なしに大幅に減少できる。
【００２５】
ＡＢＳＤＣＴを使用して、ビデオ信号は、一般に、処理のためにフレーム及びピクセルのブロックに細分化される。ＤＣＴ演算子は、時間でサンプリングされた信号を同じ信号の周波数表示に変換する１つの方法である。周波数表示に変換することによって、コンタイザー(quantizer)が、画像の周波数分布特性を利用するために設計できるので、ＤＣＴ技術は、非常に高いレベルの圧縮ができるように示されてきている。好ましい実施例では、１個の１６×１６ＤＣＴは、１次オーダリングに適用され、４個の８×８ＤＣＴは、２次オーダリングに適用され、１６個の４×４ＤＣＴは、３次オーダリングに適用され、６４個の２×２ＤＣＴは、４次オーダリングに適用される。
【００２６】
画像処理の目的に対して、ＤＣＴ演算は、重ならないブロックのアレイに分割されるピクセルデータについて実行される。ブロックサイズは、ここではＮ×Ｎの大きさであるとして説明されるが、種々のブロックサイズが使用できることが予想されることに注意する。例えば、Ｎ×Ｍブロックサイズは、ＭがＮよりも大きい若しくは小さい場合のいずれであっても、Ｎ及びＭの両者が整数である場合に利用できる。他の重要な観点は、ブロックが、Ｎ／ｉ×Ｎ／ｉ，Ｎ／ｉ×Ｎ／ｊ，Ｎ／ｉ×Ｍ／ｊ，等、ここで、ｉ及びｊは整数である、のような、少なくとも１のサブブロックに分割できることである。さらに、ここで説明したように、具体例のブロックサイズは、ＤＣＴ係数に対応するブロック及びサブブロックを有する１６×１６ピクセルブロックである。両者が偶数若しくは奇数の整数値である種々の他の整数、例えば、９×９、を使用できることが、さらに予想される。
【００２７】
カラー信号は、ＲＧＢ空間からＹＣ１Ｃ２空間、ここで、Ｙは輝度、すなわち明るさ成分であり、Ｃ１及びＣ２はクロミナンス(chrominance)、すなわち色彩成分である、に変換できる。色彩に対して目の空間感度が低いことのため、多くのシステムは、水平及び垂直方向に因数４でＣ１及びＣ２成分をサブサンプルする。しかしながら、サブサンプリングは、必ずしも必要ではない。４：４：４フォーマットとして知られる、全解像度画像は、デジタル映画を含むような、ある種のアプリケーションにおいて非常に利用価値がある若しくは必要である。２つの可能なＹＣ１Ｃ２の表示、ＹＩＱ表示及びＹＵＶ表示、は、両者ともこの分野ではよく知られている。ＹＣｂＣｒとして知られるＹＵＶ表示の変形を採用することも可能である。
【００２８】
図１Ａ及び図１Ｂは、エンコードされたデータのＮ×Ｎブロックのカラム及びロー処理１００及び１２０を図示する。Ｎ次元変換は、Ｎ個の１次元変換のカスケード(cascade)として実行できる。例えば、１個の２×２ＤＣＴは、２個の１次元ＤＣＴ処理のカスケード、先ず各カラムを演算し、その後各ローを演算する、として実行される。第１カラムｍ（１０４）が処理され、続いてカラムｍ＋１（１０８）、続いてカラムｍ＋２（１１２）等々カラムｎ（１１６）まで処理される。カラムが処理された後で、図１Ｂに示されたように、ロー１２０が処理される。先ず、ローｍ（１２４）が処理され、続いてローｍ＋１（１２８）、続いてローｍ＋２（１３２）等々ローｎ（１３６）まで処理される。
【００２９】
同様に、他の例は、ＩＤＣＴプロセスを必要とするデータの８×８ブロックである。１個の８×８ブロックは、４個の２次元ＩＤＣＴへと分解される。各２次元ＩＤＴＣは、その後、図１Ａ及び図１Ｂについて説明した２次元ＤＣＴについてと同じ方法で処理される。
【００３０】
図２Ａは、エンコーディングプロセスの期間のエンコードされたデータのフローのブロック図２５０を図示する。エンコーディングプロセスでは、エンコードされたデータは、ピクセルドメインから周波数ドメインへと変換される。図２Ｂは、デコーディングプロセスを通してエンコードされたデータの流れのブロック図２５４を図示する。デコーディングプロセスでは、エンコードされたデータは、周波数ドメインからピクセルドメインへと変換される。エンコードプロセス２５０で図示したように、エンコードされたデータのブロックサイズにされた割り当て（ＢＳＡ）が、最初に実行される（２５８）。ある実施例の１つの観点では、Ｙ，Ｃｂ及びＣｒ成分の各々が、サブサンプリングなしに処理される。それゆえ、ピクセルの１個の１６×１６ブロックの入力は、ブロックサイズ割り当て素子２５８へ提供される。ブロックサイズ割り当て素子２５８は、ビデオ圧縮に対する準備の中でブロックサイズ割り当てを実行する。
【００３１】
ブロックサイズ割り当て素子２５８は、ブロック中の画像の視覚的な特性に基づいてブロックのブロック分解を決定する。ブロックサイズ割り当ては、１６×１６ブロック中の活性度によりカッドツリー様式のより小さなブロックへと、各１６×１６ブロックをサブ分割する。ブロックサイズ割り当て素子２５８は、その長さが１及び２１ビットの間であるカッドツリーデータ、ＰＱＲデータと呼ばれる、を生成する。それゆえ、ブロックサイズ割り当てが、１個の１６×１６ブロックがこれから分割されることを決定するならば、ＰＱＲデータのＲビットが設定され、４個の分割された８×８ブロックに対応するＱデータの４個の付加されるビットが続く。ブロックサイズ割り当てが、その８×８ブロックのいずれかが、これからサブ分割されることを決定するならば、その後、サブ分割された各８×８ブロックに対する４個のＰデータの追加ビットが、付加される。
【００３２】
データは、２×２、４×４、８×８、及び１６×１６のようなブロックサイズに分割される。エンコードデータプロセッサは、その後、図３について説明したように、エンコードされたデータ（２６２）の変換（ＤＣＴ／ＤＱＴ）を実行する。ＤＣＴ／ＤＱＴプロセス２６２が終了すると、量子化プロセス（ＱＢ）２６６が、エンコードされたデータに実行される。これで、ピクセルドメインから周波数ドメインへのエンコードされたデータの変換が終了する。
【００３３】
ある実施例では、ＤＣＴ係数は、周波数重み付けマスク(frequency weighting masks)（ＦＷＭｓ）及び量子化スケールファクターを使用して量子化される。ＦＷＭは、入力ＤＣＴ係数のブロックと同じ次元の周波数重み付けの表である。周波数重み付けは、異なるＤＣＴ係数に対して異なる重みを適用する。重みは、人間の視覚システムがより敏感な周波数成分を有する入力サンプルを強調するように作られ、かつ視覚システムが敏感でない周波数成分を有するサンプルを強調しないように作られる。重みは、観賞する距離等のような要因に基づいて作ることもできる。
【００３４】
ハフマンコード(Huffman code)は、観測された若しくは理論的な画像の統計量のいずれかにより作られる。最も自然な画像は、ブランクすなわち比較的ゆっくりと変化する領域、及び対象物の境界や高コントラストの模様のような混み入った領域からなると観察されている。ＤＣＴが混み入った領域に多くのビットを割り当て、ブランク領域に少ないビットを割り当てることによりこれらの特徴を利用するように、周波数ドメインを有するハフマンコードは、変換する。一般に、ハフマンコードは、ラン長さ及び非ゼロ値をコード化するためにルックアップテーブルを使用させる。
【００３５】
重みは、経験的なデータに基づいて選択される。８×８ＤＣＴ係数に対する重みマスクを設計する方法は、ＩＳＯ／ＩＥＣ  ＪＴＣ１  ＣＤ  １０９１８、“連続色調静止画像のデジタル圧縮及びコーディング−パート１：必要条件及びガイドライン”、国際標準協会、１９９４年、に開示されており、これは、引用文献としてここに含まれている。一般に、２個のＦＷＭは、一つは輝度成分に対して、一つはクロミナンス成分に対して作られる。ブロックサイズ２×２、４×４に対するＦＷＭテーブルは、１／１０にすることにより得られ、１６×１６は、８×８ブロックに対するものの補間により得られる。スケールファクターは、品質及び量子化された係数のビットレートを制御する。
【００３６】
それゆえ、各ＤＣＴ係数は、次の関係式にしたがって量子化される：  
【数２】
0005623565.tif 000003
【００３７】
ここで、ＤＣＴ（ｉ，ｊ）は入力ＤＣＴ係数、ｆｗｍ（ｉ，ｊ）は周波数重みマスク、ｑはスケールファクター、及びＤＣＴｑ（ｉ，ｊ）は量子化された係数である。ＤＣＴ係数の符号に依存して、カギカッコ内の第１項は、切り上げ若しくは切り下げられることに注意する。ＤＱＴ係数も、適合する重み付けマスクを使用して量子化される。しかし、複数のテーブル若しくはマスクが使用でき、Ｙ，Ｃｒ，及びＣｒ成分のそれぞれに適用できる。
【００３８】
量子化された係数は、ジグザグスキャンシリアライザー(zigzag scan serializer)２６８に供給される。シリアライザー２６８は、量子化された係数の順番に並べられたストリームを生成するために、ジグザグ様式で量子化された係数のブロックをスキャンする。多くの異なるジグザグにスキャンするパターンも、ジグザグ以外のパターンと同様に選択できる。好ましい技術は、ジグザグスキャニングに８×８ブロックサイズを採用する。しかし、４×４若しくは１６×１６のような他のサイズも採用できる。
【００３９】
ジグザグスキャンシリアライザー２６８は、コンタイザー(quantizer)２６６の前若しくは後のどちらにでも設置できることに注意する。最終的な結果は、同じである。
【００４０】
いずれにせよ、量子化された係数のストリームは、可変長コーダ２６９に供給される。可変長コーダ２６９は、ゼロのラン長エンコーディングを使用させることができ、エンコーディングが続く。この技術は、前述の米国特許Ｎｏ．５，０２１，８９１、５，１０７，３４５及び５，４５２，１０４及び、引用例として取り込まれておりここでまとめられている出願中の米国特許出願Ｎｏ．＜０００１６３＞に詳しく説明されている。ラン長コーダは、量子化された係数を取り、不連続な係数より連続した係数のランに注目する。連続した値は、ラン長さ値として参照され、エンコードされる。不連続な値は、別にエンコードされる。ある実施例では、連続した値は、ゼロ値であり、不連続な値は、非ゼロ値である。代表的には、ラン長さは、０から６３ビットであり、そのサイズは、１−１０からのＡＣ値である。ファイルコードの終わりは、追加コードを付加する−このようにして、合計６４１の可能なコードがある。
【００４１】
デコーディングプロセスでは、周波数ドメイン中のエンコードされたデータは、ピクセルドメインに変換して戻される。可変長デコーダ２７０は、ラン長さ及びデータのサイズを生成し、採用されているスキャンスキームにしたがって係数を順番に並べる逆ジグザグスキャンシリアライザー２７１にデータを供給する。逆ジグザグスキャンシリアライザー２７１は、合成係数ブロック中の係数を適正な順番に並べることを助けるためにＰＱＲデータを受信する。合成ブロックは、周波数重み付けマスクを使用することによって処理を実行しないために、逆コンタイザー２７２に供給される。
【００４２】
フィンガープリンタ（Ｈ２Ｏ）２７３は、その後、エンコードされたデータについて実行される。フィンガープリンタは、データ上にウォーターマーク若しくは他の識別子情報 (identifier information)を設置する。ウォーターマークは、識別子情報を明らかにするために、後の時点で回復される。識別子情報は、どこで及びいつ題材が上演されたか、及び誰がその題材の上演を認めたか、のような情報を含むことができる。フィンガープリンタ２７３に続いて、デコーダデータプロセス２７４（ＩＤＱＴ／ＩＤＣＴ）が、開始される。これは、図４に関係して詳しく説明される。データがデコードされた後で、データは、フレームバッファインターフェース（ＦＢＩ）２７８に送られる。ＦＢＩは、同時に１フレームの圧縮されていないデータを読み出しそして書き込むように構成される。ある実施例では、ＦＢＩは、４フレームの容量を有する。しかしながら、蓄積容量を変えることができることが、予想される。
【００４３】
図２Ｃを参照して、ブロックサイズ割り当て素子２５８の演算の詳細を示すフロー図が与えられる。アルゴリズムは、ブロックをサブ分割するための決定における尺度のように、ブロックの変動を使用する。ステップ２０２から始めて、ピクセルの１個の１６×１６ブロックが読み込まれる。ステップ２０４において、その１６×１６ブロックの変動、ｖ１６、が計算される。変動は、以下のように計算される：  
【数３】
0005623565.tif 000004
【００４４】
ここで、Ｎ＝１６、及びｘｉ，ｊは、Ｎ×Ｎブロック中のｉ番目のロー、ｊ番目のカラムのピクセルである。ステップ２０６において、先ず、ブロックの平均値が２個の所定の値の間にあるならば、変動のしきい値Ｔ１６は、新しいしきい値Ｔ’１６を与えるために修正される。次に、ブロック変動は、新しいしきい値、Ｔ’１６、に対して比較される。
【００４５】
変動ｖ１６が、しきい値Ｔ１６より大きくないならば、その後ステップ２０８において、１６×１６ブロックの開始アドレスが書き込まれ、ＰＱＲデータのＲビットは、１６×１６ブロックがサブ分割できないことを示すために、０に設定される。そして、アルゴリズムは、ピクセルの次の１６×１６ブロックを読み出す。変動ｖ１６が、しきい値Ｔ１６より大きければ、その後ステップ２１０において、ＰＱＲデータのＲビットは、１６×１６ブロックが４個の８×８ブロックにこれからサブ分割されることを示すために、１に設定される。
【００４６】
４個の８×８ブロック、ｉ＝１：４、は、ステップ２１２に示されたように、さらにサブ分割するために続いて考慮される。各８×８ブロックに対して、ステップ２１４において、変動、ｖ８ｉ、が計算される。ステップ２１６において、先ず、ブロックの平均値が、２個の所定の値の間にあるならば、変動しきい値Ｔ８は、修正されて新しいしきい値Ｔ’８を与える。次に、ブロック変動は、この新しいしきい値と比較される。
【００４７】
変動ｖ８ｉが、しきい値Ｔ８より大きくないならば、その後ステップ２１８において、８×８ブロックの開始アドレスが書き込まれ、対応するＱビット、Ｑｉ、は、０に設定される。そして、次の８×８ブロックが処理される。変動ｖ８ｉが、しきい値Ｔ８より大きければ、その後ステップ２２０において、対応するＱビット、Ｑｉ、は、８×８ブロックが４個の４×４ブロックにこれからサブ分割されることを示すために、１に設定される。
【００４８】
４個の４×４ブロック、ｊｉ＝１：４、は、ステップ２２２に示されたように、さらにサブ分割するために引き続いて考慮される。各４×４ブロックに対して、ステップ２２４において、変動、ｖ４ｉｊ、が計算される。ステップ２２６において、先ず、ブロックの平均値が、２個の所定の値の間にあるならば、変動しきい値Ｔ４は、修正されて新しいしきい値Ｔ’４を与える。次に、ブロック変動は、この新しいしきい値と比較される。
【００４９】
変動ｖ４ｉｊが、しきい値Ｔ４より大きくないならば、その後ステップ２２８において、４×４ブロックのアドレスが書き込まれ、対応するＰビット、Ｐｉｊ、は、０に設定される。そして、次の４×４ブロックが処理される。変動ｖ４ｉｊが、しきい値Ｔ４より大きければ、その後ステップ２３０において、対応するＰビット、Ｐｉｊ、は、４×４ブロックが４個の２×２ブロックにこれからサブ分割されることを示すために、１に設定される。さらに、４個の２×２ブロックのアドレスが書き込まれる。
【００５０】
しきい値Ｔ１６，Ｔ８及びＴ４は、所定の定数とすることができる。これは、ハード判断として知られている。あるいは、順応すなわちソフト判断が実行できる。ソフト判断は、２Ｎ×２Ｎブロックの平均ピクセル値、ここで、Ｎは８，４若しくは２とすることができる、に依存する変動に関するしきい値を変化させる。このようにして、平均ピクセル値の関数が、しきい値として使用できる。
【００５１】
説明の目的で、次の例を考える。Ｙ成分に対する所定の変動しきい値を、１６×１６、８×８及び４×４ブロックに対して、それぞれ、５０，１１００及び８８０とする。言い換えると、Ｔ１６＝５０，Ｔ８＝１１００及びＴ１６＝８８０である。平均値の範囲が８０及び１００であるとする。１６×１６ブロックに対する計算された変動が６０であると仮定する。６０及びその平均値９０がＴ１６より大きいので、１６×１６ブロックは、４個の８×８サブブロックにサブ分割される。８×８ブロックに対する計算された変動が、１１８０，９３５，９８０及び１２１０であると仮定する。８×８ブロックの２つがＴ８より大きい変動を有するので、これら２個のブロックは、合計８個の４×４サブブロックを生成するために、さらにサブ分割される。最後に、８個の４×４ブロックの変動は、６２０，６３０，６７０，６１０，５９０，５２５，９３０及び６９０であり、最初の４つに対応する平均値は９０，１２０，１１０，１１５であると仮定する。最初の４×４ブロックの平均値が、範囲（８０，１００）にあるので、そのしきい値は、Ｔ’４＝２００に低くされるであろう。それは８８０より小さい。その結果、この４×４ブロックは、７番目の４×４ブロックと同様にサブ分割されるであろう。結果としてのブロックサイズ割り当ては、図１１Ａに図示される。対応するカッドツリー分解は、図１１Ｂに図示される。このブロックサイズ割り当てにより生成されたＰＱＲデータは、図１１Ｃに図示される。
【００５２】
同様な手順が、色彩成分Ｃ１及びＣ２に対してブロックサイズを割り当てるために使用されることに注意する。色彩成分は、水平方向、垂直方向若しくは両者で１／１０に削減することができる。さらに、ブロックサイズ割り当てが、上から下へのアプローチ、そこでは最大ブロック（この例では１６×１６）が初めに評価される、で説明されてきたが、下から上へのアプローチが、代わりに使用できる。下から上へのアプローチは、最小ブロック（この例では２×２）が最初に評価されるであろう。
【００５３】
選択されたブロックのアドレスとともに、ＰＱＲデータは、ＤＣＴ／ＤＱＴ素子２６２に供給される。ＤＣＴ／ＤＱＴ素子２６２は、選択されたブロックについて適切なサイズの離散コサイン変換を実行するためにＰＱＲデータを使用する。選択されたブロックだけが、ＤＣＴ処理を受けることが必要である。ＤＱＴは、ＤＣＴのＤＣ係数の中にある冗長性を削減するためにも使用される。ＤＣ係数は、各ＤＣＴブロックの上左角にある。ＤＣ係数は、一般に、ＡＣ係数と比較して大きい。サイズの不一致は、効率的な可変長コーダを設計することを困難にする。したがって、ＤＣ係数中の冗長性を削減することは、有利である。ＤＱＴ素子は、ＤＣ係数について、一度に２×２を受け取って、２−Ｄ  ＤＣＴを実行する。４×４ブロック中の２×２ブロックから始めて、２−Ｄ  ＤＣＴは、４個のＤＣ係数について実行される。この２×２ＤＣＴは、４個のＤＣ係数の差分カッドツリー変換、すなわちＤＱＴ、と呼ばれる。次に、１個の８×８ブロックを有する３個の隣接するＤＣ係数とともにＤＱＴのＤＣ係数は、次のレベルのＤＱＴを計算するために使用される。最後に、１個の１６×１６ブロック中の４個の８×８ブロックのＤＣ係数は、ＤＱＴを計算するために使用される。それゆえ、１個の１６×１６ブロックでは、１個の真のＤＣ係数があり、残りはＤＣＴ及びＤＱＴに対応するＡＣ係数である。
【００５４】
１フレームの中で、各１６×１６ブロックは、独立に計算される。したがって、所定のブロックに対して使用される処理アルゴリズムは、ＰＱＲにより決められたように、必要に応じて変更できる。
【００５５】
図３は、エンコードされたデータのブロックのＤＣＴ／ＤＱＴ及びＩＤＱＴ／ＩＤＣＴの計算３００を示すブロック図である。エンコードモードでは、図３に示されたように、エンコードされたデータは、最初はピクセルドメインにある。エンコードされたデータが、中間ステップを経由して処理されるので、エンコードされたデータは、周波数ドメインへと変換される。デコードモードでは、エンコードされたデータは、最初は周波数ドメインにある。エンコードされたデータが、中間ステップを経由して処理されるので、エンコードされたデータは、ピクセルドメインへ変換される。
【００５６】
図３を参照して、エンコードされたデータの少なくとも１のＭ×Ｎブロックは、トランスポーズ(transpose)ＲＡＭ３０４に記憶される。トランスポーズＲＡＭ３０４は、Ｍ×Ｎデータの１又はそれより多くのブロックを含むことができる。エンコードされたデータの２ブロックを有するある実施例では、一方は、現在のデータのＭ×Ｎブロック３０８を含むように構成され、他方は、次のブロックのＭ×Ｎデータ３１２を含むように構成される。データのブロック３０８及び３１２は、（エンコードモードでは）図２Ａに図示されたようにブロックサイズ割り当て２０８から若しくは（デコードモードでは）図２Ｂに図示されたフィンガープリンタ２２０からトランスポーズＲＡＭ３０４へ転送される。ある実施例では、トランスポーズＲＡＭ３０４は、デュアルポートＲＡＭとすることができる。その結果、トランスポーズＲＡＭインターフェース３１６は、現在のデータのブロック３０８を処理し、フィンガープリンタ２２０から次のデータのブロックを受信する。トランスポーズＲＡＭインターフェース３１６は、タイミングを制御し、バッファーされたメモリを有することができ、データのブロックをトランスポーズＲＡＭ３０４から読み出せるようにそして書き込めるようにする。ある実施例では、トランスポーズＲＡＭ３０４及びトランスポーズＲＡＭインターフェース３１６は、制御シーケンサ３２４からの１又はそれより多くの制御信号に応答できる。
【００５７】
エンコードされたデータは、トランスポーズＲＡＭ３０４から（若しくはトランスポーズＲＡＭインターフェース３１６を経由して）１又はそれより多くの入力レジスタ３３２へとデータプロセッサ３２８に入力される。ある実施例では、１６個の入力レジスタ３３２がある。ある実施例では、データプロセッサ３２８は、図１Ａに図示したように、最初にカラムデータを処理し、引き続きローデータを処理する。データプロセッサ３２８は、あるいはローに引き続きカラムを処理することができる。しかし、以下の説明は、カラムデータがローデータより先に処理されると仮定している。入力レジスタ３３２は、１６×１６ブロックの単一のカラムエンコードされたデータを備える。データプロセッサ３２８は、カラム毎にエンコードされたデータの数学演算を実行することにより変換を計算し、トランスポーズＲＡＭ３０４にデータを書き戻す。カラムのデータが処理された後、データプロセッサ３２８は、エンコードされたデータの各ローを処理する。エンコードされたデータの各ローが処理された後、データプロセッサ３２８は、出力レジスタ３５２を経由してデータを出力する。
【００５８】
ある実施例では、データのブロックは、エンコードされたデータの１個の１６×１６ブロックである。しかしながら、３２×３２、８×８、４×４、若しくは２×２、あるいはこれらの組み合わせのような、任意のサイズのデータのブロックが使用できることが予期できる。したがって、データプロセッサ３２８が、トランスポーズＲＡＭ３０４からデータのブロック（例えば、現在のデータのＭ×Ｎブロック３０８）を処理する一方で、トランスポーズＲＡＭインターフェース３１６は、ＢＳＡ２０８から（エンコードモード）若しくはフィンガープリンタ２２０から（デコードモード）次のデータのブロック３１２を受信する。データプロセッサ３２８が、現在のデータのブロックの処理を終了した場合、トランスポーズＲＡＭインターフェース３１６は、トランスポーズＲＡＭ３０４インターフェースから次のデータのブロック３１２を読み出し、データプロセッサ３２８にロードする。このようにして、トランスポーズＲＡＭ３０４からのデータ３１２は、トランスポーズＲＡＭインターフェース３１６及び制御シーケンサ３２４により指示されたように、現在のデータのブロック３０８と次のデータのブロック３１２との間でトグル（toggle）する。
【００５９】
データプロセッサ３２８は、入力レジスタ３３２、マナークバタフライクラスタ３３６内の少なくとも１のバタフライプロセッサ、及び少なくとも１の中間データレジスタ３４８を備える。データプロセッサ３２８は、保持レジスタ３４４、書き込みマルチプレクサ３４８、及び出力データレジスタ３５２も備えることができる。マナークバタフライクラスタ３３６は、第１入力マルチプレクサ３５６をさらに備えることができ、中間データレジスタ３４０は、第２入力マルチプレクサ３６０をさらに備える。前述したデータプロセッサ３２８の構成要素は、好ましくは制御シーケンサ３２４によって制御される。
【００６０】
演算において、所定のカラム若しくはローデータに対して、入力レジスタ３３２は、エンコードされたデータをトランスポーズＲＡＭ３０４からトランスポーズＲＡＭインターフェース３１６を経由して受信するように構成される。制御シーケンサ３２４は、入力レジスタの特定のアドレスをイネーブルにして、入力マルチプレクサ３５６を経由してデータを送る。データ入力は、入力マルチプレクサ３５６を経由した選択によるように再び順番に並べられ、その結果、エンコードされたデータの適切な対が、数学的演算のために選択される。制御シーケンサ３２４によって制御され、入力マルチプレクサ３５６は、マナークバタフライクラスタ３３６にデータを渡す。マナークバタフライクラスタ３３６は、１又はそれより多くのバタフライプロセッサを備える。ある実施例では、マナークバタフライクラスタ３３６は、４個の独立したバタフライプロセッサ３６４，３６８，３７２、及び３７６を備え、制御シーケンサ３２４は、入力マルチプレクサ３５６を経由して適切なバタフライプロセッサへエンコードされたデータを送る。
【００６１】
各個のバタフライプロセッサ３６４，３６８，３７２、及び３７６は、ＤＣＴ，ＩＤＣＴ，ＤＱＴ及びＩＤＱＴのような、１次元変換を実行することができる。１次元変換は、代表的には、単純な加算、減算、若しくは乗算のような、代数演算を含む。１次元変換の一部分が、一対のデータ要素に実行された後、結果の出力は、中間データレジスタ３４０に転送される。中間データレジスタ３４０は、制御シーケンサ３２４に応答できる。制御シーケンサは、ステートマシーン、マイクロコントローラ、若しくはプログラマブルプロセッサのようなデバイスとすることができる。中間データレジスタ３４０が制御シーケンサ３２４に応答するある実施例では、中間データレジスタ３４０に記憶されている選択されたデータ要素は、フィードバックパス３８０を使用してそして第１入力マルチプレクサ３５６を経由して、適切なバタフライプロセッサにフィードバックされ、再び処理（すなわち、他の部分の１個の１次元変換）される。このフィードバックループは、エンコードされたデータに対する１次元処理の全てが終了するまで続く。データの処理が終了すると、中間データレジスタ３４０からのデータは、ＷＲＢＲ保持レジスタ３４４に書き込まれる。処理されるデータがカラムデータであれば、データは、ＷＲＢＲ保持レジスタ３４４から書き込みマルチプレクサ３４８を経由して書き込まれ、トランスポーズＲＡＭ３０４に再び記憶される。その結果、ロー処理が始められる。書き込みマルチプレクサ３４８は、処理されたカラムデータを元の順番に再び並べるように制御される。保持レジスタデータがローデータ（そして、それゆえカラム処理の全てが終了される）であれば、データは、出力レジスタ３５２に送られる。制御シーケンサ３２４は、その場合には、デイジーチェイン(daisy chain)マルチプレクサ及び出力データレジスタ３５２からのデータの出力を制御できる。
【００６２】
図４は、エンコードモードにおいて図３のデータパスプロセッサ３２８により実行できるＤＣＴトレリスを示す。同様に、図５は、デコードモードにおいて図３のデータパスプロセッサ３２８により実行できるＩＤＣＴトレリスを示す。ＰＱＲデータ及び／若しくはこれから実行される計算のタイプに応じて指示されるように、制御シーケンサ３２４は、統合するためにエンコードされたデータの要素の別の対を選択でき、１次元変換の一部分を実行する。例えば、図４のトレリスにおいて、８個の演算がカラム４０４で発生する。示された演算は、以下のものである：ｘ（０）＋ｘ（７），ｘ（１）＋ｘ（６），ｘ（３）＋ｘ（４），ｘ（２）＋ｘ（５），ｘ（０）−ｘ（７），ｘ（１）−ｘ（６），ｘ（３）−ｘ（４）及びｘ（２）−ｘ（５）。各々のバタフライプロセッサ３６４，３６８，３７２及び３７６(図３に示されたように)は、所定のクロックサイクルにおいて４個の演算のうちの１個を取り扱う。それゆえ、例えば、全て同一のクロックサイクルにおいて、バタフライプロセッサ３６４は、ｘ（０）＋ｘ（７）及びｘ（０）−ｘ（７）の演算を計算し、バタフライプロセッサ３６８は、ｘ（１）＋ｘ（６）及びｘ（１）−ｘ（６）の演算を計算し、バタフライプロセッサ３７２は、ｘ（３）＋ｘ（４）及びｘ（３）−ｘ（４）の演算を計算し、及びバタフライプロセッサ３７６は、ｘ（２）＋ｘ（５）及びｘ（２）−ｘ（５）の演算を計算する。これらの演算の各々の結果は、パイプラインレジスタ中に又は中間データレジスタ３４０中に一時的に記憶でき、その後、入力マルチプレクサ３６０に送られる。パイプラインレジスタの演算は、図９Ｃ及び図９Ｄに関係して本明細書中で説明される。
【００６３】
任意選択的に、次のクロックサイクルにおいて、残りの４個の掛け算演算が、同じ４個のバタフライプロセッサを使用して計算される。したがって、バタフライプロセッサ３６４は、［ｘ（０）−ｘ（７）］＊（１／２Ｃ１１６）を計算し、バタフライプロセッサ３６８は、［ｘ（１）−ｘ（６）］＊（１／２Ｃ３１６）を計算し、バタフライプロセッサ３７２は、［ｘ（３）−ｘ（４）］＊（１／２Ｃ７１６）を計算し、及びバタフライプロセッサ３７６は、［ｘ（２）−ｘ（５）］＊（１／２Ｃ５１６）を計算する。これらの計算の結果は、中間データレジスタ３４０に一時的に記憶される。計算が終了したままでは、エンコードされたデータは、エンコードされたデータが最初に入力された時と同じ順番ではない。したがって、制御シーケンサ３２４及び入力マルチプレクサ３５６は、必要に応じて、エンコードされたデータ若しくは各フィードバックループの後で部分的に処理されるエンコードされたデータを再び順番に並べる。
【００６４】
引き続くクロックサイクルにおいて、計算は、カラム４０８に対して処理される。その結果は、中間データレジスタ３４０に再び記憶され、入力マルチプレクサ３６０を経由してフィードバックされる。再び、現在部分的に処理され、フィードバックされるエンコードされたデータは、再び順番に並べられ、エンコードされたデータの正しい部分が、適切なバタフライプロセッサに送られる。したがって、バタフライプロセッサ３６４は、ｂ（０）＋ｂ（２）及びｂ（０）−ｂ（２）を処理する。同様に、バタフライプロセッサ３６８は、ｂ（１）＋ｂ（３）及びｂ（１）−ｂ（３）を計算し、バタフライプロセッサ３７２は、ｂ（４）＋ｂ（６）及びｂ（４）−ｂ（６）を計算し、及びバタフライプロセッサ３７６は、ｂ（５）＋ｂ（７）及びｂ（５）−ｂ（７）を計算する。演算の結果は、中間データレジスタ３４０若しくはパイプラインレジスタを使用して再び記憶され、入力マルチプレクサ３６０を経由して送られる。次のクロックサイクルにおいて、１／２Ｃ１８，１／２Ｃ３８，１／２Ｃ１８，及び１／２Ｃ３８，の掛け算が、カラム３０４について説明されたものと同様な方法で実行される。したがって、バタフライプロセッサ３６４は、ｂ（０）−ｂ（２）＊１／２Ｃ１８を計算し、バタフライプロセッサ３６８は、ｂ（１）−ｂ（３）＊１／２Ｃ３８を計算し、バタフライプロセッサ３７２は、ｂ（４）−ｂ（６）＊１／２Ｃ１８を計算し、バタフライプロセッサ３７６は、ｂ（５）−ｂ（７）＊１／２Ｃ３８を計算する。
【００６５】
次のクロックサイクルにおいて、計算は、位置が計算されるｄ（０）からｄ（７）にある値についてカラム４１２に対して処理される。その結果は、中間データレジスタ３４０に再び記憶され、入力マルチプレクサ３６０にフィードバックされる。したがって、各バタフライプロセッサは、各入力の各ステージを計算する。その結果、全てが同じクロックサイクルにおいて、バタフライプロセッサ３６４は、ｄ（０）＋ｄ（１）及びｄ（０）−ｄ（１）の演算を計算し、バタフライプロセッサ３６８は、ｄ（２）＋ｄ（３）及びｄ（２）−ｄ（３）の演算を計算し、バタフライプロセッサ３７２は、ｄ（４）＋ｄ（５）及びｄ（４）−ｄ（５）の演算を計算し、そしてバタフライプロセッサ３７６は、ｄ（６）＋ｄ（７）及びｄ（６）−ｄ（７）の演算を計算する。引き続くクロックサイクルにおいて、１／２Ｃ１４の掛け算が、カラム４０４及び４０８について説明したものと同じ方法で計算される。
【００６６】
カラム４１６は、次のクロックサイクルにおいてバタフライプロセッサによって計算される数学演算の次の組を示す。図４のカラム４１６の例に示されたように、２個の演算だけがこのクロックサイクルの間に必要とされる。すなわち、ｆ（２）及びｆ（３）成分の合計、及びｆ（６）及びｆ（７）成分の合計である。したがって、バタフライプロセッサ３６４は、ｆ（２）＋ｆ（３）を計算し、バタフライプロセッサ３６８は、ｆ（６）＋ｆ（７）を計算する。
【００６７】
引き続くクロックサイクルにおいて、カラム４２０で表わされた計算が、処理される。そのようにして、ｈ（４）、ｈ（５）及びｈ（６）に対する値が、計算される。したがって、バタフライプロセッサ３６４は、ｈ（４）＋ｈ（６）を計算し、バタフライプロセッサ３６８は、ｈ（５）＋ｈ（８）を計算し、及びバタフライプロセッサ３７２は、ｈ（５）＋ｈ（６）を計算する。
【００６８】
容易に観察することが可能であるように、図５は、図４について説明したトレリスと逆の順序であるが、同様な方法で演算するＩＤＣＴトレリスを示す。ＩＤＣＴトレリスは、デコードプロセスにおいて利用され、エンコードプロセスにおいて演算するＤＣＴトレリスとは反対である。バタフライプロセッサ３６４，３６８，３７２及び３７６は、並列処理の効率性の利点を取り入れて、図４について説明したように同じ方法で演算する。エンコードプロセス及びデコードプロセスの両方において、ある実施例の顕著な利点は、トレリスの各ステージに対して同一のハードウェアを再使用することである。したがって、カラム５０４において示された計算に使用されるハードウェアは、カラム５０８，５１２，５１６及び５２０の計算に使用されるハードウェアと同一である。同様に、カラム４０４において示された計算に使用されるハードウェアは、カラム４０８，４１２，４１６及び４２０の計算に使用されるハードウェアと同一である。
【００６９】
図４のトレリスの終わりを表わす最終結果が一旦計算されると、データは、中間データレジスタ３４０から保持レジスタ３４４に転送される。保持レジスタ３４４及び出力データレジスタ３５２は、制御シーケンサ３２４によって制御される。データがカラムデータであれば、データは、書き込みマルチプレクサ３４８に転送され、トランスポーズＲＡＭ３０４に記憶し戻される。再び、エンコードされたデータは、エンコードされたデータの初めの順番を反映するために再び順番に並べられる。データがローデータであるならば、全ての計算がそれによって終了し、データは、保持レジスタ３４４から出力データレジスタ３５２に転送される。
【００７０】
図６は、１又はそれより多くの入力及び出力マルチプレクサ６００を有する単一のバタフライプロセッサの例を示す。ある実施例では、１又はそれより多くの中間データレジスタ３４０（図３参照）からのデータ出力は、入力マルチプレクサ６０４の入力ポートに接続される。ある実施例では、中間データレジスタ３４０の各々からのデータ出力は、第１マルチプレクサ６０８及び第２マルチプレクサ６１２からバタフライプロセッサへ入力される。入力ＡＲレジスタ３３２（図３参照）からのデータ出力も、入力マルチプレクサ６０４を経由して転送される。特に、ＡＲレジスタＡＲ（０）及びＡＲ（８）の出力は、マルチプレクサ６１６の入力に接続され、ＡＲ（１），ＡＲ（８），ＡＲ（９）及びＡＲ（１５）の出力は、マルチプレクサ６２０の入力に接続される。マルチプレクサ６２４及び６２８は、（図３に示された）制御シーケンサ３２４によって指示されるようにＡＲ若しくはＢＲレジスタから来る信号のいずれかを選択する。したがって、マルチプレクサ６２４は、マルチプレクサ６０８若しくは６１６からのデータのいずれかを選択し、そしてマルチプレクサ６２８は、マルチプレクサ６２０若しくはマルチプレクサ６１２からのデータのいずれかを選択する。マルチプレクサ６２４及び６２８の出力は、このようにして別々のバタフライプロセッサ６３２の入力に接続される。バタフライプロセッサ６３２は、図３、図７及び図８について説明したように、ＤＣＴ／ＩＤＣＴ／ＤＱＴ／ＩＤＱＴ変換のステージを計算する。バタフライプロセッサ６３２の２個の出力、出力６３６及び６３８、は、各中間データマルチプレクサ６４２及び６４６の入力にそれぞれ接続される。その後、データは、マルチプレクサ６４２及び６４６から選択され、中間レジスタ６５０のバンクに向かう。ある実施例では、１６個のそのような中間マルチプレクサ及びデータレジスタがある。
【００７１】
図７は、書き込みマルチプレクサのブロック図を示す。図３に示されたように、中間データレジスタ３４０の偶数出力は、マルチプレクサ７０４に入力され、中間データレジスタ３４０の奇数出力は、マルチプレクサ７０８に入力される。各々の中間レジスタのデータは、図３に示された制御シーケンサ３２４によって制御されるようにマルチプレクサ７０４，７０８，７１２及び７１６により再び順番に並べられ、それぞれ、１７−ビットレジスタ７２０及び７２４に記憶される。再び順番に並べられたデータは、その後、トランスポーズＲＡＭ３０４に記憶される。
【００７２】
図８は、各バタフライプロセッサ８００の演算を示す。ある実施例では、４個のバタフライプロセッサが実装される。しかし、タイミング及びサイズの制約を受けるが、いかなる数のバタフライプロセッサでも実装され得ることが予想される。データは、入力８０４及び８０８を経由してバタフライプロセッサに入力される。ある実施例では、入力８０４は、時々ＤＣ値を示し、トランケータ(truncator)８１２を通過する。トランケータ８１２は、２次元ＤＣＴ方程式インフラ(infra)について説明したように、１／Ｎ関数に対して応答できる。入力８０４のＤＣ値は、１７ビット−１符合ビットと１６整数ビットである。トランケータ８１２は、トランケートされたＤＣ値８１６を作り出すためにＤＣ値入力データからｎビットをトランケートする。ここで、これから処理されるデータが１６×１６ブロックであるならば、ｎは４ビットであり、これから処理されるデータが８×８ブロックであるならば、ｎは３ビットであり、これから処理されるデータが４×４ブロックであるならば、ｎは２ビットであり、そして、これから処理されるデータが２×２ブロックであるならば、ｎは１ビットである。入力がＡＣ値であるならば、トランケータ８１２は、バイパスされ、第１セレクタ８１４に送られる。そして、第１セレクタ８１４は、トランケートされたＤＣ値８１６若しくは入力Ａ８０４からのＡＣ値のいずれかを選択する。分数ビットが使用できることは予想されるけれども、この実施例では、分数ビットは使用されていない。
【００７３】
第１セレクタ８１６の出力は、ディレー(delay)８２０及び第２セレクタ８２４に送られる。セレクタ値８１６の出力が、ディレー８２０に送られる場合、トランケートされたＤＣ値は、第２セレクタ８２４に送られる前にクロックサイクルの間保持される。ある実施例では、ディレー８２０は、レジスタである。第２セレクタ８２４中のデータの選択は、そのデータにこれから実行される数学演算のタイプの関数である。好ましくは制御シーケンサから送られる制御ワード８２６は、第２セレクタ８２４をトリガする。図８全体を通して示されるように、制御ワード８２６は、多数の構成要素に対する制御を提供する。再び、これから実行される数学演算のタイプに依存して、その後、データは、加算器８３２若しくは減算器８３６を通過する。第３セレクタ８２８も、ディレー８２０からの遅延した出力値を、入力８０８とともに受信する。再び、第３セレクタ８２８中のデータの選択は、そのデータにこれから実行される数学演算のタイプの関数である。
【００７４】
データが足し算された若しくは引き算されたもののいずれかであるので、その後、データは、バタフライプロセッサ８００から出力するために第４セレクタ８４０若しくは第５セレクタ８４４のいずれかに向け通過する。入力８０４も、第４セレクタ８４０に向け通過し、そして、入力８０８は、第５セレクタ８４４に向け通過する。エンコードモードにおいて、データは、第６セレクタ８４８にも送られる。ある実施例では、エンコードモードにおいて、データは、第６セレクタ８４８に送られる前に、エンコードディレー８５２を経由して送られる。
【００７５】
第２入力、入力８０８、は、第３セレクタ８２８及び第６セレクタ８４８を通過する。入力８０８が第６セレクタ８４８によって選択されるならば、データは、マルチプレクサ８５６に送られる。ここで入力８０８は、スカラー(scalar)８６０によって掛け算される。スカラー８６０による掛け算プロセスは、スケーリングして(scale)スケーリングされた出力８６４を生成する。ある実施例では、スカラー８６０は、ビー・ジー・リーのアルゴリズムに基づいて選択される。ある実施例では、スケーリングされた出力８６４は、その後、フォーマッタ８６８に送られる。フォーマッタ８６８は、２４ビットフォーマット、１符合ビット、１６整数ビット及び７分数ビット、から１７ビットフォーマットへデータを丸め、サチュレート(saturate)する。このようにして、フォーマットされスケーリングされた出力８７２は、２０ビットの長さではなく１７ビットである。この方法でのデータの処理は、精度が計算を行う際に維持されることを容認するが、データを表現するために少ないビットしか使用しない、それは順に、ハードウェアの空間を節約する。フォーマットされスケーリングされた出力８７２は、さらに処理するために、ディレー８７６を経由して第３セレクタ８２８及び第５セレクタ８４４に送られる。
【００７６】
図９Ａから図９Ｆは、各バタフライプロセッサにより実行することができる種々の数学演算を示す。図９Ａは、バタフライプロセッサ９００によって実行される無演算を示す。２個の入力、入力Ａ（９０２）及び入力Ｂ（９０４）、が与えられ、各入力は、出力Ｃ（９０６）及び出力Ｄ（９０８）に向けて単純に通過する。したがって、無演算においては、Ｃ＝Ａ及びＤ＝Ｂである。
【００７７】
図９Ｂは、バタフライプロセッサ９１０により実行される累積演算を示す。２個の入力、入力Ａ（９１２）及び入力Ｂ（９１４）、が与えられ、出力Ｃ（９１６）は、Ａ＋Ｂの合計を表わす。入力Ａ（９１２）及び入力Ｂ（９１４）は、加算器９１３により統合される。出力Ｄ（９１８）は、入力Ｂ（９１４）の通過を表わす。したがって、累積演算においては、Ｃ＝Ａ＋Ｂ及びＤ＝Ｂである。
【００７８】
図９Ｃは、バタフライプロセッサ９２０により実行されるバタフライＤＣＴ演算を示す。２個の入力、入力Ａ（９２２）及び入力Ｂ（９２４）、が与えられ、出力Ｃ（９２６）は、入力Ａ（９２２）及び入力Ｂ（９２４）の合計を表わし、その結果、Ｃ＝Ａ＋Ｂである。入力９２２及び入力９２４は、加算器９２３により統合される。出力Ｄ（９２８）は、Ａ（９２２）及び入力Ｂ（９２４）の差を係数ＣＦ（９３０）と掛け合わせたものを表わし、その結果、Ｄ＝ＣＦ×（Ａ−Ｂ）である。入力９２４は、減算器９２５により入力９２２から引き算され、その後、乗算器９２７により掛け算される。任意の選択として、パイプラインレジスタ９３２及び９３４は、次のクロックサイクルまで途中結果を一時的に記憶するために使用できる。
【００７９】
図９Ｄは、バタフライプロセッサ９３６により実行されるバタフライＩＤＣＴ演算を示す。２個の入力、入力Ａ（９３８）及び入力Ｂ（９４０）、が与えられ、出力Ｃ（９４２）は、入力Ａ（９３８）と入力Ｂ（９４０）を係数ＣＦ（９４３）で掛け算したものの合計を表わし、その結果、出力Ｃ＝Ａ＋（Ｂ×ＣＦ）である。入力Ｂ（９４０）は、乗算器９４５により係数ＣＦ（９４３）と掛け算され、その後、加算器９４７により入力Ａ（９３８）に足し算される。同様に、出力Ｄ（９４４）は、入力Ａ（９３８）と入力Ｂ（９４０）を係数ＣＦ（９４３）で掛け算したものとの差を表わし、その結果、Ｄ＝Ａ−（Ｂ×ＣＦ）である。入力Ｂ（９４０）は、乗算器９４５により係数ＣＦ（９４３）と掛け算され、その後、減算器９４９により入力Ａ（９３８）から引き算される。任意の選択として、パイプラインレジスタ９４６及び９４８は、次のクロックサイクルまで途中結果を一時的に記憶するために使用できる。
【００８０】
図９Ｅは、バタフライプロセッサ９５０により実行される累積レジスタ演算を示す。２個の入力、入力Ａ（９５２）及び入力ＡＲＥＧ（９５４）、が与えられ、出力Ｃ（９５６）は、入力Ａ及びＡＲＥＧの合計を表わし、その結果、Ｃ＝Ａ＋ＡＲＥＧである。入力値とは反対に、ＡＲＥＧは、前のクロックサイクルからレジスタ９５１に記憶された値であってもよい。入力Ａ（９５２）は、加算器９５３によりＡＲＥＧ（９５４）に足し算される。
【００８１】
図９Ｆは、バタフライプロセッサ９５８により実行されるＤＱＴ／ＩＤＱＴ演算を表わす。２個の入力、入力Ａ（９６０）及び入力Ｂ（９６２）、が与えられ、出力Ｃ（９６４）は、入力Ａ及びＢの合計を表わし、その結果、Ｃ＝Ａ＋Ｂである。同様に、出力Ｄ（９６６）は、入力Ａ及びＢの差を表わし、その結果、Ｄ＝Ａ−Ｂである。入力Ａ（９６０）及び入力Ｂ（９６２）は、加算器９６３により統合される。入力Ｂ（９６２）は、減算器９６５により入力Ａ（９６０）から引き算される。
【００８２】
画像データ１０００の変換を計算するプロセスは、図１０に示され、そして、図３について説明したようにある構造において実行できる。そのプロセスは、ＤＣＴ，ＩＤＣＴ，ＤＱＴ及びＩＤＱＴのような、周波数ドメイン技術に対して容易に構成できる。カラム若しくはローデータは、初めにトランスポーズＲＡＭ１００４中に存在し、バタフライプロセッサ中の保持レジスタ１００８に転送される。データのブロックの個々のデータ要素は、選択されて統合され１０１２、そして個別のデータ要素に実行される数学演算が、選択される１０１６。実行されることができる数学演算は、図９Ａから図９Ｆについて説明され、無演算１０２０、累積１０２４、ＤＣＴバタフライ１０２８、ＩＤＣＴバタフライ１０３２、累積レジスタ１０３６及びＤＱＴ／ＩＤＱＴバタフライ１０４０を含む。数学演算の結果は、一時的に記憶される１０４４。それから、フィードバック判断１０４８が、さらに数学演算が必要であるかどうかに基づいてなされる。ある実施例では、フィードバック判断は、図３について説明されたように、制御シーケンサにより制御される。データがフィードバックされるならば１０５２、データは、保持レジスタへフィードバックされ１００８、プロセスが繰り返される。データがフィードバックされないならば１０５６、データは、出力保持レジスタへ転送される１０６０。他の１つの判断１０６４は、追加の数学演算が、データのカラム若しくはローに対して必要であるかどうかに関して行われる。もしそうであるならば（１０６８）、データのカラム若しくはローは、ホールダへ転送され１０７２、それからトランスポーズＲＡＭへと書き戻される１００４。そうでないならば（１０７６）、データのブロックは、出力データレジスタへ転送される１０８０。
【００８３】
例として、種々の説明的な論理ブロック、フローチャート、及びここで開示した実施例と関係して説明したステップは、用途特定集積回路（ＡＳＩＣ）、プログラマブル論理デバイス、単体ゲート若しくはトランジスタロジック、例えばレジスタ及びＦＩＦＯのような単体ハードウェア素子、ファームウェアインストラクションを実行するプロセッサ、いずれかの従来のプログラマブルソフトウェア及びプロセッサ、並びにこれらのいずれかの組み合わせを使用してハードウェア若しくはソフトウェアにおいて実装され得る若しくは実行され得る。プロセッサは、マイクロプロセッサであることが有利である、しかし代案として、プロセッサは、いずれかの従来のプロセッサ、コントローラ、マイクロコントローラ、若しくはステートマシーンであってもよい。ソフトウェアは、ＲＡＭメモリ、ＲＯＭメモリ、レジスタ、ハードディスク、取り外し可能なディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ若しくはこの分野で知られている他のいずれかの形式の記憶メディアに置くことができる。
【００８４】
好ましい実施例のこれまでの説明は、本技術分野に知識のあるいかなる者でも、本発明を作成し、若しくは使用することを可能にする。これらの実施例に対する各種の変形は、本技術分野に知識のある者に、容易に実現されるであろう。そして、ここで定義された一般的な原理は、創作的な能力を使用しなくとも他の実施例に適用できる。それゆえ、本発明は、ここに示された実施例に制限することを意図したものではなく、ここに開示した原理及び卓越した特性と整合する広い範囲に適用されるものである。
【図１Ａ】
0005623565.tif 000005
【図１Ｂ】
0005623565.tif 000006
【図２Ａ】
0005623565.tif 000007
【図２Ｂ】
0005623565.tif 000008
【図２Ｃ】
0005623565.tif 000009
【図３】
0005623565.tif 000010
【図４】
0005623565.tif 000011
【図５】
0005623565.tif 000012
【図６】
0005623565.tif 000013
【図７】
0005623565.tif 000014
【図８】
0005623565.tif 000015
【図９Ａ】
0005623565.tif 000016
【図９Ｂ】
0005623565.tif 000017
【図９Ｃ】
0005623565.tif 000018
【図９Ｄ】
0005623565.tif 000019
【図９Ｅ】
0005623565.tif 000020
【図９Ｆ】
0005623565.tif 000021
【図１０】
0005623565.tif 000022
【図１１Ａ】
0005623565.tif 000023
【図１１Ｂ】
0005623565.tif 000024
【図１１Ｃ】
0005623565.tif 000025