Hacker News Reader

Comment by dragontamer | Hacker News Reader

Your characterization seems... incorrect to me.

Reed Solomon codes are higher quality but much older and requires a matrix solve (LU decomposition plus yadda yadda, equivalent to inverting a matrix)

Turbo codes / LDPC are IIRC O(n) instead of O(n^2.5) or whatever the matrix turns out to be.

-------

Reed Solomon codes are closer to the Shannon limit but are not scalable, slower than linear and require quadratically or cubically more compute for the data.

Turbo Codes and LDPC do a shittier job but far far faster. So that makes them actually more ideal in practice even if they are worse than Reed Solomon codes.

View on HN

Reed-Solomon speed varies heavily. For the common case of worst-case recovery on moderately reliable foundations (e.g., file storage on disk) with reasonably sized codes, encoding is bottlenecked by RAM/disk/network bandwidth (wherever you're writing the results), typical decoding is blind concatenation, and worst-case decoding pulls an already solved matrix decomposition out of a cache to decode at line rate as well.

There's a trick in particular that allows you to rewrite the matmuls as a sequence of vectorized XORs, processing the same number of instruction words as other implementations (give or take control flow) but doing just a stream of zero-data-dependency vectorized math with lots of execution unit support. If you're feeling fancy you can do CSE and also choose the matrix constants minimizing XOR count.

Even without that, just basic AVX2 tricks get you a few GiB/s.

Unless the more expensive matrix math you're referring to is supposed to have n be the size of the code rather than the size of the data?

> and worst-case decoding pulls an already solved matrix decomposition out of a cache to decode at line rate as well.

I think this line says everything about your assumptions.

RAID-6 or other filesystems use extremely small ReedSolomon codes so these caching methods are possible.

But let's say you have a moderately sized (well, moderate for LDPC anyway) 65535-sized Reed Solomon problem (the maximum Reed Solomon that fits in 2^16 bits). Even with just 1% redundancy that's 655 parity.

Now consider the possible errors to solve for: 20 erasures means you have ~65535 choose 20 combinations of matricies to cache.

Or roughly 10^77 matricies you need to pre solve and cache to handle 20 erasures. Aka basically impossible.

----------

Now if you have 40 hard drives and are dealing with 3 or 4 errors tops, well sure caching is good and solves everything.

Reed Solomon is a perfect Maximally Distance code. For small n it's perfect.

For larger or even just moderate N (kilobytes for packets), it's too unwieldy. LDPC and Turbo Codes (which are imperfect codes) fill in the gap and allow for larger sizes as long as you give up on perfection.

Hm, I think I see. You're proposing using larger codes for larger data sizes? (as opposed to, e.g., the drive case where you typically have a stripe of data and assume that the failure mode to worry about is losing a whole hard drive, spreading stripes across drives)

Interestingly, for a lot of bit flip probabilities, iterating a smaller code has little additional overhead and better error handling (lower chance of that longer message having an uncorrectable error). With a 10% bit flip chance, even a 253+2 code over GF256 looks attractive comparatively (horrible overall, but better than the proposed larger code; I think your code makes more sense in practical regimes).

Basically yeah.

Ethernet frames are in the 1500 bytes MTU region. Maybe jumbo frames in the 8000 bytes or so.

Traditionally, "Fire Codes" could provide error correction at high speed over the whole packet (https://en.wikipedia.org/wiki/Burst_error-correcting_code#Fi...), not as well as Reed Solomon (or LDPC/Turbo codes), but that should give you an idea that the 1000 to 8000 bytes of "error corrected data" is actually quite pragmatic in the real world (ie: a lot of Cisco switches or routers that rely upon Fire Codes as forward error correction).

Note: A 32-bit fire code could only protect from errors that exist ALL within a singular 32-bits "burst". Its a "bad" code but very high speed. Fire Codes can never protect against two random errors spread far away, its "purely" a burst error correction scheme.

As we look towards more recent ethernet standards (ex: 802.11), they tend to use LDPC or Turbo Codes instead. I don't know the MTU of 802.11 but I assume its also in the 1000 to 8000 bytes region.

65535-sized is the limits to Parchive, which uses 16-bit Reed Solomon. It doesn't grow quite to that size in practice, but you're still dealing with error correction (or erasure-correction) codes far larger than what happens in RAID6 or other such scenarios.

---------

All are pragmatic. But the region where Turbo Codes / LDPC excels at are the much much larger codes where Reed Solomon's O(n^2.5) (or something) is a disqualification. I'd imagine that if "Pararchive" were rewritten with today's technology, it'd be a Turbo Code or LDPC.

I don't see how classic RS codes could beat Turbo Codes (or LDPC). One of the key innovations of the latter is that they handle soft decoding; i.e., different levels of uncertainty of the incoming bits. It's much better to say that you're only 51% confident that a bit is 0 (when it should be 1) than 100% confident! This is especially important for analog systems (like radios) where the incoming bits naturally come with a confidence value.

There are soft versions of RS codes, but these came much later and use the same iterative techniques that Turbo/LDPC decoders use.

That's irrelevant for the discussion of the Shannon Limit.

Reed Solomon codes are literally perfect, or more mathematically they are Maximum Distance Codes (https://en.wikipedia.org/wiki/Singleton_bound)

Turbo Codes and LDPC are provably imperfect, failing this property. However, they are very close to perfect (like 99.999999% perfect in practice).

Now the issue with Reed Solomon is that matrix factorization / effective matrix inverse. It's basically impossible to run Reed Solomon above say, 16 bits or 65536 elements or so (2 bytes at that point so 128kB). Because the matrix to solve this would be 65536 x 65536 x 2 bytes or like 8Gb or something.

Hmmm, I guess modern computers can handle 8GB lol. But you get the gist, the O(n^2) is a problem.

LDPC and Turbo Codes are linear. So a 4MB LDPC is gonna be you know... Actually possible on modern computers... While a 4MB Reed Solomon Code will need some number of exabytes to just build the damn decoding matrix. (32 bits times 4MB squared or something like that)

Reply on news.ycombinator.com