Analysis and Construction of Insertion/Deletion Correcting Codes

次世代情報ストレージとして注目されているDNAストレージやレーストラックメモリには同期誤りと呼ばれる誤りが生じうることが知られており，保存していた情報系列の一部が削除されたり，情報系列の途中に意図しないシンボルが挿入されうる．挿入削除訂正符号は同期誤りを訂正する基礎技術の一つであり，近年研究が盛んにされている．挿入削除訂正符号は，いわゆる普通の誤り訂正符号とは異なり，線型符号では十分な性能が得られず，非線型符号を用いる必要がある．線型符号についてはこれまでの符号理論の研究において様々な解析手法や構成法が与えられてきたが，非線型符号である挿入削除訂正符号については解析手法や設計法が十分に与えられていないのが現状である．本年度は，挿入削除訂正符号の解析と設計に関して，次の成果を得た．(1)古典的な挿入削除訂正符号は数論的符号と呼ばれるクラスに属しており，複数の合同式によって規定することができる．符号の性能指標のひとつに符号化率と呼ばれるものがあり，符号の符号語数から導出できることが知られている．本研究では，数論的符号に対して包括的に符号語数を導出する枠組みを与え，幾つかの特殊な符号に対して符号語数を陽に与えた．(2)量子挿入削除訂正符号は量子情報に対する挿入削除誤りを訂正可能な量子符号である．量子削除訂正符号の最初の構成法は2020年に与えられているが，複数個の挿入誤りを訂正可能な多元量子符号の構成法は明らかでなかった．本研究では，既存の符号である複数個の削除誤りを訂正可能な多元量子符号が複数個の挿入誤りも訂正可能であることを示し，その挿入訂正復号法を与えた．

次世代情報ストレージとして注目されているDNAストレージやレーストラックメモリには同期誤りと呼ばれる誤りが生じうることが知られており，保存していた情報系列の一部が削除されたり，情報系列の途中に意図しないシンボルが挿入されうる．挿入削除訂正符号は同期誤りを訂正する基礎技術の一つであり，近年研究が盛んにされている．挿入削除訂正符号は，いわゆる普通の誤り訂正符号とは異なり，線型符号では十分な性能が得られず，非線型符号を用いる必要がある．線型符号についてはこれまでの符号理論の研究において様々な解析手法や構成法が与えられてきたが，非線型符号である挿入削除訂正符号については解析手法や設計法が十分に与えられていないのが現状である．本年度は，挿入削除訂正符号の解析と設計に関して，次の成果を得た．(1)古典的な挿入削除訂正符号は数論的符号と呼ばれるクラスに属しており，複数の合同式によって規定することができる．符号の性能指標のひとつに符号化率と呼ばれるものがあり，符号の符号語数から導出できることが知られている．本研究では，数論的符号に対して包括的に符号語数を導出する枠組みを与え，幾つかの特殊な符号に対して符号語数を陽に与えた．(2)量子挿入削除訂正符号は量子情報に対する挿入削除誤りを訂正可能な量子符号である．量子削除訂正符号の最初の構成法は2020年に与えられているが，複数個の挿入誤りを訂正可能な多元量子符号の構成法は明らかでなかった．本研究では，既存の符号である複数個の削除誤りを訂正可能な多元量子符号が複数個の挿入誤りも訂正可能であることを示し，その挿入訂正復号法を与えた．