疎シュタイナー三重系および関連する組合せ構造の性質とその存在の解明

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

昨年度に引き続き、組合せデザイン論および極値集合論において長年未解決であるr-sparse予想において存在が予想されている特殊なシュタイナー三重系(以下STSと呼ぶ)の存在性を調べるとともに、関連する組合せ構造がもつ情報科学への新しい応用に関して研究成果を得た。これまで様々な研究者により、反復復号を行う際のLDPC符号がもつ誤り訂正能力や、消失耐性符号の消失復旧能力は、符号内部に現れる特殊な組合せ構造と強い関連があることが指摘されていた。STSにおけるr-sparse性も符号と関連ずる特殊な内部構造の代表例である。本研究ではアリゾナ州立大学計算機科学科のColbourn教授と共同で、STSの結合行列をLDPC符号の検査行列に利用する際に問題となる、stopping setと呼ばれる内部構造の大きさについて調べた。ここでは、組合せデザイン論において回避問題と呼ばれる問題の、これまでにない新しい一般的解決法のひとつを発見することを通して、自明でないSTSが必ずもつstopping setの大きさについて上限式を与えた。また内部に存在する最小のstopping setが比較的大きな場合について、確率的手法を用いることで、部分的STSの最大ブロック数に対する下限を導いた。これらの成果により、どのような三重系をLDPC符号に用いるかについて検討ずる際のひとつの指針を与えたほか、三重系における回避問題おいても進展がみられた。さらに我々は、Vermont大学計算機科学科のLing教授と共同で、集積回路などに対するスキャンテストに利用される、X-符号について組合せ論的な視点から研究を行つた。X-符号と、疎構造に代表される特殊な内部構造との間の関係について、我々は昨年度に得た符号語数の上限式を改良するとともに、新たにtranslation-free systemという概念を導入することで、畳み込み式圧縮回路の理論的構成法を与えた。