haming code & java or C++

dilberim82 · 02-03-2004, 10:13 AM

Hi everyone,
I am trying to write a project that is supposed to turn a number or character into its binary value, then add redundancy bits to it and corrupt one of the redundancy bits and finally find the corrupt bit and fix it. I am sorry its a little confusing. We are almost done w/ it but i cannot figure out a function to calculate the redundancy bits.
R = redundancy bit

R1 adds bits 1, 3, 5, 7, 9, 11, 13, etc. <~(my approach is to do a for loop, start from 1 and add 2 each time until there are no more bits)

R2 adds bits 2,3,6,7, 10,11, etc. (do a for loop, start from 2 add 4 each time and then go back and start from 3 and add 4 each time until the end of bits) <~~i am not sure if i can do this

R3 adds bits 8,9,10,11,12 (this one is easy).

My question is, do i have to calculate each redundancy bit by itself or is there any other easier way and more efficient way. And calculatings the 2nd redundancy bit seems hard. It looks i have to use two loops.

Thanks in advance.

Mohsen · 02-03-2004, 11:14 AM

There are some ready-to-work CRC (e.g. crc32.h) checksum algorithms (here is one crc32.cpp, and here's the header file: crc32.h.
If you want to implement one, with the mentioned way there seems to be no problem!
Suppose that you want to extract n'th bit from string myStr:

Code:

for (i = 1; i <= size; i++)
{
  R1 += getBit (i * 2 - 1, myStr);

  R2 += getBit (i * 4 + 2, myStr);
  R2 += getBit (i * 4 + 3, myStr);

  R3 += getBit (i + 8, myStr);
}

Now you should just implment `getBit (int bitNum, char* str)'. That's easy:

Code:

// I know this is not a very good implementation (I've done it in hurry;))
int getBit (int bitNum, char* str) {
  int k = bitNum / 8;
  char ch = str[k];
  ch >>= bitNum - k*8;
  ch <<= 8 - (bitNum - k*8);
  return ch;
}

Mohsen · 02-03-2004, 11:29 AM

also you should know that this:

Code:

for (int i = 0; i < 100; i++) {
   f1 ();
   f2 ();
}

hase the same order (O(n) where n is 100 here) of running time with:

Code:

for (int i = 0; i < 100; i++)
   f1 ();
for (int j = 0; j < 100; j++)
   f2 ();

dilberim82 · 02-03-2004, 03:35 PM

Thanks a lot Mohsen.
I knew the pattern i just didn't know how to do it in 1 for loop. I was thinking about doing each redundancy bit in their own loop. That helps a lot.

wapcaplet · 02-03-2004, 05:31 PM

If your code isn't too long (say 8 bits), it'd probably be easiest to just use a lookup table for finding the redundancy bits; declare an array of size 256, and store the three-bit checksum for code X in array[X]. Might be handy if you're using them repeatedly.

I think the easiest way to calculate them would be to multiply each 8-bit input by an 3x8 matrix that has "1" in the positions that should be added to the result, and "0" in all the rest. So, since bit 1 of the checksum should be bits 1, 3, 5, and 7, the first row of the matrix would be:

Code:

1 0 1 0 1 0 1 0

Bit 2 of the checksum would be row 2 of the matrix, and bit 3 would be row 3. Call it matrix E. Then you get your 8-bit input as an 8x1 column vector M, and multiply it on the right by E:

E x M = C

where C is your 3-bit checksum. You could probably simplify it even more; don't even need to use a matrix, since it's just 1 bit in each position. You could just represent the matrix as three 8-bit variables R1, R2, R3 (one for the 8 bits in each row, so R1 = [10101010], etc.); logical AND M with each of those and XOR them together: (R1 & M) ^ (R2 & M) ^ (R3 & M)

Then again, I've taken a whole university course on this stuff, so if that looks too complicated, then nevermind

dilberim82 · 02-03-2004, 06:58 PM

User is allowed enter any number so it can be any size. I am using arraylist (java).