4.信道及其容量

第4章 离散信道及其容量 4.1节 离散无记忆信道（DMC, Discrete Memoryless Channel） 什么是 “信道”？ 通信的基本目标是将信源发出的消息有效、可靠地通过“信道”传输到目的地，即信宿（sink）。但什么是“信道”？ Kelly称信道是通信系统中“不愿或不能改变的部分”。比如CDMA通信中，设备商只能针对给定的频谱范围进行设备开发，而运营商可能出于成本的考虑，不愿意进行新的投资，仍旧采用老的设备。通信是对随机信号的通信，因此信源必须具有可选的消息，因此不可能利用一个sin(·)信号进行通信，而是至少需要两个可供发射机进行选择。一旦选择了信息传输所采用的信号，信道决定了从信源到信宿的过程中信号所受到的各种影响。从数学上理解，信道指定了接收机接收到各种信号的条件概率(conditional probability)，但输入信号的先念概念（prior probability）则由使用信道的接收机指定。 如果只考虑离散时间信道，则输入、输出均可用随机变量序列进行描述。输入序列X1, X2,……是由发射机进行选择，信道则决定输出序列Y1, Y2,……的条件概率。数学上考虑的最简单的信道是离散无记忆信道。 离散无记忆信道由三部分组成： （1） 输入字符集A={a1, a2, a3,…}。该字符集既可以是有限，也可以是可数无限。其中每个符号ai代表发射机使用信道时可选择的信号。 （2） 输出字符集B={b1, b2, b3,…}。该字符集既可以是有限，也可以是可数无限。其中每个符号bi代表接收机使用信道时可选择的信号。 （3） 条件概率分布PY|X(·|X)，该条件分布定义在B上，其中X∈A。它描述了信道对输入信号的影响。 离散无记忆的假设表明，信道在某一时刻的输出只与该时刻的输入有关，而与该时刻之前的输入无关。或者： ，n=1,2,3…. Remark: (1) 在信道传输时受到的影响与n时刻以前的输入信号无关。 (2) DMC是时不变的，即与n无关。因此可简写为。 例 4.1 （二进制对称信道，BSC）  (b) 二进制擦除信道 例 4.2  BSC信道假设的合理性：考虑一个通信系统，其发射机采用二进制频移键控(BPSK)方式发射信号，即采用两个不同频率的正弦信号分别代表“0”和“1”。发射机每毫秒产生一个脉冲，代表“0”和“1”，该信号通过宽带信道进行传输。接收机每毫秒对接收到的信号作一次 “硬判决”，由于传输媒介中噪声和接收机前端热噪声的影响，该判决会存在误差。如果带宽足够宽，则各次判决之间的误差是独立。此时，该信道可以用BSC进行建模。     本课程只讨论不带反馈的离散无记忆信道，即条件分布满足：             注意这个假设并不代表各个输入之间相互独立。 定理4.3  对于离散无记忆信道，条件分布满足：                   n=1,2,3….   证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ：                                                                                     两边同时除于，即得到所需要的等式。   该定理经常被错误地用作DMC的定义！在应用该定理作为DMC的定义时，一般都隐含地假设了信道是无反馈的。 例4.4  BSC信道的条件概率为 图4.1 二元对称信道 发送长度为N的分组时， 其中为接收到的数据分组，为这两个分组之间的汉明距离。所谓汉明距离指的是两个分组之间不同比特的个数，比如d(000, 111)=3, d(101, 011)=2。 定理4.5  对于无反馈离散无记忆信道，如果n, 证明。因为信道是DMC信道， 因此，有 从而有 可以看到等式成立的条件是 即输出分组是独立的。 定理4.6  如果信源是离散无记忆信源(DMS: Discrete Memoryless Source)，则有 证明. 因为信源是无记忆信源，所以 因此有 考虑条件熵 最后一个不等式利用了条件会降低熵。 现在考虑两分组之间的互信息： 等式成立的条件是，当且仅当对任意的i，有 等价于说 证明完毕。 注释1. 定理4.5中，如果信源是无记忆的，则 计算输出分组的概率： 即输出分组也是独立的，此时有： 注释2. 在定理4.6中，如果信道是离散无记忆信道，即 可以计算出 （分别由信道是DMC，信源是DMS和注释1得到） 因此 从而有 两个定理在附加的条件下达到的结论相同。从而，由定理4.5，定理4.6和相关的注释，得到下面这个定理： 定理4.7  如果信源是离散无记忆信源，信道是离散无记忆信道，则 4.2节  信道容量 在通信系统中，信道由条件概率确定，而且一般情况下信道是给定的。比如设备制造商开发新的移动通信设备，必须在指定的频段使用，并且满足国家相关部门制定的入网标准。但通信系统中传输信息的用户可以自由的选择，来最大化传输的速率。 基于这个考虑，很自然定义信道容量如下。 定义4.8 定义信道容量为通过选择，离散无记忆信道能获得的最大平均互信息，即 例4.9 无噪声二元信道 图4.2 无噪声二元信道 该信道的任意二元输入都能在输出端正确接收。因此，每次可以无差错传输1比特，因此C=1。也可以通过定义来计算，采用等概输入，可以计算出C=1. 例4.10 二元对称信道 等式成立的条件是输出Y等概。当输入服从一致分布时，即 输出的分布： = 即一致输入导致一致输出， bits 例4.11 二元删除信道（BEC, Binary Erasure Channel） 图4.3 BEC信道 该信道的特点是，信源传输0或1时，接收端以的概率正确接收，以概率被删除。被删除的信息无法恢复。但是信息不会被错误接收，即0不会被翻转为1, 1也不会翻转为0。 其中 为二元熵，即 直观的猜测是BEC的容量为，因为由表达式C=猜测当Y服从一致分布时，H(Y)=log3。进一步猜测输入X分布为等概时，Y会等概。但这个猜测是错误的，事实上，当X等概时， 要输出等概则要求，即，但删除概率是个变量。可以进一步的证明，无论采用怎样的输入分布，输出Y都无法等概，或H(Y)无法取得最大值log3。 现在我们来计算BEC的容量。令E代表删除事件，，则 第一个等式用到E是Y的函数。考虑输出Y的分布： 因此 因此 = 取得最大值的输入分布为等概分布，即当时。 直观的理解：由于比例的信息在传输中被删除，且无法恢复，因而能够恢复的信息比例最多为1-，从而最大传输信息即容量为1-。 4.3节  特殊信道的容量计算 从上面例子可以看出，即使对于很简单的信道，比如BSC, BEC，计算它们的容量也比较复杂。事实上，信道容量的计算是一个非常复杂的问题，但是如果信道满足一些特定的条件，具有比较好的结构，它的容量的计算可能会得到极大的简化。 信道由从输入到输出的条件转移概率p(j|i)来描述。假设输入X的字母表为{ 1, 2, …, J}，输出字母表为{1, 2, …, K}，则描述信道的条件转移概率共有KJ个。把这些概率写成矩阵的形式，得到 矩阵称为信道转移矩阵，注意矩阵的行对应的是输入，列对应的是输出。矩阵中元素代表的是输入为j，输出为k的条件概率。注意到这个矩阵的每一行的和是1，即 =1, j=1, 2, …, J 但是列的和不一定是1，比如BEC信道，它的信道转移矩阵为： BSC信道的转移矩阵为 其中为交叉概率。 4.3.1 离散输入对称信道容量的计算 定义4.12（离散输入对称信道）. 如果信道转移矩阵p的每一行都是其他行的置换，则称该信道为离散输入对称信道。或者说，离开每个输入节点的条件概率都相同。 例4.13. 图4.4 可以写出信道转移矩阵为 除了出现的次序，两行的元素相同，都是0,1/2,1/2。 引理4.14 对于输入对称的离散无记忆信道，条件熵H(Y|X)与输入分布p(x)无关，且 其中是离开每个输入符号节点的条件概率。 证明. 由离散输入对称的定义马上可得： 因此 证明完毕。 例4.15 由离散输入对称信道的定义很容易判断出BSC和BEC信道都是离散输入对称信道。对于BSC信道 对于BEC信道 例4.13中信道的条件熵。 根据该引理和容量的定义，可以得出离散输入对称DMC信道的容量为   这样，输入对称DMC信道容量的计算问题就转化为通过选择p(x)最大化H(Y)，目标是计算 4.3.2 离散输出对称信道容量的计算 定义4.16（离散输出对称信道）. 如果信道转移矩阵p的每一列都是其他列的置换，则称该信道为离散输出对称信道。或者说，进入每个输出节点的条件概率都相同。 引理4.17 对于离散输出对称DMC信道，如果，则。即服从一致分布的输入能得到服从一致分布的输出。 证明. 考虑 注意到代表的是进入输出节点y的J个条件概率的和，根据输出对称的定义，进入每个输出节点的条件概率相同，因此对每个输出节点都相同，从而是常数，因此 证明完毕。 由该引理和输出对称的定义马上可以得到，对于离散输出对称DMC信道 且取得最大值的输入分布为。 例4.18 可以判断出BSC信道是输出对称信道，BEC不是。 4.3.3 对称信道容量的计算 定义4.19（对称信道） DMC信道如果既是输入对称信道，又是输出对称信道，则称为对称信道。 根据对称信道的定义可知，对称信道的信道转移矩阵的每一行都是其他行的置换，并且每一列都是其他列的置换。 综合引理4.14和引理4.17可以很容易计算出对称信道的容量。 定理4.20 一个具有J个输入，K个输出的离散无记忆对称信道的容量为 其中是离开每个输入符号节点的条件概率，也是矩阵p的任意行的元素。取得容量的输入分布为为一致分布，即 证明. 引理4.17保证了一致输入导致一致输出，从而取得容量。证明完毕。 例4.21  BSC信道的容量 =1 4.3.4 准对称信道容量的计算 从上面的讨论可以看到，对称信道的容量计算非常简单，但很多信道具有明显的对称结构，比如BEC，但不是对称信道。引理4.17表明取得容量要求输入的分布能导致出一致的输出分布，我们希望能推广“对称”的概念，把BEC这类的信道也包括进来。尽管BEC不是对称信道，但仔细分析可以发现BEC可以分解为两个对称信道： 图4.5 可以这样理解，BEC信道在确定了要发送的输入符号后，以概率选择使用信道1，以概率选择使用信道2来传输该符号，进一步的信道分解图如下 图4.6 定义4.22（离散准对称信道）一个DMC信道，如果存在整数L，使得该信道可以分解为L个对称子信道，相应的选择概率为，则称该DMC信道为离散准对称信道。 定理4.23 准对称DMC信道的容量为 其中是L个子对称信道的容量，是相应的选择的选择概率。 例4.24 由图4.5和图4.6可以看出，BEC可以分解为两个对称信道，且，。因此BEC容量为 定理4.23的证明. 定义随机变量Z。当输出字符属于第i个子对称信道的输出符号集时，令Z=i。因此Z是Y的函数，从而H(Z|Y)=0。进一步，由Z的定义，即Z可以用来标示信息传输时所选择的子信道。另外，根据假设，Z与X统计独立。 =                                             考虑到X与Z独立 =0 因此 代入公式（）和（），则互信息为 用代表第i个子信道的互信息，每个子信道的输入分布与准对称信道的输入分布相同，即，则有 等式成立的充分必要条件是为一致分布。 因为 因此 从而 当为一致分布时，所有的子信道同时取得容量，从而，准对称信道取得容量。 证明完毕。 注释1：一般情况下，等式成立的条件是输入分布使得所有的子信道同时取得它的容量。 注释2：准对称信道一定是离散输入对称信道。准对称信道在进行信道矩阵分割的时候，是把它的列分割成互斥的子集，每个子集的列都相同（置换！），而每一行元素都相同，是其他行的置换。 例4.25 给定DMC信道的转移矩阵为 观察转移矩阵，第二行是第一行的置换，因此是输入对称信道，但第二列不是其他列的置换，不是输出对称信道。该矩阵可以分解为两个对称矩阵，因此是准对称信道，这两个子信道为： 即第一个子信道是二元对称信道，选择概率， 即第二个子信道的选择概率，这个信道是个纯噪声信道， 因此，该信道容量为 bits 例4.26（K元对称信道）K元对称信道指的是概率转移矩阵具有如下形式的DMC信道 观察这个转移矩阵，可以发现每行都是第一行的置换，每列都是第一列的置换，所以这是一个对称矩阵，其容量为 4.4节 信道编码定理（概要） 考虑如下图所示通信系统 图 消息W取自消息集{1, 2, …, M}，经编码器后生成信号，经过信道传输后，接收到的序列为，接收机采用适当的译码器对进行判决，得到关于消息W的一个估计，如果，则接收机宣布出现了错误。 定义4.25. 离散信道（A, p(y|x), B），A和B分别是输入、输出的字母表，p(y|x)代表信道转移概率，，，X和Y分别看着信道的输入和输出。 定义4.26. DMC的n次扩展指信道，其中 定义4.27. 信道（A, p(y|x), B）的（M, n）码序列由以下几个部分组成构成： 1． 指标集{1, 2, …, M}。 2． 编码函数 生成码字。所有码字的集合称为码本（codebook） 3． 译码函数 译码函数对每个接收到的向量进行判决，给出消息的估计。 定义4.28（条件误差概率）令 为当发送消息为i，但接收机判决出的消息却不为i时的条件概率，I(.)为示性函数。 定义4.29 （M, n）码的最大误差概率定义为 定义4.30 （M, n）码的平均误差概率定义为 显然 如果消息从指标集中按一致分布选择，，则 定义4.31 （M, n）码的码率R定义为 bits per transmission 定义4.32 如果存在一个码序列，当时，，则称码率R可达。 定义4.33 信道容量定义为所有可达码率的上确界。 联合典型序列 粗糙地讲，如果码字与接收到的序列是联合典型，则将译为消息i。我们来定义联合典型的概念、计算正确译码概率和差错概率。 定义4.34 联合典型序列集指的是经验熵和真实熵相差不超过，长度为n的序列对构成的集合，其中X和Y服从联合分布。 其中 定理4.35（联合典型）设为服从的独立同分布、长度为n的序列对，则 1． 当时，。 2． 3． 如果，即与独立，且与有相同的边际分布，那么 并且，对于充分大的n， 证明：略 下图是联合典型集的示意图。 图 大约有个典型的X序列，大约有个典型的Y序列。但联合典型序列个数只有个，因此并不是所以的X典型序列与Y典型序列构成的序列对都是典型的。序列对是联合典型的概率大约为。因此，大约个序列对中有一个联合典型序列对。这表明可区分的信号的个数大概是个。 考虑上述问题的另一种方式是与固定输出序列联合典型的序列的集合。假设真实的输入信号是，对于该，大约有个条件典型输入信号与该构成联合典型序列。某个随机选择的输入信号与联合典型的概率为 这再次表明可以选择大约个码字，同时保证这些码字不会与输出序列对应的真实码字想混淆。 香农信道编码定理表明只要传输的码率小于信道容量，信息就可以在该信道上可靠地传输，在证明这个定理的过程中，香农使用了很多新思想，包括： ★ 运行任意小的非0误差概率； ★ 连续使用信道多次，从而可以有效使用大数定律 ★ 在随机生成的码本上计算平均误差概率，使概率对称，从而证明至少存在一个好码。 香农的证明是基于联合典型序列的思想，严格的证明很晚才给出。所有的证明都采用的基本思想—随机码的选择、计算随机选择的码字的平均误差概率等等。 定理4.36（信道编码定理）对于DMC信道，小于容量C的所有码率都是可达的。即，对于任意的，存在一个码序列，它的最大误差概率。反之，任何满足的码序列必定有。 证明：略 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 习题