Pat
J-GLOBAL ID：201403081223434342
線形符号におけるLP復号器及び整数解計算方法及びプログラム
Inventor：
,
,
Applicant, Patent owner：
,
Agent (3)：
伊東 忠重
, 伊東 忠彦
, 石原 隆治
Gazette classification：特許公報
Application number (International application number)：2011129334
Publication number (International publication number)：2012257108
Patent number：5574340
Application date： Jun. 09, 2011
Publication date： Dec. 27, 2012
Claim (excerpt)：
【請求項1】 対象となるアルファベットを2値{0,1}とし、該{0,1}上の確率分布P、n×k行列A,及びシンドロームu∈{0,1}kが与えられたとき長さnの2値系列x∈{0,1}nを
(但し、記号argは右辺のmaxを達成する
を左辺のxとして出力することを意味する)
として与える線形符号の最適な整数解を求める最尤復号器であって、
前記式(1)の緩和問題を線形計画法によって解く線形計画問題処理手段と、
拘束条件とする座標数をλとして、前記2値系列のn個の座標xのうち、λ個をランダムに選択し、
実行可能領域を前記線形計画問題処理手段により得られた目的関数fの最適値から所定の値までを一定間隔εで等分した各領域をスライス領域として、一の前記スライス領域について、
前記選択したλ個の座標xをそれぞれ0もしくは1に設定した一の場合について、
前記選択したλ個の座標x以外の(n-λ)個の座標のうちの一の座標xを対象として、当該座標xに0もしくは1を代入し、前記式(1)の緩和問題における実行可能解が存在するか否かを線形計画法によって判定し、
実行可能解が存在する場合には、当該座標xを前記代入した値に設定した上で、前記(n-λ)個の座標のうちの他の座標xを対象として同様の判定を実行し、
実行可能解が存在しない場合には、前記選択したλ個の座標xをそれぞれ0もしくは1に設定した他の場合について同様の判定を実行し、
前記選択したλ個の座標xをそれぞれ0もしくは1に設定したいずれかの場合について、全ての前記(n-λ)個の座標に対して実行可能解が存在すると判定された場合に、各座標xを前記代入した値に設定して、前記式(1)の緩和問題を線形計画法によって解き、前記目的関数fの最適値を与える各座標xが全て整数値ならば、当該各座標xを整数解として出力し、それ以外の場合はその時点で得られた非整数解を記憶手段に格納し、
他の前記スライス領域について同様の処理を実行し、すべての前記スライス領域について該処理を実行した時点でも整数解が得られない場合には、それまでに該記憶手段に格納されている解を出力する判別アルゴリズム実行手段と、
を有することを特徴とするLP復号器。
IPC (2)：
H03M 13/19 ( 200 6.01)
, H03M 13/39 ( 200 6.01)
Cited by examiner (5)
-
線形計画法復号のための座標上昇法
Gazette classification：公表公報
Application number：特願2010-519952
Applicant：ヒューレット-パッカードデベロップメントカンパニーエル.ピー.
-
符号化装置、符号化方法および符号化プログラム
Gazette classification：公開公報
Application number：特願2008-175734
Applicant：日本電信電話株式会社, 国立大学法人東京大学
-
シンボルから成るブロックを復号するための多段復号器及び方法
Gazette classification：公開公報
Application number：特願2009-277535
Applicant：ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド
Show all
Article cited by the Patent：
Return to Previous Page
