Blundell Thermal Physics · Problem 15.2

Information theory

Physics — Statistical Mechanics · shannon-entropy-logic-gates

Problem

A particular logic gate takes two binary inputs

A

and

B

and has two binary outputs

A'

and

B'

. Its truth table is

\begin{array}{cc|cc} A & B & A' & B' \\ \hline 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{array}

and the operations producing these outputs are

A' = \text{NOT}\, A

and

B' = \text{NOT}\, B

. The input has a Shannon entropy of 2 bits. Show that the output has a Shannon entropy of 2 bits. A second logic gate has a truth table given by

\begin{array}{cc|cc} A & B & A' & B' \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array}

This can be achieved using

A' = A\, \text{OR}\, B

and

B' = A\, \text{AND}\, B

. Show that the output now has an entropy of

\frac{3}{2}

bits. What is the crucial difference between the two logic gates?