Half bit storage

Mezzo bit

Come possiamo immagazzinare mezzo bit di informazione?

Una storage unit da 1 bit immagazzina, appunto, 1 bit. Consideriamo però una storage unit difettosa, che può portare a un bit flip in lettura con una data probabilità p.

Se p = 0, abbiamo il caso iniziale, cioè con nessun difetto.

Se p = 1/2, il numero letto sarà completamente casuale; è quindi sostanzialmente impossibile immagazzinare informazione, e intuitivamente l'informazione immagazzinata sarà appunto 0 bit.

Ma se 0 < p < 1/2? Per p molto vicino a 0, ha senso che l'informazione sia vicina a 1 bit, ma leggermente meno. Così come per p vicino a 1/2, avrò poca informazione, ma più di 0 bit. L'informazione dovrà variare in modo continuo tra 1 bit e 0 bit al variare di p tra 0 e 1/2.

Per ottenere p per cui si hanno 0.5 bit, notiamo che dopo un'osservazione avremo due casi possibili: il bit è flippato, con probabilità p, o è originale, con probabilità 1 - p.

Utilizziamo la teoria dell'informazione di Shannon. Calcoliamo l'entropia di Shannon:

H(p) = -p log₂(p) - (1 - p) log₂(1 - p)

A questo punto, l'informazione immagazzinata sarà:

I(p) = 1 - H(p)

Numericamente, se 1 - H(p) = 1/2, cioè H(p) = 1/2, la probabilità che risolve l'equazione è circa:

p = 0.110027... ≈ 11.0%

Half a Bit

How can we store half a bit of information?

A 1-bit storage unit stores, by definition, 1 bit. Now consider a defective storage unit, where reading it may cause a bit flip with some probability p.

If p = 0, we are back to the initial case: with no defect.

If p = 1/2, the value we read is completely random. It is therefore essentially impossible to store information, and intuitively the stored information is exactly 0 bits.

But what if 0 < p < 1/2? For p very close to 0, it makes sense for the information to be close to 1 bit, but slightly less. Likewise, for p close to 1/2, we will have little information, but more than 0 bits. The information must vary continuously from 1 bit to 0 bits as p varies from 0 to 1/2.

To find p such that we have 0.5 bits, note that after one observation there are two possible cases: the bit has been flipped, with probability p, or it is still the original bit, with probability 1 - p.

We use Shannon information theory. We compute the Shannon entropy:

H(p) = -p log₂(p) - (1 - p) log₂(1 - p)

At this point, the stored information is:

I(p) = 1 - H(p)

Numerically, if 1 - H(p) = 1/2, that is H(p) = 1/2, the probability solving the equation is approximately:

p = 0.110027... ≈ 11.0%