Erasure resilient checksum codes
In real time media transmission over internet (such as VOIP), the sender may need to add after every k media packets some additional redundant packets (relevant to the last k media packets). The redundant packets are computed such that the receiver can recover the lost media packets if a sufficient number of total packets are survived.
(4, 2) erasure resilient code:
- Packet size is at least 2 bits and is divisible by 2
- Information is in two packets
- Transmitted are 4 packets, two of which are information and two others are redundant (the code is systematic)
- It is sufficient to receive any of two out of four transmitted packets to recover the two information packets (it is an MDS code)
-
Note that with Reed Solomon, with two two-bit symbols
(packets) you can add only one redundant symbol, since the total length of the codeword
cannot exceed 
symbols
Redundant messages are computed as follows:
Let
-
be the first information packet, where 
and 
are the first and
second half of the packet a
-
be the second information packet, where 
and 
are the first and
second half of the packet b
The redundant packets are the following:
-
-
- where the operation + is binary XOR
The diagram for decoding, for any possible two survivals is given in an excel file
(5, 2) erasure resilient code:
- Packet size is at least 3 bits and is divisible by 3
- Information is in two packets
- Transmitted are 5 packets, two of which are information and three others are redundant (thus the code is systematic)
- It is sufficient to receive any of two out of five transmitted packets to recover the two information messages (thus it is an MDS code)
Redundant messages are computed as follows:
Let
-
be the first information packet, where , and 
are the first, second
and third equal portions of the packet a
-
the same for packet b
The three redundant packets are
-
-
-
- where the operation + is binary XOR
The diagram for decoding, for any possible two survivals is given in an excel file
* * *
© Switzernet (www.switzernet.com)