2元線形ブロック符号に対するグレブナ基底を用いた最尤復号法の計算量

摘要

本稿では,著者によって提案されているグレブナ基底を用いた最尤復号法について議論する。 この最尤復号法は軟判定ならびに硬判定に適用することができるが,どちらの場合においても計算量の評価はなされていなかった。この最尤復号法の計算量はグレブナ基底の個数によって決まるので,本研究ではグレブナ基底の個数の上界を与える。