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)

 

 

US Mirror

CH Mirror