信息论与编码第6章 信道编码

1、26.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、端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。 如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。 特点： 充分发挥码的检错和纠错性能,在较差的信道中仍可收到较好的效果。 需反馈信道和较复杂的译码电路16 信息反馈(IRQ)： 收端把收到的信息原封不动反馈回发端,发端比较反馈信息与原信息,若有错,重发。 特点： 没有检错和纠错编码,电路简单， 需反馈信道,且传输速率低。17 从概念上分析纠错编码的基本原理,可以把纠错能力的获取归结为两条： 利用冗余度 噪声均化(随机化、概率化)

7、冗余度 就是在信息流中插入冗余比特,这些冗余比特与信息比特之间存在着特定的相关性。 在传输过程中个别信息受损,可以利用相关性从其他未受损的冗余比特中推测出受损比特的原貌,保证了信息的可靠性。18 0:晴,1:雨 若10,01。收端无法发现错误00晴1001110011雨能发现一个错误禁用码组 插入1位监督码后具有检出1位错码的能力,但不能予以纠正。19000晴010001111000111雨晴 在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检检出2位或2位以下的错码。100011101110雨20 最大似然译码： 将接收到的码字译码为与它的许用码字,并且认为这个许用码字就是它所对应

8、的发送码字,从而在码字的纠错能力内实现自动纠错。 纠错编码之所以具有检错、纠错能力,是因为在信息码元之外加入了监督码。监督码不载信息,只是用来监督信息码在传输中有无差错。 纠错编码所提高的可靠性,是以牺牲信道利用率为代价换取的。 监督码引入越多,检错、纠错能力越强,但信道的传输效率下降也越多。21 传输冗余比特必然要动用冗余的资源。 时间： 比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。 频带： 插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。 功率： 采用多进制符号,用8进制ASK符号代替4

9、进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。 8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。 设备复杂度： 加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。22 信道编码 在被传输信息中附加一些冗余码冗余码,即监督码元,利用附加码元与信息码元间的约束关系加以校验,以。 信源编码减少了 冗余度是随机的、无规律的 信道编码增加了 冗余度是特定的、有规律的,故可利用其在接收端进行检错和纠错。23 噪声均化 设法将危害较大的、较为集中的噪声干扰分摊开来,使不可恢复的信息损伤最小。

10、噪声干扰的危害大小不仅与噪声总量有关,而且与其分布有关。 集中的噪声干扰(突发差错)的危害甚于分散的噪声干扰(随机差错)。 噪声均化正是将差错均匀分摊给各码字,达到提高总体差错控制能力的目的。24 噪声均化的方法主要有3种： 增加码长N 增加码长可使译码误差减小的原因在于:码长越大,具体每个码字中误码的比例就越接近统计平均值。 卷积 卷积码在一定约束长度内的若干码字之间也加进了相关性,译码时不是根据单个码字,而是一串码字来作判决 交错(交织)25c1, c2, c3, c4, c5, c6, c7, c8, c9, 输入写交织传输写去交织输出c1, c2, c3, c4, c5, c6, c7

11、, c8, c9, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,c13, c14, c15, c16,c1, c5, c9, c13, c2, c6, c10, c14, c3, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12,c13, c14, c15, c16,260, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,0, 1, 0, 0 0, 1, 0, 0 0, 1, 0, 0 1, 0, 0, 0写0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0,

12、 1, 突发差错离散差错传输去交织输出27 译码器的任务 从受损的信息序列中尽可能正确地恢复出原信息。 码字： ci = (ci1, ci2, , ciN) 接收码： r = (r1,r2, rN)28 最佳译码(最大后验概率译码)： 在已知r的条件下找出可能性最大的发码c作为译码估值： )|(maxrcpcii 最佳译码是一种通过经验与归纳由收码推测发码的方法,是我们认为的最优译码算法。 在实际译码时,后验概率的定量确定是很困难的29 最大似然译码： 在已知r的条件下使先验概率最大的译码算法,即令)|(maxiicrpc p(r | c)：似然函数30 根据贝叶斯公式可以建立先验概率和后验概

13、率之间的关系 p(ci)是发送码字c的概率 p(r)是接收码为r的概率 p(r |c)是先验概率 p(ci|r)是后验概率)()|()()|(rpcrpcprcpiii31 BSC信道的最大似然译码可以简化为最小汉明距离译码。 当逐位比较发码和收码时,仅存在两种可能性: 相同或不同。 两种情况发生的概率分别是：)(1)()|(jijjijijjrcprcpcrp 如果r中有d个码元与ci的码元不同,则r与ci的汉明距离是d 。32 汉明距离NjijjiicrcrWcrdisd1)(),( 发送的码字C 1 1 1 1 1 1 1 1 1 1 接收的码字R 1 0 0 1 0 0 1 1 1 1

14、 差错的图样E 0 1 1 0 1 1 0 0 0 0 d= 433 似然函数 1( | )( | )(1)() 11NNdN ddijijjppr cpr cpppp 式中,(1p )N是常数,而 p / (1p )1。 d越大,似然函数p(r |ci)越小,因此求最大似然函数max p(r |ci)的问题可转化成求最小汉明距离 mind的问题。34 纠错编码的检错纠错能力,要取决于码组的码距 码距越大,检错、纠错能力越强。 汉明距离： 二个码组对应码位码元不同的个数。 最小码距dmin： 一个码组的集合中任意二个码组间的最小汉明距离。 码重W： 码组中非0的数目。35 定理：若纠错码的最小

15、距离为dmin，可以检测出任意小于等于l = dmin1个差错可以纠正任意小于等于 个差错21mindt可以检测出任意小于等于l同时纠正小于等于t个差错， 其中l、t满足： l + t dmin1 t l36 编码效率： 一个组中信息所占的比重nkR k：信息码元的数目 n：编码组码元的总数目 n = k+ r r：监督码元的数目37 奇偶校验码(n，n-1)(k+1，k)0110pmmmk p 为偶校验位 则 C =(m0,m1,m2,mk1,p) 为一个偶校验码字。C 中一定有偶数个“1”准用码000011101110m2m1 00 01 10 11 p0110禁用码00101010011

16、138 n重复码： 码率为 1/n,仅有两个码字C0和C1,传送1比特(k=1)消息； C0=(000),C1=(111) n重复码可以检测出任意小于 n/2 个差错的错误图案 BSC信道：p1/2,n比特传输中发生差错数目越少,概率越大 (1p)N p(1p)N 1 pd(1p)Nd pN 总认为发生差错的图案是差错数目较少的图案。3940 等重码/定比码 设计码字中的非0符号个数恒为常数,即 C 由全体重量恒等于 m 的 n 重向量组成。 5中取3等重码可以检测出全部奇数位差错,对某些码字的传输则可以检测出部分偶数位差错。4142 重复码(n,l)： n,可靠性,有效性 奇(偶)监督码(n

17、,nl)： n,有效性,抗干扰性 只能发现单个或奇数个独立随机差错 我们要寻找的是： 随着n增长 差错率Pe0 的信道编码 编码效率R1 迄今为止,已找到的绝大多数实用编码方法,都无法同时满足上述既可靠又有效的要求。43 线性分组码： 可用线性方程组表述码的规律性的分组码。 分组码： 把信源输出的信息序列按k个相继码元分为一组并按一定规律对每一信息组增加r个监督码元,组成长为 的码字。44 线性分组码的编码： 二进制： 码长n 2n 种组合 分组码(n,k) 2k 码字集合 分组码的编码问题就是定出一套:45 例： (7,3) 线性分组码。 n =7,k =3, r =4, 码率R=k/n=3

18、/7 输入编码器的信息分为3个一组:m = m3 m2 m1 设码字为:(c6c5c4c3c2c1c0) c6c5c4为信息元 c3c2c1c0为监督元,每个码元取“0”或“1”46mGc101110011100100111001)(123mmm47 G:生成矩阵 (kn)矩阵 ,可以产生整个码组 mGc101110011100100111001)(123mmm48 例:信息码组 (101),即c6=1,c5=0,c4 =1由信息码组 (101) 编出的码字为:1010011101110011100100111001101c49500000100011001000110010111000110

19、10123456ccccccc51000010001100100011001011100011010123456ccccccc52 假定(n，k)线性码是， G =IkP 则： H =PTIn-k (7,4)线性分组码:1 1 1 0 1 0 01 1 0 1 0 1 01 0 1 1 0 0 1H1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1G53 线性分组码 生成矩阵G 校验矩阵H 54 伴随式译码 设发送码组C = cn-1 c1c0 接收码组R = rn-1 r1 r0 差错图样E = en-1 e1 e0ECRCRCRE收码有

20、错收码无错00(TTTTTEHEHCHE)HCRH55 定义： (n,k)线性分组码的伴随式是一个r维向量S S = (sr-1 s1 s0) = RHT =EHT56 采用伴随式纠错译码的方法是(图6-13)按最可能出现的2r (qr )个差错图案E,计算相应的伴随式S,并构造伴随式差错图样表S，E对接收向量R计算伴随式S查S,E表得E纠错计算ERC57 例：已知(6,3)线性分组码的生成矩阵：ES000000000100000111010000110001000011000100100000010010000001001100010101100010001110011111IPHT1101

21、00011010111001G58001100010001110011111100110TRHS100111000001100110ERC5960 标准阵列的构造方法是：选择所有码字构成阵列的第0行,通常将全零码字 C0作为第0行第 1列元素。选择差错图案Ei作为第0列,通常以无差错图案E0= (00)作为第0列第 1行元素。阵列中的i行j列元素为EiCj; i =0,l,2r，j = 0,l,2k对越小的i, Ei选择为越容易出现的差错图案，61C0000000C1001011C2010110C3011101C4100111C5101100C6110001C7111010SE0000000 E0 +C0E0 +C1E0 +C2E0 +C3E0 +C4E0 +C5E0 +C6E0 +C7000E1100000E1 +C0E1 +C1101011111E2010000E2 +C0110E3001000E3 +C0Ei +Cj010101011E4000100E4 +C0100E5000010E5 +C0010E600