How to recover $k$ lost items in binary data $x_1,x_2,x_3 \dots,x_n$?

Question

$$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. Because $\oplus$ can be defined

$$ 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:

• if we lose k items in ($x_1,x_2,x_3,.....,x_n$ ) , How can the k lost items be recovered?
• What are the minimum number of spare items $y_1,y_2,..,y_m$ required to recover the k lost items?
• Which binary operators and algorithm should be used to recover the k lost items in series?

My attempt to solve 2 lost items :($k=2$)

I do not know if they are minimum or not, I used $\oplus$ operator for now. I put my approach without proof below.

for $n=3$; We need minimum 2 store places. $$y_1=x_1 \oplus x_2 $$ $$y_2=x_2 \oplus x_3 $$

for $n=4$; We need minimum 3 store places. $$y_1=x_1 \oplus x_2 $$ $$y_2=x_2 \oplus x_3 $$ $$y_3=x_4 \oplus x_1 $$

for $n=5$; We need minimum 3 store places. $$y_1=x_1 \oplus x_2 \oplus x_3 $$ $$y_2=x_2 \oplus x_3 \oplus x_4 $$ $$y_3=x_3 \oplus x_4 \oplus x_5 $$

for $n=6$; We need minimum 3 store places. $$y_1=x_1 \oplus x_2 \oplus x_3 $$ $$y_2=x_3 \oplus x_4 \oplus x_5 $$ $$y_3=x_5 \oplus x_6 \oplus x_1 $$

for $n=7$; I have just found minimum 3 store places. $$y_1=x_1 \oplus x_2 \oplus x_3 \oplus x_4 $$ $$y_2=x_3 \oplus x_4 \oplus x_5 \oplus x_6 $$ $$y_3=x_6 \oplus x_7 \oplus x_1 \oplus x_3 $$

I believe if we can solve the problem for 2 lost items , It can be generalized for k lost items.

The problem is also very related with combinatorics. I would like to get comments how to approach to the general problem .

Thanks a lot for answers and comments

EDIT: 04/25/2018

I would like to write my approach to solve the general problem (for any $n$ and $k$).

As @Mike Earnest wrote in his answer , 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 not minimum but they have not failed yet for any number when I tested them.

\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!}$$

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.

An example: I would like to give an example how to write solution for $n=10$, $k=6$

$$x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10}$$

We need to recover 6 terms in 10 inputs .

\begin{matrix} &y_9&y_8&y_7&y_6&y_5&y_4&y_3&y_2&y_1\\ 1=&0&0&0&0&0&0&0&0&1&x_1\\2= &0&0&0&0&0&0&0&1&0&x_2 \\4= &0&0&0&0&0&0&1&0&0&x_3\\8= &0&0&0&0&0&1&0&0&0&x_4 \\16= &0&0&0&0&1&0&0&0&0&x_5 \\32= &0&0&0&1&0&0&0&0&0&x_6 \\63= &0&0&0&1&1&1&1&1&1&x_7 \\120= &0&0&1&1&1&1&0&0&0&x_8 \\219= &0&1&1&0&1&1&0&1&1&x_9 \\382= &1&0&1&1&1&1&1&1&0&x_{10} \end{matrix}

If we write xor equations from table. We need 9 spares.

$$y_1=x_1 \oplus x_7 \oplus x_9 $$ $$y_2=x_2 \oplus x_7 \oplus x_9 \oplus x_{10} $$ $$y_3=x_3 \oplus x_7 \oplus x_{10} $$ $$y_4=x_4 \oplus x_7 \oplus x_8 \oplus x_9 \oplus x_{10} $$ $$y_5=x_5 \oplus x_7 \oplus x_8 \oplus x_9 \oplus x_{10} $$ $$y_6=x_6 \oplus x_7 \oplus x_8 \oplus x_{10} $$ $$y_7=x_8 \oplus x_9 \oplus x_{10} $$ $$y_8=x_9 $$ $$y_9= x_{10} $$

Note: I do not claim that it is minimum solution. I just claim that it is a solution for problem.

EDIT:(4/27/2018) $$A_k(n) =\sum_{i=0}^{k-1}\binom{n-1}{i}$$ Required spare numbers (m) can be found $$m=\log_2(A_k(n))+1$$

$n>>k$ and for very big $n$ $$A_k(n) \approx \frac{n^{k-1}}{(k-1)!} $$

$$m\approx\log_2( \frac{n^{k-1}}{(k-1)!})+1$$ $$m\approx(k-1)log_2( n)+1-log_2((k-1)!)$$

$$k=2 ---> m\approx log_2( n)+1$$ $$k=3 ---> m\approx 2log_2( n)$$ $$k=4 ---> m\approx 3log_2( n)-log_2( 3!)+1$$ $$k=5 ---> m\approx 4log_2( n)-log_2( 4!)+1$$ $$k=6 ---> m\approx 5log_2( n)-log_2( 5!)+1$$

Answer 1

What you are looking for is called an Erasure Code.

For $k=2$, you can recover the data using $1+\log_2 n$ spare items. To explain the approach, it will simplify things to index the items from $0$, like $x_0,x_1,\dots,x_{n-1}$.

Let $y_0=x_0\oplus x_1\oplus\dots\oplus x_{n-1}$ be the xor of all the items. For each $k=1,\dots,\lceil \log_2 n\rceil$, let $y_k$ be the xor of all the items $x_i$ whose index $i$ has a $1$ in the $k^{th}$ place when written in binary. For example, $y_1$ is the xor of all the odd index items, while $y_2=x_2\oplus x_3\oplus x_6\oplus x_7\oplus x_{10}\oplus x_{11}\cdots$.

To recover the data, suppose that $x_i$ and $x_j$ are missing. Writing $i$ and $j$ in binary, there must exist a digit where $i$ and $j$ differ. Say this is the $k^{th}$ digit, so that $i$ has a $1$ in its $k^{th}$ digit and $j$ has a $0$. Using $y_k$, you can recover $x_i$, and using $y_0\oplus y_k$, you can recover $x_j$.

I know this is not optimal in general, because your solution for $k=2,n=3$ only uses $2$ spare items while mine would use $3$. But I do know that it is close to optimal. Namely, I can prove that $(\log_2 n)-1$ spare items are not sufficient in general. Basically, every spare item is the xor of the items whose indices are in some set, $S$. Say you have $k$ spare items, corresponding to set $S_1,\dots,S_k$. Partition the items $x_0,\dots,x_{n-1}$ into $2^k$ boxes, based on whether or not $x_i$ is in each set $S_j$. If $n>2^k$, then there will exist two items $x_i$ and $x_\ell$ which are in the same box, meaning they cannot be distinguished using the stored information.

I'm not sure yet how to generalize to higher $k$. Again, you should look into erasure codes.

---

Okay, I have an answer which is optimal, but it is not based on xor's, and only works for specific types of data. Specifcally, suppose all of the $x_i$ are binary strings with $b$ bits. Then, as long as $$ 2^b \ge (n+k),\tag{*} $$ then you can recover $k$ lost items by storing exactly $k$ additional files! This is certainly optimal.

The method is called the Reed-Solomon Code. The idea is to treat each data vector as an element of the finite field with $2^b$ elements, and to fit a polynomial of degree $n-1$ to this data, then let $y_1,y_2,\dots,y_k$ be the values of the polynomial at $k$ other points. The requirement $(*)$ is necessary so there are enough points to evaluate the polynomial at. Since a polynomial of degree $n-1$ is determined by its values at any $n$ points, you can recover the polynomial with the $n$ pieces of data you see.

When $(*)$ does not hold, then you would need to group the files of size $b$ into batches with a total of $\log_2(n+k)$ bits, so each batch has $\frac{\log_2(n+k)}{b}$ files. You then need $k$ additional batches, for $$k\cdot\frac{\log_2(n+k)}b$$ additional files.

---

As to your conjectured $A_k(n)$, I think it is much too large. For example, you have $A_2(n)=n$, when the method I gave is much smaller, $1+\log_2(n)$. If you allow codes which are not based on xors, then the Reed-Solomon method would $A_k(n)$ at most $k\log(n+k)$.

However, assuming only xors are allowed, determining the optimal number of extra items seems like a hard combinatorics problem. It is frustrating, because there is no information-theoretic reason why $k$ additional files do not suffices to recover $k$ pieces of data, but something about the constraint of using xors makes that unachievable. Unfortunately, at this point I am stuck.