削除訂正符号の限界解明

点击翻译按钮获取中文摘要

挿入・削除に対する誤り訂正問題に対し，与えられたアルファベットサイズ，符号長，訂正半径（最小 Levenshtein 距離）に対し，どの程度大きな符号を構成できるかという符号の存在性問題に取り組んだ．可能性と不可能性の両方面から新しい限界式または評価値を明らかにすることを目指した．可能性に関する結果として，通常の Hamming 距離に関してグラフ理論を用いたアプローチ（グラフの独立数問題に帰着）が有効であり，Turan の定理や，Caro-Wei 限界を用いた符号サイズの下界式を数値的に評価した．さらに，挿入削除球サイズのタイトな上界式が改善につながるため，上界式の数え上げにおいて重複を減らした式を導出し，新たな下界式を示した．これらの限界式ならびに関連研究である Sala ら (ISIT2014) が示した下界式を，アルファベットサイズ q = 2, 4 で評価した．符号長は 10-40 程度，最小距離は 4以上について数値を導出したが，ある程度の範囲では今回導出した下界式が最も良い性能を示した．Sala らの限界式は，論文においては既存のどの限界式よりも優れているとの主張であったが，数値評価したところ，Levenshtein (ISIT2002) が示した下界よりも劣る場合があることが明らかになった．新たに導出した下界式は，漸近的には Levenshtein (ISIT2002) の下界式に一致するため，数値計算でしか改善を示すことができなかった．上界式についても，球充填上界やリスト復号可能性を利用した Elias タイプの上界式について評価した．訂正半径がある程度以上であれば，Elias タイプの上界が最も良い性能を示した．