Research another type of ecc codes: Raptor/LT/Fountain

klauspost / reedsolomon

Reed-Solomon Erasure Coding in Go

MIT License

1.88k stars 248 forks source link

Research another type of ecc codes: Raptor/LT/Fountain #3

Closed sokoow closed 9 years ago

sokoow commented 9 years ago

Reed-solomon is one of the earliest turbo codes, it has evolved since into:

http://blog.notdot.net/2012/01/Damn-Cool-Algorithms-Fountain-Codes

Opening an issue to point your attention to it also :)

klauspost commented 9 years ago

@sokoow thanks for the link!

I don't see huge advantages, but here thy are just for reference:

FC Pros
- Shard number is unlimited (not 256 as this RS implementation).
- Likely faster on many shards.
- You don't need all shards to be able to reconstruct.
RS Pros
- Decoding is predictable. You need 16GB valid shard data to decode 16GB. With FC it depends. I don't like unpredictability ;)

lrq3000 commented 9 years ago

Reed-Solomon are not a kind of turbo code. Reed-Solomon is an optimal error correction algorithm (meaning that it can reach exactly the Singleton bound), whereas turbo codes are near-optimal codes (they always are below the Singleton bound). Maybe you can find some similarities (and in fact, both can be combined in convolutional or concatenated codes), but they are not the same class of algorithms at all.

klauspost commented 9 years ago

I will put it on my "future-projects" list. But thanks for bringing it up!

Either way it will be a separate package, so I will close this.