(57)【要約】【課題】複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての複数の値の系列である実現値についての確率の分布を第二確率分布に従う乱数の系列を生成する技術を提供する。【解決手段】複数の値の系列を構成する１個の値である実現値についての確率である第三確率を、その実現値を用いて更新前の複数の値の系列を更新後も所定の条件を満たすように更新した後の複数の値の系列が第一確率分布に従って出現する確率に応じた確率として、取り得る全ての実現値についての第四確率の分布である第四確率分布を生成する第三確率分布生成部の処理と、第三確率分布に従い１個の実現値を生成し、その生成された実現値を用いて複数の値の系列を更新後も所定の条件を満たすように更新する系列更新部の処理とを繰り返し行う。【選択図】図１
2015206941.tif 000002
【特許請求の範囲】
【請求項１】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
上記所定の条件を満たす複数の値の系列の初期値を決定する初期値決定部と、
上記複数の値の系列を構成する１個の値である実現値についての確率である第三確率を、その実現値を用いて更新前の複数の値の系列を更新後も上記所定の条件を満たすように更新した後の複数の値の系列が上記第一確率分布に従って出現する確率に応じた確率として、取り得る全ての実現値についての上記第四確率の分布である第四確率分布を生成する第三確率分布生成部と、
上記第三確率分布に従い１個の実現値を生成し、その生成された実現値を用いて上記複数の値の系列を更新後も上記所定の条件を満たすように更新する系列更新部と、
上記第三確率分布生成部及び上記系列更新部の処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる第一制御部と、
を含む乱数系列生成装置。
【請求項２】
請求項１の乱数系列生成装置であって、
上記初期値決定部は、
上記複数の値の系列を構成する１個の値である実現値についての確率である第四確率を、その実現値が出現したときに次回以降の繰り返し処理で生成される残りの乱数の系列が上記第一確率分布に従って出現しかつ上記所定の条件を満たす確率に応じた確率として、取り得る全ての実現値についての上記第四確率の分布である第四確率分布を生成する第四確率分布生成部と、
上記第四確率分布に従い１個の実現値を乱数として生成する乱数生成部と、
上記第四確率分布生成部及び上記乱数生成部の処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させ、その生成された乱数の系列を上記所定の条件を満たす複数の値の系列の初期値とする第二制御部と、
を更に含む、
乱数系列生成装置。
【請求項３】
請求項１又は２の乱数系列生成装置を含み、
上記所定の条件は、メッセージ及び所定の共有情報と、上記複数の値の系列との関係を所定の関数を用いて表現した条件である、
符号化装置。
【請求項４】
請求項１又は２の乱数系列生成装置を含み、
上記生成された乱数の系列及び所定の第二関数を用いて符号を生成する圧縮部と、を含み、
上記所定の条件は、所定の共有情報と複数の値の系列との関係を所定の第一関数を用いて表現した条件であり、
上記所定の第一確率分布は、符号化対象の情報を条件とする条件付き確率である、
符号化装置。
【請求項５】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
初期値決定部が、上記所定の条件を満たす複数の値の系列の初期値を決定する初期値決定ステップと、
第三確率分布生成部が、上記複数の値の系列を構成する１個の値である実現値についての確率である第三確率を、その実現値を用いて更新前の複数の値の系列を更新後も上記所定の条件を満たすように更新した後の複数の値の系列が上記第一確率分布に従って出現する確率に応じた確率として、取り得る全ての実現値についての上記第四確率の分布である第四確率分布を生成する第三確率分布生成ステップと、
系列更新部が、上記第三確率分布に従い１個の実現値を生成し、その生成された実現値を用いて上記複数の値の系列を更新後も上記所定の条件を満たすように更新する系列更新ステップと、
第一制御部が、上記第三確率分布生成部及び上記系列更新部の処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる第一制御ステップと、
を含む乱数系列生成方法。
【請求項６】
請求項５の乱数系列生成方法を含み、
上記所定の条件は、メッセージ及び所定の共有情報と、上記複数の値の系列との関係を所定の関数を用いて表現した条件である、
符号化方法。
【請求項７】
請求項５の乱数系列生成方法を含み、
上記生成された乱数の系列及び所定の第二関数を用いて符号を生成する圧縮部と、を含み、
上記所定の条件は、所定の共有情報と複数の値の系列との関係を所定の第一関数を用いて表現した条件であり、
上記所定の第一確率分布は、符号化対象の情報を条件とする条件付き確率である、
符号化方法。
【請求項８】
請求項１から４の何れかの乱数系列生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、乱数の系列を生成する技術及び情報を符号化する技術に関する。
【背景技術】
【０００２】
［記法の説明］
Xが確率変数であるとき、Xのとりうる値の集合を[X]と記す。、すなわち集合Sに含まれる要素の数を|S|と記す。差集合をS＼S’と記し、これは集合Sに含まれており、かつ集合S’に含まれていない要素全体からなる集合を表す。空集合をφと記す。
【０００３】
Xn≡(X1,X2,…,Xn)はn次元の確率変数で、その実現値をxn≡(x1,x2,…,xn)と記す。[X]のn次元直積集合を[X]nと記す。確率変数Xと対応する確率分布をpXと記す。
【０００４】
A,Bは一般には関数を表し、Axnは関数Aのベクトルxnにおける値を表す。関数Aの値域をImA≡{Axn:xn∈[X]n}と記す。qを一つの素数の巾となる(すなわち素数pと整数kが存在してq=pkとなる)整数とする。関数A:GF(q)n→GF(q)mがq元の有限体GF(q)上ベクトル空間の線形写像の場合、
【０００５】
【数１】
2015206941.tif 000003
【０００６】
のように行列で表記する。このとき、xnは列ベクトル
【０００７】
【数２】
2015206941.tif 000004
【０００８】
となる。以後、GF(q)の要素の和、差、積には通常の演算記号を用いる。例えば、a,b∈GF(q)に対して、a+b,a-b,abはそれぞれGF(q)での和、差、積を表す。特に、各i∈{1,…,n}でai∈GF(q)のときΣi=1naiはGF(q)での和a1+…+anを表す。
【０００９】
離散値を取る確率変数XのエントロピーH(X)を
【００１０】
【数３】
2015206941.tif 000005
【００１１】
とする。連続値を取り売る確率変数Yの密度関数をpY、確率変数Yが与えられた時のXの条件付き確率分布をpX|Yで与えたとき、エントロピーH(X|Y)を
【００１２】
【数４】
2015206941.tif 000006
【００１３】
とする。歪み関数d:[X]×[Y]→[0,∞)が与えられたとき、平均歪みEXY[d(X,Y)]を
【００１４】
【数５】
2015206941.tif 000007
【００１５】
とする。ここで、[Y]が離散集合の時は積分∫[Y]dyを和Σy∈[Y]と置き換える。
【００１６】
無記憶な同時確率分布pXnを次のように定義する。
【００１７】
【数６】
2015206941.tif 000008
【００１８】
最後に、関数|θ|+を次のように定義する。
【００１９】
【数７】
2015206941.tif 000009
【００２０】
［従来の制約条件を満たす乱数系列生成法］
本節ではA、vm≡(v1,v2,…,vm)及び無記憶な確率変数Xn≡(X1,X2,…,Xn)の分布pXnが与えられたときに、
【００２１】
【数８】
2015206941.tif 000010
【００２２】
に従う乱数xnを発生させる方法を記述する（例えば、非特許文献１参照。）。
【００２３】
所定の条件をAxn=vmとし、所定の第一確率分布をpXnとする。上式の右辺の分子は、第一確率分布pXnにおいて実現値xnが出現する確率である。分母は正規化項であるため、μ(xn)は、第一確率分布pXnにおいて実現値xnが出現する確率に応じた確率についての確率分布であると言える。また、μ(xn)は、所定の条件Axn=vmを満たす全ての複数の値の系列である実現値xnについての上記確率の分布であるとも言える。この確率分布を、第二確率分布とする。
【００２４】
以下では、[X]≡GF(q)を仮定し、m≦nとして、(1)で与えたフルランクのm×n行列Aを考える。この行列のi行目のn次元行ベクトルをain≡(ai,1,ai,2,…,ai,n)とする。上式の右辺はベクトルainとxn≡(x1,x2,…,xn)∈[X]nの内積を
【００２５】
【数９】
2015206941.tif 000011
【００２６】
と定義する。行列Aとベクトル
【００２７】
【数１０】
2015206941.tif 000012
【００２８】
に対して、確率分布(2)で定まる分布を発生させる乱数系列生成装置の具体処理を記述する。
【００２９】
以下、Aをフルランクの行列として、行列Aの右側のm×m行列A2が正則行列であると仮定しても一般性は失われない。実際に、任意の行列Aとベクトルvmから冗長な条件式を構成するAの行とvmの成分を取り除いた行列を求め、この行列の行ベクトルと変数(x1,x2,…,xn)の順序を適切に並びかえることにより所望の行列を求めることができる。
【００３０】
行列Aの左側のm×(n-m)行列をA1とすると、上記の仮定から、xn-m≡(x1,…,xn-m)を決定すれば、
【００３１】
【数１１】
2015206941.tif 000013
【００３２】
によってAxn=vmを満たす残りの変数(xn-m+1,…,xn)を求めることができる。ここで、A2-1はA2の逆行列を表し、アルゴリズムの実行前に求めることができる。特にA2が単位行列である場合は、xn-m≡(x1,…, xn-m)を決定すれば各i∈{1,…,m}で
【００３３】
【数１２】
2015206941.tif 000014
【００３４】
によってAxn=vmを満たす残りの変数(xn-m+1,…,xn)を決定することができる。
【００３５】
各i∈{1,…,m}でインデックス集合T(i)⊂{1,2,…,n}を次のように定義する。
【００３６】
【数１３】
2015206941.tif 000015
【００３７】
このとき、内積ain・xnは次の等式を満たしている。
【００３８】
【数１４】
2015206941.tif 000016
【００３９】
xT(i)をxnからインデックス集合T(i)と対応する部分を取り出した|T(i)|次元のベクトルとする。χ(xT(i),vi)を次のように定義する。
【００４０】
【数１５】
2015206941.tif 000017
【００４１】
一般的にsum-productアルゴリズムとは、変数ベクトルwnの一部からなる変数ベクトルwJ(i)で定まる関数es(wJ(i))が各i∈Iで与えられたとき、周辺化関数
【００４２】
【数１６】
2015206941.tif 000018
【００４３】
を求める手続きである。ここで、Σ_(wn＼{w})は、ベクトルwnに現れる変数wを固定した全てのwnの値を動かした時の和である。また、(3)で定めたf(w)ではなく、右辺の分子に現れた
【００４４】
【数１７】
2015206941.tif 000019
【００４５】
を求める手続きとしてsum-productアルゴリズムが記述される場合があるが、以下では、(3)で定めたf(w)を求める手続きをsum-productアルゴリズムと呼ぶことにする。sum-product アルゴリズム実行中では、事前に設定した繰り返し回数に到達するか、周辺化関数の変化が微小になった時点で処理を中断する。ここで、繰り返し回数が大きい程計算時間がかかるが、周辺化関数の近似性能は良くなる。
【００４６】
以下では、確率分布(2)に従う乱数xnを発生させる乱数系列生成装置について説明する。(2)で定義された確率分布に従う乱数を発生させるために、乱数系列生成装置は次の手続きを実行する。以下Σはその下に書かれている変数の全てのとりうる値に関する和を表すこととする。例えば、Σxjは全てのxj∈[X]に関する和である。
【００４７】
[[乱数系列生成装置の具体処理]]
(Step 1) 初期設定部は、k=1に設定する。
【００４８】
(Step 2) 関数計算部が、sum-productアルゴリズムを実行して、関数
【００４９】
【数１８】
2015206941.tif 000020
【００５０】
を求める。なお、上式の右辺ではこれまでに記録したx1,…,xk-1を代入し、χ(xT(i),vi)が定数となったものを記録しておけば将来の計算を省略できる。
【００５１】
(Step 3) 乱数生成部が、確率分布fk(xk)でxkを発生させ記憶部に記録する。
【００５２】
(Step 4) 終了判定部が、k=nであれば、これまでに記録した変数の値を連結した、xn≡(x1,…,xn)を出力して終了する。k<nであれば、これまでに記録した(x1,…,xk)からAxn=vmを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する。もしも唯一定まるのであれば、(xk+1,…,xn)を求めてxn≡(x1,…,xn)を出力して終了する。唯一に定まらない場合には、kの値を1増やして(Step2)に戻る。
【００５３】
本アルゴリズムの計算時間は、(Step 2)にsum-productアルゴリズムを適用してO(n)で実行することを仮定し、(Step 4)の計算時間がO(n2)であることを仮定すれば、全体でO(n2)の計算時間で終了する。
【先行技術文献】
【非特許文献】
【００５４】
【非特許文献１】J. Muramatsu, “Channel coding and lossy source coding using a constrained random number generator”, arXiv:1302.1951, 2013.
【発明の概要】
【発明が解決しようとする課題】
【００５５】
従来の乱数系列生成装置の具体処理では、wを行列Aの行重み(1行にある非零成分の個数)の最大値とすると、sum-product内の1回の繰り返しではO(nw2qw)回の実数の演算を必要としていた。
【００５６】
この発明は、従来よりも性能を向上させた乱数系列生成装置、符号化装置、これらの方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００５７】
この発明の一態様による乱数系列生成装置は、複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての複数の値の系列である実現値についての確率の分布を第二確率分布として、所定の条件を満たす複数の値の系列の初期値を決定する初期値決定部と、複数の値の系列を構成する１個の値である実現値についての確率である第三確率を、その実現値を用いて更新前の複数の値の系列を更新後も所定の条件を満たすように更新した後の複数の値の系列が第一確率分布に従って出現する確率に応じた確率として、取り得る全ての実現値についての第四確率の分布である第四確率分布を生成する第三確率分布生成部と、第三確率分布に従い１個の実現値を生成し、その生成された実現値を用いて複数の値の系列を更新後も所定の条件を満たすように更新する系列更新部と、第三確率分布生成部及び系列更新部の処理を繰り返すことにより、第二確率分布に従う乱数の系列を生成させる第一制御部と、を備えている。
【００５８】
この発明の一態様による符号化装置は、乱数系列生成装置を含み、所定の条件は、メッセージ及び所定の共有情報と、複数の値の系列との関係を所定の関数を用いて表現した条件である。
【００５９】
この発明の一態様による符号化装置は、乱数系列生成装置を含み、生成された乱数の系列及び所定の第二関数を用いて符号を生成する圧縮部と、を含み、所定の条件は、所定の共有情報と複数の値の系列との関係を所定の第一関数を用いて表現した条件であり、所定の第一確率分布は、符号化対象の情報を条件とする条件付き確率である。
【発明の効果】
【００６０】
従来よりも性能を向上させることができる。例えば、従来よりも演算量を軽減することができる。
【図面の簡単な説明】
【００６１】
【図１】乱数系列生成装置の例を説明するためのブロック図。
【図２】初期値決定部の例を説明するためのブロック図。
【図３】乱数系列生成方法の例を説明するためのフローチャート。
【図４】初期値決定の例を説明するためのフローチャート。
【図５】第一の符号化装置及び復号装置の例を説明するためのブロック図。
【図６】第一の符号化方法の例を説明するためのフローチャート。
【図７】第一の復号方法の例を説明するためのフローチャート。
【図８】第二の符号化装置及び復号装置の例を説明するためのブロック図。
【図９】第二の符号化方法の例を説明するためのフローチャート。
【図１０】第二の復号方法の例を説明するためのフローチャート。
【発明を実施するための形態】
【００６２】
［乱数系列生成装置及び方法］
以下では、m×n行列Aとm次元ベクトルvm≡(v1,v2,…,vm)を与えたときに、確率分布(2)に従う乱数xnを発生させる乱数系列生成装置及び方法について説明する。
【００６３】
以下では、Aの右側のm×m行列は単位行列であると仮定する。すなわち、Aは
【００６４】
【数１９】
2015206941.tif 000021
【００６５】
行列Aの右側のm×m行列が単位行列であると仮定しても一般性は失われない。実際に、任意の行列Aとベクトルvmから冗長な条件式を構成するAの行とvmの成分を取り除いた行列を求め、この行列の行ベクトルと変数(x1,x2,…,xn)の順序を適切に並びかえることにより行列Aの右側のm×m行列をフルランクの行列にすることが出来る。更に、行列Aの右側のm×m行列A2がフルランクの行列であるとき、条件Axn=vmは
【００６６】
【数２０】
2015206941.tif 000022
【００６７】
と変形できる。ここで、行列A2-1Aの右側のm×m行列は単位行列となっている。すなわち、(5)を満たす行列A,ベクトルvmをそれぞれ行列A2-1A,ベクトルA2-1vmとして、下記の具体処理を実行することが出来る。
【００６８】
以下に二つの乱数系列生成装置の具体処理を記述する。
【００６９】
[[乱数系列生成装置の具体処理１]]
図１に示すように、乱数系列生成装置１は、記憶部１１、第一制御部１２、第三確率分布生成部１３、系列更新部１４及び初期値決定部１５を例えば備えている。
【００７０】
乱数系列生成装置の具体処理１では、j∈{1,…,n-m}に対して、Ijを次のように定義する。
【００７１】
【数２１】
2015206941.tif 000023
【００７２】
Kをあらかじめ定めた繰り返し回数とする。また[K]を正の整数の集合とする。
【００７３】
(Step S1) 初期値決定部１５は、Axn=vmを満たすxn=(x1,…,xn)を定めて初期値とする。具体的には、(x1,…,xn-m)にあらかじめ定めた初期値(ランダムでも良い)を代入した後に各i∈{1,…,m}に対して、
【００７４】
【数２２】
2015206941.tif 000024
【００７５】
と定める。 特に(x1,…,xn-m)=(0,…,0)である場合は
【００７６】
【数２３】
2015206941.tif 000025
【００７７】
となる。
【００７８】
なお、Axn=vmを満たすxn=(x1,…,xn)の初期値を後述する[[乱数系列生成装置の具体処理２]]を用いて決定してもよい。このときには、sum-productアルゴリズムの反復回数を少なくして計算時間が小さいが近似精度が悪い乱数系列を用いることが出来る。すなわち、sum-productアルゴリズムを用いた従来手法による乱数の確率分布の近似精度を向上させるために本アルゴリズムを利用できる。言い換えれば、Axn=vmを満たすxn=(x1,…,xn)の初期値を後述する[[乱数系列生成装置の具体処理２]]を用いて決定することにより、ループ処理に要する時間（収束するまでの時間）を短くすることができ、効率良く近似精度の高い乱数を生成することができる。
【００７９】
このようにして、初期値決定部１５は、所定の条件を満たす複数の値の系列の初期値を決定する。
【００８０】
(Step S2) 第一制御部１２は、もしも、最適化すべき目的関数g(xn)がある場合は
【００８１】
【数２４】
2015206941.tif 000026
【００８２】
とする。最適化すべき目的関数がなければこの処理を省略できる。
【００８３】
(Step S3) 第一制御部１２は、k←1とする。
【００８４】
(Step S4) 第一制御部１２は、j∈{1,…,n-m}を等確率で選択する。すなわち、特定のjを選択する確率は1/(n-m)である。
【００８５】
(Step S5) 第三確率分布生成部１３は、以下で定まる確率分布ρ(xj’)を求める。
【００８６】
【数２５】
2015206941.tif 000027
【００８７】
xj’は、複数の値の系列xn≡(x1,x2,…,xn)を構成する１個の値である。上式の右辺の分子
【００８８】
【数２６】
2015206941.tif 000028
【００８９】
は、実現値xj’を用いて更新前の複数の値の系列を更新後も所定の条件を満たすように更新した後の複数の値の系列が第一確率分布pXnに従って出現する確率と言える。上式の右辺の分母は正規化項であるため、ρ(xj’)は、実現値xj’を用いて更新前の複数の値の系列を更新後も所定の条件を満たすように更新した後の複数の値の系列が第一確率分布pXnに従って出現する確率に応じた確率についての確率分布であると言える。この確率分布を、第三確率分布とする。
【００９０】
(Step S6) 系列更新部１４は、第三確率分布ρ(xj’)に従ってxj’を発生させる。各i∈Ijでxn-m+iを
【００９１】
【数２７】
2015206941.tif 000029
【００９２】
と更新し、xjを
【００９３】
【数２８】
2015206941.tif 000030
【００９４】
と更新する。
【００９５】
ここで、更新された系列(x1,…,xn)もまたAxn=vmを満たしている。
【００９６】
このように、系列更新部１４は、第三確率分布ρ(xj’)に従い１個の実現値を生成し、その生成された実現値を用いて複数の値の系列を更新後も上記所定の条件を満たすように更新する。
【００９７】
(Step S7) 第一制御部１２は、もしも、最適化すべき目的関数g(xn)がある場合は更新したxnを用いてg(xn)を計算し、これがgoptよりも最適である場合は
【００９８】
【数２９】
2015206941.tif 000031
【００９９】
とする。最適化すべき目的関数がなければこの処理を省略できる。なお、この処理をk∈[K]を満たすときのみに行うことにより計算時間を削減することが出来る。
【０１００】
(Step S8) 第一制御部１２は、もしもk=Kならばxnを出力して終了する。ここで、最適化すべき目的関数g(xn)がある場合は
【０１０１】
【数３０】
2015206941.tif 000032
【０１０２】
として各i∈{1,…,m}に対して
【０１０３】
【数３１】
2015206941.tif 000033
【０１０４】
を求め、xnを出力して終了する。
【０１０５】
(Step S9) 第一制御部１２は、k←k+1として(Step S4)に戻るように制御を行う。
【０１０６】
このように、第一制御部１２は、第三確率分布生成部１３及び系列更新部１４の処理を繰り返すことにより、第二確率分布に従う乱数の系列を生成させる。
【０１０７】
なお、記憶部１１には確率分布の集合と行列の成分{ai,j}i,jを記録しておく。また、各j∈{1,…,n-m}でIjを求めて記録しておけば、(Step S5)(Step S6)を早く処理することが出来る。
【０１０８】
このアルゴリズムの実行中には、(Step S5)において(6)で定義されたρの分子の計算結果と対応するq 個の実数と、ρの分母の計算結果と対応する1つの実数と、xnを記録するためのn個のGF(q)の値(整数) のためのメモリを必要とするだけである(記憶部１１のメモリはカウントしていない)。最適化すべき目的関数がある場合は更にxoptn-mを記録するための(n-m)個のGF(q)の値(整数)とgoptを記録するための1つの実数を必要とする。
【０１０９】
また、(Step S5)の処理では、ρの分子の計算のための高々q[|Ij|+1]回の実数の積と、ρの分母の計算のためのq回の実数の和を必要とするだけである。
【０１１０】
また、(Step 6)の乱数発生は、[0,1)内の一様ランダムな実数が与えられればO(q)の計算時間(実数の差の計算)との値を積算するためのm個の実数を記録するメモリを必要とするだけである。
【０１１１】
このように、[[乱数系列生成装置の具体処理１]]においては、計算時間とメモリ量を削減して実用的な時間で乱数を発生させることができる。具体的には、w’を行列Aの列重み(１列にある非零成分の個数)の最大値とすると、O(w’q)回の実数の演算に削減できる. また計算にはn+1個の整数(GF(q)の値)とq+1個の実数を記録するためのメモリを必要とするだけである。
【０１１２】
なお、pXnは、条件付き確率分布pXn|Ynであってもよい。すなわち、与えられた条件付き確率分布{pXi|Yi}i=1nに対して
【０１１３】
【数３２】
2015206941.tif 000034
【０１１４】
であるとき、制約条件を満たし、確率分布
【０１１５】
【数３３】
2015206941.tif 000035
【０１１６】
に従う乱数を生成するときには、
【０１１７】
【数３４】
2015206941.tif 000036
【０１１８】
と置き換えて、上記の乱数系列生成装置の具体処理を実行すればよい。
【０１１９】
[[乱数系列生成装置の具体処理２]]
初期値決定部１５は、記憶部１５１、第二制御部１５２、第四確率分布生成部１５３及び乱数生成部１５４を備えている。
【０１２０】
(Step S11) 第二制御部１５２は、I←{1,…,n-m}と定めて初期値とする。
【０１２１】
(Step S12) 第四確率分布生成部１５３は、sum-productアルゴリズムを実行して、各k∈Iで関数
【０１２２】
【数３５】
2015206941.tif 000037
【０１２３】
を求める。
【０１２４】
xkは、複数の値の系列xn≡(x1,x2,…,xn)を構成する１個の値である。上式の右辺の分子
【０１２５】
【数３６】
2015206941.tif 000038
【０１２６】
は、実現値xkが出現したときに次回以降の繰り返し処理で生成される残りの乱数の系列{xj}j∈I＼{k}が第一確率分布pXnに従って出現しかつ所定の条件を満たす確率と言える。上式の右辺の分母は正規化項であるため、fk(xk)は、実現値xkが出現したときに次回以降の繰り返し処理で生成される残りの乱数の系列{xj}j∈I＼{k}が第一確率分布pXnに従って出現しかつ所定の条件を満たす確率に応じた確率についての確率分布であると言える。この確率分布を、第四確率分布とする。
【０１２７】
なお、上式の右辺ではこれまでに記録した{xj}j∈{1,…,n-m}＼Iを代入し、χ(xT(i),vi)が定数となったものを記録しておけば将来の計算を省略できる。
【０１２８】
(Step S13) 乱数生成部１５４が、fk(xk)が最大となるk,xkを求めて記憶部１５１に記録する。すなわち、以下の式により定義されるk,xkを求めて記憶部１５１に記録する。
【０１２９】
【数３７】
2015206941.tif 000039
【０１３０】
このように、乱数生成部１５４は、第四確率分布fk(xk)に従い１個の実現値xkを乱数として生成する。
【０１３１】
(Step S14) 第二制御部１５２は、I←I＼{k}とする。
【０１３２】
(Step S15) 第二制御部１５２が、もしもI=φであれば、これまでに記憶部１５１に記録した変数の値(x1,…,xn-m)から各i∈{1,…,m}に対して
【０１３３】
【数３８】
2015206941.tif 000040
【０１３４】
によって(xn-m+1,…,xn)を求め、これらを連結したxn≡(x1,…,xn)を出力して終了する。この出力されたxn≡(x1,…,xn)は初期値とされる。
【０１３５】
このように、第二制御部１５２は、第四確率分布生成部１５３及び乱数生成部１５４の処理を繰り返すことにより、第二確率分布に従う乱数の系列を生成させ、その生成された乱数の系列を所定の条件を満たす複数の値の系列の初期値とする。
【０１３６】
(Step S16) 第二制御部１５２は、I=φでなければ、ステップ(Step S12)に戻るように制御を行う。
【０１３７】
［第一の符号化装置及び方法］
図５に示すように、符号化装置１００は、乱数系列生成装置１及び記憶部１０１を例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００と復号装置２００は、通信路３００で接続されている。
【０１３８】
あらかじめ、m1×n行列B1と、m2×n行列B2と、ベクトルcm1∈Im[B1]とを符号化装置１００と復号装置２００で共有しておく。すなわち、B1,B2,cm1は、記憶部１０１及び記憶部２０１に予め記録されているとする。記憶部１０１には確率分布pXnが更に記録され、記憶部２０１には確率分布pXn|Ynが更に記録されているとする。
【０１３９】
乱数系列生成装置１は、必要に応じて記憶部４０１からこれらの記録されている情報を読み込み後述する処理を行う。同様に、乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部５０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０１４０】
なお、図示していない最適入力分布計算部が、例えば後述する[[最適量子化点及び条件付き確率分布について]]の欄で述べる方法により確率分布pXnを計算して、記憶部１０１に記録してもよい。
【０１４１】
m≡m1+m2とおき、B1,B2を上下に連結したm×n行列をAとする。
【０１４２】
符号化装置１００は、メッセージbm2∈Im[B2]とあらかじめ定めたcm1∈Im[B1]を連結したm次元列ベクトルvmを求める。そして、
【０１４３】
【数３９】
2015206941.tif 000041
【０１４４】
に従う乱数系列xnを発生させ、これを符号化装置１００の出力として通信路３００に入力する（ステップＢｅ１）。すなわち、符号化装置１００は、乱数系列xnを符号として出力する。
【０１４５】
ここで、[B1],[B2]は
【０１４６】
【数４０】
2015206941.tif 000042
【０１４７】
を満たすようにとる。
【０１４８】
vmは、メッセージbm2とあらかじめ定めたcm1とを連結したm次元列ベクトルであるため、所定の条件Axn=vmは、メッセージbm2及び所定の共有情報cm1と、複数の値の系列xnとの関係を所定の関数Aを用いて表現した条件と言える。
【０１４９】
符号化装置１００による乱数系列xnの生成は、符号化装置１００の乱数系列生成装置１により行われる。
【０１５０】
ここで、最適化すべき関数g(xn)として次の(1)-(4)の何れかを例えば取ることができる。
【０１５１】
(1)関数
【０１５２】
【数４１】
2015206941.tif 000043
【０１５３】
を最大化する。
【０１５４】
(2) pXjがjに依存せず同一の関数pXの場合は
【０１５５】
【数４２】
2015206941.tif 000044
【０１５６】
または
【０１５７】
【数４３】
2015206941.tif 000045
【０１５８】
または
【０１５９】
【数４４】
2015206941.tif 000046
【０１６０】
を最小化する。ここで、
【０１６１】
【数４５】
2015206941.tif 000047
【０１６２】
であり、pY|Xは定常無記憶通信路の遷移確率である。
【０１６３】
(3) pXjがjに依存せず同一の関数pXの場合は
【０１６４】
【数４６】
2015206941.tif 000048
【０１６５】
を最小化する。
【０１６６】
(4) pXjがjに依存せず同一の関数pXで、かつ[X]={0,1}の場合は
【０１６７】
【数４７】
2015206941.tif 000049
【０１６８】
を最小化もしくは最大化する。ここで、Σj=1nxjは整数の和である。
【０１６９】
上記の関数gはいずれも、関数gj’:[Xj]→(-∞,∞),g’’(-∞,∞)→(-∞,∞)を用いて
【０１７０】
【数４８】
2015206941.tif 000050
【０１７１】
と表現できる。
【０１７２】
この場合は次のようにして計算時間を削減できる。以下、この場合の乱数系列生成装置１の処理の例を説明するが、[[乱数系列生成装置の具体処理1]]の欄で説明した内容と同様の部分については重複記載を省略する。すなわち、[[乱数系列生成装置の具体処理1]] の欄で説明した内容と異なる部分を中心に説明する。
【０１７３】
(Step S2)において、第一制御部１２は、変数である実数g’の初期値を次のように定める。
【０１７４】
【数４９】
2015206941.tif 000051
【０１７５】
gopt,xoptn-mの初期値を以下のように計算する。
【０１７６】
【数５０】
2015206941.tif 000052
【０１７７】
とする。
【０１７８】
(Step S4)と(Step S5)との間の(Step S4’)において、第一制御部１２は、実数g’を次のように更新する。(Step S4’)は、図３では破線で示されている。
【０１７９】
【数５１】
2015206941.tif 000053
【０１８０】
(Step S6)と(Step S7)との間の(Step S6’)において、第一制御部１２は、実数g’を次のように更新する。
【０１８１】
【数５２】
2015206941.tif 000054
【０１８２】
(Step S7)において、第一制御部１２は、gを最小化する場合、もしも、
【０１８３】
【数５３】
2015206941.tif 000055
【０１８４】
ならば(gを最大化する場合、もしも、
【０１８５】
【数５４】
2015206941.tif 000056
【０１８６】
ならば)
【０１８７】
【数５５】
2015206941.tif 000057
【０１８８】
とする。なお、この処理をk∈[K]を満たすときのみに行うことにより計算時間を削減することが出来る。
【０１８９】
なお、符号化では、必ずしも関数gの最適化は必要ない。すなわち、(Step S2),(Step S4’),(Step S6’),(Step S7)を省略して、(Step S8)を「もしもk=Kならばxnを出力して終了する」と置き換えることが出来る。これにより性能の劣化とひきかえに計算時間を削減できる。
【０１９０】
また、(Step S7)の処理をk∈[K] を満たす時のみに行う場合、次回の(Step S7)の処理を行うまでの間隔に応じて処理を変更することにより計算時間を小さくすることが出来る。具体的には、次回の(Step S7)の処理を行うまでの間隔が小さいときは(Step S4’), (Step S6’),(Step S7)の実行を行い、その間隔が大きいときは(次回の(Step S7)の処理まで(Step S4’)(Step S6’)の実行を省略して次回の(Step S7)の処理において、g’’(g’)を求める前に、(7)によるg’の計算を行う。
【０１９１】
通信路３００に入力されたxnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路３００の出力yn≡(y1,…,yn)は集合[Yn]の要素である。
【０１９２】
復号装置２００は、乱数系列推定部２０２にて通信路３００の出力ynからxnの推定値
【０１９３】
【数５６】
2015206941.tif 000058
【０１９４】
を求め（ステップＢｄ１）、続いてメッセージ推定部２０３にてβ≡B2ξnを計算することによりメッセージbm2の推定値を得る（ステップＢｄ２）。この推定値を近似するものして、例えば、sum-product アルゴリズムや線形計画法を用いた復号アルゴリズムを利用できる（例えば、参考文献１，２参照）。
【０１９５】
〔参考文献１〕S. M. Aji and R. J. McEliece, “The generalized distributive law”, IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 325-343, Mar. 2000.
【０１９６】
〔参考文献２〕J. Feldman, M.J. Wainwright, and D.R. Karger, “Using linear programming to decode binary linear codes”, IEEE Trans. Inform. Theory, vol. IT-51, no. 3, pp. 954-972, Mar. 2005.
【０１９７】
符号化において、[[乱数系列生成装置の具体処理１]]のみを用いることにより、 高速で少ないメモリ消費で符号化の処理を行うことができる。また、処理を十分な回数繰り返すことにより、発生させた乱数の分布が期待する確率分布に収束するという性質を有しているため、性能を向上させることが出来る。さらに、[[乱数系列生成装置の具体処理１]]と[[乱数系列生成装置の具体処理２]]を組み合わせることにより、性能をさらに向上させることが出来る。
【０１９８】
[[最適入力分布について]]
通信路３００の入力アルファベットを[Z]、出力アルファベットを[Y]とする。これらは連続集合としてもよい。[X]を離散集合として{Q(x)}x∈[X]⊂[Z]を考える。[Z]が離散集合の場合は[X]=[Z]として、Qを恒等写像とすることが出来る。
【０１９９】
通信路３００の条件付き確率分布pY|Zが与えられたとき、最適な[X]上の入力確率分布pXを次のアルゴリズムにより求める。
【０２００】
[X]上の確率分布pXと量子化点の集合{Q(x)}x∈[X]⊂[Z]が与えられたとき、条件付き確率pX|Yを次のように定義する。
【０２０１】
【数５７】
2015206941.tif 000059
【０２０２】
[Y]が無限集合の時は、これを関数として実装する。
【０２０３】
もしもΣx∈[X]pX(x)pY|Z(y|Q(x’))が数値計算の結果0になってしまう場合は、本質的に同じとなる以下の式を用いる。
【０２０４】
【数５８】
2015206941.tif 000060
【０２０５】
[[[最適な[X]上の入力確率分布pXを求める具体的な処理]]]
(Step 1) pXを[X]上の一様分布として初期化する。すなわち各x∈[X]で
【０２０６】
【数５９】
2015206941.tif 000061
【０２０７】
とする。
【０２０８】
(Step 2) 各x∈[X]で
【０２０９】
【数６０】
2015206941.tif 000062
【０２１０】
とする。
【０２１１】
(Step 3) 各x∈[X]でpX(x)を次のように更新する。
【０２１２】
【数６１】
2015206941.tif 000063
【０２１３】
(Step 4) もしも、事前に与えたε>0に対して、任意のx∈[X]で|pX(x)-p’X(x)|≦εを満たすならば終了する。満たさなければ(Step 2)に戻る。
【０２１４】
上記の処理で、定積分の計算には例えば参考文献３にある方法を用いる。
【０２１５】
〔参考文献３〕H. Takahasi, and M. Mori. “Double exponential formulas for numerical integration”, Publications of the Research Institute for Mathematical Sciences vol. 9, no. 3, pp. 721-741, 1973.
【０２１６】
[第二の符号化装置及び方法]
第二の符号化装置及び方法は、歪みを許す情報圧縮に関する。歪みを許す情報圧縮とは、情報源の出力と復号装置の出力の不一致を許す場合の情報圧縮のことである。
【０２１７】
図８に示すように、符号化装置４００は、記憶部４０１、圧縮部４０２及び乱数系列生成装置１を例えば備える。復号装置５００は、記憶部５０１、乱数系列推定部５０２及びメッセージ推定部５０３を例えば備える。
【０２１８】
記憶部４０１には、関数A,Bと、所定の共有情報vmと、確率分布pXn|Ynとが記録されている。必要に応じて最適量子化点Qについての情報も記憶部５０１に記録される。乱数系列生成装置１及び圧縮部４０２は、必要に応じて記憶部４０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０２１９】
記憶部５０１には、関数A,Bと、所定の共有情報vmと、確率分布pXnとが記録されている。乱数系列推定部５０２は、必要に応じて記憶部５０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０２２０】
なお、図示していない最適量子化点計算部及び条件付き確率分布計算部が、例えば後述する[[最適量子化点及び条件付き確率分布について]]の欄で述べる方法により確率分布pXn,pXn|Yn及び最適量子化点Qを計算して、記憶部４０１及び記憶部５０１に記録してもよい。
【０２２１】
符号化装置４００は、情報源出力ynとあらかじめ定めたvm∈ImAに対して確率分布
【０２２２】
【数６２】
2015206941.tif 000064
【０２２３】
に従う乱数系列xnを発生させる（ステップＣｅ１）。
【０２２４】
ここで、Aは、
【０２２５】
【数６３】
2015206941.tif 000065
【０２２６】
を満たすようにとる。
【０２２７】
ここで、所定の条件Axn=vmは、所定の共有情報vmと複数の値の系列xn=(x,…,xn)との関係を所定の第一関数Aを用いて表現した条件と言える。
【０２２８】
また、所定の第一確率分布pXn|Ynは、符号化対象の情報を条件とする条件付き確率である。
【０２２９】
最適化(最小化)すべき関数としてg(xn)を以下のように定義する。
【０２３０】
【数６４】
2015206941.tif 000066
【０２３１】
ここで、nH(X),nEXY[d(X,Y)]は事前に計算することが出来る。また、各x∈[X]でlog(1/pX(x))を事前に計算して記録しておけば、以下ではlog(1/pX(x))をその都度計算する必要はない。
【０２３２】
この場合は次のようにしてg(xn)の計算時間を削減することができる。以下、この場合の乱数系列生成装置１の処理の例を説明するが、[[乱数系列生成装置の具体処理1]]の欄で説明した内容と同様の部分については重複記載を省略する。すなわち、[[乱数系列生成装置の具体処理1]]の欄で説明した内容と異なる部分を中心に説明する。
【０２３３】
(Step S2)において、第一制御部１２は、変数であるΛ,Δの初期値を次のように定める。
【０２３４】
【数６５】
2015206941.tif 000067
【０２３５】
gopt,xoptn-mの初期値を以下のように計算する。
【０２３６】
【数６６】
2015206941.tif 000068
【０２３７】
(Step S4)と(Step S5)との間の(Step S4’)において、第一制御部１２は、Λ,Δを次のように更新する。
【０２３８】
【数６７】
2015206941.tif 000069
【０２３９】
(Step S6)と(Step S7)との間の(Step S6’)において、第一制御部１２は、Λ,Δを次の順で更新する。
【０２４０】
【数６８】
2015206941.tif 000070
【０２４１】
(Step S7)において、第一制御部１２は、g’を次のように定める。
【０２４２】
【数６９】
2015206941.tif 000071
【０２４３】
もしも、
【０２４４】
【数７０】
2015206941.tif 000072
【０２４５】
ならば、
【０２４６】
【数７１】
2015206941.tif 000073
【０２４７】
とする。なお、この処理をk∈[K]を満たすときのみに行うことにより計算時間を削減することが出来る。
【０２４８】
なお、符号化では、必ずしも関数gの最小化は必要ない。すなわち、(Step S2),(Step S4’),(Step S6’),(Step S7)を省略して、(Step S8)を「もしもk=Kならばxnを出力して終了する」と置き換えることが出来る。これにより性能の劣化とひきかえに計算時間を削減できる。
【０２４９】
また、(Step S7)の処理をk∈[K] を満たす時のみに行う場合、次回の(Step S7)の処理を行うまでの間隔に応じて処理を変更することにより計算時間を小さくすることが出来る。具体的には、次回の(Step S7)の処理を行うまでの間隔が小さいときは(Step S4’), (Step S6’)及び(Step S7)で(10)によるg’の計算を行い、その間隔が大きいときは次回の(Step S7)の処理まで(Step S4’)(Step S6’)の実行を省略して次回の(Step S7)の処理において、(10)によるg’の計算の前に、(8)(9)によってΛ,Δの計算を行う。
【０２５０】
圧縮部４０２は、m’×n行列Bを用いた固定長符号を構成する。具体的には、次のような処理を行う。xn=(x1,…,xn)を乱数系列生成装置１が発生させた乱数系列とする。
【０２５１】
圧縮部４０２は、bm’=Bxnを求めて、これを符号として復号装置５００に出力する（ステップＣｅ２）。ここで、行列Bは
【０２５２】
【数７２】
2015206941.tif 000074
【０２５３】
を満たすようにとる。
【０２５４】
このように、圧縮部４０２は、上記生成された乱数の系列xn=(x1,…,xn)及び所定の第二関数Bを用いて符号語を生成する。
【０２５５】
復号装置５００の乱数系列推定部５０２は、符号語bm’とあらかじめ定めたvmからxnの推定値
【０２５６】
【数７３】
2015206941.tif 000075
【０２５７】
を求めて復号装置５００の出力とする（ステップＣｄ１）。この推定値を近似するものして、例えば、sum-product アルゴリズムや線形計画法を用いた復号アルゴリズムを利用できる（例えば、参考文献１，２参照）。
【０２５８】
歪みを許す情報圧縮を伴う符号化において、[[乱数系列生成装置の具体処理１]]のみを用いることにより、高速で少ないメモリ消費で符号化の処理を行うことができる。また、処理を十分な回数繰り返すことにより、発生させた乱数の分布が期待する確率分布に収束するという性質を有しているため、性能を向上させることが出来る。さらに、[[乱数系列生成装置の具体処理１]]と[[乱数系列生成装置の具体処理２]]を組み合わせることにより、性能をさらに向上させることが出来る。
【０２５９】
なお、(x1,…,xn-m)が定まれば、Axn=vmを満たす残りの系列(xn-m+1,…,xn)が唯一定まる場合には、圧縮部４０２は、(x1,…,xn)の中の(x1,…,xn-m)を符号語としてもよい。
【０２６０】
この場合、復号装置５００は、受信した(x1,…,xn-m)から条件式Axn=vmを満たす残りの系列(xn-m+1,…,xn)を求めて復号装置５００の出力とする。特に行列Aの右側正方行列が単位行列である場合は、左側のm×(n-m)行列の成分を用いて、i∈{1,…,m}に対して
【０２６１】
【数７４】
2015206941.tif 000076
【０２６２】
とすることにより(xn-m+1,…,xn)を求めることができる。
【０２６３】
なお、符号化装置４００の圧縮部４０２は、算術符号を用いる参考文献４の方法を利用して可変長符号を構成してもよい。この場合、符号化装置４００は、次のような処理を行う。(x1,…,xn)を乱数系列発生装置１が発生させた乱数の系列とする。
【０２６４】
〔参考文献４〕J. Honda and H. Yamamoto, “Variable length lossy coding using LDPC code”, Proc. 2009 Int. Symp. Inform. Theory, Seoul, Korea, pp. 1973-1977.
【０２６５】
圧縮部４０２は、初期値設定部、確率分布生成部、符号語計算部及び終了判定部を備えているとする。
【０２６６】
(Step 1) 初期設定部は、αk=0,βk=1,k=1に設定する。
【０２６７】
(Step 2) 確率分布生成部は、sum-productアルゴリズムを実行して、関数
【０２６８】
【数７５】
2015206941.tif 000077
【０２６９】
を求める。なお、上式の右辺ではこれまでに使用したx1,…,xk-1を代入し、χ(xT(i),vi)が定数となったものを記録しておけば将来の計算を省略できる。
【０２７０】
(Step 3) 符号語計算部は、xkを算術符号を用いて符号化した理想符号長-log2gk(xk)ビットの符号語系列を記録する。具体的には、区間[αk,βk)を比{gk(xk)}xk∈[X]で分割して、符号語から再生したシンボルxkと対応する区間が[αk+1,βk+1)になるようにαk+1,βk+1を定める。
【０２７１】
(Step 4) 終了判定部は、k=nであれば、[αk+1,βk+1)に含まれる┌-Σj=1nlog2gj(xj)┐bit の2-進小数γを符号語系列として出力して終了する。k<nであれば、これまでに記録した(x1,…,xk)からAxn=vmを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する。もしも唯一定まるのであれば、[αk+1,βk+1)に含まれる┌-Σj=1nlog2gj(xj)┐bit の2-進小数γを符号語系列として出力して終了する。唯一に定まらない場合には、kの値を1増やして(Step 2)に戻る。
【０２７２】
この場合、復号装置５００の乱数系列推定部５０２は、圧縮部４０２が用いた算術符号の符号方法と対応する復号方法を用いて復号する。γを符号語を2-進小数と見たときの[0,1)に含まれている実数とする。
【０２７３】
乱数系列推定部５０２は、初期値設定部、確率分布生成部、再生語計算部及び終了判定部を例えば備えているとする。
【０２７４】
(Step 1) 初期値設定部は、αk=0,βk=1,k=1に設定する。
【０２７５】
(Step 2) 確率分布生成部関数計算部は、sum-product アルゴリズムを実行して、(11)と同一の関数
【０２７６】
【数７６】
2015206941.tif 000078
【０２７７】
を求める。なお、上式の右辺ではこれまでに使用したx1,…,xk-mを代入し、χ(xT(i),vi)が定数となったものを記録しておけば将来の計算を省略できる。
【０２７８】
(Step 3) 再生語計算部が、xkを再生記録する。具体的には、区間[αk,βk)を比{gk(xk)}xk∈[X]で分割して、γを含む区間を[αk+1,βk+1)と定める。そしてこの区間と対応するシンボルxkを記録する。
【０２７９】
(Step 4) 終了判定部が、k=nであれば、これまでに記録した(x1,…,xn)を出力して終了する。k<nであれば、これまでに記録した(x1,…,xk)からAxn=vmを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する。もしも唯一定まるのであれば、そのような(xk+1,…,xn)を求めた後に(x1,…,xn)を出力して終了する。唯一に定まらない場合には、kの値を1増やして(Step 2)に戻る。
【０２８０】
[[最適量子化点及び条件付き確率分布について]]
[Y]≡(-∞,∞)上の確率分布pYが与えられたとき、最適な量子化点と条件付き確率分布を次のアルゴリズムにより求める。
【０２８１】
[X]上の確率分布pXと量子化点の集合{Q(x)}x∈[X]⊂[Y]が与えられたとき、条件付き確率pX|Yを次のように定義する。
【０２８２】
【数７７】
2015206941.tif 000079
【０２８３】
ここで、λはあらかじめ定めた定数である。[Y]が無限集合の時は、これを関数として実装する。
【０２８４】
もしもΣx∈[X]pX(x)exp(-λd(Q(x),y))が数値計算の結果0になってしまう場合は、本質的に同じとなる以下の式を用いる。
【０２８５】
【数７８】
2015206941.tif 000080
【０２８６】
[[[最適量子化点、条件付き確率分布計算装置の具体処理]]]
(Step 1) pXを[X]上の一様分布として初期化する。すなわち各x∈[X]で
【０２８７】
【数７９】
2015206941.tif 000081
【０２８８】
続いて、{Q(x)}x∈[X]を集合[Y]のスカラ量子化点の集合とする。例えば[Y]の有界部分集合を一様に量子化した点を与えることが出来る。
【０２８９】
(Step 2) 各x∈[X]で
【０２９０】
【数８０】
2015206941.tif 000082
【０２９１】
とする。
【０２９２】
(Step 3) 各x∈[X]でpX(x)を次のように更新する。
【０２９３】
【数８１】
2015206941.tif 000083
【０２９４】
(Step 4) 以下で定義された量
【０２９５】
【数８２】
2015206941.tif 000084
【０２９６】
を最小化する量子化点の集合{Q(x)}x∈[X]を求める。例えば、d(Q(x),y)≡[Q(x)-y]2の場合は、各x∈[X]でQ(x)を次のように更新する。
【０２９７】
【数８３】
2015206941.tif 000085
【０２９８】
例えばd(Q(x),y)≡|Q(x)-y|の場合は各x∈[X]でQ(x)は次の式
【０２９９】
【数８４】
2015206941.tif 000086
【０３００】
を満たすように更新する。
【０３０１】
(Step 5) もしも、 事前に与えたε>0に対して、任意のx∈[X]で|pX(x)-p’X(x)|≦εと|Q(x)-Q(x)|≦εを満たすならば終了する。満たさなければ(Step 2)に戻る。
【０３０２】
上記の処理で、定積分の計算には例えば参考文献３にある方法を用いる。
【０３０３】
［変形例等］
上記装置及び方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０３０４】
また、上記装置における処理手段をコンピュータによって実現する場合、上記装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記装置における処理手段がコンピュータ上で実現される。
【０３０５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０３０６】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０３０７】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【０３０８】
１      乱数系列生成装置
１１    記憶部
１２    第一制御部
１３    第三確率分布生成部
１４    系列更新部
１５    初期値決定部
１５１  記憶部
１５２  第二制御部
１５３  第四確率分布生成部
１５４  乱数生成部
１００  符号化装置
１０１  記憶部
２００  復号装置
２０１  記憶部
２０２  乱数系列推定部
２０３  メッセージ推定部
３００  通信路
４００  符号化装置
４０１  記憶部
４０２  圧縮部
５００  復号装置
５０１  記憶部
５０２  乱数系列推定部
【図１】
2015206941.tif 000087
【図２】
2015206941.tif 000088
【図３】
2015206941.tif 000089
【図４】
2015206941.tif 000090
【図５】
2015206941.tif 000091
【図６】
2015206941.tif 000092
【図７】
2015206941.tif 000093
【図８】
2015206941.tif 000094
【図９】
2015206941.tif 000095
【図１０】
2015206941.tif 000096