線形符号におけるＬＰ復号器及び整数解計算方法及びプログラム
【課題】 LP復号器の実現において線形計画法を用いた際に、効率的に整数解を出力する。
【解決手段】 線形符号における最尤復号の緩和問題を線形計画法によって解き、その実行可能領域を得られた目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス領域）内において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する。
【解決手段】 線形符号における最尤復号の緩和問題を線形計画法によって解き、その実行可能領域を得られた目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス領域）内において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線形符号におけるLP（線形計画）復号器及び整数解計算方法及びプログラムに係り、特に、線形計画法を用いた符号において整数出力を効率的に実現するためのLP復号器及び整数解計算方法及びプログラムに関する。
【背景技術】
【０００２】
従来、線形符号における最尤復号を実現する技術として以下のような手法がある。
【０００３】
対象となるアルファベットは2値｛０，１｝とし、２元体としての算法（加法および乗法）が適用されるものとする。
【０００４】
まず線形符号における最尤復号を定義する．最尤復号とは、｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１］nを
【０００５】
【数１】
として与えるものである。
【０００６】
ここで、記号argは右辺のmaxを達成する
【０００７】
【数２】
を左辺のxとして出力するという意味である。
【０００８】
注目すべきことは式（１）をそのまま実行するのならばｎに関して指数オーダーの実行時間が必要となるが、非特許文献１にて提案された緩和法を適用することによって近似的に線形計画法で記述できることが示されているということである。従って、もしAが疎行列、すなわち要素が１である個数が０である個数に比べて圧倒的に少ないならば、シンプレックス法や内点法を適用して式（１）の緩和問題を解けば符号長ｎに関して多項式オーダーの実行時間となる。式（１）を緩和法によって線形計画問題に書き換えて得られる近似解法をLP復号と呼ぶ（非特許文献１参照）。
【０００９】
しかし一方で式（１）の条件部分を緩和したことによって、線形計画問題を解いて得られる解は必ずしも整数解とはならないという不都合が生じる。このとき、どのようにして整数解を得るのかが新たな問題である。例えば特許文献１では得られた非整数解において疎行列Aの冗長行と対応する成分を四捨五入によって固定し、残りの成分を連立一次方程式を解くことで求めている。しかしながら、このような方法はヒューリスティックな性質が強く、得られる整数解は確かに式（１）の拘束条件は満たすが、最適値を与えるという保証を与えるものではなかった。
【００１０】
また、非特許文献２では適応的切除平面法という緩和条件に新たな条件を追加する方式で整数解を得る可能性を高めた。しかしながら追加する条件は必ずしも拘束条件の疎行列性を保持しなくなるので実行時間が符号長ｎに関して多項式オーダーである保証がなくなるという欠点を持つ。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２０１０−０１６６８４号公報
【非特許文献】
【００１２】
【非特許文献１】J. Feldman, M. J. Wainwright, and D. R. Karger, "Using linear programming to decode binary linear codes," IEEE Trans. Inform. Theory, vol. 51, no. 3, pp. 954-972, 2005.
【非特許文献２】村松 純, "線形計画法を用いた2元線形符号の復号における適応的切除平面法の改良," 信学技報, vol. IT2010, no. 40, pp. 37-42, 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上記のように、従来の手法では、LP復号器の実現において線形計画法を用いた際に、出力が非整数解となる、アルゴリズムの実行時間が符号長に関して多項式オーダーである保証がなくなるという欠点があった。
【００１４】
本発明は、上記の点に鑑みなされたもので、前述の式（１）を緩和した線形計画問題をシンプレックス法などの適切な方法を用いて解いた際に最適な整数解を得やすくするために全体のアルゴリズムを見直し、また、見直した後のアルゴリズムの実行時間は符号を構成する行列が疎行列である場合、符号長ｎに関して多項式オーダーとなるようなLP復号器及び整数解計算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記の課題を解決するため、対象となるアルファベットを２値｛０，１｝とし、該｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１｝nを
【００１６】
【数３】
（但し、記号argは右辺のmaxを達成する
【００１７】
【数４】
を左辺のxとして出力するという意味である）
として与える線形符号の最適な整数解を近似的に求めるLP復号器であって、
前記式（１）の緩和問題を線形計画法によって解く線形計画問題処理手段と、実行可能領域を前記線形計画問題処理手段に用いられる目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス）領域において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、を有する。
【発明の効果】
【００１８】
上記のように、本発明によれば、LP復号問題における実行可能領域を適切に分割し、順番に各領域内に超立方体の頂点が含まれるかどうかを判別する、という方式を採用したことで、頂点を含む／含まない、の判別のための実行時間が符号長ｎに関して多項式オーダーであるならば符号化アルゴリズム全体も多項式オーダーとなることが示せる。
【００１９】
これにより、LP復号器を用いるデータ圧縮符号化や誤り訂正符号化の実行時間を短縮することができ、効率のよい符号化の実現が可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施の形態における線形符号器の構成図である。
【図２】式（1）を緩和した線形計画問題の模式図である。
【図３】本発明の一実施の形態における実行可能領域の分割の例である。
【図４】本発明の一実施の形態における判別アルゴリズム（ｎ＝２）である。
【図５】本発明の一実施の形態における全体アルゴリズムである。
【図６】本発明の一実施の形態における判別アルゴリズムである。
【図７】既存アルゴリズムとの比較である。
【発明を実施するための形態】
【００２１】
以下図面と共に、本発明の実施の形態を説明する。
【００２２】
図１は、本発明の一実施の形態におけるLP復号器の構成を示す。
【００２３】
本発明のLP復号器は、入力部１、記憶部２、出力部３、処理部１０から構成される。記憶部２は、メモリやハードディスク等の記憶媒体である。
【００２４】
処理部１０は、判別アルゴリズム実行部１１と線形計画問題処理部１２から構成される。
【００２５】
入力部１は、シンドロームｕ（長さｋの２値系列）、領域分割のパラメータε、判別アルゴリズムで拘束条件とする座標数λを入力する。
【００２６】
記憶部２は、ｎ×ｋ行列Ａ、｛０，１｝上の確率分布Ｐを格納する。
【００２７】
判別アルゴリズム実行部１１は、実行可能領域を目的関数ｆ平行にｆの最適値から適切な値（例えばｆの初期値）を一定間隔（ε）で分割した領域について、順に走査して単位正方形（単位超立方体）の頂点が含まれる場合に当該含まれる頂点の座標ｘを最適解として出力部３に出力する。判別アルゴリズム実行部１１は、走査途中の暫定解を格納するためのメモリ（図示せず）を具備しているものとする。
【００２８】
線形計画問題処理部１２は、前述の式（１）の緩和問題を線形計画法によって解く。
【００２９】
図２は、式（１）を緩和した線形計画問題を模式化したものである。
【００３０】
同図の塗りつぶされた凸領域が実行可能領域で、この領域と図中の線ａ（目的関数ｆに相当する）とが接する点が線形計画問題の解である。
【００３１】
図２にて示される最適解は非整数解である。この場合、最適解を与えるｘの値は(1,0)であるので、元の線形計画問題に新たな工夫を施して(1,0)を出力するようにしたい。
【００３２】
まず図３で示すように図２の線ａ（目的関数ｆの最適値Slice(0)）と平行な直線(Slice(r))を一定間隔（ε）で描くことで実行可能領域を分割する。分割された各領域（以下、「スライス領域」と記す）は線形計画法の最適解を含む領域から順に番号付けが可能であることに注意する。
【００３３】
本実施の形態で行うことは、判別アルゴリズム実行部１１において、判別アルゴリズムにより分割された各スライス領域を順に走査して、単位正方形の頂点を含むか否かをチェックすることである。単位正方形が含まれた最初の領域が見つかれば、判別アルゴリズム実行部１１は領域に含まれる単位正方形の頂点座標（ｘ0，ｘ１）を出力して終了する。ここで注意すべきことは間隔εを十分小さくとれば各領域の幅が小さくなるので、単位正方形の頂点を複数個含む場合の出現頻度は無視できることである。
【００３４】
以下に、判別アルゴリズム実行部１１において実行される判別アルゴリズムについて説明する。
【００３５】
図４は、本発明の一実施の形態における判別アルゴリズム（ｎ＝２）の例である。
【００３６】
同図は、図３に示す各領域において単位正方形の頂点が含まれるか否かをチェックする判別アルゴリズム(n=2の場合)である。
【００３７】
まず、判別アルゴリズム実行部１１は、拘束条件とする座標のインデックスｊを０とし、領域のインデックスｒを０とし、初期化を行う。
【００３８】
次に、ｘｊに０及び１を代入して前述の緩和問題の式（１）の拘束条件として追加した緩和問題について領域ｒ内に実行可能解があるかどうかをチェックする（Step1）。実行可能解が存在すれば「ＯＫ」、存在しなければ「ＮＧ」とする。チェックはCase1〜Case４に示すとおりである。
【００３９】
Case１の場合（xj＝0もxj＝１もＮＧ）は、ｒ＝ｒ＋１、ｊ＝０として当該Step１を繰り返す。
【００４０】
Case2の場合（xj＝0はＯＫ、xj＝１はＮＧ）は、ｘj＝０を式（１）の拘束条件に追加して、線形計画問題を解くソルバ（シンプレックス法や内点法等）を呼び出して緩和問題を解く。緩和問題を解いた結果、最適値を与えるｘ*が整数値をとるならば、ｘout＝x*を整数解として出力部３に出力する。そうでない場合は、ｊ＝０のきはｊ＝１とインクリメントして当該Step1を行う。ｊ＝１のときはｒ＝ｒ＋１、ｊ＝０として当該Step1を行う。
【００４１】
Case３の場合（xj＝0はＮＧ、xj＝１はＯＫ）は、ｘj＝１を式（１）の拘束条件に追加して、上記と同様に、シンプレックス法や内点法等の線形計画問題を解くソルバを呼び出して緩和問題を解く。緩和問題を解いた結果、最適値を与えるｘ*が整数値をとるならば、ｘout＝x*を整数解として出力部３に出力する。そうでない場合は、ｊ＝０のきはｊ＝１とインクリメントして当該Step1を行う。ｊ＝１のときはｒ＝ｒ＋１、ｊ＝０として当該Step1を行う。
【００４２】
Case４の場合（xj＝0もxj＝１もＯＫ）は、最適値を与えるｘ*を整数値をとるように近似したものを暫定解としてメモリに保持する。ｊ＝０のきはｊ＝１とインクリメントして当該Step1を行う。ｊ＝１のときはｒ＝ｒ＋１、ｊ＝０として当該Step1を行う。
【００４３】
上記のStep1では、ｘｊに０及び１を代入して、式（１）の拘束条件として追加した緩和問題についてスライス領域ｒ内に実行可能解があるかどうかをCase1〜Case4についてチェックしている。例えば、図３の領域ｂではx0=1の条件下で実行可能解が存在する（図４：Step 1のCase 3）が、x*は整数解とならない。整数解は図３の領域ｃに存在する。このとき、判別アルゴリズム(図４)のStep 1において、実行可能解の有無の判別は線形計画問題に帰着することに注意しておく。なお、図４のStep 1のCase 2およびCase 3でx*が整数値からなるかどうかを判別しているが、この際には厳密に整数かどうかの判別ではなくε／２程度の誤差を許容している。
【００４４】
図４のCase 4は、条件xｊ＝０もｘj＝１も注目しているスライス領域と交叉するか接する場合である。この場合、xｊ＝０もｘj＝１も有効な拘束条件とならないため現時点で得られている最適値ｘ*（非整数解）を適切に処理したもの（処理の仕方は特許文献１などを参照）を暫定解としてメモリに記憶することになる。この暫定解は全てのスライス領域まで走査された後でも整数解が得られない場合にその時点でメモリに保持されているものが出力される役割を持つ。
【００４５】
以上は、簡単のためにn=2の場合のアルゴリズムを説明した。一般の場合のアルゴリズムは図５および図６に示すように、全体アルゴリズムと判別アルゴリズムからなる。
【００４６】
まず、図５の全体アルゴリズムについて説明する。
【００４７】
最初に処理部１０は、入力部１より長さｋの２値系列ｕを取得し、記憶部２よりｎ×ｋ行列Ａと｛０，１｝上の確率分布Ｐを取得する。さらに、領域のインデックスｒを０とする。
【００４８】
Step1において、線形計画問題処理部１２は、入力されたｕ，Ａ，Ｐを用いて、式（１）の緩和問題を線形計画法により解く。判別アルゴリズム実行部１１は、線形計画問題処理部１２で得られた値について、目的関数ｆの最適値（＝ｆ*）を与えるベクトルｘ*の各座標が全て整数値ならば、ｘout＝ｘとして出力部３に出力して終了する。それ以外の場合は、
Slice(r)＝目的関数の最適値，Slice(r+1)＝Slice（r）+ε
として、Step2に移行する。
【００４９】
Step2では、判別アルゴリズム実行部１１において、
【００５０】
【数５】
ならば終了する。この場合は走査中の暫定解を格納するメモリ上にある値が出力される。ここで、fmaxは目的関数ｆの最大値（もしくはｆの初期値）である。そうでないならば、図６に示す判別アルゴリズムを実行する。
【００５１】
図６の判別アルゴリズムについて説明する。
【００５２】
判別アルゴリズム処理部１１は、入力部１より領域のインデックスｒ、領域の下限のSlice(r)、記憶部２より拘束条件とする座標数λ、領域分割のパラメータεを取得する。更に、初期化処理として、拘束条件のインデックスｊを０とし、
【００５３】
【数６】
を[0:n-1]よりランダムに選ぶ。
【００５４】
Step1において、座標集合I1,I2について、
【００５５】
【数７】
を求める。
【００５６】
Step2において、I2 ＝I1ならばStep4に移行し、そうでないならばI2：＝I1, i：＝０とし、Step3に移行する。
【００５７】
Step3において、i ∈ I1ならば、i:= i + 1とし、Step3へ進む。この処理は既定の拘束条件I1に加え、新たな拘束条件に対応するインデックスを探すためのものである。i ∈ I1でないならば、線形計画問題処理部１２において、xｉに０もしくは１を代入して、xｉの値及びIndexにおいて２以外の値をとる座標の値及びSlice(r)≦ｆ＜Slice(r+1)を拘束条件に追加した式（１）の緩和問題における実行可能解の有無を線形計画法で解き、実行可能解が存在する場合はOK、そうでない場合はNGとする。
【００５８】
Case1の場合（xｉ＝０もxｉ＝１もNG）は、ｊ:＝ｊ＋１としてI1を別の拘束条件の組にインクリメントし、Step1に戻る。もし、
【００５９】
【数８】
ならば、ｒ:＝ｒ＋１として図５の全体アルゴリズムのStep2へ戻る。
【００６０】
Case2の場合（xｉ＝０はOK、xｉ＝１はNG）は、Indexの第i座標を０にセットし、
【００６１】
【数９】
とし、ｉ＜ｎならばStep3へ移行し、i=ｎならばStep2へ戻る。
【００６２】
Case3の場合（xｉ＝０はNG、xｉ＝１はOK）は、Indexの第i座標を１にセットする。
【００６３】
【数１０】
とし、ｉ＜ｎならばStep3へ移行し、i=nならばStep2へ戻る。
【００６４】
Case4の場合（xｉ＝０もxｉ＝１もOK）は、i:=i+１とし、ｉ＜ｎならばStep3へ移行し、i=ｎならばStep2へ戻る。各rに対して拘束条件の集合I1が大きくなれば次のStep4において整数解を得やすくなるというのが本アルゴリズムの眼目である．
Step4において、線形計画問題処部１２は、Indexにおいて２以外の値をとる座標の値及びSlice(r)≦f<Slice(r+1)を拘束条件に追加した式（１）の緩和問題を線形計画法で解く。その結果、目的関数ｆの最適値（＝ｆ*）を与えるベクトルｘ*の各座標が全て整数値ならばxｏｕｔ=ｘ*として終了する。それ以外の場合は、適切な方法（例えば、非特許文献１）による出力をｘoutの暫定解としてメモリに保持し、r:=r+1として図５の全体アルゴリズムのStep２へ戻る。
【００６５】
上記の図５・図６と図４との大きな違いは、座標に関する拘束条件（xｊ＝０またはｘj＝１）を式（１）に追加に追加する前に、新たに前提
【００６６】
【数１１】
を既定の拘束条件としてアドホックに固定していることである。この前提条件は図６のStep 1において
【００６７】
【数１２】
の全ての場合を（最悪の場合）尽くすことになる（図７で示すシミュレーションではλ=3である）。
【００６８】
また、図６のStep 1で定義する座標集合Indexはその要素の値が２以外の座標についてはIndexにある値が注目しているスライス領域での拘束条件となる。
【００６９】
なお、図６のStep 2においてＩ2＝Ｉ1となる場合は、その前処理のStep 3においてI1に入っていない全ての座標ｘjに関してxj＝0もxj＝１も新たな拘束条件として追加されなかったことを示すことに注意する。このときは、最終的な拘束条件I1（もしくはIndex）を用いてStep 4にて最適化を実行する。
【００７０】
また、図６のStep 4で保持される暫定解は、全てのスライス領域まで走査された後でも整数解が得られない場合にその時点で保持されているものが出力される役割を持つ。
【００７１】
上記のように、本実施の形態では、式（１）の近似解法を念頭に置いた。情報理論では式（１）は情報源符号化問題において出現する最適化問題である。一方、通信路符号化問題や有歪み情報源符号化問題においても式（１）と等価な問題に帰着できることが知られている（文献：S. Miyake and J. Muramatsu, "Construction of a lossy source code using LDPC matrices," IEICE Trans. Fundam., vol. E-91A, no. 6, pp. 1488-1501, 2008.）。従って、データ圧縮、誤り訂正に関する問題における符号を疎行列を用いて構成する場合、本アルゴリズムを線形計画法と併用することによって効率良い符号化実現が可能となる。
【００７２】
なお図７は、式（１）を緩和して線形計画法で解く際に非整数解出力を回避するための既存のアルゴリズム（非特許文献２）と比較したものである。同図中、"Standard"，"Cutting Plane"，"Slice"はそれぞれ式（１）を緩和したものを線形計画問題で解いただけのもの、Standardの条件に加え切除平面法を用いたもの、Standardの条件に加え本アルゴリズムを用いたものである。切除平面法を用いたアルゴリズムの結果が復号誤りの観点からは最も良く、本発明によるものがそれに次ぐ。ただし、非特許文献２の切除平面法は、符号を構成する行列から新たな拘束条件を見出し追加するという方式であるため、必ずしも行列の疎行列性は有効に利用されない。従って本方式とは異なり符号長ｎに関する多項式オーダーの実行時間は保証されていない。
【００７３】
なお、上記の実施の形態では、図１の線形符号器の構成に基づいて説明したが、当該装置は、コンピュータとプログラムによっても実現でき、プログラムを記憶媒体に記録することも、ネットワークを通して提供することも可能である。
【００７４】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７５】
１ 入力部
２ 記憶部
３ 出力部
１０ 処理部
１１ 判別アルゴリズム実行部
１２ 線形計画問題処理部
【技術分野】
【０００１】
本発明は、線形符号におけるLP（線形計画）復号器及び整数解計算方法及びプログラムに係り、特に、線形計画法を用いた符号において整数出力を効率的に実現するためのLP復号器及び整数解計算方法及びプログラムに関する。
【背景技術】
【０００２】
従来、線形符号における最尤復号を実現する技術として以下のような手法がある。
【０００３】
対象となるアルファベットは2値｛０，１｝とし、２元体としての算法（加法および乗法）が適用されるものとする。
【０００４】
まず線形符号における最尤復号を定義する．最尤復号とは、｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１］nを
【０００５】
【数１】
として与えるものである。
【０００６】
ここで、記号argは右辺のmaxを達成する
【０００７】
【数２】
を左辺のxとして出力するという意味である。
【０００８】
注目すべきことは式（１）をそのまま実行するのならばｎに関して指数オーダーの実行時間が必要となるが、非特許文献１にて提案された緩和法を適用することによって近似的に線形計画法で記述できることが示されているということである。従って、もしAが疎行列、すなわち要素が１である個数が０である個数に比べて圧倒的に少ないならば、シンプレックス法や内点法を適用して式（１）の緩和問題を解けば符号長ｎに関して多項式オーダーの実行時間となる。式（１）を緩和法によって線形計画問題に書き換えて得られる近似解法をLP復号と呼ぶ（非特許文献１参照）。
【０００９】
しかし一方で式（１）の条件部分を緩和したことによって、線形計画問題を解いて得られる解は必ずしも整数解とはならないという不都合が生じる。このとき、どのようにして整数解を得るのかが新たな問題である。例えば特許文献１では得られた非整数解において疎行列Aの冗長行と対応する成分を四捨五入によって固定し、残りの成分を連立一次方程式を解くことで求めている。しかしながら、このような方法はヒューリスティックな性質が強く、得られる整数解は確かに式（１）の拘束条件は満たすが、最適値を与えるという保証を与えるものではなかった。
【００１０】
また、非特許文献２では適応的切除平面法という緩和条件に新たな条件を追加する方式で整数解を得る可能性を高めた。しかしながら追加する条件は必ずしも拘束条件の疎行列性を保持しなくなるので実行時間が符号長ｎに関して多項式オーダーである保証がなくなるという欠点を持つ。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２０１０−０１６６８４号公報
【非特許文献】
【００１２】
【非特許文献１】J. Feldman, M. J. Wainwright, and D. R. Karger, "Using linear programming to decode binary linear codes," IEEE Trans. Inform. Theory, vol. 51, no. 3, pp. 954-972, 2005.
【非特許文献２】村松 純, "線形計画法を用いた2元線形符号の復号における適応的切除平面法の改良," 信学技報, vol. IT2010, no. 40, pp. 37-42, 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上記のように、従来の手法では、LP復号器の実現において線形計画法を用いた際に、出力が非整数解となる、アルゴリズムの実行時間が符号長に関して多項式オーダーである保証がなくなるという欠点があった。
【００１４】
本発明は、上記の点に鑑みなされたもので、前述の式（１）を緩和した線形計画問題をシンプレックス法などの適切な方法を用いて解いた際に最適な整数解を得やすくするために全体のアルゴリズムを見直し、また、見直した後のアルゴリズムの実行時間は符号を構成する行列が疎行列である場合、符号長ｎに関して多項式オーダーとなるようなLP復号器及び整数解計算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記の課題を解決するため、対象となるアルファベットを２値｛０，１｝とし、該｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１｝nを
【００１６】
【数３】
（但し、記号argは右辺のmaxを達成する
【００１７】
【数４】
を左辺のxとして出力するという意味である）
として与える線形符号の最適な整数解を近似的に求めるLP復号器であって、
前記式（１）の緩和問題を線形計画法によって解く線形計画問題処理手段と、実行可能領域を前記線形計画問題処理手段に用いられる目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス）領域において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、を有する。
【発明の効果】
【００１８】
上記のように、本発明によれば、LP復号問題における実行可能領域を適切に分割し、順番に各領域内に超立方体の頂点が含まれるかどうかを判別する、という方式を採用したことで、頂点を含む／含まない、の判別のための実行時間が符号長ｎに関して多項式オーダーであるならば符号化アルゴリズム全体も多項式オーダーとなることが示せる。
【００１９】
これにより、LP復号器を用いるデータ圧縮符号化や誤り訂正符号化の実行時間を短縮することができ、効率のよい符号化の実現が可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施の形態における線形符号器の構成図である。
【図２】式（1）を緩和した線形計画問題の模式図である。
【図３】本発明の一実施の形態における実行可能領域の分割の例である。
【図４】本発明の一実施の形態における判別アルゴリズム（ｎ＝２）である。
【図５】本発明の一実施の形態における全体アルゴリズムである。
【図６】本発明の一実施の形態における判別アルゴリズムである。
【図７】既存アルゴリズムとの比較である。
【発明を実施するための形態】
【００２１】
以下図面と共に、本発明の実施の形態を説明する。
【００２２】
図１は、本発明の一実施の形態におけるLP復号器の構成を示す。
【００２３】
本発明のLP復号器は、入力部１、記憶部２、出力部３、処理部１０から構成される。記憶部２は、メモリやハードディスク等の記憶媒体である。
【００２４】
処理部１０は、判別アルゴリズム実行部１１と線形計画問題処理部１２から構成される。
【００２５】
入力部１は、シンドロームｕ（長さｋの２値系列）、領域分割のパラメータε、判別アルゴリズムで拘束条件とする座標数λを入力する。
【００２６】
記憶部２は、ｎ×ｋ行列Ａ、｛０，１｝上の確率分布Ｐを格納する。
【００２７】
判別アルゴリズム実行部１１は、実行可能領域を目的関数ｆ平行にｆの最適値から適切な値（例えばｆの初期値）を一定間隔（ε）で分割した領域について、順に走査して単位正方形（単位超立方体）の頂点が含まれる場合に当該含まれる頂点の座標ｘを最適解として出力部３に出力する。判別アルゴリズム実行部１１は、走査途中の暫定解を格納するためのメモリ（図示せず）を具備しているものとする。
【００２８】
線形計画問題処理部１２は、前述の式（１）の緩和問題を線形計画法によって解く。
【００２９】
図２は、式（１）を緩和した線形計画問題を模式化したものである。
【００３０】
同図の塗りつぶされた凸領域が実行可能領域で、この領域と図中の線ａ（目的関数ｆに相当する）とが接する点が線形計画問題の解である。
【００３１】
図２にて示される最適解は非整数解である。この場合、最適解を与えるｘの値は(1,0)であるので、元の線形計画問題に新たな工夫を施して(1,0)を出力するようにしたい。
【００３２】
まず図３で示すように図２の線ａ（目的関数ｆの最適値Slice(0)）と平行な直線(Slice(r))を一定間隔（ε）で描くことで実行可能領域を分割する。分割された各領域（以下、「スライス領域」と記す）は線形計画法の最適解を含む領域から順に番号付けが可能であることに注意する。
【００３３】
本実施の形態で行うことは、判別アルゴリズム実行部１１において、判別アルゴリズムにより分割された各スライス領域を順に走査して、単位正方形の頂点を含むか否かをチェックすることである。単位正方形が含まれた最初の領域が見つかれば、判別アルゴリズム実行部１１は領域に含まれる単位正方形の頂点座標（ｘ0，ｘ１）を出力して終了する。ここで注意すべきことは間隔εを十分小さくとれば各領域の幅が小さくなるので、単位正方形の頂点を複数個含む場合の出現頻度は無視できることである。
【００３４】
以下に、判別アルゴリズム実行部１１において実行される判別アルゴリズムについて説明する。
【００３５】
図４は、本発明の一実施の形態における判別アルゴリズム（ｎ＝２）の例である。
【００３６】
同図は、図３に示す各領域において単位正方形の頂点が含まれるか否かをチェックする判別アルゴリズム(n=2の場合)である。
【００３７】
まず、判別アルゴリズム実行部１１は、拘束条件とする座標のインデックスｊを０とし、領域のインデックスｒを０とし、初期化を行う。
【００３８】
次に、ｘｊに０及び１を代入して前述の緩和問題の式（１）の拘束条件として追加した緩和問題について領域ｒ内に実行可能解があるかどうかをチェックする（Step1）。実行可能解が存在すれば「ＯＫ」、存在しなければ「ＮＧ」とする。チェックはCase1〜Case４に示すとおりである。
【００３９】
Case１の場合（xj＝0もxj＝１もＮＧ）は、ｒ＝ｒ＋１、ｊ＝０として当該Step１を繰り返す。
【００４０】
Case2の場合（xj＝0はＯＫ、xj＝１はＮＧ）は、ｘj＝０を式（１）の拘束条件に追加して、線形計画問題を解くソルバ（シンプレックス法や内点法等）を呼び出して緩和問題を解く。緩和問題を解いた結果、最適値を与えるｘ*が整数値をとるならば、ｘout＝x*を整数解として出力部３に出力する。そうでない場合は、ｊ＝０のきはｊ＝１とインクリメントして当該Step1を行う。ｊ＝１のときはｒ＝ｒ＋１、ｊ＝０として当該Step1を行う。
【００４１】
Case３の場合（xj＝0はＮＧ、xj＝１はＯＫ）は、ｘj＝１を式（１）の拘束条件に追加して、上記と同様に、シンプレックス法や内点法等の線形計画問題を解くソルバを呼び出して緩和問題を解く。緩和問題を解いた結果、最適値を与えるｘ*が整数値をとるならば、ｘout＝x*を整数解として出力部３に出力する。そうでない場合は、ｊ＝０のきはｊ＝１とインクリメントして当該Step1を行う。ｊ＝１のときはｒ＝ｒ＋１、ｊ＝０として当該Step1を行う。
【００４２】
Case４の場合（xj＝0もxj＝１もＯＫ）は、最適値を与えるｘ*を整数値をとるように近似したものを暫定解としてメモリに保持する。ｊ＝０のきはｊ＝１とインクリメントして当該Step1を行う。ｊ＝１のときはｒ＝ｒ＋１、ｊ＝０として当該Step1を行う。
【００４３】
上記のStep1では、ｘｊに０及び１を代入して、式（１）の拘束条件として追加した緩和問題についてスライス領域ｒ内に実行可能解があるかどうかをCase1〜Case4についてチェックしている。例えば、図３の領域ｂではx0=1の条件下で実行可能解が存在する（図４：Step 1のCase 3）が、x*は整数解とならない。整数解は図３の領域ｃに存在する。このとき、判別アルゴリズム(図４)のStep 1において、実行可能解の有無の判別は線形計画問題に帰着することに注意しておく。なお、図４のStep 1のCase 2およびCase 3でx*が整数値からなるかどうかを判別しているが、この際には厳密に整数かどうかの判別ではなくε／２程度の誤差を許容している。
【００４４】
図４のCase 4は、条件xｊ＝０もｘj＝１も注目しているスライス領域と交叉するか接する場合である。この場合、xｊ＝０もｘj＝１も有効な拘束条件とならないため現時点で得られている最適値ｘ*（非整数解）を適切に処理したもの（処理の仕方は特許文献１などを参照）を暫定解としてメモリに記憶することになる。この暫定解は全てのスライス領域まで走査された後でも整数解が得られない場合にその時点でメモリに保持されているものが出力される役割を持つ。
【００４５】
以上は、簡単のためにn=2の場合のアルゴリズムを説明した。一般の場合のアルゴリズムは図５および図６に示すように、全体アルゴリズムと判別アルゴリズムからなる。
【００４６】
まず、図５の全体アルゴリズムについて説明する。
【００４７】
最初に処理部１０は、入力部１より長さｋの２値系列ｕを取得し、記憶部２よりｎ×ｋ行列Ａと｛０，１｝上の確率分布Ｐを取得する。さらに、領域のインデックスｒを０とする。
【００４８】
Step1において、線形計画問題処理部１２は、入力されたｕ，Ａ，Ｐを用いて、式（１）の緩和問題を線形計画法により解く。判別アルゴリズム実行部１１は、線形計画問題処理部１２で得られた値について、目的関数ｆの最適値（＝ｆ*）を与えるベクトルｘ*の各座標が全て整数値ならば、ｘout＝ｘとして出力部３に出力して終了する。それ以外の場合は、
Slice(r)＝目的関数の最適値，Slice(r+1)＝Slice（r）+ε
として、Step2に移行する。
【００４９】
Step2では、判別アルゴリズム実行部１１において、
【００５０】
【数５】
ならば終了する。この場合は走査中の暫定解を格納するメモリ上にある値が出力される。ここで、fmaxは目的関数ｆの最大値（もしくはｆの初期値）である。そうでないならば、図６に示す判別アルゴリズムを実行する。
【００５１】
図６の判別アルゴリズムについて説明する。
【００５２】
判別アルゴリズム処理部１１は、入力部１より領域のインデックスｒ、領域の下限のSlice(r)、記憶部２より拘束条件とする座標数λ、領域分割のパラメータεを取得する。更に、初期化処理として、拘束条件のインデックスｊを０とし、
【００５３】
【数６】
を[0:n-1]よりランダムに選ぶ。
【００５４】
Step1において、座標集合I1,I2について、
【００５５】
【数７】
を求める。
【００５６】
Step2において、I2 ＝I1ならばStep4に移行し、そうでないならばI2：＝I1, i：＝０とし、Step3に移行する。
【００５７】
Step3において、i ∈ I1ならば、i:= i + 1とし、Step3へ進む。この処理は既定の拘束条件I1に加え、新たな拘束条件に対応するインデックスを探すためのものである。i ∈ I1でないならば、線形計画問題処理部１２において、xｉに０もしくは１を代入して、xｉの値及びIndexにおいて２以外の値をとる座標の値及びSlice(r)≦ｆ＜Slice(r+1)を拘束条件に追加した式（１）の緩和問題における実行可能解の有無を線形計画法で解き、実行可能解が存在する場合はOK、そうでない場合はNGとする。
【００５８】
Case1の場合（xｉ＝０もxｉ＝１もNG）は、ｊ:＝ｊ＋１としてI1を別の拘束条件の組にインクリメントし、Step1に戻る。もし、
【００５９】
【数８】
ならば、ｒ:＝ｒ＋１として図５の全体アルゴリズムのStep2へ戻る。
【００６０】
Case2の場合（xｉ＝０はOK、xｉ＝１はNG）は、Indexの第i座標を０にセットし、
【００６１】
【数９】
とし、ｉ＜ｎならばStep3へ移行し、i=ｎならばStep2へ戻る。
【００６２】
Case3の場合（xｉ＝０はNG、xｉ＝１はOK）は、Indexの第i座標を１にセットする。
【００６３】
【数１０】
とし、ｉ＜ｎならばStep3へ移行し、i=nならばStep2へ戻る。
【００６４】
Case4の場合（xｉ＝０もxｉ＝１もOK）は、i:=i+１とし、ｉ＜ｎならばStep3へ移行し、i=ｎならばStep2へ戻る。各rに対して拘束条件の集合I1が大きくなれば次のStep4において整数解を得やすくなるというのが本アルゴリズムの眼目である．
Step4において、線形計画問題処部１２は、Indexにおいて２以外の値をとる座標の値及びSlice(r)≦f<Slice(r+1)を拘束条件に追加した式（１）の緩和問題を線形計画法で解く。その結果、目的関数ｆの最適値（＝ｆ*）を与えるベクトルｘ*の各座標が全て整数値ならばxｏｕｔ=ｘ*として終了する。それ以外の場合は、適切な方法（例えば、非特許文献１）による出力をｘoutの暫定解としてメモリに保持し、r:=r+1として図５の全体アルゴリズムのStep２へ戻る。
【００６５】
上記の図５・図６と図４との大きな違いは、座標に関する拘束条件（xｊ＝０またはｘj＝１）を式（１）に追加に追加する前に、新たに前提
【００６６】
【数１１】
を既定の拘束条件としてアドホックに固定していることである。この前提条件は図６のStep 1において
【００６７】
【数１２】
の全ての場合を（最悪の場合）尽くすことになる（図７で示すシミュレーションではλ=3である）。
【００６８】
また、図６のStep 1で定義する座標集合Indexはその要素の値が２以外の座標についてはIndexにある値が注目しているスライス領域での拘束条件となる。
【００６９】
なお、図６のStep 2においてＩ2＝Ｉ1となる場合は、その前処理のStep 3においてI1に入っていない全ての座標ｘjに関してxj＝0もxj＝１も新たな拘束条件として追加されなかったことを示すことに注意する。このときは、最終的な拘束条件I1（もしくはIndex）を用いてStep 4にて最適化を実行する。
【００７０】
また、図６のStep 4で保持される暫定解は、全てのスライス領域まで走査された後でも整数解が得られない場合にその時点で保持されているものが出力される役割を持つ。
【００７１】
上記のように、本実施の形態では、式（１）の近似解法を念頭に置いた。情報理論では式（１）は情報源符号化問題において出現する最適化問題である。一方、通信路符号化問題や有歪み情報源符号化問題においても式（１）と等価な問題に帰着できることが知られている（文献：S. Miyake and J. Muramatsu, "Construction of a lossy source code using LDPC matrices," IEICE Trans. Fundam., vol. E-91A, no. 6, pp. 1488-1501, 2008.）。従って、データ圧縮、誤り訂正に関する問題における符号を疎行列を用いて構成する場合、本アルゴリズムを線形計画法と併用することによって効率良い符号化実現が可能となる。
【００７２】
なお図７は、式（１）を緩和して線形計画法で解く際に非整数解出力を回避するための既存のアルゴリズム（非特許文献２）と比較したものである。同図中、"Standard"，"Cutting Plane"，"Slice"はそれぞれ式（１）を緩和したものを線形計画問題で解いただけのもの、Standardの条件に加え切除平面法を用いたもの、Standardの条件に加え本アルゴリズムを用いたものである。切除平面法を用いたアルゴリズムの結果が復号誤りの観点からは最も良く、本発明によるものがそれに次ぐ。ただし、非特許文献２の切除平面法は、符号を構成する行列から新たな拘束条件を見出し追加するという方式であるため、必ずしも行列の疎行列性は有効に利用されない。従って本方式とは異なり符号長ｎに関する多項式オーダーの実行時間は保証されていない。
【００７３】
なお、上記の実施の形態では、図１の線形符号器の構成に基づいて説明したが、当該装置は、コンピュータとプログラムによっても実現でき、プログラムを記憶媒体に記録することも、ネットワークを通して提供することも可能である。
【００７４】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００７５】
１ 入力部
２ 記憶部
３ 出力部
１０ 処理部
１１ 判別アルゴリズム実行部
１２ 線形計画問題処理部
【特許請求の範囲】
【請求項１】
対象となるアルファベットを２値｛０，１｝とし、該｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１｝nを
【数１３】
（但し、記号argは右辺のmaxを達成する
【数１４】
を左辺のxとして出力することを意味する）
として与える線形符号の最適な整数解を求める最尤復号器であって、
前記式（１）の緩和問題を線形計画法によって解く線形計画問題処理手段と、
実行可能領域を前記線形計画問題処理手段により得られた目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス領域）において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、
を有することを特徴とするLP復号器。
【請求項２】
対象となるアルファベットを２値｛０，１｝とし、該｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１｝nを
【数１５】
（但し、記号argは右辺のmaxを達成する
【数１６】
を左辺のxとして出力することを意味する）
として与える線形符号の最適な整数解を求める整数解計算方法であって、
線形計画問題処理手段が、前記式（１）の緩和問題を線形計画法によって解く線形計画問題処理ステップと、
判別アルゴリズム実行手段が、実行可能領域を前記線形計画問題処理ステップで得られた目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス領域）内において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行ステップと、
を行うことを特徴とする整数解計算方法。
【請求項３】
コンピュータを、
請求項１記載のLP復号器の各手段として機能させるための整数解計算プログラム。
【請求項１】
対象となるアルファベットを２値｛０，１｝とし、該｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１｝nを
【数１３】
（但し、記号argは右辺のmaxを達成する
【数１４】
を左辺のxとして出力することを意味する）
として与える線形符号の最適な整数解を求める最尤復号器であって、
前記式（１）の緩和問題を線形計画法によって解く線形計画問題処理手段と、
実行可能領域を前記線形計画問題処理手段により得られた目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス領域）において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、
を有することを特徴とするLP復号器。
【請求項２】
対象となるアルファベットを２値｛０，１｝とし、該｛０，１｝上の確率分布Ｐ、ｎ×ｋ行列Ａ，及びシンドロームｕ∈｛０，１｝kが与えられたとき長さｎの２値系列ｘ∈｛０，１｝nを
【数１５】
（但し、記号argは右辺のmaxを達成する
【数１６】
を左辺のxとして出力することを意味する）
として与える線形符号の最適な整数解を求める整数解計算方法であって、
線形計画問題処理手段が、前記式（１）の緩和問題を線形計画法によって解く線形計画問題処理ステップと、
判別アルゴリズム実行手段が、実行可能領域を前記線形計画問題処理ステップで得られた目的関数ｆの最適値から適切な値（例えばｆの初期値）までを一定間隔εで等分した領域（スライス領域）内において、分割された各スライス領域について順に超立方体の頂点を含むか否かを判定し、該領域に頂点が含まれる場合に、含まれる頂点の座標ｘを整数解として出力し、含まれない場合はその時点で得られた非整数解を記憶手段に格納し、すべてのスライス領域を走査した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行ステップと、
を行うことを特徴とする整数解計算方法。
【請求項３】
コンピュータを、
請求項１記載のLP復号器の各手段として機能させるための整数解計算プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−２５７１０８（Ｐ２０１２−２５７１０８Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１１−１２９３３４（Ｐ２０１１−１２９３３４）
【出願日】平成２３年６月９日（２０１１．６．９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２３年６月９日（２０１１．６．９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１３７９１２）国立大学法人 東京大学 (1,942)
【Ｆターム（参考）】
[ Back to top ]