信息与编码编码11课件

第六章编码理论的基本知识（二）11/22/20221

第六章编码理论的基本知识（二）11/21/20221第六章编码理论的基本知识2本节主要介绍编码理论的一些基本知识，主要内容包括：编码理论的基本问题置换码码的重量码的界11/22/20222第六章编码理论的基本知识2本节主要介绍编码理论的一些基本知识第三节编码理论的基本问题在上文中我们已经给出，一个(q,n,M)码的主要指标是：码率和最小距离d=d(C)。因此，编码理论的基本问题是在以下条件下构造q元的(n,M,d)码：(1)在码率R固定的条件下，使最小距离d尽量大。(2)在最小距离d固定的条件下，使码率R尽量大。如果码长n固定，那么以上编码问题就化为：(3)在码元数M固定的条件下，使最小距离d尽量大。(4)在最小距离d固定的条件下，使码元数M尽量大。11/22/20223第三节编码理论的基本问题在上文中我们已经给出，一个(q,n,第三节编码理论的基本问题这里d尽量大意味着可以纠正更多的差错，而M尽量大意味着可以发送更多的信息。我们以下定义Aq(n,d)为d固定，M为最大的q元(n,M,d)码。编码理论的基本问题之一就是讨论对Aq(n,d)的值的分析。对于d=1和d=n，有如下结果。定理6.3.1对于任意n>1,Aq(n,1)=q(n),Aq(n,n)=q.设A={a1,a2,…as}是任意有限集合，则从A到A的一个1-1映射σ，称为A上的一个置换。11/22/20224第三节编码理论的基本问题这里d尽量大意味着可以纠正更多的差第三节编码理论的基本问题定义6.3.1关于码的置换有两种，一种是关于下标集合的置换，另一种是关于信号字母表的置换。我们分别记之为我们分别称这两种类型的置换为σ1型与σ2型的置换，或简称换位型与换元型置换。11/22/20225第三节编码理论的基本问题定义6.3.1关于码的置换有两种，第三节编码理论的基本问题定义6.3.2由换位型与换元型的置换可产生换位型与换元型的码，这就是对一个q元的(n,M)的码C，对它可产生换位型与换元型的置换码：(1)

换位型置换码，也就是说对每个向量的坐标进行置换，如记为C中的任意码元，它的坐标位置上的置换为这时我们记并称之为C的换位型置换码。11/22/20226第三节编码理论的基本问题定义6.3.2由换位型与换元型的置第三节编码理论的基本问题(2)换元型置换码，这时对每个坐标位上的码元符号进行置换，我们记其中每个是换元型的置换。这时对每个它的码元符号的置换为我们同样记，并称之为C的换元型置换码。11/22/20227第三节编码理论的基本问题(2)换元型置换码，这时对每个坐标位第三节编码理论的基本问题如果把码C按矩阵排列，每一个码字为一行，那么C可排成一个的矩阵，我们记之为这时换位型置换等价于矩阵列的置换，而换元型置换等价于每一列中码字符的置换。因此，在上述两种运算下，码字之间距离保持不变。从而称是C的等价码，它们有相同的参数(n,M,d)以及可以纠正相同的错误。11/22/20228第三节编码理论的基本问题如果把码C按矩阵排列，每一个码字为一第三节编码理论的基本问题引理6.3.1如果0∈U，则U上任意一个q元(n,M,d)码等价于一个包含零码字0=0…0的q元(n,M,d)码。例1三元码

等价于码长为3的三元重复码，对此我们做换元置换为：是一个恒等变换，而取11/22/20229第三节编码理论的基本问题引理6.3.1如果0∈U，则U上任第三节编码理论的基本问题这时得到例2设二元(5,4,3)码则C与C2等价11/22/202210第三节编码理论的基本问题这时得到例2设二元(5,4,3)码第三节编码理论的基本问题此时在码C的第三个位置上进行置换，作其余的为恒等变换，那么然后把第三行和第四行交换，再把第二列和第四列交换，就得到码C1。

11/22/202211第三节编码理论的基本问题此时在码C的第三个位置上进行置换，作第三节编码理论的基本问题现在确定Aq(5,3),设C为一个二元(5,M,3)码，我们最大的M，易知C包含零码字0=0…0，则其余码字汉明势必大于或等于3，汉明势为4或5的码字至多只有一个，分析知A2(5,3)≤3+1=4此时可以构造C为11/22/202212第三节编码理论的基本问题现在确定Aq(5,3),设C为一个二第三节编码理论的基本问题由此可见，一般构造Aq(n,d)的最优码是十分困难的，为此讨论它的一些性质。定义6.3.3设x∈V(n,q)，x的汉明势又称重量，这时记为w(x)，它们是x中非零位置的个数。码的最小重量(简称为重量)定义为定义6.3.4设x=x1x2…xn和y=y1y2…yn

∈

V(n,2)，x和y的交定义为11/22/202213第三节编码理论的基本问题由此可见，一般构造Aq(n,d)的最第三节编码理论的基本问题因此，中第i位置是非零的充分必要条件是x和y在第i个位置都是非零的。引理6.3.2

(1)对于所有的(2)对于所有的定理6.3.2设d为奇数，则二元(n,M,d)码存在充分必要条件是二元(n+1,M,d+1)码存在。11/22/202214第三节编码理论的基本问题因此，中第i位置是非零的充分第三节编码理论的基本问题推论6.3.1如果d是奇数，则。它等价于，如果d是偶数，则。例3由例2知，。因此。而且可由例2中的二元(5,4,3)码构造一个二元(6,4,4)码:11/22/202215第三节编码理论的基本问题推论6.3.1如果d是奇数，则第三节编码理论的基本问题定义6.3.5设x∈V(n,q)，r为一非负整数，则中心在x、半径为r的球定义为。引理6.3.3设x∈V(n,q)，则球中所含V(n,q)中向量的个数为11/22/202216第三节编码理论的基本问题定义6.3.5设x∈V(n,q)第三节编码理论的基本问题定理6.3.3(汉明界)q元(n,M,2t+1)码满足定义6.3.6设C是一个q元(n,M,2t+1)码，如果则称C为完备码。11/22/202217第三节编码理论的基本问题定理6.3.3(汉明界)q元(n第三节编码理论的基本问题定理6.3.4(Gilbert-Varshamov界)存在的(n,M,d)码，因此11/22/202218第三节编码理论的基本问题定理6.3.4(Gilbert-Va第三节编码理论的基本问题定理6.3.5(Singleton界)

Aq(n,d)≥qn-d+1。

11/22/202219第三节编码理论的基本问题定理6.3.5(Singleton

第六章编码理论的基本知识（二）11/22/202220

第六章编码理论的基本知识（二）11/21/20221第六章编码理论的基本知识2本节主要介绍编码理论的一些基本知识，主要内容包括：编码理论的基本问题置换码码的重量码的界11/22/202221第六章编码理论的基本知识2本节主要介绍编码理论的一些基本知识第三节编码理论的基本问题在上文中我们已经给出，一个(q,n,M)码的主要指标是：码率和最小距离d=d(C)。因此，编码理论的基本问题是在以下条件下构造q元的(n,M,d)码：(1)在码率R固定的条件下，使最小距离d尽量大。(2)在最小距离d固定的条件下，使码率R尽量大。如果码长n固定，那么以上编码问题就化为：(3)在码元数M固定的条件下，使最小距离d尽量大。(4)在最小距离d固定的条件下，使码元数M尽量大。11/22/202222第三节编码理论的基本问题在上文中我们已经给出，一个(q,n,第三节编码理论的基本问题这里d尽量大意味着可以纠正更多的差错，而M尽量大意味着可以发送更多的信息。我们以下定义Aq(n,d)为d固定，M为最大的q元(n,M,d)码。编码理论的基本问题之一就是讨论对Aq(n,d)的值的分析。对于d=1和d=n，有如下结果。定理6.3.1对于任意n>1,Aq(n,1)=q(n),Aq(n,n)=q.设A={a1,a2,…as}是任意有限集合，则从A到A的一个1-1映射σ，称为A上的一个置换。11/22/202223第三节编码理论的基本问题这里d尽量大意味着可以纠正更多的差第三节编码理论的基本问题定义6.3.1关于码的置换有两种，一种是关于下标集合的置换，另一种是关于信号字母表的置换。我们分别记之为我们分别称这两种类型的置换为σ1型与σ2型的置换，或简称换位型与换元型置换。11/22/202224第三节编码理论的基本问题定义6.3.1关于码的置换有两种，第三节编码理论的基本问题定义6.3.2由换位型与换元型的置换可产生换位型与换元型的码，这就是对一个q元的(n,M)的码C，对它可产生换位型与换元型的置换码：(1)

换位型置换码，也就是说对每个向量的坐标进行置换，如记为C中的任意码元，它的坐标位置上的置换为这时我们记并称之为C的换位型置换码。11/22/202225第三节编码理论的基本问题定义6.3.2由换位型与换元型的置第三节编码理论的基本问题(2)换元型置换码，这时对每个坐标位上的码元符号进行置换，我们记其中每个是换元型的置换。这时对每个它的码元符号的置换为我们同样记，并称之为C的换元型置换码。11/22/202226第三节编码理论的基本问题(2)换元型置换码，这时对每个坐标位第三节编码理论的基本问题如果把码C按矩阵排列，每一个码字为一行，那么C可排成一个的矩阵，我们记之为这时换位型置换等价于矩阵列的置换，而换元型置换等价于每一列中码字符的置换。因此，在上述两种运算下，码字之间距离保持不变。从而称是C的等价码，它们有相同的参数(n,M,d)以及可以纠正相同的错误。11/22/202227第三节编码理论的基本问题如果把码C按矩阵排列，每一个码字为一第三节编码理论的基本问题引理6.3.1如果0∈U，则U上任意一个q元(n,M,d)码等价于一个包含零码字0=0…0的q元(n,M,d)码。例1三元码

等价于码长为3的三元重复码，对此我们做换元置换为：是一个恒等变换，而取11/22/202228第三节编码理论的基本问题引理6.3.1如果0∈U，则U上任第三节编码理论的基本问题这时得到例2设二元(5,4,3)码则C与C2等价11/22/202229第三节编码理论的基本问题这时得到例2设二元(5,4,3)码第三节编码理论的基本问题此时在码C的第三个位置上进行置换，作其余的为恒等变换，那么然后把第三行和第四行交换，再把第二列和第四列交换，就得到码C1。

11/22/202230第三节编码理论的基本问题此时在码C的第三个位置上进行置换，作第三节编码理论的基本问题现在确定Aq(5,3),设C为一个二元(5,M,3)码，我们最大的M，易知C包含零码字0=0…0，则其余码字汉明势必大于或等于3，汉明势为4或5的码字至多只有一个，分析知A2(5,3)≤3+1=4此时可以构造C为11/22/202231第三节编码理论的基本问题现在确定Aq(5,3),设C为一个二第三节编码理论的基本问题由此可见，一般构造Aq(n,d)的最优码是十分困难的，为此讨论它的一些性质。定义6.3.3设x∈V(n,q)，x的汉明势又称重量，这时记为w(x)，它们是x中非零位置的个数。码的最小重量(简称为重量)定义为定义6.3.4设x=x1x2…xn和y=y1y2…yn

∈

V(n,2)，x和y的交定义为11/22/202232第三节编码理论的基本问题由此可见，一般构造Aq(n,d)的最第三节编码理论的基本问题因此，中第i位置是非零的充分必要条件是x和y在第i个位置都是非零的。引理6.3.2

(1)对于所有的(2)对于所有的定理6.3.2设d为奇数，则二元(n,M,d)码存在充分必要条件是二元(n+1,M,d+1)码存在。11/22/202233第三节编码理论的基本问题因此，中第i位置是非零的充分第三节编码理论的基本问题推论6.3.1如果d是奇数，则。它等价于，如果d是