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

1、2022-12-11第六章编码理论的基本知识第六章编码理论的基本知识（二）（二）2022-12-12第六章编码理论的基本知识第六章编码理论的基本知识2本节主要介绍编码理论的一些基本知识，主要内容包本节主要介绍编码理论的一些基本知识，主要内容包括：括：编码理论的基本问题编码理论的基本问题F置换码置换码F码的重量码的重量F码的界码的界2022-12-13第三节编码理论的基本问题第三节编码理论的基本问题n在上文中我们已经给出，一个在上文中我们已经给出，一个(q,n,M)(q,n,M)码的主要指标码的主要指标是：是：和和d=d(C)d=d(C)。因此，编码理论的基。因此，编码理论的基本问题是在以下条件

2、下构造本问题是在以下条件下构造q q元的元的(n,M,d)(n,M,d)码：码：(1)(1)在码率在码率R R固定的条件下，使最小距离固定的条件下，使最小距离d d尽量大。尽量大。(2)(2)在最小距离在最小距离d d 固定的条件下，使码率固定的条件下，使码率R R尽量大。尽量大。如果码长如果码长n n固定，那么以上编码问题就化为：固定，那么以上编码问题就化为：(3)(3)在码元数在码元数M M固定的条件下，使最小距离固定的条件下，使最小距离d d 尽量尽量大。大。(4)(4)在最小距离在最小距离d d 固定的条件下，使码元数固定的条件下，使码元数M M尽量尽量大。大。2022-12-14第三

3、节编码理论的基本问题第三节编码理论的基本问题n这里这里d d 尽量大意味着可以纠正更多的差错，而尽量大意味着可以纠正更多的差错，而M M尽量尽量大意味着可以发送更多的信息。我们以下定义大意味着可以发送更多的信息。我们以下定义A Aq q(n,d(n,d)为为d d固定，固定，M M为最大的为最大的q q元元(n,M,d)(n,M,d)码。编码理码。编码理论的基本问题之一就是讨论对论的基本问题之一就是讨论对A Aq q(n,d(n,d)的值的分析。的值的分析。n对于对于d=1d=1和和d=nd=n，有如下结果。，有如下结果。对于任意对于任意n1,An1,Aq q(n,1)=q(n,1)=q(n)

4、(n),A,Aq q(n,n(n,n)=q.)=q.设设A=a=a1 1,a,a2 2,a as s 是任意有限集合，则从是任意有限集合，则从A到到A的一的一个个1-11-1映射映射，称为，称为A上的一个上的一个。2022-12-15第三节编码理论的基本问题第三节编码理论的基本问题 关于码的置换有两种，一种是关于关于码的置换有两种，一种是关于，另一种是关于，另一种是关于。我。我们分别记之为们分别记之为)(.)2(2)1(11111nn)1(1.)1(1)0(02222qq我们分别称这两种类型的置换为我们分别称这两种类型的置换为，或简称，或简称。2022-12-16第三节编码理论的基本问题第三节

5、编码理论的基本问题n定义定义6.3.2 6.3.2 由换位型与换元型的置换可产生换位型由换位型与换元型的置换可产生换位型与换元型的码，这就是对一个与换元型的码，这就是对一个q q元的元的(n,M)(n,M)的码的码C C，对它可产生对它可产生：(1)(1)置换码，也就是说对每个向量的坐标置换码，也就是说对每个向量的坐标进行置换，如记为进行置换，如记为C C中的任意码元，它的坐标位中的任意码元，它的坐标位置上的置换为置上的置换为)()2(2)1(11111.)(nnxxxxxxx这时我们记这时我们记 并称之为并称之为C C的的。:)()(111CxxCC2022-12-17第三节编码理论的基本问

6、题第三节编码理论的基本问题(2)(2)，这时对每个坐标位上的码元符，这时对每个坐标位上的码元符号进行置换，我们记号进行置换，我们记),.,(222212n其中每个其中每个 是换元型的置换。这时对每个是换元型的置换。这时对每个 它的码元符号的置换为它的码元符号的置换为Cxxxxn),.,(21j2)(.)()()(2222212112nnnxxxxxxx我们同样记我们同样记 ，并称之为，并称之为C C的的。:)()(222CxxCC2022-12-18第三节编码理论的基本问题第三节编码理论的基本问题n如果把码如果把码C C按矩阵排列，每一个码字为一行，那么按矩阵排列，每一个码字为一行，那么C C

7、可排成一个的矩阵，我们记之为可排成一个的矩阵，我们记之为MnMMnnxxxxxxxxxC.212222111211 这时这时，而，而。因此，在上述。因此，在上述两种运算下，码字之间距离保持不变。从而称是两种运算下，码字之间距离保持不变。从而称是C C的的等价码，它们有相同的参数等价码，它们有相同的参数(n,M,d(n,M,d)以及可以纠正相以及可以纠正相同的错误。同的错误。2022-12-19第三节编码理论的基本问题第三节编码理论的基本问题 如果如果0 0U U，则，则U U上任意一个上任意一个q q元元(n,M,d)(n,M,d)码码等价于一个包含零码字等价于一个包含零码字0=00=00 0

8、的的q q元元(n,M,d)(n,M,d)码码。n例例1 1 三元码三元码 201120012C等价于码长为等价于码长为3 3的三元重复码，对此我们做换元置换的三元重复码，对此我们做换元置换 为：为：是一个恒等变换，而取是一个恒等变换，而取),(23222122110221022021210232022-12-110第三节编码理论的基本问题第三节编码理论的基本问题这时得到这时得到222111000)(22CC例例2 2 设二元设二元(5,4,3)(5,4,3)码码100100000000001101101,11111101101100011011CC则则C C与与C2C2等价等价2022-12

9、-111第三节编码理论的基本问题第三节编码理论的基本问题此时在码此时在码C C的第三个位置上进行置换，作的第三个位置上进行置换，作 其余的其余的 为恒等变换，那么为恒等变换，那么0110233,2jj01100110101011001100)(21CC然后把第三行和第四行交换，再把第二列和第四列然后把第三行和第四行交换，再把第二列和第四列交换，就得到码交换，就得到码C1C1。2022-12-112第三节编码理论的基本问题第三节编码理论的基本问题n现在确定现在确定Aq(5,3),设设C为一个二元为一个二元(5,M,3)码，我们最码，我们最大的大的M，易知，易知C包含零码字包含零码字0=00，则其

10、余码字汉，则其余码字汉明势必大于或等于明势必大于或等于3，汉明势为，汉明势为4或或5的码字至多只的码字至多只有一个，分析知有一个，分析知A2(5,3)3+1=4n此时可以构造此时可以构造C为为11001100011010101010C2022-12-113第三节编码理论的基本问题第三节编码理论的基本问题n由此可见，一般构造由此可见，一般构造A Aq q(n,d(n,d)的最优码是十分困难的，的最优码是十分困难的，为此讨论它的一些性质。为此讨论它的一些性质。设设xV(n,qxV(n,q)，x x的汉明势又称的汉明势又称，这时，这时记为记为w w(x(x)，它们是，它们是x x中非零位置的个数。码

11、中非零位置的个数。码 的的(简称为简称为)定义为定义为),(qnVC 0,|)(min)(xCxxc 设设x=x1x2xn和和y=y1y2yn V(n,2)，x和和y的的定义为定义为),.,(2211nnyxyxyxyx2022-12-114第三节编码理论的基本问题第三节编码理论的基本问题因此，因此，中第中第i i位置是非零的充分必要条件是位置是非零的充分必要条件是x x和和y y在第在第i i个位置都是非零的。个位置都是非零的。yx (1)(1)对于所有的对于所有的(2)(2)对于所有的对于所有的)(),(),(,yxyxdqnVyx)(2)()(),(),2,(,yxyxyxdnVyx 设

12、设d d为奇数，则二元为奇数，则二元(n,M,d(n,M,d)码存在充分码存在充分必要条件是二元必要条件是二元(n+1,M,d+1)(n+1,M,d+1)码存在。码存在。2022-12-115第三节编码理论的基本问题第三节编码理论的基本问题推论推论6.3.1 6.3.1 如果如果d d是奇数，则是奇数，则 。它等。它等价于，如果价于，如果d d是偶数，则是偶数，则 。),()1,1(22dnAdnA)1,1(),(22dnAdnA 由例由例2 2知，知，。因此。因此 。而且可由。而且可由例例2 2中的二元中的二元(5,4,3)(5,4,3)码构造一个二元码构造一个二元(6,4,4)(6,4,4

13、)码码:4)3,5(2A4)4,6(2A110110101101011011000000)4,4,6(11011101100110100000)3,4,5(码增加奇偶校验位码2022-12-116第三节编码理论的基本问题第三节编码理论的基本问题 设设x xV(n,q)V(n,q)，r r为一非负整数，则中心为一非负整数，则中心在在x x、半径为、半径为r r的球定义为。的球定义为。设设x xV(n,q)V(n,q)，则球，则球 中所含中所含V(n,q)V(n,q)中向量的个数为中向量的个数为),(|),(),(ryxdqnVyrxSq),(rxSqrqrnqnn)1(.)1(102022-12

14、-117第三节编码理论的基本问题第三节编码理论的基本问题(汉明界汉明界)q)q元元(n,M,2t+1)(n,M,2t+1)码满足码满足 设设C C是一个是一个q q元元(n,M,2t+1)(n,M,2t+1)码，如果码，如果 则称则称C C为为。)()1(.)1(10ntqqtnqnnM)()1(.)1(10ntqqtnqnnM2022-12-118第三节编码理论的基本问题第三节编码理论的基本问题n定理定理6.3.4(Gilbert-Varshamov6.3.4(Gilbert-Varshamov界界)存在存在 的的(n,M,d)(n,M,d)码，因此码，因此10)()1(diinqinqM10)()1(),(diinqqinqMdnA2022-12-119第三节编码理论的基本问题第三节编码理论的基本问题n定理定理6.3.5(Singleton6.3.5(Singleton界界)A Aq q(n,d(n,d)q qn-d+1n-d+1 。