Chapter 2
The Basic “Data Recovery Problem”
In this chapter, we introduce a basic Data Recovery Problem. The content include:
1. We first introduce a basic Parity Code, which can correct one erasure. 2. We then introduce an EVENODD code, which can correct two erasures. 3. We then formally define the basic “Data Recovery Problem”.
2.1 Story 1: Parity Code and XOR Operation
For bits, we can define an XOR operation ⊕ as follows: 0⊕0=0, 0⊕1=1, 1⊕0=1, 1⊕1=0
Now consider m bits (b0 , b1 , · · · , bm−1 ), which are stored in a computer. Sometimes a stored bit can be erased, which means that we can no longer read the bit, although we know the bit exists. We can represent an erased bit by the symbol ×.
Example 1 Assume m = 5 and (b0,b1,··· ,bm−1) = (1,0,1,0,1). If the bit b1 is erased, the bit sequence becomes (1, ×, 1, 0, 1).
Obviously, once a bit is erased, we cannot recover it unless there is some kind of “protection mechanism”. One such method is to use a Parity Code. In a Parity Code, given a bit sequence (b0, b1, · · · , bm−1), we add a new bit
m!−1 i=0
bm =b0 ⊕b1 ⊕···⊕bm−1 = 2
bi
to make it a longer sequence (b0, b1, · · · , bm−1, bm). This longer sequence (b0,b1,··· ,bm−1,bm)
is called a codeword, where the firs”t m bits (b0 , b1 , · · · , bm−1 ) are called infor- mation bits and the last bit bm = m−1 bi is called the parity bit (also called
parity-check bit).
Given a Parity Code, if a bit is erased, we can recover it using the remaining
bits in the codeword, because the erased bit always equals the XOR of the remaining bits.
i=0
And the Parity Code”codeword is (b0, b1, · · · , bm) = (1, 0, 1, 0, 1, 1).
i=0
Example 2 Assume m”= 5 and (b0,b1,··· ,bm−1) = (1,0,1,0,1). Then the paritybitisbm =b5 = m−1bi =b0⊕b1⊕b2⊕b3⊕b4 =1⊕0⊕1⊕0⊕1=1.
If the bit b1 is erased, the codeword becomes (1, ×, 1, 0, 1, 1). We can recover b1 correctly as b1 = 0≤i≤m,i∕=1 = b0 ⊕b2 ⊕b3 ⊕b4 ⊕b5 = 1⊕1⊕0⊕1⊕1 = 0, which is correct. We can now store the value b1 = 0 again in the computer, and the erased bit b1 is now restored.
The Parity-Code has an Encoding Algorithm and a Decoding Algorithm, as described below.
2.1.1 Encoding Algorithm of Parity Code
In the Encoding Algorithm, given the m information bits b0, b1, · · · , bm−1, we need to determine the value of the parity-bit bm. That is, for the Encoding Algorithm, its input is the m information bits b0 , b1 , · · · , bm−1 , and its output is the value of the parity-bit bm.
The Parity Code has a simple Encoding Algorithm:
• Given the input bits b0,b1,··· ,bm−1, we return bm as
m!−1 bm= bi
i=0
2.1.2 Decoding Algorithm of Parity Code for One Erasure
In the Decoding Algorithm, given a codeword whose bit bi has been erased
(where 0 ≤ i ≤ m):
(b0,··· ,bi−1,×,bi+1,··· ,bm)
we need to determine the value of the erased bit bi. That is, for the Decoding Algorithm, its input is the codeword (b0, · · · , bi−1, ×, bi+1, · · · , bm) with one erasure, and its output is the value of the erased bit bi.
The Parity Code has a simple Decoding Algorithm:
• Given the codeword (b0, · · · , bi−1, ×!, bi+1, · · · , bm) with one erasure, we return bi as
bi = bj 0≤j ≤m,j ∕=i
3
2.2 Story 2: Store Bit-Vectors and Correct Two Erasures
In the previous section, an erasure erased one bit at a time. Now consider the case where an erasure erased a bit vector (a sequence of bits) at a time.
Consider m computers in a network, where each computer stores k bits. For j = 0,1,··· ,m−1, let the k bits stored in the j-th computer be denoted by the
column vector
A=$a1,j ‘
which we also call the j-th bit-vector (or the bit-vector stored in the j-th com- puter).
Example 3 Assume m = 5 and k = 4. Then we have these 5 bit-vectors stored in the 5 computers, respectively:
#$ a 0 , 0 &’ #$ a 0 , 1 &’ #$ a 0 , 2 &’ #$ a 0 , 3 &’ #$ a 0 , 4 &’ A0 =$% a1,0 ‘(,A1 =$% a1,1 ‘(,A2 =$% a1,2 ‘(,A3 =$% a1,3 ‘(,A4 =$% a1,4 ‘(
a2,0 a2,1 a2,2 a2,3 a2,4 a3,0 a3,1 a3,2 a3,3 a3,4
When a computer loses its data, the whole bit-vector stored in it is lost. We call this event an erasure (or node erasure since we can see the computer as a node in the network), and say the corresponding bit-vector has been erased. We can represent an erased bit-vector by
#$ × &’ $% . ‘( ×
#$ a0,j &’
j % . ( ak−1,j
Example4 Assumem=5,k=4and
#$ 10 &’ #$ 01 &’ #$ 1 1 &’ #$ 10 &’ #$ 0 0 &’
A 0 = $% 1 ‘( , A 1 = $% 1 ‘( , A 2 = $% 0 ‘( , A 3 = $% 0 ‘( , A 4 = $% 0 ‘( 01011
If the bit-vector A1 is erased, the sequence of bit-vectors becomes
#$ 10 &’ #$ × × &’ #$ 1 1 &’ #$ 10 &’ #$ 0 0 &’
A 0 = $% 1 ‘( , A 1 = $% × ‘( , A 2 = $% 0 ‘( , A 3 = $% 0 ‘( , A 4 = $% 0 ‘( 0×011
4
Obviously, once a bit-vector is erased, we cannot recover it unless there is some kind of “protection mechanism”. One such method is to use a code that can correct erasures of bit-vectors. If the worst-case scenario is to have one bit- vector erased (namely, we lose one computer), then we can use a Parity-Code (same as before, except that the XOR operation is performed on the bit-vectors instead of on bits).
The worst-case scenario, however, can be worse. Sometimes we may lose two computers at the same time. If this is the worst-case scenario, then we need a code that can correct two erasures. In the following, we show such a code.
2.2.1 Encoding Algorithm for A Code that Corrects Two Erasures
The code we will introduce has a nice name: EVENODD code. Given m bit- vectors A0, A1, · · · , Am−1, it will add two new bit-vectors (called parity-check bit-vectors)
#$ a0,m &’ #$ a0,m+1 &’ A =$ a1,m ‘ andA =$ a1,m+1 ‘
m % . ( m+1 % . ( ak−1,m ak−1,m+1
So together the codeword becomes
#$ a0,0 &’ #$ a0,1 &’ #$ a0,m+1 &’ A =$ a1,0 ‘,A =$ a1,1 ‘,···,A =$ a1,m+1 ‘
0 % . ( 1 % . ( m+1 % . ( ak−1,0 ak−1,1 ak−1,m+1
or equivalently (where we put all the bit-vectors together to form a two-dimensional array) the codeword:
#$
$ $%
a0,m+1 &’ a1,m+1 ‘ . . . ‘(
ak−1,1
#$ 10 &’ #$ 01 &’ #$ 1 1 &’ #$ 10 &’ #$ 0 0 &’
01011
then by the EVENODD code’s Encoding Algorithm (which we will introduce
5
a0,0 a1,0 . . .
a0,1 a1,1 . . .
· · · · · ·
. . .
a0,m−1 a1,m−1 . . .
a0,m a1,m . . .
ak−1,0
Example5 Letm=5andk=4. Supposethat
ak−1,m+1
· · ·
ak−1,m−1
A 0 = $% 1 ‘( , A 1 = $% 1 ‘( , A 2 = $% 0 ‘( , A 3 = $% 0 ‘( , A 4 = $% 0 ‘(
ak−1,m
below), it will add two parity-check bit-vectors
#$ 10 &’ #$ 0 0 &’ A 5 = $% 0 ‘( , A 6 = $% 1 ‘(
10
and the whole codeword, which has m + 2 = 7 bit-vectors, becomes
#$ 1 0 1 1 0 1 0 &’ $% 0 1 1 0 0 0 0 ‘( 1100001 0101110
We now introduce the Encoding Algorithm of the EVENODD code. The code works when m is a prime number and k = m − 1.
In its Encoding Algorithm, given the m bit-vectors A0, A1, ···, Am−1, we need to determine the value of the two parity-check bit-vectors Am and Am+1. Here is how to do it:
1. Let am−1,0 = am−1,1 = · · · = am−1,m−1 = 0. And we define the modulo function 〈n〉m as follows: 〈n〉m = j if and only if j ≡ n(mod m) and 0≤j≤m−1. (Forexample,〈7〉5 =2and〈−2〉5 =3.)
2. Let
S =
3. For l = 0, 1, · · · , m−2, the two l-th bits of the two parity-check bit-vectors
are obtained as follows:
al,m+1 = S ⊕
Example6 Letm=5andk=m−1=4. Supposethat
m!−1 t=1
am−1−t,t
al,m =
m!−1 t=0
a〈l−t〉m,t
#$ 10 &’ #$ 01 &’ #$ 1 1 &’ #$ 10 &’ #$ 0 0 &’
Now let’s use the Encoding Algorithm to obtain the parity-check bit-vectors Am and Am+1.
6
A 0 = $% 1 ‘( , A 1 = $% 1 ‘( , A 2 = $% 0 ‘( , A 3 = $% 0 ‘( , A 4 = $% 0 ‘( 01011
al,t
)! *
m−1 t=0
First, let’s combine the m = 5 bit-vectors A0, A1, A2, A3 and A4 (which are column vectors) into a 2-dimensional array, and then append an all-0 row
(am−1,0, am−1,1, am−1,2, am−1,3, am−1,4) = (a4,0, a4,1, a4,2, a4,3, a4,4) = (0, 0, 0, 0, 0)
below the array, to get a m × m array:
#$ a 0 , 0 a0,1 a0,2
$a1,0 a1,1 a1,2
&’#$10110&’
a0,3 a0,4 a1,3 a1,4 a2,3 a2,4
‘ $0 1 1 0 0’ = 11000
I= a2,0 a2,1 a2,2
$% a ” a a a a ‘( $% 0 1 0 1 1 ‘(
3,0 3,1 3,2 a4,0 a4,1 a4,2
3,3 3,4 a4,3 a4,4
00000
m−1 am−1−t,t = a3,1 ⊕a2,2 ⊕a1,3 ⊕a0,4 = 1. Note that S is
Next, let S =
the XOR of the red bits in the following array (note that a4,0 = 0, so it is OK for us to include it in the XOR, too):
t=1
a0,1 a1,1 a 2 , 1 a3,1 a4,1
0,5
⊕m−1a =a ⊕a ⊕a ⊕a ⊕a =1,anda =S⊕ ⊕m−1a =
1 ⊕ (a〈0〉5,0 ⊕ a〈−1〉5,1 ⊕ a〈−2〉5,2 ⊕ a〈−3〉5,3 ⊕ a〈−4〉5,4) = 1 ⊕ (a0,0 ⊕ a4,1 ⊕ a3,2 ⊕ a2,3 ⊕ a1,4) = 0. Note that a0,5 is the XOR of the blue bits in the following array:
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,2 a1,2 a 2 , 2 a3,2 a4,2
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 a1,4 a 2 , 4 a3,4 a4,4
&’ #$ 1 0 11 0 &’
‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
00000
Let us now compute a and a . By the Encoding Algorithm, a =
0,6
t=0 0,t 0,0 0,1 0,2 0,3 0,4 0,6 t=0 〈0−t〉m,t
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,1 a1,1 a 2 , 1 a3,1 a4,1
a0,2 a1,2 a 2 , 2 a3,2 a4,2
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 a1,4 a 2 , 4 a3,4 a4,4
&’#$1 0 11 0 &’
‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
00000
0,5 +,
and a0,6 is the XOR of the red
with wrapping around) in the following array:
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,1 a1,1 a 2 , 1 a3,1 a4,1
&’#$1 0 11 0 &’
‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
a0,2 a1,2 a 2 , 2 a3,2 a4,2
#$ a 0 , 0 a 0 , 1 a 0 , 2 a 0 , 3 a 0 , 4 a 0 , 5 C=$% a1,0 a1,1 a1,2 a1,3 a1,4
a2,0 a2,1 a2,2 a2,3 a2,4
a3,0 a3,1 a3,2 a3,3 a3,4
7
and green bits (which form two diagonal lines,
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 a1,4 a 2 , 4 a3,4 a4,4
00000
Now that we know a0,5 = 1 and a0,6 = 0, we can “fill out” part of the final
codeword C as follows:
a 0 , 6
&’ #$ 1 0 1 1 0 1
‘(=$% 0 1 1 0 0 11000 01011
0 &’ ‘(
Let us continue, to find out the values of a1,5 and a1,6.
By the Encoding Algorithm, a = ⊕m−1a = a m−1 1,5 t=0 1,t
⊕a
⊕a
⊕a
⊕a = 1,4
+,
1,0
1,1
1,2
1,3
0,anda1,6 =S⊕ ⊕t=0 a〈1−t〉m,t =1⊕(a〈1〉5,0⊕a〈0〉5,1⊕a〈−1〉5,2⊕a〈−2〉5,3⊕ a〈−3〉5,4) = 1⊕(a1,0 ⊕a0,1 ⊕a4,2 ⊕a3,3 ⊕a2,4) = 0. Note that a1,5 is the XOR of the blue bits in the following array:
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,1 a1,1 a 2 , 1 a3,1 a4,1
a0,2 a1,2 a 2 , 2 a3,2 a4,2
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 a1,4 a 2 , 4 a3,4 a4,4
&’ #$ 1 0 11 0 &’
‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
00000
and a1,6 is the XOR of the red
with wrapping around) in the following array:
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,1 a1,1 a 2 , 1 a3,1 a4,1
a0,2 a1,2 a 2 , 2 a3,2 a4,2
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 &’ #$ 1 0 11 0 &’ a1,4 ‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
and green bits (which form two diagonal lines,
a 2 , 4 a3,4 a4,4
Now that we know a1,5 codeword C as follows:
#$ a0,0 a0,1 a0,2 C = $% a1,0 a1,1 a1,2 a2,0 a2,1 a2,2 a3,0 a3,1 a3,2
00000
= 0 and a1,6 = 0, we can “fill out” part of the final
a 0 , 3 a 0 , 4 a 0 , 5 a 0 , 6 &’ #$ 1 0 1 1 0 1 0 &’
a 1 , 3 a 1 , 4 a 1 , 5 a 1 , 6 ‘( = $% 0 1 1 0 0 0 0 ‘( a2,3 a2,4 11000
a3,3 a3,4 01011
Let us continue, to find out the values of a2,5 and a2,6.
By the Encoding Algorithm, a +, m−1 2,5
= ⊕m−1a = a t=0 2,t
2,0
⊕a
2,1
⊕a
2,2
⊕a
2,3
⊕a = 2,4
= 1 ⊕ (a〈2〉5,0 ⊕ a〈1〉5,1 ⊕ a〈0〉5,2 ⊕ a〈−1〉5,3 ⊕
0, and a2,6 = S ⊕ ⊕t=0 a〈2−t〉m,t
a〈−2〉5,4) = 1⊕(a2,0 ⊕a1,1 ⊕a0,2 ⊕a4,3 ⊕a3,4) = 1. Note that a2,5 is the XOR of the blue bits in the following array:
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,1 a1,1 a 2 , 1 a3,1 a4,1
a0,2 a1,2 a 2 , 2 a3,2 a4,2
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 a1,4 a 2 , 4 a3,4 a4,4
&’ #$ 1 0 11 0 &’
‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
00000
and a2,6 is the XOR of the red
with wrapping around) in the following array:
#$ a 0 , 0
$a1,0 I = $% a 2 , 0 a3,0 a4,0
a0,1 a1,1 a 2 , 1 a3,1 a4,1
a0,2 a1,2 a 2 , 2 a3,2 a4,2
a0,3 a1,3 a 2 , 3 a3,3 a4,3
a0,4 &’ #$ 1 0 11 0 &’ a1,4 ‘ $0 1 1 0 0’ a 2 , 4 ‘( = $% 1 1 0 0 0 ‘( a3,4 01011 a4,4 00000
8
and green bits (which form two diagonal lines,
Now that we know a2,5 = 0 and a2,6 = 1, we can “fill out” part of the final codeword C as follows:
a0,4 a0,5 a0,6 &’ #$ 1011010&’
01011
#$ a0,0 a0,1 a0,2 a0,3 C = $% a1,0 a1,1 a1,2 a1,3
a1,4 a 1 , 5 a 1 , 6 ‘( = $% 0110000′( a2,0 a2,1 a2,2 a2,3 a2,4 a2,5 a2,6 1100001
a3,0 a3,1 a3,2 a3,3 a3,4
Let us continue, to find out the values of a3,5 and a3,6.
By the Encoding Algorithm, a +, m−1 3,5
= ⊕m−1a = a t=0 3,t
3,0
⊕a
3,1
⊕a
3,2
⊕a
3,3
⊕a = 3,4
#$a0,0a0,1
$a1,0 a1,1 I = $% a 2 , 0 a 2 , 1 a3,0 a3,1 a4,0 a4,1
a0,2 a0,3 a1,2 a1,3 a 2 , 2 a 2 , 3 a3,2 a3,3 a4,2 a4,3
a0,4 a1,4 a 2 , 4 a3,4 a4,4
&’ #$ 1 011 0 &’
‘ $0 1 1 0 0’
‘( = $% 1 1 0 0 0 ‘( 01011
00000
= 1 ⊕ (a〈3〉5,0 ⊕ a〈2〉5,1 ⊕ a〈1〉5,2 ⊕ a〈0〉5,3 ⊕
1, and a4,6 = S ⊕ ⊕t=0 a〈3−t〉m,t
a〈−1〉5,4) = 1⊕(a3,0 ⊕a2,1 ⊕a1,2 ⊕a0,3 ⊕a4,4) = 0. Note that a3,5 is the XOR of the blue bits in the following array:
and a3,6 is the XOR of the red and green bits (which form two diagonal lines, with wrapping around) in the following array:
#$a0,0a0,1
$a1,0 a1,1 I = $% a 2 , 0 a 2 , 1 a3,0 a3,1 a4,0 a4,1
a0,2 a0,3 a1,2 a1,3 a 2 , 2 a 2 , 3 a3,2 a3,3 a4,2 a4,3
a0,4 &’ #$ 1 011 0 &’ a1,4 ‘ $0 1 1 0 0′
00000
Now that we know a3,5 = 1 and a3,6 = 0, we can “fill out” part of the final
codeword C as follows:
#$ a0,0 a0,1 a0,2 a0,3 C = $% a1,0 a1,1 a1,2 a1,3 a2,0 a2,1 a2,2 a2,3 a3,0 a3,1 a3,2 a3,3
a0,4 a0,5 a0,6 &’ #$ 1011010&’
a1,4 a 1 , 5 a 1 , 6 ‘( = $% 0110000′( a2,4 a2,5 a2,6 1100001 a3,4 a3,5 a3,6 0101110
a 2 , 4 a3,4 a4,4
‘( = $% 1 1 0 0 0 ‘( 01011
That is it! We have encoded the information bits (the m = 5 bit-vectors) #$ 1 0 1 1 0 &’
(A0,A1,A2,A3,A4) = $% 0 1 1 0 0 ‘( 11000
01011
into a codeword of the EVENODD code:
#$ 1 0 1 1 0 1 0 &’ C = $% 0 1 1 0 0 0 0 ‘(
1100001 0101110
9
From the above example, I hope you have noticed some very interesting geometric patterns: every time we compute a parity-check bit, it is the XOR of some horizontal line or diagonal lines in the two-dimensional array (where diagonal line may “wrap around” in the two-dimensional array). This is im- portant: when we design an algorithm for a code, we always want to find some “patterns”, so that we can significantly reduce the solution space. (Otherwise, if we disregard patterns and use exhaustive search, the solution space will grow exponentially in the values of the input parameters.)
The EVENODD code can handle any two node erasures (namely, the loss of any two columns of the codeword C). We will show how to do it in the next subsection, which is the Decoding Algorithm.
2.2.2 Decoding Algorithm for A Code that Corrects Two Erasures
We now show the Decoding Algorithm of the EVENODD Code. Given m bit- vectors A0, A1, · · · , Am−1 (where each bit-vector has m − 1 bits, and m needs to be a prime number), the Encoding Algorithm has turned them into m + 2 bit-vectors A0, A1, ···, Am+1 (where each bit-vector still has m−1 bits). These m + 2 bit-vectors form a codeword
#$ a0,0 a0,1 · · · a0,m−1 a0,m a0,m+1 &’ C = $ a1,0 a1,1 · · · a1,m−1 a1,m a1,m+1 ‘ % . . … . . . (
am−2,0 am−2,1 · · · am−2,m−1 am−2,m am−2,m+1
where each bit-vector Ai (for i = 0,1,··· ,m + 1) is a column of the two- dimensional array C. We can store the m + 2 bit-vector on m + 2 computers. If any two computers lose their data (called two node erasures), we can use a Decoding Algorithm to recover the two lost bit-vectors. (If there is only one node erasure, the Decoding Algorithm can certainly also handle it.)
Before giving the actual Decoding Algorithm for correcting two erasures, let us give an example that illustrates the idea behind it.
Example 7 We again assume that m = 5, as in our previous examples. As- sume that we have the following two-dimensional array as our codeword C, in which column 0 and column 2 have been erased (lost):
#$ × 0 × 1 0 1 1 &’ C = $% × 1 × 0 0 0 1 ‘(
×1×0011 ×1×1100
This is the main case for the Decoding Algorithm: two columns storing infor- mation bits (instead of parity-check bits) have been erased. (The cases in which at least one of the two parity-check columns have been erased are special cases that are easier to handle.)
10
The first step is to find a diagonal line that contains only one erased bit, and start decoding from there. We immediately see that the red diagonal line in the following array contains only one erased bit (for convenience, we add the all-0 row used in the Encoding Algorithm back to the array):
#$ × 0 × 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% × 1 × 0 0 1 1 ‘(
×1×1100 00000
$ × 1 × 0 0 0 1 ‘ C = $% × 1 × 0 0 1 1 ‘(
If we know the XOR of all the bits in the above red diagonal line (which is called the Parity of those bits), then we can easily recover the erased bit in the line, just as we did for a Parity Code. Can we know that parity? Yes. From the Encoding Algorithm, it is not difficult to see that the Parity of the two parity- check bit-vectors (shown in green below) equals the Parity of the red diagonal line:
#$ × 0 × 1 0 1 1 &’
×1×1100 00000
So the Parity of the red diagonal line above is 1. So we know the erased bit in it must be 0. So we have the following codeword (with one erased bit recovered)
as:
Take a look at the red horizontal line above, whose Parity equals the green parity-check bit. The red horizontal line above has only one erased bit, so using the Parity, we know its value must be 0. So we have the following codeword (with one more erased bit recovered) as:
#$ × 0 × 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% 0 1 0 0 0 1 1 ‘(
×1×1100 00000
Take a look at the red diagonal lines and the cyan diagonal line above, whose Parity equals the green parity-check bit. The two red diagonal lines above have only one erased bit, so using the Parity, we know its value must be 0. So we
11
#$ × 0 × 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% × 1 0 0 0 1 1 ‘(
×1×1100 00000
have the following codeword (with one more erased bit recovered) as:
#$ × 0 0 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% 0 1 0 0 0 1 1 ‘(
×1×1100 00000
Take a look at the red horizontal line above, whose Parity equals the green parity-check bit. The red horizontal line above has only one erased bit, so using the Parity, we know its value must be 0. So we have the following codeword (with one more erased bit recovered) as:
#$ 0 0 0 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% 0 1 0 0 0 1 1 ‘(
×1×1100 00000
Take a look at the red diagonal lines and the cyan diagonal line above, whose Parity equals the green parity-check bit. The two red diagonal lines above have only one erased bit, so using the Parity, we know its value must be 0. So we have the following codeword (with one more erased bit recovered) as:
#$ 0 0 0 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% 0 1 0 0 0 1 1 ‘(
×101100 00000
Take a look at the red horizontal line above, whose Parity equals the green parity-check bit. The red horizontal line above has only one erased bit, so using the Parity, we know its value must be 1. So we have the following codeword (with one more erased bit recovered) as:
#$ 0 0 0 1 0 1 1 &’
$ × 1 × 0 0 0 1 ‘ C = $% 0 1 0 0 0 1 1 ‘(
1101100 00000
Take a look at the red diagonal lines and the cyan diagonal line above, whose Parity equals the green parity-check bit. The two red diagonal lines above have only one erased bit, so using the Parity, we know its value must be 0. So we have the following codeword (with one more erased bit recovered) as:
12
#$ 0 0 0 1 0 1 1 &’
$ × 1 0 0 0 0 1 ‘ C = $% 0 1 0 0 0 1 1 ‘(
1101100 00000
Take a look at the red horizontal line above, whose Parity equals the green parity-check bit. The red horizontal line above has only one erased bit, so using the Parity, we know its value must be 1. So we have the following codeword (with one more erased bit recovered) as:
#$ $
0 0 0 1 0 1 1 &’ 1 1 0 0 0 0 1 ‘ 0 1 0 0 0 1 1 ‘( 1101100 00000
C = $%
All the erasures have been corrected! We have successfully recovered the
original codeword:
#$ 0 0 0 1 0 1 1 &’ C = $% 1 1 0 0 0 0 1 ‘(
0100011 1101100
From the above example, we can see that the Decoding algorithm uses the following method repeatedly to correct more and more erased bits, until all erased bits are corrected:
• Each time, find a set of bits with two properties: (1) their parity is known; (2) they contain only one erased bit. We then use the method of Parity Code to correct this erased bit.
The above method is also called “Peeling Algorithm”, which is a basic method for correcting erasures.
We now formally present the Decoding Algorithm of the EVENODD algo- rithm. We include it to show you what a formal Decoding Algorithm may look like, and also for completeness of the results here. However, you do not need to remember it, because your project is not to design the EVENODD code again. You just need to know that it considers several different cases, and in each case, it uses the Peeling Algorithm (like the example shown above), or sometimes just the Encoding Algorithm, to recovered the erased bits. If you feel like skipping the following formal Decoding Algorithm, and jump directly to the next section, please go ahead.
Algorithm 1 (Two Erasure Decoding Algorithm of EVENODD Code): Con- sider the (m − 1) × (m + 2) array of bits ai,j , such that the last two columns
13
are the parity-check bits obtained using the Encoding Algorithm. If one column is erased, say column i, i ∕= m + 1, then it can be recovered using the XOR of columns l, 0 ≤ l ≤ m, l ∕= i. If column (m+1) is erased, then the bits can be recovered using the Encoding Algorithm.
Next, assume that columns i and j have been erased, where 0 ≤ i < j ≤ m+1. We have four cases:
1. i = m and j = m + 1. In this case, both parity-check bit-vectors have been erased. We can reconstruct them simply using the Encoding Algorithm.
2. i < m and j = m. In this case, one parity-check bit-vector and one infor- mation bit-vector have been erased. We can recover the i-th bit-vector as
follows: let
l=0
where we assume that am−1,l =0 for 0≤l≤m+1. Then,
)! *
m−1
S = a〈i−1〉m,m+1 ⊕ a〈i−l−1〉m,l ,
ap,i = S ⊕ a〈i−1〉m,m+1 ⊕ #% ! 0≤l≤m−1,l∕=i
a〈p+i−l〉m,l&( for0≤p≤m−2;andap,m (for0≤p≤m−2)canberecoveredusing
the Encoding Algorithm once the i-th bit-vector is recovered.
3. i < m and j = m + 1. In this case, one parity-check bit-vector and one information bit-vector have been erased. We can first recover the i-th bit- vector by seeing the first m+1 columns as a Parity Code, and then recover the (m + 1)-th bit vector using the Encoding Algorithm.
4. i < m and j < m. This is the main case. In this case, both erased columns contain information bits, and we cannot retrieve them using the parities separately, as in the previous three cases. We analyze this case in detail.
Assume that am−1,l = 0 for 0 ≤ l ≤ m − 1 and compute the diagonal parity S as follows:
)m−2 *)m−2 * S= !al,m ⊕ !al,m+1
l=0 l=0
(i.e., S is the XOR of the bits in columns m and m+1. Find the horizontal
syndromes
and the diagonal syndromes
S0 = S(0),S(0),··· ,S(0) 01 m−1
S(1) = S(1),S(1),··· ,S(1) 01 m−1
14
as follows: ! S(0) =
a
S(1)=S⊕a ⊕#% ! a &(
u
u,l
0≤l≤m,l∕=i,j
u u,m+1 〈u−l〉m ,l
0≤l≤m−1,l∕=i,j
where 0 ≤ u ≤ m−1. Next, we retrieve the bits in columns i and j as
follows:
(a) Set s←〈−(j−i)−1〉m and am−1,l ←0 for 0≤l≤m−1.
(1) (0)
(b) Let as,j ← S〈j+s〉m ⊕ a〈s+(j−i)〉m,i and as,i ← Ss ⊕ as,j.
(c) Set s←〈s−(j−i)〉m. If s=m−1 then stop, else go to step 2.
The EVENODD Code can correct two node erasures. Obviously, we can consider how to design a code that can correct 3 node erasures, 4 node erasures, and so on.
2.3 Formulation of Basic “Data Recovery Prob- lem”
In this section, we will formally define the basic “Data Recovery Problem” used in our project.
We have seen two data recovery schemes: the first scheme is a Parity Code, which can correct one erasure; and the second scheme is the EVENODD Code, which can correct two erasures. That is great! Now let us consider how the problem can be extended.
Assume there are n computers, and each Computer can store k bits, where k is a positive integer.
Let " < n be a positive integer. We assume that at most " computers can lose their data. (When a computer loses its data, all the k bits in it are erased, and we call it a node erasure, or just erasure.)
Assume that there are x information bits to store, and x < nk. Let us denote the x information bits by
B = (b0,b1,··· ,bx−1)
whereeachbi ∈{0,1}isabitfor0≤i≤x−1. (ThereforeB∈{0,1}x.)
We can define an Encoding Algorithm as follows. An Encoding Algorithm
maps the x information bits to a codeword
# a0,0 a0,1 ··· a0,n−1 & $ a1,0 a1,1 ··· a1,n−1 '
C = (A0,A1,··· ,An−1) = $ . . ... .
%a a .a (
k−1,0 k−1,1 k−1,n−1 15
'
whose i-th column (for 0 ≤ i ≤ n − 1) is
#$ a0,i &'
A=$a1,i ' i % . (
ak−1,i
is called the i-th bit vector. We require that the Encoding Algorithm uses only XOR operations. More specifically, for j = 0,1,··· ,n−1 and i = 0,1,··· ,k−1, the Encoding Algorithm chooses a subs!et Si,j ⊆ {0, 1, · · · , x − 1} and encodes the bit ai,j as
ai,j = bs s∈Si,j
We call it an XOR Encoding Algorithm. And we call the code an XOR Code. Note that both the Parity Code and the EVENODD Code are XOR Codes.
Our objective is to design an XOR Code (which consists of an Encoding Algorithm and a Decoding Algorithm) that can correct any " node erasures, and maximize x (the number of information bits we store) given that they satisfy the first condition (of being able to correcting any " node erasures). Formally, we can define the problem as follows:
• The Basic “Data Recovery Problem”:
Input: There are n computers, where each computer can store k bits. Let
" < n be a positive integer.
Output: An XOR Code that maximizes x (the number of information bits that are mapped to the codeword) and can correct any " node erasures for the codeword.
Again, note that when we design a code, we need both an Encoding Algo- rithm and a Decoding Algorithm.
16
Chapter 3
Extensions of the Basic “Data Recover Problem”
In this chapter, we introduce various extensions for the basic “Data Recovery Problem”. The content include:
1. Extension One: Computers with Unbalanced Storage Capacities
2. Extension Two: Bounded Rebuilding Cost for Single Node Erasure
3. Extension Three: Bounded Rebuilding Cost on Shortest Paths
4. Extension Four: Average Rebuilding Cost
5. Extension Five: Local Usage of Data
6. Extension Six: Recover Function of Data
7. Extension Seven: Unequal Protection
8. Extension Eight: Rateless Code
3.1 Extension One: Computers with Unbalanced Storage Capacities
In the basic “Data Recovery Problem”, we have assumed that every computer can store k bits (as a bit-vector). In reality, however, the storage capacity of different computers can be different. For example, in a 5G wireless network in a “smart home” setting, maybe a smart surveillance video recorder is able to store more data, but a smart weather-monitoring sensor can store less data. In this section, We will extend the basic “Data Recovery Problem” by assuming that computers may have unbalanced storage capacities.
17
Assume there are n computers, and for i = 0, 1, 2, ···, n−1, the Computer i can store ki bits, where ki is a positive integer.
Let " < n be a positive integer. We assume that at most " computers can lose their data. -n−1
Assume that there are x information bits to store, and x < i=0 ki. Let us denote the x information bits by
B = (b0,b1,··· ,bx−1)
whereeachbi ∈{0,1}isabitfor0≤i≤x−1. (ThereforeB∈{0,1}x.)
We can define an Encoding Algorithm as follows. An Encoding Algorithm
maps the x information bits to a codeword
# a0,0 a0,1 ··· a0,n−1 &
$ a1,0 a1,1 · · · a1,n−1 ' C = (A0,A1,··· ,An−1) = $ . . ... . '
%a a .a ( k0 −1,0 k1 −1,1 kn−1 −1,n−1
whose i-th column (for 0 ≤ i ≤ n − 1) is
#$ a0,i &'
A=$a1,i ' i % . (
aki −1,i
is called the i-th bit vector. Note that the n bit-vectors can have different lengths. We require that the Encoding Algorithm uses only XOR operations. More specifically, for j = 0,1,··· ,n − 1 and i = 0,1,··· ,kj − 1, the Encoding Algorithm chooses a subset Si,j ⊆ {0, 1,!· · · , x − 1} and encodes the bit ai,j as
ai,j = bs s∈Si,j
As before, we call it an XOR Encoding Algorithm. And we call the code an XOR Code.
Example 8 Assume n=3, k0 =1, k1 =2, k2 =3, x=3. Then the codeword
is
with
#% a0,0 a0,1 a0,2 &( C = a1,1 a1,2 a2,2
. a0,1 / A0 = (a0,0), A1 = a1,1 ,
18
= (A0, A1, A2)
A2 =
#% a0,2 &( a1,2 .
a2,2
Let the -n−1 ki subsets be i=0
S0,0 = {0} Then given the information bits
the codeword is
b1 ⊕ b2
For instance, if the x information bits are B = (1,0,1), then the Encoding
Algorithm will turn it into
#% 1 0 1 ⊕ 0 &( #% 1 0 1 &( C=11⊕1=10 0⊕1 1
In the following example, we illustrate how the small code in the example above can correct a node erasure.
Example 9 Assume " = 1. Following the previous example, let us assume that the column A1 is erased, so that the codeword becomes
#% 1 × 1 &( C=×0.
1
Then the Decoding Algorithm can first pick the equation a0,2 = b0 ⊕ b1 to recover
b1 =a0,2 ⊕b0 =1⊕1=0, and get
#% 1 0 1 &( C=×0.
1
It can then pick the equation a1,2 = b0 ⊕b2 to recover b2 = a1,2 ⊕b0 = 0⊕1 = 1,
and get
#% 1 0 1 &( C=10.
1
S0,1 = {1} S1,1 = {2}
S0,2 = {0,1} S1,2 = {0, 2} S2,2 = {1, 2}
B = (b0, b1, b2),
#% b 0 b 1 b 0 ⊕ b 1 &( C= b2b0⊕b2.
Our objective is to design an XOR Code (which consists of an Encoding Algorithm and a Decoding Algorithm) that can correct any " node erasures, and maximize x (the number of information bits we store) given that they satisfy the first condition (of being able to correcting any " node erasures). Formally, we can define the problem as follows:
19
• Data Recovery Problem with Unbalanced Storage Capacities: Input : There are n computers, where each computer i (for 0 ≤ i ≤ n − 1)
can store ki bits. Let " < n be a positive integer.
Output: An XOR Code that maximizes x (the number of information bits that are mapped to the codeword) and can correct any " node erasures for the codeword.
Clearly, the basic “Data Recovery Problem” is a special case of the above problem (with k0 = k1 = · · · = kn−1 = k).
3.2 Extension Two: Bounded Rebuilding Cost for Single Node Erasure
When we have a code that can correct " node erasures, we should notice that having “" node erasures” is just the worst-case scenario. In a computer network, a more likely case is to have one node erasure, and we can recover it in time before the second node erasure happens. We care about the cost of recovering the node erasure, especially if the network’s communication bandwidth is limited (such as for a wireless network). That motivates us to consider the following generalization of the basic “Data Recovery Problem”.
Assume there are n computers, where each computer can store k bits. As- sume there is an Encoding Algorithm that can map x information bits to a codeword
#$ a 0 , 0 a 0 , 1 · · · a 0 , n − 1 &' C=(A ,A ,···,A )=$ a1,0 a1,1 ··· a1,n−1 ',
0 1 n−1 % . . ... . ( ak−1,0 ak−1,1 · · · ak−1,n−1
where each column Ai is the bit-vector of k bits stored in computer i. As- sume there is a corresponding Decoding Algorithm that can correct any " node erasures, where " ≥ 1 is a positive integer.
Consider any node erasure that erased the i-th column Ai (for 0 ≤ i ≤ n−1). (Notice that here we are talking about only one node erasure, not " node erasures, even though the code is capable of correcting " node erasures.) Say that to recover Ai, the Decoding Algorithm needs to use the bit-vectors that are stored in ci other computers. We call ci the cost of recovering Ai. And we call
cmax =max{c0,c1,···,cn−1}
the rebuilding cost of the code for a single node erasure (or simply rebuilding cost).
20
Example 10 Consider the EVENODD Code example shown in Section 2.2, where m=5. The codeword has n=m+2=7 bit-vectors:
#$ 1 0 1 1 0 1 0 &' C = (A0,A1,A2,A3,A4,A5,A6) = $% 0 1 1 0 0 0 0 '(
IfanyAi iserased(for0≤i≤m),wecanusetheothermcolumns among {A0 , A1 , · · · , Am } to recover it, by simply taking their bit-wise XOR. For example, if A2 is erased and the codeword becomes
#$ 1 0 × 1 0 1 0 &' C = $% 0 1 × 0 0 0 0 '(
11×0001 01×1110
We can recover A2 as A2 = A0 ⊕A1 ⊕A3 ⊕A4 ⊕A5. So the cost ci of recovering Ai, for 0≤i≤m, is m.
If Am+1 is erased, we can recover it using the Encoding Algorithm since we know the values of A0, A1, · · · , Am−1. So the cost cm+1 of recovering Am+1 is also m.
Therefore, for EVENODD Code, the rebuilding cost cmax is m = n − 2.
We can generalize the basic “Data Recovery Problem” by adding a constraint on the rebuilding cost: let crebuild be a positive integer, and we can require that the rebuilding cost is at most crebuild. Formally, we can define the problem as follows:
• Data Recovery Problem with Bounded Rebuilding Cost
Input: There are n computers, where each computer can store k bits. Let
3.3
" < n and crebuild < n be two positive integers.
Output: An XOR Code that maximizes x (the number of information bits that are mapped to the codeword) and satisfy two conditions: (1) they can correct any " node erasures for the codeword; (2) the rebuilding cost is at most crebuild.
Extension Three: Bounded Rebuilding Cost on Shortest Paths
If the computers form a computer network (such as a multi-hop wireless net- work), the communication cost of transmitting a bit-vector from one computer to another computer depends not only on the size of the bit-vector, but also on how far away they are in the network. Let us formulate the notion as follows.
Let G = (V,E) be a directed graph, where each node in V represents a computer. Forconvenience,letV ={0,1,···,n−1},whereanyintegeri∈V denotes the i-th node in G (namely, it denotes computer i).
21
1100001 0101110
For any directed path in G, the length of the path is defined as the number of edges in that path. For any two nodes i ∈ V and j ∈ V , the minimum distance δ(i,j) is defined as the length of the shortest path from node i to node j. (If there does not exist any path from node i to node j, then δ(i, j) = ∞.) Notice that δ(i, j) and δ(j, i) are not necessarily equal.
Assume each of the n computers can store k bits. Assume there is an En- coding Algorithm that can map x information bits to a codeword
#$ a 0 , 0 a 0 , 1 · · · a 0 , n − 1 &' C=(A ,A ,···,A )=$ a1,0 a1,1 ··· a1,n−1 ',
0 1 n−1 % . . ... . ( ak−1,0 ak−1,1 · · · ak−1,n−1
where each column Ai is the bit-vector of k bits stored in computer i. As- sume there is a corresponding Decoding Algorithm that can correct any " node erasures, where " ≥ 1 is a positive integer.
Consider any node erasure that erased the i-th column Ai (for 0 ≤ i ≤ n−1). (Notice that here we are talking about only one node erasure, not " node erasures, even though the code is capable of correcting " node erasures.) Say that to recover Ai, the Decoding Algorithm needs to use the bit-vectors that are stored in the computers
Ci ⊆{0,1,···,i−1,i+1,···,n−1},
and transmit those bit-vectors to computer i (so that computer i can recover Ai using those received bit-vectors). In other words, computer i needs to retrieve the bit-vectors
{Aj |j∈Ci}
from |Ci| other computers to recover Ai. For any computer j ∈ Ci, it takes a path of length δ(j, i) to transmit the bit-vector Aj from computer j to computer i, and we consider that cost to be δ(j, i). So naturally, we call
ci = 0 δ(j,i) j ∈Ci
the cost of recovering Ai. And we call
cmax =max{c0,c1,···,cn−1}
the rebuilding cost of the code.
Example 11 Consider the EVENODD Code example shown in Section 2.2,
where m = 5. The codeword has m + 2 = 7 bit-vectors:
#$ 1 0 1 1 0 1 0 &'
C = (A0,A1,A2,A3,A4,A5,A6) = $% 0 1 1 0 0 0 0 '( 1100001
0101110 22
Figure 3.1: A directed graph G = (V,E) with n = 7 nodes, where each node stores a bit-vector.
Letn=m+2=7. AssumethatthegraphG=(V,E)isasshownin Fig.3.1. Fori=0,1,···,n−1,thenodeistoresthebit-vectorAi.
IfanyAi iserased(for0≤i≤m),wecanusetheothermcolumns among {A0 , A1 , · · · , Am } to recover it, by simply taking their bit-wise XOR. For example, if A2 is erased and the codeword becomes
#$ 1 0 × 1 0 1 0 &' C = $% 0 1 × 0 0 0 0 '(
11×0001 01×1110
We can recover A2 as A2 = A0 ⊕A1 ⊕A3 ⊕A4 ⊕A5. So the cost ci of recovering Ai, for 0≤i≤m, is:
1. If i = 0, c0 = δ(1, 0)+δ(2, 0)+δ(3, 0)+δ(4, 0)+δ(5, 0) = 1+2+3+4+5 = 15.
2. If i = 1, c1 = δ(0, 1)+δ(2, 1)+δ(3, 1)+δ(4, 1)+δ(5, 1) = 1+1+2+3+4 = 11.
3. In general, ci = -i−1 (i − j) + -m (j − i) = i(i+1) + (m−i)(m−i+1) for
0 ≤ i ≤ m.
If Am+1 is erased, we can recover it using the Encoding Algorithm since we know the values of A0, A1, · · · , Am−1. But there is actually a better way: we can use A1, A2, · · · , Am as well (which can give us A0 easily by taking their XOR)
to recover Am+1. So the cost of recovering Am+1 is cm+1 =1+2+···+m= m(m+1) .
2
Therefore, it is easy to see that for EVENODD Code placed as in Fig. 3.1, the rebuilding cost is cmax = m(m+1) .
2
The definition of rebuilding cost here generalizes that definition used in the “Extension Two: Data Recovery Problem with Bounded Rebuilding Cost”: we go back to that problem if G is a complete graph.
Let us formally define our problem here as follows:
• Data Recovery Problem with Bounded Rebuilding Cost on Short- est Paths
Input: There are n computers, where each computer can store k bits. The n computers form the nodes of a directed graph G = (V,E). Let " < n and crebuild be two positive integers.
23
j=0 j=i+1 2 2
3.4
Output: An XOR Code that maximizes x (the number of information bits that are mapped to the codeword) and satisfy two conditions: (1) they can correct any " node erasures for the codeword; (2) the rebuilding cost is at most crebuild. (Here the rebuilding cost is defined based on the directed graph G.)
Extension Four: Average Rebuilding Cost
In the problem “Extension Two: Data Recovery Problem with Bounded Re- building Cost”, we have defined the rebuilding cost as
cmax = max{c0, c1, · · · , cn−1},
which is the worst rebuilding cost over all the nodes.
We can consider an alternative: instead of considering the worst rebuilding
cost over all the nodes, we can consider the average rebuilding cost over all the nodes. Specifically, we can define the average rebuilding cost as
1 n0− 1 cavg = n ci.
i=0
We can generalize the basic “Data Recovery Problem” by adding a constraint on the average rebuilding cost: let crebuild be a positive real number, and we can require that the average rebuilding cost is at most crebuild. Formally, we can define the problem as follows:
• Data Recovery Problem with Bounded Average Rebuilding Cost Input: There are n computers, where each computer can store k bits. Let
3.5
" < n be a positive integer, and let crebuild < n be a positive real number.
Output: An XOR Code that maximizes x (the number of information bits that are mapped to the codeword) and satisfy two conditions: (1) they can correct any " node erasures for the codeword; (2) the average rebuilding cost cavg is at most crebuild.
Extension Five: Local Usage of Data
So far we have discussed how computers collaborate to protect data. We have not yet discussed how computers use the data. While the data might be useful for all computers, it is also possible that each computer uses only its own data, and the collaborative erasure-correction method is only used to protect their data more effectively. In this case, we need to think how to balance two factors simultaneously: efficient data usage, and efficient data recovery.
Assume there are n computers, each of which has collected x bits of data for its own use. (That is, no computer really needs to use any data collected by other computers.) Each computer can store k bits (with k > x). Therefore,
24
each computer can use the k − x bits of extra storage capacity it has for a joint Data Recovery Scheme.
For j = 0, 1, · · · , n − 1, let
# b0,j & $ b1,j ‘ $ . ‘
$ bx−1,j ‘ Aj = $ a0,j ‘
$ a1,j ‘ % . (
ak−x−1,j
be the bit-vector of k bits stored on computer i. Here the top x bits
#$ b0,j &’ $ b1,j ‘ $% . ‘(
bx−1,j
are the data (called information bits) that the computer i has collected itself for its own uses (namely, no other computer needs to use it), and the bottom
ak−x−1,j
are the parity-check bits that the computer i uses for jointly protecting its own data and other computers’ data from node erasures. Specifically, let B = {bi,j |0≤i