18 ms·
There's an idea used in the analysis of error correcting codes, to set up a polynomial where the coefficients are the number of codewords with each Hamming weig
by tlb 8y ago
There's an idea used in the analysis of error correcting codes, to set up a polynomial where the coefficients are the number of codewords with each Hamming weight. It works out the same as adding up all the codewords, where you replace each 0 by x and each 1 by y. So a code
010 101 => xyx + yxy = x^2y + xy^2
https://en.wikipedia.org/wiki/Enumerator_polynomial https://en.wikipedia.org/wiki/Enumerator_polynomial
Then you can use real (or even complex) analysis on these polynomials. There's a thick book of things you can prove about sets of binary words using those techniques: https://www.elsevier.com/books/the-theory-of-error-correcting-codes/macwilliams/978-0-444-85193-2 https://www.elsevier.com/books/the-theory-of-error-correctin...
And Noam Elkies' course notes on it: http://www.math.harvard.edu/~elkies/M256.13/index.html http://www.math.harvard.edu/~elkies/M256.13/index.html
- sillysaurus3 8y agomic drop Thank you. This was a legendary answer. I really have been hunting this question for years: https://news.ycombinator.com/item?id=13764917 https://news.ycombinator.com/item?id=13764917 This seems like how he did it. Error correcting codes are a natural domain for questions like "What are the fewest gates gates required to transmit some information?" But the missing puzzle piece was that you can analyze them with polynomials.
- graycat 8y agoError correcting codes, coding theory, etc. is an old, serious, and deep field. Once I took a grad course in it. The course was heavily abstract algebra, especially finite fields. A respected text is W.\ Wesley Peterson and E.\ J.\ Weldon, Jr., {\it Error-Correcting Codes, Second Edition.\/} Last I heard, there has been some surprisingly good progress in the field. Might look up, say, "turbo codes".