Signal Processing: Hadamard Matrices

[chris.lloyd]

Hi,
Just to make things obvious, I am a student. I have been learning C given an assignment to code a program similar to that used on the Voyager 9 probe. It uses hadamard matrices to make sure that bits transmitted through space have redundancy and are not lost.

Each line of a n by n Hadamard matrix is different in n/2 ways from each other line. Here a small example.

\left| \begin{array}{ccc}1 & 1 & 1 & 1 \\1 & 0 & 1 & 0 \\1 & 1 & 0 & 0 \\1 & 0 & 0 & 1 \end{array} \right| 00 would be sent as row 1, 01 would be row 2, 10 would be row 3 and 11 would be row 4.

If you can be bothered reading (it is actually quite interesting for general knowledge), here is a better explaination:
http://www.cs.princeton.edu/courses/archive/spring03/cs126/assignments/mariner.html

So far I have have made the program structure and generated the hadamard matrix (a 2D matrix of ints). I am a little confused as to how I should be comparing the matrix to the number. I am working with 5 bit image files. A 1x1 white pixel would be 63 63 63 in represented in binary. How do I take the file pointer, read in binary mode, and convert it to somthing I can compare against each integer row of the matrix?

I have a feeling I should maybe make the matrix unsigned long type, but I don't understand what unsigned actually does.

Also, the "advanced level implementation" asks for the program to work with any bit image file (i.e. a 16 bit image file). Apparently this can be done with bitwise operators, but I don't understand them very well either. I'm fairly experienced with other languages but this is my first C program so all the binary stuff is just *whoosh* over my head.

Sorry for the long explaination. I'm not looking for a complete answer (I have read the rules, and I do enjoy coding), I just would just like a little help please.

[Salem]

To open a file in binary mode FILE *fp = fopen("image.bin","rb"); To read a byte from the file

int ch = fgetc( fp );
if ( ch != EOF ) { /* do something */ }

Reading the whole file extends to while ( (ch=fgetc(fp)) != EOF ) To extract pairs of bits to index your matrix, do something like index = ( ch >> n ) & 0x03; Since there are 4 pairs of bits in your average 8-bit byte, you would need to have a loop, and values of n of 0,2,4,6

[chris.lloyd]

To extract pairs of bits to index your matrix, do something like index = ( ch >> n ) & 0x03; Since there are 4 pairs of bits in your average 8-bit byte, you would need to have a loop, and values of n of 0,2,4,6

Thanks for your help but I'm still a little confused. I've read up on unsigned variables and bitwise operations so I think I know whats going on there.

Say I have an input file with the binary value of 001101 010101 011100 (a 1x1 pixel image with R:13 G:21 and B:28). How would I tell that it meant 13, 21, 28 rather than 53, 87 and 0? It seems a bit processor intensive and flimsy to count the number of bits then do somthing like % (6||8) == 0.

I would like to try the "advanced level" implementation. Here is what the assignment says about it.

The nominal-level implementation is limited in that each 8-bit byte read from the input file must hold a value less than 64 to permit simple representation as a 32-bit Hadamard code. That is, we are only using 6 bits in each byte, and can only encode files that abide by this limitation. The advanced-level implementation extends the program to deal with any file, where each input byte may hold a value in the range 0 to 255. This involves some bitwise trickery. The program will read in and store 8-bit bytes and then encode them in 6-bit chunks. This will require bit-shifting operations and other manipulations. Decoding will similarly involve reading in Hadamard codes, accumulating the 6-bit decoded values and reconstituting them as 8-bit bytes.

The advanced-level implementation requires some more sophisticated use of bit operations. You will need to read in single bytes and accumulate the bits in a larger variable, say an unsigned long, and then extract bits from this store as enough become available. The right and left shift operators, >> and <<, are essential. To do these packing and unpacking operations, you will need to keep track of how many bits are already packed, how many bits are being pushed on, and how many bits are being taken off.

I'm feeling pretty overwhelmed by this, working at a bit level is very different to what I'm used to. :sad: Again, if you feel like your doing the assignment don't worry about it, I'd just like a little clarification on the subject.

BTW, I don't use void main :cheesy:.

[chris.lloyd]

Ok, I'm a bit of an idiot. I figured out what they were asking for the advanced implementation. The only thing I am stuck on now generating the Hadamard matrix as somthing I can compare

Here is the code I have now to make it:

int **create_2D_matrix(int n, int m) {
    Counter i, j;
    int **matrix;

    if (!(matrix = (int**)
        calloc(n, sizeof(int*))))
        return FALSE;

    for (i=0; i < n; ++i)
        if (!(matrix[i] = (int*) calloc(m, sizeof(int)))) {
            /* could not allocate, so free all the old memory */
            for (j=0; j < i; ++j)
                free(matrix[j]);
            free(matrix);
            return FALSE;
        }
    return matrix;
}
/* Hadamard matrices are made by doubling the matrix, and inverting the lower right character. So [ 1 1 ; 1 0 ] becomes [ 1 1 1 1 ; 1 0 1 0 ; 1 1 0 0 ; 1 0 0 1 ] (Matlab notation).
*/
static int ** hdouble_matrix(int **original, int n, int m){
    Matrix duplicate;
    Counter i, j;

    duplicate.n = 2*n;
    duplicate.m = 2*m;
    if (!(duplicate.data = create_2D_matrix(duplicate.n,duplicate.m)))
        error_memory("duplicate");

    for (i=0; i<n; ++i)
        for (j=0; j<m; ++j)
            duplicate.data[i][j] = original[i][j];

    for (i=n; i<duplicate.n; ++i)
        for (j=0; j<m; ++j)
            duplicate.data[i][j] = original[i-n][j];

    for (i=0; i<n; ++i)
        for (j=m; j<duplicate.m; ++j)
            duplicate.data[i][j] = original[i][j-m];

    for (i=n; i<duplicate.n; ++i)
        for (j=m; j<duplicate.m; ++j){
            if (original[i-n][j-m] == 1) duplicate.data[i][j] = 0;
            if (original[i-n][j-m] == 0) duplicate.data[i][j] = 1;
        }

    return duplicate.data;
}
int ** create_hadamard(void){
    Counter i;
    Matrix h;
    h.n = 1;
    h.m = 1;

    if (!( h.data = create_2D_matrix(h.n,h.m) ))
        output_merror();
    h.data[0][0] = 1;

    for (i=0; i<NBITS-1; ++i) {
        h.data = hdouble_matrix(h.data,h.n,h.m);
        h.n = h.n*2;
        h.m = h.m*2;
    }
    return h.data;
}

where

typedef struct { 
    int **data;
    int n;
    int m;
} Matrix;

That was before I got involved with all this bit-trickery. I'm thinking that I either have to have a 32x4 character array or just keep the current format and use bit masking or somthing for the compare.

In the notes the instructor said that:

To fill the Hadamard matrix with the appropriate 1’s and 0’s, first set the top-left element, then copy it to make a 2×2 Hadamard, then copy that to make a 4×4 Hadamard, and so on until the entire 32 × 32 matrix is filled. This may be implemented in about ten lines of code using three nested for-loops.

My solution seems a little bloated in that case. Can you think of a way of doing this?

Thanks for any help... Chris :cheesy:

[Salem]

> Say I have an input file with the binary value of 001101 010101 011100
Do you have a 1x1 image file to hand? How big is it?

All information in files is stored in multiples of 8 bits, and read with nothing finer than 8 bits at a time. Since your data is arranged in groups of 6 bits, there are two basic choices.

1. Pad each group of 6 bits with 2 bits of unused data, which may be at the start or end of the byte.
So your input data looks like one of these (the black 0's are padding which you need to ignore)
00001101 00010101 00011100
00110100 01010100 01110000

2. Pack each group of 6 bits into bytes, like so
00110101 01010111 00000000
but this results in some values being spread over more than one byte in the file. Over a large file, this would use a lot less space than padding each byte.

A 1x1 image file coded with either of these would be 3 bytes long.

Or maybe for your test code, the binary data is really just a text file containing groups of human readable 0 and 1 characters which you can read and edit with any text editor.

A 1x1 image file coded with either of these would be about 20 bytes long.

[chris.lloyd]

Hi,

I have an example image (its about 300k). I just looked throught the file and the data is stored like this:

00001101 00010101 00011100

From what I understand now is that the advanced level implementation asks for each group of 6 bits to be encoded on their own so that it would take 6 bit data like:

00001101 00010101 00011100

This would allow for any data to be transmitted, rather than somthing just specific to an image. An each of those groups of 6 bits would translate into a row of a 64x32 hadamard matrix (rows 1- 32 are the original matrix and rows 33-64 are the original matrix bitflipped).

I guess where I'm having a problem is choosing how to store/create the hadamard matrix so I can compare it to the chunks of bits.

Thanks so much for your colourful help Salem! If you want I can upload my sourcecode so far, but I don't think that'll solve the problem.

Chris

[chris.lloyd]

Ok! I think I have somthing, I can store the bits in an unsigned long type like:

unsigned long * hadamard[64];

Now I just have to figure out how to get each row of the hadamard matrix into long form. If anybody has any suggestions they would really be appreciated.

Chris

[chris.lloyd]

Ok! I've figured out how to store the matrix and have set up the loops to copy the squares. I'm having a little trouble coming up with a bitwise operation to copy bit x on line y, to bit j on line i.

Here's what I have so far:

void populate_lookup(unsigned long * lookup){

    Counter i; // ROWS
    Counter j; // COLUMNS
    Counter y; // Original ROWS
    Counter x; // Original Columns
    Counter n;
    lookup[0] = 1 << (HADAMARD_SIZE-1); // Sets the first bit to 1

    for (n=1; n<HADAMARD_SIZE; n*=2 ){
        for (i=0; i<(2*n); i++) {
            for (j=(HADAMARD_SIZE-1); j>(HADAMARD_SIZE-1-(2*n)); --j) {
                if (i>=n) y = i-n; else y = i;
                if (j<=(HADAMARD_SIZE-1-n)) x = j + n; else x = j;

/* This is the line.
 * y is the row being copied from and x is the position on that row (minused from 31)
 * i is the row being the bit is copied to, and j is the position it should be copied to (again, like x, minused from 31)
 * These values have all been tested so they are correct, I just can't get the bitwise equation to work.
 * I'm not worrying about inverting the lower right bit yet, I know how to do that once I've got this line.

                lookup[i] |= (lookup[y] & (1L << x)) >> (j+1-HADAMARD_SIZE);
            }
        } 
    }
// This just inverst the current results for the rest of the matrix.
    for (i=HADAMARD_SIZE; i<(2*HADAMARD_SIZE); ++i)
        lookup[i] = ~lookup[i-HADAMARD_SIZE];
}

Yeah, I'm pretty stuck. I'm just trying to do it without inverting the lower right bit first, so technically I should get a 32x32 matrix of 1's. I'm thinking that maybe I have to look into XOR ^ rather than using all those bitshifts. Does anybody have any suggestions? I'm also thinking that I might have to put this into a new thread as its evolved quite a bit from the original problem.