Error Detection and Correction

The purpose of this assignment is to explore error detection and correction codes which are employed in data transmission, memory checks, and CDs.

Test your program and demonstrate that you have tested it (by handing in a printout of your tests). Do not use any built in functions or code from the web that may exist.

1. Error Detection: Parity

Complete the following functions which check and generate parity:

    //This function checks the given value for even parity and returns true
    // if it does (and false otherwise).
    static boolean isEvenParity ( int value ) {
        .
        .
        .
    }

    //This function checks the given value for odd parity and returns true
    // if it does (and false otherwise).
    static boolean isOddParity ( int value ) {
        .
        .
        .
    }

    //Given an integer value ranging from 0x00000000 to at most 0x0000FFFF,
    // this function returns a value with odd parity using the most
    // significant bit as the parity bit.
    static int oddParityMSB ( int value ) {
        .
        .
        .
    }

    //Given an integer value ranging from 0x00000000 to at most 0x0000FFFF,
    // this function returns a value with even parity by adding a new, least
    // significant bit as the parity bit.
    static int evenParityLSB ( int value ) {
        .
        .
        .
    }

2. Error Correction: Hamming Code

Complete the following table by entering the missing entries (i.e., print it out, fill it out, and hand it in). Also, explain why you made the entry that you did. Note that bi indicates a check bit and bj indicates a data bit. Adopt the convention that b1 is the most significant bit and b7 is the least.

base 2 code word base 10 base 16
  b1     b2     b3     b4     b5     b6     b7       code word       data       code word       data  
0 0 0 0 0 0 0
1 1 0 1 0 0 1 105
0 1 0 1 0 1 0
1 0 0 0 0 1 1
1 0 0 1 1 0 0
0 1 0 0 1 0 1
1 1 0 0 1 1 0
0 0 0 1 1 1 1
1 1 1 0 0 0 0
0 1 1 0 0 1 9
1 1 1 0 1 0
0 1 0 0 1 1
0 1 1 1 0 0
1 0 1 0 0 1
0 0 1 0 1 0
1 1 1 1 1 1

Using the table above, write a program that implements this Hamming code. You will need to code the following functions:

    //This function returns the Hamming distance between the code words A and B.
    static int HammingDistance ( final int A, final int B ) {
        .
        .
        .
    }

    //Given a set of code words, this function returns the minimum Hamming
    // distance over all (different) pairs of elements.
    static int minHammingDistance ( final int set[] ) {
        .
        .
        .
    }

    //Given a set of code words and a possibly corrupted code word A, this
    // function returns the data (corresponding to the code word).
    static int bestMatch ( final int A, final int set[] ) {
        .
        .
        .
    }

How many single bit errors can be detected? How many single bit errors can be corrected? Justify your answers.