A space probe is controlled by 7 different instructions from the ground. the probabilities of sending these instructions vary -
the three most common instructions have probabilities 1/2, 1/4, and 1/8 of being sent, respectively. the remaining four instructions are equally likely to be sent. in expectation, what is the minimum number of whole number bits required to communicate with the probe?
<span>2
This question pertains to entropy and Shannon information density. We'll consider the base 2 logarithm of the probability for each command. For simplicity, I will represent the commands as a, b, c, d, e, f, g, with the most frequent ones listed first. The commands, their probabilities, and the base 2 logarithms are as follows:
a: 0.5, -1
b: 0.25, -2
c: 0.125, -3
d: 0.03125, -5
e: 0.03125, -5
f: 0.03125, -5
g: 0.03125, -5
Next, we will negate each of the base 2 logarithms to get the values 1, 2, 3, 5, 5, 5, 5. These figures indicate the number of bits of information that correspond to each command. Since command "a" occurs half the time, only one bit is needed. Command "b" requires 2 bits, and similarly for the others up to the remaining 5 commands. Therefore, the expected number of bits to be sent can be calculated as the probability of each command multiplied by the number of bits needed to represent that command. Thus:
0.5 * 1 + 0.25 * 2 + 0.125 * 3 + 0.03125 * 5 + 0.03125 * 5 + 0.03125 * 5 + 0.03125 * 5
= 0.5 + 0.5 + 0.375 + 0.15625 + 0.15625 + 0.15625 + 0.15625
= 2
Now, let’s illustrate such an encoding. I will use Huffman coding as an example, but I won't explain how to derive this encoding, as that is outside the scope of this problem. For command "a", I will assign the single bit "0".
a: 0
If the probe observes the bit "0", it understands that command "a" is being transmitted. Conversely, if it sees "1", it recognizes that more bits are on the way for another command. Therefore, for command "b", I will use the sequence "10". So the entire command table could look like this:
a: 0
b: 10
Further expanding, the complete command table could be as follows:
a: 0
b: 10
c: 110
d: 11100
e: 11101
f: 11110
g: 11111
It's important to note that no shorter sequences are prefixes for any longer sequences, enabling the shorter sequences to be acknowledged the moment they've been sent. Moreover, the previous table represents one of many potential encoding schemes.</span>
The space probe must be able to recognize 7 distinct command types. The number of combinations that can be encoded using n bits is 2^n. Thus, the minimum number of bits required to encode at least 7 different commands would be:
