Erasure resilient (10,3) checksum codes
Emin Gabrielyan
emin.gabrielyan@{epfl.ch, switzernet.com}
Given is the problem:
- Packets of equal length divisible by 3 (minimum 3 bit)
- 3 information packets
- 7 redundant packets
- Information must be restored upon successful reception of any of three packets out of 10
How to construct:
Let (a,b,c) be the first packet, where a, b and c represent the first, second and third portions of the packet
Let (x,y,z) and (t,v,w) bet the second and third packets
A redundant packet is formed as follows:
where
(a,b,c)+(x,y,z)=(a+x,b+y,c+z)
Henceforth, operation + is an XOR
Each of 
, 
and 
is obtained by XOR-ing a subset from x, y and z (same is for 
, 
and 
). Thus the functions f
and g can be defined via 3 by 3
binary matrices.
Functions f and g are invertible, such that you can always
obtain (x,y,z) from 
and (t,v,w) from 
.
There are 168 invertible packets (or functions).
They are listed here with some IDs and we will further
refer to them by these IDs.
The codeword consists of three information packets (the code
is systematic) and a block of 7 distinct redundant packets. For each of 7
redundant packets we need to have a distinct pair of 
and 
functions:
(a,b,c) + 
(x,y,z) + 
(t,v,w)
(a,b,c) + 
(x,y,z) + 
(t,v,w)
…
(a,b,c)
+ 
(x,y,z)
+ 
(t,v,w)
The set of seven f (or g) functions has the following properties
, for any 
, where F is the
set of all 168 invertible packets
In 051027-erasure-9-2-resilient we obtained 192 different 7-member subsets satisfying this property: an XOR of two members is invertible. Let us denote the set of these 192 subsets of F as G.
Here is the list of these 192 subsets. Elements of the subsets are the IDs of the invertible functions.
Now let us analyze how the decoding works in a simple cases, when (x,y,z) is received with the following two redundant packets:
(a,b,c) + (x,y,z) + (t,v,w)
(a,b,c) + 
(x,y,z) + 
(t,v,w)
By XOR-ing the redundant packets we eliminate (a,b,c) and obtain:
(x,y,z) + (t,v,w) + (x,y,z) + (t,v,w)
Since (x,y,z)
is known, we compute (x,y,z)
+ (x,y,z)
and XOR it with the previous result, obtaining:
(t,v,w)
+(t,v,w)
Since, by the choice of the 7-member subset(t,v,w)
+(t,v,w)
is invertible we can obtain (t,v,w),
then (t,v,w)
or (t,v,w)
and then by using one of the redundant packets finally (a,b,c).
The same reasoning works when (t,v,w) is received with two redundant packets.
The case is obvious when we are receiving two information
packets with a redundant packet: (a,b,c)
+ (x,y,z)
+ (t,v,w),
since (a,b,c), (x,y,z)
and (t,v,w)
are all invertible.
It is more
complicated when (a,b,c)
is received with two redundant packets:
We have shown that by applying any inverse function to any other invertible packet we obtain always another invertible packet
if
( f(x,y,z)
) = (x,y,z)
where (x,y,z)
F
then
(t,v,w)
F
for any (t,v,w)F
F is the set of all 168 invertible packets
The block of redundant packets is represented by a pair of two 7-tuples
Where 
is one of the possible
192 members of G (such that+ is also in F, for
any ) and 
is any re-ordering of
a member of the same set G.
From all possible 
combinations (where
#(G)=192) the codeword can recover information when (a,b,c) survived with two redundant packets, only if:
G
If we received the following three packets:
(a,b,c)
(a,b,c)
+ (x,y,z)
+ (t,v,w)
(a,b,c) + (x,y,z) + (t,v,w)
We obtain these two:
(x,y,z)
+ (t,v,w)
(x,y,z) + (t,v,w)
Then these two:
(x,y,z) + (t,v,w) = (x,y,z) + (t,v,w)
(x,y,z) + (t,v,w) = (x,y,z) + (t,v,w)
Then this one:
(t,v,w)
+ (t,v,w)
And since
G
then
(t,v,w)
+ (t,v,w)
F
Therefore we can recover (t,v,w) and successively (x,y,z)
Assuming that =
=1 we obtained 152 pairs of 7-tuples (out of 46080 possible
candidates)
Satisfying the following constraint for successful decoding when (a,b,c) survives with any two redundant packets:
G
When receiving only
redundant packets …
Take (i,j,k) triplet from the 7 redundant packets and take two pairs from this triplet, e.g (i,j) and (i,k).
We can eliminate (a,b,c) composant and obtain these two packets:
(x,y,z) +(x,y,z) + (t,v,w) + (t,v,w)
(x,y,z) +
(x,y,z) + (t,v,w) + 
(t,v,w)
Since is in G (7-member subsets, such that the XOR
of any pair from it is invertible),
(x,y,z) +(x,y,z) and (x,y,z) +(x,y,z) are in F (162 invertibles)
Similarly
(t,v,w)
+ (t,v,w)
and (t,v,w)
+ (t,v,w)
are also in F
Thus
and 
are in F as well
If we find
Such that any triplet (i,j,k) contains a pair, e.g (i,j) and (i,k), such that
+ is in F, then we
have a (10,3)-code
(The two other possible pairs of the triplet are (i,j) and (j,k) or (i,k) and (j,k))
80 out of 152 candidates satisfied this triplet constraint
Pair of the following tuple:
11 73 140 167 198 292 323
With any of these 10 tuples
(11,140,198,73,292,323,167) (11,198,323,140,167,73,292)
(11,140,292,198,323,167,73) (11,292,167,198,73,323,140)
(11,167,73,323,140,198,292) (11,292,323,73,140,167,198)
(11,167,198,292,323,73,140) (11,323,73,292,167,140,198)
(11,198,292,323,73,140,167) (11,323,167,140,292,198,73)
Is an example of a (10,3)-code
(As everywhere, the numbers are IDs of invertible packets, from here)
All possible 80 pairs of tuples (always assuming that ==1) are given here
Note that we exceed the limit of Reed-Solomon code 
by 3 and the usual
limit of MDS codes 
by 1, since our
codeword can be as long as 10 packets, with s=3.
AMPL programs generating the examples
-
Step1
-
Step2
-
Step3
-
Data
* * *
Relevant links: