(57)【要約】【課題】適応ゴロムライス符号化における有効桁数kを低コストで推定する。【解決手段】有効桁数統計メモリ１２１は、過去に符号化した符号化対象値について、２進での有効桁数の累積値と累積回数を保持する。有効桁数推定テーブル１２２は、累積値と累積回数の組み合わせに対応する有効桁数推定値を事前に保持する。信号入力装置１１から入力信号が入力されると、順位変換手段１３５が入力信号を非負値の値に変換する。有効桁数推定手段１３２は、有効桁数統計メモリ１２１に保持されている累積値と累積回数の組み合わせに対応する有効桁数推定値をテーブル１２２から取得し、ゴロムライス符号化手段１３４はこの有効桁数推定値を用いて非負値をゴロムライス符号に変換する。有効桁数累積手段１３３は、ゴロムライス符号の対象となった非負値の有効桁数を求めて有効桁数統計メモリ１２１の累積値に加算し、累積回数をカウントアップする。【選択図】図１
2008072562.tif 000002
【特許請求の範囲】
【請求項１】
過去に符号化した符号化対象値について、２進での有効桁数を算出して累積するとともに、累積回数をカウントする有効桁数累積手段と、前記有効桁数累積手段における有効桁数の累積値と累積回数を保持する有効桁数統計メモリと、前記有効桁数累積手段における有効桁数の累積値と累積回数を初期化する統計値初期化手段と、前記有効桁数の累積値と累積回数の組み合わせに対応する有効桁数推定値を求める有効桁数推定手段と、前記有効桁数推定値を用いて前記符号化対象値をゴロムライス符号化するゴロムライス符号化手段とを備えた符号化装置。
【請求項２】
入力信号を非負値に順位変換する順位変換手段を備え、前記非負値を前記符号化対象値とすることを特徴とする請求項１に記載の符号化装置。
【請求項３】
前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする請求項１に記載の符号化装置。
【請求項４】
前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項１に記載の符号化装置。
【請求項５】
前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項３に記載の符号化装置。
【請求項６】
前記統計値初期化手段は、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする請求項３または５に記載の符号化装置。
【請求項７】
前記有効桁数統計メモリは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記有効桁数推定手段は、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする請求項５に記載の符号化装置。
【請求項８】
過去にゴロムライス復号した結果値について、２進での有効桁数を算出して累積するとともに、累積回数をカウントする有効桁数累積手段と、前記有効桁数累積手段における有効桁数の累積値と累積回数を保持する有効桁数統計メモリと、前記有効桁数累積手段における有効桁数の累積値と累積回数を初期化する統計値初期化手段と、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める有効桁数推定手段と、前記有効桁数推定値を用いて入力符号をゴロムライス復号するゴロムライス復号手段とを備えた復号装置。
【請求項９】
ゴロムライス復号の結果値を逆順位変換して信号値を生成する順位逆変換手段を備えることを特徴とする請求項８に記載の復号装置。
【請求項１０】
前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする請求項８に記載の復号装置。
【請求項１１】
前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項８に記載の復号装置。
【請求項１２】
前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項１０に記載の復号装置。
【請求項１３】
前記統計値初期化手段は、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする請求項１０または１２に記載の復号装置。
【請求項１４】
前記有効桁数統計メモリは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記有効桁数推定手段は、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする請求項１２に記載の復号装置。
【請求項１５】
コンピュータを用いて符号化を行う符号化方法であって、
前記コンピュータが、有効桁数統計メモリに保持された有効桁数の累積値と累積回数を初期化する第１のステップ、
前記コンピュータが、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める第２のステップ、
前記コンピュータが、前記有効桁数推定値を用いて符号化対象値をゴロムライス符号化する第３のステップ、
前記コンピュータが、前記ゴロムライス符号化した符号化対象値について、２進での有効桁数を算出して前記有効桁数統計メモリに保持された累積値に加算し且つ前記累積回数を更新する第４のステップを含む符号化方法。
【請求項１６】
入力信号を非負値に順位変換した値を前記符号化対象値とすることを特徴とする請求項１５に記載の符号化方法。
【請求項１７】
前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする請求項１５に記載の符号化方法。
【請求項１８】
前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項１５に記載の符号化方法。
【請求項１９】
前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項１７に記載の符号化方法。
【請求項２０】
前記第１のステップでは、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルでは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする請求項１７または１９に記載の符号化方法。
【請求項２１】
前記有効桁数統計メモリでは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記第２のステップでは、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする請求項１９に記載の符号化方法。
【請求項２２】
コンピュータを用いて入力符号の復号を行う復号方法であって、
前記コンピュータが、有効桁数統計メモリに保持された有効桁数の累積値と累積回数を初期化する第１のステップ、
前記コンピュータが、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める第２のステップ、
前記コンピュータが、前記有効桁数推定値を用いて入力符号をゴロムライス復号する第３のステップ、
前記コンピュータが、ゴロムライス復号の結果値について、２進での有効桁数を算出して前記有効桁数統計メモリに保持された累積値に加算し且つ前記累積回数を更新する第４のステップを含む復号方法。
【請求項２３】
前記第４のステップでは、さらに、ゴロムライス復号の結果値を逆順位変換して信号値を生成することを特徴とする請求項２２に記載の復号方法。
【請求項２４】
前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする請求項２２に記載の復号方法。
【請求項２５】
前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項２２に記載の復号方法。
【請求項２６】
前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項２４に記載の復号方法。
【請求項２７】
前記第１のステップでは、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルでは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする請求項２４または２６に記載の復号方法。
【請求項２８】
前記有効桁数統計メモリでは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記第２のステップでは、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする請求項２６に記載の復号方法。
【請求項２９】
コンピュータに、
有効桁数統計メモリに保持された有効桁数の累積値と累積回数を初期化する第１の処理と、
前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める第２の処理と、
前記有効桁数推定値を用いて符号化対象値をゴロムライス符号化する第３の処理と、
前記ゴロムライス符号化した符号化対象値について、２進での有効桁数を算出して前記有効桁数統計メモリに保持された累積値に加算し且つ前記累積回数を更新する第４の処理とを行わせるための符号化プログラム。
【請求項３０】
入力信号を非負値に順位変換した値を前記符号化対象値とすることを特徴とする請求項２９に記載の符号化プログラム。
【請求項３１】
前記第４の処理では、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする請求項２９に記載の符号化プログラム。
【請求項３２】
前記第２の処理では、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項２９に記載の符号化プログラム。
【請求項３３】
前記第２の処理では、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項３１に記載の符号化プログラム。
【請求項３４】
前記第１の処理では、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルでは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする請求項３１または３３に記載の符号化プログラム。
【請求項３５】
前記有効桁数統計メモリでは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記第２の処理では、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記第４の処理では、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする請求項３３に記載の符号化プログラム。
【請求項３６】
コンピュータに、
有効桁数統計メモリに保持された有効桁数の累積値と累積回数を初期化する第１の処理と、
前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める第２の処理と、
前記有効桁数推定値を用いて入力符号をゴロムライス復号する第３の処理と、
ゴロムライス復号の結果値について、２進での有効桁数を算出して前記有効桁数統計メモリに保持された累積値に加算し且つ前記累積回数を更新する第４の処理とを行わせるための復号プログラム。
【請求項３７】
前記第４の処理では、さらに、ゴロムライス復号の結果値を逆順位変換して信号値を生成することを特徴とする請求項３６に記載の復号プログラム。
【請求項３８】
前記第４の処理では、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする請求項３６に記載の復号プログラム。
【請求項３９】
前記第２の処理では、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項３６に記載の復号プログラム。
【請求項４０】
前記第２の処理では、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする請求項３８に記載の復号プログラム。
【請求項４１】
前記第１の処理では、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルでは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする請求項３８または４０に記載の復号プログラム。
【請求項４２】
前記有効桁数統計メモリでは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記第２の処理では、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記第４の処理では、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする請求項４０に記載の復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデジタル信号の可変長符号化方式に関し、特に、適応ゴロムライス（Golomb-Rice）符号による可変長符号化方式に関する。
【背景技術】
【０００２】
ゴロムライス符号は、信号値を「単進符号」+「kビットの固定長符号（kは有効桁数の推定値）」として出力するもので、０に近い値ほど短い符号長となることから、予測残差の簡易符号化として知られている。
【０００３】
ゴロムライス符号化は、符号化対象となる２進数を下位kビットと上位の残りビットとに分割し、上位の残りビットを単進符号に置き換える。たとえば、信号00010011（２値表現）をk=3で符号化する場合、下位3ビットを除く上位5ビット(00010)が単進符号化された後、下位3ビットがそのまま出力される。単進符号として、ビット列で表現される数だけの"0"のビットに"1"のビットを付加した符号を用いる場合、上記の例では上位5ビットの数値が2であるため、2ビットの"0"が出力され、"1"で終端される。下位3ビットとあわせて最終的に"001011"が符号として出力される。
【０００４】
復号側では、符号化に使われたものと同じkの値を用いて、復号対象となる２進数を下位kビットと上位の残りビットとに分割し、上位の残りビットを単進符号前の状態に復号する。たとえば、k=3として符号化された上述の例の符号"001011"の復号では、まず、単進符号"001"から2という数値が復号されて上位5ビット"00010"として出力され、さらに、後続する"011"が下位3ビットとして出力される。この結果、元の信号と完全に一致する信号00010011が得られる。このようにゴロムライス符号は可逆圧縮符号の一種である。
【０００５】
ゴロムライス符号は、符号化すべき信号値の有効桁とk値が一致する場合に、最も符号長が短くなる。上述の信号00010011の例では、有効桁は5桁なので、k=5の時、出力される符号が110011となって符号長が最短となる。そのため、最適なk値を予測する適応型ゴロムライス符号が考案されている。
【０００６】
適応型ゴロムライス符号の一例が特許文献1に記載されている。特許文献1に記載された適応型ゴロムライス符号化方式は、ゴロムライス符号化の対象とする信号値d（特許文献1では予測残差をゴロムライス符号化の対象としている）の統計から、最適なk値を予測するものである。具体的には、それまでに出現した信号値dの絶対値を累積し、その総和aと累積回数nから平均的な有効桁数kが推定される。また、累積回数があらかじめ決められた上限値（Reset）に達すると、累積値と累積回数をそれぞれ半分にする再スケール処理が行われる。
【０００７】
【特許文献１】米国特許第5764374号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献1に記載の適応型ゴロムライス符号化方式では、それまでに出現したゴロムライス符号化対象信号値dの絶対値の累積値aと累積回数nから有効桁数kを推定している。このため、有効桁数kの推定に多くの処理と時間を必要とし、推定コストが大きいという課題があった。その理由は、ゴロムライス符号化対象信号値dの絶対値の累積値aと累積回数nから有効桁数kを推定するためには、n×2k≧aを満たす最小のkを求める必要があり、そのためにはnのシフトを順次行ってaと比較する探索処理が必要になるためである。このような探索処理をソフトウェアで実現する場合には、分岐処理が頻繁に発生するプログラムが必要になるために処理速度が大幅に低下し、またハードウェアで実現する場合には、複雑な組み合わせ回路を必要とする。
【０００９】
また、有効桁数kの推定処理を参照テーブル（ルックアップテーブル）によって実現することを考えた場合、従来の適応型ゴロムライス符号化方式では参照テーブルが巨大化するという課題がある。たとえば、JPEG-LS等で標準的なパラメータとして、ゴロムライス符号化対象となる残差dが8ビットでReset=64の場合、aの範囲は[0,128×63]、nの範囲は[0,63]となり、約512kBのテーブルメモリが必要になる。このため、ハードウェア実装の場合には回路規模の増大、ソフトウェア実装の場合にはそれに加えてキャッシュミスヒットの多発による速度低下といった問題が生じる。
【００１０】
『発明の目的』
本発明の目的は、適応ゴロムライス符号化における有効桁数kを低コストで推定し得るようにすることにある。
【００１１】
本発明の別の目的は、適応ゴロムライス符号化における有効桁数kの推定を１回のテーブル参照だけで行えるようにすることにある。
【００１２】
本発明の他の目的は、適応ゴロムライス符号化・復号処理における回路規模および処理速度を改善すること、特に、汎用CPUによるソフトウェア処理で高速な符号化・復号処理を実現することにある。
【課題を解決するための手段】
【００１３】
本発明の第１の符号化装置は、過去に符号化した符号化対象値について、２進での有効桁数を算出して累積するとともに、累積回数をカウントする有効桁数累積手段と、前記有効桁数累積手段における有効桁数の累積値と累積回数を保持する有効桁数統計メモリと、前記有効桁数累積手段における有効桁数の累積値と累積回数を初期化する統計値初期化手段と、前記有効桁数の累積値と累積回数の組み合わせに対応する有効桁数推定値を求める有効桁数推定手段と、前記有効桁数推定値を用いて前記符号化対象値をゴロムライス符号化するゴロムライス符号化手段とを備えている。
【００１４】
本発明の第２の符号化装置は、第１の符号化装置において、入力信号を非負値に順位変換する順位変換手段を備え、前記非負値を前記符号化対象値とすることを特徴とする。
【００１５】
本発明の第３の符号化装置は、第１の符号化装置において、前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする。
【００１６】
本発明の第４の符号化装置は、第１の符号化装置において、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００１７】
本発明の第５の符号化装置は、第３の符号化装置において、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００１８】
本発明の第６の符号化装置は、第３または第５の符号化装置において、前記統計値初期化手段は、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする。
【００１９】
本発明の第７の符号化装置は、第５の符号化装置において、前記有効桁数統計メモリは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記有効桁数推定手段は、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする。
【００２０】
本発明の第１の復号装置は、過去にゴロムライス復号した結果値について、２進での有効桁数を算出して累積するとともに、累積回数をカウントする有効桁数累積手段と、前記有効桁数累積手段における有効桁数の累積値と累積回数を保持する有効桁数統計メモリと、前記有効桁数累積手段における有効桁数の累積値と累積回数を初期化する統計値初期化手段と、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める有効桁数推定手段と、前記有効桁数推定値を用いて入力符号をゴロムライス復号するゴロムライス復号手段とを備えている。
【００２１】
本発明の第２の復号装置は、第１の復号装置において、ゴロムライス復号の結果値を逆順位変換して信号値を生成する順位逆変換手段を備えることを特徴とする。
【００２２】
本発明の第３の復号装置は、第１の復号装置において、前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする。
【００２３】
本発明の第４の復号装置は、第１の復号装置において、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００２４】
本発明の第５の復号装置は、第３の復号装置において、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを備え、前記有効桁数推定手段は、前記累積値と前記累積回数とから前記有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００２５】
本発明の第６の復号装置は、第３または第５の復号装置において、前記統計値初期化手段は、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする。
【００２６】
本発明の第７の復号装置は、第５の復号装置において、前記有効桁数統計メモリは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記有効桁数推定手段は、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記有効桁数累積手段は、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする。
【００２７】
本発明の第１の符号化方法は、コンピュータを用いて符号化を行う符号化方法であって、前記コンピュータが、有効桁数統計メモリに保持された有効桁数の累積値と累積回数を初期化する第１のステップ、前記コンピュータが、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める第２のステップ、前記コンピュータが、前記有効桁数推定値を用いて符号化対象値をゴロムライス符号化する第３のステップ、前記コンピュータが、前記ゴロムライス符号化した符号化対象値について、２進での有効桁数を算出して前記有効桁数統計メモリに保持された累積値に加算し且つ前記累積回数を更新する第４のステップを含んでいる。
【００２８】
本発明の第２の符号化方法は、第１の符号化方法において、入力信号を非負値に順位変換した値を前記符号化対象値とすることを特徴とする。
【００２９】
本発明の第３の符号化方法は、第１の符号化方法において、前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする。
【００３０】
本発明の第４の符号化方法は、第１の符号化方法において、前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００３１】
本発明の第５の符号化方法は、第３の符号化方法において、前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００３２】
本発明の第６の符号化方法は、第３または第５の符号化方法において、前記第１のステップでは、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルでは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする。
【００３３】
本発明の第７の符号化方法は、第５の符号化方法において、前記有効桁数統計メモリでは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記第２のステップでは、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする。
【００３４】
本発明の第１の復号方法は、コンピュータを用いて入力符号の復号を行う復号方法であって、前記コンピュータが、有効桁数統計メモリに保持された有効桁数の累積値と累積回数を初期化する第１のステップ、前記コンピュータが、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を求める第２のステップ、前記コンピュータが、前記有効桁数推定値を用いて入力符号をゴロムライス復号する第３のステップ、前記コンピュータが、ゴロムライス復号の結果値について、２進での有効桁数を算出して前記有効桁数統計メモリに保持された累積値に加算し且つ前記累積回数を更新する第４のステップを含んでいる。
【００３５】
本発明の第２の復号方法は、第１の復号方法において、前記第４のステップでは、さらに、ゴロムライス復号の結果値を逆順位変換して信号値を生成することを特徴とする。
【００３６】
本発明の第３の復号方法は、第１の復号方法において、前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、累積値と累積回数とを２で除することを特徴とする。
【００３７】
本発明の第４の復号方法は、第１の復号方法において、前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００３８】
本発明の第５の復号方法は、第３の復号方法において、前記第２のステップでは、前記有効桁数の累積値と前記累積回数の組み合わせに対応する有効桁数推定値を保持する有効桁数推定テーブルを参照して前記有効桁数推定値を求めることを特徴とする。
【００３９】
本発明の第６の復号方法は、第３または第５の復号方法において、前記第１のステップでは、累積回数の初期値として、前記上限値の２分の１以上の値を設定し、前記有効桁数推定テーブルでは、累積回数が前記上限値の２分の１以上となる要素についてのみ前記有効桁数推定値を保持することを特徴とする。
【００４０】
本発明の第７の復号方法は、第５の復号方法において、前記有効桁数統計メモリでは、累積回数を上位ビットに、累積値を下位ビットにそれぞれ対応付けた統計値を保持し、前記第２のステップでは、前記統計値から前記有効桁数推定テーブルを参照することによって有効桁数推定値を求め、前記第４のステップでは、前記累積回数があらかじめ定められた上限値に達した場合に、前記統計値を２で除することを特徴とする。
【００４１】
『作用』
本発明の符号化装置とその方法にあっては、符号化対象値そのものを累積するのではなく、過去に符号化した符号化対象値の有効桁数を累積し、この有効桁数の累積値と累積回数の組み合わせに対応する有効桁数推定値を求める。同様に本発明の復号装置とその方法にあっては、ゴロムライス復号された結果値そのものを累積するのではなく、過去のゴロムライス復号された結果値の有効桁数を累積し、この有効桁数の累積値と累積回数の組み合わせに対応する有効桁数推定値を求める。
【００４２】
有効桁数を累積しているので、有効桁数推定値の算出は、有効桁数の累積値を累積回数で除することで求めることができる。有効桁数推定値は、その都度除算の計算を行って求めても良いし、事前に用意された有効桁数推定テーブルを参照して求めても良い。
【発明の効果】
【００４３】
本発明によれば、適応ゴロムライス符号化における有効桁数を低コストで推定することができる。その理由は、符号化時においては、符号化対象値そのものを累積するのではなく、過去に符号化した符号化対象値の有効桁数を累積し、この有効桁数の累積値と累積回数との組み合わせに対応する有効桁数推定値を求めるためである。また、復号時においては、ゴロムライス復号された結果値そのものを累積するのではなく、過去のゴロムライス復号された結果値の有効桁数を累積し、この有効桁数の累積値と累積回数との組み合わせに対応する有効桁数推定値を求めるためである。
【００４４】
特に有効桁数推定テーブルを用いる構成によれば、適応ゴロムライス符号化における有効桁数の推定を１回のテーブル参照だけで行える効果がある。この場合、本発明では、信号の絶対値ではなく有効桁数を累積するため、絶対値を累積する方式に比べて累積値のとり得る範囲を小さく抑えることができ、有効桁数推定テーブルのサイズを縮小することができる。
【００４５】
以上のことから、本発明によれば、適応ゴロムライス符号化・復号処理における回路規模および処理速度を改善でき、特に、汎用CPUによるソフトウェア処理で高速な符号化・復号処理を実現することができる。
【発明を実施するための最良の形態】
【００４６】
次に、本発明を実施するための最良の形態について図面を参照して詳細に説明する。
【００４７】
図１を参照すると、本発明の実施の形態にかかる符号化装置は、信号入力装置１１と、データ記憶装置１２と、プログラム制御により動作するデータ処理装置１３と、符号出力装置１４とから構成されている。
【００４８】
データ記憶装置１２は、有効桁数統計メモリ１２１、有効桁数推定テーブル１２２、有効桁数推定値メモリ１２３、順位変換値メモリ１２４、信号値メモリ１２５を含む。また、有効桁数統計メモリ１２１は、有効桁数累積値メモリ１２１１と有効桁数累積回数メモリ１２１２とを含む。
【００４９】
有効桁数推定テーブル１２２は、整数aと整数nの組み合わせからfloor(a/n)の演算結果を引くことのできるテーブルである（floor(x)はx以下の最大の整数値を表す）。ここで、整数aは有効桁数累積値aに、整数nは有効桁数累積回数nにそれぞれ対応し、floor(a/n)が有効桁数kに対応する。
【００５０】
データ処理装置１３は、統計値初期化手段１３１、有効桁数推定手段１３２、有効桁数累積手段１３３、ゴロムライス符号化手段１３４、順位変換手段１３５を含む。
【００５１】
これらの手段はそれぞれ概略つぎのように動作する。
【００５２】
統計値初期化手段１３１は、有効桁数統計メモリ１２１の内容を、あらかじめ決められた初期値に設定する。
【００５３】
信号入力装置１１からは、固定ビット長の整数（たとえば-127から128まで）の信号値dが順次入力される。
【００５４】
順位変換手段１３５は、信号入力装置１１から信号値dが信号値メモリ１２５に読み込まれると、信号値dを非負の値mに順位変換し、順位変換値メモリ１２４に格納する。順位変換のための演算として、たとえば、d≧0の場合m=2d,d＜0の場合m=-2d-1とする方法がある。
【００５５】
有効桁数推定手段１３２は、有効桁数統計メモリ１２１内の有効桁数累積値メモリ１２１１の値aと有効桁数累積回数メモリ１２１２の値nで有効桁数推定テーブル１２２を参照して有効桁数推定値kを算出し、有効桁数推定値メモリ１２３へ格納する。
【００５６】
ゴロムライス符号化手段１３４は、順位変換値メモリ１２４および有効桁数推定メモリ１２３からm,kを読み出し、mをパラメータkでゴロムライス符号化し、符号出力装置１４へ出力する。
【００５７】
有効桁数累積手段１３３は、順位変換値メモリ１２４からmを読み出し、mの有効桁数を算出して有効桁数統計メモリ１２１の内容を更新する。具体的には、有効桁数累積回数メモリ１２１２の値(n)に1を加え、有効桁数累積値メモリ１２１１の値(a)にmの有効桁数を加算する。また、この結果、nがあらかじめ定められたReset値に達した場合、有効桁数累積手段１３３は、nおよびaの値をそれぞれ半分に再スケールし、有効桁数累積回数メモリ１２１２および有効桁数累積値メモリ１２１１に格納する。
【００５８】
次に、図１及び図２のフローチャートを参照して、本実施の形態にかかる符号化装置の全体の動作について詳細に説明する。
【００５９】
まず統計値初期化手段１３１が、有効桁数統計メモリ１２１内の有効桁数累積値メモリ１２１１および有効桁数累積回数メモリ１２１２の内容a,nを、あらかじめ定められた初期値に設定する（図２のステップＳ１０１）。
【００６０】
その後、信号入力装置１１から固定ビット長の整数（たとえば-127から128まで）の信号値dが入力されると、その信号値dは信号値メモリ１２５に読み込まれる（ステップＳ１０２）。
【００６１】
次に順位変換手段１３５が、信号値メモリ１２５から信号値dを読み出し、この信号値dを非負の値mに順位変換し、順位変換値メモリ１２４に格納する（ステップＳ１０３）
【００６２】
次に有効桁数推定手段１３２が、有効桁数統計メモリ１２１内の有効桁数累積値メモリ１２１１の値aと有効桁数累積回数メモリ１２１２の値nで有効桁数推定テーブル１２２を参照して有効桁数推定値kを算出し、有効桁数推定値メモリ１２３へ格納する（ステップＳ１０４）。
【００６３】
次にゴロムライス符号化手段１３４が、順位変換値メモリ１２４および有効桁数推定メモリ１２３からm,kを読み出し、mをパラメータkでゴロムライス符号化し、符号出力装置１４へ出力する（ステップＳ１０５）。
【００６４】
次に有効桁数累積手段１３３が、順位変換値メモリ１２４からmを読み出し、mの有効桁数を算出して有効桁数統計メモリ１２１の内容を更新する。具体的には、有効桁数累積回数メモリ１２１２の値(n)に1を加え、有効桁数累積値メモリ１２１１の値(a)にmの有効桁数を加算する。この結果nがあらかじめ定められたReset値に達した場合、nおよびaの値をそれぞれ半分に再スケールし、有効桁数累積回数メモリ１２１２および有効桁数累積値メモリ１２１１に格納する（ステップＳ１０６）。
【００６５】
その後、全ての入力信号について処理が完了したかが判定され（ステップＳ１０７）、未処理の入力信号があれば入力信号の読み込み（ステップＳ１０２）に戻る。
【００６６】
次に、本実施の形態の効果について説明する。
【００６７】
本実施の形態では、有効桁数推定手段１３２および有効桁数推定テーブル１２２により、１回のテーブル参照だけで有効桁数の推定を行うことができるため、除算処理および条件分岐が不要となる。これにより、高速な符号化処理が可能となる。特に、条件分岐が無くなることで、汎用CPUでの符号化処理が高速化される。
【００６８】
また、有効桁数推定テーブル１２２は、たとえば入力信号が8ビットで、Reset=64の場合、32768要素(32kB)で構成可能である。これは、mの有効桁数が最大で8であることから、累積値aの範囲が[0,8×63]、nの値の範囲が[0,63]となるためである。これにより、符号化装置をハードウェアで実現する場合には回路面積の縮小が可能になり、符号化装置をCPU上で動作するプログラムで実現する場合にはキャッシュヒット率向上による高速化が達成される。さらに、nの初期値として、Reset値の半分(32)を与えるようにすれば、nの値の範囲を[32,63]とすることができるため、テーブルの要素数を更に半分（16384要素,16kB）にすることができ、符号化装置をハードウェアで実現する場合には回路面積のより一層の縮小が可能になり、符号化装置をCPU上で動作するプログラムで実現する場合にはキャッシュヒット率のより一層の向上による高速化が達成される。
【００６９】
以上のように、本実施の形態にかかる符号化装置では、有効桁数kの推定を高速に行うことができ、汎用CPUで、特許文献１の方式に比べて約1.5〜2倍の高速化が達成される。なお、ゴロムライス符号化対象信号の絶対値ではなくその有効桁数を累積するため、特許文献１の方式に比べて統計の精度が若干低下するが、その影響は圧縮率にして約0.5%と僅かである。
【００７０】
なお、上記説明では、有効桁数推定テーブル１２２にfloor(a/n)を格納するものとしたが、たとえば入力信号が8bitの場合には、有効桁数推定値が8以上になると圧縮率が低下するため、上限値を7にするようにしてもよい。
【００７１】
また、上記説明では、信号入力装置１１から入力される信号値をゴロムライス符号化対象としたが、データ処理装置１３によって別途処理した値をゴロムライス符号化対象としてもよい。たとえば、DPCMなどで予測差分を求め、その差分値をゴロムライス符号化対象にしてもよい。
【００７２】
また、上記説明では、有効桁数累積値メモリ１２１１と有効桁数累積回数メモリ１２１２とを別のメモリとして扱っているが、後述する実施例で説明するように、これらを結合して単一のレジスタに保持するようにしてもよい。その場合、Resetの値は2の倍数とし、nをレジスタの上位、aを下位に割り当てておくことが望ましい。これにより、テーブル参照のための引数として直接そのレジスタ値が利用でき、また、再スケール時のシフト演算も、単一レジスタに対して処理するだけでよい。このため、特に汎用CPUにおいて高速化が達成される。
【００７３】
次に、本発明の実施の形態にかかる復号装置について図面を参照して詳細に説明する。
【００７４】
図３を参照すると、本発明の実施の形態にかかる復号装置は、符号入力装置２１と、データ記憶装置２２と、プログラム制御により動作するデータ処理装置２３と、信号出力装置２４とから構成されている。
【００７５】
データ記憶装置２２は、有効桁数統計メモリ２２１、有効桁数推定テーブル２２２、有効桁数推定値メモリ２２３、順位変換値メモリ２２４、信号値メモリ２２５を含む。また、有効桁数統計メモリ２２１は、有効桁数累積値メモリ２２１１と有効桁数累積回数メモリ２２１２とを含む。
【００７６】
有効桁数推定テーブル２２２は、整数aと整数nの組み合わせからfloor(a/n)の演算結果を引くことのできるテーブルである（floor(x)はx以下の最大の整数値を表す）。ここで、整数aは有効桁数累積値aに、整数nは有効桁数累積回数nにそれぞれ対応し、floor(a/n)が有効桁数kに対応する。
【００７７】
データ処理装置２３は、統計値初期化手段２３１、有効桁数推定手段２３２、有効桁数累積手段２３３、ゴロムライス復号手段２３４、順位逆変換手段２３５を含む。
【００７８】
これらの手段はそれぞれ概略つぎのように動作する。
【００７９】
まず、統計値初期化手段２３１は、有効桁数統計メモリ２２１内の有効桁数累積値メモリ２２１１および有効桁数累積回数メモリ２２１２の内容を、あらかじめ定められた初期値に設定する。
【００８０】
符号入力装置２１からは、図１に示した符号化装置でゴロムライス符号化された可変ビット長の符号が順次入力される。
【００８１】
有効桁数推定手段２３２は、有効桁数統計メモリ２２１内の有効桁数累積値メモリ２２１１の値aと有効桁数累積回数メモリ２２１２の値nで有効桁数推定テーブル２２２を参照して有効桁数推定値kを算出し、有効桁数推定値メモリ２２３へ格納する。
【００８２】
ゴロムライス復号手段２３４は、有効桁数推定メモリ２２３の値kに基づいて、符号入力装置２１から入力されたゴロムライス符号を復号し、復号結果の値を順位変換値mとして順位変換値メモリ２２４に格納する。
【００８３】
有効桁数累積手段２３３は、順位変換値メモリ２２４からmを読み出し、mの有効桁数を算出して有効桁数統計メモリ２２１の内容を更新する。具体的には、有効桁数累積回数メモリ２２１２の値(n)に1を加え、有効桁数累積値メモリ２２１１の値(a)にmの有効桁数を加算する。また、この結果、nがあらかじめ定められたReset値に達した場合、有効桁数累積手段２３３は、nおよびaの値をそれぞれ半分に再スケールし、有効桁数累積回数メモリ２２１２および有効桁数累積値メモリ２２１１に格納する。
【００８４】
順位逆変換手段２３５は、順位変換値メモリ２２４から読み出した非負の値mを順位逆変換し、信号値dとして信号値メモリ２２５に格納する。
【００８５】
信号出力装置２４は、信号値メモリ２２５から信号値dを読み出して出力する。
【００８６】
次に、図３及び図４のフローチャートを参照して、本実施の形態の全体の動作について詳細に説明する。
【００８７】
まず、統計値初期化手段２３１が、有効桁数統計メモリ２２１内の有効桁数累積値メモリ２２１１および有効桁数累積回数メモリ２２１２の内容a,nを、あらかじめ定められた初期値に設定する（図４のステップＳ２０１）。
【００８８】
その後、符号入力装置２１から可変ビット長のゴロムライス符号を順次読み込む（ステップＳ２０２）。読み込まれたゴロムライス符号に対して、まず有効桁数推定手段２３２が、有効桁数統計メモリ２２１内の有効桁数累積値メモリ２２１１の値aと有効桁数累積回数メモリ２２１２の値nで有効桁数推定テーブル２２２を参照して有効桁数推定値kを算出し、有効桁数推定値メモリ２２３へ格納する（ステップＳ２０３）。
【００８９】
次にゴロムライス復号手段２３４が、有効桁数推定値メモリ２２３から有効桁数推定値kを読み出し、このkに基づいて、符号入力装置２１から前記入力されたゴロムライス符号を復号し、順位変換値mとして順位変換値メモリ２２４に格納する（ステップＳ２０４）。
【００９０】
次に有効桁数累積手段２３３が、順位変換値メモリ２２４からmを読み出し、mの有効桁数を算出して有効桁数統計メモリ２２１の内容を更新する。具体的には、有効桁数累積回数メモリ２２１２の値(n)に1を加え、有効桁数累積値メモリ２２１１の値(a)にmの有効桁数を加算する。この結果、nがあらかじめ定められたReset値に達した場合、nおよびaの値をそれぞれ半分に再スケールし、有効桁数累積回数メモリ２２１２および有効桁数累積値メモリ２２１１に格納する（ステップＳ２０５）。
【００９１】
次に順位逆変換手段２３５が、非負の値mを順位逆変換し、信号値dとして信号値メモリ２２５を通じて信号出力装置２４へ出力する（ステップＳ２０６）。順位逆変換のための演算として、たとえば、mが偶数のときd=m/2、mが奇数のときd=-(m+1)/2とする方法がある。なお、ステップＳ２０６の順位逆変換処理とステップＳ２０５の有効桁数累積処理の順序は入れ替えても良い。
【００９２】
その後、全ての入力符号について処理が完了したかが判定され（ステップＳ２０７）、未処理の入力符号があれば入力符号の読み込み（ステップＳ２０２）に戻る。
【００９３】
次に、本実施の形態の効果について説明する。
【００９４】
本実施の形態では、有効桁数推定手段２３２および有効桁数推定テーブル２２２により、１回のテーブル参照だけで有効桁数の推定を行うことができるため、除算処理および条件分岐が不要となる。これにより、高速な復号処理が可能となる。特に、条件分岐が無くなることで、汎用CPUでの復号処理が高速化される。
【００９５】
また、有効桁数推定テーブル２２２は、たとえば順位変換値mが8ビットで、Reset=64の場合、32768要素(32kB)で構成可能である。これは、mの有効桁数が最大で8であることから、累積値aの範囲が[0,8×63]、nの値の範囲が[0,63]となるためである。これにより、復号装置をハードウェアで実現する場合には回路面積の縮小が可能になり、復号装置をCPU上で動作するプログラムで実現する場合にはキャッシュヒット率向上による高速化が達成される。さらに、nの初期値として、Reset値の半分(32)を与えるようにすれば、nの値の範囲を[32,63]とすることができるため、テーブルの要素数を更に半分（16384要素,16kB）にすることができ、復号装置をハードウェアで実現する場合には回路面積のより一層の縮小が可能になり、復号装置をCPU上で動作するプログラムで実現する場合にはキャッシュヒット率のより一層の向上による高速化が達成される。
【００９６】
なお、上記説明では、有効桁数推定テーブル２２２にfloor(a/n)を格納するものとしたが、図１の符号化装置と同様な上限値を設けるようにしてもよい。
【００９７】
また、上記説明では、有効桁数累積値メモリ２２１１と有効桁数累積回数メモリ２２１２とを別のメモリとして扱っているが、後述する実施例で説明するように、これらを結合して単一のレジスタに保持するようにしてもよい。その場合、Resetの値は2の倍数とし、nをレジスタの上位、aを下位に割り当てておくことが望ましい。これにより、テーブル参照のための引数として直接そのレジスタ値が利用でき、また、再スケール時のシフト演算も、単一レジスタに対して処理するだけでよい。このため、特に汎用CPUにおいて高速化が達成される。
【実施例】
【００９８】
以下、図５〜図６を参照して、本発明の実施形態の具体的な実施例について説明する。
【００９９】
図５は、本発明の実施の形態にかかる符号化装置の一実施例の符号化動作を模式的に示した図である。本実施例では、データ処理装置１３としてパーソナルコンピュータを、データ記憶装置１２として半導体メモリ（パーソナルコンピュータに含まれる）を、符号出力装置１４として磁気ディスク装置を備えているものとする。また、入力信号データは、各8ビットの符号付き整数として、磁気ディスク装置上のファイルから与えられるものとする。さらに、符号化プログラムが磁気ディスク装置等のコンピュータ可読記録媒体に記録されており、起動時などにデータ処理装置１３に読み取られる。符号化プログラムは、データ処理装置１３の動作を制御することにより、データ処理装置１３上に統計値初期化手段１３１、有効桁数推定手段１３２、有効桁数累積手段１３３、ゴロムライス符号化手段１３４および順位変換手段１３５を実現し、図２に示した処理を実行させる。
【０１００】
図５を参照すると、有効桁数推定テーブルＺ１０１には、各nおよびaに対応する有効桁数推定値kのデータがあらかじめ格納されている。また、統計値初期化手段１３１によって、有効桁数統計メモリ１２１はＺ１０２の値で初期化されるものとする。
【０１０１】
有効桁数推定テーブルＺ１０１は、nとaとを結合した値でテーブルを引くことができる。たとえば、n=8,a=31の場合には、nの２進表現である"1000"とaの２進表現である"0011111"とが結合された"10000011111"の位置のテーブルが参照され、k=3が得られる。
【０１０２】
本実施例では、Reset=16とし、nの初期値として"1000"すなわち8を与えている。このため、nの範囲は8〜15となり、有効桁数推定テーブルＺ１０１はn=8以上のみ保持している。
【０１０３】
また、入力信号データが各8ビットであるため、テーブルＺ１０１内のk値の上限は7となっている。たとえば、n=8(1000),a=127(1111111)の場合、本来のfloor(a/n)は15となるが、上限値である7を超えているため、テーブル上には7という値が格納されている。
【０１０４】
有効桁数統計メモリ１２１は、Ｚ１０２に示す形式で構成しており、単一の変数（レジスタ）上にnとaとを結合された形で保持している。最上位のRsはReset判定用のビットであり、これも同一レジスタ上に配置されている。詳しくは後述する。
【０１０５】
まず、磁気ディスクから入力信号Ｚ１０３が読み込まれる。読み込まれた信号値はd=-12である。これが、非負の値となるよう順位変換される。d≧0の場合m=2d,d＜0の場合m=-2d-1として変換すると、m=23(00010111)となる。
【０１０６】
有効桁数累積手段１３３は、n=8,a=31から有効桁数統計メモリＺ１０２を参照し、有効桁数の推定値としてk=3を得る。
【０１０７】
ゴロムライス符号化手段１３４は、m=23をk=3でゴロムライス符号化し、符号データＺ１０４（001 111）を磁気ディスクへ出力する。
【０１０８】
有効桁数累積手段１３３は、有効桁数統計メモリＺ１０２のnの値に１を加え、aの値にm=23(00010111)の有効桁数である5を加える。この結果、有効桁数統計メモリはＺ１０５に示すように"0 1001 0100100"となる。
【０１０９】
以降も同様に、入力信号が読み込まれて符号化が行われる。有効桁数統計メモリ１２１がＺ１０５の状態では、有効桁数の推定値はk=4となり、kの値が適応的に変化して信号が圧縮される。
【０１１０】
こうした符号化が継続し、n=15(1111)、a=69(1000101)となった状態の有効桁数統計メモリ１２１をＺ１０６に示す。この状態から、有効桁数累積手段１３３がnに１、aに4を加えた場合、有効桁数統計メモリの状態はＺ１０７（1 0000 1001001）となる。
【０１１１】
この状態では、n=16、すなわちResetに達したことで、Rsのビットが立っている、Rsが立っている場合には、再スケール処理が行われる。ここでは、Rs,n,aを結合した状態で1ビット右シフトを行うことで実現できる。
【０１１２】
この結果、有効桁数統計メモリ１２１はＺ１０８の状態、すなわちn=8(1000)、a=34(0100100)となる。
【０１１３】
なお、再スケール処理が上記方法で実現できる理由は、nがReset=16に達した場合にはnの最下位ビットが0となり、結合状態で右シフトを行ってもaの値に影響を与えないためである。
【０１１４】
また、本方式では、以下に説明するように桁あふれについても問題が発生することはない。
【０１１５】
mの最大有効桁は8であるため、有効桁数累積手段１３３によって、aに加算される値は最大で8である。これがn=8の状態から（Resetを経ることなく）8回繰り返された場合、aの値は64となって、一時的に有効桁数統計メモリ１２１のaのビット幅を超える。
【０１１６】
しかし、その場合、必ず同時にn=16となっているため、有効桁数統計メモリ１２１の値は"1 0001 0000000"となる。したがって、その直後の再スケール処理によって有効桁数統計メモリ１２１の値は"0 1000 1000000"となり、桁あふれに伴う問題は回避することができる。
【０１１７】
なお、本方式では、Resetが2の倍数であり、かつ、nをレジスタの上位、aを下位として結合している場合に限り、桁あふれの問題を回避できる。nを上位、aを下位とする理由は、逆にするとReset時の桁あふれで問題が発生するからである（累積値aの最下位ビットは、Reset時に必ず0になっているとは限らないため）。
【０１１８】
図６は、本発明の実施の形態にかかる復号装置の一実施例による復号動作を模式的に示した図である。本実施例では、データ処理装置２３としてパーソナルコンピュータを、データ記憶装置２２として半導体メモリ（パーソナルコンピュータに含まれる）を、信号出力装置２４として磁気ディスク装置を備えているものとする。また、入力符号データは、磁気ディスク装置上のファイルから与えられるものとする。さらに、復号プログラムが磁気ディスク装置等のコンピュータ可読記録媒体に記録されており、起動時などにデータ処理装置２３に読み取られる。復号プログラムは、データ処理装置２３の動作を制御することにより、データ処理装置２３上に統計値初期化手段２３１、有効桁数推定手段２３２、有効桁数累積手段２３３、ゴロムライス符号化手段２３４および順位変換手段２３５を実現し、図４に示した処理を実行させる。
【０１１９】
図６を参照すると、有効桁数推定テーブルＺ２０１には、各nおよびaに対応する有効桁数推定値kのデータがあらかじめ格納されている。また、統計値初期化手段２３１によって、有効桁数統計メモリ２２１はＺ２０２の値で初期化されるものとする。
【０１２０】
有効桁数推定テーブル２２２および有効桁数統計メモリ２２１の構成および初期値は、図５を参照して説明した符号化装置の実施例と同様である。
【０１２１】
まず、磁気ディスクから入力符号Ｚ２０３が読み込まれる。読み込まれた符号は"001 111"である。
【０１２２】
有効桁数累積手段２３３は、n=8,a=31から有効桁数統計メモリＺ２０２を参照し、有効桁数の推定値としてk=3を得る。
【０１２３】
ゴロムライス復号手段２３４は、符号"001 111"をk=3でゴロムライス復号し、m=23を得る。
【０１２４】
有効桁数累積手段２３３は、有効桁数統計メモリＺ２０２のnの値に１を加え、aの値にm=23(00010111)の有効桁数である5を加える。この結果、有効桁数統計メモリ２２１はＺ２０５に示すように"0 1001 0100100"となる。
【０１２５】
順位逆変換手段２３５は、非負の値mを信号値dへ順位逆変換する。mが偶数のときd=m/2、mが奇数のときd=-(m+1)/2として変換すると、Ｚ２０４のように、d=-12となる。
【０１２６】
こうして得られた信号データＺ２０４が磁気ディスクへ出力される。
【０１２７】
以降も同様に、入力符号が読み込まれて復号が行われる。有効桁数統計メモリ２２１がＺ２０５の状態では、有効桁数の推定値はk=4となり、kの値が適応的に変化して符号が展開される。
【０１２８】
復号が継続し、n=15(1111)、a=69(1000101)となった状態の有効桁数統計メモリ２２１がＺ２０６である。この状態から有効桁数累積手段２３３が累積処理を行った場合の動作は、実施例１（図５のＺ１０６〜Ｚ１０８）と同様であり、Ｚ２０６〜Ｚ２０８のようにして再スケール処理が行われる。
【産業上の利用可能性】
【０１２９】
本発明によれば、画像信号や音声信号の予測差分符号化において、信号を高速に符号化・復号して伝送するといった用途に適用できる。
【図面の簡単な説明】
【０１３０】
【図１】本発明の実施の形態にかかる符号化装置のブロック図である。
【図２】本発明の実施の形態にかかる符号化装置による符号化処理の流れを示すフローチャートである。
【図３】本発明の実施の形態にかかる復号装置のブロック図である。
【図４】本発明の実施の形態にかかる復号装置による復号処理の流れを示すフローチャートである。
【図５】本発明の符号化装置の一実施例の動作を模式的に示す図である。
【図６】本発明の復号装置の一実施例の動作を模式的に示す図である。
【符号の説明】
【０１３１】
１１…信号入力装置
１２…データ記憶装置
１２１…有効桁数統計メモリ
１２１１…有効桁数累積値メモリ
１２１２…有効桁数累積回数メモリ
１２２…有効桁数推定テーブル
１２３…有効桁数推定値メモリ
１２４…順位変換値メモリ
１２５…信号値メモリ
１３…データ処理装置
１３１…統計値初期化手段
１３２…有効桁数推定手段
１３３…有効桁数累積手段
１３４…ゴロムライス符号化手段
１３５…順位変換手段
１４…符号出力装置
２１…符号入力装置
２２…データ記憶装置
２２１…有効桁数統計メモリ
２２１１…有効桁数累積値メモリ
２２１２…有効桁数累積回数メモリ
２２２…有効桁数推定テーブル
２２３…有効桁数推定値メモリ
２２４…順位変換値メモリ
２２５…信号値メモリ
２３…データ処理装置
２３１…統計値初期化手段
２３２…有効桁数推定手段
２３３…有効桁数累積手段
２３４…ゴロムライス復号手段
２３５…順位逆変換手段
２４…符号出力装置
【図１】
2008072562.tif 000003
【図２】
2008072562.tif 000004
【図３】
2008072562.tif 000005
【図４】
2008072562.tif 000006
【図５】
2008072562.tif 000007
【図６】
2008072562.tif 000008