CSCI 4717 Assignment
Simulation of Error Detection and Correction

Objectives:

This assignment is meant to solidify the lecture material on error detection and correction by asking you to create two functions to simulate an SEC/DED system. The first function will generate the parity bits from the data bits. The second function will receive "stored" data and parity bits and return the data if there is no error, correct the data if there is a single bit error or flag a double bit error if one has occurred.

Team/Individual:

This assignment is to be done as an individual with team support.

Assignment Description:

First, the bad news - I haven't written any code for you for this assignment. The good news is that the implementation isn't that hard. We're simply implementing the 8 data bit/4 parity bit error correction and detection scheme discussed in class.

This week's assignment is based on the discussion of a 4-bit check code (parity bits) used for single error correction on an 8-bit data word. We discussed this in class, and there is a similar discussion in the textbook in section 5.2.

Detailed Instructions:

The textbook begins its discussion with the general block-diagram of the error-correcting code function shown in the figure below. (Source: Stallings, William, Computer Organization & Architecture, 6e, Prentice Hall, New Jersey, Figure 5.7, p. 155.):

First, we need to make the function f. This function is actually used twice, once to calculate the parity bits to store with the data before the data is stored in memory and once to calculate the parity bits to compare with the stored parity bits when data is retrieved from memory. This function should receive as its data the M-bits of data to be stored or retrieved. It should output the K parity bits.

The second function that we will be making will be the Corrector. This function will receive as its input the M-bits of data and the K-bits of parity "retrieved". If the data and parity bits have no errors or if there is a single bit error, the corrector will return the corrected version of the data. (Of course there is no correction required if the data and parity bits have no errors.) Do not worry about the multiple errors case. The data set that you will be sent will contain none of those.

Below you will find the prototypes for these two functions.

    unsigned int generateParityBitsFromData(unsigned int data);
    unsigned int correctData(unsigned int data, unsigned int parity_bits);

Now for the specifics of the error correcting code you will be using. The error checking system for this assignment will be slightly different than that presented in class or the one presented on page 157 of our textbook. The table below presents all of the possible syndrome words and the conditions indicated by each one. Notice that for 8 data bits and 4 check bits there are 13 conditions, i.e., the error-free condition, 8 conditions representing single-bit errors in the data, and 4 conditions representing single-bit errors within the parity bits. This means that there are three patterns of ones and zeros in the syndrome word that will be unused.

Remember that the syndrome word is created using the bitwise XOR of the stored parity bits with the parity bits generated after retrieving the data from memory. The bitwise XOR is going to create a syndrome word that is exactly as long as the parity bits with ones in the positions where the parity bits differ. For example, if parity bits P₀ and P₃ differ between the stored values and the values generated after retrieving the data, then the syndrome word will be 1001₂.

So what would a syndrome word 1001₂ mean? Well, if a single bit error occurred, then it would mean that the bit that was involved in generating parity bits P₀ and P₃ had flipped. The position number is what we use to see which groups the data bits generate parity for. In other words, since no two data or parity bits share the same position number, each one belongs to a unique set of groups.

Looking at our table, the binary digit D₅ is the only bit that belongs to the parity equations for both P₀ and P₃. Therefore, D₅ must be the one that flipped.

Now here is the part that confuses some people. To calculate the parity bits (of which there are 4), simply do an exclusive-OR of the data bits that have a 1 in the binary position number corresponding to that particular bit. For example, P₃ has a single bit in it, the most significant bit (MSB). Therefore, every data bit that has a 1 in the MSB of its binary position number should be XOR'd to create the MSB (P₃) of the parity. This gives us an equation for P₃ (note that ^ represents XOR in my equation):

Doing the same thing for P₂ would give us:

I'll let you do the rest on your own. Note that the XOR is really just a parity check. If there are an odd number of ones, the result is a 1 and if there are an even number of ones, there result is 0.

generateParityBitsFromData() should receive the 8-bit data, generate the 4 parity bits along with the overall parity bit, then return all five parity bits as an integer with P₀ as the least significant bit and P₁, P₂, and P₃ located in the neighboring three bit positions and the overall parity bit located in the fifth position.

correctData() will receive a 8-bit data in the first passed value (unsigned int data) and the 4 parity bits in the second passed value (unsigned int parity_bits). If no error has occurred, simply return the data untouched. If a single-bit error has occurred, then correct the data and return it. If a double bit error has occurred, return -1.

To check your work, all you should have to do is "store" an 8-bit value with generateParityBitsFromData(). This will return the 5 bits required for SEC/DED. Change one bit in either the data or the parity bits and pass them to correctData(). If it returns the original 8-bit value, then your code works, or at least with that particular piece of data.

Submission Details:

You should submit a single text document to the drop box folder titled, "SEC and DED Functions," by Tuesday, October 9, 2007. The file name should consist of your userid and the string "_sec_ded_functions.txt". For example, if your userid is zabc123, then your file name should be "zabc123_sec_ded_functions.txt." Be sure to include your name inside the file too.