0
\$\begingroup\$

This is unconventional, based on what I've seen, but I can't get a hold of my professor's aides to clarify this assignment. I hope this is still ok to post here.

I would greatly appreciate some help from you folks in interpreting the instructions for a programming assignment I've been given, related to parity bits and CRC error checking. I would like help with the logic behind the instructions, and some guidance on what the processes that are named in the instructions are meant to do. Once I understand the logic, I (at least hope) plan to be able to take care of the actual programming portion myself from there.

I feel the instructions are not very concise (though they may be just fine to those familiar with the material). Phrases I am especially perplexed by will be in bold+italics:

Error Detection and Coding: Parity, CRC & FEC

Part 1:

a) Write a program (in any language, such as C, C++, Java, Javascript, or Python) that generates a parity bit (even or odd - you choose) for each byte of data and verify its correct operation.

b) Write another program to detect correct data based on the parity you have defined. Then use the program to generate a byte of data along with the parity bit (9-bits total), and observe what happens when there are 0, 1, 2, or 3 bits in error in a given byte. Include a screenshot of the results (command line or other) and discuss the probability of an undetected error occurring.

Part 2:

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. Include a screenshot of the results and discuss the probability of an undetected error occurring.

CRC Program Pseudocode

Initialize counter and data stream
Loop for each bit in data stream
Define next states for each bit
Next Bit 1 = next bit of Data In
Next Bit 2 = Present Bit 1
Next Bit 3 = Present Bit 2 XOR
present Bit 8
Next Bit 4 = Present Bit 3 XOR
present Bit 8
Next Bit 5 = Present Bit 4 XOR
present Bit 8
Next Bit 6 = Present Bit 5
Next Bit 7 = Present Bit 6
Next Bit 8 = Present Bit 7
Move next states into present states
Present Bit 1 = Next Bit 1
Present Bit 2 = Next Bit 2
Present Bit 3 = Next Bit 3
Present Bit 4 = Next Bit 4
Present Bit 5 = Next Bit 5
Present Bit 6 = Next Bit 6
Present Bit 7 = Next Bit 7
Present Bit 8 = Next Bit 8
Output CRC encoder byte to screen
End loop
Output final CRC checksum byte

Bold+Italics Portions:

1a)

  • I'm creating a function through which I manually type out a byte, in order to test my program. Correct?

  • "even or odd - you choose" - I know a byte is a string of 8 bits, each of which is either a 1 or a 0. I know a parity bit is a "9th bit" tacked at the end of the bit sequence. I think "even or odd - you choose" means that I should decide whether a 1 parity bit indicates that there is an even number of 1's in the byte or that there is an odd number of 1's in the byte. Correct?

1b)

  • I'm now creating a byte generator that - based on whether there are an even or odd # of 1's in the generated byte - tacks on a parity bit, being a 1 or a 0. (Let's just decide now that an even number of 1's means the parity bit will be 1, and vice versa). Is this correct?

  • "detect correct data based on the parity" - So...Just confirm that I have the correct number of 1's in my byte, based on the parity bit's value? Isn't that the same thing as "verify[ing] its correct operation" from step a)? What bytes are we using to do this step? We haven't created our byte generator yet. We were already asked to "verify [the parity bit's] correct operation" in step a), so is this step redundant?

  • "what happens when there are 0, 1, 2, or 3 bits in error" - Wait. So am I to intentionally create a byte generator that contains errors in some of the generated bytes? How would I even know that a generated byte has an error in it? I have no "base case" or "correct version of the byte" to compare each byte to. Who's to say that there's an error in it?

  • probability of an undetected error - We're dealing with 1 byte, or 8 bits. I found this page that states the probability of an undetected error in 8-bit systems is \$P_{ue} = 1 - (1 - q)^8\$. Is this correct, standard equation that's used? Would the probability in a 16-bit system just be \$P_{ue} = 1 - (1 - q)^{16}\$?

2a)

8-bit CRC checksum - So I need to write a function that generates a sequence of XOR gates at random positions in the 8-bit sequence? Based on the image below?:

enter image description here

I assume there can't be 0 XOR gates and there can't be XOR gates at all 8 bits. Are there any other limitations to generating a CRC checksum? So if the 8-bit Encoder looked like above, would the checksum be 01110000? What do I do with the checksum?

2-byte data streams both with and without errors - 2 bytes is 16 bits. Are we using the checksum generator in this step? Am I supposed to program the checksum generator to occasionally make mistakes? In this case, an "error" would be a byte that passes through the CRC encoder and ends up with a 1 where there should be a 0 or vice versa. Correct? I'm supposed to program it so the XOR gates/CRC encoder don't always do their job?

\$\endgroup\$
  • \$\begingroup\$ I hope your teacher also lets you know that parity checks is a horrible, unprofessional way of looking for any form of errors and that you should never use such crap in real-world applications. Particularly not as part of UART communication. \$\endgroup\$ – Lundin Nov 3 '17 at 12:04
2
\$\begingroup\$

To go through in order, and not answer specifically for homework purposes.

1a I wouldn't manually type out a byte stream, but it's easy to write a script to generate a nice selection of known values. Regards a parity bit, yes, you are correct.

1b You've started right. It's not redundant, as 1a was to write a script that generated a parity bit, and 1b is to write a script that checks the parity bit. You need to make a known byte stream that is correct, and then you can randomly flip some bits and see if the parity checker indicates a fault. Obviously you need to track if you flipped a bit. You can do the question parts.

2 You need to read a little bit more about checksums, but again you're on the correct lines. The errors in the byte stream refer to corrupted transfers, not errors in the CRC system.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.