數(shù)字邏輯02-14-16ppt課件

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 2Gray code is path that visits each vertex exactly once

2、3-cube1100101110111000001010014-cube3 3Example: N=3Example: N=3 L = 000,111 L = 000,1110001111000100011011100114奇偶校驗(yàn)碼奇偶校驗(yàn)碼u在每組數(shù)據(jù)信息上附加一位奇偶校驗(yàn)位，假在每組數(shù)據(jù)信息上附加一位奇偶校驗(yàn)位，假設(shè)采用奇校驗(yàn)方式，那么使包括校驗(yàn)碼在內(nèi)設(shè)采用奇校驗(yàn)方式，那么使包括校驗(yàn)碼在內(nèi)的數(shù)據(jù)含有奇數(shù)個(gè)的數(shù)據(jù)含有奇數(shù)個(gè)“1；偶校驗(yàn)方式，那么；偶校驗(yàn)方式，那么使包括校驗(yàn)碼在內(nèi)的數(shù)據(jù)含有偶數(shù)個(gè)使包括校驗(yàn)碼在內(nèi)的數(shù)據(jù)含有偶數(shù)個(gè)“1。u例：字母例：字母“E的的7位位ASCII碼為：碼為：u1

3、0 0 0 1 0 1，假設(shè)在最高位添加一位奇偶，假設(shè)在最高位添加一位奇偶校驗(yàn)位，其奇校驗(yàn)編碼那么為校驗(yàn)位，其奇校驗(yàn)編碼那么為0 1 0 0 0 1 0 1；其偶校驗(yàn)編碼那么為其偶校驗(yàn)編碼那么為1 1 0 0 0 1 0 1。5任務(wù)原理任務(wù)原理 奇偶檢驗(yàn)碼的任務(wù)原理如以下圖所示。 檢檢 測(cè)測(cè) 器器編碼器編碼器 x1 x1 x2 x2 x3 x3 x4 x4 1 11 11 11 11 11 10 00 00 00 01 1F F發(fā)發(fā)現(xiàn)現(xiàn)錯(cuò)錯(cuò)誤誤P(P(奇奇) ) 發(fā)送端發(fā)送端 接納端接納端 6特點(diǎn)特點(diǎn): : (1) (1) 編碼簡(jiǎn)單、容易實(shí)現(xiàn)編碼簡(jiǎn)單、容易實(shí)現(xiàn) ； (2) (2) 奇偶檢驗(yàn)碼只

4、需檢錯(cuò)才干，沒(méi)有糾錯(cuò)才干奇偶檢驗(yàn)碼只需檢錯(cuò)才干，沒(méi)有糾錯(cuò)才干 ； (3) (3) 只能發(fā)現(xiàn)單錯(cuò)，不能發(fā)現(xiàn)雙錯(cuò)只能發(fā)現(xiàn)單錯(cuò)，不能發(fā)現(xiàn)雙錯(cuò) 。 7 7Code space contains 2N possible N-bit code words:1010AHD = 1HD = 1HD = 1HD = 11110E1011B10008001021-bit error in “AError not correctable. Reason: No redundancy.Hammings idea: Increase HD between valid code words.N = 4CodeSymbol

5、000000001100102001130100401015011060111710008100191010A1011B1100C1101D1110E1111F8 81010010 A1-bit error in “Ashortest distancedecoding eliminateserrorHD = 2HD = 10010101 21000111 81011001 B1110100 EHD = 3HD = 3HD = 3HD = 40010010 ?HD = 3HD = 4HD = 40011110 39 9Example: correct one bit errors or dete

6、ct two-bit errorsError-correcting codesminimum distance between code words 1101015 14 13 12 11 10 9 8 7 6 5 4 3 2 1Group 8Group 1Group 2Group 415,1115,11漢明碼漢明碼11 11位信息位，位信息位，4 4位校驗(yàn)位位校驗(yàn)位分組分組151111141110131101121100111011101010910018100070111601105010140100300112001010001100001000010000111 11Note:Sing

7、le 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.1212Code information packets to maintain even pari

8、ty 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 10101017,47,4漢明碼漢明碼4 4位信息位，位信息位，3 3位校驗(yàn)位位校驗(yàn)位1313Traditional to permute che

9、ck bits to far rightUsed in memory protection schemes14141212，8 8Hamming CodeHamming Code10101001Data bits001?1?Codeword1010123456789101112Bit position 1: 0?1 0 1 1 10Bit position 1Bit position 2? 1 0 1 0 1Bit position 2: 111015Hamming Code (2)Hamming Code (2)00100111Codeword1010Assume error in bit

10、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).123456789101112016CRCCRC校驗(yàn)碼校驗(yàn)碼(Cyclic Redundancy Check)CRC校驗(yàn)是用一個(gè)固定數(shù)去除信息碼得出余校驗(yàn)是用一個(gè)固定數(shù)去除信息碼得出余數(shù)，將此余數(shù)附加在原信息之后

11、，成為數(shù)，將此余數(shù)附加在原信息之后，成為CRC字符。字符。接納方用同樣的數(shù)去除含有接納方用同樣的數(shù)去除含有CRC字符的信息，字符的信息，假設(shè)接納無(wú)錯(cuò)誤，那么結(jié)果為假設(shè)接納無(wú)錯(cuò)誤，那么結(jié)果為0。17例：知被傳送的信息例：知被傳送的信息C(X) =1001，生成多項(xiàng)式，生成多項(xiàng)式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)余數(shù)表達(dá)式余數(shù)表達(dá)式R(X)=110 C(X) 2r + R(X

12、)=1001110 即即CRC碼為碼為1001110CRCCRC校驗(yàn)碼校驗(yàn)碼10111 0 1 01 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 01818Two-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

13、 number of 1s in that position across all bytes in frameCommentsCatches all 1-, 2- and 3-bit errors10111011110110Parity BitsParity Byte010100111010011011110000111001101001011111Data19191 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 colum

14、n consists of check bits for each rowTwo-dimensional parity check code20201 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 Tw

15、o errorsOne errorThree errorsFour errorsArrows indicate failed check bits2121Two-dimensional codes (product codes)min distance is product ofrow and column distancesfor simple parity on each (below)min distance is 422題題2-462-46XXX2323Checksum codesmod-256 sum of info bytes becomes checksum bytemod-25

16、5 sum used in IP packets /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 024Error Detection vs. Error CorrectionError Detection vs. Error Correcti

17、onDetectionPro: 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 expensiveCorrection if probability of errors is high25Data can be transmitted by

18、 either serial transfer or parallel transfer.Serial and Parallel DataComputerModem10110010t0t1t2t3t4t5t6t7ComputerPrinter101100102626Serial data transmission(simple) transmit clock and sync with data (3 lines)(complex) recover clock and/or sync from data line2727Manchester: zero = 0 to 1 transition,