Question

A data stream sent over Ethernet is divided up into frames of up to 1,500 bytes each. Each frame is terminated by a 32-bit checksum calculated using a hashing algorithm called the cyclic redundancy check (CRC).

Show that there must be at least two frames (somewhere, sometime) that have the same CRC checksum.

This is an "essay" question. Write a an argument of a paragraph or so. Imagine you are trying to explain this to another computer science student who is familiar with the concepts but is otherwise unconvinced.

Answer 1

Answer:-

We Know that the size of Ethernet varies from 64 to 1518 bytes. Now, According to the question, The data sent over Ethernet is divided into 1500 bytes for each frame.

Also, each frame is terminated by the 32-bit Checksum. (In checksum method of error detecting method we divide the data into (say)x segments and each segment is of (say)k-bit. )

Now, 2³² -Bit CRC will be having 4,294,967296 unique values. (since, 2³²=4,294,967296 )

Let m= 2³² , and we are trying to send m+1 frames then it is obvious that two or even more(i.e; at least two) frames should be having the same CRC.

Let's Understand the above concept by a simple concept of dice having 6 faces.

Suppose I have to throw dice for seven times and for the six times I got the result as 1,2,3,4,5,6, now when I'll throw the dice for the seventh time I can only be getting the numbers between 1 to 6 that means one of the numbers must have to repeat in the 7^th throw.

Similarly, if we compare our above concept with our problem we can say 32 bit CRS is a dice having 4,294,967296 sides.

Hence, there must be at least 2 frames that are repeated with the same value of CRC checksum.