数字逻辑邓建021416.ppt

上传人:p** 文档编号:464977 上传时间:2023-09-07 格式:PPT 页数:29 大小:872.50KB
下载 相关 举报
数字逻辑邓建021416.ppt_第1页
第1页 / 共29页
数字逻辑邓建021416.ppt_第2页
第2页 / 共29页
数字逻辑邓建021416.ppt_第3页
第3页 / 共29页
数字逻辑邓建021416.ppt_第4页
第4页 / 共29页
数字逻辑邓建021416.ppt_第5页
第5页 / 共29页
数字逻辑邓建021416.ppt_第6页
第6页 / 共29页
数字逻辑邓建021416.ppt_第7页
第7页 / 共29页
数字逻辑邓建021416.ppt_第8页
第8页 / 共29页
数字逻辑邓建021416.ppt_第9页
第9页 / 共29页
数字逻辑邓建021416.ppt_第10页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数字逻辑邓建021416.ppt》由会员分享,可在线阅读,更多相关《数字逻辑邓建021416.ppt(29页珍藏版)》请在第壹文秘上搜索。

1、1 1 1 1Hamming distance between x and y is count of positions where x-bit differs from y-bitAlso equals link count in shortest path from x to yn-cubes and Distancen-cubes and Distance0-cube1-cube2-cube01100011013-cube1100101110111000001010014-cube2 2 2 2Gray code is path that visits each vertex exac

2、tly once3-cube1100101110111000001010014-cube3 3 3 3Example:N=3Example:N=3 L=L=000,111 0001111000100011011100114 4奇偶校验码奇偶校验码u在每组数据信息上附加一位奇偶校验位,若在每组数据信息上附加一位奇偶校验位,若采用奇校验方式,则使包括校验码在内的数采用奇校验方式,则使包括校验码在内的数据含有奇数个据含有奇数个“1”;偶校验方式,则使包括;偶校验方式,则使包括校验码在内的数据含有偶数个校验码在内的数据含有偶数个“1”。u例:字母例:字母“E”的的7位位ASCII码为:码为:u1 0

3、0 0 1 0 1,若在最高位增加一位奇偶校,若在最高位增加一位奇偶校验位,其奇校验编码则为验位,其奇校验编码则为0 1 0 0 0 1 0 1;其;其偶校验编码则为偶校验编码则为1 1 0 0 0 1 0 1。5 5工作原理工作原理 奇偶检验码的工作原理如下图所示。奇偶检验码的工作原理如下图所示。检检 测测 器器编码器编码器 x x1 1 x x2 2 x x3 3 x x4 4 1 11 11 11 11 11 10 00 00 00 01 1F F发发现现错错误误P(P(奇奇)发送端发送端 接收端接收端 6 6特点特点:(1)(1)编码简单、容易实现编码简单、容易实现 ;(2)(2)奇偶

4、检验码只有检错能力,没有纠错能力奇偶检验码只有检错能力,没有纠错能力 ;(3)(3)只能发现单错,不能发现双错只能发现单错,不能发现双错 。7 7 7 7Code space contains 2N possible N-bit code words:1010”A”HD=1HD=1HD=1HD=11110”E”1011”B”1000”8”0010”2”1-bit error in“A”Error not correctable.Reason:No redundancy.Hammings idea:Increase HD between valid code words.N=4CodeSymbo

5、l000000001100102001130100401015011060111710008100191010A1011B1100C1101D1110E1111F8 8 8 81010010”A”1-bit error in“A”shortest distancedecoding eliminateserrorHD=2HD=10010101”2”1000111”8”1011001”B”1110100”E”HD=3HD=3HD=3HD=40010010”?”HD=3HD=4HD=40011110”3”9 9 9 9Example:correct one bit errors or detect

6、two-bit errorsError-correcting codesminimum distance between code words 11010101015 14 13 12 11 10 9 8 7 6 5 4 3 2 1Group 8Group 1Group 2Group 4(15,1115,11)汉明码)汉明码11 11位信息位,位信息位,4 4位校验位位校验位分组分组151111141110131101121100111011101010910018100070111601105010140100300112001010001100001000010000111 11 11 1

7、1Note:Single bit error corrupts one or more parity groupsTwo-bit error in locations x,y corrupts at least one parity groupThree-bit error(i.e.1,4,5)goes undetected3=2(1)+0+1=2(0)+2+1=can correct 1-bit errors or detect errors of size 1 or 2.12121212Code information packets to maintain even parity in

8、groupse.g.(n=7)packet is 1011=positions 7,6,5,37 6 5 4 3 2 11 0 1 x 1 x xConsult group memberships to compute check bitscheckinformation1 3,5,7=bit 1 is 1 2 3,6,7=bit 2 is 04 5,6,7=bit 4 is 0Code word is 1010101(7,47,4)汉明码)汉明码4 4位信息位,位信息位,3 3位校验位位校验位13131313Traditional to permute check bits to far r

9、ightUsed in memory protection schemes14141414(1212,8 8)Hamming CodeHamming Code10101001Data bits001?1?Codeword1010123456789101112Bit position 1:0?1 0 1 1 10Bit position 1Bit position 2?1 0 1 0 1Bit position 2:11101515Hamming Code(2)Hamming Code(2)00100111Codeword1010Assume error in bit 9Recompute th

10、e check bits at the receiver.Bit 1=1(0,error)Bit 2=1(=1,no error)Bit 4=1(=1,no error)Bit 8=1(0,error)Error is in bit position=1+8=9 flip it(correction).12345678910111201616CRCCRC校验码校验码(Cyclic Redundancy Check)CRC校验是用一个固定数去除信息码得出余校验是用一个固定数去除信息码得出余数,将此余数附加在原信息之后,成为数,将此余数附加在原信息之后,成为CRC字符。字符。接收方用同样的数去除含

11、有接收方用同样的数去除含有CRC字符的信息,字符的信息,若接收无错误,则结果为若接收无错误,则结果为0。1717例:已知被传送的信息例:已知被传送的信息C(X)=1001,生成多项式,生成多项式G(X)=1011,求,求C(X)的的CRC码。码。解:解:G(X)=1011,4位位,则则 r=4-1=3C(X)左移左移r=3位:位:C(X)2r=1001 23=1001000再用模再用模2除法将除法将C(X)2r除以除以G(X)余数表达式余数表达式R(X)=110 C(X)2r+R(X)=1001110 即即CRC码为码为1001110CRCCRC校验码校验码10111 0 1 01 0 0 1

12、 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 018181818Two-Dimensional ParityTwo-Dimensional ParityUse 1-dimensional parityAdd one bit to a 7-bit code to ensure an even/odd number of 1sAdd 2nd dimensionAdd an extra byte to frameBits are set to ensure even/odd number of 1s in that position across all bytes in f

13、rameCommentsCatches all 1-,2-and 3-bit errors10111011110110Parity BitsParity Byte010100111010011011110000111001101001011111Data191919191 0 0 1 0 00 1 0 0 0 11 0 0 1 0 01 1 0 1 1 01 0 0 1 1 1 Bottom row consists of check bit for each column Last column consists of check bits for each rowTwo-dimension

14、al parity check code202020201 0 0 1 0 00 0 0 0 0 11 0 0 1 0 01 1 0 1 1 01 0 0 1 1 1 1 0 0 1 0 00 0 0 0 0 11 0 0 1 0 01 0 0 1 1 01 0 0 1 1 1 1 0 0 1 0 00 0 0 1 0 11 0 0 1 0 01 0 0 1 1 01 0 0 1 1 1 1 0 0 1 0 00 0 0 1 0 11 0 0 1 0 01 0 0 0 1 01 0 0 1 1 1 Two errorsOne errorThree errorsFour errorsArrows

15、 indicate failed check bits21212121Two-dimensional codes(product codes)min distance is product ofrow and column distancesfor simple parity on each(below)min distance is 42222题题2-462-46XXX23232323Checksum codesmod-256 sum of info bytes becomes checksum bytemod-255 sum used in IP packets http:/en.wiki

16、pedia.org/wiki/IPv4_header_checksumm-hot codes(m out of n codes)each valid codes has m ones in a frame of n bitsmin distance is 2detect all unidirectional errorsbit flips are all 0 to 1 or 1 to 02424Error Detection vs.Error CorrectionError Detection vs.Error CorrectionDetectionPro:Overhead only on messages with errorsCon:Cost in bandwidth and latency for retransmissionsCorrectionPro:Quick recoveryCon:Overhead on all messagesWhat should we use?Correction if retransmission is too expensiveCorrecti

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 高等教育 > 大学课件

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!