Suppose you have some storage medium of a given size M, and can make some kind of backup on another medium of size B with M > B. You can choose the scheme to determine the contents of the backup.


After you made that partial backup, an adversary (or a random process) will make a number of changes to your original medium. Given the changed medium and your partial backup, your task is to restore the original state of your medium. How many changes could you undo? What is the theoretical maximum? And how successful are the schemes you can come up with?


I have toyed with this question for a while. Obviously, in general you can not hope to undo more than B changes. Viewed more mathematical, I am looking for a systematic code that works with huge block sizes.



Partial backups
Your question is very similar to the extended idea of *erasure-resilient codes* discussed here:


[Y. M. Chee, C. J. Colbourn, A. C. H. Ling, *Asymptotically optimal erasure-resilient codes for large disk arrays,* Discrete Appl. Math. **102** (2000) 3–36](http://www.sciencedirect.com/science/article/pii/S0166218X99002280).


Originally, erasure-resilient codes were introduced for [RAID (redundant array of independent disks)](http://en.wikipedia.org/wiki/RAID) and similar storage systems. They are systematic codes, and Chee, Colbourn, and Ling's version is good for the type of problem you described. As is often the case with studies on reliability of storage, the focus of erasure-resilient codes is on data corruptions, unreadable bits, disk failure, and the like (which are all "erasures" in math) rather than bit flips. But if we forget about more practical issues and focus on math, erasures and bit flips can both be treated the same way by the notion of minimum distance, so here's some little things that are known about such codes in the math literature.


The idea is basically the same as systematic linear codes. For the sake of simplicity, we only consider the binary case here. Assume that we have a linear $[n,k,d]$ code of length $n$, dimension $k$, and minimum distance $d$. Here, the dimension $k$ and the number $n-k$ will be your $M$ and $B$ respectively. Because it's systematic, we use a parity-check matrix $H$ in standard form:


$$\begin{align\*}
H &= \left[\begin{array}{cc}I & A\end{array}\right]\\
 &= \left[\begin{array}{ccccccc}
1&0&\dots&0 & a\_{0,0} & a\_{0,1} & \dots &a\_{0,k-1}\\
0&1&\dots&0 & a\_{1,0} & a\_{1,1} & \dots &a\_{1,k-1}\\
\vdots&\vdots&\ddots&\vdots&&&\vdots&\\
0&0&\dots&1 & a\_{k-1,0} & a\_{k-1,1} & \dots &a\_{k-1,k-1}
\end{array}\right]
\end{align\*},$$


where $I$ is the $(n-k)\times(n-k)$ identity matrix and $A = (a\_{i,j})$ is a $k \times k$ matrix with $a\_{i,j} \in \mathbb{F}\_2$. The rows of $H$ are indexed by the $n-k$ bits for "some kind of backup" in your question (or any kind of storage medium of size $B = n-k$ for that matter) and columns of $A$ are indexed by the $k$ data bits we want to protect (i.e., the original data of size $M = k$).


The backup scheme is that on the $i$th backup bit, we write the sum of the data bits according to whether $a\_{i,j}$ is $0$ ("ignore") or $1$ ("add"), so that the $i$th backup bit $\beta\_i$ is


$$\beta\_i = \sum\_{x \in \{j \ \mid\ a\_{i,j} = 1\} } \delta\_x \pmod{2},$$


where $\delta\_j$ is the $j$th unreliable data bit we are going to protect.


It is straightforward to see that the standard syndrome decoding will detect errors on $\delta\_i$ as long as the number of affected data bits are fewer than or equal to $\lfloor\frac{d-1}{2}\rfloor$; we just compare each $\beta\_i$ with the sum of the corresponding data bits and see if they add up, which will give us the error syndrome.


Now, we have the assumption that the backups $\beta\_i$ are more reliable than the original data $\delta\_j$. (Chee, Colbourn, and Ling's view is a bit different. But in situations we consider, both views coincide.) In your case, all $\beta\_i$ are assumed to be immune to errors.


The question is whether we can correct more than $\lfloor\frac{d-1}{2}\rfloor$ errors if $\beta\_i$ are all reliable. In general, the answer should be yes. So, your question boils down to how much this assumption can increase the maximum number of tolerable errors and how we can construct systematic linear codes that take full advantage of the reliable backups.


Unfortunately, these questions appear to be open in general. Basically, we need to understand how the minimum distance changes when the $n-k$ check bits of systematic linear $[n,k,d]$ codes are chopped off to form new non-systematic linear codes of length $k$. But it can be proved that some nice combinatorial structure, when used as the $A$ part, roughly doubles the minimum distance compared to when $\beta\_i$ can be erroneous while having a huge block size as you requested. For instance, the following paper proved that the incidence matries of the Steiner $2$-designs forming the points and lines of affine geometry $\text{AG}(m,q)$ with $q$ odd are of this "almost doubling" kind:


[M. Müller, M. Jimbo, *Erasure-resilient codes from affine spaces,* Discrete Appl. Math., **143** (2004) 292–297.](http://www.sciencedirect.com/science/article/pii/S0166218X04000484)


The code parameters in the case of affine geometry $\text{AG}(m,q)$ with $q$ odd and $m \geq 2$ is


$$\begin{align\*}
n &= q^{m-1}\frac{q^m-1}{q-1}+q^m,\\
k &= q^{m-1}\frac{q^m-1}{q-1},\\
d' &= 2q\ \quad \text{ if backups are reliable},\\
(d &= q+1\ \text{ if backups are as unreliable}).
\end{align\*}$$


Actually, their assumption is slightly more pessimistic in the sense that $\beta\_i$ are "less prone" to errors, not completely reliable like your case. So they proved something stronger than the almost doubled minimum distance. In fact, their codes are asymptotically optimal under the pessimistic assumption as well as one more assumption that the column weights of $A$ are assumed to be uniform $w$ (which happens to be a reasonable thing to assume for the original, main intended purpose of erasure-resilient codes). Note that such $H = \left[\begin{array}{cc}I & A\end{array}\right]$ can be of minimum distance at most $d = w+1$ because a column of $A$ and a set of $w$ columns from $I$ can form a linearly dependent set. All else being equal, such error patters are much less likely than those that involve fewer backup bits. (And in the case of perfectly reliable backups, they don't happen.)


As in your question, let $B$ be the number of backup bits. Assume that we require our erasure-resilient code to detect all errors on $d'-1$ bits or fewer except the very unlikely ones that involve one data bit and $w=d+1$ backups. Define $\text{ex}(B,d,d')$ to be the maximum number of data bits for such an erasure-resilient code. Chee, Colbourn, and Ling proved that


$$\text{ex}(B,d,d') \leq c\cdot B^{d-\lfloor\frac{d'-1}{2}\rfloor}$$


for some constant $c$. Because codes from $\text{AG}(m,q)$ is of uniform column weight $q$, they asymptotically attain the upper bound on the block size $c\cdot B^2$.


A friend of mine proved the same thing for projective geometry, although it's not published yet. (If you're curious about the exact statement, you can find it in the language of design theory as Theorem 3.16 in our preprint <http://arxiv.org/pdf/1309.5587.pdf>)


So, while the case of completely reliable backups doesn't seem to have directly been studied, there are similar studies that give infinitely many examples of codes that significantly improve error correction capabilities when backup data are free from errors. And they are designed to support extremely large numbers of data bits, which translates to huge block sizes as requested. But constructions for codes and general bounds on improved minimum distance $d'$ for when backup bits $\beta\_i$ are perfectly reliable seem to be wide open.


