hamming.c

/*
 * hamming.c
 * Dillon Beliveau
 * CS 121
 * Due 9/16/14
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>

int hamming_distance(uint16_t code1, uint16_t code2) {
    uint16_t difference = code1 ^ code2; //Bitwise XOR
    int distance = 0;
    int i;
    // Loop once for each bit in uint16_t
    for (i = 0; i < sizeof(uint16_t) * 8; i++) {
        // Check rightmost bit to see if it is set

        if (difference % 2 == 1) { // If it's not divisible by 2, rightmost bit must be 1
            distance++;
        }
        // Shift so that next loop we check the next bit
        difference >>= 1;
    }
    return distance;
}

int arr_hamming_distance(uint16_t code[], int code_length) {
    printf("Code length: %i\n", code_length);

    int i,j;
    int minimum = INT_MAX;
    for (i = 0; i < code_length; i++) {
        for (j = 0; j < code_length; j++) {
            // Don't compare the same two codes
            if (i == j) {
                continue;
            }
            printf("Checking code %i against code %i. Distance: ", i + 1, j + 1);
            // Do the comparison

            int distance = hamming_distance(code[i], code[j]);

            printf("%i\n",distance);

            if (distance < minimum) {
                minimum = distance;
                printf("New smallest distance found: %i\n", distance);
            }


        }
    }
    return minimum;
}

int pow_of_two(int num) {
    // Continue dividing by 2 until we can't anymore
    // Special case - 0 is not a power of 2
    while ((num % 2 == 0) && num != 0) {
        num /= 2;
    }
    // If we're left with a 1, then it is a power of 2.
    // Any other number, and it's not.
    return num == 1;
}

// Gets a bit
int getbit(uint16_t num, int bit) {
    // Shift it so the bit we want is in the least significant position, and check if it's 1 or 0 using mod 2
    return (num >> (bit - 1)) % 2 == 1;
    /*return (num >> (codebits - bit)) % 2 == 1;*/
}

uint16_t setbit(uint16_t num, int bit, int val) {
    val = val ? 1 : 0; // Convert val to a 1 or a 0
    int codebits = sizeof(uint16_t) * 8;
    uint16_t insertcode = val << (codebits - bit);

    return num | insertcode;
}

void print_binary(uint16_t num) {
    char binarray[sizeof(uint16_t) * 8 + 1];
    int i;
    // Fill the binarray with correct data
    for(i = 0; i < sizeof(uint16_t) * 8; i++) {
        int bit = getbit(num, i+1);
        binarray[sizeof(uint16_t) * 8 - i - 1] = bit ? '1' : '0';
    }
    binarray[sizeof(uint16_t) * 8] = '\0';

    printf("%s\n", binarray);

    return;
}

int get_parity_bit(uint16_t num, int pbit) {
    // Check pbit, skip pbit.
    if (!pow_of_two(pbit)) {
        printf("Not a parity bit.\n");
    }

    int j = pbit + 1;

    int numchecked = 0, numskipped = 0;
    /*int status = 0; // 0 - checking, 1 - skipping*/
    typedef enum {
        checking,
        skipping
    } status_t;
    status_t status = checking;
    int total = 0;
    do {
        /*printf("On bit %i: value: %i, status: %s\n", j, getbit(num,j), status ? "skipping" : "checking");*/
        if (status == checking) {
            /*printf("Checking bit %i: %i\n", j, getbit(num,j));*/
            total += getbit(num, j);
            /*printf("Running total: %i\n", total);*/

            j++;
            if (j % pbit == 0) {
                status = skipping;
            }
        }
        else {
            j++;
            if (j % pbit == 0) {
                status = checking;
            }
        }
    } while(j <= sizeof(uint16_t) * 8);
    /*printf("Total: %i, i: %i\n", total, i);*/

    /*printf("Parity bit should be: %i ---- Actually: %i\n", total % 2, getbit(num,i));*/

    /*printf("%i % 2 == %i\n", total, getbit(num,i));*/

    return total % 2; // 1 if odd, 0 if even
}

int check_hamming_code(uint16_t num) {
    int i;

    int bitwitherror = 0; // Used to track the bit with the error
    for(i = 1; i <= sizeof(uint16_t) * 8; i++) {
        if (pow_of_two(i)) { // If it's a parity bit...
            printf("!!!!!!!!!!Checking parity bit %i\n", i);

            if (get_parity_bit(num,i) == getbit(num,i)) {
                printf("Parity bit %i OK.\n", i);
            }
            else {
                printf("Parity bit %i detected an error.\n", i);
                bitwitherror += i; // Add i to the list of parity bits that detected an error.
            }
        }
    }
    if (bitwitherror) {
        printf("Bit %i seems to be incorrect. Value: %i Should be: %i\n", bitwitherror, getbit(num, bitwitherror), !getbit(num, bitwitherror));
    }
    return bitwitherror;
}

void print_without_parity_bits(uint16_t num) {
    int i;
    for (i = 1; i <= sizeof(uint16_t) * 8; i++) {
        if (!pow_of_two(i)) {
            // Only print if not a power of 2
            printf("%i", getbit(num, i));
        }
    }
    printf("\n");
}

// Takes an 11 bit codeword (padded with 5 zeroes in the leftmost positions)
// and inserts the parity bits to form the correct codeword
uint16_t insertparity(uint16_t num) {
    uint16_t codeword = 0;

    int i;
    int offset = 0;
    for (i = 1; i <= sizeof(uint16_t) * 8; i++) {
        if (pow_of_two(i)) {
            offset++;
            continue;
        }

        codeword = setbit(codeword,i, getbit(num,i-offset));
    }
    for (i = 1; i <= sizeof(uint16_t) * 8; i++) {
        if (!pow_of_two(i)) {
            continue;
        }
        codeword = setbit(codeword, i, get_parity_bit(codeword, i));
    }
    return codeword;
}

/*c c     c c*/
/*1 1 1 1 1 1 1 1*/
/*8 7 6 5 4 3 2 1*/

int main (int argc, char** argv) {

    uint16_t code[] = {
        0b0011010010111100,
        0b0000011110001111,
        0b0010010110101101,
        0b0001011010011110
    };

    /*int k;*/
    /*for(k = 0; k < 4; k++) {*/
    /*check_hamming_code(code[k]);*/
    /*}*/


    // Part a
    int code_length = sizeof(code) / sizeof(uint16_t);
    printf("Calculated hamming distance: %i\n", arr_hamming_distance(code, code_length));

    // Part b
    // Remove parity bits and display:

    int i;
    int codebits = sizeof(uint16_t) * 8;
    for(i = 0; i < code_length; i++) {
        printf("Code %i with parity bits stripped: 0b",i+1);
        print_without_parity_bits(code[i]);
    }


    // Part c
    uint16_t newcodeword = insertparity(0b11111111111);


    // Rebuild the codeword array with the new codeword
    uint16_t code2[] = {
        code[0],
        code[1],
        code[2],
        code[3],
        newcodeword
    };

    printf("New hamming distance: %i\n", arr_hamming_distance(code2, 5));
}