From: Lynn Killingbeck Subject: Re: Coding Theory? Date: Wed, 10 Feb 1999 02:43:00 -0600 Newsgroups: sci.math Keywords: What is coding theory? Fritz J Schneider wrote: > > A friend of mine mentioned something called 'Coding Theory' the > other day. I poked around a bit but couldn't find much (good) > information. I have a suspicion that it is related to combinatorics > and/or DSP? Could anyone here point me in the right direction? Please cc > me in if you post to the newsgroup as the traffic here is quite heavy. > Thanks in advance. > > =-----------------------------------+-------------------------------------= > Fritz Schneider / fritz@columbia.edu | For PGP Public Key finger me here: > Columbia University Engineering | "schneider,fritz"@cunix.cc.columbia.edu > =-----------------------------------+-------------------------------------= > http://www.columbia.edu/~fjs18 Try starting with the well-known author Richard W. Hamming. I have his 'Coding and Information Theory' in my collection. (No claims to really having read and understood it, though!). Lynn Killingbeck ============================================================================== From: eclrh@sun.leeds.ac.uk (Robert Hill) Subject: Re: Coding Theory? Date: Wed, 10 Feb 1999 16:05:29 +0000 (GMT) Newsgroups: sci.math In article <36C14694.323@phoenix.net>, Lynn Killingbeck writes: [post above -- djr] Similarly I've several times tried to read "Algebraic Coding Theory" by E.R. Berlekamp, egged on by the knowledge that it won a prize from the IEEE or somebody, and that he is one of the co-authors of "Winning Ways", but have never got very far with it. Another good key phrase to search on is "Error-correcting codes". The subject is largely about how to design economical ways of incorporating redundancy in information to allow it to be reconstructed after transmission over noisy channels. Useful for telephone engineers, people at JPL receiving messages from spacecraft, etc. Also has connections to many other subjects. -- Robert Hill University Computing Service, Leeds University, England "Though all my wares be trash, the heart is true." - John Dowland, Fine Knacks for Ladies (1600) ============================================================================== From: Jeremy Lee Subject: Re: Coding Theory? Date: Wed, 10 Feb 1999 21:17:52 +0000 Newsgroups: sci.math To: Fritz J Schneider Personally, when I did this, I found Hamming's book quite hard going.. I'd recommend C.M. Goldie and R.G.E. Pinch, "Communication Theory" which I think is better for more general theory, and not skewed heavily to Hamming Jeremy Fritz J Schneider wrote: > On Wed, 10 Feb 1999, Lynn Killingbeck wrote: > > > Try starting with the well-known author Richard W. Hamming. I have his > > 'Coding and Information Theory' in my collection. (No claims to really > > having read and understood it, though!). > > Great. I vaguely remember hearing about the 'Hamming Distance' > and 'Hamming Single Error Correction' in my digital logic class... Thanks. > > =-----------------------------------+-------------------------------------= > Fritz Schneider / fritz@columbia.edu | For PGP Public Key finger me here: > Columbia University Engineering | "schneider,fritz"@cunix.cc.columbia.edu > =-----------------------------------+-------------------------------------= > http://www.columbia.edu/~fjs18 ============================================================================== From: chavey@beloit.edu (Darrah Chavey) Subject: Re: Coding Theory? Date: Wed, 10 Feb 1999 13:04:29 -0600 Newsgroups: sci.math Fritz J Schneider wrote: [as above -- djr] Some of the books on Coding Theory are really too mathematical; some are too outdated. I learned from "The Theory of Error-Correcting Codes" by F.J. MacWilliams and N.J.A. Sloane, and I very much liked that text, although it is dated (1978). Look for books in the library near this one, or the Hamming book mentioned. --Darrah Chavey Department of Math & Computer Science chavey@beloit.edu Beloit College; 700 College St; Beloit, Wisc. (608)-363-2220 http://www.beloit.edu/~chavey 53511 -- The main reason Santa is so jolly is because he knows where all the naughty girls live. ============================================================================== From: phunt@interpac.net Subject: Re: Coding Theory? Date: Wed, 10 Feb 1999 23:04:25 GMT Newsgroups: sci.math To: fjs18@columbia.edu In article , Fritz J Schneider wrote: > A friend of mine mentioned something called 'Coding Theory' the > other day. I poked around a bit but couldn't find much (good) A large part of information theory is concerned with principles of encoding and decoding, error detection and correction, and, error minimization and optimization schemes. Coding occurs when information is represented by symbols from a signalling alphabet. I can't say more, as I've only recently begun to study this stuff, however, I do recall a classic introduction for beginners titled: "Symbols, Signals, and Noise," by, J.R. Pierce. /ph - - - - - - - - - - - - - - - - - - - - - - - - - - - In article , Fritz J Schneider wrote: [as above -- djr] -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ============================================================================== From: torquemada@my-dejanews.com Subject: Re: Coding Theory? Date: Fri, 12 Feb 1999 19:09:13 GMT Newsgroups: sci.math In article , Fritz J Schneider wrote: > A friend of mine mentioned something called 'Coding Theory' the > other day. I poked around a bit but couldn't find much (good) > information. I have a suspicion that it is related to combinatorics > and/or DSP? Coding theory is at the heart of some of the deepest, richest and most beautiful mathematics around today. One thing coding theory is about is error correcting codes. These are ways to represent m-bit strings using n-bit *codewords* (n>=m) in such a way that if up to d bits get flipped randomly in the n-bit codeword you can still figure out which m-bit string it came from. This gives you a way to send data down a noisy channel. A code is *perfect* if you can correct d bits and there is no wastage - ie. every n-bit string is within d bits of exactly one representation of an m-bit string with nothing left over. All perfect codes have been found and there aren't many. One that stands out is the 23 bit Golay code. Extend it by adding a parity check bit and you get the 24 bit extended Golay code G_24. If you look at the permutations of these 24 bits that map codewords to codewords you get the Mathieu group M_24. This is one of the 26 exceptional 'sporadic' groups that appears in the classification of finite simple groups and has a myriad of wonderful properties. Using G_24 you can construct a 24-dimensional lattice called the Leech lattice which is one of the most remarkable objects in all of mathematics. It gives the densest known packing of spheres in 24 dimensions and all densest known packings in lower dimensions come from slices of this. It is closely tied up with the Monster group and the Monstrous Moonshine conjectures that form part of the work of Borcherds who just recently received a Fields medal. There is a connection with String Theory in physics which in some sense is a 24 dimensional theory. There are also connections with the theory of experimental designs, game theory, algebraic geometry, elliptic functions and on and on... So *do* check it out! -- Torque http://travel.to/tanelorn -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ============================================================================== From: cmonico@nd.edu (Chris Monico) Subject: Re: Coding Theory? Date: Sun, 14 Feb 99 06:48:53 GMT Newsgroups: sci.math To: fjs18@columbia.edu In article , Fritz J Schneider wrote: [as above -- djr] It depends on what flavor you'd like- but for a more theoretical treatment, you'd want to learn some information theory (see the foundational paper by Claude Shannon from 1948). Shannon essentially layed the mathematical groundwork for for Information Theory, including channel coding (i.e., error correcting codes), source coding (i.e., data compression, cryptography - via mutual information,...). But Shannon gave limits on the best possible error correcting codes, proved that the one-time pad is an unconditionally secure cryptosystem, and did many similar things before anyone else had any idea how to do them. For a mathematician, I would suggest J.H. van Lint's 'Into to Coding Theory' - (in addition to the papers of Shannon) it's a Springer book. I think there is a new edition which treats convolutional codes. But he probably does not treat the so-called Turbo Codes. These are a recently discovered class of codes that provide near Shannon-limit decoding capabilities, but they are not well understood. There is little mathematical treatment of them at the moment, but they are nevertheless very interesting in that they use non-optimal decoders, but still perform far better than other codes, and are nearly as good as the theoretically best possible codes. But convolutional codes are very interesting as well, and are recently lending themselves to some very nice mathematics. There is alot of new treatment of them, by which classical linear block codes become a special case. best wishes, ============================================================================== From: David Subject: Re: Coding Theory? Date: 16 Feb 1999 00:11:15 GMT Newsgroups: sci.math jsavard wrote: : Hunting in books on the subject, and on the web, I have so far failed to : find a nice, simple, spelled-out illustration of the binary Golay code and : the best method of decoding it - the way Hamming codes are given : explicitly. Try the book "Coding Theory" by D.G. Hoffman, et al. ISBN: 0824786114 it's got a chapter on perfect codes, which includes algorithms for decoding the Golay and Extended Golay Codes. David ============================================================================== From: scoffey@quip.eecs.umich.edu (Sean Coffey) Subject: Re: HELP!: seeking algorithms for coding theory problem Date: 12 Feb 1999 01:51:08 GMT Newsgroups: sci.math,sci.math.research,sci.crypt In article , Markus Grassl wrote: < list of papers on the decoding problem deleted > There is an extensive review chapter by Alexander Barg in the newly published "Handbook of Coding Theory" (eds. Pless and Huffman), North-Holland '98. This covers the history of the algorithms that have been put forward for all the (many) different versions of this problem. Sean Coffey ============================================================================== From: "Charles H. Giffen" Subject: Re: What is coding theory? Date: Wed, 25 Aug 1999 13:04:00 -0400 Newsgroups: sci.math To: Chris Hillman Chris Hillman wrote: > > On 25 Aug 1999, Nakazanie wrote: > > > I have heard the term "coding theory" thrown around a lot. Could someone > > please tell what coding theory is all about? ( I have some background in > > number theory) > > Please respond via email. > > Try the short paper "Performance and Complexity" by David Forney which you > can find on my page > > http://www.math.washington.edu/~hillman/Entropy/infcode.html > > Chris Hillman > > Home Page: http://www.math.washington.edu/~hillman/personal.html If you were to ask a homological algebraist or category theorist, you might get the answer that Coding Theory is the dual of Ding Theory! --Chuck Giffen