Question

Hello, please keep the solutions simple and understandable, I am not a computer scientist. Thank you!

1.1. How many bits are necessary to represent the alphabet using a binary code if we only allow uppercase characters? How about if we allow both uppercase and lowercase characters? 1.2. Describe how you can create an OR gate using NOT gates and AND gates. 1.3. A kilobyte is 1024 bytes. How many messages can it store? 1.4. What is the entropy associated with the tossing of a fair coin? 1.5. Suppose that X consists of the characters A. B, C, D that occur in a signal with respective probabilities 0.1, 0.4, 0.25, and 0.25. What is the Shannon entropy? 1.6. A room full of people has incomes distributed in the following way: (25.5)3 n(30)5 (42)7 n(63) 1 (90)1 What is the most probable income? What is the average income? What is the variance of this distribution?

Answer 1

1)

You would only need 5 bits because you are counting to 26 (if we take only upper or lowercase letters). 5 bits will count up to 31, so you've actually got more space than you need. You can't use 4 because that only counts to 15.

If you want both upper and lowercase then 6 bits is your answer - 6 bits will happily count to 63, while your double alphabet has (2 * 24 = 48) characters, again leaving plenty of headroom.

2)

De Mof g ons A-A) (e.el

well a NAND gate is a combination of NOT and AND Y=(AB)'

3)

1,024 bytes make up a kilobyte or KB.

Assume a 100-word paragraph with each word containing 5 characters. So, 1 KB would represent approximately two paragraphs.

4)

A fair coin has two sides — picture one side with a 0 (zero), and the other side a 1 (one). The only possible results of tossing this coin is to see either the 0 or the 1 side (ignoring the remote possibility that the coin ends up standing on the side).

That “information” — which of the two sides that came up at the coin toss — can be stored in one data bit, but to call that bit “information” is a bit of a misnomer (no pun intended):

t is the number of bits needed on average to store an outcome. Clearly one bit.

Formal answer: the probability distribution of a fair coin has P(heads)=P(tails)=1/2P(heads)=P(tails)=1/2. (This is called a Bernoulli distribution.) The entropy of a discrete distribution is defined as follows:

H(P)=∑xP(x)⋅log(1/P(x)).H(P)=∑xP(x)⋅log⁡(1/P(x)).

In our case, this is

H(P)=P(heads)⋅log(1/P(heads))+P(tails)⋅log(1/P(tails)).H(P)=P(heads)⋅log⁡(1/P(heads))+P(tails)⋅log⁡(1/P(tails)).

We can substitute these probabilities to find

H(P)=1/2⋅log(2)+1/2⋅log(2)=1/2+1/2=1,H(P)=1/2⋅log⁡(2)+1/2⋅log⁡(2)=1/2+1/2=1,

at least if we take log to base two.

So the entropy is one bit.