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