Erausre resulient (9,7)-code
Given are:
- packets of identical size, divisible by 3, minimum 3 bits
- 7 information packets
- 2 redundant packets
- Reception of any 7 packets must restore the information
Let the information packets be
…
where 
, 
and 
are the first, second and third portions of the same packet
The first redundant packet is a simple XOR checksum of all information packets
where the summation is by XOR
The second redundant packet is:
where 
, such that 
, 
and 
are XOR results of
some combinations of x, y and z and thus f can be
represented by a 3 by 3 binary matrix.
Any 
is invertible, i.e.
there exists 
, such that 
.
There are 168 invertible functions and thus invertible 
packets (see here).
The case is obvious, if we have lost one information with one redundant packet.
If we have lost two information packets i and j then from the redundant packets we can obtain these two packets:
+
+
The second one can be transformed to
+
Note that is also invertible for any i and j
By XOR-ing the two packets we obtain
+
And if the result is invertible then we can restore and consecutively also
Thus we need to chose the set of f functions such that the following is ensured:
if 
F and F
then +1F
For all elements of F we can built a set of pairs E such that if fF, gF and 
gF, then (f , g)E. Thus we have a
graph G(F,E). The size of the max
clique of G is the length of the
maximal codeword minus 2.
The max-clique size is 7, thus we can construct (9,7)-code with this method.
Here is a corresponding AMPL program and data. The max-clique here is the same as the one needed for the construction of (9,2)-code.
* * *
© 2005, Switzernet (www.switzernet.com)
Relevant links: