7 ms·

A Mathematical Theory of Communication [pdf]

298 points by luu 2y ago

whereismyacc 2y ago
my holy book
ziofill 2y ago
I use this paper whenever I teach information theory. If you are mathematically inclined, I’d recommend you to read the demonstration of his two main theorems, it’s illuminating.
the_panopticon 2y ago
Another great read from Shannon https://archive.org/details/bstj28-4-656 https://archive.org/details/bstj28-4-656
mehulashah 2y ago
When you read this and think about the world he was in — it’s even more remarkable. How did he come up with it?
- 082349872349872 2y ago
  From playing 20 Questions and attempting to formalise it? EDIT: actually the cryptography connection is more likely: Leibniz was XVII; who was it that was already using binary alternatives for steganography a few centuries earlier? EDIT2: did entropy in p-chem come before or after Shannon? EDIT3: well before; S = k_B ln Ω was 1877.
- duped 2y ago
  This is apocryphal, but it probably had something to do with dropping shells on Nazis - he was developing fire control systems for the US Navy around the time he developed the theorem, and only published several years after the War. Allegedly he also derived Mason's Gain Formula around the same time but that was classified until Mason published it.
shalabhc 2y ago
While well known for this paper and "information theory", Shannon's master's thesis* is worth checking out as well. It demonstrated some equivalence between electrical circuits and boolean algebra, and was one of the key ideas that enabled digital computers. * https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_and_Switching_Circuits https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
- B1FF_PSUVM 2y ago
  The funny thing is that, at the time, digital logic circuits were made with relays. For most of the XX century you could hear relays clacking away at street junctions, inside metal boxes controlling traffic lights. Then you got bipolar junction transistors (BJTs), and most digital logic, such as ECL and TTL, was based on a different paradigm for a few decades. Then came the MOS revolution, allowing for large scale integration. And it worked like relays used to, but Shannon's work was mostly forgotten by then.
  - mturmon 2y ago
    > Then you got bipolar junction transistors (BJTs), and most digital logic, such as ECL and TTL, was based on a different paradigm for a few decades. I think the emphasis is misplaced here. It is true that a single BJT, when considered as a three terminal device, does not operate in the same “gated” way as a relay and a CMOS gate does. But the BJT components still were integrated into chips, or assembled into standard design blocks that implemented recognizable Boolean operations, and synthesis of desired logical functions would use tools like Karnaugh maps that were (as I understand it) outgrowths of Shannon’s approach.
  - kragen 2y ago
    i don't think traffic light control systems were designed with boolean logic before shannon, nor were they described as 'logic' (or for that matter 'digital')
- egl2021 2y ago
  This is my candidate for the most influential master's thesis ever.
ShaneCurran 2y ago
Not many know about it, but this paper (written in 1948) stemmed from a lesser-known paper Shannon wrote in 1945 called "A Mathematical Theory of Cryptography"[0]. [0]: https://evervault.com/papers/shannon https://evervault.com/papers/shannon
- mercacona 2y ago
  Wow! Could you suggest some extra bibliography that discusses this?
SatvikBeri 2y ago
Among other things, this paper is surprisingly accessible. You can give it to a beginner without much math background and they'll be able to understand it. I actually find it better than most modern books on information theory.
kouru225 2y ago
Always upvote Shannon
dilawar 2y ago
I find it incredible how "simple" were his theories and enormous impact they had. Is there anyone else who developed such seemingly "simple" theories?
- deleted 2y ago
  [deleted]
- robrenaud 2y ago
  Newton.
ImageXav 2y ago
If anyone is on the fence about reading this, or worried about their ability to comprehend the content, I would tell you to go ahead and give it a chance. Shannon's writing is remarkably lucid and transparent. The jargon is minimal, and his exposition is fantastic. As many other commentators has mentioned, it is impressive that such an approachable paper would lay the foundations for a whole field. I actually find that many subsequent textbooks seem to obfuscate the simplicity of the idea of entropy. Two examples from the paper really stuck with me. In one, he discusses the importance of spaces for encoding language, something which I had never really considered before. In the second, he discusses how it is the redundancy of language that allows for crosswords, and that a less redundant language would make it harder to design these (unless we started making them 3D!). It made me think more deeply about communication as a whole.
- jp42 2y ago
  I am one of the few who is on the fence. This comment motivates me to give it try to this paper. Thanks ImageXav!
- jessriedel 2y ago
  Agreed. This is one of the all time great papers in that it both launched an entire field (information theory) and remains very accessible and pedagogical. A true gem.
- Anon84 2y ago
  He also creates the first (at least that I could find) instance of a auto-regressive (markovian) language model as a clarifying example in the first 10 pages :)
- contingencies 2y ago
  > Two examples from the paper really stuck with me. In one, he discusses the importance of spaces for encoding language, something which I had never really considered before. As a westerner who has studied quite a few writing systems this is kind of hard to interpret. Verbally however, the timing of pauses are important in all languages I've learned. This would be a more coherent argument to place at the pan-lingual level than one related to written representation, which is pretty arbitrary (many languages have migrated scripts over the years, see for example the dual mode devanagari/arabic hindu/urdu divide, many other languages migrating to arabic, phagspa, vietnamese moving from chinese to french diacritics, etc.). > In the second, he discusses how it is the redundancy of language that allows for crosswords, and that a less redundant language would make it harder to design these (unless we started making them 3D!). It made me think more deeply about communication as a whole. Yeah, good luck making a Chinese crossword. Not sure "redundancy" is the right term, however. Perhaps "frequent [even tediously repetitive?] glyph reuse".
loph 2y ago
Shannon did a lot more interesting things than just this paper. If you become more interested in Claude Shannon, I recommend the biography "A Mind At Play" https://en.wikipedia.org/wiki/A_Mind_at_Play https://en.wikipedia.org/wiki/A_Mind_at_Play A very interesting person.
- JoeDaDude 2y ago
  Agreed, One niche interest of mine is his treatment of board games and the machines he built to play them. https://boardgamegeek.com/geeklist/143233/claude-shannon-the-man-the-games-and-the-machines https://boardgamegeek.com/geeklist/143233/claude-shannon-the...
pid-1 2y ago
As an undergrad I struggled to understand why log was used to measure information. Could not find a reason in any textbook. Took a deep breath and decided to download and read this paper. Surprise, surprise: it's super approachable and the reasoning for using log is explained on the first page.
- bmdac 2y ago
  [dead]
FarhadG 2y ago
I recently went through two books: (1) Fortune's Formula and (2) A Man for All Markets. They both impressed upon me a deep appreciation for Shannon's brilliant mind. Curious if there are any great resources/books you'd recommend on Information Theory.
- fat_cantor 2y ago
  Cover & Thomas
- JoeDaDude 2y ago
  An Introduction to Information Theory Symbols, Signals & Noise By John Robinson Pierce https://www.google.com/books/edition/An_Introduction_to_Information_Theory/QFw6DwAAQBAJ?hl=en&gbpv=0 https://www.google.com/books/edition/An_Introduction_to_Info...
- chrispeel 2y ago
  * The Idea Factory (https://en.wikipedia.org/wiki/The_Idea_Factory https://en.wikipedia.org/wiki/The_Idea_Factory) includes info on Kelly (https://en.wikipedia.org/wiki/Kelly_criterion https://en.wikipedia.org/wiki/Kelly_criterion) as well as Shannon. * A Mind at Play (https://en.wikipedia.org/wiki/A_Mind_at_Play https://en.wikipedia.org/wiki/A_Mind_at_Play) is a bio of Shannon. I think a much better bio could be written, but this is all we have. * "Information Theory" by Cover and Thomas is a mathematical introduction to information theory. This is a technical book, and is very different than the books above. If you haven't yet done so, read Shannon's paper as linked above
groovimus 2y ago
Shannon's original paper on the topic was written during WWII and I believe it was classified and is much more concise as an introduction. After that, he and Weaver put together the famous and much more comprehensive 1948 paper which expanded into the noisy coding theorem. Meanwhile his original paper ("Communication in the Presence of Noise") was published in 1949, possibly after declassification. I highly recommend reading it first, taking maybe an hour to read. Another terrific intro is a chapter of a book by Bruce Carlson: "Communication Systems: An Introduction to Signals and Noise..." I have a scan of the chapter linked here: https://drive.google.com/file/d/0B9oyGOnmkS7GTFlmQ2F1RWNFd28/view?usp=drivesdk&resourcekey=0-1XuLeFM81UbGviMW3ONqNQ https://drive.google.com/file/d/0B9oyGOnmkS7GTFlmQ2F1RWNFd28...
aragonite 2y ago
The LaTeX code can be found at [1] (.tar.gz) or by clicking the 'directory' link towards the bottom of page [2]. [1] https://web.archive.org/web/20080516051043/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.tar.gz https://web.archive.org/web/20080516051043/http://cm.bell-la... [2] https://web.archive.org/web/20080516051043/http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html https://web.archive.org/web/20080516051043/http://cm.bell-la...
intalentive 2y ago
Shannon:Kolmogorov::LLMs:minds

298 points by luu 2y ago

my holy book

I use this paper whenever I teach information theory. If you are mathematically inclined, I’d recommend you to read the demonstration of his two main theorems, it’s illuminating.

the_panopticon 2y ago

Another great read from Shannon https://archive.org/details/bstj28-4-656 https://archive.org/details/bstj28-4-656

mehulashah 2y ago

When you read this and think about the world he was in — it’s even more remarkable. How did he come up with it?

082349872349872 2y ago
From playing 20 Questions and attempting to formalise it? EDIT: actually the cryptography connection is more likely: Leibniz was XVII; who was it that was already using binary alternatives for steganography a few centuries earlier? EDIT2: did entropy in p-chem come before or after Shannon? EDIT3: well before; S = k_B ln Ω was 1877.
duped 2y ago
This is apocryphal, but it probably had something to do with dropping shells on Nazis - he was developing fire control systems for the US Navy around the time he developed the theorem, and only published several years after the War. Allegedly he also derived Mason's Gain Formula around the same time but that was classified until Mason published it.

shalabhc 2y ago

While well known for this paper and "information theory", Shannon's master's thesis* is worth checking out as well. It demonstrated some equivalence between electrical circuits and boolean algebra, and was one of the key ideas that enabled digital computers. * https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_and_Switching_Circuits https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...

B1FF_PSUVM 2y ago
The funny thing is that, at the time, digital logic circuits were made with relays. For most of the XX century you could hear relays clacking away at street junctions, inside metal boxes controlling traffic lights. Then you got bipolar junction transistors (BJTs), and most digital logic, such as ECL and TTL, was based on a different paradigm for a few decades. Then came the MOS revolution, allowing for large scale integration. And it worked like relays used to, but Shannon's work was mostly forgotten by then.
- mturmon 2y ago
  > Then you got bipolar junction transistors (BJTs), and most digital logic, such as ECL and TTL, was based on a different paradigm for a few decades. I think the emphasis is misplaced here. It is true that a single BJT, when considered as a three terminal device, does not operate in the same “gated” way as a relay and a CMOS gate does. But the BJT components still were integrated into chips, or assembled into standard design blocks that implemented recognizable Boolean operations, and synthesis of desired logical functions would use tools like Karnaugh maps that were (as I understand it) outgrowths of Shannon’s approach.
- kragen 2y ago
  i don't think traffic light control systems were designed with boolean logic before shannon, nor were they described as 'logic' (or for that matter 'digital')
egl2021 2y ago
This is my candidate for the most influential master's thesis ever.

ShaneCurran 2y ago

Not many know about it, but this paper (written in 1948) stemmed from a lesser-known paper Shannon wrote in 1945 called "A Mathematical Theory of Cryptography"[0]. [0]: https://evervault.com/papers/shannon https://evervault.com/papers/shannon

mercacona 2y ago
Wow! Could you suggest some extra bibliography that discusses this?

SatvikBeri 2y ago

Among other things, this paper is surprisingly accessible. You can give it to a beginner without much math background and they'll be able to understand it. I actually find it better than most modern books on information theory.

kouru225 2y ago

Always upvote Shannon

dilawar 2y ago

I find it incredible how "simple" were his theories and enormous impact they had. Is there anyone else who developed such seemingly "simple" theories?

deleted 2y ago
[deleted]
robrenaud 2y ago
Newton.

ImageXav 2y ago

If anyone is on the fence about reading this, or worried about their ability to comprehend the content, I would tell you to go ahead and give it a chance. Shannon's writing is remarkably lucid and transparent. The jargon is minimal, and his exposition is fantastic. As many other commentators has mentioned, it is impressive that such an approachable paper would lay the foundations for a whole field. I actually find that many subsequent textbooks seem to obfuscate the simplicity of the idea of entropy. Two examples from the paper really stuck with me. In one, he discusses the importance of spaces for encoding language, something which I had never really considered before. In the second, he discusses how it is the redundancy of language that allows for crosswords, and that a less redundant language would make it harder to design these (unless we started making them 3D!). It made me think more deeply about communication as a whole.

jp42 2y ago
I am one of the few who is on the fence. This comment motivates me to give it try to this paper. Thanks ImageXav!
jessriedel 2y ago
Agreed. This is one of the all time great papers in that it both launched an entire field (information theory) and remains very accessible and pedagogical. A true gem.
Anon84 2y ago
He also creates the first (at least that I could find) instance of a auto-regressive (markovian) language model as a clarifying example in the first 10 pages :)
contingencies 2y ago
> Two examples from the paper really stuck with me. In one, he discusses the importance of spaces for encoding language, something which I had never really considered before. As a westerner who has studied quite a few writing systems this is kind of hard to interpret. Verbally however, the timing of pauses are important in all languages I've learned. This would be a more coherent argument to place at the pan-lingual level than one related to written representation, which is pretty arbitrary (many languages have migrated scripts over the years, see for example the dual mode devanagari/arabic hindu/urdu divide, many other languages migrating to arabic, phagspa, vietnamese moving from chinese to french diacritics, etc.). > In the second, he discusses how it is the redundancy of language that allows for crosswords, and that a less redundant language would make it harder to design these (unless we started making them 3D!). It made me think more deeply about communication as a whole. Yeah, good luck making a Chinese crossword. Not sure "redundancy" is the right term, however. Perhaps "frequent [even tediously repetitive?] glyph reuse".

loph 2y ago

Shannon did a lot more interesting things than just this paper. If you become more interested in Claude Shannon, I recommend the biography "A Mind At Play" https://en.wikipedia.org/wiki/A_Mind_at_Play https://en.wikipedia.org/wiki/A_Mind_at_Play A very interesting person.

JoeDaDude 2y ago
Agreed, One niche interest of mine is his treatment of board games and the machines he built to play them. https://boardgamegeek.com/geeklist/143233/claude-shannon-the-man-the-games-and-the-machines https://boardgamegeek.com/geeklist/143233/claude-shannon-the...

pid-1 2y ago

As an undergrad I struggled to understand why log was used to measure information. Could not find a reason in any textbook. Took a deep breath and decided to download and read this paper. Surprise, surprise: it's super approachable and the reasoning for using log is explained on the first page.

bmdac 2y ago
[dead]

FarhadG 2y ago

I recently went through two books: (1) Fortune's Formula and (2) A Man for All Markets. They both impressed upon me a deep appreciation for Shannon's brilliant mind. Curious if there are any great resources/books you'd recommend on Information Theory.

fat_cantor 2y ago
Cover & Thomas
JoeDaDude 2y ago
An Introduction to Information Theory Symbols, Signals & Noise By John Robinson Pierce https://www.google.com/books/edition/An_Introduction_to_Information_Theory/QFw6DwAAQBAJ?hl=en&gbpv=0 https://www.google.com/books/edition/An_Introduction_to_Info...
chrispeel 2y ago
* The Idea Factory (https://en.wikipedia.org/wiki/The_Idea_Factory https://en.wikipedia.org/wiki/The_Idea_Factory) includes info on Kelly (https://en.wikipedia.org/wiki/Kelly_criterion https://en.wikipedia.org/wiki/Kelly_criterion) as well as Shannon. * A Mind at Play (https://en.wikipedia.org/wiki/A_Mind_at_Play https://en.wikipedia.org/wiki/A_Mind_at_Play) is a bio of Shannon. I think a much better bio could be written, but this is all we have. * "Information Theory" by Cover and Thomas is a mathematical introduction to information theory. This is a technical book, and is very different than the books above. If you haven't yet done so, read Shannon's paper as linked above

groovimus 2y ago

Shannon's original paper on the topic was written during WWII and I believe it was classified and is much more concise as an introduction. After that, he and Weaver put together the famous and much more comprehensive 1948 paper which expanded into the noisy coding theorem. Meanwhile his original paper ("Communication in the Presence of Noise") was published in 1949, possibly after declassification. I highly recommend reading it first, taking maybe an hour to read. Another terrific intro is a chapter of a book by Bruce Carlson: "Communication Systems: An Introduction to Signals and Noise..." I have a scan of the chapter linked here: https://drive.google.com/file/d/0B9oyGOnmkS7GTFlmQ2F1RWNFd28/view?usp=drivesdk&resourcekey=0-1XuLeFM81UbGviMW3ONqNQ https://drive.google.com/file/d/0B9oyGOnmkS7GTFlmQ2F1RWNFd28...

aragonite 2y ago

The LaTeX code can be found at [1] (.tar.gz) or by clicking the 'directory' link towards the bottom of page [2]. [1] https://web.archive.org/web/20080516051043/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.tar.gz https://web.archive.org/web/20080516051043/http://cm.bell-la... [2] https://web.archive.org/web/20080516051043/http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html https://web.archive.org/web/20080516051043/http://cm.bell-la...

intalentive 2y ago

Shannon:Kolmogorov::LLMs:minds