Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
This question differs from the ones I've seen discussed in coding theory, because you're given that errors can be introduced only into the original medium, not into the backup. (Note that I wrote "I've seen" --- there's plenty of coding theory that I haven't seen, and questions like this may well have been treated there.) –  Andreas Blass May 24 '12 at 18:31
1  
I would start calculations based on Reed-Solomon code, but it has the following obvious drawbacks: 1) it will correct data only in chunks that are multiples of the size of the field element (=symbol), 2) the larger the total package M+B, the larger will the symbols have to be: with $r$ bit symbols the maximum size of M+B is $r\cdot 2^r$ bits, 3) the amount of corrupted data is counted in terms of the affected symbols, so if the adversary changes a single bit of a symbol, the entire symbol is corrupted, 4) it won't take advantage of the fact that the errors are all in the original. –  Jyrki Lahtonen May 24 '12 at 19:25
1  
...(continue, sorry). So I would like to know a little bit more about what kind of errors the adversary will be able to induce. Do we know anything about that? Will the adversary like make a pass with a magnet over your storage medium (in which case we might reasonably assume that contiguous blocks of data will be affected). A scheme based on an RS-code has the big plus side that with $R=B/r$ check symbols we can correct up to $R/2$ corrupted symbols. You can double this number, if (a big if, but again something I need to ask) we know the locations of the changes. –  Jyrki Lahtonen May 24 '12 at 19:31
1  
...(continue, sorry^2). How large can we expect M+B to be? Are we talking kilobytes, megabytes or gigabytes? At some point the granularity of RS-codes may become an issue. Another idea that comes to mind is to "waste" some of the storage space of the original copy by adding 32-bit CRCs to chunks of data (or some error-detection scheme like that). Then we can encode/decode on a chunk-by-chunk basis, and we shall automatically know which chunks are corrupted (in which case R extra chunks in B allow the recovery of R corrupted chunks in M). But again, a single flipped bit will ruin a chunk. –  Jyrki Lahtonen May 24 '12 at 19:41
2  
Without some restrictions on the backup, it seems to be a red herring. You want to be able to extract some number of bits out of $M$, a standard problem. If you can store $B$ bits reliably in the backup, this lowers the number of bits you need to store in the medium by $B$. –  Douglas Zare May 24 '12 at 20:43

1 Answer 1

up vote 2 down vote accepted

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.

Originally, erasure-resilient codes were introduced for RAID (redundant array of independent disks) 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.

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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