Lessons from History: Human Anatomy, from the Origin to the ...
4
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
- cours - matière potentielle : that herophilus
- cours - matière potentielle : toward the scientific method
- expression écrite
- cours - matière potentielle : the phrenic nerve
- exposé - matière potentielle : data
- cours - matière potentielle : today
- exposé - matière potentielle : polybus
- expression écrite - matière potentielle : a thousand years
- animal spirit
- chalcedon
- herophilus
- anatomy of humans with the publication
- human dissection
- scientific biography
- th century
- humans
- human anatomy
- anatomy
Publié par
Langue
English
Polynomial Arithmetic for CRC Please keep in mind that the polynomial arithmetic here isdifferentfrom normal integer arithmetic, because: Coefficients of the polynomial may be only zero or one Operations are performed using modulo 2. 1.How to represent a binary sequence using polynomial, and how to represent a polynomial using binary sequence? Examples: 7 6 5 4 3 2 1 0 M1= 0010,1101ÙM1+ 1x+ 1x+ 0x+ 1x(x) = 0x+ 0x+ 1x+ 0x 5 3 2 =x +x +x +1 7 6 5 4 3 2 1 0 M2= 1000,0100ÙM2+ 0x+ 1x+ 0x+ 0x+ 0x+ 0x+ 0x(x) = 1x 7 2 =x +x 2.How to subtract (or add) two polynomials? Answer: Represent the polynomials using binary sequences Perform bitwise XOR between the two sequences Convert the XOR result back to polynomial Examples: M1(x) – M2(x)ÙM1⊕M2= 0010,1101⊕1000,0100 = 1010,1001 7 53 Ùx +x +1x + 3.How to represent transmission errors using polynomial arithmetic? If a bit isflippedin transmission we get an error. Flipping a bit is equivalent to XOR the bit with 1. We therefore can represent transmission error by XORing an error binary sequence with the original sequence. rd Example: M1= 0010,1101. During transmission the 3bit is flipped (onebit error), and the receiver actually receives R = 0010,1001. Therefore, E = 0000,0100, and R = M1⊕E. If the number of 1’s in E is two, we say we get twobit error in our transmission. Remember that adding two polynomials is equivalent to XORing their binary sequence representations. Therefore another way to represent transmission error is to use polynomial addition.
2 53 22 53 Example: R = M1⊕EÙM1+ x+ 1+ x+ 1) + (x ) = x(x) + (x ) = (x+ xÙR 4.How to do polynomial multiplication? Answer: multiplying two polynomials is similar to normal polynomial multiplication with “addition” defined above (XOR). Example from lecture slides: 3 24 2 M = x+ x+ 1, N = x+ x+ x. M×N = 1101ÅM 10110ÅN 0000 1101 1101 0000 ⊕ 1101 11111110 7 6 5 4 3 2 = x+ x+ x+ x+ x+ x+ x 5.How to do polynomial division? Answer: dividing a polynomial with another one of lower degree is similar to normal polynomial division with “subtract” defined above (XOR). Example from lecture slides: P(x) / C(x):
C(x) = P(x) =
3 2 x+x+1 =110110 7 5 4 2 x+x+x+x+x+100101101011 =
1101 10010110101 P(x) 1101 1000 C(x) 1101 1011 1101 1101 1101 Remainder (lower 0101 degree than divisor C(x)) 6.How is CRC related to above? CRC works as follows. The sender appends a few bits (CRC code) to a given binary sequence (a message), so that the polynomial representation of the concatenated binary sequence (transmitted message) is completely divisible by a given polynomial (CRC generator). Say the sender transmits a binary sequence (with CRC codes appended) P, which is completely divisible by C. Say the receiver receives a binary sequence R = P⊕E, where E is the transmission error. Since polynomial addition is defined as binary XOR, we can also represent the received binary sequence as: R(x) = P(x) + E(x), where E(x) is the polynomial representation of the error E. The receiver divides the received binary sequence (received message) R (or R(x)) by the given CRC generator C (or C(x)). Note that the sender and receiver agree on the same CRC generator. If the remainder is nonzero, then the receiver knows there must be errors in the transmission (RP, or E≠0). If the remainder is zero, two scenarios are possible: The received message matches the transmitted message (R = P, or E = 0), or The (polynomial representation of the) error is also completely divisible by the CRC generator. nd The art of CRC design is to choose the CRC generator to rule out the above 2 scenario for typical patterns of transmission errors (i.e., for certain types of E’s). See textbook for more elaboration on: Given a binary sequence (message) and a CRC generator, how to append bits to the end of the message so that the concatenated binary sequence is completely divisible by the CRC generator, and CRC generators that do not completely divide typical transmission errors (E’s).
7.More hints on homework question 4b. You basically have to look for an error binary sequence (with only two 1’s) that is completely divisible by the given CRC polynomial. The minimum length of the error sequence limits the largest value ofn. You can try to multiply the given CRC polynomial with another polynomial (of your choice) to see how you can get a product with only two 1’s. This way the product polynomial will be completely divisible by the CRC polynomial. In your exploration you might figure out the minimum length of the product polynomial.
