在有噪信道中,怎么能使消息通过传输后 发生的错误最少? 在有噪信道中,无错误传输的可达的最大 信息传输率是多少? 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 − = = − = − = − = − =