News for hackers. Stuff that matters.
Re:Answer to a 150-Year-Old Math Conundrum Brings More Mystery by beagle3 on Sunday June 21, 2015 @12:52AM (#9752233)
> after only a few decades of work (say, 1948 to 1993), turbo codes were discovered.

But LDPC codes were shown by Gallager in 1963[0], and while they were not feasible to implement at the time, saying that the theory waited for turbo code discovery is wrong.

[0] https://en.wikipedia.org/wiki/Low-density_parity-check_code#...

Re:Answer to a 150-Year-Old Math Conundrum Brings More Mystery by mturmon on Sunday June 21, 2015 @01:50AM (#9752358)
I disagree completely. There is a theory of finding practical codes, and that theory took decades to elucidate.

A practical code must be not just computationally tractable, but also, the channel capacity must be approached quickly as block length increases, and decoding must not blow up for large block lengths. As you can read in Gallager's thesis, this was not known for LDPCs back in 1960.

Even in the mid-90s, when the connection between LDPC's and turbocodes became understood, it took more theoretical work to understand why some codes (those having short cycles) had poor performance -- because decoding them was fragile. (See the excellent http://sigpromu.org/sarah/SJohnsonLDPCintro.pdf).

Similarly to the OP, there may be multiple ways to find designs, but some of the methods or the resulting designs may be clumsy or inefficient.

Incidentally, it turns out there is a deep connection between coding (i.e., the present analogy) and designs (the OP), see http://www.ces.clemson.edu/~keyj/psfiles/booktoc.html, and the follow-up article http://www.ces.clemson.edu/~keyj/Key/dccupdateb.pdf, especially chapter 7.

Re:Answer to a 150-Year-Old Math Conundrum Brings More Mystery by darkmighty on Sunday June 21, 2015 @01:06AM (#9752265)
Large good codes were always known to exist, the crux from when Shannon published his work (I believe) was to actually get good codes that are computationally viable (else you could even use Shannon's random code). LDPC codes were rediscovered only because decoding became viable due increased computational power (w.r.t the 60's) and, crucially, discovery of iterative decoding for them (belief propagation etc).