信息与编码编码课件

第七章线性码（二）9/27/20231第七章 线

性

码（二）9/27/20232本节主要介绍线性码理论的一些基本知识，主要内容包括：线性码的译码方法线性码的重量分布第三节线性码的译码方法第三节线性码的译码方法应用线性码的校验矩阵，我们可以获得一种非常有

效的线性码的译码方法。下面我们来介绍这种方法，即线性码的标准阵译码方法。为此，我们首先介绍

一个概念。定义7.3.1

设L是一个q元[n,k]线性码，H为它的校验矩阵。对任意 ，称

为x的伴随式，记为S(x)。显然，设 为H的行向量，则9/27/20233第三节线性码的译码方法如果 是一个线性码，则V(n,q)关于L的商空间定义为 。集合称为L的陪集。商空间是Fq上的向量空间，它们的运算定义如下：a(x+L)=ax+L,(x+L)+(y+L)=(x+y)+L.而且x+L=y+L充分必要条件是

。10/21/20234第三节线性码的译码方法定理7.3.1

设L是一个q元[n,k]线性码，H是它的校验矩阵，则 属于同一个陪集的充分必要条件是它们的伴随式相同。定理7.3.2

设L是一个线性码，H是它的校验矩阵，则最小距离译码等价于把收到的字x译成码字c=x-a，其中a是倍集x+L中具有最小重量的字，或a是与x具有相同伴随式并且重量最小的字。10/21/20235第三节线性码的译码方法上述译码方法可以用列表的形式描述如下：10/21/20236第三节线性码的译码方法10/21/20237表中的第一行为L中的所有码字，在V(n,q)选取一

个不在第一行且具有最小重量的字a1，与第一行的

每一个字相加得到第二行，它们构成a1+L。一般地，选取一个不在前i行中且具有最小重量的字ai，与第

一行的每一个字相加得到i+1行，它们构成ai

+L。此过程一直进行到表中包含V(n,q)中所有的字。上述列表称为L的标准阵。第一列中的ai称为陪集头。如果收到的字x在表中的第j+1列，则x=cj+ai，对某个i。由于的ai取法，因此x译成ci=x-ai，即是包含x的那一列中最上边的码字。这种译码方法称为标准

阵译码。第三节线性码的译码方法10/21/20238由于每一行可以由它的元素的伴随式惟一决定，上述过程可以简化。我们只需列出陪集头和对应的伴随式。如果x是收到的字，计算它的伴随式xHT，确定有相同伴随式的陪集头ai，则x被译为c=x-ai。这种译码过程称为伴随式译码

.第三节线性码的译码方法例7.3.1 设L是一个二元[4,2]线性码，它的生成矩阵把G的第二行加到第一行，得到L的一个标准型的生成矩阵10/21/20239第三节线性码的译码方法L的校验矩阵为L的标准阵为10/21/202310第三节线性码的译码方法如果x=1100是收到的字，查上表可知，1100译成

1110。由陪集头和它们的伴随式列表如下：如果收到的字x=0001，计算它的伴随式xHT=01查上表知，它的陪集头为0100，因此，x被译为0001-0100=0101。10/21/202311§7.4

线性码的重量分布10/21/202312值得注意的是，对于一个q元[n,k]线性码，当n,k不是很大时，这种方法很有效。但当

n,k很大时，工作量相当大，这种译码方法的效率不很高。§7.4

线性码的重量分布在本节里，我们将要讨论线性码的某种结构，并对线性码和它的对偶码建立一种联系，这

就是我们将要重点介绍的MacWilliams恒等式。§7.4

线性码的重量分布设L是一个q元[n,k]

线性码，Ai表示L中重量等于i的码字个数，

我们称

为L的重量分布，而称多项式称为L的重量分布多项式。显然，10/21/202313§7.4

线性码的重量分布例7.4.1

(1) 设L是二元[3,2] 线性码，L={000,011,101,110}.其对偶码L和 的重量分布多项式分别为(2)对于二元线性码L={00,11},其对偶码即L是自对偶的。因此，10/21/202314§7.4

线性码的重量分布一般来讲，对给定的码确定它的重量分布是一件困难的事件，但是对于线性码，MacWilliams恒等式使线性码L和它的对偶的重量分布建立了一种特殊

的关系。我们下面主要介绍二元线性码的

MacWilliams恒等式.引理7.4.1

设L是一个二元[n,k]线性码，

但，则对于任意 ，码L中使x·y等于0和1的码字个数相等。10/21/202315§7.4

线性码的重量分布引理7.4.2

设L是二元[n,k]线性码，,则引理7.4.3设，则10/21/202316§7.4

线性码的重量分布定理7.4.1(二元线性码的MacWilliams恒等式)设L是一个二元[n,k]

线性码， 是它的对偶码，则定理7.4.2

(q元线性码的MacWilliams恒等式)设L是一个二元[n,k]线性码，是它的对偶码,则10/21/202317§7.4

线性码的重量分