transmission. Show that this error is detected at the receiver’s end.
Solution:
Message M (x) = 10011101 = x7+x4+ x3+ x2+ 1
CRC Polynomial C (x) = x3+ 1 = 1001
Multiply the message with x3 since the divisor polynomial is of degree 3.
? T (x) = x3 (x7+x4+ x3+ x2+ 1) = x10+x7+ x6+ x5+x3 ? 10011101000
Divide 10011101000 by 1001 i.e., divide T (x) by C (x)
1000110
---------------------------------------------
1001 | 10011101000 ? Message
| 1001
-----------------
1101
1001
---------
1000
1001
-----------
100 ? Remainder
-----------
Since T (x) minus the remainder would be exactly divisible by C (x), we subtract the remainder from T (x) as shown below:
Note: The minus operation in polynomial arithmetic is the logical XOR operation.
T (x): 10011101000
Remainder: 100
-------------------
10011101100 ? This turns out to be the original message with
------------------- the remainder appended to it.
If the third bit form the left is inverted during transmission, the bit stream would be: 10111101100. Dividing this by 1001 we get:
10101
---------------------------------------------
1001 | 10111101100 ? Message
| 1001
-----------------
1011
1001
---------
1001
1001
------------
0100 ? Remainder
------------
Since the remainder is 100, which is different form 0, the receiver detects the error and can ask for retransmission.
http://www.cis.temple.edu/~latecki/Courses/CIS617-04/Solutions/archana_guptaHW1.pdf
- Cyclic Redundancy Check
Goal
Maximize protection, Minimize extra bits
Idea
Add k bits of redundant data to an n-bit message
N-bit message is represented as a n-degree polynomial with each bit in the message being the corresponding coefficient in the polynomial
Example
Message = 10011010
Polynomial
= 1 ?x7 ? 0 ?x6 ? 0 ?x5 ? 1 ?x4 ? 1 ?x3 ? 0 ?x2 ? 1 ?x ? 0
= x7 ? x4 ? x3 ? x
- Cyclic Redundancy Check
Checked at many layers
? Physical (e.g. modulation)
? Datalink (e.g. cyclic redundancy check)
? Network/Transport (e.g. IP Checksum)
? Application (e.g. MD5 hash)
Today: simple parity, redundancy w/voting, 2
dimensional parity, IP checksum, CRCs
(CRC)
Polynomial code
? Treat packet bits a coefficients of n-bit polynomial
» Message = 10011010
» Polynomial
=1 ?x7 ?0 ?x6 ?0 ?x5 ?1 ?x4 ?1 ?x3 ?0 ?x2 ?1 ?x ?0= 1 ?x7 ?0 ?x6 ?0 ?x5 ?1 ?x4 ?1 ?x3 ?0 ?x2 ?1 ?x ?0
= x7 ?x4 ?x3 ?x
http://cseweb.ucsd.edu/classes/fa09/cse123/123f09_Lec4.pdf
- Computer Networks 2-9: Error Detection
https://www.youtube.com/watch?v=BxCmS7NIDR4
fakecineaste gives fake answer.. what do you think about that division?? hmmm?
ReplyDeleteunakwama bro
ReplyDelete