通信原理下册-全部PPT

1、通信原理通信原理II山东大学山东大学 信息科学与工程学院信息科学与工程学院 推荐参考书：推荐参考书： 信息论与编码理论信息论与编码理论 王育民王育民 等等 编著编著 高等教育出版社高等教育出版社 （2002005 5年年1212月第月第1 1版）版） 通信系统工程通信系统工程 John G. Proakis John G. Proakis， Masoud Salehi Masoud Salehi 著著 叶芝慧、赵新胜等译叶芝慧、赵新胜等译 （20022002年年7 7月第月第1 1版）版）第一章第一章 绪论绪论通信系统模型通信系统模型信源编码器信道译码器信宿干扰源通信系统模型进一步细分通信系统

2、模型进一步细分信源信源编码器信道编码器调制器信道干扰源解调器信道译码器信源译码器信宿等效离散信道等效离散信源等效信宿信道编码器信道译码器各部件功能各部件功能各部件功能各部件功能各部件功能各部件功能信息、消息和信号信息、消息和信号1.2 信息论研究的中心问信息论研究的中心问题和发展题和发展Shannon信息论的基本任务信息论的基本任务信息论的研究内容信息论的研究内容狭义信息论体系结构狭义信息论体系结构Shannon信息论压缩理论有失真编码无失真编码等长编码定理Shannon1948McMillan1953变长编码定理Shannon1948McMillan1956Huffman码(1952)、Fa

3、no码算术码(1976,1982)LZ码(1977,1978)率失真理论ShannonGallagerBerger压缩编码JPEGMPEG传输理论信道编码定理网络信息理论纠错码编码调制理论网络最佳码信息论发展简史信息论发展简史信息论发展简史信息论发展简史信息论发展简史信息论发展简史信息论发展简史信息论发展简史信息的概念信息的概念l第一个重要概念第一个重要概念：信道上传送的是随机变量的信道上传送的是随机变量的值。注意：值。注意： （1 1）这就是说，我们在收到消息之前，并不知）这就是说，我们在收到消息之前，并不知道消息的内容。否则消息是没有必要发送的。道消息的内容。否则消息是没有必要发送的。 （

4、2 2）消息随机变量有一个概率分布。）消息随机变量有一个概率分布。 （3 3）消息随机变量的一个可能取值就称为一个）消息随机变量的一个可能取值就称为一个事件事件。信息的概念信息的概念第二个重要概念：第二个重要概念： 事件发生的概率越小，此事件含有的信息量就越大。事件发生的概率越小，此事件含有的信息量就越大。（不太可能发生的事件竟然发生了，令人震惊）（不太可能发生的事件竟然发生了，令人震惊） 例例 事件事件“中国足球队中国足球队3 3：0 0力克韩国足球队力克韩国足球队”含有的含有的信息量大。（小概率事件发生了，事件信息量大）信息量大。（小概率事件发生了，事件信息量大） 例例 事件事件“中国足球

5、队中国足球队0 0：1 1负于韩国足球队负于韩国足球队”含有的含有的信息量小。（大概率事件发生了，事件信息量小）信息量小。（大概率事件发生了，事件信息量小）信息的概念信息的概念 第三个重要概念：第三个重要概念：消息随机变量的随机性越大，消息随机变量的随机性越大，此消息随机变量含有的信息量就越大。此消息随机变量含有的信息量就越大。 例例 消消息随机变量息随机变量X X=“=“中国足球队与韩国足球队比中国足球队与韩国足球队比赛的结果赛的结果”，则消息随机变量，则消息随机变量X X含有的信息量含有的信息量小。小。 （随机性小，可预见性大，因此该消息（随机性小，可预见性大，因此该消息随机变量含有的信息

6、量小。）随机变量含有的信息量小。） 例例 消息随机变量消息随机变量X X=“=“意大利足球队与德国足意大利足球队与德国足球队比赛的结果球队比赛的结果”，则消息随机变量，则消息随机变量X X含有的含有的信息量大。信息量大。 （随机性大，可预见性小，因此（随机性大，可预见性小，因此该消息随机变量含有的信息量大。）该消息随机变量含有的信息量大。） 信息的概念信息的概念l第四个重要概念：两个消息随机变量的相互依第四个重要概念：两个消息随机变量的相互依赖性越大，它们的赖性越大，它们的互信息量互信息量就越大（这里指的就越大（这里指的是绝对值大）。是绝对值大）。 例例 X X= =西安明日平均气温西安明日平

7、均气温, , Y Y= =咸阳明日平均气咸阳明日平均气温，温，Z Z= =北京明日平均气温，北京明日平均气温，WW= =纽约明日平均纽约明日平均气温。气温。 则则 X X与与Y Y互信息量大，互信息量大， X X与与Z Z互信息量小得多，互信息量小得多， X X与与WW互信息量几乎为互信息量几乎为0 0。第二章第二章 信息量和熵信息量和熵信息量和熵信息量和熵l2.1 离散变量的非平均信息量离散变量的非平均信息量l2.2 离散集的平均自信息量熵离散集的平均自信息量熵l2.3 离散集的平均互信息量离散集的平均互信息量l2.4 连续随机变量的互信息和熵连续随机变量的互信息和熵l2.5 凸函数和互信息

8、的凸性凸函数和互信息的凸性2.1 离散变量的非平均信离散变量的非平均信息量息量输入，输出空间定义输入，输出空间定义非平均互信息量非平均互信息量l例例2.1.1X1X2X3X4X5X6X7x80000010100111001011101111/81/81/81/81/81/81/81/81/41/41/41/40000001/21/2000000010000非平均互信息量非平均互信息量输入消息输入消息码字码字p(xk)收到收到0收到收到01收到收到011X1X2X3X4X5X6X7x80000010100111001011101111/81/41/81/41/161/161/161/161/61

9、/31/61/30000001/32/3000000010000非平均互信息量非平均互信息量l例2.1.2输入消息码字p(xk)收到0收到01收到011X1X20001111/21/21-pp1/21/21-pp1-p1-p0011pp非平均互信息量非平均互信息量)|(),();(jkkjkyxpxqfyxI)|;()|;();();(213121jjjkjjkjkjkyyyxIyyxIyxIyxI);()()|(log)()|(log);(kjjkjakjkajkxyIyxypxqyxpyxI条件互信息和联合事件互信息条件互信息和联合事件互信息l三个事件集的条件互信息定义为l可以推广到任意有

10、限多个空间情况)|()|()|(log)|()|(log)|;(323132131321321uupuupuuupuupuuupuuuI互信息的可加性互信息的可加性系统u1u2u3系统u1u2u3)|;();()|;();();(3213123121321uuuIuuIuuuIuuIuuuI离散变量的非平均自信息量离散变量的非平均自信息量)(log)(1log)()|(log);(kkkjkjkxqxqxqyxpyxI)(log)(1log)(kkkxqxqxI非平均自信息的性质非平均自信息的性质l非负l体现先验不确定性大小)();()();(jjkkjkyIyxIxIyxI条件自信息和联合自

11、信息条件自信息和联合自信息)|(log)|(2121uupuuI)(log)(jkjkyxpyxI)|()()|()();(kjjjkkjkxyIyIyxIxIyxI自信息、条件自信息和互信息自信息、条件自信息和互信息)()()();(jkjkjkyxIyIxIyxII(xk)I(yj)I(xk ;yj)2.2 离散集的平均自信离散集的平均自信息量熵息量熵熵熵)(log)()(xqxqxH集X中事件出现的平均不确定性例2.2.1 H(p)例2.2.2条件熵和联合熵条件熵和联合熵xyyxpxypYXH)|(log)()|( XY独立时有H(X|Y)=H(X)|()()|()()()(log)()

12、(YXHYHXYHXHXYHxypxypXYHxy熵的性质熵的性质l对称性l非负性l确定性l扩展性l可加性l极值性l是H(P)上凸函数熵的性质可加性熵的性质可加性lH(p1q11,p1q12,p4q44)=H(p1,p4)+p1H(q11,q14)+p4H(q41,q44)p1p2p3p4q11q12q13q14熵的极值性熵的极值性l引理1: lnxx-1熵的极值性熵的极值性l引理2：lH(X|Y) H(X)lH(U1UN) H(U1)+H(UN)11log),(kkkKqpppH熵的凸性熵的凸性lH(P)是P的上凸函数)()1 ()()1 (2121PHPHPPH2.3 离散集的平均互信息离

13、散集的平均互信息量量平均互信息量平均互信息量xyxqyxpxypYXI)()|(log)();(1.非负性2.对称性3. )|()()()|()()|()();(YXHYHXHXYHYHYXHXHYXI平均互信息量平均互信息量4. I(X;Y)H(X) ,I(X;Y)H(Y)H(X)H(Y)I(X;Y)H(Y|X)H(X|Y)条件互信息条件互信息xyzzxpzxypxyzpZYXI)|()|(log)()|;()|()|()|;(YZXHZXHZYXI)|;();()|;();();(ZYXIZXIYZXIYXIYZXI信息处理定理信息处理定理lZ出现情况下，X和Y独立,构成一个马氏链系统1系

14、统2XYZ(| )( | ) ( | )(;|)0(|)(|)p xy zp x z p y zI X Y ZH X YZH X Z信息处理定理信息处理定理);();()|()|(YXIZXIYXHZXH2.4 连续随机变量的互信连续随机变量的互信息和相对熵息和相对熵连续随机变量的互信息连续随机变量的互信息 dxdyypxpxypxypYXIYXXYXY)()()(log)();()|;();();();();()|;()|;();();(0);(XZYIZXIZXYIYXIZXIZXYIZYXIXYIYXIYXI例例:求互信息求互信息2222)()1 (21exp121)(xxyxXYmxx

15、yp22)()(2uyyxyxmymymxxXYXdyxypxp21)()(221exp()2xxxmyXYYdxxypyp21)()(221exp()2yyym例例:求互信息求互信息 dxdyypxpxypxypYXIYXXYXY)()()(log)()( ；yxyxxxmymxmxn)1 ()(2)1 ()(2111122222dxdyxypmymxmyXYyyxxyy)()()()1 ()(22222221111121121)1 (12122222n)1 (1212n 随机变量的相对熵随机变量的相对熵(微分熵微分熵)dxxpxpxHXXc)(log)()(均匀分布的相对熵均匀分布的相对熵

16、),(0),(1)(baxbaxabxpbaCabndxabnabXH)(1)(11)(高斯分布的相对熵高斯分布的相对熵21)(xp221exp()2xmdxmxnxpXHC22)(21211)()()(222212ln21)(XHcceeexH熵功率相对熵的极大化相对熵的极大化l1.峰值功率受限l均匀分布相对熵最大l2.平均功率受限l高斯分布相对熵最大l3.平均功率大于等于熵功率2.5 凸函数与互信息的凸凸函数与互信息的凸性性凸函数凸函数l凸集R：a，b属于R，a(1)b也属于R，其中01l概率矢量矢量a的所有分量和为1l上凸函数)1 ()()1 ()(babafff凸函数的性质凸函数的性质

17、1.f(a)是上凸的，f(a)是下凸的2.f1(a),fL(a)是R上的上凸函数，c1,cL是正数，c1f1(a)+cLfL(a)也是上凸函数3.f(a)是上凸函数，Ef(a)fE(a),E为求数学期望K-T条件条件lf(a)是定义域R上的上凸函数，a是概率矢量。偏导数 存在且连续， f(a)在R上为极大的 充分必要条件kaaf)(0)(0)(kkkkaaafaaaf互信息的凸性互信息的凸性xyiixypiQxypxypxqYXI)|()()|(log)|()();(p(y|x)给定，I(X;Y)是q(x)的上凸函数Q(x)给定，I(X;Y)是p(y|x)的下凸函数互信息的凸性互信息的凸性q1

18、和和q2是是X上的任意上的任意两个概率矢量，相应两个概率矢量，相应的互信息为的互信息为I1和和I2，令令满足满足0L0,错误概率小于e，R是可达的l等长编码定理lRH(U),R是可达的，RH(U)是不可达的l编码效率hH(U)/R3.3 DMS的不等长编码的不等长编码平均码长平均码长kkknapn)(几个定义几个定义l唯一可译码l逗点码，无逗点码l字头或前缀l异字头码或异前缀码l树码，满树，非满树，全树l树码构造异字头码例子例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111ShannonFano编码编

19、码lD元码l每次信源符号化为概率近似相等的D个子集l这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。l理想情况I(ak)=nklogD, p(ak)=D-nkKraft不等式不等式11KknkD不等长编码定理不等长编码定理1log)(log)(DUHnDUHLDUHnDUH1log)(log)(3.4最佳不等长编码最佳不等长编码两个定理两个定理1.对于给定信源，存在最佳唯一二元可译码，最小概率的两个码字码长相等且最长，他们之间仅最后一位不同2. 对辅助集为最佳的码，对原始集也是最佳的Huffman编码编码l例(0.20,0.19,0.18,0.17,0.15,0.10

20、,0.01)D元元Huffman编码编码l共有K个符号，概率最小的R个符号码长最长lK+B=D+m(D-1)l注意B010101010101,.,1 , 0)|(log)|(log)|(1,.,1 , 0log)|()|(log)|(1,.,1 , 0)|(JjJjjJjjJjKkkjKkkjpkjpCkjpKkCkjpkjpkjpKjkjpQ一般一般DMC的容量计算的容量计算jjjCjjjjjCCbbb2log12log4.3 信道的组合信道的组合积信道积信道lC1maxI(X1,Y1)lC2maxI(X2,Y2)l信道1和信道2同时传递消息，输入集X=X1X2,输出集Y=Y1Y2,转移概率

21、p(jj|kk)=p(j|k)p(j|k)lC=C1+C2信道1P(j|k)X1Y1信道2P(j|k)X2Y2证明证明);();(2121YYXXIYXI) () | (log) | () (kkjjjjkkjjpkkjjpkkQ) () | ()|(log) | ()|() (kkjjjjkjpkjpkjpkjpkkQ11)|(log) | ()|() ();(kkjjjkjpkjpkjpkkQYXI22) | (log) | ()|() ();(kkjjjkjpkjpkjpkkQYXI和信道和信道l单位时间内可随机选用信道1和信道2中的一个，选用信道1的概率为p1，选用信道2的概率为p2，

22、 p1 p21l输入空间X=X1+X2， Y=Y1+Y2，nnCCnNnCCCpCCPHpYXIpYXIYXI22log22log)();();();(1222211121, 22,11) | (log) | ()|(log)|();(jkjkjkjkpkjpkjpQppkjpkjpQpYXI级联信道级联信道l信道1的输出作为信道2的输入jjkjpkjpkjp)| ()|()| (4.4 时间离散的无记忆连时间离散的无记忆连续信道续信道可加噪声信道可加噪声信道lP(y|x)=p(y-x)=p(z)()();()()|(ZHYHYXIZHXYHcccc可加噪声信道可加噪声信道l高斯噪声信道)1l

23、og(21)()();(22zxcXHYHYXI平均功率受限的可加噪声信道平均功率受限的可加噪声信道nxnnnNnnxdxQxxSxNn)(12212平均功率受限的时间离散、恒参平均功率受限的时间离散、恒参、可加高斯噪声信道容量、可加高斯噪声信道容量)1log(212SC最佳分布是均值为0，方差为S的高斯型分布平均功率受限时间离散恒参可加平均功率受限时间离散恒参可加噪声信道容量噪声信道容量22222222log21)1log(21xyxSCS给定信号功率，高斯信道是最差的信道yxz平行可加高斯噪声信道平行可加高斯噪声信道lX=(x1,xN),y=(y1,yN)BSESBSCnnNnnBnnNn

24、nnn21:212,log21)1log(2124.5 波形信道波形信道可加波形信道可加波形信道lY(t)=x(t)+z(t),(),()()()()()()()()(1100NNTnnTnnnnnnnnyyyxxxdtttyydtttxxtytytxtx可加波形信道可加波形信道);(sup1,lim);(lim)();()|()()|(log);();(lim)();(NNTTTNNNTNNNNTYXITCCCYXItYtXIdxxypxQxypyxIyxItytxI可加波形信道可加波形信道STSxESTdttxEzxydtttzztztznnnnTnnnTnnnnn)()()()()()(

25、2020可加波形信道可加波形信道)21log(2)21log(2);(max)21log(21);();(00101NNSTTNCNNSTNYXINSYXIYXITNNNnnNnnnNNShannon公式公式lN=2WT)/(44. 1)1log(00NSCWNSWCW趋于无穷大，单位时间的信道容量Shannon极限-1.59dB第五章第五章 信道编码定理信道编码定理l1.离散信道编码问题l2.信道译码l3.Fano不等式和信道编码逆定理1.离散信道编码问题离散信道编码问题纠错编码器纠错编码器l送给纠错编码器的消息是经过最佳信源编码后，信息速率为比特/秒的离散二元或q元数字序列。 l分组码 每

26、K个信息数字为一组，计算出N个编码数字，称这些数字为一个码字。通常N为整数。l卷积码l输出的n0长码段不仅依赖于当前的k0位信息数字，还依赖于前m个信息段的信息数字，即总共与（m1）k0个信息数字有关。 Kk 0纠错编码器纠错编码器lRK/N，码率l误组率l误比特率LlelbmmpLpxxp11)(2.信道译码问题信道译码问题译码错误概率译码错误概率)|(1)|()(ymmpymmPypNNe译码准则译码准则l最小错误概率译码：使pe(y)最小l最大后验概率译码：)|()| (ympymprr最大似然译码最大似然译码)|() |()()|()()|(mypmypypmypmQymp所有Q(m)

27、相同最大对数似然译码最大对数似然译码)|(ln) |(lnmypmyp最小汉明距离译码最小汉明距离译码l汉明距离 d(x,y), x,y中分量不同的数目l码字先验等概lK元对称信道) 1/()|(1)|(Kpijppiip最小汉明距离译码最小汉明距离译码/ ) 1)(1ln(),()1ln()1ln(),(1ln),()|(ln)|(ln1pKpxydpNpxydNKpxydxypxypmmmNnmiim判决区域判决区域lYm:lnp(y|xm)lnp(y|xm)l给定m,错误概率MmemeYymempmQpxyppCm1)()|(高斯信道高斯信道2212221111()1max( |)exp

28、22maxln( |)min()min2NnmnmnNNNNmnmnmnmnnnnnnnyxp y xy xyxxxyyFano不等式和信道编码不等式和信道编码逆定理逆定理Fano不等式不等式CLNUHYXILUHVUIUHLVUHLpHMpVUHpHMpLNNLLLLLLbbbb)();(1)();()(1)|(1)() 1log()|()() 1log(信道编码逆定理信道编码逆定理l离散平稳源有M个字母熵为HL(U),信道容量为C,当HL(U)(N/L)C时,误码率为非零值信道编码定理信道编码定理lR0，存在编译码方法，当N足够大，pe第七章第七章 信道编码信道编码线性分组码线性分组码l信

29、息位，信息空间l码字，码空间l分组码：n维线性空间中的k维子空间l参数（n,k,d），n是码长，k是信息位长度，d是最小汉明距离l汉明重量：向量x中非零分量的数目l最小距离：所有码字中最小非零重量lGF（2）上的向量GF(2)l包含0,1l定义了两个运算l加法：000，01101，110l乘法：000，010，100，111ld(x,y)=w(x+y)生成矩阵生成矩阵lK维子空间的基底lC=u0g0+u1g1+uk-1gk-11, 11 , 10, 11, 111101, 00100110nkkknnkggggggggggggG(7,4)汉明码汉明码消息序列码字消息序列码字0000000100

30、1000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111系统码系统码校验位信息位10001010100111001011000010114210ggggG生成矩阵生成矩阵32002101321261032103210),(),(uuucuuucuuuccccgggguuuuuGc校验矩阵校验矩阵lC的对偶空间Vlcv=0l

31、V的生成矩阵H是G的校验矩阵lV的维数是N-K000TTTcHHGGH校验矩阵校验矩阵1, 11 , 10, 11, 111101, 00100110nknknknnnknhhhhhhhhhHhhh生成矩阵和校验矩阵的关系生成矩阵和校验矩阵的关系10001010100111001011000010114210ggggG111010001110101101001H错误图样错误图样),(,),(),(110110110NnnnNNeeecvevvvcccecvevc错误图样伴随式伴随式TTTTknTHHHHssseececvHs)(),(110伴随式和错误的关系伴随式和错误的关系ls0,有错误出现

32、lS=0le0，没有错误le=ci, 不可检错误l不可检错误概率CccwcwncwudppCp0)()()()1 ()(重量分布矢量重量分布矢量lAi码中重量为i的码字数目NiiniiudppACp1)1 ()(陪集陪集 l将2N个可能的向量分为2N-k个集合l集合中每个向量的伴随式相同l这样的集合称为陪集l选择陪集中重量最轻的向量作为陪集代表，称为陪集首。标准阵标准阵12121121212121111112100000kknknknknkkceceesceceesccces伴随式陪集首陪集正确译码概率正确译码概率niiniillwnlwcpppppkn0120)()()1 ()1 (a第l个

33、陪集首的重量重量为i的陪集首的数量(6,3)码的标准阵码的标准阵001001111100000100010000010001000001000100011000010101000110101011011101000001110000111101010011100000000000陪集首伴随式译码步骤译码步骤l计算接收矢量的伴随式l由伴随式确定陪集首l将陪集首作为错误图样elC=v-e校验矩阵和最小距离的关系校验矩阵和最小距离的关系lV属于码字集合的冲要条件是v的非零码元与H相应列的乘积之和为0l若矩阵H中任意d-1列线性无关，相应码的最小距离至少为d最小距离和纠错能力的关系最小距离和纠错能力的

34、关系l码的最小距离为dmin,可以纠错的最大数目为21mindt译码错误概率译码错误概率ntiinieppinp1)1 (汉明码汉明码l汉明码的校验矩阵由所有非零的m维向量构成列向量ln=2m-1,k=2m-m-1,d=3l（31，26），（7，4）(15,11)卷积码卷积码l（2,1,2）卷积码2,1,2卷积码的卷积码的trellis图图卷积码的卷积码的viterbi译码译码lc=(11 10 00 01 10 01 11)lu=(10111)lR=(10 10 01 01 10 01 01)第九章第九章 率失真函数率失真函数一般概念与定义一般概念与定义l不等长编码平均长度不超过HL(U)/

35、logD+1/L可以无失真l等长编码HL(U)+e/logD失真不会超过给定值l传输信息允许失真，信息率可以下降例：例：H(U)=2.24u1u2u3u4u5P(ui)不等长编码等长编码允许失真0.2500000000.2501001010.25100101001011110011信道失真信道失真ld(u,v)是U和V的非负函数，U,V为离散变量lUV=a1,a2,ak2)(),(|00),(vuvudjidjiajidavauddijijjiij平均失真平均失真LllLlllLLLlllLuvUVijijjiidLvudELdEdvudLddudvvuduvPuQd

36、dPQvudEd111|1),(1),(),(1),(),()|()(),(vuvu率失真函数率失真函数lPD是满足 所有Pji的集合Dd );(min)(VUIDRDjiPP 失真不超过D时传输所需的最小互信息量失真率函数失真率函数DRDRDD min)(给定信息率，找最小的失真的编码方式率失真函数的基本性质率失真函数的基本性质)()(lim)()(00UHDRUHDRD率失真函数定义域率失真函数定义域l不允许最小失真小于某一值，DDminlDmax是使R(D)=0的D的最小值l令PD是使I(Pji)0的全体转移概率的集合),(minmaxvudEDDjiPP 率失真函数的定义域率失真函数的

37、定义域lI(Pji)=0的充要条件是U和V统计独立uVvuvUVvuduQDvuduQvwDvuvP),()(min),()()(min)()|(maxmax|R(D)性质性质lR(D)是下凸函数lR(D)是D的连续单调减函数有失真时的逆信源编码定理有失真时的逆信源编码定理l当速率小于R(D)时，不论采取什么方式，平均失真必大于D.R(D)的计算的计算|(|)0V UjiPvu1)|(1|JjijUVuvPDvuduvPuQPDKiJjjiijUVi11|),()|()()(对所有对所有uiiijUViijUVjijUViuvPuQuvPuvPuQPI|)|()()|(ln)|()()(使使关于关于P(v|u)最小最小拉格朗日函