(57)【要約】【課題】量子化処理のための除算演算処理の高速化を図る。【解決手段】除数が２のべき乗の数であるか否か判定するとともに、除数が２のべき乗の数である場合における被除数のシフト量を決定し、被除数をシフト量に応じてシフト演算し、除数が２のべき乗の数である場合には、シフト演算手段から出力されるシフト演算結果に基づいて前記商を求める。【選択図】図３
2009175959.tif 000002
【特許請求の範囲】
【請求項１】
被除数を除数で除算した商を求める除算器であって、
前記除数が２のべき乗の数であるか否か判定するとともに、前記除数が２のべき乗の数である場合における被除数のシフト量を決定する２のべき乗判定手段と、
前記被除数を前記シフト量に応じてシフト演算するシフト演算手段と、
前記除数が２のべき乗の数である場合には、前記シフト演算手段から出力されるシフト演算結果に基づいて前記商を求める制御手段と、
を備えることを特徴とする除算器。
【請求項２】
請求項１記載の除算器であって、
さらに、前記被除数が前記除数よりも小さいか否か比較判定するための比較手段を備え、
前記制御手段は、前記被除数が前記除数よりも小さい場合には、各ビットの商をゼロとすることにより、前記商を求める
ことを特徴とする除算器。
【請求項３】
請求項１または請求項２記載の除算器であって、
前記被除数は画像データを離散コサイン変換したＤＣＴ係数であり、前記除数は所定の量子化閾値である、
ことを特徴とする除算器。
【請求項４】
請求項３記載の除算器を備え、
前記除算器に、前記被除数として前記ＤＣＴ係数を入力し、前記除数として前記量子化閾値を入力することにより、前記ＤＣＴ係数を前記量子化閾値で除算して求められる商を前記量子化係数として得ることを特徴とする画像符号化装置。
【請求項５】
被除数を除数で除算した商を求める除算方法であって、
前記除数が２のべき乗の数であるか否か判定するとともに、前記除数が２のべき乗の数である場合における被除数のシフト量を決定し、
前記被除数を前記シフト量に応じてシフト演算し、
前記除数が２のべき乗の数である場合には、前記シフト演算手段から出力されるシフト演算結果に基づいて前記商を求める、
ことを特徴とする除算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、除算器、特に、画像符号化装置において実行される量子化処理のための除算演算を効率的に行なうことが可能な除算器に関する。
【背景技術】
【０００２】
画像データの圧縮符号化方式であるＪＰＥＧ（Joint Photographic Expert Group）やＭＰＥＧ（Moving Picture Experts Group）による画像データの圧縮符号化では、二次元離散コサイン変換（二次元ＤＣＴ）により得られたＤＣＴ係数を、量子化閾値で除算することにより、その商としての量子化係数を得る量子化処理が実行される。従って、画像データの圧縮符号化を実行する画像符号化装置には、量子化処理を実行する回路として除算演算を実行する除算器が備えられることになる。
【０００３】
ここで、除算演算を実行する除算器は、一般的に処理速度が遅いという問題がある。図６は、基本的な除算演算のアルゴリズムを示す説明図である。
【０００４】
まず、［Ｎ＋１］ビットの被減数Ｍｄの各ビットの値を“０”とするとともに、インデックスｉの値を［Ｍ−１］とする（ステップＳ１０１０）。ここで、Ｍは被除数Ｄｄのビット数を示し、Ｎは除数Ｄｓのビット数を示す。
【０００５】
そして、被減数Ｍｄに、インデックスｉに対応するビットＤｄ［ｉ］の値を加算する（ステップＳ１０２０）。
【０００６】
次に、被減数Ｍｄが除数Ｄｓ以上の場合には（ステップＳ１０３０：ＹＥＳ）、被減数Ｍｄから除数Ｄｓを減算し（ステップＳ１０４０）、インデックスｉに対応するビットの商Ｑ［ｉ］を“１”とする（ステップＳ１０５０）。一方、被減数Ｍｄが除数Ｄｓよりも小さい場合には（ステップＳ１０３０：ＮＯ）、商Ｑ［ｉ］を“０”とする（ステップＳ１０６０）。
【０００７】
そして、インデックスｉが“０”である場合には（ステップＳ１０７０：ＹＥＳ）、この除算演算を終了する。一方、インデックスｉが“０”でない場合には（ステップＳ１０７０：ＮＯ）、インデックスｉを“１”減算し（ステップＳ１０８０）、被減数Ｍｄを１ビット左シフトして、最上位ビットの値を廃棄した値を新たな被減数Ｍｄとした上で（ステップＳ１０９０）、ステップＳ１０２０に戻ってステップＳ１０２０〜ステップＳ１０６０の処理を実行する。すなわち、インデックスｉが“０”となるまで、ステップＳ１０２０〜ステップＳ１０９０の処理を繰り返す。
【０００８】
以上のように、除算演算の基本的なアルゴリズムは、ステップＳ１０２０〜ステップＳ１０９０の処理を被除数の最上位ビット（ｉ＝［Ｍ−１］）から最下位ビット（ｉ＝０）まで順に繰り返し実行することにより除算結果を得るものである。
【０００９】
図７は、除算演算の基本的なアルゴリズムに従った除算器として、演算アルゴリズムにおける被除数Ｄｄの各ビットについての処理を、基準クロックの１クロックの間に、１ビットの処理を実行する場合の構成を示すブロック図である。
【００１０】
この除算器１０００は、Ｍビットの被除数Ｄｄを記憶する被除数レジスタ１０１と、Ｎビットの除数Ｄｓを記憶する除数レジスタ１０２と、Ｍビットの商Ｑを記憶する商レジスタ１０３と、を備える。また、除算器１０００は、Ｍビットの被除数Ｄｄ［Ｍ−１：０］から１ビットの被除数Ｄｄ［ｉ］を選択して出力するセレクタ１０４と、１ビットの被除数Ｄｄ［ｉ］を被減数Ｍｄの最下位ビットとして記憶する［Ｎ＋１］ビットの被減数レジスタ１０５と、を備える。さらに、また、除算器１０００は、［Ｎ＋１］ビットの被減数ＭｄからＮビットの除数Ｄｓを減算し、そのＮビットの減算結果（剰余）を出力する減算器１０６と、被減数Ｍｄが除数Ｄｓ以上であるか否か比較し、その１ビットの比較結果を出力する比較器１０７と、［Ｎ＋１］ビットの被減数Ｍｄを１ビット左シフトし、Ｎビットの被減数Ｍｄを出力する左シフト回路１０８と、減算器１０６の出力と左シフト回路１０８の出力のいずれか一方を選択して出力するセレクタ１０９と、比較器１０７の１ビットの出力をＭビットの商レジスタ１０３のいずれのビットに書き込むかを決定するセレクタ１１０と、セレクタ１０４およびセレクタ１１０の動作を制御する制御回路１１１と、を備える。なお、比較器１０７の出力は、セレクタ１０９の制御信号としてセレクタ１０９にも入力される。
【００１１】
セレクタ１０４および被除数レジスタ１０５によって、図６のステップＳ１０２０の処理、すなわち、被減数Ｍｄに、インデックスｉに対応するビットの被除数Ｄｄ［ｉ］の値を加算する処理が実行される。
【００１２】
減算器１０６、比較器１０７、および、セレクタ１１０によって、ステップＳ１０３０〜Ｓ１０６０の処理、すなわち、被減数Ｍｄが除数Ｄｓ以上の場合には、被減数Ｍｄら除数Ｄｓを減算し、インデックスｉに対応するビットの商Ｑ［ｉ］を“１”とし、被減数Ｍｄが除数Ｄｓよりも小さい場合には、商Ｑ［ｉ］を“０”とする、処理が実行される。
【００１３】
制御回路１１１、左シフト回路１０８、および、セレクタ１０９によって、ステップＳ１０７０〜Ｓ１０９０の処理、すなわち、インデックスｉを“１”減算し、被減数Ｍｄを１ビット左シフトして、最上位ビットの値を廃棄した値を被減数Ｍｄの上位Ｎビットの新たな値とする処理が実行される。
【００１４】
図７のような構成とした場合には、被除数Ｄｄのビット数Ｍに等しいクロック数に対応する時間が除算演算処理のために必要となる。例えば、被除数としてのＤＣＴ係数は１１ビット（符号ナシ）で表され、除数としての量子化係数は８ビットで表されるが、基準クロックの１クロックで１ビットの処理を実行する場合には、１１クロック分の時間が除算演算処理のために必要となる。
【００１５】
また、図８は、除算演算の基本的なアルゴリズムに従った除算器として、演算アルゴリズムにおける被除数Ｄｄの各ビットについての処理を、基準クロックの１クロックの間に、３ビットの処理を実行する場合の構成を示すブロック図である。
【００１６】
この除算器１０００Ａは、基準クロックの１クロックの間に３ビットの処理を実行するために、図７の除算器１０００の減算器１０６、比較器１０７、左シフト回路１０８、および、セレクタ１０９に換えて、３ビット分の減算器１０６ａ〜１０６ｃ、比較器１０７ａ〜１０７ｃ、左シフト回路１０８ａ〜１０８ｃ、および、セレクタ１０９ａ〜１０９ｃを３段に備える構成としたものである。また、この構成に対応するために、除算器１０００のセレクタ１０４およびセレクタ１１０に換えて、Ｍビットの被除数Ｄｄ［Ｍ−１：０］から３ビットの被除数Ｄｄ［ｉ］，Ｄｄ［ｉ−１］，Ｄｄ［ｉ−２］を選択し、減算器１０６ａ，１０６ｂ，１０６ｃに入力する［Ｎ＋１］ビットの被減数Ｍｄのうちの最下位ビットとして出力するセレクタ１０４Ａと、比較器１０７ａ〜１０７ｃの出力をＭビットの商レジスタ１０３のいずれの３ビットに書き込むかを決定するセレクタ１１０Ａと、を備える。さらに、制御回路１１１に換えて、セレクタ１０４Ａおよびセレクタ１１０Ａの動作を制御する制御回路１１１Ａを備える。
【００１７】
図８のような構成とした場合には、図７の構成の場合に比べて、除算演算処理の時間は短くなる。例えば、１１ビットのＤＣＴ係数を被除数とし、８ビットの量子化係数を除数とする場合、基準クロックの４クロック分の時間で除算演算処理が実行される。しかしながら、一度に処理できるビット数は回路の動作速度や回路を構成する半導体プロセスの種類等に依存するため、まとめて実行可能なビット数には制限がある。また、まとめて実行するビット数が増えるほど、回路規模もそれに比例して増大することになる。
【００１８】
また、一連の処理をパイプライン処理化することで除算器のスループットを向上させることも可能であるが、この場合にも、やはりパイプライン段数分の演算処理回路が増加し、加えてパイプライン・レジスタも必要となるため、回路規模が増加する。
【００１９】
以上のような問題を解決する除算演算の手法を用いた除算器として、例えば、特許文献１，２に記載の例が提案されている。これらの除算演算の手法は、被除数としてのＤＣＴ係数と除数としての量子化閾値とを比較する。そして、ＤＣＴ係数よりも量子化閾値の方が大きい場合には、被減数から除数を減算する処理を繰り返すことによって実行される除算演算処理を行なわずに、量子化係数としての商を“０”に設定することによって、実際の除算演算処理を省略し、全体としての演算処理時間の高速化を図るものである。
【００２０】
しかしながら、上記除算演算の手法を用いた除算器では、被除数としてのＤＣＴ係数が除数としての量子化閾値よりも大きい場合には、結局、被除数としてのＤＣＴ係数の各ビットについて最上位ビットから最下位ビットまで順に、ステップＳ１０２０〜ステップＳ１０９０のような処理を繰り返すことになり、除算演算処理時間の短縮化を図ることができず、全体としての演算処理時間の高速化が不十分であった。
【００２１】
【特許文献１】特開平１０−１９１３３４号公報
【特許文献２】特開平３−８５８７１号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
本発明は、上記課題を解決するためになされたものであり、量子化処理のための除算演算処理の高速化を図ることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００２３】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態又は適用例として実現することが可能である。
【００２４】
［適用例１］
被除数を除数で除算した商を求める除算器であって、
前記除数が２のべき乗の数であるか否か判定するとともに、前記除数が２のべき乗の数である場合における被除数のシフト量を決定する２のべき乗判定手段と、
前記被除数を前記シフト量に応じてシフト演算するシフト演算手段と、
前記除数が２のべき乗の数である場合には、前記シフト演算手段から出力されるシフト演算結果に基づいて前記商を求める制御手段と、
を備えることを特徴とする除算器。
【００２５】
適用例１記載の除算器では、除数が２のべき乗の数である場合には、シフト演算手段から出力されるシフト演算結果に基づいて前記商を求めて、実際に被除数を除数で除算する処理を省略することができるので、除算演算処理に要する時間を短縮化し、除算演算処理の高速化を図ることが可能である。
【００２６】
［適用例２］
適用例１記載の除算器であって、
さらに、前記被除数が前記除数よりも小さいか否か比較判定するための比較手段を備え、
前記制御手段は、前記被除数が前記除数よりも小さい場合には、各ビットの商をゼロとすることにより、前記商を求める
ことを特徴とする除算器。
【００２７】
適用例２記載の除算器では、被除数が除数よりも小さい場合には、各ビットの商をゼロとすることにより、被除数を除数で除算した商を求めて、実際に被除数を除数で除算する処理を省略することができるので、さらに、除算演算処理に要する時間を短縮化し、除算演算処理の高速化を図ることが可能である。
【００２８】
［適用例３］
適用例１または適用例２記載の除算器であって、
前記被除数は画像データを離散コサイン変換したＤＣＴ係数であり、前記除数は所定の量子化閾値である、
ことを特徴とする除算器。
【００２９】
適用例３に記載の除算器では、被除数としてのＤＣＴ係数を除数としての量子化閾値で除算して、その商としての量子化係数を得る除算演算処理としての量子化処理に要する時間を短縮化し、量子化処理の高速化を図ることが可能である。
【００３０】
［適用例４］
適用例３記載の除算器を備え、
前記除算器に、前記被除数として前記ＤＣＴ係数を入力し、前記除数として前記量子化閾値を入力することにより、前記ＤＣＴ係数を前記量子化閾値で除算して求められる商を前記量子化係数として得ることを特徴とする画像符号化装置。
【００３１】
適用例４に記載の画像符号化装置では、適用例３と同様の効果を奏することができる。
【００３２】
［適用例５］
被除数を除数で除算した商を求める除算方法であって、
前記除数が２のべき乗の数であるか否か判定するとともに、前記除数が２のべき乗の数である場合における被除数のシフト量を決定し、
前記被除数を前記シフト量に応じてシフト演算し、
前記除数が２のべき乗の数である場合には、前記シフト演算手段から出力されるシフト演算結果に基づいて前記商を求める、
ことを特徴とする除算方法。
【００３３】
適用例５に記載の除算方法によれば、適用例１と同様の効果を奏することができる。
【発明を実施するための最良の形態】
【００３４】
Ａ．画像符号化装置の構成：
Ｂ．除算器の構成：
Ｂ１．除算アルゴリズム：
Ｂ２．除算器の具体例：
Ｃ．変形例：
【００３５】
Ａ．画像符号化装置の構成：
図１は、本発明の除算器を量子化部に適用した画像符号化装置の構成を示すブロック図である。図２は、画像符号化装置で実行される量子化処理について示す説明図である。
【００３６】
画像符号化装置１０は、ＤＣＴ部２０と、量子化部３０と、量子化テーブル４０と、ハフマン符号化部５０と、ハフマンテーブル６０と、を備える。
【００３７】
ＤＣＴ部２０は、図２（Ａ）に示すような［８×８］画素のブロックに分割された各画像について、二次元離散コサイン変換を行なって、図２（Ｂ）に示すようなＤＣＴ係数を得る機能ブロックである。
【００３８】
量子化部３０は、図２（Ｃ）に示すような量子化テーブル４０に格納されている量子化閾値で各ブロックのＤＣＴ係数を除算することにより、図２（Ｄ）に示すように、その商としての量子化係数を得る機能ブロックである。
【００３９】
得られた量子化係数は、図２（Ｄ）に示すように、番号Ｑ１〜Ｑ６４で表される量子化係数の走査順に取り出され、ハフマン符号化部５０に入力される。
【００４０】
ハフマン符号化部５０は、入力された量子化係数をハフマンテーブル６０に従って符号化する機能ブロックである。
【００４１】
以上のように、画像符号化装置１０は、画像を表す画像データをＤＣＴ部２０でＤＣＴ係数に変換し、除算器を用いた量子化部３０で、得られたＤＣＴ係数を量子化閾値で除算処理することにより量子化し、得られた量子化係数をハフマン符号化部５０で符号化することにより、画像データの表す画像を符号化した符号データを生成する装置である。
【００４２】
Ｂ．除算器の構成：
以下では、画像符号化装置１０の量子化部３０に用いられる一実施例としての除算器について説明する。
【００４３】
Ｂ１．除算アルゴリズム：
ＪＰＥＧ方式による画像圧縮符号化処理の場合には、量子化処理として、［ＤＣＴ係数（符号ナシ１１ビット）÷量子化閾値(符号ナシ８ビット)］で表される除算演算が実行され、その商としての量子化係数（符号ナシ１１ビット）は、［０ｘ０００］〜［０ｘ７ＦＦ］の範囲となる。
【００４４】
ここで、実際の自然画像、例えば、デジタルカメラで撮像した５Ｍピクセルの写真を、高品質モードでＪＰＥＧ方式による画像圧縮符号化処理を実行した場合の量子化係数について調べると、以下の特徴を有していることがわかった。
【００４５】
［ａ］自然画像は高周波成分をあまり含んでいないため、画像データをＤＣＴ変換することにより得られたＤＣＴ係数のうち、高周波成分のＤＣＴ係数については除去したとしても、画質の劣化は少ないと考えられる。そこで、量子化処理としての除算演算では、高周波成分を除去することによる画像データの圧縮を目的として、被除数としての量子化閾値のうち、高周波成分に対応する部分の量子化閾値に、除算演算の商である量子化係数がゼロとなるような大きな数値が用いられる。例えば、上記実際の自然画像では、６５〜８０％の量子化係数が［０ｘ０００］となっている。
【００４６】
［ｂ］自然画像の低周波成分は画質の劣化に影響が大きい。そこで、除算演算による量子化処理では、画質の劣化の防止および画像データの圧縮を目的として、低周波成分に対応する部分の量子化閾値に比較的小さな数値（［０ｘ０１］〜［０ｘ２０］）が用いられる。このような比較的ちいさな数値は、そもそも２のべき乗の数である割合が高い。例えば、［０ｘ０１］〜［０ｘ２０］の範囲の３２個の数値の内、２のべき乗の数は、［０ｘ０１］，［０ｘ０２］，［０ｘ０４］，［０ｘ０８］，［０ｘ１０］，［０ｘ２０］の６個あり、約１８％を占めている。また、デジタル処理の分野では、２のべき乗の数の演算処理は速度の高速化が可能であるため、処理対象のデータとして２のべき乗の数とする傾向にあり、量子化閾値も２のべき乗の数である頻度が比較的高い。例えば、上記実際の自然画像では、商としての量子化係数が［０ｘ０００］とならない部分（全体の３５〜１５％）の中で、１０〜５０％の除数としての量子化閾値が２のべき乗の数となっている。
【００４７】
そこで、以上の点に着目すると、以下で説明するように、除算演算処理の高速化を図ることが可能であると考えられる。
【００４８】
［１］量子化係数が［０ｘ０００］であることは、ＤＣＴ係数(被除数)が量子化閾値(除数)よりも小さいことを示している。そこで、従来例でも説明したように、ＤＣＴ係数と量子化閾値とを比較し、ＤＣＴ係数＜量子化閾値である場合には、除算演算の商としての量子化係数を［０ｘ０００］として、従来アルゴリズムで説明したＤＣＴ係数（被除数）のビットごとに実行する減算処理（図６のステップＳ１０２０〜Ｓ１０９０の処理参照）を省略する。これにより、例えば、上記実際の自然画像の量子化処理としての除算演算処理のうち、６５〜８０％の除算演算処理における処理時間の短縮化を図ることがで、全体として除算演算処理の高速化を図ることができる。
【００４９】
［２］除数としての量子化閾値が２のべき乗である場合には、被除数としてのＤＣＴ係数をシフト演算することにより、除算演算の商としての量子化係数を求めて、従来アルゴリズムで説明したＤＣＴ係数（被除数）のビットごとに実行する減算処理（図６のステップＳ１０２０〜Ｓ１０９０の処理参照）を省略する。これにより、例えば、上記実際の自然画像の量子化処理としての除算演算処理のうち、量子化係数が［０ｘ０００］とならない部分（全体の３５〜１５％）の中の１０〜５０％の除算演算処理における処理時間の短縮化を図ることができ、全体として除算演算処理の高速化を図ることができる。
【００５０】
図３は、本発明の実施例としての除算演算のアルゴリズムを示す説明図である。
【００５１】
まず、Ｍビットの被除数ＤｄがＮビットの除数Ｄｓ以上であるか否か判断する（ステップＳ１０１）。被除数Ｄｄが除数Ｄｓよりも小さい場合には（ステップＳ１０１：ＮＯ）、Ｍビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を“０”とし（ステップＳ１０２）、この除算演算を終了する。一方、被除数Ｄｄが除数Ｄｓ以上である場合には（ステップＳ１０１：ＹＥＳ）、さらに、除数Ｄｓが２のべき乗の数であるか否か判断し（ステップＳ１０３）、その結果に応じて次の処理を実行する。
【００５２】
除数Ｄｓが２のべき乗の数である場合には（ステップＳ１０３：ＹＥＳ）、除数Ｄｓに応じて被除数Ｄｄをシフト演算することによりＭビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を求める（ステップＳ１０４）。
【００５３】
一方、除数Ｄｓが２のべき乗の数でない場合には（ステップＳ１０３：ＮＯ）、ステップＳ１０５〜ステップＳ１１３の処理を実行し、Ｍビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を求める。なお、このステップＳ１０５〜ステップＳ１１３は、図６のステップＳ１０１０〜ステップＳ１０９０による通常の除算演算処理と同じであるので、ここではその説明を省略する。
【００５４】
以上のように、本実施例のアルゴリズムでは、第１に、被除数Ｄｄが除数Ｄｓ以上である場合には、Ｍビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を“０”とすることにより除算結果を得るものである。第２に、除数Ｄｓが２のべき乗の数である場合には、被除数Ｄｄをシフト演算してＭビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を得ることにより除算結果を得るものである。第３に、第１の場合でも第２の場合でもない場合には、従来と同様の除算演算を実行してＭビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を得ることにより除算結果を得るものである。従って、被除数Ｄｄが除数Ｄｓよりも小さい場合および除数Ｄｓが２のべき乗の数である場合には、従来と同様の除算演算処理であるステップＳ１０５〜ステップＳ１１３の処理を省略することができる。
【００５５】
例えば、上記したように、１枚の自然画像のＪＰＥＧ方式による画像圧縮符号化処理の場合において、量子化処理としての除算演算の商である量子化係数が［０ｘ０００］となる場合、すなわち、Ｍビットの被除数Ｄｄとしての１１ビットのＤＣＴ係数がＮビットの除数Ｄｓとしての８ビットの量子化閾値よりも小さくなる場合が６５〜８０％である。従って、この場合には、上記自然画像の量子化処理としての除算演算処理のうち、６５〜８０％の除算演算処理における処理時間の短縮化を図ることができ、全体として除算演算処理の高速化を図ることが可能となる。また除数Ｄｓとしての量子化閾値が２のべき乗である場合が、量子化係数が［０ｘ０００］とならない部分（全体の３５〜１５％）の中の１０〜５０％である。従って、この場合には、上記自然画像の量子化処理としての除算演算処理のうち、１．５〜１７．５％の除算演算処理における処理時間の短縮化を図ることができ、全体として除算演算処理の高速化を図ることが可能である。
【００５６】
Ｂ２．除算器の具体例：
図４は、本発明の実施例としての除算演算のアルゴリズムに従った除算器として、被除数Ｄｄの各ビットについての処理を、基準クロックの１クロックの間に、１ビットの処理を実行する場合の構成を示すブロック図である。
【００５７】
この除算器１００は、図７に示した基本的な除算演算のアルゴリズムに従った従来の除算器１０００の構成に加えて、比較器１１２と、２のべき乗判定回路３と、シフト演算器１１４と、を備える。また、セレクタ１１０と商レジスタ１０３との間に、セレクタ１１５を備える。さらに、制御回路１１１に換えて、制御回路１１６を備える。
【００５８】
比較器１１２は、Ｍビットの被除数Ｄｄと、Ｎビットの除数Ｄｓと、を比較し、その比較結果を制御回路１１６へ出力する機能ブロックである。
【００５９】
２のべき乗判定回路１１３は、除数Ｄｓが２のべき乗の数であるか否か判定するとともに、除数Ｄｓが２のべき乗の数である場合の被除数Ｄｄのシフト量を決定し、その判定結果を制御回路１１６へ出力するとともに、シフト量をシフト演算器１１４へ出力する機能ブロックである。２のべき乗の数であるか否かの判定およびシフト量は、除数Ｄｓの各ビットのうちの１ビットのみが“１”となっていることを検出する論理回路により簡単に構成可能である。
【００６０】
シフト演算器１１４は、２のべき乗判定回路１１３から入力されたシフト量で、被除数Ｄｄをシフト演算し、得られた結果を商Ｑとしてセレクタ１１５に出力する機能ブロックである。
【００６１】
セレクタ１１５は、セレクタ１１０の出力を商レジスタ１０３に書き込むか、シフト演算器１１４の出力を商レジスタ１０３に書き込むか、“０”を商レジスタ１０３に書き込むか、を制御回路１１６の制御信号に応じて選択する機能ブロックである。
【００６２】
制御回路１１６は、比較器１１２の比較結果および２のべき乗判定回路１１３の判定結果に応じて、セレクタ１０４、セレクタ１１０、および、セレクタ１１５の動作を制御する機能ブロックである。
【００６３】
比較器１１２、セレクタ１１５、および、制御回路１１６によって、図３のステップＳ１０１およびステップＳ１０２の処理、すなわち、Ｍビットの被除数ＤｄがＮビットの除数Ｄｓよりも小さいか否か判断し、被除数Ｄｓが除数Ｄｓよりも小さい場合には、Ｍビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を“０”とする処理が実行される。
【００６４】
２のべき乗判定回路１１３、シフト演算器１４、セレクタ１１５、および、制御回路１１６によって、ステップＳ１０３およびステップＳ１０４の処理、すなわち、除数Ｄｓが２のべき乗の数であるか否か判断し除数Ｄｓが２のべき乗の数である場合には、除数Ｄｓに応じて被除数Ｄｄをシフト演算することによりＭビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を求める処理が実行される。
【００６５】
なお、従来の除算器１０００と同じ構成部分である、セレクタ１０４、被減数レジスタ１０５、減算器１０６、比較器１０７、左シフト回路１０８、セレクタ１０９、および、セレクタ１１０によって、ステップＳ１０５〜Ｓ１１０の処理、すなわち、図６に示した従来の基本的な除算演算のアルゴリズムにおけるステップＳ１０１０〜ステップＳ１０９０による通常の除算演算処理と同じ処理が実行され、Ｍビットの商Ｑの各ビットの商Ｑ［Ｍ−１］〜Ｑ［０］を求める処理が実行される。
【００６６】
この除算器１００の構成では、図３に示した除算演算のアルゴリズムに従った除算演算を実行することができ、画像圧縮符号化装置における量子化処理としての除算演算の処理時間の短縮化を図ることができるので、量子化処理のための除算演算処理の高速化を図ることが可能である。
【００６７】
また、この除算器１００の構成では、基本的には、従来の除算器１０００（図７参照）に、比較器１１２、２のべき乗判定回路１１３、シフト演算器１１４、および、セレクタ１１５を追加するのみで構成することができるので、例えば、汎用プロセッサに備えられる除算器のような複雑かつ回路規模の大きい除算器と比較して、効率が良い。
【００６８】
また、被除数Ｄｄが除数Ｄｓ以上である場合や除数Ｄｓが２のべき乗の数でない場合には、従来と同様の除算演算処理が実行されるので、少なくとも従来の除算器１０００と同様に動作することができる。
【００６９】
図５は、本発明の実施例としての除算演算のアルゴリズムに従った除算器として、被除数Ｄｄの各ビットについての処理を、基準クロックの１クロックの間に、３ビットの処理を実行する場合の構成を示すブロック図である。
【００７０】
この除算器１００Ａは、図８に示した基本的な除算演算のアルゴリズムに従った従来の除算器１０００Ａの構成に加えて、図４に示した除算器１００と同様に、比較器１１２と、２のべき乗判定回路３と、シフト演算器１１４と、を備える。また、セレクタ１１０と商レジスタ１０３との間に、セレクタ１１５を備える。さらに、制御回路１１１Ａに換えて、制御回路１１６Ａを備える。
【００７１】
制御回路１１６Ａは、比較器１１２の比較結果および２のべき乗判定回路１１３の判定結果に応じて、セレクタ１０４Ａ、セレクタ１１０Ａ、および、セレクタ１１５の動作を制御する機能ブロックである。
【００７２】
この除算器１００Ａの構成では、図４に示した除算器１００と同様に、図３に示した除算演算のアルゴリズムに従った除算演算を実行することができ、画像圧縮符号化装置における量子化処理としての除算演算の処理時間の短縮化を図ることができるので、量子化処理のための除算演算処理の高速化を図ることが可能である。
【００７３】
また、この除算器１００Ａの構成では、図４に示した除算器１００が、基準クロックの１クロックの間に１ビットの処理を実行するのに対して、３ビットの処理を実行することができるので、除算器１００に比べて、図３のステップＳ１０５〜ステップＳ１１３において繰り返し実行される処理の時間をさらに短縮化することができるので、量子化処理のための除算演算処理の高速化を図ることが可能である。
【００７４】
また、この除算器１００Ａの構成も、基本的には、従来の除算器１０００Ａ（図８参照）に、比較器１１２、２のべき乗判定回路１１３、シフト演算器１１４、および、セレクタ１１５を追加するのみで構成することができるので、例えば、汎用プロセッサに備えられる除算器のような複雑かつ回路規模の大きい除算器と比較して、効率が良い。
【００７５】
また、被除数Ｄｄが除数Ｄｓ以上である場合や除数Ｄｓが２のべき乗の数でない場合には、従来と同様の除算演算処理が実行されるので、少なくとも従来の除算器１０００Ａと同様に動作することができる。
【００７６】
なお、上記除算器１００，１００Ａにおいて、比較器１１２が本発明の被除数全体比較手段に相当する。
【００７７】
Ｃ．変形例：
なお、本発明は上記した実施例や実施形態に限られるものではなく、その要旨を逸脱しない範囲において種々の態様にて実施することが可能である。
【００７８】
上記した実施例では、除算器の具体例として、１クロックの間に１ビットの処理を実行する場合の構成の例と、１クロックの間に３ビットの処理を実行する場合の構成の例を示したが、これに限定されるものではなく、１クロックの間に２ビットの処理を実行する場合や、４ビットの処理を実行する場合の構成等、１クロックの間に複数ビットの処理を実行する場合の構成に適用可能である。
【００７９】
上記した実施例では、自然画像の画像データを二次元離散コサイン変換することにより得られたＤＣＴ係数を被除数とし、量子化閾値を除数とし、除算演算の商として量子化係数を得る場合を例として説明したが、これに限定されるものではなく、種々の場合に適用可能である。特に、除数が２のべき乗の数を多く含む場合に有効である。
【図面の簡単な説明】
【００８０】
【図１】本発明の除算器を量子化部に適用した画像符号化装置の構成を示すブロック図である。
【図２】画像符号化装置で実行される量子化処理について示す説明図である。
【図３】本発明の実施例としての除算演算のアルゴリズムを示す説明図である。
【図４】本発明の実施例としての除算演算のアルゴリズムに従った除算器として被除数Ｄｄの各ビットについての処理を基準クロックの１クロックの間に１ビットの処理を実行する場合の構成を示すブロック図である。
【図５】本発明の実施例としての除算演算のアルゴリズムに従った除算器として被除数Ｄｄの各ビットについての処理を基準クロックの１クロックの間に３ビットの処理を実行する場合の構成を示すブロック図である。
【図６】基本的な除算演算のアルゴリズムを示す説明図である。
【図７】除算演算の基本的なアルゴリズムに従った除算器として演算アルゴリズムにおける被除数Ｄｄの各ビットについての処理を基準クロックの１クロックの間に１ビットの処理を実行する場合の構成を示すブロック図である。
【図８】除算演算の基本的なアルゴリズムに従った除算器として演算アルゴリズムにおける被除数Ｄｄの各ビットについての処理を基準クロックの１クロックの間に３ビットの処理を実行する場合の構成を示すブロック図である。
【符号の説明】
【００８１】
１０…画像符号化装置
２０…ＤＣＴ部
３０…量子化部
４０…量子化テーブル
５０…ハフマン符号化部
６０…ハフマンテーブル
１００…除算器
１００Ａ…除算器
１０１…被除数レジスタ
１０２…除数レジスタ
１０３…商レジスタ
１０５…被減数レジスタ
１０４…セレクタ
１０４Ａ…セレクタ
１０６…減算器
１０７…比較器
１０８…左シフト回路
１０９…セレクタ
１０６ａ〜１０６ｃ…減算器
１０７ａ〜１０７ｃ…比較器
１０８ａ〜１０８ｃ…左シフト回路
１０９ａ〜１０９ｃ…セレクタ
１１０…セレクタ
１１０Ａ…セレクタ
１１１…制御回路
１１１Ａ…制御回路
１１２…比較器
１１３…２のべき乗判定回路
１１４…シフト演算器１１４
１１５…セレクタ
１１６…制御回路
１１６Ａ…制御回路
【図１】
2009175959.tif 000003
【図２】
2009175959.tif 000004
【図３】
2009175959.tif 000005
【図４】
2009175959.tif 000006
【図５】
2009175959.tif 000007
【図６】
2009175959.tif 000008
【図７】
2009175959.tif 000009
【図８】
2009175959.tif 000010