第4章 离散信道及其容量4.1节离散无记忆信道（DMC, Discrete Memoryless Channel ）什么是 “信道”？通信的基本目标是将信源发出的消息有效、可靠地通过“信道”传输到目的地，即信宿（sink ）。
但什么是“信道”？Kelly 称信道是通信系统中“不愿或不能改变的部分”。
比如CDMA 通信中，设备商只能针对给定的频谱范围进行设备开发，而运营商可能出于成本的考虑，不愿意进行新的投资，仍旧采用老的设备。
通信是对随机信号的通信，因此信源必须具有可选的消息，因此不可能利用一个sin(·)信号进行通信，而是至少需要两个可供发射机进行选择。
一旦选择了信息传输所采用的信号，信道决定了从信源到信宿的过程中信号所受到的各种影响。
从数学上理解，信道指定了接收机接收到各种信号的条件概率(conditional probability)，但输入信号的先念概念（prior probability ）则由使用信道的接收机指定。
如果只考虑离散时间信道，则输入、输出均可用随机变量序列进行描述。
输入序列X 1,X 2,……是由发射机进行选择，信道则决定输出序列Y 1, Y 2,……的条件概率。
数学上考虑的最简单的信道是离散无记忆信道。
离散无记忆信道由三部分组成：（1） 输入字符集A ={a 1, a 2, a 3,…}。
该字符集既可以是有限，也可以是可数无限。
其中每个符号a i 代表发射机使用信道时可选择的信号。
（2） 输出字符集B={b 1, b 2, b 3,…}。
该字符集既可以是有限，也可以是可数无限。
其中每个符号bi 代表接收机使用信道时可选择的信号。
（3） 条件概率分布P Y |X (·|X )，该条件分布定义在B 上，其中X ∈A 。
它描述了信道对输入信号的影响。
离散无记忆的假设表明，信道在某一时刻的输出只与该时刻的输入有关，而与该时刻之前的输入无关。
或者：1111|(|,...,,,...,)(|)n n n Y X n n P y x x y y P y x --=，n =1,2,3….Remark: (1) n x 在信道传输时受到的影响与n 时刻以前的输入信号无关。
(2) DMC 是时不变的，即|n n Y X P 与n 无关。
因此|(|)n n Y X n n P y x 可简写为|(|)Y X n n P y x 。
例 4.1 （二进制对称信道，BSC ） (b) 二进制擦除信道例 4.2 BSC 信道假设的合理性：考虑一个通信系统，其发射机采用二进制频移键控(BPSK)方式发射信号，即采用两个不同频率的正弦信号分别代表“0”和“1”。
发射机每毫秒产生一个脉冲，代表“0”和“1”，该信号通过宽带信道进行传输。
接收机每毫秒对接收到的信号作一次 “硬判决”，由于传输媒介中噪声和接收机前端热噪声的影响，该判决会存在误差。
如果带宽足够宽，则各次判决之间的误差是独立。
此时，该信道可以用BSC 进行建模。
本课程只讨论不带反馈的离散无记忆信道，即条件分布满足：111111(|,...,,,...,)(|,...,)n n n n n P x x x y y P x x x ---= 注意这个假设并不代表各个输入i x 之间相互独立。
定理4.3 对于离散无记忆信道，条件分布满足： 111|1(,...,,|,...,)(|)nn n n Y Xi i i P y y y x x Py x -==∏ n =1,2,3….证明：111111111(,...,,,...,)(|,...,,,...,)(|,...,,,...,)n n i i i i i i P x x y y P x x x y y P y x x y y ---= 11|1(|,...,)(|)nii Y X i i i P x x xP y x -==∏g11|11(|,...,)(|)n n j j Y X i i j i P x x x P y x -==⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦∏∏1|1(,...,)(|)nn Y Xi i i P x x Py x ==∏两边同时除于1(,...,)n P x x ，即得到所需要的等式。
该定理经常被错误地用作DMC 的定义！在应用该定理作为DMC 的定义时，一般都隐含地假设了信道是无反馈的。
例4.4 BSC 信道的条件概率为()()()()0|010|11|01|11p y x p y x p y x p y x εεεε===-=========-图4.1 二元对称信道发送长度为N 的分组()12,,...,N N x x x =x 时，()()()(),,|1N NN Nd N d NNp εε-=-x y x y y x()(),11N Nd Nεεε⎛⎫=- ⎪-⎝⎭x y其中()12,,...,N N y y y =y 为接收到的数据分组，(),N Nd x y为这两个分组之间的汉明距离。
所谓汉明距离指的是两个分组之间不同比特的个数，比如d(000, 111)=3, d(101, 011)=2。
定理4.5 对于无反馈离散无记忆信道，如果n 1≥,()()1;;nNNiii I I X Y =≤∑x y证明。
因为信道是DMC 信道，()()1||nNNiii p p y x ==∏y x因此，有()()|log |N N N N H E p =-y x y x()1log |ni i i E p y x ==-∏()1log |ni i i E p y x ==-∑()1|ni i i H y x ==∑从而有()()();|N N N N N I H H =-x y y y x()()1|nNiii H H y x ==-∑y()()11|nn i i i i i H y H y x ==≤-∑∑()1;ni i i I X Y ==∑可以看到等式成立的条件是()()1nNii H H y ==∑y即输出分组Ny 是独立的。
定理4.6 如果信源是离散无记忆信源(DMS: Discrete Memoryless Source)，则有()()1;;nNNiii I I X Y =≥∑x y证明. 因为信源是无记忆信源，所以()()()()12...N N p p x p x p x =x因此有()()log N N H E p =-x x()()()12log ...N E p x p x p x =-()1log Ni i E p x ==-∑()1ni i H x ==∑考虑条件熵()|N N H x y()12...|N N H x x x =y()11|,Ni N i i H x -==∑x y()1|Ni i i H x y =≤∑最后一个不等式利用了条件会降低熵。
现在考虑两分组之间的互信息：()()();|N N N N N I H H =-x y x x y()()1|nNN ii H x H ==-∑xy()()11|nNi i i i i H x H x y ==≥-∑∑()1;ni i i I X Y ==∑等式成立的条件是，当且仅当对任意的i ，有()()1|,|i N i i i H x H x y -=x y等价于说()()1|,|i N i i i p x p x y -=x y证明完毕。
注释1. 定理4.5中，如果信源是无记忆的，则()()()()12...N N p p x p x p x =x计算输出分组的概率：()(),NN N N p p =∑x y x y()()|NN N N p p =∑x x y x()()|Ni i i ip x p y x =∑∏x(),Ni i ip x y =∑∏x()i ip y =∏即输出分组也是独立的，此时有：()()1;;nNNiii I I X Y ==∑x y注释2. 在定理4.6中，如果信道是离散无记忆信道，即()()1||nNNiii p p y x ==∏y x可以计算出()()(),|N N N N Np p p =x y x y y()()()|NNNNp p p =y x x y()()()|i i i ii p y x p x p y =∏（分别由信道是DMC ，信源是DMS 和注释1得到）()|i i ip x y =∏因此()|NNH x y()1|Niii H x y ==∑从而有()()1;;nNNiii I I X Y ==∑x y两个定理在附加的条件下达到的结论相同。
从而，由定理4.5，定理4.6和相关的注释，得到下面这个定理：定理4.7 如果信源是离散无记忆信源，信道是离散无记忆信道，则()()1;;nNNiii I I X Y ==∑x y4.2节 信道容量在通信系统中，信道由条件概率()|p y x 确定，而且一般情况下信道是给定的。
比如设备制造商开发新的移动通信设备，必须在指定的频段使用，并且满足国家相关部门制定的入网标准。
但通信系统中传输信息的用户可以自由的选择()p x ，来最大化传输的速率。
基于这个考虑，很自然定义信道容量如下。
定义4.8 定义信道容量为通过选择()p x ，离散无记忆信道能获得的最大平均互信息，即()()max ;p x C I X Y =()()()max |p x H Y H Y X =-⎡⎤⎣⎦例4.9 无噪声二元信道图4.2 无噪声二元信道该信道的任意二元输入都能在输出端正确接收。
因此，每次可以无差错传输1比特，因此C=1。
也可以通过定义来计算，采用等概输入，可以计算出C=1.例4.10 二元对称信道()()();|I X Y H Y H Y X =-()()()|xH Y p x H Y X x =-=∑()()()xH Y p x h ε=-∑()()H Y h ε=- ()1h ε≤-等式成立的条件是输出Y 等概。
当输入服从一致分布时，即()()1201p X p X ==== 输出的分布：()()()()0011p Y p X p X εε===-+=()121εε=-+⎡⎤⎣⎦=12()()()()()112211101p Y p X p X εεεε===-+==-+=⎡⎤⎣⎦即一致输入导致一致输出，()1C h ε=-bits例4.11 二元删除信道（BEC, Binary Erasure Channel ）图4.3 BEC 信道该信道的特点是，信源传输0或1时，接收端以1α-的概率正确接收，以概率α被删除。
被删除的信息无法恢复。
但是信息不会被错误接收，即0不会被翻转为1, 1也不会翻转为0。
()()max ;p x C I X Y =()()()max |p x H Y H Y X =-⎡⎤⎣⎦()()()max p x H Y h δ=-其中()()()||xH Y X p x H Y X x ==∑()()()()0|01|1p X H Y X p X H Y X ===+==()()()()01p X h p X h δδ==+=()h δ=()h δ为二元熵，即()h δ()()log 1log 1δδδδ=----直观的猜测是BEC 的容量为()log3h δ-，因为由表达式C=()()()max p x H Y h δ-猜测当Y服从一致分布时，H(Y)=log3。