(57)【要約】【課題】計算時間を短縮することを課題とする。【解決手段】推定装置は、まず、初期の制約条件を用いて暫定解ｚｊを算出する。次に、行列の要素が０でない列を示すインデックスｊの集合を作成し、ｊの集合を、集合Ｓ０及び集合Ｓ１にそれぞれ分類する。続いて、線形方程式の切片が０である場合にはＳ１に分類されたｊの数が奇数となるように、また、切片が１である場合にはＳ１に分類されたｊの数が偶数となるように調整する。調整の結果、Ｓ１に属することとなったｊに対応する暫定解ｚｊ全てについて１との距離を加算した加算値と、Ｓ０に属することとなったｊに対応する暫定解ｚｊ全てについて０との距離を加算した加算値との総和が、１以上となるか否かを判定する。判定の結果、１以上とならないと判定した場合に、判定に用いた不等式に基づき切除不等式を抽出し、制約不等式の集合に追加する。【選択図】図１
2010278782.tif 000002
【特許請求の範囲】
【請求項１】
０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化する推定装置であって、
０以上かつ１以下であることを示す制約不等式の集合を初期の制約条件として、また、暫定的な最適解ｚｊを切除する切除不等式が抽出された場合には当該切除不等式を追加した制約不等式の集合を新たな制約条件として、暫定解ｚｊを算出する暫定解算出手段と、
前記線形方程式の係数である行列の各行ごとに、行列の要素が０でない列を示すインデックスｊの集合を作成し、当該インデックスｊの集合を、当該インデックスｊに対応する暫定解ｚｊと１との距離が０との距離を上回る場合には第一集合Ｓ０に、暫定解ｚｊと１との距離が０との距離を下回る場合には第二集合Ｓ１にそれぞれ分類する分類手段と、
前記線形方程式の切片が０である場合には前記第二集合Ｓ１に分類されたインデックスｊの数が奇数となるように、また、前記線形方程式の切片が１である場合には前記第二集合Ｓ１に分類されたインデックスｊの数が偶数となるように、前記分類手段によって分類された第一集合Ｓ０及び第二集合Ｓ１を調整する調整手段と、
前記調整手段によって調整された結果、前記第二集合Ｓ１に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて１との距離を加算した加算値と、前記第一集合Ｓ０に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて０との距離を加算した加算値との総和が、１以上となるか否かを判定する判定手段と、
前記判定手段によって判定された結果、１以上とならないと判定した場合に、前記判定に用いた不等式に基づき前記切除不等式を抽出する抽出手段と、
前記抽出手段によって抽出された切除不等式を前記制約不等式の集合に追加する追加手段と
を備えたことを特徴とする推定装置。
【請求項２】
前記抽出手段によって切除不等式が抽出されない場合に、前記行列を、０と１との間の中央値である１／２と前記暫定解ｚｊとの距離が小さいインデックスｊに対応する行列の行の成分を０にするように変形する変形手段をさらに備え、
前記分類手段は、前記変形手段によって変形後の行列の各行ごとに、前記インデックスｊの集合を第一集合Ｓ０及び第二集合Ｓ１にそれぞれ分類することを特徴とする請求項１に記載の推定装置。
【請求項３】
請求項１または２に記載の推定装置を、加法的雑音を伴う通信路の符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が備えたことを特徴とする復号器。
【請求項４】
請求項１または２に記載の推定装置を、固定長無歪み符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が備えたことを特徴とする復号器。
【請求項５】
請求項１または２に記載の推定装置を、補助情報を利用できる固定長無歪み符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が備えたことを特徴とする復号器。
【請求項６】
請求項１または２に記載の推定装置を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで、通信路に送出する情報を符号化する符号器が備えたことを特徴とする符号器。
【請求項７】
請求項１または２に記載の推定装置を、通信路に送出する情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が備えたことを特徴とする復号器。
【請求項８】
請求項１または２に記載の推定装置を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで、有歪み符号によって情報を符号化する符号器が備えたことを特徴とする符号器。
【請求項９】
請求項１または２に記載の推定装置を、有歪み符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が備えたことを特徴とする復号器。
【請求項１０】
０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化する推定方法であって、
コンピュータが、
０以上かつ１以下であることを示す制約不等式の集合を初期の制約条件として、また、暫定的な最適解ｚｊを切除する切除不等式が抽出された場合には当該切除不等式を追加した制約不等式の集合を新たな制約条件として、暫定解ｚｊを算出する暫定解算出工程と、
前記線形方程式の係数である行列の各行ごとに、行列の要素が０でない列を示すインデックスｊの集合を作成し、当該インデックスｊの集合を、当該インデックスｊに対応する暫定解ｚｊと１との距離が０との距離を上回る場合には第一集合Ｓ０に、暫定解ｚｊと１との距離が０との距離を下回る場合には第二集合Ｓ１にそれぞれ分類する分類工程と、
前記線形方程式の切片が０である場合には前記第二集合Ｓ１に分類されたインデックスｊの数が奇数となるように、また、前記線形方程式の切片が１である場合には前記第二集合Ｓ１に分類されたインデックスｊの数が偶数となるように、前記分類工程によって分類された第一集合Ｓ０及び第二集合Ｓ１を調整する調整工程と、
前記調整工程によって調整された結果、前記第二集合Ｓ１に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて１との距離を加算した加算値と、前記第一集合Ｓ０に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて０との距離を加算した加算値との総和が、１以上となるか否かを判定する判定工程と、
前記判定工程によって判定された結果、１以上とならないと判定した場合に、前記判定に用いた不等式に基づき前記切除不等式を抽出する抽出工程と、
前記抽出工程によって抽出された切除不等式を前記制約不等式の集合に追加する追加工程と
を含んだことを特徴とする推定方法。
【請求項１１】
前記抽出工程によって切除不等式が抽出されない場合に、前記行列を、０と１との間の中央値である１／２と前記暫定解ｚｊとの距離が小さいインデックスｊに対応する行列の行の成分を０にするように変形する変形工程をさらに含み、
前記分類工程は、前記変形工程によって変形後の行列の各行ごとに、前記インデックスｊの集合を第一集合Ｓ０及び第二集合Ｓ１にそれぞれ分類することを特徴とする請求項１０に記載の推定方法。
【請求項１２】
請求項１０または１１に記載の推定方法を、加法的雑音を伴う通信路の符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が含むことを特徴とする復号方法。
【請求項１３】
請求項１０または１１に記載の推定方法を、固定長無歪み符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が含むことを特徴とする復号方法。
【請求項１４】
請求項１０または１１に記載の推定方法を、補助情報を利用できる固定長無歪み符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が含むことを特徴とする復号方法。
【請求項１５】
請求項１０または１１に記載の推定方法を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで、通信路に送出する情報を符号化する符号器が含むことを特徴とする符号方法。
【請求項１６】
請求項１０または１１に記載の推定方法を、通信路に送出する情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が含むことを特徴とする復号方法。
【請求項１７】
請求項１０または１１に記載の推定方法を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで、有歪み符号によって情報を符号化する符号器が含むことを特徴とする符号方法。
【請求項１８】
請求項１０または１１に記載の推定方法を、有歪み符号によって符号化された情報を、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化することで復号化する復号器が含むことを特徴とする復号方法。
【請求項１９】
請求項１０〜１８のいずれか一つに記載の方法をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推定装置、符号器及び復号器に関する。
【背景技術】
【０００２】
符号化や復号化の手法には、情報を短い表現に符号化し、復号化した情報の品質を保証する「情報圧縮」の目的や、伝送した情報に雑音が混入しても正しい情報に復元する「誤り訂正」の目的が存在する。この点、２元有限体上の線形方程式を制約条件として目的関数を最適化する手法は、両目的を実現するものとして知られている（非特許文献１〜４など）。
【０００３】
ところで、線形方程式を制約条件として目的関数を最適化する整数計画問題を実数空間上の線形計画法で解くにあたり、線形方程式は、実数空間上の線形不等式の集合に変形される。そこで、符号器や復号器は、この線形不等式の集合を用いて目的関数の最適化処理を実行することになるが、線形不等式の数は指数的に増大するおそれがあり、計算処理負荷の増大や必要メモリの増大などが懸念されてきた。
【０００４】
このため、従来、例えば非特許文献６では、適応的に線形不等式を追加する手法が提案されている。この手法では、まず、初期の線形不等式の集合のみを制約条件として暫定的な最適解を求め、次に、暫定的な最適解が満たしていない線形不等式（暫定的な最適解を切除する線形不等式）を集合から探索する。そして、線形不等式を探索できた場合に、その線形不等式を集合に追加し、新たな集合を制約条件として、再び暫定的な最適解を求める。なお、その他にも、各種アルゴリズムが提案されている（非特許文献５〜７など）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】J.  Muramatsu  and  S.  Miyake,  “Hash  property  and  coding  theorems  for  sparse  matrices  and  maximum-likelihood  coding,”、http://arxiv.org/abs/0801.3878
【非特許文献２】J.  Muramatsu  and  S.  Miyake,  “Hash  property  and  fixed-rate  universal  coding  theorems,”、http://arxiv.org/abs/0804.1183
【非特許文献３】J.  Muramatsu,  “Secret  key  agreement  from  correlated  source  outputs  using  low  density  parity  check  matrices,”、IEICE  Trans.  Fundamentals,  vol.  E89-A,  no.  7,  pp.  2036-2046,  Jul.  2006.
【非特許文献４】Jun  Muramatsu  and  Shigeki  Miyake,  “Construction  of  Wiretap  Channel  Codes  by  Using  Sparse  Matrices,”、第6回シャノン理論ワークショップ予稿集,  2008.
【非特許文献５】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.
【非特許文献７】M.  Miwa,  T.  Wadayama,  I.  Takumi,  “A  cutting  plane  method  based  on  redundant  rows  for  improving  fractional  distance,”、http://arxiv.org/abs/0807.2701
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記した従来の技術では、依然として計算時間が長いという課題があった。例えば、適応的に線形不等式を追加する従来の手法では、暫定的な最適解を切除する線形不等式を得るために条件を繰り返し検査しなければならず、依然として計算時間は長くなってしまう。
【０００７】
開示の技術は、上記に鑑みてなされたものであって、計算時間を短縮することが可能な推定装置、符号器、復号器、推定方法、符号方法、復号方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願の開示する推定装置、符号器及び復号器は、一つの態様において、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化する推定装置であって、０以上かつ１以下であることを示す制約不等式の集合を初期の制約条件として、また、暫定的な最適解ｚｊを切除する切除不等式が抽出された場合には当該切除不等式を追加した制約不等式の集合を新たな制約条件として、暫定解ｚｊを算出する暫定解算出手段と、前記線形方程式の係数である行列の各行ごとに、行列の要素が０でない列を示すインデックスｊの集合を作成し、当該インデックスｊの集合を、当該インデックスｊに対応する暫定解ｚｊと１との距離が０との距離を上回る場合には第一集合Ｓ０に、暫定解ｚｊと１との距離が０との距離を下回る場合には第二集合Ｓ１にそれぞれ分類する分類手段と、前記線形方程式の切片が０である場合には前記第二集合Ｓ１に分類されたインデックスｊの数が奇数となるように、また、前記線形方程式の切片が１である場合には前記第二集合Ｓ１に分類されたインデックスｊの数が偶数となるように、前記分類手段によって分類された第一集合Ｓ０及び第二集合Ｓ１を調整する調整手段と、前記調整手段によって調整された結果、前記第二集合Ｓ１に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて１との距離を加算した加算値と、前記第一集合Ｓ０に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて０との距離を加算した加算値との総和が、１以上となるか否かを判定する判定手段と、前記判定手段によって判定された結果、１以上とならないと判定した場合に、前記判定に用いた不等式に基づき前記切除不等式を抽出する抽出手段と、前記抽出手段によって抽出された切除不等式を前記制約不等式の集合に追加する追加手段とを備える。
【発明の効果】
【０００９】
本願の開示する推定装置、符号器、復号器、推定方法、符号方法、復号方法及びプログラムの一つの態様によれば、計算時間を短縮することが可能になるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る推定装置１０の構成を示すブロック図である。
【図２】図２は、実施例１に係る推定装置１０における処理手順を示すフローチャートである。
【図３】図３は、加法的雑音を伴う通信路に対する誤り訂正符号を説明するための図である。
【図４−１】図４−１は、第一アルゴリズムを説明するためのフローチャートである。
【図４−２】図４−２は、第一アルゴリズムを説明するためのフローチャートである。
【図４−３】図４−３は、第一アルゴリズムを説明するためのフローチャートである。
【図５−１】図５−１は、第二アルゴリズムを説明するためのフローチャートである。
【図５−２】図５−２は、第二アルゴリズムを説明するためのフローチャートである。
【図５−３】図５−３は、第二アルゴリズムを説明するためのフローチャートである。
【図６】図６は、実施例２に係る推定装置１０の構成を示すブロック図である。
【図７】図７は、実施例２に係る推定装置１０における処理手順を示すフローチャートである。
【図８】図８は、符号化、復号化に現れる最適化問題を示す図である。
【図９】図９は、固定長無歪み符号における符号器及び復号器を説明するための図である。
【図１０】図１０は、補助情報を利用できる固定長無歪み符号における符号器及び復号器を説明するための図である。
【図１１】図１１は、一般の通信路符号における符号器及び復号器を説明するための図である。
【図１２】図１２は、一般の通信路符号における符号器及び復号器を説明するための図である。
【図１３】図１３は、有歪み符号における符号器及び復号器を説明するための図である。
【図１４】図１４は、有歪み符号における符号器及び復号器を説明するための図である。
【図１５】図１５は、シミュレーション結果を示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する推定装置の実施例を詳細に説明する。なお、以下の実施例により本発明が限定されるものではない。
【実施例１】
【００１２】
実施例１に係る推定装置１０は、２元の有限体ＧＦ（２）上において線形方程式Ａｚ＝ｃを制約条件として関数ｆ（ｚ）を最適化する装置である。Ａは、ｌ行ｎ列の行列であり、ｚは、ｎ次元の列ベクトルであり、ｃは、ｌ次元の列ベクトルである。また、実施例１に係る推定装置１０は、以下に説明するように、線形方程式Ａｚ＝ｃを変形した実数空間上の線形不等式の集合Ineq（ｋ）に、暫定的な最適解を切除できる不等式だけを加える手法を用いる。以下、まず、図１を用いて実施例１に係る推定装置１０の構成を説明し、次に、図２〜図５−３を用いて実施例１に係る推定装置１０における処理手順及びアルゴリズムを説明する。
【００１３】
なお、行列Ａはフルランクである必要は無く、非特許文献７にあるように、非整数成分を持つ０ベクトル付近の最適解を切除する冗長行を行列に事前に付加しておくこともできる。非整数成分を持つ０ベクトル付近の最適解を切除する冗長行を求める時には、本発明の第一アルゴリズム、第二アルゴリズムを利用することができる。但し、以下の実施例にあるアルゴリズムでは、第二アルゴリズムを、冗長行を含まないもとの行列に対して実行してもよい。
【００１４】
［実施例１に係る推定装置１０の構成］
図１は、実施例１に係る推定装置１０の構成を示すブロック図である。実施例１に係る推定装置１０は、図１に示すように、記憶部１１と、入力部１２と、暫定解算出部１３と、切除不等式抽出部１４と、出力部１５とを備える。
【００１５】
記憶部１１は、推定装置１０における推定処理に用いる各種情報を記憶する。具体的には、記憶部１１は、推定装置１０を利用する利用者などによって予め登録される情報として、数式（１−１）に示す行列Ａ、及び、数式（１−２）に示す初期の制約不等式の集合を記憶する。また、記憶部１１は、数式（１−３）に示すベクトルｃを入力部１２から格納されることで記憶する。また、記憶部１１は、推定装置１０における推定処理の中で、切除不等式抽出部１４によって抽出された切除不等式を切除不等式抽出部１４から格納されることで記憶する。記憶部１１が記憶するこれらの情報は、主に、暫定解算出部１３による処理に利用される。
【００１６】
【数１−１】
2010278782.tif 000003
【００１７】
【数１−２】
2010278782.tif 000004
【００１８】
【数１−３】
2010278782.tif 000005
【００１９】
入力部１２は、推定装置１０における推定処理の処理対象信号を取得する。具体的には、入力部１２は、推定装置１０の外部から、処理対象信号であるベクトルｃを通信などによって取得し、取得したベクトルｃを記憶部１１に格納する。なお、入力部１２は、推定装置１０の外部から目的関数を取得し、取得した目的関数を暫定解算出部１３に伝達してもよい。
【００２０】
暫定解算出部１３は、最適化法（線形計画法）によって暫定的な最適解（適宜「暫定解」という）を算出する。具体的には、暫定解算出部１３は、記憶部１１に予め登録された初期の制約不等式の集合や、推定処理の中で切除不等式抽出部１４によって更新され記憶部１１に格納された制約不等式の集合を用いて暫定解を算出し、算出した暫定解を切除不等式抽出部１４に格納する。暫定解は、数式（１−４）に示すベクトルｚである。
【数１−４】
2010278782.tif 000006
【００２１】
切除不等式抽出部１４は、暫定解を切除する不等式を抽出する。具体的には、切除不等式抽出部１４は、記憶部１１に記憶されている行列Ａ及びベクトルｃと、暫定解算出部１３によって算出された暫定解とを用いて、行列Ａの全ての行に対して第一アルゴリズムを適用し、切除不等式が存在するか否かを判定する。
【００２２】
切除不等式抽出部１４は、切除不等式が存在する場合には、暫定解を切除する行を行列Ａから抽出するとともに切除不等式を抽出し、抽出した切除不等式を記憶部１１に格納する。この時、切除不等式抽出部１４は、記憶部１１に記憶されている制約条件不等式の集合に、新たに抽出した切除不等式を加え、制約条件不等式の集合を更新するとともに、暫定解算出部１３に、制約条件不等式の集合を更新した旨通知する。
【００２３】
一方、切除不等式抽出部１４は、切除不等式が存在しない場合には、暫定解の成分が全て整数であるか否かをさらに判定し、全て整数である場合には、当該暫定解を最終解として出力部１５に通知する。暫定解の成分に非整数を含む場合には、切除不等式抽出部１４は、行列Ａ及びベクトルｃに対して第二アルゴリズムを適用し、行列Ａ´（ダッシュ）、ベクトルｃ´（ダッシュ）を生成する。
【００２４】
そして、切除不等式抽出部１４は、行列Ａ´及びベクトルｃ´と、暫定解算出部１３によって算出された暫定解とを用いて、行列Ａ´の全ての行に対して第一アルゴリズムを適用し、切除不等式が存在するか否かを判定する。
【００２５】
切除不等式抽出部１４は、切除不等式が存在する場合には、暫定解を切除する行を行列Ａ´から抽出するとともに切除不等式を抽出し、抽出した切除不等式を記憶部１１に格納する。この時、切除不等式抽出部１４は、記憶部１１に記憶されている制約条件不等式の集合に、新たに抽出した切除不等式を加え、制約条件不等式の集合を更新する。一方、切除不等式抽出部１４は、切除不等式が存在しない場合には、非整数を含む当該暫定解を最終解として出力部１５に通知する。
【００２６】
出力部１５は、推定装置１０における推定処理の最終解を出力する。具体的には、出力部１３は、切除不等式抽出部１４から通知された最終解を出力する。
【００２７】
［実施例１に係る推定装置１０における処理手順及びアルゴリズム］
次に、図２〜図５−３を用いて、実施例１に係る推定装置１０における処理手順及びアルゴリズムを説明する。図２は、実施例１に係る推定装置１０における処理手順を示すフローチャートであり、図３は、加法的雑音を伴う通信路に対する誤り訂正符号を説明するための図である。また、図４−１〜図４−３は、第一アルゴリズムを説明するためのフローチャートであり、図５−１〜図５−３は、第二アルゴリズムを説明するためのフローチャートである。
【００２８】
［推定装置１０における処理手順］
図２に示すように、まず、推定装置１０において、入力部１２が、処理対象信号であるベクトルｃを取得する（ステップＳ１）。
【００２９】
次に、暫定解算出部１３が、記憶部１１に予め登録された初期の制約不等式の集合を制約条件に設定し（ステップＳ２）、設定した制約条件を用いて最適化法によって暫定解を算出する（ステップＳ３）。
【００３０】
続いて、切除不等式抽出部１４が、記憶部１１に記憶されている行列Ａ及びベクトルｃと、暫定解算出部１３によって算出された暫定解とを用いて、行列Ａの全ての行に対して第一アルゴリズムを適用し、切除不等式が存在するか否かを判定する（ステップＳ４）。
【００３１】
切除不等式が存在し、抽出した場合には（ステップＳ５肯定）、切除不等式抽出部１４は、記憶部１１に記憶されている制約条件不等式の集合に、新たに抽出した切除不等式を加え、制約条件不等式の集合を更新する（ステップＳ６）。
【００３２】
一方、切除不等式が存在せず、抽出しない場合には（ステップＳ５否定）、切除不等式抽出部１４は、暫定解の成分が全て整数であるか否かをさらに判定する（ステップＳ７）。全て整数である場合には（ステップＳ７肯定）、当該暫定解を最終解として出力部１５に通知する（ステップＳ８）。
【００３３】
一方、暫定解の成分に非整数を含む場合には（ステップＳ７否定）、切除不等式抽出部１４は、行列Ａ及びベクトルｃに対して第二アルゴリズムを適用し、行列Ａ´、ベクトルｃ´を生成する（ステップＳ９）。
【００３４】
そして、切除不等式抽出部１４は、行列Ａ´及びベクトルｃ´と、暫定解算出部１３によって算出された暫定解とを用いて、行列Ａ´の全ての行に対して第一アルゴリズムを適用し、切除不等式が存在するか否かを判定する（ステップＳ１０）。なお、第一アルゴリズムを適用する行の順序は任意であるが、例えば、行列の上の行もしくは下の行から順に、最初に暫定解を切除する切除不等式が見つかったところで終了する、あるいは、暫定解を切除する冗長行ａ´ｉで｜Ｓｕｐｐ（ａ´ｉ）｜が最も小さい行の切除不等式を求めるといった方法が考えられる。ここで、ベクトルａ´ｉは、行列Ａ´の中の一つの行である。
【００３５】
切除不等式が存在し、抽出した場合には（ステップＳ１１肯定）、切除不等式抽出部１４は、記憶部１１に記憶されている制約条件不等式の集合に、新たに抽出した切除不等式を加え、制約条件不等式の集合を更新する（ステップＳ６）。
【００３６】
一方、切除不等式が存在せず、抽出しない場合には（ステップＳ１１否定）、非整数を含む当該暫定解を最終解として出力部１５に通知する。（ステップＳ８）。
【００３７】
なお、図２のステップＳ２とステップＳ３との間において、さらに、記録部１１に登録されている制約不等式の集合に対して暫定解が等号を満たしていない不等式を削除する、という処理を実行してもよい。このような処理をすることによって、線形計画法を適用する制約不等式の数を抑える効果がある。
【００３８】
［誤り訂正符号の構成法及び線形計画法を用いた最尤復号法］
ところで、第一アルゴリズムを説明する前に、行列を用いた加法的雑音を伴う通信路に対する誤り訂正符号の構成法、及び、線形計画法を用いた最尤復号法を説明する。
【００３９】
［加法的雑音を伴う通信路に対する誤り訂正符号］
例えば、加法的雑音を伴う通信路に対する誤り訂正符号を例に従来の手法を説明する。加法的雑音を伴う通信路に対する誤り訂正符号は、図３で与えられる。図３は、加法的雑音を伴う通信路に対する誤り訂正符号を説明するための図である。以下、数式（１−５）に示すように、ＧＦ（２）を２元の有限体とし、ｎ次元のベクトル空間をＧＦ（２）ｎと示す。
【数１−５】
2010278782.tif 000007
【００４０】
整数ｎを通信路の入出力長とすると、ＧＦ（２）上のｎ次元の列ベクトルは、数式（１−６）とする。
【数１−６】
2010278782.tif 000008
ここで、数式（１−７）は、全てＧＦ（２）上の要素である。
【数１−７】
2010278782.tif 000009
【００４１】
ＧＦ（２）上のｌ×ｎ行列Ａを数式（１−８）とする。
【数１−８】
2010278782.tif 000010
【００４２】
また、全ての成分が０となる零ベクトルを数式（１−９）と記す。
【数１−９】
2010278782.tif 000011
なお、零ベクトルの次元は特に明示しないが、ここではｌ次元のベクトルとする。
【００４３】
誤り訂正符号においては、数式（１−１０）を満たす集合を「符号」もしくは「符号語の集合」と呼ぶ。行列Ａのランクがｌであるとき、Ｃはｎ−ｌ次元のベクトル空間となる。また、Ｃは、ｎ次元ベクトル空間ＧＦ（２）ｎの部分空間となっている。
【数１−１０】
2010278782.tif 000012
【００４４】
Ｃがｎ−ｌ次元のベクトル空間であることから、メッセージの集合をＧＦ（２）ｎ−ｌとすれば、集合ＧＦ（２）ｎ−ｌから集合Ｃへの全単射が存在する。実際には、数式（１−１１）に示すメッセージベクトルに対して、「生成行列」と呼ばれるｎ×（ｎ−ｌ）行列Ｇを用いて、数式（１−１２）を求めることによって、Ｃの要素を対応させる。生成行列Ｇは、任意のメッセージｍに対してＧｍがＣの要素になるように与えることができる。
【数１−１１】
2010278782.tif 000013
【数１−１２】
2010278782.tif 000014
【００４５】
加法的雑音を伴う通信路の誤り訂正符号において、メッセージｍは、数式（１−１３）へ符号化され、通信路に入力される。
【数１−１３】
2010278782.tif 000015
【００４６】
雑音を数式（１−１４）とすると、加法的雑音を伴う通信路の出力は、数式（１−１５）、数式（１−１６）となる。ここで、（＋）（丸の中にプラスの記号）は、ＧＦ（２）の加法を表す。
【数１−１４】
2010278782.tif 000016
【数１−１５】
2010278782.tif 000017
【数１−１６】
2010278782.tif 000018
【００４７】
数式（１−１６）をベクトルの成分で書き表すと、数式（１−１７）となる。
【数１−１７】
2010278782.tif 000019
【００４８】
ベクトルｙを受信した復号器は、「最尤復号」と呼ばれる方法を用いて、入力信号ベクトルｘを推定した数式（１−１８）を求める。
【数１−１８】
2010278782.tif 000020
【００４９】
通信路が定常無記憶であることを仮定すると、遷移確率は、数式（１−１９）となる。
【数１−１９】
2010278782.tif 000021
【００５０】
ここで、Ｐｒｏｂ（ｚｊ）は、一次元の雑音ｚｊが発生する確率であり、数式（１−２０）を仮定する。
【数１−２０】
2010278782.tif 000022
【００５１】
最尤復号では、数式（１−２１）、数式（１−２２）のように、推定したｘベクトルを求める。
【数１−２１】
2010278782.tif 000023
【数１−２２】
2010278782.tif 000024
【００５２】
ここで、最初の＝では、通信路の入力が数式（１−２３）を満たしていることと、数式（１−２４）を用いた。
【数１−２３】
2010278782.tif 000025
【数１−２４】
2010278782.tif 000026
【００５３】
また、最後の＝では、数式（１−２５）から、ｚｊ＝０を満たすｊをできる限り大きくする、すなわちｚｊ＝１を満たすｊをできる限り小さくすることにより、目的関数の最大化を達成できることによる。
【数１−２５】
2010278782.tif 000027
【００５４】
数式（１−２６）の場合は、同様に、数式（１−２７）となる。
【数１−２６】
2010278782.tif 000028
【数１−２７】
2010278782.tif 000029
【００５５】
［線形計画法を用いた最尤復号法］
以下では、数式（１−２８）を例にとり、非特許文献５で提案された線形計画法を用いた最尤復号法を説明する。
【数１−２８】
2010278782.tif 000030
【００５６】
復号器は、受信ベクトルｙから、数式（１−２９）
【数１−２９】
2010278782.tif 000031
すなわち、
【数１−３０】
2010278782.tif 000032
を求めておく。
【００５７】
数式（１−２８）は、ＧＦ（２）上の線形方程式
【数１−３１】
2010278782.tif 000033
を制約条件として、線形の目的関数
【数１−３２】
2010278782.tif 000034
を最小化する問題である。すなわち、数式（１−２８）は、数式（１−３３）と等価となる。
【数１−３３】
2010278782.tif 000035
【００５８】
以下、目的関数をｆ（ｚ）と記し、最大化、最小化を単に「最適化」と呼ぶ。また、数式（１−２８）は厳密には整数計画問題であり、実数空間上での線形計画問題ではない。以下では、ＧＦ（２）上の線形方程式を制約条件として目的関数ｆ（ｚ）を最適化する問題を単に「ＧＦ（２）上の線形方程式を制約条件とする整数計画問題」と呼ぶ。
【００５９】
ＧＦ（２）上の線形方程式を制約条件とする整数計画問題を実数空間上の線形計画法で解くにあたり、ＧＦ（２）上の線形方程式を実数空間上の線形不等式の集合に書き改める。
【００６０】
Ａにある一つの行ベクトル
【数１−３４】
2010278782.tif 000036
に注目すると、線形方程式Ａｚ＝ｃは、ｌ個のＧＦ（２）上の方程式
【数１−３５】
2010278782.tif 000037
の集合とみなせる。ここで、「・」は、ベクトルの内積を表す。ベクトルａ＝（ａ１、・・・、ａｊ、・・・、ａｎ）に対して、集合｛１、２、・・・、ｎ｝の部分集合Ｓｕｐｐ（ａｉ）（ａは行ベクトル）を数式（１−３６）のように定義する。
【数１−３６】
2010278782.tif 000038
【００６１】
以下、｜Ｓ｜を集合Ｓの大きさを表し、Ｓ＼Ｓ´（ダッシュ）は、差集合（Ｓに含まれていてＳ´（ダッシュ）に含まれない要素からなる集合）を表す。ＧＦ（２）上の線形方程式である数式（１−３５）を、実数空間上の線形不等式の集合である数式（１−３７）に書き改める。
【数１−３７】
2010278782.tif 000039
ただし、部分集合Ｓは、Ｃｉ＝０のときは｜Ｓ｜が奇数であるものだけを、Ｃｉ＝１のときは｜Ｓ｜が偶数であるものだけをとる。
【００６２】
このように、ＧＦ（２）上の線形方程式を実数空間上の線形不等式の集合
【数１−３８】
2010278782.tif 000040
に変形（緩和）して、線形計画法を用いて解を求め、これを利用して目的関数ｆ（ｚ）の最適化を行う。
【００６３】
ここで、非特許文献５によれば、線形計画法で求めた最適解を与えるｚの成分が全て整数であったときには、ＧＦ（２）上の線形方程式を制約条件とする整数計画問題の最適解になっていることが証明されている。
【００６４】
しかしながら、上記の手法では、以下の二つの課題が知られている。
【００６５】
まず、数式（１−３７）に含まれる不等式は、２｜Ｓｕｐｐ（ａｉ）｜−１個存在する。これは、不等式の個数がベクトルａｉに含まれる１の個数に対して指数的に大きくなることを意味しており、線形計画法の計算量や必要なメモリ量の増加を引き起こす。
【００６６】
また、線形計画法で求めた最適解を与えるｚの成分が常に全て整数であるとは限らない。ｚに非整数な成分を含む場合、ＧＦ（２）上の線形方程式を制約条件とする整数計画問題の最適解を求めたことにはなっていない。
【００６７】
［アルゴリズムＡ］
上記したように、数式（１−３８）に含まれる不等式の全てを制約条件として線形計画法を解くと多くの計算量・メモリ量を必要とするため、アルゴリズムＡでは、以下のような手続きで最適解を求める。
【００６８】
（１）ｋ＝０とする。数式（１−３９）で示される初期の不等式の集合のみを制約式として、線形計画法により暫定的な最適解を求める。
【数１−３９】
2010278782.tif 000041
【００６９】
（２）暫定的な最適解が満たしていない不等式(暫定的な最適解を切除する切除不等式)を一つ以上数式（１−３８）から探す。もし見付からなかったら、暫定的な最適解を最終的な最適解として終了する。
【００７０】
（３）ステップ（２）で暫定的な最適解を切除する切除不等式が見付かれば、その切除不等式をＩｎｅｑ（ｋ）に追加したものをＩｎｅｑ（ｋ＋１）として、Ｉｎｅｑ（ｋ＋１）を制約式とした線形計画法により最適解を求め、これを新たな暫定的な最適解とする。
【００７１】
（４）ｋの値を１増やしてステップ（２）へ戻る。
【００７２】
［アルゴリズムＢ］
アルゴリズムＡにおいて、各ｉでＩｎｅｑ（ａｉ・ｚ＝ｃｉ）の全ての不等式を求める必要は無く、暫定的な最適解を切除できる切除不等式をＩｎｅｑ（ａｉ・ｚ＝ｃｉ）から見付けることができれば十分であることが分かる。しかし、素朴な方法では、２｜Ｓｕｐｐ（ａｉ）｜−１個の不等式が暫定的な最適解を切除できるかどうかを順に調べることになり、依然として指数的に増大する計算量が残る。非特許文献６では、制約条件となるＧＦ（２）の方程式がａｉ・ｚ＝０（右辺が０）であることを仮定して、Ｏ(lｍａｘｉ｜Ｓｕｐｐ（ａｉ）｜＋ｎｌｏｇ２ｎ)の計算量で計算できるアルゴリズムを以下のように与えている。これを「アルゴリズムＢ」と呼ぶ。非整数の成分を含む暫定的な最適解をｚとする。
【００７３】
（１）Ｓｕｐｐ（ａｉ）のインデックスを、インデックスと対応するｚの成分の値の大きい順に並び変えたものを求めておく。
【００７４】
（２）ｖ＝１としてＳ（１）をｚｊが最大となるｊだけからなる集合とする。最大となるｊは、ステップ（１）で求めた並び替えを利用する。
【００７５】
（３）数式（１−４０）を満たしていなければ、これをｚを切除している切除不等式として終了する。
【数１−４０】
2010278782.tif 000042
【００７６】
（４）ステップ（３）で不等式が数式（１−４０）を満たしている場合、数式（１−４１）を満たしているならば、切除している不等式は見つからないことを報告して終了する。
【数１−４１】
2010278782.tif 000043
【００７７】
（５）ステップ（３）で不等式が数式（１−４０）を満たし、かつステップ（４）で数式（１−４１）を満たしていないならば、数式（１−４２）でｚｊのもっとも大きいｊを２個Ｓ（ｖ）に追加したものをＳ（ｖ＋２）とする。最大となるｊは、ステップ（１）で求めた並び替えを利用して求める。そして、ｖの値を２増大させる。
【数１−４２】
2010278782.tif 000044
【００７８】
Ｓ（ｖ）が、数式（１−４３）を満たしていればステップ（３）に戻る。
【数１−４３】
2010278782.tif 000045
満たしていなければ、切除している不等式は見つからないことを報告して終了する。
【００７９】
［アルゴリズムＣ］
ところで、ｚに非整数な成分を含む場合、ＧＦ（２）上の線形方程式を制約条件とする整数計画問題の最適解を求めたことにはなっていない課題については上記した通りである。続いて、この課題について非特許文献６で提案された適応的な手続を説明する。
【００８０】
非特許文献５では、「冗長行」と呼ばれる行列Ａの行ベクトル集合の線形和で書ける行を行列Ａに追加して、新たなＧＦ（２）上の線形方程式を制約条件とする整数計画問題を用意し、これを実数空間上の線形計画法で解くことにより、復号性能を向上させることができることが提案されている。具体的には以下のような方法である。
【００８１】
行列Ａの行ベクトルの集合を数式（１−４４）とする。
【数１−４４】
2010278782.tif 000046
【００８２】
また、任意のベクトルを数式（１−４５）とし、数式（１−４６）とする。
【数１−４５】
2010278782.tif 000047
【数１−４６】
2010278782.tif 000048
【００８３】
そして、ベクトルｃより、数式（１−４７）を求める。
【数１−４７】
2010278782.tif 000049
【００８４】
すると、ＧＦ（２）上の線形方程式Ａｚ＝ｃは、数式（１−４８）と同値となる。
【数１−４８】
2010278782.tif 000050
【００８５】
同様にして、行列Ａに複数の冗長行を追加して、Ａｚ＝ｃと同値な方程式をつくることができる。以後、行列Ａの「冗長行」と呼ぶときは、対応する方程式の右辺の値（上記の例ではｃｌ＋１）も含めているものとする。また、追加した冗長行に対して数式（１−３７）で定められた不等式の集合が、線形計画法が求めた非整数の成分を含む最適解を切除できる場合、これを「線形計画法が求めた非整数の成分を含む最適解を切除できる冗長行」と呼ぶ。
【００８６】
非特許文献６では、線形計画法が求めた非整数の成分を含む最適解を等式の集合で切除できるような冗長行を求める方法を提案している。具体的な方法を以下で与え、これを「アルゴリズムＣ」と呼ぶ。
【００８７】
非特許文献６と同様に、方程式Ａｚ＝ｃを仮定し、非整数の成分を含む最適解をｚとする。
【００８８】
（１）行列Ａのｊ番目の列で、対応するｚｊが非整数となる列を全て取り除き、これを新たに行列Ｂとする。
【００８９】
（２）行列Ｂの行のインデックスｉを｛１，２，・・・，ｌ｝からランダムに選び、ｉを順に記録する。
【００９０】
（３）行列Ｂのｉ番目の行のｊ番目の成分が０で無いｊをランダムに一つ選ぶ。ただし、ｊは直前に実行したステップ（４）のｊと異なるものを選ぶ。
【００９１】
（４）行列Ｂのｊ番目の列のｉ番目の成分が０で無いｉをランダムに一つ選ぶ。ただし、ｉは直前に実行したステップ（３）のｉと異なるものを選ぶ。
【００９２】
（５）ステップ（４）で選んだｉが記録に残っていれば、過去にｉが現れるまでのインデックスの記録（ｉを含む）を冗長行を求めるためのインデックスの集合とする。ステップ（４）で選んだｉが記録に残っていなければ、ステップ（３）に戻る。
【００９３】
（６）ステップ（５）で求めたインデックスの集合に対応するＡの行を全て足したものａ´を冗長行とする。
【００９４】
（７）ステップ（６）で求めた方程式ａ´・ｚ＝０からｚを切除する不等式を作ることができれば、これを線形計画法の制約不等式に追加する。切除していなければ、インデックスの記録をクリアしてステップ（２）へ戻る。方程式からｚを切除する不等式が作れるかどうかは、アルゴリズムＢを用いる。
【００９５】
［アルゴリズムＤ］
アルゴリズムＣは、アルゴリズムＡのステップ（２）において最初の行列による方程式が作る不等式群から切除不等式を見付けられなかったときに呼び出され、アルゴリズムＣによって求められた冗長行から得られた切除不等式が、アルゴリズムＡのステップ（３）において加えられる。この他、冗長行を求める方法として行列の基本変形を用いた方法が、非特許文献７で提案されている。これは、ベクトル０付近の非整数成分を含む最適解を求め、方程式Ａｚ＝０を仮定して最適解を切除する方法である。これを「アルゴリズムＤ」と呼ぶ。
【００９６】
（１）集合｛１，２，・・・，ｌ｝の部分集合Ｑを数式（１−４９）のように定義する。
【数１−４９】
2010278782.tif 000051
そして、行列ＡでＱに含まれるインデックスの行だけを残した部分行列をＡＱとする。
【００９７】
（２）ｚの成分を大きい順に並べ替えたものを数式（１−５０）とする。
【数１−５０】
2010278782.tif 000052
【００９８】
（３）ステップ（２）において求めたｊ１，ｊ２，・・・，ｊｎに対して、数式（１−５１）のように置換する。
【数１−５１】
2010278782.tif 000053
そして、数式（１−５１）の置換と対応する行列ＡＱの行の置換を行う。行列ＡＱの行を置換する行列Πとする。
【００９９】
（４）ＡＱΠに列基本変形を施して階段行列（行列の対角成分より下が全て０になる行列）を求め、これをＵとする。
【０１００】
（５）Πの逆行列Π−１を求め、ＵΠ−１のｉ番目の行ベクトルｕｉが数式（１−５２）を満たしているものを冗長行とする。
【数１−５２】
2010278782.tif 000054
複数のｉの候補があるときは、最も小さなｉと対応する冗長行を与える。
【０１０１】
このように、アルゴリズムＤは、もとの行列にアルゴリズムＤによって求めた冗長行を追加して、行列を事前に拡大しておくために用いられる。
【０１０２】
［アルゴリズムＡ〜Ｄの課題］
ところで、上記してきたアルゴリズムＡ〜Ｄには、いくつかの課題がある。
【０１０３】
第一に、アルゴリズムＢでは、数式（１−４０）を繰り返しチェックする必要がある。
【０１０４】
第二に、アルゴリズムＢ、アルゴリズムＣ、アルゴリズムＤでは、ＧＦ（２）の制約式として、方程式Ａｚ＝０を仮定していたが、一般の制約式Ａｚ＝ｃでも扱えるようにする必要がある。
【０１０５】
第三に、アルゴリズムＣでは冗長行を見付けることができずに動作し続ける可能性がある。また、同じ冗長行を何度も探索する可能性があり効率よく冗長行を見付けていない。
【０１０６】
第四に、アルゴリズムＤの階段行列への基本変形を用いた方法は、切除平面の判定が厳しすぎて冗長行が切除平面を持つことを見落とす可能性があり、効率よく冗長行を見付けていない。
【０１０７】
以上の課題は、線形計画法の実行時間を悪化させるだけでなく、最終的に整数解が求まらずに符号の性能を悪化させる可能性がある。以下に説明する第一アルゴリズム及び第二アルゴリズムは、上記の従来の手法の欠点に鑑みてなされたものであり、線形計画法で整数解が求まる確率を向上させることができるという効果を奏するものである。
【０１０８】
上記した課題を解決するための手段は、以下の二つの部分から成り立っている。
【０１０９】
第一の課題を解決するために、第一アルゴリズムは、アルゴリズムＢを改良し、ＧＦ（２）上の方程式Ａｚ＝ｃから暫定解ｚを切除する切除不等式をより効率よく求める。
【０１１０】
第二の課題を解決するために、ＧＦ（２）上の方程式Ａｚ＝ｃを同値な方程式Ａハットｚハット＝０に変形する。
【０１１１】
第三の課題、あるいは第四の課題を解決するために、アルゴリズムＣ、あるいは、アルゴリズムＤを改良し、切除する冗長行を効率よく求める。同時に、第二の課題を解決するために、一般的なＧＦ（２）上の方程式Ａｚ＝ｃを扱えるようにする。第二アルゴリズムがこれに該当する。
【０１１２】
以下、第一アルゴリズム、第二アルゴリズムを順に説明する。
【０１１３】
［第一アルゴリズム］
第一アルゴリズムでは、数式（１−３６）に示す部分集合Ｓｕｐｐ（ａ）（ａは行列Ａの一つの行ベクトル）を、ベクトルｚの成分ｚｊが１／２を超えるか否かに応じて、互いに素な部分集合Ｓ０及びＳ１に分類する。また、第一アルゴリズムでは、ベクトルｚの成分ｚｊが１／２に最も近い一つのインデックスｊを部分集合Ｓ０、Ｓ１の一方から他方へ移動させることによって、ベクトルｃの行列Ａの行と対応する成分の値ｃと、｜Ｓ１｜の偶数奇数との関係を調整する。また、第一アルゴリズムでは、暫定解を切除する切除不等式が存在するか否かを１回の不等式評価で判定する。
【０１１４】
具体的には、切除不等式抽出部１４は、集合｛１，２，・・・，ｎ｝の互いに素な部分集合Ｓ０、Ｓ１を数式（１−５３）に示すように設定する。
【数１−５３】
2010278782.tif 000055
ここで、ｚｊ＝１／２を満たすｊを部分集合Ｓ０、Ｓ１のどちらの集合に含めるようにするかは任意であるが、実施例１においては、部分集合Ｓ０に含めるものとした。
【０１１５】
切除不等式抽出部１４は、ｃ＝０の時は｜Ｓ１｜が偶数、ｃ＝１の時は｜Ｓ１｜が奇数であれば、数式（１−５４）を求める。
【数１−５４】
2010278782.tif 000056
【０１１６】
そして、切除不等式抽出部１４は、ｊ´（ダッシュ）が部分集合Ｓ０に入っていれば、これを部分集合Ｓ１に移動させ、ｊ´が部分集合Ｓ１に入っていれば、これを部分集合Ｓ０に移動させる。すなわち、移動後の部分集合Ｓ０、Ｓ１は、数式（１−５５）、数式（１−５６）で与えられる。
【数１−５５】
2010278782.tif 000057
【数１−５６】
2010278782.tif 000058
ここで、右辺の部分集合Ｓ０、Ｓ１は、移動前の部分集合Ｓ０、Ｓ１である。なお、ｃ＝０かつ｜Ｓ１｜が奇数、もしくは、ｃ＝０かつ｜Ｓ１｜が偶数のときは、部分集合Ｓ０、Ｓ１について移動を行わない。
【０１１７】
そして、切除不等式抽出部１４は、数式（１−５７）を満たしているか否かを判定することで、切除不等式が存在するか否かを判定する。
【数１−５７】
2010278782.tif 000059
数式（１−５７）を満たしていない場合には、暫定解を切除する切除不等式が存在し、当該不等式が切除不等式であるとして抽出する。一方、数式（１−５７）を満たしている場合には、暫定解を切除する切除不等式が存在しないと判定する。
【０１１８】
この第一アルゴリズムを図４−１〜図４−３を用いて説明する。切除不等式抽出部１４は、行列Ａの全ての行に対して第一アルゴリズムを適用し、切除不等式が存在するか否かを判定する。
【０１１９】
まず、切除不等式抽出部１４は、Ｓｕｐｐ（ａ）（ａは行ベクトル）をＮｕｌｌに設定する（ステップＳ１０１）。ここで、行ベクトルａは、行列Ａにある一つの行や冗長行、あるいは行列Ａに第二アルゴリズムを適用して変形した行列Ａ´（ダッシュ）の一つの行と対応する。ここで、ａ＝（ａ１，・・・，ａｊ，・・・，ａｎ）とする。
【０１２０】
次に、切除不等式抽出部１４は、インデックスｊに初期値１を設定し（ステップＳ１０２）、インデックスｊの値がｎ以下であるか否かを判定する（ステップＳ１０３）。
【０１２１】
インデックスｊの値がｎ以下である場合（ステップＳ１０３肯定）、切除不等式抽出部１４は、ａｊの値が０であるか否かを判定する（ステップＳ１０４）。ここで、ａｊは、行ベクトルａのｊ列目の要素である。
【０１２２】
ａｊの値が０でない場合（ステップＳ１０４否定）、切除不等式抽出部１４は、インデックスｊの値をＳｕｐｐ（ａ）の要素に追加してから（ステップＳ１０５）、インデックスｊの値を１つ増加する（ステップＳ１０６）。一方、ａｊの値が０である場合（ステップＳ１０４肯定）、切除不等式抽出部１４は、インデックスｊの値をＳｕｐｐ（ａ）の要素に追加することなく、そのままインデックスｊの値を１つ増加する（ステップＳ１０６）。
【０１２３】
切除不等式抽出部１４は、インデックスｊの値を１つ増加した後（ステップＳ１０６）、再び、ステップＳ１０３に戻り、インデックスｊの値がｎ以下であるか否かを判定する。すなわち、切除不等式抽出部１４は、インデックスｊの値がｎを上回るまで、ステップＳ１０３〜ステップＳ１０６の処理を繰り返す。
【０１２４】
さて、ステップＳ１０３においてインデックスｊの値がｎを上回ると（ステップＳ１０３否定）、切除不等式抽出部１４は、続いて、ベクトルｚの成分ｚｊが１／２を超えるか否かに応じて、互いに素な部分集合Ｓ０及びＳ１に分類する。
【０１２５】
具体的には、図４−２に示すように、切除不等式抽出部１４は、インデックスｊに初期値１を設定し、インデックスｊ´（ダッシュ）に初期値１を設定し（ステップＳ１０７）、インデックスｊの値がｎ以下であるか否かを判定する（ステップＳ１０８）。
【０１２６】
インデックスｊの値がｎ以下である場合（ステップＳ１０８肯定）、切除不等式抽出部１４は、インデックスｊがＳｕｐｐ（ａ）の要素であるか否かを判定する（ステップＳ１０９）。
【０１２７】
インデックスｊがＳｕｐｐ（ａ）の要素である場合（ステップＳ１０９肯定）、切除不等式抽出部１４は、ｚｊの値が０．５以下であるか否かを判定し(ステップＳ１１０)、ｚｊの値が０以上０．５以下である場合には（ステップＳ１１０肯定）、インデックスｊを部分集合Ｓ０の要素とする（ステップＳ１１１）。一方、ｚｊの値が０以上０．５以下でない場合には（ステップＳ１１０否定）、切除不等式抽出部１４は、インデックスｊを部分集合Ｓ１の要素とする（ステップＳ１１２）。
【０１２８】
続いて、切除不等式抽出部１４は、ｚｊがｚｊ´（ダッシュ）よりも０．５に近いか否かを判定する（ステップＳ１１３）。近い場合には（ステップＳ１１３肯定）、切除不等式抽出部１４は、ｊ´の値をインデックスｊの値に置き換えた後（ステップＳ１１４）、インデックスｊの値を１つ増加する（ステップＳ１１５）。一方、近くない場合には（ステップＳ１１３否定）、切除不等式抽出部１４は、ｊ´の値をインデックスｊの値に置き換えることなく、インデックスｊの値を１つ増加する（ステップＳ１１５）。
【０１２９】
切除不等式抽出部１４は、インデックスｊの値を１つ増加した後（ステップＳ１１５）、再び、ステップＳ１０８に戻り、インデックスｊの値がｎ以下であるか否かを判定する。すなわち、切除不等式抽出部１４は、インデックスｊの値がｎを上回るまで、ステップＳ１０８〜ステップＳ１１５の処理を繰り返す。
【０１３０】
さて、ステップＳ１０８においてインデックスｊの値がｎを上回ると（ステップＳ１０８否定）、切除不等式抽出部１４は、続いて、ベクトルｚの成分ｚｊが１／２に最も近い一つのインデックスｊを部分集合Ｓ０、Ｓ１の一方から他方へ移動させることによって、ベクトルｃの成分ｃの値と、｜Ｓ１｜の偶数奇数との関係を調整する。
【０１３１】
具体的には、図４−３に示すように、切除不等式抽出部１４は、条件Ａを満たすか否かを判定する（ステップＳ１１６）。
【０１３２】
ここで、条件Ａとは、（イ）ｃの値が０であり、かつＳ１に含まれる要素の数が偶数である、という条件であり、（ロ）ｃの値が１であり、かつＳ１に含まれる要素の数が奇数である、という条件である。また、ｃは、行ベクトルａが行列Ａのｉ番目の行の場合は、ｃｉを使用する。また、行ベクトルａが冗長行の場合は、記憶部にある対応するｃを使用する。また、行ベクトルａが行列Ａに第二アルゴリズムを適用した新たな行列Ａ´（ダッシュ）のｉ番目の行ならば、対応するｃ´ｉを使用する。なお、図２では、対応するｃの値を含めて冗長行と呼んでいる。すなわち、切除不等式抽出部１４は、（イ）、（ロ）のいずれかの条件を満たすか否かを判定する。
【０１３３】
条件Ａを満たすと判定した場合には（ステップＳ１１６肯定）、切除不等式抽出部１４は、ｊ´（ダッシュ）が部分集合Ｓ０に含まれる場合にはｊ´を部分集合Ｓ１に移動し、ｊ´が部分集合Ｓ１に含まれる場合にはｊ´を部分集合Ｓ０に移動する（ステップＳ１１７）。一方、条件Ａを満たさないと判定した場合には（ステップＳ１１６否定）、切除不等式抽出部１４は、ステップＳ１１７の処理を行わない。
【０１３４】
次に、切除不等式抽出部１４は、数式（１−５７）を満たすか否かを判定する（ステップＳ１１８）。すなわち、切除不等式抽出部１４は、数式（１−５７）の不等式が真であるか否かを判定する。
【０１３５】
そして、真でないと判定した場合には（ステップＳ１１８否定）、切除不等式抽出部１４は、暫定解を切除する切除不等式が存在し、真でないと判定した当該不等式が切除不等式であるとして、第一アルゴリズムの処理を終了する（ステップＳ１１９）。一方、真であると判定した場合には（ステップＳ１１８否定）、切除不等式抽出部１４は、この行は、暫定解を切除する切除不等式を持たないとして、第一アルゴリズムを終了する（ステップＳ１２０）。
【０１３６】
［アルゴリズムＢ´］
続いて、第二の課題を解決するための方法として、ＧＦ（２）上の方程式Ａｚ＝ｃを方程式Ａハットｚハット＝０に変形する方法について説明する。
【０１３７】
ＧＦ（２）上の方程式Ａｚ＝ｃが、数式（１−５８）のように表されるとき、
【数１−５８】
2010278782.tif 000060
これと同値な２つの方程式である数式（１−５９）、数式（１−６０）のように書き改めることができる。これを、Ａハットｚハット＝０、ｚｎ＋１＝１とする。ここで（−）（丸の中にマイナス）はＧＦ（２）の減法を表す。
【数１−５９】
2010278782.tif 000061
【数１−６０】
2010278782.tif 000062
【０１３８】
したがって、変数ベクトルをｚの次元から一つ増やしたｚハットとして、制約条件を数式（１−６１）として線形計画問題を適用することができる。ここで、目的関数ｆ（ｚ）には、変数ｚｎ＋１は登場しない。
【数１−６１】
2010278782.tif 000063
【０１３９】
ところで、このような変形を加えた上でアルゴリズムＢを適用することは、アルゴリズムＢのステップ（２）を以下のものに置き換えることと等価である。
【０１４０】
（２´）ｃｉ＝１ならｖ＝０としてＳ（０）を空集合、ｃｉ＝０ならｖ＝１としてＳ（１）をｚｊが最大となるｊだけからなる集合とする。最大となるｊは、ステップ（１）で求めた並び替えを利用する。このような置き換えを行ったものをアルゴリズムＢ´とする。
【０１４１】
［第二アルゴリズム］
さて、第二アルゴリズムでは、行列Ａに基本変形を施して、ベクトルｚの成分で｜ｚｊ−１／２｜の値の小さいインデックスｊに対応する行列の行の成分を、できる限り０にできるようにする。
【０１４２】
この第二アルゴリズムを図５−１〜図５−３を用いて説明する。行列Ａが、数式（１−６２）で与えられ、ベクトルｃが、数式（１−６３）で与えられている時、切除不等式抽出部１４は、行列Ａ´（ダッシュ）を数式（１−６４）とする。
【数１−６２】
2010278782.tif 000064
【数１−６３】
2010278782.tif 000065
【数１−６４】
2010278782.tif 000066
【０１４３】
すなわち、切除不等式抽出部１４は、図５−１に示すように、行列Ａ´を作成する（ステップＳ２０１）。
【０１４４】
次に、切除不等式抽出部１４は、ベクトルｚのインデックスｊを｜ｚｊ−１／２｜の値が小さい順に並べ替えたインデックスｊの配列を求める（ステップＳ２０２）。なお、複数のインデックスｊの値が同じ順位ならば、例えばインデックスｊが小さい順に並べるといった順序付けを行う。
【０１４５】
続いて、切除不等式抽出部１４は、ｋに初期値１を設定し（ステップＳ２０３）、ｉに初期値１を設定し（ステップＳ２０４）、ｉの値がｌ以下であるか否かを判定する（ステップＳ２０５）。
【０１４６】
ｉの値がｌ以下である場合には（ステップＳ２０５肯定）、切除不等式抽出部１４は、行列Ａの要素ａｉ，ｊｋ（ｋはｊの添え字）が０であるか否かを判定する（ステップＳ２０６）。０である場合には（ステップＳ２０６肯定）、切除不等式抽出部１４は、ｉの値を１つ増加して（ステップＳ２０７）、ステップＳ２０５の処理に戻る。
【０１４７】
行列Ａの要素ａｉ，ｊｋが全て０である場合には、ステップＳ２０６において常に肯定に判定され、その後、ステップＳ２０５においてｉの値がｌの値を上回る（ステップＳ２０５否定）。
【０１４８】
すると、切除不等式抽出部１４は、ｋの値がｌ以下であるか否かを判定し（ステップＳ２０８）、ｌ以下である場合には（ステップＳ２０８肯定）、ｋの値を１つ増加して（ステップＳ２１０）、再び、ステップＳ２０４の処理に戻る。
【０１４９】
一方、ｋの値がｌの値を上回る場合には（ステップＳ２０８否定）、切除不等式抽出部１４は、行列Ａ´のｎ＋１列目をベクトルｃ´（ダッシュ）として分離して、第二アルゴリズムを終了する（ステップＳ２０９）。
【０１５０】
さて、ステップＳ２０６において、行列Ａの要素ａｉ，ｊｋが０でない場合には（ステップＳ２０６否定）、切除不等式抽出部１４は、行列Ａ´に対して行基本変形を施してｉ´行目の要素ａｉ，ｊｋの値を全て０にする。
【０１５１】
すなわち、図５−３に示すように、切除不等式抽出部１４は、ｉ´に初期値１を設定し（ステップＳ２１１）、ｉ´の値がｌ以下であるか否かを判定する（ステップＳ２１２）。
【０１５２】
ｉ´の値がｌ以下である場合（ステップＳ２１２肯定）、切除不等式抽出部１４は、ｉ´がｉでないことを判定し（ステップＳ２１３）、ｉ´がｉでない場合には（ステップＳ２１３肯定）、行列Ａの要素ａｉ，ｊｋが０でないか否かを判定する（ステップＳ２１４）。
【０１５３】
行列Ａの要素ａｉ，ｊｋが０でない場合には（ステップＳ２１４肯定）、切除不等式抽出部１４は、ベクトル（ａｉ´，１、ａｉ´，２、・・・、ａｉ´，ｎ、ｃｉ´）に、ベクトル（ａｉ，１、ａｉ，２、・・・、ａｉ，ｎ、ｃｉ）をａｉ´，ｊｋ／ａｉ´，ｊｋ倍（ｋはｊの添え字）して引いたものを新たにベクトル（ａｉ´，１、ａｉ´，２、・・・、ａｉ´，ｎ、ｃｉ´）と定める（ステップＳ２１５）。この結果、行列Ａの要素ａｉ，ｊｋは０となる。
【０１５４】
そして、切除不等式抽出部１４は、ｉ´の値を１つ増加し（ステップＳ２１６）、図５−３に示すステップＳ２１２の処理に戻る。なお、ステップＳ２１２において、ｉ´の値がｌを上回ると（ステップＳ２１２否定）、図５−３及び図５−２に示すように、切除不等式抽出部１４は、ステップＳ２０８の処理に戻る。
【０１５５】
なお、目的関数の値が整数値になることが事前に分っており、最適化問題が最小化問題である場合は、暫定的な最適解z´が求まった後に、数式（１−６５）がｚ´を切除する。したがって、実施例１において、Ｉｎｅｑ（ｋ＋１）を求めるときに、この制約式を加えることができる。ここで、右辺は、ｆ（ｚ´）の小数部分を切り上げた整数である。
【数１−６５】
2010278782.tif 000067
【０１５６】
同様に、最適化問題が最大化問題であり、目的関数の値が整数値になることが事前に分かっている場合は、暫定的な最適解にｚ´が求まった後で、数式（１−６６）を制約式に加えることができる。ここで、右辺は、ｆ（ｚ´）の小数部分を切り捨てた整数である。
【数１−６６】
2010278782.tif 000068
【０１５７】
［実施例１の効果］
上記してきたように、実施例１に係る推定装置は、０と１との２元の有限体上において線形方程式を制約条件として目的関数を最適化する推定装置である。また、推定装置は、０以上かつ１以下であることを示す制約不等式の集合を初期の制約条件として、また、暫定的な最適解ｚｊを切除する切除不等式が抽出された場合には当該切除不等式を追加した制約不等式の集合を新たな制約条件として、暫定解ｚｊを算出する。また、推定装置は、線形方程式の係数である行列の各行ごとに、行列の要素が０でない列を示すインデックスｊの集合を作成し、当該インデックスｊの集合を、当該インデックスｊに対応する暫定解ｚｊと１との距離が０との距離を上回る場合には第一集合Ｓ０に、暫定解ｚｊと１との距離が０との距離を下回る場合には第二集合Ｓ１にそれぞれ分類する。また、推定装置は、線形方程式の切片が０である場合には第二集合Ｓ１に分類されたインデックスｊの数が奇数となるように、また、線形方程式の切片が１である場合には第二集合Ｓ１に分類されたインデックスｊの数が偶数となるように、分類された第一集合Ｓ０及び第二集合Ｓ１を調整する。そして、推定装置は、調整された結果、第二集合Ｓ１に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて１との距離を加算した加算値と、第一集合Ｓ０に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて０との距離を加算した加算値との総和が、１以上となるか否かを判定する。推定装置は、判定された結果、１以上とならないと判定した場合に、判定に用いた不等式を切除不等式として抽出する。そして、推定装置は、抽出された切除不等式を制約不等式の集合に追加する。
【０１５８】
また、実施例１に係る推定装置は、切除不等式が抽出されない場合に、行列を、０と１との間の中央値である１／２と暫定解ｚｊとの距離が小さいインデックスｊに対応する行列の行の成分を０にするように変形する。また、推定装置は、変形後の行列の各行ごとに、インデックスｊの集合を第一集合Ｓ０及び第二集合Ｓ１にそれぞれ分類する。
【０１５９】
このようなことから、実施例１に係る推定装置によれば、計算時間を短縮することが可能になる。すなわち、実施例１に係る推定装置は、暫定解ｚｊを切除する不等式が存在するかどうかを一度の不等式判定（数式（１−５７）による判定）だけで行うことができる。また、同時に、暫定解ｚｊを切除する不等式が存在する時には、その不等式を与えることができる。
【０１６０】
この時、実施例１に係る推定装置は、アルゴリズムＢのようにｚｊの成分の値の大きい順にインデックスｊをソートする必要はなく、ｚｊが１／２より大きいか小さいか、また１／２に最も近いかどうかだけを最初に求めておけばよい。これらは、Ｏ（ｎ）の計算時間で実行することができる。不等式の判定もＯ（ｎ）の計算時間で行うことができるので、結局、最終的な計算時間はＯ（ｎ）であり、第一アルゴリズムはアルゴリズムＢよりも計算時間に優れている。また、第一アルゴリズムでは、方程式ａ・ｚ＝ｃからｚを切除する不等式が構成できるにもかかわらず、構成できないと判定して停止してしまうことはない。すなわち、方程式ａ・ｚ＝ｃからｚを切除する不等式がみつけられるときは必ず、第一アルゴリズムはその不等式の一つを出力して終了する。
【０１６１】
ここで、ｚｊが１／２より大きいか小さいかを求める点についてさらに説明すると、実施例１に係る推定装置は、数式（１−５７）による判定を行うことで、暫定解ｚｊを切除する不等式が存在するかどうかを一度の不等式判定で行うことができるわけであるが、この場合、左辺をできる限り小さい値とすることに意味がある。すなわち、左辺の値をできるだけ小さい値としておけば、それ以上小さいものはないということで、一度の不等式判定で済むのである。
【０１６２】
そこで推定装置は、左辺をできるだけ小さい値とするために、ｚｊが１／２より大きいか小さいかを求めるのである。左辺をみるとわかるように、左辺第一項は、第二集合Ｓ１に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて１との距離を加算した加算値である。また、第二項は、第一集合Ｓ０に属することとなったインデックスｊに対応する暫定解ｚｊ全てについて０との距離を加算した加算値である。言い換えると、第二集合Ｓ１に、予め１に近い値をもつインデックスｊを分類しておき、第一集合Ｓ０に、予め０に近い値を持つインデックスｊを分類しておけば、左辺全体として最も小さい値となることがわかる。実施例１に係る推定装置は、この点を利用するものである。
【０１６３】
また、実施例１に係る推定装置によれば、ＧＦ（２）上の方程式Ａｚ＝ｃを同値な方程式Ａハットｚハット＝０に変形することで、より一般的な方程式Ａｚ＝ｃを制約式として設定することができるようになり、より多くの最適化問題を扱えるようになる。また、計算時間が大幅に削減できると同時に、符号の性能も大幅に向上させることができる。また、効率良く切除平面を求め、符号化効率を向上させることができる。
【実施例２】
【０１６４】
実施例２に係る推定装置は、実施例１に係る推定装置による手法に加え、暫定的な最適解を切除できる冗長行を加える手法を用いる。以下、まず、図６を用いて実施例２に係る推定装置１０の構成を説明し、次に、図７を用いて実施例１に係る推定装置１０における処理手順を説明する。
【０１６５】
［実施例２に係る推定装置１０の構成］
図６は、実施例２に係る推定装置１０の構成を示すブロック図である。実施例２に係る推定装置１０は、図６に示すように、切除不等式抽出部と記憶部との間で、切除冗長行の送受信が行われる点で実施例１と異なる。すなわち、実施例１では、推定装置１０は、記憶部に切除冗長行を記憶する必要がなかったが、実施例２では、これを記憶するものである。
【０１６６】
［実施例２に係る推定装置１０による処理手順］
次に、実施例２に係る推定装置１０における処理手順を説明する。図７に示すように、実施例２に係る推定装置１０は、ステップＳ６において、必要に応じて切除冗長行も記録し、ステップＳ４において、行列Ａの冗長行に対しても第一アルゴリズムを適用する点が、実施例１に係る推定装置１０と異なる。図７は、実施例２に係る推定装置１０における処理手順を示すフローチャートである。
【０１６７】
具体的には、実施例２に係る推定装置１０では、以下のような処理手順となる。
【０１６８】
（１）ｋ１＝０、ｋ２＝０とする。初期の不等式の集合（数式（１−３９））のみを制約式として、線形計画法により暫定的な最適解を求める。初期の行列をＡ０とする。
【０１６９】
（２）Ｉｎｅｑ（ｋ１）にある不等式の中で、暫定的な最適解が等式として満たしている不等式を残して、他の不等式を削除したものを、Ｉｎｅｑ（ｋ１＋１）とする。そして、ｋ１の値を１増やす。なお、ステップ（２）の処理は、図７のステップＳ３とステップＳ４との間で実行される。
【０１７０】
（３）行列Ａｋ２の全ての行に対して第一アルゴリズムを適用して、暫定的な最適解を切除する不等式を一つ以上Ｉｎｅｑ（Ａｋ２ｚ＝ｃ）から探す。
【０１７１】
（４）ステップ（３）で暫定的な最適解を切除する不等式がみつかれば、その不等式をＩｎｅｑ（ｋ１）に追加したものをＩｎｅｑ（ｋ１＋１）とする。Ｉｎｅｑ（ｋ１＋１）を制約式とした線形計画法により最適解を求め、これを新たな暫定的な最適解とする。そして、ｋ１の値を１増やしてステップ（２）に戻る。
【０１７２】
（５）もしも不等式を発見できず、かつ暫定的な最適解の成分が全て整数だった場合はこれを最適解として終了する。
【０１７３】
（６）もしも不等式を発見できず、かつ暫定的な最適解に非整数の成分を含んでいる場合は、初期の行列Ａ０に第二アルゴリズムを適用して、暫定的な最適解を切除する冗長行を求める。もしも見付かれば、その冗長行を行列Ａｋ２に追加した新たな行列をＡｋ２＋１とする。そしてｋ２の値を１増やしてステップ（２）へ戻る。見付からなければ、非整数成分を含む暫定的な最適解を最適解として終了する。
【０１７４】
ここで、ステップ（２）は、線形計画法を適用する制約不等式の数を抑える効果がある。これによって線形計画法が必要とするメモリの大きさを削減できる効果がある一方で、符号の実行時間が増える可能性もあるので、ステップ（２）では何も実行せずに次のステップに移っても構わない。
【実施例３】
【０１７５】
さて、これまで実施例１及び実施例２として、２元の有限体ＧＦ（２）上において線形方程式Ａｚ＝ｃを制約条件として関数ｆ（ｚ）を最適化する推定装置を説明してきた。また、実施例１において、本発明を適用可能な最適化問題として、加法的雑音を伴う通信路符号を説明した。続いて、実施例３以降では、符号器及び復号器に本発明を適用した実施例を説明する。
【０１７６】
ここで、図８に示すように、本発明は、様々な最適化問題に適用することが可能である。図８は、符号化、復号化に現れる最適化問題を示す図である。制約式Ａｚ＝ｃ、Ｂｚ＝ｍは、ＡとＢを縦に連結した一つの行列を考えれば、一つの制約式で表現できる。探索問題では、探索の成功を１、失敗を０とした目的関数の最大化を考える。以下では、まず、実施例３として、固定長無歪み符号における符号器及び復号器に本発明を適用した実施例を説明する。
【０１７７】
以下、行列やベクトルの要素は、｛０，１｝に属しているものとする。また、|  ・  |は、集合の個数を表すものとし、Ｈ（ｚ）、Ｈ（ｚ｜ｙ）を、数式（２−１）及び数式（２−２）のように定義する。
【数２−１】
2010278782.tif 000069
【数２−２】
2010278782.tif 000070
【０１７８】
固定長無歪み符号における符号器及び復号器は、図９で与えられる。図９は、固定長無歪み符号における符号器及び復号器を説明するための図である。
【０１７９】
符号器及び復号器は、予め適切なｌ×ｎ行列Ａを共有しておく。符号器は、ベクトルｚで表現されたｎ次元の情報に行列Ａを作用させて、l次元のベクトルｃ＝Ａｚを求め、これを送信もしくはメモリ等に蓄える。一方、復号器は、受信もしくはメモリ等の情報から読みとったベクトルｃから、確率分布μＺが既知の時には、数式（２−３）で定義される最適化問題を解くことによって、元の情報ｚの復元を試みる。
【数２−３】
2010278782.tif 000071
ここで、ｇＡの右辺の実現に、本発明を適用することができる。
【０１８０】
確率分布μＺが未知の時には、数式（２−４）、数式（２−５）、数式（２−６）で定義される最適化問題を解くことによって、元の情報ｚの復元を試みる。
【数２−４】
2010278782.tif 000072
【数２−５】
2010278782.tif 000073
【数２−６】
2010278782.tif 000074
ここで、数式（２−４）、数式（２−５）で定義される目的関数は、実数の和を考える。この場合も、数式（２−４）、数式（２−５）で定義される目的関数に、本発明を適用することができる。
【実施例４】
【０１８１】
次に、実施例４は、加法的雑音を伴う通信路の符号に本発明を適用した実施例である。なお、加法的雑音を伴う通信路に対する誤り訂正符号は、上記したように、図３で与えられる。
【０１８２】
符号器及び復号器は、予め適切なｌ×ｎ行列Ａを共有しておく。符号器は、実施例１ですでに説明したように、生成行列と呼ばれる行列Ｇを用いて、メッセージのベクトルｍから数式（１−１３）によってベクトルｘを求め、これを通信路入力とする。ここで、通信路入力の集合は、数式（１−１０）で表される。復号器は、通信路出力となるベクトルｙからベクトルｃ＝Ａｙを求める。
【０１８３】
このとき、通信路の雑音ｚに対して、関係式Ａｚ＝ｃが成り立つことから、実施例３と同様にして、雑音の確率分布μｚが既知の時には、数式（２−３）で定義される最適化問題を解くことによって、雑音ｚの復元を試みる。ここで、ｇＡの右辺の実現に、本発明を適用することができる。
【０１８４】
雑音の確率分布μｚが未知の時にも、実施例３と同様にして、数式（２−４）、数式（２−５）、数式（２−６）で定義される最適化問題を解くことによって、雑音ｚの復元を試みる。
【０１８５】
復号器は、最後に、復元した雑音ｚから数式（３−１）（丸の中にマイナスの記号はＧＦ（２）ｎの減法）によって通信路入力ｘを推定し、これと数式（１−１３）の関係式から元のメッセージｍを推定する。
【数３−１】
2010278782.tif 000075
【実施例５】
【０１８６】
次に、実施例５は、補助情報を利用できる固定長無歪み符号における符号器及び復号器に本発明を適用した実施例である。
【０１８７】
補助情報を利用できる固定長無歪み符号における符号器及び復号器は、図１０で与えられる。図１０は、補助情報を利用できる固定長無歪み符号における符号器及び復号器を説明するための図である。
【０１８８】
符号器及び復号器は、予め適切なｌ×ｎ行列Ａを共有しておく。符号器は、ベクトルｚで表現されたｎ次元の情報に行列Ａを作用させて、ｌ次元のベクトルｃ＝Ａｚを求め、これを送信もしくはメモリ等に蓄える。復号器は、受信もしくはメモリ等の情報から読みとったベクトルｃ以外にも、ｚと相関のある補助情報ｙを受信できるものとする。通信路の遷移確率分布μＺ｜Ｙが既知であるときは、数式（４−１）で定義される最適化問題を解くことによって、通信路入力ｚの復元を試みる。
【数４−１】
2010278782.tif 000076
【０１８９】
通信路の遷移確率分布μＺ｜Ｙが未知であるときは、数式（４−２）、数式（４−３）、数式（４−４）で定義される最適化問題を定める。
【数４−２】
2010278782.tif 000077
【数４−３】
2010278782.tif 000078
【数４−４】
2010278782.tif 000079
ここで、数式（４−２）及び数式（４−３）の制約条件に現れるｚｉのΣ（ｉ＝１〜ｎ）、目的関数に現れるｙｉｚｉのΣ（ｉ＝１〜ｎ）は、実数の和を表している。数式（４−２）及び数式（４−３）で定義される最適化問題に対して本発明を適用することができる。
【実施例６】
【０１９０】
次に、実施例６は、一般の通信路符号における符号器及び復号器に本発明を適用した実施例である。
【０１９１】
一般の通信路符号における符号器及び復号器は、図１１及び図１２で与えられる。図１１及び図１２は、一般の通信路符号における符号器及び復号器を説明するための図である。
【０１９２】
符号器及び復号器は、予め適切なｌＡ×ｎ行列Ａ、ｌＢ×ｎ行列Ｂ、ｌＡ次元のベクトルｃ、ｗ∈{０，１，・・・，ｎ}を共有しておく。符号器は、ベクトルｍで表現されたｌＢ次元の情報とベクトルｃから、数式（５−１）で示される最適化問題を解くことにより、Ａｚ＝ｃ、Ｂｚ＝ｍを満たすｎ次元の通信路入力ｚを求める。
【数５−１】
2010278782.tif 000080
【０１９３】
ここで、行列Ａ、Ｂに対して、これを縦に連結した［ｌＡ＋ｌＢ］×ｎ行列をＡ´（ダッシュ）、列ベクトルｃ、ｍを縦に連結したｌＡ＋ｌＢ次元ベクトルをｃ´（ダッシュ）とすれば、制約条件Ａｚ＝ｃ、Ｂｚ＝ｍは、一つの制約条件Ａ´ｚ＝ｃ´に書き改めることができる。そして、この最適化問題は、２次計画問題となる。このｇＡＢの実現に、本発明を適用することができる。
【０１９４】
復号器は、受信したｎ次元のベクトルｙから復号を試みる。ここで、復号器は、通信路の遷移確率分布μＺ｜Ｙが既知の場合は、数式（４−１）、未知の場合は、数式（４−２）、数式（４−３）、数式（４−４）で定義される数式を用いて、通信路入力ｚを推定する。そして、復号器は、推定したｚからＢｚを求めることにより、もとのメッセージを推定する。
【実施例７】
【０１９５】
次に、実施例７は、有歪み符号における符号器及び復号器に本発明を適用した実施例である。
【０１９６】
有歪み符号における符号器及び復号器は、図１３及び図１４で与えられる。図１３及び図１４は、有歪み符号における符号器及び復号器を説明するための図である。
【０１９７】
符号器及び復号器は、予め適切なｌＡ×ｎ行列Ａ、ｌＢ×ｎ行列Ｂ、ｌＡ次元のベクトルｃと適切な実数γを共有しておく。ここで、γの正負は情報源の分布μＹから定められる。また、文字ｙ、ｚ間の歪み尺度をｄ（ｙ，ｚ）とする。
【０１９８】
符号器は、ｎ次元の情報ｙから、数式（６−１）で定義される最適化問題を解くことにより、Ａｚ＝ｃを満たすｎ次元のベクトルｚを求め、ｌＢ次元ベクトルｍ≡Ｂｚを符号語と、送信やメモリ等への蓄積を行う。
【数６−１】
2010278782.tif 000081
【０１９９】
なお、数式（６−１）は、数式（６−２）と置き換えても良い。これは、後の復号を容易にする効果がある。
【数６−２】
2010278782.tif 000082
【０２００】
そして、数式（６−１）及び数式（６−２）のｇＡの右辺の実現に本発明を適用することができる。
【０２０１】
復号器は、受信もしくはメモリ等から取り出したベクトルｍから、数式（６−３）で定義される最適化問題を解くことにより、ベクトルｚを復元する。
【数６−３】
2010278782.tif 000083
ここで、行列Ａ、Ｂに対して、これを縦に連結した［ｌＡ＋ｌＢ］×ｎ行列をＡ´（ダッシュ）、列ベクトルｃ、ｍを縦に連結したｌＡ＋ｌＢ次元ベクトルをｃ´（ダッシュ）とすれば、制約条件Ａｚ＝ｃ、Ｂｚ＝ｍは、一つの制約条件Ａ´ｚ＝ｃ´に書き改めることができる。そして、このｇＡの右辺の実現に本発明を適用することができる。
【実施例８】
【０２０２】
次に、実施例８では、従来のアルゴリズムと本発明のアルゴリズムとの比較を与える。まず、ｌ×ｎ行列Ａを用意する。ｎ次元のベクトルｚを独立にランダムに与える。このとき、各次元の要素が１となる確率をＰ（Ｚ＝１）とする。符号器では、情報ベクトルｚに対して、ｌ次元の符号語ベクトルｃ≡Ａｚを計算する。
【０２０３】
復号器では、数式（７−１）でｎ次元のベクトルｇＡ（ｃ）を計算する。
【数７−１】
2010278782.tif 000084
【０２０４】
ここで、ベクトルｚ＝（ｚ１，ｚ２，・・・，ｚｎ）である。これを線形計画法を用いて求める場合は、制約条件は数式（７−２）となり、目的関数ｆ（ｚ）は、数式（７−３）となる。
【数７−２】
2010278782.tif 000085
【数７−３】
2010278782.tif 000086
【０２０５】
ｇＡ（ｃ）に線形計画法を適用して求めたベクトルを、ｚ（ｃ）（ｚにハット）とする。ただし、線形計画法を用いて求めたベクトルが非整数成分を持つときは、その成分を四捨五入して０または１に丸めるものとする。ｚ（ｃ）（ｚにハット）がｚと一致しないときに、復号誤りとなる。
【０２０６】
ところで、この問題では、暫定的な最適解ｚ´（ダッシュ）が求まった後は、数式（７−４）という不等式がｚ´を切除するので、線形計画法を実行するときにこの制約式を加える。
【数７−４】
2010278782.tif 000087
【０２０７】
この実験をｋ個の独立に発生させたベクトルｚに対して行うとき、復号誤り確率を数式（７−５）によって推定することが出来る。
【数７−５】
2010278782.tif 000088
【０２０８】
ここで、ｚｉは、ｉ回目の実験で発生させた情報ベクトルで、ｃｉは、ｉ回目の実験で発生させた符号語ベクトルであり、数式（７−６）のように定義する。
【数７−６】
2010278782.tif 000089
【０２０９】
図１５は、シミュレーション結果を示す図である。グラフの横軸はＰ（Ｚ＝１）を表し、縦軸はErrorを表す。また、ｋ＝１０００として実験を行った。各グラフは、下記の実験結果と対応する。なお、以下では、第一アルゴリズムを「アルゴリズムＥ」と称し、第二アルゴリズムを「アルゴリズムＦ」と称する。
【０２１０】
アルゴリズムＤでは、事前に追加する冗長行の数の上限を１００としたが、実際は使用メモリの問題で４行しか追加されなかった。
【０２１１】
Ａ＋Ｂ´＋Ｃ（１）は、アルゴリズムＡを実行し、更に切除不等式を求める時にアルゴリズムＣを実行するアルゴリズムである。また、下記のＡ＋Ｅ＋Ｆ（１）では、一つの切除不等式を求めるときに基本変形で８０行の冗長行の候補を用意するため、冗長行の候補を求める回数を８０×１０００回とした。
【０２１２】
Ａ＋Ｂ´＋Ｃ（２）は、アルゴリズムＡを実行し、更に切除する冗長行を求める時に、アルゴリズムＣを実行するアルゴリズムである。また、下記のＡ＋Ｅ＋Ｆ（２）では、一つの切除する冗長行を求めるときに基本変形で８０行の冗長行の候補を用意するため、冗長行の候補を求める回数を８０×１００回とした。
【０２１３】
Ａ＋Ｅ＋Ｆ（１）は、実施例１で説明した形態である。ただし、行列Ａに含まれる行から作られた切除不等式を全て加えた。また、不等式を追加する回数を１０００回とした。Ａ＋Ｅ＋Ｆ（２）は、実施例２で説明した形態である。ただし、Ａｋ２に含まれる行から作られた切除不等式を全て加えた。また、冗長行を追加する回数を１００回とした。
【０２１４】
ただし、Ａ＋Ｂ´＋Ｃ（１）、および、Ａ＋Ｂ´＋Ｃ（１）において、アルゴリズムＡのステップ２とアルゴリズムＣのステップ７では、アルゴリズムＢの代わりにアルゴリズムＢ´を用いた。ここで、アルゴリズムＢ´を用いたのは、アルゴリズムＢでは、制約式にＡｚ＝０を仮定するためにこれを利用できないからである。また、Ａ＋Ｂ´＋Ｃ（１）、Ａ＋Ｂ´＋Ｃ（２）、Ａ＋Ｅ＋Ｆ（１）、Ａ＋Ｅ＋Ｆ（２）で、Ｐ（Ｚ＝１）＝０．０６の結果が記載されていないのは、復号誤りが０となったためである。
【０２１５】
図１５のシミュレーション結果は、実施例１、実施例２の復号性能が、従来のアルゴリズムに比べて改善されていることを示している。
【０２１６】
なお、本発明は、非特許文献１に記載されているSlepian-Wolf問題、Wyner-Ziv問題、Gel’fand-Pinsker問題、One-helps-one問題にも同様に適用することができる。
【符号の説明】
【０２１７】
１０  推定装置
１１  記憶部
１２  入力部
１３  暫定解算出部
１４  切除不等式抽出部
１５  出力部
【図１】
2010278782.tif 000090
【図２】
2010278782.tif 000091
【図３】
2010278782.tif 000092
【図４−１】
2010278782.tif 000093
【図４−２】
2010278782.tif 000094
【図４−３】
2010278782.tif 000095
【図５−１】
2010278782.tif 000096
【図５−２】
2010278782.tif 000097
【図５−３】
2010278782.tif 000098
【図６】
2010278782.tif 000099
【図７】
2010278782.tif 000100
【図８】
2010278782.tif 000101
【図９】
2010278782.tif 000102
【図１０】
2010278782.tif 000103
【図１１】
2010278782.tif 000104
【図１２】
2010278782.tif 000105
【図１３】
2010278782.tif 000106
【図１４】
2010278782.tif 000107
【図１５】
2010278782.tif 000108