Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The essence of Reed-Solomon coding

mazzo.li

Post reply on HN
Print view View original

11–20 of 44 posts

Re: The essence of Reed-Solomon coding

#11

Post by nayuki »

klodolph wrote: post #4

Some additions, as "exercise for the reader": 1. The finite field you choose has a minimum size. What is the minimum size field 2^bits for an RS(N,K) coding system? What happens when you try to construct a Reed-Solomon code with a finite field that is too small? 2. Consider a Reed-Solomon coding system which uses a lookup table for the finite field multiplication operation that fits in L1 cache. Given that the table…

> What is the minimum size field 2^bits for an RS(N,K) coding system?

Your field size must be at least N+1, noting that you shouldn't use the value 0 in the encoding matrix.

> What happens when you try to construct a Reed-Solomon code with a finite field that is too small?

Your system of linear equations doesn't have enough linearly independent equations.

> how could you make the encoder/decoder faster

Maybe put the lookup table in a 64-bit general-purpose register and use bit shifting, or in a 128/256/512-bit SIMD register and use extraction instructions (shuffle bytes, etc.).

Re: The essence of Reed-Solomon coding

#13

Post by [deleted] »

vlovich123 wrote: post #8

I really wish physical and OS network stacks would be able to give you the ability to send uncorrected bit streams. That way you can tune the error rate at the application level that makes sense. For example, with video streaming, you probably don’t need much error correction on the data stream as periodic i-frames would correct any transient glitches (you’d only bother to EC the control headers for the video). Then…

[deleted]

Re: The essence of Reed-Solomon coding

#14

Post by Hanschri »

nayuki wrote: post #10

Using Reed-Solomon coding to recover from erasures (at known positions) is relatively straightforward. It can be understood with a basic knowledge of linear algebra and finite field arithmetic. Using RS for error correction (at initially unknown positions) is quite difficult. I wrote a step-by-step guide on it including demo code, and it doesn't even cover the most efficient decoding algorithm (I used PGZ instead of…

To understand how error correction works and to learn more about Hamming codes & Reed-Solomon, 3Blue1Brown and Ben Eater were invaluable. 3Blue1Brown and Ben Eater are by far some of the best educational content creators within their fields, mathematics and computer engineering respectively.

I would strongly recommend anyone interested in the topic to check out any of these videos:

How to send a self-correcting message (Hamming codes): https://www.youtube.com/watch?v=X8jsijhllIA

Hamming codes part 2, the elegance of it all: https://www.youtube.com/watch?v=b3NxrZOu_CE

And any of Ben Eater's five videos on error correction: https://eater.net/crc

As an aside, Ben Eater does all of his videos and demonstrations using an 8-bit computer he has built step by step in videos on a breadboard. Very impressive and inspiring.

Re: The essence of Reed-Solomon coding

#15

Post by agsamek »

Reed-Solomon is the foundation of today's computing. It is used in data storage (hdd, ssd) and in data transfer protocols. It allows for building of a reliable system on top of an unreliable real life fenomens with desired level of certainty. This is so incredible tech that once implemented we can just forget about it in the higher level abstractions.

Re: The essence of Reed-Solomon coding

#16

Post by not2b »

est wrote: post #2

I think Reed-solomon should be considered in future network protocols designs to combat censorship. Every byte should be demuxed into bits and transferred in independent data streams, so MITM boxes can only intercept incomplete streams, and aggregate streams back to original would be insanely difficult. Let transport layers do only one job and no distinguish whatever the content might be inside. Currently H2 does sup…

That seems an inferior approach to just using encryption.

Re: The essence of Reed-Solomon coding

#17

Post by markc »

nayuki wrote: post #12
QuinnyPig wrote: post #5

This is, for example, how Amazon S3 works.

This is how Backblaze works. https://www.backblaze.com/blog/reed-solomon/ , https://github.com/Backblaze/JavaReedSolomon , https://news.ycombinator.com/item?id=9726890

And Sia distributed storage network https://gitlab.com/NebulousLabs/Sia/-/blob/master/modules/er...

Re: The essence of Reed-Solomon coding

#18

Post by jonathanlydall »

vlovich123 wrote: post #8

I really wish physical and OS network stacks would be able to give you the ability to send uncorrected bit streams. That way you can tune the error rate at the application level that makes sense. For example, with video streaming, you probably don’t need much error correction on the data stream as periodic i-frames would correct any transient glitches (you’d only bother to EC the control headers for the video). Then…

This is already done by many audio/video chat compression algorithms which use UDP.

The idea being that with something like voice or video, if a packet doesn’t arrive, instead of stalling everything while you wait for a retransmit, you instead just carry on regardless.

The occasional missing packet in voice is almost imperceptible, however the more packets that get lost the more the voice seems to “break up”.

With video the symptoms are an accumulation of visual corruption until the next key frame.

FPS games also do this (or at least used to), servers would send a stream of UDP packets of entity states (as opposed to sending deltas of state changes), so things like player1 is at x,y,z coordinate with velocity a and heading vector of b.

If clients missed a packet they would just wait for the next one since it’s useless to know later where someone else was, all you actually care about is where they are, or what’s happening, now.

Re: The essence of Reed-Solomon coding

#19

Post by sgtnoodle »

vlovich123 wrote: post #8

I really wish physical and OS network stacks would be able to give you the ability to send uncorrected bit streams. That way you can tune the error rate at the application level that makes sense. For example, with video streaming, you probably don’t need much error correction on the data stream as periodic i-frames would correct any transient glitches (you’d only bother to EC the control headers for the video). Then…

You can do it in linux, with drivers that implement packet injection. You're giving up a lot, though. I think you're right about it being a wash with regard to control overhead. In particular, because of the data ACKs, the firmware can aggressively ramp the 802.11 frame data rate up and down. Thanks to packet aggregation, the cost of the frame preamble gets amortized across all buffered up data. Letting each application schedule its own transmission would quickly eat up the available channel bandwidth in frame overhead. It works for a single specialized application, but monopolizes the entire shared channel.

Folk do that sort of thing when transmitting low latency first-person-video from drones, using commodity wifi hardware.

Re: The essence of Reed-Solomon coding

#20

Post by terramars »

I implemented the RS encoder that ended up being used on the production satellite bus for the telemetry system in space systems / Loral upgraded bus during my engineering coop in school! All in verilog. It's complicated especially the decoder but understandable with time. The turbo codes and more modern extensions that enable lte / 5g and other low power / small antenna applications are absolute black magic though. Such a cool field!
Post reply on HN