当前位置:首页 >> IT/计算机 >>

第六章 有噪信道编码


第六章 有噪信道编码

信息论与编码

6.1 译码准则 与译码错误概率
? 有噪声信道编码的主要目的是提高传输可 靠性,增加抗干扰能力,因此也称为纠错 编码或抗干扰编码。 ? 信源编码之后的码字序列抗干扰能力很脆 弱,在信道噪声的影响下容易产生差错, 为了提高通信系统的有效性和可靠性,要 在信源编码器和信道之间加上一个信道编 码器,
信息论与编码

6.1.1 译码准则的含义
? 一个例子 影响通信系统可靠性的一个重要问题是译码方式,可以通 过一个例子看一下; 有一个BSC信道,如图所示。

信息论与编码

?

对于这样一个信道,如果采用自然的译码准则, 即收0判0,收1判1;这时可以明显看到,当信 源先验概率的等概时p(0)=p(1)=1/2;这时收到 Y判X的后验概率等于信道转移概率,系统正 确的译码概率为1/4,错误译码概率为3/4。但 如果采用另一种译码准则,收0判1,收1判0; 则系统正确的译码概率为3/4,错误译码概率 为1/4,通信的可靠性提高了。 译码准则

?

信息论与编码

? 这时定义一个收到yj后判定为xi的单值函数, 即: F(yj)=xi (i=1,2,…n; j=1,2,…m);这个函 数称为译码函数。它构成一个译码函数组,这 些函数的值组成了译码准则。 ? 对于有n个输入,m个输出的信道来说,可以 有nm个不同的译码准则。例如上面例子中有4 中译码准则分别为: A:{F(0)=0;F(1)=0} B:{F(0)=0;F(1)=1} C:{F(0)=1;F(1)=0} D:{F(0)=1;F(1)=1}
信息论与编码

6.1.2译码错误概率
? 译码准则确定之后,当接收端收到一个yj后,则按 译码准则译成F(yj)=xi,这时如果发送的为xi则为正 确译码,如果发送的不是xi则为错误译码。所以接 收到yj后正确译码的概率就是接收端收到yj后,推 测发送端发出xi的后验概率: Prj=P{F(yj)=P(xi/yj)} 而错误译码的概率为收到yj后,推测发出除了xi之 外其它符号的概率:Pej=P{e/yj}=1-P{F(yj)=xi/yj}
信息论与编码

? 其中e表示除了xi之外的所有其它信源符 号的集合。然后对所有的yj取平均,则平 均正确译码概率为:

Pr = ∑ P( y j ) Prj = ∑ p( y j ) ? p{F ( y j ) = xi / y j }
j =1 j =1

m

m

同样可以得到平均错误译码概率为:
Pe =

∑ p( y
j =1

m

j

) P{e / y j } =

∑ p( y
j =1

m

j

){1 ? P[ F ( y j ) = x i / y j ]}
信息论与编码

6.1.3最大后验概率准则 最大后验概率准则
? 由平均错误译码概率的表达式可以看出,错误译码 概率与信道输出端随机变量Y的概率分布p(yj)有关, 也与译码准则有关。当信道信道转移概率p(yj/xi)确 定后,而且信源统计特性p(xi)确定之后,信道输出 端的p(yj)也就确定了。因为:p(xi,yj)=p(xi)p(yj/xi); p(yj) p(xi,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, n)求和得到。 因此,在这种情况下,平均错误译码概率只与译码 准则有关了。通过选择译码准则可以使平均译码概 率达到最小值。 当式中的每一项的P{F(yj)=xi/yj}达到最大值时,平 均错误译码概率就可以为最小值。 设信源X的信源空间为:
信息论与编码

? 收到每一个yj(j=1,2,…m)后,推测发送为xi(i=1,2,…n)的后验 概率共有n个,为: p(x1/yj),p(x2/yj),……p(xn/yj)。 这其中必有一个为最大的,设其为:p(x*/yj),即有: p(x*/yj)≥p(xi/yj) (对一切的i) 这表明:收到符号yj后就译为输入符号x*,即译码函数选为: F(yj)=a* (j==1,2,…m) 这种译码准则称为“最大后验概率准则”。 信息论与编码

? 这个表达式平均错误译码概率的最小值, 是把每一个yj对应的后验概率排除后再连续 求和。 ? 从表达式中可以看到,这个最小值与信源 先验概率和信道转移概率有关,特别是信 道转移概率,如果除了p(yj/x*)外,其它的 项多很小,错误译码概率会减小。

信息论与编码

6.1.4 最大似然准则
? 使用最大后验概率译码准则必须已知后验 概率,但信道的统计特性描述总是给出信 道转移概率,因此利用信道转移概率的译 码准则。 由概率中的贝叶斯定理可有:
p( x i / y j ) = p( x i ) p( y j / x i ) p( y j )

p( x * / y j ) =

p( x * ) p( y j / x ? ) p( y j )
信息论与编码

?这样,根据最大后验概率译码准则,如果 p(x*)p(yj/x*)≥p(xi)p(yj/xi) (i=1,2,……n) 就等于:p(x*/yj)≥p(xi/yj) 则选择译码准则:F(yj)=x* (j=1,2,……n) 这样,可以看到当信道输入符号集X的先验概 率为等概时[p(xi)=1/n],比较上面三个式子,最 大后验概率可以用最大信道转移概率来取代。 这时,在X的先验概率为等概时,如果p(yj/x*) 是yj相应的n个信道转移概率 p(yj/x1),p(yj/x2),……,p(yj/xn) 中的最大者,则我们就将yj译成x*,这种译码方 法称为“最大似然译码准则”。
信息论与编码

最大似然译码准则利用了信道转移概率, 而不用后验概率,将会更方便。 为了减小错误译码概率,主要方法是改变 信道转移概率,

信息论与编码

6.2信道编码定理 信道编码定理
[定理]:有噪声信道编码定理(Shannon第二编码定 理) 如一个离散有噪声信道有n个输入符号,m个输出 C R≤C 符号,信道容量为C。当信道的熵速率R≤C时,只 要码长足够长,总可以找到一种编码方法及译码准 则,使信道输出端的平均错误译码概率达到任意小, [pe=ε]。当R>C时,则不可能找到一种编码方法及 译码准则,使信道输出端的平均错误译码概率达到 任意小。
信息论与编码

? 编码定理的证明比较复杂,主要参考课本 140页 ? 这个定理是一个存在定理,指出错误率趋 于0的编码方法是存在的。 ? 定理表明,在错误率趋于0的同时,还可以 使R趋于C,这是具有理论指导意义的。

信息论与编码

引入冗余
? 一个BSC信道,输入为X={0,1},且为等 概分布,信道模型为:

信息论与编码

? 按最大似然译码准则为:F(0)=0; F(1)=1; ? pe=0.01这里没有采用任何信道编码。

信息论与编码

编译码方法
?将0编为000,1编为111。 这时的可用码字为8;分别为: X1=000 X2=001 X3=010 X4=100 X5=011 X6=110 X7=101 X8=111 而许用码字为000和111, 相当于信道输入为X1=000,X2=111,而信道输 出端为: Y1=000;Y2=001;Y3=010;Y4=100 Y5=011;Y6=110;Y7=101;Y8=111 这时的信道转移矩阵为:
信息论与编码

这时如果按最大似然法则译码,将为: F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000 F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111 错误译码概率为: Pe ≈3×10-4 可见简单重复码可以将错误译码概率下降两个数 量级。 这是三次方法;可以看出如果是五次重复码,误 码率还要降低
信息论与编码

6.3 信道编码
信道编码又称为差错控制编码,简称为纠 错编码,即在信息序列中按一定的规则 附加若干监督码元,以便对信息传输 (或存储)起检错 纠错作用,目的在 检错与纠错 检错 纠错 于提高通信(或存储)的可靠性,减低 提高通信( 提高通信 或存储)的可靠性, 误码率。 误码率

信息论与编码

6.3.1分类

信息论与编码

几个基本概念
? 码字空间: 如果原始信源空间有M个码字,对其进行q元等长 码的信道编码,码长为N,信道码字空间的所有 码字为qN个,编码器将在这qN个可用码字中选 择M个码字分别代表原始信源中的M个码字,信 道编码码字空间的这M个码字称为“许用码字”, 而另外的qN-M个码字称为“禁用码字”。为了 实现纠错编码,一定有qN>M。这M个许用码字 也称为一个码组,或称为码字集合。

信息论与编码

汉明距离:(Hamming distance)
? 在一个码组(码字集合)中,任意两个等长码字之间, 如果有d个相对应的码元不同,则称d为这两个码字的 汉明距离。 例如:α和β为码组X中的两个不同码字,X为一个长度为 N的二元码组,其中: α=[a1,a2,……aN] ai∈{0,1} β=[b1,b2,……bN] bi∈{0,1} 则α与β的汉明距离为: d=0表明为全同码,d=N表明为全异码,如果用模2加法 的概念,有 模2 加法等同于“异或”运算 信息论与编码

? 最小码距:d (α , β ) = ∑ a i ⊕ bi
i =1

N

在一个码字集合中,任何两个码字之间的汉明距 离组成一个元素集合,D(α,β),这个集合中的最小 值称为这个码字集合的最小汉明距离,简称最小 码距,记为:dmin。 dmin=min{d(α,β) α,β∈X α≠β}

信息论与编码

码字重量(汉明重量) (Hamming weight)
? 在二元编码的码字集合中,码字中“1”码元 的个数称为这个码字的重量。记为: W(α)

信息论与编码

举例:
? 气象台预报天气 信码 监督元 位 晴 00 0 云 01 1 阴 10 1 雨 11 0 码字 (偶校验)传输中错一 (000)→100,010,001 (011) →111,001,010 (101) →001,111,100 (110) →010,100,111 许用码字 禁用码组

可检一位错,之所以能检错,是因为引入了冗余( 可检一位错,之所以能检错,是因为引入了冗余(禁 冗余 用码组) 用码组)

信息论与编码

? 例2 可检查出2位错。附加两个监督元,设只有“晴”、 “雨”两种信息: 信码 监督元 码字 传输中错一位 晴 0 00 (000)→100,010,001 →0 雨 1 11 (111) →011,101,110 →1 可纠1位错 (000)(111)许用码字 ,其他为禁用码字 许用码字 其他为禁用码字. 其他为禁用码字 在例2中,若编码规则为 晴 011, 雨 000, 则无纠错能力。当发生1位错时: (011)→111,001,010 (000) →001,100,010 则不能纠1位错,但仍能检1位错。

信息论与编码

纠、检错能力与最小距离d0之间的关系
? 一个码能够检测出

t d ≤ d min ? 1

个错误;

只用于纠错,能纠正

? dmin ? 1? 个错误; tc ≤ ? 2 ? ? ?

用于既纠tc个错,又检td个错

tc + td ≤ d min ? 1
信息论与编码

6.3.2线性分组码
? 分组码是一种代数编码,它的基本关系一 个码字包括独立的信息元和监督元,其监 督元与信息元之间是一种代数关系,如果 这种代数关系为线性的则称为线性分组码。 分组码的编码器的模型为:

信息论与编码

? [m]为编码器的输入,称为信息码元(信息 位),它由k位码元组成。[C]为编码器的输 出,称为码字矢量,它由n位码元组成,其 中有k位信息元,r=n-k位监督元。 ? 线性分组码:监督元与信息元之间的关系 线性分组码: 可用一组线性方程组来描述的(n, k)分组码。

信息论与编码

以(7,4)汉明码为例简单介绍
? N=7,k=4,r=3.

[C]=[c6,c5,c4,c3,c2,c1,c0];其中[c6,c5,c4,c3]为 信息位,[c2,c1,c0]为监督位。
信息论与编码

? 由[H][C]T=[0]可知:监督方程为: c2=c5+c4+c3 c1=c6+c4+c3 c0=c6+c5+c3 其中加号为”模2和”规则.

信息论与编码

? 根据这个方程组可以进行编码。例如信息 码元m=[1011],则有 c2=c5+c4+c3=0+1+1=0 c1=c6+c4+c3=1+1+1=1 c0=c6+c5+c3=1+0+1=0 ? 则汉明码字[C]=[1011010]。

信息论与编码

? 假如接收码字为[R]=[0100101]可以看到: [S]T=[H][R]T=[0] 这时表明无差错; 如果接收码字有一位差错,[R]=[0110101]; 即错误图样[E]=[0010000];接收码字的 第三位错。这时校验子矢量为:
信息论与编码

? 可见这时校验子[S]T不为0,译码器认为 有错,且正好等于[H]的第三列,表明接 收码字的第三位码元错了。这时判断发 送码字位[0100101],译码正确。
信息论与编码

? 如果接收码字由两位差错,[R]=[0111101]; 即错误图样[E]=[0011000];接收码字的第 三、四位错。这时校验子矢量为:

信息论与编码

? 可见这时,校验子矢量不为0,但是如果这 时接收机按原来的译码方法,将认为第7位 出错。但如果接收机设计为检错系统,当 校验子不为0,就认为有错。因为(7,4)汉明 码的最小码距为3 (3<1+2+1),其不具备一 种方法同时具有纠错检错能力.

信息论与编码

? 注意:纠错码的选用要小心,要根据信道 注意:纠错码的选用要小心, 条件来确定,如果信道较差, 条件来确定,如果信道较差,而使用的纠 错码能力不够,可能使译码错误反而增加, 错码能力不够,可能使译码错误反而增加, 不仅错误的码元没有纠正, 不仅错误的码元没有纠正,原来正确的码 元还被错误的改变。错上加错。 元还被错误的改变。错上加错。

信息论与编码

? 这种纠检错能力是由码组的最小码距决定 的。 可以验证:下面的(7,3)线性分组码的最小码 距为4,可以纠一位错,同时检两位错,其 基本监督矩阵为:

信息论与编码

生成矩阵(Generator matrix) 生成矩阵
? [C]=[m3,m2,m1,m0].[G]

[m]=[1100], [C]=[1100][G]=[1100110]

信息论与编码

? 即有: [H][G]T=[0],同时有:[G][H]T=[0] 称[H]与[G]为正交矩阵

信息论与编码


相关文章:
信息论复习题2
第六章 信道编码 题纲: I. 基本概念 1. 编码器 2. 二元码 3. 等长码 4...有噪信道编码定理 III. 线性分组码 IV. 循环码 需掌握的问题: 1. 什么是...
信息论第6章
27页 免费 信息论0第6章 暂无评价 58页 1财富值 (信息论)第6章有噪信道编码... 34页 免费 6--第6章信息论课件 30页 免费 信息论第六章 72页 免费喜...
信息论复习
物理意义是信源端的信息通过信道后传输到信宿端的 平均信息量 4、疑义度表示...第五章 香农第一定理:无失真信源编码定理 第六章 香农第二定理:有噪信道编码...
信息论基础-理论教学大纲
离散信源无失真和限失真信源编码理论和编码方法; 离散有噪信道编码理论和编码...三、本章学时数 14 学时 第六章:总复习一、教学要求 总结掌握信息论基础课程...
信息编码样卷
调制与级联码简介; 第六章 有噪信道编码定理 考试内容: 错误概率和译码规则、错误概率与编码方法、联合 e 典型序列 、有噪信道编码 定理、 联合信源信道编码定理...
信息论基础
信源无失真和限失真信源编码理论和编码方法; 离散有噪信道 编码理论和编码原则...三、本章学时数 14 学时 第六章:总复习 一、教学要求 总结掌握信息论基础...
基于PCM有噪信道编码
有噪 信道编码实验方法;介绍了通信系统中 PCM 编码的工作原理以及其他相 关理论...4 之间作为第六段,依此分下去,直至剩余的最小一段为 0~1/128 作为第一段...
《信息论与编码》复习大纲
信源编码定理、有噪信道编码定理,限 失真信源编码定理) 2、 信源编码: 无...? p ?S ? p r 第六章:信道编码 1、基本概念: 差错符号、差错比特;差错...
信息论与编码教学大纲
离散信源无失真和限失真信源编码理论和编码方法; 离散有噪信道编码理论和编码...三、本章学时数 本章学时数 10 学时 第六章:波形信源和波形信道一、教学...
无线通信 读后总结
本书可以简要的分为三部分:第一部分,即第一章到第六章,是本书的核心 部分,...“三个定理”就是香农的三大编码定理:无失真信 源编码定理,有噪信道编码定理和...
更多相关标签: