3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ These are the fundamental questions in coding theory, particularly linear block codes. Check out the Wikipedia page en.wikipedia.org/wiki/Block_code for an introduction. $\endgroup$ – Jeremy Dover Apr 11 '18 at 20:01
10
+100
$\begingroup$

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.

$\endgroup$
5
  • 4
    $\begingroup$ As is often the case, math is like magic in that knowing the name of something gives you power over it. $\endgroup$ – marty cohen Apr 11 '18 at 21:59
  • $\begingroup$ @MikeEarnest: Thanks a lot for your answer. It gave me a starting point how to approach the problem. Could you please check my last edit in question? Do you have comment about it? $\endgroup$ – Mathlover Apr 26 '18 at 8:03
  • $\begingroup$ @Mathlover See my edit for some additional thoughts. It would appear you have asked a very hard question, it might be well-received on math overflow. $\endgroup$ – Mike Earnest Apr 26 '18 at 13:24
  • $\begingroup$ @MikeEarnest : Thanks a lot for your last edit. I will check the Reed-Solomon method. Please check my last edit about required spare number (m) . It can be found by $m=\log_2(A_k(n))+1$ in my method. It is just extension for $k=2$ and we need to convert $A_k(n)$ to binary bits to calculate total spare number. Please help me compare with Reed-Solomon method . I added an edit about spare number in my question. Best Regards $\endgroup$ – Mathlover Apr 27 '18 at 6:53
  • $\begingroup$ @MikeEarnest Hi Mike , I have asked a question in mathoverflow that is related to this question. Thanks a lot for help and advice. mathoverflow.net/questions/301360/… $\endgroup$ – Mathlover May 29 '18 at 11:47

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.