(57)【要約】信号およびデータ処理に対する計算を効率的に実行するための技法が開示される。乗算のない処理については、中間値の数列が、処理されるデータに対する入力値に基づいて生成される。数列内の少なくとも１つの中間値は、この数列内の少なくとも１つの他の中間値に基づいて生成される。数列内の１つの中間値は、入力値と定数値とを乗算するための出力値として提供される。定数値は、整数定数、有理定数または無理定数であってもよい。無理定数は、整数の分子と２の累乗である分母とを有する２進分数定数で近似される。乗算のない処理は、種々の変換（例えば、ＤＣＴおよびＩＤＣＴ）、フィルタ処理並びに、他の種類の信号およびデータ処理に対して用いられてもよい。
2009512075.tif 000002
【特許請求の範囲】
【請求項１】
処理されるデータに対する入力値を受け取るための第１のロジックと、
前記入力値に基づいて中間値の数列を生成し、前記数列内の少なくとも１つの他の中間値に基づいて、前記数列内の少なくとも１つの中間値を生成するための第２のロジックと、
前記数列内の１つの中間値を、前記入力値と定数値との乗算の出力値として提供するための第３のロジックと、
を備える装置。
【請求項２】
前記第２のロジックは、前記数列内の第１の中間値を除いて、前記数列内の少なくとも１つの先の中間値に基づいて、前記数列内の各中間値を生成する、請求項１に記載の装置。
【請求項３】
前記第２のロジックは、前記入力値に対して、前記数列内の第１の中間値を設定し、前記数列内の少なくとも１つの先の中間値に基づいて、後続の各中間値を生成し、
前記第３のロジックは、前記数列内の最後の中間値を前記出力値として提供する、請求項１に記載の装置。
【請求項４】
前記第２のロジックは、前記数列内の第１の中間値を除いて、前記数列内の少なくとも１つの先の中間値に、ビットシフト、加算、またはビットシフトと加算とを実行することによって、前記数列内の各中間値を生成する、請求項１に記載の装置。
【請求項５】
前記定数値は、整数値で近似される、請求項１に記載の装置。
【請求項６】
前記定数値は、整数の分子と２の累乗である分母とを有する２進分数定数で近似される、請求項１に記載の装置。
【請求項７】
前記第３のロジックは、前記入力値と別の定数値との別の乗算のために、前記数列内の別の中間値を別の出力値として提供する、請求項１に記載の装置。
【請求項８】
前記定数値は、整数値で近似される、請求項７に記載の装置。
【請求項９】
前記定数値は、整数の分子と２の累乗である分母とを有する２進分数定数で近似される、請求項７に記載の装置。
【請求項１０】
前記数列は、前記出力値を得るための、最小数の中間値を含んでいる、請求項１に記載の装置。
【請求項１１】
前記中間値の数列は、最小数のシフト演算および加法演算により生成される、請求項１に記載の装置。
【請求項１２】
処理されるデータに対する入力値を受け取ることと、
前記入力値に基づいて中間値の数列を生成することであって、前記数列内の少なくとも１つの中間値は、前記数列内の少なくとも１つの他の中間値に基づいて生成されることと、
前記数列内の１つの中間値を、前記入力値と定数値との乗算の出力値として提供することと、
を備える方法。
【請求項１３】
前記中間値の数列を生成することは、
前記入力値に対して、前記数列内の第１の中間値を設定することと、
前記数列内の少なくとも１つの先の中間値に基づいて後続の各中間値を生成することと、
を備える、請求項１２に記載の方法。
【請求項１４】
前記中間値の数列を生成することは、
前記数列内の第１の中間値を除いて、前記数列内の少なくとも１つの先の中間値に、ビットシフト、加算、またはビットシフトと加算とを実行することによって、前記数列内の各中間値を生成することを備える、請求項１２に記載の方法。
【請求項１５】
前記入力値と別の定数値との別の乗算のために、前記数列内の別の中間値を、別の出力値として提供することをさらに備える、請求項１２に記載の方法。
【請求項１６】
処理されるデータに対する入力値を受け取る手段と、
前記入力値に基づいて中間値の数列を生成する手段であって、前記数列内の少なくとも１つの中間値は、前記数列内の少なくとも１つの他の中間値に基づいて生成される、手段と、
前記数列内の１つの中間値を、前記入力値と定数値との乗算の出力値として提供する手段と、
を備える装置。
【請求項１７】
前記中間値の数列を生成する手段は、
前記入力値に対して、前記数列内の第１の中間値を設定する手段と、
前記数列内の少なくとも１つの先の中間値に基づいて、後続の各中間値を生成する手段と、
を備える、請求項１６に記載の装置。
【請求項１８】
前記中間値の数列を生成する手段は、
前記数列内の第１の中間値を除いて、前記数列内の少なくとも１つの先の中間値に、ビットシフト、加算、またはビットシフトと加算とを実行することによって、前記数列内の各中間値を生成する手段を備える、請求項１６に記載の装置。
【請求項１９】
前記入力値と別の定数値との別の乗算のために、前記数列内の別の中間値を、別の出力値として提供する手段をさらに備える、請求項１６に記載の装置。
【請求項２０】
処理されるデータに対する入力値を受け取るための第１のロジックと、
前記入力値に基づいて中間値の数列を生成し、前記数列内の少なくとも１つの他の中間値に基づいて、前記数列内の少なくとも１つの中間値を生成するための第２のロジックと、
前記数列内の１つの中間値を、演算の出力値として提供するための第３のロジックと、
を備える、演算の出力値を得るための装置
【請求項２１】
前記演算は、前記入力値と定数値との乗算である、請求項２０に記載の装置。
【請求項２２】
前記第２のロジックは、前記入力値に対して、前記数列内の第１の中間値を設定し、前記数列内の少なくとも１つの先の中間値に基づいて、後続の中間値をそれぞれ生成し、
前記第３のロジックは、前記数列内の最後の中間値を、前記演算の出力値として提供する、請求項２０に記載の装置。
【請求項２３】
処理されるデータに対する入力値を受け取ることと、
前記入力値に基づいて中間値の数列を生成することであって、前記数列内の少なくとも１つの中間値は、前記数列内の少なくとも１つの他の中間値に基づいて生成されることと、
前記数列内の１つの中間値を、演算の出力値として提供することと、
を備える、前記演算の出力値を得るための方法。
【請求項２４】
処理されるデータに対する入力値を受け取るための少なくとも１つの命令と、
前記入力値に基づいて中間値の数列を生成するための少なくとも１つの命令であって、前記数列内の少なくとも１つの中間値は、前記数列内の少なくとも１つの他の中間値に基づいて生成される、命令と、
前記数列内の１つの中間値を、演算の出力値として提供するための少なくとも１つの命令と、
を備える、コンピュータ読取可能媒体に記憶される少なくとも１つの命令を含むコンピュータ読取可能媒体。
【請求項２５】
一連の出力データ値を得るために、一連の入力データ値に処理を実行する第１のロジックと、
前記処理のために、入力データ値と定数値との乗算を実行し、前記乗算のために中間値の数列を生成し、前記数列内の少なくとも１つの他の中間値に基づいて前記数列内の少なくとも１つの中間値を生成する第２のロジックと、
１つの中間値を、前記入力データ値と前記定数値との前記乗算の結果として提供する第３のロジックと、
を備える装置。
【請求項２６】
前記第１のロジックは、前記一連の入力データ値を、第１の領域から第２の領域に変換するための処理を実行する、請求項２５に記載の装置。
【請求項２７】
前記第１のロジックは、前記一連の入力データ値をフィルタ処理することを実行する、請求項２５に記載の装置。
【請求項２８】
前記定数値は整数値で近似される、請求項２５に記載の装置。
【請求項２９】
前記定数値は、整数の分子と２の累乗である分母とを有する２進分数定数で近似される、請求項２５に記載の装置。
【請求項３０】
一連の出力データ値を得るために、一連の入力データ値に処理を実行することと、
前記処理のために、入力データ値と定数値との乗算を実行することと、
前記乗算のために中間値の数列を生成することであって、前記数列は、前記数列内の少なくとも１つの他の中間値に基づいて生成された少なくとも１つの中間値を有していることと、
前記数列内の１つの中間値を、前記入力データ値と前記定数値との前記乗算の結果として提供することと、
を備える方法。
【請求項３１】
前記処理を実行することは、
前記一連の入力データ値を第１の領域から第２の領域に変換するための処理を実行することを備える、請求項３０に記載の方法。
【請求項３２】
前記処理を実行することは、
前記一連の入力データ値のフィルタ処理を実行することを備える、請求項３０に記載の方法。
【請求項３３】
一連の出力データ値を得るために、一連の入力データ値に処理を実行する手段と、
前記処理のために、入力データ値と定数値との乗算を実行する手段と、
前記乗算のために中間値の数列を生成する手段であって、前記数列は、前記数列内の少なくとも１つの他の中間値に基づいて生成された少なくとも１つの中間値を有している、手段と、
前記数列内の１つの中間値を、前記入力データ値と前記定数値との前記乗算の結果として提供する手段と、
を備える装置。
【請求項３４】
前記処理を実行する手段は、前記一連の入力データ値を第１の領域から第２の領域に変換する処理を実行する手段を備える、請求項３３に記載の装置。
【請求項３５】
前記処理を実行する手段は、前記一連の入力データ値をフィルタ処理することを実行する手段を備える、請求項３３に記載の装置。
【請求項３６】
一連の出力値を得るために、一連の入力値に変換を実行する第１のロジックと、
前記変換のために、中間変数と定数値との乗算を実行し、前記乗算のために中間値の数列を生成し、前記数列内の少なくとも１つの他の中間値に基づいて前記数列内の少なくとも１つの値を生成する第２のロジックと、
前記数列内の１つの中間値を、前記中間変数と前記定数値との乗算の結果として、提供する第３のロジックと、
を備える装置。
【請求項３７】
前記第１のロジックは、前記一連の入力値に離散コサイン変換（ＤＣＴ）を実行して、前記一連の出力値に対する一連の変換係数を得る、請求項３６に記載の装置。
【請求項３８】
前記第１のロジックは、前記一連の出力値を得るために、前記一連の入力値に対する一連の変換係数に逆離散コサイン変換（ＩＤＣＴ）を実行する、請求項３６に記載の装置。
【請求項３９】
前記定数値は整数値で近似される、請求項３６に記載の装置。
【請求項４０】
前記定数値は、整数の分子と２の累乗である分母とを有する２進分数定数で近似される、請求項３６に記載の装置。
【請求項４１】
一連の出力値を得るために、一連の入力値に変換を実行することと、
前記変換のために、中間変数と定数値との乗算を実行することと、
前記乗算のために中間値の数列を生成することであって、前記数列は、前記数列内の少なくとも１つの他の中間値に基づいて生成された少なくとも１つの中間値を有することと、
前記数列内の１つの中間値を、前記中間変数と前記定数値との乗算の結果として提供することと、
を備える方法。
【請求項４２】
前記変換を実行することは、前記一連の出力値に対する一連の変換係数を得るために、前記入力値群に離散コサイン変換（ＤＣＴ）を実行することを備える、請求項４１に記載の方法。
【請求項４３】
前記変換を実行することは、前記一連の出力値を得るために、前記一連の入力値に対する変換係数群に逆離散コサイン変換（ＩＤＣＴ）を実行することを備える、請求項４１に記載の方法。
【請求項４４】
一連の出力値を得るために、一連の入力値に変換を実行する手段と、
前記変換のために、中間変数と定数値との乗算を実行する手段と、
前記乗算のために中間値の数列を生成する手段であって、前記数列は、前記数列内の少なくとも１つの他の中間値に基づいて生成された少なくとも１つの中間値を有する、手段と、
前記数列内の１つの中間値を、前記中間変数の前記定数値との乗算の結果として提供する手段と、
を備える装置。
【請求項４５】
前記変換を実行する手段は、前記一連の出力値に対する一連の変換係数を得るために、前記一連の入力値に離散コサイン変換（ＤＣＴ）を実行する手段を備える、請求項４４に記載の装置。
【請求項４６】
前記変換を実行する手段は、前記一連の出力値を得るために、前記一連の入力値に対する一連の変換係数に逆離散コサイン変換（ＩＤＣＴ）を実行する手段を備える、請求項４４に記載の装置。
【請求項４７】
８つの出力値を得るために、８つの入力値に変換を実行する第１のロジックと、
前記変換のために第１の中間変数に２つの乗算を実行する第２のロジックと、
前記変換のために第２の中間変数に２つの乗算を実行する第３のロジックであって、前記第２および第３のロジックは、前記変換のための、合計６つの乗算のうち４つを実行する、第３のロジックと、
を備える装置。
【請求項４８】
前記第２のロジックは、前記第１の中間変数での前記２つの乗算のために、中間値の第１の数列を生成し、
前記第３のロジックは、前記第２中間変数での前記２つの乗算のために、中間値の第２の数列を生成する、請求項４７に記載の装置。
【請求項４９】
前記変換のための第３中間変数についての乗算のために、中間値の第３の数列を生成する第４のロジックと、
前記変換のための第４中間変数についての乗算のために、中間値の第４の数列を生成する第５のロジックと、
をさらに備える、請求項４８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、処理に関し、より詳細には、信号およびデータ処理における計算を効率的に実行する技法に関する。
【背景技術】
【０００２】
信号およびデータ処理は、各種アプリケーションにおける様々な種類のデータに対して広く実行されている。重要な種類の処理の１つは、異なるドメイン間のデータ変換である。例えば、空間ドメインから周波数ドメインにデータ変換するために、離散コサイン変換（ＤＣＴ）が一般に用いられ、周波数ドメインから空間ドメインへデータを変換するために、逆離散コサイン変換（ＩＤＣＴ）が一般に用いられている。ＤＣＴは画像／ビデオ圧縮に広く用いられて、画像またはビデオフレーム内の画素ブロックを空間的に無相関化する。結果としての変換係数は一般に、相互依存性が小さく、この結果、これらの係数が量子化および符号化により適するようになる。ＤＣＴはまた、画素ブロックのエネルギーの大部分をわずかな数の係数（一般に、低位の）にマップする能力であるエネルギー圧縮特性を示す。このエネルギー圧縮特性によって、符号化アルゴリズムの設計を容易にすることができる。
【０００３】
ＤＣＴおよびＩＤＣＴなどの変換、並びに他の種類の信号およびデータ処理は、大量のデータに関して実行されることがある。したがって、信号およびデータ処理の計算を可能な限り効率的に実行するのが望ましい。さらに、コストおよび複雑性を低減するために、簡単なハードウェアを用いて計算を実行することが望ましい。
【０００４】
したがって、当分野では、信号およびデータ処理の計算を効率よく実行する技法が必要である。
【発明の開示】
【０００５】
（米国特許法第１１９条に基づく優先権主張）
本願は、ともに発明の名称が「ＤＣＴ（離散コサイン変換）／ＩＤＣＴ（逆離散コサイン変換）の効率的な無乗算実行（"Efficient Multiplication-Free Implementation of DCT (Discrete Cosine Transform)/IDCT (Inverse Discrete Cosine Transform)"）で、本願の譲受人に譲渡された、２００５年１０月１２日付出願の米国特許仮出願第６０／７２６，３０７号明細書および２００５年１０月１３日付出願の米国特許仮出願第６０／７２６，７０２号明細書の優先権を主張するものであり、これら出願の内容は参照により本明細書に組み込まれる。
【発明の概要】
【０００６】
本明細書では、信号およびデータ処理の計算を効率よく実行する技法が開示される。本発明の一実施形態によれば、処理されるデータの入力値を受け取り、この入力値に基づいて中間値の数列を生成する装置が開示される。装置は、数列のうちの少なくとも１つの別の中間値に基づいて数列のうちの少なくとも１つの中間値を生成する。装置は数列のうちの１つの中間値を、入力値を定数値と乗算するための出力値として提供する。この定数値は、整数定数、有理定数または無理定数であってもよい。無理定数は、整数の分子と２の累乗である分母とを有する２進分数定数で近似されてもよい。
【０００７】
別の実施形態によれば、一連の出力データを得るために一連の入力データについて処理を実行する装置が開示される。この装置は、少なくとも１つの入力データ値を少なくとも１つの定数値と乗算する処理を実行する。この装置は、少なくとも１つの乗算に対して中間値の少なくとも１つの数列を生成し、各数列は、数列の少なくとも１つの他の中間値に基づいて生成された少なくとも１つの中間値を有する。装置は各数列のうちの１つまたは複数の中間値を、関連する入力データ値を１つまたは複数の定数値と乗算した１つまたは複数の結果として提供する。
【０００８】
さらに別の実施形態によれば、一連の入力値について変換を実行して、一連の出力値を提供する装置が開示される。装置は、少なくとも１つの中間変数を少なくとも１つの定数値と少なくとも１回乗算する処理を実行する。この装置は、少なくとも１回の乗算に対して中間値の少なくとも１つの数列を生成し、各数列、数列の少なくとも１つの他の中間値に基づいて生成された少なくとも１つの中間値を有する。装置は各数列のうちの１つまたは複数の中間値を、関連する中間変数を１つまたは複数の定数値と乗算した結果として提供する。変換は、ＤＣＴ、ＩＤＣＴ、または特定の他の種類の変換であってもよい。
【０００９】
さらに別の実施形態によれば、８個の出力値を得るために８個の入力値について変換を実行する装置が開示される。装置は、第１の中間変数について２回の乗算、第２の中間変数について２回の乗算、および合計６回の乗算処理を実行する。
【００１０】
本発明の様々な態様および実施形態は以下にさらに詳細に説明される。
【詳細な説明】
【００１１】
用語の「例示的」は、本明細書では、「１つの実例、例証または説明としての役割を果たす」ことを意味するために用いられている。本明細書で開示されるいずれの例示的な実施形態も、必ずしも、他の例示的な実施形態よりも好ましい、または有利であると解釈されるべきではない。
【００１２】
本明細書で開示される計算技法は、例えば、変換、フィルタなどの様々な種類の信号およびデータ処理に用いることができる。本発明の技法はまた、画像およびビデオ処理、通信、計算、データネットワーク、データ記憶など様々な用途に用いることもできる。一般に、本発明の技法は、乗算を実行する任意の用途に用いてもよい。明確にするために、この技法を、画像およびビデオ処理で一般的に用いられるＤＣＴおよびＩＤＣＴについて、以下で具体的に説明する。
【００１３】
タイプＩＩの１次元（１Ｄ）のＮ点ＤＣＴと１ＤのＮ点ＩＤＣＴは、以下のように定義される。
【数１】
2009512075.tif 000003
【００１４】
ここで、Ｘ＝０の場合、ｃ（Ｘ）＝１／√２、それ以外では、ｃ（Ｘ）＝１であり、
ｆ（ｘ）は１Ｄの空間ドメイン関数であり、
Ｆ（Ｘ）は１Ｄの周波数ドメイン関数である。
【００１５】
式（１）の１ＤのＤＣＴは、ｘ＝０，・・・，Ｎ−１についてＮ個の空間ドメイン値に関して演算を行い、Ｘ＝０，・・・，Ｎ−１についてＮ個の変換係数を生成する。式（２）の１ＤのＩＤＣＴは、Ｎ個の変換係数に関して演算を行い、Ｎ個の空間ドメイン値を生成する。タイプＩＩのＤＣＴは、１つのタイプの変換であり、一般に、画像／ビデオ圧縮に対して提案された複数のエネルギー圧縮変換のうち最も効率の良い変換の１つと考えられている。
【００１６】
２次元（２Ｄ）のＮ×ＮのＤＣＴおよび２ＤのＮ×ＮのＩＤＣＴは、以下のように定義される。
【数２】
2009512075.tif 000004
【００１７】
ここで、Ｘ＝０の場合、ｃ（Ｘ）＝１／√２、それ以外では、ｃ（Ｘ）＝１であり、Ｙ＝０の場合、ｃ（Ｙ）＝１／√２、それ以外では、ｃ（Ｙ）＝１であり、
ｆ（ｘ，ｙ）は、２Ｄの空間ドメイン関数であり、
Ｆ（Ｘ，Ｙ）は、２Ｄの周波数ドメイン関数である。
【００１８】
式（３）の２ＤのＤＣＴは、ｘ，ｙ＝０，・・・，Ｎ−１について、Ｎ×Ｎブロックの空間ドメインサンプルまたは画素に関して演算を行い、Ｘ，Ｙ＝０，・・・，Ｎ−１について、Ｎ×Ｎブロックの変換係数を生成する。式（４）の２ＤのＩＤＣＴは、Ｎ×Ｎブロックの変換係数に関して演算を行い、Ｎ×Ｎブロックの空間ドメインサンプルを生成する。一般に、２ＤのＤＣＴと２ＤのＩＤＣＴとは、任意のブロックサイズで実行されてもよい。しかし、一般には、８×８のＤＣＴおよび８×８のＩＤＣＴが、画像およびビデオ処理に用いられる。この場合、Ｎは８に等しい、例えば、８×８のＤＣＴおよび８×８のＩＤＣＴは、ＪＰＥＧ、ＭＰＥＧ−１、ＭＰＥＧ−２、ＭＰＥＧ−４（Ｐ．２）、Ｈ．２６１、Ｈ．２６３などといった様々な画像およびビデオ符号化規格の標準的構成要素として用いられる。
【００１９】
式（３）は、２ＤのＤＣＴがＸおよびＹで分離可能であることを示している。この分離可能な分解によって、まず、８×８のデータブロックの各行（または各列）に関して１ＤのＮ点ＤＣＴ変換を実行して８×８の中間ブロックを生成し、次いで、中間ブロックの各列（または各行）に関して１ＤのＮ点ＤＣＴを実行して８×８の変換係数ブロックを生成することによって、２ＤのＤＣＴを計算することができる。同様に、式（４）は、２ＤのＩＤＣＴがｘおよびｙで分解可能であることを示している。２ＤのＤＣＴ／ＩＤＣＴを１ＤのＤＣＴ群／ＩＤＣＴ群のカスケードに分解することによって、２ＤのＤＣＴ／ＩＤＣＴの効率が１ＤのＤＣＴ／ＩＤＣＴの効率に依存する。
【００２０】
１ＤのＤＣＴおよび１ＤのＩＤＣＴは、式（１）および式（２）でそれぞれ示されている元々の形式で実施されてもよい。しかし、計算上の複雑性は、乗算および加算ができる限り少なくなる因数分解を見つけることによって、大幅に低減できる。
【００２１】
図１は、８点ＩＤＣＴの例示的な因数分解のフローグラフ１００を示している。フローグラフ１００では、加算はそれぞれ記号  
【数３】
2009512075.tif 000005
【００２２】
で表され、乗算はそれぞれ四角形で表されている。加算はそれぞれ、２つの入力値を合計または引き算して出力値を提供する。乗算はそれぞれ、入力値を、四角形の中で示された変換定数で乗算して出力値を提供する。この因数分解は以下の定数因数を用いる。
【数４】
2009512075.tif 000006
【００２３】
フローグラフ１００は８個の倍率変更された変換係数Ａ０・Ｆ（０）〜Ａ７・Ｆ（７）を受け取り、これらの係数に関して８点ＩＤＣＴを実行し、８個の出力サンプルｆ（０）〜ｆ（７）を生成する。Ａ０〜Ａ７はスケール因子であって、以下の式で与えられる。
【数５】
2009512075.tif 000007
【００２４】
フローグラフ１００は、多数のバタフライ演算を含んでいる。バタフライ演算は、２つの入力値を受け取り、２つの出力値を生成する。この場合、一方の出力値は２つの入力値の合計であり、他方の出力値は２つの入力値の差である。例えば、入力値Ａ０・Ｆ（０）およびＡ４・Ｆ（４）に対するバタフライ演算は、最上部ブランチに出力値Ａ０・Ｆ（０）＋Ａ４・Ｆ（４）を、最下部ブランチに出力値Ａ０・Ｆ（０）−Ａ４・Ｆ（４）を生成する。
【００２５】
図１は、８点ＩＤＣＴの１つの例示的な因数分解を示している。他の因数分解も、例えばクーリー・テューキーのＤＦＴアルゴリズムといった他の既知の高速アルゴリズムへのマッピングを用いることによって、または例えば時間デシメーションもしくは周波数デシメーションといった系統的因数分解法を適用することによって、導き出されている。図１で示された因数分解は結果的に合計で６回の乗算と２８回の加算となり、これは、式（２）を直接計算するのに必要な乗算および加算の回数よりも大幅に少ない。一般に、因数分解は、無理定数との乗算である基本乗算の数を減らすが、それらをゼロにするわけではない。
【００２６】
以下の用語は、数学で一般的に用いられている。
【００２７】
・有理数−２つの整数の比ａ／ｂ、ここでｂはゼロではない
・無理数−有理数ではない任意の実数
・代数的数−整数係数を有する多項式の根として表現可能な任意の数
・超越数−有理もしくは代数的ではない任意の実数または複素数
図１の乗算は、無理定数、またはより詳細には、異なった角度（π／８の倍数）のサイン値とコサイン値を表す代数的定数を用いる。これらの乗算は、浮動小数点の乗数を用いて実行され、これはコストと複雑を増大させる可能性がある。あるいは、これらの乗算は、本明細書で開示する計算技法を用いて、所望の精度を達成するために、固定小数点の整数演算を用いて効率的に実行されてもよい。
【００２８】
例示的な一実施形態では、無理定数は、以下のように、２進分母を有する有理定数によって近似される。
【数６】
2009512075.tif 000008
【００２９】
ここで、αは近似される無理定数であり、ｃおよびｂは整数であり、ｂ＞０である。分数ｃ／２ｂはまた、一般に、２進分数または２進比と称される。ｃはまた定乗数とも称され、ｂはまたシフト定数とも称される。
【００３０】
式（５）の近似によって、以下のように、固定小数点整数演算を用いて、整数変数ｘを無理定数αと乗算することができる。
【数７】
2009512075.tif 000009
【００３１】
ここで、「＞＞」は、ビット単位の右シフト演算を示し、これは２ｂによる除算に近似する。ビットシフト演算は、２ｂによる除算と類似しているが、正確には等しくはない。
【００３２】
式（６）において、ｘのαとの乗算は、ｘに整数値ｃを乗じ、その結果をｂビット右にシフトすることによって近似される。しかし、依然として、ｘのｃとの乗算は存在する。この乗算は、１サイクルの乗算があるいくつかの計算環境では許容できる。しかし、多数のサイクルまたは大面積シリコンを要する多くの環境では、乗算を回避することが望ましい。このような既存の環境の例には、パーソナルコンピュータ（ＰＣ）、無線デバイス、セルラ電話および様々な組込みプラットフォームが含まれる。これらの場合、定数との乗算は、例えば、加算およびシフトといった一連のより簡単な演算に分解される。
【００３３】
加算およびシフトを用いる乗算の実行は、例を用いて説明される。この例では、α＝２−１／２＝０．７０７１０６７８１１である。２進小数でのαの５ビット近似は、  
【数８】
2009512075.tif 000010
【００３４】
となる。１０進数の２３を２進数で表すと、２３＝ｂ０１０１１１となる。ここで、「ｂ」は２進数を示している。次に、ｘとαとの乗算が次のように近似される。
【数９】
2009512075.tif 000011
【００３５】
式（７）の乗算は、４つのシフトと３つの加算により達成できる。実質的には、定乗数ｃの「１」ビットそれぞれに対して少なくとも１回の演算が実行される。
【００３６】
同じ乗算は、以下のように、減算およびシフトを用いて実行されてもよい。
【数１０】
2009512075.tif 000012
【００３７】
式（８）の乗算は、２つのシフトと２つの減算だけで達成できる。一般には、上述の技法を用いることによって、乗算の複雑性は、定乗数ｃにおける数の「０１」と「１０」の遷移に比例する。
【００３８】
式（７）および式（８）は、加算とシフトを用いて乗算を近似する、いくつかの例である。より効率的な近似が、いくつかの他の例で見出される可能性もある。
【００３９】
様々な例示的な実施形態によれば、乗算はシフト演算および加法演算によって、および中間結果を用いて効率的に実行され、演算の全回数を減らすこともできる。例示的な実施形態は、以下のように要約できる。
【００４０】
１つの例示的な実施形態では、整数定数との乗算は、シフト演算と加法演算によって生成される中間値の数列を用いて達成される。「数列」および「シーケンス」は同義語であって、本明細書では交換可能に使用されている。この例示的な実施形態の一般的な手順は以下のとおり与えられる。
【００４１】
整数変数ｘと整数定数ｕが与えられる場合、整数値の積、
【数１１】
2009512075.tif 000013
【００４２】
は、以下の中間値の数列を用いて得られる。
【数１２】
2009512075.tif 000014
【００４３】
ここで、ｚ０＝０、ｚ１＝ｘであり、全ての２≦ｉ≦ｔ値に対してｚｉは以下の式で得られる。
【数１３】
2009512075.tif 000015
【００４４】
ここで、「±」はプラスまたはマイナスのいずれかを意味し、
【数１４】
2009512075.tif 000016
【００４５】
は、中間値ｚｋをｓｉビット分、左にシフトすることを意味し、
ｔは数列の中間値の数を示している。
【００４６】
式（１１）では、ｚｉは、
【数１５】
2009512075.tif 000017
【００４７】
に等しい。数列の各中間値ｚｉは、数列の２つの先の中間値ｚｊとｚｋに基づいて導き出される。ここで、ｚｊまたはｚｋのいずれかはゼロであってもよい。各中間値ｚｉは、１つのシフトおよび／または１つの加算によって得ることができる。ｓｉがゼロに等しい場合、シフトは必要ない。ｚｊ＝ｚ０＝０の場合、加算は必要ない。乗算に対する加算およびシフトの全回数は、数列の中間値の数（ｔ、並びに各中間値に用いられる式）によって決定される。定数ｕとの乗算は、基本的に、一連のシフト演算および加法演算に展開される。
【００４８】
数列は、数列の最終値が所望の整数値の積、すなわち以下になるように定義される。
【数１６】
2009512075.tif 000018
【００４９】
別の例示的な実施形態では、２進分母を有する有理定数（２進分数定数とも称する）との乗算が、シフト演算および加法演算によって生成された中間値の数列で近似される。この例示的な実施形態の一般的な手順は以下のとおり与えられる。
【００５０】
整数変数ｘと２進分数定数ｕ＝ｃ／２ｂ（ｂおよびｃは整数であり、ｂ＞０）とが与えられる場合、整数値の積、
【数１７】
2009512075.tif 000019
【００５１】
は、以下の中間値の数列を用いて近似される。
【数１８】
2009512075.tif 000020
【００５２】
ここで、ｚ０＝０、ｚ１＝ｘであり、全ての２≦ｉ≦ｔ値に対してｚｉは以下のとおりに得られる。
【数１９】
2009512075.tif 000021
【００５３】
ここで、  
【数２０】
2009512075.tif 000022
【００５４】
は、中間値ｚｋを｜ｓｉ｜ビット分、（定数ｓｉの符号によって）左右いずれかにシフトすることを意味する。
【００５５】
数列は、数列の最終値が所望の整数値の積、すなわち以下になるように定義される。
【数２１】
2009512075.tif 000023
【００５６】
さらに別の例示的な実施形態では、複数の整数定数との乗算が、シフト演算および加法演算によって生成される中間値の共通の数列により達成される。この例示的な実施形態の一般的な手順は以下のとおり与えられる。
【００５７】
整数変数ｘと整数定数ｕ、ｖとが与えられる場合、２つの整数値の積、  
【数２２】
2009512075.tif 000024
【００５８】
は、中間値の数列、  
【数２３】
2009512075.tif 000025
【００５９】
を用いて得られる。ここで、ｗ０＝０、ｗ１＝ｘであり、全ての２≦ｉ≦ｔ値に対してｗｉは以下の式で得られる。
【数２４】
2009512075.tif 000026
【００６０】
ここで、  
【数２５】
2009512075.tif 000027
【００６１】
は、中間値ｗｋをｓｉビット分、左にシフトすることを意味する。
【００６２】
数列は、以下のように、所望の整数値の積が、各ステップｍ、ｎで得られるように定義される。
【数２６】
2009512075.tif 000028
【００６３】
ただし、ｍ，ｎ≦ｔであり、ｍまたはｎのいずれかがｔに等しい。さらに別の例示的な実施形態では、複数の２進分数定数との乗算が、シフト演算および加法演算によって生成された中間値の共通の数列により達成される。この例示的な実施形態の一般的な手順は以下のとおり与えられる。
【００６４】
整数変数ｘと２進分数定数ｕ＝ｃ／２ｂおよびｖ＝ｅ／２ｄ（ｂ、ｃ、ｄ、ｅは整数であり、ｂ＞０およびｄ＞０）とが与えられる場合、２つの整数値の積、
【数２７】
2009512075.tif 000029
【００６５】
は、中間値の数列、
【数２８】
2009512075.tif 000030
【００６６】
を用いて近似される。ここで、ｗ０＝０、ｗ１＝ｘであり、全ての２≦ｉ≦ｔ値に対してｗｉは以下の式で得られる。
【数２９】
2009512075.tif 000031
【００６７】
ここで、  
【数３０】
2009512075.tif 000032
【００６８】
は、中間値ｗｋを｜ｓｉ｜ビット分、（定数ｓｉの符号によって）左右いずれかにシフトすることを意味する。
【００６９】
数列は、以下のとおり、所望の整数値の積が、各ステップｍ、ｎで得られるように定義される。
【数３１】
2009512075.tif 000033
【００７０】
ここで、ｍ，ｎ≦ｔであり、ｍまたはｎのいずれかがｔに等しい。
【００７１】
表１は、上述の例示的な実施形態による乗算の手順を要約している。
【表１】
2009512075.tif 000034
【００７２】
整数変数ｘと１つおよび２つの定数との乗算は上で説明してきた。一般に、整数変数ｘは、任意の数の定数と乗算されてもよい。整数変数ｘと２つ以上の定数との乗算は、中間値の共通の数列を用いて共同因数分解することにより、乗算に対して所望の積を生成できる。中間値の共通の数列は、乗算の計算において任意の類似点または重複部分を利用して、これらの乗算に対するシフト演算と加法演算の数を減らすことができる。
【００７３】
上述の例示的な実施形態のそれぞれに対する計算プロセスにおいては、ゼロの加算および減算並びにゼロビット分のシフトといった自明な演算は省略される。以下のように簡略化がなされる。
【数３２】
2009512075.tif 000035
【００７４】
式（２５）および式（２６）のそれぞれにおいて、「⇒」の左の式は、ゼロの加算または減算（ｚ０またはｗ０で示される）を含み、１つのシフトで実行できる、「⇒」の右の対応する式で示されるとおり簡略化されてもよい。式（２７）および式（２８）のそれぞれにおいて、「⇒」の左の式は、ゼロビット分のシフト（２０で示される）を含み、１つの加算で実行できる、「⇒」の右の対応する式で示されているとおりに簡略化されてもよい。
【００７５】
上述の例示的な実施形態では、たとえ１つの中間値が１つの入力値に等しく、また１つまたは複数の中間値が１つまたは複数の出力値と等しい場合にも、各数列の要素は、（簡略化のため）「中間値」と称される。数列の要素はまた、他の専門用語によって称されてもよい。例えば、数列は、入力値（ｚ１またはｗ１に対応する）と、ゼロまたは複数の中間結果と、１つまたは複数の出力値（ｚｔまたはｗｍおよびｗｎに対応する）とを含むと定義される。
【００７６】
上述の例示的な実施形態のそれぞれにおいて、中間値の数列は、演算全体の計算または実施の全体コストが最小となるように選択される。例えば、数列は、数列が最小数の中間値または最小のｔ値を含むように選択される。数列はまた、中間値が最小数のシフト演算および加法演算によって生成できるように選択されてもよい。最小数の中間値は、一般には（必ずしもというわけではないが）、結果的に最小数の演算となる。所望の数列が各種の方法で決定されてもよい。例示的な実施形態では、所望の数列は、中間値の可能な数列全てを評価し、中間値の数または各数列に対する演算の数を数え、最小数の中間値および／または最小数の演算の数列を選択することによって決定される。
【００７７】
上述の例示的な実施形態のうちの任意の１つが、整数変数ｘを１つまたは複数の定数と１回以上乗算するために用いられる。特定の例示的な実施形態の使用は、定数（複数可）が整数定数（複数可）または無理定数（複数可）のいずれであるかに依存する。複数の定数との乗算は、変換および他の種類の処理では共通である。ＤＣＴおよびＩＤＣＴでは、サインおよびコサインで乗算することによって、平面回転が実現される。例えば、図１における中間の変数ＦｃおよびＦｄはそれぞれ、ｃｏｓ（３π／８）およびｓｉｎ（３π／８）の両方で乗算される。
【００７８】
図１の乗算は、上述の例示的な実施形態を用いて効率的に実行される。図１の乗算は、以下の無理定数を用いる。
【数３３】
2009512075.tif 000036
【００７９】
上記の無理定数は、最終結果で所望の精度を達成するのに十分な数のビットの有理定数で近似されてもよい。以下の記載では、各超越定数が２つの２進分数定数で近似される。第１の有理定数が、８ビット画素に対してＩＥＥＥ１１８０〜１１９０精度基準を満たすように選択される。第２の有理定数は、１２ビット画素に対してＩＥＥＥ１１８０〜１１９０精度基準を満たすように選択される。
【００８０】
超越定数Ｃπ／４は、以下のとおり、８ビットおよび１６ビットの２進分数定数で近似される。
【数３４】
2009512075.tif 000037
【００８１】
ここで、  
【数３５】
2009512075.tif 000038
【００８２】
は、Ｃπ／４の８ビット近似であり、  
【数３６】
2009512075.tif 000039
【００８３】
は、Ｃπ／４の１６ビット近似である。
【００８４】
整数変数ｘと定数
【数３７】
2009512075.tif 000040
【００８５】
との乗算は、次の式で表される。
【数３８】
2009512075.tif 000041
【００８６】
式（１９）の乗算は、以下の一連の演算で達成される。
【数３９】
2009512075.tif 000042
【００８７】
「／／」の右の２進値は、変数ｘを乗じた中間定数である。
【００８８】
所望の８ビット積は、ｚ４に等しいかまたは、ｚ４＝ｚである。式（３０）における乗算は、３つの中間値ｚ２、ｚ３およびｚ４を生成するために３つの加算と３つのシフトにより実行される。
【００８９】
整数変数ｘと定数  
【数４０】
2009512075.tif 000043
【００９０】
との乗算は、次のように表される。
【数４１】
2009512075.tif 000044
【００９１】
式（３２）における乗算は、式（３１）で示された中間値の数列と、さらに１つの演算、すなわち、
【数４２】
2009512075.tif 000045
【００９２】
により達成される。
【００９３】
所望の１６ビット積は、ｚ５にほぼ等しいかまたは、  
【数４３】
2009512075.tif 000046
【００９４】
である。式（３２）の乗算は、４つの中間値ｚ２、ｚ３、ｚ４およびｚ５に対して４つの加算と４つのシフトにより実行される。
【００９５】
定数Ｃ３π／８およびＳ３π／８は、因数分解の奇数部分における平面回転で用いられる。奇数部分は、奇数指数を有する変換係数を含む。図１で示されているとおり、これらの定数との乗算は、中間変数ＦｃおよびＦｄのそれぞれに対して同時に実行される。したがって、これらの定数に対しては共同の因数分解が用いられる。
【００９６】
超越定数Ｃ３π／８およびＳ３π／８は、以下のように、２進分数定数で近似される。
【数４４】
2009512075.tif 000047
【数４５】
2009512075.tif 000048
【００９７】
ここで、  
【数４６】
2009512075.tif 000049
【００９８】
はＣ３π／８の７ビット近似で、  
【数４７】
2009512075.tif 000050
【００９９】
は、Ｃ３π／８の１３ビット近似であり、  
【数４８】
2009512075.tif 000051
【０１００】
はＳ３π／８の９ビット近似で、  
【数４９】
2009512075.tif 000052
【０１０１】
はＳ３π／８の１５ビット近似である。Ｃ３π／８の７ビット近似およびＳ３π／８の９ビット近似は、８ビット画素に対するＩＥＥＥ１１８０〜１１９０精度基準を満たすのに十分である。Ｃ３π／８の１３ビットの近似およびＳ３π／８の１５ビット近似は、１６ビット画素に対する望ましい高精度を達成するのに十分である。
【０１０２】
整数変数ｘの定数  
【数５０】
2009512075.tif 000053
【０１０３】
および  
【数５１】
2009512075.tif 000054
【０１０４】
との乗算は、以下の式で表される。
【数５２】
2009512075.tif 000055
【０１０５】
式（３６）における乗算は以下の一連の演算により達成される。
【数５３】
2009512075.tif 000056
【０１０６】
所望の８ビット積は、ｗ６およびｗ８に等しいかまたは、ｗ６＝ｙおよびｗ８＝ｚである。式（数３６）において共同因数分解を用いた２つの乗算は、７つの中間値ｗ２からｗ８を生成するために５つの加算と５つのシフトにより実行される。ｗ３およびｗ６の生成では、ゼロの加算は省略される。ｗ４およびｗ５の生成では、ゼロ分のシフトは省略される。
【０１０７】
整数変数ｘと定数
【数５４】
2009512075.tif 000057
【０１０８】
および
【数５５】
2009512075.tif 000058
【０１０９】
との乗算は、以下のように表される。
【数５６】
2009512075.tif 000059
【０１１０】
式（３８）における乗算は以下の一連の演算により達成される。
【数５７】
2009512075.tif 000060
【０１１１】
所望の１６ビット積は、ｗ７およびｗ９に等しいかまたは、ｗ７＝ｙおよびｗ９＝ｚである。式（３８）において共同因数分解を用いた２つの乗算は、８個の中間値ｗ２からｗ９を生成するために６つの加算と６つのシフトにより実行される。ｗ３およびｗ６の生成では、ゼロの加算は省略される。ｗ４およびｗ５の生成では、ゼロ分のシフトは省略される。
【０１１２】
図１で示された因数分解を用いた８点ＩＤＣＴに関しては、定数
【数５８】
2009512075.tif 000061
【数５９】
2009512075.tif 000062
【０１１３】
および
【数６０】
2009512075.tif 000063
【０１１４】
との乗算について本明細書で開示した技法を用いると、８ビット精度に対する全体の複雑性は以下のように与えられる。すなわち、２８＋３・２＋５・２＝４４加算および３・２＋５・２＝１６シフトである。定数
【数６１】
2009512075.tif 000064
【数６２】
2009512075.tif 000065
【０１１５】
および
【数６３】
2009512075.tif 000066
【０１１６】
との乗算を用いた８点ＩＤＣＴに関しては、１６ビット精度に対する全体の複雑性は以下のように与えられる。すなわち、２８＋４・２＋６・２＝４８加算および４・２＋６・２＝２０シフトである。一般に、各定数に対して十分なビット数を用いることによって、任意の所望の精度を達成できる。全体の複雑性は、式（２）で示された総当り的な計算に比べて大幅に低減される。さらに、乗算の必要なしに、加算とシフトのみを用いて変換を達成することができる。
【０１１７】
式（３１）、式（３３）、式（３７）および式（３９）における中間値シーケンスは、例示的なシーケンスである。所望の積はまた、中間値の他のシーケンスを用いて得られる。一般に、所定のシーケンスにおける加算演算および／またはシフト演算の数を最小限にすることが望ましい。いくつかのプラットフォームでは、加算はシフトよりも複雑であり、そのため、目的は、最小数の加算でシーケンスを見出すことになる。いくつかの別のプラットフォームでは、シフトはよりコストが高くなる可能性がある。この場合、シーケンスは、最小数のシフト（および／または全シフト演算においてシフトされる総ビット数）を含むべきである。一般に、シーケンスは、最小加重平均数の加算演算およびシフト演算を含んでもよく、この場合の加重は、対応して生じる、加算およびシフトの相対的複雑性を表す。このようなシーケンスを見出す際に、いくつかの追加的な制約が適用されてもよい。例えば、相互依存する中間値の最長サブシーケンスが特定の所定の値を超えないことを保証することが重要である。シーケンスの選択において用いられる他の例示的な基準は、右シフトによって生じる近似誤差のいくつかの測定基準（例えば、平均値、分散、大きさなど）を含んでもよい。
【０１１８】
整数変数ｘと１つまたは複数の定数との乗算は、中間値の様々なシーケンスにより達成される。最小数の加算演算および／またはシフト演算を用いた、または追加で課せられた制約もしくは最適化基準を有するシーケンスは、様々な方法で決定される。1つの方法では、中間値の可能なシーケンスの全ては、全数検索によって特定され、評価される。最小数の演算による（および他の制約および基準全てを満たす）シーケンスが選択され使用される。
【０１１９】
中間値のシーケンスは、無理定数を近似するのに用いられる有理定数に依存する。各有理定数に対するシフト定数ｂは、ビットシフト数を決定し、シフト演算と加算演算の数にも影響を与える可能性がある。小さいシフト定数は、通常は（必ずしもというわけではないが）、乗算を近似するためのシフト演算および加法演算の数が少ないことを意味する。
【０１２０】
いくつかの場合においては、フローグラフの乗算グループに対して、共通のスケール因子を見出すことにより無理定数に対する近似誤差が最小になるようにする。このような共通のスケール因子は、変換の入力スケール因子Ａ０〜Ａ７と結合、吸収されてもよい。
【０１２１】
上述の８ビットおよび１６ビットＩＤＣＴの実行は、コンピュータシミュレーションを用いて試験された。ＩＥＥＥ規格１１８０〜１１９０およびその審議中の代替案では、実際のＤＣＴ／ＩＤＣＴの実行の精度に対して広く受け入れられているベンチマークを提供している。要約すると、この規格は、近似ＩＤＣＴを試験後に乱数発生器からの入力データを用いて基準６４ビット浮動小数点ＤＣＴを試験することを規定している。基準ＤＣＴは入力データを受け取り、変換係数を生成する。近似ＩＤＣＴは、変換係数（適切に端数を丸めた）を受け取り、出力サンプルを生成する。次に、この出力サンプルを、表２で与えられる５つの異なった測定基準を用いて、入力データと比較する。さらに、近似ＩＤＣＴは、ゼロ変換係数を提供する場合は全てゼロを発生させ、近似ＤＣ反転挙動を示すことが要求される。
【表２】
2009512075.tif 000067
【０１２２】
コンピュータシミュレーションは、上述の８ビット近似を採用するＩＤＣＴが、表２の測定基準の全てに対してＩＥＥＥ１１８０〜１１９０精度要求を満たすことを示す。このコンピュータシミュレーションはさらに、上述の１６ビット近似を使用するＩＤＣＴが、表２の測定基準の全てに対してＩＥＥＥ１１８０〜１１９０精度要求を大幅に超えていることを示している。８ビットおよび１６ビットＩＤＣＴ近似はさらに、オールゼロ入力および近似ＤＣ反転試験に合格する。
【０１２３】
簡単化のために、上述の説明の大部分は、ＩＥＥＥ規格１１８０〜１１９０の精度要求を満たす、８点倍率変更１ＤのＩＤＣＴを効率よく実行するためのものである。この倍率変更された１ＤのＩＤＣＴは、ＪＰＥＧ、ＭＰＥＧ−１、２、４、Ｈ．２６１、Ｈ．２６３符合器／復号器（符復号器）および他のアプリケーションでの使用に適している。１ＤのＩＤＣＴは、図１に示された、２８個の加算と無理定数による６つの乗算を有する、倍率変更ＩＤＣＴ因数分解を使用する。これらの乗算は、上述のように、シフト演算と加法演算のシーケンスに展開される。演算の数は、中間結果を用いて中間値のシーケンスを生成することによって、低減される。さらに、所定変数と複数の定数との乗算が共同で計算されて、これらの定数に存在する共通要因（またはパターン）を一度だけ計算することによって、シフト演算と加算演算の数がさらに低減される。上述の８ビットの８点倍率変更１ＤのＩＤＣＴの全体的な複雑性は、４４個の加算と１６個のシフトである。これによって、このＩＤＣＴを、今日まで知られている最も簡単で乗算のない、ＩＥＥＥ−１１８０準拠の実現形態にしている。上述の１６ビットの８点倍率変更１ＤのＩＤＣＴの全体的な複雑性は、４８個の加算と２０個のシフトである。このより正確な１ＤのＩＤＣＴは、ＭＰＥＧ−４スタジオプロファイルおよび他のアプリケーションにおいて用いられてもよく、新しいＭＰＥＧ  ＩＤＣＴ規格にも適している。
【０１２４】
図２は、倍率変更および分離可能な方式で実現される２ＤのＩＤＣＴ２００の例示的な実施形態を示している。２ＤのＩＤＣＴ２００は、入力倍率変更ステージ２１２、次いで、列（または行）用の第１倍率変更される１ＤのＩＤＣＴステージ２１４、さらに次いで、行（または列）用の第２倍率変更される１ＤのＩＤＣＴステージ２１６、最後に出力倍率変更ステージ２１８を備えている。倍率変更される因数分解とは、変換の入力および／または出力に既知のスケール因子を乗算することを意味する。スケール因子は、変換の前方および／または後方へ移される共通の因子を含み、フローグラフ内でより簡単な定数を生成し、この結果計算を簡略化する。入力倍率変更ステージ２１２は、各変換係数Ｆ（Ｘ，Ｙ）に定数Ｃ＝２Ｐを予め乗算するか、または各変換係数をＰビット左へシフトする。ここで、Ｐは、確保された「仮数」ビットの数を示している。倍率変更の後、２Ｐ−１量をＤＣ変換係数に加算して、出力サンプルにおける適正な端数の丸めを達成する。
【０１２５】
第１の１ＤのＩＤＣＴステージ２１４は、倍率変更された変換係数ブロックの各列でＮ点ＩＤＣＴを実行する。第２の１ＤのＩＤＣＴステージ２１６は、第１の１ＤのＩＤＣＴステージ２１４によって生成された中間ブロックの各列で、Ｎ点ＩＤＣＴを実行する。８×８ＩＤＣＴについては、上述され、図１で示されたとおり、８点の１ＤのＩＤＣＴが、各列および各行に対して実行される。第１および第２ステージの１ＤのＩＤＣＴは、内部の事前または事後倍率変更を実行せずに、それらの入力データを直接処理できる。行および列を両方とも処理した後、出力倍率変更ステージ２１８は、結果として生じた量を、第２の１ＤのＩＤＣＴステージ２１６からＰビット右へシフトして、２ＤのＩＤＣＴに対する出力サンプルを生成する。スケール因子と精度定数Ｐは、２ＤのＩＤＣＴ全体が所望の幅のレジスタを用いて実現されるように選択される。
【０１２６】
図２における２ＤのＩＤＣＴの倍率変更を実現することにより、乗算の全回数を少なくする結果になり、さらに、乗算の大部分を、量子化および／または逆量子化ステージで実行することを可能にする。量子化および逆量子化は、典型的には、符号器によって実行される。逆量子化は、典型的には、復号器によって実行される。
【０１２７】
図３は、８点ＤＣＴの例示的な因数分解のフローグラフ３００を示している。フローグラフ３００は、８つの入力サンプルｆ（０）〜ｆ（７）を受け取り、これらの入力サンプルで８点ＤＣＴを実行し、８つの倍率変更された変換係数８Ａ０・Ｆ（０）〜８Ａ７・Ｆ（７）を生成する。スケール因子Ａ０〜Ａ７は上記の通りである。フローグラフ３００は、可能な限り少ない乗算と加算を用いるように定義される。中間変数Ｆｅ、Ｆｆ、Ｆｇ、Ｆｈに対する乗算は、上述の通り実行されてもよい。特に、無理定数１／Ｃπ／４、Ｃ３π／８およびＳ３π／８は有理定数により近似されてもよく、有理定数との乗算は、中間値のシーケンスにより達成されてもよい。
【０１２８】
図４は、分離可能な方式で実行され、倍率変更された１ＤのＤＣＴ因数分解を使用する２ＤのＤＣＴ４００の例示的な一実施形態を示している。２ＤのＤＣＴ４００は、入力倍率変更ステージ４１２、その後に列（または行）に対する第１の１ＤのＤＣＴステージ４１４、その後に行（または列）に対する第２の１ＤのＤＣＴステージ４１６、最後に出力倍率変更ステージ４１８を備えている。入力倍率変更ステージ４１２は、入力サンプルを予め乗算する。第１の１ＤのＤＣＴステージ４１４は、倍率変更された変換係数ブロックの各列についてＮ点ＤＣＴを実行する。第２の１ＤのＤＣＴステージ４１６は、第１の１ＤのＤＣＴステージ４１４によって生成された中間ブロックの各列で、Ｎ点ＤＣＴを実行する。出力倍率変更ステージ４１８は第２の１ＤのＤＣＴステージ４１６の出力を倍率変更して、２ＤのＤＣＴに対する変換係数を生成する。
【０１２９】
図５は、画像／ビデオ符号化および復号システム５００のブロック図を示している。符号化システム５１０では、ＤＣＴユニット５２０は、入力データブロック（Ｐｘ，ｙとして示されている）を受け取り、変換係数ブロックを生成する。入力データブロックは、Ｎ×Ｎブロックの画素、Ｎ×Ｎブロックの画素差値（または残り）、または、ソース信号（例えば、ビデオ信号）から生成される、特定の他の種類のデータであってもよい。画素差値は、２つの画素ブロック間の差、または画素ブロックと予測画素ブロックと間の差などであってもよい。Ｎは、一般には８に等しいが、他の値であってもよい。符号器５３０は、ＤＣＴユニット５２０から変換係数ブロックを受け取り、変換係数を符号化して、圧縮データを生成する。符号器５３０は、Ｎ×Ｎブロックの変換係数のジグザグ走査、変換係数の量子化、エントロピー符号化、パケット化など様々な機能を実行する。符号器５３０からの圧縮データは、記憶ユニットに記憶され、および／または、通信チャネル（集団５４０）を介して送信される。
【０１３０】
復号システム５５０では、復号器５６０が記憶ユニットまたは通信チャネル５４０から圧縮データを受け取り、変換係数を再構成する。復号器５６０は、逆パケット化、エントロピー復号化、逆量子化、逆ジグザグ走査など様々な機能を実行する。ＩＤＣＴユニット５７０は、再構成された変換係数を復号器５６０から受け取り、出力データブロック（Ｐ’ｘ，ｙとして示される）を生成する。出力データブロックは、Ｎ×Ｎブロックの再構成画素、Ｎ×Ｎブロックの再構成画素差値などである。出力データブロックは、ＤＣＴユニット５２０に与えられる入力データブロックの推定値であり、ソース信号を再構成するのに用いられる。
【０１３１】
図６は符号化システム６００のブロック図を示し、このシステムは、図５の符号化システム５１０の例示的な一実施形態である。キャプチャー装置／メモリ６１０がソース信号を受け取り、デジタル形式に変換し、入力／生データを提供する。キャプチャー装置６１０は、ビデオカメラ、デジタイザ、または何らかの他の装置であってもよい。プロセッサ６２０が、生データを処理し、圧縮データを生成する。プロセッサ６２０内では、生データがＤＣＴユニット６２２で変換され、ジグザグ走査ユニット６２４によって走査され、量子化器６２６によって量子化され、エントロピー符号器６２８によって符号化され、パケタイザ６３０によってパケット化される。ＤＣＴユニット６２２は、上述の技法に従って、生データに２ＤのＤＣＴを実行する。ユニット６２２から６３０はそれぞれ、ハードウェア、ファームウェアおよび／またはソフトウェアで実現されてもよい。例えば、ＤＣＴユニット６２２は、専用のハードウェア、または算術論理演算装置（ＡＬＵ）などのための命令群、またはその組み合わせで実現されてもよい。
【０１３２】
記憶ユニット６４０がプロセッサ６２０からの圧縮データを記憶する。送信機６４２が圧縮データを送信する。コントローラ／プロセッサ６５０が、符号化システム６００内の種々のユニットの演算を制御する。メモリ６５２が符号化システム６００用のデータおよびプログラムコードを記憶する。１つまたは複数のバス６６０が符号化システム６００内の種々のユニットを相互接続する。
【０１３３】
図７は、復号システム７００のブロック図を示している。これは、図５の復号システム５５０の例示的な一実施形態である。受信機７１０が符号化システムからの圧縮データを受信し、記憶ユニット７１２が受信した圧縮データを記憶する。プロセッサ７２０が、この圧縮データを処理し、出力データを生成する。プロセッサ７２０内では、圧縮データがデパケッタイザ７２２によって逆パケット化され、エントロピーデコーダ７２４によって復号され、逆量子化器７２６によって逆量子化され、逆ジグザグ走査ユニット７２８によって適切な順序で配置され、ＩＤＣＴユニット７３０によって変換される。ＩＤＣＴユニット７３０は、上述の技法に従って、再構成された変換係数に２ＤのＩＤＣＴを実行する。ユニット７２２〜７３０はそれぞれ、ハードウェア、ファームウェアおよび／またはソフトウェアで実現されてもよい。例えば、ＩＤＣＴユニット７３０は、専用のハードウェア、またはＡＬＵなどのための命令群、またはその組み合わせで実現されてもよい。表示ユニット７４０が、プロセッサ７２０から再構成された画像およびビデオを表示する。
【０１３４】
コントローラ／プロセッサ７５０は、復号システム７００内の種々のユニットの演算を制御する。メモリ７５２が、復号システム７００のためのデータおよびプログラムコードを記憶する。１つまたは複数のバス７６０が復号システム７００内の種々のユニットを相互接続する。
【０１３５】
プロセッサ６２０および７２０はそれぞれ、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）、デジタルシグナルプロセッサ（ＤＳＰ）および／または他の特定のタイプのプロセッサにより実現されてもよい。あるいは、プロセッサ６２０および７２０はそれぞれ、１つまたは複数のランダムアクセスメモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、電気プログラマブルＲＯＭ（ＥＰＲＯＭ）、電気的消去可能なプログラマブルＲＯＭ（ＥＥＰＲＯＭ）、磁気ディスク、光ディスクおよび／または当分野で公知の他のタイプの揮発性および不揮発性メモリと置き換えられてもよい。
【０１３６】
本明細書で開示される計算技法は、種々のタイプの信号およびデータ処理に用いられてもよい。この技法を変換のために用いることを上記で説明してきた。特定の例示的なフィルタ処理のためにこの技法を用いることが以下に開示される。
【０１３７】
図８Ａは、有限インパルス応答（ＦＩＲ）フィルタ８００の例示的な一実施形態のブロック図を示している。ＦＩＲフィルタ８００では、直列接続された多数の遅延素子８１２ｂ〜８１２ｌに入力サンプルｒ（ｎ）が供給される。各遅延素子８１２は１つのサンプル遅延時間を提供する。遅延素子８１２ｂ〜８１２ｌの入力サンプルと出力とがそれぞれ、乗算器８１４ａ〜８１４ｌに提供される。各乗算器８１４はまたそれぞれフィルタ係数を受け取り、乗算器のサンプルにこのフィルタ係数を乗算し、倍率変更されたサンプルを加算器８１６に提供する。各サンプリング期間において、加算器８１６は、乗算器８１４ａ〜８１４ｌからの倍率変更されたサンプルを合計し、そのサンプリング期間に対する出力サンプルを提供する。サンプリング期間ｎに対する出力サンプルｙ（ｎ）は、以下の式で表される。
【数６４】
2009512075.tif 000068
【０１３８】
ここで、ｈｉは、ＦＩＲフィルタ８００のｉ番目のタップに対するフィルタ係数である。
【０１３９】
乗算器８１４ａ〜８１４ｌはそれぞれ、上述のとおり、シフト演算および加算演算により実行されてもよい。各フィルタ係数は、整数定数または２進分数定数で近似されてもよい。各乗算器８１４から倍率変更されたサンプルはそれぞれ、その乗算器に対する整数定数または２進分数定数に基づいて生成された中間値の数列を基に得られる。
【０１４０】
図８Ｂは、ＦＩＲフィルタ８５０の例示的な一実施形態のブロック図を示している。ＦＩＲフィルタ８５０内では、入力サンプルｒ（ｎ）が、Ｌ個の乗算器８５２ａ〜８５２ｌに提供される。各乗算器８５２はまた、それぞれフィルタ係数を受け取り、乗算器のサンプルにこのフィルタ係数を乗算し、倍率変更されたサンプルを遅延ユニット８５４に提供する。ユニット８５４は、倍率変更されたサンプルを各ＦＩＲタップに対して適切な量で遅延する。各サンプリング期間において、加算器８５６がユニット８５４からのＮ個の遅延サンプルを合計し、そのサンプリング期間に対する出力サンプルを提供する。
【０１４１】
ＦＩＲフィルタ８５０はまた式（４０）を実行する。しかし、Ｌ個の乗算が、入力サンプルそれぞれで、Ｌフィルタ係数を用いて実行される。乗算器８５２ａ〜８５２ｌの複雑性を低減するために、これらのＬ個の乗算に対して共同の因数分解が用いられる。
【０１４２】
図８Ｃは、ＦＩＲフィルタ８７０の例示的な一実施形態のブロック図を示している。ＦＩＲフィルタ８７０は、カスケードに接続されたＬ／２セクション８８０ａ〜８８０ｊを含む。最初のセクション８８０ａは入力サンプルｒ（ｎ）を受け取り、最後のセクション８８０ｊは出力サンプルｙ（ｎ）を提供する。各セクション８８０は、２次フィルタセクションである。
【０１４３】
各セクション８８０内では、ＦＩＲフィルタ８７０に対する入力サンプルｒ（ｎ）または先のセクションからの出力サンプルが、直列接続された遅延要素８８２ｂおよび８８２ｃに提供される。入力サンプルと、遅延素子８８２ｂおよび８８２ｃの出力とが、乗算器８８４ａ〜８８４ｃにそれぞれ提供される。各乗算器８８４はまた、それぞれフィルタ係数を受け取り、乗算器のサンプルにこのフィルタ係数を乗算し、倍率変更されたサンプルを加算器８８６に提供する。各サンプリング期間において、加算器８８６が乗算器８８４ａ〜８８４ｃからの倍率変更されたサンプルを合計し、そのサンプリング期間に対する出力サンプルを提供する。最後のセクション８８０ｊからの、サンプリング期間ｎに対する出力サンプルｙ（ｎ）は、次の式で表される。
【数６５】
2009512075.tif 000069
【０１４４】
ここで、ｈ０，ｉ、ｈ１，ｉおよびｈ２，ｉは、ｉ番目のフィルタセクションに対するフィルタ係数である。
【０１４５】
各セクションに対して、各入力サンプルについて最大３つの乗算が実行される。各セクションでは、乗算器８８２ａ、８８２ｂおよび８８２ｃの複雑性を低減するために、これらの乗算に対して共同の因数分解が用いられる。
【０１４６】
図９は、無限インパルス応答（ＩＩＲ）フィルタ９００の例示的な一実施形態のブロック図を示している。ＩＩＲフィルタ９００内では、乗算器９１２が入力サンプルｒ（ｎ）を受け取り、フィルタ係数ｋで倍率変更し、倍率変更されたサンプルを提供する。加算器９１４が、倍率変更されたサンプルから乗算器９１８の出力を減算し、出力サンプルｚ（ｎ）を提供する。レジスタ９１６が加算器９１４からの出力サンプルを記憶する。乗算器９１８がレジスタ９１６からの遅延出力サンプルにフィルタ係数（１−ｋ）を乗算する。サンプリング期間ｎに対する出力サンプルｚ（ｎ）は以下の式で表される。
【数６６】
2009512075.tif 000070
【０１４７】
ここで、ｋはフィルタ処理の量を決定するフィルタ係数である。
【０１４８】
乗算器９１２および９１８はそれぞれ、上述のとおり、シフト演算と加算演算により実現されてもよい。フィルタ係数ｋおよび（１−ｋ）はそれぞれ、整数定数または２進分数定数で近似されてもよい。乗算器９１２および９１８のそれぞれから倍率変更されたサンプルは、それぞれ、この乗算器に対する整数定数または２進分数定数に基づいて生成された中間値の数列を基に導き出すことができる。
【０１４９】
本明細書で開示される計算は、ハードウェア、ファームウェア、ソフトウェアまたはそれらの組み合わせで実行されてもよい。例えば、入力値に定数値を乗算するためのシフト演算および加算演算は、１つまたは複数のロジックで実行されてもよい。ロジックはまた、ユニット、モジュールなどとも称される。ロジックは、ロジックゲート、トランジスタおよび／または当分野で公知の他の回路を備えたハードウェアロジックであってもよい。ロジックはまた、機械読取可能なコードを備えたファームウェアおよび／またはソフトウェアロジックであってもよい。
【０１５０】
１つの設計においては、装置は、（ａ）処理されるデータに対する入力値を受け取るための第１のロジックと、（ｂ）この入力値に基づいて中間値の数列を生成し、数列の少なくとも１つの他の中間値に基づいて、数列の少なくとも１つの中間値を生成するための第２のロジックと、（ｃ）数列の１つの中間値を、入力値に定数値を乗算するための出力値として提供するための第３のロジックとを備えている。第１、第２および第３のロジックは、別個のロジックであってもよい。あるいは、第１、第２および第３のロジックは、同一の共通ロジックまたは共有ロジックであってもよい。例えば、第３のロジックは、第２のロジックの一部であってもよく、第２のロジックは、第１のロジックの一部であってもよい。
【０１５１】
装置はまた、入力値に基づいて中間値の数列を生成し、数列の少なくとも１つの他の中間値に基づいて数列の少なくとも１つの中間値を生成し、数列の１つの中間値を、演算用の出力値として提供することによって、入力値に関する演算を実行する。演算は、算術演算、数学的演算（例えば、乗算）、他の特定の種類の演算、または、演算の集合もしくは組み合わせであってもよい。
【０１５２】
ファームウェアおよび／またはソフトウェア実現に関しては、入力値と定数値との乗算は、所望のシフト演算および加算演算を実行する機械読取可能なコードで実現されてもよい。コードは、ハードウェアに組み込まれているか、またはメモリ（例えば、図６のメモリ６５２または図７のメモリ７５２）に記憶され、プロセッサ（例えば、プロセッサ６５０または７５０）または他の特定のハードウェアユニットによって実行される。
【０１５３】
本明細書で開示される計算技法は、種々のタイプの装置に実装できる。例えば、本発明の技法は、種々のタイプのプロセッサ、種々のタイプの集積回路、種々のタイプの電子デバイス、種々のタイプの電子回路などに実装できる。
【０１５４】
本明細書で開示される計算技法は、ハードウェア、ファームウェア、ソフトウェアまたはそれらの組み合わせで実現されてもよい。この計算は、当分野で公知の任意のコンピュータ読取可能な媒体で実行されるコンピュータ読取可能な命令としてコード化される。本明細書および添付の請求項では、用語の「コンピュータ読取可能な媒体」は、実施のため、任意のプロセッサ（例えば、図６および図７で示されたコントローラ／プロセッサ）に命令を与えて実行することに関連する任意の媒体を意味する。このような媒体は、記憶装置タイプのものであってもよく、例えば、図６および図７のプロセッサ６２０およびプロセッサ７２０に関する説明で上述したとおり、揮発性または不揮発性記憶媒体の形態を取ってもよい。このような媒体はまた、伝送タイプのものであってもよく、同軸ケーブル、銅ワイヤ、光ケーブル、および機械もしくはコンピュータで読み取り可能な信号を伝達することができる音波または電磁波を伝播する空気インタフェースを含んでもよい。
【０１５５】
当業者であれば、多様な種々の技法および技法のいずれかを用いて、情報および信号を表すことができることは理解されるであろう。例えば、上記の説明全体にわたって参照されるデータ、命令、コマンド、情報、信号、ビット、記号およびチップは、電圧、電流、電磁波、磁場もしくは磁気粒子、光場もしくは光粒子、またはそれらの任意の組み合わせによって表すことができる。
【０１５６】
当業者であればさらに、本明細書で開示された実施形態に関連して説明される種々の例示的なロジックブロック、モジュール、回路およびアルゴリズムステップが、電子ハードウェア、コンピュータソフトウェアまたはこれらの組み合わせとして実現できることは理解されるであろう。ハードウェアおよびソフトウェアのこの互換性を明確に説明するために、種々の例示的な構成部品、ブロック、モジュール、回路およびステップが、一般に、これらの機能の観点から上記で説明されてきた。このような機能がハードウェアとして実現されるかまたはソフトウェアとして実現されるかは、特定用途と、システム全体に課せられる設計上の制約とに依存する。当業者は、上述の機能を、特定用途それぞれに対して種々の方法で実現可能であるが、このような実現の決定は、本発明の範囲からの逸脱を生じると解釈されるべきではない。
【０１５７】
本明細書で開示した実施形態に関して説明された種々の例示的なロジックブロック、モジュールおよび回路は、汎用目的のプロセッサ、ＤＳＰ、ＡＳＩＣ、フィールドグラマブルゲートアレイ（ＦＰＧＡ）または他のプログラム可能なロジックデバイス、ディスリートゲートもしくはトランジスタロジック、ディスリートハードウェアコンポーネント、または本明細書で記載した機能を実行するよう設計されたこれらの任意の組み合わせを用いて、実現または実行されてもよい。汎用目的のプロセッサは、マイクロプロセッサであってもよいが、代替例では、プロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラまたは状態機械であってもよい。プロセッサはまた、計算デバイスの組み合わせ（例えば、ＤＳＰとマイクロプロセッサの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアと併用する１つまたは複数のマイクロプロセッサ、または任意の他のこのような構成）として実現されてもよい。
【０１５８】
本明細書で開示した実施形態に関して説明された方法またはアルゴリズムのステップは、直接ハードウェアで、プロセッサによって実行されるソフトウェアモジュールで、またはこの２つの組み合わせで、具体化されてもよい。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭまたは当分野で公知の任意の他の形態の記憶媒体内に存在してもよい。例示的な記憶媒体はプロセッサに結合されており、これにより、プロセッサは記録媒体から情報を読み取り、記録媒体に情報を書き込むことができる。代替例では、記憶媒体はプロセッサに一体化されてもよい。プロセッサおよび記憶媒体はＡＳＩＣ内に存在してもよい。ＡＳＩＣはユーザ端末内に存在してもよい。代替例では、プロセッサおよび記憶媒体は、ユーザ端末内のディクリートコンポーネントとして存在してもよい。
【０１５９】
開示された実施形態の先の説明は、当業者が本発明を作製または利用することを可能にするために提供されている。これらの実施形態に対する種々の変更形態は、当業者には容易に明らかであり、本明細書で定義された一般原理は、本発明の精神または範囲から逸脱することなく、他の実施形態に適用可能である。したがって、本発明は、本明細書で示した実施形態に限定することを意図するものではなく、本明細書で開示される原理および新規の特徴に整合する最も広い範囲と合致するものとする。
【図面の簡単な説明】
【０１６０】
【図１】８点ＩＤＣＴの例示的な因数分解のフローグラフを示している。
【図２】例示的な２次元ＩＤＣＴを示している。
【図３】８点ＤＣＴの例示的な因数分解のフローグラフを示している。
【図４】例示的な２次元ＤＣＴを示している。
【図５】画像／ビデオ符号化および復号化システムのブロック図を示している。
【図６】符号化システムのブロック図を示している。
【図７】復号化システムのブロック図を示している。
【図８Ａ】例示的な有限インパルス応答（ＦＩＲ）フィルタの1つを示している。
【図８Ｂ】例示的な有限インパルス応答（ＦＩＲ）フィルタの1つを示している。
【図８Ｃ】例示的な有限インパルス応答（ＦＩＲ）フィルタの1つを示している。
【図９】例示的な無限インパルス応答（ＩＩＲ）フィルタを示している。
【図１】
2009512075.tif 000071
【図２】
2009512075.tif 000072
【図３】
2009512075.tif 000073
【図４】
2009512075.tif 000074
【図５】
2009512075.tif 000075
【図６】
2009512075.tif 000076
【図７】
2009512075.tif 000077
【図８Ａ】
2009512075.tif 000078
【図８Ｂ】
2009512075.tif 000079
【図８Ｃ】
2009512075.tif 000080
【図９】
2009512075.tif 000081
【国際調査報告】
2009512075.tif 000082
2009512075.tif 000083
2009512075.tif 000084