(57)【要約】      （修正有）【課題】一般のデータの損失性圧縮のための信頼ある方法および装置を提供する。【解決手段】自己相関係数とボルツマン温度係数と変換され格納されたソースデータに関するバイアス制御パラメータとに対する所与のゼロでない値の組を用いて、自己相関係数を含む反応項を有するThouless-Anderson-Palmer 方程式を用いたデータストリングの損失性圧縮の方法および装置が開示される。また、その双方及び装置において用いられるパラメータの最適化方法が開示される。【選択図】図３
2006129407.tif 000002
【特許請求の範囲】
【請求項１】
第１のデータ変換手段を用いてＭビットのソースデータのストリングをイジング表示に変換するステップと、
前記変換されたソースデータのストリングを第１メモリに格納するステップと、
自己相関係数とボルツマン温度係数と変換され格納されたソースデータに関するバイアス制御パラメータとに対する所与のゼロでない値の組を用いて、自己相関係数を含む反応項を有するThouless-Anderson-Palmerの式を第１の演算手段を用いて解くステップと、
補助場変数に対する結果値を第２メモリに格納するステップと、
前記Thouless-Anderson-Palmerの式を解くステップを、前記補助場変数に対する前記値が収束するまで、前記第２メモリ内に格納された値を用いて繰り返す繰り返しステップと、
前記補助場変数に対する収束値を第３メモリ内に格納するステップと、
平均場変数に対するＮ個の値を、第２の演算手段を用いて前記第３メモリの中に格納された前記補助場変数に対する前記値から計算するステップと、
前記Ｎ個の値を第４メモリの中に格納するステップと、
第２のデータ変換手段によって前記第４メモリの中に格納された平均場変数に対するＮ個の値のブール変換から、Ｎビットの符号語のシーケンスを得て出力するステップと
を含み、前記Ｍ及びＮは正の数を表わしＭがＮよりも大きい、ソースデータの損失性圧縮方法。
【請求項２】
前記ボルツマン温度係数を第５メモリに格納するステップと、
前記繰り返しステップまでに、前記ボルツマン温度係数を最適化するボルツマン温度係数最適化ステップと
をさらに含み、
前記ボルツマン温度係数最適化ステップは、
前記第５メモリ内のボルツマン温度係数のデータを、前記イジング表現をアップスピンおよびダウンスピンとして有するイジング磁性体システムのオーダーパラメータの満たすべき鞍点方程式に代入して、該鞍点方程式を第３の演算手段により解いて、前記オーダーパラメータのデータを得て第６メモリに格納するステップと、
前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムの自由エネルギーを第４の演算手段により算出して第７メモリに格納するステップと、
前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムのエネルギーを第５の演算手段により算出して第８メモリに格納するステップと、
前記第５メモリ内の前記ボルツマン温度係数のデータと、前記第７メモリ内の前記自由エネルギーのデータと、前記第８メモリ内の前記エネルギーのデータとから、第６の演算手段により、前記イジング磁性体システムのエントロピーを算出して第９メモリに格納するステップと、
前記第９メモリ内の前記エントロピーのデータが略０となるまで、前記第３〜第６の演算手段が、前記第５メモリ内の前記ボルツマン温度係数のデータ値を変更して上記各ステップを繰り返すステップと
を含むものである、請求項１に記載のソースデータの損失性圧縮方法。
【請求項３】
前記オーダーパラメータは、Ｎ個の第１オーダーパラメータとＮ個の第２オーダーパラメータとの集合により算出されるものであり、
前記鞍点方程式を前記第３の演算手段により解くステップは、
前記第１オーダーパラメータと前記第２オーダーパラメータのデータとの所定の初期値データを第１０メモリに格納するステップと、
前記第１オーダーパラメータの全てについて、前記第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を前記第３の演算手段により算出し、該算出した値を前記第１０メモリ内の前記第１オーターパラメータの格納場所に格納する第１オーダーパラメータ算出ステップと、
前記第２オーダーパラメータの全てについて、前記第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を前記第３の演算手段により算出し、該算出した値を前記第１０メモリ内の前記第２オーターパラメータの格納場所に格納する第２オーダーパラメータ算出ステップと、
第１オーダーパラメータ算出ステップと前記第２オーダーパラメータ算出ステップとを前記第３の演算手段により交互に所定回数繰り返すステップと、
前記第１オーダーパラメータを前記第３の演算手段により規格化して、前記第６メモリの第１の所定の記憶域に格納するステップと、
前記第２オーダーパラメータを前記第３の演算手段により規格化して、前記第６メモリの第２の所定の記憶域に格納するステップと
を含むものである、請求項２に記載のソースデータの損失性圧縮方法。
【請求項４】
Ｍビットのソースデータのストリングをイジング表示に変換する第１のデータ変換手段と、
前記変換されたソースデータのストリングを格納する第１メモリと、
自己相関係数とボルツマン温度係数と前記変換され格納されたソースデータに関するバイアス制御パラメータとに対する所与のゼロでない値の組を用いて、自己相関係数を含む反応項を有するThouless-Anderson-Palmerの式を解く第１の演算手段と、
補助場変数に対する結果値を格納する第２メモリと、
前記第１の演算手段を用いてThouless-Anderson-Palmerの式を解くステップを、前記補助場変数に対する前記値が収束するまで、前記第２メモリ内に格納された値を用いて繰り返す制御手段と、
前記補助場変数に対する収束値を格納する第３メモリと、
平均場変数に対するＮ個の値を、前記第３メモリの中に格納された前記補助場変数に対する前記収束値から計算する第２の演算手段と、
前記Ｎ個の値を格納する第４メモリと、
前記第４メモリの中に格納された前記平均場変数に対する前記Ｍ個の値のブール変換から、Ｎビットの符号語のシーケンスを得て出力する第２のデータ変換手段と
を備え、前記Ｍ及びＮは正の数を表わしＭがＮよりも大きい、ソースデータの損失性圧縮装置。
【請求項５】
前記ボルツマン温度係数を格納する第５メモリと、前記ボルツマン温度係数を最適化するボルツマン温度係数最適化手段とをさらに備え、
該ボルツマン温度係数最適化手段は、
第５メモリ内のボルツマン温度係数のデータを、前記イジング表現をアップスピンおよびダウンスピンとして有するイジング磁性体システムのオーダーパラメータの満たすべき鞍点方程式に代入して、該鞍点方程式を解く第３の演算手段と、
前記オーダーパラメータのデータを格納する第６メモリと、
前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムの自由エネルギーを算出する第４の演算手段と、
前記自由エネルギーのデータを格納する第７メモリと、
前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムのエネルギーを算出する第５の演算手段と、
前記エネルギーのデータを格納する第８メモリと、
前記第５メモリ内の前記ボルツマン温度係数のデータと、前記第７メモリ内の前記自由エネルギーのデータと、前記第８メモリ内の前記エネルギーのデータとから、前記イジング磁性体システムのエントロピーを算出する第６の演算手段と、
前記エントロピーのデータを格納する第９メモリと、
前記第３〜第６の演算手段に、前記第９メモリ内の前記エントロピーのデータが略０となるまで、前記第５メモリ内の前記ボルツマン温度係数のデータ値を変更して演算させる制御手段と
を含むものである、請求項４に記載のソースデータの損失性圧縮装置。
【請求項６】
前記オーダーパラメータは、Ｎ個の第１オーダーパラメータとＮ個の第２オーダーパラメータとの集合により算出されるものであり、
前記第１オーダーパラメータと前記第２オーダーパラメータのデータとの所定の初期値データを格納する第１０メモリと、
前記第１オーダーパラメータの全てについて、前記第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を算出し、該算出した値を前記第１０メモリ内の前記第１オーターパラメータの格納場所に格納する第１オーダーパラメータ算出手段と、
前記第２オーダーパラメータの全てについて、前記第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を算出し、該算出した値を前記第１０メモリ内の前記第２オーターパラメータの格納場所に格納する第２オーダーパラメータ算出手段と、
第１オーダーパラメータ算出手段と前記第２オーダーパラメータ算出手段を交互に所定回数繰り返すよう制御する制御手段と、
前記第１オーダーパラメータを規格化して、前記第６メモリの第１の所定の記憶域に格納し、前記第２オーダーパラメータを前記第３の演算手段により規格化して、前記第６メモリの第２の所定の記憶域に格納するする規格化演算手段と
を含み、前記第３の演算手段により前記鞍点方程式を解く請求項５に記載のソースデータの損失性圧縮装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にデータシーケンスのある程度劣化が許容される圧縮法に関し、より具体的には、冗長性を利用しない損失性圧縮を行うための方法および装置に関する。
【背景技術】
【０００２】
Lampel及びZivの圧縮並びにＬＺＷと呼ばれるその変形法（米国特許第４，５５８，３０２号）などの各種の高性能な方法は、データを損失なしで圧縮するために現在利用することができる。不可逆性のすなわち損失のある圧縮として知られているＪＰＥＧ規格においても、用いられる圧縮エンジンは損失のない形式である。他方では、損失性圧縮は高周波数成分の圧縮のような特定の用途では注意深く用いられているが、一般に高速でデータを圧縮する場合は、それには多くの問題があるため、十分に開発されていないと見なされている。
【０００３】
損失性圧縮は、我々の現代生活において極めて重要である。情報は適当な形式に符号化される。この符号化された情報はデコードされて、同様の情報のシーケンスを再生する。この種の忠実度の規範を有する圧縮技術に対する理論的な枠組みはレート歪み理論と呼ばれ、これはシャノンの情報理論の重要な部分を占める（非特許文献１）。
【非特許文献１】C.E. Shannon, Bell Syst. Tech. J. 27, 379 (1948).
【非特許文献２】T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, New York, 1991).
【非特許文献３】Y. Matsunaga and H. Yamamoto, IEEE Trans. Inf. Theory 49, 2225 (2003).
【非特許文献４】T. Murayama and M. Okada, in Advances in Neural Information Processing Systems 15, edited by S. Becker, S. Thrun, and K. Obermayer (MIT Press, Cambridge, MA, 2003).
【非特許文献５】Y. Kabashima and D. Saad, Europhys. Lett. 45, 97 (1999).
【非特許文献６】N. Sourlas, Nature .London. 339, 693 (1989).
【非特許文献７】Y. Kabashima and D. Saad, Europhys. Lett. 44, 668 (1998).
【非特許文献８】M. Mezard, G. Parisi, and M. Virasoro, Spin-Glass Theory and Beyond (World Scientific, Singapore, 1987).
【非特許文献９】M. Opper and D. Saad, Advanced Mean Field Methods: Theory and Practice (MIT Press, Cambridge, MA, 2001).
【非特許文献１０】T.J. Richardson and R.L. Urbanke, IEEE Trans. Inf. Theory 47, 599 (2001).
【発明の開示】
【課題を解決するための手段】
【０００４】
本発明は、ある態様として、下記のステップを含むソースデータの損失性圧縮を行う方法を提供する。すなわち、本発明は、第１のデータ変換手段を用いてＭビットのソースデータのストリングをイジング表示（Ising representation）に変換するステップと、この変換されたソースデータのストリングを第１メモリに格納するステップと、自己相関係数とボルツマン温度係数と変換され格納されたソースデータに関するバイアス制御パラメータとに対する所与のゼロでない値の組を用いて、自己相関係数を含む反応項を有するThouless-Anderson-Palmerの式を第１の演算手段を用いて解くステップと、補助場変数（auxliary field variable）に対する結果値を第２メモリに格納するステップと、Thouless-Anderson-Palmerの式を解くステップを、補助場変数に対する値が収束するまで、第２メモリ内に格納された値を用いて繰り返すステップと、補助場変数に対する収束値を第３メモリ内に格納するステップと、平均場変数に対するＮ個の値を、第２の演算手段を用いて第３メモリの中に格納された補助場変数に対する値から計算するステップと、このＮ個の値を第４メモリの中に格納するステップと、第２のデータ変換手段によって第４メモリの中に格納された平均場変数に対するＮ個の値のブール変換から、Ｎビットの符号語のシーケンスを得て出力するステップとを含む。この場合、Ｍ及びＮは正の数を表わし、ＭがＮよりも大きい。
【０００５】
上記態様においては、  前記ボルツマン温度係数を第５メモリに格納するステップと、
前記繰り返しステップまでに、前記ボルツマン温度係数を最適化するボルツマン温度係数最適化ステップとをさらに含むものとすると好適である。ここで、前記ボルツマン温度係数最適化ステップは、前記第５メモリ内のボルツマン温度係数のデータを、前記イジング表現をアップスピンおよびダウンスピンとして有するイジング磁性体システムのオーダーパラメータの満たすべき鞍点方程式に代入して、該鞍点方程式を第３の演算手段により解いて、前記オーダーパラメータのデータを得て第６メモリに格納するステップと、前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムの自由エネルギーを第４の演算手段により算出して第７メモリに格納するステップと、前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムのエネルギーを第５の演算手段により算出して第８メモリに格納するステップと、前記第５メモリ内の前記ボルツマン温度係数のデータと、前記第７メモリ内の前記自由エネルギーのデータと、前記第８メモリ内の前記エネルギーのデータとから、第６の演算手段により、前記イジング磁性体システムのエントロピーを算出して第９メモリに格納するステップと、前記第９メモリ内の前記エントロピーのデータが略０となるまで、前記第３〜第６の演算手段が、前記第５メモリ内の前記ボルツマン温度係数のデータ値を変更して上記各ステップを繰り返すステップとを含むものとすることができる。
【０００６】
さらにこの場合には、前記オーダーパラメータは、Ｎ個の第１オーダーパラメータとＮ個の第２オーダーパラメータとの集合により算出されるものであり、前記鞍点方程式を前記第３の演算手段により解くステップは、前記第１オーダーパラメータと前記第２オーダーパラメータのデータとの所定の初期値データを第１０メモリに格納するステップと、前記第１オーダーパラメータの全てについて、前記第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を前記第３の演算手段により算出し、該算出した値を前記第１０メモリ内の前記第１オーターパラメータの格納場所に格納する第１オーダーパラメータ算出ステップと、前記第２オーダーパラメータの全てについて、前記第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を前記第３の演算手段により算出し、該算出した値を前記第１０メモリ内の前記第２オーターパラメータの格納場所に格納する第２オーダーパラメータ算出ステップと、第１オーダーパラメータ算出ステップと前記第２オーダーパラメータ算出ステップとを前記第３の演算手段により交互に所定回数繰り返すステップと、前記第１オーダーパラメータを前記第３の演算手段により規格化して、前記第６メモリの第１の所定の記憶域に格納するステップと、前記第２オーダーパラメータを前記第３の演算手段により規格化して、前記第６メモリの第２の所定の記憶域に格納するステップとを含むものとするとさらに好適である。
【０００７】
本発明は、他の態様として、下記を備えるソースデータの損失性圧縮を行う装置も提供する。すなわち、本発明は、第１のデータ変換手段を用いてＭビットのソースデータのストリングをイジング表示に変換する第１のデータ変換手段と、この変換されたソースデータのストリングを格納する第１メモリと、自己相関係数とボルツマン温度係数と変換され格納されたソースデータに関するバイアス制御パラメータとに対する所定のゼロでない値の組を用いて自己相関係数を含む反応項を有するThouless-Anderson-Palmerの式を解くための第１の演算手段と、補助場変数に対する結果値を格納する第２メモリと、第１の演算手段を用いてThouless-Anderson-Palmerの式を解くステップを補助場変数に対する値が収束するまで、第２メモリ内に格納された値を用いて繰り返す制御手段と、補助場変数に対する収束値を格納する第３メモリと、平均場変数に対するＮ個の値を、第３メモリの中に格納された補助場変数に対する収束値から計算する第２の演算手段と、このＮ個の値を格納する第４メモリと、第４メモリの中に格納された平均場変数に対するＮ個の値のブール変換から、Ｎビットの符号語のシーケンスを得て出力する第２のデータ変換手段とを備える。この場合、Ｍ及びＮは正の数を表わし、ＭがＮよりも大きい。
【０００８】
本発明のこの態様においては、前記ボルツマン温度係数を格納する第５メモリと、前記ボルツマン温度係数を最適化するボルツマン温度係数最適化手段とをさらに備えることが好適である。この場合、該ボルツマン温度係数最適化手段は、第５メモリ内のボルツマン温度係数のデータを、前記イジング表現をアップスピンおよびダウンスピンとして有するイジング磁性体システムのオーダーパラメータの満たすべき鞍点方程式に代入して、該鞍点方程式を解く第３の演算手段と、前記オーダーパラメータのデータを格納する第６メモリと、前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムの自由エネルギーを算出する第４の演算手段と、前記自由エネルギーのデータを格納する第７メモリと、前記第６メモリ内の前記オーダーパラメータのデータから、前記イジング磁性体システムのエネルギーを算出する第５の演算手段と、前記エネルギーのデータを格納する第８メモリと、前記第５メモリ内の前記ボルツマン温度係数のデータと、前記第７メモリ内の前記自由エネルギーのデータと、前記第８メモリ内の前記エネルギーのデータとから、前記イジング磁性体システムのエントロピーを算出する第６の演算手段と、前記エントロピーのデータを格納する第９メモリと、前記第３〜第６の演算手段に、前記第９メモリ内の前記エントロピーのデータが略０となるまで、前記第５メモリ内の前記ボルツマン温度係数のデータ値を変更して演算させる制御手段とを備えるものとすることができる。
【０００９】
本発明のこの態様においては、前記オーダーパラメータは、Ｎ個の第１オーダーパラメータとＮ個の第２オーダーパラメータとの集合により算出されるものであり、前記第１オーダーパラメータと前記第２オーダーパラメータのデータとの所定の初期値データを格納する第１０メモリと、前記第１オーダーパラメータの全てについて、前記第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を算出し、該算出した値を前記第１０メモリ内の前記第１オーターパラメータの格納場所に格納する第１オーダーパラメータ算出手段と、前記第２オーダーパラメータの全てについて、前記第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、前記鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を算出し、該算出した値を前記第１０メモリ内の前記第２オーターパラメータの格納場所に格納する第２オーダーパラメータ算出手段と、第１オーダーパラメータ算出手段と前記第２オーダーパラメータ算出手段を交互に所定回数繰り返すよう制御する制御手段と、前記第１オーダーパラメータを規格化して、前記第６メモリの第１の所定の記憶域に格納し、前記第２オーダーパラメータを前記第３の演算手段により規格化して、前記第６メモリの第２の所定の記憶域に格納するする規格化演算手段とを含み、前記第３の演算手段により前記鞍点方程式を解くものとすることがさらに好適である。
【００１０】
本発明の方法及び装置は、ＣＰＵ、Ｉ／Ｏインターフェース及びＲＡＭ又はハードディスクなどのメモリ装置を有するワークステーション又はパーソナルコンピュータを含む任意のコンピュータ上で、コンピュータにロードしコンピュータ上で実行できるソフトウェアによって実現できる。それらは、個人用データ端末（ＰＤＡ）及び携帯電話などの十分な計算能力を有する任意の装置又は機器上でも実現できる。また、第１〜第６の演算手段や、第１オーダーパラメータ算出手段などの機能的な演算手段は、ＣＰＵなどのプロセッサの機能を用いることにより実現されるが、プロセッサアーキテクチャ等には特に依存しない。この際、各演算手段は、適当なプロシージャや関数などを用いて適宜構成されるプログラム等のソフトウェアの援用を前提としてＣＰＵ内の制御装置などが動作して、汎用のＣＰＵなどのプロセッサの数値・論理演算ユニット（ＡＬＵ）等の演算機能を用いて実現される機能手段や、専用のＡＳＩＣなどにより実現されるプロセッサ（例えばＤＳＰなど）により実現されるハードワイアードの手段として、あるいは、これらの中間となるＰＬＤ（プログラマブルロジックデバイス）等により外部から信号処理機能を書き込んでハードウェアに特定の信号処理を行なわせることにより実現することもできる。また、第１〜第１０メモリ等の各メモリは、ＣＰＵに内蔵してまたはＣＰＵと共に用いられる任意の記憶手段、例えば、ＣＰＵ内のレジスタ、ＲＡＭ（ランダムアクセスメモリ）、キャッシュメモリ等の揮発性メモリや、ハードディスク等の不揮発性メモリを用いて実現され、メモリ空間の構成（例えば、実記憶域であるか、仮想記憶域であるか）には依存しない。
【００１１】
本発明の方法及び装置は、本発明による方法のステップを実行できるように具体的に設計された特別なハードウェア装置上で実現することもできる。そのようなハードウェアで実現することにより、通常高速な動作が提供されるため、高速なコーディングが必要とされる用途に対して望ましい。
【発明の効果】
【００１２】
本発明はより一般的で高速なデータストリングを圧縮する方法を提供するため、それはデータ通信の分野における広い産業上の用途に適用できる。本発明によるデータ圧縮は限られた記憶空間を節約し、より高速なデータ送信を提供する。
【発明を実施するための最良の形態】
【００１３】
発明者らは、レート歪み理論の概念を定義し、また主な結果（非特許文献１）の最も単純なバージョンをまず説明する。Jをアルファベット
【数１】
2006129407.tif 000003
を有する離散的なランダム変数とする。発明者らはシーケンスJ1, J2, ..., JMを発生するソースを有すると仮定する。ここで、各シンボルは分布から無作為に抽出される。このアルファベットは有限であると仮定する。本願の明細書では、説明の便宜上、シーケンス
【数２】
2006129407.tif 000004
を表示するためにベクトル表記法を使用する。ここで、エンコーダは符号語
【数３】
2006129407.tif 000005
によってソースのシーケンス
【数４】
2006129407.tif 000006
を記述する。デコーダは、推定値
【数５】
2006129407.tif 000007
によってJを表示する。Mはソースシーケンスの長さを示し、一方Nは符号語の長さを表示することに注意されたい。この場合、レートはR=N/Mによって定義される。圧縮が考慮される場合、関係式N<Mが常に保たれ、これによりR<1も成り立つことに注意されたい。
【００１４】
歪み関数は、ソースのアルファベット−再生アルファベットの対の組から負でない実数の組へマッピング
【数６】
2006129407.tif 000008
する。直感的には、歪み
【数７】
2006129407.tif 000009
は、シンボル
【数８】
2006129407.tif 000010
によってシンボルJを表示するコストの測度である。この定義は極めて一般的である。しかしながら、大抵の場合、再生アルファベット
【数９】
2006129407.tif 000011
はソースのアルファベット
【数１０】
2006129407.tif 000012
と同じである。以後、我々は
【数１１】
2006129407.tif 000013
と設定し、次の歪み測度を忠実度の規範として採用する。ハミング歪みは下記のように与えられる。
【数１２】
2006129407.tif 000014
これは、関係式
【数１３】
2006129407.tif 000015
が成り立つため、結果として考えられる誤差歪みを発生する。この式でEJ[]は期待値を示し、P[]はその引数の確率を表す。歪み測度は、これまではシンボルごとに定義されている。発明者らは、この定義をシーケンスにまで拡張する。シーケンス
【数１４】
2006129407.tif 000016
間の歪みは、
【数１５】
2006129407.tif 000017
によって定義される。このため、シーケンスに対する歪みは、シーケンスの成分のシンボル当たりの平均歪みである。符号に関する歪みは
【数１６】
2006129407.tif 000018
のように定義され、ここで期待値は
【数１７】
2006129407.tif 000019
に対する確率分布に関連する。レート歪み符号のシーケンス(f,g)が、極限N→∞において
【数１８】
2006129407.tif 000020
について存在するならば、レート歪みの対(R,D)を作ることができる。さらに、達成可能なレート歪みの対の組のクロージャは、ソースに対するレート歪み領域と呼ばれる。最後に、発明者らは境界を記述する関数を定義できる。すなわち、レート歪み関数R(D)はレートRの下限であるため、(R,D)は所定の歪みDに対するソースのレート歪み領域の中にある。
【００１５】
この明細書の中で行われた開示に関して、簡単にするために、自身をハミングの歪み測度を持つ２進のソースJに制限する。発明者らは２進のアルファベットは無作為に抽出されると仮定する、すなわち、ソースは冗長性のために圧縮の可能性を除外するように偏らされることはない。こうして、発明者らは、推定されたエラーの割合がD以下のソースを記述するために必要な記述レートR(D)を見出す。シャノンによるこの単純化された事例では、境界を下記のように記載できる、すなわち、ハミング歪みがある２進ソースに対するレート歪み関数は、以下のように与えられる。
【数１９】
2006129407.tif 000021
ここで、h2()は２進のエントロピー関数を示す。
【００１６】
次に、損失性圧縮に対して玩具モデル（toy model）を取り入れる。発明者らはソーラス形（Sourlas-type）デコーディングの逆問題を使用して、最適な符号化方式を実現する。その変形例は最近何人かの情報理論家（非特許文献３）によって研究されてきた。前の段落の中で説明されたように、２進のアルファベットは偏りのないソースから無作為に抽出され、またハミングの歪み測度が忠実度の規範として選択されると仮定する。理論的に言うと、パリシ(Parisi)のワンステップRSB方式は典型的な歪みをうまく捕捉して、R(D)に対して物理的な解釈（非特許文献４）を行うことができることが報告されている。この明細書では、発明者らはこの符号の最適なファミリーに対して実際の符号化技術を検討する。
【００１７】
最初に、２進アルファベット
【数２０】
2006129407.tif 000022
のブール表示を行う、すなわち、
【数２１】
2006129407.tif 000023
と設定する。発明者らはまた符号語を表すために
【数２２】
2006129407.tif 000024
と設定する。JをMビットのソースシーケンス、ξをNビットの符号語、また
【数２３】
2006129407.tif 000025
をMビットの再生シーケンスとする。ここデコード化問題を次のように表現することができる。歪みD及び寸法M×Nの無作為に組み立てられたブールマトリックスAを考えると、
【数２４】
2006129407.tif 000026
（２を法とする）を満足するNビットの符号語のシーケンスξが見出される。ここで、全てのMビットのソースシーケンスJに基づいて、忠実度の規範
【数２５】
2006129407.tif 000027
が成り立つ。発明者らが加算演算に対して２を法とする数の算法を適用したことに注意されたい。この枠組みでは、デコーディングは単に線形のマッピング
【数２６】
2006129407.tif 000028
であるが、符号化はNP-コンプリートの問題（NP-complete problem）のままである。
【００１８】
行に対してはKにより、また列に対してはCによりブールマトリックスAを特徴付ける（非特許文献５）。有限で通常は小さい数のK及びCは、特定の符号を定義する。K及びCの組合せを選択することによって、符号のレートを任意の値に設定できる。発明者らはまたK及びCを制御パラメータとして使用して、レートR=K/Cを定義する。Kの値が小さい場合、すなわち、関係式K<<Nが成り立つ場合、ブールマトリックスは極めて疎のマトリックスを結果として生じる。これとは対照的に、密集した構成の事例を考える場合、Kは極めて大きくなければならず、またO(N)の値を持つ必要がある。K<<Nの場合以外は、KはO(1)でないとも仮定できる。
【００１９】
この種の符号とイジングスピンシステム（Ising spin system）との間の類似性は、最初Sourlasによって指摘された（非特許文献６）。彼はエラー訂正符号との関連で、イジングスピンシステムハミルトニアン上への符号のマッピングを定式化した。本発明を円滑にするために、発明者らは、まず、問題を、Sourlasの方法にしたがい、有限の連結性(connectivity)のあるイジングモデルの問題へとマッピングする。発明者らはブール表示[0,1]ではなく、アルファベットJ及びXのイジング表示[1,-1]を用いる。すなわち、ソースJ及び符号語のシーケンスξの成分はイジング値で書き直され、再生シーケンスは、イジング表示において関連する２進符号語のシーケンスの成分の積を取ることによって生成される、つまり、
【数２７】
2006129407.tif 000029
である。ここで、ソースのインデックスμに関係する符号語のインデックスiの集合を、
【数２８】
2006129407.tif 000030
として
【数２９】
2006129407.tif 000031
により表す。これにより、選択された複数のiは、行ごとの複数の１に対応し、
【数３０】
2006129407.tif 000032
のイジング版が生成される。ブール表示の加算演算は、イジング表示の乗算に変換されることに注意されたい。以後、
【数３１】
2006129407.tif 000033
と設定するが、簡単にするために表記法は変更しない。さらに、統計力学の手法を使用するから、レートR=N/Mを有限としながら、ソース及び符号語のシーケンスの大きさ（M及びNそれぞれ）を無限とみなす。
【００２０】
システムの可能性を探るために、
【数３２】
2006129407.tif 000034
として、ハミルトニアン
【数３３】
2006129407.tif 000035
を考察する。ここで、ξiの最適値を捜すために動的変数Siを取り入れ、また
【数３４】
2006129407.tif 000036
はソースビットJμに隣り合うランダムハイパーグラフの局部的な連結性を示す。逆温度（inverse temperature）β（以後、「ボルツマン温度係数」と呼ぶ）を有する
【数３５】
2006129407.tif 000037
の形式におけるソースJを考えると、符号語Sの事後確率（posterior probability）を示すことが都合が良い。ここで、
【数３６】
2006129407.tif 000038
は分配関数である。
【００２１】
確率分布（またはオーダーパラメータ）π(x)（第１オーダーパラメータ）及び
【数３７】
2006129407.tif 000039
（第２オーダーパラメータ）に関して表されたソースビット当たりの自由エネルギー（free energy）に対する表示を得て、これにより、鞍点（saddle point）の関係の組を提供する。
【数３８】
2006129407.tif 000040
これらの詳細については、ボルツマン温度係数βの最適化とともに後述する。
【００２２】
自由エネルギーに関して得られた結果を用いることによって、さらに直接的な計算を容易に行い、再生エラーを記録する内部エネルギーを含む他の全ての観察可能な熱力学的な量を見つけ出すことができる。この式（３）及び（４）の組は、一般的なβ、K及びCについて数値的に解くことができる。スピングラスの解（spin glass solution）は、レプリカ対称及びワンステップRSB前提（one-step RSB ansatz）の両方について計算することができる。前者はR<1に対しては非物理的となる常磁性の解(fRS=-1)にまで減らすが、後者は凝固点βgにおいて連続形分布π(x)及び
【数３９】
2006129407.tif 000041
を生じる。これは負でないレプリカ対称のエントロピーを実行する式の根から得ることができる。ランダムエネルギーのモデルの極限K,C→∞及び単純な代数により、レートR=N/Mと形式R=1-h2(D)との間の関係が与えられる。これはシャノンの定理におけるレート歪み関数と一致する（非特許文献４）。
【００２３】
ここで、以前の考えのマルコフ過程の仮定を使用して動的モデルを構築するために、Thouless-Anderson-Palmerの方式を採用して、実際的な符号化に対する式の完結した組を得ることができることを示す。この時点で、ソースシーケンスJのある実現値に対する動的変数Sの依存性に対して平均場動作（mean field behavior）を仮定する、すなわち、この依存性は因数分解することができ、平均場の積で置き換えることができる。さらに、特定の符号語のビットSiに対するボルツマンウエイトは、ソースビットJμに関して因数分解できる（非特許文献７）。他方では、物理学者の観点からすると、従来のマルコフ過程の仮定を取り入れてスピングラス状態の中で解を見つけることは自然である。この項は、時刻tにおける変数に対する事前の知識が与えられたときの、ある時刻t+1における事前の知識と考えることができる。以後、パラメータt=1,2,...を導入して時間発展を示す。このシナリオでは、下記のコンシステンシー方程式（consistency equation）の組を導き出すことができる。
【数４０】
2006129407.tif 000042
この場合、aμiは規格化因子である。式（７）には、決定すべき２つのパラメータがある、すなわち、αは強磁性体のバイアスを示し、γはシーケンスに対する自己相関を表す。以後、αを「バイアス制御パラメータ」及びγを「自己相関係数」と呼ぶ。
【００２４】
ここデコード語のインデックスiにリンクされたソースインデックスの組を定義するような別の組
【数４１】
2006129407.tif 000043
を導入する。式（５）は、
【数４２】
2006129407.tif 000044
が事後分布に従う場合、新たにSiに対して加えられたパリティビットJμの平均的な影響を評価する。この事後分布は、残りのデータセット
【数４３】
2006129407.tif 000045
が決定する必要がある。この計算は、従来の枠組みのキャビティ法に対応し、Jμが発生した実効ボルツマンウエイト
【数４４】
2006129407.tif 000046
を示す。ここで、自己誘導の寄与は、環の多い相互作用（非特許文献８）に対してツリー記述（tree description）を仮定することによって除かれる。他方では、式（６）は、事後分布
【数４５】
2006129407.tif 000047
を決定するキャビティフィールド（cavity field）のスタックを示す。
【００２５】
この式では、近似された周辺事後確率は、下記のようになる。
【数４６】
2006129407.tif 000048
この式は、式（５）及び（６）によってセルフコンシステントに決定されたキャビティフィールドの全セットを考慮している。ここで、aiは前に述べた規格化因子である。
【００２６】
次に、上記の式の一層便利な形式を示す。条件付き確率
【数４７】
2006129407.tif 000049
は、下記の規格化された実効ボルツマンウエイトである。
【数４８】
2006129407.tif 000050
ここで、bμiは規格化定数である。この関係は、システムから接続体μを取り出し、他の全ての接続体に対して変数Sの依存性を考慮することによって得られる。
【００２７】
恒等式
【数４９】
2006129407.tif 000051
及び下記の関係
【数５０】
2006129407.tif 000052
を満足する新たに定義された変数
【数５１】
2006129407.tif 000053
に関する簡単な代数計算によって、下記の擬似事後表現（pseudoposterior expression）
【数５２】
2006129407.tif 000054
を有する下記の形式の中でコンシステンシー方程式（consistency equation）のセットが与えられる。
【数５３】
2006129407.tif 000055
【００２８】
式（１３）及び（１４）の組は、符号の生成に対して反復アルゴリズムを与える。
【数５４】
2006129407.tif 000056
及び
【数５５】
2006129407.tif 000057
は補助場（auxiliary field）の変数であり、それらを補助場変数と呼ぶことにする。発明者らの動的モデルでパラメータγ=0を選択すると、その結果、反応項のない純真なThouless-Anderson-Palmerの式（非特許文献９）を生ずる。このため、この場合、ダイナミックスは、メッセージの受け渡しのデコーディングの下で低密度のパリティチェック符号の能力を決定することに関連させてRichardson及びUrbankeが提案した「密度発展（density evolution）」の方法を用いて完全に捕捉できる（非特許文献１０）。ρ()が(1/β)tanh-1mμiの共通の密度を表し、
【数５６】
2006129407.tif 000058
が
【数５７】
2006129407.tif 000059
の密度を示すものとする。確率分布の組が鞍点の式（３）及び（４）を満たすことは容易に理解できる。情報理論的な密度発展技術と歪みのある統計システムに対するレプリカ理論との間の整合性が見出されることは極めて興味深い。このため、πとρ（又は
【数５８】
2006129407.tif 000060
と
【数５９】
2006129407.tif 000061
）との間の類似性は優れた符号化に対する重要な測度と考えることができ、図１に示すようなダイナミックスモデルに対する設計原理を与えるものとなる。図１では、K=2, L=3及びβg=2.35に対する確率分布のスナップショットが示される。上側のグラフは、式（３）及び（４）の安定な解がモンテカルロ法によって計算されることを示す。様々な初期条件で始まる確率分布π(x)及び
【数６０】
2006129407.tif 000062
を近似するために、105のバイナリモデル（bin model）を使用する。図１の下側のグラフでは、式（１３）及び（１４）の密度発展に対する固定点の条件が、同じバイナリモデルの中の確率分布に関して示される。関係式
【数６１】
2006129407.tif 000063
及び
【数６２】
2006129407.tif 000064
を使用する。ここで、変数はそれぞれ共通密度ρ及び
【数６３】
2006129407.tif 000065
から生成されると仮定する。
【００２９】
最後に、式（１５）は、イジング表示におけるBayesの最適な符号化
【数６４】
2006129407.tif 000066
を提供する。変数mi(t)は、平均場に属すると考えることができる。この変数を「平均場変数」と呼ぶ。この変数は-1と1との間の任意の値を取り、その符号を取ると、イジング表示における最適な符号化が得られる。
【００３０】
この圧縮モデルに対する実際的な符号化方式は、下記のようになる。ソースシーケンスJを考えると、最初にブール形アルファベットをイジング形アルファベットに変換する。次に、制御パラメータα、β及びγに対する固定値のあるセットに対して、式（１３）及び（１４）は、結果が特定の固定点に収束するまで繰り返し計算される。この収束は単一点である必要はないが、結果が十分に安定した符号語のシーケンスξを提供する場合、結果は収束する。最後に、式（１５）に基づいて、
【数６５】
2006129407.tif 000067
のブール変換から符号語のシーケンスξを計算する。デコーディング工程は単に線形のマッピングに過ぎないことに注意されたい。検査のための最も興味深い量は、明らかに所定の圧縮レートに対する最小限の典型的な歪みとなる。
【００３１】
実験結果は、レプリカ法を用いた符号構成に対する理論的な評価とともに図２に示されている。図２に示すように、数値計算による実験値は、最適なα=0及びβ=βgを有するアルゴリズムは、K=2及びL=3,4,...,12の符号の疎の構成に対する境界を達成できることを示した。発明者らはC=3に対してγ=0.01を、残りの値に対してはγ=0.1を選択する。実線はシャノンによる２進数列に対するレート歪み関数R(D)を示し、一方点線は汎用の無損失コーディング技術によって容易に実現できる。（○）各評価に対して１０回の試行を平均した、システムサイズがN=20,000の数値計算結果である。（□）レプリカ構造におけるモンテカルロのサンプリングに対して105のビンモデルによって得られた疎の構成に関する理論的な境界である。
【００３２】
発明者らは、ビット当たりのエントロピーが凝固点で消滅する、符号の生成に最適な逆温度βgを使用する。以下、この最適化について説明する。
【００３３】
逆温度（ボルツマン温度係数）βの最適化について、まず、解析的な表現を用いて整理し、その後、数値的な計算手法について説明する。
【００３４】
本願発明者は、最適なボルツマン温度係数βとして、本発明で説明したイジング表現に対応するアップスピンとダウンスピンとによる磁化を実現するようなイジング磁性体の仮想的な系（システム）を考慮し、そのイジング磁性体システムのエントロピーがゼロになるときのボルツマン温度係数βの値を用いる。このボルツマン温度係数βは、このイジング磁性体システムにおける温度の逆数を表現しており、その温度とは、エントロピーが最小になった値の温度、すなわち、磁化のスピンが凍結した状態（スピングラス）の温度に対応する統計物理的な意味を有している。
【００３５】
このイジング磁性体システムのエントロピーは、ボルツマン温度係数βと、βを変数として含む自由エネルギーｆ（β）と、エネルギーｅ（β）とにより解析的な表式に表現できる。
【００３６】
まず、自由エネルギーｆ（β）は、βの関数であると共に、確率分布（オーダーパラメータ）π（第１オーダーパラメータ）および
【数６６】
2006129407.tif 000068
（第２オーダーパラメータ）の汎関数である。この自由エネルギーとβとの積であるβｆ（β）は、
【数６７】
2006129407.tif 000069
となる。ただし、
【数６８】
2006129407.tif 000070
である。このβｆ（β）をβにより微分すれば、イジング磁性体システムのエネルギーが計算することができる。すなわち、エネルギーｅ（β）は、
【数６９】
2006129407.tif 000071
により求めることができる。
【００３７】
既に説明した式（３）および（４）（鞍点方程式）は、固定されたボルツマン温度係数βについて自由エネルギーｆ（β）の鞍点を与える連立積分汎関数方程式になっている。式（３）および（４）を連立させた解となる確率分布（オーダーパラメータ）がそのときのボルツマン温度係数βに対するオーダーパラメータπ（第１オーダーパラメータ）およびそれに共役な関数（第２オーダーパラメータ）
【数７０】
2006129407.tif 000072
である。
【００３８】
エントロピーｓ（β）は、ボルツマン温度係数βと、βを変数として含む自由エネルギーｆ（β）およびエネルギーｅ（β）とを用いて、ｓ（β）＝βｅ（β）−βｆ（β）との関係から計算することができる。
【００３９】
次に、数値的に計算を行なう場合について、特に、鞍点方程式の算出の方法について説明する。式（３）および（４）により示した鞍点方程式は、関数Ａ（）およびＢ（）を用いると、形式的には、
【数７１】
2006129407.tif 000073
という形をしている。この式を数値的に計算するために、以下の手順を実行することができる。
（１）まず、長さＮの配列π［１］、・・・、π［Ｎ］および
【数７２】
2006129407.tif 000074
を作成する。これは、プログラムにおいては、例えば配列を宣言してメモリ空間をこれらの配列に割り当てることに対応する。例えば、このオーダーパラメータπや
【数７３】
2006129407.tif 000075
のそれぞれは、所定の範囲の整数値とすることができる。
（２）次いでこれらの配列に適当な初期値を設定する。
【００４０】
（３）第２オーダーパラメータの配列
【数７４】
2006129407.tif 000076
のＮ個の要素のうちから、非復元抽出により無作為にＣ個の要素を読み出して、例えば、
【数７５】
2006129407.tif 000077
とする。こうして、第２オーダーパラメータの値のうちから無作為抽出した値を順にｘハットに割り当てる。
【００４１】
（４）そのｘハットを用いて、鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスであるｘから減算される関数（ここでは、Ａ（））の値を算出する。すなわち、
【数７６】
2006129407.tif 000078
を求める。
【００４２】
（５）これをＮ回行うことにより、同様に、π［］、…π［Ｎ］を求める。
以上の（３）から（５）をメモリを用いて演算手段により行うことにより、第１オーダーパラメータの全てについて、第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を演算手段により算出し、その算出した値をメモリ内の第１オーターパラメータの格納場所に格納することができる。
【００４３】
（６）さらに、第１オーダーパラメータの配列πのＮ個の要素のうちから、非復元抽出により無作為にＫ個の要素を読み出して、例えば、ｘ1＝π［２］、ｘ2＝π［１３］、…、ｘK＝π［４３］などとする。こうして、第１オーダーパラメータの値のうちから無作為抽出した値を順にｘに割り当てる。
【００４４】
（７）そして、そのｘを用いて、鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスであるｘハットから減算される関数（ここでは、Ｂ（））の値を算出する。すなわち、
【数７７】
2006129407.tif 000079
を求める。
【００４５】
（８）これをＮ回行うことにより、同様に、
【数７８】
2006129407.tif 000080
を求める。
【００４６】
以上の（６）から（８）をメモリを用いて演算手段により行うことにより、第２オーダーパラメータの全てについて、第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を演算手段により算出し、その算出した値をメモリ内の第２オーターパラメータの格納場所に格納することができる。
【００４７】
（９）さらに、（３）〜（５）と、（６）〜（７）とを演算手段により交互に所定回数繰り返す。これにより、オーダーパラメータが、イジング磁性体システムに対応するように初期値から系によって定まる値へと変化してゆく。なお、この値は、必ずしも完全に収束しなくても、振動等の挙動が見られなくなる程度に落ち着くことで後の計算が可能になるため、実用上は、繰り返し回数はある程度以上の回数行えばよい。そして、第１および第２オーダーパラメータを演算手段により規格化して、オーダーパラメータの絶対値の最大値が１となるようにスケールする。
以上のような手順を実行することにより、オーダーパラメータπおよび
【数７９】
2006129407.tif 000081
の数値データを得ることができ、ボルツマン温度係数βを最適化し、本発明の符号化をより効率よく行うことができる。
【００４８】
なお、−βｆ（β）の表式をすでに示したが、この表式の算出根拠は、統計力学の手法に基づいている。すなわち、コスト関数として
【数８０】
2006129407.tif 000082
を定義して、これをエネルギーとして有するイジング磁性体システムの自由エネルギーを算出するために、ＪおよびＬに関する平均値としての自由エネルギーｆ（β）を
【数８１】
2006129407.tif 000083
から算出することに基づいている。ただし、
【数８２】
2006129407.tif 000084
は分配関数である。
【００４９】
次に、図３〜図８を用いて上記に説明した符号化方法や装置の動作を説明し、さらに、図９〜図１４を用いて本発明の符号化方法や装置によってデータを符号化し、さらに複合化した場合のデータの変化と歪の例を説明する。
【００５０】
図３は、本発明の符号化方法の処理を示すフローチャートである。
本発明の符号化方法においては、まず、データ変換手段を用いてＭビットのソースデータのストリングをイジング表示に変換し、変換されたソースデータのストリングをメモリに格納する（ステップＳ１０２）。これにより、ソースデータが例えば２進数｛０，１｝のアルファベットにより表現されているときに、アップスピンである＋１とダウンスピンである−１をアルファベットとするように変換する。そして、自己相関係数とボルツマン温度係数と変換され格納されたソースデータに関するバイアス制御パラメータとに対する所与のゼロでない値の組を用いて、自己相関係数を含む反応項を有するThouless-Anderson-Palmerの式を演算手段を用いて解き、補助場変数に対する結果値をメモリに格納する（ステップＳ１０４）。そして、Thouless-Anderson-Palmerの式を解くステップを、補助場変数に対する値が収束するまで（ステップＳ１０６）、メモリ内に格納された値を用いて繰り返す。そして、補助場変数に対する収束値をメモリに格納する（ステップＳ１０８）。そして、メモリの中に格納された補助場変数に対する値から、演算手段により、平均場変数に対するＮ個の値を計算し、メモリに格納する（ステップＳ１１０）。  データ変換手段によってこのメモリの中に格納された平均場変数に対するＮ個の値のブール変換から、Ｎビットの符号語のシーケンスを得て出力する（ステップＳ１１２）。これは、平均場変数がイジング表現となっているため、例えば元の２進数｛０，１｝のアルファベットにより表現しなおすことである。なお、Ｍ及びＮは正の数を表わしＭがＮよりも大きい。
【００５１】
図４は、本発明の符号化装置の構成を示すブロック図である。
本符号化装置は、Ｍビットのソースデータのストリングを、最終的にＮビットの符号語に変換する。第１のデータ変換手段１２は、このＭビットのソースデータのストリングをイジング表示に変換する。第１メモリ１６は、この変換されたソースデータのストリングを格納する。第１の演算手段２２は、自己相関係数とボルツマン温度係数と変換され格納されたソースデータに関するバイアス制御パラメータとに対する所与のゼロでない値の組を用いて、自己相関係数を含む反応項を有するThouless-Anderson-Palmerの式を解く。第２メモリ２６は、補助場変数に対する結果値を格納する。制御手段３２は、第１の演算手段を用いてThouless-Anderson-Palmerの式を解くステップを、補助場変数に対する値が収束するまで、第２メモリ２６に格納された値を用いて繰り返す。第３メモリ３６は、補助場変数に対する収束値を格納する。第２の演算手段４２は、平均場変数に対するＮ個の値を、第３メモリ３６の中に格納された補助場変数に対する収束値から計算する。第４メモリ４６は、Ｎ個の値を格納する。第２のデータ変換手段５２は、第４メモリ４６の中に格納された平均場変数に対するＭ個の値のブール変換によって、Ｎビットの符号語のシーケンスを得て出力する。
【００５２】
図５は、ボルツマン温度係数βを最適化する処理を示すフローチャートである。このフローチャートは、図３におけるステップＳ１０６までのいずれかの段階に実行される処理を示している。
まず、メモリ内のボルツマン温度係数のデータを、イジング表現をアップスピンおよびダウンスピンとして有するイジング磁性体システムのオーダーパラメータの満たすべき鞍点方程式に代入して（ステップＳ２０２）、鞍点方程式を演算手段により解いて（ステップＳ２０４）、オーダーパラメータのデータを得てメモリに格納する（ステップＳ２０６）。そして、メモリ内のオーダーパラメータのデータから、イジング磁性体システムの自由エネルギーを演算手段により算出してメモリに格納する（ステップＳ２０８）。さらに、メモリ内のオーダーパラメータのデータから、イジング磁性体システムのエネルギーを演算手段により算出してメモリに格納する（ステップＳ２１０）加えて、メモリ内のボルツマン温度係数のデータと、メモリ内の自由エネルギーのデータと、メモリ内のエネルギーのデータとから、演算手段により、イジング磁性体システムのエントロピーを算出してメモリに格納する（ステップＳ２１２）。なお、ステップＳ２０８とＳ２１０は、逆の順序に行なうこともできる。ボルツマン温度係数の最適値は、エントロピーが０となる場合なので、計算されたエントロピーのデータが０となるまで（ステップＳ２１４）、メモリ内のボルツマン温度係数のデータ値を変更して（ステップＳ２１６）、ステップＳ２０２〜Ｓ２１２を繰り返す。
【００５３】
図６は、鞍点方程式を数値的に解くための処理を示すフローチャートである。これは、図５のステップＳ２０４を実施する場合の詳細な処理の一例である。ここで、オーダーパラメータは、Ｎ個の第１オーダーパラメータとＮ個の第２オーダーパラメータとの集合を用いて算出される。鞍点方程式を演算手段により解くステップ（ステップＳ２０４、図５）は、例えば、計算回数をカウントするカウンタを０にセットし（ステップＳ３０２）、第１オーダーパラメータと第２オーダーパラメータのデータとの所定の初期値データをメモリに格納する（ステップＳ３０４）。そして、回数カウンタを１だけインクリメントする（ステップＳ３０６）。さらに、Ｎ個ある第１オーダーパラメータの全てについて、第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を演算手段により算出し、算出した値をメモリ内の第１オーターパラメータの格納場所に格納する（ステップＳ３０８）。次いで、第２オーダーパラメータの全てについて、第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を演算手段により算出し、算出した値をメモリ内の第２オーターパラメータの格納場所に格納する（ステップＳ３１０）。回数カウンタが所定回数に達するまでは（ステップＳ３１２）、ステップＳ３０８とステップＳ３１０を所定回数繰り返す。所定回数繰り返すと、第１オーダーパラメータおよび第２オーダーパラメータを演算手段により規格化する（ステップＳ３１４）。
【００５４】
図７は、ボルツマン温度係数最適化手段２００の構成を示すブロック図である。
ボルツマン温度係数は、第５メモリ２０２に格納される。ボルツマン温度係数最適化手段２００において、第３の演算手段２０６は、第５メモリ内のボルツマン温度係数のデータを、イジング表現をアップスピンおよびダウンスピンとして有するイジング磁性体システムのオーダーパラメータの満たすべき鞍点方程式に代入して、鞍点方程式を解く。第６メモリ２１２は、オーダーパラメータのデータを格納する。第４の演算手段２１６は、第６メモリ２１２のオーダーパラメータのデータから、イジング磁性体システムの自由エネルギーを算出する。第７メモリ２２２は、自由エネルギーのデータを格納する。第５の演算手段２２６は、第６メモリ内のオーダーパラメータのデータから、イジング磁性体システムのエネルギーを算出する。第８メモリ２３２は、エネルギーのデータを格納する。第６の演算手段２３６は、第５メモリ２０２内のボルツマン温度係数のデータと、第７メモリ２２２の自由エネルギーのデータと、第８メモリ２３２内のエネルギーのデータとから、イジング磁性体システムのエントロピーを算出する。第９メモリ２４２は、エントロピーのデータを格納する。制御手段２４６は、前記第３〜第６の演算手段に、前記第９メモリ内の前記エントロピーのデータが略０となるまで、前記第５メモリ内の前記ボルツマン温度係数のデータ値を変更して演算させる。
【００５５】
図８は、本発明の鞍点方程式ソルバ３００の構成を示すブロック図である。ここで、オーダーパラメータは、Ｎ個の第１オーダーパラメータとＮ個の第２オーダーパラメータとの集合により算出される。
第１０メモリ３０２は、第１オーダーパラメータと第２オーダーパラメータのデータとの所定の初期値データを格納する。第１オーダーパラメータ算出手段３０６は、第１オーダーパラメータの全てについて、第２オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、鞍点方程式の第１式のデルタ関数において第１オーダーパラメータのインデックスの値から減算される関数値を算出し、算出した値を第１０メモリ３０２の第１オーターパラメータの格納場所３１２に格納する。第２オーダーパラメータ算出手段３１６は、第２オーダーパラメータの全てについて、第１オーダーパラメータのＮ個のデータから、非復元抽出により複数のデータを略無作為に読み出し、鞍点方程式の第２式のデルタ関数において第２オーダーパラメータのインデックスの値から減算される関数値を算出し、算出した値を第１０メモリ内の第２オーターパラメータの格納場所３２２に格納する。制御手段３２６は、第１オーダーパラメータ算出手段３０６と第２オーダーパラメータ算出手段３１６を交互に所定回数繰り返すよう制御する。規格化手段３３２は、第１オーダーパラメータを規格化して、第６メモリ２１２（図７）の第１の所定の記憶域に格納し、第２オーダーパラメータを第３の演算手段により規格化して、第６メモリ２１２の第２の所定の記憶域に格納する。
【００５６】
図９は、本発明の符号化方法及び装置を用いて実施したデータの圧縮（符号化）および復元（復号化、デコード）を行なうために用いた元の２値画像データによる画像である。この画像は、８１×８１個の画素からなる画像であり、Ｍ＝６５６１である。
【００５７】
そして、図１０は、圧縮した系列を２次元に表示した画像である。この画像は、５４×８１（Ｎ＝４３７４）の２値データの画素を含んでいる。この画像を得るためには、１次元系列のデータとして扱って圧縮及び複合を行なっている。圧縮率Ｒは２／３とし、計算に用いたパラメータは、Ｋ＝２、Ｃ＝３、β＝２．３５、γ＝０．１とした。図３に示した例と異なり、収束判定は行なわず、更新回数は１００回で打ち切っている。
【００５８】
図１１は、図１０に示した圧縮データから復元（デコード）した画像である。図９の画像と同様の画素数を有している。
【００５９】
そして、図１２は、図９の画像を与えるデータと図１１の画像を与えるデータとの差を画像として表現した差分系列の画像である。この画像は、この例における歪みを画像として表示したものである。この一連の圧縮（符号化）および復元（復号化、デコード）におけるハミング歪はＤ＝０．０７８３であった。このとき、図１２漢わかるように、歪の発生が、元の画像データとは全く無関係に、一様に生じている事がわかる。これは、本発明の符号化においては、データが有する冗長性を利用した圧縮や、人間の視覚特性を考慮した圧縮（例えば、ＪＰＥＧにおける離散コサイン変換等）を行なっていないためである。
【００６０】
図１３は、本発明を音声データ（時系列サンプリング波形）に用いた例におけるソースデータのグラフであり、図１４は、図１３に示したソースデータを圧縮および復元を行なった後のデータである。
【００６１】
図１３は、４４０Ｈｚと４４４Ｈｚの合成音のデータによってうなりを生じさせているデータであり、録音時間は０．５秒、各周波数の振動は振幅を１Ｖ（peak to peak）とする等しい振幅を有する。また、サンプリングの量子化ビットは振幅成分に４ビット、符号を１ビットを割り当てた５ビットとした。これにより、１秒当たりの標本化数は２０４８である。この場合、Ｍ＝３４８９となる。圧縮後は、Ｎ＝２３２６となり、Ｒ＝２／３である。ここでも、計算に用いたパラメータは、Ｋ＝２、Ｃ＝３、β＝２．３５、γ＝０．１とした。図１３に示したデータと図１４に示したデータから算出されるハミング歪はＤ＝０．０８１４であった。
【００６２】
情報科学における最近の研究は、シャノンの限界R(D)に取り組む符号を設計することは実際的な意味で極めて困難であることを明らかにしている。発明者らは特にO(N)に対するあまり複雑でない優れたコーディング法を持ち合わせてない。しかしながら、発明者らの符号の構成は丁度O(N)を取りつつ、性能は驚くほど良好である。発明者らは、物理学者の手法は、エラー訂正符号との関連で既に見てきたように、損失性圧縮方式において重要な役割を演ずることができると信じている。
【図面の簡単な説明】
【００６３】
【図１】図１は、確率分布のスナップショットを示す図である。上のグラフは方程式（３）および（４）の定常解がモンテカルロ法によって計算されたことを示す。図１の下のグラフは、式（１３）および（１４）の密度発展の固定点条件が、確率密度によって表現されていることを示す。
【図２】図２は、実験結果を、レプリカ法を用いた符号構成の理論的な評価と共に示す。
【図３】図３は、本発明の方法および装置のフローチャートを示す。
【図４】図４は、本発明の方法および装置の構成図を示す。
【図５】図５は、本発明においてボルツマン温度係数βを最適化する処理を示すフローチャートである。
【図６】図６は、本発明において鞍点方程式を数値的に解くための処理を示すフローチャートである。
【図７】図７は、本発明のボルツマン温度係数最適化手段の構成を示すブロック図である。
【図８】図８は、本発明の鞍点方程式ソルバの構成を示すブロック図である。
【図９】図９は、本発明の符号化方法及び装置を用いる際にソースデータとして用いる画像の例である。
【図１０】図１０は、図９の画像を本発明の符号化方法及び装置により圧縮した系列を２次元に表示した画像である。
【図１１】図１１は、図１０に示した圧縮データから復元した画像である。
【図１２】図１２は、図９の画像を与えるデータと図１１の画像を与えるデータとの差を画像として表現した差分系列のデータを画像として表わしたものである。
【図１３】図１３は、本発明の符号化方法及び装置を音声データ（時系列サンプリング波形）に用いた例におけるソースデータのグラフである。
【図１４】図１４は、図１３に示したソースデータを圧縮および復元を行なった後のデータのグラフである。
【図１】
2006129407.tif 000085
【図２】
2006129407.tif 000086
【図３】
2006129407.tif 000087
【図４】
2006129407.tif 000088
【図５】
2006129407.tif 000089
【図６】
2006129407.tif 000090
【図７】
2006129407.tif 000091
【図８】
2006129407.tif 000092
【図９】
2006129407.tif 000093
【図１０】
2006129407.tif 000094
【図１１】
2006129407.tif 000095
【図１２】
2006129407.tif 000096
【図１３】
2006129407.tif 000097
【図１４】
2006129407.tif 000098