2025-11-19T11:49:14.147379

On codes induced from Hadamard matrices

Hurley
Unit derived schemes applied to Hadamard matrices are used to construct and analyse linear block and convolutional codes. Codes are constructed to prescribed types, lengths and rates and multiple series of self-dual, dual-containing, linear complementary dual and quantum error-correcting of both linear block {\em and} convolutional codes are derived.
academic

On codes induced from Hadamard matrices

基本信息

  • 论文ID: 2410.24027
  • 标题: On codes induced from Hadamard matrices
  • 作者: Ted Hurley (University of Galway)
  • 分类: cs.IT math.IT (Information Theory)
  • 发表时间: 2024年10月（v2: 2025年11月17日）
  • 论文链接: https://arxiv.org/abs/2410.24027

摘要

本文将单位导出方案（unit derived schemes）应用于Hadamard矩阵，用于构造和分析线性分组码和卷积码。论文构造了具有指定类型、长度和码率的编码，并导出了多个系列的自对偶码、包含对偶码、线性互补对偶码以及量子纠错码，涵盖线性分组码和卷积码两大类。

研究背景与动机

研究问题

  1. 卷积码构造的代数方法缺失：正如McEliece等人指出的，卷积码缺乏通用的代数构造和设计方法，这极大限制了其规模和可用性。
  2. 特定类型码的系统化构造：需要构造满足特定属性的编码（自对偶、包含对偶、LCD码等），并能够控制其长度、距离和码率。
  3. 量子纠错码的构造：需要通过经典编码理论（如CSS方法）构造量子纠错码。

研究重要性

  • 理论意义：为编码理论提供统一的代数构造框架
  • 实际应用：
    • LCD码可用于抵御侧信道攻击和故障攻击
    • 自对偶码和包含对偶码可构造量子纠错码
    • 卷积码在通信系统中广泛应用（如Viterbi算法解码）

现有方法局限

  • Walsh-Hadamard码虽然有很好的距离特性，但码率极低（1/2^k）
  • 缺乏从Hadamard矩阵系统化构造不同类型码的通用方法
  • 卷积码的构造长期依赖计算机生成，缺乏代数理论支撑

研究动机

本文扩展了作者在27中提出的单位导出方法，将其应用于Hadamard矩阵，实现：

  • 同时构造线性分组码和卷积码
  • 构造到指定类型、长度和码率
  • 获得可计算的距离界
  • 从单个Hadamard矩阵生成多个编码

核心贡献

  1. 理论框架：建立了基于Hadamard矩阵的单位导出编码构造理论，证明了5个核心命题（Propositions 2.1-2.5）
  2. 算法设计：提出4个通用构造算法：
    • Algorithm 1: 构造任意码率r/n的LCD线性分组码
    • Algorithm 2: 构造长度2n的自对偶线性分组码
    • Algorithm 3: 构造长度n的自对偶卷积码
    • Algorithm 4: 构造码率r/n（r≥n/2）的包含对偶卷积码
  3. 多类型码的统一构造：从同一Hadamard矩阵可构造LCD、自对偶、DC和量子纠错码
  4. 距离分析：提供了距离的代数计算方法，卷积码距离可达线性分组码的两倍
  5. 具体应用：给出H(20)、H(28)等多个具体案例，构造了大量新的编码

方法详解

任务定义

输入：n×n Hadamard矩阵H，满足HH^T = nI_n，元素为±1 输出：

  • 线性分组码：n,r,d_q码（长度n，维度r，最小距离d，域GF(q)）
  • 卷积码：(n,k,δ;μ,d_f)_q码（长度n，秩k，度δ，记忆μ，自由距离d_f）

约束条件：

  • 域的特征p满足p∤n（对大多数构造）
  • 对于自对偶卷积码需要i=√(-1)在域中存在
  • 矩阵的秩条件

核心方法架构

1. 线性分组码构造（基础方法）

将Hadamard矩阵分块：H = (A/B)，其中A为r×n矩阵

关键性质：

(A/B)(A^T  B^T) = nI_n

在域GF(p)（p∤n）中，这变为：

AA^T + BB^T = 0 (mod p)
即 AB^T = 0

结果：

  • A生成一个n,r码
  • B^T是校验矩阵
  • B生成对偶码

2. LCD码构造（Proposition 2.1）

定理：对于H = (A/B)，若p∤n，则A生成LCD码

证明要点：

  • AB^T = 0 ⟹ B生成A的对偶码
  • H可逆 ⟹ A的行不能是B的行的非平凡组合
  • 因此 C∩C^⊥ = 0（LCD性质）

3. 自对偶线性分组码（Proposition 2.2）

构造：G = (I_n, αH)，其中α满足1+α²n=0

关键计算：

(I_n, αH)(I_n / αH^T) = I_n + α²nI_n = (1+α²n)I_n

当1+α²n=0时：

  • (I_n / αH^T)是秩为n的校验矩阵
  • K = (I_n, αH)生成对偶码
  • 因此码是自对偶的

实现细节：

  • α可能在GF(p)或其二次扩张GF(p²)中
  • 生成器矩阵直接以系统形式给出

4. 自对偶卷积码（Proposition 2.3）

构造：H = (A/B)，n=2m，A和B各m×n

定义生成矩阵：

G(z) = A + iBz，其中i=√(-1)

验证自对偶性：

G(z)(iB^T + A^Tz) = (A+iBz)(iB^T+A^Tz)
                   = 0 + nI_m·z - nI_m·z + 0 = 0

因此H^T(z) = iB^T + A^Tz是校验矩阵，H(z^(-1))z = A+iB生成对偶码

非灾难性验证：

(A+iBz)A^T = nI_m

因此G(z)有右多项式逆，码是非灾难性的

距离计算：

d_f = d(A) + d(B)

5. 包含对偶卷积码（Proposition 2.4）

构造：H = (A/B)，A为r×n，B为(n-r)×n，r>n-r

定义：

B_1 = (0_{t×n} / B)，其中t=2r-n
G(z) = A + iB_1z

验证DC性质：

  • 构造校验矩阵H^T(z) = iB^T + C_1z
  • 对偶码生成器：C_1^T + iB
  • 验证对偶码包含在原码中

技术创新点

  1. 矩阵分块策略：通过不同的分块方式从同一Hadamard矩阵获得不同类型的码
  2. 参数控制：通过选择行数r实现码率控制（r/n）
  3. 域扩张技巧：利用√(-1)的存在性构造卷积码
  4. 距离可计算性：利用Hadamard矩阵的正交性代数计算距离
  5. 统一框架：线性分组码和卷积码的构造方法统一

实验设置

数据集（Hadamard矩阵）

本文使用多个尺寸的Hadamard矩阵：

  • 小尺寸：H(12), H(20), H(24), H(28)
  • 中等尺寸：H(36), H(40), H(72)
  • 大尺寸：H(144)

矩阵类型：

  • Paley-Hadamard矩阵（用于尺寸12k）
  • 非可分Hadamard矩阵（优先使用）

评价指标

  1. 码长n：编码的长度
  2. 维度/秩r或k：信息位数量
  3. 码率：r/n（线性分组码）或k/n（卷积码）
  4. 最小距离d：纠错能力的度量
  5. 记忆μ：卷积码的记忆长度
  6. 自由距离d_f：卷积码的距离度量

计算工具

  • GAP计算机代数系统及其包：
    • Guava包：编码理论计算
    • Gauss包：有限域上的矩阵运算
  • 用于：子矩阵操作、有限域计算、距离验证

实现细节

  • 域选择：主要使用GF(3), GF(5), GF(7)及其扩张GF(3²), GF(5²)
  • 秩计算：在模p意义下计算矩阵秩
  • 距离计算：
    • 小长度（≤100）：计算机直接计算
    • 大长度：使用代数方法（Proposition 2.6, Lemma 2.18）

实验结果

主要结果

1. 从H(20)构造的码

类型参数域说明
LCD20,13,4₃, 20,7,6₃GF(3)线性互补对偶码
自对偶卷积(20,10,10;1,12)₃₂GF(3²)距离12
DC卷积(20,13,7;1,8)₃₂GF(3²)包含对偶
量子码长度20, 距离8, 码率6/20GF(3²)通过CSS构造
自对偶20,10,8₅GF(5)线性分组码
自对偶卷积(20,10,10;1,14)₇₂GF(7²)距离14
自对偶40,20,12₃GF(3)系统形式

2. 从H(28)构造的码

类型参数域
LCD28,16,6₃, 28,12,9₅GF(3), GF(5)
自对偶卷积(28,14,14;1,12)₃GF(3)
DC卷积(28,18,10;1,8)₃GF(3)
量子码长度28, 距离8, 码率8/28GF(3)
自对偶卷积(28,14,14;1,16)₅GF(5)
自对偶28,14,9₇GF(7)

3. 三元码的极值性质

对于H(12k)的Paley-Hadamard矩阵：

  • 构造自对偶12k, 6k, d₃码
  • 验证结果：对于k=1,2,3,4,5（即n=12,24,36,48,60），构造的码达到最优距离
  • 理论上界：d ≤ ⌊n/12⌋+3
  • n=72及以上不存在极值码

关键发现

1. 距离性能

卷积码 vs 线性分组码：

  • 例如H(12)：
    • 线性分组码A：12,6,6
    • 卷积码G(z)=A+iBz：距离d_f=12
    • 卷积码距离是线性分组码的2倍

2. 码率灵活性

  • 可构造任意码率r/n（0<r<n）的LCD码
  • 自对偶码：码率固定为1/2
  • DC卷积码：码率r/n，r≥n/2

3. 秩性质（Lemma 2.7）

对于p|n（p≠2）的素数：

rank(H) ≤ n/2 在GF(p)中

验证：Paley-Hadamard矩阵H(12k)在GF(3)中秩恰好为6k

具体案例分析

Prototype Example 2.9: H(12)详解

矩阵分解：H = (A/B)，A和B各6×12

应用1：自对偶线性分组码（GF(3)）

  • 在GF(3)中：AA^T = 0（因为3|12）
  • A生成12,6,6₃自对偶码
  • 最优性：达到理论最优距离
  • 纠错能力：可纠正2个错误

应用2：LCD码（GF(5)）

  • A生成12,6,6₅ LCD码
  • B生成对偶码，也是12,6,6₅

应用3：自对偶卷积码（GF(5)）

  • G(z) = A + 2Bz（2=√(-1) in GF(5)）
  • 参数：(12,6,6;1,12)₅
  • 距离：d_f = d(A) + d(B) = 6+6 = 12
  • 非灾难性：(A+2Bz)A^T = 6I₆ = I₆

应用4：长度24自对偶码（GF(5²)）

  • 需要α²=2，x²-2在GF(5)上不可约
  • 在GF(5²)中：(I₁₂, αH)生成24,12,8₅₂自对偶码

应用5：长度24自对偶码（GF(7)）

  • α=2满足1+12α²=0 in GF(7)
  • (I₁₂, 2H)生成24,12,8₇自对偶码

Example 2.10: 高记忆卷积码

从H(12)构造记忆3的卷积码：

A = H[1..3][1..12]
B = H[4..6][1..12]
C = H[7..9][1..12]
D = H[10..12][1..12]
G(z) = A + Bz + Cz² + Dz³

参数：(12,3,9;3,24) 距离：24（因为所有子矩阵距离为6）

大规模应用

Example 2.11: 大长度码

  • H(72): 72,36,18₃自对偶码
  • H(144): 144,72,d₃码

Example 2.15: H(36)

  • 36,18,12₃自对偶码（GF(3)）
  • (36,18,18;1,d)₅自对偶卷积码（GF(5)）
  • 量子纠错码：长度36，距离d

相关工作

编码理论基础

  1. 经典教材：
    • Blahut 1: 数据传输的代数码
    • MacWilliams & Sloane 4: 纠错码理论
    • McEliece 3: 信息与编码理论
  2. 卷积码理论：
    • Johannesson & Zigangirov 2: 卷积编码基础
    • Rosenthal等35,36,38: MDS卷积码
    • Bocharova等12: 对偶卷积码

特殊类型码

  1. LCD码：
    • Massey 30,31: 首次引入LCD码概念
    • Carlet等15-17: LCD码的现代研究
    • 应用：侧信道攻击防御18,19
  2. 自对偶码：
    • Mallows & Sloane 29: 自对偶码上界
    • Pless 33: GF(3)上的对称码
    • Mallows等37: GF(3)上的自对偶码
  3. 量子纠错码：
    • Calderbank & Shor 14: CSS构造
    • Calderbank等13: GF(4)上的量子码
    • Steane 39: 简单量子纠错码

Hadamard矩阵

  • van Lint & Wilson 5: 组合学基础
  • Horadam 6: Hadamard矩阵及其应用（专著）

单位导出方法（作者前期工作）

  • Hurley & Hurley 8,9,22-25: 单位导出方法的发展
  • Hurley 27: 最终线性分组和卷积码（本文基础）
  • Hurley 26,28: MDS码构造

本文相比相关工作的优势

  1. 统一框架：首次统一处理线性分组码和卷积码
  2. 代数构造：解决McEliece提出的卷积码代数构造缺失问题
  3. 多类型码：从单个矩阵构造多种类型码
  4. 可计算距离：提供代数距离计算方法
  5. 大规模可行：可构造大长度、高码率的码

结论与讨论

主要结论

  1. 理论贡献：
    • 建立了基于Hadamard矩阵的编码构造完整理论框架
    • 证明了5个核心命题，提供了4个通用算法
    • 统一了线性分组码和卷积码的构造方法
  2. 构造能力：
    • 可构造任意码率的LCD码
    • 可构造自对偶、DC、量子纠错码
    • 从单个Hadamard矩阵获得多个不同类型的码
  3. 性能优势：
    • 卷积码距离可达线性分组码的2倍
    • 三元码在小长度达到极值性质
    • 大长度、高码率可实现

局限性

  1. 域的限制：
    • 大多数构造要求p∤n
    • 自对偶卷积码需要√(-1)存在
    • 某些构造需要域扩张
  2. 距离计算：
    • 大长度情况下距离难以精确计算
    • 依赖代数方法和计算机验证
    • 某些情况只能给出估计
  3. Hadamard矩阵依赖：
    • 需要预先知道Hadamard矩阵的显式表达
    • 非可分Hadamard矩阵性能更好但构造困难
    • Hadamard猜想未解决限制可用尺寸
  4. 高记忆卷积码：
    • 论文主要关注记忆1的情况
    • 高记忆情况留待后续研究（仅给出Example 2.10）
  5. 实际应用验证：
    • 缺少实际通信系统中的性能测试
    • 解码复杂度分析不充分

未来方向

  1. 理论扩展：
    • 高记忆卷积码的系统化构造
    • 其他类型正交矩阵的应用
    • 非二进制域上的深入研究
  2. 距离改进：
    • 更精确的距离界
    • 达到Singleton界的MDS码构造
    • 渐近性质分析
  3. 应用拓展：
    • 实际通信系统实现
    • 量子计算中的应用
    • 密码学应用
  4. 计算优化：
    • 高效解码算法
    • 并行实现
    • 硬件友好设计

深度评价

优点

  1. 理论创新性强：
    • 首次系统化地将Hadamard矩阵用于构造多类型码
    • 解决了卷积码代数构造的长期难题
    • 单位导出方法的创新应用
  2. 方法统一性好：
    • 线性分组码和卷积码统一处理
    • 不同类型码（LCD、自对偶、DC）统一框架
    • 从理论到算法到应用的完整链条
  3. 实用价值高：
    • 提供明确的构造算法
    • 可实现任意码率和长度
    • GAP系统易于实现
  4. 实验充分：
    • 多个尺寸的Hadamard矩阵
    • 多种有限域（GF(3), GF(5), GF(7)及扩张）
    • 详细的原型示例（Example 2.9）
  5. 写作清晰：
    • 结构层次分明
    • 定义、命题、算法、应用逻辑清晰
    • 数学推导严谨

不足

  1. 理论完备性：
    • p|n情况的处理不够系统
    • 高记忆卷积码理论不完整
    • 某些命题的证明过于简略（如Proposition 2.3的距离证明）
  2. 实验局限：
    • 缺少与现有最优码的系统比较
    • 距离计算主要依赖计算机（长度≤100）
    • 缺少解码性能实验
  3. 应用指导不足：
    • 如何选择合适的Hadamard矩阵？
    • 不同应用场景下的参数选择策略？
    • 解码复杂度分析缺失
  4. 可复现性：
    • 未提供代码或具体实现
    • 某些Hadamard矩阵的构造未说明
    • GAP实现细节不够
  5. 比较分析：
    • 与Walsh-Hadamard码的详细比较不足
    • 与其他代数构造方法的对比缺失
    • 性能-复杂度权衡分析不够

影响力

  1. 学术贡献：
    • 为编码理论提供新的构造工具
    • 推动Hadamard矩阵在编码中的应用
    • 可能引发后续系列研究
  2. 实用价值：
    • 量子纠错码构造有实际应用潜力
    • LCD码在安全领域有应用价值
    • 大长度码的构造满足现代通信需求
  3. 可复现性：
    • 理论方法清晰可复现
    • 需要GAP系统支持
    • 具体实现需要一定工作量
  4. 局限性：
    • 依赖Hadamard矩阵的存在性
    • 某些构造需要域扩张
    • 实际系统应用需要进一步验证

适用场景

  1. 理论研究：
    • 编码理论的代数构造方法研究
    • Hadamard矩阵的应用研究
    • 量子信息理论
  2. 实际应用：
    • 量子通信：量子纠错码构造
    • 安全通信：LCD码抵御侧信道攻击
    • 数据存储：高码率纠错码
    • 无线通信：卷积码应用
  3. 教学用途：
    • 编码理论课程的案例
    • 代数方法在编码中的应用示例
    • Hadamard矩阵的应用教学
  4. 不适用场景：
    • 需要极高码率（>0.9）的应用
    • 对解码复杂度极其敏感的场景
    • 需要软判决解码的应用

参考文献（关键文献）

  1. 3 McEliece: 信息与编码理论经典教材，指出卷积码代数构造缺失问题
  2. 6 Horadam: Hadamard矩阵及其应用的权威专著
  3. 13,14 Calderbank & Shor: CSS量子纠错码构造的开创性工作
  4. 27 Hurley: 本文的理论基础，最终线性分组和卷积码
  5. 31 Massey: LCD码的开创性工作
  6. 35,38 Rosenthal等: MDS卷积码的重要研究

总体评价：这是一篇理论创新性强、方法系统完整的优秀论文。作者成功地将Hadamard矩阵与单位导出方法结合，建立了构造多类型编码的统一框架，特别是解决了卷积码代数构造的难题。论文的主要价值在于提供了从理论到算法到应用的完整方法论，具有较强的学术意义和应用潜力。主要不足在于高记忆卷积码理论不完整、实际应用验证不足。建议后续工作加强实际系统实现和性能测试。