Hamming Code: Number of parity bits

2
votes

I'm trying to write a method in java that will take an input of any number of 0 or 1 digits and output that line after being encoded with Hamming Code.

I have managed to write the code when knowing the number of digits the input will have (in this case 16) because knowing the number of digits in the input, I immediately know the number of parity bits there have to be added (5 in this case) to a total of 21 digits in the final output. I am working with int arrays so I need to declare a size in the beginning and my code works based on those exact sizes.

Can you guys think of any way/algorithm that can give me the number of digits the output will have (after adding the relevant parity digits to the number of input digits) based solely on the number of input digits?

Or do I have to tackle this problem in a totally different way? Any suggestions? Thank you in advance!

Cheers!

2
javaalgorithmhamming-code
This great question appears to be off-topic; it would be better asked and answered on math.stackexchange.com. – Richard Sitze
Indeed, this seems to be more of a maths question than actual programming. – Dimebag

2 Answers

0
votes

From my understanding, you get your 6th parity bit at 32 bits of input, 7th at 64, etc. so what you need is floor(lg(n)) + 1, which in java you can get by using 32 - Integer.numberOfLeadingZeros(n).

Assuming your input is made up entirely of 0s and 1s, you would do

int parityDigits = 32 - Integer.numberOfLeadingZeros(input.length());
0
votes

Is your input a String or individual bits? If you input as a String, you can convert each character to a bit, and the length of the String gives you the length of the array.

If you need to input the bits one at a time, store them in an ArrayList. When all bits have been entered, you can convert your list to an array easily, or use the size of the list etc.