リスト復号の質問計算量

スポンサーリンク

概要

論文の詳細を見る
本報告ではリスト復号の質問計算量について議論を行う.我々の主結果はリスト復号のために必要な質問回数の下界証明である.より詳しく言うと,あるδ=δ(κ)があって任意のq元符号C:Z^k_q→Z^n_qと任意の定数0<γ<1に対してもしε<1/((1+δ)(q-1))ならば,リストサイズをεq^<o(k)>にするためには,その符号のリスト復号器は受信語の少なくとも(1-γ)(1-H_q((1-1/q)(1-(1+δ)ε)))^<-1>k個のブロックを(乱択的かつ適応的な方法でも)参照する必要がある,ということを証明する.特にq=o(k ln k)ならばδ∈o(1)である.qとεがその条件を満たす場合,この下界は最良のリスト復号可能符号でのブロック長とほぼ一致しており,したがってこのようなパラメータ設定では受信語への局所的参照はリスト復号器が得る必要がある情報量について大きな優位性を持たない.
2012-04-20

著者

関連論文

もっと見る

スポンサーリンク