You are here

Joint error correction enhancement of the Fountain Codes concept

1 post / 0 new
Jarek Duda
Joint error correction enhancement of the Fountain Codes concept

In standard (forward) error correction the encoder is adding some level of redundancy, which allows the decoder to repair damage level up to some threshold.
For example increasing twice a file theoretically allows to repair when at most 11% randomly chosen bits were flipped (binary symmetric channel, rate = 1-h(epsilon), h(0.11)~1/2).

However, in many situations, the sender doesn't know the details of later damage.
Fountain codes allow to handle situation when the sender doesn't know which of packets will be lost - the sender prepares a larger set of packets, such that any large enough subset is sufficient for complete reconstruction.
For example the sender could take a 10MB message and produce 20 packets of 1MB, such that any 10 (11 rather) of them allow to reconstruct the message.

The sender may have also none or limited knowledge of the damage levels, which is required to choose redundancy level in standard error correction, for example:
- broadcasting: while each packet (receiver) may have an independent damage level, the broadcaster has to prepare universal packets,
- storage media: while recording we usually don't know how badly the medium will be damaged while reading,
- networking: the sender often doesn't know the route of individual packets, which can determine the damage level,
- watermarking: the sender doesn't know the capturing conditions.

Joint Reconstruction Codes allow to handle such situations by combining the process of error correction and reconstruction from multiple packets. The packets prepared by sender can be treated by receiver as payload or redundancy, depending on the situation. They are jointly corrected using damage levels (estimated a posteriori) as individual trust level for each packet.
Preprint: http://arxiv.org/pdf/1505.07056

For example it allows to write DVD disks (or other storage media), such that there would be basically 3 options:
- fast straightforward decoding from any single undamaged disk,
- error correction from any single disk if damage is low,
- for high damage level, error correction from multiple disks.

What other applications could you think of?
Have you heard of some research for this common situation of sender not knowing damage levels?
What other solutions for such problems have you heard of?

Edited by: Jarek Duda on 08/24/2015 - 07:30