通信原理 信道编码基本概念汉明码编码错误图样纠检过程PPT课件

1、第1页/共35页有上述分析可知：假设一个码能检测e个独立错误，则要求其最小码距 dmine + 1反之，若码的最小距离为dmin，则最多能检测dmin-1个错码第2页/共35页第3页/共35页第4页/共35页由上述分析可知：一个码能纠正t个错码，则要求其最小码距 dmin 2t+1反之，若码的最小距离为dmin ，则最多能纠正 (dmin-1)/2个错码第5页/共35页一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1 (et)纠正t个错码，同时能检测e个错码，称为纠检结合，错码数较少时执行纠错方式，错码数较多时执行检错方式第6页/共35页有限域的简单知识所谓有限域

2、是指包含有限个元素的集合，按照所规定的运算规则运算后的结果仍为集合中的元素编码理论中有限域为0, 1二元集合，记为GF(2)GF(2)的加法与乘法： 1）加法：相同为0，相异为1； 2）乘法：除了11 = 1，其他均为0二元扩展域，记为GF(2n) ：由GF(2)中的元素构成的长为n的序列的集合，若 1）加法 2）乘法112200(, )nnnnXXxxxxxx112200(, )nnnnX Xxxxxxx120(,)(2 )GFnnnX xxx第7页/共35页二、线性分组码线性分组码的数学定义： 信道编码可表示为由编码前的信息码元空间Uk到编码后的码字空间Cn的一个映射f，即：f： Uk C

3、n 其中( n k ) 若f进一步满足线性关系：则称f为线性编码映射，若f为一一对应映射，则称f为唯一可译线性编码，由f编写的码c = (cn-1cn-2c0)称为线性分组码，u = (un-1un-2 u0 )为编码前的信息分组，其中k为信息位数，n为码长，其编码效率为= k/n()()(),(2)0,1, GF kfuufufuu uU 第8页/共35页数学定义的解释： 1）“线性”是指码组中码元之间的约束关系为线性； 2）“分组”是在编码时将每k个信息位分为一组进行独立处理； 3）将其变换成长度为n（nk）的二进制码组，一般称为（n, k）线性分组码线性分组码的特征： 1）加法封闭性：码

4、组集合中任意两个码组相加仍为集合中的一个许用码组； 2）全零序列是线性分组码中的一个码字； 3）码组集合中码组之间的最小码距等于某非零码字的最小码重第9页/共35页偶监督偶校验码发送端编码：将一位监督码元附加在信息码元后，使得码组中“1”码元个数为偶数（偶监督）接收端译码校验： 1）计数接收码组中“1”码元个数是否为偶数，即计算 S = an-1+ an-2+ a0 2）S = 0认为没错，S = 1认为有错 3）上式称为监督方程（监督关系式），其中S 称为校正子（校验子、伴随式） 4）S只能判断有错无措，而不能纠错汉明码的构造第10页/共35页 假设有1个信息码组由4位二进制位组成，在其后添

5、加3位二进制位作为监督码元，最后所组成的码组表示为：c = (u6u5u4u3c2c1c0)并且令： 1）c2监督u6 u5 u4，即 2）c1监督u6 u5 u3，即 3）c0监督u6 u4 u3，即接收端译码校验，得到监督方程：65310uuuc65420uuuc64300uuuc654226531164300uuucSuuucSuuucS6542uuuc6531uuuc6430uuuc第11页/共35页对于上式，若无错误发生，三个校验子均为0；假设传输过程中有且仅有一位发生错误：1）若c0发生错误，观察监督方程，则三个校验子S2 S1 S0的组合为001；2）若c1发生错误， S2 S1

6、 S0 = 010；3）若c2发生错误， S2 S1 S0 = 100；4）若u3发生错误， S2 S1 S0 = 011；5）若u4发生错误， S2 S1 S0 = 101；6）若u5发生错误， S2 S1 S0 = 110；7）若u6发生错误， S2 S1 S0 = 111；654226531164300uuucSuuucSuuucS第12页/共35页因此依据监督关系式就可计算出所有4位二进制信息位u6u5u4u3的监督位c2c1c0，这一过程即为( 7, 4 )线性码的构造过程，其码组空间为：654265316430000uuucuuucuuuc第13页/共35页监督矩阵的推导将监督关系

7、式进行变换观察发现上式即为一个线性方程组，因此可用矩阵方程来表示：654265316430000uuucuuucuuuc654321065432106543210111010001101010010110010uuuucccuuuucccuuuuccc 6543210111010001101010010110010uuuuccc 第14页/共35页对于上面的矩阵方程，令：则矩阵方程可化简为：HCT=OT 或 CHT=O那么H称为线性码监督矩阵，rn 阶的矩阵，由r（监督位个数）个线性独立方程组的系数组成，每一行代表了监督位与信息位间的监督关系。观察矩阵H：把具有(PIr)形式的H矩阵称为典型形

8、式的监督矩阵，其中P矩阵为rk 阶矩阵, Ir矩阵为rr 阶单位方阵H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关111010011010101011001H6543210 Cuuuuccc111010011010101011001rHP I0 0 0 O 第15页/共35页生成矩阵的推导对监督关系式进行移项变换（移动红色部分）：654321065432106543210111010011010101011001uuuucccuuuucccuuuuccc 210265436543654310210100011100110101010110001ccuucccuuuuuccc

9、uuuuuc 654326543165430111011101110111uuuucuuuucuuuuc 6251403111011011011ucucucu第16页/共35页观察上面的矩阵方程：其中系数矩阵与监督矩阵H中的P矩阵一样，对此矩阵方程两边做转置变换：其中Q = PT，为kr 阶矩阵；U矩阵表示信息位由上面的矩阵方程可知，只要用信息位与矩阵Q相乘就可得到监督位，然后拼接在信息位之后就是一个（n, k）线性分组码集合中的一个码字6251403111011011011ucucucu 21065436543111110101011TcccuuuuuuuuPUQ第17页/共35页虽然通过Q

10、矩阵可以产生线性分组码，但需要分为两步，如果对Q矩阵做变换： 在Q矩阵的左边加上一个kk阶单位阵，即：则一个（n, k）线性分组码可以通过下面的矩阵方程产生65436543654365432101000111010011000101010001011 kuuuu GuuuuIQuuuuuuuuccc1000111010011000101010001011kGIQ第18页/共35页对于生成矩阵G：1）kn阶矩阵；2）编码方法完全由生成矩阵G确定；3）把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中Ik为kk阶单位方阵，Q为k r阶矩阵；4）由典型生成矩阵产生的分组码一定是系统码；5）若某生成

11、矩阵G不具有典型形式，则产生的线性分组码为非系统码；若将G进行线性初等矩阵变换，使其具有典型形式，则产生的码组与不变换产生的码组有同样的纠检能力，即系统码与非系统码的纠检能力相同；6）H = PIr = QTIr G = IkQ = IkPT7）生成矩阵G的各行线性无关第19页/共35页对于监督矩阵H：1）H矩阵rn 阶的矩阵2）H矩阵中每行和其码组集合中的任一码字的内积为0；3）任意一个( n, k )线性分组码的H矩阵行线性无关；4）一个( n, k, d )线性分组码，若要至多纠正t个错误，则其充要条件是H矩阵中任何2t列线性无关，由于最小距离d = 2t + 1，所以也相当于要求H矩阵

12、中任意(d 1)列线性无关654321065432106543210111010001101010010110010ccccccccccccccccccccc 第20页/共35页生成矩阵G与监督矩阵H的关系：因为信息位不会全零，因此：再由： H = PIr，G = IkQ，代入上式，得：上式中矩阵的下标为其阶数TTTk rkk rrPG HIQPQOITTTTH COC HOU G HOCU GTG HO第21页/共35页例：设（7, 4）线性码的生成矩阵G为：当信息位为0001时，试求其后的监督位。1101000101010001100101110001第22页/共35页例：试求上例的监督矩

13、阵H解：根据生成矩阵和监督矩阵的关系：G = IkQ，H=PIr可得监督矩阵H为：100110101010110010111第23页/共35页对偶码定义：对于线性分组码： 1）将( n, k ) 码的监督矩阵H作为( n, n k )码的生成矩阵G； 2）将( n, k ) 码的生成矩阵G作为( n, n k )码的监督矩阵H这样的( n, k ) 码与( n, n k )码互为对偶码第24页/共35页编码过程观察(7, 4)码的监督关系式：可设计出相应的编码电路：654265316430uuucuuucuuuc第25页/共35页译码纠、检过程错误矩阵/错误图样E：设发送码组为c，接收码组为y

14、，则 对于二元有限域，上式中的减法等价于加法，即： 对于二元有限域的加法的具有确定两个码组中不同比特位的特性，例如：假设长度为n的码组A和B分别为：假设这两个码组的第k位不同，其他位相同，根据加法规则：因此接收端可以利用这种特性进行纠错，即若能确定错误图样就可以进行纠错：120nnecyeee120nnecyeee10()nnka aaa10()nnkb bbb1010()(0010)() nnknnka aaab bbb cey第26页/共35页接收端利用监督矩阵计算校正子S，即可见校正子S只与E有关，即错误图样与校正子之间有确定的关系而校正子S可以用接收码组y与监督矩阵HT相乘获得，则错误

15、图样也就得到确认，即：上式即为一个线性方程组，但它的解不唯一，即求得的错误图样不唯一。假设其中一个解为e0，即e0 HT = S，则对于码组集合中的任一许用码组c，下式一定成立：因此这个线性方程组一共有2k个解，即2k个错误图样TTTTTSyHec HeHcHeHTSeH000()TTTTec He HcHe HS第27页/共35页因此利用等式 及2k个错误图样可以纠正出2k个码组，即：稍作变换，每个等式进行移项：再由两个码组之和的码重等于两个码组的码距，可得：最佳译码应选择那些离y最近的 ，再由上式可知： 1）所有错误图样中选择码重最小图样； 2）该图样所对应的 作为纠正后的码组 cey00

16、 cey11 cey2121kkcey00ecy11ecy2121kkecy00( ,)( )d y cW e11( , )( )d y cW e2121( ,)()kkd y cW e c c第28页/共35页例如，某( 7, 3 )线性分组码的监督矩阵为：1）若收到的码组y = ( 1001001 )，则利用式S = yHT计算出校正子，其结果为S = ( 0111 )；2）再利用式eHT = S计算出所有可能的错误图样，因为k = 3，则共有8个图样分别为：( 1001001 ) ( 1010100 ) ( 1101110 ) ( 1110011 ) ( 0000111 ) ( 0011

17、010 ) ( 0100000 ) ( 0111101 )3）其中图样( 0100000 )的码重最小，则纠正后的码组为：e + y = ( 0100000 ) + ( 1001001 ) = ( 1101001 )1011000111010011000100110001H 第29页/共35页在实际中译码： 1）一般事先确定好每种校正子S所对应的所有错误图样； 2）选择码重最小的错误图样作为可纠正的错误图样； 3）然后将校正子与最小码重的错误图样制成表格； 4）译码时，利用校正子查表，然后用等式c = e + y进行纠正译码电路包括三个部分： 1）计算校正子； 2）查找确定纠正图样； 3）纠正

18、接收码组中的错误译码纠、检过程第30页/共35页某（7，4）码的监督矩阵以及校正子错误图样表：查表方法如下：第31页/共35页观察错误图样表发现校正子与错误图样一一对应利用二元有限域的乘法规则，对于等式：S2 S1 S0 = 1当且仅当S2、S1、S0全为1时成立，因此： 1）对每一校正子设计一个这样的乘式，保证其乘积为1； 2）对于右表共设计7个乘式，对应于7种可能出现的错误图样； 3）当三位校正子确定后，代入到7个乘式中计算，哪个乘式为1，就表明是哪一个图样2101SSS2101SSS21021021021021011111SSSSSSSSSSSSSSS第32页/共35页653226541154300uuucSuuucSuuucS c e y 210