DOC PREVIEW
Berkeley COMPSCI 150 - CRCs, LFSRs

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 150 - CRCs, LFSRs

Documents in this Course
Lab 2

Lab 2

9 pages

Debugging

Debugging

28 pages

Lab 1

Lab 1

15 pages

Memory

Memory

13 pages

Lecture 7

Lecture 7

11 pages

SPDIF

SPDIF

18 pages

Memory

Memory

27 pages

Exam III

Exam III

15 pages

Quiz

Quiz

6 pages

Problem

Problem

3 pages

Memory

Memory

26 pages

Lab 1

Lab 1

9 pages

Memory

Memory

5 pages

Load more
Download CRCs, LFSRs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CRCs, LFSRs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CRCs, LFSRs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?