数字逻辑邓建021416.ppt
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 exactly 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 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)奇偶检验码只有检错能力，没有纠错能力奇偶检验码只有检错能力，没有纠错能力 ；(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=4CodeSymbol000000001100102001130100401015011060111710008100191010A1011B1100C1101D1110E1111F8 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 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 11Note: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 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 rightUsed 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 the 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字符。字符。接收方用同样的数去除含有接收方用同样的数去除含有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 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 frameCommentsCatches 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-dimensional 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 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.wikipedia.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
