This assignment is 3 weeks late now because, even after speaking in person with my professor, paying an online tutor $40+ dollars to help me, posting on StackExchange, and talking both in person and via email with a Teacher's Aide (TA) (who I just emailed two additional times), the wording on this is still so utterly and completely vague and cryptic to me. We learned about CRC's in class for maybe like 10 minutes, and were never tested on it or reviewed it ever again. And I can't find information online that speaks of CRC checksum generation or errors in terms of individual bits/bytes, like I'm dealing with here.

Here's the assignment:

a) Write a program that generates an 8-bit CRC checksum for a data stream. An example of this program follows, in pseudocode. This same program may be used to check correct reception of the data stream. The simplest data stream for which this may be used is two bytes; simulate at least 5 different 2-byte data streams both with and without errors and log the results. Particularly interesting are error data streams which differ by only 1 bit from the correct data.

b) Also, simulate at least one 32-byte data stream with at least one error and log the results.

So, 2 questions:
1. How do I "check [for] correct reception of the data stream"? What does that mean? What would incorrect reception of the data stream even look like?

2. How do I create errors in a 2-byte data stream? By changing bits? Then how do you know if there's errors in it at that point? What do you compare? The generated CRC checksum after changing the bits vs. the generated CRC checksum before changing the bits?

Could someone please formulate a sample output that my C++ program should output?

 

How do I "check [for] correct reception of the data stream"? What does that mean?

Normally the CRC checksum is transmitted along with the data stream so the receiver can generate a CRC checksum on the received data. If the two CRC checksums match, then it is assumed that the transmitted data was received without error.

 

Normally the CRC checksum is transmitted along with the data stream so the receiver can generate a CRC checksum on the received data. If the two CRC checksums match, then it is assumed that the transmitted data was received without error.

Ahhh, yes. So it's as I thought:
1. Generate a CRC checksum (a.k.a The "transmitter's" checksum) from a 2-byte data stream.
2. Modify some bits in the original 2-byte data stream to generate data-transfer "errors"
3. Generate a NEW CRC checksum (a.k.a The "receiver's" checksum) from the erroneous 2-byte data stream
4. Compare the 2 CRC checksums. If the receiver's checksum is different than the original transmitter's checksum, then there was an error in the data reception

 

Ahhh, yes. So it's as I thought:
1. Generate a CRC checksum (a.k.a The "transmitter's" checksum) from a 2-byte data stream.
2. Modify some bits in the original 2-byte data stream to generate data-transfer "errors"
3. Generate a NEW CRC checksum (a.k.a The "receiver's" checksum) from the erroneous 2-byte data stream
4. Compare the 2 CRC checksums. If the receiver's checksum is different than the original transmitter's checksum, then there was an error in the data reception

Yes, that's the idea.

One thing you might do is examine how the CRC checksum is calculated and see if you can't create an error that the receiver fails to detect.

Of particular interest is the fewest number of bit errors that have to exist for this to be possible. That is the error-detecting strength of the checksum algorithm.

 

Yes, that's the idea.

One thing you might do is examine how the CRC checksum is calculated and see if you can't create an error that the receiver fails to detect.

Of particular interest is the fewest number of bit errors that have to exist for this to be possible. That is the error-detecting strength of the checksum algorithm.

Ok, thanks. I finished, but I can't get my program to NOT detect errors. My assignment says: "Particularly interesting are error data streams which differ by only 1 bit from the correct data." But when I change 1 bit, the CRC checksums are still always different & it detects the error...

Any ideas? Is my code messed up?

This is the CRC encoder we're using to create the checksums:

 

Hi,

The idea is to try to make sure that there is a change in the check sum if there is one bit difference, not to make sure the check sum is the same. That's the whole idea of CRC anyway. IF there is a change in data, that means the data was corrupted and you want to know that. IT would do no good to see the same checksum with different data.

So if you have four bits transmitted:
1001

and your checksum was 0xF1

then if your received checksum was 0xF2 then the data was corrupted as it was being sent.

Most CRC algorithms are created to have very little probability of generating the same code for different data sets, and most are designed so that even a 1 bit change causes a huge change in the checksum code. So if 1001 generates code 0xF1 then 1000 would probably generate 0x53 or something like that which is very different than 0xF1.

 

It far more involved than just whether or not the checksum changes when the data changes or whether the change in the checksum is "huge" or not.

In order for the error to be detected, the received checksum must not match the received data.

Remember, the receiver does not know what the "correct" checksum is -- it only knows what it received. Also keep in mind that, as far as errors are concerned, a bit in the checksum is just as likely to get corrupted as a bit in the data.

Another thing to keep in mind is that if the data has more bits than the checksum, then the pigeon hole principle guarantees that multiple data values WILL result in the same checksum value, rendering errors that transform one such data value into another undetectable.

If all of the errors occur in the checksum and none in the data, then these errors will be detected. But that's about as far as you can go with a blanket statement.

If all of the errors occur in the data and none in the checksum, then there is a minimum number of bit errors required to transform the data into a data value having the same checksum. All errors involving fewer than this number of errors will be detected.

If errors occur in both the data and the checksum, then there is also a minimum number of bit errors needed to make the checksum of the corrupted data match the corrupted checksum. This minimum number is no greater than the errors in the data alone (since that is a special case) and is usually smaller.

 

Hi,

Yes there's also the start code which we did not talk about either, or the polynomial. But the main point is that if a different CRC (not really a simple checksum) is generated than received, it is assumed that the data is corrupted. It's too bad if the CRC code itself is bad