formation of numbers - IBM Research Puzzle – 5-ops implementation of erasure code

I found this interesting puzzle on IBM Research Puzzling Page called Ponder This; specifically, here.

Design a storage system that encodes 24 information bits on 8 disks of 4 bits each, such that:

1. 
   

   Combining the 8×4 bits into a 32 bits number (taking a nibble from each disk), a function f from 24 bits to 32 can be computed using only 5 operations, each of which is out of the set {+, -, *, /, %, &, |, ~} (addition; subtraction, multiplication; integer division, modulo; bitwise-and; bitwise-or; and bitwise-not) on variable length integers. In other words, if every operation takes a nanosecond, the function can be computed in 5 nanoseconds.

   
   


2. 
   

   One can recover the original 24 bits even after any 2 of the 8 disks crash (making them unreadable and hence losing 2 nibbles).

   
   

---

And here’s the rest of the challenge — I don’t know whether it should be hidden, but the clues do seem to give away quite a bit of information.

When you read the data, you know which two disks have failed.

Clue #1:

f(x) = ((((x * c₁) & c₂) * c₃) & c₄) % c₅

Clue #2:

c₁= (2⁷⁹²-1)/(2³³-1);  c₂= (2⁸¹⁶-1)/(2³⁴-1);  c₄= (2¹⁰⁸⁸-1)/(2³⁴-1)

Answer

Posting a partial answer after clue 2:

Let's see then. (Doing binary operations in my head, so please forgive any errors.)

A number of the form $2^M -1$ is a string of "1" bits in binary, and there are $M$ bits in that string. Dividing a long string of $M$ ones with a shorter string of $N$ ones will result in a repeated pattern of "Lots of Zeroes ($N-1$ of them), One, LoZ, one, LoZ, one.." with $\frac{M}{N}$ repetitions in total. (Think long division. You don't have even think in binary, since the result looks the same in base 10, or any other base for that matter.) So the $\mathbf{c_n}$ constants given so far consist of mostly zeroes, with a single "1" at regular intervals.

Multiplying $x$ by $\mathbf{c_1}$ makes 24 copies of $\mathbf{x}$ (the original 24 bits of data). Each copy has 32 bits assigned to it, and there's one extra zero bit always in front of a copy.

Masking (bitwise $AND$ is sometimes called masking, because you can only "see" the bits of original data that correspond to "holes" (ones) in the mask.) with $c_2$ then zeroes everything except one bit (a different one) in every copy. This leaves us with the bits in the original data, in the original order, separated from each other by a bunch of zeroes.

As an aside, since $c_2$ is only used as a mask, looks like we could just as well have used $c_4$ instead: the bit pattern is the same, $c_4$ just has 32 repetitions instead of 24. Since our data string is currently only 24 repetitions long, the extra ones in the mask would only produce leading zeroes, which don't matter. In other words, $\mathbf{c_2}$ is redundant, and we could have used the longer mask $\mathbf{c_4}$ instead.

Multiplying with $c_3$ then probably causes any "1" bits to flip the next copies' bits according to some pattern, because $c_4$ again selects the same bits that $c_2$ did. In other words, $\mathbf{c_3}$ is where the magic happens, everything else is just preparation for it. Since $c_4$ is longer than $c_2$, it's likely that $c_3$ is approximately $2^{272}$.

EDIT: $c_4$ also selects 8 bits that weren't our original data. We should probably modify them instead of the other data bits. That may not be as simple as it sounds; the leftmost bit needs to be multiplied with an annoyingly small number, which might cause the original data bits to flip unless $c_3$'s bit pattern is Extremely Smart. Also, this places doubts on the size estimate in the chapter above: if we want the rightmost bit to flip the leftmost one, it needs to be multiplied by $2^{1054}$. (Or possibly by another number around those neighbourhoods; not doing exact calculations here.)

Continuing on the "don't mess up the original data" hypothesis, the polynomial pattern could then possibly be repeated 24 times in $c_3$, for each of the bits in the original data. If one carefully avoided putting any "1" bits in positions that are divisible by 34, the multiplications maybe could avoid flipping the first 24 "interesting" bits, and only affected the parity bits on the "far left", and of course all the empty space between the original data's bits.

Now if only I had an irreducible polynomial handy, I think I might be able to work this one out. (I think I may have the parts to construct the XOR portion of the solution now, but haven't tested the idea yet.)

--

EDIT OF EDIT, nine days later: Since this question has received practically no attention whatsoever (not even any hints or comments from OP), I went ahead and snuck a peek at the intended solution. The intended solution actually does garble up the data, so the solution is not RAID 6, and recovering the initial data requires processing even when all the drives are intact.

Since that kind of encoding wasn't what I wanted to learn, I'm going to drop any effort on this puzzle, and just add the intended solution here:

$c_3$ looks for any "1" bits in the data. If it finds one at position N (counting from the right), it then flips the bits at positions N+1, N+3, N+4, and N+8. All the flips are done simultaneously (or if you like, starting with the leftmost bit and working towards the right from there), so a flip's result doesn't cause or prevent any other flips. After this operation, an "1" bit in the original data will have an effect on three consecutive nybbles, hopefully in such a manner that each possible input nybble will produce a unique effect on the adjacent output nybbles, and therefore each bit can (hopefully) be recovered even if any two nybbles are lost. The numerical value for $c_3$ that achieves this effect is $2^{\mathbf8*34}+2^{\mathbf4*34}+2^{\mathbf3*34}+2^{\mathbf1*34}+2^{\mathbf0*34}$.

Recovering the original data from the final result is so boring, that even the IBM guys writing the question in 2009 couldn't be bothered. Really. They didn't even give instructions on how to read the data on an intact disk array. (Not that it's all that difficult if you know how it was encoded.)

Given that what we are trying to do is called RAID 6, then $c_3$ is likely to contain the bits corresponding to the coefficients of an irreducible polynomial in the finite field $GF[2^4]$. (These are mostly new words for me, I have no idea how this actually works..). The size of the field is 16, because out of our 8 parity bits, we probably want to reserve 4 for the regular XOR, which we must also somehow magic up while were are multiplying here.

If the RAID 6 assumption is correct, we want to have as our output the original bits, followed (or, as is more likely, preceded) by the XOR nybble and the polynomial result nybble in some order. Exactly how to achieve this in $c_3$, I don't know.

Because we want a 32 bit result, then $c_5$ must be at least $2^{32}$. (If we need to recover 8 bits of lost data, then every single one of our parity bit combinations must be assigned to a different lost data combination, so $c_5$ cannot possibly be smaller than that.) That exact number won't work though, since it would just grab the last 32 bits of our huge bit string, and discard all the multiplication results we painstakingly achieved. Because the masking with $c_4$ has left us with 32 "important" bits, each separated by 33 zeroes (I think), the sensible thing would be to pick them one by one as the bits of the result. Taking a modulo with a number looking like "111...111110" does exactly that, so $\mathbf{c_5}$ is probably $\mathbf{2^{34}-2}$

EDIT OF EDIT: This value for $c_5$ seems to work. The IBM solution uses half of this one, which gives the same remainder for every possible input. I think.

There's absolutely no way I can get the actual value for $c_3$, so now it's bedtime for me.