🔢 mathematics

On the equivalence between additive and linear codes

本論文は、加法符号が線形符号と等価かどうかを判定する決定論的テストを提案し、既報の四元加法符号の厳密な加法性を検証するとともに、既知の加法相補的直交符号が線形エルミート LCD 符号と等価であることを示すことで、その性能限界の向上に貢献しています。

原著者： Kanat Abdukhalikov, Duy Ho

公開日 2026-03-17

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Kanat Abdukhalikov, Duy Ho

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

この論文は、**「コード（情報の箱）」**という世界における、ある重要な「正体見抜き」の話をしています。

専門用語を一切使わず、日常の比喩を使って説明しましょう。

1. 物語の舞台：「コード」という箱

まず、**「コード」とは何か想像してください。
それは、メッセージを安全に送るための「特別な箱」**です。
この箱には、2 種類の作り方がありました。

リニア（線形）コード：
- 特徴：非常に整然としていて、ルールがシンプル。
- 例え：「レゴブロック」のように、決まった形（直線や平面）で組み立てられた箱。計算が簡単で、昔からよく使われていました。
アディティブ（加法）コード：
- 特徴：少し自由奔放で、複雑な形をしている。
- 例え：「粘土」や「自由な積み木」のように、レゴのルールには縛られない、もっと柔軟な箱。
- 最近の発見：実は、この「自由な箱（アディティブ）」の方が、同じ大きさなのに**「より多くの情報」を詰め込めたり、「より壊れにくい（エラーに強い）」**箱を作れることがわかってきました。

2. 問題：「偽物」を見抜くのは難しい

ここで大きな問題が起きました。
「自由な箱（アディティブ）」が作られると、**「実はこれ、レゴのルール（リニア）で作れる箱と同じじゃないか？」**という疑いが生まれます。

もし「自由な箱」が実は「レゴの箱」と同じなら、わざわざ複雑な作り方をしなくても、単純なレゴでいいことになります。
もし「自由な箱」が本当に「レゴにはない新しい形」なら、それは画期的な発見です。

これまでの研究では、この「正体見抜き」をするために、**「幾何学（図形）」**という難しい道具を使って、箱の形をひたすら眺めて判断していました。しかし、箱が大きくなると、この方法では「同じか違うか」を判断するのが非常に難しく、時間がかかりすぎていました。

3. 解決策：「魔法の検査キット」の開発

この論文の著者たちは、**「生成マトリクス（箱の設計図）」という、箱を作るための「レシピ」さえあれば、すぐに正体を見抜ける「新しい検査キット」**を開発しました。

このキットの仕組みは、とてもシンプルで論理的です。

設計図をスキャンする：
箱のレシピ（生成マトリクス）をスキャンします。
小さな部品をチェック：
箱を小さなブロック（2 つの数字のペア）に分けて、それぞれが「レゴのルール」に従っているかチェックします。もし、あるブロックが「レゴのルール」に合わない形をしていれば、**「これはリニア（レゴ）コードではない！」**と即座に判定できます。
「奇数」の魔法：
もしすべてのブロックが整っていても、さらに奥深くの計算（「核の次元」という難しい言葉を使いますが、ここでは**「隠れたパズルのピースの数」**と想像してください）を行います。
- もしその数が**「奇数」であれば、「これは絶対にレゴ（リニア）コードには変換できない！」**と確定します。
- もし「偶数」なら、まだ可能性がありますが、さらに詳しく調べる必要があります。

この方法は、**「幾何学（図形）」という重たい道具を使わず、「代数（計算）」**という軽やかな道具だけで、どんな箱でも瞬時にチェックできるのが最大の特徴です。

4. 実際の成果：「新しい箱」の発見と「偽物」の暴露

著者たちは、この新しい検査キットを使って、最近発表されたいくつかの有名な「自由な箱（アディティブコード）」をテストしました。

結果 A：「本当に新しい箱」だった
多くの箱は、検査の結果**「奇数」が出ました。つまり、これらは「レゴ（リニア）コードには変換できない、本当に新しい自由な箱」**であることが証明されました。これらは、これまでの「レゴ箱」よりも性能が良いことが確認できました。
結果 B：「実はレゴ箱だった」の発見
一方で、ある特定の箱（[22, 10, 9] というパラメータを持つ箱）を調べたところ、**「実はレゴのルールで作れる箱」**であることがわかりました。
- 驚きの展開：この箱は、これまで知られていた「レゴ箱」の記録を**「塗り替える」**ほど高性能でした。
- つまり、「自由な箱だと思っていたら、実はもっと高性能な『レゴ箱』の隠れた形だった」という発見ができました。これにより、レゴ箱の性能記録が更新されました。

まとめ

この論文は、以下のようなことを伝えています。

新しい検査キット：複雑な箱が「レゴ（リニア）」なのか「自由な箱（アディティブ）」なのかを、設計図（レシピ）だけで素早く見抜く方法を作った。
正体見抜き：これを使って、多くの「自由な箱」が本当に新しいものであることを証明した。
記録更新：逆に、ある「自由な箱」が実は高性能な「レゴ箱」だったことを発見し、レゴ箱の性能記録を更新した。

つまり、**「コードという箱の世界で、何が本当に新しいのか、何が隠れた天才なのかを、誰でも簡単に見分けられるようになった」**という画期的な研究なのです。

この論文「Additive and Linear Codes の等価性について（On the equivalence between additive and linear codes）」は、加法的符号（Additive codes）と線形符号（Linear codes）の関係を明確化し、特に「厳密に加法的である（線形符号と等価ではない）符号」を判定するための決定論的テストを提案した研究です。以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定

背景: 加法的符号は、特に量子誤り訂正符号の構成において、線形符号よりも優れた性能を示す可能性があるとして注目されています。しかし、既存の文献で報告されている多くの「加法的符号」が、実は線形符号と等価（モノミアル同値）であるのか、それとも本質的に線形符号とは異なる「厳密に加法的な符号」であるのかを区別することが困難でした。
課題: 新たな加法的符号が構築された際、それが既知の線形符号と等価かどうかを判定する確定的な方法が不足していました。従来の手法は主に幾何学的な技術（擬似弧や Desarguesian スプレッドなど）に依存しており、一般的な加法的符号に適用するには限界がありました。
目的: 符号の生成行列（Generator matrix）のみを用いて、加法的符号が線形符号と等価かどうかを判定する代数的手法を開発すること。

2. 手法と理論的枠組み

著者らは、有限体 $\mathbb{F}_{q^2}$ 上の加法的符号を $\mathbb{F}_q$ 上のベクトル空間として捉え、以下の代数構造に基づいた判定アルゴリズムを提案しました。

表現と定義:
- $\mathbb{F}_{q^2}$ の元を $\mathbb{F}_q$ 上の基底 $\{1, \omega\}$ を用いて表現し、符号を $\mathbb{F}_q$ 上の $2n$ 次元空間への写像 $\phi$ で表現します。
- 符号が線形符号と等価であるための必要十分条件は、符号の生成行列 $G$ に対して、ある可逆行列 $R$ とブロック対角行列 $A$ が存在し、 $RG = G(AM_\omega A^{-1})$ を満たすかどうかです（ここで $M_\omega$ は $\omega$ の companion 行列）。
判定アルゴリズム（Algorithm 1）:
1. ランクチェック: 生成行列をブロック列 $G_i$ に分割し、いずれかの $G_i$ のランクが 1 である場合、その符号は線形符号と等価ではないと判定します（Theorem 3.2）。
2. 零度（Nullity）テスト: 連立一次方程式系 $Sx=0 $を構成します（$ S $は$ G $から導出される行列）。この行列$ S$ の零度（nullity）が奇数である場合、その符号は線形符号と等価ではないと判定します（Theorem 3.3）。これは、線形符号と等価な場合、解空間の次元が偶数でなければならないという性質に基づいています。
3. 解空間の探索: 零度が偶数の場合、解空間から条件を満たす $R$ が存在するかを直接検索します。

3. 主要な貢献

決定論的テストの確立: 幾何学的な手法に依存せず、生成行列のみから加法的符号の線形性等価性を判定する純粋に代数的なアルゴリズムを提案しました。
理論的証明:
- 加法的符号が線形符号と等価であるための必要十分条件の定式化（Theorem 3.1）。
- 生成行列のブロック列のランクが 1 である場合の非等価性の証明（Theorem 3.2）。
- 導出行列 $S$ の零度が奇数であることが、符号が厳密に加法的であるための十分条件となることの証明（Theorem 3.3）。
既存研究の検証と改善: 提案されたアルゴリズムを計算機代数システム MAGMA を用いて実装し、既存の文献で報告された符号群に対して適用しました。

4. 結果

著者らは、主に 4 進（Quaternary, $q=2$ ）加法的符号に対して以下の検証を行いました。

Guan ら [14] の符号の検証:
- [14] で報告された多数の準巡回加法的符号（Table II および Table IV）について、アルゴリズムを適用しました。
- 結果、[14] の Table II にあるすべての符号、および Table IV の大部分の符号（最小距離が線形符号の限界を超えるもの）は、厳密に加法的（線形符号と等価ではない）であることが確認されました。
ACD 符号（Additive Complementary Dual）の発見と改善:
- [14] の Table IV にある特定の符号（パラメータ [22, 10, 9] $_2^2$ ）について、アルゴリズムのステップ 3（解空間の探索）により、これが線形 Hermitian LCD 符号と等価であることが示されました。
- この発見により、線形 Hermitian LCD 符号の既知の性能限界（[2] の Table 6）が改善されました。
Plotkin 和構成による符号の検証:
- [18] で報告された Plotkin 和構成を用いた 10 個の 4 進 ACD 符号について、すべてが厳密に加法的であることを確認しました（一部はランク条件、残りは零度テストまたは直接計算により判定）。

5. 意義

符号理論への寄与: 「加法的符号が線形符号を超える性能を持つ」という主張の正当性を、厳密な代数的手法で裏付けることができました。これにより、単にパラメータが良いだけでなく、本質的に新しい符号構造を持つことを証明する標準的な手法が提供されました。
実用的なツール: 研究者が新しい加法的符号を構築した際、それが既存の線形符号の単なる変形なのか、真に新しい符号なのかを効率的に判定できるツール（Algorithm 1）を提供しました。
量子符号への応用: 4 進加法的符号は量子誤り訂正符号の構築に不可欠です。本研究は、より高性能な量子符号を設計する際に、線形符号の枠組みを超えた真に新しい符号の探索を可能にする基盤となりました。

総じて、この論文は加法的符号と線形符号の等価性問題に対する長年の疑問に、明確な代数的解答を与え、既存の最良記録の更新と厳密な分類を両立させた重要な研究です。