(57)【要約】【課題】少ない計算量で解を探索することができる解探索装置、解探索方法および解探索プログラムを提供すること。【解決手段】解探索装置１０は、２元有限体の直積を要素とする系列を求める最適化問題の解を探索する解探索装置であり、予め算出された複数のヒストグラムを、ヒストグラムより定まる評価関数を用いて評価するヒストグラム評価部１２と、ヒストグラム評価部１２による評価順にヒストグラムに対応する条件式を取得して解を探索する解探索部１３とを備える。【選択図】図１
2011150465.tif 000002
【特許請求の範囲】
【請求項１】
２元有限体の直積を要素とする系列を求める最適化問題の解を探索する解探索装置であって、
予め算出された複数のヒストグラムを、ヒストグラムより定まる評価関数を用いて評価するヒストグラム評価手段と、
前記ヒストグラム評価手段による評価順にヒストグラムに対応する条件式を取得して解を探索する解探索手段と
を備えることを特徴とする解探索装置。
【請求項２】
前記評価関数は、ヒストグラムより定まる相対頻度と確率分布との距離に応じてヒストグラムを評価することを特徴とする請求項１に記載の解探索装置。
【請求項３】
ブロードキャスト通信路符号に関する解を探索することを特徴とする請求項１または２に記載の解探索装置。
【請求項４】
相関のある情報源符号に関する解を探索することを特徴とする請求項１または２に記載の解探索装置。
【請求項５】
相関のある加法的雑音を伴う通信路符号に関する解を探索することを特徴とする請求項１または２に記載の解探索装置。
【請求項６】
２元有限体の直積を要素とする系列を求める最適化問題の解を探索する解探索方法であって、
予め算出された複数のヒストグラムを、ヒストグラムより定まる評価関数を用いて評価するヒストグラム評価工程と、
前記ヒストグラム評価工程における評価順にヒストグラムに対応する条件式を取得して解を探索する解探索工程と
を含むことを特徴とする解探索方法。
【請求項７】
前記評価関数は、ヒストグラムより定まる相対頻度と確率分布との距離に応じてヒストグラムを評価することを特徴とする請求項６に記載の解探索方法。
【請求項８】
ブロードキャスト通信路符号に関する解を探索することを特徴とする請求項６または７に記載の解探索方法。
【請求項９】
相関のある情報源符号に関する解を探索することを特徴とする請求項６または７に記載の解探索方法。
【請求項１０】
相関のある加法的雑音を伴う通信路符号に関する解を探索することを特徴とする請求項６または７に記載の解探索方法。
【請求項１１】
コンピュータを請求項１〜５のいずれか１つに記載の解探索装置として機能させることを特徴とする解探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、解探索装置、解探索方法および解探索プログラムに関し、特に、少ない計算量で解を探索することができる解探索装置、解探索方法および解探索プログラムに関する。
【背景技術】
【０００２】
従来より、２元有限体（以下、「ＧＦ（２）」ともいう）上の線形方程式を満たしながら、与えられた目的関数を最大化／最小化する技術が知られている。例えば、非特許文献１および２で紹介されている誤り訂正符号の復号方法等では、ある関数ｄを定めて、以下の式（１）により入力メッセージの復元が実現される。
【０００３】
【数１】
2011150465.tif 000003
【０００４】
ここで、ｕは、式（２）に示すような、ＧＦ（２）上のｎ次元の列ベクトルであり、ｕｊ（ｊ＝１，２，・・・，ｎ）は、全てＧＦ（２）の要素である。また、Ａは、式（３）に示すような、ＧＦ（２）上のｌ×ｎ行列である。また、ｃは、ｌ次元のベクトルであり、例えば、式（４）のように表現される。
【０００５】
【数２】
2011150465.tif 000004
【０００６】
【数３】
2011150465.tif 000005
【０００７】
【数４】
2011150465.tif 000006
【０００８】
非特許文献１で提案されている線形計画法を用いた最適化問題の解法についてさらに詳しく説明する。ｇＡ（ｃ）は、ＧＦ（２）上の線形方程式Ａｕ＝ｃを制約条件として目的関数ｄ（ｕ）を最小化する問題である。また、式（１）は、厳密には整数計画問題であり、実数空間上での線形計画問題ではない。
【０００９】
なお、以下の議論では目的関数とその最大化／最小化には影響しないので、線形目的関数をｄ（ｕ）と記し、最大化／最小化を単に「最適化」と呼ぶことがある。また、以下では、ＧＦ（２）上の線形方程式Ａｕ＝ｃを制約条件として目的関数ｆ（ｕ）を最適化する問題を単に「ＧＦ（２）上の線形方程式を制約条件とする整数計画問題」と呼ぶことがある。
【００１０】
ＧＦ（２）上の線形方程式を制約条件とする整数計画問題を実数空間上の線形計画法で解くにあたり、ＧＦ（２）上の線形方程式Ａｕ＝ｃを実数空間上の線形不等式の集合に書き改める。
【００１１】
Ａにある一つの行ベクトル
【数５】
2011150465.tif 000007
に注目すると、Ａｕ＝ｃはｌ個のＧＦ（２）上の方程式
【数６】
2011150465.tif 000008
の集合とみなせる。ここで、「・」はベクトルの内積を表す。
【００１２】
以下、｜Ｓ｜は集合Ｓの大きさを表し、Ｓ＼Ｓ’は差集合（Ｓに含まれていてＳ’に含まれない要素からなる集合）を表すものとする。また、集合｛１，２，．．．，ｎ｝の部分集合Ｓｕｐｐ（ａｉ）を次のように定義する。
【００１３】
【数７】
2011150465.tif 000009
【００１４】
これにより、ＧＦ（２）上の線形方程式である式（６）は、以下の実数空間上の線形不等式の集合Ｉｎｅｑ（ａｉ・ｕ＝ｃｉ）に書き改めることができる。ただし、部分集合Ｓは、ｃｉ＝０のときは｜Ｓ｜が奇数であるものだけをとり、ｃｉ＝１のときは｜Ｓ｜が偶数であるものだけをとる。
【００１５】
【数８】
2011150465.tif 000010
【００１６】
非特許文献１で提案されている解法では、このように、ＧＦ（２）上の線形方程式Ａｕ＝ｃを以下の実数空間上の線形不等式の集合に変形（緩和）し、線形計画法を用いて解を求め、これを利用して目的関数をｄ（ｕ）の最適化を行う。
【００１７】
【数９】
2011150465.tif 000011
【００１８】
非特許文献１によれば、ｄをｕの線形関数に定めたとき、線形計画法で求めた最適解を与えるｕの成分が全て整数であれば、ＧＦ（２）上の線形方程式を制約条件とする整数計画問題の最適解になっていることが証明されている。
【００１９】
ただし、線形計画法で求めた最適解を与えるｕの成分が常に全て整数であるとは限らないし、また、ｕに非整数な成分を含む場合、ＧＦ（２）上の線形方程式を制約条件とする整数計画問題の最適解を求めたことにはなっていない。非特許文献２では、この問題点を解決する方法が提案されている。
【００２０】
また、非特許文献３および４では、１つの入力と２つ以上の出力をもつ通信路であるブロードキャスト通信路において用いられる符号化法が提案されており、非特許文献５〜７では、２つ以上の相関のある系列をそれぞれ独立に符号化して符号語を生成する複数の符号器と、生成された全ての符号語から元の系列を全て復元する復号器とにおいて用いられる相関のある情報源の符号化法が提案されている。また、非特許文献７では、相関を有する加法的雑音を伴う複数の通信路の符号化法が提案されている。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】J. Feldman, M. J. Waingwright, and D. R. Karger, “Using linear programming to decode binary linear codes”, IEEE Trans. Inform. Theory, vol. IT-51, pp. 954-972, Mar. 2005.
【非特許文献２】M. H. Taghavi N. and P. H. Siegel, “Adaptive methos for linear programming decoding”, IEEE Trans. Inform. Theory, vol. IT-54, pp. 5396-5410, Dec. 2008.
【非特許文献３】K. Marton, “A coding theorem for the discrete memoryless broadcast channel”, IEEE Trans. Inform. Theory, vol. IT-25, pp. 306-311, May 1979.
【非特許文献４】A. El Gamal and E. Van der Meulen, “A proof of Marton’s coding theorem for the discrete memoryless broadcast channel”, IEEE Trans. Inform. Theory, vol. IT-27, pp. 120-122, Jan. 1981.
【非特許文献５】T. M. Cover, “A proof of the data compression theorem of Slepian and Wolf for ergodic sources”, IEEE Trans. Inform Theory, vol. IT-21, no. 2, pp. 226-228, Mar. 1975.
【非特許文献６】I. Csisz ar, “Linear codes for sources and source networks: Error exponents, universal coding”, IEEE Trans. Inform. Theory, vol. IT-28, no. 4, pp. 585-592, Jul. 1982.
【非特許文献７】J. Muramatsu, T. Uyematsu, and T. Wadayama, “Low density parity check matrices for coding of correlated sources”, IEEE Trans. Inform. Theory, vol. IT-51, no. 10, pp. 3645-3653, Oct. 2005.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、上記の非特許文献３〜７で提案されている技術には、入出力ベクトルの次元に対して計算量が指数的に増大するという問題があった。この問題を解決するには、複数のＧＦ（２）を直積させたＧＦ（２）ｋ（ｋは２以上の整数）を要素とする系列を求める最適化問題を解く必要があるが、非特許文献１および２で開示されている技術は、探索空間がＧＦ（２）、すなわち、ｋが１の場合に限定されているため、そのまま適用することができなかった。
【００２３】
本発明は、上記に鑑みてなされたものであって、少ない計算量で解を探索することができる解探索装置、解探索方法および解探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２４】
上述した課題を解決し、目的を達成するために、本発明に係る解探索装置は、２元有限体の直積を要素とする系列を求める最適化問題の解を探索する解探索装置であって、予め算出された複数のヒストグラムを、ヒストグラムより定まる評価関数を用いて評価するヒストグラム評価手段と、前記ヒストグラム評価手段による評価順にヒストグラムに対応する条件式を取得して解を探索する解探索手段とを備えることを特徴とする。
【００２５】
また、本発明に係る解探索方法は、２元有限体の直積を要素とする系列を求める最適化問題の解を探索する解探索方法であって、予め算出された複数のヒストグラムを、ヒストグラムより定まる評価関数を用いて評価するヒストグラム評価工程と、前記ヒストグラム評価工程における評価順にヒストグラムに対応する条件式を取得して解を探索する解探索工程とを含むことを特徴とする。
【００２６】
また、本発明に係る解探索プログラムは、コンピュータを上記の解探索装置として機能させることを特徴とする。
【発明の効果】
【００２７】
本発明に係る解探索装置、解探索方法および解探索プログラムは、少ない計算量で解を探索することができるという効果を奏する。
【図面の簡単な説明】
【００２８】
【図１】図１は、実施例１に係る解探索装置の機能構成を示すブロック図である。
【図２】図２は、解探索処理の処理手順を示すフローチャートである。
【図３】図３は、実施例２に係る解探索装置の機能構成を示すブロック図である。
【図４】図４は、実施例２に係る解探索装置によって実行される処理の処理手順を示すフローチャートである。
【図５】図５は、ブロードキャスト通信路の一例を示す図である。
【図６】図６は、ブロードキャスト通信路における符号器を示す図である。
【図７】図７は、ブロードキャスト通信路における復号器を示す図である。
【図８】図８は、相関のある情報源符号の一例を示す図である。
【図９】図９は、相関のある情報源符号における符号器を示す図である。
【図１０】図１０は、相関のある情報源符号における復号器を示す図である。
【図１１】図１１は、相関のある加法的雑音を伴う通信路の一例を示す図である。
【図１２】図１２は、相関のある加法的雑音を伴う通信路における符号器と復号器を示す図である。
【発明を実施するための形態】
【００２９】
以下に、本発明に係る解探索装置、解探索方法および解探索プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００３０】
図１は、本実施例に係る解探索装置１０の機能構成を示すブロック図である。図１に示すように、解探索装置１０は、記憶部１１と、ヒストグラム評価部１２と、解探索部１３とを有する。記憶部１１は、例えば、半導体記憶装置や磁気記憶装置であり、ヒストグラムの集合Τと、条件式の集合とを記憶する。条件式の集合には、線形不等式の集合と線形方程式の集合が含まれる。
【００３１】
記憶部１１が記憶する情報について説明する。各ｉ∈｛１，．．．，ｋ｝に対して、ｕ（ｉ）≡（ｕ１（ｉ），．．．，ｕｎ（ｉ））をＧＦ（２）を要素とするｎ次元のベクトルとする。また、ＧＦ（２）ｋを要素とするｎ次元のベクトル（ｕ（１），ｕ（２），．．．，ｕ（ｋ））とｂ≡（ｂ１，ｂ２，．．．，ｂｋ）∈ＧＦ（２）ｋに対して、
【数１０】
2011150465.tif 000012
と定め、（ｕ（１），ｕ（２），．．．，ｕ（ｋ））のヒストグラムｔ（ｕ（１），ｕ（２），．．．，ｕ（ｋ））を次のように定義する。
【００３２】
【数１１】
2011150465.tif 000013
【００３３】
これは、ｋ個のＧＦ（２）をアルファベットとするｎ次元のベクトル
【数１２】
2011150465.tif 000014
をＧＦ（２）ｋをアルファベットとするｎ次元のベクトルと見直したとき、ｔ（ｕ（１），ｕ（２），．．．，ｕ（ｋ））は、（ｂ１，ｂ２，．．．，ｂｋ）∈ＧＦ（２）ｋが（ｕ（１），ｕ（２），．．．，ｕ（ｋ））中に何回現れているかを表している。
【００３４】
以下の最適化問題を考える。
【００３５】
【数１３】
2011150465.tif 000015
【００３６】
ここで、ｄは、ベクトル（ｕ（１），ｕ（２），．．．，ｕ（ｋ））のヒストグラムにのみ依存する関数であり、Ｃは、ＧＦ（２）ｋを要素とするｎ次元のベクトルからなる集合とする。また、集合Ｔを以下のように定義する。
【００３７】
【数１４】
2011150465.tif 000016
【００３８】
これは、ＧＦ（２）ｋを要素とするｎ次元のベクトルのヒストグラムとして存在しうるものを全て集めたもので、この集合の大きさは
【数１５】
2011150465.tif 000017
以下である。
【００３９】
上記の式（１３）を最適化法で解くために、ｔ∈Ｔとｂ∈ＧＦ（２）ｋに対して、補助変数
【数１６】
2011150465.tif 000018
と実数上の線形方程式
【数１７】
2011150465.tif 000019
を導入する。
【００４０】
ここで、補助変数と方程式は全てのｂ∈ＧＦ（２）ｋに対して与えるので、２ｋｎ個の補助変数と２ｋ個の方程式ができる。さらに、集合Ｓ（ｂ）∈ＧＦ（２）ｋ＋１を以下のように定義する。
【００４１】
【数１８】
2011150465.tif 000020
【００４２】
この集合は２ｋ個の要素をもつ。そして、公知の方法を用いて、ｂ∈ＧＦ（２）ｋに対して、Ｓ（ｂ）を頂点に含む凸多面体を与える線形不等式の集合を求める。その集合は、以下のように与えられる。
【００４３】
【数１９】
2011150465.tif 000021
【００４４】
ここで、不等式中の変数はｖ≡（ｖ０，ｖ１，．．．，ｖｋ）である。
【００４５】
記憶部１１に記憶されるヒストグラムの集合Τは、上記の式（１４）に相当する。また、記憶部１１に記憶される線形不等式の集合は、上記の式（１９）の集合であり、以下の式（２０）のように表現され、記憶部１１に記憶される線形方程式の集合は、上記の式（１７）の集合であり、以下の式（２１）のように表現される。
【００４６】
【数２０】
2011150465.tif 000022
【００４７】
【数２１】
2011150465.tif 000023
【００４８】
ヒストグラム評価部１２は、指定された関数ｄを用いて、記憶部１１に記憶されるヒストグラムの集合Τの各要素を評価する。解探索部１３は、ヒストグラム評価部１２による評価順に、ヒストグラムの集合Τの要素に対応する条件式を取得して、取得された条件式と、入力として与えられた条件Ｃとを満たす解を探索する。
【００４９】
以下に、図２のフローチャートを参照しながら、ヒストグラム評価部１２と解探索部１３によって実行される解探索処理の処理手順について説明する。まず、ヒストグラム評価部１２は、関数ｄを取得し、Ｔの要素ｔをｄ（ｔ）の小さい順（最大化の場合は大きい順）にソートする（ステップＳ１０１）。ここで、ソートされた集合をＴ＝｛ｔ１，．．．，ｔｊ，．．．，ｔ｜Τ｜｝とする。
【００５０】
続いて、解探索部１３は、指定された条件Ｃを取得する（ステップＳ１０２）。そして、解探索部１３は、ｊ＝１として、ヒストグラムのインデックスを初期化する（ステップＳ１０３）。
【００５１】
続いて、解探索部１３は、インデックスｊに対応するΤの要素ｔｊに対応する線形方程式の集合である式（２１）と以下の式（２２）で表現される線形不等式の集合を記憶部１１から取得する（ステップＳ１０４）。
【００５２】
【数２２】
2011150465.tif 000024
【００５３】
そして、解探索部１３は、指定された条件Ｃと、記憶部１１から取得した条件式を全て満たすベクトル（ｕ（１），ｕ（２），．．．，ｕ（ｋ））を探索する（ステップＳ１０５）。具体的には、条件Ｃを満たし、
【数２３】
2011150465.tif 000025
を満たし、式（２１）の要素を全て満たし、式（２２）の要素を全て満たすベクトル（ｕ（１），ｕ（２），．．．，ｕ（ｋ））が探索される。
【００５４】
そして、全ての条件を満たすベクトルが存在した場合（ステップＳ１０６肯定）、解探索部１３は、そのベクトルを解として出力して、解探索処理を終了させる（ステップＳ１０７）。一方、そのようなベクトルが存在しない場合（ステップＳ１０６否定）、ｊが｜Τ｜でなければ（ステップＳ１０８否定）、解探索部１３は、ｊに１を加算して（ステップＳ１０９）、ステップＳ１０４から処理手順を再開する。ｊが｜Τ｜であれば（ステップＳ１０８肯定）、解探索部１３は、「解なし」を出力して、解探索処理を終了させる（ステップＳ１１０）。
【００５５】
上述してきたように、本実施例に係る解探索方法および解探索装置では、高々
【数１５】
2011150465.tif 000026
個であるヒストグラムの集合Τの要素を関数ｄで評価し、その評価順に集合Τの要素に対応する条件式を用いて解を探索することとしたので、入出力ベクトルの次元に対して指数的に計算量が増大していた素朴な方法と比較して、計算量を大幅に減少させることが期待できる。
【実施例２】
【００５６】
実施例２では、ヒストグラム
【数２４】
2011150465.tif 000027
により定まる相対頻度関数ｖｔを
【数２５】
2011150465.tif 000028
のように定義することとして、最適化問題
【数２６】
2011150465.tif 000029
を解く例について説明する。
【００５７】
ここで、行列とベクトルの要素は全てＧＦ（２）である。ｊ∈｛１，２，．．．，ｋ｝に対して、Ａ（ｊ）は、ｌ（ｊ）×ｎ行列であり、ｕ（ｊ）は、ｎ次元のベクトルであり、ｃ（ｊ）は、ｌ（ｊ）次元のベクトルである。関数ｄは、式（１１）で定義されたヒストグラムｔ（ｕ（１），ｕ（２），．．．，ｕ（ｋ））より定まる相対頻度
【数２７】
2011150465.tif 000030
とＧＦ（２）ｋ＝｛０，１｝ｋ上の確率分布
【数２８】
2011150465.tif 000031
の距離を算出する関数であり、以下の例がある。
【００５８】
【数２９】
2011150465.tif 000032
【００５９】
【数３０】
2011150465.tif 000033
【００６０】
式（２９）に示した関数ｄｖは、ｐとｑをＧＦ（２）ｋ上の確率分布としたときのｐとｑの変動距離を算出する関数であり、式（３０）に示した関数ｄｄは、ｐとｑをＧＦ（２）ｋ上の確率分布としたときのｐとｑのダイヴァージェンスを算出する関数である。ｄｖとｄｄのいずれを用いても、式（２６）の右辺に現れるｄは、（ｕｉ（１），ｕｉ（２），．．．，ｕｉ（ｋ））より定まるヒストグラムｔ（ｕｉ（１），ｕｉ（２），．．．，ｕｉ（ｋ））のみに依存して定まる関数であるので、実施例１で説明した解探索方法の適用が可能である。
【００６１】
図３は、本実施例に係る解探索装置２０の機能構成を示すブロック図である。図３に示すように、解探索装置２０は、記憶部２１と、条件算出部２２と、解探索部２３とを有する。記憶部２１は、例えば、半導体記憶装置や磁気記憶装置であり、行列Ａ（１），Ａ（２），．．．，Ａ（ｋ）と、関数ｄとを記憶する。
【００６２】
条件算出部２２は、指定されたベクトル（ｃ（１），ｃ（２），．．．，ｃ（ｋ））と、記憶部２１に記憶されている行列Ａ（１），Ａ（２），．．．，Ａ（ｋ）とから、以下のようにして条件（ｕ（１），ｕ（２），．．．，ｕ（ｋ））∈Ｃを定める。
【００６３】
【数３１】
2011150465.tif 000034
【００６４】
解探索部２３は、実施例１で説明した解探索装置１０に相当し、条件算出部２２によって算出された条件Ｃと、記憶部２１に記憶されている関数ｄとを入力として、解を探索して探索結果を出力する。ここで、（ｕ（１），ｕ（２），．．．，ｕ（ｋ））∈Ｃは、式（９）で定義される線形不等式の集合に書き改めることができるので、図２に示したステップＳ１０６での探索では非特許文献１および２で提案された線形計画法を利用できる。なお、解探索部２３が有する記憶部１１と、記憶部２１とを統合して１つの記憶部としてもよい。
【００６５】
以下に、図４のフローチャートを参照しながら、解探索装置２０によって実行される処理の処理手順について説明する。まず、条件算出部２２は、指定されたベクトル（ｃ（１），ｃ（２），．．．，ｃ（ｋ））と、記憶部２１に記憶されている行列Ａ（１），Ａ（２），．．．，Ａ（ｋ）とから、条件Ｃを算出する（ステップＳ２０１）。
【００６６】
続いて、解探索部２３は、条件算出部２２によって算出された条件Ｃと、記憶部２１に記憶されている関数ｄとを入力として、図２に示した解探索処理を実行し（ステップＳ２０２）、探索結果として、ベクトル（ｕ（１），ｕ（２），．．．，ｕ（ｋ））または「解なし」を出力する（ステップＳ２０３）。
【００６７】
以下に、本実施例に係る解探索装置および解探索方法による解探索の具体例について説明する。ｋ＝２を仮定して、以下の最適化問題を考える。
【００６８】
【数３２】
2011150465.tif 000035
【００６９】
ここで、
【数３３】
2011150465.tif 000036
を｛０，１｝２上の確率分布とする。
【００７０】
この場合、式（１４）と対応するヒストグラムの集合は、以下のようになる。
【００７１】
【数３４】
2011150465.tif 000037
【００７２】
これを図２のステップＳ１０１にて、
【数３５】
2011150465.tif 000038
の小さい順にソートしておく。
【００７３】
式（３２）を実現するために、ｉ∈｛１，．．．，ｎ｝、（ｕ（１），ｕ（２））∈｛０，１｝２に対して、新たに変数ｓｉ（ｕ（１），ｕ（２））を導入し、式（１７）と対応する等式
【数３６】
2011150465.tif 000039
を導入しておく。
【００７４】
式（１８）と対応する集合Ｓ（ｕ（１），ｕ（２））は、以下のようになる。
【００７５】
【数３７】
2011150465.tif 000040
【００７６】
また、式（１９）と対応する、Ｓ（ｕ（１），ｕ（２））を頂点とする多面体を構成する不等式は、以下のようになる。
【００７７】
【数３８】
2011150465.tif 000041
【００７８】
したがって、図２のステップＳ１０６で用いられる等式、不等式の集合は、ｔ∈Τに対して、以下のようになる。
【００７９】
【数３９】
2011150465.tif 000042
【００８０】
ここで、最初の２つの不等式集合の具体的な構成は、非特許文献１で提案されている方法を用いて、式（９）で与えたものである。
【実施例３】
【００８１】
本実施例では、実施例１および２で説明した技術をブロードキャスト通信路符号に適用する例について説明する。ブロードキャスト通信路符号とは、ブロードキャスト通信路にて用いられる符号であり、ブロードキャスト通信路とは、１つの入力と２つ以上の出力をもつ通信路である。
【００８２】
出力が２つのブロードキャスト通信路の一例を図５に示す。図５に示す符号器は、メッセージＭ（１）とＭ（２）を符号化して通信路入力Ｘを求めて送信する。図５に示す２つの復号器は、それぞれの通信路出力からそれぞれのメッセージを小さな誤り確率で復号する。
【００８３】
ここで、ブロードキャスト通信路の入力Ｘのアルファベットを［Ｘ］として、各ｊ∈｛１，２，．．．，ｋ｝に対して、ブロードキャスト通信路のｊ番目の出力Ｙ（ｊ）のアルファベットを［Ｙ］（ｊ）とする。また、通信路の遷移確率を
【数４０】
2011150465.tif 000043
とする。
【００８４】
まず最初に、Ｘｋの要素を値にとる確率分布
【数４１】
2011150465.tif 000044
と関数ｆ：［Ｘ］ｋ→［Ｘ］を与える。
【００８５】
そして、（Ｕ（１），．．．，Ｕ（ｋ），Ｘ，Ｙ（１），．．．，Ｙ（ｋ））の同時分布を以下のように与える。
【００８６】
【数４２】
2011150465.tif 000045
【００８７】
ここで、
【数４３】
2011150465.tif 000046
と定義する。
【００８８】
また、ベクトルの次元を次のように定義する。
【００８９】
【数４４】
2011150465.tif 000047
【００９０】
【数４５】
2011150465.tif 000048
【００９１】
ここで、任意のｊ∈｛１，２，．．．，ｋ｝と、空集合を除き、全体集合を含む任意のＪ⊆｛１，２，．．．，ｋ｝に対して、
【数４６】
2011150465.tif 000049
と
【数４７】
2011150465.tif 000050
が整数であり、かつ、
【数４８】
2011150465.tif 000051
を満たすように、
【数４９】
2011150465.tif 000052
と
【数５０】
2011150465.tif 000053
を定める。
【００９２】
Ｈ（Ｕ（ｊ）｜Ｙ（ｊ））は、Ｙ（ｊ）を与えたときのＵ（ｊ）の条件付きエントロピーであり、Ｈ（｛Ｕ（ｊ）｝ｊ∈Ｊ）は、確率変数｛Ｕ（ｊ）｝ｊ∈Ｊの同時エントロピーである。
【００９３】
そして、各ｊ∈｛１，２，．．．，ｋ｝で、ｌ（ｊ）次元のベクトルｂ（ｊ）と、ｌ（ｊ）×ｎ行列Ｂ（ｊ）と、＾ｌ（ｊ）×ｎ行列＾Ｂ（ｊ）を定める（＾ｌは、ハット付きの「ｌ」を表し、＾Ｂは、ハット付きの「Ｂ」を表すものとする。以下同様）。また、各ｊ∈｛１，２，．．．，ｋ｝で、＾ｌ（ｊ）次元のベクトルで表現されるｋ個のメッセージ
【数５１】
2011150465.tif 000054
に対して、符号器φを以下のように構成する。
【００９４】
【数５２】
2011150465.tif 000055
【００９５】
ここで、［Ｘ］＝｛０，１｝を仮定して、行列Ｂ（ｊ）と＾Ｂ（ｊ）を連結した［ｌ（ｊ）＋＾ｌ（ｊ）］×ｎ行列Ａ（ｊ）と、ベクトルｂ（ｊ）とｍ（ｊ）を連結した［ｌ（ｊ）＋＾ｌ（ｊ）］ベクトルｃ（ｊ）≡（ｂ（ｊ），ｍ（ｊ））を考えれば、上記の式（５２）の右辺は式（２６）と同一となる。したがって、実施例１および２で説明した解探索方法を適用できる。なお、関数ｄについては、式（２９）と式（３０）のどちらを使用してもよい。
【００９６】
各ｊ∈｛１，２，．．．，ｋ｝に対して、ｎ次元ベクトルｙ（ｊ）を受信した復号器は、次のように元のメッセージ＾ｍ（ｊ）を復元する。
【００９７】
【数５３】
2011150465.tif 000056
【００９８】
通信路の統計的性質が未知の場合は、
【数５４】
2011150465.tif 000057
を以下の式
【数５５】
2011150465.tif 000058
で定義される
【数５６】
2011150465.tif 000059
と置き換える。ここで、Ｈ（ｕ｜ｙ）は、
【数５７】
2011150465.tif 000060
で定義される。ここで、［Ｘ］＝｛０，１｝を仮定すれば、式（５３）および式（５５）の実現には非特許文献１および２で紹介された方法を用いることができる。
【００９９】
以下に、本実施例に係る解探索方法による解探索の具体例について説明する。ここでは、ｋ＝２、［Ｘ］＝［Ｕ］（１）＝［Ｕ］（２）＝｛０，１｝の場合のブロードキャスト通信路符号の例について説明する。図５に全体の構成を示し、図６に符号器の構成を示し、図７に復号器の構成を示す。
【０１００】
｛０，１｝２上の確率分布
【数５８】
2011150465.tif 000061
と関数ｆ：｛０，１｝２→｛０，１｝を定め、以下のように定義する。
【０１０１】
【数５９】
2011150465.tif 000062
【０１０２】
そして、（Ｕ（１），Ｕ（２），Ｘ，Ｙ（１），Ｙ（２））の同時分布を以下のように定める。
【０１０３】
【数６０】
2011150465.tif 000063
【０１０４】
また、ベクトルの次元を次のように定義する。
【０１０５】
【数６１】
2011150465.tif 000064
【０１０６】
ここで、式（４８）にｋ＝２を適用した条件式
【数６２】
2011150465.tif 000065
を満たすように、ε（１）＞０、ε（２）＞０、Ｒ（１）＞０、Ｒ（２）＞０を定める。
【０１０７】
これは、
【数６３】
2011150465.tif 000066
と同値である。
【０１０８】
また、ｌ（１）次元のベクトルｂ（１）、ｌ（２）次元のベクトルｂ（２）、ｌ（１）×ｎ行列Ｂ（１）、＾ｌ（１）×ｎ行列＾Ｂ（１）、ｌ（２）×ｎ行列Ｂ（２）、＾ｌ（２）×ｎ行列＾Ｂ（２）を定める。そして、ｍ（１）を＾ｌ（１）次元のベクトルとし、ｍ（２）を＾ｌ（２）次元のベクトルとし、２つのメッセージ（ｍ（１），ｍ（２））に対して符号器を以下のように定める。
【０１０９】
【数６４】
2011150465.tif 000067
【０１１０】
ここで、ｕ（１）≡（ｕ１（１），ｕ２（１），．．．，ｕｎ（１））、ｕ（２）≡（ｕ１（２），ｕ２（２），．．．，ｕｎ（２））である。関数ｄについては、式（２９）と式（３０）のどちらを使用してもよい。
【０１１１】
ここで、Ａ（１）をＢ（１）と＾Ｂ（１）を連結した［ｌ（１）＋＾ｌ（１）］×ｎ行列とし、Ａ（２）をＢ（２）と＾Ｂ（２）を連結した［ｌ（２）＋＾ｌ（２）］×ｎ行列とする。さらに、ｃ（１）≡（ｂ（１），ｍ（１））をｂ（１）とｍ（１）を連結した［ｌ（１）＋＾ｌ（１）］ベクトルとし、ｃ（２）≡（ｂ（２），ｍ（２））をｂ（２）とｍ（２）を連結した［ｌ（２）＋＾ｌ（２）］ベクトルとする。このとき、条件Ｂ（１）ｕ（１）＝ｂ（１）、＾Ｂ（１）ｕ（１）＝ｍ（１）は、Ａ（１）ｕ（１）＝ｃ（１）となり、条件Ｂ（２）ｕ（２）＝ｂ（２）、＾Ｂ（２）ｕ（２）＝ｍ（２）は、Ａ（２）ｕ（２）＝ｃ（２）となる。したがって、式（６４）の右辺は、式（３２）と同一のものになる。
【０１１２】
ｎ次元ベクトルｙ（１）を受信した復号器は、次のように元のメッセージ＾ｍ（１）を復元する。
【０１１３】
【数６５】
2011150465.tif 000068
【０１１４】
通信路の統計的性質が未知の場合は、
【数６６】
2011150465.tif 000069
を
【数６７】
2011150465.tif 000070
で定義される
【数６８】
2011150465.tif 000071
と置き換える。ここで、Ｈ（ｕ（１）｜ｙ（１））は、式（５７）で定義されたものであり、［Ｘ］＝｛０，１｝を仮定すれば、式（６５）と式（６７）の実現には、非特許文献１および２で紹介された方法を用いることができる。
【０１１５】
同様に、ｎ次元ベクトルｙ（２）を受信した復号器は、次のように元のメッセージ＾ｍ（２）を復元する。
【０１１６】
【数６９】
2011150465.tif 000072
【０１１７】
通信路の統計的性質が未知の場合は、
【数７０】
2011150465.tif 000073
を
【数７１】
2011150465.tif 000074
で定義される
【数７２】
2011150465.tif 000075
と置き換える。ここで、Ｈ（ｕ（２）｜ｙ（２））は、式（５７）で定義されたものであり、［Ｘ］＝｛０，１｝を仮定すれば、式（６９）と式（７１）の実現には、非特許文献１および２で紹介された方法を用いることができる。
【実施例４】
【０１１８】
本実施例では、実施例１および２で説明した技術を相関のある情報源符号に適用する例について説明する。相関のある情報源符号とは、２つ以上の相関のある系列をそれぞれ独立に符号化して符号語を生成する複数の符号器と、生成された全ての符号語から元の系列を全て復元する復号器とによって用いられる符号である。
【０１１９】
２つの情報源の場合の符号化・復号化の流れを図８に示す。なお、図８において、Ｕ（２）をそのエントロピーＲ（２）＝Ｈ（Ｕ（２））のレートで無歪みで圧縮して復号器へ送信し、Ｕ（１）を条件付きエントロピーＲ（１）＝Ｈ（Ｕ（１）｜Ｕ（２））のレートで圧縮し、復号器が（Ｕ（１），Ｕ（２））を無歪みで符号化・復号化する符号を構成して、時分割原理と呼ばれる方法を用いて条件を満たす一般のレート対（Ｒ（１），Ｒ（２））を達成する方法があるが、以下では、時分割原理を用いることなく一般のレート対を達成する方法を考える。
【０１２０】
相関のある情報源を
【数７３】
2011150465.tif 000076
として、その同時分布を
【数７４】
2011150465.tif 000077
とする。
【０１２１】
各ｊ∈｛１，２，．．．，ｋ｝に対して、ｊ番目の情報源Ｕ（ｊ）のアルファベットを［Ｕ］（ｊ）とする。
【０１２２】
そして、
【数７５】
2011150465.tif 000078
を、全体集合を含む任意のＪ⊆｛１，２，．．．，ｋ｝で以下の式を満たすように定める。
【０１２３】
【数７６】
2011150465.tif 000079
【０１２４】
そして、各ｊ∈｛１，２，．．．，ｋ｝に対して、ｌ（ｊ）×ｎ行列Ａ（ｊ）を用意する。
【０１２５】
各ｊ∈｛１，２，．．．，ｋ｝に対して、ｎ次元のベクトルｕ（ｊ）を符号化する符号器は、次のように符号化を行ってｌ（ｊ）次元のベクトル（符号語）を得る。
【０１２６】
【数７７】
2011150465.tif 000080
【０１２７】
各ｊ∈｛１，２，．．．，ｋ｝に対して、ｌ（ｊ）次元ベクトルｃ（ｊ）を符号器φ（ｊ）が符号化した符号語とする。そして、復号器を以下のように与える。
【０１２８】
【数７８】
2011150465.tif 000081
【０１２９】
この式は、式（２６）に他ならないので、実施例１および２で説明した解探索方法を適用できる。なお、関数ｄについては、式（２９）と式（３０）のどちらを使用してもよい。
【０１３０】
以下に、本実施例に係る解探索方法による解探索の具体例について説明する。ここでは、ｋ＝２、［Ｕ］（１）＝［Ｕ］（２）＝｛０，１｝の場合の相関性のある情報源符号の例について説明する。図８に全体の構成を示し、図９に符号器の構成を示し、図１０に復号器の構成を示す。
【０１３１】
相関のある情報源（Ｕ（１），Ｕ（２））の同時分布を
【数７９】
2011150465.tif 000082
とする。この場合、条件式（７６）は、次のようになる。
【０１３２】
【数８０】
2011150465.tif 000083
【０１３３】
Ｒ（１）、Ｒ（２）を
【数８１】
2011150465.tif 000084
と定めれば、これは、図８で書かれている条件式にほかならない。
【０１３４】
そして、（ｌ（１），ｌ（２））を上記の式を満たすようにとり、ｌ（１）×ｎ行列Ａ（１）とｌ（２）×ｎ行列Ａ（２）を用意する。
【０１３５】
ｎ次元のベクトルｕ（１）を符号化する符号器を以下のように定義する。符号語は、ｌ（１）次元のベクトルとなる。
【０１３６】
【数８２】
2011150465.tif 000085
【０１３７】
同様に、ｎ次元のベクトルｕ（２）を符号化する符号器を以下のように定義する。符号語は、ｌ（２）次元のベクトルとなる。
【０１３８】
【数８３】
2011150465.tif 000086
【０１３９】
ｃ（１）を符号器φ（１）の符号語を表すｌ（１）次元ベクトルとし、ｃ（２）を符号器φ（２）の符号語を表すｌ（２）次元ベクトルとして、復号器を以下のように与える。
【０１４０】
【数８４】
2011150465.tif 000087
【０１４１】
この式は、式（３２）に他ならないので、実施例１および２で説明した解探索方法を適用できる。なお、関数ｄについては、式（２９）と式（３０）のどちらを使用してもよい。
【実施例５】
【０１４２】
本実施例では、実施例１および２で説明した技術を相関のある加法的雑音を伴う通信路符号に適用する例について説明する。加法的雑音を伴う通信路とは、２つ以上の入出力をもつ通信路で、一つの入出力間の雑音が加法的であり、かつ、それらの雑音が相関をもっているような通信路である。図１１は、２つの加法的雑音を伴う通信路を表している。
【０１４３】
相関のある雑音を
【数８５】
2011150465.tif 000088
として、その同時分布を
【数８６】
2011150465.tif 000089
とする。
【０１４４】
各ｊ∈｛１，２，．．．，ｋ｝に対して、ｊ番目の雑音Ｕ（ｊ）のアルファベットを［Ｕ］（ｊ）とする。
【０１４５】
そして、
【数８７】
2011150465.tif 000090
を、全体集合を含む任意のＪ⊆｛１，２，．．．，ｋ｝で式（７６）を満たすように定める。また、各ｊ∈｛１，２，．．．，ｋ｝に対して、ｌ（ｊ）×ｎ行列Ａ（ｊ）を用意する。そして、［ｎ−ｌ（ｊ）］×ｎ行列Ｇ（ｊ）を、任意の［ｎ−ｌ（ｊ）］次元のベクトルｍ（ｊ）に対して、Ａ（ｊ）Ｇ（ｊ）ｍ（ｊ）＝０を満たすように与える。ここで、０は、ｌ（ｊ）次元のベクトルであり、Ｇ（ｊ）は、検査行列Ａ（ｊ）と対応する生成行列と呼ばれるものである。
【０１４６】
各ｊ∈｛１，２，．．．，ｋ｝に対して、［ｎ−ｌ（ｊ）］次元のベクトルｍ（ｊ）を符号化する符号器は、次のように符号化を実行して得たｎ次元のベクトルを送信する。
【０１４７】
【数８８】
2011150465.tif 000091
【０１４８】
通信路入力を
【数８９】
2011150465.tif 000092
とすると、通信路出力は、雑音ｕ（ｊ）を用いて、
【数９０】
2011150465.tif 000093
と表現できる。ここで、「＋」は、ＧＦ（２）上のベクトルの加法である。
【０１４９】
そして、
【数９１】
2011150465.tif 000094
を受信した復号器は、各ｊ∈｛１，２，．．．，ｋ｝に対して、ｌ（ｊ）次元ベクトルｃ（ｊ）を以下のように求める。
【０１５０】
【数９２】
2011150465.tif 000095
【０１５１】
このとき、
【数９３】
2011150465.tif 000096
を満たしていることから、
【数９４】
2011150465.tif 000097
は、相関のある雑音
【数９５】
2011150465.tif 000098
を情報源とみなして、式（７７）の符号化を行った符号語とみなすことができる。したがって、式（７８）を用いて雑音を推定することができる。
【０１５２】
推定した雑音
【数９６】
2011150465.tif 000099
から、通信路入力
【数９７】
2011150465.tif 000100
を以下のように推定する。
【０１５３】
【数９８】
2011150465.tif 000101
【０１５４】
ここで、「−」は、ＧＦ（２）上のベクトルの減法である。
【０１５５】
そして、［ｎ−ｌ（ｊ）］×ｎ行列Ｇ’（ｊ）を、ｎ×ｎ行列Ｇ’（ｊ）Ｇ（ｊ）が単位行列となるものとする。復号器は、最後に、
【数９９】
2011150465.tif 000102
を実行して、メッセージ
【数１００】
2011150465.tif 000103
を推定する。
【０１５６】
以下に、本実施例に係る解探索方法による解探索の具体例について説明する。ここでは、ｋ＝２、［Ｕ］（１）＝［Ｕ］（２）＝｛０，１｝を仮定して、相関のある雑音（Ｕ（１），Ｕ（２））を伴う通信路の構成を与える。図１２に全体の構成を示す。
【０１５７】
相関のある雑音の同時分布を
【数１０１】
2011150465.tif 000104
とする。
【０１５８】
（ｌ（１），ｌ（２））を
【数１０２】
2011150465.tif 000105
を満たすようにとる
【数１０３】
2011150465.tif 000106
とすれば、これは図１２にある条件式と同一である。
【０１５９】
そして、ｌ（１）×ｎ行列Ａ（１）を与え、［ｎ−ｌ（１）］×ｎ行列Ｇ（１）を、任意の［ｎ−ｌ（１）］次元のベクトルｍ（１）に対して、Ａ（１）Ｇ（１）ｍ（１）＝０を満たすように与える。同様に、ｌ（２）×ｎ行列Ａ（２）を与え、［ｎ−ｌ（２）］×ｎ行列Ｇ（２）を、任意の［ｎ−ｌ（２）］次元のベクトルｍ（２）に対して、Ａ（２）Ｇ（２）ｍ（２）＝０を満たすように与える。
【０１６０】
［ｎ−ｌ（１）］次元のベクトルｍ（１）を符号化する符号器は、次のように符号化を実行して得たｎ次元のベクトルを送信する。
【０１６１】
【数１０４】
2011150465.tif 000107
【０１６２】
同様に、［ｎ−ｌ（２）］次元のベクトルｍ（２）を符号化する符号器は、次のように符号化を実行して得たｎ次元のベクトルを送信する。
【０１６３】
【数１０５】
2011150465.tif 000108
【０１６４】
通信路入力を
【数１０６】
2011150465.tif 000109
とすると、通信路出力は雑音（ｕ（１），ｕ（２））を用いて、
【数１０７】
2011150465.tif 000110
と表現できる。
【０１６５】
（ｙ（１），ｙ（２））を受信した復号器は、ｌ（１）次元ベクトルｃ（１）とｌ（２）次元ベクトルｃ（２）を以下のように求める。
【０１６６】
【数１０８】
2011150465.tif 000111
【０１６７】
このとき、
【数１０９】
2011150465.tif 000112
を満たしていることから、（ｃ（１），ｃ（２））は、相関のある雑音（ｕ（１），ｕ（２））を情報源とみなして、相関のある情報源の符号化を行った符号語とみなすことができる。したがって、式（８４）を用いて雑音を推定することができる。
【０１６８】
推定した雑音（＾ｕ（１），＾ｕ（２））から通信路入力（＾ｘ（１），＾ｘ（２））を以下のように推定する。
【０１６９】
【数１１０】
2011150465.tif 000113
【０１７０】
［ｎ−ｌ（１）］×ｎ行列Ｇ’（１）を、ｎ×ｎ行列Ｇ’（１）Ｇ（１）が単位行列となるものとする。同様に、［ｎ−ｌ（２）］×ｎ行列Ｇ’（２）を、ｎ×ｎ行列Ｇ’（２）Ｇ（２）が単位行列となるものとする。
【０１７１】
復号器は、最後に
【数１１１】
2011150465.tif 000114
を実行して、メッセージ（＾ｍ（１），＾ｍ（２））を推定する。
【０１７２】
なお、上記の各実施例に示した本発明の実施態様は、要旨を逸脱しない範囲で種々に変更することができる。例えば、上記の各実施例に示した解探索方法をコンピュータプログラムとして実装し、これをコンピュータで実行することにより、上記の各実施例に示した解探索装置、符号器、復号器と同等の機能を実現することができる。このようなコンピュータプログラムは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の記憶媒体、コンピュータが内蔵するハードディスク装置等の記憶装置、または、コンピュータとネットワーク接続されたサーバ装置に記憶され、コンピュータが内蔵するＣＰＵによってメモリー上に展開されて実行状態となる。
【符号の説明】
【０１７３】
１０  解探索装置
１１  記憶部
１２  ヒストグラム評価部
１３  解探索部
２０  解探索装置
２１  記憶部
２２  条件算出部
２３  解探索処理部
【図１】
2011150465.tif 000115
【図２】
2011150465.tif 000116
【図３】
2011150465.tif 000117
【図４】
2011150465.tif 000118
【図５】
2011150465.tif 000119
【図６】
2011150465.tif 000120
【図７】
2011150465.tif 000121
【図８】
2011150465.tif 000122
【図９】
2011150465.tif 000123
【図１０】
2011150465.tif 000124
【図１１】
2011150465.tif 000125
【図１２】
2011150465.tif 000126