新信息论与编码ch.PPT

§3.1 信道的描述和分类 信道的描述 信道的分类 离散无记忆信道 若信道的输入是有r种取值可能的随机变量X，输出是有s种取值可能的随机变量Y，则信道的输入输出之间的统计关系可以由转移概率： 描述。 无干扰信道中没有随机性干扰，输出符号 与输入符号 之间有确定的对应关系。这种确定关系可以是如下三种形式中的一种： § 3.2 信道容量的定义 信息传输率 信道容量 § 3.3 信道容量的计算 对称信道的信道容量 准对称信道的信道容量 可逆矩阵信道的信道容量 1o 错误概率与信道统计特性相关，即与信道矩阵有关： 例： 2o 错误概率与译码规则有关： 例： 引理2得证。 信息论与编码－－第三章 信道及信道容量 记： 记空间： 那么，由于 则： 为联合典型序列在空间 中的密度。 根据概率的定义，有： 信息论与编码－－第三章 信道及信道容量 当 时， 与引理2中的上下界限相同。 即： 信息论与编码－－第三章 信道及信道容量 Shannon第二编码定理的证明： 设信道输入为 ，输出 ，转移概率为： 若发送消息为 ，接收消息序列为 ，则在发 条件下译码错误的概率为： 则消息独立等概时的平均错误率为： 信息论与编码－－第三章 信道及信道容量 采用随机编码方法，即从XN中独立随机地选择M=2NR，（R=logM/N）个序列作为码字，这相当于每个码字出现的概率为： 其中：R是要求的编码信息传输率， 并设X中的所有元素独立、等概的出现。这种编码方法称为随机编码。 信息论与编码－－第三章 信道及信道容量 译码规则：对 ，若存在唯一的 ，使： 则将 译为 ，即 若实际发送的为 ，则当 而 与 联合典型，就认为出现译码错误。不妨设发送的是第一个消息： 令： 信息论与编码－－第三章 信道及信道容量 则发送消息 时： 与j无关 信息论与编码－－第三章 信道及信道容量 由引理2 为了使R大，使I(X;Y)极大化，取I(X;Y)=C，若 ，则 时，上式趋于0，故： 即当 时， ，所以必然存在一种编码，使N足够大时，其 任意小。 信息论与编码－－第三章 信道及信道容量 编码逆定理：设离散无记忆信道的信道容量为C， 为任意小的正数，若选用码字个数 ，则无论N多大，也不能找到一种编码，使译码错误概率任意小。 证明： 取 个码字，每个码字的概率为 的离散无记忆信道 则： 则： 信息论与编码－－第三章 信道及信道容量 由Fano不等式： 从而 为非零值。 Shannon 第二编码定理和逆定理综合说明，在信道中信道容量是可靠传输的最大信息传输率。 信息论与编码－－第三章 信道及信道容量 线性分组码 卷积码 §3.6 信道编码原理 消息符号为M个，码源符号集中有r个元素，编码长度为N时，须有： 信息论与编码－－第三章 信道及信道容量 设码源符号集为： ，与信道输入符号集一致，编码长度为N，码字一般表示为： 其中 信源输出的符号集： ，其L次扩展信源为： ，每个消息符号对应一个L维矢量。 定义：r元符号集上的一个分组码C是由表示消息序列的，长度为N的M个r元序列构成的集合，且称为r元分组码。 信息论与编码－－第三章 信道及信道容量 例：取N=3， ，L=2， ，则消息序列为： 备选序列为： 可有的映射种类有： 种 （允许重码） 若不允许重码，则： 信息论与编码－－第三章 信道及信道容量 汉明距离：两个长为N 的r 元序列 和 之间的汉明距离定义为两者之间对应位不同的位数，以 表示。 例： 和 之间的汉明距离为3， 之间的汉明距离为2。 最小汉明距离：码C 中任何两个码字之间的最小距离，