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.