差错控制编码

第九章差错控制编码（信道编码）9.1引言一、信源编码与信道编码数字通信中，根据不同的目的，编码分为信源编码与信道编码二大类。信源编码〜提高数字信号的有效性，如,PCM编码，M编码，图象数据压缩编码等。信道编码~提高传输的可靠性，又称抗干扰编码，纠错编码。由于数字通信传输过程中，受到干扰，乘性干扰引起的码间干扰，可用均衡办法解决。加性干扰解决的办法有：选择调制解码，提高发射功率。如果上述措施难以满足要求，则要考虑本章讨论的信道编码技术，对误码（可能或已经出现）进行差错控制。从差错控制角度看：信道分三类（：信道编码技术）随机信道：由加性白噪声引起的误码，错码是随机的，错码间统计独突发信道：错码成串，由脉冲噪声干扰引起。混合信道：既存在随机错误，又存在突发错码，那一种都不能忽略不计的信道。信道编码（差错控制编码）是使不带规律性的原始数字信号，带上规律性（或加强规律性，或规律性不强）的数字信号，信道译码器则利用这些规律性来鉴别是否发生错误，或进而纠错。需要说明的是信道编码是用增加数码，增加冗余来提高抗干扰能力。二：差错控制的工作方式（1） 检错重发（2） 前向纠错，不要反向信道（3） 反馈校验法，双向信道这三种差错控制的工作方式见下图所示：检错重发二：差错控制的工作方式（1） 检错重发（2） 前向纠错，不要反向信道（3） 反馈校验法，双向信道这三种差错控制的工作方式见下图所示：检错重发前向纠错r^"i检错误判决信号纠错码反馈校验法 信息信号信息信号9.2纠错编码的基本原理举例说明纠错编码的基本原理。用三位二进制编码表示8种不同天气。厂0厂000晴001云010阴一组码共011雨8种中只准许使甬4种计8种100雪101霜110雾111雹000晴、Oil云》1oi阴〉许用码组，其它为禁用码组1 1 0雨许用码组中，只要错一位（不管哪位错，）就是禁用码组，故这种编码能发现任何一位出错，但不能发现的二位出错，二位出错后又产生许用码。上述这种编码只能检测错误，不能纠正错误。因为晴雨阴错一位，都变成100。要想纠错，可以把8种组合（3位编码）中，只取2种为许用码，其它6种为禁用码。例如：000晴 111雨这时，接收端能检测两个以下的错误，或者能纠正一个错码。例：收到禁用码组100时，如认为只有一位错，则可判断此错码发生在第1位，从而纠正为000（晴），因为111（雨）发生任何一个错误都不会变成100。若上述接收码组种的错码数认为不超过二个，则存在两种可能性：000)/000)/(111)错位错位变成100因为只能检出错误，但不能纠正。一：分组码，码重，码距（见樊书P282表9-1）将码组分段：分成信息位段和监督位段，称为分组码，记为i,（k）n~编码组的总位数，简称码长（码组的长度）k~每组二进制信息码元数目（，信息位段）n-k=r〜监督码元数目，（监督位段（见樊书P282，图9-2）在分组码中，有“1”的数目称为码组的重量，简称码重。例如，码组(11010),码长n=5,码重为3。把两个码组对应位不同的数目称为这两个码组的距离，简称码距，又称Hamming(汉明)的距离。(11000A例如，码组(11000)与(10011)的距离为3。(10011丿而码组集合中，全体码组之间的距离的最小值称为最小码距d()。0码距的几何意义见樊书P283，图9-3。从图看出，码距d越大，检错，纠错能力越强。二：纠错编码的效用樊书P284监督位数r越多，对提高抗干扰，降低误码率越有好处。例子表明：纠错码的抗干扰能力完全取决于许用码字之间的距离码，的最小距离越大，说明码字的最小差别越大，抗干扰能力就越。因此，码字之间的最小距离是衡量该码字检错和纠错能力的重要依据，最小码距是信道编码的一个重要的参数。在一般情况下，分组码的最小汉明距离与检错和纠错能力之间满足下列关系：当码字用于检测错误时，如果要检测个错误，则d>e+10当码字用于纠正错误时，如果要纠正个错误，则d>2t+10若码字用于纠t个错误，同时检e个错误时(e>t)，则d>t+e+19.3常用的简单编码纠错码的分类(沈振元书P388)(1)奇偶校验码“1”的数目应为偶数或奇数)(见樊书P285)

偶校验码满足条件：a㊉a㊉ ㊉a=0n-1举例：偶校验的例子：n-2 0㊉㊉㊉㊉㊉码组：110011广F广0广飞广飞广码长n—6，11001*— -_ —-1信息位段长k—5， 信息位偶校验位监督位数r—1偶校验位=“1”满足条件：1㊉1㊉0㊉0㊉1㊉1—0(2)二维奇偶校验码仍然举偶校验的例子11对称出现4个错/码也检不出来/11100 1 1]j行监督位1㊉1㊉0㊉0㊉1㊉11对称出现4个错/码也检不出来/1111010701 /110001111001100001I I~1~10节 S I」\列监督位，)㊉1㊉0㊉0㊉0㊉1=0(3)恒比码例如，我国电传机传输阿拉伯数字时，用5位代码表示，每个码组的长度为5，其中恒有3个“1”，称为“5中取3”恒比码。阿拉伯数字保护电码阿拉伯数字保护电码101011610101211001711100310110801110411010910011500111001101(4)正反码正反码的信息位段长与监督位段长相同，如正反码组：信息位段有奇数个1:1100111001 (监督位与信息位重复)信息位段有偶数个1：1000101110普位(监督位是信息位反码)信息位监督位9.4线性分组码一：基本概念可用线性方程组（代数关系）表述码的规律性的分组码为线性分组码。如奇偶校验码的编程原理利用了代数关系，a㊉a㊉…㊉a=0（偶校验关系）称奇偶校验码为线性分组码。n—1n—2 0在代数码中，常见的是线性码，即编码中的信息位和监督位是由一些线性代数方程联系着，或者说可用线性代数方程表述编码的规律性。上述正反码中，为了纠正一位错误，使用的监督位和信息位一样多，即编码效率只有50%（编码效率n=k/n）。那么为了纠正一位错误码在分组码中最少要几位监督码位？编码效率能否提高。从这种思想出发，便导致了汉明码的诞生。汉明码是能够纠正一位错码且编码效率较高的一种线性分组码。二：线性分组码的一种一一汉明码下面介绍汉明码（Hamming）的构造原理。先回顾偶校验码，在接收端实际上计算监督关系式:s=a㊉a㊉…㊉an—1n—2 0若s=0〜无错s=1〜有错s〜称校正子由于s校正子只有两种形式0”或“1”只能代表有错或无错，因而不能找出错码的位置。不难想象，如果监督位增加一位，即变成二位监督位，即能增加一个类似于偶校验码监督式的新的监督式。两个监督式就有两个校正子，其可能值有4种组合：00，01，10，11，这4种组合代表不同信息。若用1种组合表示无错，其余3种组合就可以用来表示一位错码的3种不同位置。同理，r个监督式能指示一位错码的2r-1个可能位置。一般来说，若码长n，信息位数k，则监督位r=n—k，汉明码n与r满足：n=2r—1

现以（n,k）=（7,4）,r=3为例的汉明码来说明如何具体构造这些监督关系式。设码字（n，设码字（n，k）=aaaa654 0210aaa~信息位654s,s,s〜校正子（3个监督关系式中的校正子）123这3个校正子s,s,s,可建立三个互为独立的监督关系式。123s,s,s的值与错码位置的对应关系可以规定如下表：123（见樊书P288，图9-4）s,s,s1 2 3错码位置s,s,s1 2 3错码位置001a0101a4010a1110a5100a2111a6011a3000无错s,s,s全为零,表示无错。123只要s（或s,或s）为“1”，就表示有错，s是不是1,由a,a,a,a1 2 3 1 2 4 5 6的出错决定,可写成偶监督关系式：s=a㊉a㊉a㊉a1 6 5 4 2（只有s］为零时才无错，发送编码时，将监督码a2与信息码元的关系满足此式）同理s=a㊉a㊉a㊉a26531同理s=a㊉a㊉a㊉a3 6 4 3 0在发端编码时，信息位a,a,a,a的值是随机的，监督位a,a,a应根3 4 5 6 2 1 0据信息位按监督关系来确定，即监督位应使上面的,s,s监督式为零。123即要求：a㊉a㊉a㊉a=06542a㊉a㊉a㊉a=06531a㊉a㊉a㊉a=06430或写成监督码元在左边的形式：a=a㊉a㊉a2654a=a㊉a㊉a1 6 5 3a=a㊉a㊉a0643

信息位作,a5，a4，厲一旦确定后，可直接按上式计算出监督位。（见樊书P289图9-5）接收端收到每个码字（码组）后，先计算出偶监督关系式，s,s,s再按123表9-4（樊书P288）判断错码情况。如果Si,S2,S3不全零，可判出在哪一位出错。a二二a㊉a㊉a二二a㊉a㊉a2654a二二a㊉a㊉a1653a二二a㊉a㊉a0643发送端，将信息位按此式加上监督位后发送a㊉a㊉a㊉a=06542a㊉a㊉a㊉a=06531a㊉a㊉a㊉a=06430查樊书表9-4,判错哪一位并纠正之接收端，先计算校9S2,S3为零否，丄 厶 O不为零则出错码，查表后，纠正改之汉明码最小距d=3（见樊书表9-5），能够纠正单个错误。0三：线性分组码的一般原理（1）监督阵和生成矩阵将上述汉明码74）的监督关系式改写成（见樊书P289,9.4-8）TOC\o"1-5"\h\z1-a+1-a+1-a+0-a+1-a+0-a+0-a=06 5 4 3 2 1 01-a+1-a+0-a+1-a+0-a+1-a+0-a=06 5 4 3 2 1 01-a+0-a+1-a+1-a+0-a+0-a+1-a=06 5 4 3 2 1 0上式中㊉简写为+,表示模2相加。写成矩阵形式：11101110101011000"a"11101110101011000"a"0"410a=0301a0—2——5a10模2)简记H简记H-At=0t (H监督矩阵）监督矩阵H为rxn（r行，n列）阶矩阵，H阵的每行之间彼此线性无关。也可将H矩阵分为两部分:j11j11H=110101a6a3001 0 0\o"CurrentDocument"0 1 0 =[pi ]r\o"CurrentDocument"0 0 1aaa210其中其中P为rXk阶矩阵，i为rXr阶单位矩阵。r若把监督关系式改写补充:za「6—a6a—a55aza「6—a6a—a55a—4a—3a—a+a265a—a+a165<a—a06+a4+a+a+a可改写为矩阵形式:即At=Gta6a5a4a3a"1000~6a01005aa001064aa—0001—53aa111042aa110131a10110'―—1433变换为A=[aaaa6543100其中G=1001100其中G=100100kG称为生成矩阵，0111011001011011Q如果找到G,则纠错编码方法就确定了，可由信息组和G可产生全部码字。11G比Q11G比Q]〜也称典型生成矩阵，其中Q=k0110111000IkIk为尺方车10010001由典型生成矩阵得出的码组A中，信息位不变，监督位附加其后，这种码称为系统码。（2）校正子S（伴随式）设发送码组A=ta,a,…a,a]（在传输过程中可能发生误码）n—1n-2 10设接收码组B=lb,b，…b,bJn—1n—2 1 0则发送码组与接收码组之差定义海（也称错误图样）E=B—A（模2）[en—[en—1,en—2…e,eJ，其中e=10i0,当b=a2 i i1,当b丰aii因此，若e=0，表示该位接收码元无错；若=1，则表示有错。iiE=B—A，也可改写为B=A+E例如：发送A=[1000111]错误E=[0000100]接收B=[1000011]令S=B-Ht 称S为校正子，也称伴随式。S二B-HT二(A+E)Ht二AHt+EHt——一零矩阵二EHt 、~由此可见，校正子