Erasure resilient (10,7) code
Given are:
- packets of identical size, divisible by 3, minimum 3 bits
- 7 information packets
- 3 redundant packets
- Information must be recovered upon a loss of any three packets out of 10
First redundant packet is the XOR of all 7 information packets
The second redundant packet is:
and the third is
where the summation is done by XOR operation, 
is the i-th packet and 
, 
and 
are its first, second
and third portions (remember that the packet size is divisible by 3).
f and g functions applied to (x,y,z) produce derivative packets of the same size, whose first, second and third components are XOR results of various subsets of {x,y,z}. Thus these functions can be represented via 3 by 3 matrices.
Additionally all f anf g functions are invertible and applied to (x,y,z) produce invertible packets. There are 168 invertible packets and functions.
In case of a loss of two
information packets i, j and the g-redundant packet we can restore 
if 
is invertible for any 
, where operation + is XOR.
The same reasoning is valid in case of the lost of two information packets and the f-redundant packet.
There are 192 various max-cliques each consisting of 7 packets satisfying this condition. Thus particular f and g sequences of functions must be chosen from this set.
We have 
possibilities to make
pairs of f and g. We are limiting our choice by f and g pairs, such that 
and we are examining 
possibilities.
In case of a loss of two information packets i, j and the first redundant packet, we must restore the information using the following f-redundant and g-redundant packets (after extraction of components of all received packets):
+
+
From these two packets we can obtain this one
+
and if it is invertible, then we
can restore and successively
Among combinations of f and g there are only 152 pairs of f and g for which the above condition holds for any .
It remains to examine the
situation when three information packets are lost and we have to restore them from the three redundant packets.
For any triplet (i,j,k) 
of lost information
packets we extract the following packets from the three received redundant
packets
++
++
++
From these three packets we can obtain these two:
++
+
++
+
or differently said:
(
+1)+ (
+1)
(
+1)+ (
+1)
and from these two we can obtain
+
and if it is invertible we obtain
and consecutively and
From 152 pairs of f and g we found 80 pairs satisfying the above constraint of triplets.
AMPL programs:
- step 1
- step 2
- data
* * *
© 2005, Switzernet (www.switzernet.com)
Relevant links: