1、第四章 离散信道及其容量离散信道及其容量n什么是什么是“信道信道”？nKelly：不愿或不能改变的部分n信源必须是随机的n信道决定了从信源到信宿的过程中信号所受到的各种影响n信道指定了接收机接收到各种信号的条件概率。输入信号的先念概念则由使用信道的接收机指定2023-1-171DMCn数学上：输入、输出均可用随机变量序列进行描述，输入序列X1,X2,是由发射机进行选择，信道则决定输出序列Y1,Y2,的条件概率nDMC由三部分组成 输入字符集A=a1,a2,a3,输出字符集B=b1,b2,b3,条件概率分布PY|X(|X)，描述了信道对输入信号的影响2023-1-172n离散无记忆：信道在某一时
2、刻的输出只与该时刻的输入有关，而与该时刻之前的输入无关。n1.xn在信道传输时受到的影响与n时刻以前的输入信号无关。n2.DMC是时不变的2023-1-1731111|(|,.,.,)(|)nnnY XnnP yxxyyPyxBSC（二元对称信道）nEpslon为交叉概率2023-1-1740|010|11|01|11p yxp yxp yxp yx BSC解释n考虑一个通信系统，其发射机采用二进制频移键控(BPSK)方式发射信号，即采用两个不同频率的正弦信号分别代表“0”和“1”。发射机每毫秒产生一个脉冲，代表“0”和“1”，该信号通过宽带信道进行传输。接收机每毫秒对接收到的信号作一次“硬判
3、决”，由于传输媒介中噪声和接收机前端热噪声的影响，该判决会存在误差。如果带宽足够宽，则各次判决之间的误差是独立。此时，该信道可以用BSC进行建模。2023-1-175传输.n发送长度为N的分组2023-1-17612,.,NNx xxx,|1NNNNdN dNNpxyxyyx,11NNdNxy汉明距离n汉明距离：两个分组之间不同比特的个数，比如d(000,111)=3,d(101,011)=2。2023-1-177,NNd xyBEC 二元擦除信道nDelta为擦除概率2023-1-178n本课程只讨论不带反馈的离散无记忆信道，即条件分布满足这个假设并不代表各个输入xi之间相互独立2023-1
4、-179111111(|,.,.,)(|,.,)nnnnnP xxxyyP xxx定理n对于离散无记忆信道，条件分布满足：n证明2023-1-1710111|1(,.,|,.,)(|)nnnnY XiiiP yyyxxPyx1111|1(,.,.,)(|,.,)(|)nnniiY XiiiP xxyyP xxxPyx11|11(|,.,)(|)nnjjY XiijiP xxxPyx1|1(,.,)(|)nnY XiiiP xxPyx定理n对于无反馈离散无记忆信道证明.信道是DMC信道2023-1-17111;nNNiiiII X Yxy1|nNNiiipp yxyx2023-1-1712|lo
5、g|NNNNHEp yxyx1log|niiiEp yx 1log|niiiEp yx 1|niiiH yx;|NNNNNIHHxyyyx1|nNiiiHH yxy11|nniiiiiH yH yx1;niiiI X Yn等式成立的条件是即输出分组是独立的2023-1-17131nNiiHH yy评论n该定理中，如果信源是无记忆即独立输入导致独立输出2023-1-1714 12.NNpp xp xp xx,NNNNppxyxy|NNNNppxxyx|Niiiip x p yxx,Niiip x yxiip y1;nNNiiiII X Yxy定理n如果信源是离散无记忆信源，则有证明.DMS，20
6、23-1-17151;nNNiiiII X Yxy 12.NNpp xp xp xxlogNNHEp xx 12log.NEp xp xp x 2023-1-1716 1logNiiEp x 1niiH x|NNH xy12.|NNH x xxy11|,NiNiiH xxy1|NiiiH xy;|NNNNNIHHxyxxy 1|nNNiiH xHxyn等式成立的条件n等价于2023-1-171711|nNiiiiiH xH xy1;niiiI X Y1|,|iNiiiH xH xyxy1|,|iNiiip xp xyxy评论n如果信道是离散无记忆信道2023-1-17181|nNNiiipp
7、yxyx,|NNNNNpppxyxyy|NNNNpppyxxy|iiiiip yxp xp y|iiip xy1|NNNiiiHH xyxy1;nNNiiiII X Yxy定理n如果信源是离散无记忆信源，信道是离散无记忆信道，则2023-1-17191;nNNiiiII X Yxy4.2 信道信道容量容量n在通信系统中，信道由条件概率p(y|x)确定，而且一般情况下信道是给定的。比如设备制造商开发新的移动通信设备，必须在指定的频段使用，并且满足国家相关部门制定的入网标准。但通信系统中传输信息的用户可以自由的选择p(x)，来最大化传输的速率。2023-1-1720容量定义n定义离散无记忆信道的容
8、量为：max;p xCI X Y max|p xH YH Y X无噪声二元信道n例1：无噪声二元信道每次传输的比特能精确接收，容量为1bit。也可以用公式计算，容量在输入等概时取得。2023-1-1722例2.BSC容量n二元对称信道容量，交叉概率为epslon;|I X YH YH Y X|xH Yp x H Y Xx2023-1-1724 xH Yp x h H Yh 1 h 1201p Xp X00 11p Yp Xp X11221112211 101p Yp Xp X 1Ch 例3 BEC容量 max;p xCI X Y max|p xH YH Y X maxp xH Yh|xH Y
9、Xp x H Y Xx0|0.1|1p XH Y Xp XH Y X 01p Xhp Xh hBEC 看起来似乎H(Y)的最大值是log3，但可惜不论如何选择选择输入分布都取不到这个值，进一步猜测输入X分布为等概时，Y会等概。但这个猜测是错误，X等概时 进一步的证明，无论采用怎样的输入分布，输出Y都无法等概，或H(Y)无法取得最大值log3。2023-1-17261200 11p Yp X1211 11p Yp X01p Yep Xp Xn设E代表事件Y=e，Pr(1)X,H YH Y E|H EH Y E00 111p Yp X11 11p Yp Xp Ye 11,1,H YH11log 1
10、11log1log 11log 111log 1.1log 11loglog 2023-1-1728 1log 111log 11loglog 11log 1logh 1hh maxp xCH Yh max 1hhh max 1h1 直观解释n取得容量的分布为输入等概n由于a比例的信息在传输中被删除，且无法恢复，因而能够恢复的信息比例最多为1-a，从而最大传输信息即容量为1-a。2023-1-17294.3 特殊信道的容量计算n离散输入对称信道n离散输出对称信道n对称信道n准对称信道信道转移概率矩阵nK个输入，J个输出n行对应输入，列对应输出，p(j|k)代表的是输入为k，输出为j的条件概率.
11、n每一行的和是11|1.|1.1|.|pp JpKp J Kp1|1Jjp j kn列的和不一定是1，如BECnBSC2023-1-17321001p11p1.离散输入对称信道离散输入对称信道n定义：若信道转移概率矩阵所有行矢量都是第一行的置换，或者说离开每个输入节点的条件分布集合都相同。1122112200p1.离散输入对称信道离散输入对称信道n定理：对于离散输入对称信道，H(Y|X)与p(x)无关，且 其中 是离开每个节点的转移概率集合，也是转移矩阵每行的元素集合121(|)log(,.,)JjjJjH Y XppH p pp 12,.,Jp pp1.离散输入对称信道离散输入对称信道证：例
12、：BSC:例：BEC:1(|)logJjjjH Y Xkpp(|)(,1)()H Y XHh(|)(,1)()H Y XHh|xH Y XH Y Xx p x 1logJjjjxppp x 1logJjjjpp 1.离散输入对称信道离散输入对称信道n容量：容量的计算转化为计算：()()()max(;)max()(|)max()(|)p xp xp xCI X YH YH Y XH YH Y X()max()p xH Y2.离散输出对称信道n定义：如果P的每一列都是第一列的置换。或者说进入每个输出节点的条件分布集合都相同。n引理：对于离散输出对称信道，如果输入服从均匀分布p(x)=1/K，则输出
13、也服从均匀分布p(y)=1/J。即一致输入会导致一致输出。引理证明n注意到 代表的是进入输出节点y的K个条件概率的和2023-1-1738,xp yp x y|xp x p y x1|xp y xK|xp y x定理n定理3：对于离散输出对称信道，有 且取得该值的输入分布为一致分布，即p(x)=1/K证明：由引理2知一致输入可得到一致输出，一致输出可得到最大熵logJ例：BSC是离散输出对称信道，BEC不是()max()logp xH YJ3.对称信道n定义：同时满足输入对称和输出对称的离散信道n容量：()()max(;)max()(|)p xp xCI X YH YH Y X()1max()
14、(|)logp xJjjH YH YXJpn例：BSC信道容量取得该容量的输入分布为2023-1-1741log2log(1)log(1)1()Ch(0)(1)0.5p Xp X准对称信道nBEC信道不是对称信道，但该信道有明显的对称性！BEC可以分解为如下两个对称信道：分解成：输入以概率 选择信道C1和C21001P101011 (1-)和(1-)和2023-1-1743准对称信道n定义 准对称信道：如果该DMC能分解成L个对称信道。n定理：如果各对称信道被选择的概率为 对应的L个对称信道的容量为 ，则准对称信道容量为12,.,Lq qq12,.,LC CC1LiiiCq Cn推论：准对称信
15、道必为离散输入对称。n判断方法：将矩阵P按输出Y进行划分，如果能分解成L个对称矩阵，则为准对称信道。nRemark：取得准对称信道容量的输入分布为等概分布。2023-1-1745例1：转移矩阵不是对称信道，但是准对称信道，可分解为：8.01.01.01.01.08.0P0.8 0.10.8/0.9 0.1/0.90.90.1 0.80.1/0.9 0.8/0.910.11 120.8 0.10.90.10.9 log2,0.1 00.44710.9 0.9CCCHbits 例2 K元对称信道n转移概率为转移矩阵如下，该信道为对称信道，容量为1111111.1.1ppKKppKKppKKppPp2023-1-174811log(1,.,)ppKKCKHp 共K-1项1log(1)log(1)logloglog(1)()pKKpppKpKH pEND2023-1-1749
