2 ms·

I'm surprised rateless fountain codes aren't mentioned! If you enjoy this sort of thing, you'll find the Luby Transform Code fascinating: https://en.wikipedia.o

I'm surprised rateless fountain codes aren't mentioned! If you enjoy this sort of thing, you'll find the Luby Transform Code fascinating: https://en.wikipedia.org/wiki/Luby_transform_code https://en.wikipedia.org/wiki/Luby_transform_code This paper is a really nice overview with more detail: https://switzernet.com/people/emin-gabrielyan/060112-capillary-references/ref/MacKay05.pdf https://switzernet.com/people/emin-gabrielyan/060112-capilla... LT codes are used as the "outer code" in the linear time RaptorQ encoding specified in RFC6330: https://www.rfc-editor.org/rfc/rfc6330 https://www.rfc-editor.org/rfc/rfc6330

AYBABTME 2y ago
Aren't there patent problems with fountain codes?
- jcalvinowens 2y ago
  Luby's original paper was published in 2002. Not sure about RaptorQ though...
  - Sanzig 2y ago
    IIRC, Qualcomm still holds patents on RaptorQ. They do provide a blanket license exemption for implementing RFC6330.
Luker88 2y ago
I have implemented RaptorQ and RFC6330. First, the rfc is pointlessly complex and optimized for files, not for streaming. if you want to play with it, manage blocks by yourself, ignore the asinine interleaving and block size management. Second, the algorithm is actually split in two parts, and while the second (generation of repair blocks) is linear, the first is cubic on the number of messages that you put together in a block (~~ matrix gaussian elimination). And while parts of both encoding and decoding can be cached, I think that "linear time" encoding for raptorq is actually just false marketing speak.
jumperabg 2y ago
Are rateless fountain codes the better solution and if are there any systems that are using them?
- toolslive 2y ago
  Amplidata did this https://en.wikipedia.org/wiki/Amplidata https://en.wikipedia.org/wiki/Amplidata It's a great solution (fast, storage overhead of about 1.2%) iff your data is immutable.

AYBABTME 2y ago

Aren't there patent problems with fountain codes?

jcalvinowens 2y ago
Luby's original paper was published in 2002. Not sure about RaptorQ though...
- Sanzig 2y ago
  IIRC, Qualcomm still holds patents on RaptorQ. They do provide a blanket license exemption for implementing RFC6330.

Luker88 2y ago

I have implemented RaptorQ and RFC6330. First, the rfc is pointlessly complex and optimized for files, not for streaming. if you want to play with it, manage blocks by yourself, ignore the asinine interleaving and block size management. Second, the algorithm is actually split in two parts, and while the second (generation of repair blocks) is linear, the first is cubic on the number of messages that you put together in a block (~~ matrix gaussian elimination). And while parts of both encoding and decoding can be cached, I think that "linear time" encoding for raptorq is actually just false marketing speak.

jumperabg 2y ago

Are rateless fountain codes the better solution and if are there any systems that are using them?

toolslive 2y ago
Amplidata did this https://en.wikipedia.org/wiki/Amplidata https://en.wikipedia.org/wiki/Amplidata It's a great solution (fast, storage overhead of about 1.2%) iff your data is immutable.