(57)【特許請求の範囲】
【請求項１】
シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、符号化データに応じた区間を特定することによって、符号化データからシンボル列を復号化する復号化システムにおいて、
前回のサイクルで出力された前記シンボルによって更新された前記符号範囲を、前回のサイクルよりも前のサイクルまでに出力された前記シンボルが反映された前記確率分布に応じた区間に分割するとともに、当該符号範囲から前記符号化データに応じた区間を選択することによって、今回のサイクルの前記シンボルを出力するシンボル処理部と、
前記シンボル出力部から出力された今回のサイクルの前記シンボルに応じて、次回のサイクルで用いられる前記符号範囲を更新する符号範囲更新部と、
前記シンボル出力部から出力された今回のサイクルの前記シンボルに応じて、次回のサイクルよりも後のサイクルで用いられる前記確率分布を更新する確率分布更新部と
を有することを特徴とする復号化システム。
【請求項２】
前記確率分布更新部は、前記シンボル処理部の処理と並行して、前記確率分布の更新を行うことを特徴とする請求項１に記載された復号化システム。
【請求項３】
前記確率分布更新部は、今回のサイクルで出力された前記シンボルと、従前のサイクルで出力された少なくとも一つの前記シンボルとに応じて、前記確率分布の更新を行うことを特徴とする請求項１または２に記載された復号化システム。
【請求項４】
前記確率分布更新部は、前記従前のサイクルで出力された少なくとも一つのシンボルよりも大きな重み付けを前記今回のサイクルで出力されたシンボルに施した上で、前記確率分布の更新を行うことを特徴とする請求項３に記載された復号化システム。
【請求項５】
シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、符号化データに応じた区間を特定することによって、符号化データからシンボル列を復号化する復号化方法において、
前回のサイクルで出力された前記シンボルによって更新された前記符号範囲を、前回のサイクルよりも前のサイクルまでに出力された前記シンボルが反映された前記確率分布に応じた区間に分割する第１のステップと、
前記符号範囲から前記符号化データに応じた区間を選択することによって、今回のサイクルの前記シンボルを出力する第２のステップと、
今回のサイクルで出力された前記シンボルに応じて、次回のサイクルで用いられる前記符号範囲を更新する第３のステップと、
今回のサイクルで出力された前記シンボルに応じて、次回のサイクルよりも後のサイクルで用いられる前記確率分布を更新する第４のステップと
を有することを特徴とする復号化方法。
【請求項６】
シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、符号化データに応じた区間を特定することによって、符号化データからシンボル列を復号化する符号化処理をコンピュータに実行させる復号化プログラムにおいて、
前回のサイクルで出力された前記シンボルによって更新された前記符号範囲を、前回のサイクルよりも前のサイクルまでに出力された前記シンボルが反映された前記確率分布に応じた区間に分割する第１のステップと、
前記符号範囲から前記符号化データに応じた区間を選択することによって、今回のサイクルの前記シンボルを出力する第２のステップと、
今回のサイクルで出力された前記シンボルに応じて、次回のサイクルで用いられる前記符号範囲を更新する第３のステップと、
今回のサイクルで出力された前記シンボルに応じて、次回のサイクルよりも後のサイクルで用いられる前記確率分布を更新する第４のステップと
を有する復号化処理をコンピュータに実行させる復号化プログラム。
【請求項７】
シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、シンボルに応じた区間を特定することによって、シンボル列を符号化データに符号化する符号化システムにおいて、
前回のサイクルで処理対象となる前記シンボルによって更新された前記符号範囲を、前回のサイクルよりも前のサイクルまでに入力された前記シンボルが反映された前記確率分布に応じた区間に分割する境界設定部と、
前記符号範囲から今回のサイクルで処理対象となる前記シンボルに応じた区間を選択し、当該選択された区間を次回のサイクルで用いられる前記符号範囲に設定する符号範囲更新部と、
今回のサイクルで処理対象となる前記シンボルに応じて、次回のサイクルよりも後のサイクルで用いられる前記確率分布を更新する確率分布更新部と、
今回のサイクルで処理対象となる前記シンボルが前記シンボル列の終端である場合、前記符号範囲更新部によって選択された区間内の一値を前記符号化データとして出力する符号化データ出力部と
を有することを特徴とする符号化システム。
【請求項８】
前記確率分布更新部は、今回のサイクルで入力された前記シンボルと、従前のサイクルで入力された少なくとも一つの前記シンボルとに応じて、前記確率分布の更新を行うことを特徴とする請求項７に記載された符号化システム。
【請求項９】
前記確率分布更新部は、前記従前のサイクルで入力された少なくとも一つのシンボルよりも大きな重み付けを前記今回のサイクルで出力されたシンボルに施した上で、前記確率分布の更新を行うことを特徴とする請求項８に記載された符号化システム。
【請求項１０】
シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、シンボルに応じた区間を特定することによって、シンボル列を符号化データに符号化する符号化方法において、
前回のサイクルで処理対象となる前記シンボルによって更新された前記符号範囲を、前回のサイクルよりも前のサイクルまでに入力された前記シンボルが反映された前記確率分布に応じた区間に分割する第１のステップと、
前記符号範囲から今回のサイクルで処理対象となる前記シンボルに応じた区間を選択する第２のステップと、
今回のサイクルで処理対象となる前記シンボルが前記シンボル列の終端でない場合、当該シンボルに応じて選択された区間を次回のサイクルで用いられる前記符号範囲に設定する第３のステップと、
今回のサイクルで処理対象となる前記シンボルが前記シンボル列の終端である場合、当該シンボルに応じて選択された区間内の一値を前記符号化データとして出力する第４のステップと、
今回のサイクルで処理対象となる前記シンボルに応じて、次回のサイクルよりも後のサイクルで用いられる前記確率分布を更新する第５のステップと
を有することを特徴とする符号化方法。
【請求項１１】
シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、シンボルに応じた区間を特定することによって、シンボル列を符号化データに符号化する符号化処理をコンピュータに実行させる符号化プログラムにおいて、
前回のサイクルで処理対象となる前記シンボルによって更新された前記符号範囲を、前回のサイクルよりも前のサイクルまでに入力された前記シンボルが反映された前記確率分布に応じた区間に分割する第１のステップと、
前記符号範囲から今回のサイクルで処理対象となる前記シンボルに応じた区間を選択する第２のステップと、
今回のサイクルで処理対象となる前記シンボルが前記シンボル列の終端でない場合、当該シンボルに応じて選択された区間を次回のサイクルで用いられる前記符号範囲に設定する第３のステップと、
今回のサイクルで処理対象となる前記シンボルが前記シンボル列の終端である場合、当該シンボルに応じて選択された区間内の一値を前記符号化データとして出力する第４のステップと、
今回のサイクルで処理対象となる前記シンボルに応じて、次回のサイクルよりも後のサイクルで用いられる前記確率分布を更新する第５のステップと
を有する符号化処理をコンピュータに実行させることを特徴とする符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レンジコーダ（Range Coder）を含む算術符号の符号化および復号化に係り、特に、確率分布の更新に関する。
【背景技術】
【０００２】
従来より、エントロピー符号の一つである算術符号や、算術符号から派生したレンジコーダが知られている。レンジコーダは、原理的には算術符号とほぼ同様であるが、算術符号では実数で表現される符号範囲（確率空間）を整数で表現する点で相違する。レンジコーダは、算術符号と比較して、精度の面では若干劣るものの、高速処理が可能であるという利点を有する。
【０００３】
特許文献１には、算術符号処理の高速化を図るために、処理過程で行われる除算をビットシフトに置き換えた適応的多値算術符号が開示されている。この手法において、累積頻度の最大値は２の整数幅で表現される。処理過程における除算は、この幅数を用いたシフト処理に置換され、累積頻度の更新も累積頻度の最大値を２の整数幅に保った形で行われる。
【０００４】
また、特許文献２には、符号範囲を処理対象となるシンボルに応じた区間に分割するという処理をサイクル毎に繰り返して、シンボル列を符号化するシステムが開示されている。このシステムにおいて、符号範囲の更新は、あるシフト量でビットシフトさせるシフト処理によって行われる。このシフト量は、符号範囲の幅を総出現頻度で除算した除算値に基づいて決定される。符号範囲の更新に関して、処理の高速化を図るために、乗算処理および除算処理がシフト処理に置換される。
【０００５】
【特許文献１】特開平１０−３２４９６号公報
【特許文献２】特開２００７−８２０５８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、レンジコーダの復号化、或いは、レンジコーダの上位概念である算術符号の復号化では、シンボルの確率分布が処理サイクル毎に随時更新される。従来のレンジコーダでは、今回のサイクルにおけるデコード出力を、前回のサイクルで更新された符号範囲と、前回のサイクルで更新された確率分布とに基づいて行っている。したがって、前回のサイクルにおける符号範囲の更新および確率分布の更新の双方が終了しない限り、今回のサイクルのデコード出力を開始できないという時間的な制約を伴う。一般に、確率分布の更新は、符号範囲の更新と比較して演算量が多く、その処理時間も長い。そのため、確率分布の更新が復号化処理の高速化を阻害するボトルネックとなり得る。
【０００７】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、レンジコーダを含む算術符号に関して、復号化処理の高速化を図ることである。
【課題を解決するための手段】
【０００８】
かかる課題を解決するために、第１の発明は、シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、符号化データに応じた区間を特定することによって、符号化データからシンボル列を復号化する復号化システムを提供する。この復号化システムは、シンボル出力部と、符号範囲更新部と、確率分布更新部とを有する。シンボル出力部は、前回のサイクルに出力されたシンボルによって更新された符号範囲を、前回のサイクルよりも前のサイクルまでに出力されたシンボルが反映された確率分布に応じた区間に分割するとともに、この符号範囲から符号化データに応じた区間を選択することによって、今回のサイクルのシンボルを出力する。符号範囲更新部は、シンボル出力部から出力された今回のサイクルのシンボルに応じて、次回のサイクルで用いられる符号範囲を更新する。確率分布更新部は、シンボル出力部から出力された今回のサイクルのシンボルに応じて、次回のサイクルよりも後のサイクルで用いられる確率分布を更新する。
【０００９】
第２の発明は、シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、符号化データに応じた区間を特定することによって、符号化データからシンボル列を復号化する復号化方法を提供する。この復号化方法は、前回のサイクルで出力されたシンボルによって更新された符号範囲を、前回のサイクルよりも前のサイクルまでに出力されたシンボルが反映された確率分布に応じた区間に分割する第１のステップと、この符号範囲から符号化データに応じた区間を選択することによって、今回のサイクルのシンボルを出力する第２のステップと、今回のサイクルで出力されたシンボルに応じて、次回のサイクルで用いられる符号範囲を更新する第３のステップと、今回のサイクルで出力されたシンボルに応じて、次回のサイクルよりも後のサイクルで用いられる確率分布を更新する第４のステップとを有する。
【００１０】
第３の発明は、シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、符号化データに応じた区間を特定することによって、符号化データからシンボル列を復号化する符号化処理をコンピュータに実行させる復号化プログラムを提供する。この復号化プログラムは、前回のサイクルで出力されたシンボルによって更新された符号範囲を、前回のサイクルよりも前のサイクルまでに出力されたシンボルが反映された確率分布に応じた区間に分割する第１のステップと、この符号範囲から符号化データに応じた区間を選択することによって、今回のサイクルのシンボルを出力する第２のステップと、今回のサイクルで出力されたシンボルに応じて、次回のサイクルで用いられる符号範囲を更新する第３のステップと、今回のサイクルで出力されたシンボルに応じて、次回のサイクルよりも後のサイクルで用いられる確率分布を更新する第４のステップとを有する復号化処理をコンピュータに実行させる。
【００１１】
第４の発明は、シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、シンボルに応じた区間を特定することによって、シンボル列を符号化データに符号化する符号化システムを提供する。この符号化システムは、境界設定部と、符号範囲更新部と、確率分布更新部と、符号化データ出力部とを有する。境界設定部は、前回のサイクルで処理対象となるシンボルによって更新された符号範囲を、前回のサイクルよりも前のサイクルまでに出力されたシンボルが反映された確率分布に応じた区間に分割する。符号範囲更新部は、この符号範囲から今回のサイクルで処理対象となるシンボルに応じた区間を選択し、この選択された区間を次回のサイクルで用いられる符号範囲に設定する。確率分布更新部は、今回のサイクルで処理対象となるシンボルに応じて、次回のサイクルよりも後のサイクルで用いられる確率分布を更新する。符号化データ出力部は、今回のサイクルで処理対象となるシンボルがシンボル列の終端である場合、符号範囲更新部によって選択された区間内の一値を符号化データとして出力する。
【００１２】
第５の発明は、シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、シンボルに応じた区間を特定することによって、シンボル列を符号化データに符号化する符号化方法を提供する。この符号化方法は、前回のサイクルで処理対象となるシンボルによって更新された符号範囲を、前回のサイクルよりも前のサイクルまでに出力されたシンボルが反映された確率分布に応じた区間に分割する第１のステップと、この符号範囲から今回のサイクルで処理対象となるシンボルに応じた区間を選択する第２のステップと、今回のサイクルで処理対象となるシンボルがシンボル列の終端でない場合、シンボルに応じて選択された区間を次回のサイクルで用いられる符号範囲に設定する第３のステップと、今回のサイクルで処理対象となるシンボルがシンボル列の終端である場合、シンボルに応じて選択された区間内の一値を符号化データとして出力する第４のステップと、今回のサイクルで処理対象となるシンボルに応じて、次回のサイクルよりも後のサイクルで用いられる確率分布を更新する第５のステップとを有する。
【００１３】
第６の発明は、シンボル列に含まれるシンボルの確率分布に応じた区間に分割された符号範囲から、シンボルに応じた区間を特定することによって、シンボル列を符号化データに符号化する符号化処理をコンピュータに実行させる符号化プログラムを提供する。この符号化プログラムは、前回のサイクルで処理対象となるシンボルによって更新された符号範囲を、前回のサイクルよりも前のサイクルまでに出力されたシンボルが反映された確率分布に応じた区間に分割する第１のステップと、この符号範囲から今回のサイクルで処理対象となるシンボルに応じた区間を選択する第２のステップと、今回のサイクルで処理対象となるシンボルがシンボル列の終端でない場合、シンボルに応じて選択された区間を次回のサイクルで用いられる符号範囲に設定する第３のステップと、今回のサイクルで処理対象となるシンボルがシンボル列の終端である場合、シンボルに応じて選択された区間内の一値を符号化データとして出力する第４のステップと、今回のサイクルで処理対象となるシンボルに応じて、次回のサイクルよりも後のサイクルで用いられる確率分布を更新する第５のステップとを有する符号化処理をコンピュータに実行させる。
【００１４】
ここで、第１から第６の発明のいずれかにおいて、確率分布の更新は、今回のサイクルで出力されたシンボルと、従前のサイクルで出力された少なくとも一つのシンボルとを用いて行ってもよい。この場合、確率分布の更新は、上記従前のサイクルで出力された少なくとも一つのシンボルよりも大きな重み付けを上記今回のサイクルで出力されたシンボルに施した上で行うことが好ましい。
【発明の効果】
【００１５】
第１から第３の発明において、今回のサイクルのデコード出力にはシンボルの確率分布が用いられるが、この確率分布として、前回のサイクルに出力されたシンボルを反映したものではなく、前回のサイクルよりも前のサイクルまでに出力されたシンボルを反映したものを用いる。したがって、前回のサイクルに出力されたシンボルを反映するための確率分布の更新が終了しているか否かにかかわりなく、今回のサイクルのデコード出力を開始できる。その結果、復号化処理の高速化を図ることができる。
【００１６】
また、第４から第６の発明によれば、このような復号化処理の一部変更に対応して、その前処理に相当する符号化においても同様の変更を行う。これにより、復号化によって生成されたシンボル列と、本来のシンボル列との同一性を保証することができる。
【発明を実施するための最良の形態】
【００１７】
本発明は、概念的に類似するレンジコーダおよび算術符号のいずれに対しても適用可能であるが、以下の各実施形態では、レンジコーダへの適用例について説明する。算術符号への適用については、当業者であれば、本明細書の記載を以て容易に理解できよう。また、多値コーディックを一例としているが、二値コーディックにも適用可能であることはいうまでもない。
【００１８】
本実施形態に係るレンジコーダの具体的なシステム構成の説明に先立ち、まず、レンジコーダの概要について説明する。算術符号の一種であるレンジコーダは、入力された任意の長さのシンボル列をある実数に写像することで圧縮を行い、この実数を逆写像することで元のシンボル列への伸張を行う可逆圧縮技術である。実数に写像する際、シンボルの種類（以下、単にシンボルという）の確率分布を元に、そのシンボルが占有する実数の範囲が漸次的に決定される。この確率分布を算出する方法には様々なものが存在するが、符号化（エンコード）時には、過去に入力された各シンボル（入力シンボル）の出現頻度に基づき確率分布が計算される。逆に、復号化（デコード）時には、デコード結果である出力シンボル列を用いて、各シンボルの出力頻度に基づき確率分布が計算される。
【００１９】
図１は、４つのシンボルａ〜ｄを含むシンボル列を対象としたデコードの概念説明図であり、デコードの処理過程における符号範囲の時系列的な推移を示す。このデコード処理においては、基本的に、符号範囲から符号化データに応じた区間を特定するといった処理がサイクル毎に繰り返される。ここで、符号範囲は、下限値、上限値および幅といった３つのファクターを有するが、いずれか２つが特定されれば、残りの一つは自ずと特定される。例えば、ある符号範囲の下限値と、その幅とが特定されれば、残りの上限値は（下限値＋幅）として一義的に特定されるといった如くである。したがって、符号範囲を規定する値としては、上述した３つのファクターのうちの任意の２つを用いれば足りる。以下の説明では、符号範囲を規定する２つのファクター（例えば下限値および幅）を「符号範囲特定値ＲＮＧ」と総称する。
【００２０】
符号範囲は、シンボルａ〜ｄの確率分布に応じて、複数の区間ａ〜ｄに分割されており、区間ａ〜ｄのそれぞれがシンボルａ〜ｄのいずれかに対応付けられている。取り扱うシンボルが４種類（ａ，ｂ，ｃ，ｄ）の場合、符号範囲が４つの区間に分割され、例えば、下から順にａ，ｂ，ｃ，ｄが割り当てられる。区間ａ〜ｄのそれぞれは、互いに隣接した区間の境界を示す境界値ＢＮＤ１〜３によって規定される。区間ａは、符号範囲における境界値ＢＮＤ１未満の範囲であり、区間ｄは、符号範囲における境界値ＢＮＤ３以上の範囲となる。また、ｘ以上ｙ未満の区間を［ｘ，ｙ）で表すと、区間ｂは［ＢＮＤ１，ＢＮＤ２）の範囲、区間ｃは［ＢＮＤ２，ＢＮＤ３）となる。
【００２１】
エンコーダからデコーダに引き渡される情報は、両者の間で処理に関する必要な取り決めがなされていることを条件として、基本的に符号化データＣｏｄｅのみである。したがって、シンボル列のデコードは、符号化データＣｏｄｅ（一値）に基づいて行われる。符号化データＣｏｄｅは、符号範囲内における特定の値を示す。必要な取り決めとしては、符号範囲特定値ＲＮＧの初期値、境界値ＢＮＤ１〜３の初期値、および、符号範囲が狭くなった際にこれを伸張する条件や方法を規定するスケーリング規則等が挙げられる。なお、デコード側に引き渡すべきその他の情報として、シンボル列の終端を特定するために用いられるシンボル総数を必要に応じて含めてもよい（シンボル総数が不要な手法も存在する）。
【００２２】
算術符号では、区間［0，1）を初期状態として分割が開始される。これに対して、レンジコーダでは、［0，1）を分割するのではなく、最初に大きな区間、例えば［0，1000）を設定して、それを小さな区間に分割していく。整数処理を前提とするレンジコーダは、記号列が長くなると区間が狭くなって実数処理が生じるが、その場合には、スケーリング（符号範囲を伸張すること）によって対応する。例えば、［0、1000）を分割していき［123，124）になった場合、もうこれ以上分割できないので、区間を100倍して［12300，12400）に伸張するといった如くである。その際、符号範囲全体の大きさは［0，1000）ではなく、それを1000倍した［0，100000）と考える。単純に考えると、区間を表すために多倍長整数が必要になるが、区間を伸張するタイミングを適切に定めることにより、通常の整数演算だけで済む。デコード時には、エンコード時と同じタイミングでスケーリングを行うことで、符号化コードＣｏｄｅから本来のシンボル列への復元が保証される。
【００２３】
図示したケースにおいて、まず、初回のサイクル（ｎ＝１）の符号範囲では、符号化コードＣｏｄｅが示す値が区間ｂ内（［ＢＮＤ１，ＢＮＤ２））に存在する。したがって、初回のサイクルでは、この区間ｂに対応付けられたシンボルｂがデコード結果として出力される。これに続く２回目のサイクル（ｎ＝２）では、この符号化コードＣｏｄｅが区間ｃ内なので、これに対応付けられたシンボルｃが出力される。以下、３回目のサイクル（ｎ＝３）ではシンボルｄ、４回目のサイクル（ｎ＝４）ではシンボルａ、５回目のサイクル（ｎ＝５）ではシンボルｂがそれぞれ出力される。このような繰り返し処理によって、符号化コードＣｏｄｅを入力としたデコード結果として、”ｂｃｄａｂ”というシンボル列が出力される。なお、同図では、符号化コードＣｏｄｅの値が各サイクルで異なるように見えるが、これは符号範囲のサイズを正規化しているからであって、実際には同一値である点に留意されたい（図２についても同様）。
【００２４】
符号範囲は、サイクル毎に更新され、前回のサイクル（以下、「前サイクル」という）の出力シンボルに応じて更新されたものが今回のサイクル（以下、「現サイクル」という）で、現サイクルの出力シンボルに応じて更新されたものが次回のサイクル（以下、「次サイクル」という）でそれぞれ用いられる。具体的には、前サイクルの符号範囲のうち、前サイクルで出力されたシンボルに対応する区間が切り出され、この切り出された区間が次サイクルで用いられる符号範囲となる。例えば、初回のサイクルでシンボルｂが出力された場合、区間ｂ（［ＢＮＤ１，ＢＮＤ２））が２回目のサイクルの符号範囲となるといった如くである。このような区間の切り出しによって、符号範囲の幅は、サイクルの推移にともない狭くなっていく。そして、実数での処理が必要になるほど符号範囲が狭くなった場合、スケーリングによって符号範囲がｎ倍に伸張される。スケーリングの実行判定は、どのようなものであってもよいが、一例として、符号範囲の幅がシンボルの出現頻度の総和よりも小さくなったか否かという基準を用いることができる。
【００２５】
一方、シンボルａ〜ｄの確率分布もサイクル毎に更新されるが、この確率分布は、符号範囲に区間を設定するために、換言すれば、区間の境界を規定する境界値ＢＮＤ１〜３を設定するために用いられる。一般に、あるシンボルが出現する確率が高くなるほど、これに対応する区間が広くなる。例えば、従前のシンボルの出現回数が、ａ＝１回、ｂ＝２回、ｃ＝３回、ｄ＝４回の場合、区間ａ〜ｄが１：２：３：４の比で設定されるといった如くである。
【００２６】
この確率分布の更新に関して、従来のレンジコーダは、前サイクルまでの出力シンボルを反映した確率分布を現サイクルで、これに現サイクルの出力シンボルを反映した確率分布を次サイクルでそれぞれ用いている。一般に、高速処理が求められるレンジコーダでは、シンボル列の入力レートがシステムの最大動作レートで動作することが望ましい。しかしながら、基本的に算術符号化は重い処理であり、符号化・復号化処理がシステムの処理速度を律速してしまう場合が多い。デコード時には、シンボルの確率分布の計算に出力シンボル列が用いられるので、原理的に、エンコードよりもデコードの方が処理が重くなる。そこで、デコード時間の短縮を図るべく、確率分布の適用時期（サイクル）に変更を加える。具体的には、現サイクルでは、前サイクルの出力シンボルを反映したものではなく、前サイクルよりも前のサイクルまでの出力シンボルを反映した確率分布を用いる。また、現サイクルの出力シンボルを反映した確率分布は、次サイクルではなく、次サイクルよりも後のサイクルで用いる。
【００２７】
図２は、４つのシンボルａ〜ｄを含むシンボル列を対象としたエンコードの概念説明図であり、エンコードの処理過程における符号範囲の時系列的な推移を示す。このエンコード処理においては、基本的に、符号範囲からシンボルに応じた区間を選択し、この選択された区間を新たな符号範囲に設定するといった処理がサイクル毎に繰り返される。
【００２８】
図示したケースにおいて、初回のサイクル（ｎ＝１）で処理対象となるシンボル（入力シンボル）はシンボルｂである。したがって、初期状態の符号範囲のうち、この入力シンボルｂに対応付けられた区間ｂ（＝［ＢＮＤ１，ＢＮＤ２）が選択され、これが次回（ｎ＝２）の符号範囲に設定される。これに続く２回目のサイクル（ｎ＝２）では、初回のサイクルで設定された符号範囲のうち、今回の入力シンボルｃに応じた区間ｃが選択され、これが次回（ｎ＝３）の符号範囲に設定される。同様に、３回目のサイクル（ｎ＝３）では区間ｄ、４回目のサイクル（ｎ＝４）では区間ａ、５回目のサイクル（ｎ＝５）では区間ｂがそれぞれ選択され、符号範囲の更新が繰り返される。そして、５回目のサイクルで、シンボル列”ｂｃｄａｂ”の終端シンボル（ｎ＝５のシンボルｂ）に応じた区間ｂが選択されると、この区間ｂ内の任意の一値（例えば区間ｂの下限値）が符号化データＣｏｄｅとして出力される。
【００２９】
デコード時間の短縮を意図した変更にともない、これとの整合性を図るために、エンコードの処理も同様に変更する。すなわち、シンボルａ〜ｄの確率分布の更新に関して、現サイクルでは、前サイクルの入力シンボルを反映した確率分布ではなく、前サイクルよりも前のサイクルまでの入力シンボルを反映した確率分布を用いる。また、現サイクルの入力シンボルを反映した確率分布は、次サイクルではなく、次サイクルよりも後のサイクルで用いる。
【００３０】
以下に挙げる各実施形態では、一例として、確率分布の適用時期を２サイクルずらすケースについて説明する。この場合、現サイクルｎでは、前々回のサイクル（ｎ−２）（以下、「前々サイクル」という）までの出力シンボルが反映された確率分布が用いられる。また、現サイクルｎの出力シンボルを反映した確率分布は、次々回のサイクル（ｎ＋２）（以下、「次々サイクル」という）で用いられる。しかしながら、本発明はこれに限定されるものではなく、確率分布の適用時期を３サイクル以上ずらしても適用可能であることは当然である。
【００３１】
(第１の実施形態）
図３は、第１の実施形態に係る復号化システム（デコーダ）のブロック構成図である。この復号化システムは、記憶部１と、シンボル処理部２と、符号範囲更新部３と、確率分布更新部４とを主体に構成されており、同図の左端から右端に至るまでの処理が単位時間（サイクル）毎に行われる。
【００３２】
記憶部１には、符号化データＣｏｄｅと、符号範囲特定値ＲＮＧと、出現頻度表ＦＯＡと、出力シンボルＳｙｍとが記憶・格納される。符号化データＣｏｄｅは、エンコーダ側から引き渡される情報であり、任意の長さのシンボル列を写像した実数に相当する。符号範囲特定値ＲＮＧは、あるサイクルにおける符号範囲を規定し、初回のサイクル（ｎ＝１）では、エンコーダ−デコーダ間で取り決められた初期値が用いられる。出現頻度表ＦＯＡは、シンボルの確率分布を近似したものであり、一例として、それぞれのシンボルの出現回数を示すカウント値を用いることができる。なお、エンコーダによって生成された圧縮ファイルには、上記符号化データＣｏｄｅ以外に、シンボル列を構成するシンボルの総数も含まれており、これによって、デコーダはシンボル列の終端を把握する。
【００３３】
シンボル処理部２は、現サイクルｎで設定された符号範囲から符号化データＣｏｄｅに応じた区間を選択することによって、現サイクルｎの出力シンボルＳｙｍ(n)を決定する。このシンボル処理部２は、境界設定部５と、出力判定部６とを有する。境界設定部５は、符号範囲に対する区間設定を行うとともに、必要に応じて上述したスケーリングも行う。具体的には、まず、符号範囲特定値ＲＮＧ(n-1)および出現頻度表ＦＯＡ(n-1)が記憶部１から読み出される。符号範囲特定値ＲＮＧ(n-1)は、前サイクル（ｎ−１）の出力シンボルＳｙｍ(n-1)によって決定された符号範囲である。また、出現頻度表ＦＯＡ(n-1)は、前サイクル（ｎ−１）で更新されたものであるが、後述するメカニズムから、これには、前々サイクル（ｎ−２）までに出力されたシンボルＳｙｍ(1)，(2)，・・・,(n-2)が反映されている。したがって、前サイクル（ｎ−１）で更新された確率分布には、このサイクル（ｎ−１）で出力されたシンボルＳｙｍ(n-1)は反映されていない。符号範囲特定値ＲＮＧ(n-1)によって規定される符号範囲は、出現頻度表ＦＯＡ(n-1)によって特定される確率分布に応じた区間ａ〜ｄに分割される。そして、区間ａ−ｂの境界を示す境界値ＢＮＤ１、区間ｂ−ｃ間の境界を示す境界値ＢＮＤ２、および、区間ｃ−ｄ間の境界を示す境界値ＢＮＤ３がそれぞれ算出される。
【００３４】
なお、境界設定部５は、符号範囲の更新に必要な乗算・除算処理をシフト処理に置き換えて行ってもよい。シフト処理への置き換えは、この更新処理の高速化や回路規模の縮小を図る上で有効である。このシフト処理の詳細については、特開２００７−８２０５８号公報に開示されているので、必要ならば参照されたい。本実施形態では、符号範囲の幅が確率分布のダイナミックレンジの１倍以上２倍未満になるようにスケーリング処理を行う。
【００３５】
一方、出力判定部６は、現サイクルｎで境界設定部５によって算出された境界値ＢＮＤ１〜３と、符号化データＣｏｄｅとに基づいて、以下の出力規則に則って、現サイクルｎの出力シンボルＳｙｍ(n)を生成する。生成された出力シンボルＳｙｍ(n)は、記憶部１に格納される。
（出力規則）
符号化データの値                出力シンボルＳｙｍ
Ｃｏｄｅ＜ＢＮＤ１                    シンボルａ
ＢＮＤ１≦Ｃｏｄｅ＜ＢＮＤ２          シンボルｂ
ＢＮＤ２≦Ｃｏｄｅ＜ＢＮＤ３          シンボルｃ
ＢＮＤ≦Ｃｏｄｅ                      シンボルｄ
【００３６】
符号範囲更新部３は、現サイクルｎの出力シンボルＳｙｍ(n)に応じて符号範囲を更新し、新たな符号範囲特定値ＲＮＧ(n)を算出する。例えば、出力シンボルＳｙｍ(n)がシンボルｂの場合、［ＢＮＤ１，ＢＮＤ２）の範囲が新たな符号範囲特定値ＲＮＧ(n)に設定される。この符号範囲特定値ＲＮＧ(n)は、記憶部１に格納され、次サイクル（ｎ＋１）で用いられる。
【００３７】
確率分布更新部４は、記憶部１から出現頻度表ＦＯＡ(n-1)および出力シンボルＳｙｍ(n-1)を読み出し、出力シンボルＳｙｍ(n-1)を反映した新たな出現頻度表ＦＯＡ(n)を生成する。現サイクルｎで生成された出現頻度表ＦＯＡ(n)は、記憶部１に再び格納される。確率分布更新部４は、シンボル処理部２の処理と並行して確率分布の更新を行う。
【００３８】
ここで留意すべきは、現サイクルｎの出力シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n)は、次サイクル（ｎ＋１）ではなく、次々サイクル（ｎ＋２）の境界設定・デコード出力で用いられる点である。この点を図４のタイミングチャートに基づいて説明する。
【００３９】
１サイクル中で行われる処理には、境界設定部５による境界設定、出力判定部６によるデコード出力、符号範囲更新部３による符号範囲更新、および、確率分布更新部４による確率分布更新が存在する。ここで、デコード出力、境界設定および符号範囲更新には、処理の依存関係があり、デコード出力は境界設定後に行われ、符号範囲更新はデコード出力後に行われる。また、境界設定および確率分布更新は、サイクルの開始タイミングにおいて並列処理にて行われる。なお、同図は、各サイクルの開始タイミングで確率分布更新を開始するケースを示しているが、サイクルを跨いでこれを行ってもよい。
【００４０】
サイクルｎにおいて、境界設定が終了すると、それに続くデコード出力によって出力シンボルＳｙｍ(n)が出力される。デコード出力は、境界設定を以て可能になるので、両者の間には依存関係（ａ）が成立する。デコードされた出力シンボルＳｙｍ(n)は記憶部１に格納されるとともに、この出力シンボルＳｙｍ(n)に基づいて、符号範囲更新が行われる。符号範囲更新は、デコード出力を以て可能になるので、両者の間には依存関係（ｂ）が成立する。なお、サイクルｎの出力シンボルＳｙｍ(n)は、同一サイクルｎで更新される出現頻度表ＦＯＡ(n)には未だ反映されず、同一サイクルｎで行われる境界設定・デコード出力にも用いられない。
【００４１】
次サイクル（ｎ＋１）において、シンボルＳｙｍ(n)が記憶部１から読み出され、このサイクル（ｎ＋１）の確率分布更新によって、シンボルＳｙｍ(n)が出現頻度表ＦＯＡ(n+1)に反映される。したがって、サイクルｎのデコード出力と、サイクル（ｎ＋１）の確率分布更新との間には、依存関係（ｃ）が成立する。シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n+1)は記憶部１に格納される。なお、サイクル（ｎ＋１）で更新された出現頻度表ＦＯＡ(n+1)は、同一サイクル（ｎ＋１）の境界設定・デコード出力には用いられない。
【００４２】
次々サイクル（ｎ＋２）において、シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n+1)が記憶部１から読み出され、サイクル（ｎ＋２）の境界設定にこれが用いられる。したがって、サイクル（ｎ＋１）の確率分布更新と、サイクル（ｎ＋２）の境界設定との間には、依存関係（ｄ）が成立する。そして、この境界設定に基づいて、同一サイクル（ｎ＋２）のデコード出力が行われる（依存関係（ｅ））。
【００４３】
以上のプロセスから、サイクルｎの出力シンボルＳｙｍ(n)が出現頻度表ＦＯＡ(n+1)に反映されるまでに１サイクルを要し、これを反映した出現頻度表ＦＯＡ(n+1)が境界設定・デコード出力に用いられるまでに更に１サイクルを要するので、合計２サイクルずれることになる。
【００４４】
本実施形態によれば、デコード処理の高速化を図ることができるという効果を奏する。高速化を図る上でのポイントは、同一サイクル内の処理において、デコード出力に依存する処理を減らすことである。従来のレンジコーダでは、出現頻度更新および確率分布更新の双方がデコード出力に依存しており、原理的にエンコーダよりも処理が重くなる。一般に、確率分布更新は、出現頻度更新よりも演算量が多く処理時間も長い。そのため、確率分布更新が高速化を図る上でのボトルネックとなる。そこで、本実施形態では、確率分布の適用時期を１サイクルではなく２サイクル以上ずらすことで、デコード出力との依存関係を低減させる。すなわち、現サイクルｎのデコード出力（およびその前処理にあたる境界設定）に必要な確率分布としては、前サイクル（ｎ−１）のシンボルＳｙｍ(n-1)を反映したものではなく、前々サイクル（ｎ−２）までに出力されたシンボル列Ｓｙｍ(1)，Ｓｙｍ(2)，・・・，Ｓｙｍ(n-2)を反映したものが用いられる。これにより、現サイクルｎにおけるデコード出力は、前サイクル（ｎ−１）に出力されたシンボルを出現頻度表ＦＯＡ(n-1)に反映する処理が終了しているか否かにかかわりなく開始できる。その結果、このような時間的制約が緩和された分だけデコード処理の高速化を図ることができる。
【００４５】
この点に関して、比較例として、サイクルｎで更新された符号範囲と、サイクルｎの出力シンボルを反映した出現頻度表とに基づいて、次サイクル（ｎ＋１）のデコード出力を行うケースについて考える。図５は、この比較例におけるデコード処理のタイミングチャートである。この場合、１サイクルで行われる境界設定、デコード出力、符号範囲更新および確率分布更新の全てに依存関係が生じる（同図に示した矢印参照）。デコード出力は境界設定の後、符号範囲更新および確率分布更新はデコード出力の後といった如くである。サイクル（ｎ＋１）における境界設定・デコード出力は、前サイクルｎにおける符号範囲更新および確率分布更新の双方が終了しなければ開始できない。したがって、符号範囲更新が終了してから確率分布更新が終了するまでの時間τが全体的な処理速度を律速させるボトルネックとなってしまう。
【００４６】
また、本実施形態によれば、シンボル処理部２の出力を確率分布更新部４に直接入力する必要がない。そのため、確率分布更新部４へデータを伝達するための駆動回路等を設ける必要がなくなるので、シンボル処理部２の駆動時間が短くなり、回路全体の動作速度の向上（高クロック周波数での動作）が可能になる。
【００４７】
なお、上述した実施形態において、デコーダ入力となる符号化データＣｏｄｅを構成する全ビットを各サイクルで参照するのではなく、符号範囲の幅に応じて、必要なビット列を上位ビットから順次取り込んで参照してもよい。
【００４８】
（第２の実施形態）
図６は、第２の実施形態に係る符号化システム（エンコーダ）のブロック構成図である。このエンコーダは、第１の実施形態に係るデコーダに供給する圧縮ファイルを生成するために用いられ、記憶部１１と、境界設定部１２と、符号範囲更新部１３と、確率分布更新部１４と、符号化データ出力部１５とを主体に構成されている。
【００４９】
記憶部１１には、入力シンボルＳｙｍと、符号範囲特定値ＲＮＧと、出現頻度表ＦＯＡとが記憶・格納される。入力シンボルＳｙｍは、符号化対象となるシンボル列ＳＹＭのうちの１シンボルであり、所定の順序でサイクル毎に記憶部１に順次取り込まれる。シンボル列ＳＹＭから入力シンボルＳｙｍの取り込みに１サイクルを要するので、これが出現頻度に反映されるのに１サイクルずれることになる。
【００５０】
境界設定部１２は、前サイクル（ｎ−１）で処理対象となった入力シンボルＳｙｍ(n-1)によって更新された符号範囲を、出現頻度表ＦＯＡ(n-1)に応じた区間に分割する。これによって、現サイクルｎの符号範囲に区間の境界が設定され、境界値ＢＮＤ１〜３が出力される。出現頻度表ＦＯＡ(n-1)には、前々サイクル（ｎ−２）までに出力されたシンボルＳｙｍ(1)，Ｓｙｍ(2)，・・・，Ｓｙｍ(n-2)が反映されている。
【００５１】
符号範囲更新部１３は、境界設定部１２によって区間の境界が設定された符号範囲から現サイクルｎで処理対象となる入力シンボルＳｙｍ(n)に応じた区間を選択する。これによって、この区間が次サイクル（ｎ＋１）で用いられる符号範囲として設定され、これを規定する符号範囲特定値ＲＮＧ(n)が記憶部１に格納される。確率分布更新部１４は、現サイクルｎで処理対象となる入力シンボルＳｙｍ(n)に応じて、次々サイクル（ｎ＋２）で用いられる出現頻度表ＦＯＡ(n)を更新し、これを記憶部１に格納する。符号化データ出力部１５は、シンボル列ＳＹＭの終端シンボルの場合、符号範囲更新部１４によって選択された区間内の一値を符号化データＣｏｄｅとして出力する。
【００５２】
デコーダの変更を考慮して、現サイクルｎの出力シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n)は、以下のプロセスによって、次サイクル（ｎ＋１）ではなく、次々サイクル（ｎ＋２）で用いられる。サイクルｎの入力シンボルＳｙｍ(n)は、記憶部１に格納される。このサイクルｎにおいて、シンボルＳｙｍ(n)は出現頻度表ＦＯＡ(n)に未だ反映されず、このサイクルｎの境界設定にも用いられない。
【００５３】
次サイクル（ｎ＋１）において、シンボルＳｙｍ(n)が記憶部１から読み出され、このサイクル（ｎ＋１）で出現頻度表ＦＯＡ(n+1)に反映される。シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n+1)は記憶部１に格納される。ただし、サイクル（ｎ＋１）において、この出現頻度表ＦＯＡ(n+1)は、このサイクル（ｎ＋１）の境界設定に未だ用いられない。
【００５４】
次々サイクル（ｎ＋２）において、シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n+1)が記憶部１から読み出され、このサイクル（ｎ＋２）の境界設定にこれが用いられる。以上のプロセスからわかるように、サイクルｎの入力シンボルＳｙｍ(n)が境界設定に用いられるまでに２サイクルを要する。
【００５５】
このように、本実施形態では、デコード側の一部変更に対応して、その前処理に相当するエンコード側においても同様の変更を行う。これにより、復号化によって生成されたシンボル列と、本来のシンボル列との同一性を保証することができる。
【００５６】
なお、デコーダの高速化のために、結果的にエンコード処理手順を一部変更したため、厳密には、圧縮結果が異なるものになり、圧縮率も同一にはならない。しかしながら、出現頻度表ＦＯＡの使用目的は、あくまでシンボルの確率分布を使用することである。したがって、シンボル列がある程度入力された後は、処理で使用する確率分布の１サイクルあたりの変化が非常に少なく、圧縮率等に有意な差は原理的に発生しない。通常、処理の最適化は、圧縮結果が変化しないように行うことが多いが、本手法では圧縮結果の変化を許容した最適化を行う。この前提が本発明に至る重要なポイントである。
【００５７】
（第３の実施形態）
第３の実施形態は、上述した第１の実施形態に係るデコーダを基本構成とし、これを最適化したものである。第１の実施形態に係る復号化システムは、上述したように確率分布更新処理に関して明らかな効果があるものの、符号範囲更新処理に関しては比較的効果が少ない。そこで、デコーダのみ処理手順を最適化することで、本手法による利点の最大化を図る。
【００５８】
図７は、本実施形態にかかるデコーダのブロック構成図である。このデコーダは、第１の実施形態と同様、記憶部１と、境界設定部５および出力判定部６によって構成されたシンボル処理部２と、符号範囲更新部３と、確率分布更新部４とを主体に構成されている。第１の実施形態との基本的な相違点は、境界設定部５および出力判定部６の接続関係であり、境界設定部５が出力判定部６の後段に位置している。また、記憶部１に記憶すべき情報として境界値ＢＮＤ１〜３を追加されている。
【００５９】
図８は、本実施形態にかかる復号化処理のタイミングチャートである。本実施形態では、デコード出力を以て境界設定が行われる。１サイクル中の処理には、境界設定部５による境界設定、出力判定部６によるデコード出力、符号範囲更新部３による符号範囲更新、および、確率分布更新部４による確率分布更新が存在する。ここで、デコード出力、符号範囲更新および境界設定には処理の依存関係があり、符号範囲更新はデコード出力後、境界設定は符号範囲更新後にそれぞれ行われる。また、デコード出力および確率分布更新は、サイクルの開始タイミングにおいて並列処理にて行われる。なお、同図は、各サイクルの開始タイミングで確率分布更新を開始するケースを示しているが、サイクルを跨いでこれを行ってもよい。
【００６０】
サイクルｎでは、デコード出力および確率分布更新が並行処理で行われる。デコード出力に関しては、前サイクル（ｎ−１）で更新された境界値ＢＮＤ(n-1)と、符号化データＣｏｄｅとが記憶部１から読み出される。そして、上述した出力規則にしたがって、サイクルｎの出力シンボルＳｙｍ(n)が生成される。生成された出力シンボルＳｙｍ(n)は、記憶部１に格納されるとともに、符号範囲更新部３に供給される。一方、確率分布更新に関しては、前サイクル（ｎ−１）で更新された出現頻度表ＦＯＡ(n-1)と、前サイクル（ｎ−１）の出力シンボルＳｙｍ(n-1)とが記憶部１から読み出される。このサイクルｎで更新された出現頻度表ＦＯＡ(n)は、記憶部１に格納されるとともに、境界設定部５に供給される。
【００６１】
デコード出力の終了を以て、符号範囲更新が開始される。これによって、サイクルｎの符号範囲から出力シンボルＳｙｍ(n)に応じた区間が選択され、これが新たな符号範囲となる。この符号範囲を規定する符号範囲特定値ＲＮＧ(n)は、境界設定部５を経て記憶部１に格納される。符号範囲更新と、デコード出力との間には依存関係（ａ）が成立する。
【００６２】
符号範囲更新の終了を以て、境界設定が開始される。これによって、サイクルｎで新たに設定された符号範囲に出現頻度表ＦＯＡ(n)に応じた区間が設定され、境界値ＢＮＤ(n)が記憶部１に格納される。符号範囲更新と、境界設定との間には、依存関係（ｂ）が成立する。なお、出力シンボルＳｙｍ(n)は、サイクルｎで更新される確率分布には未だ反映されないが、サイクルｎで行われる境界設定には用いられる。
【００６３】
次サイクル（ｎ＋１）において、記憶部１から出力シンボルＳｙｍ(n)が読み出され、このサイクル（ｎ＋１）の確率分布更新によって、シンボルＳｙｍ(n)が出現頻度表ＦＯＡ(n+1)に反映される。したがって、サイクルｎのデコード出力と、サイクル（ｎ＋１）の確率分布更新との間には、依存関係（ｃ）が成立する。シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n+1)は記憶部１に格納されるが、同一サイクル（ｎ＋１）の境界設定に未だ用いられない。
【００６４】
次々サイクル（ｎ＋２）において、シンボルＳｙｍ(n)を反映した出現頻度表ＦＯＡ(n+1)が記憶部１から読み出され、サイクル（ｎ＋２）のデコード出力にこれが用いられる。したがって、サイクル（ｎ＋１）の確率分布更新と、サイクル（ｎ＋２）のデコード出力との間には、依存関係（ｄ）が成立する。
【００６５】
以上のプロセスから、サイクルｎの出力シンボルＳｙｍ(n)が出現頻度表ＦＯＡ(n+1)に反映されるまでに１サイクルを要し、反映された出現頻度表ＦＯＡ(n+1)がデコード出力に用いられるまでに更に１サイクルを要するので、合計２サイクルずれることになる。
【００６６】
本実施形態によれば、サイクルの最初に行われる処理が境界設定ではなくデコード出力になる。したがって、各サイクルの開始直後にシンボルを出力することが可能となる。また、デコード出力に依存する処理が減少することで、集積回路等での実装において、各トランジスタの負荷が減ることで応答速度が向上し、デコーダ処理全体の高速化にも寄与する。
【００６７】
なお、本実施形態にかかるデコーダに対応するエンコーダについては、図６に示したエンコーダをベースに本実施形態で述べた変更を加えればよく、当業者であれば、その構成を当然に想定できるであろうから、ここでの説明を省略する。
【００６８】
また、上述した各実施形態では、シンボルの確率分布を表すものとして出現頻度表ＦＯＡを使用するケースについて説明した。図９に示すように、出現頻度表ＦＯＡは、シンボルの出力確率の相対的な比率を近似したものであるが、本発明はこれに限定されず、以下のケース（これらのケースの組合わせも可能）を含めて、シンボルの確率分布を近似できる機構のいずれを採用してもよい。
【００６９】
（１）出現頻度に更に係数処理を導入した近似
図１０に示すように、シンボルの出現頻度に対して、出現頻度直近に出現したシンボルに対して大きな重み付けを行う。具体的には、確率分布更新部４，１４は、現サイクルｎのシンボルＳｙｍ(n)と、従前の少なくとも一つのシンボルＳｙｍ(1)，Ｓｙｍ(2)，・・・，Ｓｙｍ(n-1)と畳み込んで、シンボルの出現頻度に対する係数をそれぞれ算出する。この畳み込みに際しては、各シンボルが直近で出現するほど係数を大きくする。そして、当初の出現頻度表ＦＯＡに頻度に対する係数を乗じることによって、補正した出現頻度表ＦＯＡ’を算出し、これを出力確率として用いる。このような重み付けは、空間的にムラが大きい画像や時間的にムラが大きい音声を圧縮対象とする場合に有効である。
【００７０】
（２）確率密度関数を用いた確率分布の近似
図１１に示すように、シンボルの確率分布によっては、正規分布を使用して、前々サイクルまでの出力シンボルで出力シンボルの平均と分散を計算し、シンボルの出力確率を算出する。正規分布以外にもポアソン分布など、圧縮対象によって様々な選択肢がある。
【００７１】
（３）マルコフモデルを用いた確率分布の近似
図１２に示すように、マルコフモデルを使用して時間的・空間的な変化に強い近似を行う。シンボルの確率分布が時空的に変化する場合には、複数の確率密度関数または複数の係数を用意して、サイクル毎に最適な確率密度関数または係数を選択する方法が考えられる（出現頻度表Ａ，Ｂの切り換え）。例えば、画像領域の特性に応じて切り換えるといった如くである。
【００７２】
（４）隠れマルコフモデル（ＨＭＭ）を用いた確率分布の近似
図１３に示すように、隠れマルコフモデルを使用して遷移自体も確率的に近似する。確率分布の時空的変化が明確でない場合には、確率分布関数または係数に対して使用される確率を算出し、それら（確率分布関数、係数）を重み付け和する方法が考えられる。
【図面の簡単な説明】
【００７３】
【図１】レンジコーダにおける復号化の概念説明図
【図２】レンジコーダにおける符号化の概念説明図
【図３】第１の実施形態にかかる復号化システムのブロック構成図
【図４】第１の実施形態にかかる復号化処理のタイミングチャート
【図５】比較例の復号化処理のタイミングチャート
【図６】第２の実施形態にかかる符号化システムのブロック構成図
【図７】第３の実施形態にかかる復号化システムのブロック構成図
【図８】第３の実施形態にかかる復号化処理のタイミングチャート
【図９】出現頻度表を用いた確率分布の近似の説明図
【図１０】出現頻度に係数処理を導入した確率分布の近似の説明図
【図１１】確率密度関数を用いた確率分布の近似の説明図
【図１２】マルコフモデルを用いた確率分布の近似の説明図
【図１３】隠れマルコフモデル（ＨＭＭ）を用いた確率分布の近似の説明図
【符号の説明】
【００７４】
１  記憶部
２  シンボル処理部
３  符号範囲更新部
４  確率分布更新部
５  境界設定部
６  出力判定部
１１  記憶部
１２  境界設定部
１３  符号範囲更新部
１４  確率分布更新部
１５  符号化データ出力部
【図１】
0004524501.tif 000002
【図２】
0004524501.tif 000003
【図３】
0004524501.tif 000004
【図４】
0004524501.tif 000005
【図５】
0004524501.tif 000006
【図６】
0004524501.tif 000007
【図７】
0004524501.tif 000008
【図８】
0004524501.tif 000009
【図９】
0004524501.tif 000010
【図１０】
0004524501.tif 000011
【図１１】
0004524501.tif 000012
【図１２】
0004524501.tif 000013
【図１３】
0004524501.tif 000014