(57)【要約】【課題】第二確率分布に従う乱数の系列を生成する技術に基づいて情報を符号化する技術を提供する。【解決手段】実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての第三確率の分布である第三確率分布を生成する確率分布生成部の処理と、第三確率分布に従い１つの実現値を乱数として生成する乱数生成部の処理とを繰り返し行う。【選択図】図１
2014109697.tif 000002
【特許請求の範囲】
【請求項１】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が上記所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成部と、上記第三確率分布に従い１つの実現値を乱数として生成する乱数生成部と、上記確率分布生成部及び上記乱数生成部の処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる制御部と、を含む乱数系列生成装置と、
上記生成された乱数の系列及び所定の第二関数を用いて符号語を生成する圧縮部と、を含み、
上記所定の条件は、所定の共有情報と複数の値の系列との関係を所定の第一関数を用いて表現した条件であり、
上記所定の第一確率分布は、符号化対象の情報を条件とする条件付き確率である、
符号化装置。
【請求項２】
請求項１の符号化装置であって、
上記所定の第一関数をAとし、上記所定の第二関数をBとし、関数Aの値域をIm[A]とし、関数Bの値域をIm[B]とし、上記所定の共有情報をa∈Im[A]とし、上記符号語をb∈Im[B]とし、上記複数の値の系列(x1,x2,…,xn)をxn∈[Xn]とし、上記所定の条件をA(xn)=aとし、上記符号化対象の情報をynとし、上記第一確率分布をpXn|ynとして、
上記第二確率分布における各実現値xnについての確率は、次式で定義されるμ(xn)であり、
【数１３３】
2014109697.tif 000135
上記圧縮部は、B(xn)を計算してその計算結果を符号語bとする、
符号化装置。
【請求項３】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が上記所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成ステップと、上記第三確率分布に従い１つの実現値を乱数として生成する乱数生成ステップと、上記確率分布生成ステップ及び上記乱数生成ステップを繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる制御ステップと、を含む乱数系列生成ステップと、
上記生成された乱数の系列及び所定の第二関数を用いて符号語を生成する圧縮ステップと、を含み、
上記所定の条件は、所定の共有情報と複数の値の系列との関係を所定の第一関数を用いて表現した条件であり、
上記所定の第一確率分布は、符号化対象の情報を条件とする条件付き確率である、
符号化方法。
【請求項４】
請求項３の符号化方法であって、
上記所定の第一関数をAとし、上記所定の第二関数をBとし、関数Aの値域をIm[A]とし、関数Bの値域をIm[B]とし、上記所定の共有情報をa∈Im[A]とし、上記符号語をb∈Im[B]とし、上記複数の値の系列(x1,x2,…,xn)をxn∈[Xn]とし、上記所定の条件をA(xn)=aとし、上記符号化対象の情報をynとし、上記第一確率分布をpXn|ynとして、
上記第二確率分布における各実現値xnについての確率は、次式で定義されるμ(xn)であり、
【数１３４】
2014109697.tif 000136
上記圧縮ステップは、B(xn)を計算してその計算結果を符号語bとする、
符号化方法。
【請求項５】
請求項１又は２の符号化装置としてコンピュータを機能させるためのプログラム。
【請求項６】
請求項１又は２の符号化装置としてコンピュータを機能させるためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報を符号化する技術に関する。
【背景技術】
【０００２】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布に従う乱数の系列を生成する技術、及び、この技術に基づいて情報を符号化する技術はこれまで提案されていない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
この発明は、第二確率分布に従う乱数の系列を生成する技術に基づいて情報を符号化する符号化装置、方法、プログラム及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００４】
この発明の一態様による符号化装置は、複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての複数の値の系列である実現値についての確率の分布を第二確率分布として、実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての第三確率の分布である第三確率分布を生成する確率分布生成部と、第三確率分布に従い１つの実現値を乱数として生成する乱数生成部と、確率分布生成部及び乱数生成部の処理を繰り返すことにより、第二確率分布に従う乱数の系列を生成させる制御部と、を含む乱数系列生成装置と、生成された乱数の系列及び所定の第二関数を用いて符号語を生成する圧縮部と、備え、所定の条件は、所定の共有情報と複数の値の系列との関係を所定の第一関数を用いて表現した条件であり、所定の第一確率分布は、符号化対象の情報を条件とする条件付き確率である。
【発明の効果】
【０００５】
第二確率分布に従う乱数の系列を生成する技術に基づいて情報を符号化することができる。
【図面の簡単な説明】
【０００６】
【図１】乱数系列生成装置の例を説明するためのブロック図。
【図２】乱数系列生成装置の他の例を説明するためのブロック図。
【図３】乱数系列生成方法の例を説明するためのフローチャート。
【図４】符号化装置及び復号装置の例を説明するためのブロック図。
【図５】符号化装置及び復号装置の例を説明するためのブロック図。
【図６】符号化方法の例を説明するためのフローチャート。
【図７】復号方法の例を説明するためのフローチャート。
【発明を実施するための形態】
【０００７】
［記法の説明］
まず、記法の説明を行う。Xが確率変数であるとき、Xのとり得る値の集合を[X]と記す。集合Sの大きさ、すなわち集合Sに含まれる要素の数を|S|と記す。差集合をS＼S’と記し、これは集合Sに含まれており、かつ集合S’に含まれていない要素全体からなる集合を表す。
【０００８】
Xn≡(X1,X2,…,Xn)はn次元の確率変数で、その実現値をxn≡(x1,x2,…,xn)と記す。
[Xn]≡[X1]×[X2]×…×[Xn]と記す。確率変数Xと対応する確率分布をpXと記す。なお、pXをp_(X)と記すこともある。
【０００９】
Φは一般には関数を表し、Φ(xn)は関数Φのベクトルxnにおける値を表す。qを素数として、関数Φ:GF(q)n→GF(q)mがq元の有限体GF(q)上ベクトル空間の線形写像の場合、
【００１０】
【数１】
2014109697.tif 000003
【００１１】
のように行列で表記する。このとき、xnは列ベクトル
【００１２】
【数２】
2014109697.tif 000004
【００１３】
となる。この場合はΦ(xn)をΦxnと記す。
【００１４】
変数のとり得る値の集合が有限であることが明示されていないときは、連続値をとることができる。また、和Σをとる変数が連続値である場合にはΣは積分∫となる。
【００１５】
［制約条件を満たす素朴な乱数系列生成法］
関数の集合Φ≡{φs:[Xn]→Vs}s=1lに対してΦ(xn)∈V1×V2×…×Vlを
【００１６】
【数３】
2014109697.tif 000005
【００１７】
と定義する。vl≡(v1,v2,…,vl)及び確率変数Xn≡(X1,X2,…,Xn)の分布pXnが与えられたときに、次式で定義されるμ(xn)を考える。
【００１８】
【数４】
2014109697.tif 000006
【００１９】
所定の条件をΦ(xn)=vlとし、所定の第一確率分布をpXnとすると、実現値xn≡(x1,x2,…,xn)についての確率μ(xn)は、所定の第一確率分布pXnにおいてその実現値xnが出現する確率に応じた確率である。
【００２０】
ここでは、所定の条件Φ（ｘｎ）＝ｖｌを満たす全ての実現値についての確率μ(xn)の分布（第二確率分布）に従ういずれか一つの実現値xnを乱数の系列として発生させる素朴な２つの方法を記述する。
【００２１】
＜方法１＞
まず最初に、Φ(xn)=vlを満たすxnを列挙した集合Ωを求める。続いて、各xn∈Ωについて、関係式
【００２２】
【数５】
2014109697.tif 000007
【００２３】
を用いて(a2)の右辺を計算することにより、確率分布μを求める。最後に、確率分布μに従いxn∈Ωを選択する。
【００２４】
なお、＜方法１＞において、入力はpXn、関数の集合Φ及びベクトルvlであり、出力は乱数xnである。
【００２５】
＜方法２＞
確率分布pXnに従いxn∈[Xn]を選択する。続いて、xnが条件Φ(xn)=vlを満たすかどうかを確認する。これをΦ(xn)=vlを満たすxnが選択されるまで繰り返し、最終的に、この条件を満たすxnを乱数の系列として出力して終了する。
【００２６】
なお、＜方法２＞において、入力はpXn、関数の集合Φ及びベクトルvlであり、出力は乱数xnである。
【００２７】
＜方法１＞では、Φ(xn)=vlを満たすxnを列挙した集合Ωを求める必要があるが、一般に|Ω|はnの増大に伴い指数的に増大するため、集合Ωを求めることが困難となる可能性がある。この事実は(a3)の計算も困難とするため、確率分布μを求めることも困難となる可能性がある。また、仮に、確率分布μが求まったとしても、μに従いxn∈Ωを選択することも困難となる可能性がある。さらに、pXnが事前に固定されている場合は、Ωやμを事前に計算して記憶部に記録することもできるが、この場合は記憶量がnとともに指数的に増大する可能性がある。
【００２８】
＜方法２＞では、Φ(xn)=vlを満たすxnを選択するまで繰り返し乱数を発生させるが、一般にΦ(xn)=vlを満たすxnを選択する確率はnとともに指数的に0に近付くことから、繰り返し回数が指数的に増大する可能性がある。
【００２９】
［乱数系列生成装置及び方法の第一実施形態］
以下では、関数の集合Φ≡{φs:[Xn]→Vs}s=1lとvl≡(v1,v2,…,vl)を与え、Φ(xn)∈V1×V2×…×Vlを(a1)で定義したときに、(a2)の確率分布μに従う乱数の系列xnを発生させる乱数系列生成装置について説明する。
【００３０】
T(s)⊂{1,2,…,n}を関数φs(xn)を計算する際に使用する変数xn≡(x1,x2,…,xn)のインデックスの集合とする。xT(s)をxnからインデックス集合T(s)と対応する部分を取り出した|T(s)|次元のベクトルとする。以下では、関数φs(xn)を計算する際に使用する変数だけに注目して、φs(xn)をφs(xT(s))と記す。例えば、関数φs(xn)を計算するときに使用する変数がx1,x2であるときには、T(s)={1,2},φs(xT(s))≡φs(x1,x2)=φs(xn)を満たしている。
【００３１】
Φ≡{φs:[Xn]→Vs}s=1lより定まるχ(xT(s),vs)を次のように定義する。
【００３２】
【数６】
2014109697.tif 000008
【００３３】
確率分布pXnを次のように分解する。
【００３４】
【数７】
2014109697.tif 000009
【００３５】
ここで、上式の右辺でt=1の時には
【００３６】
【数８】
2014109697.tif 000010
【００３７】
とする。例えば、pXnが無記憶の場合は、
【００３８】
【数９】
2014109697.tif 000011
【００３９】
となり、pXnがδ次Markov性を持つ場合は
【００４０】
【数１０】
2014109697.tif 000012
【００４１】
となる。
乱数系列生成装置１は、図１に示すように、制御部１１、確率分布生成部１２、乱数生成部１３、記憶部１４及び乱数推定部１５を例えば備えている。
【００４２】
(a2)で定義された確率分布μに従う乱数を発生させるために、乱数系列生成装置は次の処理を実行する。以下、Σはその下に書かれている変数の全てのとり得る値に関する和を表すこととする。例えば、Σxtは全てのxt∈[Xt]に関する和である。
【００４３】
制御部１１は、k=1とする（ステップＡ１，図３）。
【００４４】
確率分布生成部１２が、次式により定義される関数fk(xk)を求める（ステップＡ２）。関数fk(xk)は、例えばsum-productアルゴリズムを実行することにより求めることができる。sum-productアルゴリズムについては、後述する。
【００４５】
【数１１】
2014109697.tif 000013
【００４６】
なお、上式の右辺ではこれまでに記録したx1,…,xk-1を代入する。
【００４７】
また、χ(xT(s),vs)が定数となったものを記録しておけば将来の計算を省略できる。例えばT(s)が{1,…,k}である場合には、χ(xT(s),vs)の値はxk+1,…,xnの値によらず0又は1となり定数となる。この場合、定数であるχ(xT(s),vs)を次回以降の繰り返し処理で用いるために記憶部１４に記録する。
【００４８】
x1,…,xk-1を既に生成された乱数の系列とし、今回生成される乱数をxkとし、次回以降生成される残りの乱数の系列をxk+1,…,xnとすると、(a5)の右辺の分子に現れる
【００４９】
【数１２】
2014109697.tif 000014
【００５０】
は、既に生成された乱数の系列x1,…,xt-1を条件としたときに実現値xtが出現する第一確率と言える。
【００５１】
また、(a5)の右辺の分子に現れる
【００５２】
【数１３】
2014109697.tif 000015
【００５３】
は、既に生成された乱数の系列x1,…,xk-1及び今回生成される乱数xkを条件としたときに、次回以降生成される残りの乱数の系列xk+1,…,xnが、所定の条件（この場合、Φ(xn)=vl）を満たす第二確率と言える。
【００５４】
(a5)の分母は正規化項なので、例えば(a5)で表されるfk(xk)は、実現値が上記第一確率と上記第二確率との積に応じた値である確率分布ということができる。
【００５５】
乱数生成部１３が、確率分布fk(xk)に従い乱数xkを発生させ記憶部１４に記録する（ステップＡ３）。
【００５６】
制御部１１は、k=nであるか判定する（ステップＡ４）。
【００５７】
k=nであれば、制御部１１は、これまでに記録した変数の値を連結したxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ５）。
【００５８】
k<nであれば、制御部１１は、これまでに記録した(x1,…,xk)からΦ(xn)=vlを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する（ステップＡ６）。
【００５９】
もし唯一定まるのであれば、乱数推定部１５は(xk+1,…,xn)を求めてxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ７）。なお、唯一定まるかどうかを確認するための基準及びこの場合の(xk+1,…,xn)の求め方の例は、乱数系列生成装置及び方法の第二実施形態で説明する。
【００６０】
唯一に定まらない場合には、制御部１１はkの値を１増やしてステップＡ２に戻る（ステップＡ８）。
【００６１】
このようにして、制御部１１は、確率分布生成部１２及び乱数生成部１３の処理を繰り返すことにより、確率分布μに従う乱数の系列を生成させる。
【００６２】
なお、ステップＡ６及びステップＡ７の処理は行わなくてもよい。例えば、(xk+1,…,xn)が唯一に定まるかどうかを確認する処理に時間がかかるか、この確認をすることができない場合、また唯一定まる(xk+1,…,xn)を求める処理に時間がかかるか、この処理をすることができない場合、この確認処理を省略し、k<nであればkの値を1増やしてステップＡ２に戻る構成としてもよい。この場合、乱数系列生成装置１は、図２に例示するように、乱数推定部１５を備えていなくてもよい。
【００６３】
乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1)}t=1nと関数の集合{χ(xT(s),vs)}s=1lであり、乱数系列生成装置１の出力はxnである。上述のように、記憶部１４には、入力の他にχ(xT(s),vs)が定数となったものを記録しておいてもよい。
【００６４】
ステップＡ２において(a5)を計算する際に、変数(xk,xk+1,…,xn)のなかで注目する変数(上記ではxk)を自由に選択できる。従って、ステップＡ２では全ての変数(xk,xk+1,…,xn)に対して周辺化関数を求めた結果から、後の計算に都合のよい周辺化関数を利用することができる。これは、変数(x1,…,xn)の周辺化を行う順序をステップＡ２で適応的に変えられることを意味する。ここで、注目する変数の順序の変更にともない、(a5)の右辺に現れるp_(Xn|X1t-1)の再計算を必要とする場合があることを注意しておく。ただし、pXnが無記憶、すなわち(a4)を満たすときは、ステップＡ２において(a5)を計算する際に変数(xk,xk+1,…,xn)のなかで注目する変数(上記ではxk)を変えても、注目する変数の順序の変更にともなうp_(Xt|X1t-1)=pXtの再計算の必要はない。
【００６５】
なお、条件式Φxn=vlと等価で、かつsum-productアルゴリズムの計算精度が向上する条件式に変形した後で、制約条件を満たす乱数生成アルゴリズムを適用してもよい。
sum-productの近似精度を上げるために、例えば、集合T(s)の大きさが小さくなるように、また条件式Φｘｎ＝ｖｌと対応するファクターグラフが短いループを持たないように、条件式を変形することなどが考えられる。
【００６６】
なお、ステップＡ２において所望の乱数を発生させるために、参考文献１に記載されている区間アルゴリズムを用いて一様乱数列からxkを求めてもよい。参考文献１では発生させる乱数列は独立同分布であることを仮定しているが、ここではこの仮定が成り立たないので、次のような改良を施す。今、ωを2以上の整数として、十分な長さの一様ω元乱数列r1,r2,…があるとする。この乱数列r1,r2,…は、例えば図１に破線で示した一様乱数生成部１６により生成される。以下では
[ζ,η)≡{θ:ζ≦θ＜η}
とする。
【００６７】
〔参考文献１〕[11] T.S. Han and M. Hoshi, “Interval algorithm for random number generation,” IEEE Trans. Inform. Theory, vol. IT-44, no. 2, pp. 599-611, Mar. 1997.
【００６８】
ステップＡ１において、区間の初期値を[ζ1,η1)≡[0,1)とする。
【００６９】
ステップＡ３において、区間[ζk,ηk)を長さ{fk(x)}x∈[Xk]の部分区間に分割し、長さfk(x)と対応する区間にラベルx∈[Xk]を付ける。そして、ω進小数0.r1r2…を含む区間と対応するラベルをxkとする。ステップＡ２の最後に、先程求めたxkと対応する区間、すなわちω進小数0.r1r2…を含む区間を[ζk+1,ηk+1)とする。
【００７０】
この改良によって、xn=(x1,…,xn)と対応する区間の幅はμ(xn)となるので、(x1,…,xn)と対応する区間に一様乱数より求めたω進小数0.r1r2…が含まれる確率はμ(xn)となる。ここで、アルゴリズムがk=k’で停止した場合は(x1,…,xk’)までしか乱数は発生させないが、k=k’の時点の区間の分割は後述する(a11)と対応しているので、所望の確率分布に従う乱数系列(x1,…,xn)が得られている。
【００７１】
ステップＡ２でsum-product アルゴリズムを適用してO(n)で実行することを仮定し、ステップＡ６及びステップＡ７の計算時間はO(n2)であることを仮定すれば、このアルゴリズムは全体でO(n2)の計算時間で終了する。このため、このアルゴリズムにより、上述の［制約条件を満たす素朴な乱数系列生成法］よりも短い計算時間で乱数系列を生成することができる。
【００７２】
以下では、本アルゴリズムが期待する結果を出力することを証明する。(a5)の右辺の分子に現れる式を
【００７３】
【数１４】
2014109697.tif 000016
【００７４】
とすると、
【００７５】
【数１５】
2014109697.tif 000017
【００７６】
が成り立っている。
【００７７】
xn=(x1,x2,…,xn)を最終的に出力した乱数系列とする。アルゴリズムのステップＡ４においてk=nで終了した場合は、
【００７８】
【数１６】
2014109697.tif 000018
【００７９】
となる。一方で、 アルゴリズムのステップＡ６及びステップＡ７でk=k’<nで終了した場合は、(x1,x2,…,xk’)からΦ(xn)=vlを満たす残りの変数の値(xk’+1,…,xn)が唯一定まることから、
【００８０】
【数１７】
2014109697.tif 000019
【００８１】
となる。(a8)は(a7)をk’=nの場合として含んでいるので、以下、k=k’で終了した場合を考える。
【００８２】
(a6)よりk≧2の時は
【００８３】
【数１８】
2014109697.tif 000020
【００８４】
が成り立つ。また、k=1の時は
【００８５】
【数１９】
2014109697.tif 000021
【００８６】
が成り立つ。(a8),(a9),(a10)より最終的にxnを出力する確率は
【００８７】
【数２０】
2014109697.tif 000022
【００８８】
となる。したがって、このアルゴリズムは、確率分布(a2)に従う乱数列xnを出力する。
【００８９】
＜sum-productアルゴリズムについて＞
一般的にsum-productアルゴリズムとは、変数ベクトルxnの一部からなる変数ベクトルxT(s)で定まる関数es(xT(s))が各s∈Sで与えられたとき、周辺化関数
【００９０】
【数２１】
2014109697.tif 000023
【００９１】
を求める手続きである。ここで、N≡{1,2,…,n}として、各s∈SでT(s)⊂Nである。また
Σxn＼{xt}は、ベクトルxnに現れる変数xt以外の全てのxnの値を動かした時の総和である。また、(a12)で定めたg(xt)ではなく、右辺の分子に現れた
【００９２】
【数２２】
2014109697.tif 000024
【００９３】
を求める手続きとしてsum-productアルゴリズムが記述される場合があるが、以下では、(a12)で定めたg(xt)を求める手続きをsum-productアルゴリズムと呼ぶことにする。
【００９４】
以下にsum-productアルゴリズムを記述する。メッセージと呼ばれる関数πxt→es(xt),σes→xt(xt)を次のように定義する。
【００９５】
【数２３】
2014109697.tif 000025
【００９６】
ここで、Σx_(T(s)＼{t})は全ての{xt’}t’∈T(s)＼{t}を動かした時の総和であり、Σx_(T(s))は全ての{xt}t∈T(s)を動かした時の総和を表す。また、T(s)={t}の時は
【００９７】
【数２４】
2014109697.tif 000026
【００９８】
と定め、xt∈T(s’)を満たすs’∈S＼{s}が存在しないときは
【００９９】
【数２５】
2014109697.tif 000027
【０１００】
と定める。
以下、sum-product アルゴリズムの具体処理について説明する。
Step 1 T(s)={t}を満たすt∈N,s∈Sに対して
【０１０１】
【数２６】
2014109697.tif 000028
【０１０２】
と初期化する。
Step 2 xt∈T(s’)を満たすs’∈S＼{s}が存在しないようなt∈N,s∈Sに対して
【０１０３】
【数２７】
2014109697.tif 000029
【０１０４】
と初期化する。
Step 3 t∈T(s)を満たすt∈N,s∈Sに対して、πxt→es(xt)をStep 2 で初期化しなかったならば、これに適当な初期値を設定する。例えば、xtのとり得る値の集合が[Xt]であれば、
【０１０５】
【数２８】
2014109697.tif 000030
【０１０６】
とする。
Step 4 t∈T(s)を満たしているような全てのt∈N,s∈Sに対して(a13)によって
σes→xt(xt)を求める。ここで、Step 1で初期化したs,tの組合せについてはσes→xt(xt)の計算を省略する。
Step 5 t∈T(s)を満たしているような全てのt∈N,s∈Sに対して(a14)によってπxt→es(xt)を求める。ここで、Step 2で初期化したs,tの組合せについてはπxt→es(xt)の計算を省略する。
Step 6 Step 4とStep 5を予め定めた繰り返し回数繰り返した後、以下の関数を求めて終了する。
【０１０７】
【数２９】
2014109697.tif 000031
【０１０８】
なお、制約を満たす乱数生成アルゴリズムにsum-productアルゴリズムを用いる場合、(a5)において
【０１０９】
【数３０】
2014109697.tif 000032
【０１１０】
を{es}s∈Sとみなして適用する。sum-productアルゴリズムの実行後に得られた(a15)の右辺がfk(xk)の近似式となる。
【０１１１】
［乱数系列生成装置及び方法の第二実施形態］
乱数系列生成装置及び方法の第二実施形態は、関数が線形性を持つときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１１２】
以下では、[X1]=[X2]=…=[Xn]=[V1]=[V2]=…=[Vl]=GF(q)を仮定し、l≦nとして、フルランクのl×n行列
【０１１３】
【数３１】
2014109697.tif 000033
【０１１４】
を考える。関数φs:[Xn]→Vsを
【０１１５】
【数３２】
2014109697.tif 000034
【０１１６】
と定義する。上式の右辺は行列Φのｓ行目のｎ次元ベクトル（φs,1, φs,2,...,φs,n）とxn≡(x1,x2,…,xn)∈[Xn]の内積である。
【０１１７】
上記のように定義されたΦ≡{φs}s=1lとベクトル
【０１１８】
【数３３】
2014109697.tif 000035
【０１１９】
に対して、確率分布(a2)で定まる分布を発生させる乱数系列生成装置１の具体処理を記述する。
【０１２０】
ここで、Φとｖｌは与えられた行列とベクトルそのままを利用しても良いが、Φとｖｌを連結した以下の行列
【０１２１】
【数３４】
2014109697.tif 000036
【０１２２】
に対して行基本変形を施した結果
【０１２３】
【数３５】
2014109697.tif 000037
【０１２４】
の左側l×n行列Φ´と右側l×1行列（l次元ベクトル）ｖ´ｌを、それぞれΦおよびｖｌとして代用しても良い。例えば、行列Φ´の０となる成分が多く、Φ´とｘnとｖ´lから定まるファクターグラフが短いループを持たないようなΦ´とｖ´lを用いることにより、sum-product アルゴリズムによる近似精度が向上する場合があるので、本願発明の乱数系列生成装置が出力する乱数の確率分布の精度をより向上させることができる。
【０１２５】
以下、Φをフルランクの行列として、行列Φの右側のl×l行列Ψ2が正則行列であると仮定しても一般性は失われない。実際に、任意の行列Φとベクトルvlから冗長な条件式を構成するΦの行とvlの成分を取り除いた行列を求め、この行列の行ベクトルと変数(x1,x2,…,xn)の順序を適切に並びかえることにより所望の行列を求めることができる。
【０１２６】
行列Φの左側のl×(n-l)行列をΨ1とすると、上記の仮定から、xn-l≡(x1,…,xn-l)を決定すれば
(xn-l+1,…,xn)≡Ψ2-1(vl-Ψ1xn-l)
によってΦxn=vlを満たす残りの変数(xn-l+1,…,xn)を求めることができる。ここで、Ψ2-1はΨ2の逆行列を表し、アルゴリズムの実行前に求めることができる。
【０１２７】
T(s,k)⊂{k,…,n}を行列Φに現れるベクトル(φs,k,…,φs,n)の中で、φs,t≠0を満たすインデックスsの集合とする。すなわち、T(s,k)は以下のように定義される。
T(s,k)≡{t∈{k,…,n}:φs,t≠0}
【０１２８】
ここで、χ(xT(s,k),vs(k))を次のように定義する。
【０１２９】
【数３６】
2014109697.tif 000038
【０１３０】
以上の設定により、乱数系列生成装置１の具体処理を以下のように変更することができる。
【０１３１】
制御部１１は、k=1とする。各s∈{1,…,l}でvs(k)=vsとする。
【０１３２】
確率分布生成部１２は、次式により定義される関数fk(xk)を求める（ステップＡ２）。関数fk(xk)は、例えばsum-productアルゴリズムを実行することにより求めることができる。
【０１３３】
【数３７】
2014109697.tif 000039
【０１３４】
乱数生成部１３が、確率分布fk(xk)でxkを発生させ、記憶部に記録する（ステップＡ３）。
【０１３５】
制御部１１は、k=nであるか判定する（ステップＡ４）。
【０１３６】
k=nであれば、制御部１１は、これまでに記録した変数の値を連結したxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ５）。
【０１３７】
k<nであれば、制御部１１は、これまでに記録した(x1,…,xk)からΦxn=vlを満たす残りの変数の値(xk+1,…,xn)が唯一に定まるかどうかを確認する。この例では、制御部１１はk=lであるか判定する（ステップＡ６）。
【０１３８】
k=lであれば、乱数推定部１５は、残りの変数の値(xl+1,…,xn)≡Ψ2-1vl(k+1)を求めて記録し、これまでに記録したxn≡(x1,x2,…,xn)を出力して終了する（ステップＡ７）。
【０１３９】
k<lであれば、制御部１１はkの値を1増やして、ステップＡ２に戻る（ステップＡ８）。なお、ステップＡ２に戻る際に、vl(k+1)≡(v1(k+1),…,vl(k+1))を各s∈{1,…,l}で
vs(k+1)≡vs(k)-φs,kxk
とする。
【０１４０】
なお、上記の具体処理において、ステップＡ４とステップＡ５の処理を省略して、ステップＡ３から直ちにステップＡ６に進んでもよい。あるいは、ステップＡ７において、Ψ2-1vl(k+1)の計算に時間がかかる場合は、ステップＡ６とステップＡ７の処理を省略して、ステップＡ４から直ちにステップＡ８に進んでもよい。
【０１４１】
第二実施形態の乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1)}t=1nと行列Φであり、出力はxnである。記憶部１４には入力とGF(q)の計算に必要な情報qの他に、ΦからΨ2-1を求めて記録しておくことができる。(xT(s,k),vs(k))はkとともにΦを用いて更新される。
【０１４２】
［乱数系列生成装置及び方法の第三実施形態］
乱数系列生成装置及び方法の第三実施形態は、pXnが条件付き確率分布のときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１４３】
条件付き確率分布p_(Xn|Un)が与えられたとき、制約条件を満たし、
【０１４４】
【数３８】
2014109697.tif 000040
【０１４５】
に従う乱数を生成するときには、
【０１４６】
【数３９】
2014109697.tif 000041
【０１４７】
と置き換えて乱数系列生成装置の具体処理を実行する。すなわち、例えば(a5)は、次式のようになる。
【０１４８】
【数４０】
2014109697.tif 000042
【０１４９】
第三実施形態の乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1Un)}t=1n、関数の集合Φ,vl,unであり、出力はxnである。
【０１５０】
記憶部１４には入力の他に
【０１５１】
【数４１】
2014109697.tif 000043
【０１５２】
を計算するために必要な情報を保持しておき、確率分布の計算に利用する。
【０１５３】
なお、上記同様にして、乱数系列生成装置及び方法の第二実施形態においてもpXnが条件付き確率分布であってもよい。
【０１５４】
［歪みを許す情報圧縮に関する実施形態についての注意］
歪みを許す情報圧縮に関する実施形態である［歪みを許す情報圧縮についての符号化装置及び方法並びに復号装置及び方法に関する実施形態］の説明の前に、この［歪みを許す情報圧縮についての符号化装置及び方法並びに復号装置及び方法に関する実施形態］についての注意を述べる。
【０１５５】
歪みを許す情報圧縮とは、情報源の出力と復号装置の出力の不一致を許す場合の情報圧縮のことである。
【０１５６】
以下では、対数の底を例えば2等などに統一する。
A,Bは一般には関数を表し、A(xn)、B(xn)はそれぞれ関数A、Bのベクトルxnにおける値を表す。関数A、Bの値域をそれぞれImA≡{A(xn):xn∈[Xn]}、ImB≡{B(xn):xn∈[Xn]}と記す。
【０１５７】
以下の実施形態では[Xn]を定義域とする関数の集合[A],[B]を考える。そして、Im[A],Im[B]を次のようにする。
【０１５８】
【数４２】
2014109697.tif 000044
【０１５９】
[A],[B]は条件式を記述するためだけに使用し、符号化では関数A,Bをそれぞれ[A],[B]から１つずつ選ぶ。また、[Xn],ImA,ImB,Im[A],Im[B]が線形空間であってもなくてもよい。変数xnと関数A,Bによって定まるファクターグラフが疎な構造を持つ場合、特に関数A,Bが疎行列によって表現されている場合は、sum-productアルゴリズムによる近似性能を向上させることができる。さらに、復号の構成においても例えば参考文献２，３に記載されている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.
〔参考文献３〕F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498-519, Feb. 2001.
〔参考文献４〕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.
〔参考文献５〕T. Wadayama, “An LP decoding algorithm based on primal path-following interior point method,” Proc.2009, Int. Symp. Inform. Theory, Seoul, Korea, pp. 389-393, 2009.
【０１６１】
[Xn]が有限体GF(q)上のn次元ベクトル空間であり、符号化に用いる関数A,Bが有限体GF(q)の要素を値とする行列である場合は、[A]をm×n行列全体からなる集合、[B]をm’×n行列全体からなる集合とすることにより、
【０１６２】
【数４３】
2014109697.tif 000045
【０１６３】
となるので、後に登場するlog|Im[A]|,log|Im[B]|に関する条件式をq,n,m,m’に関する条件式に変換することができる。そして、aはm次元のベクトル、bはm’次元のベクトルとなる。
【０１６４】
確率変数XnのエントロピーYnが与えられた時のXnの条件付きエントロピーを以下のように定義する。
【０１６５】
【数４４】
2014109697.tif 000046
【０１６６】
制約条件を満たす乱数系列生成法を適用するとき、条件付き確率分布を用いて定まる制約条件を満たす乱数を必要とする場合は、［乱数系列生成装置及び方法の第一実施形態］から［乱数系列生成装置及び方法の第三実施形態］で説明した方法を適用すればよい。
【０１６７】
関数が記録されているとは、関数を計算する手段が記録されていることを意味する。関数が線形性を持つ場合は、その係数を行列の形で記録しておけばよい。確率分布が記録されているとは、実現値の確率を計算する手段が記録されていることを意味する。関数を計算する手段及び実現値の確率を計算する手段は、後述のように例えばプログラムにより実装される。例えばGauss分布等のパラメトライズされた連続分布や定常無記憶性やマルコフ性を仮定すれば、少ない容量で確率を計算する手段を記録することができる。制約付き乱数生成アルゴリズムを利用する場合は、fk(xk)を計算するために必要な情報と置き換えることができる。
【０１６８】
以下、歪みを許す情報圧縮に関する実施形態におけるデータの大まかな流れを説明する。
【０１６９】
情報源の出力yn≡(y1,y2,…,yn)は集合[Yn]の要素であり、情報源からはynが出力されている。ここで扱う圧縮はブロック符号であり、ynを１つのブロックとして符号化を行う。集合[Yn]は、有限集合とは限らないとする。
【０１７０】
所定の共有情報であるaは集合Im[A]の要素であり、Aがm×n行列である場合はaはm次元のベクトルとなる。符号化装置は情報源出力ynとaから圧縮されたデータである符号語bを求め、誤りのない通信路を用いて送信、あるいはメモリ等に保存する。ここで、bはIm[B]の要素であり、Bがm’×n行列である場合はm’次元のベクトルとなる。なお、符号化の途中で計算されるxnは有限集合[Xn]の要素である。
【０１７１】
復号装置はbとaからξnを求める。ここで、ξnは有限集合[Xn]の要素である。ただし、復号装置が補助情報の出力unを観測する場合は、復号装置はbとaとunからwnを求める。unは[Un]の要素であり、ξnは[Xn]の要素であり、wnは[Wn]の要素である。un及びwnは、有限集合とは限らないとする。
【０１７２】
［歪みを許す情報圧縮についての符号化装置及び方法並びに復号装置及び方法に関する実施形態］
＜復号装置がunを観測しない場合＞
以下では、図４を参照して、復号装置２００が情報源の出力ynと相関のある情報源の出力unを観測しない場合の構成を述べる。
【０１７３】
図４に示すように、符号化装置１００は、乱数系列生成装置１、記憶部１０１及び圧縮部１０３を例えば備える。復号装置２００は、記憶部２０１及び乱数系列推定部２０２を例えば備える。
【０１７４】
記憶部１０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Ynとが記録されている。乱数系列生成装置１及び圧縮部１０３は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０１７５】
記憶部２０１には、関数A,Bと、所定の共有情報aと、確率分布pXnとが記録されている。乱数系列推定部２０２は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０１７６】
ここで、[A],[B]は、以下の関係を満たすように設定しておく。
【０１７７】
【数４５】
2014109697.tif 000047
【０１７８】
xn∈[Xn],yn∈[Yn]とする。歪み尺度をdn:[Xn]×[Yn]→[0,∞)とする。情報源を特徴づける確率分布をpYnとする。条件付き確率分布pXn|Ynは設計パラメータであり任意に与えることができるが、(H(Xn)-H(Xn|Yn))と以下に定義される平均歪みEXnYn[dn(xn,yn)]が小さいパラメータを選択する。
【０１７９】
【数４６】
2014109697.tif 000048
【０１８０】
また、pXn(xn)を以下のように定義する。
【０１８１】
【数４７】
2014109697.tif 000049
【０１８２】
符号化装置１００の乱数系列生成装置１に情報源の出力ynが入力される。
【０１８３】
乱数系列生成装置１は、情報源の出力ynと所定の共有情報a∈Im[A]に対して、以下の確率分布μに従う乱数の系列xnを発生させる（ステップＣｅ１，図６）。乱数の系列xnは、圧縮部１０３に送信される。
【０１８４】
【数４８】
2014109697.tif 000050
【０１８５】
乱数系列生成装置１は、［乱数系列生成装置及び方法の第三実施形態］で説明した方法を適用することにより、乱数の系列xnを生成することができる。ここで、ステップＣｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxnとしてもよい。
【０１８６】
圧縮部１０３は、乱数の系列xn及び所定の第二関数Bを用いて符号語bを生成する（ステップＣｅ３）。圧縮部１０３は、具体的には、b≡B(xn)を符号語として出力する。すなわち、B(xn)を計算してその計算結果を符号語bとする。
【０１８７】
符号化装置１００の出力である符号語bは、復号装置２００の乱数系列推定部２０２に入力される。
【０１８８】
乱数系列推定部２０２は、符号語bと所定の共有情報aから、次式により定義される、xnの推定値ξnを求める（ステップＣｄ１，図７）。 ここで、(c1)を求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξnを近似的に求めてもよい。
【０１８９】
【数４９】
2014109697.tif 000051
【０１９０】
以下、具体的な例を記述する。関数Aをm×n行列、関数Bをm’×n行列として、以下のように表記する。
【０１９１】
【数５０】
2014109697.tif 000052
【０１９２】
ここで行列A,Bがフルランクであることを仮定する。m次元ベクトルaを以下のように表記する。
【０１９３】
【数５１】
2014109697.tif 000053
【０１９４】
関数Φを以下のようにm×n行列とし、l≡mとしてベクトルvlを以下のようにする。
【０１９５】
【数５２】
2014109697.tif 000054
【０１９６】
Φは行列Aと同じであり、vlはベクトルaと同じである。圧縮したい系列ynに対して、Un≡Yn,un≡ynとおいて、符号化装置１００は［乱数系列生成装置及び方法の第三実施形態］で説明した方法により分布μで発生させた乱数xn
【０１９７】
【数５３】
2014109697.tif 000055
【０１９８】
を求め、以下のm’次元のベクトルbを圧縮後の系列である符号語bとする。
【０１９９】
【数５４】
2014109697.tif 000056
【０２００】
ここで、条件式Φ(θn)=vlは、以下のようになる。
【０２０１】
【数５５】
2014109697.tif 000057
【０２０２】
復号装置１００は圧縮系列である符号語bから(c1)によってxnの推定値ξnを求める。
【０２０３】
【数５６】
2014109697.tif 000058
【０２０４】
ここで、条件式A(θn)=aは、以下のようになる。
【０２０５】
【数５７】
2014109697.tif 000059
【０２０６】
また、条件式B(θn)=bは、以下のようになる。
【０２０７】
【数５８】
2014109697.tif 000060
【０２０８】
以下、他の具体的な例を記述する。
【０２０９】
q=2,n=7として、[Xn]≡GF(2)7,[Yn]≡GF(2)7とする。dn(xn,yn)を次のように定める。
【０２１０】
【数５９】
2014109697.tif 000061
【０２１１】
情報源の確率分布を次のように仮定する。
【０２１２】
【数６０】
2014109697.tif 000062
【０２１３】
ここで、ηは0以上1以下の実数である。条件付き確率分布を次のように定める。
【０２１４】
【数６１】
2014109697.tif 000063
【０２１５】
ここで、ζ0,ζ1は0以上1以下の実数である。このとき、以下の式が満たされる。
【０２１６】
【数６２】
2014109697.tif 000064
【０２１７】
確率分布p_(Xt|X1t-1Yn)は以下で与えられる。
【０２１８】
【数６３】
2014109697.tif 000065
【０２１９】
確率分布pXnは以下のようなる。
【０２２０】
【数６４】
2014109697.tif 000066
【０２２１】
η=3/7,ζ0=1/7,ζ1=5/7とすると、次のようになる。
【０２２２】
【数６５】
2014109697.tif 000067
【０２２３】
関数A,Bを行列として、列数をそれぞれm=4,m’=2とすると、以下の式を満たしている。ここで、対数の底を2とした。
【０２２４】
【数６６】
2014109697.tif 000068
【０２２５】
4×7行列A、2×7行列Bを以下のように定める。
【０２２６】
【数６７】
2014109697.tif 000069
【０２２７】
4次元ベクトルaを以下のように設定する。
【０２２８】
【数６８】
2014109697.tif 000070
【０２２９】
これから圧縮対象となる以下の7次元のベクトルynを符号化する。
【０２３０】
【数６９】
2014109697.tif 000071
【０２３１】
Φ=Aとする。すなわち、Φは以下のように設定されているとする。
【０２３２】
【数７０】
2014109697.tif 000072
【０２３３】
また、l≡m=4としてベクトルvl=aとする。すなわち、vlは以下のように設定されているとする。
【０２３４】
【数７１】
2014109697.tif 000073
【０２３５】
［乱数系列生成装置及び方法の第二実施形態］に従って乱数を発生するにあたり、Ψ1,Ψ2を次のように定める。
【０２３６】
【数７２】
2014109697.tif 000074
【０２３７】
Ψ2は正則行列であるので、逆行列Ψ2-1は以下のようになる。
【０２３８】
【数７３】
2014109697.tif 000075
【０２３９】
ここで、［乱数系列生成装置及び方法の第二実施形態］の具体処理を行う。
【０２４０】
1. Step A1において、k=1に設定する。vs(1)は次のようになる。
【０２４１】
【数７４】
2014109697.tif 000076
【０２４２】
2. Step A2 においてT(s,1),χ(xT(s,1),vs(1))は次のようになる。
【０２４３】
【数７５】
2014109697.tif 000077
【０２４４】
関数
【０２４５】
【数７６】
2014109697.tif 000078
【０２４６】
を計算することにより、
【０２４７】
【数７７】
2014109697.tif 000079
【０２４８】
を得る。なお、この例ではsum-product法は使用していない。
【０２４９】
3. Step A3 において確率分布
【０２５０】
【数７８】
2014109697.tif 000080
【０２５１】
で乱数0又は1を発生させる。以下、0を発生させたと仮定し、x1=0とする。
【０２５２】
4. k=2とする。vs(2)は次のようになる。
【０２５３】
【数７９】
2014109697.tif 000081
【０２５４】
そして、Step A2に戻る。
【０２５５】
5. Step A2 においてT(s,2),χ(xT(s,2),vs(2))は次のようになる。
【０２５６】
【数８０】
2014109697.tif 000082
【０２５７】
関数
【０２５８】
【数８１】
2014109697.tif 000083
【０２５９】
を計算することにより、
【０２６０】
【数８２】
2014109697.tif 000084
【０２６１】
を得る。なお、この例ではsum-product法は使用していない。
【０２６２】
6. Step A3において確率分布
【０２６３】
【数８３】
2014109697.tif 000085
【０２６４】
で乱数0又は1を発生させる。以下、1を発生させたと仮定し、x2=1とする。
【０２６５】
7. Step A4においてk=3とする。vs(3)は次のようになる。
【０２６６】
【数８４】
2014109697.tif 000086
【０２６７】
そして、Step A2に戻る。
【０２６８】
8. Step A2 においてT(s,3),χ(xT(s,3),vs(3))は次のようになる。
【０２６９】
【数８５】
2014109697.tif 000087
【０２７０】
関数
【０２７１】
【数８６】
2014109697.tif 000088
【０２７２】
を計算することにより、
【０２７３】
【数８７】
2014109697.tif 000089
【０２７４】
を得る。なお、この例ではsum-product法は使用していない。
【０２７５】
9. Step A3において確率分布
【０２７６】
【数８８】
2014109697.tif 000090
【０２７７】
で乱数0又は1を発生させる。以下、0を発生させたと仮定し、x3=0とする。
【０２７８】
10. ここで、vs(4)は次のようになる。
【０２７９】
【数８９】
2014109697.tif 000091
【０２８０】
ここで、(x4,x5,x6,x7)を求めると、以下のようになる。
【０２８１】
【数９０】
2014109697.tif 000092
【０２８２】
乱数発生装置はxn=(0,1,0,0,0,1,0)を出力して終了する。
【０２８３】
符号化装置は乱数発生装置の出力xn=(0,1,0,0,0,1,0)から符号語bを得る。
【０２８４】
【数９１】
2014109697.tif 000093
【０２８５】
符号語b=(1,0)を受信した復号装置は最初にxnの推定値
【０２８６】
【数９２】
2014109697.tif 000094
【０２８７】
を求めた結果、xnの推定値
【０２８８】
【数９３】
2014109697.tif 000095
【０２８９】
を得る。
なお、圧縮部１０３では関数Bを用いる代わりに、算術符号を用いる参考文献６に記載された方法を利用して可変長符号を構成してもよい。具体的には、制約条件を満たす乱数系列生成アルゴリズムのステップＡ３において、発生させたxkに
【０２９０】
【数９４】
2014109697.tif 000096
【０２９１】
の理想符号長が割り当てられるような算術符号による符号語を求めて、アルゴリズムが終了した時点で求めた符号語を出力する。復号装置は、符号化装置が用いた算術符号の符号化装置と対応する復号装置を用いて復号する。ここで、(c2)は、sum-productアルゴリズムを用いて計算することができる。なお、乱数の系列xnを発生させるために使用する確率分布はpXn|Ynであり、符号語を得るために用いる確率分布はpXnであることを注意しておく。復号装置は、(c2)を順次求め、符号語から(c2)の理想符号長を持つxkを求めることにより、xnを誤り無く再生できる。アルゴリズムがk<nで停止した場合には、(x1,…,xk)よりA(xn)= aを満たす残りの変数(xk+1,…,xn)が唯一定まるので、(xk+1,…,xn)と対応する符号語は必要無いことを注意しておく。提案法と参考文献６に記載された方法の違いは、参考文献６に記載された方法では歪んだ系列をsum-product法や線形計画法を用いて求めてから算術符号アルゴリズムを適用するのに対して、提案法ではランダムに発生させた乱数xnに対して算術符号アルゴリズムを適用する点にある。
〔参考文献６〕J. Honda and H. Yamamoto, “Variable length lossy coding using LDPC code,” Proc. 2009 Int. Symp. Inform. Theory, Seoul, Korea, pp. 1973-1977.
【０２９２】
この場合、記憶部１０１には、関数Aと、所定の共有情報aと、確率分布pXn|yn,pXn|ynとが記録されている。乱数系列生成装置１及び圧縮部１０３は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。符号化装置１００の入力はynであり、符号化装置１００の出力はbである。
【０２９３】
記憶部２０１には、関数Bと、所定の共有情報aと、確率分布pXnとが記録されている。乱数系列推定部２０２は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。復号装置２００の入力はbであり、復号装置２００の出力はξnである。
【０２９４】
＜復号装置がunを観測する場合＞
以下では、復号装置２００が情報源の出力ynと相関のある情報源の出力unを観測できる場合の構成を述べる。
【０２９５】
図４に示すように、符号化装置１００は、乱数系列生成装置１、記憶部１０１及び圧縮部１０３を例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及び変換フィルタ部２０４を例えば備える。
【０２９６】
記憶部１０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Ynとが記録されている。乱数系列生成装置１及び圧縮部１０３は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０２９７】
記憶部２０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Un,pWn|XnUnとが記録されている。乱数系列推定部２０２及び変換フィルタ部２０４は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０２９８】
ここで、[A],[B]は、以下の関係を満たすように設定しておく。
【０２９９】
【数９５】
2014109697.tif 000097
【０３００】
un∈[Un],wn∈[Wn],xn∈[Xn],yn∈[Yn]とする。歪み尺度をdn:[Wn]×[Yn]→[0,∞)とする。情報源を特徴づける確率分布をpYnUnとする。条件付き確率分布pXn|Yn,pWn|XnUnは設計パラメータであり任意に与えることができるが、(H(Xn|Un)-H(Xn|Yn))と以下に定義される平均歪みEWnYn[dn(wn,yn)]が小さいパラメータを選択する。
【０３０１】
【数９６】
2014109697.tif 000098
【０３０２】
また、pXn|Un(xn|un)を以下のように定義する。
【０３０３】
【数９７】
2014109697.tif 000099
【０３０４】
符号化装置１００の乱数系列生成装置１に情報源の出力ynが入力される。
【０３０５】
乱数系列生成装置１は、情報源の出力ynと所定の共有情報a∈Im[A]に対して、以下の確率分布μに従う乱数の系列xnを発生させる（ステップＣｅ１，図６）。乱数の系列xnは、圧縮部１０３に送信される。
【０３０６】
【数９８】
2014109697.tif 000100
【０３０７】
乱数系列生成装置１は、［乱数系列生成装置及び方法の第三実施形態］で説明した方法を適用することにより、乱数の系列xnを生成することができる。ここで、ステップＣｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxnとしてもよい。
【０３０８】
圧縮部１０３は、乱数の系列xn及び所定の第二関数Bを用いて符号語bを生成する（ステップＣｅ３）。圧縮部１０３は、具体的には、b≡B(xn)を符号語として出力する。すなわち、B(xn)を計算してその計算結果を符号語bとする。
【０３０９】
符号化装置１００の出力である符号語bは、復号装置２００の乱数系列推定部２０２に入力される。
【０３１０】
乱数系列推定部２０２は、符号語bと、情報源の出力unと、所定の共有情報aとから、次式により定義される、xnの推定値ξnを求める（ステップＣｄ１，図７）。ξnは、変換フィルタ部２０４に送信される。
【０３１１】
【数９９】
2014109697.tif 000101
【０３１２】
なお、上記式によりξnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξnを近似的に求めてもよい。
【０３１３】
変換フィルタ部２０４は、分布pWn|XnUnに従う、ランダム又は決定的な変換Fを通して得られた系列wn≡F(ξn,un)を復号装置２００の出力とする。
【０３１４】
参考文献７に記載されている従来技術による従来技術では、ブロック長nが大きくなると計算時間が指数関数的に増加する可能性があった。
【０３１５】
〔参考文献７〕J. Muramatsu and S. Miyake, “Hash property and coding theorems for sparse matrices and maximal-likelihood coding,” IEEE Trans. Inform. Theory, vol. IT-56, no. 5, pp. 2143-2167, May 2010.
【０３１６】
これに対して、［歪みを許す情報圧縮についての符号化装置及び方法並びに復号装置及び方法に関する実施形態］における乱数の系列の生成において、例えば、ステップＡ２でsum-product アルゴリズムを適用してO(n)で実行することを仮定し、ステップＡ６及びステップＡ７の計算時間はO(n2)であることを仮定すれば、符号化及び復号のそれぞれの計算時間はO(n2)となる。このように、乱数の系列の生成を多項式時間で行うことにより、符号化及び復号のそれぞれを多項式時間で行うことができる。
【０３１７】
以下、［歪みを許す情報圧縮についての符号化装置及び方法並びに復号装置及び方法に関する実施形態］による歪みを許す情報圧縮の誤り確率が0に収束することを証明する。以下の証明において、[1]から[5]は以下の文献を示す。
【０３１８】
[1] T. M. Cover and J. A. Thomas, “Elements of Information Theory 2nd. Ed.,” John Wiley & Sons, Inc., 2006.
[2] J. L. Carter and M. N. Wegman, “Universal classes of hash functions,” J. Comput. Syst. Sci., vol. 18, pp. 143-154, 1979.
[3] J. Muramatsu and S. Miyake, “Hash property and coding theorems for sparse matrices and maximal-likelihood coding,” IEEE Trans. Inform. Theory, vol. IT-56, no. 5, pp. 2143{2167, May 2010. Corrections: vol.IT-56, no.9, p. 4762, Sep. 2010.
[4] J. Muramatsu and S. Miyake, “Construction of Slepian-Wolf source code and broadcast channel code based on hash property,” available at arXiv:1006.5271[cs.IT], 2010.
[5] J. Muramatsu and S. Miyake, “Construction of strongly secure wiretap channel code based on hash property,” Proc. of 2011 IEEE Int. Symp. Inform. Theory, St. Petersburg, Russia, Jul. 31-Aug. 5, 2011, pp.612-616.
【０３１９】
まず、ハッシュ性について説明する。
【０３２０】
1.1 定義と補題
φを空集合とする。[Un]を定義域とする関数の集合を[A]と記す。ImA,Im[A]を次のように定義する。
【０３２１】
【数１００】
2014109697.tif 000102
【０３２２】
集合CA(a),CAB(a,b)を次のように定義する。
【０３２３】
【数１０１】
2014109697.tif 000103
【０３２４】
関数A∈[A]を値とする確率変数とa∈ImAを、それぞれAs,asと記す。なお、数式においては、As,asを、それぞれサンセリフ書体のA,aを用いて表すこともある。
【０３２５】
ただし、n次元ベクトルun∈[Un]を値とする確率変数はUnと記すことに注意。
【０３２６】
定義1. [An]を関数An:[Un]→Im[An]の集合として、集合の列{[An]}n=1∞を考える。[An]上の確率変数をpAs,nをとり、系列{([An],pAs,n)}n=1∞をアンサンブルと呼ぶ。{([An],pAs,n)}n=1∞に対して{pAs,n}n=1∞に依存した実数列{αAs(n)}n=1∞,{βAs(n)}n=1∞が存在して、任意のnとun∈[Un]に対して
【０３２７】
【数１０２】
2014109697.tif 000104
【０３２８】
及び
【０３２９】
【数１０３】
2014109697.tif 000105
【０３３０】
を満たすとき、{([An],pAs,n)}n=1∞は{αAs(n),βAs(n)}n=1∞-ハッシュ性を持つという。以後、[A],pAs,αAs,βAsはnに依存しているが、nが動かないときはこれを省略する。
【０３３１】
例えば、[A]が2-ユニヴァーサルハッシュ性[2]を持ち、pAsを[A]上の一様分布とするとき、{([An],pAs,n)}n=1∞は{(1,0)}n=1∞-ハッシュ性を持つ。{(1,0)}n=1∞は任意のnでαAs≡1,βAs≡0となる列である。線形写像(行列)のアンサンブルのハッシュ性については次節で説明する。
【０３３２】
次の補題が成り立つ。
【０３３３】
補題1 ([4,Lemma 4]). {([An],pAs,n)}n=1∞,({([Bn],pBs,n)}n=1∞){αAs(n),βAs(n)}n=1∞-ハッシュ性({αBs(n),βBs(n)}n=1∞-ハッシュ性)を持つアンサンブルとする。関数(A,B)∈[A]×[B]を次のように定義する。
【０３３４】
【数１０４】
2014109697.tif 000106
【０３３５】
[A]×[B]上の確率分布pAsBsを次のように定義する。
【０３３６】
【数１０５】
2014109697.tif 000107
【０３３７】
(αAsBs,βAsBs)を次のように定義する。
【０３３８】
【数１０６】
2014109697.tif 000108
【０３３９】
このとき、新たなアンサンブル([An]×[Bn],pAsBs,n)}n=1∞は、{αAsBs(n),βAsBs(n)}n=1∞-ハッシュ性を持つ。
【０３４０】
補題2 ([4,Lemma 1])。 ([A],pAs)が(H3)を満たすとき、任意のT,T’⊂[Un]に対して、以下の式が成立する。
【０３４１】
【数１０７】
2014109697.tif 000109
【０３４２】
補題3 ([3、Lemma 1])。 ([A],pA)が(H3')を満たすとき、任意のT⊂[Un],un∈[Un]に対して、以下の式が成立する。
【０３４３】
【数１０８】
2014109697.tif 000110
【０３４４】
補題4 ([5,Lemma 4])。 ([A],pAs) が(H3)を満たすとき、任意の関数Q:[Un]→[0,1)とT⊂[Un]に対して、以下の式が成立する。
【０３４５】
【数１０９】
2014109697.tif 000111
【０３４６】
ここで、Q(T)は次のように定義される。
【０３４７】
【数１１０】
2014109697.tif 000112
【０３４８】
1.2 線形写像からなるアンサンブルのハッシュ性
[Un]≡GF(q)n,[Ul]≡GF(q)lとする。[A]を線形写像A:[Un]→[Ul]の集合とする。Aはl×n行列で表現できる。
【０３４９】
t(un)をun∈[Un]のタイプ(unの相対頻度分布)とする。[H]をt(0n)を除く全ての長さnの系列のタイプからなる集合とする。l×n行列全体の集合上の確率分布pAsとタイプt∈[H]に対してS(pAs,t)を次のように定義する。
【０３５０】
【数１１１】
2014109697.tif 000113
【０３５１】
集合[H’]⊂[H]を与えたときαAs(n),βAs(n)を次のように定義する。
【０３５２】
【数１１２】
2014109697.tif 000114
【０３５３】
ここで、p￣はl×n行列全体からなる集合上の一様分布を表す。
【０３５４】
補題5 ([4,Theorem 1])． ([A], pAs)を線形写像の集合として、pAs({A:Aun=0l})がt(un)のみに依存している(t(un)=t(vn)ならpAs({A:Aun=0l})=pAs({A:Avn=0l})とする。(B2),(B3)で定義された{αAs(n),βAs(n)}n=1∞が(H1),(H2)を満たしているとき、{([An],pAs,n)}n=1∞は{αAs(n),βAs(n)}n=1∞-ハッシュ性を持つ。
【０３５５】
以下、U≡GF(q),0<R<1としてl≡nRとする。l×n行列Aを次の手続きにより生成する。
1. 行列の全ての成分を0で初期化する。
2. 各i∈{1,…,n}で以下の手続きをτ回繰り返す。
(a) (j,θ)∈{1,…,l}×[GF(q)＼{0}]を一様に選択する。
(b) θをAの(j,i)-成分に(GF(q)の加法で)加える。
【０３５６】
τ=O(log n)を偶数として、([A],pAs)を上記の手続きにより定まるものとする。[H’]⊂[H]を適切に定め、(αAs,βAs)を(B2),(B3)により定義する。このとき、このアンサンブルに対して{αAs(n),βAs(n)}n=1∞が(H1)、(H2)を満たすことは[3, Theorem 2]で証明されている。したがって補題5 によりこのアンサンブルは{αAs(n),βAs(n)}n=1∞-ハッシュ性を持つ。
【０３５７】
次に、歪みを許す情報圧縮の誤り確率が0に収束することを証明する。
【０３５８】
情報源出力の集合[Yn]を無限集合、連続集合を含む任意の集合として、再生アルファベット[Xn]を有限集合とする。
【０３５９】
r,R>0を与えたとき、関数A:[Xn]→Im[A],B:[Xn]→Im[B]のアンサンブルを考える。ここで、圧縮されたデータの集合をIm[B]とする。
【０３６０】
以下では、関数A∈[A],B∈[B]とa∈Im[A]を固定し、これらが符号化装置と復号装置で利用できることを仮定する。
【０３６１】
情報源の確率分布pYnと確率分布pXn|Ynを与えて、pXnを次のように定義する。
【０３６２】
【数１１３】
2014109697.tif 000115
【０３６３】
符号化装置を構成するために制約条件を満たす乱数発生装置を利用する。X~n≡X~An(a|yn)を以下の分布に従う確率変数とする。
【０３６４】
【数１１４】
2014109697.tif 000116
【０３６５】
符号化装置Φn:[Yn]→Im[B]と復号装置ψn:Im[B]→[Xn]を次のように定義する。
【０３６６】
【数１１５】
2014109697.tif 000117
【０３６７】
ここでpXn|Yn(CA(a)|yn)=0のときは符号化エラーを宣言する。また、gABを次のように定義する。
【０３６８】
【数１１６】
2014109697.tif 000118
【０３６９】
誤り確率Error(A,B,a,D)は次のように定義される。
【０３７０】
【数１１７】
2014109697.tif 000119
【０３７１】
ここで、pXn|Yn(CA(a)|yn)=0のときはdn(ψn(Φn(yn)),yn)≡maxxn,yndn(xn,yn)と定義する。
【０３７２】
定理2. もしもr,R>0が
【０３７３】
【数１１８】
2014109697.tif 000120
【０３７４】
を満たしているとき、任意のδ>0と十分大きなnに対してA∈[A],B∈[B],a∈Im[A]が存在して、以下の関係を満たす。
【０３７５】
【数１１９】
2014109697.tif 000121
【０３７６】
情報源の分布pYnに対してpXn|YnがinfpXn|Yn:EXnYn[dn(Xn,Yn)]<DI(Xn;Yn)を達成する事を仮定する。このとき、rをH(Xn|Yn)に近付ける事により、RをinfpXn|Yn:EXnYn[dn(Xn,Yn)]<DI(Xn;Yn)に近付ける事ができる。一方で提案符号は(C30)より、
【０３７７】
【数１２０】
2014109697.tif 000122
【０３７８】
を満たすので、maxxn,yndn(xn,yn)<∞を仮定することにより平均歪みEXnYn[dn(Xn,Yn)]をDに近付ける事ができる。
【０３７９】
証明:
【０３８０】
【数１２１】
2014109697.tif 000123
【０３８１】
とすると、(C28),(C29)より、
【０３８２】
【数１２２】
2014109697.tif 000124
【０３８３】
を満たすε>0が存在する。
【０３８４】
T_をTの下付きバーとし、T-をTの上付きバーとし、T-X⊂[Xn],T_X|Y⊂[Xn]×[Yn]を以下のように定義する。
【０３８５】
【数１２３】
2014109697.tif 000125
【０３８６】
[1,Theorem 16.8.1]より、以下の式が成り立つ。
【０３８７】
【数１２４】
2014109697.tif 000126
【０３８８】
xn⊂T-X,gAB(Axn,Bxn)≠xnを仮定する。このとき、θn≠xn及び
【０３８９】
【数１２５】
2014109697.tif 000127
【０３９０】
を満たすθn∈CAB(Axn,Bxn)が存在する。したがって、T-X∩CAB(Axn,Bxn)≠φが成り立っているので、
【０３９１】
【数１２６】
2014109697.tif 000128
【０３９２】
を得る。ここで、χを次のように定義する。
【０３９３】
【数１２７】
2014109697.tif 000129
【０３９４】
また、最初の不等式では補題3を、2番目の不等式では
【０３９５】
【数１２８】
2014109697.tif 000130
【０３９６】
を用いた。続いて、以下の式が成り立つ。
【０３９７】
【数１２９】
2014109697.tif 000131
【０３９８】
ここで、最後の不等式では(C35)を用いた。また、以下の式が成り立つ。
【０３９９】
【数１３０】
2014109697.tif 000132
【０４００】
ここで、2番目の不等式では補題4を用いた。aの分布を一様分布とするとき、以下の式が成り立つ。
【０４０１】
【数１３１】
2014109697.tif 000133
【０４０２】
ここで2番目の不等式では、以下の関係を用いた。
【０４０３】
【数１３２】
2014109697.tif 000134
【０４０４】
また、3番目の不等式では(C36),(C37)を用いた。(C31),(C32)(C38)とn→1とともにαAs→1,βAs→0,αAB→1,βAB→0,pXn([T_X]c)→0,pXnYn([T_X|Y]c)→0であることから、(C38)の右辺はn→∞とともに0に収束する。このことから定理の成立がいえる。
【０４０５】
［変形例等］
上記装置及び方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０４０６】
また、乱数系列生成装置、符号化装置及び復号装置における処理手段をコンピュータによって実現する場合、乱数系列生成装置、符号化装置及び復号装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、乱数系列生成装置、符号化装置及び復号装置における処理手段がコンピュータ上で実現される。
【０４０７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０４０８】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０４０９】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【０４１０】
１  乱数系列生成装置
１１  制御部
１２  確率分布生成部
１３  乱数生成部
１４  記憶部
１５  乱数推定部
１６  一様乱数生成部
１００  符号化装置
１０１  記憶部
１０２  変換フィルタ部
１０３  圧縮部
２００  復号装置
２０１  記憶部
２０２  乱数系列推定部
２０４  変換フィルタ部
【図１】
2014109697.tif 000137
【図２】
2014109697.tif 000138
【図３】
2014109697.tif 000139
【図４】
2014109697.tif 000140
【図５】
2014109697.tif 000141
【図６】
2014109697.tif 000142
【図７】
2014109697.tif 000143