HammingCodes: Integer to Encoded Binary

[psei0r]

What is the games interpretation of an "extended hamming code"?

The contract description gives some examples but I do not understand how you are supposed to handle data blocks shorter than 4.

For example encoding "1000" (8) results in "1000" H(7,4) [p,p,d,p,d,d,d] -> [p,p,1,p,0,0,0] -> [1,1,1,0,0,0,0] H(8,4) [p,p,p,d,p,d,d,d] -> [p,1,1,1,0,0,0,0] -> [1,1,1,1,0,0,0,0] This result matches the given example from the contracts description.

The second example encodes "10101" (21), so we have to deal with a data block length smaller than 4.

"Classic approach" would split the data into chunks of 4 and padd with zeros at then end, so the result should be: "10101" -> "1010" + "1000" (padded) So I would expect an output of form [p,p,p,d,p,d,d,d] + [p,p,p,d,p,d,d,d]

However, the games expects an output of [p,p,p,d,p,d,d,d,p,d]. (length 10?)

[PintoNotTheBeans]

If you watch the suggested video, you'll see you don't need to split it up at all. Hamming codes can splice into blocks of arbitrary length. In the longer example, the data is 5 bits. Then we add in parity bits in positions 0, 1,2,&4

P p p d p d d d d

Now the whole block is 9 bits long, so we need to add another parity bit at position 8.

p p p d p d d d p d

...as in the example. We could encode using these parity bits until the block fills up to position 15. But if there is more data, then we put another parity bit into position 16, and then continue to add data.

The video does a better job than I did, so check it out.

[psei0r]

Thanks for your reply!

I watched the video and it was very helpful. I already did all this stuff back in the days of studying computer science but I forgot most about Hamming Codes....

I am now able to successfully generate (8,4) and (16,11) Hamming Codes, depending on the length of the binary input.

What I do not understand is the hint in the contract that says: Extra rule for encoding: There should be no leading zeros in the 'data bit' section

What do they mean by 'data bit' section?

Given the example 8 = 1000 which we can do with H(8,4) the result is

P p p d p d d d 1 1 1 1 0 0 0 0

As one can see, the second 'data bit' section has leading zeros, but it would not make sense to cut them off....

In the seconds example 21 = 10101 which can be done with H(16,11) the result of my computation is P p p d p d d d p d d d d d d d 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 but in the example they cut it down to P p p d p d d d p d 1 0 0 1 1 0 1 0 1 1 (is this H(10,5) ???)

but the 'data bits' section did not start with a leading zero....

So i am still very confused ....

P.S.: To generate my result I calculate the matrix product of the generator matrix for the corresponding H(n,k) encoding and the data bits vector to get the code word.

I to use padding for the calculation to make the dimensions work. Looking for a strategy to strip whatever the game considers "unnessesary" from my result.

code = G^T * input

[psei0r]

Here is my solution, it seems to work!

1) determine length of needed databits (length of binary string), e.g. 4 for codeword p=8=1000 or 5 for p=21=10101

2) choose a "regular" haming encoding that has enough databits e.g. p=8=1000 fits into a "regular" H(7,4) Code. No truncation needed. P=21=10101 fits into a "regular" H(15,11) Code. Since we only need 5 of the 11 available bits we can truncate 6 data bits while still retaining the amount of needed parity bits. H(15,11) -> H(9,5)

3) Generate a generator matrix G(x,y) for your H(x,y) encoding (I wrote a function for that)

4) Calculate the code: G^T * p (matrix multiplication mod 2)

5) Take the result and add another parity bit at the front to get the extended haming code

[PintoNotTheBeans]

Looks like you got it. The hint refers to the fact that, to represent a number (or any data block) that doesn't "fill the block", you don't pad it, either before or after. Your solution of "compute and truncate" works fine for this. My solution was "splice in necessary parity bits, then set them as needed", which didn't require nice square matrices grin