(57)【要約】【課題】ハミング符号のＡＬＰによる復号を実現し、結果として、復号方法の実装負荷を低減し、かつ計算時間を短縮できるＡＬＰ復号方法を提供することを目的とする。【解決手段】  ＡＬＰ復号方法は、所定の検査行列で定義されるハミング符号のファクターグラフを生成するファクターグラフ生成ステップと、変数ノードの拘束条件を、変数ノードが満たすべき条件式に基づいて導出する拘束条件導出ステップと、生成したファクターグラフから複数のチェックノードに接続している変数ノードのうち、１つのチェックノードに接続している孤立変数ノードを検出する孤立変数ノード検出ステップと、孤立変数ノードを整数の値とする制限を加える制限付加ステップと、拘束条件と制限が加えられた孤立変数ノードに関する情報とに基づいて、ＭＩＬＰにより解を算出してハミング符号の復号結果とする復号結果算出ステップとを備える。【選択図】  図１７
2019208097.tif 000002
【特許請求の範囲】
【請求項１】
演算装置と、記憶装置と、通信制御装置とを備える復号装置によって実行される適応的線形計画復号方法であって、
前記通信制御装置を介して受信される所定の検査行列で定義されるハミング符号のファクターグラフを生成して前記記憶装置に記憶するファクターグラフ生成ステップと、
前記演算装置が、前記検査行列の複数列にそれぞれ対応する変数ノードの拘束条件を、前記記憶装置に記憶されている変数ノードが満たすべき条件式に基づいて導出する拘束条件導出ステップと、
前記演算装置が、前記記憶装置に記憶されている前記ファクターグラフから前記検査行列の複数行にそれぞれ対応する複数のチェックノードに接続している前記変数ノードのうち、１つのチェックノードに接続している孤立変数ノードを検出する孤立変数ノード検出ステップと、
前記演算装置が、前記孤立変数ノードを整数の値とする制限を加える制限付加ステップと、
前記演算装置が、前記拘束条件と前記制限が加えられた前記孤立変数ノードに関する情報とに基づいて、混合整数線形計画法により解を算出して算出結果を前記ハミング符号の復号結果として前記記憶装置に記憶する復号結果算出ステップと
を備えることを特徴とする適応的線形計画復号方法。
【請求項２】
請求項１に記載の適応的線形計画復号方法において、
前記ハミング符号は、前記検査行列に基づく拡大ハミング符号であり、
前記制限付加ステップは、前記検査行列の前記孤立変数ノードおよび前記拡大ハミング符号について前記孤立変数ノード検出ステップで検出された孤立変数ノードを整数の値とする制限を加える
ことを特徴とする適応的線形計画復号方法。
【請求項３】
請求項１または請求項２に記載の適応的線形計画復号方法において、
前記復号結果算出ステップは、前記検査行列の行、およびその行の線形結合により得られる任意の新たな行を用いて前記混合整数線形計画法による解を算出することを特徴とする適応的線形計画復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、適応的線形計画復号方法に関し、特にハミング符号の適応的線形計画法による復号技術に関する。
【背景技術】
【０００２】
低密度パリティ検査符号（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅ、以下、「ＬＤＰＣ」という。）は、Ｇａｌｌａｒｇｅｒにより最初に発見され、その後ＭａｃＫａｙにより発展させられた符号訂正の方法である（非特許文献２参照）。この符号訂正は、スパース行列と呼ばれる行列を検査行列に用いることを特徴とする。
【０００３】
図３３にその検査行列の一例を示す。スパース行列（以下、「Ｈ」と表現する。）において、例えば、１００行２００列の場合によく用いられる行列形式は、１列に含まれる「１」の数が３個、そして１行に含まれる「１」の数が６個である。「１」の数がまばらであることからスパース（ｓｐａｒｓｅ）行列と呼ばれる。
【０００４】
図３３に示す従来のＬＤＰＣの検査行列の例において、破線の円で囲まれた「１」の配置からなる四角形ループは禁止されている。したがって、この場合、４つの破線で囲まれた「１」のうちの１つは削除される。
【０００５】
ここではＭａｃｋａｙの方法により従来のＬＤＰＣによる符号訂正法を説明する。まず、スパース行列のすべての行について、その「１」の配列要素に対応する符号ビットに対して、「１」か「０」であるかの確率ｒxmn、（ただしｍｎは行列要素を表し、ｘは「０」か「１」をとる。）を計算する。その後、検査行列のすべての列の「１」の要素について、その計算した確率ｒxmnを用いてその列に対応する符号のビット位置が「１」か「０」かの確率ｑxmnを計算する。
【０００６】
確率ｑxmnを行列要素ｍについて乗算し、それをｑxnとおく。ｑxnが０．５より大きい場合には「１」、小さい場合には「０」とする。ｑをｑxnを成分とするベクトルとするとｑ×ＨT＝０を満たせば、そのｑが求める符号となる。確率ｑxmn、ｒxmnの計算はあたかも確率密度が伝搬するようなので、確率伝搬（Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ、以下「ＢＰ」いう。）法と呼ばれる。
【０００７】
このような従来の復号方法に対して、非特許文献１に記載されているように、２００５年にＦｅｌｄｍａｎによって線形計画（Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ、以下「ＬＰ」という。）による復号法が提案された。これは復号すべきビット（ｂｉｔ）それぞれに対数尤度比（以下「ＬＬＲ」ということがある。）を求め、ＬＬＲを係数、符号成分を変数とする線形関数をつくる。
【０００８】
なお、対数尤度比（ＬＬＲ）とは、ビットが「０」になる確率と「１」となる確率を求めて、その比の対数をとったものである。ＬＰによりその線形関数の最小値を求めると、そのときの成分が復号すべき符号となっているというものである。
【０００９】
非特許文献３には、このＬＰをさらに発展させた適応的線形計画（Ａｄａｐｔｉｖｅ  ＬＰ、以下「ＡＬＰ」という。）が開示されている。図３４の検査行列を用いて説明すると、これまでのパリティチェックは検査行列の行の個数に対応して３個しかなかったが、それにさらに行同士を足し算したものもパリティチェックに加えたものである。
【００１０】
この新たに生成されたパリティチェックを冗長パリティチェック（Ｒｅｄｕｎｄａｎｔ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ、以下「ＲＰＣ」という。）と呼ぶ。このＲＰＣを用いて復号を行うと復号特性（すなわち、Ｂｅｒ（Ｂｉｔ  Ｅｒｒｏｒ  ｒａｔｅ：符号誤り率）ｖ．ｓ．ＳＮＲ（Ｓｉｇｎａｌ  Ｎｏｉｓｅ  Ｒａｔｉｏ：ＳＮ比）特性）は向上する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】Ｊｏｎ  Ｆｅｌｄｍａｎ，Ｍａｒｔｉｎ  Ｊ．  Ｗａｉｎｗｒｉｇｈｔ，ａｎｄ  Ｄａｖｉｄ  Ｒ．Ｋａｒｇｅｒ，“Ｕｓｉｎｇ  Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ  ｔｏ  Ｄｅｃｏｄｅ  Ｂｉｎａｒｙ  Ｌｉｎｅａｒ  Ｃｏｄｅｓ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ，ｖｏｌ．５１，ｎｏ．３，ｐｐ．９５４−９７２，Ｍａｒ．，２００５．
【非特許文献２】和田山  正，「誤り訂正技術の基礎」，森北出版（２０１０）．
【非特許文献３】Ｍｏｈａｍｍａｄ  Ｈ．Ｔａｇｈａｖｉ  ａｎｄ  Ｐａｕｌ  Ｈ．Ｓｉｅｇｅｌ，“Ａｄａｐｔｉｖｅ  Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｄｅｃｏｄｉｎｇ”，ＩＳＩＴ  ２００６，Ｓｅａｔｌｅ，ＵＳＡ，Ｊｕｌｙ９−１４，２００６，ｐｐ．１３７４−１３７８．
【非特許文献４】Ｎａｎａ  Ｔｒａｏｒｅ，Ｓｈａｓｈｉ  Ｋａｎｔ，Ｔｏｂｉａｓ  Ｌｉｎｄｓｔｒｏｍ  Ｊｅｎｓｅｎ，“Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｄｅｃｏｄｉｎｇ  ５”，［ｏｎｌｉｎｅ］，［平成３０年４月１１日検索］，インターネット＜ｈｔｔｐ：／／ｋｏｍ．ａａｕ．ｄｋ／〜ｔｌｊ／ｍｐａ＿ｌｐ＿ｄｅｃｏｄｉｎｇ＿ｌｄｐｃ．ｐｄｆ＞
【非特許文献５】Ｘｉａｏｊｉｅ  Ｚｈａｎｇ  ａｎｄ  Ｐａｕｌ  Ｈ．Ｓｉｅｇｅｌ，“Ａｄａｐｔｉｖｅ  Ｃｕｔ  Ｇｅｎｅｒａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｍｐｒｏｖｅｄ  Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｂｉｎａｒｙ  Ｌｉｎｅａｒ  Ｃｏｄｅｓ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆ．Ｔｈｅｏｒｙ，ｖｏｌ．５８，ｎｏ．１０，ｐｐ．６５８１−６５９４，Ｏｃｔ．，２０１２．
【非特許文献６】先名健一，「例題で学ぶ符号理論入門，第２章  通信路符号化と線形符号」，森北出版（２０１１）
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかし、従来のＡＬＰ復号方法をハミング符号の復号に用いると、検査行列（図３４）の本来のパリティチェックによる線形結合のパリティチェックの下、うまくＬＰが働かずに解が求まらない場合がある。そのため、復号方法の実装負荷が大きく、計算時間が長くなってしまう問題があった。
【００１３】
本発明は、上述した課題を解決するためになされたものであり、ハミング符号のＡＬＰによる復号を実現し、結果として、復号方法の実装負荷を低減し、かつ計算時間を短縮できる適応的線形計画復号方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した課題を解決するために、本発明に係る適応的線形計画復号方法は、演算装置と、記憶装置と、通信制御装置とを備える復号装置によって実行される適応的線形計画復号方法であって、前記通信制御装置を介して受信される所定の検査行列で定義されるハミング符号のファクターグラフを生成して前記記憶装置に記憶するファクターグラフ生成ステップと、前記演算装置が、前記検査行列の複数列にそれぞれ対応する変数ノードの拘束条件を、前記記憶装置に記憶されている変数ノードが満たすべき条件式に基づいて導出する拘束条件導出ステップと、前記演算装置が、前記記憶装置に記憶されている前記ファクターグラフから前記検査行列の複数行にそれぞれ対応する複数のチェックノードに接続している前記変数ノードのうち、１つのチェックノードに接続している孤立変数ノードを検出する孤立変数ノード検出ステップと、前記演算装置が、前記孤立変数ノードを整数の値とする制限を加える制限付加ステップと、前記演算装置が、前記拘束条件と前記制限が加えられた前記孤立変数ノードに関する情報とに基づいて、混合整数線形計画法により解を算出して算出結果を前記ハミング符号の復号結果として前記記憶装置に記憶する復号結果算出ステップとを備えることを特徴とする。
【００１５】
また、本発明に係る適応的線形計画復号方法において、前記ハミング符号は、前記検査行列に基づく拡大ハミング符号であり、前記制限付加ステップは、前記検査行列の前記孤立変数ノードおよび前記拡大ハミング符号について前記孤立変数ノード検出ステップで検出された孤立変数ノードを整数の値とする制限を加えてもよい。
【００１６】
また、本発明に係る適応的線形計画復号方法において、前記復号結果算出ステップは、前記検査行列の行、およびその行の線形結合により得られる任意の新たな行を用いて前記混合整数線形計画法による解を算出してもよい。
【発明の効果】
【００１７】
本発明によれば、所定の検査行列で定義されるハミング符号のファクターグラフからチェックノードに接続している変数ノードのうち、１つのチェックノードのみに接続している孤立変数ノードを整数の値とする制限を加えて混合整数線形計画法により復号結果を算出するので、ハミング符号のＡＬＰによる復号を実現し、復号方法の実装負荷を低減し、かつ計算時間を短縮することができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、本発明の実施の形態に係るＡＬＰ復号方法を実施する復号装置のハードウェア構成を示すブロック図である。
【図２】図２は、本発明の実施の形態に係る検査行列を示す図である。
【図３】図３は、図２に対応するファクターグラフを示す図である。
【図４】図４は、本発明の実施の形態に係るコストベクトルの例を示す図である。
【図５】図５は、本発明の実施の形態に係るチェックノードに属する変数ノードが満たすべき式を示す図である。
【図６Ａ】図６Ａは、本発明の実施の形態に係るＬＰ復号プログラムの例を示す図である。
【図６Ｂ】図６Ｂは、本発明の実施の形態に係るＬＰ復号プログラムの例を示す図である。
【図７】図７は、図３のファクターグラフの整数値を持つ変数ノードを「×」で消し、それ以外の変数ノードとチェックノードが作るサークルを求める手順を説明する図である。
【図８】図８は、図２の検査行列の１行目と３行目の和のパリティチェックが満たすべき行列式を説明する図である。
【図９】図９は、ステップ２の結果を示すファクターグラフである。
【図１０】図１０は、ステップ３の結果を示すファクターグラフである。
【図１１】図１１は、ステップ４の結果を示すファクターグラフである。
【図１２】図１２は、図２の検査行列を並び替えた行列を説明する図である。
【図１３】図１３は、図１２の行列の簡約化行列を説明する図である。
【図１４】図１４は、図２の検査行列の列の入れ替えを説明する図である。
【図１５】図１５は、図１４の簡約化行列を説明する図である。
【図１６】図１６は、表１のイタレーション２−１の変数ノードの値を反映したファクターグラフを示す図である。
【図１７】図１７は、本実施の形態に係るＡＬＰ復号方法を説明するフローチャートである。
【図１８】図１８は、短縮ハミング符号の検査行列を示す図である。
【図１９】図１９は、図１８に対応するファクターグラフを示す図である。
【図２０】図２０は、ＬＰによる復号結果を反映したファクターグラフを示す図である。
【図２１】図２１は、チェックノードＡ＋Ｃを追加した復号結果を反映したファクターグラフを示す図である。
【図２２】図２２は、図１８の検査行列の列を入れ替えた行列を示す図である。
【図２３】図２３は、図２２の行列の簡約化行列を説明する図である。
【図２４Ａ】図２４Ａは、拡大ハミング符号の検査行列を示す図である。
【図２４Ｂ】図２４Ｂは、拡大ハミング符号を説明する図である。
【図２５】図２５は、図２４Ａに対応するファクターグラフを示す図である。
【図２６】図２６は、評価結果を反映したファクターグラフを示す図である。
【図２７】図２７は、図２４Ａの検査行列を復号結果により並び替えた行列を示す図である。
【図２８】図２８は、図２７の行列の簡約化行列を説明する図である。
【図２９】図２９は、図２４Ａの検査行列を復号結果により並び替えた行列を示す図である。
【図３０】図３０は、図２９の検査行列の簡約化行列を説明する図である。
【図３１】図３１は、図２４Ａの検査行列を復号結果により並び替えた行列を示す図である。
【図３２】図３２は、図３１の行列の簡約化行列を説明する図である。
【図３３】図３３は、従来のＬＤＰＣ法を説明するための図である。
【図３４】図３４は、従来の復号方法を説明するための検査行列を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の好適な実施の形態について、図１から図３２を参照して詳細に説明する。
［発明の原理］
はじめに、本発明の原理について説明する。
まず、前述したように、ＡＬＰを用いたハミング符号の復号ができない場合があることが、以下に示すシミュレーションにより見出された。
【００２０】
以下において、符号長７、信号長４、パリティ検査長３のハミング符号の符号語をＣ（７，４，３）と書くことにし、検査行列は図２に示したものとする。要素７，４，３は、それぞれ送信する全体の符号長、信号長、検査行列の行同士の比較において異なった要素を持つ最小数、すなわち最小の距離を示している。
【００２１】
まずＦｅｌｄｍａｎの方法にしたがってハミング符号の復号を行う。非特許文献４の第５章にしたがって図２に示す検査行列、および図４に示すＬＬＲを成分とするベクトル（以下「コストベクトル」という。）を用いてｍａｔｌａｂ（登録商標）においてシミュレーションを行った。
【００２２】
図４に示すＬＰで用いられるコストベクトルλの一例において、左から変数ノードｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7に対応している。この場合は、ｘ1＝１なので、その係数（ＬＬＲ）は、−７／４であり、それ以外はゼロなので、ＬＬＲは「１」となっている。なお、目的関数ｆを、ｆ＝（−７／４）ｘ1＋ｘ2＋ｘ3＋ｘ4＋ｘ5＋ｘ6＋ｘ7として、目的関数ｆの最小値をＬＰにより求め、その結果を復号結果とする。
【００２３】
この場合、送信したビットのデータが符号であるための条件が図５に示す式で与えられる。ここで、ｘnはチェックノード（後述する図３の「四角」で示されているノード。）につながっている変数ノード（後述する図３の「丸」で示されているノード。）である。
【００２４】
ここで具体的な例を用いて図５に示す式を説明する。ｎ（ｍ）はチェックノードに接続している変数ノードの全体の集まり、Ｖはｎ（ｍ）の部分集合である。
【００２５】
【数１】
2019208097.tif 000003
【００２６】
上記式はｎ（ｍ）の要素からＶの要素を除いた集合を表し、｜Ｖ｜はその要素数を表す。変数ノードｘnが符号であるためには図５に示す式が成り立ち、そのとき｜Ｖ｜が奇数でなければならないということを意味している。
【００２７】
検査行列の第１行（以下、「チェックノードＡ」と呼び、「ｃｈｋ（Ａ）」と略す。）を例にとると、要素をその列数で表すとｎ（ｍ）＝｛１，２，４，５｝である。ここでＶ＝｛１｝として、その要素がｘ1とすると、満たすべき式の１つは次式（１）で表される。
ｘ1−（ｘ2＋ｘ4＋ｘ5）≦０          ・・・（１）
【００２８】
上式（１）において、ｘ1をｘ2，ｘ4，ｘ5に置き換えて同様に式を求める。これらは、図６Ａに示す復号プログラムの例における行列Ａおよび行列ｂ（図６Ａの矢印）に反映される。また、図６Ａに示すプログラム例においては、図６Ｂの中で要素数｜Ｖ｜＝３の場合についても反映されている。そして、行列Ａおよび行列ｂの条件のもと、図６Ａに示す、目的関数の最小値を求める。求めた解がすべて整数なら、それが符号である。
【００２９】
復号過程の具体例を以下に示す。ここでは簡単のため符号［０，０，０，０，０，０，０］を取り上げ、その第１ビットが反転したとして、送信語として［１，０，０，０，０，０，０］を送りＬＰにより復号を行う。
【００３０】
［ステップ１］
前述した行列Ａの最後の行でｘ1＝１のとき、それに対応する行列ｂの値が「１」となっているのはｘ1の最大値を決めるためである。反転ビットのＬＬＲは図４に示したように負なので、上記のように行列ｂの対応する値を「１」としないとｘ1は無限に大きくなる。
結果はｘ＝［１，１／３，０，１／３，１／３，０，０］となり、非特許文献４の結果と一致した。
【００３１】
その後、非特許文献３、４にしたがってＡＬＰにより復号を行う。今回、ステップ１では整数ではない要素が得られたので、整数の要素部分を切り取るためのファクターグラフ（図３）が必要となる。
【００３２】
図３は、図２に示す検査行列に対応するファクターグラフを示す図である。ファクターグラフは、図２に示す検査行列の行を上からチェックノードＡ，Ｂ，Ｃとし、列を左から変数ノードｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7とした場合におけるチェックノードと変数ノードとの関係を示している。
【００３３】
要素１，３，６，７が整数なのでその部分の変数ノードを削除するとファクターグラフは図７に示す構成となる。図７のファクターグラフでは、整数部分のノードに「×」と示している。
【００３４】
［ステップ２］
ここでは、パリティチェックＡ（以下「ｃｈｋ（Ａ）」と示す。）とパリティチェックＣ（以下「ｃｈｋ（Ｃ）」と示す。）で作られるサイクル（ｃｙｃｌｅ）を採用すると、ｃｈｋ（Ａ）＋ｃｈｋ（Ｃ）の満たすべき条件は図８に示す行列式で表現されている。この場合ｘ3はｃｈｋ（Ａ）, ｃｈｋ（Ｃ）ともゼロであり、またｘ4、ｘ5は、同じ数の２進法による足し算なのでゼロとなる。
【００３５】
図８に示す行列式の１行目を試してみると、１×１＋（１／３）×（−１）＝２／３≦０となり不等式を満たさない。そのため、この第１行目を拘束条件（以降「ｃｕｔ」ということがある。）として使い、拘束条件の中に加える。そして再びプログラムを走らせて目的関数の最適解を求める。
【００３６】
結果はｘ＝［１，２／３，０，１／３，０，１／３，０］となり非特許文献４の結果と一致した。ステップ１と同様に、図９に示すファクターグラフを使ってサイクルとなるパリティチェックを探す。
【００３７】
［ステップ３］
この場合、図９においてサイクルが２つ存在する。ここではまずｃｈｋ（Ｂ）とｃｈｋ（Ｃ）とを選択する。ｃｈｋ（Ｂ）とｃｈｋ（Ｃ）を選択しても、ｘ＝［１，２／３，０，１／３，０，１／３，０］は拘束条件ｘ2−ｘ3−ｘ5−ｘ7≦０を満たさない。図６Ａおよび図６Ｂに示す行列Ａおよび行列ｂにさらに［０，１，−１，０，−１，０，−１］と「０」を追加してシミュレーションを行う。
【００３８】
結果は以下のように得られた。
ｘ＝［１，１／２，０，１６９／７４５，２３３／８５３，２３３／８５３，１６９／７４５］
なお、図６Ａに示した復号プログラムの最後で「ｒａｔｓ」という命令で小数を分数に変換しているので、上記の結果をもとの小数に直すと次のように表される。
ｘ＝［１．００００，０．５０００，０．００００，０．２２６８，０．２７３２，０．２７３２，０．２２６８］
これより、ｘ5＋ｘ7＝０．５となり、本ステップで付け加えた拘束条件ｘ2−ｘ3−ｘ5−ｘ7≦０を満足することがわかる。
【００３９】
また、ステップ１およびステップ２と同様にファクターグラフを作成し、サイクルとなるパリティチェックを探す。図１０は上記結果を示すファクターグラフである。図１０のファクターグラフでは、整数部分のノードに「×」と示している。
【００４０】
非特許文献５に記載されている従来のＲＰＣ検索法を用いると、ステップ３で得られた結果においては、冗長パリティチェックであるＲＰＣを生み出さないことがわかる。なお、非特許文献５に記載されているＲＰＣ検索法の詳細は後述する。
【００４１】
［ステップ４］
次に、もうひとつのサイクルを選択する。ｃｈｋ（Ａ）とｃｈｋ（Ｂ）を選択するとｘ＝［１，２／３，０，１／３，０，１／３，０］は拘束条件ｘ1−ｘ3−ｘ5−ｘ6≦０を満たさない。ステップ３と同様に計算すると、ｘ＝［１，１／２，０，０，１／２，１／２，０］となった。このファクターグラフを図１１に示す。サイクルとなっているパリティチェックはｃｈｋ（Ａ）＋ｃｈｋ（Ｂ）＋ｃｈｋ（Ｃ）である。また、図１１において整数部分のノードに「×」と示している。
【００４２】
［ステップ５］
ステップ４で算出されたｘ＝［１，１／２，０，０，１／２，１／２，０］は、拘束条件ｘ1−ｘ3−ｘ4−ｘ7≦０を満たさない。ステップ４と同様に計算した結果は次の通りである。
ｘ＝［０．２１６１，０．０８０６，０．０８３４，０．０６８３，０．０８０６，０．０７１７，０．０８３４］×１０-8
【００４３】
以上のステップ１からステップ５までのシミュレーション結果を、表１に示す。また、非特許文献４に記載の技術を用いてハミング符号（７，４，３）のＡＬＰによる復号を上記シミュレーションと同じ条件で行った計算結果を表２に示す。
【００４４】
【表１】
2019208097.tif 000004
【００４５】
【表２】
2019208097.tif 000005
【００４６】
表１および表２は、それぞれイタレーション（ｉ）、サイクルとなるパリティチェック、冗長パリティチェック（ＲＰＣ）の拘束条件（ｃｕｔ）、および復号結果を示す解ｘをそれぞれ示している。
【００４７】
表１と表２との比較より、（ｉ）互いの最終結果が異なっていることがわかる。また、（ｉｉ）上記ステップ１からステップ５までのシミュレーションによる計算結果に示されるイタレーション２−１およびイタレーション２−２におけるチェックノード選択の手順でイタレーション２−１を選んでしまうと解析が止まってしまうことがわかる。（ｉ）の最終結果が互いに異なっていることについては、得られた結果が非常に小さく実質的にゼロとみなせることより、一致すると判断できる。
【００４８】
今回の例では手動で図６Ａのプログラム例に示す行列Ａおよび行列ｂの設定を行っているが、実際にはプログラムを組んで検査行列の任意の行を選んで線形結合を作成し、計算を行う。
【００４９】
ここで、受信した符号の解析からＲＰＣが存在するかどうか判断するには、非特許文献５に記載されているＲＰＣ検索法を使う。非特許文献５に記載されているＲＰＣ検索法では、まず得られた解のベクトルｘの成分を；（ａ）非整数、ゼロ、１の順にしたがって分類する。ただし非整数要素だけは１／２から距離の絶対値に応じて、小さい方の要素から順に並べ換える；（ｂ）次に、（ａ）と同じ順序で検査行列の列を並べる；（ｃ）そして、非整数要素の行列部分を行階段（ｅｃｈｅｌｏｎ）形にする。そのときｅｃｈｅｌｏｎ部分の行の重みが１つだけ（行の中の要素がただ１つ）のとき、ＲＰＣは存在する。
【００５０】
上述したシミュレーションの例を用いて、ＲＰＣ検索を行う。表１のイタレーション１の復号結果を示す解ｘ＝［１，２／３，０，１／３，０，１／３，０］を用いる。上記手順（ａ）および（ｂ）を行った結果得られた行列Ａ1を図１２に示す。なお、｜２／３−１／２｜＝｜１／３−１／２｜＝１／６である。
【００５１】
上記手順（ｃ）に従って、図１２に示す行列Ａ1を簡約化行列（ｒｅｄｕｃｅｄ  ｒｏｗ  ｅｃｈｅｌｏｎ  ｆｏｒｍ、以下「ｒｒｅｆ」と記す。）化したものを図１３に示す。この場合、行列ｒｒｅｆ（Ａ1）は３個のＲＰＣが存在することがわかる。図１３に示す行列ｒｒｅｆ（Ａ1）において、２進法の演算規則（−１＝１、２＝０）を用いてさらに変換している。
【００５２】
今度は表１のイタレーション２−１の復号結果を示す解ｘ＝［１．００００，０．５０００，０．００００，０．２２６８，０．２７３２，０．２７３２，０．２２６８］を使う。上記手順（ａ）および（ｂ）に従って検査行列の列を入れ替えた行列Ａ1を図１４に示す。さらにそのｒｒｅｆを求めると図１５に示す行列ｒｒｅｆ（Ａ1）となり、どの行列もｅｃｈｅｌｏｎ部分は「１」の要素が２以上なのでＲＰＣはないことがわかる。なお、図１５において、分数領域は、１列から５列までの領域である。また、図１６は、表１のイタレーション２−１の変数ノードの値をファクターグラフ上に表示した図である。
【００５３】
ここで再び図１０に示す上記シミュレーションのステップ３に基づくファクターグラフとその結果図１６について立ち返る。図１６のファクターグラフを見ると、パリティチェックを満たすため、それぞれの共通の変数ノードを分数としていることがわかる。ここでＲＰＣを満たさないファクターグラフでは、分数になる変数ノードは、それ自身のパリティチェックだけに接続している変数ノード（ここではｘ7）にも起こっている。
【００５４】
この場合、パリティチェック（ｘ2−ｘ3−ｘ5−ｘ7＝０）を満たすためには、１つの変数ノード（ｘ5）では済まず、他の変数ノード（ｘ4，ｘ6）にもおよび、また他のチェックノード（ここではチェックノードＡおよびＢ）の変数ノード（ｘ2）を分数にしている。その結果、分数を持つ変数ノードの数が増えてＲＰＣを発生させる条件（この場合は分数の変数のノードの数≦３）が成り立たなくなってしまう。
【００５５】
そのため、本発明では、チェックノードに接続している変数ノードのうち、該当するチェックノード以外他にどこにもつながってない変数ノードに対して、整数の値以外とらないという制限を加える構成を採用する。そして、本発明では、ＬＰによる復号方法を拡張した混合整数線形計画（Ｍｉｘｅｄ  Ｉｎｔｅｇｅｒ  Ｌｉｎｅａｒ  Ｐｒｏｇｒａｍｍｉｎｇ、以下「ＭＩＬＰ」という。）を用いて、変数ノードに整数および実数の値を有する問題の最適解を求めてハミング符号を復号する。
【００５６】
［実施の形態］
以下、本発明に係る適応的線形計画（ＡＬＰ）復号方法を実施するための復号装置１について説明する。
【００５７】
図１に示すように、復号装置１は、バス１０１を介して接続されるＣＰＵ１０３と主記憶装置１０４とを有する演算装置１０２、通信制御装置１０５、外部記憶装置１０６、表示装置１０７を備えるコンピュータと、これらのハードウェア資源を制御するプログラムによって実現することができる。
【００５８】
ＣＰＵ１０３と主記憶装置１０４とは、演算装置１０２を構成する。主記憶装置１０４には、ＣＰＵ１０３が各種制御や演算を行うためのプログラムが予め格納されている。なお、復号装置１は、復号処理を実行する専用のハードウェアで構成されていてもよい。例えば、グラフィックプロセッサ、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｌｅ  Ｇａｔｅ  Ａｒｒａｙ）などの集積回路を採用できる。
【００５９】
通信制御装置１０５は、復号装置１と各種外部電子機器との間を、通信ネットワークＮＷを介して接続するための制御装置である。通信制御装置１０５は、通信ネットワークＮＷを介して復号する符号化データを受信する。
【００６０】
外部記憶装置１０６は、読み書き可能な記憶媒体と、その記憶媒体に対してプログラムやデータなどの各種情報を読み書きするための駆動装置とで構成されている。外部記憶装置１０６には、記憶媒体としてハードディスクやフラッシュメモリなどの半導体メモリを使用することができる。外部記憶装置１０６は、データ記憶部１０６ａ、設定情報記憶部１０６ｂ、プログラム格納部１０６ｃ、図示しないその他の格納装置で、例えば、この外部記憶装置１０６内に格納されているプログラムやデータなどをバックアップするための格納装置などを有することができる。
【００６１】
データ記憶部１０６ａには、通信制御装置１０５を介して受信された符号化データや復号データなどが記憶される。
設定情報記憶部１０６ｂには、検査行列に関する情報、拘束条件に関する情報、予め定められている条件式、整数とする変数ノードに関する情報などの設定情報が記憶されている。
【００６２】
プログラム格納部１０６ｃには、本実施の形態における行列演算処理や、ファクターグラフ生成処理、拘束条件導出処理、ＲＰＣ検索処理などハミング符号の復号に必要な処理を実行するための各種プログラムが格納されている。
【００６３】
表示装置１０７は、復号装置１の表示画面を構成する。表示装置１０７は液晶ディスプレイなどによって実現される。表示装置１０７には、例えは、ファクターグラフなど復号装置１による演算結果が画面に表示される。
【００６４】
［ハミング符号のＡＬＰ復号処理］
次に、本実施の形態に係るハミング符号のＡＬＰ復号処理について、図１７のフローチャートを参照して説明する。本実施の形態では、［発明の原理］で用いた符号と同様に、符号長７、信号長４、パリティ検査長３のハミング符号（７，４，３）を復号の対象とし、図２で示す検査行列を用いる。
【００６５】
まず、演算装置１０２は、図２に示す検査行列より、図３に示すファクターグラフを生成する（ステップＳ１）。生成されたファクターグラフは、データ記憶部１０６ａに記憶される。図３に示すファクターグラフにおいて、変数ノードｘ1〜ｘ７は「丸」で表され、チェックノードＡ，Ｂ，Ｃは、「四角」で表されている。
【００６６】
次に、演算装置１０２は、設定情報記憶部１０６ｂに記憶されているチェックノードに属する変数ノードｘnが満たすべき式（条件式）を読み出し、ハミング符号（７，４，３）が満たすべき不等式で表される拘束条件を導出する（ステップＳ２）。拘束条件として、前述した式（１）（ｘ1−（ｘ2＋ｘ4＋ｘ5）≦０）が得られる。演算装置１０２は導出した拘束条件を設定情報記憶部１０６ｂに記憶する。
【００６７】
次に、演算装置１０２は、プログラム格納部１０６ｃに格納されている復号プログラム（図６Ａ）において、復号処理における条件を設定する行列Ａおよび行列ｂを求める（ステップＳ３）。演算装置１０２は、例えば、図６Ｂに示す行列Ａおよび行列ｂを設定する。行列Ａにおいて最後の行［１，０，０，０，０，０，０］および行列ｂの一番右の列の１はｘ1≦１を表す。演算装置１０２は、求めた行列Ａおよび行列ｂを復号プログラムにおいてロードする。
【００６８】
また、本実施の形態では、演算装置１０２は、混合整数線形計画法（ＭＩＬＰ）を用いるので、図６Ａに示す復号プログラムにおいて、線形計画法（ＬＰ）の関数示す「ｌｉｎｐｒｏｂ」からＭＩＬＰの関数「ｉｎｔｌｉｎｐｒｏｂ」に変更する。
【００６９】
次に、演算装置１０２は、ステップＳ１で生成したファクターグラフにおいてチェックノードに接続している変数ノードのうち、１つのチェックノードのみに接続している変数ノード（以下、「孤立変数ノード」という。）を検出する（ステップＳ４）。図３に示す例では、演算装置１０２は、孤立変数ノードｘ1、ｘ3、ｘ7を検出する。演算装置１０２は、検出した孤立変数ノードの情報を主記憶装置１０４に一時的に記憶する。
【００７０】
次に、演算装置１０２は、ステップＳ４で検出した孤立変数ノードは整数の値のみとする指定を行う（ステップＳ５）。具体的には、演算装置１０２は、孤立変数ノードｘ1，ｘ3，ｘ7に対して整数以外はとらないという制限を加える。より詳細には、演算装置１０２は、整数とする孤立変数ノードｘ1，ｘ3，ｘ7の指定をｉｎｔｃｏｎ＝［１，３，７］で与える。
【００７１】
その後、演算装置１０２は、ＭＩＬＰによる復号を行い解を求める（ステップＳ６）。
より詳細には、演算装置１０２は、ステップＳ２で導出された拘束条件、ステップＳ３で求められた行列Ａおよび行列ｂ、および整数とする制限が加えられた孤立変数ノードに関する情報に基づいて、ＭＩＬＰによる解を算出し、算出結果をハミング符号の復号結果としてデータ記憶部１０６ａに記憶する。
【００７２】
より具体的には、演算装置１０２が実行したＭＩＬＰによる表１に示す評価を行うと、表１のイタレーション２−１の復号結果を示す解ｘは、ｘ＝［１，１／２，０，０，１／２，１／２，０］と算出された。また、以降のイタレーションにおいては、表２に示すイタレーション３、４の復号結果を示す解ｘと同じ値となった。
【００７３】
以上、本実施の形態に係るハミング符号のＡＬＰ復号方法によれば、検査行列の独立した変数ノードを整数にするという条件を加えて線形計画法による解を求めると、どのようなチェックノードの組み合わせでもＲＰＣが存在することがわかる。したがって、この場合には、非特許文献５によるＲＰＣ検索過程は不要となり、復号方法の実装が簡単になり、計算時間を短縮することができる。すなわち、表２のチェックノードの組み合わせを順番に作用させればハミング符号の復号ができる。
【００７４】
［変形例１］
次に、本実施の形態に係るハミング符号のＡＬＰ復号方法の変形例１について説明する。変形例１では、図１８で示す検査行列（１５，１１，３）（非特許文献６の例題２．２０の検査行列）から生成される短縮ハミング符号（８，４，４）の復号について説明する。
【００７５】
本変形例１においても、演算装置１０２は、短縮ハミング符号について、上述した実施の形態と同様に図１７のフローチャートで示すステップＳ１からステップＳ６までの復号処理を実行する。演算装置１０２が検査行列に基づいてステップＳ１で生成したファクターグラフを図１９に示す。
【００７６】
ここで、本発明との比較のため、ＬＰによって導出された復号結果の解について説明する。演算装置１０２が、図６Ａに示す復号プログラムに従ってＬＰによる復号を実行して得られた解ｘは、次式（２）となった。
ｘ＝［１，１／２，１／２，１／２，０，０，０，０］      ・・・（２）
この復号結果を反映したファクターグラフを図２０に示す。整数のノードは「×」で示されている。また、図２０に示すように、変数ノードｘ2，ｘ3，ｘ4からつくられるチェックノードのループは５種類存在することがわかる。
【００７７】
具体的には、チェックノードＡとＣからなるサークル（以下「Ａ−Ｃ」という。）；チェックノードのループがＢとＣからなるサークル（以下「Ｂ−Ｃ」という。）；チェックノードのループがＣとＤからなるサークル（以下「Ｃ−Ｄ」という。）；チェックノードのループがＡ、Ｂ、Ｃからなるサークル（以下「Ａ−Ｂ−Ｃ」という。）；およびチェックノードのループがＡ、Ｂ、Ｄからなるサークル（以下「Ａ−Ｂ−Ｄ」という。）の５種類である。以下、そのいくつかの場合について考察する。
【００７８】
（ａ）サークルＡ−Ｃを選択した場合
この場合、符号が満たすべき拘束条件の式の１つは、図５に示す条件式より、｜Ｖ｜＝１の場合、ｘ1−ｘ3−ｘ5−ｘ7≦０となる。上式（２）で示すＬＰによる解ｘは、この拘束条件を満たさない。ここで、［１，０，−１，０，−１，０，−１，０］を図６Ａおよび図６Ｂの行列Ａに、そして「０」を行列ｂに挿入して、評価を実行してＬＰによる解を求めると、次の式（３）のような復号結果を示す解ｘが得られた。
ｘ＝［１，１／３，２／３，１／３，１／３，０，０，０］      ・・・（３）
【００７９】
上式（３）で示すチェックノードのサークルＡ−Ｃを追加した復号結果のファクターグラフを図２１に示す。図２１に示すように、各チェックノードの作るサークルは、図２０のファクターグラフに示すものと同じである。
【００８０】
ここで、前述した非特許文献５に記載のＲＰＣ検索法を行う。図１８に示す検査行列の列を上式（３）で示す復号結果を示す解ｘによって入れ替えた行列Ａ1を図２２に、それをｒｒｅｆの形にした行列ｒｒｅｆ（Ａ1）を図２３に示す。図２３に示す行列ｒｒｅｆ（Ａ1）の下の列の数字は、Ａ1の列を示している。これより、すべての行がＲＰＣの存在する条件を満たすので、第１行をとる。これを図２１に示すチェックノード（サークルＡ−Ｃ）を追加した復号結果を反映したファクターグラフで確認すると、サークルＣ−Ｄとなっている。
【００８１】
このＲＰＣから作られるパリティチェックの１つがｘ1−ｘ2−ｘ7−ｘ8≦０であり、これは上式（３）で示す復号結果の解を満たさない。このことから、図６Ａおよび図６Ｂに示す行列Ａに［１，−１，０，０，０，０，−１，−１］を挿入し、行列ｂに「０」を挿入してＬＰによる解ｘを算出する。
【００８２】
この場合の解ｘは次の式（４）となる。
ｘ＝１．０ｅ−１４×［０．７２１９，０．５２９１，０．５２９１，０．１５３２，０．０４６９，０．００４４，０．１５３８，０．０４６９］        ・・・（４）
【００８３】
ここで、本変形例１において用いている検査行列のファクターグラフ（図１９）の中で、ただ１つのチェックノードに接続している孤立変数ノードｘ5、ｘ6、ｘ7、ｘ8を整数にするという制限を加えてＭＩＬＰにより復号を行うと、復号結果の解ｘは、次のとおりとなった。
ｘ＝［１，１／２，１／２，１／２，０，０，０，０］
この結果は、上記孤立変数ノードｘ5、ｘ6、ｘ7、ｘ8を整数にするという制限を加えていない場合の復号結果の解と同様であった。しかし、サークルＡ−Ｃを選択した場合の制約ｘ1−ｘ3−ｘ5−ｘ7≦０を加えてＬＰによる復号結果を算出すると、
ｘ＝［０，０，０，０，０，０，０，０］
が得られた。
【００８４】
（ｂ）サークルＢ−Ｃを選択した場合
次に、サークルＢ−Ｃを選択した場合、孤立変数ノードを整数にするという制限を加えていない場合のＬＰによる復号結果の解は、
ｘ＝［１，１／３，１／３，２／３，０，１／３，０，０］
が得られたが、孤立変数ノードを整数にする制限を加えた場合のＭＩＬＰによる復号結果の解ｘは、
ｘ＝［０，０，０，０，０，０，０，０］
となった。
【００８５】
（ｃ）サークルＡ−Ｂ−Ｄを選択した場合
次に、サークルＡ−Ｂ−Ｄを選択した場合、孤立変数ノードを整数にするという制限を加えていない場合のＬＰによる復号結果の解ｘは、
ｘ＝１．０ｅ−１２×［０．６７４９，０．２３０５，０．２３０５，０．２３０５，０．２２９７，０．２２９７，０．００９６，０．２２９７］
となるが、孤立変数ノードを整数にする制限を加えた場合のＭＩＬＰによる復号結果の解ｘは、
ｘ＝［０，０，０，０，０，０，０，０］
となった。
【００８６】
上記（ａ）、（ｂ）、（ｃ）の結果を表３〜表８に示す。
表３および表４は、パリティチェックとして検査行列の１行と３行の線形結合を選んだ場合の「整数指定なし」および「整数指定あり」の復号結果をそれぞれ示している。
表５および表６は、パリティチェックとして検査行列の２行と３行の線形結合を選んだ場合の「整数指定なし」および「整数指定あり」の復号結果をそれぞれ示している。
表７および表８は、パリティチェックとして検査行列の１行、２行、および４行の線形結合を選んだ場合の「整数指定なし」および「整数指定あり」の復号結果をそれぞれ示している。
【００８７】
【表３】
2019208097.tif 000006
【００８８】
【表４】
2019208097.tif 000007
【００８９】
【表５】
2019208097.tif 000008
【００９０】
【表６】
2019208097.tif 000009
【００９１】
【表７】
2019208097.tif 000010
【００９２】
【表８】
2019208097.tif 000011
【００９３】
以上説明したように、短縮ハミング符号の復号についても孤立変数ノードを整数指定する制限を加えてＭＩＬＰによる解を求めることで、ＲＰＣ検索過程は不要となり、ＡＬＰ復号方法の実装がより簡単になる。また、孤立変数ノードを整数にするという条件を加えて評価を行うことで、少ない評価回数で解にたどり着くことが可能となるので、ＬＰによる復号における演算時間の短縮が可能となる。
【００９４】
［変形例２］
次に、本実施の形態に係るハミング符号のＡＬＰ復号方法の変形例２について説明する。変形例２では、図２４Ａで示す検査行列（７，４，３）から生成される拡大ハミング符号（８，４，４）の復号について説明する。
【００９５】
拡大ハミング符号とは、図２４Ｂに示すように、図２に示した検査行列に１行１列を加えて検査行列を拡張したハミング符号である。図２４Ｂの例では、ハミング符号（７，４，３）の検査行列（図２）の最後の行に全ての要素が「１」である１行８列を加え（図２４Ｂの矢印）、最後の列にすべての要素が「０」である３行１列を加えている（図２４Ｂの矢印）。
【００９６】
本変形例２においても、演算装置１０２は、拡大ハミング符号について、上述した実施の形態と同様に図１７のフローチャートで示すステップＳ１からステップＳ６までの復号処理を実行する。演算装置１０２が検査行列に基づいてステップＳ１で生成したファクターグラフを図２５に示す。図２５に示すファクターグラフにおいて、点線は、拡大ハミング符号における新たなチェックノードＤによる結合を表している。
【００９７】
ここで、本発明との比較のため、ＬＰによって導出された解について説明する。演算装置１０２が、図６Ａに示す復号プログラムに従って実行したＬＰによる復号結果を示す解ｘは、次式（５）となった。
ｘ＝［１，１／３，０，１／３，１／３，０，０，０］      ・・・（５）
【００９８】
この復号結果のファクターグラフを図２６に示す。整数のノードは「×」で示されている。また、サークルを形成するチェックノードはＡ−Ｂ、Ａ−Ｃ、Ａ−Ｄ、Ｃ−Ｂ−Ｄ、Ｃ−Ｂ−Ａ、およびＣ−Ｂ−Ｄ−Ａとなっている。
【００９９】
ここで、非特許文献５に記載のＲＰＣ検索を行う。
図２４に示す検査行列の列を、上式（５）で示されるＬＰによる解ｘに従って、分数；ゼロ；１の順に並べ替える。並べ替えた行列Ａ1を図２７に示す。
【０１００】
図２８は、並べ替えた行列Ａ1より求められた行列ｒｒｅｆ（Ａ1）を示す。図２８において、行列の上に示す数字は図２４Ａの検査行列の列に対応する。図２８に示す行列ｒｒｅｆ（Ａ1）の第１行目よりチェックノードが満たすべき拘束条件の不等式の１つは、
ｘ1−ｘ2−ｘ6−ｘ7≦０
であり、上式（５）で示されるＬＰによる復号結果を示す解ｘは上記条件を満たさない。ＲＰＣ（サークルＡ−Ｃに対応して）として、図６Ａおよび図６Ｂに示す行列Ａに［１，−１，０，０，０，−１，−１，０］を挿入し、行列ｂには「０」を挿入し、ＬＰによる復号を行う。
【０１０１】
ＬＰによる復号結果を示す解ｘは、
ｘ＝［１，２／３，０，１／３，０，１／３，０，０］・・・（６）
となった。
【０１０２】
ここで再び、図２４に示す検査行列の列を上式（６）で示される復号結果に従って、分数；ゼロ；１の順に並べ変える。並べ替えた行列Ａ1を図２９に示す。さらに、行列Ａ1のｒｒｅｆを求める。図３０に行列ｒｒｅｆ（Ａ1）を示す。図３０の行列の上に示す数字は図２４の検査行列の列に対応する。
【０１０３】
この行列ｒｒｅｆ（Ａ1）の第１行目より、チェックノードが満たすべき拘束条件の不等式の１つは、
ｘ1−ｘ2−ｘ3−ｘ8≦０
であるが、上式（６）で示されるＬＰによる復号結果を示す解ｘは、上記条件を満たさない。
【０１０４】
さらに、図６Ａおよび図６Ｂに示す行列Ａに［１，−１，−１，０，０，０，−１］を挿入し、行列ｂに「０」を挿入して再度評価する。なお、行列Ａに［１，−１，−１，０，０，０，−１］を加えることは、チェックノードＡ＋ＣとＡ＋Ｄを加えたものに等しい。
【０１０５】
復号結果を示す解ｘは、
ｘ＝［１，４／３，１／４，１／４，０，１／４，０，０］・・・（７）
となった。上式（７）で示される復号結果にしたがって、図２４Ａに示す検査行列の列を組み替えると図３１に示す行列Ａ1で表される。
【０１０６】
さらに図３１に示す行列Ａ1よりｒｒｅｆを求めると図３２に示す行列ｒｒｅｆ（Ａ1）が得られる。図３２において行列の上に示す数字は、図２４の検査行列の列に対応する。図３２に示すように、ＲＰＣは存在しないことが示され、上式（７）で示される復号結果の解が確定される。
【０１０７】
ここで、図２４Ａに示す検査行列のファクターグラフ（図２５）において、変数ノードｘ1，ｘ3，ｘ7，ｘ8を整数とする制限を加えると、整数の変数ノードはＲＰＣ検索において「×」で示されるため、サークルには寄与できない。このことから、ファクターグラフは、実質的には、例えば、図１６に示すハミング符号（７，４，３）におけるファクターグラフの変数ノードｘ2，ｘ4，ｘ5,  ｘ6にチェックノードＤを接続した構造となっている。
【０１０８】
変数ノードを整数とする制限を加えた場合の、１回目のＭＩＬＰによる復号結果は、
ｘ＝［１，１／３，０，１／３，１／３，０，０，０］
となり、変数ノードを整数とする制限を加えていない場合（式（５））と同じ結果となった。同様にＲＰＣ検索を行って評価すると、復号結果は、
ｘ＝［１，２／３，０，１／３，０，１／３，０，０］
となり、これも変数ノードを整数とする制限を加えていない場合（式（６））と同じ結果となった。再度ＲＰＣ検索を行って評価すると、復号結果は、
ｘ＝［０，０，０，０，０，０，０，０］となり正解に到達した。
【０１０９】
以上説明した拡大ハミング符号の復号結果について、「整数指定なし」、および「整数指定あり」の場合の結果をそれぞれ表９および表１０に示す。
【０１１０】
【表９】
2019208097.tif 000012
【０１１１】
【表１０】
2019208097.tif 000013
【０１１２】
以上説明したように、変形例２によれば、拡大ハミング符号の復号においても一部の変数ノードを整数とする制限を加えること、すなわち、検査行列の孤立変数ノードと新たに加わったチェックノードの孤立変数ノードを整数とする制限を加えることで、復号結果の解にたどりつくことができる。
【０１１３】
なお、図５に示すチェックノードに属する変数ノードが満たすべき式を満足する変数ノードの組み合わせは復号結果には何ら影響も与えない。つまり、そのような変数ノードの組み合わせの効果を取り入れてＬＰにより復号しても復号結果は何ら変わらないことを示している。
【０１１４】
復号結果に影響を与えるのは、図５に示す関係を満たさないパリティチェックの組み合わせだけということができる。変数ノードに対する整数指定はＲＰＣの存在を保証するので、非特許文献５に記載されているＲＰＣ検索過程を用いる必要がなく、任意のパリティチェックの組み合わせが図５に示す関係を満足するかを確認するだけで足りる。
【０１１５】
以上、本発明の適応的線形計画復号方法における実施の形態について説明したが、本発明は説明した実施の形態に限定されるものではなく、請求項に記載した発明の範囲において当業者が想定し得る各種の変形を行うことが可能である。
【符号の説明】
【０１１６】
１…復号装置、１０１…バス、１０２…演算装置、１０３…ＣＰＵ、１０４…主記憶装置、１０５…通信制御装置、１０６…外部記憶装置、１０６ａ…データ記憶部、１０６ｂ…設定情報記憶部、１０６ｃ…プログラム格納部、１０７…表示装置、ＮＷ…通信ネットワーク。
【図１】
2019208097.tif 000014
【図２】
2019208097.tif 000015
【図３】
2019208097.tif 000016
【図４】
2019208097.tif 000017
【図５】
2019208097.tif 000018
【図６Ａ】
2019208097.tif 000019
【図６Ｂ】
2019208097.tif 000020
【図７】
2019208097.tif 000021
【図８】
2019208097.tif 000022
【図９】
2019208097.tif 000023
【図１０】
2019208097.tif 000024
【図１１】
2019208097.tif 000025
【図１２】
2019208097.tif 000026
【図１３】
2019208097.tif 000027
【図１４】
2019208097.tif 000028
【図１５】
2019208097.tif 000029
【図１６】
2019208097.tif 000030
【図１７】
2019208097.tif 000031
【図１８】
2019208097.tif 000032
【図１９】
2019208097.tif 000033
【図２０】
2019208097.tif 000034
【図２１】
2019208097.tif 000035
【図２２】
2019208097.tif 000036
【図２３】
2019208097.tif 000037
【図２４Ａ】
2019208097.tif 000038
【図２４Ｂ】
2019208097.tif 000039
【図２５】
2019208097.tif 000040
【図２６】
2019208097.tif 000041
【図２７】
2019208097.tif 000042
【図２８】
2019208097.tif 000043
【図２９】
2019208097.tif 000044
【図３０】
2019208097.tif 000045
【図３１】
2019208097.tif 000046
【図３２】
2019208097.tif 000047
【図３３】
2019208097.tif 000048
【図３４】
2019208097.tif 000049