1 基本概念
对偶码是线性编码理论中的核心对象之一。它通过“正交”这一代数关系，把一个线性码与另一组在内积意义下与之兼容的码字联系起来。借助对偶码，可以更清晰地描述原码的结构、维数、检错能力以及校验关系，也为后续的矩阵表示和构造方法提供基础。
1.1 线性码的定义
线性码通常指有限域上一个定长向量空间的线性子空间。若在某个有限域上选定码长为 \(n\)，则码字可视为该域中 \(n\) 维向量，所有码字构成的集合若对加法与数乘封闭，就称为线性码。线性码的维数反映其信息容量，而最小距离则与纠错能力直接相关。
1.2 对偶码的定义
对偶码是与给定线性码在某种内积下全部正交的向量集合。对一个线性码而言，对偶码本身仍是线性码，并且常被记作原码的“伴随”对象。它不仅提供了与原码互补的代数结构，也常被用来构造校验矩阵和分析码的约束条件。
1.2.1 正交条件
若两个码字在所选内积下的结果为零，则称它们正交。对偶码中的任意码字都必须与原码中的每一个码字正交。这个条件把“合法码字”与“约束向量”区分开来，因此对偶码可理解为所有满足原码约束的线性关系集合。
1.2.2 内积的选取
最常见的是欧几里得内积，即对应位置逐项相乘后求和。在扩域或特定编码场景中，也可使用 Hermitian 内积等变体。内积形式不同，对偶码的具体内容也会改变，但“正交子空间”的基本思想保持一致。
1.3 对偶码的基本性质
对偶码继承了线性空间的诸多性质，因此在理论分析中非常方便。它与原码之间存在稳定的维数联系，也与双重对偶运算形成自然闭包关系。通过这些性质，可以把许多编码问题转化为线性代数问题。
1.3.1 线性子空间结构
对偶码是原空间中的一个线性子空间。若两个向量都与原码正交，那么它们的线性组合也仍与原码正交。正因如此，对偶码可以用矩阵、基、秩等工具进行描述和计算。
1.3.2 维数关系
在有限维向量空间中，原码与其对偶码的维数之和等于码长。若原码维数为 \(k\)，码长为 \(n\)，则对偶码维数为 \(n-k\)。这一关系是编码理论中最基本的公式之一，直接反映了信息维与校验维之间的互补性。
1.3.3 双重对偶码
对偶码再次取对偶后，得到的双重对偶码与原码一致。也就是说，在标准的线性码框架下，取对偶是一种“可逆”的操作。这个性质说明原码完全可以通过其正交约束恢复出来。
1.4 相关术语
对偶码理论中常会出现一些相近概念，虽然名称不同，但都与码字之间的正交关系有关。理解这些术语有助于区分不同语境下的表述方式。
1.4.1 伴随码
伴随码通常是对与某个码结构上对应的另一组码字的泛称。它强调二者之间的配对关系，而不一定局限于某种固定的记号体系。在不少教材中，它可作为对偶码的近义表达使用。
1.4.2 正交码字
正交码字是指在指定内积下彼此乘积和为零的两个码字。它们构成对偶关系的最基本单元。若一个码字与码中所有码字都正交，则它属于对偶码。
2 代数表示
对偶码的一个突出优点，是可以用矩阵语言直接表达。生成矩阵描述“码如何生成”，校验矩阵则描述“码需满足什么条件”，两者之间正好对应原码与对偶码的关系。
2.1 生成矩阵与校验矩阵
生成矩阵把码字表示为若干基向量的线性组合，而校验矩阵则通过线性方程约束码字。对偶码恰好与校验条件紧密相连，因此它在矩阵形式下非常自然。
2.1.1 生成矩阵的行空间
线性码的生成矩阵的行向量张成原码。换言之，原码就是生成矩阵行空间中的全部向量。这个表示法把抽象的码集合变成了可操作的矩阵对象。
2.1.2 校验矩阵与对偶码
校验矩阵的每一行都可以视作对原码施加约束的向量。其行空间往往正是对偶码，或与对偶码密切对应。若某个向量与生成矩阵的每一行都正交，那么它就是对偶码中的元素。
2.2 矩阵形式下的求法
在实际计算中，对偶码通常通过矩阵变换求出。常见做法是先把生成矩阵化为标准形式，再利用线性方程组求出正交空间的基。
2.2.1 标准形矩阵
将生成矩阵通过初等行变换化为标准形后，主元结构更清楚，便于识别自由变量与约束关系。此时可以直接写出与其正交的向量条件，从而构造对偶码的基。
2.2.2 消元与基的构造
通过高斯消元可将求对偶码转化为求解齐次线性方程组。解空间的基向量即构成对偶码的一组生成元。该方法简洁、通用，适用于多数有限域上的线性码。
2.3 维数公式
维数公式是理解对偶码最重要的代数结论之一。它把码的长度、维数和对偶关系联系起来，构成理论分析与实际计算的基础。
2.3.1 秩与余维
若生成矩阵秩为 \(k\)，则原码维数即为 \(k\)，而对偶码维数是余维 \(n-k\)。因此，秩越大，对偶码的自由度越小。这个结果在构造校验方程时尤为直观。
2.3.2 对偶空间视角
从向量空间的角度看，对偶码就是原子空间的正交补。线性代数中的“子空间—正交补”理论可直接迁移到编码理论中。这样一来，对偶码的许多性质都能通过空间分解来解释。
3 主要性质
对偶码的性质不仅反映其自身结构，也揭示了它与原码之间的深层联系。许多经典结论都围绕包含关系、距离特征以及特殊的自反结构展开。
3.1 与原码的关系
原码与对偶码并非独立存在，而是通过正交性紧密耦合。它们在空间上常呈现出互补、交叉或包含的关系，这些关系决定了编码的许多代数特征。
3.1.1 包含关系
若一个码包含于其对偶码，则称其具有自正交倾向。若一个码等于其对偶码，则形成更强的自对偶结构。包含关系在构造特殊码时很常见，也常作为设计约束使用。
3.1.2 交集与和空间
原码与对偶码的交集通常包含那些既属于原码又与原码全部正交的码字。两者的和空间则往往覆盖更大的子空间。通过分析交集与和空间，可以更细致地理解码的冗余和约束来源。
3.2 最小距离性质
最小距离是衡量码性能的关键指标。对偶码的最小距离既能反映其自身的纠错能力，也与原码的结构复杂度存在关联。
3.2.1 对偶码的最小距离
对偶码的最小距离是其非零码字重量中的最小值。这个数值决定了对偶码能识别的最少错误模式，也影响校验方程的有效性。对偶码最小距离越大，通常说明原码具有更强的约束分散性。
3.2.2 原码与对偶码的距离联系
原码与对偶码的最小距离并无简单恒等式，但二者常受彼此结构影响。某些特殊码族中，原码的稀疏性会体现在对偶码距离上，而对偶码的短距离也可能揭示原码中存在的低阶关系。
3.3 自正交与自对偶
自正交和自对偶是对偶码理论中最具代表性的特殊情形。它们常出现在结构对称性强的码族中，并在理论研究与构造实践里占据重要地位。
3.3.1 自正交码
若一个码包含于其对偶码，则称为自正交码。此时码中任意两个码字都正交，连自身也满足对应的内积条件。自正交码通常具有较强的代数约束，适合用于构造更复杂的编码结构。
3.3.2 自对偶码
若一个码与其对偶码完全相同，则称为自对偶码。这类码在维数上通常满足一半长度原则，因此具有高度对称性。自对偶码在组合设计和某些优化问题中也经常出现。
3.3.3 近自对偶码
近自对偶码是指与自对偶结构十分接近但并不完全相等的一类码。它们保留了部分对称特征，同时又具备更灵活的参数选择。该类码常被用于平衡结构美感与性能需求。
4 特殊类型的对偶码
不同类别的线性码在取对偶后会呈现出各自鲜明的结构特征。某些码族在对偶操作下保持同类性质，因而特别适合理论研究和工程应用。
4.1 循环码的对偶
循环码具有移位不变性，是最经典的线性码族之一。其对偶码通常也具有可描述的代数结构，因此便于分析和构造。
4.1.1 循环结构保持性
在许多情形下，循环码的对偶码仍是循环码。也就是说，对码字的循环位移不会破坏其对偶结构。这种保持性使得循环码及其对偶码可以用多项式语言统一处理。
4.1.2 生成多项式与校验多项式
循环码通常可由生成多项式描述，而对偶码则与相应的校验多项式相关联。二者之间存在明确的代数对应关系，借助多项式的互补因子，可以方便地求得对偶码。
4.2 迹码与对偶码
迹码常出现在扩域编码和域迹映射相关的构造中。它们的对偶关系往往依赖于底域与扩域之间的线性联系。
4.2.1 扩域上的对偶关系
在扩域上构造的码，其对偶关系不仅涉及向量正交，还会受到域扩张结构的影响。若编码环境允许使用迹映射等工具，则对偶码可通过扩域中的线性形式加以描述。
4.2.2 子域限制
把扩域上的码限制到较小子域后，对偶结构有时会发生变化。此时原先的对偶码未必直接保持不变，但仍可通过子域上的内积关系重新分析。该现象在跨域编码中较为常见。
4.3 二元码与 q 元码
按字母表大小区分时，二元码和一般 \(q\) 元码是两类基础对象。对偶码理论在这两种情形下都成立，只是具体计算与符号表达略有差异。
4.3.1 二元对偶码
二元码定义在只有两个元素的有限域上，是应用最广的一类线性码。其对偶码的计算通常较为直接，且在逻辑电路、存储系统等领域具有良好解释性。
4.3.2 一般有限域上的对偶码
在任意有限域上，线性码都可以定义对偶码。尽管域的大小不同会影响具体参数，但正交补、维数互补和双重对偶等基本规律保持成立。这使得对偶码成为统一不同编码体系的重要语言。
5 构造与计算
对偶码的构造既可以从理论定义出发，也可以借助具体矩阵进行计算。实际工作中，算法化处理非常常见，尤其适合处理高维码和复杂码族。
5.1 显式构造方法
显式构造强调直接给出对偶码的生成方式，而不是仅停留在抽象定义层面。常见思路包括从生成矩阵推导，或者依据校验条件反向建立码空间。
5.1.1 从生成矩阵构造
给定原码的生成矩阵后，可求其正交补，从而得到对偶码。具体做法是寻找与所有行向量都正交的向量集合，再从中选取一组基作为对偶码生成元。
5.1.2 从校验条件构造
若已知原码的校验关系，也可以直接把这些约束向量组织起来形成对偶码。由于校验矩阵的行空间与对偶码紧密对应，这种方法在工程实现中尤其方便。
5.2 算法求解
对偶码的求解本质上是线性代数问题，因此可用标准算法处理。随着码长增大，计算效率与存储需求也会变得重要。
5.2.1 线性代数算法
常用算法包括高斯消元、基变换和零空间求解等。它们可将“求正交补”转化为“解齐次方程组”，从而直接输出对偶码的一组基。
5.2.2 计算复杂度
对偶码的计算复杂度主要取决于矩阵规模和所处有限域的运算代价。对于中小规模问题，常规消元已足够；而在大规模应用中，则更需要优化的矩阵算法和结构化表示。
5.3 示例计算
通过具体示例可以更直观地理解对偶码的定义与求法。简单例子能展示基本过程，经典码例则能说明理论在实际码族中的典型表现。
5.3.1 小维数码示例
设一个小维数线性码由少量基向量生成，则其对偶码可通过逐项正交条件直接列方程求出。此类示例通常便于手算，适合说明“正交补”的具体含义。
5.3.2 常见经典码示例
许多经典码，如某些循环码、汉明码及其相关变体，都有明确的对偶结构。通过分析这些例子，可以观察到生成矩阵、校验矩阵与对偶码之间的对应关系如何在经典场景中体现。
6 应用
对偶码不仅是纯代数对象，也在信息传输、密码学和离散结构研究中具有实际价值。它帮助人们从约束和冗余两个方向理解编码系统。
6.1 纠错编码
在纠错编码中，对偶码常用于分析检错条件和构造译码方法。它把“哪些错误能被发现”转化为线性关系的判定问题。
6.1.1 检错能力分析
若接收到的向量与对偶码中的某些校验向量不满足正交条件，则可判断原始传输中可能出现了错误。对偶码距离越大，通常越容易发现较复杂的错误模式。
6.1.2 译码中的应用
译码过程里，对偶码对应的校验方程常用于计算综合征。综合征可以快速指示错误类型或错误位置，从而显著减少直接搜索的成本。
6.2 密码学中的相关角色
在一些密码学研究中，对偶码用于描述结构特征、辅助分析参数分布，并帮助理解码类方案中的代数约束。它更多扮演分析工具而非独立机制。
6.2.1 结构分析
对偶码可以揭示原码内部是否存在低重量关系、稀疏约束或对称性。这类信息有助于研究者判断某种编码结构是否过于规则，进而影响方案设计。
6.2.2 安全性辅助工具
在某些基于编码的密码系统中，对偶码用于评估潜在的结构泄露风险。通过检查对偶空间的性质，可辅助判断参数选择是否过于“整齐”或可预测。
6.3 组合设计与有限几何
对偶码与组合设计、有限几何之间存在丰富联系。码的行空间和正交结构常可对应到块设计、点线关系等离散对象。
6.3.1 设计构造
某些对偶码的码字支持集可与设计理论中的块结构相联系。借助这种对应，可以从编码参数推出设计参数，或者反向由设计构造特定码。
6.3.2 几何解释
在有限几何中，线性码的对偶关系可解释为子空间之间的正交配对。码字可视为几何对象，而对偶码则刻画与之垂直或互补的几何方向。
7 相关扩展
对偶码的概念并不局限于标准欧几里得线性码框架。随着编码理论的发展，它逐渐扩展到更一般的内积、更复杂的代数环境以及更广泛的研究领域。
7.1 对偶码的推广
在非线性码和其他更一般的编码体系中，人们也尝试定义类似“对偶”的对象。虽然形式不完全相同，但其核心仍是寻找某种互补约束。
7.1.1 非线性码的对偶概念
对于非线性码，传统线性代数意义下的对偶不再直接适用，但可以通过关联的生成结构或距离关系建立类比概念。这类推广常用于比较不同码的结构性质。
7.1.2 不同内积下的对偶
除欧几里得内积外，还可以在特定背景下引入加权内积、Hermitian 内积等。不同内积会导出不同的对偶码，适合处理不同域结构和对称性要求。
7.2 伴随理论与泛化
伴随理论关注各种“对应空间”之间的关系。对偶码可以看作这一思想在编码理论中的典型体现，并可进一步推广到其他代数对象。
7.2.1 欧几里得对偶
欧几里得对偶是最常见、最基础的对偶形式，通常基于标准逐项乘积求和。它适用于大多数经典线性码，是入门和应用中的首选模型。
7.2.2 Hermitian 对偶
Hermitian 对偶使用带共轭的内积，常见于扩域上的编码研究。与欧几里得对偶相比，它更适合处理具有域自同构结构的情形，因此在某些构造中更自然。
7.3 研究历史
对偶码的发展与编码理论整体演进密切相关。它从早期的线性代数方法出发，逐渐扩展到更复杂的构造和跨学科应用。
7.3.1 早期编码理论发展
早期编码理论主要关注如何通过冗余提高可靠传输，而对偶关系很快成为分析校验方程的重要工具。随着线性码系统化研究的深入，对偶码逐步被视为独立而基础的对象。
7.3.2 现代应用拓展
进入现代以后，对偶码不再局限于通信场景，而是广泛进入计算机科学、组合数学和密码学研究之中。其理论价值与应用价值相互促进，形成了持续发展的研究方向。