Analysis and Construction of Insertion/Deletion Correcting Codes

插入/删除校正码的分析与构造

基本信息

批准号：
22K11905
负责人：
野崎隆之
金额：
$ 2.66万
依托单位：
Yamaguchi University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

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

众所周知，在DNA存储和赛马场记忆中可能发生称为同步错误的错误，这些错误在下一代信息存储中引起了人们的注意，并且可以删除存储的信息系列的一部分，也可以在信息系列中间插入意外符号。插入和删除校正代码是纠正同步错误的基本技术之一，近年来研究一直在越来越受欢迎。与所谓的普通误差校正代码不同，线性代码不能提供足够的性能，并且必须使用非线性代码。在先前关于代码理论的研究中，已经对线性代码进行了各种分析方法和构造方法，但是当前的情况是，分析方法和设计方法尚未足够针对非线性代码，插入和删除校正代码。今年，我们在插入和删除校正代码的分析和设计中取得了以下结果。（1）经典插入和删除校正代码属于称为数字理论代码的类，可以通过多个一致表达式来定义。代码的性能指标之一称为编码率，众所周知，它可以从CodeWord的代码字数中得出。在这项研究中，我们给出了一个以全面的数值代码来得出代码字的框架，并明确给了多个特殊代码的代码字。（2）量子插入和删除校正代码是量子代码，可以纠正插入和删除错误以获取量子信息。构建量子缺失校正代码的第一种方法是在2020年给出的，但是尚不清楚如何构建可以纠正多个插入误差的多个量子代码。在这项研究中，我们已经表明，可以纠正现有代码的多个删除误差的多个量子代码也可以纠正多个插入错误，并且我们给出了插入校正解码方法。