(57)【要約】【課題】符号範囲を用いた符号化および復号化において、処理速度の高速化を図る。【解決手段】符号範囲特定値によって設定される符号範囲を処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返すことで、シンボル列を符号化する符号化システムを提供する。この符号化システムは、符号範囲の幅を総出現頻度で除算した除算値に基づいて、シフト量を設定するシフト量算出部と、このシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する符号範囲更新部とを有する。【選択図】図１
2007082058.tif 000002
【特許請求の範囲】
【請求項１】
符号範囲特定値によって設定される符号範囲を処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返し、当該繰り返し処理によって得られた演算結果を符号化することによって、複数のシンボルで構成されたシンボル列を符号化する符号化システムにおいて、
シンボル列に含まれるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値を記憶する記憶部と、
シンボル列よりシンボルが処理対象として読み込まれる毎に、当該読み込まれたシンボルのシンボル種に対応したカウント値を更新する更新部と、
今回の処理対象として一のシンボルが読み込まれた場合、前記更新部によって前記一のシンボルのシンボル種に対応したカウント値が更新されるのに先立ち、前記記憶部に記憶されている出現頻度を読み出して、前記一のシンボルのシンボル種に対応したカウント値に対して、今回の処理対象で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する符号範囲更新部と、
前記符号範囲更新部よって更新された符号範囲特定値により特定される符号範囲の幅を、カウント値によって特定される総出現頻度で除算した除算値を２nで近似し、当該近似によって得られた値ｎを次回の処理対象で用いられるシフト量として設定するシフト量算出部と
を有することを特徴とする符号化システム。
【請求項２】
前記符号範囲更新部の更新処理によって、前記符号範囲の幅が所定値よりも小さくなった場合、または、前記符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合、今回の処理対象の処理によって更新された前記符号範囲特定値を符号化データとして出力する判定部をさらに有することを特徴とする請求項１に記載された符号化システム。
【請求項３】
前記シフト量算出部は、前記総出現頻度に対して、前記近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出し、
前記符号範囲更新部は、前記近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる前記符号範囲を構成するシンボル種毎の各区間に割り当てることを特徴とする請求項１また２に記載された符号化システム。
【請求項４】
前記符号範囲は、前記符号範囲特定値である上限値、下限値または幅のうちの所定の組み合わせによって特定されることを特徴とする請求項１から３のいずれかに記載された符号化システム。
【請求項５】
符号範囲特定値によって設定される符号範囲を処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返し、当該繰り返し処理によって得られた演算結果を符号化することによって、複数のシンボルで構成されたシンボル列を符号化する符号化方法をコンピュータに実行させる符号化コンピュータ・プログラムおいて、
複数のシンボルで構成されたシンボル列のうち、一のシンボルを今回の処理対象として読み込む第１のステップと、
前記シンボル列に含まれるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値のうち、前記一のシンボルのシンボル種に対応したカウント値を更新する第２のステップと、
前記一のシンボルのシンボル種に対応したカウント値が更新されるのに先立ち、前記一のシンボルのシンボル種に対応したカウント値に対して、今回の処理対象で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する第３のステップと、
前記更新された符号範囲特定値により特定される符号範囲の幅をカウント値によって特定される総出現頻度で除算した除算値を２nで近似し、当該近似によって得られた値ｎを次回の処理対象で用いられるシフト量として設定する第４のステップと、
シンボル列において、処理対象となる一のシンボルを順次シフトさせながら、所定の出力条件を満たすまで、前記第１のステップから前記第４のステップまでの処理を繰り返す第５のステップと
を有することを特徴とする符号化方法をコンピュータに実行させる符号化コンピュータ・プログラム。
【請求項６】
前記出力条件は、前記符号範囲特定値の更新によって、前記符号範囲の幅が所定値よりも小さくなった場合、または、前記符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合であることを特徴とする請求項５に記載された符号化コンピュータ・プログラム。
【請求項７】
前記第４のステップは、前記総出現頻度に対して、前記近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出する第６のステップを含み、
前記第３のステップは、前記近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる前記符号範囲を構成するシンボル種毎の各区間に割り当てるステップを含むことを特徴とする請求項５または６に記載された符号化コンピュータ・プログラム。
【請求項８】
前記符号範囲は、前記符号範囲特定値である上限値、下限値または幅のうちの所定の組み合わせによって特定されることを特徴とする請求項５から７のいずれかに記載された符号化コンピュータ・プログラム。
【請求項９】
符号範囲特定値によって設定され、かつ、シンボルのシンボル種に応じた区間に分割された符号範囲から符号化データの値に対応した区間を特定し、当該特定された区間に対応するシンボルを出力する探索処理を繰り返し、当該繰り返しによって得られたシンボルを並べることによって、符号化データを複数のシンボルで構成されたシンボル列に復号化する復号化システムにおいて、
前記探索処理によって出力されるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値を記憶する記憶部と、
前記探索処理によってシンボルが出力される毎に、当該出力されたシンボルのシンボル種に対応したカウント値を更新する更新部と、
今回の処理対象として一のシンボルが出力された場合、前記更新部によって前記一のシンボルのシンボル種に対応したカウント値が更新されるのに先立ち、
前記記憶部に記憶されている出現頻度を読み出して、前記一のシンボルのシンボル種に対応したカウント値に対して、今回の処理で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、次回の処理で用いられる符号範囲特定値を設定する符号範囲更新部と、
前記符号範囲更新部よって設定された符号範囲特定値により特定される符号範囲の幅を、カウント値によって特定される総出現頻度で除算した除算値を２nで近似し、当該近似によって得られた値ｎを次回の処理で用いられるシフト量として設定するシフト量算出部と
を有することを特徴とする復号化システム。
【請求項１０】
前記符号範囲更新部の更新処理によって、前記符号範囲の幅が所定値よりも小さくなった場合、または、前記符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合、前記符号化データを前記上位ビット数のシフト量でビットシフトさせるシフト処理を行う判定部をさらに有することを特徴とする請求項９に記載された復号化システム。
【請求項１１】
前記シフト量算出部は、前記総出現頻度に対して、前記近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出し、
前記符号範囲更新部は、前記近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる前記符号範囲を構成するシンボル種毎の各区間に割り当てることを特徴とする請求項９また１０に記載された復号化システム。
【請求項１２】
前記符号範囲は、前記符号範囲特定値である上限値、下限値または幅のうちの所定の組み合わせによって特定されることを特徴とする請求項９から１１のいずれかに記載された復号化システム。
【請求項１３】
符号範囲特定値によって設定され、かつ、シンボルのシンボル種に応じた区間に分割された符号範囲から符号化データの値に対応した区間を特定し、当該特定された区間に対応するシンボルを出力する探索処理を繰り返し、当該繰り返しによって得られたシンボルを並べることによって、符号化データを複数のシンボルで構成されたシンボル列に復号化する復号化方法をコンピュータに実行させる復号化コンピュータ・プログラムおいて、
前記探索処理によって、前記符号化データから前記一のシンボルのシンボル種を出力する第１のステップと、
前記探索処理によって出力されるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値のうち、前記一のシンボルのシンボル種に対応したカウント値を更新する第２のステップと、
前記一のシンボルのシンボル種に対応したカウント値が更新されるのに先立ち、前記一のシンボルのシンボル種に対応したカウント値に対して、今回の処理対象で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する第３のステップと、
前記更新された符号範囲特定値により特定される符号範囲の幅をカウント値によって特定される総出現頻度で除算した除算値を２nで近似し、当該近似によって得られた値ｎを次回の処理対象で用いられるシフト量として設定する第４のステップと、
シンボル列において、処理対象となる一のシンボルを順次シフトさせながら、所定の判定条件を満たすまで、前記第１のステップから前記第４のステップまでの処理を繰り返す第５のステップと
を有することを特徴とする復号化方法をコンピュータに実行させる復号化コンピュータ・プログラム。
【請求項１４】
前記判定条件は、前記符号範囲特定値の更新によって、前記符号範囲の幅が所定値よりも小さくなった場合、または、前記符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合であることを特徴とする請求項１３に記載された復号化コンピュータ・プログラム。
【請求項１５】
前記第４のステップは、前記総出現頻度に対して、前記近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出する第６のステップを含み、
前記第３のステップは、前記近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる前記符号範囲を構成するシンボル種毎の各区間に割り当てるステップを含むことを特徴とする請求項１３また１４に記載された復号化コンピュータ・プログラム。
【請求項１６】
前記符号範囲は、前記符号範囲特定値である上限値、下限値または幅のうちの所定の組み合わせによって特定されることを特徴とする請求項１３から１５のいずれかに記載された復号化コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号範囲を処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返し、この繰り返し処理によって得られた演算結果を符号化することによって、複数のシンボルで構成されたシンボル列を符号化する技術に関する。
【背景技術】
【０００２】
エントロピー符号化の一つとして算術符号化がある。算術符号化は、シンボル列をひとつの符号語にする符号化であり、シンボルの出現確率を線分（符号範囲）を、シンボルのシンボル種（シンボルの種類）に応じた区間に分割する処理を繰り返すことで、最終的にその区間に含まれる一つの実数を出力する処理である。特許文献１には、この算術符号化において、処理速度を高速化を図る技術が開示されている。具体的には、シンボル種の出現頻度の最大値を２の累乗に維持することで、除算処理をシフト処理のみで実行する。
【０００３】
【特許文献１】特開平１０−３２４９６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に記載された符号化には、乗算処理が残り、この除算処理を行うための回路を別途設ける必要がある。この除算処理は、乗算処理と同様に複雑な回路を要し、符号化処理における処理速度の低下や、回路の大規模化を招く要因なる。また、算術符号化の符号範囲に類似するレンジコーダには適用ができない。
【０００５】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、符号化または復号化における乗算・除算処理を減らし、全体的な処理速度の高速化を図ることである。
【０００６】
また、本発明の別の目的は、乗算・除算を行う回路を削減することにより、回路の小規模化を図ることである。
【課題を解決するための手段】
【０００７】
かかる課題を解決するために、第１の発明は、符号範囲特定値によって設定される符号範囲を処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返し、この繰り返し処理によって得られた演算結果を符号化することによって、複数のシンボルで構成されたシンボル列を符号化する符号化システムを提供する。このシステムは、記憶部と、更新部と、符号範囲更新部と、シフト量算出部とを有する。記憶部は、シンボル列に含まれるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値を記憶する。更新部は、シンボル列よりシンボルが処理対象として読み込まれる毎に、読み込まれたシンボルのシンボル種に対応したカウント値を更新する。符号範囲更新部は、今回の処理対象として一のシンボルが読み込まれた場合、更新部によって一のシンボルのシンボル種に対応したカウント値が更新されるのに先立ち、記憶部に記憶されている出現頻度を読み出す。そして、符号範囲更新部は、一のシンボルのシンボル種に対応したカウント値に対して、今回の処理対象で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する。シフト量算出部は、符号範囲更新部よって更新された符号範囲特定値により特定される符号範囲の幅を、カウント値によって特定される総出現頻度で除算した除算値を２nで近似し、この近似によって得られた値ｎを次回の処理対象で用いられるシフト量として設定する。
【０００８】
ここで、第１の発明において、符号範囲更新部の更新処理によって、符号範囲の幅が所定値よりも小さくなった場合、または、符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合、今回の処理対象の処理によって更新された符号範囲特定値を符号化データとして出力する判定部をさらに設けてもよい。
【０００９】
また、第１の発明において、シフト量算出部は、総出現頻度に対して、近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出することが好ましい。この場合、符号範囲更新部は、近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる符号範囲を構成するシンボル種毎の各区間に割り当てる。
【００１０】
第２の発明は、符号範囲特定値によって設定される符号範囲を処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返し、この繰り返し処理によって得られた演算結果を符号化することによって、複数のシンボルで構成されたシンボル列を符号化する符号化方法をコンピュータに実行させる符号化コンピュータ・プログラムを提供する。このプログラムは、複数のシンボルで構成されたシンボル列のうち、一のシンボルを今回の処理対象として読み込む第１のステップと、シンボル列に含まれるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値のうち、一のシンボルのシンボル種に対応したカウント値を更新する第２のステップと、一のシンボルのシンボル種に対応したカウント値が更新されるのに先立ち、一のシンボルのシンボル種に対応したカウント値に対して、今回の処理対象で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する第３のステップと、更新された符号範囲特定値により特定される符号範囲の幅をカウント値によって特定される総出現頻度で除算した除算値を２nで近似し、この近似によって得られた値ｎを次回の処理対象で用いられるシフト量として設定する第４のステップと、シンボル列において、処理対象となる一のシンボルを順次シフトさせながら、所定の出力条件を満たすまで、第１のステップから第４のステップまでの処理を繰り返す第５のステップとを有する符号化方法をコンピュータに実行させる。
【００１１】
ここで、第２の発明において、出力条件は、符号範囲特定値の更新によって、符号範囲の幅が所定値よりも小さくなった場合、または、符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合であってもよい。
【００１２】
また、第２の発明において、第４のステップは、総出現頻度に対して、近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出する第６のステップを含むことが好ましい。この場合、第３のステップは、近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる符号範囲を構成するシンボル種毎の各区間に割り当てるステップを含んでいてもよい。
【００１３】
第３の発明は、符号範囲特定値によって設定され、かつ、シンボルのシンボル種に応じた区間に分割された符号範囲から符号化データの値に対応した区間を特定し、この特定された区間に対応するシンボルを出力する探索処理を繰り返し、この繰り返しによって得られたシンボルを並べることによって、符号化データを複数のシンボルで構成されたシンボル列に復号化する復号化システムを提供する。このシステムは、記憶部と、更新部と、符号範囲更新部と、シフト量算出部とを有する。記憶部は、探索処理によって出力されるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値を記憶する。更新部は、探索処理によってシンボルが出力される毎に、出力されたシンボルのシンボル種に対応したカウント値を更新する。符号範囲更新部は、今回の処理として一のシンボルが出力された場合、記憶部に記憶されている出現頻度を読み出す。そして、符号範囲更新部は、一のシンボルのシンボル種に対応したカウント値に対して、今回の処理で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、次回の処理で用いられる符号範囲特定値を設定する。シフト量算出部は、符号範囲更新部よって設定された符号範囲特定値により特定される符号範囲の幅を、カウント値によって特定される総出現頻度で除算した除算値を２nで近似し、この近似によって得られた値ｎを次回の処理で用いられるシフト量として設定する。
【００１４】
ここで、第３の発明において、符号範囲更新部の更新処理によって、符号範囲の幅が所定値よりも小さくなった場合、または、符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合、符号化データを上位ビット数でシフト量でビットシフトさせるシフト処理を行う判定部をさらに設けてもよい。
【００１５】
また、第３の発明において、シフト量算出部は、総出現頻度に対して、近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出することが好ましい。この場合、符号範囲更新部は、近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる符号範囲を構成するシンボル種毎の各区間に割り当てることが望ましい。
【００１６】
第４の発明は、符号範囲特定値によって設定され、かつ、シンボルのシンボル種に応じた区間に分割された符号範囲から符号化データの値に対応した区間を特定し、この特定された区間に対応するシンボルを出力する探索処理を繰り返し、この繰り返しによって得られたシンボルを並べることによって、符号化データを複数のシンボルで構成されたシンボル列に復号化する復号化方法をコンピュータに実行させる復号化コンピュータ・プログラムを提供する。このプログラムは、探索処理によって、符号化データから一のシンボルのシンボル種を出力する第１のステップと、探索処理によって出力されるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値のうち、一のシンボルのシンボル種に対応したカウント値を更新する第２のステップと、一のシンボルのシンボル種に対応したカウント値に対して、今回の処理対象で用いられるｎ（ｎは自然数）ビットのシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値を更新する第３のステップと、更新された符号範囲特定値により特定される符号範囲の幅をカウント値によって特定される総出現頻度で除算した除算値を２nで近似し、この近似によって得られた値ｎを次回の処理対象で用いられるシフト量として設定する第４のステップと、シンボル列において、処理対象となる一のシンボルを順次シフトさせながら、所定の判定条件を満たすまで、第１のステップから第４のステップまでの処理を繰り返す第５のステップとを有する復号化方法をコンピュータに実行させる。
【００１７】
ここで、第４の発明において、判定条件は、符号範囲特定値の更新によって、符号範囲の幅が所定値よりも小さくなった場合、または、符号範囲特定値の所定範囲の上位ビットが変化しなくなった場合であってもよい。
【００１８】
また、第４の発明において、第４のステップは、総出現頻度に対して、近似によって得られたシフト量でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である近似誤差を算出する第６のステップを含んでいてもよい。この場合、第３のステップは、近似誤差をシンボル種に応じた所定の比率で按分した上で、次回の処理対象で用いられる符号範囲を構成するシンボル種毎の各区間に割り当てるステップを含むことが好ましい。
【００１９】
さらに、第１から第４の発明のいずれかにおいて、符号範囲は、符号範囲特定値である上限値、下限値または幅のうちの所定の組み合わせによって特定されることが好ましい。
【発明の効果】
【００２０】
第１または第２の発明によれば、符号範囲特定値により特定される符号範囲の幅が、カウント値によって特定される総出現頻度で除算した除算値をシフト量で近似される。そして、このシフト量でビットシフトさせるシフト処理を少なくとも含む演算処理を行うことによって、符号範囲特定値が更新される。このように、符号範囲特定値の更新に関して、乗算処理および除算処理をシフト処理に置き換えることで、符号化処理の高速化を図ることが可能となる。それとともに、第１の発明によれば、乗算・除算を行う回路を削減できるので、回路の小規模化を図ることが可能となる。
【００２１】
また、第３または第４の発明によれば、上述した第１または第２の発明と同様の理由で、復号化処理の高速化を図ることができ、第３の発明によれば、回路の小規模化を図ることが可能となる。
【発明を実施するための最良の形態】
【００２２】
＜第１の実施形態（符号化）＞
図１は、符号化システムの構成図である。この符号化システムは、符号範囲特定値によって設定される符号範囲を、処理対象となるシンボルのシンボル種に応じた区間に分割する処理が繰り返し実行される。そして、この繰り返し処理によって得られた演算結果を符号化することによって、シンボル列の符号化が行われる。また、カウント値CNT等のデータに付された添字(i)，(i-1)は、繰り返し処理における１サイクルを示す。添字(i)は、今回のサイクル（ｉ）で処理対象となるシンボルに基づいて算出された値を示し、添字(i-1)は、前回のサイクル（ｉ−１）で処理対象となったシンボルに基づいて算出された値を示す。
【００２３】
符号化システムは、出現頻度管理部１と、符号範囲管理部２と、シフト量算出部３と、第１の出力管理部４とから構成されている。出現頻度管理部１は、処理対象となるシンボル列に含まれるそれぞれのシンボル種が、現段階でどれだけの回数が入力されたかを管理する。出現頻度管理部１は、記憶部１１と更新部１２とから構成されている。
【００２４】
記憶部１１は、シンボル列に含まれるそれぞれのシンボル種の出現頻度を特定可能な複数のカウント値で記憶する。この記憶部１１の記憶内容は、出現頻度表としての構成を有しており、これによってカウント値が記憶される。シンボル種の出現頻度は、出現頻度CNT[j]および累積出現頻度SUM[j]（j：一つのシンボルを示す）といった２種類のカウント値によって管理されている。
【００２５】
出現頻度CNT[j]は、あるシンボル種ｊの出現回数である。初期値は１であり、例えばシンボル"ａ"が２回読み込まれた（入力された）場合、シンボル"ａ"の出現頻度CNT[ａ]が１（初期値）から３へとカウントアップされる。また、累積出現頻度SUM[j]は、出現頻度表におけるシンボルが下位から上位に至る所定の順序において、そのシンボル種より下位の出現頻度CNTの累積値である。例えば、出現頻度表が下位からシンボル"ａ"，"ｂ"，"ｃ"の順に並べられていた場合、シンボル"ａ"の累積出現頻度SUM[ａ]、シンボル"ｂ"の累積出現頻度SUM[ｂ]、およびシンボル"ｃ"の累積出現頻度SUM[ｃ]は下式で示される。
SUM[ａ]＝０（または"NULL"）
SUM[ｂ]＝CNT[ａ]
SUM[ｃ]＝CNT[ａ]＋CNT[ｂ]
【００２６】
また、記憶部１１の出現頻度表は、全てのシンボル種の出現頻度CNT[j]を累積した総出現頻度SUMALLも併せて記憶している。例えば、出現頻度表が３つのシンボル"ａ"，"ｂ"，"ｃ"で構成されている場合、総出現頻度SUMALLは下式で表せる。
SUMALL＝CNT[ａ]＋CNT[ｂ]＋CNT[ｃ]
【００２７】
なお、出現頻度表として、シンボル種毎の出現頻度CNT[j]および累積出現頻度SUM[j]が管理されているが、双方を管理する必要は必ずしもなく、少なくともいずれか一方のみを管理すれば足りる。なぜなら、累積出現頻度SUM[j]については、出現頻度CNTに基づく加算処理によって一義的に特定でき、出現頻度CNT[j]についても、累積出現頻度SUMに基づく減算処理によって一義的に特定できるからである。総出現頻度SUMALLについても同様であり、記憶部１１に記憶している出現頻度表から全てのシンボル種の出現頻度CNT[j]が算出できれば、記憶部１１は全てのシンボル種の出現頻度CNT[j]を管理する必要はない。
【００２８】
また、本実施形態において、出現頻度CNT[j]はシンボル種の出現回数を管理するが、少なくともシンボル種の出現比率が把握できれば足りる。例えば、出現頻度表がシンボル"ａ"，"ｂ"，"ｃ"から構成され、それぞれの出現頻度がCNT[ａ]＝２，CNT[ｂ]＝４，CNT[ｃ]＝２であった場合、その都度、出現頻度のそれぞれに１／２を乗じ（１ビットの右シフト処理を施し）て、CNT[ａ]＝１，CNT[ｂ]＝２，CNT[ｃ]＝１と更新してもよい。なお、この出現頻度[j]の更新条件および更新のタイミングは、復号化における再現性の確保のために、後述の復号化システムのそれとと、同じであることが必要である。
【００２９】
更新部１２は、シンボル列よりシンボルSym(i)が処理対象として入力される毎に、この入力されたシンボル種に対応したカウント値（CNT，SUM）を更新する。例えば、出現頻度表が下位からシンボル"ａ"，"ｂ"，"ｃ"の順に並べられており、シンボル"ａ"が処理対象として入力された場合、出現頻度CNT[ａ]に１を加算した値に更新される。これに応じて累積出現頻度SUM[ｂ]、SUM[ｃ]および総出現頻度SUMALLもそれぞれ１づつ加算した値に更新される。
【００３０】
符号範囲管理部２は、処理対象であるシンボル列に対応する符号範囲を、シンボルが入力される毎に繰り返し更新する。符号範囲管理部２は、符号範囲記憶部２１と、符号範囲更新部２２とから構成されている。符号範囲記憶部２１は、符号範囲を特定する符号範囲特定値を記憶する。符号範囲特定値は、１次元の線分で表現される符号範囲の絶対的な位置を特定するための情報であり、一例として、符号範囲の下限値LOWと幅RNGとが用いられる。ただし、符号範囲特定値としては、下限値LOWおよび幅RNG以外に、符号範囲の上限を示す上限値UPも存在し、これらの内の少なくとも２つを管理すれば、符号範囲を一義的に特定できる。したがって、管理すべき符号範囲特定値は、本実施形態のような組み合わせに限定されるものではなく、下限値LOWと上限値UPとの組み合わせ、上限値UPと幅RNGとの組み合わせ、或いは、下限値LOWと上限値UPと幅RNGとの組み合わせであってもよい。なお、符号範囲記憶部２１に記憶する下限値LOWおよび幅RNGの初期値は、復号化時のデータ再現性を確保すべく、後述の復号化システムのそれと同一であることが前提となる。
【００３１】
符号範囲更新部２２は、今回の処理対象である一のシンボルSym(i)が入力された場合、符号範囲（符号範囲特定値）を更新する。ここで留意すべきは、符号範囲の更新は、出現頻度表の更新前、換言すれば、このシンボルSym(i)のシンボル種に対応したカウント値が更新されるのに先立って行われる点である。具体的には、まず、符号範囲更新部２２は、記憶部１１の出現頻度表を更新する前に、記憶部１１に記憶しているカウント値CNT[j](i-1)，SUM[j](i-1)を読み出す。そして、このシンボルSym(i)のシンボル種に対応したカウント値CNT[Sym(i)](i-1)，SUM[Sym(i)](i-1)に対して、シフト処理を少なくとも含む演算処理が行われ、新たな符号範囲特定値として下限値LOW(i)および幅RNG(i)が算出される。シフト処理とは、今回の処理対象で用いられるｎビットのシフト量SFTでビットシフトさせる演算処理である。なお、算出された符号範囲特定値は、符号範囲記憶部２１に記憶される。
【００３２】
図２は、符号範囲更新部２２の構成図である。符号範囲更新部２２は、下限値算出部２２ａと、幅算出部２２ｅとから構成されている。下限値算出部２２ａは、シフタ２２ｂと、シフタ２２ｃと、加算器２２ｄとを有している。シフタ２２ｂは、入力されたシンボル種Sym(i)に対応した更新前のカウント値SUM[Sym(i)](i-1)を読み込み、このカウント値SUM[Sym(i)](i-1)に対して、シフト量SFT(i-1)で左ビットシフト処理を行う。また、シフタ２２ｃは、近似誤差RMD(i-1)を読み込み、下限値算出部２２ａに入力されたシンボルSym(i)に応じた所定値（例えば値Ｌ）で右ビットシフト処理を行う。また、加算器２２ｄは、シフタ２２ｂ，２２ｃがシフト処理したそれぞれの値と、符号範囲記憶部２１に記憶されている更新前の下限値LOW(i-1)の値とを加算して、新たな（次回の処理対象で用いられる）符号範囲の下限値LOW(i)を算出する。なお、算出された下限値LOW(i)は、符号範囲記憶部２１に記憶される。下限値算出部２２ａが算出する下限値LOW(i)は、下式のようになる。なお、"＜＜"は左ビットシフト処理、"＞＞"は右ビットシフト処理を示し、例えば"SUM[Sym(i)](i-1)＜＜SFT(i-1)"は、カウント値SUM[Sym(i)](i-1)をシフト量SFT(i-1)ビット分だけ左シフト、つまり２SFT(i-1)を乗じる処理である。
LOW(i)＝SUM[Sym(i)](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞Ｌ＋LOW(i-1)
【００３３】
幅算出部２２ｅは、下限値算出部２２ａと同様に、シフタ２２ｆと、シフタ２２ｇと、加算器２２ｈとを有しているが、処理対象となるカウント値が異なっている。また、加算器２２ｈが符号範囲記憶部２１に記憶されている更新前の符号範囲特定値を用いない点も異なっている。シフタ２２ｆは、入力されたシンボル種Sym(i)に対応した更新前のカウント値CNT[Sym(i)](i-1)を読み込み、このカウント値CNT[Sym(i)](i-1)に対して、シフト量SFT(i-1)で左ビットシフト処理を行う。また、シフタ２２ｇは、近似誤差RMD(i-1)を読み込み、幅算出部２２ｅに入力されたシンボルSym(i)に応じた所定値（例えば値Ｒ）で右ビットシフト処理を行う。加算器２２ｈは、シフタ２２ｆ，２２ｇがシフト処理したそれぞれの値とを加算して、新たな（次回の処理対象で用いられる）符号範囲の幅RNG(i)を算出する。なお、算出された幅RNG(i)は、符号範囲記憶部２１に記憶される。幅算出部２２ｅが算出する下限値RNG(i)は、下式のようになる。
RNG(i)＝CNT[Sym(i)](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞Ｒ
【００３４】
シフト量算出部３は、符号範囲管理部２よって更新された符号範囲特定値により特定される符号範囲の幅RNG(i-1)を、カウント値によって特定される総出現頻度SUMALL(i-1)で除算した除算値を２n（２の階乗）で近似する。そして、この近似によって得られた値ｎを次回の処理対象で用いられるシフト量SFTとして設定する。
【００３５】
図３は、シフト量算出部の構成図である。シフト量算出部３は、近似部３１とシフタ３２と、減算器３３とから構成されている。近似部３１は、符号範囲記憶部２１に記憶された幅RNG(i-1)を、記憶部１１に記憶された更新前の総出現頻度SUMALL(i-1)で除算した除算値を２の階乗で近似し、シフト量SFT(i-1)を算出する。本実施形態では、総出現頻度SUMALL(i-1)を左ビットシフト処理した値と、幅RNG(i-1)を比較した値とを比較することによってシフト量SFT(i-1)が算出される。具体的には、下式を満たすシフト量SFT(i-1)が算出される。なお、近似は単純に幅RNG(i-1)と総出現頻度SUMALLとの除算値を求め、この除算値と２の階乗とを比較することで、シフト量ｎを算出することシフト量を算出してもよい。
（SUMALL(i-1)＜＜SFT(i-1)）≦ RNG(i-1) ＜（SUMALL＜＜SFT(i-1)＋１）
【００３６】
シフタ３２は、更新前の総出現頻度SUMALL(i-1)を近似部３１で算出したシフト量SFT(i-1)で左ビットシフト処理を行う。また、減算器３３は、シフタ３２で算出された値と、符号範囲記憶部２１に記憶された更新前の幅RNG(i-1)との減算を行い、近似誤差RMD(i-1)を算出する。近似誤差RMD(i-1)は、シフト量SFT(i-1)への近似を行った結果、総出現頻度をシフト量SFT(i-1)でビットシフトさせるシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅との差分値である。近似誤差RMDは下式のようになる。SUMALL＜＜SFT＝RNGである場合、近似誤差は算出されない。
RMD(i-1)＝RNG(i-1)−（SUMALL(i-1)＜＜SFT(i-1)）
【００３７】
第１の出力管理部４は、処理対象のシンボルSym(i)が入力されることによって符号範囲更新部２２が更新した符号範囲特定値を、符号範囲記憶部２１から読み取り、所定の条件を満たすことで、この符号範囲特定値の一部を符号化データとして出力する。第１の出力管理部４は、判定部４１と、出力更新部４２とによって構成される。判定部４１は、符号範囲記憶部２１の符号範囲の下限値LOW(i)および幅RNG(i)を読み出し、所定の出力条件および終了条件を満たすか否かの判定を行い、この判定に基づいて出力更新部４２の制御を行う。また、出力更新部４２は、判定部４１の判定に基づき、符号範囲記憶部２１に記憶される下限値LOW(i)の値を符号化データとして出力するとともに、下限値LOW(i)および幅RNG(i)を再更新する。
【００３８】
図４は、符号化処理のフローチャートである。この処理フローは全体として、符号範囲特定値によって設定される符号範囲を、処理対象となるシンボルのシンボル種に応じた区間に分割する処理を繰り返す（ステップ１０３〜ステップ１１２）。そして、この繰り返し処理によって得られた演算結果を出力する（ステップ１０７，ステップ１１１）ことによって、複数のシンボルで構成されたシンボル列を符号化する。
【００３９】
まず、ステップ１０１において、処理対象のシンボルSym(i)が読み込まれる（入力される）前に、記憶部１１に記憶されているカウント値CNT，SUMおよびシフト量SFTと、符号範囲記憶部２１に記憶されている下限値LOWおよび幅RNGが初期化がされる。具体的には、更新部１２が、記憶部１１の出現頻度表に記憶されたシンボル種のカウント値CNT[j]を全て１に更新（全てのシンボルの出現確率は等確率と過程）する。
【００４０】
例えば、処理対象のシンボル列に含まれるシンボル種が"ａ"，"ｂ"，"ｃ"のみで構成されている場合、出現頻度表のカウント値CNT[ａ](0)，CNT[ｂ](0)，CNT[ｃ](0)は全て１である。これに伴い、総出現頻度SUMALL(0)も３に更新される。また、符号範囲記憶部２１の符号範囲特定値も所定の値（例えば、LOW(0)＝０，RNG(0)＝６５５３５といった自然数）に更新される。このとき、この総出現頻度SUMALL(0)と、幅RNG(0)が既に設定されたことになるので、シフト量算出部３はこれらの値に基づいてシフト量SFT(0)、近似誤差RMD(0)を算出する。算出されたシフト量SFT(0)、近似誤差RMD(0)は、シフト量算出部３または符号範囲更新部２２が備えるバッファ（図示せず）に記憶される。
【００４１】
ステップ１０２において、ループ変数ｉが設定される。このループ変数は、シンボルの入力に対する出現頻度表および符号範囲の更新タイミングを示すものであり、初期値として１が設定される。なお、シンボルの入力に対する出現頻度表および符号範囲の更新のタイミングを管理できれば、ループ変数ｉは、この符号化システム内外のいずれかのバッファ（例えば、更新部１２）に記憶されてもよい。
【００４２】
ステップ１０３において、処理対象のシンボル列のうちｉ番目（初期値であれば１）のシンボルSym(i)が入力される。入力されたシンボルSym(i)は、出現頻度管理部１の更新部１２と、符号範囲管理部２の符号範囲更新部２２とにそれぞれ入力される。このとき、更新部１２は、この入力シンボルSym(i)に対するカウント値（出現頻度表）の更新を行わない。
【００４３】
そして、ステップ１０４において、符号範囲更新部２２は、入力されたシンボルSym(i)に対応したカウント値CNT[Sym(i)](i-1)，SUM[Sym(i)](i-1)と、シフト量算出部３によって算出されたシフト量SFT(i-1)と、近似誤差RMD(i-1)とを読み込む。上述したように、これらのカウント値CNT[Sym(i)](i-1)，SUM[Sym(i)](i-1)は、更新部１２が記憶部１１の出現頻度表を更新する前のものが用いられる。なお、本実施形態においてシフト量SFT(i-1)は、後述のステップ１１２（またはステップ１０１）で予め算出（設定）されているが、例えばステップ１０４でシフト量SFT(i-1)を算出するといった如く、次のステップ１０５の処理前に算出されていれば足りる。
【００４４】
ステップ１０５において、符号範囲更新部２２は、ステップ１０４で読み込まれたこれらの値CNT(i-1)，SUM(i-1)，SFT(i-1)，RMD(i-1)に基づいて、次回のシンボルの入力による更新処理に用いられる新たな下限値LOW(i)および新たな幅RNG(i)を算出する。この新たな符号範囲特定値が、符号範囲記憶部２１に記憶されることで符号範囲が更新される。
【００４５】
ステップ１０６において、第１の出力管理部４の判定部４１が、シンボル列の符号化を終了するか否かの終了条件を判定する。この終了条件を満たす場合は処理をステップ１０７へ進め、満たさない場合は処理をステップ１０８へ進める。この終了条件は、符号化処理における繰り返し処理を防ぎ、後述の復号化システムにも共通して適用できる（判定できる）ものあれば、どのような条件であってもよい。本実施形態において、終了条件は例として以下がある。
（例１）
符号化処理前に予め符号化終了を示すシンボル（例えば、シンボル"EOF"）を設定しておき、このシンボル処理対象として入力された場合（Sym(i)＝"EOF"）。
（例２）
符号化処理前に予めループ回数の閾値（LAST）を設定しておき、ループ変数ｉが閾値に達した場合（i＝LAST)。
【００４６】
終了条件を満たし、ステップ１０７へ処理が進んだ場合、判定部４１が出力更新部４２に対して、符号範囲記憶部２１に記憶されている下限値LOW(i)を符号化データとして出力して、処理を終了する。一方、終了条件を満たさず、ステップ１０８へ処理が進んだ場合、カウント値が更新される。具体的には、更新部１２は、記憶部１１に対してカウント値CNT[j]，SUM[j]を更新する。なお、ステップ１０１と同様に、算出されたシフト量SFT(i)および近似誤差RMD(i)は、シフト量算出部３または符号範囲更新部２２が備えるバッファ（図示せず）に記憶される。その後、処理をステップ１０９へ進める。
【００４７】
つぎに説明するステップ１０９およびステップ１１０は、ステップ１０５で更新された符号範囲特定値を出力する出力条件である。本実施形態の出力条件は、ステップ１０９の後にステップ１１０が実行されているが、ステップ１１０の後にステップ１０９が実行されてもよい。
【００４８】
ステップ１０９において、次回の処理対象で用いられる幅RNG(i)が所定値よりも小さいか否かが判定される。具体的には、第１の出力管理部４の判定部４１が、符号範囲記憶部２１に記憶された幅RNG(i)を読み取り、この幅RNG(i)が所定値より小さくなったかどうかを判定する。幅RNG(i)が所定値よりも小さくない場合、つまり、幅RNGは値を縮小させる余地ある（幅RNG(i)をさらに縮小させても、以降の演算処理に影響がない）場合には、処理をステップ１１０へ進める。一方、幅RNG(i)が所定値よりも小さい場合、つまり、幅RNGは値を縮小させる余地ない（幅RNG(i)をさらに縮小させると、以降の演算処理に影響がある）場合には、処理をステップ１１１へ進める。
【００４９】
ステップ１１０において、符号範囲更新部２２の更新処理によって、符号範囲特定値の所定範囲の上位ビットが変化しなくなったか否かが判定される。この判定は、回の処理対象で用いられる符号範囲特定値の所定範囲の上位ビットと、今回の処理対象で用いられる符号範囲特定値の所定範囲の上位ビットとを比較することによって行われる。具体的には、第１の出力管理部４の判定部４１が、前回の処理対象で算出されていた下限値LOW(i-1)を記憶しており、符号範囲記憶部２１に記憶されている下限値LOW(i)を読み取り、下限値LOW(i-1)との比較を行う。そして、下限値(i)と下限値(i-1)の上位８ビットが異なっている、つまり下限値LOW(i)の値に大きな差がみられる場合、処理をステップ１１２へ進める。下限値(i)と下限値(i-1)の上位８ビットが不変、つまり、これ以上符号範囲を更新を行っても、下限値LOW(i)の値が変わらない場合、処理をステップ１１１へ進める。なお、本実施形態において、以前の処理対象で算出されていた下限値LOW(i-1)は、判定部４１に記憶されているが、符号範囲記憶部２１に記憶してもよい。この場合、判定部４１は符号範囲記憶部２１から、下限値LOW(i)とともに、下限値LOW(i-1)も読み込んで上記の比較を行う。
【００５０】
ステップ１０９およびステップ１１０における出力条件を満たし、ステップ１１１へ処理が進んだ場合、下限値LOW(i)が符号化データcodeとして出力され、あわせて下限値LOW(i)と幅RNG(i)とが再更新される。具体的には、判定部４１が出力更新部４２に対して、下限値LOW(i)の出力・更新を行うように制御する。そして、出力更新部４２は、この制御に応じて符号範囲記憶部２１から下限値LOW(i)および幅RNG(i)を読み取り、このうち下限値LOW(i)の上位８ビットを出力し、下限値(i)および幅RNG(i)の値を８ビット分を左シフトするビットシフト処理を行う。つまり、出力更新部４２は、下限値LOW(i)を左シフトさせ、これによって桁があふれたビット分を符号化データcodeとして出力する。
【００５１】
なお、下限値(i)を左シフトすることで空白（または"NULL"）になる下位８ビットには０が挿入される。また、これと同様に、幅RNGも８ビット左シフトするビットシフト処理が行われる。この処理は、符号化データcodeの出力と同時に、値の小さくなった符号範囲特定値が再び大きくするもので、下限値LOWおよび幅RNGを用いた符号化処理の演算処理の低下を抑えることができる。そして、シフト量算出部３が符号範囲記憶部２１の幅RNG(i)を読み取り、シフト量SFT(i)および近似誤差RMD(i)を算出する（ステップ１１２）。最後に、ループ変数がインクリメントされた上で（ステップ１１３）、処理をステップ１０３へ進める。
【００５２】
つぎに、図５の符号化における符号範囲の遷移図を参照しながら、本実施形態に係る符号範囲の具体的なケースについて説明する。本ケースでは、出現頻度表に３つのシンボル種"ａ"，"ｂ"，"ｃ"のカウント値が予め設定されており、入力として"ｂ"，"ａ"の順にシンボル列のシンボルが入力され、この２つのシンボルの入力が完了すると、符号化が終了する（LAST=2）。なお、ステップ１０９，１１０で説明した出力条件は満たしておらず、これに伴いステップ１１１の処理も行わないものとする。
【００５３】
図５（ａ）は、初期状態(i＝0)における符号範囲の状態を示している（ステップ１０１）。符号範囲記憶部２１に記憶されている幅RNG(0)および下限値LOW(0)は、符号化処理前に予め設定されている初期値である。また図中の符号範囲は、シンボル種毎に線分が分割されているが、これは説明を簡略化するために表記したものであり、実装上、それぞれのシンボル種を示す区間を特定する値（境界値）は、符号範囲記憶部２１には記憶されていない。
【００５４】
図５（ｂ）は、シフト量算出部３が、記憶部１１のカウント値CNT[j]，SUM[j]および符号範囲記憶部２１の幅RNG(0)から、シフト量SFT(0)および近似誤差RMD(0)を算出した符号範囲の状態を示している（ステップ１０４）。符号範囲更新部２２は、この近似誤差を所定の比率（ａ：ｂ：ｃ＝１：２：１）で按分した上で、符号範囲を構成するシンボル種毎の各区間に割り当てる。
【００５５】
近似誤差の割り当ては、近似誤差RMDを除算および乗算処理を用いることも可能であるが、本実施形態の場合、ビットシフト処理を用いることも可能である。なぜなら、１ビットの右シフトを行うと値は１／２になり、２ビットの右シフトを行うと値は１／４になるからである。近似誤差の分割を上記の比率で固定して割り当てる場合、入力されるシンボルSym(i)と新たに算出される下限値LOW(i)，幅RNG(i)の対応関係は、下式で表せる。
（１）Sym(i)＝"ａ"の場合
LOW(i)＝SUM[ａ](i-1)＜＜SFT(i-1)＋LOW(i-1)
RNG(i)＝CNT[ａ](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞２
（２）Sym(i)＝"ｂ"の場合
LOW(i)＝SUM[ｂ](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞２＋LOW(i-1)
RNG(i)＝CNT[ｂ](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞１
（３）Sym(i)＝"ｃ"の場合
LOW(i)＝SUM[ｃ](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞２＋＋RMD(i-1)＞＞１＋LOW(i-1)
RNG(i)＝CNT[ｃ](i-1)＜＜SFT(i-1)＋RMD(i-1)＞＞２
【００５６】
したがって、本ケースの場合、入力されるシンボルが"ｂ"なので、新たに算出される下限値LOW(1)および幅RNG(1)は下式のようになる。図５（ｃ）は、この式により算出された近似誤差をシンボル種毎の各区間に按分した上で割り当てることによって、新たな符号範囲に更新された状態を示している。（ステップ１０５）。
LOW(1)＝SUM[ｂ](0)＜＜SFT(0)＋RMD(0)＞＞2＋LOW(0)
RNG(1)＝CNT[ｂ](0)＜＜SFT(0)＋RMD(0)＞＞1
【００５７】
なお、近似誤差の割り当ては、本ケースのように符号化処理前に予め設定した比率で静的に割り当てることも可能であるが、近似誤差を動的に割り当ててもよい。例えば、今回の符号処理の直前に入力したシンボルSym(i-1)や、符号処理における今現在の出現頻度表のカウント値の分布に応じて、近似誤差の割り当てを変化させてもよい。具体的には、同じシンボルが連続して出現する（入力される）可能性が高い場合、このシンボルの幅RNGに多く近似誤差RMDを割り当てたり、今現在のそれぞれのシンボル種のカウント値CNTをそのまま比率として割り当てることもできる。ただし、静的な割り当てと同様に、近似誤差RMDの割当設定は後述の復号化と同じである必要がある。
【００５８】
図５（ｄ）は、１回目のシンボル入力が完了した(i＝1)符号範囲の状態を示している。初期状態と同様に、それぞれのシンボル種を示す区間を特定する値（境界値）は、符号範囲記憶部２１には記憶されていない。そして、同図（ｅ）はシフト量算出部３が、記憶部１１のカウント値SUMALL(1)と、符号範囲記憶部２１の幅RMG(1)とに基づいて、シフト量SFT(1)および近似誤差RMD(1)を算出した符号範囲の状態を示している（ステップ１０４）。そして、同図（ｂ）と同様に、この近似誤差をシンボル"ａ"，"ｂ"，"ｃ"に対して１：２：１の比率で按分して割り当てる。
【００５９】
図５（ｆ）は、算出された近似誤差RMD(1)をシンボル種に応じて割り当て、新たな符号範囲に更新された状態を示している（ステップ１０５）。なお、累積出現頻度SUMALL[ａ](1)には値が記憶されていない（０または"NULL"）ので、左シフト処理を行っても値は０である。したがって、新たに設定される下限値LOW(2)は、下限値LOW(1)のままになる。そして、同図（ｇ）のような次回のシンボル処理に対応する下限値LOW(2)および幅RNG(2)が更新され、このうち下限値LOW(2)がシンボル列を符号化した符号化データcodeとして、出力更新部４２から出力される（ステップ１０７）。
【００６０】
このように、本実施形態によれば、シフト量算出部３が、符号化において符号範囲の幅RNG(i-1)を総出現頻度SUMALL(i-1)での除算値を除算値を２nで近似し、この近似によって得られた値ｎを次回の処理対象で用いられるシフト量SFT(i-1)として設定する。そして、符号範囲更新部２２が、このシフト量SFTとカウント値CNT[j](i-1)，SUM[j](i-1)とに基づいて、新たな下限値LOW(i)および新たな幅RNG(i）を設定する。これにより、次回の符号範囲特定値の更新において、乗算処理および除算処理が、シフト処理にかえることができるので、全体の処理速度の高速化を図ることが可能となる。また、除算・乗算処理も削減されるので、回路全体の規模を縮小することが可能になる。
【００６１】
また、本実施形態によれば、上記の近似においてシフト量算出部３が、総出現頻度SUMALL(i-1)をシフト量SFT(i-1)でシフト処理によって算出された値と、今回の処理対象で用いられる符号範囲の幅RNG(i-1)との差分値である近似誤差RMD(i-1)を算出している。そして、符号範囲更新部２２が、この近似誤差RMD(i-1)をシンボル種に応じた所定の比率で分割するとともに、分割した値を次回の処理対象で用いられる符号範囲の下限値LOW(i)および幅RNG(i)に分配する演算処理を行う。これにより、新たに設定される下限値LOW(i)および幅RNG(i)が必要以上に減少を抑えることができるので、以降の繰り返し処理において、桁数の減少による演算量の増加を抑え、演算処理速度の低下を防止することができる。
【００６２】
＜第２の実施形態（復号化）＞
図６は、復号化システムの構成図である。この復号化システムは、上述の符号化システムと同様に、符号範囲を出力するシンボルのシンボル種に応じた区間に分割する処理を繰り返す。そして、入力された符号化データcodeに対応する区間を、この符号範囲の中から検索することによって、該当する区間に対応するシンボルを出力する。
【００６３】
復号化システムは、出現頻度管理部１と、符号範囲管理部２と、シフト量算出部３と、第２の出力管理部５とから構成されている。本実施形態の出現頻度管理部１は、第２の出力管理部５からシンボルSym(i)を出力する毎に、この出力されたシンボルSym(i)のシンボル種に対応した出現頻度表のカウント値CNT[j]，SUM[j]を更新する。また、シフト量算出部３は、このカウント値の更新に応じてシフト量SFT(i-1)と近似誤差RMD(i-1)を算出し、符号範囲管理部２は、このシフト量SFT(i-1)と近似誤差RMD(i-1)に基づいて新たな下限値LOW(i)および幅RNG(i)を算出する。出現頻度管理部１、符号範囲管理部２およびシフト量算出部３の構成は、上述の符号化システムのそれと同様である。
【００６４】
第２の出力管理部５は、シフト量SFT(i-1)、近似誤差RMD(i-1)およびカウント値（累積出現頻度SUM[j]）に基づいて、符号範囲をシンボル種毎に分割する境界値BASE[j]を算出し、シンボル種毎に対応した区間を設定する。そして、復号化システムに入力された符号化データcodeの値を含む区間を検索・特定し、特定された区間に対応するシンボル種を出力シンボルSym(i)として出力する。第２の出力管理部５は、記憶部５１と、判定部５２と、更新部５３と、境界算出部５４と、出力部５５とから構成されている。
【００６５】
記憶部５１は、シンボル列を符号化によって生成した符号化データcodeを記憶する。判定部５２は、第１の実施形態と同様に、符号範囲記憶部２１に記憶されている下限値LOW(i)および幅RNG(i)を読み出し、所定の更新条件および終了条件を満たすか否かの判定を行い、この判定結果に応じて、記憶部５１および更新部５３とを制御する。更新部５３は、判定部５２の判定結果に応じて、符号範囲記憶部２１に記憶される下限値LOW(i)および幅RNG(i)を再更新する。
【００６６】
境界算出部５４は、シフト量算出部３が算出したシフト量SFT(i-1)および近似誤差RMD(i-1)と、出現頻度管理部１に記憶したカウント値SUM[j]とに基づいて、符号範囲をシンボル種毎に分割する境界値BASE[j]を算出する。出力部５５は、境界算出部５４が算出した境界値BASE[j]をもとに符号範囲の区間を設定し、記憶部５１に記憶した符号化データcodeに対応する区間を検索・特定する。そして、この区間に対応するシンボル種を出力シンボルSym(i)として出力する。
【００６７】
図７は、境界算出部５４の構成図である。境界算出部５４は、シフタ５４ａと、シフタ５４ｂと、加算器５４ｃとを有している。シフタ５４ａは、全てのシンボル種に対応した更新前のカウント値SUM[j](i-1)を読み込み、それぞれのカウント値SUM[j](i-1)に対して、シフト量SFT(i-1)で左ビットシフト処理を行う。また、シフタ５４ｂは、近似誤差RMD(i-1)を読み込み、この近似誤差RMD(i-1)に対してシンボルに応じた所定値（例えば値Ｂ）で右シフト処理を行う。また、加算器５４ｃは、シフタ５４ａ，５４ｂがシフト処理したそれぞれの値と、前回のシンボルで使用した符号範囲の下限値LOW(i-1)とを加算して、境界値BASE[j](i)を算出する。算出された境界値BASE[j](i)は、出力部５５に出力される。境界算出部５４が算出する境界値BASE[j](i)は、下式のようになる。
BASE[j](i)＝BASE[j-1](i)＋SUM[j](i-1)＜＜SFT(0)＋RMD(i-1)＞＞Ｂ＋LOW(i-1)
【００６８】
出力部５５は、記憶部５１に記憶された符号化データcodeと、境界算出部５４が算出した境界値BASE[j]とを読み込む。そして、出力部５５は、境界値BASE[j]で分割された符号範囲の区間を設定し、符号化データcodeの値に対応する区間を検索・特定し、特定された区間に対応するシンボル種を出力シンボルとしてSym(i)が出力する。
【００６９】
図８は、復号化のフローチャートである。全体として、まず符号範囲の境界値を設けてシンボル種に対応する区間を設定し、符号化データcodeの値に対応する区間のシンボル種を出力し、最後に符号範囲およびカウント値等を更新する。これらの一連の処理を繰り返し、シンボル種を並べることによって、符号化データcodeに対応するシンボル列に復号化する。
【００７０】
まず、ステップ２０１において、カウント値CNT，SUM、シフト量SFT等が初期化され、続くステップ２０１においてループ変数ｉが１に設定される（図４のステップ１０１，１０２と同様）。ステップ２０３において、図４のステップ１０４と同様に、カウント値SUM(i-1)、シフト量SFT(i-1)等が読み込まれる。なお、本実施形態においてシフト量SFT(i-1)は、後述のステップ２１３（またはステップ２０１）で予め算出（設定）されているが、このステップ２０３で、シフト量SFT(i-1)を算出するといった如く、ステップ２０４における境界値BASE[j]の算出までに算出されていれば足りる。
【００７１】
ステップ２０４において、ステップ２０３で算出されたシフト量SFT(i-1)および近似誤差RMD(i-1)と、出現頻度管理部１に記憶したカウント値（SUM[j]）とに基づいて、境界算出部５４が、符号範囲をシンボル種毎の区間に分割する境界値BASE[j]を算出する。そして、続くステップ２０５において、符号化データcodeが読み込まれる。読み込まれた符号化データcodeは記憶部５１に記憶され、処理をステップ２０６へ進める。
【００７２】
ステップ２０６において、ステップ２０４で算出された境界値BASE[j]と、記憶部５１に記憶された符号化データcodeとに基づいて、出力部５５が、シンボルのシンボル種に応じた区間に分割された符号範囲から符号化データcodeの値に対応した区間を探索・特定する。これによって特定された区間、すなわち、符号化データcodeの値を含む区間に対応するシンボル種が出力される。そして、続くステップ２０７において、判定部５２は、図４のステップ１０７と同様に、最後のシンボルであるか否かを判定する。終了条件を満たした場合、処理を終了し、終了条件を満たしていない場合、処理をステップ２０８へ進める。
【００７３】
ステップ２０８において、更新部５３は、図４のステップ１０５と同様に、下限値LOW(i)および幅RNG(i)を更新する。ステップ２０９において、判定部５２は、図４のステップ１０８と同様に、カウント値CNT(i)，SUM(i)を更新する。ステップ２１０およびステップ２１１において、判定部５２は、更新条件の判定を行う。これらの更新条件は、図４のステップ１０９，１１０に示した出力条件と同様である。それぞれの更新条件のいずれかを満たす場合、処理をステップ２１２へ進め、満たさない場合、処理をステップ２１３へ進める。
【００７４】
ステップ２１０およびステップ２１１における更新条件を満たし、処理がステップ２１２へ進んだ場合、符号化データcodeが更新され、あわせて下限値LOW(i)と幅RNG(i)が再更新される。具体的には、判定部５２が記憶部５１に対して符号化データcodeの更新を行うように制御する。そして、記憶部５１はこの制御に応じて、codeの上位８ビットを左ビットシフト処理し、下位８ビットに新たな符号を加える。つまり、記憶部５１は、符号化データcodeの不要な部分を削除し、これによって空白（または"NULL"）ができた下位ビットに新たな符号化データが挿入される。
【００７５】
また、記憶部５１では、同様に下限値LOW(i)および幅RNG(i)も８ビット左シフトするビットシフト処理が行われる。この処理は、符号化データcodeの更新と同時に、値の小さくなった符号範囲特定値が再び大きくするもので、下限値LOWおよび幅RNGを用いた符号化処理の演算処理の低下を抑えることができる。そして、ステップ２１３において、シフト量算出部３は、図４のステップ１１２と同様に符号範囲記憶部２１の幅RNG(i)を読み取り、シフト量SFT(i)および近似誤差RMD(i)を算出する。ステップ２１３の処理が完了すると、ループ変数がインクリメントされた上で（ステップ２１４）、ステップ２０３に処理を進める。
【００７６】
つぎに、図９の復号化における符号範囲の遷移図を参照しながら、本実施形態に係る符号範囲の具体的なケースについて説明する。本ケースでは、出現頻度表に３つのシンボル種"ａ"，"ｂ"，"ｃ"のカウント値が予め設定されており、入力として上述の符号化システムによって符号化された"ｂ"，"ａ"に対応する符号化データcodeを用いる。この２つのシンボルSym(i)の出力が完了すると、復号化も終了する（LAST=2）ものとする。
【００７７】
図９（ａ）は、初期状態(i＝0)における符号範囲の状態を示している。符号範囲記憶部２１に記憶されている初期状態の幅RNG(0)および下限値LOW(0)は、符号化処理前に予め設定されている値である（ステップ２０１）。また、下限値LOW(0)および幅RNG(0)の値は第１の実施形態に記載された符号化システムと同一である。また、図９（ｂ）は、シフト量算出部３が、記憶部１１のカウント値（総出現頻度SUMALL）および符号範囲記憶部２１の幅RNG(0)に基づいて、シフト量SFT(0)および近似誤差RMD(0)を算出した符号範囲の状態を示している（ステップ２０３）。本実施形態では、第１の実施形態と同様に符号範囲更新部２２が、この近似誤差をシンボル"ａ"，"ｂ"，"ｃ"に対して１：２：１の比率で按分して割り当てる。
【００７８】
図９（ｃ）は、シンボル"ｂ"が出力される場合の境界算出部５４が設定する符号範囲の状態を示している（ステップ２０４〜２０６）。境界算出部５４は、シフト量算出部３が算出したシフト量SFT(0)および近似誤差RMD(0)と、出現頻度管理部１に記憶した累積出現頻度SUM[j](0)とに基づいて、符号範囲をシンボル種毎に分割する境界値BASE[j](0)を算出する。本ケースの場合、それぞれの境界値は下式で表せる。
BASE[ａ](1)＝SUM[ａ](0)＜＜SFT(0)＋LOW(0)
BASE[ｂ](1)＝SUM[ｂ](0)＜＜SFT(0)＋RMD(0)＞＞２＋LOW(0)
BASE[ｃ](1)＝SUM[ｃ](0)＜＜SFT(0)＋RMD(0)＞＞２＋＋RMD(0)＞＞１＋LOW(0)
【００７９】
そして、出力部５５は、これらの境界値に基づいて、記憶部５１に記憶された符号化データcodeを含む区間の検索を行う。本ケースの場合、第１の実施形態が符号化した符号化データcodeは、SUM[ｂ]＜＜SFT(0)＋RMD(0)＜＜２＋LOW(0)である。したがって、codeはシンボル"ｂ"に対応する区間に含まれるのでシンボル"ｂ"が出力される。
【００８０】
図９（ｄ）は、１回目のシンボル出力が完了した(i＝1)符号範囲の状態を示している。初期状態と同様に、それぞれのシンボル種を示す区間を特定する値（境界値）は、符号範囲記憶部２１には記憶されていない（ステップ２０８）。そして、同図（ｅ）はシフト量算出部３が、記憶部１１のカウント値SUMALL(1)と、符号範囲記憶部２１の幅RMG(1)とからシフト量SFT(1)および近似誤差RMD(1)を算出した符号範囲の状態を示している（ステップ２０９）。そして、同図（ｂ）と同様に、この近似誤差をシンボル"ａ"，"ｂ"，"ｃ"に対して１：２：１の比率で按分して割り当てる。
【００８１】
図９（ｆ）は、算出された近似誤差RMD(1)をシンボル種に応じて割り当て、新たな符号範囲に更新された状態を示している（ステップ２０４〜２０６）。なお、累積出現頻度SUMALL[ａ](1)には値が記憶されていない（０または"NULL"）ので、左シフト処理を行っても値は０である。したがって、新たに設定される下限値LOW(2)は、下限値LOW(1)のままになる。そして、同図（ｇ）のような次回のシンボル処理に対応する下限値LOW(2)，幅RNG(2)が更新され、このうち下限値LOW(2)がシンボル列を符号化した符号化データcodeが、出力更新部４２から出力される。そして、出力部５５は、これらの境界値に基づいて、記憶部５１に記憶された符号化データcodeを含む区間の検索を行う。本ケースの場合、第１の実施形態が符号化した符号化データcodeは、SUM[ａ](1)＜＜SFT(1)＋LOW(1)（＝SUM[ｂ]＜＜SFT(0)＋RMD(0)＜＜２＋LOW(0)）である。したがって、codeはシンボル"ａ"に対応する区間に含まれるのでシンボル"ａ"が出力される。
【００８２】
このように、本実施形態によれば、上述した第１の実施形態と同様の理由で、復号化処理の高速化を図ることができ、回路の小規模化を図ることも可能となる。
【００８３】
上述した第１および第２の実施形態の基本的な処理フローをまとめると以下のようになる。
（１）  符号範囲の幅RNG(i-1)と、総出現頻度SUMALL(i-1)を用いてシフト量SFT(i-1)を算出する。
（２）  処理対象となるシンボルを出現頻度表の更新前に取得する。
（３）  下限値LOW(i)および幅RNG(i）を更新する。
（４）  （２）で取得したシンボルに基づいて出現頻度表の更新する。
（５）  （１）に戻り、所定の条件を満たすまで繰り返す。
【００８４】
符号化および復号化の相違点は、（２）における処理対象となる入力データ（シンボル）にある。具体的に、符号化システムでは、入力データがシンボル列のシンボルであり、復号化システムにおいては、入力データが復号化により出力されたシンボルである点である。したがって、符号範囲（特定値）の初期値、出現頻度表の更新ルール（出現頻度表に用意するシンボル種の数、終了条件など）を一致させることにより、シンボルの入力および出力による符号化システム・復号化システムともに再現性を確保することができる。
【００８５】
なお、第１および第２の実施形態において、処理対象が"ａ"や"ｂ"といったテキスト（文字）データであったが、例えば、"０"〜"２５５"といった数値が処理対象であってもよい。したがって、画像データおよび音声データといったデータ形式に限らず符号化が可能である。なお、この場合、記憶部１１には入力され得るシンボル種の数（j＝２５６）に応じた出現頻度表（カウント値）の確保が必要である。
【００８６】
さらに、上述した２つの実施形態は、図１の符号化システム、または図６の復号化システムの機能を実現するプログラムを、コンピュータが読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータシステムに導入することでも実現可能である。ここでいう「コンピュータシステム」とは、ＯＳやハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境あるいは表示環境を備えたＷＷＷシステムも含むものとする。また、「コンピュータが読み取り可能な記録媒体」は、ＲＯＭ（Read Only Memory）、磁気ディスク、光ディスク、光磁気ディスクなどといった可搬媒体、およびハードディスクを指す。さらに、「コンピュータが読み取り可能な記録媒体は、インターネットなどのネットワーク回線を介してプログラムが送信されるサーバや、コンピュータシステム内部の揮発性メモリも含まれる。また、「プログラム」は、このプログラムを記憶媒体に記憶したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により、他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワークや電話回線等の通信回線（通信線）のように、情報を一部実現するためのものであってもよい。またこれら機能をコンピュータシステムによって、すでに記録されているプログラムとの組み合わせで実現できる差分ファイルであってもよい。
【図面の簡単な説明】
【００８７】
【図１】符号化システムの構成図
【図２】符号範囲更新部の構成図
【図３】シフト量算出部の構成図
【図４】符号化処理のフローチャート
【図５】符号化における符号範囲の遷移図
【図６】復号化システムの構成図
【図７】出力部の構成図
【図８】復号化処理のフローチャート
【図９】復号化における符号範囲の遷移図
【符号の説明】
【００８８】
１  出現頻度管理部
１１  記憶部
１２  更新部
２  符号範囲管理部
２１  符号範囲記憶部
２２  符号範囲更新部
２２ａ  下限値算出部
２２ｂ  シフタ
２２ｃ  シフタ
２２ｄ  加算器
２２ｅ  幅算出部
２２ｆ  シフタ
２２ｇ  シフタ
２２ｈ  加算器
３  シフト量算出部
３１  近似部
３２  シフタ
３３  減算器
４  第１の出力管理部
４１  判定部
４２  出力更新部
５  第２の出力管理部
５１  記憶部
５２  判定部
５３  更新部
５４  境界算出部
５５  出力部
５４ａ  シフタ
５４ｂ  シフタ
５４ｃ  加算器
５５  出力部
【図１】
2007082058.tif 000003
【図２】
2007082058.tif 000004
【図３】
2007082058.tif 000005
【図４】
2007082058.tif 000006
【図５】
2007082058.tif 000007
【図６】
2007082058.tif 000008
【図７】
2007082058.tif 000009
【図８】
2007082058.tif 000010
【図９】
2007082058.tif 000011