Comment by dragontamer | Hacker News Reader

Comment by dragontamer | Hacker News Reader

Parent Full thread

Reed Solomon is closer to "perfect" but is unnecessary.

IIRC, Turbo Codes and LDPCs are less-perfect (they cannot offer strict guarantees like Reed-Solomon can), but as XOR-based simple operations, they are extremely extremely fast to implement.

LDPC has high-probabilities of fixing errors (near Reed-Solomon level), which is good enough in practice. Especially since LDPC's simple XOR-based operation is far faster and like O(n) instead of Reed-Solomon's matrix-multiplication (O(n^2)) algorithm.

The state of the art has moved forward. Reed Solomon is great for proving the practice and providing strict assurances (likely better for storage where you have strict size limits and need strong guarantees for MTBF or other such statistics). But for a "faster" algorithm (ie: trying to prevent repeated packets in a communication stream like TCP or similar protocol), LDPC and/or Turbo codes are likely a better solution.

-----

Reed Solomon is probably best for "smaller" codes where the matrix is smaller and O(n^2) hasn't gotten out of hand yet. But as codes increase in size, the O(n) "less than perfect" codes (such as Turbo codes or LDPC codes) become better-and-better ideas.

That being said: I can imagine some crazy GPU / SIMD algorithm where we have such cheap compute and low bandwidth where the O(n^2) operation might serve as a better basis than the cheap XOR operation. The future of computers is going to be more compute and less relative memory bandwidth after all, so the pendulum may swing the other way depending on how future machines end up.

I'm interested in using LDPC (or Turbo Codes) in software for error correction, but most of the resources I've found only cover soft-decision LDPC. When I've found LDPC papers, it's hard for me to know how efficient the algorithms are and whether it's worth spending time on them. Reed-Solomon has more learning resources that are often more approachable (plus open source libraries). Do you have more information on how to implement LDPC decoding using XOR-based operations?

Alas, no. I'm mostly spitballing here since I know that XOR-based codes are obviously much faster than Reed-solomon erasure code / matrix solving methodology.

There's a lot of names thrown out for practical LDPC erasure codes. Raptor Codes, Tornado Codes, and the like. Hopefully those names can give you a good starting point?

EDIT: I also remember reading a paper on a LDPC Fountain Code (ex: keep sending data + LDPC checkbits until the other side got enough to reconstruct the data), as a kind of "might as well keep sending data while waiting for the ACK", kind of thing, which should cut down on latency.

--------

I'm personally on the "Finished reading my book on Reed-Solomon codes. Figuring out what to study next" phase. There's a lot of codes out there, and LDPC is a huge class...

Then again, the project at work that I had that benefited from these error (erm... erasure) correcting codes was complete and my Reed-solomon implementation was good enough and doesn't really need to be touched anymore. So its not like I have a real reason to study this stuff anymore. Just a little bit of extra data that allowed the protocol to cut off some latency and reduce the number of resends in a very noisy channel we had. The good ol' "MVP into shelved code" situation, lol. Enough code to prove it works, made a nice demo that impressed the higher-ups, and then no one ended up caring for the idea.

If I were to productize the concept, I'd research these more modern, faster codes (like LDPC, Raptor, Tornado, etc. etc.) and implement a state-of-the-art erasure correction solution, ya know? But at this point, the projects just dead.

But honestly, the blog-post's situation (cut down on latency with forward error correction) is seemingly a common problem that's solved again and again in our industry. But at the same time, there's so much to learn in the world of Comp. Sci that sometimes its important to "be lazy" and "learn it when its clearly going to be useful" (and not learning it to hypothetically improve a dead project, lol).

All right, I'll search for those and read about them.

It's unfortunate when a project I've worked on for a while is never used, but at least nice when I learned something from writing it.

Thanks!

The search term you want for that is "binary erasure channel" + LDPC decoding .

I hadn't heard that term before. I'll search for it. Thanks!

I haven't heard about LDPCs before. Thanks!

Do they serve the same use case though? With Reed-Solomon the idea is to recover from complete loss of a fragment of data (erasure coding), isn't LPDC strictly for error correction/"noise" (e.g. certain bits flipping but the data overall exists)?

I admit that I haven't thought it all the way through, but in general, all error-correction codes I'm aware of have a simpler erasure-code version available too.

Reed Solomon traditionally is an error-correction code, for example. But has common implementations in its simplified erasure-only code. (Ex: fixing "lost data" is far easier than fixing "contradictory data").

I'm fairly certain that LDPC erasure codes is as simple as "Is there only one missing erasure in this particular code??" and "answer is LDPC XOR (other data) == missing-data".

EDIT: The "hard part" is the exact composition of (other data), of which there's many styles and different methodologies with tons of different tradeoffs.

That's true too, this approach isn't limited to Reed-Solomon (or MDS codes). For non-MDS codes the fetch logic becomes a little more complicated (you need to wait for a subset you can reconstruct from rather than just the first k), but that's not a huge increase in complexity.

Reply on news.ycombinator.com