Covering Sequences and Covering-Sequences Codes

技術要約：被覆シーケンスおよび被覆シーケンス符号

問題提起
本論文は、$(n, R)_q$-被覆シーケンス（CS）および$(n, m, R)_q$-被覆シーケンス符号（CSC）の構成について扱っている。$(n, R)_q$-被覆シーケンスとは、アルファベット $\Sigma_q$ 上の長さ $\ell$ の巡回シーケンスであり、その連続する $n$ 個のタプルが $(n, R)_q$-被覆符号（すべての単語が $\Sigma_q^n$ 内の符号語からハミング距離 $R$ 以内にある集合）を形成するものである。主な目的は、このようなシーケンスの長さを最小化することである。

本論文ではまた、集団としての連続する $n$ 個のタプルが $(n, R)_q$-被覆符号を形成する、長さ $m$ の $M$ 個の巡回シーケンスの集合として定義される $(n, m, R)_q$-CSCという概念を導入している。本論文は、これらの被覆符号が短い被覆シーケンスを構築するための基本的な構成要素として機能すると主張している。先行研究（具体的には[3]）は、小さな半径を持つバイナリシーケンス（$q=2$）に焦点を当てていたが、本研究はこれらの概念を非バイナリ・アルファベット（$q > 2$）およびより大きな半径へと一般化することを目的とし、特に $m > n$ である場合のCSCの構造的な役割を強調している。

手法
核となる手法は、「Construction MC」（Merging Cycles：サイクルの結合）と呼ばれる構成法に基づいている。このプロセスは、$(n, m, R)_q$-CSCからの符号語の集合を、単一の巡回被覆シーケンスへと変換するものである：

1. 拡張（Extension）： 長さ $m$ の各符号語 $c$ は、末尾に最初の $n-1$ 個の記号を付加することで、長さ $m+n-1$ に拡張される。
2. 結合（Merging）： 拡張された符号語は、あるものの接尾辞が次のものの接頭辞と重なるように順序付けられる。
3. 連結（Concatenation）： 重複部分を取り除き、残りのセグメントを連結して、単一の巡回シーケンス $S$ を形成する。
   本論文は、元の符号語の集合が $(n, m, R)_q$-CSCを形成する場合、得られるシーケンス $S$ は $(n, R)_q$-CSになることを証明している。

本論文は、以下の特定の代数構造を用いてこの構成を適用している：

• バイナリの場合 ($q=2$)： 長さ $n=2^r-1$、半径 $R=1$ の巡回ハミング符号 $H_2(r)$ を利用する。また、「自己双対シーケンス」（補集合に対して不変なシーケンスであり、$[X, \bar{X}]$ で表される）の集合も用いており、これらは $n=2^r$ において準完全被覆符号を形成する。
• 非バイナリの場合 ($q > 2$)： 有限体 $\mathbb{F}_q$ への一般化を行う。標準的なハミング符号 $H_q(r)$ は必ずしも巡回的ではないため、本論文では**定数巡回符号（constacyclic codes）**を利用している。$H_q(r)$ が定数巡回符号として表現可能であることを示し、これによりConstruction MCの適用を可能にしている。
• インターリービング（Interleaving）： より大きな半径（$R > 1$）に対処するため、既存の巡回符号のパリティ検査行列をインターリービングすることを提案している。具体的には、$R$ 個のパリティ検査行列 $H$ をインターリーブすることで、新しい符号が得られ、その半径は $R \cdot r_{old}$ となり、長さもそれに応じてスケールされる。これは、半径2以上を持つシーケンスを構築するためにハミング符号に適用される。

主要な貢献および結果

1. 非バイナリ・アルファベットへの一般化： 本論文は、被覆シーケンスの理論をバイナリから任意の素数冪アルファベット（$q > 2$）へと拡張している。ハミング符号 $\mathbb{F}_q$ 上のものが、結合サイクル構成を容易にするために定数巡回符号として扱えることを確立している。
2. 最適性因子：
   • $n=2^r$ および $R=1$ のバイナリシーケンスにおいて、自己双対シーケンスを用いることで、最適サイズに対して1.25の範囲内の被覆シーケンスが得られる。
   • $\mathbb{F}_q$ 上の $n = \frac{q^r-1}{q-1}$ および $R=1$ の非バイナリシーケンスにおいて、構築されたシーケンスは理論的な下界（球面被覆界）に対して$\frac{q}{q-1}$の範囲内にある。
   • 半径 $R=2$ の場合、ハミング符号のパリティ検査行列のインターリービングは、下界に対して小さな定数因子（特定のパラメータに応じて2または4の因子）の範囲内のシーケンスを生成する。
3. 退化したシーケンスの構造： 「退化した」シーケンス（周期がその長さよりも小さいもの）を分析している。バイナリ・ハミング符号については、長さ $2^r-1$ のすべての退化した単語が符号語であることを証明している。しかし、この特性は非バイナリの定数巡回表現には単純には一般化されないことを指摘しており、非バイナリケースにおける退化した軌道の正確なカウントをさらなる分析のための未解決領域としている。
4. 新しい符号族： 特に $m > n$ であるような（例：自己双対シーケンスや定数巡回表現を用いる）特定の $(n, m, R)_q$-CSCの族を構築し、これらが被覆シーケンスの効率的な構成要素であることを論じている。

意義および主張
本論文は、被覆シーケンス符号（CSC）が「巡回被覆符号と被覆シーケンスの間の架け橋」であり、特に符号の総長が最適に近い場合において、今後の研究の主要な焦点となるべきであると主張している。

本研究の意義は以下の通りである：

• $(n, R)_q$-CS および $(n, m, R)_q$-CSC に関する、$q > 2$ における最初の体系的な解説を提供したこと。
• 代数符号理論（特にハミング符号、ネガサイクリック符号、および定数巡回符号）が、非バイナリ・アルファベットであっても、最適に近い被覆シーケンスを構築するために効果的に活用できることを示したこと。
• パリティ検査行列のインターリービングを通じて、相対的に短いシーケンス長を維持しながら、被覆半径を増加させる手法を導入したこと。

著者らは、構築されたシーケンスは最適性の範囲内で小さな定数因子内に収まっているものの、特に大きな半径についてはさらなる改善が可能であると謙虚に述べている。彼らは、これらの計算式（正確な数の巡回シーケンス（軌道）を計算するための簡略化された式）や、非バイナリ定数巡回表現における軌道の周期に関するより完全な分析など、いくつかの未解決問題を特定している。