信息与编码理论 第2版 课件 5.3 线性分组码

§5.3线性分组码概述线性分组码：具有线性性质的分组码。最为重要的一类信道编码技术，它是讨论其它各类码的基础。线性分组码可以用的形式来描述。如果符号只取自于由两个元素（0和1）构成集合，则称为二进制码。

k元组（k-tuples）

n元组（n-tuples）线性映射5.3.1向量空间定义所有二进制元组构成的集合称为二进制域（包括0和1两个元素）上的一个向量空间，记作。二进制域中的运算在不混淆的情况下也常常用“+”来表示模2加法。5.3.2线性分组码的结构子空间向量空间的一个子集如果满足下列两个条件，则称为的一个子空间：1)中包含全零向量；2)中任意两个向量的和仍然在内（封闭性质）。线性分组码构成一个子空间假设和是某二进制分组码中的两个码字向量，则该码是线性码的充要条件是也为该码的许用码字向量。例如，向量空间中共包括下列个4元组：显然，下列元素构成的子集是的一个子空间：容易验证子集中任意两个向量的和任然是中的一个向量。00000001001000100100100010011010110001010110001111011110011111110000010110101111总结：对于二进制编码，个元组构成的集合是一个线性分组码的充要条件是该集合为向量空间（包括所有的元组）的一个子空间。线性分组码是由个长度为的二进制向量组成的码字集合；对于任意两个码字向量均有；零向量将会是任意线性分组码中的一个合法码字向量。对于线性分组码，码字重量和码字之间的距离存在一一对应的关系：由式(5-6)可知，而也是一个合法码字。最小重量某线性分组码中所有非零码字重量的最小值，即线性分组码的最小重量与最小码距相等，即线性分组码的几何解释：个元组（图中所有圆点与方点）构成了向量空间，而该向量空间内的个元组（图中所有方点）构成了一个码字向量子空间，这些方点代表了合法码字（或称许用码字）。由图可知选择编码方案的基本目标：1）为了提高编码效率，应该在向量空间中安排尽可能多的码字向量，这样才能减少码字向量中的冗余度；2）许用码字之间的距离要尽可能的远，这样，即使发送码字在传输过程中受到扰乱，仍然能够以较高的概率实现正确译码。例：线性分组码该码共有个消息向量，因此共有8个码字，但是在向量空间中共有个6元组，所以需要在64个6元组中选择8个来构成码的所有许用码字。下表中的8个码字构成了向量空间的一个子空间，因此这些码字就构成了一个线性分组码。5.3.3生成矩阵对于线性分组码，利用前述的方法可以建立消息向量与码字之间的对应关系，并可以用类似于表格的结构存储下来，这样编码器便可以通过查表的方法来实现对不同消息向量的编码操作。如果的取值较大，则利用查表法实现编码器的复杂度会非常巨大。以码为例，该码共有个（约为）码字，此时如果仍使用简单的查表法来进行编码的话，会对计算机的内存空间提出巨大需求。因此需要寻找更为实用的编码实现方法：可以通过按需生成而非存储所有码字的方法来减小编码过程的复杂度。子空间的基一个线性分组码的码字集合是二进制维向量空间的一个维子空间（），所以通常可以找到少于个的元组构成的集合，该集合中的向量可以生成所有的个码字，此时称这些向量张成了一个子空间，张成该子空间的最小线性独立集合称为子空间的基，而其中包含的向量个数称为子空间的维数。设由个线性独立的元组向量组成的集合构成一个基，这样可以使用这些向量来生成所需的线性分组码，即个码字中的每一个码字均可以表示为（取值为0或1）为消息比特。生成矩阵（GeneratorMatrix）如果由个比特组成的消息序列可以表示为如下的行向量则码字向量可以如下得到：维矩阵。【例5-3】确定表5-3中线性分组码的生成矩阵。【解】选取下列3个线性独立的码字向量来构成生成矩阵：这样，使用该生成矩阵便可以生成表5-3中的所有码字，例如：讨论：显然，码字向量是生成矩阵中行向量的线性组合。因为一个线性分组码可以由其生成矩阵来完全确定，因此编码器仅仅需要存储的个行向量，而不用存储所有的个码字向量。对于本例而言，相比于表5-3中显示的维码字向量矩阵，编码器仅需要存储维的生成矩阵，这可以极大的降低编码器的复杂度。5.3.4系统线性分组码系统码码字向量中有连续位的内容与消息向量完全一样，而剩下的位表示校验比特。系统线性分组码的生成矩阵具有如下形式：使用系统码可以进一步减小编码器的复杂度。系统形式码字的生成公式为于是【例5-4】给出表5-3中线性分组码的码字生成公式。【解】因为在例5-3中已经给出了该码的生成矩阵，因此该码的码字可以如下生成：显然，利用上式得到的码字为系统码。5.3.5监督矩阵对于某个码维的生成矩阵，一定存在一个维的监督矩阵（Parity-CheckMatrix），该矩阵的行向量与生成矩阵的行向量正交，即对于该码的任意一个码字，均有判断码字是由矩阵生成的充要条件为。对于系统码而言，其生成矩阵形式为，为了保证与生成矩阵之间的正交性要求，其监督矩阵显然应具有如下结构【例5-5】给出表5-3中码的监督矩阵，并验证。【解】由例5-3可知该码的生成矩阵，于是可知监督矩阵为因此，可得由例5-4可知，代入上式可得线性分组码的最小码距和监督矩阵之间关系假如选择是具有最小重量（或）的码字，那么由关系式可知监督矩阵中有列是线性相关的；另一方面，由于没有重量小于的码字，所以中不可能会有少于列是线性相关的。例：观察例5-5中码的监督矩阵，可以发现其线性相关的列向量的最小数目为3，所以可以确定该码的最小码距为。

等于中线性相关的列向量的最小数目，也就是说的列空间是维的。对偶码一个线性分组码是向量空间的一个维子空间，因此会有一个正交补集（OrthogonalComplement），即由所有正交于的向量组成的集合。显然，正交补集是向量空间的一个维子空间，所以也表示了一个线性分组码，称为码的对偶码（DualCode）。可以证明，码的生成矩阵是对偶码的一个监督矩阵。5.3.6伴随式校验错误图样（ErrorPattern）对于编码器输出的一个码字，传输过程中某些位可能会出错，这样经过信道传输后的接收向量可以表示为式中表示信道传输引起的错误向量，称为错误图样。显然，对于长度为的二进制码字，一共有个可能的非零错误图样。伴随式（Syndrome）对于接收向量，定义下面的维向量为对应于的伴随式：译码器为了进行校验会计算其伴随式：如果是一个合法码字，则其对应的伴随式；如果中包含可检测到的错误，则其对应的伴随式中会有非零元素值；如果中包含可纠正的错误，则其伴随式中会有特殊的非零值来标记特定的错误图样。显然即由受扰码字向量或是对应的错误图样得到的伴随式是一样的。线性分组码有一个重要的性质（译码的基础）：可纠正的错误图样和伴随式是一一对应的。由上式可知，监督矩阵应具有下列两个重要性质：监督矩阵的列向量不能有全零向量。否则，在对应的码字位置发生的错误不会改变伴随式，故该种错误不能检测到。监督矩阵的所有列向量必须彼此不同。否则，如果中的两列是相同的，则发生在这两个对应位置的错误将是不可区分的。【例5-6】仍考虑前例中的线性分组码，假设当发送码字为时，接收向量是。求伴随式，并验证其等于。【解】由接收向量可得其伴随式为

显然错误图样为，于是5.3.7错误纠正标准阵列（StandardArray）对于一个码，标准阵列是由所有个可能的比特长的接收向量组成的列行的阵列。结构如下：第一行由所有的合法码字构成，其中第一个元素为全零码字；第一列包含所有可纠正的错误图样；每一行称为一个陪集（Coset），每行的第一个元素表示一个错误图样，称为陪集首（CosetLeader），每行后面的元素都是合法码字被该行陪集首扰乱后的接收向量。标准阵列的结构：结构特点：标准阵列第一行第一列的元素为全零码字，该元素有双重作用：既是合法码字之一，又可看作是一个错误图样，表示传输过程中没有错误发生，即。标准阵列包含了向量空间中所有的个元组，每个元组在标准阵列中仅出现一次，这样，每个陪集包含个元组，标准阵列中共有个陪集。利用标准阵列的译码思想：将受扰的接收向量（标准阵列中第一行之外的其它元组）纠正为该向量所在列顶部的合法码字。假设一个合法码字（）通过一个噪声干扰的信道传输，得到的受扰接收向量为，式中。如果信道引起的错误图样是一个陪集首，接收向量会被正确的纠正为传输码字；如果错误图样不是一个陪集首，则会导致译码错误发生。陪集的伴随式如果是第个陪集的陪集首（即错误图样），则将会是该陪集中的一个元组，该元组的伴随式为因为是一个合法码字，所以，于是上式变为从上式可知：陪集（标准阵列的每行）中的每一个元素均有相同的伴随式，而不同陪集对应的伴随式则彼此均不相同，这样便可以通过伴随式来估计对应的错误图样。纠错译码的步骤：(1)计算接收向量的伴随式；(2)从标准阵列中找到某个陪集首（错误图样），使得其伴随式也等于；(3)利用式将接收向量纠正为合法码字。该式可以理解为从接收向量中减去了找到的错误图样，由于是二进制运算，所以减法和加法是相同的。例：对前面讨论的码使用标准阵列来进行译码。给出该码的一个标准阵列，如下表：8个合法码字构成了标准阵列的第一行。第一列中的7个非零陪集首表示可纠正的错误图样。在剩下的8个6元组构成的陪集中，可以灵活的选择一个作为陪集首。所有重量为1的错误图样（共有6个）均是可以纠正的。注意：当且仅当信道引起的真实错误图样是该标准阵列中的一个陪集首时，译码结果才是正确的。对于一个纠错能力为的码，如果标准阵列的陪集首正好包含所有的不大于个错误的错误图样，且不包含任何其它错误图样（即没有多余的纠错能力），则称该码为完美码（PerfectCode）。陪集首的选择：应按照错误图样重量从小到大的顺序来排列。重量小的错误图样出现的概率更高，这样才能使得正确译码的概率最高。例如，对于错误转移概率为的二进制对称信道，上述码的码字经过该信道传输之后，不发生错误的概率为：发生1比特错误的概率为：发生2比特错误的概率为：发生3比特错误的概率为：以此类推。接下来，通过计算的值可以获得每个陪集首对应的伴随式，而这些伴随式均对应可以纠正的错误图样。即故各个陪集首对应的伴随式计算结果如右表：纠错对于接收向量，在计算得到其伴随式之后，可以通过形如上页的伴随式查询表来找到对应的错误图样。这样得到的错误图样是实际错误图样的一个估计值，可以记作，然后译码器将其与接收向量相加，便可得到发送码字的估计值：由上式可知：假如估计的错误图样与实际的错误图样相同，即，那么得到的码字估计值与发送的实际码字相等；假如错误图样的估计值不正确，则译码器得到的码字估计值不是实际的发送码字，这会导致无法检测的译码错误发生。【例5-7】继续考虑上述码，假设当发送码字为时的接收向量为，利用表5-6所示的伴随式查询表对进行译码。【解】由接收向量可以求得伴随式为通过伴随式