2.2 线性分组码

差错控制编码理论与实践中最常用的信道编码是定义在有限域上的码。假设信源的输出是有限域GF(2)上连续的二元符号序列，称为信息序列。通常把信息序列中的二元符号称为信息比特。在分组码中，信息序列被划分为固定长度的消息分组，每一个消息分组含有k个信息比特，所以一共有2k个不同的消息。在信道编码器中，每个输入消息u=(u0, u1, · · ·, uk-1)，其含有k个信息比特，按照一定的编码规则被编码成长为n的二进制序列c=(c1, c2, · · ·, cn-1)，其中n＞k。序列c称为消息序列u的码字。码字中的二进制数字被称为码比特。因为有2k个不同的消息，对应有2k个码字，所有码字的集合构成一个(n, k)分组码。其中，参数n称为码长，k称为码的维数或消息长度，由编码器产生的n-k个添加到每个输入消息中的比特称为冗余比特。比率R=k/n称为码率，可以解释为每一个码比特所携带的平均信息比特数。

在分组码中，最重要的一类是线性分组码。如果一个码C的码字形成GF(q)上的一个向量空间，我们就说这个码是线性码。如果q＞2，那么称码C为多元或q元码。

2.2.1 线性分组码的定义与最小汉明距离

定义2.2 一个二元(n, k)线性分组码C是GF(2)上所有n维向量组成的向量空间V的一个k维子空间，它包含有2k个码字。

在任何线性码中，都包含一个作为向量空间原点的全零码字。

令c=(c0, c1, · · ·, cn-1)是GF(2)上的n维向量。c的汉明重量（Hamming weight）（简称重量），记为w(c)，它表示c中非零元素的个数。现在考虑一个码字符号在GF(2)上的(n, k)线性分组码C。对0≤i≤n，让Ai表示C中汉明重量为i的码字数。数A0, A1, · · ·, An称为C的重量分布。显然，A0+A1+· · ·+An=2k。由于线性分组码里有且仅有一个全零码字，因此A0=1。码C的最小汉明重量，记为wmin(C)，是C中非零码字的最小重量，即

令v和w是GF(2)上的两个n维向量。v和w之间的汉明距离，记为d(v, w)，表示v和w相应位置元素不相同的元素个数。对于线性码，dH(v, w)=d(0, w-v)=d(0, c)=w(c)。

(n, k)线性分组码C的最小距离dmin(C)定义为C中两个不同码字之间的最小汉明距离，即

可以很容易证明，C的最小距离dmin(C)等于C的最小重量wmin(w)：

因此，对于线性分组码，确定其最小距离就等价于确定其最小重量。一般来说，采用硬判决译码的纠错性能由其最小距离决定，而采用软判决最大似然译码的纠错性能则由码重量分布决定。

2.2.2 生成矩阵和校验矩阵

因为一个二元(n, k)线性分组码C是GF(2)上所有n维向量组成的向量空间的一个k维子空间，所以C中存在k 个线性独立的码字g0, g1, · · ·, gk-1，使得C中每个码字c是这k个线性独立码字的线性组合，即

其中ui∈GF(2)。

可以把C中k个线性独立的码字g0, g1, · · ·, gk-1作为一个GF(2)上的k×n矩阵的行向量，表示如下：

令u=(u0, u1, · · ·, uk-1)是待编码的消息。这个消息的对应码字c=(c0, c1, · · ·, cn-1)可用u和G的矩阵乘积表示为

因此，消息u的码字c是矩阵G的行向量的线性组合。矩阵G称为(n, k)线性分组码C的生成矩阵。

二元(n, k)线性分组码C是GF(2)上所有n维向量组成的向量空间V的一个k维子空间。它的零空间（或对偶空间）记为Cd，是V的一个n-k维子空间：

Cd是一个二元(n, n-k)线性分组码，称为C的对偶码。

通常，生成矩阵G可以经过线性变换转化成如下的系统形式：

其中，Ik为一个k×k的单位矩阵，P为一个k ×(n-k)的矩阵，pi, j∈GF(2)。由系统矩阵G编出的码被称为系统码，其中的码字具有图2.2所示的结构，码字的第一部分包含k个原来的信息符号，第二部分为包含n-k个校验符号的冗余校验部分。如果一个线性分组码有上述结构，那么称它为线性系统码（linear systematic code）。

令u=(u0, u1, · · ·, uk-1)是一个待编码的消息。根据式(2.11)和式(2.13)，可得到对应的系统码字：

其中n个码比特为

及

式(2.15)表示码字c最左边的k个码比特与k个待编码的信息比特u0, u1, · · ·, uk-1是完全一致的。式(2.16)表示c最右边的n-k个码比特是信息比特的线性组合。这n-k个由信息比特线性求和得到的码比特称为一致校验比特（简称校验比特）。由式(2.16)给出的n-k个等式称为码的校验方程。式(2.13)的生成矩阵形式称为系统形式。

除上述的定义方法之外，一个(n, k)线性分组码C还可以由其校验矩阵H完全定义。假定H的维数是m，其中m≥n-k。矩阵G和H的关系为

当且仅当c · HT=0（n-k维全零向量）时，二进制n维向量c∈V是C中的码字，即

H称为C的校验矩阵，C称为H的零空间（null space）。因此，一个线性分组码可以由两个矩阵唯一确定，即生成矩阵和校验矩阵。后面介绍的LDPC码通常是基于校验矩阵定义的，而Polar码是基于生成矩阵定义的。如果线性分组码的校验矩阵H的秩和它的行数相等，那么就说其是满秩的。但是在很多情况下，(n, k)线性分组码的校验矩阵并不是满秩的，即它的行数大于其行秩n-k。在这种情况下，校验矩阵H的一些行是n-k个线性独立的行的线性组合。这些额外的行称为冗余行。我们将在第3章介绍LDPC码，它的校验矩阵不一定是满秩的。

如果(n, k)线性分组码C的生成矩阵是形如式(2.13)的系统形式，那么对应的系统形式的校验矩阵如下。

很容易证明G·HT=0。有些文献中，将系统形式的生成矩阵表示为G=[P Ik]，则对应的校验矩阵为H=[In-kP T]。一般二元线性分组码的H矩阵是GF(2)上的(n-k)×n矩阵：

例2.1 令n=7, k=4，考虑系统形式的(7,4)线性分组码。消息向量u=(u0, u1, u2, u3)，码字c=(c0, c1, c2, c3, c4, c5, c6)=(u0, u1, u2, u3, c4, c5, c6)。系统形式的生成矩阵和校验矩阵为

这样，分组码。

2.2.3 对一个线性码简单修改而构造新码

假定C是一个已有的(n, k)线性分组码，可以对其进行简单修改而得到一个新码。这些方法很简单，但很实用，在编码系统设计中经常用到。

（1）扩展码（extending a code）：通过对C中的码字增加校验符号而增加码长（或者说获得码长更长的新码），这对应于增加生成矩阵的列。例如，对Hamming码增加一个全校验位就得到扩展Hamming码。

（2）删余码（puncturing a code）：通过将C中码字的一些校验符号删去（或者说进行打孔）而减少码长，从而得到码率更高的码。这对应于删掉生成矩阵的列。

（3）缩短码（shortening a code）：通过扔掉一些数据符号而减少码长，这对应于删去校验矩阵的列或者说减少生成矩阵的维数。新码的码率为。扔掉的数据符号一般是固定取值的，从而收发双方已知。

（4）增余删信码（expurgating a code）：它是在原码基础上，删去一些数据符号而同时增加校验符号，从而码长不改变，但显然码率会降低，这对应于删去生成矩阵的行。一个增余删信码是原码的子码。