1
$\begingroup$

I was reading about how there is an upper limit to how fast information can be transmitted over a given channel - the Shannon–Hartley theorem.

I was wondering how this theorem works with codebooks. For example, say my friend and I share a codebook that maps every possible grammatical sentence to an integer.

Then no matter how complex a sentence I want to make, all I need to do is send that single integer! Sure, such a codebook would be huge, huge, huge. But does that matter? I was still able to communicate a sentence of arbitrary complexity just by sending a single number.

Basically, does the Shannon–Hartley theorem take into consideration the size of the codebooks approaching infinity? The codebook itself wouldn't need to be transmitted since we can have a copy sitting with us in advance. Or perhaps do a look up in a database.

If the numbers get very large, my friend and I can work in hexadecimal. Or even a number system with 200 characters. That would cut down the size of the numbers considerably.

I know all this is impractical. I'm just curious about how it works in principle...

$\endgroup$

closed as off-topic by CuriousOne, sammy gerbil, Jim, knzhou, ACuriousMind Aug 8 '16 at 21:38

  • This question does not appear to be about physics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Apart from the difficulty that your codebook could probably not encode Shakespeare, at best you are getting a constant (and relatively small) coding gain that eliminates the inefficiency of the English language. Since English allows to make sentences of infinite length your codebook can never be finite. None of this is physics, though. $\endgroup$ – CuriousOne Aug 6 '16 at 23:18
  • 2
    $\begingroup$ The problem is that your "codes" would be almost as long as the thing you're encoding! Moving to a higher base (hexadecimal) doesn't help because then transmitting each digit is harder. $\endgroup$ – knzhou Aug 6 '16 at 23:23
  • 1
    $\begingroup$ The reason is that bigger cookbooks get you closer to the optimal bound, as you've noticed for English words. So in the infinite limit you get the optimal bound. $\endgroup$ – knzhou Aug 7 '16 at 5:21
  • 1
    $\begingroup$ Whether or not a really big cookbook is practically useful depends on the application. This site isn't the place to ask that question. $\endgroup$ – knzhou Aug 7 '16 at 5:21
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because it is about mathematical theorems in theoretical computer science, not physics $\endgroup$ – Jim Aug 8 '16 at 20:02
2
$\begingroup$

Information held in an integer can never be more than 32 bits, if the integer is a 32-bit quantity. It can never be more than 64 bits, if the integer is a 64-bit quantity. Your hypothetical codebook will either limit the message (just as Morse code only handled the Latin alphabet), or it will grow very large for a wide set of sentences (including short ones).

The best 'codebook' scheme we know is Lempel-Ziv compression, which builds a set of codes based on the repeating elements (words, phrases, whatever) in the messages of interest.

A modern implementation is described in Terry A. Welch, "A Technique for High Performance Data Compression", IEEE Computer, Vol. 17, No. 6, 1984

The Shannon-Hartley theorem is in no danger from such schemes; like 'simplified spelling' they may reduce the number of symbols, but only for predictable-pattern text; compression of random-number tables does NOT work well.

$\endgroup$
  • $\begingroup$ Is there a problem in principle if the codebook grows very large? After all, we're not transmitting the codebook itself am I right? So no matter how large the codebook is and no matter how long it takes to look something up, we will ultimately just need to transmit an integer - in however many bits it requires. $\endgroup$ – Bhagwad Jal Park Aug 7 '16 at 4:18
  • $\begingroup$ Suppose, however, instead of 'a sentence', what I wish to transmit is a 64-bit binary number? What codebook can do that, which does NOT have 64-bits length of its lookup integer? Now, reconsider the question with an arbitrary length binary number. Shannon's theorem predicted this would not exceed his limit, and it appears Shannon was correct. $\endgroup$ – Whit3rd Aug 7 '16 at 6:24
  • $\begingroup$ You're right - I tried to see if instead of sending a number, I could send it's square root instead and saw that I needed to use an equivalent number of floating points to reconstruct it. Or maybe I'm missing some more efficient way. In any case, you're saying that the Shannon theorem will work even for codebooks approaching infinite size is that correct? $\endgroup$ – Bhagwad Jal Park Aug 7 '16 at 13:55
  • $\begingroup$ Yes, the Shannon limit applies to codebook schemes of any length. If one were to always speak in quotations from Bartlett's Quotations, you'd only need integers up to 8000 or so, but it'd be hard to express 'pi =3.14159'. So the codebook loses efficiency in some messages as it gains in others. $\endgroup$ – Whit3rd Aug 8 '16 at 3:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.