《信息论与编码a_第6章信道编码概述》由会员分享，可在线阅读，更多相关《信息论与编码a_第6章信道编码概述（62页珍藏版）》请在金锄头文库上搜索。
1、1,第6章 信道编码概述,信息论与编码 Information and Coding Theory,西南交通大学 信息科学与技术学院,2,第6章 信道编码,6.1 信道差错概率 6.2 信道编码概念 6.3 信道信道译码准则 6.4 码的检错与纠错能力 6.5 信道编码定理,3,6.1 信道差错概率,信道差错在通信过程中，传送的最小信号波形是符号，编码后也称为码元。由于噪声干扰，码元在信道传输过程中会发生变化，信宿方接收到的码元符号不一定是信源发出的码元符号. YX,4,6.1.1 随机差错信道,信道中，各码元是否出现差错，与其前、后码元是否出现差错无关，每个码元独立地按一定概率产生差错。这类
2、信道称为随机差错信道. 随机差错是由加性高斯白噪声引起. 主要参数: 码元差错概率，简称为误码率,5,6.1.1 随机差错信道,DMC的差错概率 信道输入X ：A=a1, a2, aq 信道输出Y ：B=b1, b2, bs 信道差错规律：条件概率描述,6,6.1.1 随机差错信道,DMC的平均误码率 码元ai正确传输概率为：,码元ai出错概率为：,信道先验概率分布为：,信道因噪声干扰产生的平均错误概率为：,7,6.1.2 突发差错信道,信道中，差错成片出现，一个差错成片称为一个突发差错。 突发差错总是以差错码元开头、且以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个标准
3、值。 通信系统中的突发差错是由突发噪声（如雷电、强脉冲、时变信道的衰落等）引起的。 存储系统中，磁带、磁盘物理介质的缺陷或读写头接触不良等造成的差错均为突发差错。,8,第6章 信道编码,6.1 信道差错概率 6.2 信道编码概念 6.3 信道信道译码准则 6.4 码的检错与纠错能力 6.5 信道编码定理,9,6.2 信道编码概念,信道编码器是一个映射f，它把信源符号序列m变换成信道符号序列c = f (m)，f称为信道编码函数，或称为纠错编码函数。信道编码也称为纠错编码。,10,6.2 信道编码概念,符号集：A=a1, a2, aq 信源符号序列： m=m1m2mk (mi A) 信道编码函数
4、f ：c = f (m)= c1c2cn (cj A) 信息元：m1,m2,mk 信息位长度：k 码字 (codeword)： c 码字长度: n,设S是全体信源符号序列构成的集合，C = f (m) | m S称为信道码，或称为纠错码，简称为码 (code)。,11,6.2 信道编码概念,系统码 信道编码函数f ：c = f (m)= m1m2,mk d1d2,dr (dj A) 信息元：m1m2,mk 校验（监督）元：d1d2,dr,k：信息位长度 r: 校验位长度，或称为冗余位长度 n=k+r : 码字长度,12,6.2 信道编码概念,按码元数分类 q元码，或q进制码 2元码，或2进制码
5、,按照编码函数f的线性性 线性码：编码函数f ( f1,f2,fn)是线性函数 非线性码：否则，称为非线性码。,13,6.2 信道编码概念,分组码设k, n是正整数，k n，则把从EAk到An的编码函数 f : EAn 称为一个(n, k)分组码编码器，或称为(n, k)编码函数。全体码字构成的集合C=c =f (m): mE 称为一个q元 (n, k)分组码 (block code)，或简称为(n, k)码。,按照编码函数对信息元处理方法: 分组码与卷积码,14,6.2 信道编码概念,设M =| E |，q元 (n, k)分组码的信息传输率，或称为码率、速率：,当E=Ak时 q元 (n, k
6、)分组码C包含有qk个码字，称为许用码字 长度为n的符号序列共有qn个，其中有qk个是许用码字，其余qnqk个称为禁用码字 一个(n, k)分组码编码器其实就是确定一个规则，以便从qn个n重符号中选出qk个许用码字 码率：,15,6.2 信道编码概念,分组码 循环码如果一个码的全体码字可以分为若干组，使得每组中任一码字的码元循环移位后任是该组的码字，这样的分组码称为循环码 非循环码不是循环码的分组码，称为非循环码,16,6.2 信道编码概念,卷积码(n, k, m) 把信源符号序列分成长为k的段，依次对每段进行编码，码字长度都为n。如果每个码字的码元不但与该段的k位信息元有关，还与之前m段的信
7、息元有关，这样得到的信道码称为 (n, k, m) 卷积码。即卷积码码字的码元与(m +1)k位信息元有关。,17,6.2 信道编码概念,18,6.2 信道编码概念,译码函数信道译码器的主要功能就是确定一套译码规则g，由接收到的符号序列r给出信源符号序列c的一个最接近的估计g(r)。g称为译码函数，由r求g(r)的过程称为信道译码。如果g(r)=c，说明信道译码器译码正确。如果g(r)c，说明信道译码器译码错误。,19,6.2 信道编码概念,在接收到符号序列r的条件概率，译码器译码错误的条件概率定义为：,译码器平均译码错误概率定义为,20,6.2 信道编码概念,P(r)是译码器接收符号序列r的
8、概率分布：,信道因噪声干扰产生的平均错误概率为,使用信道编码技术的主要目的就是使PE PC.,21,6.2 信道编码概念,例6.1 重复码 重复码是一个(n, 1)分组码，其编码规则是将每位信息元重复n 1次，也称为n次重复码。即C =000, 111。对重复码，可以采用大数准则译码。即如果接收序列中0的个数多于1的个数，则译为0；否则，译为1。 例如，2元3次重复码的编码规则如下：“0” “000”， “1” “111”。它是一个2元(3, 1)分组码C=000, 111 。,22,6.2 信道编码概念,译码器接收符号序列r及译码结果,23,6.2 信道编码概念,假设使用一个具有错误概率为p
9、 1/2的无记忆二元对称信道传输一个信源符号，且信源发出符号0和1的概率均为1/2。 计算接收符号序列r的概率分布P( r) 。,24,6.2 信道编码概念,当三个符号在传输过程中有一位或二位出错时，译码器能够发现接收到的序列有错，但不知道那些位出了错。但当三个符号在传输过程中都出错时，译码器不能发现错误。即分组码C最多能检出2位错误。 如果采用大数准则译码方法，当传输的符号序列有一位出错时，能正确纠正。即分组码C能纠正1位错误。,25,6.2 信道编码概念,译码错误条件概率,26,6.2 信道编码概念,译码器平均译码错误概率为,如果不使用信道编码，直接传输信源符号，则信宿方接收到符号0时译为
10、0，接收到符号1时译为1，其信道错误概率为,因为PE PC，所以3次重复码的使用提高了信道的可靠性。,27,6.2 信道编码概念,例如，当PC = p=102时，有,使用简单的重复编码方法，已将错误概率降低了接近二个数量级!,28,6.2 信道编码概念,当重复次数n增加时，平均错误概率将进一步降低，但码率也随之降低。,29,第6章 信道编码,6.1 信道差错概率 6.2 信道编码概述 6.3 信道译码准则 6.4 码的检错与纠错能力 6.5 信道编码定理,30,6.3 信道译码准则,最小错误概率译码,译码函数g应该具有最小平均译码错误概率PE。 定义g(r)的值满足：,译码函数g称为最小错误译
11、码函数，或称为最大后验概率译码。 选择最大后验概率译码函数g,31,6.3 信道译码准则,平均译码错误概率,信源服从均匀分布时，P(c)也是均匀分布，设码字总数为M =|C|，则有P(c)= M1，,32,6.3 信道译码准则,最大似然译码(MLD)定义g(r)的值满足：,译码函数g称为最大似然译码，P(r | c) 称为似然函数 最大似然译码函数只与信道转移概率有关，与信源概率分布无关。 最大似然译码函数g由下式确定,33,6.3 信道译码准则,当信源服从均匀分布时,因此，在信源服从均匀分布情况下，最大后验概率译码与最大似然译码是相同的，其平均译码错误概率为最小。,34,6.3 信道译码准则
12、,例6-2. 有一个离散信道，输入符号集为A=a1, a2, a3，接收符号集为B=b1, b2, b3，信道矩阵为,（1）求最大似然译码函数因为信道矩阵P的第一列中P(b1| a1)=0.5为最大，第三列中P(b3| a2)=0.5为最大，第二列中P(b2| a1)= P(b2| a2)= P(b2| a3)=0.3，所以最大似然译码函数为：g(b1)=a1, g(b2)=a3, g(b3)=a2.,35,6.3 信道译码准则,36,6.3 信道译码准则,例6-2（续2）（2）求最大后验概率译码函数h 首先计算接收符号r概率分布P( r),计算后验概率P(c|r):,37,6.3 信道译码准
13、则,例6-2（续3）（2）求最大后验概率译码函数h,最大后验概率译码函数h: h(b1)=a3, h(b2)=a3, h(b3)=a3,输入不是等概率分布时，最大似然译码函数的平均错误概率不是最小的!,38,6.3 信道译码准则,汉明（Hamming）距离两个长为n的码字x与y之间汉明（Hamming）距离是指x与y之间对应位置上不相同码元的个数，用符号d(x, y)表示。 汉明重量：码字x中非零码元的个数称为x的汉明重量，用符号w(x)表示。,例如: 对于两个二元码字: x=101111， y=111100有d(x, y)=3。 又如: 对于两个码字: x=1320120, y=122331
14、0有d(x, y)=4。,39,6.3 信道译码准则,设 x= x1x2xn, y= y1y2yn是两个二元码字，容易验证以下等式成立:,其中是模二加法 汉明距离的性质 定理6-1 设x、y与z是长为n的码字，那么汉明距离满足以下性质：(1) 非负性：d(x, y) 0。且d(x, y) = 0的充分必要条件是x = y；(2) 对称性：d(x, y) = d(y, x)；(3) 三角不等式：d(x, y) d(x, z)+ d( z, y)。,40,6.3 信道译码准则,如果译码函数g将二元序列r译成二元码字c，那么r与c之间的汉明距离d(r, c)就是译码出错的位数。 译码出错的位数尽可能
15、小！ 最小汉明距离译码,称为最小汉明距离译码函数，简称为最小距离译码函数。 最小汉明距离译码与信道转移概率无关,41,6.3 信道译码准则,对于二元对称无记忆信道，设每个符号出错概率为p1/2，r=(r1, r2, rn)，c=(c1, c2, cn)，那么,当r不变时，选择c使P(r|c)达到最大的充分必要条件是使d(r, c) 达到最小。 对于二元对称无记忆信道，最小汉明距离译码与最大似然译码是相同的。,42,6.3 信道译码准则,在二元对称无记忆信道中，平均译码错误概率可用汉明距离表示。设信源服从均匀分布，码字总数为M =|C|，有,43,6.3 信道译码准则,例6-3 对n次重复码C
16、=000, 111进行最小距离译码。 设接收的序列为r，如果d(r, 000) d(r, 111)，则将r译为111。 如果d (r, 000)=d(r,111)，则不能正常译码，只能发现差错。 注意到，当d (r, 000) d (r, 111)时，序列r中1的个数多于0的个数，所以n次重复码的最小距离译码与大数准则译码相同。,44,6.3 信道译码准则,例6-4. 设一个离散信源有四个符号S=(s1, s2, s3, s4)，编码器输出的码为C =0000, 1010, 0111, 1101。如果在一个具有单符号错误概率为p=102的BSC上传送码字，求最佳译码及平均译码错误概率。(1) 如果信源服从均匀分布：,
