第7章 数据传输PPT讲稿.ppt
第7章 数据传输第1页，共65页，编辑于2022年，星期一7.1 纠错与线性分组码的编码原则纠错与线性分组码的编码原则1、纠错、纠错信道编码信道编码通过在发送端增加冗余使消息出现传输错误时由接收通过在发送端增加冗余使消息出现传输错误时由接收端进行纠正端进行纠正纠错纠错第2页，共65页，编辑于2022年，星期一2、n重复码重复码例例1信源等概率时的平均译码错误概率信源等概率时的平均译码错误概率第3页，共65页，编辑于2022年，星期一最大似然准则译码最大似然准则译码收到收到y1时时收到收到y2时时第4页，共65页，编辑于2022年，星期一平均译码错误概率平均译码错误概率通信系统中一般要求平均译码错误概率的数量级通信系统中一般要求平均译码错误概率的数量级10-6-10-9第5页，共65页，编辑于2022年，星期一三重复码三重复码消息重复三次消息重复三次x1=0c1=000，x2=1c2=111三次扩展信源的子信源，三次扩展信三次扩展信源的子信源，三次扩展信宿宿三次扩展信道的子信道三次扩展信道的子信道第6页，共65页，编辑于2022年，星期一最大似然准则译码最大似然准则译码收到收到y1=000时时收到收到y2=001时时第7页，共65页，编辑于2022年，星期一收到收到y3=010时时收到收到y4=011时时收到收到y5=100时时第8页，共65页，编辑于2022年，星期一收到收到y6=101时时收到收到y7=110时时收到收到y8=111时时第9页，共65页，编辑于2022年，星期一三重复码三重复码通过在发送端增加冗余使消息出现一位传输错通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正误时由接收端进行纠正纠错纠错第10页，共65页，编辑于2022年，星期一平均译码错误概率平均译码错误概率第11页，共65页，编辑于2022年，星期一重复重复n次次n重复码重复码n重复码的码长为原来的重复码的码长为原来的n倍倍编码效率为编码效率为1/n第12页，共65页，编辑于2022年，星期一需要找的需要找的“好码好码”足够小的平均译码错误概率足够小的平均译码错误概率Pe较高的编码效率较高的编码效率第13页，共65页，编辑于2022年，星期一3、线性分组码及其编码原则、线性分组码及其编码原则线性分组码线性分组码定义定义具有恒定码字长度和消息长度，消息相加后的编码等具有恒定码字长度和消息长度，消息相加后的编码等同于各自编码相加的纠错码同于各自编码相加的纠错码表示表示(n,k)其中其中n为码字长度，为码字长度，k为消息长度，为消息长度，n-k为校验为校验长度长度第14页，共65页，编辑于2022年，星期一例例2(4,3)偶校验码偶校验码第15页，共65页，编辑于2022年，星期一码距和最小码距码距和最小码距2k个码字构成的码表中，任意两个码字之间的码距个码字构成的码表中，任意两个码字之间的码距(汉汉明距离明距离)定义定义任意两个码字对应位上不同码元的个数任意两个码字对应位上不同码元的个数表示表示第16页，共65页，编辑于2022年，星期一例例3(4,3)偶校验码中码字偶校验码中码字c2和和c3之间的码距之间的码距d23第17页，共65页，编辑于2022年，星期一2k个码字构成的码表中，码字之间的最小码距个码字构成的码表中，码字之间的最小码距定义定义所有码字之间码距的最小值所有码字之间码距的最小值表示表示第18页，共65页，编辑于2022年，星期一线性分组码的编码原则线性分组码的编码原则例例4(3,1)线性分组码线性分组码三次扩展信源中三次扩展信源中8个可能的码字个可能的码字第19页，共65页，编辑于2022年，星期一8个可能的码字构成的码表中，任意两个码字之间的个可能的码字构成的码表中，任意两个码字之间的码距码距第20页，共65页，编辑于2022年，星期一如果选取其中如果选取其中c1=000，c8=111为许用码，其余为禁用码为许用码，其余为禁用码三重复码三重复码2个码字构成的码表中个码字构成的码表中及信源等概率条件下的平均译码错误概率及信源等概率条件下的平均译码错误概率在信道在信道第21页，共65页，编辑于2022年，星期一如果选取其中如果选取其中c2=001，c7=110为许用码，其余为禁用为许用码，其余为禁用码码2个码字构成的码表中个码字构成的码表中及信源等概率条件下及信源等概率条件下在信道在信道第22页，共65页，编辑于2022年，星期一x=0c2=001，x=1c7=110三次扩展信源的子信三次扩展信源的子信源，三次扩展信宿源，三次扩展信宿三次扩展信道的子信道三次扩展信道的子信道第23页，共65页，编辑于2022年，星期一最大似然准则译码最大似然准则译码收到收到y1=000时时收到收到y2=001时时第24页，共65页，编辑于2022年，星期一收到收到y3=010时时收到收到y4=011时时收到收到y5=100时时第25页，共65页，编辑于2022年，星期一收到收到y6=101时时收到收到y7=110时时收到收到y8=111时时第26页，共65页，编辑于2022年，星期一通过在发送端增加冗余使消息出现一位传输错误时由接通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正收端进行纠正纠错纠错第27页，共65页，编辑于2022年，星期一平均译码错误概率平均译码错误概率第28页，共65页，编辑于2022年，星期一如果选取其中如果选取其中c1=000，c5=100为许用码，其余为禁用码为许用码，其余为禁用码2个码字构成的码表中个码字构成的码表中及信源等概率条件下及信源等概率条件下在信道在信道第29页，共65页，编辑于2022年，星期一x=0c1=000，x=1c5=100三次扩展信源的子信源，三次扩展信源的子信源，三次扩展信宿三次扩展信宿三次扩展信道的子信道三次扩展信道的子信道第30页，共65页，编辑于2022年，星期一最大似然准则译码最大似然准则译码收到收到y1=000时时收到收到y2=001时时第31页，共65页，编辑于2022年，星期一收到收到y3=010时时收到收到y4=011时时收到收到y5=100时时第32页，共65页，编辑于2022年，星期一收到收到y6=101时时收到收到y7=110时时收到收到y8=111时时第33页，共65页，编辑于2022年，星期一通过在发送端增加冗余使消息出现一位传输错误时不通过在发送端增加冗余使消息出现一位传输错误时不能完全由接收端进行纠正能完全由接收端进行纠正第34页，共65页，编辑于2022年，星期一平均译码错误概率平均译码错误概率第35页，共65页，编辑于2022年，星期一线性分组码的编码线性分组码的编码选取许用码选取许用码线性分组码的编码原则线性分组码的编码原则保证最小码距足够大保证最小码距足够大第36页，共65页，编辑于2022年，星期一线性分组码检错纠错的充要条件线性分组码检错纠错的充要条件线性分组码线性分组码(n,k)检检e位错并同时纠位错并同时纠t位错的充要条件位错的充要条件检一位错并同时纠一位错的充要条件检一位错并同时纠一位错的充要条件第37页，共65页，编辑于2022年，星期一7.2 汉明汉明码码汉明码汉明码最小码距最小码距dmin=3的线性分组码的线性分组码设设(n,k)汉明码的码字汉明码的码字为校验位，校验长度为为校验位，校验长度为n-k其中其中 为消息位，消息长度为为消息位，消息长度为k第38页，共65页，编辑于2022年，星期一1、汉明码的编码、汉明码的编码编码步骤编码步骤构造满秩的构造满秩的(n-k)n校验矩阵校验矩阵Hri第第i个接收码字，个接收码字，1n向量向量si第第i个接收码字的误码标志，个接收码字的误码标志，1(n-k)向量向量ci第第i个发送码字，个发送码字，1n向量向量第39页，共65页，编辑于2022年，星期一设满秩的设满秩的kn生成矩阵生成矩阵Gxi第第i个发送消息，个发送消息，1k向量向量由生成矩阵由生成矩阵G与校验矩阵与校验矩阵H之间之间GHT=0求出求出G即可编即可编码码第40页，共65页，编辑于2022年，星期一例例1(3,1)汉明码汉明码构造满秩的构造满秩的23校验矩阵校验矩阵H所有所有2维非零列向量构成校验矩阵维非零列向量构成校验矩阵H，如，如第41页，共65页，编辑于2022年，星期一设满秩的设满秩的13生成矩阵生成矩阵G第42页，共65页，编辑于2022年，星期一最小码距最小码距(3,1)汉明码汉明码三重复码能检一位错并同时纠一位错三重复码能检一位错并同时纠一位错(3,1)汉明码的码长为原来的汉明码的码长为原来的3倍倍编码效率为编码效率为1/3第43页，共65页，编辑于2022年，星期一例例2(7,4)汉明码的编码汉明码的编码构造满秩的构造满秩的37校验矩阵校验矩阵H所有所有3维非零列向量构成校验矩阵维非零列向量构成校验矩阵H，如，如第44页，共65页，编辑于2022年，星期一设满秩的设满秩的47生成矩阵生成矩阵G第45页，共65页，编辑于2022年，星期一第46页，共65页，编辑于2022年，星期一第47页，共65页，编辑于2022年，星期一第48页，共65页，编辑于2022年，星期一第49页，共65页，编辑于2022年，星期一第50页，共65页，编辑于2022年，星期一第51页，共65页，编辑于2022年，星期一第52页，共65页，编辑于2022年，星期一任意两个码字之间的码距任意两个码字之间的码距最小码距最小码距第53页，共65页，编辑于2022年，星期一(7,4)汉明码能检一位错并同时纠一位错汉明码能检一位错并同时纠一位错(7,4)汉明码的码长为原来的汉明码的码长为原来的7/4倍倍编码效率为编码效率为4/7第54页，共65页，编辑于2022年，星期一2、汉明码的译码、汉明码的译码译码步骤译码步骤检错检错误码标志误码标志si当出现一位传输错误当出现一位传输错误第55页，共65页，编辑于2022年，星期一第56页，共65页，编辑于2022年，星期一纠错纠错(n-k)n变换变换+模二加模二加通过通过(n-k)n变换将误码标志变换将误码标志si变换为形如变换为形如1000，0100，0001，0000的错误图案的错误图案ei错误图案错误图案ei与接收码字与接收码字ri的模二加的模二加第57页，共65页，编辑于2022年，星期一例例3(7,4)汉明码的译码汉明码的译码第58页，共65页，编辑于2022年，星期一第59页，共65页，编辑于2022年，星期一第60页，共65页，编辑于2022年，星期一第61页，共65页，编辑于2022年，星期一检错检错误码标志误码标志s6第62页，共65页，编辑于2022年，星期一纠错纠错3-7变换变换+模二加模二加第63页，共65页，编辑于2022年，星期一检错检错误码标志误码标志s6第64页，共65页，编辑于2022年，星期一纠错纠错3-7变换变换+模二加模二加第65页，共65页，编辑于2022年，星期一
