(57)【要約】【課題】第二確率分布に従う乱数の系列を生成する技術に基づいて情報を符号化する技術を提供する。【解決手段】実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成部の処理と、第三確率分布に従い１つの実現値を乱数として生成する乱数生成部の処理とを繰り返し行う。所定の条件は、メッセージ及び所定の共有情報と、複数の値の系列との関係を所定の関数を用いて表現した条件である。【選択図】図１
2014110533.tif 000002
【特許請求の範囲】
【請求項１】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が上記所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての上記実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成部と、上記第三確率分布に従い１つの実現値を乱数として生成する乱数生成部と、上記確率分布生成部及び上記乱数生成部の処理を繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる制御部と、を含む乱数系列生成装置を含み、
上記所定の条件は、メッセージ及び所定の共有情報と、上記複数の値の系列との関係を所定の関数を用いて表現した条件である、
符号化装置。
【請求項２】
請求項１の符号化装置であって、
上記所定の第一確率分布は、所定の事象を条件とする条件付き確率分布であり、
上記第一確率及び上記第二確率は、上記所定の事象を条件とする条件付き確率であり、
上記第二確率分布に従う乱数の系列に対して、上記所定の事象及び上記第二確率分布に従う乱数の系列を条件とする所定の第四確率分布に従う変換フィルタを適用して複数の値の系列を求めて、求まった複数の値の系列を通信路の入力とする変換フィルタ部を更に含む、
符号化装置。
【請求項３】
請求項１の符号化装置であって、
上記所定の関数をA,Bとし、関数Aの値域をIm[A]とし、関数Bの値域をIm[B]とし、上記所定の共有情報をa∈Im[A]とし、上記メッセージをb∈Im[B]とし、上記複数の値の系列(x1,x2,…,xn)をxn∈[Xn]とし、上記所定の条件をA(xn)=a,B(xn)=bとし、上記第一確率分布をpXnとして、
上記第二確率分布における各実現値xnについての確率は、次式で定義されるμ(xn)である、
【数１８０】
2014110533.tif 000182
符号化装置。
【請求項４】
請求項２の符号化装置であって、
上記所定の関数をA,Bとし、関数Aの値域をIm[A]とし、関数Bの値域をIm[B]とし、上記所定の共有情報をa∈Im[A]とし、上記メッセージをb∈Im[B]とし、上記所定の事象をun∈[Un]とし、上記複数の値 (x1,x2,…,xn) の系列をxn∈[Xn]とし、上記第一確率分布をpXn|Unとして、
上記第二確率分布における各実現値xnについての確率は、次式で定義されるμ(xn)である、
【数１８１】
2014110533.tif 000183
符号化装置。
【請求項５】
請求項１の符号化装置であって、
上記所定の関数をA,Bとし、関数Aの値域をIm[A]とし、関数Bの値域をIm[B]とし、上記所定の共有情報をa∈Im[A]とし、上記メッセージをb∈Im[B]とし、上記所定の条件をA(xn)=a,B(xn)=bとし、上記複数の値 (x1,x2,…,xn) の系列をxn∈[Xn]とし、上記第一確率分布をpXnとして、
上記第二確率分布における各実現値xnについての確率は、次式で定義されるμ(xn)であり、
【数１８２】
2014110533.tif 000184
上記第二確率分布に従う乱数の系列に対して、上記第二確率分布に従う乱数の系列を条件とする所定の第五確率分布に従う変換フィルタを適用して複数の値の系列を求めて、求まった複数の値の系列を通信路の入力とする変換フィルタ部を更に含む、
符号化装置。
【請求項６】
請求項１の符号化装置であって、
iを1,2,…,κの何れかの整数とし、上記所定の関数をAi, Biとし、関数Aiの値域をIm[Ai]とし、関数Biの値域をIm[Bi]とし、上記所定の共有情報をai∈Im[Ai]とし、上記メッセージをbi∈Im[Bi]とし、上記複数の値(xi,1,xi,2,…,xi,n)の系列をxin∈[Xin]とし、上記所定の条件をAi(xin)=ai,Bi(xin)=biとし、上記第一確率分布をp_(Xin)として、
上記第二確率分布における各実現値xinについての確率は、次式で定義されるμ(xin)である、
【数１８３】
2014110533.tif 000185
符号化装置。
【請求項７】
請求項２の符号化装置であって、
iを1,2,…,κの何れかの整数とし、上記所定の関数をAi, Biとし、関数Aiの値域をIm[Ai]とし、関数Biの値域をIm[Bi]とし、上記所定の共有情報をai∈Im[Ai], un∈[Un]とし、上記メッセージをbi∈Im[Bi]とし、上記複数の値(xi,1,xi,2,…,xi,n)の系列をxin∈[Xin]とし、上記所定の条件をAi(xin)=ai,Bi(xin)=biとし、上記第一確率分布をp_(Xin|Un)として、
上記第二確率分布における各実現値xinについての確率は、次式で定義されるμ(xin)である、
【数１８４】
2014110533.tif 000186
符号化装置。
【請求項８】
請求項１の符号化装置であって、
iを1,2,…,κの何れかの整数とし、上記所定の関数をAi, Biとし、関数Aiの値域をIm[Ai]とし、関数Biの値域をIm[Bi]とし、上記所定の共有情報をai∈Im[Ai]とし、上記メッセージをbi∈Im[Bi]とし、上記複数の値の系列をxKn≡{xin}i∈K∈[XKn]とし、xin≡(xi,1,xi,2,…,xi,n) とし、上記所定の条件をAi(xin)=ai,Bi(xin)=biとし、上記第一確率分布をp_(XKn)として、
上記第二確率分布における各実現値xKnについての確率は、次式で定義されるμ(xin)であり、
【数１８５】
2014110533.tif 000187
上記第二確率分布に従う乱数の系列に対して、上記第二確率分布に従う乱数の系列を条件とする所定の第五確率分布に従う変換フィルタを適用して複数の値の系列を求めて、求まった複数の値の系列を通信路の入力とする変換フィルタ部を更に含む、
符号化装置。
【請求項９】
請求項１の符号化装置であって、
iを1,2,…,κの何れかの整数とし、上記所定の関数をAi, Biとし、関数Aiの値域をIm[Ai]とし、関数Biの値域をIm[Bi]とし、上記所定の共有情報をai∈Im[Ai],un∈[Un]とし、上記メッセージをbi∈Im[Bi]とし、上記複数の値の系列をxKn≡{xin}i∈K∈[XKn]とし、xin≡(xi,1,xi,2,…,xi,n)とし、上記所定の条件をAi(xin)=ai,Bi(xin)=biとし、上記第一確率分布をp_(XKn)とし、上記第一確率分布をp_(XKn|Un)として、
上記第二確率分布における各実現値xKnについての確率は、次式で定義されるμ(xin)である、
【数１８６】
2014110533.tif 000188
上記第二確率分布に従う乱数の系列に対して、上記所定の共有情報un及び上記第二確率分布に従う乱数の系列を条件とする所定の第四確率分布に従う変換フィルタを適用して複数の値の系列を求めて、求まった複数の値の系列を通信路の入力とする変換フィルタ部を更に含む、
符号化装置。
【請求項１０】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布を第二確率分布として、
実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が上記所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての上記実現値についての上記第三確率の分布である第三確率分布を生成する確率分布生成ステップと、上記第三確率分布に従い１つの実現値を乱数として生成する乱数生成ステップと、上記確率分布生成ステップ及び上記乱数生成ステップを繰り返すことにより、上記第二確率分布に従う乱数の系列を生成させる制御ステップと、を含む乱数系列生成ステップを含み、
上記所定の条件は、メッセージ及び所定の共有情報と、上記複数の値の系列との関係を所定の関数を用いて表現した条件である、
符号化方法。
【請求項１１】
請求項１の符号化方法であって、
上記所定の第一確率分布は、所定の事象を条件とする条件付き確率分布であり、
上記第一確率及び上記第二確率は、上記所定の事象を条件とする条件付き確率であり、
上記第二確率分布に従う乱数の系列に対して、上記所定の事象及び上記第二確率分布に従う乱数の系列を条件とする所定の第四確率分布に従う変換フィルタを適用して複数の値の系列を求めて、求まった複数の値の系列を通信路の入力とする変換フィルタステップを更に含む、
符号化方法。
【請求項１２】
請求項１から９の何れかの符号化装置としてコンピュータを機能させるためのプログラム。
【請求項１３】
請求項１から９の何れかの符号化装置としてコンピュータを機能させるためのプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報を符号化する技術に関する。
【背景技術】
【０００２】
複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての上記複数の値の系列である実現値についての上記確率の分布である第二確率分布に従う乱数の系列を生成する技術、及び、この技術に基づいて情報を符号化する技術はこれまで提案されていない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
この発明は、第二確率分布に従う乱数の系列を生成する技術に基づいて情報を符号化する符号化装置、方法、プログラム及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００４】
この発明の一態様による符号化装置は、複数の値の系列である実現値についての確率を所定の第一確率分布においてその実現値が出現する確率に応じた確率とし、所定の条件を満たす全ての複数の値の系列である実現値についての確率の分布を第二確率分布として、実現値についての確率である第三確率を、既に生成された乱数の系列を条件としたときにその実現値が出現する第一確率と、既に生成された乱数の系列及び今回生成される乱数を条件としたときに次回以降生成される残りの乱数の系列が所定の条件を満たす第二確率と、の積に応じた確率とし、取りうる全ての実現値についての第三確率の分布である第三確率分布を生成する確率分布生成部と、第三確率分布に従い１つの実現値を乱数として生成する乱数生成部と、確率分布生成部及び乱数生成部の処理を繰り返すことにより、第二確率分布に従う乱数の系列を生成させる制御部と、を備え、所定の条件は、メッセージ及び所定の共有情報と、複数の値の系列との関係を所定の関数を用いて表現した条件である。
【発明の効果】
【０００５】
第二確率分布に従う乱数の系列を生成する技術に基づいて情報を符号化することができる。
【図面の簡単な説明】
【０００６】
【図１】乱数系列生成装置の例を説明するためのブロック図。
【図２】乱数系列生成装置の他の例を説明するためのブロック図。
【図３】乱数系列生成方法の例を説明するためのフローチャート。
【図４】第一実施形態の符号化装置及び復号装置の例を説明するためのブロック図。
【図５】第一実施形態の符号化装置及び復号装置の例を説明するためのブロック図。
【図６】第二実施形態の符号化装置及び復号装置の例を説明するためのブロック図。
【図７】第二実施形態の符号化装置及び復号装置の例を説明するためのブロック図。
【図８】第三実施形態の符号化装置及び復号装置の例を説明するためのブロック図。
【図９】第四実施形態の符号化装置及び復号装置の例を説明するためのブロック図。
【図１０】符号化方法の例を説明するためのフローチャート。
【図１１】復号方法の例を説明するためのフローチャート。
【発明を実施するための形態】
【０００７】
［記法の説明］
まず、記法の説明を行う。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)上ベクトル空間の線形写像の場合、
【００１０】
【数１】
2014110533.tif 000003
【００１１】
のように行列で表記する。このとき、xnは列ベクトル
【００１２】
【数２】
2014110533.tif 000004
【００１３】
となる。この場合はΦ(xn)をΦxnと記す。
【００１４】
変数のとり得る値の集合が有限であることが明示されていないときは、連続値をとることができる。また、和Σをとる変数が連続値である場合にはΣは積分∫となる。
【００１５】
［制約条件を満たす素朴な乱数系列生成法］
関数の集合Φ≡{φs:[Xn]→Vs}s=1lに対してΦ(xn)∈V1×V2×…×Vlを
【００１６】
【数３】
2014110533.tif 000005
【００１７】
と定義する。vl≡(v1,v2,…,vl)及び確率変数Xn≡(X1,X2,…,Xn)の分布pXnが与えられたときに、次式で定義されるμ(xn)を考える。
【００１８】
【数４】
2014110533.tif 000006
【００１９】
所定の条件をΦ(xn)=vlとし、所定の第一確率分布をpXnとすると、実現値xn≡(x1,x2,…,xn)についての確率μ(xn)は、所定の第一確率分布pXnにおいてその実現値xnが出現する確率に応じた確率である。
【００２０】
ここでは、所定の条件Φ（ｘｎ）＝ｖｌを満たす全ての実現値についての確率μ(xn)の分布（第二確率分布）に従ういずれか一つの実現値xnを乱数の系列として発生させる素朴な２つの方法を記述する。
【００２１】
＜方法１＞
まず最初に、Φ(xn)=vlを満たすxnを列挙した集合Ωを求める。続いて、各xn∈Ωについて、関係式
【００２２】
【数５】
2014110533.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)を次のように定義する。
【００３２】
【数６】
2014110533.tif 000008
【００３３】
確率分布pXnを次のように分解する。
【００３４】
【数７】
2014110533.tif 000009
【００３５】
ここで、上式の右辺でt=1の時には
【００３６】
【数８】
2014110533.tif 000010
【００３７】
とする。例えば、pXnが無記憶の場合は、
【００３８】
【数９】
2014110533.tif 000011
【００３９】
となり、pXnがδ次Markov性を持つ場合は
【００４０】
【数１０】
2014110533.tif 000012
【００４１】
となる。
乱数系列生成装置１は、図１に示すように、制御部１１、確率分布生成部１２、乱数生成部１３、記憶部１４及び乱数推定部１５を例えば備えている。
【００４２】
(a2)で定義された確率分布μに従う乱数を発生させるために、乱数系列生成装置は次の処理を実行する。以下、Σはその下に書かれている変数の全てのとり得る値に関する和を表すこととする。例えば、Σxtは全てのxt∈[Xt]に関する和である。
【００４３】
制御部１１は、k=1とする（ステップＡ１，図３）。
【００４４】
確率分布生成部１２が、次式により定義される関数fk(xk)を求める（ステップＡ２）。関数fk(xk)は、例えばsum-productアルゴリズムを実行することにより求めることができる。sum-productアルゴリズムについては、後述する。
【００４５】
【数１１】
2014110533.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)の右辺の分子に現れる
【００４９】
【数１２】
2014110533.tif 000014
【００５０】
は、既に生成された乱数の系列x1,…,xt-1を条件としたときに実現値xtが出現する第一確率と言える。
【００５１】
また、(a5)の右辺の分子に現れる
【００５２】
【数１３】
2014110533.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)の右辺の分子に現れる式を
【００７３】
【数１４】
2014110533.tif 000016
【００７４】
とすると、
【００７５】
【数１５】
2014110533.tif 000017
【００７６】
が成り立っている。
【００７７】
xn=(x1,x2,…,xn)を最終的に出力した乱数系列とする。アルゴリズムのステップＡ４においてk=nで終了した場合は、
【００７８】
【数１６】
2014110533.tif 000018
【００７９】
となる。一方で、 アルゴリズムのステップＡ６及びステップＡ７でk=k’<nで終了した場合は、(x1,x2,…,xk’)からΦ(xn)=vlを満たす残りの変数の値(xk’+1,…,xn)が唯一定まることから、
【００８０】
【数１７】
2014110533.tif 000019
【００８１】
となる。(a8)は(a7)をk’=nの場合として含んでいるので、以下、k=k’で終了した場合を考える。
【００８２】
(a6)よりk≧2の時は
【００８３】
【数１８】
2014110533.tif 000020
【００８４】
が成り立つ。また、k=1の時は
【００８５】
【数１９】
2014110533.tif 000021
【００８６】
が成り立つ。(a8),(a9),(a10)より最終的にxnを出力する確率は
【００８７】
【数２０】
2014110533.tif 000022
【００８８】
となる。したがって、このアルゴリズムは、確率分布(a2)に従う乱数列xnを出力する。
【００８９】
＜sum-productアルゴリズムについて＞
一般的にsum-productアルゴリズムとは、変数ベクトルxnの一部からなる変数ベクトルxT(s)で定まる関数es(xT(s))が各s∈Sで与えられたとき、周辺化関数
【００９０】
【数２１】
2014110533.tif 000023
【００９１】
を求める手続きである。ここで、N≡{1,2,…,n}として、各s∈SでT(s)⊂Nである。また
Σxn＼{xt}は、ベクトルxnに現れる変数xt以外の全てのxnの値を動かした時の総和である。また、(a12)で定めたg(xt)ではなく、右辺の分子に現れた
【００９２】
【数２２】
2014110533.tif 000024
【００９３】
を求める手続きとしてsum-productアルゴリズムが記述される場合があるが、以下では、(a12)で定めたg(xt)を求める手続きをsum-productアルゴリズムと呼ぶことにする。
【００９４】
以下にsum-productアルゴリズムを記述する。メッセージと呼ばれる関数πxt→es(xt),σes→xt(xt)を次のように定義する。
【００９５】
【数２３】
2014110533.tif 000025
【００９６】
ここで、Σx_(T(s)＼{t})は全ての{xt’}t’∈T(s)＼{t}を動かした時の総和であり、Σx_(T(s))は全ての{xt}t∈T(s)を動かした時の総和を表す。また、T(s)={t}の時は
【００９７】
【数２４】
2014110533.tif 000026
【００９８】
と定め、xt∈T(s’)を満たすs’∈S＼{s}が存在しないときは
【００９９】
【数２５】
2014110533.tif 000027
【０１００】
と定める。
以下、sum-product アルゴリズムの具体処理について説明する。
Step 1 T(s)={t}を満たすt∈N,s∈Sに対して
【０１０１】
【数２６】
2014110533.tif 000028
【０１０２】
と初期化する。
Step 2 xt∈T(s’)を満たすs’∈S＼{s}が存在しないようなt∈N,s∈Sに対して
【０１０３】
【数２７】
2014110533.tif 000029
【０１０４】
と初期化する。
Step 3 t∈T(s)を満たすt∈N,s∈Sに対して、πxt→es(xt)をStep 2 で初期化しなかったならば、これに適当な初期値を設定する。例えば、xtのとり得る値の集合が[Xt]であれば、
【０１０５】
【数２８】
2014110533.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を予め定めた繰り返し回数繰り返した後、以下の関数を求めて終了する。
【０１０７】
【数２９】
2014110533.tif 000031
【０１０８】
なお、制約を満たす乱数生成アルゴリズムにsum-productアルゴリズムを用いる場合、(a5)において
【０１０９】
【数３０】
2014110533.tif 000032
【０１１０】
を{es}s∈Sとみなして適用する。sum-productアルゴリズムの実行後に得られた(a15)の右辺がfk(xk)の近似式となる。
【０１１１】
［乱数系列生成装置及び方法の第二実施形態］
乱数系列生成装置及び方法の第二実施形態は、関数が線形性を持つときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１１２】
以下では、[X1]=[X2]=…=[Xn]=[V1]=[V2]=…=[Vl]=GF(q)を仮定し、l≦nとして、フルランクのl×n行列
【０１１３】
【数３１】
2014110533.tif 000033
【０１１４】
を考える。関数φs:[Xn]→Vsを
【０１１５】
【数３２】
2014110533.tif 000034
【０１１６】
と定義する。上式の右辺は行列Φのｓ行目のｎ次元ベクトル（φs,1, φs,2,...,φs,n）とxn≡(x1,x2,…,xn)∈[Xn]の内積である。
【０１１７】
上記のように定義されたΦ≡{φs}s=1lとベクトル
【０１１８】
【数３３】
2014110533.tif 000035
【０１１９】
に対して、確率分布(a2)で定まる分布を発生させる乱数系列生成装置１の具体処理を記述する。
【０１２０】
ここで、Φとｖｌは与えられた行列とベクトルそのままを利用しても良いが、Φとｖｌを連結した以下の行列
【０１２１】
【数３４】
2014110533.tif 000036
【０１２２】
に対して行基本変形を施した結果
【０１２３】
【数３５】
2014110533.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))を次のように定義する。
【０１２９】
【数３６】
2014110533.tif 000038
【０１３０】
以上の設定により、乱数系列生成装置１の具体処理を以下のように変更することができる。
【０１３１】
制御部１１は、k=1とする。各s∈{1,…,l}でvs(k)=vsとする。
【０１３２】
確率分布生成部１２は、次式により定義される関数fk(xk)を求める（ステップＡ２）。関数fk(xk)は、例えばsum-productアルゴリズムを実行することにより求めることができる。
【０１３３】
【数３７】
2014110533.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)が与えられたとき、制約条件を満たし、
【０１４４】
【数３８】
2014110533.tif 000040
【０１４５】
に従う乱数を生成するときには、
【０１４６】
【数３９】
2014110533.tif 000041
【０１４７】
と置き換えて乱数系列生成装置の具体処理を実行する。すなわち、例えば(a5)は、次式のようになる。
【０１４８】
【数４０】
2014110533.tif 000042
【０１４９】
第三実施形態の乱数系列生成装置１の入力は確率分布の集合{p_(Xt|X1t-1Un)}t=1n、関数の集合Φ,vl,unであり、出力はxnである。
【０１５０】
記憶部１４には入力の他に
【０１５１】
【数４１】
2014110533.tif 000043
【０１５２】
を計算するために必要な情報を保持しておき、確率分布の計算に利用する。
【０１５３】
なお、上記同様にして、乱数系列生成装置及び方法の第二実施形態においてもpXnが条件付き確率分布であってもよい。
【０１５４】
［乱数系列生成装置及び方法の第四実施形態］
乱数系列生成装置及び方法の第四実施形態は、定義域が同一の関数を複数用いて制約条件が記述されるときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１５５】
c∈Cとする。Cは2以上の所定の定数である。制約条件を満たす乱数生成法において、定義域が同一の複数の関数の集合
Φc≡{φc,s:[Xn]→Vc,s}s=1lc
及び
vclc≡(vc,1,vc,2,…,vc,l)∈Vc,1×Vc,2×…×Vc,lc
および分布pXnが与えられたとき、
【０１５６】
【数４２】
2014110533.tif 000044
【０１５７】
に従う乱数を生成するには
【０１５８】
【数４３】
2014110533.tif 000045
【０１５９】
とおいて、乱数系列生成装置及び方法の第一実施形態の具体処理を実行すればよい。
すなわち、例えば(a5)は、次式のようになる。
【０１６０】
【数４４】
2014110533.tif 000046
【０１６１】
ここで、T(c,s)⊂{1,2,…,n}はφc,s(xn)=vc,sを計算する際に使用する変数xn=(x1, x2, …, xn)のインデックスの集合であり、
【０１６２】
【数４５】
2014110533.tif 000047
【０１６３】
である。
もちろん、関数Φcが全て線形写像(行列)である場合は、関数を表す行列を連結した１つのl×n行列を考えて乱数系列生成装置及び方法の第二実施形態の具体処理を実行してもよい。
【０１６４】
また、［乱数系列生成装置及び方法の第四実施形態］においても、［乱数系列生成装置及び方法の第三実施形態］のように確率分布が条件付き確率分布で与えられていてもよい。この場合、fk(xk)は以下のようになる。
【０１６５】
【数４６】
2014110533.tif 000048
【０１６６】
［乱数系列生成装置及び方法の第五実施形態］
乱数系列生成装置及び方法の第四実施形態は、定義域が異なる関数を複数用いて制約条件が記述されるときの乱数系列生成装置及び方法である。以下では、乱数系列生成装置及び方法の第一実施形態と異なる部分を中心に説明し、乱数系列生成装置及び方法の第一実施形態と同様の部分については重複説明を省略する。
【０１６７】
i∈K≡{1,2,…,κ},XK*≡{Xini}i∈Kとする。ここで、
[Xini]≡[Xi,1]×[Xi,2]×…×[Xi,n]
Xini≡(Xi,1,Xi,2,…,Xi,ni)∈[Xini]
である。制約条件を満たす乱数生成法において、定義域が異なる複数の関数の集合
Φi≡{φi,s:[Xini]→Vi,s}s=1li
及び
vili≡(vi,1,vi,2,…,vi,li)∈Vi,1×Vi,2×…×Vi,li
および分布p_(XK*)が与えられたとき、
【０１６８】
【数４７】
2014110533.tif 000049
【０１６９】
に従う乱数
【０１７０】
【数４８】
2014110533.tif 000050
【０１７１】
を生成するには
【０１７２】
【数４９】
2014110533.tif 000051
【０１７３】
とおいて、乱数系列生成装置及び方法の第一実施形態の具体処理を実行すればよい。ここで、
θk*≡{θi}i∈K
であり、XK*およびxnに含まれる確率変数を並べる順序は任意である。以下，xの下に付くインデックスはそのように並べ替えた後のインデックスを指すものとする。
すなわち、例えば(a5)は、次式のようになる。
【０１７４】
【数５０】
2014110533.tif 000052
【０１７５】
ここで、T(i,s)⊂{1,2,…, n}は
【０１７６】
【数５１】
2014110533.tif 000053
【０１７７】
を計算する際に使用する変数xiniのxnにおけるインデックスの集合であり、
【０１７８】
【数５２】
2014110533.tif 000054
【０１７９】
である。
もちろん、[Xini]∈GF(q)niであり、関数Φcが全て線形写像(行列)である場合は、関数を表す行列を連結した１つのl×n行列を考えて乱数系列生成装置及び方法の第二実施形態の具体処理を実行してもよい。すなわち、行列を対角線上に連結して関数と無関係な変数の部分を0で埋めたl×n行列を考えて乱数系列生成装置及び方法の第二実施形態の具体処理を利用することができる。例えば、Φ1,Φ2がそれぞれl1×n1行列、l2×n2行列で表現できるときは、Φを表現する行列は(l1＋l2)×(n1＋n2)行列
【０１８０】
【数５３】
2014110533.tif 000055
【０１８１】
となる。ここで、Oは零行列を表す。
【０１８２】
また、［乱数系列生成装置及び方法の第五実施形態］においても、［乱数系列生成装置及び方法の第三実施形態］のように確率分布が条件付き確率分布で与えられていてもよい。この場合、fk(xk)は以下のようになる。
【０１８３】
【数５４】
2014110533.tif 000056
【０１８４】
［乱数系列生成装置及び方法の実施形態の変形例］
なお、［乱数系列生成装置及び方法の第四実施形態］と［乱数系列生成装置及び方法の第五実施形態］を組み合わせることができる。このとき、unがない場合、fk(xk)は以下のようになる。
【０１８５】
【数５５】
2014110533.tif 000057
【０１８６】
［乱数系列生成装置及び方法の第四実施形態］と［乱数系列生成装置及び方法の第五実施形態］を組み合わせたときであって、unがある場合、fk(xk)は以下のようになる。
【０１８７】
【数５６】
2014110533.tif 000058
【０１８８】
［乱数系列生成装置及び方法の第四実施形態］と［乱数系列生成装置及び方法の第五実施形態］を組み合わせるとき、集合Cはiに依存して決まり、l(ベクトルvlの次元)はiとcに依存して決まる。fk(xk)の式に現れる(x1,x2,…,ｘn)のインデックスは{xini}i∈Kを適切な順序で並べたものを(x1,x2,…,ｘn)としたときのインデックスと対応し、T(i,c,s)は関数φi,c,sを計算する際に用いる変数の(x1,x2,…,ｘn)に関するインデックスを表す。なお、n≡Σi∈Kniである。
【０１８９】
［通信路符号に関する実施形態についての注意］
通信路符号に関する実施形態である［符号化装置及び方法並びに復号装置及び方法の第一実施形態］から［符号化装置及び方法並びに復号装置及び方法の第五実施形態］の説明の前に、これらの通信路符号に関する実施形態についての注意を述べる。
【０１９０】
以下では、対数の底を例えば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]を次のようにする。
【０１９３】
【数５７】
2014110533.tif 000059
【０１９４】
[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行列全体からなる集合とすることにより、
【０１９７】
【数５８】
2014110533.tif 000060
【０１９８】
となるので、後に登場するlog|Im[A]|,log|Im[B]|に関する条件式をq,n,m,m’に関する条件式に変換することができる。そして、aはm次元のベクトル、bはm’次元のベクトルとなる。
【０１９９】
確率変数XnのエントロピーYnが与えられた時のXnの条件付きエントロピーを以下のように定義する。
【０２００】
【数５９】
2014110533.tif 000061
【０２０１】
制約条件を満たす乱数系列生成法を適用するとき、条件付き確率分布を用いて定まる制約条件を満たす乱数を必要とする場合は、［乱数系列生成装置及び方法の第一実施形態］から［乱数系列生成装置及び方法の第五実施形態］で説明した方法を適用すればよい。
【０２０２】
関数が記録されているとは、関数を計算する手段が記録されていることを意味する。関数が線形性を持つ場合は、その係数を行列の形で記録しておけばよい。確率分布が記録されているとは、実現値の確率を計算する手段が記録されていることを意味する。関数を計算する手段及び実現値の確率を計算する手段は、後述のように例えばプログラムにより実装される。例えばGauss分布等のパラメトライズされた連続分布や定常無記憶性やマルコフ性を仮定すれば、少ない容量で確率を計算する手段を記録することができる。制約付き乱数生成アルゴリズムを利用する場合は、fk(xk)を計算するために必要な情報と置き換えることができる。
【０２０３】
［符号化装置及び方法並びに復号装置及び方法の第一実施形態］
＜符号化装置がunを観測しない場合＞
以下では、図４を参照して、符号化装置１００が通信路３００の補助情報unを観測しない場合の構成を述べる。
【０２０４】
まず、通信路符号に関する本実施形態におけるデータの大まかな流れを説明する。
【０２０５】
メッセージbは集合Im[B]の要素であり、Bがm’×n行列である場合はm’次元のベクトルとなる。所定の共有情報であるaは集合Im[A]の要素であり、Aがm×n行列である場合はm次元のベクトルとなる。符号化装置はメッセージbとaから通信路の入力となる符号語xnを求める。符号語xn≡(x1,x2,…,xn)は集合[Xn]の要素である。
【０２０６】
通信路に入力されたxnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路の出力yn≡(y1,…,yn)は集合[Yn]の要素である。復号装置はynとaからメッセージbの推定値βを求める。βはIm[B]の要素である。
【０２０７】
図４に示すように、符号化装置１００は、乱数系列生成装置１及び記憶部１０１を例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００及び復号装置２００は、通信路３００で接続されている。
【０２０８】
記憶部１０１には、関数A,Bと、所定の共有情報aと、確率分布pXnとが記録されている。乱数系列生成装置１は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０２０９】
記憶部２０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Ynとが記録されている。記憶部２０１に記録されているこれらの情報は、通信路３００の性質に応じて予め管理者等が設定しておくものとする。乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０２１０】
ここで、[A],[B]は、以下の関係を満たすように設定しておく。
【０２１１】
【数６０】
2014110533.tif 000062
【０２１２】
xn∈[Xn],yn∈[Yn]とする。通信路３００を特徴づける確率分布をpYn|Xnとする。入力分布pXnは設計パラメータであり任意に与えることができるが、通常は(H(Xn)-H(Xn|Yn))が大きいものを与える。ここで、PYn(yn)及びPXn|Yn(xn|yn)を以下のように定義する。
【０２１３】
【数６１】
2014110533.tif 000063
【０２１４】
符号化装置１００の乱数系列生成装置１にメッセージbが入力される。
【０２１５】
乱数系列生成装置１は、メッセージb∈Im[B]と所定の共有情報a∈Im[A]に対して、以下の確率分布μに従う乱数の系列xnを発生させ、これを符号化装置１００の出力である符号語として通信路３００に入力する（ステップＢｅ１，図１）。
【０２１６】
【数６２】
2014110533.tif 000064
【０２１７】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxnとしてもよい。
【０２１８】
乱数系列生成装置１は、このように所定の条件がAxn=a,Bxn=bである場合は、
Im[A]⊂V1,1×V1,2×…×V1,m
Im[B]⊂V2,1×V2,2×…×V2,m’
を満たす集合V1,1,V1,2,…,V1,m,V2,1,…,V2,m’が存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第四実施形態］で説明した方法を適用することにより、乱数の系列xnを例えば生成することができる。
【０２１９】
【数６３】
2014110533.tif 000065
【０２２０】
通信路３００の出力ynは、復号装置２００の乱数系列推定部２０２に入力される。
【０２２１】
乱数系列推定部２０２は、通信路３００の出力ynから、次式により定義される、xnの推定値ξnを求める（ステップＢｄ１，図１１）。求まったξnは、メッセージ推定部２０３に送信される。
【０２２２】
【数６４】
2014110533.tif 000066
【０２２３】
なお、(b1)を求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξnを近似的に求めてもよい。
【０２２４】
このように、乱数系列推定部２０２は、所定の共有情報aを所与としたときに所定の関数Aを満たす複数の値の系列θｎのうち、通信路３００の出力ynを条件としたときにθｎが出現する確率を最大にするθｎをξnとして求め、求まった値の系列ξnを乱数系列生成装置１の出力であった乱数の系列xnとして推定する。
【０２２５】
メッセージ推定部２０３は、β≡B(ξn)を計算することによりメッセージの推定値βを得る（ステップＢｄ２）。このように、メッセージ推定部２０３は、所定の関数Bを用いて、推定された乱数の系列ξnから、メッセージの推定値βを生成する。
【０２２６】
なお、乱数系列生成装置１は、A,Bが線形写像、すなわち行列の場合は、行列を連結した(m+m’)×n 行列を考えて、［乱数系列生成装置及び方法の第二実施形態］で説明した方法を適用することにより、乱数の系列xnを生成してもよい。
【０２２７】
以下、具体的な例を記述する。関数Aをm×n行列、関数Bをm’×n行列として、以下のように表記する。
【０２２８】
【数６５】
2014110533.tif 000067
【０２２９】
行列A,Bがフルランクであることを仮定して、m次元ベクトルaとメッセージを表すm’次元のベクトルbを以下のように表記する。
【０２３０】
【数６６】
2014110533.tif 000068
【０２３１】
関数Φを以下のように(m+m’)×n行列とし、l≡m+m’としてベクトルvlを以下のようにする。
【０２３２】
【数６７】
2014110533.tif 000069
【０２３３】
[Xn]上の確率分布pXnを定め、符号化装置１００は(a2)で定まる分布μで発生させた乱数xnを通信路３００に入力する。ここで、Φ(θn)=vlは、以下のようになる
【０２３４】
【数６８】
2014110533.tif 000070
【０２３５】
通信路３００出力ynを受信した復号装置は(b1)によってxnの推定値ξnを求めて、ｍ’次元ベクトルであるβをメッセージの推定値とする。
【０２３６】
【数６９】
2014110533.tif 000071
【０２３７】
ここで、条件式A(θn)=aは、以下のようになる。
【０２３８】
【数７０】
2014110533.tif 000072
【０２３９】
以下、他の具体例について説明する。
【０２４０】
q=2,n=7として、[Xn]≡GF(2)7,[Yn]≡GF(2)7とする。通信路の確率分布を次のように仮定する。
【０２４１】
【数７１】
2014110533.tif 000073
【０２４２】
ここで、ζは0以上1以下の実数とする。[Xn]上の確率分布pXnを以下のように定める。
【０２４３】
【数７２】
2014110533.tif 000074
【０２４４】
確率分布pXn|Ynは以下で与えられる。
【０２４５】
【数７３】
2014110533.tif 000075
【０２４６】
確率分布p_(Xt|X1t-1)は以下で与えられる。
【０２４７】
【数７４】
2014110533.tif 000076
【０２４８】
ここで、ηは0以上1以下の実数とする。ζ=1/4,η=5/7とすると、以下のようになる。
【０２４９】
【数７５】
2014110533.tif 000077
【０２５０】
関数A,Bを行列として、列数をそれぞれm=3,m’=2とすると、以下の式を満たしている。
【０２５１】
【数７６】
2014110533.tif 000078
【０２５２】
ここで、対数の底を2とした。
【０２５３】
3×7行列A、2×7行列B を以下のように定める。
【０２５４】
【数７７】
2014110533.tif 000079
【０２５５】
3次元ベクトルaを以下のように定義する。
【０２５６】
【数７８】
2014110533.tif 000080
【０２５７】
これからメッセージを表す以下の2次元のベクトルを符号化する。
【０２５８】
【数７９】
2014110533.tif 000081
【０２５９】
関数Φを5×7行列
【０２６０】
【数８０】
2014110533.tif 000082
【０２６１】
とし、l≡m+m’=5としてベクトルvlを以下のように定義する。
【０２６２】
【数８１】
2014110533.tif 000083
【０２６３】
［乱数系列生成装置及び方法の第二実施形態］で説明した方法に従って乱数の系列を発生するにあたり、Ψ1,Ψ2を次のように定める。
【０２６４】
【数８２】
2014110533.tif 000084
【０２６５】
Ψ2は正則行列であるので、逆行列Ψ2-1は以下のようになる。
【０２６６】
【数８３】
2014110533.tif 000085
【０２６７】
ここで、［乱数系列生成装置及び方法の第二実施形態］の乱数発生装置の具体処理を行う。
【０２６８】
1. ステップＡ１においてk=1に設定する。vs(1)は次のようになる。
【０２６９】
【数８４】
2014110533.tif 000086
【０２７０】
2. ステップＡ２においてT(s,1),χ(xT(s,1),vs(1))は次のようになる。
【０２７１】
【数８５】
2014110533.tif 000087
【０２７２】
関数
【０２７３】
【数８６】
2014110533.tif 000088
【０２７４】
を計算することにより、
【０２７５】
【数８７】
2014110533.tif 000089
【０２７６】
を得る。
【０２７７】
3. ステップＡ３において確率分布
【０２７８】
【数８８】
2014110533.tif 000090
【０２７９】
で乱数0又は1を発生させる。以下0を発生させたと仮定し、x1=0とする。
【０２８０】
4. ステップＡ４においてk=2とする。vs(2)は次のようになる。
【０２８１】
【数８９】
2014110533.tif 000091
【０２８２】
そして、ステップＡ２に戻る。
【０２８３】
5. ステップＡ２においてT(s,2),χ(xT(s,2),vs(2))は次のようになる。
【０２８４】
【数９０】
2014110533.tif 000092
【０２８５】
関数
【０２８６】
【数９１】
2014110533.tif 000093
【０２８７】
を計算することにより
【０２８８】
【数９２】
2014110533.tif 000094
【０２８９】
を得る。
6. ステップＡ３において確率分布
【０２９０】
【数９３】
2014110533.tif 000095
【０２９１】
で乱数0又は1を発生させる。以下1を発生させたと仮定し、x2=1とする。
【０２９２】
7. ステップＡ６においてvs(3)は次のようになる。
【０２９３】
【数９４】
2014110533.tif 000096
【０２９４】
ここで、(x3,…,x7)を求めると、以下のようになる。
【０２９５】
【数９５】
2014110533.tif 000097
【０２９６】
乱数系列発生装置はxn=(0,1,0,0,1,1,1)を出力して終了する。
【０２９７】
符号化装置は乱数発生装置の出力xn=(0,1,0,0,1,1,1)を符号語として通信路に入力する。
【０２９８】
以下では通信路の出力をyn=(0,1,0,1,1,1,1)とする。通信路の出力ynを受信した復号装置は最初にxnの推定値
【０２９９】
【数９６】
2014110533.tif 000098
【０３００】
を求めた結果、
【０３０１】
【数９７】
2014110533.tif 000099
【０３０２】
を得る。続いてメッセージ推定部にてメッセージの推定値
【０３０３】
【数９８】
2014110533.tif 000100
【０３０４】
を得る。
＜符号化装置がunを観測する場合＞
以下では、図５を参照して、通信路３００が２つの入力wnとunを持ち、符号化装置１００がunを観測する場合の構成を述べる。
【０３０５】
まず、通信路符号に関する本実施形態におけるデータの大まかな流れを説明する。
【０３０６】
乱数系列生成装置１の出力xn≡(x1,x2,…,xn)は集合[Xn]の要素である。通信路入力un≡(u1,…,un)は集合[Un]の要素である。
【０３０７】
メッセージbは集合Im[B]の要素であり、Bがm’×n行列である場合はm’次元のベクトルとなる。所定の共有情報であるaは集合Im[A]の要素であり、Aがm×n行列である場合はm次元のベクトルとなる。符号化装置はメッセージbとaとunとから通信路の入力となる符号語wnを求め、通信路に入力する。符号語wn≡(w1,…,wn)は集合[Wn]の要素である。  通信路に入力されたwnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路の出力yn≡(y1,…,yn)は集合[Yn]の要素である。集合[Yn]は、有限集合とは限らないとする。復号装置はynとaからメッセージbの推定値βを求める。βはIm[B]の要素である。
【０３０８】
図５に示すように、符号化装置１００は、乱数系列生成装置１、記憶部１０１及び変換フィルタ部１０２を例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００及び復号装置２００は、通信路３００で接続されている。
【０３０９】
記憶部１０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Un,pWn|XnUnとが記録されている。乱数系列生成装置１及び変換フィルタ部１０２は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３１０】
記憶部２０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Ynが記録されている。記憶部２０１に記録されているこれらの情報は、通信路３００の性質に応じて予め管理者等が設定しておくものとする。乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３１１】
ここで、[A],[B]は、以下の関係を満たすように設定しておく。
【０３１２】
【数９９】
2014110533.tif 000101
【０３１３】
xn∈[Xn],yn∈[Yn],un∈[Un],wn∈[Wn]とする。通信路３００を特徴づける確率分布をpUn,pYn|WnUnとする。条件付き確率分布pWn|XnUn,pXn|Unは設計パラメータであり任意に与えることができるが、通常は(H(Xn|Un)-H(Xn|Yn))が大きいものを与える。ここで、PYn(yn),PXn|Yn(xn|yn)を以下のように定義する。
【０３１４】
【数１００】
2014110533.tif 000102
【０３１５】
符号化装置１００の乱数系列生成装置１にメッセージb及びunが入力される。
【０３１６】
乱数系列生成装置１は、メッセージb∈Im[B]、通信路３００の入力unと所定の共有情報a∈Im[A]に対して、以下の確率分布μに従う乱数の系列xnを発生させる（ステップＢｅ１，図１０）。乱数の系列xnは、変換フィルタ部１０２に送信される。
【０３１７】
【数１０１】
2014110533.tif 000103
【０３１８】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxnとしてもよい。
【０３１９】
乱数系列生成装置１は、このように所定の条件がAxn=a,Bxn=bである場合は、
Im[A]⊂V1,1×V1,2×…×V1,m
Im[B]⊂V2,1×V2,2×…×V2,m’
を満たす集合V1,1,V1,2,…,V1,m,V2,1,…,V2,m’が存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第三実施形態］及び［乱数系列生成装置及び方法の第四実施形態］で説明した方法を適用することにより、乱数の系列xnを例えば生成することができる。
【０３２０】
【数１０２】
2014110533.tif 000104
【０３２１】
変換フィルタ部１０２は、確率分布pWn|XnUnに従うランダム又は決定的な変換Fを通して得られた系列wn≡F(xn,un)を符号化装置１００の出力である符号語として通信路３００に入力する（ステップＢｅ２）。
【０３２２】
通信路３００の出力ynは、復号装置２００の乱数系列推定部２０２に入力される。
【０３２３】
乱数系列推定部２０２は、通信路３００の出力ynから、次式により定義される、xnの推定値ξnを求める（ステップＢｄ１，図１１）。求まったξnは、メッセージ推定部２０３に送信される。
【０３２４】
【数１０３】
2014110533.tif 000105
【０３２５】
なお、上記式よりξnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξnを近似的に求めてもよい。
【０３２６】
このように、乱数系列推定部２０２は、所定の共有情報aを所与としたときに所定の関数Aを満たす複数の値の系列θｎのうち、通信路３００の出力ynを条件としたときにθｎが出現する確率を最大にするθｎをξnとして求め、求まった値の系列ξnを乱数系列生成装置１の出力であった乱数の系列xnとして推定する。
【０３２７】
メッセージ推定部２０３は、β≡B(ξn)を計算することによりメッセージの推定値βを得る（ステップＢｄ２）。このように、メッセージ推定部２０３は、所定の関数Bを用いて、推定された乱数の系列ξnから、メッセージの推定値βを生成する。
【０３２８】
［符号化装置及び方法並びに復号装置及び方法の第二実施形態］
図６及び図７を参照して、通信路３００が１つの入力wnと２つの出力yn,znとを持ち、盗聴者がznを観測している盗聴通信路についての符号を構成する、符号化装置及び方法並びに復号装置及び方法の第二実施形態について説明する。
【０３２９】
＜符号化装置がunを観測しない場合＞
まず、図６を参照して、符号化装置１００が通信路３００の補助情報unを観測しない場合の構成を述べる。
【０３３０】
通信路符号に関する実施形態におけるデータの大まかな流れを説明する。
【０３３１】
乱数系列生成装置１の出力xn≡(x1,x2,…,xn)は集合[Xn]の要素である。
【０３３２】
メッセージbは集合Im[B]の要素であり、Bがm’×n行列である場合はm’次元のベクトルとなる。所定の共有情報であるaは集合Im[A]の要素であり、Aがm×n行列である場合はm次元のベクトルとなる。符号化装置はメッセージbとaから通信路の入力となる符号語wnを求め、通信路に入力する。符号語wn≡(w1,…,wn)は集合[Wn]の要素である。
【０３３３】
通信路に入力されたwnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路の出力yn≡(y1,…,yn)は集合[Yn]の要素である。復号装置はynとaからメッセージbの推定値βを求める。βはIm[B]の要素である。復号装置はynとaからメッセージbの推定値βを求める。βはIm[B]の要素である。
【０３３４】
また、第三者は通信路を盗聴することにより、情報znを通信路の出力として得る。通信路の出力zn≡(z1,…,zn)は集合[Zn]の要素である。
【０３３５】
図６に示すように、符号化装置１００は、乱数系列生成装置１、記憶部１０１及び変換フィルタ部１０２を例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００及び復号装置２００は、通信路３００で接続されている。
【０３３６】
記憶部１０１には、関数A,Bと、所定の共有情報aと、確率分布pXn,pWn|Xnとが記録されている。乱数系列生成装置１及び変換フィルタ部１０２は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３３７】
記憶部２０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Ynが記録されている。記憶部２０１に記録されているこれらの情報は、通信路３００の性質に応じて予め管理者等が設定しておくものとする。乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３３８】
ここで、[A],[B]は、以下の関係を満たすように設定しておく。
【０３３９】
【数１０４】
2014110533.tif 000106
【０３４０】
ここで、H(Xn|Zn)は、以下のpZn(zn),pXn|Zn(xn|zn)によって定まる。
【０３４１】
【数１０５】
2014110533.tif 000107
【０３４２】
xn∈[Xn],yn∈[Yn],zn∈[Zn],wn∈[Wn]とする。通信路３００を特徴づける確率分布をpYnZn|Wnとする。分布pXn,pWn|Xnは設計パラメータであり任意に与えることができるが、通常は(H(Xn|Zn)-H(Xn|Yn))の大きいものを与える。
【０３４３】
【数１０６】
2014110533.tif 000108
【０３４４】
符号化装置１００の乱数系列生成装置１にメッセージbが入力される。
【０３４５】
乱数系列生成装置１は、メッセージb∈Im[B]、所定の共有情報a∈Im[A]に対して、以下の確率分布μに従う乱数の系列xnを発生させる（ステップＢｅ１，図１０）。乱数の系列xnは、変換フィルタ部１０２に送信される。
【０３４６】
【数１０７】
2014110533.tif 000109
【０３４７】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxnとしてもよい。
【０３４８】
乱数系列生成装置１は、このように所定の条件がAxn=a,Bxn=bである場合は、
Im[A]⊂V1,1×V1,2×…×V1,m
Im[B]⊂V2,1×V2,2×…×V2,m’
を満たす集合V1,1,V1,2,…,V1,m,V2,1,…,V2,m’が存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第三実施形態］で説明した方法を適用することにより、乱数の系列xnを例えば生成することができる。
【０３４９】
【数１０８】
2014110533.tif 000110
【０３５０】
変換フィルタ部１０２は、確率分布pWn|Xnに従うランダム又は決定的な変換Fを通して得られた系列wn≡F(xn)を符号化装置１００の出力である符号語として通信路３００に入力する（ステップＢｅ２）。
【０３５１】
通信路３００の出力ynは、復号装置２００の乱数系列推定部２０２に入力される。
【０３５２】
乱数系列推定部２０２は、通信路３００の出力ynから、次式により定義される、xnの推定値ξnを求める（ステップＢｄ１，図１１）。求まったξnは、メッセージ推定部２０３に送信される。
【０３５３】
【数１０９】
2014110533.tif 000111
【０３５４】
なお、上記式によりξnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξnを近似的に求めてもよい。
【０３５５】
このように、乱数系列推定部２０２は、所定の共有情報aを所与としたときに所定の関数Aを満たす複数の値の系列θｎのうち、通信路３００の出力ynを条件としたときにθｎが出現する確率を最大にするθｎをξnとして求め、求まった値の系列ξnを乱数系列生成装置１の出力であった乱数の系列xnとして推定する。
【０３５６】
メッセージ推定部２０３は、β≡B(ξn)を計算することによりメッセージの推定値βを得る（ステップＢｄ２）。このように、メッセージ推定部２０３は、所定の関数Bを用いて、推定された乱数の系列ξnから、メッセージの推定値βを生成する。
【０３５７】
＜符号化装置がunを観測する場合＞
以下では、図７を参照して、通信路３００が２つの入力wnとunを持ち、符号化装置１００がunを観測する場合の構成を述べる。ここで、盗聴者はunを観測できないことを仮定する。
【０３５８】
乱数生成装置１の出力xn≡(x1,x2,…,xn)は有限集合[Xn]の要素である。通信路の入力un≡(u1,…,un)は集合[Un]の要素である。
【０３５９】
メッセージbは集合Im[B]の要素であり、Bがm’×n行列である場合はm’次元のベクトルとなる。所定の共有情報であるaは集合Im[A]の要素であり、Aがm×n行列である場合はm次元のベクトルとなる。符号化装置はメッセージbとaとunとから通信路の入力となる符号語wnを求め、通信路に入力する。符号語wn≡(w1,…,wn)は集合[Wn]の要素である。
【０３６０】
通信路に入力されたwnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路の出力yn≡(y1,…,yn)は集合[Yn]の要素である。復号装置はynとaからメッセージbの推定値βを求める。βはIm[B]の要素である。
【０３６１】
また、第三者は通信路を盗聴することにより、情報znを通信路の出力として得る。通信路の出力zn≡(z1,…,zn)は集合[Zn]の要素である。
【０３６２】
図７に示すように、符号化装置１００は、乱数系列生成装置１、記憶部１０１及び変換フィルタ部１０２を例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００及び復号装置２００は、通信路３００で接続されている。
【０３６３】
記憶部１０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Un,pWn|XnUnとが記録されている。乱数系列生成装置１及び変換フィルタ部１０２は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３６４】
記憶部２０１には、関数A,Bと、所定の共有情報aと、確率分布pXn|Ynが記録されている。記憶部２０１に記録されているこれらの情報は、通信路３００の性質に応じて予め管理者等が設定しておくものとする。乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３６５】
ここで、[A],[B]は、以下の関係を満たすように設定しておく。
【０３６６】
【数１１０】
2014110533.tif 000112
【０３６７】
ここで、H(Xn|Zn)は、以下のpZn(zn),pXn|Zn(xn|zn)によって定まる。
【０３６８】
【数１１１】
2014110533.tif 000113
【０３６９】
xn∈[Xn],yn∈[Yn],zn∈[Zn],un∈[Un],wn∈[Wn]とする。通信路を特徴づける確率分布をpUn,pYnZn|WnUnとする。条件付き確率分布pWn|XnUn,pXn|Unは設計パラメータであり任意に与えることができるが、通常は(min{H(Xn|Un),H(Xn|Zn)}-H(Xn|Yn))が大きいものを与える。ここで、PYn(yn),PXn|Yn(xn|yn)を以下のように定義する。
【０３７０】
【数１１２】
2014110533.tif 000114
【０３７１】
符号化装置１００の乱数系列生成装置１にメッセージb及びunが入力される。
【０３７２】
乱数系列生成装置１は、メッセージb∈Im[B]、通信路３００の入力unと所定の共有情報a∈Im[A]に対して、以下の確率分布μに従う乱数の系列xnを発生させる（ステップＢｅ１，図１０）。乱数の系列xnは、変換フィルタ部１０２に送信される。
【０３７３】
【数１１３】
2014110533.tif 000115
【０３７４】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxnとしてもよい。
【０３７５】
乱数系列生成装置１は、このように所定の条件がAxn=a,Bxn=bである場合は、
Im[A]⊂V1,1×V1,2×…×V1,m
Im[B]⊂V2,1×V2,2×…×V2,m’
を満たす集合V1,1,V1,2,…,V1,m,V2,1,…,V2,m’が存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第三実施形態］及び［乱数系列生成装置及び方法の第四実施形態］で説明した方法を適用することにより、乱数の系列xnを例えば生成することができる。
【０３７６】
【数１１４】
2014110533.tif 000116
【０３７７】
変換フィルタ部１０２は、確率分布pWn|XnUnに従うランダム又は決定的な変換Fを通して得られた系列wn≡F(xn,un)を符号化装置１００の出力である符号語として通信路３００に入力する（ステップＢｅ２）。
【０３７８】
通信路３００の出力ynは、復号装置２００の乱数系列推定部２０２に入力される。
【０３７９】
乱数系列推定部２０２は、通信路３００の出力ynから、次式により定義される、xnの推定値ξnを求める（ステップＢｄ１，図１１）。求まったξnは、メッセージ推定部２０３に送信される。
【０３８０】
【数１１５】
2014110533.tif 000117
【０３８１】
なお、上記式によりξnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξnを近似的に求めてもよい。
【０３８２】
このように、乱数系列推定部２０２は、所定の共有情報aを所与としたときに所定の関数Aを満たす複数の値の系列θｎのうち、通信路３００の出力ynを条件としたときにθｎが出現する確率を最大にするθｎをξnとして求め、求まった値の系列ξnを乱数系列生成装置１の出力であった乱数の系列xnとして推定する。
【０３８３】
メッセージ推定部２０３は、β≡B(ξn)を計算することによりメッセージの推定値βを得る（ステップＢｄ２）。このように、メッセージ推定部２０３は、所定の関数Bを用いて、推定された乱数の系列ξnから、メッセージの推定値βを生成する。
【０３８４】
盗聴者によってunが観測される恐れがある場合は、(b2)を以下の式に置き換えてもよい。
【０３８５】
【数１１６】
2014110533.tif 000118
【０３８６】
ここで、H(Xn|Zn,Un)は、以下のpZn(zn),pXn|Zn(xn|zn)によって定まる。
【０３８７】
【数１１７】
2014110533.tif 000119
【０３８８】
条件付き確率分布pWn|XnUn,pXn|Unは設計パラメータであり任意に与えることができるが、通常は(H(Xn|Zn,Un)-H(Xn|Yn))が大きいものを与える。
【０３８９】
［符号化装置及び方法並びに復号装置及び方法の第三実施形態］
κを１以上の所定の整数とし、K≡{0,1,…,κ},i∈K,xin≡(xi,1,xi,2,…,xi,n),xKn≡{xin}i∈K,Xin≡(Xi,1,Xi,2,…,Xi,n),XKn≡{Xin}i∈Kとする。図８を参照して、通信路３００がκ個の入力xKn≡{xin}i∈Kと１つの出力ynを持ついわゆるマルチプルアクセス通信路についての符号を構成する、符号化装置及び方法並びに復号装置及び方法の第三実施形態について説明する。
【０３９０】
＜符号化装置と復号化装置がunを共有しない場合＞
まず、図８を参照して、符号化装置１００−ｉ及び復号装置２００が、補助情報unを共有しない場合の構成を述べる。
【０３９１】
メッセージbiは集合Im[Bi]の要素であり、Biがm’i×n行列である場合はm’i次元のベクトルとなる。所定の共有情報であるaiは集合Im[Ai]の要素であり、Aiがmi×n行列である場合はmi次元のベクトルとなる。符号化装置はメッセージbiとaiから通信路の入力となる符号語xinを求める。符号語xin≡(xi,1,xi,2,…,xi,n)は集合[Xin]の要素である。
【０３９２】
通信路に入力されたxKnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路の出力yn≡(y1,…,yn)は集合[Yn]の要素である。復号装置はynとaiからメッセージbiの推定値βiを求める。βiはIm[Bi]の要素である。
【０３９３】
図８に示すように、i∈Kとして、符号化装置１００−ｉは、乱数系列生成装置１−ｉ及び記憶部１０１−ｉを例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００−ｉ及び復号装置２００は、通信路３００で接続されている。
【０３９４】
i∈Kとして、記憶部１０１−ｉには、関数Ai,Biと、所定の共有情報aiと、確率分布pXinが記録されている。i∈Kとして、乱数系列生成装置１−ｉは、必要に応じて記憶部１０１−ｉからこれらの記録されている情報を読み込み後述する処理を行う。
【０３９５】
記憶部２０１には、関数{Ai}i∈K,{Bi}i∈Kと、所定の共有情報{ai}i∈Kと、確率分布pXKn|Ynが記録されている。乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０３９６】
ここで、[AK]≡{[Ai]}i∈K,[BK]≡{[Bi]}i∈Kは、任意のi∈KとI⊂Kに対して、以下の関係を満たすように設定しておく。XIn≡{Xin}i∈Iであり、K＼Iは差集合、すなわちKに含まれているがIには含まれない要素からなる集合を表す。
【０３９７】
【数１１８】
2014110533.tif 000120
【０３９８】
また、H(XIn|Yn,XK＼In)は、以下のpYnXK＼In(yn,xnk＼I),pXIn|YnXK＼In(xIn|yn,xK＼In)によって定まる。Σの下付きxInはxIn≡{xin}i∈Iがとりうる値の全てを動かした時の和である。
【０３９９】
【数１１９】
2014110533.tif 000121
【０４００】
xin∈[Xin],yn∈[Yn]とする。通信路を特徴づける確率分布をpYn|XKnとする。{pXin}i∈Kは設計パラメータで任意に与えることができるが、通常は後述の|Im[Bi]|を大きくできるものを選ぶ。ここで、PYn(yn)及びPXKn|Yn(xnK|yn)を以下のように定義する。Σの下付きxKnはxKn≡{xin}i∈Kがとりうる値の全てを動かした時の和である。
【０４０１】
【数１２０】
2014110533.tif 000122
【０４０２】
i∈Kとして、符号化装置１００−ｉの乱数系列生成装置１−ｉにメッセージbiが入力される。
【０４０３】
i∈Kとして、乱数系列生成装置１−ｉは、メッセージbi∈Im[Bi]と所定の共有情報ai∈Im[Ai]に対して、以下の確率分布μに従う乱数の系列xinを発生させ、これを符号化装置１００−ｉの出力である符号語として通信路３００に入力する（ステップＢｅ１，図１０）。
【０４０４】
【数１２１】
2014110533.tif 000123
【０４０５】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxinとしてもよい。
【０４０６】
乱数系列生成装置１−ｉは、このように所定の条件がAi(xin)=ai,Bi(xin)=biである場合は、
【０４０７】
【数１２２】
2014110533.tif 000124
【０４０８】
を満たす集合Vi,1,1,Vi,1,2,…,Vi,1,mi,Vi,2,1,…,Vi,2,m’iが存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第四実施形態］で説明した方法を適用することにより、乱数の系列xinを例えば生成することができる。
【０４０９】
【数１２３】
2014110533.tif 000125
【０４１０】
通信路３００の出力ynは、復号装置２００の乱数系列推定部２０２に入力される。
【０４１１】
復号装置２００は、乱数系列推定部２０２において通信路３００の出力ynと予め定められた{ai}i∈Kから、次式により定義される、xKn≡{xin}i∈Kの推定値ξKnを求める（ステップＢｄ１，図１１）。求まったξKnは、メッセージ推定部２０３に送信される。
【０４１２】
【数１２４】
2014110533.tif 000126
【０４１３】
なお、上記式によりξKnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξKnを近似的に求めてもよい。
【０４１４】
このように、乱数系列推定部２０２は、所定の共有情報{ai}i∈Kを所与としたときに所定の関数{Ai}i∈Kを満たす値θｉｎの系列θＫｎのうち、通信路３００の出力ynを条件としたときにθＫｎが出現する確率を最大にするθＫｎをξKnとして求め、求まった値の系列ξnKを乱数系列発生装置１の出力であった乱数の系列xKnとして推定する。ここで、θKn≡{θin}i∈K,ξKn≡{ξin}i∈Kである。
【０４１５】
メッセージ推定部２０３は、i∈Kとして、βi≡Bi(ξin)を計算することによりメッセージの推定値βiを得る（ステップＢｄ２）。このように、メッセージ推定部２０３は、所定の関数Biを用いて、推定された乱数の系列ξinから、メッセージの推定値βiを生成する。
【０４１６】
＜符号化装置と復号化装置がunを共有する場合＞
図８を参照して、符号化装置１００−ｉ及び復号装置２００が、補助情報unを共有する場合の構成を述べる。
【０４１７】
乱数系列生成装置１−ｉの出力xin≡(xi,1,xi,2,…,xi,n)は集合[Xin]の要素である。共有情報un≡(u1,…,un)は集合[Un]の要素であり、予め符号器と復号器の記憶部に記憶されている。
【０４１８】
メッセージbiは集合Im[Bi]の要素であり、Biがm’i×n行列である場合はm’i次元のベクトルとなる。所定の共有情報であるaiは集合Im[Ai]の要素であり、Aiがmi×n行列である場合はmi次元のベクトルとなる。符号化装置はメッセージbiとaiとunとから通信路の入力となる符号語xinを求め、通信路に入力する。符号語xin≡(xi,1,…,xi,n)は集合[Xn]の要素である。
【０４１９】
通信路に入力されたxKnは、雑音等の影響を受けて変化しynとして通信路から出力される。ここで、通信路の出力yn≡(y1,…,yn)は集合[Yn]の要素である。復号装置はynとaiからメッセージbiの推定値βiを求める。βiはIm[Bi]の要素である。
【０４２０】
図８に示すように、i∈Kとして、符号化装置１００−ｉは、乱数系列生成装置１−ｉ及び記憶部１０１−ｉを例えば備える。復号装置２００は、記憶部２０１、乱数系列推定部２０２及びメッセージ推定部２０３を例えば備える。符号化装置１００−ｉ及び復号装置２００は、通信路３００で接続されている。
【０４２１】
i∈Kとして、記憶部１０１−ｉには、関数Ai,Biと、所定の共有情報aiおよびunと、確率分布pXin|Unが記録されている。i∈Kとして、乱数系列生成装置１−ｉは、必要に応じて記憶部１０１−ｉからこれらの記録されている情報を読み込み後述する処理を行う。
【０４２２】
記憶部２０１には、関数{Ai}i∈K,{Bi}i∈Kと、所定の共有情報{ai}i∈Kおよびun∈[Un]と、確率分布pXKn|YnUnが記録されている。乱数系列推定部２０２及びメッセージ推定部２０３は、必要に応じて記憶部２０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０４２３】
ここで、[AK]≡{[Ai]}i∈K,[BK]≡{[Bi]}i∈Kは、任意のi∈KとI∈Kに対して、以下の関係を満たすように設定しておく。XIn≡{Xin}i∈Iであり、K＼Iは差集合、すなわちKに含まれているがIには含まれない要素からなる集合を表す。
【０４２４】
【数１２５】
2014110533.tif 000127
【０４２５】
また、H(XIn|Yn,XK＼In,Un)は、以下のpYnXK＼InUn(yn,xnk＼I,un),pXIn|YnXK＼InUn(xIn|yn,xK＼In,un)によって定まる。Σの下付きxInはxIn≡{xin}i∈Iがとりうる値の全てを動かした時の和である。
【０４２６】
【数１２６】
2014110533.tif 000128
【０４２７】
xin∈[Xin],yn∈[Yn]とする。通信路を特徴づける確率分布をpYn|XKnとする。pUn,{pXin|Un}i∈Kは設計パラメータで任意に与えることができるが、通常は後述の|Im[Bi]|を大きくできるものを選ぶ。ここで、PYn|Un(yn|un)及びPXKn|YnUn(xnK|yn,un)を以下のように定義する。Σの下付きxKnはxKn≡{xin}i∈Kがとりうる値の全てを動かした時の和である。
【０４２８】
【数１２７】
2014110533.tif 000129
【０４２９】
符号化装置１００−ｉの乱数系列生成装置１−ｉにメッセージbiが入力される。
【０４３０】
i∈Kとして、乱数系列生成装置１−ｉは、メッセージbi∈Im[Bi]と記憶部１０１−ｉに記憶された所定の共有情報ai∈Im[Ai]およびun∈[Un]に対して、以下の確率分布μに従う乱数の系列xinを発生させ、これを符号化装置１００−ｉの出力である符号語として通信路３００に入力する（ステップＢｅ１，図１０）。
【０４３１】
【数１２８】
2014110533.tif 000130
【０４３２】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxinとしてもよい。
【０４３３】
乱数系列生成装置１−ｉは、このように所定の条件がAi(xin)=ai,Bi(xin)=biである場合は、
【０４３４】
【数１２９】
2014110533.tif 000131
【０４３５】
を満たす集合Vi,1,1,Vi,1,2,…,Vi,1,mi,Vi,2,1,…,Vi,2,m’iが存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第四実施形態］で説明した方法を適用することにより、乱数の系列xinを例えば生成することができる。
【０４３６】
【数１３０】
2014110533.tif 000132
【０４３７】
通信路３００の出力ynが、復号装置２００の乱数系列推定部２０２に入力される。
【０４３８】
復号装置２００は、乱数系列推定部２０２において通信路３００の出力ynと記憶部２０１に記憶された予め定められた{ai}i∈Kおよびuｎから、次式により定義される、xKn≡{xin}i∈Kの推定値ξKnを求める（ステップＢｄ１，図１１）。求まったξKnは、メッセージ推定部２０３に送信される。
【０４３９】
【数１３１】
2014110533.tif 000133
【０４４０】
このように、乱数系列推定部２０２は、所定の共有情報{ai}i∈Kを所与としたときに所定の関数{Ai}i∈Kを満たすθｉｎの系列θＫｎのうち、通信路３００の出力ynと記憶部２０１に記憶された共有情報uｎとを条件としたときにθＫｎが出現する確率を最大にするθＫｎをξKnとして求め、求まった値の系列ξKnを乱数系列生成装置１の出力であった乱数の系列xKnとして推定する。ここで、θKn≡{θin}i∈K,ξKn≡{ξin}i∈Kである。
【０４４１】
メッセージ推定部２０３は、i∈Kとして、βi≡Bi(ξin)を計算することによりメッセージの推定値βiを得る（ステップＢｄ２）。このように、メッセージ推定部２０３は、所定の関数Biを用いて、推定された乱数の系列ξinから、メッセージの推定値βiを生成する。
【０４４２】
［符号化装置及び方法並びに復号装置及び方法の第四実施形態］
κ,λのそれぞれを１以上の所定の整数とする。κとλは同じ値でも異なる値であってもよい。K≡{0,1,…,κ},L≡{0,1,…,λ},i∈K,j∈Lとする。図９を参照して、通信路３００が１つの入力wnとλ個の出力yLn≡{yjn}j∈Lを持ついわゆるブロードキャスト通信路についての符号を構成する、符号化装置及び方法並びに復号装置及び方法の第四実施形態について説明する。
【０４４３】
j∈Lとして、復号装置２００−ｊが復号するメッセージのインデックスの集合をDj⊂Kとする。すなわち、j∈Lとして、復号装置２００−ｊは、bDj≡{bi}i∈Djを再生する。
【０４４４】
＜符号化装置と復号化装置がunを共有しない場合＞
まず、図９を参照して、符号化装置１００及び復号装置２００−ｊが、補助情報unを共有しない場合の構成を述べる。
【０４４５】
乱数系列生成装置１の出力xKn≡{xin}i∈K （ここでxin≡ (xi,1,xi,2,…,xi,n)）は集合[XKn]の要素である。
【０４４６】
メッセージbi（ｉ＝1,2,…,K)は集合Im[Bi]の要素であり、Biがm’i×n行列である場合はm’i次元のベクトルとなる。所定の共有情報であるai（ｉ＝1,2,…,K)は集合Im[Ai]の要素であり、Aiがmi×n行列である場合はmi次元のベクトルとなる。符号化装置はメッセージ{bi}i∈Kと{ai}i∈Kとから乱数の系列xKn≡{xin}i∈Kを求め、求めた乱数の系列xKnを通信路入力となる符号語wn≡F(xKn)に変換し、wnを通信路に入力する。wn≡ (w1,w2,…,wn)は集合[Wn]の要素である。
【０４４７】
通信路入力wnは雑音等の影響を受けて変化しyn≡{yjn}i∈Ｌとして通信路から出力される。ここで、通信路の出力yjn≡(yj,1,…,yj,n)は集合[Yjn]の要素である。集合[Yjn]は、有限集合とは限らないとする。復号装置２００−ｊはyjnと{ai}i∈Djからメッセージ{bi}i∈Djの推定値{βi}i∈Djを求める。βiはIm[Bi]の要素である。
【０４４８】
図９に示すように、符号化装置１００は、乱数系列生成装置１及び記憶部１０１を例えば備える。j∈Lとして、復号装置２００−ｊは、記憶部２０１−ｊ、乱数系列推定部２０２−ｊ及びメッセージ推定部２０３−ｊを例えば備える。j∈Lとして、符号化装置１００及び復号装置２００−ｊは、通信路３００で接続されている。
【０４４９】
記憶部１０１には、関数{Ai}i∈K,{Bi}i∈Kと、所定の共有情報{ai}i∈Kと、確率分布pXKn,pWn|XKnが記録されている。乱数系列生成装置１は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０４５０】
j∈Lとして、記憶部２０１−ｊには、関数{Aj}j∈Dj,{Bj}j∈Djと、所定の共有情報{ai}i∈Djと、確率分布pDjn|Yjnが記録されている。乱数系列推定部２０２−ｊ及びメッセージ推定部２０３−ｊは、必要に応じて記憶部２０１−ｊからこれらの記録されている情報を読み込み後述する処理を行う。
【０４５１】
ここで、[AK]≡{[Ai]}i∈K,[BK]≡{[Bi]}i∈Kは、任意のI⊂K,j∈L,I’⊂Dj⊂Kに対して、以下の関係を満たすように設定しておく。AiとBiは定義域が同じである。一方、i≠i’である場合には、(Ai,Bi)の定義域と(Ai’,Bi’)の定義域とは異なっていてもよい。
【０４５２】
【数１３２】
2014110533.tif 000134
【０４５３】
また、H(XI’n|YjnXDj＼I’n),H(XIn)は、以下のp_(YjnXDj＼I’n)(yjnxDj＼I’n),p_(XI’n|YjnXDj＼I’n)(xI’n|yjn,xDj＼I’n),pXIn(xIn)によって定まる。
【０４５４】
【数１３３】
2014110533.tif 000135
【０４５５】
xn∈[Xn],yjn∈[Yjn]とする。通信路を特徴づける確率分布をpYLn|Wnとする。pXKn,pWn|XKnは設計パラメータで任意に与えることができるが、通常は後述の|Im[Bi]|を大きくできるものを選ぶ。ここで、PYin(yin)及びPXDjn|Yjn(xDjn|yjn)を以下のように定義する。
【０４５６】
【数１３４】
2014110533.tif 000136
【０４５７】
符号化装置１００の乱数系列生成装置１にメッセージb K≡{bi}i∈K(bi∈Im[Bi])が入力される。
【０４５８】
乱数系列生成装置１は、メッセージbK≡{bi}i∈K(bi∈Im[Bi])と所定の共有情報{ai}i∈K(ai∈Im[Ai])に対して、以下の確率分布μに従う乱数の系列xKn≡{xin}i∈Kを発生させる（ステップＢｅ１，図１０）。乱数の系列xKnは、変換フィルタ部１０２に送信される。
【０４５９】
【数１３５】
2014110533.tif 000137
【０４６０】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxKnとしてもよい。
【０４６１】
乱数系列生成装置１は、このように所定の条件がAi(xin)=ai,Bi(xin)=biである場合は、
【０４６２】
【数１３６】
2014110533.tif 000138
【０４６３】
を満たす集合Vi,1,1,Vi,1,2,…,Vi,1,mi,Vi,2,1,…,Vi,2,m’iが存在することを仮定して、以下の定義に基づいて［乱数系列生成装置及び方法の第四実施形態］及び［乱数系列生成装置及び方法の第五実施形態］で説明した方法を適用することにより、乱数の系列xKnを例えば生成することができる。
【０４６４】
【数１３７】
2014110533.tif 000139
【０４６５】
変換フィルタ部１０２は、確率分布pWn|XKnに従うランダム又は決定的な変換Fを通して得られた系列wn≡F(xKn)を符号化装置１００の出力である符号語として通信路３００に入力する（ステップＢｅ２）。
【０４６６】
j∈Lとして、通信路３００の出力yjnは、復号装置２００−ｊの乱数系列推定部２０２−ｊに入力される。
【０４６７】
j∈Lとして、復号装置２００−ｊは、乱数系列推定部２０２−ｊにおいて通信路３００の出力yjnと予め定められた{ai}i∈Djから、次式により定義される、xDjn≡{xin}i∈Djの推定値ξDjnを求める（ステップＢｄ１，図１１）。求まったξDjnは、メッセージ推定部２０３−ｊに送信される。
【０４６８】
【数１３８】
2014110533.tif 000140
【０４６９】
なお、上記式によりξDjnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξDjnを近似的に求めてもよい。
【０４７０】
このように、j∈Lとして、乱数系列推定部２０２−ｊは、所定の共有情報{ai}i∈Djを所与としたときに所定の関数{Ai}i∈Djを満たす値θｉｎの系列θＤｊｎのうち、通信路３００の出力yjnを条件としたときにθＤｊｎが出現する確率を最大にするθＤｊｎをξDjnとして求め、求まった値の系列ξDjnを乱数系列生成装置１の出力の一部であった乱数の系列xDjnとして推定する。ここで、θDjn≡{θin}i∈Dj,ξDjn≡{ξin}i∈Djである。
【０４７１】
j∈Lとして、メッセージ推定部２０３−ｊは、各i∈Dｊに対してβi≡Bi(ξin)を計算することによりメッセージの推定値βiを得る（ステップＢｄ２）。このように、j∈Lとして、メッセージ推定部２０３は、所定の関数{Bi}i∈Djを用いて、推定された乱数の系列ξinから、メッセージの推定値βiを生成する。
【０４７２】
＜符号化装置と復号化装置がunを共有する場合＞
図９を参照して、符号化装置１００及び復号装置２００−ｊが、補助情報unを共有する場合の構成を述べる。
【０４７３】
乱数系列生成装置１の出力xKn≡{xin}i∈K （ここでxin≡ (xi,1,xi,2,…,xi,n)）は集合[XKn]の要素である。共有情報un≡(u1,…,un)は集合[Un]の要素であり、予め符号器と復号器の記憶部に記憶されている。集合[Un]は、有限集合とは限らないとする。
【０４７４】
メッセージbi（ｉ＝1,2,…,K)は集合Im[Bi]の要素であり、Biがm’i×n行列である場合はm’i次元のベクトルとなる。所定の共有情報であるai（ｉ＝1,2,…,K)は集合Im[Ai]の要素であり、Aiがmi×n行列である場合はmi次元のベクトルとなる。符号化装置はメッセージ{bi}i∈Kと{ai}i∈Kとunとから乱数の系列xKn≡{xin}i∈Kを求め、求めた乱数の系列xKnを通信路入力となる符号語wn≡F(xKn, un)に変換し、wnを通信路に入力する。wn≡ (w1,w2,…,wn)は集合[Wn]の要素である。
【０４７５】
通信路に入力されたwnは、雑音等の影響を受けて変化しyn≡{yjn}i∈Ｌとして通信路から出力される。ここで、通信路の出力yjn≡(yj,1,…,yj,n)は集合[Yjn]の要素である。復号装置２００−ｊはyjnと{ai}i∈Djとunとからメッセージ{bi}i∈Djの推定値βiを求める。βiはIm[Bi]の要素である。
【０４７６】
図９に示すように、符号化装置１００は、乱数系列生成装置１及び記憶部１０１を例えば備える。j∈Lとして、復号装置２００−ｊは、記憶部２０１−ｊ、乱数系列推定部２０２−ｊ及びメッセージ推定部２０３−ｊを例えば備える。j∈Lとして、符号化装置１００及び復号装置２００−ｊは、通信路３００で接続されている。
【０４７７】
記憶部１０１には、関数{Ai}i∈K,{Bi}i∈Kと、所定の共有情報{ai}i∈Kおよびun∈[Un]と、確率分布pXKn|Un,pWn|XKnUnが記録されている。乱数系列生成装置１は、必要に応じて記憶部１０１からこれらの記録されている情報を読み込み後述する処理を行う。
【０４７８】
j∈Lとして、記憶部２０１−ｊには、関数{Aj}j∈Dj,{Bj}j∈Djと、所定の共有情報{ai}i∈Djおよびun∈[Un]と、確率分布pDjn|YjnUnが記録されている。乱数系列推定部２０２−ｊ及びメッセージ推定部２０３−ｊは、必要に応じて記憶部２０１−ｊからこれらの記録されている情報を読み込み後述する処理を行う。
【０４７９】
ここで、[AK]≡{[Ai]}i∈K,[BK]≡{[Bi]}i∈Kは、任意のI⊂K,j∈L,I’⊂Djに対して、以下の関係を満たすように設定しておく。AiとBiは定義域が同じである。一方、i≠i’である場合には、(Ai,Bi)の定義域と(Ai’,Bi’)の定義域とは異なっていてもよい。
【０４８０】
【数１３９】
2014110533.tif 000141
【０４８１】
また、H(XI’n|YjnXDj＼I’n,Un),H(XIn|Un)は、以下のp_(YjnXDj＼I’nUn)(yjnxDj＼I’n,un),p_(XI’n|YjnXDj＼I’nUn)(xI’n|yjn,xDj＼I’n,un),pXInUn(xIn|un)によって定まる。
【０４８２】
【数１４０】
2014110533.tif 000142
【０４８３】
xn∈[Xn],yjn∈[Yjn]とする。通信路を特徴づける確率分布をpYLn|Wnとする。pUn,pXKn|Un,pWn|XKnUnは設計パラメータで任意に与えることができるが、通常は後述の|Im[Bi]|を大きくできるものを選ぶ。ここで、PYin|Un(yin|un)及びPXDjn|YjnUn(xDjn|yjn,un)を以下のように定義する。
【０４８４】
【数１４１】
2014110533.tif 000143
【０４８５】
符号化装置１００の乱数系列生成装置１にメッセージb K≡{bi}i∈K(bi∈Im[Bi])及びunが入力される。
【０４８６】
乱数系列生成装置１は、メッセージbK≡{bi}i∈K(bi∈Im[Bi])と記憶部１０１に記憶された所定の共有情報{ai}i∈K(ai∈Im[Ai])およびunに対して、以下の確率分布μに従う乱数の系列xKn≡{xin}i∈Kを発生させる（ステップＢｅ１，図１０）。乱数の系列xKnは、変換フィルタ部１０２に送信される。
【０４８７】
【数１４２】
2014110533.tif 000144
【０４８８】
ここで、ステップＢｅ１において、確率分布μに従う乱数の系列を複数個発生させた中から一つ選択したものをxKnとしてもよい。
【０４８９】
乱数系列生成装置１は、このように所定の条件がAi(xin)=ai,Bi(xin)=biである場合は、
【０４９０】
【数１４３】
2014110533.tif 000145
【０４９１】
を満たす集合V1,1,V1,2,…,V1,mi,V2,1,…,V2,m’iが存在することを仮定して、以下の定義に基づいて[乱数系列生成装置及び方法の第四実施形態］及び［乱数系列生成装置及び方法の第五実施形態］で説明した方法を適用することにより、乱数の系列xKnを例えば生成することができる。
【０４９２】
【数１４４】
2014110533.tif 000146
【０４９３】
変換フィルタ部１０２は、確率分布pWn|XKnUnに従うランダム又は決定的な変換Fを通して得られた系列wn≡F(xKn,un)を符号化装置１００の出力である符号語として通信路３００に入力する（ステップＢｅ２）。
【０４９４】
j∈Lとして、通信路３００の出力yjnは、復号装置２００−ｊの乱数系列推定部２０２−ｊに入力される。
【０４９５】
j∈Lとして、復号装置２００−ｊは、乱数系列推定部２０２−ｊにおいて通信路３００の出力yjnと記憶部２０１−ｊに記憶された{ai}i∈Djとunとから、次式により定義される、xDjn≡{xin}i∈Djの推定値ξDjnを求める（ステップＢｄ１，図１１）。求まったξDjnは、メッセージ推定部２０３−ｊに送信される。
【０４９６】
【数１４５】
2014110533.tif 000147
【０４９７】
なお、上記式によりξDjnを求める代わりに、例えば参考文献２，３に記載されているsum-productアルゴリズムや例えば参考文献４，５に記載されている線形計画法を用いてξDjnを近似的に求めてもよい。
【０４９８】
このように、j∈Lとして、乱数系列推定部２０２−ｊは、所定の共有情報{ai}i∈Djを所与としたときに所定の関数{Ai}i∈Djを満たす値θｉｎの系列θＤｊｎのうち、通信路３００の出力yjnと記憶部２０１−ｊに記憶された共有情報unを条件としたときにθＤｊｎが出現する確率を最大にするθＤｊｎをξDjnとして求め、求まった値の系列ξDjnを乱数系列生成装置１の出力の一部であった乱数の系列xDjnとして推定する。ここで、θDjn≡{θin}i∈Dj,ξDjn≡{ξin}i∈Djである。
【０４９９】
j∈Lとして、メッセージ推定部２０３−ｊは、各i∈Dｊに対してβi≡Bi(ξin)を計算することによりメッセージの推定値βiを得る（ステップＢｄ２）。このように、j∈λとして、メッセージ推定部２０３は、所定の関数{Bi}i∈Djを用いて、推定された乱数の系列ξinから、メッセージの推定値βiを生成する。
【０５００】
参考文献６から８に記載されている従来技術による従来技術では、ブロック長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.
〔参考文献７〕J. Muramatsu and S. Miyake “Construction of codes for wiretap channel and secret key agreement from correlated source outputs based on hash property,” IEEE Trans. Inform. Theory, vol. IT-58, no. 2, pp. 671-692, Feb. 2012.
〔参考文献８〕J. Muramatsu and S. Miyake, “Construction of multiple access channel code based on hash property,” Proc. 2011 IEEE Int. Symp. Inform. Theory, St. Ptersburg, Russia, pp. 2274-2278, 2011.
【０５０２】
これに対して、［符号化装置及び方法並びに復号装置及び方法の第一実施形態］から［符号化装置及び方法並びに復号装置及び方法の第四実施形態］における乱数の系列の生成において、例えば、ステップＡ２でsum-product アルゴリズムを適用してO(n)で実行することを仮定し、ステップＡ６及びステップＡ７の計算時間はO(n2)であることを仮定すれば、第一実施形態から第二実施形態で述べた符号化及び復号のそれぞれの計算時間はO(n2)となる。このように、乱数の系列の生成を多項式時間で行うことにより、符号化及び復号のそれぞれを多項式時間で行うことができる。
【０５０３】
以下、［符号化装置及び方法並びに復号装置及び方法の第一実施形態］から［符号化装置及び方法並びに復号装置及び方法の第四実施形態］による通信路符号の誤り確率が０に収束することを証明する。以下の証明において、[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]を次のように定義する。
【０５０７】
【数１４６】
2014110533.tif 000148
【０５０８】
集合CA(a),CAB(a,b)を次のように定義する。
【０５０９】
【数１４７】
2014110533.tif 000149
【０５１０】
関数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]に対して
【０５１３】
【数１４８】
2014110533.tif 000150
【０５１４】
及び
【０５１５】
【数１４９】
2014110533.tif 000151
【０５１６】
を満たすとき、{([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]を次のように定義する。
【０５２０】
【数１５０】
2014110533.tif 000152
【０５２１】
[A]×[B]上の確率分布pAsBsを次のように定義する。
【０５２２】
【数１５１】
2014110533.tif 000153
【０５２３】
(αAsBs,βAsBs)を次のように定義する。
【０５２４】
【数１５２】
2014110533.tif 000154
【０５２５】
このとき、新たなアンサンブル([An]×[Bn],pAsBs,n)}n=1∞は、{αAsBs(n),βAsBs(n)}n=1∞-ハッシュ性を持つ。
【０５２６】
補題2 ([4,Lemma 1])． ([A],pAs)が(H3)を満たすとき、任意のT,T’⊂[Un]に対して、以下の式が成立する。
【０５２７】
【数１５３】
2014110533.tif 000155
【０５２８】
補題3 ([3、Lemma 1])． ([A],pA)が(H3')を満たすとき、任意のT⊂[Un],un∈[Un]に対して、以下の式が成立する。
【０５２９】
【数１５４】
2014110533.tif 000156
【０５３０】
補題4 ([5,Lemma 4])． ([A],pAs) が(H3)を満たすとき、任意の関数Q:[Un]→[0,1)とT⊂[Un]に対して、以下の式が成立する。
【０５３１】
【数１５５】
2014110533.tif 000157
【０５３２】
ここで、Q(T)は次のように定義される。
【０５３３】
【数１５６】
2014110533.tif 000158
【０５３４】
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)を次のように定義する。
【０５３６】
【数１５７】
2014110533.tif 000159
【０５３７】
集合[H’]⊂[H]を与えたときαAs(n),βAs(n)を次のように定義する。
【０５３８】
【数１５８】
2014110533.tif 000160
【０５３９】
ここで、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に収束することを証明する。
【０５４４】
通信路入力の集合[Xn]を有限集合、通信路出力の集合[Yn]を無限集合、連続集合を含む任意の集合とする。
【０５４５】
関数A:[Xn]→Im[A],B:[Xn]→Im[B]のアンサンブルを考える。ここで、全てのメッセージからなる集合をIm[B]とする。
【０５４６】
以下では、関数A∈[A],B ∈[B],a∈Im[A]を固定し、これらが符号化装置と復号装置で利用できることを仮定する。
【０５４７】
符号化装置を構成するために制約条件を満たす乱数発生器を利用する。X~n≡X~nAB(a,b)を以下の分布μに従う確率変数とする。
【０５４８】
【数１５９】
2014110533.tif 000161
【０５４９】
符号化装置Φn:Im[B]→[Xn]と復号装置ψn:[Yn]→Im[B]を次のように定義する。
【０５５０】
【数１６０】
2014110533.tif 000162
【０５５１】
ここで、pXn(CAB(a,b))=0のときは符号化装置は符号化エラーを宣言する。またgAを次のように定義する。
【０５５２】
【数１６１】
2014110533.tif 000163
【０５５３】
誤り確率Error(A,B,a) は次のように定義される。
【０５５４】
【数１６２】
2014110533.tif 000164
【０５５５】
定理1.
【０５５６】
【数１６３】
2014110533.tif 000165
【０５５７】
を満たせば、任意の>0と十分大きなnに対して、あるA∈[A],B∈[B],a∈Im[A]が存在して、以下の式を満たす。
【０５５８】
【数１６４】
2014110533.tif 000166
【０５５９】
定常エルゴード通信路pYn|Xnに対して、pXnを
【０５６０】
【数１６５】
2014110533.tif 000167
【０５６１】
を達成する分布にとり、nr をH(Xn|Yn)に近付ける事により、Rを
【０５６２】
【数１６６】
2014110533.tif 000168
【０５６３】
に近付ける事ができる。
【０５６４】
証明:
【０５６５】
【数１６７】
2014110533.tif 000169
【０５６６】
とする。(B9),(B10)より、
【０５６７】
【数１６８】
2014110533.tif 000170
【０５６８】
を満たすε>0が存在する。
【０５６９】
T_をTの下付きバーとし、T-をTの上付きバーとし、T_X⊂[Xn],T-X|Y⊂[Xn]×[Yn]を以下のように定義する。
【０５７０】
【数１６９】
2014110533.tif 000171
【０５７１】
[1,Theorem 16.8.1]より、以下の式が成り立つ。
【０５７２】
【数１７０】
2014110533.tif 000172
【０５７３】
(xn,yn)∈T-X|Y,gA(Axn|yn)≠xnを仮定する。このとき、θ≠xnと
【０５７４】
【数１７１】
2014110533.tif 000173
【０５７５】
を満たすθn∈CA(Axn) が存在する。したがって、T-X|Y(yn)を
【０５７６】
【数１７２】
2014110533.tif 000174
【０５７７】
と定義することによりT-X|Y(yn)∩CA(Axn)≠φを満たしている。任意の(xn,yn)∈T-X|Yに対して、以下の式が成立する。
【０５７８】
【数１７３】
2014110533.tif 000175
【０５７９】
ここで、χを次のように定義する。
【０５８０】
【数１７４】
2014110533.tif 000176
【０５８１】
また、2番目の不等式では補題3、3番目の不等式では
【０５８２】
【数１７５】
2014110533.tif 000177
【０５８３】
を用いた。続いて、以下の式が成立する。
【０５８４】
【数１７６】
2014110533.tif 000178
【０５８５】
ここで、最後の不等式では(B18)を用いた。また、以下の式が成立する。
【０５８６】
【数１７７】
2014110533.tif 000179
【０５８７】
ここで、2番目の不等式は補題4を用いた。asの分布を一様分布とするとき、以下の式が成立する。
【０５８８】
【数１７８】
2014110533.tif 000180
【０５８９】
ここで最初の不等式では、以下の式を用いた。
【０５９０】
【数１７９】
2014110533.tif 000181
【０５９１】
また2番目の不等式では(B19)(B20)を用いた。不等式(B12),(B13),(B21)とn→∞とすることによりαAs→1,βAs→0,αAsBs→1,βAB→0,pXn([T_X]c)→0,pXnYn([T_XY]c)→0が成り立つことから、(B21)の右辺はn→∞とともに0に近付く。このことから定理の成立がいえる。
【０５９２】
［変形例等］
上記装置及び方法において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０５９３】
また、乱数系列生成装置、符号化装置及び復号装置における処理手段をコンピュータによって実現する場合、乱数系列生成装置、符号化装置及び復号装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、乱数系列生成装置、符号化装置及び復号装置における処理手段がコンピュータ上で実現される。
【０５９４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０５９５】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０５９６】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【０５９７】
１  乱数系列生成装置
１１  制御部
１２  確率分布生成部
１３  乱数生成部
１４  記憶部
１５  乱数推定部
１６  一様乱数生成部
１００  符号化装置
１０１  記憶部
１０２  変換フィルタ部
２００  復号装置
２０１  記憶部
２０２  乱数系列推定部
２０３  メッセージ推定部
３００  通信路
【図１】
2014110533.tif 000189
【図２】
2014110533.tif 000190
【図３】
2014110533.tif 000191
【図４】
2014110533.tif 000192
【図５】
2014110533.tif 000193
【図６】
2014110533.tif 000194
【図７】
2014110533.tif 000195
【図８】
2014110533.tif 000196
【図９】
2014110533.tif 000197
【図１０】
2014110533.tif 000198
【図１１】
2014110533.tif 000199