Error Correcting Codes

Modern computer memory makes use of a Single Error Correction, Double Error Detection (SECDEC) code. For this assignment, you will implement a form of SECDED for 16-bit words. For each 16-bit word, you will need to store 5 more check bits for the single error correction part of the code. In addition, you will need a parity bit for the second error detection. This parity bit will check both the data bits and the 5 check bits. First, you will need to develop the equations for the five check bits in the same manner as we did in class for the 8-bit words. Next, you will need to determine what to do for each of the possible check-bit/parity bit outcomes. They are: • stored_parity == computed_parity and stored_check == computed_check: obviously there are no errors in this case. • stored_parity != computed_parity and stored_check == computed_check. • stored_parity == computed_parity and stored_check != computed_check. • stored_parity != computed_parity and stored_check != computed_check. Each of these cases will require a different action on your part. After you have worked all of the details out by hand, you will need to implement it (I strongly suggest that you write a pseudo-code implementation first). I have constructed a system in which you will develop your code. In the directory ~mbailey/320/secded you will find several files: mem.o (object code that implements an error-prone memory and exercises your code), secded.cc (a file in which you can place your code), a makefile to build the system and matching header files mem.h and secded.h for the C++ files. To implement your algorithm, you will need an error-prone memory (a memory that will spontaneously experience 1- and 2-bit errors) to store 22-bit words. I have provided the following interface, in mem.o, for such a memory: void store (unsigned long address, unsigned long data); unsigned long load (unsigned long address); store takes an address and an unsigned long (32-bits) of data. However, it will clear the top 10 bits of the data (forcing you to store all of your information in the low 22 bits of the word). load takes an address and returns an unsigned long whose low-order 22 bits contain the data that was stored at the address (possibly with some errors). In secded.cc, you will find skeleton implementations of secded_load, and secded_store. These two functions have the following C++ signatures: bool secded_load (unsigned long address, unsigned short& data); void secded_store (unsigned long address, unsigned short data); Error Correcting Codes secded_store takes an address (unsigned long), and 16 data bits (unsigned short). It computes the check bits and parity bit and stores all 22 bits in the computer’s memory using the function store. secded_load takes an address and a reference to an unsigned short. This function should use the function load to retrieve the requested 22 data bits. It will then need to recompute the parity and check-bits to determine if an error has occurred. The resulting data is loaded into the location pointed to by the data pointer. If an error has been detected, but cannot be corrected (two-bit error), secded_load should return false. Otherwise, if the resulting 16-bit data is valid, secded_load should return true. Your secded_store and secded_load functions will be called by an exercising harness (provided by me in mem.o) that will execute loads and stores (using your two functions) for a range of random data values and addresses. The harness will cause 1- and 2-bit errors in the error-prone memory. Your responsibility is to create an interface to the memory that is not susceptible to 1-bit errors and will detect all 2-bit errors. To run the program (after compiling it using make), type: ./mem You will be notified when an error occurs that you do not correct or detect. Common Operations There are a number of bit operators in the C++ language that you will need to use: | (bitwise-OR), & (bitwise-AND), ^ (bitwise-XOR), >> (right-shift), and << (left-shift). Here are several operations that you may wish to use in your code: bits = bits ^ (1 << 13); // Toggle bit 13 (14th bit) bit = (bits >> 10) & 1; // Extract bit 10 (11th bit) bits = bits & 0xffff; // Clear all but the low 16 bits bits = bits | more_bits << 16; // Place more_bits above the low 16 bits // (assuming the high bits are clear) Coding Style and Grading Your solution should demonstrate clean functional decomposition. There are a number of obvious choices for functions. Programs that do not compile will receive no credit (after all, I give you a program that compiles). Since the exercising harness will report errors in your implementation, it should be possible for you to verify that your algorithm is coded perfectly. Therefore, the best programs will not only work perfectly, but will present a clean, nicely documented solution to the problem. You will submit the secded.cc file, so be sure to make no changes to any other files. Submit your file using the course submission procedure.