11EECS 150 - Components and Design Techniques for Digital SystemsLec 26 – CRCs, LFSRs(and a little power)David CullerElectrical Engineering and Computer SciencesUniversity of California, Berkeleyhttp://www.eecs.berkeley.edu/~cullerhttp://www-inst.eecs.berkeley.edu/~cs1502Review• Concept of error coding– Add a few extra bits (enlarges the space of values) that carry information about all the bits– Detect: Simple function to check of entire data+check received correctly» Small subset of the space of possible values– Correct: Algorithm for locating nearest valid symbol• Hamming codes– Selective use of parity functions– Distance + # bit flips– Parity: XOR of the bits => single error detection– SECDED» databits+p+1 < 2p3Outline• Introduce LFSR as fancy counter• Practice of Cyclic Redundancy Checks– Burst errors in networks, disks, etc.• Theory of LFSRs• Power4Linear Feedback Shift Registers (LFSRs)• These are n-bit counters exhibiting pseudo-random behavior.• Built from simple shift-registers with a small number of xorgates.• Used for:– random number generation– counters– error checking and correction• Advantages:– very little hardware– high speed operation• Example 4-bit LFSR:Q DQ1Q DQ2Q DQ3Q DQ4CLK54-bit LFSR• Circuit counts through 24-1 different non-zero bit patterns.• Left most bit determines shiftl or more complex operation• Can build a similar circuit with any number of FFs, may need more xorgates.• In general, with n flip-flops, 2n-1different non-zero bit patterns. • (Intuitively, this is a counter that wraps around many times and in a strange way.) 0 0 0 1 0xor 0 0 0 0 0 0 0 0 1 0 0 xor 0 0 0 0 0 0 0 1 0 0 0 xor 0 0 0 0 0 0 1 0 0 0 0 xor 1 0 0 1 1 0 0 0 1 1 0 xor 0 0 0 0 0 0 0 1 1 0 0 xor 0 0 0 0 0 0 1 1 0 0 0 xor 1 0 0 1 1 0 1 0 1 1Q4 Q3 Q2 Q10001001001001000001101101100101101011010011111101111110110010001Q DQ1Q DQ2Q DQ3Q DQ4CLK6Applications of LFSRs• Performance:– In general, xors are only ever 2-input and never connect in series.– Therefore the minimum clock period for these circuits is:T > T2-input-xor+ clock overhead– Very little latency, and independent of n!• This can be used as a fast counter, if the particular sequence of count values is not important. – Example: micro-code micro-pc• Can be used as a random number generator. – Sequence is a pseudo-random sequence:» numbers appear in a random sequence» repeats every 2n-1 patterns– Random numbers useful in:» computer graphics» cryptography» automatic testing• Used for error detection and correction» CRC (cyclic redundancy codes)» ethernet uses them27Concept: Redundant Check• Send a message M and a “check” word C• Simple function on <M,C> to determine if both received correctly (with high probability)• Example: XOR all the bytes in M and append the “checksum” byte, C, at the end– Receiver XORs <M,C> – What should result be?– What errors are caught?***bit i is XOR of ith bit of each byte8Example: TCP ChecksumApplication(HTTP,FTP, DNS)Transport(TCP, UDP)Network(IP)Data Link(Ethernet, 802.11b)Physical12347TCP Packet Format• TCP Checksum a 16-bit checksum, consisting of the one's complement of the one's complement sum of the contents of the TCP segment header and data, is computed by a sender, and included in a segment transmission. (note end-around carry)• Summing all the words, including the checksum word, should yield zero9Example: Ethernet CRC-32Application(HTTP,FTP, DNS)Transport(TCP, UDP)Network(IP)Data Link(Ethernet, 802.11b)Physical1234710CRC concept • I have a msg polynomial M(x) of degree m• We both have a generator poly G(x) of degree m• Let r(x) = remainder of M(x) xn/ G(x)– M(x) xn= G(x)p(x) + r(x)– r(x) is of degree n• What is (M(x) xn– r(x)) / G(x) ?• So I send you M(x) xn– r(x) – m+n degree polynomial– You divide by G(x) to check– M(x) is just the m most signficant coefficients, r(x) the lower m• n-bit Message is viewed as coefficients of n-degree polynomial over binary numbersn bits of zero at the endtack on n bits of remainderInstead of the zeros11Announcements• Reading– XILINX IEEE 802.3 Cyclic Redundancy Check (pages 1-3)– ftp://ftp.rocksoft.com/papers/crc_v3.txt• Final on 12/15• What’s Going on in EECS?– Towards simulation of a Digital Human– Yelick: Simulation of the Human Heart Using the Immersed Boundary Method on Parallel Machines12Galois Fields - the theory behind LFSRs• LFSR circuits performs multiplication on a field.• A field is defined as a set with the following:– two operations defined on it:» “addition” and “multiplication”– closed under these operations – associative and distributive laws hold– additive and multiplicative identity elements– additive inverse for every element– multiplicative inverse for every non-zero element• Example fields:– set of rational numbers– set of real numbers– set of integers is not a field (why?)• Finite fields are called Galois fields. • Example: – Binary numbers 0,1 with XOR as “addition” and AND as “multiplication”.– Called GF(2).– 0+1 = 1– 1+1 = 0– 0-1 = ?– 1-1 = ?313Galois Fields - The theory behind LFSRs• Consider polynomials whose coefficients come from GF(2).• Each term of the form xnis either present or absent.• Examples: 0, 1, x, x2, and x7+ x6 + 1 = 1·x7+ 1· x6 + 0 · x5 + 0 · x4 + 0 · x3 + 0 · x2 + 0 · x1 + 1· x0 • With addition and multiplication these form a field:• “Add”: XOR each element individually with no carry:x4+ x3 + + x + 1+ x4 + + x2 + xx3+ x2+ 1 • “Multiply”: multiplying by xnis like shifting to the left.x2+ x + 1××××x + 1x2+ x + 1x3+ x2+ xx3+ 114So what about division (mod)x4+ x2x= x3+ x with remainder 0 x4+ x2 + 1X + 1= x3+ x2with remainder 1 x4+ 0x3+ x2 + 0x + 1X + 1x3x4+ x3x3+ x2+ x2x3+ x20x2+ 0x+ 0x0x + 1+ 0Remainder 115Polynomial division• When MSB is zero, just shift left, bringing in next bit• When MSB is 1, XOR with divisor and shiftl1 0 1 1 0 0 1 0 0 0 01 0 0 1 1Q DQ1Q DQ2Q DQ3Q DQ4CLKserial_in0 0 0 0 1 0 0 1 10 0 1 0 110 1 0 1 001 0 1 0 11 0 0 1 110 0 1 0 016CRC encodingQ DQ1Q DQ2Q DQ3Q DQ4CLKserial_in1 0 1 1 0 0 1 0 0 0 00 0 0 00 0 0 1 0 1 1 0 0 1 0 0 0 00 0 1 0 1 1
View Full Document