信息论与编码 曹雪芹 Chap6

1、126.1 纠错编译码的基本原理与分析方法6.2 线性分组码6.3 卷积码3 信源编码 提高数字信号 将信源的模拟信号转变为数字信号 降低数码率,压缩传输频带(数据压缩) 信道编码 提高数字通信 数字信号在信道的传输过程中,由于实际信道的传输特性不理想以及存在加性噪声,在接收端往往会产生误码。45是衡量传输质量的重要指标之一,它有几种不同的定义。 码元差错率/符号差错率 指在传输的码元总数中发生差错的码元数所占的比例(平均值),简称误码率。 是指差错概率 比特差错率 /比特误码率： 在传输的比特总数中发生差错的比特数所占比例 是指差错概率 对二进制传输系统,符号差错等效于比特差错;对多进制系统

2、,一个符号差错对应多少比特差错却难以确定6 根据不同的应用场合对差错率有不同的要求: 在电报传送时,允许的比特差错率约为: 104105； 计算机数据传输,一般要求比特差错率小于: 108109； 在遥控指令和武器系统的指令系统中,要求有更小的误比特率或码组差错率7 为定量地描述信号的差错,定义差错图样E E=CR (模M ) 最常用的二进制码可当作特例来研究,其差错图样等于收码与发码的模2加,即 E = C R 或 C = R E 设发送的码字C 1 1 1 1 1 1 1 1 1 1 接收的码字R 1 0 0 1 0 0 1 1 1 1 差错的图样E 0 1 1 0 1 1 0 0 0 0

3、 差错图样中的“1”既是符号差错也是比特差错,差错的个数叫汉明距离。0:传输中无错1:传输中有错8 随机差错： 差错是相互独立的,不相关 存在这种差错的信道是无记忆信道或随机信道 突发差错： 指成串出现的错误,错误与错误间有相关性,一个差错往往要影响到后面一串字 E: 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 突发长度= 4突发长度= 69 从功能角度讲,差错码分为检错码和纠错码 检错码：用于发现差错 纠错码：能自动纠正差错 纠错码与检错码在理论上没有本质区别,只是应用场合不同,而侧重的性能参数也不同。10 按照对信息序列的处理方法,有

4、分组码和卷积码 分组码： 将k个信息码元分成一组,由这k个码元按照一定规则产生r个监督码元,组成长度n = k + r的码字 卷积码： 先将信息序列分组,不同的是编解码运算不仅与本组信息有关,而且还与前面若干组有关。kk010 101 010 001 110 010 xxxx 101xxxx 010 xxxxrnr11 按照码元与原始信息位的关系,分为 线性码：所有码元均是原始信息元的线性组合,编码器不带反馈回路。 非线性码：码元并不都是信息元的线性组合,可能还与前面已编的码元有关,编码器可能含反馈回路。 由于非线性码的分析比较困难,早期实用的纠错码多为线性码,但当今发现的很多好码恰恰是非线性

5、码。12 按照适用的差错类型,分成: 纠随机差错码:用于随机差错信道,其纠错能力用码组内允许的独立差错的个数来衡量。 纠突发差错码:针对突发差错而设计,其纠错能力主要用可纠突发差错的最大长度来衡量13 前向纠错(FEC)： 发送端的信道编码器将信息码组编成具有一定纠错能力的码。 接收端信道译码器对接收码字进行译码,若传输中产生的差错数目在码的纠错能力之内时,译码器对差错进行定位并加以纠正。14 自动请求重发(ARQ)： 发端发送检错码， 收端译码器判断当前码字传输是否出错； 当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字(全部或部分)。15 混合纠错(HEC)： 是FEC与ARQ

6、方式的结合。 发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。 如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。 信息反馈(IRQ)： 收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没有发现错误为止。16 0:晴,1:雨 若10,01。收端无法发现错误00晴1001110011雨能发现一个错误禁用码组 插入1位监督码后具有检出1位错码的能力,但不能予以纠正。17000晴010001111000

7、111雨晴 在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检检出2位或2位以下的错码。100011101110雨18 最大似然译码： 将接收到的码字译码为与它的许用码字,并且认为这个许用码字就是它所对应的发送码字,从而在码字的纠错能力内实现自动纠错。 纠错编码之所以具有检错、纠错能力,是因为在信息码元之外加入了监督码。监督码不载信息,只是用来监督信息码在传输中有无差错。 纠错编码所提高的可靠性,是以牺牲信道利用率为代价换取的。 监督码引入越多,检错、纠错能力越强,但信道的传输效率下降也越多。1920(4) 等重码/定比码设计码字中的非0符号个数恒为常数，即 C 由全体重量恒等于 m

8、 的 n 重向量组成。5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。21(2) 最大似然译码译码过程 由图6.1.2可见：译码器接收到一个接收码字 R 后，按编码规则对 R 进行译码后输出信息码组的估值 m； 信息码组与码字 C 之间是有固定规则的，这相当于信道译码器能给出码字 C 的估值 C。当CC时就出现了译码错误。因为只有当 C=C 时，m=m。22最大后验概率译码准则 当译码器收到某一个接收码字R后，根据最大后验概率p(C/R)进行译码判决，一定是译码错误概率最小。 根据贝叶斯原理 似然函数：p(R/C)kiipp/pppppppi2 , 2 ,

9、1)(max)()()/(,)()()()()()(CRCRCRRCCCRCRCRCRCCC即具有最大值，要求条件概率最大就等效于则相同的先验概率如果所有码字23 设每个码字长为 n，若接收码字 R 与码字 C 的距离为 d(R,C)，则条件概率 p(RC) 可表示为 最大化 p(RC) 等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C 距离最小的译码。),(),(),(1)1 ()1 ()(CRCRCRCRdbbnbdbdnbpppppp) ,(),(min: CRCRCCddii24 信道编码 在被传输信息中附加一些冗余码冗余码,即监督码元,利用附加码元

10、与信息码元间的约束关系加以校验,以。 信源编码减少了 冗余度是随机的、无规律的 信道编码增加了 冗余度是特定的、有规律的,故可利用其在接收端进行检错和纠错。25 传输冗余比特必然要动用冗余的资源。 时间： 比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。 频带： 插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。 功率： 采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。 8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗

11、余比特。 设备复杂度： 加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。26 信道编码 按一定规则给数字序列m增加一些多余的码元,使不具有规律性的信息序列 m 变换为具有某种规律性的数码序列 C； 码序列中的信息序列码元与多余码元之间是的； 信道译码器利用这种预知的编码规则译码。检验接收到的数字序列 R 是否符合既定的 规则,从而发现 R 中是否有错,或者纠正其中的差错； 根据来检测/发现和纠正传输过程中产生的差错就是信道编码的基本思想。27 纠错编码的检错纠错能力,要取决于码组的码距 码距越大,检错、纠错能力越强。 汉明距离

12、： 二个码组对应码位码元不同的个数。 最小码距dmin： 一个码组的集合中任意二个码组间的最小汉明距离。 码重W： 码组中非0的数目。28 定理：若纠错码的最小距离为dmin，可以检测出任意小于等于l = dmin1个差错可以纠正任意小于等于 个差错21mindt可以检测出任意小于等于l同时纠正小于等于t个差错， 其中l、t满足： l + t dmin1 t l29 编码效率： 一个组中信息所占的比重nkR k：信息码元的数目 n：编码组码元的总数目 n = k+ r r：监督码元的数目30 奇偶校验码(n，n-1)(k+1，k) 偶校验码字0110pmmmk31(2) 偶（或奇）校验方法 一

13、个奇偶校验位 p 为偶校验位 m0+m1+m2+mk1+p=0 (mod 2) 则 C =(m0,m1,m2,mk1,p) 为一个偶校验码字。C 中一定有偶数个“1” 所有可能的 C 的全体称为一个码率为 k/(k+1) 的(k+1,k) 偶校验码； 确定校验位 p 的编码方程为 p= m0+m1+m2+mk1 当差错图案 E 中有奇数个“1”，即 R 中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。 校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。32多个奇偶校验位一个校验位可以由信息位的部分或全部按校验方程产生；例如 C 是一个对阵列消息进行垂直与水平

14、校验以及总校验的码字；其码率为2mod1, 1 , 0, 2mod1, 1 , 0, 2mod111) 1(1010,10,10,1,0, 11, 10, 1,01,00,0sitjjstitssijijstjjititstsststssttmmptjmpsimpppppmmpmmsttstsststRCl当校验位数增加时，可以检测到差错图案种类数也增加，同时码率减小。33(3) 重复消息位方法n重复码：码率为 1/n，仅有两个码字 C0和 C1，传送1比特(k=1)消息；C0=(000)，C1=(111)n重复码可以检测出任意小于 n/2 个差错的错误图案 BSC信道：pb1/2，n比特传输

15、中发生差错数目越少，概率越大 (1pb)n pb(1pb)n 1 pbt(1pb)n t pbn 总认为发生差错的图案是差错数目较少的图案，当接收到重复码的接收序列 R 中“1”的个数少于一半时，认为发送的是C0，否则认为是 C1。图6.1.7所示纠1个任意差错的3重复码。34 6.2.1 有噪信道编码定理 定理6.2 设有一个离散无记忆平稳信道，其信道容量为C。当信息传输率RC，只要码长n足够长，则总存在一种编码，可以使平均译码错误概率任意小。 这个定理称为有噪信道编码定理，又称为香农第二定理。 35 通过一个有噪信道可以实现几乎无失真传输，这与人们通过一个有噪信道可以实现几乎无失真传输，这

16、与人们的直观想象似乎是大相径庭的，而定理的证明也是非常巧的直观想象似乎是大相径庭的，而定理的证明也是非常巧妙的。香农巧妙地先，他不去构造理想的好码，而是用随妙的。香农巧妙地先，他不去构造理想的好码，而是用随机编码的方法得到所有可能生成的码的集合，然后在码集机编码的方法得到所有可能生成的码的集合，然后在码集合中随机选择一个码作为输入码序列，最后计算这样随机合中随机选择一个码作为输入码序列，最后计算这样随机选择的一个码在码集合上的平均性能。在译码时，利用了选择的一个码在码集合上的平均性能。在译码时，利用了联合典型序列的概念，即将接收序列译成与其联合典型的联合典型序列的概念，即将接收序列译成与其联合

17、典型的码字这种译码方法不是最优译码，但便于理论分析。码字这种译码方法不是最优译码，但便于理论分析。36 定义定义6.6 设 是长为n的随机序列对，且 则在这些随机序列对中同时满足以下条件的序列对称为联 合典型序列。(,)ijx y1()()nijijkkkpp x yx y1log(),ipH Xnxix即即 是是X的的典型序列；典型序列；(1)(2)1log(),jpH Xny即即 是是X的的典型序列；典型序列；1log(),ijpH XYnx , yiy(3)是任意小的正数。是任意小的正数。联合联合典型序列的全体构成的集合称为典型序列的全体构成的集合称为联合联合典型序典型序列集列集，记作，

18、记作()GXY37按照以上定义可以得到联合渐进等分割性。对于任意小的正数0,0,当n足够大时，有(1) 典型列集和联合典型列集的概率满足：()1( )1()1rrrP GXP G YP GXY ()()( )( )()()2()22()22()2n H Xn H Xin H Yn H Yjn H XYn H XYijpppxyx y(2) 典型列和联合典型列出现的概率满足：38典型序列典型序列 是输入端高概率出现的序列，典型序列是输入端高概率出现的序列，典型序列 是输是输出端高概率出现的序列，而联合典型序列对出端高概率出现的序列，而联合典型序列对 则是信则是信道输入和输出之间关联密切且经常出现的序列对。也就是道输入和输出之间关联密切且经常出现的序列对。也就是说，当某一输入典型序列说，当某一输入典型序列 发送时，必定高概率地以和它发送时，必定高