信息论与编码技术 第6章有噪信道编码定理 苗付友 mfy@ustc.edu.cn 2019年12月
苗付友 mfy@ustc.edu.cn 2019年12月
在有噪信道中,怎么能使消息通过传输后 发生的错误最少? 在有噪信道中,无错误传输的可达的最大 信息传输率是多少? 0(0 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 2/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 2/ 在有噪信道中，怎么能使消息通过传输后 发生的错误最少？ 在有噪信道中，无错误传输的可达的最大 信息传输率是多少？
主要内容 6.1平均错误概率和译码规则 62平均错误概率与编码方法 63联合e典型序列 6.4有噪信道编码定理 6.5联合信源信道编码定理 0(0 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 3/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 3/ 6.1 平均错误概率和译码规则 6.2 平均错误概率与编码方法 6.3 联合𝜀典型序列 6.4 有噪信道编码定理 6.5 联合信源信道编码定理
对于无噪无损信道只要对信源进行适当的编码《(总 能以信道容量无差错的传递信息。但是一般信道总会存在 噪声和干扰,那么在有噪信道中进行无错传输可以达到的 最大信息传输率是多少呢? 编码器 信道 译码器 信源编码器 信源译码器 图61编码信道 信道编码的对象:信源编码器输出的数字序列(信 息序列)M,通常是0、1符号构成的序列。信源经过变 长编码后,编码的码符号往往等概率分布。因此信道编 码中的信源往往被认为是等概论出现。 信道编码: 数字序列M增加的 数字序列X 无规律性)多余码元 (有规律性) mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 4/ 图6.1 编码信道 信道编码的对象：信源编码器输出的数字序列（信 息序列）M, 通常是0、1符号构成的序列。信源经过变 长编码后，编码的码符号往往等概率分布。因此信道编 码中的信源往往被认为是等概论出现。 信道编码： 数字序列M （无规律性） 增加的 多余码元 数字序列X （有规律性） ＋ 对于无噪无损信道只要对信源进行适当的编码，总 能以信道容量无差错的传递信息。但是一般信道总会存在 噪声和干扰，那么在有噪信道中进行无错传输可以达到的 最大信息传输率是多少呢？
61平均错误概率和译码规则约 为了减少错误,提高通信的可靠性,就必须分析错误概 率与哪些因素有关,有没有办法控制,能控制到什么程度。 在有噪信道中传输消息是会发生错误的。错误概率与信道 统计特性有关。信道的统计特性可由信道的转移矩阵来描述。 例:有一个BSC信道,如图所示013:0 若收到“0”译作“0”,收到“1” 译作“1”,则平均错误概率为:2/3 E =P(0)P0+P(1)2 3 0(0 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 5/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 5/ 为了减少错误，提高通信的可靠性，就必须分析错误概 率与哪些因素有关，有没有办法控制，能控制到什么程度。 在有噪信道中传输消息是会发生错误的。错误概率与信道 统计特性有关。信道的统计特性可由信道的转移矩阵来描述。 0 1 0 1 1/3 1/3 2/3 2/3 例：有一个BSC信道，如图所示 若收到“0”译作“0”，收到“1” 译作“1”，则平均错误概率为： (0) (1) 2 (0) (1) 3 P P P P P E e e = + =
6.1平均错误概率和译码规则 反之,若收到“0译作“1”,收到“1”译作“0”,则平 均错误概率为1/3,可见错误概率与译码准则有关 可见,错误概率既与信道的统计特有关,又与码 规有关。 译码规则设离散单符号信道的输入符号集为A={a i=1,2,…,r输出符号集B=[b],j=1,2,…,s。 若对每一个输出符号b都有一个确定的数f(b)使b对 应于惟一的一个输入符号a1,则这样的函数称为译码规 则,记为f(b)=a71=1,2,…,r=1,2,,S ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 6/ 反之，若收到“0”译作“1”，收到“1”译作“0”，则平 均错误概率为1/3，可见错误概率与译码准则有关。 可见，错误概率既与信道的统计特性有关，又与译码 规则有关。 译码规则 设离散单符号信道的输入符号集为 输出符号集 。 若对每一个输出符号 都有一个确定的数 使 对 应于惟一的一个输入符号 ，则这样的函数称为译码规 则，记为 F b j = ai ( ) i =1，2，，r j =1，2，，s ={ }, A ai = = [ ], 1 2 B b j i ， ， ，s i r =1 2 ， ， ， j b j b i a ( ) F bj
61平均错误概率和译码规则 例6.1(p200) 0.50.30.2 0.20.30.5 0.30.30.4 可以设计译码准则: F(b1)=a1 F(b) A:F(b2)=a2 B: F(b,) F(b2)=a2 译码规则的选择应该有一个依据,一个自然的依据就 是使平均错误概率最小。 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 7/ 例6.1（p200） 1 2 3 1 2 3 0.5 0.3 0.2 0.2 0.3 0.5 0.3 0.3 0.4 b b b a a a P = 1 1 2 2 3 3 ( ) ( ) ( ) F b a A F b a F b a = = = ： 1 1 2 3 3 2 ( ) ( ) ( ) F b a B F b a F b a = = = ： 可以设计译码准则： 译码规则的选择应该有一个依据，一个自然的依据就 是使平均错误概率最小
6.1平均错误概率和译码规则 有了译码规则以后,收到b,的情况下,译码的条件正确概率为 P(F(b,76=P(a, 1b,) 而错误译码的概率为收到b后,推测发出除了a之外 其它符号的概率:P(e/b)=1-P(a/b) 可以得到平均错误译码概率为: P=∑(b)P(eb)=∑P(b)(1-P(a/b) 它表示经过译码后平均接收到一个符号所产生错误的大 ,也称平均错误概率。 如何设计译码规则F(b)=a,使P最小 ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 8/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 8/ ( ( ) / ) ( / ) P F b b P a b j j i j = 而错误译码的概率为收到 后，推测发出除了 之外 其它符号的概率： j b i a ( / ) 1 ( / ) P e b P a b j i j = − 可以得到平均错误译码概率为： 1 1 ( ) ( / ) ( )(1 ( / )) m s e j j j i j j j P p b P e b p b P a b = = = = − 它表示经过译码后平均接收到一个符号所产生错误的大 小，也称平均错误概率。 如何设计译码规则 F b a P ( ) , j i E = 使 最小？ 有了译码规则以后，收到 bj 的情况下，译码的条件正确概率为：
6.1平均错误概率和译码规则 由前边的讨论可以看出,为使P(e/b,)最小,就应选择 P(F(b)/b为最大,即选择译码函数F(b)=a并使之满 足条件:Pa/b)≥Pa/b)a≠a 也就是说,收到一个符号以后译成具有最大后验概率 的那个输入符号。这种译码准则称为“最大后验概率准则” 或“最小错误概率准则”。 根据贝叶斯定律,上式也可以写成 P(b, /(a) p(b,/ap(a) erence P(b,) 0(0 P(b,) ash mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 9/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 9/ 由前边的讨论可以看出，为使 最小，就应选择 为最大，即选择译码函数 并使之满 足条件： ( ( ) / ) P F b b j j ( / ) P e bj * ( ) F b a j = * * ( / ) ( / ) P a b P a b a a j i j i 也就是说，收到一个符号以后译成具有最大后验概率 的那个输入符号。这种译码准则称为“最大后验概率准则” 或“最小错误概率准则” 。 根据贝叶斯定律，上式也可以写成 * * ( / ) ( ) ( / ) ( ) ( ) ( ) j j i i j j P b a P a P b a P a P b P b
61平均错误概率和译码规则 即:P(b,/a)P(a)≥P(b,/a2)P(a) 当信源等概分布时,上式为: P(b,/a)≥P(b,/a1) 这称为最大似然译码准则,方法是收到一个b,后, 在信道矩阵的第j列,选择最大的值所对应的输入符号作 为译码输出。可进一步写出平均错误概率 =∑P(b)P(e/b)=∑1-PIF(b)b}P(b) 1-∑P[F(b)l=∑pab)∑PF(b,)b XY ∑pab)∑Pnb=∑P(ab) YX-a mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 10/
mfy@ustc.edu.cn 信息论与编码技术-信道纠错编码 10/ 即： * * ( / ) ( ) ( / ) ( ) P b a P a P b a P a j j i i 当信源等概分布时，上式为： * ( / ) ( / ) P b a P b a j j i 这称为最大似然译码准则，方法是收到一个 后， 在信道矩阵的第j列，选择最大的值所对应的输入符号作 为译码输出。 j b 可进一步写出平均错误概率： * , * , , ( ) ( / ) {1 [ ( )/ ]} ( ) 1 [ ( ) ] ( ) [ ( ) ] ( ) [ ] ( ) E j j j j j Y Y j j i j j j Y X Y Y i j j i j X Y Y Y X a P P b P e b P F b b P b P F b b p a b P F b b p a b P a b P a b − = = − = − = − = − =