2
$\begingroup$

I asked this question in math.stackexchange (link) and I have had an answer for general case by using Reed-Solomon Code. More information for Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems (pdf). It explains general solution via using arithmatics over Galois Field.

However, it needs another operator for multiplication and the solution can be very complex for higher $n$ and $k$ values. I wondered how to recover the k lost items if we let only XOR operator. I have a conjecture for general solution but I have not found out a way if the conjecture is true for general case or not. I need help to prove or disprove my conjecture . And I wonder how I can approach to solve such combinatorics problem. What can the minimal solution be?

$$x_1,x_2,x_3,\dots,x_n$$ where they all are same size binary data.

If we lose one of them in series and if we want it to recover, we just need to store $y_1$ that is same size like the items in series.

$$y_1=x_1 \oplus x_2 \oplus x_3 \oplus ... \oplus x_n$$

where $\oplus$ is the XOR binary operator. $\oplus$ can be defined as

$$ x \oplus x =0 $$ $$ x \oplus 0 =x $$ $$ 0 \oplus x =x $$ $$ x \oplus y = y \oplus x $$

$$ (x \oplus y) \oplus y =x \oplus (y \oplus y) = x \oplus 0 = x $$

Let's assume that we lost $x_1$. We just need to apply $n-1$ xor operations to recover $x_1$ $$y_1 \oplus x_2 \oplus x_3 \oplus ... \oplus x_n =x_1$$

My question:

  • How can k lost items be recovered if we let only XOR operator?
  • What is the minimum number of spare items ($y_1,y_2,..,y_m$) be required to recover the k lost items by using only XOR operator?

I would like to write my conjecture for the solution of the general problem (for any $n$ and $k$).

The general solution for $k=2$ can be found via erasure codes.

$k=2$


$n=2$ $$y_1=x_1$$ $$y_2=x_2$$

\begin{matrix} &y_2&y_1\\1=&0&1&x_1\\2= &1&0&x_2 \end{matrix}

$n=3$ $$y_1=x_1\oplus x_3 $$ $$y_2=x_2 \oplus x_3$$

\begin{matrix} &y_2&y_1\\1=&0&1&x_1\\2= &1&0&x_2 \\3= &1&1&x_3 \end{matrix}

$n=4$ $$y_1=x_1\oplus x_3 $$ $$y_2=x_2 \oplus x_3$$ $$y_3=x_4 $$

\begin{matrix} &y_3&y_2&y_1\\1=&0&0&1&x_1\\2= &0&1&0&x_2 \\3= &0&1&1&x_3 \\4= &1&0&0&x_4 \end{matrix}

$n=5$ $$y_1=x_1\oplus x_3 \oplus x_5 $$ $$y_2=x_2 \oplus x_3$$ $$y_3=x_4 \oplus x_5 $$

\begin{matrix} &y_3&y_2&y_1\\1=&0&0&1&x_1\\2= &0&1&0&x_2 \\3= &0&1&1&x_3 \\4= &1&0&0&x_4 \\5= &1&0&1&x_5 \end{matrix}

For $k=2$, This sequence goes linear and increase 1 for each new $x_i$. At least one bit always changes for 2 random selected inputs.

I would like to extend this idea for higher k

$k=3$


$n=3$, Minimum solution $$y_1=x_1 $$ $$y_2=x_2 $$ $$y_3=x_3 $$

\begin{matrix} &y_3&y_2&y_1\\1=&0&0&1&x_1\\2= &0&1&0&x_2 \\4= &1&0&0&x_3 \end{matrix}

$n=4$, Minimum solution $$y_1=x_1 \oplus x_4 $$ $$y_2=x_2 \oplus x_4 $$ $$y_3=x_3 \oplus x_4 $$

\begin{matrix} &y_3&y_2&y_1\\1=&0&0&1&x_1\\2= &0&1&0&x_2 \\4= &1&0&0&x_3 \\7= &1&1&1&x_4 \end{matrix}

$k=4$


$n=4$, Minimum solution $$y_1=x_1 $$ $$y_2=x_2 $$ $$y_3=x_3 $$ $$y_4=x_4 $$

\begin{matrix} &y_4&y_3&y_2&y_1\\1=&0&0&0&1&x_1\\2= &0&0&1&0&x_2 \\4= &0&1&0&0&x_3 \\8= &1&0&0&0&x_4 \end{matrix}

$n=5$, Minimum solution $$y_1=x_1 \oplus x_5 $$ $$y_2=x_2 \oplus x_5 $$ $$y_3=x_3 \oplus x_5 $$ $$y_4=x_4 \oplus x_5 $$

\begin{matrix} &y_4&y_3&y_2&y_1\\1=&0&0&0&1&x_1\\2= &0&0&1&0&x_2 \\4= &0&1&0&0&x_3 \\8= &1&0&0&0&x_4 \\15= &1&1&1&1&x_5 \end{matrix}

My Conjecture for general solution:

I have noticed that If we continue the table series in the way I wrote below, they satisfy my request. They all may not be minimum but they have not failed yet for any number that I tested .

\begin{matrix} n=&1&2&3&4&5&6&7&8&9&10&...n \\ &-&-&-&-&-&-&-&-&-&-& \\ k=1 |&1&1&1&1&1&1&1&1&1&1&...A_1(n)=1 \\ k=2 |&1&2&3&4&5&6&7&8&9&10&...A_2(n)=n\\ k=3 |&1&2&4&7&11&16&22&29&37&46&...A_3(n)=\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}=\frac{n^2-n+2}{2} \\k=4 |&1&2&4&8&15&26&42&64&93&130&...A_4(n)=\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\binom{n-1}{3} \\k=5 |&1&2&4&8&16&31&57&99&163&256&... A_5(n)=\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\binom{n-1}{3}+\binom{n-1}{4}\\k=6 |&1&2&4&8&16&32&63&120&219&382&...A_6(n)=\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\binom{n-1}{3}+\binom{n-1}{4}+\binom{n-1}{5} \end{matrix}

General formula for the table $A_k(n)$ for $n,k>0$ and $A_k(1)=1$ and $A_1(n)=1$ $$A_{k+1}(n+1) =A_{k+1}(n)+A_{k}(n)$$

$$A_k(n)=\sum_{i=0}^{k-1}\binom{n-1}{i}$$

Generating function of $A_k(n)$ :

$$e^x\sum_{i=0}^{k-1}\frac{x^i}{i!}=\sum_{n=0}^{\infty} A_k(n)\frac{x^n}{n!}$$

I need to prove for all $A_k(n)$ or disprove for any $A_k(n)$ that does not satisfy the solution.

Please help me prove that my conjecture is a solution or not for general problem if we let only XOR operator.

$\endgroup$
  • 2
    $\begingroup$ Loks like it is a linear algebra problem: you try to find $n\times m$ matrix with the minimal number $m$ of columns such that every $k\times m$ submatrix has full rank (XOR is just addition in $\mathbb Z_2$). In principle, even considering random matrices can give you the right order of magnitude on the rough scale, though I suspect that this problem has been studied long ago and has a full solution. $\endgroup$ – fedja May 28 '18 at 19:30
  • $\begingroup$ Isn't this just linear algebra over $\mathbb{Z}/2\mathbb{Z}$? $\endgroup$ – Harry Gindi May 29 '18 at 6:48
  • $\begingroup$ Unless I am missing something, the Reed–Solomon code over a field of characteristic $2$ is an $\mathbb F_2$-linear map, and as such can be written with XOR only. $\endgroup$ – Emil Jeřábek 3.0 May 29 '18 at 7:06
  • $\begingroup$ @EmilJeřábek RAID-6 that supports losing any two drives uses Reed-Solomon Code and It based on XOR as addition and a linear feedback shift register (LFSR) as multiplication via the algebra of a Galois field, $GF(2^8)$. $GF(2^8)$ allows for a maximum of 255 drives and 2 spare disks . Reference link:mirrors.edge.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf $\endgroup$ – Mathlover May 29 '18 at 7:24
  • $\begingroup$ Reed Solomon codes have characteristic 2 alphabet but in extension fields, such as $GF(2^8).$ The nonzero scalars of the extension field are needed to make a decent code. $\endgroup$ – kodlu May 29 '18 at 7:47
4
$\begingroup$

The keywords you need to use are regenerating codes, and distributed storage codes with repair. Some researchers in this space are Tamo/Barg, P V Kumar, A. Dimakis, and others. This is a very active research area, and things have moved quite rapidly in the last decade.

Having said that, there is probably much more to be done. Most of these codes are over extension fields, and used for massive distributed databases where, e.g., web pages are replicated, storage as a service etc.

I found an interesting paper at the link here which seems to focus on binary operations only, and uses shifts, it may be of interest to you. It is called `` BASIC Regenerating Code: Binary Addition and Shift for Exact Repair''.

Happy hunting!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.