How to calculate Hamming code without converting to binary string?

Question

I am trying to solve a problem that comes down to finding the hamming code without using binary string of the long number in java.

I don't understand how we can do that, I have searched at many places like the wikipedia explanation and this one I found online but all of them need binary string to work with, but here in this case I can't use them.

I have a long number that represents the input binary, now I need to find the hamming code.

As I understand it, I can have the empty places at positions 1, 2, 8 ... in that binary. Now I can put 0 or 1 in that place using the boolean that tells me if this is an even parity or odd.

I wrote a code using string and lists, but I need to this without using strings or lists.

String text = new Scanner(System.in).next() ;
    int len = text.length() ;
    ArrayList codearray = new ArrayList() ;
    ArrayList pos_arr = new ArrayList() ;


    while (!(len + r + 1 <= Math.pow(2, r))) {
        r++;
    }


    System.out.println("Number of parity bits : "+r);

    for (int i=0 ; i<len + r  ; i++) {

        if (IsPowerTwo(i+1) ){
            codearray.add("?") ;
        }else {
            codearray.add(text.charAt(j));
            j++ ;
        }
    }


    System.out.println(codearray.toString());

    //to determine the position of parity bits
    for (int i=0 ; i< codearray.size() ; i++) {
        if (codearray.get(i) == "?") {
            int k ,s=1;
            // For Debugging.
            //System.out.println("Calculate at position " + (i+1) ) ;
            for (k = i ; k < codearray.size() ; k++){

                if (i==0) {
                    k++ ;
                    pos_arr.add(k);
                }else {

                    pos_arr.add(k+1);
                    if(s % (i+1) == 0) {
                        k += i+1 ;
                    }
                }
                s++ ;

            }

            checkOnes(pos_arr,codearray,i) ;
            pos_arr.clear();
        }


    }

    System.out.println("Code word: ");
    Arr_to_Str(codearray) ;
}

public static boolean IsPowerTwo(int num){
    int checked = num & num -1 ;
    if (checked == 0 ){
        return true ;
    }else {
        return false ;
    }

}
public static void checkOnes(ArrayList array, ArrayList codearray, int position ){

    int count =0;

    for (int i=0 ; i < array.size(); i++) {
        int index = (int) array.get(i) -1 ;
        if (codearray.get(index) == "?"  ) {
            codearray.set(index,0) ;
        }

        int num = Integer.parseInt(codearray.get(index).toString()) ;
        if (num == 1  ) {
            count++ ;
        }
        if(count % 2 ==0 ){
            codearray.set(position, 0) ;
        }else {
            codearray.set(position, 1) ;
        }

    }
}

public static void Arr_to_Str(ArrayList array){
    for (int i=0;i<array.size();i++){
        System.out.print(array.get(i));
    }
}

But this requires me to work with binary string or list, how can I do the same with long numbers like, say 210.

I am really new to bit manipulation and hence I can't wrap my head around this. I would really appreciate any help.

Answer 1

Hamming encoding can be implemented with bit manipulation. It is probably even simpler that with a string. Here are some ideas on the implementation.

Outline of Hamming encoding algorithm is the following

input_val is a long int to encode
output_val_is the long int result
for s in 0..5
  count number of bits in input_val whose position has bit s set
  add to output_val the parity of this count
  add next 2^s bits from input_val to output_val

There are indeed two problems: getting the parity of a specific set of bits and creating the output with bit shifts.

Counting set bits on a given pattern*

For Hamming encoding, one must compute parity on a subset of the bit (pattern). Patterns are 010101010101...01 for first step, 001100110...00110 for second step, etc, and can be encoded in an array mask indexed by the step number. mask[0]=0x5555555555555555, mask[1]=0x6666666666666666, mask[2]=0xf0f0f0f0f0f0f0f0, mask[3]=0xff00ff00ff00ff00, etc

To get this parity, the simpler is to count the number of bits and to get the lSB of this count. There is a function in java that gives the number of bits in an integer. Hence the only operation required here is

count=Integer.bitcount(input_val & masks[s]) ;

where s is the computation stage number.

Then you have to add to output count & 0x1 to add the parity of the count.

Adding a bit to an integer

It is closely related on the number of bits in your input and output value size. I assume for sake on simplicity that both your data can be coded on 64 bits. This means that you have 6 parity bits and that your input data is only part of your variable and that the 6 MSB of input_data are zero.

To add the LSB of an integer v to output_val the simpler is to add it at the MSB position of result, and to shift it right. After 64 bits are added, all is in its proper place. Note the output_val must be unsigned to avoid a right arithmetic shift.

So, to add the LSB of v to output_val, the operation to do is

output_val = (output_val >> 1) | (v<< 63);

v<<63 extract the LSB and put it in MSB position. The OR adds to the shifted result.

To add several bits (k, for instance), one can use

output_val = (output_val >> k) | (v<< (64-k));

So the final implementation (to improve) would be something like

input_queue = input_val;
output_val = 0;
for (s=0; s<6;s++) {'
  count=Integer.bitcount(input_val & masks[s]) ; // compute parity
  output_val = (output_val >> 1) | (count << 63);// add parity to output
  output_val = (output_val >> (1<<s)) | (input_queue << (64-(1<<s)); 
                                   // add 2^s LSB of input to output
  input_queue >>=(1<<s);           // suppress 2^s bits form input_queue
}