1 基本概念
1.1 定义
线性分组码是分组码的一种，同时满足线性码的代数性质。它将长度固定的一段信息符号映射为同样长度的码字，并要求全部码字构成某个有限域向量空间中的线性子空间。由于这种结构，线性分组码既便于分析，也便于构造和译码。
从功能上看，这类码的主要任务是为信息增加冗余，使接收端能够检测并纠正传输过程中产生的错误。与非线性分组码相比，线性分组码通常可以借助矩阵工具进行描述，因此在工程实现中应用十分广泛。
1.2 线性分组码的构成
线性分组码的基本构成包括信息部分与冗余部分。编码时，原始信息被分成若干固定长度的组，每组经过一定规则转换后生成码字。码字通常由信息符号和为检错纠错而加入的附加符号共同组成。
这种构成方式的核心在于：冗余并非随意附加，而是按照线性关系生成，使码字满足预定的代数约束。这样一来，即使码字在传输中遭到扰动，接收端仍可利用这些约束判断原信息是否发生错误。
1.2.1 码字
码字是编码后得到的合法符号序列，也是线性分组码中的基本元素。所有合法码字共同组成一个码空间，任一码字都应满足该码的线性条件。
在实际系统中，码字不仅承载原始信息，还包含用于恢复和校验的冗余信息。码字之间的距离关系直接影响该码的纠错性能，因此码字的设计是分组码理论中的关键内容。
1.2.2 信息符号与冗余符号
信息符号是待传输或待存储的原始数据，冗余符号则是为了增强可靠性而加入的附加数据。在线性分组码中，冗余符号通常由信息符号通过线性变换得到，而不是独立随机生成。
信息符号决定了码字所承载的有效内容，冗余符号则负责建立可检验的结构约束。两者结合后，编码既保持了信息完整性，也提升了抗错能力。
1.3 码参数
线性分组码通常用若干基本参数描述，包括码长、维数和最小距离。这些参数共同刻画了码的长度、信息承载能力以及纠错性能。
不同参数之间存在明显权衡：码长增加通常意味着冗余提高，维数与编码效率则可能下降，而最小距离增大往往会带来更强的纠错能力。因而，码参数的选择需要兼顾性能与开销。
1.3.1 码长
码长是指一个码字包含的符号总数，通常记为 n。它决定了编码后每个数据块的长度，也是设计通信与存储协议时的重要尺度。
在固定码长条件下，码字中的一部分位置用于承载信息，其余位置用于冗余校验。码长越大，设计空间通常越丰富，但实现复杂度也可能随之提高。
1.3.2 维数
维数表示码空间中独立信息的个数，通常记为 k。对于线性分组码而言，维数直接对应可承载的原始信息长度，因此它反映了码的有效载荷能力。
若将码看作向量空间，维数越高，说明可表示的信息组合越多；但在码长固定时，维数增大通常意味着冗余减少，检测和纠错能力可能相应下降。
1.3.3 最小距离
最小距离是任意两个不同码字之间的最小汉明距离，通常记为 d。它是衡量码性能的核心指标之一，决定了可检测和可纠正错误的范围。
对于线性分组码，最小距离也等于所有非零码字的最小汉明重量。该性质使得最小距离可以通过考察码空间内部结构来求得，便于理论分析。
1.4 线性性与分组性
线性性指码字集合对加法和数乘封闭，即若两个码字属于该码，它们的线性组合仍属于该码。分组性则指信息按固定长度分块处理，每一块独立编码，适合逐块传输和逐块恢复。
这两种性质相结合，使线性分组码既保留了严格的代数结构，又适应实际系统的分帧、分块操作。正因如此，它成为经典编码理论中的基础类型之一。
2 数学基础
2.1 有限域与向量空间
线性分组码通常建立在有限域上。有限域中的元素数量有限，但仍可像普通数域一样进行加法和乘法运算，从而为编码提供代数环境。
在这一框架下，长度为 n 的符号序列可以视为向量空间中的向量，码则是其中的子空间。由此，编码问题可转化为线性代数问题进行处理。
2.1.1 有限域上的线性代数
有限域上的线性代数包含向量、矩阵、线性变换和秩等概念。线性分组码的生成矩阵、校验矩阵及其相关运算，均依赖这些基础工具。
由于域的大小有限，很多运算都可通过枚举或矩阵消元完成。这使得线性分组码在理论上清晰、在实现上也相对可操作。
2.1.2 子空间与维数定理
码空间作为向量空间的子空间，其维数由独立生成元的数量决定。维数定理说明，子空间之间的维数关系与整个空间的结构相互制约，这对于理解生成矩阵和校验矩阵尤为重要。
在线性分组码中，码空间的维数与校验空间的维数通常相加等于总长度 n。这个关系是构建和分析线性分组码的基础。
2.2 汉明距离与汉明重量
汉明距离用于度量两个等长序列在对应位置上的差异个数，而汉明重量则表示单个序列中非零符号的个数。二者在纠错编码中占据中心地位。
线性分组码的纠错能力与最小汉明距离直接相关，因此汉明度量不仅是数学定义，也是一种性能刻画工具。
2.2.1 距离度量
距离度量用于判断两个码字或两个向量相差多少。汉明距离是最常见的一种，它直观反映了符号错误的数量。
在离散信道模型中，若传输发生少量符号翻转，汉明距离较大的码通常更容易将受损码字与其他合法码字区分开来。
2.2.2 错误模式表示
错误模式是指传输过程中发生错误的位置与形式，可用一个误差向量来表示。接收端收到的序列可视为原码字与误差向量的叠加结果。
这种表示方法便于分析错误检测与纠正过程。通过比较接收序列与合法码空间之间的关系，可以推断误差是否存在，以及误差可能出现在哪里。
2.3 生成矩阵与校验矩阵
生成矩阵和校验矩阵是线性分组码最重要的两种矩阵表示方式。前者用于生成全部码字，后者用于判定序列是否满足码约束。
二者从不同角度描述同一个码：生成矩阵强调“如何构造”，校验矩阵强调“如何验证”。它们在编码、译码和理论分析中都非常常用。
2.3.1 系统形式生成矩阵
系统形式生成矩阵是一种特殊排列方式的生成矩阵，其中通常包含一个单位矩阵和一个附加矩阵。该形式便于直接看出信息位与校验位的对应关系。
采用系统形式后，编码过程更直观，信息符号可直接嵌入码字的固定位置，冗余符号则由矩阵运算自动生成。这种形式在工程中非常常见。
2.3.2 校验方程
校验方程由校验矩阵导出，用于描述所有合法码字必须满足的线性约束。若一个向量与校验矩阵相乘后得到零向量，则它可以视为合法码字。
校验方程不仅可用于错误检测，也可在译码时帮助定位异常。它们构成了综合、综合表和其他代数译码方法的基础。
3 码的构造
3.1 直接构造方法
直接构造方法是指根据目标参数和代数条件，显式设计码空间或矩阵表示。与依赖特定递推规则的方法相比，这类方法更强调从结构上满足要求。
在实际应用中，直接构造可根据需要选择不同思路，例如从代数对象出发，或通过矩阵显式给出生成关系。
3.1.1 代数构造
代数构造通常利用有限域、多项式环或特定代数结构来建立码。通过选择满足条件的代数元素，可生成具有预定性质的码字集合。
这类方法的优点是理论性强，往往能够得到参数较为规整、性质明确的码。其适合用于研究与标准化设计。
3.1.2 矩阵构造
矩阵构造直接给出生成矩阵或校验矩阵，然后由矩阵运算定义全部码字。只要矩阵满足秩和约束关系，就能形成合法的线性分组码。
这种方法直观、便于实现，也容易与计算机程序结合，因此在工程设计和算法验证中很常见。
3.2 常见线性分组码
在众多线性分组码中，有几类结构简单、性质典型的基础码。它们既可独立使用，也常作为更复杂编码方案的组成部分。
这些典型码能够说明线性分组码的基本思想，并帮助理解纠错能力与冗余设计之间的关系。
3.2.1 重复码
重复码通过将同一信息符号重复多次形成码字。它的结构最为简单，译码时可依据多数表决判断原始信息。
虽然重复码的冗余较大、效率不高，但其原理清晰，常用于教学示例和对基本纠错思想的说明。
3.2.2 单校验码
单校验码在信息后附加一个校验符号，使整个码字满足某种简单的奇偶约束。它能够有效检测单个比特错误，并对某些错误模式提供基础识别能力。
这种码的实现成本低，常见于需要轻量级校验的场景。尽管纠错能力有限，但其设计简洁，应用历史较长。
3.2.3 汉明码
汉明码是一类经典的单错误纠正码，具有较高的理论代表性。它通过精心设计的校验关系，使接收端能够定位并修正单个符号错误。
汉明码在参数选择上有明确规则，常被视为线性分组码中结构最典型、分析最方便的例子之一。
3.3 循环码与其关系
循环码是线性分组码的重要分支，其码字在循环位移下仍保持合法性。由于具有额外的代数对称性，循环码在构造和译码方面具有较强优势。
许多线性分组码都可与循环结构建立联系，尤其是在多项式表示下，这种联系更加明显。
3.3.1 循环结构
循环结构要求码字经过一次循环位移后仍属于同一码。这个性质使码字之间存在规则的代数关系，也便于利用多项式工具进行处理。
循环性带来的对称结构，常使编码器和译码器实现更高效，尤其适用于硬件电路设计。
3.3.2 多项式表示
在多项式表示中，码字被看作有限域上某个多项式的系数序列。循环位移则对应多项式乘法与模运算，从而将问题转化为代数环上的运算。
这种表示方法使循环码的生成和校验更为简洁，也便于寻找生成多项式与检查多项式。
4 编码与译码
4.1 编码过程
编码过程是将信息转换为合法码字的步骤。对于线性分组码而言，这一过程本质上是线性映射，输入信息块经过矩阵运算后形成输出码字。
编码的目标不是改变信息内容，而是为其附加结构化冗余，从而在后续传输中提高可靠性。
4.1.1 信息到码字的映射
信息到码字的映射要求每个信息块对应唯一的码字。在线性分组码中，这一映射通常由生成矩阵实现，因此具有可计算、可重复的特点。
由于映射保持线性，输入的叠加关系会被保留到编码结果中，这有助于分析整体系统行为。
4.1.2 系统编码
系统编码是指码字中直接包含原始信息符号的一种编码方式。这样，接收端在无需完全恢复全部结构的情况下，也能直接读取信息部分。
系统编码通常把信息位放在固定位置，其余位置由校验关系计算得到。由于便于实现和调试，这种方式在实际系统中应用广泛。
4.2 译码过程
译码是接收端根据收到的序列推断原始信息或原始码字的过程。由于信道可能引入错误，译码往往需要结合校验关系、距离准则和概率模型进行判断。
译码的质量直接决定编码系统的最终性能，因此它与编码设计同等重要。
4.2.1 误差检测
误差检测的目的是判断接收序列是否仍符合码的约束。若不满足校验条件，则说明传输过程中很可能发生了错误。
检测并不一定能给出错误位置，但它可以作为进一步纠错的前提步骤，为后续处理提供依据。
4.2.2 误差纠正
误差纠正是在检测到异常后，尝试恢复原始码字的过程。其基本思路是根据最接近合法码字的原则，寻找最可能的发送结果。
纠正能力取决于码的最小距离和译码算法。对于设计良好的线性分组码，少量错误往往可以被可靠修复。
4.2.3 最大似然译码
最大似然译码以概率最大为准则，在已知信道模型时选择最可能的发送码字。若信道满足对称且独立的错误模型，它通常等价于最小距离译码。
这种译码方法理论上性能优良，但计算复杂度可能较高，因此实际应用中常需结合近似算法或结构化码来降低开销。
4.3 译码算法
译码算法是把理论译码准则转化为可执行步骤的具体方法。不同算法在复杂度、性能和适用范围上各不相同。
在工程中，算法选择通常由码的结构、信道特征和实现资源共同决定。
4.3.1 综合译码
综合译码利用校验矩阵计算接收序列的综合，即判断其是否满足校验方程。综合的非零结果表明存在错误，并可据此推断误差类型。
该方法特别适合结构明确的线性分组码，因为综合与错误模式之间常有对应关系，便于查表或规则推断。
4.3.2 代数译码
代数译码利用码的代数结构直接求解错误位置或错误值。它常见于循环码、汉明码等具有明显代数特征的码类。
这类方法通常比穷举搜索更高效，尤其适合特定类型的码。但其适用性依赖于码的结构是否足够规整。
4.3.3 软判决与硬判决
硬判决译码只利用接收符号的最终判定结果，例如“0”或“1”；软判决译码则进一步使用符号的可信度或概率信息。后者通常能提供更好的性能。
在相同码和信道条件下，软判决往往优于硬判决，但实现复杂度也更高。因此，实际系统会在性能和成本之间作出权衡。
5 性能分析
5.1 纠错能力
纠错能力是评价线性分组码的重要指标，反映了码在噪声环境下恢复原始信息的能力。它与最小距离密切相关，并受译码策略影响。
一般而言，纠错能力越强，系统可靠性越高，但所需冗余也往往更多。
5.1.1 可检错位数
可检错位数指码能够稳定发现错误的最大错误数量。若错误数不超过某一范围，接收端通常可以确认码字已被破坏。
检错能力通常高于纠错能力，因为检测只需判断“是否异常”，而纠错还要进一步确定“正确内容是什么”。
5.1.2 可纠错位数
可纠错位数指码能无歧义恢复的最大错误数量。对于最小距离为 d 的线性分组码，通常可纠正不超过 \(\lfloor (d-1)/2 \rfloor\) 个符号错误。
这一数值是设计编码系统时的重要参考，也是判断某种码是否适合特定信道环境的关键依据。
5.2 码率与冗余度
码率描述编码前后有效信息所占比例，而冗余度则反映为可靠性所额外付出的代价。二者是一对相互关联的指标。
高码率意味着信息效率较高，低码率则通常带来更强的保护能力。具体选择取决于应用场景对可靠性与带宽的要求。
5.2.1 编码效率
编码效率通常可理解为信息符号占总码长的比例。若维数为 k、码长为 n，则码率常记作 k/n。
编码效率越高，单位传输中承载的有效信息越多；但若冗余不足，抗错能力可能下降。因此，效率与鲁棒性之间常需平衡。
5.2.2 冗余开销
冗余开销是指为了提高可靠性而增加的额外符号数量。它是线性分组码区别于简单原始传输的重要特征。
适量冗余能够显著改善传输质量，但过多冗余会降低吞吐率并增加资源消耗。实际设计中需要根据系统要求进行优化。
5.3 距离界
距离界是关于码参数之间关系的不等式或限制，用于说明在给定长度和维数条件下，最小距离不可能无限增大。它们是编码理论中的基本工具。
通过这些界，可以判断某个码是否接近理论极限，也可以评估某类码的参数优劣。
5.3.1 汉明界
汉明界给出了码长、维数和最小距离之间的经典限制关系。它说明了在固定长度下，较大的纠错能力必然伴随一定的信息损失。
这一界在编码设计中具有指导意义，可用于检验参数组合的可行性。
5.3.2 谷德曼界
谷德曼界从另一个角度约束线性码的参数，尤其适用于分析维数与最小距离的平衡关系。它给出了构造高性能码时的重要理论下限。
该界常用于比较不同码族的优劣，并评估某些构造是否接近最优。
5.3.3 斯鲁普界
斯鲁普界也是描述线性码参数限制的重要界之一，尤其在研究某些特殊码类时常被提及。它通常比一般性的粗略估计更细致。
在理论分析中，这类界帮助研究者了解码结构的可能上限与不可达区域。
6 重要性质
6.1 对偶码
对偶码是与原码在正交关系下对应的另一组码。它在分析校验结构、推导参数关系和研究权分布时非常重要。
原码与对偶码之间存在紧密联系，许多性质可以通过对偶关系相互转化。
6.1.1 对偶空间
对偶空间由与原码中所有向量都正交的向量组成。若把原码视为一个子空间，则对偶码正对应其正交补。
这一概念使校验矩阵的理解更加自然：校验矩阵的行空间往往就是对偶码的一个生成集合。
6.1.2 对偶码的参数关系
原码与对偶码的维数之和等于总长度，这是最基本的参数关系之一。除此之外，两者的最小距离和权分布也存在一定联系。
这些关系使得研究原码时常可借助对偶码的性质获得补充信息，尤其在证明和构造中作用明显。
6.2 权分布
权分布描述码中不同汉明重量的码字数量，是刻画码内部结构的重要统计信息。它不仅反映码字的分散程度，也与译码性能相关。
权分布越均匀或越符合特定规律，往往越便于分析其误差性能和对偶关系。
6.2.1 重量枚举函数
重量枚举函数用代数形式汇总不同重量码字的数量，是权分布的生成工具。通过它可以更紧凑地表达码的结构特征。
这一函数常用于证明与比较不同码的性质，也为进一步推导恒等式提供基础。
6.2.2 MacWilliams恒等式
MacWilliams恒等式描述了原码与对偶码的重量枚举函数之间的精确关系。它说明对偶结构不仅在维数上相关，在权分布上也具有可转换性。
该恒等式是编码理论中的经典结果，常用于从已知码的权分布推导对偶码的权分布。
6.3 自对偶码
自对偶码是指其与对偶码完全一致的线性码。它在结构上具有高度对称性，因此在理论研究中非常受关注。
由于自对偶码同时满足原码和对偶码的条件，它往往具有特殊的参数限制和良好的代数性质。
6.3.1 定义与判定
若一个码与其对偶码相同，则称为自对偶码。判定时需要同时检查维数条件与正交条件是否成立。
自对偶码通常要求码空间恰好等于自身的正交补，因此只有在特定参数下才可能存在。
6.3.2 典型性质
自对偶码常具有较强的结构对称性，在权分布、最小距离和构造方式上都有特殊表现。某些自对偶码还能与格、模形式等更高阶对象建立联系。
在基础编码理论中，它们常被用作研究对称结构与最优参数之间关系的典型对象。
7 应用
7.1 通信系统
线性分组码在通信系统中应用最为广泛，主要用于提升信号在噪声环境中的可靠传输能力。它们能够在发送端加入校验信息，在接收端帮助识别和修复错误。
由于其结构清晰、实现成熟，这类码长期以来都是信道编码的重要组成部分。
7.1.1 信道编码
信道编码通过在发送前增加冗余，降低传输错误对信息的影响。线性分组码是其中的基础方案之一，常与调制和解调环节协同使用。
在实际系统中，信道编码可以显著改善误码率，使有限带宽条件下的通信更加稳定。
7.1.2 抗干扰传输
当信道中存在噪声、衰落或其他随机扰动时，线性分组码能够增强系统的抗干扰能力。接收端通过检测和纠错机制，减少错误数据直接进入上层应用。
这类能力对于远距离通信、无线链路和低信噪比环境尤其重要。
7.2 存储系统
在线性分组码的帮助下，存储系统可以在介质出现局部损坏或读写误差时，尽可能恢复原始数据。其作用不仅体现在传输阶段，也体现在静态数据保护中。
从磁盘到闪存，纠错编码几乎是可靠存储的标准配置之一。
7.2.1 纠错存储
纠错存储是指利用编码机制在读出错误发生后自动恢复数据。线性分组码可用于块存储、条带化存储以及多级校验方案。
当存储介质出现单点或少量比特异常时，这些码能够帮助系统避免数据不可逆丢失。
7.2.2 可靠性提升
通过引入冗余校验，存储系统的容错水平可以明显提高。即使局部区域受损，系统也往往能通过译码重建有效数据。
这种机制延长了设备可用寿命，也降低了由偶发错误带来的维护成本。
7.3 计算机科学中的应用
线性分组码在计算机科学中不仅用于通信与存储，还常出现在数据校验、分布式系统和可靠计算等场景中。其思想是用代数结构提高系统的可验证性和容错性。
由于实现简单且适合软件与硬件协同，相关方法具有较强的普适性。
7.3.1 数据校验
数据校验利用编码规则检查文件、报文或内存块是否被破坏。线性分组码可以把校验过程统一到矩阵运算或综合计算中，便于自动化处理。
这一类应用常见于传输协议、文件系统和缓存一致性检查中。
7.3.2 可靠计算
在可靠计算中，编码思想可用于降低错误结果传播的风险。通过对中间数据进行冗余表示，系统能够在局部故障出现时维持一定的计算正确性。
这类方法在高可靠硬件、并行计算和容错软件设计中具有一定价值。