10
$\begingroup$

until today I knew that one bit is a variable, or a space in memory that can hold a value of either One (high) or Zero (low). This is the concept I learned from studying computer programming, microprocessor or DATA bus etc.

But after starting the course on information theory, I found out that bit is expressed as the information content of a symbol in message. This is calculated taking the logarithm (base 2) of the inverse of the probability of occurrence of the symbol.

Are these two concepts same ? On one hand one bit is a variable that can store either zero or one. On the other hand, one bit is the uncertainty associated with one of two symbols with probability of occurrence of 0.5. So, does 1 bit in computer programming or ASCII code mean 1 bit in information content of source or information theory?

A little edit: here is one thing I am finding trouble understanding this topic. See, in data transfer of English alphabets, if we use ASCII code, we basically represent each symbol with 8 bits. Suppose that's 00000000 for a, 00000001 for b etc. So we are essentially allocating 8 quantization levels for each symbol.

But when the information theory comes into play, we take the probability of each symbol into account. 'E' has the highest frequency, where 'Z' has the lowest. So average information content comes down to 3 or 4 bits, right ?

My book says, 'Entropy or average information content is the minimum average number of bits required to represent each sample without distortion'.So, in this case, for efficient data transfer, are we creating maximum four quantization levels for each symbols? Because, on an average they carry information worth 4 bits. If that's so, isn't bit in information theory the same as the one in computer programming, data transfer or ASCII code etc ?

You probably get that I am clearly a noob here :p

Improve this question
$\endgroup$
4
  • $\begingroup$ one thing to add to MBaz's answer is that the scaling of the "bit" in information theory is such that it the same as "bits" in computer memory. there are other units of information in Shannon IT. whatever multiplies the $I(m) = -C\log(P(m))$ function. if it's $C= \frac{1}{\log(2)}$ that scales the log function, then $I(m)$ is in bits. $\endgroup$
    – robert bristow-johnson
    Commented Oct 15, 2015 at 0:21
  • $\begingroup$ @robertbristow-johnson, that's a good point. $\endgroup$
    – MBaz
    Commented Oct 15, 2015 at 12:35
  • 1
    $\begingroup$ Huffman coding tries to reach the information theoretic bound by assigning fewer bits to frequent symbols. This is an approximate process as the true frequencies are unknown, and as the number of bits must remain an integer. Arithmetic coding does better and manages to pack using fractional number of bits per symbols. $\endgroup$
    – user7657
    Commented Oct 16, 2015 at 8:14
  • $\begingroup$ the frequencies (say, of characters, if it's a text file) can be known by counting. also different symbols (with a fractional number of bits) can be grouped together into a single compound message that has close to an integer number of bits. but it will always be less efficient than the theoretic bound. $\endgroup$
    – robert bristow-johnson
    Commented Oct 18, 2015 at 3:31

3 Answers 3

Reset to default
10
$\begingroup$

They are not the same, but they're related. In particular, if you look at a computer memory holding $M$ "computer" bits, where each bit can be considered random and independent of all other bits, and there are roughly 50% of zeros, then the memory also holds roughly $M$ "information theory" bits.

Of course, this is often not the case: computer bits are usually correlated, and not uniformly random. This is why they can be compressed. Compressor programs such as LZW ("source coders" in information theory parlance) work, in a sense, by making each computer bit hold one information bit.

Edited to add: This example may make the distinction clearer. Consider a memoryless source with two outputs, $m_1=000$ and $m_2=001$, with probability 0.5 for each. Clearly, the information in each message is one (information) bit, but its length is three (computer) bits. A source coder, such as the Huffman algorithm, will readily code the messages to $c_1=0$ and $c_2=1$, compressing the source output. You can easily extrapolate this example to a source that produces ASCII-encoded text.

Note that, in the case of written languages in general and English in particular, nobody knows what the actual source entropy is, because there is no model for it. That is why there are contests for the best compression of large bodies of text; nobody is really sure what the optimum compression algorithm for English is.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks MBaz . But here is one thing I am finding trouble understanding this topic. See, in data transfer of English alphabets, if we use ASCII code, we basically represent each symbol with 8 bits. Suppose that's 00000000 for a, 00000001 for b etc. So we are essentially allocating 8 quantization levels for each symbol. But when the information theory comes into play, we take the probability of each symbol into account. 'E' has the highest frequency, where 'Z' has the lowest. So average information content comes down to 3 or 4 bits, right ? $\endgroup$
    – benjamin
    Commented Oct 14, 2015 at 22:42
  • $\begingroup$ @benjamin, that is right, and that's the reason text can be compressed so much. It contains much less information than the number of (computer) bits used to represent it. $\endgroup$
    – MBaz
    Commented Oct 14, 2015 at 23:44
  • $\begingroup$ Hi, I posted the comment in the answer section in detail actually as it was getting too long. Must have forgotten to delete it. btw, that basically means that text symbols contain 3 to 4 bits worth of information whereas we use 8 bits to transfer them, right? So they contain useless bits or redundancy. So, for efficient data transfer, we can encode them using less bits and thus compress them. That means we can create lesser quantization levels to encode them. Previously we created 8 quantization levels, but now 4 quantization levels would be enough. $\endgroup$
    – benjamin
    Commented Oct 15, 2015 at 0:05
  • $\begingroup$ One quantization level is 1 binary digit bit. So now we can use lesser quantization levels or less binary digit bits. So aren't we considering binary digit bits and quantization bits as basically the same thing ? Back then, we used 8 bits to transmit a single symbol. But now we know the symbols are worth only 4 bits of information on average. So we are sending them using 4 quantization levels or 4 binary digit bits, because they carry 4 bits of information. In fact I tried to learn a little about Hoffman coding on my own, but here is where I got really stuck. $\endgroup$
    – benjamin
    Commented Oct 15, 2015 at 0:09
  • $\begingroup$ @benjamin, I think you're on the right track here. Think about it this way, when the text (or any computer file or date) is perfectly compressed, every computer bit in it will carry one information bit. $\endgroup$
    – MBaz
    Commented Oct 15, 2015 at 0:52
2
$\begingroup$

Bit is a unit of measurement and multiple quantities are measured in bits. It's not that bit in programming and information theory mean different things. It's that memory and information content represent conceptually different quantities.

For example we can take the password ''123456''. If encoded in UTF-8, it requires 6 * 8 = 48 bits of memory. For real world purposes, its information content is about 10 bits. Bit means the same in both cases, the quantity that is measured is what is different. If you compress the password, the amount of memory it takes decreases, but the information content won't change.

One analogy: Physical quantities like gravity and electromagnetic force are both measured in Newtons but represent different types of interactions. You can empirically see that the unit Newton represents the same idea in both cases - gravity and electromagnetic force can balance each other (magnetic levitation).

I hope that helps :)

Improve this answer
$\endgroup$
0
$\begingroup$

On the data bus, we can in theory do better than information theory says. I know how to construct a circuit that will let me send 8 bits in parallel down 6 wires. This involves a trick using diodes and pull up/down resistors that allows using all three non-burning states of a digital wire for conveying information. With 3 states of 6 lines, I get 729 possible states, which allows me to carry EOF, INT, CLK, and disconnected in the main channel and still have plenty of room (this only uses 518 of the 729 states).

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Now that's just redefining the channel and adding memory ;) $\endgroup$
    – bright-star
    Commented Oct 15, 2015 at 6:02
  • 1
    $\begingroup$ What trevor said. You implicitely assume that the "information theorist" just uses the channel once every symbol duration to send 1 information of either H or L, but if you add states, you're doing something that is not the same :) $\endgroup$
    – Marcus Müller
    Commented Oct 15, 2015 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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