CS118 Homework 4
1. (Cyclic Redundancy Check) Consider the 7-bit generator, G = 10011, and suppose that D has
the value 1010101010. What is the value of R?
2. Consider the previous problem, but suppose that D has the value
(a) 1001010101
(b) 0101101010
(c) 1010100000
3. Slotted ALOHA
(a) Recall that when there are N active nodes, the efficiency of slotted ALOHA is N p(1−p)N−1.
Find the value of p that maximizes this expression.
(b) Using the value of p found in (a), find the efficiency of slotted ALOHA by letting N approach
infinity.
4. Suppose nodes A and B are on the same 10Mbps broadcast channel, and the propagation delay
between the two nodes is 325 bit times. Suppose CSMA/CD and Ethernet packets are used
for this broadcast channel. Suppose node A begins transmitting a frame and, before it finishes,
node B begins transmitting a frame. Can A finish transmitting before it detects that B has
transmitted? Why or why not?
1
