您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 计算机组成原理第7讲_校验码
计算机组成原理PrinciplesofComputerOrganization广义双语教学课程青岛理工大学校级精品课程@qtech.edu.cn2第3章运算方法和运算部件Errordetectionistheabilitytodetectthepresenceoferrorscausedbynoiseorotherimpairmentsduringtransmissionfromthetransmittertothereceiver:Errorcorrectionistheadditionalabilitytoreconstructtheoriginal,error-freedata.(6)§3.7数据校验码jlsheng@qtech.edu.cn3海明校验码HammingCode海明校验码是1种能检测1位或几位错误,又能自动纠正1位错误的线性分组码。在数据中加入若干个校验位,把各个数据位分在几个奇偶校验组中,把数据代码的码距比较均匀地拉大。任一位出错都会引起有关的几个校验位的值发生变化,从而发现错误。设m位校验码中数据为k位,校验位为r位。把校验码分成r组作奇偶校验。所产生的r位检错信息构成一个指误字,可指出2r种状态。指误字全0表示无错,其余2r-1种状态能指明k+r位中的某一位出错。即指误字应能表示k位数据哪一位出错,r个校验位哪一位出错和无错这k+r+1种情况。AHammingcodeisalinearerror-correctingcodenamedafteritsinventor,RichardHamming.Hammingcodescandetectuptotwosimultaneousbiterrors,andcorrectsingle-biterrors;4•若要求海明码能指出并纠正一位错,则数据位的位数k和校验位的位数r应满足如下关系(海明不等式):2r≥k+r+1此时码距为3,海明码中的每一信息位至少要参加两组奇偶校验并至少影响两个校验位。•若要求海明码能检测发现2位错并能自动纠正一位错,则数据位的位数k和校验位的位数r应满足如下关系:2r-1≥k+r满足这个不等式的海明码称为:扩展海明码/推广海明码此时码距为4,推广海明码中的每一信息位至少要参加3组奇偶校验并至少影响3个校验位。(1)校验位的位数海明校验码HammingCodejlsheng@qtech.edu.cn5(2)分组原则(编码规则)设:海明码HmHm-1……H2H1的最高位号为m,最低位号为1。m=k+r①每个校验位Pi在海明码中被分配在位号2i-1的位置,其余各位为数据位,并按从低向高逐位依次排列的关系分配。②海明码的每一位码Hi由多个校验位作校验,被校验的每一位的海明码位号等于校验它的各校验位的海明码位号之和,以便使校验的结果能正确反映出错位的位号。③在增大合法码的码距时,尽量使所有码的码距均匀的增大,以保证对所有码的检错能力平衡提高。[例1]8位数据的海明码(能指出并纠正一位错)的编码和校验①编码数据位k=8,按海明不等式算出r=4,m=k+r=12各位对应关系如下:数据位/校验位参与校验的校验位位号海明码位号H12H11H10H9H8H7H6H5H4H3H2H1D8D7D6D5P4D4D3D2P3D1P2P14,81,2,82,81,881,2,42,41,441,221按Pi的位号等于2i-1的关系,校验位P1,P2,P3,P4对应的海明码的位号分别为H1,H2,H4,H8。12位海明码分成4组进行偶校验。被校验的每一位的海明码位号等于校验它的各校验位的海明码位号之和。2r≥k+r+1各校验位与数据位的关系(本例为偶校验)为:数据位/校验位参与校验的校验位位号海明码位号H12H11H10H9H8H7H6H5H4H3H2H1D8D7D6D5P4D4D3D2P3D1P2P14,81,2,82,81,881,2,42,41,441,221754211DDDDDP764312DDDDDP84323DDDDP87654DDDDP每个小组只有一个校验位。每个校验位校验其自身和4~5个数据位,不参与其它校验位的校验。每个数据位至少出现在两个Pi值的形成关系中。当任一数据位发生变化时,必将引起二或三个Pi值跟着变化。不同信息位出现在Pi项中的次数不同。D4和D7出现3次,而D1、D2、D3、D5、D6、D8仅出现2次,使不同代码的海明码的码距不等。jlsheng@qtech.edu.cn8例如,数据11010011的海明码为001010011011海明码P1P2D1P3D2D3D4P4D5D6D7D8数据位/校验位H1H2H3H4H5H6H7H8H9H10H11H12海明码位号754211DDDDDP764312DDDDDP84323DDDDP87654DDDDP偶校验如果要求海明码能检测发现2位错并能自动纠正一位错,则推广海明码的校验位位数r=5。海明码的总位数m=k+r=13。13位海明码分成4组进行偶校验。各位对应关系如下:数据位/校验位参与校验的校验位位号海明码位号H13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P1134,81,2,82,81,881,2,42,41,441,221增加的一个校验位P5只能在H13。8653215DDDDDDP每个信息位都均匀地出现在3个Pi值的形成关系中。当任一信息位发生变化时,必将引起3个Pi值跟着变化。2r-1≥k+r或者12348653215PPPPDDDDDDPjlsheng@qtech.edu.cn10例如,数据11010011的推广海明码为0010100110110推广海明码P1P2D1P3D2D3D4P4D5D6D7D8P5数据位/校验位H1H2H3H4H5H6H7H8H9H10H11H12H13海明码位号754211DDDDDP764312DDDDDP84323DDDDP87654DDDDP8653215DDDDDDPjlsheng@qtech.edu.cn11②校验数据接收方按以下关系对收到的海明码进行校验(本例为偶校验),产生指误字(SyndromeWord):7542111DDDDDPS7643122DDDDDPS876544DDDDPS843233DDDDPS校验得到的结果S4S3S2S1的值构成指误字,能反映该12位海明码出错情况:jlsheng@qtech.edu.cn12①S4S3S2S1=0000,表明无错误。②S4S3S2S1中只有一位不为0,表明是某一校验位出错,出错的是该Si对应的Pi位,不需纠正。也可能是3位海明码(包括数据位和校验位)同时出错,但无法指出是哪3位错。由于多位代码同时出错的概率比仅一位代码出错的概率小得多,故认为是一位错。③S4S3S2S1中有两位或三位不为0,表明是一位数据位出错,出错位的位号由S4~S1这4位的编码值指明(例如,S4~S1=1011,则H11位出错),因此可将其纠正过来。或者可能是三个校验位同时出错,但此种出错的概率极小,故认为是一位错。④当S4S3S2S1中有4位不为0时,表明出错情况严重。指误字(SyndromeWord)D8H120011D7H111101D6H100101D5H91001P4H80001D4H71110D3H60110D2H51010P3H40010D1H31100P2H20100P1H110000000数据位/校验位出错位S1S2S3S4jlsheng@qtech.edu.cn14对于推广海明码86532155DDDDDDPSS5~S1的值构成指误字,反映该13位海明码出错情况:①S5S4S3S2S1=00000,表明无错误。②S5S4S3S2S1中只有一位不为0,表明是某一校验位出错,出错的是该Si对应的Pi位,不需纠正。也可能是3位海明码(包括数据位和校验位)同时出错,但无法指出是哪3位错。由于多位代码同时出错的概率比仅一位代码出错的概率小得多,故认为是一位错。jlsheng@qtech.edu.cn15对于推广海明码86532155DDDDDDPS③S5S4S3S2S1中有两位不为0,表明是2位海明码同时出错,但不能确定出错位的位号。④S5S4S3S2S1中有三位不为0,表明是一位数据位出错,出错位的位号由S4~S1这4位的编码值指明(例如,S5~S1=01011,则H11位出错),因此可将其纠正过来。或者可能是三个校验位同时出错,但此种出错的概率极小,故认为是一位错。⑤S5S4S3S2S1中有4位或5位不为0时,表明出错情况严重。7542111DDDDDPS7643122DDDDDPS876544DDDDPS843233DDDDPSP5H1300001D8H1200111D7H1111010D6H1001011D5H910011P4H800010D4H711100D3H601101D2H510101P3H400100D1H311001P2H201000P1H11000000000数据位/校验位出错位S1S2S3S4S5jlsheng@qtech.edu.cn17HomeworkCRCsarenot,bythemselves,suitableforprotectingagainstintentionalalterationofdata(forexample,inauthenticationapplicationsfordatasecurity),becausetheirconvenientmathematicalpropertiesmakeiteasytocomputetheCRCadjustmentrequiredtomatchanygivenchangetothedata.Allerrordetectioncodes(whichincludeallerror-detection-and-correctioncodes)transmitmorebitsthanwereintheoriginaldata.Anerror-correctingcode(ECC)orforwarderrorcorrection(FEC)codeisredundantdatathatisaddedtothemessageonthesenderside.3-26,jlsheng@qtech.edu.cn18测验1请写好自己的姓名、学号、班级19测验1一.(10分)求[X]补、[X/2]补、[X/4]补、[2X]补=?X=-43/64二.(12分)定点数的表示范围。32位整数原码。25位小数原码。28位整数补码。27位小数补码。三.(16分)定点补码加减法。求X+Y,X—YX=-0.5625,Y=+39/64请不要抄题,只写题号jlsheng@qtech.edu.cn20五.(16分)移码加减法。求X+Y,X—YX=-69,Y=+57四.(8分)求浮点数表示范围。尾数12位原码,阶码8位补码。写出该浮点数能表示的:最大正数,绝对值最大负数,最小正数,绝对值最小负数。测验1请不要抄题,只写题号三.(16分)定点补码加减法。求X+Y,X—YX=-0.5625,Y=+39/64jlsheng@qtech.edu.cn21五.(16分)移码加减法。求X+Y,X—YX=-69,Y=+57六.(23分)浮点数,尾数8位补码,阶码6位移码(都包括符号位)。X=-4.75,Y=+28.75,(1)求X和Y的规格化浮点机器数(2)求X+Y测验1请不要抄题,只写题号2
本文标题:计算机组成原理第7讲_校验码
链接地址:https://www.777doc.com/doc-2044322 .html