Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

One related scheme is fountain codes, where you can split a file into a pseudo infinite stream of blocks such that finding N blocks will almost certainly allow reconstruction. Very useful in UDP / satellite transmission, where you can keep broadcasting these blocks and clients can listen at their convenience.

The state of the art codec is RaptorQ, I’ve got a Go library that uses the slightly older Raptor standard to do chunking

https://github.com/sudhirj/pump




What happens if you can't get N blocks, but say N-1 or N-2? Can you get a partial reconstruction, or nothing at all?


It's actually probabilistic, though the probabilities very quickly approach 0 and 1 on each side.

But to answer your question, yes, you could recover some of the file if you didn't get as many pieces as you needed. Been a year or so since I did any work with fountain codes, but I believe most implementations send all the chunks, followed by n error correction chunks, so it would depend on how many real chunks you got. The error corrections wouldn't get you anywhere though.


online codes [0] just generate random linear equations of the source chunks and send both generated right hand side and the seed that generated the equation. This way there's no state to keep (now, which equations did I send ?) Most generated equations are of degree 2 (so an equation with 2 ones) some (about 1% iirc) are of degree 1 (so pure data). Having less than the critical mass of equations will give you partial reconstruction. But all bets are off regarding how much you will get. They were used in storage by Amplidata in their Amplistor at some point.

[0] https://en.wikipedia.org/wiki/Online_codes


Fountain codes are seeing use in DNA storage encoding schemes. That's how I use them, at any rate.


I know nothing about this but it sounds super interesting. Care to share more?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: