InformationandCodingTheory码的最小距离.pptVIP

根据最小距离译码法则，译码器选择e = 001000，因为这个e的重量最小 找到这个e之后，则可以计算出发送的码字 =100101 + 001000 =101101 * 7.6 汉明码 汉明码：汉明码是一类能纠正任意单个错误的码，它的相关参数如下： 最简单的汉明码为[7, 4, 3]汉明码，它的奇偶校验矩阵为： * 奇偶校验阵： 可计算出它的生成矩阵： 编码过程既可以有奇偶校验矩阵出发，也可以有生成矩阵出发。消息的长度为4，所以编码过程如下：码字的第一部分，即前面的4位即是消息： * 后面三位由奇偶校验方程组决定： 码字的个数为24 = 16： * 可以看出 * 习题 讲义中第1～7题 * * Information and Coding Theory * 第7章 纠错编码初步 内容 7.1 导论 7.2 分组码的模型 7.3 线性码的特点 7.4 接收端 7.5 译码 * 导论 信源编码： 信道编码 数字信号在传输的过程中更容量产生错误。模拟信号的差错有一个逐渐变差的过程。而数字信号却是突然的变化，比如直接由0变为1。因此数字信号更需要得到有效的保护。 * 分组码的模型 纠错码可以分为两种类型：分组码(block code)和卷积码(convolutional code) 分组码： 信源输出的是二进制的比特流，称信源产生的输出为消息 * 分组码的模型 分组码指的是编码器对比特流进行分块处理，编码器将长度为k的消息符号 （ ui=0或者1）映射为一个码字 (xi =0或者1)，其中 ，所有码字构成的集合称为码（code）。 系统线性码：码字的第一部分包含消息本身， 接下来是n-k位校验符号 校验符号选择的方法是使得码字满足： * H((n-k)xn阵)称为码的奇偶校验矩阵 该矩阵可写出如下的分块矩阵形式： P是某个固定的 (n-k)xk矩阵 * 例1 例1：奇偶校验矩阵定义了一个k =3, n =6 的码 编码过程： * 由奇偶校验方程 如果消息u = 011，码字为x = 011011 共8个码字，一般地，有2^k个码字 000000 001110 010101 011011 100011 101101 110110 111000 * 定义线性码：令H为任意的二元矩阵，定义奇偶校验矩阵为H的线性码为由所有满足 （其中的运算指的是模2的运算）的向量x组成的集合。 * 例2 重复码 重复码：一个k = 4, n = 5的重复码指的是具有如下奇偶校验矩阵的线性码： 每个码字只包含一个消息符号u, 奇偶校验方程为 只有2个码字：00000和11111. * 例3 偶重量码 一个k = 3, n = 4的重复码指的是具有奇偶校验矩阵H=[1 1 1 1]的线性码；每个码字包含3个消息符号 和一个校验符号 总共有23=8个码字： 0000，0011，0101，1001， 0110，1010，1100，1111 所有的码字都有偶数个1. * 7.3 线性码的特点 1. X是一个码字当且仅当它满足 2. H为[P|In-k]的(n-k)xn阵，码字个数2^k。 3.生成矩阵： 如何由 得到 * 由码定义 码字是G的行向量的所有可能组合，这个性质也可以用来定义码 * H和G的联系： * 例1 续 例1续 x= uG= 第2行+第3行 = 010101+001110 = 011011 * 4. 线性码的参数：码长为n，n也称为码的分块长度，如果H有n – k 个线性独立的行，则总共有2^k个码字，k称为码的维度。这个维度的概念和线性代数中讲述的向量空间的维度概念完全是一样的。我们称这样的码为[n, k]码。 * 5. 其他的生成矩阵和奇偶校验矩阵：一个码可以有多个不同的生成矩阵，从一个给定的码中，选择任意的最大线性无关码字集，用该最大线性无关码字集合中的每个码字作为一个行向量，这样得到的矩阵就可以作为该码的生成矩阵。 类似的，如果将对任意的码字x都满足hxT= 0 的行向量h称为校验子(parity check)，则任意的最大线性无关校验子集可作为该码的奇偶校验矩阵H的行向量。 * 6. 线性性：如果x和y是一个给定的码的码字，则x + y也是码字 这就是为什么这些码被称为线性码的原因，因为这些码字满足线性性。事实上，这样的码也是一个加法群，还是一个域上的线性