信源-信道编码定理

1、Any real communication system can be subsumed under the model of Figure. The encoder block represents all the data processing performed on the source output before transmission. The channel is assumed to accept channel input symbols at discrete intervals, and response to emit channel to emit channel

2、 output symbols. The “decoder” block represents all the data processing performed on the channel output before delivery to the destination.We are given the channels input alphabet and output alphabet. Also, we are given the channel statistics. For each positive integer n and 0, define Cn( ) by 给定信道输

3、入字母表和输出字母表，同时给定信道统计分布。n和 0，定义Cn( )为 )(: );(sup)(nbEICnXYX, 2 , 1: )(1sup)(nCnCn The capacity-cost function C( ) is defined by )(: );(sup)(nbEICnXYX容量-代价函数 C( )定义为, 2 , 1: )(1sup)(nCnCn (a) each codeword satisfies b (xi) n (b) (c) , i = 1, 2, , M. Channel Coding Theorem: Fix 0 min. Then for any tripl

4、e (, C , ) with 0, C 0, there exist for all sufficiently large n, a code x1, x2, , xM of length n and a decoding rule such asnCM2)(iEPWe are given a source alphabet, a destination alphabet and the “distortion” d (u, v). Also, we are given the source statistics. For each positive integer k and min de

5、fine Rk ( ) by 给定信源字母表、信宿字母表和失真d (u, v)，同时给定信源统计分布。对于所有的正整数k和 min，定义Rk ( )为 The rate-distortion function of the source is defined by 信源的率失真函数定义为),(: );(inf)(kdEIRkVUVU, 2 , 1: )(1inf)(kRkRk),(: );(inf)(kdEIRkVUVU, 2 , 1: )(1inf)(kRkRkSource coding Theorem：Fix min. Then for any pair ( , R ) with and

6、R R (), for all sufficiently large k there exists a source code C = (v1, v2, , vM) of length k such that:（a）M 2 k R ；（b）d (C) min, and r C( )/ R ( ), it is possible to design a system of the type depicted in Figure such that . rand,)()(RCr rr and,ChannelChannel DecoderSource Decoder(Y1, , Yn)(Z1, ,

7、Zn)(V1, , Vk)YZVFigure The general design of the decoderDecoderSourceSource EncoderChannel Encoder(U1, , Uk)(W1, , Wk)(X1, , Xn)UWXFigure The general design of the encoderEncoder例：例：一个快餐店只提供汉堡包和牛排，当顾客进店以后只需向厨房喊一声“B”或“Z”就表示他点的是汉堡包或牛排，不过通常8%的概率厨师可能会听错。一般来说进店的顾客90%会点汉堡包，10%会点牛排。问：（1）这个信道的信道容量；（2）每次顾客来点

8、菜时提供的信息；（3）这个信道可不可以正确地传递顾客点菜的信息。例：例：发送端有3种等概率符号(x1, x2, x3)，p(xi) =1/3，接收端收到3种符号(y1, y2, y3)，信道转移概率矩阵（1）接收端收到一个符号后得到的信息量H(Y)；（2）计算噪声熵H(Y|X)；（3）计算接收端收到一个符号y2的错误概率；（4）计算从接收端看的平均错误概率；（5）从转移矩阵中能看出该信道的好坏吗？09 . 01 . 03 . 03 . 04 . 02 . 03 . 05 . 0P例：例：就业问题：假如政府的就业问题顾问在考虑全国的就业问题时，把全体国民的就业情况分为三类：全就业（100%就业）

9、、部分就业（50%就业）和失业（0%就业），分别用概率p(E)，p(F)和p(U)表示。要使全民的就业率达到95%，请问：（1）p(E)的取值范围；（2）求就业情况的熵作为p(E)的函数；例：例：网球比赛中David和Mike在前面的比赛中打平，最后三场与其他选手的比赛结果将最终决定他们的胜、负或平。（1）假定最后3场他们与其他选手的比赛结果胜负的可能性均为0.5，把Mike的最终结果胜、负、平作为随机变量，计算它的熵；（2）假定David最后三场比赛全部获胜，计算Mike的最终比赛结果的条件熵。 作业：作业：1. 世界职业棒球锦标赛为7场赛制，只要其中一队赢得4场，比赛就结束。设随机变量X代表在棒球锦标赛中A队和B队较量的可能结果，X的可能取值为AAAA，BABABAB和