(57)【特許請求の範囲】
【請求項１】
連続アルファベットを符号化する符号化装置であって、
予め、Ｎ×Ｌの疎行列Ａ、Ｎ×Ｋの疎行列Ｂ、Ｌ次元横ベクトルｃL、及び条件付確率密度関数ｗ(ｙ|ｘ)が格納された第１記憶手段と、
連続情報源からの出力をＮ次元横ベクトルで表現したｘNを、ｑを奇素数、Δをスカラー量子化の量子化幅である正の実数として、次式
【数１】
0005817645.tif 000070
によってスカラー量子化し、スカラー量子化された結果
【数２】
0005817645.tif 000071
に対して、ｙのスカラー量子化を
【数３】
0005817645.tif 000072
として、前記条件付確率密度関数ｗ(ｙ|ｘ)を次式
【数４】
0005817645.tif 000073
によってスカラー量子化したもの、前記疎行列Ａ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数５】
0005817645.tif 000074
によって最適化処理を行うことでベクトル量子化を行い、φN(ｘN)を出力するベクトル量子化手段と、
前記ベクトル量子化手段の出力φN(ｘN)に、前記疎行列Ｂを掛けることでＫ次元横ベクトルで表現した符号語ｍKを求める符号化手段と、
を具備したことを特徴とする符号化装置。
【請求項２】
前記ベクトル量子化手段は、
前記連続情報源からの出力ｘの確率密度関数をｐ、該確率密度関数ｐを次式
【数６】
0005817645.tif 000075
によってスカラー量子化したものをＰとし、前記条件付確率密度関数ｗ、前記スカラー量子化された条件付確率密度関数Ｗを用いて、次式
【数７】
0005817645.tif 000076
によって定義されたＩ(Ｐ，Ｗ)、及びＩ(ｐ，ｗ)を用いて、歪み限界への到達性を保証するための条件を、
【数８】
0005817645.tif 000077
とする
ことを特徴とする請求項１に記載の符号化装置。
【請求項３】
請求項１または２に記載の符号化装置によって符号化された信号を復号化する復号化装置であって、
予め、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLが格納された第２記憶手段と、
入力された前記符号語ｍKに対して、
【数９】
0005817645.tif 000078
の系列上のアルファベットの経験分布を
【数１０】
0005817645.tif 000079
とするとき、次式
【数１１】
0005817645.tif 000080
で表されるエントロピー関数、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数１２】
0005817645.tif 000081
によって最適化処理を行うことで復号化を行う復号化手段
を具備したことを特徴とする復号化装置。
【請求項４】
前記第１記憶手段は、予め、前記連続情報源からの出力ｘの確率密度関数ｐ(ｘ)が更に格納され、
前記符号語ｍKに対して、前記確率密度関数ｐ(ｘ)を次式
【数１３】
0005817645.tif 000082
によってスカラー量子化したもの、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数１４】
0005817645.tif 000083
によって最適化を行うことにより通信路符号化を行い、φN(ｍK)を出力する通信路符号化手段を更に具備し、
前記通信路符号化手段の出力φN(ｍK)を連続通信路に入力する
ことを特徴とする請求項１または２記載の符号化装置。
【請求項５】
前記通信路符号化手段は、
前記確率密度関数ｐ、前記スカラー量子化された確率密度関数Ｐ、前記条件付確率密度関数ｗ、前記スカラー量子化された条件付確率密度関数Ｗを用いて、次式
【数１５】
0005817645.tif 000084
によって定義されたＩ(Ｐ，Ｗ)、及びＩ(ｐ，ｗ)を用いて、レート限界への到達性を保証するための条件を、
【数１６】
0005817645.tif 000085
とする
ことを特徴とする請求項４に記載の符号化装置。
【請求項６】
請求項４または５に記載の符号化装置によって通信符号化された信号を復号化する復号化装置であって、
予め、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLが格納された第２記憶手段と、
前記連続通信路から出力された信号ｙNに対して、
【数１７】
0005817645.tif 000086
の各系列上のアルファベットの経験分布を
【数１８】
0005817645.tif 000087
とするとき、次式
【数１９】
0005817645.tif 000088
で表されるエントロピー関数、前記疎行列Ａ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数２０】
0005817645.tif 000089
によって最適化処理を行うことで通信路復号化を行う通信路復号化手段と、
前記通信路復号化手段の出力ψN(ｙN)に前記疎行列Ｂを掛けることで前記符号語ｍKの推定値を求めるメッセージ推定手段と、
前記符号語ｍKの推定値に対して、
【数２１】
0005817645.tif 000090
の系列上のアルファベットの経験分布を
【数２２】
0005817645.tif 000091
とするとき、次式
【数２３】
0005817645.tif 000092
で表されるエントロピー関数、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数２４】
0005817645.tif 000093
によって最適化処理を行うことで復号化を行う復号化手段と
を具備したことを特徴とする復号化装置。
【請求項７】
連続アルファベットを符号化する符号化方法であって、
符号化装置において、
予め、Ｎ×Ｌの疎行列Ａ、Ｎ×Ｋの疎行列Ｂ、Ｌ次元横ベクトルｃL、及び条件付確率密度関数ｗ(ｙ|ｘ)を第１記憶手段に格納しておき、
ベクトル量子化手段が、連続情報源からの出力をＮ次元横ベクトルで表現したｘNを、ｑを奇素数、Δをスカラー量子化の量子化幅である正の実数として、次式
【数２５】
0005817645.tif 000094
によってスカラー量子化し、スカラー量子化された結果
【数２６】
0005817645.tif 000095
に対して、ｙのスカラー量子化を
【数２７】
0005817645.tif 000096
として、前記条件付確率密度関数ｗ(ｙ|ｘ)を次式
【数２８】
0005817645.tif 000097
によってスカラー量子化したもの、前記疎行列Ａ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数２９】
0005817645.tif 000098
によって最適化処理を行うことでベクトル量子化を行い、φN(ｘN)を出力するベクトル量子化ステップと、
符号化手段が、前記ベクトル量子化ステップにより出力されたφN(ｘN)に、前記疎行列Ｂを掛けることでＫ次元横ベクトルで表現した符号語ｍKを求める符号化ステップと、
を行うことを特徴とする符号化方法。
【請求項８】
請求項７に記載の符号化方法によって符号化された信号を復号化する復号化方法であって、
復号化装置において、
予め、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを第２記憶手段に格納しておき、
復号化手段が、入力された前記符号語ｍKに対して、
【数３０】
0005817645.tif 000099
の系列上のアルファベットの経験分布を
【数３１】
0005817645.tif 000100
とするとき、次式
【数３２】
0005817645.tif 000101
で表されるエントロピー関数、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数３３】
0005817645.tif 000102
によって最適化処理を行うことで復号化を行う復号化ステップ
を行うことを特徴とする復号化方法。
【請求項９】
前記符号化装置において、
予め、前記連続情報源からの出力ｘの確率密度関数ｐ(ｘ)を前記第１記憶手段に更に格納しておき、
符号化手段が、前記符号語ｍKに対して、前記確率密度関数ｐ(ｘ)を次式
【数３４】
0005817645.tif 000103
によってスカラー量子化したもの、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数３５】
0005817645.tif 000104
によって最適化を行うことにより通信路符号化を行い、φN(ｍK)を出力する通信路符号化ステップを更に行い、
前記通信路符号化ステップにより出力されたφN(ｍK)を連続通信路に入力する
ことを特徴とする請求項７に記載の符号化方法。
【請求項１０】
請求項９に記載の符号化方法によって符号化された信号を復号化する復号化方法であって、
復号化装置において、
予め、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを第２記憶手段に格納しておき、
通信路復号化手段が、前記連続通信路から出力された信号ｙNに対して、
【数３６】
0005817645.tif 000105
の各系列上のアルファベットの経験分布を
【数３７】
0005817645.tif 000106
とするとき、次式
【数３８】
0005817645.tif 000107
で表されるエントロピー関数、前記疎行列Ａ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数３９】
0005817645.tif 000108
によって最適化処理を行うことで通信路復号化を行う通信路復号化ステップと、
メッセージ推定手段が、前記通信路復号化ステップにより出力されたψN(ｙN)に前記疎行列Ｂを掛けることで前記符号語ｍKの推定値を求めるメッセージ推定ステップと、
復号化手段が、前記符号語ｍKの推定値に対して、
【数４０】
0005817645.tif 000109
の系列上のアルファベットの経験分布を
【数４１】
0005817645.tif 000110
とするとき、次式
【数４２】
0005817645.tif 000111
で表されるエントロピー関数、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数４３】
0005817645.tif 000112
によって最適化処理を行うことで復号化を行う復号化ステップと
を行うことを特徴とする復号化方法。
【請求項１１】
コンピュータを、
請求項１または２に記載の符号化装置の各手段として機能させるための符号化プログラム。
【請求項１２】
コンピュータを、
請求項３に記載の復号化装置の各手段として機能させるための復号化プログラム。
【請求項１３】
コンピュータを、
請求項４または５に記載の符号化装置の各手段として機能させるための符号化プログラム。
【請求項１４】
コンピュータを、
請求項６に記載の復号化装置の各手段として機能させるための復号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラムに係り、特に、連続アルファベット上の通信系において、理論で示される符号化限界にいくらでも近づき得るような疎行列符号化を実現するための符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラムに関する。
【背景技術】
【０００２】
従来では、符号化の理論限界への到達よりも符号化を効率的に処理できることの方が重視されてきた。ところが、１９９０年代に通信路符号化の分野で効率的な符号化・復号化が可能でありながら、かつ符号化レートが理論限界に近づくまでに到達可能であるLDPC(Low Density Parity Check)符号やターボ符号が出現した。それ以降、効率的な符号処理も符号化レートの理論限界への到達も同時に実現を目指すような符号の考案が大きな位置を占めるようになった。しかしながら、LDPC符号やそれに類する符号の適用先は殆どが離散アルファベットの通信系であり、連続系への適用例としてよく知られているのは２入力（０−１入力）実数出力のAWGN(Additive White Noise Gaussian)通信路くらいである。典型的な連続通信路であるガウス型通信路に対してもシャノン限界を達成する符号語の配置は与えることができても、あるメッセージを効率的に符号化・復号化する手段は知られていない。連続アルファベットの有歪情報源符号化に関しても同様である。
【０００３】
以下では通信系を情報源符号化と通信路符号化に分けて従来技術を概説し、さらに近年効率的な符号化実現方式のひとつであるとして議論されている疎行列符号化について言及する。
【０００４】
１．有歪み情報源符号化
連続アルファベットを出力とする情報源としてガウス型情報源に関してはシャノン限界を達成する符号の存在が示されているが（例えば、非特許文献１参照）、効率的な符号に関する検討はあまりなされていない。有歪み情報源符号化の実現方式としてはスカラー量子化とベクトル量子化がある。
【０００５】
・スカラー量子化：容易に実現可能であるが（例えば、非特許文献２参照）、符号化の理論限界（レート歪み関数で示される）に近づき得ない。
【０００６】
・ベクトル量子化：現実的なアルゴリズムが数多く提案されているが（例えば、非特許文献２参照）、符号化処理を効率的に行わせるために理論限界への到達性を犠牲にしている。
【０００７】
２．通信路符号化
・連続アルファベットを入出力とする通信路に関しては、理論的にはガウス型通信路の様な対称性を持つ通信路に関してはシャノン限界を達成する符号の存在が示されているが（例えば、非特許文献１参照）、効率的な符号に関する検討はあまりなされていない。ＬＤＰＣ符号の連続通信路への応用として、入力は２値，出力は連続であるＡＷＧＮ通信路が知られている（例えば、非特許文献３参照）。
【０００８】
３．疎行列符号化
・離散アルファベット上の通信系に対しては，様々な符号化方式（例えば、非特許文献４，５参照）が提案されており、理論的には符号化限界に到達することが示されている。さらに、sum-product法やＬＰ(Linear Programming)復号法などの適切な実現アルゴリズムによって効率的に実現可能であることが近年シミュレーション等で示されつつある。一方で、連続アルファベットに関しては未だ検討は行われていない。なお、多値アルファベットの符号の実現方式については例えば線形復号法（以下ＬＰ復号法）を使ったもの（例えば、非特許文献６参照）等がある。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】T. M. Cover and J. A. Thomas, Elements of Information Theory 2ndEd., Wiley, 2006.
【非特許文献２】Gersho and R. M. Gray, Vector Quantization and Signal Compression, Kluwer Academic, 1992.
【非特許文献３】和田山正, 低密度検査符号とその復号法, トリケップス, 2002.
【非特許文献４】S. Miyake and J. Muramatsu, "A construction of lossy source code using LDPC matrices," IEICE Trans. Fundamentals, vol. E91-A, no. 6, pp. 1488-1501, 2008.
【非特許文献５】Muramatsu and S. Miyake, "Hash property and coding theorems for sparse matrices and maximum-likelihood coding, " IEEE Trans. Inform. Theory, vol. 56, no. 5, pp. 2143-2162, 2010.
【非特許文献６】本多淳也, 山本博資, "拡大体上のＬＤＰＣ符号の線形計画法による復号法, "第３３回情報理論とその応用シンポジウム(SITA2010)予稿集, pp. 121-126, 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
スカラー量子化を用いて連続アルファベットを適切に離散化し、そこで疎行列符号化を適用するアルゴリズムを考える。その際に、
・通常は通信系の統計的な性質は明らかでない。従って通信系の統計的な性質に依存しない符号（ユニバーサル符号）となるよう構成する：
・量子化幅Δを小さくする際の条件を明確にする。特に量子化幅Δが小さくなった極限で、相互情報量などの符号化レートに関連する量が連続系における対応する量に近づかなければならない：
という点に注意する必要がある。
【００１１】
本発明は、上記の点に鑑みなされたもので、上記の条件を満たし、連続アルファベット上の通信系において、符号化限界に近い性能を示しつつ、効率的な実現も可能とするような符号化・復号化システム及び方法及び符号化プログラム及び復号化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するため、本発明（請求項１）は、連続アルファベットを符号化する符号化装置であって、
予め、Ｎ×Ｌの疎行列Ａ、Ｎ×Ｋの疎行列Ｂ、Ｌ次元横ベクトルｃL、及び条件付確率密度関数ｗ(ｙ|ｘ)が格納された第１記憶手段と、
連続情報源からの出力をＮ次元横ベクトルで表現したｘNを、ｑを奇素数、Δをスカラー量子化の量子化幅である正の実数として、次式
【数４４】
0005817645.tif 000002
によってスカラー量子化し、スカラー量子化された結果
【００１３】
【数４５】
0005817645.tif 000003
に対して、ｙのスカラー量子化を
【数４６】
0005817645.tif 000004
として、前記条件付確率密度関数ｗ(ｙ|ｘ)を次式
【数４７】
0005817645.tif 000005
によってスカラー量子化したもの、前記疎行列Ａ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数４８】
0005817645.tif 000006
によって最適化処理を行うことでベクトル量子化を行い、φN(ｘN)を出力するベクトル量子化手段と、
前記ベクトル量子化手段の出力φN(ｘN)に、前記疎行列Ｂを掛けることでＫ次元横ベクトルで表現した符号語ｍKを求める符号化手段と、を具備したことを特徴とする。
【００１４】
また、本発明（請求項２）は、前記の符号化装置において、
前記ベクトル量子化手段は、
前記連続情報源からの出力ｘの確率密度関数をｐ、該確率密度関数ｐを次式
【数４９】
0005817645.tif 000007
によってスカラー量子化したものをＰとし、前記条件付確率密度関数ｗ、前記スカラー量子化された条件付確率密度関数Ｗを用いて、次式
【数５０】
0005817645.tif 000008
によって定義されたＩ(Ｐ，Ｗ)、及びＩ(ｐ，ｗ)を用いて、歪み限界への到達性を保証するための条件を、
【００１５】
【数５１】
0005817645.tif 000009
とすることを特徴とする。
【００１６】
また、本発明（請求項３）は、前記の符号化装置によって符号化された信号を復号化する復号化装置であって、
予め、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLが格納された第２記憶手段と、
入力された前記符号語ｍKに対して、
【数５２】
0005817645.tif 000010
の系列上のアルファベットの経験分布を
【数５３】
0005817645.tif 000011
とするとき、次式
【数５４】
0005817645.tif 000012
で表されるエントロピー関数、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数５５】
0005817645.tif 000013
によって最適化処理を行うことで復号化を行う復号化手段を具備したことを特徴とする。
【００１７】
本発明（請求項４）は、前記の符号化装置において、
前記第１記憶手段は、予め、前記連続情報源からの出力ｘの確率密度関数ｐ(ｘ)が更に格納され、
前記符号語ｍKに対して、前記確率密度関数ｐ(ｘ)を次式
【数５６】
0005817645.tif 000014
によってスカラー量子化したもの、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【００１９】
【数５７】
0005817645.tif 000015
によって最適化を行うことにより通信路符号化を行い、φN(ｍK)を出力する通信路符号化手段を更に具備し、
前記通信路符号化手段の出力φN(ｍK)を連続通信路に入力する
ことを特徴とする。
【００２０】
また、本発明（請求項５）は、前記の符号化装置において、
前記通信路符号化手段は、
前記確率密度関数ｐ、前記スカラー量子化された確率密度関数Ｐ、前記条件付確率密度関数ｗ、前記スカラー量子化された条件付確率密度関数Ｗを用いて、次式
【数５８】
0005817645.tif 000016
によって定義されたＩ(Ｐ，Ｗ)、及びＩ(ｐ，ｗ)を用いて、レート限界への到達性を保証するための条件を、
【００２１】
【数５９】
0005817645.tif 000017
とすることを特徴とする。
【００２２】
また、本発明（請求項６）は、前記の符号化装置によって通信符号化された信号を復号化する復号化装置であって、
予め、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLが格納された第２記憶手段と、
前記連続通信路から出力された信号ｙNに対して、
【数６０】
0005817645.tif 000018
の各系列上のアルファベットの経験分布を
【数６１】
0005817645.tif 000019
とするとき、次式
【数６２】
0005817645.tif 000020
で表されるエントロピー関数、前記疎行列Ａ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数６３】
0005817645.tif 000021
によって最適化処理を行うことで通信路復号化を行う通信路復号化手段と、
前記通信路復号化手段の出力ψN(ｙN)に前記疎行列Ｂを掛けることで前記符号語ｍKの推定値を求めるメッセージ推定手段と、
【００２４】
前記符号語ｍKの推定値に対して、
【数６４】
0005817645.tif 000022
の系列上のアルファベットの経験分布を
【数６５】
0005817645.tif 000023
とするとき、次式
【数６６】
0005817645.tif 000024
で表されるエントロピー関数、前記疎行列Ａ、前記疎行列Ｂ、及び前記Ｌ次元横ベクトルｃLを用いて、最適化における最適値を与える引数を出力する関数argで表される次式
【数６７】
0005817645.tif 000025
によって最適化処理を行うことで復号化を行う復号化手段とを具備したことを特徴とする。
【発明の効果】
【００２５】
通常の連続系におけるデータ圧縮（有歪み情報源符号化）に関しては、サンプリング、スカラー（量子化）の後、量子化された量をさらに２値化した後、符号化を行うが、本発明によれば、スカラー量子化後の２値化の処理は不要となるので、従来よりも効率的な処理が可能となる。
【００２６】
一方、誤り訂正（通信路符号化）に関しては、AWGN通信路に限ることなく、連続アルファベットを持つ一般の通信路に対しても、本発明で示した疎行列符号化を適用することでシャノン限界に迫る伝送レートを持ち、かつ、効率的に実現可能となる。
【図面の簡単な説明】
【００２７】
【図１】本発明の一実施の形態における符号化・復号化システムの構成図である。
【図２】本発明の一実施の形態における有歪み符号化器の構成図である。
【図３】本発明の一実施の形態における有歪み符号化器の動作のフローチャートである。
【図４】本発明の一実施の形態における有歪み復号化器の構成図である。
【図５】本発明の一実施の形態における有歪み復号化器の動作のフローチャートである。
【図６】本発明の一実施の形態における通信路符号化器の構成図である。
【図７】本発明の一実施の形態における通信路符号化器の動作のフローチャートである。
【図８】本発明の一実施の形態における通信路復号化器の構成図である。
【図９】本発明の一実施の形態における通信路復号化器の動作のフローチャートである。
【図１０】本発明の一実施の形態における実数の量子化を示す図である。
【発明を実施するための形態】
【００２８】
以下、図面と共に本発明の実施の形態を説明する。
【００２９】
図１は、本発明の一実施の形態における符号化・復号化システム構成図である。
【００３０】
本発明の符号化・復号化システムは、情報源及び通信路に適用する符号化器と復号化器を有する。同図に示すように、情報源に適用され、連続アルファベットを符号化する有歪み符号化器１００と、情報符号化された連続アルファベットを復号化する有歪み符号化器２００と、通信路に適用される、連続アルファベットを入出力とし、符号化を行う通信路符号化器３００、復号化を行う通信路復号化器４００、から構成される。
【００３１】
以下に動作の概要を示す。
【００３２】
＜有歪み符号化器１００＞
データ圧縮のための有歪み符号化器１００は、図２に示すように、ベクトル量子化部１１０と符号化部１２０を有する。ベクトル量子化部１１０は、疎行列A及び最適化のためのベクトルｃL、条件付確率密度関数（ｗ（ｙ｜ｘ））をメモリ（図示せず）に保持し、符号化部１２０は、疎行列Bをメモリ（図示せず）に保持するものとする。
【００３３】
図３は、本発明の一実施の形態における有歪み符号化器の動作のフローチャートである。
【００３４】
ベクトル量子化部１１０では、連続情報源からの出力［連続アルファベット］xNを取得すると（ステップ１０１）、メモリ（図示せず）に格納された行列A、ベクトルｃL、条件付確率密度関数（ｗ（ｙ｜ｘ））を用いてスカラー量子化し（ステップ１０２）、その結果
【００３５】
【数８】
0005817645.tif 000026
を用いて最適化処理を行うことでベクトル量子化を行い、φ（xN）を出力する（ステップ１０３）。符号化部１２０は、ベクトル量子化部１１０の出力φ（xN）に疎行列Bを掛けることで、符号語信号ｍKを求める（ステップ１０４）。
【００３６】
当該有歪み符号化器１００の詳細な動作については後述する。
【００３７】
＜有歪み復号化器２００＞
有歪み情報源符号化されたデータを復号する有歪み復号化器２００は、図４に示すように、復号化部２１０を有する。復号化部２１０は、疎行列A、BとベクトルｃLをメモリ（図示せず）保持する。
【００３８】
図５は、本発明の一実施の形態における有歪み復号化器の動作のフローチャートである。
【００３９】
復号化部２１０は、符号語ｍKを取得し（ステップ２０１）、入力された符号語ｍKについて、疎行列A、B、及びベクトルｃLを用いて最適化処理を行うことで復号化を行う（ステップ２０２）。
【００４０】
＜通信路符号化器３００＞
次に、通信路符号化器３００は、図６に示すように符号化部３１０を有する。符号化部３１０は、疎行列A、B、及び最適化のためのベクトルcLをメモリ（図示せず）に保持するものとする。
【００４１】
図７は、本発明の一実施の形態における通信路符号化器の動作のフローチャートである。
【００４２】
符号化部３１０は、相手に伝えるメッセージｍKを取得し（ステップ３０１）、保持している疎行列A、B及びベクトルcL及び、取得したｍKを用いて最適化を行うことで符号化を行う（ステップ３０２）。なお、通信路符号化器３００の詳細な動作については後述する。
【００４３】
＜通信路復号化器４００＞
次に、通信路復号化器４００は、図８に示すように、復号化部４１０とメッセージ推定部４２０を有する。なお、復号化部４１０は、疎行列A及びベクトルｃLをメモリ（図示せず）に保持しているものとする。また、メッセージ推定部４２０は、疎行列Bをメモリ（図示せず）に保持しているものとする。
【００４４】
図９は、本発明の一実施の形態における通信路復号化器の動作のフローチャートである。
【００４５】
復号化部４１０は、連続通信路からの出力ｙNを取得し（ステップ４０１）、保持している疎行列A及びベクトルをｃL用いて、最適化処理を行うことで復号化を行う（ステップ４０２）。メッセージ推定部４２０は、復号化部４１０の出力
【００４６】
【数９】
0005817645.tif 000027
に疎行列Bを掛けることで符号語信号
【００４７】
【数１０】
0005817645.tif 000028
を求める（ステップ４０３）。なお、当該通信路復号化器４００の詳細な動作について後述する。
【００４８】
以下に、上記の各構成の動作の詳細を説明する。
【００４９】
以下では、まず、連続情報源ｐが与えられたときの有歪み情報源符号について述べた後、連続通信路ｗが与えられたときの通信路符号について説明する。
【００５０】
＜有歪み符号化装置１００＞
図２に沿って、有歪み符号化器１００の処理について説明する。
【００５１】
ベクトル量子化部１１０で用いられる量子化アルゴリズムを説明する。
【００５２】
符号化部１２０は、ベクトル量子化１１０の出力φ（xN）に疎行列Bを掛けることで符号語信号mkを求める。
【００５３】
以下に具体的に説明する。
【００５４】
まず、有歪み情報源符号の構成を示す。
【００５５】
ｑ元体Ｆqを、
【００５６】
【数１１】
0005817645.tif 000029
とする。また、N×L疎行列A、N×K疎行列B、およびL次元横ベクトルｃL、および条件付き確率密度関数w(y|x)は、予め与えられメモリ（図示せず）に格納されているものとし、w(y|x)は次式で表される歪条件を満足するものとする。
【００５７】
【数１２】
0005817645.tif 000030
ベクトル量子化部１１０において条件付き確率密度関数w(y|x)を量子化したものを
【００５８】
【数１３】
0005817645.tif 000031
とする。すなわち、
【００５９】
【数１４】
0005817645.tif 000032
に対して、
【００６０】
【数１５】
0005817645.tif 000033
とする。但し、
【００６１】
【数１６】
0005817645.tif 000034
は、
【００６２】
【数１７】
0005817645.tif 000035
によって与えられる（図１０参照）。但し、ｑを奇素数、Δを正の実数とする。
【００６３】
【数１８】
0005817645.tif 000036
も同様である。
【００６４】
xN を連続情報源ｐNからの出力とすると、xNのベクトル量子化は、
【００６５】
【数１９】
0005817645.tif 000037
として与えられる。関数argは最適化（今の場合はmax）における最適値を与える引数を出力するものである。ベクトル量子化
【００６６】
【数２０】
0005817645.tif 000038
の符号語をｍKとすると、符号化部１２０では、疎行列Bを用いて、
【００６７】
【数２１】
0005817645.tif 000039
とし、ｍKを出力する。符号器について、情報源pの統計的性質とは無関係に構成できることに注意しておく。
【００６８】
＜有歪み復号化器２００＞
次に、有歪み復号化器２００について説明する。
【００６９】
図４に沿って、有歪み復号化器２００について説明する。
【００７０】
有歪み復号化器２００の復号化部２１０は、入力された符号語信号ｍK用いて最適化を行うことで復号化を行う。
【００７１】
以下に詳細に説明する。
【００７２】
符号語ｍKが復号化部２１０に与えられたものとすると、復号化器
【００７３】
【数２２】
0005817645.tif 000040
は、
【００７４】
【数２３】
0005817645.tif 000041
として与えられる。但し、上式中の関数H(エントロピー関数)は、
【００７５】
【数２４】
0005817645.tif 000042
のタイプ（すなわち系列上のアルファベットの経験分布）を
【００７６】
【数２５】
0005817645.tif 000043
とするとき、
【００７７】
【数２６】
0005817645.tif 000044
である。
【００７８】
また、最適化の実行には多値の場合のＬＰ復号を用いる。これは、エントロピー関数がタイプの関数であるのでタイプを固定して、固定されたタイプに関する実現可能性を判定する問題に帰着できる事実を用いる。復号化部２１０についても連続情報源pの統計的性質とは無関係に構成できることに注意しておく。
【００７９】
＜シャノン限界への到達性＞
次に、連続アルファベットを出力とする有歪み符号化問題について、シャノン限界への到達性について説明する。
【００８０】
【数２７】
0005817645.tif 000045
とする。有歪み符号化問題において圧縮レートR=K/Nが与えられたときに達成可能な歪みの限界は、
【００８１】
【数２８】
0005817645.tif 000046
で与えられる（非特許文献１）。歪み限界への到達性を保証するためには、
【００８２】
【数２９】
0005817645.tif 000047
が成り立たなければならない。上式が成立するためには、新たにパラメータnを導入して
【００８３】
【数３０】
0005817645.tif 000048
となるように、有歪み符号化器１００のベクトル量子化部１１０において量子化を行えばよい。
【００８４】
＜通信路符号化器３００＞
通信路符号化器３００について、図６に沿って説明する。
【００８５】
ｑ元体Fqを、
【００８６】
【数３１】
0005817645.tif 000049
とする。また、N×L疎行列A，N×K疎行列B，およびL次元横ベクトルcLは予め与えられているものとする。符号化部３１０において符号語のエネルギー制約
【００８７】
【数３２】
0005817645.tif 000050
を満足する確率密度関数p(x)を量子化したものを、
【００８８】
【数３３】
0005817645.tif 000051
とする。すなわち、
【００８９】
【数３４】
0005817645.tif 000052
に対して、
【００９０】
【数３５】
0005817645.tif 000053
とする。但し、
【００９１】
【数３６】
0005817645.tif 000054
はｘのスカラー量子化である。このとき、送りたいメッセージを、
【００９２】
【数３７】
0005817645.tif 000055
とすると、符号化部３１０
【００９３】
【数３８】
0005817645.tif 000056
は、
【００９４】
【数３９】
0005817645.tif 000057
として与えられる。関数argは最適化（今の場合はmax）における最適値を与える引数を出力するものである。なお、上の符号化には通信路Wは含まれていないことに注意しておく。
【００９５】
＜通信路復号化器４００＞
図８に沿って、通信路復号化器４００について説明する。
【００９６】
まず、復号化部４１０の処理を説明する。
【００９７】
yNを通信路からの出力、yNの各要素をスカラー量子化したものを、
【００９８】
【数４０】
0005817645.tif 000058
とすると、復号部４１０
【００９９】
【数４１】
0005817645.tif 000059
は、
【０１００】
【数４２】
0005817645.tif 000060
として与えられる。ただし、上式中の関数（エントロピー関数）Hは、
【０１０１】
【数４３】
0005817645.tif 000061
のタイプ（すなわち、各系列上のアルファベットの経験分布）を、
【０１０２】
【数４４】
0005817645.tif 000062
とするとき、
【０１０３】
【数４５】
0005817645.tif 000063
である。また、メッセージ推定部４２０で求められるメッセージｍKの推定値を
【０１０４】
【数４６】
0005817645.tif 000064
とすると、
【０１０５】
【数４７】
0005817645.tif 000065
となる。また、最適化の実行には多値の場合のＬＰ復号を用いる。これは、エントロピー関数がタイプの関数であるのでタイプを固定して、固定されたタイプに関する実現可能性を判定する問題に帰着できる事実を用いる。復号化器についても通信路ｗの統計的性質とは無関係に構成できることに注意しておく。
【０１０６】
＜シャノン限界への到達性＞
【０１０７】
【数４８】
0005817645.tif 000066
とする。通信路符号化問題において復号誤りが漸近的に０となるためには伝送レートR=K/Nについて、
【０１０８】
【数４９】
0005817645.tif 000067
でなければならない（非特許文献１）。レート限界への到達性を保証するためには、
【０１０９】
【数５０】
0005817645.tif 000068
が成り立たなければならない。上式が成立するためには、新たにパラメータｎを導入して、
【０１１０】
【数５１】
0005817645.tif 000069
となるように、符号化部３１０においてスカラー量子化を行えばよい。
【０１１１】
上記のように、本発明は、従来からあるスカラー量子化と疎行列とを組み合わせることにより、連続アルファベット上の通信系（情報源及び通信路）において、符号化限界に近い性能を示しつつ効率的な実現も可能とする符号化・復号化システムを構成した。さらに、符号化器、復号化器のアルゴリズムは通信系の統計的な性質を知ることなく、実行可能なユニバーサル性を持つ。
【０１１２】
なお、上記の符号化器及び復号化器の各構成要素の動作（アルゴリズム）をプログラムとして構築し、符号化器、復号化器として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１３】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１１４】
１００  有歪み符号化器
１１０  ベクトル量子化部
１２０  符号化部
２００  有歪み復号化器
２１０  復号化部
３００  通信路符号化器
３１０  符号化部
４００  通信路復号化器
４１０  復号化部
４２０  メッセージ推定部
【図１】
0005817645.tif 000113
【図２】
0005817645.tif 000114
【図３】
0005817645.tif 000115
【図４】
0005817645.tif 000116
【図５】
0005817645.tif 000117
【図６】
0005817645.tif 000118
【図７】
0005817645.tif 000119
【図８】
0005817645.tif 000120
【図９】
0005817645.tif 000121
【図１０】
0005817645.tif 000122