Introduction to Fountain Codes: LT Codes with Python | Hacker News Reader

Introduction to Fountain Codes: LT Codes with Python

franpapers.com

71 pointsespeed11 comments

This is super cool. The author is remarkably good at quickly explaining and conveying how all of this works.

I was initially surprised that they were able to get an actual error correcting code running in Python at 100 MB/s to 300 MB/s, but once I saw that it was just XOR all over the place, that made lots more sense.

I think it'd be really cool to see this author write a post explaining some of the more advanced codes such as Raptor codes.

Raptor codes are powerful, but one has to be careful with them, as they are heavily patent encumbered by Qualcomm according to Wikipedia[1]:

"Raptor codes are heavily covered with patents in various jurisdictions. For the specific instances specified in RFCs, statements by patent owners may or may not provide some leeway, depending among other things on whether the device carrying the implementation also implements a "wide-area wireless" specification."

So I encourage people who otherwise work with Error-Correcting codes to tread lightly when considering implementing Raptor and RaptorQ codes.

[1] https://en.wikipedia.org/wiki/Raptor_code

Huh. That's slightly disappointing.

Do you know of any other fountain codes more powerful than the LT code described in the article, that are not particularly patent encumbered? This seems like a really interesting area, but from reading around a bit, it seems like part of the issue is that because all of the research is so recent, you end up stepping on someone or other's IP.

You can have a look at Tornado codes[1]. These codes are also based on LT codes and their patent seems to be no longer in effect.

For a completely open and free alternative for application-level forward erasure correction (AL-FEC) codes, checkout OpenFEC[2].

1 - https://en.wikipedia.org/wiki/Tornado_code 2 - http://openfec.org

Online Codes (https://en.wikipedia.org/wiki/Online_codes) are very similar to Raptor codes for rateless erasure coding. The construction consists of an inner an outer code. However unlike RaptorQ, they are not optimized for an entire range of block lengths.

Hi, I'm the author of this article! I really appreciate your comment, thank you.

I had the idea to continue this "series" with the Raptor Codes but, as it was replied, it is under a lot of patents and I have to admit that it was discouraging. What a frustration for the readers to understand something but no being able to use it freely.

I am not so sure about the LT Codes either.

    Knowing b1, we find b2 such that b2 = b1 \oplus s;
    Knowing b2, we find b1 such that b1 = b1 \oplus s.

Do you mean, b1 = b2 \oplus s in the second bullet? I also cannot follow the example right below it: XOR s5 and s6 gives b3, not b4.

Can someone help me with this?

You're right for b1 = b2 xor s in the second bullet, I corrected it.

You cannot solve b3 before you solve s2. b4 is solved with s6 right after that you realize that s1 = b1, and thus s6 = b1 xor b4

I remember Fountain Codes in the news around the 2000's. It seemed like a promising technology for file transfer and storage.

What are the applications today?

They are used to transmit data through very lossy connections, satellites being the primary application.

I think due to aggressive patenting many applications never materialized. I know I looked at them several times and the decision was always "not worth the licensing hassle".

Reply on news.ycombinator.com