(57)【要約】【課題】複数種類の符号表から時系列データを符号化するための符号表を選択するための処理量を削減する。【解決手段】予め定められた離散時間区間における時系列データのデータ値xの頻度h(x)を求め、各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)と、求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と各データ値xと各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)との積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出し、算出された積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間における時系列データを符号化するための符号表を選択する。【選択図】図６
2011217381.tif 000002
【特許請求の範囲】
【請求項１】
時系列データを符号化するための符号表を選択する符号表選択方法であって、
(A) 予め定められた離散時間区間における時系列データのデータ値xの頻度h(x)を求めるステップと、
(B) 各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)と、前記ステップ(A)で求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と各データ値xと各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)と、の積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出するステップと、
(C) 前記ステップ(B)で算出された積和SP(j)を用い、複数種類の符号表T(j)及び基準符号表T(J)から、前記離散時間区間における時系列データを符号化するための符号表を選択するステップと、
を有する符号表選択方法。
【請求項２】
時系列データを符号化するための符号表を選択して時系列データの符号化を行う符号化装置であって、
予め定められた離散時間区間における時系列データのデータ値xの頻度h(x)を求める頻度算出部と、
各データ値xと各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)と、各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)と、前記頻度算出部で求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)と、の積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出する積和算出部と、
前記積和算出部で算出された積和SP(j)を用い、複数種類の符号表T(j)及び基準符号表T(J)から、前記離散時間区間における時系列データを符号化するための符号表を選択する符号表選択部と、
を有する符号化装置。
【請求項３】
請求項１の符号表選択方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時系列データを符号化する技術に関し、特に、時系列データを符号化するための符号表を選択する技術に関する。
【背景技術】
【０００２】
時系列データを効率よく符号化するための技術にエントロピー符号化がある。エントロピー符号化とは、符号化対象である各シンボルの出現確率に応じてビット数の異なる符号を割り当てる方法であり、その具体例には、ハフマン符号（Huffman Coding）などがある（例えば、非特許文献１）。エントロピー符号化によって符号化を行う場合、各シンボルの出現確率に応じて各シンボルに割り当てる符号を求めることも可能である。しかし、計算量の観点から、事前に複数種類の符号表（例えば、ハフマン符号表）を用意しておき、それらから符号量を最小化する符号表を選択して符号化を行う方法が一般的である。
【０００３】
図１（Ａ）は、事前に用意しておいた複数の符号表を用いてエントロピー符号化を行う従来の符号化装置１０１０の機能構成を例示した図である。また、図１（Ｂ）は、符号表の一例を説明するための図である。
【０００４】
図１（Ａ）の例では、事前に複数（jmax）種類の符号表T(j)(j=1,...,jmax)を用意しておき、それらを記憶部１０１３に格納しておく。図１（Ｂ）に例示するように、この例の符号表T(j)は、シンボルであるデータ値xと各データ値xに割り当てられた符号x(x,j)と各符号x(x,j)のビット数b(x,j)とが対応付けられたテーブルである。図１（Ｂ）の例の場合、データ値xは時系列データの振幅値であり、L(L≧2)種類の整数値x=0,...,L-1をとる。
【０００５】
入力された時系列データDATA(n)の符号化は、フレームなどの予め定められた離散時間区間（n=0,...,N-1、Nは2以上の整数）ごとに行われる。まず、当該離散時間区間の時系列データDATA(n)（n=0,...,N-1）が符号量計算部１０１４に入力され、符号量計算部１０１４は、記憶部１０１３に格納された符号表T(j)ごとに、当該離散時間区間の時系列データDATA(n)を符号化するためのビット数（符号量）を算出する。具体的には、符号量計算部１０１４は、符号表T(j)から各時系列データDATA(n)（n=0,...,N-1）に対応するビット数b(x,j)をそれぞれ抽出し、E(j)=Σn=0N-1b(DATA(n),j)の演算によって符号量E(j)を算出する。この処理はすべての符号表T(j)について行われるため、必要となる符号表T(j)の検索回数は平均N・jmax・(L/2)となり、演算回数はN・jmax回となる。例えば、jmax=16,N=160,L=32であれば、必要となる符号表T(j)の検索回数は平均40960回となり、演算回数は2560回となる。
【０００６】
算出された各符号量E(j)は符号表選択部１０１５に入力される。符号表選択部１０１５は、入力された各符号量E(j)を比較し、符号量E(j)を最小化する符号表T(h)を選択し、その符号表T(h)を特定するためのパラメータhを出力する。出力されたパラメータhは、符号化部１０１７とパラメータ符号化部１０１６とに入力される。
【０００７】
符号化部１０１７は、入力されたパラメータhを用いて記憶部１０１３に格納された符号表T(h)を特定し、特定した符号表T(h)を用いて各時系列データDATA(n)（n=0,...,N-1）を符号化した符号Cd(n)を生成して出力する。また、パラメータ符号化部１０１６は、入力されたパラメータhを符号化した符号Ccを生成して出力する。
【０００８】
以上のように生成された符号Cd(n),Ccを受け取った復号装置は、符号Ccを復号してパラメータhを生成し、パラメータhによって特定される符号表T(h)を用いて符号Cd(n)を復号して時系列データDATA(n)を生成する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】David Salomon, "Data Compression : The Complete Reference", Springer, 1998年, ISBN0-387-98280-9, pp.68-72.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来の方法では、符号化に用いる符号表T(h)を選択するために、離散時間区間ごとに平均平均N・jmax・(L/2)回の探索処理とN・jmax回の演算とを行う必要があり、符号表を選択するための処理量が多いという問題点がある。
本発明は、複数種類の符号表から時系列データを符号化するための符号表を選択するための処理量を削減することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、予め定められた離散時間区間における時系列データのデータ値xの頻度h(x)を求め、各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)と、求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と各データ値xと各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)との積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出し、算出された積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間における時系列データを符号化するための符号表を選択する。
【発明の効果】
【００１２】
本発明では、複数種類の符号表T(j)から時系列データを符号化するための符号表を選択するための処理量を削減することができる。
【図面の簡単な説明】
【００１３】
【図１】（Ａ）は従来の符号化装置の機能構成を例示した図であり、（Ｂ）は符号表の一例を説明するための図である。
【図２】（Ａ）は、第１実施形態の符号化装置の機能構成を例示した図である。（Ｂ）は、符号表の一例を説明するための図であり、（Ｃ）は、データ値の頻度を例示した図である。
【図３】第１実施形態の復号装置の機能構成を例示した図。
【図４】（Ａ）は、第１実施形態の符号化方法を説明するためのフローチャートであり、（Ｂ）は、第１実施形態の復号方法を説明するためのフローチャートである。
【図５】図４（Ａ）のステップＳ２０の一例を説明するためのフローチャート。
【図６】（Ａ）は、第２実施形態の符号化装置の機能構成を例示した図である。また、（Ｂ）は、基準符号表T(J)の一例を説明するための図であり、（Ｃ）は、符号表T(j)の一例を説明するための図である。
【図７】第２実施形態の符号化方法を説明するためのフローチャート。
【図８】第３実施形態の符号化装置の機能構成を例示した図。
【図９】第３実施形態の復号装置の機能構成を例示した図。
【図１０】第３実施形態の符号化方法を説明するためのフローチャート。
【図１１】第３実施形態の符号化方法を説明するためのフローチャート。
【図１２】図１１のステップＳ４７０の具体例を説明するためのフローチャート。
【図１３】（Ａ）は、第３実施形態の復号方法を説明するためのフローチャートであり、（Ｂ）は、（Ａ）のステップＳ５３０の具体例を説明するためのフローチャートである。
【図１４】各被除数を法2sで割った商を示した表。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施形態を説明する。
〔原理〕
まず、本形態の原理を説明する。
本形態では、(A) 予め定められた離散時間区間〔0,...,N-1（N≧2）〕における時系列データDATA(n)(n=0,...,N-1)のデータ値xの頻度h(x)を求めるステップと、(B) 各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)〔j=1,...,jmax（jmax≧2）〕とが少なくとも対応付けられた複数種類の符号表T(j)と、ステップ(A)で求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出するステップと、(C) ステップ(B)で算出された積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間（n=0,...,N-1）における時系列データDATA(n)を符号化するための符号表T(h)を選択するステップとを実行する。これらの処理をベクトル表現すると以下のようになる。まず、ステップ(A)では、予め定められた離散時間区間〔0,...,N-1（N≧2）〕における時系列データDATA(n)(n=0,...,N-1)のデータ値xの頻度h(x)を求める。次のステップ(B)では、各データ値x=x0,x1,...,xL-1〔L（L≧2）は予め設定されたデータ値xの全種類数〕と各データ値xにそれぞれ対応する各符号c(x,j)〔j=1,...,jmax（jmax≧2）〕とが少なくとも対応付けられた複数種類の符号表T(j)と、ステップ(A)で求められた各頻度h(x)とを用い、少なくとも一部のデータ値x=x0,x1,...,xW-1（WはW≦Lを満たす整数）の頻度h(x)を要素とするヒストグラムH=(h(x0), h(x1),..., h(xW-1))と、当該データ値xに対応する符号c(x,j)のビット数b(x,j)を要素とするヒストグラムB=(b(x0,j),b(x1,j),...,b(xW-1,j))との内積H・BT（BTはBの転置を示す）を各符号表T(j)についてそれぞれ算出し、各積和SP(j)=H・BTを求める。そして、ステップ(C)では、ステップ(B)で算出された積和SP(j)=H・BTを用い、複数種類の符号表T(j)から、離散時間区間（n=0,...,N-1）における時系列データDATA(n)を符号化するための符号表T(h)を選択する。なお、時系列データDATA(n)が０以上の値しかとらないのであれば、時系列データDATA(n)がとり得る振幅値を各データ値xとすればよい。また、時系列データDATA(n)が正負の値をとり得るのであれば、DATA(n)がとり得る値を各データ値xとすればよい。また、時系列データDATA(n)に対応するインデックスを各データ値xとしてもよい。
【００１５】
上述のように算出される積和SP(j)は、符号表T(j)を用いて離散時間区間（n=0,...,N-1）における時系列データDATA(n)を符号化した場合の総符号量E(j)又はその推定値となる。本形態では、データ値xの頻度h(x)を求めてから積和SP(j)を求めるため、総符号量E(j)又はその推定値を効率よく求めることができる。以下にその理由を説明する。
【００１６】
まず、本形態では、符号表T(j)からのビット数b(x,j)の探索を、各離散時刻n=0,...,N-1の時系列データDATA(n)についてそれぞれ行う必要はなく、多くても頻度がh(x)≧1となるデータ値xについてそれぞれ行えばよい。よって、本形態では、離散時間区間（n=0,...,N-1）におけるビット数b(x,j)の平均探索回数をL・jmax・(L/2)以下とすることができる。これによる探索回数の削減効果は、時系列データDATA(n)がデータ値xに偏りが存在するデータである場合（音響信号やその予測残差など）や、データ値xの種類数Lが離散時間区間長Nよりも小さい場合に特に大きい。例えば、jmax=16,N=160,L=32であれば、本形態で必要な平均検索回数は8192回以下となり、従来の40960回よりも大幅に削減できる。
【００１７】
また、本形態のデータ値xの頻度h(x)を求めるための演算回数はN回となり、積和SP(j)を求めるために必要な加算や乗算の回数はそれぞれL・jmax回以下となる。例えば、jmax=16,N=160,L=32であれば、本形態で必要となる演算回数の合計は512+512+160=1184回以下となり、従来の2560回よりも大幅に削減できる。
【００１８】
また、L種類すべてのデータ値xについての積和SP(j)を求めるのではなく、その一部〔U（U<L）種類〕のデータ値xのみについての積和SP(j)を求めた場合、離散時間区間（n=0,...,N-1）ごとの平均探索回数はU・jmax・(U/2)以下となり、積和SP(j)を求めるために必要な加算や乗算の回数はそれぞれU・jmax回以下となる。例えば、jmax=16,N=160,L=32,U=16であれば、平均探索回数は2048回となり、演算回数の合計は256+256+160=672回以下となる。
【００１９】
また、積和SP(j)を求めるための一部〔U（U<L）種類〕のデータ値xの選択方法を工夫することで、符号表T(h)の選択精度をさほど落とすことなく、探索回数や演算回数を削減できる。例えば、頻度h(x)が大きい順に選択された一部のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)を各符号表T(j)についてそれぞれ算出し、それらを用いて符号表T(h)を選択する。また、例えば、各符号表T(j)からそれぞれビット数b(x,j)が小さい順に選択された一部の符号c(x,j)のビット数b(x,j)と当該符号c(x,j)に対応するデータ値xの頻度h(x)との積和SP(j)=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出し、それらを用いて符号表T(h)を選択する。このようにした場合、符号表T(h)の選択精度をさほど落とすことなく、探索回数や演算回数をさらに削減できる。
【００２０】
また、一部のデータ値xのみについての積和SPpre(j)を各符号表T(j)について求め、基準符号表T(J)に対する積和SPpre(j)との差が予め定められた閾値を超えるほど大きくなる積和SPpre(j)に対応する符号表T(j)を候補から除外し、候補として残った符号表についてのみ、より多くのデータ値xについての積和SPpre(j)を求めてもよい。すなわち、時系列データDATA(n)のデータ値xがL種類存在し、m2,m1がL≧m2＞m1を満たす1以上の整数であり、ステップ(B)が、(B-1) m1種類のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SPpre(j)=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出するステップと、(B-2) 基準符号表T(J)について算出された積和SPpre(J)と各符号表T(j)についてそれぞれ算出された積和SPpre(j)とを比較し、積和SPpre(J)よりも小さいか、又は、積和SPpre(J)との差が予め定められた閾値以下である積和SPpre(j)を選択するステップと、(B-3) ステップ(B-2)で選択された積和SPpre(j)に対応する符号表T(j)のみについて、m2種類のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)をそれぞれ算出するステップと、を含んでもよい。また、ステップ(B-1)の例は、頻度h(x)が大きい順に選択されたm1種類のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SPpre=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出するステップ、又は、各符号表T(j)からそれぞれビット数b(x,j)が小さい順に選択されたm1種類の符号c(x,j)のビット数b(x,j)と当該符号c(x,j)に対応するデータ値xの頻度h(x)との積和SPpre=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出するステップである。なお、基準符号表T(J)は、１つであってもよいし複数であってもよい。また、基準符号表T(J)は、各積和SPpre(j)の閾値判定に対して同一であってもよいし、異なっていてもよい。このようにした場合、符号表T(h)の選択精度を高く維持しつつ、探索回数や演算回数を削減できる。
【００２１】
また、データ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)ではなく、データ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)と、の積和SP(j)=Σxh(x)・Δb(x,j)を用いてもよい。すなわち、(A') 予め定められた離散時間区間における時系列データのデータ値xの頻度h(x)を求めるステップと、(B') 各データ値xと各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)と、各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)と、ステップ(A')で求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)と、の積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出するステップと、(C') ステップ(B')で算出された積和SP(j)を用い、複数種類の符号表T(j)及び基準符号表T(J)から、離散時間区間における時系列データを符号化するための符号表を選択するステップとを実行してもよい。この場合、積和SP(j)=Σxh(x)・Δb(x,j)のΔb(x,j)=0となる項については乗算や加算が不要となるため、演算量をさらに削減できる。なお、この場合も、一部〔U（U<L）種類〕のデータ値xのみについての積和SP(j)を求めてもよいし、一部のデータ値xのみについての積和SPpre(j)を各符号表T(j)について求め、基準符号表T(J)に対する積和SPpre(j)との差が予め定められた閾値を超えるほど大きくなる積和SPpre(j)に対応する符号表T(j)を候補から除外し、候補として残った符号表についてのみ、より多くのデータ値xについての積和SPpre(j)を求めてもよい。また、基準符号表T(J)は、１つであってもよいし複数であってもよい。また、基準符号表T(J)は、各積和SPpre(j)の閾値判定に対して同一であってもよいし、異なっていてもよい。
【００２２】
また、時系列データDATA(n)のデータ値xの頻度分布に偏りがあってその偏りに傾向がある場合、その傾向に沿った符号表T(j)とその傾向から外れた例外的な符号表T(EX)とを用意しておいてもよい。そして、時系列データDATA(n)のデータ値xの頻度分布が当該傾向に沿ったものである場合には上記の何れかの方法によって符号表T(h)を特定し、時系列データDATA(n)のデータ値xの頻度分布が当該傾向から外れたものであった場合には符号表T(EX)を符号表T(h)としてもよい。例えば、時系列データDATA(n)の性質によっては、データ値xの頻度分布がx=0のとき最も高くなり、xの絶対値が大きくなるにつれて小さくなるような傾向〔例えば、ラプラス分布（Laplace distribution）に近似する傾向〕がある。このような場合には、例えば、データ値xの絶対値が大きくなるにつれてビット数b(x,j)が大きくなる符号表〔例えば、α符号に近似する符号表〕を傾向に沿った各符号表T(j)とし、その傾向から外れた符号表を符号表T(EX)とする。そして、例えば、最大のデータ値xL-1の頻度h(xL-1)と予め定められた閾値とを比較し、頻度h(xL-1)が当該閾値以下の場合には、上記の何れかの方法によって各符号表T(j)から符号表T(h)を選択し、頻度h(xL-1)が当該閾値を超えた場合には例外処理として符号表T(EX)を符号表T(h)とする。
【００２３】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
図２（Ａ）は、第１実施形態の符号化装置１０の機能構成を例示した図である。また、図２（Ｂ）は、符号表の一例を説明するための図であり、図２（Ｃ）は、データ値の頻度を例示した図である。また、図３は、第１実施形態の復号装置２０の機能構成を例示した図である。なお、図２（Ａ）において図１（Ａ）と共通する部分については、図１（Ａ）と同じ符号を用いた。また、図４（Ａ）は、第１実施形態の符号化方法を説明するためのフローチャートであり、図４（Ｂ）は、第１実施形態の復号方法を説明するためのフローチャートである。図５は、図４（Ａ）のステップＳ２０の一例を説明するためのフローチャートである。
【００２４】
＜構成＞
図２（Ａ）に示すように、本形態の符号化装置１０は、制御部１０１１、一時メモリ１０１２、記憶部１０１３、パラメータ符号化部１０１６、符号化部１０１７、頻度算出部１２、積和算出部１３、及び、符号表選択部１４を有する。また、符号化装置１０は、例えば、ＣＰＵ(central processing unit)，ＲＡＭ(random-access memory)，ＲＯＭ(read-only memory)等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。すなわち、一時メモリ１０１２や記憶部１０１３は、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。また、制御部１０１１、パラメータ符号化部１０１６、符号化部１０１７、頻度算出部１２、積和算出部１３、及び、符号表選択部１４は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、符号化装置１０は、制御部１０１１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０１２に格納され、その他の演算処理の際に読み出されて利用される。
【００２５】
図３に示すように、本形態の復号装置２０は、制御部２１、一時メモリ２２、記憶部２３、パラメータ復号部２４、及び、復号部２５を有する。また、復号装置２０は、例えば、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。すなわち、一時メモリ２２及び記憶部２３は、例えば、ＲＡＭ、磁気記録装置、光磁気記録媒体やそれらの少なくとも一部の結合によって構成される記憶領域である。また、制御部２１、パラメータ復号部２４及び復号部２５は、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、復号装置２０は、制御部２１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ２２に格納され、その他の演算処理の際に読み出されて利用される。
【００２６】
＜事前設定＞
事前設定として、予め定められた範囲のL種類のデータ値x=x0,x1,...,xL-1と、各データ値xにそれぞれ対応する各符号c(x,j)と、各符号c(x,j)のビット数b(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)(j=1,...,jmax)が記憶部１０１３に格納される。なお、図２（Ｂ）の例のデータ値xは、0以上L-1以下の整数x=0,1,...,N-1である。また、各符号表T(j)の一例はハフマン符号表である。また、記憶部１０１３に格納されたのと同様な符号表T(j)が復号装置２０の記憶部２３にも格納される。
【００２７】
＜符号化処理＞
まず、予め定められた離散時間区間(n=0,...,N-1)における時系列データDATA(n)(n=0,...,N-1)が符号化装置１０（図２（Ａ））に入力される。なお、離散時間区間の例は、データ処理単位であるフレームやフレームをさらに複数に区分したサブフレームである。
【００２８】
入力された各時系列データDATA(n)は頻度算出部１２に入力され、頻度算出部１２は、離散時間区間(n=0,...,N-1)における時系列データDATA(n)の各データ値x=x0,x1,...,xL-1の頻度h(x)をそれぞれ求める（ステップＳ１０）。図２（Ｃ）の例では、各データ値x=0,1,2,3,4,...,L-1の各頻度h(0)=50,h(1)=25,h(2)=13,h(3)=6,h(4)=4,...,h(L-1)=1が求められる。
【００２９】
各頻度h(x)は、それぞれに対応するデータ値xを特定可能な状態で積和演算部１３に入力される。積和演算部１３は、入力された各頻度h(x)と、記憶部１０１３に格納された各符号表T(j)とを用い、少なくとも一部のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出する（ステップＳ２０）。
【００３０】
［ステップＳ２０の具体例］
以下に、ステップＳ２０の具体例を示す。
≪具体例１-1≫
積和演算部１３は、入力された各頻度h(x)に対応する各データ値x=x0,x1,...,xL-1に対応する各符号c(x,j)のビット数b(x,j)を記憶部１０１３に格納された符号表T(j)から抽出する。次に、積和演算部１３は、データ値x=x0,x1,...,xL-1の各頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和
SP(j)=h(x0)・b(x0,j)+h(x1)・b(x1,j)+…+h(xL-1)・b(xL-1,j) 
を、各符号表T(j)についてそれぞれ算出する。
【００３１】
≪具体例1-２≫
まず、積和演算部１３は、入力された各頻度h(x)を互いに比較し、頻度h(x)が大きい順にU（U<L）個のデータ値x=x0,x1,...,xU-1が選択される。次に、積和演算部１３は、選択した各データ値x=x0,x1,...,xU-1に対応する各符号c(x,j)のビット数b(x,j)を記憶部１０１３に格納された符号表T(j)から抽出する。次に、積和演算部１３は、選択されたデータ値x=x0,x1,...,xU-1の各頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和
SP(j)=h(x0)・b(x0,j)+h(x1)・b(x1,j)+…+h(xU-1)・b(xU-1,j) 
を、各符号表T(j)についてそれぞれ算出する。
【００３２】
≪具体例１-３≫
まず、積和演算部１３は、記憶部１０１３に格納された各符号表T(j)から、それぞれビット数b(x,j)が小さい順にU（U<L）個の符号c(x0,j),c(x1,j),...,c(xU-1,j)を選択する。次に、積和演算部１３は、入力された各頻度h(x)から、選択したU個の符号c(x,j)に対応するデータ値x=x0,x1,...,xU-1に対応する各頻度h(x0),h(x1),...,h(xU-1)を選択する。そして、積和演算部１３は、選択した各符号c(x0,j), c(x1,j),...,c(xU-1,j)のビット数b(x0,j),b(x1,j),...,b(xU-1,j)と各頻度h(x0),h(x1),...,h(xU-1)との積和
SP(j)=h(x0)・b(x0,j)+h(x1)・b(x1,j)+…+h(xU-1)・b(xU-1,j)
を、各符号表T(j)についてそれぞれ算出する。
【００３３】
≪具体例1-4≫
m2,m1がL≧m2＞m1を満たす1以上の整数であり、積和SP(j)がm2種類のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)であるとする。なお、以下で添え字として使用する「m1」や「m2」は、それぞれ「m2」や「m1」を意味する。
【００３４】
図５に示すように、まず、積和演算部１３は、m1種類のデータ値x=x0,x1,...,xm1-1の頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和
SPpre(j)=h(x0)・b(x0,j)+h(x1)・b(x1,j)+…+h(xU-1)・b(xm1-1,j)
を、各符号表T(j)についてそれぞれ算出する（ステップＳ２１）。なお、ステップＳ２１は、頻度h(x)が大きい順に選択されたm1種類のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和を、各符号表T(j)についてそれぞれ算出するステップであってもよいし、各符号表T(j)からそれぞれビット数b(x,j)が小さい順に選択されたm1種類の符号c(x,j)のビット数b(x,j)と当該符号c(x,j)に対応するデータ値xの頻度h(x)との積和SPpreを、各符号表T(j)についてそれぞれ算出するステップであってもよいし、その他の基準で選択されたm1種類のデータ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和を、各符号表T(j)についてそれぞれ算出するステップであってもよい。
【００３５】
次に、積和演算部１３は、符号表T(j)から選択された基準符号表T(J)について算出された積和SPpre(J)と各符号表T(j)についてそれぞれ算出された積和SPpre(j)とを比較し、積和SPpre(J)よりも小さいか、又は、積和SPpre(J)との差が予め定められた閾値以下である積和SPpre(j)を選択する（ステップＳ２２）。そして、積和演算部１３は、選択した積和SPpre(j)に対応する符号表T(j)のみについて、m2種類のデータ値x=x0,x1,...,xm2-1の頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和
SP(j)=h(x0)・b(x0,j)+h(x1)・b(x1,j)+…+h(xU-1)・b(xm2-1,j)
をそれぞれ算出する（ステップＳ２３）。
【００３６】
なお、これらの具体例における積和SP(j)は、前述のようにの頻度h(x)を要素とするベクトルと、対応するビット数b(x,j)を要素とするベクトルとの内積と等価である。よって、ベクトル間の内積を高速に演算できるアルゴリズムがあるのであれば、内積演算によって各積和SP(j)を求めてもよい（［ステップＳ２０の具体例］の説明終わり）。
算出された積和SP(j)は、符号表選択部１４に入力される。符号表選択部１４は、積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間(n=0,...,N-1)における時系列データDATA(n)を符号化するための符号表T(h)を選択する（ステップS３０）。
【００３７】
［ステップＳ３０の具体例］
以下に、ステップＳ３０の具体例を示す。
≪具体例2-１≫
各積和SP(j)を相互に比較し、最小の積和SP(j)に対応する符号表T(j)を、離散時間区間(n=0,...,N-1)における時系列データDATA(n)を符号化するための符号表T(h)として選択する。
【００３８】
≪具体例2-2≫
各符号表T(j)を相互に順次比較していき、大きさが小さいほうから所定番目以内であると最初に判定された積和SP(j)に対応する符号表T(j)を、離散時間区間(n=0,...,N-1)における時系列データDATA(n)を符号化するための符号表T(h)として選択する。
【００３９】
≪具体例2-3≫
データ値x=x0,x1,...,xL-1から選択されたデータ値X（例えば、X=xL-1）の頻度h(X)を予め定められた閾値と比較し、頻度h(X)が当該閾値以下の場合には具体例2-１や2-2などの原則的な方法で各符号表T(j)から符号表T(h)を選択し、頻度h(X)が当該閾値を越える場合には、例外的な方法として特定の符号表T(EX)を符号表T(h)として選択する。なお、データ値Xは、時系列データDATA(n)の特定に依存して選択される。例えば、データ値xの頻度分布h(x)がラプラス分布に近似する傾向がある場合、データ値xの絶対値が大きくなるにつれてビット数b(x,j)が大きくなるα符号に近似する符号表を各符号表T(j)とし、その傾向から外れた符号表を符号表T(EX)とする。そして、例えば、最大のデータ値xL-1の頻度h(xL-1)と予め定められた閾値とを比較し、頻度h(xL-1)が当該閾値以下の場合には、上記の何れかの方法によって各符号表T(j)から符号表T(h)を選択し、頻度h(xL-1)が当該閾値を超えた場合には例外処理として符号表T(EX)を符号表T(h)とする。
【００４０】
≪具体例2-4≫
データ値x=x0,x1,...,xL-1から選択されたデータ値Xの大きさに応じ、探索する符号表を変える。例えば、データ値x=x0,x1,...,xL-1から選択されたデータ値X（例えば、X=xL-1）の頻度h(X)を予め定められた閾値と比較し、頻度h(X)が当該閾値以下の場合には具体例2-１や2-2などの方法で各符号表T(j)から符号表T(h)を選択し、頻度h(X)が当該閾値を越える場合には、具体例2-１や2-2などの方法で特定の複数種類の符号表T(ex)から符号表T(h)として選択する（［ステップＳ３０の具体例］の説明終わり）。
【００４１】
符号表選択部１４で選択された符号表T(h)を特定するパラメータhが符号化部１０１７に入力される。符号化部１０１７には、さらに離散時間区間(n=0,...,N-1)における時系列データDATA(n)が入力される。そして、符号化部１０１７は、記憶部１０１３に格納された各符号表T(j)からパラメータhによって特定される符号表T(h)を選択し、選択した符号表T(h)を用い、各時系列データDATA(n)を符号化し、符号Cd(n)を生成する（ステップS４０）。すなわち、符号化部１０１７は、符号表T(h)を参照して時系列データDATA(n)に対応する符号c(x,j)をそれぞれ選択し、それを時系列データDATA(n)に対応する符号Cd(n)とする。
【００４２】
また、符号化選択部１４で選択されたた符号表T(h)を特定するパラメータhは、パラメータ符号化部１０１６にも入力される。パラメータ符号化部１０１６は、パラメータhを符号化したパラメータ符号Ccを生成する。このパラメータ符号Ccは離散時間区間(n=0,...,N-1)ごとに生成される（ステップＳ５０）。なお、パラメータ符号化部１０１６で行われる符号化方法の例は、ゴロムライス（Golomb Rice）符号化などである。
【００４３】
そして、符号化装置１０は、上記のように生成された各符号Cd(n)とパラメータ符号Ccを出力する（ステップＳ６０）。出力された各符号Cd(n)とパラメータ符号Ccは、ネットワークや可搬型記録媒体を用いて復号装置２０に伝送される。
【００４４】
＜復号処理＞
離散時間区間(n=0,...,N-1)における各符号Cd(n)とパラメータ符号Ccは復号装置２０に入力される。パラメータ符号Ccはパラメータ復号部２４に入力され、パラメータ復号部２４はパラメータ符号Ccを復号してパラメータhを生成する（ステップＳ１１０）。生成されたパラメータhは復号部２５に入力される。復号部２５は、記憶部２３に格納された各符号表T(j)から符号表T(h)を特定する（ステップＳ１２０）。復号部２５には、各符号Cd(n)も入力され、復号部２５は特定した符号表T(h)を用いて各符号Cd(n)を復号し、時系列データDATA(n)を生成して出力する（ステップＳ１３０）。
【００４５】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。
第１実施形態では、データ値xの頻度h(x)と当該データ値xに対応する符号c(x,j)のビット数b(x,j)との積和SP(j)=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出し、算出された積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間(0,…,N-1)における時系列データDATA(n)を符号化するための符号表T(h)を選択することとした。しかし、第２実施形態では、データ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)と、の積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出し、算出された積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間(0,…,N-1)における時系列データDATA(n)を符号化するための符号表T(h)を選択する。以下では、第１実施形態との相違点を中心に説明し、第１実施形態と共通する事項については説明を省略する。
【００４６】
図６（Ａ）は、第２実施形態の符号化装置１１０の機能構成を例示した図である。また、図６（Ｂ）は、基準符号表T(J)の一例を説明するための図であり、図６（Ｃ）は、符号表T(j)の一例を説明するための図である。なお、図６（Ａ）において図１（Ａ）や図２（Ａ）と共通する部分については、それらと同じ符号を用いた。また、図７は、第２実施形態の符号化方法を説明するためのフローチャートである。なお、図７において図４（Ａ）と共通するステップについては、それと同じ符号を用いた。
【００４７】
＜構成＞
図６（Ａ）に示すように、本形態の符号化装置１１０は、制御部１０１１、一時メモリ１０１２、記憶部１０１３、パラメータ符号化部１０１６、符号化部１０１７、頻度算出部１２、積和算出部１１３、及び、符号表選択部１４を有する。また、符号化装置１１０は、例えば、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。例えば、積和算出部１１３は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、符号化装置１１０は、制御部１０１１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０１２に格納され、その他の演算処理の際に読み出されて利用される。
復号装置の構成は第１実施形態と同じである。ここでは説明を省略する。
【００４８】
＜事前設定＞
事前設定として、予め定められた範囲のL種類のデータ値x=x0,x1,...,xL-1と、各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)と、各データ値x=x0,x1,...,xL-1と、各データ値xにそれぞれ対応する各符号c(x,j)と、各符号c(x,j)のビット数b(x,j)と基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)が少なくとも対応付けられた複数種類の符号表T(j) (j=1,...,jmax)が記憶部１０１３に格納される。なお、図６（Ｂ）（Ｃ）の例のデータ値xは、0以上L-1以下の整数x=0,1,...,N-1である。また、基準符号表T(J)や各符号表T(j)やの一例はハフマン符号表である。
【００４９】
＜符号化処理＞
まず、第１実施形態で説明したステップＳ１０が実行される。ステップＳ１０で算出された各頻度h(x)は、それぞれに対応するデータ値xを特定可能な状態で積和演算部１１３に入力される。積和演算部１１３は、入力された各頻度h(x)と、記憶部１０１３に格納された各符号表T(j)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)と、の積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出する（ステップＳ３２０）。なお、ステップＳ３２０の具体例は、第１実施形態で説明したステップＳ２０の具体例のビット数b(x,j)を差Δb(x,j)に置換したものとなる。また、T(j)＝T(J)の場合には、計算をしなくても積和SP(J)=0とすればよい。そして、j=1からjmaxまでのjmax個の積和SP(j)の中で積和SP(j)を最小とするようなjを選択する。もし、積和SP(J)を除くすべての積和SP(j)が正であればJを選択する。ここで、Ｊがj=1からjmaxに含まれないのであれば、jmax回の積和SP(j)の計算で（jmax+1）個の中から最も望ましい符号表を選択することになる。すなわち、この場合には選択すべき符号表の個数より１回少ない関和の回数で符号表を選択できる。
その後、第１実施形態で説明したステップＳ３０からＳ６０の処理が実行される。
【００５０】
＜復号処理＞
第１実施形態と同じである。
〔第３実施形態〕
次に、本発明の第３実施形態を説明する。
本形態は第１実施形態の応用例である。本形態では、dを1以上の整数とし、パラメータs(0)をd以上の整数とし、パラメータs(d)=s(0)-dとし、yを整数とした場合における、0以上の整数からなる時系列データe(n)（「第２時系列データ」に相当）を2s(0)+yで割った商、及び、当該第２時系列データを2s(d)+yで割った商を時系列データのデータ値xとし、パラメータs(d)及びs(0)に対してそれぞれ第１実施形態を適用する。そして、パラメータs(d)及びs(0)についてそれぞれ選択された符号表を用いて符号化した場合の符号量を比較し、パラメータs(d)及びs(0)の一方を選択する。以下では、第１実施形態との相違点を中心に説明する。
【００５１】
図８は、第３実施形態の符号化装置２１０の機能構成を例示した図である。また、図９は、第３実施形態の復号装置２２０の機能構成を例示した図である。なお、図８において上述の実施形態と共通する部分については、それらと同じ符号を用いた。また、図１０及び図１１は、第３実施形態の符号化方法を説明するためのフローチャートである。また、図１２は、図１１のステップＳ４７０の具体例を説明するためのフローチャートである。また、図１３（Ａ）は、第３実施形態の復号方法を説明するためのフローチャートであり、図１３（Ｂ）は、図１３（Ａ）のステップＳ５３０の具体例を説明するためのフローチャートである。また、図１４は、整数e(n)を法2sで割った商を示した表である。
【００５２】
＜構成＞
図８に示すように、本形態の符号化装置２１０は、制御部１０１１、一時メモリ１０１２、記憶部１０１３、符号化部１０１７、頻度算出部１２、積和算出部１３、符号表選択部１４、パラメータ算出部２１１，２１２、選択部２１３，２１７、分離演算部２１４、頻度併合部２１５、パラメータ符号化部２１６、比較部２１８、及び合成部２１９を有する。また、符号化装置２１０は、例えば、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。例えば、パラメータ算出部２１１，２１２、選択部２１３，２１７、分離演算部２１４、頻度併合部２１５、パラメータ符号化部２１６、比較部２１８、及び合成部２１９は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、符号化装置２１０は、制御部１０１１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ１０１２に格納され、その他の演算処理の際に読み出されて利用される。
【００５３】
図９に示すように、本形態の復号装置２２０は、制御部２１、一時メモリ２２、記憶部２３、復号部２５、分離部２２１、合成演算部２２２、及びパラメータ復号部２２４を有する。また、復号装置２２０は、例えば、ＣＰＵ，ＲＡＭ，ＲＯＭ等を有する公知のコンピュータに所定のプログラムが読み込まれ、ＣＰＵがこれを実行することによって構成される。例えば、分離部２２１、合成演算部２２２、及びパラメータ復号部２２４は、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。なお、復号装置２２０は、制御部２１の制御のもと各処理を実行する。また、各演算処理で生成されたデータは、逐一、一時メモリ２２に格納され、その他の演算処理の際に読み出されて利用される。
【００５４】
＜事前設定＞
事前設定として、第１実施形態で説明したように、複数種類の符号表T(j)(j=1,...,jmax)が、符号化装置２１０の記憶部１０１３と復号装置２２０の記憶部２３とに格納される。
【００５５】
＜符号化処理＞
まず、離散時間区間(n=0,...,N-1)における時系列データe(n)が符号化装置２１０に入力される。なお、時系列データe(n)の例は、音響信号を線形予測分析や長期予測分析して得られた予測残差である。入力された時系列データe(n)はパラメータ算出部２１１に入力され、パラメータ算出部２１１は、離散時間区間(n=0,...,N-1)の時系列データe(n)を用い、当該離散時間区間(n=0,...,N-1)に対応するパラメータs(0)を算出する（ステップＳ４０１）。例えば、パラメータ算出部２１１は、d以上（d≧1）のライスパラメータをパラメータs(0)とする。具体的には、
log2{ln2・(2・D/N)}
をd以上（d≧1）の整数に整数化したものをパラメータs(0)とする。なお、D=|e(0)|+|e(1)|+…+|e(N-1)|であり、整数化の例は四捨五入、切り上げ、切捨てなどである。また、式(1)を整数化したしたものがd未満であった場合にはs(0)=dとしてもよい。また、dの一例は定数であり、その値の例は１である。
【００５６】
生成されたパラメータs(0)は、パラメータ算出部２１２に入力される。パラメータ算出部２１２は、
s(d)=s(0)-d 
の演算によってパラメータs(d)を算出する（ステップＳ４０２）。
【００５７】
次に、パラメータs(d)は選択部２１３に入力され、選択部２１３はパラメータs(d)を分離演算部２１４に入力させる。分離演算部２１４にはさらに離散時間区間(n=0,...,N-1)における時系列データe(n)が入力され、分離演算部２１４は、時系列データe(n)を2s(d)+yで割った商q(d,n)を算出する（ステップＳ４０３）。
離散時間区間(n=0,...,N-1)の各商q(d,n)は頻度算出部１２に入力される。頻度算出部１２は、商q(d,n)であるデータ値x=z・2d,z・2d +1,…,z・2d+2d-1の各頻度h(x)を、１種類以上の各整数z（z≧0）についてそれぞれ求める（ステップＳ４１１）。
【００５８】
ステップＳ４１１で得られた各頻度h(x)（x=z・2d,z・2d +1,…,z・2d+2d-1）は、頻度併合部２１５に入力される。頻度併合部２１５は、各整数zについてそれぞれh(z)=h(z・2d)+h(z・2d +1)+…+h(z・2d+2d-1)の演算を行ってデータ値x=zの各頻度h(z)を求める（ステップＳ４１２）。このステップＳ４１２で得られる頻度h(z)は、時系列データe(n)を2s(0)+yで割った商q(0,n)の各頻度となる（図１４参照）。例えば、d=1, s(0)=3, s(d)=2, z=0,y=0の場合を考えると、時系列データe(n)=0,...,7を23で割った各商q(d,n)（データ値z）はすべて0となるのに対し、時系列データe(n)=0,...,3を22で割った商q(0,n)（データ値x）は0となり、時系列データe(n)=4,...,7を22で割った商q(0,n)（データ値x）は1となる。これより、時系列データe(n)=0,...,7を23で割った各商q(d,n)（データ値z）が0になる頻度h(0)は、時系列データe(n)=0,...,3を22で割った商q(0,n)（データ値x）が0となる頻度h(0)と、時系列データe(n)=4,...,7を22で割った商q(0,n)（データ値x）が1となる頻度h(1)との合計によって算出できることがわかる。これにより、時系列データe(n)を2s(0)+yで割った商q(0,n)の各頻度を容易に算出することができる。
【００５９】
次に、選択部２１７の制御に基づき、頻度算出部１２で算出された各整数zに対応するデータ値x=z・2d,z・2d+1,…,z・2 d+2d-1の各頻度h(x)が積和算出部１３に入力される。積和算出部１３は、記憶部１０１３に格納された各符号表T(j)を参照し、各整数zに対応するデータ値x=z・2d,z・2 d+1,…,z・2 d+2d-1の各頻度h(x)と当該データ値xに対応する各符号c(x,j)の各ビット数b(x,j)との積和SP(d,j)=Σxh(x)・b(x,j)を、各符号表T(j)についてそれぞれ算出する（ステップＳ４２１）。
【００６０】
また、選択部２１７の制御に基づき、頻度併合部２１５で算出された各整数zに対応するデータ値x=zの各頻度h(z)が積和算出部１３に入力される。積和算出部１３は、記憶部１０１３に格納された各符号表T(j)を参照し、各整数zに対応するデータ値x=zの各頻度h(z)と当該データ値x=zに対応する各符号c(z,j)の各ビット数b(z,j)との積和SP(0,j)=Σzh(z)・b(z,j)を、各符号表T(j)についてそれぞれ算出する（ステップＳ４２２）。
【００６１】
ステップＳ４２１で生成された積和SP(d,j)は符号表選択部１４に入力される。符号表選択部１４は、積和SP(d,j)を用い、複数種類の符号表T(j)から、時系列データe(n)を2s(d)+yで割った商q(d,n)を符号化するための符号表T(h(d))を選択する（ステップＳ４３１）。また、ステップＳ４２２で生成された積和SP(0,j)も符号表選択部１４に入力される。符号表選択部１４は、積和SP(0,j)を用い、複数種類の符号表T(j)から、時系列データe(n)を2s(0)+yで割った商q(d,0)を符号化するための符号表T(h(0))を選択する （ステップＳ４３２）。なお、積和を用いて商（時系列データ）符号化するための符号表を選択する具体的な方法は第１実施形態で説明した通りである。
【００６２】
次に、少なくとも、符号表選択部１４で選択された符号表T(h(d))を特定するためのパラメータh(d)と、符号表T(h(0))を特定するためのパラメータh(0)とが、それぞれ、比較部２１８に入力される。比較部２１８は、パラメータs(d)を分離パラメータsとし、かつ、ステップＳ４３１で選択された符号表T(h(d))を用いて時系列データe(n)を符号化した場合の総符号量E(d)（又はその推定値）と、パラメータs(0)を分離パラメータsとし、かつ、ステップＳ４３２で選択された符号表T(h(0))を用いて時系列データe(n)を符号化した場合の総符号量E(0)（又はその推定値）とを比較する （ステップＳ４４１）。
【００６３】
[ステップＳ４４１の具体例]
以下に、ステップＳ４４１の具体例を示す。
《具体例3-1》
比較部２１８には、それぞれ、符号表選択部１４で選択された符号表T(h(d))を特定するためのパラメータh(d)とそれに対応する積和SP(d,h(d))と、符号表T(h(0))を特定するためのパラメータh(0)とそれに対応する積和SP(0,h(0))とが入力される。比較部２１８は、積和SP(d,h(d))を総符号量E(d)の推定値とし、積和SP(0,h(0))を総符号量E(0)の推定値とし、これらを比較する。
【００６４】
《具体例3-2》
比較部２１８には、それぞれ、符号表選択部１４で選択された符号表T(h(d))を特定するためのパラメータh(d)とそれに対応する積和SP(d,h(d))と、符号表T(h(0))を特定するためのパラメータh(0)とそれに対応する積和SP(0,h(0))とが入力される。さらに、選択部２１３の制御のもと、分離演算部２１４にパラメータs(0)とパラメータs(d)とが入力される。また、分離演算部２１４には離散時間区間（n=0,...,N-1）における時系列データe(n)が入力される。分離演算部２１４は、時系列データe(n)を2s(0)+yで割った場合の剰余を特定する情報sub(0,n)と、時系列データe(n)を2s(d)+yで割った場合の剰余を特定するための情報sub(d,n)とを求め、それら又はそれらのビット数を比較部２１８に送る。なお、時系列データe(n)を2s(0)+yや2s(d)+yで割った場合の剰余を特定する情報sub(0,n)やsub(d,n)の算出は、例えば、参考文献１「ISO/IEC 14496-3 AMENDMENT 2: Audio Lossless Cording (ALS), new audio profiles and BSAC extensions.」のP59に記載された方法によって行う。比較部２１８は、「積和SP(d,h(d))+sub(d,n)のビット数」を総符号量E(d)又はその推定値とし、「積和SP(0,h(0))+sub(0,n)のビット数」を総符号量E(0)又はその推定値とし、それらを比較する。
【００６５】
《具体例3-3》
具体例3-1又は具体例3-2に加え、パラメータのビット数も比較する。すなわち、選択部２１３の制御のもと、パラメータ符号化部２１６にはパラメータs(d),s(0)が入力される。また、パラメータ符号化部２１６にはさらにパラメータh(d),h(0)が入力される。パラメータ符号化部２１６は、パラメータs(d),h(d)に対応する符号又は当該符号のビット数と、パラメータs(0),h(0)に対応する符号又は当該符号のビット数とを比較部２１８に送る。比較部２１８は、「積和SP(d,h(d))+パラメータs(d),h(d)に対応する符号のビット数」を総符号量E(d)又はその推定値とし、「積和SP(0,h(0))+パラメータs(0),h(0)に対応する符号のビット数」を総符号量E(0)又はその推定値とし、それらを比較する。又は、比較部２１８は、「積和SP(d,h(d))+sub(d,n)のビット数+パラメータs(d),h(d)に対応する符号のビット数」を総符号量E(d)又はその推定値とし、「積和SP(0,h(0))+sub(0,n)のビット数+パラメータs(0),h(0)に対応する符号のビット数」を総符号量E(0)又はその推定値とし、それらを比較する。
【００６６】
《具体例3-4》
その他、上記の具体例具体例3-1、3-2、3-3において、積和SP(d,h(d))の代わりに、時系列データe(n)を2s(d)+yで割った場合の商q(d,n)を実際に符号表T(h(d))を用いて符号化した場合のビット数を用い、積和SP(0,h(0))の代わりに、時系列データe(n)を2s(0)+yで割った場合の商q(0,n)を実際に符号表T(h(0))を用いて符号化した場合のビット数を用いてもよい（[ステップＳ４４１の具体例]の説明終わり）。
【００６７】
ステップＳ４４１の比較で、総符号量E(d)（又はその推定値）＜総符号量E(0)（又はその推定値）であった場合（ステップＳ４４２）、比較部２１８は、パラメータs(d)とステップＳ４３１で選択された符号表T(h(d))とを、それぞれ時系列データe(n)を符号化するための分離パラメータs及び符号表T(h)として選択し、分離パラメータsを特定するための情報と符号表T(h)を特定するためのパラメータhとを出力する（ステップＳ４５１）。一方、ステップＳ４４１の比較で、総符号量E(d)（又はその推定値）≧総符号量E(0)（又はその推定値）であった場合（ステップＳ４４２）、比較部２１８は、パラメータs(0)とステップＳ４３２で選択された符号表T(h(0))とを、それぞれ時系列データe(n)を符号化するための分離パラメータs及び符号表T(h)として選択し、分離パラメータsを特定するための情報と符号表T(h)を特定するためのパラメータhとを出力する（ステップＳ４５２）。
【００６８】
比較部２１８から出力された分離パラメータsを特定するための情報は選択部２１３に入力される。選択部２１３は、分離パラメータsを特定するための情報を用いた制御により、分離パラメータsとして選択された分離パラメータs(0)又はs(d)を、分離演算部２１４及びパラメータ符号化部２１６に入力させる。また、比較部２１８から出力されたパラメータhは、符号化部１０１７及びパラメータ符号化部２１６に入力される。パラメータ符号化部２１６は、分離パラメータsとパラメータhとを符号化したパラメータ符号Ccを離散時間区間(n=0,...,N-1)ごとに生成する（ステップＳ４６０）。また、分離演算部２１４、合成部２１９及び符号化部１０１７は、分離パラメータs及びパラメータhで特定される符号表T(h)を用いて時系列データe(n)を符号化した符号Ce(n)を生成する（ステップＳ４７０）。ステップＳ４７０の符号化は、時系列データe(n)を選択された分離パラメータsに対する2s+yで割った商q(n)を、符号表符号表T(h)を用いて符号化した情報prefix(n)と、時系列データe(n)を分離パラメータsに対する2s+yで割った剰余を特定する情報sub(n)とを含む符号を生成する処理である。なお、「時系列データを分離パラメータsに対する2s+yで割った剰余を特定する情報sub(n)」はnull情報をも含む概念である。
【００６９】
[ステップＳ４７０の具体例]
以下に、ステップＳ４７０の具体例を示す。
図１２に示すように、まず、分離演算部２１４は、入力された分離パラメータsが０であるか否かを判定する（ステップＳ４７１）。ここで、s=0でなかった場合、分離演算部２１４は、入力された時系列データe(n)が０以上であるか否かを判定し（ステップＳ４７２ａ）、e(n)≧0であると判定された場合、
q(n)=floor(e(n)/2s−1) (for e(n)≧０)
に従って整数の商q(n)を生成し（ステップＳ４７３ａ）、
sub(n)=e(n)−2s−1・q(n)+2s−1 (for e(n)≧０)
に従って剰余を特定するための情報sub(n)を生成して出力する（ステップＳ４７４ａ）。
【００７０】
一方、ステップＳ４７２ａでe(n)≧0でないと判定された場合、分離演算部２１４は
sub(n)=floor{(−e(n)−1)/2s−1} (for e(n)＜０)
に従って整数の商q(n)を生成し（ステップＳ４７３ｂ）、
sub(n)=(−e(n)−1)−2s−1・q(n) (for e(n)＜０)
に従って剰余を特定するための情報sub(n)を生成して出力する（ステップＳ４７４ｂ）。
【００７１】
一方、ステップＳ４７１でs=0であると判定された場合、分離演算部２１４は、入力された時系列データe(n)が０以上であるか否かを判定し（ステップＳ４７２ｂ）、e(n)≧0であると判定された場合、
q(n)=2・e(n) (for e(n)≧０)
に従って剰余を特定するための情報sub(n)を生成し（ステップＳ４７３ｃ）、sub(n)をnullとして出力する（ステップＳ４７４ｃ）。
【００７２】
一方、ステップＳ４７２ｂでe(n)≧0でないと判定された場合、分離演算部２１４は、
q(n)=−2・e(n)−1 (for e(n)＜０)
に従って整数の商q(n)を生成し（ステップＳ４７３ｄ）、sub(n)をnullとして出力する（ステップＳ４７４ｃ）。
【００７３】
次に、分離演算部２１４から出力された商q(n)と比較部２１８から出力されたパラメータhとが符号化部１０１７に入力される。符号化部１０１７は、記憶部１０１３に格納された符号表T(j)からパラメータhに対応する符号表T(h)を特定し、符号表T(h)を用いて商q(n)を符号化し、商q(n)に対応する情報prefix(n)を生成する（ステップＳ４７５）。次に、分離演算部２１４から出力された情報sub(n)と符号化部１０１７から出力された情報prefix(n)とが合成部２１９に入力される。合成部２１９は、情報prefix(n)と情報sub(n)とを合成して符号Ce(n)を生成する（ステップＳ４７６／[ステップＳ４７０の具体例]の説明終わり）。
【００７４】
＜復号処理＞
離散時間区間(n=0,...,N-1)における各符号Ce(n)とパラメータ符号Ccは復号装置２２０に入力される。パラメータ符号Ccはパラメータ復号部２２４に入力される。パラメータ復号部２２４は、パラメータ符号Ccを復号して分離パラメータsとパラメータhとを生成する（ステップＳ５１０）。生成された分離パラメータsは合成演算部２２２に入力され、パラメータhは復号部２５に入力される。
【００７５】
復号部２５は、パラメータhを用い、記憶部２３に格納された各符号表T(j)から符号表T(h)を特定する（ステップＳ５２０）。また、分離部２２１、合成演算部２２２及び復号部２５は、分離パラメータs及び符号表T（h）を用いて各符号Ce(n)を復号し、時系列データe(n)を生成して出力する（ステップＳ５３０）。
【００７６】
[ステップＳ５３０の具体例]
まず、符号Ceが分離部２２１に入力される。分離部２２１は、入力された符号Ceを分離し、情報prefix(n)と、情報sub(n)とを生成する（ステップＳ５３１）。
分離部２２１から出力された情報prefix(n)は、復号部２５に入力される。復号部２５は、符号表T(h)を用いて情報prefix(n)を復号し、商q(n)を生成する（ステップＳ５３２）。
【００７７】
また、合成演算部２２２は、入力された分離パラメータsが０であるか否かを判定する（ステップＳ５３３）。ここで、s=0でないと判定された場合、次に合成演算部２２２は、分離部２２１から出力された情報sub(n)が2ｓ−１以上であるか否かを判定する（ステップＳ５３４ａ）。この判定は時系列データe(n)が０以上であるか否かを判定することに相当する。ステップＳ５３４ａでsub(n)≧2ｓ−１と判定された場合、合成演算部２２２は、
e(n)=sub(n)+2s−1・q(n)−2s−1
によって時系列データe(n)を算出する（ステップＳ５３５ａ）。
【００７８】
一方、ステップＳ５３４ａでsub(n)＜2ｓ−１と判定された場合、合成演算部２２２は、
e(n)=−sub(n)−1−2s−1・q(n)
によって時系列データe(n)を算出する（ステップＳ５３５ｂ）。
一方、ステップＳ５３３でs=0と判定された場合、次に合成演算部２２２は、情報q(n)が偶数であるか否かを判定する（ステップＳ５３４ｂ）。この判定は時系列データe(n)が０以上であるか否かを判定することに相当する。ステップＳ５３４ｂでq(n)が偶数であると判定された場合、合成演算部２２２は、
e(n)=q(n)/2
によって時系列データe(n)を算出する（ステップＳ５３５ｃ）。
【００７９】
一方、ステップＳ５３４ｂでq(n)が奇数であると判定された場合、合成演算部２２２は、
e(n)=−(q(n)+1)/2
によって時系列データe(n)を算出する（ステップＳ５３５ｄ）。
以上のように生成された時系列データe(n)は、合成演算部２２２から出力される（［ステップＳ５３０の詳細の例示］の説明終わり）。
【００８０】
〔第３実施形態の変形例〕
次に、本発明の第３実施形態の変形例を説明する。
第３実施形態のステップＳ４３２では、符号表選択部１４が、積和SP(0,j)を用い、複数種類の符号表T(j)から、時系列データe(n)を2s(0)+yで割った商q(d,0)を符号化するための符号表T(h(0))を選択することとした。しかし、ステップＳ４３２において、符号表選択部１４が、ステップＳ４３１で選択された符号表T(h(d))との距離が予め定められた閾値以下の符号表T(j)から、時系列データe(n)を2s(0)で割った商を符号化するための符号表T(h(0))を選択することにしてもよい。最適な符号表T(h(d))と符号表T(h(0))とは近いものであることが多く、このように符号表T(j)を探索することで、精度をさほど落とすことなく、符号表T(j)の探索数を削減できる。また、符号表T(h(d))と符号表T(j)との距離を事前計算しておけば、符号表T(j)の探索時に符号表T(h(d))と符号表T(j)との距離を計算する必要もない。なお、符号表T(h(d))と符号表T(j)との距離は、例えば、符号表T(h(d))においてデータ値kに対応付けられる符号のビット数をbu(k)とし、符号表T(j) においてデータ値kに対応付けられる符号のビット数をbx(k)とし、fu(k)=0.5bu(k)とし、fx(k)=0.5bx(k)とした場合における、(bu(k)−bx(k))(fu(k)−fx(k))の各kについての総和に対して単調増加する値として定義できる。
【００８１】
〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記の各実施形態では、各符号のビット数を各符号表に格納しておくこととした。しかし、積和の演算のたびに各符号のビット数を計算してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００８２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００８６】
本発明の産業上の利用分野としては、例えば、音響信号の可逆圧縮符号化・復号化技術を例示できる。また、本発明は、音響信号以外にも、映像信号、生体信号、地震波信号などの可逆圧縮符号化・復号化技術にも応用可能である。
【符号の説明】
【００８７】
１０，２１０，１０１０  符号化装置
２０，２２０  復号装置
【図１】
2011217381.tif 000003
【図２】
2011217381.tif 000004
【図３】
2011217381.tif 000005
【図４】
2011217381.tif 000006
【図５】
2011217381.tif 000007
【図６】
2011217381.tif 000008
【図７】
2011217381.tif 000009
【図８】
2011217381.tif 000010
【図９】
2011217381.tif 000011
【図１０】
2011217381.tif 000012
【図１１】
2011217381.tif 000013
【図１２】
2011217381.tif 000014
【図１３】
2011217381.tif 000015
【図１４】
2011217381.tif 000016
【手続補正書】
【提出日】平成23年5月25日(2011.5.25)
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
本発明では、予め定められた離散時間区間における時系列データのデータ値xの頻度h(x)を求め、各データ値xと各データ値xにそれぞれ対応する各符号c(x,j)とが少なくとも対応付けられた複数種類の符号表T(j)と、求められた各頻度h(x)とを用い、少なくとも一部のデータ値xの頻度h(x)と、符号表T(j)で当該データ値xに対応付けられた符号c(x,j)のビット数b(x,j)と各データ値xと各データ値xにそれぞれ対応する各符号c(x,J)とが少なくとも対応付けられた基準符号表T(J)で当該データ値xに対応付けられた符号c(x,J)のビット数b(x,J)との差Δb(x,j)との積和SP(j)=Σxh(x)・Δb(x,j)を、各符号表T(j)についてそれぞれ算出し、算出された積和SP(j)を用い、複数種類の符号表T(j)から、離散時間区間における時系列データを符号化するための符号表を選択する。