信息与编码编码13课件.ppt

1、2023-5-21第七章第七章线性码线性码（二）（二）2023-5-22第七章第七章 线线 性性 码（二）码（二）本节主要介绍线性码理论的一些基本知识，主要内容本节主要介绍线性码理论的一些基本知识，主要内容包括：包括：u线性码的译码方法线性码的译码方法u线性码的重量分布线性码的重量分布2023-5-23第三节第三节线性码的译码方法线性码的译码方法n第三节第三节线性码的译码方法线性码的译码方法n应用线性码的校验矩阵，我们可以获得一种非常有应用线性码的校验矩阵，我们可以获得一种非常有效的线性码的译码方法。下面我们来介绍这种方法，效的线性码的译码方法。下面我们来介绍这种方法，即线性码的标准阵译码方法

2、。为此，我们首先介绍即线性码的标准阵译码方法。为此，我们首先介绍一个概念。一个概念。设设L是一个是一个q元元n,k线性码，线性码，H为它的校验为它的校验矩阵。对任意矩阵。对任意 ，称，称 为为x的的，记为，记为S(x)。),(qnVxTxH显然，显然，设设 为为H H的行向量，则的行向量，则 LxxS 0)(knhhh,.,21),.,()(21knhxhxhxxS2023-5-24第三节第三节线性码的译码方法线性码的译码方法如果如果 是一个线性码，则是一个线性码，则V(n,q)关于关于L的商的商空间定义为空间定义为 。集合。集合 称为称为L的的。商空间是。商空间是Fq上的上的向量空间，它们的

3、运算定义如下：向量空间，它们的运算定义如下：),(qnVL),(|/),(qnVxLxLqnV|LccxLx a(x+L)=ax+L,(x+L)+(y+L)=(x+y)+L.而且而且x+L=y+L充分必要条件是充分必要条件是 。Lyx2023-5-25第三节第三节线性码的译码方法线性码的译码方法 设设L是一个是一个q元元n,k线性码，线性码，H是它是它的校验矩阵，则的校验矩阵，则 属于同一个陪集属于同一个陪集的充分必要条件是它们的伴随式相同。的充分必要条件是它们的伴随式相同。),(,qnVyx 设设L是一个线性码，是一个线性码，H是它的校验矩是它的校验矩阵，则最小距离译码等价于把收到的字阵，则

4、最小距离译码等价于把收到的字x译成译成码字码字c=x-a，其中，其中a是倍集是倍集x+L中具有最小重量中具有最小重量的字，或的字，或a是与是与x具有相同伴随式并且重量最具有相同伴随式并且重量最小的字。小的字。2023-5-26第三节第三节线性码的译码方法线性码的译码方法n上述译码方法可以用列表的形式描述如下：上述译码方法可以用列表的形式描述如下：LALacacacaacacacaacacacacccsmsssmmm 121222212112111210.2023-5-27第三节第三节线性码的译码方法线性码的译码方法n表中的第一行为表中的第一行为L中的所有码字，在中的所有码字，在V(n,q)选取

5、一选取一个不在第一行且具有最小重量的字个不在第一行且具有最小重量的字a1，与第一行的，与第一行的每一个字相加得到第二行，它们构成每一个字相加得到第二行，它们构成a1+L。一般地，。一般地，选取一个不在前选取一个不在前i行中且具有最小重量的字行中且具有最小重量的字ai，与第，与第一行的每一个字相加得到一行的每一个字相加得到i+1+1行，它们构成行，它们构成ai +L。此过程一直进行到表中包含此过程一直进行到表中包含V(n,q)中所有的字。上中所有的字。上述列表称为述列表称为L L的标准阵。第一列中的的标准阵。第一列中的ai称为称为。n如果收到的字如果收到的字x在表中的第在表中的第j+1+1列，则

6、列，则x=cj+ai，对某，对某个个i。由于的由于的ai取法，因此取法，因此x译成译成ci=x-ai，即是包含，即是包含x的那一列中最上边的码字。这种译码方法称为的那一列中最上边的码字。这种译码方法称为。2023-5-28第三节第三节线性码的译码方法线性码的译码方法n由于每一行可以由它的元素的伴随式惟一决由于每一行可以由它的元素的伴随式惟一决定，上述过程定，上述过程。我们只需列出陪集。我们只需列出陪集头和对应的伴随式。如果头和对应的伴随式。如果x是收到的字，计是收到的字，计算它的伴随式算它的伴随式xHT，确定有相同伴随式的陪，确定有相同伴随式的陪集头集头ai，则，则x被译为被译为c=x-ai。

7、这种译码过程称。这种译码过程称为为 .2023-5-29第三节第三节线性码的译码方法线性码的译码方法n例例7.3.1 7.3.1 设设L是一个二元是一个二元4,24,2线性码，它的生成线性码，它的生成矩阵矩阵 10100111G10101101G把把G的第二行加到第一行，得到的第二行加到第一行，得到L的一个标准的一个标准型的生成矩阵型的生成矩阵2023-5-210第三节第三节线性码的译码方法线性码的译码方法nL L的校验矩阵为的校验矩阵为10110101H1100011110010010101000011111010001101101001110001110010110110000L的标准阵为

8、的标准阵为2023-5-211第三节第三节线性码的译码方法线性码的译码方法n如果如果x=1100=1100是收到的字，查上表可知，是收到的字，查上表可知，11001100译成译成11101110。由陪集头和它们的伴随式列表如下：。由陪集头和它们的伴随式列表如下：100010010100111000000000伴随式陪集头如果收到的字如果收到的字x=0001，计算它的伴随式，计算它的伴随式xHT=01查上表知，它的陪集头为查上表知，它的陪集头为0100，因此，因此，x被译为被译为 0001-0100=0101。2023-5-2127.4 7.4 n值得注意的是，对于一个值得注意的是，对于一个q元

9、元 n,k 线性码，线性码，当当。但当。但当n,k很大时，工作量相当大，这种译码方法的很大时，工作量相当大，这种译码方法的效率不很高效率不很高。n7.4 7.4 n在本节里，我们将要讨论线性码的某种结构，在本节里，我们将要讨论线性码的某种结构，并对线性码和它的对偶码建立一种联系，这并对线性码和它的对偶码建立一种联系，这就是我们将要重点介绍的就是我们将要重点介绍的MacWilliamsMacWilliams恒等恒等式式。2023-5-2137.4 7.4 设设L是一个是一个q元元n,k 线性码，线性码，Ai表示表示L中重量中重量等于等于i的码字个数，的码字个数，我们称我们称 为为L的重量分布，而

10、称多项式的重量分布，而称多项式ni 0nAAA,.,10)(0)(10.)(ninniiLzAzAAzAzWLxxLzzW)()(称为称为L的重量分布多项式。显然的重量分布多项式。显然，2023-5-2147.4 7.4 (1)(1)设设L L是二元是二元3,2 3,2 线性码，线性码，L=000,011,101,110.其对偶码其对偶码 L和和 的重量分布多项式分别为的重量分布多项式分别为111,000LL321)(31)(zzWzzWLLLL 21)()(zzWzWLL(2)(2)对于二元线性码对于二元线性码L=00,11,L=00,11,其对偶码其对偶码即即L L是自对偶的。因此，是自对

11、偶的。因此，2023-5-2157.4 7.4 n一般来讲，对给定的码确定它的重量分布一般来讲，对给定的码确定它的重量分布，但是对于线性码，但是对于线性码，MacWilliamsMacWilliams恒等式恒等式使线性码使线性码L L和它的对偶的重量分布建立了一种特殊和它的对偶的重量分布建立了一种特殊的关系。我们下面主要介绍二元线性码的的关系。我们下面主要介绍二元线性码的MacWilliamsMacWilliams恒等式恒等式.设设L是一个二元是一个二元n,k线性码，线性码，但但 ，则对于任意，则对于任意 ，码，码L中使中使xy等于等于0和和1的码字个数相等。的码字个数相等。)2,(nVyLy

12、Lx2023-5-2167.4 7.4 设设L是二元是二元n,k 线性码，线性码，,则则)2,(nVyLxkyxLyLy02)1(设设 ，则，则)2,(nVx)2,()()()()()1()1()1()1(nVyxnxxyxyzzzz2023-5-2177.4 7.4 定理定理7.4.1(二元线性码的二元线性码的MacWilliams恒等式恒等式)设设L是一个二元是一个二元n,k 线性码，线性码，是它的对偶码，则是它的对偶码，则LzzWzzWLnkL11)1(21)(zqzWzqqzWLnkL)1(11)1(1(1)(定理定理7.4.2(q元线性码的元线性码的MacWilliams恒等式恒等式)设设L是一个二元是一个二元n,k 线性码，线性码，是它的对偶码是它的对偶码,则则L2023-5-2187.4 7.4 例例7.4.2 把定理把定理7.4.1应用到例应用到例7.4.1中中。(1),根据定理根据定理7.4.1。231)(zzWL32331)1()1(3)1(4111)1(41)(zzzzzzWzzWLL这和例这和例7.4.1中的结果一致。同样我们可以利用中的结果一致。同样我们可以利用 求求 ,)(zWL)(zWL233331)1()1(2111)1(21)(zzzzzWzzWLL2023-5-219作业作业 P168,7.8,7.10P168,7.8,7.10