Ponder This Challenge - April 2009 - 5-ops implementation of erasure code

Ponder This Challenge:

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 loosing 2 nibbles).

Clue #1 (04/06): f(x) = ((((x * c1) & c2) * c3) & c4) % c5;

Update (04/07): When you read the data, you know which two disks have failed.

Clue #2 (updated 04/24): c1 = (2792-1)/(233-1); c2 = (2816-1)/(234-1); c4 = (21088-1)/(234-1)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  f(x) = ((((x * c1) & c2) * c3) & c4) % c5, where
  c1 = (2792-1)/(233-1);
  c2 = (2816-1)/(234-1);
  c3 = 1+234+23*34+24*34+28*34;
  c4 = (21088-1)/(234-1)
  c5 = 233-1;

  We encoded a linear erasure code using O(1) operations, thanks to Eli Biham who gave us a simpler solution. A nice discussion on this issue can be found at http://www.brand.site.co.il/riddles/200902q.html (link resides outside of ibm.com) and the links from it.

Solvers

• Michael Brand (04/02/2009 04:47 PM EDT)
• Eli Biham (04/16/2009 06:15 AM EDT)
• Boris Nikolaus (04/30/2009 12:44 PM EDT)
• Nyles Heise (04/30/2009 00:16 AM EDT)
• Corey Cerovsek (05/04/2009 08:58 AM EDT)
• Gary M Gerken (05/05/2009 11:48 PM EDT)
• Daniel Bitin (05/06/2009 12:55 PM EDT)
• Balakrishnan V (05/07/2009 02:00 PM EDT)
• Dan Dima (05/21/2009 10:02 AM EDT)
• Liubing Yu (05/29/2009 04:30 AM EDT)
• Hongcheng Zhu (05/31/2009 10:39 AM EDT)