"対象となるアルファベットを2値{0,1}とし、該{0,1}上の確率分布P、n×k行列A,及びシンドロームu∈{0,1}kが与えられたとき長さnの2値系列x∈{0,1}nを但し、記号argは右辺のmaxを達成するを左辺のxとして出力することを意味するとして与える線形符号の最適な整数解を求める最尤復号器であって、前記式1の緩和問題を線形計画法によって解く線形計画問題処理手段と、実行可能領域を前記線形計画問題処理手段により得られた目的関数fの最適値から適切な値例えばfの初期値までを一定間隔εで等分した領域スライス領域において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標xを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、を有することを特徴とするLP復号器。対象となるアルファベットを2値{0,1}とし、該{0,1}上の確率分布P、n×k行列A,及びシンドロームu∈{0,1}kが与えられたとき長さnの2値系列x∈{0,1}nを但し、記号argは右辺のmaxを達成するを左辺のxとして出力することを意味するとして与える線形符号の最適な整数解を求める整数解計算方法であって、線形計画問題処理手段が、前記式1の緩和問題を線形計画法によって解く線形計画問題処理ステップと、判別アルゴリズム実行手段が、実行可能領域を前記線形計画問題処理ステップで得られた目的関数fの最適値から適切な値例えばfの初期値までを一定間隔εで等分した領域スライス領域内において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標xを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行ステップと、を行うことを特徴とする整数解計算方法。コンピュータを、請求項1記載のLP復号器の各手段として機能させるための整数解計算プログラム。上記のように、従来の手法では、LP復号器の実現において線形計画法を用いた際に、出力が非整数解となる、アルゴリズムの実行時間が符号長に関して多項式オーダーである保証がなくなるという欠点があった。本発明は、上記の点に鑑みなされたもので、前述の式1を緩和した線形計画問題をシンプレックス法などの適切な方法を用いて解いた際に最適な整数解を得やすくするために全体のアルゴリズムを見直し、また、見直した後のアルゴリズムの実行時間は符号を構成する行列が疎行列である場合、符号長nに関して多項式オーダーとなるようなLP復号器及び整数解計算方法及びプログラムを提供することを目的とする。上記の課題を解決するため、対象となるアルファベットを2値{0,1}とし、該{0,1}上の確率分布P、n×k行列A,及びシンドロームu∈{0,1}kが与えられたとき長さnの2値系列x∈{0,1}nを但し、記号argは右辺のmaxを達成するを左辺のxとして出力するという意味であるとして与える線形符号の最適な整数解を近似的に求めるLP復号器であって、前記式1の緩和問題を線形計画法によって解く線形計画問題処理手段と、実行可能領域を前記線形計画問題処理手段に用いられる目的関数fの最適値から適切な値例えばfの初期値までを一定間隔εで等分した領域スライス領域において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標xを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、を有する。上記のように、本発明によれば、LP復号問題における実行可能領域を適切に分割し、順番に各領域内に超立方体の頂点が含まれるかどうかを判別する、という方式を採用したことで、頂点を含む/含まない、の判別のための実行時間が符号長nに関して多項式オーダーであるならば符号化アルゴリズム全体も多項式オーダーとなることが示せる。これにより、LP復号器を用いるデータ圧縮符号化や誤り訂正符号化の実行時間を短縮することができ、効率のよい符号化の実現が可能となる。以下図面と共に、本発明の実施の形態を説明する。図1は、本発明の一実施の形態におけるLP復号器の構成を示す。本発明のLP復号器は、入力部1、記憶部2、出力部3、処理部10から構成される。記憶部2は、メモリやハードディスク等の記憶媒体である。処理部10は、判別アルゴリズム実行部11と線形計画問題処理部12から構成される。入力部1は、シンドロームu長さkの2値系列、領域分割のパラメータε、判別アルゴリズムで拘束条件とする座標数λを入力する。記憶部2は、n×k行列A、{0,1}上の確率分布Pを格納する。判別アルゴリズム実行部11は、実行可能領域を目的関数f平行にfの最適値から適切な値例えばfの初期値を一定間隔εで分割した領域について、順に走査して単位正方形単位超立方体の頂点が含まれる場合に当該含まれる頂点の座標xを最適解として出力部3に出力する。判別アルゴリズム実行部11は、走査途中の暫定解を格納するためのメモリ図示せずを具備しているものとする。線形計画問題処理部12は、前述の式1の緩和問題を線形計画法によって解く。図2は、式1を緩和した線形計画問題を模式化したものである。同図の塗りつぶされた凸領域が実行可能領域で、この領域と図中の線a目的関数fに相当するとが接する点が線形計画問題の解である。図2にて示される最適解は非整数解である。この場合、最適解を与えるxの値はであるので、元の線形計画問題に新たな工夫を施してを出力するようにしたい。まず図3で示すように図2の線a目的関数fの最適値Sliceと平行な直線を一定間隔εで描くことで実行可能領域を分割する。分割された各領域以下、スライス領域と記すは線形計画法の最適解を含む領域から順に番号付けが可能であることに注意する。本実施の形態で行うことは、判別アルゴリズム実行部11において、判別アルゴリズムにより分割された各スライス領域を順に走査して、単位正方形の頂点を含むか否かをチェックすることである。単位正方形が含まれた最初の領域が見つかれば、判別アルゴリズム実行部11は領域に含まれる単位正方形の頂点座標x0,x1を出力して終了する。ここで注意すべきことは間隔εを十分小さくとれば各領域の幅が小さくなるので、単位正方形の頂点を複数個含む場合の出現頻度は無視できることである。以下に、判別アルゴリズム実行部11において実行される判別アルゴリズムについて説明する。図4は、本発明の一実施の形態における判別アルゴリズムn=2の例である。同図は、図3に示す各領域において単位正方形の頂点が含まれるか否かをチェックする判別アルゴリズムである。まず、判別アルゴリズム実行部11は、拘束条件とする座標のインデックスjを0とし、領域のインデックスrを0とし、初期化を行う。次に、xjに0及び1を代入して前述の緩和問題の式1の拘束条件として追加した緩和問題について領域r内に実行可能解があるかどうかをチェックするStep1。実行可能解が存在すればOK、存在しなければNGとする。チェックはCase1~Case4に示すとおりである。Case1の場合xj=0もxj=1もNGは、r=r1、j=0として当該Step1を繰り返す。Case2の場合xj=0はOK、xj=1はNGは、xj=0を式1の拘束条件に追加して、線形計画問題を解くソルバシンプレックス法や内点法等を呼び出して緩和問題を解く。緩和問題を解いた結果、最適値を与えるxが整数値をとるならば、xout=xを整数解として出力部3に出力する。そうでない場合は、j=0のきはj=1とインクリメントして当該Step1を行う。j=1のときはr=r1、j=0として当該Step1を行う。Case3の場合xj=0はNG、xj=1はOKは、xj=1を式1の拘束条件に追加して、上記と同様に、シンプレックス法や内点法等の線形計画問題を解くソルバを呼び出して緩和問題を解く。緩和問題を解いた結果、最適値を与えるxが整数値をとるならば、xout=xを整数解として出力部3に出力する。そうでない場合は、j=0のきはj=1とインクリメントして当該Step1を行う。j=1のときはr=r1、j=0として当該Step1を行う。Case4の場合xj=0もxj=1もOKは、最適値を与えるxを整数値をとるように近似したものを暫定解としてメモリに保持する。j=0のきはj=1とインクリメントして当該Step1を行う。j=1のときはr=r1、j=0として当該Step1を行う。上記のStep1では、xjに0及び1を代入して、式1の拘束条件として追加した緩和問題についてスライス領域r内に実行可能解があるかどうかをCase1~Case4についてチェックしている。例えば、図3の領域bではx01の条件下で実行可能解が存在する図4:Step1のCase3が、xは整数解とならない。整数解は図3の領域cに存在する。このとき、判別アルゴリズムのStep1において、実行可能解の有無の判別は線形計画問題に帰着することに注意しておく。なお、図4のStep1のCase2およびCase3でxが整数値からなるかどうかを判別しているが、この際には厳密に整数かどうかの判別ではなくε/2程度の誤差を許容している。図4のCase4は、条件xj=0もxj=1も注目しているスライス領域と交叉するか接する場合である。この場合、xj=0もxj=1も有効な拘束条件とならないため現時点で得られている最適値x非整数解を適切に処理したもの処理の仕方は特許文献1などを参照を暫定解としてメモリに記憶することになる。この暫定解は全てのスライス領域まで走査された後でも整数解が得られない場合にその時点でメモリに保持されているものが出力される役割を持つ。以上は、簡単のためにn2の場合のアルゴリズムを説明した。一般の場合のアルゴリズムは図5および図6に示すように、全体アルゴリズムと判別アルゴリズムからなる。まず、図5の全体アルゴリズムについて説明する。最初に処理部10は、入力部1より長さkの2値系列uを取得し、記憶部2よりn×k行列Aと{0,1}上の確率分布Pを取得する。さらに、領域のインデックスrを0とする。Step1において、線形計画問題処理部12は、入力されたu,A,Pを用いて、式1の緩和問題を線形計画法により解く。判別アルゴリズム実行部11は、線形計画問題処理部12で得られた値について、目的関数fの最適値=fを与えるベクトルxの各座標が全て整数値ならば、xout=xとして出力部3に出力して終了する。それ以外の場合は、Slice=目的関数の最適値,Slice=Slicerεとして、Step2に移行する。Step2では、判別アルゴリズム実行部11において、ならば終了する。この場合は走査中の暫定解を格納するメモリ上にある値が出力される。ここで、fmaxは目的関数fの最大値もしくはfの初期値である。そうでないならば、図6に示す判別アルゴリズムを実行する。図6の判別アルゴリズムについて説明する。判別アルゴリズム処理部11は、入力部1より領域のインデックスr、領域の下限のSlice、記憶部2より拘束条件とする座標数λ、領域分割のパラメータεを取得する。更に、初期化処理として、拘束条件のインデックスjを0とし、を0n1よりランダムに選ぶ。Step1において、座標集合I1I2について、を求める。Step2において、I2=I1ならばStep4に移行し、そうでないならばI2:=I1i:=0とし、Step3に移行する。Step3において、i∈I1ならば、ii1とし、Step3へ進む。この処理は既定の拘束条件I1に加え、新たな拘束条件に対応するインデックスを探すためのものである。i∈I1でないならば、線形計画問題処理部12において、xiに0もしくは1を代入して、xiの値及びIndexにおいて2以外の値をとる座標の値及びSlice≦f<Sliceを拘束条件に追加した式1の緩和問題における実行可能解の有無を線形計画法で解き、実行可能解が存在する場合はOK、そうでない場合はNGとする。Case1の場合xi=0もxi=1もNGは、j=j1としてI1を別の拘束条件の組にインクリメントし、Step1に戻る。もし、ならば、r=r1として図5の全体アルゴリズムのStep2へ戻る。Case2の場合xi=0はOK、xi=1はNGは、Indexの第i座標を0にセットし、とし、i<nならばStep3へ移行し、inならばStep2へ戻る。Case3の場合xi=0はNG、xi=1はOKは、Indexの第i座標を1にセットする。とし、i<nならばStep3へ移行し、inならばStep2へ戻る。Case4の場合xi=0もxi=1もOKは、ii1とし、i<nならばStep3へ移行し、inならばStep2へ戻る。各rに対して拘束条件の集合I1が大きくなれば次のStep4において整数解を得やすくなるというのが本アルゴリズムの眼目である.Step4において、線形計画問題処部12は、Indexにおいて2以外の値をとる座標の値及びSlice≦fSliceを拘束条件に追加した式1の緩和問題を線形計画法で解く。その結果、目的関数fの最適値=fを与えるベクトルxの各座標が全て整数値ならばxoutxとして終了する。それ以外の場合は、適切な方法例えば、非特許文献1による出力をxoutの暫定解としてメモリに保持し、rr1として図5の全体アルゴリズムのStep2へ戻る。上記の図5図6と図4との大きな違いは、座標に関する拘束条件xj=0またはxj=1を式1に追加に追加する前に、新たに前提を既定の拘束条件としてアドホックに固定していることである。この前提条件は図6のStep1においての全ての場合を最悪の場合尽くすことになる図7で示すシミュレーションではλ3である。また、図6のStep1で定義する座標集合Indexはその要素の値が2以外の座標についてはIndexにある値が注目しているスライス領域での拘束条件となる。なお、図6のStep2においてI2=I1となる場合は、その前処理のStep3においてI1に入っていない全ての座標xjに関してxj=0もxj=1も新たな拘束条件として追加されなかったことを示すことに注意する。このときは、最終的な拘束条件I1もしくはIndexを用いてStep4にて最適化を実行する。また、図6のStep4で保持される暫定解は、全てのスライス領域まで走査された後でも整数解が得られない場合にその時点で保持されているものが出力される役割を持つ。上記のように、本実施の形態では、式1の近似解法を念頭に置いた。情報理論では式1は情報源符号化問題において出現する最適化問題である。一方、通信路符号化問題や有歪み情報源符号化問題においても式1と等価な問題に帰着できることが知られている文献:SMiyakeandJMuramatsuConstructionofalossysourcecodeusingLDPCmatricesIEICETransFundamvolE91Ano6pp148815012008。従って、データ圧縮、誤り訂正に関する問題における符号を疎行列を用いて構成する場合、本アルゴリズムを線形計画法と併用することによって効率良い符号化実現が可能となる。なお図7は、式1を緩和して線形計画法で解く際に非整数解出力を回避するための既存のアルゴリズム非特許文献2と比較したものである。同図中、Standard,CuttingPlane,Sliceはそれぞれ式1を緩和したものを線形計画問題で解いただけのもの、Standardの条件に加え切除平面法を用いたもの、Standardの条件に加え本アルゴリズムを用いたものである。切除平面法を用いたアルゴリズムの結果が復号誤りの観点からは最も良く、本発明によるものがそれに次ぐ。ただし、非特許文献2の切除平面法は、符号を構成する行列から新たな拘束条件を見出し追加するという方式であるため、必ずしも行列の疎行列性は有効に利用されない。従って本方式とは異なり符号長nに関する多項式オーダーの実行時間は保証されていない。なお、上記の実施の形態では、図1の線形符号器の構成に基づいて説明したが、当該装置は、コンピュータとプログラムによっても実現でき、プログラムを記憶媒体に記録することも、ネットワークを通して提供することも可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更応用が可能である。"