Efficiency of transmitting checksum
packets for some pairs from the set of original packets
We are comparing the decoding efficiency of three simple methods adding redundant packets to the set of original packets.
Given are 9 original packets
- in the first method we transmit with each original packet two copies of the same packet, i.e. in total 27 packets are transmitted
- in the second method we align the 9 packets sequentially, one after the other; we add at the ends of the sequence a pair of heading and trailing packets (the heading and trailing packets are any two packets known for the sender and receiver); for each two neighbors in the extended sequence (10 neighbors) we produce two redundant packets using a RS(4,2) code; therefore we transmit in total 29 packets
- in the third method we place the nine packets in a 3x3 matrix rolled around at the edges (i.e. in a torus); each packet has four neighbors; for each pair of neighbors (18 in total) we send a redundant packet – the XOR packet of the neighbors; thus in total we transmit 27 packets
We compute for each three methods the probability of restoring the original 9 packets from 9 to 27 available (randomly chosen) packets. The results are presented in the below chart.
(see the excel file)
From the compared three methods, obviously the one which simply sends duplicates is the worst. After collecting 23 packets, in this method, there is still a noticeable probability of not being able to restore the original 9 packets. The best one is the torus method, whose curve approaches to 100% faster of all.
The success probability of the first method, sending two copies for each original packet, is computed by a combinatorial method (see a C program text and the data).
The success probability of the second method, sending two redundant RS(4,2) packets for every two successive original packets, is also computed by a combinatorial method (see the recursive algorithm in C program text; see in an excel file the comparison with the previous method). About RS redundant packets see at the end of the page. The heading and trailing packets of this method do not bring to the decoding any specific improvement; they are added to simplify our particular combinatorial algorithm for computing the probabilities.
The success probabilities of the third method (the torus method with 9 original packets and 18 redundant packets) are computed via a synthetic simulation. We generated 30 million random samples of subsets for forming the decoding probability curve (see a C program text).
* * *
About RS packets:
for a pair of original packets we can generate a number of redundant packets,
such that the original pair of packets can be recovered from any two redundant
packets, or from any one redundant packet together with any one original packet.
Example: let a be the first packet
and b be the second packet; let us
split the packets in two halves, such that 
and 
; the three redundant packets satisfying the above conditions
are: 
, 
and 
. If the packet can be divided into two halves (it must have
at least 2 bits) there are at most three such redundant packets. If the packet
is divisible by 3 there can be 7 such redundant packets. See an AMPL script for building the redundant packets.
* * *
Examples of construction of simple erasure resilient codes (Generalized Reed Solomon codes)
[051025-erasure-resilient] (US mirror) RS(4,2) erasure resilient MDS code
[051027-erasure-9-2-resilient] (US mirror) RS(9,2) erasure resilient MDS code
[051031-erasure-10-3-resilient] (US mirror) RS(10,3) erasure resilient MDS code
[051101-erasure-9-7-resilient] (US mirror) RS(9,7) erasure resilient MDS code
[051102-erasure-10-7-resilient] (US mirror) RS(10,7) erasure resilient MDS code
[051103-erasure-9-5-resilient] (US mirror) RS(9,5) erasure resilient MDS code
* * *